| //===- MustExecute.h - Is an instruction known to execute--------*- C++ -*-===// |
| // |
| // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
| // See https://llvm.org/LICENSE.txt for license information. |
| // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
| // |
| //===----------------------------------------------------------------------===// |
| /// \file |
| /// Contains a collection of routines for determining if a given instruction is |
| /// guaranteed to execute if a given point in control flow is reached. The most |
| /// common example is an instruction within a loop being provably executed if we |
| /// branch to the header of it's containing loop. |
| /// |
| /// There are two interfaces available to determine if an instruction is |
| /// executed once a given point in the control flow is reached: |
| /// 1) A loop-centric one derived from LoopSafetyInfo. |
| /// 2) A "must be executed context"-based one implemented in the |
| /// MustBeExecutedContextExplorer. |
| /// Please refer to the class comments for more information. |
| /// |
| //===----------------------------------------------------------------------===// |
| |
| #ifndef LLVM_ANALYSIS_MUSTEXECUTE_H |
| #define LLVM_ANALYSIS_MUSTEXECUTE_H |
| |
| #include "llvm/ADT/DenseMap.h" |
| #include "llvm/ADT/DenseSet.h" |
| #include "llvm/Analysis/EHPersonalities.h" |
| #include "llvm/Analysis/InstructionPrecedenceTracking.h" |
| #include "llvm/IR/PassManager.h" |
| #include "llvm/Support/raw_ostream.h" |
| |
| namespace llvm { |
| |
| namespace { |
| template <typename T> using GetterTy = std::function<T *(const Function &F)>; |
| } |
| |
| class BasicBlock; |
| class DominatorTree; |
| class Instruction; |
| class Loop; |
| class LoopInfo; |
| class PostDominatorTree; |
| |
| /// Captures loop safety information. |
| /// It keep information for loop blocks may throw exception or otherwise |
| /// exit abnormally on any iteration of the loop which might actually execute |
| /// at runtime. The primary way to consume this information is via |
| /// isGuaranteedToExecute below, but some callers bailout or fallback to |
| /// alternate reasoning if a loop contains any implicit control flow. |
| /// NOTE: LoopSafetyInfo contains cached information regarding loops and their |
| /// particular blocks. This information is only dropped on invocation of |
| /// computeLoopSafetyInfo. If the loop or any of its block is deleted, or if |
| /// any thrower instructions have been added or removed from them, or if the |
| /// control flow has changed, or in case of other meaningful modifications, the |
| /// LoopSafetyInfo needs to be recomputed. If a meaningful modifications to the |
| /// loop were made and the info wasn't recomputed properly, the behavior of all |
| /// methods except for computeLoopSafetyInfo is undefined. |
| class LoopSafetyInfo { |
| // Used to update funclet bundle operands. |
| DenseMap<BasicBlock *, ColorVector> BlockColors; |
| |
| protected: |
| /// Computes block colors. |
| void computeBlockColors(const Loop *CurLoop); |
| |
| public: |
| /// Returns block colors map that is used to update funclet operand bundles. |
| const DenseMap<BasicBlock *, ColorVector> &getBlockColors() const; |
| |
| /// Copy colors of block \p Old into the block \p New. |
| void copyColors(BasicBlock *New, BasicBlock *Old); |
| |
| /// Returns true iff the block \p BB potentially may throw exception. It can |
| /// be false-positive in cases when we want to avoid complex analysis. |
| virtual bool blockMayThrow(const BasicBlock *BB) const = 0; |
| |
| /// Returns true iff any block of the loop for which this info is contains an |
| /// instruction that may throw or otherwise exit abnormally. |
| virtual bool anyBlockMayThrow() const = 0; |
| |
| /// Return true if we must reach the block \p BB under assumption that the |
| /// loop \p CurLoop is entered. |
| bool allLoopPathsLeadToBlock(const Loop *CurLoop, const BasicBlock *BB, |
| const DominatorTree *DT) const; |
| |
| /// Computes safety information for a loop checks loop body & header for |
| /// the possibility of may throw exception, it takes LoopSafetyInfo and loop |
| /// as argument. Updates safety information in LoopSafetyInfo argument. |
| /// Note: This is defined to clear and reinitialize an already initialized |
| /// LoopSafetyInfo. Some callers rely on this fact. |
| virtual void computeLoopSafetyInfo(const Loop *CurLoop) = 0; |
| |
| /// Returns true if the instruction in a loop is guaranteed to execute at |
| /// least once (under the assumption that the loop is entered). |
| virtual bool isGuaranteedToExecute(const Instruction &Inst, |
| const DominatorTree *DT, |
| const Loop *CurLoop) const = 0; |
| |
| LoopSafetyInfo() = default; |
| |
| virtual ~LoopSafetyInfo() = default; |
| }; |
| |
| |
| /// Simple and conservative implementation of LoopSafetyInfo that can give |
| /// false-positive answers to its queries in order to avoid complicated |
| /// analysis. |
| class SimpleLoopSafetyInfo: public LoopSafetyInfo { |
| bool MayThrow = false; // The current loop contains an instruction which |
| // may throw. |
| bool HeaderMayThrow = false; // Same as previous, but specific to loop header |
| |
| public: |
| bool blockMayThrow(const BasicBlock *BB) const override; |
| |
| bool anyBlockMayThrow() const override; |
| |
| void computeLoopSafetyInfo(const Loop *CurLoop) override; |
| |
| bool isGuaranteedToExecute(const Instruction &Inst, |
| const DominatorTree *DT, |
| const Loop *CurLoop) const override; |
| }; |
| |
| /// This implementation of LoopSafetyInfo use ImplicitControlFlowTracking to |
| /// give precise answers on "may throw" queries. This implementation uses cache |
| /// that should be invalidated by calling the methods insertInstructionTo and |
| /// removeInstruction whenever we modify a basic block's contents by adding or |
| /// removing instructions. |
| class ICFLoopSafetyInfo: public LoopSafetyInfo { |
| bool MayThrow = false; // The current loop contains an instruction which |
| // may throw. |
| // Contains information about implicit control flow in this loop's blocks. |
| mutable ImplicitControlFlowTracking ICF; |
| // Contains information about instruction that may possibly write memory. |
| mutable MemoryWriteTracking MW; |
| |
| public: |
| bool blockMayThrow(const BasicBlock *BB) const override; |
| |
| bool anyBlockMayThrow() const override; |
| |
| void computeLoopSafetyInfo(const Loop *CurLoop) override; |
| |
| bool isGuaranteedToExecute(const Instruction &Inst, |
| const DominatorTree *DT, |
| const Loop *CurLoop) const override; |
| |
| /// Returns true if we could not execute a memory-modifying instruction before |
| /// we enter \p BB under assumption that \p CurLoop is entered. |
| bool doesNotWriteMemoryBefore(const BasicBlock *BB, const Loop *CurLoop) |
| const; |
| |
| /// Returns true if we could not execute a memory-modifying instruction before |
| /// we execute \p I under assumption that \p CurLoop is entered. |
| bool doesNotWriteMemoryBefore(const Instruction &I, const Loop *CurLoop) |
| const; |
| |
| /// Inform the safety info that we are planning to insert a new instruction |
| /// \p Inst into the basic block \p BB. It will make all cache updates to keep |
| /// it correct after this insertion. |
| void insertInstructionTo(const Instruction *Inst, const BasicBlock *BB); |
| |
| /// Inform safety info that we are planning to remove the instruction \p Inst |
| /// from its block. It will make all cache updates to keep it correct after |
| /// this removal. |
| void removeInstruction(const Instruction *Inst); |
| }; |
| |
| bool mayContainIrreducibleControl(const Function &F, const LoopInfo *LI); |
| |
| struct MustBeExecutedContextExplorer; |
| |
| /// Enum that allows us to spell out the direction. |
| enum class ExplorationDirection { |
| BACKWARD = 0, |
| FORWARD = 1, |
| }; |
| |
| /// Must be executed iterators visit stretches of instructions that are |
| /// guaranteed to be executed together, potentially with other instruction |
| /// executed in-between. |
| /// |
| /// Given the following code, and assuming all statements are single |
| /// instructions which transfer execution to the successor (see |
| /// isGuaranteedToTransferExecutionToSuccessor), there are two possible |
| /// outcomes. If we start the iterator at A, B, or E, we will visit only A, B, |
| /// and E. If we start at C or D, we will visit all instructions A-E. |
| /// |
| /// \code |
| /// A; |
| /// B; |
| /// if (...) { |
| /// C; |
| /// D; |
| /// } |
| /// E; |
| /// \endcode |
| /// |
| /// |
| /// Below is the example extneded with instructions F and G. Now we assume F |
| /// might not transfer execution to it's successor G. As a result we get the |
| /// following visit sets: |
| /// |
| /// Start Instruction | Visit Set |
| /// A | A, B, E, F |
| /// B | A, B, E, F |
| /// C | A, B, C, D, E, F |
| /// D | A, B, C, D, E, F |
| /// E | A, B, E, F |
| /// F | A, B, E, F |
| /// G | A, B, E, F, G |
| /// |
| /// |
| /// \code |
| /// A; |
| /// B; |
| /// if (...) { |
| /// C; |
| /// D; |
| /// } |
| /// E; |
| /// F; // Might not transfer execution to its successor G. |
| /// G; |
| /// \endcode |
| /// |
| /// |
| /// 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 inner loop 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 |
| /// visist sets 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 |
| /// |
| /// Start Instruction | Visit Set |
| /// A | A, B |
| /// B | A, B |
| /// C | A, B, C |
| /// D | A, B, D |
| /// E | A, B, D, E, F |
| /// F | A, B, D, F |
| /// G | A, B, D, G |
| /// |
| /// |
| /// Note that the examples show optimal visist sets but not necessarily the ones |
| /// 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. |
| struct MustBeExecutedIterator { |
| /// Type declarations that make his class an input iterator. |
| ///{ |
| typedef const Instruction *value_type; |
| typedef std::ptrdiff_t difference_type; |
| typedef const Instruction **pointer; |
| typedef const Instruction *&reference; |
| 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. |
| ///{ |
| MustBeExecutedIterator &operator++() { |
| CurInst = advance(); |
| return *this; |
| } |
| |
| MustBeExecutedIterator operator++(int) { |
| MustBeExecutedIterator tmp(*this); |
| operator++(); |
| return tmp; |
| } |
| ///} |
| |
| /// 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; |
| } |
| |
| bool operator!=(const MustBeExecutedIterator &Other) const { |
| return !(*this == Other); |
| } |
| ///} |
| |
| /// Return the underlying instruction. |
| const Instruction *&operator*() { return CurInst; } |
| const Instruction *getCurrentInst() const { return CurInst; } |
| |
| /// 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}); |
| } |
| |
| private: |
| using VisitedSetTy = |
| DenseSet<PointerIntPair<const Instruction *, 1, ExplorationDirection>>; |
| |
| /// Private constructors. |
| MustBeExecutedIterator(ExplorerTy &Explorer, const Instruction *I); |
| |
| /// Reset the iterator to its initial state pointing at \p I. |
| void reset(const Instruction *I); |
| |
| /// Reset the iterator to point at \p I, keep cached state. |
| void resetInstruction(const Instruction *I); |
| |
| /// Try to advance one of the underlying positions (Head or Tail). |
| /// |
| /// \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; |
| |
| /// 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; |
| |
| friend struct MustBeExecutedContextExplorer; |
| }; |
| |
| /// A "must be executed context" for a given program point PP is the set of |
| /// instructions, potentially before and after PP, that are executed always when |
| /// PP is reached. The MustBeExecutedContextExplorer an interface to explore |
| /// "must be executed contexts" in a module through the use of |
| /// MustBeExecutedIterator. |
| /// |
| /// The explorer exposes "must be executed iterators" that traverse the must be |
| /// executed context. There is little information sharing between iterators as |
| /// the expected use case involves few iterators for "far apart" instructions. |
| /// If that changes, we should consider caching more intermediate results. |
| struct MustBeExecutedContextExplorer { |
| |
| /// 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, |
| /// for which the MustBeExecutedIterator is created. |
| /// |
| /// \param ExploreInterBlock Flag to indicate if instructions in blocks |
| /// other than the parent of PP should be |
| /// explored. |
| /// \param ExploreCFGForward Flag to indicate if instructions located after |
| /// PP in the CFG, e.g., post-dominating PP, |
| /// should be explored. |
| /// \param ExploreCFGBackward Flag to indicate if instructions located |
| /// before PP in the CFG, e.g., dominating PP, |
| /// should be explored. |
| MustBeExecutedContextExplorer( |
| bool ExploreInterBlock, bool ExploreCFGForward, bool ExploreCFGBackward, |
| GetterTy<const LoopInfo> LIGetter = |
| [](const Function &) { return nullptr; }, |
| GetterTy<const DominatorTree> DTGetter = |
| [](const Function &) { return nullptr; }, |
| GetterTy<const PostDominatorTree> PDTGetter = |
| [](const Function &) { return nullptr; }) |
| : ExploreInterBlock(ExploreInterBlock), |
| ExploreCFGForward(ExploreCFGForward), |
| ExploreCFGBackward(ExploreCFGBackward), LIGetter(LIGetter), |
| DTGetter(DTGetter), PDTGetter(PDTGetter), EndIterator(*this, nullptr) {} |
| |
| /// Iterator-based interface. \see MustBeExecutedIterator. |
| ///{ |
| using iterator = MustBeExecutedIterator; |
| 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.reset(new iterator(*this, PP)); |
| return *It; |
| } |
| |
| /// Return an iterator to explore the cached context around \p PP. |
| const_iterator &begin(const Instruction *PP) const { |
| return *InstructionIteratorMap.find(PP)->second; |
| } |
| |
| /// Return an universal end iterator. |
| ///{ |
| iterator &end() { return EndIterator; } |
| iterator &end(const Instruction *) { return EndIterator; } |
| |
| const_iterator &end() const { return EndIterator; } |
| const_iterator &end(const Instruction *) const { return EndIterator; } |
| ///} |
| |
| /// Return an iterator range to explore the context around \p PP. |
| llvm::iterator_range<iterator> 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<const_iterator> range(const Instruction *PP) const { |
| return llvm::make_range(begin(PP), end(PP)); |
| } |
| ///} |
| |
| /// Check \p Pred on all instructions in the context. |
| /// |
| /// This method will evaluate \p Pred and return |
| /// true if \p Pred holds in every instruction. |
| bool checkForAllContext(const Instruction *PP, |
| function_ref<bool(const Instruction *)> 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); |
| } |
| |
| /// Helper to look for \p I in the context defined by \p EIt and \p EEnd. |
| /// |
| /// 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, iterator &EIt, iterator &EEnd) { |
| bool Found = EIt.count(I); |
| while (!Found && EIt != EEnd) |
| Found = (++EIt).getCurrentInst() == I; |
| return Found; |
| } |
| |
| /// 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); |
| /// 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); |
| |
| /// Find the next join point from \p InitBB in forward direction. |
| const BasicBlock *findForwardJoinPoint(const BasicBlock *InitBB); |
| |
| /// Find the next join point from \p InitBB in backward direction. |
| const BasicBlock *findBackwardJoinPoint(const BasicBlock *InitBB); |
| |
| /// Parameter that limit the performed exploration. See the constructor for |
| /// their meaning. |
| ///{ |
| const bool ExploreInterBlock; |
| const bool ExploreCFGForward; |
| const bool ExploreCFGBackward; |
| ///} |
| |
| private: |
| /// Getters for common CFG analyses: LoopInfo, DominatorTree, and |
| /// PostDominatorTree. |
| ///{ |
| GetterTy<const LoopInfo> LIGetter; |
| GetterTy<const DominatorTree> DTGetter; |
| GetterTy<const PostDominatorTree> PDTGetter; |
| ///} |
| |
| /// Map to cache isGuaranteedToTransferExecutionToSuccessor results. |
| DenseMap<const BasicBlock *, Optional<bool>> BlockTransferMap; |
| |
| /// Map to cache containsIrreducibleCFG results. |
| DenseMap<const Function*, Optional<bool>> IrreducibleControlMap; |
| |
| /// Map from instructions to associated must be executed iterators. |
| DenseMap<const Instruction *, std::unique_ptr<MustBeExecutedIterator>> |
| InstructionIteratorMap; |
| |
| /// A unique end iterator. |
| MustBeExecutedIterator EndIterator; |
| }; |
| |
| class MustExecutePrinterPass : public PassInfoMixin<MustExecutePrinterPass> { |
| raw_ostream &OS; |
| |
| public: |
| MustExecutePrinterPass(raw_ostream &OS) : OS(OS) {} |
| PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); |
| }; |
| |
| class MustBeExecutedContextPrinterPass |
| : public PassInfoMixin<MustBeExecutedContextPrinterPass> { |
| raw_ostream &OS; |
| |
| public: |
| MustBeExecutedContextPrinterPass(raw_ostream &OS) : OS(OS) {} |
| PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM); |
| }; |
| |
| } // namespace llvm |
| |
| #endif |