cf2 1.8 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950
  1. .NH 2
  2. Control Flow
  3. .PP
  4. A \fIsuccessor\fR of a basic block B is a block C
  5. that can be executed immediately after B.
  6. C is said to be a \fIpredecessor\fR of B.
  7. A block ending with a RET instruction
  8. has no successors.
  9. Such a block is called a \fIreturn block\fR.
  10. Any block that has no predecessors cannot be
  11. executed at all (i.e. it is unreachable),
  12. unless it is the first block of a procedure,
  13. called the \fIprocedure entry block\fR.
  14. .PP
  15. Internally, the successor and predecessor
  16. attributes of a basic block are stored as \fIsets\fR.
  17. Alternatively, one may regard all these
  18. sets of all basic blocks as a conceptual \fIgraph\fR,
  19. in which there is an edge from B to C if C
  20. is in the successor set of B.
  21. We call this conceptual graph
  22. the \fIControl Flow Graph\fR.
  23. .PP
  24. The only successor of a basic block ending on an
  25. unconditional branch instruction is the block that
  26. contains the label definition of the target of the jump.
  27. The target instruction can be found via the LAB_ID
  28. that is the operand of the jump instruction,
  29. by using the label-map table mentioned
  30. above.
  31. If the last instruction of a block is a
  32. conditional jump,
  33. the successors are the target block and the textually
  34. next block.
  35. The last instruction can also be a case jump
  36. instruction (CSA or CSB).
  37. We then analyze the case descriptor,
  38. to find all possible target instructions
  39. and their associated blocks.
  40. We require the case descriptor to be allocated in
  41. a ROM, so it cannot be changed dynamically.
  42. A case jump via an alterable descriptor could in principle
  43. go to any label in the program.
  44. In the presence of such an uncontrolled jump,
  45. hardly any optimization can be done.
  46. We do not expect any front end to generate such a descriptor,
  47. however, because of the controlled nature
  48. of case statements in high level languages.
  49. If the basic block does not end in a jump instruction,
  50. its only successor is the textually next block.