Accelerate MergeFunctions with hashing

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.

Author: jrkoenig

Reviewers: nlewycky, dschuff, jfb

Subscribers: llvm-commits, aemerson

Differential revision: http://reviews.llvm.org/D11923