Add more opportunities for constant folding in ScalarEvolution.

[timmurray]

Summary

More constant multiplies will be folded. This prevents SCEVs from
being generated with mismatches such as

{((4 * ((-1 * %x1) + %X.unr)) + %1),+,32}<%Loop>

vs

{((4 * %X.unr) + (-4 * %x1) + %1),+,32}

[timmurray]

fix change description

[majnemer]

lib/Analysis/ScalarEvolution.cpp

2212

Please give this function a name that starts with a lower case letter. Also, pointers bind to the variable name.

2216

It's more natural in LLVM to write:

const auto *Target = dyn_cast<SCEVNAryExpr>(Expr);

2220–2221

This would probably read easier as:

for (const SCEV *Operand : Target->operands())

2220–2227

I think this would look a little more natural:

for (const SCEV *Operand : Target->operands()) {
  if (isa<SCEVConstant>(*Operand))
    return true;
  if (isa<SCEVAddExpr>(*Operand) || isa<SCEVMulExpr>(*Operand))
    if (containsConstantSomewhere(*Operand))
      return true;
}

2222

These extra parens look strange.

[nlewycky]

lib/Analysis/ScalarEvolution.cpp

2210

I forget; are expr's guaranteed to be "GroupByComplexity"'d? If so, ContainsConstantSomewhere can be optimized greatly. If there's any constant, it's guaranteed to be in a group at the end. You only recurse on Add and Mul, so if you've gone past those (to umax, smax, unknown or could-not-compute, you can stop).

Also, please iterate with a worklist instead of recursing. Create a SmallVector<SCEV*>, push your starting element into it, use pop_back_val to grab the latest one off the top of the list. If you're worried about revisiting the same thing multiple times, add a SmallSet<SCEV*> and test whether inserting the new element succeeds -- if it doesn't, it's already in the set.

2269–2270

Capitalize 'If', remove extra space before 'then'.

[timmurray]

Switch to worklist-based constant search instead of recursion. Clean up style.

[nlewycky]

lib/Analysis/ScalarEvolution.cpp

2212

"SCEV* StartExpr" should be "SCEV *StartExpr".

2221

This cast is guaranteed to succeed because of the if isa's above. Use cast<> instead of dyn_cast<>.

[timmurray]

Update style and cast.

[nlewycky]

LGTM

[nlewycky]

Er, wait. Needs a test.

[timmurray]

Add test for additional fold opportunity.

[nlewycky]

LGTM with comment.

test/Analysis/ScalarEvolution/scev-mul-expr-fold.ll

53–62

I think you can safely drop all the metadata from this test?

[Eugene.Zelenko]

Looks like patch was not committed.

[nlewycky]

It looks like I LGTM'd it with comments that aren't resolved. If you don't have commit access, please upload a version which I can commit for you with no changes. Usually I LGTM+comments with the expectation that you can resolve the comments and commit without going through another round of review.

lib/Analysis/ScalarEvolution.cpp

static uint64_t Choose(uint64_t n, uint64_t k, bool &Overflow) {
   uint64_t r = 1;
   for (uint64_t i = 1; i <= k; ++i) {
     r = umul_ov(r, n-(i-1), Overflow);
     r /= i;
   }
   return r;
 }
 
