nsz Git - libfirm/blob - ir/be/bephiopt.c

   1 /**
   2  * @author Daniel Grund
   3  * @date 04.01.2005
   4  */
   5 #ifdef HAVE_CONFIG_H
   6 #include "config.h"
   7 #endif
   8
   9 #include <stdlib.h>
  10 #include <stdio.h>
  11
  12 #include "pset.h"
  13 #include "obst.h"
  14 #include "irgraph.h"
  15 #include "irnode.h"
  16 #include "irgwalk.h"
  17 #include "irouts.h"
  18 #include "irdom.h"
  19
  20 #include "beutil.h"
  21 #include "bera_t.h"
  22 #include "bephiopt.h"
  23 #include "phiclass_t.h"
  24 #include "bephicoal_t.h"
  25 #include "phistat.h"
  26
  27 #define DEBUG_LVL 0
  28 //SET_LEVEL_1
  29 #define CHECK_RESULTS      1
  30 #define COUNT_COPY_SAVINGS 1
  31 #define DUMP_OPT_DIFF      0
  32
  33 #define DO_PHI_STATISTICS  0
  34 #define DUMP_IRG_PHI_STAT  1
  35 #define DUMP_DIR_PHI_STAT  1
  36 #define DUMP_ALL_PHI_STAT  1
  37
  38 #define PHI_STAT_FILE "dir.phistat"
  39 #define ENV_PHI_STAT "PHI_STAT"
  40
  41 static firm_dbg_module_t *dbgphi = NULL;
  42
  43 static void phi_node_walker(ir_node *node, void *env) {
  44         if (is_Phi(node) && mode_is_datab(get_irn_mode(node)))
  45                 pset_insert_ptr((pset *)env, node);
  46 }
  47
  48
  49 static void node_collector(ir_node *node, void *env) {
  50         struct obstack *obst = env;
  51         if (!is_Block(node) && is_allocatable_irn(node))
  52                 obstack_ptr_grow(obst, node);
  53 }
  54
  55
  56 static void check_result(ir_graph *irg) {
  57         struct obstack ob;
  58         ir_node **nodes, *n1, *n2;
  59         int i, o;
  60
  61         obstack_init(&ob);
  62         irg_walk_graph(irg, node_collector, NULL, &ob);
  63         obstack_ptr_grow(&ob, NULL);
  64         nodes = (ir_node **) obstack_finish(&ob);
  65         for (i = 0, n1 = nodes[i]; n1; n1 = nodes[++i]) {
  66                 assert(! (is_allocatable_irn(n1) && get_irn_color(n1) == NO_COLOR));
  67                 for (o = i+1, n2 = nodes[o]; n2; n2 = nodes[++o])
  68                         if (phi_ops_interfere(n1, n2) && get_irn_color(n1) == get_irn_color(n2)) {
  69                                 DBG((dbgphi, 1, "Ouch!\n   %n in %n\n   %n in %n\n", n1, get_nodes_block(n1), n2, get_nodes_block(n2)));
  70                                 assert(0 && "Interfering values have the same color!");
  71                         }
  72         }
  73
  74         obstack_free(&ob, NULL);
  75 }
  76
  77
  78 /* TODO: how to count copies in case of phi swapping */
  79 static void count_copies(pset *all_phi_nodes, int *copies, int *inevitable) {
  80         int i, max, phi_color;
  81         ir_node *phi;
  82
  83         for (phi = pset_first(all_phi_nodes); phi; phi = pset_next(all_phi_nodes)) {
  84                 phi_color = get_irn_color(phi);
  85                 for (i = 0, max = get_irn_arity(phi); i < max; ++i) {
  86                         ir_node *arg = get_irn_n(phi, i);
  87                         if (phi_color != get_irn_color(arg))
  88                                 (*copies)++;
  89                         if (phi_ops_interfere(phi, arg))
  90                                 (*inevitable)++;
  91                 }
  92         }
  93 }
  94
  95
  96 void be_phi_opt(ir_graph* irg) {
  97         pset *all_phi_nodes, *all_phi_classes;
  98         int before, after, inevitable;
  99
 100         DBG((dbgphi, 1, "\n\n=======================> IRG: %s\n\n", get_entity_name(get_irg_entity(irg))));
 101
 102
 103         /* get all phi nodes */
 104         DBG((dbgphi, 1, "-----------------------> Collecting phi nodes <-----------------------\n"));
 105         all_phi_nodes = pset_new_ptr(64);
 106         irg_walk_graph(irg, phi_node_walker, NULL, all_phi_nodes);
 107
 108
 109         /* get all phi congruence classes */
 110         DBG((dbgphi, 1, "-----------------------> Collecting phi classes <---------------------\n"));
 111         all_phi_classes = phi_class_compute_by_phis(all_phi_nodes);
 112
 113
 114         /* do some statistics */
 115         if (DO_PHI_STATISTICS) {
 116                 DBG((dbgphi, 1, "-----------------------> Collecting phi stats <-----------------------\n"));
 117                 phi_stat_reset();
 118                 phi_stat_collect(irg, all_phi_nodes, all_phi_classes);
 119                 if (DUMP_IRG_PHI_STAT) {
 120                         char buf[1024];
 121                         snprintf(buf, sizeof(buf), "%s.phistat", get_entity_name(get_irg_entity(irg)));
 122                         /*phi_stat_dump(buf);*/
 123                         phi_stat_dump_pretty(buf);
 124                 }
 125                 if (DUMP_DIR_PHI_STAT)
 126                         phi_stat_update(PHI_STAT_FILE);
 127                 if (DUMP_ALL_PHI_STAT)
 128                         phi_stat_update(getenv(ENV_PHI_STAT));
 129         }
 130
 131
 132         /* try to coalesce the colors of each phi class */
 133         DBG((dbgphi, 1, "-----------------------> Coalescing <---------------------------------\n"));
 134         compute_outs(irg);
 135         compute_doms(irg);
 136
 137         if (COUNT_COPY_SAVINGS) {
 138                 before = 0;
 139                 count_copies(all_phi_nodes, &before, &inevitable);
 140         }
 141
 142         if (CHECK_RESULTS)
 143                 check_result(irg);
 144
 145         if (DUMP_OPT_DIFF)
 146                 dump_allocated_irg(irg, "-before");
 147
 148         be_phi_coalesce(all_phi_classes);
 149
 150         if (DUMP_OPT_DIFF)
 151                 dump_allocated_irg(irg, "-opt");
 152
 153         if (CHECK_RESULTS)
 154                 check_result(irg);
 155
 156         if (COUNT_COPY_SAVINGS) {
 157                 after = 0;
 158                 inevitable = 0;
 159                 count_copies(all_phi_nodes, &after, &inevitable);
 160                 DBG((dbgphi, 0, "Irg: %s. Copies form %d to %d. %d phi-interferers\n", get_entity_name(get_irg_entity(irg)), before, after, inevitable));
 161         }
 162         free_dom_and_peace(irg);
 163 }
 164
 165
 166 void be_phi_opt_init(void) {
 167         dbgphi = firm_dbg_register("ir.be.phiopt");
 168         firm_dbg_set_mask(dbgphi, DEBUG_LVL);
 169
 170         phi_class_init();
 171         be_phi_coal_init();
 172 }