[ptr_provenance] Introduce optional ptr_provenance operand to load/store

[jeroen.dobbelaere]

Summary

This patch introduces an optional ptr_provenance operand to LoadInst and the StoreInst.

This allows to separate the provenance of the pointer operand from the value of the pointer operand.

This is needed by the full restrict patched (D68484), but will be also useful to resolve problems with
optimizations that, by replacing the pointer operand with an equivalent computation, also happen to
replace its provenance. At the same time, it can speed up some alias analysis phases, as, for the
ptr_provenance path, we can skip most of the computations.

Notes:

• This patch corresponds to D68488 from the original Full Restrict series.
• For the specification, a UnknownProvenance provenance can be treated as indicating that it can correspond to any object.
• For the Load and Store instructions, the absence of the ptr_provenance operand is an indication the we should look at the pointer operand to track the provenance.
• When cloning a load/store instruction that has a separate ptr_provenance, the ptr_provenance of the clone is set to 'UnknownProvenance'. When that is not wanted, it must be modified explicitely.
  • Note: this results in a different behavior when the original instruction has a ptr_provenance that is identical to the ptr, vs an instruction without the ptr_provenance.

[jeroen.dobbelaere]

I also plan to add patches for:

• fixing the handling of load/store instructions in various places where a single (for load) or double operands (for store) are assumed.
• introduction of an intrinsic that combines the pointer provenance with the pointer value (Corresponding to the llvm.noalias.arg.guard in D68487)

[jeroen.dobbelaere]

• Rebased
• Use a ConstantPointerNull when cloning a load/store instruction with a ptr_provenance.

[jeroen.dobbelaere]

Compile time impact: https://llvm-compile-time-tracker.com/index.php?config=NewPM-O3&stat=instructions&branch=dobbelaj-snps/perf/ptr_provenance-20210803-03

[jeroen.dobbelaere]

• rebase
• make use of UnknownProvenance

[jeroen.dobbelaere]

Compile time impact: https://llvm-compile-time-tracker.com/index.php?config=NewPM-O3&stat=instructions&branch=dobbelaj-snps/perf/ptr_provenance-20211005-04

[jeroen.dobbelaere]

LangRef update. Refer to `unknown_provenance` now.

[asbirlea]

Adding a few items/questions discussed in the open meeting:

• Clarified item: If a load/store has 2/3 operands out of which only 1/2 are used, these operands are stored in the last position(s). So when adding provenance, the current operands need to be shifted to the first position(s) and the provenance added as the last operand.
• Discussion on why is cloning a load/store setting the ptr_provenance to unknown_provenance? When cloning a load/store instruction, the cloned instruction needs to have the same number of operands. Otherwise crashes were observed in some passes (example given: LoopVectorization). Why can't the number of operands remain the same, but set the ptr_provenance to the (otherwise default) ptr_operand?

@jeroen.dobbelaere: Could you describe using unknown for the cloning question for future reference?

[jeroen.dobbelaere]

In D104268#3107611, @asbirlea wrote:

• Clarified item: If a load/store has 2/3 operands out of which only 1/2 are used, these operands are stored in the last position(s). So when adding provenance, the current operands need to be shifted to the first position(s) and the provenance added as the last operand.

There are a number of implementations possible for adding an optional argument. They all share that at some moment, they need to know the actual
number of arguments in use. Depending on the implementation, those moments can differ.

It is also important to know that the operands are stored _before_ the this pointer. (See implementation of getIntrusiveOperands())
In order to get to the location of the first operand, we subtract NumUserOperands from this.

The original (obsolete) implementation (variant 0) always reserves the optional argument. The reserved amount of operands is stored in NumUserOperands,
and an extra bit 'NumUserOperandsDelta' was used when we need to know the actual number of operands.

