Index: llvm/trunk/include/llvm/Transforms/Utils/LoopUtils.h =================================================================== --- llvm/trunk/include/llvm/Transforms/Utils/LoopUtils.h +++ llvm/trunk/include/llvm/Transforms/Utils/LoopUtils.h @@ -109,7 +109,7 @@ /// arguments. Diagnostics is emitted via \p ORE. It returns changed status. bool sinkRegion(DomTreeNode *, AliasAnalysis *, LoopInfo *, DominatorTree *, TargetLibraryInfo *, TargetTransformInfo *, Loop *, - AliasSetTracker *, LoopSafetyInfo *, + AliasSetTracker *, ICFLoopSafetyInfo *, OptimizationRemarkEmitter *ORE); /// Walk the specified region of the CFG (defined by all blocks @@ -122,7 +122,7 @@ /// ORE. It returns changed status. bool hoistRegion(DomTreeNode *, AliasAnalysis *, LoopInfo *, DominatorTree *, TargetLibraryInfo *, Loop *, AliasSetTracker *, - LoopSafetyInfo *, OptimizationRemarkEmitter *ORE); + ICFLoopSafetyInfo *, OptimizationRemarkEmitter *ORE); /// This function deletes dead loops. The caller of this function needs to /// guarantee that the loop is infact dead. @@ -151,7 +151,8 @@ SmallVectorImpl &, PredIteratorCache &, LoopInfo *, DominatorTree *, const TargetLibraryInfo *, - Loop *, AliasSetTracker *, LoopSafetyInfo *, + Loop *, AliasSetTracker *, + ICFLoopSafetyInfo *, OptimizationRemarkEmitter *); /// Does a BFS from a given node to all of its children inside a given loop. Index: llvm/trunk/lib/Transforms/Scalar/LICM.cpp =================================================================== --- llvm/trunk/lib/Transforms/Scalar/LICM.cpp +++ llvm/trunk/lib/Transforms/Scalar/LICM.cpp @@ -103,10 +103,10 @@ const LoopSafetyInfo *SafetyInfo, TargetTransformInfo *TTI, bool &FreeInLoop); static void hoist(Instruction &I, const DominatorTree *DT, const Loop *CurLoop, - LoopSafetyInfo *SafetyInfo, + ICFLoopSafetyInfo *SafetyInfo, OptimizationRemarkEmitter *ORE); static bool sink(Instruction &I, LoopInfo *LI, DominatorTree *DT, - const Loop *CurLoop, LoopSafetyInfo *SafetyInfo, + const Loop *CurLoop, ICFLoopSafetyInfo *SafetyInfo, OptimizationRemarkEmitter *ORE, bool FreeInLoop); static bool isSafeToExecuteUnconditionally(Instruction &Inst, const DominatorTree *DT, @@ -123,7 +123,8 @@ const LoopInfo *LI, const LoopSafetyInfo *SafetyInfo); -static void eraseInstruction(Instruction &I, AliasSetTracker *AST); +static void eraseInstruction(Instruction &I, ICFLoopSafetyInfo &SafetyInfo, + AliasSetTracker *AST); namespace { struct LoopInvariantCodeMotion { @@ -269,7 +270,7 @@ BasicBlock *Preheader = L->getLoopPreheader(); // Compute loop safety information. - SimpleLoopSafetyInfo SafetyInfo; + ICFLoopSafetyInfo SafetyInfo(DT); SafetyInfo.computeLoopSafetyInfo(L); // We want to visit all of the instructions in this loop... that are not parts @@ -376,7 +377,7 @@ bool llvm::sinkRegion(DomTreeNode *N, AliasAnalysis *AA, LoopInfo *LI, DominatorTree *DT, TargetLibraryInfo *TLI, TargetTransformInfo *TTI, Loop *CurLoop, - AliasSetTracker *CurAST, LoopSafetyInfo *SafetyInfo, + AliasSetTracker *CurAST, ICFLoopSafetyInfo *SafetyInfo, OptimizationRemarkEmitter *ORE) { // Verify inputs. @@ -406,7 +407,7 @@ LLVM_DEBUG(dbgs() << "LICM deleting dead inst: " << I << '\n'); salvageDebugInfo(I); ++II; - eraseInstruction(I, CurAST); + eraseInstruction(I, *SafetyInfo, CurAST); Changed = true; continue; } @@ -423,7 +424,7 @@ if (sink(I, LI, DT, CurLoop, SafetyInfo, ORE, FreeInLoop)) { if (!FreeInLoop) { ++II; - eraseInstruction(I, CurAST); + eraseInstruction(I, *SafetyInfo, CurAST); } Changed = true; } @@ -440,7 +441,7 @@ /// bool llvm::hoistRegion(DomTreeNode *N, AliasAnalysis *AA, LoopInfo *LI, DominatorTree *DT, TargetLibraryInfo *TLI, Loop *CurLoop, - AliasSetTracker *CurAST, LoopSafetyInfo *SafetyInfo, + AliasSetTracker *CurAST, ICFLoopSafetyInfo *SafetyInfo, OptimizationRemarkEmitter *ORE) { // Verify inputs. assert(N != nullptr && AA != nullptr && LI != nullptr && DT != nullptr && @@ -481,7 +482,7 @@ CurAST->copyValue(&I, C); I.replaceAllUsesWith(C); if (isInstructionTriviallyDead(&I, TLI)) - eraseInstruction(I, CurAST); + eraseInstruction(I, *SafetyInfo, CurAST); Changed = true; continue; } @@ -510,14 +511,16 @@ auto One = llvm::ConstantFP::get(Divisor->getType(), 1.0); auto ReciprocalDivisor = BinaryOperator::CreateFDiv(One, Divisor); ReciprocalDivisor->setFastMathFlags(I.getFastMathFlags()); + SafetyInfo->insertInstructionTo(I.getParent()); ReciprocalDivisor->insertBefore(&I); auto Product = BinaryOperator::CreateFMul(I.getOperand(0), ReciprocalDivisor); Product->setFastMathFlags(I.getFastMathFlags()); + SafetyInfo->insertInstructionTo(I.getParent()); Product->insertAfter(&I); I.replaceAllUsesWith(Product); - eraseInstruction(I, CurAST); + eraseInstruction(I, *SafetyInfo, CurAST); hoist(*ReciprocalDivisor, DT, CurLoop, SafetyInfo, ORE); Changed = true; @@ -886,9 +889,11 @@ return New; } -static void eraseInstruction(Instruction &I, AliasSetTracker *AST) { +static void eraseInstruction(Instruction &I, ICFLoopSafetyInfo &SafetyInfo, + AliasSetTracker *AST) { if (AST) AST->deleteValue(&I); + SafetyInfo.removeInstruction(&I); I.eraseFromParent(); } @@ -999,7 +1004,7 @@ /// position, and may either delete it or move it to outside of the loop. /// static bool sink(Instruction &I, LoopInfo *LI, DominatorTree *DT, - const Loop *CurLoop, LoopSafetyInfo *SafetyInfo, + const Loop *CurLoop, ICFLoopSafetyInfo *SafetyInfo, OptimizationRemarkEmitter *ORE, bool FreeInLoop) { LLVM_DEBUG(dbgs() << "LICM sinking instruction: " << I << "\n"); ORE->emit([&]() { @@ -1090,7 +1095,7 @@ Instruction *New = sinkThroughTriviallyReplaceablePHI(PN, &I, LI, SunkCopies, SafetyInfo, CurLoop); PN->replaceAllUsesWith(New); - eraseInstruction(*PN, nullptr); + eraseInstruction(*PN, *SafetyInfo, nullptr); Changed = true; } return Changed; @@ -1100,7 +1105,7 @@ /// is safe to hoist, this instruction is called to do the dirty work. /// static void hoist(Instruction &I, const DominatorTree *DT, const Loop *CurLoop, - LoopSafetyInfo *SafetyInfo, OptimizationRemarkEmitter *ORE) { + ICFLoopSafetyInfo *SafetyInfo, OptimizationRemarkEmitter *ORE) { auto *Preheader = CurLoop->getLoopPreheader(); LLVM_DEBUG(dbgs() << "LICM hoisting to " << Preheader->getName() << ": " << I << "\n"); @@ -1120,6 +1125,8 @@ !SafetyInfo->isGuaranteedToExecute(I, DT, CurLoop)) I.dropUnknownNonDebugMetadata(); + SafetyInfo->removeInstruction(&I); + SafetyInfo->insertInstructionTo(Preheader); // Move the new node to the Preheader, before its terminator. I.moveBefore(Preheader->getTerminator()); @@ -1180,6 +1187,7 @@ int Alignment; bool UnorderedAtomic; AAMDNodes AATags; + ICFLoopSafetyInfo &SafetyInfo; Value *maybeInsertLCSSAPHI(Value *V, BasicBlock *BB) const { if (Instruction *I = dyn_cast(V)) @@ -1202,11 +1210,13 @@ SmallVectorImpl &LEB, SmallVectorImpl &LIP, PredIteratorCache &PIC, AliasSetTracker &ast, LoopInfo &li, DebugLoc dl, int alignment, - bool UnorderedAtomic, const AAMDNodes &AATags) + bool UnorderedAtomic, const AAMDNodes &AATags, + ICFLoopSafetyInfo &SafetyInfo) : LoadAndStorePromoter(Insts, S), SomePtr(SP), PointerMustAliases(PMA), LoopExitBlocks(LEB), LoopInsertPts(LIP), PredCache(PIC), AST(ast), LI(li), DL(std::move(dl)), Alignment(alignment), - UnorderedAtomic(UnorderedAtomic), AATags(AATags) {} + UnorderedAtomic(UnorderedAtomic), AATags(AATags), SafetyInfo(SafetyInfo) + {} bool isInstInList(Instruction *I, const SmallVectorImpl &) const override { @@ -1243,7 +1253,10 @@ // Update alias analysis. AST.copyValue(LI, V); } - void instructionDeleted(Instruction *I) const override { AST.deleteValue(I); } + void instructionDeleted(Instruction *I) const override { + SafetyInfo.removeInstruction(I); + AST.deleteValue(I); + } }; @@ -1281,7 +1294,7 @@ SmallVectorImpl &ExitBlocks, SmallVectorImpl &InsertPts, PredIteratorCache &PIC, LoopInfo *LI, DominatorTree *DT, const TargetLibraryInfo *TLI, - Loop *CurLoop, AliasSetTracker *CurAST, LoopSafetyInfo *SafetyInfo, + Loop *CurLoop, AliasSetTracker *CurAST, ICFLoopSafetyInfo *SafetyInfo, OptimizationRemarkEmitter *ORE) { // Verify inputs. assert(LI != nullptr && DT != nullptr && CurLoop != nullptr && @@ -1500,7 +1513,7 @@ SSAUpdater SSA(&NewPHIs); LoopPromoter Promoter(SomePtr, LoopUses, SSA, PointerMustAliases, ExitBlocks, InsertPts, PIC, *CurAST, *LI, DL, Alignment, - SawUnorderedAtomic, AATags); + SawUnorderedAtomic, AATags, *SafetyInfo); // Set up the preheader to have a definition of the value. It is the live-out // value from the preheader that uses in the loop will use. @@ -1520,7 +1533,7 @@ // If the SSAUpdater didn't use the load in the preheader, just zap it now. if (PreheaderLoad->use_empty()) - eraseInstruction(*PreheaderLoad, CurAST); + eraseInstruction(*PreheaderLoad, *SafetyInfo, CurAST); return true; } Index: llvm/trunk/test/CodeGen/AMDGPU/build-vector-insert-elt-infloop.ll =================================================================== --- llvm/trunk/test/CodeGen/AMDGPU/build-vector-insert-elt-infloop.ll +++ llvm/trunk/test/CodeGen/AMDGPU/build-vector-insert-elt-infloop.ll @@ -18,7 +18,7 @@ %tmp4 = bitcast half %tmp3 to i16 %tmp5 = insertelement <2 x i16> , i16 %tmp4, i32 1 %tmp6 = bitcast i16* %arg to half* - store half %tmp2, half* %tmp6, align 2 + store volatile half %tmp2, half* %tmp6, align 2 %tmp7 = bitcast <2 x i16> %tmp to <2 x half> %tmp8 = extractelement <2 x half> %tmp7, i32 0 br label %bb1 Index: llvm/trunk/test/Transforms/LICM/guards.ll =================================================================== --- llvm/trunk/test/Transforms/LICM/guards.ll +++ llvm/trunk/test/Transforms/LICM/guards.ll @@ -85,15 +85,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: llvm/trunk/test/Transforms/LICM/hoist-mustexec.ll =================================================================== --- llvm/trunk/test/Transforms/LICM/hoist-mustexec.ll +++ llvm/trunk/test/Transforms/LICM/hoist-mustexec.ll @@ -456,3 +456,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: llvm/trunk/test/Transforms/LICM/hoist-nounwind.ll =================================================================== --- llvm/trunk/test/Transforms/LICM/hoist-nounwind.ll +++ llvm/trunk/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: llvm/trunk/test/Transforms/LICM/preheader-safe.ll =================================================================== --- llvm/trunk/test/Transforms/LICM/preheader-safe.ll +++ llvm/trunk/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