Index: include/llvm/Analysis/AliasAnalysis.h =================================================================== --- include/llvm/Analysis/AliasAnalysis.h +++ include/llvm/Analysis/AliasAnalysis.h @@ -55,6 +55,7 @@ class MemTransferInst; class MemIntrinsic; class DominatorTree; +class NumberedBasicBlock; /// The possible results of an alias query. /// @@ -471,12 +472,14 @@ /// site modifies or reads the specified memory location. ModRefResult callCapturesBefore(const Instruction *I, const MemoryLocation &MemLoc, - DominatorTree *DT); + DominatorTree *DT, + NumberedBasicBlock *NBB = nullptr); /// callCapturesBefore - A convenience wrapper. ModRefResult callCapturesBefore(const Instruction *I, const Value *P, - uint64_t Size, DominatorTree *DT) { - return callCapturesBefore(I, MemoryLocation(P, Size), DT); + uint64_t Size, DominatorTree *DT, + NumberedBasicBlock *NBB = nullptr) { + return callCapturesBefore(I, MemoryLocation(P, Size), DT, NBB); } //===--------------------------------------------------------------------===// Index: include/llvm/Analysis/CaptureTracking.h =================================================================== --- include/llvm/Analysis/CaptureTracking.h +++ include/llvm/Analysis/CaptureTracking.h @@ -20,6 +20,7 @@ class Use; class Instruction; class DominatorTree; + class NumberedBasicBlock; /// PointerMayBeCaptured - Return true if this pointer value may be captured /// by the enclosing function (which is required to exist). This routine can @@ -44,7 +45,8 @@ /// final parameter is true. bool PointerMayBeCapturedBefore(const Value *V, bool ReturnCaptures, bool StoreCaptures, const Instruction *I, - DominatorTree *DT, bool IncludeI = false); + DominatorTree *DT, bool IncludeI = false, + NumberedBasicBlock *NBB = nullptr); /// This callback is used in conjunction with PointerMayBeCaptured. In /// addition to the interface here, you'll need to provide your own getters Index: include/llvm/Analysis/NumberedBasicBlock.h =================================================================== --- /dev/null +++ include/llvm/Analysis/NumberedBasicBlock.h @@ -0,0 +1,57 @@ +//===- llvm/Analysis/NumberedBasicBlock.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 NumberedBasicBlock class. NumberedBasicBlock 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 NumberedBasicBlock to do +// such queries. NumberedBasicBlock lazily built after a source BasicBlock and +// maintains an internal Instruction -> Position map. A NumberedBasicBlock +// 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_NUMBEREDBASICBLOCK_H +#define LLVM_ANALYSIS_NUMBEREDBASICBLOCK_H + +#include "llvm/ADT/DenseMap.h" +#include "llvm/IR/BasicBlock.h" + +namespace llvm { + +class Instruction; +class BasicBlock; + +class NumberedBasicBlock { +private: + SmallDenseMap NumberedInsts; + BasicBlock::const_iterator LastInstFound; + unsigned LastInstPos; + const BasicBlock *BB; + + /// \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); + +public: + NumberedBasicBlock(const BasicBlock *BasicB); + + /// \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); +}; + +} // End llvm namespace + +#endif Index: lib/Analysis/AliasAnalysis.cpp =================================================================== --- lib/Analysis/AliasAnalysis.cpp +++ lib/Analysis/AliasAnalysis.cpp @@ -345,8 +345,10 @@ // 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. -AliasAnalysis::ModRefResult AliasAnalysis::callCapturesBefore( - const Instruction *I, const MemoryLocation &MemLoc, DominatorTree *DT) { +AliasAnalysis::ModRefResult +AliasAnalysis::callCapturesBefore(const Instruction *I, + const MemoryLocation &MemLoc, + DominatorTree *DT, NumberedBasicBlock *NBB) { if (!DT) return AliasAnalysis::ModRef; @@ -361,7 +363,8 @@ if (llvm::PointerMayBeCapturedBefore(Object, /* ReturnCaptures */ true, /* StoreCaptures */ true, I, DT, - /* include Object */ true)) + /* include Object */ true, + /* NumberedBasicBlock */ NBB)) return AliasAnalysis::ModRef; unsigned ArgNo = 0; Index: lib/Analysis/CMakeLists.txt =================================================================== --- lib/Analysis/CMakeLists.txt +++ lib/Analysis/CMakeLists.txt @@ -45,6 +45,7 @@ MemoryLocation.cpp ModuleDebugInfoPrinter.cpp NoAliasAnalysis.cpp + NumberedBasicBlock.cpp PHITransAddr.cpp PostDominators.cpp PtrUseVisitor.cpp Index: lib/Analysis/CaptureTracking.cpp =================================================================== --- lib/Analysis/CaptureTracking.cpp +++ 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/NumberedBasicBlock.h" #include "llvm/IR/CallSite.h" #include "llvm/IR/Constants.h" #include "llvm/IR/Dominators.h" @@ -52,63 +53,6 @@ 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 @@ struct CapturesBefore : public CaptureTracker { CapturesBefore(bool ReturnCaptures, const Instruction *I, DominatorTree *DT, - bool IncludeI) - : LocalInstCache(I->getParent()), BeforeHere(I), DT(DT), + bool IncludeI, NumberedBasicBlock *IC) + : NumberedBB(IC), BeforeHere(I), DT(DT), ReturnCaptures(ReturnCaptures), IncludeI(IncludeI), Captured(false) {} void tooManyUses() override { Captured = true; } @@ -131,7 +75,7 @@ // 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' + // 'NumberedBB', 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 @@ // UseBB == BB, avoid pruning. if (isa(BeforeHere) || isa(I) || I == BeforeHere) return false; - if (!LocalInstCache.dominates(BeforeHere, I)) + if (!NumberedBB->dominates(BeforeHere, I)) return false; // 'BeforeHere' comes before 'I', it's safe to prune if we also @@ -196,7 +140,7 @@ return true; } - NumberedInstCache LocalInstCache; + NumberedBasicBlock *NumberedBB; const Instruction *BeforeHere; DominatorTree *DT; @@ -241,17 +185,25 @@ /// or not. bool llvm::PointerMayBeCapturedBefore(const Value *V, bool ReturnCaptures, bool StoreCaptures, const Instruction *I, - DominatorTree *DT, bool IncludeI) { + DominatorTree *DT, bool IncludeI, + NumberedBasicBlock *NBB) { assert(!isa(V) && "It doesn't make sense to ask whether a global is captured."); if (!DT) return PointerMayBeCaptured(V, ReturnCaptures, StoreCaptures); + if (!NBB) { + NumberedBasicBlock NewNBB(I->getParent()); + CapturesBefore CB(ReturnCaptures, I, DT, IncludeI, &NewNBB); + PointerMayBeCaptured(V, &CB); + return CB.Captured; + } + // TODO: See comment in PointerMayBeCaptured regarding what could be done // with StoreCaptures. - CapturesBefore CB(ReturnCaptures, I, DT, IncludeI); + CapturesBefore CB(ReturnCaptures, I, DT, IncludeI, NBB); PointerMayBeCaptured(V, &CB); return CB.Captured; } Index: lib/Analysis/MemoryDependenceAnalysis.cpp =================================================================== --- lib/Analysis/MemoryDependenceAnalysis.cpp +++ 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/NumberedBasicBlock.h" #include "llvm/Analysis/ValueTracking.h" #include "llvm/IR/DataLayout.h" #include "llvm/IR/Dominators.h" @@ -416,6 +417,12 @@ 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. + NumberedBasicBlock NBB(BB); + // Walk backwards through the basic block, looking for dependencies. while (ScanIt != BB->begin()) { Instruction *Inst = --ScanIt; @@ -619,7 +626,7 @@ AliasAnalysis::ModRefResult MR = AA->getModRefInfo(Inst, MemLoc); // If necessary, perform additional analysis. if (MR == AliasAnalysis::ModRef) - MR = AA->callCapturesBefore(Inst, MemLoc, DT); + MR = AA->callCapturesBefore(Inst, MemLoc, DT, &NBB); switch (MR) { case AliasAnalysis::NoModRef: // If the call has no effect on the queried pointer, just ignore it. Index: lib/Analysis/NumberedBasicBlock.cpp =================================================================== --- /dev/null +++ lib/Analysis/NumberedBasicBlock.cpp @@ -0,0 +1,79 @@ +//===- NumberedBasicBlock.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 NumberedBasicBlock class. NumberedBasicBlock +// 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 +// NumberedBasicBlock to do such queries. NumberedBasicBlock lazily built after +// a source BasicBlock and maintains an internal Instruction -> Position map. A +// NumberedBasicBlock 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/NumberedBasicBlock.h" +#include "llvm/IR/Instruction.h" +using namespace llvm; + +NumberedBasicBlock::NumberedBasicBlock(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 *NumberedBasicBlock::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 NumberedBasicBlock::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); +}