[Verifier] Check for TBAA Access Tag presence

[lebedev.ri]

Summary

I don't really know if this is useful or not, i was just curious to try to make something like this.

There may be several use-cases:

• Verify that front-end indeed did mark every instruction that could have such a TBAA Access Tag (TBAAVerifier::CouldHaveTBAAAccessTag()) with the tag.
• Assuming that the input is ok (see previous point), verify that the passes don't loose these tags, don't.

The design is very simplistic right now:

• One option to toggle the check (default to off)
• One option on how to treat the missing access tag:
  • Treat any missing tag as a fatal error
  • Missing tag is never a error
  • If there is at least one instruction that is tagged, then a missing tag is an error.

The last option makes sense to be the default, e.g. because one can globally disable TBAA info
(-O0, -fno-strict-aliasing?), and then *nothing* is tagged. Since we can't know beforehand
if there is a TBAA metadata, i simply track whether we have seen any tagged instructions,
and decide whether this is a fatal error at the end.

An observation: while trying to test, i have *quickly* found this very simple test,

input.cpp58 BDownload

,
in which the loads/stores aren't being tagged (with roughly -O1 -fstrict-aliasing + verifier enabled).
I'm sure there are more.

Now, question[s]:

• If TBAA is enabled, are there valid (i.e. not a bug) cases where these missing tags are genuinely ok/intentional? That would make this way less useful.
• Does this have any actual use cases? (no is an ok answer, too)
• Should i try to look into this further, look into missing tags?

[lebedev.ri]

Had a brief chat with @rjmccall about this, it seems this is conceptually fine, so let's turn this into an actual review.

[kosarev]

lib/IR/Verifier.cpp

5037–5038

We generate a significant amount of such instructions that are not supposed to be decorated. See for example D41562 and D39138. For my local experiments I was adding marks associated with load and store instructions that give a clue on their origin. If we can have such a mechanism in the mainline to make things like this patch more useful, then that would be great.

[lebedev.ri]

Thank you @kosarev, i will dig deeper.

lib/IR/Verifier.cpp

5037–5038

We generate a significant amount of such instructions that are not supposed to be decorated.

Aha, interesting.

For my local experiments I was adding marks associated with load and store instructions that give a clue on their origin.

I did not look into details, but that sounds bad. It's kind-of a 'chicken and egg' problem.
We'd basically need a verifier to make sure *that* info is not lost :/

include/llvm/IR/Verifier.h

class TBAAVerifier {
   /// @}
 
 public:
   TBAAVerifier(VerifierSupport *Diagnostic = nullptr)
       : Diagnostic(Diagnostic) {}
   /// Visit an instruction and return true if it is valid, return false if an
   /// invalid TBAA is attached.
   bool visitTBAAMetadata(Instruction &I, const MDNode *MD);
+
+  static bool ShouldHaveTBAAAccessTag(Instruction &I);
+  static bool CouldHaveTBAAAccessTag(Instruction &I);
 };
 
 /// \brief Check a function for errors, useful for use when debugging a
 /// pass.
 ///
 /// If there are no errors, the function returns false. If an error is found,
 /// a message describing the error is written to OS (if non-null) and true is
 /// returned.

lib/IR/Verifier.cpp

 #include <cassert>
 #include <cstdint>
 #include <memory>
 #include <string>
 #include <utility>
 
 using namespace llvm;
 
