Remove Merge Functions pointer comparisons

[• jrkoenig]

Summary

This patch removes two remaining places where pointer value comparisons
are used to order functions: comparing range annotation metadata, and comparing
block address constants. (These are both rare cases, and so no actual
non-determinism was observed from either case).

The fix for range metadata is simple: the annotation always consists of a pair
of integers, so we just order by those integers.

The fix for block addresses is more subtle. Two constants are the same if they
are the same basic block in the same function, or if they refer to corresponding
basic blocks in each respective function. Note that in the first case, merging
is trivially correct. In the second, the correctness of merging relies on the
fact that the the values of block addresses cannot be compared. This change is
actually an enhancement, as these functions could not previously be merged (see
merge-block-address.ll).

There is still a problem with cross function block addresses, in that constants
pointing to a basic block in a merged function is not updated.

This also more robustly compares floating point constants by all fields of their
semantics, and fixes a dyn_cast/cast mixup.

[jfb]

Missing range metadata tests :-)

lib/Transforms/IPO/MergeFunctions.cpp

536

Could you add a TODO that explains how one could merge functions with different range metadata? The comparison could ignore it, and merging would take the most conservative of the ranges (widest interval, taking caution if there's wrapping, and deleting range information if the range becomes full/emtpy, merging pairs, ...).

543

Range metadata has *pairs* of integers. It has at least two, but can have more:
http://llvm.org/docs/LangRef.html#range-metadata

544

No need for the asserts, since getOperand already asserts.

734

Use a range-based for with F->getBasicBlockList().

743

Need a return here for MSVC.

test/Transforms/MergeFunc/merge-block-address-other-function.ll

7

Remove the auto-generated comments and metadata from the tests (e.g. the #0 below).

test/Transforms/MergeFunc/merge-block-address.ll

57

tail call _Z1fi would be clearer.

100

Same on metadata and comments above.

[• jrkoenig]

Fixed range metadata comparison. Cleaned up tests.

[• jrkoenig]

Fixed typo & expanded TODO

[jfb]

In D12376#234543, @jfb wrote:

Missing range metadata tests :-)

Forgot to git add the range metadata tests?

[• jrkoenig]

Add multi-segment range test.

[• jrkoenig]

(There is already a test/Transforms/MergeFunc/ranges.ll test in the suite.)

[jfb]

lgtm

lib/Transforms/IPO/MergeFunctions.cpp

private:
   /// 5. If types are complex.
   /// Then both Left and Right are to be expanded and their element types will
   /// be checked with the same way. If we get Res != 0 on some stage, return it.
   /// Otherwise return 0.
   /// 6. For all other cases put llvm_unreachable.
   int cmpTypes(Type *TyL, Type *TyR) const;
 
   int cmpNumbers(uint64_t L, uint64_t R) const;
-
   int cmpAPInts(const APInt &L, const APInt &R) const;
   int cmpAPFloats(const APFloat &L, const APFloat &R) const;
   int cmpInlineAsm(const InlineAsm *L, const InlineAsm *R) const;
   int cmpMem(StringRef L, StringRef R) const;
   int cmpAttrs(const AttributeSet L, const AttributeSet R) const;
+  int cmpRangeMetadata(const MDNode* L, const MDNode* R) const;
 
   // The two functions undergoing comparison.
   const Function *FnL, *FnR;
 
   /// Assign serial numbers to values from left function, and values from
   /// right function.
   /// Explanation:
   /// Being comparing functions we need to compare values we meet at left and
int FunctionComparator::cmpAPInts(const APInt &L, const APInt &R) const {
   if (int Res = cmpNumbers(L.getBitWidth(), R.getBitWidth()))
     return Res;
   if (L.ugt(R)) return 1;
   if (R.ugt(L)) return -1;
   return 0;
 }
 
 int FunctionComparator::cmpAPFloats(const APFloat &L, const APFloat &R) const {
-  // TODO: This correctly handles all existing fltSemantics, because they all
-  // have different precisions. This isn't very robust, however, if new types
-  // with different exponent ranges are introduced.
+  // Floats are ordered first by semantics (i.e. float, double, half, etc.),
+  // then by value interpreted as a bitstring (aka APInt).
   const fltSemantics &SL = L.getSemantics(), &SR = R.getSemantics();
   if (int Res = cmpNumbers(APFloat::semanticsPrecision(SL),
                            APFloat::semanticsPrecision(SR)))
     return Res;
+  if (int Res = cmpNumbers(APFloat::semanticsMaxExponent(SL),
+                           APFloat::semanticsMaxExponent(SR)))
+    return Res;
+  if (int Res = cmpNumbers(APFloat::semanticsMinExponent(SL),
+                           APFloat::semanticsMinExponent(SR)))
+    return Res;
+  if (int Res = cmpNumbers(APFloat::semanticsSizeInBits(SL),
+                           APFloat::semanticsSizeInBits(SR)))
+    return Res;
   return cmpAPInts(L.bitcastToAPInt(), R.bitcastToAPInt());
 }
 
 int FunctionComparator::cmpMem(StringRef L, StringRef R) const {
   // Prevent heavy comparison, compare sizes first.
   if (int Res = cmpNumbers(L.size(), R.size()))
     return Res;
 
for (unsigned i = 0, e = L.getNumSlots(); i != e; ++i) {
     }
     if (LI != LE)
       return 1;
     if (RI != RE)
       return -1;
   }
   return 0;
 }
