[MustExecute] Move isGuaranteedToExecute and related rourtines to Analysis
Next step is to actually merge the implementations and get both implementations tested through the new printer.
llvm-svn: 328055
diff --git a/llvm/lib/Transforms/Utils/LoopUtils.cpp b/llvm/lib/Transforms/Utils/LoopUtils.cpp
index 48b15ce..2f0fd42 100644
--- a/llvm/lib/Transforms/Utils/LoopUtils.cpp
+++ b/llvm/lib/Transforms/Utils/LoopUtils.cpp
@@ -19,6 +19,7 @@
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/LoopPass.h"
+#include "llvm/Analysis/MustExecute.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
#include "llvm/Analysis/ScalarEvolutionExpander.h"
@@ -1482,139 +1483,6 @@
}
}
-/// Computes loop safety information, checks loop body & header
-/// for the possibility of may throw exception.
-///
-void llvm::computeLoopSafetyInfo(LoopSafetyInfo *SafetyInfo, Loop *CurLoop) {
- assert(CurLoop != nullptr && "CurLoop cant be null");
- BasicBlock *Header = CurLoop->getHeader();
- // Setting default safety values.
- SafetyInfo->MayThrow = false;
- SafetyInfo->HeaderMayThrow = false;
- // Iterate over header and compute safety info.
- SafetyInfo->HeaderMayThrow =
- !isGuaranteedToTransferExecutionToSuccessor(Header);
-
- SafetyInfo->MayThrow = SafetyInfo->HeaderMayThrow;
- // Iterate over loop instructions and compute safety info.
- // Skip header as it has been computed and stored in HeaderMayThrow.
- // The first block in loopinfo.Blocks is guaranteed to be the header.
- assert(Header == *CurLoop->getBlocks().begin() &&
- "First block must be header");
- for (Loop::block_iterator BB = std::next(CurLoop->block_begin()),
- BBE = CurLoop->block_end();
- (BB != BBE) && !SafetyInfo->MayThrow; ++BB)
- SafetyInfo->MayThrow |=
- !isGuaranteedToTransferExecutionToSuccessor(*BB);
-
- // Compute funclet colors if we might sink/hoist in a function with a funclet
- // personality routine.
- Function *Fn = CurLoop->getHeader()->getParent();
- if (Fn->hasPersonalityFn())
- if (Constant *PersonalityFn = Fn->getPersonalityFn())
- if (isFuncletEHPersonality(classifyEHPersonality(PersonalityFn)))
- SafetyInfo->BlockColors = colorEHFunclets(*Fn);
-}
-
-/// Return true if we can prove that the given ExitBlock is not reached on the
-/// first iteration of the given loop. That is, the backedge of the loop must
-/// be executed before the ExitBlock is executed in any dynamic execution trace.
-static bool CanProveNotTakenFirstIteration(BasicBlock *ExitBlock,
- const DominatorTree *DT,
- const Loop *CurLoop) {
- auto *CondExitBlock = ExitBlock->getSinglePredecessor();
- if (!CondExitBlock)
- // expect unique exits
- return false;
- assert(CurLoop->contains(CondExitBlock) && "meaning of exit block");
- auto *BI = dyn_cast<BranchInst>(CondExitBlock->getTerminator());
- if (!BI || !BI->isConditional())
- return false;
- auto *Cond = dyn_cast<CmpInst>(BI->getCondition());
- if (!Cond)
- return false;
- // todo: this would be a lot more powerful if we used scev, but all the
- // plumbing is currently missing to pass a pointer in from the pass
- // Check for cmp (phi [x, preheader] ...), y where (pred x, y is known
- auto *LHS = dyn_cast<PHINode>(Cond->getOperand(0));
- auto *RHS = Cond->getOperand(1);
- if (!LHS || LHS->getParent() != CurLoop->getHeader())
- return false;
- auto DL = ExitBlock->getModule()->getDataLayout();
- auto *IVStart = LHS->getIncomingValueForBlock(CurLoop->getLoopPreheader());
- auto *SimpleValOrNull = SimplifyCmpInst(Cond->getPredicate(),
- IVStart, RHS,
- {DL, /*TLI*/ nullptr,
- DT, /*AC*/ nullptr, BI});
- auto *SimpleCst = dyn_cast_or_null<Constant>(SimpleValOrNull);
- if (!SimpleCst)
- return false;
- if (ExitBlock == BI->getSuccessor(0))
- return SimpleCst->isZeroValue();
- assert(ExitBlock == BI->getSuccessor(1) && "implied by above");
- return SimpleCst->isAllOnesValue();
-}
-
-/// Returns true if the instruction in a loop is guaranteed to execute at least
-/// once.
-bool llvm::isGuaranteedToExecute(const Instruction &Inst,
- const DominatorTree *DT, const Loop *CurLoop,
- const LoopSafetyInfo *SafetyInfo) {
- // We have to check to make sure that the instruction dominates all
- // of the exit blocks. If it doesn't, then there is a path out of the loop
- // which does not execute this instruction, so we can't hoist it.
-
- // If the instruction is in the header block for the loop (which is very
- // common), it is always guaranteed to dominate the exit blocks. Since this
- // is a common case, and can save some work, check it now.
- if (Inst.getParent() == CurLoop->getHeader())
- // If there's a throw in the header block, we can't guarantee we'll reach
- // Inst.
- return !SafetyInfo->HeaderMayThrow;
-
- // Somewhere in this loop there is an instruction which may throw and make us
- // exit the loop.
- if (SafetyInfo->MayThrow)
- return false;
-
- // Note: There are two styles of reasoning intermixed below for
- // implementation efficiency reasons. They are:
- // 1) If we can prove that the instruction dominates all exit blocks, then we
- // know the instruction must have executed on *some* iteration before we
- // exit. We do not prove *which* iteration the instruction must execute on.
- // 2) If we can prove that the instruction dominates the latch and all exits
- // which might be taken on the first iteration, we know the instruction must
- // execute on the first iteration. This second style allows a conditional
- // exit before the instruction of interest which is provably not taken on the
- // first iteration. This is a quite common case for range check like
- // patterns. TODO: support loops with multiple latches.
-
- const bool InstDominatesLatch =
- CurLoop->getLoopLatch() != nullptr &&
- DT->dominates(Inst.getParent(), CurLoop->getLoopLatch());
-
- // Get the exit blocks for the current loop.
- SmallVector<BasicBlock *, 8> ExitBlocks;
- CurLoop->getExitBlocks(ExitBlocks);
-
- // Verify that the block dominates each of the exit blocks of the loop.
- for (BasicBlock *ExitBlock : ExitBlocks)
- if (!DT->dominates(Inst.getParent(), ExitBlock))
- if (!InstDominatesLatch ||
- !CanProveNotTakenFirstIteration(ExitBlock, DT, CurLoop))
- return false;
-
- // As a degenerate case, if the loop is statically infinite then we haven't
- // proven anything since there are no exit blocks.
- if (ExitBlocks.empty())
- return false;
-
- // FIXME: In general, we have to prove that the loop isn't an infinite loop.
- // See http::llvm.org/PR24078 . (The "ExitBlocks.empty()" check above is
- // just a special case of this.)
- return true;
-}
-
Optional<unsigned> llvm::getLoopEstimatedTripCount(Loop *L) {
// Only support loops with a unique exiting block, and a latch.
if (!L->getExitingBlock())