CSE402 – Compiler Engineering

[Link], AP – III, SoC [Link], AP – III, SoC 1

1
 Intermediate Representations
• Front end – produces an intermediate representation (IR)
• Middle – transforms the IR into an equivalent IR that runs more efficiently
• Back end – transforms the IR into native code.
• IR encodes the compiler’s knowledge of the program
• Middle end usually consists of several passes.
• IR design affect speed and efficiency of the compiler.
• IR properties are:
1. Easy generation & manipulation
2. Freedom of expression
3. Level of abstraction.

[Link], AP – III, SoC 2

 Intermediate Representations
• Three Axes:
1. Structural organization [analysis, optimization & code generation]
2. Level of abstraction [operations probability & feasibility of different optimization].
3. Naming discipline [represent value in a code]
• Type of IR: Structural categories
1. Graphical - Trees, DAGs
Graph based
Source-to-source translation
Large
2. Linear – 3 address code, stack machine code
Pseudo-code for an abstract machine
Level of abstractions varies
Simple, compact data structures
Easier to rearrange.
3. Hybrid – Control flow graph.
Combination of graphs and linear code.

[Link], AP – III, SoC 3

 Intermediate Representations
Level of Abstraction
• High level AST – Good for memory disambiguation and low level AST – Good for address calculation.
• The level of detail exposed in an IR influences the profitability and feasibility of different optimizations.
• Two different representations of an array reference: A[i, j] 🡨 A[1to10, 1to10].
A[i, j] = BaseAddress (A)+ ((i-1)*rowsize+(j-1))

[Link], AP – III, SoC 4

 Intermediate Representations
Name space:
• Represent values in the code.
• E.g. a-2* b – represent by sequence of operations.

• 4 names are used here. Names are able to be reused but current value may not be available at the subsequent, redundant
evaluation.

[Link], AP – III, SoC 5

 Intermediate Representations –Graphical IR
• Syntax –related trees
Parse trees – graphical representation of the derivation.
Abstract syntax trees – Simplified version of the parse tree. Near source level representation.
Directed acyclic graphs – Avoid duplication in AST.
In optimization: Parse tree < Abstract syntax tree < DAG

• Graphs
Control-flow graph
Dependence graph
Call graph.

[Link], AP – III, SoC 6

 Intermediate Representations –Graphical IR
Parse Tree
• The parse tree is large relative to the source text because it represents the complete derivation, with a node for each
grammar symbol in the derivation.
• The compiler must allocate memory for each node and each edge, and it must traverse all those nodes and edges during
compilation, it is worth considering ways to shrink this parse tree.

[Link], AP – III, SoC 7

 Intermediate Representations –Graphical IR
Abstract Syntax Tree (AST)
• AST retains the essential structure of the parse tree but eliminate the extraneous nodes.
• The precedence and meaning of the expression remain, but extraneous nodes have disappeared.
• The AST is a near-source-level representation. The near-source-level affect usability.
• Many compiler and interpreters use AST. The level of abstraction varies widely source-level abstraction and below the
abstraction level.

[Link], AP – III, SoC 8

 Intermediate Representations –Graphical IR
Abstract Syntax Tree (AST) with different level of abstraction:
E.g. W= a – (2 * b) w=(rarp+4)−(2×(rarp+(−16)+@G+12))

• A val node represent the value already in a register. A num node represents a known constant. A lab node represents an

assembly-level label.

• ◆ indicates the dereferences a value. It treats the value as a memory address and returns the contents of the memory at that address.
• W is stored at offset 4 from the pointer in rarp, which holds the pointer to the data area for the current procedure.
[Link], AP – III, SoC 9
• The double dereference of a shows that is a call-by-reference formal access through 16 bytes before r .
 Intermediate Representations –Graphical IR
