[SCEV] Compute SCEV for ashr(add(shl(x, n), c), m) instr triplet

[vedant-amd]

Summary

%x = shl i64 %w, n
%y = add i64 %x, c
%z = ashr i64 %y, m

The above given instruction triplet is seen many times in the generated
LLVM IR, but SCEV model is not able to compute the SCEV value of AShr
instruction in this case.

This patch models the two cases of the above instruction pattern using
the following expression:

> sext(add(mul(trunc(w), 2^(n-m)), c >> m))

1. when n = m the expression reduces to sext(add(trunc(w), c >> n))

as n-m=0, and multiplying with 2^0 gives the same result.

2. when n > m the expression works as given above.

It also adds several unittest to verify that SCEV is able to compute
the value.

$ opt sext-add-inreg.ll -passes="print<scalar-evolution>"

Comparing the snippets of the result of SCEV analysis:

• SCEV of ashr before change ----------------------------

%idxprom = ashr exact i64 %sext, 32

-->  %idxprom U: [-2147483648,2147483648) S: [-2147483648,2147483648)
Exits: 8                LoopDispositions: { %for.body: Variant }

• SCEV of ashr after change ---------------------------

%idxprom = ashr exact i64 %sext, 32

-->  {0,+,1}<nuw><nsw><%for.body> U: [0,9) S: [0,9)
Exits: 8                LoopDispositions: { %for.body: Computable }

LoopDisposition of the given SCEV was LoopVariant before, after adding
the new way to model the instruction, the LoopDisposition becomes
LoopComputable as it is able to compute the SCEV of the instruction.

[vedant-amd]

Hey @fhahn @nikic @mkazantsev can you please review this patch, I stumbled upon this while working on a bug in LSR, this patch does fail one of the unit test-case (scaling-factor-incompat-type.ll) in LSR. I believe that might be an effect of SCEV of this AShr pattern being computed, as LSR generally does do some optimizations based on the Shl + Add + AShr instructions.

[vedant-amd]

In D152278#4399751, @vedant-amd wrote:

Hey @fhahn @nikic @mkazantsev can you please review this patch, I stumbled upon this while working on a bug in LSR, this patch does fail one of the unit test-case (scaling-factor-incompat-type.ll) in LSR. I believe that might be an effect of SCEV of this AShr pattern being computed, as LSR generally does do some optimizations based on the Shl + Add + AShr instructions.

ping ! Could you please take a look at this patch once.

[efriedma]

llvm/lib/Analysis/ScalarEvolution.cpp

7890

Is there some reason to expect that "c" fits into an int64_t?

7891

I guess the reason AddOperandCI has to be a constant is that this shift needs to constant-fold?

7894

This could be extended to cases where n is greater than m? You can skip that for the initial patch, of course.

I don't really see any reason to restrict the shift amounts like this; the transform is pretty restricted even without that. What effect are you worried about?

llvm/test/Analysis/ScalarEvolution/sext-add-inreg.ll

38

Try to avoid "undef" in testcases where it isn't relevant. I don't think it really has much effect here, but still.

[vedant-amd]

llvm/lib/Analysis/ScalarEvolution.cpp

7890

Right, I need to add a check like this I guess ?

if (CI->getValue().uge(BitWidth))

7891

Theoretically, it doesn't have to be a constant. But, I don't see where such a IR will be emitted. I can handle this case in a future patch.

This IR is usually emitted for the following C code. InstCombine does the optimization.

int64_t a = 10;
int32_t b = a - 1;
printf("%d", arr[b]);

[efriedma]

llvm/lib/Analysis/ScalarEvolution.cpp

7890

That doesn't look like the right check.

If it were necessary, you could use isIntN or something like that. But you should just be able to just do the math in APInt: AddOperandCI->getValue().ashr(AShrAmt) or something like that.

[vedant-amd]

Updated unit test to remove ret undefs

[vedant-amd]

llvm/test/Analysis/ScalarEvolution/sext-add-inreg.ll

38

Sure, will keep this in mind.

[vedant-amd]

llvm/lib/Analysis/ScalarEvolution.cpp

7894

This could be extended to cases where n is greater than m? You can skip that for the initial patch, of course.

I could do that, but the original goal was to handle sext(trunc) expression that are expanded into these statements by instcombine.

I don't really see any reason to restrict the shift amounts like this; the transform is pretty restricted even without that. What effect are you worried about?