+/// Determine if any of the operands in this SCEV are a constant or if
+/// any of the add or multiply expressions in this SCEV contain a constant.
+static bool containsConstantSomewhere(const SCEV *StartExpr) {
+  SmallVector<const SCEV *, 4> Ops;
+  Ops.push_back(StartExpr);
+  while (!Ops.empty()) {
+    const SCEV *CurrentExpr = Ops.pop_back_val();
+    if (isa<SCEVConstant>(*CurrentExpr))
+      return true;
+
+    if (isa<SCEVAddExpr>(*CurrentExpr) || isa<SCEVMulExpr>(*CurrentExpr)) {
+      const auto *CurrentNAry = cast<SCEVNAryExpr>(CurrentExpr);
+      for (const SCEV *Operand : CurrentNAry->operands())
+        Ops.push_back(Operand);
+    }
+  }
+  return false;
+}
+
 /// getMulExpr - Get a canonical multiply expression, or something simpler if
 /// possible.
 const SCEV *ScalarEvolution::getMulExpr(SmallVectorImpl<const SCEV *> &Ops,
                                         SCEV::NoWrapFlags Flags) {
   assert(Flags == maskFlags(Flags, SCEV::FlagNUW | SCEV::FlagNSW) &&
          "only nuw or nsw allowed");
   assert(!Ops.empty() && "Cannot get empty mul!");
   if (Ops.size() == 1) return Ops[0];
#endif
   GroupByComplexity(Ops, LI);
 
   // If there are any constants, fold them together.
   unsigned Idx = 0;
   if (const SCEVConstant *LHSC = dyn_cast<SCEVConstant>(Ops[0])) {
 
     // C1*(C2+V) -> C1*C2 + C1*V
     if (Ops.size() == 2)
         if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(Ops[1]))
-        if (Add->getNumOperands() == 2 &&
-            isa<SCEVConstant>(Add->getOperand(0)))
+          // If any of Add's ops are Adds or Muls with a constant,
+          // apply this transformation as well.
+          if (Add->getNumOperands() == 2)
+            if (containsConstantSomewhere(Add))
               return getAddExpr(getMulExpr(LHSC, Add->getOperand(0)),
                                 getMulExpr(LHSC, Add->getOperand(1)));
 
     ++Idx;
     while (const SCEVConstant *RHSC = dyn_cast<SCEVConstant>(Ops[Idx])) {
       // We found two constants, fold them together!
       ConstantInt *Fold = ConstantInt::get(getContext(),
                                            LHSC->getValue()->getValue() *
                                            RHSC->getValue()->getValue());
       Ops[0] = getConstant(Fold);

test/Analysis/ScalarEvolution/scev-mul-expr-fold.ll

+; RUN: opt -analyze -scalar-evolution < %s | FileCheck %s
+target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-n32-S64"
+
+%ParamStruct = type { i8**, i32*, i8*, i32, i32, i32, i8*, i32, i32, i32, i32 }
+
+; Function Attrs: nounwind
+define void @root.expand(%ParamStruct* nocapture readonly %p, i32 %x1, i32 %x2, i32 %outstep) #0 {
+Begin:
+  %0 = getelementptr inbounds %ParamStruct* %p, i32 0, i32 2
+  %1 = bitcast i8** %0 to float**
+  %2 = load float** %1, align 4, !tbaa !8, !alias.scope !12
+  %3 = bitcast %ParamStruct* %p to float***
+  %inputs_base2 = load float*** %3, align 4
+  %input_base1 = load float** %inputs_base2, align 4, !tbaa !8, !alias.scope !12
+  %4 = icmp ugt i32 %x2, %x1
+  br i1 %4, label %Loop.preheader, label %Exit
+
+Loop.preheader:                                   ; preds = %Begin
+  %5 = sub i32 %x2, %x1
+  %xtraiter = and i32 %5, 7
+  %lcmp.mod = icmp ne i32 %xtraiter, 0
+  %lcmp.overflow = icmp eq i32 %x2, %x1
+  %lcmp.or = or i1 %lcmp.overflow, %lcmp.mod
+  br i1 %lcmp.or, label %Loop.prol, label %Loop.preheader.split
+
+Loop.prol:                                        ; preds = %Loop.prol, %Loop.preheader
+  %X.prol = phi i32 [ %7, %Loop.prol ], [ %x1, %Loop.preheader ]
+  %prol.iter = phi i32 [ %prol.iter.sub, %Loop.prol ], [ %xtraiter, %Loop.preheader ]
+  %6 = sub i32 %X.prol, %x1
+  %7 = add nuw i32 %X.prol, 1
+  %prol.iter.sub = add i32 %prol.iter, -1
+  %prol.iter.cmp = icmp eq i32 %prol.iter.sub, 0
+  br i1 %prol.iter.cmp, label %Loop.preheader.split, label %Loop.prol, !llvm.loop !16
+
+Loop.preheader.split:                             ; preds = %Loop.prol, %Loop.preheader
+  %X.unr = phi i32 [ %x1, %Loop.preheader ], [ %7, %Loop.prol ]
+  %8 = icmp ult i32 %5, 8
+  br i1 %8, label %Exit, label %Loop
+
+Exit:                                             ; preds = %Loop, %Loop.preheader.split, %Begin
+  ret void
+
+Loop:                                             ; preds = %Loop, %Loop.preheader.split
+  %X = phi i32 [ %X.unr, %Loop.preheader.split ]
+  %9 = sub i32 %X, %x1
+  %testSCEV = getelementptr float* %2, i32 %9
+; CHECK: ((4 * %X.unr) + (-4 * %x1) + %2)
+  br label %Exit
+}
+
+attributes #0 = { nounwind }
+
+!8 = metadata !{metadata !9, metadata !9, i64 0}
+!9 = metadata !{metadata !"pointer", metadata !10, i64 0}
+!10 = metadata !{metadata !"", metadata !11}
+!11 = metadata !{metadata !""}
+!12 = metadata !{metadata !12, metadata !13, metadata !"argument_scope"}
+!13 = metadata !{metadata !13}
+!14 = metadata !{metadata !15, metadata !15, i64 0}
+!15 = metadata !{metadata !"", metadata !10, i64 0}
+!16 = metadata !{metadata !16, metadata !17}
+!17 = metadata !{metadata !"llvm.loop.unroll.disable"}