Directed Acyclic Graphs (DAG)
• A DAG avoids the duplications. In a DAG, nodes can have multiple parents, and identical subtrees are reused. Make sharing
explicit and encodes redundancy. Such sharing makes the DAG more compact than the corresponding AST.
• DAGs usage:
1. If memory constraints limit the size of programs that the compiler can handle, using a DAG can help by reducing the
memory footprint.
2. Better compiled code. The redundant code execute only once.

AST DAG

[Link], AP – III, SoC 10

 Intermediate Representations –Graphical IR
Example:
1. Construct parse tree, AST and DAG for the given expression.
Use the expression
E🡨E+T|E–T|T
T🡨T*F|T/F|F
F 🡨 (E) | id
a + a * (b – c) + (b- c) * d
2. Construct DAG for
T1= a + b a=b*c
T2 = a – b d= b
T3 = T1 * T2 e=d*c
T4 = T1 – T3 h=e
T5 = T4 + T3 f=b+c
g= f + d

[Link], AP – III, SoC 11

 Intermediate Representations –Graphical IR
Graphs – Control flow graph (CFG)
• The simplest unit of control flow in a program is a basic block – a maximal length sequence of
straight line , or branch-free, code.
• A basic block is a sequence of operations that always execute together, unless an operation
raises an exception.
• Control always enters a basic block at its first operation and exits at its last operation.
• A CFG models the flow of control between the basic blocks in a program.
• A CFG is a directed graph, G=(N, E). Each node n ∈ N corresponds to a basic block.
• Each edge e = (ni, nj) ∈ E corresponds to a possible transfer of control from block ni to block nj.
• The CFG provides a graphical representation of the possible runtime control flow paths.
• In CFG the edges show grammatical structure.

[Link], AP – III, SoC 12

 Intermediate Representations –Graphical IR
Graphs – Control flow graph (CFG)

[Link], AP – III, SoC 13

 Intermediate Representations –Graphical IR
Dependence graph
• Compilers use graphs to encode the flow of values from the point where a value is created, a definition, to any point where
it is used, a use.
• Data-dependence graph - a graph that models the flow of values from definitions to uses in a code fragment.
• Node in a data-dependence graph represent operations. Most operations contain both definitions and uses.
• An edge in a data-dependence graph connects two nodes, one that defines a value and another that use it.
• Draw dependence graphs with edges that run from definition to use.

[Link], AP – III, SoC 14

 Intermediate Representations –Graphical IR
Dependence graph

[Link], AP – III, SoC 15

 Intermediate Representations –Graphical IR
Dependence graph
• The graph has a node for each statement in the block. Each edge shows the flow of a single value.
• The edges in the graph represent real constraints on the sequencing of operations – a value cannot be used until it has been
defined.
• The dependence graph does not fully capture the program’s control flow. E.g. The graph requires that 1 and 2 precede 6.
• Dependency graph play a central role in instruction scheduling. Helps to reorder loops to expose parallelism and to
improve memory behavior. Interaction between control flow and the dependency graph: Initialization
↓
While condition (3)
↓ TRUE
If condition (4)
↙ ↘
TRUE FALSE
↓ ↓
(5) (6)
↘ ↙
(6)
↓
back to (3)

[Link], AP – III, SoC 16

 Intermediate Representations –Graphical IR
Call graph
• To address inefficiencies that arise across procedure boundaries, some
compilers perform inter-procedural analysis and optimization.
• To represent the runtime transfers of control between procedures,
compilers use a call graph. A call graph has a node for each procedure
and an edge for each distinct procedure call site.
• Inter-procedural – any technique that examines interactions across
multiple procedures is called inter-procedural.
• Intra-procedural – any technique that limits its attention to a single
procedure is called intra-procedural.

[Link], AP – III, SoC 17

 Intermediate Representations –Linear IR
• An assembly-language program is a form of linear code. It consists of a sequence of instructions that execute in their order
of appearance.
• Types of linear IRs:
1. One-address code – the behavior of accumulator machines and stack machines. These codes expose the machine’s use of
implicit names. E.g. Stack machine code
2. Two address code
3. Three-address code – A machine where most operations take two operands and produce a result.

