Accelerate MergeFunctions with hashing

[• jrkoenig]

Summary

This patch makes the Merge Functions pass faster by calculating and comparing
a hash value which captures the essential structure of a function before
performing a full function comparison.

The hash is calculated by hashing the function signature, then walking the basic
blocks of the function in the same order as the main comparison function. The
opcode of each instruction is hashed in sequence, which means that different
functions according to the existing total order cannot have the same hash, as
the comparison requires the opcodes of the two functions to be the same order.

The hash function is a static member of the FunctionComparator class because it
is tightly coupled to the exact comparison function used. For example, functions
which are equivalent modulo a single variant callsite might be merged by a more
aggressive MergeFunctions, and the hash function would need to be insensitive to
these differences in order to exploit this.

The hashing function uses a utility class which accumulates the values into an
internal state using a standard bit-mixing function. Note that this is a different interface
than a regular hashing routine, because the values to be hashed are scattered
amongst the properties of a llvm::Function, not linear in memory. This scheme is
fast because only one word of state needs to be kept, and the mixing function is
a few instructions.

The main runOnModule function first computes the hash of each function, and only
further processes functions which do not have a unique function hash. The hash
is also used to order the sorted function set. If the hashes differ, their
values are used to order the functions, otherwise the full comparison is done.

Both of these are helpful in speeding up MergeFunctions. Together they result in
speedups of 9% for mysqld (a mostly C application with little redundancy), 46%
for libxul in Firefox, and 117% for Chromium. (These are all LTO builds.) In all
three cases, the new speed of MergeFunctions is about half that of the module
verifier, making it relatively inexpensive even for large LTO builds with
hundreds of thousands of functions. The same functions are merged, so this
change is free performance.

[jfb]

• "mysql" typo in the description.
• Speedup numbers are hard to understand. What's a 117% speedup?

lib/Transforms/IPO/MergeFunctions.cpp

34

s/comparision/comparison/

141

Here and else, terminate sentences with periods.

443

s/comparision/comparison/

1116

Can you just use F.args() instead?

1302

Make uint64_t a typedef from the HashAccumulator above, and use it here. This will prevent the types from diverging.

[• jrkoenig]

Mysqld is the name of the server binary, as opposed to the client library or
CLI binary. Timings of just the MergeFunctions pass (average of 4 runs):

Binary	Before	After	Speedup
Mysqld	0.212s	0.193s	9%
Chromium	11.5s	5.31s	117%
libxul.so (Firefox)	10.4s	7.11s	46%

117% speedup is a little over 2x faster.

[• jrkoenig]

Fix typos, makes typedef for hash value, and fixes issue with signature hashing

Fixes several typos in comments, as pointed out by jfb.

Makes a new typedef in FunctionComparator, FunctionHash because the hash type is part of the comparator interface. The HashAccumulator (now HashAccumulator64) class is moved near the FunctionComparator::functionHash function because it is an implementation detail.

The types of function arguments are no longer considered in the hashing, because they did not contribute any discriminating power to the hash, and the previous implementation was inconsistent with cmpTypes (which may cause rare missed merges).

[• jrkoenig]

Actually use the typedef in client code.

[jfb]

Overall this looks good.

lib/Transforms/IPO/MergeFunctions.cpp

1114

