Fix: Distinguish CFI Metadata Checks in MergeFunctions Pass

[oskarwirga]

Summary

This diff fixes an issue in the MergeFunctions pass where two different Control Flow Integrity (CFI) metadata checks were incorrectly considered identical. These merges would lead to runtime violations down the line as two separate objects contained a single destructor which itself contained checks for only one of the objects.

Here I update the comparison logic to take into account the metadata at llvm.type.test checks. Now, only truly identical checks will be considered for merging, thus preserving the integrity of each check.

[nikic]

llvm/lib/Transforms/Utils/FunctionComparator.cpp

665

This doesn't looks like a problem specific to the type.test intrinsic. Other calls may have metadata operands as well.

[oskarwirga]

llvm/lib/Transforms/Utils/FunctionComparator.cpp

665

Should I remove the intrinsic check and instead loop through the arg operands to check that they are the same?

[nikic]

llvm/lib/Transforms/Utils/FunctionComparator.cpp

665

The caller cmpBasicBlocks() already does a loop over the operands and compares them via cmpValues(). So that's probably the place where MetadataAsValue needs to be handled.

[oskarwirga]

Generalize the metadata checks

[smeenai]

llvm/lib/Transforms/Utils/FunctionComparator.cpp

880

Should this be inside cmpValues instead, since that has a bunch of other callers too?

882

Is it correct to just check for pointer equality here? https://llvm.org/docs/LangRef.html#metadata mentions !unique for avoiding content-baed metadata merging, but it wasn't clear if that merging would otherwise always take place.

[oskarwirga]

llvm/lib/Transforms/Utils/FunctionComparator.cpp

882

Yeah you know what maybe what we need to do is add !unique to type test metadata checks because this is too broad and its failing to merge functions with differing debug metadata. We need some way to prevent the CFI metadata as part of the cfi checks from getting merged but we need identical debug metadata (and perhaps other metadata) to get merged.

llvm/test/Transforms/MergeFunc/cfi-function-merging.ll

41

@smeenai @nikic This metadata is pretty generic and I am not entirely sure how CFI knows to populate it later with the correct vtable entry

[oskarwirga]

Added checks for distinct metadata in operands to prevent merging unless it's just debug info. This ensures that distinct metadata, which should be treated as different, is not merged.

[oskarwirga]

ping :^)

[oskarwirga]

ping

[oskarwirga]

ping

[oskarwirga]

ping

[manmanren]

This looks reasonable to me in the sense that it treats distinct metadata as being different but bypasses distinct debug info. CC @dexonsmith

[oskarwirga]

Update to use cmpValues() instead of cmpBasicBlock

[kyulee]

Thanks for fixing this! This seems a good case to cover.

llvm/lib/Transforms/Utils/FunctionComparator.cpp

802

Like the below Constant case below, can you run dyn_cast more explicit to ensure they're not null?.

