The document Optimization Of Basic Blocks Computer Science Engineering (CSE) Notes | EduRev is a part of the Computer Science Engineering (CSE) Course Compiler Design.

All you need of Computer Science Engineering (CSE) at this link: Computer Science Engineering (CSE)

**3. OPTIMIZATION OF BASIC BLOCKS**

There are two types of basic block optimizations.

They are :

Structure -Preserving Transformations

Algebraic Transformations

**.1 Structure- Preserving Transformations**:

The primary Structure-Preserving Transformation on basic blocks are: � Common sub-expression elimination

- Dead code elimination
- Renaming of temporary variables
- Interchange of two independent adjacent statements.

**3.2 Common sub-expression elimination: **

Common sub expressions need not be computed over and over again. Instead they can be computed once and kept in store from where it’s referenced when encountered again – of course providing the variable values in the expression still remain constant.

Example:

a: =b+c

b: =a-d

c: =b+c

d: =a-d

The 2^{nd} and 4^{th} statements compute the same expression: b+c and a-d

Basic block can be transformed to

a: =b+c

b: =a-d

c: =a

d: =b

**3.3 Dead code elimination: **

It’s possible that a large amount of dead (useless) code may exist in the program. This might be especially caused when introducing variables and procedures as part of construction or error -correction of a program – once declared and defined, one forgets to remove them in case they serve no purpose. Eliminating these will definitely optimize the code. 3.4 Renaming of temporary variables:

- A statement t:=b+c where t is a temporary name can be changed to u:=b+c where u is another temporary name, and change all uses of t to u.

- In this we can transform a basic block to its equivalent block called normal-form block.

**3.5 Interchange of two independent adjacent statements:**

Two statements

t1:=b+c

t2:=x+y

can be interchanged or reordered in its computation in the basic block when value of t1 does not affect the value of t2.

**3.6 Algebraic Transformations:**

- Algebraic identities represent another important class of optimizations on basic blocks. This includes simplifying expressions or replacing expensive operation by cheaper ones i.e. reduction in strength.

- Another class of related optimizations is constant folding. Here we evaluate constant expressions at compile time and replace the constant expressions by their values. Thus the expression 2*3.14 would be replaced by 6.28.

- The relational operators <=, >=, <, >, + and = sometimes generate unexpected common sub expressions.

- Associative laws may also be applied to expose common sub expressions. For example, if the source code has the assignments

a :=b+c e :=c+d+b

the following intermediate code may be generated:

a :=b+c t :=c+d

e :=t+b

- The compiler writer should examine the language carefully to determine what rearrangements of computations are permitted; since computer arithmetic does not always obey the algebraic identities of mathematics. Thus, a compiler may evaluate x*y-x*z as x*(y-z) but it may not evaluate a+(b-c) as (a+b)-c.

Offer running on EduRev: __Apply code STAYHOME200__ to get INR 200 off on our premium plan EduRev Infinity!

16 videos|44 docs|29 tests