[LSR] Check SCEV on isZero() after extend. PR40514

[mkazantsev]

Summary

When LSR first adds SCEVs to BaseRegs, it only does it if isZero() has returned false.
In the end, in invocation of InsertFormula, it asserts that all values there are still not
zero constants. However between these two points, it makes some transformations,
in particular extends them to wider type.

SCEV does not give us guarantee that if S is not a constant zero, then sext(S) is
also not a constant zero. It might have missed some optimizing transforms when it
was calculating S and then made them when it took sext. For example, it may
happen if previously optimizing transforms were limited by depth or somehow else.

This patch adds a bailout when we may end up with a zero SCEV after extension.

[samparker]

Hi Max,

Why don't be just return false from InsertFormula if we find zero?

[mkazantsev]

Let me check if it works. I am not familiar well enough with LSR's logic, to me it seemed like we tried really hard to *not* allow zeros here (but still end up with them).

[mkazantsev]

You were right, we can keep asserts and make a bailout at the point where we take extensions.

[samparker]

Cheers, LGTM.

lib/Transforms/Scalar/LoopStrengthReduce.cpp

3963

typo: while

lib/Transforms/Scalar/LoopStrengthReduce.cpp

bool LSRUse::InsertFormula(const Formula &F, const Loop &L) {
   SmallVector<const SCEV *, 4> Key = F.BaseRegs;
   if (F.ScaledReg) Key.push_back(F.ScaledReg);
   // Unstable sort by host order ok, because this is only used for uniquifying.
   llvm::sort(Key);
 
   if (!Uniquifier.insert(Key).second)
     return false;
 
-  // Using a register to hold the value of 0 is not profitable.
-  assert((!F.ScaledReg || !F.ScaledReg->isZero()) &&
-         "Zero allocated in a scaled register!");
-#ifndef NDEBUG
-  for (const SCEV *BaseReg : F.BaseRegs)
-    assert(!BaseReg->isZero() && "Zero allocated in a base register!");
-#endif
-
   // Add the formula to the list.
   Formulae.push_back(F);
 
   // Record registers now being used by this use.
   Regs.insert(F.BaseRegs.begin(), F.BaseRegs.end());
   if (F.ScaledReg)
     Regs.insert(F.ScaledReg);
 
void LSRInstance::GenerateTruncates(LSRUse &LU, unsigned LUIdx, Formula Base) {
   Type *DstTy = Base.getType();
   if (!DstTy) return;
   DstTy = SE.getEffectiveSCEVType(DstTy);
 
   for (Type *SrcTy : Types) {
     if (SrcTy != DstTy && TTI.isTruncateFree(SrcTy, DstTy)) {
       Formula F = Base;
 
-      if (F.ScaledReg) F.ScaledReg = SE.getAnyExtendExpr(F.ScaledReg, SrcTy);
-      for (const SCEV *&BaseReg : F.BaseRegs)
-        BaseReg = SE.getAnyExtendExpr(BaseReg, SrcTy);
+      if (F.ScaledReg) {
+        const SCEV *NewScaledReg = SE.getAnyExtendExpr(F.ScaledReg, SrcTy);
+        if (NewScaledReg->isZero())
+          LLVM_DEBUG(dbgs() << "WARNING: after ext, ScaledReg turned into "
+                               "constant zero. It might be non-profitable.");
+        F.ScaledReg = NewScaledReg;
+      }
+      for (const SCEV *&BaseReg : F.BaseRegs) {
+        const SCEV *NewBaseReg = SE.getAnyExtendExpr(BaseReg, SrcTy);
+        if (NewBaseReg->isZero())
+          LLVM_DEBUG(dbgs() << "WARNING: after ext, BaseReg turned into "
+                               "constant zero. It might be non-profitable.");
+        BaseReg = NewBaseReg;
+      }
 
       // TODO: This assumes we've done basic processing on all uses and
       // have an idea what the register usage is.
       if (!F.hasRegsUsedByUsesOtherThan(LUIdx, RegUses))
         continue;
 
       F.canonicalize(*L);
       (void)InsertFormula(LU, LUIdx, F);

test/Transforms/LoopStrengthReduce/X86/pr40514.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -loop-reduce -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 @pluto(i32 %arg) #0 {
+; CHECK-LABEL: @pluto(
+; CHECK-NEXT:  bb:
+; CHECK-NEXT:    br label [[BB10:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    store i64 [[LSR_IV_NEXT2:%.*]], i64 addrspace(1)* undef, align 8
+; CHECK-NEXT:    ret i32 [[LSR_IV_NEXT:%.*]]
+; CHECK:       bb10:
+; CHECK-NEXT:    [[LSR_IV1:%.*]] = phi i64 [ [[LSR_IV_NEXT2]], [[BB10]] ], [ 9, [[BB:%.*]] ]
+; CHECK-NEXT:    [[LSR_IV:%.*]] = phi i32 [ [[LSR_IV_NEXT]], [[BB10]] ], [ undef, [[BB]] ]
+; CHECK-NEXT:    [[LSR_IV_NEXT]] = add i32 [[LSR_IV]], 1
+; CHECK-NEXT:    [[LSR_IV_NEXT2]] = add nuw nsw i64 [[LSR_IV1]], 1
+; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB10]]
+;
+
+bb:
+  br label %bb10
+
+bb1:                                              ; preds = %bb10
+  %tmp = and i64 %tmp24, 4294967295
+  %tmp2 = shl i64 %tmp23, 33
+  %tmp3 = ashr exact i64 %tmp2, 32
+  %tmp4 = add i64 undef, %tmp
+  %tmp5 = add i64 %tmp4, %tmp3
+  %tmp6 = add i64 %tmp5, undef
+  %tmp7 = add i64 %tmp6, undef
+  %tmp8 = add i64 undef, %tmp7
+  store i64 %tmp8, i64 addrspace(1)* undef, align 8
+  %tmp9 = trunc i64 %tmp7 to i32
+  ret i32 %tmp9
+
+bb10:                                             ; preds = %bb10, %bb
+  %tmp11 = phi i64 [ 9, %bb ], [ %tmp24, %bb10 ]
+  %tmp12 = shl i64 undef, 1
+  %tmp13 = mul i64 %tmp12, %tmp12
+  %tmp14 = shl i64 %tmp13, 1
+  %tmp15 = mul i64 %tmp14, %tmp14
+  %tmp16 = shl i64 %tmp15, 1
+  %tmp17 = mul i64 %tmp16, %tmp16
+  %tmp18 = shl i64 %tmp17, 1
+  %tmp19 = mul i64 %tmp18, %tmp18
+  %tmp20 = shl i64 %tmp19, 1
+  %tmp21 = mul i64 %tmp20, %tmp20
+  %tmp22 = shl i64 %tmp21, 1
+  %tmp23 = mul i64 %tmp22, %tmp22
+  %tmp24 = add nuw nsw i64 %tmp11, 1
+  br i1 undef, label %bb1, label %bb10
+}
+
+
+attributes #0 = { "target-cpu"="broadwell" "target-features"="+sse2,+cx16,+sahf,-tbm,-avx512ifma,-sha,-gfni,-fma4,-vpclmulqdq,+prfchw,+bmi2,-cldemote,+fsgsbase,-ptwrite,-xsavec,+popcnt,+aes,-avx512bitalg,-movdiri,-xsaves,-avx512er,-avx512vnni,-avx512vpopcntdq,-pconfig,-clwb,-avx512f,-clzero,-pku,+mmx,-lwp,-rdpid,-xop,+rdseed,-waitpkg,-movdir64b,-sse4a,-avx512bw,-clflushopt,+xsave,-avx512vbmi2,+64bit,-avx512vl,+invpcid,-avx512cd,+avx,-vaes,+rtm,+fma,+bmi,+rdrnd,-mwaitx,+sse4.1,+sse4.2,+avx2,-wbnoinvd,+sse,+lzcnt,+pclmul,-prefetchwt1,+f16c,+ssse3,-sgx,-shstk,+cmov,-avx512vbmi,+movbe,+xsaveopt,-avx512dq,+adx,-avx512pf,+sse3" }