#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"
+#define DEBUG_LVL 0
size_t phi_irn_data_offset = 0;
-firm_dbg_module_t *dbgmod = NULL;
+static firm_dbg_module_t *dbgphi = NULL;
void be_phi_congr_class_init(void) {
- dbgmod = firm_dbg_register("Phi congr. classes");
- firm_dbg_set_mask(dbgmod, 1);
+ dbgphi = firm_dbg_register("Phi classes");
+ firm_dbg_set_mask(dbgphi, DEBUG_LVL);
phi_irn_data_offset = register_additional_node_data(sizeof(phi_info_t));
}
#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((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);
}
/**
- * 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((dbgphi, 1, "\tcorrect %n\n", n));
/* copy all class members from n to new_tgt. Duplicates eliminated by pset */
src = get_phi_class(n);
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);
}
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((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);\
+ set_phi_class(curr_phi, pc);
phi_class_insert(pc, curr_phi, curr_phi);
}
ir_node *arg, *phi;
arg = get_irn_n(curr_phi, i);
- ir_debugf(" Arg %n\n", arg);
+ 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) && "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((dbgphi, 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");
- }
- }
+pset *be_phi_congr_classes(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))
+ 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(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);
}
- 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);
+ return all_phi_classes;
}