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

   1 /*
   2  * Copyright (C) 1995-2007 University of Karlsruhe.  All right reserved.
   3  *
   4  * This file is part of libFirm.
   5  *
   6  * This file may be distributed and/or modified under the terms of the
   7  * GNU General Public License version 2 as published by the Free Software
   8  * Foundation and appearing in the file LICENSE.GPL included in the
   9  * packaging of this file.
  10  *
  11  * Licensees holding valid libFirm Professional Edition licenses may use
  12  * this file in accordance with the libFirm Commercial License.
  13  * Agreement provided with the Software.
  14  *
  15  * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
  16  * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  17  * PURPOSE.
  18  */
  19
  20 /**
  21  * @file
  22  * @brief  Implementation of phiclass analysis
  23  * @author Daniel Grund, Christian Wuerdig
  24  * @cvsid  $Id$
  25  * @date   09.08.2005
  26  */
  27 #ifdef HAVE_CONFIG_H
  28 # include "config.h"
  29 #endif
  30
  31 #ifdef HAVE_STDLIB_H
  32 # include <stdlib.h>
  33 #endif
  34
  35 #include "irnode.h"
  36 #include "debug.h"
  37 #include "irgwalk.h"
  38 #include "irop_t.h"
  39 #include "iredges_t.h"
  40 #include "phiclass.h"
  41 #include "irphase_t.h"
  42 #include "irnodeset.h"
  43
  44 struct _phi_classes_t {
  45         ir_phase ph;                 /* The phase object holding the irn data */
  46         pset     *all_phi_classes;   /* A set containing all Phi classes */
  47         ir_graph *irg;               /* The irg this is all about */
  48         unsigned pure_phi_classes;   /* Build pure Phi classes */
  49         DEBUG_ONLY(firm_dbg_module_t *dbg);
  50 };
  51
  52 typedef struct _irn_phi_class_t {
  53         ir_node ***phi_cls; /* the array of node pointers representing the class */
  54 } irn_phi_class_t;
  55
  56 static INLINE ir_node ***_get_phi_class(ir_phase *ph, ir_node *irn) {
  57         irn_phi_class_t *ipc = phase_get_or_set_irn_data(ph, irn);
  58         return ipc->phi_cls;
  59 }
  60
  61 static INLINE void _set_phi_class(ir_phase *ph, ir_node *irn, ir_node ***cls) {
  62         irn_phi_class_t *ipc = phase_get_or_set_irn_data(ph, irn);
  63         ipc->phi_cls = cls;
  64 }
  65
  66 /* initialize data structure for given irn in given phase */
  67 static void *irn_phi_class_init(ir_phase *ph, ir_node *irn, void *data) {
  68         irn_phi_class_t *ipc = data ? data : phase_alloc(ph, sizeof(ipc[0]));
  69         (void) irn;
  70         memset(ipc, 0, sizeof(ipc[0]));
  71         return ipc;
  72 }
  73
  74 /**
  75  * Builds the phi class, starting from.
  76  * @param phi_classes  The phi class object
  77  * @param irn          The to start from
  78  * @param pc           The phi class this irn should be put into.
  79  *                     Set to NULL if you want a new one.
  80  */
  81 static void phi_class_build(phi_classes_t *phi_classes, ir_node *irn, ir_node ***pc) {
  82         const ir_edge_t *edge;
  83
  84         assert((! phi_classes->pure_phi_classes || is_Phi(irn)) && "Node must be Phi when pure_phi_classes set.");
  85
  86         /* If irn has a phi class assigned already
  87          * return immediately to stop recursion */
  88         if (_get_phi_class(&phi_classes->ph, irn)) {
  89                 DBG((phi_classes->dbg, LEVEL_2, "\talready done for %+F\n", irn));
  90                 return;
  91         }
  92
  93         /* The initial call to phi_class_build doesn't
  94          * provide a nodeset, so alloc it */
  95         if (! pc) {
  96                 DBG((phi_classes->dbg, LEVEL_1, "Computing phi class for %+F:\n", irn));
  97                 assert(is_Phi(irn));
  98                 pc  = phase_alloc(&phi_classes->ph, sizeof(*pc));
  99                 *pc = NEW_ARR_F(ir_node *, 0);
 100                 DBG((phi_classes->dbg, LEVEL_2, "\tcreated class %p in container %p\n", *pc, pc));
 101         }
 102
 103         /* Add the irn to the phi class */
 104         DBG((phi_classes->dbg, LEVEL_1, "\t\tadding %+F to class %p, container %p\n", irn, *pc, pc));
 105         ARR_APP1(ir_node *, *pc, irn);
 106         _set_phi_class(&phi_classes->ph, irn, pc);
 107
 108         /* Check the 'neighbour' irns */
 109         if (is_Phi(irn) && mode_is_datab(get_irn_mode(irn))) {
 110                 int i;
 111                 DBG((phi_classes->dbg, LEVEL_2, "\tchecking args of %+F:\n", irn));
 112                 /* Add all args of the phi to the phi-class. */
 113                 for (i = get_irn_arity(irn) - 1; i >= 0; --i) {
 114                         ir_node *op = get_irn_n(irn, i);
 115                         DBG((phi_classes->dbg, LEVEL_2, "\tchecking arg %+F\n", op));
 116                         if (! phi_classes->pure_phi_classes || is_Phi(op))
 117                                 phi_class_build(phi_classes, op, pc);
 118                 }
 119         }
 120
 121         /* Add a user of the irn to the class,
 122          * iff it is a phi node  */
 123         if (! phi_classes->pure_phi_classes || 1) {
 124                 DBG((phi_classes->dbg, LEVEL_2, "\tchecking users of %+F:\n", irn));
 125                 foreach_out_edge(irn, edge) {
 126                         ir_node *user = edge->src;
 127                         DBG((phi_classes->dbg, LEVEL_2, "\tchecking user %+F ... ", user));
 128                         if (is_Phi(user) && mode_is_datab(get_irn_mode(user))) {
 129                                 DB((phi_classes->dbg, LEVEL_2, "is a Phi, descend\n"));
 130                                 phi_class_build(phi_classes, user, pc);
 131                         }
 132                         else {
 133                                 DB((phi_classes->dbg, LEVEL_2, "not a Phi, skip\n"));
 134                         }
 135                 }
 136         }
 137 }
 138
 139 /**
 140  * Call by a walker. If @p node is Phi, it build the Phi class starting from this node.
 141  */
 142 static void phi_class_construction_walker(ir_node *node, void *env) {
 143         phi_classes_t *pc = env;
 144
 145         if (is_Phi(node) && mode_is_datab(get_irn_mode(node))) {
 146                 ir_node ***irn_pc = _get_phi_class(&pc->ph, node);
 147
 148                 if (! irn_pc) {
 149                         ir_node **pc_values;
 150                         phi_class_build(pc, node, NULL);
 151
 152                         pc_values = *_get_phi_class(&pc->ph, node);
 153                         DBG((pc->dbg, LEVEL_1, "inserting phiclass %p (%d members) into all classes\n", pc_values, ARR_LEN(pc_values)));
 154
 155                         pset_insert_ptr(pc->all_phi_classes, pc_values);
 156                 }
 157         }
 158 }
 159
 160 /**
 161  * Walk over the irg and build the Phi classes.
 162  */
 163 static void phi_class_compute(phi_classes_t *pc) {
 164         irg_walk_graph(pc->irg, phi_class_construction_walker, NULL, pc);
 165 }
 166
 167 /**
 168  * Build the Phi classes for the set of given Phis.
 169  */
 170 static void phi_class_compute_by_phis(phi_classes_t *pc, ir_nodeset_t *all_phi_nodes) {
 171         if (ir_nodeset_size(all_phi_nodes) > 0) {
 172                 ir_nodeset_iterator_t iter;
 173                 ir_node               *phi;
 174
 175                 foreach_ir_nodeset(all_phi_nodes, phi, iter) {
 176                         ir_node ***irn_pc = _get_phi_class(&pc->ph, phi);
 177
 178                         assert(is_Phi(phi) && mode_is_datab(get_irn_mode(phi)));
 179
 180                         if (! irn_pc) {
 181                                 ir_node **pc_values;
 182
 183                                 phi_class_build(pc, phi, NULL);
 184
 185                                 pc_values = *_get_phi_class(&pc->ph, phi);
 186                                 DBG((pc->dbg, LEVEL_1, "inserting phiclass %p into all classes\n", pc_values));
 187
 188                                 pset_insert_ptr(pc->all_phi_classes, pc_values);
 189                         }
 190                 }
 191         }
 192 }
 193
 194 /**
 195  * Return the array containing all nodes assigned to the same Phi class as @p irn.
 196  */
 197 ir_node **get_phi_class(phi_classes_t *pc, ir_node *irn) {
 198         return *_get_phi_class(&pc->ph, irn);
 199 }
 200
 201 /**
 202  * Assigns a new array of nodes representing the new Phi class to @p irn.
 203  */
 204 void set_phi_class(phi_classes_t *pc, ir_node *irn, ir_node **cls) {
 205         _set_phi_class(&pc->ph, irn, &cls);
 206 }
 207
 208 /**
 209  * Returns a set containing all computed Phi classes.
 210  */
 211 pset *get_all_phi_classes(phi_classes_t *pc) {
 212         return pc->all_phi_classes;
 213 }
 214
 215 /**
 216  * Builds the Phi classes for all Phis in @p irg.
 217  * @return The Phi class object for the @p irg.
 218  */
 219 phi_classes_t *phi_class_new_from_irg(ir_graph *irg, int pure_phi_classes) {
 220         phi_classes_t *res = xmalloc(sizeof(*res));
 221
 222         FIRM_DBG_REGISTER(res->dbg, "ir.ana.phiclass");
 223         phase_init(&res->ph, "phi_classes", irg, PHASE_DEFAULT_GROWTH, irn_phi_class_init, NULL);
 224
 225         res->irg              = irg;
 226         res->all_phi_classes  = pset_new_ptr(5);
 227         res->pure_phi_classes = pure_phi_classes;
 228
 229         phi_class_compute(res);
 230
 231         return res;
 232 }
 233
 234 /**
 235  * Builds all Phi classes for the given set of Phis.
 236  * @return The Phis class object for @p all_phis.
 237  */
 238 phi_classes_t *phi_class_new_from_set(ir_graph *irg, ir_nodeset_t *all_phis, int pure_phi_classes) {
 239         phi_classes_t *res = xmalloc(sizeof(*res));
 240
 241         FIRM_DBG_REGISTER(res->dbg, "ir.ana.phiclass");
 242         phase_init(&res->ph, "phi_classes", irg, PHASE_DEFAULT_GROWTH, irn_phi_class_init, NULL);
 243
 244         res->irg              = irg;
 245         res->all_phi_classes  = pset_new_ptr(5);
 246         res->pure_phi_classes = pure_phi_classes;
 247
 248         phi_class_compute_by_phis(res, all_phis);
 249
 250         return res;
 251 }
 252
 253 /**
 254  * Free all allocated data.
 255  */
 256 void phi_class_free(phi_classes_t *pc) {
 257         ir_node **ipc;
 258         foreach_pset(pc->all_phi_classes, ipc) {
 259                 DEL_ARR_F(ipc);
 260         }
 261         del_pset(pc->all_phi_classes);
 262         phase_free(&pc->ph);
 263         xfree(pc);
 264 }