Update prebuilt Clang to r416183b from Android.
https://android.googlesource.com/platform/prebuilts/clang/host/
linux-x86/+/06a71ddac05c22edb2d10b590e1769b3f8619bef
clang 12.0.5 (based on r416183b) from build 7284624.
Change-Id: I277a316abcf47307562d8b748b84870f31a72866
Signed-off-by: Olivier Deprez <olivier.deprez@arm.com>
diff --git a/linux-x64/clang/include/llvm/Analysis/MustExecute.h b/linux-x64/clang/include/llvm/Analysis/MustExecute.h
index 3ef539c..df489aa 100644
--- a/linux-x64/clang/include/llvm/Analysis/MustExecute.h
+++ b/linux-x64/clang/include/llvm/Analysis/MustExecute.h
@@ -7,33 +7,46 @@
//===----------------------------------------------------------------------===//
/// \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
+/// 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/Analysis/LoopInfo.h"
-#include "llvm/IR/BasicBlock.h"
-#include "llvm/IR/Dominators.h"
-#include "llvm/IR/Instruction.h"
+#include "llvm/IR/PassManager.h"
+#include "llvm/Support/raw_ostream.h"
namespace llvm {
-class Instruction;
+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 abnormaly on any iteration of the loop which might actually execute
-/// at runtime. The primary way to consume this infromation is via
+/// 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
@@ -100,19 +113,15 @@
bool HeaderMayThrow = false; // Same as previous, but specific to loop header
public:
- virtual bool blockMayThrow(const BasicBlock *BB) const;
+ bool blockMayThrow(const BasicBlock *BB) const override;
- virtual bool anyBlockMayThrow() const;
+ bool anyBlockMayThrow() const override;
- virtual void computeLoopSafetyInfo(const Loop *CurLoop);
+ void computeLoopSafetyInfo(const Loop *CurLoop) override;
- virtual bool isGuaranteedToExecute(const Instruction &Inst,
- const DominatorTree *DT,
- const Loop *CurLoop) const;
-
- SimpleLoopSafetyInfo() : LoopSafetyInfo() {};
-
- virtual ~SimpleLoopSafetyInfo() {};
+ bool isGuaranteedToExecute(const Instruction &Inst,
+ const DominatorTree *DT,
+ const Loop *CurLoop) const override;
};
/// This implementation of LoopSafetyInfo use ImplicitControlFlowTracking to
@@ -129,15 +138,15 @@
mutable MemoryWriteTracking MW;
public:
- virtual bool blockMayThrow(const BasicBlock *BB) const;
+ bool blockMayThrow(const BasicBlock *BB) const override;
- virtual bool anyBlockMayThrow() const;
+ bool anyBlockMayThrow() const override;
- virtual void computeLoopSafetyInfo(const Loop *CurLoop);
+ void computeLoopSafetyInfo(const Loop *CurLoop) override;
- virtual bool isGuaranteedToExecute(const Instruction &Inst,
- const DominatorTree *DT,
- const Loop *CurLoop) const;
+ 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.
@@ -158,12 +167,399 @@
/// from its block. It will make all cache updates to keep it correct after
/// this removal.
void removeInstruction(const Instruction *Inst);
-
- ICFLoopSafetyInfo(DominatorTree *DT) : LoopSafetyInfo(), ICF(DT), MW(DT) {};
-
- virtual ~ICFLoopSafetyInfo() {};
};
-}
+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