auto *MDL = cast<MetadataAsValue>(L);
auto *MDR = cast<MetadataAsValue>(R);
if (MDL && MDR) {

878

This space seems unrelated.

[kyulee]

llvm/lib/Transforms/Utils/FunctionComparator.cpp

802

Sorry. I meant dyn_cast not cast.

[kyulee]

llvm/test/Transforms/MergeFunc/cfi-function-merging.ll

34

Can you also simplify the test?
I think you can delete attributes like unnamed_addr #3, #6, align 8, etc.,, to focus on only relevant metadata..

[kyulee]

llvm/lib/Transforms/Utils/FunctionComparator.cpp

808

I think you can drop llvm: as with others.

[oskarwirga]

Address @kyulee 's comments

[dexonsmith]

Sorry, Phabricator lost my comment somehow. Adding back a version of it now.

I don't think it's viable to have the two functions arbitrarily compare "less than" if they both have distinct metadata. That leads to assertions like this:

assert(!(V1<V2 && V2<V1) && "Both values are less than the other?");

firing.

It also makes it undefined behaviour to use the comparator in "sort" algorithms. Have a look at:
https://en.cppreference.com/w/cpp/named_req/LessThanComparable
https://en.wikipedia.org/wiki/Weak_ordering#Strict_weak_orderings

And I assume this is used for sorting somehow?

I suggest changing function merging to check for distinct metadata as a second step, after functions compare equal. But there might be another way.

llvm/lib/Transforms/Utils/FunctionComparator.cpp

810

This breaks strict weak ordering, which means compareValues can never be used for sorting, which I assume is the whole point.

[oskarwirga]

Remove more unnecessary metadata from test

[oskarwirga]

ping

[dexonsmith]

In D154119#4638649, @oskarwirga wrote:

ping

Looks like you're still breaking strict-weak ordering. Is there a reason that's not a problem?

In particular, is it somehow guaranteed that the comparator is never used in a sorting function (where it would lead to undefined behaviour)? If so, how?

[oskarwirga]

llvm/lib/Transforms/Utils/FunctionComparator.cpp

810

I had to consult with ChatGPT about what strict weak ordering is, but IIUC what I am doing wrong here is that I am returning -1 no matter what rather than 1 vs -1 depending on L vs R and R vs L, is my understanding correct here?

[dexonsmith]

llvm/lib/Transforms/Utils/FunctionComparator.cpp

810

Correct. As I suggested in my longer comment, it I suspect it’s better to fix this outside of the compare function.

llvm/lib/Transforms/Utils/FunctionComparator.cpp

 #include "llvm/ADT/Hashing.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/IR/Attributes.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/Constant.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DataLayout.h"
+#include "llvm/IR/DebugInfoMetadata.h"
 #include "llvm/IR/DerivedTypes.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/GlobalValue.h"
 #include "llvm/IR/InlineAsm.h"
 #include "llvm/IR/InstrTypes.h"
 #include "llvm/IR/Instruction.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/LLVMContext.h"
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;
     for (size_t i = 0, e = LIndices.size(); i != e; ++i) {
       if (int Res = cmpNumbers(LIndices[i], RIndices[i]))
         return Res;
     }
     return 0;
   }
   if (const ExtractValueInst *EVI = dyn_cast<ExtractValueInst>(L)) {
     ArrayRef<unsigned> LIndices = EVI->getIndices();
     ArrayRef<unsigned> RIndices = cast<ExtractValueInst>(R)->getIndices();
     if (int Res = cmpNumbers(LIndices.size(), RIndices.size()))
       return Res;
     for (size_t i = 0, e = LIndices.size(); i != e; ++i) {
       if (int Res = cmpNumbers(LIndices[i], RIndices[i]))
int FunctionComparator::cmpInlineAsm(const InlineAsm *L,
   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 {
+  // Distinct metadata is different and shouldn't be merged unless it's
+  // just debug info
+  if (auto *MDL = dyn_cast<MetadataAsValue>(L)) {
+    auto *MDR = cast<MetadataAsValue>(R);
+
+    const MDNode *MDNodeL = dyn_cast<MDNode>(MDL->getMetadata());
+    const MDNode *MDNodeR = dyn_cast<MDNode>(MDR->getMetadata());
+    if (MDNodeL && MDNodeR) {
+      if (MDNodeL->isDistinct() && MDNodeR->isDistinct()) {
+        if (isa<llvm::DINode>(MDNodeL) && isa<llvm::DINode>(MDNodeR))
+          return 0;
+        return -1;
+      }
+      if (MDNodeL->isDistinct()) {
+        return 1;
+      }
+      if (MDNodeR->isDistinct()) {
+        return -1;
+      }
+    }
+  }
+
   // Catch self-reference case.
   if (L == FnL) {
     if (R == FnR)
       return 0;
     return -1;
   }
   if (R == FnR) {
     if (L == FnL)
do {
     if (int Res = cmpOperations(&*InstL, &*InstR, needToCmpOperands))
       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))
           return Res;
         // cmpValues should ensure this is true.
         assert(cmpTypes(OpL->getType(), OpR->getType()) == 0);
       }
     }
 
     ++InstL;
     ++InstR;
   } while (InstL != InstLE && InstR != InstRE);
 
   if (InstL != InstLE && InstR == InstRE)

llvm/test/Transforms/MergeFunc/cfi-function-merging.ll

+;; Check the cases involving internal CFI instrumented functions where we do not expect functions to be merged.
+; RUN: opt -S -passes=mergefunc < %s | FileCheck %s
+
+
+target datalayout = "e-m:e-i8:8:32-i16:16:32-i64:64-i128:128-n32:64-S128"
+target triple = "aarch64-none-linux-android28"
+
+; Function Attrs: nocallback nofree nosync nounwind readnone speculatable willreturn
+declare i1 @llvm.type.test(ptr, metadata) #6
+
+define internal void @A__on_zero_sharedEv(ptr noundef nonnull align 8 dereferenceable(32) %this) unnamed_addr #3 align 2 {
+; CHECK-LABEL: @A__on_zero_sharedEv
+entry:
+  %this.addr = alloca ptr, align 8
+  store ptr %this, ptr %this.addr, align 8
+  %this1 = load ptr, ptr %this.addr, align 8
+  %vtable = load ptr, ptr %this1, align 8
+  %0 = call i1 @llvm.type.test(ptr %vtable, metadata !11), !nosanitize !47
+  ret void
+}
+
+; Function Attrs: mustprogress noinline nounwind optnone uwtable
+define internal void @B__on_zero_sharedEv(ptr noundef nonnull align 8 dereferenceable(32) %this) unnamed_addr #3 align 2 {
+; CHECK-LABEL: @B__on_zero_sharedEv
+entry:
+  %this.addr = alloca ptr, align 8
+  store ptr %this, ptr %this.addr, align 8
+  %this1 = load ptr, ptr %this.addr, align 8
+  %vtable = load ptr, ptr %this1, align 8
+  %0 = call i1 @llvm.type.test(ptr %vtable, metadata !22), !nosanitize !47
+  ret void
+}
+
+attributes #3 = { mustprogress noinline nounwind optnone uwtable "frame-pointer"="non-leaf" "min-legal-vector-width"="0" "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="generic" "target-features"="+fix-cortex-a53-835769,+neon,+outline-atomics,+v8a" }
+attributes #6 = { nocallback nofree nosync nounwind readnone speculatable willreturn }
+
+!10 = !{i64 16, !11}
+!11 = distinct !{}
+!21 = !{i64 16, !22}
+!22 = distinct !{}
+!47 = !{}