util/ego/cj/cj.c

   1 /* $Id: cj.c,v 1.10 1994/06/24 10:20: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 /* C R O S S   J U M P I N G
   7  *
   8  * CJ.H
   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/def.h"
  26 #include "../share/stack_chg.h"
  27 #include "../share/go.h"
  28
  29
  30 /* Cross jumping performs optimzations like:
  31  *
  32  *       if cond then goto L1;                   if cond then goto L1
  33  *       S1;                     ----->          S1;
  34  *       S2;                                     goto L3;
  35  *       goto L2;                               L1:
  36  *      L1:                                      S3;
  37  *       S3;                                    L3:
  38  *       S2;                                     S2;
  39  *      L2:
  40  *
  41  * CJ looks for two basic blocks b1 and b2 with the following properties:
  42  *  - there exists a basic block S such that SUCC(b1) = SUCC(b2) = {S}
  43  *    (so both have only 1 successor)
  44  *  - the last N (N > 0) instructions of b1 and b2, not counting a possible
  45  *    BRAnch instruction, are the same.
  46  * As a result of the first condition, at least of the two blocks must end
  47  * on an (unconditional) BRAnch instruction. If both end on a BRA, one block
  48  * is chosen at random. Assume this block is b1. A new label L is put just
  49  * before the N common instructions of block b2 (so this block is split
  50  * into two). The BRA of b1 is changed into a BRA L. So dynamically the same
  51  * instructions are executed in a slightly different order; yet the size of
  52  * the code has become smaller.
  53  */
  54
  55
  56 STATIC int Scj;  /* number of optimizations found */
  57
  58 STATIC showinstr();
  59
  60
  61
  62 #define DLINK(l1,l2)    l1->l_next=l2; l2->l_prev=l1
  63
  64
  65 STATIC bool same_instr(l1,l2)
  66         line_p l1,l2;
  67 {
  68         /* See if l1 and l2 are the same instruction */
  69
  70         if (l1 == 0 || l2 == 0 || TYPE(l1) != TYPE(l2)) return FALSE;
  71         if (INSTR(l1) != INSTR(l2)) return FALSE;
  72         switch(TYPE(l1)) {
  73                 case OPSHORT: return SHORT(l1) == SHORT(l2);
  74                 case OPOFFSET: return OFFSET(l1) == OFFSET(l2);
  75                 case OPPROC: return PROC(l1) == PROC(l2);
  76                 case OPOBJECT: return OBJ(l1) == OBJ(l2);
  77                 case OPINSTRLAB: return INSTRLAB(l1) == INSTRLAB(l2);
  78                 case OPNO: return TRUE;
  79                 default: return FALSE;
  80         }
  81 }
  82
  83
  84
  85 STATIC line_p last_mnem(b)
  86         bblock_p b;
  87 {
  88         /* Determine the last line of a list */
  89
  90         register line_p l;
  91
  92         for (l = b->b_start; l->l_next != (line_p) 0; l = l->l_next);
  93         while (l != (line_p) 0 && (INSTR(l) < sp_fmnem || INSTR(l) > sp_lmnem)) {
  94                 l = PREV(l);
  95         }
  96         return l;
  97 }
  98
  99
 100 STATIC bool is_desirable(text)
 101         line_p text;
 102 {
 103         /* We avoid to generate a BRAnch in the middle of some expression,
 104          * as the code generator will write the contents of the fakestack
 105          * to the real stack if it encounters a BRA. We do not avoid to
 106          * split the parameter-pushing code of a subroutine call into two,
 107          * as the parameters are pushed on the real stack anyway.
 108          * So e.g. "LOL a ; LOL b; ADI" will not be split, but
 109          * "LOL a; LOL b; CAL f" may be split.
 110          */
 111
 112         line_p l;
 113         bool ok;
 114         int stack_diff,pop,push;
 115
 116         stack_diff = 0;
 117         for (l = text; l != (line_p) 0; l = l->l_next) {
 118                 switch(INSTR(l)) {
 119                         case op_cal:
 120                         case op_asp:
 121                         case op_bra:
 122                                 return TRUE;
 123                 }
 124                 line_change(l,&ok,&pop,&push);
 125                 /* printf("instr %d, pop %d, push %d, ok %d\n",INSTR(l),pop,push,ok); */
 126                 if (!ok || (stack_diff -= pop) < 0) {
 127                         return FALSE;
 128                 } else {
 129                         stack_diff += push;
 130                 }
 131         }
 132         return TRUE;
 133 }
 134
 135
 136 STATIC cp_loops(b1,b2)
 137         bblock_p b1,b2;
 138 {
 139         /* Copy the loopset of b2 to b1 */
 140
 141         Lindex i;
 142         loop_p lp;
 143         for (i = Lfirst(b2->b_loops); i != (Lindex) 0;
 144              i = Lnext(i,b2->b_loops)) {
 145                 lp = (loop_p) Lelem(i);
 146                 Ladd(lp,&b1->b_loops);
 147         }
 148 }
 149
 150
 151 STATIC jump_cross(l1,l2,b1,b2)
 152         line_p l1,l2;
 153         bblock_p b1,b2;
 154 {
 155         /* A cross-jump from block b2 to block b1 is found; the code in
 156          * block b2 from line l2 up to the BRAnch is removed; block b1 is
 157          * split into two; the second part consists of a new label
 158          * followed by the code from l1 till the end of the block.
 159          */
 160
 161         line_p l;
 162         bblock_p b;
 163         bblock_p s;
 164
 165         /* First adjust the control flow graph */
 166         b = freshblock();  /* create a new basic block */
 167         b->b_succ = b1->b_succ;
 168         /* SUCC(b1) = {b} */
 169         b1->b_succ = Lempty_set(); Ladd(b,&b1->b_succ);
 170         /* SUCC(b2) = {b} */
 171         Ldeleteset(b2->b_succ); b2->b_succ = Lempty_set(); Ladd(b,&b2->b_succ);
 172         /* PRED(b) = {b1,b2} */
 173         b->b_pred = Lempty_set(); Ladd(b1,&b->b_pred); Ladd(b2,&b->b_pred);
 174         /* PRED(SUCC(b)) := PRED(SUCC(b)) - {b1,b2} + {b} */
 175         assert(Lnrelems(b->b_succ) == 1);
 176         s = (bblock_p) Lelem(Lfirst(b->b_succ));
 177         Lremove(b1,&s->b_pred); Lremove(b2,&s->b_pred); Ladd(b,&s->b_pred);
 178         cp_loops(b,b1);
 179         b->b_idom = common_dom(b1,b2);
 180         b->b_flags = b1->b_flags;
 181         b->b_next = b1->b_next;
 182         b1->b_next = b;
 183
 184         /* Now adjust the EM text */
 185         l = PREV(l1);
 186         while (l && INSTR(l) == op_lab) {
 187                 l1 = l;
 188                 l = PREV(l);
 189         }
 190         if (l == (line_p) 0) {
 191                 b1->b_start = (line_p) 0;
 192         } else {
 193                 l->l_next = (line_p) 0;
 194         }
 195         if (INSTR(l1) == op_lab) {
 196                 l = l1;
 197         }
 198         else {
 199                 l = newline(OPINSTRLAB);
 200                 l->l_instr = op_lab;
 201                 INSTRLAB(l) = freshlabel();
 202                 DLINK(l,l1);
 203         }
 204         b->b_start = l;
 205         for (l = l2; INSTR(l) != op_bra;) {
 206                 line_p next = l->l_next;
 207
 208                 assert (l != (line_p) 0);
 209                 rm_line(l,b2);
 210                 l = next;
 211         }
 212         INSTRLAB(l) = INSTRLAB(b->b_start);
 213 }
 214
 215
 216 STATIC bool try_tail(b1,b2)
 217         bblock_p b1,b2;
 218 {
 219         /* See if b1 and b2 end on the same sequence of instructions */
 220
 221         line_p l1,l2;
 222         bblock_p b = (bblock_p) 0;
 223         int cnt = 0;
 224         /* printf("try block %d and %d\n",b1->b_id,b2->b_id); */
 225
 226         if (b1->b_start == (line_p) 0 || b2->b_start == (line_p) 0) return FALSE;
 227         l1 = last_mnem(b1);
 228         l2 = last_mnem(b2);
 229         if (l1 == (line_p) 0 || l2 == (line_p) 0) return FALSE;
 230         /* printf("consider:\n"); showinstr(l1); showinstr(l2); */
 231         if (INSTR(l1) == op_bra) {
 232                 b = b1;
 233                 l1 = PREV(l1);
 234         }
 235         if (INSTR(l2) == op_bra) {
 236                 b = b2;
 237                 l2 = PREV(l2);
 238         }
 239         assert(b != (bblock_p) 0);
 240         while(same_instr(l1,l2)) {
 241                 cnt++;
 242                 l1 = PREV(l1);
 243                 l2 = PREV(l2);
 244                 /* printf("consider:\n"); showinstr(l1); showinstr(l2); */
 245         }
 246         if (cnt >= 1) {
 247                 l1 = (l1 == 0 ? b1->b_start : l1->l_next);
 248                 l2 = (l2 == 0 ? b2->b_start : l2->l_next);
 249                 if (is_desirable(l1)) {
 250                         if (b == b1) {
 251                                 jump_cross(l2,l1,b2,b1);
 252                                 Scj++;
 253                         } else {
 254                                 jump_cross(l1,l2,b1,b2);
 255                                 Scj++;
 256                         }
 257                         return TRUE;
 258                 }
 259         }
 260         return FALSE;
 261 }
 262
 263
 264
 265 STATIC bool try_pred(b)
 266         bblock_p b;
 267 {
 268         /* See if there is any pair (b1,b2), both in PRED(b) for
 269          * which we can perform cross jumping.
 270          */
 271
 272         register bblock_p b1,b2;
 273         register Lindex i,j;
 274         lset s = b->b_pred;
 275
 276         for (i = Lfirst(s); i != (Lindex) 0; i = Lnext(i,s)) {
 277                 b1 = (bblock_p) Lelem(i);
 278                 if (Lnrelems(b1->b_succ) != 1) continue;
 279                 for (j = Lfirst(s); j != (Lindex) 0; j = Lnext(j,s)) {
 280                         b2 = (bblock_p) Lelem(j);
 281                         if (b1 != b2 && Lnrelems(b2->b_succ) == 1) {
 282                                 if (try_tail(b1,b2)) return TRUE;
 283                         }
 284                 }
 285         }
 286         return FALSE;
 287 }
 288
 289
 290
 291 cj_optimize(p)
 292         proc_p p;
 293 {
 294         /* Perform cross jumping for procedure p.
 295          * In case cases a cross-jumping optimization which give
 296          * new opportunities for further cross-jumping optimizations.
 297          * Hence we repeat the whole process for the entire procedure,
 298          * untill we find no further optimizations.
 299          */
 300
 301         bblock_p b;
 302         bool changes = TRUE;
 303
 304         if (IS_ENTERED_WITH_GTO(p)) return;
 305         while(changes) {
 306                 changes = FALSE;
 307                 b = p->p_start;
 308                 while (b != (bblock_p) 0) {
 309                         if (try_pred(b)) {
 310                                 changes = TRUE;
 311                         } else {
 312                                 b = b->b_next;
 313                         }
 314                 }
 315         }
 316 }
 317
 318
 319 main(argc,argv)
 320         int argc;
 321         char *argv[];
 322 {
 323         go(argc,argv,no_action,cj_optimize,no_action,no_action);
 324         report("cross jumps",Scj);
 325         exit(0);
 326 }
 327
 328
 329
 330 /******
 331  * Debugging stuff
 332  */
 333
 334 extern char em_mnem[]; /* The mnemonics of the EM instructions. */
 335
 336 STATIC showinstr(lnp) line_p lnp; {
 337
 338     /* Makes the instruction in `lnp' human readable. Only lines that
 339      * can occur in expressions that are going to be eliminated are
 340      * properly handled.
 341      */
 342     if (lnp == 0) return;
 343     if (INSTR(lnp) < sp_fmnem || INSTR(lnp) > sp_lmnem) {
 344         printf("\t*** ?\n");
 345         return;
 346     }
 347
 348     printf("\t%s", &em_mnem[4 * (INSTR(lnp)-sp_fmnem)]);
 349     switch (TYPE(lnp)) {
 350         case OPNO:
 351             break;
 352         case OPSHORT:
 353             printf(" %d", SHORT(lnp)); break;
 354         case OPOBJECT:
 355             printf(" %d", OBJ(lnp)->o_id); break;
 356         case OPOFFSET:
 357             printf(" %ld", OFFSET(lnp)); break;
 358         default:
 359             printf(" ?"); break;
 360     }
 361     printf("\n");
 362 } /* showinstr */