Index: include/llvm/Analysis/MustExecute.h =================================================================== --- include/llvm/Analysis/MustExecute.h +++ include/llvm/Analysis/MustExecute.h @@ -19,6 +19,7 @@ #include "llvm/ADT/DenseMap.h" #include "llvm/Analysis/EHPersonalities.h" +#include "llvm/Analysis/InstructionPrecedenceTracking.h" #include "llvm/Analysis/LoopInfo.h" #include "llvm/IR/BasicBlock.h" #include "llvm/IR/Dominators.h" @@ -47,8 +48,8 @@ class LoopSafetyInfo { bool MayThrow = false; // The current loop contains an instruction which // may throw. - bool HeaderMayThrow = false; // Same as previous, but specific to loop header - + // Contains information about implicit control flow in this loop's blocks. + mutable ImplicitControlFlowTracking ICF; /// Collect all blocks from \p CurLoop which lie on all possible paths from /// the header of \p CurLoop (inclusive) to BB (exclusive) into the set /// \p Predecessors. If \p BB is the header, \p Predecessors will be empty. @@ -60,21 +61,25 @@ // Used to update funclet bundle operands. DenseMap BlockColors; - /// Returns true iff the header block of the loop for which this info is - /// calculated contains an instruction that may throw or otherwise exit - /// abnormally. - bool headerMayThrow() const; - /// Returns true iff any block of the loop for which this info is contains an /// instruction that may throw or otherwise exit abnormally. bool anyBlockMayThrow() const; /// Return true if we must reach the block \p BB under assumption that the - /// loop \p CurLoop is entered and no instruction throws or otherwise exits - /// abnormally. + /// loop \p CurLoop is entered. bool allLoopPathsLeadToBlock(const Loop *CurLoop, const BasicBlock *BB, const DominatorTree *DT) const; + /// Return true if we must execute the instruction \p I under assumption that + /// the loop \p CurLoop is entered. + bool mustExecuteInLoop(const Loop *CurLoop, const Instruction *I, + const DominatorTree *DT) const; + + /// Drops cached information regarding the implicit control flow in block + /// \p BB. It should be called for every block in which we add or remove any + /// instructions. + void dropCachedInfo(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. @@ -82,11 +87,12 @@ /// LoopSafetyInfo. Some callers rely on this fact. void computeLoopSafetyInfo(Loop *); - LoopSafetyInfo() = default; + LoopSafetyInfo(DominatorTree *DT): ICF(DT) {} }; /// Returns true if the instruction in a loop is guaranteed to execute at least /// once (under the assumption that the loop is entered). +/// TODO: Remove the function, call SafetyInfo->mustExecuteInLoop instead. bool isGuaranteedToExecute(const Instruction &Inst, const DominatorTree *DT, const Loop *CurLoop, const LoopSafetyInfo *SafetyInfo); Index: lib/Analysis/MustExecute.cpp =================================================================== --- lib/Analysis/MustExecute.cpp +++ lib/Analysis/MustExecute.cpp @@ -22,29 +22,20 @@ #include "llvm/Support/raw_ostream.h" using namespace llvm; -bool LoopSafetyInfo::headerMayThrow() const { - return HeaderMayThrow; -} - bool LoopSafetyInfo::anyBlockMayThrow() const { return MayThrow; } void LoopSafetyInfo::computeLoopSafetyInfo(Loop *CurLoop) { assert(CurLoop != nullptr && "CurLoop can't be null"); - BasicBlock *Header = CurLoop->getHeader(); - // 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); + ICF.clear(); + MayThrow = false; + // Figure out the fact that at least one block may throw. + for (auto &BB : CurLoop->blocks()) + if (ICF.hasICF(&*BB)) { + MayThrow = true; + break; + } // Compute funclet colors if we might sink/hoist in a function with a funclet // personality routine. @@ -148,7 +139,10 @@ // 3) Exit blocks which are not taken on 1st iteration. // Memoize blocks we've already checked. SmallPtrSet CheckedSuccessors; - for (auto *Pred : Predecessors) + for (auto *Pred : Predecessors) { + // Check if we can exit via throw or other abnormal exit. + if (ICF.hasICF(Pred)) + return false; for (auto *Succ : successors(Pred)) if (CheckedSuccessors.insert(Succ).second && Succ != BB && !Predecessors.count(Succ)) @@ -169,42 +163,29 @@ if (CurLoop->contains(Succ) || !CanProveNotTakenFirstIteration(Succ, DT, CurLoop)) return false; + } // All predecessors can only lead us to BB. return true; } +bool LoopSafetyInfo::mustExecuteInLoop(const Loop *CurLoop, + const Instruction *I, + const DominatorTree *DT) const { + return !ICF.isDominatedByICFIFromSameBlock(I) && + allLoopPathsLeadToBlock(CurLoop, I->getParent(), DT); +} + +void LoopSafetyInfo::dropCachedInfo(const BasicBlock *BB) { + ICF.invalidateBlock(BB); +} + /// 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 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() || - Inst.getParent()->getFirstNonPHIOrDbg() == &Inst; - - // Somewhere in this loop there is an instruction which may throw and make us - // exit the loop. - if (SafetyInfo->anyBlockMayThrow()) - return false; - - // If there is a path from header to exit or latch that doesn't lead to our - // instruction's block, return false. - if (!SafetyInfo->allLoopPathsLeadToBlock(CurLoop, Inst.getParent(), DT)) - return false; - - return true; + return SafetyInfo->mustExecuteInLoop(CurLoop, &Inst, DT); } @@ -240,7 +221,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; + LoopSafetyInfo LSI(DT); LSI.computeLoopSafetyInfo(L); 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 @@ -267,7 +267,7 @@ BasicBlock *Preheader = L->getLoopPreheader(); // Compute loop safety information. - LoopSafetyInfo SafetyInfo; + LoopSafetyInfo SafetyInfo(DT); SafetyInfo.computeLoopSafetyInfo(L); // We want to visit all of the instructions in this loop... that are not parts @@ -404,6 +404,7 @@ LLVM_DEBUG(dbgs() << "LICM deleting dead inst: " << I << '\n'); salvageDebugInfo(I); ++II; + SafetyInfo->dropCachedInfo(BB); CurAST->deleteValue(&I); I.eraseFromParent(); Changed = true; @@ -423,6 +424,8 @@ if (!FreeInLoop) { ++II; CurAST->deleteValue(&I); + // Dropping SafetyInfo is already done within sink, so no need for + // it here. I.eraseFromParent(); } Changed = true; @@ -484,6 +487,7 @@ CurAST->deleteValue(&I); I.eraseFromParent(); } + SafetyInfo->dropCachedInfo(BB); Changed = true; continue; } @@ -508,6 +512,9 @@ if (I.getOpcode() == Instruction::FDiv && CurLoop->isLoopInvariant(I.getOperand(1)) && I.hasAllowReciprocal()) { + // We are going to make changes to BB which means we need to invalidate + // cached info to have valid info by the moment of hoist. + SafetyInfo->dropCachedInfo(BB); auto Divisor = I.getOperand(1); auto One = llvm::ConstantFP::get(Divisor->getType(), 1.0); auto ReciprocalDivisor = BinaryOperator::CreateFDiv(One, Divisor); @@ -1013,6 +1020,10 @@ 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->dropCachedInfo(I.getParent()); + bool Changed = false; if (isa(I)) ++NumMovedLoads; @@ -1045,6 +1056,8 @@ // unreachable. BasicBlock *BB = PN->getIncomingBlock(U); if (!DT->isReachableFromEntry(BB)) { + // No need to invalidate the safety info here: U's parent is not a part of + // the loop. U = UndefValue::get(I.getType()); Changed = true; continue; @@ -1096,6 +1109,8 @@ // The PHI must be trivially replaceable. Instruction *New = sinkThroughTriviallyReplaceablePHI(PN, &I, LI, SunkCopies, SafetyInfo, CurLoop); + // Invalidation of SafetyInfo is not required because PN is outside the + // loop. PN->replaceAllUsesWith(New); PN->eraseFromParent(); Changed = true; @@ -1127,6 +1142,8 @@ !isGuaranteedToExecute(I, DT, CurLoop, SafetyInfo)) I.dropUnknownNonDebugMetadata(); + // Contents of a block has changed, we need to mark it in safety info. + SafetyInfo->dropCachedInfo(I.getParent()); // Move the new node to the Preheader, before its terminator. I.moveBefore(Preheader->getTerminator()); Index: lib/Transforms/Scalar/LoopIdiomRecognize.cpp =================================================================== --- lib/Transforms/Scalar/LoopIdiomRecognize.cpp +++ lib/Transforms/Scalar/LoopIdiomRecognize.cpp @@ -319,7 +319,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); SafetyInfo.computeLoopSafetyInfo(CurLoop); if (SafetyInfo.anyBlockMayThrow()) return MadeChange; Index: lib/Transforms/Scalar/LoopUnswitch.cpp =================================================================== --- lib/Transforms/Scalar/LoopUnswitch.cpp +++ lib/Transforms/Scalar/LoopUnswitch.cpp @@ -184,7 +184,7 @@ BasicBlock *loopPreheader = nullptr; bool SanitizeMemory; - LoopSafetyInfo SafetyInfo; + 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 @@ -515,12 +515,14 @@ LI = &getAnalysis().getLoopInfo(); LPM = &LPM_Ref; DT = &getAnalysis().getDomTree(); + LoopSafetyInfo LSI(DT); + SafetyInfo = &LSI; currentLoop = L; Function *F = currentLoop->getHeader()->getParent(); SanitizeMemory = F->hasFnAttribute(Attribute::SanitizeMemory); if (SanitizeMemory) - SafetyInfo.computeLoopSafetyInfo(L); + SafetyInfo->computeLoopSafetyInfo(L); bool Changed = false; do { @@ -699,7 +701,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/LoopUnrollAndJam.cpp =================================================================== --- lib/Transforms/Utils/LoopUnrollAndJam.cpp +++ lib/Transforms/Utils/LoopUnrollAndJam.cpp @@ -761,7 +761,7 @@ } // Check the loop safety info for exceptions. - LoopSafetyInfo LSI; + LoopSafetyInfo LSI(&DT); LSI.computeLoopSafetyInfo(L); if (LSI.anyBlockMayThrow()) { LLVM_DEBUG(dbgs() << "Won't unroll-and-jam; Something may throw\n"); 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 @@ -59,6 +60,7 @@ ; 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: call void @maythrow_and_use(i32 %v) ; (mustexec in: loop) ; CHECK-NOT: mustexec entry: Index: test/Transforms/LICM/guards.ll =================================================================== --- test/Transforms/LICM/guards.ll +++ test/Transforms/LICM/guards.ll @@ -84,15 +84,15 @@ } -; TODO: We can also hoist this load and guard from mustexec non-header block. +; TODO: We can also hoist this guard from mustexec non-header block. define void @test4(i1 %c, i32* %p) { ; CHECK-LABEL: @test4( ; CHECK-LABEL: entry: -; CHECK-LABEL: loop: -; CHECK-LABEL: backedge: ; CHECK: %a = load i32, i32* %p ; CHECK: %invariant_cond = icmp ne i32 %a, 100 +; CHECK-LABEL: loop: +; CHECK-LABEL: backedge: ; CHECK: call void (i1, ...) @llvm.experimental.guard(i1 %invariant_cond) entry: Index: test/Transforms/LICM/hoist-mustexec.ll =================================================================== --- test/Transforms/LICM/hoist-mustexec.ll +++ test/Transforms/LICM/hoist-mustexec.ll @@ -455,3 +455,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 +} \ No newline at end of file Index: test/Transforms/LICM/preheader-safe.ll =================================================================== --- test/Transforms/LICM/preheader-safe.ll +++ test/Transforms/LICM/preheader-safe.ll @@ -112,11 +112,31 @@ exit: ret void } + +; Positive test - can hoist something that happens before thrower. +define void @nothrow_header_pos(i64 %x, i64 %y, i1 %cond) { +; CHECK-LABEL: nothrow_header_pos +; CHECK-LABEL: entry +; CHECK: %div = udiv i64 %x, %y +; CHECK-LABEL: loop +; CHECK: call void @use(i64 %div) +entry: + br label %loop +loop: ; preds = %entry, %for.inc + br label %loop-if +loop-if: + %div = udiv i64 %x, %y + call void @use(i64 %div) + br label %loop +} + + ; Negative test - can't move out of throwing block define void @nothrow_header_neg(i64 %x, i64 %y, i1 %cond) { ; CHECK-LABEL: nothrow_header_neg ; CHECK-LABEL: entry ; CHECK-LABEL: loop +; CHECK: call void @maythrow() ; CHECK: %div = udiv i64 %x, %y ; CHECK: call void @use(i64 %div) entry: @@ -124,6 +144,7 @@ loop: ; preds = %entry, %for.inc br label %loop-if loop-if: + call void @maythrow() %div = udiv i64 %x, %y call void @use(i64 %div) br label %loop