Compiler Design Test 5

Concept:

Peephole optimization is a technique for locally improving the target code which is done by examining a sliding window of target instructions and replacing the instruction sequences within the peephole by shorter or faster sequences wherever possible.

Explanation:

The code in the peephole need not be contiguous although some implementations do require this. Some characteristics of peephole optimization are:

• Redundant instruction elimination
• Elimination of unreachable code
• Reduction in strength
• Algebraic simplifications
• Use of machine idioms

Loop unrolling can be applied to reduce number of iterations.
int i = 0;
while( i < 1000)
{
            printf(“%d”, i);
            i++;
            printf(“%d”, i);
            i++;
}

Comparison is decreased by half due to loop unrolling in the above code.

In live variable analysis, we wish to know for variable x and point p whether the value of x at p could be used along some path in the flow graph starting at p. If so, x is live at point p otherwise x is dead at p.

Some points regarding live variable analysis are:

• Live variable information is used for register allocation for basic blocks.
• After a value is computed in a register and presumably used within a block, it is not necessary to store that value if it is dead at the end of the block.
• If all registers are full and we need another register, we should favor using a register with a dead value since that value does not have to be stored.

Given code in question contains loop invariant computation

Optimized code:

int FUN() {

int i, j, x, y, m, n;
n=20;
for (i = 1; i < n; i = i+2)
{
for (j = 0; j < n; j++)
{ 
x += j<<2;
y += j<<2;        // this further can reduce
}
x += i*n*5;
y += n*7;
}
return x+y
}

Explanation:

In the above code, strength reduction and common sub-expression elimination technique has been used. Therefore option 1, 3 and 4 are correct

The correct answer is option 2 i.e. Both S1 and S2.

Register allocation is the process of deciding which IR values to keep in registers. Graph coloring is an effective technique for doing register allocation in compilers.

Register assignment is the process of deciding which register should hold a given IR value.  

It consists of statements which can be moved outside the body of a loop without affecting the semantics of the program.

Loops are very important place for optimizations. Code motion is a loop optimization technique which reduces the amount of code in a loop. This transformation takes an expression that yields the same result independent of the number of times a loop is executed and evaluates the expression before the loop.

Example:

While (I < = limit - 2)

After code motion, it can be written as:

Temp = limit – 2

while(I < = temp)

Now computation of limit – 2 is performed only once before entering the loop.

Concept:

Common subexpression evaluation is a compiler optimization technique that finds the common subexpressions or identical expressions and try to replace them with a single expression holding the computed value.

Explanation:

Given code is :

t6 =  4 * i

x = a[t6]

t7 = 4 * i

t8 = 4 * j

t9 = a[t8]

a[t7] = t9

t10 = 4 * j

a[t10] = x

go to L

Here, there are two calculations that are repeated in nature such as 4 * i and 4 *j. As, none of these calculations were requested explicitly by the programmer. So, try to replace them with a single expression which does not change the result. So, after eliminating common subexpression result will be :

t6 = 4* i

x = a[t6]

t8 = 4 *j

t9 = a[t8]

a[t6] = t9

a[t8] = x

goto L