Basic Blocks
De nition
sequence of code
control enters at top, exits at bottom
no branch/halt except at end
Construction algorithm (for 3-address code)
1. determine set of leaders
(a) rst statement
(b) target of goto or conditional goto
(c) statement following goto or conditional goto
2. add to basic block all statements following
leader up to next leader or end of program
Example:
A := 0;
if (<cond>) goto L;
A := 1;
B := 1;
L: C := A;
CPSC 434 Lecture 23, Page 1
Local vs. Global Optimization
Scope
local | within basic block
global | across basic blocks
refers to both analyses and optimizations
Some optimizations may be applied locally or
globally (e.g., dead code elimination):
A := 0; A := 0;
A := 1; if (<cond>) goto L;
B := A; A := 1;
B := A;
Some optimizations require global analysis
(e.g., loop-invariant code motion):
while (<cond>) do
A := B + C;
foo(A);
end;
CPSC 434 Lecture 23, Page 2
Local optimization
Value numbering
another basic-block level optimization
combines common subexpression elimination &
constant folding
avoids the graph manipulation involved in dag
construction
References
John Cocke and Jack Schwartz in
\Programming Languages and Their Compilers;
Preliminary Notes" (1970)
\A Survey of Data Flow Analysis Techniques"
by K.W. Kennedy (in Program Flow Analysis,
N.D. Jones and S.S. Muchnick, editors)
See also Aho, Sethi, and Ullman, pages 292,
293, and 635
CPSC 434 Lecture 23, Page 3
Value numbering
Assumptions
can nd basic blocks
input is in triples
no knowledge about world before or after the
block
reference's type is textually obvious
(tag lhs and rhs )
Input
basic block (n instructions )
symbol table (w/constant bit )
Output
improved basic block (cse, constant folding )
table of available expressions y
table of constant values
y
an expression is available at point p if it is de ned along each
path leading to p and none of its constituent values has been
subsequently rede ned.
CPSC 434 Lecture 23, Page 4
Value numbering
Key Notions
each variable, each expression, and each constant
is assigned a unique number, its value number
{ same number ) same value
{ based solely on information from within the
block
{ stored in di erent places
? variables and constants ! symbol table
(SYMBOLS)
? expressions ! available expression table
(AVAIL) & triple
if an expression's value is available (already
computed), we should not recompute it
) re-write subsequent references (subsumption )
constants denoted with a bit in SYMBOLS and in
the triple
CPSC 434 Lecture 23, Page 5
Value numbering
Principal data structures
CODE
array of triples
Fields: result, lhs, op, rhs
SYMBOLS
hash table keyed by variable name
Fields: name, val, isConstant
AVAIL
hash table keyed by (val, op, val )
Fields: lhsVal,op, rhsval, resultVal, isConstant,
instruction
CONSTANTS (a nit )
table to hold funky, machine-speci c values
important in cross-compilation
Fields: val, bits
CPSC 434 Lecture 23, Page 6
Value numbering
for i1 to n
r value number for [ ] rhs i
l value number for [ ] lhs i
if [ ] is a store then
op i
SYMBOLS[ [ ]].val lhs i r
if is constant then
r
SYMBOLS[ [ ]].isConstant true
lhs i
else /* an expression */
if is constant then replace
l [ ] with constant lhs i
if is constant then replace
r [ ] with constant rhs i
if is \ref " then replace
l k[ ] with lhs i k
if is \ref " then replace
r k [ ] with rhs i k
if and are both constant then
l r
create CONSTANTS( [ ] ) l; op i ; r
CONSTANTS( [ ] ).bits eval ( [ ] )
l; op i ; r l op i r
CONSTANTS( [ ] ).val new value number
l; op i ; r
[ ] \constant ( [ ] )"
op i l op i r
else
if ( [ ] ) 2 AVAIL then
l; op i ; r
op i [ ] \ref AVAIL( [ ] ).resultVal"
l; op i ; r
else
create AVAIL( [ ] ) l; op i ; r
AVAIL( [ ] ).val new value number
l; op i ; r
for i 1 to n
if [ ] is ref or constant then delete instruction
op i i
CPSC 434 Lecture 23, Page 7
Example
Triples Source
T1: a C4 a 4
T2: i j
T3: T2 + C5
T4: k T3 k i j + 5
T5: C5 a
T6: T5 k
T7: l T6 l 5 a k
T8: m i m i
T9: m j
T10: i a
T11: T9 + T10
T12: b T11 b m j + i a
T13: a T12 a b
CPSC 434 Lecture 23, Page 8
Value numbering
Safety
constant folding | applied only to constant
arguments
common subexpressions | construction ensures
it
Pro tability
assume that load of constant is cheaper than op
assume that reference (or copy) is cheaper than
op
forwarding mechanism (ref) does subsumption
Opportunity
look at each instruction
linear time, but assumes basic blocks are small
CPSC 434 Lecture 23, Page 9
Value numbering
What does value numbering accomplish?
assign a value number to each available
expression
{ identity based on value, not name
{ DAG construction has same property
elminate duplicate evaluations
evaluate and fold constant expressions
Can we extend this idea across blocks?
CPSC 434 Lecture 23, Page 10
Value numbering across blocks
What would we need to value number across multiple
blocks?
1. a control
ow ordering on the blocks
2. AVAIL information for logical predecessors
3. uniform naming scheme for values (con
uence )
4. formal de nition of availability
Terminology
this kind of analysis is called data-
ow analysis
it requires a control
ow graph
{ nodes represent basic blocks
{ edges represent possible control
ow paths
{ an algorithm to construct the control
ow
graph
CPSC 434 Lecture 23, Page 11
