[IndVars] Replace PHIs if loop exits on 1st iteration

[dmakogon]

Summary

This is a part of https://reviews.llvm.org/D108910
We replace all loop PHIs with values coming from the loop preheader if we proved that backedge is never taken.

[lebedev.ri]

LG

[reames]

Reverted patch due to issue caught in post commit review. See inline.

llvm/lib/Transforms/Scalar/IndVarSimplify.cpp

1317

As written, this code does not preserve LCSSA. Consider the case where we have two sibling loops and the header of the second is directly an exit block of the first. This is not loop simplify form (i.e. no preheader), but it is a possible case.

[mkazantsev]

llvm/lib/Transforms/Scalar/IndVarSimplify.cpp

1317

Philip, there is an assert on line 1741 that the loop is in simplify form. I don't think the situation you are referring to is even possible.

[reames]

Just to close the loop here, I agree with Max that the case I was concerned about was not possible due to an earlier bail out. The reapply of the reverted patch and the added assert resolve my concern entirely. Thanks.

(Sorry for delayed response, took a vacation last week and thus only seeing this now.)

llvm/lib/Transforms/Scalar/IndVarSimplify.cpp

static void foldExit(const Loop *L, BasicBlock *ExitingBB, bool IsTaken,
   BranchInst *BI = cast<BranchInst>(ExitingBB->getTerminator());
   bool ExitIfTrue = !L->contains(*succ_begin(ExitingBB));
   auto *OldCond = BI->getCondition();
   auto *NewCond =
       ConstantInt::get(OldCond->getType(), IsTaken ? ExitIfTrue : !ExitIfTrue);
   replaceExitCond(BI, NewCond, DeadInsts);
 }
 
