util/ego/cs/cs_profit.c

   1 /* $Id: cs_profit.c,v 1.14 1995/03/17 12:32:47 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 <stdio.h>
   7 #include <em_mnem.h>
   8 #include <em_spec.h>
   9 #include "../share/types.h"
  10 #include "../share/debug.h"
  11 #include "../share/global.h"
  12 #include "../share/aux.h"
  13 #include "../share/cset.h"
  14 #include "../share/lset.h"
  15 #include "cs.h"
  16 #include "cs_aux.h"
  17 #include "cs_debug.h"
  18 #include "cs_avail.h"
  19 #include "cs_partit.h"
  20
  21 STATIC cset     addr_modes;
  22 STATIC cset     cheaps;
  23 STATIC cset     forbidden;
  24 STATIC cset     sli_counts;
  25 STATIC short    LX_threshold;
  26 STATIC short    AR_limit;
  27
  28 STATIC get_instrs(f, s_p)
  29         FILE *f;
  30         cset *s_p;
  31 {
  32         /* Read a set of integers from inputfile f into *s_p.
  33          * Such a set must be delimited by a negative number.
  34          */
  35         int instr;
  36
  37         fscanf(f, "%d", &instr);
  38         while (instr >= 0) {
  39                 Cadd((Celem_t) instr, s_p);
  40                 fscanf(f, "%d", &instr);
  41         }
  42 }
  43
  44 STATIC choose_cset(f, s_p, max)
  45         FILE *f;
  46         cset *s_p;
  47 {
  48         /* Read two compact sets of integers from inputfile f.
  49          * Choose the first if we optimize with respect to time,
  50          * the second if we optimize with respect to space, as
  51          * indicated by time_space_ratio.
  52          */
  53         cset cs1, cs2; /* Two dummy sets. */
  54
  55         *s_p = Cempty_set((short) max);
  56
  57         cs1 = Cempty_set((short) max);
  58         get_instrs(f, &cs1);
  59         cs2 = Cempty_set((short) max);
  60         get_instrs(f, &cs2);
  61
  62         Ccopy_set(time_space_ratio >= 50 ? cs1 : cs2, s_p);
  63
  64         Cdeleteset(cs1); Cdeleteset(cs2);
  65 }
  66
  67 cs_machinit(f)
  68         FILE *f;
  69 {
  70         char s[100];
  71         int time, space;
  72
  73         /* Find piece that is relevant for this phase. */
  74         do {
  75                 while (getc(f) != '\n');
  76                 fscanf(f, "%s", s);
  77         } while (strcmp(s, "%%CS"));
  78
  79         /* Choose a set of instructions which must only be eliminated
  80          * if they are at the root of another expression.
  81          */
  82         choose_cset(f, &addr_modes, sp_lmnem);
  83
  84         /* Choose a set of cheap instructions; i.e. instructions that
  85          * are cheaper than a move to save the result of such an
  86          * instruction.
  87          */
  88         choose_cset(f, &cheaps, sp_lmnem);
  89
  90         /* Read how many lexical levels back an LXL/LXA instruction
  91          * must at least look before it will be eliminated.
  92          */
  93         fscanf(f, "%d %d", &time, &space);
  94         LX_threshold = time_space_ratio >= 50 ? time : space;
  95
  96         /* Read what the size of an array-element may be,
  97          * before we think that it is to big to replace
  98          * a LAR/SAR of it by AAR LOI/STI <size>.
  99          */
 100         fscanf(f, "%d", &space);
 101         AR_limit = space;
 102
 103         /* Read for what counts we must not eliminate an SLI instruction
 104          * when it is part of an array-index computation.
 105          */
 106         choose_cset(f, &sli_counts, 8 * ws);
 107
 108         /* Read a set of instructions which we do not want to eliminate.
 109          * Note: only instructions need be given that may in principle
 110          * be eliminated, but for which better code can be generated
 111          * when they stay, and with which is not dealt in the common
 112          * decision routines.
 113          */
 114         choose_cset(f, &forbidden, sp_lmnem);
 115 }
 116
 117 STATIC bool sli_no_eliminate(lnp)
 118         line_p lnp;
 119 {
 120         /* Return whether the SLI-instruction in lnp is part of
 121          * an array-index computation, and should not be eliminated.
 122          */
 123         offset cst;
 124
 125         return  lnp->l_prev != (line_p) 0 && INSTR(lnp->l_prev) == op_loc &&
 126                 lnp->l_next != (line_p) 0 && INSTR(lnp->l_next) == op_ads &&
 127                 ((cst = off_set(lnp->l_prev)), cst == (Celem_t) cst) &&
 128                 Cis_elem((Celem_t) cst, sli_counts)
 129                 ;
 130 }
 131
 132 STATIC bool gains(avp)
 133         avail_p avp;
 134 {
 135         /* Return whether we can gain something, when we eliminate
 136          * an expression such as in avp. We just glue together some
 137          * heuristics with some user-supplied stuff.
 138          */
 139         if (Cis_elem(avp->av_instr & BMASK, forbidden))
 140                 return FALSE;
 141
 142         if (avp->av_instr == (byte) op_lxa || avp->av_instr == (byte) op_lxl)
 143                 return off_set(avp->av_found) >= LX_threshold;
 144
 145         if (avp->av_instr == (byte) op_sli || avp->av_instr == (byte) op_slu)
 146                 return ! sli_no_eliminate(avp->av_found);
 147
 148         if (avp->av_instr == (byte) op_ads &&
 149             avp->av_found->l_prev &&
 150             ( INSTR(avp->av_found->l_prev) == op_sli ||
 151               INSTR(avp->av_found->l_prev) == op_slu))
 152                 return ! sli_no_eliminate(avp->av_found->l_prev);
 153
 154         if (Cis_elem(avp->av_instr & BMASK, addr_modes))
 155                 return instrgroup(avp->av_found->l_prev) != SIMPLE_LOAD;
 156
 157         if (Cis_elem(avp->av_instr & BMASK, cheaps))
 158                 return avp->av_saveloc != (entity_p) 0;
 159
 160         return TRUE;
 161 }
 162
 163 STATIC bool okay_lines(avp, ocp)
 164         avail_p avp;
 165         occur_p ocp;
 166 {
 167         register line_p lnp, next;
 168         offset sz;
 169
 170         for (lnp = ocp->oc_lfirst; lnp != (line_p) 0; lnp = next) {
 171                 next = lnp != ocp->oc_llast ? lnp->l_next : (line_p) 0;
 172
 173                 if (INSTR(lnp) < sp_fmnem || INSTR(lnp) > sp_lmnem)
 174                         return FALSE;
 175                 if (!stack_group(INSTR(lnp))) {
 176                         /* Check for SAR-instruction. */
 177                         if (INSTR(lnp) != op_sar || next != (line_p) 0)
 178                                 return FALSE;
 179                 }
 180         }
 181         /* All lines in this occurrence can in principle be eliminated;
 182          * no stores, messages, calls etc.
 183          * We now check whether it is desirable to treat a LAR or a SAR
 184          * as an AAR LOI/STI. This depends on the size of the array-elements.
 185          */
 186         if (INSTR(ocp->oc_llast) == op_lar || INSTR(ocp->oc_llast) == op_sar) {
 187                 sz = array_elemsize(avp->av_othird);
 188                 if (sz == UNKNOWN_SIZE) return FALSE;
 189                 if (avp->av_instr == (byte) op_aar && time_space_ratio < 50) {
 190                         return sz <= AR_limit;
 191                 }
 192         }
 193         return TRUE;
 194 }
 195
 196 bool desirable(avp)
 197         avail_p avp;
 198 {
 199         register Lindex i, next;
 200
 201         if (!gains(avp)) {
 202                 OUTTRACE("no gain", 0);
 203                 SHOWAVAIL(avp);
 204                 return FALSE;
 205         }
 206
 207         /* Walk through the occurrences to see whether it is okay to
 208          * eliminate them. If not, remove them from the set.
 209          */
 210         for (i = Lfirst(avp->av_occurs); i != (Lindex) 0; i = next) {
 211                 next = Lnext(i, avp->av_occurs);
 212
 213                 if (!okay_lines(avp, occ_elem(i))) {
 214                         OUTTRACE("may not eliminate", 0);
 215 #                       ifdef TRACE
 216                                 SHOWOCCUR(occ_elem(i));
 217 #                       endif
 218                         oldoccur(occ_elem(i));
 219                         Lremove(Lelem(i), &avp->av_occurs);
 220                 }
 221         }
 222
 223         return Lnrelems(avp->av_occurs) > 0;
 224 }