[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

741

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

 
 #ifndef LLVM_TRANSFORMS_UTILS_FUNCTIONCOMPARATOR_H
 #define LLVM_TRANSFORMS_UTILS_FUNCTIONCOMPARATOR_H
 
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/IR/Attributes.h"
 #include "llvm/IR/Instructions.h"
+#include "llvm/IR/Intrinsics.h"
+#include "llvm/IR/Module.h"
 #include "llvm/IR/Operator.h"
 #include "llvm/IR/ValueMap.h"
 #include "llvm/Support/AtomicOrdering.h"
 #include "llvm/Support/Casting.h"
 #include <cstdint>
 #include <tuple>
 
 namespace llvm {
public:
   using FunctionHash = uint64_t;
   static FunctionHash functionHash(Function &);
 
 protected:
   /// Start the comparison.
   void beginCompare() {
     sn_mapL.clear();
     sn_mapR.clear();
+
+    auto *M = FnL->getParent();
+    Fn_dbg_declare = M->getFunction(Intrinsic::getName(Intrinsic::dbg_declare));
+    Fn_dbg_value = M->getFunction(Intrinsic::getName(Intrinsic::dbg_value));
+    Fn_dbg_addr = M->getFunction(Intrinsic::getName(Intrinsic::dbg_addr));
+    Fn_dbg_label = M->getFunction(Intrinsic::getName(Intrinsic::dbg_label));
   }
 
   /// Compares the signature and other general attributes of the two functions.
   int compareSignature() const;
 
   /// Test whether two basic blocks have equivalent behaviour.
   int cmpBasicBlocks(const BasicBlock *BBL, const BasicBlock *BBR) const;
 
protected:
   /// Stage 2: InlineAsm instances are greater than others. If both left and
   ///          right are InlineAsm instances, InlineAsm* pointers casted to
   ///          integers and compared as numbers.
   /// Stage 3: For all other cases we compare order we meet these values in
   ///          their functions. If right value was met first during scanning,
   ///          then left value is greater.
   ///          In another words, we compare serial numbers, for more details
   ///          see comments for sn_mapL and sn_mapR.
-  int cmpValues(const Value *L, const Value *R) const;
+  int cmpValues(const Value *L, const Value *R,
+                bool needToCmpMetadata = true) const;
 
   /// Compare two Instructions for equivalence, similar to
   /// Instruction::isSameOperationAs.
   ///
   /// Stages are listed in "most significant stage first" order:
   /// On each stage below, we do comparison between some left and right
   /// operation parts. If parts are non-equal, we assign parts comparison
   /// result to the operation comparison result and exit from method.
protected:
   /// 6.5.Load: range metadata (as integer ranges)
   /// On this stage its better to see the code, since its not more than 10-15
   /// strings for particular instruction, and could change sometimes.
   ///
   /// Sets \p needToCmpOperands to true if the operands of the instructions
   /// still must be compared afterwards. In this case it's already guaranteed
   /// that both instructions have the same number of operands.
   int cmpOperations(const Instruction *L, const Instruction *R,
-                    bool &needToCmpOperands) const;
+                    bool &needToCmpOperands, bool &needToCmpMetadata) const;
 
   /// cmpType - compares two types,
   /// defines total ordering among the types set.
   ///
   /// Return values:
   /// 0 if types are equal,
   /// -1 if Left is less than Right,
   /// +1 if Left is greater than Right.
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:
private:
   /// defined at the same place.
   /// But, we are still not able to compare operands of PHI nodes, since those
   /// could be operands from further BBs we didn't scan yet.
   /// So it's impossible to use dominance properties in general.
   mutable DenseMap<const Value*, int> sn_mapL, sn_mapR;
 
   // The global state we will use
   GlobalNumberState* GlobalNumbers;
+
+  // @llvm.dbg.* functions, or null if not used in the module
+  Function *Fn_dbg_declare;
+  Function *Fn_dbg_value;
+  Function *Fn_dbg_addr;
+  Function *Fn_dbg_label;
 };
 
 } // end namespace llvm
 
 #endif // LLVM_TRANSFORMS_UTILS_FUNCTIONCOMPARATOR_H

