[SCEV] Add SCEVCompareExpr node

[reames]

Summary

A SCEVCompareExpr node represents the boolean result of performing a comparison as specified by it's predicate and operands. This is essentially an extension of the IR instruction icmp into SCEV.

We've talked about this off and on for a while, but I think it's time to actually do this.

I want to highlight that adding the node does not mean we have to extend IR pattern matching. At the moment, I'm planning on using this to simplify and generalize PredicatedScalarEvolution and the loop versioning checks used by various transforms. The decision as to whether we want these in generic SCEV expressions can (and should be) explicitly deferred here.

[reames]

Fix a bug and add missing piece from expander which showed up when I built on top of this.

[nikic]

I want to highlight that adding the node does not mean we have to extend IR pattern matching. At the moment, I'm planning on using this to simplify and generalize PredicatedScalarEvolution and the loop versioning checks used by various transforms. The decision as to whether we want these in generic SCEV expressions can (and should be) explicitly deferred here.

Could you provide a bit more information on how this is going to be used? It's not completely clear to me whether/why this should be part of the SCEV hierarchy, rather than something that uses SCEV nodes but is not one itself.

Having it as a SCEV makes sense if you want to make it a part of a larger expression, but it's not immediately obvious how that will look in practice (I guess you could use umin/umax as an awkward way to and/or conditions).

[reames]

In D119558#3315198, @nikic wrote:

I want to highlight that adding the node does not mean we have to extend IR pattern matching. At the moment, I'm planning on using this to simplify and generalize PredicatedScalarEvolution and the loop versioning checks used by various transforms. The decision as to whether we want these in generic SCEV expressions can (and should be) explicitly deferred here.

Could you provide a bit more information on how this is going to be used? It's not completely clear to me whether/why this should be part of the SCEV hierarchy, rather than something that uses SCEV nodes but is not one itself.

So, my current thinking is that SCEVPredicate is just going to end up as a wrapper around a SCEV*. Currently, we have three predicates types - union, compare, and nowrap. My immediate plan is to replace the compare with a wrapped SCEV - I should have a patch shortly. I'd then replace the nowrap variant, and once that's done, do the same for the wrapping union.

I'd originally thought the separate hierarchy make sense as well, but when I started look into it I kept finding myself needing to duplicate logic we already have in SCEV today. (implication, negation, inference, etc..) I really do think it makes sense for predicates to just be SCEV expressions.

Having it as a SCEV makes sense if you want to make it a part of a larger expression, but it's not immediately obvious how that will look in practice (I guess you could use umin/umax as an awkward way to and/or conditions).

We have a way to represent logic or/and in SCEV. Maybe umin/umax is a bit ugly, but we already have precedent for that. Having a single set of simplification and inference rules seems strongly better than having two less well tested implementations which largely duplicate functionality.

[reames]

I sent an RFC to discourse for broader discussion on this idea.

https://discourse.llvm.org/t/rfc-adding-a-scevcompareexpr-to-scalarevolution/60157

[mkazantsev]

llvm/lib/Analysis/ScalarEvolution.cpp

4153

I wonder, should we disallow pointer types of LHS and RHS here? I don't see what kind of problems it may bring, just being a bit wary about interpretingo of signed comparisons of pointers.

13232

UDiv -> Cmp

[reames]

ping, any chance I can get an LGTM?

llvm/lib/Analysis/ScalarEvolution.cpp

4153

I actually see one of the advantages of having a scev compare expression as being able to model pointer compares in an analogous way to IR without needing to introduce explicit ptrtoints. Having said that, I'm entirely happy to disable that for now, and discuss that in a separate review. I'd largely forgotten about that aspect, and didn't mean to commingle the discussion.

13232

Agreed, please assume the naming is fixed before landing.

[reames]

Closing review I'm not currently working on, and am unlikely to get back to in near future. Will reopen if priorities change.

llvm/include/llvm/Analysis/ScalarEvolution.h

public:
   const SCEV *getUMaxExpr(const SCEV *LHS, const SCEV *RHS);
   const SCEV *getUMaxExpr(SmallVectorImpl<const SCEV *> &Operands);
   const SCEV *getSMinExpr(const SCEV *LHS, const SCEV *RHS);
   const SCEV *getSMinExpr(SmallVectorImpl<const SCEV *> &Operands);
   const SCEV *getUMinExpr(const SCEV *LHS, const SCEV *RHS,
                           bool Sequential = false);
   const SCEV *getUMinExpr(SmallVectorImpl<const SCEV *> &Operands,
                           bool Sequential = false);
