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 ↗

(On Diff #16992)

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);