The main issue with variant 0, is that it introduces and extra bit extract + addition in a number of common operations. Not just for load/store instructions, but for all instructions.
This has a measurable compile time impact :(

The split-up compile time impact (and patches) of variant0 can be found here:
https://llvm-compile-time-tracker.com/index.php?config=NewPM-O3&stat=instructions&branch=dobbelaj-snps/perf/test_instructions_20200907-01

So, I came up with 2 other variants that can be seen here:
https://llvm-compile-time-tracker.com/index.php?config=NewPM-O3&stat=instructions&branch=dobbelaj-snps/perf/test_instructions_20200907-02

variant 1: This variant also always reserves the optional argument. But now, NumUserOperands tracks the actual number of operands in use.
As getIntrusiveOperands() uses NumUserOperands() to find back the location of the first operand, we now have a problem when introducing (or removing)
the ptr_provenance operand: when changing NumUserOperands, suddenly all operands are shifted. Because of this behavior, the code for
adding (removing) the operand is slightly more complex, as it is also moving around the operands to compensate for the shifting behavior.

The big benefit is that we now only pay this penalty when using the new operand. So, variant 1 only has a minor compile time impact.

Then I also tried out variant 2. This is similar to variant 1, but they introduce a separate version of Load (and Store) with or without memory
space for the optional argument. The main benefit is that, if the ptr_provenance is never used, no space is reserved for it. But, the initial switching from
a 'standard' Load/Store to a 'Load/Store with optional ptr_provance support' is a lot higher and maintaining the correct usage of the instructions is also
more complex, which tend to result in more subtle errors.

Looking at the compile time and heap impact, and the potential maintenance issues, I settled on using variant 1, which is also the version implemented in this review.

[jeroen.dobbelaere]

In D104268#3107611, @asbirlea wrote:

• Discussion on why is cloning a load/store setting the ptr_provenance to unknown_provenance? When cloning a load/store instruction, the cloned instruction needs to have the same number of operands. Otherwise crashes were observed in some passes (example given: LoopVectorization). Why can't the number of operands remain the same, but set the ptr_provenance to the (otherwise default) ptr_operand?

@jeroen.dobbelaere: Could you describe using unknown for the cloning question for future reference?

One of the goals when introducing the optional parameter, was to reduce the impact on existing code/optimizations as much as possible. When cloning the instruction there are 5 possible cases to be considered:

1. omit (=do not clone) the ptr_provenance operand. This resulted in problems, as now, the number of operands between the original and the cloned instruction can differ.
2. clone the ptr_provenance operand when available. This resulted in dominance violations for some optimization passes that are not aware of the provenance operand.
3. When available, replace the ptr_provenance with the 'pointer' operand in the clone. This results in an extra use of the pointer operand, potentially resulting in worse code for optimizations depending on 'hasOneUse()'.
4. When available, replace the ptr_provenance with undef in the clone. (Special value for the original Full Restrict)
5. When available, replace the ptr_provenance with unknown_provenance in the clone.

In the original full restrict patches, (4) is done, as this (together with not copying !noalias metadata) resulted in the safest approach. A undef ptr_provenance is treated there as: look at the pointer operand for the provenance, aka similar to omitting the ptr_provenance, without actually doing it (1), and also similar to (3), but without introducing an extra 'use' on the pointer operand.

When preparing this part of the infrastructure, I wanted to take into account a more generic usage of the ptr_provenance infrastructure. For that, a special constant unknown_provenance is introduced. This indicates that, for the cloned access, we don't know the ptr_provenance (and associated noalias annotations). We can also not depend on the pointer operand for the provenance, as the pointer value can have a different provenance (!). Only when the optimization pass that is introducing the clone is aware of the ptr_provenance operand, the right decision can be taken, which can result in better code. So, (5) is the safe approach with minimal impact on existing code.

[asbirlea]

Thank you for all the clarifications. I'm convinced this is the right way to move forward at this point.

To add a note from offline discussions: the correct options when cloning are either unknown provenance, like in this patch, where it's possible for some optimizations to be missed, or cloning the ptr_provenance and resolving the dominance (and other?) issues in all passes (that move instructions, but probably not limited to these).
It is not correct to use the ptr_operand: with ptr_provenance, the issue described in https://bugs.llvm.org/show_bug.cgi?id=34548#c93 would be resolved, but not if a clone would go back to using the ptr_operand.

[nikic]

It's been a while since I looked at this, so please excuse the stupid question...

Why do we model provenance as an additional value on the load/store? Naively, I would think that it would be preferable to have an intrinsic like p' = llvm.with.provenance(p, provenance), because that would work with any use of the pointer -- the ptr_provenance operand is limited to loads and stores, but not with memory-accessing calls or captured pointers, and I don't think it can really be extended in that direction.

[jeroen.dobbelaere]

In D104268#3266800, @nikic wrote:

It's been a while since I looked at this, so please excuse the stupid question...

Why do we model provenance as an additional value on the load/store? Naively, I would think that it would be preferable to have an intrinsic like p' = llvm.with.provenance(p, provenance), because that would work with any use of the pointer -- the ptr_provenance operand is limited to loads and stores, but not with memory-accessing calls or captured pointers, and I don't think it can really be extended in that direction.

Hi Nikita,

my talk on the 2021 LLVM Dev Conference explains this. See https://www.youtube.com/watch?v=08XwXB3GHck 2021 LLVM Dev Mtg “ptr_provenance and @llvm.noalias: The Tale of Full Restrict”

In short:

• there is the llvm.with.provenance(p, provenance) equivalent intrinsic: it is called llvm.experimental.ptr.provenance (see D107355)
• load/store instructions are handled differently, mostly to make the process more efficient and to make the new support easier to integrate with existing optimization passes. Those that just replace the pointer computation won't influence the provenance (once that is set).

[nikic]

In D104268#3266830, @jeroen.dobbelaere wrote:

In D104268#3266800, @nikic wrote:

It's been a while since I looked at this, so please excuse the stupid question...

Why do we model provenance as an additional value on the load/store? Naively, I would think that it would be preferable to have an intrinsic like p' = llvm.with.provenance(p, provenance), because that would work with any use of the pointer -- the ptr_provenance operand is limited to loads and stores, but not with memory-accessing calls or captured pointers, and I don't think it can really be extended in that direction.

Hi Nikita,

my talk on the 2021 LLVM Dev Conference explains this. See https://www.youtube.com/watch?v=08XwXB3GHck 2021 LLVM Dev Mtg “ptr_provenance and @llvm.noalias: The Tale of Full Restrict”

In short:

• there is the llvm.with.provenance(p, provenance) equivalent intrinsic: it is called llvm.experimental.ptr.provenance (see D107355)
• load/store instructions are handled differently, mostly to make the process more efficient and to make the new support easier to integrate with existing optimization passes. Those that just replace the pointer computation won't influence the provenance (once that is set).

Thanks! So the ptr_provenance is just an optimized representation of the intrinsic, that makes sense.

Have you considered inverting this patch stack and landing the intrinsic first, as that part seems more straightforward than the IR change? I have a suspicion that actually supporting independent address + provenance will require some significant work for various users of getUnderlyingObject(), which may not account for the possibility of address and provenance being different. Updating all users seems like something we can do using just the intrinsic.

[jeroen.dobbelaere]

In D104268#3268608, @nikic wrote:

Have you considered inverting this patch stack and landing the intrinsic first, as that part seems more straightforward than the IR change? I have a suspicion that actually supporting independent address + provenance will require some significant work for various users of getUnderlyingObject(), which may not account for the possibility of address and provenance being different. Updating all users seems like something we can do using just the intrinsic.

It should be possible, but I am not sure it makes a lot of sense: Looking at the big picture, this proposed set of patches for providing ptr_provenance is a logical next step. My intention is that these patches only go in once all of them have been reviewed and accepted. At that time the basic infrastructure is available for the full restrict patches, which means that the next steps will start making use of this basic infrastructure.
The current users of the 'GetUnderlyingObject' can keep their behavior (for now), being: look for the underlying object following the computational path of the pointer. With more actual usage of the ptr_provenance, some of those GetUnderlyingObject users can switch to the provenance path, which should result in a speedup.
The more tricky changes are related to some of the bugs where the provenance of pointers gets switched and to N2676. Once the base infrastructure is there, we can also fix those.

[jeroen.dobbelaere]

Rebase to 49cb4fef02e635bf304906232214166c7531d753

[jeroen.dobbelaere]

Rebased to ffe262a198a9f9030991df6d3ddd812e74fa3523

[jeroen.dobbelaere]

Ping - Anyone who can help reviewing this ?

[jdoerfert]

LG overall. Comments seem to be fine with this as well. Some nits on the style and order, can be addressed before the merge.

llvm/docs/LangRef.rst

10308

ptr_provenance is after syncscope in the ASM printer, also for loads. I would put ptr_provenance in the end honestly.

llvm/include/llvm/IR/Instructions.h

305

No else after return

465–466

Nit: No else after return.

llvm/lib/IR/Instructions.cpp

1611

1705

[RalfJung]

llvm/docs/LangRef.rst

10196–10199

Rust and C also have a notion of "pointer provenance", but it is subtly difference: provenance in those languages is something that flows with pointer values. IOW, a value of pointer type consists of some address in memory, plus some "provenance" metadata. LLVM also has that kind of provenance, it is needed e.g. to explain some of the behavior of getelementptr. (A pointer returned by getelementptr without inbounds can go out-of-bounds but must not be used to access memory outside the bounds of the allocation it started with. In other words, the pointer "remembers" the allocation it is associated with in some way that is separate from the integer address it points to.)

Is it a good idea to use the same term for this slightly different concept? A load operation already receives provenance from its pointer argument, and now with this patchset it *also* receives something else, but also called provenance, via a separate argument.

[RalfJung]

llvm/docs/LangRef.rst

646–648

This is confusing, what does it mean that "computations can be omitted"? Computations *that do not alter provenance* can be omitted, sure -- for example getelementptr. But other operations could affect provenance and those are still relevant. (E.g., passing a pointer to a function as a noalias argument gives it a fresh distinct provenance, so such a computation/operation cannot be omitted even on the provenance path.)

Provenance is an inherent part of a value of pointer type, as far as correctness arguments for LLVM analyses and transformations go. Trying to treat it as any less real than the directly observable bits and bytes will only lead to trouble such as https://github.com/llvm/llvm-project/issues/34577.

652–653

In particular this sounds just wrong, if ptr_provenance is merely sugar for a "combine address with provenance" intrinsic: if ptr_provenance is present, it would be a bug for alias analysis to make any conclusions based on the provenance of the pointer argument.

10196–10199

(replying to my own comment after realizing there was prior discussion on that topic here -- sorry, I am completely lost in all this "patch stack" business)

So the ptr_provenance is just an optimized representation of the intrinsic, that makes sense.

Okay so sounds like this is supposed to completely override the provenance that comes with the pointer itself? Does that mean that it is now legal to do something like

• use getelementptr %ptr1 to compute some %ptr1a that is address-equal to some other %ptr2
• load %ptr1a ptr_provenance %ptr2_provenance

This would usually be UB if ptr2 points to a different allocation, since ptr1a is "based on" the wrong allocation.

In other words, when ptr_provenance is present, only the address of the pointer argument matters, and for everything else (including things like which allocation this pointer was "derived from"), only ptr_provenance matters?

[jeroen.dobbelaere]

Hi Ralph,

thanks for the feedback !

Greetings,

Jeroen

llvm/docs/LangRef.rst

646–648

This is confusing, what does it mean that "computations can be omitted"?

This should indeed be: Computations that **do not change provenance** can be omitted.

652–653

Hmm. The wording seems to allow a misinterpretation. You cannot choose if the 'provenance' is that of the pointer computation or if it is the decoupled one. If the provenance is decoupled, that is what you need to use.

10196–10199

In other words, when ptr_provenance is present, only the address of the pointer argument matters, and for everything else (including things like which allocation this pointer was "derived from"), only ptr_provenance matters?

Yes. That is indeed the case.

Note that this is an extension from the original goal of the ptr_provenance. The original goal was to provide a path where restrict annotations were added so that those would not clobber the pointer value. In that world, the pointer value and ptr_provenance would come together again at some point. The extension allows to completely separate the pointer value and the ptr_provenance. This provides a solution to handle this kind of optimizations in a correct way.

[RalfJung]

llvm/docs/LangRef.rst

652–653

Okay, that makes sense. So the documentation should then clearly state that in the presence of ptr_provenance, alias analysis *must not* make any conclusions by checking that the ptr argument is "based on" -- only the integer address of that pointer must be used, no other attached information (such as noalias/getelementptr-induced restrictions).

It is hard to even precisely discuss this without documenting in more detail what the provenance model of LLVM is: that every value of pointer type comes with some extra "ghost state" attached to it, which is how restrictions such as "getelementptr stays in the bounds of its allocations" and noalias flow through the program; that that "ghost state" is preserved when the pointer is itself stored to memory and loaded back out of memory; that alias analysis uses this "ghost state" to determine that a certain load/store cannot alias with another. I think documenting this better will also help a lot to avoid issues that the lack of precision around pointer provenance has caused in the past. (This immediately raises some new questions, such as how that provenance of a pointer stored in memory interacts with low-level byte-manipulating memory accesses that read or write some or all of the bytes of that pointer. Over time the LangRef should give answers to all these questions, but even acknowledging these issues would already be a great step forward. I'm happy to share the state of that discussion in Rust in case people are interested; we thought about this quite a bit.)

[jeroen.dobbelaere]

Rebased to ef545ef62a833152d8975ff16333b57cc41befcc (Jan 9, 2023)

NOTE: still need to update to recent comments.

[jeroen.dobbelaere]

Rebased to: 8c7cfa357280dd93d33b10bbba0fe33797e27d63 (Feb 14, 2023)

llvm/docs/LangRef.rst

 key exception: the optimizer may not, in general, insert new dynamic
 occurrences of such casts.  If a new cast is inserted, the optimizer would
 need to either ensure that a) all possible values are valid, or b)
 appropriate fencing is inserted.  Since the appropriate fencing is
 implementation defined, the optimizer can't do the latter.  The former is
 challenging as many commonly expected properties, such as
 ``ptrtoint(v)-ptrtoint(v) == 0``, don't hold for non-integral types.
 
