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,10 +52,28 @@ 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. + DenseSet> EarlyExits; + + // Utility to check for dominance information with caching. + OrderedInstructions OI; + // Used to update funclet bundle operands. DenseMap BlockColors; - LoopSafetyInfo() = default; + // Delete the specified early exit. This can happen if the early exit + // is removed from the loop. + void deleteExit(Instruction *E) { EarlyExits.erase(E); } + + // Return true if this instruction is an early exit, false otherwise. + bool isExit(Instruction *E) { return EarlyExits.count(E); } + + // Constructor. + LoopSafetyInfo(DominatorTree *DT) : OI(DT) {} }; /// The RecurrenceDescriptor is used to identify recurrences variables in a @@ -444,13 +463,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> 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, @@ -243,9 +241,9 @@ // Get the preheader block to move instructions into... BasicBlock *Preheader = L->getLoopPreheader(); - // Compute loop safety information. - LoopSafetyInfo SafetyInfo; - computeLoopSafetyInfo(&SafetyInfo, L); + // Compute loop safety information. Along with all the early exits. + LoopSafetyInfo SafetyInfo(DT); + 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 @@ -370,6 +368,11 @@ DEBUG(dbgs() << "LICM deleting dead inst: " << I << '\n'); ++II; CurAST->deleteValue(&I); + // We could have treated this instruction as an early exit, update the + // early exit list. + SafetyInfo->deleteExit(&I); + // The ordered instruction list for this block is no longer valid. + SafetyInfo->OI.invalidateBlock(I.getParent()); I.eraseFromParent(); Changed = true; continue; @@ -425,6 +428,11 @@ I.replaceAllUsesWith(C); if (isInstructionTriviallyDead(&I, TLI)) { CurAST->deleteValue(&I); + // We could have treated this instruction as an early exit, update the + // early exit list. + SafetyInfo->deleteExit(&I); + // The ordered instruction list for this block is no longer valid. + SafetyInfo->OI.invalidateBlock(I.getParent()); I.eraseFromParent(); } Changed = true; @@ -447,6 +455,11 @@ Product->setFastMathFlags(I.getFastMathFlags()); Product->insertAfter(&I); I.replaceAllUsesWith(Product); + // The ordered instruction list for this block is no longer valid. + SafetyInfo->OI.invalidateBlock(I.getParent()); + // We do not update the early exit list here, i.e. how can we treat this + // instruction as an early exit ? + assert(SafetyInfo->isExit(&I) && "Invalid early exit"); I.eraseFromParent(); hoist(*ReciprocalDivisor, DT, CurLoop, SafetyInfo, ORE); @@ -476,17 +489,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.insert(&*I); + } SafetyInfo->MayThrow = SafetyInfo->HeaderMayThrow; // Iterate over loop instructions and compute safety info. @@ -495,10 +518,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.insert(&*I); + } // Compute funclet colors if we might sink/hoist in a function with a funclet // personality routine. @@ -794,8 +825,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 +886,12 @@ PN->eraseFromParent(); } + + // We could have treated this instruction as an early exit, update the + // early exit list. + SafetyInfo->deleteExit(&I); + // The ordered instruction list for this block is no longer valid. + SafetyInfo->OI.invalidateBlock(I.getParent()); CurAST->deleteValue(&I); I.eraseFromParent(); return Changed; @@ -865,8 +901,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 +919,9 @@ !isGuaranteedToExecute(I, DT, CurLoop, SafetyInfo)) I.dropUnknownNonDebugMetadata(); + // The OBB for this basic block is no longer valid. + SafetyInfo->OI.invalidateBlock(I.getParent()); + SafetyInfo->deleteExit(&I); // Move the new node to the Preheader, before its terminator. I.moveBefore(Preheader->getTerminator()); @@ -909,7 +947,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/Scalar/LoopIdiomRecognize.cpp =================================================================== --- lib/Transforms/Scalar/LoopIdiomRecognize.cpp +++ lib/Transforms/Scalar/LoopIdiomRecognize.cpp @@ -283,7 +283,7 @@ // The following transforms hoist stores/memsets into the loop pre-header. // Give up if the loop has instructions may throw. - LoopSafetyInfo SafetyInfo; + LoopSafetyInfo SafetyInfo(DT); computeLoopSafetyInfo(&SafetyInfo, CurLoop); if (SafetyInfo.MayThrow) return MadeChange; Index: lib/Transforms/Scalar/LoopUnswitch.cpp =================================================================== --- lib/Transforms/Scalar/LoopUnswitch.cpp +++ lib/Transforms/Scalar/LoopUnswitch.cpp @@ -172,7 +172,6 @@ BasicBlock *loopPreheader; bool SanitizeMemory; - LoopSafetyInfo SafetyInfo; // LoopBlocks contains all of the basic blocks of the loop, including the // preheader of the loop, the body of the loop, and the exit blocks of the @@ -193,7 +192,7 @@ } bool runOnLoop(Loop *L, LPPassManager &LPM) override; - bool processCurrentLoop(); + bool processCurrentLoop(LoopSafetyInfo *SafetyInfo); bool isUnreachableDueToPreviousUnswitching(BasicBlock *); /// This transformation requires natural loop information & requires that /// loop preheaders be inserted into the CFG. @@ -508,6 +507,7 @@ Function *F = currentLoop->getHeader()->getParent(); SanitizeMemory = F->hasFnAttribute(Attribute::SanitizeMemory); + LoopSafetyInfo SafetyInfo(DT); if (SanitizeMemory) computeLoopSafetyInfo(&SafetyInfo, L); @@ -515,7 +515,7 @@ do { assert(currentLoop->isLCSSAForm(*DT)); redoLoop = false; - Changed |= processCurrentLoop(); + Changed |= processCurrentLoop(&SafetyInfo); } while(redoLoop); // FIXME: Reconstruct dom info, because it is not preserved properly. @@ -554,7 +554,7 @@ } /// Do actual work and unswitch loop if possible and profitable. -bool LoopUnswitch::processCurrentLoop() { +bool LoopUnswitch::processCurrentLoop(LoopSafetyInfo *SafetyInfo) { bool Changed = false; initLoopData(); @@ -649,7 +649,7 @@ // This is a workaround for the discrepancy between LLVM IR and MSan // semantics. See PR28054 for more details. if (SanitizeMemory && - !isGuaranteedToExecute(*TI, DT, currentLoop, &SafetyInfo)) + !isGuaranteedToExecute(*TI, DT, currentLoop, SafetyInfo)) continue; if (BranchInst *BI = dyn_cast(TI)) { 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)) + 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,7 @@ /// tree. bool OrderedInstructions::dominates(const Instruction *InstA, const Instruction *InstB) const { + assert(DT && "Uninitialized dominator tree"); 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,107 @@ +; RUN: opt -S -licm < %s | FileCheck %s + +declare void @use(i64 %a) +declare void @use_nothing() +declare void @call_nothrow() nounwind + +; 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(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(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 not transfer execution to successor, even +; though it does not throw. +define void @throw_body3(i64 %x, i64 %y, i1* %cond) { +; CHECK-LABEL: throw_body3 +; CHECK-LABEL: body +; CHECK: call void @call_nothrow() +; CHECK: %div = udiv i64 %x, %y +entry: + br label %loop + +loop: ; preds = %entry, %for.inc + br label %body + +body: + call void @call_nothrow() + %div = udiv i64 %x, %y + call void @use(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.