2 * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved.
4 * This file is part of libFirm.
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.
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.
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
22 * @brief Implementation of phiclass analysis
23 * @author Daniel Grund, Christian Wuerdig
39 #include "iredges_t.h"
41 #include "irphase_t.h"
42 #include "irnodeset.h"
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);
52 typedef struct _irn_phi_class_t {
53 ir_node ***phi_cls; /* the array of node pointers representing the class */
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);
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);
66 /* initialize data structure for given irn in given phase */
67 static void *irn_phi_class_init(ir_phase *ph, const ir_node *irn, void *data) {
68 irn_phi_class_t *ipc = data ? data : phase_alloc(ph, sizeof(ipc[0]));
70 memset(ipc, 0, sizeof(ipc[0]));
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.
81 static void phi_class_build(phi_classes_t *phi_classes, ir_node *irn, ir_node ***pc) {
82 const ir_edge_t *edge;
84 assert((! phi_classes->pure_phi_classes || is_Phi(irn)) && "Node must be Phi when pure_phi_classes set.");
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));
93 /* The initial call to phi_class_build doesn't
94 * provide a nodeset, so alloc it */
96 DBG((phi_classes->dbg, LEVEL_1, "Computing phi class for %+F:\n", 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));
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);
108 /* Check the 'neighbour' irns */
109 if (is_Phi(irn) && mode_is_datab(get_irn_mode(irn))) {
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);
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);
133 DB((phi_classes->dbg, LEVEL_2, "not a Phi, skip\n"));
140 * Call by a walker. If @p node is Phi, it build the Phi class starting from this node.
142 static void phi_class_construction_walker(ir_node *node, void *env) {
143 phi_classes_t *pc = env;
145 if (is_Phi(node) && mode_is_datab(get_irn_mode(node))) {
146 ir_node ***irn_pc = _get_phi_class(&pc->ph, node);
150 phi_class_build(pc, node, NULL);
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)));
155 pset_insert_ptr(pc->all_phi_classes, pc_values);
161 * Walk over the irg and build the Phi classes.
163 static void phi_class_compute(phi_classes_t *pc) {
164 irg_walk_graph(pc->irg, phi_class_construction_walker, NULL, pc);
168 * Build the Phi classes for the set of given Phis.
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;
175 foreach_ir_nodeset(all_phi_nodes, phi, iter) {
176 ir_node ***irn_pc = _get_phi_class(&pc->ph, phi);
178 assert(is_Phi(phi) && mode_is_datab(get_irn_mode(phi)));
183 phi_class_build(pc, phi, NULL);
185 pc_values = *_get_phi_class(&pc->ph, phi);
186 DBG((pc->dbg, LEVEL_1, "inserting phiclass %p into all classes\n", pc_values));
188 pset_insert_ptr(pc->all_phi_classes, pc_values);
195 * Return the array containing all nodes assigned to the same Phi class as @p irn.
197 ir_node **get_phi_class(phi_classes_t *pc, ir_node *irn) {
198 return *_get_phi_class(&pc->ph, irn);
202 * Assigns a new array of nodes representing the new Phi class to @p irn.
204 void set_phi_class(phi_classes_t *pc, ir_node *irn, ir_node **cls) {
205 _set_phi_class(&pc->ph, irn, &cls);
209 * Returns a set containing all computed Phi classes.
211 pset *get_all_phi_classes(phi_classes_t *pc) {
212 return pc->all_phi_classes;
216 * Builds the Phi classes for all Phis in @p irg.
217 * @return The Phi class object for the @p irg.
219 phi_classes_t *phi_class_new_from_irg(ir_graph *irg, int pure_phi_classes) {
220 phi_classes_t *res = XMALLOC(phi_classes_t);
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);
226 res->all_phi_classes = pset_new_ptr(5);
227 res->pure_phi_classes = pure_phi_classes;
229 phi_class_compute(res);
235 * Builds all Phi classes for the given set of Phis.
236 * @return The Phis class object for @p all_phis.
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(phi_classes_t);
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);
245 res->all_phi_classes = pset_new_ptr(5);
246 res->pure_phi_classes = pure_phi_classes;
248 phi_class_compute_by_phis(res, all_phis);
254 * Free all allocated data.
256 void phi_class_free(phi_classes_t *pc) {
258 foreach_pset(pc->all_phi_classes, ipc) {
261 del_pset(pc->all_phi_classes);