Basic blocks - compiler design

This is our compiler design presentation. The presentation topic is Basic Blocks.

Hope you enjoy it...

1. Great Mates

2. WELCOME! Thank you for coming today!

3. Fazle Rabbi Khan 161-15-6917

4. 4 BASIC BLOCKS AND FLOW GRAPHS

5. 5 What is Basic Blocks? A basic block is a sequence of consecutive instructions which are always executed in sequence without halt or possibility of branching.

6. 6 Type of Basic Blocks Basic Blocks Transformations on Basic Blocks Structure preserving Transformations Algebraic transformations Representation of Basic Blocks

7. 7 Steps of Basic Blocks Introduce a graph representation of three address statement that is helpful for discussing code generation . Nodes in flow graph – Computation Edges in flow graph – Control Flow Register Assignment to find inner loop flow control is used . Partition the intermediate code into basic blocks The basic blocks become the nodes of a flow graph, whose edges indicate which blocks can follow which other blocks.

8. 8 Basic Blocks B 2 : The flow graph for the above three address code is given below: B1: PROD = I = 1 T2=addr(A)-4 T4 =addr(B)-4 T1 =4*I T3= T2[T1] T5 = T4[T1] T6 =T3*T5 PROD =PROD + T6 I =I+1 IF I<= 20 GOTO B2

9. A bdur Rahman 162-15-7749

10. 10 Basic Blocks Construction Algorithm. Algorithm: Partitioning three-address instructions into basic blocks . INPUT: A sequence of three-address instructions . OUTPUT: A list of the basic blocks for that sequence in which each instruction is assigned to exactly one basic block.

11. 11 Basic Blocks Find the leaders

12. Basic Blocks

13. 13 Follow Diagram

14. 14 H.M Nasim 161-15-7365

15. 15 T rans f ormations on B a si c Blo c ks A code-improving transformation is a code optimization to improve speed or reduce code size . Global transformations are performed across basic blocks . Local transformations are only performed on single basic blocks. Transformations must be safe and preserve the meaning of the code . A local transformation is safe if the transformed basic block is guaranteed to be equivalent to its original form

16. 16 Transformations on Basic Blocks Local Transformation Some local transformation are: Common- S u b e xpre s sion Elimination Dead Code Elimination Renaming Temporary Variables Interchange of Statements Algebraic T r a ns f o r m a tio n s

17. 17 Common- Subexpression Elimination Remove redundant computations 2nd and 4th:compute same expression in fig:1(a) Look at 1st and 3 rd in fig:1(b) :b is redefine in 2 nd therefore different in3rd, not the same expression f ig:1(a) f ig:1(b) a := b + c b := a - d c := b + c d := a - d a := b + c b := a - d c := b + c d := b t1 := b * c t2 := a - t1 t3 := b * c t4 := t2 + t3 t1 := b * c t2 := a - t1 t4 := t2 + t1

18. 18 Sukanta Dey 161-15-7259

19. Dead Code Elimination Remove unused statements Assuming a is dead (not used) Remove unreachable code b := a + 1 a := b + c … b := a + 1 … goto L2 b := x + y …

20. Renaming Temporary Variables Temporary variables that are dead at the end of a block can be safely renamed. The basic block is transforms into an equivalent block in which each statement that defines a temporary defines a new temporary. Such a basic block is called normal-form block or simple block . Normal-form block Note that normal-form blocks permit all statement interchanges that are possible. t1 := b + c t2 := a - t1 t1 := t1 * d d := t2 + t1 t1 := b + c t2 := a - t1 t3 := t1 * d d := t2 + t3

21. Interchange of Statements Independent statements can be reordered without effecting the value of block to make its optimal use. Note that normal-form blocks permit all statement interchanges that are possible t1 := b + c t2 := a - t1 t3 := t1 * d d := t2 + t3 t1 := b + c t3 := t1 * d t2 := a - t1 d := t2 + t3

22. 22 OVI modak 162-15-7795

23. Algebraic Transformations Change arithmetic operations to transform blocks to algebraic equivalent forms. Simplify expression or replace expensive expressions by cheaper ones. In statement 3,usually require a function call Transforms to simple and equivalent statement t1 := a - a t2 := b + t1 t3 := t2 **2 t1 := t2 := b t3 := t2 * t2

24. 24 Representation of Basic Blocks Variety of data structures . Quadruples are used with pointers . Jumping from one block to another block with conditional and unconditional jumps . Block B finishes the code then B’ is continued Block B’ reaches last line then control goes back to the beginning of B’.

25. 25 LOOPS of Diagram No.1 No. 2 No. 3 Loop contains no other loop is called inner loop. The collection of node has unique entry All node in the collection are strongly connected.

26. 26 Google.com Wikipedia . Slide Shares.com Online.Visual-paradiagram.com Youtube.com Reference & Tools

27. THANK Y OU! ANY QUESTIONS?