+int FunctionComparator::cmpRangeMetadata(const MDNode* L,
+                                         const MDNode* R) const {
+  if (L == R)
+    return 0;
+  if (!L)
+    return -1;
+  if (!R)
+    return 1;
+  // Range metadata is a sequence of numbers. Make sure they are the same
+  // sequence. 
+  // TODO: Note that as this is metadata, it is possible to drop and/or merge
+  // this data when considering functions to merge. Thus this comparison would
+  // return 0 (i.e. equivalent), but merging would become more complicated
+  // because the ranges would need to be unioned. It is not likely that
+  // functions differ ONLY in this metadata if they are actually the same
+  // function semantically.
+  if (int Res = cmpNumbers(L->getNumOperands(), R->getNumOperands()))
+    return Res;
+  for (size_t I = 0; I < L->getNumOperands(); ++I) {
+    ConstantInt* LLow = mdconst::extract<ConstantInt>(L->getOperand(I));
+    ConstantInt* RLow = mdconst::extract<ConstantInt>(R->getOperand(I));
+    if (int Res = cmpAPInts(LLow->getValue(), RLow->getValue()))
+      return Res;
+  }
+  return 0;
+}
 
 /// Constants comparison:
 /// 1. Check whether type of L constant could be losslessly bitcasted to R
 /// type.
 /// 2. Compare constant contents.
 /// For more details see declaration comments.
 int FunctionComparator::cmpConstants(const Constant *L, const Constant *R) {
 
int FunctionComparator::cmpConstants(const Constant *L, const Constant *R) {
   if (GlobalValueL && GlobalValueR) {
     return cmpGlobalValues(GlobalValueL, GlobalValueR);
   }
 
   if (int Res = cmpNumbers(L->getValueID(), R->getValueID()))
     return Res;
 
   if (const auto *SeqL = dyn_cast<ConstantDataSequential>(L)) {
-    const auto *SeqR = dyn_cast<ConstantDataSequential>(R);
+    const auto *SeqR = cast<ConstantDataSequential>(R);
     // This handles ConstantDataArray and ConstantDataVector. Note that we
     // compare the two raw data arrays, which might differ depending on the host
     // endianness. This isn't a problem though, because the endiness of a module
     // will affect the order of the constants, but this order is the same
     // for a given input module and host platform.
     return cmpMem(SeqL->getRawDataValues(), SeqR->getRawDataValues());
   }
 
case Value::ConstantExprVal: {
     for (unsigned i = 0; i < NumOperandsL; ++i) {
       if (int Res = cmpConstants(cast<Constant>(LE->getOperand(i)),
                                  cast<Constant>(RE->getOperand(i))))
         return Res;
     }
     return 0;
   }
   case Value::BlockAddressVal: {
-    // FIXME: This still uses a pointer comparison. It isn't clear how to remove
-    // this. This only affects programs which take BlockAddresses and store them
-    // as constants, which is limited to interepreters, etc.
-    return cmpNumbers((uint64_t)L, (uint64_t)R);
+    const BlockAddress *LBA = cast<BlockAddress>(L);
+    const BlockAddress *RBA = cast<BlockAddress>(R);
+    if (int Res = cmpValues(LBA->getFunction(), RBA->getFunction()))
+      return Res;
+    if (LBA->getFunction() == RBA->getFunction()) {
+      // They are BBs in the same function. Order by which comes first in the
+      // BB order of the function. This order is deterministic.
+      Function* F = LBA->getFunction();
+      BasicBlock *LBB = LBA->getBasicBlock();
+      BasicBlock *RBB = RBA->getBasicBlock();
+      if (LBB == RBB)
+        return 0;
+      for(BasicBlock &BB : F->getBasicBlockList()) {
+        if (&BB == LBB) {
+          assert(&BB != RBB);
+          return -1;
+        }
+        if (&BB == RBB)
+          return 1;
+      }
+      llvm_unreachable("Basic Block Address does not point to a basic block in "
+                       "its function.");
+      return -1;
+    } else {
+      // cmpValues said the functions are the same. So because they aren't
+      // literally the same pointer, they must respectively be the left and
+      // right functions.
+      assert(LBA->getFunction() == FnL && RBA->getFunction() == FnR);
+      // cmpValues will tell us if these are equivalent BasicBlocks, in the
+      // context of their respective functions.
+      return cmpValues(LBA->getBasicBlock(), RBA->getBasicBlock());
+    }
   }
   default: // Unknown constant, abort.
     DEBUG(dbgs() << "Looking at valueID " << L->getValueID() << "\n");
     llvm_unreachable("Constant ValueID not recognized.");
     return -1;
   }
 }
 