We only wanted to support the data types supported by C/C++, and also since these instr are transformed from sext(trunc) it makes sense to just support standard integer types.

[vedant-amd]

llvm/lib/Analysis/ScalarEvolution.cpp

7891

I guess the reason AddOperandCI has to be a constant is that this shift needs to constant-fold?

This can be implemented for non-constants as well, maybe in a future patch. But, it involves coming up with complex SCEV expression involving div.

[vedant-amd]

Added check to make sure AddConstant isn't nullptr and few other changes.

[vedant-amd]

llvm/lib/Analysis/ScalarEvolution.cpp

7890

I have made the following change, please take a look once.

[vedant-amd]

Hey @efriedma , I have made the requested changes (and replied to the questions). Please let me know if anything more needs to be done. Thanks !

[vedant-amd]

updated using clang-format

[nikic]

I assume the motivation for this is the following InstCombine transform? https://llvm.godbolt.org/z/zd63TWKbW I don't think we can change that canonicalization, so undoing it in SCEV is fine.

llvm/lib/Analysis/ScalarEvolution.cpp

7879–7907

We already have code to handle the general shl+ashr pattern here, including for the case where n and m are not the same. We should reuse the same code. For your pattern, we'd just have an extra add at the start.

[vedant-amd]

llvm/lib/Analysis/ScalarEvolution.cpp

7879–7907

That could be done, but it would be a major refactoring. I will post a patch anyways.

[vedant-amd]

In D152278#4407841, @nikic wrote:

I assume the motivation for this is the following InstCombine transform? https://llvm.godbolt.org/z/zd63TWKbW I don't think we can change that canonicalization, so undoing it in SCEV is fine.

Yup, that's correct. This canonicalization is used several times in LSR, so having it's SCEV might be beneficial.

[vedant-amd]

Refactored code to reuse ashr + shl handling code

[vedant-amd]

In D152278#4407841, @nikic wrote:

I assume the motivation for this is the following InstCombine transform? https://llvm.godbolt.org/z/zd63TWKbW I don't think we can change that canonicalization, so undoing it in SCEV is fine.

Hey @nikic, I did refactor the change, please take a look, all the SCEV test cases do pass with it. It look correct functionally.

[vedant-amd]

In D152278#4408118, @vedant-amd wrote:

In D152278#4407841, @nikic wrote:

I assume the motivation for this is the following InstCombine transform? https://llvm.godbolt.org/z/zd63TWKbW I don't think we can change that canonicalization, so undoing it in SCEV is fine.

Hey @nikic, I did refactor the change, please take a look, all the SCEV test cases do pass with it. It look correct functionally.

ping ! could you please give a +1 ? @nikic @efriedma

[xbolva00]

You should update checks in loopstrengthreduce::scaling-factor-incompat-type.ll

[vedant-amd]

In D152278#4411959, @xbolva00 wrote:

You should update checks in loopstrengthreduce::scaling-factor-incompat-type.ll

I was going to send another patch for that, testcase failure. Sure, will do so.

[vedant-amd]

Ping ! I didn't add the LSR failing testcase fix here, because I honestly don't know if it uncovered a bug, or it's a valid transformation in LSR.

[xbolva00]

You have to update that file anyway. Pre-commit builds are clearly failing.

[vedant-amd]

In D152278#4416367, @xbolva00 wrote:

You have to update that file anyway. Pre-commit builds are clearly failing.

Right, is it fine if I mark the test case as XFAIL for now ?

[nikic]

In D152278#4416394, @vedant-amd wrote:

In D152278#4416367, @xbolva00 wrote:

You have to update that file anyway. Pre-commit builds are clearly failing.

Right, is it fine if I mark the test case as XFAIL for now ?

No, you need to regenerate the test by running the update_test_checks.py script.

llvm/lib/Analysis/ScalarEvolution.cpp

7892

There should be no restriction on the shift amount.

7896

We should verify that the add constant has lowest n bits unset, to make reassociation valid. It doesn't matter if n==m, but it matters if n!=m.

7906

You can keep the truncate in the comment code by making this trunc(add()) instead of add(trunc()). Unless I'm missing something, they're equivalent in this context.

7916

Stray newline

llvm/test/Analysis/ScalarEvolution/sext-add-inreg.ll

7

