C Compilers and Code Optimization for DSPs - Signal Processing Systems - page 1018

a b c

/ ∗ Region 1 ∗ / / ∗ Region 1 ∗ / / ∗ New f u n c t i o n ∗ /

...
x=a+b;
y=c

...
f(&x,&y,&z ,
a,b,c,d);

void f(&x,&y,&z ,
a,b,c,d)
{ x=a+b;
y=c

− d;

z=x ∗ y;

...
...
/ ∗

...
...
/ ∗

− d;

z=x ∗ y;

Region 2 ∗ / Region 2 ∗ / }

r=n+m;
s=o −

f(&r,&s,&t ,
n,m,o,p); p;

t=r ∗ s;

... ...

Fig. 16 Example: procedural abstraction. ( a ) Original code. ( b ) Code after procedural abstraction.
( c ) Newly created function

instance and control transfer instructions (jumps or function calls) to this single
block of code. This optimization effectively “outlines” repeated fragments of code
and replaces the original, redundant occurrences with function calls (jumps) to
the newly created function (block). This code transformation is also known as
procedural abstraction if a single, new function is created, or cross-jumping or tail
merging if a region of code is replaced with a direct jump to a single instance of an
identical code block. An example of procedural abstraction is illustrated in Fig. 16 .
Coalescing of repeated instructions sequences, either through procedural ab-
straction or cross-jumping, involves a number steps. Initially, repeated instructions
sequences need to be identified using a suffix tree [ 16 ] from which a repeat
table is constructed. Repeated instruction sequences identified during these stages
might still contain unsafe operations that interfere with code size reducing code
transformations. These control hazards , e.g. jumps into or out of the code fragment,
must be avoided, for example, by splitting these repeats appropriately. Each of the
smaller fragments can then be dealt with separately. Once the compiler has identified
a set of repeats suitable for compaction it will determine if coalescing of repeated
instruction sequences is profitable and, if so, either apply the procedural abstraction
or cross-jumping transformation. The former requires that the block of code to be
“outlined” is single-entry, single-exit , i.e. all internal jumps must be within the body
of the region. For cross-jumping all of the control-flow successors must match for
each repeated region.
If repeated code patterns occur frequently and are large enough the overall
benefit from procedural abstraction or cross-jumping outweighs their code size and
performance overheads. On the other hand, for each code region replaced with a
function call there is a function call overhead resulting in additional instructions
possibly outweighing the benefit, especially for very short code fragments. Also,
the additional control flow instructions may introduce a significant performance
overhead when compared with the original straight-line code.