2 * This is the C implementation of the trivial mst algo
3 * originally written in Java by Sebastian Hack.
4 * Performs simple copy minimzation.
6 * @author Christian Wuerdig
13 #endif /* HAVE_CONFIG_H */
18 #include "raw_bitset.h"
19 #include "irphase_t.h"
25 typedef struct _aff_chunk_t {
30 typedef struct _aff_edge_t {
36 /* main coalescing environment*/
37 typedef struct _co_mst_safe_env_t {
38 int n_regs; /**< number of regs in class */
39 int k; /**< number of non-ignore registers in class */
40 bitset_t *ignore_regs; /**< set containing all global ignore registers */
41 ir_phase ph; /**< phase object holding data for nodes */
42 pqueue *chunks; /**< priority queue for chunks */
43 be_ifg_t *ifg; /**< the interference graph */
44 const arch_env_t *aenv; /**< the arch environment */
47 /* stores coalescing related information for a node */
48 typedef struct _co_mst_safe_irn_t {
58 #define get_co_mst_safe_irn(mst_env, irn) (phase_get_or_set_irn_data(&(mst_env)->ph, (irn)))
60 /* compares two affinity edges */
61 static int cmp_aff_edge(const void *a, const void *b) {
62 const aff_edge_t * const *e1 = d1;
63 const aff_edge_t * const *e2 = d2;
65 /* sort in descending order */
66 return (*e1)->weight < (*e2)->weight ? 1 : -1;
70 * In case there is no phase information for irn, initialize it.
72 static void *co_mst_safe_irn_init(ir_phase *ph, ir_node *irn, void *old) {
73 co_mst_safe_irn_t *res = old ? old : phase_alloc(ph, sizeof(res[0]));
74 co_mst_safe_env_t *env = ph->priv;
77 void *neigh_it = be_ifg_neighbours_iter_alloca(env->ifg);
78 const arch_register_req_t *req;
86 res->init_col = arch_register_get_index(arch_get_irn_register(env->aenv, irn));
88 /* set admissible registers */
89 res->adm_colors = bitset_obstack_alloc(phase_obst(ph), env->n_regs);
91 /* Exclude colors not assignable to the irn */
92 req = arch_get_register_req(env->aenv, irn, -1);
93 if (arch_register_req_is(req, limited))
94 rbitset_copy_to_bitset(req->limited, res->adm_colors);
96 /* exclude global ignore registers as well */
97 bitset_andnot(res->adm_colors, env->ignore_regs);
99 /* calculate the number of interfering neigbours */
100 be_ifg_foreach_neighbour(env->ifg, neigh_it, irn, m) {
101 if (! arch_irn_is(env->aenv, m, ignore))
111 * Build chunks of nodes connected by affinity edges.
112 * We start at the heaviest affinity edge.
113 * The chunks of the two edge-defining nodes will be
114 * merged if there are no interference edges from one
115 * chunk to the other.
117 static void build_affinity_chunks(co_mst_safe_env_t *env) {
118 void *nodes_it = be_ifg_nodes_iter_alloca(env->ifg);
119 aff_edge_t **edges = NEW_ARR_F(aff_edge_t *, 0);
122 /* at first we create the affinity edge objects */
123 be_ifg_foreach_node(env->ifg, nodes_it, n) {
124 int n_idx = get_irn_idx(n);
125 co_mst_safe_irn_t *n1;
128 if (arch_irn_is(env->aenv, n, ignore))
131 n1 = get_co_mst_safe_irn(env, n);
132 an = get_affinity_info(co, n);
136 co_gs_foreach_neighb(an, neigh) {
137 ir_node *m = neigh->irn;
138 int m_idx = get_irn_idx(m);
139 co_mst_safe_irn_t *n2;
141 if (arch_irn_is(env->aenv, m, ignore))
144 n2 = get_co_mst_safe_irn(env, m);
146 /* record the edge in only one direction and only to non-ignore nodes */
148 aff_edge_t *edge = phase_alloc(&env->ph, sizeof(*edge));
152 edge->weight = (double)neigh->cost / (double)(1 + n1->int_neigh + n2->int_neigh);
153 ARR_APP1(aff_edge_t *, edges, edge);
159 /* now: sort edges and build the chunks */
160 qsort(edges, ARR_LEN(edges), sizeof(edges[0]), cmp_aff_edge);
161 for (i = 0; i < ARR_LEN(edges); ++i) {
169 * Main driver for mst safe coalescing algorithm.
171 int co_solve_heuristic_mst_safe(copy_opt_t *co)
173 be_ifg_t *ifg = co->cenv->ifg;
174 unsigned n_regs = co->cenv->cls->n_regs;
175 bitset_t *ignore_regs = bitset_alloca(n_regs);
177 co_mst_safe_env_t mst_env;
180 phase_init(&mst_env.ph, "co_mst_safe", co->irg, PHASE_DEFAULT_GROWTH, co_mst_safe_irn_init, &mst_env);
182 k = be_put_ignore_regs(co->cenv->birg, co->cenv->cls, ignore_regs);
185 mst_env.n_regs = n_regs;
187 mst_env.chunks = new_pqueue();
190 /* build affinity chunks */
191 build_affinity_chunks(&mst_env);
193 /* color chunks as long as there are some */
194 while (! pqueue_empty(mst_env.chunks)) {
195 aff_chunk_t *chunk = pqueue_get(mst_env.chunks);
196 color_aff_chunk(&mst_env, chunk);
199 /* free allocated memory */
200 del_pqueue(mst_env.chunks);
201 phase_free(&mst_env.ph);