Given the following code snippet: a = p*3 + q*5; for(int i = 0; i < 198; ++i){…

Definition (CSE + LICM)

Common Subexpression Elimination (CSE):
It is a compiler optimization technique that identifies and eliminates repeated occurrences of the same expression by computing it once and reusing the result.

Loop Invariant Code Motion (LICM):
It moves computations outside the loop if their values do not change across iterations (loop-invariant expressions).

Identification of Optimizable Expressions

Given code:

a = p*3 + q*5;

for(int i = 0; i < 198; ++i){
    if((z+i)%2 == 0){
        b = p*3 + (z*i);
    } else {
        c = q*5 + c;
    }
}

Common Subexpressions:

• p * 3 (appears multiple times)

• q * 5 (appears multiple times)

Observation:

• 
  Both expressions do not depend on loop variable i
  
  Hence, they are loop-invariant and can be hoisted using LICM + CSE
  

Optimized Code

t1 = p * 3;     // hoisted (LICM + CSE)
t2 = q * 5;     // hoisted (LICM + CSE)

a = t1 + t2;

for(int i = 0; i < 198; ++i){
    if((z+i)%2 == 0){
        b = t1 + (z*i);
    } else {
        c = t2 + c;
    }
}

Multiplication Count (Step-by-Step)

Pre-loop Computation

Total (outside loop) = 2 multiplications

Inside Loop Computation

• Loop runs 198 times

• Condition: (z + i) % 2 == 0

Logical Reasoning:

• As i increments by 1 each time, (z+i) alternates between even and odd

• Therefore, condition is true exactly:

198 / 2 = 99 times

Total (inside loop) = 99 multiplications

Answer

Total number of multiplications after CSE = 101