nsz Git - libfirm/blob - ir/ana/phiclass.c

   1 /**
   2  * @author Daniel Grund, Christian Wuerdig
   3  * @cvsid  $Id$
   4  * @date   09.08.2005
   5  */
   6 #ifdef HAVE_CONFIG_H
   7 # include "config.h"
   8 #endif
   9
  10 #ifdef HAVE_STDLIB_H
  11 # include <stdlib.h>
  12 #endif
  13
  14 #include "irnode.h"
  15 #include "debug.h"
  16 #include "irgwalk.h"
  17 #include "irop_t.h"
  18 #include "iredges_t.h"
  19 #include "phiclass.h"
  20 #include "irphase_t.h"
  21
  22 struct _phi_classes_t {
  23         phase_t  ph;                 /* The phase object holding the irn data */
  24         pset     *all_phi_classes;   /* A set containing all Phi classes */
  25         ir_graph *irg;               /* The irg this is all about */
  26         DEBUG_ONLY(firm_dbg_module_t *dbg);
  27 };
  28
  29 typedef struct _irn_phi_class_t {
  30         ir_node ***phi_cls; /* the array of node pointers representing the class */
  31 } irn_phi_class_t;
  32
  33 static INLINE ir_node ***_get_phi_class(phase_t *ph, ir_node *irn) {
  34         irn_phi_class_t *ipc = phase_get_or_set_irn_data(ph, irn);
  35         return ipc->phi_cls;
  36 }
  37
  38 static INLINE void _set_phi_class(phase_t *ph, ir_node *irn, ir_node ***cls) {
  39         irn_phi_class_t *ipc = phase_get_or_set_irn_data(ph, irn);
  40         ipc->phi_cls = cls;
  41 }
  42
  43 /* initialize data structure for given irn in given phase */
  44 static void *irn_phi_class_init(phase_t *ph, ir_node *irn, void *data) {
  45         irn_phi_class_t *ipc = data ? data : phase_alloc(ph, sizeof(ipc[0]));
  46         memset(ipc, 0, sizeof(ipc[0]));
  47         return ipc;
  48 }
  49
  50 /**
  51  * Builds the phi class, starting from.
  52  * @param phi_classes  The phi class object
  53  * @param irn          The to start from
  54  * @param pc           The phi class this irn should be put into.
  55  *                     Set to NULL if you want a new one.
  56  */
  57 static void phi_class_build(phi_classes_t *phi_classes, ir_node *irn, ir_node ***pc) {
  58         const ir_edge_t *edge;
  59
  60         /* If irn has a phi class assigned already
  61          * return immediately to stop recursion */
  62         if (_get_phi_class(&phi_classes->ph, irn)) {
  63                 DBG((phi_classes->dbg, LEVEL_2, "  already done for %+F\n", irn));
  64                 return;
  65         }
  66
  67         /* The initial call to phi_class_build doesn't
  68          * provide a nodeset, so alloc it */
  69         if (! pc) {
  70                 DBG((phi_classes->dbg, LEVEL_1, "Computing phi class for %+F\n", irn));
  71                 assert(is_Phi(irn));
  72                 pc  = phase_alloc(&phi_classes->ph, sizeof(*pc));
  73                 *pc = NEW_ARR_F(ir_node *, 0);
  74         }
  75
  76         /* Add the irn to the phi class */
  77         DBG((phi_classes->dbg, LEVEL_1, "  adding %+F\n", irn));
  78         ARR_APP1(ir_node *, *pc, irn);
  79         _set_phi_class(&phi_classes->ph, irn, pc);
  80
  81         /* Check the 'neighbour' irns */
  82         if (is_Phi(irn) && mode_is_datab(get_irn_mode(irn))) {
  83                 int i;
  84
  85                 /* Add all args of the phi to the phi-class. */
  86                 for (i = get_irn_arity(irn) - 1; i >= 0; --i) {
  87                         ir_node *op = get_irn_n(irn, i);
  88                         DBG((phi_classes->dbg, LEVEL_2, "  checking arg %+F\n", op));
  89                         phi_class_build(phi_classes, op, pc);
  90                 }
  91         }
  92
  93         /* Add a user of the irn to the class,
  94          * iff it is a phi node  */
  95         foreach_out_edge(irn, edge) {
  96                 ir_node *user = edge->src;
  97                 DBG((phi_classes->dbg, LEVEL_2, "  checking user %+F\n", user));
  98                 if (is_Phi(user) && mode_is_datab(get_irn_mode(user)))
  99                         phi_class_build(phi_classes, user, pc);
 100         }
 101 }
 102
 103 /**
 104  * Call by a walker. If @p node is Phi, it build the Phi class starting from this node.
 105  */
 106 static void phi_class_construction_walker(ir_node *node, void *env) {
 107         phi_classes_t *pc = env;
 108
 109         if (is_Phi(node) && mode_is_datab(get_irn_mode(node))) {
 110                 ir_node ***irn_pc = _get_phi_class(&pc->ph, node);
 111
 112                 if (! irn_pc) {
 113                         phi_class_build(pc, node, NULL);
 114                         pset_insert_ptr(pc->all_phi_classes, *_get_phi_class(&pc->ph, node));
 115                 }
 116         }
 117 }
 118
 119 /**
 120  * Walk over the irg and build the Phi classes.
 121  */
 122 static void phi_class_compute(phi_classes_t *pc) {
 123         irg_walk_graph(pc->irg, phi_class_construction_walker, NULL, pc);
 124 }
 125
 126 /**
 127  * Build the Phi classes for the set of given Phis.
 128  */
 129 static void phi_class_compute_by_phis(phi_classes_t *pc, pset *all_phi_nodes) {
 130         if (pset_count(all_phi_nodes)) {
 131                 ir_node *phi;
 132
 133                 foreach_pset(all_phi_nodes, phi) {
 134                         ir_node ***irn_pc = _get_phi_class(&pc->ph, phi);
 135
 136                         assert(is_Phi(phi) && mode_is_datab(get_irn_mode(phi)));
 137
 138                         if (! irn_pc) {
 139                                 phi_class_build(pc, phi, NULL);
 140                                 pset_insert_ptr(pc->all_phi_classes, *_get_phi_class(&pc->ph, phi));
 141                         }
 142                 }
 143         }
 144 }
 145
 146 /**
 147  * Return the array containing all nodes assigned to the same Phi class as @p irn.
 148  */
 149 ir_node **get_phi_class(phi_classes_t *pc, ir_node *irn) {
 150         return *_get_phi_class(&pc->ph, irn);
 151 }
 152
 153 /**
 154  * Assigns a new array of nodes representing the new Phi class to @p irn.
 155  */
 156 void set_phi_class(phi_classes_t *pc, ir_node *irn, ir_node **cls) {
 157         _set_phi_class(&pc->ph, irn, &cls);
 158 }
 159
 160 /**
 161  * Returns a set containing all computed Phi classes.
 162  */
 163 pset *get_all_phi_classes(phi_classes_t *pc) {
 164         return pc->all_phi_classes;
 165 }
 166
 167 /**
 168  * Builds the Phi classes for all Phis in @p irg.
 169  * @return The Phi class object for the @p irg.
 170  */
 171 phi_classes_t *phi_class_new_from_irg(ir_graph *irg) {
 172         phi_classes_t *res = xmalloc(sizeof(*res));
 173
 174         FIRM_DBG_REGISTER(res->dbg, "ir.ana.phiclass");
 175         phase_init(&res->ph, "phi_classes", irg, PHASE_DEFAULT_GROWTH, irn_phi_class_init);
 176
 177         res->irg             = irg;
 178         res->all_phi_classes = pset_new_ptr(5);
 179
 180         phi_class_compute(res);
 181
 182         return res;
 183 }
 184
 185 /**
 186  * Builds all Phi classes for the given set of Phis.
 187  * @return The Phis class object for @p all_phis.
 188  */
 189 phi_classes_t *phi_class_new_from_set(ir_graph *irg, pset *all_phis) {
 190         phi_classes_t *res = xmalloc(sizeof(*res));
 191
 192         FIRM_DBG_REGISTER(res->dbg, "ir.ana.phiclass");
 193         phase_init(&res->ph, "phi_classes", irg, PHASE_DEFAULT_GROWTH, irn_phi_class_init);
 194
 195         res->irg             = irg;
 196         res->all_phi_classes = pset_new_ptr(5);
 197
 198         phi_class_compute_by_phis(res, all_phis);
 199
 200         return res;
 201 }
 202
 203 /**
 204  * Free all allocated data.
 205  */
 206 void phi_class_free(phi_classes_t *pc) {
 207         ir_node **ipc;
 208         foreach_pset(pc->all_phi_classes, ipc) {
 209                 DEL_ARR_F(ipc);
 210         }
 211         del_pset(pc->all_phi_classes);
 212         phase_free(&pc->ph);
 213         xfree(pc);
 214 }