[PATCH 03/27] [noalias] [IR] Introduce ptr_provenance for LoadInst/StoreInst

[jeroen.dobbelaere]

Summary

This is part of the series started by D68484.

The ptr_provenance parameter tracks dependencies on noalias intrinsics without
blocking optimizations on the pointer value.

Note: the space for the optional ptr_provenance argument will always be reserved for each LoadInst/StoreInst.

Note: this is a stable point and tests should run fine with the patches applied up to this point.

[lebedev.ri]

All that subtle magic about "we may have 2 operands but in some places we need to pretend that we have 3 operands" seems suboptimal to me.
Semantically, can we just always allocate space for 3 operands, but use either nullptr or undef as a magic to deduce whether we actually have the third operand?

llvm/include/llvm/IR/Instructions.h

313

assertion message missing

471

assertion message missing

[jeroen.dobbelaere]

In D68488#1696512, @lebedev.ri wrote:

All that subtle magic about "we may have 2 operands but in some places we need to pretend that we have 3 operands" seems suboptimal to me.
Semantically, can we just always allocate space for 3 operands, but use either nullptr or undef as a magic to deduce whether we actually have the third operand?

It is kind of magic and it took some time to get it right. The technique comes from GlobalVariable where there is either 0 or 1 operands.
There are 2 operands allocated for LoadInst, 3 for StoreInst. The challenge is that the operands are allocated before the instruction.
When the NumUserOperands changes, suddenly all operands are shifted. That is not convenient. That's why I choose to keep NumUserOperands constant, and to
add an extra 'delta'. Any better solution that works is welcome though.

[jeroen.dobbelaere]

Added assert message; clang-format

[a.elovikov]

llvm/lib/IR/Instructions.cpp

4427

Why is it safe? Consider we have aliasing load and store, we clone them so load.clone and load.store now have undef in the sidechannels, so optimizations are free to choose the values for them that would mean noalias.

[jeroen.dobbelaere]

llvm/lib/IR/Instructions.cpp

4427

• Undef is maybe the wrong value and could indeed trigger problems in future.
• null is not safe, as that is used to indicate a converted load/store instruction, when it does not depend on a restrict pointer (still in combination with the !noalias metadata, which must be present and indicate what scopes are visible)..
• Copying the noalias_sidechannel from the original is also not safe. It might not be valid in the new context.
• Removing the noalias_sidechannel (as was done in some earlier version) also does not work: some passes rightfully expect the clone to have the same number of arguments as the original.

[jeroen.dobbelaere]

Rebased

[jeroen.dobbelaere]

Rebased to c06b7e2ab5167ad031745a706204abed1aefd823 (July 14, 2020)

[jeroen.dobbelaere]

Rebased to 9fb46a452d4e5666828c95610ceac8dcd9e4ce16 (September 7, 2020)

[jeroen.dobbelaere]

The performance impact of different parts of this patch can be seen here: https://llvm-compile-time-tracker.com/index.php?branch=dobbelaj-snps/perf/test_instructions_20200907-01

• Introducing the 'NumUserOperandsDelta' has a measurable impact on the number of instructions as it affects every instruction. Maybe that can be avoided ?
• Introducing the optional extra argument for LoadInst/StoreInst has (as expected) some effect on the RSS.

[jeroen.dobbelaere]

I have 3 variants of this patch:

• variant 0 : always reserve place for the ptr_provenance; Introduce NumOfOperandsDelta to get the correct number of operands
  • extra space overhead for load/store instructions;
  • extra instruction overhead for ALL instructions ('getNumOperand()');
  • low overhead when adding/removing ptr_provenance
  • NOTE: this is the current provided patch
• variant 1 : always reserve place for the ptr_provenance; Move arguments around when adding/removing ptr_provenance
  • extra space overhead for load/store instructions;
  • NO impact on other instructions;
  • slightly more overhead when accessing operands of load/store instructions;
  • medium overhead when adding/removing ptr_provenance
