From 8fea35acadea2e55824682a78bef54639e5ecfce Mon Sep 17 00:00:00 2001 From: Bruno Cardoso Lopes Date: Fri, 31 Jul 2015 14:31:35 +0000 Subject: [PATCH] [CaptureTracker] Provide an ordered basic block to PointerMayBeCapturedBefore This patch is a follow up from r240560 and is a step further into mitigating the compile time performance issues in CaptureTracker. By providing the CaptureTracker with a "cached ordered basic block" instead of computing it every time, MemDepAnalysis can use this cache throughout its calls to AA->callCapturesBefore, avoiding to recompute it for every scanned instruction. In the same testcase used in r240560, compile time is reduced from 2min to 30s. This also fixes PR22348. rdar://problem/19230319 Differential Revision: http://reviews.llvm.org/D11364 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@243750 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Analysis/AliasAnalysis.h | 18 +++-- include/llvm/Analysis/CaptureTracking.h | 7 +- include/llvm/Analysis/OrderedBasicBlock.h | 66 ++++++++++++++++++ lib/Analysis/AliasAnalysis.cpp | 18 +++-- lib/Analysis/CMakeLists.txt | 1 + lib/Analysis/CaptureTracking.cpp | 82 +++++----------------- lib/Analysis/MemoryDependenceAnalysis.cpp | 9 ++- lib/Analysis/OrderedBasicBlock.cpp | 85 +++++++++++++++++++++++ 8 files changed, 205 insertions(+), 81 deletions(-) create mode 100644 include/llvm/Analysis/OrderedBasicBlock.h create mode 100644 lib/Analysis/OrderedBasicBlock.cpp diff --git a/include/llvm/Analysis/AliasAnalysis.h b/include/llvm/Analysis/AliasAnalysis.h index 8725429fb78..e76f7771d4d 100644 --- a/include/llvm/Analysis/AliasAnalysis.h +++ b/include/llvm/Analysis/AliasAnalysis.h @@ -55,6 +55,7 @@ class AnalysisUsage; class MemTransferInst; class MemIntrinsic; class DominatorTree; +class OrderedBasicBlock; /// The possible results of an alias query. /// @@ -501,16 +502,19 @@ public: virtual ModRefInfo getModRefInfo(ImmutableCallSite CS1, ImmutableCallSite CS2); - /// Return information about whether a particular call site modifies or reads - /// the specified memory location. + /// \brief Return information about whether a particular call site modifies + /// or reads the specified memory location \p MemLoc before instruction \p I + /// in a BasicBlock. A ordered basic block \p OBB can be used to speed up + /// instruction ordering queries inside the BasicBlock containing \p I. ModRefInfo callCapturesBefore(const Instruction *I, - const MemoryLocation &MemLoc, - DominatorTree *DT); + const MemoryLocation &MemLoc, DominatorTree *DT, + OrderedBasicBlock *OBB = nullptr); - /// A convenience wrapper to synthesize a memory location. + /// \brief A convenience wrapper to synthesize a memory location. ModRefInfo callCapturesBefore(const Instruction *I, const Value *P, - uint64_t Size, DominatorTree *DT) { - return callCapturesBefore(I, MemoryLocation(P, Size), DT); + uint64_t Size, DominatorTree *DT, + OrderedBasicBlock *OBB = nullptr) { + return callCapturesBefore(I, MemoryLocation(P, Size), DT, OBB); } /// @} diff --git a/include/llvm/Analysis/CaptureTracking.h b/include/llvm/Analysis/CaptureTracking.h index 8b7c7a90f7c..8d2c095d858 100644 --- a/include/llvm/Analysis/CaptureTracking.h +++ b/include/llvm/Analysis/CaptureTracking.h @@ -20,6 +20,7 @@ namespace llvm { class Use; class Instruction; class DominatorTree; + class OrderedBasicBlock; /// PointerMayBeCaptured - Return true if this pointer value may be captured /// by the enclosing function (which is required to exist). This routine can @@ -41,10 +42,12 @@ namespace llvm { /// it or not. The boolean StoreCaptures specified whether storing the value /// (or part of it) into memory anywhere automatically counts as capturing it /// or not. Captures by the provided instruction are considered if the - /// final parameter is true. + /// final parameter is true. An ordered basic block in \p OBB could be used + /// to speed up capture-tracker queries. bool PointerMayBeCapturedBefore(const Value *V, bool ReturnCaptures, bool StoreCaptures, const Instruction *I, - DominatorTree *DT, bool IncludeI = false); + DominatorTree *DT, bool IncludeI = false, + OrderedBasicBlock *OBB = nullptr); /// This callback is used in conjunction with PointerMayBeCaptured. In /// addition to the interface here, you'll need to provide your own getters diff --git a/include/llvm/Analysis/OrderedBasicBlock.h b/include/llvm/Analysis/OrderedBasicBlock.h new file mode 100644 index 00000000000..5aa813eb483 --- /dev/null +++ b/include/llvm/Analysis/OrderedBasicBlock.h @@ -0,0 +1,66 @@ +//===- llvm/Analysis/OrderedBasicBlock.h --------------------- -*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defines the OrderedBasicBlock class. OrderedBasicBlock maintains +// an interface where clients can query if one instruction comes before another +// in a BasicBlock. Since BasicBlock currently lacks a reliable way to query +// relative position between instructions one can use OrderedBasicBlock to do +// such queries. OrderedBasicBlock is lazily built on a source BasicBlock and +// maintains an internal Instruction -> Position map. A OrderedBasicBlock +// instance should be discarded whenever the source BasicBlock changes. +// +// It's currently used by the CaptureTracker in order to find relative +// positions of a pair of instructions inside a BasicBlock. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ANALYSIS_ORDEREDBASICBLOCK_H +#define LLVM_ANALYSIS_ORDEREDBASICBLOCK_H + +#include "llvm/ADT/DenseMap.h" +#include "llvm/IR/BasicBlock.h" + +namespace llvm { + +class Instruction; +class BasicBlock; + +class OrderedBasicBlock { +private: + /// \brief Map a instruction to its position in a BasicBlock. + SmallDenseMap NumberedInsts; + + /// \brief Keep track of last instruction inserted into \p NumberedInsts. + /// It speeds up queries for uncached instructions by providing a start point + /// for new queries in OrderedBasicBlock::comesBefore. + BasicBlock::const_iterator LastInstFound; + + /// \brief The position/number to tag the next instruction to be found. + unsigned NextInstPos; + + /// \brief The source BasicBlock to map. + const BasicBlock *BB; + + /// \brief Given no cached results, find if \p A comes before \p B in \p BB. + /// Cache and number out instruction while walking \p BB. + bool comesBefore(const Instruction *A, const Instruction *B); + +public: + OrderedBasicBlock(const BasicBlock *BasicB); + + /// \brief Find out whether \p A dominates \p B, meaning whether \p A + /// comes before \p B in \p BB. This is a simplification that considers + /// cached instruction positions and ignores other basic blocks, being + /// only relevant to compare relative instructions positions inside \p BB. + bool dominates(const Instruction *A, const Instruction *B); +}; + +} // End llvm namespace + +#endif diff --git a/lib/Analysis/AliasAnalysis.cpp b/lib/Analysis/AliasAnalysis.cpp index 22ef7739a2d..9e69342e80b 100644 --- a/lib/Analysis/AliasAnalysis.cpp +++ b/lib/Analysis/AliasAnalysis.cpp @@ -335,13 +335,18 @@ ModRefInfo AliasAnalysis::getModRefInfo(const AtomicRMWInst *RMW, return MRI_ModRef; } -// FIXME: this is really just shoring-up a deficiency in alias analysis. -// BasicAA isn't willing to spend linear time determining whether an alloca -// was captured before or after this particular call, while we are. However, -// with a smarter AA in place, this test is just wasting compile time. +/// \brief Return information about whether a particular call site modifies +/// or reads the specified memory location \p MemLoc before instruction \p I +/// in a BasicBlock. A ordered basic block \p OBB can be used to speed up +/// instruction-ordering queries inside the BasicBlock containing \p I. +/// FIXME: this is really just shoring-up a deficiency in alias analysis. +/// BasicAA isn't willing to spend linear time determining whether an alloca +/// was captured before or after this particular call, while we are. However, +/// with a smarter AA in place, this test is just wasting compile time. ModRefInfo AliasAnalysis::callCapturesBefore(const Instruction *I, const MemoryLocation &MemLoc, - DominatorTree *DT) { + DominatorTree *DT, + OrderedBasicBlock *OBB) { if (!DT) return MRI_ModRef; @@ -356,7 +361,8 @@ ModRefInfo AliasAnalysis::callCapturesBefore(const Instruction *I, if (llvm::PointerMayBeCapturedBefore(Object, /* ReturnCaptures */ true, /* StoreCaptures */ true, I, DT, - /* include Object */ true)) + /* include Object */ true, + /* OrderedBasicBlock */ OBB)) return MRI_ModRef; unsigned ArgNo = 0; diff --git a/lib/Analysis/CMakeLists.txt b/lib/Analysis/CMakeLists.txt index 3ec79adba57..399c0e733b5 100644 --- a/lib/Analysis/CMakeLists.txt +++ b/lib/Analysis/CMakeLists.txt @@ -45,6 +45,7 @@ add_llvm_library(LLVMAnalysis MemoryLocation.cpp ModuleDebugInfoPrinter.cpp NoAliasAnalysis.cpp + OrderedBasicBlock.cpp PHITransAddr.cpp PostDominators.cpp PtrUseVisitor.cpp diff --git a/lib/Analysis/CaptureTracking.cpp b/lib/Analysis/CaptureTracking.cpp index 52ef807aeb5..fc23aa53d7c 100644 --- a/lib/Analysis/CaptureTracking.cpp +++ b/lib/Analysis/CaptureTracking.cpp @@ -21,6 +21,7 @@ #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Analysis/CFG.h" #include "llvm/Analysis/CaptureTracking.h" +#include "llvm/Analysis/OrderedBasicBlock.h" #include "llvm/IR/CallSite.h" #include "llvm/IR/Constants.h" #include "llvm/IR/Dominators.h" @@ -52,63 +53,6 @@ namespace { bool Captured; }; - struct NumberedInstCache { - SmallDenseMap NumberedInsts; - BasicBlock::const_iterator LastInstFound; - unsigned LastInstPos; - const BasicBlock *BB; - - NumberedInstCache(const BasicBlock *BasicB) : LastInstPos(0), BB(BasicB) { - LastInstFound = BB->end(); - } - - /// \brief Find the first instruction 'A' or 'B' in 'BB'. Number out - /// instruction while walking 'BB'. - const Instruction *find(const Instruction *A, const Instruction *B) { - const Instruction *Inst = nullptr; - assert(!(LastInstFound == BB->end() && LastInstPos != 0) && - "Instruction supposed to be in NumberedInsts"); - - // Start the search with the instruction found in the last lookup round. - auto II = BB->begin(); - auto IE = BB->end(); - if (LastInstFound != IE) - II = std::next(LastInstFound); - - // Number all instructions up to the point where we find 'A' or 'B'. - for (++LastInstPos; II != IE; ++II, ++LastInstPos) { - Inst = cast(II); - NumberedInsts[Inst] = LastInstPos; - if (Inst == A || Inst == B) - break; - } - - assert(II != IE && "Instruction not found?"); - LastInstFound = II; - return Inst; - } - - /// \brief Find out whether 'A' dominates 'B', meaning whether 'A' - /// comes before 'B' in 'BB'. This is a simplification that considers - /// cached instruction positions and ignores other basic blocks, being - /// only relevant to compare relative instructions positions inside 'BB'. - bool dominates(const Instruction *A, const Instruction *B) { - assert(A->getParent() == B->getParent() && - "Instructions must be in the same basic block!"); - - unsigned NA = NumberedInsts.lookup(A); - unsigned NB = NumberedInsts.lookup(B); - if (NA && NB) - return NA < NB; - if (NA) - return true; - if (NB) - return false; - - return A == find(A, B); - } - }; - /// Only find pointer captures which happen before the given instruction. Uses /// the dominator tree to determine whether one instruction is before another. /// Only support the case where the Value is defined in the same basic block @@ -116,8 +60,8 @@ namespace { struct CapturesBefore : public CaptureTracker { CapturesBefore(bool ReturnCaptures, const Instruction *I, DominatorTree *DT, - bool IncludeI) - : LocalInstCache(I->getParent()), BeforeHere(I), DT(DT), + bool IncludeI, OrderedBasicBlock *IC) + : OrderedBB(IC), BeforeHere(I), DT(DT), ReturnCaptures(ReturnCaptures), IncludeI(IncludeI), Captured(false) {} void tooManyUses() override { Captured = true; } @@ -131,7 +75,7 @@ namespace { // Compute the case where both instructions are inside the same basic // block. Since instructions in the same BB as BeforeHere are numbered in - // 'LocalInstCache', avoid using 'dominates' and 'isPotentiallyReachable' + // 'OrderedBB', avoid using 'dominates' and 'isPotentiallyReachable' // which are very expensive for large basic blocks. if (BB == BeforeHere->getParent()) { // 'I' dominates 'BeforeHere' => not safe to prune. @@ -142,7 +86,7 @@ namespace { // UseBB == BB, avoid pruning. if (isa(BeforeHere) || isa(I) || I == BeforeHere) return false; - if (!LocalInstCache.dominates(BeforeHere, I)) + if (!OrderedBB->dominates(BeforeHere, I)) return false; // 'BeforeHere' comes before 'I', it's safe to prune if we also @@ -196,7 +140,7 @@ namespace { return true; } - NumberedInstCache LocalInstCache; + OrderedBasicBlock *OrderedBB; const Instruction *BeforeHere; DominatorTree *DT; @@ -238,21 +182,29 @@ bool llvm::PointerMayBeCaptured(const Value *V, /// returning the value (or part of it) from the function counts as capturing /// it or not. The boolean StoreCaptures specified whether storing the value /// (or part of it) into memory anywhere automatically counts as capturing it -/// or not. +/// or not. A ordered basic block \p OBB can be used in order to speed up +/// queries about relative order among instructions in the same basic block. bool llvm::PointerMayBeCapturedBefore(const Value *V, bool ReturnCaptures, bool StoreCaptures, const Instruction *I, - DominatorTree *DT, bool IncludeI) { + DominatorTree *DT, bool IncludeI, + OrderedBasicBlock *OBB) { assert(!isa(V) && "It doesn't make sense to ask whether a global is captured."); + bool UseNewOBB = OBB == nullptr; if (!DT) return PointerMayBeCaptured(V, ReturnCaptures, StoreCaptures); + if (UseNewOBB) + OBB = new OrderedBasicBlock(I->getParent()); // TODO: See comment in PointerMayBeCaptured regarding what could be done // with StoreCaptures. - CapturesBefore CB(ReturnCaptures, I, DT, IncludeI); + CapturesBefore CB(ReturnCaptures, I, DT, IncludeI, OBB); PointerMayBeCaptured(V, &CB); + + if (UseNewOBB) + delete OBB; return CB.Captured; } diff --git a/lib/Analysis/MemoryDependenceAnalysis.cpp b/lib/Analysis/MemoryDependenceAnalysis.cpp index 5ac6fdf239a..54ac1b61054 100644 --- a/lib/Analysis/MemoryDependenceAnalysis.cpp +++ b/lib/Analysis/MemoryDependenceAnalysis.cpp @@ -22,6 +22,7 @@ #include "llvm/Analysis/InstructionSimplify.h" #include "llvm/Analysis/MemoryBuiltins.h" #include "llvm/Analysis/PHITransAddr.h" +#include "llvm/Analysis/OrderedBasicBlock.h" #include "llvm/Analysis/ValueTracking.h" #include "llvm/IR/DataLayout.h" #include "llvm/IR/Dominators.h" @@ -420,6 +421,12 @@ MemDepResult MemoryDependenceAnalysis::getPointerDependencyFrom( const DataLayout &DL = BB->getModule()->getDataLayout(); + // Create a numbered basic block to lazily compute and cache instruction + // positions inside a BB. This is used to provide fast queries for relative + // position between two instructions in a BB and can be used by + // AliasAnalysis::callCapturesBefore. + OrderedBasicBlock OBB(BB); + // Walk backwards through the basic block, looking for dependencies. while (ScanIt != BB->begin()) { Instruction *Inst = --ScanIt; @@ -623,7 +630,7 @@ MemDepResult MemoryDependenceAnalysis::getPointerDependencyFrom( ModRefInfo MR = AA->getModRefInfo(Inst, MemLoc); // If necessary, perform additional analysis. if (MR == MRI_ModRef) - MR = AA->callCapturesBefore(Inst, MemLoc, DT); + MR = AA->callCapturesBefore(Inst, MemLoc, DT, &OBB); switch (MR) { case MRI_NoModRef: // If the call has no effect on the queried pointer, just ignore it. diff --git a/lib/Analysis/OrderedBasicBlock.cpp b/lib/Analysis/OrderedBasicBlock.cpp new file mode 100644 index 00000000000..0f0016f22cc --- /dev/null +++ b/lib/Analysis/OrderedBasicBlock.cpp @@ -0,0 +1,85 @@ +//===- OrderedBasicBlock.cpp --------------------------------- -*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file implements the OrderedBasicBlock class. OrderedBasicBlock +// maintains an interface where clients can query if one instruction comes +// before another in a BasicBlock. Since BasicBlock currently lacks a reliable +// way to query relative position between instructions one can use +// OrderedBasicBlock to do such queries. OrderedBasicBlock is lazily built on a +// source BasicBlock and maintains an internal Instruction -> Position map. A +// OrderedBasicBlock instance should be discarded whenever the source +// BasicBlock changes. +// +// It's currently used by the CaptureTracker in order to find relative +// positions of a pair of instructions inside a BasicBlock. +// +//===----------------------------------------------------------------------===// + +#include "llvm/Analysis/OrderedBasicBlock.h" +#include "llvm/IR/Instruction.h" +using namespace llvm; + +OrderedBasicBlock::OrderedBasicBlock(const BasicBlock *BasicB) + : NextInstPos(0), BB(BasicB) { + LastInstFound = BB->end(); +} + +/// \brief Given no cached results, find if \p A comes before \p B in \p BB. +/// Cache and number out instruction while walking \p BB. +bool OrderedBasicBlock::comesBefore(const Instruction *A, + const Instruction *B) { + const Instruction *Inst = nullptr; + assert(!(LastInstFound == BB->end() && NextInstPos != 0) && + "Instruction supposed to be in NumberedInsts"); + + // Start the search with the instruction found in the last lookup round. + auto II = BB->begin(); + auto IE = BB->end(); + if (LastInstFound != IE) + II = std::next(LastInstFound); + + // Number all instructions up to the point where we find 'A' or 'B'. + for (; II != IE; ++II) { + Inst = cast(II); + NumberedInsts[Inst] = NextInstPos++; + if (Inst == A || Inst == B) + break; + } + + assert(II != IE && "Instruction not found?"); + assert((Inst == A || Inst == B) && "Should find A or B"); + LastInstFound = II; + return Inst == A; +} + +/// \brief Find out whether \p A dominates \p B, meaning whether \p A +/// comes before \p B in \p BB. This is a simplification that considers +/// cached instruction positions and ignores other basic blocks, being +/// only relevant to compare relative instructions positions inside \p BB. +bool OrderedBasicBlock::dominates(const Instruction *A, const Instruction *B) { + assert(A->getParent() == B->getParent() && + "Instructions must be in the same basic block!"); + + // First we lookup the instructions. If they don't exist, lookup will give us + // back ::end(). If they both exist, we compare the numbers. Otherwise, if NA + // exists and NB doesn't, it means NA must come before NB because we would + // have numbered NB as well if it didn't. The same is true for NB. If it + // exists, but NA does not, NA must come after it. If neither exist, we need + // to number the block and cache the results (by calling comesBefore). + auto NAI = NumberedInsts.find(A); + auto NBI = NumberedInsts.find(B); + if (NAI != NumberedInsts.end() && NBI != NumberedInsts.end()) + return NAI->second < NBI->second; + if (NAI != NumberedInsts.end()) + return true; + if (NBI != NumberedInsts.end()) + return false; + + return comesBefore(A, B); +} -- 2.34.1