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"
41 static FILE *my_open(const be_chordal_env_t *env, const char *prefix, const char *suffix)
48 n = strlen(env->birg->main_env->cup_name);
49 tu_name = XMALLOCN(char, n + 1);
50 strcpy(tu_name, env->birg->main_env->cup_name);
51 for (i = 0; i < n; ++i)
52 if (tu_name[i] == '.')
55 ir_snprintf(buf, sizeof(buf), "%s%s_%F_%s%s", prefix, tu_name, env->irg, env->cls->name, suffix);
57 result = fopen(buf, "wt");
59 panic("Couldn't open '%s' for writing.", buf);
66 static void insert_into_reverse_peo(ir_node *block, void *data) {
72 sched_foreach(block, irn) {
75 if (get_irn_mode(irn) == mode_T) {
76 const ir_edge_t *edge;
78 foreach_out_edge(irn, edge) {
79 ir_node *proj = get_edge_src_irn(edge);
80 if (!arch_irn_consider_in_reg_alloc(pbqp_co->cls, proj))
83 // get related pbqp_node and insert into reverse peo
84 // node = pmap_find(pbqp_co->map,proj)->value;
85 assert(node && "No corresponding PBQP-Node found!");
86 plist_insert_back(pbqp_co->rpeo, get_node(pbqp_co->pbqp, get_irn_idx(proj)));
89 if (!arch_irn_consider_in_reg_alloc(pbqp_co->cls, irn))
92 // get related pbqp_node and insert into reverse peo
93 // node = pmap_find(pbqp_co->map,irn)->value;
94 assert(node && "No corresponding PBQP-Node found!");
95 plist_insert_back(pbqp_co->rpeo, get_node(pbqp_co->pbqp, get_irn_idx(irn)));
100 static int co_solve_heuristic_pbqp(copy_opt_t *co) {
101 void *nodes_it = be_ifg_nodes_iter_alloca(co->cenv->ifg);
102 void *neigh_it = be_ifg_neighbours_iter_alloca(co->cenv->ifg);
104 ir_node *if_neighb_node;
108 unsigned number_registers = co->cls->n_regs;
109 unsigned number_nodes = get_irg_last_idx(co->irg);
110 unsigned nodeIdx = 0;
112 // // count nodes in ifg
113 // be_ifg_foreach_node(co->cenv->ifg, nodes_it, ifg_node) {
117 // create and initialize data structure for pbqp copy min. optimization
118 pbqp_co.cls = co->cls;
119 pbqp_co.rpeo = plist_new();;
120 pbqp_co.map = pmap_create_ex(number_nodes);
121 pbqp_co.pbqp = alloc_pbqp(number_nodes);
122 pbqp_co.ignore_reg = bitset_malloc(number_registers);
124 // get ignored registers
125 be_put_ignore_regs(co->cenv->birg, co->cls, pbqp_co.ignore_reg);
127 // add costs vector to nodes
129 be_ifg_foreach_node(co->cenv->ifg, nodes_it, ifg_node) {
130 // create costs vector
131 struct vector *costs_vector = vector_alloc(pbqp_co.pbqp, number_registers);
135 for(cnt = 0; cnt < costs_vector->len; cnt++) {
136 if (bitset_is_set(pbqp_co.ignore_reg,cnt)) {
137 vector_set(costs_vector, cnt, INF_COSTS);
140 if (!arch_reg_out_is_allocatable(ifg_node, arch_register_for_index(co->cls, cnt)))
142 vector_set(costs_vector, cnt, INF_COSTS);
145 vector_set(costs_vector, cnt, 0);
148 #if KAPS_ENABLE_VECTOR_NAMES
150 vector_set_description(costs_vector, cnt, arch_register_for_index(co->cls, cnt)->name);
154 // add costs vector to node
155 add_node_costs(pbqp_co.pbqp, get_irn_idx(ifg_node), costs_vector);
157 // insert ir_node and pbqp_node into map
158 pmap_insert(pbqp_co.map, ifg_node, get_node(pbqp_co.pbqp, get_irn_idx(ifg_node)));
160 // // increment nodeIndex
164 // add pbqp edges and cost matrix
165 be_ifg_foreach_node(co->cenv->ifg, nodes_it, ifg_node) {
166 // pbqp_node *src_node = pmap_find(pbqp_co.map,ifg_node)->value;
167 // unsigned int srcNodeIdx = src_node->index;
169 // add costs matrix between nodes (interference edge)
170 be_ifg_foreach_neighbour(co->cenv->ifg, neigh_it, ifg_node, if_neighb_node) {
171 // pbqp_node *trg_node = pmap_find(pbqp_co.map,if_neighb_node)->value;
172 if(get_edge(pbqp_co.pbqp,get_irn_idx(ifg_node), get_irn_idx(if_neighb_node)) == NULL) {
173 // create costs matrix
174 struct pbqp_matrix *matrix = pbqp_matrix_alloc(pbqp_co.pbqp, number_registers, number_registers);
178 for(row = 0; row < number_registers; row++) {
179 for(col = 0; col < number_registers; col++) {
181 pbqp_matrix_set(matrix, row, col, INF_COSTS);
184 pbqp_matrix_set(matrix, row, col, 0);
189 // add costs matrix to interference edge
190 add_edge_costs(pbqp_co.pbqp, get_irn_idx(ifg_node), get_irn_idx(if_neighb_node) , matrix);
194 // add costs matrix between nodes (affinity edge)
195 affinity_node_t *aff_node = get_affinity_info(co, ifg_node);
196 neighb_t *aff_neighb_node;
197 if(aff_node != NULL) {
198 co_gs_foreach_neighb(aff_node, aff_neighb_node) {
199 pmap_entry *ptr_pbqp_node = pmap_find(pbqp_co.map,aff_neighb_node->irn);
201 if(ptr_pbqp_node == NULL) {
204 // pbqp_node *trg_node = ptr_pbqp_node->value;
205 if(get_edge(pbqp_co.pbqp, get_irn_idx(ifg_node), get_irn_idx(if_neighb_node)) == NULL) {
206 // create costs matrix
207 struct pbqp_matrix *matrix = pbqp_matrix_alloc(pbqp_co.pbqp, number_registers, number_registers);
211 for(row = 0; row < number_registers; row++) {
212 for(col = 0; col < number_registers; col++) {
214 pbqp_matrix_set(matrix, row, col, 0);
217 pbqp_matrix_set(matrix, row, col, 2);
222 // add costs matrix to interference edge
223 add_edge_costs(pbqp_co.pbqp, get_irn_idx(ifg_node), get_irn_idx(if_neighb_node) , matrix);
229 // create reverse perfect elimination order
230 assure_doms(co->irg);
231 dom_tree_walk_irg(co->irg, insert_into_reverse_peo, NULL, &pbqp_co);
234 // dump graph before solving pbqp
235 FILE *file_before = my_open(co->cenv, "", "-before.html");
236 set_dumpfile(pbqp_co.pbqp, file_before);
237 pbqp_dump_input(pbqp_co.pbqp);
241 // solve pbqp problem
242 solve_pbqp_heuristical_co(pbqp_co.pbqp, pbqp_co.rpeo);
243 num solution = get_solution(pbqp_co.pbqp);
245 assert(solution != INF_COSTS && "No PBQP solution found");
249 // dump graph after solving pbqp
250 FILE *file_after = my_open(co->cenv, "", "-after.html");
251 set_dumpfile(pbqp_co.pbqp, file_after);
252 pbqp_dump_input(pbqp_co.pbqp);
256 be_ifg_foreach_node(co->cenv->ifg, nodes_it, ifg_node) {
257 // pbqp_node *node = pmap_find(pbqp_co.map,ifg_node)->value;
258 num index = get_node_solution(pbqp_co.pbqp, get_irn_idx(ifg_node));
259 const arch_register_t *reg = arch_register_for_index(co->cls, index);
260 arch_set_irn_register(ifg_node, reg);
263 // free pbqp resources
268 bitset_free(pbqp_co.ignore_reg);
269 pmap_destroy(pbqp_co.map);
270 plist_free(pbqp_co.rpeo);
271 free_pbqp(pbqp_co.pbqp);
276 void be_init_copypbqp(void)
278 static co_algo_info copyheur = {
279 co_solve_heuristic_pbqp, 0
282 be_register_copyopt("pbqp", ©heur);
285 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_copypbqp);