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 RewriteLoopExitValuesWithoutBECount(Loop *L); Value *LinearFunctionTestReplace(Loop *L, const SCEV *BackedgeTakenCount, PHINode *IndVar, SCEVExpander &Rewriter); @@ -704,6 +705,76 @@ Rewriter.clearInsertPoint(); } +//===---------------------------------------------------------------------===// +// RewriteLoopExitValuesWithoutBECount: Rewrite loop exit values with their +// initial values from loop preheader. It will reduce phis generated by LCSSA. +//===---------------------------------------------------------------------===// + +/// 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. If the induction variable used in the exit path +/// has not been updated before the exit condition, it will keep its initial +/// value from loop preheader. Therefore, we can rewrite the exit value with +/// its initial value. As a side effect, the phi node generated by LCSSA is +/// no longer needed. +/// NOTE: this should also work if the induction variable has been updated +/// before the exit condition. In that case we need to replace it with the +/// first updated value. This is not supported in the current implementation. +void IndVarSimplify::RewriteLoopExitValuesWithoutBECount(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 (PHINode *PN = dyn_cast(begin++)) { + // We only deal with LCSSA phis. + if (PN->getNumIncomingValues() != 1) + continue; + + // Get condition that leads to the exit path. + auto *TermInst = PN->getIncomingBlock(0)->getTerminator(); + + Value *Cond = nullptr; + if (BranchInst *BI = dyn_cast(TermInst)) { + if (!BI->isConditional()) + continue; + Cond = BI->getCondition(); + } else if (SwitchInst *SI = dyn_cast(TermInst)) { + Cond = SI->getCondition(); + } + + // All non-instructions are loop-invariant. + if (auto *CondInst = dyn_cast(Cond)) + if (!L->hasLoopInvariantOperands(CondInst)) + continue; + + // Get the induction variable phi node, which should have one + // incoming block as loop preheader, and others as back edges. + auto *InductionPHI = + dyn_cast(PN->getIncomingValue(0)); + + if (!InductionPHI) + continue; + + // Rewrite the induction variable with its initial value from + // loop preheader. Note that the preheader could be in an outer + // loop and the initial value is an induction variable of that + // loop. For that case, further rewrite could possibly happen + // when process outer loop. + auto *LoopPreheader = L->getLoopPreheader(); + if (InductionPHI->getBasicBlockIndex(LoopPreheader) != -1) { + PN->setIncomingValue(0, + InductionPHI->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 +2132,9 @@ // loop may be sunk below the loop to reduce register pressure. SinkUnusedInvariants(L); + // Further clean up loop exit values. + RewriteLoopExitValuesWithoutBECount(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 if loop induction variable is updated +;; before loop exit condition, it should not be rewritten. +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