Index: llvm/lib/IR/Verifier.cpp
===================================================================
--- llvm/lib/IR/Verifier.cpp
+++ llvm/lib/IR/Verifier.cpp
@@ -349,6 +349,9 @@
 
   SmallVector<IntrinsicInst *, 4> NoAliasScopeDecls;
 
+  // Instructions that have an UnknownProvenenace as one of their operands.
+  SmallVector<Instruction *, 4> UnknownProvenanceUsers;
+
   void checkAtomicMemAccessSize(Type *Ty, const Instruction *I);
 
 public:
@@ -398,6 +401,8 @@
     SiblingFuncletInfo.clear();
     verifyNoAliasScopeDecl();
     NoAliasScopeDecls.clear();
+    verifyUnknownProvenanceUsage();
+    UnknownProvenanceUsers.clear();
 
     return !Broken;
   }
@@ -595,6 +600,9 @@
 
   /// Verify the llvm.experimental.noalias.scope.decl declarations
   void verifyNoAliasScopeDecl();
+
+  /// Verify the usage of UnknownProvenance
+  void verifyUnknownProvenanceUsage();
 };
 
 } // end anonymous namespace
@@ -621,6 +629,9 @@
 void Verifier::visit(Instruction &I) {
   for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i)
     Check(I.getOperand(i) != nullptr, "Operand is null", &I);
+  if (llvm::any_of(I.operands(),
+                   [](auto &Op) { return isa<UnknownProvenance>(Op); }))
+    UnknownProvenanceUsers.emplace_back(&I);
   InstVisitor<Verifier>::visit(I);
 }
 
@@ -6352,6 +6363,58 @@
   }
 }
 
+void Verifier::verifyUnknownProvenanceUsage() {
+  SmallPtrSet<Instruction *, 8> Handled;
+  SmallVector<Instruction *, 8> WorkList;
+
+  enum State { Invalid, ValidStop, ValidPropagate };
+  auto IsValidUnknownProvenanceUser = [](Instruction *I, const unsigned OpNo) {
+    if (isa<StoreInst>(I))
+      return OpNo == StoreInst::getPtrProvenanceOperandIndex() ? ValidStop
+                                                               : Invalid;
+    else if (isa<LoadInst>(I))
+      return OpNo == LoadInst::getPtrProvenanceOperandIndex() ? ValidStop
+                                                              : Invalid;
+    else if (isa<SelectInst>(I))
+      return OpNo != 0 ? ValidPropagate : Invalid;
+    else if (isa<PHINode>(I))
+      return ValidPropagate;
+    else if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
+      if (II->getIntrinsicID() == Intrinsic::experimental_ptr_provenance)
+        return OpNo == 1 ? ValidStop : Invalid;
+    }
+    return Invalid;
+  };
+
+  auto HandleUnknownProvenanceUser = [&](Instruction *I, unsigned OpNo) {
+    auto Result = IsValidUnknownProvenanceUser(I, OpNo);
+    Check(Result != Invalid, "UnknownProvenance not on the ptr_provenance path",
+          I, OpNo);
+    if (Result == ValidPropagate)
+      WorkList.push_back(I);
+  };
+
+  // Bootstrap instructions directly using UnknownProvenance
+  for (auto *I : UnknownProvenanceUsers) {
+    unsigned OpNo = 0;
+    for (auto &Op : I->operands()) {
+      if (isa<UnknownProvenance>(Op))
+        HandleUnknownProvenanceUser(I, OpNo);
+      OpNo++;
+    }
+  }
+
+  // Check Propagation
+  while (!WorkList.empty()) {
+    Instruction *I = WorkList.back();
+    WorkList.pop_back();
+    if (Handled.insert(I).second)
+      for (auto &U : I->uses())
+        HandleUnknownProvenanceUser(cast<Instruction>(U.getUser()),
+                                    U.getOperandNo());
+  }
+}
+
 //===----------------------------------------------------------------------===//
 //  Implement the public interfaces to this file...
 //===----------------------------------------------------------------------===//