Can you explain how the hash function is tied to the comparison function (things that the comparison function doesn't about must not be hashed). This will be important to document when merging similar (but not quite the same) functions.

Also explain why this is a special-purpose hash function for merge funcs, and isn't generally useful for ADT/Hashing.h or std::hash.

[dschuff]

just a couple of nits

lib/Transforms/IPO/MergeFunctions.cpp

1119

use ULL suffix here too?

1151

The style of this file seems to be "auto &Inst"

1304–1305

Might as well make this a range-for as long as you're touching every line around it.

1306

Style of this file is "Function *F"

1314

space between for and (
also, could just be a range-for

1317

space between if ((

[• jrkoenig]

Fix style issues, change hash and test, add comments

Minor style issues are fixed.

The hash is changed to using an existing LLVM function to do the mixing.
This causes a test to fail because the functions are emitted in the
opposite order than before. (This is an issue with the test being flakey,
not the determinism of the compiler, because the order is stable for each
choice of hash function.)

Adds a comment explaining the relation between the hash and the comparison.

[• jrkoenig]

Updated style issues, etc.

lib/Transforms/IPO/MergeFunctions.cpp

1326

This can't be a range for because the next and previous values are needed.

[jfb]

Can you update the patch description, since it's now not quite correct (e.g. farmhash).

In D11923#223233, @jrkoenig wrote:

The hash is changed to using an existing LLVM function to do the mixing.
This causes a test to fail because the functions are emitted in the
opposite order than before. (This is an issue with the test being flakey,
not the determinism of the compiler, because the order is stable for each
choice of hash function.)

Can you expand on this? Which test fails, and how? Can you fix it?

[• jrkoenig]

@jfb The failing test is Transforms/MergeFunc/call-and-invoke-with-ranges.ll. I have included a fix in this patch. This quick fix is to just swap the functions so the CHECK-LABEL directives pick up on the right definitions. The compile is still correct, the test is just not robust enough to see this.

[jfb]

lgtm, leaving open for others to comment.

test/Transforms/MergeFunc/call-and-invoke-with-ranges.ll

79 ↗

(On Diff #31991)

How sensitive is mergefunc to slight changes causing reordering of functions?

It might be something worth tackling later.

[• jrkoenig]

Any other comments?

[jfb]

llvm/trunk/lib/Transforms/IPO/MergeFunctions.cpp

1319 ↗

(On Diff #32208)

(for posterity) @chapuni fixed this line in r245168 to be a stable sort and ignore the pair's Function*.

[chapuni]

llvm/trunk/lib/Transforms/IPO/MergeFunctions.cpp

1311 ↗

(On Diff #32208)

IMO, sorting hashes might be overkill here.

Assumptions;

1. Most of each hash entry might have single Function. In practical code, I assume that hundreds of functions wouldn't collide.
2. For merging, order among hashes wouldn't be matter. Each hash could be considered as individual domain.

I suggest like

DenseMap<FunctionHash,SmallVector<Function*,1>> HashedFuncs;

[• jrkoenig]

llvm/trunk/lib/Transforms/IPO/MergeFunctions.cpp

1311 ↗

(On Diff #32208)

1. Most entries are single functions, yes, but the design of the hash still makes huge groups. For example, all functions of the form define f(...) { ret CONSTANT; } are in the same bucket, and there are thousands of them!
2. The order in the function tree set is by hash, then full comparison, so the functions have to be sorted anyway. The sorting is a negligible part of the runtime.

I'm working on more extensive reworking of MergeFunctions which should split the functions into domains by hash, as you suggested. This patch was designed to be a small, self-contained start.

lib/Transforms/IPO/MergeFunctions.cpp

 //
 // Comparison iterates through each instruction in each basic block.
 // Functions are kept on binary tree. For each new function F we perform
 // lookup in binary tree.
 // In practice it works the following way:
 // -- We define Function* container class with custom "operator<" (FunctionPtr).
 // -- "FunctionPtr" instances are stored in std::set collection, so every
 //    std::set::insert operation will give you result in log(N) time.
-//
+// 
+// As an optimization, a hash of the function structure is calculated first, and
+// two functions are only compared if they have the same hash. This hash is
+// cheap to compute, and has the property that if function F == G according to
+// the comparision function, then hash(F) == hash(G). This consistency property
+// is critical to ensuring all possible merging opportunities are exploited.
+// Collisions in the hash affect the speed of the pass but not the correctness
+// or determinism of the resulting transformation.
+//
 // When a match is found the functions are folded. If both functions are
 // overridable, we move the functionality into a new internal function and
 // leave two overridable thunks to it.
 //
 //===----------------------------------------------------------------------===//
 //
 // Future work:
 //
static cl::opt<unsigned> NumFunctionsForSanityCheck(
     "mergefunc-sanity",
     cl::desc("How many functions in module could be used for "
              "MergeFunctions pass sanity check. "
              "'0' disables this check. Works only with '-debug' key."),
     cl::init(0), cl::Hidden);
 
 namespace {
 
+// Accumulate the hash of a sequence of 64-bit integers. This is similar to a
+// hash function but the entire input does not need to be available at once.
+class HashAccumulator {
+    uint64_t Hash;
+  public:
+    // Initialize to random constant, so the state isn't zero.
+    HashAccumulator() { Hash = 0x6acaa36bef8325c5; }
+    void add(uint64_t v) {
+       // MurmurHash like hashing function, with two rounds of mixing
+       // One round is insufficient to avoid collisions
+       const uint64_t Mul = 0x9ddfea08eb382d69ULL;
+       Hash ^= v;
+       Hash *= Mul;
+       Hash ^= (Hash >> 47);
+       Hash *= Mul;
+       Hash ^= (Hash >> 44);
+    }
+    // No finishing is required, because the entire hash value is used
+    uint64_t getHash() { return Hash; }
+};
+
 /// FunctionComparator - Compares two functions to determine whether or not
 /// they will generate machine code with the same behaviour. DataLayout is
 /// used if available. The comparator always fails conservatively (erring on the
 /// side of claiming that two functions are different).
 class FunctionComparator {
 public:
   FunctionComparator(const Function *F1, const Function *F2)
       : FnL(F1), FnR(F2) {}
 
   /// 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.
+  static uint64_t functionHash(Function&);
 
 private:
   /// Test whether two basic blocks have equivalent behaviour.
   int compare(const BasicBlock *BBL, const BasicBlock *BBR);
 
   /// Constants comparison.
   /// Its analog to lexicographical comparison between hypothetical numbers
   /// of next format:
private:
   /// 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.
   DenseMap<const Value*, int> sn_mapL, sn_mapR;
 };
 
 class FunctionNode {
   mutable AssertingVH<Function> F;
+  uint64_t Hash;
 
 public:
-  FunctionNode(Function *F) : F(F) {}
+  // Note the hash is recalculated potentially multiple times, but it is cheap.
+  FunctionNode(Function *F) : F(F), Hash(FunctionComparator::functionHash(*F)){}
   Function *getFunc() const { return F; }
 
   /// Replace the reference to the function F by the function G, assuming their
   /// implementations are equal.
   void replaceBy(Function *G) const {
     assert(!(*this < FunctionNode(G)) && !(FunctionNode(G) < *this) &&
            "The two functions must be equal");
 
     F = G;
   }
 
   void release() { F = 0; }
   bool operator<(const FunctionNode &RHS) const {
+    // Order first by hashes, then full function comparision
+    if (Hash != RHS.Hash)
+      return Hash < RHS.Hash;
     return (FunctionComparator(F, RHS.getFunc()).compare()) == -1;
   }
 };
 }
 
 int FunctionComparator::cmpNumbers(uint64_t L, uint64_t R) const {
   if (L < R) return -1;
   if (L > R) return 1;
for (unsigned i = 0, e = TermL->getNumSuccessors(); i != e; ++i) {
 
       FnLBBs.push_back(TermL->getSuccessor(i));
       FnRBBs.push_back(TermR->getSuccessor(i));
     }
   }
   return 0;
 }
 
+uint64_t FunctionComparator::functionHash(Function& F) {
+  HashAccumulator H;
+  H.add(F.isVarArg() ? 5433 : 82654);
+  for(auto I = F.arg_begin(), IE = F.arg_end(); I != IE; ++I) {
+    H.add(I->getType()->getTypeID());
+  }
+  
+  SmallVector<const BasicBlock *, 8> BBs;
+  SmallSet<const BasicBlock *, 16> VisitedBBs;
+
+  // Walk the blocks in the same order as FunctionComparator::compare(),
+  // 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) {
+      H.add(Inst.getOpcode());
+    }
+    const TerminatorInst *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();
+}
+
+
 namespace {
 
 /// MergeFunctions finds functions which will generate identical machine code,
 /// by considering all pointer types to be equivalent. Once identified,
 /// MergeFunctions will fold them by replacing a call to one to a call to a
 /// bitcast of the other.
 ///
 class MergeFunctions : public ModulePass {
 public:
   static char ID;
   MergeFunctions()
     : ModulePass(ID), HasGlobalAliases(false) {
     initializeMergeFunctionsPass(*PassRegistry::getPassRegistry());
   }
if (const unsigned Max = NumFunctionsForSanityCheck) {
     return Valid;
   }
   return true;
 }
 
 bool MergeFunctions::runOnModule(Module &M) {
   bool Changed = false;
 
+  // All functions in the module, ordered by hash. Functions with a unique
+  // hash value are easily eliminated.
+  std::vector<std::pair<uint64_t, Function*>> HashedFuncs;
+  
   for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) {
-    if (!I->isDeclaration() && !I->hasAvailableExternallyLinkage())
-      Deferred.push_back(WeakVH(I));
+    if (!I->isDeclaration() && !I->hasAvailableExternallyLinkage()) {
+      Function* F = cast<Function>(I);
+      HashedFuncs.push_back({FunctionComparator::functionHash(*F), F});
+    }
+  }
+
+  std::sort(HashedFuncs.begin(), HashedFuncs.end());
+  
+  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
+    // consider merging it. Otherwise it is dropped and never considered again.
+    if((I != S && std::prev(I)->first == I->first) ||
+       (std::next(I) != IE && std::next(I)->first == I->first)) {
+      Deferred.push_back(WeakVH(I->second));
+    }
   }
   
   do {
     std::vector<WeakVH> Worklist;
     Deferred.swap(Worklist);
 
     DEBUG(doSanityCheck(Worklist));
 
     DEBUG(dbgs() << "size of module: " << M.size() << '\n');
     DEBUG(dbgs() << "size of worklist: " << Worklist.size() << '\n');
 
     // Insert only strong functions and merge them. Strong function merging
     // always deletes one of them.
     for (std::vector<WeakVH>::iterator I = Worklist.begin(),