util/ego/ud/ud_copy.c

   1 /* $Id: ud_copy.c,v 1.6 1994/06/24 10:33:25 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 /* C O P Y   P R O P A G A T I O N */
   7
   8 #include <em_mnem.h>
   9 #include <em_pseu.h>
  10 #include <em_spec.h>
  11 #include "../share/types.h"
  12 #include "ud.h"
  13 #include "../share/debug.h"
  14 #include "../share/global.h"
  15 #include "../share/alloc.h"
  16 #include "../share/lset.h"
  17 #include "../share/cset.h"
  18 #include "../share/def.h"
  19 #include "../share/aux.h"
  20 #include "../share/locals.h"
  21 #include "../ud/ud_defs.h"
  22 #include "ud_copy.h"
  23 #include "ud_const.h"
  24 #include "ud_aux.h"
  25
  26
  27
  28 line_p *copies;         /* table of copies; every entry points to the
  29                          * store-instruction.
  30                          */
  31 short *def_to_copynr;   /* table that maps a 'definition'-number to a
  32                          * 'copy' number.
  33                          */
  34 short nrcopies;         /* number of copies in the current procedure
  35                          * (length of copies-table)
  36                          */
  37
  38 #define COPY_NR(c)      def_to_copynr[c]
  39 #define CHANGED(v,b) (Cis_elem(v,CHGVARS(b)) || Cis_elem(IMPLICIT_DEF(v),GEN(b)))
  40
  41
  42 #define COUNT 0
  43 #define MAP 1
  44
  45 STATIC traverse_defs(p,action)
  46         proc_p p;
  47         int action;
  48 {
  49         bblock_p b;
  50         line_p l;
  51         bool found;
  52         short defcnt,v,cnt;
  53
  54         defcnt = 1;
  55         if (action == COUNT) {
  56                 nrcopies = 0;
  57         } else {
  58                 copies = (line_p *) newmap(nrcopies);
  59                 def_to_copynr = newtable(nrdefs);
  60                 cnt = 1;
  61         }
  62         if (defcnt > nrdefs) return;
  63         for (b = p->p_start; b != (bblock_p) 0; b = b->b_next) {
  64                 for (l = b->b_start; l != (line_p) 0; l = l->l_next) {
  65                         if (defs[defcnt] == l) {
  66                                 if (is_copy(l)) {
  67                                         var_nr(PREV(l),&v,&found);
  68                                         if (found) {
  69                                                 if (action == COUNT) {
  70                                                         nrcopies++;
  71                                                 } else {
  72                                                         copies[cnt] = l;
  73                                                         def_to_copynr[defcnt] =
  74                                                            cnt++;
  75                                                 }
  76                                         }
  77                                 }
  78                                 if (++defcnt > nrdefs) return;
  79                         }
  80                 }
  81         }
  82 }
  83
  84
  85
  86 STATIC make_copytab(p)
  87         proc_p p;
  88 {
  89         /* Make a table of all copies appearing in procedure p.
  90          * We first count how many there are, because we
  91          * have to allocate a dynamic array of the correct size.
  92          */
  93
  94         traverse_defs(p,COUNT);
  95         traverse_defs(p,MAP);
  96 }
  97
  98
  99
 100 STATIC bool is_changed(varl,start,stop)
 101         line_p varl, start, stop;
 102 {
 103         /* See if the variable used by instruction varl
 104          * is changed anywhere between 'start' and 'stop'
 105          */
 106
 107         register line_p l;
 108         short v;
 109         bool found;
 110
 111         var_nr(varl,&v,&found);
 112         if (!found) {
 113                 return TRUE; /* We don't maintain ud-info for this variable */
 114         }
 115         for (l = start; l != (line_p) 0 && l != stop; l = l->l_next) {
 116                 if (does_expl_def(l) && same_var(varl,l)) return TRUE;
 117                 if (does_impl_def(l) && affected(varl,v,l)) return TRUE;
 118         }
 119         return FALSE;
 120 }
 121
 122
 123
 124 STATIC gen_kill_copies(p)
 125         proc_p p;
 126 {
 127         /* Compute C_GEN and C_KILL for every basic block
 128          * of p.
 129          */
 130
 131         register line_p l;
 132         register bblock_p b,n;
 133         short v;
 134         bool found;
 135         short copycnt = 1, defcnt = 1;
 136
 137         for (b = p->p_start; b != (bblock_p) 0; b = b->b_next) {
 138                 C_GEN(b) = Cempty_set(nrcopies);
 139                 C_KILL(b) = Cempty_set(nrcopies);
 140         }
 141         if (nrcopies == 0) return;
 142         for (b = p->p_start; b != (bblock_p) 0; b = b->b_next) {
 143                 for (l = b->b_start; l != (line_p) 0; l = l->l_next) {
 144                         if (copies[copycnt] == l) {
 145                                 var_nr(PREV(l),&v,&found);
 146                                 assert(found);
 147                                 for (n = p->p_start; n != (bblock_p) 0;
 148                                      n = n->b_next) {
 149                                         if (n != b && CHANGED(v,n) &&
 150                                             Cis_elem(EXPL_TO_DEFNR(defcnt),IN(n))) {
 151                                                 Cadd(copycnt,&C_KILL(n));
 152                                         }
 153                                 }
 154                                 if (is_changed(PREV(l),l,(line_p) 0)) {
 155                                         Cadd(copycnt,&C_KILL(b));
 156                                 } else {
 157                                         Cadd(copycnt,&C_GEN(b));
 158                                 }
 159                                 if (++copycnt > nrcopies) return;
 160                         }
 161                         if (defs[defcnt] == l) defcnt++;
 162                 }
 163         }
 164 }
 165
 166
 167
 168 STATIC intersect_outs(bbset,setp,full_set)
 169         lset bbset;
 170         cset *setp,full_set;
 171 {
 172         /* Take the intersection of C_OUT(b), for all b in bbset,
 173          * and put the result in setp.
 174          */
 175
 176         Lindex i;
 177
 178         Ccopy_set(full_set,setp);
 179         for (i = Lfirst(bbset); i != (Lindex) 0; i = Lnext(i,bbset)) {
 180                 Cintersect(C_OUT((bblock_p) Lelem(i)), setp);
 181         }
 182 }
 183
 184
 185
 186 STATIC init_cin(p,full_set)
 187         proc_p p;
 188         cset full_set;
 189 {
 190         /* Initialize C_IN(b) and C_OUT(b), for every basic block b.
 191          * C_IN of the root of the CFG (i.e. the procedure entry block)
 192          * will contain every copy, as it trivially holds that for
 193          * every copy "s: A := B" there is no assignment to B on any
 194          * path from s to the beginning of the root (because PRED(root)=empty).
 195          * C_IN and C_OUT of the root will never be changed.
 196          * For all remaining blocks b, C_IN(b) is initialized to the set of
 197          * all copies, and C_OUT is set to all copies but those killed in b.
 198          */
 199
 200         bblock_p b;
 201         bblock_p root = p->p_start;
 202
 203         C_IN(root) = Cempty_set(nrcopies);
 204         Ccopy_set(full_set,&C_IN(root)); /* full_set is the set of all copies */
 205         /* C_OUT(root) = {all copies} - C_KILL(root) + C_GEN(root) */
 206         C_OUT(root) = Cempty_set(nrcopies);
 207         Ccopy_set(full_set,&C_OUT(root));
 208         Csubtract(C_KILL(root),&C_OUT(root));
 209         Cjoin(C_GEN(root),&C_OUT(root));
 210         for (b = root->b_next; b != (bblock_p) 0; b = b->b_next) {
 211                 C_IN(b) = Cempty_set(nrcopies);
 212                 Ccopy_set(full_set,&C_IN(b));
 213                 C_OUT(b) = Cempty_set(nrcopies);
 214                 Ccopy_set(full_set,&C_OUT(b));
 215                 Csubtract(C_KILL(b),&C_OUT(b));
 216         }
 217 }
 218
 219
 220
 221 STATIC solve_cin(p)
 222         proc_p p;
 223 {
 224         /* Solve the data flow equations for reaching
 225          * definitions of procedure p.
 226          * These equations are:
 227          *  (1)  C_OUT(b) = C_IN(b) - C_KILL(b) + C_GEN(b)
 228          *  (2)  C_IN(b)  = C_OUT(p1) * .. * C_OUT(pn)
 229          *  (3)  C_IN(root) = {all copies} ;
 230          *       where PRED(b) = {p1, .. , pn}
 231          *       and '*' denotes set intersection.
 232          * We use the iterative algorithm of Aho&Ullman to
 233          * solve the equations.
 234          */
 235
 236         register bblock_p b;
 237         bool     change;
 238         cset     newin,full_set;
 239         short n;
 240
 241         /* initializations */
 242         full_set = Cempty_set(nrcopies);
 243         for (n = 1; n <= nrcopies; n++) {
 244                 Cadd(n,&full_set);
 245         }
 246         newin = Cempty_set(nrcopies);
 247         init_cin(p,full_set);
 248         change = TRUE;
 249         /* main loop */
 250         while (change) {
 251                 change = FALSE;
 252                 for (b = p->p_start->b_next; b != (bblock_p) 0; b = b->b_next) {
 253                         intersect_outs(b->b_pred, &newin,full_set);
 254                         /* newin = C_OUT(p1) * .. * C_OUT(pn) */
 255                         if (!Cequal(newin,C_IN(b))) {
 256                                 change = TRUE;
 257                                 Ccopy_set(newin, &C_IN(b));
 258                                 Ccopy_set(C_IN(b),   &C_OUT(b));
 259                                 Csubtract(C_KILL(b), &C_OUT(b));
 260                                 Cjoin(C_GEN(b),      &C_OUT(b));
 261                         }
 262                 }
 263         }
 264         Cdeleteset(newin);
 265         Cdeleteset(full_set);
 266 }
 267
 268
 269
 270 copy_analysis(p)
 271         proc_p p;
 272 {
 273         /* Determine which copies procedure p has. Compute C_IN(b),
 274          * for every basic block b.
 275          */
 276
 277         make_copytab(p); /* Make a table of all copies */
 278         gen_kill_copies(p); /* Compute C_GEN(b) and C_KILL(b), for every b */
 279         solve_cin(p); /* Solve equations for C_IN(b) */
 280 }
 281
 282
 283
 284 bool is_copy(def)
 285         line_p def;
 286 {
 287         /* See if the definition def is also a 'copy', i.e. an
 288          * statement of the form 'A := B' (or, in EM terminology:
 289          * a sequence 'Load Variable; Store Variable').
 290          */
 291
 292
 293         line_p lhs;
 294         int instr;
 295
 296         lhs = PREV(def);
 297         if (lhs == (line_p) 0) return FALSE;
 298         instr = INSTR(def);
 299         switch(INSTR(lhs)) {
 300                 case op_lol:
 301                 case op_loe:
 302                         return instr == op_stl || instr == op_ste;
 303                 case op_ldl:
 304                 case op_lde:
 305                         return instr == op_sdl || instr == op_sde;
 306                 default:
 307                         return FALSE;
 308         }
 309         /* NOTREACHED */
 310 }
 311
 312
 313
 314 fold_var(old,new,b)
 315         line_p old, new;
 316         bblock_p b;
 317 {
 318         /* The variable referenced by the EM instruction 'old'
 319          * must be replaced by the variable referenced by 'new'.
 320          */
 321
 322         line_p l;
 323
 324 /* DEBUGGING:
 325         local_p loc;
 326         short nr;
 327         bool ok;
 328         if (TYPE(old) == OPOBJECT) {
 329                 printf("global var.");
 330         } else {
 331                 printf("local var. with off. %ld",off_set(old));
 332                 find_local(off_set(old),&nr,&ok);
 333                 assert(ok);
 334                 loc = locals[nr];
 335                 printf(",score %ld",loc->lc_score);
 336         }
 337         printf(" replaced by ");
 338         if (TYPE(new) == OPOBJECT) {
 339                 printf("global var.");
 340         } else {
 341                 printf("local var. with off. %ld",off_set(new));
 342                 find_local(off_set(new),&nr,&ok);
 343                 assert(ok);
 344                 loc = locals[nr];
 345                 printf(",score %ld",loc->lc_score);
 346         }
 347         printf("\n");
 348 END DEBUG */
 349         l = old;
 350         if (TYPE(l) != TYPE(new)) {
 351                 l = newline(TYPE(new));
 352                 l->l_instr = INSTR(new);
 353                 repl_line(old,l,b);
 354         }
 355         switch(TYPE(new)) {
 356                 case OPOBJECT:
 357                         OBJ(l) = OBJ(new);
 358                         break;
 359                 case OPSHORT:
 360                         SHORT(l) = SHORT(new);
 361                         break;
 362                 case OPOFFSET:
 363                         OFFSET(l) = OFFSET(new);
 364                         break;
 365                 default:
 366                         assert(FALSE);
 367         }
 368 }
 369
 370
 371
 372 bool value_retained(copy,defnr,use,b)
 373         line_p copy,use;
 374         short  defnr;
 375         bblock_p b;
 376 {
 377         /* See if the right hand side variable of the
 378          * copy still has the same value at 'use'.
 379          * If the copy and the use are in the same
 380          * basic block (defnr = 0), search from the
 381          * copy to the use, to see if the rhs variable
 382          * is changed. If the copy is in another block,
 383          * defnr is the definition-number of the copy.
 384          * Search from the beginning of the block to
 385          * the use, to see if the rhs is changed; if not,
 386          * check that the copy is in C_IN(b).
 387          */
 388
 389         line_p rhs, start;
 390
 391         rhs = PREV(copy);
 392         start = (defnr == 0 ? copy : b->b_start);
 393         return !is_changed(rhs,start,use) &&
 394                (defnr == 0 || Cis_elem(COPY_NR(defnr), C_IN(b)));
 395 }