1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950 |
- .NH 2
- Control Flow
- .PP
- A \fIsuccessor\fR of a basic block B is a block C
- that can be executed immediately after B.
- C is said to be a \fIpredecessor\fR of B.
- A block ending with a RET instruction
- has no successors.
- Such a block is called a \fIreturn block\fR.
- Any block that has no predecessors cannot be
- executed at all (i.e. it is unreachable),
- unless it is the first block of a procedure,
- called the \fIprocedure entry block\fR.
- .PP
- Internally, the successor and predecessor
- attributes of a basic block are stored as \fIsets\fR.
- Alternatively, one may regard all these
- sets of all basic blocks as a conceptual \fIgraph\fR,
- in which there is an edge from B to C if C
- is in the successor set of B.
- We call this conceptual graph
- the \fIControl Flow Graph\fR.
- .PP
- The only successor of a basic block ending on an
- unconditional branch instruction is the block that
- contains the label definition of the target of the jump.
- The target instruction can be found via the LAB_ID
- that is the operand of the jump instruction,
- by using the label-map table mentioned
- above.
- If the last instruction of a block is a
- conditional jump,
- the successors are the target block and the textually
- next block.
- The last instruction can also be a case jump
- instruction (CSA or CSB).
- We then analyze the case descriptor,
- to find all possible target instructions
- and their associated blocks.
- We require the case descriptor to be allocated in
- a ROM, so it cannot be changed dynamically.
- A case jump via an alterable descriptor could in principle
- go to any label in the program.
- In the presence of such an uncontrolled jump,
- hardly any optimization can be done.
- We do not expect any front end to generate such a descriptor,
- however, because of the controlled nature
- of case statements in high level languages.
- If the basic block does not end in a jump instruction,
- its only successor is the textually next block.
|