[Link], AP – III, SoC 18

 Intermediate Representations –Linear IR
One-address code – Stack machine code:
• Most operations take their operands from the stack and push their results back onto the
stack.
• The stack discipline creates a need for some new operations. Stack IRs usually include
a swap operation that interchanges the top two elements of the stack.
• Several stack-based computers have been built.
• Stack-machine code is compact. The stack creates an implicit name space and
Example 2:
eliminates many names from the IR. This shrinks the size of a program in IR form.
((a + b) × (c − d) + e) / (f + g)
• Stack-machine code is simple to generate and to execute. E.g. byte code – an IR
ab+cd-*e+fg+/
designed specifically for its compact form typically code for an abstract stack machine.
E.g. a – 2* b

[Link], AP – III, SoC 19

 Intermediate Representations –Linear IR
Two address code:
• Allows statements of the form X 🡨 X op Y – has 1 operator and at most 2 names
• Can be very compact
• Example: z 🡨 x – 2 * y becomes

Example 2:
((a + b) × (c − d) + e) / (f + g)

• Problems:
Machines no longer rely on destructive operations
Difficult name space – destructive operations make reuse hard.

[Link], AP – III, SoC 20

 Intermediate Representations –Linear IR
Three address code:
• In three-address code most operations have the form i🡨 j op k, with an operator (op),
two operands (j and k) and one result (i).
• Some operations need fewer arguments and sometimes, an operation with more than
three addresses is needed.
• E.g. a-2*b
• Three-address code is reasonably compact. Most operations consist of four items: an
operation and three names.
Example 2:
• Both the operation and the names are drawn from limited sets. Operations typically
((a + b) × (c − d) + e) / (f + g)
require 1 or 2 bytes.
• Separate names for the operands and the target give the compiler freedom to control
the reuse of names and values. Three address code has no destructive operations.

[Link], AP – III, SoC 21

 Intermediate Representations –Linear IR
Type of Three address code:
• Quadruples – simple record structure and easy to reorder.
Explicit names.
E.g. x – y * 2

Example 2:
((a + b) × (c − d) + e) / (f + g)
• Triples – index used as implicit name, 25% less space
consumed than quads. Much harder to reorder.
E.g. x – y * 2

[Link], AP – III, SoC 22

 Intermediate Representations –Linear IR
Type of Three address code: Indirect triples
• List first triple in each statement. Implicit name space
Example 2:
• Uses more space than triples, but easier to reorder.
((a + b) × (c − d) + e) / (f + g)
• Major tradeoff between quads and triples is compactness versus ease of
manipulation.
• In the past compile-time space was critical. Today, speed may be more • Instead of direct references, it uses
important. pointers (indices) to another table.
• Each operation uses references to
previously computed values instead of
actual values.
• Store indices separately in a pointer table
reduces memory access costs.

[Link], AP – III, SoC 23

 Intermediate Representations –Linear IR
Type of Three address code: Indirect triples

[Link], AP – III, SoC 24

 Intermediate Representations –Linear IR
Representing Linear Codes
• Three-address codes (TAC) are often implemented as a set of quadruples. Each quadruple is represented with four fields: an operator, two
operands (or sources), and a destination.
• To form blocks, the compiler needs a mechanism to connect individual quadruples.
• Simple array – uses a short array to represent each basic block. Often, the compiler writer places the array inside a node in the CFG.
• Array of pointers – to group quadruples into a block. The pointer can be contained in a CFG node.
• Linked list – links the quadruples together to form a list. It requires less storage in the CFG node, at the cost of restricting accesses to sequential
traversals.

[Link], AP – III, SoC 25

 Intermediate Representations –Linear IR