You can test these cases with basic patterns using just the shl+add+ashr sequence, without a loop (though it's also ok to keep a loop test as a motivating case). Please also test the case where the shift amounts are different.

[vedant-amd]

In D152278#4417345, @nikic wrote:

In D152278#4416394, @vedant-amd wrote:

In D152278#4416367, @xbolva00 wrote:

You have to update that file anyway. Pre-commit builds are clearly failing.

Right, is it fine if I mark the test case as XFAIL for now ?

No, you need to regenerate the test by running the update_test_checks.py script.

Will do so, I was not sure if the testcase will be still valid after the updated CHECKs.

[vedant-amd]

updated failing testcase in LSR

[vedant-amd]

removed restriction on shift amount and the corresponding test case

[vedant-amd]

llvm/lib/Analysis/ScalarEvolution.cpp

7896

Do you mean to say check for unset bits from nth bit to the mth bit ? because anything lower than mth bit will anyways be irrelevant once we right shift by m amount.

[vedant-amd]

llvm/lib/Analysis/ScalarEvolution.cpp

7896

I tried to understand this, I am not able to make sense of it. Can you explain further what you mean to say ?

[vedant-amd]

updated code to shift right the AddConstant by ShlAmt and flip add, trunc exprs

llvm/lib/Analysis/ScalarEvolution.cpp

7906

So, it should look like this ?

AddTruncateExpr = getTruncateExpr(getAddExpr(ShlOp0SCEV, AddConstant), TruncTy);

[vedant-amd]

In D152278#4420657, @vedant-amd wrote:

updated code to shift right the AddConstant by ShlAmt and flip add, trunc exprs

ping !! I have addressed majority of the comments.

[vedant-amd]

ping !! @nikic can you take a look at this, thanks !

[vedant-amd]

Rebase

[vedant-amd]

Updated LSR testcase and added new testcases for AShr SCEV model

[vedant-amd]

Hey @nikic and @efriedma Sorry for the ping again, but I have addressed all the comments (added the testcases as well), can you please review once again, it's been stuck since a long time. Thanks for your time.

[efriedma]

llvm/test/Analysis/ScalarEvolution/sext-add-inreg-unequal.ll

13

How is this equivalent? Say %a is zero; the original function returns 1, this SCEV expression returns 0. (I think maybe the "ashr" of the constant is shifting by 10, instead of shifting by 8?)

[vedant-amd]

llvm/test/Analysis/ScalarEvolution/sext-add-inreg-unequal.ll

13

Yeah, the SCEV is wrong. I will fix this. This is what is should have been, but it's a bit opposite.

= (a*2^10 + 256)/2*8
= a*4 + 1

So, we need SCEV like this:

2^(shl_amt - ashr_amt) * a + c >> ashr_amt

I have updated my code, here's the correct SCEV:

(1 + (sext i56 (4 * (trunc i64 %a to i56)) to i64))<nuw><nsw> U: [1,-2) S: [-36028797018963967,36028797018963966)

Does it seem correct ?

[vedant-amd]

Fixed issue with generated SCEV for ShlAmt > AshrAmt

[vedant-amd]

Hey @efriedma Thanks for spotting the bug, I updated the SCEV for case when m > n, it seems to be correct now. Can you please review the patch, thanks !

CC: @nikic

[efriedma]

llvm/test/Analysis/ScalarEvolution/sext-add-inreg-unequal.ll

13

I suspect the updated code isn't right... can you add an example with a larger operand to the add? The add needs to happen before the sign-extend, but in this specific example, that doesn't matter because the two expressions are equivalent.

[vedant-amd]

llvm/test/Analysis/ScalarEvolution/sext-add-inreg-unequal.ll

13

I will add one, but I believe we can move the add out of the sext as the add constant is already shifted right by Ashr amount.

[vedant-amd]

llvm/test/Analysis/ScalarEvolution/sext-add-inreg-unequal.ll

13

Also, I am confused about one thing, the Type of MulExpr turns out to be i56 and that of the addConstant is i64, I am able to add them before the Sign extend. Adding the m > n part to this ashr model seems to buggy at this point, as I had proposed can this patch just address the case where m=n ? and I submit, the m > n thing later with thorough thinking. But, I think @nikic wants them in the same patch.

[vedant-amd]

llvm/test/Analysis/ScalarEvolution/sext-add-inreg-unequal.ll

13

Adding to the previous comment, the Ashr + Add + Shl with shlamt > ashramt quite rarely occur in LLVM IR. But, the case where the shlamt = ashramt is quite common in LLVM IR, notably because instcombine like passes do the transformation. I propose that this patch just address the latter and I send a patch for the m > n case at a later point. This patch is stuck from a long time, and just taking care of m=n case won't negatively affect as it'll safely exit in the m > n case.

Please let me know your thoughts about this, thanks ! cc: @nikic

[vedant-amd]

ping ping !!

[efriedma]

I'm not sure why you're having so much trouble with the unequal shift math. The case of unequal shift amount is really just treating the shl as two shifts: one shift by an arbitrary amount, followed by one shift with shift amount equal to the ashr.

That said I'd be okay with a patch that bailed out on that case.

[vedant-amd]

Update the SCEV code and add a new testcase

[vedant-amd]

In D152278#4590846, @efriedma wrote:

I'm not sure why you're having so much trouble with the unequal shift math. The case of unequal shift amount is really just treating the shl as two shifts: one shift by an arbitrary amount, followed by one shift with shift amount equal to the ashr.

I am having trouble with keeping the addition part inside the SextExpr thing, because it always returns back i64 int, but now came up with a better implementation. It seems correct to me, please take a look.

That said I'd be okay with a patch that bailed out on that case.

In D152278#4590846, @efriedma wrote:

I'm not sure why you're having so much trouble with the unequal shift math. The case of unequal shift amount is really just treating the shl as two shifts: one shift by an arbitrary amount, followed by one shift with shift amount equal to the ashr.

That said I'd be okay with a patch that bailed out on that case.

[vedant-amd]

updated with clang-format

[vedant-amd]

added empty line at end of file in a test case

[vedant-amd]

@efriedma I have fixed the SCEV part, it mostly seems correct. Also added the testcase with large add constant. Please take a look once ! thanks !

[vedant-amd]

ping !

[vedant-amd]

Rebased

[efriedma]

The revised logic makes sense.

llvm/lib/Analysis/ScalarEvolution.cpp

7907

Instead of checking if (ShlAmt > AShrAmt) here, can you just unconditionally do AddTruncateExpr = getTruncateExpr(ShlOp0SCEV, TruncTy);, then add an if (L->getOpcode() != Instruction::Shl) check to the equal shift amount case?

Or better, just unify the ShlAmt > AShrAmt and ShlAmt == AShrAmt cases; the logic for the ShlAmt > AShrAmt case should just work for the ShlAmt == AShrAmt case (it ends up multiplying by a constant 1, which simplifies to exactly the same thing as the existing ShlAmt == AShrAmt code).

[vedant-amd]

Simplified expression handling code, and cleaned up other things

llvm/lib/Analysis/ScalarEvolution.cpp

7907

I have implemented the second suggestion, refactored and cleaned up the comments. Now the code looks in good shape. Please give a final review for the same.

[efriedma]

LGTM

[vedant-amd]

Updated the commit message

llvm/lib/Analysis/ScalarEvolution.cpp

case Instruction::Shl:
         }
 
         ConstantInt *X = ConstantInt::get(
             getContext(), APInt::getOneBitSet(BitWidth, SA->getZExtValue()));
         return getMulExpr(getSCEV(BO->LHS), getConstant(X), Flags);
       }
       break;
 
