12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394 |
- .bp
- .NH
- The Control Flow Phase
- .PP
- In the previous chapter we described the intermediate
- code of the global optimizer.
- We also specified which part of this code
- was constructed by the IC phase of the optimizer.
- The Control Flow Phase (\fICF\fR) does
- the remainder of the job,
- i.e. it determines:
- .IP -
- the control flow graphs
- .IP -
- the loop tables
- .IP -
- the calling, change and use attributes of
- the procedure table entries
- .LP
- CF operates on one procedure at a time.
- For every procedure it first reads the EM instructions
- from the EM-text file and groups them into basic blocks.
- For every basic block, its successors and
- predecessors are determined,
- resulting in the control flow graph.
- Next, the immediate dominator of every basic block
- is computed.
- Using these dominators, any loop in the
- procedure is detected.
- Finally, interprocedural analysis is done,
- after which we will know the global effects of
- every procedure call on its environment.
- .sp
- CF uses the same internal data structures
- for the procedure table and object table as IC.
- .NH 2
- Partitioning into basic blocks
- .PP
- With regard to flow of control, we distinguish
- three kinds of EM instructions:
- jump instructions, instruction label definitions and
- normal instructions.
- Jump instructions are all conditional or unconditional
- branch instructions,
- the case instructions (CSA/CSB)
- and the RET (return) instruction.
- A procedure call (CAL) is not considered to be a jump.
- A defining occurrence of an instruction label
- is regarded as an EM instruction.
- .PP
- An instruction starts
- a new basic block, in any of the following cases:
- .IP 1.
- It is the first instruction of a procedure
- .IP 2.
- It is the first of a list of instruction label
- defining occurrences
- .IP 3.
- It follows a jump
- .LP
- If there are several consecutive instruction labels
- (which is highly unusual),
- all of them are put in the same basic block.
- Note that several cases may overlap,
- e.g. a label definition at the beginning of a procedure
- or a label following a jump.
- .PP
- A simple Finite State Machine is used to model
- the above rules.
- It also recognizes the end of a procedure,
- marked by an END pseudo.
- The basic blocks are stored internally as a doubly linked
- linear list.
- The blocks are linked in textual order.
- Every node of this list has the attributes described
- in the previous chapter (see syntax rule for
- basic_block).
- Furthermore, every node contains a pointer to its
- EM instructions,
- which are represented internally
- as a linear, doubly linked list,
- just as in the IC phase.
- However, instead of one list per procedure (as in IC)
- there is now one list per basic block.
- .PP
- On the fly, a table is build that maps
- every label identifier to the label definition
- instruction.
- This table is used for computing the control flow.
- The table is stored as a dynamically allocated array.
- The length of the array is the number of labels
- of the current procedure;
- this value can be found in the procedure table,
- where it was stored by IC.
|