cf_succ.c 5.8 KB

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