llvm/lib/Transforms/Utils/FunctionComparator.cpp

 }
 
 // Determine whether the two operations are the same except that pointer-to-A
 // and pointer-to-B are equivalent. This should be kept in sync with
 // Instruction::isSameOperationAs.
 // Read method declaration comments for more details.
 int FunctionComparator::cmpOperations(const Instruction *L,
                                       const Instruction *R,
-                                      bool &needToCmpOperands) const {
+                                      bool &needToCmpOperands,
+                                      bool &needToCmpMetadata) const {
   needToCmpOperands = true;
+  needToCmpMetadata = true;
   if (int Res = cmpValues(L, R))
     return Res;
 
   // Differences from Instruction::isSameOperationAs:
   //  * replace type comparison with calls to cmpTypes.
   //  * we test for I->getRawSubclassOptionalData (nuw/nsw/tail) at the top.
   //  * because of the above, we don't test for the tail bit on calls later on.
   if (int Res = cmpNumbers(L->getOpcode(), R->getOpcode()))
if (auto *CBL = dyn_cast<CallBase>(L)) {
     if (int Res = cmpAttrs(CBL->getAttributes(), CBR->getAttributes()))
       return Res;
     if (int Res = cmpOperandBundlesSchema(*CBL, *CBR))
       return Res;
     if (const CallInst *CI = dyn_cast<CallInst>(L))
       if (int Res = cmpNumbers(CI->getTailCallKind(),
                                cast<CallInst>(R)->getTailCallKind()))
         return Res;
+    // Ignore metadata values in debug info intrinsic calls.
+    if (CBL->getCalledFunction() == Fn_dbg_declare)
+      needToCmpMetadata = false;
+    if (CBL->getCalledFunction() == Fn_dbg_value)
+      needToCmpMetadata = false;
+    if (CBL->getCalledFunction() == Fn_dbg_addr)
+      needToCmpMetadata = false;
+    if (CBL->getCalledFunction() == Fn_dbg_label)
+      needToCmpMetadata = false;
     return cmpRangeMetadata(L->getMetadata(LLVMContext::MD_range),
                             R->getMetadata(LLVMContext::MD_range));
   }
   if (const InsertValueInst *IVI = dyn_cast<InsertValueInst>(L)) {
     ArrayRef<unsigned> LIndices = IVI->getIndices();
     ArrayRef<unsigned> RIndices = cast<InsertValueInst>(R)->getIndices();
     if (int Res = cmpNumbers(LIndices.size(), RIndices.size()))
       return Res;
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;
int FunctionComparator::cmpInlineAsm(const InlineAsm *L,
   assert(L->getFunctionType() != R->getFunctionType());
   return 0;
 }
 
 /// Compare two values used by the two functions under pair-wise comparison. If
 /// this is the first time the values are seen, they're added to the mapping so
 /// that we will detect mismatches on next use.
 /// See comments in declaration for more details.
-int FunctionComparator::cmpValues(const Value *L, const Value *R) const {
+int FunctionComparator::cmpValues(const Value *L, const Value *R,
+                                  bool needToCmpMetadata) const {
   // Catch self-reference case.
   if (L == FnL) {
     if (R == FnR)
       return 0;
     return -1;
   }
   if (R == FnR) {
     if (L == FnL)
if (ConstL && ConstR) {
     return cmpConstants(ConstL, ConstR);
   }
 
   if (ConstL)
     return 1;
   if (ConstR)
     return -1;
 
+  if (needToCmpMetadata) {
+    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();
 
   do {
     bool needToCmpOperands = true;
-    if (int Res = cmpOperations(&*InstL, &*InstR, needToCmpOperands))
+    bool needToCmpMetadata = true;
+    if (int Res = cmpOperations(&*InstL, &*InstR, needToCmpOperands,
+                                needToCmpMetadata))
       return Res;
     if (needToCmpOperands) {
       assert(InstL->getNumOperands() == InstR->getNumOperands());
 
       for (unsigned i = 0, e = InstL->getNumOperands(); i != e; ++i) {
         Value *OpL = InstL->getOperand(i);
         Value *OpR = InstR->getOperand(i);
-        if (int Res = cmpValues(OpL, OpR))
+        if (int Res = cmpValues(OpL, OpR, needToCmpMetadata))
           return Res;
         // cmpValues should ensure this is true.
         assert(cmpTypes(OpL->getType(), OpR->getType()) == 0);
       }
     }
 
     ++InstL;
     ++InstR;

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
+}