+  const SCEV *getCompareExpr(ICmpInst::Predicate P, const SCEV *RHS,
+                             const SCEV *LHS);
   const SCEV *getUnknown(Value *V);
   const SCEV *getCouldNotCompute();
 
   /// Return a SCEV for the constant 0 of a specific type.
   const SCEV *getZero(Type *Ty) { return getConstant(Ty, 0); }
 
   /// Return a SCEV for the constant 1 of a specific type.
   const SCEV *getOne(Type *Ty) { return getConstant(Ty, 1); }

llvm/include/llvm/Analysis/ScalarEvolutionDivision.h

public:
   void visitZeroExtendExpr(const SCEVZeroExtendExpr *Numerator) {}
   void visitSignExtendExpr(const SCEVSignExtendExpr *Numerator) {}
   void visitUDivExpr(const SCEVUDivExpr *Numerator) {}
   void visitSMaxExpr(const SCEVSMaxExpr *Numerator) {}
   void visitUMaxExpr(const SCEVUMaxExpr *Numerator) {}
   void visitSMinExpr(const SCEVSMinExpr *Numerator) {}
   void visitUMinExpr(const SCEVUMinExpr *Numerator) {}
   void visitSequentialUMinExpr(const SCEVSequentialUMinExpr *Numerator) {}
+  void visitCompareExpr(const SCEVCompareExpr *) {}
   void visitUnknown(const SCEVUnknown *Numerator) {}
   void visitCouldNotCompute(const SCEVCouldNotCompute *Numerator) {}
 
   void visitConstant(const SCEVConstant *Numerator);
 
   void visitAddRecExpr(const SCEVAddRecExpr *Numerator);
 
   void visitAddExpr(const SCEVAddExpr *Numerator);

llvm/include/llvm/Analysis/ScalarEvolutionExpressions.h

enum SCEVTypes : unsigned short {
   scUDivExpr,
   scAddRecExpr,
   scUMaxExpr,
   scSMaxExpr,
   scUMinExpr,
   scSMinExpr,
   scSequentialUMinExpr,
   scPtrToInt,
+  scCompareExpr,
   scUnknown,
   scCouldNotCompute
 };
 
 /// This class represents a constant integer value.
 class SCEVConstant : public SCEV {
   friend class ScalarEvolution;
 

 
 public:
   /// Methods for support type inquiry through isa, cast, and dyn_cast:
   static bool classof(const SCEV *S) {
     return S->getSCEVType() == scSequentialUMinExpr;
   }
 };
 