Representing Linear Codes
• Simple array – moving the load of ‘b’ ahead of the immediate load [Swap] requires saving the four fields of the first operation, copying the
corresponding fields from the second slot into the first slot and overwriting the fields in the second slot with the saved values for the immediate
load.
• Array of pointers – same three step, except that only the pointer values must be changed. The compiler saves the pointer to the immediate load,
copies the pointer to the load of ‘b’ into the first slot in the array, and overwrites the second slot in the array with the saved pointer to the
immediate load.
• For the linked list, the operations are similar, except that the compiler must save enough state to let it traverse the list.

[Link], AP – III, SoC 26

 Intermediate Representations –Linear IR
Representing Linear Codes
• Simple array form and array of pointers, the compiler must select a size for the array, the number of quadruples that it
excepts in a block. As it generates the quadruples, it fills in the array.
• If the array is too large, it wastes space. If it is too small, the compiler must reallocate it to obtain a larger array, copy the
contents of the “too small” array into the new, larger array, and deallocate the small array.
• Linked avoids these problems. Expanding the list just requires allocating a new quadruple and setting the appropriate
pointer in the list.
• Front end to generate IR – linked list might both simplify the implementation and reduce the overall cost.
• Instruction scheduler – Focus on rearranging the operations, array implementations might make more sense.

[Link], AP – III, SoC 27

 Intermediate Representations –Linear IR
Representing Linear Codes

[Link], AP – III, SoC 28

 Intermediate Representations –Linear IR
Representing Linear Codes
2. c=0 3. swith(ch)
Example: Write three address code for the following
do{ {
1. if (a < b + c) Answer : t1 = b + c
if (a < b) then case 1: c = a+ b
a= a –c t2 = a < t1
x++; break;
c= b * c if t2 goto L0 else
else case 2: c = a – b;
goto L1
x--; break;
L0: t3 = a – c
c++; }
a = t3
} while (c < 5);
L1: t4 = b * c
c = t4

[Link], AP – III, SoC 29

 Intermediate Representations –Linear IR

Building a Control-Flow graph from a Linear code

• To build a CFG from a linear IR such as ILOC. In CFG, first step is the compiler must find the beginning and the end of
each basic blocks in the linear IR.
• The initial operation of a block a leader. An operation is a leader if it is the first operation in the procedure, or if it has a
label that is, potentially, the target of some branch.
• The compiler can identify leaders in a single pass over the IR. It iterates over the operations in the program, in order,
finds the labeled statements, and records them as leaders.

[Link], AP – III, SoC 30

 Intermediate Representations –Linear IR
Building basic blocks algorithm

[Link], AP – III, SoC 31

 Intermediate Representations –Linear IR
Building basic blocks algorithm

[Link], AP – III, SoC 32

 Intermediate Representations –Linear IR
Finding Leaders, last and adding edges

[Link], AP – III, SoC 33

 Intermediate Representations –Linear IR
Example (Linear to Hybrid)

[Link], AP – III, SoC 34

 Intermediate Representations –Mapping Values to
Names
• The discipline that the compiler uses to assign internal names to the various values computed during execution has an
effect on the code that it can generate.
• A naming scheme can expose opportunities for optimization or it can obscure them.
• The compiler must invent names for many, if not all, of the intermediate results that the program produces when it
executes.
• The choice that it makes with regard to names determines, to a large extent, which computations can be analyzed and
optimized.

[Link], AP – III, SoC 35

 Intermediate Representations –Mapping Values to
Names
1. Naming Temporary values:
• The IR form of a program usually contains more detail than does the source version. Some of those details are implicit in
the source code, other result from deliberate choices in the translation.
• Assume that the names refer to distinct values.

[Link], AP – III, SoC 36

 Intermediate Representations –Mapping Values to
