Page MenuHomePhabricator

Reassociate in favor of grouping previously paired operands

Authored by jingyue on Jun 8 2015, 4:03 PM.



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;
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;
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
RewriteExprTree later.

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.

Diff Detail

Event Timeline

wengxt updated this revision to Diff 27345.Jun 8 2015, 4:03 PM
wengxt retitled this revision from to Reassociate in favor of grouping previously paired operands.
wengxt updated this object.
wengxt edited the test plan for this revision. (Show Details)
wengxt added a subscriber: Unknown Object (MLST).
dberlin edited edge metadata.Jun 8 2015, 4:05 PM

For reference, can you explain the difference between this and the
last patch I posted that does the same thing?

wengxt added a comment.Jun 8 2015, 4:23 PM

Related discussion and original patch on llvmdev.

There are some differences between the original patch and this version:

  1. Because OptimizeExpression has some assumptions about the order of linearized ops, in this version the order of operands is adjusted after calling function OptimizeExpression.
  2. Because RewriteExprTree can only pair the last two operands in Ops, in this patch the order of operands is not adjusted by rank but by simply moving one pair of operands to the end of Ops.
  3. Paired operands are indexed with their corresponding Opcode and Instruction. So (add a, b) will not make a, b together in a multiplication expression.
  4. The pair will be discarded correctly in following case:
  5. The corresponding instruction of the pair is removed.
  6. The corresponding instruction of the pair is being linearized
  7. Last pairing map is cleared after processing every basic block.
wengxt updated this revision to Diff 27419.Jun 9 2015, 5:15 PM
wengxt edited edge metadata.

Updated based on Daniel's comment.

This patch shift the rank range by (1 << 16) to have some reserved
space for pairing operands. Ranks are now adjusted after function
OptimizeExpresssion and resort again.

jingyue commandeered this revision.Mar 15 2016, 10:31 AM
jingyue edited reviewers, added: wengxt; removed: jingyue.
jingyue abandoned this revision.Mar 15 2016, 10:53 AM

Pressed the wrong button. Meant to say "needs revision". Feel free to reclaim it.