-    case Instruction::AShr: {
+    case Instruction::AShr:
       // AShr X, C, where C is a constant.
       ConstantInt *CI = dyn_cast<ConstantInt>(BO->RHS);
       if (!CI)
         break;
 
       Type *OuterTy = BO->LHS->getType();
       uint64_t BitWidth = getTypeSizeInBits(OuterTy);
       // If the shift count is not less than the bitwidth, the result of
       // the shift is undefined. Don't try to analyze it, because the
       // resolution chosen here may differ from the resolution chosen in
       // other parts of the compiler.
       if (CI->getValue().uge(BitWidth))
         break;
 
       if (CI->isZero())
         return getSCEV(BO->LHS); // shift by zero --> noop
 
       uint64_t AShrAmt = CI->getZExtValue();
       Type *TruncTy = IntegerType::get(getContext(), BitWidth - AShrAmt);
 
       Operator *L = dyn_cast<Operator>(BO->LHS);
-      if (L && L->getOpcode() == Instruction::Shl) {
+      const SCEV *AddTruncateExpr = nullptr;
+      ConstantInt *ShlAmtCI = nullptr;
+      const SCEV *AddConstant = nullptr;
+
+      if (L && L->getOpcode() == Instruction::Add) {
+        // X = Shl A, n
+        // Y = Add X, c
+        // Z = AShr Y, m
+        // n, c and m are constants.
+
+        Operator *LShift = dyn_cast<Operator>(L->getOperand(0));
+        ConstantInt *AddOperandCI = dyn_cast<ConstantInt>(L->getOperand(1));
+        if (LShift && LShift->getOpcode() == Instruction::Shl) {
+          if (AddOperandCI) {
+            const SCEV *ShlOp0SCEV = getSCEV(LShift->getOperand(0));
+            ShlAmtCI = dyn_cast<ConstantInt>(LShift->getOperand(1));
+            // since we truncate to TruncTy, the AddConstant should be of the
+            // same type, so create a new Constant with type same as TruncTy.
+            // Also, the Add constant should be shifted right by AShr amount.
+            APInt AddOperand = AddOperandCI->getValue().ashr(AShrAmt);
+            AddConstant = getConstant(TruncTy, AddOperand.getZExtValue(),
+                                      AddOperand.isSignBitSet());
+            // we model the expression as sext(add(trunc(A), c << n)), since the
+            // sext(trunc) part is already handled below, we create a
+            // AddExpr(TruncExp) which will be used later.
+            AddTruncateExpr = getTruncateExpr(ShlOp0SCEV, TruncTy);
+          }
+        }
+      } else if (L && L->getOpcode() == Instruction::Shl) {
         // X = Shl A, n
         // Y = AShr X, m
         // Both n and m are constant.
 
         const SCEV *ShlOp0SCEV = getSCEV(L->getOperand(0));
-        if (L->getOperand(1) == BO->RHS)
-          // For a two-shift sext-inreg, i.e. n = m,
-          // use sext(trunc(x)) as the SCEV expression.
-          return getSignExtendExpr(
-              getTruncateExpr(ShlOp0SCEV, TruncTy), OuterTy);
+        ShlAmtCI = dyn_cast<ConstantInt>(L->getOperand(1));
+        AddTruncateExpr = getTruncateExpr(ShlOp0SCEV, TruncTy);
+      }
 
-        ConstantInt *ShlAmtCI = dyn_cast<ConstantInt>(L->getOperand(1));
-        if (ShlAmtCI && ShlAmtCI->getValue().ult(BitWidth)) {
-          uint64_t ShlAmt = ShlAmtCI->getZExtValue();
-          if (ShlAmt > AShrAmt) {
-            // When n > m, use sext(mul(trunc(x), 2^(n-m)))) as the SCEV
-            // expression. We already checked that ShlAmt < BitWidth, so
-            // the multiplier, 1 << (ShlAmt - AShrAmt), fits into TruncTy as
-            // ShlAmt - AShrAmt < Amt.
-            APInt Mul = APInt::getOneBitSet(BitWidth - AShrAmt,
-                                            ShlAmt - AShrAmt);
-            return getSignExtendExpr(
-                getMulExpr(getTruncateExpr(ShlOp0SCEV, TruncTy),
-                getConstant(Mul)), OuterTy);
-          }
+      if (AddTruncateExpr && ShlAmtCI) {
+        // We can merge the two given cases into a single SCEV statement,
+        // incase n = m, the mul expression will be 2^0, so it gets resolved to
+        // a simpler case. The following code handles the two cases:
+        //
+        // 1) For a two-shift sext-inreg, i.e. n = m,
+        //    use sext(trunc(x)) as the SCEV expression.
+        //
+        // 2) When n > m, use sext(mul(trunc(x), 2^(n-m)))) as the SCEV
+        //    expression. We already checked that ShlAmt < BitWidth, so
+        //    the multiplier, 1 << (ShlAmt - AShrAmt), fits into TruncTy as
+        //    ShlAmt - AShrAmt < Amt.
+        uint64_t ShlAmt = ShlAmtCI->getZExtValue();
+        if (ShlAmtCI->getValue().ult(BitWidth) && ShlAmt >= AShrAmt) {
+          APInt Mul = APInt::getOneBitSet(BitWidth - AShrAmt, ShlAmt - AShrAmt);
+          const SCEV *CompositeExpr =
+              getMulExpr(AddTruncateExpr, getConstant(Mul));
+          if (L->getOpcode() != Instruction::Shl)
+            CompositeExpr = getAddExpr(CompositeExpr, AddConstant);
+
+          return getSignExtendExpr(CompositeExpr, OuterTy);
         }
       }
       break;
     }
-    }
-  }
 
   switch (U->getOpcode()) {
   case Instruction::Trunc:
     return getTruncateExpr(getSCEV(U->getOperand(0)), U->getType());
 
   case Instruction::ZExt:
     return getZeroExtendExpr(getSCEV(U->getOperand(0)), U->getType());
 

llvm/test/Analysis/ScalarEvolution/sext-add-inreg-loop.ll

+; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py UTC_ARGS: --version 2
+; RUN: opt < %s -disable-output "-passes=print<scalar-evolution>" 2>&1 | FileCheck %s
+
+@.str = private unnamed_addr constant [3 x i8] c"%x\00", align 1
+
+define dso_local i32 @test_loop(ptr nocapture noundef readonly %x) {
+; CHECK-LABEL: 'test_loop'
+; CHECK-NEXT:  Classifying expressions for: @test_loop
+; CHECK-NEXT:    %i.03 = phi i64 [ 1, %entry ], [ %inc, %for.body ]
+; CHECK-NEXT:    --> {1,+,1}<nuw><nsw><%for.body> U: [1,10) S: [1,10) Exits: 9 LoopDispositions: { %for.body: Computable }
+; CHECK-NEXT:    %conv = shl nuw nsw i64 %i.03, 32
+; CHECK-NEXT:    --> {4294967296,+,4294967296}<nuw><nsw><%for.body> U: [4294967296,38654705665) S: [4294967296,38654705665) Exits: 38654705664 LoopDispositions: { %for.body: Computable }
+; CHECK-NEXT:    %sext = add nsw i64 %conv, -4294967296
+; CHECK-NEXT:    --> {0,+,4294967296}<nuw><nsw><%for.body> U: [0,34359738369) S: [0,34359738369) Exits: 34359738368 LoopDispositions: { %for.body: Computable }
+; CHECK-NEXT:    %idxprom = ashr exact i64 %sext, 32
+; CHECK-NEXT:    --> {0,+,1}<nuw><nsw><%for.body> U: [0,9) S: [0,9) Exits: 8 LoopDispositions: { %for.body: Computable }
+; CHECK-NEXT:    %arrayidx = getelementptr inbounds i32, ptr %x, i64 %idxprom
+; CHECK-NEXT:    --> {%x,+,4}<nuw><%for.body> U: full-set S: full-set Exits: (32 + %x) LoopDispositions: { %for.body: Computable }
+; CHECK-NEXT:    %0 = load i32, ptr %arrayidx, align 4
+; CHECK-NEXT:    --> %0 U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %for.body: Variant }
+; CHECK-NEXT:    %call = tail call i32 (ptr, ...) @printf(ptr noundef nonnull dereferenceable(1) @.str, i32 noundef %0)
+; CHECK-NEXT:    --> %call U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %for.body: Variant }
+; CHECK-NEXT:    %inc = add nuw nsw i64 %i.03, 1
+; CHECK-NEXT:    --> {2,+,1}<nuw><nsw><%for.body> U: [2,11) S: [2,11) Exits: 10 LoopDispositions: { %for.body: Computable }
+; CHECK-NEXT:  Determining loop execution counts for: @test_loop
+; CHECK-NEXT:  Loop %for.body: backedge-taken count is 8
+; CHECK-NEXT:  Loop %for.body: constant max backedge-taken count is 8
+; CHECK-NEXT:  Loop %for.body: symbolic max backedge-taken count is 8
+; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is 8
+; CHECK-NEXT:   Predicates:
+; CHECK:       Loop %for.body: Trip multiple is 9
+;
+entry:
+  br label %for.body
+
+for.cond.cleanup:                                 ; preds = %for.body
+  ret i32 0
+
+for.body:                                         ; preds = %entry, %for.body
+  %i.03 = phi i64 [ 1, %entry ], [ %inc, %for.body ]
+  %conv = shl nuw nsw i64 %i.03, 32
+  %sext = add nsw i64 %conv, -4294967296
+  %idxprom = ashr exact i64 %sext, 32
+  %arrayidx = getelementptr inbounds i32, ptr %x, i64 %idxprom
+  %0 = load i32, ptr %arrayidx, align 4
+  %call = tail call i32 (ptr, ...) @printf(ptr noundef nonnull dereferenceable(1) @.str, i32 noundef %0)
+  %inc = add nuw nsw i64 %i.03, 1
+  %exitcond.not = icmp eq i64 %inc, 10
+  br i1 %exitcond.not, label %for.cond.cleanup, label %for.body
+}
+
+declare noundef i32 @printf(ptr nocapture noundef readonly, ...)