Naming Temporary values: Names
• The block deals with just four names, {a, b, c, d}. It refers to more than four values.
• Each of b, c, and d have a value before the first statement executes. The first
statement computes a new value, b + c, as does the second, which computes a - d.
• The expression b + c in the third statement computes a different value than the earlier
b + c.
• The last statement computes a - d , its result is always identical to that produced by
the second statement.
• Value names reflect the computed values, identical expression produce same result.
• Source names uses fewer names than the value names. Source names can easily relate
the code back to the source code.
• Value names uses more names than the code. Its naming discipline reflects the
computed values and ensures that textually identical expressions produce the same
result.
• This one ensures that ‘a’ and ‘c’ may receive different values, while ‘b’ and ‘d’ must
receive the same value.

[Link], AP – III, SoC 37

 Intermediate Representations –Mapping Values to
Names
Naming Temporary values:
• Consider the representation of an array reference A[i, j]. Two IR
fragments that represent the same computation at very different
levels of abstraction.
• The high- level IR (source level AST) contains all the essential
information and is easy to identify as a subscript reference.
• The low-level IR (ILOC) – expose many details to the compiler
that are implicit in the high-level AST fragment. All of the details
in the low-level IR can be inferred from the source-level AST.
• In the low-level IR, each intermediate result has its own name.
using distinct names exposes those results to analysis and
transformation.

[Link], AP – III, SoC 38

 Intermediate Representations –Mapping Values to
Names
Static Single-Assignment (SSA) Form:
• SSA form – an IR that has a value-based name system, created by renaming and use of pseudo-operations called Ø - function.
• SSA encodes both control and value flow. It is used widely in optimization.
• In SSA form, names correspond uniquely to specific definition points in the code; each name is defined by one operation, hence the
name static single assignment.
• SSA form inserts special operations, called Ø – function, at points where control-flow paths meet.
• SSA form constraints:
1. Each definition has a distinct name.
2. Each use refers to a single definition.
• To transform an IR program to SSA form, the compiler inserts Ø – function at points where different control-flow paths merge and it
then renames variables to make the single-assignment property hold.
• Ø – function – Takes several names and merges them, defining a new name. The new name never redefined / killed and available in
along the path.

[Link], AP – III, SoC 39

 Intermediate Representations –Mapping Values to
Names
Static Single-Assignment Form (SSA):
• Variable names include subscripts to create a distinct
name for each definition. Ø – function have been
inserted at points where multiple distinct values can
reach the start of a block.
• The while construct has been rewritten with two
distinct tests, to reflect the fact that the initial test
refer to x0 while the end-of-loop test refers to x2.

[Link], AP – III, SoC 40

 Intermediate Representations
Exercises:
1. Show how the expression x – 2 * y might be translated into an AST, one-address code, two-address code and TAC.
2. Examine the code fragment. Draw its CFG and show its SSA form as a linear code.
3. Write the SSA form for:
a=10;
t=1;
while(a<100)
{
t= t+ a;
a = a -10;
}

[Link], AP – III, SoC 41

 Intermediate Representations –Mapping Values to
Names
Type of Memory Models
1. Register –to-Register Model [Compiler uses more registers than target machine provided]
• Keep all values that can legally be stored in a register
• Ignore machine limitations on number of registers
• Compiler back-end must insert loads and stores
• A value that cannot be kept in a register for most of its lifetime is stored in memory.
• The compiler generates code to store its value each time it is computed and to load its value at each use.
2. Memory-to-Memory Model [Uses fewer registers than a provided]
• Keep all values in memory
• Only promote values to registers directly before they are used
• Compiler back-end can remove loads and stores
• Compilers for RISC machines usually use register-to-register. Reflects programming model. Easier to determine when registers are
used.

[Link], AP – III, SoC 42

 Intermediate Representations –Mapping Values to
Names
Circumstances in which the models are desirable:
1. Register-to-Register model – Desired by compiler when the large amount of data needs to be kept in registers without limitation of physical
register set.
2. Memory-to-Memory – preferred when number of registers cannot be used by the compiler.

