Compiler Construction

Question

Consider the following code which computes the inner product of 2 vectors:

prod := 0;

i := 1;

repeat

{

prod := prod + a[i] * b[i]

i = i+1;

until i >20

}

Below is possible IR for this program :

1) prod := 0

2) i :=1

3) t1 :=4*i

4) t2 :=a[t1]

5) t3 :=4*i

6) t4 :=b[t3]

7) t5 :=t2*t4

8)t6 :=prod + t5

9) prod :- t6

10)t7 := i+1

11) i :=t7

12) if i<=20 goto (3)

13) ..

 

Create Basic Blocks and the control Flow Graph and also show any Optimizatioions.If you Find.

Comments

why it is t1 = 4*i ?

Answer 1

The original code is computes inner product of vectors i.e., a[1]*b[1] + a[2]*b[2] + ...... + a[20]*b[20]. So, it can be re-written as $\Rightarrow$

int prod = 0;
for(i=1;i<=20;i++) prod += a[i]*b[i];

Now, Intermediate representations can be in many ways, but if the IR given in question is considered, then we Find Basic Blocks and CFG by finding leaders first.

• First statement is a leader.
• Target of goto is a leader
• Statement that immediatedly follows goto is a leader.

And a Basic block starts from one leader and continues till starting of next leader without including that leader. So, statement $1,3$ and $13$ are leaders here.

And Basic blocks are $(1-2)$, $(3-12)$ and  $13$ onwards till program exits. Flow graph looks like $\Rightarrow$

And Cycle in program detects the presence of a loop. Further optimization like Loop Unrolling can be done here.

Comments

respected sir I have problem in optimization part only, rest i have already done :(

please tell how to remove the loop :( please

---

Removing loop is not a good approach. But It can be done like :

$t_1 = a[1]$
$t_2 = b[1]$
$t_3 = t_1*t_2$
Doing this for $20$ times and then adding them, but it requires lot of registers. Thus using loop is much better. Because Loop doesn't create any problem.
 

Loop Unrolling means decreasing the number of times condition is checked.

int prod = 0;
for(i=1;i<=20;i++) { // condition is checked less number of times
prod += a[i]*b[i];
i++;
prod += a[i]*b[i];
}

---

i should be less than or equal to ten now ??.

int prod = 0;
for(i=1;i<=20;i++) { // condition is checked less number of times
prod += a[i]*b[i];
i++;
prod += a[i]*b[i];
}

over here look in for loop

condition should be as:

for (i=1;i<=10;i++)

???

---

No, loop checking will be for $i = 1$, $i = 3$ and $i = 5$ and so on. (i.e., $10$ times)

---

here multiplication is a length operation so wont it be removed??

---

Didn't get your question.

---

i mean in this no loop unrolling will bedone and also neither multiplication sign will not be replaced with plus sign,
because according to optimization technique whener you see multiplication sign replace it with plus
bu tthen you are saying it will occupy a lot of registers.

---

In the above Code, Optimisation is not required. But if you want to do it only Loop Unrolling can be done(no other machine independent optimisation)

And Iam hearing for the first time that whenever you see multiplication sign replace it with plus.

---

@Joshi Multiplication by 0 can be replaced by 0, by 1 can be ignored, by powers of 2 can be replaced by left shift etc. But these are all specific to the operand values.

And loop unrolling has another advantage that it avoids the "conditional" branch which affects pipeline in a bad way.

---

Yes sir. statements like : $x = x + 0$ and $x = x*1$ can also be ignored. and please explain loop unrolling has another advantage that it avoids the "conditional" branch which affects pipeline in a bad way little more.

---

@ arjun sir yes sir you are right .

now please tell how to do the optimizations in this code i mean please rewrite and tell what will be code after optimization

---

@mcjoshi Say a loop is iterating for only 4 times. By keeping the loop, during execution time, CPU encounters 5 conditional jump instructions - and as we know in pipeline this can be bad due to unavoidable stall. Only way to get around is branch prediction - if its there then not a big deal. Otherwise by unrolling the loop 4 times, we remove the "conditional branch", (actually we resolve the condition at compile time and not runtime). But this causes an increase in code size- potential issue for instruction cache. So, loop unrolling by increasing code size is only done in "O3" optimization level or when we explicitly tell the compiler to do so.

@Lav Sorry, not possible now.

---

Thanks Arjun Sir