• variant 2 : Have a LoadInst, LoadWithProvInst and StoreInst, StoreWithProvInst. Only the 'WithProv' variant reserves place for optional argument. When the ptr_provenance is added, it can involve creating a Load/StoreWithProv based on the original Load/Store. Adding/removing the ptr_provenance argument involves moving arguments around.
  • extra space only needed when we know we will need it.
  • NO impact on other instructions;
  • slightly more overhead when accessing operands of load/store instructions;
  • medium to high overhead when adding ptr_provenance. medium when removing it.
  • higher risk in keeping things correct in optimization: adding the ptr_provenance can require recreating the Load/Store instruction. This might be difficult if the optimization pass is tracking pointers to the original Load/Store instruction.
  • main benefit: almost no impact from this change if the feature is not used (aka -fno-full-restrict)

Any preference in the way forward ? variant 1 is the easy one, as it is just a drop-in. Variant 2 is at the moment less-stable as it requires changes in all optimization passes that need to track the ptr_provenance.

[lebedev.ri]

In D68488#2278602, @jeroen.dobbelaere wrote:

I have 3 variants of this patch:

• variant 0 : always reserve place for the ptr_provenance; Introduce NumOfOperandsDelta to get the correct number of operands
  • extra space overhead for load/store instructions;
  • extra instruction overhead for ALL instructions ('getNumOperand()');
  • low overhead when adding/removing ptr_provenance
  • NOTE: this is the current provided patch
• variant 1 : always reserve place for the ptr_provenance; Move arguments around when adding/removing ptr_provenance
  • extra space overhead for load/store instructions;
  • NO impact on other instructions;
  • slightly more overhead when accessing operands of load/store instructions;
  • medium overhead when adding/removing ptr_provenance
• variant 2 : Have a LoadInst, LoadWithProvInst and StoreInst, StoreWithProvInst. Only the 'WithProv' variant reserves place for optional argument. When the ptr_provenance is added, it can involve creating a Load/StoreWithProv based on the original Load/Store. Adding/removing the ptr_provenance argument involves moving arguments around.
  • extra space only needed when we know we will need it.
  • NO impact on other instructions;
  • slightly more overhead when accessing operands of load/store instructions;
  • medium to high overhead when adding ptr_provenance. medium when removing it.
  • higher risk in keeping things correct in optimization: adding the ptr_provenance can require recreating the Load/Store instruction. This might be difficult if the optimization pass is tracking pointers to the original Load/Store instruction.
  • main benefit: almost no impact from this change if the feature is not used (aka -fno-full-restrict)

Any preference in the way forward ? variant 1 is the easy one, as it is just a drop-in. Variant 2 is at the moment less-stable as it requires changes in all optimization passes that need to track the ptr_provenance.

I think variant 1 is the obvious winner.
Though while i'm not familiar with the code, i'm not sure why you'd need to move args around - can't ptr_provenance be added as a new last 'argument'?

[jeroen.dobbelaere]

In D68488#2278622, @lebedev.ri wrote:

I think variant 1 is the obvious winner.
Though while i'm not familiar with the code, i'm not sure why you'd need to move args around - can't ptr_provenance be added as a new last 'argument'?

This is what is done in the current patch (variant 0). I had to introduce a NumUserOperandsDelta to compensate, as now getNumUserOperands() == NumUserOperands - NumUserOperandsDelta.
This had impact on op_end() and getNumUserOperands():

• op_begin(): static_cast<Use*>(this)-NumUserOperands
• op_end(): op_begin() + NumUserOperands - NumUserOperandsDelta
• getNumUserOperands(): NumUserOperands - NumUserOperandsDelta

The way how variant 1 works is the following:

• Operands are allocated before the 'this' that points to the instruction
• LoadInst/StoreInst become associated to the 'VariadicOperandTraits' (instead of the OptionalOperandTraits)
• op_begin(): static_cast<Use*>(this)-NumUserOperands
• op_end(): op_begin() + NumUserOperands
• getNumUserOperands(): NumUserOperands
• When we switch from 2 to 3 arguments, the operands suddenly switch place (op_begin() changes). The shuffling can be done like:

void setPtrProvenance(Value *PtrProvenance) {
  if (getNumOperands() == 2) {
    setNumOperands(3);
    setOperand(0, getOperand(1));
    setOperand(1, getOperand(2));
  }
  setOperand(2, PtrProvenance);
}

It is even likely that a more efficient mechanism for the shuffling is possible.

[lebedev.ri]

llvm/include/llvm/IR/Instructions.h

210