if (int Res =
             cmpNumbers(LI->getAlignment(), cast<LoadInst>(R)->getAlignment()))
       return Res;
     if (int Res =
             cmpNumbers(LI->getOrdering(), cast<LoadInst>(R)->getOrdering()))
       return Res;
     if (int Res =
             cmpNumbers(LI->getSynchScope(), cast<LoadInst>(R)->getSynchScope()))
       return Res;
-    return cmpNumbers((uint64_t)LI->getMetadata(LLVMContext::MD_range),
-                      (uint64_t)cast<LoadInst>(R)->getMetadata(LLVMContext::MD_range));
+    return cmpRangeMetadata(LI->getMetadata(LLVMContext::MD_range),
+        cast<LoadInst>(R)->getMetadata(LLVMContext::MD_range));
   }
   if (const StoreInst *SI = dyn_cast<StoreInst>(L)) {
     if (int Res =
             cmpNumbers(SI->isVolatile(), cast<StoreInst>(R)->isVolatile()))
       return Res;
     if (int Res =
             cmpNumbers(SI->getAlignment(), cast<StoreInst>(R)->getAlignment()))
       return Res;
     if (int Res =
             cmpNumbers(SI->getOrdering(), cast<StoreInst>(R)->getOrdering()))
       return Res;
     return cmpNumbers(SI->getSynchScope(), cast<StoreInst>(R)->getSynchScope());
   }
   if (const CmpInst *CI = dyn_cast<CmpInst>(L))
     return cmpNumbers(CI->getPredicate(), cast<CmpInst>(R)->getPredicate());
   if (const CallInst *CI = dyn_cast<CallInst>(L)) {
     if (int Res = cmpNumbers(CI->getCallingConv(),
                              cast<CallInst>(R)->getCallingConv()))
       return Res;
     if (int Res =
             cmpAttrs(CI->getAttributes(), cast<CallInst>(R)->getAttributes()))
       return Res;
-    return cmpNumbers(
-        (uint64_t)CI->getMetadata(LLVMContext::MD_range),
-        (uint64_t)cast<CallInst>(R)->getMetadata(LLVMContext::MD_range));
+    return cmpRangeMetadata(
+        CI->getMetadata(LLVMContext::MD_range),
+        cast<CallInst>(R)->getMetadata(LLVMContext::MD_range));
   }
   if (const InvokeInst *CI = dyn_cast<InvokeInst>(L)) {
     if (int Res = cmpNumbers(CI->getCallingConv(),
                              cast<InvokeInst>(R)->getCallingConv()))
       return Res;
     if (int Res =
             cmpAttrs(CI->getAttributes(), cast<InvokeInst>(R)->getAttributes()))
       return Res;
-    return cmpNumbers(
-        (uint64_t)CI->getMetadata(LLVMContext::MD_range),
-        (uint64_t)cast<InvokeInst>(R)->getMetadata(LLVMContext::MD_range));
+    return cmpRangeMetadata(
+        CI->getMetadata(LLVMContext::MD_range),
+        cast<InvokeInst>(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;
     for (size_t i = 0, e = LIndices.size(); i != e; ++i) {
       if (int Res = cmpNumbers(LIndices[i], RIndices[i]))

test/Transforms/MergeFunc/merge-block-address-other-function.ll

+; RUN: opt -S -mergefunc < %s | FileCheck %s
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+define i32 @_Z1fi(i32 %i) #0 {
+entry:
+  %retval = alloca i32, align 4
+  %i.addr = alloca i32, align 4
+  store i32 %i, i32* %i.addr, align 4
+  %0 = load i32, i32* %i.addr, align 4
+  %cmp = icmp eq i32 %0, 1
+  br i1 %cmp, label %if.then, label %if.end
+
+if.then:
+  store i32 3, i32* %retval
+  br label %return
+
+if.end:
+  %1 = load i32, i32* %i.addr, align 4
+  %cmp1 = icmp eq i32 %1, 3
+  br i1 %cmp1, label %if.then.2, label %if.end.3
+
+if.then.2:
+  store i32 56, i32* %retval
+  br label %return
+
+if.end.3:
+  store i32 0, i32* %retval
+  br label %return
+
+return:
+  %2 = load i32, i32* %retval
+  ret i32 %2
+}
+
+
+define internal i8* @Afunc(i32* %P) {
+  store i32 1, i32* %P
+  store i32 3, i32* %P
+  ret i8* blockaddress(@_Z1fi, %if.then.2)
+}
+
+define internal i8* @Bfunc(i32* %P) {
+; CHECK-NOT: @Bfunc
+  store i32 1, i32* %P
+  store i32 3, i32* %P
+  ret i8* blockaddress(@_Z1fi, %if.then.2)
+}

test/Transforms/MergeFunc/merge-block-address.ll

+; RUN: opt -S -mergefunc < %s | FileCheck %s
+
+; These two functions are identical. The basic block labels are the same, and
+; induce the same CFG. We are testing that block addresses within different
+; functions are compared by their value, and not based on order. Both functions
+; come from the same C-code, but in the first the two val_0/val_1 basic blocks
+; are in a different order (they were manually switched post-compilation).
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+define i32 @_Z1fi(i32 %i) #0 {
+entry:
+  %i.addr = alloca i32, align 4
+  %ret = alloca i32, align 4
+  %l = alloca i8*, align 8
+  store i32 %i, i32* %i.addr, align 4
+  store i32 0, i32* %ret, align 4
+  store i8* blockaddress(@_Z1fi, %val_0), i8** %l, align 8
+  %0 = load i32, i32* %i.addr, align 4
+  %and = and i32 %0, 256
+  %cmp = icmp eq i32 %and, 0
+  br i1 %cmp, label %if.then, label %if.end
+
+if.then:
+  store i8* blockaddress(@_Z1fi, %val_1), i8** %l, align 8
+  br label %if.end
+
+if.end:
+  %1 = load i8*, i8** %l, align 8
+  br label %indirectgoto
+
+val_1:
+  store i32 42, i32* %ret, align 4
+  br label %end
+
+val_0:
+  store i32 12, i32* %ret, align 4
+  br label %end
+
+
+end:
+  %2 = load i32, i32* %ret, align 4
+  ret i32 %2
+
+indirectgoto:
+  %indirect.goto.dest = phi i8* [ %1, %if.end ]
+  indirectbr i8* %indirect.goto.dest, [label %val_0, label %val_1]
+}
+
+define i32 @_Z1gi(i32 %i) #0 {
+; CHECK-LABEL: define i32 @_Z1gi
+; CHECK-NEXT: tail call i32 @_Z1fi
+; CHECK-NEXT: ret
+entry:
+  %i.addr = alloca i32, align 4
+  %ret = alloca i32, align 4
+  %l = alloca i8*, align 8
+  store i32 %i, i32* %i.addr, align 4
+  store i32 0, i32* %ret, align 4
+  store i8* blockaddress(@_Z1gi, %val_0), i8** %l, align 8
+  %0 = load i32, i32* %i.addr, align 4
+  %and = and i32 %0, 256
+  %cmp = icmp eq i32 %and, 0
+  br i1 %cmp, label %if.then, label %if.end
+
+if.then:
+  store i8* blockaddress(@_Z1gi, %val_1), i8** %l, align 8
+  br label %if.end
+
+if.end:
+  %1 = load i8*, i8** %l, align 8
+  br label %indirectgoto
+
+val_0:
+  store i32 12, i32* %ret, align 4
+  br label %end
+
+val_1:
+  store i32 42, i32* %ret, align 4
+  br label %end
+
+end:
+  %2 = load i32, i32* %ret, align 4
+  ret i32 %2
+
+indirectgoto:
+  %indirect.goto.dest = phi i8* [ %1, %if.end ]
+  indirectbr i8* %indirect.goto.dest, [label %val_0, label %val_1]
+}
+

test/Transforms/MergeFunc/no-merge-block-address-different-labels.ll

+; RUN: opt -S -mergefunc < %s | FileCheck %s
+
+; There is a slight different in these two functions, in that the label values
+; are switched. They are thus not mergeable. This tests that block addresses
+; referring to blocks within each respective compared function are correctly
+; ordered.
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+; Function Attrs: nounwind uwtable
+define i32 @_Z1fi(i32 %i) #0 {
+; CHECK-LABEL: define i32 @_Z1fi
+; CHECK-NEXT: entry:
+; CHECK-NEXT: alloca
+entry:
+  %i.addr = alloca i32, align 4
+  %ret = alloca i32, align 4
+  %l = alloca i8*, align 8
+  store i32 %i, i32* %i.addr, align 4
+  store i32 0, i32* %ret, align 4
+; Right here, this is val_0, and later the if might assign val_1
+  store i8* blockaddress(@_Z1fi, %val_0), i8** %l, align 8
+  %0 = load i32, i32* %i.addr, align 4
+  %and = and i32 %0, 256
+  %cmp = icmp eq i32 %and, 0
+  br i1 %cmp, label %if.then, label %if.end
+
+if.then:
+  store i8* blockaddress(@_Z1fi, %val_1), i8** %l, align 8
+  br label %if.end
+
+if.end:
+  %1 = load i8*, i8** %l, align 8
+  br label %indirectgoto
+
+val_0:
+  store i32 12, i32* %ret, align 4
+  br label %end
+
+val_1:
+  store i32 42, i32* %ret, align 4
+  br label %end
+
+end:
+  %2 = load i32, i32* %ret, align 4
+  ret i32 %2
+
+indirectgoto:
+  %indirect.goto.dest = phi i8* [ %1, %if.end ]
+  indirectbr i8* %indirect.goto.dest, [label %val_0, label %val_1]
+}
+
+; Function Attrs: nounwind uwtable
+define i32 @_Z1gi(i32 %i) #0 {
+; CHECK-LABEL: define i32 @_Z1gi
+; CHECK-NEXT: entry:
+; CHECK-NEXT: alloca
+entry:
+  %i.addr = alloca i32, align 4
+  %ret = alloca i32, align 4
+  %l = alloca i8*, align 8
+  store i32 %i, i32* %i.addr, align 4
+  store i32 0, i32* %ret, align 4
+; This time, we store val_1 initially, and later the if might assign val_0
+  store i8* blockaddress(@_Z1gi, %val_1), i8** %l, align 8
+  %0 = load i32, i32* %i.addr, align 4
+  %and = and i32 %0, 256
+  %cmp = icmp eq i32 %and, 0
+  br i1 %cmp, label %if.then, label %if.end
+
+if.then:
+  store i8* blockaddress(@_Z1gi, %val_0), i8** %l, align 8
+  br label %if.end
+
+if.end:
+  %1 = load i8*, i8** %l, align 8
+  br label %indirectgoto
+
+val_0:
+  store i32 12, i32* %ret, align 4
+  br label %end
+
+val_1:
+  store i32 42, i32* %ret, align 4
+  br label %end
+
+end:
+  %2 = load i32, i32* %ret, align 4
+  ret i32 %2
+
+indirectgoto:
+  %indirect.goto.dest = phi i8* [ %1, %if.end ]
+  indirectbr i8* %indirect.goto.dest, [label %val_1, label %val_0]
+}
+

