hphp/runtime/vm/jit/region-tracelet.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/region-selection.h"
  18
  19 #include "hphp/runtime/vm/jit/inlining-decider.h"
  20 #include "hphp/runtime/vm/jit/irgen-bespoke.h"
  21 #include "hphp/runtime/vm/jit/irgen-exit.h"
  22 #include "hphp/runtime/vm/jit/location.h"
  23 #include "hphp/runtime/vm/jit/normalized-instruction.h"
  24 #include "hphp/runtime/vm/jit/print.h"
  25 #include "hphp/runtime/vm/jit/punt.h"
  26 #include "hphp/runtime/vm/jit/timer.h"
  27 #include "hphp/runtime/vm/jit/translator.h"
  28 #include "hphp/runtime/vm/jit/analysis.h"
  29
  30 #include "hphp/util/configs/jit.h"
  31 #include "hphp/util/trace.h"
  32
  33 #include <folly/MapUtil.h>
  34
  35 #include <algorithm>
  36 #include <vector>
  37
  38 #include "hphp/runtime/vm/jit/irgen.h"
  39
  40 // TODO(#5710324): it seems a little odd that region-tracelet is not part of
  41 // irgen:: but needs access to this.  Probably we don't have the right
  42 // abstraction boundaries.  We'll resolve this somehow later.
  43 #include "hphp/runtime/vm/jit/irgen-internal.h"
  44
  45 namespace HPHP { namespace jit {
  46
  47 TRACE_SET_MOD(region);
  48
  49 using InterpSet = hphp_hash_set<SrcKey, SrcKey::Hasher>;
  50
  51 namespace {
  52
  53 ///////////////////////////////////////////////////////////////////////////////
  54
  55 constexpr int MaxJmpsTracedThrough = 5;
  56
  57 struct Env {
  58   Env(const RegionContext& ctx,
  59       TransKind kind,
  60       InterpSet& interp,
  61       int32_t maxBCInstrs,
  62       bool inlining)
  63     : ctx(ctx)
  64     , interp(interp)
  65     , sk{ctx.sk}
  66     , region(std::make_shared<RegionDesc>())
  67     , curBlock(region->addBlock(sk, 0, ctx.spOffset))
  68     , prevBlocks()
  69     // TODO(#5703534): this is using a different TransContext than actual
  70     // translation will use.
  71     , unit(TransContext{
  72               TransIDSet{}
  73             , 0 /* optIndex */
  74             , kind
  75             , sk
  76             , nullptr
  77             , sk.packageInfo()}
  78           , std::make_unique<AnnotationData>())
  79     , irgs(unit, nullptr, 0, nullptr)
  80     , numJmps(0)
  81     , numBCInstrs(maxBCInstrs)
  82     , profiling(kind == TransKind::Profile)
  83     , inlining(inlining)
  84   {
  85     irgen::defineFrameAndStack(irgs, ctx.spOffset);
  86     irgs.formingRegion = true;
  87     irgs.irb->enableConstrainGuards();
  88   }
  89
  90   const RegionContext& ctx;
  91   InterpSet& interp;
  92   SrcKey sk;
  93   NormalizedInstruction inst;
  94   RegionDescPtr region;
  95   RegionDesc::Block* curBlock;
  96   jit::hash_map<Offset, jit::vector<RegionDesc::Block*>> prevBlocks;
  97   IRUnit unit;
  98   irgen::IRGS irgs;
  99   uint32_t numJmps;
 100   int32_t numBCInstrs;
 101   // This map memoizes reachability of IR blocks during tracelet
 102   // formation.  A block won't have it's reachability stored in this
 103   // map until it's been computed.
 104   jit::hash_map<unsigned,bool> irReachableBlocks;
 105
 106   const bool profiling;
 107   const bool inlining;
 108
 109  private:
 110   Env(const Env&) = delete;
 111   Env& operator=(const Env&) = delete;
 112 };
 113
 114 const Func* curFunc(const Env& env) {
 115   return irgen::curFunc(env.irgs);
 116 }
 117
 118 const Unit* curUnit(const Env& env) {
 119   return irgen::curUnit(env.irgs);
 120 }
 121
 122 SBInvOffset curSpOffset(const Env& env) {
 123   return env.irgs.irb->fs().bcSPOff();
 124 }
 125
 126 /*
 127  * Check if the input has a known datatype or whether we need
 128  * to insert a guard.
 129  */
 130 bool needGuardForInput(Env& env, const InputInfo& input) {
 131   if (input.dontGuard) return false;
 132   auto const type = irgen::provenType(env.irgs, input.loc);
 133
 134   if (type.isKnownDataType()) return false;
 135
 136   FTRACE(1, "selectTracelet: {} input {}, needs a guard due to unknown type {}\n",
 137          env.inst.toString(), show(input.loc), type.toString());
 138   return true;
 139 }
 140
 141 /*
 142  * Add the current instruction to the region.
 143  */
 144 void addInstruction(Env& env) {
 145   if (!env.sk.funcEntry()) {
 146     auto prevBlocksIt = env.prevBlocks.find(env.sk.offset());
 147     if (prevBlocksIt != env.prevBlocks.end()) {
 148       FTRACE(2, "selectTracelet adding new block at {} after:\n{}\n",
 149              showShort(env.sk), show(*env.curBlock));
 150       always_assert(env.sk.func() == curFunc(env));
 151       env.curBlock = env.region->addBlock(env.sk, 0, curSpOffset(env));
 152       for (auto block : prevBlocksIt->second) {
 153         env.region->addArc(block->id(), env.curBlock->id());
 154       }
 155     }
 156   }
 157
 158   FTRACE(2, "selectTracelet adding instruction {}\n", env.inst.toString());
 159   env.curBlock->addInstruction();
 160   env.numBCInstrs--;
 161 }
 162
 163 bool instructionEndsRegion(const Env& env) {
 164   auto const& inst = env.inst;
 165   if (opcodeBreaksBB(inst.op(), env.inlining)) return true;
 166   if (env.profiling && instrBreaksProfileBB(inst)) return true;
 167   if (dontGuardAnyInputs(inst) && opcodeChangesPC(inst.op())) return true;
 168   return false;
 169 }
 170
 171 Type getLiveType(const jit::vector<RegionContext::LiveType>& liveTypes,
 172                  const Location& loc) {
 173   for (auto const& lt : liveTypes) {
 174     if (lt.location == loc) return lt.type;
 175   }
 176   return TCell;
 177 }
 178
 179 /*
 180  * Populate most fields of the NormalizedInstruction, assuming its sk
 181  * has already been set. Returns false iff the region should be
 182  * truncated before inst's SrcKey.
 183  */
 184 bool prepareInstruction(Env& env) {
 185   env.inst.~NormalizedInstruction();
 186   new (&env.inst) NormalizedInstruction(env.sk, curUnit(env));
 187   irgen::prepareForNextHHBC(env.irgs, env.sk);
 188
 189   if (env.sk.funcEntry()) {
 190     addInstruction(env);
 191     return true;
 192   }
 193
 194   auto inputInfos = getInputs(env.inst, env.irgs.irb->fs().bcSPOff());
 195   for (auto const loc : irgen::guardsForBespoke(env.irgs, env.sk)) {
 196     FTRACE(1, "prepareInstruction: adding bespoke guard: {}\n", show(loc));
 197     inputInfos.emplace_back(loc);
 198   }
 199
 200   auto const op = env.inst.op();
 201   auto& fs = env.irgs.irb->fs();
 202
 203   Block* guardFailBlock = nullptr;
 204   auto addGuardIfUntracked = [&](Location loc) {
 205     FTRACE(1, "prepareInstruction: input: {}\n", show(loc));
 206     if (!fs.tracked(loc) &&
 207         (loc.tag() != LTag::Local || !fs.localsCleared())) {
 208       auto const type = getLiveType(env.ctx.liveTypes, loc);
 209       assert_flog(type <= TCell, "loc = {}: type = {}", show(loc), type);
 210       if (guardFailBlock == nullptr) guardFailBlock = irgen::makeExit(env.irgs);
 211       irgen::checkType(env.irgs, loc, type, guardFailBlock);
 212     }
 213   };
 214
 215   // Guard any input that hasn't been guarded yet.
 216   for (auto const& input : inputInfos) {
 217     addGuardIfUntracked(input.loc);
 218   }
 219
 220   // Guard any output local that hasn't been guarded yet -- they'll be read to
 221   // be decref'd.
 222   auto const outputLocals = getLocalOutputs(env.inst);
 223   for (auto locId : outputLocals) {
 224     addGuardIfUntracked(Location::Local{locId});
 225   }
 226
 227   // AssertRAT* instructions are special: they refine the type of a location
 228   // without taking it as an input.  The location will start to be tracked by
 229   // FrameState after these instructions, so we need to first guard them since
 230   // the guards may provide additional type information.
 231   if (op == OpAssertRATL) {
 232     auto loc = Location::Local{safe_cast<uint32_t>(env.inst.imm[0].u_ILA)};
 233     addGuardIfUntracked(loc);
 234   }
 235   if (op == OpAssertRATStk) {
 236     auto const bcSPOff = env.irgs.irb->fs().bcSPOff();
 237     auto const sbInvOff =
 238       BCSPRelOffset{safe_cast<int32_t>(env.inst.imm[0].u_IVA)}.
 239         to<SBInvOffset>(bcSPOff);
 240     addGuardIfUntracked(Location::Stack{sbInvOff});
 241   }
 242
 243   for (auto const& input : inputInfos) {
 244     if (needGuardForInput(env, input)) {
 245       FTRACE(2, "Stopping tracelet consuming {} input {}\n",
 246              opcodeToName(env.inst.op()), show(input.loc));
 247       return false;
 248     }
 249   }
 250
 251   addInstruction(env);
 252
 253   if (isFCall(op)) {
 254     auto const asyncEagerOffset = env.inst.imm[0].u_FCA.asyncEagerOffset;
 255     if (asyncEagerOffset != kInvalidOffset) {
 256       // Note that the arc between the block containing asyncEagerOffset and
 257       // the previous block is not added to the region on purpose, as it comes
 258       // from the slow path (await of a finished Awaitable after failed async
 259       // eager return, which usually produces unfinished Awaitable) with
 260       // possibly unknown type pessimizing next execution.
 261       auto const sk = env.sk;
 262       env.prevBlocks[sk.advanced().offset()].push_back(env.curBlock);
 263       env.prevBlocks[sk.offset() + asyncEagerOffset].push_back(env.curBlock);
 264     }
 265   }
 266
 267   return true;
 268 }
 269
 270 bool traceThroughJmp(Env& env) {
 271   // Func entry is not a jmp.
 272   if (env.sk.funcEntry()) return false;
 273
 274   // We only trace through unconditional jumps and conditional jumps with const
 275   // inputs while inlining.
 276   if (!(isUnconditionalJmp(env.inst.op()) || isInterceptableJmp(env.inst.op())) &&
 277       !(env.inlining && isConditionalJmp(env.inst.op()) &&
 278         irgen::publicTopType(env.irgs, BCSPRelOffset{0}).hasConstVal())) {
 279     return false;
 280   }
 281
 282   // We want to keep profiling translations to basic blocks, inlining shouldn't
 283   // happen in profiling translations
 284   if (env.profiling) {
 285     assertx(!env.inlining);
 286     return false;
 287   }
 288
 289   // Don't trace through too many jumps, unless we're inlining. We want to make
 290   // sure we don't break a tracelet in the middle of an inlined call; if the
 291   // inlined callee becomes too big that's caught in shouldIRInline.
 292   if (env.numJmps == MaxJmpsTracedThrough && !env.inlining) {
 293     return false;
 294   }
 295
 296   auto offset = env.inst.imm[0].u_BA;
 297   // Only trace through backwards jumps if it's an Enter and we're
 298   // inlining. This is to get DV funclets.
 299   if (offset <= 0 && (env.inst.op() != OpEnter || !env.inlining)) {
 300     return false;
 301   }
 302
 303   // Ok we're good. For unconditional jumps, just set env.sk to the dest. For
 304   // known conditional jumps we have to consume the const value on the top of
 305   // the stack and figure out which branch to go to.
 306   if (isUnconditionalJmp(env.inst.op()) || isInterceptableJmp(env.inst.op())) {
 307     env.sk.setOffset(env.sk.offset() + offset);
 308   } else {
 309     auto value = irgen::popC(env.irgs);
 310     auto taken =
 311       value->variantVal().toBoolean() == (env.inst.op() == OpJmpNZ);
 312     FTRACE(2, "Tracing through {}taken Jmp(N)Z on constant {}\n",
 313            taken ? "" : "not ", *value->inst());
 314
 315     env.sk.setOffset(taken ? env.sk.offset() + offset
 316                            : env.sk.advanced().offset());
 317   }
 318
 319   env.numJmps++;
 320   env.prevBlocks[env.sk.offset()].push_back(env.curBlock);
 321   return true;
 322 }
 323
 324 bool isLiteral(Op op) {
 325   switch (op) {
 326     case OpNull:
 327     case OpNullUninit:
 328     case OpTrue:
 329     case OpFalse:
 330     case OpInt:
 331     case OpDouble:
 332     case OpString:
 333     case OpDict:
 334     case OpVec:
 335     case OpKeyset:
 336       return true;
 337
 338     default:
 339       return false;
 340   }
 341 }
 342
 343 bool isThisSelfOrParent(Op op) {
 344   switch (op) {
 345     case OpThis:
 346     case OpSelfCls:
 347     case OpParentCls:
 348       return true;
 349
 350     default:
 351       return false;
 352   }
 353 }
 354
 355 /*
 356  * For every instruction in trace representing a tracelet guard, call func with
 357  * its location and type.
 358  */
 359 template<typename F>
 360 void visitGuards(IRUnit& unit, F func) {
 361   auto blocks = rpoSortCfg(unit);
 362
 363   for (auto const block : blocks) {
 364     for (auto const& inst : *block) {
 365       switch (inst.op()) {
 366         case EndGuards:
 367           return;
 368         case CheckLoc:
 369           func(&inst,
 370                Location::Local{inst.extra<LocalId>()->locId},
 371                inst.typeParam());
 372           break;
 373         case CheckStk: {
 374           auto const irSPRel = inst.extra<IRSPRelOffsetData>()->offset;
 375
 376           auto const defSP = inst.src(0)->inst();
 377           assertx(defSP->is(DefFrameRelSP, DefRegSP));
 378           auto const irSPOff = defSP->extra<DefStackData>()->irSPOff;
 379
 380           func(&inst,
 381                Location::Stack{irSPRel.to<SBInvOffset>(irSPOff)},
 382                inst.typeParam());
 383           break;
 384         }
 385         case CheckMBase:
 386           func(&inst, Location::MBase{}, inst.typeParam());
 387           break;
 388         default: break;
 389       }
 390     }
 391   }
 392 }
 393
 394 /*
 395  * Records any type predictions we depend on in the region.
 396  */
 397 void recordDependencies(Env& env) {
 398   // Relax guards and record the ones that survived.
 399   auto& firstBlock = *env.region->blocks().front();
 400   auto& unit = env.irgs.unit;
 401   auto guardMap = std::map<Location,Type>{};
 402   ITRACE(2, "Visiting guards\n");
 403   auto catMap = std::map<Location,DataTypeCategory>{};
 404   const auto& guards = env.irgs.irb->guards()->guards;
 405   visitGuards(unit, [&] (const IRInstruction* guard,
 406                          const Location& loc,
 407                          Type type) {
 408     Trace::Indent indent;
 409     assertx(type <= TCell);
 410     auto const gc = folly::get_default(guards, guard);
 411     auto gcToRelax = gc;
 412     if (DataTypeGeneric < gc.category && gc.category < DataTypeSpecific) {
 413       gcToRelax = DataTypeSpecific;
 414     }
 415     auto const relaxedType = relaxToConstraint(type, gcToRelax);
 416     ITRACE(3, "{}: {} -> {} {}\n",
 417            show(loc), type, relaxedType, gcToRelax.toString());
 418
 419     auto inret = guardMap.insert(std::make_pair(loc, relaxedType));
 420     if (inret.second) {
 421       catMap[loc] = gc.category;
 422       return;
 423     }
 424     inret.first->second &= relaxedType;
 425     auto& oldCat = catMap[loc];
 426     oldCat = std::max(oldCat, gc.category);
 427   });
 428
 429   for (auto& kv : guardMap) {
 430     if (kv.second == TCell) {
 431       // Guard was relaxed to Cell---don't record it.
 432       continue;
 433     }
 434     auto const preCond = RegionDesc::GuardedLocation {
 435       kv.first, kv.second,
 436       catMap[kv.first]
 437     };
 438     ITRACE(1, "selectTracelet adding guard {}\n", show(preCond));
 439     firstBlock.addPreCondition(preCond);
 440   }
 441 }
 442
 443 void truncateLiterals(Env& env) {
 444   if (!env.region || env.region->empty() ||
 445       env.region->blocks().back()->empty()) return;
 446
 447   // Don't finish a region with literal values or values that have a class
 448   // related to the current context class. They produce valuable information
 449   // for optimizations that's lost across region boundaries.
 450   auto& lastBlock = *env.region->blocks().back();
 451   auto sk = lastBlock.start();
 452   auto endSk = sk;
 453   auto func = lastBlock.func();
 454   for (int i = 0, len = lastBlock.length(); i < len; ++i, sk.advance(func)) {
 455     if (!sk.funcEntry()) {
 456       auto const op = sk.op();
 457       if (isLiteral(op) || isThisSelfOrParent(op) || isTypeAssert(op)) continue;
 458     }
 459
 460     if (i == len - 1) return;
 461     endSk = sk;
 462   }
 463
 464   // Don't truncate if we've decided we want to truncate the entire block.
 465   // That'll mean we'll chop off the trailing N-1 opcodes, then in the next
 466   // region we'll select N-1 opcodes and chop off N-2 opcodes, and so forth...
 467   if (endSk != lastBlock.start()) {
 468     FTRACE(1, "selectTracelet truncating block after offset {}:\n{}\n",
 469            endSk.offset(), show(lastBlock));
 470     lastBlock.truncateAfter(endSk);
 471   }
 472 }
 473
 474 RegionDescPtr form_region(Env& env) {
 475   SCOPE_ASSERT_DETAIL("Tracelet Selector") {
 476     return folly::sformat("Region:\n{}\n\nUnit:\n{}\n",
 477                           *env.region, show(env.irgs.irb->unit()));
 478   };
 479
 480   auto const eager =
 481     env.ctx.liveTypes.size() <= Cfg::Jit::TraceletEagerGuardsLimit;
 482
 483   Block* guardFailBlock = nullptr;
 484   for (auto const& lt : env.ctx.liveTypes) {
 485     // Local and stack slots are lazily guarded when there are too many live
 486     // locations; but MBase is always eagerly guarded.
 487     if (eager || lt.location.tag() == LTag::MBase) {
 488       auto t = lt.type;
 489       assertx(t <= TCell);
 490       if (guardFailBlock == nullptr) guardFailBlock = irgen::makeExit(env.irgs);
 491       irgen::checkType(env.irgs, lt.location, t, guardFailBlock);
 492     }
 493   }
 494
 495   // EndGuards is used to mark the end of the guards, allowing visitGuards to
 496   // avoid scanning through the entire unit.  We only insert EndGuards if all
 497   // guards were eagerly inserted because, with lazy guarding, the guards will
 498   // be emitted later.
 499   if (eager) irgen::gen(env.irgs, EndGuards);
 500
 501   for (bool firstInst = true; true; firstInst = false) {
 502     assertx(env.numBCInstrs >= 0);
 503     if (env.numBCInstrs == 0) {
 504       FTRACE(1, "selectTracelet: breaking region due to size limit\n");
 505       break;
 506     }
 507
 508     // Break translation if there's already a translation starting at the
 509     // current SrcKey.
 510     if (!firstInst) {
 511       auto const sr = tc::findSrcRec(env.sk);
 512       if (sr != nullptr && sr->getTopTranslation() != nullptr) {
 513         FTRACE(1, "selectTracelet: breaking region at TC entry: {}\n",
 514                show(env.sk));
 515         break;
 516       }
 517     }
 518
 519     if (!prepareInstruction(env)) break;
 520     if (traceThroughJmp(env)) continue;
 521     env.inst.interp = env.interp.count(env.sk);
 522
 523     try {
 524       translateInstr(env.irgs, env.inst);
 525     } catch (const FailedIRGen& exn) {
 526       FTRACE(1, "ir generation for {} failed with {}\n",
 527              env.inst.toString(), exn.what());
 528       always_assert_flog(
 529         !env.interp.count(env.sk),
 530         "Double PUNT trying to translate {}\n", env.inst
 531       );
 532       env.interp.insert(env.sk);
 533       env.region.reset();
 534       break;
 535     }
 536
 537     irgen::finishHHBC(env.irgs);
 538
 539     if (!env.sk.funcEntry() && !instrAllowsFallThru(env.inst.op())) {
 540       FTRACE(1, "selectTracelet: tracelet broken after instruction with no "
 541              "fall-through {}\n", env.inst);
 542       break;
 543     }
 544
 545     // We successfully translated the instruction, so update env.sk.
 546     assertx(env.sk.func() == curFunc(env));
 547     env.sk.advance(env.curBlock->func());
 548
 549     if (env.inst.source.funcEntry()) {
 550       auto const func = curFunc(env);
 551       if (env.inst.source.trivialDVFuncEntry() ||
 552           func->hasNonTrivialDVFuncEntry()) {
 553         FTRACE(1, "selectTracelet: tracelet broken after func entry\n");
 554         break;
 555       }
 556       continue;
 557     }
 558
 559     if (instructionEndsRegion(env)) {
 560       FTRACE(1, "selectTracelet: tracelet broken after {}\n", env.inst);
 561       break;
 562     } else if (isIteratorOp(env.sk.op())) {
 563       FTRACE(1, "selectTracelet: tracelet broken before iterator op\n");
 564       break;
 565     }
 566
 567     if (env.irgs.irb->inUnreachableState()) {
 568       FTRACE(1, "selectTracelet: tracelet ending at unreachable state\n");
 569       break;
 570     }
 571
 572     const auto numGuards = env.irgs.irb->numGuards();
 573     if (numGuards >= Cfg::Jit::TraceletGuardsLimit) {
 574       FTRACE(1, "selectTracelet: tracelet broken due to too many guards ({})\n",
 575              numGuards);
 576       break;
 577     }
 578   }
 579
 580   if (env.region && !env.region->empty()) {
 581     // Make sure we end the region before trying to print the IRUnit.
 582     irgen::endRegion(env.irgs, env.sk);
 583
 584     printUnit(
 585       kTraceletLevel, env.irgs.irb->unit(),
 586       env.inlining ? " after inlining tracelet formation "
 587                    : " after tracelet formation ",
 588       nullptr,
 589       env.irgs.irb->guards()
 590     );
 591
 592     recordDependencies(env);
 593
 594     auto const truncate = [&] () -> bool {
 595       // Make sure that the IR unit contains a main exit corresponding
 596       // to the last bytecode instruction in the region.  Note that this
 597       // check has to happen before the call to truncateLiterals()
 598       // because that updates the region but not the IR unit.
 599       if (env.region->blocks().back()->empty()) return true;
 600       auto lastSk = env.region->lastSrcKey();
 601       auto const mainExits = findMainExitBlocks(env.irgs.irb->unit(), lastSk);
 602       /*
 603        * If the last instruction is an Unreachable, its probably due to
 604        * unreachable code. We don't want to truncate the tracelet in that case,
 605        * because we could lose the assertion (eg if the Unreachable is due to a
 606        * failed AssertRAT).
 607        */
 608       for (auto& me : mainExits) {
 609         if (me->back().is(Unreachable)) return false;
 610       }
 611       return true;
 612     }();
 613
 614     if (truncate) {
 615       truncateLiterals(env);
 616     }
 617   }
 618
 619   return std::move(env.region);
 620 }
 621
 622 ///////////////////////////////////////////////////////////////////////////////
 623 }
 624
 625 RegionDescPtr selectTracelet(const RegionContext& ctx, TransKind kind,
 626                              int32_t maxBCInstrs, bool inlining /* = false */) {
 627   Timer _t(Timer::selectTracelet, nullptr);
 628   InterpSet interp;
 629   RegionDescPtr region;
 630   uint32_t tries = 0;
 631
 632   FTRACE(1, "selectTracelet: starting with maxBCInstrs = {}\n", maxBCInstrs);
 633
 634   tracing::Block _{
 635     "select-tracelet",
 636     [&] {
 637       return tracing::Props{}
 638         .add("sk", show(ctx.sk))
 639         .add("trans_kind", show(kind))
 640         .add("inlining", inlining)
 641         .add("max_bc_instrs", maxBCInstrs);
 642     }
 643   };
 644
 645   if (ctx.liveTypes.size() > Cfg::Jit::TraceletLiveLocsLimit) {
 646     return nullptr;
 647   }
 648
 649   do {
 650     Env env{ctx, kind, interp, maxBCInstrs, inlining};
 651     region = form_region(env);
 652     ++tries;
 653   } while (!region);
 654
 655   if (region->empty() || region->blocks().front()->length() == 0) {
 656     tracing::addPoint("select-tracelet-giving-up");
 657     FTRACE(1, "selectTracelet giving up after {} tries\n", tries);
 658     return nullptr;
 659   }
 660
 661   if (region->blocks().back()->length() == 0) {
 662     // If the final block is empty because it would've only contained
 663     // instructions producing literal values, kill it.
 664     region->deleteBlock(region->blocks().back()->id());
 665   }
 666
 667   tracing::annotateBlock(
 668     [&] {
 669       return tracing::Props{}
 670         .add("region_size", region->instrSize())
 671         .add("tries", tries);
 672     }
 673   );
 674
 675   FTRACE(1, "selectTracelet returning, {}, {} tries:\n{}\n",
 676          inlining ? "inlining" : "not inlining", tries, show(*region));
 677   return region;
 678 }
 679
 680 } }