Are there Instruction/Value subclasses already, that define non-trivial destructor?
I think this may be a problem for bumpptr allocators.

[jeroen.dobbelaere]

llvm/include/llvm/IR/Instructions.h

210

Are there Instruction/Value subclasses already, that define non-trivial destructor?
I think this may be a problem for bumpptr allocators.

How would that interfere ?

The non-trivial destructor is is handled in Value::deleteValue() (https://github.com/llvm/llvm-project/blob/master/llvm/lib/IR/Value.cpp#L123).

I got the base idea by looking at GlobalVariable which uses the OptionalOperandTraits.
(See https://github.com/llvm/llvm-project/blob/3d65030c45971bf041b7cdeb4b3b1378cadc4abe/llvm/include/llvm/IR/GlobalVariable.h#L73 ; But it seems that in the mean time part of the implementation has moved to operator delete)

Of course GlobalVariable is a Constant, but in retrospect, it seems that an Instruction is handled in a similar way.

[jeroen.dobbelaere]

Switch to 'Variant 1': spend more time when a ptr_provenance argument is added or removed. This removes the impact on 'all instructions' in the previous version.

[jeroen.dobbelaere]

https://llvm-compile-time-tracker.com/index.php?branch=dobbelaj-snps/perf/test_instructions_20200907-02 shows the effect of 'variant 1' and 'variant 2', on a pristine version of llvm (= without other changes related to full restrict).

[jeroen.dobbelaere]

Rebased to f8dbd61074176bae92ec360a093ac7bc498c9321.

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.
   /// FIXME: Remove this function once transition to Align is over.
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 hasNoaliasProvenanceOperand() const { return getNumOperands() == 2; }
+  Value *getNoaliasProvenanceOperand() const {
+    assert(hasNoaliasProvenanceOperand() && "we need a ptr_provenance");
+    return getOperand(1);
+  }
+  static unsigned getNoaliasProvenanceOperandIndex() { return 1U; }
+  void setNoaliasProvenanceOperand(Value *Provenance);
+  void removeNoaliasProvenanceOperand();
   // 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
   }
+  void *operator new(size_t s) { return User::operator new(s, 3); }
 
   /// 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); }
 
   /// Transparently provide more efficient getOperand methods.
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 hasNoaliasProvenanceOperand() const { return getNumOperands() == 3; }
+  Value *getNoaliasProvenanceOperand() const {
+    assert(hasNoaliasProvenanceOperand() && "we need a ptr_provenance");
+    return getOperand(2);
+  }
+  static unsigned getNoaliasProvenanceOperandIndex() { return 2U; }
+  void setNoaliasProvenanceOperand(Value *Provenance);
+  void removeNoaliasProvenanceOperand();
   // 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.
 class FenceInst : public Instruction {
   using OrderingField = AtomicOrderingBitfieldElementT<0>;
 
   void Init(AtomicOrdering Ordering, SyncScope::ID SSID);
 
 protected:
   // Note: Instruction needs to be a friend here to call cloneImpl.

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();
 
     // Select, Store and ShuffleVector always print all types.
-    if (isa<SelectInst>(I) || isa<StoreInst>(I) || isa<ShuffleVectorInst>(I)
-        || isa<ReturnInst>(I)) {
+    if (isa<SelectInst>(I) || isa<ShuffleVectorInst>(I) || isa<ReturnInst>(I)) {
       PrintAllTypes = true;
     } else {
       for (unsigned i = 1, E = I.getNumOperands(); i != E; ++i) {
         Operand = I.getOperand(i);
         // note that Operand shouldn't be null, but the test helps make dump()
         // more tolerant of malformed IR
         if (Operand && Operand->getType() != TheType) {
           PrintAllTypes = true;    // We have differing types!  Print them all!
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->hasNoaliasProvenanceOperand()) {
+      Out << ", ptr_provenance ";
+      writeOperand(LI->getNoaliasProvenanceOperand(), true);
+    }
     if (LI->getAlignment())
       Out << ", align " << LI->getAlignment();
   } else if (const StoreInst *SI = dyn_cast<StoreInst>(&I)) {
     if (SI->isAtomic())
       writeAtomic(SI->getContext(), SI->getOrdering(), SI->getSyncScopeID());
+    if (SI->hasNoaliasProvenanceOperand()) {
+      Out << ", ptr_provenance ";
+      writeOperand(SI->getNoaliasProvenanceOperand(), true);
+    }
     if (SI->getAlignment())
       Out << ", align " << SI->getAlignment();
   } 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(!(isAtomic() && getAlignment() == 0) &&
          "Alignment required for atomic load");
+  assert((!hasNoaliasProvenanceOperand() || getOperand(1)) &&
+         "ptr_provenance must be non-null");
+  assert((!hasNoaliasProvenanceOperand() ||
+          (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(Ty == cast<PointerType>(Ptr->getType())->getElementType());
+  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(Ty == cast<PointerType>(Ptr->getType())->getElementType());
   setVolatile(isVolatile);
   setAlignment(Align);
   setAtomic(Order, SSID);
   AssertOK();
   setName(Name);
 }
 
+void LoadInst::setNoaliasProvenanceOperand(llvm::LoadInst::Value *Provenance) {
+  assert(Provenance && "Needs a provenance");
+  if (!hasNoaliasProvenanceOperand()) {
+    setLoadInstNumOperands(2);
+    // shift operands
+    setOperand(0, getOperand(1));
+  }
+  setOperand(1, Provenance);
+  AssertOK();
+}
+
+void LoadInst::removeNoaliasProvenanceOperand() {
+  assert(hasNoaliasProvenanceOperand() && "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(getOperand(0)->getType() ==
                  cast<PointerType>(getOperand(1)->getType())->getElementType()
          && "Ptr must be a pointer to Val type!");
   assert(!(isAtomic() && getAlignment() == 0) &&
          "Alignment required for atomic store");
+  assert((!hasNoaliasProvenanceOperand() || getOperand(2)) &&
+         "ptr_provenance must be non-null");
+  assert((!hasNoaliasProvenanceOperand() ||
+          (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::setNoaliasProvenanceOperand(
+    llvm::StoreInst::Value *Provenance) {
+  assert(Provenance && "Needs a provenance");
+  if (!hasNoaliasProvenanceOperand()) {
+    setStoreInstNumOperands(3);
+    // shift uses; FIXME: can be made faster ?
+    setOperand(0, getOperand(1));
+    setOperand(1, getOperand(2));
+  }
+  setOperand(2, Provenance);
+  AssertOK();
+}
+
+void StoreInst::removeNoaliasProvenanceOperand() {
+  assert(hasNoaliasProvenanceOperand() && "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 *Result =
       new AllocaInst(getAllocatedType(), getType()->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 undef.
+  if (hasNoaliasProvenanceOperand())
+    Result->setNoaliasProvenanceOperand(
+        UndefValue::get(getNoaliasProvenanceOperand()->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 undef.
+  if (hasNoaliasProvenanceOperand())
+    Result->setNoaliasProvenanceOperand(
+        UndefValue::get(getNoaliasProvenanceOperand()->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().getFnAttributes().hasAttribute(
       Attribute::StrictFP));
 
   Builder.CreateRetVoid();
   EXPECT_FALSE(verifyModule(*M));
 }
 
+TEST_F(IRBuilderTest, Provenance) {
+  IRBuilder<> Builder(BB);
+
+  auto *L = Builder.CreateLoad(GV->getValueType(), GV);
+  EXPECT_TRUE(!L->hasNoaliasProvenanceOperand());
+
+  auto *S = Builder.CreateStore(L, GV);
+  EXPECT_TRUE(!S->hasNoaliasProvenanceOperand());
+
+  L->setNoaliasProvenanceOperand(GV);
+  EXPECT_TRUE(L->hasNoaliasProvenanceOperand());
+
+  S->setNoaliasProvenanceOperand(GV);
+  EXPECT_TRUE(S->hasNoaliasProvenanceOperand());
+
+  EXPECT_EQ(L->getNoaliasProvenanceOperand(), GV);
+  EXPECT_EQ(S->getNoaliasProvenanceOperand(), GV);
+
+  L->removeNoaliasProvenanceOperand();
+  EXPECT_TRUE(!L->hasNoaliasProvenanceOperand());
+
+  S->removeNoaliasProvenanceOperand();
+  EXPECT_TRUE(!S->hasNoaliasProvenanceOperand());
+}
+
 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);