summaryrefslogtreecommitdiff
path: root/contrib/llvm-project/llvm/lib/Analysis/MustExecute.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'contrib/llvm-project/llvm/lib/Analysis/MustExecute.cpp')
-rw-r--r--contrib/llvm-project/llvm/lib/Analysis/MustExecute.cpp314
1 files changed, 314 insertions, 0 deletions
diff --git a/contrib/llvm-project/llvm/lib/Analysis/MustExecute.cpp b/contrib/llvm-project/llvm/lib/Analysis/MustExecute.cpp
index b616cd6f762b..952c2cbfec4e 100644
--- a/contrib/llvm-project/llvm/lib/Analysis/MustExecute.cpp
+++ b/contrib/llvm-project/llvm/lib/Analysis/MustExecute.cpp
@@ -7,20 +7,27 @@
//===----------------------------------------------------------------------===//
#include "llvm/Analysis/MustExecute.h"
+#include "llvm/ADT/PostOrderIterator.h"
+#include "llvm/Analysis/CFG.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/Passes.h"
+#include "llvm/Analysis/PostDominators.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/AssemblyAnnotationWriter.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/InstIterator.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/Module.h"
+#include "llvm/InitializePasses.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/FormattedStream.h"
#include "llvm/Support/raw_ostream.h"
+
using namespace llvm;
+#define DEBUG_TYPE "must-execute"
+
const DenseMap<BasicBlock *, ColorVector> &
LoopSafetyInfo::getBlockColors() const {
return BlockColors;
@@ -306,6 +313,17 @@ namespace {
}
bool runOnFunction(Function &F) override;
};
+ struct MustBeExecutedContextPrinter : public ModulePass {
+ static char ID;
+
+ MustBeExecutedContextPrinter() : ModulePass(ID) {
+ initializeMustBeExecutedContextPrinterPass(*PassRegistry::getPassRegistry());
+ }
+ void getAnalysisUsage(AnalysisUsage &AU) const override {
+ AU.setPreservesAll();
+ }
+ bool runOnModule(Module &M) override;
+ };
}
char MustExecutePrinter::ID = 0;
@@ -320,6 +338,57 @@ FunctionPass *llvm::createMustExecutePrinter() {
return new MustExecutePrinter();
}
+char MustBeExecutedContextPrinter::ID = 0;
+INITIALIZE_PASS_BEGIN(
+ MustBeExecutedContextPrinter, "print-must-be-executed-contexts",
+ "print the must-be-executed-contexed for all instructions", false, true)
+INITIALIZE_PASS_DEPENDENCY(PostDominatorTreeWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
+INITIALIZE_PASS_END(MustBeExecutedContextPrinter,
+ "print-must-be-executed-contexts",
+ "print the must-be-executed-contexed for all instructions",
+ false, true)
+
+ModulePass *llvm::createMustBeExecutedContextPrinter() {
+ return new MustBeExecutedContextPrinter();
+}
+
+bool MustBeExecutedContextPrinter::runOnModule(Module &M) {
+ // We provide non-PM analysis here because the old PM doesn't like to query
+ // function passes from a module pass.
+ SmallVector<PostDominatorTree *, 8> PDTs;
+ SmallVector<DominatorTree *, 8> DTs;
+ SmallVector<LoopInfo *, 8> LIs;
+
+ GetterTy<LoopInfo> LIGetter = [&](const Function &F) {
+ DominatorTree *DT = new DominatorTree(const_cast<Function &>(F));
+ LoopInfo *LI = new LoopInfo(*DT);
+ DTs.push_back(DT);
+ LIs.push_back(LI);
+ return LI;
+ };
+ GetterTy<PostDominatorTree> PDTGetter = [&](const Function &F) {
+ PostDominatorTree *PDT = new PostDominatorTree(const_cast<Function &>(F));
+ PDTs.push_back(PDT);
+ return PDT;
+ };
+ MustBeExecutedContextExplorer Explorer(true, LIGetter, PDTGetter);
+ for (Function &F : M) {
+ for (Instruction &I : instructions(F)) {
+ dbgs() << "-- Explore context of: " << I << "\n";
+ for (const Instruction *CI : Explorer.range(&I))
+ dbgs() << " [F: " << CI->getFunction()->getName() << "] " << *CI
+ << "\n";
+ }
+ }
+
+ DeleteContainerPointers(PDTs);
+ DeleteContainerPointers(LIs);
+ DeleteContainerPointers(DTs);
+ return false;
+}
+
static bool isMustExecuteIn(const Instruction &I, Loop *L, DominatorTree *DT) {
// TODO: merge these two routines. For the moment, we display the best
// result obtained by *either* implementation. This is a bit unfair since no
@@ -396,3 +465,248 @@ bool MustExecutePrinter::runOnFunction(Function &F) {
return false;
}
+
+/// Return true if \p L might be an endless loop.
+static bool maybeEndlessLoop(const Loop &L) {
+ if (L.getHeader()->getParent()->hasFnAttribute(Attribute::WillReturn))
+ return false;
+ // TODO: Actually try to prove it is not.
+ // TODO: If maybeEndlessLoop is going to be expensive, cache it.
+ return true;
+}
+
+static bool mayContainIrreducibleControl(const Function &F, const LoopInfo *LI) {
+ if (!LI)
+ return false;
+ using RPOTraversal = ReversePostOrderTraversal<const Function *>;
+ RPOTraversal FuncRPOT(&F);
+ return !containsIrreducibleCFG<const BasicBlock *, const RPOTraversal,
+ const LoopInfo>(FuncRPOT, *LI);
+}
+
+/// Lookup \p Key in \p Map and return the result, potentially after
+/// initializing the optional through \p Fn(\p args).
+template <typename K, typename V, typename FnTy, typename... ArgsTy>
+static V getOrCreateCachedOptional(K Key, DenseMap<K, Optional<V>> &Map,
+ FnTy &&Fn, ArgsTy&&... args) {
+ Optional<V> &OptVal = Map[Key];
+ if (!OptVal.hasValue())
+ OptVal = Fn(std::forward<ArgsTy>(args)...);
+ return OptVal.getValue();
+}
+
+const BasicBlock *
+MustBeExecutedContextExplorer::findForwardJoinPoint(const BasicBlock *InitBB) {
+ const LoopInfo *LI = LIGetter(*InitBB->getParent());
+ const PostDominatorTree *PDT = PDTGetter(*InitBB->getParent());
+
+ LLVM_DEBUG(dbgs() << "\tFind forward join point for " << InitBB->getName()
+ << (LI ? " [LI]" : "") << (PDT ? " [PDT]" : ""));
+
+ const Function &F = *InitBB->getParent();
+ const Loop *L = LI ? LI->getLoopFor(InitBB) : nullptr;
+ const BasicBlock *HeaderBB = L ? L->getHeader() : InitBB;
+ bool WillReturnAndNoThrow = (F.hasFnAttribute(Attribute::WillReturn) ||
+ (L && !maybeEndlessLoop(*L))) &&
+ F.doesNotThrow();
+ LLVM_DEBUG(dbgs() << (L ? " [in loop]" : "")
+ << (WillReturnAndNoThrow ? " [WillReturn] [NoUnwind]" : "")
+ << "\n");
+
+ // Determine the adjacent blocks in the given direction but exclude (self)
+ // loops under certain circumstances.
+ SmallVector<const BasicBlock *, 8> Worklist;
+ for (const BasicBlock *SuccBB : successors(InitBB)) {
+ bool IsLatch = SuccBB == HeaderBB;
+ // Loop latches are ignored in forward propagation if the loop cannot be
+ // endless and may not throw: control has to go somewhere.
+ if (!WillReturnAndNoThrow || !IsLatch)
+ Worklist.push_back(SuccBB);
+ }
+ LLVM_DEBUG(dbgs() << "\t\t#Worklist: " << Worklist.size() << "\n");
+
+ // If there are no other adjacent blocks, there is no join point.
+ if (Worklist.empty())
+ return nullptr;
+
+ // If there is one adjacent block, it is the join point.
+ if (Worklist.size() == 1)
+ return Worklist[0];
+
+ // Try to determine a join block through the help of the post-dominance
+ // tree. If no tree was provided, we perform simple pattern matching for one
+ // block conditionals and one block loops only.
+ const BasicBlock *JoinBB = nullptr;
+ if (PDT)
+ if (const auto *InitNode = PDT->getNode(InitBB))
+ if (const auto *IDomNode = InitNode->getIDom())
+ JoinBB = IDomNode->getBlock();
+
+ if (!JoinBB && Worklist.size() == 2) {
+ const BasicBlock *Succ0 = Worklist[0];
+ const BasicBlock *Succ1 = Worklist[1];
+ const BasicBlock *Succ0UniqueSucc = Succ0->getUniqueSuccessor();
+ const BasicBlock *Succ1UniqueSucc = Succ1->getUniqueSuccessor();
+ if (Succ0UniqueSucc == InitBB) {
+ // InitBB -> Succ0 -> InitBB
+ // InitBB -> Succ1 = JoinBB
+ JoinBB = Succ1;
+ } else if (Succ1UniqueSucc == InitBB) {
+ // InitBB -> Succ1 -> InitBB
+ // InitBB -> Succ0 = JoinBB
+ JoinBB = Succ0;
+ } else if (Succ0 == Succ1UniqueSucc) {
+ // InitBB -> Succ0 = JoinBB
+ // InitBB -> Succ1 -> Succ0 = JoinBB
+ JoinBB = Succ0;
+ } else if (Succ1 == Succ0UniqueSucc) {
+ // InitBB -> Succ0 -> Succ1 = JoinBB
+ // InitBB -> Succ1 = JoinBB
+ JoinBB = Succ1;
+ } else if (Succ0UniqueSucc == Succ1UniqueSucc) {
+ // InitBB -> Succ0 -> JoinBB
+ // InitBB -> Succ1 -> JoinBB
+ JoinBB = Succ0UniqueSucc;
+ }
+ }
+
+ if (!JoinBB && L)
+ JoinBB = L->getUniqueExitBlock();
+
+ if (!JoinBB)
+ return nullptr;
+
+ LLVM_DEBUG(dbgs() << "\t\tJoin block candidate: " << JoinBB->getName() << "\n");
+
+ // In forward direction we check if control will for sure reach JoinBB from
+ // InitBB, thus it can not be "stopped" along the way. Ways to "stop" control
+ // are: infinite loops and instructions that do not necessarily transfer
+ // execution to their successor. To check for them we traverse the CFG from
+ // the adjacent blocks to the JoinBB, looking at all intermediate blocks.
+
+ // If we know the function is "will-return" and "no-throw" there is no need
+ // for futher checks.
+ if (!F.hasFnAttribute(Attribute::WillReturn) || !F.doesNotThrow()) {
+
+ auto BlockTransfersExecutionToSuccessor = [](const BasicBlock *BB) {
+ return isGuaranteedToTransferExecutionToSuccessor(BB);
+ };
+
+ SmallPtrSet<const BasicBlock *, 16> Visited;
+ while (!Worklist.empty()) {
+ const BasicBlock *ToBB = Worklist.pop_back_val();
+ if (ToBB == JoinBB)
+ continue;
+
+ // Make sure all loops in-between are finite.
+ if (!Visited.insert(ToBB).second) {
+ if (!F.hasFnAttribute(Attribute::WillReturn)) {
+ if (!LI)
+ return nullptr;
+
+ bool MayContainIrreducibleControl = getOrCreateCachedOptional(
+ &F, IrreducibleControlMap, mayContainIrreducibleControl, F, LI);
+ if (MayContainIrreducibleControl)
+ return nullptr;
+
+ const Loop *L = LI->getLoopFor(ToBB);
+ if (L && maybeEndlessLoop(*L))
+ return nullptr;
+ }
+
+ continue;
+ }
+
+ // Make sure the block has no instructions that could stop control
+ // transfer.
+ bool TransfersExecution = getOrCreateCachedOptional(
+ ToBB, BlockTransferMap, BlockTransfersExecutionToSuccessor, ToBB);
+ if (!TransfersExecution)
+ return nullptr;
+
+ for (const BasicBlock *AdjacentBB : successors(ToBB))
+ Worklist.push_back(AdjacentBB);
+ }
+ }
+
+ LLVM_DEBUG(dbgs() << "\tJoin block: " << JoinBB->getName() << "\n");
+ return JoinBB;
+}
+
+const Instruction *
+MustBeExecutedContextExplorer::getMustBeExecutedNextInstruction(
+ MustBeExecutedIterator &It, const Instruction *PP) {
+ if (!PP)
+ return 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()) {
+ LLVM_DEBUG(dbgs() << "\tReached terminator in intra-block mode, done\n");
+ return nullptr;
+ }
+
+ // 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);
+ if (!TransfersExecution)
+ return nullptr;
+
+ // If this is not a terminator we know that there is a single instruction
+ // 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");
+ return NextPP;
+ }
+
+ // Finally, we have to handle terminators, trivial ones first.
+ assert(PP->isTerminator() && "Expected a terminator!");
+
+ // A terminator without a successor is not handled yet.
+ if (PP->getNumSuccessors() == 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();
+ }
+
+ // 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()))
+ return &JoinBB->front();
+
+ LLVM_DEBUG(dbgs() << "\tNo join point found\n");
+ return nullptr;
+}
+
+MustBeExecutedIterator::MustBeExecutedIterator(
+ MustBeExecutedContextExplorer &Explorer, const Instruction *I)
+ : Explorer(Explorer), CurInst(I) {
+ reset(I);
+}
+
+void MustBeExecutedIterator::reset(const Instruction *I) {
+ CurInst = I;
+ Visited.clear();
+ Visited.insert(I);
+}
+
+const Instruction *MustBeExecutedIterator::advance() {
+ assert(CurInst && "Cannot advance an end iterator!");
+ const Instruction *Next =
+ Explorer.getMustBeExecutedNextInstruction(*this, CurInst);
+ if (Next && !Visited.insert(Next).second)
+ Next = nullptr;
+ return Next;
+}
generated by cgit v1.2.3 (git 2.25.1) at 2025-12-08 22:09:13 +0000