Optimization of Basic Blocks in Compiler Design

Optimization of Basic Blocks

We can apply the optimization process on a basic block. While optimization, there is no need to change the set of expressions computed by the block.

The basic block optimization can be done in two ways:

  • Structure-Preserving Transformations
  • Algebraic Transformations

Structure-Preserving Transformations

The primary Structure-Preserving Transformation on basic blocks are as follows:

  • Common sub-expression elimination
  • Dead code elimination
  • Renaming of temporary variables
  • Interchange of two adjacent independent statements.

Common sub-expression elimination:

Suppose we have two expressions that compute the same values. In that case, we need to eliminate one of the expressions. This method is known as the common sub-expression elimination method.

Example:

 p = a + b
 q = c – d
 r = x+ y
 s = c - d 

This example shows that the second and fourth statements compute the same expression: c - d. So the basic block can be transformed as follows:

 p = a + b
 q = c - d
 r = x + y
 s = q 

Dead code elimination:

Whenever a programmer writes a program, there is a possibility that the program may have some dead code. These dead codes are the result of some expression in the program. Generally, a programmer doesn't introduce dead code intentionally. The dead code may be a variable or the result of some expression computed by the programmer that may not have any further uses. By eliminating these useless things from a code, the code will get optimized.

Example:

A statement p = q + r appears in a block, and p is a dead symbol. It means that it will never be used subsequently so that we can eliminate this statement. This elimination does not have any impact on the values of the basic block.

Renaming of temporary variables:

Consider the statement x = a + b

The given statement's value is stored in the temporary variable x that can be changed to another temporary variable y and changes all uses of x to y.

This kind of transformation is also known as a normal-form block.

Interchange of two independent adjacent statements:

Suppose we have two statements as follows:

                          p = a + b
                          q = x + y                 

The given statement can be interchanged without affecting the value of the block when the value of p does not affect the value of q.

Algebraic Transformations:

We can also optimized the basic blocks using algebraic identities. For example, we may apply arithmetic identities, such as

 x + 0 = 0 + x = x                  x , 0= x
  x * 1=1 * x = x                    x= 1 = x                     

Local reduction in strength is also another kind of algebraic transformation. In this optimization, a more expensive operator is replaced by a cheaper one.

EXPENSIVE                  CHEAPER

x^2                                        x * x

2 * x                                       x + x  

x/2                                           x * 0.5

The third class of optimizations is constant folding. In constant folding, the value of the constant expression is evaluated at compile-time, and their values replace constant expression. So, the expression 3 * 3 will be replaced by 9.

Sometimes unexpected common subexpression arose due to some relational operators like <, >, and =.           

The relational operators such as < and = sometimes generate unexpected common subexpressions.

Sometimes associative rule may be applied to expose common sub expression. If the source code has the assignments:

a = b + c;

e = c + d+ b;

Then, the intermediate code may be generated as the following:

a = b + c

t = c + d

e = t + b


Related Topics

Storage Allocation

Storage Allocation The storage allocation represents memory management. The allocation of memory can be done in the following ways: Static AllocationStack AllocationHeap Management Static Allocation: It is a procedure used for the allocation of...

1 minute read.

Run-Time Storage Management

Run-Time Storage Management Every executing program has its own logical address space. Logical address space is partitioned into: Code: It is responsible for storing the executable target code. Static: It is used to...

3 minutes read.

CLR Parsing Compiler Design

CLR Parsing CLR parsing refers to the canonical lookahead. We will use the canonical collection of LR(1) items for the construction of the CLR(1) parsing table. Generally, CLR(1) parsing has more...

6 minutes read.

Data Flow Analysis in Compiler Design

Data Flow Analysis All the optimization techniques we have learned earlier depend on data flow analysis. DFA is a technique used to know about how the data is flowing in any...

3 minutes read.

Symbol Table Compiler Design

Symbol Table It is an important data structure used by the compiler. It stores information about various entities such as object, class, variable names, functions name, interfaces, procedure, literals, string etc.  The...

3 minutes read.

YACC in Compiler Design

YACC  YACC is known as Yet Another Compiler Compiler. It is used to produce the source code of the syntactic analyzer of the language produced by LALR (1) grammar. The input...

5 minutes read.

LR Parser in Compiler Design

LR Parser The most popular type of bottom-up parsing is LR(K) parsing. The LR() parser scans the input from left – to – right, which is the actual abbreviation of L...

2 minutes read.

Lexical Analysis in Compiler Design

Lexical Analysis It is the first phase of the compiler. As we know, it is also known as a scanner. The input for lexical analysis is source code. After taking source...

2 minutes read.

Optimization of Basic Blocks in Compiler Design

Optimization of Basic Blocks We can apply the optimization process on a basic block. While optimization, there is no need to change the set of expressions computed by the block. The basic...

3 minutes read.

Boolean Expression in Compiler Design

Boolean Expression The translation of conditional statements such as if-else statements and while-do statements is associated with Boolean expression's translation. The main use of the Boolean expression is the following: Boolean expressions...

3 minutes read.

Machine-Independent Optimizations in Compiler Design

Machine-Independent Optimizations The main aim of machine-independent optimization is to improve the generated intermediate code so that compiler can get better target code. Eliminating unwanted code from the object code or replacing...

8 minutes read.

Target Machine

Target Machine A target machine is a byte-addressable machine. This machine has n general-purpose registers, R0, R1,.....Rn-1. A Simple Target Machine Model has three-address instruction. A full-edged assembly language would have...

3 minutes read.

Translation of Array References in Compiler Design

Translation of Array References We can access the elements of an array stored in consecutive blocks very easily and quickly. In a programming language like C and Java, the size of...

2 minutes read.

Syntax Analysis Compiler Design

Syntax Analysis This article will describe the parsing method used in the compiler. The grammatical rule of programming language can be constructed with the help of context-free grammars or BNF (Backus–Naur...

3 minutes read.

SLR 1 Parsing Compiler Design

SLR(1) Parsing It is a simple LR parsing. Most of the function of this parsing is the same as LR(0) parsing. The parsing table for both the parser vary. The SLR(1)...

5 minutes read.

Phases of Compiler

Phases of Compiler The compilation process of a compiler goes through various phases. Each phase of the compiler takes the output from the previous as an input. Here we will see all...

2 minutes read.

LR Parser Compiler Design

LR Parser LR parsing is a type of bottom-up parsing that is used to parse the large class of grammars. Here "L" stands for left-to-right scanning of the input "R" stands...

6 minutes read.

Evolution of Programming Languages in Compiler Design

The Evolution of Programming Languages The first computer came in the 1940s and was programmed in a binary language that told the computer what operations are to be performed and in...

4 minutes read.

Finite State Machine

Finite State Machine A finite state machine is a simple machine to recognize patterns. It takes a string of symbols as the input and changes its state to another state, but...

3 minutes read.

Code Generation

Code Generation The last phase of the compiler is code generation. It is the compiler's back-end that makes multiple passes over the IR before generating the target program. The code generator's...

4 minutes read.