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 { @@ -41,11 +42,7 @@ // Used to update funclet bundle operands. DenseMap BlockColors; - LoopSafetyInfo(Loop *L, DominatorTree *DT) { - // TODO: DT will later be used by ICF analysis that will come in a follow-up - // patch. So far we only need it to make signature changes properly. - if (DT) - (void)DT; + LoopSafetyInfo(Loop *L, DominatorTree *DT) : CurLoop(L), ICF(DT) { if (L) reset(L); } @@ -54,16 +51,23 @@ bool anyBlockMayThrow(); + bool mayThrowBefore(const BasicBlock *BB); + + bool mayThrowBefore(const Instruction *Insn); + + void invalidateBlock(const BasicBlock *BB); + void reset(Loop *L); private: - bool MayThrow = false; // The current loop contains an instruction which - // may throw. - bool HeaderMayThrow = false; // Same as previous, but specific to loop header // 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 Index: lib/Analysis/MustExecute.cpp =================================================================== --- lib/Analysis/MustExecute.cpp +++ lib/Analysis/MustExecute.cpp @@ -26,41 +26,83 @@ /// otherwise exit abnormally. bool LoopSafetyInfo::mayThrow(const BasicBlock *BB) { assert(CurLoop && "Should calculate the info first!"); - assert(CurLoop->getHeader() == BB && "Currently we only support header!"); - return HeaderMayThrow; + 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() { assert(CurLoop && "Should calculate the info first!"); - return MayThrow; + for (auto *BB : CurLoop->blocks()) + if (mayThrow(BB)) + return true; + return false; } -/// Computes loop safety information, checks loop body & header -/// for the possibility of may throw exception. -/// -void LoopSafetyInfo::reset(Loop *CurLoop) { - assert(CurLoop != nullptr && "CurLoop can't be null"); - this->CurLoop = CurLoop; - BasicBlock *Header = CurLoop->getHeader(); - // Setting default safety values. - MayThrow = false; - HeaderMayThrow = false; - // Iterate over header and compute safety info. - HeaderMayThrow = !isGuaranteedToTransferExecutionToSuccessor(Header); - - MayThrow = 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) && !MayThrow; ++BB) - MayThrow |= !isGuaranteedToTransferExecutionToSuccessor(*BB); +/// 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 && "Should calculate the info first!"); + 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) { + assert(CurLoop && "Should calculate the info first!"); + 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 && "Should calculate the info first!"); + 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) { + assert(L != nullptr && "Should never reset to null!"); + BlockColors.clear(); + ICF.clear(); + MayThrowBefore.clear(); + CurLoop = L; // Compute funclet colors if we might sink/hoist in a function with a funclet // personality routine. Function *Fn = CurLoop->getHeader()->getParent(); @@ -133,9 +175,8 @@ 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->anyBlockMayThrow()) + // 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 Index: lib/Transforms/Scalar/LICM.cpp =================================================================== --- lib/Transforms/Scalar/LICM.cpp +++ lib/Transforms/Scalar/LICM.cpp @@ -942,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; @@ -1057,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()); 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/hoist-mustexec.ll =================================================================== --- test/Transforms/LICM/hoist-mustexec.ll +++ test/Transforms/LICM/hoist-mustexec.ll @@ -429,3 +429,150 @@ 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 +}