10 #include "bechordal.h"
14 #include "bephicongr_t.h"
15 #include "bephicoal_t.h"
19 #define MAX_PHI_CLS_SIZE (1<<(sizeof(unsigned char)*8)) /* possible colors added should fit into unsigned char */
23 static firm_dbg_module_t *dbgphi = NULL;
26 typedef enum _live_status_t {
32 typedef struct _phi_unit_t {
34 unsigned char phi_count;
35 ir_node **members; /* [0..phi_count-1] are phi nodes. [phi_count..count-1] the rest/arguments of the phis */
37 int *tgt_colors; /* [i] is the color to set for members[i]. [i] == -1 means dont change anything for members[i]*/
38 live_status_t *live_info; /* [i] says how/where members[i] is live */
45 static INLINE void set_color(ir_node *irn, int col) {
46 if (!pset_find_ptr(done, irn)) {
47 set_irn_color(irn, col);
48 pset_insert_ptr(done, irn);
53 static void coalesce(phi_unit_t *pu) {
55 if (pu->phi_count != 1) {
56 DBG((dbgphi, 1, "Dropped: phicount\n"));
61 done = pset_new_ptr(64);
63 for (i = 0; i < pu->count; ++i)
64 if (pu->live_info[i] & livein) {
65 DBG((dbgphi, 1, "Dropped: live-in\n"));
69 for (i = 0; i < pu->count; ++i) {
72 if (pu->tgt_colors[i] == -1)
75 /* TODO: if we move ahead to swapping (not just allocating new colors) this is wrong */
76 set_color(pu->members[i], pu->tgt_colors[i]);
77 if (pu->live_info[i] & liveout) {
78 bl = get_dominated_dfs(get_nodes_block(pu->members[i]));
88 static void ana_1_phi(phi_unit_t *pu) {
89 ir_node *phi, *phi_blk;
90 int i, o, n, col, best_color, size, best_size;
91 ir_node **cand, **max_set, **best_max_set;
93 cand = malloc(pu->count * sizeof(ir_node*));
94 max_set = malloc(pu->count * sizeof(ir_node*));
95 best_max_set = malloc(pu->count * sizeof(ir_node*));
98 phi_blk = get_nodes_block(phi);
102 DBG((dbgphi, 1, "\tLiveness info\n"));
104 if (is_live_out(phi_blk, phi)) {
105 pu->live_info[0] = liveout;
106 DBG((dbgphi, 1, "\t\t%n lives out\n", phi));
110 for (i = 0, n = get_irn_arity(phi); i < n; ++i) {
112 ir_node *arg, *block_ith_pred;
114 arg = get_irn_n(phi, i);
115 block_ith_pred = get_nodes_block(get_irn_n(phi_blk, i));
117 /* find the arg in the members array */
119 for (o = 0; o < pu->count; ++o)
120 if (pu->members[o] == arg) {
124 assert(midx != -1 && "All args have to be in the members!\n");
126 if (is_live_in(block_ith_pred, arg)) {
127 pu->live_info[midx] |= livein;
128 DBG((dbgphi, 1, "\t\t%n lives in\n", arg));
131 if (is_live_out(block_ith_pred, arg)) {
132 pu->live_info[midx] |= liveout;
133 DBG((dbgphi, 1, "\t\t%n lives out\n", arg));
137 /* find best color */
139 for (col = 0; col < MAX_COLORS; ++col) { /* TODO: try phi color first */
140 DBG((dbgphi, 1, "\tTesting colors %d\n", col));
142 memset(cand, 0, pu->count * sizeof(ir_node*));
143 memset(max_set, 0, pu->count * sizeof(ir_node*));
145 /* BETTER: Alle die mit dem phi interferieren koennen eigentlich
146 * schon frueher raus, da unabhaengig von Farbe. */
147 /* for this color get all potential candidates for a max indep. set */
150 for (i = 1; i < pu->count; ++i)
151 if ((!bitset_is_set(pu->used_cols[i], col) || get_irn_color(pu->members[i]) == col)
152 && !phi_ops_interfere(phi, pu->members[i])) {
153 /* color is free or already used by the node
154 * and argument is not interfering with phi */
155 cand[i] = pu->members[i];
156 DBG((dbgphi, 1, "\t\tAdding candidate %n\n", cand[i]));
159 if (size <= best_size) {
160 /* If the candidate set is smaller the max indep. set wont be larger :) */
164 /* determine the max indep. set */
165 /* TODO: make this 'un-greedy' */
167 for (i = 0; i < pu->count; ++i) {
172 for (o = 0; o < pu->count; ++o) {
175 if (phi_ops_interfere(cand[i], max_set[o])) {
176 DBG((dbgphi, 1, "\t\t\n"));
183 DBG((dbgphi, 1, "\t\tAdding to set %n\n", cand[i]));
184 max_set[i] = cand[i];
190 DBG((dbgphi, 1, "\t\tColor %d resulted in a set size of %d\n", col, size));
192 /* Did we find a better max set? */
193 if (size > best_size) {
200 best_max_set = max_set;
204 /* Is this a best possible set? */
205 /* BETTER: Find a better lower bound than pu->count, considering interferences */
206 if (best_size == pu->count)
209 DBG((dbgphi, 1, "Best color was %d. %d of %d copies needed.\n", best_color, pu->count-best_size, pu->count-1));
212 /* now we have the best_max_set with its best_size
213 * so set the tgt_colors */
214 for (i = 0; i < pu->count; ++i)
215 if (best_max_set[i] && get_irn_color(best_max_set[i]) != best_color)
216 pu->tgt_colors[i] = best_color;
218 pu->tgt_colors[i] = -1;
226 static phi_unit_t *new_phi_unit(pset *pc) {
231 assert(pset_count(pc) <= MAX_PHI_CLS_SIZE && "Phi class too large!");
233 pu = malloc(sizeof(phi_unit_t));
234 pu->count = pset_count(pc);
235 pu->members = malloc(pu->count * sizeof(*pu->members));
236 pu->used_cols = malloc(pu->count * sizeof(bitset_t*));
237 pu->tgt_colors = malloc(pu->count * sizeof(int));
238 pu->live_info = calloc(pu->count, sizeof(ir_node*));
241 /* fill the members array */
242 DBG((dbgphi, 1, "Phi class:\n"));
245 for (n = (ir_node *)pset_first(pc); n; n = (ir_node *)pset_next(pc)) {
246 DBG((dbgphi, 1, "\t%n\n", n));
248 pu->members[i++] = n;
250 pu->members[o--] = n;
253 DBG((dbgphi, 1, "\n"));
256 /* fill used colors array */
257 for (i = 0; i < pu->count; ++i)
258 pu->used_cols[i] = get_ra_block_info(get_nodes_block(pu->members[i]))->used_colors;
261 if (pu->phi_count == 1) {
272 static void free_phi_unit(phi_unit_t *pu) {
273 DBG((dbgphi, 1, "\n"));
276 free(pu->tgt_colors);
282 void be_phi_coalesce(pset *all_phi_classes) {
286 for (pc = (pset *)pset_first(all_phi_classes); pc; pc = (pset *)pset_next(all_phi_classes)) {
287 pu = new_phi_unit(pc);
294 void be_phi_coal_init(void) {
295 dbgphi = firm_dbg_register("Phi coalescing");
296 firm_dbg_set_mask(dbgphi, DEBUG_LVL);