util/ego/ud/ud.c

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