Java Reference
In-Depth Information
16. In performing on-the-fly register allocation, some implementations store
freed registers on a stack. Thus, themost recently freed registerwill be the
next register to be allocated. On the other hand, other implementations
place freed registers at the back of a queue. Thus, the least-recently freed
register will be the next to be allocated. (This is often called
round robin
allocation
.)
From the point of viewof a postpass code scheduler, which of the register
reallocation implementations (stack vs. queue) is preferable? Why?
17. The
DAG code scheduler of Section 13.4 assumes that instruc-
tions that can stall have unit delay. That is, one instruction must separate
an instruction that can stall from the first use of the value it produces.
It may happen that some instructions have
n
cycle delays, meaning
n
instructions must separate the instruction from the first use of the value
it produces.
schedule
How must
schedule
DAG be modified to handle instructions that have
n
cycle delays?
18. The
DAG code scheduler is a
postpass code scheduler
.That
is, it schedules instructions after registers have been allocated. It is pos-
sible to create a dependency DAG in terms of instructions that reference
pseudo-registers. After instructions are scheduled, the pseudo-registers
are mapped to real registers. Such a scheduler is a
prepass scheduler
,
since it operates before register allocation.
It is important to note that the order in which instructions are scheduled
will a
schedule
ect the number of registers that are needed later. For example,
scheduling all loads immediately will force each load to use a di
ff
er-
ent register. Scheduling some loads after other operations may allow
registers to be reused.
ff
If
DAG is used as a prepass code scheduler, how should it be
modified so that the number of pseudo-registers in use is a criterion in
selecting the next instruction to schedule? That is, scheduling an instruc-
tion that increases the number of registers that will be needed should be
discouraged unless it serves to avoid stalls in the code schedule.
schedule
