[NFCi][MergeFunctions] Consolidate Hashing Functions

[aidengrossman]

Summary

A couple years ago, StructuralHash was created, copying the exact
hashing implementation from FunctionComparator (minus a couple small
details/refactorings). Since then, the hashing implementation has not
diverged, but several other areas, like unit testing, have diverged
significantly, with StructuralHash getting more attention in these
areas. This patch aims to consolidate the two hashing functions into
StructuralHash given they do the exact same thing and having less
divergence in areas like unit testing would be beneficial.

The original aim at creating a separate StructuralHash was to make the
implementation divergent and capture additional details like instruction
operands (which neither hashing implementation does currently). The
MergeFunctions pass doesn't need these detaisl, but verification of pass
return values would benefit from this additional data. Setting an option
to calculate these values would allow for divergent behavior where
appropriate while reducing code duplication with little runtime
overhead.

[aeubanks]

I think it's important to add comments in StructuralHash that different users of it may want different behavior, so in the future if that's desired we should be able to add flags to tune the behavior of the hashing

but otherwise this seems fine

[aidengrossman]

Address reviewer feedback

• Add comment that different users might want different behavior so options

should be preferred.

[aeubanks]

thanks!

[mgorny]

This change has caused a test regression on 32-bit hosts (reproduced on ARM and x86):

FAIL: LLVM :: Transforms/MergeFunc/inline-asm.ll (14 of 62)
******************** TEST 'LLVM :: Transforms/MergeFunc/inline-asm.ll' FAILED ********************
Script:
--
: 'RUN: at line 1';   /home/mgorny/llvm-project/build/bin/opt -passes=mergefunc -S < /home/mgorny/llvm-project/llvm/test/Transforms/MergeFunc/inline-asm.ll | /home/mgorny/llvm-project/build/bin/FileCheck /home/mgorny/llvm-project/llvm/test/Transforms/MergeFunc/inline-asm.ll
--
Exit Code: 1

Command Output (stderr):
--
/home/mgorny/llvm-project/llvm/test/Transforms/MergeFunc/inline-asm.ll:9:16: error: CHECK-LABEL: expected string not found in input
; CHECK-LABEL: @int_ptr_arg_same
               ^
