Also Common Subexpression Elimination. A frequently-used technique in compilers. Where a subexpression appears more than once in an expression (or in a wider range, if the compiler is smart enough), and can be proven to have the same value on each evaluation, the value of the subexpression can be calculated only once, and reused.
Example:
max = (((a-b) >> 31) & b) + (a-b);
The 'a-b' term appears twice, so naively compiles to:
sub t1, a, b
shr t1, t1, #31
and t1, t1, b
add t1, t1, b
sub t1, t1, a
But by using CSE on the expression, we can rewrite the code as
register int t2 = (a-b);
max = (t2>>31) & b + t2;
which, similarly naively, compiles to
sub t2, a, b
shr t1, t1, #31
and t1, t1, b
add t1, t1, t2
Code and execution time saving is proportional to the complexity
of the subexpression and the number of times it appears, minus one;
in the above case, a single instruction.
In general, CSE decreases code size but increases register pressure.
If many simple expressions are reused only once, it's often quicker to
calculate the expression each use rather than save and restore the
registers.
|
