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