Optimizing Global Value Numbering

Among the few optimizations in the Tachyon front-end, there is a pass that does Global Value Numbering (GVN). This optimization tries to identify and eliminate SSA instructions that are effectively computing the same value within a function. It does so by mapping instructions into a hash map based on what operation they compute and their operands. Each instruction is mapped to a number, and because SSA temporaries are immutable, the instructions that map to the same number are computing the same result (provided, of course, that the said instructions have no side-effects). It’s a little less trivial than it sounds, because a flow-based analysis then needs to be performed to establish which SSA temporaries must reach given locations in the Control-Flow Graph (CFG) in order to establish which instructions can be eliminated.

Unfortunately, quick profiling revealed that GVN was actually the slowest pass of the Tachyon front-end, using about 18% of the total compilation time, or slightly more than half the time taken by all front-end passes combined. This is obviously unacceptable, and probably made GVN the least useful pass in terms of cost-benefits. I had assumed that it was the flow analysis part of GVN that was slowest, but further profiling revealed that most of the execution time in this analysis was taken by the hash function used for value numbering. It turned out that the problem was fairly obvious. I was using the strings representations of SSA instructions to compute their hash values. This seemed like a good idea at the time because of the inherent simplicity.

To optimize GVN, I decided to change the hash function to use the numerical value of the first character of each instruction’s opcode, the SSA temporary numbers, and the value of integer constants in computing the hash function. String constants and other constants are not used in the hash function. This is not perfect, but it worked well to improve performance. The time taken by GVN went from 18% to about 8% of the total compilation time. Only 6 lines or code or so needed to be changed. This illustrates very well how very small pieces of code can make a big difference in the final performance of a system.