util/ego/sr/sr_iv.c

   1 /* $Id: sr_iv.c,v 1.6 1994/06/24 10:32:21 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 _ I V . C
   9  *
  10  */
  11
  12
  13 #include <em_mnem.h>
  14 #include <em_pseu.h>
  15 #include "../share/types.h"
  16 #include "sr.h"
  17 #include "../share/lset.h"
  18 #include "../share/cset.h"
  19 #include "../share/debug.h"
  20 #include "../share/global.h"
  21 #include "../share/alloc.h"
  22 #include "../share/aux.h"
  23 #include "sr_aux.h"
  24 #include "sr_cand.h"
  25 #include "sr_iv.h"
  26
  27
  28
  29 STATIC lset ivvars;     /* set of induction variables */
  30
  31 STATIC short nature(lnp)
  32         line_p lnp;
  33 {
  34         /* Auxiliary routine used by inc_or_dec, is_add and plus_or_min.
  35          * Determine if lnp had INCREMENT/DECREMENT-nature (1),
  36          * ADD-nature (2), SUBTRACT-nature (3)
  37          * or Buddha-nature (0).
  38          */
  39
  40         bool size_ok;
  41
  42         assert(lnp != (line_p) 0);
  43         size_ok = (TYPE(lnp) == OPSHORT && SHORT(lnp) == ws);
  44         switch(INSTR(lnp)) {
  45                 case op_inc:
  46                 case op_dec:
  47                         return 1;
  48                 case op_adi:
  49                 case op_adu:
  50                         return (size_ok? 2:0);
  51                 case op_sbi:
  52                 case op_sbu:
  53                         return (size_ok? 3:0);
  54         }
  55         return 0;
  56 }
  57
  58
  59
  60 #define is_add(l)       (nature(l) == 2)
  61 #define plus_or_min(l)  (nature(l) > 1)
  62 #define inc_or_dec(l)   (nature(l) == 1)
  63
  64
  65 STATIC bool is_same(l,lnp)
  66         line_p l, lnp;
  67 {
  68         /* lnp is a STL x , where x is a candidate
  69          * induction variable. See if l is a LOL x
  70          * (with the same x as the store-instruction)
  71          */
  72
  73         assert(INSTR(lnp) == op_stl);
  74         return l != (line_p) 0 && INSTR(l) == op_lol &&
  75                 off_set(l) == off_set(lnp);
  76 }
  77
  78
  79 STATIC ivar(lnp,step)
  80         line_p  lnp;
  81         int     step;
  82 {
  83         /* Record the fact that we've found a new induction variable.
  84          * lnp points to the last instruction of the code that
  85          * increments the induction variable, i.e. a STL, DEL or INL.
  86          */
  87
  88         iv_p i;
  89
  90         i = newiv();
  91         i->iv_off = (TYPE(lnp) == OPSHORT ? (offset) SHORT(lnp) : OFFSET(lnp));
  92         i->iv_incr = lnp;       /* last instruction of increment code */
  93         i->iv_step = step;      /* step value */
  94         Ladd(i,&ivvars);
  95 }
  96
  97
  98 STATIC int sign(lnp)
  99         line_p lnp;
 100 {
 101         switch(INSTR(lnp)) {
 102                 case op_inc:
 103                 case op_inl:
 104                 case op_adi:
 105                 case op_adu:
 106                         return 1;
 107                 case op_dec:
 108                 case op_del:
 109                 case op_sbi:
 110                 case op_sbu:
 111                         return (-1);
 112                 default:
 113                         assert(FALSE);
 114         }
 115         /* NOTREACHED */
 116 }
 117
 118
 119 STATIC try_patterns(lnp)
 120         line_p lnp;
 121 {
 122         /* lnp is a STL x; try to recognize
 123          * one of the patterns:
 124          *  'LOAD const; LOAD x; ADD; STORE x'
 125          * or 'LOAD x; LOAD const; ADD or SUBTRACT;
 126          *     STORE x'
 127          * or 'LOAD x; INCREMENT/DECREMENT; STORE x'
 128          */
 129
 130         line_p l, l2;
 131
 132         l = PREV(lnp); /* instruction before lnp*/
 133         if (l == (line_p) 0) return;  /* no match possible */
 134         l2 = PREV(l);
 135         if (inc_or_dec(l)) {
 136                 if (is_same(l2,lnp)) {
 137                         /* e.g. LOL iv ; INC ; STL iv */
 138                         ivar(lnp,sign(l));
 139                 }
 140                 return;
 141         }
 142         if (is_add(lnp)) {
 143                 if(is_same(l2,lnp) && is_const(PREV(l2))) {
 144                         ivar(lnp,SHORT(PREV(l2)));
 145                         return;
 146                 }
 147         }
 148         if (plus_or_min(l)) {
 149                 if (is_const(l2) && is_same(PREV(l2),lnp)) {
 150                         ivar(lnp,sign(l) * SHORT(l2));
 151                 }
 152         }
 153 }
 154
 155
 156 induc_vars(loop,ivar_out, vars_out)
 157         loop_p loop;
 158         lset   *ivar_out, *vars_out;
 159 {
 160         /* Construct the set of induction variables. We use several
 161          * global variables computed by 'candidates'.
 162          */
 163
 164         Lindex i;
 165         line_p lnp;
 166         lset cand_iv, vars;
 167
 168         ivvars = Lempty_set();
 169         candidates(loop, &cand_iv, &vars);
 170         /* Find the set of all variables that are assigned precisely
 171          * once within the loop, within a firm block.
 172          * Also find all remaining local variables that are changed
 173          * within the loop.
 174          */
 175         if (Lnrelems(cand_iv) > 0) {
 176                 for (i = Lfirst(cand_iv); i != (Lindex) 0; i = Lnext(i,cand_iv)) {
 177                         lnp = (line_p) Lelem(i);
 178                         if (INSTR(lnp) == op_inl || INSTR(lnp) == op_del) {
 179                                 ivar(lnp,sign(lnp));
 180                         } else {
 181                                 try_patterns(lnp);
 182                         }
 183                 }
 184         }
 185         Ljoin(cand_iv, &vars);
 186         *ivar_out = ivvars;
 187         *vars_out = vars;
 188 }