types.h 11 KB

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