util/ego/sr/sr_expr.c

   1 /* $Id: sr_expr.c,v 1.5 1994/06/24 10:32:16 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 _ E X P R . C
   9  *
  10  */
  11
  12
  13 #include <stdio.h>
  14 #include <em_mnem.h>
  15 #include "../share/types.h"
  16 #include "sr.h"
  17 #include "../share/debug.h"
  18 #include "../share/global.h"
  19 #include "../share/aux.h"
  20 #include "sr_aux.h"
  21 #include "../share/lset.h"
  22 #include "sr_iv.h"
  23
  24
  25
  26 #define ME_NONE         0
  27 #define ME_UNAIR        1
  28 #define ME_BINAIR       2
  29 #define ME_LOOPCONST    3
  30 #define ME_IV           4
  31
  32
  33
  34 STATIC iv_p last_iv;
  35 STATIC int  iv_sign;
  36 STATIC lset ivars, loopvars;
  37
  38 STATIC bool is_loadiv(lnp)
  39         line_p lnp;
  40 {
  41         /* See if lnp is a LOL iv instruction, where iv is an
  42          * induction variable of the set ivars. If so, set the
  43          * the global variable last_iv to its descriptor.
  44          */
  45
  46         Lindex i;
  47         iv_p iv;
  48         offset off;
  49
  50         if (INSTR(lnp) == op_lol) {
  51                 off = off_set(lnp);
  52                 for (i = Lfirst(ivars); i != (Lindex) 0; i = Lnext(i,ivars)) {
  53                         iv = (iv_p) Lelem(i);
  54                         if (iv->iv_off == off) {
  55                                 last_iv = iv;
  56                                 return TRUE;
  57                         }
  58                 }
  59         }
  60         return FALSE;
  61 }
  62
  63
  64
  65
  66 #define size_ok(l)      (TYPE(l) == OPSHORT && SHORT(l) == ws)
  67
  68
  69 STATIC int me_kind(l,sign_in,sign_out)
  70         line_p l;
  71         int    sign_in, *sign_out;
  72 {
  73         if (l != (line_p) 0) {
  74                 switch(INSTR(l)) {
  75                         case op_adi:
  76                         case op_adu:
  77                                 if (size_ok(l)) {
  78                                         *sign_out = sign_in;
  79                                         return ME_BINAIR;
  80                                 }
  81                                 break;
  82                         case op_sbi:
  83                         case op_sbu:
  84                                 if (size_ok(l)) {
  85                                         *sign_out = - sign_in;
  86                                         return ME_BINAIR;
  87                                 }
  88                                 break;
  89                         case op_ngi:
  90                                 if (size_ok(l)) {
  91                                         *sign_out = - sign_in;
  92                                         return ME_UNAIR;
  93                                 }
  94                                 break;
  95                         case op_inc:
  96                         case op_dec:
  97                                 *sign_out = sign_in;
  98                                 return ME_UNAIR;
  99                         case op_loc:
 100                                 return ME_LOOPCONST;
 101                         case op_lol:
 102                                 if (is_loadiv(l)) {
 103                                         iv_sign = sign_in;
 104                                         return ME_IV;
 105                                 }
 106                                 if (is_loopconst(l,loopvars)) return ME_LOOPCONST;
 107                 }
 108         }
 109         return ME_NONE;
 110 }
 111
 112
 113
 114 STATIC bool match_expr(l,iv_allowed,lbegin,iv_seen,sign)
 115         line_p l,*lbegin;
 116         bool   iv_allowed, *iv_seen;
 117         int    sign;
 118 {
 119         /* This routine is a top down parser for simple
 120          * EM expressions. It recognizes expressions that
 121          * have as operators + and - (unary - is also allowed)
 122          * and that have as operands a number of loop constants
 123          * (either a constant or a variable that is not
 124          * changed within the loop) and at most one induction
 125          * variable.
 126          * The parameter iv_allowed is propagated downwards
 127          * in the expression tree, indicating whether the
 128          * subexpression may use an induction variable as
 129          * operand. The parameter iv_seen is propagated
 130          * upwards, indicating if the subexpression has used
 131          * an induction variable. The parameter sign is
 132          * propagated downwards; it indicates the sign of
 133          * the subexpression. lbegin will point to the
 134          * beginning of the recognized subexpression
 135          * (it is an out parameter). Note that we scan the
 136          * EM text from right to left (i.e. top down).
 137          */
 138
 139         line_p l1;
 140         bool   iv_insubexpr;
 141         int    sign2;
 142
 143         switch(me_kind(l,sign,&sign2)) {
 144            case ME_UNAIR:
 145                 /* unairy operator, match one subexpression */
 146                 if (match_expr(PREV(l),iv_allowed,&l1,&iv_insubexpr,sign2)) {
 147                         *lbegin = l1;
 148                         *iv_seen = iv_insubexpr;
 149                         return TRUE;
 150                 }
 151                 return FALSE;
 152            case ME_BINAIR:
 153                 /* binairy operator, match two subexpressions */
 154                 if (match_expr(PREV(l), iv_allowed, &l1, &iv_insubexpr,sign2)) {
 155                         l = PREV(l1);
 156                         iv_allowed = iv_allowed && !iv_insubexpr;
 157                         if (match_expr(l,iv_allowed,&l1,
 158                                 &iv_insubexpr,sign)) {
 159                                 *lbegin = l1;
 160                                 *iv_seen = !iv_allowed || iv_insubexpr;
 161                                 return TRUE;
 162                         }
 163                 }
 164                 return FALSE; /* subexpression not recognized */
 165            case ME_LOOPCONST:
 166                 *lbegin = l;  /* expression is a loop constant */
 167                 *iv_seen = FALSE;
 168                 return TRUE;
 169            case ME_IV:
 170                 if (iv_allowed) {
 171                         *iv_seen = TRUE;
 172                         *lbegin = l;
 173                         return TRUE;
 174                 }
 175                 /* fall through ... */
 176            default:
 177                 return FALSE;
 178         }
 179 }
 180
 181
 182 bool is_ivexpr(l,ivs,vars,lbegin_out,iv_out,sign_out)
 183         line_p l, *lbegin_out;
 184         lset   ivs,vars;
 185         iv_p   *iv_out;
 186         int    *sign_out;
 187 {
 188         line_p l2;
 189         bool iv_seen;
 190
 191
 192         loopvars = vars;
 193         ivars = ivs;
 194         if (match_expr(l,TRUE,&l2,&iv_seen,1)) {
 195                 if (iv_seen) {
 196                         /* recognized a correct expression */
 197                         *lbegin_out = l2;
 198                         *iv_out     = last_iv;
 199                         *sign_out   = iv_sign;
 200                         return TRUE;
 201                 }
 202         }
 203         return FALSE;
 204 }