[LSR] Handle case 1*reg => reg. PR50918

[mkazantsev]

Summary

This patch addresses assertion failure in case when the only found formula for LSR
is 1*reg => reg which was supposed to be an impossible situation, however there
is a test that shows it is possible.

In this case, we can use scale register with scale of 1 as the missing base register.

[reames]

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

514

Given the comment indicates an unimplemented case here, why not just implement it?

Adding the following code just above the assert appears to address your test case.

+
+ if (BaseRegs.empty() && ScaledReg && Scale == 1) {
+ BaseRegs.push_back(ScaledReg);
+ Scale = 0;
+ ScaledReg = nullptr;
+ return;
+ }

Any reason why this is a poor approach?

[huihuiz]

Another note on LSRInstance::GenerateReassociationsImpl() where 1*reg is created, eventually trigger this assertion.

Looks like LSR is rewriting Formula

reg((-64 + (32 * ((112 * (((trunc i32 undef to i8) * ((trunc i32 %tmp3 to i8) + {94,+,-3}<%bb1>)) + {-94,+,3}<%bb1>)) + (-56 * (trunc i32 %tmp3 to i8)) + {-110,+,88}<%bb1>)))) + 1*reg({0,+,-128}<%bb21>)

into

reg({0,+,-128}<%bb21>) + imm(256)

I am not sure this rewrite is correct ?

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

488–489

We will still need to keep this logic unchanged.

BaseRegs could be erased in LSRInstance::GenerateReassociationsImpl(), it's possible to have a non-canonical formula 1*reg, which need to be canonicalized later on.

if (InnerSumSC && SE.getTypeSizeInBits(InnerSumSC->getType()) <= 64 &&
    TTI.isLegalAddImmediate((uint64_t)F.UnfoldedOffset +
                            InnerSumSC->getValue()->getZExtValue())) {
  F.UnfoldedOffset =
      (uint64_t)F.UnfoldedOffset + InnerSumSC->getValue()->getZExtValue();
  if (IsScaledReg)
    F.ScaledReg = nullptr;
  else
    // This may create a non-canonical formula 1*reg
    F.BaseRegs.erase(F.BaseRegs.begin() + Idx);  
} else if (IsScaledReg)
  F.ScaledReg = InnerSum;
else
  F.BaseRegs[Idx] = InnerSum;

[mkazantsev]

In D105009#2849126, @huihuiz wrote:

Another note on LSRInstance::GenerateReassociationsImpl() where 1*reg is created, eventually trigger this assertion.

Looks like LSR is rewriting Formula

reg((-64 + (32 * ((112 * (((trunc i32 undef to i8) * ((trunc i32 %tmp3 to i8) + {94,+,-3}<%bb1>)) + {-94,+,3}<%bb1>)) + (-56 * (trunc i32 %tmp3 to i8)) + {-110,+,88}<%bb1>)))) + 1*reg({0,+,-128}<%bb21>)

into

reg({0,+,-128}<%bb21>) + imm(256)

I am not sure this rewrite is correct ?

Yes it is, because 1st register contains undef and therefore whole thing is undef.

[mkazantsev]

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

514

It seems that null scaled reg is not allowed, because this code always sets it to non-null.

if (!ScaledReg) {
  ScaledReg = BaseRegs.pop_back_val();
  Scale = 1;
}

I don't know if there are other places that rely on this.

[reames]

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

514

This comment is incorrect. ScaledReg can be null, see isCanonical and the return just above this line.

The actual invariant appears to be that if ScaledReg is null, BaseRegs must have 0 or 1 element. Which makes sense, because we're then describing either a constant, or register indexing mode.

[mkazantsev]

Thanks Philip!

[mkazantsev]

Ping

[huihuiz]

I think this fix looks right, but wait a bit for @reames , in case he caught anything unusual ?

[reames]