[Link], AP – III, SoC 43

 Intermediate Representations –Mapping Values to
Names
Exercise:
Write down the ILOC that a compiler’s front end might generate for this code under a register-to-register model and under a
memory-to-memory model. How do the two compare? Under what circumstances might each model be desirable?
Register-to-Register Model Memory-to-Memory model

[Link], AP – III, SoC 44

 Intermediate Representations –Symbol Tables
Symbol Tables:

• The symbol table localizes information derived from potentially distant parts of the source code. It
makes information easily and efficiently available, it simplifies the design and implementation of
any code.

• It avoids the expense of searching the IR to find the portion that represents a variables declarations
• Hash tables: Use a hash function, h, to map names to small integers, and use the small integer to
index the table.

• With a hashed symbol table, the compiler stores all the information that it derives about the name
‘n’ in the table in slot h(n).

• Hash tables is to provide a constant-time expected case lookup keyed by a textual name. To achieve
this, h must be inexpensive to compute.
[Link], AP – III, SoC 45
 Intermediate Representations –Symbol Tables
Hash table:
• Given an appropriate function h, accessing the record for ‘n’ requires computing h(n) and indexing into the table at h(n).
• If h maps two or more symbols to the same small integers, a collision occurs. If ‘h’ is a perfect hash function, that it never
produces a collision.

Building a Symbol table:

1. Lookup(name) returns the record stored in the table at h(name) if one exists. Otherwise, it returns a value indicating that
name was not found.
2. Insert(name, record) stores the information in record in the table at h(name). It may expand the table to accommodate the
record for name.
• The compiler can use separate functions for lookup and insert, or they can be combined by passing Lookup a flag that
specifies whether or not to insert the name.

[Link], AP – III, SoC 46

 Intermediate Representations –Symbol Tables
Building a Symbol table:
• In processing declaration syntax, the compiler builds up a set of attributes (type, scope, memory location etc.) for each
variable.

• When the parser recognizes a production that declares some variable, it can enter the name and attributes into the symbol
table using Insert.
int x, y;
• If a variable name can appear in only one declaration, the parser can call Lookup first to detect a repeated use of the name.
int x; lookup(variable_name)

[Link], AP – III, SoC 47

 Intermediate Representations –Symbol Tables
Building a Symbol table:
• When the parser encounters a variable name outside the declaration (variable in assignment, expression, or function call)
syntax, it uses Lookup to obtain the appropriate information from the symbol table.
During declaration During Expression parsing

• Lookup fails on any undeclared name. The compiler writer, may need to add functions to initialize the table, to store it to
and retrieve it from external media and to finalize it.

[Link], AP – III, SoC 48

 Intermediate Representations –Symbol Tables
Handling Nested Scopes:
• Most languages allow a program to declare names at
multiple levels. Each of these levels has a scope, or a
region in the program’s text where the name can be
used.
• Each of these levels has a lifetime, or a period at
runtime where the value is preserved.
• If the source language allows scopes to be nested
one inside another, then the front end needs a
mechanism to translate a reference, such as x, to the
proper scope and lifetime.
• The primary mechanism that compilers use to
perform this translation is a scoped symbol

[Link], AP – III, SoC 49

 Intermediate Representations –Symbol Tables
Handling Nested Scopes:
• To compile a program that contains nested scopes, the compiler must map each variable reference to
its specific declaration.
• This process, called name resolution, maps each reference to the lexical level at which it is declared.
• The mechanism that compilers use to accomplish this name resolution is a lexically scoped symbol
table.
• Each time the parser enters a new lexical scope, it can create a new symbol table for that scope.
• This scheme creates a sheaf of tables, linked together in an order that corresponds to the lexical nesting
levels.
• As it encounters declarations in the scope, it enters the information into the current table.
• Insert operates on the current symbol table. When encounters a variable reference, lookup must first
check the table for the current scope.
• If the current scope does not hold a declaration for the name, it checks the table for the surrounding
scope.

