Introduction to
Programming
Languages
Dr. M. A. Rouf
Compilation vs. Translation
• Translation: does a ‘mechanical’ translation of the source
code
• No deep analysis of the syntax/semantics of the code
• Compilation: does a thorough understanding and translation
of the code
• A compiler/translator changes a program from one language
into another
• C compiler: from C into assembly
• An assembler then translates it into machine language
• Java compiler: from Java code to Java bytecode
• The Java interpreter then runs the bytecode
CSE-3821 Dr. M. A. Rouf, Dept. of CSE, DUET, Gazipur 2
Compilation Steps of C Program/
High-level Program
1. Scanner
2. Parser
3. Semantic analysis
4. Intermediate code generation
5. Machine-independent code improvement
(optional)
1. Target code generation
2. Machine-specific code improvement (optional)
Static linking
CSE-3821 Dr. M. A. Rouf, Dept. of CSE, DUET,
Gazipur
3
Example of Compilation
Process
Object Code
Library
CSE-3821 Dr. M. A. Rouf, Dept. of CSE, DUET, Gazipur 4
Code Optimization
Syntactic/semantic
structure
tokens Syntactic
Scanner Parser structure Semantic Code
Source Target
language
(lexical (syntax Analysis Generator language
analysis) analysis) (IC generator)
Code
Optimizer
Symbol
Table
CSE-3821 Dr. M. A. Rouf, Dept. of CSE, DUET, Gazipur 5
Peephole Optimizations
• Constant Folding
x := 32 becomes x := 64
x := x + 32
• Unreachable Code
goto L2
x := x + 1 Unneeded Code
L2:
• Flow of Control Optimizations
goto L1 becomes goto L2
…
L1: goto L2
CSE-3821 Dr. M. A. Rouf, Dept. of CSE, DUET, Gazipur 6
Peephole Optimizations
• Algebraic Simplification
x := x + 0 unneeded
• Dead code
x := 32 where x not used after statement
y := x + y y := y + 32
• Reduction in strength
x := x * 2 x := x + x
CSE-3821 Dr. M. A. Rouf, Dept. of CSE, DUET, Gazipur 7
Basic Block Level
• Common Subexpression elimination
• Constant Propagation
• Dead code elimination
• Plus many others such as copy propagation, value numbering, partial
redundancy elimination, …
CSE-3821 Dr. M. A. Rouf, Dept. of CSE, DUET, Gazipur 8
Common Expression can be Eliminated
Simple example: a[i+1] = b[i+1]
• t1 = i+1 • t1 = i + 1
• t2 = b[t1] • t2 = b[t1]
• t3 = i + 1 • t3 = i + 1 no longer live
• a[t3] = t2 • a[t1] = t2
CSE-3821 Dr. M. A. Rouf, Dept. of CSE, DUET, Gazipur 9
Control Flow Graph - CFG
CFG = < V, E, Entry >, where
V = vertices or nodes, representing an instruction or basic
block (group of statements).
E = (V x V) edges, potential flow of control
Entry is an element of V, the unique program entry
Two sets used in algorithms:
• Succ(v) = {x in V| exists e in E, e = v x}
• Pred(v) = {x in V| exists e in E, e = x v}
1 2 3 4 5
CSE-3821 Dr. M. A. Rouf, Dept. of CSE, DUET, Gazipur 10
Constant Propagation
b=5 b=5 b=5
c = 4*b c = 20 c = 20
c>b c>5 20 > 5
t t t
f f f
d=b+2 d=7 d=7
e=a+b e=a+5 e=a+5
CSE-3821 Dr. M. A. Rouf, Dept. of CSE, DUET, Gazipur 11
Constant Propagation
b=5 b=5
c = 20 c = 20
20 > 5 d=7
t e=a+5
f
d=7
e=a+5
CSE-3821 Dr. M. A. Rouf, Dept. of CSE, DUET, Gazipur 12
Copy Propagation
b=a b=a
c = 4*b c = 4*a
c>b c>a
d=b+2 d=a+2
e=a+b e=a+a
CSE-3821 Dr. M. A. Rouf, Dept. of CSE, DUET, Gazipur 13
Data Dependencies
• Flow Dependencies – Read After Write (RAW)
x := 4;
y := x + 1
• Output Dependencies – Write After Write (WAW)
x := 4;
x := y + 1;
• Antidependencies – Write After Read (WAR)
y := x + 1;
x := 4;
CSE-3821 Dr. M. A. Rouf, Dept. of CSE, DUET, Gazipur 14