llvm/test/Analysis/ScalarEvolution/sext-add-inreg-unequal.ll

+; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py UTC_ARGS: --version 2
+; RUN: opt < %s -disable-output "-passes=print<scalar-evolution>" 2>&1 | FileCheck %s
+
+define i64 @test00(i64 %a) {
+; CHECK-LABEL: 'test00'
+; CHECK-NEXT:  Classifying expressions for: @test00
+; CHECK-NEXT:    %add = shl i64 %a, 10
+; CHECK-NEXT:    --> (1024 * %a) U: [0,-1023) S: [-9223372036854775808,9223372036854774785)
+; CHECK-NEXT:    %shl = add i64 %add, 256
+; CHECK-NEXT:    --> (256 + (1024 * %a))<nuw><nsw> U: [256,-767) S: [-9223372036854775552,9223372036854775041)
+; CHECK-NEXT:    %ashr = ashr exact i64 %shl, 8
+; CHECK-NEXT:    --> (1 + (sext i56 (4 * (trunc i64 %a to i56)) to i64))<nuw><nsw> U: [1,-2) S: [-36028797018963967,36028797018963966)
+; CHECK-NEXT:  Determining loop execution counts for: @test00
+;
+  %add = shl i64 %a, 10
+  %shl = add i64 %add, 256
+  %ashr = ashr exact i64 %shl, 8
+  ret i64 %ashr
+}
+
+define i64 @test01(i64 %a) {
+; CHECK-LABEL: 'test01'
+; CHECK-NEXT:  Classifying expressions for: @test01
+; CHECK-NEXT:    %add = shl i64 %a, 6
+; CHECK-NEXT:    --> (64 * %a) U: [0,-63) S: [-9223372036854775808,9223372036854775745)
+; CHECK-NEXT:    %shl = add i64 %add, 256
+; CHECK-NEXT:    --> (256 + (64 * %a)) U: [0,-63) S: [-9223372036854775808,9223372036854775745)
+; CHECK-NEXT:    %ashr = ashr exact i64 %shl, 8
+; CHECK-NEXT:    --> %ashr U: [-36028797018963968,36028797018963968) S: [-36028797018963968,36028797018963968)
+; CHECK-NEXT:  Determining loop execution counts for: @test01
+;
+  %add = shl i64 %a, 6
+  %shl = add i64 %add, 256
+  %ashr = ashr exact i64 %shl, 8
+  ret i64 %ashr
+}
+
+define i64 @test02(i64 %a) {
+; CHECK-LABEL: 'test02'
+; CHECK-NEXT:  Classifying expressions for: @test02
+; CHECK-NEXT:    %add = shl i64 %a, 12
+; CHECK-NEXT:    --> (4096 * %a) U: [0,-4095) S: [-9223372036854775808,9223372036854771713)
+; CHECK-NEXT:    %shl = add i64 %add, 4096
+; CHECK-NEXT:    --> (4096 + (4096 * %a)) U: [0,-4095) S: [-9223372036854775808,9223372036854771713)
+; CHECK-NEXT:    %ashr = ashr exact i64 %shl, 8
+; CHECK-NEXT:    --> (sext i56 (16 + (16 * (trunc i64 %a to i56))) to i64) U: [0,-15) S: [-36028797018963968,36028797018963953)
+; CHECK-NEXT:  Determining loop execution counts for: @test02
+;
+  %add = shl i64 %a, 12
+  %shl = add i64 %add, 4096
+  %ashr = ashr exact i64 %shl, 8
+  ret i64 %ashr
+}

