nsz Git - libfirm/blob - ir/be/bepbqpcoloring.c

   1 /*
   2  * Copyright (C) 1995-2008 University of Karlsruhe.  All right reserved.
   3  *
   4  * This file is part of libFirm.
   5  *
   6  * This file may be distributed and/or modified under the terms of the
   7  * GNU General Public License version 2 as published by the Free Software
   8  * Foundation and appearing in the file LICENSE.GPL included in the
   9  * packaging of this file.
  10  *
  11  * Licensees holding valid libFirm Professional Edition licenses may use
  12  * this file in accordance with the libFirm Commercial License.
  13  * Agreement provided with the Software.
  14  *
  15  * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
  16  * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  17  * PURPOSE.
  18  */
  19
  20 /**
  21  * @file
  22  * @brief       PBQP based register allocation.
  23  * @author      Thomas Bersch
  24  * @date        27.11.2009
  25  * @version     $Id: bechordal.c 26750 2009-11-27 09:37:43Z bersch $
  26  */
  27
  28 /*      miscellaneous includes */
  29 #include "config.h"
  30
  31 #ifdef FIRM_KAPS
  32
  33 #include "debug.h"
  34 #include "error.h"
  35
  36 #include "irdom.h"
  37 #include "iredges_t.h"
  38 #include "irprintf.h"
  39 #include "irgwalk.h"
  40 #include "time.h"
  41
  42 /* libfirm/ir/be includes */
  43 #include "bearch.h"
  44 #include "beirg.h"
  45 #include "besched.h"
  46 #include "bemodule.h"
  47 #include "bechordal_common.h"
  48 #include "bechordal.h"
  49 #include "bechordal_t.h"
  50 #include "beinsn_t.h"
  51 #include "benode.h"
  52 #include "belive.h"
  53 #include "belive_t.h"
  54 #include "beutil.h"
  55 #include "plist.h"
  56 #include "pqueue.h"
  57
  58 /* pbqp includes */
  59 #include "kaps.h"
  60 #include "matrix.h"
  61 #include "vector.h"
  62 #include "vector_t.h"
  63 #include "heuristical.h"
  64 #include "pbqp_t.h"
  65 #include "html_dumper.h"
  66 #include "pbqp_node_t.h"
  67 #include "pbqp_node.h"
  68
  69
  70 typedef struct _be_pbqp_alloc_env_t {
  71         pbqp                                            *pbqp_inst;             /**< PBQP instance for register allocation */
  72         be_irg_t                        *birg;          /**< Back-end IRG session. */
  73         ir_graph                        *irg;           /**< The graph under examination. */
  74         const arch_register_class_t *cls;                       /**< Current processed register class */
  75         be_lv_t                     *lv;
  76         bitset_t                    *ignored_regs;
  77         pbqp_matrix                                     *ife_matrix_dummy;
  78         pbqp_matrix                                     *aff_matrix_dummy;
  79         plist_t                                         *rpeo;
  80         unsigned                                        *restr_nodes;
  81         be_chordal_env_t                        *env;
  82 } be_pbqp_alloc_env_t;
  83
  84
  85 #define is_Reg_Phi(irn)         (is_Phi(irn) && mode_is_data(get_irn_mode(irn)))
  86 #define get_Perm_src(irn)       (get_irn_n(get_Proj_pred(irn), get_Proj_proj(irn)))
  87 #define is_Perm_Proj(irn)       (is_Proj(irn) && be_is_Perm(get_Proj_pred(irn)))
  88
  89 static inline int is_2addr_code(const arch_register_req_t *req)
  90 {
  91         return (req->type & arch_register_req_type_should_be_same) != 0;
  92 }
  93
  94
  95 #if KAPS_DUMP
  96 static FILE *my_open(const be_chordal_env_t *env, const char *prefix, const char *suffix)
  97 {
  98         FILE *result;
  99         char buf[1024];
 100         size_t i, n;
 101         char *tu_name;
 102
 103         n = strlen(env->birg->main_env->cup_name);
 104         tu_name = XMALLOCN(char, n + 1);
 105         strcpy(tu_name, env->birg->main_env->cup_name);
 106         for (i = 0; i < n; ++i)
 107                 if (tu_name[i] == '.')
 108                         tu_name[i] = '_';
 109
 110         ir_snprintf(buf, sizeof(buf), "%s%s_%F_%s%s", prefix, tu_name, env->irg, env->cls->name, suffix);
 111         xfree(tu_name);
 112         result = fopen(buf, "wt");
 113         if(result == NULL) {
 114                 panic("Couldn't open '%s' for writing.", buf);
 115         }
 116
 117         return result;
 118 }
 119 #endif
 120
 121
 122 static unsigned create_pbqp_node(be_pbqp_alloc_env_t *pbqp_alloc_env, ir_node *irn) {
 123         const arch_register_class_t *cls = pbqp_alloc_env->cls;
 124         pbqp     *pbqp_inst              = pbqp_alloc_env->pbqp_inst;
 125         bitset_t *ignored_regs           = pbqp_alloc_env->ignored_regs;
 126         unsigned  colors_n               = arch_register_class_n_regs(cls);
 127         unsigned  cntConstrains          = 0;
 128
 129         /* create costs vector depending on register constrains */
 130         struct vector *costs_vector = vector_alloc(pbqp_inst, colors_n);
 131
 132         /* set costs depending on register constrains */
 133         unsigned idx;
 134         for(idx = 0; idx < colors_n; idx++) {
 135                 if(bitset_is_set(ignored_regs, idx) || !arch_reg_out_is_allocatable(irn, arch_register_for_index(cls, idx))) {
 136                         vector_set(costs_vector, idx, INF_COSTS);
 137                         cntConstrains++;
 138                 }
 139         }
 140
 141         /* add vector to pbqp node */
 142         add_node_costs(pbqp_inst, get_irn_idx(irn), costs_vector);
 143
 144         /* return number of free selectable registers */
 145         return (colors_n - cntConstrains);
 146 }
 147
 148 static void build_graph_walker(ir_node *irn, void *env) {
 149         be_pbqp_alloc_env_t         *pbqp_alloc_env = env;
 150         pbqp                                            *pbqp_inst              = pbqp_alloc_env->pbqp_inst;
 151         const arch_register_class_t *cls            = pbqp_alloc_env->cls;
 152         const arch_register_req_t   *req            = arch_get_register_req_out(irn);
 153         unsigned pos, max;
 154
 155         if (arch_irn_consider_in_reg_alloc(cls, irn))
 156                 return;
 157
 158         if (is_Reg_Phi(irn)) { /* Phis */
 159                 for (pos=0, max=get_irn_arity(irn); pos<max; ++pos) {
 160                         ir_node *arg = get_irn_n(irn, pos);
 161                         //add_edges(co, irn, arg, co->get_costs(co, irn, arg, pos));
 162
 163                         if (!arch_irn_consider_in_reg_alloc(cls, arg))
 164                                 continue;
 165
 166                         /* no edges to itself */
 167                         if(irn == arg) {
 168                                 continue;
 169                         }
 170
 171                         if(get_edge(pbqp_inst, get_irn_idx(irn), get_irn_idx(arg)) == NULL) {
 172                                 /* copy matrix */
 173                                 struct pbqp_matrix *matrix = pbqp_matrix_copy(pbqp_inst, pbqp_alloc_env->aff_matrix_dummy);
 174                                 /* add costs matrix to affinity edge */
 175                                 add_edge_costs(pbqp_inst, get_irn_idx(irn), get_irn_idx(arg) , matrix);
 176                         }
 177                 }
 178         }
 179         else if (is_Perm_Proj(irn)) { /* Perms */
 180                 ir_node *arg = get_Perm_src(irn);
 181                 //add_edges(co, irn, arg, co->get_costs(co, irn, arg, 0));
 182
 183                 if (!arch_irn_consider_in_reg_alloc(cls, arg))
 184                         return;
 185
 186                 if(get_edge(pbqp_inst, get_irn_idx(irn), get_irn_idx(arg)) == NULL) {
 187                         /* copy matrix */
 188                         struct pbqp_matrix *matrix = pbqp_matrix_copy(pbqp_inst, pbqp_alloc_env->aff_matrix_dummy);
 189                         /* add costs matrix to affinity edge */
 190                         add_edge_costs(pbqp_inst, get_irn_idx(irn), get_irn_idx(arg) , matrix);
 191                 }
 192         }
 193         else { /* 2-address code */
 194                 if (is_2addr_code(req)) {
 195                         const unsigned other = req->other_same;
 196                         int i;
 197
 198                         for (i = 0; 1U << i <= other; ++i) {
 199                                 if (other & (1U << i)) {
 200                                         ir_node *other = get_irn_n(skip_Proj(irn), i);
 201 //                                      if (!arch_irn_is_ignore(other)) {
 202                                                 //add_edges(co, irn, other, co->get_costs(co, irn, other, 0));
 203                                                 if (!arch_irn_consider_in_reg_alloc(cls, other))
 204                                                         continue;
 205
 206                                                 /* no edges to itself */
 207                                                 if(irn == other) {
 208                                                         continue;
 209                                                 }
 210
 211                                                 if(get_edge(pbqp_inst, get_irn_idx(irn), get_irn_idx(other)) == NULL) {
 212                                                         /* copy matrix */
 213                                                         struct pbqp_matrix *matrix = pbqp_matrix_copy(pbqp_inst, pbqp_alloc_env->aff_matrix_dummy);
 214                                                         /* add costs matrix to affinity edge */
 215                                                         add_edge_costs(pbqp_inst, get_irn_idx(irn), get_irn_idx(other) , matrix);
 216                                                 }
 217 //                                      }
 218                                 }
 219                         }
 220                 }
 221         }
 222 }
 223
 224 static void create_pbqp_coloring_inst(ir_node *block, void *data) {
 225         be_pbqp_alloc_env_t         *pbqp_alloc_env     = data;
 226         be_lv_t                     *lv                 = pbqp_alloc_env->lv;
 227         const arch_register_class_t *cls                = pbqp_alloc_env->cls;
 228         plist_t                                         *rpeo                           = pbqp_alloc_env->rpeo;
 229         pbqp                                            *pbqp_inst                      = pbqp_alloc_env->pbqp_inst;
 230         unsigned                                        *restr_nodes            = pbqp_alloc_env->restr_nodes;
 231         pbqp_matrix                             *ife_matrix_dummy       = pbqp_alloc_env->ife_matrix_dummy;
 232         pqueue_t                                        *queue                  = new_pqueue();
 233         pqueue_t                                        *restr_nodes_queue      = new_pqueue();
 234         plist_t                                         *temp_list              = plist_new();
 235         ir_node                     *irn;
 236         ir_nodeset_t                 live_nodes;
 237
 238         /* first, determine the pressure */
 239         /* (this is only for compatibility with copymin optimization, it's not needed for pbqp coloring) */
 240         create_borders(block, pbqp_alloc_env->env);
 241
 242         /* calculate living nodes for the first step */
 243         ir_nodeset_init(&live_nodes);
 244         be_liveness_end_of_block(lv, cls, block, &live_nodes);
 245
 246         /* create pbqp nodes, interference edges and reverse perfect elimination order */
 247         sched_foreach_reverse(block, irn) {
 248                 ir_node *live, *if_live;
 249                 ir_nodeset_iterator_t  iter, iter2;
 250
 251                 /* create nodes and interference edges */
 252                 foreach_ir_nodeset(&live_nodes, live, iter) {
 253                         /* create pbqp source node if it dosn't exist */
 254                         if(get_node(pbqp_inst, get_irn_idx(live)) == NULL) {
 255                                 restr_nodes[get_irn_idx(live)] = create_pbqp_node(pbqp_alloc_env, live);
 256                         }
 257
 258                         iter2 = iter;
 259                         for(if_live = ir_nodeset_iterator_next(&iter2); if_live != NULL; if_live = ir_nodeset_iterator_next(&iter2)) {
 260                                 /* create pbqp target node if it dosn't exist */
 261                                 if(get_node(pbqp_inst, get_irn_idx(if_live)) == NULL) {
 262                                         restr_nodes[get_irn_idx(if_live)] = create_pbqp_node(pbqp_alloc_env, if_live);
 263                                 }
 264                                 else {
 265                                         /* no edges to itself */
 266                                         if(live == if_live)
 267                                                 continue;
 268                                         /* only one interference edge between two nodes */
 269                                         if(get_edge(pbqp_inst, get_irn_idx(live), get_irn_idx(if_live)))
 270                                                 continue;
 271                                 }
 272
 273                                 /* do useful optimization to improve pbqp solving (we can do this because we know our matrix) */
 274                                 if(restr_nodes[get_irn_idx(live)] == 1 && restr_nodes[get_irn_idx(if_live)] == 1) {
 275                                         unsigned src_idx = vector_get_min_index(get_node(pbqp_inst, get_irn_idx(live))->costs);
 276                                         unsigned trg_idx = vector_get_min_index(get_node(pbqp_inst, get_irn_idx(if_live))->costs);
 277                                         assert(src_idx != trg_idx && "Interfering nodes could not have the same register!");
 278                                         continue;
 279                                 }
 280                                 if(restr_nodes[get_irn_idx(live)] == 1 || restr_nodes[get_irn_idx(if_live)] == 1) {
 281                                         if(restr_nodes[get_irn_idx(live)] == 1) {
 282                                                 unsigned idx = vector_get_min_index(get_node(pbqp_inst, get_irn_idx(live))->costs);
 283                                                 vector_set(get_node(pbqp_inst, get_irn_idx(if_live))->costs, idx, INF_COSTS);
 284                                         }
 285                                         else {
 286                                                 unsigned idx = vector_get_min_index(get_node(pbqp_inst, get_irn_idx(if_live))->costs);
 287                                                 vector_set(get_node(pbqp_inst, get_irn_idx(live))->costs, idx, INF_COSTS);
 288                                         }
 289                                         continue;
 290                                 }
 291
 292                                 /* copy matrix */
 293                                 struct pbqp_matrix *matrix = pbqp_matrix_copy(pbqp_inst, ife_matrix_dummy);
 294                                 /* add costs matrix to interference edge */
 295                                 add_edge_costs(pbqp_inst, get_irn_idx(live), get_irn_idx(if_live) , matrix);
 296                         }
 297                 }
 298
 299                 /* order nodes for perfect elimination order */
 300                 if (get_irn_mode(irn) == mode_T) {
 301                         plist_element_t *first = plist_first(temp_list);
 302                         const ir_edge_t *edge;
 303
 304                         foreach_out_edge(irn, edge) {
 305                                 ir_node *proj = get_edge_src_irn(edge);
 306                                 if (!arch_irn_consider_in_reg_alloc(cls, proj))
 307                                         continue;
 308
 309                                 // insert proj node into priority queue (descending by the number of interference edges)
 310                                 if(restr_nodes[get_irn_idx(proj)] <= 4/*bitset_is_set(restr_nodes, get_irn_idx(proj))*/) {
 311                                         pqueue_put(restr_nodes_queue, proj, pbqp_node_get_degree(get_node(pbqp_inst, get_irn_idx(proj))));
 312                                 }
 313                                 else {
 314                                         pqueue_put(queue,proj, pbqp_node_get_degree(get_node(pbqp_inst, get_irn_idx(proj))));
 315                                 }
 316
 317                         }
 318
 319                         /* first insert all restricted nodes */
 320                         while(!pqueue_empty(restr_nodes_queue)) {
 321                                 if(first == NULL) {
 322                                         plist_insert_back(temp_list, get_node(pbqp_inst, get_irn_idx(pqueue_pop_front(restr_nodes_queue))));
 323                                         first = plist_first(temp_list);
 324                                 } else {
 325                                         plist_insert_before(temp_list, first, get_node(pbqp_inst, get_irn_idx(pqueue_pop_front(restr_nodes_queue))));
 326                                 }
 327                         }
 328
 329                         /* insert proj nodes descending by their number of interference edges */
 330                         while(!pqueue_empty(queue)) {
 331                                 if(first == NULL) {
 332                                         plist_insert_back(temp_list, get_node(pbqp_inst, get_irn_idx(pqueue_pop_front(queue))));
 333                                         first = plist_first(temp_list);
 334                                 } else {
 335                                         plist_insert_before(temp_list, first, get_node(pbqp_inst, get_irn_idx(pqueue_pop_front(queue))));
 336                                 }
 337                         }
 338                 }
 339                 else {
 340                         if (arch_irn_consider_in_reg_alloc(cls, irn)) {
 341                                 plist_insert_front(temp_list, get_node(pbqp_inst, get_irn_idx(irn)));
 342                         }
 343                 }
 344
 345                 /* get living nodes for next step */
 346                 if (!is_Phi(irn)) {
 347                         be_liveness_transfer(cls, irn, &live_nodes);
 348                 }
 349         }
 350
 351         /* insert nodes into reverse perfect elimination order */
 352         plist_element_t *el;
 353         foreach_plist(temp_list, el) {
 354                 plist_insert_back(rpeo, el->data);
 355         }
 356
 357         /* free reserved memory */
 358         ir_nodeset_destroy(&live_nodes);
 359         plist_free(temp_list);
 360         del_pqueue(queue);
 361         del_pqueue(restr_nodes_queue);
 362 }
 363
 364 static void insert_perms(ir_node *block, void *data) {
 365         /*
 366          * Start silent in the start block.
 367          * The silence remains until the first barrier is seen.
 368          * Each other block is begun loud.
 369          */
 370         be_chordal_env_t *env    = data;
 371         ir_node          *irn;
 372         int               silent = block == get_irg_start_block(get_irn_irg(block));
 373
 374         /*
 375          * If the block is the start block search the barrier and
 376          * start handling constraints from there.
 377          */
 378         for (irn = sched_first(block); !sched_is_end(irn);) {
 379                 int silent_old = silent;        /* store old silent value */
 380                 if (be_is_Barrier(irn))
 381                         silent = !silent;               /* toggle silent flag */
 382
 383                 be_insn_t *insn         = chordal_scan_insn(env, irn);
 384                 irn                                     = insn->next_insn;
 385
 386                 if (silent_old)
 387                         continue;
 388
 389                 if (!insn->has_constraints)
 390                         continue;
 391
 392                 pre_process_constraints(env, &insn);
 393         }
 394 }
 395
 396
 397 void be_pbqp_coloring(be_chordal_env_t *env) {
 398         ir_graph                      *irg  = env->irg;
 399         be_irg_t                      *birg = env->birg;
 400         const arch_register_class_t   *cls  = env->cls;
 401         unsigned colors_n                                   = arch_register_class_n_regs(cls);
 402         be_pbqp_alloc_env_t pbqp_alloc_env;
 403         unsigned idx, row, col;
 404         be_lv_t *lv;
 405
 406 //      ir_timer_t *t_ra_pbqp_alloc_create    = ir_timer_register("be_pbqp_alloc_create", "pbqp alloc create");
 407 //      ir_timer_t *t_ra_pbqp_alloc_solve     = ir_timer_register("be_pbqp_alloc_solve", "pbqp alloc solve");
 408 //      ir_timer_t *t_ra_pbqp_alloc_create_aff  = ir_timer_register("be_pbqp_alloc_create_aff", "pbqp alloc create aff");
 409
 410         lv = be_assure_liveness(birg);
 411         be_liveness_assure_sets(lv);
 412         be_liveness_assure_chk(lv);
 413
 414 //      printf("#### ----- === Allocating registers of %s (%s) ===\n", cls->name, get_entity_name(get_irg_entity(irg)));
 415
 416         /* insert perms */
 417         assure_doms(irg);
 418         dom_tree_walk_irg(irg, insert_perms, NULL, env);
 419
 420         /* dump graph after inserting perms */
 421         if (env->opts->dump_flags & BE_CH_DUMP_CONSTR) {
 422                 char buf[256];
 423                 snprintf(buf, sizeof(buf), "-%s-constr", cls->name);
 424                 be_dump(irg, buf, dump_ir_block_graph_sched);
 425         }
 426
 427         /* initialize pbqp allocation data structure */
 428         pbqp_alloc_env.pbqp_inst    = alloc_pbqp(get_irg_last_idx(irg));                /* initialize pbqp instance */
 429         pbqp_alloc_env.birg         = birg;
 430         pbqp_alloc_env.cls          = cls;
 431         pbqp_alloc_env.irg          = irg;
 432         pbqp_alloc_env.lv           = lv;
 433         pbqp_alloc_env.ignored_regs = bitset_malloc(colors_n);
 434         pbqp_alloc_env.rpeo                     = plist_new();
 435         pbqp_alloc_env.restr_nodes  = XMALLOCNZ(unsigned, get_irg_last_idx(irg));
 436         pbqp_alloc_env.env                      = env;
 437         be_put_ignore_regs(birg, cls, pbqp_alloc_env.ignored_regs);                             /* get ignored registers */
 438
 439         /* create costs matrix for interference edges */
 440         struct pbqp_matrix *ife_matrix = pbqp_matrix_alloc(pbqp_alloc_env.pbqp_inst, colors_n, colors_n);
 441         /* set costs */
 442         for(row = 0, col=0; row < colors_n; row++, col++)
 443                 pbqp_matrix_set(ife_matrix, row, col, INF_COSTS);
 444
 445         pbqp_alloc_env.ife_matrix_dummy = ife_matrix;
 446
 447         /* create costs matrix for affinity edges */
 448         struct pbqp_matrix *afe_matrix = pbqp_matrix_alloc(pbqp_alloc_env.pbqp_inst, colors_n, colors_n);
 449         /* set costs */
 450         for(row = 0; row < colors_n; row++) {
 451                 for(col = 0; col < colors_n; col++) {
 452                         if(row != col)
 453                                 pbqp_matrix_set(afe_matrix, row, col, 2);
 454                 }
 455         }
 456         pbqp_alloc_env.aff_matrix_dummy = afe_matrix;
 457
 458
 459         /* create pbqp instance */
 460 //      ir_timer_reset_and_start(t_ra_pbqp_alloc_create);
 461         assure_doms(irg);
 462         dom_tree_walk_irg(irg, create_pbqp_coloring_inst , NULL, &pbqp_alloc_env);
 463 //      ir_timer_stop(t_ra_pbqp_alloc_create);
 464
 465         /* set up affinity edges */
 466 //      ir_timer_reset_and_start(t_ra_pbqp_alloc_create_aff);
 467         irg_walk_graph(irg, build_graph_walker, NULL, &pbqp_alloc_env);
 468 //      ir_timer_stop(t_ra_pbqp_alloc_create_aff);
 469
 470 #if KAPS_DUMP
 471         // dump graph before solving pbqp
 472         FILE *file_before = my_open(env, "", "-pbqp_coloring.html");
 473         set_dumpfile(pbqp_alloc_env.pbqp_inst, file_before);
 474 #endif
 475
 476         /* solve pbqp instance */
 477 //      ir_timer_reset_and_start(t_ra_pbqp_alloc_solve);
 478         solve_pbqp_heuristical_co(pbqp_alloc_env.pbqp_inst,pbqp_alloc_env.rpeo);
 479 //      ir_timer_stop(t_ra_pbqp_alloc_solve);
 480         num solution = get_solution(pbqp_alloc_env.pbqp_inst);
 481         assert(solution != INF_COSTS && "No PBQP solution found");
 482
 483         plist_element_t *element;
 484         foreach_plist(pbqp_alloc_env.rpeo, element) {
 485                 pbqp_node *node                    = element->data;
 486                 idx                                    = node->index;
 487                 ir_node *irn               = get_idx_irn(irg, idx);
 488                 num color                  = get_node_solution(pbqp_alloc_env.pbqp_inst, idx);
 489                 const arch_register_t *reg = arch_register_for_index(cls, color);
 490
 491                 arch_set_irn_register(irn, reg);
 492         }
 493
 494 //      printf("%-20s: %8.3lf msec\n" , ir_timer_get_description(t_ra_pbqp_alloc_create), (double)ir_timer_elapsed_usec(t_ra_pbqp_alloc_create) / 1000.0);
 495 //      printf("%-20s: %8.3lf msec\n" , ir_timer_get_description(t_ra_pbqp_alloc_solve), (double)ir_timer_elapsed_usec(t_ra_pbqp_alloc_solve) / 1000.0);
 496 //      printf("%-20s: %8.3lf msec\n" , ir_timer_get_description(t_ra_pbqp_alloc_create_aff), (double)ir_timer_elapsed_usec(t_ra_pbqp_alloc_create_aff) / 1000.0);
 497
 498
 499         /* free reserved memory */
 500 #if KAPS_DUMP
 501         fclose(file_before);
 502 #endif
 503         bitset_free(pbqp_alloc_env.ignored_regs);
 504         free_pbqp(pbqp_alloc_env.pbqp_inst);
 505         plist_free(pbqp_alloc_env.rpeo);
 506         xfree(pbqp_alloc_env.restr_nodes);
 507 }
 508
 509
 510 /**
 511  * Initializes this module.
 512  */
 513 void be_init_pbqp_coloring(void) {
 514
 515         static be_ra_chordal_coloring_t coloring = {
 516                 be_pbqp_coloring
 517         };
 518
 519         be_register_chordal_coloring("pbqp", &coloring);
 520 }
 521
 522 BE_REGISTER_MODULE_CONSTRUCTOR(be_pbqp_alloc);
 523
 524 #endif