+static cl::opt<bool> VerifyTBAAAccessTagsPresense(
+    "verify-tbaa-tags",
+    cl::desc("Should the presence of TBAA Access Tags be checked"), cl::Hidden,
+    cl::init(false));
+
+enum class TBAAAccessTagsLevel { Never, Partial, Always };
+static cl::opt<TBAAAccessTagsLevel> VerifyTBAAAccessTagsFatality(
+    "verify-tbaa-tags-fatal",
+    cl::desc("If the tag is missing, when is that a fatal error"),
+    cl::values(clEnumValN(TBAAAccessTagsLevel::Never, "never",
+                          "missing tag is never a fatal error"),
+               clEnumValN(TBAAAccessTagsLevel::Partial, "partial",
+                          "if only some tags are missing, not all of them"),
+               clEnumValN(TBAAAccessTagsLevel::Always, "always",
+                          "any missing tag is always a fatal error")),
+    cl::Hidden, cl::init(TBAAAccessTagsLevel::Partial));
+
 namespace llvm {
 
 struct VerifierSupport {
   raw_ostream *OS;
   const Module &M;
   ModuleSlotTracker MST;
   const DataLayout &DL;
   LLVMContext &Context;
 
   /// Track the brokenness of the module while recursively visiting.
   bool Broken = false;
   /// Broken debug info can be "recovered" from by stripping the debug info.
   bool BrokenDebugInfo = false;
   /// Whether to treat broken debug info as an error.
   bool TreatBrokenDebugInfoAsError = true;
+  /// Was any appropriate instruction not tagged with a TBAA Access Tag?
+  bool MissingTBAAAccessTags = false;
 
   explicit VerifierSupport(raw_ostream *OS, const Module &M)
       : OS(OS), M(M), MST(&M), DL(M.getDataLayout()), Context(M.getContext()) {}
 
 private:
   void Write(const Module *M) {
     *OS << "; ModuleID = '" << M->getModuleIdentifier() << "'\n";
   }
public:
   /// A debug info check failed (with values to print).
   template <typename T1, typename... Ts>
   void DebugInfoCheckFailed(const Twine &Message, const T1 &V1,
                             const Ts &... Vs) {
     DebugInfoCheckFailed(Message);
     if (OS)
       WriteTs(V1, Vs...);
   }
+
+  /// A TBAA Access Tag presense check failed.
+  void TBAAAccessTagsCheckFailed(const Twine &Message) {
+    if (OS)
+      *OS << Message << '\n';
+    MissingTBAAAccessTags = true;
+  }
+
+  /// A TBAA Access Tag presense check failed (with values to print).
+  template <typename T1, typename... Ts>
+  void TBAAAccessTagsCheckFailed(const Twine &Message, const T1 &V1,
+                                 const Ts &... Vs) {
+    TBAAAccessTagsCheckFailed(Message);
+    if (OS)
+      WriteTs(V1, Vs...);
+  }
 };
 
 } // namespace llvm
 
 namespace {
 
 class Verifier : public InstVisitor<Verifier>, VerifierSupport {
   friend class InstVisitor<Verifier>;
class Verifier : public InstVisitor<Verifier>, VerifierSupport {
 
   /// \brief Whether we've seen a call to @llvm.localescape in this function
   /// already.
   bool SawFrameEscape;
 
   /// Whether the current function has a DISubprogram attached to it.
   bool HasDebugInfo = false;
 
+  /// Whether we have seen any TBAA Access tags on appropriate instructions.
+  bool SeenTBAAAccessTags = false;
+
   /// Stores the count of how many objects were passed to llvm.localescape for a
   /// given function and the largest index passed to llvm.localrecover.
   DenseMap<Function *, std::pair<unsigned, unsigned>> FrameEscapeInfo;
 
   // Maps catchswitches and cleanuppads that unwind to siblings to the
   // terminators that indicate the unwind, used to detect cycles therein.
   MapVector<Instruction *, TerminatorInst *> SiblingFuncletInfo;
 
explicit Verifier(raw_ostream *OS, bool ShouldTreatBrokenDebugInfoAsError,
                     const Module &M)
       : VerifierSupport(OS, M), LandingPadResultTy(nullptr),
         SawFrameEscape(false), TBAAVerifyHelper(this) {
     TreatBrokenDebugInfoAsError = ShouldTreatBrokenDebugInfoAsError;
   }
 
   bool hasBrokenDebugInfo() const { return BrokenDebugInfo; }
 
+  bool hasBrokenTBAAInfo() const {
+    switch (VerifyTBAAAccessTagsFatality) {
+    case TBAAAccessTagsLevel::Never:
+      return false;
+    case TBAAAccessTagsLevel::Partial:
+      return SeenTBAAAccessTags && MissingTBAAAccessTags;
+    case TBAAAccessTagsLevel::Always:
+      return MissingTBAAAccessTags;
+    };
+  }
+
   bool verify(const Function &F) {
     assert(F.getParent() == &M &&
            "An instance of this class only works with a specific module!");
 
     // First ensure the function is well-enough formed to compute dominance
     // information, and directly compute a dominance tree. We don't rely on the
     // pass manager to provide this as it isolates us from a potentially
     // out-of-date dominator tree and makes it significantly more complex to run
for (const BasicBlock &BB : F) {
       }
       return false;
     }
 
     Broken = false;
     // FIXME: We strip const here because the inst visitor strips const.
     visit(const_cast<Function &>(F));
     verifySiblingFuncletUnwinds();
+    Broken |= hasBrokenTBAAInfo();
+
     InstsInThisBlock.clear();
     DebugFnArgs.clear();
     LandingPadResultTy = nullptr;
     SawFrameEscape = false;
     SiblingFuncletInfo.clear();
 
     return !Broken;
   }
void Verifier::visitInstruction(Instruction &I) {
   }
 
   if (MDNode *MD = I.getMetadata(LLVMContext::MD_dereferenceable))
     visitDereferenceableMetadata(I, MD);
 
   if (MDNode *MD = I.getMetadata(LLVMContext::MD_dereferenceable_or_null))
     visitDereferenceableMetadata(I, MD);
 
-  if (MDNode *TBAA = I.getMetadata(LLVMContext::MD_tbaa))
+  if (MDNode *TBAA = I.getMetadata(LLVMContext::MD_tbaa)) {
     TBAAVerifyHelper.visitTBAAMetadata(I, TBAA);
+    SeenTBAAAccessTags = true;
+  } else if (VerifyTBAAAccessTagsPresense &&
+             TBAAVerifier::ShouldHaveTBAAAccessTag(I))
+    TBAAAccessTagsCheckFailed("Instruction is missing a TBAA access tag.", &I);
 
   if (MDNode *AlignMD = I.getMetadata(LLVMContext::MD_align)) {
     Assert(I.getType()->isPointerTy(), "align applies only to pointer types",
            &I);
     Assert(isa<LoadInst>(I), "align applies only to load instructions, "
            "use attributes for calls or invokes", &I);
     Assert(AlignMD->getNumOperands() == 1, "align takes one operand!", &I);
     ConstantInt *CI = mdconst::dyn_extract<ConstantInt>(AlignMD->getOperand(0));
static bool isNewFormatTBAATypeNode(llvm::MDNode *Type) {
   // its first operand.
   MDNode *Parent = dyn_cast_or_null<MDNode>(Type->getOperand(0));
   if (!Parent)
     return false;
 
   return true;
 }
 
+bool TBAAVerifier::ShouldHaveTBAAAccessTag(Instruction &I) {
+  return isa<LoadInst>(I) || isa<StoreInst>(I) || isa<VAArgInst>(I) ||
+         isa<AtomicRMWInst>(I) || isa<AtomicCmpXchgInst>(I);
+}
+
+bool TBAAVerifier::CouldHaveTBAAAccessTag(Instruction &I) {
+  return ShouldHaveTBAAAccessTag(I) || isa<CallInst>(I);
+}
+
 bool TBAAVerifier::visitTBAAMetadata(Instruction &I, const MDNode *MD) {
-  AssertTBAA(isa<LoadInst>(I) || isa<StoreInst>(I) || isa<CallInst>(I) ||
-                 isa<VAArgInst>(I) || isa<AtomicRMWInst>(I) ||
-                 isa<AtomicCmpXchgInst>(I),
+  AssertTBAA(CouldHaveTBAAAccessTag(I),
              "This instruction shall not have a TBAA access tag!", &I);
 
   bool IsStructPathTBAA =
       isa<MDNode>(MD->getOperand(0)) && MD->getNumOperands() >= 3;
 
   AssertTBAA(
       IsStructPathTBAA,
       "Old-style TBAA is no longer allowed, use struct-path TBAA instead", &I);

test/Verifier/tbaa-tag-missing.ll

+; RUN: opt -verify -verify-tbaa-tags < %s 2>&1 | FileCheck %s
+; RUN: opt -verify -verify-tbaa-tags -verify-tbaa-tags-fatal=never < %s 2>&1 | FileCheck %s
+; RUN: opt -verify -verify-tbaa-tags -verify-tbaa-tags-fatal=partial < %s 2>&1 | FileCheck %s
+; RUN: not opt -verify -verify-tbaa-tags -verify-tbaa-tags-fatal=always < %s 2>&1 | FileCheck %s -check-prefixes=CHECK,CHECK-ERROR
+
+declare void @callee()
+declare void @llvm.va_start(i8*) nounwind
+
+; None of the instructions are marked with a TBAA access tag.
+
+define void @f_0(i8* %ptr, ...) {
+; TMPOFF: Instruction is missing a TBAA access tag.
+; TMPOFF-NEXT:   call void @llvm.va_start(i8* %args)
+; CHECK: Instruction is missing a TBAA access tag.
+; CHECK-NEXT:   %old = atomicrmw add i8* %ptr, i8 0 seq_cst
+; CHECK: Instruction is missing a TBAA access tag.
+; CHECK-NEXT:   %pair = cmpxchg i8* %ptr, i8 0, i8 1 acquire acquire
+; CHECK: Instruction is missing a TBAA access tag.
+; CHECK-NEXT:   %ld = load i8, i8* %ptr
+; CHECK: Instruction is missing a TBAA access tag.
+; CHECK-NEXT:   store i8 1, i8* %ptr
+; TMPOFF: Instruction is missing a TBAA access tag.
+; TMPOFF-NEXT:   call void @callee()
+
+  %args = alloca i8, align 8
+  call void @llvm.va_start(i8* %args)
+
+  %old = atomicrmw add i8* %ptr, i8 0 seq_cst
+  %pair = cmpxchg i8* %ptr, i8 0, i8 1 acquire acquire
+  %ld = load i8, i8* %ptr
+  store i8 1, i8* %ptr
+  call void @callee()
+  %argval = va_arg i8* %args, i8
+
+  ret void
+}
+
+; CHECK-NOT: input module is broken
+; CHECK-ERROR: input module is broken
+
+; We can't actually know whether this metadata is in the module,
+;so it does not matter. We only check the tags.
+!0 = !{!"root"}
+!1 = !{!"scalar-a", !0}

test/Verifier/tbaa-tag-partially-missing.ll

+; RUN: not opt -verify -verify-tbaa-tags < %s 2>&1 | FileCheck %s -check-prefixes=CHECK,CHECK-ERROR
+; RUN: opt -verify -verify-tbaa-tags -verify-tbaa-tags-fatal=never < %s 2>&1 | FileCheck %s
+; RUN: not opt -verify -verify-tbaa-tags -verify-tbaa-tags-fatal=partial < %s 2>&1 | FileCheck %s -check-prefixes=CHECK,CHECK-ERROR
+; RUN: not opt -verify -verify-tbaa-tags -verify-tbaa-tags-fatal=always < %s 2>&1 | FileCheck %s -check-prefixes=CHECK,CHECK-ERROR
+
+declare void @callee()
+declare void @llvm.va_start(i8*) nounwind
+
+define void @f_0(i8* %ptr, ...) {
+; TMPOFF: Instruction is missing a TBAA access tag.
+; TMPOFF-NEXT:   call void @llvm.va_start(i8* %args)
+; CHECK: Instruction is missing a TBAA access tag.
+; CHECK-NEXT:   %old = atomicrmw add i8* %ptr, i8 0 seq_cst
+; CHECK: Instruction is missing a TBAA access tag.
+; CHECK-NEXT:   %pair = cmpxchg i8* %ptr, i8 0, i8 1 acquire acquire
+; CHECK: Instruction is missing a TBAA access tag.
+; CHECK-NEXT:   %ld = load i8, i8* %ptr
+; CHECK: Instruction is missing a TBAA access tag.
+; CHECK-NEXT:   store i8 1, i8* %ptr
+; TMPOFF: Instruction is missing a TBAA access tag.
+; TMPOFF-NEXT:   call void @callee()
+
+  %args = alloca i8, align 8
+  call void @llvm.va_start(i8* %args)
+
+  %old = atomicrmw add i8* %ptr, i8 0 seq_cst
+  %pair = cmpxchg i8* %ptr, i8 0, i8 1 acquire acquire
+  %ld = load i8, i8* %ptr
+  store i8 1, i8* %ptr
+  call void @callee()
+  %argval = va_arg i8* %args, i8
+
+  ; One instruction witn TBAA access tag not omitted.
+  call void @callee(), !tbaa !{!1, !1, i64 0}
+
+  ret void
+}
+
+; CHECK-NOT: input module is broken
+; CHECK-ERROR: input module is broken
+
+!0 = !{!"root"}
+!1 = !{!"scalar-a", !0}

test/Verifier/tbaa-tag-present.ll

+; RUN: opt -verify -verify-tbaa-tags < %s
+; RUN: opt -verify -verify-tbaa-tags -verify-tbaa-tags-fatal=never < %s
+; RUN: opt -verify -verify-tbaa-tags -verify-tbaa-tags-fatal=partial < %s
+; RUN: opt -verify -verify-tbaa-tags -verify-tbaa-tags-fatal=always < %s
+
+declare void @callee()
+declare void @llvm.va_start(i8*) nounwind
+
+; All the instructions are marked with a TBAA access tag.
+
+define void @f_0(i8* %ptr, ...) {
+  %args = alloca i8, align 8
+
+  call void @llvm.va_start(i8* %args),                  !tbaa !{!1, !1, i64 0}
+  %old = atomicrmw add i8* %ptr, i8 0 seq_cst,          !tbaa !{!1, !1, i64 0}
+  %pair = cmpxchg i8* %ptr, i8 0, i8 1 acquire acquire, !tbaa !{!1, !1, i64 0}
+  %ld = load i8, i8* %ptr,                              !tbaa !{!1, !1, i64 0}
+  store i8 1, i8* %ptr,                                 !tbaa !{!1, !1, i64 0}
+  call void @callee(),                                  !tbaa !{!1, !1, i64 0}
+  %argval = va_arg i8* %args, i8,                       !tbaa !{!1, !1, i64 0}
+  ret void
+}
+
+!0 = !{!"root"}
+!1 = !{!"scalar-a", !0}