Optimizing Compilers

                          Optimizing Compilers

 

Effective optimizing compilers need to gather information about the structure and the flow of control through programs.

 

·        Which instructions are always executed before a given instruction.

·        Which instructions are always executed after a given instruction.

·        Where the loops in a program are 90% of any computation is normally spent in 10% of the code: the inner loops.

 

Features of Optimization Techniques:

·        The most complex component of modern compilers must always be

sound, with  semantics-preserving.

·        Need to pay attention to exception cases as well

·        Use a conservative approach: risk missing out optimization rather

than changing semantics.

·        Reduce runtime resource requirements (most of the time)‏

·        Usually, runtime, but there are memory optimizations as well

·        Runtime optimizations focus on frequently executed code

·        Cost-effective, i.e., benefits of optimization must be worth

the effort of its implementation.

 

Various Levels :

 

High-level optimizations

• Operate at a level close to that of source-code

• Often language-dependent

 

 

Intermediate code optimizations

• Most optimizations fall here

• Typically, language-independent

 

Low-level optimizations

• Usually specific to each architecture

 

High Level Optimizations :

• Inlining

•Replace function call with the function body

• Partial evaluation

•Statically evaluate those components of a program that can be evaluated

• Tail recursion elimination

• Loop reordering

• Array alignment, padding, layout

 

Intermediate Level Optimizations :

• Common subexpression elimination

• Constant propagation

• Jump-threading

• Loop-invariant code motion

• Dead-code elimination

• Strength reduction

 

Low-level Optimizations

• Register allocation

• Instruction Scheduling for pipelined machines.

• loop unrolling

• instruction reordering

• delay slot filling

• Utilizing features of specialized components, e.g., floating-point units.

• Branch Prediction

 

Constant propogation :

 

·        Identify expressions that can be evaluated at compile time, and replace them with their values.

 

Strength reduction :

·        Replace expensive operations with equivalent cheaper (more efficient) ones.

y = 2;

ð y = 2;

z = x^y; z = x*x;

 

·        The underlying architecture may determine which operations are cheaper and which ones are more expensive.

 

Loop-Invariant Code Motion :

•Move code whose effect is independent of the loop's iteration outside the loop.

 

Common Subexpression Elimination:

 

·        Expression previously computed

 

§  Values of all variables in expression have not changed.

§  Based on available expressions analysis

 

·        Dead Code Elimination :

 

§  Dead variable: a variable whose value is no longer used

§  Live variable: opposite of dead variable

§  Dead code: a statement that assigns to a dead variable