util/ego/ud/ud_defs.c

   1 /* $Id: ud_defs.c,v 1.6 1994/06/24 10:33:32 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 /*  U S E  -  D E F I N I T I O N   A N A L Y S I S
   8  *
   9  *  U D _ D E F S . C
  10  */
  11
  12 #include <em_mnem.h>
  13 #include "../share/types.h"
  14 #include "ud.h"
  15 #include "../share/debug.h"
  16 #include "../share/global.h"
  17 #include "../share/lset.h"
  18 #include "../share/cset.h"
  19 #include "../share/map.h"
  20 #include "../share/locals.h"
  21 #include "ud_defs.h"
  22 #include "../share/alloc.h"
  23 #include "../share/aux.h"
  24
  25 short nrdefs;           /* total number of definitions */
  26 short nrexpldefs;       /* number of explicit definitions */
  27 line_p *defs;
  28 cset *vardefs;
  29
  30 STATIC cset all_globl_defs, all_indir_defs;
  31 /* auxiliary sets, used by gen_sets */
  32
  33
  34 bool does_expl_def(l)
  35         line_p l;
  36 {
  37         /* See if instruction l does an explicit definition */
  38
  39         switch(INSTR(l)) {
  40                 case op_stl:
  41                 case op_sdl:
  42                 case op_ste:
  43                 case op_sde:
  44                 case op_inl:
  45                 case op_del:
  46                 case op_ine:
  47                 case op_dee:
  48                 case op_zrl:
  49                 case op_zre:
  50                         return TRUE;
  51                 default:
  52                         return FALSE;
  53         }
  54         /* NOTREACHED */
  55 }
  56
  57
  58
  59 bool does_impl_def(l)
  60         line_p l;
  61 {
  62         /* See if instruction l does an implicit definition */
  63
  64         switch(INSTR(l)) {
  65                 case op_cal:
  66                 case op_cai:
  67                 case op_sil:
  68                 case op_stf:
  69                 case op_sti:
  70                 case op_sts:
  71                 case op_sdf:
  72                 case op_sar:
  73                 case op_blm:
  74                 case op_bls:
  75                 case op_zrf:
  76                         return TRUE;
  77                 default:
  78                         return FALSE;
  79         }
  80 }
  81
  82
  83 make_defs(p)
  84         proc_p p;
  85 {
  86         /* Make a map of all explicit definitions
  87          * occurring in p.
  88          * Determine the set of explicit definitions
  89          * of variable v (i.e. vardefs[v]), for all
  90          * v from 1 to nrvars.
  91          * For every basic block b, compute CHGVARS(b),
  92          * i.e. the set of variables changed in b by an
  93          * explicit definition.
  94          */
  95
  96         register bblock_p b;
  97         register  line_p l;
  98         short v, i, cnt = 0;
  99         bool  found;
 100
 101         /* first count the number of definitions */
 102         for (b = p->p_start; b != (bblock_p) 0; b = b->b_next) {
 103                 for (l = b->b_start; l != (line_p) 0 ; l = l->l_next) {
 104                         if (does_expl_def(l)) {
 105                                 var_nr(l,&v,&found);
 106                                 if (!found) continue; /* no ud for this var */
 107                                 cnt++;
 108                         }
 109                 }
 110         }
 111         nrexpldefs = cnt;
 112         /* now allocate the defs table and the vardefs table*/
 113         defs = (line_p *) newmap(nrexpldefs);
 114         vardefs = (cset *) newmap(nrvars);
 115         for (i = 1; i <= nrvars; i++) {
 116                 vardefs[i] = Cempty_set(nrexpldefs);
 117         }
 118         cnt = 1;
 119         for (b = p->p_start; b != (bblock_p) 0; b = b->b_next) {
 120                 CHGVARS(b) =Cempty_set(nrvars);
 121                 for (l = b->b_start; l != (line_p) 0 ; l = l->l_next) {
 122                         if (does_expl_def(l)) {
 123                                 var_nr(l,&v,&found);
 124                                 if (!found) continue;
 125                                 assert (v <= nrvars);
 126                                 Cadd(v,&CHGVARS(b));
 127                                 defs[cnt] = l;
 128                                 Cadd(cnt,&vardefs[v]);
 129                                 cnt++;
 130                         }
 131                 }
 132         }
 133 }
 134
 135
 136
 137 STATIC init_gen(nrdefs)
 138         short nrdefs;
 139 {
 140         /* Initializing routine of gen_sets. Compute the set
 141          * of all implicit definitions to global variables
 142          * (all_globl_defs) and the set of all implicit
 143          * definition generated by an indirect assignment
 144          * through a pointer (all_indir_defs).
 145          */
 146
 147         short v;
 148
 149         all_globl_defs = Cempty_set(nrdefs);
 150         all_indir_defs = Cempty_set(nrdefs);
 151         for (v = 1; v <= nrglobals; v++) {
 152                 Cadd(IMPLICIT_DEF(GLOB_TO_VARNR(v)), &all_globl_defs);
 153                 Cadd(IMPLICIT_DEF(GLOB_TO_VARNR(v)), &all_indir_defs);
 154         }
 155         for (v = 1; v <= nrlocals; v++) {
 156                 if (!IS_REGVAR(locals[v])) {
 157                         Cadd(IMPLICIT_DEF(LOC_TO_VARNR(v)), &all_indir_defs);
 158                 }
 159         }
 160 }
 161
 162
 163
 164 STATIC clean_gen()
 165 {
 166         Cdeleteset(all_globl_defs);
 167         Cdeleteset(all_indir_defs);
 168 }
 169
 170
 171
 172 STATIC bool same_target(l,defnr)
 173         line_p l;
 174         short  defnr;
 175 {
 176         /* See if l defines the same variable as def */
 177
 178         line_p def;
 179         short  v;
 180
 181         if (IS_IMPL_DEF(defnr)) {
 182                 /* An implicitly generated definition */
 183                 v = IMPL_VAR(TO_IMPLICIT(defnr));
 184                 if (IS_GLOBAL(v)) {
 185                         return TYPE(l) == OPOBJECT &&
 186                                 OBJ(l)->o_globnr == TO_GLOBAL(v);
 187                 } else {
 188                         return TYPE(l) != OPOBJECT &&
 189                                 locals[TO_LOCAL(v)]->lc_off == off_set(l);
 190                 }
 191         }
 192         /* explicit definition */
 193         def = defs[TO_EXPLICIT(defnr)];
 194         if (TYPE(l) == OPOBJECT) {
 195                 return TYPE(def) == OPOBJECT && OBJ(def) == OBJ(l);
 196         } else {
 197                 return TYPE(def) != OPOBJECT && off_set(def) == off_set(l);
 198         }
 199 }
 200
 201
 202
 203 STATIC rem_prev_defs(l,gen_p)
 204         line_p l;
 205         cset   *gen_p;
 206 {
 207         /* Remove all definitions in gen that define the
 208          * same variable as l.
 209          */
 210
 211         cset gen;
 212         Cindex i,next;
 213
 214         gen = *gen_p;
 215         for (i = Cfirst(gen); i != (Cindex) 0; i = next) {
 216                 next = Cnext(i,gen);
 217                 if (same_target(l,Celem(i))) {
 218                         Cremove(Celem(i),gen_p);
 219                 }
 220         }
 221 }
 222
 223
 224
 225
 226 STATIC impl_globl_defs(p,gen_p)
 227         proc_p p;
 228         cset   *gen_p;
 229 {
 230         /* Add all definitions of global variables
 231          * that are generated implicitly by a call
 232          * to p to the set gen_p.
 233          */
 234
 235         Cindex i;
 236         short v;
 237         cset ext = p->p_change->c_ext;
 238
 239         for (i = Cfirst(ext); i != (Cindex) 0; i = Cnext(i,ext)) {
 240                 if (( v = omap[Celem(i)]->o_globnr) != (short) 0) {
 241                         /* the global variable v, for which we do
 242                          * maintain ud-info is changed by p, so a
 243                          * definition of v is generated implicitly.
 244                          */
 245                         Cadd(IMPLICIT_DEF(GLOB_TO_VARNR(v)),gen_p);
 246                 }
 247         }
 248 }
 249
 250
 251
 252 STATIC impl_gen_defs(l,gen_p)
 253         line_p l;
 254         cset   *gen_p;
 255 {
 256         /* Add all definitions generated implicitly by instruction l
 257          * to gen_p. l may be a call or some kind of indirect
 258          * assignment.
 259          */
 260
 261         proc_p p;
 262
 263         switch(INSTR(l)) {
 264                 case op_cal:
 265                         p = PROC(l);
 266                         if (BODY_KNOWN(p)) {
 267                                 impl_globl_defs(p,gen_p);
 268                                 if (!CHANGE_INDIR(p)) return;
 269                                 break;
 270                         }
 271                         /* else fall through ... */
 272                 case op_cai:
 273                         /* Indirect subroutine call or call to
 274                          * a subroutine whose body is not available.
 275                          * Assume worst case; all global
 276                          * variables are changed and
 277                          * the called proc. does a store-
 278                          * indirect.
 279                          */
 280                         Cjoin(all_globl_defs,gen_p);
 281                         break;
 282                 /* default: indir. assignment */
 283         }
 284         Cjoin(all_indir_defs,gen_p);
 285 }
 286
 287
 288
 289
 290 gen_sets(p)
 291         proc_p p;
 292 {
 293         /* Compute for every basic block b of p the
 294          * set GEN(b) of definitions in b (explicit as
 295          * well as implicit) that reach the end of b.
 296          */
 297
 298         register bblock_p b;
 299         register line_p   l;
 300         short defnr = 1;
 301
 302         init_gen(nrdefs);  /* compute all_globl_defs and all_indir_defs */
 303         for (b = p->p_start; b != (bblock_p) 0; b = b->b_next) {
 304                 GEN(b) = Cempty_set(nrdefs);
 305                 for (l = b->b_start; l != (line_p) 0; l = l->l_next) {
 306                         if (does_impl_def(l)) {
 307                                 impl_gen_defs(l,&GEN(b));
 308                                 /* add definitions implicitly
 309                                  * generated by subroutine call
 310                                  * or indir. pointer assignment.
 311                                  */
 312                         } else {
 313                                 if (does_expl_def(l)) {
 314                                         if (defnr <= nrdefs && defs[defnr] == l) {
 315                                                 rem_prev_defs(l,&GEN(b));
 316                                                 /* previous defs. of same var
 317                                                  * don't reach the end of b.
 318                                                  */
 319                                                 Cadd(EXPL_TO_DEFNR(defnr),&GEN(b));
 320                                                 defnr++;
 321                                         }
 322                                 }
 323                         }
 324                 }
 325         }
 326         clean_gen();  /* clean up */
 327 }
 328
 329
 330
 331
 332 STATIC killed_defs(v,b)
 333         short v;
 334         bblock_p b;
 335 {
 336         /* Put all definitions of v occurring outside b
 337          * in KILL(b). In fact, we also put explicit
 338          * definitions occurring in b, but not reaching the
 339          * end of b, in KILL(b). This causes no harm.
 340          */
 341
 342         Cindex i;
 343         short d;
 344
 345         for (i = Cfirst(vardefs[v]); i != (Cindex) 0; i = Cnext(i,vardefs[v])) {
 346                 d = Celem(i);  /* d is an explicit definition of v */
 347                 if (!Cis_elem(EXPL_TO_DEFNR(d),GEN(b))) {
 348                         Cadd(EXPL_TO_DEFNR(d),&KILL(b));
 349                 }
 350         }
 351         /* Also add implicit definition of v to KILL(b) */
 352         Cadd(IMPLICIT_DEF(v),&KILL(b));
 353 }
 354
 355
 356
 357
 358 kill_sets(p)
 359         proc_p p;
 360 {
 361         /* For every basic block b of p compute the set
 362          * KILL(b) of definitions outside b that define
 363          * variables redefined by b.
 364          * KILL(b) contains explicit as well as implicit
 365          * definitions.
 366          */
 367
 368         register bblock_p b;
 369         Cindex i;
 370         short v;
 371
 372         for (b = p->p_start; b != (bblock_p) 0; b = b->b_next) {
 373                 KILL(b) = Cempty_set(nrdefs);
 374                 for (i = Cfirst(CHGVARS(b)); i != (Cindex) 0;
 375                                                 i = Cnext(i,CHGVARS(b))) {
 376                         v = Celem(i); /* v is a variable changed in b */
 377                         killed_defs(v,b);
 378                 }
 379         }
 380 }