[SCEV] rewriteLoopExitValues(): even if have hard uses, still rewrite if cheap (PR44668)

[lebedev.ri]

Summary

Replacing uses of IV outside of the loop is likely generally useful,
but rewriteLoopExitValues() is cautious, and if it isn't told to always
perform the replacement, and there are hard uses of IV in loop,
it doesn't replace.

In PR44668,
that prevents -indvars from replacing uses of induction variable
after the loop, which might be one of the optimization failures
preventing that code from being vectorized.

Instead, now that the cost model is fixed, i believe we should be
a little bit more optimistic, and also perform replacement
if we believe it is within our budget.

Fixes PR44668.

[reames]

The general structure of the patch looks entirely reasonable. I am concerned about the number of test diffs. Mostly because there might be regressions herein, and it would be really hard to spot. I'd like to suggest a strategy for making the test changes easier.

Split the patch into a couple of stages:

1. Add all the TTI plumbing, and one simple use of the costing (e.g. trunc), but keep most of isHighCostExpansion as is. Intention is that very few tests change, and results are obviously correct.
2. Add remaining use of TTI in isHighCost except for the min/max (since those were unconditional failures previously). Again, hopefully smallish number of diffs to review.
3. Add the min/max logic. These are the most interesting diffs to study.
4. Change the bailout logic in IndVarSimplify.

If you're okay with this approach, consider yourself to have a conditional LGTM for (1) provided that the test diffs are actually very limited.

If you want to make an alternate suggestion as to how to review the test diffs effectively, I'm open to it.

llvm/lib/Analysis/ScalarEvolutionExpander.cpp

2156 ↗