+.. _ptr_provenance:
+
+Pointer Provenance
+------------------
+
+Note: the introduction of pointer provenance is a work in progress, and should
+be considered experimental at this time.
+
+The provenance of a pointer identifies the possible objects to which that
+pointer can refer. The :ref:`Load<_i_load>` and :ref:`Store<_i_store>`
+instructions have an optional ``ptr_provenance`` operand. When this is set, the
+provenance is decoupled from the actual pointer computation. As computations
+are not needed to track the origin of a pointer, those can be omitted for the
+``ptr_provenance`` operand. Dependencies on ``PHI`` and ``select`` instructions
+can still be useful to accurately identify possible origins. Especially when
+later optimizations are able to reduce the set of possibilities.
+
+Alias analysis can make use of both, the computed pointer value and the
+provenance to come up with alias conclusions.
+
+An ``unknown_provenance`` pointer provenance value indicates that the origin is
+unknown, and that it can refer to any object. This special constant can only
+be used on the provenance path.
+
 .. _globalvars:
 
 Global Variables
 ----------------
 
 Global variables define regions of memory allocated at compilation time
 instead of run-time.
 

 '``load``' Instruction
 ^^^^^^^^^^^^^^^^^^^^^^
 
 Syntax:
 """""""
 
 ::
 
