X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fana%2Fphiclass.c;h=af8284e296150d5d3ef8091b242c3ded767aec31;hb=58e533a640ff427362877a3d2f1a5142c96391e1;hp=40f0cf038934a4b97c8a4ff8e251cf240de7cbc4;hpb=8cedf9d2c38f2a21a910f6652921a9158727dc4b;p=libfirm diff --git a/ir/ana/phiclass.c b/ir/ana/phiclass.c index 40f0cf038..af8284e29 100644 --- a/ir/ana/phiclass.c +++ b/ir/ana/phiclass.c @@ -1,139 +1,106 @@ /** * @author Daniel Grund - * @date 09.12.2004 + * @date 09.08.2005 */ +#ifdef HAVE_CONFIG_H +# include "config.h" +#endif -#include -#include -#include +#ifdef HAVE_STDLIB_H +# include +#endif #include "debug.h" -#include "irprog.h" #include "irgwalk.h" -#include "irop.h" +#include "irop_t.h" +#include "iredges_t.h" #include "phiclass_t.h" -#define DEBUG_LVL 0 +DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;) size_t phi_irn_data_offset = 0; -static firm_dbg_module_t *dbgphi = NULL; -#define _get_phi(irn) get_irn_phi_info(irn)->phi -#define _set_phi(irn,p) get_irn_phi_info(irn)->phi = p -#define _get_phi_class(irn) get_irn_phi_info(irn)->phi_class -#define _set_phi_class(irn,cls) get_irn_phi_info(irn)->phi_class = cls +static void phi_class_build(ir_node *irn, pset *pc) { + int i, max; + const ir_edge_t *edge; -#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 INLINE void phi_class_insert(pset *class, ir_node *phi, ir_node *member) { - DBG((dbgphi, 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); -} - -/** - * 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_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."); - DBG((dbgphi, 1, "\tcorrect %n\n", n)); - - /* copy all class members from n to new_tgt. Duplicates eliminated by pset */ - src = _get_phi_class(n); - tgt = _get_phi_class(new_tgt); - for (p = (ir_node *)pset_first(src); p; p = (ir_node *)pset_next(src)) - phi_class_insert(tgt, new_tgt, p); - - /* phi class of n is no longer needed */ - del_pset(src); - _set_phi_class(n, NULL); -} - -/** - * Determines the phi congruence class of a phi node. - * This will assign a phi class to all operands of this - * phi node. Exceptions may be const nodes: See CONSTS_SPLIT_PHI_CLASSES - */ -static void phi_class_det(ir_node *curr_phi) { - pset *pc; - int i, n; - assert(is_Phi(curr_phi) && "This must be a phi node."); - DBG((dbgphi, 1, "Det. phi class of %n.\n", curr_phi)); + /* If irn has a phi class assigned already + * return immediately to stop recursion */ + if (_get_phi_class(irn)) { + DBG((dbg, LEVEL_2, " already done for %+F\n", irn)); + return; + } - pc = _get_phi_class(curr_phi); + /* The initial call to phi_class_build doesn't + * provide a pset, so alloc it */ if (!pc) { - pc = pset_new_ptr(2); - _set_phi_class(curr_phi, pc); - phi_class_insert(pc, curr_phi, curr_phi); + DBG((dbg, LEVEL_1, "Computing phi class for %+F\n", irn)); + assert(is_Phi(irn)); + pc = pset_new_ptr(4); } - for (i = 0, n = get_irn_arity(curr_phi); i < n; i++) { - ir_node *arg, *phi; - - arg = get_irn_n(curr_phi, i); - DBG((dbgphi, 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) && CONSTS_SPLIT_PHI_CLASSES) && "Const nodes must not have a phi class assigned. See CONSTS_SPLIT_PHI_CLASSES"); - phi_class_union(phi, curr_phi); - } + /* Add the irn to the phi class */ + DBG((dbg, LEVEL_1, " adding %+F\n", irn)); + pset_insert_ptr(pc, irn); + _set_phi_class(irn, pc); + + /* Check the 'neighbour' irns */ + if (is_Phi(irn) && mode_is_datab(get_irn_mode(irn))) { + /* Add all args of the phi to the phi-class. */ + for (i=0, max=get_irn_arity(irn); isrc; + DBG((dbg, LEVEL_2, " checking user %+F\n", user)); + if (is_Phi(user) && mode_is_datab(get_irn_mode(user))) + phi_class_build(user, pc); } - - return all_phi_classes; } static void phi_class_construction_walker(ir_node *node, void *env) { if (is_Phi(node) && mode_is_datab(get_irn_mode(node))) - phi_class_det(node); + phi_class_build(node, NULL); +} + +static void phi_class_destruction_walker(ir_node *node, void *env) { + pset *clss = _get_phi_class(node); + if (clss) { + ir_node *n; + for(n = pset_first(clss); n; n = pset_next(clss)) + _set_phi_class(n, NULL); + del_pset(clss); + } } void phi_class_compute(ir_graph *irg) { + irg_walk_graph(irg, phi_class_destruction_walker, NULL, NULL); irg_walk_graph(irg, phi_class_construction_walker, NULL, NULL); } -static void phi_class_destruction_walker(ir_node *node, void *env) { - if (is_Phi(node) && mode_is_datab(get_irn_mode(node))) { - pset *class = _get_phi_class(node); - if (class) { - free(class); - class = NULL; +pset *phi_class_compute_by_phis(pset *all_phi_nodes) { + int i; + ir_node *phi; + pset *all_phi_classes = pset_new_ptr_default(); + + if (pset_count(all_phi_nodes)) { + ir_graph *irg = get_irn_irg(pset_first(all_phi_nodes)); + pset_break(all_phi_nodes); + irg_walk_graph(irg, phi_class_destruction_walker, NULL, NULL); + + for (i = 0, phi=pset_first(all_phi_nodes); phi; phi=pset_next(all_phi_nodes)) { + assert(is_Phi(phi) && mode_is_datab(get_irn_mode(phi))); + phi_class_build(phi, NULL); + pset_insert_ptr(all_phi_classes, _get_phi_class(phi)); } } + + return all_phi_classes; } void phi_class_free(ir_graph *irg) { @@ -141,15 +108,10 @@ void phi_class_free(ir_graph *irg) { } pset *get_phi_class(const ir_node *irn) { - ir_node *phi; - if (phi = _get_phi(irn), phi) - return _get_phi_class(phi); - else - return NULL; + return get_irn_phi_info(irn)->phi_class; } void phi_class_init(void) { - dbgphi = firm_dbg_register("ir.ana.phiclass"); - firm_dbg_set_mask(dbgphi, DEBUG_LVL); + FIRM_DBG_REGISTER(dbg, "ir.ana.phiclass"); phi_irn_data_offset = register_additional_node_data(sizeof(phi_info_t)); }