whitespace

[oota-llvm.git] / lib / Analysis / ScalarEvolution.cpp

diff --git a/lib/Analysis/ScalarEvolution.cpp b/lib/Analysis/ScalarEvolution.cpp
index 4bb69ddb276a17f95c1400d7d832ebdf6472a9ff..b1662a026086e0d1bd9471fbadc22fe2a4a742af 100644 (file)
--- a/lib/Analysis/ScalarEvolution.cpp
+++ b/lib/Analysis/ScalarEvolution.cpp
@@ -1974,7 +1974,8 @@ const SCEV *ScalarEvolution::getMulExpr(SmallVectorImpl<const SCEV *> &Ops,
     // multiplied together.  If so, we can fold them.
     for (unsigned OtherIdx = Idx+1;
          OtherIdx < Ops.size() && isa<SCEVAddRecExpr>(Ops[OtherIdx]);
-         ++OtherIdx)
+         ++OtherIdx) {
+      bool Retry = false;
       if (AddRecLoop == cast<SCEVAddRecExpr>(Ops[OtherIdx])->getLoop()) {
         // {A,+,B}<L> * {C,+,D}<L>  -->  {A*C,+,A*D + B*C + B*D,+,2*B*D}<L>
         //
@@ -1985,7 +1986,7 @@ const SCEV *ScalarEvolution::getMulExpr(SmallVectorImpl<const SCEV *> &Ops,
         // Rearranging, X = x, Y = y+z, Z = 2z.
         //
         // x = A*C, y = (A*D + B*C), z = B*D.
-        // Therefore X = A*C, Y = (A*D + B*C) - B*D and Z = 2*B*D.
+        // Therefore X = A*C, Y = A*D + B*C + B*D and Z = 2*B*D.
         for (; OtherIdx != Ops.size() && isa<SCEVAddRecExpr>(Ops[OtherIdx]);
              ++OtherIdx)
           if (const SCEVAddRecExpr *OtherAddRec =
@@ -1998,24 +1999,32 @@ const SCEV *ScalarEvolution::getMulExpr(SmallVectorImpl<const SCEV *> &Ops,
               const SCEV *NewStart = getMulExpr(A, C);
               const SCEV *BD = getMulExpr(B, D);
               const SCEV *NewStep = getAddExpr(getMulExpr(A, D),
-                                               getMulExpr(B, C),
-                                               getNegativeSCEV(BD));
+                                               getMulExpr(B, C), BD);
               const SCEV *NewSecondOrderStep =
                   getMulExpr(BD, getConstant(BD->getType(), 2));
 
-              SmallVector<const SCEV *, 3> AddRecOps;
-              AddRecOps.push_back(NewStart);
-              AddRecOps.push_back(NewStep);
-              AddRecOps.push_back(NewSecondOrderStep);
-              const SCEV *NewAddRec = getAddRecExpr(AddRecOps,
-                                                    AddRec->getLoop(),
-                                                    SCEV::FlagAnyWrap);
-              if (Ops.size() == 2) return NewAddRec;
-              Ops[Idx] = AddRec = cast<SCEVAddRecExpr>(NewAddRec);
-              Ops.erase(Ops.begin() + OtherIdx); --OtherIdx;
+              // This can happen when AddRec or OtherAddRec have >3 operands.
+              // TODO: support these add-recs.
+              if (isLoopInvariant(NewStart, AddRecLoop) &&
+                  isLoopInvariant(NewStep, AddRecLoop) &&
+                  isLoopInvariant(NewSecondOrderStep, AddRecLoop)) {
+                SmallVector<const SCEV *, 3> AddRecOps;
+                AddRecOps.push_back(NewStart);
+                AddRecOps.push_back(NewStep);
+                AddRecOps.push_back(NewSecondOrderStep);
+                const SCEV *NewAddRec = getAddRecExpr(AddRecOps,
+                                                      AddRec->getLoop(),
+                                                      SCEV::FlagAnyWrap);
+                if (Ops.size() == 2) return NewAddRec;
+                Ops[Idx] = AddRec = cast<SCEVAddRecExpr>(NewAddRec);
+                Ops.erase(Ops.begin() + OtherIdx); --OtherIdx;
+                Retry = true;
+              }
             }
-        return getMulExpr(Ops);
+        if (Retry)
+          return getMulExpr(Ops);
       }
+    }
 
     // Otherwise couldn't fold anything into this recurrence.  Move onto the
     // next one.
@@ -3537,7 +3546,13 @@ const SCEV *ScalarEvolution::createSCEV(Value *V) {
         AddOps.push_back(Op1);
     }
     AddOps.push_back(getSCEV(U->getOperand(0)));
-    return getAddExpr(AddOps);
+    SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap;
+    OverflowingBinaryOperator *OBO = cast<OverflowingBinaryOperator>(V);
+    if (OBO->hasNoSignedWrap())
+      setFlags(Flags, SCEV::FlagNSW);
+    if (OBO->hasNoUnsignedWrap())
+      setFlags(Flags, SCEV::FlagNUW);
+    return getAddExpr(AddOps, Flags);
   }
   case Instruction::Mul: {
     // See the Add code above.