This patch enhances Reassociate to group operands that are paired
previously. With this patch, Reassociate can expose in general more
opportunities for later redundancy elimination. For example,
foo(a + c); foo(a + (b + c));
t1 = a + c; foo(t); t2 = b + c; t3 = a + t2; foo(t3); // using 5 instructions
With this patch, since a, c are paired together in t1, later instruction
will try to pair a, c together so it can be optimized to
t1 = a + c; foo(t1); t2 = t1 + b; foo(t2); // using 4 instructions
We implement this idea leveraging a data structure called
LastOperandPairsMap that stores the most recently paired operands. It is
indexed by a Value and its corresponding Opcode in this pair.
For example, LastOperandPairsMap[x][op] = <y, I> means there is an instruction I
in form of (op x, y) or or (op y, x) in the current block.
Each time when function ReassocaiteExpression sorts the operands of an
expression, it searches the map for any pair of leaves that have been
reassociated recently, and moves such pair (if any) to the end of the
operand list so that they are guaranteed to be grouped together by function
Note that this optimization overlaps quite a bit with NaryReassociate.
However, since NaryReassociate requires ScalarEvolution and is a
iterative algorithm, NaryReassociate is much more expensive than the
algorithm introduced in this patch and thus cannot be run as pervasively
as Reassociate. This optimization allows Reassociate to cheaply handle
many cases NaryReassociate is designed for.