From: Siddharth Saluja <email@example.com>
Date: Thu, Jan 30, 2014 at 2:19 AM
Subject: Optimizing Compilers
Effective optimizing compilers need to gather information about the structure and the ﬂow 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 :
• Operate at a level close to that of source-code
• Often language-dependent
Intermediate code optimizations
• Most optimizations fall here
• Typically, language-independent
• Usually specific to each architecture
High Level Optimizations :
•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
• Loop-invariant code motion
• Dead-code elimination
• Strength reduction
• 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