2 * @author Daniel Grund, Christian Wuerdig
18 #include "iredges_t.h"
20 #include "irphase_t.h"
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);
29 typedef struct _irn_phi_class_t {
30 ir_node ***phi_cls; /* the array of node pointers representing the class */
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);
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);
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]));
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.
57 static void phi_class_build(phi_classes_t *phi_classes, ir_node *irn, ir_node ***pc) {
58 const ir_edge_t *edge;
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));
67 /* The initial call to phi_class_build doesn't
68 * provide a nodeset, so alloc it */
70 DBG((phi_classes->dbg, LEVEL_1, "Computing phi class for %+F\n", irn));
72 pc = phase_alloc(&phi_classes->ph, sizeof(*pc));
73 *pc = NEW_ARR_F(ir_node *, 0);
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);
81 /* Check the 'neighbour' irns */
82 if (is_Phi(irn) && mode_is_datab(get_irn_mode(irn))) {
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);
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);
104 * Call by a walker. If @p node is Phi, it build the Phi class starting from this node.
106 static void phi_class_construction_walker(ir_node *node, void *env) {
107 phi_classes_t *pc = env;
109 if (is_Phi(node) && mode_is_datab(get_irn_mode(node))) {
110 ir_node ***irn_pc = _get_phi_class(&pc->ph, node);
113 phi_class_build(pc, node, NULL);
114 pset_insert_ptr(pc->all_phi_classes, *_get_phi_class(&pc->ph, node));
120 * Walk over the irg and build the Phi classes.
122 static void phi_class_compute(phi_classes_t *pc) {
123 irg_walk_graph(pc->irg, phi_class_construction_walker, NULL, pc);
127 * Build the Phi classes for the set of given Phis.
129 static void phi_class_compute_by_phis(phi_classes_t *pc, pset *all_phi_nodes) {
130 if (pset_count(all_phi_nodes)) {
133 foreach_pset(all_phi_nodes, phi) {
134 ir_node ***irn_pc = _get_phi_class(&pc->ph, phi);
136 assert(is_Phi(phi) && mode_is_datab(get_irn_mode(phi)));
139 phi_class_build(pc, phi, NULL);
140 pset_insert_ptr(pc->all_phi_classes, *_get_phi_class(&pc->ph, phi));
147 * Return the array containing all nodes assigned to the same Phi class as @p irn.
149 ir_node **get_phi_class(phi_classes_t *pc, ir_node *irn) {
150 return *_get_phi_class(&pc->ph, irn);
154 * Assigns a new array of nodes representing the new Phi class to @p irn.
156 void set_phi_class(phi_classes_t *pc, ir_node *irn, ir_node **cls) {
157 _set_phi_class(&pc->ph, irn, &cls);
161 * Returns a set containing all computed Phi classes.
163 pset *get_all_phi_classes(phi_classes_t *pc) {
164 return pc->all_phi_classes;
168 * Builds the Phi classes for all Phis in @p irg.
169 * @return The Phi class object for the @p irg.
171 phi_classes_t *phi_class_new_from_irg(ir_graph *irg) {
172 phi_classes_t *res = xmalloc(sizeof(*res));
174 FIRM_DBG_REGISTER(res->dbg, "ir.ana.phiclass");
175 phase_init(&res->ph, "phi_classes", irg, PHASE_DEFAULT_GROWTH, irn_phi_class_init);
178 res->all_phi_classes = pset_new_ptr(5);
180 phi_class_compute(res);
186 * Builds all Phi classes for the given set of Phis.
187 * @return The Phis class object for @p all_phis.
189 phi_classes_t *phi_class_new_from_set(ir_graph *irg, pset *all_phis) {
190 phi_classes_t *res = xmalloc(sizeof(*res));
192 FIRM_DBG_REGISTER(res->dbg, "ir.ana.phiclass");
193 phase_init(&res->ph, "phi_classes", irg, PHASE_DEFAULT_GROWTH, irn_phi_class_init);
196 res->all_phi_classes = pset_new_ptr(5);
198 phi_class_compute_by_phis(res, all_phis);
204 * Free all allocated data.
206 void phi_class_free(phi_classes_t *pc) {
208 foreach_pset(pc->all_phi_classes, ipc) {
211 del_pset(pc->all_phi_classes);