Remove SCEVCache and FindConstantPointers from complete loop unrolling heuristic.

[mzolotukhin]

Summary

Using some SCEV functionality helped to entirely remove SCEVCache class and FindConstantPointers SCEV visitor.
Also, this makes the code more universal - I'll take advandate of it in next patches where I start handling additional types of instructions.

[atrick]

Great use of SCEV.

lib/Transforms/Scalar/LoopUnrollPass.cpp

304 ↗

(On Diff #27020)

"I am"

326 ↗

(On Diff #27020)

"AddRec"

[mzolotukhin]

Thanks, Andy!

I also want to wait for a response from Chandler since he put a lot of efforts into this code.

Michael

lib/Transforms/Scalar/LoopUnrollPass.cpp

304 ↗

(On Diff #27020)

There is no typo here, but probably I should've added \param:

/// \brief Try to simplify instruction \param I using its SCEV expression.

326 ↗

(On Diff #27020)

Thanks for the catch!

[mzolotukhin]

• Fix typos.

[mzolotukhin]

• Not only GetElementPtrInst could have a base pointer - allow for that in GEPPointerBases type.

[chandlerc]

As Andy said, really nice use of SCEV. This is exactly the direction I was hoping for here.

Detailed comments below. Mostly this is about sorting out minor details, naming, and how to cache these things.

lib/Transforms/Scalar/LoopUnrollPass.cpp

281–288 ↗

(On Diff #27089)

Based on this (very nice) comment, the name should just be "PointerBases"... Or even better, BasePointers. But see below...

315 ↗

(On Diff #27089)

I think a better name for this would be 'simplifyInstWithSCEV'

326 ↗

(On Diff #27089)

I'd compute this as part of the constructor (and thus once).

338–339 ↗

(On Diff #27089)

For pointer types, is this the byte difference or are the units in something other than bytes?

340–341 ↗

(On Diff #27089)

I don't think this quite works.

The offset value, while constant, is not the simplification of this instruction. For example, if the offset is 2, and we see 'icmp eq' of I and the constant '2', it shouldn't be able to constant fold.

I think you want to store a mapping from instruction to a pair of Value* and Constant*, "BasePointersAndOffsets" or some such. Not sure of a good name here.

361–362 ↗

(On Diff #27089)

Is this better than constant folding? It's not clear to me that it is, it seems like it might be much more expensive.

I think I would change the *end* of this function to 'if (SimpleV) return true;' and then add a final return that was essentially 'return Base::visitBinaryOperator(I);' so its clear you're just delegating.

387–389 ↗

(On Diff #27089)

This shouldn't be needed now, right?

407–411 ↗

(On Diff #27089)

The comment above doesn't make much sense any more. =]

I'd also consider bailing or asserting if the offset requires lots of bits here rather than limiting it.

[mzolotukhin]

• Rebase on master.
• Rename SCEVSimplify to simplifyInstWithSCEV.
• Use assert + getSExtValue instead of getLimitedValue and remove no
• Introduce SimplifiedOffsets.
• Remove unneeded code.
• Move initialize of IterationNumber to constructor.
• Doxygenify comment for SimplifiedValues.
• Fallback to Base visitor if failed to constant fold (and only then call simplifyInstWithSCEV).

[chandlerc]

This is looking really good. A bunch of minor stuff below. I'm happy for you to just address most of this before it gets committed, but I don't see the definition of 'simplifyUsingOffsets'. That's the only thing I really want to see before LGTM-ing.

lib/Transforms/Scalar/LoopUnrollPass.cpp

275 ↗

(On Diff #27259)

I think this should just be a ConstantInt, it'll save you casting below.

290–296 ↗

(On Diff #27259)

I'd call this 'SimplifiedAddresses'. That also corresponds nicely to them being pointers.

340 ↗

(On Diff #27259)

I would invert this to use early exit.

auto *AR = dyn_cast<SCEVAddRecExpr>(S);
if (!AR)
  return false;

...

348–349 ↗

(On Diff #27259)

Should we check that I is a pointer? Shouldn't this be dyn_cast_or_null?

356–357 ↗

(On Diff #27259)

If you're going to assert, you can just write 'cast<ConstantInt>' and it will assert for you.

I think that means you can just write:

SimplifiedOffsets[I] = {Base->getValue(), cast<ConstantInt>(Offset->getValue())};

387 ↗

(On Diff #27259)

Where is this defined?

410–412 ↗

(On Diff #27259)

I think I've mentioned this before, but please don't use 'count' and then 'lookup'. It queries the hashtable twice. You should just use 'find' and the iterator.

[mzolotukhin]

Hi Chandler,

Thanks for the review! I'll address the concerns and commit the patch soon. Please also find some comments inline:

lib/Transforms/Scalar/LoopUnrollPass.cpp

348–349 ↗

(On Diff #27259)

No, this is correct.
getPointerBase(S) returns a SCEV expression - if it fails to find the base, it'll return the incoming SCEV expression S. Then, when we try to cast it to SCEVUnknown we get nullptr, which is tested in the following check.
So, the fail condition here is getting not SCEVUnknown.

387 ↗

(On Diff #27259)

Oops, it crept to the subsequent patch (D10206). I'll move it to this one before committing, but do you mind taking a glance there too?

[chandlerc]

See below before committing please.

lib/Transforms/Scalar/LoopUnrollPass.cpp

387 ↗

(On Diff #27259)

Please commit *without* this change.

I don't think simplifyUsingOffsets is the right approach (as handled in D10206), and I'd rather not hold the rest of this up on that review.

[mzolotukhin]

Thanks for review, updated patch landed in r239282.

llvm/trunk/lib/Transforms/Scalar/LoopUnrollPass.cpp

Pass *llvm::createLoopUnrollPass(int Threshold, int Count, int AllowPartial,
   return new LoopUnroll(Threshold, Count, AllowPartial, Runtime);
 }
 
 Pass *llvm::createSimpleLoopUnrollPass() {
   return llvm::createLoopUnrollPass(-1, -1, 0, 0);
 }
 
 namespace {
-/// \brief SCEV expressions visitor used for finding expressions that would
-/// become constants if the loop L is unrolled.
-struct FindConstantPointers {
-  /// \brief Shows whether the expression is ConstAddress+Constant or not.
-  bool IndexIsConstant;
-
-  /// \brief Used for filtering out SCEV expressions with two or more AddRec
-  /// subexpressions.
-  ///
-  /// Used to filter out complicated SCEV expressions, having several AddRec
-  /// sub-expressions. We don't handle them, because unrolling one loop
-  /// would help to replace only one of these inductions with a constant, and
-  /// consequently, the expression would remain non-constant.
-  bool HaveSeenAR;
-
-  /// \brief If the SCEV expression becomes ConstAddress+Constant, this value
-  /// holds ConstAddress. Otherwise, it's nullptr.
-  Value *BaseAddress;
-
-  /// \brief The loop, which we try to completely unroll.
-  const Loop *L;
-
-  ScalarEvolution &SE;
-
-  FindConstantPointers(const Loop *L, ScalarEvolution &SE)
-      : IndexIsConstant(true), HaveSeenAR(false), BaseAddress(nullptr),
-        L(L), SE(SE) {}
-
-  /// Examine the given expression S and figure out, if it can be a part of an
-  /// expression, that could become a constant after the loop is unrolled.
-  /// The routine sets IndexIsConstant and HaveSeenAR according to the analysis
-  /// results.
-  /// \returns true if we need to examine subexpressions, and false otherwise.
-  bool follow(const SCEV *S) {
-    if (const SCEVUnknown *SC = dyn_cast<SCEVUnknown>(S)) {
-      // We've reached the leaf node of SCEV, it's most probably just a
-      // variable.
-      // If it's the only one SCEV-subexpression, then it might be a base
-      // address of an index expression.
-      // If we've already recorded base address, then just give up on this SCEV
-      // - it's too complicated.
-      if (BaseAddress) {
-        IndexIsConstant = false;
-        return false;
-      }
-      BaseAddress = SC->getValue();
-      return false;
-    }
-    if (isa<SCEVConstant>(S))
-      return false;
-    if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) {
-      // If the current SCEV expression is AddRec, and its loop isn't the loop
-      // we are about to unroll, then we won't get a constant address after
-      // unrolling, and thus, won't be able to eliminate the load.
-      if (AR->getLoop() != L) {
-        IndexIsConstant = false;
-        return false;
-      }
-      // We don't handle multiple AddRecs here, so give up in this case.
-      if (HaveSeenAR) {
-        IndexIsConstant = false;
-        return false;
-      }
-      HaveSeenAR = true;
-    }
-
-    // Continue traversal.
-    return true;
-  }
-  bool isDone() const { return !IndexIsConstant; }
-};
-} // End anonymous namespace.
-
-namespace {
-/// \brief A cache of SCEV results used to optimize repeated queries to SCEV on
-/// the same set of instructions.
-///
-/// The primary cost this saves is the cost of checking the validity of a SCEV
-/// every time it is looked up. However, in some cases we can provide a reduced
-/// and especially useful model for an instruction based upon SCEV that is
-/// non-trivial to compute but more useful to clients.
-class SCEVCache {
-public:
-  /// \brief Struct to represent a GEP whose start and step are known fixed
-  /// offsets from a base address due to SCEV's analysis.
-  struct GEPDescriptor {
-    Value *BaseAddr = nullptr;
-    unsigned Start = 0;
-    unsigned Step = 0;
-  };
-
-  Optional<GEPDescriptor> getGEPDescriptor(GetElementPtrInst *GEP);
-
-  SCEVCache(const Loop &L, ScalarEvolution &SE) : L(L), SE(SE) {}
-
-private:
-  const Loop &L;
-  ScalarEvolution &SE;
-
-  SmallDenseMap<GetElementPtrInst *, GEPDescriptor> GEPDescriptors;
-};
-} // End anonymous namespace.
-
-/// \brief Get a simplified descriptor for a GEP instruction.
-///
-/// Where possible, this produces a simplified descriptor for a GEP instruction
-/// using SCEV analysis of the containing loop. If this isn't possible, it
-/// returns an empty optional.
-///
-/// The model is a base address, an initial offset, and a per-iteration step.
-/// This fits very common patterns of GEPs inside loops and is something we can
-/// use to simulate the behavior of a particular iteration of a loop.
-///
-/// This is a cached interface. The first call may do non-trivial work to
-/// compute the result, but all subsequent calls will return a fast answer
-/// based on a cached result. This includes caching negative results.
-Optional<SCEVCache::GEPDescriptor>
-SCEVCache::getGEPDescriptor(GetElementPtrInst *GEP) {
-  decltype(GEPDescriptors)::iterator It;
-  bool Inserted;
-
-  std::tie(It, Inserted) = GEPDescriptors.insert({GEP, {}});
-
-  if (!Inserted) {
-    if (!It->second.BaseAddr)
-      return None;
-
-    return It->second;
-  }
-
-  // We've inserted a new record into the cache, so compute the GEP descriptor
-  // if possible.
-  Value *V = cast<Value>(GEP);
-  if (!SE.isSCEVable(V->getType()))
-    return None;
-  const SCEV *S = SE.getSCEV(V);
-
-  // FIXME: It'd be nice if the worklist and set used by the
-  // SCEVTraversal could be re-used between loop iterations, but the
-  // interface doesn't support that. There is no way to clear the visited
-  // sets between uses.
-  FindConstantPointers Visitor(&L, SE);
-  SCEVTraversal<FindConstantPointers> T(Visitor);
-
-  // Try to find (BaseAddress+Step+Offset) tuple.
-  // If succeeded, save it to the cache - it might help in folding
-  // loads.
-  T.visitAll(S);
-  if (!Visitor.IndexIsConstant || !Visitor.BaseAddress)
-    return None;
-
-  const SCEV *BaseAddrSE = SE.getSCEV(Visitor.BaseAddress);
-  if (BaseAddrSE->getType() != S->getType())
-    return None;
-  const SCEV *OffSE = SE.getMinusSCEV(S, BaseAddrSE);
-  const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(OffSE);
-
-  if (!AR)
-    return None;
-
-  const SCEVConstant *StepSE =
-      dyn_cast<SCEVConstant>(AR->getStepRecurrence(SE));
-  const SCEVConstant *StartSE = dyn_cast<SCEVConstant>(AR->getStart());
-  if (!StepSE || !StartSE)
-    return None;
-
-  // Check and skip caching if doing so would require lots of bits to
-  // avoid overflow.
-  APInt Start = StartSE->getValue()->getValue();
-  APInt Step = StepSE->getValue()->getValue();
-  if (Start.getActiveBits() > 32 || Step.getActiveBits() > 32)
-    return None;
-
-  // We found a cacheable SCEV model for the GEP.
-  It->second.BaseAddr = Visitor.BaseAddress;
-  It->second.Start = Start.getLimitedValue();
-  It->second.Step = Step.getLimitedValue();
-  return It->second;
-}
-
-namespace {
 // This class is used to get an estimate of the optimization effects that we
 // could get from complete loop unrolling. It comes from the fact that some
 // loads might be replaced with concrete constant values and that could trigger
 // a chain of instruction simplifications.
 //
 // E.g. we might have:
 //   int a[] = {0, 1, 0};
 //   v = 0;
 //   for (i = 0; i < 3; i ++)
 //     v += b[i]*a[i];
 // If we completely unroll the loop, we would get:
 //   v = b[0]*a[0] + b[1]*a[1] + b[2]*a[2]
 // Which then will be simplified to:
 //   v = b[0]* 0 + b[1]* 1 + b[2]* 0
 // And finally:
 //   v = b[1]
 class UnrolledInstAnalyzer : private InstVisitor<UnrolledInstAnalyzer, bool> {
   typedef InstVisitor<UnrolledInstAnalyzer, bool> Base;
   friend class InstVisitor<UnrolledInstAnalyzer, bool>;
+  struct SimplifiedAddress {
+    Value *Base = nullptr;
+    ConstantInt *Offset = nullptr;
+  };
 
 public:
   UnrolledInstAnalyzer(unsigned Iteration,
                        DenseMap<Value *, Constant *> &SimplifiedValues,
-                       SCEVCache &SC)
-      : Iteration(Iteration), SimplifiedValues(SimplifiedValues), SC(SC) {}
+                       const Loop *L, ScalarEvolution &SE)
+      : Iteration(Iteration), SimplifiedValues(SimplifiedValues), L(L), SE(SE) {
+      IterationNumber = SE.getConstant(APInt(64, Iteration));
+  }
 
   // Allow access to the initial visit method.
   using Base::visit;
 
 private:
+  /// \brief A cache of pointer bases and constant-folded offsets corresponding
+  /// to GEP (or derived from GEP) instructions.
+  ///
+  /// In order to find the base pointer one needs to perform non-trivial
+  /// traversal of the corresponding SCEV expression, so it's good to have the
+  /// results saved.
+  DenseMap<Value *, SimplifiedAddress> SimplifiedAddresses;
+
   /// \brief Number of currently simulated iteration.
   ///
   /// If an expression is ConstAddress+Constant, then the Constant is
   /// Start + Iteration*Step, where Start and Step could be obtained from
   /// SCEVGEPCache.
   unsigned Iteration;
 
-  // While we walk the loop instructions, we we build up and maintain a mapping
-  // of simplified values specific to this iteration.  The idea is to propagate
-  // any special information we have about loads that can be replaced with
-  // constants after complete unrolling, and account for likely simplifications
-  // post-unrolling.
+  /// \brief SCEV expression corresponding to number of currently simulated
+  /// iteration.
+  const SCEV *IterationNumber;
+
+  /// \brief A Value->Constant map for keeping values that we managed to
+  /// constant-fold on the given iteration.
+  ///
+  /// While we walk the loop instructions, we build up and maintain a mapping
+  /// of simplified values specific to this iteration.  The idea is to propagate
+  /// any special information we have about loads that can be replaced with
+  /// constants after complete unrolling, and account for likely simplifications
+  /// post-unrolling.
   DenseMap<Value *, Constant *> &SimplifiedValues;
 
-  // We use a cache to wrap all our SCEV queries.
-  SCEVCache &SC;
+  const Loop *L;
+  ScalarEvolution &SE;
+
+  /// \brief Try to simplify instruction \param I using its SCEV expression.
+  ///
+  /// The idea is that some AddRec expressions become constants, which then
+  /// could trigger folding of other instructions. However, that only happens
+  /// for expressions whose start value is also constant, which isn't always the
+  /// case. In another common and important case the start value is just some
+  /// address (i.e. SCEVUnknown) - in this case we compute the offset and save
+  /// it along with the base address instead.
+  bool simplifyInstWithSCEV(Instruction *I) {
+    if (!SE.isSCEVable(I->getType()))
+      return false;
+
+    const SCEV *S = SE.getSCEV(I);
+    if (auto *SC = dyn_cast<SCEVConstant>(S)) {
+      SimplifiedValues[I] = SC->getValue();
+      return true;
+    }
+
+    auto *AR = dyn_cast<SCEVAddRecExpr>(S);
+    if (!AR)
+      return false;
+
+    const SCEV *ValueAtIteration = AR->evaluateAtIteration(IterationNumber, SE);
+    // Check if the AddRec expression becomes a constant.
+    if (auto *SC = dyn_cast<SCEVConstant>(ValueAtIteration)) {
+      SimplifiedValues[I] = SC->getValue();
+      return true;
+    }
+
+    // Check if the offset from the base address becomes a constant.
+    auto *Base = dyn_cast<SCEVUnknown>(SE.getPointerBase(S));
+    if (!Base)
+      return false;
+    auto *Offset =
+        dyn_cast<SCEVConstant>(SE.getMinusSCEV(ValueAtIteration, Base));
+    if (!Offset)
+      return false;
+    SimplifiedAddress Address;
+    Address.Base = Base->getValue();
+    Address.Offset = Offset->getValue();
+    SimplifiedAddresses[I] = Address;
+    return true;
+  }
 
   /// Base case for the instruction visitor.
-  bool visitInstruction(Instruction &I) { return false; };
+  bool visitInstruction(Instruction &I) {
+    return simplifyInstWithSCEV(&I);
+  }
 
   /// TODO: Add visitors for other instruction types, e.g. ZExt, SExt.
 
   /// Try to simplify binary operator I.
   ///
   /// TODO: Probaly it's worth to hoist the code for estimating the
   /// simplifications effects to a separate class, since we have a very similar
   /// code in InlineCost already.
   bool visitBinaryOperator(BinaryOperator &I) {
     Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
     if (!isa<Constant>(LHS))
       if (Constant *SimpleLHS = SimplifiedValues.lookup(LHS))
         LHS = SimpleLHS;
     if (!isa<Constant>(RHS))
       if (Constant *SimpleRHS = SimplifiedValues.lookup(RHS))
         RHS = SimpleRHS;
+
     Value *SimpleV = nullptr;
     const DataLayout &DL = I.getModule()->getDataLayout();
     if (auto FI = dyn_cast<FPMathOperator>(&I))
       SimpleV =
           SimplifyFPBinOp(I.getOpcode(), LHS, RHS, FI->getFastMathFlags(), DL);
     else
       SimpleV = SimplifyBinOp(I.getOpcode(), LHS, RHS, DL);
 
     if (Constant *C = dyn_cast_or_null<Constant>(SimpleV))
       SimplifiedValues[&I] = C;
 
-    return SimpleV;
+    if (SimpleV)
+      return true;
+    return Base::visitBinaryOperator(I);
   }
 
   /// Try to fold load I.
   bool visitLoad(LoadInst &I) {
     Value *AddrOp = I.getPointerOperand();
-    if (!isa<Constant>(AddrOp))
-      if (Constant *SimplifiedAddrOp = SimplifiedValues.lookup(AddrOp))
-        AddrOp = SimplifiedAddrOp;
 
-    auto *GEP = dyn_cast<GetElementPtrInst>(AddrOp);
-    if (!GEP)
-      return false;
-    auto OptionalGEPDesc = SC.getGEPDescriptor(GEP);
-    if (!OptionalGEPDesc)
+    auto AddressIt = SimplifiedAddresses.find(AddrOp);
+    if (AddressIt == SimplifiedAddresses.end())
       return false;
+    ConstantInt *SimplifiedAddrOp = AddressIt->second.Offset;
 
-    auto GV = dyn_cast<GlobalVariable>(OptionalGEPDesc->BaseAddr);
+    auto *GV = dyn_cast<GlobalVariable>(AddressIt->second.Base);
     // We're only interested in loads that can be completely folded to a
     // constant.
     if (!GV || !GV->hasInitializer())
       return false;
 
     ConstantDataSequential *CDS =
         dyn_cast<ConstantDataSequential>(GV->getInitializer());
     if (!CDS)
       return false;
 
-    // This calculation should never overflow because we bound Iteration quite
-    // low and both the start and step are 32-bit integers. We use signed
-    // integers so that UBSan will catch if a bug sneaks into the code.
     int ElemSize = CDS->getElementType()->getPrimitiveSizeInBits() / 8U;
-    int64_t Index = ((int64_t)OptionalGEPDesc->Start +
-                     (int64_t)OptionalGEPDesc->Step * (int64_t)Iteration) /
-                    ElemSize;
+    assert(SimplifiedAddrOp->getValue().getActiveBits() < 64 &&
+           "Unexpectedly large index value.");
+    int64_t Index = SimplifiedAddrOp->getSExtValue() / ElemSize;
     if (Index >= CDS->getNumElements()) {
       // FIXME: For now we conservatively ignore out of bound accesses, but
       // we're allowed to perform the optimization in this case.
       return false;
     }
 
     Constant *CV = CDS->getElementAsConstant(Index);
     assert(CV && "Constant expected.");
analyzeLoopUnrollCost(const Loop *L, unsigned TripCount, ScalarEvolution &SE,
   // Don't simulate loops with a big or unknown tripcount
   if (!UnrollMaxIterationsCountToAnalyze || !TripCount ||
       TripCount > UnrollMaxIterationsCountToAnalyze)
     return None;
 
   SmallSetVector<BasicBlock *, 16> BBWorklist;
   DenseMap<Value *, Constant *> SimplifiedValues;
 
-  // Use a cache to access SCEV expressions so that we don't pay the cost on
-  // each iteration. This cache is lazily self-populating.
-  SCEVCache SC(*L, SE);
-
   // The estimated cost of the unrolled form of the loop. We try to estimate
   // this by simplifying as much as we can while computing the estimate.
   unsigned UnrolledCost = 0;
   // We also track the estimated dynamic (that is, actually executed) cost in
   // the rolled form. This helps identify cases when the savings from unrolling
   // aren't just exposing dead control flows, but actual reduced dynamic
   // instructions due to the simplifications which we expect to occur after
   // unrolling.
   unsigned RolledDynamicCost = 0;
 
   // Simulate execution of each iteration of the loop counting instructions,
   // which would be simplified.
   // Since the same load will take different values on different iterations,
   // we literally have to go through all loop's iterations.
   for (unsigned Iteration = 0; Iteration < TripCount; ++Iteration) {
     SimplifiedValues.clear();
-    UnrolledInstAnalyzer Analyzer(Iteration, SimplifiedValues, SC);
+    UnrolledInstAnalyzer Analyzer(Iteration, SimplifiedValues, L, SE);
 
     BBWorklist.clear();
     BBWorklist.insert(L->getHeader());
     // Note that we *must not* cache the size, this loop grows the worklist.
     for (unsigned Idx = 0; Idx != BBWorklist.size(); ++Idx) {
       BasicBlock *BB = BBWorklist[Idx];
 
       // Visit all instructions in the given basic block and try to simplify