util/ego/sr/sr.c

   1 /* $Id: sr.c,v 1.11 1994/06/24 10:31:56 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
   9 #include <stdio.h>
  10 #include "../share/types.h"
  11 #include "sr.h"
  12 #include "../share/debug.h"
  13 #include "../share/global.h"
  14 #include "../share/files.h"
  15 #include "../share/get.h"
  16 #include "../share/put.h"
  17 #include "../share/lset.h"
  18 #include "../share/map.h"
  19 #include "../share/alloc.h"
  20 #include "../share/go.h"
  21 #include "../share/aux.h"
  22 #include "sr_aux.h"
  23 #include "sr_iv.h"
  24
  25 /* Strength reduction tries to change expensive operators occurring
  26  * in a loop into cheaper operators. The expensive operators considered
  27  * are multiplication, left-shift and array referencing.
  28  * The transformations can be expressed in C as:
  29  *
  30  * [1]:         for (i = e1; i <= e2; i++)
  31  *                      print(118*i);
  32  *   becomes:
  33  *              for (i = e1, t = 118*e1; i <= e2; i++, t += 118)
  34  *                      print(t);
  35  *
  36  * [2]:         for (i = e1; i <= e2; i++)
  37  *                      print(a[i]);
  38  *   becomes:
  39  *              for (i = e1, p = &a[i]; i <= e2; i++, p++)
  40  *                      print(*p);
  41  * The latter optimization is suppressed if array bound checking
  42  * is required.
  43  */
  44
  45 /* Machine and/or language dependent parameters: */
  46
  47 int ovfl_harmful;
  48 int arrbound_harmful;
  49 int sli_threshold;
  50
  51 int Ssr;  /* #optimizations found */
  52
  53 sr_machinit(f)
  54         FILE *f;
  55 {
  56         /* Read target machine dependent information */
  57         char s[100];
  58
  59
  60         for (;;) {
  61                 while(getc(f) != '\n');
  62                 fscanf(f,"%s",s);
  63                 if (strcmp(s,"%%SR") == 0)break;
  64         }
  65         fscanf(f,"%d",&ovfl_harmful);
  66         fscanf(f,"%d",&arrbound_harmful);
  67         fscanf(f,"%d",&sli_threshold);
  68 }
  69
  70 STATIC del_ivs(ivs)
  71         lset ivs;
  72 {
  73         /* Delete the set of iv structs */
  74
  75         Lindex i;
  76
  77         for (i = Lfirst(ivs); i != (Lindex) 0; i = Lnext(i,ivs)) {
  78                 oldiv(Lelem(i));
  79         }
  80         Ldeleteset(ivs);
  81 }
  82
  83
  84 STATIC do_loop(loop)
  85         loop_p loop;
  86 {
  87         lset ivs, vars;
  88
  89         OUTTRACE("going to process loop %d",loop->lp_id);
  90         induc_vars(loop,&ivs, &vars);
  91         /* Build a set of iv_structs, one for every induction
  92          * variable of the loop, i.e. a variable i that
  93          * is changed only by  i := i + c, where c is a loop constant.
  94          * Also detects variables that are changed (including induction
  95          * variables!).
  96          */
  97         OUTTRACE("loop has %d induction variables",Lnrelems(ivs));
  98         if (Lnrelems(ivs) > 0) {
  99                 strength_reduction(loop,ivs,vars);
 100                 /* Perform strength reduction. Reduce:
 101                  *    iv * c    to addition
 102                  *    a[iv]     to indirection (*p)
 103                  *     (unless array bound checking is required)
 104                  */
 105         }
 106         del_ivs(ivs);
 107         Ldeleteset(vars);
 108 }
 109
 110
 111
 112 STATIC loopblocks(p)
 113         proc_p p;
 114 {
 115         /* Compute the LP_BLOCKS sets for all loops of p */
 116
 117         register bblock_p b;
 118         register Lindex i;
 119
 120         for (b = p->p_start; b != (bblock_p) 0; b = b->b_next) {
 121                 for (i = Lfirst(b->b_loops); i != (Lindex) 0;
 122                    i = Lnext(i,b->b_loops)) {
 123                         Ladd(b,&(((loop_p) Lelem(i))->LP_BLOCKS));
 124                 }
 125         }
 126 }
 127
 128
 129
 130 STATIC opt_proc(p)
 131         proc_p p;
 132 {
 133         /* Optimize all loops of one procedure. We first do all
 134          * outer loops at the lowest nesting level and proceed
 135          * in the inwards direction.
 136          */
 137
 138         Lindex i;
 139         loop_p lp,outermost;
 140         int min_level;
 141
 142         for (;;) {
 143                 min_level = 1000;
 144                 outermost = 0;
 145                 for (i = Lfirst(p->p_loops); i != (Lindex) 0;
 146                      i = Lnext(i,p->p_loops)) {
 147                         lp = (loop_p) Lelem(i);
 148                         if (!lp->LP_DONE && lp->lp_level < min_level) {
 149                                 min_level = lp->lp_level;
 150                                 outermost = lp;
 151                         }
 152                 }
 153                 if (! outermost) break;
 154                 do_loop(outermost);
 155                 outermost->LP_DONE = TRUE;
 156                 OUTTRACE("loop %d processed",outermost->lp_id);
 157         }
 158 }
 159
 160
 161
 162 STATIC bblock_p header(lp)
 163         loop_p lp;
 164 {
 165         /* Try to determine the 'header' block of loop lp.
 166          * If 'e' is the entry block of loop L, then block 'b' is
 167          * called the header block of L, iff:
 168          *      SUCC(b) = {e} & b dominates e.
 169          * If lp has no header block, 0 is returned.
 170          */
 171
 172         bblock_p x = lp->lp_entry->b_idom;
 173
 174         if (x != (bblock_p) 0 && Lnrelems(x->b_succ) == 1 &&
 175             (bblock_p) Lelem(Lfirst(x->b_succ)) == lp->lp_entry) {
 176                 return x;
 177         }
 178         return (bblock_p) 0;
 179 }
 180
 181
 182
 183 STATIC sr_extproc(p)
 184         proc_p p;
 185 {
 186         /* Allocate the extended data structures for procedure p */
 187
 188         register loop_p lp;
 189         register Lindex pi;
 190
 191         for (pi = Lfirst(p->p_loops); pi != (Lindex) 0;
 192            pi = Lnext(pi,p->p_loops)) {
 193                 lp = (loop_p) Lelem(pi);
 194                 lp->lp_extend = newsrlpx();
 195                 lp->LP_HEADER = header(lp);
 196                 if (lp->LP_HEADER) {
 197                         lp->LP_INSTR = last_instr(lp->LP_HEADER);
 198                 }
 199         }
 200 }
 201
 202
 203 STATIC sr_cleanproc(p)
 204         proc_p p;
 205 {
 206         /* Remove the extended data structures for procedure p */
 207
 208         register loop_p lp;
 209         register Lindex pi;
 210
 211
 212         for (pi = Lfirst(p->p_loops); pi != (Lindex) 0;
 213            pi = Lnext(pi,p->p_loops)) {
 214                 lp = (loop_p) Lelem(pi);
 215                 oldsrlpx(lp->lp_extend);
 216         }
 217 }
 218
 219
 220 sr_optimize(p)
 221         proc_p p;
 222 {
 223         if (IS_ENTERED_WITH_GTO(p)) return;
 224         sr_extproc(p);
 225         loopblocks(p);
 226         opt_proc(p);
 227         sr_cleanproc(p);
 228 }
 229
 230
 231
 232 main(argc,argv)
 233         int argc;
 234         char *argv[];
 235 {
 236         go(argc,argv,no_action,sr_optimize,sr_machinit,no_action);
 237         report("strength reductions",Ssr);
 238         exit(0);
 239 }