+/// This class represents a icmp comparing two SCEVS.  Currently, this node
+/// does not appear in generic SCEV expressions.  It is only used to support
+/// PredicatedScalarEvolution.
+class SCEVCompareExpr : public SCEV {
+  friend class ScalarEvolution;
+
+  const ICmpInst::Predicate Pred;
+  std::array<const SCEV *, 2> Operands;
+
+  SCEVCompareExpr(const FoldingSetNodeIDRef ID, const ICmpInst::Predicate Pred,
+                  const SCEV *LHS, const SCEV *RHS)
+    : SCEV(ID, scCompareExpr, computeExpressionSize({LHS, RHS})), Pred(Pred) {
+    Operands[0] = LHS;
+    Operands[1] = RHS;
+  }
+
+public:
+  ICmpInst::Predicate getPredicate() const { return Pred; }
+  const SCEV *getLHS() const { return Operands[0]; }
+  const SCEV *getRHS() const { return Operands[1]; }
+  size_t getNumOperands() const { return 2; }
+  const SCEV *getOperand(unsigned i) const {
+    assert((i == 0 || i == 1) && "Operand index out of range!");
+    return i == 0 ? getLHS() : getRHS();
+  }
+
+  using op_iterator = std::array<const SCEV *, 2>::const_iterator;
+  using op_range = iterator_range<op_iterator>;
+  op_range operands() const {
+    return make_range(Operands.begin(), Operands.end());
+  }
+
+  Type *getType() const {
+    return IntegerType::getInt1Ty(getRHS()->getType()->getContext());
+  }
+
+  /// Methods for support type inquiry through isa, cast, and dyn_cast:
+  static bool classof(const SCEV *S) {
+    return S->getSCEVType() == scCompareExpr;
+  }
+};
+
 /// This means that we are dealing with an entirely unknown SCEV
 /// value, and only represent it as its LLVM Value.  This is the
 /// "bottom" value for the analysis.
 class SCEVUnknown final : public SCEV, private CallbackVH {
   friend class ScalarEvolution;
 
   /// The parent ScalarEvolution value. This is used to update the
   /// parent's maps when the value associated with a SCEVUnknown is
case scUMaxExpr:
       return ((SC *)this)->visitUMaxExpr((const SCEVUMaxExpr *)S);
     case scSMinExpr:
       return ((SC *)this)->visitSMinExpr((const SCEVSMinExpr *)S);
     case scUMinExpr:
       return ((SC *)this)->visitUMinExpr((const SCEVUMinExpr *)S);
     case scSequentialUMinExpr:
       return ((SC *)this)
           ->visitSequentialUMinExpr((const SCEVSequentialUMinExpr *)S);
+    case scCompareExpr:
+      return ((SC *)this)->visitCompareExpr((const SCEVCompareExpr *)S);
     case scUnknown:
       return ((SC *)this)->visitUnknown((const SCEVUnknown *)S);
     case scCouldNotCompute:
       return ((SC *)this)->visitCouldNotCompute((const SCEVCouldNotCompute *)S);
     }
     llvm_unreachable("Unknown SCEV kind!");
   }
 
while (!Worklist.empty() && !Visitor.isDone()) {
         continue;
       case scAddExpr:
       case scMulExpr:
       case scSMaxExpr:
       case scUMaxExpr:
       case scSMinExpr:
       case scUMinExpr:
       case scSequentialUMinExpr:
+      case scCompareExpr:
       case scAddRecExpr:
         for (const auto *Op : cast<SCEVNAryExpr>(S)->operands())
           push(Op);
         continue;
       case scUDivExpr: {
         const SCEVUDivExpr *UDiv = cast<SCEVUDivExpr>(S);
         push(UDiv->getLHS());
         push(UDiv->getRHS());
const SCEV *visitSequentialUMinExpr(const SCEVSequentialUMinExpr *Expr) {
     bool Changed = false;
     for (auto *Op : Expr->operands()) {
       Operands.push_back(((SC *)this)->visit(Op));
       Changed |= Op != Operands.back();
     }
     return !Changed ? Expr : SE.getUMinExpr(Operands, /*Sequential=*/true);
   }
 
+  const SCEV *visitCompareExpr(const SCEVCompareExpr *Expr) {
+    SmallVector<const SCEV *, 2> Operands;
+    bool Changed = false;
+    for (auto *Op : Expr->operands()) {
+      Operands.push_back(((SC *)this)->visit(Op));
+      Changed |= Op != Operands.back();
+    }
+    return !Changed ? Expr : SE.getCompareExpr(Expr->getPredicate(),
+                                               Operands[0], Operands[1]);
+  }
+
   const SCEV *visitUnknown(const SCEVUnknown *Expr) { return Expr; }
 
   const SCEV *visitCouldNotCompute(const SCEVCouldNotCompute *Expr) {
     return Expr;
   }
 };
 
 using ValueToValueMap = DenseMap<const Value *, Value *>;

llvm/include/llvm/Transforms/Utils/ScalarEvolutionExpander.h

private:
   Value *visitUMaxExpr(const SCEVUMaxExpr *S);
 
   Value *visitSMinExpr(const SCEVSMinExpr *S);
 
   Value *visitUMinExpr(const SCEVUMinExpr *S);
 
   Value *visitSequentialUMinExpr(const SCEVSequentialUMinExpr *S);
 
+  Value *visitCompareExpr(const SCEVCompareExpr *Expr);
+
   Value *visitUnknown(const SCEVUnknown *S) { return S->getValue(); }
 
   void rememberInstruction(Value *I);
 
   bool isNormalAddRecExprPHI(PHINode *PN, Instruction *IncV, const Loop *L);
 
   bool isExpandedAddRecExprPHI(PHINode *PN, Instruction *IncV, const Loop *L);
 

llvm/lib/Analysis/ScalarEvolution.cpp

case scSequentialUMinExpr: {
     }
     return;
   }
   case scUDivExpr: {
     const SCEVUDivExpr *UDiv = cast<SCEVUDivExpr>(this);
     OS << "(" << *UDiv->getLHS() << " /u " << *UDiv->getRHS() << ")";
     return;
   }
