doc/ego/cf/cf1

   1 .bp
   2 .NH
   3 The Control Flow Phase
   4 .PP
   5 In the previous chapter we described the intermediate
   6 code of the global optimizer.
   7 We also specified which part of this code
   8 was constructed by the IC phase of the optimizer.
   9 The Control Flow Phase (\fICF\fR) does
  10 the remainder of the job,
  11 i.e. it determines:
  12 .IP -
  13 the control flow graphs
  14 .IP -
  15 the loop tables
  16 .IP -
  17 the calling, change and use attributes of
  18 the procedure table entries
  19 .LP
  20 CF operates on one procedure at a time.
  21 For every procedure it first reads the EM instructions
  22 from the EM-text file and groups them into basic blocks.
  23 For every basic block, its successors and
  24 predecessors are determined,
  25 resulting in the control flow graph.
  26 Next, the immediate dominator of every basic block
  27 is computed.
  28 Using these dominators, any loop in the
  29 procedure is detected.
  30 Finally, interprocedural analysis is done,
  31 after which we will know the global effects of
  32 every procedure call on its environment.
  33 .sp
  34 CF uses the same internal data structures
  35 for the procedure table and object table as IC.
  36 .NH 2
  37 Partitioning into basic blocks
  38 .PP
  39 With regard to flow of control, we distinguish
  40 three kinds of EM instructions:
  41 jump instructions, instruction label definitions and
  42 normal instructions.
  43 Jump instructions are all conditional or unconditional
  44 branch instructions,
  45 the case instructions (CSA/CSB)
  46 and the RET (return) instruction.
  47 A procedure call (CAL) is not considered to be a jump.
  48 A defining occurrence of an instruction label
  49 is regarded as an EM instruction.
  50 .PP
  51 An instruction starts
  52 a new basic block, in any of the following cases:
  53 .IP 1.
  54 It is the first instruction of a procedure
  55 .IP 2.
  56 It is the first of a list of instruction label
  57 defining occurrences
  58 .IP 3.
  59 It follows a jump
  60 .LP
  61 If there are several consecutive instruction labels
  62 (which is highly unusual),
  63 all of them are put in the same basic block.
  64 Note that several cases may overlap,
  65 e.g. a label definition at the beginning of a procedure
  66 or a label following a jump.
  67 .PP
  68 A simple Finite State Machine is used to model
  69 the above rules.
  70 It also recognizes the end of a procedure,
  71 marked by an END pseudo.
  72 The basic blocks are stored internally as a doubly linked
  73 linear list.
  74 The blocks are linked in textual order.
  75 Every node of this list has the attributes described
  76 in the previous chapter (see syntax rule for
  77 basic_block).
  78 Furthermore, every node contains a pointer to its
  79 EM instructions,
  80 which are represented internally
  81 as a linear, doubly linked list,
  82 just as in the IC phase.
  83 However, instead of one list per procedure (as in IC)
  84 there is now one list per basic block.
  85 .PP
  86 On the fly, a table is build that maps
  87 every label identifier to the label definition
  88 instruction.
  89 This table is used for computing the control flow.
  90 The table is stored as a dynamically allocated array.
  91 The length of the array is the number of labels
  92 of the current procedure;
  93 this value can be found in the procedure table,
  94 where it was stored by IC.