[Link], AP – III, SoC 50

 Intermediate Representations –Symbol Tables
Handling Nested Scopes:
• The compiler needs a call that initializes a new symbol table for a scope and one that finalizes the table
for a scope.
1. InitializeScope( ) – increments the current level and creates a new symbol table for that level. It links
the new table to the enclosing levels table and updates the current level pointer used by Lookup and
Insert.
2. FinalizeScope( ) – changes the current-level pointer so that it points to the table for the scope
surrounding the current level and then decrements the current level. If the compiler needs to preserve
the level-by-level tables for later use, FinalizeScope can either leave the table intact in memory or
write the table to external media and reclaim its space.

[Link], AP – III, SoC 51

 Intermediate Representations –Symbol Tables
Handling Nested Scopes:
• The parser calls InitializeScope each time it enters a
new lexical scope and FinalizeScope each time it
exits a lexical scope.
• As it enters each scope, the compiler calls
InitializeScope. It adds each name to the table using
Insert.
• When it leaves a given scope, it calls FinalizeScope
to discard the declarations for that scope.
• For assignment statement, it looks up each of the
names, as encountered.
• If finalizeScope retains the symbol table for finalized
levels in memory, the net result of these calls.

[Link], AP – III, SoC 52

 Intermediate Representations –Symbol Tables
Uses for Symbol Tables:
• Structure table – for each field in a structure, the compiler needs to record its type, its size, and its offset inside the record.
• Separate tables – the compiler can maintain a separate symbol table for each record definition.
• Selector table – the compiler can maintain a separate table for field names. To avoid clashes between fields with identical names in different
structures, it must use qualified names – concatenate either the name of the structure or something that uniquely maps to the structure.
• Unified table – the compiler can store field names in its principal symbol table by using qualified names.

[Link], AP – III, SoC 53

 Revision
1. Find the cost of the given expression a= (b + c) * (d – e) / f using Adhoc SDT representation.
2. Find the type of the given expression x = ( 5 + 3.5f) * (10.0 d – 2.0f) / 4.0d using type inferences.
3. Generating ILOC for an expression a= (b + c) * (d – e) / f
4. Construct parse tree, AST and DAG for an expression (a + b) * (c - d) + (a + b) / (c - d)
5. Generate one-address, two-address and three address for an expression (a + b) * (c - d) + (a + b) / (c - d)
6. Write a SSA (Static Single Assignment) for the given set of code
i 🡨....
while (i < 10)
{
x = i * 2;
y = x + 1;
i = i + 1;
}

[Link], AP – III, SoC 54

 Revision
7. Write a TAC, identify the leader and basic block for the following and code and construct the CFG
x = 0;
y = 0; #include <stdio.h>
while (x < 10) int main() {
int x = 0;
{
int y = 5;
y = y + x; while (x < 3) {
x = x + 1; int z = x + y;
} printf("Outer loop: x = %d, y = %d, z = %d\n", x, y, z);
if (y > 20) for (int i = 0; i < 2; i++) {
int l = z + i;
{
printf(" Inner for loop: i = %d, l = %d\n", i, l);
y = y - 10; if (l > 5) {
} int m = l * 2;
else printf(" If block: m = %d\n", m);
{ } else {
int n = l + 1;
y = y + 10;
printf(" Else block: n = %d\n", n);
} }
8. Construct the nested symbol table for the given code. }
x++;
}
return 0;
}

[Link], AP – III, SoC 55

 Revision
7. Write a TAC, identify the leader and basic block for the following and code and construct the CFG
x = 0;
y = 0;
while (x < 10)
{
y = y + x;
x = x + 1;
}
if (y > 20)
{
y = y - 10;
}
else
{
y = y + 10;
}
8. Construct the nested symbol table for the given code.

[Link], AP – III, SoC 56