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

@ 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