In my previous trace compiler I did Common Subexpression Elimination (CSE) by going over the tree in forward order and keeping a per-opcode history of all instruction that were seen before during iteration and thus could replace this (redundant) instruction. Thus, for each instruction all instructions with the same opcode have to be scanned. In our new trace tree compiler we use a hash table lookup based on value numbers instead. The hash table is cloned every time we hit a guard node to save the set of available expression to match against at that point. This saved set is than used when a secondary trace branch off that guard is analyzed.

As value numbers we use the sum of the value number of each operand plus the hash code of the class of the instruction (each instruction in the IR is a class in our compiler). The value number of constants is the value of the constant. For every instruction we don’t want to be subject to CSE, we use the object hash code as value number and thus it won’t match anything (except itself). We also added a commutative() method to each binary instruction that indicates whether the operand order is irrelevant. Since we use the sum of the operand value numbers the overall value number will always be identical, no matter whether the operation is commutative or not, but the subsequent equality test will fail if the ordering doesn’t match and the operation is not commutative.