(On Diff #240661)

Minor: We may already have a SCEVType to OpCode conversion helper. If we don't, we should probably create one and factor this out. I'm sure we have the same logic elsewhere as well.

2184 ↗

(On Diff #240661)

The second check here is redundant as you've already checked that RHS is a constant.

2261 ↗

(On Diff #240661)

Style wise, I'd suggest splitting AddRec into it's own case since it requires complexity the others don't.

llvm/lib/Transforms/Utils/LoopUtils.cpp

1370

Can I ask you to split this piece into it's own separate patch? The rest of NFC-ish, this really isn't.

Also, you can remove the not-constant and not-unknown cases as that's now handled by the high cost clause.

llvm/lib/Transforms/Utils/SimplifyIndVar.cpp

48 ↗

(On Diff #240661)

Given we have the same magic number scatter around, I'd suggest moving this to a utility file and sharing the same constant param for all uses. We can split later if useful.

llvm/test/Transforms/IndVarSimplify/dont-recompute.ll

38–39

This test change is against the intention of the file per the name. I think when you split as suggested above, this will need consolidated, renamed, or something.

[lebedev.ri]

Thank you for taking a look!

In D73501#1844914, @reames wrote:

The general structure of the patch looks entirely reasonable.

Aha. That was the main question here.

I am concerned about the number of test diffs.
Mostly because there might be regressions herein, and it would be really hard to spot.

I agree that the test changes do look unreviewable.

The main question may be: what do we consider a regression?
"Previously we considered this SCEV high-cost and now we don't" won't work well,
because of the nature of the patch - we go from semi-arbitrary rules
to "consistent" application of "consistent" cost model.
Naturally, some patterns will no longer be high-cost, and some will become high-cost.

For example, i believe all of the min/max+loop latch changes fall into this category,
and i suspect that the majority of changes are of that nature.

"Cost-modelling is incorrect, SCEV expression should have cost N but we counted it as K"
This is the main problem IMO. This might need unittests for isHighCostExpansion() cost-modelling.

I'd like to suggest a strategy for making the test changes easier.
Split the patch into a couple of stages:

1. Add all the TTI plumbing, and one simple use of the costing (e.g. trunc), but keep most of isHighCostExpansion as is. Intention is that very few tests change, and results are obviously correct.
2. Add remaining use of TTI in isHighCost except for the min/max (since those were unconditional failures previously). Again, hopefully smallish number of diffs to review.
3. Add the min/max logic. These are the most interesting diffs to study.
4. Change the bailout logic in IndVarSimplify.

If you're okay with this approach, consider yourself to have a conditional LGTM for (1) provided that the test diffs are actually very limited.

If you want to make an alternate suggestion as to how to review the test diffs effectively, I'm open to it.

I'll explore ways to make diffs more reviewable.

llvm/lib/Analysis/ScalarEvolutionExpander.cpp

2156 ↗

(On Diff #240661)

We don't necessarily have 1:1 mapping between SCEV type and an IR instruction.
(E.g. scAddRecExpr, and even min/max)
What should that helper be doing in that case?

2261 ↗

(On Diff #240661)

Also, this overcharges scAddRecExpr if Op is actually a zero constant.

[lebedev.ri]

Okay, here it goes, patch splitting complete :)

[lebedev.ri]

Rebased.

[lebedev.ri]

Ping @reames / @mkazantsev - the patches are all nicely splitted for review :)
Thanks

[lebedev.ri]

Ping @reames / @mkazantsev
Thanks

[lebedev.ri]

Ping @reames / @mkazantsev
Please do indicate if there is any way i can help move this process along.
Thanks

[mkazantsev]

LGTM

[lebedev.ri]

In D73501#1890715, @mkazantsev wrote:

LGTM

Thank you for the review!

[lebedev.ri]

Rebased, NFC.

[samparker]

Hi,
Did you get performance numbers for these patches? We track the performance of our (Arm) open source DSP library and the cost model fixes were generally a notable improvement, so many thanks for that! But the final patch for rewriting exit values has generally been bad, especially considering the gains from the modelling improvements. I need to look into it further, but on my current test case I'm seeing +30% increase in stack accesses with a similar decrease in performance. I'm just wondering if you observed any negative effects yourself?

[lebedev.ri]

In D73501#1905171, @samparker wrote:

Hi,

Hi. Thank you for bringing this up to my attention.

We track the performance of our (Arm) open source DSP library
and the cost model fixes were generally a notable improvement,
so many thanks for that!

Which i believe means that we stopped performing many of the expansions
we've previously done because they now no longer fit
into our arbitrarily-picked budget magic number..

But the final patch for rewriting exit values has generally been bad,
especially considering the gains from the modelling improvements.

The goal of this change in particular was to really try to get rid of
uses of IV outside of the loop, since that was one of the obstacles
preventing vectorization in one of the loops i looked at.
(read: in some cases this patch could lead to dramatic improvements due to vectorization)

In light of cost modelling issues you pointed out, this means two things:

1. We need an undo transform :) It obviously would need to be quite late in pipeline though. https://bugs.llvm.org/show_bug.cgi?id=42965 / D12494 / D66450 (CC @reames @danilaml @srking - what would it take such a pass moving? :))
2. After all, we might not be modelling the cost correctly, as pointed out in post-commit review notes @ D73744. Will take a look.

I need to look into it further, but on my current test case I'm seeing +30% increase
in stack accesses with a similar decrease in performance.

I'm not sure what "increase in stack accesses" mean here?
I'm reading that as: since we need some values after the loop (to re-compute the values),
we end up spilling them onto stack to free up registers for/in loop,
and then end up reloading them after the loop? That's not unexpected i guess,
although the perf drop (define "similar"?) is obviously alarming.

I'm interested whether @dmgreen, @bjope also observed something similar from these patches?

Did you get performance numbers for these patches?
I'm just wondering if you observed any negative effects yourself?

I just double-checked, and i'm not seeing anything like that.
But cost modelling being cost modelling i'm not very surprised.
Let's see what happens if i address post-commit-review comments..

On LLVM's LNT, the closest runs are http://lnt.llvm.org/db_default/v4/nts/132695?compare_to=132694
It says there are some improvements and one regression,
but from http://lnt.llvm.org/db_default/v4/nts/graph?plot.0=1364.1604571.3&highlight_run=132695
that regression looks like noise to me.

[lebedev.ri]

@samparker, maybe @dmgreen @bjope: posted D75908. if possible, please consider seeing if/how it alters benchmark results and maybe reply on that patch

[danilaml]

@lebedev.ri I've been successfully using a pass based on https://reviews.llvm.org/D12494 in a downstream port (although I'm not sure if it's enough to fix all ARM's regressions). I was planning to submit it for the review after some touch ups (i.e. it only uses legacy pm) but haven't found the time for that yet. I also need to evaluate whether it is still needed after D75908 (that might take some time).

[lebedev.ri]

In D73501#1924303, @danilaml wrote:

@lebedev.ri I've been successfully using a pass based on https://reviews.llvm.org/D12494 in a downstream port (although I'm not sure if it's enough to fix all ARM's regressions). I was planning to submit it for the review after some touch ups (i.e. it only uses legacy pm) but haven't found the time for that yet.

I also need to evaluate whether it is still needed after D75908 (that might take some time).

I don't see why it wouldn't be needed after that, i would even think it's needed more than ever now.

[efriedma]

The goal of this change in particular was to really try to get rid of
uses of IV outside of the loop, since that was one of the obstacles
preventing vectorization in one of the loops i looked at.

Maybe we should teach the vectorizer to rewrite exit values? If we know a loop will be vectorized after rewriting exit values, there's a stronger incentive to rewrite them. Not sure how hard that would be? Off the top of my head, it should be straightforward to fit into the vectorizer code that classifies instructions.

[lebedev.ri]

In D73501#1925618, @efriedma wrote:

The goal of this change in particular was to really try to get rid of
uses of IV outside of the loop, since that was one of the obstacles
preventing vectorization in one of the loops i looked at.

Maybe we should teach the vectorizer to rewrite exit values? If we know a loop will be vectorized after rewriting exit values, there's a stronger incentive to rewrite them. Not sure how hard that would be? Off the top of my head, it should be straightforward to fit into the vectorizer code that classifies instructions.

That might be worth exploring.

llvm/lib/Transforms/Utils/LoopUtils.cpp

while ((PN = dyn_cast<PHINode>(BBI++))) {
           if (isa<SCEVCouldNotCompute>(ExitValue) ||
               !SE->isLoopInvariant(ExitValue, L) ||
               !isSafeToExpand(ExitValue, *SE))
             continue;
         }
 
         // Computing the value outside of the loop brings no benefit if it is
         // definitely used inside the loop in a way which can not be optimized
-        // away. Avoid doing so unless we know we have a value which computes
-        // the ExitValue already. TODO: This should be merged into SCEV
-        // expander to leverage its knowledge of existing expressions.
-        if (ReplaceExitValue != AlwaysRepl &&
-            !isa<SCEVConstant>(ExitValue) && !isa<SCEVUnknown>(ExitValue) &&
+        // away. Avoid doing so unless either we know we have a value
+        // which computes the ExitValue already, or it is cheap to do so.
+        // TODO: This should be merged into SCEV expander to leverage
+        // its knowledge of existing expressions.
+        bool HighCost = Rewriter.isHighCostExpansion(
+            ExitValue, L, SCEVCheapExpansionBudget, TTI, Inst);
+        if (ReplaceExitValue != AlwaysRepl && HighCost &&
             hasHardUserWithinLoop(L, Inst))
           continue;
 
-        bool HighCost = Rewriter.isHighCostExpansion(
-            ExitValue, L, SCEVCheapExpansionBudget, TTI, Inst);
         Value *ExitVal = Rewriter.expandCodeFor(ExitValue, PN->getType(), Inst);
 
         LLVM_DEBUG(dbgs() << "rewriteLoopExitValues: AfterLoopVal = "
                           << *ExitVal << '\n' << "  LoopVal = " << *Inst
                           << "\n");
 
         if (!isValidRewrite(SE, Inst, ExitVal)) {
           DeadInsts.push_back(ExitVal);
           continue;
         }
 
 #ifndef NDEBUG
         // If we reuse an instruction from a loop which is neither L nor one of

llvm/test/Transforms/IndVarSimplify/dont-recompute.ll

 ; CHECK-NEXT:    [[I_06:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[INC:%.*]], [[FOR_BODY]] ]
 ; CHECK-NEXT:    [[A_05:%.*]] = phi i32 [ 0, [[ENTRY]] ], [ [[ADD:%.*]], [[FOR_BODY]] ]
 ; CHECK-NEXT:    [[ADD]] = add i32 [[A_05]], [[M:%.*]]
 ; CHECK-NEXT:    tail call void @func(i32 [[ADD]])
 ; CHECK-NEXT:    [[INC]] = add nuw nsw i32 [[I_06]], 1
 ; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i32 [[INC]], 186
 ; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR_END:%.*]], label [[FOR_BODY]]
 ; CHECK:       for.end:
-; CHECK-NEXT:    [[ADD_LCSSA:%.*]] = phi i32 [ [[ADD]], [[FOR_BODY]] ]
-; CHECK-NEXT:    tail call void @func(i32 [[ADD_LCSSA]])
+; CHECK-NEXT:    [[TMP0:%.*]] = mul i32 [[M]], 186
+; CHECK-NEXT:    tail call void @func(i32 [[TMP0]])
 ; CHECK-NEXT:    ret void
 ;
 entry:
   br label %for.body
 
 for.body:                                         ; preds = %for.body, %entry
   %i.06 = phi i32 [ 0, %entry ], [ %inc, %for.body ]
   %a.05 = phi i32 [ 0, %entry ], [ %add, %for.body ]

 ; CHECK-NEXT:    [[I_06:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[INC:%.*]], [[FOR_BODY]] ]
 ; CHECK-NEXT:    [[A_05:%.*]] = phi i32 [ 0, [[ENTRY]] ], [ [[ADD:%.*]], [[FOR_BODY]] ]
 ; CHECK-NEXT:    [[ADD]] = add i32 [[A_05]], [[M:%.*]]
 ; CHECK-NEXT:    tail call void @func(i32 [[ADD]])
 ; CHECK-NEXT:    [[INC]] = add nuw nsw i32 [[I_06]], 1
 ; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i32 [[INC]], 186
 ; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR_END:%.*]], label [[FOR_BODY]]
 ; CHECK:       for.end:
-; CHECK-NEXT:    [[ADD_LCSSA:%.*]] = phi i32 [ [[ADD]], [[FOR_BODY]] ]
-; CHECK-NEXT:    ret i32 [[ADD_LCSSA]]
+; CHECK-NEXT:    [[TMP0:%.*]] = mul i32 [[M]], 186
+; CHECK-NEXT:    ret i32 [[TMP0]]
 ;
 entry:
   br label %for.body
 
 for.body:                                         ; preds = %for.body, %entry
   %i.06 = phi i32 [ 0, %entry ], [ %inc, %for.body ]
   %a.05 = phi i32 [ 0, %entry ], [ %add, %for.body ]
   %add = add i32 %a.05, %m

 ; CHECK-NEXT:    [[I_06:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[INC:%.*]], [[FOR_BODY]] ]
 ; CHECK-NEXT:    [[A_05:%.*]] = phi i32 [ 0, [[ENTRY]] ], [ [[ADD:%.*]], [[FOR_BODY]] ]
 ; CHECK-NEXT:    [[ADD]] = add i32 [[A_05]], [[M:%.*]]
 ; CHECK-NEXT:    tail call void @func(i32 [[ADD]])
 ; CHECK-NEXT:    [[INC]] = add nuw nsw i32 [[I_06]], 1
 ; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i32 [[INC]], 186
 ; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR_END:%.*]], label [[FOR_BODY]]
 ; CHECK:       for.end:
-; CHECK-NEXT:    [[ADD_LCSSA:%.*]] = phi i32 [ [[ADD]], [[FOR_BODY]] ]
-; CHECK-NEXT:    tail call void @func(i32 [[ADD_LCSSA]])
+; CHECK-NEXT:    [[TMP0:%.*]] = mul i32 [[M]], 186
+; CHECK-NEXT:    tail call void @func(i32 [[TMP0]])
 ; CHECK-NEXT:    ret void
 ;
 entry:
   br label %for.body
 
 for.body:                                         ; preds = %for.body, %entry
   %i.06 = phi i32 [ 0, %entry ], [ %inc, %for.body ]
   %a.05 = phi i32 [ 0, %entry ], [ %add, %for.body ]

 ; CHECK-NEXT:    [[I_06:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[INC:%.*]], [[FOR_BODY]] ]
 ; CHECK-NEXT:    [[A_05:%.*]] = phi i32 [ 0, [[ENTRY]] ], [ [[ADD:%.*]], [[FOR_BODY]] ]
 ; CHECK-NEXT:    [[ADD]] = add i32 [[A_05]], [[M:%.*]]
 ; CHECK-NEXT:    tail call void @func(i32 [[ADD]])
 ; CHECK-NEXT:    [[INC]] = add nuw nsw i32 [[I_06]], 1
 ; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i32 [[INC]], 186
 ; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR_END:%.*]], label [[FOR_BODY]]
 ; CHECK:       for.end:
-; CHECK-NEXT:    [[ADD_LCSSA:%.*]] = phi i32 [ [[ADD]], [[FOR_BODY]] ]
-; CHECK-NEXT:    [[SOFT_USE:%.*]] = add i32 [[ADD_LCSSA]], 123
+; CHECK-NEXT:    [[TMP0:%.*]] = mul i32 [[M]], 186
+; CHECK-NEXT:    [[SOFT_USE:%.*]] = add i32 [[TMP0]], 123
 ; CHECK-NEXT:    tail call void @func(i32 [[SOFT_USE]])
 ; CHECK-NEXT:    ret void
 ;
 entry:
   br label %for.body
 
 for.body:                                         ; preds = %for.body, %entry
   %i.06 = phi i32 [ 0, %entry ], [ %inc, %for.body ]

 ; CHECK-NEXT:    [[A_05:%.*]] = phi i32 [ 0, [[ENTRY]] ], [ [[ADD:%.*]], [[FOR_BODY]] ]
 ; CHECK-NEXT:    [[ADD]] = add i32 [[A_05]], [[M:%.*]]
 ; CHECK-NEXT:    [[SOFT_USE:%.*]] = add i32 [[ADD]], 123
 ; CHECK-NEXT:    tail call void @func(i32 [[SOFT_USE]])
 ; CHECK-NEXT:    [[INC]] = add nuw nsw i32 [[I_06]], 1
 ; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i32 [[INC]], 186
 ; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR_END:%.*]], label [[FOR_BODY]]
 ; CHECK:       for.end:
-; CHECK-NEXT:    [[ADD_LCSSA:%.*]] = phi i32 [ [[ADD]], [[FOR_BODY]] ]
-; CHECK-NEXT:    tail call void @func(i32 [[ADD_LCSSA]])
+; CHECK-NEXT:    [[TMP0:%.*]] = mul i32 [[M]], 186
+; CHECK-NEXT:    tail call void @func(i32 [[TMP0]])
 ; CHECK-NEXT:    ret void
 ;
 entry:
   br label %for.body
 
 for.body:                                         ; preds = %for.body, %entry
   %i.06 = phi i32 [ 0, %entry ], [ %inc, %for.body ]
   %a.05 = phi i32 [ 0, %entry ], [ %add, %for.body ]

 ; CHECK-NEXT:    [[ADD]] = add i32 [[A_05]], [[M:%.*]]
 ; CHECK-NEXT:    [[SOFT_USE:%.*]] = add i32 [[ADD]], 123
 ; CHECK-NEXT:    [[PIDX:%.*]] = getelementptr i32, i32* [[P:%.*]], i32 [[ADD]]
 ; CHECK-NEXT:    store i32 [[SOFT_USE]], i32* [[PIDX]]
 ; CHECK-NEXT:    [[INC]] = add nuw nsw i32 [[I_06]], 1
 ; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i32 [[INC]], 186
 ; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR_END:%.*]], label [[FOR_BODY]]
 ; CHECK:       for.end:
-; CHECK-NEXT:    [[ADD_LCSSA:%.*]] = phi i32 [ [[ADD]], [[FOR_BODY]] ]
-; CHECK-NEXT:    tail call void @func(i32 [[ADD_LCSSA]])
+; CHECK-NEXT:    [[TMP0:%.*]] = mul i32 [[M]], 186
+; CHECK-NEXT:    tail call void @func(i32 [[TMP0]])
 ; CHECK-NEXT:    ret void
 ;
 entry:
   br label %for.body
 
 for.body:                                         ; preds = %for.body, %entry
   %i.06 = phi i32 [ 0, %entry ], [ %inc, %for.body ]
   %a.05 = phi i32 [ 0, %entry ], [ %add, %for.body ]

