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 "benumb_t.h"
  22 #include "bera_t.h"
  23 #include "bephiopt.h"
  24 #include "phiclass_t.h"
  25 #include "bephicoal_t.h"
  26 #include "bephicoalilp_t.h"
  27 #include "phistat.h"
  28
  29 #define DO_HEURISTIC
  30 #undef DO_OPTIMAL
  31
  32 #define DEBUG_LVL SET_LEVEL_1
  33
  34 /** checks if two interfering nodes have the same color */
  35 #define CHECK_RESULTS
  36 /** counts the copies needed before and after optimization */
  37 #define COUNT_COPY_SAVINGS
  38 /** dumps 2 allocated graphs; before and after opt. */
  39 #undef DUMP_OPT_DIFF
  40
  41 #undef DO_PHI_STATISTICS
  42 #define DUMP_IRG_PHI_STAT
  43 #define DUMP_DIR_PHI_STAT
  44 #define DUMP_ALL_PHI_STAT
  45
  46 #define PHI_STAT_FILE "dir.phistat"
  47 #define ENV_PHI_STAT "PHI_STAT"
  48
  49 static firm_dbg_module_t *dbgphi = NULL;
  50
  51 typedef struct _copies_t {
  52         int lb, ub;
  53         int count[3]; /* before, after heuristics, after optimality */
  54 } copies_t;
  55
  56
  57 static void phi_node_walker(ir_node *node, void *env) {
  58         if (is_Phi(node) && mode_is_datab(get_irn_mode(node)))
  59                 pset_insert_ptr((pset *)env, node);
  60 }
  61
  62
  63 static void node_collector(ir_node *node, void *env) {
  64         struct obstack *obst = env;
  65         if (!is_Block(node) && is_allocatable_irn(node))
  66                 obstack_ptr_grow(obst, node);
  67 }
  68
  69
  70 static void check_result(ir_graph *irg) {
  71         struct obstack ob;
  72         ir_node **nodes, *n1, *n2;
  73         int i, o;
  74
  75         obstack_init(&ob);
  76         irg_walk_graph(irg, node_collector, NULL, &ob);
  77         obstack_ptr_grow(&ob, NULL);
  78         nodes = (ir_node **) obstack_finish(&ob);
  79         for (i = 0, n1 = nodes[i]; n1; n1 = nodes[++i]) {
  80                 assert(! (is_allocatable_irn(n1) && get_irn_color(n1) == NO_COLOR));
  81                 for (o = i+1, n2 = nodes[o]; n2; n2 = nodes[++o])
  82                         if (phi_ops_interfere(n1, n2) && get_irn_color(n1) == get_irn_color(n2)) {
  83                                 DBG((dbgphi, 1, "Ouch!\n   %n[%d]in %n\n   %n[%d] in %n\n", n1, get_irn_graph_nr(n1), get_nodes_block(n1), n2, get_irn_graph_nr(n2), get_nodes_block(n2)));
  84                                 assert(0 && "Interfering values have the same color!");
  85                         }
  86         }
  87
  88         obstack_free(&ob, NULL);
  89 }
  90
  91
  92 /**
  93  * Init the copies struct lower and upper bound
  94  */
  95 static void init_copies(copies_t *c, pset *all_phi_nodes) {
  96         ir_node *phi;
  97
  98         c->count[0] = c->count[1] = c->count[2] = -1;
  99         c->ub = c->lb = 0;
 100
 101         for (phi = pset_first(all_phi_nodes); phi; phi = pset_next(all_phi_nodes)) {
 102                 /* upper bound: each argument of a phi node is a potential copy */
 103                 int i, max = get_irn_arity(phi);
 104                 c->ub += max;
 105                 /* lower bound: at least all interfering pairs */
 106                 for (i = 0; i < max; ++i) {
 107                         ir_node *arg = get_irn_n(phi, i);
 108                         if (phi_ops_interfere(phi, arg))
 109                                 c->lb++;
 110                 }
 111         }
 112 }
 113
 114
 115 /**
 116  * Count the copies needed with current coloring
 117  */
 118 static void count_copies(copies_t *c, pset *all_phi_nodes, int stage) {
 119         int i, max, phi_color;
 120         ir_node *phi;
 121
 122         c->count[stage] = 0;
 123
 124         for (phi = pset_first(all_phi_nodes); phi; phi = pset_next(all_phi_nodes)) {
 125                 phi_color = get_irn_color(phi);
 126                 for (i = 0, max = get_irn_arity(phi); i < max; ++i) {
 127                         ir_node *arg = get_irn_n(phi, i);
 128                         if (phi_color != get_irn_color(arg)) {
 129                                 c->count[stage]++;
 130                                 DBG((dbgphi, LEVEL_2, "Copy: %n %n\n", phi, arg));
 131                         }
 132                 }
 133         }
 134 }
 135
 136
 137 void be_phi_opt(ir_graph* irg) {
 138         pset *all_phi_nodes, *all_phi_classes;
 139         copies_t *copies;
 140
 141         DBG((dbgphi, 1, "\n\n=======================> IRG: %s\n\n", get_entity_name(get_irg_entity(irg))));
 142
 143
 144         /* get all phi nodes */
 145         DBG((dbgphi, 1, "-----------------------> Collecting phi nodes <-----------------------\n"));
 146         all_phi_nodes = pset_new_ptr(64);
 147         irg_walk_graph(irg, phi_node_walker, NULL, all_phi_nodes);
 148
 149
 150         /* get all phi congruence classes */
 151         DBG((dbgphi, 1, "-----------------------> Collecting phi classes <---------------------\n"));
 152         all_phi_classes = phi_class_compute_by_phis(all_phi_nodes);
 153
 154
 155         /* do some statistics */
 156 #ifdef DO_PHI_STATISTICS
 157         DBG((dbgphi, 1, "-----------------------> Collecting phi stats <-----------------------\n"));
 158         phi_stat_reset();
 159         phi_stat_collect(irg, all_phi_nodes, all_phi_classes);
 160 #ifdef DUMP_IRG_PHI_STAT
 161                 char buf[1024];
 162                 snprintf(buf, sizeof(buf), "%s.phistat", get_entity_name(get_irg_entity(irg)));
 163                 /*phi_stat_dump(buf);*/
 164                 phi_stat_dump_pretty(buf);
 165 #endif
 166 #ifdef DUMP_DIR_PHI_STAT
 167                 phi_stat_update(PHI_STAT_FILE);
 168 #endif
 169 #ifdef DUMP_ALL_PHI_STAT
 170                 phi_stat_update(getenv(ENV_PHI_STAT));
 171 #endif
 172 #endif
 173
 174
 175         /* try to coalesce the colors of each phi class */
 176         DBG((dbgphi, 1, "-----------------------> Coalescing <---------------------------------\n"));
 177         compute_outs(irg);
 178         compute_doms(irg);
 179
 180
 181 #ifdef DUMP_OPT_DIFF
 182         dump_allocated_irg(irg, "-before");
 183 #endif
 184 #ifdef CHECK_RESULTS
 185         check_result(irg);
 186 #endif
 187 #ifdef COUNT_COPY_SAVINGS
 188         copies = malloc(sizeof(*copies));
 189         init_copies(copies, all_phi_nodes);
 190         DBG((dbgphi, 0, "Copy bounds  : %3d < . < %3d\n", copies->lb, copies->ub));
 191         count_copies(copies, all_phi_nodes, 0);
 192 #endif
 193
 194
 195
 196 #ifdef DO_HEURISTIC
 197         be_phi_coalesce(all_phi_classes);
 198 #ifdef DUMP_OPT_DIFF
 199         dump_allocated_irg(irg, "-heur");
 200 #endif
 201 #ifdef CHECK_RESULTS
 202         check_result(irg);
 203 #endif
 204 #ifdef COUNT_COPY_SAVINGS
 205         count_copies(copies, all_phi_nodes, 1);
 206 #endif
 207 #endif /* DO_HEURISTIC */
 208
 209
 210         if (copies->count[1] == -1 || copies->count[1] > copies->lb) {
 211 #ifdef DO_OPTIMAL
 212                 be_phi_coalesce_ilp(irg, all_phi_nodes);
 213 #ifdef DUMP_OPT_DIFF
 214                 dump_allocated_irg(irg, "-opt");
 215 #endif
 216 #ifdef CHECK_RESULTS
 217                 check_result(irg);
 218 #endif
 219 #ifdef COUNT_COPY_SAVINGS
 220                 count_copies(copies, all_phi_nodes, 2);
 221 #endif
 222 #endif /* DO_OPTIMAL */
 223         }
 224 #ifdef COUNT_COPY_SAVINGS
 225         DBG((dbgphi, 0, "Copies before/heur/opt: %3d / %3d / %3d\n", copies->count[0], copies->count[1], copies->count[2]));
 226 #endif
 227         free_dom_and_peace(irg);
 228 }
 229
 230
 231 void be_phi_opt_init(void) {
 232         dbgphi = firm_dbg_register("ir.be.phiopt");
 233         firm_dbg_set_mask(dbgphi, DEBUG_LVL);
 234
 235         phi_class_init();
 236 #ifdef DO_HEURISTIC
 237         be_phi_coal_init();
 238 #endif
 239 #ifdef DO_OPTIMAL
 240         be_phi_coal_ilp_init();
 241 #endif
 242 }