<stdin>:35:26: note: scanning from here
define void @int_ptr_null() {
                         ^
<stdin>:36:19: note: possible intended match here
 tail call void @float_ptr_null()
                  ^

Input file: <stdin>
Check file: /home/mgorny/llvm-project/llvm/test/Transforms/MergeFunc/inline-asm.ll

-dump-input=help explains the following input dump.

Input was:
<<<<<<
           .
           .
           .
          30: define void @int_ptr_arg_same(ptr %0) { 
          31:  tail call void @float_ptr_arg_same(ptr %0) 
          32:  ret void 
          33: } 
          34:  
          35: define void @int_ptr_null() { 
label:9'0                              X~~~~ error: no match found
          36:  tail call void @float_ptr_null() 
label:9'0     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
label:9'1                       ?                possible intended match
          37:  ret void 
label:9'0     ~~~~~~~~~~
          38: } 
label:9'0     ~~
>>>>>>

--

FWICS the functions are now output in different order depending on the arch.

[aidengrossman]

Thanks for bringing this to my attention! Not sure how I completely missed the buildbot notifications. I've reverted for now so that I can work on a fix out-of-trunk and will resubmit once I have this fixed (and after more thorough testing).

[aidengrossman]

It looks like hash_code stores everything as size_t which causes the difference between the 32 bit and 64 bit platforms. The functions end up in different places as MergeFunctions ends up ordering them by hash. I've switched the hashing a little bit (mainly using uint64_t and switching to hash_16_bytes from hash_combine to get rid of the size_t) so that things are consistent across platforms. I've also updated the magic constant as the function header to prevent any unnecessary churn in the test diffs and I've verified that behavior is consistent between 64 and 32 bit builds now.

Relanded in 64da0be1fc06ee2199bd27c980736986e0eccd9d.

[mgorny]

Thank you. I'm going to try again later today.

[mgorny]

I've just confirmed that the tests pass on 32-bit and 64-bit x86 now. Thanks, again!

llvm/include/llvm/IR/StructuralHash.h

 
 #include <cstdint>
 
 namespace llvm {
 
 class Function;
 class Module;
 
-uint64_t StructuralHash(const Function &F);
-uint64_t StructuralHash(const Module &M);
+using IRHash = uint64_t;
+
+IRHash StructuralHash(const Function &F);
+IRHash StructuralHash(const Module &M);
 
 } // end namespace llvm
 
 #endif

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

 public:
   FunctionComparator(const Function *F1, const Function *F2,
                      GlobalNumberState* GN)
       : FnL(F1), FnR(F2), GlobalNumbers(GN) {}
 
   /// Test whether the two functions have equivalent behaviour.
   int compare();
 
-  /// Hash a function. Equivalent functions will have the same hash, and unequal
-  /// functions will have different hashes with high probability.
-  using FunctionHash = uint64_t;
-  static FunctionHash functionHash(Function &);
-
 protected:
   /// Start the comparison.
   void beginCompare() {
     sn_mapL.clear();
     sn_mapR.clear();
   }
 
   /// Compares the signature and other general attributes of the two functions.

llvm/lib/IR/StructuralHash.cpp

 class StructuralHashImpl {
   hash_code Hash;
 
   template <typename T> void hash(const T &V) { Hash = hash_combine(Hash, V); }
 
 public:
   StructuralHashImpl() : Hash(4) {}
 
+  // A function hash is calculated by considering only the number of arguments
+  // and whether a function is varargs, the order of basic blocks (given by the
+  // successors of each basic block in depth first order), and the order of
+  // opcodes of each instruction within each of these basic blocks. This mirrors
+  // the strategy FunctionComparator::compare() uses to compare functions by
+  // walking the BBs in depth first order and comparing each instruction in
+  // sequence. Because this hash currently does not look at the operands, it is
+  // insensitive to things such as the target of calls and the constants used in
+  // the function, which makes it useful when possibly merging functions which
+  // are the same modulo constants and call targets.
+  //
+  // Note that different users of StructuralHash will want different behavior
+  // out of it (i.e., MergeFunctions will want something different from PM
+  // expensive checks for pass modification status). When modifying this
+  // function, most changes should be gated behind an option and enabled
+  // selectively.
   void update(const Function &F) {
     // Declarations don't affect analyses.
     if (F.isDeclaration())
       return;
 
-    hash(12345); // Function header
+    hash(0x6acaa36bef8325c5ULL); // Function header
 
     hash(F.isVarArg());
     hash(F.arg_size());
 
     SmallVector<const BasicBlock *, 8> BBs;
     SmallPtrSet<const BasicBlock *, 16> VisitedBBs;
 
+    // Walk the blocks in the same order as
+    // FunctionComparator::cmpBasicBlocks(), 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();
-      hash(45798); // Block header
+
+      // 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
+      hash(45798);
       for (auto &Inst : *BB)
         hash(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));
for (const Function &F : M)
       update(F);
   }
 
   uint64_t getHash() const { return Hash; }
 };
 
 } // namespace
 
