+
+ // Otherwise, no immediates to move.
+}
+
+
+/// SeparateSubExprs - Decompose Expr into all of the subexpressions that are
+/// added together. This is used to reassociate common addition subexprs
+/// together for maximal sharing when rewriting bases.
+static void SeparateSubExprs(std::vector<SCEVHandle> &SubExprs,
+ SCEVHandle Expr) {
+ if (SCEVAddExpr *AE = dyn_cast<SCEVAddExpr>(Expr)) {
+ for (unsigned j = 0, e = AE->getNumOperands(); j != e; ++j)
+ SeparateSubExprs(SubExprs, AE->getOperand(j));
+ } else if (SCEVAddRecExpr *SARE = dyn_cast<SCEVAddRecExpr>(Expr)) {
+ SCEVHandle Zero = SCEVUnknown::getIntegerSCEV(0, Expr->getType());
+ if (SARE->getOperand(0) == Zero) {
+ SubExprs.push_back(Expr);
+ } else {
+ // Compute the addrec with zero as its base.
+ std::vector<SCEVHandle> Ops(SARE->op_begin(), SARE->op_end());
+ Ops[0] = Zero; // Start with zero base.
+ SubExprs.push_back(SCEVAddRecExpr::get(Ops, SARE->getLoop()));
+
+
+ SeparateSubExprs(SubExprs, SARE->getOperand(0));
+ }
+ } else if (!isa<SCEVConstant>(Expr) ||
+ !cast<SCEVConstant>(Expr)->getValue()->isZero()) {
+ // Do not add zero.
+ SubExprs.push_back(Expr);
+ }
+}
+
+
+/// RemoveCommonExpressionsFromUseBases - Look through all of the uses in Bases,
+/// removing any common subexpressions from it. Anything truly common is
+/// removed, accumulated, and returned. This looks for things like (a+b+c) and
+/// (a+c+d) -> (a+c). The common expression is *removed* from the Bases.
+static SCEVHandle
+RemoveCommonExpressionsFromUseBases(std::vector<BasedUser> &Uses) {
+ unsigned NumUses = Uses.size();
+
+ // Only one use? Use its base, regardless of what it is!
+ SCEVHandle Zero = SCEVUnknown::getIntegerSCEV(0, Uses[0].Base->getType());
+ SCEVHandle Result = Zero;
+ if (NumUses == 1) {
+ std::swap(Result, Uses[0].Base);
+ return Result;
+ }
+
+ // To find common subexpressions, count how many of Uses use each expression.
+ // If any subexpressions are used Uses.size() times, they are common.
+ std::map<SCEVHandle, unsigned> SubExpressionUseCounts;
+
+ // UniqueSubExprs - Keep track of all of the subexpressions we see in the
+ // order we see them.
+ std::vector<SCEVHandle> UniqueSubExprs;
+
+ std::vector<SCEVHandle> SubExprs;
+ for (unsigned i = 0; i != NumUses; ++i) {
+ // If the base is zero (which is common), return zero now, there are no
+ // CSEs we can find.
+ if (Uses[i].Base == Zero) return Zero;
+
+ // Split the expression into subexprs.
+ SeparateSubExprs(SubExprs, Uses[i].Base);
+ // Add one to SubExpressionUseCounts for each subexpr present.
+ for (unsigned j = 0, e = SubExprs.size(); j != e; ++j)
+ if (++SubExpressionUseCounts[SubExprs[j]] == 1)
+ UniqueSubExprs.push_back(SubExprs[j]);
+ SubExprs.clear();
+ }
+
+ // Now that we know how many times each is used, build Result. Iterate over
+ // UniqueSubexprs so that we have a stable ordering.
+ for (unsigned i = 0, e = UniqueSubExprs.size(); i != e; ++i) {
+ std::map<SCEVHandle, unsigned>::iterator I =
+ SubExpressionUseCounts.find(UniqueSubExprs[i]);
+ assert(I != SubExpressionUseCounts.end() && "Entry not found?");
+ if (I->second == NumUses) { // Found CSE!
+ Result = SCEVAddExpr::get(Result, I->first);
+ } else {
+ // Remove non-cse's from SubExpressionUseCounts.
+ SubExpressionUseCounts.erase(I);
+ }
+ }
+
+ // If we found no CSE's, return now.
+ if (Result == Zero) return Result;
+
+ // Otherwise, remove all of the CSE's we found from each of the base values.
+ for (unsigned i = 0; i != NumUses; ++i) {
+ // Split the expression into subexprs.
+ SeparateSubExprs(SubExprs, Uses[i].Base);
+
+ // Remove any common subexpressions.
+ for (unsigned j = 0, e = SubExprs.size(); j != e; ++j)
+ if (SubExpressionUseCounts.count(SubExprs[j])) {
+ SubExprs.erase(SubExprs.begin()+j);
+ --j; --e;
+ }
+
+ // Finally, the non-shared expressions together.
+ if (SubExprs.empty())
+ Uses[i].Base = Zero;
+ else
+ Uses[i].Base = SCEVAddExpr::get(SubExprs);
+ SubExprs.clear();
+ }
+
+ return Result;
+}
+
+/// isZero - returns true if the scalar evolution expression is zero.
+///
+static bool isZero(SCEVHandle &V) {
+ if (SCEVConstant *SC = dyn_cast<SCEVConstant>(V))
+ return SC->getValue()->isZero();
+ return false;
+}
+
+/// ValidStride - Check whether the given Scale is valid for all loads and
+/// stores in UsersToProcess. Pulled into a function to avoid disturbing the
+/// sensibilities of those who dislike goto's.
+///
+bool LoopStrengthReduce::ValidStride(int64_t Scale,
+ const std::vector<BasedUser>& UsersToProcess) {
+ int64_t Imm;
+ for (unsigned i=0, e = UsersToProcess.size(); i!=e; ++i) {
+ if (SCEVConstant *SC = dyn_cast<SCEVConstant>(UsersToProcess[i].Imm))
+ Imm = SC->getValue()->getSExtValue();
+ else
+ Imm = 0;