L1.1.2 Introduction to Programming Languages.pptx

CSE425

1. Introduction to Programming Languages Dr. M. A. Rouf

2. 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 2 CSE-3821 Dr. M. A. Rouf, Dept. of CSE, DUET, Gazipur

3. Compilation Steps of C Program/ High-level Program CSE-3821 Dr. M. A. Rouf, Dept. of CSE, DUET, Gazipur Static linking 3 Scanner Parser Semantic analysis Intermediate code generation Machine-independent code improvement (optional ) Target code generation Machine-specific code improvement (optional)

4. Example of Compilation Process 4 CSE-3821 Dr. M. A. Rouf, Dept. of CSE, DUET, Gazipur Library Object Code

5. 5 Code Optimization Scanner (lexical analysis) Parser (syntax analysis) Code Optimizer Semantic Analysis (IC generator) Code Generator Symbol Table Source language tokens Syntactic structure Syntactic/semantic structure Target language CSE-3821 Dr. M. A. Rouf, Dept. of CSE, DUET, Gazipur

6. 6 Peephole Optimizations Constant Folding x := 32 becomes x := 64 x := x + 32 Unreachable Code goto L2 x := x + 1  U nneeded 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

7. CSE-3821 Dr. M. A. Rouf, Dept. of CSE, DUET, Gazipur 7 Peephole Optimizations Algebraic Simplification x := x + 0  unneeded Dead code void example1() { int x = 10; return; // Program exits here x = 20; // Dead code (never executed) } Reduction in strength Ex1: x := x * 2  x := x + x Ex2: Y=X^2 -> Y=X*X;

8. 8 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

9. 9 Simple example: a[ i+1 ] = b[ i+1 ] t1 = i+1 t2 = b[t1] t3 = i + 1 a[t3] = t2 t1 = i + 1 t2 = b[t1] t3 = i + 1  no longer live a[t1] = t2 Common Expression can be Eliminated CSE-3821 Dr. M. A. Rouf, Dept. of CSE, DUET, Gazipur

10. 10 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

11. 11 Constant Propagation b = 5 c = 4*b c > b d = b + 2 e = a + b b = 5 c = 20 c > 5 d = 7 e = a + 5 e = a + b t f t f b = 5 c = 20 20 > 5 d = 7 e = a + 5 t f CSE-3821 Dr. M. A. Rouf, Dept. of CSE, DUET, Gazipur

12. 12 Constant Propagation b = 5 c = 20 20 > 5 d = 7 e = a + 5 t f b = 5 c = 20 d = 7 e = a + 5 CSE-3821 Dr. M. A. Rouf, Dept. of CSE, DUET, Gazipur

13. 13 Copy Propagation b = a c = 4*b c > b d = b + 2 e = a + b b = a c = 4* a c > a d = a + 2 e = a + a e = a + b CSE-3821 Dr. M. A. Rouf, Dept. of CSE, DUET, Gazipur

14. CSE-3821 Dr. M. A. Rouf, Dept. of CSE, DUET, Gazipur 14 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;