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 #include "irnodeset.h"
  22
  23 struct _phi_classes_t {
  24         phase_t  ph;                 /* The phase object holding the irn data */
  25         pset     *all_phi_classes;   /* A set containing all Phi classes */
  26         ir_graph *irg;               /* The irg this is all about */
  27         unsigned pure_phi_classes;   /* Build pure Phi classes */
  28         DEBUG_ONLY(firm_dbg_module_t *dbg);
  29 };
  30
  31 typedef struct _irn_phi_class_t {
  32         ir_node ***phi_cls; /* the array of node pointers representing the class */
  33 } irn_phi_class_t;
  34
  35 static INLINE ir_node ***_get_phi_class(phase_t *ph, ir_node *irn) {
  36         irn_phi_class_t *ipc = phase_get_or_set_irn_data(ph, irn);
  37         return ipc->phi_cls;
  38 }
  39
  40 static INLINE void _set_phi_class(phase_t *ph, ir_node *irn, ir_node ***cls) {
  41         irn_phi_class_t *ipc = phase_get_or_set_irn_data(ph, irn);
  42         ipc->phi_cls = cls;
  43 }
  44
  45 /* initialize data structure for given irn in given phase */
  46 static void *irn_phi_class_init(phase_t *ph, ir_node *irn, void *data) {
  47         irn_phi_class_t *ipc = data ? data : phase_alloc(ph, sizeof(ipc[0]));
  48         memset(ipc, 0, sizeof(ipc[0]));
  49         return ipc;
  50 }
  51
  52 /**
  53  * Builds the phi class, starting from.
  54  * @param phi_classes  The phi class object
  55  * @param irn          The to start from
  56  * @param pc           The phi class this irn should be put into.
  57  *                     Set to NULL if you want a new one.
  58  */
  59 static void phi_class_build(phi_classes_t *phi_classes, ir_node *irn, ir_node ***pc) {
  60         const ir_edge_t *edge;
  61
  62         assert((! phi_classes->pure_phi_classes || is_Phi(irn)) && "Node must be Phi when pure_phi_classes set.");
  63
  64         /* If irn has a phi class assigned already
  65          * return immediately to stop recursion */
  66         if (_get_phi_class(&phi_classes->ph, irn)) {
  67                 DBG((phi_classes->dbg, LEVEL_2, "\talready done for %+F\n", irn));
  68                 return;
  69         }
  70
  71         /* The initial call to phi_class_build doesn't
  72          * provide a nodeset, so alloc it */
  73         if (! pc) {
  74                 DBG((phi_classes->dbg, LEVEL_1, "Computing phi class for %+F:\n", irn));
  75                 assert(is_Phi(irn));
  76                 pc  = phase_alloc(&phi_classes->ph, sizeof(*pc));
  77                 *pc = NEW_ARR_F(ir_node *, 0);
  78                 DBG((phi_classes->dbg, LEVEL_2, "\tcreated class %p in container %p\n", *pc, pc));
  79         }
  80
  81         /* Add the irn to the phi class */
  82         DBG((phi_classes->dbg, LEVEL_1, "\t\tadding %+F to class %p, container %p\n", irn, *pc, pc));
  83         ARR_APP1(ir_node *, *pc, irn);
  84         _set_phi_class(&phi_classes->ph, irn, pc);
  85
  86         /* Check the 'neighbour' irns */
  87         if (is_Phi(irn) && mode_is_datab(get_irn_mode(irn))) {
  88                 int i;
  89                 DBG((phi_classes->dbg, LEVEL_2, "\tchecking args of %+F:\n", irn));
  90                 /* Add all args of the phi to the phi-class. */
  91                 for (i = get_irn_arity(irn) - 1; i >= 0; --i) {
  92                         ir_node *op = get_irn_n(irn, i);
  93                         DBG((phi_classes->dbg, LEVEL_2, "\tchecking arg %+F\n", op));
  94                         if (! phi_classes->pure_phi_classes || is_Phi(op))
  95                                 phi_class_build(phi_classes, op, pc);
  96                 }
  97         }
  98
  99         /* Add a user of the irn to the class,
 100          * iff it is a phi node  */
 101         if (! phi_classes->pure_phi_classes || 1) {
 102                 DBG((phi_classes->dbg, LEVEL_2, "\tchecking users of %+F:\n", irn));
 103                 foreach_out_edge(irn, edge) {
 104                         ir_node *user = edge->src;
 105                         DBG((phi_classes->dbg, LEVEL_2, "\tchecking user %+F ... ", user));
 106                         if (is_Phi(user) && mode_is_datab(get_irn_mode(user))) {
 107                                 DB((phi_classes->dbg, LEVEL_2, "is a Phi, descend\n"));
 108                                 phi_class_build(phi_classes, user, pc);
 109                         }
 110                         else {
 111                                 DB((phi_classes->dbg, LEVEL_2, "not a Phi, skip\n"));
 112                         }
 113                 }
 114         }
 115 }
 116
 117 /**
 118  * Call by a walker. If @p node is Phi, it build the Phi class starting from this node.
 119  */
 120 static void phi_class_construction_walker(ir_node *node, void *env) {
 121         phi_classes_t *pc = env;
 122
 123         if (is_Phi(node) && mode_is_datab(get_irn_mode(node))) {
 124                 ir_node ***irn_pc = _get_phi_class(&pc->ph, node);
 125
 126                 if (! irn_pc) {
 127                         ir_node **pc_values;
 128                         phi_class_build(pc, node, NULL);
 129
 130                         pc_values = *_get_phi_class(&pc->ph, node);
 131                         DBG((pc->dbg, LEVEL_1, "inserting phiclass %p (%d members) into all classes\n", pc_values, ARR_LEN(pc_values)));
 132
 133                         pset_insert_ptr(pc->all_phi_classes, pc_values);
 134                 }
 135         }
 136 }
 137
 138 /**
 139  * Walk over the irg and build the Phi classes.
 140  */
 141 static void phi_class_compute(phi_classes_t *pc) {
 142         irg_walk_graph(pc->irg, phi_class_construction_walker, NULL, pc);
 143 }
 144
 145 /**
 146  * Build the Phi classes for the set of given Phis.
 147  */
 148 static void phi_class_compute_by_phis(phi_classes_t *pc, ir_nodeset_t *all_phi_nodes) {
 149         if (ir_nodeset_size(all_phi_nodes) > 0) {
 150                 ir_nodeset_iterator_t iter;
 151                 ir_node               *phi;
 152
 153                 foreach_ir_nodeset(all_phi_nodes, phi, iter) {
 154                         ir_node ***irn_pc = _get_phi_class(&pc->ph, phi);
 155
 156                         assert(is_Phi(phi) && mode_is_datab(get_irn_mode(phi)));
 157
 158                         if (! irn_pc) {
 159                                 ir_node **pc_values;
 160
 161                                 phi_class_build(pc, phi, NULL);
 162
 163                                 pc_values = *_get_phi_class(&pc->ph, phi);
 164                                 DBG((pc->dbg, LEVEL_1, "inserting phiclass %p into all classes\n", pc_values));
 165
 166                                 pset_insert_ptr(pc->all_phi_classes, pc_values);
 167                         }
 168                 }
 169         }
 170 }
 171
 172 /**
 173  * Return the array containing all nodes assigned to the same Phi class as @p irn.
 174  */
 175 ir_node **get_phi_class(phi_classes_t *pc, ir_node *irn) {
 176         return *_get_phi_class(&pc->ph, irn);
 177 }
 178
 179 /**
 180  * Assigns a new array of nodes representing the new Phi class to @p irn.
 181  */
 182 void set_phi_class(phi_classes_t *pc, ir_node *irn, ir_node **cls) {
 183         _set_phi_class(&pc->ph, irn, &cls);
 184 }
 185
 186 /**
 187  * Returns a set containing all computed Phi classes.
 188  */
 189 pset *get_all_phi_classes(phi_classes_t *pc) {
 190         return pc->all_phi_classes;
 191 }
 192
 193 /**
 194  * Builds the Phi classes for all Phis in @p irg.
 195  * @return The Phi class object for the @p irg.
 196  */
 197 phi_classes_t *phi_class_new_from_irg(ir_graph *irg, int pure_phi_classes) {
 198         phi_classes_t *res = xmalloc(sizeof(*res));
 199
 200         FIRM_DBG_REGISTER(res->dbg, "ir.ana.phiclass");
 201         phase_init(&res->ph, "phi_classes", irg, PHASE_DEFAULT_GROWTH, irn_phi_class_init);
 202
 203         res->irg              = irg;
 204         res->all_phi_classes  = pset_new_ptr(5);
 205         res->pure_phi_classes = pure_phi_classes;
 206
 207         phi_class_compute(res);
 208
 209         return res;
 210 }
 211
 212 /**
 213  * Builds all Phi classes for the given set of Phis.
 214  * @return The Phis class object for @p all_phis.
 215  */
 216 phi_classes_t *phi_class_new_from_set(ir_graph *irg, ir_nodeset_t *all_phis, int pure_phi_classes) {
 217         phi_classes_t *res = xmalloc(sizeof(*res));
 218
 219         FIRM_DBG_REGISTER(res->dbg, "ir.ana.phiclass");
 220         phase_init(&res->ph, "phi_classes", irg, PHASE_DEFAULT_GROWTH, irn_phi_class_init);
 221
 222         res->irg              = irg;
 223         res->all_phi_classes  = pset_new_ptr(5);
 224         res->pure_phi_classes = pure_phi_classes;
 225
 226         phi_class_compute_by_phis(res, all_phis);
 227
 228         return res;
 229 }
 230
 231 /**
 232  * Free all allocated data.
 233  */
 234 void phi_class_free(phi_classes_t *pc) {
 235         ir_node **ipc;
 236         foreach_pset(pc->all_phi_classes, ipc) {
 237                 DEL_ARR_F(ipc);
 238         }
 239         del_pset(pc->all_phi_classes);
 240         phase_free(&pc->ph);
 241         xfree(pc);
 242 }