Compiler Design (register allocation)

Question

In such questions, In which it is asked " minimum number of registers required for executing this three address code without spilling", can we apply code motion optimization or not?

As in a question of made easy test series :

T1 = a;

T2= b;

T3 =c;

T4 = d;

T5 = T1 + T2;

T6 = T3 + T5;

T7 = T6 +T4;

T8 = T7 + T3

T9 = T8 + T6

a = T9

When we use normal method without optimization, it will require 4 registers, as each temporaries will be assigned one register, as they are live at that point and none of these temporaries will share registers initially.

But if we'll apply code motion optimization, this can be done by 3 registers only. As

T1 = a;  { R1 = T1}

T2 = b;   { R2 = T2}

T5 = T1 + T2  { R1 = R1 + R2 }

T3 = c;  {R2 = T3}

T6 = T3 + T5; {R1 = R1 + R2}

T4 = d; {R3 = T4}

T7 = T6 + T4;  {R3 = R3 + R1}

T8 = T7 + T3; {R2 = R3+R2}

T9 = T8 + T6; {R1= R1+R2}

a = T9; {a = R1}

So,which one is correct, made easy one or second one applying code motion?

Can anybody please clarify this.

Comments

i think if in  question not mentioned about optimization  then we can not apply optimization okk

if we are making dag for this code then only  three regiter required but in question not mention any where optimization

---

In many answers i have seen they are applying code motion, and In some not applying. Getting so confused in this😅

Answer 1

Without spilling we will be needing minimum 4 registers.