[LSR] Make sure that Factor fits into Base type

[danilaml]

Summary

Fixes pr42770

[danilaml]

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

3974

Avoids truncation/overflow here.

[anna]

llvm/test/Transforms/LoopStrengthReduce/pr42770.ll

1

You could add REQUIRES:assert here along with XFAIL to precommit the test.

[danilaml]

Add missing REQUIRES: asserts

[danilaml]

Addressed Anna's suggestions

[danilaml]

ping

[danilaml]

Ping

[qcolombet]

llvm/test/Transforms/LoopStrengthReduce/pr42770.ll

1

Could you check that we generate something sensible here as opposed to just no-crash?

1

Could you set a more descriptive file name than a pr number?

E.g., incompatible IV type and add the PR number in the comment of the test.

[danilaml]

Addressed Quentin's comments

[danilaml]

llvm/test/Transforms/LoopStrengthReduce/pr42770.ll

1

I've added some checks although I don't really like the idea of checking the generated IR past the labels (and it looks like most of the lit tests in this folder don't do it either), since I don't want to depend on the actual optimizations made by LSR. Just that it won't try to use out-of-range scaling factor for one of the IVs.

[qcolombet]

One last comment, otherwise LGTM.

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

1–3

Could you add a more descriptive comment on what this is testing and how? (I.e., the characteristics of the test and what we should be observing when the optimization does the right thing.)

[danilaml]

Add more comments to the test

[danilaml]

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

1–3

It's more about preventing the wrong logic (that quickly leads to assert), when expecting anything out of the optimization.

In the test case Factor == 2^32 truncated to i16 would be 0, which meant that F.BaseRegs were zeroed out as well.

const SCEV *FactorS = SE.getConstant(IntTy, Factor);

 // Check that multiplying with each base register doesn't overflow.
 for (size_t i = 0, e = F.BaseRegs.size(); i != e; ++i) {
   F.BaseRegs[i] = SE.getMulExpr(F.BaseRegs[i], FactorS)

This then quickly asserted in InsertFormula.

Anyway, hopefully if anyone needs more context, they can look up this review or bug report.

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

if (Base.ScaledReg && Base.ScaledReg->getType()->isPointerTy())
     return;
   for (const SCEV *BaseReg : Base.BaseRegs)
     if (BaseReg->getType()->isPointerTy())
       return;
   assert(!Base.BaseGV && "ICmpZero use is not legal!");
 
   // Check each interesting stride.
   for (int64_t Factor : Factors) {
+    // Check that Factor can be represented by IntTy
+    if (!ConstantInt::isValueValidForType(IntTy, Factor))
+      continue;
     // Check that the multiplication doesn't overflow.
     if (Base.BaseOffset == std::numeric_limits<int64_t>::min() && Factor == -1)
       continue;
     int64_t NewBaseOffset = (uint64_t)Base.BaseOffset * Factor;
     assert(Factor != 0 && "Zero factor not expected!");
     if (NewBaseOffset / Factor != Base.BaseOffset)
       continue;
     // If the offset will be truncated at this use, check that it is in bounds.
for (int64_t Factor : Factors) {
 
     // Check that this scale is legal.
     if (!isLegalUse(TTI, Offset, Offset, LU.Kind, LU.AccessTy, F))
       continue;
 
     // Compensate for the use having MinOffset built into it.
     F.BaseOffset = (uint64_t)F.BaseOffset + Offset - LU.MinOffset;
 
     const SCEV *FactorS = SE.getConstant(IntTy, Factor);
 
     // Check that multiplying with each base register doesn't overflow.
     for (size_t i = 0, e = F.BaseRegs.size(); i != e; ++i) {
       F.BaseRegs[i] = SE.getMulExpr(F.BaseRegs[i], FactorS);
       if (getExactSDiv(F.BaseRegs[i], FactorS, SE) != Base.BaseRegs[i])
         goto next;
     }
 

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

-; Check that it doesn't crash
+; 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
-; XFAIL: *
-; RUN: opt < %s -loop-reduce -S
+; RUN: opt < %s -loop-reduce -S | FileCheck %s
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128-ni:1"
 
+; CHECK-LABEL: @foo(
 define void @foo() {
 bb:
   br label %bb4
-
+; CHECK: bb1:
+; CHECK: %tmp3 = ashr i64 %lsr.iv.next, 32
 bb1:                                              ; preds = %bb13
   %tmp = shl i64 %tmp14, 32
   %tmp2 = add i64 %tmp, 1
   %tmp3 = ashr i64 %tmp2, 32
   ret void
-
+; CHECK bb4:
 bb4:                                              ; preds = %bb13, %bb
   %tmp5 = phi i64 [ 2, %bb ], [ %tmp14, %bb13 ]
   %tmp6 = add i64 %tmp5, 4
   %tmp7 = trunc i64 %tmp6 to i16
   %tmp8 = urem i16 %tmp7, 3
   %tmp9 = mul i16 %tmp8, 2
   %tmp10 = icmp eq i16 %tmp9, 1
   br i1 %tmp10, label %bb11, label %bb13