casestat.C 8.8 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385
  1. /*
  2. * (c) copyright 1987 by the Vrije Universiteit, Amsterdam, The Netherlands.
  3. * See the copyright notice in the ACK home directory, in the file "Copyright".
  4. *
  5. * Author: Ceriel J.H. Jacobs
  6. */
  7. /* C A S E S T A T E M E N T C O D E G E N E R A T I O N */
  8. /* $Id$ */
  9. /* Generation of case statements is done by first creating a
  10. description structure for the statement, build a list of the
  11. case-labels, then generating a case description in the code,
  12. and generating either CSA or CSB, and then generating code for the
  13. cases themselves.
  14. */
  15. #include "debug.h"
  16. #include <em_label.h>
  17. #include <em_arith.h>
  18. #include <em_code.h>
  19. #include <alloc.h>
  20. #include <assert.h>
  21. #include "Lpars.h"
  22. #include "type.h"
  23. #include "LLlex.h"
  24. #include "node.h"
  25. #include "desig.h"
  26. #include "walk.h"
  27. #include "chk_expr.h"
  28. #include "def.h"
  29. #include "density.h"
  30. struct switch_hdr {
  31. label sh_break; /* label of statement after this one */
  32. label sh_default; /* label of ELSE part, or 0 */
  33. int sh_nrofentries; /* number of cases */
  34. t_type *sh_type; /* type of case expression */
  35. arith sh_lowerbd; /* lowest case label */
  36. arith sh_upperbd; /* highest case label */
  37. struct case_entry *sh_entries; /* the cases with their generated
  38. labels
  39. */
  40. };
  41. /* STATICALLOCDEF "switch_hdr" 5 */
  42. struct case_entry {
  43. struct case_entry *ce_next; /* next in list */
  44. label ce_label; /* generated label */
  45. arith ce_low, ce_up; /* lower and upper bound of range */
  46. };
  47. /* STATICALLOCDEF "case_entry" 20 */
  48. /* The constant DENSITY determines when CSA and when CSB instructions
  49. are generated. Reasonable values are: 2, 3, 4.
  50. On machines that have lots of address space and memory, higher values
  51. might also be reasonable. On these machines the density of jump tables
  52. may be lower.
  53. */
  54. compact(nr, low, up)
  55. arith low, up;
  56. {
  57. /* Careful! up - low might not fit in an arith. And then,
  58. the test "up-low < 0" might also not work to detect this
  59. situation! Or is this just a bug in the M68020/M68000?
  60. */
  61. arith diff = up - low;
  62. return (nr != 0 && diff >= 0 && fit(diff, (int) word_size) &&
  63. diff / nr <= (DENSITY - 1));
  64. }
  65. #define nd_lab nd_symb
  66. int
  67. CaseCode(nd, exitlabel, end_reached)
  68. t_node *nd;
  69. label exitlabel;
  70. {
  71. /* Check the expression, stack a new case header and
  72. fill in the necessary fields.
  73. "exitlabel" is the exit-label of the closest enclosing
  74. LOOP-statement, or 0.
  75. */
  76. register struct switch_hdr *sh = new_switch_hdr();
  77. register t_node *pnode = nd;
  78. register struct case_entry *ce;
  79. register arith val;
  80. label CaseDescrLab;
  81. int rval;
  82. assert(pnode->nd_class == Stat && pnode->nd_symb == CASE);
  83. if (ChkExpression(&(pnode->nd_LEFT))) {
  84. MkCoercion(&(pnode->nd_LEFT),BaseType(pnode->nd_LEFT->nd_type));
  85. CodePExpr(pnode->nd_LEFT);
  86. }
  87. sh->sh_type = pnode->nd_LEFT->nd_type;
  88. sh->sh_break = ++text_label;
  89. /* Now, create case label list
  90. */
  91. while (pnode = pnode->nd_RIGHT) {
  92. if (pnode->nd_class == Link && pnode->nd_symb == '|') {
  93. if (pnode->nd_LEFT) {
  94. /* non-empty case
  95. */
  96. pnode->nd_LEFT->nd_lab = ++text_label;
  97. AddCases(sh, /* to descriptor */
  98. pnode->nd_LEFT->nd_LEFT,
  99. /* of case labels */
  100. (label) pnode->nd_LEFT->nd_lab
  101. /* and code label */
  102. );
  103. }
  104. }
  105. else {
  106. /* Else part
  107. */
  108. sh->sh_default = ++text_label;
  109. break;
  110. }
  111. }
  112. if (!sh->sh_nrofentries) {
  113. /* There were no cases, so we have to check the case-expression
  114. here
  115. */
  116. if (! (sh->sh_type->tp_fund & T_DISCRETE)) {
  117. node_error(nd, "illegal type in CASE-expression");
  118. }
  119. }
  120. /* Now generate code for the switch itself
  121. First the part that CSA and CSB descriptions have in common.
  122. */
  123. CaseDescrLab = ++data_label; /* the rom must have a label */
  124. C_df_dlb(CaseDescrLab);
  125. if (sh->sh_default) C_rom_ilb(sh->sh_default);
  126. else C_rom_ucon("0", pointer_size);
  127. if (compact(sh->sh_nrofentries, sh->sh_lowerbd, sh->sh_upperbd)) {
  128. /* CSA
  129. */
  130. int gen = 1;
  131. ce = sh->sh_entries;
  132. while (! ce->ce_label) ce = ce->ce_next;
  133. C_rom_cst((arith) 0);
  134. C_rom_cst(sh->sh_upperbd - sh->sh_lowerbd);
  135. for (val = sh->sh_lowerbd; val <= sh->sh_upperbd; val++) {
  136. assert(ce);
  137. if (gen || val == ce->ce_low) {
  138. gen = 1;
  139. C_rom_ilb(ce->ce_label);
  140. if (val == ce->ce_up) {
  141. gen = 0;
  142. ce = ce->ce_next;
  143. while (ce && ! ce->ce_label) ce = ce->ce_next;
  144. }
  145. }
  146. else if (sh->sh_default) C_rom_ilb(sh->sh_default);
  147. else C_rom_ucon("0", pointer_size);
  148. }
  149. C_loc(sh->sh_lowerbd);
  150. C_sbu(word_size);
  151. c_lae_dlb(CaseDescrLab); /* perform the switch */
  152. C_csa(word_size);
  153. }
  154. else {
  155. /* CSB
  156. */
  157. C_rom_cst((arith)sh->sh_nrofentries);
  158. for (ce = sh->sh_entries; ce; ce = ce->ce_next) {
  159. /* generate the entries: value + prog.label
  160. */
  161. if (! ce->ce_label) continue;
  162. val = ce->ce_low;
  163. do {
  164. C_rom_cst(val);
  165. C_rom_ilb(ce->ce_label);
  166. } while (val++ != ce->ce_up);
  167. }
  168. c_lae_dlb(CaseDescrLab); /* perform the switch */
  169. C_csb(word_size);
  170. }
  171. /* Now generate code for the cases
  172. */
  173. pnode = nd;
  174. rval = 0;
  175. while (pnode = pnode->nd_RIGHT) {
  176. if (pnode->nd_class == Link && pnode->nd_symb == '|') {
  177. if (pnode->nd_LEFT) {
  178. rval |= LblWalkNode((label) pnode->nd_LEFT->nd_lab,
  179. pnode->nd_LEFT->nd_RIGHT,
  180. exitlabel, end_reached);
  181. c_bra(sh->sh_break);
  182. }
  183. }
  184. else {
  185. /* Else part
  186. */
  187. assert(sh->sh_default != 0);
  188. rval |= LblWalkNode(sh->sh_default,
  189. pnode, exitlabel, end_reached);
  190. break;
  191. }
  192. }
  193. def_ilb(sh->sh_break);
  194. FreeSh(sh);
  195. return rval;
  196. }
  197. FreeSh(sh)
  198. register struct switch_hdr *sh;
  199. {
  200. /* free the allocated switch structure
  201. */
  202. register struct case_entry *ce;
  203. ce = sh->sh_entries;
  204. while (ce) {
  205. struct case_entry *tmp = ce->ce_next;
  206. free_case_entry(ce);
  207. ce = tmp;
  208. }
  209. free_switch_hdr(sh);
  210. }
  211. AddCases(sh, node, lbl)
  212. struct switch_hdr *sh;
  213. register t_node *node;
  214. label lbl;
  215. {
  216. /* Add case labels to the case label list
  217. */
  218. if (node->nd_class == Link) {
  219. if (node->nd_symb == UPTO) {
  220. assert(node->nd_LEFT->nd_class == Value);
  221. assert(node->nd_RIGHT->nd_class == Value);
  222. AddOneCase(sh, node->nd_LEFT, node->nd_RIGHT, lbl);
  223. return;
  224. }
  225. assert(node->nd_symb == ',');
  226. AddCases(sh, node->nd_LEFT, lbl);
  227. AddCases(sh, node->nd_RIGHT, lbl);
  228. return;
  229. }
  230. assert(node->nd_class == Value);
  231. AddOneCase(sh, node, node, lbl);
  232. }
  233. AddOneCase(sh, lnode, rnode, lbl)
  234. register struct switch_hdr *sh;
  235. t_node *lnode, *rnode;
  236. label lbl;
  237. {
  238. register struct case_entry *ce = new_case_entry();
  239. register struct case_entry *c1 = sh->sh_entries, *c2 = 0;
  240. int fund = sh->sh_type->tp_fund;
  241. arith diff;
  242. if (! ChkCompat(&lnode, sh->sh_type, "case") ||
  243. ! ChkCompat(&rnode, sh->sh_type, "case")) {
  244. }
  245. ce->ce_label = lbl;
  246. ce->ce_low = lnode->nd_INT;
  247. ce->ce_up = rnode->nd_INT;
  248. diff = rnode->nd_INT - lnode->nd_INT;
  249. #define MAXRANGE 100
  250. if (diff < 0 || diff > MAXRANGE) {
  251. /* This is a bit of a hack, but it prevents the compiler
  252. from crashing on things like
  253. CASE a OF
  254. 10 .. MAX(CARDINAL): ....
  255. If the range covers more than MAXRANGE cases, this case
  256. is dealt with separately.
  257. */
  258. label cont = ++text_label;
  259. C_dup(int_size);
  260. C_loc(lnode->nd_INT);
  261. if (fund == T_INTEGER) {
  262. C_blt(cont);
  263. }
  264. else {
  265. C_cmu(int_size);
  266. C_zlt(cont);
  267. }
  268. C_dup(int_size);
  269. C_loc(rnode->nd_INT);
  270. if (fund == T_INTEGER) {
  271. C_bgt(cont);
  272. }
  273. else {
  274. C_cmu(int_size);
  275. C_zgt(cont);
  276. }
  277. C_asp(int_size);
  278. c_bra(lbl);
  279. C_df_ilb(cont);
  280. ce->ce_label = 0;
  281. }
  282. if (sh->sh_entries == 0) {
  283. /* first case entry
  284. */
  285. sh->sh_entries = ce;
  286. if (ce->ce_label) {
  287. sh->sh_lowerbd = ce->ce_low;
  288. sh->sh_upperbd = ce->ce_up;
  289. }
  290. }
  291. else {
  292. /* second etc. case entry
  293. find the proper place to put ce into the list
  294. */
  295. while (c1 && chk_bounds(c1->ce_low, ce->ce_low, fund)) {
  296. c2 = c1;
  297. c1 = c1->ce_next;
  298. }
  299. /* At this point three cases are possible:
  300. 1: c1 != 0 && c2 != 0:
  301. insert ce somewhere in the middle
  302. 2: c1 != 0 && c2 == 0:
  303. insert ce right after the head
  304. 3: c1 == 0 && c2 != 0:
  305. append ce to last element
  306. The case c1 == 0 && c2 == 0 cannot occur, since
  307. the list is guaranteed not to be empty.
  308. */
  309. if (c2) {
  310. if ( chk_bounds(ce->ce_low, c2->ce_up, fund)) {
  311. node_error(rnode, "multiple case entry for value %ld", (long)(ce->ce_low));
  312. free_case_entry(ce);
  313. return;
  314. }
  315. }
  316. if (c1) {
  317. if ( chk_bounds(c1->ce_low, ce->ce_up, fund)) {
  318. node_error(rnode, "multiple case entry for value %ld", (long)(ce->ce_up));
  319. free_case_entry(ce);
  320. return;
  321. }
  322. if (c2) {
  323. ce->ce_next = c2->ce_next;
  324. c2->ce_next = ce;
  325. }
  326. else {
  327. ce->ce_next = sh->sh_entries;
  328. sh->sh_entries = ce;
  329. }
  330. }
  331. else {
  332. assert(c2);
  333. c2->ce_next = ce;
  334. }
  335. if (ce->ce_label) {
  336. if (! chk_bounds(sh->sh_lowerbd, ce->ce_low, fund)) {
  337. sh->sh_lowerbd = ce->ce_low;
  338. }
  339. if (! chk_bounds(ce->ce_up, sh->sh_upperbd, fund)) {
  340. sh->sh_upperbd = ce->ce_up;
  341. }
  342. }
  343. }
  344. if (ce->ce_label) sh->sh_nrofentries += ce->ce_up - ce->ce_low + 1;
  345. }