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.