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

   1 /*
   2  * This file is part of libFirm.
   3  * Copyright (C) 2012 University of Karlsruhe.
   4  */
   5
   6 /**
   7  * @file
   8  * @brief       Block-scheduling strategies.
   9  * @author      Matthias Braun, Christoph Mallon
  10  * @date        27.09.2006
  11  *
  12  * The goals of the greedy (and ILP) algorithm here works by assuming that
  13  * we want to change as many jumps to fallthroughs as possible (executed jumps
  14  * actually, we have to look at the execution frequencies). The algorithms
  15  * do this by collecting execution frequencies of all branches (which is easily
  16  * possible when all critical edges are split) then removes critical edges where
  17  * possible as we don't need and want them anymore now. The algorithms then try
  18  * to change as many edges to fallthroughs as possible, this is done by setting
  19  * a next and prev pointers on blocks. The greedy algorithm sorts the edges by
  20  * execution frequencies and tries to transform them to fallthroughs in this order
  21  */
  22 #include "config.h"
  23
  24 #include "beblocksched.h"
  25
  26 #include <stdlib.h>
  27
  28 #include "array.h"
  29 #include "pdeq.h"
  30 #include "beirg.h"
  31 #include "iredges.h"
  32 #include "irgwalk.h"
  33 #include "irnode_t.h"
  34 #include "irgraph_t.h"
  35 #include "irloop.h"
  36 #include "irprintf.h"
  37 #include "execfreq.h"
  38 #include "irdump_t.h"
  39 #include "irtools.h"
  40 #include "util.h"
  41 #include "debug.h"
  42 #include "beirgmod.h"
  43 #include "bemodule.h"
  44 #include "be.h"
  45 #include "error.h"
  46
  47 #include "lc_opts.h"
  48 #include "lc_opts_enum.h"
  49
  50 #include "lpp.h"
  51 #include "lpp_net.h"
  52
  53 DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;)
  54
  55 typedef enum blocksched_algos_t {
  56         BLOCKSCHED_NAIV, BLOCKSCHED_GREEDY, BLOCKSCHED_ILP
  57 } blocksched_algos_t;
  58
  59 static int algo = BLOCKSCHED_GREEDY;
  60
  61 static const lc_opt_enum_int_items_t blockschedalgo_items[] = {
  62         { "naiv",   BLOCKSCHED_NAIV },
  63         { "greedy", BLOCKSCHED_GREEDY },
  64         { "ilp",    BLOCKSCHED_ILP },
  65         { NULL,     0 }
  66 };
  67
  68 static lc_opt_enum_int_var_t algo_var = {
  69         &algo, blockschedalgo_items
  70 };
  71
  72 static const lc_opt_table_entry_t be_blocksched_options[] = {
  73         LC_OPT_ENT_ENUM_INT ("blockscheduler", "the block scheduling algorithm", &algo_var),
  74         LC_OPT_LAST
  75 };
  76
  77 /*
  78  *   ____                   _
  79  *  / ___|_ __ ___  ___  __| |_   _
  80  * | |  _| '__/ _ \/ _ \/ _` | | | |
  81  * | |_| | | |  __/  __/ (_| | |_| |
  82  *  \____|_|  \___|\___|\__,_|\__, |
  83  *                            |___/
  84  */
  85
  86 typedef struct blocksched_entry_t blocksched_entry_t;
  87 struct blocksched_entry_t {
  88         ir_node            *block;
  89         blocksched_entry_t *next;
  90         blocksched_entry_t *prev;
  91 };
  92
  93 typedef struct edge_t edge_t;
  94 struct edge_t {
  95         ir_node *block;             /**< source block */
  96         int     pos;                /**< number of cfg predecessor (target) */
  97         double  execfreq;           /**< the frequency */
  98         double  outedge_penalty_freq; /**< for edges leaving the loop this is the
  99                                            penality when we make them a
 100                                            fallthrough. */
 101         int     highest_execfreq;   /**< flag that indicates whether this edge is
 102                                          the edge with the highest execfreq pointing
 103                                          away from this block */
 104 };
 105
 106 typedef struct blocksched_env_t blocksched_env_t;
 107 struct blocksched_env_t {
 108         ir_graph       *irg;
 109         struct obstack  obst;
 110         edge_t         *edges;
 111         pdeq           *worklist;
 112         int            blockcount;
 113 };
 114
 115 static blocksched_entry_t* get_blocksched_entry(const ir_node *block)
 116 {
 117         return (blocksched_entry_t*)get_irn_link(block);
 118 }
 119
 120 /**
 121  * Collect cfg frequencies of all edges between blocks.
 122  * Also determines edge with highest frequency.
 123  */
 124 static void collect_egde_frequency(ir_node *block, void *data)
 125 {
 126         blocksched_env_t   *env = (blocksched_env_t*)data;
 127         int                arity;
 128         edge_t             edge;
 129         blocksched_entry_t *entry;
 130         ir_loop            *loop;
 131
 132         memset(&edge, 0, sizeof(edge));
 133
 134         entry = OALLOCZ(&env->obst, blocksched_entry_t);
 135         entry->block = block;
 136         set_irn_link(block, entry);
 137
 138         loop = get_irn_loop(block);
 139
 140         arity = get_Block_n_cfgpreds(block);
 141
 142         if (arity == 0) {
 143                 /* must be the start block (or end-block for endless loops),
 144                  * everything else is dead code and should be removed by now */
 145                 assert(block == get_irg_start_block(env->irg)
 146                                 || block == get_irg_end_block(env->irg));
 147                 /* nothing to do here */
 148                 return;
 149         } else if (arity == 1) {
 150                 ir_node *pred_block = get_Block_cfgpred_block(block, 0);
 151                 ir_loop *pred_loop  = get_irn_loop(pred_block);
 152                 float    freq       = (float)get_block_execfreq(block);
 153
 154                 /* is it an edge leaving a loop */
 155                 if (get_loop_depth(pred_loop) > get_loop_depth(loop)) {
 156                         float pred_freq = (float)get_block_execfreq(pred_block);
 157                         edge.outedge_penalty_freq = -(pred_freq - freq);
 158                 }
 159
 160                 edge.block            = block;
 161                 edge.pos              = 0;
 162                 edge.execfreq         = freq;
 163                 edge.highest_execfreq = 1;
 164                 ARR_APP1(edge_t, env->edges, edge);
 165         } else {
 166                 int    i;
 167                 double highest_execfreq = -1.0;
 168                 int    highest_edge_num = -1;
 169
 170                 edge.block = block;
 171                 for (i = 0; i < arity; ++i) {
 172                         double  execfreq;
 173                         ir_node *pred_block = get_Block_cfgpred_block(block, i);
 174
 175                         execfreq = get_block_execfreq(pred_block);
 176
 177                         edge.pos              = i;
 178                         edge.execfreq         = execfreq;
 179                         edge.highest_execfreq = 0;
 180                         ARR_APP1(edge_t, env->edges, edge);
 181
 182                         if (execfreq > highest_execfreq) {
 183                                 highest_execfreq = execfreq;
 184                                 highest_edge_num = ARR_LEN(env->edges) - 1;
 185                         }
 186                 }
 187
 188                 if (highest_edge_num >= 0)
 189                         env->edges[highest_edge_num].highest_execfreq = 1;
 190         }
 191 }
 192
 193 static int cmp_edges_base(const edge_t *e1, const edge_t *e2)
 194 {
 195         long nr1 = get_irn_node_nr(e1->block);
 196         long nr2 = get_irn_node_nr(e2->block);
 197         if (nr1 < nr2) {
 198                 return 1;
 199         } else if (nr1 > nr2) {
 200                 return -1;
 201         } else {
 202                 if (e1->pos < e2->pos) {
 203                         return 1;
 204                 } else if (e1->pos > e2->pos) {
 205                         return -1;
 206                 } else {
 207                         return 0;
 208                 }
 209         }
 210 }
 211
 212 static int cmp_edges(const void *d1, const void *d2)
 213 {
 214         const edge_t *e1 = (const edge_t*)d1;
 215         const edge_t *e2 = (const edge_t*)d2;
 216         double        freq1 = e1->execfreq;
 217         double        freq2 = e2->execfreq;
 218         if (freq1 < freq2) {
 219                 return 1;
 220         } else if (freq1 > freq2) {
 221                 return -1;
 222         } else {
 223                 return cmp_edges_base(e1, e2);
 224         }
 225 }
 226
 227 static int cmp_edges_outedge_penalty(const void *d1, const void *d2)
 228 {
 229         const edge_t *e1   = (const edge_t*)d1;
 230         const edge_t *e2   = (const edge_t*)d2;
 231         double        pen1 = e1->outedge_penalty_freq;
 232         double        pen2 = e2->outedge_penalty_freq;
 233         if (pen1 > pen2) {
 234                 return 1;
 235         } else if (pen1 < pen2) {
 236                 return -1;
 237         } else {
 238                 return cmp_edges_base(e1, e2);
 239         }
 240 }
 241
 242 static void clear_loop_links(ir_loop *loop)
 243 {
 244         int i, n;
 245
 246         set_loop_link(loop, NULL);
 247         n = get_loop_n_elements(loop);
 248         for (i = 0; i < n; ++i) {
 249                 loop_element elem = get_loop_element(loop, i);
 250                 if (*elem.kind == k_ir_loop) {
 251                         clear_loop_links(elem.son);
 252                 }
 253         }
 254 }
 255
 256 static void coalesce_blocks(blocksched_env_t *env)
 257 {
 258         int i;
 259         int edge_count = ARR_LEN(env->edges);
 260         edge_t *edges = env->edges;
 261
 262         /* sort interblock edges by execution frequency */
 263         qsort(edges, ARR_LEN(edges), sizeof(edges[0]), cmp_edges);
 264
 265         /* run1: only look at jumps */
 266         for (i = 0; i < edge_count; ++i) {
 267                 const edge_t *edge  = &edges[i];
 268                 ir_node      *block = edge->block;
 269                 int           pos   = edge->pos;
 270                 ir_node      *pred_block;
 271                 blocksched_entry_t *entry, *pred_entry;
 272
 273                 /* only check edge with highest frequency */
 274                 if (! edge->highest_execfreq)
 275                         continue;
 276
 277                 /* the block might have been removed already... */
 278                 if (is_Bad(get_Block_cfgpred(block, 0)))
 279                         continue;
 280
 281                 pred_block = get_Block_cfgpred_block(block, pos);
 282                 entry      = get_blocksched_entry(block);
 283                 pred_entry = get_blocksched_entry(pred_block);
 284
 285                 if (pred_entry->next != NULL || entry->prev != NULL)
 286                         continue;
 287
 288                 /* only coalesce jumps */
 289                 if (get_block_succ_next(pred_block, get_block_succ_first(pred_block)) != NULL)
 290                         continue;
 291
 292                 /* schedule the 2 blocks behind each other */
 293                 DB((dbg, LEVEL_1, "Coalesce (Jump) %+F -> %+F (%.3g)\n",
 294                            pred_entry->block, entry->block, edge->execfreq));
 295                 pred_entry->next = entry;
 296                 entry->prev      = pred_entry;
 297         }
 298
 299         /* run2: pick loop fallthroughs */
 300         clear_loop_links(get_irg_loop(env->irg));
 301
 302         qsort(edges, ARR_LEN(edges), sizeof(edges[0]), cmp_edges_outedge_penalty);
 303         for (i = 0; i < edge_count; ++i) {
 304                 const edge_t *edge  = &edges[i];
 305                 ir_node      *block = edge->block;
 306                 int           pos   = edge->pos;
 307                 ir_node      *pred_block;
 308                 blocksched_entry_t *entry, *pred_entry;
 309                 ir_loop      *loop;
 310                 ir_loop      *outer_loop;
 311
 312                 /* already seen all loop outedges? */
 313                 if (edge->outedge_penalty_freq == 0)
 314                         break;
 315
 316                 /* the block might have been removed already... */
 317                 if (is_Bad(get_Block_cfgpred(block, pos)))
 318                         continue;
 319
 320                 pred_block = get_Block_cfgpred_block(block, pos);
 321                 entry      = get_blocksched_entry(block);
 322                 pred_entry = get_blocksched_entry(pred_block);
 323
 324                 if (pred_entry->next != NULL || entry->prev != NULL)
 325                         continue;
 326
 327                 /* we want at most 1 outedge fallthrough per loop */
 328                 loop = get_irn_loop(pred_block);
 329                 if (get_loop_link(loop) != NULL)
 330                         continue;
 331
 332                 /* schedule the 2 blocks behind each other */
 333                 DB((dbg, LEVEL_1, "Coalesce (Loop Outedge) %+F -> %+F (%.3g)\n",
 334                            pred_entry->block, entry->block, edge->execfreq));
 335                 pred_entry->next = entry;
 336                 entry->prev      = pred_entry;
 337
 338                 /* all loops left have an outedge now */
 339                 outer_loop = get_irn_loop(block);
 340                 do {
 341                         /* we set loop link to loop to mark it */
 342                         set_loop_link(loop, loop);
 343                         loop = get_loop_outer_loop(loop);
 344                 } while (loop != outer_loop);
 345         }
 346
 347         /* sort interblock edges by execution frequency */
 348         qsort(edges, ARR_LEN(edges), sizeof(edges[0]), cmp_edges);
 349
 350         /* run3: remaining edges */
 351         for (i = 0; i < edge_count; ++i) {
 352                 const edge_t *edge  = &edges[i];
 353                 ir_node      *block = edge->block;
 354                 int           pos   = edge->pos;
 355                 ir_node      *pred_block;
 356                 blocksched_entry_t *entry, *pred_entry;
 357
 358                 /* the block might have been removed already... */
 359                 if (is_Bad(get_Block_cfgpred(block, pos)))
 360                         continue;
 361
 362                 pred_block = get_Block_cfgpred_block(block, pos);
 363                 entry      = get_blocksched_entry(block);
 364                 pred_entry = get_blocksched_entry(pred_block);
 365
 366                 /* is 1 of the blocks already attached to another block? */
 367                 if (pred_entry->next != NULL || entry->prev != NULL)
 368                         continue;
 369
 370                 /* schedule the 2 blocks behind each other */
 371                 DB((dbg, LEVEL_1, "Coalesce (CondJump) %+F -> %+F (%.3g)\n",
 372                            pred_entry->block, entry->block, edge->execfreq));
 373                 pred_entry->next = entry;
 374                 entry->prev      = pred_entry;
 375         }
 376 }
 377
 378 static void pick_block_successor(blocksched_entry_t *entry, blocksched_env_t *env)
 379 {
 380         ir_node            *block = entry->block;
 381         ir_node            *succ  = NULL;
 382         blocksched_entry_t *succ_entry;
 383         double              best_succ_execfreq;
 384
 385         if (irn_visited_else_mark(block))
 386                 return;
 387
 388         env->blockcount++;
 389
 390         DB((dbg, LEVEL_1, "Pick succ of %+F\n", block));
 391
 392         /* put all successors into the worklist */
 393         foreach_block_succ(block, edge) {
 394                 ir_node *succ_block = get_edge_src_irn(edge);
 395
 396                 if (irn_visited(succ_block))
 397                         continue;
 398
 399                 /* we only need to put the first of a series of already connected
 400                  * blocks into the worklist */
 401                 succ_entry = get_blocksched_entry(succ_block);
 402                 while (succ_entry->prev != NULL) {
 403                         /* break cycles... */
 404                         if (succ_entry->prev->block == succ_block) {
 405                                 succ_entry->prev->next = NULL;
 406                                 succ_entry->prev       = NULL;
 407                                 break;
 408                         }
 409                         succ_entry = succ_entry->prev;
 410                 }
 411
 412                 if (irn_visited(succ_entry->block))
 413                         continue;
 414
 415                 DB((dbg, LEVEL_1, "Put %+F into worklist\n", succ_entry->block));
 416                 pdeq_putr(env->worklist, succ_entry->block);
 417         }
 418
 419         if (entry->next != NULL) {
 420                 pick_block_successor(entry->next, env);
 421                 return;
 422         }
 423
 424         DB((dbg, LEVEL_1, "deciding...\n"));
 425         best_succ_execfreq = -1;
 426
 427         /* no successor yet: pick the successor block with the highest execution
 428          * frequency which has no predecessor yet */
 429
 430         foreach_block_succ(block, edge) {
 431                 ir_node *succ_block = get_edge_src_irn(edge);
 432
 433                 if (irn_visited(succ_block))
 434                         continue;
 435
 436                 succ_entry = get_blocksched_entry(succ_block);
 437                 if (succ_entry->prev != NULL)
 438                         continue;
 439
 440                 double execfreq = get_block_execfreq(succ_block);
 441                 if (execfreq > best_succ_execfreq) {
 442                         best_succ_execfreq = execfreq;
 443                         succ = succ_block;
 444                 }
 445         }
 446
 447         if (succ == NULL) {
 448                 DB((dbg, LEVEL_1, "pick from worklist\n"));
 449
 450                 do {
 451                         if (pdeq_empty(env->worklist)) {
 452                                 DB((dbg, LEVEL_1, "worklist empty\n"));
 453                                 return;
 454                         }
 455                         succ = (ir_node*)pdeq_getl(env->worklist);
 456                 } while (irn_visited(succ));
 457         }
 458
 459         succ_entry       = get_blocksched_entry(succ);
 460         entry->next      = succ_entry;
 461         succ_entry->prev = entry;
 462
 463         pick_block_successor(succ_entry, env);
 464 }
 465
 466 static blocksched_entry_t *finish_block_schedule(blocksched_env_t *env)
 467 {
 468         ir_graph           *irg        = env->irg;
 469         ir_node            *startblock = get_irg_start_block(irg);
 470         blocksched_entry_t *entry      = get_blocksched_entry(startblock);
 471
 472         ir_reserve_resources(irg, IR_RESOURCE_IRN_VISITED);
 473         inc_irg_visited(irg);
 474
 475         env->worklist = new_pdeq();
 476         pick_block_successor(entry, env);
 477         assert(pdeq_empty(env->worklist));
 478         del_pdeq(env->worklist);
 479
 480         ir_free_resources(irg, IR_RESOURCE_IRN_VISITED);
 481
 482         return entry;
 483 }
 484
 485 static ir_node **create_blocksched_array(blocksched_env_t *env, blocksched_entry_t *first,
 486                                                                                 int count, struct obstack* obst)
 487 {
 488         int                i = 0;
 489         ir_node            **block_list;
 490         blocksched_entry_t *entry;
 491         (void) env;
 492
 493         block_list = NEW_ARR_D(ir_node *, obst, count);
 494         DB((dbg, LEVEL_1, "Blockschedule:\n"));
 495
 496         for (entry = first; entry != NULL; entry = entry->next) {
 497                 assert(i < count);
 498                 block_list[i++] = entry->block;
 499                 DB((dbg, LEVEL_1, "\t%+F\n", entry->block));
 500         }
 501         assert(i == count);
 502
 503         return block_list;
 504 }
 505
 506 static ir_node **create_block_schedule_greedy(ir_graph *irg)
 507 {
 508         blocksched_env_t   env;
 509         blocksched_entry_t *start_entry;
 510         ir_node            **block_list;
 511
 512         env.irg        = irg;
 513         env.edges      = NEW_ARR_F(edge_t, 0);
 514         env.worklist   = NULL;
 515         env.blockcount = 0;
 516         obstack_init(&env.obst);
 517
 518         assure_loopinfo(irg);
 519
 520         // collect edge execution frequencies
 521         irg_block_walk_graph(irg, collect_egde_frequency, NULL, &env);
 522
 523         (void)be_remove_empty_blocks(irg);
 524
 525         if (algo != BLOCKSCHED_NAIV)
 526                 coalesce_blocks(&env);
 527
 528         start_entry = finish_block_schedule(&env);
 529         block_list  = create_blocksched_array(&env, start_entry, env.blockcount,
 530                                               be_get_be_obst(irg));
 531
 532         DEL_ARR_F(env.edges);
 533         obstack_free(&env.obst, NULL);
 534
 535         return block_list;
 536 }
 537
 538 /*
 539  *  ___ _     ____
 540  * |_ _| |   |  _ \
 541  *  | || |   | |_) |
 542  *  | || |___|  __/
 543  * |___|_____|_|
 544  *
 545  */
 546
 547 typedef struct ilp_edge_t {
 548         ir_node *block;   /**< source block */
 549         int     pos;      /**< number of cfg predecessor (target) */
 550         int     ilpvar;
 551 } ilp_edge_t;
 552
 553 typedef struct blocksched_ilp_env_t {
 554         blocksched_env_t env;
 555         ilp_edge_t       *ilpedges;
 556         lpp_t            *lpp;
 557 } blocksched_ilp_env_t;
 558
 559 typedef struct blocksched_ilp_entry_t {
 560         ir_node *block;
 561         struct blocksched_entry_t *next;
 562         struct blocksched_entry_t *prev;
 563
 564         int out_cst;
 565 } blocksched_ilp_entry_t;
 566
 567 static int add_ilp_edge(ir_node *block, int pos, double execfreq, blocksched_ilp_env_t *env)
 568 {
 569         char       name[64];
 570         ilp_edge_t edge;
 571         int        edgeidx = ARR_LEN(env->ilpedges);
 572
 573         snprintf(name, sizeof(name), "edge%d", edgeidx);
 574
 575         edge.block  = block;
 576         edge.pos    = pos;
 577         edge.ilpvar = lpp_add_var_default(env->lpp, name, lpp_binary, execfreq, 1.0);
 578
 579         ARR_APP1(ilp_edge_t, env->ilpedges, edge);
 580         return edgeidx;
 581 }
 582
 583 static void collect_egde_frequency_ilp(ir_node *block, void *data)
 584 {
 585         blocksched_ilp_env_t *env        = (blocksched_ilp_env_t*)data;
 586         ir_graph             *irg        = env->env.irg;
 587         ir_node              *startblock = get_irg_start_block(irg);
 588         int                  arity;
 589         char                 name[64];
 590         int                  out_count;
 591         blocksched_ilp_entry_t *entry;
 592
 593         snprintf(name, sizeof(name), "block_out_constr_%ld", get_irn_node_nr(block));
 594         out_count = get_irn_n_edges_kind(block, EDGE_KIND_BLOCK);
 595
 596         entry          = OALLOC(&env->env.obst, blocksched_ilp_entry_t);
 597         entry->block   = block;
 598         entry->next    = NULL;
 599         entry->prev    = NULL;
 600         entry->out_cst = lpp_add_cst_uniq(env->lpp, name, lpp_greater_equal, out_count - 1);
 601         set_irn_link(block, entry);
 602
 603         if (block == startblock)
 604                 return;
 605
 606         arity = get_irn_arity(block);
 607         if (arity == 1) {
 608                 double execfreq = get_block_execfreq(block);
 609                 add_ilp_edge(block, 0, execfreq, env);
 610         }
 611         else {
 612                 int i;
 613                 int cst_idx;
 614
 615                 snprintf(name, sizeof(name), "block_in_constr_%ld", get_irn_node_nr(block));
 616                 cst_idx = lpp_add_cst_uniq(env->lpp, name, lpp_greater_equal, arity - 1);
 617
 618                 for (i = 0; i < arity; ++i) {
 619                         double     execfreq;
 620                         int        edgenum;
 621                         ilp_edge_t *edge;
 622                         ir_node    *pred_block = get_Block_cfgpred_block(block, i);
 623
 624                         execfreq = get_block_execfreq(pred_block);
 625                         edgenum  = add_ilp_edge(block, i, execfreq, env);
 626                         edge     = &env->ilpedges[edgenum];
 627                         lpp_set_factor_fast(env->lpp, cst_idx, edge->ilpvar, 1.0);
 628                 }
 629         }
 630 }
 631
 632 static blocksched_ilp_entry_t *get_blocksched_ilp_entry(const ir_node *block)
 633 {
 634         return (blocksched_ilp_entry_t*)get_irn_link(block);
 635 }
 636
 637 static void coalesce_blocks_ilp(blocksched_ilp_env_t *env)
 638 {
 639         int           edge_count = ARR_LEN(env->ilpedges);
 640         int           i;
 641
 642         /* complete out constraints */
 643         for (i = 0; i < edge_count; ++i) {
 644                 const ilp_edge_t *edge  = &env->ilpedges[i];
 645                 ir_node          *block = edge->block;
 646                 ir_node          *pred;
 647                 blocksched_ilp_entry_t *entry;
 648
 649                 /* the block might have been removed already... */
 650                 if (is_Bad(get_Block_cfgpred(block, 0)))
 651                         continue;
 652
 653                 pred  = get_Block_cfgpred_block(block, edge->pos);
 654                 entry = get_blocksched_ilp_entry(pred);
 655
 656                 DB((dbg, LEVEL_1, "Adding out cst to %+F from %+F,%d\n",
 657                                   pred, block, edge->pos));
 658                 lpp_set_factor_fast(env->lpp, entry->out_cst, edge->ilpvar, 1.0);
 659         }
 660
 661         lpp_solve_net(env->lpp, be_options.ilp_server, be_options.ilp_solver);
 662         assert(lpp_is_sol_valid(env->lpp));
 663
 664         /* Apply results to edges */
 665         for (i = 0; i < edge_count; ++i) {
 666                 const ilp_edge_t   *edge  = &env->ilpedges[i];
 667                 ir_node            *block = edge->block;
 668                 ir_node            *pred;
 669                 int                is_jump;
 670                 blocksched_entry_t *entry;
 671                 blocksched_entry_t *pred_entry;
 672
 673                 /* the block might have been removed already... */
 674                 if (is_Bad(get_Block_cfgpred(block, 0)))
 675                         continue;
 676
 677                 is_jump = (int)lpp_get_var_sol(env->lpp, edge->ilpvar);
 678                 if (is_jump)
 679                         continue;
 680
 681                 pred       = get_Block_cfgpred_block(block, edge->pos);
 682                 entry      = get_blocksched_entry(block);
 683                 pred_entry = get_blocksched_entry(pred);
 684
 685                 assert(entry->prev == NULL && pred_entry->next == NULL);
 686                 entry->prev      = pred_entry;
 687                 pred_entry->next = entry;
 688         }
 689 }
 690
 691 static ir_node **create_block_schedule_ilp(ir_graph *irg)
 692 {
 693         blocksched_ilp_env_t env;
 694         blocksched_entry_t   *start_entry;
 695         ir_node              **block_list;
 696
 697         env.env.irg        = irg;
 698         env.env.worklist   = NULL;
 699         env.env.blockcount = 0;
 700         env.ilpedges       = NEW_ARR_F(ilp_edge_t, 0);
 701         obstack_init(&env.env.obst);
 702
 703         env.lpp = lpp_new("blockschedule", lpp_minimize);
 704         lpp_set_time_limit(env.lpp, 20);
 705         lpp_set_log(env.lpp, stdout);
 706
 707         irg_block_walk_graph(irg, collect_egde_frequency_ilp, NULL, &env);
 708
 709         (void)be_remove_empty_blocks(irg);
 710         coalesce_blocks_ilp(&env);
 711
 712         start_entry = finish_block_schedule(&env.env);
 713         block_list  = create_blocksched_array(&env.env, start_entry,
 714                                               env.env.blockcount,
 715                                               be_get_be_obst(irg));
 716
 717         DEL_ARR_F(env.ilpedges);
 718         lpp_free(env.lpp);
 719         obstack_free(&env.env.obst, NULL);
 720
 721         return block_list;
 722 }
 723
 724 /*
 725  *  __  __       _
 726  * |  \/  | __ _(_)_ __
 727  * | |\/| |/ _` | | '_ \
 728  * | |  | | (_| | | | | |
 729  * |_|  |_|\__,_|_|_| |_|
 730  *
 731  */
 732 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_blocksched)
 733 void be_init_blocksched(void)
 734 {
 735         lc_opt_entry_t *be_grp = lc_opt_get_grp(firm_opt_get_root(), "be");
 736
 737         lc_opt_add_table(be_grp, be_blocksched_options);
 738
 739         FIRM_DBG_REGISTER(dbg, "firm.be.blocksched");
 740 }
 741
 742 ir_node **be_create_block_schedule(ir_graph *irg)
 743 {
 744         switch (algo) {
 745         case BLOCKSCHED_GREEDY:
 746         case BLOCKSCHED_NAIV:
 747                 return create_block_schedule_greedy(irg);
 748         case BLOCKSCHED_ILP:
 749                 return create_block_schedule_ilp(irg);
 750         }
 751
 752         panic("unknown blocksched algo");
 753 }