util/ego/il/il2_aux.c

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