Index: include/llvm/Analysis/CaptureTracking.h =================================================================== --- include/llvm/Analysis/CaptureTracking.h +++ include/llvm/Analysis/CaptureTracking.h @@ -50,18 +50,28 @@ /// addition to the interface here, you'll need to provide your own getters /// to see whether anything was captured. struct CaptureTracker { + + /// Action - The possible actions shouldExplore must return. + enum Action { + Search, + Prune, + TooExpensive + }; + virtual ~CaptureTracker(); - /// tooManyUses - The depth of traversal has breached a limit. There may be + /// tooExpensive - The depth of traversal or the number of instructions + /// to search inside a basic block has breached a limit. There may be /// capturing instructions that will not be passed into captured(). - virtual void tooManyUses() = 0; + virtual void tooExpensive() = 0; - /// shouldExplore - This is the use of a value derived from the pointer. - /// To prune the search (ie., assume that none of its users could possibly - /// capture) return false. To search it, return true. + /// shouldExplore - This is the use of a value derived from the pointer. To + /// prune the search (ie., assume that none of its users could possibly + /// capture) return Action::Prune. To search it, return Action::Search. + /// To avoid really expensive compile time, return Action::TooExpensive. /// /// U->getUser() is always an Instruction. - virtual bool shouldExplore(const Use *U); + virtual Action shouldExplore(const Use *U); /// captured - Information about the pointer was captured by the user of /// use U. Return true to stop the traversal or false to continue looking Index: lib/Analysis/CaptureTracking.cpp =================================================================== --- lib/Analysis/CaptureTracking.cpp +++ lib/Analysis/CaptureTracking.cpp @@ -25,19 +25,25 @@ #include "llvm/IR/Constants.h" #include "llvm/IR/Dominators.h" #include "llvm/IR/Instructions.h" +#include "llvm/Support/CommandLine.h" using namespace llvm; +static cl::opt +BlockScanLimit("capture-tracker-blockscan-limit", cl::init(1000), cl::Hidden, + cl::desc("Limit the number of instructions to scan in a block")); + CaptureTracker::~CaptureTracker() {} -bool CaptureTracker::shouldExplore(const Use *U) { return true; } +CaptureTracker::Action CaptureTracker::shouldExplore(const Use *U) + { return CaptureTracker::Search; } namespace { struct SimpleCaptureTracker : public CaptureTracker { explicit SimpleCaptureTracker(bool ReturnCaptures) : ReturnCaptures(ReturnCaptures), Captured(false) {} - void tooManyUses() override { Captured = true; } + void tooExpensive() override { Captured = true; } bool captured(const Use *U) override { if (isa(U->getUser()) && !ReturnCaptures) @@ -62,25 +68,56 @@ : BeforeHere(I), DT(DT), ReturnCaptures(ReturnCaptures), IncludeI(IncludeI), Captured(false) {} - void tooManyUses() override { Captured = true; } + void tooExpensive() override { Captured = true; } - bool shouldExplore(const Use *U) override { + CaptureTracker::Action shouldExplore(const Use *U) override { Instruction *I = cast(U->getUser()); + if (BeforeHere == I && !IncludeI) - return false; + return CaptureTracker::Prune; BasicBlock *BB = I->getParent(); // We explore this usage only if the usage can reach "BeforeHere". // If use is not reachable from entry, there is no need to explore. if (BeforeHere != I && !DT->isReachableFromEntry(BB)) - return false; + return CaptureTracker::Prune; + + // Compute the case where both instructions are inside the same basic + // block and limit the number of instructions to search. We avoid using + // 'dominates' and 'isPotentiallyReachable' since both get very expensive + // in large basic block scenarios. + if (BB == BeforeHere->getParent()) { + if (BeforeHere == I) + return CaptureTracker::Search; + + // Loop through the basic block until we find BeforeHere or I. + unsigned int Limit = BlockScanLimit; + BasicBlock::const_iterator II = BB->begin(); + for (; Limit && &*II != BeforeHere && &*II != I; ++II, --Limit) + /*empty*/; + + if (!Limit) + return CaptureTracker::TooExpensive; + + // BeforeHere dominates I, we can also conservatively assume there's no + // path from I to BeforeHere if we're on the entry block or if there are + // no BB successors. + if (BeforeHere != I && &*II == BeforeHere && + (BB == &BB->getParent()->getEntryBlock() || + !BB->getTerminator()->getNumSuccessors())) + return CaptureTracker::Prune; + + return CaptureTracker::Search; + } + // If the value is defined in the same basic block as use and BeforeHere, // there is no need to explore the use if BeforeHere dominates use. // Check whether there is a path from I to BeforeHere. if (BeforeHere != I && DT->dominates(BeforeHere, I) && !isPotentiallyReachable(I, BeforeHere, DT)) - return false; - return true; + return CaptureTracker::Prune; + + return CaptureTracker::Search; } bool captured(const Use *U) override { @@ -176,9 +213,14 @@ // If there are lots of uses, conservatively say that the value // is captured to avoid taking too much compile time. if (Count++ >= Threshold) - return Tracker->tooManyUses(); + return Tracker->tooExpensive(); + + CaptureTracker::Action Res = Tracker->shouldExplore(&U); + if (Res == CaptureTracker::TooExpensive) + return Tracker->tooExpensive(); + if (Res == CaptureTracker::Prune) + continue; - if (!Tracker->shouldExplore(&U)) continue; Visited.insert(&U); Worklist.push_back(&U); } @@ -237,11 +279,16 @@ // If there are lots of uses, conservatively say that the value // is captured to avoid taking too much compile time. if (Count++ >= Threshold) - return Tracker->tooManyUses(); + return Tracker->tooExpensive(); + + if (Visited.insert(&UU).second) { + CaptureTracker::Action Res = Tracker->shouldExplore(&UU); - if (Visited.insert(&UU).second) - if (Tracker->shouldExplore(&UU)) + if (Res == CaptureTracker::Search) Worklist.push_back(&UU); + if (Res == CaptureTracker::TooExpensive) + return Tracker->tooExpensive(); + } } break; case Instruction::ICmp: Index: lib/Transforms/IPO/FunctionAttrs.cpp =================================================================== --- lib/Transforms/IPO/FunctionAttrs.cpp +++ lib/Transforms/IPO/FunctionAttrs.cpp @@ -346,7 +346,7 @@ ArgumentUsesTracker(const SmallPtrSet &SCCNodes) : Captured(false), SCCNodes(SCCNodes) {} - void tooManyUses() override { Captured = true; } + void tooExpensive() override { Captured = true; } bool captured(const Use *U) override { CallSite CS(U->getUser());