util/ego/cs/cs_elim.c

   1 /* $Id: cs_elim.c,v 1.7 1994/06/24 10:22:09 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_reg.h>
   7 #include <em_mnem.h>
   8 #include "../share/types.h"
   9 #include "../share/alloc.h"
  10 #include "../share/lset.h"
  11 #include "../share/aux.h"
  12 #include "../share/global.h"
  13 #include "../share/debug.h"
  14 #include "cs.h"
  15 #include "cs_avail.h"
  16 #include "cs_alloc.h"
  17 #include "cs_aux.h"
  18 #include "cs_debug.h"
  19 #include "cs_profit.h"
  20 #include "cs_partit.h"
  21 #include "cs_debug.h"
  22
  23 STATIC dlink(l1, l2)
  24         line_p l1, l2;
  25 {
  26         /* Doubly link the lines in l1 and l2. */
  27
  28         if (l1 != (line_p) 0)
  29                 l1->l_next = l2;
  30         if (l2 != (line_p) 0)
  31                 l2->l_prev = l1;
  32 }
  33
  34 STATIC remove_lines(first, last)
  35         line_p first, last;
  36 {
  37         /* Throw away the lines between and including first and last.
  38          * Don't worry about any pointers; the (must) have been taken care of.
  39          */
  40         register line_p lnp, next;
  41
  42         last->l_next = (line_p) 0; /* Delimit the list. */
  43         for (lnp = first; lnp != (line_p) 0; lnp = next) {
  44                 next = lnp->l_next;
  45                 oldline(lnp);
  46         }
  47 }
  48
  49 STATIC bool contained(ocp1, ocp2)
  50         occur_p ocp1, ocp2;
  51 {
  52         /* Determine whether ocp1 is contained within ocp2. */
  53
  54         register line_p lnp, next;
  55
  56         for (lnp = ocp2->oc_lfirst; lnp != (line_p) 0; lnp = next) {
  57                 next = lnp != ocp2->oc_llast ? lnp->l_next : (line_p) 0;
  58
  59                 if (lnp == ocp1->oc_llast) return TRUE;
  60         }
  61         return FALSE;
  62 }
  63
  64 STATIC delete(ocp, start)
  65         occur_p ocp;
  66         avail_p start;
  67 {
  68         /* Delete all occurrences that are contained within ocp.
  69          * They must have been entered in the list before start:
  70          * if an expression is contained with an other, its operator line
  71          * appears before the operator line of the other because EM-expressions
  72          * are postfix.
  73          */
  74         register avail_p ravp;
  75         register Lindex i, next;
  76
  77         for (ravp = start; ravp != (avail_p) 0; ravp = ravp->av_before) {
  78                 for (i = Lfirst(ravp->av_occurs); i != (Lindex) 0; i = next) {
  79                         next = Lnext(i, ravp->av_occurs);
  80
  81                         if (contained(occ_elem(i), ocp)) {
  82                                 OUTTRACE("delete contained occurrence", 0);
  83 #                               ifdef TRACE
  84                                         SHOWOCCUR(occ_elem(i));
  85 #                               endif
  86                                 oldoccur(occ_elem(i));
  87                                 Lremove(Lelem(i), &ravp->av_occurs);
  88                         }
  89                 }
  90         }
  91 }
  92
  93 STATIC complete_aar(lnp, instr, descr_vn)
  94         line_p lnp;
  95         int instr;
  96         valnum descr_vn;
  97 {
  98         /* Lnp is an instruction that loads the address of an array-element.
  99          * Instr tells us what effect we should achieve; load (instr is op_lar)
 100          * or store (instr is op_sar) this array-element. Descr_vn is the
 101          * valuenumber of the address of the descriptor of this array.
 102          * We append a loi or sti of the correct number of bytes.
 103          */
 104         register line_p lindir;
 105
 106         lindir = int_line(array_elemsize(descr_vn));
 107         lindir->l_instr = instr == op_lar ? op_loi : op_sti;
 108         dlink(lindir, lnp->l_next);
 109         dlink(lnp, lindir);
 110 }
 111
 112 STATIC replace(ocp, tmp, avp)
 113         occur_p ocp;
 114         offset tmp;
 115         avail_p avp;
 116 {
 117         /* Replace the lines in the occurrence in ocp by a load of the
 118          * temporary with offset tmp.
 119          */
 120         register line_p lol, first, last;
 121
 122         assert(avp->av_size == ws || avp->av_size == 2*ws);
 123
 124         first = ocp->oc_lfirst; last = ocp->oc_llast;
 125
 126         lol = int_line(tmp);
 127         lol->l_instr = avp->av_size == ws ? op_lol : op_ldl;
 128         dlink(lol, last->l_next);
 129
 130         if (first->l_prev == (line_p) 0) ocp->oc_belongs->b_start = lol;
 131         dlink(first->l_prev, lol);
 132
 133         if (avp->av_instr == (byte) op_aar) {
 134                 /* There may actually be a LAR or a SAR instruction; in that
 135                  * case we have to complete the array-instruction.
 136                  */
 137                 register int instr = INSTR(last);
 138
 139                 if (instr != op_aar) complete_aar(lol, instr, avp->av_othird);
 140         }
 141
 142         /* Throw away the by now useless lines. */
 143         remove_lines(first, last);
 144 }
 145
 146 STATIC append(avp, tmp)
 147         avail_p avp;
 148         offset tmp;
 149 {
 150         /* Avp->av_found points to a line with an operator in it. This
 151          * routine emits a sequence of instructions that saves the result
 152          * in a local with offset tmp. In most cases we just append
 153          * avp->av_found with stl/sdl tmp and lol/ldl tmp depending on
 154          * avp->av_size. If however the operator is an aar contained
 155          * within a lar or sar, we must first generate the aar.
 156          */
 157         register line_p stl, lol;
 158
 159         assert(avp->av_size == ws || avp->av_size == 2*ws);
 160
 161         stl = int_line(tmp);
 162         stl->l_instr = avp->av_size == ws ? op_stl : op_sdl;
 163         lol = int_line(tmp);
 164         lol->l_instr = avp->av_size == ws ? op_lol : op_ldl;
 165
 166         dlink(lol, avp->av_found->l_next);
 167         dlink(stl, lol);
 168         dlink(avp->av_found, stl);
 169
 170         if (avp->av_instr == (byte) op_aar) {
 171                 register int instr = INSTR(avp->av_found);
 172
 173                 if (instr != op_aar) {
 174                         complete_aar(lol, instr, avp->av_othird);
 175                         avp->av_found->l_instr = op_aar;
 176                 }
 177         }
 178 }
 179
 180 STATIC set_replace(avp, tmp)
 181         avail_p avp;
 182         offset tmp;
 183 {
 184         /* Avp->av_occurs is now a set of occurrences, each of which will be
 185          * replaced by a reference to a local.
 186          * Each time we eliminate an expression, we delete from our
 187          * list those expressions that are physically contained in them,
 188          * because we cannot eliminate them again.
 189          */
 190         register Lindex i;
 191         register lset s = avp->av_occurs;
 192
 193         for (i = Lfirst(s); i != (Lindex) 0; i = Lnext(i, s)) {
 194                 OUTVERBOSE("eliminate duplicate", 0);
 195                 SHOWOCCUR(occ_elem(i));
 196                 Scs++;
 197                 delete(occ_elem(i), avp->av_before);
 198                 replace(occ_elem(i), tmp, avp);
 199         }
 200 }
 201
 202 STATIC int reg_score(enp)
 203         entity_p enp;
 204 {
 205         /* Enp is a local that will go into a register.
 206          * We return its score upto now.
 207          */
 208         assert(is_regvar(enp->en_loc));
 209         return regv_arg(enp->en_loc, 4);
 210 }
 211
 212 STATIC line_p gen_mesreg(off, avp, pp)
 213         offset off;
 214         avail_p avp;
 215         proc_p pp;
 216 {
 217         /* Generate a register message for the local that will hold the
 218          * result of the expression in avp, at the appropriate place in
 219          * the procedure in pp.
 220          */
 221         register line_p reg;
 222
 223         reg = reg_mes(off, (short) avp->av_size, regtype(avp->av_instr), 0);
 224         appnd_line(reg, pp->p_start->b_start);
 225
 226         return reg;
 227 }
 228
 229 STATIC change_score(mes, score)
 230         line_p mes;
 231         int score;
 232 {
 233         /* Change the score in the register message in mes to score. */
 234
 235         register arg_p ap = ARG(mes);
 236
 237         ap = ap->a_next; /* Offset. */
 238         ap = ap->a_next; /* Size. */
 239         ap = ap->a_next; /* Type. */
 240         ap = ap->a_next; /* Score. */
 241
 242         ap->a_a.a_offset = score;
 243 }
 244
 245 eliminate(pp)
 246         proc_p pp;
 247 {
 248         /* Eliminate costly common subexpressions within procedure pp.
 249          * We scan the available expressions in - with respect to time found -
 250          * reverse order, to find largest first, e.g. `A + B + C' before
 251          * `A + B'.
 252          * We do not eliminate an expression when the size
 253          * is not one of ws or 2*ws, because then we cannot use lol or ldl.
 254          * Code is appended to the first occurrence of the expression
 255          * to store the result into a local.
 256          */
 257         register avail_p ravp;
 258         register int score;
 259         register offset tmp;
 260         register line_p mes;
 261
 262         for (ravp = avails; ravp != (avail_p) 0; ravp = ravp->av_before) {
 263
 264                 if (ravp->av_size != ws && ravp->av_size != 2*ws) continue;
 265
 266                 if (ravp->av_saveloc == (entity_p) 0) {
 267                         /* We save it ourselves. */
 268                         score = 2; /* Stl and lol. */
 269                 } else {
 270                         score = reg_score(ravp->av_saveloc);
 271                 }
 272                 if (desirable(ravp)) {
 273                         score += Lnrelems(ravp->av_occurs);
 274                         OUTTRACE("temporary local score %d", score);
 275                         if (ravp->av_saveloc != (entity_p) 0) {
 276                                 tmp = ravp->av_saveloc->en_loc;
 277                                 mes = find_mesreg(tmp);
 278                                 OUTVERBOSE("re-using %ld(LB)", tmp);
 279                         } else {
 280                                 tmp = tmplocal(pp,  ravp->av_size);
 281                                 mes = gen_mesreg(tmp, ravp, pp);
 282                                 append(ravp, tmp);
 283                         }
 284                         change_score(mes, score);
 285                         set_replace(ravp, tmp);
 286                 }
 287         }
 288 }