Java Reference
In-Depth Information
procedure
form
B
asic
B
locks
()
leaders ←{
first instruction in stream
}
foreach instruction s in the stream do
23
targets ←{
distinct targets branched to from s }
24
if
| targets |>
1
then
foreach t targets do
leaders leaders ∪{ t }
foreach l leaders do
block ( l )
25
←{ l }
s
next instruction after l
while s leaders and s
do
block ( l )
Block ( l )
∪{ s }
s
Next instruction in stream
end
Figure 14.7: Partitioning of instructions into basic blocks. The
value
in pseudocode means undefined and is typically denoted as
null in most programming languages.
solutions within a basic block, and global data flow analysis solves a
problem over the flow graph. In terms of software development and
maintenance, two levels of analysis are at least twice as costly as one level.
A more general solution would allow arbitrary levels of analysis, but
typical programs do not require such sophistication. In practice, a single,
wisely chosen level of representation su
ces for most applications.
Basic blocks can be constructed on-the-fly as intermediate code is gener-
ated. Figure 14.7 contains a two-pass algorithm that partitions a flat (non-
structured) streamof instructions into basic blocks. Marker 23 considers each
instruction in the stream in turn, adding to leaders those instructions that be-
gin a new basic block. Note that nonbranching and conditionally branching
statements can implicitly branch to the next instruction in the stream. Also,
branching instructions may repeatedly target the same instruction. To avoid
spurious basic blocks, Marker 24 must find the number of distinct successors
of instruction s .Marker 25 performs a second pass, creating a basic block
from each leader and its ensuing instructions, up to the next statement that
begins a new basic block. If the instruction stream is too large to store con-
veniently, then the leaders set can be organized (e.g., sorted) so that random
access to instructions is unnecessary. Alternatively, the instruction stream can
be considered in fixed-sized segments, where the first statement in each seg-
ment is a leader. Although this approachmay introduce spurious basic blocks,
these a
ff
ect only the space e
ciency of the representation, not the accuracy or
overall time.
 
Search WWH ::




Custom Search