util/ego/sr/sr_cand.c

   1 /* $Id: sr_cand.c,v 1.5 1994/06/24 10:32:10 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 /*  S T R E N G T H   R E D U C T I O N
   7  *
   8  *  S R _ C A N D . C
   9  */
  10
  11
  12 #include <em_mnem.h>
  13 #include <em_pseu.h>
  14 #include "../share/types.h"
  15 #include "../share/lset.h"
  16 #include "../share/cset.h"
  17 #include "../share/debug.h"
  18 #include "../share/global.h"
  19 #include "../share/map.h"
  20 #include "../share/aux.h"
  21 #include "sr.h"
  22 #include "sr_aux.h"
  23 #include "sr_cand.h"
  24
  25
  26 /* A candidate induction variable of a loop (hereafter called candidate) is a
  27  * local variable (of the current procedure) that is assigned a value
  28  * precisely once within the loop. Furthermore, this assignment must
  29  * take place in a firm block of the loop.
  30  * We determine those locals that are assigned precisely once, within
  31  * a firm block;
  32  *
  33  * We represent a local variable via an instruction that references it,
  34  * e.g. LOL -6 represents the local variable at offset -6 with size=wordsize.
  35  * We keep track of two sets:
  36  *  cand     - the set of all candidate variables
  37  *  dismiss  - a set of variables that may not be made a candidate
  38  *              (because they are assigned more than once, or because
  39  *               they are assigned outside a firm block).
  40  * Only local variables for which a register message is given are considered.
  41  */
  42
  43
  44 STATIC lset cand,               /* set of candidates */
  45             dism;               /* set of dismissed variables */
  46
  47
  48 #define ALL_LINES(lnp,list)     lnp = list; lnp != (line_p) 0; lnp = lnp->l_next
  49
  50
  51
  52 STATIC un_cand(lnp)
  53         line_p lnp;
  54 {
  55         /* remove the variable stored into by lnp from the list of
  56          * candidates (if it was there anyway).
  57          */
  58
  59         Lindex i, next;
  60
  61         for (i = Lfirst(cand); i != (Lindex) 0; i = next) {
  62                 next = Lnext(i,cand);
  63                 if (same_local(lnp,Lelem(i))) {
  64                         OUTTRACE("remove candidate",0);
  65                         Lremove(Lelem(i), &cand);
  66                 }
  67         }
  68 }
  69
  70
  71 STATIC bool is_cand(lnp)
  72         line_p lnp;
  73 {
  74         /* see if the variable stored into by lnp is a candate */
  75
  76         Lindex i;
  77
  78         for (i = Lfirst(cand); i != (Lindex) 0; i = Lnext(i,cand)) {
  79                 if (same_local(lnp,Lelem(i))) {
  80                         return TRUE;
  81                 }
  82         }
  83         return FALSE;
  84 }
  85
  86
  87 STATIC make_cand(lnp)
  88         line_p lnp;
  89 {
  90         /* make the variable stored into by lnp a candidate */
  91
  92
  93         OUTTRACE("add a new candidate",0);
  94         Ladd(lnp,&cand);
  95 }
  96
  97
  98
  99 STATIC do_dismiss(lnp)
 100         line_p lnp;
 101 {
 102         Ladd(lnp,&dism);
 103 }
 104
 105
 106 STATIC dismiss(lnp)
 107         line_p lnp;
 108 {
 109         /* The variable referenced by lnp is turned definitely into
 110          * a non-candidate.
 111          */
 112
 113         un_cand(lnp);   /* remove it from the candidate set,
 114                          * if it was there in the first place.
 115                          */
 116         do_dismiss(lnp); /* add it to the set of dismissed variables */
 117 }
 118
 119
 120 STATIC bool not_dismissed(lnp)
 121         line_p lnp;
 122 {
 123         Lindex i;
 124
 125         for (i = Lfirst(dism); i != (Lindex) 0; i = Lnext(i,dism)) {
 126                 if (same_local(Lelem(i),lnp)) {
 127                         return FALSE; /* variable was dismissed */
 128                 }
 129         }
 130         return TRUE;
 131 }
 132
 133
 134 STATIC try_cand(lnp,b)
 135         line_p lnp;
 136         bblock_p b;
 137 {
 138         /* If the variable stored into by lnp was not already a candidate
 139          * and was not dismissed, then it is made a candidate
 140          * (unless the assignment takes places in a block that is not firm).
 141          */
 142
 143         if (!is_regvar(off_set(lnp))) return;
 144         if (is_cand(lnp) || !IS_FIRM(b)) {
 145                 dismiss(lnp);
 146         } else {
 147                 if (not_dismissed(lnp)) {
 148                         make_cand(lnp);
 149                 }
 150         }
 151 }
 152
 153
 154 candidates(lp,cand_out,vars_out)
 155         loop_p lp;
 156         lset   *cand_out, *vars_out;
 157 {
 158         /* Find the candidate induction variables.
 159          */
 160
 161         bblock_p b;
 162         line_p lnp;
 163         Lindex i;
 164
 165         OUTTRACE("find candidates of loop %d",lp->lp_id);
 166         cand = Lempty_set();
 167         dism = Lempty_set();
 168
 169         for (i = Lfirst(lp->LP_BLOCKS); i != (Lindex) 0;
 170                                           i = Lnext(i,lp->LP_BLOCKS)) {
 171                 b = (bblock_p) Lelem(i);
 172                 for ( ALL_LINES(lnp, b->b_start)) {
 173                         OUTTRACE("inspect instruction %d",INSTR(lnp));
 174                         switch(INSTR(lnp)) {
 175                                 case op_stl:
 176                                 case op_inl:
 177                                 case op_del:
 178                                         OUTTRACE("it's a store local",0);
 179                                         try_cand(lnp,b);
 180                                         break;
 181                                 case op_zrl:
 182                                         OUTTRACE("it's a destroy local",0);
 183                                         if (is_regvar(off_set(lnp))) {
 184                                                 dismiss(lnp);
 185                                         }
 186                                         break;
 187                         }
 188                 }
 189         }
 190         *cand_out = cand;
 191         *vars_out = dism;
 192 }