,)
D)
In-line
expansion
Leaf-routine
optimization
Shrink
wrapping
Machine idioms
Tail
merging
Branch
optimizations
and conditional
moves
Dead-code
elimination
Software
pipelining,
with
loop
unrolling,
variable
expansion, register
renaming,
and hierarchical reduction
Basic-blockand
branch
scheduling
1
Register
allocation
by graph coloring
Basic-block and branch
scheduling
2
Intraprocedural
I-cache
optimization
Instruction
prefetching
Data
prefetching
Branch
prediction)
,)
Interprocedural register
allocation
E
Aggregation
of
global
references
Interprocedural
I-cache
optimization)
(to
constant
folding,
algebraic
simplifications,
and
reassociation)
A)
I
I
I
I
I
I
I
I
I
I
I
I
I
I
I
I
I
- - - - - - - - - - - - - - - - I)
B,
C These
optimizations
are
typically performed
on medium-
or
low-level intermediate
code,
depending
on the
overall
organization
of
the
compiler.
If
code
selectionis done before all
optimizations
other than those
in
box
A
(known
as the \"low-level\" model of
optimizer
struc-
ture),
then these
optimizations
are
performed
on low-levelcode.
If,
on the other
hand,
some
optimizations
are
performed
on a
medium-level,
relatively
machine-independent
intermedi-
ate
code
and others are
performed
on low-level code after code
generation
(known
as
the
\"mixed\"
model),
then
these
optimizations
are
generally
done on
the medium-level interme-
diate code.
The
branches from Cl to
C2
and C3
represent
a
choiceof
the
method
used
to
perform
essentially
the same
optimization (namely, moving computations
to
places
where
they
are
per-
formed less
frequently
without
changing
the
semantics of
the
program).
They
also
represent
a choiceof
the
data-flow
analyses
used to
perform
the
optimization.
D
These
optimizations
are almost
always
done on
a low-level form
of code-one that
may
be
quite machine-dependent (e.g.,
a structured
assemblylanguage)
or that
may
be
somewhat
more
general,
such
as
the
low-level intermediate code
used
in
this
book-because
they
require
that
addresses
have
been turned
into
the
form
required by
the
target processor
and because
severalof them
require
low-level
control-flow code.
E
These
optimizations
are
performed
at
link
time,
so
they operate
on relocatable
object
code.
Three
optimizations, namely,
constant
folding, algebraic simplification,
and
reassociation,
are
in
boxes connected to the other
phases
of the
optimization process by
dotted
lines
because
they
are
best structured
as
subroutines
that can
beinvoked whenever
they
are needed.
A
version
of
this
diagram appears
in
Chapters
1
and
11
through
20 to
guide
the
reader
in
ordering optimizer components
in
a
compiler.)))
