Skip to content
GATEiit

GATE CSE 2021 Set 2 Q40: Additions and dereferences after common subexpression elimination

Question

Consider the following ANSI C code segment:

z = x + 3 + y->f1 + y->f2;
for (i = 0; i < 200; i = i + 2){
  if (z > i) {
    p = p + x + 3;
    q = q + y->f1;
  } else {
    p = p + y->f2;
    q = q + x + 3;
  }
}

Assume that the variable y points to a struct (allocated on the heap) containing two fields f1 and f2, and the local variables x, y, z, p, q, and i are allotted registers. Common sub-expression elimination (CSE) optimization is applied on the code. The number of addition and dereference operations (of the form y->f1 or y->f2) in the optimized code, respectively, are:

Try it: multiple choice: exactly one correct option

Select one option
Wrong answer costs 2/3 mark in GATE.
Show answer and explanation

Answer: D (official GATE 2021 final answer key)

Concept used: CSE computes x + 3, y->f1 and y->f2 once before the loop and reuses them; count the operations actually executed.

First step: Before the loop: t=x+3t = x+3, a=a = y->f1, b=b = y->f2, z=t+a+bz = t + a + b (3 additions, 2 dereferences); then each of the 100 iterations does i+2i + 2 and two more additions.

Full step-by-step solution

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

WhatsAppDownload image

Source: official GATE 2021 Set 2 CS question paper and final answer key, organised by IIT Bombay. Question paper · Answer key

More Compiler Design PYQs

PracticePractise Compiler Design questions →Full paperAll GATE CSE 2021 Set 2 questions →