util/ego/bo/bo.c

   1 /* $Id: bo.c,v 1.13 1994/11/29 14:53:02 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 /* B R A N C H   O P T I M I Z A T I O N
   7  *
   8  * B O . C
   9  */
  10
  11
  12 #include <stdio.h>
  13 #include <em_mnem.h>
  14 #include <em_pseu.h>
  15 #include <em_spec.h>
  16 #include <em_flag.h>
  17 #include "../share/types.h"
  18 #include "../share/debug.h"
  19 #include "../share/global.h"
  20 #include "../share/files.h"
  21 #include "../share/get.h"
  22 #include "../share/put.h"
  23 #include "../share/lset.h"
  24 #include "../share/map.h"
  25 #include "../share/alloc.h"
  26 #include "../share/aux.h"
  27 #include "../share/def.h"
  28 #include "../share/go.h"
  29
  30 extern char em_flag[];
  31
  32 #define LP_BLOCKS       lp_extend->lpx_ra.lpx_blocks
  33
  34 #define newbolpx()      (lpext_p)       newstruct(lpext_ra)
  35 #define oldbolpx(x)     oldstruct(lpext_ra,x)
  36
  37 STATIC int Sbo;  /* #optimizations found */
  38
  39 #define DLINK(l1,l2)    l1->l_next=l2; l2->l_prev=l1
  40
  41 /* This module performs some very simple branch optimizations.
  42  *
  43  * I) Look for pairs of basic blocks (B1,B2), such that
  44  *        SUCC(b1) = {B2} and
  45  *        PRED(B2) = {B1}.
  46  *    In this case B1 and B2 can be combined into one block.
  47  *    This optimization is mainly succesful:
  48  *     1) for switch statements in C, as the C compiler generates a branch
  49  *        over the entire switch.
  50  *     2) for return statements, if the only way to return from a procedure
  51  *        is via a return statement somewhere in the middle of the procedure.
  52  * II) Optimize while statements. Transformations like:
  53  *         1:                           jmp 2
  54  *              tst cond                1:
  55  *              beq 2f                      S
  56  *              S                       2:
  57  *              jmp 1                       tst cond
  58  *          2:                              bneq 1
  59  *      are done by this optimization.
  60  */
  61
  62
  63
  64 STATIC line_p last_code(lines,skip_pseu)
  65         line_p lines;
  66         bool skip_pseu;
  67 {
  68         /* Determine the last line of a list */
  69
  70         register line_p l;
  71
  72         for (l = lines; l->l_next != (line_p) 0; l = l->l_next);
  73         if (skip_pseu) {
  74                 while (l && (INSTR(l) < sp_fmnem || INSTR(l) > sp_lmnem)) l = PREV(l);
  75         }
  76         return l;
  77 }
  78
  79 STATIC short cc_tab[12] =
  80         {op_blt,op_zlt,op_ble,op_zle,op_beq,op_zeq,
  81          op_zne,op_bne,op_zgt,op_bgt,op_zge,op_bge};
  82
  83
  84 STATIC short rev_cond(cond)
  85          short cond;
  86 {
  87          register i;
  88
  89          for (i = 0; i < 12; i++) {
  90                 if (cond == cc_tab[i]) return cc_tab[11-i];
  91         }
  92         return op_nop;
  93 }
  94
  95 STATIC bool is_bcc(l)
  96         line_p l;
  97 {
  98         return rev_cond(INSTR(l)) != op_nop;
  99 }
 100
 101
 102 STATIC bo_optloop(p,b,x,bra,bcc)
 103         proc_p p;
 104         bblock_p b,x;
 105         line_p bra,bcc;
 106 {
 107         bblock_p prevb,n;
 108         line_p l;
 109
 110         if (b->b_start == bra) {
 111                 b->b_start = (line_p) 0;
 112         } else {
 113                 PREV(bra)->l_next = (line_p) 0;
 114         }
 115         PREV(bra) = (line_p) 0;
 116         bcc->l_instr = rev_cond(INSTR(bcc));
 117         n = x->b_next;
 118         l = n->b_start;
 119         if (l == (line_p) 0 || INSTR(l) != op_lab) {
 120                 l = newline(OPINSTRLAB);
 121                 l->l_instr = op_lab;
 122                 INSTRLAB(l) = freshlabel();
 123                 if (n->b_start != (line_p) 0) {
 124                         DLINK(l,n->b_start);
 125                 }
 126                 n->b_start = l;
 127         }
 128         INSTRLAB(bcc) = INSTRLAB(l);
 129         for (prevb = p->p_start; prevb != (bblock_p) 0 && prevb->b_next != x;
 130                 prevb = prevb->b_next);
 131         if (prevb == (bblock_p) 0) {
 132                 p->p_start = x->b_next;
 133         } else {
 134                 prevb->b_next = x->b_next;
 135                 l = last_instr(prevb);
 136                 if (l == (line_p) 0) {
 137                         prevb->b_start = bra;
 138                 } else {
 139                         if ((em_flag[INSTR(l)-sp_fmnem]&EM_FLO) == FLO_T) {
 140                                 oldline(bra);
 141                         } else {
 142                                 appnd_line(bra,l);
 143                         }
 144                 }
 145         }
 146         x->b_next = b->b_next;
 147         b->b_next = x;
 148 }
 149
 150
 151
 152 STATIC bo_tryloop(p,loop)
 153         proc_p p;
 154         lset loop;
 155 {
 156         Lindex i,j;
 157         bblock_p b,x;
 158         line_p bra,bcc;
 159
 160         for (i = Lfirst(loop); i != (Lindex) 0; i = Lnext(i,loop)) {
 161                 b = (bblock_p) Lelem(i);
 162                 if (b->b_next != (bblock_p) 0 && !Lis_elem(b->b_next,loop)) {
 163                         j = Lfirst(b->b_succ);
 164                         if (j != (Lindex) 0 &&
 165                             (bra = last_instr(b)) != (line_p) 0 &&
 166                             INSTR(bra) == op_bra) {
 167                                 x = (bblock_p) Lelem(j); /* single successor */
 168                                 if (Lis_elem(b->b_next,x->b_succ) &&
 169                                     is_bcc((bcc = last_instr(x)))) {
 170 OUTVERBOSE("branch optimization proc %d block %d\n", curproc->p_id,x->b_id);
 171                                         Sbo++;
 172                                         bo_optloop(p,b,x,bra,bcc);
 173                                         return;
 174                                 }
 175                         }
 176                 }
 177         }
 178 }
 179
 180
 181
 182 STATIC bo_loops(p)
 183         proc_p p;
 184 {
 185         Lindex i;
 186         loop_p lp;
 187
 188         for (i = Lfirst(p->p_loops); i != (Lindex) 0; i = Lnext(i,p->p_loops)) {
 189                 lp = (loop_p) (Lelem(i));
 190                 bo_tryloop(p,lp->LP_BLOCKS);
 191         }
 192 }
 193
 194 STATIC mv_code(b1,b2)
 195         bblock_p b1,b2;
 196 {
 197         line_p l,x;
 198
 199         l = last_code(b2->b_start,TRUE);
 200         assert(INSTR(l) == op_bra);
 201         DLINK(l,b1->b_start);
 202         x = l->l_next;
 203         rm_line(l,b2);
 204         if (INSTR(x) == op_lab) {
 205                 rm_line(x,b2);
 206         }
 207 }
 208
 209 bo_switch(b)
 210         bblock_p b;
 211 {
 212         bblock_p s,x;
 213         Lindex i;
 214         line_p l,bra;
 215
 216         if (Lnrelems(b->b_succ) == 1) {
 217                 s = (bblock_p) Lelem(Lfirst(b->b_succ));
 218                 if (b->b_start != (line_p) 0 &&
 219                     s->b_start != (line_p) 0 &&
 220                     Lnrelems(s->b_pred) == 1 &&
 221                     (bra = last_code(b->b_start,TRUE)) != (line_p) 0 &&
 222                     INSTR(bra) == op_bra &&
 223                     (s->b_next == (bblock_p) 0 ||
 224                      !Lis_elem(s->b_next,s->b_succ) ||
 225                      ((bra = last_code(s->b_start, TRUE)) != (line_p) 0 &&
 226                       (em_flag[INSTR(bra)-sp_fmnem]&EM_FLO) == FLO_T))) {
 227                         l = last_code(s->b_start,FALSE);
 228                         if (INSTR(l) == ps_end) {
 229                                 if (PREV(l) == (line_p) 0) return;
 230                                 PREV(l)->l_next = (line_p) 0;
 231                                 PREV(l) = (line_p) 0;
 232                         } else {
 233                                 l = (line_p) 0;
 234                         }
 235 OUTVERBOSE("branch optimization in proc %d, block %d",curproc->p_id,b->b_id);
 236                         Sbo++;
 237                         Ldeleteset(b->b_succ);
 238                         b->b_succ = s->b_succ;
 239                         Ldeleteset(s->b_pred);
 240                         s->b_succ = Lempty_set();
 241                         s->b_pred = Lempty_set();
 242                         for (i = Lfirst(b->b_succ); i != (Lindex) 0;
 243                                                 i = Lnext(i,b->b_succ)) {
 244                                 x = (bblock_p) Lelem(i);
 245                                 Lremove(s,&x->b_pred);
 246                                 Ladd(b,&x->b_pred);
 247                                 if (x->b_idom == s) {
 248                                         x->b_idom = b;
 249                                 }
 250                         }
 251                         mv_code(s,b);
 252                         s->b_start = l;
 253                 }
 254         }
 255 }
 256
 257 STATIC bo_extproc(p)
 258         proc_p p;
 259 {
 260         /* Allocate the extended data structures for procedure p */
 261
 262         register loop_p lp;
 263         register Lindex pi;
 264
 265         for (pi = Lfirst(p->p_loops); pi != (Lindex) 0;
 266            pi = Lnext(pi,p->p_loops)) {
 267                 lp = (loop_p) Lelem(pi);
 268                 lp->lp_extend = newbolpx();
 269         }
 270 }
 271
 272
 273 STATIC loop_blocks(p)
 274         proc_p p;
 275 {
 276         /* Compute the LP_BLOCKS sets for all loops of p */
 277
 278         register bblock_p b;
 279         register Lindex i;
 280
 281         for (b = p->p_start; b != (bblock_p) 0; b = b->b_next) {
 282                 for (i = Lfirst(b->b_loops); i != (Lindex) 0;
 283                    i = Lnext(i,b->b_loops)) {
 284                         Ladd(b,&(((loop_p) Lelem(i))->LP_BLOCKS));
 285                 }
 286         }
 287 }
 288
 289 STATIC bo_cleanproc(p)
 290         proc_p p;
 291 {
 292         /* Allocate the extended data structures for procedure p */
 293
 294         register loop_p lp;
 295         register Lindex pi;
 296         register bblock_p b;
 297
 298         for (pi = Lfirst(p->p_loops); pi != (Lindex) 0;
 299            pi = Lnext(pi,p->p_loops)) {
 300                 lp = (loop_p) Lelem(pi);
 301                 oldbolpx(lp->lp_extend);
 302         }
 303 }
 304
 305 bo_optimize(p)
 306         proc_p p;
 307 {
 308         bblock_p b;
 309
 310         if (IS_ENTERED_WITH_GTO(p)) return;
 311         bo_extproc(p);
 312         loop_blocks(p);
 313         bo_loops(p);
 314         for (b = p->p_start; b != 0; b = b->b_next) {
 315                 bo_switch(b);
 316         }
 317         bo_cleanproc(p);
 318 }
 319
 320
 321
 322 main(argc,argv)
 323         int argc;
 324         char *argv[];
 325 {
 326         go(argc,argv,no_action,bo_optimize,no_action,no_action);
 327         report("branch optimizations", Sbo);
 328         exit(0);
 329 }