il2_aux.c 15 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693
  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 L I N E S U B S T I T U T I O N
  7. *
  8. * I L 2 _ A U X . C
  9. */
  10. #include <stdio.h>
  11. #include <em_spec.h>
  12. #include <em_mnem.h>
  13. #include "../share/types.h"
  14. #include "il.h"
  15. #include "../share/debug.h"
  16. #include "../share/alloc.h"
  17. #include "../share/global.h"
  18. #include "../share/lset.h"
  19. #include "il_aux.h"
  20. #include "il2_aux.h"
  21. #include "../share/get.h"
  22. #include "../share/cset.h"
  23. #include "../share/aux.h"
  24. #define USE_INDIR(p) (p->p_use->u_flags & UF_INDIR)
  25. #define OFTEN_USED(f) ((f->f_flags&FF_OFTENUSED) == FF_OFTENUSED)
  26. #define CHANGE_EXT(p) (Cnrelems(p->p_change->c_ext) > 0)
  27. #define NOT_INLINE(a) (a->ac_inl = FALSE)
  28. #define INLINE(a) (a->ac_inl = TRUE)
  29. #define CHANGED(p) p->p_flags2 |= PF_CHANGED
  30. #define IS_CHANGED(p) (p->p_flags2 & PF_CHANGED)
  31. void Sstat(proc_p proclist, long space);
  32. static bool match_pars(formal_p fm, actual_p act)
  33. {
  34. /* Check if every actual parameter has the same
  35. * size as its corresponding formal. If not, the
  36. * actual parameters should not be expanded in line.
  37. */
  38. while (act != (actual_p) 0) {
  39. if (fm == (formal_p) 0 || tsize(fm->f_type) != act->ac_size) {
  40. return FALSE;
  41. }
  42. act = act->ac_next;
  43. fm = fm->f_next;
  44. }
  45. return (fm == (formal_p) 0 ? TRUE : FALSE);
  46. }
  47. static bool change_act(proc_p p, actual_p act)
  48. {
  49. /* See if a call to p migth change any of the
  50. * operands of the actual parameter expression.
  51. * If the parameter is to be expanded in line,
  52. * we must be sure its value does not depend
  53. * on the point in the program where it is
  54. * evaluated.
  55. */
  56. line_p l;
  57. for (l = act->ac_exp; l != (line_p) 0; l = l->l_next) {
  58. switch(INSTR(l)) {
  59. case op_lil:
  60. case op_lof:
  61. case op_loi:
  62. case op_los:
  63. case op_ldf:
  64. return TRUE;
  65. /* assume worst case */
  66. case op_lol:
  67. case op_ldl:
  68. if (CHANGE_INDIR(p)) {
  69. return TRUE;
  70. }
  71. break;
  72. case op_loe:
  73. case op_lde:
  74. if (CHANGE_INDIR(p) || CHANGE_EXT(p)) {
  75. return TRUE;
  76. }
  77. break;
  78. }
  79. }
  80. return FALSE;
  81. }
  82. static bool is_simple(line_p expr)
  83. {
  84. /* See if expr is something simple, i.e. a constant or
  85. * a variable. So the expression must consist of
  86. * only one instruction.
  87. */
  88. if (expr->l_next == (line_p) 0) {
  89. switch(INSTR(expr)) {
  90. case op_loc:
  91. case op_ldc:
  92. case op_lol:
  93. case op_ldl:
  94. case op_loe:
  95. case op_lde:
  96. return TRUE;
  97. }
  98. }
  99. return FALSE;
  100. }
  101. static bool too_expensive(formal_p fm, actual_p act)
  102. {
  103. /* If the formal parameter is used often and the
  104. * actual parameter is not something simple
  105. * (i.e. an expression, not a constant or variable)
  106. * it may be too expensive too expand the parameter
  107. * in line.
  108. */
  109. return (OFTEN_USED(fm) && !is_simple(act->ac_exp));
  110. }
  111. bool anal_params(call_p c)
  112. {
  113. /* Determine which of the actual parameters of a
  114. * call may be expanded in line.
  115. */
  116. proc_p p;
  117. actual_p act;
  118. formal_p form;
  119. int inlpars = 0;
  120. p = c->cl_proc; /* the called procedure */
  121. if (!match_pars(p->P_FORMALS, c->cl_actuals)) return FALSE;
  122. if (!INLINE_PARS(p)) {
  123. for (act = c->cl_actuals; act != (actual_p) 0;
  124. act = act->ac_next) {
  125. NOT_INLINE(act);
  126. }
  127. return TRUE; /* "# of inline pars." field in cl_flags remains 0 */
  128. }
  129. for (act = c->cl_actuals, form = p->P_FORMALS; act != (actual_p) 0;
  130. act = act->ac_next, form = form->f_next) {
  131. if (form->f_flags & FF_BAD ||
  132. change_act(p,act) || too_expensive(form,act)) {
  133. NOT_INLINE(act);
  134. } else {
  135. INLINE(act);
  136. inlpars++;
  137. }
  138. }
  139. if (inlpars > 15) inlpars = 15; /* We've only got 4 bits! */
  140. c->cl_flags |= inlpars; /* number of inline parameters */
  141. return TRUE;
  142. }
  143. static short space_saved(call_p c)
  144. {
  145. /* When a call gets expanded in line, the total size of the
  146. * code usually gets incremented, because we have to
  147. * duplicate the text of the called routine. However, we save
  148. * ourselves a CAL instruction and possibly anASP instruction
  149. * (if the called procedure has parameters). Moreover, if we
  150. * can put some parameters in line, we don't have to push
  151. * their results on the stack before doing the call, so we
  152. * save some code here too. The routine estimates the amount of
  153. * code saved, expressed in number of EM instructions.
  154. */
  155. return (1 + (c->cl_flags & CLF_INLPARS) + (c->cl_proc->p_nrformals>0));
  156. }
  157. static short param_score(call_p c)
  158. {
  159. /* If a call has an inline parameter that is a constant,
  160. * chances are high that other optimization techniques
  161. * can do further optimizations, especially if the constant
  162. * happens to be "0". So the call gets extra points for this.
  163. */
  164. register actual_p act;
  165. line_p l;
  166. short score = 0;
  167. for (act = c->cl_actuals; act != (actual_p) 0; act = act->ac_next) {
  168. if (act->ac_inl) {
  169. l = act->ac_exp;
  170. if (l->l_next == (line_p) 0 &&
  171. (INSTR(l) == op_loc || INSTR(l) == op_ldc)) {
  172. score += (off_set(l) == (offset) 0 ? 2 : 1);
  173. /* 0's count for two! */
  174. }
  175. }
  176. }
  177. return score;
  178. }
  179. void assign_ratio(call_p c)
  180. {
  181. /* This routine is one of the most important ones
  182. * of the inline substitution phase. It assigns a number
  183. * (a 'ratio') to a call, indicating how desirable
  184. * it is to expand the call in line.
  185. * Currently, a very simplified straightforward heuristic
  186. * is used.
  187. */
  188. short ll, loopfact, ratio;
  189. ll = c->cl_proc->P_SIZE - space_saved(c);
  190. if (ll <= 0) ll = 1;
  191. ratio = 1000 / ll;
  192. if (ratio == 0) ratio = 1;
  193. /* Add points if the called procedure falls through
  194. * it's end (no BRA needed) or has formal parameters
  195. * (ASP can be deleted).
  196. */
  197. if (c->cl_proc->p_flags2 & PF_FALLTHROUGH) {
  198. ratio += 10;
  199. }
  200. if (c->cl_proc->p_nrformals > 0) {
  201. ratio += 10;
  202. }
  203. if (c->cl_caller->p_localbytes == 0) {
  204. ratio -= 10;
  205. }
  206. ratio += (10 *param_score(c));
  207. /* Extra points for constants as parameters */
  208. if (ratio <= 0) ratio = 1;
  209. ll = c->cl_looplevel+1;
  210. if (ll == 1 && !IS_CALLED_IN_LOOP(c->cl_caller)) ll = 0;
  211. /* If the call is not in a loop and the called proc. is never called
  212. * in a loop, ll is set to 0.
  213. */
  214. loopfact = (ll > 3 ? 10 : ll*ll);
  215. ratio *= loopfact;
  216. if (c->cl_flags & CLF_FIRM) {
  217. ratio = 2*ratio;
  218. }
  219. c->cl_ratio = ratio;
  220. }
  221. call_p abstract(call_p c)
  222. {
  223. /* Abstract information from the call that is essential
  224. * for choosing the calls that will be expanded.
  225. * Put the information is an 'abstracted call'.
  226. */
  227. call_p a;
  228. a = newcall();
  229. a->cl_caller = c->cl_caller;
  230. a->cl_id = c->cl_id;
  231. a->cl_proc = c->cl_proc;
  232. a->cl_looplevel = c->cl_looplevel;
  233. a->cl_ratio = c->cl_ratio;
  234. a->cl_flags = c->cl_flags;
  235. return a;
  236. }
  237. static void adjust_counts(proc_p callee, FILE *ccf)
  238. {
  239. /* A call to callee is expanded in line;
  240. * the text of callee is not removed, so
  241. * every proc called by callee gets its
  242. * P_NRCALLED field incremented.
  243. */
  244. calcnt_p cc, head;
  245. head = getcc(ccf,callee); /* get calcnt info of called proc */
  246. for (cc = head; cc != (calcnt_p) 0; cc = cc->cc_next) {
  247. cc->cc_proc->P_NRCALLED += cc->cc_count;
  248. }
  249. remcc(head); /* remove calcnt info */
  250. }
  251. static bool is_dispensable(proc_p callee, FILE *ccf)
  252. {
  253. /* A call to callee is expanded in line.
  254. * Decrement its P_NRCALLED field and see if
  255. * it can now be removed because it is no
  256. * longer called. Procedures that ever have
  257. * their address taken (via LPI) will never
  258. * be removed, as they might be called indirectly.
  259. */
  260. if ((--callee->P_NRCALLED) == 0 &&
  261. (complete_program || (callee->p_flags1 & PF_EXTERNAL) == 0) &&
  262. (callee->p_flags1 & PF_LPI) == 0) {
  263. DISPENSABLE(callee);
  264. OUTVERBOSE("dispensable: procedure %d can be removed",callee->p_id);
  265. #ifdef VERBOSE
  266. Spremoved++;
  267. #endif
  268. return TRUE;
  269. } else {
  270. adjust_counts(callee,ccf);
  271. return FALSE;
  272. }
  273. }
  274. static call_p nested_calls(call_p a)
  275. {
  276. /* Get a list of all calls that will appear in the
  277. * EM text if the call 'a' is expanded in line.
  278. * These are the calls in the P_CALS list of the
  279. * called procedure.
  280. */
  281. call_p c, cp, head, *cpp;
  282. head = (call_p) 0;
  283. cpp = &head;
  284. for (c = a->cl_proc->P_CALS; c != (call_p) 0; c = c->cl_cdr) {
  285. cp = abstract(c);
  286. cp->cl_looplevel += a->cl_looplevel;
  287. cp->cl_flags = (byte) 0;
  288. if (a->cl_flags & CLF_FIRM) {
  289. cp->cl_flags |= CLF_FIRM;
  290. }
  291. assign_ratio(cp);
  292. *cpp = cp;
  293. cpp = &cp->cl_cdr;
  294. }
  295. return head;
  296. }
  297. static call_p find_origin(call_p c)
  298. {
  299. /* c is a nested call. Find the original call.
  300. * This origional must be in the P_CALS list
  301. * of the calling procedure.
  302. */
  303. register call_p x;
  304. for (x = c->cl_caller->P_CALS; x != (call_p) 0; x = x->cl_cdr) {
  305. if (x->cl_id == c->cl_id) return x;
  306. }
  307. assert(FALSE);
  308. /* NOTREACHED */
  309. return 0;
  310. }
  311. static void selected(call_p a)
  312. {
  313. /* The call a is selected for in line expansion.
  314. * Mark the call as being selected and get the
  315. * calls nested in it; these will be candidates
  316. * too now.
  317. */
  318. SELECTED(a);
  319. EVER_EXPANDED(find_origin(a));
  320. a->cl_car = nested_calls(a);
  321. }
  322. static void compare(call_p x, call_p *best, long space)
  323. {
  324. /* See if x is better than the current best choice */
  325. if (x != (call_p) 0 && !IS_CHANGED(x->cl_proc) &&
  326. x->cl_proc->P_SIZE - space_saved(x) <= space) {
  327. if ((*best == (call_p) 0 && x->cl_ratio != 0) ||
  328. (*best != (call_p) 0 && x->cl_ratio > (*best)->cl_ratio )) {
  329. *best = x;
  330. }
  331. }
  332. }
  333. static call_p best_one(call_p list, long space)
  334. {
  335. /* Find the best candidate of the list
  336. * that has not already been selected. The
  337. * candidate must fit in the given space.
  338. * We look in the cdr as well as in the car
  339. * direction.
  340. */
  341. call_p best = (call_p) 0;
  342. call_p c;
  343. for (c = list; c != (call_p) 0; c = c->cl_cdr) {
  344. if (IS_SELECTED(c)) {
  345. compare(best_one(c->cl_car,space),&best,space);
  346. } else {
  347. compare(c,&best,space);
  348. }
  349. }
  350. return best;
  351. }
  352. static void singles(call_p cals)
  353. {
  354. /* If a procedure is only called once, this call
  355. * will be expanded in line, because it costs
  356. * no extra space.
  357. */
  358. call_p c;
  359. for (c = cals; c != (call_p) 0; c = c->cl_cdr) {
  360. if (IS_SELECTED(c)) {
  361. singles(c->cl_car);
  362. } else {
  363. if (c->cl_proc->P_NRCALLED == 1 &&
  364. !IS_CHANGED(c->cl_proc) &&
  365. (complete_program ||
  366. (c->cl_proc->p_flags1 & PF_EXTERNAL) == 0) &&
  367. (c->cl_proc->p_flags1 & PF_LPI) == 0) {
  368. c->cl_proc->P_NRCALLED = 0;
  369. SELECTED(c);
  370. EVER_EXPANDED(find_origin(c));
  371. DISPENSABLE(c->cl_proc);
  372. CHANGED(c->cl_caller);
  373. OUTVERBOSE("singles: procedure %d can be removed",
  374. c->cl_proc->p_id);
  375. #ifdef VERBOSE
  376. Spremoved++;
  377. #endif
  378. }
  379. }
  380. }
  381. }
  382. static void single_calls(proc_p proclist)
  383. {
  384. proc_p p;
  385. for (p = proclist; p != (proc_p) 0; p = p->p_next) {
  386. if (!BIG_CALLER(p) && !IS_DISPENSABLE(p)) {
  387. /* Calls appearing in a large procedure or in
  388. * a procedure that was already eliminated
  389. * are not considered.
  390. */
  391. singles(p->P_CALS);
  392. }
  393. }
  394. }
  395. void select_calls(proc_p proclist, FILE *ccf, long space)
  396. {
  397. /* Select all calls that are to be expanded in line. */
  398. proc_p p,chp;
  399. call_p best, x;
  400. for (;;) {
  401. best = (call_p) 0;
  402. chp = (proc_p) 0; /* the changed procedure */
  403. for (p = proclist; p != (proc_p) 0; p = p->p_next) {
  404. if (!BIG_CALLER(p) && !IS_DISPENSABLE(p)) {
  405. /* Calls appearing in a large procedure or in
  406. * a procedure that was already eliminated
  407. * are not considered.
  408. */
  409. x = best_one(p->P_CALS,space);
  410. compare(x,&best,space);
  411. if (x == best) chp = p;
  412. }
  413. }
  414. if (best == (call_p) 0) break;
  415. if (!is_dispensable(best->cl_proc,ccf)) {
  416. space -= (best->cl_proc->P_SIZE - space_saved(best));
  417. }
  418. else space += space_saved(best);
  419. #ifdef VERBOSE
  420. if (verbose_flag) fprintf(stderr, "space left: %ld\n", space);
  421. #endif
  422. selected(best);
  423. CHANGED(chp);
  424. }
  425. single_calls(proclist);
  426. #ifdef VERBOSE
  427. Sstat(proclist,space);
  428. #endif
  429. }
  430. static void nonnested_calls(FILE *cfile)
  431. {
  432. register call_p c,a;
  433. while((c = getcall(cfile)) != (call_p) 0) {
  434. /* find the call in the call list of the caller */
  435. for (a = c->cl_caller->P_CALS;
  436. a != NULL && c->cl_id != a->cl_id; ) a = a->cl_cdr;
  437. assert(a != NULL && a->cl_proc == c->cl_proc);
  438. if (IS_EVER_EXPANDED(a)) {
  439. a->cl_actuals = c->cl_actuals;
  440. c->cl_actuals = (actual_p) 0;
  441. }
  442. rem_call(c);
  443. }
  444. }
  445. static void copy_pars(call_p src, call_p dest)
  446. {
  447. /* Copy the actual parameters of src to dest. */
  448. actual_p as,ad, *app;
  449. app = &dest->cl_actuals;
  450. for (as = src->cl_actuals; as != (actual_p) 0; as = as->ac_next) {
  451. ad = newactual();
  452. ad->ac_exp = copy_expr(as->ac_exp);
  453. ad->ac_size = as->ac_size;
  454. ad->ac_inl = as->ac_inl;
  455. *app = ad;
  456. app = &ad->ac_next;
  457. }
  458. }
  459. static void nest_pars(call_p cals)
  460. {
  461. /* Recursive auxiliary procedure of add_actuals. */
  462. call_p c,org;
  463. for (c = cals; c != (call_p) 0; c = c->cl_cdr) {
  464. if (IS_SELECTED(c)) {
  465. org = find_origin(c);
  466. copy_pars(org,c);
  467. nest_pars(c->cl_car);
  468. }
  469. }
  470. }
  471. void add_actuals(proc_p proclist, FILE *cfile)
  472. {
  473. /* Fetch the actual parameters of all selected calls.
  474. * For all non-nested calls (i.e. those calls that
  475. * appeared originally in the EM text), we get the
  476. * parameters from the cal-file.
  477. * For nested calls (i.e. calls
  478. * that are a result of in line substitution) we
  479. * get the parameters from the original call.
  480. */
  481. proc_p p;
  482. call_p a;
  483. nonnested_calls(cfile);
  484. for (p = proclist; p != (proc_p) 0; p = p->p_next) {
  485. for (a = p->P_CALS; a != (call_p) 0; a = a->cl_cdr) {
  486. nest_pars(a->cl_car);
  487. }
  488. }
  489. }
  490. static void clean(call_p *cals)
  491. {
  492. call_p c,next,*cpp;
  493. /* Recursive auxiliary routine of cleancals */
  494. cpp = cals;
  495. for (c = *cpp; c != (call_p) 0; c = next) {
  496. next = c->cl_cdr;
  497. if (IS_SELECTED(c)) {
  498. clean(&c->cl_car);
  499. cpp = &c->cl_cdr;
  500. } else {
  501. assert(c->cl_car == (call_p) 0);
  502. oldcall(c);
  503. *cpp = next;
  504. }
  505. }
  506. }
  507. void cleancals(proc_p proclist)
  508. {
  509. /* Remove all calls in the P_CALS list of p
  510. * that were not selected for in line expansion.
  511. */
  512. register proc_p p;
  513. for (p = proclist; p != (proc_p) 0; p = p->p_next) {
  514. clean(&p->P_CALS);
  515. }
  516. }
  517. void append_abstract(call_p a, proc_p p)
  518. {
  519. /* Append an abstract of a call-descriptor to
  520. * the call-list of procedure p.
  521. */
  522. call_p c;
  523. if (p->P_CALS == (call_p) 0) {
  524. p->P_CALS = a;
  525. } else {
  526. for (c = p->P_CALS; c->cl_cdr != (call_p) 0; c = c->cl_cdr);
  527. c->cl_cdr = a;
  528. }
  529. }
  530. #ifdef VERBOSE
  531. /* At the end, we traverse the entire call-list, to see why the
  532. * remaining calls were not expanded inline.
  533. */
  534. void Sstatist(call_p list, long space)
  535. {
  536. call_p c;
  537. for (c = list; c != (call_p) 0; c = c->cl_cdr) {
  538. if (IS_SELECTED(c)) {
  539. Sstatist(c->cl_car,space);
  540. } else {
  541. if (IS_CHANGED(c->cl_proc)) Schangedcallee++;
  542. else if (BIG_PROC(c->cl_proc)) Sbigcallee++;
  543. else if (c->cl_proc->P_SIZE > space) Sspace++;
  544. else if (c->cl_ratio == 0) Szeroratio++;
  545. else assert(FALSE);
  546. }
  547. }
  548. }
  549. void Sstat(proc_p proclist, long space)
  550. {
  551. proc_p p;
  552. for (p = proclist; p != (proc_p) 0; p = p->p_next) {
  553. if (BIG_CALLER(p)) Sbig_caller++;
  554. else if (IS_DISPENSABLE(p)) Sdispensable++;
  555. else Sstatist(p->P_CALS,space);
  556. }
  557. }
  558. #endif