+  case scCompareExpr: {
+    const SCEVCompareExpr *Cmp = cast<SCEVCompareExpr>(this);
+    OS << "(" << *Cmp->getLHS() << " "
+       << CmpInst::getPredicateName(Cmp->getPredicate())
+       << " " << *Cmp->getRHS() << ")";
+    return;
+  }
   case scUnknown: {
     const SCEVUnknown *U = cast<SCEVUnknown>(this);
     Type *AllocTy;
     if (U->isSizeOf(AllocTy)) {
       OS << "sizeof(" << *AllocTy << ")";
       return;
     }
     if (U->isAlignOf(AllocTy)) {
Type *SCEV::getType() const {
   case scSMinExpr:
     return cast<SCEVMinMaxExpr>(this)->getType();
   case scSequentialUMinExpr:
     return cast<SCEVSequentialMinMaxExpr>(this)->getType();
   case scAddExpr:
     return cast<SCEVAddExpr>(this)->getType();
   case scUDivExpr:
     return cast<SCEVUDivExpr>(this)->getType();
+  case scCompareExpr:
+    return cast<SCEVCompareExpr>(this)->getType();
   case scUnknown:
     return cast<SCEVUnknown>(this)->getType();
   case scCouldNotCompute:
     llvm_unreachable("Attempt to use a SCEVCouldNotCompute object!");
   }
   llvm_unreachable("Unknown SCEV kind!");
 }
 
case scUDivExpr: {
     if (X != 0)
       return X;
     X = CompareSCEVComplexity(EqCacheSCEV, EqCacheValue, LI, LC->getRHS(),
                               RC->getRHS(), DT, Depth + 1);
     if (X == 0)
       EqCacheSCEV.unionSets(LHS, RHS);
     return X;
   }
+  case scCompareExpr: {
+    auto *LC = cast<SCEVCompareExpr>(LHS);
+    auto *RC = cast<SCEVCompareExpr>(RHS);
+
+    // Lexicographically compare udiv expressions.
+    auto X = CompareSCEVComplexity(EqCacheSCEV, EqCacheValue, LI, LC->getLHS(),
+                                   RC->getLHS(), DT, Depth + 1);
+    if (X != 0)
+      return X;
+    X = CompareSCEVComplexity(EqCacheSCEV, EqCacheValue, LI, LC->getRHS(),
+                              RC->getRHS(), DT, Depth + 1);
+    if (X == 0)
+      EqCacheSCEV.unionSets(LHS, RHS);
+    return X;
+  }
 
   case scPtrToInt:
   case scTruncate:
   case scZeroExtend:
   case scSignExtend: {
     const SCEVCastExpr *LC = cast<SCEVCastExpr>(LHS);
     const SCEVCastExpr *RC = cast<SCEVCastExpr>(RHS);
 
public:
   RetVal visitUMinExpr(const SCEVUMinExpr *Expr) {
     return visitAnyMinMaxExpr(Expr);
   }
 
   RetVal visitSequentialUMinExpr(const SCEVSequentialUMinExpr *Expr) {
     return visitAnyMinMaxExpr(Expr);
   }
 
+  RetVal visitCompareExpr(const SCEVCompareExpr *Expr) { return Expr; }
+
   RetVal visitUnknown(const SCEVUnknown *Expr) { return Expr; }
 
   RetVal visitCouldNotCompute(const SCEVCouldNotCompute *Expr) { return Expr; }
 };
 
 } // namespace
 
 const SCEV *

 }
 
 const SCEV *ScalarEvolution::getUMinExpr(SmallVectorImpl<const SCEV *> &Ops,
                                          bool Sequential) {
   return Sequential ? getSequentialMinMaxExpr(scSequentialUMinExpr, Ops)
                     : getMinMaxExpr(scUMinExpr, Ops);
 }
 
