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 one set of code with another set of code, which makes the object code faster without changing the result of object code, is generally called code improvement or code optimization.

A high-level language can have run-time overhead. Writing a program in a high-level language can cause redundancy. Code optimization will allow us to remove these inefficiencies.

Optimized code will use less space and makes the program execution fast. The optimized code can be re-used.

Code optimization can be performed in the following ways:

Compile Time Evaluation

  1. a = 4*(19/0.5)*r

            Perform 4*(19/0.5)*r at compile time

      2) a = 5

           b = a/6

           Perform a/6 as 5/6 at compile time

Global Common Subexpressions

Any expression can be known as a common subexpression if the value of an expression is previously computed. And the value of the variable in expression has not changed since the previous computation.

Example

p = x * y

q = x

r = q * y + 9

After the optimization of code:

p = x * y

q = x

r = x * y + 9

Here, after variable propagation, x * y and q * y identified as common sub-expression.

Dead-Code Elimination

If any variable's value can be used anywhere in the program, then the variable will be called live at a point in a program; otherwise, it will be termed as dead code. A dead code is not added intentionally by the programmer in any program. It may be the result of the previous computation.

Example

Before the elimination of code:

p = x * y

q = x

r = q * y + 9

After the elimination of code:

p = x * y

r = q * y + 9

In this example, q = x is a dead code because there is no use of this code in the program.

Code Motion

Loops have a very important place for optimizations, mostly in the inner loops where programs tend to spend a lot of their time. A program's run time complexity may be improved by decreasing the amount of code in an inner loop, even if we increase the amount of code outside that loop.

Code motion reduces the number of code in a loop. This optimization computes a loop-invariant statement outside the loop.

Example

Evaluation of limit - 2 in the following while-statement:

while (i <= limit - 2)

This code will be further optimized as:

t = limit-2

while (i <= t)  

After the optimization, limit-2 is computed only one time before entering the loop.  Previously there would be n +1 calculations of limit-2 if we iterated the body of the loop n times.

Induction Variables and Reduction in Strength

Optimization of induction variables inside a loop is also an important optimization. Any variable of the form x = x + constant is induction variable.

Induction variables can be computed with a single increment per loop iteration.

Replacing an expensive operator with low strength is strength reduction.

Example

Before the reduction, code is:

i= 2;                                                                                                                          

while(i<10)                                                                                                               

{                                                                                                                                 

  y = i * 6                                                                                                                   

}                                                                                                                              

Code, after the reduction:

i=2                                                                                                                          

x = 6                                                                                                                        

{                                                                                                                             

  while(x<30)                                                                                                          

  y =x;                                                                                                                    

  x = x +4:                                                                                                               

}                                                                                                                             


Related Topics

Regular Expression | Compiler Design

Regular Expression A regular expression is a set of patterns that can match a character or string. It can also match alternative characters or strings. The grammar defined by the regular...

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

Syntax-Directed Translation

Syntax-Directed Translation A context-free-grammar with some additional rules is known as a syntax-directed definition. In SDT, attributes are associated with grammar symbols and rules are associated with productions. The attributes can...

3 minutes read.

Basic Blocks and Flow Graphs in Compiler Design

Basic Blocks and Flow Graphs In this section, we are going to learn how to work with basic block and flow graphs in compiler design. Basic Block The basic block is a set...

3 minutes read.

Shift Reduce Parsing in Compiler Design

Like the bottom-up parsing, the shift reduce parser also builds the parse tree from the leaves (bottom) to the root (up). The LR parser is a more versatile variation of...

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

Parsing in Compiler Design

Parsing is the term used to describe the process of converting data between different formats. The parser can carry out this operation. The parser is a part of the translator...

4 minutes read.

LALR 1 Parsing | Compiler Design

LALR (1) Parsing The LALR parsing refers to the "lookahead LR" that has many lesser steps than typical parsers based on LR(1) items. For constructing the LALR(1) parsing table, the canonical...

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

Ambiguity Elimination Compiler Design

Ambiguity Elimination Ambiguity elimination makes the sentence clear and readable. A sentence is grammatically ambiguous if it can produce more than one parse tree for a particular grammar. In this article,...

3 minutes 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.

Run-Time Environments

Run-Time Environments Storage Organization Every target program has its own logical address, and an executable program runs in it. The logical address space has the location for each program value. The...

2 minutes read.

LEX

LEX Lex is a tool/computer program that generates a Lexical analyzer. Lex is developed by Vern Paxson in C around 1987. Lex works together with the YACC parser generator. It allows...

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

Compiler Design Tutorial

Our compiler design tutorial will provide all the information about compiler from basic to advanced level. This compiler tutorial will help the student for their semester as well as for...

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

Bottom-Up Parsing in Compiler Design

Bottom-Up Parsing A bottom-up parsing constructs the parse tree for an input string beginning from the bottom (the leaves) and moves to work towards the top (the root). Bottom-up parsing is...

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.

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.

Intermediate-Code Generator Compiler Design

Intermediate-Code Generator The process of translating a source language into machine code for a given target machine is done by intermediate-code. It lies between the high-level language and the machine language....

2 minutes read.