hphp/runtime/vm/jit/region-selection.cpp

   1 /*
   2    +----------------------------------------------------------------------+
   3    | HipHop for PHP                                                       |
   4    +----------------------------------------------------------------------+
   5    | Copyright (c) 2010-2014 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/runtime/vm/jit/region-selection.h"
  17
  18 #include <algorithm>
  19 #include <functional>
  20 #include <exception>
  21 #include <utility>
  22 #include <iostream>
  23
  24 #include "folly/Memory.h"
  25 #include "folly/Conv.h"
  26 #include "folly/String.h"
  27
  28 #include "hphp/util/assertions.h"
  29 #include "hphp/util/map-walker.h"
  30 #include "hphp/runtime/base/runtime-option.h"
  31 #include "hphp/runtime/vm/jit/normalized-instruction.h"
  32 #include "hphp/runtime/vm/jit/prof-data.h"
  33 #include "hphp/runtime/vm/jit/trans-cfg.h"
  34 #include "hphp/runtime/vm/jit/translator-inline.h"
  35 #include "hphp/runtime/vm/jit/translator.h"
  36
  37 namespace HPHP { namespace jit {
  38
  39 TRACE_SET_MOD(region);
  40
  41
  42 //////////////////////////////////////////////////////////////////////
  43
  44 extern RegionDescPtr selectMethod(const RegionContext&);
  45 extern RegionDescPtr selectOneBC(const RegionContext&);
  46 extern RegionDescPtr selectHotBlock(TransID transId,
  47                                     const ProfData* profData,
  48                                     const TransCFG& cfg);
  49
  50 //////////////////////////////////////////////////////////////////////
  51
  52 namespace {
  53
  54 enum class RegionMode {
  55   None,      // empty region
  56
  57   // Modes that create a region by inspecting live VM state
  58   Method,    // region with a whole method
  59   Tracelet,  // single-entry, multiple-exits region that ends on conditional
  60              // branches or when an instruction consumes a value of unknown type
  61 };
  62
  63 RegionMode regionMode() {
  64   auto& s = RuntimeOption::EvalJitRegionSelector;
  65   if (s == ""        ) return RegionMode::None;
  66   if (s == "method"  ) return RegionMode::Method;
  67   if (s == "tracelet") return RegionMode::Tracelet;
  68   FTRACE(1, "unknown region mode {}: using none\n", s);
  69   assert(false);
  70   return RegionMode::None;
  71 }
  72
  73 enum class PGORegionMode {
  74   Hottrace, // Select a long region, using profile counters to guide the trace
  75   Hotblock, // Select a single block
  76   WholeCFG, // Select the entire CFG that has been profiled
  77 };
  78
  79 PGORegionMode pgoRegionMode() {
  80   auto& s = RuntimeOption::EvalJitPGORegionSelector;
  81   if (s == "hottrace") return PGORegionMode::Hottrace;
  82   if (s == "hotblock") return PGORegionMode::Hotblock;
  83   if (s == "wholecfg") return PGORegionMode::WholeCFG;
  84   FTRACE(1, "unknown pgo region mode {}: using hottrace\n", s);
  85   assert(false);
  86   return PGORegionMode::Hottrace;
  87 }
  88
  89 template<typename Container>
  90 void truncateMap(Container& c, SrcKey final) {
  91   c.erase(c.upper_bound(final), c.end());
  92 }
  93 }
  94
  95 //////////////////////////////////////////////////////////////////////
  96
  97 bool RegionDesc::empty() const {
  98   return m_blocks.empty();
  99 }
 100
 101 RegionDesc::BlockPtr RegionDesc::entry() const {
 102   assert(!empty());
 103   return m_blocks[0];
 104 }
 105
 106 bool RegionDesc::isExit(BlockId bid) const {
 107   return succs(bid).empty();
 108 }
 109
 110 SrcKey RegionDesc::start() const {
 111   assert(!empty());
 112   return m_blocks[0]->start();
 113 }
 114
 115 uint32_t RegionDesc::instrSize() const {
 116   uint32_t size = 0;
 117   for (auto& b : m_blocks) {
 118     size += b->length();
 119   }
 120   return size;
 121 }
 122
 123 RegionDesc::Block* RegionDesc::addBlock(SrcKey sk,
 124                                         int    length,
 125                                         Offset spOffset) {
 126   m_blocks.push_back(
 127     std::make_shared<Block>(sk.func(), sk.resumed(), sk.offset(), length,
 128                             spOffset));
 129   BlockPtr block = m_blocks.back();
 130   m_data[block->id()] = BlockData(block);
 131   return block.get();
 132 }
 133
 134 void RegionDesc::deleteBlock(BlockId bid) {
 135   auto it = std::find_if(m_blocks.begin(), m_blocks.end(),
 136                          [&](const BlockPtr b) { return b->id() == bid; });
 137   if (it == m_blocks.end()) return;
 138   m_blocks.erase(it);
 139   auto d = data(bid);
 140   always_assert(d.succs.empty() && d.preds.empty() &&
 141                 "RegionDesc::deleteBlock needs support for blocks with arcs");
 142   m_data.erase(bid);
 143 }
 144
 145 const RegionDesc::BlockVec& RegionDesc::blocks() const {
 146   return m_blocks;
 147 }
 148
 149 RegionDesc::BlockData& RegionDesc::data(BlockId id) {
 150   auto it = m_data.find(id);
 151   assert(it != m_data.end());
 152   return it->second;
 153 }
 154
 155 bool RegionDesc::hasBlock(BlockId id) const {
 156   return m_data.count(id);
 157 }
 158
 159 RegionDesc::BlockPtr RegionDesc::block(BlockId id) const {
 160   return const_cast<RegionDesc*>(this)->data(id).block;
 161 }
 162
 163 const RegionDesc::BlockIdSet& RegionDesc::succs(BlockId id) const {
 164   return const_cast<RegionDesc*>(this)->data(id).succs;
 165 }
 166
 167 const RegionDesc::BlockIdSet& RegionDesc::preds(BlockId id) const {
 168   return const_cast<RegionDesc*>(this)->data(id).preds;
 169 }
 170
 171 const RegionDesc::BlockIdSet& RegionDesc::sideExitingBlocks() const {
 172   return m_sideExitingBlocks;
 173 }
 174
 175 void RegionDesc::addArc(BlockId srcId, BlockId dstId) {
 176   data(srcId).succs.insert(dstId);
 177   data(dstId).preds.insert(srcId);
 178 }
 179
 180 void RegionDesc::renumberBlock(BlockId oldId, BlockId newId) {
 181   assert( hasBlock(oldId));
 182   assert(!hasBlock(newId));
 183
 184   block(oldId)->setId(newId);
 185   m_data[newId] = m_data[oldId];
 186   m_data.erase(oldId);
 187
 188   // Fix predecessor sets for the successors.
 189   for (auto succId : m_data[newId].succs) {
 190     BlockIdSet& succPreds = m_data[succId].preds;
 191     assert(succPreds.count(oldId));
 192     succPreds.erase(oldId);
 193     succPreds.insert(newId);
 194   }
 195
 196   // Fix successor sets for the predecessors.
 197   for (auto predId : m_data[newId].preds) {
 198     BlockIdSet& predSuccs = m_data[predId].succs;
 199     assert(predSuccs.count(oldId));
 200     predSuccs.erase(oldId);
 201     predSuccs.insert(newId);
 202   }
 203 }
 204
 205 void RegionDesc::setSideExitingBlock(BlockId bid) {
 206   m_sideExitingBlocks.insert(bid);
 207 }
 208
 209 bool RegionDesc::isSideExitingBlock(BlockId bid) const {
 210   return m_sideExitingBlocks.count(bid);
 211 }
 212
 213 void RegionDesc::copyArcsFrom(const RegionDesc& srcRegion) {
 214   for (auto const b : srcRegion.m_blocks) {
 215     auto bid = b->id();
 216     for (auto succId : srcRegion.succs(bid)) {
 217       addArc(bid, succId);
 218     }
 219   }
 220 }
 221
 222 void RegionDesc::copyBlocksFrom(const RegionDesc&  other,
 223                                 BlockVec::iterator where) {
 224   auto otherBlocks = other.blocks();
 225   m_blocks.insert(where, otherBlocks.begin(), otherBlocks.end());
 226   for (auto b : otherBlocks) {
 227     m_data[b->id()] = BlockData(b);
 228   }
 229 }
 230
 231 void RegionDesc::append(const RegionDesc& other) {
 232   copyBlocksFrom(other, m_blocks.end());
 233   copyArcsFrom(other);
 234   m_sideExitingBlocks.insert(other.m_sideExitingBlocks.begin(),
 235                              other.m_sideExitingBlocks.end());
 236 }
 237
 238 void RegionDesc::prepend(const RegionDesc& other) {
 239   copyBlocksFrom(other, m_blocks.begin());
 240   copyArcsFrom(other);
 241   m_sideExitingBlocks.insert(other.m_sideExitingBlocks.begin(),
 242                              other.m_sideExitingBlocks.end());
 243 }
 244
 245 std::string RegionDesc::toString() const {
 246   auto ret = show(*this);
 247   ret += "data:\n";
 248   for (auto d : m_data) {
 249     ret += folly::format("  block id: {}\n", d.first).str();
 250   }
 251   return ret;
 252 }
 253
 254 //////////////////////////////////////////////////////////////////////
 255
 256 RegionDesc::BlockId RegionDesc::Block::s_nextId = -1;
 257
 258 TransID getTransId(RegionDesc::BlockId blockId) {
 259   return blockId >= 0 ? blockId : kInvalidTransID;
 260 }
 261
 262 bool hasTransId(RegionDesc::BlockId blockId) {
 263   return blockId >= 0;
 264 }
 265
 266 RegionDesc::Block::Block(const Func* func, bool resumed, Offset start,
 267                          int length, Offset initSpOff)
 268   : m_id(s_nextId--)
 269   , m_func(func)
 270   , m_resumed(resumed)
 271   , m_start(start)
 272   , m_last(kInvalidOffset)
 273   , m_length(length)
 274   , m_initialSpOffset(initSpOff)
 275   , m_inlinedCallee(nullptr)
 276 {
 277   assert(length >= 0);
 278   if (length > 0) {
 279     SrcKey sk(func, start, resumed);
 280     for (unsigned i = 1; i < length; ++i) sk.advance();
 281     m_last = sk.offset();
 282   }
 283   checkInstructions();
 284   checkMetadata();
 285 }
 286
 287 bool RegionDesc::Block::contains(SrcKey sk) const {
 288   return sk >= start() && sk <= last();
 289 }
 290
 291 void RegionDesc::Block::addInstruction() {
 292   if (m_length > 0) checkInstruction(last().op());
 293   assert((m_last == kInvalidOffset) == (m_length == 0));
 294
 295   ++m_length;
 296   if (m_length == 1) {
 297     m_last = m_start;
 298   } else {
 299     m_last = last().advanced().offset();
 300   }
 301 }
 302
 303 void RegionDesc::Block::truncateAfter(SrcKey final) {
 304   assert_not_implemented(!m_inlinedCallee);
 305
 306   auto skIter = start();
 307   int newLen = -1;
 308   for (int i = 0; i < m_length; ++i, skIter.advance(unit())) {
 309     if (skIter == final) {
 310       newLen = i + 1;
 311       break;
 312     }
 313   }
 314   assert(newLen != -1);
 315   m_length = newLen;
 316   m_last = final.offset();
 317
 318   truncateMap(m_typePreds, final);
 319   truncateMap(m_byRefs, final);
 320   truncateMap(m_refPreds, final);
 321   truncateMap(m_knownFuncs, final);
 322
 323   checkInstructions();
 324   checkMetadata();
 325 }
 326
 327 void RegionDesc::Block::addPredicted(SrcKey sk, TypePred pred) {
 328   FTRACE(2, "Block::addPredicted({}, {})\n", showShort(sk), show(pred));
 329   assert(pred.type <= Type::StackElem);
 330   assert(contains(sk));
 331   m_typePreds.insert(std::make_pair(sk, pred));
 332 }
 333
 334 void RegionDesc::Block::setParamByRef(SrcKey sk, bool byRef) {
 335   FTRACE(2, "Block::setParamByRef({}, {})\n", showShort(sk),
 336          byRef ? "by ref" : "by val");
 337   assert(m_byRefs.find(sk) == m_byRefs.end());
 338   assert(contains(sk));
 339   m_byRefs.insert(std::make_pair(sk, byRef));
 340 }
 341
 342 void RegionDesc::Block::addReffinessPred(SrcKey sk, const ReffinessPred& pred) {
 343   FTRACE(2, "Block::addReffinessPred({}, {})\n", showShort(sk), show(pred));
 344   assert(contains(sk));
 345   m_refPreds.insert(std::make_pair(sk, pred));
 346 }
 347
 348 void RegionDesc::Block::setKnownFunc(SrcKey sk, const Func* func) {
 349   if (func == nullptr && m_knownFuncs.empty()) return;
 350
 351   FTRACE(2, "Block::setKnownFunc({}, {})\n", showShort(sk),
 352          func ? func->fullName()->data() : "nullptr");
 353   assert(m_knownFuncs.find(sk) == m_knownFuncs.end());
 354   assert(contains(sk));
 355   auto it = m_knownFuncs.lower_bound(sk);
 356   if (it != m_knownFuncs.begin() && (--it)->second == func) {
 357     // Adding func at this sk won't add any new information.
 358     FTRACE(2, "  func exists at {}, not adding\n", showShort(it->first));
 359     return;
 360   }
 361
 362   m_knownFuncs.insert(std::make_pair(sk, func));
 363 }
 364
 365 void RegionDesc::Block::setPostConditions(const PostConditions& conds) {
 366   m_postConds = conds;
 367 }
 368
 369 /*
 370  * Check invariants about the bytecode instructions in this Block.
 371  *
 372  * 1. Single entry, single exit (aside from exceptions).  I.e. no
 373  *    non-fallthrough instructions mid-block and no control flow (not
 374  *    counting calls as control flow).
 375  *
 376  */
 377 void RegionDesc::Block::checkInstructions() const {
 378   if (!debug || length() == 0) return;
 379
 380   auto u = unit();
 381   auto sk = start();
 382
 383   for (int i = 1; i < length(); ++i) {
 384     if (i != length() - 1) checkInstruction(sk.op());
 385     sk.advance(u);
 386   }
 387   assert(sk.offset() == m_last);
 388 }
 389
 390 void RegionDesc::Block::checkInstruction(Op op) const {
 391   if (instrFlags(op) & TF) {
 392     FTRACE(1, "Bad block: {}\n", show(*this));
 393     assert(!"Block may not contain non-fallthrough instruction unless "
 394            "they are last");
 395   }
 396   if (instrIsNonCallControlFlow(op)) {
 397     FTRACE(1, "Bad block: {}\n", show(*this));
 398     assert(!"Block may not contain control flow instructions unless "
 399            "they are last");
 400   }
 401 }
 402
 403 /*
 404  * Check invariants about the metadata for this Block.
 405  *
 406  * 1. Each SrcKey in m_typePreds, m_byRefs, m_refPreds, and m_knownFuncs is
 407  *    within the bounds of the block.
 408  *
 409  * 2. Each local id referred to in the type prediction list is valid.
 410  *
 411  * 3. (Unchecked) each stack offset in the type prediction list is
 412  *    valid.
 413 */
 414 void RegionDesc::Block::checkMetadata() const {
 415   auto rangeCheck = [&](const char* type, Offset o) {
 416     if (o < m_start || o > m_last) {
 417       std::cerr << folly::format("{} at {} outside range [{}, {}]\n",
 418                                  type, o, m_start, m_last);
 419       assert(!"Region::Block contained out-of-range metadata");
 420     }
 421   };
 422   for (auto& tpred : m_typePreds) {
 423     rangeCheck("type prediction", tpred.first.offset());
 424     auto& loc = tpred.second.location;
 425     switch (loc.tag()) {
 426     case Location::Tag::Local: assert(loc.localId() < m_func->numLocals());
 427                                break;
 428     case Location::Tag::Stack: // Unchecked
 429                                break;
 430     }
 431   }
 432
 433   for (auto& byRef : m_byRefs) {
 434     rangeCheck("parameter reference flag", byRef.first.offset());
 435   }
 436   for (auto& refPred : m_refPreds) {
 437     rangeCheck("reffiness prediction", refPred.first.offset());
 438   }
 439   for (auto& func : m_knownFuncs) {
 440     rangeCheck("known Func*", func.first.offset());
 441   }
 442 }
 443
 444 RegionDescPtr selectRegion(const RegionContext& context,
 445                            TransKind kind) {
 446   auto const mode = regionMode();
 447
 448   FTRACE(1,
 449     "Select region: mode={} context:\n{}",
 450     static_cast<int>(mode), show(context)
 451   );
 452
 453   auto region = [&]{
 454     try {
 455       switch (mode) {
 456         case RegionMode::None:
 457           return RegionDescPtr{nullptr};
 458         case RegionMode::Method:
 459           return selectMethod(context);
 460         case RegionMode::Tracelet:
 461           return selectTracelet(context, kind == TransKind::Profile);
 462       }
 463       not_reached();
 464     } catch (const std::exception& e) {
 465       FTRACE(1, "region selector threw: {}\n", e.what());
 466       return RegionDescPtr{nullptr};
 467     }
 468   }();
 469
 470   if (region) {
 471     FTRACE(3, "{}", show(*region));
 472     always_assert(region->instrSize() <= RuntimeOption::EvalJitMaxRegionInstrs);
 473   } else {
 474     FTRACE(1, "no region selectable; using tracelet compiler\n");
 475   }
 476
 477   return region;
 478 }
 479
 480 RegionDescPtr selectHotRegion(TransID transId,
 481                               MCGenerator* mcg) {
 482
 483   assert(RuntimeOption::EvalJitPGO);
 484
 485   const ProfData* profData = mcg->tx().profData();
 486   FuncId funcId = profData->transFuncId(transId);
 487   TransCFG cfg(funcId, profData, mcg->tx().getSrcDB(),
 488                mcg->getJmpToTransIDMap());
 489   TransIDSet selectedTIDs;
 490   assert(regionMode() != RegionMode::Method);
 491   RegionDescPtr region;
 492   switch (pgoRegionMode()) {
 493     case PGORegionMode::Hottrace:
 494       region = selectHotTrace(transId, profData, cfg, selectedTIDs);
 495       break;
 496
 497     case PGORegionMode::Hotblock:
 498       region = selectHotBlock(transId, profData, cfg);
 499       break;
 500
 501     case PGORegionMode::WholeCFG:
 502       region = selectWholeCFG(transId, profData, cfg, selectedTIDs);
 503       break;
 504   }
 505   assert(region);
 506
 507   if (Trace::moduleEnabled(HPHP::Trace::pgo, 5)) {
 508     std::string dotFileName = std::string("/tmp/trans-cfg-") +
 509                               folly::to<std::string>(transId) + ".dot";
 510
 511     cfg.print(dotFileName, funcId, profData, &selectedTIDs);
 512     FTRACE(5, "selectHotRegion: New Translation {} (file: {}) {}\n",
 513            mcg->tx().profData()->curTransID(), dotFileName,
 514            region ? show(*region) : std::string("empty region"));
 515   }
 516
 517   always_assert(region->instrSize() <= RuntimeOption::EvalJitMaxRegionInstrs);
 518
 519   return region;
 520 }
 521
 522 //////////////////////////////////////////////////////////////////////
 523
 524 static bool postCondMismatch(const RegionDesc::TypePred& postCond,
 525                              const RegionDesc::TypePred& preCond) {
 526   return postCond.location == preCond.location &&
 527          preCond.type.not(postCond.type);
 528 }
 529
 530 bool preCondsAreSatisfied(const RegionDesc::BlockPtr& block,
 531                           const PostConditions& prevPostConds) {
 532   const auto& preConds = block->typePreds();
 533   for (const auto& it : preConds) {
 534     for (const auto& post : prevPostConds) {
 535       const RegionDesc::TypePred& preCond = it.second;
 536       if (postCondMismatch(post, preCond)) {
 537         FTRACE(6, "preCondsAreSatisfied: postcondition check failed!\n"
 538                "  postcondition was {}, precondition was {}\n",
 539                show(post), show(preCond));
 540         return false;
 541       }
 542     }
 543   }
 544   return true;
 545 }
 546
 547 bool breaksRegion(Op opc) {
 548   switch (opc) {
 549     case OpMIterNext:
 550     case OpMIterNextK:
 551     case OpSwitch:
 552     case OpSSwitch:
 553     case OpCreateCont:
 554     case OpYield:
 555     case OpYieldK:
 556     case OpRetC:
 557     case OpRetV:
 558     case OpExit:
 559     case OpFatal:
 560     case OpMIterInit:
 561     case OpMIterInitK:
 562     case OpIterBreak:
 563     case OpDecodeCufIter:
 564     case OpThrow:
 565     case OpUnwind:
 566     case OpEval:
 567     case OpNativeImpl:
 568       return true;
 569
 570     default:
 571       return false;
 572   }
 573 }
 574
 575 //////////////////////////////////////////////////////////////////////
 576
 577 namespace {
 578
 579 struct DFSChecker {
 580
 581   explicit DFSChecker(const RegionDesc& region)
 582     : m_region(region) { }
 583
 584   bool check(RegionDesc::BlockId id) {
 585     if (m_visiting.count(id) > 0) {
 586       // Found a loop. This is only valid if EvalJitLoops is enabled.
 587       return RuntimeOption::EvalJitLoops;
 588     }
 589     if (m_visited.count(id) > 0) return true;
 590     m_visited.insert(id);
 591     m_visiting.insert(id);
 592     for (auto succ : m_region.succs(id)) {
 593       if (!check(succ)) return false;
 594     }
 595     m_visiting.erase(id);
 596     return true;
 597   }
 598
 599   size_t numVisited() const { return m_visited.size(); }
 600
 601  private:
 602   const RegionDesc&      m_region;
 603   RegionDesc::BlockIdSet m_visited;
 604   RegionDesc::BlockIdSet m_visiting;
 605 };
 606
 607 }
 608
 609 /*
 610  * Checks if the given region is well-formed, which entails the
 611  * following properties:
 612  *
 613  *   1) The region has at least one block.
 614  *
 615  *   2) Each block in the region has a different id.
 616  *
 617  *   3) All arcs involve blocks within the region.
 618  *
 619  *   4) For each arc, the bytecode offset of the dst block must
 620  *      possibly follow the execution of the src block.
 621  *
 622  *   5) Each block contains at most one successor corresponding to a
 623  *      given SrcKey.
 624  *
 625  *   6) The region doesn't contain any loops, unless JitLoops is
 626  *      enabled.
 627  *
 628  *   7) All blocks are reachable from the entry block.
 629  *
 630  *   8) For each block, there must be a path from the entry to it that
 631  *      includes only earlier blocks in the region.
 632  *
 633  *   9) The region is topologically sorted unless loops are enabled.
 634  *
 635  */
 636 bool check(const RegionDesc& region, std::string& error) {
 637
 638   auto bad = [&](const std::string& errorMsg) {
 639     error = errorMsg;
 640     return false;
 641   };
 642
 643   // 1) The region has at least one block.
 644   if (region.empty()) return bad("empty region");
 645
 646   RegionDesc::BlockIdSet blockSet;
 647   for (auto b : region.blocks()) {
 648     auto bid = b->id();
 649     // 2) Each block in the region has a different id.
 650     if (blockSet.count(bid)) {
 651       return bad(folly::format("many blocks with id {}", bid).str());
 652     }
 653     blockSet.insert(bid);
 654   }
 655
 656   for (auto b : region.blocks()) {
 657     auto bid = b->id();
 658     SrcKey    lastSk = region.block(bid)->last();
 659     OffsetSet validSuccOffsets = lastSk.succOffsets();
 660     OffsetSet succOffsets;
 661
 662     for (auto succ : region.succs(bid)) {
 663       SrcKey succSk = region.block(succ)->start();
 664       Offset succOffset = succSk.offset();
 665
 666       // 3) All arcs involve blocks within the region.
 667       if (blockSet.count(succ) == 0) {
 668         return bad(folly::format("arc with dst not in the region: {} -> {}",
 669                                  bid, succ).str());
 670       }
 671
 672       // Checks 4) and 5) below don't make sense for arcs corresponding
 673       // to inlined calls and returns, so skip them in such cases.
 674       // This won't be possible once task #4076399 is done.
 675       if (lastSk.func() != succSk.func()) continue;
 676
 677       // 4) For each arc, the bytecode offset of the dst block must
 678       //    possibly follow the execution of the src block.
 679       if (validSuccOffsets.count(succOffset) == 0) {
 680         return bad(folly::format("arc with impossible control flow: {} -> {}",
 681                                  bid, succ).str());
 682       }
 683
 684       // 5) Each block contains at most one successor corresponding to a
 685       //    given SrcKey.
 686       if (succOffsets.count(succOffset) > 0) {
 687         return bad(folly::format("block {} has multiple successors with SK {}",
 688                                  bid, show(succSk)).str());
 689       }
 690       succOffsets.insert(succOffset);
 691     }
 692     for (auto pred : region.preds(bid)) {
 693       if (blockSet.count(pred) == 0) {
 694         return bad(folly::format("arc with src not in the region: {} -> {}",
 695                                  pred, bid).str());
 696       }
 697     }
 698   }
 699
 700   // 6) is checked by dfsCheck.
 701   DFSChecker dfsCheck(region);
 702   if (!dfsCheck.check(region.entry()->id())) {
 703     return bad("region is cyclic");
 704   }
 705
 706   // 7) All blocks are reachable from the entry (first) block.
 707   if (dfsCheck.numVisited() != blockSet.size()) {
 708     return bad("region has unreachable blocks");
 709   }
 710
 711   // 8) and 9) are checked below.
 712   RegionDesc::BlockIdSet visited;
 713   auto& blocks = region.blocks();
 714   for (unsigned i = 0; i < blocks.size(); i++) {
 715     auto bid = blocks[i]->id();
 716     unsigned nVisited = 0;
 717     for (auto pred : region.preds(bid)) {
 718       nVisited += visited.count(pred);
 719     }
 720     // 8) For each block, there must be a path from the entry to it that
 721     //    includes only earlier blocks in the region.
 722     if (nVisited == 0 && i != 0) {
 723       return bad(folly::format("block {} appears before all its predecessors",
 724                                bid).str());
 725     }
 726     // 9) The region is topologically sorted unless loops are enabled.
 727     if (!RuntimeOption::EvalJitLoops && nVisited != region.preds(bid).size()) {
 728       return bad(folly::format("non-topological order (bid: {})", bid).str());
 729     }
 730     visited.insert(bid);
 731   }
 732
 733   return true;
 734 }
 735
 736 //////////////////////////////////////////////////////////////////////
 737
 738 namespace {
 739 template<typename T>
 740 struct Ignore {
 741   bool a(const T&) const { return false; }
 742   bool b(const T&) const { return false; }
 743 };
 744
 745 struct IgnoreTypePred {
 746   explicit IgnoreTypePred(bool aLonger = false)
 747     : m_aLonger(aLonger)
 748   {}
 749
 750   // It's ok for a to have more TypePreds if it's longer.
 751   bool a(const RegionDesc::TypePred& tp) const {
 752     return m_aLonger;
 753   }
 754
 755   // It's ok for b to have more TypePreds if it's for a type we can probably
 756   // get from statically-known stack flavors.
 757   bool b(const RegionDesc::TypePred& tp) const {
 758     return tp.location.tag() == RegionDesc::Location::Tag::Stack &&
 759       tp.location.stackOffset() == 0 &&
 760       tp.type.isBoxed();
 761   }
 762
 763  private:
 764   const bool m_aLonger;
 765 };
 766
 767 struct IgnoreKnownFunc {
 768   // It's ok for a to have known funcs that b doesn't but not the other way
 769   // around.
 770   bool a(const Func*) const { return true; }
 771   bool b(const Func*) const { return false; }
 772 };
 773
 774 template<typename M, typename Cmp = std::equal_to<typename M::mapped_type>,
 775          typename IgnorePred = Ignore<typename M::mapped_type>>
 776 bool mapsEqual(const M& a, const M& b, SrcKey endSk, Cmp equal = Cmp(),
 777                IgnorePred ignore = IgnorePred()) {
 778   // Return true iff every value in aRange also exists in bRange. Leaves 'it'
 779   // pointing to aRange.second either way.
 780   using IterPair = std::pair<typename M::const_iterator,
 781                              typename M::const_iterator>;
 782   auto checkRange = [&](typename M::const_iterator& it, IterPair aRange,
 783                         IterPair bRange, bool aFirst) {
 784     for (it = aRange.first; it != aRange.second; ++it) {
 785       if (aFirst ? ignore.a(it->second) : ignore.b(it->second)) continue;
 786
 787       auto bIt = bRange.first;
 788       for (; bIt != bRange.second; ++bIt) {
 789         if (equal(it->second, bIt->second)) break;
 790       }
 791       if (bIt == bRange.second) {
 792         it = aRange.second;
 793         return false;
 794       }
 795     }
 796     return true;
 797   };
 798
 799   // Check if b has anything a doesn't
 800   for (auto it = b.begin(), end = b.end(); it != end; ) {
 801     if (!checkRange(it, b.equal_range(it->first), a.equal_range(it->first),
 802                     false)) {
 803       return false;
 804     }
 805   }
 806
 807   // Check if a has anything b doesn't, up to b's end.
 808   for (auto it = a.begin(), end = a.end(); it != end; ) {
 809     if (it->first > endSk) break;
 810
 811     if (!checkRange(it, a.equal_range(it->first), b.equal_range(it->first),
 812                     true)) {
 813       return false;
 814     }
 815   }
 816
 817   return true;
 818 }
 819 }
 820
 821 std::string show(RegionDesc::Location l) {
 822   switch (l.tag()) {
 823   case RegionDesc::Location::Tag::Local:
 824     return folly::format("Local{{{}}}", l.localId()).str();
 825   case RegionDesc::Location::Tag::Stack:
 826     return folly::format("Stack{{{},{}}}",
 827                          l.stackOffset(), l.stackOffsetFromFp()).str();
 828   }
 829   not_reached();
 830 }
 831
 832 std::string show(RegionDesc::TypePred ta) {
 833   return folly::format(
 834     "{} :: {}",
 835     show(ta.location),
 836     ta.type.toString()
 837   ).str();
 838 }
 839
 840 std::string show(const PostConditions& pconds) {
 841   std::string ret;
 842   for (const auto& postCond : pconds) {
 843     folly::toAppend("  postcondition: ", show(postCond), "\n", &ret);
 844   }
 845   return ret;
 846 }
 847
 848 std::string show(const RegionDesc::ReffinessPred& pred) {
 849   std::ostringstream out;
 850   out << "offset: " << pred.arSpOffset << " mask: ";
 851   for (auto const bit : pred.mask) out << (bit ? '1' : '0');
 852   out << " vals: ";
 853   for (auto const bit : pred.vals) out << (bit ? '1' : '0');
 854   return out.str();
 855 }
 856
 857 std::string show(RegionContext::LiveType ta) {
 858   return folly::format(
 859     "{} :: {}",
 860     show(ta.location),
 861     ta.type.toString()
 862   ).str();
 863 }
 864
 865 std::string show(RegionContext::PreLiveAR ar) {
 866   return folly::format(
 867     "AR@{}: {} ({})",
 868     ar.stackOff,
 869     ar.func->fullName()->data(),
 870     ar.objOrCls.toString()
 871   ).str();
 872 }
 873
 874 std::string show(const RegionContext& ctx) {
 875   std::string ret;
 876   folly::toAppend(ctx.func->fullName()->data(), "@", ctx.bcOffset,
 877                   ctx.resumed ? "r" : "", "\n", &ret);
 878   for (auto& t : ctx.liveTypes) folly::toAppend(" ", show(t), "\n", &ret);
 879   for (auto& ar : ctx.preLiveARs) folly::toAppend(" ", show(ar), "\n", &ret);
 880
 881   return ret;
 882 }
 883
 884 std::string show(const RegionDesc::Block& b) {
 885   std::string ret{"Block "};
 886   folly::toAppend(b.id(), ' ',
 887                   b.func()->fullName()->data(), '@', b.start().offset(),
 888                   b.start().resumed() ? "r" : "",
 889                   " length ", b.length(),
 890                   " initSpOff ", b.initialSpOffset(), '\n',
 891                   &ret
 892                  );
 893
 894   auto typePreds = makeMapWalker(b.typePreds());
 895   auto byRefs    = makeMapWalker(b.paramByRefs());
 896   auto refPreds  = makeMapWalker(b.reffinessPreds());
 897   auto knownFuncs= makeMapWalker(b.knownFuncs());
 898   auto skIter    = b.start();
 899
 900   const Func* topFunc = nullptr;
 901
 902   for (int i = 0; i < b.length(); ++i) {
 903     while (typePreds.hasNext(skIter)) {
 904       folly::toAppend("  predict: ", show(typePreds.next()), "\n", &ret);
 905     }
 906     while (refPreds.hasNext(skIter)) {
 907       folly::toAppend("  predict reffiness: ", show(refPreds.next()), "\n",
 908                       &ret);
 909     }
 910
 911     std::string knownFunc;
 912     if (knownFuncs.hasNext(skIter)) {
 913       topFunc = knownFuncs.next();
 914     }
 915     if (topFunc) {
 916       const char* inlined = "";
 917       if (i == b.length() - 1 && b.inlinedCallee()) {
 918         assert(topFunc == b.inlinedCallee());
 919         inlined = " (call is inlined)";
 920       }
 921       knownFunc = folly::format(" (top func: {}{})",
 922                                 topFunc->fullName()->data(), inlined).str();
 923     } else {
 924       assert((i < b.length() - 1 || !b.inlinedCallee()) &&
 925              "inlined FCall without a known funcd");
 926     }
 927
 928     std::string byRef;
 929     if (byRefs.hasNext(skIter)) {
 930       byRef = folly::format(" (passed by {})", byRefs.next() ? "reference"
 931                                                              : "value").str();
 932     }
 933
 934     std::string instrString;
 935     folly::toAppend(instrToString((Op*)b.unit()->at(skIter.offset()), b.unit()),
 936                     byRef,
 937                     &instrString);
 938
 939     folly::toAppend(
 940       "    ",
 941       skIter.offset(),
 942       "  ",
 943       knownFunc.empty() ? instrString
 944                         : folly::format("{:<40}", instrString).str(),
 945       knownFunc,
 946       "\n",
 947       &ret
 948     );
 949     skIter.advance(b.unit());
 950   }
 951
 952   folly::toAppend(show(b.postConds()), &ret);
 953
 954   return ret;
 955 }
 956
 957 std::string show(const RegionDesc& region) {
 958   return folly::format(
 959     "Region ({} blocks):\n{}",
 960     region.blocks().size(),
 961     [&]{
 962       std::string ret;
 963       std::string arcs;
 964       for (auto& b : region.blocks()) {
 965         folly::toAppend(show(*b), &ret);
 966         for (auto s : region.succs(b->id())) {
 967           folly::toAppend(folly::format("{} -> {}\n", b->id(), s), &arcs);
 968         }
 969       }
 970       folly::toAppend("Arcs:\n" + arcs, &ret);
 971       folly::toAppend("Side-exiting Blocks:\n",
 972                       folly::join(", ", region.sideExitingBlocks()),
 973                       "\n",
 974                       &ret);
 975       return ret;
 976     }()
 977   ).str();
 978 }
 979
 980 //////////////////////////////////////////////////////////////////////
 981
 982 }}