+static void replaceLoopPHINodesWithPreheaderValues(
+    Loop *L, SmallVectorImpl<WeakTrackingVH> &DeadInsts) {
+  auto *LoopPreheader = L->getLoopPreheader();
+  auto *LoopHeader = L->getHeader();
+  for (auto &PN : LoopHeader->phis()) {
+    auto *PreheaderIncoming = PN.getIncomingValueForBlock(LoopPreheader);
+    PN.replaceAllUsesWith(PreheaderIncoming);
+    DeadInsts.emplace_back(&PN);
+  }
+}
+
 static void replaceWithInvariantCond(
     const Loop *L, BasicBlock *ExitingBB, ICmpInst::Predicate InvariantPred,
     const SCEV *InvariantLHS, const SCEV *InvariantRHS, SCEVExpander &Rewriter,
     SmallVectorImpl<WeakTrackingVH> &DeadInsts) {
   BranchInst *BI = cast<BranchInst>(ExitingBB->getTerminator());
   Rewriter.setInsertPoint(BI);
   auto *LHSV = Rewriter.expandCodeFor(InvariantLHS);
   auto *RHSV = Rewriter.expandCodeFor(InvariantRHS);
for (BasicBlock *ExitingBB : ExitingBlocks) {
     if (MaxExitCount == ExitCount)
       // If the loop has more than 1 iteration, all further checks will be
       // executed 1 iteration less.
       SkipLastIter = true;
 
     // If we know we'd exit on the first iteration, rewrite the exit to
     // reflect this.  This does not imply the loop must exit through this
     // exit; there may be an earlier one taken on the first iteration.
-    // TODO: Given we know the backedge can't be taken, we should go ahead
-    // and break it.  Or at least, kill all the header phis and simplify.
+    // We know that the backedge can't be taken, so we replace all
+    // the header PHIs with values coming from the preheader.
     if (ExitCount->isZero()) {
       foldExit(L, ExitingBB, true, DeadInsts);
+      replaceLoopPHINodesWithPreheaderValues(L, DeadInsts);
       Changed = true;
       continue;
     }
 
     assert(ExitCount->getType()->isIntegerTy() &&
            MaxExitCount->getType()->isIntegerTy() &&
            "Exit counts must be integers");
 

llvm/test/Transforms/IndVarSimplify/eliminate-backedge.ll

 define i1 @kill_backedge_and_phis(i8* align 1 %lhs, i8* align 1 %rhs, i32 %len) {
 ; CHECK-LABEL: @kill_backedge_and_phis(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    %length_not_zero = icmp ne i32 %len, 0
 ; CHECK-NEXT:    br i1 %length_not_zero, label %loop_preheader, label %exit
 ; CHECK:       loop_preheader:
 ; CHECK-NEXT:    br label %loop
 ; CHECK:       loop:
-; CHECK-NEXT:    %iv = phi i32 [ 0, %loop_preheader ], [ %iv.next, %exiting_3 ]
-; CHECK-NEXT:    %iv.wide = phi i64 [ 0, %loop_preheader ], [ %iv.wide.next, %exiting_3 ]
-; CHECK-NEXT:    %iv.next = add nuw nsw i32 %iv, 1
-; CHECK-NEXT:    %iv.wide.next = add nuw nsw i64 %iv.wide, 1
-; CHECK-NEXT:    %left_ptr = getelementptr inbounds i8, i8* %lhs, i32 %iv
-; CHECK-NEXT:    %right_ptr = getelementptr inbounds i8, i8* %rhs, i32 %iv
+; CHECK-NEXT:    %iv.next = add nuw nsw i32 0, 1
+; CHECK-NEXT:    %left_ptr = getelementptr inbounds i8, i8* %lhs, i32 0
+; CHECK-NEXT:    %right_ptr = getelementptr inbounds i8, i8* %rhs, i32 0
 ; CHECK-NEXT:    %result = call i1 @foo(i8* %left_ptr, i8* %right_ptr)
 ; CHECK-NEXT:    br i1 %result, label %exiting_1, label %exit.loopexit
 ; CHECK:       exiting_1:
-; CHECK-NEXT:    %iv.wide.is_not_zero = icmp ne i64 %iv.wide, 0
+; CHECK-NEXT:    %iv.wide.is_not_zero = icmp ne i64 0, 0
 ; CHECK-NEXT:    br i1 false, label %exiting_2, label %exit.loopexit
 ; CHECK:       exiting_2:
 ; CHECK-NEXT:    %bar_ret = call i1 @bar()
 ; CHECK-NEXT:    br i1 %bar_ret, label %exit.loopexit, label %exiting_3
 ; CHECK:       exiting_3:
 ; CHECK-NEXT:    %baz_ret = call i1 @baz()
 ; CHECK-NEXT:    %continue = icmp ne i32 %iv.next, %len
 ; CHECK-NEXT:    %or.cond = select i1 %baz_ret, i1 %continue, i1 false

llvm/test/Transforms/IndVarSimplify/eliminate-exit-no-dl.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -indvars -S < %s | FileCheck %s
 
 ; Check the case where one exit has a pointer EC, and the other doesn't.
 ; Note that this test case is really really fragile.  Removing any
 ; instruction in the below causes the result to differ.  Note that the lack
 ; of a data layout (with pointer size info) is critical to getting a pointer
 ; EC returned by SCEV.
 
 @global = external global [0 x i8], align 1
 
 define void @foo() {
 ; CHECK-LABEL: @foo(
 ; CHECK-NEXT:  bb:
 ; CHECK-NEXT:    br label [[BB3:%.*]]
 ; CHECK:       bb3:
-; CHECK-NEXT:    [[TMP:%.*]] = phi i8* [ [[TMP4:%.*]], [[BB7:%.*]] ], [ getelementptr inbounds ([0 x i8], [0 x i8]* @global, i64 0, i64 2), [[BB:%.*]] ]
-; CHECK-NEXT:    [[TMP4]] = getelementptr inbounds i8, i8* [[TMP]], i64 -1
+; CHECK-NEXT:    [[TMP4:%.*]] = getelementptr inbounds i8, i8* getelementptr inbounds ([0 x i8], [0 x i8]* @global, i64 0, i64 2), i64 -1
 ; CHECK-NEXT:    [[TMP6:%.*]] = load i8, i8* [[TMP4]], align 1
-; CHECK-NEXT:    br i1 false, label [[BB7]], label [[BB11:%.*]]
+; CHECK-NEXT:    br i1 false, label [[BB7:%.*]], label [[BB11:%.*]]
 ; CHECK:       bb7:
 ; CHECK-NEXT:    [[TMP8:%.*]] = zext i8 [[TMP6]] to i64
 ; CHECK-NEXT:    br i1 true, label [[BB11]], label [[BB3]]
 ; CHECK:       bb11:
 ; CHECK-NEXT:    ret void
 ;
 bb:
   br label %bb3

llvm/test/Transforms/IndVarSimplify/floating-point-iv.ll

 }
 
 
 define void @test3() nounwind {
 ; CHECK-LABEL: @test3(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[BB:%.*]]
 ; CHECK:       bb:
-; CHECK-NEXT:    [[IV:%.*]] = phi double [ 0.000000e+00, [[ENTRY:%.*]] ], [ [[TMP1:%.*]], [[BB]] ]
-; CHECK-NEXT:    [[TMP0:%.*]] = tail call i32 @foo(double [[IV]]) #[[ATTR0]]
-; CHECK-NEXT:    [[TMP1]] = fadd double [[IV]], 1.000000e+00
+; CHECK-NEXT:    [[TMP0:%.*]] = tail call i32 @foo(double 0.000000e+00) #[[ATTR0]]
 ; CHECK-NEXT:    br i1 false, label [[BB]], label [[RETURN:%.*]]
 ; CHECK:       return:
 ; CHECK-NEXT:    ret void
 ;
 entry:
   br label %bb
 
 bb:   ; preds = %bb, %entry