GATE CSE 2006 | Question: 55

Question

Consider these two functions and two statements S1 and S2 about them. 

int work1(int *a, int i, int j) { int x = a[i+2]; a[j] = x+1; return a[i+2] - 3; }

int work2(int *a, int i, int j) { int t1 = i+2; int t2 = a[t1]; a[j] = t2+1; return t2 - 3; }

S1: The transformation form work1 to work2 is valid, i.e., for any program state and input arguments, work2 will compute the same output and have the same effect on program state as work1 

S2: All the transformations applied to work1 to get work2 will always improve the performance (i.e reduce CPU time) of work2 compared to work1

• A. S1 is false and S2 is false
• B. S1 is false and S2 is true
• C. S1 is true and S2 is false
• D. S1 is true and S2 is true

Comments

https://gemini.google.com/share/35e4965f517b
is it correct ? @P0535_Yedidyah_Sagar

---

@js__

Sorry, for the very late reply. 

I have updated my comment to be more clear.

Gemini is wrong. 

---

@P0535_Yedidyah_Sagar Yeah u are correct

Answer 1

Consider an array a = 1 2 3 4 5 and condition i + 2 =j. Lets take i =0 and j =2 for this example.

Work 1, 

x = a[0+2] = 3

a[2] = 3 + 1 = 4;  which means a = 1 2 4 4 5

return a[0+2] - 3 = 4 -3 = 1

Work 2

t1 = 0 + 2 = 2

t2 = a[2] = 3

a[2] = 3 + 1 = 4, which means a = 1 2 4 4 5 again

return t2 - 3 = 3 -3 =0

Hence S1 is false when i + 2 =j. S2 will also be false, since we cant explicitly say the performance of work2 will always be better than work1.

Hence answer is A

Comments

in the work2 , wer are storing value of a[t1] i..e a[i+2] in t2 and at the end we are returning t2 - 3 and in between the value of t2 is not changed. Now in work1 we are returning a[i+2] - 3 at the end, now in order for this value to be different from t2 - 3 we should somehow modify the value at a[i+2].

a[j] = x+1, now if j==i+2 that means a[i+2] is modified and the values will be different.

---

in work1, in line_2, we are changing the array, and then in line_3, we are again accessing the value and returning it.

 

In work2, we are storing a value of the array to a variable, then changing array, and then returning the stored value, that's where it changes, we, in work2 did not account for the change in the array that might affect the return value.

---

We can take any condition for j but taking j=i+2 gives the different answers for both statements.So,we consider it to just evaluate answer

Answer 2

answer - A

when j == i+2 programs will return different results

Comments

@ana @himesh  @rohan

option A is correct .

---

May anyone pls tell how such questions can be solved during gate exam? As S1 is false only when j=I+2.How to check the code robustness for any condition? Any suggestions would be appreciated.

---

because in the program we are using the index as i+2 only.

in work1,

int x=a[i+2];

and in work2

int t1=i+2;

int t2=a[t1]

 even in the return statement you can see the a[i+2]-3

we can see that, in the program it is trying to access the (i+2)th index most of the time. so basically we just try to do some modification with the value in the (i+2)th index using the variable 'j'.

if we change something like

a[i+2]=4;

and then we use j for the same

a[j]=5;

where, j=i+2

we can observe the changes only when both will conflict.

Answer 3

CounterExample for statement 1:

a= [1,7,12,3,9,6,5,13]

i=2 and j=4

{you can simply run & check that}

Code 1 will return 7 while Code 2 will return 6 , so the transformation is invalid.

 

Now statement 2: yes we are reducing computation of i+2 by storing it in a temp, but we can't gaurantee that this will always increase efficiency as this is high level optimization, & we have no idea of machine & behaviour during it.

Answer 4

 

 

The Correct Option

 

S1 is false and S2 is false

---

 

Analysis of the Code

 

To understand why, let's look at what the compiler (or the programmer) changed between work1 and work2.

• work1: Reads a[i+2] twice. Once to assign it to x, and again at the end for the return statement.

• work2: Reads a[i+2] once, stores it in a temporary variable t2, and reuses t2 for the return statement.

This transformation is known as Common Subexpression Elimination (CSE). The compiler assumes that a[i+2] does not change between the first read and the second read.

---

 

Step-by-Step Approach

 

 

1. Analyzing Statement S1 (Validity)

 

Statement: The transformation from work1 to work2 is valid... work2 will compute the same output... as work1.

Verdict: FALSE

Reasoning:

This statement fails due to Memory Aliasing. Aliasing occurs when two different pointers or indices refer to the same memory location.

Let's assume a specific case where i and j cause an overlap:

• Let i = 0

• Let j = 2

• Therefore, the index i+2 is the same as index j.

• Let the array a initially be {10, 20, 30, 40}. So a[2] is 30.

Trace for work1 (No Optimization):

1. x = a[0+2] (which is a[2]). So, x = 30.

2. a[j] = x + 1. Since j=2, we set a[2] = 31. (Memory is updated)

3. return a[i+2] - 3. Since i+2 is 2, this reads the new value of a[2].

4. Calculation: $31 - 3 = 28$.

5. Result: 28.

Trace for work2 (With Optimization):

1. t1 = 0+2.

2. t2 = a[t1]. So, t2 = 30. (The value is cached in a register/variable).

3. a[j] = t2 + 1. Since j=2, we set a[2] = 31. (Memory is updated)

4. return t2 - 3. This uses the old cached value of t2.

5. Calculation: $30 - 3 = 27$.

6. Result: 27.

Conclusion: Because the outputs differ (28 vs 27) when aliasing occurs, the transformation is not valid for all program states.

 

2. Analyzing Statement S2 (Performance)

 

Statement: All the transformations... will always improve the performance... of work2 compared to work1.

Verdict: FALSE

Reasoning:

While removing a redundant memory load (reading a[i+2] twice) usually improves speed, the word "always" makes this statement false in the context of compiler theory.

1. Register Pressure: In work2, the variable t2 must be kept "alive" (held in a CPU register) across the execution of line a[j] = t2+1.

2. Spilling: If the CPU has very few registers available (high register pressure), the compiler might be forced to "spill" t2 to the stack (RAM) to free up a register for the assignment operation, and then reload it later.

3. Cost: Spilling to the stack and reloading can be just as expensive, or sometimes more expensive, than simply reloading the value from the L1 cache as done in work1.

Therefore, we cannot guarantee that this transformation always reduces CPU time.

---

 

Summary Table

 

Statement	Truth Value	Key Concept
S1	False	Aliasing: a[j] might overwrite a[i+2], changing the return value in work1 but not work2.
S2	False	Register Pressure: Holding the temporary variable t2 might cause register spilling, potentially degrading performance

Answer 5

Ans- C

Only an extra variable t1 has been added in work 2 instead of directly computing the subscript as in work 1.The output will be same. S1 is true.

The addition of variables t1 and t2 will not improve the performance in anyway. i.e S2 is false.

Corrcet me I'm wrong

Comments

• Assume a[i+2] = 10, and j == i+2.

In work1:

1. x = a[i+2]; →x = 10

2. a[j] = x + 1; →a[i+2] = 11

3. return a[i+2] - 3; → returns 11 - 3 = 8

In work2:

1. t1 = i+2;

2. t2 = a[t1]; → t2 = 10 (loaded before the store)

3. a[j] = t2 + 1; →a[i+2] = 11

4. return t2 - 3; → returns 10 - 3 = 7
    

So S1 is false.