X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbephicoal.c;h=1002d480b16d33e006cb111d93deaa3a86776088;hb=16cd557c101a0e9283182877b6c2362d548d02a5;hp=3edfa969e023104e78be4c5e23e6e9b33a4ec6cb;hpb=a2aee2be98f3aa25b1d3e793e383fac328c811ee;p=libfirm diff --git a/ir/be/bephicoal.c b/ir/be/bephicoal.c index 3edfa969e..1002d480b 100644 --- a/ir/be/bephicoal.c +++ b/ir/be/bephicoal.c @@ -6,288 +6,504 @@ #include #include "obst.h" +#include "set.h" #include "pset.h" #include "bitset.h" #include "debug.h" +#include "irouts.h" +#include "irdom.h" #include "bechordal.h" #include "belive.h" #include "bera_t.h" -#include "bephicongr_t.h" +#include "phiclass_t.h" #include "bephicoal_t.h" -#define DEBUG_LVL 1 +#define DEBUG_LVL SET_LEVEL_3 +#define MAX_COLORS 16 -#define MAX_PHI_CLS_SIZE (1<<(sizeof(unsigned char)*8)) /* possible colors added should fit into unsigned char */ -#define MAX_COLORS 32 -#define CHANGE_IMPOSSIBLE -1 -#define CHANGE_SAVE 1 +#define INITIAL_SLOTS_PINNED_GLOBAL 256 +#define INITIAL_SLOTS_FREE_NODES 128 +#define INITIAL_SLOTS_CHANGED_NODES 32 -#define DRYRUN 1 -#define PERFORM 0 +/* some things for readable code */ +#define CHANGE_SAVE NULL +#define CHANGE_IMPOSSIBLE (ir_node *)1 +#define CHANGE_NYI (ir_node *)2 +#define is_conflicting_node(n) (((int)n) > 2) -typedef struct _phi_unit_t { - unsigned char count; - unsigned char phi_count; +/** + * Models conflicts between nodes. These may be life range conflicts or + * pinning conflicts which may occur while changing colors + */ +typedef struct _conflict_t { + ir_node *n1, *n2; +} conflict_t; +/** + * If an irn is changed, the changes first get stored in a node_stat_t, + * to allow undo of changes in case of conflicts. + */ +typedef struct _node_stat_t { + ir_node *irn; + int color; + int undo_color; + char status; /**< Bit 0: pinned, Bit 1: removed */ +} node_stat_t; + +#define _set_pinned(nodestat) nodestat->status |= 1 +#define _set_removed(nodestat) nodestat->status |= 2 +#define _clear_pinned(nodestat) nodestat->status &= 255 ^ 1 +#define _clear_removed(nodestat) nodestat->status &= 255 ^ 2 +#define _is_pinned(nodestat) (nodestat->status & 1) +#define _is_removed(nodestat) (nodestat->status & 2) + +/** + * Central data structure. Contains infos needed during coalescing of the + * corresponding phi class. + */ +typedef struct _phi_unit_t { + unsigned char phi_count; /**< the number of phi nodes in this unit */ /* 1 phi */ - ir_node **members; /**< [0] is the phi node. [1..count-1] the arguments of the phi not interfering with it */ - int *colors; /**< [i] is the color to set for members[i]. [i] == NO_COLOR means dont change anything for members[i]*/ - char *is_live_in; /**< [i]==1 means members[i] is live-in in (all of) its cf-pred-blocks of the phi node */ - int size; /**< size of the max independent set of members. The set is markes by colors[i] != NO_COLOR */ - int changes; /**< number of re-assigned nodes belonging to phi-classes */ + unsigned char node_count; /**< size of the nodes-array */ + unsigned char conflict_count; /**< size of the conflicts-array */ + unsigned char conflict_count_org; /**< initial size of the conflicts-array */ + ir_node **nodes; /**< [0] is the phi node. [1..node_count-1] the arguments of the phi not interfering with it */ + conflict_t *conflicts; /**< pairs of conflicting ir_nodes. */ + set *changed_nodes; /**< contains node_stat_t's. */ } phi_unit_t; - static firm_dbg_module_t *dbgphi = NULL; -/** - * Contains ir_nodes of phi-classes whose colors were reassigned during coalescing. - * So one can check not to switch them twice or more. - */ -static pset *pinned_nodes = NULL; - /** * Contains ir_nodes of phi-classes whose colors may change unlimited times. * These nodes are not optimizable, so there is no need to pin their color. */ static pset *free_nodes = NULL; +/** + * Contains already optimized ir_nodes of phi-classes fully processed. + * So one can perform a check not to switch them twice or more. + */ +static pset *pinned_global = NULL; -/* TODO: ask/check if additional ir_node-space is initialized with 0000 */ -#define belongs_to_a_phi_class(n) (get_irn_phi_info(n)->phi) +int set_cmp_node_stat_t(const void *x, const void *y, size_t size) { + return ((node_stat_t *)x)->irn != ((node_stat_t *)y)->irn; +} -#define is_color_free(bl,col) (!bitset_is_set(get_ra_block_info(bl)->used_colors, col)) +/** + * Finds a node status entry of a node if existent. + */ +static INLINE node_stat_t *pu_find_node(phi_unit_t *pu, ir_node *irn) { + node_stat_t find; + find.irn = irn; + return set_find(pu->changed_nodes, &find, sizeof(find), HASH_PTR(irn)); +} /** - * Set the color of node @p n to @p col, but acts - * pinning aware. + * Finds a node status entry of a node if existent. Otherwise it will return + * an initialized new entry for this node. */ -static INLINE void set_color(ir_node *n, int col) { - assert(!pset_find_ptr(pinned_nodes, n)); - set_irn_color(n, col); - if (belongs_to_a_phi_class(n) && !pset_find_ptr(free_nodes, n)) - pset_insert_ptr(pinned_nodes, n); +static INLINE node_stat_t *pu_find_or_insert_node(phi_unit_t *pu, ir_node *irn) { + node_stat_t find; + find.irn = irn; + find.color = NO_COLOR; + find.undo_color = NO_COLOR; + find.status = 0; + return set_insert(pu->changed_nodes, &find, sizeof(find), HASH_PTR(irn)); } /** - * Tries to set the color of @p n to @p col. - * @param n The node to set the color for - * @param col The color to set. - * @param dryrun If true no colors are actually set, only testing is performed. - * If false colors get set and it must be sure that no conflicts will occur. - * @return If setting the color is impossible CHANGE_IMPOSSIBLE is returned - * else the number of nodes that need a (cascading) change is returned. + * @return The virtual color of a node, if set before, else just the real color. */ -static int color_irn(ir_node *n, int col, int dryrun) { - ir_node *bl; - int res = 0; - DBG((dbgphi, 1, "\t\t\t\t%n %d\n", n, col)); - assert(is_color(col)); - - if (get_irn_color(n) == col) { - DBG((dbgphi, 1, "\t\t\t\t\tSame\n")); - return 0; - } +static INLINE int pu_get_new_color(phi_unit_t *pu, ir_node *irn) { + node_stat_t *found = pu_find_node(pu, irn); + if (found) + return found->color; + else + return get_irn_color(irn); +} - if (pset_find_ptr(pinned_nodes, n)) { - DBG((dbgphi, 1, "\t\t\t\t\tPinned\n")); - if (!dryrun) - assert(0 && "No prior check with dryrun=1 or buggy"); - return CHANGE_IMPOSSIBLE; - } +/** + * Sets the virtual color of a node. + */ +static INLINE void pu_set_new_color(phi_unit_t *pu, ir_node *irn, int color) { + node_stat_t *found = pu_find_or_insert_node(pu, irn); + /* TODO Think about + * This is only correct if no color is set >=2 times while changing + * a single phi-unit-member */ + found->undo_color = found->color; + found->color = color; +} - bl = get_nodes_block(n); - if (is_color_free(bl, col) && !is_live_out(bl, n)) { - DBG((dbgphi, 1, "\t\t\t\t\tFree\n")); - if (!dryrun) - set_color(n, col); - return 1; - } +/** + * Checks if a node is removed from consideration respectively building + * a maximum independent set. + */ +static INLINE int pu_is_node_removed(phi_unit_t *pu, ir_node *irn) { + node_stat_t *found = pu_find_node(pu, irn); + if (found) + return _is_removed(found); + else + return 0; +} - /* for now, in the aldi-version return impossible */ - DBG((dbgphi, 1, "\t\t\t\t\tImpossible\n")); - return CHANGE_IMPOSSIBLE; +/** + * Removes a node from the base set, out of which a maximum independet + * set gets build from. + */ +static INLINE void pu_remove_node(phi_unit_t *pu, ir_node *irn) { + node_stat_t *found = pu_find_or_insert_node(pu, irn); + _set_removed(found); +} - return res; +/** + * Checks if a node is local pinned; i.e. it belongs to the same phi unit and + * has been optimized before the current processed one. + */ +static INLINE int pu_is_node_pinned(phi_unit_t *pu, ir_node *irn) { + node_stat_t *found = pu_find_node(pu, irn); + if (found) + return _is_pinned(found); + else + return 0; } +/** + * Local-pins a node, so optimizations of further nodes of the same phi unit + * can handle situations in which a color change would undo prior optimizations. + */ +static INLINE void pu_pin_node(phi_unit_t *pu, ir_node *irn) { + node_stat_t *found = pu_find_or_insert_node(pu, irn); + _set_pinned(found); +} /** - * Tries to set as much members of a phi unit as possible to color @p col. + * If a local pinned conflict occurs, a new edge in the conflict graph is added. + * The next maximum independent set build, will regard it. */ -static void try_colors(phi_unit_t *pu, int col, int b_size, int b_changes) { - struct obstack ob; - int i, o, cand_size, mis_size, changes; - ir_node **cand, **mis; - - cand_size = 0; - obstack_init(&ob); - - /* first init pessimistically, so we can just return - * if we see there wont be a better result */ - pu->size = 0; - for (i = 0; i < pu->count; ++i) - pu->colors[i] = NO_COLOR; - - /* For all members check if color would be possible. - * Does not check if color is possible in combination with - * other members colors being set */ - changes = 0; - for (i = 0; i < pu->count; ++i) { - int tmp_changes = color_irn(pu->members[i], col, DRYRUN); - if (tmp_changes != CHANGE_IMPOSSIBLE) { - DBG((dbgphi, 1, "\t\t\tAdding to cand %n\n", pu->members[i])); - obstack_ptr_grow(&ob, pu->members[i]); - cand_size++; - changes += tmp_changes; - } - /* if color is not possible for the phi node then exit (phi comes first)*/ - if (cand_size == 0) - goto ret; +static INLINE void pu_add_conflict(phi_unit_t *pu, ir_node *n1, ir_node *n2) { + int count = pu->conflict_count; + + assert(count != 255 && "Too much conflicts. Can hold max 255 entries"); + if ((count & 15) == 0) + pu->conflicts = realloc(pu->conflicts, (count + 16)*sizeof(*pu->conflicts)); + + if ((int)n1 < (int)n2) { + pu->conflicts[count].n1 = n1; + pu->conflicts[count].n2 = n2; + } else { + pu->conflicts[count].n1 = n2; + pu->conflicts[count].n2 = n1; } - cand = obstack_finish(&ob); - /* shortcut: if cand is worse than best the mis wont be better. */ - if (cand_size < b_size || (cand_size == b_size && changes >= b_changes)) - goto ret; + pu->conflict_count++; +} - /* now take the candidates cand and determine a max independent set - * with respect to edges representing live range interference */ - /* TODO: make this 'un-greedy' */ - mis_size = 0; - for (i = 0; i < cand_size; ++i) { +/** + * Checks if two nodes are in a conflict. + */ +static INLINE int pu_are_conflicting(phi_unit_t *pu, ir_node *n1, ir_node *n2) { + const ir_node *o1, *o2; + int i; + + if ((int)n1 < (int)n2) { + o1 = n1; + o2 = n2; + } else { + o1 = n2; + o2 = n1; + } + + for (i = 0; i < pu->conflict_count; ++i) + if (pu->conflicts[i].n1 == o1 && pu->conflicts[i].n2 == o2) + return 1; + return 0; +} + +/** + * Determines a maximum independent set with respect to the conflict edges + * in pu->conflicts and the nodes beeing all non-removed nodes of pu->nodes. + * TODO: make this 'un-greedy' + * TODO: be aware that phi nodes should find their way in the set. + * for 1 phi in greedy version this is no prob, cause is comes first at [0]. + */ +int pu_get_max_ind_set(phi_unit_t *pu, struct obstack *res) { + int i, o, size = 0; + ir_node **mis; + + DBG((dbgphi, 1, "\t\t Max indep set\n")); + for (i = 0; i < pu->node_count; ++i) { int intf_det = 0; - for (o = 0; o < mis_size; ++o) { - mis = (ir_node**) obstack_base(&ob); - if (values_interfere(cand[i], mis[o])) { + if (pu_is_node_removed(pu, pu->nodes[i])) + continue; + mis = (ir_node**) obstack_base(res); + for (o = 0; o < size; ++o) + if (phi_ops_interfere(pu->nodes[i], mis[o])) { intf_det = 1; break; } - } if (!intf_det) { - DBG((dbgphi, 1, "\t\t\tAdding to mis %n\n", cand[i])); - obstack_ptr_grow(&ob, cand[i]); - mis_size++; + DBG((dbgphi, 1, "\t\t\tAdding to mis %n\n", pu->nodes[i])); + obstack_ptr_grow(res, pu->nodes[i]); + size++; } } - mis = obstack_finish(&ob); - - /* Now set the colors of all nodes in the mis to col. - * - Each change taken alone is conflict free. - * - If all members are not live-in in their cf-pred-blocks there will be no - * conflict applying all changes - * - If there is a member, which is live-in in its cf-pred-block of the phi - * node, it is possible that all changes together will conflict. - */ - for (i = 0; i < pu->count; ++i) - for (o = 0; o < mis_size; ++o) - if (pu->members[i] == mis[o] && get_irn_color(pu->members[i]) != col) - pu->colors[i] = col; + return size; +} -ret: - obstack_free(&ob, NULL); +/** + * Performs virtual re-coloring of node @p n to color @p col. Virtual colors of + * other nodes are changed too, as required to preserve correctness. Function is + * aware of local and global pinning. Recursive. + * @param irn The node to set the color for + * @param col The color to set. + * @param trigger The irn that caused the wish to change the color of the irn + * @param changed_nodes An obstack on which all ir_nodes get growed on, which are changed + * @return CHANGE_SAVE iff setting the color is possible, with all transiteve effects. + * CHANGE_IMPOSSIBLE iff conflicts with reg-constraintsis occured. + * CHANGE_NYI iff an unhandled situation occurs. + * Else the first conflicting ir_node encountered is returned. + * + * ASSUMPTION: Assumes that a life range of a single value can't be spilt into + * several smaller intervals where other values can live in between. + */ +static ir_node *_pu_color_irn(phi_unit_t *pu, ir_node *irn, int col, const ir_node *trigger, struct obstack *changed_nodes) { + ir_node *res; + struct obstack confl_ob; + ir_node **confl, *cn; + int i, irn_col; + + obstack_init(&confl_ob); + irn_col = pu_get_new_color(pu, irn); + + if (irn_col == col) + goto ret_save; + if (pset_find_ptr(pinned_global, irn) || pu_is_node_pinned(pu, irn)) { + DBG((dbgphi, LEVEL_2, "\t\t\t%n \t~~> %n := %d: Pinned\n", trigger, irn, col)); + res = irn; + goto ret_confl; + } + + /* get all nodes which would conflict with this change */ + { + struct obstack q; + int in, out; + + /* setup the queue */ + obstack_init(&q); + obstack_ptr_grow(&q, get_nodes_block(irn)); + in = 1; + out = 0; + + /* process the queue */ + while (out < in) { + ir_node *curr_bl, *sub_bl; + int i, max; + + curr_bl = ((ir_node **)obstack_base(&q))[out++]; + + /* Add to the result all nodes in the block which live in target color + * and interfere with the irn */ + for (i = 0, max = get_irn_n_outs(curr_bl); i < max; ++i) { + ir_node *n = get_irn_out(curr_bl, i); + if (!is_allocatable_irn(n)) + continue; + if (n != trigger && pu_get_new_color(pu, n) == col && phi_ops_interfere(irn, n)) + obstack_ptr_grow(&confl_ob, n); + } + + /* If irn lives out check i-dominated blocks where the irn lives in */ + /* Fill the queue */ + if (is_live_out(curr_bl, irn)) { + dominates_for_each(curr_bl, sub_bl) + if (is_live_in(sub_bl, irn)) { + obstack_ptr_grow(&q, sub_bl); + in++; + } + } + } + obstack_free(&q, NULL); + obstack_ptr_grow(&confl_ob, NULL); + confl = (ir_node **) obstack_finish(&confl_ob); + } + + /* process all nodes which would conflict with this change */ + for (i = 0, cn = confl[0]; cn; cn = confl[++i]) { + ir_node *sub_res; + + /* try to color the conflicting node cn with the color of the irn itself */ + DBG((dbgphi, LEVEL_3, "\t\t\t%n \t~~> %n := %d: Subcheck\n", trigger, irn, col)); + sub_res = _pu_color_irn(pu, cn, irn_col, irn, changed_nodes); + if (sub_res != CHANGE_SAVE) { + res = sub_res; + goto ret_confl; + } + } + /* if we arrive here all sub changes can be applied, so it's save to change this irn */ + +ret_save: + DBG((dbgphi, LEVEL_2, "\t\t\t%n \t~~> %n := %d: Save\n", trigger, irn, col)); + obstack_free(&confl_ob, NULL); + pu_set_new_color(pu, irn, col); + obstack_ptr_grow(changed_nodes, irn); + return CHANGE_SAVE; + +ret_confl: + DBG((dbgphi, LEVEL_2, "\t\t\t%n \t~~> %n := %d: Conflict\n", trigger, irn, col)); + obstack_free(&confl_ob, NULL); + return res; } +#define pu_color_irn(pu,irn,col,ob) _pu_color_irn(pu, irn, col, irn, ob) /** - * Sets the colors of members[i] to colors[i] as far as possible. - * Each single change must be conflict free (checked by try_colors). - * In some cases not all colors can be set. + * Tries to set as much members of a phi unit as possible to color @p col. + * All changes taken together are guaranteed to be conflict free. */ -static void set_colors(phi_unit_t *pu) { - int i; - int change_is_save, live_in_occured = 0; +static int pu_try_color(phi_unit_t *pu, int col, int b_size) { + struct obstack ob_mis, ob_undo; + int i, redo, mis_size; + ir_node **mis; + + /* first init pessimistically. Just return if we can't get a better result */ + mis_size = 0; - for (i = 0; i < pu->count; ++i) - if (pu->colors[i] != NO_COLOR) { - if (pu->is_live_in[i]) - live_in_occured = 1; + obstack_init(&ob_mis); + obstack_init(&ob_undo); + redo = 1; + while (redo) { + redo = 0; + /* get a max independent set regarding current conflicts */ + mis_size = pu_get_max_ind_set(pu, &ob_mis); + mis = obstack_finish(&ob_mis); + + /* shortcut: if mis size is worse than best, then mis won't be better. */ + if (mis_size < b_size) + goto ret; - change_is_save = CHANGE_SAVE; - if (live_in_occured) - change_is_save = color_irn(pu->members[i], pu->colors[i], DRYRUN); + /* check if its possible to set the color for all members of the maximum set*/ + for (i = 0; i < mis_size; ++i) { + ir_node *test_node, *confl_node; - /* HINT: Dont change to == CHANGE_SAVE */ - if (change_is_save != CHANGE_IMPOSSIBLE) { - DBG((dbgphi, 1, "\t\tSetting %n to %d\n", pu->members[i], pu->colors[i])); - color_irn(pu->members[i], pu->colors[i], PERFORM); + test_node = mis[i]; + DBG((dbgphi, 1, "\t\t Testing %n\n", test_node)); + confl_node = pu_color_irn(pu, test_node, col, &ob_undo); + + if (confl_node == CHANGE_SAVE) { + if (!pset_find_ptr(free_nodes, test_node)) + pu_pin_node(pu, test_node); + obstack_free(&ob_undo, obstack_finish(&ob_undo)); + continue; } else { - DBG((dbgphi, 1, "\t\tConflict due to a live-in: %n\n", pu->members[i])); + int i; + ir_node *undo_node, **undo_nodes; + + obstack_ptr_grow(&ob_undo, NULL); + undo_nodes = obstack_finish(&ob_undo); + for (i = 0, undo_node = undo_nodes[0]; undo_node; undo_node = undo_nodes[++i]) { + node_stat_t *ns = pu_find_node(pu, undo_node); + ns->color = ns->undo_color; + } + obstack_free(&ob_undo, undo_nodes); + + if (is_conflicting_node(confl_node)) { + if (pu_is_node_pinned(pu, confl_node)) + pu_add_conflict(pu, confl_node, test_node); + if (pset_find_ptr(pinned_global, confl_node)) + pu_remove_node(pu, test_node); + } } + + /* shortcut: color not possible for phi node (phi comes first) ==> exit */ + if (i == 0) + goto ret; } -} + obstack_free(&ob_mis, mis); + } +ret: + obstack_free(&ob_undo, NULL); + obstack_free(&ob_mis, NULL); + return mis_size; +} /** - * Tries to re-allocate colors of this phi-class, to achieve a lower number of - * copies placed during phi destruction. Optimized version. Works only for - * phi-classes/phi-units with exactly 1 phi node, which is the case for approx. - * 80%. + * Tries to re-allocate colors of nodes in this phi unit, to achieve a lower + * number of copy instructions placed during phi destruction. Optimized version. + * Works only for phi-classes/phi-units with exactly 1 phi node, which is the + * case for approximately 80% of all phi units. */ -static void coalesce_1_phi(phi_unit_t *pu) { - int *b_colors, b_size, b_changes, b_color; - int i, col; +static void pu_coalesce_1_phi(phi_unit_t *pu) { + int size, col, b_size, b_color; + set *b_changes; /* init best search result */ - b_colors = malloc(pu->count * sizeof(*b_colors)); - for (i = 0; i < pu->count; ++i) - b_colors[i] = NO_COLOR; + b_changes = NULL; b_size = 0; - b_changes = 0; b_color = NO_COLOR; /* find optimum of all colors */ for (col = MAX_COLORS-1; col >= 0; --col) { DBG((dbgphi, 1, "\tTrying color %d\n", col)); - try_colors(pu, col, b_size, b_changes); + size = pu_try_color(pu, col, b_size); /* did we find a better max ind. set? */ - if (pu->size > b_size || (pu->size == b_size && pu->changes < b_changes)) { - b_size = pu->size; - b_changes = pu->changes; + if (size > b_size) { + DBG((dbgphi, 1, "\t!! Better size: %d\n", size)); + if (b_changes) + del_set(b_changes); + b_changes = pu->changed_nodes; + b_size = size; b_color = col; - memcpy(b_colors, pu->colors, pu->count * sizeof(*b_colors)); - DBG((dbgphi, 1, "\t\tBetter! Size: %d Changes: %d\n", b_size, b_changes)); + } else { + del_set(pu->changed_nodes); } - /* shortcut: if all members can be colored we are content and doubt that - * reducing b_changes justifies all the further trying. */ - if (b_size == pu->count) + /* reset the phi unit to original state for next color */ + pu->changed_nodes = new_set(set_cmp_node_stat_t, INITIAL_SLOTS_CHANGED_NODES); + pu->conflict_count = pu->conflict_count_org; + + /* shortcut: if all members can be colored we are (very) content */ + if (b_size == pu->node_count) break; } /* now apply the found optimum */ - DBG((dbgphi, 1, "\tBest color: %d Copies: %d/%d Changes: %d\n", b_color, pu->count-b_size, pu->count, b_changes)); - pu->size = b_size; - pu->changes = b_changes; - memcpy(pu->colors, b_colors, pu->count * sizeof(*b_colors)); - set_colors(pu); - - free(b_colors); + if (b_changes) { + node_stat_t *ns; + DBG((dbgphi, 1, "\tBest color: %d Copies: %d/%d\n", b_color, pu->node_count-b_size, pu->node_count)); + for (ns = set_first(b_changes); ns; ns = set_next(b_changes)) + set_irn_color(ns->irn, ns->color); + free(b_changes); + } else { + DBG((dbgphi, 1, "\tBest color: none\n")); + } } /** - * Tries to re-allocate colors of this phi-class, to achieve a lower number of - * copies placed during phi destruction. General purpose version. + * Tries to re-allocate colors of nodes in this phi unit, to achieve a lower + * number of copy instructions placed during phi destruction. + * General purpose version. */ -static void coalesce_n_phi(phi_unit_t *pu) { +static void pu_coalesce_n_phi(phi_unit_t *pu) { DBG((dbgphi, 1, "\n")); /* TODO */ } /** - * Prepare a phi class for further processing as a phi unit. + * Prepares a phi class for further processing as a phi unit. + * @param pc The phi class to prepare. + * @return A so called phi unit containing some prepared informations + * needed by the following coalescing phase. */ -static phi_unit_t *new_phi_unit(pset *pc) { +static phi_unit_t *new_pu(pset *pc) { phi_unit_t *pu; ir_node *n, *phi = NULL; - assert(pset_count(pc) <= MAX_PHI_CLS_SIZE && "Phi class too large!"); - - pu = malloc(sizeof(*pu)); - pu->phi_count = 0; + /* get the phi count of this class */ + pu = calloc(1, sizeof(*pu)); for (n = pset_first(pc); n; n = pset_next(pc)) if (is_Phi(n)) { phi = n; @@ -295,61 +511,40 @@ static phi_unit_t *new_phi_unit(pset *pc) { } if (pu->phi_count == 1) { - ir_node **tmp, *phi_block; - int i, max; + ir_node **tmp; + int i, o; struct obstack ob; obstack_init(&ob); /* build member set not containing phi interferers */ DBG((dbgphi, 1, "Phi-1 class:\n")); - pu->count = 1; /*for the phi*/ + pu->node_count = 1; /*for the phi*/ for (n = pset_first(pc); n; n = pset_next(pc)) { - if (!is_Phi(n) && !values_interfere(phi, n)) { + if (is_Phi(n)) + continue; + if (!phi_ops_interfere(phi, n)) { DBG((dbgphi, 1, "\tAdding to members: %n\n", n)); obstack_ptr_grow(&ob, n); - pu->count++; + pu->node_count++; } else { DBG((dbgphi, 1, "\tPhi interferer: %n\n", n)); pset_insert_ptr(free_nodes, n); } } tmp = obstack_finish(&ob); - pu->members = malloc(pu->count * sizeof(*pu->members)); - pu->members[0] = phi; - memcpy(&pu->members[1], tmp, (pu->count-1) * sizeof(*tmp)); - - /* init of colors array */ - pu->colors = malloc(pu->count * sizeof(*pu->colors)); - - /* live-in analysis */ - /* HINT: It is possible that a node occurs twice as arg of a phi, - * one time being live-in, and another time not being live-in. - */ - pu->is_live_in = calloc(pu->count, sizeof(*pu->is_live_in)); - phi_block = get_nodes_block(phi); - for (i = 0, max = get_irn_arity(phi); i < max; ++i) { - int midx, o; - ir_node *arg, *block_ith_pred; - - arg = get_irn_n(phi, i); - block_ith_pred = get_nodes_block(get_irn_n(phi_block, i)); - - /* find the arg in the members array */ - midx = -1; - for (o = 0; o < pu->count; ++o) - if (pu->members[o] == arg) { - midx = o; - break; - } - if (midx == -1) - continue; + pu->nodes = malloc(pu->node_count * sizeof(*pu->nodes)); + pu->nodes[0] = phi; + memcpy(&pu->nodes[1], tmp, (pu->node_count-1) * sizeof(*tmp)); - if (is_live_in(block_ith_pred, arg)) { - pu->is_live_in[midx] |= 1; - DBG((dbgphi, 1, "\t%n is live-in in %n\n", arg, block_ith_pred)); - } - } + /* init conlict graph to life range interference */ + for (i = 0; i < pu->node_count; ++i) + for (o = i+1; o < pu->node_count; ++o) + if (phi_ops_interfere(pu->nodes[i], pu->nodes[o])) + pu_add_conflict(pu, pu->nodes[i], pu->nodes[o]); + pu->conflict_count_org = pu->conflict_count; + + pu->changed_nodes = new_set(set_cmp_node_stat_t, INITIAL_SLOTS_CHANGED_NODES); obstack_free(&ob, NULL); } else { @@ -361,15 +556,16 @@ static phi_unit_t *new_phi_unit(pset *pc) { return pu; } + /** * Deletes a phi unit */ -static void free_phi_unit(phi_unit_t *pu) { - DBG((dbgphi, 1, "\n")); +static void free_pu(phi_unit_t *pu) { if (pu->phi_count == 1) { - free(pu->members); - free(pu->colors); - free(pu->is_live_in); + free(pu->nodes); + free(pu->changed_nodes); + if (pu->conflicts) + free(pu->conflicts); } else { /* TODO */ } @@ -380,24 +576,24 @@ static void free_phi_unit(phi_unit_t *pu) { void be_phi_coalesce(pset *all_phi_classes) { pset *pc; - pinned_nodes = pset_new_ptr(256); - free_nodes = pset_new_ptr(64); + pinned_global = pset_new_ptr(INITIAL_SLOTS_PINNED_GLOBAL); + free_nodes = pset_new_ptr(INITIAL_SLOTS_FREE_NODES); for (pc = pset_first(all_phi_classes); pc; pc = pset_next(all_phi_classes)) { - phi_unit_t *pu = new_phi_unit(pc); + phi_unit_t *pu = new_pu(pc); if (pu->phi_count == 1) - coalesce_1_phi(pu); + pu_coalesce_1_phi(pu); else - coalesce_n_phi(pu); - free_phi_unit(pu); + pu_coalesce_n_phi(pu); + free_pu(pu); } del_pset(free_nodes); - del_pset(pinned_nodes); + del_pset(pinned_global); } void be_phi_coal_init(void) { - dbgphi = firm_dbg_register("Phi coalescing"); + dbgphi = firm_dbg_register("ir.be.phicoal"); firm_dbg_set_mask(dbgphi, DEBUG_LVL); }