util/ego/sp/sp.c

   1 /* $Id: sp.c,v 1.6 1994/06/24 10:31:19 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 A C K   P O L L U T I O N
   7  *
   8  * S P . C
   9  */
  10
  11
  12 #include <stdio.h>
  13 #include <em_mnem.h>
  14 #include <em_spec.h>
  15 #include "../share/types.h"
  16 #include "../share/debug.h"
  17 #include "../share/global.h"
  18 #include "../share/files.h"
  19 #include "../share/get.h"
  20 #include "../share/put.h"
  21 #include "../share/lset.h"
  22 #include "../share/map.h"
  23 #include "../share/alloc.h"
  24 #include "../share/aux.h"
  25 #include "../share/go.h"
  26 #include "../share/stack_chg.h"
  27
  28
  29 /* Stack pollution throws away the ASP instructions after a procedure call.
  30  * This saves a lot of code, at the cost of some extra stack space.
  31  * ASPs that are part of a loop are not removed.
  32  */
  33
  34 #define BF_MARK         04
  35 #define MARK(b)         b->b_flags |= BF_MARK
  36 #define NOT_MARKED(b)   (!(b->b_flags&BF_MARK))
  37 #define IN_LOOP(b)      (Lnrelems(b->b_loops) > 0)
  38
  39 STATIC int Ssp;  /* number of optimizations */
  40
  41 /* According to the EM definition, the stack must be cleaned up
  42  * before any return. However, for some backends it causes no harm
  43  * if the stack is not cleaned up. If so, we can do Stack Pollution
  44  * more globally.
  45  */
  46
  47 STATIC int globl_sp_allowed;
  48
  49
  50 #define IS_ASP(l)       (INSTR(l) == op_asp && TYPE(l) == OPSHORT && SHORT(l) > 0)
  51
  52
  53 STATIC sp_machinit(f)
  54         FILE *f;
  55 {
  56         /* Read target machine dependent information for this phase */
  57         char s[100];
  58
  59         for (;;) {
  60                 while(getc(f) != '\n');
  61                 fscanf(f,"%s",s);
  62                 if (strcmp(s,"%%SP") == 0)break;
  63         }
  64         fscanf(f,"%d",&globl_sp_allowed);
  65 }
  66 comb_asps(l1,l2,b)
  67         line_p l1,l2;
  68         bblock_p b;
  69 {
  70         assert(INSTR(l1) == op_asp);
  71         assert(INSTR(l2) == op_asp);
  72         assert(TYPE(l1) == OPSHORT);
  73         assert(TYPE(l2) == OPSHORT);
  74
  75         SHORT(l2) += SHORT(l1);
  76         rm_line(l1,b);
  77 }
  78
  79
  80
  81
  82 stack_pollution(b)
  83         bblock_p b;
  84 {
  85         /* For every pair of successive ASP instructions in basic
  86          * block b, try to combine the two into one ASP.
  87          */
  88
  89         register line_p l;
  90         line_p asp,next = b->b_start;
  91         bool asp_seen = FALSE;
  92         int stack_diff,pop,push;
  93         bool ok;
  94
  95         do {
  96                 stack_diff = 0;
  97                 for (l = next; l != (line_p) 0; l = next)  {
  98                         next = l->l_next;
  99                         if (IS_ASP(l)) break;
 100                         if (asp_seen) {
 101                                 if (INSTR(l) == op_ret) {
 102                                         stack_diff -= SHORT(l);
 103                                 } else {
 104                                         line_change(l,&ok,&pop,&push);
 105                                         if (!ok || (stack_diff -= pop) < 0) {
 106                                                 /* can't eliminate last ASP */
 107                                                 asp_seen = FALSE;
 108                                         } else {
 109                                                 stack_diff += push;
 110                                         }
 111                                 }
 112                         }
 113                 }
 114                 if (asp_seen) {
 115                         if (l == (line_p) 0) {
 116                                 /* last asp of basic block */
 117                                 if (globl_sp_allowed &&
 118                                     NOT_MARKED(b) && !IN_LOOP(b)) {
 119                                         Ssp++;
 120                                         rm_line(asp,b);
 121                                 }
 122                         } else {
 123                                 /* try to combine with previous asp */
 124                                 if (SHORT(l) == stack_diff) {
 125                                         Ssp++;
 126                                         comb_asps(asp,l,b);
 127                                 }
 128                         }
 129                 }
 130                 asp = l;
 131                 asp_seen = TRUE;  /* use new ASP for next try! */
 132         } while (asp != (line_p) 0);
 133 }
 134
 135 STATIC bool block_save(b)
 136         bblock_p b;
 137 {
 138
 139         register line_p l;
 140         int stack_diff,pop,push;
 141         bool ok;
 142
 143         stack_diff = 0;
 144         for (l = b->b_start; l != (line_p) 0; l = l->l_next)  {
 145                 if (INSTR(l) == op_ret) {
 146                         stack_diff -= SHORT(l);
 147                         break;
 148                 }
 149                 line_change(l,&ok,&pop,&push);
 150                 /* printf("instr %d, pop %d,push %d,ok %d\n",INSTR(l),pop,push,ok);  */
 151                 if (!ok || (stack_diff -= pop) < 0) {
 152                         return FALSE;
 153                 } else {
 154                         stack_diff += push;
 155                 }
 156         }
 157         return stack_diff >= 0;
 158 }
 159
 160
 161
 162 STATIC mark_pred(b)
 163         bblock_p b;
 164 {
 165         Lindex i;
 166         bblock_p x;
 167
 168         for (i = Lfirst(b->b_pred); i != (Lindex) 0; i = Lnext(i,b->b_pred)) {
 169                 x = (bblock_p) Lelem(i);
 170                 if (NOT_MARKED(x)) {
 171                         MARK(x);
 172                         mark_pred(x);
 173                 }
 174         }
 175 }
 176
 177
 178
 179
 180
 181 STATIC mark_unsave_blocks(p)
 182         proc_p p;
 183 {
 184         register bblock_p b;
 185
 186         for (b = p->p_start; b != (bblock_p) 0; b = b->b_next) {
 187                 if (NOT_MARKED(b) && !block_save(b)) {
 188                         MARK(b);
 189                         mark_pred(b);
 190                 }
 191         }
 192 }
 193
 194
 195 sp_optimize(p)
 196         proc_p p;
 197 {
 198         register bblock_p b;
 199
 200         if (IS_ENTERED_WITH_GTO(p)) return;
 201         mark_unsave_blocks(p);
 202         for (b = p->p_start; b != 0; b = b->b_next) {
 203                 stack_pollution(b);
 204         }
 205 }
 206
 207
 208
 209
 210 main(argc,argv)
 211         int argc;
 212         char *argv[];
 213 {
 214         go(argc,argv,no_action,sp_optimize,sp_machinit,no_action);
 215         report("stack adjustments deleted",Ssp);
 216         exit(0);
 217 }
 218
 219
 220
 221
 222 /***** DEBUGGING:
 223
 224 debug_stack_pollution(p)
 225         proc_p p;
 226 {
 227         register bblock_p b;
 228         register line_p l;
 229         int lcnt,aspcnt,instr;
 230
 231         for (b = p->p_start; b != 0; b = b->b_next) {
 232                 lcnt = 0; aspcnt = 0;
 233                 for (l = b->b_start; l != 0; l= l->l_next) {
 234                         instr = INSTR(l);
 235                         if (instr >= sp_fmnem && instr <= sp_lmnem) {
 236                                 lcnt++;
 237                                 if (instr == op_asp && off_set(l) > 0) {
 238                                         aspcnt++;
 239                                 }
 240                         }
 241                 }
 242                 printf("%d\t%d\n",aspcnt,lcnt);
 243         }
 244 }
 245
 246 */