Java Reference
In-Depth Information
between a load and the instruction that uses the loaded value, instruction
execution proceeds without delay. Thus the following instructions would be
delay-free:
lw
$12, b
# Load b into register 12
li
$11, 100
# Load 100 into register 11
add $10, $11, $12
# Add reg 11 and reg 12 into reg 10
The role of instruction scheduling is toorder instructions so that stalls (and their
delays) are minimized. The nature of processor stalls is generally architecture-
and implementation-specific. For example, the MIPS stall described above
might be avoided by superscalar processors that attempt out-of-order instruc-
tion execution.
Code scheduling is normally done at the basic block level. A
basic block
is a linear sequence of instructions thatcontainsnobranchesexceptatitsvery
end. Instructions within a basic block are always executed sequentially as a
unit. During code scheduling, all the instructions within a basic block are
analyzed to determine an execution order that produces correct computations
with a minimum of interlocks or delays. We will consider a simple but e
ff
ective
postpass code scheduler
devised by Gibbons and Muchnick [GM86].
Postpass code schedulers operate
after
code has been generated and reg-
isters have been chosen. They are very flexible and general because they
can handle code generated by any compiler (or even hand-coded assembly
language programs). However, because instructions and registers have al-
ready been selected, they cannot modify choices already made, even to avoid
interlocks.
A code scheduler tries tomove apart instructions that will interlock. How-
ever, instructions cannot be reordered haphazardly. Loads of a register must
precede use of that register, and stores of a register must follow instructions
that compute the register's value. We use a
dependencyDAG
to represent de-
pendencies between instructions. Nodes of the
directed acyclic graph
(DAG)
are instructions that are to be scheduled. An arc exists from instruction
i
to
instruction
j
if instruction
i
must be executed before instruction
j
.Thus,arcs
are added between instructions that load or compute a register and instruc-
tions that use or store that register. Similarly, an arc is added between a load
from memory location
A
and a subsequent store into location
A
. Also, an arc
is added between a store into location
B
and any subsequent load or store
involving location
B
.Inthecaseof
aliasing
, where we cannot be certain at
compile-time as to the location that is referenced by a load or store instruction,
we make worst-case assumptions. Thus, a load through a pointer
p
must pre-
cede a store into any location
p
might alias, and a store through
p
must precede
any load or store involving a location
p
might alias.
As an example, assume we generate the MIPS code shown in Figure 13.21
