+ SCEVHandle Start = SARE->getStart();
+ MoveImmediateValues(TLI, User, Start, Imm, isAddress, L);
+
+ if (Start != SARE->getStart()) {
+ std::vector<SCEVHandle> Ops(SARE->op_begin(), SARE->op_end());
+ Ops[0] = Start;
+ Val = SCEVAddRecExpr::get(Ops, SARE->getLoop());
+ }
+ return;
+ } else if (SCEVMulExpr *SME = dyn_cast<SCEVMulExpr>(Val)) {
+ // Transform "8 * (4 + v)" -> "32 + 8*V" if "32" fits in the immed field.
+ if (isAddress && isTargetConstant(SME->getOperand(0), UseTy, TLI) &&
+ SME->getNumOperands() == 2 && SME->isLoopInvariant(L)) {
+
+ SCEVHandle SubImm = SCEVUnknown::getIntegerSCEV(0, Val->getType());
+ SCEVHandle NewOp = SME->getOperand(1);
+ MoveImmediateValues(TLI, User, NewOp, SubImm, isAddress, L);
+
+ // If we extracted something out of the subexpressions, see if we can
+ // simplify this!
+ if (NewOp != SME->getOperand(1)) {
+ // Scale SubImm up by "8". If the result is a target constant, we are
+ // good.
+ SubImm = SCEVMulExpr::get(SubImm, SME->getOperand(0));
+ if (isTargetConstant(SubImm, UseTy, TLI)) {
+ // Accumulate the immediate.
+ Imm = SCEVAddExpr::get(Imm, SubImm);
+
+ // Update what is left of 'Val'.
+ Val = SCEVMulExpr::get(SME->getOperand(0), NewOp);
+ return;
+ }
+ }
+ }
+ }
+
+ // Loop-variant expressions must stay in the immediate field of the
+ // expression.
+ if ((isAddress && isTargetConstant(Val, UseTy, TLI)) ||
+ !Val->isLoopInvariant(L)) {
+ Imm = SCEVAddExpr::get(Imm, Val);
+ Val = SCEVUnknown::getIntegerSCEV(0, Val->getType());
+ return;
+ }
+
+ // 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();