-      <result> = load [volatile] <ty>, ptr <pointer>[, align <alignment>][, !nontemporal !<nontemp_node>][, !invariant.load !<empty_node>][, !invariant.group !<empty_node>][, !nonnull !<empty_node>][, !dereferenceable !<deref_bytes_node>][, !dereferenceable_or_null !<deref_bytes_node>][, !align !<align_node>][, !noundef !<empty_node>]
-      <result> = load atomic [volatile] <ty>, ptr <pointer> [syncscope("<target-scope>")] <ordering>, align <alignment> [, !invariant.group !<empty_node>]
+      <result> = load [volatile] <ty>, ptr <pointer>[, ptr_provenance ptr <channel>][,align <alignment>][, !nontemporal !<nontemp_node>][, !invariant.load !<empty_node>][, !invariant.group !<empty_node>][, !nonnull !<empty_node>][, !dereferenceable !<deref_bytes_node>][, !dereferenceable_or_null !<deref_bytes_node>][, !align !<align_node>][, !noundef !<empty_node>]
+      <result> = load atomic [volatile] <ty>, ptr <pointer>[, ptr_provenance ptr <channel>] [syncscope("<target-scope>")] <ordering>, align <alignment> [, !invariant.group !<empty_node>]
       !<nontemp_node> = !{ i32 1 }
       !<empty_node> = !{}
       !<deref_bytes_node> = !{ i64 <dereferenceable_bytes> }
       !<align_node> = !{ i64 <value_alignment> }
 
 Overview:
 """""""""
 

 Atomic loads produce :ref:`defined <memmodel>` results when they may see
 multiple atomic stores. The type of the pointee must be an integer, pointer, or
 floating-point type whose bit width is a power of two greater than or equal to
 eight and less than or equal to a target-specific size limit.  ``align`` must be
 explicitly specified on atomic loads, and the load has undefined behavior if the
 alignment is not set to a value which is at least the size in bytes of the
 pointee. ``!nontemporal`` does not have any defined semantics for atomic loads.
 
+The optional ``ptr_provenance`` argument, when present, specifies a separate
+pointer provenance path for the ``pointer`` operand of the ``load`` instruction.
+See :ref:`Pointer Provenance<_ptr_provenance>`. When it is not present, the
+``pointer`` operand can be used for the pointer provenance.
+
 The optional constant ``align`` argument specifies the alignment of the
 operation (that is, the alignment of the memory address). It is the 
 responsibility of the code emitter to ensure that the alignment information is
 correct. Overestimating the alignment results in undefined behavior. 
 Underestimating the alignment may produce less efficient code. An alignment of
 1 is always safe. The maximum possible alignment is ``1 << 32``. An alignment 
 value higher than the size of the loaded type implies memory up to the
 alignment value bytes can be safely loaded without trapping in the default

 '``store``' Instruction
 ^^^^^^^^^^^^^^^^^^^^^^^
 
 Syntax:
 """""""
 
 ::
 
-      store [volatile] <ty> <value>, ptr <pointer>[, align <alignment>][, !nontemporal !<nontemp_node>][, !invariant.group !<empty_node>]        ; yields void
-      store atomic [volatile] <ty> <value>, ptr <pointer> [syncscope("<target-scope>")] <ordering>, align <alignment> [, !invariant.group !<empty_node>] ; yields void
+      store [volatile] <ty> <value>, ptr <pointer>[, ptr_provenance ptr <channel>][, align <alignment>][, !nontemporal !<nontemp_node>][, !invariant.group !<empty_node>]        ; yields void
+      store atomic [volatile] <ty> <value>, ptr <pointer>[, ptr_provenance ptr <channel>] [syncscope("<target-scope>")] <ordering>, align <alignment> [, !invariant.group !<empty_node>] ; yields void
       !<nontemp_node> = !{ i32 1 }
       !<empty_node> = !{}
 
 Overview:
 """""""""
 
 The '``store``' instruction is used to write to memory.
 

 Atomic loads produce :ref:`defined <memmodel>` results when they may see
 multiple atomic stores. The type of the pointee must be an integer, pointer, or
 floating-point type whose bit width is a power of two greater than or equal to
 eight and less than or equal to a target-specific size limit.  ``align`` must be
 explicitly specified on atomic stores, and the store has undefined behavior if
 the alignment is not set to a value which is at least the size in bytes of the
 pointee. ``!nontemporal`` does not have any defined semantics for atomic stores.
 
+The optional ``ptr_provenance`` argument, when present, specifies a separate
+pointer provenance path for the ``pointer`` operand of the ``store`` instruction.
+See :ref:`Pointer Provenance<_ptr_provenance>`. When it is not present, the
+``pointer`` operand can be used for the pointer provenance.
+
 The optional constant ``align`` argument specifies the alignment of the
 operation (that is, the alignment of the memory address). It is the 
 responsibility of the code emitter to ensure that the alignment information is
 correct. Overestimating the alignment results in undefined behavior. 
 Underestimating the alignment may produce less efficient code. An alignment of
 1 is always safe. The maximum possible alignment is ``1 << 32``. An alignment 
 value higher than the size of the loaded type implies memory up to the
 alignment value bytes can be safely loaded without trapping in the default

llvm/include/llvm/IR/InstVisitor.h

 #include "llvm/IR/Instruction.def"
 
   // Specific Instruction type classes... note that all of the casts are
   // necessary because we use the instruction classes as opaque types...
   //
   RetTy visitICmpInst(ICmpInst &I)                { DELEGATE(CmpInst);}
   RetTy visitFCmpInst(FCmpInst &I)                { DELEGATE(CmpInst);}
   RetTy visitAllocaInst(AllocaInst &I)            { DELEGATE(UnaryInstruction);}
-  RetTy visitLoadInst(LoadInst     &I)            { DELEGATE(UnaryInstruction);}
+  RetTy visitLoadInst(LoadInst &I)                { DELEGATE(Instruction); }
   RetTy visitStoreInst(StoreInst   &I)            { DELEGATE(Instruction);}
   RetTy visitAtomicCmpXchgInst(AtomicCmpXchgInst &I) { DELEGATE(Instruction);}
   RetTy visitAtomicRMWInst(AtomicRMWInst &I)      { DELEGATE(Instruction);}
   RetTy visitFenceInst(FenceInst   &I)            { DELEGATE(Instruction);}
   RetTy visitGetElementPtrInst(GetElementPtrInst &I){ DELEGATE(Instruction);}
   RetTy visitPHINode(PHINode       &I)            { DELEGATE(Instruction);}
   RetTy visitTruncInst(TruncInst &I)              { DELEGATE(CastInst);}
   RetTy visitZExtInst(ZExtInst &I)                { DELEGATE(CastInst);}