test/Transforms/MergeFunc/no-merge-block-address-other-function.ll

+; RUN: opt -S -mergefunc < %s | FileCheck %s
+
+; We should not merge these two functions, because the blocks are different.
+; This tests the handling of block addresses from different functions.
+; ModuleID = '<stdin>'
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+
+define internal i8* @Afunc(i32* %P) {
+; CHECK-LABEL: @Afunc
+; CHECK-NEXT: store
+; CHECK-NEXT: store
+; CHECK-NEXT: ret
+  store i32 1, i32* %P
+  store i32 3, i32* %P
+  ret i8* blockaddress(@_Z1fi, %if.then)
+}
+
+define internal i8* @Bfunc(i32* %P) {
+; CHECK-LABEL: @Bfunc
+; CHECK-NEXT: store
+; CHECK-NEXT: store
+; CHECK-NEXT: ret
+  store i32 1, i32* %P
+  store i32 3, i32* %P
+  ret i8* blockaddress(@_Z1fi, %if.then.2)
+}
+
+
+; Function Attrs: nounwind uwtable
+define i32 @_Z1fi(i32 %i) #0 {
+entry:
+  %retval = alloca i32, align 4
+  %i.addr = alloca i32, align 4
+  store i32 %i, i32* %i.addr, align 4
+  %0 = load i32, i32* %i.addr, align 4
+  %cmp = icmp eq i32 %0, 1
+  br i1 %cmp, label %if.then, label %if.end
+
+if.then:
+  store i32 3, i32* %retval
+  br label %return
+
+if.end:
+  %1 = load i32, i32* %i.addr, align 4
+  %cmp1 = icmp eq i32 %1, 3
+  br i1 %cmp1, label %if.then.2, label %if.end.3
+
+if.then.2:
+  store i32 56, i32* %retval
+  br label %return
+
+if.end.3:
+  store i32 0, i32* %retval
+  br label %return
+
+return:
+  %2 = load i32, i32* %retval
+  ret i32 %2
+}