cf_succ.c 5.9 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240
  1. /* $Id$ */
  2. /*
  3. * (c) copyright 1987 by the Vrije Universiteit, Amsterdam, The Netherlands.
  4. * See the copyright notice in the ACK home directory, in the file "Copyright".
  5. */
  6. /* C O N T R O L F L O W
  7. *
  8. * C F _ S U C C . C
  9. */
  10. #include <stdio.h>
  11. #include <em_spec.h>
  12. #include <em_pseu.h>
  13. #include <em_flag.h>
  14. #include <em_mnem.h>
  15. #include "../share/types.h"
  16. #include "../share/def.h"
  17. #include "../share/debug.h"
  18. #include "../share/global.h"
  19. #include "../share/lset.h"
  20. #include "../share/cset.h"
  21. #include "cf.h"
  22. #include "../share/map.h"
  23. extern char em_flag[];
  24. static void succeeds(bblock_p succ, bblock_p pred)
  25. {
  26. assert(pred != (bblock_p) 0);
  27. if (succ != (bblock_p) 0) {
  28. Ladd(succ, &pred->b_succ);
  29. Ladd(pred, &succ->b_pred);
  30. }
  31. }
  32. #define IS_RETURN(i) (i == op_ret || i == op_rtt)
  33. #define IS_CASE_JUMP(i) (i == op_csa || i == op_csb)
  34. #define IS_UNCOND_JUMP(i) (i <= sp_lmnem && (em_flag[i-sp_fmnem] & EM_FLO) == FLO_T)
  35. #define IS_COND_JUMP(i) (i <= sp_lmnem && (em_flag[i-sp_fmnem] & EM_FLO) == FLO_C)
  36. #define TARGET(lnp) (lbmap[INSTRLAB(lnp)])
  37. #define ATARGET(arg) (lbmap[arg->a_a.a_instrlab])
  38. static arg_p skip_const(arg_p arg)
  39. {
  40. assert(arg != (arg_p) 0);
  41. switch(arg->a_type) {
  42. case ARGOFF:
  43. case ARGICN:
  44. case ARGUCN:
  45. break;
  46. default:
  47. error("bad case descriptor");
  48. }
  49. return arg->a_next;
  50. }
  51. static arg_p use_label(arg_p arg, bblock_p b)
  52. {
  53. if (arg->a_type == ARGINSTRLAB) {
  54. /* arg is a non-null label */
  55. succeeds(ATARGET(arg),b);
  56. }
  57. return arg->a_next;
  58. }
  59. static void case_flow(short instr, line_p desc, bblock_p b)
  60. {
  61. /* Analyse the case descriptor (given as a ROM pseudo instruction).
  62. * Every instruction label appearing in the descriptor
  63. * heads a basic block that is a successor of the block
  64. * in which the case instruction appears (b).
  65. */
  66. arg_p arg;
  67. assert(instr == op_csa || instr == op_csb);
  68. assert(TYPE(desc) == OPLIST);
  69. arg = ARG(desc);
  70. arg = use_label(arg,b);
  71. /* See if there is a default label. If so, then
  72. * its block is a successor of b. Set arg to
  73. * next argument.
  74. */
  75. if (instr == op_csa) {
  76. arg = skip_const(arg); /* skip lower bound */
  77. arg = skip_const(arg); /* skip lower-upper bound */
  78. while (arg != (arg_p) 0) {
  79. /* All following arguments are case labels
  80. * or zeroes.
  81. */
  82. arg = use_label(arg,b);
  83. }
  84. } else {
  85. /* csb instruction */
  86. arg = skip_const(arg); /* skip #entries */
  87. while (arg != (arg_p) 0) {
  88. /* All following arguments are alternatively
  89. * an index and an instruction label (possibly 0).
  90. */
  91. arg = skip_const(arg); /* skip index */
  92. arg = use_label(arg,b);
  93. }
  94. }
  95. }
  96. static line_p case_descr(line_p lnp)
  97. {
  98. /* lnp is the instruction just before a csa or csb,
  99. * so it is the instruction that pushes the address
  100. * of a case descriptor on the stack. Find that
  101. * descriptor, i.e. a rom pseudo instruction.
  102. * Note that this instruction will always be part
  103. * of the procedure in which the csa/csb occurs.
  104. */
  105. line_p l;
  106. dblock_p d;
  107. obj_p obj;
  108. dblock_id id;
  109. if (lnp == (line_p) 0 || (INSTR(lnp)) != op_lae) {
  110. error("cannot find 'lae descr' before csa/csb");
  111. }
  112. /* We'll first find the ROM and its dblock_id */
  113. obj = OBJ(lnp);
  114. if (obj->o_off != (offset) 0) {
  115. error("bad 'lae descr' before csa/csb");
  116. /* We require a descriptor to be an entire rom,
  117. * not part of a rom.
  118. */
  119. }
  120. d = obj->o_dblock;
  121. assert(d != (dblock_p) 0);
  122. if (d->d_pseudo != DROM) {
  123. error("case descriptor must be in rom");
  124. }
  125. id = d->d_id;
  126. /* We'll use the dblock_id to find the defining occurrence
  127. * of the rom in the EM text (i.e. a rom pseudo). As all
  128. * pseudos appear at the beginning of a procedure, we only
  129. * have to look in its first basic block.
  130. */
  131. assert(curproc != (proc_p) 0);
  132. assert(curproc->p_start != (bblock_p) 0);
  133. l = curproc->p_start->b_start; /* first instruction of curproc */
  134. while (l != (line_p) 0) {
  135. if ((INSTR(l)) == ps_sym &&
  136. SHORT(l) == id) {
  137. /* found! */
  138. assert((INSTR(l->l_next)) == ps_rom);
  139. return l->l_next;
  140. }
  141. l = l->l_next;
  142. }
  143. error("cannot find rom pseudo for case descriptor");
  144. /* NOTREACHED */
  145. return 0;
  146. }
  147. static void last2_instrs(bblock_p b, line_p *last_out, line_p *prev_out)
  148. {
  149. /* Determine the last and one-but-last instruction
  150. * of basic block b. An end-pseudo is not regarded
  151. * as an instruction. If the block contains only 1
  152. * instruction, prev_out is 0.
  153. */
  154. line_p l1,l2;
  155. l2 = b->b_start; /* first instruction of b */
  156. assert(l2 != (line_p) 0); /* block can not be empty */
  157. if ((l1 = l2->l_next) == (line_p) 0 || INSTR(l1) == ps_end) {
  158. *last_out = l2; /* single instruction */
  159. *prev_out = (line_p) 0;
  160. } else {
  161. while(l1->l_next != (line_p) 0 && INSTR(l1->l_next) != ps_end) {
  162. l2 = l1;
  163. l1 = l1->l_next;
  164. }
  165. *last_out = l1;
  166. *prev_out = l2;
  167. }
  168. }
  169. void control_flow(bblock_p head)
  170. {
  171. /* compute the successor and predecessor relation
  172. * for every basic block.
  173. */
  174. bblock_p b;
  175. line_p lnp, prev;
  176. short instr;
  177. for (b = head; b != (bblock_p) 0; b = b->b_next) {
  178. /* for every basic block, in textual order, do */
  179. last2_instrs(b, &lnp, &prev);
  180. /* find last and one-but-last instruction */
  181. instr = INSTR(lnp);
  182. /* The last instruction of the basic block
  183. * determines the set of successors of the block.
  184. */
  185. if (IS_CASE_JUMP(instr)) {
  186. case_flow(instr,case_descr(prev),b);
  187. /* If lnp is a csa or csb, then the instruction
  188. * just before it (i.e. prev) must be the
  189. * instruction that pushes the address of the
  190. * case descriptor. This descriptor is found
  191. * and analysed in order to build the successor
  192. * and predecessor sets of b.
  193. */
  194. } else {
  195. if (!IS_RETURN(instr)) {
  196. if (IS_UNCOND_JUMP(instr)) {
  197. if (instr != op_gto) {
  198. succeeds(TARGET(lnp),b);
  199. }
  200. } else {
  201. if (IS_COND_JUMP(instr)) {
  202. succeeds(TARGET(lnp),b);
  203. succeeds(b->b_next, b);
  204. /* Textually next block is
  205. * a successor of b.
  206. */
  207. } else {
  208. /* normal instruction */
  209. succeeds(b->b_next, b);
  210. }
  211. }
  212. }
  213. }
  214. }
  215. }