[TBAA] Drop support for "old style" scalar TBAA

[sanjoy]

Summary

We've had support for auto upgrading old style scalar TBAA access
metadata into the "new" struct path aware TBAA metadata for 3 years now.
The only way to actually generate old style TBAA was explicitly through
the IRBuilder API. I think this is a good time for dropping support for
old style scalar TBAA.

I will start an RFC on llvm-dev on this topic, but I wanted to have a
patch to link to first.

[mehdi_amini]

LGTM.

This is akin to our "unstable" APIs. Only the bitcode backward compatibility is supported.

[mehdi_amini]

Note: the title mislead me to think that you were dropping support from the auto-upgrade path.

[mehdi_amini]

lib/Analysis/TypeBasedAliasAnalysis.cpp

419 ↗

(On Diff #76668)

You could preserve this comment partially?

[manmanren]

Nice clean up!

Can you also update the documentation? I noticed that the language reference manual is still describing the old scalar TBAA. And I am the one to be blamed.

Cheers,
Manman

[sanjoy]

In D26229#589258, @manmanren wrote:

Nice clean up!

Can you also update the documentation? I noticed that the language reference manual is still describing the old scalar TBAA.

Yes, I will. My next steps are to:

1. Add some verification around tbaa nodes so that bad TBAA nodes are caught by the verifier as much as possible
2. Update the language reference

llvm/trunk/lib/Analysis/TypeBasedAliasAnalysis.cpp

 MDNode *MDNode::getMostGenericTBAA(MDNode *A, MDNode *B) {
   if (!A || !B)
     return nullptr;
 
   if (A == B)
     return A;
 
   // For struct-path aware TBAA, we use the access type of the tag.
-  bool StructPath = isStructPathTBAA(A) && isStructPathTBAA(B);
-  if (StructPath) {
-    A = cast_or_null<MDNode>(MutableTBAAStructTagNode(A).getAccessType());
-    if (!A)
-      return nullptr;
-    B = cast_or_null<MDNode>(MutableTBAAStructTagNode(B).getAccessType());
-    if (!B)
-      return nullptr;
-  }
+  assert(isStructPathTBAA(A) && isStructPathTBAA(B) &&
+         "Auto upgrade should have taken care of this!");
 
   SmallSetVector<MDNode *, 4> PathA;
   MutableTBAANode TA(A);
   while (TA.getNode()) {
     if (PathA.count(TA.getNode()))
       report_fatal_error("Cycle found in TBAA metadata.");
     PathA.insert(TA.getNode());
     TA = TA.getParent();
MDNode *MDNode::getMostGenericTBAA(MDNode *A, MDNode *B) {
   while (IA >= 0 && IB >= 0) {
     if (PathA[IA] == PathB[IB])
       Ret = PathA[IA];
     else
       break;
     --IA;
     --IB;
   }
-  if (!StructPath)
-    return Ret;
 
   if (!Ret)
     return nullptr;
   // We need to convert from a type node to a tag node.
   Type *Int64 = IntegerType::get(A->getContext(), 64);
   Metadata *Ops[3] = {Ret, Ret,
                       ConstantAsMetadata::get(ConstantInt::get(Int64, 0))};
   return MDNode::get(A->getContext(), Ops);
N.NoAlias =
         MDNode::intersect(N.NoAlias, getMetadata(LLVMContext::MD_noalias));
   else
     N.NoAlias = getMetadata(LLVMContext::MD_noalias);
 }
 
 /// Aliases - Test whether the type represented by A may alias the
 /// type represented by B.
 bool TypeBasedAAResult::Aliases(const MDNode *A, const MDNode *B) const {
-  // Make sure that both MDNodes are struct-path aware.
-  if (isStructPathTBAA(A) && isStructPathTBAA(B))
-    return PathAliases(A, B);
-
-  // Keep track of the root node for A and B.
-  TBAANode RootA, RootB;
-
-  // Climb the tree from A to see if we reach B.
-  for (TBAANode T(A);;) {
-    if (T.getNode() == B)
-      // B is an ancestor of A.
-      return true;
-
-    RootA = T;
-    T = T.getParent();
-    if (!T.getNode())
-      break;
-  }
-
-  // Climb the tree from B to see if we reach A.
-  for (TBAANode T(B);;) {
-    if (T.getNode() == A)
-      // A is an ancestor of B.
-      return true;
-
-    RootB = T;
-    T = T.getParent();
-    if (!T.getNode())
-      break;
-  }
-
-  // Neither node is an ancestor of the other.
-
-  // If they have different roots, they're part of different potentially
-  // unrelated type systems, so we must be conservative.
-  if (RootA.getNode() != RootB.getNode())
-    return true;
-
-  // If they have the same root, then we've proved there's no alias.
-  return false;
-}
-
-/// Test whether the struct-path tag represented by A may alias the
-/// struct-path tag represented by B.
-bool TypeBasedAAResult::PathAliases(const MDNode *A, const MDNode *B) const {
-  // Verify that both input nodes are struct-path aware.
+  // Verify that both input nodes are struct-path aware.  Auto-upgrade should
+  // have taken care of this.
   assert(isStructPathTBAA(A) && "MDNode A is not struct-path aware.");
   assert(isStructPathTBAA(B) && "MDNode B is not struct-path aware.");
 
   // Keep track of the root node for A and B.
   TBAAStructTypeNode RootA, RootB;
   TBAAStructTagNode TagA(A), TagB(B);
 
   // TODO: We need to check if AccessType of TagA encloses AccessType of

llvm/trunk/lib/IR/Verifier.cpp

private:
   void visitModuleFlags(const Module &M);
   void visitModuleFlag(const MDNode *Op,
                        DenseMap<const MDString *, const MDNode *> &SeenIDs,
                        SmallVectorImpl<const MDNode *> &Requirements);
   void visitFunction(const Function &F);
   void visitBasicBlock(BasicBlock &BB);
   void visitRangeMetadata(Instruction& I, MDNode* Range, Type* Ty);
   void visitDereferenceableMetadata(Instruction& I, MDNode* MD);
+  void visitTBAAMetadata(Instruction &I, MDNode *MD);
 
   template <class Ty> bool isValidMetadataArray(const MDTuple &N);
 #define HANDLE_SPECIALIZED_MDNODE_LEAF(CLASS) void visit##CLASS(const CLASS &N);
 #include "llvm/IR/Metadata.def"
   void visitDIScope(const DIScope &N);
   void visitDIVariable(const DIVariable &N);
   void visitDILexicalBlockBase(const DILexicalBlockBase &N);
   void visitDITemplateParameter(const DITemplateParameter &N);
Assert(isa<LoadInst>(I),
          " instructions, use attributes for calls or invokes", &I);
   Assert(MD->getNumOperands() == 1, "dereferenceable, dereferenceable_or_null "
          "take one operand!", &I);
   ConstantInt *CI = mdconst::dyn_extract<ConstantInt>(MD->getOperand(0));
   Assert(CI && CI->getType()->isIntegerTy(64), "dereferenceable, "
          "dereferenceable_or_null metadata value must be an i64!", &I);
 }
 
+void Verifier::visitTBAAMetadata(Instruction &I, MDNode *MD) {
+  bool IsStructPathTBAA =
+      isa<MDNode>(MD->getOperand(0)) && MD->getNumOperands() >= 3;
+
+  Assert(IsStructPathTBAA,
+         "Old-style TBAA is no longer allowed, use struct-path TBAA instead",
+         &I);
+}
+
 /// verifyInstruction - Verify that an instruction is well formed.
 ///
 void Verifier::visitInstruction(Instruction &I) {
   BasicBlock *BB = I.getParent();
   Assert(BB, "Instruction not embedded in basic block!", &I);
 
   if (!isa<PHINode>(I)) {   // Check that non-phi nodes are not self referential
     for (User *U : I.users()) {
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 *MD = I.getMetadata(LLVMContext::MD_tbaa))
+    visitTBAAMetadata(I, MD);
+
   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));
     Assert(CI && CI->getType()->isIntegerTy(64),

llvm/trunk/unittests/Analysis/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
   Analysis
   AsmParser
   Core
   Support
   )
 
 add_llvm_unittest(AnalysisTests
   AliasAnalysisTest.cpp
   BlockFrequencyInfoTest.cpp
   CallGraphTest.cpp
   CFGTest.cpp
   CGSCCPassManagerTest.cpp
   LazyCallGraphTest.cpp
   LoopPassManagerTest.cpp
   ScalarEvolutionTest.cpp
-  MixedTBAATest.cpp
+  TBAATest.cpp
   ValueTrackingTest.cpp
   UnrollAnalyzer.cpp
   )

llvm/trunk/unittests/Analysis/MixedTBAATest.cpp

-//===--- MixedTBAATest.cpp - Mixed TBAA unit tests ------------------------===//
-//
-//                     The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-
-#include "llvm/Analysis/TypeBasedAliasAnalysis.h"
-#include "llvm/Analysis/AliasAnalysisEvaluator.h"
-#include "llvm/Analysis/Passes.h"
-#include "llvm/IR/Constants.h"
-#include "llvm/IR/Instructions.h"
-#include "llvm/IR/LLVMContext.h"
-#include "llvm/IR/MDBuilder.h"
-#include "llvm/IR/Module.h"
-#include "llvm/IR/LegacyPassManager.h"
-#include "llvm/Support/CommandLine.h"
-#include "gtest/gtest.h"
-
-namespace llvm {
-namespace {
-
-class MixedTBAATest : public testing::Test {
-protected:
-  MixedTBAATest() : M("MixedTBAATest", C), MD(C) {}
-
-  LLVMContext C;
-  Module M;
-  MDBuilder MD;
-  legacy::PassManager PM;
-};
-
-TEST_F(MixedTBAATest, MixedTBAA) {
-  // Setup function.
-  FunctionType *FTy = FunctionType::get(Type::getVoidTy(C),
-                                        std::vector<Type *>(), false);
-  auto *F = cast<Function>(M.getOrInsertFunction("f", FTy));
-  auto *BB = BasicBlock::Create(C, "entry", F);
-  auto IntType = Type::getInt32Ty(C);
-  auto PtrType = Type::getInt32PtrTy(C);
-  auto *Value  = ConstantInt::get(IntType, 42);
-  auto *Addr = ConstantPointerNull::get(PtrType);
-
-  auto *Store1 = new StoreInst(Value, Addr, BB);
-  auto *Store2 = new StoreInst(Value, Addr, BB);
-  ReturnInst::Create(C, nullptr, BB);
-
-  // New TBAA metadata
-  {
-    auto RootMD = MD.createTBAARoot("Simple C/C++ TBAA");
-    auto MD1 = MD.createTBAAScalarTypeNode("omnipotent char", RootMD);
-    auto MD2 = MD.createTBAAScalarTypeNode("int", MD1);
-    auto MD3 = MD.createTBAAStructTagNode(MD2, MD2, 0);
-    Store2->setMetadata(LLVMContext::MD_tbaa, MD3);
-  }
-
-  // Old TBAA metadata
-  {
-    auto RootMD = MD.createTBAARoot("Simple C/C++ TBAA");
-    auto MD1 = MD.createTBAANode("omnipotent char", RootMD);
-    auto MD2 = MD.createTBAANode("int", MD1);
-    Store1->setMetadata(LLVMContext::MD_tbaa, MD2);
-  }
-
-  // Run the TBAA eval pass on a mixture of path-aware and non-path-aware TBAA.
-  // The order of the metadata (path-aware vs non-path-aware) is important,
-  // because the AA eval pass only runs one test per store-pair.
-  const char* args[] = { "MixedTBAATest", "-evaluate-aa-metadata" };
-  cl::ParseCommandLineOptions(sizeof(args) / sizeof(const char*), args);
-  PM.add(createTypeBasedAAWrapperPass());
-  PM.add(createAAEvalPass());
-  PM.run(M);
-}
-
-} // end anonymous namspace
-} // end llvm namespace
-

llvm/trunk/unittests/Analysis/TBAATest.cpp

+//===--- TBAATest.cpp - Mixed TBAA unit tests -----------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Analysis/AliasAnalysisEvaluator.h"
+#include "llvm/Analysis/Passes.h"
+#include "llvm/IR/Constants.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/IR/LLVMContext.h"
+#include "llvm/IR/MDBuilder.h"
+#include "llvm/IR/Module.h"
+#include "llvm/IR/LegacyPassManager.h"
+#include "llvm/IR/Verifier.h"
+#include "llvm/Support/CommandLine.h"
+#include "gtest/gtest.h"
+
+namespace llvm {
+namespace {
+
+class OldTBAATest : public testing::Test {
+protected:
+  OldTBAATest() : M("MixedTBAATest", C), MD(C) {}
+
+  LLVMContext C;
+  Module M;
+  MDBuilder MD;
+};
+
+TEST_F(OldTBAATest, checkVerifierBehavior) {
+  // C++ unit test case to avoid going through the auto upgrade logic.
+
+  FunctionType *FTy = FunctionType::get(Type::getVoidTy(C), {});
+  auto *F = cast<Function>(M.getOrInsertFunction("f", FTy));
+  auto *BB = BasicBlock::Create(C, "entry", F);
+  auto *IntType = Type::getInt32Ty(C);
+  auto *PtrType = Type::getInt32PtrTy(C);
+  auto *SI = new StoreInst(ConstantInt::get(IntType, 42),
+                           ConstantPointerNull::get(PtrType), BB);
+  ReturnInst::Create(C, nullptr, BB);
+
+  auto *RootMD = MD.createTBAARoot("Simple C/C++ TBAA");
+  auto *MD1 = MD.createTBAANode("omnipotent char", RootMD);
+  auto *MD2 = MD.createTBAANode("int", MD1);
+  SI->setMetadata(LLVMContext::MD_tbaa, MD2);
+
+  SmallVector<char, 0> ErrorMsg;
+  raw_svector_ostream Outs(ErrorMsg);
+
+  StringRef ExpectedFailureMsg(
+      "Old-style TBAA is no longer allowed, use struct-path TBAA instead");
+
+  EXPECT_TRUE(verifyFunction(*F, &Outs));
+  EXPECT_TRUE(StringRef(ErrorMsg.begin(), ErrorMsg.size())
+                  .startswith(ExpectedFailureMsg));
+}
+
+} // end anonymous namspace
+} // end llvm namespace