nsz Git - libfirm/blob - ir/be/bephicongr.c

   1 /**
   2  * @author Daniel Grund
   3  * @date 09.12.2004
   4  */
   5
   6 #include <stdio.h>
   7 #include <stdlib.h>
   8 #include <string.h>
   9
  10 #include "config.h"
  11 #include "irgraph.h"
  12 #include "irnode.h"
  13 #include "irgwalk.h"
  14 #include "irop.h"
  15 #include "irprog.h"
  16 #include "irprintf_t.h"
  17 #include "debug.h"
  18 #include "pset.h"
  19
  20 #include "bephicongr_t.h"
  21 #include "beutil.h"
  22 #include "bechordal.h"
  23
  24
  25 size_t phi_irn_data_offset = 0;
  26 firm_dbg_module_t *dbgmod = NULL;
  27
  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));
  32 }
  33
  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
  37
  38 #define is_Const(n)       (get_irn_opcode(n) == iro_Const)
  39
  40 /**
  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
  45  */
  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))
  50                 set_phi(arg, phi);
  51         pset_insert_ptr(class, arg);
  52 }
  53
  54
  55 /**
  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
  60  */
  61 static void phi_class_correct(ir_node *n, ir_node *new_tgt) {
  62         ir_node *p;
  63         pset *src, *tgt;
  64
  65     assert(is_Phi(n) && is_Phi(new_tgt) && "These must be phi nodes.");
  66         ir_debugf("\tcorrect %n\n", n);
  67
  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);
  73
  74         /* phi class of n is no longer needed */
  75         set_phi_class(n, NULL);
  76         del_pset(src);
  77 }
  78
  79
  80 /**
  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
  84  */
  85 static void det_phi_congr_class(ir_node *curr_phi) {
  86         pset *pc;
  87     int i, n;
  88     assert(is_Phi(curr_phi) && "This must be a phi node.");
  89     ir_debugf("Det. phi class of %n.\n", curr_phi);
  90
  91         pc = get_phi_class(curr_phi);
  92         if (!pc) {
  93                 pc = pset_new_ptr(2);
  94                 set_phi_class(curr_phi, pc);\
  95                 phi_class_insert(pc, curr_phi, curr_phi);
  96         }
  97
  98         for (i = 0, n = get_irn_arity(curr_phi); i < n; i++) {
  99                 ir_node *arg, *phi;
 100
 101                 arg = get_irn_n(curr_phi, i);
 102                 ir_debugf("    Arg %n\n", arg);
 103
 104                 phi = get_phi(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);
 110                 }
 111         }
 112         ir_debugf("Size now: %d\n", get_phi_class_size(curr_phi));
 113 }
 114
 115 /**
 116  * Determines the liveness interference information
 117  * of a phi congruence class.
 118  */
 119 static void det_interference(ir_node *n) {
 120         pset *pc;
 121         ir_node **members, *p;
 122         int count, i, o;
 123         int doit;
 124
 125         pc = get_phi_class(n);
 126         if (!pc)
 127                 return;
 128
 129         count = pset_count(pc);
 130         members = (ir_node **) malloc(count * sizeof(ir_node*));
 131
 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))
 134                 members[i++] = p;
 135         assert(i == count);
 136
 137         //determine interference of phi args
 138         for (i = 0; i < count-1; ++i) {
 139                 doit = 1;
 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++;
 145                                 if (doit) {
 146                                         get_irn_phi_info(n)->interf_vals++;
 147                                         doit = 0;
 148                                 }
 149
 150                         } else {
 151                                 ir_debugf("\tclean\n");
 152                         }
 153                 }
 154         }
 155
 156         free(members);
 157 }
 158
 159
 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);
 163 }
 164
 165
 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);
 169 }
 170
 171
 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);
 175 }