util/ego/lv/lv.c

   1 /* $Id: lv.c,v 1.10 1994/06/24 10:26:28 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
   7 /* L I V E   V A R I A B L E S   A N A L Y S I S */
   8
   9 #include <stdio.h>
  10 #include <em_mnem.h>
  11 #include <em_pseu.h>
  12 #include <em_spec.h>
  13 #include <em_mes.h>
  14 #include <em_ego.h>
  15 #include "../share/types.h"
  16 #include "lv.h"
  17 #include "../share/debug.h"
  18 #include "../share/global.h"
  19 #include "../share/lset.h"
  20 #include "../share/cset.h"
  21 #include "../share/def.h"
  22 #include "../share/files.h"
  23 #include "../share/alloc.h"
  24 #include "../share/map.h"
  25 #include "../share/get.h"
  26 #include "../share/put.h"
  27 #include "../share/aux.h"
  28 #include "../share/init_glob.h"
  29 #include "../share/locals.h"
  30 #include "../share/go.h"
  31 #include "../share/parser.h"
  32
  33 #define newlvbx()       (bext_p) newstruct(bext_lv)
  34 #define oldlvbx(x)      oldstruct(bext_lv,x)
  35
  36
  37 short nrglobals;
  38 short nrvars;
  39
  40 STATIC int Slv;
  41 STATIC bool mesgflag = FALSE;  /* Suppress generation of live/dead info */
  42
  43
  44 STATIC clean_up()
  45 {
  46         local_p *p;
  47
  48         for (p = &locals[1]; p <= &locals[nrlocals]; p++) {
  49                 oldlocal(*p);
  50         }
  51         oldmap(locals,nrlocals);
  52 }
  53
  54
  55
  56 STATIC bool is_dir_use(l)
  57         line_p l;
  58 {
  59         /* See if l is a direct use of some variable
  60          * (i.e. not through a pointer). A LIL is a
  61          * direct use of some pointer variable
  62          * (and an indirect use of some other variable).
  63          * A SIL is also a direct use.
  64          * A LOI, however, is not an direct use of a variable.
  65          * An an increment/decrement instruction is regarded
  66          * as a use here, and not as a definition, as the
  67          * variable is first used and than defined.
  68          */
  69
  70         switch(INSTR(l)) {
  71                 case op_dee:
  72                 case op_del:
  73                 case op_ine:
  74                 case op_inl:
  75                 case op_lde:
  76                 case op_ldl:
  77                 case op_lil:
  78                 case op_loe:
  79                 case op_lol:
  80                 case op_sil:
  81                         return TRUE;
  82                 default:
  83                         return FALSE;
  84         }
  85         /* NOTREACHED */
  86 }
  87
  88
  89
  90 STATIC bool is_indir_use(l)
  91         line_p l;
  92 {
  93         /* See if instruction l uses some variable(s) indirectly,
  94          * i.e. through a pointer or via a procedure call.
  95          */
  96
  97         switch(INSTR(l)) {
  98                 case op_blm:
  99                 case op_bls:
 100                 case op_cai:
 101                 case op_cal:
 102                 case op_lar:
 103                 case op_ldf:
 104                 case op_lil:
 105                 case op_lof:
 106                 case op_loi:
 107                 case op_los:
 108                 case op_mon:
 109                         return TRUE;
 110                 default:
 111                         return FALSE;
 112         }
 113         /* NOTREACHED */
 114 }
 115
 116
 117
 118 STATIC bool is_def(l)
 119         line_p l;
 120 {
 121         /* See if l does a direct definition */
 122
 123         switch(INSTR(l)) {
 124                 case op_sde:
 125                 case op_sdl:
 126                 case op_ste:
 127                 case op_stl:
 128                 case op_zre:
 129                 case op_zrl:
 130                         return TRUE;
 131                 default:
 132                         return FALSE;
 133         }
 134         /* NOTREACHED */
 135 }
 136
 137
 138 STATIC def_use(p)
 139         proc_p p;
 140 {
 141         /* Compute DEF(b) and USE(b), for every basic block b
 142          * of procedure p. DEF(b) contains the variables that
 143          * are certain to be defined (assigned) in b
 144          * before being used. USE(b) contains the variables
 145          * that may be used in b, before being defined.
 146          * (Note that uncertainty arises in the presence of
 147          *  pointers and procedure calls).
 148          * We compute these sets, by scanning the text of
 149          * the basic block from beginning till end.
 150          */
 151
 152         register bblock_p b;
 153         register line_p l;
 154         short v;
 155         bool found;
 156         cset all_ind_uses;
 157
 158         all_ind_uses = Cempty_set(nrvars);
 159         for (v = 1; v < nrlocals; v++) {
 160                 if (!IS_REGVAR(locals[v])) {
 161                         Cadd(LOC_TO_VARNR(v),&all_ind_uses);
 162                 }
 163         }
 164         for (b = p->p_start; b != (bblock_p) 0; b = b->b_next) {
 165                 USE(b) = Cempty_set(nrvars);
 166                 DEF(b) = Cempty_set(nrvars);
 167                 for (l = b->b_start; l != (line_p) 0; l = l->l_next) {
 168                         if (is_def(l)) {
 169                                 /* An direct definition (i.e. not
 170                                  * through a pointer).
 171                                  */
 172                                 var_nr(l,&v,&found);
 173                                 if (found && !Cis_elem(v,USE(b))) {
 174                                         /* We do maintain live-dead info
 175                                          * for this variable, and it was
 176                                          * not used earlier in b.
 177                                          */
 178                                         Cadd(v, &DEF(b));
 179                                 }
 180                         } else {
 181                                 if (is_dir_use(l)) {
 182                                         var_nr(l,&v,&found);
 183                                         if (found && !Cis_elem(v,DEF(b))) {
 184                                                 Cadd(v, &USE(b));
 185                                         }
 186                                 }
 187                                 if (is_indir_use(l)) {
 188                                         /* Add variable that may be used
 189                                          * by l to USE(b).
 190                                          */
 191                                         Cjoin(all_ind_uses,&USE(b));
 192                                 }
 193                         }
 194                 }
 195         }
 196         Cdeleteset(all_ind_uses);
 197 }
 198
 199
 200
 201 STATIC unite_ins(bbset,setp)
 202         lset bbset;
 203         cset *setp;
 204 {
 205         /* Take the union of L_IN(b), for all b in bbset,
 206          * and put the result in setp.
 207          */
 208
 209         Lindex i;
 210
 211         Cclear_set(setp);
 212         for (i = Lfirst(bbset); i != (Lindex) 0; i = Lnext(i,bbset)) {
 213                 Cjoin(L_IN((bblock_p) Lelem(i)), setp);
 214         }
 215 }
 216
 217
 218
 219 STATIC solve_lv(p)
 220         proc_p p;
 221 {
 222         /* Solve the data flow equations for Live Variables,
 223          * for procedure p. These equations are:
 224          *  (1)   IN[b] = OUT[b] - DEF[b] + USE[b]
 225          *  (2)   OUT(b) = IN(s1) + ... + IN(sn) ;
 226          *        where SUCC(b) = {s1, ... , sn}
 227          */
 228
 229         register bblock_p b;
 230         cset newout = Cempty_set(nrvars);
 231         bool change = TRUE;
 232
 233         for (b = p->p_start; b != (bblock_p) 0; b = b->b_next) {
 234                 L_IN(b) = Cempty_set(nrvars);
 235                 Ccopy_set(USE(b), &L_IN(b));
 236                 L_OUT(b) = Cempty_set(nrvars);
 237         }
 238         while (change) {
 239                 change = FALSE;
 240                 for (b = p->p_start; b != (bblock_p) 0; b = b->b_next) {
 241                         unite_ins(b->b_succ,&newout);
 242                         if (!Cequal(newout,L_OUT(b))) {
 243                                 change = TRUE;
 244                                 Ccopy_set(newout, &L_OUT(b));
 245                                 Ccopy_set(newout, &L_IN(b));
 246                                 Csubtract(DEF(b), &L_IN(b));
 247                                 Cjoin(USE(b), &L_IN(b));
 248                         }
 249                 }
 250         }
 251         Cdeleteset(newout);
 252 }
 253
 254
 255 STATIC live_variables_analysis(p)
 256         proc_p p;
 257 {
 258         make_localtab(p);
 259         nrvars = nrglobals + nrlocals;
 260         def_use(p);
 261         solve_lv(p);
 262 }
 263
 264
 265 STATIC init_live_dead(b)
 266         bblock_p b;
 267 {
 268         /* For every register variable, see if it is
 269          * live or dead at the end of b.
 270          */
 271
 272         register short v;
 273         local_p loc;
 274
 275         for (v = 1; v <= nrlocals; v++) {
 276                 loc = locals[v];
 277                 if (IS_REGVAR(loc) && Cis_elem(LOC_TO_VARNR(v),L_OUT(b))) {
 278                         LIVE(loc);
 279                 } else {
 280                         DEAD(loc);
 281                 }
 282         }
 283 }
 284
 285
 286
 287 STATIC line_p make_mesg(mesg,loc)
 288         short mesg;
 289         local_p loc;
 290 {
 291         /* Create a line for a message stating that
 292          * local variable loc is live/dead. This message
 293          * looks like: "mes ms_ego,ego_live,off,size" or
 294          * "mes ms_ego,ego_dead,off,size".
 295          */
 296
 297         line_p l = newline(OPLIST);
 298         register arg_p ap;
 299
 300         l->l_instr = ps_mes;
 301         ap = ARG(l) = newarg(ARGOFF);
 302         ap->a_a.a_offset = ms_ego;
 303         ap = ap->a_next = newarg(ARGOFF);
 304         ap->a_a.a_offset = mesg;
 305         ap = ap->a_next = newarg(ARGOFF);
 306         ap->a_a.a_offset = loc->lc_off;
 307         ap = ap->a_next = newarg(ARGOFF);
 308         ap->a_a.a_offset = loc->lc_size;
 309         return l;
 310 }
 311
 312
 313
 314 STATIC app_block();
 315 STATIC block_entry(b,prev)
 316         bblock_p b,prev;
 317 {
 318         short v,vn;
 319         local_p loc;
 320         bool was_live, is_live;
 321
 322         /* Generate a live/dead message for every register variable that
 323          * was live at the end of prev, but dead at the beginning of b,
 324          * or v.v. If prev = 0 (i.e. begin of procedure), parameters were
 325          * live, normal local variables were dead.
 326          */
 327
 328         for (v = 1; v <= nrlocals; v++) {
 329                 loc = locals[v];
 330                 if (IS_REGVAR(loc)) {
 331                         vn = LOC_TO_VARNR(v);
 332                         if (prev == (bblock_p) 0) {
 333                                 was_live = loc->lc_off >= 0;
 334                         } else {
 335                                 was_live = Cis_elem(vn,L_OUT(prev));
 336                         }
 337                         is_live = Cis_elem(vn,L_IN(b));
 338                         if (was_live != is_live) {
 339                                 app_block(make_mesg((is_live?ego_live:ego_dead),loc),b);
 340                         }
 341                 }
 342         }
 343 }
 344
 345
 346
 347 STATIC app_block(l,b)
 348         line_p l;
 349         bblock_p b;
 350 {
 351         line_p x = b->b_start;
 352
 353         if (x != (line_p) 0 && INSTR(x) == ps_pro) {
 354                 /* start of procedure; append after pro pseudo ! */
 355                 if ((l->l_next = x->l_next) != (line_p) 0) {
 356                         PREV(l->l_next) = l;
 357                 }
 358                 x->l_next = l;
 359                 PREV(l) = x;
 360         } else {
 361                 if ((l->l_next = x) != (line_p) 0) {
 362                         PREV(l->l_next) = l;
 363                 }
 364                 b->b_start = l;
 365                 PREV(l) = (line_p) 0;
 366         }
 367 }
 368
 369
 370
 371 STATIC definition(l,useless_out,v_out,mesgflag)
 372         line_p l;
 373         bool *useless_out;
 374         short *v_out;
 375         bool mesgflag;
 376 {
 377         /* Process a definition. If the defined (register-) variable
 378          * is live after 'l', then create a live-message and put
 379          * it after 'l'.
 380          */
 381
 382         short v;
 383         bool found;
 384         local_p loc;
 385
 386         *useless_out = FALSE;
 387         var_nr(l,&v,&found);
 388         if (found && IS_LOCAL(v)) {
 389                 *v_out = v;
 390                 loc = locals[TO_LOCAL(v)];
 391                 if (IS_REGVAR(loc)) {
 392                         /*      Tricky stuff here. Make sure that a variable
 393                                 that is assigned to is alive, at least for
 394                                 a very very short time. Otherwize, the
 395                                 register allocation pass might think that it
 396                                 is never alive, and (incorrectly) use the
 397                                 same register for this variable as for
 398                                 another variable, that is alive at this point.
 399                                 If this variable is dead after the assignment,
 400                                 the two messages (ego_live, ego_dead) are right
 401                                 after each other. Luckily, this IS an interval.
 402                         */
 403                         if (!mesgflag) {
 404                                 appnd_line(make_mesg(ego_live,loc), l);
 405                                 l = l->l_next;
 406                         }
 407                         if (IS_LIVE(loc)) {
 408                                 DEAD(loc);
 409                         } else {
 410                                 if (!mesgflag) {
 411                                         appnd_line(make_mesg(ego_dead, loc), l);
 412                                 }
 413                                 *useless_out = TRUE;
 414                         }
 415                 }
 416         }
 417 }
 418
 419
 420
 421
 422 STATIC use(l,mesgflag)
 423         line_p l;
 424         bool mesgflag;
 425 {
 426         /* Process a use. If the defined (register-) variable
 427          * is dead after 'l', then create a dead-message and put
 428          * it after 'l'.
 429          */
 430
 431         short v;
 432         bool found;
 433         local_p loc;
 434
 435         var_nr(l,&v,&found);
 436         if (found && IS_LOCAL(v)) {
 437                 loc = locals[TO_LOCAL(v)];
 438                 if (IS_REGVAR(loc) && IS_DEAD(loc)) {
 439                         if (!mesgflag) {
 440                                 appnd_line(make_mesg(ego_dead,loc), l);
 441                         }
 442                         LIVE(loc);
 443                 }
 444         }
 445 }
 446
 447
 448
 449 STATIC nothing() { }  /* No action to be undertaken at level 0 of parser */
 450
 451 STATIC rem_code(l1,l2,b)
 452         line_p l1,l2;
 453         bblock_p b;
 454 {
 455         line_p l,x,y,next;
 456
 457         x = PREV(l1);
 458         y = l2->l_next;
 459         for (l = l1; l != l2; l = next) {
 460                 next = l->l_next;
 461                 oldline(l);
 462         }
 463         if (x == (line_p) 0) {
 464                 b->b_start = y;
 465         } else {
 466                 x->l_next = y;
 467         }
 468         if (y != (line_p) 0) {
 469                 PREV(y) = x;
 470         }
 471 }
 472
 473
 474
 475
 476 #define SIZE(v) ((offset) locals[TO_LOCAL(v)]->lc_size)
 477
 478
 479
 480
 481 lv_mesg(p,mesgflag)
 482         proc_p p;
 483         bool mesgflag;
 484 {
 485         /* Create live/dead messages for every possible register
 486          * variable of p. A dead-message is put after a "use" of
 487          * such a variable, if the variable becomes dead just
 488          * after the use (i.e. this was its last use).
 489          * A live message is put after a "definition" of such
 490          * a variable, if the variable becomes live just
 491          * after the definition (which will usually be the case).
 492          * We traverse every basic block b of p from the last
 493          * instruction of b backwards to the beginning of b.
 494          * Initially, all variables that are dead at the end
 495          * of b are marked dead. All others are marked live.
 496          * If we come accross a definition of a variable X that
 497          * was marked live, we put a live-message after the
 498          * definition and mark X dead.
 499          * If we come accross a use of a variable X that
 500          * was marked dead, we put a dead-message after the
 501          * use and mark X live.
 502          * So at any point, the mark of X tells whether X is
 503          * live or dead immediately before (!) that point.
 504          * We also generate a message at the start of a basic block
 505          * for every variable that was live at the end of the (textually)
 506          * previous block, but dead at the entry of this block, or v.v.
 507          * On the fly, useless assignments are removed.
 508          */
 509
 510         register bblock_p b;
 511         register line_p l;
 512         line_p lnp, prev;
 513         bblock_p prevb = (bblock_p) 0;
 514         short v;
 515         bool useless;
 516
 517         for (b = p->p_start; b != (bblock_p) 0; b = b->b_next) {
 518                 block_entry(b,prevb); /* generate message at head of block */
 519                 prevb = b;
 520                 if (!mesgflag) {
 521                         init_live_dead(b);
 522                 }
 523                 for (l = last_instr(b); l != (line_p) 0; l = prev) {
 524                         /* traverse backwards! */
 525                         prev = PREV(l);
 526                         if (is_def(l)) {
 527                                 definition(l,&useless,&v,mesgflag);
 528                                 if (useless &&   /* assignment to dead var. */
 529                                     parse(prev,SIZE(v),&lnp,0,nothing)) {
 530                                         /* The code "VAR := expression" can
 531                                          * be removed. 'l' is the "STL VAR",
 532                                          * lnp is the beginning of the EM code
 533                                          * for the expression.
 534                                          */
 535                                         prev = PREV(lnp);
 536                                         rem_code(lnp,l,b);
 537 OUTVERBOSE("useless assignment ,proc %d,local %d", curproc->p_id,
 538   (int) locals[TO_LOCAL(v)]->lc_off);
 539                                         Slv++;
 540                                 }
 541                                 else {
 542                                 }
 543                         } else {
 544                                 if (is_dir_use(l))  {
 545                                         use(l,mesgflag);
 546                                 }
 547                         }
 548                 }
 549         }
 550 }
 551
 552
 553 STATIC lv_extend(p)
 554         proc_p p;
 555 {
 556         /* Allocate extended data structures for Use Definition analysis */
 557
 558         register bblock_p b;
 559
 560         for (b = p->p_start; b != (bblock_p) 0; b = b->b_next) {
 561                 b->b_extend = newlvbx();
 562         }
 563 }
 564
 565
 566 STATIC lv_cleanup(p)
 567         proc_p p;
 568 {
 569         /* Deallocate extended data structures for Use Definition analysis */
 570
 571         register bblock_p b;
 572
 573         for (b = p->p_start; b != (bblock_p) 0; b = b->b_next) {
 574                 Cdeleteset(USE(b));
 575                 Cdeleteset(DEF(b));
 576                 Cdeleteset(L_IN(b));
 577                 Cdeleteset(L_OUT(b));
 578                 oldlvbx(b->b_extend);
 579         }
 580 }
 581
 582 lv_flags(p)
 583         char *p;
 584 {
 585         switch(*p) {
 586                 case 'N':
 587                         mesgflag = TRUE;
 588                         break;
 589         }
 590 }
 591
 592
 593 lv_optimize(p)
 594         proc_p p;
 595 {
 596         if (IS_ENTERED_WITH_GTO(p)) return;
 597         locals = (local_p *) 0;
 598         lv_extend(p);
 599         live_variables_analysis(p);
 600         lv_mesg(p,mesgflag);
 601         /* generate live-dead messages for regvars */
 602         lv_cleanup(p);
 603         clean_up();
 604 }
 605
 606
 607
 608 main(argc,argv)
 609         int argc;
 610         char *argv[];
 611 {
 612         go(argc,argv,init_globals,lv_optimize,no_action,lv_flags);
 613         report("useless assignments deleted",Slv);
 614         exit(0);
 615 }