llvm.noalias - GetUnderlyingObjects to optionally collect noalias calls

[hfinkel]

Summary

This is part of the series started by D9375, and lets GetUnderlyingObjects, optionally, collect the llvm.noalias calls that it has looked through. This will be used by the AA implementation for llvm.noalias, to avoid double-walking (which could be expensive) and copy-and-paste.

[reames]

Resigning as a reviewer to get a very stale review off my list of blocking tasks in phabricator. Please reopen when desired.

[hfinkel]

Rebased.

I've thought about how to generalize this (it seems kind of silly to have GetUnderlyingObject(s) have a special parameter for this), but because I don't think that imposing the overhead of a virtual function call for each visited instruction is reasonable, I think the way to generalize it is to template it on some kind of customization functor. I've done that here, in the name of keeping this change small, and because I don't yet have a second use case. I'm happy to do the generalization either sequenced before this change or afterward (assuming, of course, we don't decide on a completely different way to satisfy this use case).

[majnemer]

include/llvm/Analysis/ValueTracking.h

227–235

Perhaps the NoAlias parameter deserves a mention?

lib/Analysis/ValueTracking.cpp

3070

auto *I

3070

Should we assign V the value of I->getOperand(0) ?

3070–3071

The following might be a little shorter:

if (match(V, m_Intrinsic<Intrinsic::noalias>())

3071

Braces are unneeded.

[hfinkel]

include/llvm/Analysis/ValueTracking.h

227–235

Yes. I'll add test to the comment.

lib/Analysis/ValueTracking.cpp

3070

Yes, this happens in D9383.

3070

auto *I

Sure.

3071

Both true, but I think it makes more sense this way once D9383 is also applied.

[hfinkel]

Updated per review comments.

[majnemer]

LGTM with nits

include/llvm/Analysis/ValueTracking.h

228–235

I find it more likely that a SmallVector will get passed in instead of a custom MaxLookup. Perhaps they should be reordered to one another?

[Eugene.Zelenko]

Looks like patch was not committed.

[hfinkel]

Rebased

[majnemer]

lib/Analysis/ValueTracking.cpp

3070–3074

I think you can sink this into the block for the auto CS = CallSite(V) condition. You can compare CS.getIntrinsicID() with Intrinsic::noalias.

[hfinkel]

lib/Analysis/ValueTracking.cpp

3070–3074

Yes, indeed!

[hfinkel]

Addressed review feedback.

[hfinkel]

Rebased.

include/llvm/Analysis/ValueTracking.h

template <typename T> class ArrayRef;
   /// If we can compute the length of the string pointed to by the specified
   /// pointer, return 'len+1'.  If we can't, return 0.
   uint64_t GetStringLength(const Value *V);
 
   /// This method strips off any GEP address adjustments and pointer casts from
   /// the specified value, returning the original object being addressed. Note
   /// that the returned value has pointer type if the specified value does. If
   /// the MaxLookup value is non-zero, it limits the number of instructions to
-  /// be stripped off.
+  /// be stripped off. If a NoAlias vector is provided, it is filled with any
+  /// llvm.noalias intrinsics looked through to find the underlying object.
   Value *GetUnderlyingObject(Value *V, const DataLayout &DL,
-                             unsigned MaxLookup = 6);
-  static inline const Value *GetUnderlyingObject(const Value *V,
-                                                 const DataLayout &DL,
-                                                 unsigned MaxLookup = 6) {
-    return GetUnderlyingObject(const_cast<Value *>(V), DL, MaxLookup);
+                             unsigned MaxLookup = 6,
+                             SmallVectorImpl<Instruction *> *NoAlias = nullptr);
+  static inline
+  const Value *GetUnderlyingObject(const Value *V,
+                 const DataLayout &DL, unsigned MaxLookup = 6,
+                 SmallVectorImpl<Instruction *> *NoAlias = nullptr) {
+    return GetUnderlyingObject(const_cast<Value *>(V), DL, MaxLookup, NoAlias);
   }
 
   /// \brief This method is similar to GetUnderlyingObject except that it can
   /// look through phi and select instructions and return multiple objects.
   ///
   /// If LoopInfo is passed, loop phis are further analyzed.  If a pointer
   /// accesses different objects in each iteration, we don't look through the
   /// phi node. E.g. consider this loop nest:
   ///
template <typename T> class ArrayRef;
   ///     Curr = A[i];
   ///     for (j: 0..N) {
   ///        Curr[j] = Prev[j] * B[j]
   ///     }
   ///   }
   ///
   /// Since A[i] and A[i-1] are independent pointers, getUnderlyingObjects
   /// should not assume that Curr and Prev share the same underlying object thus
-  /// it shouldn't look through the phi above.
+  /// it shouldn't look through the phi above. If a NoAlias vector is provided,
+  /// it is filled with any llvm.noalias intrinsics looked through to find the
+  /// underlying objects.
   void GetUnderlyingObjects(Value *V, SmallVectorImpl<Value *> &Objects,
                             const DataLayout &DL, LoopInfo *LI = nullptr,
-                            unsigned MaxLookup = 6);
+                            unsigned MaxLookup = 6,
+                            SmallVectorImpl<Instruction *> *NoAlias = nullptr);
 
   /// Return true if the only users of this pointer are lifetime markers.
   bool onlyUsedByLifetimeMarkers(const Value *V);
 
   /// Return true if the instruction does not have any effects besides
   /// calculating the result and does not have undefined behavior.
   ///
   /// This method never returns true for an instruction that returns true for