Index: llvm/test/Verifier/unknown_provenance.ll
===================================================================
--- /dev/null
+++ llvm/test/Verifier/unknown_provenance.ll
@@ -0,0 +1,92 @@
+; RUN: not llvm-as %s -o /dev/null 2>&1 | FileCheck %s
+
+define ptr @test00(ptr %a, ptr %b, i32 %c) {
+entry:
+  %tobool.not = icmp eq i32 %c, 0
+; CHECK: UnknownProvenance not on the ptr_provenance path
+; CHECK-NEXT: %add.ptr = getelementptr inbounds i32, ptr unknown_provenance, i64 10
+; CHECK-NEXT:0
+  %add.ptr = getelementptr inbounds i32, ptr unknown_provenance, i64 10
+  %retval = select i1 %tobool.not, ptr %add.ptr, ptr %a
+  ret ptr %retval
+}
+
+define ptr @test01(ptr %a, ptr %b, i32 %c) {
+entry:
+  %tobool.not = icmp eq i32 %c, 0
+  %retval = select i1 %tobool.not, ptr unknown_provenance, ptr %a
+; CHECK: UnknownProvenance not on the ptr_provenance path
+; CHECK-NEXT: ret ptr %retval
+; CHECK-NEXT:0
+  ret ptr %retval
+}
+
+define void @test02(ptr %a, ptr %b, i32 %c) {
+entry:
+  %tobool.not = icmp eq i32 %c, 0
+  %retval = select i1 %tobool.not, ptr unknown_provenance, ptr %a
+; CHECK: UnknownProvenance not on the ptr_provenance path
+; CHECK-NEXT: store i32 %c, ptr %retval
+; CHECK-NEXT:1
+  store i32 %c, ptr %retval
+  ret void
+}
+
+define void @test03(ptr %a, ptr %b, i32 %c) {
+entry:
+  %tobool.not = icmp eq i32 %c, 0
+  %retval = select i1 %tobool.not, ptr unknown_provenance, ptr %a
+; CHECK-NOT: store i32 %c, ptr %b, ptr_provenance ptr %retval
+  store i32 %c, ptr %b, ptr_provenance ptr %retval
+  ret void
+}
+; CHECK-NOT: UnknownProvenance not on the ptr_provenance path
+
+@t = global i32 0, align 4
+
+define void @test04(ptr %a, i32 %c) {
+entry:
+  %0 = load volatile i32, ptr @t, align 4
+  %tobool.not1 = icmp eq i32 %0, 0
+  br i1 %tobool.not1, label %while.end, label %while.body
+
+while.body:                                       ; preds = %entry, %while.body
+  %c.addr.03 = phi i32 [ %inc, %while.body ], [ %c, %entry ]
+  %a.addr.02 = phi ptr [ %incdec.ptr, %while.body ], [ %a, %entry ]
+  %prov.a = phi ptr [  unknown_provenance, %while.body ], [ %a, %entry ]
+  %inc = add nsw i32 %c.addr.03, 1
+  %incdec.ptr = getelementptr inbounds i32, ptr %a.addr.02, i64 1
+  store i32 %c.addr.03, ptr %a.addr.02, ptr_provenance ptr %prov.a, align 4
+  %1 = load volatile i32, ptr @t, align 4
+  %tobool.not = icmp eq i32 %1, 0
+  br i1 %tobool.not, label %while.end, label %while.body
+
+while.end:                                        ; preds = %while.body, %entry
+  ret void
+}
+
+define void @test05(ptr %a, i32 %c) {
+entry:
+  %0 = load volatile i32, ptr @t, align 4
+  %tobool.not1 = icmp eq i32 %0, 0
+  br i1 %tobool.not1, label %while.end, label %while.body
+
+while.body:                                       ; preds = %entry, %while.body
+  %c.addr.03 = phi i32 [ %inc, %while.body ], [ %c, %entry ]
+  %a.addr.02 = phi ptr [ %incdec.ptr, %while.body ], [ %a, %entry ]
+  %prov.a = phi ptr [  unknown_provenance, %while.body ], [ %a, %entry ]
+  %inc = add nsw i32 %c.addr.03, 1
+  %incdec.ptr = getelementptr inbounds i32, ptr %a.addr.02, i64 1
+  store i32 %c.addr.03, ptr %prov.a, ptr_provenance ptr %a.addr.02, align 4
+  %1 = load volatile i32, ptr @t, align 4
+  %tobool.not = icmp eq i32 %1, 0
+  br i1 %tobool.not, label %while.end, label %while.body
+
+while.end:                                        ; preds = %while.body, %entry
+  ret void
+}
+; CHECK:        UnknownProvenance not on the ptr_provenance path
+; CHECK-NEXT:   store i32 %c.addr.03, ptr %prov.a, ptr_provenance ptr %a.addr.02, align 4
+; CHECK-NEXT:   1
+
+; CHECK-NOT: UnknownProvenance not on the ptr_provenance path