Index: lib/Transforms/Scalar/IndVarSimplify.cpp =================================================================== --- lib/Transforms/Scalar/IndVarSimplify.cpp +++ lib/Transforms/Scalar/IndVarSimplify.cpp @@ -134,6 +134,7 @@ bool CanLoopBeDeleted(Loop *L, SmallVector &RewritePhiSet); void RewriteLoopExitValues(Loop *L, SCEVExpander &Rewriter); + void RewriteFirstIterationLoopExitValues(Loop *L); Value *LinearFunctionTestReplace(Loop *L, const SCEV *BackedgeTakenCount, PHINode *IndVar, SCEVExpander &Rewriter); @@ -704,6 +705,73 @@ Rewriter.clearInsertPoint(); } +//===---------------------------------------------------------------------===// +// RewriteFirstIterationLoopExitValues: Rewrite loop exit values if we know +// they will exit at the first iteration. +//===---------------------------------------------------------------------===// + +/// Check to see if this loop has loop invariant conditions which lead to loop +/// exits. If so, we know that if the exit path is taken, it is at the first +/// loop iteration. This lets us predict exit values of PHI nodes that live in +/// loop header. +void IndVarSimplify::RewriteFirstIterationLoopExitValues(Loop *L) { + // Verify the input to the pass is already in LCSSA form. + assert(L->isLCSSAForm(*DT)); + + SmallVector ExitBlocks; + L->getUniqueExitBlocks(ExitBlocks); + + for (auto *ExitBB : ExitBlocks) { + BasicBlock::iterator begin = ExitBB->begin(); + // If there are no more PHI nodes in this exit block, then no more + // values defined inside the loop are used on this path. + while (auto *PN = dyn_cast(begin++)) { + for (unsigned IncomingValIdx = 0, e = PN->getNumIncomingValues(); + IncomingValIdx != e; ++IncomingValIdx) { + auto *IncomingBB = PN->getIncomingBlock(IncomingValIdx); + if (!L->contains(IncomingBB)) + continue; + + // Get condition that leads to the exit path. + auto *TermInst = IncomingBB->getTerminator(); + + Value *Cond = nullptr; + if (auto *BI = dyn_cast(TermInst)) { + // Must be a conditional branch, otherwise the block + // should not be in the loop. + Cond = BI->getCondition(); + } else if (auto *SI = dyn_cast(TermInst)) { + Cond = SI->getCondition(); + } + + // All non-instructions are loop-invariant. + if (auto *CondInst = dyn_cast(Cond)) + if (!L->makeLoopInvariant(CondInst, Changed)) + continue; + + auto *ExitVal = + dyn_cast(PN->getIncomingValue(IncomingValIdx)); + + // Only deal with PHIs. + if (!ExitVal) + continue; + + // If ExitVal is a PHI on the loop header, then we know its + // value along this exit because the exit can only be taken + // on the first iteration. + auto *LoopPreheader = L->getLoopPreheader(); + assert(LoopPreheader && "Invalid loop"); + if (ExitVal->getBasicBlockIndex(LoopPreheader) != -1) { + assert(ExitVal->getParent() == L->getHeader() && + "ExitVal must be in loop header"); + PN->setIncomingValue(IncomingValIdx, + ExitVal->getIncomingValueForBlock(LoopPreheader)); + } + } + } + } +} + /// Check whether it is possible to delete the loop after rewriting exit /// value. If it is possible, ignore ReplaceExitValue and do rewriting /// aggressively. @@ -2061,6 +2129,11 @@ // loop may be sunk below the loop to reduce register pressure. SinkUnusedInvariants(L); + // RewriteFirstIterationLoopExitValues does not rely on the computation of + // trip count and therefore can further simplify exit values in addition to + // RewriteLoopExitValues. + RewriteFirstIterationLoopExitValues(L); + // Clean up dead instructions. Changed |= DeleteDeadPHIs(L->getHeader(), TLI); // Check a post-condition. Index: test/Transforms/IndVarSimplify/rewrite-loop-exit-value.ll =================================================================== --- /dev/null +++ test/Transforms/IndVarSimplify/rewrite-loop-exit-value.ll @@ -0,0 +1,75 @@ +; RUN: opt -indvars -instcombine -S < %s | FileCheck %s + +;; Test that loop's exit value is rewritten to its initial +;; value from loop preheader +define i32 @test1(i32* %var) { +; CHECK-LABEL: @test1 +entry: + br label %header + +header: + %phi_indvar = phi i32 [0, %entry], [%indvar, %loop] + %cond = icmp eq i32* %var, null + br i1 %cond, label %loop, label %exit + +loop: + %indvar = add i32 %phi_indvar, 1 + br label %header + +exit: +; CHECK: ret i32 0 + ret i32 %phi_indvar +} + + +;; Test that inner loop's exit value is first rewritten to outer +;; loop's induction variable, and then further rewritten to a +;; constant when process outer loop. +define i32 @test2(i32* %var) { +; CHECK-LABEL: @test2 +entry: + br label %outer_header + +outer_header: + %phi_outer = phi i32 [0, %entry], [%indvar_outer, %inner_exit] + br label %inner_header + +inner_header: + %phi_inner = phi i32 [%phi_outer, %outer_header], [%indvar_inner, %loop] + %cond1 = icmp eq i32* %var, null + br i1 %cond1, label %loop, label %exit + +loop: + %indvar_inner = add i32 %phi_inner, 1 + %cond2 = icmp eq i32 %indvar_inner, 10 + br i1 %cond2, label %inner_header, label %inner_exit + +inner_exit: + %indvar_outer = add i32 %phi_outer, 1 + br label %outer_header + +exit: +;; %phi_inner is first rewritten to %phi_outer +;; and then %phi_outer is rewritten to 0 + %ret_val = add i32 %phi_inner, %phi_outer +; CHECK: ret i32 0 + ret i32 %ret_val +} + +;; Test that we can not rewrite loop exit value if it's not +;; a phi node (%indvar is an add instruction in this test). +define i32 @test3(i32* %var) { +; CHECK-LABEL: @test3 +entry: + br label %header + +header: + %phi_indvar = phi i32 [0, %entry], [%indvar, %header] + %indvar = add i32 %phi_indvar, 1 + %cond = icmp eq i32* %var, null + br i1 %cond, label %header, label %exit + +exit: +; CHECK: ret i32 %indvar + ret i32 %indvar +} \ No newline at end of file Index: test/Transforms/LoopUnroll/scevunroll.ll =================================================================== --- test/Transforms/LoopUnroll/scevunroll.ll +++ test/Transforms/LoopUnroll/scevunroll.ll @@ -184,7 +184,7 @@ ; CHECK: for.body: ; CHECK: %b.03 = phi i32 [ 0, %entry ], [ %add, %for.cond ] ; CHECK: return: -; CHECK: %b.03.lcssa = phi i32 [ %b.03, %for.body ], [ %b.03, %for.cond ] +; CHECK: %b.03.lcssa = phi i32 [ %b.03, %for.body ], [ 0, %for.cond ] define void @nsw_latch(i32* %a) nounwind { entry: br label %for.body