[MergeFunctions] Extend FunctionComparator to account for metadata arguments in intrinsics, and only ignore debug info metadata

[kubamracek]

Summary

See attached testcase that shows the miscompile / mis-merge. Comparing functions for equality is done via FunctionComparator, which ignores metadata attachments and metadata arguments of instructions, with the intention of ignoring/discarding debug info. That's a problem for @llvm.type.checked.load, and other intrinsics where metadata arguments are actually semantically meaningful (e.g. type id in @llvm.type.checked.load).

[nikic]

Shouldn't this be fixed in FunctionComparator?

[kubamracek]

Shouldn't this be fixed in FunctionComparator?

So that's certainly the right question here. Should it? To me it looks like FunctionComparator is ignoring metadata attachments *on purpose*, and that fits the contract of "determine whether 2 functions will generate machine code with the same behavior".

[nikic]

In D112870#3098512, @kubamracek wrote:

Shouldn't this be fixed in FunctionComparator?

So that's certainly the right question here. Should it? To me it looks like FunctionComparator is ignoring metadata attachments *on purpose*, and that fits the contract of "determine whether 2 functions will generate machine code with the same behavior".

I'm reasonably sure that ignoring metadata arguments is just an oversight here -- they probably weren't used outside dbg intrinsics when this code was written. We have things like constrained fp intrinsics with rounding/exception mode determined by metadata arguments nowadays, and treating two fp operations with different rounding mode as equivalent would clearly be incorrect.

[pcc]

In D112870#3098512, @kubamracek wrote:

Shouldn't this be fixed in FunctionComparator?

So that's certainly the right question here. Should it? To me it looks like FunctionComparator is ignoring metadata attachments *on purpose*, and that fits the contract of "determine whether 2 functions will generate machine code with the same behavior".

I think FunctionComparator should be fixed, as the metadata arguments do influence the machine code here (presumably it was assumed that these arguments would only appear on debug intrinsics, where they indeed would not be expected to affect the machine code). Note that the same issue affects llvm.type.test.

[kubamracek]

Thanks for the feedback! I've changed the approach to teach FunctionComparator to understand metadata in instruction operands/values, and only ignore debug info metadata.

[nikic]

I'm not a fan of how dbg intrinsics are handled here. I think if we don't want to compare these, the principled way to do that would be to skip them entirely, something along these lines:

