+
+/// 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;
+
+ // If this is a load or other access, pass the type of the access in.
+ const Type *AccessTy = Type::VoidTy;
+ if (StoreInst *SI = dyn_cast<StoreInst>(UsersToProcess[i].Inst))
+ AccessTy = SI->getOperand(0)->getType();
+ else if (LoadInst *LI = dyn_cast<LoadInst>(UsersToProcess[i].Inst))
+ AccessTy = LI->getType();
+
+ if (!TLI->isLegalAddressScaleAndImm(Scale, Imm, AccessTy))
+ return false;
+ }
+ return true;
+}
+
+/// CheckForIVReuse - Returns the multiple if the stride is the multiple
+/// of a previous stride and it is a legal value for the target addressing
+/// mode scale component. This allows the users of this stride to be rewritten
+/// as prev iv * factor. It returns 0 if no reuse is possible.
+unsigned LoopStrengthReduce::CheckForIVReuse(const SCEVHandle &Stride,
+ IVExpr &IV, const Type *Ty,
+ const std::vector<BasedUser>& UsersToProcess) {
+ if (!TLI) return 0;
+
+ if (SCEVConstant *SC = dyn_cast<SCEVConstant>(Stride)) {
+ int64_t SInt = SC->getValue()->getSExtValue();
+ if (SInt == 1) return 0;
+
+ for (std::map<SCEVHandle, IVsOfOneStride>::iterator SI= IVsByStride.begin(),
+ SE = IVsByStride.end(); SI != SE; ++SI) {
+ int64_t SSInt = cast<SCEVConstant>(SI->first)->getValue()->getSExtValue();
+ if (SInt != -SSInt &&
+ (unsigned(abs(SInt)) < SSInt || (SInt % SSInt) != 0))
+ continue;
+ int64_t Scale = SInt / SSInt;
+ // Check that this stride is valid for all the types used for loads and
+ // stores; if it can be used for some and not others, we might as well use
+ // the original stride everywhere, since we have to create the IV for it
+ // anyway.
+ if (ValidStride(Scale, UsersToProcess))
+ for (std::vector<IVExpr>::iterator II = SI->second.IVs.begin(),
+ IE = SI->second.IVs.end(); II != IE; ++II)
+ // FIXME: Only handle base == 0 for now.
+ // Only reuse previous IV if it would not require a type conversion.
+ if (isZero(II->Base) && II->Base->getType() == Ty) {
+ IV = *II;
+ return Scale;
+ }
+ }
+ }
+ return 0;
+}
+
+/// PartitionByIsUseOfPostIncrementedValue - Simple boolean predicate that
+/// returns true if Val's isUseOfPostIncrementedValue is true.
+static bool PartitionByIsUseOfPostIncrementedValue(const BasedUser &Val) {
+ return Val.isUseOfPostIncrementedValue;
+}
+