Hardware Reference
In-Depth Information
statements) so that its translation into machine language does not contain any
branches. The basic blocks are connected by control statements.
A program in this form can be represented as a directed graph, as shown in
Fig. 4-45. Here we compute the sum of the cubes of the even and odd integers up
to some limit and accumulate them in
evensum
and
oddsum
, respectively. Within
each basic block, the reordering techniques of the previous section work fine.
evensum = 0;
oddsum = 0;
i=0;
evensum = 0;
oddsum = 0;
i=0;
i
>=
limit
while (i
<
limit) {
while (i
<
limit)
k=i
*
i
*
i;
k=i
*
i
*
i;
if (((i/2)
*
2) == i)
evensum = evensum + k;
if ((i/2)
*
2)==i)
T
F
evensum = evensum + k;
oddsum = oddsum + k;
else
oddsum = oddsum + k;
i=i+1;
i=i+1;
}
(a)
(b)
Figure 4-45.
(a) A program fragment. (b) The corresponding basic block graph.
The trouble is that most basic blocks are short and there is insufficient paral-
lelism in them to exploit effectively. Consequently, the next step is to allow the
reordering to cross basic block boundaries in an attempt to fill all the issue slots.
The biggest gains come when a potentially slow operation can be moved upward in
the graph to start it early. This might be a
LOAD
instruction, a floating-point opera-
tion, or even the start of a long dependence chain. Moving code upward over a
branch is called
hoisting
.
Imagine that in Fig. 4-45 all the variables were kept in registers except
even-
sum
and
oddsum
(for lack of registers). It might make sense then to move their
LOAD
instructions to the top of the loop, before computing
k
, to get them started
early on, so the values will be available when needed. Of course, only one of them
will be needed on each iteration, so the other
LOAD
will be wasted, but if the cache
and memory are pipelined and there are issue slots available, it might still be worth
doing this. Executing code before it is known if it is even going to be needed is
called
speculative execution
. Using this technique requires support from the com-
piler and the hardware as well as some architectural extensions. Normally, reorder-
ing instructions over basic block boundaries is beyond the capability of hardware,
so the compiler must move the instructions explicitly.
