GATE CS 2014 Set 2 Q.44 (CS Q.34): Intermediate Code Generation, Data Flow Analysis and Code Optimization

For a C program accessing X[i][j][k], the following intermediate code is generated by a compiler. Assume that the size of an integer is 32 bits and the size of a character is 8 bits.

t0 = i * 1024
t1 = j * 32
t2 = k * 4
t3 = t1 + t0
t4 = t3 + t2
t5 = X[t4]

Which one of the following statements about the source code for the C program is CORRECT?

X is declared as "int X[32][32][8]".

X is declared as "int X[4][1024][32]".

X is declared as "char X[4][32][8]".

X is declared as "char X[32][16][2]".

Official answer and solution

Official answer: A
From: Official GATE 2014 answer key

Solution

Match the generated intermediate address arithmetic with standard 3D array row-major memory offset formulas.

Intermediate Code Analysis:
The generated offset is:
$\text{offset} = t_4 = 1024 \cdot i + 32 \cdot j + 4 \cdot k.$
Standard Row-Major Offset Formula:
For an array declared as Type X[D1][D2][D3] with element size $S$ bytes:
$\text{Byte Offset}(i, j, k) = (i \cdot D_2 \cdot D_3 + j \cdot D_3 + k) \cdot S$ $= i \cdot (D_2 \cdot D_3 \cdot S) + j \cdot (D_3 \cdot S) + k \cdot S.$
Matching Coefficients:
- Coefficient of $k$ : $S = 4$ bytes.
  Since an int is given as 32 bits = 4 bytes and char is 8 bits = 1 byte, the base type of $X$ must be int.
- Coefficient of $j$ : $D_3 \cdot S = 32 \implies D_3 \cdot 4 = 32 \implies D_3 = 8$ .
- Coefficient of $i$ : $D_2 \cdot D_3 \cdot S = 1024 \implies D_2 \cdot 32 = 1024 \implies D_2 = 32$ .
- The outer dimension $D_1$ does not affect the offset calculation within bounds; among the given options, $D_1 = 32$ .
Conclusion:
$X$ is declared as int X[32][32][8], which matches option (A).

Final answer

Common trap

Assuming the outer dimension D1 appears in the offset formula; offset calculation only involves trailing dimensions D2 and D3.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2014 Computer Science and Information Technology (CS) Session 2
Question: 44 of 65, printed as CS Q.34
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source