24 #include "phiclass_t.h"
25 #include "bephicoal_t.h"
26 #include "bephicoalilp_t.h"
32 #define DEBUG_LVL SET_LEVEL_1
34 /** checks if two interfering nodes have the same color */
36 /** counts the copies needed before and after optimization */
37 #define COUNT_COPY_SAVINGS
38 /** dumps 2 allocated graphs; before and after opt. */
41 #undef DO_PHI_STATISTICS
42 #define DUMP_IRG_PHI_STAT
43 #define DUMP_DIR_PHI_STAT
44 #define DUMP_ALL_PHI_STAT
46 #define PHI_STAT_FILE "dir.phistat"
47 #define ENV_PHI_STAT "PHI_STAT"
49 static firm_dbg_module_t *dbgphi = NULL;
51 typedef struct _copies_t {
53 int count[3]; /* before, after heuristics, after optimality */
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);
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);
70 static void check_result(ir_graph *irg) {
72 ir_node **nodes, *n1, *n2;
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!");
88 obstack_free(&ob, NULL);
93 * Init the copies struct lower and upper bound
95 static void init_copies(copies_t *c, pset *all_phi_nodes) {
98 c->count[0] = c->count[1] = c->count[2] = -1;
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);
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))
116 * Count the copies needed with current coloring
118 static void count_copies(copies_t *c, pset *all_phi_nodes, int stage) {
119 int i, max, phi_color;
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)) {
130 DBG((dbgphi, LEVEL_2, "Copy: %n %n\n", phi, arg));
137 void be_phi_opt(ir_graph* irg) {
138 pset *all_phi_nodes, *all_phi_classes;
141 DBG((dbgphi, 1, "\n\n=======================> IRG: %s\n\n", get_entity_name(get_irg_entity(irg))));
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);
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);
155 /* do some statistics */
156 #ifdef DO_PHI_STATISTICS
157 DBG((dbgphi, 1, "-----------------------> Collecting phi stats <-----------------------\n"));
159 phi_stat_collect(irg, all_phi_nodes, all_phi_classes);
160 #ifdef DUMP_IRG_PHI_STAT
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);
166 #ifdef DUMP_DIR_PHI_STAT
167 phi_stat_update(PHI_STAT_FILE);
169 #ifdef DUMP_ALL_PHI_STAT
170 phi_stat_update(getenv(ENV_PHI_STAT));
175 /* try to coalesce the colors of each phi class */
176 DBG((dbgphi, 1, "-----------------------> Coalescing <---------------------------------\n"));
182 dump_allocated_irg(irg, "-before");
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);
197 be_phi_coalesce(all_phi_classes);
199 dump_allocated_irg(irg, "-heur");
204 #ifdef COUNT_COPY_SAVINGS
205 count_copies(copies, all_phi_nodes, 1);
207 #endif /* DO_HEURISTIC */
210 if (copies->count[1] == -1 || copies->count[1] > copies->lb) {
212 be_phi_coalesce_ilp(irg, all_phi_nodes);
214 dump_allocated_irg(irg, "-opt");
219 #ifdef COUNT_COPY_SAVINGS
220 count_copies(copies, all_phi_nodes, 2);
222 #endif /* DO_OPTIMAL */
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]));
227 free_dom_and_peace(irg);
231 void be_phi_opt_init(void) {
232 dbgphi = firm_dbg_register("ir.be.phiopt");
233 firm_dbg_set_mask(dbgphi, DEBUG_LVL);
240 be_phi_coal_ilp_init();