X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fana%2Fphiclass.c;h=f9b4de3eaacbf2d352a2c30cb14b1b6055a871b4;hb=4853d5f7a9a07cb9d1374fb2dd1f75554e0036ae;hp=0a5166b1836623731a4e455331d79819bb145f9b;hpb=1a45198099b1f6ce6032c0949f4e85aa8c97b70a;p=libfirm diff --git a/ir/ana/phiclass.c b/ir/ana/phiclass.c index 0a5166b18..f9b4de3ea 100644 --- a/ir/ana/phiclass.c +++ b/ir/ana/phiclass.c @@ -1,106 +1,264 @@ +/* + * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved. + * + * This file is part of libFirm. + * + * This file may be distributed and/or modified under the terms of the + * GNU General Public License version 2 as published by the Free Software + * Foundation and appearing in the file LICENSE.GPL included in the + * packaging of this file. + * + * Licensees holding valid libFirm Professional Edition licenses may use + * this file in accordance with the libFirm Commercial License. + * Agreement provided with the Software. + * + * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE + * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR + * PURPOSE. + */ + /** - * @author Daniel Grund - * @date 09.08.2005 + * @file + * @brief Implementation of phiclass analysis + * @author Daniel Grund, Christian Wuerdig + * @cvsid $Id$ + * @date 09.08.2005 */ +#ifdef HAVE_CONFIG_H +# include "config.h" +#endif -#include +#ifdef HAVE_STDLIB_H +# include +#endif +#include "irnode.h" #include "debug.h" #include "irgwalk.h" #include "irop_t.h" #include "iredges_t.h" -#include "phiclass_t.h" +#include "phiclass.h" +#include "irphase_t.h" +#include "irnodeset.h" + +struct _phi_classes_t { + ir_phase ph; /* The phase object holding the irn data */ + pset *all_phi_classes; /* A set containing all Phi classes */ + ir_graph *irg; /* The irg this is all about */ + unsigned pure_phi_classes; /* Build pure Phi classes */ + DEBUG_ONLY(firm_dbg_module_t *dbg); +}; + +typedef struct _irn_phi_class_t { + ir_node ***phi_cls; /* the array of node pointers representing the class */ +} irn_phi_class_t; + +static INLINE ir_node ***_get_phi_class(ir_phase *ph, ir_node *irn) { + irn_phi_class_t *ipc = phase_get_or_set_irn_data(ph, irn); + return ipc->phi_cls; +} + +static INLINE void _set_phi_class(ir_phase *ph, ir_node *irn, ir_node ***cls) { + irn_phi_class_t *ipc = phase_get_or_set_irn_data(ph, irn); + ipc->phi_cls = cls; +} -#define DEBUG_LVL SET_LEVEL_0 -static firm_dbg_module_t *dbg = NULL; +/* initialize data structure for given irn in given phase */ +static void *irn_phi_class_init(ir_phase *ph, const ir_node *irn, void *data) { + irn_phi_class_t *ipc = data ? data : phase_alloc(ph, sizeof(ipc[0])); + (void) irn; + memset(ipc, 0, sizeof(ipc[0])); + return ipc; +} -size_t phi_irn_data_offset = 0; +/** + * Builds the phi class, starting from. + * @param phi_classes The phi class object + * @param irn The to start from + * @param pc The phi class this irn should be put into. + * Set to NULL if you want a new one. + */ +static void phi_class_build(phi_classes_t *phi_classes, ir_node *irn, ir_node ***pc) { + const ir_edge_t *edge; -static void phi_class_build(ir_node *irn, pset *pc) { - int i, max; + assert((! phi_classes->pure_phi_classes || is_Phi(irn)) && "Node must be Phi when pure_phi_classes set."); /* 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)); + if (_get_phi_class(&phi_classes->ph, irn)) { + DBG((phi_classes->dbg, LEVEL_2, "\talready done for %+F\n", irn)); return; } /* The initial call to phi_class_build doesn't - * provide a pset, so alloc it */ - if (!pc) { - DBG((dbg, LEVEL_1, "Computing phi class for %+F\n", irn)); + * provide a nodeset, so alloc it */ + if (! pc) { + DBG((phi_classes->dbg, LEVEL_1, "Computing phi class for %+F:\n", irn)); assert(is_Phi(irn)); - pc = pset_new_ptr(4); + pc = phase_alloc(&phi_classes->ph, sizeof(*pc)); + *pc = NEW_ARR_F(ir_node *, 0); + DBG((phi_classes->dbg, LEVEL_2, "\tcreated class %p in container %p\n", *pc, pc)); } /* 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); + DBG((phi_classes->dbg, LEVEL_1, "\t\tadding %+F to class %p, container %p\n", irn, *pc, pc)); + ARR_APP1(ir_node *, *pc, irn); + _set_phi_class(&phi_classes->ph, irn, pc); /* Check the 'neighbour' irns */ if (is_Phi(irn) && mode_is_datab(get_irn_mode(irn))) { + int i; + DBG((phi_classes->dbg, LEVEL_2, "\tchecking args of %+F:\n", irn)); /* Add all args of the phi to the phi-class. */ - for (i=0, max=get_irn_arity(irn); i= 0; --i) { + ir_node *op = get_irn_n(irn, i); + DBG((phi_classes->dbg, LEVEL_2, "\tchecking arg %+F\n", op)); + if (! phi_classes->pure_phi_classes || is_Phi(op)) + phi_class_build(phi_classes, op, pc); + } } /* Add a user of the irn to the class, * iff it is a phi node */ - const ir_edge_t *edge; - foreach_out_edge(irn, edge) { - ir_node *user = edge->src; - 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); + if (! phi_classes->pure_phi_classes || 1) { + DBG((phi_classes->dbg, LEVEL_2, "\tchecking users of %+F:\n", irn)); + foreach_out_edge(irn, edge) { + ir_node *user = edge->src; + DBG((phi_classes->dbg, LEVEL_2, "\tchecking user %+F ... ", user)); + if (is_Phi(user) && mode_is_datab(get_irn_mode(user))) { + DB((phi_classes->dbg, LEVEL_2, "is a Phi, descend\n")); + phi_class_build(phi_classes, user, pc); + } + else { + DB((phi_classes->dbg, LEVEL_2, "not a Phi, skip\n")); + } + } } } -pset *phi_class_compute_by_phis(pset *all_phi_nodes) { - int i; - ir_node *phi; - pset *all_phi_classes = pset_new_ptr_default(); +/** + * Call by a walker. If @p node is Phi, it build the Phi class starting from this node. + */ +static void phi_class_construction_walker(ir_node *node, void *env) { + phi_classes_t *pc = env; + + if (is_Phi(node) && mode_is_datab(get_irn_mode(node))) { + ir_node ***irn_pc = _get_phi_class(&pc->ph, node); - 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)); - } + if (! irn_pc) { + ir_node **pc_values; + phi_class_build(pc, node, NULL); - return all_phi_classes; + pc_values = *_get_phi_class(&pc->ph, node); + DBG((pc->dbg, LEVEL_1, "inserting phiclass %p (%d members) into all classes\n", pc_values, ARR_LEN(pc_values))); + + pset_insert_ptr(pc->all_phi_classes, pc_values); + } + } } -static void phi_class_construction_walker(ir_node *node, void *env) { - if (is_Phi(node) && mode_is_datab(get_irn_mode(node))) - phi_class_build(node, NULL); +/** + * Walk over the irg and build the Phi classes. + */ +static void phi_class_compute(phi_classes_t *pc) { + irg_walk_graph(pc->irg, phi_class_construction_walker, NULL, pc); } -static void phi_class_destruction_walker(ir_node *node, void *env) { - pset *clss = _get_phi_class(node); - if (clss) { - del_pset(clss); - _set_phi_class(node, NULL); +/** + * Build the Phi classes for the set of given Phis. + */ +static void phi_class_compute_by_phis(phi_classes_t *pc, ir_nodeset_t *all_phi_nodes) { + if (ir_nodeset_size(all_phi_nodes) > 0) { + ir_nodeset_iterator_t iter; + ir_node *phi; + + foreach_ir_nodeset(all_phi_nodes, phi, iter) { + ir_node ***irn_pc = _get_phi_class(&pc->ph, phi); + + assert(is_Phi(phi) && mode_is_datab(get_irn_mode(phi))); + + if (! irn_pc) { + ir_node **pc_values; + + phi_class_build(pc, phi, NULL); + + pc_values = *_get_phi_class(&pc->ph, phi); + DBG((pc->dbg, LEVEL_1, "inserting phiclass %p into all classes\n", pc_values)); + + pset_insert_ptr(pc->all_phi_classes, pc_values); + } + } } } -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); +/** + * Return the array containing all nodes assigned to the same Phi class as @p irn. + */ +ir_node **get_phi_class(phi_classes_t *pc, ir_node *irn) { + return *_get_phi_class(&pc->ph, irn); +} + +/** + * Assigns a new array of nodes representing the new Phi class to @p irn. + */ +void set_phi_class(phi_classes_t *pc, ir_node *irn, ir_node **cls) { + _set_phi_class(&pc->ph, irn, &cls); } -void phi_class_free(ir_graph *irg) { - irg_walk_graph(irg, phi_class_destruction_walker, NULL, NULL); +/** + * Returns a set containing all computed Phi classes. + */ +pset *get_all_phi_classes(phi_classes_t *pc) { + return pc->all_phi_classes; +} + +/** + * Builds the Phi classes for all Phis in @p irg. + * @return The Phi class object for the @p irg. + */ +phi_classes_t *phi_class_new_from_irg(ir_graph *irg, int pure_phi_classes) { + phi_classes_t *res = xmalloc(sizeof(*res)); + + FIRM_DBG_REGISTER(res->dbg, "ir.ana.phiclass"); + phase_init(&res->ph, "phi_classes", irg, PHASE_DEFAULT_GROWTH, irn_phi_class_init, NULL); + + res->irg = irg; + res->all_phi_classes = pset_new_ptr(5); + res->pure_phi_classes = pure_phi_classes; + + phi_class_compute(res); + + return res; } -pset *get_phi_class(const ir_node *irn) { - return get_irn_phi_info(irn)->phi_class; +/** + * Builds all Phi classes for the given set of Phis. + * @return The Phis class object for @p all_phis. + */ +phi_classes_t *phi_class_new_from_set(ir_graph *irg, ir_nodeset_t *all_phis, int pure_phi_classes) { + phi_classes_t *res = xmalloc(sizeof(*res)); + + FIRM_DBG_REGISTER(res->dbg, "ir.ana.phiclass"); + phase_init(&res->ph, "phi_classes", irg, PHASE_DEFAULT_GROWTH, irn_phi_class_init, NULL); + + res->irg = irg; + res->all_phi_classes = pset_new_ptr(5); + res->pure_phi_classes = pure_phi_classes; + + phi_class_compute_by_phis(res, all_phis); + + return res; } -void phi_class_init(void) { - dbg = firm_dbg_register("ir.ana.phiclass"); - firm_dbg_set_mask(dbg, DEBUG_LVL); - phi_irn_data_offset = register_additional_node_data(sizeof(phi_info_t)); +/** + * Free all allocated data. + */ +void phi_class_free(phi_classes_t *pc) { + ir_node **ipc; + foreach_pset(pc->all_phi_classes, ipc) { + DEL_ARR_F(ipc); + } + del_pset(pc->all_phi_classes); + phase_free(&pc->ph); + xfree(pc); }