il2_aux.c 15 KB

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