Write short notes on: 

• Peephole Optimization

• Symbol Table

• Cross Compiler

Peephole optimization: In compiler optimization theory, the compiler optimization basically refers to the program optimization to achieve performance in the execution. Program optimization refers to the three aspects (i) frontend: a programming language code, (ii) intermediate code: an assembly language code generated by the compiler appropriate to the programming language and (iii) backend: the specific machine or object code generated from the assembly language code for the actual execution by the compiler.

The Peephole Optimization is a kind of optimization technique performed over a very small set of instructions in a segment of generated assembly code [Intermediate code]. The set of instructions is called a "peephole" or a "window". It works by recognizing sets of instructions that can be replaced by shorter or faster set of instructions to achieve speed or performance in the execution of the instruction sequences. Basically Peephole Optimization is a method which consists of a local investigation of the generated object code means intermediate assembly code to identify and replace inefficient sequence of instructions to achieve optimality in targeted machine code in context of execution or response time, performance of the algorithm and memory or other resources usage by the program.

Common Techniques Applied in Peephole Optimization Common techniques applied in peephole optimization.

• Constant folding - Assess constant sub expressions in advance.

                   E.g. r2 := 3 X 2              becomes               r2 := 6

• Strength reduction - Faster Operations will be replaced with slower one.

                   E.g. r1:= r2 X 2                            becomes r1 := r2 + r2                    then r1 := r2<>1

                          r1 := r2/2                             becomes r1 := r2>>1

• Null sequences – Operations that are ineffective will be removed.

                  E.g. r1 := r1 + 0     or      r1 := r1 X 1      has no effect

• Combine Operations - Replacement of the few operations with similar effective single operation.

                  E.g. r2 := r1 X 2               r3 := r2 X 1       becomes r3 := r1 + r1

• Algebraic Laws - Simplification and reordering of the instructions using algebraic laws.

                  E.g. r1 := r2 r3 := r1nbsp;           becomes          r3 := r2;

• Special Case Instructions - Use instructions designed for special operand cases. 

                  E.g. r1 := r1 + 1                    becomes         inc r1

• Address Mode Operations - Simplification of the code using address modes.

                  E.g. r2 := var                         becomes          r2 := 0x500

Symbol Table: Symbol table is an important data structure created and maintained by compilers in order to store information about the occurrence of various entities such as variable names, function names, objects, classes, interfaces, etc. Symbol table is used by both the analysis and the synthesis parts of a compiler.

A symbol table may serve the following purposes depending upon the language in hand:

• To store the names of all entities in a structured form at one place.
• To verify if a variable has been declared.
• To implement type checking, by verifying assignments and expressions in the source code are semantically correct.

A symbol table is simply a table which can be either linear or a hash table. It maintains an entry for each name in the following format:

                                      <symbol name,  type,  attribute>

For example, if a symbol table has to store information about the following variable declaration:

                                      static int interest;

then it should store the entry such as:

                                      <interest, int, static>

The attribute clause contains the entries related to the name.

Implementation

If a compiler is to handle a small amount of data, then the symbol table can be implemented as an unordered list, which is easy to code, but it is only suitable for small tables only. A symbol table can be implemented in one of the following ways:

• Linear (sorted or unsorted) list
• Binary Search Tree
• Hash table

Among all, symbol tables are mostly implemented as hash tables, where the source code symbol itself is treated as a key for the hash function and the return value is the information about the symbol.

Operations

The basic operations defined on a symbol table include:

• allocate – to allocate a new empty symbol table
• free – to remove all entries and free the storage of a symbol table
• insert – to insert a name in a symbol table and return a pointer to its entry
• lookup – to search for a name and return a pointer to its entry
• set_attribute – to associate an attribute with a given entry
• get_attribute – to get an attribute associated with a given entry 
• delete- operation removes a name previously inserted

Scope Management

A compiler maintains two types of symbol tables: a global symbol table which can be accessed by all the procedures and scope symbol tables that are created for each scope in the program.

To determine the scope of a name, symbol tables are arranged in hierarchical structure as shown in the example below:

. . .

int value=10;

void pro_one()

   {

   int one_1;

   int one_2;

      {              \

      int one_3;      |_  inner scope 1

      int one_4;      |

      }              /

   int one_5;

      {              \  

      int one_6;      |_  inner scope 2

      int one_7;      |

      }              /

   }

void pro_two()

   {

   int two_1;

<p   int two_2;

      {              \

      int two_3;      |_  inner scope 3

      int two_4;      |

      }              /

   int two_5;

   }

. . .

The above program can be represented in a hierarchical structure of symbol tables:

The global symbol table contains names for one global variable (int value) and two procedure names, which should be available to all the child nodes shown above. The names mentioned in the pro_one symbol table (and all its child tables) are not available for pro_two symbols and its child tables.

This symbol table data structure hierarchy is stored in the semantic analyzer and whenever a name needs to be searched in a symbol table, it is searched using the following algorithm:

• first a symbol will be searched in the current scope, i.e. current symbol table.
• if a name is found, then search is completed, else it will be searched in the parent symbol table until,
• either the name is found or global symbol table has been searched for the name.

Cross Compiler: cross compiler  compiler capable of creating executable code for a platform other than the one on which the compiler is running. For example, a compiler that runs on a Windows 7 PC but generates code that runs on Android smart phone is a cross compiler.

A cross compiler is necessary to compile for multiple platforms from one machine. A platform could be infeasible for a compiler to run on, such as for the microcontroller of an embedded system because those systems contain no operating system. In para-virtualization one machine runs many operating systems, and a cross compiler could generate an executable for each of them from one main source.

The fundamental use of a cross compiler is to separate the build environment from the target environment. This is useful in a number of situations:

• Embedded computers where a device has extremely limited resources.
• Compiling for multiple machines- a company supporting several different versions of OS, a single build environment can be set up to compile for each of these targets.
• Compiling on a server farm.
• Compiling native code for emulators.