[unknown_provenance] Verifier: check it only exists on the ptr_provenance path

[jeroen.dobbelaere]

Summary

Check that the unknown_provenance is onyl found on the ptr_provenance path of specific instructions (load/store/llvm.experimental.ptr.provenance).

[jeroen.dobbelaere]

Rebased to ef545ef62a833152d8975ff16333b57cc41befcc (Jan 9, 2023)

[asbirlea]

llvm/test/Verifier/unknown_provenance.ll

3

Could you add a comment for each of tests on the case being verified?

36

nit: move tests 03 and 04 at the end as valid, following all invalid? Can a single CHECK-NOT: be used then for all valid tests?

[jeroen.dobbelaere]

Rebased to: 8c7cfa357280dd93d33b10bbba0fe33797e27d63 (Feb 14, 2023)

[asbirlea]

lgtm.

llvm/lib/IR/Verifier.cpp

class Verifier : public InstVisitor<Verifier>, VerifierSupport {
 
   // Keeps track of duplicate function argument debug info.
   SmallVector<const DILocalVariable *, 16> DebugFnArgs;
 
   TBAAVerifier TBAAVerifyHelper;
 
   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:
   explicit Verifier(raw_ostream *OS, bool ShouldTreatBrokenDebugInfoAsError,
                     const Module &M)
       : VerifierSupport(OS, M), LandingPadResultTy(nullptr),
         SawFrameEscape(false), TBAAVerifyHelper(this) {
     TreatBrokenDebugInfoAsError = ShouldTreatBrokenDebugInfoAsError;
bool verify(const Function &F) {
     verifySiblingFuncletUnwinds();
     InstsInThisBlock.clear();
     DebugFnArgs.clear();
     LandingPadResultTy = nullptr;
     SawFrameEscape = false;
     SiblingFuncletInfo.clear();
     verifyNoAliasScopeDecl();
     NoAliasScopeDecls.clear();
+    verifyUnknownProvenanceUsage();
+    UnknownProvenanceUsers.clear();
 
     return !Broken;
   }
 
   /// Verify the module that this instance of \c Verifier was initialized with.
   bool verify() {
     Broken = false;
 
#include "llvm/IR/Metadata.def"
   void verifyAttachedCallBundle(const CallBase &Call,
                                 const OperandBundleUse &BU);
 
   /// Verify all-or-nothing property of DIFile source attribute within a CU.
   void verifySourceDebugInfo(const DICompileUnit &U, const DIFile &F);
 
   /// Verify the llvm.experimental.noalias.scope.decl declarations
   void verifyNoAliasScopeDecl();
+
+  /// Verify the usage of UnknownProvenance
+  void verifyUnknownProvenanceUsage();
 };
 
 } // end anonymous namespace
 
 /// We know that cond should be true, if not print an error message.
 #define Check(C, ...)                                                          \
   do {                                                                         \
     if (!(C)) {                                                                \
if (!(C)) {                                                                \
       DebugInfoCheckFailed(__VA_ARGS__);                                       \
       return;                                                                  \
     }                                                                          \
   } while (false)
 
 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);
 }
 
 // Helper to iterate over indirect users. By returning false, the callback can ask to stop traversing further.
 static void forEachUser(const Value *User,
                         SmallPtrSet<const Value *, 32> &Visited,
                         llvm::function_ref<bool(const Value *)> Callback) {
   if (!Visited.insert(User).second)
if (ItNext - ItCurrent < 32)
             Check(!DT.dominates(I, J),
                   "llvm.experimental.noalias.scope.decl dominates another one "
                   "with the same scope",
                   I);
     ItCurrent = ItNext;
   }
 }
 
+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...
 //===----------------------------------------------------------------------===//
 
 bool llvm::verifyFunction(const Function &f, raw_ostream *OS) {
   Function &F = const_cast<Function &>(f);
 
   // Don't use a raw_null_ostream.  Printing IR is expensive.

llvm/test/Verifier/unknown_provenance.ll

+; RUN: not llvm-as %s -o /dev/null 2>&1 | FileCheck %s
+
+
+; FIXME: test cases for unknown provenance
+
+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