LGTM as well.

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

 /// \see Formula::BaseRegs.
 bool Formula::isCanonical(const Loop &L) const {
   if (!ScaledReg)
     return BaseRegs.size() <= 1;
 
   if (Scale != 1)
     return true;
 
-  if (Scale == 1 && BaseRegs.empty())
-    return false;
-
   const SCEVAddRecExpr *SAR = dyn_cast<const SCEVAddRecExpr>(ScaledReg);
   if (SAR && SAR->getLoop() == &L)
     return true;
 
   // If ScaledReg is not a recurrent expr, or it is but its loop is not current
   // loop, meanwhile BaseRegs contains a recurrent expr reg related with current
   // loop, we want to swap the reg in BaseRegs with ScaledReg.
   auto I = find_if(BaseRegs, [&](const SCEV *S) {
     return isa<const SCEVAddRecExpr>(S) &&
            (cast<SCEVAddRecExpr>(S)->getLoop() == &L);
   });
   return I == BaseRegs.end();
 }
 
 /// Helper method to morph a formula into its canonical representation.
 /// \see Formula::BaseRegs.
 /// Every formula having more than one base register, must use the ScaledReg
 /// field. Otherwise, we would have to do special cases everywhere in LSR
 /// to treat reg1 + reg2 + ... the same way as reg1 + 1*reg2 + ...
 /// On the other hand, 1*reg should be canonicalized into reg.
 void Formula::canonicalize(const Loop &L) {
   if (isCanonical(L))
     return;
-  // So far we did not need this case. This is easy to implement but it is
-  // useless to maintain dead code. Beside it could hurt compile time.
-  assert(!BaseRegs.empty() && "1*reg => reg, should not be needed.");
 
   // Keep the invariant sum in BaseRegs and one of the variant sum in ScaledReg.
   if (!ScaledReg) {
+    assert(!BaseRegs.empty() && "No base regs");
     ScaledReg = BaseRegs.pop_back_val();
     Scale = 1;
-  }
+  } else if (BaseRegs.empty())
+    Scale = 1;
 
   // If ScaledReg is an invariant with respect to L, find the reg from
   // BaseRegs containing the recurrent expr related with Loop L. Swap the
   // reg with ScaledReg.
   const SCEVAddRecExpr *SAR = dyn_cast<const SCEVAddRecExpr>(ScaledReg);
   if (!SAR || SAR->getLoop() != &L) {
     auto I = find_if(BaseRegs, [&](const SCEV *S) {
       return isa<const SCEVAddRecExpr>(S) &&

llvm/test/Transforms/LoopStrengthReduce/pr50918.ll

+; RUN: opt -S -loop-reduce < %s | FileCheck %s
+;
+; Make sure we don't fail an assertion here.
+
+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() {
+; CHECK-LABEL: test
+bb:
+  br label %bb1
+
+bb1:                                              ; preds = %bb12, %bb
+  %tmp2 = phi i64 [ 94, %bb ], [ %tmp20, %bb12 ]
+  %tmp3 = phi i32 [ -28407, %bb ], [ %tmp23, %bb12 ]
+  %tmp4 = trunc i64 %tmp2 to i32
+  %tmp5 = add i32 %tmp3, %tmp4
+  %tmp6 = mul i32 undef, %tmp5
+  %tmp7 = sub i32 %tmp6, %tmp5
+  %tmp8 = shl i32 %tmp7, 1
+  %tmp9 = add i32 %tmp8, %tmp3
+  %tmp10 = add i32 %tmp9, %tmp4
+  %tmp11 = shl i32 %tmp10, 1
+  br label %bb21
+
+bb12:                                             ; preds = %bb21
+  %tmp13 = mul i32 %tmp22, -101
+  %tmp14 = add i32 %tmp22, 2
+  %tmp15 = add i32 %tmp14, %tmp13
+  %tmp16 = trunc i32 %tmp15 to i8
+  %tmp17 = shl i8 %tmp16, 5
+  %tmp18 = add i8 %tmp17, 64
+  %tmp19 = sext i8 %tmp18 to i32
+  %tmp20 = add nsw i64 %tmp2, -3
+  br label %bb1
+
+bb21:                                             ; preds = %bb21, %bb1
+  %tmp22 = phi i32 [ %tmp11, %bb1 ], [ %tmp23, %bb21 ]
+  %tmp23 = add i32 %tmp22, 1
+  br i1 false, label %bb12, label %bb21
+}