-uint64_t llvm::StructuralHash(const Function &F) {
+IRHash llvm::StructuralHash(const Function &F) {
   StructuralHashImpl H;
   H.update(F);
   return H.getHash();
 }
 
-uint64_t llvm::StructuralHash(const Module &M) {
+IRHash llvm::StructuralHash(const Module &M) {
   StructuralHashImpl H;
   H.update(M);
   return H.getHash();
 }

llvm/lib/Transforms/IPO/MergeFunctions.cpp

 #include "llvm/IR/Function.h"
 #include "llvm/IR/GlobalValue.h"
 #include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/InstrTypes.h"
 #include "llvm/IR/Instruction.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/Module.h"
+#include "llvm/IR/StructuralHash.h"
 #include "llvm/IR/Type.h"
 #include "llvm/IR/Use.h"
 #include "llvm/IR/User.h"
 #include "llvm/IR/Value.h"
 #include "llvm/IR/ValueHandle.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
static cl::opt<bool>
     MergeFunctionsAliases("mergefunc-use-aliases", cl::Hidden,
                           cl::init(false),
                           cl::desc("Allow mergefunc to create aliases"));
 
 namespace {
 
 class FunctionNode {
   mutable AssertingVH<Function> F;
-  FunctionComparator::FunctionHash Hash;
+  IRHash Hash;
 
 public:
   // Note the hash is recalculated potentially multiple times, but it is cheap.
-  FunctionNode(Function *F)
-    : F(F), Hash(FunctionComparator::functionHash(*F))  {}
+  FunctionNode(Function *F) : F(F), Hash(StructuralHash(*F)) {}
 
   Function *getFunc() const { return F; }
-  FunctionComparator::FunctionHash getHash() const { return Hash; }
+  IRHash getHash() const { return Hash; }
 
   /// Replace the reference to the function F by the function G, assuming their
   /// implementations are equal.
   void replaceBy(Function *G) const {
     F = G;
   }
 };
 
bool MergeFunctions::runOnModule(Module &M) {
 
   SmallVector<GlobalValue *, 4> UsedV;
   collectUsedGlobalVariables(M, UsedV, /*CompilerUsed=*/false);
   collectUsedGlobalVariables(M, UsedV, /*CompilerUsed=*/true);
   Used.insert(UsedV.begin(), UsedV.end());
 
   // All functions in the module, ordered by hash. Functions with a unique
   // hash value are easily eliminated.
-  std::vector<std::pair<FunctionComparator::FunctionHash, Function *>>
-    HashedFuncs;
+  std::vector<std::pair<IRHash, Function *>> HashedFuncs;
   for (Function &Func : M) {
     if (isEligibleForMerging(Func)) {
-      HashedFuncs.push_back({FunctionComparator::functionHash(Func), &Func});
+      HashedFuncs.push_back({StructuralHash(Func), &Func});
     }
   }
 
   llvm::stable_sort(HashedFuncs, less_first());
 
   auto S = HashedFuncs.begin();
   for (auto I = HashedFuncs.begin(), IE = HashedFuncs.end(); I != IE; ++I) {
     // If the hash value matches the previous value or the next one, we must

llvm/lib/Transforms/Utils/FunctionComparator.cpp

for (unsigned i = 0, e = TermL->getNumSuccessors(); i != e; ++i) {
         continue;
 
       FnLBBs.push_back(TermL->getSuccessor(i));
       FnRBBs.push_back(TermR->getSuccessor(i));
     }
   }
   return 0;
 }
-
-namespace {
-
-// Accumulate the hash of a sequence of 64-bit integers. This is similar to a
-// hash of a sequence of 64bit ints, but the entire input does not need to be
-// available at once. This interface is necessary for functionHash because it
-// needs to accumulate the hash as the structure of the function is traversed
-// without saving these values to an intermediate buffer. This form of hashing
-// is not often needed, as usually the object to hash is just read from a
-// buffer.
-class HashAccumulator64 {
-  uint64_t Hash;
-
-public:
-  // Initialize to random constant, so the state isn't zero.
-  HashAccumulator64() { Hash = 0x6acaa36bef8325c5ULL; }
-
-  void add(uint64_t V) { Hash = hashing::detail::hash_16_bytes(Hash, V); }
-
-  // No finishing is required, because the entire hash value is used.
-  uint64_t getHash() { return Hash; }
-};
-
-} // end anonymous namespace
-
-// A function hash is calculated by considering only the number of arguments and
-// whether a function is varargs, the order of basic blocks (given by the
-// successors of each basic block in depth first order), and the order of
-// opcodes of each instruction within each of these basic blocks. This mirrors
-// the strategy compare() uses to compare functions by walking the BBs in depth
-// first order and comparing each instruction in sequence. Because this hash
-// does not look at the operands, it is insensitive to things such as the
-// target of calls and the constants used in the function, which makes it useful
-// when possibly merging functions which are the same modulo constants and call
-// targets.
-FunctionComparator::FunctionHash FunctionComparator::functionHash(Function &F) {
-  HashAccumulator64 H;
-  H.add(F.isVarArg());
-  H.add(F.arg_size());
-
-  SmallVector<const BasicBlock *, 8> BBs;
-  SmallPtrSet<const BasicBlock *, 16> VisitedBBs;
-
-  // Walk the blocks in the same order as FunctionComparator::cmpBasicBlocks(),
-  // 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 (const auto &Inst : *BB) {
-      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();
-}