[TBAA] Don't generate invalid TBAA when merging nodes

[sanjoy]

Summary

Fix a corner case in MDNode::getMostGenericTBAA where we can sometimes
generate invalid TBAA metadata.

[manmanren]

Cheers,

Manman

lib/Analysis/TypeBasedAliasAnalysis.cpp

462 ↗

(On Diff #77879)

When the only common base is the root node, is it illegal to generate a tag based on the root?

unittests/Analysis/TBAATest.cpp

75 ↗

(On Diff #77879)

Why are we testing the old scalar TBAA here with createTBAANode?

[sanjoy]

lib/Analysis/TypeBasedAliasAnalysis.cpp

462 ↗

(On Diff #77879)

The comment at the top of the file states:

The second field is the access type node, it
// must be a scalar type node.

unittests/Analysis/TBAATest.cpp

75 ↗

(On Diff #77879)

The OldTBAATest name is misleading here, I'll change it to be more generic. However, the only thing we've deprecated and removed support is the using scalar tbaa *tags*. So far I don't see anything in the TBAA implementation that indicates we don't support scalar TBAA *nodes*. For instance, see line 247:

// Fast path for a scalar type node and a struct type node with a single
// field.
if (Node->getNumOperands() <= 3) {
  uint64_t Cur = Node->getNumOperands() == 2
                     ? 0
                     : mdconst::extract<ConstantInt>(Node->getOperand(2))
                           ->getZExtValue();
  Offset -= Cur;
  MDNode *P = dyn_cast_or_null<MDNode>(Node->getOperand(1));
  if (!P)
    return TBAAStructTypeNode();
  return TBAAStructTypeNode(P);
}

Even if removing scalar TBAA nodes completely is going to ultimately be a better final state (I think it will be), the amount of work is non-trivial I'd rather not fold in all of that work in this cleanup work I'm currently doing.

[sanjoy]

• address review comments

[sanjoy]

• Fix test name

[manmanren]

lib/Analysis/TypeBasedAliasAnalysis.cpp

462 ↗

(On Diff #77879)

I see. I was wondering if it caused any compilation failure or miscompile.

unittests/Analysis/TBAATest.cpp

75 ↗

(On Diff #77879)

We have createTBAAScalarTypeNode and it is used by clang currently to generate a scalar type node.
createTBAANode was used by clang with the old TBAA scalar system.

[sanjoy]

lib/Analysis/TypeBasedAliasAnalysis.cpp

462 ↗

(On Diff #77879)

I don't think today it would lead to an actual miscompile. It just breaks the spec and hence the verifier.

unittests/Analysis/TBAATest.cpp

75 ↗

(On Diff #77879)

Yes, but there are out of tree non-clang users who use createTBAANode today.

I agree that it would be nice to get rid of scalar TBAA completely, but I don't want to change too much at once. In particular, I think once D26438 is checked in (I'm also waiting for you to take a look at that one, btw :) ) it will likely break out of tree users since today it is too easy to generate slightly malformed TBAA and not realize it[0]. I want to check in D26438 first, let that bake in for some time, and then ditch scalar tbaa once out of tree users have recovered from D26438.

[0]: For instance, we were generating bad TBAA internally for a while, and things actually worked okay till one day they didn't.

[manmanren]

In particular, I think once D26438 is checked in (I'm also waiting for you to take a look at that one, btw :) )

I will take a look at that soon :)

Manman

llvm/trunk/lib/Analysis/TypeBasedAliasAnalysis.cpp

while (IA >= 0 && IB >= 0) {
     if (PathA[IA] == PathB[IB])
       Ret = PathA[IA];
     else
       break;
     --IA;
     --IB;
   }
 
-  if (!Ret)
+  // We either did not find a match, or the only common base "type" is
+  // the root node.  In either case, we don't have any useful TBAA
+  // metadata to attach.
+  if (!Ret || Ret->getNumOperands() < 2)
     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);
 }
 
 void Instruction::getAAMetadata(AAMDNodes &N, bool Merge) const {

llvm/trunk/unittests/Analysis/TBAATest.cpp

 #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 {
+class TBAATest : public testing::Test {
 protected:
-  OldTBAATest() : M("MixedTBAATest", C), MD(C) {}
+  TBAATest() : M("TBAATest", 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.
-
+static StoreInst *getFunctionWithSingleStore(Module *M, StringRef Name) {
+  auto &C = M->getContext();
   FunctionType *FTy = FunctionType::get(Type::getVoidTy(C), {});
-  auto *F = cast<Function>(M.getOrInsertFunction("f", FTy));
+  auto *F = cast<Function>(M->getOrInsertFunction(Name, 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);
 
+  return SI;
+}
+
+TEST_F(TBAATest, checkVerifierBehaviorForOldTBAA) {
+  auto *SI = getFunctionWithSingleStore(&M, "f1");
+  auto *F = SI->getFunction();
+
+  // C++ unit test case to avoid going through the auto upgrade logic.
   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));
 }
 
+TEST_F(TBAATest, checkTBAAMerging) {
+  auto *SI = getFunctionWithSingleStore(&M, "f2");
+  auto *F = SI->getFunction();
+
+  auto *RootMD = MD.createTBAARoot("tbaa-root");
+  auto *MD1 = MD.createTBAANode("scalar-a", RootMD);
+  auto *StructTag1 = MD.createTBAAStructTagNode(MD1, MD1, 0);
+  auto *MD2 = MD.createTBAANode("scalar-b", RootMD);
+  auto *StructTag2 = MD.createTBAAStructTagNode(MD2, MD2, 0);
+
+  auto *GenericMD = MDNode::getMostGenericTBAA(StructTag1, StructTag2);
+
+  EXPECT_EQ(GenericMD, nullptr);
+
+  // Despite GenericMD being nullptr, we expect the setMetadata call to be well
+  // defined and produce a well-formed function.
+  SI->setMetadata(LLVMContext::MD_tbaa, GenericMD);
+
+  EXPECT_TRUE(!verifyFunction(*F));
+}
+
 } // end anonymous namspace
 } // end llvm namespace