From 23aed5ef6ff3518516688ac3c8768fdbc743563b Mon Sep 17 00:00:00 2001 From: Philip Reames Date: Tue, 20 Mar 2018 22:45:23 +0000 Subject: [PATCH] [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 --- llvm/include/llvm/Analysis/MustExecute.h | 57 +++++++++++ llvm/include/llvm/Transforms/Utils/LoopUtils.h | 25 +---- llvm/lib/Analysis/MustExecute.cpp | 135 +++++++++++++++++++++++++ llvm/lib/Transforms/Utils/LoopUtils.cpp | 134 +----------------------- 4 files changed, 195 insertions(+), 156 deletions(-) create mode 100644 llvm/include/llvm/Analysis/MustExecute.h diff --git a/llvm/include/llvm/Analysis/MustExecute.h b/llvm/include/llvm/Analysis/MustExecute.h new file mode 100644 index 0000000..c13fb79 --- /dev/null +++ b/llvm/include/llvm/Analysis/MustExecute.h @@ -0,0 +1,57 @@ +//===- MustExecute.h - Is an instruction known to execute--------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +/// \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. +/// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ANALYSIS_MUSTEXECUTE_H +#define LLVM_ANALYSIS_MUSTEXECUTE_H + +namespace llvm { + +class Instruction; +class DominatorTree; +class Loop; + +/// \brief Captures loop safety information. +/// It keep information for loop & its header 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 +/// isGuaranteedToExecute below, but some callers bailout or fallback to +/// alternate reasoning if a loop contains any implicit control flow. +struct LoopSafetyInfo { + bool MayThrow = false; // The current loop contains an instruction which + // may throw. + bool HeaderMayThrow = false; // Same as previous, but specific to loop header + // Used to update funclet bundle operands. + DenseMap BlockColors; + + LoopSafetyInfo() = default; +}; + +/// \brief 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. +void computeLoopSafetyInfo(LoopSafetyInfo *, Loop *); + +/// Returns true if the instruction in a loop is guaranteed to execute at least +/// once (under the assumption that the loop is entered). +bool isGuaranteedToExecute(const Instruction &Inst, const DominatorTree *DT, + const Loop *CurLoop, + const LoopSafetyInfo *SafetyInfo); + +} + +#endif diff --git a/llvm/include/llvm/Transforms/Utils/LoopUtils.h b/llvm/include/llvm/Transforms/Utils/LoopUtils.h index fb53647..f503a34 100644 --- a/llvm/include/llvm/Transforms/Utils/LoopUtils.h +++ b/llvm/include/llvm/Transforms/Utils/LoopUtils.h @@ -23,6 +23,7 @@ #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Analysis/DemandedBits.h" #include "llvm/Analysis/EHPersonalities.h" +#include "llvm/Analysis/MustExecute.h" #include "llvm/Analysis/TargetTransformInfo.h" #include "llvm/IR/Dominators.h" #include "llvm/IR/IRBuilder.h" @@ -39,6 +40,7 @@ class BasicBlock; class DataLayout; class Loop; class LoopInfo; +class LoopSafetyInfo; class OptimizationRemarkEmitter; class PredicatedScalarEvolution; class PredIteratorCache; @@ -47,17 +49,6 @@ class SCEV; class TargetLibraryInfo; class TargetTransformInfo; -/// \brief Captures loop safety information. -/// It keep information for loop & its header may throw exception. -struct LoopSafetyInfo { - bool MayThrow = false; // The current loop contains an instruction which - // may throw. - bool HeaderMayThrow = false; // Same as previous, but specific to loop header - // Used to update funclet bundle operands. - DenseMap BlockColors; - - LoopSafetyInfo() = default; -}; /// The RecurrenceDescriptor is used to identify recurrences variables in a /// loop. Reduction is a special case of recurrence that has uses of the @@ -480,18 +471,6 @@ bool promoteLoopAccessesToScalars(const SmallSetVector &, SmallVector collectChildrenInLoop(DomTreeNode *N, const Loop *CurLoop); -/// \brief 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. -void computeLoopSafetyInfo(LoopSafetyInfo *, Loop *); - -/// Returns true if the instruction in a loop is guaranteed to execute at least -/// once. -bool isGuaranteedToExecute(const Instruction &Inst, const DominatorTree *DT, - const Loop *CurLoop, - const LoopSafetyInfo *SafetyInfo); - /// \brief Returns the instructions that use values defined in the loop. SmallVector findDefsUsedOutsideOfLoop(Loop *L); diff --git a/llvm/lib/Analysis/MustExecute.cpp b/llvm/lib/Analysis/MustExecute.cpp index f741b35..c3b4de7 100644 --- a/llvm/lib/Analysis/MustExecute.cpp +++ b/llvm/lib/Analysis/MustExecute.cpp @@ -7,6 +7,7 @@ // //===----------------------------------------------------------------------===// +#include "llvm/Analysis/InstructionSimplify.h" #include "llvm/Analysis/LoopInfo.h" #include "llvm/Analysis/Passes.h" #include "llvm/Analysis/ValueTracking.h" @@ -21,6 +22,140 @@ #include "llvm/Transforms/Utils/LoopUtils.h" using namespace llvm; +/// 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(CondExitBlock->getTerminator()); + if (!BI || !BI->isConditional()) + return false; + auto *Cond = dyn_cast(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(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(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 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; +} + + namespace { struct MustExecutePrinter : public FunctionPass { 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 @@ void llvm::deleteDeadLoop(Loop *L, DominatorTree *DT = nullptr, } } -/// 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(CondExitBlock->getTerminator()); - if (!BI || !BI->isConditional()) - return false; - auto *Cond = dyn_cast(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(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(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 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 llvm::getLoopEstimatedTripCount(Loop *L) { // Only support loops with a unique exiting block, and a latch. if (!L->getExitingBlock()) -- 2.7.4