llvm/test/Transforms/IndVarSimplify/elim-extend.ll

 ; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nsw i64 [[INDVARS_IV]], 1
 ; CHECK-NEXT:    [[ADR2:%.*]] = getelementptr i8, i8* [[ADDRESS]], i64 [[INDVARS_IV]]
 ; CHECK-NEXT:    store i8 0, i8* [[ADR2]]
 ; CHECK-NEXT:    [[ADR3:%.*]] = getelementptr i8, i8* [[ADDRESS]], i64 [[INDVARS_IV_NEXT]]
 ; CHECK-NEXT:    store i8 0, i8* [[ADR3]]
 ; CHECK-NEXT:    [[INNERCMP:%.*]] = icmp sgt i64 [[TMP0]], [[INDVARS_IV_NEXT]]
 ; CHECK-NEXT:    br i1 [[INNERCMP]], label [[INNERLOOP]], label [[INNEREXIT:%.*]]
 ; CHECK:       innerexit:
-; CHECK-NEXT:    [[INNERCOUNT_LCSSA_WIDE:%.*]] = phi i64 [ [[INDVARS_IV_NEXT]], [[INNERLOOP]] ]
-; CHECK-NEXT:    [[TMP4:%.*]] = trunc i64 [[INNERCOUNT_LCSSA_WIDE]] to i32
+; CHECK-NEXT:    [[TMP4:%.*]] = trunc i64 [[TMP0]] to i32
 ; CHECK-NEXT:    br label [[OUTERMERGE]]
 ; CHECK:       outermerge:
 ; CHECK-NEXT:    [[INNERCOUNT_MERGE]] = phi i32 [ [[TMP4]], [[INNEREXIT]] ], [ [[INNERCOUNT]], [[INNERPREHEADER]] ]
 ; CHECK-NEXT:    [[ADR4:%.*]] = getelementptr i8, i8* [[ADDRESS]], i64 [[INDVARS_IV1]]
 ; CHECK-NEXT:    store i8 0, i8* [[ADR4]]
 ; CHECK-NEXT:    [[OFS5:%.*]] = sext i32 [[INNERCOUNT_MERGE]] to i64
 ; CHECK-NEXT:    [[ADR5:%.*]] = getelementptr i8, i8* [[ADDRESS]], i64 [[OFS5]]
 ; CHECK-NEXT:    store i8 0, i8* [[ADR5]]

llvm/test/Transforms/IndVarSimplify/lrev-existing-umin.ll

 ; CHECK-NEXT:    [[TMP20:%.*]] = or i32 [[TMP19]], [[TMP10:%.*]]
 ; CHECK-NEXT:    [[TMP21:%.*]] = trunc i32 [[TMP20]] to i8
 ; CHECK-NEXT:    [[ADDR22:%.*]] = getelementptr inbounds i8, i8* [[TMP12:%.*]], i64 [[TMP16]]
 ; CHECK-NEXT:    store i8 [[TMP21]], i8* [[ADDR22]], align 1
 ; CHECK-NEXT:    [[TMP22]] = add nuw nsw i32 [[V_1]], 1
 ; CHECK-NEXT:    [[TMP23:%.*]] = icmp slt i32 [[TMP22]], [[TMP14]]
 ; CHECK-NEXT:    br i1 [[TMP23]], label [[NOT_ZERO11]], label [[MAIN_EXIT_SELECTOR:%.*]]
 ; CHECK:       main.exit.selector:
-; CHECK-NEXT:    [[TMP22_LCSSA:%.*]] = phi i32 [ [[TMP22]], [[NOT_ZERO11]] ]
-; CHECK-NEXT:    [[TMP24:%.*]] = icmp slt i32 [[TMP22_LCSSA]], [[LENGTH_I]]
+; CHECK-NEXT:    [[TMP24:%.*]] = icmp slt i32 [[TMP14]], [[LENGTH_I]]
 ; CHECK-NEXT:    br i1 [[TMP24]], label [[NOT_ZERO11_POSTLOOP]], label [[LEAVE:%.*]]
 ; CHECK:       leave:
 ; CHECK-NEXT:    ret void
 ; CHECK:       not_zero11.postloop:
 ; CHECK-NEXT:    ret void
 ;
 not_zero11.preheader:
   %tmp13 = icmp ugt i32 %length.i, %length.i.88