diff --git a/llvm/lib/Transforms/Utils/FunctionComparator.cpp b/llvm/lib/Transforms/Utils/FunctionComparator.cpp
index 326864803d7c..f75b75a57544 100644
--- a/llvm/lib/Transforms/Utils/FunctionComparator.cpp
+++ b/llvm/lib/Transforms/Utils/FunctionComparator.cpp
@@ -791,8 +791,10 @@ int FunctionComparator::cmpValues(const Value *L, const Value *R) const {
 // Test whether two basic blocks have equivalent behaviour.
 int FunctionComparator::cmpBasicBlocks(const BasicBlock *BBL,
                                        const BasicBlock *BBR) const {
-  BasicBlock::const_iterator InstL = BBL->begin(), InstLE = BBL->end();
-  BasicBlock::const_iterator InstR = BBR->begin(), InstRE = BBR->end();
+  auto WithoutDebugL = BBL->instructionsWithoutDebug();
+  auto WithoutDebugR = BBR->instructionsWithoutDebug();
+  auto InstL = WithoutDebugL.begin(), InstLE = WithoutDebugL.end();
+  auto InstR = WithoutDebugR.begin(), InstRE = WithoutDebugR.end();
 
   do {
     bool needToCmpOperands = true;
@@ -962,7 +964,7 @@ FunctionComparator::FunctionHash FunctionComparator::functionHash(Function &F) {
     // This random value acts as a block header, as otherwise the partition of
     // opcodes into BBs wouldn't affect the hash, only the order of the opcodes
     H.add(45798);
-    for (auto &Inst : *BB) {
+    for (auto &Inst : BB->instructionsWithoutDebug()) {
       H.add(Inst.getOpcode());
     }
     const Instruction *Term = BB->getTerminator();

And then always compare metadata operands on top of that.

[kubamracek]

@nikic Awesome suggestion, thanks! I didn't realize we have this nice facility to ignore dbginfo instructions. The diff is now really simple, and still fixes the problem.

[nikic]

llvm/lib/Transforms/Utils/FunctionComparator.cpp

730

I'm concerned that this is going to cause non-determinism, because addresses are not stable. I think we need to either look into the metadata, or assign numbers (like GlobalNumberState).

llvm/include/llvm/Transforms/Utils/FunctionComparator.h

protected:
   int cmpAPFloats(const APFloat &L, const APFloat &R) const;
   int cmpMem(StringRef L, StringRef R) const;
 
   // The two functions undergoing comparison.
   const Function *FnL, *FnR;
 
 private:
   int cmpOrderings(AtomicOrdering L, AtomicOrdering R) const;
+  int cmpMetadataAsValue(const MetadataAsValue *L,
+                         const MetadataAsValue *R) const;
   int cmpInlineAsm(const InlineAsm *L, const InlineAsm *R) const;
   int cmpAttrs(const AttributeList L, const AttributeList R) const;
   int cmpRangeMetadata(const MDNode *L, const MDNode *R) const;
   int cmpOperandBundlesSchema(const CallBase &LCS, const CallBase &RCS) const;
 
   /// Compare two GEPs for equivalent pointer arithmetic.
   /// Parts to be compared for each comparison stage,
   /// most significant stage first:

llvm/lib/Transforms/Utils/FunctionComparator.cpp

int FunctionComparator::cmpGEPs(const GEPOperator *GEPL,
   for (unsigned i = 0, e = GEPL->getNumOperands(); i != e; ++i) {
     if (int Res = cmpValues(GEPL->getOperand(i), GEPR->getOperand(i)))
       return Res;
   }
 
   return 0;
 }
 
+int FunctionComparator::cmpMetadataAsValue(const MetadataAsValue *L,
+                                           const MetadataAsValue *R) const {
+  if (L == R)
+    return 0;
+
+  // Identical metadata is automatically merged, so let's just compare pointer
+  // identity.
+  return L < R ? -1 : 1;
+}
+
 int FunctionComparator::cmpInlineAsm(const InlineAsm *L,
                                      const InlineAsm *R) const {
   // InlineAsm's are uniqued. If they are the same pointer, obviously they are
   // the same, otherwise compare the fields.
   if (L == R)
     return 0;
   if (int Res = cmpTypes(L->getFunctionType(), R->getFunctionType()))
     return Res;
if (ConstL && ConstR) {
     return cmpConstants(ConstL, ConstR);
   }
 
   if (ConstL)
     return 1;
   if (ConstR)
     return -1;
 
+  const MetadataAsValue *MDL = dyn_cast<MetadataAsValue>(L);
+  const MetadataAsValue *MDR = dyn_cast<MetadataAsValue>(R);
+  if (MDL && MDR) {
+    if (L == R)
+      return 0;
+    return cmpMetadataAsValue(MDL, MDR);
+  }
+
+  if (MDL)
+    return 1;
+  if (MDR)
+    return -1;
+
   const InlineAsm *InlineAsmL = dyn_cast<InlineAsm>(L);
   const InlineAsm *InlineAsmR = dyn_cast<InlineAsm>(R);
 
   if (InlineAsmL && InlineAsmR)
     return cmpInlineAsm(InlineAsmL, InlineAsmR);
   if (InlineAsmL)
     return 1;
   if (InlineAsmR)
     return -1;
 
   auto LeftSN = sn_mapL.insert(std::make_pair(L, sn_mapL.size())),
        RightSN = sn_mapR.insert(std::make_pair(R, sn_mapR.size()));
 
   return cmpNumbers(LeftSN.first->second, RightSN.first->second);
 }
 
 // Test whether two basic blocks have equivalent behaviour.
 int FunctionComparator::cmpBasicBlocks(const BasicBlock *BBL,
                                        const BasicBlock *BBR) const {
-  BasicBlock::const_iterator InstL = BBL->begin(), InstLE = BBL->end();
-  BasicBlock::const_iterator InstR = BBR->begin(), InstRE = BBR->end();
+  auto WithoutDebugL = BBL->instructionsWithoutDebug();
+  auto WithoutDebugR = BBR->instructionsWithoutDebug();
+  auto InstL = WithoutDebugL.begin(), InstLE = WithoutDebugL.end();
+  auto InstR = WithoutDebugR.begin(), InstRE = WithoutDebugR.end();
 
   do {
     bool needToCmpOperands = true;
     if (int Res = cmpOperations(&*InstL, &*InstR, needToCmpOperands))
       return Res;
     if (needToCmpOperands) {
       assert(InstL->getNumOperands() == InstR->getNumOperands());
 
FunctionComparator::FunctionHash FunctionComparator::functionHash(Function &F) {
   // accumulating the hash of the function "structure." (BB and opcode sequence)
   BBs.push_back(&F.getEntryBlock());
   VisitedBBs.insert(BBs[0]);
   while (!BBs.empty()) {
     const BasicBlock *BB = BBs.pop_back_val();
     // This random value acts as a block header, as otherwise the partition of
     // opcodes into BBs wouldn't affect the hash, only the order of the opcodes
     H.add(45798);
-    for (auto &Inst : *BB) {
+    for (auto &Inst : BB->instructionsWithoutDebug()) {
       H.add(Inst.getOpcode());
     }
     const Instruction *Term = BB->getTerminator();
     for (unsigned i = 0, e = Term->getNumSuccessors(); i != e; ++i) {
       if (!VisitedBBs.insert(Term->getSuccessor(i)).second)
         continue;
       BBs.push_back(Term->getSuccessor(i));
     }
   }
   return H.getHash();
 }

llvm/test/Transforms/MergeFunc/merge-type-metadata.ll

+; RUN: opt -S -mergefunc < %s | FileCheck %s
+
+; CHECK: @call_vfunc1
+define internal i32 @call_vfunc1(i8* %vtable) unnamed_addr {
+  %a = tail call { i8*, i1 } @llvm.type.checked.load(i8* %vtable, i32 0, metadata !"vtype1")
+  ret i32 0
+}
+
+; CHECK-NOT: @call_vfunc2
+define internal i32 @call_vfunc2(i8* %vtable) unnamed_addr {
+  %a = tail call { i8*, i1 } @llvm.type.checked.load(i8* %vtable, i32 0, metadata !"vtype1")
+  ret i32 0
+}
+
+; CHECK: @call_vfunc3
+define internal i32 @call_vfunc3(i8* %vtable) unnamed_addr {
+  %a = tail call { i8*, i1 } @llvm.type.checked.load(i8* %vtable, i32 0, metadata !"vtype2")
+  ret i32 0
+}
+
+declare { i8*, i1 } @llvm.type.checked.load(i8*, i32, metadata)
+
+define void @main() {
+  %a = call i32 @call_vfunc1(i8* null)
+  ; CHECK: call i32 @call_vfunc1
+  %b = call i32 @call_vfunc2(i8* null)
+  ; CHECK: call i32 @call_vfunc1
+  %c = call i32 @call_vfunc3(i8* null)
+  ; CHECK: call i32 @call_vfunc3
+  ret void
+}