[NFCI][SCEV] getPointerBase(): de-recursify

[lebedev.ri]

Summary

This is boringly straight-forward, each iteration we see if
V is some expression that we can look into, and if it has
a single pointer operand, then set V to that operand
and repeat.

[efriedma]

Do you have some plan to start using the DepthLimit somewhere?

[lebedev.ri]

In D82632#2118058, @efriedma wrote:

Do you have some plan to start using the DepthLimit somewhere?

No, i could drop it.
But it may be a good idea to consistently have such cut-offs available for use.

[efriedma]

I'd prefer not to add the cutoff until we have a real use for it.

[lebedev.ri]

In D82632#2118113, @efriedma wrote:

I'd prefer not to add the cutoff until we have a real use for it.

I see, droped it.

LG?

[nikic]

LGTM

llvm/lib/Analysis/ScalarEvolution.cpp

3971

As this is a recurring pattern, I wonder if there's room for something like llvm::get_unique(R &&Range, Getter Fn) in STLExtras.

[lebedev.ri]

In D82632#2118404, @nikic wrote:

LGTM

Thank you for the review.

llvm/include/llvm/Analysis/ScalarEvolution.h

public:
 
   /// Promote the operands to the wider of the types using zero-extension, and
   /// then perform a umin operation with them. N-ary function.
   const SCEV *getUMinFromMismatchedTypes(SmallVectorImpl<const SCEV *> &Ops);
 
   /// Transitively follow the chain of pointer-type operands until reaching a
   /// SCEV that does not have a single pointer operand. This returns a
   /// SCEVUnknown pointer for well-formed pointer-type expressions, but corner
-  /// cases do exist.
-  const SCEV *getPointerBase(const SCEV *V);
+  /// cases do exist. DepthLimit allows to limit amount of traversal done,
+  /// limit of 0 (default) imposes no restrictions.
+  const SCEV *getPointerBase(const SCEV *V, unsigned DepthLimit = 0);
 
   /// Return a SCEV expression for the specified value at the specified scope
   /// in the program.  The L value specifies a loop nest to evaluate the
   /// expression at, where null is the top-level or a specified loop is
   /// immediately inside of the loop.
   ///
   /// This method can be used to compute the exit value for a variable defined
   /// in a loop by querying what the value will hold in the parent loop.

llvm/lib/Analysis/ScalarEvolution.cpp

const SCEV *ScalarEvolution::getUMinFromMismatchedTypes(
   SmallVector<const SCEV *, 2> PromotedOps;
   for (auto *S : Ops)
     PromotedOps.push_back(getNoopOrZeroExtend(S, MaxType));
 
   // Generate umin.
   return getUMinExpr(PromotedOps);
 }
 
-const SCEV *ScalarEvolution::getPointerBase(const SCEV *V) {
+const SCEV *ScalarEvolution::getPointerBase(const SCEV *V,
+                                            unsigned DepthLimit) {
   // A pointer operand may evaluate to a nonpointer expression, such as null.
   if (!V->getType()->isPointerTy())
     return V;
 
+  for (unsigned Depth = 0; DepthLimit == 0 || Depth < DepthLimit; ++Depth) {
     if (const SCEVCastExpr *Cast = dyn_cast<SCEVCastExpr>(V)) {
-    return getPointerBase(Cast->getOperand());
+      V = Cast->getOperand();
     } else if (const SCEVNAryExpr *NAry = dyn_cast<SCEVNAryExpr>(V)) {
       const SCEV *PtrOp = nullptr;
       for (const SCEV *NAryOp : NAry->operands()) {
         if (NAryOp->getType()->isPointerTy()) {
-        // Cannot find the base of an expression with multiple pointer operands.
+          // Cannot find the base of an expression with multiple pointer ops.
           if (PtrOp)
             return V;
           PtrOp = NAryOp;
         }
       }
-    if (!PtrOp)
+      if (!PtrOp) // All operands were non-pointer.
+        return V;
+      V = PtrOp;
+    } else // Not something we can look into.
       return V;
-    return getPointerBase(PtrOp);
   }
+  // Depth cut-off reached, not allowed to look any furter.
   return V;
 }
 
 /// Push users of the given Instruction onto the given Worklist.
 static void
 PushDefUseChildren(Instruction *I,
                    SmallVectorImpl<Instruction *> &Worklist) {
   // Push the def-use children onto the Worklist stack.