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

   1 /*
   2    +----------------------------------------------------------------------+
   3    | HipHop for PHP                                                       |
   4    +----------------------------------------------------------------------+
   5    | Copyright (c) 2010-2014 Facebook, Inc. (http://www.facebook.com)     |
   6    +----------------------------------------------------------------------+
   7    | This source file is subject to version 3.01 of the PHP license,      |
   8    | that is bundled with this package in the file LICENSE, and is        |
   9    | available through the world-wide-web at the following url:           |
  10    | http://www.php.net/license/3_01.txt                                  |
  11    | If you did not receive a copy of the PHP license and are unable to   |
  12    | obtain it through the world-wide-web, please send a note to          |
  13    | license@php.net so we can mail you a copy immediately.               |
  14    +----------------------------------------------------------------------+
  15 */
  16
  17 #include "hphp/util/trace.h"
  18 #include <algorithm>
  19 #include <vector>
  20 #include "hphp/runtime/vm/jit/annotation.h"
  21 #include "hphp/runtime/vm/jit/guard-relaxation.h"
  22 #include "hphp/runtime/vm/jit/hhbc-translator.h"
  23 #include "hphp/runtime/vm/jit/ir-translator.h"
  24 #include "hphp/runtime/vm/jit/normalized-instruction.h"
  25 #include "hphp/runtime/vm/jit/print.h"
  26 #include "hphp/runtime/vm/jit/region-selection.h"
  27 #include "hphp/runtime/vm/jit/timer.h"
  28 #include "hphp/runtime/vm/jit/tracelet.h"
  29 #include "hphp/runtime/vm/jit/translator.h"
  30
  31 namespace HPHP { namespace JIT {
  32
  33
  34 TRACE_SET_MOD(region);
  35
  36 typedef hphp_hash_set<SrcKey, SrcKey::Hasher> InterpSet;
  37
  38 namespace {
  39 struct RegionDescIter : public RegionIter {
  40   explicit RegionDescIter(const RegionDesc& region)
  41     : m_blocks(region.blocks)
  42     , m_blockIter(region.blocks.begin())
  43     , m_sk(m_blockIter == m_blocks.end() ? SrcKey() : (*m_blockIter)->start())
  44   {}
  45
  46   bool finished() const { return m_blockIter == m_blocks.end(); }
  47
  48   SrcKey sk() const {
  49     assert(!finished());
  50     return m_sk;
  51   }
  52
  53   void advance() {
  54     assert(!finished());
  55     assert(m_sk.func() == (*m_blockIter)->func());
  56
  57     if (m_sk == (*m_blockIter)->last()) {
  58       ++m_blockIter;
  59       if (!finished()) m_sk = (*m_blockIter)->start();
  60     } else {
  61       m_sk.advance();
  62     }
  63   }
  64
  65  private:
  66   const std::vector<RegionDesc::BlockPtr>& m_blocks;
  67   std::vector<RegionDesc::BlockPtr>::const_iterator m_blockIter;
  68   SrcKey m_sk;
  69 };
  70
  71 struct RegionFormer {
  72   RegionFormer(const RegionContext& ctx, InterpSet& interp, int inlineDepth,
  73                bool profiling);
  74
  75   RegionDescPtr go();
  76
  77 private:
  78   const RegionContext& m_ctx;
  79   InterpSet& m_interp;
  80   SrcKey m_sk;
  81   const SrcKey m_startSk;
  82   NormalizedInstruction m_inst;
  83   RegionDescPtr m_region;
  84   RegionDesc::Block* m_curBlock;
  85   bool m_blockFinished;
  86   IRTranslator m_irTrans;
  87   HhbcTranslator& m_ht;
  88   smart::vector<ActRecState> m_arStates;
  89   RefDeps m_refDeps;
  90   const int m_inlineDepth;
  91   const bool m_profiling;
  92
  93   const Func* curFunc() const;
  94   const Unit* curUnit() const;
  95   Offset curSpOffset() const;
  96   bool resumed() const;
  97   int inliningDepth() const;
  98
  99   bool prepareInstruction();
 100   void addInstruction();
 101   bool consumeInput(int i, const InputInfo& ii);
 102   bool tryInline();
 103   void recordDependencies();
 104   void truncateLiterals();
 105 };
 106
 107 RegionFormer::RegionFormer(const RegionContext& ctx, InterpSet& interp,
 108                            int inlineDepth, bool profiling)
 109   : m_ctx(ctx)
 110   , m_interp(interp)
 111   , m_sk(ctx.func, ctx.bcOffset, ctx.resumed)
 112   , m_startSk(m_sk)
 113   , m_region(std::make_shared<RegionDesc>())
 114   , m_curBlock(m_region->addBlock(ctx.func, m_sk.resumed(), m_sk.offset(), 0,
 115                                   ctx.spOffset))
 116   , m_blockFinished(false)
 117   , m_irTrans(ctx.bcOffset, ctx.spOffset, ctx.resumed, ctx.func)
 118   , m_ht(m_irTrans.hhbcTrans())
 119   , m_arStates(1)
 120   , m_inlineDepth(inlineDepth)
 121   , m_profiling(profiling)
 122 {
 123 }
 124
 125 const Func* RegionFormer::curFunc() const {
 126   return m_ht.curFunc();
 127 }
 128
 129 const Unit* RegionFormer::curUnit() const {
 130   return m_ht.curUnit();
 131 }
 132
 133 Offset RegionFormer::curSpOffset() const {
 134   return m_ht.spOffset();
 135 }
 136
 137 bool RegionFormer::resumed() const {
 138   return m_ht.resumed();
 139 }
 140
 141 int RegionFormer::inliningDepth() const {
 142   return m_inlineDepth + m_ht.inliningDepth();
 143 }
 144
 145 RegionDescPtr RegionFormer::go() {
 146   uint32_t numJmps = 0;
 147
 148   for (auto const& lt : m_ctx.liveTypes) {
 149     auto t = lt.type;
 150     if (t <= Type::Cls) {
 151       m_ht.assertTypeStack(lt.location.stackOffset(), t);
 152       m_curBlock->addPredicted(m_sk, RegionDesc::TypePred{lt.location, t});
 153     } else {
 154       m_ht.guardTypeLocation(lt.location, t, true /* outerOnly */);
 155     }
 156   }
 157
 158   while (true) {
 159     if (!prepareInstruction()) break;
 160
 161     // Instead of translating a Jmp, go to its destination.
 162     if (!m_profiling && isUnconditionalJmp(m_inst.op()) &&
 163         m_inst.imm[0].u_BA > 0 && numJmps < Translator::MaxJmpsTracedThrough) {
 164       // Include the Jmp in the region and continue to its destination.
 165       ++numJmps;
 166       m_sk.setOffset(m_sk.offset() + m_inst.imm[0].u_BA);
 167       m_blockFinished = true;
 168
 169       continue;
 170     }
 171
 172     m_curBlock->setKnownFunc(m_sk, m_inst.funcd);
 173
 174     m_inst.interp = m_interp.count(m_sk);
 175     auto const doPrediction =
 176       m_profiling ? false : outputIsPredicted(m_inst);
 177
 178     if (tryInline()) {
 179       // If m_inst is an FCall and the callee is suitable for inlining, we can
 180       // translate the callee and potentially use its return type to extend the
 181       // tracelet.
 182
 183       auto callee = m_inst.funcd;
 184       FTRACE(1, "\nselectTracelet starting inlined call from {} to "
 185              "{} with stack:\n{}\n", curFunc()->fullName()->data(),
 186              callee->fullName()->data(), m_ht.showStack());
 187       auto returnSk = m_inst.nextSk();
 188       auto returnFuncOff = returnSk.offset() - curFunc()->base();
 189
 190       m_arStates.back().pop();
 191       m_arStates.emplace_back();
 192       m_curBlock->setInlinedCallee(callee);
 193       m_ht.beginInlining(m_inst.imm[0].u_IVA, callee, returnFuncOff,
 194                          doPrediction ? m_inst.outPred : Type::Gen);
 195
 196       m_sk = m_ht.curSrcKey();
 197       m_blockFinished = true;
 198       continue;
 199     }
 200
 201     auto const inlineReturn = m_ht.isInlining() && isRet(m_inst.op());
 202     try {
 203       m_irTrans.translateInstr(m_inst);
 204     } catch (const FailedIRGen& exn) {
 205       FTRACE(1, "ir generation for {} failed with {}\n",
 206              m_inst.toString(), exn.what());
 207       always_assert(!m_interp.count(m_sk));
 208       m_interp.insert(m_sk);
 209       m_region.reset();
 210       break;
 211     }
 212
 213     // We successfully translated the instruction, so update m_sk.
 214     m_sk.advance(m_curBlock->unit());
 215
 216     if (inlineReturn) {
 217       // If we just translated an inlined RetC, grab the updated SrcKey from
 218       // m_ht and clean up.
 219       m_sk = m_ht.curSrcKey().advanced(curUnit());
 220       m_arStates.pop_back();
 221       m_blockFinished = true;
 222       continue;
 223     } else if (m_inst.breaksTracelet ||
 224                (m_profiling && instrBreaksProfileBB(&m_inst))) {
 225       FTRACE(1, "selectTracelet: tracelet broken after {}\n", m_inst);
 226       break;
 227     } else {
 228       assert(m_sk.func() == m_ht.curFunc());
 229     }
 230
 231     if (isFCallStar(m_inst.op())) m_arStates.back().pop();
 232
 233     // Since the current instruction is over, advance HhbcTranslator's sk
 234     // before emitting the prediction (if any).
 235     if (doPrediction && m_inst.outPred < m_ht.topType(0, DataTypeGeneric)) {
 236       m_ht.setBcOff(m_sk.offset(), false);
 237       m_ht.checkTypeStack(0, m_inst.outPred, m_sk.offset());
 238     }
 239   }
 240
 241   printUnit(2, m_ht.unit(), " after tracelet formation ",
 242             nullptr, nullptr, m_ht.irBuilder().guards());
 243
 244   if (m_region && !m_region->blocks.empty()) {
 245     always_assert_log(
 246       !m_ht.isInlining(),
 247       [&] {
 248         return folly::format("Tried to end region while inlining:\n{}",
 249                              m_ht.unit()).str();
 250       });
 251
 252     m_ht.end(m_sk.offset());
 253     recordDependencies();
 254     truncateLiterals();
 255   }
 256
 257   return std::move(m_region);
 258 }
 259
 260 /*
 261  * Populate most fields of the NormalizedInstruction, assuming its sk
 262  * has already been set. Returns false iff the region should be
 263  * truncated before inst's SrcKey.
 264  */
 265 bool RegionFormer::prepareInstruction() {
 266   m_inst.~NormalizedInstruction();
 267   new (&m_inst) NormalizedInstruction();
 268   m_inst.source = m_sk;
 269   m_inst.m_unit = curUnit();
 270   m_inst.breaksTracelet = opcodeBreaksBB(m_inst.op()) ||
 271                             (dontGuardAnyInputs(m_inst.op()) &&
 272                              opcodeChangesPC(m_inst.op()));
 273   m_inst.changesPC = opcodeChangesPC(m_inst.op());
 274   m_inst.funcd = m_arStates.back().knownFunc();
 275   populateImmediates(m_inst);
 276   m_ht.setBcOff(m_sk.offset(), false);
 277
 278   InputInfos inputInfos;
 279   getInputs(m_startSk, m_inst, inputInfos, m_curBlock->func(), [&](int i) {
 280     return m_ht.irBuilder().localType(i, DataTypeGeneric);
 281   });
 282
 283   // Read types for all the inputs and apply MetaData.
 284   auto newDynLoc = [&](const InputInfo& ii) {
 285     auto dl = m_inst.newDynLoc(ii.loc, m_ht.rttFromLocation(ii.loc));
 286     FTRACE(2, "rttFromLocation: {} -> {}\n",
 287            ii.loc.pretty(), dl->rtt.pretty());
 288     return dl;
 289   };
 290
 291   for (auto const& ii : inputInfos) m_inst.inputs.push_back(newDynLoc(ii));
 292
 293   // This may not be necessary, but for now it's preserving
 294   // side-effects that the call to readMetaData used to have.
 295   if (isAlwaysNop(m_inst.op())) {
 296     m_inst.noOp = true;
 297   }
 298
 299   // This reads valueClass from the inputs so it used to need to
 300   // happen after readMetaData.  But now readMetaData is gone ...
 301   if (inliningDepth() == 0) annotate(&m_inst);
 302
 303   // Check all the inputs for unknown values.
 304   assert(inputInfos.size() == m_inst.inputs.size());
 305   for (unsigned i = 0; i < inputInfos.size(); ++i) {
 306     if (!consumeInput(i, inputInfos[i])) return false;
 307   }
 308
 309   if (!m_inst.noOp && inputInfos.needsRefCheck) {
 310     // Reffiness guards are always at the beginning of the trace for now, so
 311     // calculate the delta from the original sp to the ar.
 312     auto argNum = m_inst.imm[0].u_IVA;
 313     size_t entryArDelta = instrSpToArDelta((Op*)m_inst.pc()) -
 314       (m_ht.spOffset() - m_ctx.spOffset);
 315     try {
 316       m_inst.preppedByRef = m_arStates.back().checkByRef(argNum, entryArDelta,
 317                                                          &m_refDeps);
 318     } catch (const UnknownInputExc& exn) {
 319       // We don't have a guess for the current ActRec.
 320       FTRACE(1, "selectTracelet: don't have reffiness guess for {}\n",
 321              m_inst.toString());
 322       return false;
 323     }
 324     addInstruction();
 325     m_curBlock->setParamByRef(m_inst.source, m_inst.preppedByRef);
 326   } else {
 327     addInstruction();
 328   }
 329
 330   if (isFPush(m_inst.op())) m_arStates.back().pushFunc(m_inst);
 331
 332   return true;
 333 }
 334
 335 /*
 336  * Add the current instruction to the region.
 337  */
 338 void RegionFormer::addInstruction() {
 339   if (m_blockFinished) {
 340     FTRACE(2, "selectTracelet adding new block at {} after:\n{}\n",
 341            showShort(m_sk), show(*m_curBlock));
 342     RegionDesc::Block* newCurBlock = m_region->addBlock(curFunc(),
 343                                                         m_sk.resumed(),
 344                                                         m_sk.offset(), 0,
 345                                                         curSpOffset());
 346     m_region->addArc(m_curBlock->id(), newCurBlock->id());
 347     m_curBlock = newCurBlock;
 348     m_blockFinished = false;
 349   }
 350
 351   FTRACE(2, "selectTracelet adding instruction {}\n", m_inst.toString());
 352   m_curBlock->addInstruction();
 353 }
 354
 355 bool RegionFormer::tryInline() {
 356   if (!RuntimeOption::RepoAuthoritative ||
 357       (m_inst.op() != Op::FCall && m_inst.op() != Op::FCallD)) {
 358     return false;
 359   }
 360
 361   auto refuse = [this](const std::string& str) {
 362     FTRACE(2, "selectTracelet not inlining {}: {}\n",
 363            m_inst.toString(), str);
 364     return false;
 365   };
 366
 367   if (inliningDepth() >= RuntimeOption::EvalHHIRInliningMaxDepth) {
 368     return refuse("inlining level would be too deep");
 369   }
 370
 371   auto callee = m_inst.funcd;
 372   if (!callee || callee->isCPPBuiltin()) {
 373     return refuse("don't know callee or callee is builtin");
 374   }
 375
 376   if (callee == curFunc()) {
 377     return refuse("call is recursive");
 378   }
 379
 380   if (callee->hasVariadicCaptureParam()) {
 381     // FIXME: this doesn't have to remove inlining
 382     return refuse("callee has a variadic capture");
 383   }
 384
 385   if (m_inst.imm[0].u_IVA != callee->numParams()) {
 386     return refuse("numArgs doesn't match numParams of callee");
 387   }
 388
 389   // For analysis purposes, we require that the FPush* instruction is in the
 390   // same region.
 391   auto fpi = curFunc()->findFPI(m_sk.offset());
 392   const SrcKey pushSk{curFunc(), fpi->m_fpushOff, resumed()};
 393   int pushBlock = -1;
 394   auto& blocks = m_region->blocks;
 395   for (unsigned i = 0; i < blocks.size(); ++i) {
 396     if (blocks[i]->contains(pushSk)) {
 397       pushBlock = i;
 398       break;
 399     }
 400   }
 401   if (pushBlock == -1) {
 402     return refuse("FPush* is not in the current region");
 403   }
 404
 405   // Calls invalidate all live SSATmps, so don't allow any in the fpi region
 406   auto findFCall = [&] {
 407     for (unsigned i = pushBlock; i < blocks.size(); ++i) {
 408       auto& block = *blocks[i];
 409       auto sk = i == pushBlock ? pushSk.advanced() : block.start();
 410       while (sk <= block.last()) {
 411         if (sk == m_sk) return false;
 412
 413         auto op = sk.op();
 414         if (isFCallStar(op) || op == Op::FCallBuiltin) return true;
 415         sk.advance();
 416       }
 417     }
 418     not_reached();
 419   };
 420   if (findFCall()) {
 421     return refuse("fpi region contains another call");
 422   }
 423
 424   switch (pushSk.op()) {
 425     case OpFPushClsMethodD:
 426       if (callee->mayHaveThis()) return refuse("callee may have this pointer");
 427       // fallthrough
 428     case OpFPushFuncD:
 429     case OpFPushObjMethodD:
 430     case OpFPushCtorD:
 431     case OpFPushCtor:
 432       break;
 433
 434     default:
 435       return refuse(folly::format("unsupported push op {}",
 436                                   opcodeToName(pushSk.op())).str());
 437   }
 438
 439   // Make sure the FPushOp wasn't interpreted.
 440   auto spillFrame = findSpillFrame(m_ht.irBuilder().sp());
 441   if (!spillFrame) {
 442     return refuse("couldn't find SpillFrame for FPushOp");
 443   }
 444
 445   // Set up the region context, mapping stack slots in the caller to locals in
 446   // the callee.
 447   RegionContext ctx;
 448   ctx.func = callee;
 449   ctx.bcOffset = callee->base();
 450   ctx.spOffset = callee->numSlotsInFrame();
 451   ctx.resumed = false;
 452   for (int i = 0; i < callee->numParams(); ++i) {
 453     // DataTypeGeneric is used because we're just passing the locals into the
 454     // callee. It's up to the callee to constraint further if needed.
 455     auto type = m_ht.topType(i, DataTypeGeneric);
 456     uint32_t paramIdx = callee->numParams() - 1 - i;
 457     typedef RegionDesc::Location Location;
 458     ctx.liveTypes.push_back({Location::Local{paramIdx}, type});
 459   }
 460
 461   FTRACE(1, "selectTracelet analyzing callee {} with context:\n{}",
 462          callee->fullName()->data(), show(ctx));
 463   auto region = selectTracelet(ctx, inliningDepth() + 1, m_profiling);
 464   if (!region) {
 465     return refuse("failed to select region in callee");
 466   }
 467
 468   RegionDescIter iter(*region);
 469   if (!shouldIRInline(curFunc(), callee, iter)) {
 470     return refuse("shouldIRInline failed");
 471   }
 472   return true;
 473 }
 474
 475 void RegionFormer::truncateLiterals() {
 476   if (!m_region || m_region->blocks.empty() ||
 477       m_region->blocks.back()->empty()) return;
 478
 479   // Don't finish a region with literal values or values that have a class
 480   // related to the current context class. They produce valuable information
 481   // for optimizations that's lost across region boundaries.
 482   auto& lastBlock = *m_region->blocks.back();
 483   auto sk = lastBlock.start();
 484   auto endSk = sk;
 485   auto unit = lastBlock.unit();
 486   for (int i = 0, len = lastBlock.length(); i < len; ++i, sk.advance(unit)) {
 487     auto const op = sk.op();
 488     if (!isLiteral(op) && !isThisSelfOrParent(op)) {
 489       if (i == len - 1) return;
 490       endSk = sk;
 491     }
 492   }
 493   FTRACE(1, "selectTracelet truncating block after offset {}:\n{}\n",
 494          endSk.offset(), show(lastBlock));
 495   lastBlock.truncateAfter(endSk);
 496 }
 497
 498 /*
 499  * Check if the current type for the location in ii is specific enough for what
 500  * the current opcode wants. If not, return false.
 501  */
 502 bool RegionFormer::consumeInput(int i, const InputInfo& ii) {
 503   auto& rtt = m_inst.inputs[i]->rtt;
 504   if (ii.dontGuard || !rtt.isValue()) return true;
 505
 506   if (m_profiling && rtt.isRef() &&
 507       (m_region->blocks.size() > 1 || !m_region->blocks[0]->empty())) {
 508     // We don't want side exits when profiling, so only allow instructions that
 509     // consume refs at the beginning of the region.
 510     return false;
 511   }
 512
 513   if (!ii.dontBreak && !Type(rtt).isKnownDataType()) {
 514     // Trying to consume a value without a precise enough type.
 515     FTRACE(1, "selectTracelet: {} tried to consume {}\n",
 516            m_inst.toString(), m_inst.inputs[i]->pretty());
 517     return false;
 518   }
 519
 520   if (!rtt.isRef() || m_inst.ignoreInnerType || ii.dontGuardInner) {
 521     return true;
 522   }
 523
 524   if (!Type(rtt.innerType()).isKnownDataType()) {
 525     // Trying to consume a boxed value without a guess for the inner type.
 526     FTRACE(1, "selectTracelet: {} tried to consume ref {}\n",
 527            m_inst.toString(), m_inst.inputs[i]->pretty());
 528     return false;
 529   }
 530
 531   return true;
 532 }
 533
 534 /*
 535  * Records any type/reffiness predictions we depend on in the region. Guards
 536  * for locals and stack cells that are not used will be eliminated by the call
 537  * to relaxGuards.
 538  */
 539 void RegionFormer::recordDependencies() {
 540   // Record the incrementally constructed reffiness predictions.
 541   assert(!m_region->blocks.empty());
 542   auto& frontBlock = *m_region->blocks.front();
 543   for (auto const& dep : m_refDeps.m_arMap) {
 544     frontBlock.addReffinessPred(m_startSk, {dep.second.m_mask,
 545                                             dep.second.m_vals,
 546                                             dep.first});
 547   }
 548
 549   // Relax guards and record the ones that survived.
 550   auto& firstBlock = *m_region->blocks.front();
 551   auto blockStart = firstBlock.start();
 552   auto& unit = m_ht.unit();
 553   auto const doRelax = RuntimeOption::EvalHHIRRelaxGuards;
 554   bool changed = false;
 555   if (doRelax) {
 556     Timer _t(Timer::selectTracelet_relaxGuards);
 557     changed = relaxGuards(unit, *m_ht.irBuilder().guards(), m_profiling);
 558   }
 559
 560   visitGuards(unit, [&](const RegionDesc::Location& loc, Type type) {
 561     if (type <= Type::Cls) return;
 562     RegionDesc::TypePred pred{loc, type};
 563     FTRACE(1, "selectTracelet adding guard {}\n", show(pred));
 564     firstBlock.addPredicted(blockStart, pred);
 565   });
 566   if (changed) {
 567     printUnit(3, unit, " after guard relaxation ",
 568               nullptr, nullptr, m_ht.irBuilder().guards());
 569   }
 570
 571 }
 572 }
 573
 574 /*
 575  * Region selector that attempts to form the longest possible region using the
 576  * given context. The region will be broken before the first instruction that
 577  * attempts to consume an input with an insufficiently precise type, or after
 578  * most control flow instructions.
 579  *
 580  * May return a null region if the given RegionContext doesn't have
 581  * enough information to translate at least one instruction.
 582  */
 583 RegionDescPtr selectTracelet(const RegionContext& ctx, int inlineDepth,
 584                              bool profiling) {
 585   Timer _t(Timer::selectTracelet);
 586   InterpSet interp;
 587   RegionDescPtr region;
 588   uint32_t tries = 1;
 589
 590   while (!(region = RegionFormer(ctx, interp, inlineDepth, profiling).go())) {
 591     ++tries;
 592   }
 593
 594   if (region->blocks.size() == 0 || region->blocks.front()->length() == 0) {
 595     FTRACE(1, "selectTracelet giving up after {} tries\n", tries);
 596     return RegionDescPtr { nullptr };
 597   }
 598
 599   FTRACE(1, "selectTracelet returning, inlineDepth {}, {} tries:\n{}\n",
 600          inlineDepth, tries, show(*region));
 601   if (region->blocks.back()->length() == 0) {
 602     // If the final block is empty because it would've only contained
 603     // instructions producing literal values, kill it.
 604     region->blocks.pop_back();
 605   }
 606   return region;
 607 }
 608
 609 } }