util/ego/cs/cs_kill.c

   1 /* $Id: cs_kill.c,v 1.7 1994/06/24 10:22:27 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 #include <em_mnem.h>
   7 #include "../share/types.h"
   8 #include "../share/debug.h"
   9 #include "../share/global.h"
  10 #include "../share/lset.h"
  11 #include "../share/cset.h"
  12 #include "../share/aux.h"
  13 #include "../share/map.h"
  14 #include "cs.h"
  15 #include "cs_aux.h"
  16 #include "cs_debug.h"
  17 #include "cs_avail.h"
  18 #include "cs_entity.h"
  19
  20 STATIC base_valno(enp)
  21         entity_p enp;
  22 {
  23         /* Return the value number of the (base) address of an indirectly
  24          * accessed entity.
  25          */
  26         switch (enp->en_kind) {
  27                 default:
  28                         assert(FALSE);
  29                         break;
  30                 case ENINDIR:
  31                         return enp->en_ind;
  32                 case ENOFFSETTED:
  33                         return enp->en_base;
  34                 case ENARRELEM:
  35                         return enp->en_arbase;
  36         }
  37         /* NOTREACHED */
  38 }
  39
  40 STATIC entity_p find_base(vn)
  41         valnum vn;
  42 {
  43         /* Vn is the valuenumber of the (base) address of an indirectly
  44          * accessed entity. Return the entity that holds this address
  45          * recursively.
  46          */
  47         register Lindex i;
  48         register avail_p ravp;
  49
  50         for (i = Lfirst(entities); i != (Lindex) 0; i = Lnext(i, entities)) {
  51                 register entity_p renp = en_elem(i);
  52
  53                 if (renp->en_vn == vn) {
  54                         switch (renp->en_kind) {
  55                                 case ENAEXTERNAL:
  56                                 case ENALOCAL:
  57                                 case ENALOCBASE:
  58                                 case ENAARGBASE:
  59                                         return renp;
  60                                 case ENAOFFSETTED:
  61                                         return find_base(renp->en_base);
  62                         }
  63                 }
  64         }
  65
  66         /* We couldn't find it among the entities.
  67          * Let's try the available expressions.
  68          */
  69         for (ravp = avails; ravp != (avail_p) 0; ravp = ravp->av_before) {
  70                 if (ravp->av_result == vn) {
  71                         if (ravp->av_instr == (byte) op_aar)
  72                                 return find_base(ravp->av_ofirst);
  73                         if (ravp->av_instr == (byte) op_ads)
  74                                 return find_base(ravp->av_oleft);
  75                 }
  76         }
  77
  78         /* Bad luck. */
  79         return (entity_p) 0;
  80 }
  81
  82 STATIC bool obj_overlap(op1, op2)
  83         obj_p op1, op2;
  84 {
  85         /* Op1 and op2 point to two objects in the same datablock.
  86          * Obj_overlap returns whether these objects might overlap.
  87          */
  88         obj_p tmp;
  89
  90         if (op1->o_off > op2->o_off) {
  91                 /* Exchange them. */
  92                 tmp = op1; op1 = op2; op2 = tmp;
  93         }
  94         return  op1->o_size == UNKNOWN_SIZE ||
  95                 op1->o_off + op1->o_size > op2->o_off;
  96 }
  97
  98 #define same_datablock(o1, o2)  ((o1)->o_dblock == (o2)->o_dblock)
  99
 100 STATIC bool addr_local(enp)
 101         entity_p enp;
 102 {
 103         /* Is enp the address of a stack item. */
 104
 105         if (enp == (entity_p) 0) return FALSE;
 106
 107         return  enp->en_kind == ENALOCAL || enp->en_kind == ENALOCBASE ||
 108                 enp->en_kind == ENAARGBASE;
 109 }
 110
 111 STATIC bool addr_external(enp)
 112         entity_p enp;
 113 {
 114         /* Is enp the address of an external. */
 115
 116         return enp != (entity_p) 0 && enp->en_kind == ENAEXTERNAL;
 117 }
 118
 119 STATIC kill_external(obp, indir)
 120         obj_p obp;
 121         int indir;
 122 {
 123         /* A store is done via the object in obp. If this store is direct
 124          * we kill directly accessed entities in the same data block only
 125          * if they overlap with obp, otherwise we kill everything in the
 126          * data block. Indirectly accessed entities of which it can not be
 127          * proven taht they are not in the same data block, are killed in
 128          * both cases.
 129          */
 130         register Lindex i;
 131
 132         OUTTRACE("kill external", 0);
 133         for (i = Lfirst(entities); i != (Lindex) 0; i = Lnext(i, entities)) {
 134                 entity_p enp = en_elem(i);
 135                 entity_p base;
 136
 137                 switch (enp->en_kind) {
 138                         case ENEXTERNAL:
 139                                 if (!same_datablock(enp->en_ext, obp))
 140                                         break;
 141                                 if (!indir && !obj_overlap(enp->en_ext, obp))
 142                                         break;
 143                                 OUTTRACE("kill %d", enp->en_vn);
 144                                 enp->en_vn = newvalnum();
 145                                 break;
 146                         case ENINDIR:
 147                         case ENOFFSETTED:
 148                         case ENARRELEM:
 149                                 /* We spare its value number if we are sure
 150                                  * that its (base) address points into the
 151                                  * stack or into another data block.
 152                                  */
 153                                 base = find_base(base_valno(enp));
 154                                 if (addr_local(base))
 155                                         break;
 156                                 if (addr_external(base) &&
 157                                     !same_datablock(base->en_ext, obp)
 158                                    )
 159                                         break;
 160                                 OUTTRACE("kill %d", enp->en_vn);
 161                                 enp->en_vn = newvalnum();
 162                                 break;
 163                 }
 164         }
 165 }
 166
 167 STATIC bool loc_overlap(enp1, enp2)
 168         entity_p enp1, enp2;
 169 {
 170         /* Enp1 and enp2 point to two locals. Loc_overlap returns whether
 171          * they overlap.
 172          */
 173         entity_p tmp;
 174
 175         assert(enp1->en_kind == ENLOCAL && enp2->en_kind == ENLOCAL);
 176
 177         if (enp1->en_loc > enp2->en_loc) {
 178                 /* Exchange them. */
 179                 tmp = enp1; enp1 = enp2; enp2 = tmp;
 180         }
 181         if (enp1->en_loc < 0 && enp2->en_loc >= 0)
 182                 return  FALSE; /* Locals and parameters do not overlap. */
 183         else    return  enp1->en_size == UNKNOWN_SIZE ||
 184                         enp1->en_loc + enp1->en_size > enp2->en_loc;
 185 }
 186
 187 STATIC kill_local(enp, indir)
 188         entity_p enp;
 189         bool indir;
 190 {
 191         /* This time a store is done into an ENLOCAL. */
 192
 193         register Lindex i;
 194
 195         OUTTRACE("kill local", 0);
 196         for (i = Lfirst(entities); i != (Lindex) 0; i = Lnext(i, entities)) {
 197                 entity_p rep = en_elem(i);
 198                 entity_p base;
 199
 200                 switch (rep->en_kind) {
 201                         case ENLOCAL:
 202                                 if (indir) {
 203                                         /* Kill locals that might be stored into
 204                                          * via a pointer. Note: enp not used.
 205                                          */
 206                                         if (!is_regvar(rep->en_loc)) {
 207                                                 OUTTRACE("kill %d", rep->en_vn);
 208                                                 rep->en_vn = newvalnum();
 209                                         }
 210                                 } else if (loc_overlap(rep, enp)) {
 211                                         /* Only kill overlapping locals. */
 212                                         OUTTRACE("kill %d", rep->en_vn);
 213                                         rep->en_vn = newvalnum();
 214                                 }
 215                                 break;
 216                         case ENINDIR:
 217                         case ENOFFSETTED:
 218                         case ENARRELEM:
 219                                 if (!is_regvar(enp->en_loc)) {
 220                                         base = find_base(base_valno(rep));
 221                                         if (!addr_external(base)) {
 222                                                 OUTTRACE("kill %d", rep->en_vn);
 223                                                 rep->en_vn = newvalnum();
 224                                         }
 225                                 }
 226                                 break;
 227                         case ENALOCBASE:
 228                         case ENAARGBASE:
 229                                 if (enp->en_loc == 0 && rep->en_levels >= 1) {
 230                                         rep->en_vn = newvalnum();
 231                                 }
 232                                 break;
 233                 }
 234         }
 235 }
 236
 237 STATIC kill_sim()
 238 {
 239         /* A store is done into the ENIGNMASK. */
 240
 241         register Lindex i;
 242
 243         OUTTRACE("kill sim", 0);
 244         for (i = Lfirst(entities); i != (Lindex) 0; i = Lnext(i, entities)) {
 245                 register entity_p rep = en_elem(i);
 246
 247                 if (rep->en_kind == ENIGNMASK) {
 248                         OUTTRACE("kill %d", rep->en_vn);
 249                         rep->en_vn = newvalnum();
 250                         return; /* There is only one ignoremask. */
 251                 }
 252         }
 253 }
 254
 255 kill_direct(enp)
 256         entity_p enp;
 257 {
 258         /* A store will be done into enp. We must forget the values of all the
 259          * entities this one may overlap with.
 260          */
 261         switch (enp->en_kind) {
 262                 default:
 263                         assert(FALSE);
 264                         break;
 265                 case ENEXTERNAL:
 266                         kill_external(enp->en_ext, FALSE);
 267                         break;
 268                 case ENLOCAL:
 269                         kill_local(enp, FALSE);
 270                         break;
 271                 case ENIGNMASK:
 272                         kill_sim();
 273                         break;
 274         }
 275 }
 276
 277 kill_indir(enp)
 278         entity_p enp;
 279 {
 280         /* An indirect store is done, in an ENINDIR,
 281          * an ENOFFSETTED or an ENARRELEM.
 282          */
 283         entity_p p;
 284
 285         /* If we can find the (base) address of this entity, then we can spare
 286          * the entities that are provably not pointed to by the address.
 287          * We will also make use of the MES 3 pseudo's, generated by
 288          * the front-end. When a MES 3 is generated for a local, this local
 289          * will not be referenced indirectly.
 290          */
 291         if ((p = find_base(base_valno(enp))) == (entity_p) 0) {
 292                 kill_much(); /* Kill all entities without registermessage. */
 293         } else {
 294                 switch (p->en_kind) {
 295                         case ENAEXTERNAL:
 296                                 /* An indirect store into global data. */
 297                                 kill_external(p->en_ext, TRUE);
 298                                 break;
 299                         case ENALOCAL:
 300                         case ENALOCBASE:
 301                         case ENAARGBASE:
 302                                 /* An indirect store into stack data.  */
 303                                 kill_local(p, TRUE);
 304                                 break;
 305                 }
 306         }
 307 }
 308
 309 kill_much()
 310 {
 311         /* Kills all killable entities,
 312          * except the locals for which a registermessage was generated.
 313          */
 314         register Lindex i;
 315
 316         OUTTRACE("kill much", 0);
 317         for (i = Lfirst(entities); i != (Lindex) 0; i = Lnext(i, entities)) {
 318                 register entity_p rep = en_elem(i);
 319
 320                 if (rep->en_static) continue;
 321                 if (rep->en_kind == ENLOCAL && is_regvar(rep->en_loc)) continue;
 322                 OUTTRACE("kill %d", rep->en_vn);
 323                 rep->en_vn = newvalnum();
 324         }
 325 }
 326
 327 STATIC bool bad_procflags(pp)
 328         proc_p pp;
 329 {
 330         /* Return whether the flags about the procedure in pp indicate
 331          * that we have little information about it. It might be that
 332          * we haven't seen the text of pp, or that we have seen that pp
 333          * calls a procedure which we haven't seen the text of.
 334          */
 335         return !(pp->p_flags1 & PF_BODYSEEN) || (pp->p_flags1 & PF_CALUNKNOWN);
 336 }
 337
 338 STATIC kill_globset(s)
 339         cset s;
 340 {
 341         /* S is a set of global variables that might be changed.
 342          * We act as if a direct store is done into each of them.
 343          */
 344         register Cindex i;
 345
 346         OUTTRACE("kill globset", 0);
 347         for (i = Cfirst(s); i != (Cindex) 0; i = Cnext(i,s)) {
 348                 kill_external(omap[Celem(i)], FALSE);
 349         }
 350 }
 351
 352 kill_call(pp)
 353         proc_p pp;
 354 {
 355         /* Kill everything that might be destroyed by calling
 356          * the procedure in pp.
 357          */
 358         if (bad_procflags(pp)) {
 359                 /* We don't know enough about this procedure. */
 360                 kill_much();
 361         } else if (pp->p_change->c_flags & CF_INDIR) {
 362                 /* The procedure does an indirect store. */
 363                 kill_much();
 364         } else {
 365                 /* Procedure might affect global data. */
 366                 kill_globset(pp->p_change->c_ext);
 367         }
 368 }
 369
 370 kill_all()
 371 {
 372         /* Kills all entities. */
 373
 374         register Lindex i;
 375
 376         OUTTRACE("kill all entities", 0);
 377         for (i = Lfirst(entities); i != (Lindex) i; i = Lnext(i, entities)) {
 378                 entity_p enp = en_elem(i);
 379
 380                 OUTTRACE("kill %d", enp->en_vn);
 381                 enp->en_vn = newvalnum();
 382         }
 383 }