lib/Analysis/ValueTracking.cpp

static bool isSameUnderlyingObjectInLoop(const PHINode *PN,
   //       ...
   if (auto *Load = dyn_cast<LoadInst>(PrevValue))
     if (!L->isLoopInvariant(Load->getPointerOperand()))
       return false;
   return true;
 }
 
 Value *llvm::GetUnderlyingObject(Value *V, const DataLayout &DL,
-                                 unsigned MaxLookup) {
+                                 unsigned MaxLookup,
+                                 SmallVectorImpl<Instruction *> *NoAlias) {
   if (!V->getType()->isPointerTy())
     return V;
   for (unsigned Count = 0; MaxLookup == 0 || Count < MaxLookup; ++Count) {
     if (GEPOperator *GEP = dyn_cast<GEPOperator>(V)) {
       V = GEP->getPointerOperand();
     } else if (Operator::getOpcode(V) == Instruction::BitCast ||
                Operator::getOpcode(V) == Instruction::AddrSpaceCast) {
       V = cast<Operator>(V)->getOperand(0);
     } else if (GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) {
       if (GA->isInterposable())
         return V;
       V = GA->getAliasee();
     } else {
+      if (auto *I = dyn_cast<IntrinsicInst>(V))
+        if (I->getIntrinsicID() == Intrinsic::noalias) {
+          if (NoAlias)
+            NoAlias->push_back(I);
+        }
+
       if (auto CS = CallSite(V))
         if (Value *RV = CS.getReturnedArgOperand()) {
           V = RV;
           continue;
         }
 
       // See if InstructionSimplify knows any relevant tricks.
       if (Instruction *I = dyn_cast<Instruction>(V))
         // TODO: Acquire a DominatorTree and AssumptionCache and use them.
         if (Value *Simplified = SimplifyInstruction(I, DL, nullptr)) {
           V = Simplified;
           continue;
         }
 
       return V;
     }
     assert(V->getType()->isPointerTy() && "Unexpected operand type!");
   }
   return V;
 }
 
 void llvm::GetUnderlyingObjects(Value *V, SmallVectorImpl<Value *> &Objects,
                                 const DataLayout &DL, LoopInfo *LI,
-                                unsigned MaxLookup) {
+                                unsigned MaxLookup,
+                                SmallVectorImpl<Instruction *> *NoAlias) {
   SmallPtrSet<Value *, 4> Visited;
   SmallVector<Value *, 4> Worklist;
   Worklist.push_back(V);
   do {
     Value *P = Worklist.pop_back_val();
-    P = GetUnderlyingObject(P, DL, MaxLookup);
+    P = GetUnderlyingObject(P, DL, MaxLookup, NoAlias);
 
     if (!Visited.insert(P).second)
       continue;
 
     if (SelectInst *SI = dyn_cast<SelectInst>(P)) {
       Worklist.push_back(SI->getTrueValue());
       Worklist.push_back(SI->getFalseValue());
       continue;