llvm/test/Transforms/IndVarSimplify/pr28705.ll

 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP_I1137:%.*]] = icmp ugt i32 [[SUB_PTR_DIV_I:%.*]], 3
 ; CHECK-NEXT:    [[DOTSROA_SPECULATED:%.*]] = select i1 [[CMP_I1137]], i32 3, i32 [[SUB_PTR_DIV_I]]
 ; CHECK-NEXT:    [[CMP6483126:%.*]] = icmp eq i32 [[DOTSROA_SPECULATED]], 0
 ; CHECK-NEXT:    br i1 [[CMP6483126]], label [[XZ_EXIT:%.*]], label [[FOR_BODY650_LR_PH:%.*]]
 ; CHECK:       for.body650.lr.ph:
 ; CHECK-NEXT:    br label [[FOR_BODY650:%.*]]
 ; CHECK:       loopexit:
-; CHECK-NEXT:    [[INC_I_I_LCSSA:%.*]] = phi i32 [ [[INC_I_I:%.*]], [[FOR_BODY650]] ]
+; CHECK-NEXT:    [[TMP0:%.*]] = add i32 [[DOTSROA_SPECULATED]], 1
 ; CHECK-NEXT:    br label [[XZ_EXIT]]
 ; CHECK:       XZ.exit:
-; CHECK-NEXT:    [[DB_SROA_9_0_LCSSA:%.*]] = phi i32 [ 1, [[ENTRY:%.*]] ], [ [[INC_I_I_LCSSA]], [[LOOPEXIT:%.*]] ]
+; CHECK-NEXT:    [[DB_SROA_9_0_LCSSA:%.*]] = phi i32 [ 1, [[ENTRY:%.*]] ], [ [[TMP0]], [[LOOPEXIT:%.*]] ]
 ; CHECK-NEXT:    br label [[END:%.*]]
 ; CHECK:       for.body650:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[FOR_BODY650_LR_PH]] ], [ [[INC655:%.*]], [[FOR_BODY650]] ]
-; CHECK-NEXT:    [[IV2:%.*]] = phi i32 [ 1, [[FOR_BODY650_LR_PH]] ], [ [[INC_I_I]], [[FOR_BODY650]] ]
+; CHECK-NEXT:    [[IV2:%.*]] = phi i32 [ 1, [[FOR_BODY650_LR_PH]] ], [ [[INC_I_I:%.*]], [[FOR_BODY650]] ]
 ; CHECK-NEXT:    [[ARRAYIDX_I_I1105:%.*]] = getelementptr inbounds i8, i8* [[REF_I1174:%.*]], i32 [[IV2]]
 ; CHECK-NEXT:    store i8 7, i8* [[ARRAYIDX_I_I1105]], align 1
 ; CHECK-NEXT:    [[INC_I_I]] = add nuw nsw i32 [[IV2]], 1
 ; CHECK-NEXT:    [[INC655]] = add nuw nsw i32 [[IV]], 1
 ; CHECK-NEXT:    [[CMP648:%.*]] = icmp eq i32 [[INC655]], [[DOTSROA_SPECULATED]]
 ; CHECK-NEXT:    br i1 [[CMP648]], label [[LOOPEXIT]], label [[FOR_BODY650]]
 ; CHECK:       end:
 ; CHECK-NEXT:    ret void

llvm/test/Transforms/IndVarSimplify/pr39673.ll

 ; CHECK-NEXT:    [[K2:%.*]] = phi i16 [ [[K2_ADD:%.*]], [[LOOP2]] ], [ [[ARG2:%.*]], [[LOOP2_PREHEADER]] ]
 ; CHECK-NEXT:    [[L2:%.*]] = phi i16 [ [[L2_ADD:%.*]], [[LOOP2]] ], [ 0, [[LOOP2_PREHEADER]] ]
 ; CHECK-NEXT:    [[L2_ADD]] = add nuw nsw i16 [[L2]], 1
 ; CHECK-NEXT:    tail call void @foo(i16 [[K2]])
 ; CHECK-NEXT:    [[K2_ADD]] = add nuw nsw i16 [[K2]], 1
 ; CHECK-NEXT:    [[CMP2:%.*]] = icmp ult i16 [[L2_ADD]], 2
 ; CHECK-NEXT:    br i1 [[CMP2]], label [[LOOP2]], label [[LOOP2_END:%.*]]
 ; CHECK:       loop2.end:
-; CHECK-NEXT:    [[K2_ADD_LCSSA:%.*]] = phi i16 [ [[K2_ADD]], [[LOOP2]] ]
-; CHECK-NEXT:    ret i16 [[K2_ADD_LCSSA]]
+; CHECK-NEXT:    [[TMP0:%.*]] = add i16 [[ARG2]], 2
+; CHECK-NEXT:    ret i16 [[TMP0]]
 ;
 entry:
   br label %loop1
 
 loop1:                                           ; preds = %entry, %loop1
   %k1 = phi i16 [ 100, %entry ], [ %k1.add, %loop1 ]
   %l1 = phi i16 [ 0, %entry ], [ %l1.add, %loop1 ]
   %selector = phi i16 [ %arg1, %entry ], [ %arg2, %loop1 ]

 ; CHECK-NEXT:    [[K2:%.*]] = phi i16 [ [[K2_ADD:%.*]], [[LOOP2]] ], [ [[DUMMY]], [[LOOP2_PREHEADER]] ]
 ; CHECK-NEXT:    [[L2:%.*]] = phi i16 [ [[L2_ADD:%.*]], [[LOOP2]] ], [ 0, [[LOOP2_PREHEADER]] ]
 ; CHECK-NEXT:    [[L2_ADD]] = add nuw nsw i16 [[L2]], 1
 ; CHECK-NEXT:    tail call void @foo(i16 [[K2]])
 ; CHECK-NEXT:    [[K2_ADD]] = add nuw nsw i16 [[K2]], 1
 ; CHECK-NEXT:    [[CMP2:%.*]] = icmp ult i16 [[L2_ADD]], 2
 ; CHECK-NEXT:    br i1 [[CMP2]], label [[LOOP2]], label [[LOOP2_END:%.*]]
 ; CHECK:       loop2.end:
-; CHECK-NEXT:    [[K2_ADD_LCSSA:%.*]] = phi i16 [ [[K2_ADD]], [[LOOP2]] ]
-; CHECK-NEXT:    ret i16 [[K2_ADD_LCSSA]]
+; CHECK-NEXT:    [[TMP0:%.*]] = add i16 [[DUMMY]], 2
+; CHECK-NEXT:    ret i16 [[TMP0]]
 ;
 entry:
   br label %loop2.preheader
 
 loop2.preheader:                                 ; preds = %loop1
   %dummy = phi i16 [ %arg, %entry ]
   br label %loop2
 

 ; CHECK-NEXT:    [[K2:%.*]] = phi i16 [ [[K2_ADD:%.*]], [[LOOP2]] ], [ [[TMP0]], [[LOOP2_PREHEADER]] ]
 ; CHECK-NEXT:    [[L2:%.*]] = phi i16 [ [[L2_ADD:%.*]], [[LOOP2]] ], [ 0, [[LOOP2_PREHEADER]] ]
 ; CHECK-NEXT:    [[L2_ADD]] = add nuw nsw i16 [[L2]], 1
 ; CHECK-NEXT:    tail call void @foo(i16 [[K2]])
 ; CHECK-NEXT:    [[K2_ADD]] = add nuw nsw i16 [[K2]], 1
 ; CHECK-NEXT:    [[CMP2:%.*]] = icmp ult i16 [[L2_ADD]], 2
 ; CHECK-NEXT:    br i1 [[CMP2]], label [[LOOP2]], label [[LOOP2_END:%.*]]
 ; CHECK:       loop2.end:
-; CHECK-NEXT:    [[K2_ADD_LCSSA:%.*]] = phi i16 [ [[K2_ADD]], [[LOOP2]] ]
-; CHECK-NEXT:    ret i16 [[K2_ADD_LCSSA]]
+; CHECK-NEXT:    [[TMP1:%.*]] = add i16 [[TMP0]], 2
+; CHECK-NEXT:    ret i16 [[TMP1]]
 ;
 entry:
   br label %loop1
 
 loop1:                                           ; preds = %entry, %loop1
   %k1 = phi i16 [ %arg, %entry ], [ %k1.add, %loop1 ]
   %l1 = phi i16 [ 0, %entry ], [ %l1.add, %loop1 ]
   %k1.add = add nuw nsw i16 %k1, 1