16 #include "irprintf_t.h"
20 #include "bephicongr_t.h"
22 #include "bechordal.h"
25 size_t phi_irn_data_offset = 0;
26 firm_dbg_module_t *dbgmod = NULL;
28 void be_phi_congr_class_init(void) {
29 dbgmod = firm_dbg_register("Phi congr. classes");
30 firm_dbg_set_mask(dbgmod, 1);
31 phi_irn_data_offset = register_additional_node_data(sizeof(phi_info_t));
34 #define get_phi(irn) get_irn_phi_info(irn)->phi
35 #define set_phi(irn, p) get_irn_phi_info(irn)->phi = p
36 #define set_phi_class(irn, cls) get_irn_phi_info(irn)->phi_class = cls
38 #define is_Const(n) (get_irn_opcode(n) == iro_Const)
41 * Insert a node to the phi class of a phi node
42 * @param class The phi congruence class
43 * @param phi The phi node holding the class
44 * @param arg Node which gets assigned to the class
46 static void inline phi_class_insert(pset *class, ir_node *phi, ir_node *arg) {
47 /*DBG((dbgmod, 1, "\tinsert %n in %n\n", arg, phi));*/
48 ir_debugf("\tinsert %n in %n\n", arg, phi);
49 if (!(is_Const(arg) && CONSTS_SPLIT_PHI_CLASSES))
51 pset_insert_ptr(class, arg);
56 * Assigns all operands of a phi node
57 * to a (new) phi congruence class
58 * @param n Phi node, of which all args get reassigned
59 * @param new_tgt Phi node representing new phi congruence class
61 static void phi_class_correct(ir_node *n, ir_node *new_tgt) {
65 assert(is_Phi(n) && is_Phi(new_tgt) && "These must be phi nodes.");
66 ir_debugf("\tcorrect %n\n", n);
68 /* copy all class members from n to new_tgt. Duplicates eliminated by pset */
69 src = get_phi_class(n);
70 tgt = get_phi_class(new_tgt);
71 for (p = (ir_node *)pset_first(src); p; p = (ir_node *)pset_next(src))
72 phi_class_insert(tgt, new_tgt, p);
74 /* phi class of n is no longer needed */
75 set_phi_class(n, NULL);
81 * Determines the phi congruence class of a phi node.
82 * This will assign a phi class to all operands of this
83 * phi node. Exceptions may be const nodes: See CONSTS_SPLIT_PHI_CLASSES
85 static void det_phi_congr_class(ir_node *curr_phi) {
88 assert(is_Phi(curr_phi) && "This must be a phi node.");
89 ir_debugf("Det. phi class of %n.\n", curr_phi);
91 pc = get_phi_class(curr_phi);
94 set_phi_class(curr_phi, pc);\
95 phi_class_insert(pc, curr_phi, curr_phi);
98 for (i = 0, n = get_irn_arity(curr_phi); i < n; i++) {
101 arg = get_irn_n(curr_phi, i);
102 ir_debugf(" Arg %n\n", arg);
105 if (phi == NULL) { /* Argument is not assigned to another phi class. */
106 phi_class_insert(pc, curr_phi, arg);
107 } else if (phi != curr_phi) {
108 assert(!is_Const(arg) && "Const nodes must not have a phi class assigned");
109 phi_class_correct(phi, curr_phi);
112 ir_debugf("Size now: %d\n", get_phi_class_size(curr_phi));
116 * Determines the liveness interference information
117 * of a phi congruence class.
119 static void det_interference(ir_node *n) {
121 ir_node **members, *p;
125 pc = get_phi_class(n);
129 count = pset_count(pc);
130 members = (ir_node **) malloc(count * sizeof(ir_node*));
132 ir_debugf("\nChecking phi class of node %n:\n", n);
133 for (i=0, p = (ir_node *)pset_first(pc); p; p = (ir_node *)pset_next(pc))
137 //determine interference of phi args
138 for (i = 0; i < count-1; ++i) {
140 for (o = i+1; o < count; ++o) {
141 ir_debugf("Checking %n\t%n", members[i], members[o]);
142 if (phi_ops_interfere(members[i], members[o])) {
143 ir_debugf("\tinterfere\n");
144 get_irn_phi_info(n)->interf_pairs++;
146 get_irn_phi_info(n)->interf_vals++;
151 ir_debugf("\tclean\n");
160 static void phi_class_walker(ir_node *node, void *env) {
161 if (!(is_Phi(node) && mode_is_datab(get_irn_mode(node)))) return;
162 det_phi_congr_class(node);
166 static void phi_class_inteference_walker(ir_node *node, void *env) {
167 if (!(is_Phi(node) && mode_is_datab(get_irn_mode(node)))) return;
168 det_interference(node);
172 void be_phi_congr_classes(ir_graph *irg) {
173 irg_walk_graph(irg, phi_class_walker, NULL, NULL);
174 irg_walk_graph(irg, phi_class_inteference_walker, NULL, NULL);