hphp/runtime/vm/jit/translate-region.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
  17 #include "hphp/runtime/vm/jit/translate-region.h"
  18
  19 #include "hphp/util/arch.h"
  20 #include "hphp/util/map-walker.h"
  21 #include "hphp/util/ringbuffer.h"
  22 #include "hphp/util/timer.h"
  23 #include "hphp/util/trace.h"
  24
  25 #include "hphp/runtime/base/runtime-option.h"
  26
  27 #include "hphp/runtime/vm/bc-pattern.h"
  28
  29 #include "hphp/runtime/vm/hhbc-codec.h"
  30 #include "hphp/runtime/vm/jit/inlining-decider.h"
  31 #include "hphp/runtime/vm/jit/irgen.h"
  32 #include "hphp/runtime/vm/jit/irgen-internal.h"
  33 #include "hphp/runtime/vm/jit/ir-unit.h"
  34 #include "hphp/runtime/vm/jit/location.h"
  35 #include "hphp/runtime/vm/jit/mcgen.h"
  36 #include "hphp/runtime/vm/jit/mcgen-translate.h"
  37 #include "hphp/runtime/vm/jit/normalized-instruction.h"
  38 #include "hphp/runtime/vm/jit/opt.h"
  39 #include "hphp/runtime/vm/jit/print.h"
  40 #include "hphp/runtime/vm/jit/prof-data.h"
  41 #include "hphp/runtime/vm/jit/punt.h"
  42 #include "hphp/runtime/vm/jit/region-selection.h"
  43 #include "hphp/runtime/vm/jit/timer.h"
  44 #include "hphp/runtime/vm/jit/type.h"
  45
  46 TRACE_SET_MOD(trans);
  47
  48 namespace HPHP { namespace jit {
  49
  50 //////////////////////////////////////////////////////////////////////
  51
  52 namespace {
  53
  54 enum class TranslateResult {
  55   Retry,
  56   Success
  57 };
  58
  59 /*
  60  * Data used by irGenRegion() and friends to pass information between retries.
  61  */
  62 struct TranslateRetryContext {
  63   // Bytecode instructions that must be interpreted.
  64   ProfSrcKeySet toInterp;
  65
  66   // Regions to not inline
  67   jit::fast_set<ProfSrcKey, ProfSrcKey::Hasher> inlineBlacklist;
  68 };
  69
  70 /*
  71  * Create a map from RegionDesc::BlockId -> IR Block* for all region blocks.
  72  */
  73 BlockIdToIRBlockMap createBlockMap(irgen::IRGS& irgs,
  74                                    const RegionDesc& region) {
  75   auto ret = BlockIdToIRBlockMap{};
  76
  77   auto& irb = *irgs.irb;
  78   auto const& blocks = region.blocks();
  79   for (unsigned i = 0; i < blocks.size(); i++) {
  80     auto const rBlock = blocks[i];
  81     auto const id = rBlock->id();
  82
  83     // NB: This maps the region entry block to a new IR block, even though
  84     // we've already constructed an IR entry block. We'll make the IR entry
  85     // block jump to this block.
  86     assertx(!hasTransID(id) || profData());
  87     auto transCount = hasTransID(id)
  88       ? region.blockProfCount(id)
  89       : 1;
  90     uint64_t profCount = transCount * irgs.profFactor;
  91     auto const iBlock = irb.unit().defBlock(profCount);
  92
  93     ret[id] = iBlock;
  94     FTRACE(1,
  95            "createBlockMaps: RegionBlock {} => IRBlock {} (BC offset = {})\n",
  96            id, iBlock->id(), rBlock->start().offset());
  97   }
  98
  99   return ret;
 100 }
 101
 102 /*
 103  * Set IRBuilder's Block associated to blockId's block according to
 104  * the mapping in blockIdToIRBlock.
 105  */
 106 void setIRBlock(irgen::IRGS& irgs,
 107                 RegionDesc::BlockId blockId,
 108                 const RegionDesc& region,
 109                 const BlockIdToIRBlockMap& blockIdToIRBlock) {
 110   auto& irb = *irgs.irb;
 111   auto rBlock = region.block(blockId);
 112   auto sk = rBlock->start();
 113
 114   auto iit = blockIdToIRBlock.find(blockId);
 115   assertx(iit != blockIdToIRBlock.end());
 116
 117   assertx(!irb.hasBlock(sk));
 118   FTRACE(3, "  setIRBlock: blockId {}, offset {} => IR Block {}\n",
 119          blockId, sk.offset(), iit->second->id());
 120   irb.setBlock(sk, iit->second);
 121 }
 122
 123 /*
 124  * Set IRBuilder's Blocks for srcBlockId's successors' offsets within
 125  * the region.  It also sets the guard-failure block, if any.
 126  */
 127 void setSuccIRBlocks(irgen::IRGS& irgs,
 128                      const RegionDesc& region,
 129                      RegionDesc::BlockId srcBlockId,
 130                      const BlockIdToIRBlockMap& blockIdToIRBlock) {
 131   FTRACE(3, "setSuccIRBlocks: srcBlockId = {}\n", srcBlockId);
 132   auto& irb = *irgs.irb;
 133   irb.resetOffsetMapping();
 134   for (auto dstBlockId : region.succs(srcBlockId)) {
 135     setIRBlock(irgs, dstBlockId, region, blockIdToIRBlock);
 136   }
 137   if (auto nextRetrans = region.nextRetrans(srcBlockId)) {
 138     auto it = blockIdToIRBlock.find(nextRetrans.value());
 139     assertx(it != blockIdToIRBlock.end());
 140     irb.setGuardFailBlock(it->second);
 141   } else {
 142     irb.resetGuardFailBlock();
 143   }
 144 }
 145
 146 bool blockHasUnprocessedPred(
 147   const RegionDesc&             region,
 148   RegionDesc::BlockId           blockId,
 149   const RegionDesc::BlockIdSet& processedBlocks)
 150 {
 151   for (auto predId : region.preds(blockId)) {
 152     if (processedBlocks.count(predId) == 0) {
 153       return true;
 154     }
 155   }
 156   if (auto prevRetrans = region.prevRetrans(blockId)) {
 157     if (processedBlocks.count(prevRetrans.value()) == 0) {
 158       return true;
 159     }
 160   }
 161   return false;
 162 }
 163
 164 /*
 165  * If this region's entry block is at an entry point for a function (DV init or
 166  * main entry), we can assert that all non-parameter locals are Uninit under
 167  * some conditions.  This function checks the necessary conditions and, if they
 168  * hold, emits such type assertions.
 169  */
 170 void emitEntryAssertions(irgen::IRGS& irgs, const Func* func, SrcKey sk) {
 171   if (!func->isEntry(sk.offset())) return;
 172
 173   // If we're at the Func main entry point, we can't assume anything if there
 174   // are DV initializers, because they can run arbitrary code before they get
 175   // here (and they do, in some hhas-based builtins, and they may not even get
 176   // to the Func main entry point).
 177   if (sk.offset() == func->base()) {
 178     // The assertions inserted here are only valid if the first bytecode
 179     // instruction does not have unprocessed predecessors.  This invariant is
 180     // ensured by the emitter using an EntryNop instruction when necessary.
 181     for (auto& pinfo : func->params()) {
 182       if (pinfo.hasDefaultValue()) return;
 183     }
 184   }
 185
 186   if (func->isClosureBody()) {
 187     // In a closure, non-parameter locals can have types other than Uninit
 188     // after the prologue runs.  (Local 0 will be the closure itself, and other
 189     // locals will have used vars unpacked into them.)  We rely on hhbbc to
 190     // assert these types.
 191     return;
 192   }
 193   if (func->isPseudoMain()) {
 194     // Pseudomains inherit the variable environment of their caller, so don't
 195     // assert anything in them.
 196     return;
 197   }
 198   auto const numLocs = func->numLocals();
 199   auto loc = func->numParams();
 200   if (func->hasReifiedGenerics()) {
 201     // First non parameter local will specially set
 202     auto const t = RuntimeOption::EvalHackArrDVArrs ? TVec : TArr;
 203     irgen::assertTypeLocation(irgs, Location::Local { loc }, t);
 204     loc++;
 205   }
 206   for (; loc < numLocs; ++loc) {
 207     auto const location = Location::Local { loc };
 208     irgen::assertTypeLocation(irgs, location, TUninit);
 209   }
 210 }
 211
 212 /*
 213  * Emit type and reffiness prediction guards.
 214  */
 215 void emitPredictionsAndPreConditions(irgen::IRGS& irgs,
 216                                      const RegionDesc& /*region*/,
 217                                      const RegionDesc::Block& block,
 218                                      bool isEntry, bool checkOuterTypeOnly) {
 219   auto const sk = block.start();
 220   auto const bcOff = sk.offset();
 221   auto& typePredictions = block.typePredictions();
 222   auto& typePreConditions = block.typePreConditions();
 223
 224   if (isEntry) {
 225     irgen::ringbufferEntry(irgs, Trace::RBTypeTraceletGuards, sk);
 226     emitEntryAssertions(irgs, block.func(), sk);
 227   }
 228
 229   // Emit type predictions.
 230   for (auto const& pred : typePredictions) {
 231     auto type = pred.type;
 232     auto loc  = pred.location;
 233     assertx(type <= TGen);
 234     irgen::predictType(irgs, loc, type);
 235   }
 236
 237   // Emit type guards/preconditions.
 238   for (auto const& preCond : typePreConditions) {
 239     auto type = preCond.type;
 240     auto loc  = preCond.location;
 241     assertx(type <= TGen);
 242     irgen::checkType(irgs, loc, type, bcOff, checkOuterTypeOnly);
 243   }
 244
 245   // Finish emitting guards, and emit profiling counters.
 246   if (isEntry) {
 247     irgen::gen(irgs, EndGuards);
 248
 249     if (irgs.context.kind == TransKind::Profile) {
 250       if (block.func()->isEntry(bcOff) && !mcgen::retranslateAllEnabled()) {
 251         irgen::checkCold(irgs, irgs.context.transID);
 252       } else {
 253         irgen::incProfCounter(irgs, irgs.context.transID);
 254       }
 255     }
 256     irgen::ringbufferEntry(irgs, Trace::RBTypeTraceletBody, sk);
 257
 258     // In the entry block, hhbc-translator gets a chance to emit some code
 259     // immediately after the initial checks on the first instruction.
 260     irgen::prepareEntry(irgs);
 261   }
 262 }
 263
 264 void initNormalizedInstruction(
 265   NormalizedInstruction& inst,
 266   irgen::IRGS& irgs,
 267   const RegionDesc& region,
 268   RegionDesc::BlockId blockId,
 269   const Func* topFunc,
 270   bool lastInstr,
 271   bool toInterp
 272 ) {
 273   inst.funcd = topFunc;
 274
 275   if (lastInstr) {
 276     inst.endsRegion  = region.isExit(blockId);
 277   }
 278
 279   // We can get a more precise output type for interpOne if we know all of
 280   // its inputs, so we still populate the rest of the instruction even if
 281   // this is true.
 282   inst.interp = toInterp;
 283 }
 284
 285 bool shouldTrySingletonInline(const RegionDesc& region,
 286                               const NormalizedInstruction& inst,
 287                               unsigned /*instIdx*/, TransFlags trflags) {
 288   if (!RuntimeOption::RepoAuthoritative) return false;
 289
 290   // I don't really want to inline PPC64, yet.
 291   if (arch() == Arch::PPC64) return false;
 292
 293   // Don't inline if we're retranslating due to a side-exit from an
 294   // inlined call.
 295   auto const startSk = region.start();
 296   if (trflags.noinlineSingleton && startSk == inst.source) return false;
 297
 298   // Bail early if this isn't a push.
 299   if (inst.op() != Op::FPushFuncD &&
 300       inst.op() != Op::FPushClsMethodRD &&
 301       inst.op() != Op::FPushClsMethodD) {
 302     return false;
 303   }
 304
 305   return true;
 306 }
 307
 308 /*
 309  * Check if `i' is an FPush{Func,ClsMethod}D followed by an FCall to a
 310  * function with a singleton pattern, and if so, inline it.  Returns true if
 311  * this succeeds, else false.
 312  */
 313 bool tryTranslateSingletonInline(irgen::IRGS& irgs,
 314                                  const NormalizedInstruction& ninst,
 315                                  const Func* funcd) {
 316   using Atom = BCPattern::Atom;
 317   using Captures = BCPattern::CaptureVec;
 318
 319   if (!funcd) return false;
 320
 321   // Make sure we have an acceptable FPush and non-null callee.
 322   assertx(ninst.op() == Op::FPushFuncD ||
 323           ninst.op() == Op::FPushClsMethodD ||
 324           ninst.op() == Op::FPushClsMethodRD);
 325
 326   auto fcall = ninst.nextSk();
 327
 328   // Check if the next instruction is an acceptable FCall.
 329   if (fcall.op() != Op::FCall || funcd->isResumable()) {
 330     return false;
 331   }
 332
 333   // Check for the static property pattern.
 334   auto retc  = Atom(Op::RetC);
 335
 336   // Factory for String atoms that are required to match another captured
 337   // String opcode.
 338   auto same_string_as = [&] (int i) {
 339     return Atom(Op::String).onlyif([=] (PC pc, const Captures& captures) {
 340       auto string1 = pc;
 341       auto string2 = captures[i];
 342       assertx(peek_op(string1) == Op::String);
 343       assertx(peek_op(string2) == Op::String);
 344
 345       auto const unit = funcd->unit();
 346       auto sd1 = unit->lookupLitstrId(getImmPtr(string1, 0)->u_SA);
 347       auto sd2 = unit->lookupLitstrId(getImmPtr(string2, 0)->u_SA);
 348
 349       return (sd1 && sd1 == sd2);
 350     });
 351   };
 352
 353   auto stringProp = same_string_as(0);
 354   auto stringCls  = same_string_as(1);
 355   auto agetc = Atom(Op::ClsRefGetC);
 356   auto cgets = Atom(Op::CGetS);
 357
 358   // Look for a class static singleton pattern.
 359   auto result = BCPattern {
 360     Atom(Op::String).capture(),
 361     Atom(Op::String).capture(),
 362     Atom(Op::ClsRefGetC),
 363     Atom(Op::CGetS),
 364     Atom(Op::IsTypeC),
 365     Atom::alt(
 366       Atom(Op::JmpZ).taken({stringProp, stringCls, agetc, cgets, retc}),
 367       Atom::seq(Atom(Op::JmpNZ), stringProp, stringCls, agetc, cgets, retc)
 368     )
 369   }.ignore(
 370     {Op::AssertRATL, Op::AssertRATStk}
 371   ).matchAnchored(funcd);
 372
 373   if (result.found()) {
 374     try {
 375       irgen::prepareForNextHHBC(irgs, nullptr, ninst.source, false);
 376       irgen::inlSingletonSProp(
 377         irgs,
 378         funcd,
 379         result.getCapture(1),
 380         result.getCapture(0)
 381       );
 382     } catch (const FailedIRGen& e) {
 383       return false;
 384     }
 385     TRACE(1, "[singleton-sprop] %s <- %s\n",
 386         funcd->fullName()->data(),
 387         fcall.func()->fullName()->data());
 388     return true;
 389   }
 390
 391   return false;
 392 }
 393
 394 /*
 395  * Returns the id of the next region block in workQ whose
 396  * corresponding IR block is currently reachable from the IR unit's
 397  * entry, or folly::none if no such block exists.  Furthermore, any
 398  * unreachable blocks appearing before the first reachable block are
 399  * moved to the end of workQ.
 400  */
 401 folly::Optional<RegionDesc::BlockId> nextReachableBlock(
 402   jit::queue<RegionDesc::BlockId>& workQ,
 403   const irgen::IRBuilder& irb,
 404   const BlockIdToIRBlockMap& blockIdToIRBlock
 405 ) {
 406   auto const size = workQ.size();
 407   for (size_t i = 0; i < size; i++) {
 408     auto const regionBlockId = workQ.front();
 409     workQ.pop();
 410     auto it = blockIdToIRBlock.find(regionBlockId);
 411     assertx(it != blockIdToIRBlock.end());
 412     auto irBlock = it->second;
 413     if (irb.canStartBlock(irBlock)) return regionBlockId;
 414     // Put the block back at the end of workQ, since it may become
 415     // reachable after processing some of the other blocks.
 416     workQ.push(regionBlockId);
 417   }
 418   return folly::none;
 419 }
 420
 421 /*
 422  * Returns whether or not block `bid' is in the retranslation chain
 423  * for `region's entry block.
 424  */
 425 bool inEntryRetransChain(RegionDesc::BlockId bid, const RegionDesc& region) {
 426   auto block = region.entry();
 427   if (block->start() != region.block(bid)->start()) return false;
 428   while (true) {
 429     if (block->id() == bid) return true;
 430     auto nextRetrans = region.nextRetrans(block->id());
 431     if (!nextRetrans) return false;
 432     block = region.block(nextRetrans.value());
 433   }
 434   not_reached();
 435 }
 436
 437 /*
 438  * If `psk' is not an FCall with inlinable `callee', return nullptr.
 439  *
 440  * Otherwise, select a region for `callee' if one is not already present in
 441  * `retry'.  Update `inl' and return the region if it's inlinable.
 442  */
 443 RegionDescPtr getInlinableCalleeRegion(const ProfSrcKey& psk,
 444                                        const Func* callee,
 445                                        TranslateRetryContext& retry,
 446                                        InliningDecider& inl,
 447                                        const irgen::IRGS& irgs,
 448                                        int32_t maxBCInstrs,
 449                                        int& calleeCost,
 450                                        Annotations& annotations) {
 451   if (psk.srcKey.op() != Op::FCall) {
 452     return nullptr;
 453   }
 454   auto annotationsPtr = mcgen::dumpTCAnnotation(irgs.context.kind) ?
 455                         &annotations : nullptr;
 456   if (!inl.canInlineAt(psk.srcKey, callee, annotationsPtr)) return nullptr;
 457
 458   auto const& fpiStack = irgs.irb->fs().fpiStack();
 459   // Make sure the FPushOp was in the region
 460   if (fpiStack.empty()) {
 461     return nullptr;
 462   }
 463
 464   // Make sure the FPushOp wasn't interpreted, based on a spanned another call,
 465   // or marked as not eligible for inlining by frame-state.
 466   auto const& info = fpiStack.back();
 467   if (!info.inlineEligible || info.spansCall) {
 468     return nullptr;
 469   }
 470
 471   if (retry.inlineBlacklist.find(psk) != retry.inlineBlacklist.end()) {
 472     return nullptr;
 473   }
 474
 475   auto calleeRegion = selectCalleeRegion(psk.srcKey, callee, irgs, inl,
 476                                          maxBCInstrs, annotations);
 477   if (!calleeRegion || calleeRegion->instrSize() > maxBCInstrs) {
 478     return nullptr;
 479   }
 480
 481   calleeCost = inl.accountForInlining(psk.srcKey, info.fpushOpc, callee,
 482                                       *calleeRegion, irgs, annotations);
 483   return calleeRegion;
 484 }
 485
 486 static bool needsSurpriseCheck(Op op) {
 487   return op == Op::JmpZ || op == Op::JmpNZ || op == Op::Jmp;
 488 }
 489
 490 // Unlike isCompare, this also allows Not, Same, NSame and Cmp.
 491 static bool isCmp(Op op) {
 492   return op == Op::Not ||
 493       op == Op::Same ||
 494       op == Op::NSame ||
 495       op == Op::Eq ||
 496       op == Op::Neq ||
 497       op == Op::Lt ||
 498       op == Op::Lte ||
 499       op == Op::Gt ||
 500       op == Op::Gte ||
 501       op == Op::Cmp;
 502 }
 503
 504 TranslateResult irGenRegionImpl(irgen::IRGS& irgs,
 505                                 const RegionDesc& region,
 506                                 TranslateRetryContext& retry,
 507                                 InliningDecider& inl,
 508                                 int32_t& budgetBCInstrs,
 509                                 double profFactor,
 510                                 Annotations& annotations) {
 511   const Timer irGenTimer(Timer::irGenRegionAttempt);
 512   auto& irb = *irgs.irb;
 513   auto prevRegion      = irgs.region;      irgs.region      = &region;
 514   auto prevProfFactor  = irgs.profFactor;  irgs.profFactor  = profFactor;
 515   auto prevProfTransID = irgs.profTransID; irgs.profTransID = kInvalidTransID;
 516   auto prevOffsetMapping = irb.saveAndClearOffsetMapping();
 517   auto prevGuardFailBlock = irb.guardFailBlock(); irb.resetGuardFailBlock();
 518   SCOPE_EXIT {
 519     irgs.region      = prevRegion;
 520     irgs.profFactor  = prevProfFactor;
 521     irgs.profTransID = prevProfTransID;
 522     irb.restoreOffsetMapping(std::move(prevOffsetMapping));
 523     irb.setGuardFailBlock(prevGuardFailBlock);
 524   };
 525
 526   FTRACE(1, "translateRegion (mode={}, profFactor={:.2}) starting with:\n{}\n",
 527          show(irgs.context.kind), profFactor, show(region));
 528
 529   if (RuntimeOption::EvalDumpRegion &&
 530       mcgen::dumpTCAnnotation(irgs.context.kind)) {
 531     annotations.emplace_back("RegionDesc", show(region));
 532   }
 533
 534   std::string errorMsg;
 535   always_assert_flog(check(region, errorMsg), "{}", errorMsg);
 536
 537   auto regionSize = region.instrSize();
 538   always_assert(regionSize <= budgetBCInstrs);
 539   budgetBCInstrs -= regionSize;
 540
 541   // Create a map from region blocks to their corresponding initial IR blocks.
 542   auto blockIdToIRBlock = createBlockMap(irgs, region);
 543
 544   if (!inl.inlining()) {
 545     // Prepare to start translation of the first region block.
 546     auto const entry = irb.unit().entry();
 547     irb.startBlock(entry, false /* hasUnprocPred */);
 548
 549     // Make the IR entry block jump to the IR block we mapped the region entry
 550     // block to (they are not the same!).
 551     {
 552       auto const irBlock = blockIdToIRBlock[region.entry()->id()];
 553       always_assert(irBlock != entry);
 554       irgen::gen(irgs, Jmp, irBlock);
 555     }
 556   } else {
 557     // Set the first callee block as a successor to the FCall's block and
 558     // "fallthrough" from the caller into the callee's first block.
 559     setIRBlock(irgs, region.entry()->id(), region, blockIdToIRBlock);
 560     irgen::endBlock(irgs, region.start().offset());
 561   }
 562
 563   RegionDesc::BlockIdSet processedBlocks;
 564
 565   auto& blocks = region.blocks();
 566
 567   jit::queue<RegionDesc::BlockId> workQ;
 568   for (auto& block : blocks) workQ.push(block->id());
 569
 570   while (auto optBlockId = nextReachableBlock(workQ, irb, blockIdToIRBlock)) {
 571     auto const blockId = optBlockId.value();
 572     auto const& block  = *region.block(blockId);
 573     auto sk            = block.start();
 574     auto knownFuncs    = makeMapWalker(block.knownFuncs());
 575     auto skipTrans     = false;
 576     bool emitedSurpriseCheck = false;
 577
 578     SCOPE_ASSERT_DETAIL("IRGS") { return show(irgs); };
 579
 580     const Func* topFunc = nullptr;
 581     irgs.profTransID = hasTransID(blockId) ? getTransID(blockId)
 582                                            : kInvalidTransID;
 583     irgs.inlineLevel = inl.depth();
 584     irgs.firstBcInst = inEntryRetransChain(blockId, region) && !inl.inlining();
 585     irgen::prepareForNextHHBC(irgs, nullptr, sk, false);
 586
 587     // Prepare to start translating this region block.  This loads the
 588     // FrameState for the IR block corresponding to the start of this
 589     // region block, and it also sets the map from BC offsets to IR
 590     // blocks for the successors of this block in the region.
 591     auto const irBlock = blockIdToIRBlock[blockId];
 592     const bool hasUnprocPred = blockHasUnprocessedPred(region, blockId,
 593                                                        processedBlocks);
 594     // Note: a block can have an unprocessed predecessor even if the
 595     // region is acyclic, e.g. if the IR was able to prove a path was
 596     // unfeasible due to incompatible types.
 597     if (!irb.startBlock(irBlock, hasUnprocPred)) {
 598       // This can't happen because we picked a reachable block from the workQ.
 599       always_assert_flog(
 600         0, "translateRegion: tried to startBlock on unreachable block {}\n",
 601         blockId
 602       );
 603     }
 604     setSuccIRBlocks(irgs, region, blockId, blockIdToIRBlock);
 605
 606     // Emit an ExitPlaceholder at the beginning of the block if any of the
 607     // optimizations that can benefit from it are enabled, and only if we're
 608     // not inlining. The inlining decision could be smarter but this is enough
 609     // for now since we never emit guards in inlined functions (t7385908).
 610     const bool emitExitPlaceholder = irgs.inlineLevel == 0 &&
 611       (RuntimeOption::EvalHHIRLICM && hasUnprocPred);
 612     if (emitExitPlaceholder) irgen::makeExitPlaceholder(irgs);
 613
 614     // Emit the type and reffiness predictions for this region block. If this is
 615     // the first instruction in the region, we check inner type eagerly, insert
 616     // `EndGuards` after the checks, and generate profiling code in profiling
 617     // translations.
 618     auto const isEntry = &block == region.entry().get() && !inl.inlining();
 619     auto const checkOuterTypeOnly = !irb.guardFailBlock() &&
 620       (!isEntry || irgs.context.kind != TransKind::Profile);
 621     emitPredictionsAndPreConditions(irgs, region, block, isEntry,
 622                                     checkOuterTypeOnly);
 623     irb.resetGuardFailBlock();
 624
 625     // Generate IR for each bytecode instruction in this block.
 626     for (unsigned i = 0; i < block.length(); ++i, sk.advance(block.unit())) {
 627       ProfSrcKey psk { irgs.profTransID, sk };
 628       auto const lastInstr = i == block.length() - 1;
 629       auto const penultimateInst = i == block.length() - 2;
 630
 631       // Update bcOff here so any guards or assertions from metadata are
 632       // attributed to this instruction.
 633       irgen::prepareForNextHHBC(irgs, nullptr, sk, false);
 634
 635       // Update the current funcd, if we have a new one.
 636       if (knownFuncs.hasNext(sk)) {
 637         topFunc = knownFuncs.next();
 638       }
 639       // HHIR may have figured the topFunc even though the RegionDesc
 640       // didn't know it.  When that happens, update topFunc.
 641       if (!topFunc && !irb.fs().fpiStack().empty()) {
 642         auto const& fpiInfo = irb.fs().fpiStack().back();
 643         if (fpiInfo.func) {
 644           topFunc = fpiInfo.func;
 645         }
 646       }
 647
 648       // Create and initialize the instruction.
 649       NormalizedInstruction inst(sk, block.unit());
 650       bool toInterpInst = retry.toInterp.count(psk);
 651       initNormalizedInstruction(inst, irgs, region, blockId,
 652                                 topFunc, lastInstr, toInterpInst);
 653
 654       // If we're at a FCall and the topFunc is still unknown, we may have a
 655       // likely target based on profiling data.
 656       IRInstruction* profiledFuncCheck = nullptr;
 657       double profiledFuncBias{0};
 658       if (topFunc == nullptr && sk.op() == Op::FCall) {
 659         auto const numArgs = inst.imm[0].u_FCA.numArgs;
 660         topFunc = irgen::profiledCalledFunc(irgs, numArgs, profiledFuncCheck,
 661                                             profiledFuncBias);
 662         inst.funcd = topFunc;
 663       }
 664
 665       // Singleton inlining optimization.
 666       if (RuntimeOption::EvalHHIRInlineSingletons && !lastInstr &&
 667           shouldTrySingletonInline(region, inst, i, irgs.transFlags) &&
 668           knownFuncs.hasNext(inst.nextSk())) {
 669
 670         // This is safe to do even if singleton inlining fails; we just won't
 671         // change topFunc in the next pass since hasNext() will return false.
 672         topFunc = knownFuncs.next();
 673
 674         if (tryTranslateSingletonInline(irgs, inst, topFunc)) {
 675           // Skip the translation of this instruction (the FPush) -and- the
 676           // next instruction (the FCall) if singleton inlining succeeds.
 677           // We still want the fallthrough and prediction logic, though.
 678           skipTrans = true;
 679           continue;
 680         }
 681       }
 682
 683       int calleeCost{0};
 684       RegionDescPtr calleeRegion{nullptr};
 685       // See if we have a callee region we can inline---but only if the
 686       // singleton inliner isn't actively inlining.
 687       if (!skipTrans) {
 688         calleeRegion = getInlinableCalleeRegion(psk, inst.funcd, retry, inl,
 689                                                 irgs, budgetBCInstrs,
 690                                                 calleeCost, annotations);
 691       }
 692
 693       if (calleeRegion) {
 694         always_assert(inst.op() == Op::FCall);
 695         auto const* callee = inst.funcd;
 696         auto const numArgs = inst.imm[0].u_FCA.numArgs;
 697
 698         // We shouldn't be inlining profiling translations.
 699         assertx(irgs.context.kind != TransKind::Profile);
 700
 701         assertx(calleeRegion->instrSize() <= budgetBCInstrs);
 702
 703         FTRACE(1, "\nstarting inlined call from {} to {} with {} args "
 704                "and stack:\n{}\n",
 705                block.func()->fullName()->data(),
 706                callee->fullName()->data(),
 707                numArgs,
 708                show(irgs));
 709
 710         auto returnBlock = irb.unit().defBlock(irgen::curProfCount(irgs));
 711         auto suspendRetBlock = irb.unit().defBlock(irgen::curProfCount(irgs));
 712         auto asyncEagerOffset = callee->supportsAsyncEagerReturn()
 713           ? inst.imm[0].u_FCA.asyncEagerOffset : kInvalidOffset;
 714         auto returnTarget = irgen::ReturnTarget {
 715           returnBlock, suspendRetBlock, asyncEagerOffset
 716         };
 717         auto callFuncOff = inst.offset() - block.func()->base();
 718
 719         if (irgen::beginInlining(irgs, numArgs, callee,
 720                                  calleeRegion->start(),
 721                                  callFuncOff,
 722                                  returnTarget,
 723                                  calleeCost,
 724                                  false)) {
 725           SCOPE_ASSERT_DETAIL("Inlined-RegionDesc")
 726             { return show(*calleeRegion); };
 727
 728           // Calculate the profFactor for the callee as the weight of
 729           // the caller block over the weight of the entry block of
 730           // the callee region.
 731           double calleeProfFactor = irgen::curProfCount(irgs);
 732           auto const calleeEntryBID = calleeRegion->entry()->id();
 733           if (hasTransID(calleeEntryBID)) {
 734             assertx(profData());
 735             auto const calleeTID = getTransID(calleeEntryBID);
 736             auto calleeProfCount = calleeRegion->blockProfCount(calleeTID);
 737             if (calleeProfCount == 0) calleeProfCount = 1; // avoid div by zero
 738             calleeProfFactor /= calleeProfCount;
 739             assert_flog(calleeProfFactor >= 0, "calleeProfFactor = {:.5}\n",
 740                         calleeProfFactor);
 741           }
 742
 743           auto result = irGenRegionImpl(irgs, *calleeRegion, retry, inl,
 744                                         budgetBCInstrs, calleeProfFactor,
 745                                         annotations);
 746           assertx(budgetBCInstrs >= 0);
 747
 748           inl.registerEndInlining(callee);
 749
 750           if (result != TranslateResult::Success) {
 751             // If we failed to generate the callee don't fail the caller,
 752             // instead retry without the callee
 753             if (result != TranslateResult::Retry) {
 754               retry.inlineBlacklist.insert(psk);
 755             }
 756             // Generating the inlined call failed, bailout
 757             return TranslateResult::Retry;
 758           }
 759
 760           // Native calls end inlining before CallBuiltin
 761           if (!callee->isCPPBuiltin()) {
 762             // If the inlined region failed to contain any returns then the
 763             // rest of this block is dead- we could continue but there's no
 764             // benefit to inlining this call if it ends in a ReqRetranslate or
 765             // ReqBind* so instead we mark it as uninlinable and retry.
 766             if (!irgen::endInlining(irgs, *calleeRegion)) {
 767               retry.inlineBlacklist.insert(psk);
 768               return TranslateResult::Retry;
 769             }
 770           } else {
 771             // For native calls we don't use a return block
 772             assertx(returnBlock->empty());
 773           }
 774
 775           // Don't emit the FCall
 776           skipTrans = true;
 777         } else {
 778           inl.registerEndInlining(callee);
 779         }
 780       }
 781
 782       // A runtime check was inserted to obtain the identity of the callee.  We
 783       // handle 3 different cases here:
 784       //   1) The call was not inlined, so drop the check.
 785       //   2) The call was inlined and the check is strongly biased towards that
 786       //      callee, so keep the side exit out of the region.
 787       //   3) The call was inlined but it's not strongly biased, so emit a FCall
 788       //      instead of exiting the region when the check fails.
 789       if (profiledFuncCheck != nullptr) {
 790         assertx(sk.op() == Op::FCall);
 791         inst.funcd = topFunc = nullptr;
 792         if (skipTrans) {
 793           if (profiledFuncBias * 100 <
 794               RuntimeOption::EvalJitPGOCalledFuncExitThreshold) {
 795             // Case 2) We inlined the call.  Emit FCall if not strongly biased.
 796             //
 797             // We first emit a jump to the next block.  NB: the FCall must be
 798             // the last instruction in the block.
 799             always_assert_flog(lastInstr,
 800                                "FCall is not the last instruction in block");
 801             irgen::endBlock(irgs, inst.nextSk().offset());
 802
 803             // We then emit the FCall on the check-failure path.
 804             auto const failBlock = profiledFuncCheck->taken();
 805             auto const predBlock = profiledFuncCheck->block();
 806             irb.resetBlock(failBlock, predBlock);
 807             const bool unprocPred = blockHasUnprocessedPred(region, blockId,
 808                                                             processedBlocks);
 809             if (!irb.startBlock(failBlock, unprocPred)) {
 810               always_assert_flog(
 811                   false, "profiledFuncCheck branches to unreachable block"
 812               );
 813             }
 814             skipTrans = false; // so we translate the FCall
 815           }
 816         } else {
 817           // Case 1) We didn't inline the call, so drop the check.
 818           irgen::dropCalledFuncCheck(irgs, profiledFuncCheck);
 819         }
 820       }
 821
 822       if (!skipTrans && penultimateInst && isCmp(inst.op())) {
 823           SrcKey nextSk = inst.nextSk();
 824           Op nextOp = nextSk.op();
 825           auto const backwards = [&]{
 826             auto const offsets = instrJumpOffsets(nextSk.pc());
 827             return std::any_of(
 828               offsets.begin(), offsets.end(), [] (Offset o) { return o < 0; }
 829             );
 830           };
 831           if (needsSurpriseCheck(nextOp) && backwards()) {
 832             emitedSurpriseCheck = true;
 833             inst.forceSurpriseCheck = true;
 834           }
 835       }
 836
 837       // Emit IR for the body of the instruction.
 838       try {
 839         if (!skipTrans) {
 840           const bool firstInstr = isEntry && i == 0;
 841           auto const backwards = [&]{
 842             auto const offsets = instrJumpOffsets(inst.pc());
 843             return std::any_of(
 844               offsets.begin(), offsets.end(), [] (Offset o) { return o < 0; }
 845             );
 846           };
 847           if (lastInstr && !emitedSurpriseCheck &&
 848               needsSurpriseCheck(inst.op()) &&
 849               backwards()) {
 850             emitedSurpriseCheck = true;
 851             inst.forceSurpriseCheck = true;
 852           }
 853           translateInstr(irgs, inst, checkOuterTypeOnly, firstInstr);
 854         }
 855       } catch (const FailedIRGen& exn) {
 856         ProfSrcKey psk2{irgs.profTransID, sk};
 857         always_assert_flog(!retry.toInterp.count(psk2),
 858                            "IR generation failed with {}\n",
 859                            exn.what());
 860         FTRACE(1, "ir generation for {} failed with {}\n",
 861           inst.toString(), exn.what());
 862         retry.toInterp.insert(psk2);
 863         return TranslateResult::Retry;
 864       }
 865
 866       irgen::finishHHBC(irgs);
 867
 868       skipTrans = false;
 869
 870       // If this is the last instruction, handle block transitions.
 871       // If the block ends the region, then call irgen::endRegion to
 872       // sync the state and make a REQ_BIND_JMP service request.
 873       // Otherwise, if the instruction has a fall-through, then insert
 874       // a jump to the next offset, since it may not be the next block
 875       // to be translated.
 876       if (lastInstr) {
 877         if (region.isExit(blockId)) {
 878           if (!inl.inlining() || !isReturnish(inst.op())) {
 879             irgen::endRegion(irgs);
 880           }
 881         } else if (instrAllowsFallThru(inst.op())) {
 882           irgen::endBlock(irgs, inst.nextSk().offset());
 883         }
 884       }
 885     }
 886
 887     processedBlocks.insert(blockId);
 888
 889     assertx(!knownFuncs.hasNext());
 890   }
 891
 892   if (!inl.inlining()) {
 893     irgen::sealUnit(irgs);
 894   }
 895
 896   return TranslateResult::Success;
 897 }
 898
 899 }
 900
 901 //////////////////////////////////////////////////////////////////////
 902
 903 std::unique_ptr<IRUnit> irGenRegion(const RegionDesc& region,
 904                                     const TransContext& context,
 905                                     PostConditions& pConds,
 906                                     Annotations& annotations) noexcept {
 907   Timer irGenTimer(Timer::irGenRegion);
 908   SCOPE_ASSERT_DETAIL("RegionDesc") { return show(region); };
 909
 910   std::unique_ptr<IRUnit> unit;
 911   SCOPE_ASSERT_DETAIL("IRUnit") { return unit ? show(*unit) : "<null>"; };
 912   TranslateRetryContext retry;
 913   auto result = TranslateResult::Retry;
 914
 915   rqtrace::EventGuard trace{"IRGEN"};
 916   uint32_t tries = 0;
 917
 918   while (result == TranslateResult::Retry) {
 919     unit = std::make_unique<IRUnit>(context);
 920     unit->initLogEntry(context.func);
 921     irgen::IRGS irgs{*unit, &region};
 922     tries++;
 923
 924     // Set up inlining context, but disable it for profiling mode.
 925     InliningDecider inl(region.entry()->func());
 926     if (context.kind == TransKind::Profile) inl.disable();
 927
 928     // Set the profCount of the IRUnit's entry block, which is created a
 929     // priori.
 930     if (context.kind == TransKind::Optimize) {
 931       assertx(profData());
 932       auto entryBID = region.entry()->id();
 933       assertx(hasTransID(entryBID));
 934       auto entryTID = getTransID(entryBID);
 935       auto entryProfCount = region.blockProfCount(entryTID);
 936       irgs.unit.entry()->setProfCount(entryProfCount);
 937     }
 938
 939     int32_t budgetBCInstrs = RuntimeOption::EvalJitMaxRegionInstrs;
 940     try {
 941       result = irGenRegionImpl(irgs, region, retry, inl,
 942                                budgetBCInstrs, 1, annotations);
 943     } catch (const FailedTraceGen& e) {
 944       always_assert_flog(false, "irGenRegion failed with {}\n", e.what());
 945     }
 946     assertx(budgetBCInstrs >= 0);
 947     FTRACE(1, "translateRegion: final budgetBCInstrs = {}\n", budgetBCInstrs);
 948
 949     if (result == TranslateResult::Success) {
 950       // For profiling translations, grab the postconditions to be used for
 951       // region selection whenever we decide to retranslate.
 952       assertx(pConds.changed.empty() && pConds.refined.empty());
 953       if (context.kind == TransKind::Profile &&
 954           RuntimeOption::EvalJitPGOUsePostConditions) {
 955         auto const lastSrcKey = region.lastSrcKey();
 956         if (auto const mainExit = findMainExitBlock(irgs.unit, lastSrcKey)) {
 957           FTRACE(2, "translateRegion: mainExit: B{}\nUnit: {}\n",
 958                  mainExit->id(), show(irgs.unit));
 959           pConds = irgs.irb->fs().postConds(mainExit);
 960         } else {
 961           FTRACE(2, "translateRegion: no main exit\n");
 962         }
 963       }
 964     } else {
 965       // Clear annotations from the failed attempt.
 966       annotations.clear();
 967     }
 968   }
 969
 970   trace.annotate("tries", folly::to<std::string>(tries));
 971   trace.finish();
 972   irGenTimer.stop();
 973   if (result != TranslateResult::Success) return nullptr;
 974
 975   auto finishPass = [&](const char* msg, int level) {
 976     printUnit(level, *unit, msg, nullptr, nullptr, &annotations);
 977     assertx(checkCfg(*unit));
 978   };
 979
 980   finishPass(" after initial translation ", kIRLevel);
 981   optimize(*unit, context.kind);
 982   finishPass(" after optimizing ", kOptLevel);
 983
 984   return unit;
 985 }
 986
 987 std::unique_ptr<IRUnit> irGenInlineRegion(const TransContext& ctx,
 988                                           const RegionDesc& region,
 989                                           Annotations& annotations) {
 990   SCOPE_ASSERT_DETAIL("Inline-RegionDesc") { return show(region); };
 991
 992   std::unique_ptr<IRUnit> unit;
 993   TranslateRetryContext retry;
 994   auto result = TranslateResult::Retry;
 995   auto caller = ctx.srcKey().func();
 996   auto const entryBID = region.entry()->id();
 997
 998   while (result == TranslateResult::Retry) {
 999     unit = std::make_unique<IRUnit>(ctx);
1000     irgen::IRGS irgs{*unit, &region};
1001     if (hasTransID(entryBID)) irgs.profTransID = getTransID(entryBID);
1002
1003     auto& irb = *irgs.irb;
1004     InliningDecider inl{caller};
1005     auto const& argTypes = region.inlineInputTypes();
1006     auto const ctxType = region.inlineCtxType();
1007
1008     auto const func = region.entry()->func();
1009     inl.initWithCallee(func);
1010     inl.disable();
1011
1012     auto const entry = irb.unit().entry();
1013     auto returnBlock = irb.unit().defBlock();
1014     auto suspendRetBlock = irb.unit().defBlock();
1015     auto returnTarget = irgen::ReturnTarget {
1016       returnBlock, suspendRetBlock, kInvalidOffset
1017     };
1018
1019     // Set the profCount of the entry and return blocks we just created.
1020     entry->setProfCount(curProfCount(irgs));
1021     returnBlock->setProfCount(curProfCount(irgs));
1022
1023     SCOPE_ASSERT_DETAIL("Inline-IRUnit") { return show(*unit); };
1024     irb.startBlock(entry, false /* hasUnprocPred */);
1025     if (!irgen::conjureBeginInlining(irgs, func, region.start(),
1026                                      ctxType, argTypes, returnTarget)) {
1027       return nullptr;
1028     }
1029
1030     int32_t budgetBcInstrs = RuntimeOption::EvalJitMaxRegionInstrs;
1031     try {
1032       result = irGenRegionImpl(
1033         irgs,
1034         region,
1035         retry,
1036         inl,
1037         budgetBcInstrs,
1038         1 /* profFactor */,
1039         annotations
1040       );
1041     } catch (const FailedTraceGen& e) {
1042       FTRACE(2, "irGenInlineRegion failed with {}\n", e.what());
1043       always_assert_flog(false, "irGenInlineRegion failed with {}\n", e.what());
1044     }
1045
1046     if (result == TranslateResult::Success) {
1047       if (!irgen::conjureEndInlining(irgs, region, func->isCPPBuiltin())) {
1048         return nullptr;
1049       }
1050       irgen::sealUnit(irgs);
1051       optimize(*unit, TransKind::Optimize);
1052     }
1053   }
1054
1055   if (result != TranslateResult::Success) return nullptr;
1056   return unit;
1057 }
1058
1059 }}