types.h 11 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424
  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. /* I N T E R N A L D A T A S T R U C T U R E S O F E G O */
  7. /* This file contains the definitions of the global data types.
  8. */
  9. /* TEMPORARY: */
  10. #define LONGOFF
  11. #define IDL 256 /* maximum identifier length */
  12. #define DYNAMIC 1
  13. #define NARGBYTES 14
  14. #define BMASK 0377
  15. typedef struct argbytes argb_t;
  16. typedef char byte;
  17. typedef byte bool;
  18. typedef long offset;
  19. typedef short obj_id;
  20. typedef short proc_id;
  21. typedef short dblock_id;
  22. typedef short block_id;
  23. typedef short loop_id;
  24. typedef short lab_id;
  25. typedef struct dblock *dblock_p;
  26. typedef struct obj *obj_p;
  27. typedef struct proc *proc_p;
  28. typedef struct loop *loop_p;
  29. typedef struct change *change_p;
  30. typedef struct use *use_p;
  31. typedef struct bblock *bblock_p;
  32. typedef struct line *line_p;
  33. typedef struct arg *arg_p;
  34. typedef struct argbytes *argb_p;
  35. typedef struct elemholder *elem_p;
  36. typedef struct elemholder *lset;
  37. typedef struct bitvector *cset;
  38. typedef elem_p Lindex;
  39. typedef short Cindex;
  40. typedef void *Lelem_t;
  41. typedef short Celem_t;
  42. typedef union pext_t *pext_p;
  43. typedef union bext_t *bext_p;
  44. typedef union lpext_t *lpext_p;
  45. typedef struct call *call_p;
  46. typedef struct formal *formal_p;
  47. /* Used-Definition Analysis */
  48. typedef struct local *local_p;
  49. typedef struct cond_tab *cond_p;
  50. #define TRUE 1
  51. #define FALSE 0
  52. /* DATABLOCKS */
  53. /* A datablock is a block of global data, declared by means of
  54. * a hol, bss, con or rom pseudo. The declaration may be in a file
  55. * that is inaccessible to EGO, in which case the pseudo is unknown.
  56. * Successive rom or con pseudos that are garanteed to be in the
  57. * same fragment (according to the EM definition) share the
  58. * same fragment number.
  59. */
  60. #define DHOL 0
  61. #define DBSS 1
  62. #define DROM 2
  63. #define DCON 3
  64. #define DUNKNOWN 4
  65. /* The following constants are used by the debugging tools: */
  66. #define D_FIRST DHOL
  67. #define D_LAST DUNKNOWN
  68. struct dblock {
  69. dblock_id d_id; /* unique integer */
  70. byte d_pseudo; /* one of DHOL,DBSS,DROM,DCON,DUNKNOWN */
  71. offset d_size; /* # bytes, -1 if unknown */
  72. obj_p d_objlist; /* list of objects of the data block */
  73. byte d_flags1; /* see below */
  74. byte d_flags2; /* free to be used by phases */
  75. arg_p d_values; /* values, in case of ROM */
  76. short d_fragmnr; /* fragment number */
  77. dblock_p d_next; /* link to next block */
  78. };
  79. #define DF_EXTERNAL 01 /* Is name visible outside its module? */
  80. /* OBJECTS */
  81. /* An object is a row of successive bytes in one datablock
  82. * that are considered to be a whole. E.g. scalar variables,
  83. * arrays, I/O buffers etc. are objects.
  84. */
  85. struct obj {
  86. offset o_off; /* offset within the block */
  87. offset o_size; /* size of the object, 0 if not known */
  88. obj_id o_id; /* unique integer */
  89. dblock_p o_dblock; /* backlink to data block */
  90. short o_globnr; /* global variable number */
  91. obj_p o_next; /* link */
  92. };
  93. /* PROCEDURES */
  94. struct proc {
  95. proc_id p_id; /* unique integer */
  96. short p_nrlabels; /* #instruction labels in the proc */
  97. offset p_localbytes; /* #bytes for locals */
  98. offset p_nrformals; /* #bytes for formals */
  99. byte p_flags1; /* see below */
  100. byte p_flags2; /* free to be used by phases */
  101. bblock_p p_start; /* pointer to first basic block */
  102. cset p_calling; /* set of all procs called by this one */
  103. lset p_loops; /* information about loops */
  104. change_p p_change; /* variables changed by this proc */
  105. use_p p_use; /* variables used by this proc */
  106. pext_p p_extend; /* pointer to any further information */
  107. proc_p p_next; /* link */
  108. };
  109. union pext_t {
  110. struct pext_il {
  111. call_p p_cals; /* candidate calls for in line expansion */
  112. short p_size; /* length of proc (EM-instrs or bytes) */
  113. formal_p p_formals; /* description of formals */
  114. short p_nrcalled; /* # times proc is called (varying) */
  115. long p_ccaddr; /* address of calcnt info on disk */
  116. long p_laddr; /* address in EM-text file on disk */
  117. short p_orglabels; /* original #labels before substitution */
  118. offset p_orglocals; /* original #bytes for locals */
  119. } px_il;
  120. } ;
  121. #define PF_EXTERNAL 01 /* proc is externally visible */
  122. #define PF_BODYSEEN 02 /* body of proc is available as EM text */
  123. #define PF_CALUNKNOWN 04 /* proc calls an unavailable procedure */
  124. #define PF_ENVIRON 010 /* proc does a lxa or lxl */
  125. #define PF_LPI 020 /* proc may be called indirect */
  126. #define PF_CALINLOOP 040 /* proc ever called in a loop? (transitively) */
  127. #define PF_GTO 0100 /* proc may be entered via GTO instruction */
  128. #define CALLED_IN_LOOP(p) p->p_flags1 |= PF_CALINLOOP
  129. #define IS_CALLED_IN_LOOP(p) (p->p_flags1 & PF_CALINLOOP)
  130. #define IS_ENTERED_WITH_GTO(p) (p->p_flags1 & PF_GTO)
  131. #define ENTERED_WITH_GTO(p) p->p_flags1 |= PF_GTO
  132. #define BODY_KNOWN(p) (p->p_flags1 & (byte) PF_BODYSEEN)
  133. /* LOOPS */
  134. struct loop {
  135. loop_id lp_id; /* unique integer */
  136. short lp_level; /* nesting level, 0=outermost loop,
  137. * 1=loop within loop etc. */
  138. bblock_p lp_entry; /* unique entry block of loop */
  139. bblock_p lp_end; /* tail of back edge of natural loop */
  140. lpext_p lp_extend; /* pointer to any further information */
  141. };
  142. union lpext_t {
  143. struct lpext_cf {
  144. lset lpx_blocks;
  145. short lpx_count;
  146. bool lpx_messy;
  147. } lpx_cf;
  148. struct lpext_sr {
  149. lset lpx_blocks; /* basic blocks constituting the loop */
  150. bblock_p lpx_header; /* header block, 0 if no one allocated yet */
  151. bool lpx_done; /* TRUE if we've processed this loop */
  152. line_p lpx_instr; /* current last instruction in header block*/
  153. } lpx_sr;
  154. struct lpext_ra {
  155. lset lpx_blocks; /* basic blocks constituting the loop */
  156. bblock_p lpx_header; /* header block, 0 if no one allocated yet */
  157. } lpx_ra;
  158. } ;
  159. /* CHANGED/USED VARIABLES INFORMATION */
  160. struct change {
  161. cset c_ext; /* external variables changed */
  162. short c_flags; /* see below */
  163. };
  164. struct use {
  165. short u_flags; /* see below */
  166. };
  167. #define CF_INDIR 01
  168. #define UF_INDIR 01
  169. #define CHANGE_INDIR(p) (p->p_change->c_flags & CF_INDIR)
  170. /* SETS */
  171. /* There are 2 set representations:
  172. * - long (lset), which is essentially a list
  173. * - compact (cset), which is essentially a bitvector
  174. */
  175. struct elemholder {
  176. char *e_elem; /* pointer to the element */
  177. elem_p e_next; /* link */
  178. };
  179. struct bitvector {
  180. short v_size; /* # significant bits */
  181. int v_bits[DYNAMIC];/* a row of bits */
  182. };
  183. /* BASIC BLOCKS */
  184. /* Note that the b_succ and b_pred fields constitute the
  185. * Control Flow Graph
  186. */
  187. struct bblock {
  188. block_id b_id; /* unique integer */
  189. line_p b_start; /* pointer to first instruction */
  190. lset b_succ; /* set of successor blocks */
  191. lset b_pred; /* set of predecessor blocks */
  192. bblock_p b_idom; /* immediate dominator */
  193. lset b_loops; /* set of loops it is in */
  194. short b_flags; /* see below */
  195. bext_p b_extend; /* pointer to any further information */
  196. bblock_p b_next; /* link to textually next block */
  197. };
  198. union bext_t {
  199. struct bext_cf {
  200. short bx_semi; /* dfs number of semi-dominator */
  201. bblock_p bx_parent; /* parent in dfs spanning tree */
  202. lset bx_bucket; /* set of vertices whose sdom is b */
  203. bblock_p bx_ancestor; /* ancestor of b in forest, */
  204. bblock_p bx_label; /* used by link/eval */
  205. } bx_cf;
  206. struct bext_ud {
  207. cset bx_gen; /* definition generated in b */
  208. cset bx_kill; /* defs. outside b killed by b */
  209. cset bx_in; /* defs. reaching beginning of b */
  210. cset bx_out; /* defs. reaching end of b */
  211. cset bx_cgen; /* generated copies */
  212. cset bx_ckill; /* killed copies */
  213. cset bx_cin; /* copies reaching begin of b */
  214. cset bx_cout; /* copies reaching end of b */
  215. cset bx_chgvars; /* variables changed by b */
  216. } bx_ud;
  217. struct bext_lv {
  218. cset bx_use; /* variables used before being defined */
  219. cset bx_def; /* variables defined before being used */
  220. cset bx_lin; /* variables live at entry of b */
  221. cset bx_lout; /* variables live at exit of b */
  222. } bx_lv;
  223. struct bext_ra {
  224. short bx_begin; /* number of first instruction of block */
  225. short bx_end; /* number of last instruction of block */
  226. } bx_ra;
  227. } ;
  228. #define BF_STRONG 01
  229. #define BF_FIRM 02
  230. #define IS_STRONG(b) (b->b_flags&BF_STRONG)
  231. #define IS_FIRM(b) (b->b_flags&BF_FIRM)
  232. /* EM INSTRUCTIONS */
  233. /* Kinds of operand types (l_optype field) */
  234. #define OPNO 0
  235. #define OPSHORT 1
  236. #define OPOFFSET 2
  237. #define OPINSTRLAB 3
  238. #define OPOBJECT 4
  239. #define OPPROC 5
  240. #define OPLIST 6
  241. /* The following constants are used by the debugging tools: */
  242. #define OP_FIRST OPNO
  243. #define OP_LAST OPLIST
  244. #define LDATA 0
  245. #define LTEXT 01
  246. struct line {
  247. line_p l_next; /* link */
  248. byte l_instr; /* instruction */
  249. byte l_optype; /* kind of operand, used as tag */
  250. line_p l_prev; /* backlink to previous instruction */
  251. union {
  252. short la_short; /* short: LOC 5 */
  253. offset la_offset; /* offset: LDC 20 */
  254. lab_id la_instrlab; /* label: BRA *10 */
  255. obj_p la_obj; /* object: LOE X+2 */
  256. proc_p la_proc; /* proc: CAL F3 */
  257. arg_p la_arg; /* arguments: HOL 10,0,0 */
  258. } l_a;
  259. };
  260. /* ARGUMENTS */
  261. /* String representation of a constant, partitioned into
  262. * pieces of NARGBYTES bytes.
  263. */
  264. #define ARGOFF 0
  265. #define ARGINSTRLAB 1
  266. #define ARGOBJECT 2
  267. #define ARGPROC 3
  268. #define ARGSTRING 4
  269. #define ARGICN 5
  270. #define ARGUCN 6
  271. #define ARGFCN 7
  272. #define ARGCEND 8
  273. struct argbytes {
  274. argb_p ab_next;
  275. short ab_index;
  276. char ab_contents[NARGBYTES];
  277. };
  278. struct arg {
  279. arg_p a_next; /* link */
  280. short a_type; /* kind of argument */
  281. union {
  282. offset a_offset; /* offset */
  283. lab_id a_instrlab; /* instruction label */
  284. proc_p a_proc; /* procedure */
  285. obj_p a_obj; /* object */
  286. argb_t a_string; /* string */
  287. struct { /* int/unsigned/float constant */
  288. short ac_length; /* size in bytes */
  289. argb_t ac_con; /* its string repres. */
  290. } a_con;
  291. } a_a;
  292. };
  293. /* Macros to increase readability: */
  294. #define INSTR(lnp) (lnp->l_instr & BMASK)
  295. #define TYPE(lnp) lnp->l_optype
  296. #define PREV(lnp) lnp->l_prev
  297. #define SHORT(lnp) lnp->l_a.la_short
  298. #define OFFSET(lnp) lnp->l_a.la_offset
  299. #define INSTRLAB(lnp) lnp->l_a.la_instrlab
  300. #define OBJ(lnp) lnp->l_a.la_obj
  301. #define PROC(lnp) lnp->l_a.la_proc
  302. #define ARG(lnp) lnp->l_a.la_arg
  303. /* Data structures for Use-Definition and Live-Dead Analysis */
  304. struct local {
  305. offset lc_off; /* offset of local in stackframe */
  306. short lc_size; /* size of local in bytes */
  307. short lc_flags; /* see below */
  308. offset lc_score; /* score in register message, if regvar */
  309. local_p lc_next; /* link, only used when building the list */
  310. };
  311. /* values of lc_flags */
  312. #define LCF_BAD 01
  313. /* Set when no ud-info for this local is maintained, e.g. when it is
  314. * overlapped by another local.
  315. */
  316. #define LCF_REG 02 /* register variable */
  317. #define LCF_LIVE 04 /* use by live-dead message generation */
  318. struct cond_tab {
  319. short mc_cond; /* Denotes a condition e.g. FITBYTE */
  320. short mc_tval; /* value for time optimization */
  321. short mc_sval; /* value for space optimization */
  322. short mc_dummy; /* allignment */
  323. };
  324. /* conditions: */
  325. #define DEFAULT 0
  326. #define FITBYTE 1
  327. #define IN_0_63 2
  328. #define IN_0_8 3