From 973b65781cdd3caf9899d8c65ebf2ed28268edc3 Mon Sep 17 00:00:00 2001 From: Guilherme Ottoni Date: Tue, 24 Feb 2015 11:24:53 -0800 Subject: [PATCH] Avoid forming tracelets that can't have IR fully emitted Summary: I noticed that the tracelet selector was sometimes returning a RegionDesc that didn't quite match the IR that would be emitted for it (see examples in attached task). So this diff puts in a check to make sure that a tracelet RegionDesc always ends in an IR instruction corresponding to its last bytecode instruction, and then fixes the exposed issues. The fix was basically to break the tracelet whenever the IR that is produced for tracelet-formation purposes reaches a dead end and the following IR blocks would be unreachable. Reviewed By: @swtaarrs Differential Revision: D1858456 --- hphp/runtime/vm/jit/prof-data.cpp | 23 +-------- hphp/runtime/vm/jit/region-selection.cpp | 13 +++++ hphp/runtime/vm/jit/region-selection.h | 14 ++++++ hphp/runtime/vm/jit/region-tracelet.cpp | 85 ++++++++++++++++++++++++++++++++ 4 files changed, 113 insertions(+), 22 deletions(-) diff --git a/hphp/runtime/vm/jit/prof-data.cpp b/hphp/runtime/vm/jit/prof-data.cpp index 6e3f779418e..44263b2200d 100644 --- a/hphp/runtime/vm/jit/prof-data.cpp +++ b/hphp/runtime/vm/jit/prof-data.cpp @@ -334,31 +334,10 @@ RegionDescPtr ProfData::transRegion(TransID id) const { return pTransRec.region(); } -/* - * Returns the last BC offset in the region that corresponds to the - * function where the region starts. This will normally be the offset - * of the last instruction in the last block, except if the function - * ends with an inlined call. In this case, the offset of the - * corresponding FCall* in the function that starts the region is - * returned. - */ -static Offset findLastBcOffset(const RegionDescPtr region) { - assert(!region->empty()); - auto& blocks = region->blocks(); - FuncId startFuncId = blocks[0]->start().getFuncId(); - for (int i = blocks.size() - 1; i >= 0; i--) { - SrcKey sk = blocks[i]->last(); - if (sk.getFuncId() == startFuncId) { - return sk.offset(); - } - } - not_reached(); -} - TransID ProfData::addTransProfile(const RegionDescPtr& region, const PostConditions& pconds) { TransID transId = m_numTrans++; - Offset lastBcOff = findLastBcOffset(region); + Offset lastBcOff = region->lastSrcKey().offset(); assert(region); DEBUG_ONLY size_t nBlocks = region->blocks().size(); diff --git a/hphp/runtime/vm/jit/region-selection.cpp b/hphp/runtime/vm/jit/region-selection.cpp index 10d9be6784a..f6417ef938e 100644 --- a/hphp/runtime/vm/jit/region-selection.cpp +++ b/hphp/runtime/vm/jit/region-selection.cpp @@ -120,6 +120,19 @@ uint32_t RegionDesc::instrSize() const { return size; } +SrcKey RegionDesc::lastSrcKey() const { + assert(!empty()); + FuncId startFuncId = start().getFuncId(); + for (int i = m_blocks.size() - 1; i >= 0; i--) { + SrcKey sk = m_blocks[i]->last(); + if (sk.getFuncId() == startFuncId) { + return sk; + } + } + always_assert(0); +} + + RegionDesc::Block* RegionDesc::addBlock(SrcKey sk, int length, FPAbsOffset spOffset) { diff --git a/hphp/runtime/vm/jit/region-selection.h b/hphp/runtime/vm/jit/region-selection.h index 864daee6180..e43586c6913 100644 --- a/hphp/runtime/vm/jit/region-selection.h +++ b/hphp/runtime/vm/jit/region-selection.h @@ -79,6 +79,20 @@ struct RegionDesc { const BlockIdSet& preds(BlockId bid) const; const BlockIdSet& sideExitingBlocks() const; bool isExit(BlockId bid) const; + + /* + * Returns the last BC offset in the region that corresponds to the + * function where the region starts. This will normally be the offset + * of the last instruction in the last block, except if the function + * ends with an inlined call. In this case, the offset of the + * corresponding FCall* in the function that starts the region is + * returned. + * + * Note that the notion of "last BC offset" only makes sense for + * regions that are linear traces. + */ + SrcKey lastSrcKey() const; + Block* addBlock(SrcKey sk, int length, FPAbsOffset spOffset); void deleteBlock(BlockId bid); void renumberBlock(BlockId oldId, BlockId newId); diff --git a/hphp/runtime/vm/jit/region-tracelet.cpp b/hphp/runtime/vm/jit/region-tracelet.cpp index 276251be0a2..18c08ea5347 100644 --- a/hphp/runtime/vm/jit/region-tracelet.cpp +++ b/hphp/runtime/vm/jit/region-tracelet.cpp @@ -47,6 +47,37 @@ TRACE_SET_MOD(region); typedef hphp_hash_set InterpSet; namespace { + +/////////////////////////////////////////////////////////////////////////////// + +bool isMainExit(const Block* block, SrcKey lastSk) { + if (!block->isExit()) return false; + + auto& lastInst = block->back(); + + // This captures cases where we end the region with a terminal + // instruction, e.g. RetCtrl, RaiseError, InterpOneCF. + if (lastInst.isTerminal() && lastInst.marker().sk() == lastSk) return true; + + // Otherwise, the region must contain a ReqBindJmp to a bytecode + // offset than will follow the execution of lastSk. + if (lastInst.op() != ReqBindJmp) return false; + + auto succOffsets = lastSk.succOffsets(); + + FTRACE(6, "isMainExit: instrSuccOffsets({}): {}\n", + show(lastSk), folly::join(", ", succOffsets)); + + return succOffsets.count(lastInst.marker().bcOff()); +} + +Block* findMainExitBlock(const IRUnit& unit, SrcKey lastSk) { + for (auto block : rpoSortCfg(unit)) { + if (isMainExit(block, lastSk)) return block; + } + return nullptr; +} + /////////////////////////////////////////////////////////////////////////////// struct RegionFormer { @@ -72,6 +103,10 @@ private: uint32_t m_numJmps; uint32_t m_numBCInstrs{0}; uint32_t m_pendingInlinedInstrs{0}; + // This map memoizes reachability of IR blocks during tracelet + // formation. A block won't have it's reachability stored in this + // map until it's been computed. + jit::hash_map m_irReachableBlocks; InliningDecider& m_inl; const bool m_profiling; @@ -88,6 +123,7 @@ private: bool tryInline(uint32_t& instrSize); void recordDependencies(); void truncateLiterals(); + bool irBlockReachable(Block* block); }; RegionFormer::RegionFormer(const RegionContext& ctx, @@ -131,7 +167,27 @@ bool RegionFormer::resumed() const { return irgen::resumed(m_hts); } +bool RegionFormer::irBlockReachable(Block* block) { + auto const blockId = block->id(); + auto it = m_irReachableBlocks.find(blockId); + if (it != m_irReachableBlocks.end()) return it->second; + bool result = block == m_hts.irb->unit().entry(); + for (auto& pred : block->preds()) { + if (irBlockReachable(pred.from())) { + result = true; + break; + } + } + m_irReachableBlocks[blockId] = result; + return result; +} + RegionDescPtr RegionFormer::go() { + SCOPE_ASSERT_DETAIL("Tracelet Selector") { + return folly::sformat("Region:\n{}\n\nUnit:\n{}\n", + *m_region, m_hts.irb->unit()); + }; + for (auto const& lt : m_ctx.liveTypes) { auto t = lt.type; if (t <= Type::Cls) { @@ -217,6 +273,24 @@ RegionDescPtr RegionFormer::go() { assert(m_sk.func() == curFunc()); } + auto const curIRBlock = m_hts.irb->curBlock(); + if (!irBlockReachable(curIRBlock)) { + FTRACE(1, + "selectTracelet: tracelet broken due to unreachable code (block {})\n", + curIRBlock->id()); + break; + } + + if (!curIRBlock->empty()) { + auto& lastInst = curIRBlock->back(); + if (lastInst.isTerminal() && + (lastInst.taken() == nullptr || lastInst.taken()->isCatch())) { + FTRACE(1, "selectTracelet: tracelet broken due to terminal/non-jumpy " + "IR instruction: {}\n", lastInst.toString()); + break; + } + } + if (isFCallStar(m_inst.op())) m_arStates.back().pop(); } @@ -244,6 +318,17 @@ RegionDescPtr RegionFormer::go() { ); recordDependencies(); + + // Make sure that the IR unit contains a main exit corresponding + // to the last bytecode instruction in the region. Note that this + // check has to happen before the call to truncateLiterals() + // because that updates the region but not the IR unit. + if (!m_region->blocks().back()->empty()) { + auto lastSk = m_region->lastSrcKey(); + always_assert_flog(findMainExitBlock(m_hts.irb->unit(), lastSk), + "No main exits found!"); + } + truncateLiterals(); } -- 2.11.4.GIT