Index: include/llvm/Analysis/MustExecute.h =================================================================== --- include/llvm/Analysis/MustExecute.h +++ include/llvm/Analysis/MustExecute.h @@ -23,6 +23,7 @@ #include "llvm/IR/BasicBlock.h" #include "llvm/IR/Dominators.h" #include "llvm/IR/Instruction.h" +#include "llvm/Transforms/Utils/ImplicitControlFlowTracking.h" namespace llvm { @@ -31,33 +32,46 @@ class Loop; /// Captures loop safety information. -/// It keep information for loop & its header may throw exception or otherwise +/// It keep information for loop blocks 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 +class LoopSafetyInfo { +public: // Used to update funclet bundle operands. DenseMap BlockColors; - LoopSafetyInfo() = default; -}; + LoopSafetyInfo(Loop *L, DominatorTree *DT) : CurLoop(L), ICF(DT) {} + + bool mayThrow(const BasicBlock *BB); + + bool anyBlockMayThrow(); + + bool mayThrowBefore(const BasicBlock *BB); -/// 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 *); + bool mayThrowBefore(const Instruction *Insn); + + void invalidateBlock(const BasicBlock *BB); + + void reset(Loop *L); + +private: + // The current loop this LoopSafetyInfo is working with. It should be set via + // constructor or via the method "reset" to a non-null value before any query + // is done to this LoopSafetyInfo. + Loop *CurLoop = nullptr; + // Contains information about implicit control flow in this loop's blocks. + ImplicitControlFlowTracking ICF; + // Caches answers of 'mayThrowBefore' queries. + DenseMap MayThrowBefore; +}; /// 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); + LoopSafetyInfo *SafetyInfo); } Index: lib/Analysis/MustExecute.cpp =================================================================== --- lib/Analysis/MustExecute.cpp +++ lib/Analysis/MustExecute.cpp @@ -22,38 +22,81 @@ #include "llvm/Support/raw_ostream.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 can't 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 (isScopedEHPersonality(classifyEHPersonality(PersonalityFn))) - SafetyInfo->BlockColors = colorEHFunclets(*Fn); +/// Returns true if the block \p BB contains an instruction that may throw or +/// otherwise exit abnormally. +bool LoopSafetyInfo::mayThrow(const BasicBlock *BB) { + assert(CurLoop->contains(BB) && "Should only be called for loop blocks!"); + return ICF.hasICF(BB); +} + +/// Returns true if any loop in the current loop contains an instruction that +/// may throw or otherwise exit abnormally. +bool LoopSafetyInfo::anyBlockMayThrow() { + for (auto *BB : CurLoop->blocks()) + if (mayThrow(BB)) + return true; + return false; +} + +/// Returns true if the block \p BB may not be entered because of some +/// instruction from the same loop that may throw or otherwise exit abnormally. +/// Returns false if the block \p BB is guaranteed to be executed if the loop +/// header is entered. +bool LoopSafetyInfo::mayThrowBefore(const BasicBlock *BB) { + assert(CurLoop->contains(BB) && "Should only be called for loop blocks!"); + // There is nothing in this loop before the header. + if (BB == CurLoop->getHeader()) + return false; + + // Check if we already know the cached result. + auto It = MayThrowBefore.find(BB); + if (It != MayThrowBefore.end()) + return It->second; + + // Put false to avoid infinite recursion. This value will be updated if we + // find that some instruction executed before this block may throw. + MayThrowBefore[BB] = false; + bool Result = false; + + // Check if any of the predecessors may throw, or it may happen before them. + // Skip backedges. + for (auto *Pred : predecessors(BB)) + if (mayThrow(Pred) || mayThrowBefore(Pred)) { + Result = true; + break; + } + + // Store rhe result in cache and return. + MayThrowBefore[BB] = Result; + return Result; +} + +/// Returns true if the instruction \p Insn may not be executed because of +/// another instruction from the same loop that may throw or otherwise exit +/// abnormally. Returns false if the instruction \p Insn is guaranteed to be +/// executed if the loop header is entered. +bool LoopSafetyInfo::mayThrowBefore(const Instruction *Insn) { + return ICF.isDominatedByICFIFromSameBlock(Insn) || + mayThrowBefore(Insn->getParent()); +} + +/// Drops memoized information regarding the abnormal exits in block \p BB. +/// This method needs to be called on a block after any instruction is added or +/// removed from this block. +void LoopSafetyInfo::invalidateBlock(const BasicBlock *BB) { + assert(CurLoop->contains(BB) && "Should only be called for loop blocks!"); + ICF.invalidateBlock(BB); + MayThrowBefore.erase(BB); +} + +/// Drops all memoized information from this LoopSafetyInfo and prepares it to +/// analyze the loop \p L. This method can be used when we want to use one +/// LoopSafetyInfo to process multiple loops. +void LoopSafetyInfo::reset(Loop *L) { + BlockColors.clear(); + ICF.clear(); + MayThrowBefore.clear(); + CurLoop = L; } /// Return true if we can prove that the given ExitBlock is not reached on the @@ -103,7 +146,7 @@ /// once. bool llvm::isGuaranteedToExecute(const Instruction &Inst, const DominatorTree *DT, const Loop *CurLoop, - const LoopSafetyInfo *SafetyInfo) { + 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. @@ -116,12 +159,11 @@ // Inst unless we can prove that Inst comes before the potential implicit // exit. At the moment, we use a (cheap) hack for the common case where // the instruction of interest is the first one in the block. - return !SafetyInfo->HeaderMayThrow || + return !SafetyInfo->mayThrow(CurLoop->getHeader()) || Inst.getParent()->getFirstNonPHIOrDbg() == &Inst; - // Somewhere in this loop there is an instruction which may throw and make us - // exit the loop. - if (SafetyInfo->MayThrow) + // If we can throw before we reach the given instruction, return false. + if (SafetyInfo->mayThrowBefore(&Inst)) return false; // Note: There are two styles of reasoning intermixed below for @@ -195,8 +237,7 @@ // TODO: merge these two routines. For the moment, we display the best // result obtained by *either* implementation. This is a bit unfair since no // caller actually gets the full power at the moment. - LoopSafetyInfo LSI; - computeLoopSafetyInfo(&LSI, L); + LoopSafetyInfo LSI(L, DT); return isGuaranteedToExecute(I, DT, L, &LSI) || isGuaranteedToExecuteForEveryIteration(&I, L); } Index: lib/Transforms/Scalar/LICM.cpp =================================================================== --- lib/Transforms/Scalar/LICM.cpp +++ lib/Transforms/Scalar/LICM.cpp @@ -94,7 +94,7 @@ const LoopSafetyInfo *SafetyInfo, TargetTransformInfo *TTI, bool &FreeInLoop); static bool hoist(Instruction &I, const DominatorTree *DT, const Loop *CurLoop, - const LoopSafetyInfo *SafetyInfo, + LoopSafetyInfo *SafetyInfo, OptimizationRemarkEmitter *ORE); static bool sink(Instruction &I, LoopInfo *LI, DominatorTree *DT, const Loop *CurLoop, LoopSafetyInfo *SafetyInfo, @@ -102,7 +102,7 @@ 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, @@ -260,8 +260,7 @@ BasicBlock *Preheader = L->getLoopPreheader(); // Compute loop safety information. - LoopSafetyInfo SafetyInfo; - computeLoopSafetyInfo(&SafetyInfo, L); + LoopSafetyInfo SafetyInfo(L, DT); // 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 @@ -943,6 +942,9 @@ return OptimizationRemark(DEBUG_TYPE, "InstSunk", &I) << "sinking " << ore::NV("Inst", &I); }); + + // Contents of a block may change, we need to mark it in safety info. + SafetyInfo->invalidateBlock(I.getParent()); bool Changed = false; if (isa(I)) ++NumMovedLoads; @@ -1037,7 +1039,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, + LoopSafetyInfo *SafetyInfo, OptimizationRemarkEmitter *ORE) { auto *Preheader = CurLoop->getLoopPreheader(); LLVM_DEBUG(dbgs() << "LICM hoisting to " << Preheader->getName() << ": " << I @@ -1058,6 +1060,8 @@ !isGuaranteedToExecute(I, DT, CurLoop, SafetyInfo)) I.dropUnknownNonDebugMetadata(); + // Contents of a block has changed, we need to mark it in safety info. + SafetyInfo->invalidateBlock(I.getParent()); // Move the new node to the Preheader, before its terminator. I.moveBefore(Preheader->getTerminator()); @@ -1083,7 +1087,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)) @@ -1283,7 +1287,7 @@ const DataLayout &MDL = Preheader->getModule()->getDataLayout(); bool IsKnownThreadLocalObject = false; - if (SafetyInfo->MayThrow) { + if (SafetyInfo->anyBlockMayThrow()) { // If a loop can throw, we have to insert a store along each unwind edge. // That said, we can't actually make the unwind edge explicit. Therefore, // we have to prove that the store is dead along the unwind edge. We do Index: lib/Transforms/Scalar/LoopIdiomRecognize.cpp =================================================================== --- lib/Transforms/Scalar/LoopIdiomRecognize.cpp +++ lib/Transforms/Scalar/LoopIdiomRecognize.cpp @@ -319,9 +319,8 @@ // The following transforms hoist stores/memsets into the loop pre-header. // Give up if the loop has instructions may throw. - LoopSafetyInfo SafetyInfo; - computeLoopSafetyInfo(&SafetyInfo, CurLoop); - if (SafetyInfo.MayThrow) + LoopSafetyInfo SafetyInfo(CurLoop, DT); + if (SafetyInfo.anyBlockMayThrow()) return MadeChange; // Scan all the blocks in the loop that are not in subloops. Index: lib/Transforms/Scalar/LoopUnswitch.cpp =================================================================== --- lib/Transforms/Scalar/LoopUnswitch.cpp +++ lib/Transforms/Scalar/LoopUnswitch.cpp @@ -199,7 +199,7 @@ static char ID; // Pass ID, replacement for typeid explicit LoopUnswitch(bool Os = false, bool hasBranchDivergence = false) - : LoopPass(ID), OptimizeForSize(Os), + : LoopPass(ID), OptimizeForSize(Os), SafetyInfo(nullptr, DT), hasBranchDivergence(hasBranchDivergence) { initializeLoopUnswitchPass(*PassRegistry::getPassRegistry()); } @@ -520,7 +520,7 @@ SanitizeMemory = F->hasFnAttribute(Attribute::SanitizeMemory); if (SanitizeMemory) - computeLoopSafetyInfo(&SafetyInfo, L); + SafetyInfo.reset(L); bool Changed = false; do { Index: lib/Transforms/Utils/LoopUnrollAndJam.cpp =================================================================== --- lib/Transforms/Utils/LoopUnrollAndJam.cpp +++ lib/Transforms/Utils/LoopUnrollAndJam.cpp @@ -774,9 +774,8 @@ } // Check the loop safety info for exceptions. - LoopSafetyInfo LSI; - computeLoopSafetyInfo(&LSI, L); - if (LSI.MayThrow) { + LoopSafetyInfo LSI(L, &DT); + if (LSI.anyBlockMayThrow()) { LLVM_DEBUG(dbgs() << "Won't unroll-and-jam; Something may throw\n"); return false; } Index: test/Analysis/MustExecute/loop-header.ll =================================================================== --- test/Analysis/MustExecute/loop-header.ll +++ test/Analysis/MustExecute/loop-header.ll @@ -30,6 +30,7 @@ ; CHECK: %iv = phi i32 [ 0, %entry ], [ %iv.next, %next ] ; (mustexec in: loop) ; CHECK: %v = load i32, i32* %p ; (mustexec in: loop) ; CHECK: br label %next ; (mustexec in: loop) +; CHECK: call void @maythrow_and_use(i32 %v) ; (mustexec in: loop) ; CHECK-NOT: mustexec entry: br label %loop @@ -56,9 +57,10 @@ ; CHECK: %iv = phi i32 [ 0, %entry ], [ %iv.next, %next ] ; (mustexec in: loop) ; CHECK: br label %inner_loop ; (mustexec in: loop) ; CHECK-LABEL: inner_loop: -; CHECK: %v = load i32, i32* %p ; (mustexec in: inner_loop) -; CHECK: %inner.test = icmp eq i32 %v, 0 ; (mustexec in: inner_loop) -; CHECK: br i1 %inner.test, label %inner_loop, label %next ; (mustexec in: inner_loop) +; CHECK: %v = load i32, i32* %p ; (mustexec in 2 loops: inner_loop, loop) +; CHECK: %inner.test = icmp eq i32 %v, 0 ; (mustexec in 2 loops: inner_loop, loop) +; CHECK: br i1 %inner.test, label %inner_loop, label %next ; (mustexec in 2 loops: inner_loop, loop) +; CHECK: call void @maythrow_and_use(i32 %v) ; (mustexec in: loop) ; CHECK-NOT: mustexec entry: Index: test/Transforms/LICM/funclet.ll =================================================================== --- test/Transforms/LICM/funclet.ll +++ test/Transforms/LICM/funclet.ll @@ -57,7 +57,7 @@ ; CHECK-LABEL: define void @test2( ; CHECK: %[[CP:.*]] = cleanuppad within none [] -; CHECK-NEXT: %[[CALL:.*]] = call i32 @pure_computation() [ "funclet"(token %[[CP]]) ] +; CHECK-NEXT: %[[CALL:.*]] = call i32 @pure_computation() ; CHECK-NEXT: store i32 %[[CALL]], i32* %s ; CHECK-NEXT: cleanupret from %[[CP]] unwind to caller Index: test/Transforms/LICM/hoist-mustexec.ll =================================================================== --- test/Transforms/LICM/hoist-mustexec.ll +++ test/Transforms/LICM/hoist-mustexec.ll @@ -280,3 +280,299 @@ call void @f() ret i32 -1 } + +declare void @may_throw() inaccessiblememonly + +; Test that we can sink a mustexecute load from loop header even in presence of +; throwing instructions after it. +define void @test_hoist_from_header_01(i32* %p, i32 %n) { + +; CHECK-LABEL: @test_hoist_from_header_01( +; CHECK: entry: +; CHECK-NEXT: %load = load i32, i32* %p +; CHECK-NOT: load i32 + +entry: + br label %loop + +loop: + %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ] + %dummy = phi i32 [ 0, %entry ], [ %merge, %backedge ] + %load = load i32, i32* %p + call void @may_throw() + %cond = icmp slt i32 %iv, %n + br i1 %cond, label %if.true, label %if.false + +if.true: + %a = add i32 %iv, %iv + br label %backedge + +if.false: + %b = mul i32 %iv, %iv + br label %backedge + +backedge: + %merge = phi i32 [ %a, %if.true ], [ %b, %if.false ] + %iv.next = add i32 %iv, %merge + %loop.cond = icmp ult i32 %iv.next, %load + br i1 %loop.cond, label %loop, label %exit + +exit: + ret void +} + +define void @test_hoist_from_header_02(i32* %p, i32 %n) { + +; CHECK-LABEL: @test_hoist_from_header_02( +; CHECK: entry: +; CHECK-NEXT: %load = load i32, i32* %p +; CHECK-NOT: load i32 + +entry: + br label %loop + +loop: + %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ] + %dummy = phi i32 [ 0, %entry ], [ %merge, %backedge ] + %load = load i32, i32* %p + %cond = icmp slt i32 %iv, %n + br i1 %cond, label %if.true, label %if.false + +if.true: + call void @may_throw() + %a = add i32 %iv, %iv + br label %backedge + +if.false: + %b = mul i32 %iv, %iv + br label %backedge + +backedge: + %merge = phi i32 [ %a, %if.true ], [ %b, %if.false ] + %iv.next = add i32 %iv, %merge + %loop.cond = icmp ult i32 %iv.next, %load + br i1 %loop.cond, label %loop, label %exit + +exit: + ret void +} + +define void @test_hoist_from_header_03(i32* %p, i32 %n) { + +; CHECK-LABEL: @test_hoist_from_header_03( +; CHECK: entry: +; CHECK-NEXT: %load = load i32, i32* %p +; CHECK-NOT: load i32 + +entry: + br label %loop + +loop: + %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ] + %dummy = phi i32 [ 0, %entry ], [ %merge, %backedge ] + %load = load i32, i32* %p + %cond = icmp slt i32 %iv, %n + br i1 %cond, label %if.true, label %if.false + +if.true: + %a = add i32 %iv, %iv + br label %backedge + +if.false: + %b = mul i32 %iv, %iv + br label %backedge + +backedge: + %merge = phi i32 [ %a, %if.true ], [ %b, %if.false ] + call void @may_throw() + %iv.next = add i32 %iv, %merge + %loop.cond = icmp ult i32 %iv.next, %load + br i1 %loop.cond, label %loop, label %exit + +exit: + ret void +} + +; Check that a throwing instruction prohibits hoisting across it. +define void @test_hoist_from_header_04(i32* %p, i32 %n) { + +; CHECK-LABEL: @test_hoist_from_header_04( +; CHECK: entry: +; CHECK: loop: +; CHECK: %load = load i32, i32* %p + +entry: + br label %loop + +loop: + %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ] + %dummy = phi i32 [ 0, %entry ], [ %merge, %backedge ] + call void @may_throw() + %load = load i32, i32* %p + %cond = icmp slt i32 %iv, %n + br i1 %cond, label %if.true, label %if.false + +if.true: + %a = add i32 %iv, %iv + br label %backedge + +if.false: + %b = mul i32 %iv, %iv + br label %backedge + +backedge: + %merge = phi i32 [ %a, %if.true ], [ %b, %if.false ] + %iv.next = add i32 %iv, %merge + %loop.cond = icmp ult i32 %iv.next, %load + br i1 %loop.cond, label %loop, label %exit + +exit: + ret void +} + +; Check that we can hoist a mustexecute load from backedge even if something +; throws after it. +define void @test_hoist_from_backedge_01(i32* %p, i32 %n) { + +; CHECK-LABEL: @test_hoist_from_backedge_01( +; CHECK: entry: +; CHECK-NEXT: %load = load i32, i32* %p +; CHECK-NOT: load i32 + +entry: + br label %loop + +loop: + %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ] + %dummy = phi i32 [ 0, %entry ], [ %merge, %backedge ] + %cond = icmp slt i32 %iv, %n + br i1 %cond, label %if.true, label %if.false + +if.true: + %a = add i32 %iv, %iv + br label %backedge + +if.false: + %b = mul i32 %iv, %iv + br label %backedge + +backedge: + %merge = phi i32 [ %a, %if.true ], [ %b, %if.false ] + %iv.next = add i32 %iv, %merge + %load = load i32, i32* %p + call void @may_throw() + %loop.cond = icmp ult i32 %iv.next, %load + br i1 %loop.cond, label %loop, label %exit + +exit: + ret void +} + +; Check that we don't hoist the load if something before it can throw. +define void @test_hoist_from_backedge_02(i32* %p, i32 %n) { + +; CHECK-LABEL: @test_hoist_from_backedge_02( +; CHECK: entry: +; CHECK: loop: +; CHECK: %load = load i32, i32* %p + +entry: + br label %loop + +loop: + %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ] + %dummy = phi i32 [ 0, %entry ], [ %merge, %backedge ] + %cond = icmp slt i32 %iv, %n + br i1 %cond, label %if.true, label %if.false + +if.true: + %a = add i32 %iv, %iv + br label %backedge + +if.false: + %b = mul i32 %iv, %iv + br label %backedge + +backedge: + %merge = phi i32 [ %a, %if.true ], [ %b, %if.false ] + %iv.next = add i32 %iv, %merge + call void @may_throw() + %load = load i32, i32* %p + %loop.cond = icmp ult i32 %iv.next, %load + br i1 %loop.cond, label %loop, label %exit + +exit: + ret void +} + +define void @test_hoist_from_backedge_03(i32* %p, i32 %n) { + +; CHECK-LABEL: @test_hoist_from_backedge_03( +; CHECK: entry: +; CHECK: loop: +; CHECK: %load = load i32, i32* %p + +entry: + br label %loop + +loop: + %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ] + %dummy = phi i32 [ 0, %entry ], [ %merge, %backedge ] + %cond = icmp slt i32 %iv, %n + br i1 %cond, label %if.true, label %if.false + +if.true: + %a = add i32 %iv, %iv + br label %backedge + +if.false: + %b = mul i32 %iv, %iv + call void @may_throw() + br label %backedge + +backedge: + %merge = phi i32 [ %a, %if.true ], [ %b, %if.false ] + %iv.next = add i32 %iv, %merge + %load = load i32, i32* %p + %loop.cond = icmp ult i32 %iv.next, %load + br i1 %loop.cond, label %loop, label %exit + +exit: + ret void +} + +define void @test_hoist_from_backedge_04(i32* %p, i32 %n) { + +; CHECK-LABEL: @test_hoist_from_backedge_04( +; CHECK: entry: +; CHECK: loop: +; CHECK: %load = load i32, i32* %p + +entry: + br label %loop + +loop: + %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ] + %dummy = phi i32 [ 0, %entry ], [ %merge, %backedge ] + call void @may_throw() + %cond = icmp slt i32 %iv, %n + br i1 %cond, label %if.true, label %if.false + +if.true: + %a = add i32 %iv, %iv + br label %backedge + +if.false: + %b = mul i32 %iv, %iv + br label %backedge + +backedge: + %merge = phi i32 [ %a, %if.true ], [ %b, %if.false ] + %iv.next = add i32 %iv, %merge + %load = load i32, i32* %p + %loop.cond = icmp ult i32 %iv.next, %load + br i1 %loop.cond, label %loop, label %exit + +exit: + ret void +} Index: test/Transforms/LICM/hoist-nounwind.ll =================================================================== --- test/Transforms/LICM/hoist-nounwind.ll +++ test/Transforms/LICM/hoist-nounwind.ll @@ -49,14 +49,16 @@ ret i32 0 } -; Don't hoist load past volatile load. +; Hoist a non-volatile load past volatile load. define i32 @test3(i32* noalias nocapture readonly %a, i32* %v) nounwind uwtable { ; CHECK-LABEL: @test3( entry: br label %for.body +; CHECK: load i32 +; CHECK: for.body: ; CHECK: load volatile i32 -; CHECK-NEXT: load i32 +; CHECK-NOT: load for.body: %i.06 = phi i32 [ 0, %entry ], [ %inc, %for.body ] %x.05 = phi i32 [ 0, %entry ], [ %add, %for.body ] @@ -70,3 +72,26 @@ for.cond.cleanup: ret i32 %add } + +; Don't a volatile load past volatile load. +define i32 @test4(i32* noalias nocapture readonly %a, i32* %v) nounwind uwtable { +; CHECK-LABEL: @test4( +entry: + br label %for.body + +; CHECK: for.body: +; CHECK: load volatile i32 +; CHECK-NEXT: load volatile i32 +for.body: + %i.06 = phi i32 [ 0, %entry ], [ %inc, %for.body ] + %x.05 = phi i32 [ 0, %entry ], [ %add, %for.body ] + %xxx = load volatile i32, i32* %v, align 4 + %i1 = load volatile i32, i32* %a, align 4 + %add = add nsw i32 %i1, %x.05 + %inc = add nuw nsw i32 %i.06, 1 + %exitcond = icmp eq i32 %inc, 1000 + br i1 %exitcond, label %for.cond.cleanup, label %for.body + +for.cond.cleanup: + ret i32 %add +} Index: test/Transforms/LICM/sinking.ll =================================================================== --- test/Transforms/LICM/sinking.ll +++ test/Transforms/LICM/sinking.ll @@ -742,11 +742,21 @@ ret i32 %idx } -; We do not support splitting a landingpad block if BlockColors is not empty. ; CHECK-LABEL: @test22 -; CHECK-LABEL: while.body2 -; CHECK-LABEL: %mul -; CHECK-NOT: lpadBB.split{{.*}} +; CHECK: lpadBB.split.loop.exit: +; CHECK-NEXT: %v.lcssa = phi i32 [ %v, %while.body2 ] +; CHECK-NEXT: %lpad.split.loop.exit = landingpad { i8*, i32 } +; CHECK-NEXT: catch i8* null +; CHECK-NEXT: %mul.le = mul i32 %v.lcssa, %v2 +; CHECK-NEXT: br label %lpadBB +; CHECK: lpadBB.split.loop.exit.split-lp: +; CHECK-NEXT: %.lcssa1.ph1 = phi i32 [ 0, %while.body ] +; CHECK-NEXT: %lpad.split.loop.exit.split-lp = landingpad { i8*, i32 } +; CHECK-NEXT: catch i8* null +; CHECK-NEXT: br label %lpadBB +; CHECK: lpadBB: +; CHECK-NEXT: %.lcssa1 = phi i32 [ %mul.le, %lpadBB.split.loop.exit ], [ %.lcssa1.ph1, %lpadBB.split.loop.exit.split-lp ] +; CHECK-NEXT: br label %lpadBBSucc1 define void @test22(i1 %b, i32 %v1, i32 %v2) personality i32 (...)* @__CxxFrameHandler3 { entry: br label %while.cond