/// Assume, K > 0.
static const SCEV *BinomialCoefficient(const SCEV *It, unsigned K,
ScalarEvolution &SE,
- Type* ResultTy) {
+ Type *ResultTy) {
// Handle the simplest case efficiently.
if (K == 1)
return SE.getTruncateOrZeroExtend(It, ResultTy);
// If all of the other operands were loop invariant, we are done.
if (Ops.size() == 1) return NewRec;
- // Otherwise, add the folded AddRec by the non-liv parts.
+ // Otherwise, add the folded AddRec by the non-invariant parts.
for (unsigned i = 0;; ++i)
if (Ops[i] == AddRec) {
Ops[i] = NewRec;
// If all of the other operands were loop invariant, we are done.
if (Ops.size() == 1) return NewRec;
- // Otherwise, multiply the folded AddRec by the non-liv parts.
+ // Otherwise, multiply the folded AddRec by the non-invariant parts.
for (unsigned i = 0;; ++i)
if (Ops[i] == AddRec) {
Ops[i] = NewRec;
// 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()) {
- // F * G, where F = {A,+,B}<L> and G = {C,+,D}<L> -->
- // {A*C,+,F*D + G*B + B*D}<L>
+ // {A,+,B}<L> * {C,+,D}<L> --> {A*C,+,A*D + B*C + B*D,+,2*B*D}<L>
+ //
+ // {A,+,B} * {C,+,D} = A+It*B * C+It*D = A*C + (A*D + B*C)*It + B*D*It^2
+ // Given an equation of the form x + y*It + z*It^2 (above), we want to
+ // express it in terms of {X,+,Y,+,Z}.
+ // {X,+,Y,+,Z} = X + Y*It + Z*(It^2 - It)/2.
+ // 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.
for (; OtherIdx != Ops.size() && isa<SCEVAddRecExpr>(Ops[OtherIdx]);
++OtherIdx)
if (const SCEVAddRecExpr *OtherAddRec =
dyn_cast<SCEVAddRecExpr>(Ops[OtherIdx]))
if (OtherAddRec->getLoop() == AddRecLoop) {
- const SCEVAddRecExpr *F = AddRec, *G = OtherAddRec;
- const SCEV *NewStart = getMulExpr(F->getStart(), G->getStart());
- const SCEV *B = F->getStepRecurrence(*this);
- const SCEV *D = G->getStepRecurrence(*this);
- const SCEV *NewStep = getAddExpr(getMulExpr(F, D),
- getMulExpr(G, B),
- getMulExpr(B, D));
- const SCEV *NewAddRec = getAddRecExpr(NewStart, NewStep,
- F->getLoop(),
- SCEV::FlagAnyWrap);
- if (Ops.size() == 2) return NewAddRec;
- Ops[Idx] = AddRec = cast<SCEVAddRecExpr>(NewAddRec);
- Ops.erase(Ops.begin() + OtherIdx); --OtherIdx;
+ const SCEV *A = AddRec->getStart();
+ const SCEV *B = AddRec->getStepRecurrence(*this);
+ const SCEV *C = OtherAddRec->getStart();
+ const SCEV *D = OtherAddRec->getStepRecurrence(*this);
+ const SCEV *NewStart = getMulExpr(A, C);
+ const SCEV *BD = getMulExpr(B, D);
+ const SCEV *NewStep = getAddExpr(getMulExpr(A, D),
+ getMulExpr(B, C), BD);
+ const SCEV *NewSecondOrderStep =
+ getMulExpr(BD, getConstant(BD->getType(), 2));
+
+ // 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.
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.