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/func-util.h"
  26 #include "hphp/hhbbc/options.h"
  27 #include "hphp/hhbbc/unit-util.h"
  28 #include "hphp/hhbbc/wide-func.h"
  29
  30 namespace HPHP::HHBBC {
  31
  32 TRACE_SET_MOD(hhbbc_cfg);
  33
  34 //////////////////////////////////////////////////////////////////////
  35
  36 static bool is_dead(const php::Block* blk) {
  37   return blk->dead;
  38 }
  39
  40 namespace {
  41
  42 /*
  43  * Remove exception handlers that has no effect, either because they just
  44  * immediately rethrow the received exception, or they only unset locals
  45  * before rethrowing at the top level, which is redundant with the unwinder.
  46  */
  47 void remove_unnecessary_exception_handlers(const FuncAnalysis& ainfo,
  48                                            php::WideFunc& func) {
  49   auto& blocks = func.blocks();
  50   auto remap = std::vector<Optional<std::tuple<BlockId, ExnNodeId>>>(
  51     blocks.size(), std::nullopt);
  52
  53   // Visit exception handlers before the blocks using them.
  54   for (auto it = ainfo.rpoBlocks.rbegin(); it != ainfo.rpoBlocks.rend(); ++it) {
  55     auto& blk = blocks[*it];
  56
  57     // Apply the remap if this block handles exceptions with a remapped
  58     // exception handler.
  59     if (blk->throwExit != NoBlockId) {
  60       if (auto const r = remap[blk->throwExit]) {
  61         auto const mblk = blk.mutate();
  62         std::tie(mblk->throwExit, mblk->exnNodeId) = *r;
  63       }
  64     }
  65
  66     // If this block looks like an exception handler that can be optimized away,
  67     // add it to the remap.
  68     if (is_single_throw(*blk) ||
  69         (blk->throwExit == NoBlockId && is_unsetl_throw(*blk))) {
  70       remap[*it] = std::make_tuple(blk->throwExit, blk->exnNodeId);
  71     }
  72   }
  73 }
  74
  75 }
  76
  77 void remove_unreachable_blocks(const FuncAnalysis& ainfo, php::WideFunc& func) {
  78   auto done_header = false;
  79   auto header = [&] {
  80     if (done_header) return;
  81     done_header = true;
  82     FTRACE(2, "Remove unreachable blocks: {}\n", func->name);
  83   };
  84
  85   auto& blocks = func.blocks();
  86
  87   auto make_unreachable = [&](BlockId bid) {
  88     auto const blk = blocks[bid].get();
  89     if (is_dead(blk)) return false;
  90     auto const& state = ainfo.bdata[bid].stateIn;
  91     if (!state.initialized) return true;
  92     if (!state.unreachable) return false;
  93     return blk->hhbcs.size() != 1 ||
  94            blk->hhbcs.back().op != Op::StaticAnalysisError;
  95   };
  96
  97   for (auto bid : func.blockRange()) {
  98     if (!make_unreachable(bid)) continue;
  99     header();
 100     FTRACE(2, "Marking {} unreachable\n", bid);
 101     auto const blk = func.blocks()[bid].mutate();
 102     auto const srcLoc = blk->hhbcs.front().srcLoc;
 103     blk->hhbcs = {
 104       bc_with_loc(srcLoc, bc::StaticAnalysisError {})
 105     };
 106     blk->fallthrough = NoBlockId;
 107     blk->throwExit = NoBlockId;
 108     blk->exnNodeId = NoExnNodeId;
 109   }
 110
 111   remove_unnecessary_exception_handlers(ainfo, func);
 112
 113   auto reachable = [&](BlockId id) {
 114     if (id == NoBlockId) return false;
 115     auto const& state = ainfo.bdata[id].stateIn;
 116     return state.initialized && !state.unreachable;
 117   };
 118
 119   for (auto const bid : ainfo.rpoBlocks) {
 120     if (!reachable(bid)) continue;
 121     auto reachableTarget = NoBlockId;
 122     auto hasUnreachableTargets = false;
 123     forEachNormalSuccessor(
 124       *blocks[bid],
 125       [&] (BlockId id) {
 126         if (reachable(id)) {
 127           reachableTarget = id;
 128         } else {
 129           hasUnreachableTargets = true;
 130         }
 131       }
 132     );
 133
 134     if (!hasUnreachableTargets || reachableTarget == NoBlockId) continue;
 135     header();
 136     switch (blocks[bid]->hhbcs.back().op) {
 137       case Op::JmpNZ:
 138       case Op::JmpZ: {
 139         FTRACE(2, "blk: {} - jcc -> jmp {}\n", bid, reachableTarget);
 140         auto const blk = func.blocks()[bid].mutate();
 141         blk->hhbcs.back() = bc_with_loc(blk->hhbcs.back().srcLoc, bc::PopC {});
 142         blk->fallthrough = reachableTarget;
 143         break;
 144       }
 145       case Op::Switch:
 146       case Op::SSwitch: {
 147         FTRACE(2, "blk: {} -", bid);
 148         auto const blk = func.blocks()[bid].mutate();
 149         forEachNormalSuccessor(
 150           *blk,
 151           [&] (BlockId& id) {
 152             if (!reachable(id)) {
 153               FTRACE(2, " {}->{}", id, reachableTarget);
 154               id = reachableTarget;
 155             }
 156           }
 157         );
 158         FTRACE(2, "\n");
 159         break;
 160       }
 161       default:
 162         break;
 163     }
 164   }
 165 }
 166
 167 namespace {
 168
 169 struct MergeBlockInfo {
 170   // This block has a predecessor; used to set the multiplePreds flag
 171   uint8_t hasPred          : 1;
 172   // Block has more than one pred, or is an entry block
 173   uint8_t multiplePreds    : 1;
 174   // Block has more than one successor
 175   uint8_t multipleSuccs    : 1;
 176   // Block has simple Nop successor.
 177   uint8_t followSucc       : 1;
 178
 179   // Block contains a sequence that could be part of a switch
 180   uint8_t couldBeSwitch    : 1;
 181   // Block contains a sequence that could be part of a switch, and nothing else
 182   uint8_t onlySwitch       : 1;
 183   // Block follows the "default" of a prior switch sequence
 184   uint8_t followsSwitch    : 1;
 185
 186   // Block will not throw
 187   uint8_t noThrow          : 1;
 188 };
 189
 190 struct SwitchInfo {
 191   union Case { SString s; int64_t i; };
 192   std::vector<std::pair<Case,BlockId>> cases;
 193   BlockId defaultBlock = NoBlockId;
 194   NamedLocal switchLoc{};
 195   DataType kind;
 196 };
 197
 198 bool analyzeSwitch(const php::WideFunc& func, BlockId bid,
 199                    std::vector<MergeBlockInfo>& blkInfos,
 200                    SwitchInfo* switchInfo) {
 201   auto const& blk = *func.blocks()[bid];
 202   auto const jmp = &blk.hhbcs.back();
 203   auto& blkInfo = blkInfos[bid];
 204
 205   switch (jmp->op) {
 206     case Op::JmpZ:
 207     case Op::JmpNZ: {
 208       if (blk.hhbcs.size() < 4) return false;
 209       auto const& cmp = jmp[-1];
 210       if (cmp.op != Op::Eq && cmp.op != Op::Neq) return false;
 211       auto check = [&] (const Bytecode& arg1, const Bytecode& arg2) -> bool {
 212         NamedLocal loc;
 213         if (arg2.op == Op::CGetL) {
 214           loc = arg2.CGetL.nloc1;
 215         } else if (arg2.op == Op::CGetQuietL) {
 216           loc = NamedLocal{kInvalidLocalName, arg2.CGetQuietL.loc1};
 217         } else if (arg2.op == Op::CGetL2 && &arg2 == &arg1 + 1) {
 218           loc = arg2.CGetL2.nloc1;
 219         } else {
 220           return false;
 221         }
 222         SwitchInfo::Case c;
 223         if (arg1.op == Op::Int) {
 224           c.i = arg1.Int.arg1;
 225         } else if (arg1.op == Op::String) {
 226           c.s = arg1.String.str1;
 227         } else {
 228           return false;
 229         }
 230         if (switchInfo) {
 231           auto const dt = arg1.op == Op::Int ? KindOfInt64 : KindOfString;
 232           if (switchInfo->cases.size()) {
 233             if (loc != switchInfo->switchLoc) return false;
 234             if (dt != switchInfo->kind) return false;
 235           } else {
 236             switchInfo->switchLoc = loc;
 237             switchInfo->kind = dt;
 238           }
 239         }
 240         auto const jmpTarget = jmp->op == Op::JmpNZ ?
 241           jmp->JmpNZ.target1 : jmp->JmpZ.target1;
 242         BlockId caseTarget, defaultBlock;
 243         if ((jmp->op == Op::JmpNZ) == (cmp.op == Op::Eq)) {
 244           defaultBlock = blk.fallthrough;
 245           caseTarget = jmpTarget;
 246         } else {
 247           defaultBlock = jmpTarget;
 248           caseTarget = blk.fallthrough;
 249         }
 250         blkInfo.couldBeSwitch = true;
 251         blkInfo.onlySwitch = blk.hhbcs.size() == 4;
 252         blkInfos[defaultBlock].followsSwitch = true;
 253         if (switchInfo) {
 254           switchInfo->cases.emplace_back(c, caseTarget);
 255           switchInfo->defaultBlock = defaultBlock;
 256         }
 257         return true;
 258       };
 259       return check(jmp[-2], jmp[-3]) || check(jmp[-3], jmp[-2]);
 260     }
 261     case Op::Switch:
 262     case Op::SSwitch: {
 263       if (blk.hhbcs.size() < 2) return false;
 264       auto const& cgetl = jmp[-1];
 265       if (cgetl.op != Op::CGetL && cgetl.op != Op::CGetQuietL) return false;
 266       auto const loc = cgetl.op == Op::CGetQuietL
 267                        ? NamedLocal{kInvalidLocalName, cgetl.CGetQuietL.loc1}
 268                        : cgetl.CGetL.nloc1;
 269       auto const dt = jmp->op == Op::Switch ? KindOfInt64 : KindOfString;
 270       if (switchInfo) {
 271         if (switchInfo->cases.size()) {
 272           if (loc != switchInfo->switchLoc) return false;
 273           if (dt != switchInfo->kind) return false;
 274         } else {
 275           switchInfo->switchLoc = loc;
 276           switchInfo->kind = dt;
 277         }
 278       }
 279       if (jmp->op == Op::Switch) {
 280         if (jmp->Switch.subop1 != SwitchKind::Bounded) return false;
 281         auto const db = jmp->Switch.targets.back();
 282         auto const min = jmp->Switch.arg2;
 283         blkInfos[db].followsSwitch = true;
 284         if (switchInfo) {
 285           switchInfo->defaultBlock = db;
 286           for (size_t i = 0; i < jmp->Switch.targets.size() - 2; i++) {
 287             auto const t = jmp->Switch.targets[i];
 288             if (t == db) continue;
 289             SwitchInfo::Case c;
 290             c.i = i + min;
 291             switchInfo->cases.emplace_back(c, t);
 292           }
 293         }
 294       } else {
 295         auto const db = jmp->SSwitch.targets.back().second;
 296         blkInfos[db].followsSwitch = true;
 297         if (switchInfo) {
 298           switchInfo->defaultBlock = db;
 299           for (auto& kv : jmp->SSwitch.targets) {
 300             if (kv.second == db) continue;
 301             SwitchInfo::Case c;
 302             c.s = kv.first;
 303             switchInfo->cases.emplace_back(c, kv.second);
 304           }
 305         }
 306       }
 307       blkInfo.couldBeSwitch = true;
 308       blkInfo.onlySwitch = blk.hhbcs.size() == 2;
 309       return true;
 310     }
 311     default:
 312       return false;
 313   }
 314 }
 315
 316 Bytecode buildIntSwitch(SwitchInfo& switchInfo) {
 317   auto min = switchInfo.cases[0].first.i;
 318   auto max = min;
 319   for (size_t i = 1; i < switchInfo.cases.size(); ++i) {
 320     auto v = switchInfo.cases[i].first.i;
 321     if (v < min) min = v;
 322     if (v > max) max = v;
 323   }
 324   if (switchInfo.cases.size() / ((double)max - (double)min + 1) < .5) {
 325     return { bc::Nop {} };
 326   }
 327   CompactVector<BlockId> switchTab;
 328   switchTab.resize(max - min + 3, switchInfo.defaultBlock);
 329   for (auto i = switchInfo.cases.size(); i--; ) {
 330     auto const& c = switchInfo.cases[i];
 331     switchTab[c.first.i - min] = c.second;
 332     if (c.first.i) switchTab[max - min + 1] = c.second;
 333   }
 334   return { bc::Switch { SwitchKind::Bounded, min, std::move(switchTab) } };
 335 }
 336
 337 Bytecode buildStringSwitch(SwitchInfo& switchInfo) {
 338   hphp_fast_set<SString> seen;
 339   SSwitchTab sswitchTab;
 340   for (auto& c : switchInfo.cases) {
 341     if (seen.insert(c.first.s).second) {
 342       sswitchTab.emplace_back(c.first.s, c.second);
 343     }
 344   }
 345   sswitchTab.emplace_back(nullptr, switchInfo.defaultBlock);
 346   return { bc::SSwitch { std::move(sswitchTab) } };
 347 }
 348
 349 bool buildSwitches(php::WideFunc& func, BlockId bid,
 350                    std::vector<MergeBlockInfo>& blkInfos) {
 351   SwitchInfo switchInfo;
 352   std::vector<BlockId> blocks;
 353   if (!analyzeSwitch(func, bid, blkInfos, &switchInfo)) return false;
 354   blkInfos[bid].couldBeSwitch = false;
 355   blkInfos[bid].onlySwitch = false;
 356   while (true) {
 357     auto const& bInfo = blkInfos[switchInfo.defaultBlock];
 358     auto const nxtId = switchInfo.defaultBlock;
 359     if (bInfo.onlySwitch && !bInfo.multiplePreds &&
 360         analyzeSwitch(func, nxtId, blkInfos, &switchInfo)) {
 361       blocks.push_back(switchInfo.defaultBlock);
 362       continue;
 363     }
 364     bool ret = false;
 365     auto const minSize = switchInfo.kind == KindOfInt64 ? 1 : 8;
 366     if (switchInfo.cases.size() >= minSize && blocks.size()) {
 367       switchInfo.defaultBlock = next_real_block(func, switchInfo.defaultBlock);
 368       auto bc = switchInfo.kind == KindOfInt64 ?
 369         buildIntSwitch(switchInfo) : buildStringSwitch(switchInfo);
 370       if (bc.op != Op::Nop) {
 371         auto const blk = func.blocks()[bid].mutate();
 372         auto it = blk->hhbcs.end();
 373         // blk->fallthrough implies it was a JmpZ JmpNZ block,
 374         // which means we have exactly 4 instructions making up
 375         // the switch (see analyzeSwitch). Otherwise it was a
 376         // [S]Switch, and there were exactly two instructions.
 377         if (blk->fallthrough != NoBlockId) {
 378           it -= 4;
 379         } else {
 380           it -= 2;
 381         }
 382         bc.srcLoc = it->srcLoc;
 383         blkInfos[switchInfo.defaultBlock].multiplePreds = true;
 384         blk->hhbcs.erase(it, blk->hhbcs.end());
 385         blk->hhbcs.emplace_back(bc::CGetL { switchInfo.switchLoc });
 386         blk->hhbcs.back().srcLoc = bc.srcLoc;
 387         blk->hhbcs.push_back(std::move(bc));
 388         blk->fallthrough = NoBlockId;
 389         for (auto id : blocks) {
 390           if (blkInfos[id].multiplePreds) continue;
 391           auto const removed = func.blocks()[id].mutate();
 392           removed->dead = true;
 393           removed->hhbcs = { bc::Nop {} };
 394           removed->fallthrough = NoBlockId;
 395           removed->throwExit = NoBlockId;
 396           removed->exnNodeId = NoExnNodeId;
 397         }
 398         ret = true;
 399       }
 400     }
 401     if (bInfo.couldBeSwitch && buildSwitches(func, nxtId, blkInfos)) {
 402       ret = true;
 403     }
 404     return ret;
 405   }
 406 }
 407
 408 }
 409
 410 bool control_flow_opts(const FuncAnalysis& ainfo, php::WideFunc& func) {
 411   FTRACE(2, "control_flow_opts: {}\n", func->name);
 412
 413   std::vector<MergeBlockInfo> blockInfo(
 414       func.blocks().size(), MergeBlockInfo {});
 415
 416   bool anyChanges = false;
 417
 418   auto reachable = [&](BlockId id) {
 419     if (is_dead(func.blocks()[id].get())) return false;
 420     auto const& state = ainfo.bdata[id].stateIn;
 421     return state.initialized && !state.unreachable;
 422   };
 423
 424   // find all the blocks with multiple preds; they can't be merged
 425   // into their predecessors
 426   for (auto bid : func.blockRange()) {
 427     auto& cblk = func.blocks()[bid];
 428     if (is_dead(cblk.get())) continue;
 429     auto& bbi = blockInfo[bid];
 430     bbi.noThrow = ainfo.bdata[bid].noThrow;
 431     int numSucc = 0;
 432     if (!reachable(bid)) {
 433       bbi.multiplePreds = true;
 434       bbi.multipleSuccs = true;
 435       continue;
 436     } else {
 437       analyzeSwitch(func, bid, blockInfo, nullptr);
 438     }
 439     auto handleSucc = [&] (BlockId succId) {
 440       auto& bsi = blockInfo[succId];
 441       if (bsi.hasPred) {
 442         bsi.multiplePreds = true;
 443       } else {
 444         bsi.hasPred = true;
 445       }
 446     };
 447     forEachNormalSuccessor(
 448       *cblk,
 449       [&] (BlockId succId) {
 450         if (cblk->hhbcs.back().op == Op::Enter) {
 451           // Enter must always point to the main func entry.
 452           handleSucc(succId);
 453         } else {
 454           auto const realSucc = next_real_block(func, succId);
 455           if (succId != realSucc) bbi.followSucc = true;
 456           handleSucc(realSucc);
 457         }
 458         numSucc++;
 459       }
 460     );
 461     // Attempt to jump thread the catch blocks again, in the hope of
 462     // having two adjacent blocks end up with the same catch block.
 463     auto const nextCatch =
 464       next_catch_block(func, cblk->throwExit, cblk->exnNodeId);
 465     if (nextCatch.first != cblk->throwExit ||
 466         nextCatch.second != cblk->exnNodeId) {
 467       anyChanges = true;
 468       auto const blk = cblk.mutate();
 469       blk->throwExit = nextCatch.first;
 470       blk->exnNodeId = nextCatch.second;
 471     }
 472     if (cblk->throwExit != NoBlockId) handleSucc(cblk->throwExit);
 473     if (numSucc > 1) bbi.multipleSuccs = true;
 474   }
 475   blockInfo[func->mainEntry].multiplePreds = true;
 476   for (auto const blkId: func->dvEntries) {
 477     if (blkId != NoBlockId) {
 478       blockInfo[blkId].multiplePreds = true;
 479     }
 480   }
 481   for (auto bid : func.blockRange()) {
 482     if (blockInfo[bid].followSucc) {
 483       auto const blk = func.blocks()[bid].mutate();
 484       assertx(blk->hhbcs.back().op != Op::Enter);
 485       forEachNormalSuccessor(
 486         *blk,
 487         [&] (BlockId& succId) {
 488           auto skip = next_real_block(func, succId);
 489           auto const criticalEdge = blockInfo[bid].multipleSuccs
 490                                     && blockInfo[skip].multiplePreds;
 491           if (skip != succId) {
 492             if (!criticalEdge) anyChanges = true;
 493             succId = skip;
 494           }
 495         }
 496       );
 497     }
 498   }
 499
 500   for (auto bid : func.blockRange()) {
 501     auto& cblk = func.blocks()[bid];
 502     if (is_dead(cblk.get())) continue;
 503
 504     while (cblk->fallthrough != NoBlockId) {
 505       auto const nid = cblk->fallthrough;
 506       auto& cnxt = func.blocks()[nid];
 507       if (blockInfo[bid].multipleSuccs || blockInfo[nid].multiplePreds) break;
 508
 509       // If the two blocks have different catch blocks, we might still
 510       // be able to combine them. If one (or both) of the blocks are
 511       // no throw, it doesn't matter what the catch block is, because
 512       // its unreachable.
 513       auto useNextCatch = false;
 514       if (cblk->exnNodeId != cnxt->exnNodeId ||
 515           cblk->throwExit != cnxt->throwExit) {
 516         auto const noThrow = blockInfo[bid].noThrow;
 517         auto const nextNoThrow = blockInfo[cblk->fallthrough].noThrow;
 518         if (!nextNoThrow && !noThrow) break;
 519
 520         // Don't merge blocks containing these instructions because it
 521         // can produce bytecode which will fail the verifier.
 522         auto const unsafe = [] (const Bytecode& bc) {
 523           switch (bc.op) {
 524             case Op::IterFree:
 525             case Op::Silence:
 526               return true;
 527             default:
 528               return false;
 529           }
 530         };
 531         if (std::any_of(begin(cblk->hhbcs), end(cblk->hhbcs), unsafe)) break;
 532         if (std::any_of(begin(cnxt->hhbcs), end(cnxt->hhbcs), unsafe)) break;
 533
 534         useNextCatch = noThrow;
 535       }
 536
 537       FTRACE(2, "   merging: {} into {}\n", nid, bid);
 538       auto& bInfo = blockInfo[bid];
 539       auto const& nInfo = blockInfo[nid];
 540       bInfo.multipleSuccs = nInfo.multipleSuccs;
 541       bInfo.couldBeSwitch = nInfo.couldBeSwitch;
 542       bInfo.onlySwitch = false;
 543       bInfo.noThrow &= nInfo.noThrow;
 544
 545       auto const blk = func.blocks()[bid].mutate();
 546       blk->fallthrough = cnxt->fallthrough;
 547       if (useNextCatch) {
 548         blk->throwExit = cnxt->throwExit;
 549         blk->exnNodeId = cnxt->exnNodeId;
 550       }
 551       std::copy(cnxt->hhbcs.begin(), cnxt->hhbcs.end(),
 552                 std::back_inserter(blk->hhbcs));
 553       auto const nxt = func.blocks()[nid].mutate();
 554       nxt->fallthrough = NoBlockId;
 555       nxt->throwExit = NoBlockId;
 556       nxt->exnNodeId = NoExnNodeId;
 557       nxt->dead = true;
 558       nxt->hhbcs = { bc::Nop {} };
 559       anyChanges = true;
 560     }
 561
 562     auto& bInfo = blockInfo[bid];
 563
 564     if (bInfo.couldBeSwitch &&
 565         (bInfo.multiplePreds || !bInfo.onlySwitch || !bInfo.followsSwitch)) {
 566       // This block looks like it could be part of a switch, and it's
 567       // not in the middle of a sequence of such blocks.
 568       if (buildSwitches(func, bid, blockInfo)) {
 569         anyChanges = true;
 570       }
 571     }
 572
 573     // Turn a conditional jump to the same block into an unconditional
 574     // jump. This can make the source of the conditional jump dead.
 575     auto const jmpTarget = [&] () -> Optional<BlockId> {
 576       auto const& lastOp = cblk->hhbcs.back();
 577       if (lastOp.op == Op::JmpZ)  return lastOp.JmpZ.target1;
 578       if (lastOp.op == Op::JmpNZ) return lastOp.JmpNZ.target1;
 579       return std::nullopt;
 580     }();
 581
 582     if (jmpTarget && cblk->fallthrough == *jmpTarget) {
 583       FTRACE(2, "   removing redundant conditional jmp in {}\n", bid);
 584       auto const blk = func.blocks()[bid].mutate();
 585       blk->hhbcs.back() = bc_with_loc(blk->hhbcs.back().srcLoc, bc::PopC {});
 586       bInfo.multipleSuccs = false;
 587       anyChanges = true;
 588     }
 589   }
 590
 591   return anyChanges;
 592 }
 593
 594 void split_critical_edges(const Index& index, FuncAnalysis& ainfo,
 595                           php::WideFunc& func) {
 596   // Changed tracks if we need to recompute RPO.
 597   auto changed = false;
 598   assertx(func.blocks().size() == ainfo.bdata.size());
 599
 600   // Makes an empty block and inserts it between src and dst.  Since we can't
 601   // have empty blocks it actually stores a Nop in it to keep everyone happy.
 602   // The block will have the same exception node id, and throw exit block as
 603   // the src block.
 604   //
 605   // ainfo is not updated with the correct rpo info by this helper, but is
 606   // updated with the correct state info.
 607   auto const split_edge = [&](BlockId srcBid, php::Block* srcBlk,
 608                               BlockId dstBid) {
 609     assertx(srcBlk->hhbcs.back().op != Op::Enter);
 610     auto const srcLoc = srcBlk->hhbcs.back().srcLoc;
 611     auto const newBid = make_block(func, srcBlk);
 612     auto const newBlk = func.blocks()[newBid].mutate();
 613     newBlk->hhbcs = { bc_with_loc(srcLoc, bc::Nop{}) };
 614     newBlk->fallthrough = dstBid;
 615
 616     UNUSED bool replacedDstTarget = false;
 617     forEachNormalSuccessor(*srcBlk, [&] (BlockId& bid) {
 618       if (bid == dstBid) {
 619         bid = newBid;
 620         replacedDstTarget = true;
 621       }
 622     });
 623     assertx(replacedDstTarget);
 624
 625     IndexAdaptor adaptor{index};
 626     auto collect = CollectedInfo {
 627       adaptor, ainfo.ctx, nullptr,
 628       CollectionOpts{}, nullptr, &ainfo
 629     };
 630     auto const ctx = AnalysisContext { ainfo.ctx.unit, func, ainfo.ctx.cls };
 631     ainfo.bdata.push_back({
 632       0, // We renumber the blocks at the end of the function.
 633       locally_propagated_bid_state(index, ctx, collect, srcBid,
 634                                    ainfo.bdata[srcBid].stateIn,
 635                                    newBid)
 636     });
 637     assertx(func.blocks().size() == ainfo.bdata.size());
 638
 639     changed = true;
 640   };
 641
 642   boost::dynamic_bitset<> haveSeenPred(func.blocks().size());
 643   boost::dynamic_bitset<> hasMultiplePreds(func.blocks().size());
 644   boost::dynamic_bitset<> hasMultipleSuccs(func.blocks().size());
 645   // Switches can have the same successor for multiple cases, and we only want
 646   // to split the edge once.
 647   boost::dynamic_bitset<> seenSuccs(func.blocks().size());
 648   for (auto bid : func.blockRange()) {
 649     auto& blk = func.blocks()[bid];
 650
 651     int succCount = 0;
 652     seenSuccs.reset();
 653     forEachNormalSuccessor(*blk, [&] (BlockId succBid) {
 654       if (seenSuccs[succBid]) return;
 655       seenSuccs[succBid] = true;
 656       if (haveSeenPred[succBid]) {
 657         hasMultiplePreds[succBid] = true;
 658       } else {
 659         haveSeenPred[succBid] = true;
 660       }
 661       succCount++;
 662     });
 663
 664     hasMultipleSuccs[bid] = succCount > 1;
 665   }
 666
 667   for (auto bid : func.blockRange()) {
 668     if (!hasMultipleSuccs[bid]) continue;
 669     auto blk = func.blocks()[bid];
 670     seenSuccs.reset();
 671     forEachNormalSuccessor(*blk, [&] (BlockId succBid) {
 672       if (hasMultiplePreds[succBid] && !seenSuccs[succBid]) {
 673         seenSuccs[succBid] = true;
 674         split_edge(bid, func.blocks()[bid].mutate(), succBid);
 675       }
 676     });
 677   }
 678
 679   if (changed) {
 680     // Recompute the rpo ids.
 681     assertx(func.blocks().size() == ainfo.bdata.size());
 682     ainfo.rpoBlocks = rpoSortAddDVs(func);
 683     assertx(ainfo.rpoBlocks.size() <= ainfo.bdata.size());
 684     for (size_t rpoId = 0; rpoId < ainfo.rpoBlocks.size(); ++rpoId) {
 685       ainfo.bdata[ainfo.rpoBlocks[rpoId]].rpoId = rpoId;
 686     }
 687   }
 688 }
 689
 690 //////////////////////////////////////////////////////////////////////
 691
 692 }