[PATCH 23/27] [noalias] ArgumentPromotion/FunctionAttrs/GlobalOpt/InstCombine/GVN/JumpThreading

[jeroen.dobbelaere]

Summary

This is part of the series started by D68484.

Learn about noalias intrinsics and ptr_provenance.

Some passes have hard assumptions on the number of operands of a
load and a store instruction. Those assumptions are not valid any more.

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

[jeroen.dobbelaere]

Rebased

[jeroen.dobbelaere]

Rebased to c06b7e2ab5167ad031745a706204abed1aefd823 (July 14, 2020)

[jeroen.dobbelaere]

Rebased to 9fb46a452d4e5666828c95610ceac8dcd9e4ce16 (September 7, 2020)

[jeroen.dobbelaere]

Rebased to f8dbd61074176bae92ec360a093ac7bc498c9321.

llvm/lib/Transforms/IPO/ArgumentPromotion.cpp

if (ByValArgsToTransform.count(&*I)) {
       // or GEPs which are only used by loads
 
       // In this table, we will track which indices are loaded from the argument
       // (where direct loads are tracked as no indices).
       ScalarizeTable &ArgIndices = ScalarizedElements[&*I];
       for (User *U : make_early_inc_range(I->users())) {
         Instruction *UI = cast<Instruction>(U);
         Type *SrcTy;
-        if (LoadInst *L = dyn_cast<LoadInst>(UI))
+        IndicesVector Indices;
+        LoadInst *L = dyn_cast<LoadInst>(UI);
+        if (L)
           SrcTy = L->getType();
         else
           SrcTy = cast<GetElementPtrInst>(UI)->getSourceElementType();
         // Skip dead GEPs and remove them.
         if (isa<GetElementPtrInst>(UI) && UI->use_empty()) {
           UI->eraseFromParent();
           continue;
         }
 
-        IndicesVector Indices;
+        if (L == nullptr) { // not a direct load (loads can have 2 operands)
           Indices.reserve(UI->getNumOperands() - 1);
           // Since loads will only have a single operand, and GEPs only a single
-        // non-index operand, this will record direct loads without any indices,
-        // and gep+loads with the GEP indices.
+          // non-index operand, this will record direct loads without any
+          // indices, and gep+loads with the GEP indices.
           for (User::op_iterator II = UI->op_begin() + 1, IE = UI->op_end();
                II != IE; ++II)
             Indices.push_back(cast<ConstantInt>(*II)->getSExtValue());
           // GEPs with a single 0 index can be merged with direct loads
           if (Indices.size() == 1 && Indices.front() == 0)
             Indices.clear();
+        }
         ArgIndices.insert(std::make_pair(SrcTy, Indices));
         LoadInst *OrigLoad;
-        if (LoadInst *L = dyn_cast<LoadInst>(UI))
+        if (L)
           OrigLoad = L;
         else
           // Take any load, we will use it only to update Alias Analysis
           OrigLoad = cast<LoadInst>(UI->user_back());
         OriginalLoads[std::make_pair(&*I, Indices)] = OrigLoad;
       }
 
       // Add a parameter to the function for each element passed in.
for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end(); I != E;
           // of the previous load.
           LoadInst *newLoad =
               IRB.CreateLoad(OrigLoad->getType(), V, V->getName() + ".val");
           newLoad->setAlignment(OrigLoad->getAlign());
           // Transfer the AA info too.
           AAMDNodes AAInfo;
           OrigLoad->getAAMetadata(AAInfo);
           newLoad->setAAMetadata(AAInfo);
+          newLoad->setAAMetadataNoAliasProvenance(AAInfo);
 
           Args.push_back(newLoad);
           ArgAttrVec.push_back(AttributeSet());
         }
       }
 
     // Push any varargs arguments on the list.
     for (; AI != CB.arg_end(); ++AI, ++ArgNo) {

llvm/lib/Transforms/IPO/FunctionAttrs.cpp

case Instruction::PHI: {
       PHINode *PN = cast<PHINode>(RVI);
       for (int i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
         FlowsToReturn.insert(PN->getIncomingValue(i));
       continue;
     }
     case Instruction::Call:
     case Instruction::Invoke: {
       CallBase &CB = cast<CallBase>(*RVI);
+      if (CB.getIntrinsicID() == Intrinsic::noalias_arg_guard ||
+          CB.getIntrinsicID() == Intrinsic::noalias_copy_guard) {
+        // Look through a noalias arg/copy guard
+        FlowsToReturn.insert(RVI->getOperand(0));
+        continue;
+      }
       Function *Callee = CB.getCalledFunction();
       // A call to a node within the SCC is assumed to return null until
       // proven otherwise
       if (Callee && SCCNodes.count(Callee)) {
         Speculative = true;
         continue;
       }
       return false;

llvm/lib/Transforms/IPO/GlobalOpt.cpp

CleanupPointerRootUsers(GlobalVariable *GV,
   // Constants can't be pointers to dynamically allocated memory.
   for (Value::user_iterator UI = GV->user_begin(), E = GV->user_end();
        UI != E;) {
     User *U = *UI++;
     if (StoreInst *SI = dyn_cast<StoreInst>(U)) {
       Value *V = SI->getValueOperand();
       if (isa<Constant>(V)) {
         Changed = true;
+        // skip potential second use from ptr_provenance before the erase
+        if ((UI != E) && (*UI == SI))
+          UI++;
         SI->eraseFromParent();
       } else if (Instruction *I = dyn_cast<Instruction>(V)) {
         if (I->hasOneUse())
           Dead.push_back(std::make_pair(I, SI));
       }
     } else if (MemSetInst *MSI = dyn_cast<MemSetInst>(U)) {
       if (isa<Constant>(MSI->getValue())) {
         Changed = true;
static bool OptimizeAwayTrappingUsesOfLoads(
 
   // Replace all uses of loads with uses of uses of the stored value.
   for (Value::user_iterator GUI = GV->user_begin(), E = GV->user_end(); GUI != E;){
     User *GlobalUser = *GUI++;
     if (LoadInst *LI = dyn_cast<LoadInst>(GlobalUser)) {
       Changed |= OptimizeAwayTrappingUsesOfValue(LI, LV);
       // If we were able to delete all uses of the loads
       if (LI->use_empty()) {
+        // skip potential second use from ptr_provenance before the erase
+        if ((GUI != E) && (*GUI == LI))
+          GUI++;
         LI->eraseFromParent();
         Changed = true;
       } else {
         AllNonStoreUsesGone = false;
       }
     } else if (isa<StoreInst>(GlobalUser)) {
       // Ignore the store that stores "LV" to the global.
       assert(GlobalUser->getOperand(1) == GV &&

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

   }
   default: {
     // Handle target specific intrinsics
     Optional<Instruction *> V = targetInstCombineIntrinsic(*II);
     if (V.hasValue())
       return V.getValue();
     break;
   }
+  case Intrinsic::noalias_decl: {
+    Value *Op0 = II->getOperand(0);
+    Value *BaseOp0 = Op0->stripPointerCasts();
+    if (Op0 != BaseOp0) {
+      auto *NewNoAlias = Builder.CreateNoAliasDeclaration(
+          BaseOp0, II->getOperand(1), II->getOperand(2));
+      // bwaahh seems we need to do everything ourselves ?
+      II->replaceAllUsesWith(NewNoAlias);
+      Worklist.remove(II);
+      II->eraseFromParent();
+      MadeIRChange = true;
+
+      return nullptr;
+    }
+    break;
+  }
   }
   // Some intrinsics (like experimental_gc_statepoint) can be used in invoke
   // context, so it is handled in visitCallBase and we should trigger it.
   return visitCallBase(*II);
 }
 
 // Fence instruction simplification
 Instruction *InstCombinerImpl::visitFenceInst(FenceInst &FI) {

llvm/lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp

LoadInst *InstCombinerImpl::combineLoadToNewType(LoadInst &LI, Type *NewTy,
   Value *Ptr = LI.getPointerOperand();
   unsigned AS = LI.getPointerAddressSpace();
   Value *NewPtr = nullptr;
   if (!(match(Ptr, m_BitCast(m_Value(NewPtr))) &&
         NewPtr->getType()->getPointerElementType() == NewTy &&
         NewPtr->getType()->getPointerAddressSpace() == AS))
     NewPtr = Builder.CreateBitCast(Ptr, NewTy->getPointerTo(AS));
 
+  Value *NewProvenancePtr = nullptr;
+  if (LI.hasNoaliasProvenanceOperand()) {
+    NewProvenancePtr = Builder.CreateBitCast(LI.getNoaliasProvenanceOperand(),
+                                             NewTy->getPointerTo(AS));
+  }
+
   LoadInst *NewLoad = Builder.CreateAlignedLoad(
       NewTy, NewPtr, LI.getAlign(), LI.isVolatile(), LI.getName() + Suffix);
   NewLoad->setAtomic(LI.getOrdering(), LI.getSyncScopeID());
   copyMetadataForLoad(*NewLoad, LI);
+  if (LI.hasNoaliasProvenanceOperand()) {
+    assert(NewProvenancePtr);
+    NewLoad->setNoaliasProvenanceOperand(NewProvenancePtr);
+  }
   return NewLoad;
 }
 
 /// Combine a store to a new type.
 ///
 /// Returns the newly created store instruction.
 static StoreInst *combineStoreToNewValue(InstCombinerImpl &IC, StoreInst &SI,
                                          Value *V) {
   assert((!SI.isAtomic() || isSupportedAtomicType(V->getType())) &&
          "can't fold an atomic store of requested type");
 
   Value *Ptr = SI.getPointerOperand();
   unsigned AS = SI.getPointerAddressSpace();
   SmallVector<std::pair<unsigned, MDNode *>, 8> MD;
   SI.getAllMetadata(MD);
 
+  Value *NewProvenancePtr = nullptr;
+  if (SI.hasNoaliasProvenanceOperand()) {
+    NewProvenancePtr = IC.Builder.CreateBitCast(
+        SI.getNoaliasProvenanceOperand(), V->getType()->getPointerTo(AS));
+  }
+
   StoreInst *NewStore = IC.Builder.CreateAlignedStore(
       V, IC.Builder.CreateBitCast(Ptr, V->getType()->getPointerTo(AS)),
       SI.getAlign(), SI.isVolatile());
   NewStore->setAtomic(SI.getOrdering(), SI.getSyncScopeID());
   for (const auto &MDPair : MD) {
     unsigned ID = MDPair.first;
     MDNode *N = MDPair.second;
     // Note, essentially every kind of metadata should be preserved here! This
for (const auto &MDPair : MD) {
     case LLVMContext::MD_align:
     case LLVMContext::MD_dereferenceable:
     case LLVMContext::MD_dereferenceable_or_null:
       // These don't apply for stores.
       break;
     }
   }
 
+  if (SI.hasNoaliasProvenanceOperand()) {
+    assert(NewProvenancePtr);
+    NewStore->setNoaliasProvenanceOperand(NewProvenancePtr);
+  }
+
   return NewStore;
 }
 
 /// Returns true if instruction represent minmax pattern like:
 ///   select ((cmp load V1, load V2), V1, V2).
 static bool isMinMaxWithLoads(Value *V, Type *&LoadTy) {
   assert(V->getType()->isPointerTy() && "Expected pointer type.");
   // Ignore possible ty* to ixx* bitcast.
for (unsigned i = 0; i < NumElements; i++) {
                                                Name + ".elt");
       auto *L = IC.Builder.CreateAlignedLoad(
           ST->getElementType(i), Ptr,
           commonAlignment(Align, SL->getElementOffset(i)), Name + ".unpack");
       // Propagate AA metadata. It'll still be valid on the narrowed load.
       AAMDNodes AAMD;
       LI.getAAMetadata(AAMD);
       L->setAAMetadata(AAMD);
+      L->setAAMetadataNoAliasProvenance(AAMD);
       V = IC.Builder.CreateInsertValue(V, L, i);
     }
 
     V->setName(Name);
     return IC.replaceInstUsesWith(LI, V);
   }
 
   if (auto *AT = dyn_cast<ArrayType>(T)) {
for (uint64_t i = 0; i < NumElements; i++) {
       auto *Ptr = IC.Builder.CreateInBoundsGEP(AT, Addr, makeArrayRef(Indices),
                                                Name + ".elt");
       auto *L = IC.Builder.CreateAlignedLoad(AT->getElementType(), Ptr,
                                              commonAlignment(Align, Offset),
                                              Name + ".unpack");
       AAMDNodes AAMD;
       LI.getAAMetadata(AAMD);
       L->setAAMetadata(AAMD);
+      L->setAAMetadataNoAliasProvenance(AAMD);
       V = IC.Builder.CreateInsertValue(V, L, i);
       Offset += EltSize;
     }
 
     V->setName(Name);
     return IC.replaceInstUsesWith(LI, V);
   }
 
if (isa<UndefValue>(Op) ||
        !NullPointerIsDefined(LI.getFunction(), LI.getPointerAddressSpace())))
     return true;
   return false;
 }
 
 Instruction *InstCombinerImpl::visitLoadInst(LoadInst &LI) {
   Value *Op = LI.getOperand(0);
 
+  if (LI.hasNoaliasProvenanceOperand()) {
+    if (LI.getNoaliasProvenanceOperand() == LI.getPointerOperand() ||
+        isa<UndefValue>(LI.getNoaliasProvenanceOperand())) {
+      // degenerated ptr_provenance
+      LI.removeNoaliasProvenanceOperand();
+      return &LI;
+    }
+  }
+
   // Try to canonicalize the loaded type.
   if (Instruction *Res = combineLoadToOperationType(*this, LI))
     return Res;
 
   // Attempt to improve the alignment.
   Align KnownAlign = getOrEnforceKnownAlignment(
       Op, DL.getPrefTypeAlign(LI.getType()), DL, &LI, &AC, &DT);
   if (KnownAlign > LI.getAlign())
for (unsigned i = 0; i < Count; i++) {
       auto *Ptr = IC.Builder.CreateInBoundsGEP(ST, Addr, makeArrayRef(Indices),
                                                AddrName);
       auto *Val = IC.Builder.CreateExtractValue(V, i, EltName);
       auto EltAlign = commonAlignment(Align, SL->getElementOffset(i));
       llvm::Instruction *NS = IC.Builder.CreateAlignedStore(Val, Ptr, EltAlign);
       AAMDNodes AAMD;
       SI.getAAMetadata(AAMD);
       NS->setAAMetadata(AAMD);
+      NS->setAAMetadataNoAliasProvenance(AAMD);
     }
 
     return true;
   }
 
   if (auto *AT = dyn_cast<ArrayType>(T)) {
     // If the array only have one element, we unpack.
     auto NumElements = AT->getNumElements();
for (uint64_t i = 0; i < NumElements; i++) {
       auto *Ptr = IC.Builder.CreateInBoundsGEP(AT, Addr, makeArrayRef(Indices),
                                                AddrName);
       auto *Val = IC.Builder.CreateExtractValue(V, i, EltName);
       auto EltAlign = commonAlignment(Align, Offset);
       Instruction *NS = IC.Builder.CreateAlignedStore(Val, Ptr, EltAlign);
       AAMDNodes AAMD;
       SI.getAAMetadata(AAMD);
       NS->setAAMetadata(AAMD);
+      NS->setAAMetadataNoAliasProvenance(AAMD);
       Offset += EltSize;
     }
 
     return true;
   }
 
   return false;
 }
static bool removeBitcastsFromLoadStoreOnMinMax(InstCombinerImpl &IC,
   IC.eraseInstFromFunction(*LI);
   return true;
 }
 
 Instruction *InstCombinerImpl::visitStoreInst(StoreInst &SI) {
   Value *Val = SI.getOperand(0);
   Value *Ptr = SI.getOperand(1);
 
+  if (SI.hasNoaliasProvenanceOperand()) {
+    if (SI.getNoaliasProvenanceOperand() == SI.getPointerOperand() ||
+        isa<UndefValue>(SI.getNoaliasProvenanceOperand())) {
+      // degenerated ptr_provenance
+      SI.removeNoaliasProvenanceOperand();
+      return &SI;
+    }
+  }
+
   // Try to canonicalize the stored type.
   if (combineStoreToValueType(*this, SI))
     return eraseInstFromFunction(SI);
 
   // Attempt to improve the alignment.
   const Align KnownAlign = getOrEnforceKnownAlignment(
       Ptr, DL.getPrefTypeAlign(Val->getType()), DL, &SI, &AC, &DT);
   if (KnownAlign > SI.getAlign())
bool InstCombinerImpl::mergeStoreIntoSuccessor(StoreInst &SI) {
   NewSI->setDebugLoc(MergedLoc);
 
   // If the two stores had AA tags, merge them.
   AAMDNodes AATags;
   SI.getAAMetadata(AATags);
   if (AATags) {
     OtherStore->getAAMetadata(AATags, /* Merge = */ true);
     NewSI->setAAMetadata(AATags);
+    NewSI->setAAMetadataNoAliasProvenance(AATags);
   }
 
   // Nuke the old stores.
   eraseInstFromFunction(SI);
   eraseInstFromFunction(*OtherStore);
   return true;
 }

llvm/lib/Transforms/InstCombine/InstCombinePHI.cpp

PHINode *NewPN = PHINode::Create(FirstLI->getOperand(0)->getType(),
                                    PN.getName()+".in");
 
   Value *InVal = FirstLI->getOperand(0);
   NewPN->addIncoming(InVal, PN.getIncomingBlock(0));
   LoadInst *NewLI =
       new LoadInst(FirstLI->getType(), NewPN, "", isVolatile, LoadAlignment);
 
   unsigned KnownIDs[] = {
-    LLVMContext::MD_tbaa,
     LLVMContext::MD_range,
     LLVMContext::MD_invariant_load,
-    LLVMContext::MD_alias_scope,
-    LLVMContext::MD_noalias,
     LLVMContext::MD_nonnull,
     LLVMContext::MD_align,
     LLVMContext::MD_dereferenceable,
     LLVMContext::MD_dereferenceable_or_null,
     LLVMContext::MD_access_group,
   };
 
   for (unsigned ID : KnownIDs)
     NewLI->setMetadata(ID, FirstLI->getMetadata(ID));
 
   // Add all operands to the new PHI and combine TBAA metadata.
+  AAMDNodes AAInfo;
+  FirstLI->getAAMetadata(AAInfo);
   for (unsigned i = 1, e = PN.getNumIncomingValues(); i != e; ++i) {
     LoadInst *LI = cast<LoadInst>(PN.getIncomingValue(i));
     combineMetadata(NewLI, LI, KnownIDs, true);
+    LI->getAAMetadata(AAInfo, true);
     Value *NewInVal = LI->getOperand(0);
     if (NewInVal != InVal)
       InVal = nullptr;
     NewPN->addIncoming(NewInVal, PN.getIncomingBlock(i));
   }
+  NewLI->setAAMetadata(AAInfo);
+  NewLI->setAAMetadataNoAliasProvenance(AAInfo);
 
   if (InVal) {
     // The new PHI unions all of the same values together.  This is really
     // common, so we handle it intelligently here for compile-time speed.
     NewLI->setOperand(0, InVal);
     delete NewPN;
   } else {
     InsertNewInstBefore(NewPN, PN);

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

for (User *U : PI->users()) {
             LLVM_FALLTHROUGH;
           }
           case Intrinsic::assume:
           case Intrinsic::invariant_start:
           case Intrinsic::invariant_end:
           case Intrinsic::lifetime_start:
           case Intrinsic::lifetime_end:
           case Intrinsic::objectsize:
+          case Intrinsic::noalias_decl:
             Users.emplace_back(I);
             continue;
           }
         }
 
         if (isFreeCall(I, TLI)) {
           Users.emplace_back(I);
           continue;
if (L->isSimple() && L->hasOneUse()) {
       Value *GEP = Builder.CreateInBoundsGEP(L->getType(),
                                              L->getPointerOperand(), Indices);
       Instruction *NL = Builder.CreateLoad(EV.getType(), GEP);
       // Whatever aliasing information we had for the orignal load must also
       // hold for the smaller load, so propagate the annotations.
       AAMDNodes Nodes;
       L->getAAMetadata(Nodes);
       NL->setAAMetadata(Nodes);
+      NL->setAAMetadataNoAliasProvenance(Nodes);
       // Returning the load directly will cause the main loop to insert it in
-      // the wrong spot, so use replaceInstUsesWith().
+      // the wrong spot, so use ReplaceInstUsesWith().
+      {
+        for (auto mdtag :
+             {LLVMContext::MD_dbg, LLVMContext::MD_prof, LLVMContext::MD_fpmath,
+              LLVMContext::MD_tbaa_struct, LLVMContext::MD_invariant_load,
+              LLVMContext::MD_nontemporal,
+              LLVMContext::MD_mem_parallel_loop_access}) {
+          if (auto *MD = L->getMetadata(mdtag)) {
+            NL->setMetadata(mdtag, MD);
+          }
+        }
         return replaceInstUsesWith(EV, NL);
       }
+    }
   // We could simplify extracts from other values. Note that nested extracts may
   // already be simplified implicitly by the above: extract (extract (insert) )
   // will be translated into extract ( insert ( extract ) ) first and then just
   // the value inserted, if appropriate. Similarly for extracts from single-use
   // loads: extract (extract (load)) will be translated to extract (load (gep))
   // and if again single-use then via load (gep (gep)) to load (gep).
   // However, double extracts from e.g. function arguments or return values
   // aren't handled yet.

llvm/lib/Transforms/Scalar/GVN.cpp

if (MSSAU) {
         MSSAU->insertDef(NewDef, /*RenameUses=*/true);
       else
         MSSAU->insertUse(cast<MemoryUse>(NewAccess), /*RenameUses=*/true);
     }
 
     // Transfer the old load's AA tags to the new load.
     AAMDNodes Tags;
     Load->getAAMetadata(Tags);
-    if (Tags)
+    if (Tags) {
       NewLoad->setAAMetadata(Tags);
+      // Note: ptr_provenance propagation is not done here. A dependend
+      // provenance should be migrated first !
+    }
 
     if (auto *MD = Load->getMetadata(LLVMContext::MD_invariant_load))
       NewLoad->setMetadata(LLVMContext::MD_invariant_load, MD);
     if (auto *InvGroupMD = Load->getMetadata(LLVMContext::MD_invariant_group))
       NewLoad->setMetadata(LLVMContext::MD_invariant_group, InvGroupMD);
     if (auto *RangeMD = Load->getMetadata(LLVMContext::MD_range))
       NewLoad->setMetadata(LLVMContext::MD_range, RangeMD);
     if (auto *AccessMD = Load->getMetadata(LLVMContext::MD_access_group))

llvm/lib/Transforms/Scalar/JumpThreading.cpp

for (; &*I != StopAt; ++I) {
     // If this is a pointer->pointer bitcast, it is free.
     if (isa<BitCastInst>(I) && I->getType()->isPointerTy())
       continue;
 
     // Freeze instruction is free, too.
     if (isa<FreezeInst>(I))
       continue;
 
+    // Noalias intrinsics are free too.
+    if (isa<NoAliasScopeDeclInst>(I))
+      continue;
+    if (auto II = dyn_cast<IntrinsicInst>(I)) {
+      auto ID = II->getIntrinsicID();
+      if (ID == Intrinsic::noalias_decl || ID == Intrinsic::noalias ||
+          ID == Intrinsic::provenance_noalias ||
+          ID == Intrinsic::noalias_arg_guard ||
+          ID == Intrinsic::noalias_copy_guard)
+        continue;
+    }
+
     // Bail out if this instruction gives back a token type, it is not possible
     // to duplicate it if it is used outside this BB.
     if (I->getType()->isTokenTy() && I->isUsedOutsideOfBlock(BB))
       return ~0U;
 
     // All other instructions count for at least one unit.
     ++Size;
 
if (UnavailablePred) {
     assert(UnavailablePred->getTerminator()->getNumSuccessors() == 1 &&
            "Can't handle critical edge here!");
     LoadInst *NewVal = new LoadInst(
         LoadI->getType(), LoadedPtr->DoPHITranslation(LoadBB, UnavailablePred),
         LoadI->getName() + ".pr", false, LoadI->getAlign(),
         LoadI->getOrdering(), LoadI->getSyncScopeID(),
         UnavailablePred->getTerminator());
     NewVal->setDebugLoc(LoadI->getDebugLoc());
-    if (AATags)
+    if (AATags) {
       NewVal->setAAMetadata(AATags);
+      // Note: ptr_provenance propagation is not done here. A dependend
+      // provenance should be migrated first !
+    }
 
     AvailablePreds.emplace_back(UnavailablePred, NewVal);
   }
 
   // Now we know that each predecessor of this block has a value in
   // AvailablePreds, sort them for efficient access as we're walking the preds.
   array_pod_sort(AvailablePreds.begin(), AvailablePreds.end());
 

 DenseMap<Instruction *, Value *>
 JumpThreadingPass::cloneInstructions(BasicBlock::iterator BI,
                                      BasicBlock::iterator BE, BasicBlock *NewBB,
                                      BasicBlock *PredBB) {
   // We are going to have to map operands from the source basic block to the new
   // copy of the block 'NewBB'.  If there are PHI nodes in the source basic
   // block, evaluate them to account for entry from PredBB.
   DenseMap<Instruction *, Value *> ValueMapping;
-
   // Clone the phi nodes of the source basic block into NewBB.  The resulting
   // phi nodes are trivial since NewBB only has one predecessor, but SSAUpdater
   // might need to rewrite the operand of the cloned phi.
   for (; PHINode *PN = dyn_cast<PHINode>(BI); ++BI) {
     PHINode *NewPN = PHINode::Create(PN->getType(), 1, PN->getName(), NewBB);
     NewPN->addIncoming(PN->getIncomingValueForBlock(PredBB), PredBB);
     ValueMapping[PN] = NewPN;
   }
 
-  // Clone noalias scope declarations in the threaded block. When threading a
-  // loop exit, we would otherwise end up with two idential scope declarations
-  // visible at the same time.
-  SmallVector<MDNode *> NoAliasScopes;
-  DenseMap<MDNode *, MDNode *> ClonedScopes;
-  LLVMContext &Context = PredBB->getContext();
-  identifyNoAliasScopesToClone(BI, BE, NoAliasScopes);
-  cloneNoAliasScopes(NoAliasScopes, ClonedScopes, "thread", Context);
+  // Cloning noalias scopes is allowed and will refer to the same scope.
 
   // Clone the non-phi instructions of the source basic block into NewBB,
   // keeping track of the mapping and using it to remap operands in the cloned
   // instructions.
   for (; BI != BE; ++BI) {
     Instruction *New = BI->clone();
     New->setName(BI->getName());
     NewBB->getInstList().push_back(New);
+    // Also track the ptr_provenance
+    if (auto *SI = dyn_cast<StoreInst>(BI)) {
+      if (SI->hasNoaliasProvenanceOperand())
+        cast<StoreInst>(New)->setNoaliasProvenanceOperand(
+            SI->getNoaliasProvenanceOperand());
+    } else if (auto *LI = dyn_cast<LoadInst>(BI)) {
+      if (LI->hasNoaliasProvenanceOperand())
+        cast<LoadInst>(New)->setNoaliasProvenanceOperand(
+            LI->getNoaliasProvenanceOperand());
+    }
+
     ValueMapping[&*BI] = New;
-    adaptNoAliasScopes(New, ClonedScopes, Context);
 
     // Remap operands to patch up intra-block references.
     for (unsigned i = 0, e = New->getNumOperands(); i != e; ++i)
       if (Instruction *Inst = dyn_cast<Instruction>(New->getOperand(i))) {
         DenseMap<Instruction *, Value *>::iterator I = ValueMapping.find(Inst);
         if (I != ValueMapping.end())
           New->setOperand(i, I->second);
       }

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

if (isa<DbgInfoIntrinsic>(I1) || isa<DbgInfoIntrinsic>(I2)) {
                              LLVMContext::MD_fpmath,
                              LLVMContext::MD_invariant_load,
                              LLVMContext::MD_nonnull,
                              LLVMContext::MD_invariant_group,
                              LLVMContext::MD_align,
                              LLVMContext::MD_dereferenceable,
                              LLVMContext::MD_dereferenceable_or_null,
                              LLVMContext::MD_mem_parallel_loop_access,
+                             LLVMContext::MD_noalias,
                              LLVMContext::MD_access_group,
                              LLVMContext::MD_preserve_access_index};
       combineMetadata(I1, I2, KnownIDs, true);
 
       // I1 and I2 are being combined into a single instruction.  Its debug
       // location is the merged locations of the original instructions.
       I1->applyMergedLocation(I1->getDebugLoc(), I2->getDebugLoc());
 
static bool mergeConditionalStoreToAddress(
 
   auto *T = SplitBlockAndInsertIfThen(CombinedPred, &*QB.GetInsertPoint(),
                                       /*Unreachable=*/false,
                                       /*BranchWeights=*/nullptr, DTU);
   QB.SetInsertPoint(T);
   StoreInst *SI = cast<StoreInst>(QB.CreateStore(QPHI, Address));
   AAMDNodes AAMD;
   PStore->getAAMetadata(AAMD, /*Merge=*/false);
-  PStore->getAAMetadata(AAMD, /*Merge=*/true);
+  QStore->getAAMetadata(AAMD, /*Merge=*/true);
   SI->setAAMetadata(AAMD);
+  SI->setAAMetadataNoAliasProvenance(AAMD);
   // Choose the minimum alignment. If we could prove both stores execute, we
   // could use biggest one.  In this case, though, we only know that one of the
   // stores executes.  And we don't know it's safe to take the alignment from a
   // store that doesn't execute.
   SI->setAlignment(std::min(PStore->getAlign(), QStore->getAlign()));
 
   QStore->eraseFromParent();
   PStore->eraseFromParent();

llvm/test/Transforms/FunctionAttrs/nonnull.ll

 8:                                                ; preds = %8, %4
   %9 = phi i32 [ 1, %4 ], [ %10, %8 ]
   tail call void @sink(i32* %6)
   %10 = add nuw nsw i32 %9, 1
   %11 = icmp eq i32 %10, %1
   br i1 %11, label %7, label %8
 }
 
+; Return a pointer trivially nonnull (argument attribute) through a llvm.noalias.arg.guard
+; FNATTR: define nonnull i8* @test_noalias_arg_guard
+define i8* @test_noalias_arg_guard(i8* nonnull %p) {
+  %ret = tail call i8* @llvm.noalias.arg.guard.p0i8.p0i8(i8* %p, i8* %p)
+  ret i8* %p
+}
+
+; Function Attrs: nounwind readnone
+declare i8* @llvm.noalias.arg.guard.p0i8.p0i8(i8*, i8*) nounwind readnone
+
 attributes #0 = { null_pointer_is_valid }
 attributes #1 = { nounwind willreturn}

llvm/test/Transforms/InstCombine/fold-phi-load-metadata.ll

return:                                           ; preds = %if.end, %if.then
   store i32* %pval, i32** @g1, align 8
   ret i32 %retval
 }
 
 ; CHECK: ![[EMPTYNODE]] = !{}
 ; CHECK: ![[TBAA]] = !{![[TAG1:[0-9]+]], ![[TAG1]], i64 0}
 ; CHECK: ![[TAG1]] = !{!"int", !{{[0-9]+}}, i64 0}
 ; CHECK: ![[RANGE]] = !{i32 10, i32 25}
-; CHECK: ![[ALIAS_SCOPE]] = !{![[SCOPE0:[0-9]+]], ![[SCOPE1:[0-9]+]], ![[SCOPE2:[0-9]+]]}
+; CHECK: ![[ALIAS_SCOPE]] = !{![[SCOPE0:[0-9]+]], ![[SCOPE2:[0-9]+]], ![[SCOPE1:[0-9]+]]}
 ; CHECK: ![[SCOPE0]] = distinct !{![[SCOPE0]], !{{[0-9]+}}, !"scope0"}
-; CHECK: ![[SCOPE1]] = distinct !{![[SCOPE1]], !{{[0-9]+}}, !"scope1"}
 ; CHECK: ![[SCOPE2]] = distinct !{![[SCOPE2]], !{{[0-9]+}}, !"scope2"}
+; CHECK: ![[SCOPE1]] = distinct !{![[SCOPE1]], !{{[0-9]+}}, !"scope1"}
 ; CHECK: ![[NOALIAS]] = !{![[SCOPE3:[0-9]+]]}
 ; CHECK: ![[SCOPE3]] = distinct !{![[SCOPE3]], !{{[0-9]+}}, !"scope3"}
 
 !0 = !{!1, !4, i64 4}
 !1 = !{!"", !7, i64 0, !4, i64 4}
 !2 = !{!3, !4, i64 0}
 !3 = !{!"", !4, i64 0, !7, i64 4}
 !4 = !{!"int", !5, i64 0}

llvm/test/Transforms/InstCombine/noalias.ll

+; RUN: opt < %s -instcombine -S | FileCheck %s
+
+target datalayout = "e-i8:8:8-i16:16:16-i32:32:32-i64:32:32-f32:32:32-f64:32:32-p:32:32:32:32:8-s0:32:32-a0:8:8-S32-n32-v128:32:32-P0-p0:32:32:32:32:8-p10:32:32:32:32:8-p20:32:32:32:32:8"
+
+@__const.f1.i = private unnamed_addr constant { i8*, [4 x i8] } { i8* null, [4 x i8] undef }, align 4
+
+declare void @do_something(i8*)
+
+; Function Attrs: nounwind optsize
+define dso_local i64 @test01() local_unnamed_addr #0 {
+entry:
+  %i.sroa.6 = alloca [2 x i8], align 2
+  %i.sroa.6.0..sroa_idx6 = getelementptr inbounds [2 x i8], [2 x i8]* %i.sroa.6, i32 0, i32 0
+  call void @llvm.lifetime.start.p0i8(i64 2, i8* %i.sroa.6.0..sroa_idx6)
+  %0 = call i8* @llvm.noalias.decl.p0i8.p0a2i8.i32([2 x i8]* %i.sroa.6, i32 2, metadata !2)
+  call void @llvm.memcpy.p0i8.p0i8.i32(i8* align 2 %i.sroa.6.0..sroa_idx6, i8* align 2 getelementptr inbounds (i8, i8* bitcast ({ i8*, [4 x i8] }* @__const.f1.i to i8*), i32 2), i32 2, i1 false)
+  %i.sroa.6.cast = bitcast [2 x i8]* %i.sroa.6 to i8*
+  call void @do_something(i8* %i.sroa.6.cast)
+  call void @llvm.lifetime.end.p0i8(i64 2, i8* %i.sroa.6.0..sroa_idx6)
+  ret i64 undef
+}
+
+; CHECK-LABEL: @test01(
+; CHECK:  %i.sroa.6 = alloca i16, align 2
+; CHECK:  %0 = call i8* @llvm.noalias.decl.p0i8.p0i16.i32(i16* nonnull %i.sroa.6, i32 2, metadata !2)
+
+; Function Attrs: argmemonly nounwind
+declare void @llvm.lifetime.start.p0i8(i64 immarg, i8* nocapture) #1
+
+; Function Attrs: argmemonly nounwind
+declare void @llvm.memcpy.p0i8.p0i8.i32(i8* nocapture writeonly, i8* nocapture readonly, i32, i1 immarg) #1
+
+; Function Attrs: argmemonly nounwind
+declare void @llvm.lifetime.end.p0i8(i64 immarg, i8* nocapture) #1
+
+; Function Attrs: argmemonly nounwind
+declare i8* @llvm.noalias.decl.p0i8.p0a2i8.i32([2 x i8]*, i32, metadata) #1
+
+attributes #0 = { nounwind optsize "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "less-precise-fpmad"="false" "min-legal-vector-width"="0" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "unsafe-fp-math"="false" "use-soft-float"="false" }
+attributes #1 = { argmemonly nounwind }
+
+!llvm.module.flags = !{!0}
+!llvm.ident = !{!1}
+
+!0 = !{i32 1, !"wchar_size", i32 4}
+!1 = !{!"clang"}
+!2 = !{!3}
+!3 = distinct !{!3, !4, !"f1: i"}
+!4 = distinct !{!4, !"f1"}

llvm/test/Transforms/JumpThreading/noalias-decl.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -S -jump-threading < %s | FileCheck %s
+
+define void @test01(i32* %ptr1, i32* %ptr2) {
+; CHECK-LABEL: @test01(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[V1_DECL:%.*]] = call i8* @llvm.noalias.decl.p0i8.p0p0i32.i32(i32** null, i32 0, metadata [[META0:![0-9]+]])
+; CHECK-NEXT:    [[V1_PROV:%.*]] = call i32* @llvm.provenance.noalias.p0i32.p0i8.p0p0i32.p0p0i32.i32(i32* [[PTR1:%.*]], i8* [[V1_DECL]], i32** null, i32** null, i32 0, metadata [[META0]])
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[I_INC:%.*]], [[LATCH:%.*]] ]
+; CHECK-NEXT:    [[C:%.*]] = icmp eq i32 [[I]], 100
+; CHECK-NEXT:    br i1 [[C]], label [[EXIT:%.*]], label [[LATCH]]
+; CHECK:       latch:
+; CHECK-NEXT:    [[V2_DECL:%.*]] = call i8* @llvm.noalias.decl.p0i8.p0p0i32.i32(i32** null, i32 0, metadata [[META3:![0-9]+]])
+; CHECK-NEXT:    [[V2_PROV:%.*]] = call i32* @llvm.provenance.noalias.p0i32.p0i8.p0p0i32.p0p0i32.i32(i32* [[PTR2:%.*]], i8* [[V2_DECL]], i32** null, i32** null, i32 0, metadata [[META3]])
+; CHECK-NEXT:    store i32 0, i32* [[PTR1]], ptr_provenance i32* [[V1_PROV]], align 4, !noalias !0
+; CHECK-NEXT:    store i32 1, i32* [[PTR2]], ptr_provenance i32* [[V2_PROV]], align 4, !noalias !3
+; CHECK-NEXT:    [[I_INC]] = add i32 [[I]], 1
+; CHECK-NEXT:    br label [[LOOP]]
+; CHECK:       exit:
+; CHECK-NEXT:    [[V2_DECL2:%.*]] = call i8* @llvm.noalias.decl.p0i8.p0p0i32.i32(i32** null, i32 0, metadata [[META3]])
+; CHECK-NEXT:    [[V2_PROV3:%.*]] = call i32* @llvm.provenance.noalias.p0i32.p0i8.p0p0i32.p0p0i32.i32(i32* [[PTR2]], i8* [[V2_DECL2]], i32** null, i32** null, i32 0, metadata [[META3]])
+; CHECK-NEXT:    store i32 0, i32* [[PTR1]], ptr_provenance i32* [[V1_PROV]], align 4, !noalias !0
+; CHECK-NEXT:    store i32 1, i32* [[PTR2]], ptr_provenance i32* [[V2_PROV3]], align 4, !noalias !3
+; CHECK-NEXT:    ret void
+;
+entry:
+  %v1.decl = call i8* @llvm.noalias.decl.p0i8.p0p0i32.i32(i32** null, i32 0, metadata !0)
+  %v1.prov = call i32* @llvm.provenance.noalias.p0i32.p0i8.p0p0i32.p0p0i32.i32(i32* %ptr1, i8* %v1.decl, i32** null, i32** null, i32 0, metadata !0)
+  br label %loop
+
+loop:
+  %i = phi i32 [ 0, %entry ], [ %i.inc, %latch ]
+  %c = icmp eq i32 %i, 100
+  br i1 %c, label %if, label %latch
+
+if:
+  br label %latch
+
+latch:
+  %p = phi i1 [ true, %if ], [ false, %loop ]
+  %v2.decl = call i8* @llvm.noalias.decl.p0i8.p0p0i32.i32(i32** null, i32 0, metadata !3)
+  %v2.prov = call i32* @llvm.provenance.noalias.p0i32.p0i8.p0p0i32.p0p0i32.i32(i32* %ptr2, i8* %v2.decl, i32** null, i32** null, i32 0, metadata !3)
+  store i32 0, i32* %ptr1, ptr_provenance i32* %v1.prov, !noalias !0
+  store i32 1, i32* %ptr2, ptr_provenance i32* %v2.prov, !noalias !3
+  ; store i32 2, i32* %ptr2, ptr_provenance i32* %v2.prov, !noalias !5
+  %i.inc = add i32 %i, 1
+  br i1 %p, label %exit, label %loop
+
+exit:
+  ret void
+}
+
+; Function Attrs: argmemonly nounwind
+declare i8* @llvm.noalias.decl.p0i8.p0p0i32.i32(i32**, i32, metadata)
+
+; Function Attrs: nounwind readnone speculatable
+declare i32* @llvm.provenance.noalias.p0i32.p0i8.p0p0i32.p0p0i32.i32(i32*, i8*, i32**, i32**, i32, metadata)
+
+!0 = !{!1}
+!1 = distinct !{!1, !2, !"scope1"}
+!2 = distinct !{!2, !"domain"}
+!3 = !{!4}
+!4 = distinct !{!4, !2, !"scope2"}
+!5 = !{!1, !4}
+
+; CHECK: !0 = !{!1}
+; CHECK: !1 = distinct !{!1, !2, !"scope1"}
+; CHECK: !2 = distinct !{!2, !"domain"}
+; CHECK: !3 = !{!4}
+; CHECK: !4 = distinct !{!4, !2, !"scope2"}
+; CHECK-NOT: =
+

llvm/test/Transforms/JumpThreading/noalias-scope-decl.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -S -jump-threading < %s | FileCheck %s
 
 define void @test(i8* %ptr) {
 ; CHECK-LABEL: @test(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    call void @llvm.experimental.noalias.scope.decl(metadata !0)
+; CHECK-NEXT:    call void @llvm.experimental.noalias.scope.decl(metadata [[META0:![0-9]+]])
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[I_INC:%.*]], [[LATCH:%.*]] ]
 ; CHECK-NEXT:    [[C:%.*]] = icmp eq i32 [[I]], 100
 ; CHECK-NEXT:    br i1 [[C]], label [[EXIT:%.*]], label [[LATCH]]
 ; CHECK:       latch:
-; CHECK-NEXT:    call void @llvm.experimental.noalias.scope.decl(metadata !3)
+; CHECK-NEXT:    call void @llvm.experimental.noalias.scope.decl(metadata [[META3:![0-9]+]])
 ; CHECK-NEXT:    store i8 0, i8* [[PTR:%.*]], align 1, !noalias !0
 ; CHECK-NEXT:    store i8 1, i8* [[PTR]], align 1, !noalias !3
 ; CHECK-NEXT:    [[I_INC]] = add i32 [[I]], 1
 ; CHECK-NEXT:    br label [[LOOP]]
 ; CHECK:       exit:
-; CHECK-NEXT:    call void @llvm.experimental.noalias.scope.decl(metadata !5)
+; CHECK-NEXT:    call void @llvm.experimental.noalias.scope.decl(metadata [[META3]])
 ; CHECK-NEXT:    store i8 0, i8* [[PTR]], align 1, !noalias !0
-; CHECK-NEXT:    store i8 1, i8* [[PTR]], align 1, !noalias !5
+; CHECK-NEXT:    store i8 1, i8* [[PTR]], align 1, !noalias !3
 ; CHECK-NEXT:    ret void
 ;
 entry:
   call void @llvm.experimental.noalias.scope.decl(metadata !0)
   br label %loop
 
 loop:
   %i = phi i32 [ 0, %entry ], [ %i.inc, %latch ]

 !3 = !{!4}
 !4 = distinct !{!4, !2, !"scope2"}
 
 ; CHECK: !0 = !{!1}
 ; CHECK: !1 = distinct !{!1, !2, !"scope1"}
 ; CHECK: !2 = distinct !{!2, !"domain"}
 ; CHECK: !3 = !{!4}
 ; CHECK: !4 = distinct !{!4, !2, !"scope2"}
-; CHECK: !5 = !{!6}
-; CHECK: !6 = distinct !{!6, !2, !"scope2:thread"}
+; CHECK-NOT:  =