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"
40 static FILE *my_open(const be_chordal_env_t *env, const char *prefix, const char *suffix)
47 n = strlen(env->birg->main_env->cup_name);
48 tu_name = XMALLOCN(char, n + 1);
49 strcpy(tu_name, env->birg->main_env->cup_name);
50 for (i = 0; i < n; ++i)
51 if (tu_name[i] == '.')
54 ir_snprintf(buf, sizeof(buf), "%s%s_%F_%s%s", prefix, tu_name, env->irg, env->cls->name, suffix);
56 result = fopen(buf, "wt");
58 panic("Couldn't open '%s' for writing.", buf);
65 static void insert_into_reverse_peo(ir_node *block, void *data) {
66 pqueue_t *queue = new_pqueue();
67 pqueue_t *restrictedNodesQueue = new_pqueue();
68 pbqp_co_t *pbqp_co = data;
71 sched_foreach(block, irn) {
72 if (get_irn_mode(irn) == mode_T) {
73 const ir_edge_t *edge;
75 foreach_out_edge(irn, edge) {
76 ir_node *proj = get_edge_src_irn(edge);
77 if (!arch_irn_consider_in_reg_alloc(pbqp_co->cls, proj))
80 // insert proj node into priority queue (descending by their degree in ifg)
81 if(bitset_is_set(pbqp_co->restricted_nodes, get_irn_idx(proj))) {
82 pqueue_put(restrictedNodesQueue,proj, be_ifg_degree(pbqp_co->ifg,proj));
85 pqueue_put(queue,proj, be_ifg_degree(pbqp_co->ifg,proj));
89 /* first insert all restricted nodes */
90 while(!pqueue_empty(restrictedNodesQueue)) {
91 plist_insert_back(pbqp_co->rpeo, get_node(pbqp_co->pbqp, get_irn_idx(pqueue_pop_front(restrictedNodesQueue))));
94 /* insert proj nodes into reverse perfect elimination order (descending by their degree in ifg) */
95 while(!pqueue_empty(queue)) {
96 plist_insert_back(pbqp_co->rpeo, get_node(pbqp_co->pbqp, get_irn_idx(pqueue_pop_front(queue))));
100 if (!arch_irn_consider_in_reg_alloc(pbqp_co->cls, irn))
103 /* insert pbqp node into reverse peo */
104 plist_insert_back(pbqp_co->rpeo, get_node(pbqp_co->pbqp, get_irn_idx(irn)));
108 /* free priority queues */
110 del_pqueue(restrictedNodesQueue);
113 static int co_solve_heuristic_pbqp(copy_opt_t *co) {
114 void *nodes_it = be_ifg_nodes_iter_alloca(co->cenv->ifg);
115 void *neigh_it = be_ifg_neighbours_iter_alloca(co->cenv->ifg);
116 unsigned number_registers = co->cls->n_regs;
117 unsigned number_nodes = get_irg_last_idx(co->irg);
118 ir_timer_t *t_ra_copymin_pbqp_create = ir_timer_register("be_co_pbqp_create", "copy minimization pbqp create");
119 ir_timer_t *t_ra_copymin_pbqp_solve = ir_timer_register("be_co_pbqp_solve", "copy minimization pbqp solve");
121 ir_node *if_neighb_node;
126 printf("==>> START PBQP TIMING on IRG %s (%s) <<==\n", get_entity_name(get_irg_entity(co->irg)), arch_register_class_name(co->cls));
130 ir_timer_reset_and_start(t_ra_copymin_pbqp_create);
132 /* create and initialize data structure for pbqp copy minimization optimization */
133 pbqp_co.cls = co->cls;
134 pbqp_co.rpeo = plist_new();
135 pbqp_co.pbqp = alloc_pbqp(number_nodes);
136 pbqp_co.ignore_reg = bitset_malloc(number_registers);
137 pbqp_co.restricted_nodes = bitset_malloc(number_nodes);
138 pbqp_co.ifg = co->cenv->ifg;
140 /* no node is restricted at the beginning */
141 bitset_clear_all(pbqp_co.restricted_nodes);
143 /* get ignored registers */
144 be_put_ignore_regs(co->cenv->birg, co->cls, pbqp_co.ignore_reg);
146 /* add costs vector to nodes */
147 be_ifg_foreach_node(co->cenv->ifg, nodes_it, ifg_node) {
148 int cntFreeChoosableRegs = 0;
150 /* create costs vector */
151 struct vector *costs_vector = vector_alloc(pbqp_co.pbqp, number_registers);
155 for(cnt = 0; cnt < costs_vector->len; cnt++) {
156 if (bitset_is_set(pbqp_co.ignore_reg,cnt)) {
157 vector_set(costs_vector, cnt, INF_COSTS);
160 if (!arch_reg_out_is_allocatable(ifg_node, arch_register_for_index(co->cls, cnt)))
162 vector_set(costs_vector, cnt, INF_COSTS);
165 vector_set(costs_vector, cnt, 0);
166 cntFreeChoosableRegs++;
170 #if KAPS_ENABLE_VECTOR_NAMES
171 /* add description */
172 vector_set_description(costs_vector, cnt, arch_register_for_index(co->cls, cnt)->name);
176 /* add costs vector to node */
177 add_node_costs(pbqp_co.pbqp, get_irn_idx(ifg_node), costs_vector);
179 if(cntFreeChoosableRegs <= 4) {
180 /* node is restricted */
181 bitset_set(pbqp_co.restricted_nodes, get_irn_idx(ifg_node));
185 /* create costs matrix for interference edges */
186 struct pbqp_matrix *ife_matrix = pbqp_matrix_alloc(pbqp_co.pbqp, number_registers, number_registers);
188 for(row = 0; row < number_registers; row++) {
189 pbqp_matrix_set(ife_matrix, row, row, INF_COSTS);
192 /* create costs matrix for affinity edges */
193 struct pbqp_matrix *afe_matrix = pbqp_matrix_alloc(pbqp_co.pbqp, number_registers, number_registers);
195 for(row = 0; row < number_registers; row++) {
196 for(col = 0; col < number_registers; col++) {
198 pbqp_matrix_set(afe_matrix, row, col, 0);
201 pbqp_matrix_set(afe_matrix, row, col, 2);
206 /* add pbqp edges and cost matrix */
207 be_ifg_foreach_node(co->cenv->ifg, nodes_it, ifg_node) {
208 /* add costs matrix between nodes (interference edge) */
209 be_ifg_foreach_neighbour(co->cenv->ifg, neigh_it, ifg_node, if_neighb_node) {
210 if(get_edge(pbqp_co.pbqp,get_irn_idx(ifg_node), get_irn_idx(if_neighb_node)) == NULL) {
212 struct pbqp_matrix *matrix = pbqp_matrix_copy(pbqp_co.pbqp, ife_matrix);
214 /* add costs matrix to interference edge */
215 add_edge_costs(pbqp_co.pbqp, get_irn_idx(ifg_node), get_irn_idx(if_neighb_node) , matrix);
220 /* add costs matrix between nodes (affinity edge) */
221 affinity_node_t *aff_node = get_affinity_info(co, ifg_node);
222 neighb_t *aff_neighb_node;
223 if(aff_node != NULL) {
224 co_gs_foreach_neighb(aff_node, aff_neighb_node) {
225 /* ignore Unknowns */
226 if(get_node(pbqp_co.pbqp, get_irn_idx(aff_neighb_node->irn)) == NULL)
229 if(get_edge(pbqp_co.pbqp, get_irn_idx(aff_node->irn), get_irn_idx(aff_neighb_node->irn)) == NULL) {
231 struct pbqp_matrix *matrix = pbqp_matrix_copy(pbqp_co.pbqp, afe_matrix);
233 /* add costs matrix to affinity edge */
234 add_edge_costs(pbqp_co.pbqp, get_irn_idx(aff_node->irn), get_irn_idx(aff_neighb_node->irn) , matrix);
240 /* create reverse perfect elimination order */
241 assure_doms(co->irg);
242 dom_tree_walk_irg(co->irg, insert_into_reverse_peo, NULL, &pbqp_co);
245 ir_timer_stop(t_ra_copymin_pbqp_create);
248 // dump graph before solving pbqp
249 FILE *file = my_open(co->cenv, "", "-pbqp_copymin.html");
250 set_dumpfile(pbqp_co.pbqp, file);
254 ir_timer_reset_and_start(t_ra_copymin_pbqp_solve);
256 /* solve pbqp problem using a reverse perfect elimination order */
257 solve_pbqp_heuristical_co(pbqp_co.pbqp, pbqp_co.rpeo);
258 num solution = get_solution(pbqp_co.pbqp);
261 ir_timer_stop(t_ra_copymin_pbqp_solve);
264 printf("==>> PBQP STATISTIC on IRG %s (%s) <<==\n", get_entity_name(get_irg_entity(co->irg)), arch_register_class_name(co->cls));
265 printf("Number of Nodes: %d\n", number_nodes);
266 printf("Number of independent edges : %d\n", pbqp_co.pbqp->num_edges);
267 printf("Number of trivial solved nodes: %d\n", pbqp_co.pbqp->num_r0);
268 printf("Number of R1 reductions : %d\n", pbqp_co.pbqp->num_r1);
269 printf("Number of R2 reductions : %d\n", pbqp_co.pbqp->num_r2);
270 printf("Number of RN reductions : %d\n", pbqp_co.pbqp->num_rn);
274 printf("%-20s: %8.3lf msec\n" , ir_timer_get_description(t_ra_copymin_pbqp_create), (double)ir_timer_elapsed_usec(t_ra_copymin_pbqp_create) / 1000.0);
275 printf("%-20s: %8.3lf msec\n" , ir_timer_get_description(t_ra_copymin_pbqp_solve), (double)ir_timer_elapsed_usec(t_ra_copymin_pbqp_solve) / 1000.0);
276 printf("==>> END PBQP TIMING on IRG %s (%s) <<==\n", get_entity_name(get_irg_entity(co->irg)), arch_register_class_name(co->cls));
279 assert(solution != INF_COSTS && "No PBQP solution found");
282 be_ifg_foreach_node(co->cenv->ifg, nodes_it, ifg_node) {
283 num index = get_node_solution(pbqp_co.pbqp, get_irn_idx(ifg_node));
284 const arch_register_t *reg = arch_register_for_index(co->cls, index);
285 arch_set_irn_register(ifg_node, reg);
288 /* free allocated memory */
292 bitset_free(pbqp_co.ignore_reg);
293 bitset_free(pbqp_co.restricted_nodes);
294 plist_free(pbqp_co.rpeo);
295 free_pbqp(pbqp_co.pbqp);
300 void be_init_copypbqp(void)
302 static co_algo_info copyheur = {
303 co_solve_heuristic_pbqp, 0
306 be_register_copyopt("pbqp", ©heur);
309 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_copypbqp);