diff --git a/llvm/include/llvm/Analysis/MustExecute.h b/llvm/include/llvm/Analysis/MustExecute.h --- a/llvm/include/llvm/Analysis/MustExecute.h +++ b/llvm/include/llvm/Analysis/MustExecute.h @@ -24,12 +24,15 @@ #define LLVM_ANALYSIS_MUSTEXECUTE_H #include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/SetVector.h" #include "llvm/Analysis/EHPersonalities.h" #include "llvm/Analysis/InstructionPrecedenceTracking.h" #include "llvm/Analysis/LoopInfo.h" #include "llvm/IR/BasicBlock.h" #include "llvm/IR/Dominators.h" #include "llvm/IR/Instruction.h" +#include "llvm/Support/Allocator.h" namespace llvm { @@ -186,9 +189,318 @@ FORWARD = 1, }; -/// Must be executed iterators visit stretches of instructions that are -/// guaranteed to be executed together, potentially with other instruction -/// executed in-between. +/// Must be executed intervals are stretches of instructions that are +/// guaranteed to be executed together without any other instruction +/// executed in-between. In addition, an interval `I` can end in a link into +/// another interval `J`. This means that the instructions of the interval +/// `J`, starting from the position the link points to, are always executed +/// before or respectively after the instruction in `I`. Note that there +/// might be other instructions executed in-between linked intervals. +/// +/// Given the following code, and assuming all statements are single +/// instructions which transfer execution to the successor (see +/// isGuaranteedToTransferExecutionToSuccessor), there are three intervals as +/// shown in the table below. +/// +/// \code +/// A; +/// B; +/// if (...) { +/// C; +/// D; +/// } +/// E; +/// \endcode +/// +/// Int | Previous | Instructions | Next +/// (1) | None | A ; B | (3) +/// (2) | (1) | C ; D | (3) +/// (3) | (1) | E | None +/// +/// From the above table one can derive that C and D are always executed with +/// A, B, and E. However, A, B, and E, are not necessarily executed with C and +/// D but always together. +/// +/// +/// Below is an extended example with instructions F and G and we assume F might +/// not transfer execution to it's successor G. The resulting intervals are +/// shown in the table below. +/// +/// \code +/// A; +/// B; +/// if (...) { +/// C; +/// D; +/// } +/// E; +/// F; // Might not transfer execution to its successor G. +/// G; +/// \endcode +/// +/// Int | Previous | Instructions | Next +/// (1) | None | A ; B | (3) +/// (2) | (1) | C ; D | (3) +/// (3) | (1) | E ; F | None +/// (4) | (3) | G | None +/// +/// As indicated by the table, E and F are executed always together with A and B +/// but not C, D, or G. However, G is always executed with A, B, E, and F. +/// +/// +/// A more complex example involving conditionals, loops, break, and continue +/// is shown below. We again assume all instructions will transmit control to +/// the successor and we assume we can prove the loops to be finite. We omit +/// non-trivial branch conditions as the exploration is oblivious to them. +/// Constant branches are assumed to be unconditional in the CFG. The resulting +/// intervals are shown in the table below. +/// +/// \code +/// A; +/// while (true) { +/// B; +/// if (...) +/// C; +/// if (...) +/// continue; +/// D; +/// if (...) +/// break; +/// do { +/// if (...) +/// continue; +/// E; +/// } while (...) +/// F; +/// } +/// G; +/// \endcode +/// +/// Int | Previous | Instructions | Next +/// (1) | None | A | (7) +/// (2) | (1) | B | (4) +/// (3) | (2) | C | (4) +/// (4) | (2) | D | (7) +/// (5) | (4) | E | (6) +/// (6) | (4) | F | (2) +/// (7) | (1) | G | None +/// +/// +/// Note that the examples show optimal intervals but not necessarily the ones +/// derived by the implementation. Also note that an interval has a direction +/// so there would be an interval for the forward direction and one for the +/// backward direction. The former is linked as described by the Next column in +/// the examples the latter as described by the Previous column. +/// +struct MustBeExecutedInterval { + + /// A position on an interval. + struct Position { + + Position(MustBeExecutedInterval *Interval = nullptr) + : Interval(Interval), Offset(0) {} + + /// Return the instruction at this position. + const Instruction *getInstruction() const { + assert(bool(*this) && + "Invalid positions do not have an associated instruction!"); + return (*Interval)[Offset]; + } + + /// Return the interval at this position. + MustBeExecutedInterval *getInterval() const { return Interval; } + unsigned getOffset() const { return Offset; } + + /// Allow valid positions to evaluate to 'true' and invalid ones to 'false' + /// when a position is converted to a boolean. + operator bool() const { return Interval; } + + /// Equality operator. + bool operator==(const Position &Other) const { + return Interval == Other.Interval && Offset == Other.Offset; + } + + /// Advance the position in the direction \p Dir. + /// + /// If there is no next instruction in the direction, this will result in + /// an invalid position, hence the interval will be a nullptr. + ///{ + Position &operator++() { return (*this) += 1; } + + Position operator++(int) { + Position tmp(*this); + ++(*this); + return tmp; + } + + Position &operator+=(unsigned N) { + if (!bool(*this)) + return *this; + + // If the offset adjusted wrt. direction is still in the associated + // interval, we adjust the offset and are done. Otherwise, we try to go to + // the linked interval in the direction and set the offset accordingly, + // hence to the very beginning or end depending on the direction. If there + // is no linked interval, all members will be set to NULL and the position + // becomes invalid. + if (Interval->isInbounds(Offset + N)) { + Offset += N; + return *this; + } + + if (Interval->getPosInNextInterval()) { + unsigned Advanced = Interval->size() - Offset - 1; + assert(Interval->size() >= Offset + 1 && "Unexpected offset!"); + assert(N >= Advanced + 1 && "Unexpected offset!"); + *this = Interval->getPosInNextInterval(); + return (*this) += N - Advanced - 1; + } + + Interval = nullptr; + Offset = 0; + return *this; + } + ///} + + /// Print method for debugging purposes. + void print(raw_ostream &OS, bool Detailed = false) const { + OS << "{" << Offset << "@"; + if (Interval) + Interval->print(OS, false); + else + OS << "[NONE:NONE:N]"; + OS << "}"; + } + + private: + /// The interval this position is currently associated with. + MustBeExecutedInterval *Interval; + + /// The current offset from the beginning of the associated interval. + unsigned Offset; + + friend struct MustBeExecutedContextExplorer; + }; + + /// Constructor for a new interval centered around \p I. + MustBeExecutedInterval(const Instruction &I, ExplorationDirection Dir) + : Dir(Dir) { + Insts.insert(&I); + } + + /// Return the interval that contains the instructions executed after/before + /// the ones in this interval. + MustBeExecutedInterval *getNextInterval() const { + return PosInNextInterval.getInterval(); + } + + /// Return the position in the next interval at which execution is known to + /// continue. + const Position &getPosInNextInterval() const { return PosInNextInterval; } + + /// Return the execution direction of this interval. + ExplorationDirection getDirection() const { return Dir; } + + /// Return true if \p Offset is part of this interval, false otherwise. + bool isInbounds(unsigned Offset) { return Offset < size(); } + + /// Subscript operator to allow easy access to the instructions based on their + /// offset. + const Instruction *operator[](unsigned Offset) const { return Insts[Offset]; } + + /// Return true if \p I is in this interval + bool count(const Instruction &I) const { return Insts.count(&I); } + + /// Print method for debugging purposes. + void print(raw_ostream &OS, bool Detailed = false) const { + OS << "[" << this << "(" << size() << ") + "; + PosInNextInterval.print(OS); + OS << " : " << unsigned(getDirection()) << "]"; + if (Detailed) { + OS << "\n"; + for (auto *I : Insts) + OS << "- " << *I << "\n"; + } + } + + /// Return the number of instructions contained in this interval. + unsigned size() const { return Insts.size(); } + + /// Return true if this interval is final, that is no more extensions are + /// possible. + bool isFinalized() const { return IsFinalized; } + +private: + /// Indicate the interval is not going to be modified later on. + void finalize() { + assert(!IsFinalized && "Interval was marked finalized already!"); + IsFinalized = true; + } + + /// Set the next interval, return true if successful, false otherwise. + bool setPosInNextInterval(const Position &P) { + assert(!PosInNextInterval && "Interval already has a link to another one!"); + assert(!IsFinalized && "Interval was marked finalized already!"); + + // Do not create cyclic lists. The check is potentially expensive but should + // not be in practise because we usually explore the context to the fullest + // which will prevent an extension after a "PrevInterval" was set. However, + // to prevent the quadratic worst case, we have a cut-off. + if (HasPrevInterval) { + unsigned MaxChainLength = 6; + MustBeExecutedInterval *MBEI = P.getInterval(); + while (MBEI) { + if (MBEI == this || (--MaxChainLength == 0)) + return false; + MBEI = MBEI->getNextInterval(); + } + } + + PosInNextInterval = P; + PosInNextInterval.getInterval()->HasPrevInterval = true; + return true; + } + + /// Extend the interval by \p I + bool extend(const Instruction &I) { + assert(!PosInNextInterval && + "Cannot advance the front if a next interval is already set!"); + assert(!IsFinalized && "Interval was marked finalized already!"); + + // If we have seen the instruction we will not add it. This happens when we + // encountered an endless loop contained entirely in this interval. + return Insts.insert(&I); + } + + /// The vectors that represent the instructions in the interval. + SmallSetVector Insts; + + /// The instruction executed next after the ones in Insts. + Position PosInNextInterval; + + /// The direction in which the instruction in this interval are executed. + /// Forward means Insts[i] is executed before Insts[i+1], backward means it is + /// the other way around. + ExplorationDirection Dir; + + /// A flag to indicate the interval is not going to change anymore. Used to + /// prevent us from trying to extend it after an earlier attempted failed. + bool IsFinalized = false; + + /// Flag to indicate that another interval points into this one. Used to + /// determine if we need to check for potential endless loops or if there + /// cannot be any. + bool HasPrevInterval = false; + + friend struct MustBeExecutedContextExplorer; +}; + +/// Must be executed iterators visit stretches of instructions, so called +/// must-be-executed-intervals, that are guaranteed to be executed together, +/// potentially with other instruction executed in-between. +/// +/// See MustBeExecutedInterval for a discussion about the intervals of these +/// examples. /// /// Given the following code, and assuming all statements are single /// instructions which transfer execution to the successor (see @@ -276,6 +588,11 @@ /// derived by the explorer depending on the available CFG analyses (see /// MustBeExecutedContextExplorer). Also note that we, depending on the options, /// the visit set can contain instructions from other functions. +/// +/// Depending on the template parameter \p CachedOnly, the iterator will either +/// only visit existing instructions in the interval (\p CachedOnly == true) or +/// also use the MustBeExecutedContextExplorer to extend the intervals if +/// needed. struct MustBeExecutedIterator { /// Type declarations that make his class an input iterator. ///{ @@ -286,32 +603,12 @@ typedef std::input_iterator_tag iterator_category; ///} - using ExplorerTy = MustBeExecutedContextExplorer; - - MustBeExecutedIterator(const MustBeExecutedIterator &Other) - : Visited(Other.Visited), Explorer(Other.Explorer), - CurInst(Other.CurInst), Head(Other.Head), Tail(Other.Tail) {} - - MustBeExecutedIterator(MustBeExecutedIterator &&Other) - : Visited(std::move(Other.Visited)), Explorer(Other.Explorer), - CurInst(Other.CurInst), Head(Other.Head), Tail(Other.Tail) {} - - MustBeExecutedIterator &operator=(MustBeExecutedIterator &&Other) { - if (this != &Other) { - std::swap(Visited, Other.Visited); - std::swap(CurInst, Other.CurInst); - std::swap(Head, Other.Head); - std::swap(Tail, Other.Tail); - } - return *this; - } - - ~MustBeExecutedIterator() {} - - /// Pre- and post-increment operators. + /// Pre- and post-increment operators. Both can cause the underlying intervals + /// to be extended if this is not a cached-only iterator, that is if an + /// explorer was provided at creation time. ///{ MustBeExecutedIterator &operator++() { - CurInst = advance(); + advance(); return *this; } @@ -325,7 +622,7 @@ /// Equality and inequality operators. Note that we ignore the history here. ///{ bool operator==(const MustBeExecutedIterator &Other) const { - return CurInst == Other.CurInst && Head == Other.Head && Tail == Other.Tail; + return Pos[0] == Other.Pos[0] && Pos[1] == Other.Pos[1]; } bool operator!=(const MustBeExecutedIterator &Other) const { @@ -334,50 +631,58 @@ ///} /// Return the underlying instruction. - const Instruction *&operator*() { return CurInst; } - const Instruction *getCurrentInst() const { return CurInst; } + const Instruction *operator*() const { return getCurrentInst(); } + const Instruction *getCurrentInst() const { return Pos[0].getInstruction(); } + + /// Return true if \p I is known to be found by this iterator, thus to be + /// executed with the instruction this iterator was created for. If the known + /// context does not contain \p I, the non-const version will try to use the + /// Explorer, if available, to extend it. + bool isExecutedWith(const Instruction &I) const; - /// Return true if \p I was encountered by this iterator already. - bool count(const Instruction *I) const { - return Visited.count({I, ExplorationDirection::FORWARD}) || - Visited.count({I, ExplorationDirection::BACKWARD}); + /// Configurable print method for debugging purposes. + /// + /// \param OS The stream we print to. + /// \param PrintInst If set, the current instruction is printed. + /// \param PrintInterval If set, the interval containing the current + /// instruction is printed. + void print(raw_ostream &OS, bool PrintInst, bool PrintInterval) const { + if (PrintInst && getCurrentInst()) + OS << "[" << *getCurrentInst() << "]"; + + if (PrintInterval) + Pos[0].print(OS, false); } private: - using VisitedSetTy = - DenseSet>; - /// Private constructors. - MustBeExecutedIterator(ExplorerTy &Explorer, const Instruction *I); - - /// Reset the iterator to its initial state pointing at \p I. - void reset(const Instruction *I); + MustBeExecutedIterator() {} + MustBeExecutedIterator(const MustBeExecutedInterval::Position &FwdPos, + const MustBeExecutedInterval::Position &BwdPos, + MustBeExecutedContextExplorer *Explorer) + : Explorer(Explorer) { + Pos[0] = FwdPos; + Pos[1] = BwdPos; + } - /// Reset the iterator to point at \p I, keep cached state. - void resetInstruction(const Instruction *I); + /// Advance one of the underlying positions (Head or Tail) potentially after + /// exploring the context further (using Explorer). If this is not possible + /// the positions (Pos) are invalidated. + bool advance(); - /// Try to advance one of the underlying positions (Head or Tail). + /// The explorer that can be used to explore the context further if an end is + /// found. If none is given the iterator will only traverse the + /// existing/cached context otherwise the explorer is used to explore further. /// - /// \return The next instruction in the must be executed context, or nullptr - /// if none was found. - const Instruction *advance(); - - /// A set to track the visited instructions in order to deal with endless - /// loops and recursion. - VisitedSetTy Visited; - - /// A reference to the explorer that created this iterator. - ExplorerTy &Explorer; + /// TODO: Determine if we should pass the explorer where needed. + MustBeExecutedContextExplorer *Explorer = nullptr; - /// The instruction we are currently exposing to the user. There is always an - /// instruction that we know is executed with the given program point, - /// initially the program point itself. - const Instruction *CurInst; - - /// Two positions that mark the program points where this iterator will look - /// for the next instruction. Note that the current instruction is either the - /// one pointed to by Head, Tail, or both. - const Instruction *Head, *Tail; + /// Two interval positions that mark the program points where this iterator + /// will look for the next instruction. Note that the current instruction is + /// the one pointed to by Pos[0]. Once Pos[0] is explored to the fullest and + /// becomes invalid we swap the two positions. If both positions are invalid + /// the iterator traversed the entire context. + MustBeExecutedInterval::Position Pos[2]; friend struct MustBeExecutedContextExplorer; }; @@ -393,6 +698,7 @@ /// the expected use case involves few iterators for "far apart" instructions. /// If that changes, we should consider caching more intermediate results. struct MustBeExecutedContextExplorer { + using IntervalPosition = MustBeExecutedInterval::Position; /// In the description of the parameters we use PP to denote a program point /// for which the must be executed context is explored, or put differently, @@ -418,12 +724,7 @@ : ExploreInterBlock(ExploreInterBlock), ExploreCFGForward(ExploreCFGForward), ExploreCFGBackward(ExploreCFGBackward), LIGetter(LIGetter), - DTGetter(DTGetter), PDTGetter(PDTGetter), EndIterator(*this, nullptr) {} - - /// Clean up the dynamically allocated iterators. - ~MustBeExecutedContextExplorer() { - DeleteContainerSeconds(InstructionIteratorMap); - } + DTGetter(DTGetter), PDTGetter(PDTGetter) {} /// Iterator-based interface. \see MustBeExecutedIterator. ///{ @@ -431,35 +732,39 @@ using const_iterator = const MustBeExecutedIterator; /// Return an iterator to explore the context around \p PP. - iterator &begin(const Instruction *PP) { - auto *&It = InstructionIteratorMap[PP]; - if (!It) - It = new iterator(*this, PP); - return *It; + iterator begin(const Instruction &PP) { + return iterator( + getOrCreateIntervalPosition(PP, ExplorationDirection::FORWARD), + getOrCreateIntervalPosition(PP, ExplorationDirection::BACKWARD), this); } /// Return an iterator to explore the cached context around \p PP. - const_iterator &begin(const Instruction *PP) const { - return *InstructionIteratorMap.lookup(PP); + const_iterator cached_begin(const Instruction &PP) const { + return iterator(lookupIntervalPosition(PP, ExplorationDirection::FORWARD), + lookupIntervalPosition(PP, ExplorationDirection::BACKWARD), + nullptr); } /// Return an universal end iterator. ///{ - iterator &end() { return EndIterator; } - iterator &end(const Instruction *) { return EndIterator; } + iterator end() { return iterator(); } + iterator end(const Instruction &) { return iterator(); } - const_iterator &end() const { return EndIterator; } - const_iterator &end(const Instruction *) const { return EndIterator; } + const_iterator cached_end() const { return const_iterator(); } + const_iterator cached_end(const Instruction &) const { + return const_iterator(); + } ///} /// Return an iterator range to explore the context around \p PP. - llvm::iterator_range range(const Instruction *PP) { + llvm::iterator_range range(const Instruction &PP) { return llvm::make_range(begin(PP), end(PP)); } /// Return an iterator range to explore the cached context around \p PP. - llvm::iterator_range range(const Instruction *PP) const { - return llvm::make_range(begin(PP), end(PP)); + llvm::iterator_range + cached_range(const Instruction &PP) const { + return llvm::make_range(cached_begin(PP), cached_end(PP)); } ///} @@ -467,56 +772,52 @@ /// /// This method will evaluate \p Pred and return /// true if \p Pred holds in every instruction. - bool checkForAllContext(const Instruction *PP, - function_ref Pred) { - for (auto EIt = begin(PP), EEnd = end(PP); EIt != EEnd; ++EIt) - if (!Pred(*EIt)) - return false; - return true; - } - - /// Helper to look for \p I in the context of \p PP. /// - /// The context is expanded until \p I was found or no more expansion is - /// possible. - /// - /// \returns True, iff \p I was found. - bool findInContextOf(const Instruction *I, const Instruction *PP) { - auto EIt = begin(PP), EEnd = end(PP); - return findInContextOf(I, EIt, EEnd); + ///{ + bool checkForAllInContext(const Instruction &PP, + function_ref Pred) { + return llvm::all_of(range(PP), Pred); + } + bool + checkForCachedInContext(const Instruction &PP, + function_ref Pred) const { + return llvm::all_of(cached_range(PP), Pred); } + ///} - /// Helper to look for \p I in the context defined by \p EIt and \p EEnd. + /// Helper to look for \p I in the context of \p PP. /// - /// The context is expanded until \p I was found or no more expansion is - /// possible. + /// In the non-const variant the context is expanded until \p I was found or + /// no more expansion is possible. If a dominator tree getter was provided it + /// is used to circumvent the search. /// /// \returns True, iff \p I was found. - bool findInContextOf(const Instruction *I, iterator &EIt, iterator &EEnd) { - bool Found = EIt.count(I); - while (!Found && EIt != EEnd) - Found = (++EIt).getCurrentInst() == I; - return Found; + bool findInContextOf(const Instruction &I, const Instruction &PP) { + const DominatorTree *DT = DTGetter(*I.getFunction()); + if (DT && DT->dominates(&I, &PP)) + return true; + return begin(PP).isExecutedWith(I); } /// Return the next instruction that is guaranteed to be executed after \p PP. /// - /// \param It The iterator that is used to traverse the must be - /// executed context. /// \param PP The program point for which the next instruction /// that is guaranteed to execute is determined. - const Instruction * - getMustBeExecutedNextInstruction(MustBeExecutedIterator &It, - const Instruction *PP); + const Instruction *getMustBeExecutedNextInstruction(const Instruction &PP) { + const IntervalPosition &Pos = + getOrCreateIntervalPosition(PP, ExplorationDirection::FORWARD); + return (++iterator(Pos, IntervalPosition(), this)).getCurrentInst(); + } + /// Return the previous instr. that is guaranteed to be executed before \p PP. /// - /// \param It The iterator that is used to traverse the must be - /// executed context. /// \param PP The program point for which the previous instr. /// that is guaranteed to execute is determined. - const Instruction * - getMustBeExecutedPrevInstruction(MustBeExecutedIterator &It, - const Instruction *PP); + const Instruction *getMustBeExecutedPrevInstruction(const Instruction &PP) { + const IntervalPosition &Pos = + getOrCreateIntervalPosition(PP, ExplorationDirection::FORWARD); + return (++iterator(Pos, IntervalPosition(), this)).getCurrentInst(); + } /// Find the next join point from \p InitBB in forward direction. const BasicBlock *findForwardJoinPoint(const BasicBlock *InitBB); @@ -532,7 +833,48 @@ const bool ExploreCFGBackward; ///} + /// Return the next position that is guaranteed to be executed (at some + /// point but for sure) after \p P in the direction of the underlying + /// interval. If none is known returns an invalid position. Note that \p P has + /// to be a valid position. + IntervalPosition exploreNextPosition(const IntervalPosition &P); + private: + /// Return an instruction that is known to be executed after \p PP. + const Instruction *exploreNextExecutedInstruction(const Instruction &PP); + + /// Return an instruction that is known to be executed before \p PP. + const Instruction *explorePrevExecutedInstruction(const Instruction &PP); + + /// Lookup the interval position for the instruction \p PP. + IntervalPosition lookupIntervalPosition(const Instruction &PP, + ExplorationDirection Dir) const { + return InstPositionMap[unsigned(Dir)].lookup(&PP); + } + + /// Lookup or create a new interval position for the instruction \p PP. + /// + /// If \p PP was explored before, its interval position already exists and it + /// is returned. If \p PP was not explored before, we create a new interval + /// for it and make \p PP the center of the interval, thus the position at + /// offset 0. The new position is cached. + /// + /// \returns A position for which the current instruction is \p PP. + IntervalPosition getOrCreateIntervalPosition(const Instruction &PP, + ExplorationDirection Dir) { + IntervalPosition &Pos = InstPositionMap[unsigned(Dir)][&PP]; + + if (!Pos) { + MustBeExecutedInterval *Interval = + new (Allocator) MustBeExecutedInterval(PP, Dir); + Pos = IntervalPosition(Interval); + } + + assert(Pos.getInstruction() == &PP && + "Unexpected instruction at position!"); + return Pos; + } + /// Getters for common CFG analyses: LoopInfo, DominatorTree, and /// PostDominatorTree. ///{ @@ -541,18 +883,14 @@ GetterTy PDTGetter; ///} - /// Map to cache isGuaranteedToTransferExecutionToSuccessor results. - DenseMap> BlockTransferMap; - /// Map to cache containsIrreducibleCFG results. - DenseMap> IrreducibleControlMap; + DenseMap> IrreducibleControlMap; - /// Map from instructions to associated must be executed iterators. - DenseMap - InstructionIteratorMap; + /// Two map from instructions to associated positions, one for each direction. + DenseMap InstPositionMap[2]; - /// A unique end iterator. - MustBeExecutedIterator EndIterator; + /// The allocator used to allocate memory, e.g. for intervals. + BumpPtrAllocator Allocator; }; } // namespace llvm diff --git a/llvm/lib/Analysis/MustExecute.cpp b/llvm/lib/Analysis/MustExecute.cpp --- a/llvm/lib/Analysis/MustExecute.cpp +++ b/llvm/lib/Analysis/MustExecute.cpp @@ -386,7 +386,7 @@ for (Function &F : M) { for (Instruction &I : instructions(F)) { dbgs() << "-- Explore context of: " << I << "\n"; - for (const Instruction *CI : Explorer.range(&I)) + for (const Instruction *CI : Explorer.range(I)) dbgs() << " [F: " << CI->getFunction()->getName() << "] " << *CI << "\n"; } @@ -597,10 +597,6 @@ // for futher checks. if (!F.hasFnAttribute(Attribute::WillReturn) || !F.doesNotThrow()) { - auto BlockTransfersExecutionToSuccessor = [](const BasicBlock *BB) { - return isGuaranteedToTransferExecutionToSuccessor(BB); - }; - SmallPtrSet Visited; while (!Worklist.empty()) { const BasicBlock *ToBB = Worklist.pop_back_val(); @@ -628,8 +624,7 @@ // Make sure the block has no instructions that could stop control // transfer. - bool TransfersExecution = getOrCreateCachedOptional( - ToBB, BlockTransferMap, BlockTransfersExecutionToSuccessor, ToBB); + bool TransfersExecution = isGuaranteedToTransferExecutionToSuccessor(ToBB); if (!TransfersExecution) return nullptr; @@ -641,6 +636,7 @@ LLVM_DEBUG(dbgs() << "\tJoin block: " << JoinBB->getName() << "\n"); return JoinBB; } + const BasicBlock * MustBeExecutedContextExplorer::findBackwardJoinPoint(const BasicBlock *InitBB) { const LoopInfo *LI = LIGetter(*InitBB->getParent()); @@ -709,14 +705,12 @@ } const Instruction * -MustBeExecutedContextExplorer::getMustBeExecutedNextInstruction( - MustBeExecutedIterator &It, const Instruction *PP) { - if (!PP) - return PP; - LLVM_DEBUG(dbgs() << "Find next instruction for " << *PP << "\n"); +MustBeExecutedContextExplorer::exploreNextExecutedInstruction( + const Instruction &PP) { + LLVM_DEBUG(dbgs() << "Find next instruction for " << PP << "\n"); // If we explore only inside a given basic block we stop at terminators. - if (!ExploreInterBlock && PP->isTerminator()) { + if (!ExploreInterBlock && PP.isTerminator()) { LLVM_DEBUG(dbgs() << "\tReached terminator in intra-block mode, done\n"); return nullptr; } @@ -724,7 +718,7 @@ // If we do not traverse the call graph we check if we can make progress in // the current function. First, check if the instruction is guaranteed to // transfer execution to the successor. - bool TransfersExecution = isGuaranteedToTransferExecutionToSuccessor(PP); + bool TransfersExecution = isGuaranteedToTransferExecutionToSuccessor(&PP); if (!TransfersExecution) return nullptr; @@ -732,33 +726,36 @@ // after this one that is executed next if control is transfered. If not, // we can try to go back to a call site we entered earlier. If none exists, we // do not know any instruction that has to be executd next. - if (!PP->isTerminator()) { - const Instruction *NextPP = PP->getNextNode(); - LLVM_DEBUG(dbgs() << "\tIntermediate instruction does transfer control\n"); + if (!PP.isTerminator()) { + const Instruction *NextPP = PP.getNextNode(); + LLVM_DEBUG(dbgs() << "\tIntermediate instruction does transfer control: " + << *NextPP << "\n"); return NextPP; } // Finally, we have to handle terminators, trivial ones first. - assert(PP->isTerminator() && "Expected a terminator!"); + assert(PP.isTerminator() && "Expected a terminator!"); // A terminator without a successor is not handled yet. - if (PP->getNumSuccessors() == 0) { + unsigned NumSuccBBs = PP.getNumSuccessors(); + if (NumSuccBBs == 0) { LLVM_DEBUG(dbgs() << "\tUnhandled terminator\n"); return nullptr; } // A terminator with a single successor, we will continue at the beginning of // that one. - if (PP->getNumSuccessors() == 1) { - LLVM_DEBUG( - dbgs() << "\tUnconditional terminator, continue with successor\n"); - return &PP->getSuccessor(0)->front(); + if (NumSuccBBs == 1) { + const Instruction *NextPP = &PP.getSuccessor(0)->front(); + LLVM_DEBUG(dbgs() << "\tUnconditional terminator, continue with successor: " + << *NextPP << "\n"); + return NextPP; } // Multiple successors mean we need to find the join point where control flow // converges again. We use the findForwardJoinPoint helper function with // information about the function and helper analyses, if available. - if (const BasicBlock *JoinBB = findForwardJoinPoint(PP->getParent())) + if (const BasicBlock *JoinBB = findForwardJoinPoint(PP.getParent())) return &JoinBB->front(); LLVM_DEBUG(dbgs() << "\tNo join point found\n"); @@ -766,32 +763,28 @@ } const Instruction * -MustBeExecutedContextExplorer::getMustBeExecutedPrevInstruction( - MustBeExecutedIterator &It, const Instruction *PP) { - if (!PP) - return PP; +MustBeExecutedContextExplorer::explorePrevExecutedInstruction( + const Instruction &PP) { - bool IsFirst = !(PP->getPrevNode()); - LLVM_DEBUG(dbgs() << "Find next instruction for " << *PP - << (IsFirst ? " [IsFirst]" : "") << "\n"); + const Instruction *PrevPP = PP.getPrevNode(); + LLVM_DEBUG(dbgs() << "Find previous instruction for " << PP + << (!PrevPP ? " [IsFirst]" : "") << "\n"); // If we explore only inside a given basic block we stop at the first // instruction. - if (!ExploreInterBlock && IsFirst) { + if (!ExploreInterBlock && !PrevPP) { LLVM_DEBUG(dbgs() << "\tReached block front in intra-block mode, done\n"); return nullptr; } // The block and function that contains the current position. - const BasicBlock *PPBlock = PP->getParent(); + const BasicBlock *PPBlock = PP.getParent(); // If we are inside a block we know what instruction was executed before, the // previous one. - if (!IsFirst) { - const Instruction *PrevPP = PP->getPrevNode(); - LLVM_DEBUG( - dbgs() << "\tIntermediate instruction, continue with previous\n"); - // We did not enter a callee so we simply return the previous instruction. + if (PrevPP) { + LLVM_DEBUG(dbgs() << "\tIntermediate instruction, continue with previous: " + << *PrevPP << "\n"); return PrevPP; } @@ -806,38 +799,79 @@ return nullptr; } -MustBeExecutedIterator::MustBeExecutedIterator( - MustBeExecutedContextExplorer &Explorer, const Instruction *I) - : Explorer(Explorer), CurInst(I) { - reset(I); -} +MustBeExecutedContextExplorer::IntervalPosition +MustBeExecutedContextExplorer::exploreNextPosition(const IntervalPosition &P) { + assert(P.getInterval() && P.getInstruction() && "Unexpected position state!"); + + assert(!(++IntervalPosition(P)) && + "Exploration called on already explored interval"); + + MustBeExecutedInterval &Interval = *P.getInterval(); + assert(!Interval.getNextInterval() && + "Exploration called on already explored interval"); + if (Interval.isFinalized()) + return IntervalPosition(); + + const Instruction *NewI = nullptr; + ExplorationDirection Dir = Interval.getDirection(); + if (Dir == ExplorationDirection::FORWARD) + NewI = exploreNextExecutedInstruction(*P.getInstruction()); + else + NewI = explorePrevExecutedInstruction(*P.getInstruction()); + + if (NewI) { + // We found an instruction executed after/before the given position P. If + // the instruction is not part of an interval yet we add it to the one of + // the position P, otherwise the one of the position Pis linked to the + // position of the instruction executed after/before. + IntervalPosition &NewIPos = InstPositionMap[unsigned(Dir)][NewI]; + if (!NewIPos && Interval.extend(*NewI)) { + NewIPos = P; + return ++NewIPos; + } -void MustBeExecutedIterator::reset(const Instruction *I) { - Visited.clear(); - resetInstruction(I); -} + if (NewIPos && Interval.setPosInNextInterval(NewIPos)) + return NewIPos; + } -void MustBeExecutedIterator::resetInstruction(const Instruction *I) { - CurInst = I; - Head = Tail = nullptr; - Visited.insert({I, ExplorationDirection::FORWARD}); - Visited.insert({I, ExplorationDirection::BACKWARD}); - if (Explorer.ExploreCFGForward) - Head = I; - if (Explorer.ExploreCFGBackward) - Tail = I; + // We failed to extend the interval so we finalize it and never try again. + Interval.finalize(); + return IntervalPosition(); } -const Instruction *MustBeExecutedIterator::advance() { - assert(CurInst && "Cannot advance an end iterator!"); - Head = Explorer.getMustBeExecutedNextInstruction(*this, Head); - if (Head && Visited.insert({Head, ExplorationDirection ::FORWARD}).second) - return Head; - Head = nullptr; +bool MustBeExecutedIterator::advance() { + if (!Pos[0]) { + assert(!Pos[1] && "Unexpected iterator state!"); + return false; + } - Tail = Explorer.getMustBeExecutedPrevInstruction(*this, Tail); - if (Tail && Visited.insert({Tail, ExplorationDirection ::BACKWARD}).second) - return Tail; - Tail = nullptr; - return nullptr; + // First, check if we explored a new position already. We have to be careful + // not to forget the old position if we cannot advance it. + MustBeExecutedInterval::Position Tmp = Pos[0]; + if (++Tmp) { + Pos[0] = Tmp; + return true; + } + + // We reached the boundaries of the known underlying interval and need to + // explore further. Note that exploration can fail, e.g., there is no known + // "next" instruction. If it does succeed, the interval is either extended + // or linked to another one by the explorer. In either case we need to + // advance to the new position. + if (Explorer) + if ((Pos[0] = Explorer->exploreNextPosition(Pos[0]))) + return true; + + assert(!Pos[0] && "Inconsistent state!"); + std::swap(Pos[0], Pos[1]); + return advance(); +} + +bool MustBeExecutedIterator::isExecutedWith(const Instruction &I) const { + auto Tmp = *this; + do { + if (Tmp.getCurrentInst() == &I) + return true; + } while (Tmp.advance()); + return false; } diff --git a/llvm/lib/Transforms/IPO/Attributor.cpp b/llvm/lib/Transforms/IPO/Attributor.cpp --- a/llvm/lib/Transforms/IPO/Attributor.cpp +++ b/llvm/lib/Transforms/IPO/Attributor.cpp @@ -398,9 +398,9 @@ unsigned AttrsSize = Attrs.size(); MustBeExecutedContextExplorer &Explorer = A.getInfoCache().getMustBeExecutedContextExplorer(); - auto EIt = Explorer.begin(getCtxI()), EEnd = Explorer.end(getCtxI()); + Instruction &CtxI = *getCtxI(); for (auto &It : A2K) - if (Explorer.findInContextOf(It.first, EIt, EEnd)) + if (Explorer.findInContextOf(*It.first, CtxI)) Attrs.push_back(Attribute::get(Ctx, AK, It.second.Max)); return AttrsSize != Attrs.size(); } diff --git a/llvm/lib/Transforms/IPO/AttributorAttributes.cpp b/llvm/lib/Transforms/IPO/AttributorAttributes.cpp --- a/llvm/lib/Transforms/IPO/AttributorAttributes.cpp +++ b/llvm/lib/Transforms/IPO/AttributorAttributes.cpp @@ -599,7 +599,7 @@ // } // } - Explorer.checkForAllContext(CtxI, Pred); + Explorer.checkForAllInContext(*CtxI, Pred); for (const BranchInst *Br : BrInsts) { StateType ParentState; @@ -641,11 +641,10 @@ MustBeExecutedContextExplorer &Explorer, const Instruction *CtxI, SetVector &Uses, StateType &State) { - auto EIt = Explorer.begin(CtxI), EEnd = Explorer.end(CtxI); for (unsigned u = 0; u < Uses.size(); ++u) { const Use *U = Uses[u]; if (const Instruction *UserI = dyn_cast(U->getUser())) { - bool Found = Explorer.findInContextOf(UserI, EIt, EEnd); + bool Found = Explorer.findInContextOf(*UserI, *CtxI); if (Found && Base::followUse(A, U, UserI, State)) for (const Use &Us : UserI->uses()) Uses.insert(&Us); @@ -4710,7 +4709,7 @@ if (Frees.size() != 1) return false; Instruction *UniqueFree = *Frees.begin(); - return Explorer.findInContextOf(UniqueFree, I.getNextNode()); + return Explorer.findInContextOf(*UniqueFree, *I.getNextNode()); }; auto UsesCheck = [&](Instruction &I) {