llvm/include/llvm/IR/Instructions.h

 };
 
 //===----------------------------------------------------------------------===//
 //                                LoadInst Class
 //===----------------------------------------------------------------------===//
 
 /// An instruction for reading from memory. This uses the SubclassData field in
 /// Value to store whether or not the load is volatile.
-class LoadInst : public UnaryInstruction {
+class LoadInst : public Instruction {
   using VolatileField = BoolBitfieldElementT<0>;
   using AlignmentField = AlignmentBitfieldElementT<VolatileField::NextBit>;
   using OrderingField = AtomicOrderingBitfieldElementT<AlignmentField::NextBit>;
   static_assert(
       Bitfield::areContiguous<VolatileField, AlignmentField, OrderingField>(),
       "Bitfields must be contiguous");
 
   void AssertOK();
public:
   LoadInst(Type *Ty, Value *Ptr, const Twine &NameStr, bool isVolatile,
            Align Align, AtomicOrdering Order,
            SyncScope::ID SSID = SyncScope::System,
            Instruction *InsertBefore = nullptr);
   LoadInst(Type *Ty, Value *Ptr, const Twine &NameStr, bool isVolatile,
            Align Align, AtomicOrdering Order, SyncScope::ID SSID,
            BasicBlock *InsertAtEnd);
 
+  ~LoadInst() {
+    setLoadInstNumOperands(2); // needed by operator delete
+  }
+  // allocate space for exactly two operands
+  void *operator new(size_t s) { return User::operator new(s, 2); }
+
+  /// Transparently provide more efficient getOperand methods.
+  DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value);
+
   /// Return true if this is a load from a volatile memory location.
   bool isVolatile() const { return getSubclassData<VolatileField>(); }
 
   /// Specify whether this is a volatile load or not.
   void setVolatile(bool V) { setSubclassData<VolatileField>(V); }
 
   /// Return the alignment of the access that is being performed.
   Align getAlign() const {
public:
   static unsigned getPointerOperandIndex() { return 0U; }
   Type *getPointerOperandType() const { return getPointerOperand()->getType(); }
 
   /// Returns the address space of the pointer operand.
   unsigned getPointerAddressSpace() const {
     return getPointerOperandType()->getPointerAddressSpace();
   }
 
+  bool hasPtrProvenanceOperand() const { return getNumOperands() == 2; }
+  Value *getPtrProvenanceOperand() const {
+    assert(hasPtrProvenanceOperand() && "we need a ptr_provenance");
+    return getOperand(1);
+  }
+  /// Returns the PtrProvenanceOperand when available, otherwise the
+  /// PointerOperand.
+  Value *getPtrProvenance() {
+    return hasPtrProvenanceOperand() ? getPtrProvenanceOperand()
+                                     : getPointerOperand();
+  }
+  const Value *getPtrProvenance() const {
+    return hasPtrProvenanceOperand() ? getPtrProvenanceOperand()
+                                     : getPointerOperand();
+  }
+  static unsigned getPtrProvenanceOperandIndex() { return 1U; }
+  void setPtrProvenanceOperand(Value *Provenance);
+  void removePtrProvenanceOperand();
+  std::optional<Value *> getOptionalPtrProvenance() const {
+    if (hasPtrProvenanceOperand())
+      return getPtrProvenanceOperand();
+    else
+      return std::nullopt;
+  }
   // Methods for support type inquiry through isa, cast, and dyn_cast:
   static bool classof(const Instruction *I) {
     return I->getOpcode() == Instruction::Load;
   }
   static bool classof(const Value *V) {
     return isa<Instruction>(V) && classof(cast<Instruction>(V));
   }
 
 private:
   // Shadow Instruction::setInstructionSubclassData with a private forwarding
   // method so that subclasses cannot accidentally use it.
   template <typename Bitfield>
   void setSubclassData(typename Bitfield::Type Value) {
     Instruction::setSubclassData<Bitfield>(Value);
   }
 
   /// The synchronization scope ID of this load instruction.  Not quite enough
   /// room in SubClassData for everything, so synchronization scope ID gets its
   /// own field.
   SyncScope::ID SSID;
 };
 
+template <>
+struct OperandTraits<LoadInst> : public VariadicOperandTraits<LoadInst, 1> {};
+
+DEFINE_TRANSPARENT_OPERAND_ACCESSORS(LoadInst, Value)
+
 //===----------------------------------------------------------------------===//
 //                                StoreInst Class
 //===----------------------------------------------------------------------===//
 
 /// An instruction for storing to memory.
 class StoreInst : public Instruction {
   using VolatileField = BoolBitfieldElementT<0>;
   using AlignmentField = AlignmentBitfieldElementT<VolatileField::NextBit>;
public:
   StoreInst(Value *Val, Value *Ptr, bool isVolatile, Align Align,
             BasicBlock *InsertAtEnd);
   StoreInst(Value *Val, Value *Ptr, bool isVolatile, Align Align,
             AtomicOrdering Order, SyncScope::ID SSID = SyncScope::System,
             Instruction *InsertBefore = nullptr);
   StoreInst(Value *Val, Value *Ptr, bool isVolatile, Align Align,
             AtomicOrdering Order, SyncScope::ID SSID, BasicBlock *InsertAtEnd);
 
-  // allocate space for exactly two operands
-  void *operator new(size_t S) { return User::operator new(S, 2); }
+  ~StoreInst() {
+    setStoreInstNumOperands(3); // needed by operator delete
+  }
+  // allocate space for exactly three operands
+  void *operator new(size_t S) { return User::operator new(S, 3); }
   void operator delete(void *Ptr) { User::operator delete(Ptr); }
 
   /// Return true if this is a store to a volatile memory location.
   bool isVolatile() const { return getSubclassData<VolatileField>(); }
 
   /// Specify whether this is a volatile store or not.
   void setVolatile(bool V) { setSubclassData<VolatileField>(V); }
 
public:
   static unsigned getPointerOperandIndex() { return 1U; }
   Type *getPointerOperandType() const { return getPointerOperand()->getType(); }
 
   /// Returns the address space of the pointer operand.
   unsigned getPointerAddressSpace() const {
     return getPointerOperandType()->getPointerAddressSpace();
   }
 
+  bool hasPtrProvenanceOperand() const { return getNumOperands() == 3; }
+  Value *getPtrProvenanceOperand() const {
+    assert(hasPtrProvenanceOperand() && "we need a ptr_provenance");
+    return getOperand(2);
+  }
+  /// Returns the PtrProvenanceOperand when available, otherwise the
+  /// PointerOperand.
+  Value *getPtrProvenance() {
+    return hasPtrProvenanceOperand() ? getPtrProvenanceOperand()
+                                     : getPointerOperand();
+  }
+  const Value *getPtrProvenance() const {
+    return hasPtrProvenanceOperand() ? getPtrProvenanceOperand()
+                                     : getPointerOperand();
+  }
+  static unsigned getPtrProvenanceOperandIndex() { return 2U; }
+  void setPtrProvenanceOperand(Value *Provenance);
+  void removePtrProvenanceOperand();
+  std::optional<Value *> getOptionalPtrProvenance() const {
+    if (hasPtrProvenanceOperand())
+      return getPtrProvenanceOperand();
+    else
+      return std::nullopt;
+  }
   // Methods for support type inquiry through isa, cast, and dyn_cast:
   static bool classof(const Instruction *I) {
     return I->getOpcode() == Instruction::Store;
   }
   static bool classof(const Value *V) {
     return isa<Instruction>(V) && classof(cast<Instruction>(V));
   }
 
 private:
   // Shadow Instruction::setInstructionSubclassData with a private forwarding
   // method so that subclasses cannot accidentally use it.
   template <typename Bitfield>
   void setSubclassData(typename Bitfield::Type Value) {
     Instruction::setSubclassData<Bitfield>(Value);
   }
 
   /// The synchronization scope ID of this store instruction.  Not quite enough
   /// room in SubClassData for everything, so synchronization scope ID gets its
   /// own field.
   SyncScope::ID SSID;
 };
 
 template <>
-struct OperandTraits<StoreInst> : public FixedNumOperandTraits<StoreInst, 2> {
-};
+struct OperandTraits<StoreInst> : public VariadicOperandTraits<StoreInst, 2> {};
 
 DEFINE_TRANSPARENT_OPERAND_ACCESSORS(StoreInst, Value)
 
 //===----------------------------------------------------------------------===//
 //                                FenceInst Class
 //===----------------------------------------------------------------------===//
 
 /// An instruction for ordering other memory operations.

llvm/include/llvm/IR/User.h

public:
   /// FIXME: As that the number of operands is used to find the start of
   /// the allocated memory in operator delete, we need to always think we have
   /// 1 operand before delete.
   void setGlobalVariableNumOperands(unsigned NumOps) {
     assert(NumOps <= 1 && "GlobalVariable can only have 0 or 1 operands");
     NumUserOperands = NumOps;
   }
 
+  /// FIXME: As the number of operands is used to find the start of the
+  /// allocated memory in operator delete, we need to always think we have 3
+  /// operands before delete.
+  void setStoreInstNumOperands(unsigned NumOps) {
+    assert((2 <= NumOps) && (NumOps <= 3) &&
+           "StoreInst can only have 2 or 3 operands");
+    NumUserOperands = NumOps;
+  }
+
+  /// FIXME: As the number of operands is used to find the start of the
+  /// allocated memory in operator delete, we need to always think we have 2
+  /// operands before delete.
+  void setLoadInstNumOperands(unsigned NumOps) {
+    assert((1 <= NumOps) && (NumOps <= 2) &&
+           "LoadInst can only have 1 or 2 operands");
+    NumUserOperands = NumOps;
+  }
+
   /// Subclasses with hung off uses need to manage the operand count
   /// themselves.  In these instances, the operand count isn't used to find the
   /// OperandList, so there's no issue in having the operand count change.
   void setNumHungOffUseOperands(unsigned NumOps) {
     assert(HasHungOffUses && "Must have hung off uses to use this method");
     assert(NumOps < (1u << NumUserOperandsBits) && "Too many operands");
     NumUserOperands = NumOps;
   }

llvm/lib/IR/AsmWriter.cpp

if (isa<BranchInst>(I) && cast<BranchInst>(I).isConditional()) {
     TypePrinter.print(I.getType(), Out);
   } else if (isa<VAArgInst>(I)) {
     if (Operand) {
       Out << ' ';
       writeOperand(Operand, true);   // Work with broken code
     }
     Out << ", ";
     TypePrinter.print(I.getType(), Out);
-  } else if (Operand) {   // Print the normal way.
+  } else if (const auto *LI = dyn_cast<LoadInst>(&I)) {
+    Out << ' ';
+    TypePrinter.print(LI->getType(), Out);
+    Out << ", ";
+    writeOperand(I.getOperand(0), true);
+  } else if (isa<StoreInst>(&I)) {
+    Out << ' ';
+    writeOperand(I.getOperand(0), true);
+    Out << ", ";
+    writeOperand(I.getOperand(1), true);
+  } else if (Operand) { // Print the normal way.
     if (const auto *GEP = dyn_cast<GetElementPtrInst>(&I)) {
       Out << ' ';
       TypePrinter.print(GEP->getSourceElementType(), Out);
       Out << ',';
-    } else if (const auto *LI = dyn_cast<LoadInst>(&I)) {
-      Out << ' ';
-      TypePrinter.print(LI->getType(), Out);
-      Out << ',';
     }
 
     // PrintAllTypes - Instructions who have operands of all the same type
     // omit the type from all but the first operand.  If the instruction has
     // different type operands (for example br), then they are all printed.
     bool PrintAllTypes = false;
     Type *TheType = Operand->getType();
 
for (unsigned i = 0, E = I.getNumOperands(); i != E; ++i) {
       writeOperand(I.getOperand(i), PrintAllTypes);
     }
   }
 
   // Print atomic ordering/alignment for memory operations
   if (const LoadInst *LI = dyn_cast<LoadInst>(&I)) {
     if (LI->isAtomic())
       writeAtomic(LI->getContext(), LI->getOrdering(), LI->getSyncScopeID());
+    if (LI->hasPtrProvenanceOperand()) {
+      Out << ", ptr_provenance ";
+      writeOperand(LI->getPtrProvenanceOperand(), true);
+    }
     if (MaybeAlign A = LI->getAlign())
       Out << ", align " << A->value();
   } else if (const StoreInst *SI = dyn_cast<StoreInst>(&I)) {
     if (SI->isAtomic())
       writeAtomic(SI->getContext(), SI->getOrdering(), SI->getSyncScopeID());
+    if (SI->hasPtrProvenanceOperand()) {
+      Out << ", ptr_provenance ";
+      writeOperand(SI->getPtrProvenanceOperand(), true);
+    }
     if (MaybeAlign A = SI->getAlign())
       Out << ", align " << A->value();
   } else if (const AtomicCmpXchgInst *CXI = dyn_cast<AtomicCmpXchgInst>(&I)) {
     writeAtomicCmpXchg(CXI->getContext(), CXI->getSuccessOrdering(),
                        CXI->getFailureOrdering(), CXI->getSyncScopeID());
     Out << ", align " << CXI->getAlign().value();
   } else if (const AtomicRMWInst *RMWI = dyn_cast<AtomicRMWInst>(&I)) {
     writeAtomic(RMWI->getContext(), RMWI->getOrdering(),

llvm/lib/IR/Instructions.cpp

 
 //===----------------------------------------------------------------------===//
 //                           LoadInst Implementation
 //===----------------------------------------------------------------------===//
 
 void LoadInst::AssertOK() {
   assert(getOperand(0)->getType()->isPointerTy() &&
          "Ptr must have pointer type.");
+  assert((!hasPtrProvenanceOperand() || getOperand(1)) &&
+         "ptr_provenance must be non-null");
+  assert((!hasPtrProvenanceOperand() ||
+          (getOperand(0)->getType() == getOperand(1)->getType())) &&
+         "ptr_provenance must have the same type as the pointer");
 }
 
 static Align computeLoadStoreDefaultAlign(Type *Ty, BasicBlock *BB) {
   assert(BB && "Insertion BB cannot be null when alignment not provided!");
   assert(BB->getParent() &&
          "BB must be in a Function when alignment not provided!");
   const DataLayout &DL = BB->getModule()->getDataLayout();
   return DL.getABITypeAlign(Ty);

 LoadInst::LoadInst(Type *Ty, Value *Ptr, const Twine &Name, bool isVolatile,
                    Align Align, BasicBlock *InsertAE)
     : LoadInst(Ty, Ptr, Name, isVolatile, Align, AtomicOrdering::NotAtomic,
                SyncScope::System, InsertAE) {}
 
 LoadInst::LoadInst(Type *Ty, Value *Ptr, const Twine &Name, bool isVolatile,
                    Align Align, AtomicOrdering Order, SyncScope::ID SSID,
                    Instruction *InsertBef)
-    : UnaryInstruction(Ty, Load, Ptr, InsertBef) {
+    : Instruction(Ty, Load, OperandTraits<LoadInst>::op_end(this) - 2, 2,
+                  InsertBef) {
   assert(cast<PointerType>(Ptr->getType())->isOpaqueOrPointeeTypeMatches(Ty));
+  setLoadInstNumOperands(1);
+  Op<0>() = Ptr;
   setVolatile(isVolatile);
   setAlignment(Align);
   setAtomic(Order, SSID);
   AssertOK();
   setName(Name);
 }
 
 LoadInst::LoadInst(Type *Ty, Value *Ptr, const Twine &Name, bool isVolatile,
                    Align Align, AtomicOrdering Order, SyncScope::ID SSID,
                    BasicBlock *InsertAE)
-    : UnaryInstruction(Ty, Load, Ptr, InsertAE) {
+    : Instruction(Ty, Load, OperandTraits<LoadInst>::op_end(this) - 2, 2,
+                  InsertAE) {
+  setLoadInstNumOperands(1);
+  Op<0>() = Ptr;
   assert(cast<PointerType>(Ptr->getType())->isOpaqueOrPointeeTypeMatches(Ty));
   setVolatile(isVolatile);
   setAlignment(Align);
   setAtomic(Order, SSID);
   AssertOK();
   setName(Name);
 }
 
+void LoadInst::setPtrProvenanceOperand(llvm::LoadInst::Value *Provenance) {
+  assert(Provenance && "Needs a provenance");
+  if (!hasPtrProvenanceOperand()) {
+    setLoadInstNumOperands(2);
+    // shift operands
+    setOperand(0, getOperand(1));
+  }
+  setOperand(1, Provenance);
+  AssertOK();
+}
+
+void LoadInst::removePtrProvenanceOperand() {
+  assert(hasPtrProvenanceOperand() && "nothing to remove");
+  // shift operands
+  setOperand(1, getOperand(0));
+  setOperand(0, nullptr);
+  setLoadInstNumOperands(1);
+  AssertOK();
+}
+
 //===----------------------------------------------------------------------===//
 //                           StoreInst Implementation
 //===----------------------------------------------------------------------===//
 
 void StoreInst::AssertOK() {
   assert(getOperand(0) && getOperand(1) && "Both operands must be non-null!");
   assert(getOperand(1)->getType()->isPointerTy() &&
          "Ptr must have pointer type!");
   assert(cast<PointerType>(getOperand(1)->getType())
              ->isOpaqueOrPointeeTypeMatches(getOperand(0)->getType()) &&
          "Ptr must be a pointer to Val type!");
+  assert((!hasPtrProvenanceOperand() || getOperand(2)) &&
+         "ptr_provenance must be non-null");
+  assert((!hasPtrProvenanceOperand() ||
+          (getOperand(1)->getType() == getOperand(2)->getType())) &&
+         "ptr_provenance must have the same type as the pointer");
 }
 
 StoreInst::StoreInst(Value *val, Value *addr, Instruction *InsertBefore)
     : StoreInst(val, addr, /*isVolatile=*/false, InsertBefore) {}
 
 StoreInst::StoreInst(Value *val, Value *addr, BasicBlock *InsertAtEnd)
     : StoreInst(val, addr, /*isVolatile=*/false, InsertAtEnd) {}
 
StoreInst::StoreInst(Value *val, Value *addr, bool isVolatile, Align Align,
                      BasicBlock *InsertAtEnd)
     : StoreInst(val, addr, isVolatile, Align, AtomicOrdering::NotAtomic,
                 SyncScope::System, InsertAtEnd) {}
 
 StoreInst::StoreInst(Value *val, Value *addr, bool isVolatile, Align Align,
                      AtomicOrdering Order, SyncScope::ID SSID,
                      Instruction *InsertBefore)
     : Instruction(Type::getVoidTy(val->getContext()), Store,
-                  OperandTraits<StoreInst>::op_begin(this),
-                  OperandTraits<StoreInst>::operands(this), InsertBefore) {
+                  OperandTraits<StoreInst>::op_end(this) - 3, 3, InsertBefore) {
+  setStoreInstNumOperands(2);
   Op<0>() = val;
   Op<1>() = addr;
   setVolatile(isVolatile);
   setAlignment(Align);
   setAtomic(Order, SSID);
   AssertOK();
 }
 
 StoreInst::StoreInst(Value *val, Value *addr, bool isVolatile, Align Align,
                      AtomicOrdering Order, SyncScope::ID SSID,
                      BasicBlock *InsertAtEnd)
     : Instruction(Type::getVoidTy(val->getContext()), Store,
-                  OperandTraits<StoreInst>::op_begin(this),
-                  OperandTraits<StoreInst>::operands(this), InsertAtEnd) {
+                  OperandTraits<StoreInst>::op_end(this) - 3, 3, InsertAtEnd) {
+  setStoreInstNumOperands(2);
   Op<0>() = val;
   Op<1>() = addr;
   setVolatile(isVolatile);
   setAlignment(Align);
   setAtomic(Order, SSID);
   AssertOK();
 }
 
+void StoreInst::setPtrProvenanceOperand(llvm::StoreInst::Value *Provenance) {
+  assert(Provenance && "Needs a provenance");
+  if (!hasPtrProvenanceOperand()) {
+    setStoreInstNumOperands(3);
+    // shift uses; FIXME: can be made faster ?
+    setOperand(0, getOperand(1));
+    setOperand(1, getOperand(2));
+  }
+  setOperand(2, Provenance);
+  AssertOK();
+}
+
+void StoreInst::removePtrProvenanceOperand() {
+  assert(hasPtrProvenanceOperand() && "nothing to remove");
+  // make sure 'uses' are updated
+  setOperand(2, getOperand(1));
+  setOperand(1, getOperand(0));
+  setOperand(0, nullptr);
+
+  setStoreInstNumOperands(2);
+  AssertOK();
+}
 
 //===----------------------------------------------------------------------===//
 //                       AtomicCmpXchgInst Implementation
 //===----------------------------------------------------------------------===//
 
 void AtomicCmpXchgInst::Init(Value *Ptr, Value *Cmp, Value *NewVal,
                              Align Alignment, AtomicOrdering SuccessOrdering,
                              AtomicOrdering FailureOrdering,
AllocaInst *AllocaInst::cloneImpl() const {
   AllocaInst *Result = new AllocaInst(getAllocatedType(), getAddressSpace(),
                                       getOperand(0), getAlign());
   Result->setUsedWithInAlloca(isUsedWithInAlloca());
   Result->setSwiftError(isSwiftError());
   return Result;
 }
 
 LoadInst *LoadInst::cloneImpl() const {
-  return new LoadInst(getType(), getOperand(0), Twine(), isVolatile(),
-                      getAlign(), getOrdering(), getSyncScopeID());
+  LoadInst *Result =
+      new LoadInst(getType(), getOperand(0), Twine(), isVolatile(), getAlign(),
+                   getOrdering(), getSyncScopeID());
+  // - we must keep the same number of arguments (for vector optimizations)
+  // - if we duplicate the provenance, we can get into problems with passes
+  //   that don't know how to handle it (Like MergeLoadStoreMotion shows)
+  // - safe alternative: keep the argument, but map it to unknown_provenance.
+  if (hasPtrProvenanceOperand())
+    Result->setPtrProvenanceOperand(UnknownProvenance::get(
+        cast<PointerType>(getPtrProvenanceOperand()->getType())));
+  return Result;
 }
 
 StoreInst *StoreInst::cloneImpl() const {
-  return new StoreInst(getOperand(0), getOperand(1), isVolatile(), getAlign(),
-                       getOrdering(), getSyncScopeID());
+  StoreInst *Result =
+      new StoreInst(getOperand(0), getOperand(1), isVolatile(), getAlign(),
+
+  // we must keep the same number of arguments (for vector optimizations)
+  // - if we duplicate the provenance, we can get into problems with passes
+  //   that don't know how to handle it (Like MergeLoadStoreMotion shows)
+  // - safe alternative: keep the argument, but map it to unknown_provenance.
+  if (hasPtrProvenanceOperand())
+    Result->setPtrProvenanceOperand(UnknownProvenance::get(
+        cast<PointerType>(getPtrProvenanceOperand()->getType())));
+  return Result;
 }
 
 AtomicCmpXchgInst *AtomicCmpXchgInst::cloneImpl() const {
   AtomicCmpXchgInst *Result = new AtomicCmpXchgInst(
       getOperand(0), getOperand(1), getOperand(2), getAlign(),
       getSuccessOrdering(), getFailureOrdering(), getSyncScopeID());
   Result->setVolatile(isVolatile());
   Result->setWeak(isWeak());

llvm/unittests/IR/IRBuilderTest.cpp

TEST_F(IRBuilderTest, ConstrainedFPFunctionCall) {
   // Check the attributes to verify the strictfp attribute is on the call.
   EXPECT_TRUE(
       FCall->getAttributes().getFnAttrs().hasAttribute(Attribute::StrictFP));
 
   Builder.CreateRetVoid();
   EXPECT_FALSE(verifyModule(*M));
 }
 
+TEST_F(IRBuilderTest, PtrProvenanceLoadStore) {
+  IRBuilder<> Builder(BB);
+  auto *A = Builder.CreateAlloca(GV->getValueType());
+
+  auto *L = Builder.CreateLoad(GV->getValueType(), GV);
+  EXPECT_TRUE(!L->hasPtrProvenanceOperand());
+  EXPECT_EQ(L->getPtrProvenance(), GV);
+
+  auto *S = Builder.CreateStore(L, GV);
+  EXPECT_TRUE(!S->hasPtrProvenanceOperand());
+  EXPECT_EQ(S->getPtrProvenance(), GV);
+
+  L->setPtrProvenanceOperand(A);
+  EXPECT_TRUE(L->hasPtrProvenanceOperand());
+
+  S->setPtrProvenanceOperand(A);
+  EXPECT_TRUE(S->hasPtrProvenanceOperand());
+
+  EXPECT_EQ(L->getPtrProvenanceOperand(), A);
+  EXPECT_EQ(S->getPtrProvenanceOperand(), A);
+  EXPECT_EQ(L->getPtrProvenance(), A);
+  EXPECT_EQ(S->getPtrProvenance(), A);
+
+  L->removePtrProvenanceOperand();
+  EXPECT_TRUE(!L->hasPtrProvenanceOperand());
+
+  S->removePtrProvenanceOperand();
+  EXPECT_TRUE(!S->hasPtrProvenanceOperand());
+
+  EXPECT_EQ(L->getPtrProvenance(), GV);
+  EXPECT_EQ(S->getPtrProvenance(), GV);
+}
+
 TEST_F(IRBuilderTest, Lifetime) {
   IRBuilder<> Builder(BB);
   AllocaInst *Var1 = Builder.CreateAlloca(Builder.getInt8Ty());
   AllocaInst *Var2 = Builder.CreateAlloca(Builder.getInt32Ty());
   AllocaInst *Var3 = Builder.CreateAlloca(Builder.getInt8Ty(),
                                           Builder.getInt32(123));
 
   CallInst *Start1 = Builder.CreateLifetimeStart(Var1);