/**
- * @author Daniel Grund
- * @date 09.12.2004
+ * @author Daniel Grund, Christian Wuerdig
+ * @cvsid $Id$
+ * @date 09.08.2005
*/
+#ifdef HAVE_CONFIG_H
+# include "config.h"
+#endif
-#include <stdio.h>
-#include <stdlib.h>
-#include <string.h>
+#ifdef HAVE_STDLIB_H
+# include <stdlib.h>
+#endif
+#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"
+
+struct _phi_classes_t {
+ phase_t 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(phase_t *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(phase_t *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(phase_t *ph, ir_node *irn, void *data) {
+ irn_phi_class_t *ipc = data ? data : phase_alloc(ph, sizeof(ipc[0]));
+ 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;
-size_t phi_irn_data_offset = 0;
-static firm_dbg_module_t *dbgphi = NULL;
+ assert((! phi_classes->pure_phi_classes || is_Phi(irn)) && "Node must be Phi when pure_phi_classes set.");
-#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
+ /* 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;
+ }
-#define is_Const(n) (get_irn_opcode(n) == iro_Const)
+ /* 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));
+ }
+ /* 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);
+
+ /* 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' represented 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, pset *all_phi_nodes) {
+ if (pset_count(all_phi_nodes)) {
+ ir_node *phi;
+
+ foreach_pset(all_phi_nodes, phi) {
+ 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;
- for (i = 0, n = get_irn_arity(curr_phi); i < n; i++) {
- ir_node *arg, *phi;
+ phi_class_build(pc, phi, NULL);
- arg = get_irn_n(curr_phi, i);
- DBG((dbgphi, 1, " Arg %n\n", arg));
+ pc_values = *_get_phi_class(&pc->ph, phi);
+ DBG((pc->dbg, LEVEL_1, "inserting phiclass %p into all classes\n", pc_values));
- 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);
+ 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 *clss = _get_phi_class(node);
- if (clss) {
- del_pset(clss);
- clss = 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(sizeof(*res));
+
+ FIRM_DBG_REGISTER(res->dbg, "ir.ana.phiclass");
+ phase_init(&res->ph, "phi_classes", irg, PHASE_DEFAULT_GROWTH, irn_phi_class_init);
+
+ res->irg = irg;
+ res->all_phi_classes = pset_new_ptr(5);
+ res->pure_phi_classes = pure_phi_classes;
+
+ phi_class_compute(res);
-void phi_class_free(ir_graph *irg) {
- irg_walk_graph(irg, phi_class_destruction_walker, NULL, NULL);
+ 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, pset *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);
+
+ 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);
}
projects / libfirm / blobdiff