+
+bool SCEVExpander::isHighCostExpansionHelper(
+ const SCEV *S, Loop *L, SmallPtrSetImpl<const SCEV *> &Processed) {
+ if (!Processed.insert(S).second)
+ return false;
+
+ if (auto *UDivExpr = dyn_cast<SCEVUDivExpr>(S)) {
+ // If the divisor is a power of two and the SCEV type fits in a native
+ // integer, consider the divison cheap irrespective of whether it occurs in
+ // the user code since it can be lowered into a right shift.
+ if (auto *SC = dyn_cast<SCEVConstant>(UDivExpr->getRHS()))
+ if (SC->getValue()->getValue().isPowerOf2()) {
+ const DataLayout &DL =
+ L->getHeader()->getParent()->getParent()->getDataLayout();
+ unsigned Width = cast<IntegerType>(UDivExpr->getType())->getBitWidth();
+ return DL.isIllegalInteger(Width);
+ }
+
+ // UDivExpr is very likely a UDiv that ScalarEvolution's HowFarToZero or
+ // HowManyLessThans produced to compute a precise expression, rather than a
+ // UDiv from the user's code. If we can't find a UDiv in the code with some
+ // simple searching, assume the former consider UDivExpr expensive to
+ // compute.
+ BasicBlock *ExitingBB = L->getExitingBlock();
+ if (!ExitingBB)
+ return true;
+
+ BranchInst *ExitingBI = dyn_cast<BranchInst>(ExitingBB->getTerminator());
+ if (!ExitingBI || !ExitingBI->isConditional())
+ return true;
+
+ ICmpInst *OrigCond = dyn_cast<ICmpInst>(ExitingBI->getCondition());
+ if (!OrigCond)
+ return true;
+
+ const SCEV *RHS = SE.getSCEV(OrigCond->getOperand(1));
+ RHS = SE.getMinusSCEV(RHS, SE.getConstant(RHS->getType(), 1));
+ if (RHS != S) {
+ const SCEV *LHS = SE.getSCEV(OrigCond->getOperand(0));
+ LHS = SE.getMinusSCEV(LHS, SE.getConstant(LHS->getType(), 1));
+ if (LHS != S)
+ return true;
+ }
+ }
+
+ // Recurse past add expressions, which commonly occur in the
+ // BackedgeTakenCount. They may already exist in program code, and if not,
+ // they are not too expensive rematerialize.
+ if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(S)) {
+ for (SCEVAddExpr::op_iterator I = Add->op_begin(), E = Add->op_end();
+ I != E; ++I) {
+ if (isHighCostExpansionHelper(*I, L, Processed))
+ return true;
+ }
+ return false;
+ }
+
+ // HowManyLessThans uses a Max expression whenever the loop is not guarded by
+ // the exit condition.
+ if (isa<SCEVSMaxExpr>(S) || isa<SCEVUMaxExpr>(S))
+ return true;
+
+ // If we haven't recognized an expensive SCEV pattern, assume it's an
+ // expression produced by program code.
+ return false;
+}
+
+namespace {
+// Search for a SCEV subexpression that is not safe to expand. Any expression
+// that may expand to a !isSafeToSpeculativelyExecute value is unsafe, namely
+// UDiv expressions. We don't know if the UDiv is derived from an IR divide
+// instruction, but the important thing is that we prove the denominator is
+// nonzero before expansion.
+//
+// IVUsers already checks that IV-derived expressions are safe. So this check is
+// only needed when the expression includes some subexpression that is not IV
+// derived.
+//
+// Currently, we only allow division by a nonzero constant here. If this is
+// inadequate, we could easily allow division by SCEVUnknown by using
+// ValueTracking to check isKnownNonZero().
+//
+// We cannot generally expand recurrences unless the step dominates the loop
+// header. The expander handles the special case of affine recurrences by
+// scaling the recurrence outside the loop, but this technique isn't generally
+// applicable. Expanding a nested recurrence outside a loop requires computing
+// binomial coefficients. This could be done, but the recurrence has to be in a
+// perfectly reduced form, which can't be guaranteed.
+struct SCEVFindUnsafe {
+ ScalarEvolution &SE;
+ bool IsUnsafe;
+
+ SCEVFindUnsafe(ScalarEvolution &se): SE(se), IsUnsafe(false) {}
+
+ bool follow(const SCEV *S) {
+ if (const SCEVUDivExpr *D = dyn_cast<SCEVUDivExpr>(S)) {
+ const SCEVConstant *SC = dyn_cast<SCEVConstant>(D->getRHS());
+ if (!SC || SC->getValue()->isZero()) {
+ IsUnsafe = true;
+ return false;
+ }
+ }
+ if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) {
+ const SCEV *Step = AR->getStepRecurrence(SE);
+ if (!AR->isAffine() && !SE.dominates(Step, AR->getLoop()->getHeader())) {
+ IsUnsafe = true;
+ return false;
+ }
+ }
+ return true;
+ }
+ bool isDone() const { return IsUnsafe; }
+};
+}
+
+namespace llvm {
+bool isSafeToExpand(const SCEV *S, ScalarEvolution &SE) {
+ SCEVFindUnsafe Search(SE);
+ visitAll(S, Search);
+ return !Search.IsUnsafe;
+}
+}