Real Time Systems Design And Analysis

Chapter 7.6.18 - Combination Effects

7.6.18   Combination Effects

Although many of the optimization techniques discussed can be automated, most
compilers only perform one optimization pass, overlooking opportunities that are
not revealed until after at least one pass. Hence, hand optimization can provide
additional execution time savings. To see the effects of multiple-pass optimization,
consider the following example. The C code fragment:

for (j=1;i<=3;j++)
{
    a[j]=0;
    a[j]=a[j]+2*x
};

for (k=1;k<=3;k++)
  b[k]=b[k]+a[k]+2*k*k;


is improved by loop jamming, loop invariant removal, and removal of extraneous
code (in this case the initialization of a[j]). The resultant code is:

t=2*x;
for (j=1;j<=3;j++)
{
    a[j]=t;
    b[j]=b[j]+a[j]+2*j*j;
};


Next, loop unrolling yields:

t=2*x;
a[1]=t ;
b[1]=b[1]+a[1]+2*1*1;
a[2]=t ;
b[2]=b[2]+a[2]+2*2*2;
a[3]=t ;
b[3]=b[3]+a[3]+2*3*3;


Finally, after constant folding, the improved code is

t=2*x;
a[1]=t;
b[1]=b[1]+a[1]+2;
a[2]=t;
b[2]=b[2]+a[2]+8;
a[3]=t;


The original code involved nine additions and nine multiplications, numerous
data movement instructions, and loop overheads. The improved code requires
only six additions, 1 multiplication, less data movement, and no loop overhead.
It is very unlikely that any compiler would have been able to make such an
optimization.

UNLIMITED FREE
ACCESS
TO THE WORLD'S BEST IDEAS

SUBMIT
Already a GlobalSpec user? Log in.

This is embarrasing...

An error occurred while processing the form. Please try again in a few minutes.

Customize Your GlobalSpec Experience

Category: PCMCIA Memory Cards
Finish!
Privacy Policy

This is embarrasing...

An error occurred while processing the form. Please try again in a few minutes.