4 * Created on: Aug 28, 2009
11 #include "becopypbqp.h"
17 #include "html_dumper.h"
18 #include "heuristical.h"
19 #include "pbqp_node_t.h"
21 #include "becopyopt_t.h"
25 #include "irprintf_t.h"
39 static FILE *my_open(const be_chordal_env_t *env, const char *prefix, const char *suffix)
46 n = strlen(env->birg->main_env->cup_name);
47 tu_name = XMALLOCN(char, n + 1);
48 strcpy(tu_name, env->birg->main_env->cup_name);
49 for (i = 0; i < n; ++i)
50 if (tu_name[i] == '.')
53 ir_snprintf(buf, sizeof(buf), "%s%s_%F_%s%s", prefix, tu_name, env->irg, env->cls->name, suffix);
55 result = fopen(buf, "wt");
57 panic("Couldn't open '%s' for writing.", buf);
64 static void insert_into_reverse_peo(ir_node *block, void *data) {
65 pqueue_t *queue = new_pqueue();
66 pqueue_t *constatQueue = new_pqueue();
67 pbqp_co_t *pbqp_co = data;
70 sched_foreach(block, irn) {
73 if (get_irn_mode(irn) == mode_T) {
74 const ir_edge_t *edge;
76 foreach_out_edge(irn, edge) {
77 ir_node *proj = get_edge_src_irn(edge);
78 if (!arch_irn_consider_in_reg_alloc(pbqp_co->cls, proj))
81 // get related pbqp_node and insert into reverse peo
82 assert(node && "No corresponding PBQP-Node found!");
84 // insert proj node into priority queue (descending by their degree in ifg)
85 if(bitset_is_set(pbqp_co->restricted_nodes, get_irn_idx(proj))) {
86 pqueue_put(constatQueue,proj, be_ifg_degree(pbqp_co->ifg,proj));
89 pqueue_put(queue,proj, be_ifg_degree(pbqp_co->ifg,proj));
93 /* first insert all restricted nodes */
94 while(!pqueue_empty(constatQueue)) {
95 plist_insert_back(pbqp_co->rpeo, get_node(pbqp_co->pbqp, get_irn_idx(pqueue_pop_front(constatQueue))));
98 /* insert proj nodes into reverse perfect elimination order (descending by their degree in ifg) */
99 while(!pqueue_empty(queue)) {
100 plist_insert_back(pbqp_co->rpeo, get_node(pbqp_co->pbqp, get_irn_idx(pqueue_pop_front(queue))));
104 if (!arch_irn_consider_in_reg_alloc(pbqp_co->cls, irn))
107 /* get related pbqp_node and insert into reverse peo */
108 assert(node && "No corresponding PBQP-Node found!");
109 plist_insert_back(pbqp_co->rpeo, get_node(pbqp_co->pbqp, get_irn_idx(irn)));
113 /* free priority queues */
115 del_pqueue(constatQueue);
118 static int co_solve_heuristic_pbqp(copy_opt_t *co) {
119 void *nodes_it = be_ifg_nodes_iter_alloca(co->cenv->ifg);
120 void *neigh_it = be_ifg_neighbours_iter_alloca(co->cenv->ifg);
122 ir_node *if_neighb_node;
126 unsigned number_registers = co->cls->n_regs;
127 unsigned number_nodes = get_irg_last_idx(co->irg);
129 /* create and initialize data structure for pbqp copy minimization optimization */
130 pbqp_co.cls = co->cls;
131 pbqp_co.rpeo = plist_new();;
132 pbqp_co.map = pmap_create_ex(number_nodes);
133 pbqp_co.pbqp = alloc_pbqp(number_nodes);
134 pbqp_co.ignore_reg = bitset_malloc(number_registers);
135 pbqp_co.restricted_nodes = bitset_malloc(number_nodes);
136 pbqp_co.ifg = co->cenv->ifg;
138 /* get ignored registers */
139 be_put_ignore_regs(co->cenv->birg, co->cls, pbqp_co.ignore_reg);
141 /* add costs vector to nodes */
142 be_ifg_foreach_node(co->cenv->ifg, nodes_it, ifg_node) {
143 int cntFreeChoosableRegs = 0;
145 /* create costs vector */
146 struct vector *costs_vector = vector_alloc(pbqp_co.pbqp, number_registers);
150 for(cnt = 0; cnt < costs_vector->len; cnt++) {
151 if (bitset_is_set(pbqp_co.ignore_reg,cnt)) {
152 vector_set(costs_vector, cnt, INF_COSTS);
155 if (!arch_reg_out_is_allocatable(ifg_node, arch_register_for_index(co->cls, cnt)))
157 vector_set(costs_vector, cnt, INF_COSTS);
160 vector_set(costs_vector, cnt, 0);
161 cntFreeChoosableRegs++;
164 #if KAPS_ENABLE_VECTOR_NAMES
165 /* add description */
166 vector_set_description(costs_vector, cnt, arch_register_for_index(co->cls, cnt)->name);
170 /* add costs vector to node */
171 add_node_costs(pbqp_co.pbqp, get_irn_idx(ifg_node), costs_vector);
173 /* insert ir_node and pbqp_node into map */
174 pmap_insert(pbqp_co.map, ifg_node, get_node(pbqp_co.pbqp, get_irn_idx(ifg_node)));
176 if(cntFreeChoosableRegs <= 4) {
177 /* node is restricted */
178 bitset_set(pbqp_co.restricted_nodes, get_irn_idx(ifg_node));
182 /* node is not restricted */
183 bitset_clear(pbqp_co.restricted_nodes, get_irn_idx(ifg_node));
188 /* add pbqp edges and cost matrix */
189 be_ifg_foreach_node(co->cenv->ifg, nodes_it, ifg_node) {
190 /* add costs matrix between nodes (interference edge) */
191 be_ifg_foreach_neighbour(co->cenv->ifg, neigh_it, ifg_node, if_neighb_node) {
192 if(get_edge(pbqp_co.pbqp,get_irn_idx(ifg_node), get_irn_idx(if_neighb_node)) == NULL) {
193 /* create costs matrix */
194 struct pbqp_matrix *matrix = pbqp_matrix_alloc(pbqp_co.pbqp, number_registers, number_registers);
198 for(row = 0; row < number_registers; row++) {
199 for(col = 0; col < number_registers; col++) {
201 pbqp_matrix_set(matrix, row, col, INF_COSTS);
204 pbqp_matrix_set(matrix, row, col, 0);
209 /* add costs matrix to interference edge */
210 add_edge_costs(pbqp_co.pbqp, get_irn_idx(ifg_node), get_irn_idx(if_neighb_node) , matrix);
214 /* add costs matrix between nodes (affinity edge) */
215 affinity_node_t *aff_node = get_affinity_info(co, ifg_node);
216 neighb_t *aff_neighb_node;
217 if(aff_node != NULL) {
218 co_gs_foreach_neighb(aff_node, aff_neighb_node) {
219 pmap_entry *ptr_pbqp_node = pmap_find(pbqp_co.map,aff_neighb_node->irn);
221 /* ignore Unknowns */
222 if(ptr_pbqp_node == NULL) {
226 if(get_edge(pbqp_co.pbqp, get_irn_idx(aff_node->irn), get_irn_idx(aff_neighb_node->irn)) == NULL) {
227 /* create costs matrix */
228 struct pbqp_matrix *matrix = pbqp_matrix_alloc(pbqp_co.pbqp, number_registers, number_registers);
232 for(row = 0; row < number_registers; row++) {
233 for(col = 0; col < number_registers; col++) {
235 pbqp_matrix_set(matrix, row, col, 0);
238 pbqp_matrix_set(matrix, row, col, 2);
243 /* add costs matrix to affinity edge */
244 add_edge_costs(pbqp_co.pbqp, get_irn_idx(aff_node->irn), get_irn_idx(aff_neighb_node->irn) , matrix);
250 /* create reverse perfect elimination order */
251 assure_doms(co->irg);
252 dom_tree_walk_irg(co->irg, insert_into_reverse_peo, NULL, &pbqp_co);
255 // dump graph before solving pbqp
256 FILE *file_before = my_open(co->cenv, "", "-before.html");
257 set_dumpfile(pbqp_co.pbqp, file_before);
258 pbqp_dump_input(pbqp_co.pbqp);
262 /* solve pbqp problem using a reverse perfect elimination order */
263 solve_pbqp_heuristical_co(pbqp_co.pbqp, pbqp_co.rpeo);
264 num solution = get_solution(pbqp_co.pbqp);
266 assert(solution != INF_COSTS && "No PBQP solution found");
269 /* dump graph after solving pbqp */
270 FILE *file_after = my_open(co->cenv, "", "-after.html");
271 set_dumpfile(pbqp_co.pbqp, file_after);
272 pbqp_dump_input(pbqp_co.pbqp);
276 be_ifg_foreach_node(co->cenv->ifg, nodes_it, ifg_node) {
277 num index = get_node_solution(pbqp_co.pbqp, get_irn_idx(ifg_node));
278 const arch_register_t *reg = arch_register_for_index(co->cls, index);
279 arch_set_irn_register(ifg_node, reg);
282 /* free pbqp resources */
287 bitset_free(pbqp_co.ignore_reg);
288 pmap_destroy(pbqp_co.map);
289 plist_free(pbqp_co.rpeo);
290 free_pbqp(pbqp_co.pbqp);
295 void be_init_copypbqp(void)
297 static co_algo_info copyheur = {
298 co_solve_heuristic_pbqp, 0
301 be_register_copyopt("pbqp", ©heur);
304 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_copypbqp);