Index: include/llvm/Transforms/Utils/LoopUtils.h =================================================================== --- include/llvm/Transforms/Utils/LoopUtils.h +++ include/llvm/Transforms/Utils/LoopUtils.h @@ -28,6 +28,7 @@ #include "llvm/IR/Operator.h" #include "llvm/IR/ValueHandle.h" #include "llvm/Support/Casting.h" +#include "llvm/Transforms/Utils/OrderedInstructions.h" namespace llvm { @@ -51,6 +52,16 @@ bool MayThrow = false; // The current loop contains an instruction which // may throw. bool HeaderMayThrow = false; // Same as previous, but specific to loop header + + // Whether we have computed all the early exits. + bool ComputedEarlyExits = false; + // The early exits in the loop, excluding loop exits. + // These are calls that might throw, infinite loop, etc. + SmallVector EarlyExits; + + // Utility to check for dominance information with caching. + OrderedInstructions OI; + // Used to update funclet bundle operands. DenseMap BlockColors; @@ -444,13 +455,14 @@ /// 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 *); +/// In case ComputeEarlyExits is true, all the early exit points are recorded. +void computeLoopSafetyInfo(LoopSafetyInfo *, Loop *, + bool ComputeEarlyExits = false); /// 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); + const Loop *CurLoop, LoopSafetyInfo *SafetyInfo); /// \brief Returns the instructions that use values defined in the loop. SmallVector findDefsUsedOutsideOfLoop(Loop *L); Index: include/llvm/Transforms/Utils/OrderedInstructions.h =================================================================== --- include/llvm/Transforms/Utils/OrderedInstructions.h +++ include/llvm/Transforms/Utils/OrderedInstructions.h @@ -10,11 +10,6 @@ // This file defines an efficient way to check for dominance relation between 2 // instructions. // -// This interface dispatches to appropriate dominance check given 2 -// instructions, i.e. in case the instructions are in the same basic block, -// OrderedBasicBlock (with instruction numbering and caching) are used. -// Otherwise, dominator tree is used. -// //===----------------------------------------------------------------------===// #ifndef LLVM_TRANSFORMS_UTILS_ORDEREDINSTRUCTIONS_H @@ -27,6 +22,12 @@ namespace llvm { +/// This interface dispatches to appropriate dominance check given 2 +/// instructions, i.e. in case the instructions are in the same basic block, +/// OrderedBasicBlock (with instruction numbering and caching) are used. +/// Otherwise, dominator tree is used. This interface relies on the +/// transformations to invalidate the basic blocks in case instructions in it +/// are changed. class OrderedInstructions { /// Used to check dominance for instructions in same basic block. mutable DenseMap> @@ -36,12 +37,19 @@ DominatorTree *DT; public: - /// Constructor. + /// Constructors. + OrderedInstructions() = default; OrderedInstructions(DominatorTree *DT) : DT(DT) {} - /// Return true if first instruction dominates the second. + /// Return true if first instruction dominates the second. Use the class + /// member dominator tree. bool dominates(const Instruction *, const Instruction *) const; + /// Return true if first instruction dominates the second. Use the passed + /// dominator tree. + bool dominates(const Instruction *, const Instruction *, + const DominatorTree *) const; + /// Invalidate the OrderedBasicBlock cache when its basic block changes. void invalidateBlock(BasicBlock *BB) { OBBMap.erase(BB); } }; Index: lib/Transforms/Scalar/LICM.cpp =================================================================== --- lib/Transforms/Scalar/LICM.cpp +++ lib/Transforms/Scalar/LICM.cpp @@ -91,16 +91,14 @@ static bool isNotUsedInLoop(const Instruction &I, const Loop *CurLoop, const LoopSafetyInfo *SafetyInfo); static bool hoist(Instruction &I, const DominatorTree *DT, const Loop *CurLoop, - const LoopSafetyInfo *SafetyInfo, - OptimizationRemarkEmitter *ORE); + LoopSafetyInfo *SafetyInfo, OptimizationRemarkEmitter *ORE); static bool sink(Instruction &I, const LoopInfo *LI, const DominatorTree *DT, const Loop *CurLoop, AliasSetTracker *CurAST, - const LoopSafetyInfo *SafetyInfo, - OptimizationRemarkEmitter *ORE); + LoopSafetyInfo *SafetyInfo, OptimizationRemarkEmitter *ORE); static bool isSafeToExecuteUnconditionally(Instruction &Inst, const DominatorTree *DT, const Loop *CurLoop, - const LoopSafetyInfo *SafetyInfo, + LoopSafetyInfo *SafetyInfo, OptimizationRemarkEmitter *ORE, const Instruction *CtxI = nullptr); static bool pointerInvalidatedByLoop(Value *V, uint64_t Size, @@ -245,7 +243,7 @@ // Compute loop safety information. LoopSafetyInfo SafetyInfo; - computeLoopSafetyInfo(&SafetyInfo, L); + computeLoopSafetyInfo(&SafetyInfo, L, true); // We want to visit all of the instructions in this loop... that are not parts // of our subloops (they have already had their invariants hoisted out of @@ -476,17 +474,27 @@ /// Computes loop safety information, checks loop body & header /// for the possibility of may throw exception. /// -void llvm::computeLoopSafetyInfo(LoopSafetyInfo *SafetyInfo, Loop *CurLoop) { +void llvm::computeLoopSafetyInfo(LoopSafetyInfo *SafetyInfo, Loop *CurLoop, + bool ComputeEarlyExits) { assert(CurLoop != nullptr && "CurLoop cant be null"); BasicBlock *Header = CurLoop->getHeader(); // Setting default safety values. SafetyInfo->MayThrow = false; SafetyInfo->HeaderMayThrow = false; + SafetyInfo->EarlyExits.clear(); + SafetyInfo->ComputedEarlyExits = ComputeEarlyExits; // Iterate over header and compute safety info. - for (BasicBlock::iterator I = Header->begin(), E = Header->end(); - (I != E) && !SafetyInfo->HeaderMayThrow; ++I) - SafetyInfo->HeaderMayThrow |= - !isGuaranteedToTransferExecutionToSuccessor(&*I); + for (BasicBlock::iterator I = Header->begin(), E = Header->end(); I != E; + ++I) { + bool MayThrow = !isGuaranteedToTransferExecutionToSuccessor(&*I); + SafetyInfo->HeaderMayThrow |= MayThrow; + // Exit as soon as we find an instruction that may throw in case we are + // not computing early exits. + if (!ComputeEarlyExits && SafetyInfo->HeaderMayThrow) + break; + if (MayThrow) + SafetyInfo->EarlyExits.push_back(&*I); + } SafetyInfo->MayThrow = SafetyInfo->HeaderMayThrow; // Iterate over loop instructions and compute safety info. @@ -495,10 +503,18 @@ 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) - for (BasicBlock::iterator I = (*BB)->begin(), E = (*BB)->end(); - (I != E) && !SafetyInfo->MayThrow; ++I) - SafetyInfo->MayThrow |= !isGuaranteedToTransferExecutionToSuccessor(&*I); + BB != BBE; ++BB) + for (BasicBlock::iterator I = (*BB)->begin(), E = (*BB)->end(); I != E; + ++I) { + bool MayThrow = !isGuaranteedToTransferExecutionToSuccessor(&*I); + SafetyInfo->MayThrow |= MayThrow; + // Exit as soon as we find an instruction that may throw in case we are + // not computing early exits. + if (!ComputeEarlyExits && SafetyInfo->MayThrow) + break; + if (MayThrow) + SafetyInfo->EarlyExits.push_back(&*I); + } // Compute funclet colors if we might sink/hoist in a function with a funclet // personality routine. @@ -794,8 +810,7 @@ /// static bool sink(Instruction &I, const LoopInfo *LI, const DominatorTree *DT, const Loop *CurLoop, AliasSetTracker *CurAST, - const LoopSafetyInfo *SafetyInfo, - OptimizationRemarkEmitter *ORE) { + LoopSafetyInfo *SafetyInfo, OptimizationRemarkEmitter *ORE) { DEBUG(dbgs() << "LICM sinking instruction: " << I << "\n"); ORE->emit(OptimizationRemark(DEBUG_TYPE, "InstSunk", &I) << "sinking " << ore::NV("Inst", &I)); @@ -856,6 +871,8 @@ PN->eraseFromParent(); } + // The OBB for this basic block is no longer valid. + SafetyInfo->OI.invalidateBlock(I.getParent()); CurAST->deleteValue(&I); I.eraseFromParent(); return Changed; @@ -865,8 +882,7 @@ /// is safe to hoist, this instruction is called to do the dirty work. /// static bool hoist(Instruction &I, const DominatorTree *DT, const Loop *CurLoop, - const LoopSafetyInfo *SafetyInfo, - OptimizationRemarkEmitter *ORE) { + LoopSafetyInfo *SafetyInfo, OptimizationRemarkEmitter *ORE) { auto *Preheader = CurLoop->getLoopPreheader(); DEBUG(dbgs() << "LICM hoisting to " << Preheader->getName() << ": " << I << "\n"); @@ -884,6 +900,8 @@ !isGuaranteedToExecute(I, DT, CurLoop, SafetyInfo)) I.dropUnknownNonDebugMetadata(); + // The OBB for this basic block is no longer valid. + SafetyInfo->OI.invalidateBlock(I.getParent()); // Move the new node to the Preheader, before its terminator. I.moveBefore(Preheader->getTerminator()); @@ -909,7 +927,7 @@ static bool isSafeToExecuteUnconditionally(Instruction &Inst, const DominatorTree *DT, const Loop *CurLoop, - const LoopSafetyInfo *SafetyInfo, + LoopSafetyInfo *SafetyInfo, OptimizationRemarkEmitter *ORE, const Instruction *CtxI) { if (isSafeToSpeculativelyExecute(&Inst, CtxI, DT)) Index: lib/Transforms/Utils/LoopUtils.cpp =================================================================== --- lib/Transforms/Utils/LoopUtils.cpp +++ lib/Transforms/Utils/LoopUtils.cpp @@ -17,6 +17,7 @@ #include "llvm/Analysis/GlobalsModRef.h" #include "llvm/Analysis/LoopInfo.h" #include "llvm/Analysis/LoopPass.h" +#include "llvm/Analysis/OrderedBasicBlock.h" #include "llvm/Analysis/ScalarEvolution.h" #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h" #include "llvm/Analysis/ScalarEvolutionExpander.h" @@ -1042,24 +1043,33 @@ /// once. bool llvm::isGuaranteedToExecute(const Instruction &Inst, const DominatorTree *DT, const Loop *CurLoop, - const LoopSafetyInfo *SafetyInfo) { + LoopSafetyInfo *SafetyInfo) { + // If we have computed early exits, use it. + if (SafetyInfo->ComputedEarlyExits) { + // Check wehther the instruction dominates all early exits. If it doesn't, + // then there is a path out of the loop which does not execute this + // instruction and its not guaranteed to execute. + for (Instruction *ExitInst : SafetyInfo->EarlyExits) + if (!SafetyInfo->OI.dominates(&Inst, ExitInst, DT)) + return false; + } else { + // 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; + } + // 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; - + // which does not execute this instruction. // Get the exit blocks for the current loop. SmallVector ExitBlocks; CurLoop->getExitBlocks(ExitBlocks); @@ -1071,7 +1081,9 @@ // 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()) + // However, we also special case instruction from the header as the header + // is always guaranteed to execute. + if (ExitBlocks.empty() && Inst.getParent() != CurLoop->getHeader()) return false; // FIXME: In general, we have to prove that the loop isn't an infinite loop. Index: lib/Transforms/Utils/OrderedInstructions.cpp =================================================================== --- lib/Transforms/Utils/OrderedInstructions.cpp +++ lib/Transforms/Utils/OrderedInstructions.cpp @@ -19,6 +19,16 @@ /// tree. bool OrderedInstructions::dominates(const Instruction *InstA, const Instruction *InstB) const { + assert(DT && "Uninitialized dominator tree"); + return dominates(InstA, InstB, DT); +} + +/// Given 2 instructions, use OrderedBasicBlock to check for dominance relation +/// if the instructions are in the same basic block, Otherwise, use dominator +/// tree. +bool OrderedInstructions::dominates(const Instruction *InstA, + const Instruction *InstB, + const DominatorTree *DT) const { const BasicBlock *IBB = InstA->getParent(); // Use ordered basic block to do dominance check in case the 2 instructions // are in the same basic block. Index: test/Transforms/LICM/loop-early-exits.ll =================================================================== --- /dev/null +++ test/Transforms/LICM/loop-early-exits.ll @@ -0,0 +1,82 @@ +; RUN: opt -S -licm < %s | FileCheck %s + +declare void @use(i64 %a) +declare void @use_nothrow(i64 %a) nounwind +declare void @use_nothing() + +; We can move this udiv out of the loop as it comes before +; the call instruction that may throw. +define void @throw_header1(i64 %x, i64 %y, i1* %cond) { +; CHECK-LABEL: throw_header1 +; CHECK: %div = udiv i64 %x, %y +; CHECK-LABEL: loop +; CHECK: call void @use(i64 %div) +entry: + br label %loop + +loop: ; preds = %entry, %for.inc + %div = udiv i64 %x, %y + call void @use(i64 %div) + br label %loop +} + +; We can not move this udiv out of the loop as it comes after +; the call instruction that may throw. +define void @throw_header2(i64 %x, i64 %y, i1* %cond) { +; CHECK-LABEL: throw_header2 +; CHECK-LABEL: loop +; CHECK: call void @use_nothing() +; CHECK: %div = udiv i64 %x, %y +entry: + br label %loop + +loop: ; preds = %entry, %for.inc + call void @use_nothing() + %div = udiv i64 %x, %y + call void @use_nothrow(i64 %div) + br label %loop +} + +; We can move this udiv out of the loop as it comes before +; the call instruction that may throw. +define void @throw_body1(i64 %x, i64 %y, i1* %cond) { +; CHECK-LABEL: throw_body1 +; CHECK: %div = udiv i64 %x, %y +; CHECK-LABEL: loop +entry: + br label %loop + +loop: ; preds = %entry, %for.inc + br label %body + +body: + %div = udiv i64 %x, %y + call void @use(i64 %div) + br i1 undef, label %loop, label %exit + +exit: + ret void +} + +; We can not move this udiv out of the loop as it comes after +; the call instruction that may throw. +define void @throw_body2(i64 %x, i64 %y, i1* %cond) { +; CHECK-LABEL: throw_body2 +; CHECK-LABEL: loop +; CHECK: call void @use_nothing() +; CHECK: %div = udiv i64 %x, %y +entry: + br label %loop + +loop: ; preds = %entry, %for.inc + br label %body + +body: + call void @use_nothing() + %div = udiv i64 %x, %y + call void @use_nothrow(i64 %div) + br i1 undef, label %loop, label %exit + +exit: + ret void +} Index: test/Transforms/LICM/preheader-safe.ll =================================================================== --- test/Transforms/LICM/preheader-safe.ll +++ test/Transforms/LICM/preheader-safe.ll @@ -21,20 +21,6 @@ call void @use_nothrow(i64 %div) br label %loop } -; Negative test -define void @throw_header(i64 %x, i64 %y, i1* %cond) { -; CHECK-LABEL: throw_header -; CHECK-LABEL: loop -; CHECK: %div = udiv i64 %x, %y -; CHECK: call void @use(i64 %div) -entry: - br label %loop - -loop: ; preds = %entry, %for.inc - %div = udiv i64 %x, %y - call void @use(i64 %div) - br label %loop -} ; The header is known no throw, but the loop is not. We can ; still lift out of the header.