|
UNIT-V |
||||||||||||||||||||||||
|
TOPIC: Code Optimization |
||||||||||||||||||||||||
|
Unit-05/Lecture-1 |
||||||||||||||||||||||||
|
Code Optimization:[RGPV, Dec 2013] Optimization is the process of transforming
a piece of code to make more efficient (either in terms of time or space)
without changing its output or side-effects. The only difference visible to
the code’s user should be that it runs faster and/or consumes less memory. It
is really a misnomer that the name implies you are finding an
"optimal" solution— in truth, optimization aims to improve, not
perfect, the result. Optimization is the field where most compiler research
is done today. The tasks of the front-end (scanning, parsing, semantic
analysis) are well understood and un-optimized code generation is relatively
straightforward. Optimization, on the other hand, still retains a sizable
measure of mysticism. High-quality optimization is more of an art than a
science. Compilers for mature languages aren’t judged by how well they parse
or analyze the code—you just expect it to do it right with a minimum of
hassle-but instead by the quality of the object code they produce. Many
optimization problems are NP-complete and thus most optimization algorithms
rely on heuristics and approximations. It may be possible to come up with a
case where a particular algorithm fails to produce better code or perhaps
even makes it worse. However, the algorithms tend to do rather well overall. When and Where To Optimize: There are a variety of tactics for attacking
optimization. Some techniques are applied to the intermediate code, to
streamline, rearrange, compress, etc. in an effort to reduce the size of the
abstract syntax tree or shrink the number of TAC instructions. Others are
applied as part of final code generation—choosing which instructions to emit,
how to allocate registers and when/what to spill, and the like. And still
other optimizations may occur after final code generation, attempting to
re-work the assembly code itself into something more efficient. Optimization
can be very complex and time-consuming; it often involves multiple
sub-phases, some of which are applied more than once. Most compilers allow
optimization to be turned off to speed up compilation. IMP Points: ·
Intermediate Code undergoes
various transformations—called Optimizations—to make the resulting
code running faster and taking less space. • Optimization never guarantees
that the resulting code is the best possible. • We will consider only Machine-Independent
Optimizations—i.e., they don’t take into consideration any property of
the target machine. • The techniques used are a
combination of Control-Flow and Data-Flow analysis. – Control-Flow Analysis. Identifies loops in the flow graph of a program
since such loops are usually good candidates for improvement. – Data-Flow Analysis. Collects information about the way variables are
used in a program. Criteria for Code-Improving Transformations:[RGPV, Dec 2013] The best transformations are those that
yield the most benefit for the least effort. 1. A transformation must preserve the meaning of a program. It’s better to
miss an opportunity to apply a transformation rather than risk changing what
the program does. 2. A transformation must, on the average, speed up a program by a
measurable amount. 3. Avoid code-optimization for programs that
run occasionally or during debugging. 4. Remember! Dramatic improvements are
usually obtained by improving the source code: The programmer is always
responsible in finding the best possible data structures and algorithms for
solving a problem. Example: We will use the sorting program Quicksort
to illustrate the effects of the various optimization techniques. void quicksort(m,n) int m,n; { int i,j,v,x; if (n <= m) return; i = m-1; j = n; v = a[n]; /* fragment
begins here */ while (1) { do i = i+1; while (a[i]<v); do j = j-1; while (a[j]>v); if (i>=j) break; x = a[i]; a[i] = a[j]; a[j] =x; } x = a[i]; a[i] = a[n]; a[n] =x; /* fragment
ends here */ quicksort(m,j); quicksort(i+1,n); } The following is the three-address code for
a fragment of Quicksort.
Reference:
{Compilers: Principles, Techniques and Tools. Page No: 585-590}
|
||||||||||||||||||||||||
|
Unit-5/Lecture-2 |
||||||||||||||||||||||||
|
Basic Blocks and Flow Graphs:[RGPV, Dec 2012] · The Machine-Independent Code-Optimization phase consists of control-flow
and data-flow analysis followed by the application of
transformations. • During control-flow analysis, a program is
represented as a Flow Graph where: – Nodes represent Basic Blocks: Sequence of
consecutive statements in which flow-of-control enters at the beginning and
leaves at the end without halt or branches; – Edges represent the flow of control. Ø Flow graph for the three-address code fragment for quicksort. Each Bi
is a basic block.
The Principal Sources of Optimization:[RGPV, Dec 2012] • We individuate now the basic
transformations as the result of data-flow analysis. • We distinguish local transformations—involving
only statements in a single basic block—from global transformations. • A basic block computes a set of
expressions: A number of transformations can be applied to a basic block
without changing the expressions computed by the block. 1. Common Sub-expressions elimination; 2. Copy Propagation; 3. Dead-Code elimination; 4. Constant Folding. 5. Loop Optimization 1.
Common Sub-expressions Elimination: • Frequently a program will include
calculations of the same value. • Definition. An occurrence of an
expression E is called a Common Sub-expression if E was previously
computed, and the values of variables in E have no changed since the previous
computation. • Common Sub-expression Elimination: Assignments
to temporary variables involving common sub-expressions can be eliminated. • Example. Assignments to both t7 and
t10 in block B5 have common sub-expressions and can be eliminated. B5 is
transformed as: t6 := 4 _ i x := a[t6] t8 := 4 _ j t9 := a[t8] a[t6] := t9 a[t8] := x gotoB2 Example: After local elimination, B5 still evaluates
4 _ i and 4 _ j which are global common sub-expressions. • 4 _ j is evaluated in B3 by t4. Then, the
statements t8 := 4 _ j; t9 := a[t8]; a[t8] := x can be replaced by t9 :=
a[t4]; a[t4] := x • Now, a[t4] is also a common
sub-expression, computed in B3 by t5. Then, the statements t9 := a[t4]; a[t6]
:= t9 can be replaced by a[t6] := t5. • Analogously, the value of x is the same as
the value assigned to t3 in block B3; while t6 can be eliminated and replaced
by t2. The following flow
graph shows the result of eliminating both local and global common
sub-expressions from basic blocks B5 and B6.
Reference:
{Compilers: Principles, Techniques and Tools. Page No: 528-533}
|
||||||||||||||||||||||||
|
Unit-5/Lecture-3 |
||||||||||||||||||||||||
|
DAGs for Determining Common Sub-expressions: [RGPV, Dec 2012] • To individuate common sub-expressions we
represent a basic block as a DAG showing how expressions are re-used in a
block. • A DAG for a Basic Block has the
following labels and nodes: 1. Leaves contain unique identifiers, either
variable names or constants. 2. Interior nodes contain an operator
symbol. 3. Nodes can optionally be associated to a
list of variables representing those variables having the value computed at
the node. Example: The following shows both a three-address
code of a basic block and its associated DAG. (1) t1 := 4 *i (2) t2 := a[t1] (3) t3 := 4 *i (4) t4 := b[t3] (5) t5 := t2 *t4 (6) t6 := prod + t5 (7) prod := t6 (8) t7 := i + 1 (9) i := t7 (10) if i <= 20 goto (1) Flow Graph with basic blocks is:
DAG Representation is:
2.
Copy Propagation Copy Propagation Rule: Given the copy statement, x := y,
use y for x whenever possible after the copy statement. • Copy Propagation applied to Block B5
yields: x := t3 a[t2] := t5 a[t4] := t3 gotoB2 • This transformation together with
Dead-Code Elimination (see next slide) will give us the opportunity to
eliminate the assignment x := t3 altogether. Reference:
{Compilers: Principles, Techniques and Tools. Page No: 592-594}
|
||||||||||||||||||||||||
|
Unit-5/Lecture-4 |
||||||||||||||||||||||||
|
3.
Dead-Code Elimination:[RGPV, Dec 2012] • Intuition: A variable is live at a point in a program
if its value can be used subsequently, otherwise it is dead. • Dead Code. A piece of code is dead if data computed is
never used elsewhere and can be eliminated. • Dead-Code may appear as the result of previous transformation.
Dead-Code works well together with Copy Propagation A variable is live at a point in a program if its value can be used
subsequently; otherwise, it is dead at that point. A related idea is dead or
useless code, statements that compute values that never get used. While the
programmer is unlikely to introduce any dead code intentionally, it may
appear as the result of previous transformations. For example, we discussed
the use of debug that is set to true or false at various points in the
program, and used in statements like If (debug) print. By a data-flow
analysis, it may be possible to deduce that each time the program reaches
this statement, the value of debug is false. Usually, it is because there is
one particular statement Debug :=false . That we can deduce to be the last
assignment to debug prior to the test no matter what sequence of branches the
program actually takes. If copy propagation replaces debug by false, then the
print statement is dead because it cannot be reached. We can eliminate both
the test and printing from the o9bject code. More generally, deducing at
compile time that the value of an expression is a constant and using the
constant instead is known as constant folding. One advantage of copy
propagation is that it often turns the copy statement into dead code. For
example, copy propagation followed by dead-code elimination removes the assignment
to x and transforms 1.1 into a [t2 ] := t5 a [t4] := t3 goto B2. Example. Considering the Block B5 after Copy Propagation we can see that x is
never reused all over the code. Thus, x is a dead variable and we can
eliminate the assignment x := t3 from
B5. 4.
Constant Folding: [RGPV Dec 2012] • Intuition: Based on deducing at compile-time that the value
of an expression (and in particular of a variable) is a constant. • Constant Folding is the transformation that substitutes an
expression with a constant. • Constant Folding is useful to discover Dead-Code. Example. Consider the conditional statement: if (x) goto L. If, by Constant Folding, we discover that x is always false we can
eliminate both the if-test and the jump to L. 5.
Loop Optimization: • The running time of a program can be improved if we decree the
amount of instructions in an inner loop. • Three techniques are useful: I. Code Motion II. Reduction in Strength III. Induction-Variable elimination I. Code Motion • If the computation of an expression is loop-invariant this
transformation places such computation before the loop. • Example. Consider the following while statement: while (i <= limit - 2) do The expression limit - 2 is loop invariant. Code motion transformation
will result in: t := limit -2; while (i <= t) do II.
Reduction in Strength • It is based on the replacement of a computation with a less
expensive one. Example. Consider the assignment t4 := 4 _ j in Block B3. j is decremented by 1
each time, then t4 := 4 _ j − 4. Thus, we may replace t4 := 4 _ j by t4 := t4 − 4. Problem: We need to initialize t4 to t4 := 4 _ j before entering the
Block B3. – Result. The substitution of a multiplication by a subtraction will speed up
the resulting code. Reference:
{Compilers: Principles, Techniques and Tools. Page No: 594-598}
|
||||||||||||||||||||||||
|
Unit-5/Lecture-5 |
||||||||||||||||||||||||
|
III.
Induction Variables • A variable x is an Induction Variable of a loop if every time
the variable x changes values; it is incremented or decremented by some
constant. • A common situation is the one in which an induction variable, say i,
indexes an array, and some other induction variable, say t, is the actual
offset to access the array: – Often we can get rid of i. – In general, when there are two or more Induction Variables it is
possible to get rid of all but one. Example: Induction Variables Elimination Consider the loop of Block B3. The variables j and t4 are Induction
Variables. The same applies for variables i and t2 in Block B2. • After Reduction in Strength is applied to both t2 and t4, the only
use of i and j is to determine the test in B4. • Since t2 := 4 _ i and t4 := 4 _ j, the test i > j is equivalent
to t2 > t4. • After this replacement in the test, both i (in Block B2) and j (in
Block B3) become dead-variables and can be eliminated. Flow Graph after
Reduction in Strength and Induction-Variables elimination:
Data-flow analysis:[RGPV,
Dec 2012] As the name indicates, data-flow analysis attempts to discover how
information flows through a program. Data flow analysis is used to collect
information about the flow of data values across basic blocks. • Dominator analysis collected global information regarding the
programs structure regarding the program s structure • For performing global code optimizations global information must be
collected regarding values of information must be collected regarding values
of program variables. – Local optimizations involve statements from same basic block – Global optimizations involve statements from different basic blocks
→ data flow analysis is performed to collect global information that
drives global optimizations The liveness
analysis consisted of four things: 1. Information about which instructions can follow others, i.e., the
successors of each instruction. 2. For each instruction gen and kill sets that describe how data-flow
information is created and destroyed by the instruction. 3. Equations that define in and out sets by describing how data-flow
information flows between instructions. 4. Initialization of the in and out sets for a fixed-point iteration
that solve the data-flow equations. We will use the same template for other data-flow analyses, but the
details might differ. For example: 1. Forwards analyses require information about the predecessors of an
instruction instead of its successors. 2. Where liveness analysis uses sets of variables, other analyses
might use sets of instructions or sets of variable/value pairs. 3. The equations for in and out sets might differ. For example, they
may use intersection instead of union to combine information from several
successors or predecessors of an instruction. 4. Where liveness analysis initialises all in and out sets to empty
sets (except for the outset of the last instruction in the function, which is
initialised to the set of variables live at the exit of the function), other
analyses might initialize the sets to, for example, the set of all
instructions in the function. If we want the minimal solution to the
equations, we initialize with empty sets, but if the Want the maximal solution to the equations, we initialize with the set
of all relevant values. Flow Graph •Basic block = a
maximal sequence of consecutive instructions s.t – flow of control only enters at the
beginning – flow of control can only leave at the end (no halting or
branching except perhaps at end of block) •Flow Graphs – Nodes: basic blocks – Edges •Bi →Bj, iff
Bj can follow Bi immediately in execution Reference:
{Compilers: Principles, Techniques and Tools. Page No: 586, 596-598, 608}
|
||||||||||||||||||||||||
|
Unit-5/Lecture-6 |
||||||||||||||||||||||||
|
Global data flow analysis: [RGPV, Dec 2012, June
2006] Global data flow analysis is a process to analyze
how global data is processed and how analysis of the global data is useful in
optimizations. Basically, the data flow analysis process collects the
information about the program as a whole and then it distributes this
information to each block of the flow graph. Data flow information is defined
in terms of some data flow equations and then solving those equations to get
the data flow information. Ud-chaining: A global data flow analysis of the flow graph is
performed in order to compute ud-chaining information. It answers the
following question: If a given identifier is used at point y, then at
what point the value of X used at y would be defined? Here, the use of X
means that X occurs as an operand, and definition of X means either an
assignment to X or the reading of a value for X. A point refers to a
position before and after any intermediate code statement. Within a graph, by
assuming that all edges in the graph are traversable, we can say that, a
definition of a variable X reaches a point y if there exists a path in flow
graph from X's definition to y and no other definitions of X appear on the
path. Data flow equations: A data flow
equation has the following form: Out[BB] = in[BB] - Kill[BB] U Gen[BB] where, BB = Basic block Gen[BB] = The set of all definitions generated in
basic block BB. Kill[BB] = The set of all definitions outside basic
block BB that define the same variable as are defined in basic block BB. in[BB] = U out[P] Where, P refers to the predecessor of BB. Reference:
{Compilers: Principles, Techniques and Tools. Page No: 608-615}
References:
|
