16 #include "bechordal.h"
19 #include "bephicongr_t.h"
20 #include "bephicoal_t.h"
22 #define DEBUG_LVL SET_LEVEL_3
25 /* some things for readable code */
26 #define CHANGE_SAVE NULL
27 #define CHANGE_IMPOSSIBLE (ir_node *)1
28 #define CHANGE_NYI (ir_node *)2
29 typedef enum _perform_t { dryrun = 0, perform = 1 } perform_t;
30 /* TODO: ask/check if additional ir_node-space is initialized with 0000 */
31 //#define belongs_to_a_phi_class(n) (get_irn_phi_info(n)->phi)
32 //#define is_color_free(bl,col) (!bitset_is_set(get_ra_block_info(bl)->used_colors, col))
34 typedef struct _phi_unit_t {
36 unsigned char phi_count;
39 ir_node **members; /**< [0] is the phi node. [1..count-1] the arguments of the phi not interfering with it */
40 int *colors; /**< [i] is the color to set for members[i]. [i] == NO_COLOR means dont change anything for members[i]*/
41 /* TODO: perhaps unneccessary */
42 char *is_live_in; /**< [i]==1 means members[i] is live-in in (all of) its cf-pred-blocks of the phi node */
46 static firm_dbg_module_t *dbgphi = NULL;
47 int XXX_copies=0, XXX_count=0;
51 * Contains ir_nodes of phi-classes whose colors may change unlimited times.
52 * These nodes are not optimizable, so there is no need to pin their color.
54 static pset *free_nodes = NULL;
57 * Contains already optimized ir_nodes of phi-classes fully processed.
58 * So one can perform a check not to switch them twice or more.
60 static pset *pinned_global = NULL;
63 * Contains optimized ir_nodes of the phi-classes
64 * currently optimized. So one can perform a check not to switch them
67 static pset *pinned_local = NULL;
70 * Contains the hypothetic colors of currently processed phi unit
72 static set *hyp_cols = NULL;
74 typedef struct _hyp_col_t {
79 int set_cmp_hyp_col_t(const void *x, const void *y, size_t size) {
80 return ((hyp_col_t *)x)->irn != ((hyp_col_t *)y)->irn;
85 * @return The hypothetic color of the irn if available.
86 * Otherwise the current color of it.
88 static INLINE int get_hyp_color(ir_node *irn) {
92 found = set_find(hyp_cols, &hc, sizeof(hc), HASH_PTR(irn));
96 return get_irn_color(irn);
100 * Sets the hypothetic color of an irn
102 static INLINE void set_hyp_color(ir_node *irn, int color) {
106 found = set_find(hyp_cols, &hc, sizeof(hc), HASH_PTR(irn));
108 found->color = color;
111 set_insert(hyp_cols, &hc, sizeof(hc), HASH_PTR(irn));
118 * Variable neede in _color_irn.
119 * Not on stack, because never changed during recursion.
121 static perform_t _color_irn_perform;
124 * Get all nodes which conflict with the color-setting of a node, because they
125 * have the same color and are living together at some point in time.
126 * @param irn The ir_node to find conflicting nodes for
127 * @param color The color the conflicting nodes must have
128 * @param bl The root-block of the dom-sub-tree to start the search from.
129 * @param exc An exceptional node which is never added to the result set of conflicting nodes
130 * @param res An obstack to grow the resulting nodes on.
132 static void get_conflicting_nodes(const ir_node *irn, int color, ir_node *bl, const ir_node *exc, struct obstack *res) {
136 /* setup the queue */
138 obstack_ptr_grow(&q, bl);
142 /* process the queue */
144 ir_node *curr_bl, *sub_bl;
147 curr_bl = ((ir_node **)obstack_base(&q))[out++];
149 /* Add to the result all nodes in the block which live in target color
150 * and interfere with the irn */
151 for (i = 0, max = get_irn_n_outs(curr_bl); i < max; ++i) {
152 ir_node *n = get_irn_out(curr_bl, i);
154 if (!is_allocatable_irn(n))
156 if (_color_irn_perform == perform)
157 n_col = get_irn_color(n);
159 n_col = get_hyp_color(n);
161 if (n != exc && get_hyp_color(n) == color && phi_ops_interfere(irn, n))
162 obstack_ptr_grow(res, n);
165 /* If irn lives out check i-dominated blocks where the irn lives in */
167 if (is_live_out(curr_bl, irn)) {
168 dominates_for_each(curr_bl, sub_bl)
169 if (is_live_in(sub_bl, irn)) {
170 obstack_ptr_grow(&q, sub_bl);
176 obstack_free(&q, NULL);
181 * Tries to set the color of @p n to @p col. Performs recoloring of other nodes
182 * as required to preserve correctness. Recursive.
183 * @param irn The node to set the color for
184 * @param col The color to set.
185 * @param trigger The irn that caused the wish to change the color of the irn
186 * @return CHANGE_SAVE iff setting the color is possible.
187 * CHANGE_IMPOSSIBLE iff conflicts with reg-constraintsis occured.
188 * Else the conflicting ir_node is returned.
190 * ASSUMPTION: Assumes that a life range of a single value can't be spilt into
191 * several smaller intervals where other values can live in between.
193 static ir_node *_color_irn(ir_node *irn, int col, const ir_node *trigger) {
195 struct obstack confl_ob;
196 ir_node **confl, *cn;
199 if (_color_irn_perform == perform)
200 irn_col = get_irn_color(irn);
202 irn_col = get_hyp_color(irn);
204 obstack_init(&confl_ob);
209 if (pset_find_ptr(pinned_global, irn)) {
210 DBG((dbgphi, LEVEL_3, "\t\t\t%n \t~~> %n := %d: Pinned other\n", trigger, irn, col));
215 if (pset_find_ptr(pinned_local, irn)) {
216 DBG((dbgphi, LEVEL_3, "\t\t\t%n \t~~> %n := %d: Pinned current\n", trigger, irn, col));
221 /* process all nodes which would conflict with this change */
222 irn_bl = get_nodes_block(irn);
223 get_conflicting_nodes(irn, col, irn_bl, trigger, &confl_ob);
224 obstack_ptr_grow(&confl_ob, NULL);
225 confl = (ir_node **) obstack_finish(&confl_ob);
227 for (i = 0, cn = confl[0]; cn; cn = confl[++i]) {
230 /* for now don't let the changes spread in root-direction of the dom-tree */
231 if (is_live_in(irn_bl, cn)) {
232 DBG((dbgphi, LEVEL_3, "\t\t\t%n \t~~> %n := %d: NYI %n\n", trigger, irn, col, cn));
237 /* try to color the conflicting node cn with the color of the irn itself */
238 DBG((dbgphi, LEVEL_3, "\t\t\t%n \t~~> %n := %d: Subcheck\n", trigger, irn, col));
239 sub_res = _color_irn(cn, irn_col, irn);
240 if (sub_res != CHANGE_SAVE) {
245 /* if we arrive here all sub changes can be applied,
246 * so it is save to change this irn */
249 DBG((dbgphi, LEVEL_2, "\t\t\t%n \t~~> %n := %d: Save\n", trigger, irn, col));
250 obstack_free(&confl_ob, NULL);
251 if (_color_irn_perform == perform)
252 set_irn_color(irn, col);
254 set_hyp_color(irn, col);
258 DBG((dbgphi, LEVEL_2, "\t\t\t%n \t~~> %n := %d: Conflict\n", trigger, irn, col));
259 obstack_free(&confl_ob, NULL);
260 assert(!_color_irn_perform && "When applying changes these must be save, but if you reach here they aren't!");
265 static ir_node *color_irn(ir_node *irn, int col, perform_t do_what) {
268 _color_irn_perform = do_what;
269 res = _color_irn(irn, col, irn);
271 if (res == CHANGE_SAVE && !pset_find_ptr(free_nodes, irn)) {
272 if (do_what == perform) {
273 DBG((dbgphi, LEVEL_2, "\t\t\t\t\t @G %n\n", irn));
274 pset_insert_ptr(pinned_global, irn);
276 DBG((dbgphi, LEVEL_2, "\t\t\t\t\t @L %n\n", irn));
277 pset_insert_ptr(pinned_local, irn);
285 * Tries to set as much members of a phi unit as possible to color @p col.
286 * - Each change taken alone is guaranteed to be conflict free.
287 * - _If_ all members are neither live-in nor live-out in their cf-pred-blocks
288 * _then_ all changes together can be applied conflict free.
289 * - _If_ there is a member, which is live-in or live-out in its cf-pred-block
290 * of the phi node, it is possible that all changes together will conflict.
291 * TODO: Check above comment with swapping complete colors in mind
292 * TODO: Write sth. about dom-tree influence on this.
294 static int try_colors(phi_unit_t *pu, int col, int b_size) {
296 int i, o, cand_size, mis_size;
297 ir_node **cand, **mis;
300 pinned_local = pset_new_ptr(8);
301 hyp_cols = new_set(set_cmp_hyp_col_t, 8);
303 /* first init pessimistically, so we can just return
304 * if we see there wont be a better result */
306 for (i = 0; i < pu->count; ++i)
307 pu->colors[i] = NO_COLOR;
309 /* For all members check if color would be possible.
310 * Does not check if color is possible in combination with
311 * other members colors being set */
313 for (i = 0; i < pu->count; ++i) {
314 DBG((dbgphi, 1, "\t\t Testing %n\n", pu->members[i]));
315 if (color_irn(pu->members[i], col, dryrun) == CHANGE_SAVE) {
316 DBG((dbgphi, 1, "\t\t\tAdding to cand\n"));
317 obstack_ptr_grow(&ob, pu->members[i]);
320 DBG((dbgphi, 1, "\t\t\tImpossible\n"));
322 /* if color is not possible for the phi node then exit (phi comes first)*/
326 cand = obstack_finish(&ob);
328 /* shortcut: if cand is worse than best then mis wont be better. */
329 if (cand_size < b_size)
332 /* now take the candidates cand and determine a max independent set
333 * with respect to edges representing live range interference */
334 /* TODO: make this 'un-greedy' */
335 DBG((dbgphi, 1, "\t\t Max indep set\n"));
336 for (i = 0; i < cand_size; ++i) {
338 for (o = 0; o < mis_size; ++o) {
339 mis = (ir_node**) obstack_base(&ob);
340 if (phi_ops_interfere(cand[i], mis[o])) {
347 DBG((dbgphi, 1, "\t\t\tAdding to mis %n\n", cand[i]));
348 obstack_ptr_grow(&ob, cand[i]);
352 mis = obstack_finish(&ob);
354 /* Now set the colors of all nodes in the mis to col.
355 * HINT: Set the color of all nodes, even if one has the same color already */
356 for (i = 0; i < pu->count; ++i)
357 for (o = 0; o < mis_size; ++o)
358 if (pu->members[i] == mis[o])
363 del_pset(pinned_local);
364 obstack_free(&ob, NULL);
370 * Sets the colors of members[i] to colors[i].
371 * All changes togehter must be conflict free.
373 static void set_colors(phi_unit_t *pu) {
376 for (i = 0; i < pu->count; ++i)
377 if (pu->colors[i] != NO_COLOR)
378 color_irn(pu->members[i], pu->colors[i], perform);
383 * Tries to re-allocate colors of this phi-class, to achieve a lower number of
384 * copies placed during phi destruction. Optimized version. Works only for
385 * phi-classes/phi-units with exactly 1 phi node, which is the case for approx.
386 * 80% of all phi classes.
388 static void coalesce_1_phi(phi_unit_t *pu) {
389 int *b_colors, b_size, b_color;
392 b_colors = malloc(pu->count * sizeof(*b_colors));
394 /* init best search result */
397 for (i = 0; i < pu->count; ++i)
398 b_colors[i] = NO_COLOR;
400 /* find optimum of all colors */
401 for (col = MAX_COLORS-1; col >= 0; --col) {
402 DBG((dbgphi, 1, "\tTrying color %d\n", col));
403 size = try_colors(pu, col, b_size);
405 /* did we find a better max ind. set? */
409 memcpy(b_colors, pu->colors, pu->count * sizeof(*b_colors));
410 DBG((dbgphi, 1, "\t!! Better size: %d\n", b_size));
413 /* shortcut: if all members can be colored we are content */
414 if (b_size == pu->count)
417 DBG((dbgphi, 1, "\tBest color: %d Copies: %d/%d\n", b_color, pu->count-b_size, pu->count));
418 XXX_copies += pu->count-b_size;
419 XXX_count += pu->count;
420 if (b_color == NO_COLOR)
423 /* now apply the found optimum */
424 memcpy(pu->colors, b_colors, pu->count * sizeof(*b_colors));
433 * Tries to re-allocate colors of this phi-class, to achieve a lower number of
434 * copies placed during phi destruction. General purpose version.
436 static void coalesce_n_phi(phi_unit_t *pu) {
437 DBG((dbgphi, 1, "\n"));
443 * Prepares a phi class for further processing as a phi unit.
444 * @param pc The phi class to prepare.
445 * @return A so called phi unit containing some prepared informations
446 * needed by the following coalescing phase.
448 static phi_unit_t *new_phi_unit(pset *pc) {
450 ir_node *n, *phi = NULL;
452 /* get the phi count of this class */
453 pu = malloc(sizeof(*pu));
455 for (n = pset_first(pc); n; n = pset_next(pc))
461 if (pu->phi_count == 1) {
462 ir_node **tmp, *phi_block;
468 /* build member set not containing phi interferers */
469 DBG((dbgphi, 1, "Phi-1 class:\n"));
470 pu->count = 1; /*for the phi*/
471 for (n = pset_first(pc); n; n = pset_next(pc)) {
474 if (!phi_ops_interfere(phi, n)) {
475 DBG((dbgphi, 1, "\tAdding to members: %n\n", n));
476 obstack_ptr_grow(&ob, n);
479 DBG((dbgphi, 1, "\tPhi interferer: %n\n", n));
480 pset_insert_ptr(free_nodes, n);
483 tmp = obstack_finish(&ob);
484 pu->members = malloc(pu->count * sizeof(*pu->members));
485 pu->members[0] = phi;
486 memcpy(&pu->members[1], tmp, (pu->count-1) * sizeof(*tmp));
488 /* init of colors array */
489 pu->colors = malloc(pu->count * sizeof(*pu->colors));
491 /* live-in analysis */
492 /* HINT: It is possible that a node occurs twice as arg of a phi,
493 * one time being live-in, and another time not being live-in.
495 pu->is_live_in = calloc(pu->count, sizeof(*pu->is_live_in));
496 phi_block = get_nodes_block(phi);
497 for (i = 0, max = get_irn_arity(phi); i < max; ++i) {
499 ir_node *arg, *block_ith_pred;
501 arg = get_irn_n(phi, i);
502 block_ith_pred = get_nodes_block(get_irn_n(phi_block, i));
504 /* find the arg in the members array */
506 for (o = 0; o < pu->count; ++o)
507 if (pu->members[o] == arg) {
514 if (is_live_in(block_ith_pred, arg)) {
515 pu->is_live_in[midx] |= 1;
516 DBG((dbgphi, 1, "\t%n is live-in in %n\n", arg, block_ith_pred));
520 obstack_free(&ob, NULL);
522 DBG((dbgphi, 1, "Phi-n class:\n"));
526 DBG((dbgphi, 1, "\n"));
534 static void free_phi_unit(phi_unit_t *pu) {
535 if (pu->phi_count == 1) {
538 free(pu->is_live_in);
546 void be_phi_coalesce(pset *all_phi_classes) {
549 pinned_global = pset_new_ptr(256);
550 free_nodes = pset_new_ptr(64);
552 for (pc = pset_first(all_phi_classes); pc; pc = pset_next(all_phi_classes)) {
553 phi_unit_t *pu = new_phi_unit(pc);
554 if (pu->phi_count == 1)
561 DBG((dbgphi, 1, "Copies: %d / %d\n", XXX_copies, XXX_count));
563 del_pset(free_nodes);
564 del_pset(pinned_global);
568 void be_phi_coal_init(void) {
569 dbgphi = firm_dbg_register("Phi coalescing");
570 firm_dbg_set_mask(dbgphi, DEBUG_LVL);