[IndVars] Simplify instructions after replacing header phi with preheader value

[nikic]

Summary

After replacing a loop phi with the preheader value, it's usually possible to simplify some of the using instructions, so do that as part of replaceLoopPHINodesWithPreheaderValues().

Doing this as part of IndVars is valuable, because it may make GEPs in the loop have constant offsets and allow the following SROA run to succeed (as demonstrated in the PhaseOrdering test).

Depends on D129214.

[nikic]

Add PhaseOrdering test.

[reames]

LGTM

[mstorsjo]

This triggers failed asserts for me, with https://martin.st/temp/macroblock-reduced.c:

$ clang -target aarch64-linux-gnu -c macroblock-reduced.c -O2
clang: ../lib/Transforms/Scalar/IndVarSimplify.cpp:2059: bool {anonymous}::IndVarSimplify::run(llvm::Loop*): Assertion `L->isRecursivelyLCSSAForm(*DT, *LI) && "Indvars did not preserve LCSSA!"' failed.

[nikic]

@mstorsjo Thanks for the report! Here's a reduced test case:

define i64 @test(i64 %arg) {
entry:
  br label %loop1

loop1:
  %iv1 = phi i64 [ 0, %entry ], [ 1, %loop1.latch ]
  br label %loop2

loop2:
  %iv2 = phi i64 [ 0, %loop1 ], [ 1, %loop2 ]
  %res = add nuw nsw i64 %iv1, %iv2
  br i1 true, label %loop2, label %loop1.latch

loop1.latch:
  %res.lcssa = phi i64 [ %res, %loop2 ]
  br i1 false, label %loop1, label %exit

exit:
  %res.lcssa2 = phi i64 [ %res.lcssa, %loop1.latch ]
  ret i64 %res.lcssa2
}

This gets reduced to:

define i64 @t(i64 %arg) {
entry:
  br label %loop1

loop1:                                            ; preds = %loop1.latch, %entry
  br label %loop2

loop2:                                            ; preds = %loop2, %loop1
  %iv2 = phi i64 [ 0, %loop1 ], [ 1, %loop2 ]
  br i1 true, label %loop2, label %loop1.latch

loop1.latch:                                      ; preds = %loop2
  br i1 false, label %loop1, label %exit

exit:                                             ; preds = %loop1.latch
  %res.lcssa2 = phi i64 [ %iv2, %loop1.latch ]
  ret i64 %res.lcssa2
}

We need to make sure that we don't fold away any LCSSA phi nodes of inner loops.

[nikic]

@mstorsjo Should be fixed by https://github.com/llvm/llvm-project/commit/7a43b382ce9da2c5a4196d6cf4184d2983906400.

[mstorsjo]

In D129293#3651174, @nikic wrote:

@mstorsjo Should be fixed by https://github.com/llvm/llvm-project/commit/7a43b382ce9da2c5a4196d6cf4184d2983906400.

Thanks! The issue does indeed seem to be fixed. (Sorry for the long delay in properly rechecking the issue.)

llvm/lib/Transforms/Scalar/IndVarSimplify.cpp

static void foldExit(const Loop *L, BasicBlock *ExitingBB, bool IsTaken,
   replaceExitCond(BI, NewCond, DeadInsts);
 }
 
 static void replaceLoopPHINodesWithPreheaderValues(
     Loop *L, SmallVectorImpl<WeakTrackingVH> &DeadInsts) {
   assert(L->isLoopSimplifyForm() && "Should only do it in simplify form!");
   auto *LoopPreheader = L->getLoopPreheader();
   auto *LoopHeader = L->getHeader();
+  SmallVector<Instruction *> Worklist;
   for (auto &PN : LoopHeader->phis()) {
     auto *PreheaderIncoming = PN.getIncomingValueForBlock(LoopPreheader);
+    for (User *U : PN.users())
+      Worklist.push_back(cast<Instruction>(U));
     PN.replaceAllUsesWith(PreheaderIncoming);
     DeadInsts.emplace_back(&PN);
   }
+
+  // Replacing with the preheader value will often allow IV users to simplify
+  // (especially if the preheader value is a constant).
+  SmallPtrSet<Instruction *, 16> Visited;
+  while (!Worklist.empty()) {
+    auto *I = cast<Instruction>(Worklist.pop_back_val());
+    if (!Visited.insert(I).second)
+      continue;
+
+    // Don't simplify instructions outside the loop.
+    if (!L->contains(I))
+      continue;
+
+    if (Value *Res = simplifyInstruction(I, I->getModule()->getDataLayout())) {
+      for (User *U : I->users())
+        Worklist.push_back(cast<Instruction>(U));
+      I->replaceAllUsesWith(Res);
+      DeadInsts.emplace_back(I);
+    }
+  }
 }
 
 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);

llvm/test/Transforms/IndVarSimplify/X86/pr35406.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -S -indvars -verify-scev %s | FileCheck %s
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128-ni:1"
 target triple = "x86_64-unknown-linux-gnu"
 
 define i32 @testDiv(i8* %p, i64* %p1) {
 ; CHECK-LABEL: @testDiv(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[LOOP1:%.*]]
 ; CHECK:       loop1:
 ; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ [[INDVARS_IV_NEXT:%.*]], [[LOOP2_EXIT:%.*]] ], [ 8, [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i64 [[INDVARS_IV]], 15
 ; CHECK-NEXT:    br i1 [[EXITCOND]], label [[EXIT:%.*]], label [[GENERAL_CASE24:%.*]]
 ; CHECK:       general_case24:
 ; CHECK-NEXT:    br i1 false, label [[LOOP2_PREHEADER:%.*]], label [[LOOP2_EXIT]]
 ; CHECK:       loop2.preheader:
-; CHECK-NEXT:    [[TMP0:%.*]] = udiv i64 14, [[INDVARS_IV]]
-; CHECK-NEXT:    [[TMP1:%.*]] = udiv i64 60392, [[TMP0]]
 ; CHECK-NEXT:    br label [[LOOP2:%.*]]
 ; CHECK:       loop2:
-; CHECK-NEXT:    [[INDVARS_IV_NEXT2:%.*]] = add nuw nsw i64 [[TMP1]], -1
 ; CHECK-NEXT:    [[I4:%.*]] = load atomic i64, i64* [[P1:%.*]] unordered, align 8
-; CHECK-NEXT:    [[I6:%.*]] = sub i64 [[I4]], [[INDVARS_IV_NEXT2]]
+; CHECK-NEXT:    [[I6:%.*]] = sub i64 [[I4]], -1
 ; CHECK-NEXT:    store atomic i64 [[I6]], i64* [[P1]] unordered, align 8
 ; CHECK-NEXT:    br i1 true, label [[LOOP2_EXIT_LOOPEXIT:%.*]], label [[LOOP2]]
 ; CHECK:       loop2.exit.loopexit:
 ; CHECK-NEXT:    br label [[LOOP2_EXIT]]
 ; CHECK:       loop2.exit:
 ; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nuw nsw i64 [[INDVARS_IV]], 1
 ; CHECK-NEXT:    br i1 false, label [[EXIT]], label [[LOOP1]]
 ; CHECK:       exit:

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.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:    %result = call i1 @foo(i8* %lhs, i8* %rhs)
 ; CHECK-NEXT:    br i1 %result, label %exiting_1, label %exit.loopexit
 ; CHECK:       exiting_1:
-; 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:    %continue = icmp ne i32 1, %len
 ; CHECK-NEXT:    %or.cond = select i1 %baz_ret, i1 %continue, i1 false
 ; CHECK-NEXT:    br i1 %or.cond, label %loop, label %exit.loopexit
 ; CHECK:       exit.loopexit:
-; CHECK-NEXT:    %val.ph = phi i1 [ %baz_ret, %exiting_3 ], [ %bar_ret, %exiting_2 ], [ %iv.wide.is_not_zero, %exiting_1 ], [ %result, %loop ]
+; CHECK-NEXT:    %val.ph = phi i1 [ %baz_ret, %exiting_3 ], [ %bar_ret, %exiting_2 ], [ false, %exiting_1 ], [ %result, %loop ]
 ; CHECK-NEXT:    br label %exit
 ; CHECK:       exit:
 ; CHECK-NEXT:    %val = phi i1 [ false, %entry ], [ %val.ph, %exit.loopexit ]
 ; CHECK-NEXT:    ret i1 %val
 ;
 entry:
   %length_not_zero = icmp ne i32 %len, 0
   br i1 %length_not_zero, label %loop_preheader, label %exit

 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    %length_not_zero = icmp ne i32 %len, 0
 ; CHECK-NEXT:    br i1 %length_not_zero, label %weird_loop.preheader, label %exit
 ; CHECK:       weird_loop.preheader:
 ; CHECK-NEXT:    br label %weird_loop
 ; CHECK:       weird_loop:
 ; CHECK-NEXT:    %weird.iv = phi i32 [ %weird.iv.next, %weird_loop ], [ 0, %weird_loop.preheader ]
 ; CHECK-NEXT:    %weird.iv.next = add i32 %weird.iv, 1
-; CHECK-NEXT:    %weird.iv.wide = zext i32 %weird.iv to i64
 ; CHECK-NEXT:    %weird.cond = call i1 @bar()
 ; CHECK-NEXT:    br i1 %weird.cond, label %weird_loop, label %loop.preheader
 ; CHECK:       loop.preheader:
 ; CHECK-NEXT:    %weird.iv.lcssa = phi i32 [ %weird.iv, %weird_loop ]
-; CHECK-NEXT:    %weird.iv.wide.lcssa = phi i64 [ %weird.iv.wide, %weird_loop ]
 ; CHECK-NEXT:    br label %loop
 ; CHECK:       loop:
 ; CHECK-NEXT:    %iv.next = add i32 %weird.iv.lcssa, 1
 ; CHECK-NEXT:    %left_ptr = getelementptr inbounds i8, i8* %lhs, i32 %weird.iv.lcssa
 ; CHECK-NEXT:    %right_ptr = getelementptr inbounds i8, i8* %rhs, i32 %weird.iv.lcssa
 ; 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 %weird.iv.wide.lcssa, %weird.iv.wide.lcssa
 ; 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
 ; CHECK-NEXT:    br i1 %or.cond, label %loop, label %exit.loopexit
 ; CHECK:       exit.loopexit:
-; CHECK-NEXT:    %val.ph = phi i1 [ %baz_ret, %exiting_3 ], [ %bar_ret, %exiting_2 ], [ %iv.wide.is_not_zero, %exiting_1 ], [ %result, %loop ]
+; CHECK-NEXT:    %val.ph = phi i1 [ %baz_ret, %exiting_3 ], [ %bar_ret, %exiting_2 ], [ false, %exiting_1 ], [ %result, %loop ]
 ; CHECK-NEXT:    br label %exit
 ; CHECK:       exit:
 ; CHECK-NEXT:    %val = phi i1 [ false, %entry ], [ %val.ph, %exit.loopexit ]
 ; CHECK-NEXT:    ret i1 %val
 ;
 entry:
   %length_not_zero = icmp ne i32 %len, 0
   br i1 %length_not_zero, label %weird_loop, label %exit

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:    [[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:    [[TMP5:%.*]] = icmp ugt i8* [[TMP4]], getelementptr inbounds ([0 x i8], [0 x i8]* @global, i64 0, i64 500)
-; CHECK-NEXT:    br i1 [[TMP5]], label [[BB7:%.*]], label [[BB11:%.*]]
+; CHECK-NEXT:    [[TMP6:%.*]] = load i8, i8* getelementptr inbounds ([0 x i8], [0 x i8]* @global, i64 0, i64 1), align 1
+; 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

return:
   ret void
 }
 
 define void @test4() nounwind {
 ; CHECK-LABEL: @test4(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[BB:%.*]]
 ; CHECK:       bb:
-; CHECK-NEXT:    [[INDVAR_CONV:%.*]] = sitofp i32 40 to double
-; CHECK-NEXT:    [[TMP0:%.*]] = tail call i32 @foo(double [[INDVAR_CONV]]) #[[ATTR0]]
+; CHECK-NEXT:    [[TMP0:%.*]] = tail call i32 @foo(double 4.000000e+01) #[[ATTR0]]
 ; CHECK-NEXT:    br i1 false, label [[BB]], label [[RETURN:%.*]]
 ; CHECK:       return:
 ; CHECK-NEXT:    ret void
 ;
 entry:
   br label %bb
 
 bb:   ; preds = %bb, %entry

llvm/test/Transforms/IndVarSimplify/lcssa-preservation.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -indvars -replexitval=always -S | FileCheck %s
 ; Make sure IndVars preserves LCSSA form, especially across loop nests.
 
 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64"
 
 define void @PR18642(i32 %x) {
 ; CHECK-LABEL: @PR18642(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[OUTER_HEADER:%.*]]
 ; CHECK:       outer.header:
-; CHECK-NEXT:    [[SMAX:%.*]] = call i32 @llvm.smax.i32(i32 0, i32 undef)
-; CHECK-NEXT:    [[TMP0:%.*]] = add i32 [[SMAX]], 1
 ; CHECK-NEXT:    br label [[INNER_HEADER:%.*]]
 ; CHECK:       inner.header:
 ; CHECK-NEXT:    br i1 false, label [[INNER_LATCH:%.*]], label [[OUTER_LATCH:%.*]]
 ; CHECK:       inner.latch:
 ; CHECK-NEXT:    br i1 true, label [[INNER_HEADER]], label [[EXIT_LOOPEXIT:%.*]]
 ; CHECK:       outer.latch:
 ; CHECK-NEXT:    br i1 false, label [[OUTER_HEADER]], label [[EXIT_LOOPEXIT1:%.*]]
 ; CHECK:       exit.loopexit:
-; CHECK-NEXT:    [[INC_LCSSA:%.*]] = phi i32 [ [[TMP0]], [[INNER_LATCH]] ]
+; CHECK-NEXT:    [[INC_LCSSA:%.*]] = phi i32 [ -2147483648, [[INNER_LATCH]] ]
 ; CHECK-NEXT:    br label [[EXIT:%.*]]
 ; CHECK:       exit.loopexit1:
 ; CHECK-NEXT:    br label [[EXIT]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    [[EXIT_PHI:%.*]] = phi i32 [ [[INC_LCSSA]], [[EXIT_LOOPEXIT]] ], [ undef, [[EXIT_LOOPEXIT1]] ]
 ; CHECK-NEXT:    ret void
 ;
 entry:

llvm/test/Transforms/IndVarSimplify/no-iv-rewrite.ll

 ; Test a widened IV that is used by a phi on different paths within the loop.
 define void @phiUsesTrunc() nounwind {
 ; CHECK-LABEL: @phiUsesTrunc(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br i1 undef, label [[FOR_BODY_PREHEADER:%.*]], label [[FOR_END:%.*]]
 ; CHECK:       for.body.preheader:
 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
 ; CHECK:       for.body:
-; CHECK-NEXT:    [[TMP0:%.*]] = trunc i64 1 to i32
 ; CHECK-NEXT:    br i1 undef, label [[IF_THEN:%.*]], label [[IF_ELSE:%.*]]
 ; CHECK:       if.then:
 ; CHECK-NEXT:    br i1 undef, label [[IF_THEN33:%.*]], label [[FOR_INC:%.*]]
 ; CHECK:       if.then33:
 ; CHECK-NEXT:    br label [[FOR_INC]]
 ; CHECK:       if.else:
 ; CHECK-NEXT:    br i1 undef, label [[IF_THEN97:%.*]], label [[FOR_INC]]
 ; CHECK:       if.then97:
 ; CHECK-NEXT:    call void @use64(i64 1)
 ; CHECK-NEXT:    br label [[FOR_INC]]
 ; CHECK:       for.inc:
-; CHECK-NEXT:    [[KMIN_1:%.*]] = phi i32 [ [[TMP0]], [[IF_THEN33]] ], [ 0, [[IF_THEN]] ], [ [[TMP0]], [[IF_THEN97]] ], [ 0, [[IF_ELSE]] ]
+; CHECK-NEXT:    [[KMIN_1:%.*]] = phi i32 [ 1, [[IF_THEN33]] ], [ 0, [[IF_THEN]] ], [ 1, [[IF_THEN97]] ], [ 0, [[IF_ELSE]] ]
 ; CHECK-NEXT:    call void @use32(i32 [[KMIN_1]])
 ; CHECK-NEXT:    br i1 false, label [[FOR_BODY]], label [[FOR_END_LOOPEXIT:%.*]]
 ; CHECK:       for.end.loopexit:
 ; CHECK-NEXT:    br label [[FOR_END]]
 ; CHECK:       for.end:
 ; CHECK-NEXT:    ret void
 ;
 entry:

llvm/test/Transforms/IndVarSimplify/pr22222.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -indvars -S < %s | FileCheck %s
 
 @b = common global i32 0, align 4
 @c = common global i32 0, align 4
 @a = common global i32 0, align 4
 
 declare void @abort() #1
 
 ; Function Attrs: nounwind ssp uwtable
 define i32 @main() {
 ; CHECK-LABEL: @main(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[A_PROMOTED13:%.*]] = load i32, i32* @a, align 4
 ; CHECK-NEXT:    br label [[FOR_COND1_PREHEADER:%.*]]
 ; CHECK:       for.cond1.preheader:
 ; CHECK-NEXT:    br label [[FOR_BODY3:%.*]]
 ; CHECK:       for.body3:
-; CHECK-NEXT:    [[ADD:%.*]] = sub i32 0, 1
-; CHECK-NEXT:    [[OR:%.*]] = or i32 [[A_PROMOTED13]], [[ADD]]
 ; CHECK-NEXT:    br i1 false, label [[FOR_BODY3]], label [[FOR_END:%.*]]
 ; CHECK:       for.end:
-; CHECK-NEXT:    [[OR_LCSSA:%.*]] = phi i32 [ [[OR]], [[FOR_BODY3]] ]
 ; CHECK-NEXT:    br i1 false, label [[FOR_COND1_PREHEADER]], label [[FOR_END6:%.*]]
 ; CHECK:       for.end6:
-; CHECK-NEXT:    [[OR_LCSSA_LCSSA:%.*]] = phi i32 [ [[OR_LCSSA]], [[FOR_END]] ]
+; CHECK-NEXT:    [[OR_LCSSA_LCSSA:%.*]] = phi i32 [ -1, [[FOR_END]] ]
 ; CHECK-NEXT:    store i32 [[OR_LCSSA_LCSSA]], i32* @a, align 4
 ; CHECK-NEXT:    [[CMP7:%.*]] = icmp eq i32 [[OR_LCSSA_LCSSA]], -1
 ; CHECK-NEXT:    br i1 [[CMP7]], label [[IF_END:%.*]], label [[IF_THEN:%.*]]
 ; CHECK:       if.then:
 ; CHECK-NEXT:    tail call void @abort()
 ; CHECK-NEXT:    unreachable
 ; CHECK:       if.end:
 ; CHECK-NEXT:    ret i32 0

llvm/test/Transforms/IndVarSimplify/pr40454.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -S -indvars  < %s | FileCheck %s
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
 define void @test() {
 ; CHECK-LABEL: @test(
 ; CHECK-NEXT:  bb:
 ; CHECK-NEXT:    br label [[BB2:%.*]]
 ; CHECK:       bb1:
 ; CHECK-NEXT:    br label [[BB2]]
 ; CHECK:       bb2:
-; CHECK-NEXT:    [[TMP:%.*]] = phi i32 [ -9, [[BB:%.*]] ], [ [[TMP6:%.*]], [[BB1:%.*]] ]
+; CHECK-NEXT:    [[TMP:%.*]] = phi i32 [ -9, [[BB:%.*]] ], [ -10, [[BB1:%.*]] ]
 ; CHECK-NEXT:    br label [[BB3:%.*]]
 ; CHECK:       bb3:
 ; CHECK-NEXT:    br i1 false, label [[BB5:%.*]], label [[BB12:%.*]]
 ; CHECK:       bb5:
-; CHECK-NEXT:    [[TMP6]] = add nsw i32 -9, -1
 ; CHECK-NEXT:    br i1 undef, label [[BB8:%.*]], label [[BB9:%.*]]
 ; CHECK:       bb8:
 ; CHECK-NEXT:    br label [[BB10:%.*]]
 ; CHECK:       bb9:
 ; CHECK-NEXT:    br label [[BB10]]
 ; CHECK:       bb10:
 ; CHECK-NEXT:    br label [[BB3]]
 ; CHECK:       bb12:

llvm/test/Transforms/IndVarSimplify/scev-expander-preserve-lcssa.ll

 ; CHECK-NEXT:    br label [[FOR_INNER_2:%.*]]
 ; CHECK:       for.inner.2:
 ; CHECK-NEXT:    [[I_0_I1:%.*]] = phi i32 [ 0, [[FOR_INNER_EXIT]] ], [ [[INC_I3:%.*]], [[FOR_INNER_2]] ]
 ; CHECK-NEXT:    [[INC_I3]] = add nuw nsw i32 [[I_0_I1]], 1
 ; CHECK-NEXT:    [[CMP7_I4:%.*]] = icmp slt i8 [[N]], 0
 ; CHECK-NEXT:    br i1 [[CMP7_I4]], label [[FOR_INNER_2]], label [[FOR_INC:%.*]]
 ; CHECK:       for.inc:
 ; CHECK-NEXT:    [[INC_I3_LCSSA:%.*]] = phi i32 [ [[INC_I3]], [[FOR_INNER_2]] ]
-; CHECK-NEXT:    [[ADD71:%.*]] = add i32 0, [[INC_I_LCSSA]]
-; CHECK-NEXT:    [[ADD85:%.*]] = add i32 [[ADD71]], [[INC_I3_LCSSA]]
+; CHECK-NEXT:    [[ADD85:%.*]] = add i32 [[INC_I_LCSSA]], [[INC_I3_LCSSA]]
 ; CHECK-NEXT:    br i1 false, label [[FOR_BODY]], label [[WHILE_COND_PREHEADER:%.*]]
 ; CHECK:       while.cond.preheader:
 ; CHECK-NEXT:    [[ADD85_LCSSA:%.*]] = phi i32 [ [[ADD85]], [[FOR_INC]] ]
 ; CHECK-NEXT:    [[SHL:%.*]] = shl nuw nsw i32 [[CONV:%.*]], 2
 ; CHECK-NEXT:    br label [[WHILE_COND:%.*]]
 ; CHECK:       while.cond:
 ; CHECK-NEXT:    [[POS_8:%.*]] = phi i32 [ [[INC114:%.*]], [[WHILE_BODY:%.*]] ], [ [[ADD85_LCSSA]], [[WHILE_COND_PREHEADER]] ]
 ; CHECK-NEXT:    [[CMP112:%.*]] = icmp ult i32 [[POS_8]], [[SHL]]

llvm/test/Transforms/IndVarSimplify/sentinel.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -indvars -S < %s | FileCheck %s
 
 target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128-ni:1-p2:32:8:8:32-ni:2"
 target triple = "x86_64-unknown-linux-gnu"
 
 define void @test() personality i32* ()* @snork {
 ; CHECK-LABEL: @test(
 ; CHECK-NEXT:  bb:
 ; CHECK-NEXT:    br label [[BB4:%.*]]
 ; CHECK:       bb1:
-; CHECK-NEXT:    [[TMP0:%.*]] = sub i32 [[TMP1:%.*]], [[SMAX:%.*]]
 ; CHECK-NEXT:    br i1 true, label [[BB2:%.*]], label [[BB4]]
 ; CHECK:       bb2:
-; CHECK-NEXT:    [[TMP3:%.*]] = phi i32 [ [[TMP0]], [[BB1:%.*]] ]
+; CHECK-NEXT:    [[TMP3:%.*]] = phi i32 [ undef, [[BB1:%.*]] ]
 ; CHECK-NEXT:    ret void
 ; CHECK:       bb4:
-; CHECK-NEXT:    [[SMAX]] = call i32 @llvm.smax.i32(i32 undef, i32 36)
 ; CHECK-NEXT:    [[TMP6:%.*]] = invoke i32 @quux() [ "deopt"(i32 0, i32 0, i32 0, i32 180, i32 0, i32 25, i32 0, i32 7, i8* null, i32 7, i8* null, i32 7, i8* null, i32 3, i32 undef, i32 3, i32 undef, i32 7, i8* null, i32 3, i32 undef, i32 3, i32 undef, i32 3, i32 undef, i32 3, i32 undef, i32 4, double undef, i32 7, i8* null, i32 4, i64 undef, i32 7, i8* null, i32 0, i8 addrspace(1)* undef, i32 3, i32 undef, i32 0, i8 addrspace(1)* undef, i32 0, i8 addrspace(1)* undef, i32 0, i8 addrspace(1)* undef, i32 0, i8 addrspace(1)* undef, i32 0, i8 addrspace(1)* undef, i32 0, i8 addrspace(1)* undef, i32 0, i8 addrspace(1)* undef, i32 0, i8 addrspace(1)* undef, i32 7, i8* null) ]
 ; CHECK-NEXT:    to label [[BB7:%.*]] unwind label [[BB15:%.*]]
 ; CHECK:       bb7:
-; CHECK-NEXT:    [[TMP1]] = add i32 [[TMP6]], undef
 ; CHECK-NEXT:    br label [[BB9:%.*]]
 ; CHECK:       bb9:
 ; CHECK-NEXT:    br i1 true, label [[BB1]], label [[BB9]]
 ; CHECK:       bb15:
 ; CHECK-NEXT:    [[TMP16:%.*]] = landingpad { i8*, i32 }
 ; CHECK-NEXT:    cleanup
 ; CHECK-NEXT:    ret void
 ;

llvm/test/Transforms/LoopDeletion/pr53969.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -passes="loop(indvars,loop-deletion)" -S  < %s | FileCheck %s
 
 target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128-ni:1-p2:32:8:8:32-ni:2"
 target triple = "x86_64-unknown-linux-gnu"
 
 ; Make sure we don't crash.
 define void @test() {
 ; CHECK-LABEL: @test(
 ; CHECK-NEXT:  bb:
 ; CHECK-NEXT:    br label [[BB1:%.*]]
 ; CHECK:       bb1:
-; CHECK-NEXT:    [[TMP3:%.*]] = add nsw i32 112, -1
-; CHECK-NEXT:    [[TMP5:%.*]] = mul i32 [[TMP3]], [[TMP3]]
-; CHECK-NEXT:    [[TMP6:%.*]] = mul nsw i32 11, -6
-; CHECK-NEXT:    [[TMP7:%.*]] = mul nsw i32 [[TMP6]], [[TMP5]]
-; CHECK-NEXT:    [[TMP8:%.*]] = add nuw nsw i32 [[TMP7]], 11
 ; CHECK-NEXT:    [[TMP9:%.*]] = and i32 undef, 1
 ; CHECK-NEXT:    [[TMP10:%.*]] = icmp eq i32 [[TMP9]], 0
 ; CHECK-NEXT:    br i1 [[TMP10]], label [[BB33_LOOPEXIT1:%.*]], label [[BB34_PREHEADER:%.*]]
 ; CHECK:       bb34.preheader:
 ; CHECK-NEXT:    br label [[BB34:%.*]]
 ; CHECK:       bb11:
 ; CHECK-NEXT:    [[TMP2_LCSSA12:%.*]] = phi i32 [ 11, [[BB34]] ]
 ; CHECK-NEXT:    br label [[BB33_LOOPEXIT:%.*]]
 ; CHECK:       bb12:
-; CHECK-NEXT:    [[TMP0:%.*]] = add i64 [[TMP40:%.*]], 0
 ; CHECK-NEXT:    br label [[BB14:%.*]]
 ; CHECK:       bb14:
 ; CHECK-NEXT:    br i1 true, label [[BB32:%.*]], label [[BB22:%.*]]
 ; CHECK:       bb22:
-; CHECK-NEXT:    [[TMP1:%.*]] = trunc i64 4 to i32
-; CHECK-NEXT:    [[TMP23:%.*]] = or i32 [[TMP1]], undef
-; CHECK-NEXT:    [[TMP24:%.*]] = add i32 [[TMP23]], undef
 ; CHECK-NEXT:    br i1 false, label [[BB42:%.*]], label [[BB25:%.*]]
 ; CHECK:       bb25:
 ; CHECK-NEXT:    br label [[BB31:%.*]]
 ; CHECK:       bb31:
 ; CHECK-NEXT:    unreachable
 ; CHECK:       bb32:
 ; CHECK-NEXT:    ret void
 ; CHECK:       bb33.loopexit:
 ; CHECK-NEXT:    [[TMP2_LCSSA9:%.*]] = phi i32 [ [[TMP2_LCSSA12]], [[BB11:%.*]] ]
 ; CHECK-NEXT:    br label [[BB33:%.*]]
 ; CHECK:       bb33.loopexit1:
 ; CHECK-NEXT:    [[TMP2_LCSSA:%.*]] = phi i32 [ 11, [[BB1]] ]
 ; CHECK-NEXT:    br label [[BB33]]
 ; CHECK:       bb33:
 ; CHECK-NEXT:    [[TMP210:%.*]] = phi i32 [ [[TMP2_LCSSA]], [[BB33_LOOPEXIT1]] ], [ [[TMP2_LCSSA9]], [[BB33_LOOPEXIT]] ]
 ; CHECK-NEXT:    call void @use(i32 [[TMP210]])
 ; CHECK-NEXT:    ret void
 ; CHECK:       bb34:
-; CHECK-NEXT:    [[TMP36:%.*]] = xor i32 0, [[TMP8]]
-; CHECK-NEXT:    [[TMP38:%.*]] = add i32 [[TMP36]], undef
-; CHECK-NEXT:    [[TMP39:%.*]] = add i32 [[TMP38]], undef
-; CHECK-NEXT:    [[TMP40]] = sext i32 [[TMP39]] to i64
 ; CHECK-NEXT:    br i1 false, label [[BB11]], label [[BB12:%.*]]
 ; CHECK:       bb42:
-; CHECK-NEXT:    [[TMP24_LCSSA:%.*]] = phi i32 [ [[TMP24]], [[BB22]] ]
-; CHECK-NEXT:    [[TMP18_LCSSA4:%.*]] = phi i64 [ [[TMP0]], [[BB22]] ]
+; CHECK-NEXT:    [[TMP24_LCSSA:%.*]] = phi i32 [ undef, [[BB22]] ]
+; CHECK-NEXT:    [[TMP18_LCSSA4:%.*]] = phi i64 [ 0, [[BB22]] ]
 ; CHECK-NEXT:    store atomic i64 [[TMP18_LCSSA4]], i64 addrspace(1)* undef unordered, align 8
 ; CHECK-NEXT:    call void @use(i32 [[TMP24_LCSSA]])
 ; CHECK-NEXT:    ret void
 ;
 bb:
   br label %bb1
 
 bb1:                                              ; preds = %bb31, %bb