llvm/test/Analysis/ScalarEvolution/sext-add-inreg.ll

+; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py UTC_ARGS: --version 2
+; RUN: opt < %s -disable-output "-passes=print<scalar-evolution>" 2>&1 | FileCheck %s
+
+define i64 @test(i64 %a) {
+; CHECK-LABEL: 'test'
+; CHECK-NEXT:  Classifying expressions for: @test
+; CHECK-NEXT:    %add = shl i64 %a, 8
+; CHECK-NEXT:    --> (256 * %a) U: [0,-255) S: [-9223372036854775808,9223372036854775553)
+; CHECK-NEXT:    %shl = add i64 %add, 256
+; CHECK-NEXT:    --> (256 + (256 * %a)) U: [0,-255) S: [-9223372036854775808,9223372036854775553)
+; CHECK-NEXT:    %ashr = ashr exact i64 %shl, 8
+; CHECK-NEXT:    --> (sext i56 (1 + (trunc i64 %a to i56)) to i64) U: [-36028797018963968,36028797018963968) S: [-36028797018963968,36028797018963968)
+; CHECK-NEXT:  Determining loop execution counts for: @test
+;
+  %add = shl i64 %a, 8
+  %shl = add i64 %add, 256
+  %ashr = ashr exact i64 %shl, 8
+  ret i64 %ashr
+}