+const SCEV *ScalarEvolution::getCompareExpr(ICmpInst::Predicate Pred,
+                                            const SCEV *LHS,
+                                            const SCEV *RHS) {
+  FoldingSetNodeID ID;
+  ID.AddInteger(scCompareExpr);
+  ID.AddInteger(Pred);
+  ID.AddPointer(LHS);
+  ID.AddPointer(RHS);
+  void *IP = nullptr;
+  if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP))
+    return S;
+
+  // TODO: Add various simplification rules here by moving/borrowing
+  // existing inference code.
+
+  // The Insertion Point (IP) might be invalid by now (due to UniqueSCEVs
+  // changes). Make sure we get a new one.
+  IP = nullptr;
+  if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
+  SCEV *S = new (SCEVAllocator) SCEVCompareExpr(ID.Intern(SCEVAllocator),
+                                                Pred, LHS, RHS);
+  UniqueSCEVs.InsertNode(S, IP);
+  registerUser(S, {LHS, RHS});
+  return S;
+}
+
 const SCEV *
 ScalarEvolution::getSizeOfScalableVectorExpr(Type *IntTy,
                                              ScalableVectorType *ScalableTy) {
   Constant *NullPtr = Constant::getNullValue(ScalableTy->getPointerTo());
   Constant *One = ConstantInt::get(IntTy, 1);
   Constant *GEP = ConstantExpr::getGetElementPtr(ScalableTy, NullPtr, One);
   // Note that the expression we created is the final expression, we don't
   // want to simplify it any further Also, if we call a normal getSCEV(),
bool follow(const SCEV *S) {
       case scSignExtend:
       case scAddExpr:
       case scMulExpr:
       case scUMaxExpr:
       case scSMaxExpr:
       case scUMinExpr:
       case scSMinExpr:
       case scSequentialUMinExpr:
+      case scCompareExpr:
         // These expressions are available if their operand(s) is/are.
         return true;
 
       case scAddRecExpr: {
         // We allow add recurrences that are on the loop BB is in, or some
         // outer loop.  This guarantees availability because the value of the
         // add recurrence at BB is simply the "current" value of the induction
         // variable.  We can relax this in the future; for instance an add
if (Constant *LHS = BuildConstantFromSCEV(SU->getLHS()))
           return ConstantExpr::getUDiv(LHS, RHS);
     return nullptr;
   }
   case scSMaxExpr:
   case scUMaxExpr:
   case scSMinExpr:
   case scUMinExpr:
   case scSequentialUMinExpr:
+  case scCompareExpr:
     return nullptr; // TODO: smax, umax, smin, umax, umin_seq.
   }
   llvm_unreachable("Unknown SCEV kind!");
 }
 
 const SCEV *ScalarEvolution::computeSCEVAtScope(const SCEV *V, const Loop *L) {
   if (isa<SCEVConstant>(V)) return V;
 
case scUDivExpr: {
     if (LD == LoopVariant)
       return LoopVariant;
     LoopDisposition RD = getLoopDisposition(UDiv->getRHS(), L);
     if (RD == LoopVariant)
       return LoopVariant;
     return (LD == LoopInvariant && RD == LoopInvariant) ?
            LoopInvariant : LoopComputable;
   }
+  case scCompareExpr: {
+    auto *UDiv = cast<SCEVCompareExpr>(S);
+    LoopDisposition LD = getLoopDisposition(UDiv->getLHS(), L);
+    if (LD == LoopVariant)
+      return LoopVariant;
+    LoopDisposition RD = getLoopDisposition(UDiv->getRHS(), L);
+    if (RD == LoopVariant)
+      return LoopVariant;
+    return (LD == LoopInvariant && RD == LoopInvariant) ?
+           LoopInvariant : LoopComputable;
+  }
   case scUnknown:
     // All non-instruction values are loop invariant.  All instructions are loop
     // invariant if they are not contained in the specified loop.
     // Instructions are never considered invariant in the function body
     // (null loop) because they are defined within the "loop".
     if (auto *I = dyn_cast<Instruction>(cast<SCEVUnknown>(S)->getValue()))
       return (L && !L->contains(I)) ? LoopInvariant : LoopVariant;
     return LoopInvariant;
case scUDivExpr: {
     const SCEVUDivExpr *UDiv = cast<SCEVUDivExpr>(S);
     const SCEV *LHS = UDiv->getLHS(), *RHS = UDiv->getRHS();
     BlockDisposition LD = getBlockDisposition(LHS, BB);
     if (LD == DoesNotDominateBlock)
       return DoesNotDominateBlock;
     BlockDisposition RD = getBlockDisposition(RHS, BB);
     if (RD == DoesNotDominateBlock)
       return DoesNotDominateBlock;
     return (LD == ProperlyDominatesBlock && RD == ProperlyDominatesBlock) ?
       ProperlyDominatesBlock : DominatesBlock;
   }
+  case scCompareExpr: {
+    const SCEVCompareExpr *UDiv = cast<SCEVCompareExpr>(S);
+    const SCEV *LHS = UDiv->getLHS(), *RHS = UDiv->getRHS();
+    BlockDisposition LD = getBlockDisposition(LHS, BB);
+    if (LD == DoesNotDominateBlock)
+      return DoesNotDominateBlock;
+    BlockDisposition RD = getBlockDisposition(RHS, BB);
+    if (RD == DoesNotDominateBlock)
+      return DoesNotDominateBlock;
+    return (LD == ProperlyDominatesBlock && RD == ProperlyDominatesBlock) ?
+      ProperlyDominatesBlock : DominatesBlock;
+  }
   case scUnknown:
     if (Instruction *I =
           dyn_cast<Instruction>(cast<SCEVUnknown>(S)->getValue())) {
       if (I->getParent() == BB)
         return DominatesBlock;
       if (DT.properlyDominates(I->getParent(), BB))
         return ProperlyDominatesBlock;
       return DoesNotDominateBlock;

llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp

for (Value *Op : ArrayRef<Value *>(Ops).drop_back())
     OpIsZero.emplace_back(Builder.CreateICmpEQ(Op, SaturationPoint));
 
   Value *AnyOpIsZero = Builder.CreateLogicalOr(OpIsZero);
 
   Value *NaiveUMin = expandUMinExpr(S);
   return Builder.CreateSelect(AnyOpIsZero, SaturationPoint, NaiveUMin);
 }
 
+Value *SCEVExpander::visitCompareExpr(const SCEVCompareExpr *Expr) {
+  return Builder.CreateICmp(Expr->getPredicate(), expand(Expr->getLHS()),
+                            expand(Expr->getRHS()));
+}
+
 Value *SCEVExpander::expandCodeForImpl(const SCEV *SH, Type *Ty,
                                        Instruction *IP, bool Root) {
   setInsertPoint(IP);
   Value *V = expandCodeForImpl(SH, Ty, Root);
   return V;
 }
 
 Value *SCEVExpander::expandCodeForImpl(const SCEV *SH, Type *Ty, bool Root) {
case scSequentialUMinExpr: {
     }
     default:
       assert(!isa<SCEVSequentialMinMaxExpr>(S) &&
              "Unhandled SCEV expression type?");
       break;
     }
     break;
   }
+  case scCompareExpr:
+    Cost += CmpSelCost(Instruction::ICmp, 2, 0, 1);
+    break;
   case scAddRecExpr: {
     // In this polynominal, we may have some zero operands, and we shouldn't
     // really charge for those. So how many non-zero coeffients are there?
     int NumTerms = llvm::count_if(S->operands(), [](const SCEV *Op) {
                                     return !Op->isZero();
                                   });
 
     assert(NumTerms >= 1 && "Polynominal should have at least one term.");
bool SCEVExpander::isHighCostExpansionHelper(
   case scTruncate:
   case scPtrToInt:
   case scZeroExtend:
   case scSignExtend: {
     Cost +=
         costAndCollectOperands<SCEVCastExpr>(WorkItem, TTI, CostKind, Worklist);
     return false; // Will answer upon next entry into this function.
   }
+  case scCompareExpr: {
+    Cost += costAndCollectOperands<SCEVCompareExpr>(WorkItem, TTI, CostKind,
+                                                    Worklist);
+    return false; // Will answer upon next entry into this function.
+  }
   case scUDivExpr: {
     // 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, we need to account for it's cost.
 
     // At the beginning of this function we already tried to find existing
     // value for plain 'S'. Now try to lookup 'S + 1' since it is common