cf_succ.c 6.0 KB

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