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

   1 /*
   2    +----------------------------------------------------------------------+
   3    | HipHop for PHP                                                       |
   4    +----------------------------------------------------------------------+
   5    | Copyright (c) 2010-2013 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 <boost/range/adaptors.hpp>
  20
  21 #include "folly/Memory.h"
  22 #include "folly/Conv.h"
  23
  24 #include "hphp/util/assertions.h"
  25 #include "hphp/util/map-walker.h"
  26 #include "hphp/runtime/base/runtime-option.h"
  27 #include "hphp/runtime/vm/jit/normalized-instruction.h"
  28 #include "hphp/runtime/vm/jit/tracelet.h"
  29 #include "hphp/runtime/vm/jit/translator.h"
  30 #include "hphp/runtime/vm/jit/trans-cfg.h"
  31 #include "hphp/runtime/vm/jit/translator-inline.h"
  32 #include "hphp/runtime/vm/jit/region-hot-trace.h"
  33
  34 namespace HPHP { namespace JIT {
  35
  36 TRACE_SET_MOD(region);
  37
  38
  39 //////////////////////////////////////////////////////////////////////
  40
  41 extern RegionDescPtr selectMethod(const RegionContext&);
  42 extern RegionDescPtr selectOneBC(const RegionContext&);
  43 extern RegionDescPtr selectHotBlock(TransID transId,
  44                                     const ProfData* profData,
  45                                     const TransCFG& cfg);
  46
  47 //////////////////////////////////////////////////////////////////////
  48
  49 namespace {
  50
  51 enum class RegionMode {
  52   None,      // empty region
  53
  54   // Modes that create a region by inspecting live VM state
  55   Method,    // region with a whole method
  56   Tracelet,  // single-entry, multiple-exits region that ends on conditional
  57              // branches or when an instruction consumes a value of unknown type
  58   Legacy,    // same as Tracelet, but using the legacy analyze() code
  59 };
  60
  61 RegionMode regionMode() {
  62   auto& s = RuntimeOption::EvalJitRegionSelector;
  63   if (s == ""        ) return RegionMode::None;
  64   if (s == "method"  ) return RegionMode::Method;
  65   if (s == "tracelet") return RegionMode::Tracelet;
  66   if (s == "legacy"  ) return RegionMode::Legacy;
  67   FTRACE(1, "unknown region mode {}: using none\n", s);
  68   assert(false);
  69   return RegionMode::None;
  70 }
  71
  72 enum class PGORegionMode {
  73   Hottrace, // Select a long region, using profile counters to guide the trace
  74   Hotblock, // Select a single block
  75 };
  76
  77 PGORegionMode pgoRegionMode() {
  78   auto& s = RuntimeOption::EvalJitPGORegionSelector;
  79   if (s == "hottrace") return PGORegionMode::Hottrace;
  80   if (s == "hotblock") return PGORegionMode::Hotblock;
  81   FTRACE(1, "unknown pgo region mode {}: using hottrace\n", s);
  82   assert(false);
  83   return PGORegionMode::Hottrace;
  84 }
  85
  86 template<typename Container>
  87 void truncateMap(Container& c, SrcKey final) {
  88   c.erase(c.upper_bound(final), c.end());
  89 }
  90 }
  91
  92 //////////////////////////////////////////////////////////////////////
  93
  94 RegionDesc::Block::Block(const Func* func, Offset start, int length,
  95                          Offset initSpOff)
  96   : m_func(func)
  97   , m_start(start)
  98   , m_last(kInvalidOffset)
  99   , m_length(length)
 100   , m_initialSpOffset(initSpOff)
 101   , m_inlinedCallee(nullptr)
 102 {
 103   assert(length >= 0);
 104   if (length > 0) {
 105     SrcKey sk(func, start);
 106     for (unsigned i = 1; i < length; ++i) sk.advance();
 107     m_last = sk.offset();
 108   }
 109   checkInstructions();
 110   checkMetadata();
 111 }
 112
 113 bool RegionDesc::Block::contains(SrcKey sk) const {
 114   return sk >= start() && sk <= last();
 115 }
 116
 117 void RegionDesc::Block::addInstruction() {
 118   if (m_length > 0) checkInstruction(last().op());
 119   assert((m_last == kInvalidOffset) == (m_length == 0));
 120
 121   ++m_length;
 122   if (m_length == 1) {
 123     m_last = m_start;
 124   } else {
 125     m_last = last().advanced().offset();
 126   }
 127 }
 128
 129 void RegionDesc::Block::truncateAfter(SrcKey final) {
 130   assert_not_implemented(!m_inlinedCallee);
 131
 132   auto skIter = start();
 133   int newLen = -1;
 134   for (int i = 0; i < m_length; ++i, skIter.advance(unit())) {
 135     if (skIter == final) {
 136       newLen = i + 1;
 137       break;
 138     }
 139   }
 140   assert(newLen != -1);
 141   m_length = newLen;
 142   m_last = final.offset();
 143
 144   truncateMap(m_typePreds, final);
 145   truncateMap(m_byRefs, final);
 146   truncateMap(m_refPreds, final);
 147   truncateMap(m_knownFuncs, final);
 148
 149   checkInstructions();
 150   checkMetadata();
 151 }
 152
 153 void RegionDesc::Block::addPredicted(SrcKey sk, TypePred pred) {
 154   FTRACE(2, "Block::addPredicted({}, {})\n", showShort(sk), show(pred));
 155   assert(pred.type <= Type::StackElem);
 156   assert(contains(sk));
 157   m_typePreds.insert(std::make_pair(sk, pred));
 158 }
 159
 160 void RegionDesc::Block::setParamByRef(SrcKey sk, bool byRef) {
 161   FTRACE(2, "Block::setParamByRef({}, {})\n", showShort(sk),
 162          byRef ? "by ref" : "by val");
 163   assert(m_byRefs.find(sk) == m_byRefs.end());
 164   assert(contains(sk));
 165   m_byRefs.insert(std::make_pair(sk, byRef));
 166 }
 167
 168 void RegionDesc::Block::addReffinessPred(SrcKey sk, const ReffinessPred& pred) {
 169   FTRACE(2, "Block::addReffinessPred({}, {})\n", showShort(sk), show(pred));
 170   assert(contains(sk));
 171   m_refPreds.insert(std::make_pair(sk, pred));
 172 }
 173
 174 void RegionDesc::Block::setKnownFunc(SrcKey sk, const Func* func) {
 175   FTRACE(2, "Block::setKnownFunc({}, {})\n", showShort(sk),
 176          func ? func->fullName()->data() : "nullptr");
 177   assert(m_knownFuncs.find(sk) == m_knownFuncs.end());
 178   assert(contains(sk));
 179   auto it = m_knownFuncs.lower_bound(sk);
 180   if (it != m_knownFuncs.begin() && (--it)->second == func) {
 181     // Adding func at this sk won't add any new information.
 182     FTRACE(2, "  func exists at {}, not adding\n", showShort(it->first));
 183     return;
 184   }
 185
 186   m_knownFuncs.insert(std::make_pair(sk, func));
 187 }
 188
 189 void RegionDesc::Block::setPostConditions(const PostConditions& conds) {
 190   m_postConds = conds;
 191 }
 192
 193 /*
 194  * Check invariants about the bytecode instructions in this Block.
 195  *
 196  * 1. Single entry, single exit (aside from exceptions).  I.e. no
 197  *    non-fallthrough instructions mid-block and no control flow (not
 198  *    counting calls as control flow).
 199  *
 200  */
 201 void RegionDesc::Block::checkInstructions() const {
 202   if (!debug || length() == 0) return;
 203
 204   auto u = unit();
 205   auto sk = start();
 206
 207   for (int i = 1; i < length(); ++i) {
 208     if (i != length() - 1) checkInstruction(sk.op());
 209     sk.advance(u);
 210   }
 211   assert(sk.offset() == m_last);
 212 }
 213
 214 void RegionDesc::Block::checkInstruction(Op op) const {
 215   if (instrFlags(op) & TF) {
 216     FTRACE(1, "Bad block: {}\n", show(*this));
 217     assert(!"Block may not contain non-fallthrough instruction unless "
 218            "they are last");
 219   }
 220   if (instrIsNonCallControlFlow(op)) {
 221     FTRACE(1, "Bad block: {}\n", show(*this));
 222     assert(!"Block may not contain control flow instructions unless "
 223            "they are last");
 224   }
 225 }
 226
 227 /*
 228  * Check invariants about the metadata for this Block.
 229  *
 230  * 1. Each SrcKey in m_typePreds, m_byRefs, m_refPreds, and m_knownFuncs is
 231  *    within the bounds of the block.
 232  *
 233  * 2. Each local id referred to in the type prediction list is valid.
 234  *
 235  * 3. (Unchecked) each stack offset in the type prediction list is
 236  *    valid.
 237 */
 238 void RegionDesc::Block::checkMetadata() const {
 239   auto rangeCheck = [&](const char* type, Offset o) {
 240     if (o < m_start || o > m_last) {
 241       std::cerr << folly::format("{} at {} outside range [{}, {}]\n",
 242                                  type, o, m_start, m_last);
 243       assert(!"Region::Block contained out-of-range metadata");
 244     }
 245   };
 246   for (auto& tpred : m_typePreds) {
 247     rangeCheck("type prediction", tpred.first.offset());
 248     auto& loc = tpred.second.location;
 249     switch (loc.tag()) {
 250     case Location::Tag::Local: assert(loc.localId() < m_func->numLocals());
 251                                break;
 252     case Location::Tag::Stack: // Unchecked
 253                                break;
 254     }
 255   }
 256
 257   for (auto& byRef : m_byRefs) {
 258     rangeCheck("parameter reference flag", byRef.first.offset());
 259   }
 260   for (auto& refPred : m_refPreds) {
 261     rangeCheck("reffiness prediction", refPred.first.offset());
 262   }
 263   for (auto& func : m_knownFuncs) {
 264     rangeCheck("known Func*", func.first.offset());
 265   }
 266 }
 267
 268 //////////////////////////////////////////////////////////////////////
 269
 270 RegionDescPtr selectTraceletLegacy(Offset initSpOffset,
 271                                    const Tracelet& tlet) {
 272   typedef RegionDesc::Block Block;
 273
 274   auto region = std::make_shared<RegionDesc>();
 275   SrcKey sk(tlet.m_sk);
 276   auto unit = tlet.func()->unit();
 277
 278   const Func* topFunc = nullptr;
 279   Block* curBlock = nullptr;
 280   auto newBlock = [&](const Func* func, SrcKey start, Offset spOff) {
 281     assert(curBlock == nullptr || curBlock->length() > 0);
 282     region->blocks.push_back(
 283       std::make_shared<Block>(func, start.offset(), 0, spOff));
 284     curBlock = region->blocks.back().get();
 285   };
 286   newBlock(tlet.func(), sk, initSpOffset);
 287
 288   for (auto ni = tlet.m_instrStream.first; ni; ni = ni->next) {
 289     assert(sk == ni->source);
 290     assert(ni->unit() == unit);
 291
 292     Offset curSpOffset = initSpOffset + ni->stackOffset;
 293
 294     curBlock->addInstruction();
 295     if ((curBlock->length() == 1 && ni->funcd != nullptr) ||
 296         ni->funcd != topFunc) {
 297       topFunc = ni->funcd;
 298       curBlock->setKnownFunc(sk, topFunc);
 299     }
 300
 301     if (ni->calleeTrace && !ni->calleeTrace->m_inliningFailed) {
 302       assert(ni->op() == OpFCall);
 303       assert(ni->funcd == ni->calleeTrace->func());
 304       // This should be translated as an inlined call. Insert the blocks of the
 305       // callee in the region.
 306       auto const& callee = *ni->calleeTrace;
 307       curBlock->setInlinedCallee(ni->funcd);
 308       SrcKey cSk = callee.m_sk;
 309       Unit* cUnit = callee.func()->unit();
 310
 311       newBlock(callee.func(), cSk, curSpOffset);
 312
 313       for (auto cni = callee.m_instrStream.first; cni; cni = cni->next) {
 314         assert(cSk == cni->source);
 315         assert(cni->op() == OpRetC ||
 316                cni->op() == OpRetV ||
 317                cni->op() == OpContRetC ||
 318                cni->op() == OpNativeImpl ||
 319                !instrIsNonCallControlFlow(cni->op()));
 320
 321         curBlock->addInstruction();
 322         cSk.advance(cUnit);
 323       }
 324
 325       if (ni->next) {
 326         sk.advance(unit);
 327         newBlock(tlet.func(), sk, curSpOffset);
 328       }
 329       continue;
 330     }
 331
 332     if (!ni->noOp && isFPassStar(ni->op())) {
 333       curBlock->setParamByRef(sk, ni->preppedByRef);
 334     }
 335
 336     if (ni->next && isUnconditionalJmp(ni->op())) {
 337       // A Jmp that isn't the final instruction in a Tracelet means we traced
 338       // through a forward jump in analyze. Update sk to point to the next NI
 339       // in the stream.
 340       auto dest = ni->offset() + ni->imm[0].u_BA;
 341       assert(dest > sk.offset()); // We only trace for forward Jmps for now.
 342       sk.setOffset(dest);
 343
 344       // The Jmp terminates this block.
 345       newBlock(tlet.func(), sk, curSpOffset);
 346     } else {
 347       sk.advance(unit);
 348     }
 349   }
 350
 351   auto& frontBlock = *region->blocks.front();
 352
 353   // Add tracelet guards as predictions on the first instruction. Predictions
 354   // and known types from static analysis will be applied by
 355   // Translator::translateRegion.
 356   for (auto const& dep : tlet.m_dependencies) {
 357     if (dep.second->rtt.isVagueValue() ||
 358         dep.second->location.isThis()) continue;
 359
 360     typedef RegionDesc R;
 361     auto addPred = [&](const R::Location& loc) {
 362       auto type = Type(dep.second->rtt);
 363       frontBlock.addPredicted(tlet.m_sk, {loc, type});
 364     };
 365
 366     switch (dep.first.space) {
 367       case Location::Stack: {
 368         uint32_t offsetFromSp = uint32_t(-dep.first.offset - 1);
 369         uint32_t offsetFromFp = initSpOffset - offsetFromSp;
 370         addPred(R::Location::Stack{offsetFromSp, offsetFromFp});
 371         break;
 372       }
 373       case Location::Local:
 374         addPred(R::Location::Local{uint32_t(dep.first.offset)});
 375         break;
 376
 377       default: not_reached();
 378     }
 379   }
 380
 381   // Add reffiness dependencies as predictions on the first instruction.
 382   for (auto const& dep : tlet.m_refDeps.m_arMap) {
 383     RegionDesc::ReffinessPred pred{dep.second.m_mask,
 384                                    dep.second.m_vals,
 385                                    dep.first};
 386     frontBlock.addReffinessPred(tlet.m_sk, pred);
 387   }
 388
 389   FTRACE(2, "Converted Tracelet:\n{}\nInto RegionDesc:\n{}\n",
 390          tlet.toString(), show(*region));
 391   return region;
 392 }
 393
 394 RegionDescPtr selectRegion(const RegionContext& context,
 395                            const Tracelet* t,
 396                            TransKind kind) {
 397   auto const mode = regionMode();
 398
 399   FTRACE(1,
 400     "Select region: mode={} context:\n{}",
 401     static_cast<int>(mode), show(context)
 402   );
 403
 404   auto region = [&]{
 405     try {
 406       switch (mode) {
 407         case RegionMode::None:     return RegionDescPtr{nullptr};
 408         case RegionMode::Method:   return selectMethod(context);
 409         case RegionMode::Tracelet: return selectTracelet(context, 0,
 410                                                          kind == TransProfile);
 411         case RegionMode::Legacy:
 412                  always_assert(t); return selectTraceletLegacy(context.spOffset,
 413                                                                *t);
 414       }
 415       not_reached();
 416     } catch (const std::exception& e) {
 417       FTRACE(1, "region selector threw: {}\n", e.what());
 418       return RegionDescPtr{nullptr};
 419     }
 420   }();
 421
 422   if (region) {
 423     FTRACE(3, "{}", show(*region));
 424   } else {
 425     FTRACE(1, "no region selectable; using tracelet compiler\n");
 426   }
 427
 428   return region;
 429 }
 430
 431 RegionDescPtr selectHotRegion(TransID transId,
 432                               TranslatorX64* tx64) {
 433
 434   assert(RuntimeOption::EvalJitPGO);
 435
 436   const ProfData* profData = tx64->profData();
 437   FuncId funcId = profData->transFuncId(transId);
 438   TransCFG cfg(funcId, profData, tx64->getSrcDB(), tx64->getJmpToTransIDMap());
 439   TransIDSet selectedTIDs;
 440   assert(regionMode() != RegionMode::Method);
 441   RegionDescPtr region;
 442   switch (pgoRegionMode()) {
 443     case PGORegionMode::Hottrace:
 444       region = selectHotTrace(transId, profData, cfg, selectedTIDs);
 445       break;
 446
 447     case PGORegionMode::Hotblock:
 448       region = selectHotBlock(transId, profData, cfg);
 449       break;
 450   }
 451   assert(region);
 452
 453   if (Trace::moduleEnabled(HPHP::Trace::pgo, 5)) {
 454     std::string dotFileName = std::string("/tmp/trans-cfg-") +
 455                               folly::to<std::string>(transId) + ".dot";
 456
 457     cfg.print(dotFileName, funcId, profData, &selectedTIDs);
 458     FTRACE(5, "selectHotRegion: New Translation {} (file: {}) {}\n",
 459            tx64->profData()->curTransID(), dotFileName,
 460            region ? show(*region) : std::string("empty region"));
 461   }
 462
 463   return region;
 464 }
 465
 466 //////////////////////////////////////////////////////////////////////
 467
 468 static bool postCondMismatch(const RegionDesc::TypePred& postCond,
 469                              const RegionDesc::TypePred& preCond) {
 470   return postCond.location == preCond.location &&
 471          preCond.type.not(postCond.type);
 472 }
 473
 474 bool preCondsAreSatisfied(const RegionDesc::BlockPtr& block,
 475                           const PostConditions& prevPostConds) {
 476   const auto& preConds = block->typePreds();
 477   for (const auto& it : preConds) {
 478     for (const auto& post : prevPostConds) {
 479       const RegionDesc::TypePred& preCond = it.second;
 480       if (postCondMismatch(post, preCond)) {
 481         FTRACE(6, "preCondsAreSatisfied: postcondition check failed!\n"
 482                "  postcondition was {}, precondition was {}\n",
 483                show(post), show(preCond));
 484         return false;
 485       }
 486     }
 487   }
 488   return true;
 489 }
 490
 491 //////////////////////////////////////////////////////////////////////
 492
 493 std::string show(RegionDesc::Location l) {
 494   switch (l.tag()) {
 495   case RegionDesc::Location::Tag::Local:
 496     return folly::format("Local{{{}}}", l.localId()).str();
 497   case RegionDesc::Location::Tag::Stack:
 498     return folly::format("Stack{{{}, {}}}",
 499                          l.stackOffset(), l.stackOffsetFromFp()).str();
 500   }
 501   not_reached();
 502 }
 503
 504 std::string show(RegionDesc::TypePred ta) {
 505   return folly::format(
 506     "{} :: {}",
 507     show(ta.location),
 508     ta.type.toString()
 509   ).str();
 510 }
 511
 512 std::string show(const RegionDesc::ReffinessPred& pred) {
 513   std::ostringstream out;
 514   out << "offset: " << pred.arSpOffset << " mask: ";
 515   for (auto const bit : pred.mask) out << (bit ? '1' : '0');
 516   out << " vals: ";
 517   for (auto const bit : pred.vals) out << (bit ? '1' : '0');
 518   return out.str();
 519 }
 520
 521 std::string show(RegionContext::LiveType ta) {
 522   return folly::format(
 523     "{} :: {}",
 524     show(ta.location),
 525     ta.type.toString()
 526   ).str();
 527 }
 528
 529 std::string show(RegionContext::PreLiveAR ar) {
 530   return folly::format(
 531     "AR@{}: {} ({})",
 532     ar.stackOff,
 533     ar.func->fullName()->data(),
 534     ar.objOrCls.toString()
 535   ).str();
 536 }
 537
 538 std::string show(const RegionContext& ctx) {
 539   std::string ret;
 540   folly::toAppend(ctx.func->fullName()->data(), "@", ctx.bcOffset, "\n", &ret);
 541   for (auto& t : ctx.liveTypes) folly::toAppend(" ", show(t), "\n", &ret);
 542   for (auto& ar : ctx.preLiveARs) folly::toAppend(" ", show(ar), "\n", &ret);
 543
 544   return ret;
 545 }
 546
 547 std::string show(const RegionDesc::Block& b) {
 548   std::string ret{"Block "};
 549   folly::toAppend(
 550     b.func()->fullName()->data(), '@', b.start().offset(),
 551     " length ", b.length(), " initSpOff ", b.initialSpOffset(), '\n',
 552     &ret
 553   );
 554
 555   auto typePreds = makeMapWalker(b.typePreds());
 556   auto byRefs    = makeMapWalker(b.paramByRefs());
 557   auto refPreds  = makeMapWalker(b.reffinessPreds());
 558   auto knownFuncs= makeMapWalker(b.knownFuncs());
 559   auto skIter    = b.start();
 560
 561   const Func* topFunc = nullptr;
 562
 563   for (int i = 0; i < b.length(); ++i) {
 564     while (typePreds.hasNext(skIter)) {
 565       folly::toAppend("  predict: ", show(typePreds.next()), "\n", &ret);
 566     }
 567     while (refPreds.hasNext(skIter)) {
 568       folly::toAppend("  predict reffiness: ", show(refPreds.next()), "\n",
 569                       &ret);
 570     }
 571
 572     std::string knownFunc;
 573     if (knownFuncs.hasNext(skIter)) {
 574       topFunc = knownFuncs.next();
 575     }
 576     if (topFunc) {
 577       const char* inlined = "";
 578       if (i == b.length() - 1 && b.inlinedCallee()) {
 579         assert(topFunc == b.inlinedCallee());
 580         inlined = " (call is inlined)";
 581       }
 582       knownFunc = folly::format(" (top func: {}{})",
 583                                 topFunc->fullName()->data(), inlined).str();
 584     } else {
 585       assert((i < b.length() - 1 || !b.inlinedCallee()) &&
 586              "inlined FCall without a known funcd");
 587     }
 588
 589     std::string byRef;
 590     if (byRefs.hasNext(skIter)) {
 591       byRef = folly::format(" (passed by {})", byRefs.next() ? "reference"
 592                                                              : "value").str();
 593     }
 594
 595     std::string instrString;
 596     folly::toAppend(instrToString((Op*)b.unit()->at(skIter.offset()), b.unit()),
 597                     byRef,
 598                     &instrString);
 599
 600     folly::toAppend(
 601       "    ",
 602       skIter.offset(),
 603       "  ",
 604       knownFunc.empty() ? instrString
 605                         : folly::format("{:<40}", instrString).str(),
 606       knownFunc,
 607       "\n",
 608       &ret
 609     );
 610     skIter.advance(b.unit());
 611   }
 612
 613   for (const auto& postCond : b.postConds()) {
 614     folly::toAppend("  postcondition: ", show(postCond), "\n", &ret);
 615   }
 616
 617   return ret;
 618 }
 619
 620 std::string show(const RegionDesc& region) {
 621   return folly::format(
 622     "Region ({} blocks):\n{}",
 623     region.blocks.size(),
 624     [&]{
 625       std::string ret;
 626       for (auto& b : region.blocks) {
 627         folly::toAppend(show(*b), &ret);
 628       }
 629       return ret;
 630     }()
 631   ).str();
 632 }
 633
 634 //////////////////////////////////////////////////////////////////////
 635
 636 }}