[Skip to Body]
Primary:
[Front Door]
[Current]
[Glance]
-
[Honesty]
[Instructions]
[Links]
[Search]
Groupings:
[EBoards]
[Examples]
[Exams]
[Handouts]
[Homework]
[Labs]
[Outlines]
[Project]
[Readings]
[Reference]
Misc:
[2001S]
[2002F]
[SamR]
Back to Register Allocation.
Held: Thursday, 6 May 2004
Summary: Today we look at some of the issues involved in the improvement of program code, focusing primarily on intermediate code.
Related Pages:
Notes:
Overview:
nearly as good as that hand coded by a talented programmer.
on the fly,as it generates code from portions of the annotated parse tree (or as it parses the program), it is often easier to improve the code in a separate pass.
Optimizeimplies
optimalas in
you can't be any better than this.
optimizationsare guaranteed to produce unimprovable code because it may always be possible to choose a better algorithm (especially if you know more about the input data)
Peepholeimprovement (look at a few lines at a time)
for i := 1 to N do for j := 1 to N do B[i,j] := A[i,j]; for j := 1 to N do for i := 1 to N do B[i,j] := A[i,j]
basic blocksand edges between those basic blocks.
piece of code(e.g., statement, series of statements, block, and group of blocks), we might consider the variables that provide values that are used in the code (uses) and those variables that have values set by the code (defines).
ADD b c a
, the instruction uses b and c and
defines a).
add
(as I like to do), there are many
ways to translate that to a two-parameter add,
depending on what you already have in registers.
ADD b c -> a
b
in a register, add to that
register, and move into a
.
b
and c
into registers,
do register addition, and move the result into a
.
ADD y z -> x ... ADD y z -> a
mov x a
.
ADD a b -> c GOTO WHATEVER ADD a b -> d GOTO WHATEVER WHATEVER: ADD a b -> e
ADD
by a
MOVE
, we need to add another variable
and some extra work.
ADD a b -> t MOVE t -> c GOTO WHATEVER ADD a b -> t MOVE t -> d GOTO WHATEVER WHATEVER: MOVE t -> e
mov x y
, we can use x
in
place of y
in subsequent statements (until
x
or y
is updated).
ADD $1 t -> t MUL t $4 -> u
ADD $1 t -> t ADD $4 u -> u
Back to Register Allocation.
[Skip to Body]
Primary:
[Front Door]
[Current]
[Glance]
-
[Honesty]
[Instructions]
[Links]
[Search]
Groupings:
[EBoards]
[Examples]
[Exams]
[Handouts]
[Homework]
[Labs]
[Outlines]
[Project]
[Readings]
[Reference]
Misc:
[2001S]
[2002F]
[SamR]
Disclaimer:
I usually create these pages on the fly
, which means that I rarely
proofread them and they may contain bad grammar and incorrect details.
It also means that I tend to update them regularly (see the history for
more details). Feel free to contact me with any suggestions for changes.
This document was generated by
Siteweaver on Thu May 6 08:49:51 2004.
The source to the document was last modified on Tue Jan 20 23:07:04 2004.
This document may be found at http://www.cs.grinnell.edu/~rebelsky/Courses/CS362/2004S/Outlines/outline.41.html
.
You may wish to
validate this document's HTML
;
;
Check with Bobby