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 block_entry(b,prev)
 315         bblock_p b,prev;
 316 {
 317         short v,vn;
 318         local_p loc;
 319         bool was_live, is_live;
 320
 321         /* Generate a live/dead message for every register variable that
 322          * was live at the end of prev, but dead at the beginning of b,
 323          * or v.v. If prev = 0 (i.e. begin of procedure), parameters were
 324          * live, normal local variables were dead.
 325          */
 326
 327         for (v = 1; v <= nrlocals; v++) {
 328                 loc = locals[v];
 329                 if (IS_REGVAR(loc)) {
 330                         vn = LOC_TO_VARNR(v);
 331                         if (prev == (bblock_p) 0) {
 332                                 was_live = loc->lc_off >= 0;
 333                         } else {
 334                                 was_live = Cis_elem(vn,L_OUT(prev));
 335                         }
 336                         is_live = Cis_elem(vn,L_IN(b));
 337                         if (was_live != is_live) {
 338                                 app_block(make_mesg((is_live?ego_live:ego_dead),loc),b);
 339                         }
 340                 }
 341         }
 342 }
 343
 344
 345
 346 STATIC app_block(l,b)
 347         line_p l;
 348         bblock_p b;
 349 {
 350         line_p x = b->b_start;
 351
 352         if (x != (line_p) 0 && INSTR(x) == ps_pro) {
 353                 /* start of procedure; append after pro pseudo ! */
 354                 if ((l->l_next = x->l_next) != (line_p) 0) {
 355                         PREV(l->l_next) = l;
 356                 }
 357                 x->l_next = l;
 358                 PREV(l) = x;
 359         } else {
 360                 if ((l->l_next = x) != (line_p) 0) {
 361                         PREV(l->l_next) = l;
 362                 }
 363                 b->b_start = l;
 364                 PREV(l) = (line_p) 0;
 365         }
 366 }
 367
 368
 369
 370 STATIC definition(l,useless_out,v_out,mesgflag)
 371         line_p l;
 372         bool *useless_out;
 373         short *v_out;
 374         bool mesgflag;
 375 {
 376         /* Process a definition. If the defined (register-) variable
 377          * is live after 'l', then create a live-message and put
 378          * it after 'l'.
 379          */
 380
 381         short v;
 382         bool found;
 383         local_p loc;
 384
 385         *useless_out = FALSE;
 386         var_nr(l,&v,&found);
 387         if (found && IS_LOCAL(v)) {
 388                 *v_out = v;
 389                 loc = locals[TO_LOCAL(v)];
 390                 if (IS_REGVAR(loc)) {
 391                         /*      Tricky stuff here. Make sure that a variable
 392                                 that is assigned to is alive, at least for
 393                                 a very very short time. Otherwize, the
 394                                 register allocation pass might think that it
 395                                 is never alive, and (incorrectly) use the
 396                                 same register for this variable as for
 397                                 another variable, that is alive at this point.
 398                                 If this variable is dead after the assignment,
 399                                 the two messages (ego_live, ego_dead) are right
 400                                 after each other. Luckily, this IS an interval.
 401                         */
 402                         if (!mesgflag) {
 403                                 appnd_line(make_mesg(ego_live,loc), l);
 404                                 l = l->l_next;
 405                         }
 406                         if (IS_LIVE(loc)) {
 407                                 DEAD(loc);
 408                         } else {
 409                                 if (!mesgflag) {
 410                                         appnd_line(make_mesg(ego_dead, loc), l);
 411                                 }
 412                                 *useless_out = TRUE;
 413                         }
 414                 }
 415         }
 416 }
 417
 418
 419
 420
 421 STATIC use(l,mesgflag)
 422         line_p l;
 423         bool mesgflag;
 424 {
 425         /* Process a use. If the defined (register-) variable
 426          * is dead after 'l', then create a dead-message and put
 427          * it after 'l'.
 428          */
 429
 430         short v;
 431         bool found;
 432         local_p loc;
 433
 434         var_nr(l,&v,&found);
 435         if (found && IS_LOCAL(v)) {
 436                 loc = locals[TO_LOCAL(v)];
 437                 if (IS_REGVAR(loc) && IS_DEAD(loc)) {
 438                         if (!mesgflag) {
 439                                 appnd_line(make_mesg(ego_dead,loc), l);
 440                         }
 441                         LIVE(loc);
 442                 }
 443         }
 444 }
 445
 446
 447
 448 STATIC nothing() { }  /* No action to be undertaken at level 0 of parser */
 449
 450 STATIC rem_code(l1,l2,b)
 451         line_p l1,l2;
 452         bblock_p b;
 453 {
 454         line_p l,x,y,next;
 455
 456         x = PREV(l1);
 457         y = l2->l_next;
 458         for (l = l1; l != l2; l = next) {
 459                 next = l->l_next;
 460                 oldline(l);
 461         }
 462         if (x == (line_p) 0) {
 463                 b->b_start = y;
 464         } else {
 465                 x->l_next = y;
 466         }
 467         if (y != (line_p) 0) {
 468                 PREV(y) = x;
 469         }
 470 }
 471
 472
 473
 474
 475 #define SIZE(v) ((offset) locals[TO_LOCAL(v)]->lc_size)
 476
 477
 478
 479
 480 lv_mesg(p,mesgflag)
 481         proc_p p;
 482         bool mesgflag;
 483 {
 484         /* Create live/dead messages for every possible register
 485          * variable of p. A dead-message is put after a "use" of
 486          * such a variable, if the variable becomes dead just
 487          * after the use (i.e. this was its last use).
 488          * A live message is put after a "definition" of such
 489          * a variable, if the variable becomes live just
 490          * after the definition (which will usually be the case).
 491          * We traverse every basic block b of p from the last
 492          * instruction of b backwards to the beginning of b.
 493          * Initially, all variables that are dead at the end
 494          * of b are marked dead. All others are marked live.
 495          * If we come accross a definition of a variable X that
 496          * was marked live, we put a live-message after the
 497          * definition and mark X dead.
 498          * If we come accross a use of a variable X that
 499          * was marked dead, we put a dead-message after the
 500          * use and mark X live.
 501          * So at any point, the mark of X tells whether X is
 502          * live or dead immediately before (!) that point.
 503          * We also generate a message at the start of a basic block
 504          * for every variable that was live at the end of the (textually)
 505          * previous block, but dead at the entry of this block, or v.v.
 506          * On the fly, useless assignments are removed.
 507          */
 508
 509         register bblock_p b;
 510         register line_p l;
 511         line_p lnp, prev;
 512         bblock_p prevb = (bblock_p) 0;
 513         short v;
 514         bool useless;
 515
 516         for (b = p->p_start; b != (bblock_p) 0; b = b->b_next) {
 517                 block_entry(b,prevb); /* generate message at head of block */
 518                 prevb = b;
 519                 if (!mesgflag) {
 520                         init_live_dead(b);
 521                 }
 522                 for (l = last_instr(b); l != (line_p) 0; l = prev) {
 523                         /* traverse backwards! */
 524                         prev = PREV(l);
 525                         if (is_def(l)) {
 526                                 definition(l,&useless,&v,mesgflag);
 527                                 if (useless &&   /* assignment to dead var. */
 528                                     parse(prev,SIZE(v),&lnp,0,nothing)) {
 529                                         /* The code "VAR := expression" can
 530                                          * be removed. 'l' is the "STL VAR",
 531                                          * lnp is the beginning of the EM code
 532                                          * for the expression.
 533                                          */
 534                                         prev = PREV(lnp);
 535                                         rem_code(lnp,l,b);
 536 OUTVERBOSE("useless assignment ,proc %d,local %d", curproc->p_id,
 537   (int) locals[TO_LOCAL(v)]->lc_off);
 538                                         Slv++;
 539                                 }
 540                                 else {
 541                                 }
 542                         } else {
 543                                 if (is_dir_use(l))  {
 544                                         use(l,mesgflag);
 545                                 }
 546                         }
 547                 }
 548         }
 549 }
 550
 551
 552 STATIC lv_extend(p)
 553         proc_p p;
 554 {
 555         /* Allocate extended data structures for Use Definition analysis */
 556
 557         register bblock_p b;
 558
 559         for (b = p->p_start; b != (bblock_p) 0; b = b->b_next) {
 560                 b->b_extend = newlvbx();
 561         }
 562 }
 563
 564
 565 STATIC lv_cleanup(p)
 566         proc_p p;
 567 {
 568         /* Deallocate extended data structures for Use Definition analysis */
 569
 570         register bblock_p b;
 571
 572         for (b = p->p_start; b != (bblock_p) 0; b = b->b_next) {
 573                 Cdeleteset(USE(b));
 574                 Cdeleteset(DEF(b));
 575                 Cdeleteset(L_IN(b));
 576                 Cdeleteset(L_OUT(b));
 577                 oldlvbx(b->b_extend);
 578         }
 579 }
 580
 581 lv_flags(p)
 582         char *p;
 583 {
 584         switch(*p) {
 585                 case 'N':
 586                         mesgflag = TRUE;
 587                         break;
 588         }
 589 }
 590
 591
 592 lv_optimize(p)
 593         proc_p p;
 594 {
 595         if (IS_ENTERED_WITH_GTO(p)) return;
 596         locals = (local_p *) 0;
 597         lv_extend(p);
 598         live_variables_analysis(p);
 599         lv_mesg(p,mesgflag);
 600         /* generate live-dead messages for regvars */
 601         lv_cleanup(p);
 602         clean_up();
 603 }
 604
 605
 606
 607 main(argc,argv)
 608         int argc;
 609         char *argv[];
 610 {
 611         go(argc,argv,init_globals,lv_optimize,no_action,lv_flags);
 612         report("useless assignments deleted",Slv);
 613         exit(0);
 614 }