ra_items.c 6.9 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351
  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. /* R E G I S T E R A L L O C A T I O N
  7. *
  8. * R A _ I T E M S . C
  9. */
  10. #include <em_mnem.h>
  11. #include <em_spec.h>
  12. #include <em_pseu.h>
  13. #include <em_reg.h>
  14. #include "../share/types.h"
  15. #include "../share/debug.h"
  16. #include "../share/def.h"
  17. #include "../share/global.h"
  18. #include "../share/lset.h"
  19. #include "../share/aux.h"
  20. #include "../share/alloc.h"
  21. #include "ra.h"
  22. #include "ra_aux.h"
  23. #include "ra_items.h"
  24. #include "itemtab.h"
  25. /* Maps EM mnemonics onto item types, e.g. op_lol -> LOCALVAR, op_ldc->DCONST,
  26. * generated from em_mmen.h and itemtab.src files.
  27. */
  28. #define SMALL_CONSTANT(c) (c >= 0 && c <= 8)
  29. /* prevent small constants from being put in a register */
  30. clean_tab(items)
  31. item_p items[];
  32. {
  33. int t;
  34. for (t = 0; t < NRITEMTYPES;t++) {
  35. items[t] = (item_p) 0;
  36. }
  37. }
  38. short item_type(l)
  39. line_p l;
  40. {
  41. int instr = INSTR(l);
  42. int t;
  43. if (instr < sp_fmnem || instr > sp_lmnem) return NO_ITEM;
  44. t = itemtab[instr - sp_fmnem].id_type;
  45. if (t == CONST && SMALL_CONSTANT(off_set(l))) return NO_ITEM;
  46. return t;
  47. }
  48. bool is_item(l)
  49. line_p l;
  50. {
  51. return item_type(l) != NO_ITEM;
  52. }
  53. item_p item_of(off,items)
  54. offset off;
  55. item_p items[];
  56. {
  57. register item_p x;
  58. for (x = items[LOCALVAR]; x != (item_p) 0; x = x->it_next) {
  59. if (off == x->i_t.it_off) {
  60. if (!x->it_desirable) break;
  61. /* don't put this item in reg */
  62. return x;
  63. }
  64. }
  65. return (item_p) 0;
  66. }
  67. fill_item(item,l)
  68. item_p item;
  69. line_p l;
  70. {
  71. item->it_type = item_type(l);
  72. item->it_desirable = TRUE;
  73. switch(item->it_type) {
  74. case GLOBL_ADDR:
  75. item->i_t.it_obj = OBJ(l);
  76. break;
  77. case PROC_ADDR:
  78. item->i_t.it_proc = PROC(l);
  79. break;
  80. default:
  81. item->i_t.it_off = off_set(l);
  82. }
  83. }
  84. STATIC bool desirable(l)
  85. line_p l;
  86. {
  87. /* See if it is really desirable to put the item of line l
  88. * in a register. We do not put an item in a register if it
  89. * is used as 'address of array descriptor' of an array
  90. * instruction.
  91. */
  92. if (l->l_next != (line_p) 0) {
  93. switch(INSTR(l->l_next)) {
  94. case op_aar:
  95. case op_lar:
  96. case op_sar:
  97. return FALSE;
  98. }
  99. }
  100. return TRUE;
  101. }
  102. STATIC int cmp_items(a,b)
  103. item_p a,b;
  104. {
  105. /* This routine defines the <, = and > relations between items,
  106. * used to sort them for fast lookup.
  107. */
  108. offset n1,n2;
  109. switch(a->it_type) {
  110. case GLOBL_ADDR:
  111. assert(b->it_type == GLOBL_ADDR);
  112. n1 = (offset) a->i_t.it_obj->o_id;
  113. n2 = (offset) b->i_t.it_obj->o_id;
  114. break;
  115. case PROC_ADDR:
  116. assert(b->it_type == PROC_ADDR);
  117. n1 = (offset) a->i_t.it_proc->p_id;
  118. n2 = (offset) b->i_t.it_proc->p_id;
  119. break;
  120. default:
  121. n1 = a->i_t.it_off;
  122. n2 = b->i_t.it_off;
  123. }
  124. return (n1 == n2 ? 0 : (n1 > n2 ? 1 : -1));
  125. }
  126. bool same_item(a,b)
  127. item_p a,b;
  128. {
  129. return cmp_items(a,b) == 0;
  130. }
  131. STATIC bool lt_item(a,b)
  132. item_p a,b;
  133. {
  134. return cmp_items(a,b) == -1;
  135. }
  136. /* build_itemlist()
  137. *
  138. * Build a list of all items used in the current procedure. An item
  139. * is anything that can be put in a register (a local variable, a constant,
  140. * the address of a local or global variable).
  141. * For each type of item we use a sorted list containing all items of
  142. * that type found so far.
  143. * A local variable is only considered to be an item if there is a
  144. * register message for it (indicating it is never accessed indirectly).
  145. * For each item, we keep track of all places where it is used
  146. * (either fetched or stored into). The usage of a local variable is also
  147. * considered to be a usage of its address.
  148. */
  149. static item_p items[NRITEMTYPES]; /* items[i] points to the list of type i */
  150. STATIC short reg_type(item)
  151. item_p item;
  152. {
  153. /* See which type of register the item should best be assigned to */
  154. switch(item->it_type) {
  155. case LOCALVAR:
  156. return regv_type(item->i_t.it_off);
  157. /* use type mentioned in reg. message for local */
  158. case LOCAL_ADDR:
  159. case GLOBL_ADDR:
  160. case PROC_ADDR:
  161. return reg_pointer;
  162. case CONST:
  163. case DCONST:
  164. return reg_any;
  165. default: assert(FALSE);
  166. }
  167. /* NOTREACHED */
  168. }
  169. STATIC short item_size(item)
  170. item_p item;
  171. {
  172. /* Determine the size of the item (in bytes) */
  173. switch(item->it_type) {
  174. case LOCALVAR:
  175. return regv_size(item->i_t.it_off);
  176. /* use size mentioned in reg. message for local */
  177. case LOCAL_ADDR:
  178. case GLOBL_ADDR:
  179. case PROC_ADDR:
  180. return ps; /* pointer size */
  181. case CONST:
  182. return ws; /* word size */
  183. case DCONST:
  184. return 2 * ws; /* 2 * word size */
  185. default: assert(FALSE);
  186. }
  187. /* NOTREACHED */
  188. }
  189. STATIC init_item(a,b)
  190. item_p a,b;
  191. {
  192. a->it_type = b->it_type;
  193. switch(a->it_type) {
  194. case GLOBL_ADDR:
  195. a->i_t.it_obj = b->i_t.it_obj;
  196. break;
  197. case PROC_ADDR:
  198. a->i_t.it_proc = b->i_t.it_proc;
  199. break;
  200. default:
  201. a->i_t.it_off = b->i_t.it_off;
  202. }
  203. a->it_usage = Lempty_set();
  204. a->it_regtype = reg_type(b);
  205. a->it_size = item_size(b);
  206. a->it_desirable = b->it_desirable;
  207. }
  208. STATIC add_item(item,t,items)
  209. item_p item;
  210. time_p t;
  211. item_p items[];
  212. {
  213. /* See if there was already a list element for item. In any
  214. * case record the fact that item is used at 't'.
  215. */
  216. register item_p x, *q;
  217. q = &items[item->it_type]; /* each type has its own list */
  218. for (x = *q; x != (item_p) 0; x = *q) {
  219. if (same_item(x,item)) {
  220. /* found */
  221. if (!item->it_desirable) {
  222. x->it_desirable = FALSE;
  223. }
  224. Ladd(t,&x->it_usage);
  225. return; /* done */
  226. }
  227. if (lt_item(item,x)) break;
  228. q = &x->it_next;
  229. }
  230. /* not found, allocate new item; q points to it_next field of
  231. * the item after which the new item should be put.
  232. */
  233. x = newitem();
  234. x->it_next = *q;
  235. *q = x;
  236. init_item(x,item);
  237. Ladd(t,&x->it_usage);
  238. }
  239. STATIC add_usage(l,b,items)
  240. line_p l;
  241. bblock_p b;
  242. item_p items[];
  243. {
  244. /* An item is used at line l. Add it to the list of items.
  245. * A local variable is only considered to be an item, if
  246. * there is a register message for it; else its address
  247. * is also considered to be an item.
  248. */
  249. struct item thisitem;
  250. fill_item(&thisitem,l); /* fill in some fields */
  251. if (!desirable(l)) {
  252. thisitem.it_desirable = FALSE; /* don't put item in reg. */
  253. }
  254. if (thisitem.it_type == LOCALVAR && !is_regvar(thisitem.i_t.it_off)) {
  255. /* Use address of local instead of local itself */
  256. thisitem.it_type = LOCAL_ADDR;
  257. thisitem.it_regtype = reg_pointer;
  258. }
  259. add_item(&thisitem,cons_time(l,b),items);
  260. }
  261. build_itemlist(p,items,nrinstr_out)
  262. proc_p p;
  263. item_p items[];
  264. int *nrinstr_out;
  265. {
  266. /* Make a list of all items used in procedure p.
  267. * An item is anything that can be put in a register,
  268. * such as a local variable, a constant etc.
  269. * As a side effect, determine the number of instructions of p.
  270. */
  271. register line_p l;
  272. register bblock_p b;
  273. register cnt= 0;
  274. clean_tab(items);
  275. for (b = p->p_start; b != (bblock_p) 0; b = b->b_next) {
  276. for (l = b->b_start; l != (line_p) 0; l = l->l_next) {
  277. if (is_item(l)) {
  278. add_usage(l,b,items);
  279. }
  280. cnt++;
  281. }
  282. }
  283. *nrinstr_out = cnt;
  284. }