[getUnderlyingObject] support ptr_provenance

[jeroen.dobbelaere]

Summary

Allow to follow the pointer path through the computation operand 0 of llvm.experimental.ptr.provenance) or through the provenance (operand 1 of llvm.experimental.ptr.provenance).

Note: No further usage of this change is made at this moment. The BasicAliasAnalysis is mixing up the 'provenance' (as meant in ptr provenance and 'base' as where you end up when looking through the pointer computations. Any change there means choosing a policy (like explained in N2676 and others). At this moment, I am not sure what path to follow.

• For full restrict, the idea is that the ptr_provenance and the underlying object of the computation end up to be the same. For N2676 this is not necessarily the case. Also for fixing issues related to GVN optimizing pointers based on 'equality', but losing provenance by doing so, this will also change that assumption.

[jeroen.dobbelaere]

• Rebased
• Note: still need to update the (obsolete) comment

[jeroen.dobbelaere]

Refer to UnknownProvenance instead of ConstantPointerNull in comment of getUnderlyingObject.

[jeroen.dobbelaere]

Rebase to 49cb4fef02e635bf304906232214166c7531d753

[Zoxc]

It does kind of seem to me that getUnderlyingObject is intended to discover the provenance given that it discards GEPs. So always following the provenance path seems reasonable. However for full restrict the question to follow noalias intrinsics or not does appear to be more situational. So perhaps FollowProvenance should turn in to a FollowNoAlias argument?

[jdoerfert]

I think this is fine, we can argue about the name but it won't matter much. A test would be nice though.

[jeroen.dobbelaere]

Rebased to ffe262a198a9f9030991df6d3ddd812e74fa3523

[jeroen.dobbelaere]

Rebased to ef545ef62a833152d8975ff16333b57cc41befcc (Jan 9, 2023)

[asbirlea]

I'm ok to not bikeshed this one at this time :-).

[jeroen.dobbelaere]

Rebased to: 8c7cfa357280dd93d33b10bbba0fe33797e27d63 (Feb 14, 2023)

llvm/include/llvm/Analysis/ValueTracking.h

constexpr unsigned MaxAnalysisRecursionDepth = 6;
   /// the intrinsic must preserve the nullness of the pointer.
   bool isIntrinsicReturningPointerAliasingArgumentWithoutCapturing(
       const CallBase *Call, bool MustPreserveNullness);
 
   /// 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.
-  const Value *getUnderlyingObject(const Value *V, unsigned MaxLookup = 6);
-  inline Value *getUnderlyingObject(Value *V, unsigned MaxLookup = 6) {
+  /// be stripped off. When FollowProvenance is set, the provenance side of
+  /// llvm.experimental.ptr.provenance is taken. Be aware that for provenance,
+  /// a ConstantPointerNull indicates that any valid object can be the
+  /// underlying object.
+  const Value *getUnderlyingObject(const Value *V, unsigned MaxLookup = 6,
+                                   bool FollowProvenance = false);
+  inline Value *getUnderlyingObject(Value *V, unsigned MaxLookup = 6,
+                                    bool FollowProvenance = false) {
     // Force const to avoid infinite recursion.
     const Value *VConst = V;
     return const_cast<Value *>(getUnderlyingObject(VConst, MaxLookup));
   }
 
   /// This method is similar to getUnderlyingObject except that it can
   /// look through phi and select instructions and return multiple objects.
   ///
constexpr unsigned MaxAnalysisRecursionDepth = 6;
   ///     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.
+  /// When FollowProvenance is set, the provenance side of
+  /// llvm.experimental.ptr.provenance is taken.
   void getUnderlyingObjects(const Value *V,
                             SmallVectorImpl<const Value *> &Objects,
-                            LoopInfo *LI = nullptr, unsigned MaxLookup = 6);
+                            LoopInfo *LI = nullptr, unsigned MaxLookup = 6,
+                            bool FollowProvenance = false);
 
   /// This is a wrapper around getUnderlyingObjects and adds support for basic
   /// ptrtoint+arithmetic+inttoptr sequences.
   bool getUnderlyingObjectsForCodeGen(const Value *V,
                                       SmallVectorImpl<Value *> &Objects);
 
   /// Returns unique alloca where the value comes from, or nullptr.
   /// If OffsetZero is true check that V points to the begining of the alloca.

llvm/lib/Analysis/ValueTracking.cpp

static bool isSameUnderlyingObjectInLoop(const PHINode *PN,
   //       int *p = a[i];
   //       ...
   if (auto *Load = dyn_cast<LoadInst>(PrevValue))
     if (!L->isLoopInvariant(Load->getPointerOperand()))
       return false;
   return true;
 }
 
-const Value *llvm::getUnderlyingObject(const Value *V, unsigned MaxLookup) {
+const Value *llvm::getUnderlyingObject(const Value *V, unsigned MaxLookup,
+                                       bool FollowProvenance) {
   if (!V->getType()->isPointerTy())
     return V;
   for (unsigned Count = 0; MaxLookup == 0 || Count < MaxLookup; ++Count) {
     if (auto *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);
       if (!V->getType()->isPointerTy())
         return V;
     } else if (auto *GA = dyn_cast<GlobalAlias>(V)) {
       if (GA->isInterposable())
         return V;
       V = GA->getAliasee();
     } else {
       if (auto *PHI = dyn_cast<PHINode>(V)) {
         // Look through single-arg phi nodes created by LCSSA.
         if (PHI->getNumIncomingValues() == 1) {
           V = PHI->getIncomingValue(0);
           continue;
         }
       } else if (auto *Call = dyn_cast<CallBase>(V)) {
+        if (Call->getIntrinsicID() == Intrinsic::experimental_ptr_provenance) {
+          V = Call->getArgOperand(FollowProvenance ? 1 : 0);
+          continue;
+        }
+
         // CaptureTracking can know about special capturing properties of some
         // intrinsics like launder.invariant.group, that can't be expressed with
         // the attributes, but have properties like returning aliasing pointer.
         // Because some analysis may assume that nocaptured pointer is not
         // returned from some special intrinsic (because function would have to
         // be marked with returns attribute), it is crucial to use this function
         // because it should be in sync with CaptureTracking. Not using it may
         // cause weird miscompilations where 2 aliasing pointers are assumed to
         // noalias.
         if (auto *RP = getArgumentAliasingToReturnedPointer(Call, false)) {
           V = RP;
           continue;
         }
       }
 
       return V;
     }
     assert(V->getType()->isPointerTy() && "Unexpected operand type!");
   }
   return V;
 }
 
 void llvm::getUnderlyingObjects(const Value *V,
                                 SmallVectorImpl<const Value *> &Objects,
-                                LoopInfo *LI, unsigned MaxLookup) {
+                                LoopInfo *LI, unsigned MaxLookup,
+                                bool FollowProvenance) {
   SmallPtrSet<const Value *, 4> Visited;
   SmallVector<const Value *, 4> Worklist;
   Worklist.push_back(V);
   do {
     const Value *P = Worklist.pop_back_val();
-    P = getUnderlyingObject(P, MaxLookup);
+    P = getUnderlyingObject(P, MaxLookup, FollowProvenance);
 
     if (!Visited.insert(P).second)
       continue;
 
     if (auto *SI = dyn_cast<SelectInst>(P)) {
       Worklist.push_back(SI->getTrueValue());
       Worklist.push_back(SI->getFalseValue());
       continue;