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.

2272–2273

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* Expr) {
+  if (isa<SCEVConstant>(Expr))
+    return true;
+
+  const SCEVNAryExpr * Target = dyn_cast<const SCEVNAryExpr>(Expr);
+  if (!Target)
+    return false;
+
+  for (auto Operand = Target->op_begin(),
+         E = Target->op_end(); Operand != E; ++Operand)
+    if ((isa<SCEVAddExpr>(*Operand)) || (isa<SCEVMulExpr>(*Operand))) {
+      if (ContainsConstantSomewhere(*Operand))
+        return true;
+    } else if (isa<SCEVConstant>(*Operand)) {
+      return true;
+    }
+
+  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
+          //  then 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);