ud.c 11 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549
  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. /* U S E - D E F I N I T I O N A N A L Y S I S */
  7. #include <stdlib.h>
  8. #include <stdio.h>
  9. #include <string.h>
  10. #include <em_spec.h>
  11. #include "../share/types.h"
  12. #include "ud.h"
  13. #include "../share/debug.h"
  14. #include "../share/global.h"
  15. #include "../share/lset.h"
  16. #include "../share/cset.h"
  17. #include "../share/def.h"
  18. #include "../share/files.h"
  19. #include "../share/map.h"
  20. #include "../share/get.h"
  21. #include "../share/put.h"
  22. #include "../share/alloc.h"
  23. #include "../share/aux.h"
  24. #include "../share/init_glob.h"
  25. #include "../share/locals.h"
  26. #include "../share/go.h"
  27. #include "ud_defs.h"
  28. #include "ud_const.h"
  29. #include "ud_copy.h"
  30. /* core allocation macros */
  31. #define newudbx() (bext_p) newstruct(bext_ud)
  32. #define oldudbx(x) oldstruct(bext_ud,x)
  33. short nrglobals;
  34. short nrvars;
  35. int Svalue,Svariable;
  36. cond_p globl_cond_tab,local_cond_tab;
  37. static cond_p getcondtab(FILE *f)
  38. {
  39. int l,i;
  40. cond_p tab;
  41. fscanf(f,"%d",&l);
  42. tab = newcondtab(l);
  43. for (i = 0; i < l; i++) {
  44. fscanf(f,"%hd %hd %hd",&tab[i].mc_cond,&tab[i].mc_tval,
  45. &tab[i].mc_sval);
  46. }
  47. assert(tab[l-1].mc_cond == DEFAULT);
  48. return tab;
  49. }
  50. static int ud_machinit(void *param)
  51. {
  52. char s[100];
  53. FILE *f = (FILE *)param;
  54. for (;;) {
  55. while(getc(f) != '\n');
  56. fscanf(f,"%s",s);
  57. if (strcmp(s,"%%UD") == 0)break;
  58. }
  59. globl_cond_tab = getcondtab(f);
  60. local_cond_tab = getcondtab(f);
  61. return 0;
  62. }
  63. static bool test_cond(short cond, offset val)
  64. {
  65. switch(cond) {
  66. case DEFAULT:
  67. return TRUE;
  68. case FITBYTE:
  69. return val >= -128 && val < 128;
  70. }
  71. assert(FALSE);
  72. /* NOTREACHED */
  73. return FALSE;
  74. }
  75. static short map_value(struct cond_tab tab[], offset val, bool time)
  76. {
  77. cond_p p;
  78. for (p = &tab[0]; ; p++) {
  79. if (test_cond(p->mc_cond,val)) {
  80. return (time ? p->mc_tval : p->mc_sval);
  81. }
  82. }
  83. }
  84. static int init_root(void *param)
  85. {
  86. /* Initialise the IN OUT sets of the entry block of the
  87. * current procedure. Global variables and parameters
  88. * already have a value at this point, although we do
  89. * not know which value. Therefor, implicit definitions
  90. * to all global variables and parameters are
  91. * put in IN.
  92. */
  93. bblock_p root = (bblock_p)param;
  94. short v;
  95. for (v = 1; v <= nrglobals; v++) {
  96. Cadd(IMPLICIT_DEF(GLOB_TO_VARNR(v)), &IN(root));
  97. }
  98. for (v = 1; v <= nrlocals; v++) {
  99. if (locals[v]->lc_off >= 0) {
  100. Cadd(IMPLICIT_DEF(LOC_TO_VARNR(v)),&IN(root));
  101. }
  102. }
  103. /* OUT(root) = IN(root) - KILL(root) + GEN(root) */
  104. Ccopy_set(IN(root),&OUT(root));
  105. Csubtract(KILL(root),&OUT(root));
  106. Cjoin(GEN(root),&OUT(root));
  107. return 0;
  108. }
  109. static void unite_outs(lset bbset, cset *setp)
  110. {
  111. /* Take the union of OUT(b), for all b in bbset,
  112. * and put the result in setp.
  113. */
  114. Lindex i;
  115. Cclear_set(setp);
  116. for (i = Lfirst(bbset); i != (Lindex) 0; i = Lnext(i,bbset)) {
  117. Cjoin(OUT((bblock_p) Lelem(i)), setp);
  118. }
  119. }
  120. static void solve_equations(proc_p p)
  121. {
  122. /* Solve the data flow equations for reaching
  123. * definitions of procedure p.
  124. * These equations are:
  125. * (1) OUT(b) = IN(b) - KILL(b) + GEN(b)
  126. * (2) IN(b) = OUT(p1) + .. + OUT(pn) ;
  127. * where PRED(b) = {p1, .. , pn}
  128. * We use the iterative algorithm of Aho&Ullman to
  129. * solve the equations.
  130. */
  131. bblock_p b;
  132. bool change;
  133. cset newin;
  134. /* initializations */
  135. newin = Cempty_set(nrdefs);
  136. for (b = p->p_start; b != (bblock_p) 0; b = b->b_next) {
  137. IN(b) = Cempty_set(nrdefs);
  138. OUT(b) = Cempty_set(nrdefs);
  139. Ccopy_set(GEN(b), &OUT(b));
  140. }
  141. init_root(p->p_start);
  142. /* Global variables and parameters have already a value
  143. * at the procedure entry block.
  144. */
  145. change = TRUE;
  146. /* main loop */
  147. while (change) {
  148. change = FALSE;
  149. for (b = p->p_start->b_next; b != (bblock_p) 0; b = b->b_next) {
  150. unite_outs(b->b_pred, &newin);
  151. /* newin = OUT(p1) + .. + OUT(pn) */
  152. if (!Cequal(newin,IN(b))) {
  153. change = TRUE;
  154. Ccopy_set(newin, &IN(b));
  155. Ccopy_set(IN(b), &OUT(b));
  156. Csubtract(KILL(b), &OUT(b));
  157. Cjoin(GEN(b), &OUT(b));
  158. }
  159. }
  160. }
  161. for (b = p->p_start; b != (bblock_p) 0; b = b->b_next) {
  162. Cdeleteset(KILL(b));
  163. Cdeleteset(OUT(b));
  164. }
  165. Cdeleteset(newin);
  166. }
  167. static short global_addr_cost()
  168. {
  169. return add_timespace(map_value(globl_cond_tab,(offset) 0,TRUE),
  170. map_value(globl_cond_tab,(offset) 0,FALSE));
  171. }
  172. short local_addr_cost(offset off)
  173. {
  174. return add_timespace(map_value(local_cond_tab,off,TRUE),
  175. map_value(local_cond_tab,off,FALSE));
  176. }
  177. static bool fold_is_desirable(line_p old, line_p new)
  178. {
  179. /* See if it is desirable to replace the variable used by the
  180. * EM instruction 'old' by the variable used by 'new'.
  181. * We do not replace 'cheaply addressable variables' by 'expensively
  182. * addressable variables'. E.g. if we're optimizing object code size,
  183. * we do not replace a local variable by a global variable on a VAX,
  184. * because the former occupies 1 or 2 bytes and the latter occupies
  185. * 4 bytes.
  186. * If 2 local variables are equally expensive to address, we replace
  187. * the first one by the second only if the first one is used at
  188. * least as many times as the second one.
  189. */
  190. local_p oldloc,newloc;
  191. short old_cost,new_cost,nr;
  192. bool ok;
  193. if (TYPE(old) == OPOBJECT) {
  194. /* old variable is a global variable */
  195. return TYPE(new) != OPOBJECT &&
  196. global_addr_cost() >=
  197. local_addr_cost(off_set(new));
  198. }
  199. find_local(off_set(old),&nr,&ok);
  200. assert(ok);
  201. oldloc = locals[nr];
  202. old_cost = local_addr_cost(off_set(old));
  203. if (TYPE(new) == OPOBJECT) {
  204. return oldloc->lc_score == 2 || /* old var. can be eliminated */
  205. old_cost > global_addr_cost();
  206. }
  207. find_local(off_set(new),&nr,&ok);
  208. assert(ok);
  209. newloc = locals[nr];
  210. new_cost = local_addr_cost(off_set(new));
  211. return old_cost > new_cost ||
  212. (old_cost == new_cost && oldloc->lc_score < newloc->lc_score);
  213. }
  214. #ifdef TRACE
  215. /*********** TRACING ROUTINES ***********/
  216. static void pr_localtab()
  217. {
  218. short i;
  219. local_p lc;
  220. printf("LOCAL-TABLE (%d)\n\n",nrlocals);
  221. for (i = 1; i <= nrlocals; i++) {
  222. lc = locals[i];
  223. printf("LOCAL %d\n",i);
  224. printf(" offset= %ld\n",lc->lc_off);
  225. printf(" size= %d\n",lc->lc_size);
  226. printf(" flags= %d\n",lc->lc_flags);
  227. }
  228. }
  229. void pr_globals()
  230. {
  231. dblock_p d;
  232. obj_p obj;
  233. printf("GLOBALS (%d)\n\n",nrglobals);
  234. printf("ID GLOBNR\n");
  235. for (d = fdblock; d != (dblock_p) 0; d = d->d_next) {
  236. for (obj = d->d_objlist; obj != (obj_p) 0; obj = obj->o_next) {
  237. if (obj->o_globnr != 0) {
  238. printf("%d %d\n", obj->o_id,obj->o_globnr);
  239. }
  240. }
  241. }
  242. }
  243. extern char em_mnem[];
  244. static void pr_defs()
  245. {
  246. short i;
  247. line_p l;
  248. printf("DEF TABLE\n\n");
  249. for (i = 1; i <= nrexpldefs; i++) {
  250. l = defs[i];
  251. printf("%d %s ",EXPL_TO_DEFNR(i),
  252. &em_mnem[(INSTR(l)-sp_fmnem)*4]);
  253. switch(TYPE(l)) {
  254. case OPSHORT:
  255. printf("%d\n",SHORT(l));
  256. break;
  257. case OPOFFSET:
  258. printf("%ld\n",OFFSET(l));
  259. break;
  260. case OPOBJECT:
  261. printf("%d\n",OBJ(l)->o_id);
  262. break;
  263. default:
  264. assert(FALSE);
  265. }
  266. }
  267. }
  268. static void pr_set(char *name, short k, cset s, short n)
  269. {
  270. short i;
  271. printf("%s(%d) = {",name,k);
  272. for (i = 1; i <= n; i++) {
  273. if (Cis_elem(i,s)) {
  274. printf("%d ",i);
  275. }
  276. }
  277. printf ("}\n");
  278. }
  279. static void pr_blocks(proc_p p)
  280. {
  281. bblock_p b;
  282. short n;
  283. for (b = p->p_start; b != 0; b = b->b_next) {
  284. printf ("\n");
  285. n = b->b_id;
  286. pr_set("GEN",n,GEN(b),nrdefs);
  287. pr_set("KILL",n,KILL(b),nrdefs);
  288. pr_set("IN ",n,IN(b),nrdefs);
  289. pr_set("OUT",n,OUT(b),nrdefs);
  290. pr_set("CHGVARS",n,CHGVARS(b),nrvars);
  291. }
  292. }
  293. static void pr_copies()
  294. {
  295. short i;
  296. printf("\nCOPY TABLE\n\n");
  297. for (i = 1; i <= nrdefs; i++) {
  298. if (def_to_copynr[i] != 0) {
  299. printf("%d %d\n",i,def_to_copynr[i]);
  300. }
  301. }
  302. }
  303. static void pr_cblocks(proc_p p)
  304. {
  305. bblock_p b;
  306. short n;
  307. for (b = p->p_start; b != 0; b = b->b_next) {
  308. printf ("\n");
  309. n = b->b_id;
  310. pr_set("CGEN",n,C_GEN(b),nrcopies);
  311. pr_set("CKILL",n,C_KILL(b),nrcopies);
  312. pr_set("CIN ",n,C_IN(b),nrcopies);
  313. pr_set("COUT",n,C_OUT(b),nrcopies);
  314. }
  315. }
  316. /*********** END TRACING ********/
  317. #endif
  318. static void ud_analysis(proc_p p)
  319. {
  320. /* Perform use-definition analysis on procedure p */
  321. make_localtab(p); /* See for which local we'll keep ud-info */
  322. #ifdef TRACE
  323. pr_localtab();
  324. #endif
  325. nrvars = nrglobals + nrlocals;
  326. make_defs(p); /* Make a table of all useful definitions in p */
  327. #ifdef TRACE
  328. pr_defs();
  329. #endif
  330. nrdefs = nrexpldefs + nrvars; /* number of definitions */
  331. gen_sets(p); /* compute GEN(b), for every basic block b */
  332. kill_sets(p); /* compute KILL(b), for every basic block b */
  333. solve_equations(p); /* solve data flow equations for p */
  334. #ifdef TRACE
  335. pr_blocks(p);
  336. #endif
  337. }
  338. static void clean_maps()
  339. {
  340. local_p *p;
  341. cset *v;
  342. oldmap((short **)defs,nrexpldefs);
  343. for (p = &locals[1]; p <= &locals[nrlocals]; p++) {
  344. oldlocal(*p);
  345. }
  346. oldmap((short **)locals,nrlocals);
  347. for (v = &vardefs[1]; v <= &vardefs[nrvars]; v++) {
  348. Cdeleteset(*v);
  349. }
  350. oldmap((short **)vardefs,nrvars);
  351. }
  352. static bool try_optim(line_p l, bblock_p b)
  353. {
  354. /* Try copy propagation and constant propagation */
  355. line_p def;
  356. offset val;
  357. short defnr;
  358. if (is_use(l) && (def = unique_def(l,b,&defnr)) != (line_p) 0) {
  359. if (is_copy(def)) {
  360. if (value_retained(def,defnr,l,b) &&
  361. fold_is_desirable(l,PREV(def))) {
  362. fold_var(l,PREV(def),b);
  363. OUTVERBOSE("vp:variable folded in proc %d",
  364. curproc->p_id,0);
  365. Svariable++;
  366. return TRUE;
  367. }
  368. } else {
  369. if (value_known(def,&val)) {
  370. fold_const(l,b,val);
  371. OUTVERBOSE("vp:value folded in proc %d",
  372. curproc->p_id,0);
  373. Svalue++;
  374. return TRUE;
  375. }
  376. }
  377. }
  378. return FALSE;
  379. }
  380. void value_propagation(proc_p p)
  381. {
  382. /* Apply value propagation to procedure p */
  383. bool changes;
  384. bblock_p b;
  385. line_p l, next;
  386. changes = TRUE;
  387. /* If a statement like A := B is folded to A := constant,
  388. * new opportunities for constant folding may arise,
  389. * e.g. the value of A might be statically known too now.
  390. */
  391. while (changes) {
  392. changes = FALSE;
  393. for (b = p->p_start; b != (bblock_p) 0; b = b->b_next) {
  394. for (l = b->b_start; l != (line_p) 0; l = next) {
  395. next = l->l_next;
  396. if (try_optim(l,b)) {
  397. changes = TRUE;
  398. }
  399. }
  400. }
  401. }
  402. oldmap((short **)copies,nrcopies);
  403. oldtable((short **)def_to_copynr,nrdefs);
  404. }
  405. static void ud_extend(proc_p p)
  406. {
  407. /* Allocate extended data structures for Use Definition analysis */
  408. register bblock_p b;
  409. for (b = p->p_start; b != (bblock_p) 0; b = b->b_next) {
  410. b->b_extend = newudbx();
  411. }
  412. }
  413. static void ud_cleanup(proc_p p)
  414. {
  415. /* Deallocate extended data structures for Use Definition analysis */
  416. register bblock_p b;
  417. for (b = p->p_start; b != (bblock_p) 0; b = b->b_next) {
  418. Cdeleteset(GEN(b));
  419. Cdeleteset(IN(b));
  420. Cdeleteset(C_GEN(b));
  421. Cdeleteset(C_KILL(b));
  422. Cdeleteset(C_IN(b));
  423. Cdeleteset(C_OUT(b));
  424. Cdeleteset(CHGVARS(b));
  425. oldudbx(b->b_extend);
  426. }
  427. }
  428. static int ud_optimize(void *param)
  429. {
  430. proc_p p = (proc_p)param;
  431. if (IS_ENTERED_WITH_GTO(p)) return 0;
  432. ud_extend(p);
  433. locals = (local_p *) 0;
  434. vardefs = (cset *) 0;
  435. defs = (line_p *) 0;
  436. ud_analysis(p);
  437. copy_analysis(p);
  438. #ifdef TRACE
  439. pr_copies();
  440. pr_cblocks(p);
  441. #endif
  442. value_propagation(p);
  443. ud_cleanup(p);
  444. clean_maps();
  445. return 0;
  446. }
  447. main(argc,argv)
  448. int argc;
  449. char *argv[];
  450. {
  451. go(argc,argv,init_globals,ud_optimize,ud_machinit,no_action);
  452. report("values folded",Svalue);
  453. report("variables folded",Svariable);
  454. exit(0);
  455. }