From e47815829124e485f67ef268dd9a166495a7da19 Mon Sep 17 00:00:00 2001 From: Daniel Grund Date: Wed, 5 Jan 2005 12:31:36 +0000 Subject: [PATCH] Added basics of phi optimize phase. --- ir/be/Makefile.in | 3 +- ir/be/bechordal.h | 3 + ir/be/bemain.c | 14 ++-- ir/be/bephicoal.c | 155 +++++++++++++++++++++++++++++++++++++++++++ ir/be/bephicoal_t.h | 14 ++++ ir/be/bephicongr.c | 119 +++++++++++---------------------- ir/be/bephicongr_t.h | 34 +++++----- ir/be/bephiopt.c | 35 ++++++++++ ir/be/bephiopt.h | 16 +++++ 9 files changed, 288 insertions(+), 105 deletions(-) create mode 100644 ir/be/bephicoal.c create mode 100644 ir/be/bephicoal_t.h create mode 100644 ir/be/bephiopt.c create mode 100644 ir/be/bephiopt.h diff --git a/ir/be/Makefile.in b/ir/be/Makefile.in index bd839b901..18b043cfe 100644 --- a/ir/be/Makefile.in +++ b/ir/be/Makefile.in @@ -21,7 +21,8 @@ SOURCES = $(INSTALL_HEADERS) SOURCES += Makefile.in besched.h belistsched.h belistsched.c \ beutil.h bemain.c besched.c bemain.c belive.c belive.h benumb.h \ - benumb_t.h benumb.c bechordal.c bera.c beutil.c phistat.c phistat.h bephicongr.c + benumb_t.h benumb.c bechordal.c bera.c beutil.c phistat.c \ + bephiopt.c bephicongr.c bephicoal.c include $(topdir)/MakeRules diff --git a/ir/be/bechordal.h b/ir/be/bechordal.h index 580a98c23..10e6cd028 100644 --- a/ir/be/bechordal.h +++ b/ir/be/bechordal.h @@ -8,6 +8,9 @@ #ifndef __BECHORDAL_H #define __BECHORDAL_H +#include "irgraph.h" +#include "irnode.h" + /** * Allocate registers for an ir graph. * @param irg The graph. diff --git a/ir/be/bemain.c b/ir/be/bemain.c index a8692d428..2f43b0a79 100644 --- a/ir/be/bemain.c +++ b/ir/be/bemain.c @@ -21,12 +21,13 @@ #include "besched_t.h" #include "belistsched.h" #include "belive_t.h" -#include "bephicongr_t.h" #include "beutil.h" #include "bechordal.h" +#include "bephiopt.h" #include "phistat.h" #define N_PHASES 256 +#define DO_STATISTICS typedef struct _be_graph_info_t { bitset_t *applied_phases; @@ -94,7 +95,7 @@ void be_init(void) be_liveness_init(); be_numbering_init(); be_ra_init(); - be_phi_congr_class_init(); + be_phi_opt_init(); } extern void be_ra_chordal(ir_graph *irg); @@ -110,19 +111,22 @@ static void be_main_loop(void) list_sched(irg, trivial_selector, NULL); be_liveness(irg); be_ra_chordal(irg); - be_phi_congr_classes(irg); + be_phi_opt(irg); - dump_allocated_irg(irg); - + //dump_allocated_irg(irg); +#ifndef DO_STATISTICS be_ra_chordal_done(irg); be_numbering_done(irg); +#endif } } void be_main(int argc, const char *argv[]) { be_main_loop(); +#ifdef DO_STATISTICS do_phi_statistics(); +#endif } diff --git a/ir/be/bephicoal.c b/ir/be/bephicoal.c new file mode 100644 index 000000000..895f183e2 --- /dev/null +++ b/ir/be/bephicoal.c @@ -0,0 +1,155 @@ +/** + * @author Daniel Grund + * @date 04.01.2005 + */ + +#include + +#include "debug.h" +#include "bechordal.h" + +#include "bera_t.h" +#include "bephicongr_t.h" +#include "bephicoal_t.h" + + +firm_dbg_module_t *dbgmod = NULL; + + +void be_phi_coal_init(void) { + dbgmod = firm_dbg_register("Phi coalescing"); + firm_dbg_register("Testsdflkjsdf"); + firm_dbg_set_mask(dbgmod, 1); + DBG((dbgmod, 1, "Phi coalescing dbg enabled")); +} + + +static INLINE ir_node **pset_to_array(pset *theset) { + ir_node **res, *p; + int i, count; + + count = pset_count(theset); + res = (ir_node **) malloc(count * sizeof(ir_node*)); + for (i = 0, p = (ir_node *)pset_first(theset); p; p = (ir_node *)pset_next(theset)) + res[i++] = p; + assert(i == count); + + return res; +} + + +static INLINE pset *clone(pset *theset) { + void *p; + pset *res; + + res = pset_new_ptr(8); + for (p = pset_first(theset); p; p = pset_next(theset)) + pset_insert_ptr(res, p); + + return res; +} + + +static void coalesce_locals(pset *phi_class) { + int i, count, phi_count, arity, intf_det, phi_col; + pset *pc, *intffree; + ir_node *phi, *n, *m; +// ir_node **members; + + count = pset_count(phi_class); + pc = clone(phi_class); +// members = pset_to_array(phi_class); + + /* how many phi nodes are in this class? */ + DBG((dbgmod, 1, "Checking phi count\n")); + phi_count = 0; + for (n = (ir_node *)pset_first(pc); n; n = (ir_node *)pset_next(pc)) { + if (is_Phi(n)) { + phi = n; + phi_count++; + } + } + + if (phi_count > 1) { + DBG((dbgmod, 1, "Dropped: Too many phis\n")); + goto exit; + } + assert(phi_count == 1 && phi); + + + /* where is the definition of the arguments? */ + DBG((dbgmod, 1, "Checking arg def\n")); + arity = get_irn_arity(phi); + for (i = 0; i < arity; ++i) { + ir_node *block_of_arg, *block_ith_pred; + ir_node *arg = get_irn_n(phi, i); + + /* TODO: check next few lines after const node copy placement */ +// if (iro_Const == get_irn_opcode(arg) && CONSTS_SPLIT_PHI_CLASSES) +// continue; + + block_of_arg = get_nodes_block(arg); + block_ith_pred = get_nodes_block(get_irn_n(get_nodes_block(phi), i)); + + if (block_of_arg != block_ith_pred) { + DBG((dbgmod, 1, "Dropped: Arg-def not in pred-block\n")); + goto exit; + } + } + + + /* determine a greedy set of non-interfering members + * crucial: starting with the phi node + */ + DBG((dbgmod, 1, "Building greedy non-intfering set\n")); + intffree = pset_new_ptr(4); + + pset_remove_ptr(pc, phi); + pset_insert_ptr(intffree, phi); + + while (m = (ir_node *)pset_first(pc), m) { + DBG((dbgmod, 1, "Checking %n\n", m)); + pset_break(pc); + pset_remove_ptr(pc, m); + + intf_det = 0; + for (n = (ir_node *)pset_first(intffree); n; n = (ir_node *)pset_next(intffree)) { + DBG((dbgmod, 1, "\t%n", n)); + if (phi_ops_interfere(m, n)) { + DBG((dbgmod, 1, "\tinterf\n")); + intf_det = 1; + } else { + DBG((dbgmod, 1, "\tclean\n")); + } + } + + if (!intf_det) { + DBG((dbgmod, 1, "Added to set\n")); + pset_insert_ptr(intffree, m); + } + } + + /* + * color the intffree set + */ + DBG((dbgmod, 1, "Coloring...\n")); + phi_col = get_irn_color(phi); + DBG((dbgmod, 1, "phi-color: %d\n", tgt_col)); + + + +exit: + del_pset(pc); +// free(members); +} + + +void be_phi_coalesce_locals(pset *all_phi_classes) { + pset *phi_class; + + DBG((dbgmod, 1, "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX\n")); + + /* determine all phi classes */ + for (phi_class = (pset *)pset_first(all_phi_classes); phi_class; phi_class = (pset *)pset_next(all_phi_classes)) + coalesce_locals(phi_class); +} diff --git a/ir/be/bephicoal_t.h b/ir/be/bephicoal_t.h new file mode 100644 index 000000000..503352847 --- /dev/null +++ b/ir/be/bephicoal_t.h @@ -0,0 +1,14 @@ +/** + * @author Daniel Grund + * @date 04.01.2005 + */ + +#ifndef _BEPHICOAL_T_H +#define _BEPHICOAL_T_H + +#include "pset.h" + +void be_phi_coal_init(void); +void be_phi_coalesce_locals(pset *all_phi_classes); + +#endif diff --git a/ir/be/bephicongr.c b/ir/be/bephicongr.c index 0e159a6fd..184602143 100644 --- a/ir/be/bephicongr.c +++ b/ir/be/bephicongr.c @@ -10,23 +10,22 @@ #include "config.h" #include "irgraph.h" #include "irnode.h" -#include "irgwalk.h" #include "irop.h" #include "irprog.h" -#include "irprintf_t.h" #include "debug.h" #include "pset.h" #include "bephicongr_t.h" #include "beutil.h" -#include "bechordal.h" +pset *all_phi_classes = NULL; + size_t phi_irn_data_offset = 0; -firm_dbg_module_t *dbgmod = NULL; +static firm_dbg_module_t *dbgmod = NULL; void be_phi_congr_class_init(void) { - dbgmod = firm_dbg_register("Phi congr. classes"); + dbgmod = firm_dbg_register("Phi congruence classes"); firm_dbg_set_mask(dbgmod, 1); phi_irn_data_offset = register_additional_node_data(sizeof(phi_info_t)); } @@ -37,33 +36,32 @@ void be_phi_congr_class_init(void) { #define is_Const(n) (get_irn_opcode(n) == iro_Const) + /** * Insert a node to the phi class of a phi node * @param class The phi congruence class * @param phi The phi node holding the class * @param arg Node which gets assigned to the class */ -static void inline phi_class_insert(pset *class, ir_node *phi, ir_node *arg) { - /*DBG((dbgmod, 1, "\tinsert %n in %n\n", arg, phi));*/ - ir_debugf("\tinsert %n in %n\n", arg, phi); - if (!(is_Const(arg) && CONSTS_SPLIT_PHI_CLASSES)) - set_phi(arg, phi); - pset_insert_ptr(class, arg); +static INLINE void phi_class_insert(pset *class, ir_node *phi, ir_node *member) { + DBG((dbgmod, 1, "\tinsert %n in %n\n", member, phi)); + if (!(is_Const(member) && CONSTS_SPLIT_PHI_CLASSES)) + set_phi(member, phi); + pset_insert_ptr(class, member); } /** - * Assigns all operands of a phi node - * to a (new) phi congruence class - * @param n Phi node, of which all args get reassigned - * @param new_tgt Phi node representing new phi congruence class + * Unites two phi classes repesented by two phi nodes. + * @param n Phi node representing phi class to reassign + * @param new_tgt Phi node, which will hold the new bigger phi class */ -static void phi_class_correct(ir_node *n, ir_node *new_tgt) { +static void phi_class_union(ir_node *n, ir_node *new_tgt) { ir_node *p; pset *src, *tgt; assert(is_Phi(n) && is_Phi(new_tgt) && "These must be phi nodes."); - ir_debugf("\tcorrect %n\n", n); + DBG((dbgmod, 1, "\tcorrect %n\n", n)); /* copy all class members from n to new_tgt. Duplicates eliminated by pset */ src = get_phi_class(n); @@ -72,8 +70,8 @@ static void phi_class_correct(ir_node *n, ir_node *new_tgt) { phi_class_insert(tgt, new_tgt, p); /* phi class of n is no longer needed */ - set_phi_class(n, NULL); del_pset(src); + set_phi_class(n, NULL); } @@ -86,7 +84,7 @@ static void det_phi_congr_class(ir_node *curr_phi) { pset *pc; int i, n; assert(is_Phi(curr_phi) && "This must be a phi node."); - ir_debugf("Det. phi class of %n.\n", curr_phi); + DBG((dbgmod, 1, "Det. phi class of %n.\n", curr_phi)); pc = get_phi_class(curr_phi); if (!pc) { @@ -99,77 +97,38 @@ static void det_phi_congr_class(ir_node *curr_phi) { ir_node *arg, *phi; arg = get_irn_n(curr_phi, i); - ir_debugf(" Arg %n\n", arg); + DBG((dbgmod, 1, " Arg %n\n", arg)); phi = get_phi(arg); if (phi == NULL) { /* Argument is not assigned to another phi class. */ phi_class_insert(pc, curr_phi, arg); } else if (phi != curr_phi) { - assert(!is_Const(arg) && "Const nodes must not have a phi class assigned"); - phi_class_correct(phi, curr_phi); + assert(!(is_Const(arg) && CONSTS_SPLIT_PHI_CLASSES) && "Const nodes must not have a phi class assigned. See CONSTS_SPLIT_PHI_CLASSES"); + phi_class_union(phi, curr_phi); } } - ir_debugf("Size now: %d\n", get_phi_class_size(curr_phi)); + DBG((dbgmod, 1, "Size now: %d\n", pset_count(get_phi_class(curr_phi)))); } + /** - * Determines the liveness interference information - * of a phi congruence class. + * Determines the phi congruence classes of + * all phi nodes in a given pset */ -static void det_interference(ir_node *n) { - pset *pc; - ir_node **members, *p; - int count, i, o; - int doit; - - pc = get_phi_class(n); - if (!pc) - return; - - count = pset_count(pc); - members = (ir_node **) malloc(count * sizeof(ir_node*)); - - ir_debugf("\nChecking phi class of node %n:\n", n); - for (i=0, p = (ir_node *)pset_first(pc); p; p = (ir_node *)pset_next(pc)) - members[i++] = p; - assert(i == count); - - //determine interference of phi args - for (i = 0; i < count-1; ++i) { - doit = 1; - for (o = i+1; o < count; ++o) { - ir_debugf("Checking %n\t%n", members[i], members[o]); - if (phi_ops_interfere(members[i], members[o])) { - ir_debugf("\tinterfere\n"); - get_irn_phi_info(n)->interf_pairs++; - if (doit) { - get_irn_phi_info(n)->interf_vals++; - doit = 0; - } - - } else { - ir_debugf("\tclean\n"); - } - } +void be_phi_congr_classes(pset *phis) { + int i; + ir_node *phi; + pset *phi_class; + + /* determine all phi classes */ + for (i = 0, phi = (ir_node *)pset_first(phis); phi; phi = (ir_node *)pset_next(phis)) + det_phi_congr_class(phi); + + /* store them in a pset for fast retrieval */ + all_phi_classes = pset_new_ptr(64); + for (i = 0, phi = (ir_node *)pset_first(phis); phi; phi = (ir_node *)pset_next(phis)) { + phi_class = get_phi_class(phi); + if (phi_class) + pset_insert_ptr(all_phi_classes, phi_class); } - - free(members); -} - - -static void phi_class_walker(ir_node *node, void *env) { - if (!(is_Phi(node) && mode_is_datab(get_irn_mode(node)))) return; - det_phi_congr_class(node); -} - - -static void phi_class_inteference_walker(ir_node *node, void *env) { - if (!(is_Phi(node) && mode_is_datab(get_irn_mode(node)))) return; - det_interference(node); -} - - -void be_phi_congr_classes(ir_graph *irg) { - irg_walk_graph(irg, phi_class_walker, NULL, NULL); - irg_walk_graph(irg, phi_class_inteference_walker, NULL, NULL); } diff --git a/ir/be/bephicongr_t.h b/ir/be/bephicongr_t.h index 8bb5fbcbb..6b19da8be 100644 --- a/ir/be/bephicongr_t.h +++ b/ir/be/bephicongr_t.h @@ -9,36 +9,32 @@ #include "irnode.h" #include "pset.h" -/** - * Setting this to 0 will treat const nodes like - * all other nodes when computing phi congruence classes. - * A non zero value results in splitting phi congruence - * classes at all const nodes (except they do share - * some non-const nodes too) - */ -#define CONSTS_SPLIT_PHI_CLASSES 1 - typedef struct _phi_info_t { ir_node *phi; /* only set in args of phi nodes (which could be a phi itslef). Points to a phi node or NULL */ pset *phi_class; /* only set in phi nodes. A set containing the members of the phi congruence class this phi node belongs to */ - int interf_pairs; - int interf_vals; } phi_info_t; extern size_t phi_irn_data_offset; +extern pset *all_phi_classes; + +/** + * Setting this to 0 will treat const nodes like + * all other nodes when computing phi congruence classes. + * A non zero value results in splitting phi congruence + * classes at all const nodes (except they do share + * some non-const nodes too) + * + * A non zero value can only be set if copies of const + * nodes are placed correctly. + */ +#define CONSTS_SPLIT_PHI_CLASSES 1 #define get_irn_phi_info(irn) get_irn_data(irn, phi_info_t, phi_irn_data_offset) -/* Only for phi nodes */ -#define get_phi_class(irn) get_irn_phi_info(irn)->phi_class -#define get_phi_class_size(irn) (get_phi_class(irn)==NULL ? 0 : pset_count(get_phi_class(irn))) +#define get_phi_class(irn) get_irn_phi_info(irn)->phi_class /* Only for phi nodes */ void be_phi_congr_class_init(void); +void be_phi_congr_classes(pset *phis); -/** - * Determines the phi congruence classes of - * all phi nodes in a graph - */ -void be_phi_congr_classes(ir_graph *irg); #endif diff --git a/ir/be/bephiopt.c b/ir/be/bephiopt.c new file mode 100644 index 000000000..5ed3ab9b8 --- /dev/null +++ b/ir/be/bephiopt.c @@ -0,0 +1,35 @@ +/** + * @author Daniel Grund + * @date 04.01.2005 + */ + +#include "pset.h" +#include "irnode.h" +#include "irgwalk.h" + +#include "bephiopt.h" +#include "bephicongr_t.h" +#include "bephicoal_t.h" + +pset *all_phi_nodes = NULL; + + +static void phi_node_walker(ir_node *node, void *env) { + if (is_Phi(node) && mode_is_datab(get_irn_mode(node))) + pset_insert_ptr(all_phi_nodes, node); +} + + +void be_phi_opt(ir_graph* irg) { + all_phi_nodes = pset_new_ptr(64); + irg_walk_graph(irg, phi_node_walker, NULL, NULL); + + be_phi_congr_classes(all_phi_nodes); + be_phi_coalesce_locals(all_phi_classes); +} + + +void be_phi_opt_init(void) { + be_phi_congr_class_init(); + be_phi_coal_init(); +} diff --git a/ir/be/bephiopt.h b/ir/be/bephiopt.h new file mode 100644 index 000000000..c2dd01894 --- /dev/null +++ b/ir/be/bephiopt.h @@ -0,0 +1,16 @@ +/** + * @author Daniel Grund + * @date 04.01.2005 + */ + +#ifndef _BEPHIOPT_H +#define _BEPHIOPT_H + +#include "irgraph.h" + + +void be_phi_opt_init(void); +void be_phi_opt(ir_graph* irg); + + +#endif -- 2.20.1