util/ego/cs/cs.c

   1 /* $Id: cs.c,v 1.6 1994/06/24 10:21:40 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
   7 /* C O M M O N   S U B E X P R E S S I O N   E L I M I N A T I O N */
   8
   9
  10 #include <stdio.h>
  11 #include "../share/types.h"
  12 #include "../share/lset.h"
  13 #include "../share/debug.h"
  14 #include "../share/go.h"
  15 #include "cs.h"
  16 #include "cs_aux.h"
  17 #include "cs_avail.h"
  18 #include "cs_debug.h"
  19 #include "cs_elim.h"
  20 #include "cs_entity.h"
  21 #include "cs_profit.h"
  22 #include "cs_stack.h"
  23 #include "cs_vnm.h"
  24
  25 int Scs; /* Number of optimizations found. */
  26
  27 STATIC cs_clear()
  28 {
  29         clr_avails();
  30         clr_entities();
  31         clr_stack();
  32
  33         start_valnum();
  34 }
  35
  36 STATIC cs_optimize(p)
  37         proc_p p;
  38 {
  39         /* Optimize all basic blocks of one procedure. */
  40
  41         register bblock_p rbp, bdone;
  42
  43         if (IS_ENTERED_WITH_GTO(p)) return;
  44         avails = (avail_p) 0;
  45         entities = Lempty_set();
  46         cs_clear();
  47
  48         rbp = p->p_start;
  49
  50         while (rbp != (bblock_p) 0) {
  51                 /* First we build a list of common expressions with the
  52                  * value numbering algorithm. We take blocks in textual order
  53                  * as long as the next block can only be reached through the
  54                  * block we have just done. Note that if a block is preceded
  55                  * by itself, the number of predecessors is greater than 1,
  56                  * but the previous block can still be its immediate dominator.
  57                  */
  58                 do {    vnm(rbp); bdone = rbp;
  59                         OUTTRACE("basic block %d processed", bdone->b_id);
  60                         rbp = rbp->b_next;
  61                 } while (rbp != (bblock_p) 0 && rbp->b_idom == bdone &&
  62                         Lnrelems(rbp->b_pred) == 1
  63                 );
  64                 OUTTRACE("value numbering completed", 0);
  65                 OUTAVAILS(); OUTENTITIES();
  66
  67                 /* Now we put out the instructions without common
  68                  * subexpressions but with the use of temporaries,
  69                  * which will be local variables of procedure p.
  70                  */
  71                 eliminate(p);
  72                 cs_clear();
  73         }
  74 }
  75
  76 main(argc, argv)
  77         int     argc;
  78         char    *argv[];
  79 {
  80         Scs = 0;
  81         go(argc, argv, no_action, cs_optimize, cs_machinit, no_action);
  82         report("Duplicate expressions eliminated", Scs);
  83         exit(0);
  84 }