4.1 [GATE 2006 : 2 Marks]
Question:
Consider the following C code segment.
for (i=0; i<n; i++)
{
for (j=0; j<n; j++)
{
if (i % 2)
{
x += (4 * j + 5 * i);
y += (7 + 4 * j);
}
}
}
Which one of the following is false?
(a) The code contains loop invariant computation
(b) There is scope of common sub-expression elimination in this code
(c) There is scope of strength reduction in this code
(d) There is scope of dead code elimination in this code
Answer: (d) There is scope of dead code elimination – This is FALSE
Solution:
(a) TRUE: i % 2 inner loop के लिए Loop Invariant है, क्योंकि i outer loop का है, inner loop में change नहीं होता। इसे inner loop से पहले निकाला जा सकता है।
(b) TRUE: 4j दो बार आ रहा है – एक बार x वाले statement में और एक बार y वाले में। ये Common Sub-Expression है। (c) TRUE: 4j को j*4 Multiplication है, इसे Strength Reduction से j<<2 या j+j+j+j में बदला जा सकता है, या induction variable से।
(d) FALSE: इस Code में कोई Dead Code नहीं है। x और y दोनों का Use हो रहा है, कोई Computation ऐसी नहीं जो Result को Use ही न करे।
1-Line Trick: 4*j = Common, i%2 = Loop Invariant, Dead Code कोई नहीं।
4.2 [GATE 2008 : 1 Mark]
Question:
Some code optimizations are carried out on the intermediate code because
(a) They enhance the portability of the compiler to other target processors
(b) Program analysis is more accurate on intermediate code than on machine code
(c) The information from data flow analysis cannot otherwise be used for optimization
(d) The information from the front end cannot otherwise be used for optimization
Answer: (a) They enhance the portability of the compiler to other target processors [GATE Official Answer]
Solution:
Compiler Structure: Source -> Front End -> Intermediate Code -> Optimizer -> Back End -> Machine Code.
Intermediate Code पर Optimization करने से फायदा ये है कि Optimizer Machine Independent रहता है। एक ही Optimizer को x86, ARM, RISC-V सबके लिए Use कर सकते हैं, सिर्फ Back End बदलो।
(b) भी Theoretically True है – Intermediate Code पर Analysis आसान होता है, Machine Code पर Registers और Scheduling की वजह से मुश्किल होता है, पर GATE ने (a) को ज्यादा Accurate माना है क्योंकि Portability Main Reason है।
1-Line Trick: IC पर Optimize = एक Optimizer, कई Target – Portability बढ़ती है।
4.3 [GATE 2010 : 1 Mark]
Question:
Which languages necessarily need heap allocation in the runtime environment?
(a) Those that support recursion
(b) Those that use dynamic scoping
(c) Those that allow dynamic data structures
(d) Those that use global variables
Answer: (c) Those that allow dynamic data structures
Solution:
(a) Recursion के लिए Stack ही काफी है, Activation Record Stack पर बनता है।
(b) Dynamic Scoping के लिए भी Stack से काम चल जाता है।
(d) Global Variables Static Data Area में रहते हैं।
(c) Dynamic Data Structures जैसे Linked List, Tree का Size Compile Time पर पता नहीं होता, Runtime पर बढ़ता-घटता है, इसलिए Heap पर malloc/free से Allocate करना पड़ता है। ये Heap Necessarily चाहिए।
1-Line Trick: Dynamic Structure = Size Runtime पर पता = Heap जरूरी।
4.4 [GATE 2011 : 2 Marks]
Question:
Consider two binary operators ‘↑’ and ‘↓’ with the precedence of operator ↓ being lower than that of the operator ↑. Operator ↑ is right associative while operator ↓ is left associative. Which one of the following represents the parse tree for expression (7↓3↑4↑3↓2)?
(a) (b) (c) (d) [Options are trees shown in image, (b) is marked as correct]
Answer: (b)
Solution:
Precedence: ↑ > ↓, तो ↑ पहले Evaluate होगा।
Associativity: ↑ Right, ↓ Left।
Step 1: 3↑4↑3 => ↑ Right है तो 3↑(4↑3)
Step 2: अब Expression बना 7↓[3↑(4↑3)]↓2
Step 3: ↓ Left है तो (7↓[3↑(4↑3)])↓2
तो Parse Tree:
Root = Last वाला ↓ (final)
Right Child = 2
Left Child = ↓ (first वाला)
– Left of that ↓ = 7
– Right of that ↓ = ↑ (3↑(4↑3))
– Left = 3, Right = ↑ (4↑3) with Left=4, Right=3
यही Structure Option (b) में है – ऊपर से ↓, फिर ↓, फिर ↑ की Right Chain।
1-Line Trick: High Precedence नीचे, Low Precedence ऊपर, Right Assoc = Right Chain।
Q 4.5 – GATE 2011 – Runtime Environment / Static ChainComplete Question:
Consider the program given below, in a block-structured pseudo-language with lexical scoping and nesting of procedures permitted.
Program main;
Var …
Procedure A1;
Var …
Call A2;
End A1
Procedure A2;
Var …
Procedure A21;
Var …
Call A1;
End A21
Call A21;
End A2
Call A1;
End main;
Consider the calling chain: Main -> A1 -> A2 -> A21 -> A1
The correct set of activation records along with their access links is given by ?Answer:
Option (D) – जिसमें:Main सबसे नीचे
A1 (first) -> access link = Main
A2 -> access link = Main
A21 -> access link = A2
A1 (second, A21 से call हुआ) -> access link = Main
Solution: Lexical scoping का Rule याद रख:
Access Link Rule: अगर Procedure P, Procedure Q के अंदर Define है, तो P का access link हमेशा Q के Most Recent Activation को point करेगा। Dynamic call chain से मतलब नहीं।
यहाँ Define कहाँ है?
A1 defined under Main
A2 defined under Main
A21 defined under A2
इसलिए:
1.Main का कोई access link नहीं (root)
Main -> A1 : A1 का access link -> Main
2.A1 -> A2 : A2 का access link -> Main (क्योंकि A2 Main में define है, A1 में नहीं)
3.A2 -> A21 : A21 का access link -> A2 (क्योंकि A21 A2 के अंदर define है)
4.A21 -> A1 : ये दूसरा A1 है, पर ये भी Main में define है, तो इसका access link भी -> Main
Call chain से stack बनता है: Main, A1, A2, A21, A1(top) और उनके access links ऊपर बताए जैसे।
1-Line Trick / Final Note:
GATE में हमेशा धोखा Call से होता है, Answer हमेशा Definition से निकलता है। Call को मत देखो, Procedure X कहाँ लिखा है वही देखो। A1 और A2 दोनों Main के बच्चे हैं, तो दोनों का बाप Main ही रहेगा चाहे किसी ने भी Call किया हो।
Common Data for 4.6 and 4.7 [GATE 2013 : 2 Marks]
Code Segment (only register operands, max 2 source + 1 dest, all vars dead after segment):
c = a + b;
d = c * a;
e = c * c;
if (d > a) {
b = a * a;
d = d * d;
e = e * e;
}
4.6 Minimum number of spills to memory with only 2 registers and code motion allowed?
(a) 0 (b) 1 (c) 2 (d) 3
Answer: (b) 1
Solution:
Without code motion, live ranges overlap ज्यादा हैं।
c = a+b (c live)
d = ca (c,d live) e = cc (c,d,e live – 3 registers needed)
पर Code Motion से b = aa को ऊपर ले जा सकते हैं, जो a के बाद independent है। Best allocation 2 registers में: R1 = a, R2 = b -> c = a+b (R2 = c, a still needed) d = ca needs a,c – okay
e = cc needs c only – पर d और e दोनों को बाद में जरूरत है if में। If में b = aa, d = dd, e = ee – यहाँ d,e को preserve करना पड़ेगा।
2 Registers में 1 variable को spill करना ही पड़ेगा (c को memory में)।
Code motion से 1 spill तक कम हो जाता है, 0 possible नहीं।
1-Line Trick: 2 Registers + 3 Live Vars (c,d,e) = 1 Spill पक्का, code motion से 2 से 1 हो जाता है।
4.7 Minimum number of registers needed without any spill, only register allocation optimization?
(a) 3 (b) 4 (c) 5 (d) 6
Answer: (b) 4
Solution:
Interference Graph बनाओ:
c = a+b -> a,b dead? नहीं, a बाद में use होता है (d=ca, e=cc, if condition, b=aa)। b भी बाद में use हो सकता है? Actually b = aa से overwrite हो रहा है, तो पहले वाला b dead है if से पहले।
Live Analysis:
After c=a+b: c live, a live (for d), b dead
After d=ca: c,d live, a live After e=cc: c,d,e live, a live (for if condition d>a and b=a*a)
if(d>a) block में: a,d,e live
तो Max Live at a time = c,d,e,a = 4 variables एक साथ।
इसलिए 4 Registers चाहिए बिना spill के।
1-Line Trick: Point e=c*c के बाद a,c,d,e 4 एक साथ live = 4 Registers।
4.8 [GATE 2014 Set-1 : 1 Mark]
Question:
Which one of the following is FALSE?
(a) A basic block is a sequence of instructions where control enters the sequence at the beginning and exits at the end.
(b) Available expression analysis can be used for common subexpression elimination.
(c) Live variable analysis can be used for dead code elimination.
(d) x = 4 * 5 => 20 is an example of common subexpression elimination.
Answer: (d) x = 4*5 => 20 is an example of common subexpression elimination.
Solution:
(a) TRUE – Basic Block की यही Definition है।
(b) TRUE – Available Expression से पता चलता है Expression पहले Compute हुआ है या नहीं, तो Common Subexpression Eliminate कर सकते हैं।
(c) TRUE – Live Variable Analysis से पता चलता है Variable आगे Use होगा या नहीं, Dead है तो Dead Code Elimination।
(d) FALSE – x=4*5 => 20 ये Constant Folding है, Common Subexpression Elimination नहीं। CSE में Same Expression दो जगह होता है जैसे a=b+c, d=b+c।
1-Line Trick: 4*5=>20 = Constant Folding, CSE नहीं।
4.9 [GATE 2014 Set-2 : 1 Mark]
Question:
Which one of the following is NOT performed during compilation?
(a) Dynamic memory allocation
(b) Type checking
(c) Symbol table management
(d) Inline expansion
Answer: (a) Dynamic memory allocation
Solution:
Compilation में Static चीजें होती हैं: Lexical Analysis, Parsing, Type Checking, Symbol Table, Intermediate Code, Optimization, Code Generation।
Inline expansion (function को call की जगह body रखना) Optimization में होता है।
Dynamic memory allocation (malloc/new) Runtime पर होता है, Compilation पर नहीं। Compiler सिर्फ उसके लिए Code Generate करता है, Allocation खुद Runtime पर OS करता है।
1-Line Trick: Dynamic Allocation = Runtime, Compilation = Static।
4.10 [GATE 2014 Set-2 : 1 Mark]
Question:
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?
(a) X is declared as int X[32][32][8]
(b) X is declared as int X[4][1024][32]
(c) X is declared as char X[4][32][8]
(d) X is declared as char X[32][16][2]
Answer: (a) X is declared as int X[32][32][8]
Solution:
Address Formula: X[i][j][k] = Base + (i * (Dim2Dim3elem_size) + j * (Dim3*elem_size) + k * elem_size)
Given: t0 = i1024, t1=j32, t2=k4 elem_size = 4 bytes (because k4 = int size 32 bits = 4 bytes)
So Dim3elem_size = 32 => Dim3 = 32/4 = 8 Dim2Dim3elem_size = 1024 => Dim284 = 1024 => Dim2 = 1024/32 = 32 तो Array = [?][32][8] और पहला Dimension 32 मान सकते हैं क्योंकि i1024 से।
Option (a) int X[32][32][8] exact match करता है: 3284=1024, 84=32, 14=4।
1-Line Trick: k4 = int (4 bytes), j32 = 84, i1024 = 3284 => [32][32][8].
4.11 [GATE 2014 Set-3 : 1 Mark]
Question:
Which of the following statements are CORRECT?
1) Static allocation of all data areas by a compiler makes it impossible to implement recursion.
2) Automatic garbage collection is essential to implement recursion.
3) Dynamic allocation of activation records is essential to implement recursion.
4) Both heap and stack are essential to implement recursion.
(a) 1 and 2 only (b) 2 and 3 only (c) 3 and 4 only (d) 1 and 3 only
Answer: (d) 1 and 3 only
Solution:
1) TRUE: Static allocation में Compile Time पर ही एक ही Copy Fix होती है। Recursion में एक ही Function की कई Copies एक साथ Active होती हैं, हर Call का अलग Activation Record चाहिए, तो Static से Possible नहीं।
2) FALSE: Recursion के लिए Garbage Collection जरूरी नहीं, C Language बिना GC के Recursion Support करती है। Return पर Stack Pop हो जाता है।
3) TRUE: हर Recursive Call के लिए नया Activation Record Runtime पर Dynamically बनना चाहिए (Stack पर)।
4) FALSE: Recursion के लिए सिर्फ Stack ही Essential है, Heap जरूरी नहीं। Heap Dynamic Data के लिए होता है।
1-Line Trick: Recursion = Stack पर Dynamic AR, Static से नहीं होगा, GC/Heap से कोई लेना-देना नहीं।
4.12 [GATE 2014 Set-3 : 2 Marks]
Question:
Consider the basic block given below.
a = b + c
c = a + d
d = b + c
e = d – b
a = e + b
The minimum number of nodes and edges present in the DAG representation of the above basic block respectively are
(a) 6 and 6 (b) 8 and 10 (c) 9 and 12 (d) 4 and 4
Answer: (a) 6 and 6
Solution:
DAG बनाओ:
Leaf Nodes: b, c, d (3 Nodes)
Step1: a = b+c => Node (+)1 with child b,c -> a attach
Step2: c = a + d => Node (+)2 with child (+)1,a और d -> c attach (a का value (+)1 ही है)
Step3: d = b + c => b + c = b + (a+d) = b + ((b+c)+d) -> पर CSE देखो: b+c पहले से है (+)1, इसलिए d = (+)1 ही, नया Node नहीं।
Step4: e = d – b => Node (-)1 with child d(+)1 और b
Step5: a = e + b => Node (+)3 with child (-)1 और b -> a redefined
Total Distinct Nodes:
Leaves: b,c,d = 3
Interior: (+)1(b+c), (+)2(a+d), (-)1(d-b), (+)3(e+b) = 4? पर (+)1 reuse होने से actually 6 Nodes ही बनते हैं।
Edges: हर Interior Node के 2 Edges = 6 Edges.
Optimized count = 6 Nodes, 6 Edges।
1-Line Trick: b+c Common है, d = b+c reuse -> Node कम = 6 Nodes, 6 Edges।
4.13 [GATE 2015 Set-1 : 2 Marks]
Question:
A variable x is said to be live at a statement Si if:
- There exists a statement Sj that uses x
- There is a path from Si to Sj in the flow graph
- The path has no intervening assignment to x including at Si and Sj
Flow graph: Block1: p=q+r, s=p+q, u=sv | Block2: v=r+u | Block3: q=su | Block4: q=v+r with edges 1->2,1->3,2->4,3->4,4->1
The variables which are live both at the end of basic block 2 and at the end of basic block 3 are?
(a) p,s,u (b) r,s,u (c) r,u (d) q,v
Answer: (b) r, s, u
Solution:
Live at end of block = उस Block के बाद कौन से Variables आगे Use होंगे बिना Redefine हुए।
Block4 में: q = v + r => v,r use, q define। So v,r live on entry to 4।
Block2: v = r + u => r,u use। Its end goes to Block4, so live out of 2 includes r,u plus what is live out of 4 (r,v) minus def(v) = r,u,r,v => r,u,v? But v is defined in 2, so not live out of 2? Actually analysis से:
Block3: q = s * u => s,u use।
Block1 uses q,r,s,v etc.
Full Data Flow करने पर: r हर जगह Use होता है (Block2 और Block4 में), s Block1 में Define होकर Block3 में Use होता है, u Block1 में Define होकर Block2,3 में Use होता है।
Intersection of live at end of 2 and end of 3 = r,s,u।
1-Line Trick: r,s,u ही दोनों Branches से आगे जाकर Block1/4 में Use होते हैं।
4.14 [GATE 2015 Set-1 : 2 Marks]
Question:
The least number of temporary variables required to create a three-address code in static single assignment form for the expression q + r/3 + s – t5 + uv/w is _
Answer: 8
Solution:
SSA में हर Assignment नया Variable, हर Binary Operation के लिए नया Temp।
Break:
t1 = r / 3
t2 = t * 5
t3 = u * v
t4 = t3 / w
t5 = q + t1
t6 = t5 + s
t7 = t6 – t2
t8 = t7 + t4
Total 8 Temporaries।
कोई Common Subexpression नहीं, तो reuse नहीं।
1-Line Trick: 4 Division/Multi + 4 Add/Sub = 8 Temps।
4.15 [GATE 2015 Set-2 : 1 Mark]
Question:
In the context of abstract-syntax-tree (AST) and control-flow-graph (CFG), which one of the following is TRUE?
(a) In both AST and CFG, let node N2 be successor of N1. Code of N2 is present after code of N1 in input program.
(b) For any input program, neither AST nor CFG will contain a cycle
(c) The maximum number of successors of a node in an AST and a CFG depends on the input program
(d) Each node in AST and CFG corresponds to at most one statement in input program
Answer: (c) The maximum number of successors of a node in an AST and a CFG depends on the input program
Solution:
(a) FALSE: CFG में Successor Loop की वजह से पहले भी हो सकता है (backward edge)। AST में ही Order Follow होता है।
(b) FALSE: AST में Cycle कभी नहीं होता (Tree है), पर CFG में Loop की वजह से Cycle होता है।
(c) TRUE: AST में Node के Successors = Operator के Operands की संख्या, जो Program पर Depend करती है। CFG में Node के Successors = Basic Block से कितने Branches निकल रहे हैं (if-else में 2, switch में ज्यादा), ये भी Program पर Depend।
(d) FALSE: CFG के एक Node (Basic Block) में Multiple Statements हो सकते हैं। AST का Leaf एक Statement हो सकता है पर Interior Node Expression होता है।
1-Line Trick: AST = No Cycle, CFG = Cycle Possible, Successor Count = Program Dependent।
4.16 [GATE 2015 Set-2 : 2 Marks]
Question:
Consider the intermediate code:
- i=1 2. j=1 3. t1=5i 4. t2=t1+j 5. t3=4t2 6. t4=t3 7. a[t4]=-1 8. j=j+1 9. if j<=5 goto(3) 10. i=i+1 11. if i<5 goto(2)
The number of nodes and edges in the control-flow-graph respectively are?
(a) 5 and 7 (b) 6 and 7 (c) 5 and 5 (d) 7 and 8
Answer: (b) 6 and 7
Solution:
Basic Blocks बनाओ:
B1: 1. i=1 (Leader)
B2: 2. j=1 (Target of goto 11)
B3: 3-8. t1=5*i… j=j+1 (Target of goto 9, includes 3-8, no jump inside)
B4: 9. if j<=5 goto(3) (Conditional) B5: 10. i=i+1 (Fall through) B6: 11. if i<5 goto(2) (Conditional) Total 6 Nodes। Edges: B1->B2
B2->B3
B3->B4
B4->B3 (True) and B4->B5 (False) = 2 edges
B5->B6
B6->B2 (True) and B6->Exit (False) = 2 edges? पर Exit को Node नहीं गिनते तो B6->B2 only 1? Standard Counting में 7 Edges बनते हैं: B1-B2, B2-B3, B3-B4, B4-B3, B4-B5, B5-B6, B6-B2 = 7 Edges।
1-Line Trick: 2 Loops = 6 Blocks, 7 Edges।