X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fana%2Fphiclass.c;h=421cef92f1ae0620a0df5f0a20cb2d4de4f59ab0;hb=5da05531f4190e4bf3dccb416aaf1b3f5417073f;hp=40f0cf038934a4b97c8a4ff8e251cf240de7cbc4;hpb=8cedf9d2c38f2a21a910f6652921a9158727dc4b;p=libfirm diff --git a/ir/ana/phiclass.c b/ir/ana/phiclass.c index 40f0cf038..421cef92f 100644 --- a/ir/ana/phiclass.c +++ b/ir/ana/phiclass.c @@ -1,155 +1,260 @@ +/* + * 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.12.2004 + * @file + * @brief Implementation of phiclass analysis + * @author Daniel Grund, Christian Wuerdig + * @cvsid $Id$ + * @date 09.08.2005 */ +#include "config.h" -#include #include -#include +#include "irnode.h" #include "debug.h" -#include "irprog.h" #include "irgwalk.h" -#include "irop.h" -#include "phiclass_t.h" +#include "irop_t.h" +#include "iredges_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 0 +/* 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; +} + +/** + * 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; + + 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(&phi_classes->ph, irn)) { + DBG((phi_classes->dbg, LEVEL_2, "\talready done for %+F\n", irn)); + return; + } -size_t phi_irn_data_offset = 0; -static firm_dbg_module_t *dbgphi = NULL; + /* The initial call to phi_class_build doesn't + * 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 = 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)); + } -#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 + /* Add the irn to the phi class */ + 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); -#define is_Const(n) (get_irn_opcode(n) == iro_Const) + /* 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 = get_irn_arity(irn) - 1; 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 */ + 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")); + } + } + } +} /** - * 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 + * Call by a walker. If @p node is Phi, it build the Phi class starting from this node. */ -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); +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); + + if (! irn_pc) { + ir_node **pc_values; + phi_class_build(pc, node, NULL); + + 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); + } + } } /** - * 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 + * Walk over the irg and build the Phi classes. */ -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); +static void phi_class_compute(phi_classes_t *pc) { + irg_walk_graph(pc->irg, phi_class_construction_walker, NULL, pc); } /** - * 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 + * Build the Phi classes for the set of given Phis. */ -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)); - - pc = _get_phi_class(curr_phi); - if (!pc) { - pc = pset_new_ptr(2); - _set_phi_class(curr_phi, pc); - phi_class_insert(pc, curr_phi, curr_phi); - } +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; - for (i = 0, n = get_irn_arity(curr_phi); i < n; i++) { - ir_node *arg, *phi; + foreach_ir_nodeset(all_phi_nodes, phi, iter) { + ir_node ***irn_pc = _get_phi_class(&pc->ph, phi); - arg = get_irn_n(curr_phi, i); - DBG((dbgphi, 1, " Arg %n\n", arg)); + assert(is_Phi(phi) && mode_is_datab(get_irn_mode(phi))); - 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); + 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); + } } } - DBG((dbgphi, 1, "Size now: %d\n", pset_count(_get_phi_class(curr_phi)))); } -pset *phi_class_compute_by_phis(pset *all_phi_nodes) { - int i; - ir_node *phi; - pset *phi_class, *all_phi_classes; - - /* determine all phi classes */ - for (i = 0, phi = (ir_node *)pset_first(all_phi_nodes); phi; phi = (ir_node *)pset_next(all_phi_nodes)) - phi_class_det(phi); - - /* store them in a pset for fast retrieval */ - all_phi_classes = pset_new_ptr(64); - for (i = 0, phi = (ir_node *)pset_first(all_phi_nodes); phi; phi = (ir_node *)pset_next(all_phi_nodes)) { - phi_class = _get_phi_class(phi); - if (phi_class) - pset_insert_ptr(all_phi_classes, phi_class); - } - - return all_phi_classes; +/** + * 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); } -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); +/** + * 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_compute(ir_graph *irg) { - irg_walk_graph(irg, phi_class_construction_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; } -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; - } - } -} +/** + * 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(phi_classes_t); + + FIRM_DBG_REGISTER(res->dbg, "ir.ana.phiclass"); + phase_init(&res->ph, "phi_classes", irg, PHASE_DEFAULT_GROWTH, irn_phi_class_init, NULL); -void phi_class_free(ir_graph *irg) { - irg_walk_graph(irg, phi_class_destruction_walker, NULL, 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) { - ir_node *phi; - if (phi = _get_phi(irn), phi) - return _get_phi_class(phi); - else - return NULL; +/** + * 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(phi_classes_t); + + 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) { - dbgphi = firm_dbg_register("ir.ana.phiclass"); - firm_dbg_set_mask(dbgphi, 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); }