hphp/hhbbc/cfg-opts.cpp

   1 /*
   2    +----------------------------------------------------------------------+
   3    | HipHop for PHP                                                       |
   4    +----------------------------------------------------------------------+
   5    | Copyright (c) 2010-present Facebook, Inc. (http://www.facebook.com)  |
   6    +----------------------------------------------------------------------+
   7    | This source file is subject to version 3.01 of the PHP license,      |
   8    | that is bundled with this package in the file LICENSE, and is        |
   9    | available through the world-wide-web at the following url:           |
  10    | http://www.php.net/license/3_01.txt                                  |
  11    | If you did not receive a copy of the PHP license and are unable to   |
  12    | obtain it through the world-wide-web, please send a note to          |
  13    | license@php.net so we can mail you a copy immediately.               |
  14    +----------------------------------------------------------------------+
  15 */
  16 #include "hphp/hhbbc/cfg-opts.h"
  17
  18 #include <vector>
  19 #include <string>
  20
  21 #include "hphp/hhbbc/analyze.h"
  22 #include "hphp/hhbbc/bc.h"
  23 #include "hphp/hhbbc/cfg.h"
  24 #include "hphp/hhbbc/dce.h"
  25 #include "hphp/hhbbc/unit-util.h"
  26
  27 namespace HPHP { namespace HHBBC {
  28
  29 TRACE_SET_MOD(hhbbc_cfg);
  30
  31 //////////////////////////////////////////////////////////////////////
  32
  33 void remove_unreachable_blocks(const FuncAnalysis& ainfo) {
  34   auto& func = *ainfo.ctx.func;
  35   Trace::Bump bumper{
  36     Trace::hhbbc_cfg, kSystemLibBump, is_systemlib_part(*func.unit)
  37   };
  38   auto done_header = false;
  39   auto header = [&] {
  40     if (done_header) return;
  41     done_header = true;
  42     FTRACE(2, "Remove unreachable blocks: {}\n", func.name);
  43   };
  44
  45   auto make_unreachable = [&](borrowed_ptr<php::Block> blk) {
  46     if (blk->id == NoBlockId) return false;
  47     auto const& state = ainfo.bdata[blk->id].stateIn;
  48     if (!state.initialized) return true;
  49     if (!state.unreachable) return false;
  50     return blk->hhbcs.size() != 2 ||
  51            blk->hhbcs.back().op != Op::Fatal;
  52   };
  53
  54   for (auto const& blk : ainfo.ctx.func->blocks) {
  55     if (!make_unreachable(borrow(blk))) continue;
  56     header();
  57     FTRACE(2, "Marking {} unreachable\n", blk->id);
  58     auto const srcLoc = blk->hhbcs.front().srcLoc;
  59     blk->hhbcs = {
  60       bc_with_loc(srcLoc, bc::String { s_unreachable.get() }),
  61       bc_with_loc(srcLoc, bc::Fatal { FatalOp::Runtime })
  62     };
  63     blk->fallthrough = NoBlockId;
  64     blk->exnNode = nullptr;
  65   }
  66
  67   if (!options.RemoveDeadBlocks) return;
  68
  69   auto reachable = [&](BlockId id) {
  70     if (id == NoBlockId) return false;
  71     auto const& state = ainfo.bdata[id].stateIn;
  72     return state.initialized && !state.unreachable;
  73   };
  74
  75   for (auto const& blk : ainfo.rpoBlocks) {
  76     if (!reachable(blk->id)) continue;
  77     auto reachableTarget = NoBlockId;
  78     auto hasUnreachableTargets = false;
  79     forEachTakenEdge(blk->hhbcs.back(), [&] (BlockId id) {
  80         if (reachable(id)) {
  81           reachableTarget = id;
  82         } else {
  83           hasUnreachableTargets = true;
  84         }
  85       });
  86     if (!hasUnreachableTargets) continue;
  87     header();
  88     switch (blk->hhbcs.back().op) {
  89       case Op::JmpNZ:
  90       case Op::JmpZ:
  91         FTRACE(2, "blk: {} - jcc -> jmp {}\n", blk->id, reachableTarget);
  92         blk->hhbcs.back() = bc_with_loc(blk->hhbcs.back().srcLoc, bc::PopC {});
  93         blk->fallthrough = reachableTarget;
  94         break;
  95       default:
  96         FTRACE(2, "blk: {} -", blk->id, reachableTarget);
  97         forEachTakenEdge(blk->hhbcs.back(), [&] (const BlockId& id) {
  98             if (!reachable(id)) {
  99               FTRACE(2, " {}->{}", id, reachableTarget);
 100               const_cast<BlockId&>(id) = reachableTarget;
 101             }
 102           });
 103         FTRACE(2, "\n");
 104         break;
 105     }
 106   }
 107 }
 108
 109 namespace {
 110
 111 struct MergeBlockInfo {
 112   // This block has a predecessor; used to set the multiplePreds flag
 113   uint8_t hasPred          : 1;
 114   // Block has more than one pred, or is an entry block
 115   uint8_t multiplePreds    : 1;
 116   // Block has more than one successor
 117   uint8_t multipleSuccs    : 1;
 118
 119   // Block contains a sequence that could be part of a switch
 120   uint8_t couldBeSwitch    : 1;
 121   // Block contains a sequence that could be part of a switch, and nothing else
 122   uint8_t onlySwitch       : 1;
 123   // Block follows the "default" of a prior switch sequence
 124   uint8_t followsSwitch    : 1;
 125 };
 126
 127 struct SwitchInfo {
 128   union Case { SString s; int64_t i; };
 129   std::vector<std::pair<Case,BlockId>> cases;
 130   BlockId defaultBlock = NoBlockId;
 131   LocalId switchLoc    = NoLocalId;
 132   DataType kind;
 133 };
 134
 135 bool analyzeSwitch(const php::Block& blk,
 136                    std::vector<MergeBlockInfo>& blkInfos,
 137                    SwitchInfo* switchInfo) {
 138   auto const jmp = &blk.hhbcs.back();
 139   auto& blkInfo = blkInfos[blk.id];
 140
 141   switch (jmp->op) {
 142     case Op::JmpZ:
 143     case Op::JmpNZ: {
 144       if (blk.hhbcs.size() < 4) return false;
 145       auto const& cmp = jmp[-1];
 146       if (cmp.op != Op::Eq && cmp.op != Op::Neq) return false;
 147       auto check = [&] (const Bytecode& arg1, const Bytecode& arg2) -> bool {
 148         LocalId loc;
 149         if (arg2.op == Op::CGetL) {
 150           loc = arg2.CGetL.loc1;
 151         } else if (arg2.op == Op::CGetL2 && &arg2 == &arg1 + 1) {
 152           loc = arg2.CGetL2.loc1;
 153         } else {
 154           return false;
 155         }
 156         SwitchInfo::Case c;
 157         if (arg1.op == Op::Int) {
 158           c.i = arg1.Int.arg1;
 159         } else if (arg1.op == Op::String) {
 160           c.s = arg1.String.str1;
 161         } else {
 162           return false;
 163         }
 164         if (switchInfo) {
 165           auto const dt = arg1.op == Op::Int ? KindOfInt64 : KindOfString;
 166           if (switchInfo->cases.size()) {
 167             if (loc != switchInfo->switchLoc) return false;
 168             if (dt != switchInfo->kind) return false;
 169           } else {
 170             switchInfo->switchLoc = loc;
 171             switchInfo->kind = dt;
 172           }
 173         }
 174         auto const jmpTarget = jmp->op == Op::JmpNZ ?
 175           jmp->JmpNZ.target : jmp->JmpZ.target;
 176         BlockId caseTarget, defaultBlock;
 177         if ((jmp->op == Op::JmpNZ) == (cmp.op == Op::Eq)) {
 178           defaultBlock = blk.fallthrough;
 179           caseTarget = jmpTarget;
 180         } else {
 181           defaultBlock = jmpTarget;
 182           caseTarget = blk.fallthrough;
 183         }
 184         blkInfo.couldBeSwitch = true;
 185         blkInfo.onlySwitch = blk.hhbcs.size() == 4;
 186         blkInfos[defaultBlock].followsSwitch = true;
 187         if (switchInfo) {
 188           switchInfo->cases.emplace_back(c, caseTarget);
 189           switchInfo->defaultBlock = defaultBlock;
 190         }
 191         return true;
 192       };
 193       return check(jmp[-2], jmp[-3]) || check(jmp[-3], jmp[-2]);
 194     }
 195     case Op::Switch:
 196     case Op::SSwitch: {
 197       if (blk.hhbcs.size() < 2) return false;
 198       auto const& cgetl = jmp[-1];
 199       if (cgetl.op != Op::CGetL) return false;
 200       auto const dt = jmp->op == Op::Switch ? KindOfInt64 : KindOfString;
 201       if (switchInfo) {
 202         if (switchInfo->cases.size()) {
 203           if (cgetl.CGetL.loc1 != switchInfo->switchLoc) return false;
 204           if (dt != switchInfo->kind) return false;
 205         } else {
 206           switchInfo->switchLoc = cgetl.CGetL.loc1;
 207           switchInfo->kind = dt;
 208         }
 209       }
 210       if (jmp->op == Op::Switch) {
 211         if (jmp->Switch.subop1 != SwitchKind::Bounded) return false;
 212         auto const db = jmp->Switch.targets.back();
 213         auto const min = jmp->Switch.arg2;
 214         blkInfos[db].followsSwitch = true;
 215         if (switchInfo) {
 216           switchInfo->defaultBlock = db;
 217           for (size_t i = 0; i < jmp->Switch.targets.size() - 2; i++) {
 218             auto const t = jmp->Switch.targets[i];
 219             if (t == db) continue;
 220             SwitchInfo::Case c;
 221             c.i = i + min;
 222             switchInfo->cases.emplace_back(c, t);
 223           }
 224         }
 225       } else {
 226         auto const db = jmp->SSwitch.targets.back().second;
 227         blkInfos[db].followsSwitch = true;
 228         if (switchInfo) {
 229           switchInfo->defaultBlock = db;
 230           for (auto& kv : jmp->SSwitch.targets) {
 231             if (kv.second == db) continue;
 232             SwitchInfo::Case c;
 233             c.s = kv.first;
 234             switchInfo->cases.emplace_back(c, kv.second);
 235           }
 236         }
 237       }
 238       blkInfo.couldBeSwitch = true;
 239       blkInfo.onlySwitch = blk.hhbcs.size() == 2;
 240       return true;
 241     }
 242     default:
 243       return false;
 244   }
 245 }
 246
 247 Bytecode buildIntSwitch(SwitchInfo& switchInfo) {
 248   auto min = switchInfo.cases[0].first.i;
 249   auto max = min;
 250   for (size_t i = 1; i < switchInfo.cases.size(); ++i) {
 251     auto v = switchInfo.cases[i].first.i;
 252     if (v < min) min = v;
 253     if (v > max) max = v;
 254   }
 255   if (switchInfo.cases.size() / ((double)max - (double)min + 1) < .5) {
 256     return { bc::Nop {} };
 257   }
 258   CompactVector<BlockId> switchTab;
 259   switchTab.resize(max - min + 3, switchInfo.defaultBlock);
 260   for (auto i = switchInfo.cases.size(); i--; ) {
 261     auto const& c = switchInfo.cases[i];
 262     switchTab[c.first.i - min] = c.second;
 263     if (c.first.i) switchTab[max - min + 1] = c.second;
 264   }
 265   return { bc::Switch { SwitchKind::Bounded, min, std::move(switchTab) } };
 266 }
 267
 268 Bytecode buildStringSwitch(SwitchInfo& switchInfo) {
 269   std::set<SString> seen;
 270   SSwitchTab sswitchTab;
 271   for (auto& c : switchInfo.cases) {
 272     if (seen.insert(c.first.s).second) {
 273       sswitchTab.emplace_back(c.first.s, c.second);
 274     }
 275   }
 276   sswitchTab.emplace_back(nullptr, switchInfo.defaultBlock);
 277   return { bc::SSwitch { std::move(sswitchTab) } };
 278 }
 279
 280 bool buildSwitches(php::Func& func,
 281                    borrowed_ptr<php::Block> blk,
 282                    std::vector<MergeBlockInfo>& blkInfos) {
 283   SwitchInfo switchInfo;
 284   std::vector<BlockId> blocks;
 285   if (!analyzeSwitch(*blk, blkInfos, &switchInfo)) return false;
 286   blkInfos[blk->id].couldBeSwitch = false;
 287   blkInfos[blk->id].onlySwitch = false;
 288   while (true) {
 289     auto const& bInfo = blkInfos[switchInfo.defaultBlock];
 290     auto const nxt = borrow(func.blocks[switchInfo.defaultBlock]);
 291     if (bInfo.onlySwitch && !bInfo.multiplePreds &&
 292         analyzeSwitch(*nxt, blkInfos, &switchInfo)) {
 293       blocks.push_back(switchInfo.defaultBlock);
 294       continue;
 295     }
 296     bool ret = false;
 297     auto const minSize = switchInfo.kind == KindOfInt64 ? 1 : 8;
 298     if (switchInfo.cases.size() >= minSize && blocks.size()) {
 299       switchInfo.defaultBlock = next_real_block(func, switchInfo.defaultBlock);
 300       auto bc = switchInfo.kind == KindOfInt64 ?
 301         buildIntSwitch(switchInfo) : buildStringSwitch(switchInfo);
 302       if (bc.op != Op::Nop) {
 303         auto it = blk->hhbcs.end();
 304         // blk->fallthrough implies it was a JmpZ JmpNZ block,
 305         // which means we have exactly 4 instructions making up
 306         // the switch (see analyzeSwitch). Otherwise it was a
 307         // [S]Switch, and there were exactly two instructions.
 308         if (blk->fallthrough != NoBlockId) {
 309           it -= 4;
 310         } else {
 311           it -= 2;
 312         }
 313         blkInfos[switchInfo.defaultBlock].multiplePreds = true;
 314         blk->hhbcs.erase(it, blk->hhbcs.end());
 315         blk->hhbcs.emplace_back(bc::CGetL { switchInfo.switchLoc });
 316         blk->hhbcs.push_back(std::move(bc));
 317         blk->fallthrough = NoBlockId;
 318         for (auto id : blocks) {
 319           if (blkInfos[id].multiplePreds) continue;
 320           auto const removed = borrow(func.blocks[id]);
 321           removed->id = NoBlockId;
 322           removed->hhbcs = { bc::Nop {} };
 323           removed->fallthrough = NoBlockId;
 324           removed->factoredExits = {};
 325         }
 326         ret = true;
 327       }
 328     }
 329     return (bInfo.couldBeSwitch && buildSwitches(func, nxt, blkInfos)) || ret;
 330   }
 331 }
 332
 333 template<typename S>
 334 bool strip_exn_tree(const php::Func& func,
 335                     CompactVector<std::unique_ptr<php::ExnNode>>& nodes,
 336                     const std::set<borrowed_ptr<php::ExnNode>> &seenExnNodes,
 337                     uint32_t& nextId,
 338                     S& sectionExits) {
 339   auto it = std::remove_if(nodes.begin(), nodes.end(),
 340                            [&] (const std::unique_ptr<php::ExnNode>& node) {
 341                              if (seenExnNodes.count(borrow(node))) return false;
 342                              FTRACE(2, "Stripping ExnNode {}\n", node->id);
 343                              return true;
 344                            });
 345   auto ret = false;
 346   if (it != nodes.end()) {
 347     nodes.erase(it, nodes.end());
 348     ret = true;
 349   }
 350   for (auto& n : nodes) {
 351     n->id = nextId++;
 352     if (n->parent) {
 353       match<void>(
 354         n->info,
 355         [&] (const php::CatchRegion& cr) {},
 356         [&] (const php::FaultRegion& fr) {
 357           auto pentry = match<BlockId>(
 358             n->parent->info,
 359             [&] (const php::CatchRegion& cr2) { return cr2.catchEntry; },
 360             [&] (const php::FaultRegion& fr2) { return fr2.faultEntry; }
 361           );
 362           auto const sectionId =
 363             static_cast<size_t>(func.blocks[fr.faultEntry]->section);
 364           sectionExits[sectionId].insert(pentry);
 365         });
 366     }
 367     if (strip_exn_tree(func, n->children, seenExnNodes, nextId, sectionExits)) {
 368       ret = true;
 369     }
 370   }
 371
 372   return ret;
 373 }
 374
 375 }
 376
 377 bool rebuild_exn_tree(const FuncAnalysis& ainfo) {
 378   auto& func = *ainfo.ctx.func;
 379   Trace::Bump bumper{
 380     Trace::hhbbc_cfg, kSystemLibBump, is_systemlib_part(*func.unit)
 381   };
 382   FTRACE(4, "Rebuild exn tree: {}\n", func.name);
 383
 384   auto reachable = [&](BlockId id) {
 385     if (id == NoBlockId) return false;
 386     auto const& state = ainfo.bdata[id].stateIn;
 387     return state.initialized && !state.unreachable;
 388   };
 389   std::unordered_map<BlockId,std::set<BlockId>> factoredExits;
 390   std::unordered_map<size_t, std::set<BlockId>> sectionExits;
 391   std::set<borrowed_ptr<php::ExnNode>> seenExnNodes;
 392
 393   for (auto const& blk : ainfo.rpoBlocks) {
 394     if (!reachable(blk->id)) {
 395       FTRACE(4, "Unreachable: {}\n", blk->id);
 396       continue;
 397     }
 398     if (auto node = blk->exnNode) {
 399       auto entry = match<BlockId>(
 400         node->info,
 401         [&] (const php::CatchRegion& cr) { return cr.catchEntry; },
 402         [&] (const php::FaultRegion& fr) { return fr.faultEntry; }
 403       );
 404       factoredExits[blk->id].insert(entry);
 405       do {
 406         if (!seenExnNodes.insert(node).second) break;
 407       } while ((node = node->parent) != nullptr);
 408     }
 409   }
 410
 411   uint32_t nextId = 0;
 412   if (!strip_exn_tree(func, func.exnNodes,
 413                       seenExnNodes, nextId, sectionExits)) {
 414     return false;
 415   }
 416
 417   for (auto const& blk : func.blocks) {
 418     if (!reachable(blk->id)) {
 419       blk->exnNode = nullptr;
 420       continue;
 421     }
 422     auto &fe = factoredExits[blk->id];
 423     auto it = sectionExits.find(static_cast<size_t>(blk->section));
 424     if (it != sectionExits.end()) {
 425       fe.insert(it->second.begin(), it->second.end());
 426     }
 427     auto update = false;
 428     if (blk->factoredExits.size() != fe.size()) {
 429       update = true;
 430       FTRACE(2, "Old factored edges: blk:{} -", blk->id);
 431       for (auto DEBUG_ONLY id : blk->factoredExits) FTRACE(2, " {}", id);
 432       FTRACE(2, "\n");
 433       blk->factoredExits.resize(fe.size());
 434     }
 435
 436     size_t i = 0;
 437     for (auto b : fe) {
 438       if (blk->factoredExits[i] != b) {
 439         assert(update);
 440         blk->factoredExits[i] = b;
 441       }
 442       i++;
 443     }
 444     if (update) {
 445       FTRACE(2, "New factored edges: blk:{} -", blk->id);
 446       for (auto DEBUG_ONLY id : blk->factoredExits) FTRACE(2, " {}", id);
 447       FTRACE(2, "\n");
 448     }
 449   }
 450
 451   return true;
 452 }
 453
 454 bool control_flow_opts(const FuncAnalysis& ainfo) {
 455   auto& func = *ainfo.ctx.func;
 456   Trace::Bump bumper{
 457     Trace::hhbbc_cfg, kSystemLibBump, is_systemlib_part(*func.unit)
 458   };
 459   FTRACE(2, "control_flow_opts: {}\n", func.name);
 460
 461   std::vector<MergeBlockInfo> blockInfo(func.blocks.size(), MergeBlockInfo {});
 462
 463   bool anyChanges = false;
 464
 465   auto reachable = [&](BlockId id) {
 466     auto const& state = ainfo.bdata[id].stateIn;
 467     return state.initialized && !state.unreachable;
 468   };
 469   // find all the blocks with multiple preds; they can't be merged
 470   // into their predecessors
 471   for (auto const& blk : func.blocks) {
 472     if (blk->id == NoBlockId) continue;
 473     auto& bbi = blockInfo[blk->id];
 474     int numSucc = 0;
 475     if (!reachable(blk->id)) {
 476       bbi.multiplePreds = true;
 477       bbi.multipleSuccs = true;
 478       continue;
 479     } else {
 480       analyzeSwitch(*blk, blockInfo, nullptr);
 481     }
 482     auto handleSucc = [&] (BlockId succId) {
 483       auto& bsi = blockInfo[succId];
 484       if (bsi.hasPred) {
 485         bsi.multiplePreds = true;
 486       } else {
 487         bsi.hasPred = true;
 488       }
 489       numSucc++;
 490     };
 491     forEachNormalSuccessor(*blk, [&](const BlockId& succId) {
 492         auto skip = next_real_block(func, succId);
 493         if (skip != succId) {
 494           const_cast<BlockId&>(succId) = skip;
 495           anyChanges = true;
 496         }
 497         handleSucc(succId);
 498       });
 499     for (auto& ex : blk->factoredExits) handleSucc(ex);
 500     if (numSucc > 1) bbi.multipleSuccs = true;
 501   }
 502   blockInfo[func.mainEntry].multiplePreds = true;
 503   for (auto const blkId: func.dvEntries) {
 504     if (blkId != NoBlockId) {
 505       blockInfo[blkId].multiplePreds = true;
 506     }
 507   }
 508
 509   for (auto& blk : func.blocks) {
 510     if (blk->id == NoBlockId) continue;
 511     while (blk->fallthrough != NoBlockId) {
 512       auto nxt = borrow(func.blocks[blk->fallthrough]);
 513       if (blockInfo[blk->id].multipleSuccs ||
 514           blockInfo[nxt->id].multiplePreds ||
 515           blk->exnNode != nxt->exnNode ||
 516           blk->section != nxt->section) {
 517         break;
 518       }
 519
 520       FTRACE(1, "merging: {} into {}\n", (void*)nxt, (void*)blk.get());
 521       auto& bInfo = blockInfo[blk->id];
 522       auto const& nInfo = blockInfo[nxt->id];
 523       bInfo.multipleSuccs = nInfo.multipleSuccs;
 524       bInfo.couldBeSwitch = nInfo.couldBeSwitch;
 525       bInfo.onlySwitch = false;
 526
 527       blk->fallthrough = nxt->fallthrough;
 528       blk->fallthroughNS = nxt->fallthroughNS;
 529       if (nxt->factoredExits.size()) {
 530         if (blk->factoredExits.size()) {
 531           std::set<BlockId> exitSet;
 532           std::copy(begin(blk->factoredExits), end(blk->factoredExits),
 533                     std::inserter(exitSet, begin(exitSet)));
 534           std::copy(nxt->factoredExits.begin(), nxt->factoredExits.end(),
 535                     std::inserter(exitSet, begin(exitSet)));
 536           blk->factoredExits.resize(exitSet.size());
 537           std::copy(begin(exitSet), end(exitSet), blk->factoredExits.begin());
 538           nxt->factoredExits = decltype(nxt->factoredExits) {};
 539         } else {
 540           blk->factoredExits = std::move(nxt->factoredExits);
 541         }
 542       }
 543       std::copy(nxt->hhbcs.begin(), nxt->hhbcs.end(),
 544                 std::back_inserter(blk->hhbcs));
 545       nxt->fallthrough = NoBlockId;
 546       nxt->id = NoBlockId;
 547       nxt->hhbcs = { bc::Nop {} };
 548       anyChanges = true;
 549     }
 550     auto const& bInfo = blockInfo[blk->id];
 551     if (bInfo.couldBeSwitch &&
 552         (bInfo.multiplePreds || !bInfo.onlySwitch || !bInfo.followsSwitch)) {
 553       // This block looks like it could be part of a switch, and it's
 554       // not in the middle of a sequence of such blocks.
 555       if (buildSwitches(func, borrow(blk), blockInfo)) {
 556         anyChanges = true;
 557       }
 558     }
 559   }
 560
 561   return anyChanges;
 562 }
 563
 564 //////////////////////////////////////////////////////////////////////
 565
 566 }}