llvm/test/Transforms/LoopStrengthReduce/scaling-factor-incompat-type.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; Check that it doesn't crash by generating formula with zero in base register
 ; when one of the IV factors does't fit (2^32 in this test) the formula type
 ; see pr42770
 ; REQUIRES: asserts
 ; RUN: opt < %s -loop-reduce -S | FileCheck %s
-
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128-ni:1"
 
 define void @foo() {
 ; CHECK-LABEL: @foo(
 ; CHECK-NEXT:  bb:
 ; CHECK-NEXT:    br label [[BB4:%.*]]
 ; CHECK:       bb1:
-; CHECK-NEXT:    [[T3:%.*]] = ashr i64 [[LSR_IV_NEXT:%.*]], 32
+; CHECK-NEXT:    [[T:%.*]] = shl i64 [[T14:%.*]], 32
+; CHECK-NEXT:    [[T2:%.*]] = add i64 [[T]], 1
+; CHECK-NEXT:    [[T3:%.*]] = ashr i64 [[T2]], 32
 ; CHECK-NEXT:    ret void
 ; CHECK:       bb4:
-; CHECK-NEXT:    [[LSR_IV1:%.*]] = phi i16 [ [[LSR_IV_NEXT2:%.*]], [[BB13:%.*]] ], [ 6, [[BB:%.*]] ]
-; CHECK-NEXT:    [[LSR_IV:%.*]] = phi i64 [ [[LSR_IV_NEXT]], [[BB13]] ], [ 8589934593, [[BB]] ]
-; CHECK-NEXT:    [[T5:%.*]] = phi i64 [ 2, [[BB]] ], [ [[T14:%.*]], [[BB13]] ]
+; CHECK-NEXT:    [[LSR_IV:%.*]] = phi i16 [ [[LSR_IV_NEXT:%.*]], [[BB13:%.*]] ], [ 6, [[BB:%.*]] ]
+; CHECK-NEXT:    [[T5:%.*]] = phi i64 [ 2, [[BB]] ], [ [[T14]], [[BB13]] ]
 ; CHECK-NEXT:    [[T6:%.*]] = add i64 [[T5]], 4
 ; CHECK-NEXT:    [[T7:%.*]] = trunc i64 [[T6]] to i16
 ; CHECK-NEXT:    [[T8:%.*]] = urem i16 [[T7]], 3
 ; CHECK-NEXT:    [[T9:%.*]] = mul i16 [[T8]], 2
-; CHECK-NEXT:    [[LSR_IV_NEXT]] = add nuw nsw i64 [[LSR_IV]], 25769803776
-; CHECK-NEXT:    [[LSR_IV_NEXT2]] = add nuw nsw i16 [[LSR_IV1]], 6
+; CHECK-NEXT:    [[LSR_IV_NEXT]] = add nuw nsw i16 [[LSR_IV]], 6
 ; CHECK-NEXT:    [[T14]] = add nuw nsw i64 [[T5]], 6
 ; CHECK-NEXT:    [[T10:%.*]] = icmp eq i16 [[T9]], 1
 ; CHECK-NEXT:    br i1 [[T10]], label [[BB11:%.*]], label [[BB13]]
 ; CHECK:       bb11:
-; CHECK-NEXT:    [[T12:%.*]] = udiv i16 1, [[LSR_IV1]]
+; CHECK-NEXT:    [[T12:%.*]] = udiv i16 1, [[LSR_IV]]
 ; CHECK-NEXT:    unreachable
 ; CHECK:       bb13:
 ; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB4]]
 ;
 bb:
   br label %bb4
 bb1:                                              ; preds = %bb13
   %t = shl i64 %t14, 32