[SCEV] Add transform zext((A * B * ...)<nuw>) --> (zext(A) * zext(B) * ...)<nuw>.

[sanjoy]

lgtm

[mzolotukhin]

Hi Justin,

This (or the previous) commit caused a ~1.4% compile time slowdown on CTMark/mafft/pairlocalalign. Any ideas on how we can avoid it?
I don’t have more details at the moment, but I’d be happy to dig deeper if that helps.

Thanks,
Michael

[sanjoy]

In D48041#1129233, @mzolotukhin wrote:

Hi Justin,

This (or the previous) commit caused a ~1.4% compile time slowdown on CTMark/mafft/pairlocalalign. Any ideas on how we can avoid it?

Is there some way to figure out what exactly got slower (it could be SCEV or some user of SCEV)?

[mzolotukhin]

Is there some way to figure out what exactly got slower (it could be SCEV or some user of SCEV)?

Not really at the moment.

I'm trying to locally reproduce it, and maybe I'll get more insight into it later. So far it's been reported by several internal bots testing different opt-levels, so it doesn't look to be just a noise.

Michael

llvm/lib/Analysis/ScalarEvolution.cpp

if (SA->hasNoUnsignedWrap()) {
       // commute the zero extension with the addition operation.
       SmallVector<const SCEV *, 4> Ops;
       for (const auto *Op : SA->operands())
         Ops.push_back(getZeroExtendExpr(Op, Ty, Depth + 1));
       return getAddExpr(Ops, SCEV::FlagNUW, Depth + 1);
     }
   }
 
+  if (auto *SA = dyn_cast<SCEVMulExpr>(Op)) {
+    // zext((A * B * ...)<nuw>) --> (zext(A) * zext(B) * ...)<nuw>
+    if (SA->hasNoUnsignedWrap()) {
+      // If the multiply does not unsign overflow then we can, by definition,
+      // commute the zero extension with the multiply operation.
+      SmallVector<const SCEV *, 4> Ops;
+      for (const auto *Op : SA->operands())
+        Ops.push_back(getZeroExtendExpr(Op, Ty, Depth + 1));
+      return getMulExpr(Ops, SCEV::FlagNUW, Depth + 1);
+    }
+  }
+
   // The cast wasn't folded; create an explicit cast node.
   // Recompute the insert position, as it may have been invalidated.
   if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
   SCEV *S = new (SCEVAllocator) SCEVZeroExtendExpr(ID.Intern(SCEVAllocator),
                                                    Op, Ty);
   UniqueSCEVs.InsertNode(S, IP);
   addToLoopUseLists(S);
   return S;

llvm/test/Analysis/ScalarEvolution/zext-mul.ll

+; RUN: opt < %s -analyze -scalar-evolution | FileCheck %s
+
+; Check that we convert
+;   zext((a * b)<nuw>)
+; to
+;   (zext(a) * zext(b))<nuw>
+
+declare i32 @get_int();
+
+; Transform doesn't apply here, because %a lacks range metadata.
+; CHECK-LABEL: @no_range
+define void @no_range() {
+  %a = call i32 @get_int()
+  %b = mul i32 %a, 4
+  %c = zext i32 %b to i64
+  ; CHECK: %c
+  ; CHECK-NEXT: --> (zext i32 (4 * %a) to i64)
+  ret void
+}
+
+; CHECK-LABEL: @range
+define void @range() {
+  %a = call i32 @get_int(), !range !0
+  %b = mul i32 %a, 4
+  %c = zext i32 %b to i64
+  ; CHECK: %c
+  ; CHECK-NEXT: --> (4 * (zext i32 %a to i64))<nuw>
+  ret void
+}
+
+!0 = !{i32 0, i32 100}