il2_aux.c 15 KB

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