THE FOLD / CO-OP / THE MERGE / THE COMMON SUBEXPRESSION
THE COMMON SUBEXPRESSION
it converts arithmetic into pressure on the register file
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
If the same expression appears twice and nothing it depends on has changed between them, the second one is a lookup. Finding them is easy; the condition attached to the sentence is the whole problem.
LIT verified live. 8 expressions containing 4 distinct ones. 4 evaluations are removed — 50.0%. Three expressions repeat: a+b three times, c*d twice, e-f twice. The removal is valid only where no assignment to a, b, c, d, e or f occurs between the occurrences.
LIT verified live. 8 expressions containing 4 distinct ones. 4 evaluations are removed — 50.0%. Three expressions repeat: a+b three times, c*d twice, e-f twice. The removal is valid only where no assignment to a, b, c, d, e or f occurs between the occurrences.
2 HOW IT WAS WEAVED · AI + HUMAN
Common-subexpression elimination is usually done on a value-numbered DAG, where identical subtrees become the same node by construction rather than by search.
AVAN (AI) is being explicit that the 50.0% is the upper bound. This counts syntactic repetition; it is what the pass could remove if nothing intervenes. Every intervening assignment takes one back, and in real code the availability analysis is where the pass spends its time — not in finding the duplicates.
AVAN (AI) is being explicit that the 50.0% is the upper bound. This counts syntactic repetition; it is what the pass could remove if nothing intervenes. Every intervening assignment takes one back, and in real code the availability analysis is where the pass spends its time — not in finding the duplicates.
3 ONE DIMENSION
Eight expressions, four distinct.
4 TWO DIMENSIONS · INTERACTIVE
Insert an assignment and watch a saving disappear.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the same thing said once.
AVAN’s addition (the inverse-companion): the forward reading is that eliminating a common subexpression saves an evaluation. The inverse is that it replaces a computation with a live value, and live values need registers. The saved multiply becomes a variable that must stay alive from the first use to the last, lengthening a live range and pushing the allocator toward a spill. Read backwards, this pass does not remove work — it converts arithmetic into pressure on the register file, and the trade is only a win while there are seats left.
LIT 8 expressions containing 4 distinct ones allow 4 evaluations to be removed - 50.0% - across three repeats, a+b three times and c*d and e-f twice each, and the removal is valid only where no assignment to a, b, c, d, e or f occurs between the occurrences
FIG Common-subexpression elimination is usually done on a value-numbered DAG, where identical subtrees become the same node by construction rather than by search. AVAN is explicit that the 50.0% is an upper bound: this counts syntactic repetition, which is what the pass could remove if nothing intervenes. Every intervening assignment takes one back, and in real code the availability analysis is where the pass spends its time.
FIG Common-subexpression elimination is usually done on a value-numbered DAG, where identical subtrees become the same node by construction rather than by search. AVAN is explicit that the 50.0% is an upper bound: this counts syntactic repetition, which is what the pass could remove if nothing intervenes. Every intervening assignment takes one back, and in real code the availability analysis is where the pass spends its time.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE MERGE · David Lee Wise (ROOT0), with AVAN