nsz Git - libfirm/blob - ir/be/benewalloc.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       New approach to allocation and copy coalescing
  23  * @author      Matthias Braun
  24  * @date        14.2.2009
  25  * @version     $Id$
  26  *
  27  * ... WE NEED A NAME FOR THIS ...
  28  *
  29  * Only a proof of concept at this moment...
  30  *
  31  * The idea is to allocate registers in 2 passes:
  32  * 1. A first pass to determine "preferred" registers for live-ranges. This
  33  *    calculates for each register and each live-range a value indicating
  34  *    the usefulness. (You can roughly think of the value as the negative
  35  *    costs needed for copies when the value is in the specific registers...)
  36  *
  37  * 2. Walk blocks and assigns registers in a greedy fashion. Preferring
  38  *    registers with high preferences. When register constraints are not met,
  39  *    add copies and split live-ranges.
  40  *
  41  * TODO:
  42  *  - make use of free registers in the permute_values code
  43  *  - think about a smarter sequence of visiting the blocks. Sorted by
  44  *    execfreq might be good, or looptree from inner to outermost loops going
  45  *    over blocks in a reverse postorder
  46  *  - propagate preferences through Phis
  47  */
  48 #include "config.h"
  49
  50 #include <float.h>
  51 #include <stdbool.h>
  52
  53 #include "error.h"
  54 #include "execfreq.h"
  55 #include "ircons.h"
  56 #include "irdom.h"
  57 #include "iredges_t.h"
  58 #include "irgraph_t.h"
  59 #include "irgwalk.h"
  60 #include "irnode_t.h"
  61 #include "obst.h"
  62 #include "raw_bitset.h"
  63
  64 #include "beabi.h"
  65 #include "bechordal_t.h"
  66 #include "be.h"
  67 #include "beirg.h"
  68 #include "belive_t.h"
  69 #include "bemodule.h"
  70 #include "benode_t.h"
  71 #include "bera.h"
  72 #include "besched.h"
  73 #include "bespill.h"
  74 #include "bespillutil.h"
  75 #include "beverify.h"
  76
  77 #include "hungarian.h"
  78
  79 #define USE_FACTOR         1.0f
  80 #define DEF_FACTOR         1.0f
  81 #define NEIGHBOR_FACTOR    0.2f
  82 #define AFF_SHOULD_BE_SAME 0.5f
  83 #define AFF_PHI            1.0f
  84 #define SPLIT_DELTA        1.0f
  85
  86 DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;)
  87
  88 static struct obstack               obst;
  89 static be_irg_t                    *birg;
  90 static ir_graph                    *irg;
  91 static const arch_register_class_t *cls;
  92 static const arch_register_req_t   *default_cls_req;
  93 static be_lv_t                     *lv;
  94 static const ir_exec_freq          *execfreqs;
  95 static unsigned                     n_regs;
  96 static unsigned                    *normal_regs;
  97
  98 /** info about the current assignment for a register */
  99 struct assignment_t {
 100         ir_node *value;            /**< currently assigned value */
 101 };
 102 typedef struct assignment_t assignment_t;
 103
 104 /** currently active assignments (while processing a basic block) */
 105 static assignment_t *assignments;
 106
 107 /**
 108  * allocation information: last_uses, register preferences
 109  * the information is per firm-node.
 110  */
 111 struct allocation_info_t {
 112         unsigned  last_uses;      /**< bitset indicating last uses (input pos) */
 113         ir_node  *current_value;  /**< copy of the value that should be used */
 114         ir_node  *original_value; /**< for copies point to original value */
 115         float     prefs[0];       /**< register preferences */
 116 };
 117 typedef struct allocation_info_t allocation_info_t;
 118
 119 /** helper datastructure used when sorting register preferences */
 120 struct reg_pref_t {
 121         unsigned num;
 122         float    pref;
 123 };
 124 typedef struct reg_pref_t reg_pref_t;
 125
 126 /** per basic-block information */
 127 struct block_info_t {
 128         bool         processed;       /**< indicate wether block is processed */
 129         assignment_t assignments[0];  /**< register assignments at end of block */
 130 };
 131 typedef struct block_info_t block_info_t;
 132
 133 /**
 134  * Get the allocation info for a node.
 135  * The info is allocated on the first visit of a node.
 136  */
 137 static allocation_info_t *get_allocation_info(ir_node *node)
 138 {
 139         allocation_info_t *info;
 140         if (!irn_visited_else_mark(node)) {
 141                 size_t size = sizeof(info[0]) + n_regs * sizeof(info->prefs[0]);
 142                 info = obstack_alloc(&obst, size);
 143                 memset(info, 0, size);
 144                 info->current_value  = node;
 145                 info->original_value = node;
 146                 set_irn_link(node, info);
 147         } else {
 148                 info = get_irn_link(node);
 149         }
 150
 151         return info;
 152 }
 153
 154 /**
 155  * Get allocation information for a basic block
 156  */
 157 static block_info_t *get_block_info(ir_node *block)
 158 {
 159         block_info_t *info;
 160
 161         assert(is_Block(block));
 162         if (!irn_visited_else_mark(block)) {
 163                 size_t size = sizeof(info[0]) + n_regs * sizeof(info->assignments[0]);
 164                 info = obstack_alloc(&obst, size);
 165                 memset(info, 0, size);
 166                 set_irn_link(block, info);
 167         } else {
 168                 info = get_irn_link(block);
 169         }
 170
 171         return info;
 172 }
 173
 174 /**
 175  * Get default register requirement for the current register class
 176  */
 177 static const arch_register_req_t *get_default_req_current_cls(void)
 178 {
 179         if (default_cls_req == NULL) {
 180                 struct obstack      *obst = get_irg_obstack(irg);
 181                 arch_register_req_t *req  = obstack_alloc(obst, sizeof(*req));
 182                 memset(req, 0, sizeof(*req));
 183
 184                 req->type = arch_register_req_type_normal;
 185                 req->cls  = cls;
 186
 187                 default_cls_req = req;
 188         }
 189         return default_cls_req;
 190 }
 191
 192 /**
 193  * Link the allocation info of a node to a copy.
 194  * Afterwards, both nodes uses the same allocation info.
 195  * Copy must not have an allocation info assigned yet.
 196  *
 197  * @param copy   the node that gets the allocation info assigned
 198  * @param value  the original node
 199  */
 200 static void mark_as_copy_of(ir_node *copy, ir_node *value)
 201 {
 202         ir_node           *original;
 203         allocation_info_t *info      = get_allocation_info(value);
 204         allocation_info_t *copy_info = get_allocation_info(copy);
 205
 206         /* find original value */
 207         original = info->original_value;
 208         if (original != value) {
 209                 info = get_allocation_info(original);
 210         }
 211
 212         assert(info->original_value == original);
 213         info->current_value = copy;
 214
 215         /* the copy should not be linked to something else yet */
 216         assert(copy_info->original_value == copy);
 217         /* copy over allocation preferences */
 218         memcpy(copy_info->prefs, info->prefs, n_regs * sizeof(copy_info->prefs[0]));
 219         copy_info->original_value = original;
 220 }
 221
 222 /**
 223  * Calculate the penalties for every register on a node and its live neighbors.
 224  *
 225  * @param live_nodes  the set of live nodes at the current position, may be NULL
 226  * @param penalty     the penalty to subtract from
 227  * @param limited     a raw bitset containing the limited set for the node
 228  * @param node        the node
 229  */
 230 static void give_penalties_for_limits(const ir_nodeset_t *live_nodes,
 231                                       float penalty, const unsigned* limited,
 232                                       ir_node *node)
 233 {
 234         ir_nodeset_iterator_t iter;
 235         unsigned              r;
 236         allocation_info_t     *info = get_allocation_info(node);
 237         ir_node               *neighbor;
 238
 239         /* give penalty for all forbidden regs */
 240         for (r = 0; r < n_regs; ++r) {
 241                 if (rbitset_is_set(limited, r))
 242                         continue;
 243
 244                 info->prefs[r] -= penalty;
 245         }
 246
 247         /* all other live values should get a penalty for allowed regs */
 248         if (live_nodes == NULL)
 249                 return;
 250
 251         /* TODO: reduce penalty if there are multiple allowed registers... */
 252         penalty *= NEIGHBOR_FACTOR;
 253         foreach_ir_nodeset(live_nodes, neighbor, iter) {
 254                 allocation_info_t *neighbor_info;
 255
 256                 /* TODO: if op is used on multiple inputs we might not do a
 257                  * continue here */
 258                 if (neighbor == node)
 259                         continue;
 260
 261                 neighbor_info = get_allocation_info(neighbor);
 262                 for (r = 0; r < n_regs; ++r) {
 263                         if (!rbitset_is_set(limited, r))
 264                                 continue;
 265
 266                         neighbor_info->prefs[r] -= penalty;
 267                 }
 268         }
 269 }
 270
 271 /**
 272  * Calculate the preferences of a definition for the current register class.
 273  * If the definition uses a limited set of registers, reduce the preferences
 274  * for the limited register on the node and its neighbors.
 275  *
 276  * @param live_nodes  the set of live nodes at the current node
 277  * @param weight      the weight
 278  * @param node        the current node
 279  */
 280 static void check_defs(const ir_nodeset_t *live_nodes, float weight,
 281                        ir_node *node)
 282 {
 283         const arch_register_req_t *req;
 284
 285         if (get_irn_mode(node) == mode_T) {
 286                 const ir_edge_t *edge;
 287                 foreach_out_edge(node, edge) {
 288                         ir_node *proj = get_edge_src_irn(edge);
 289                         check_defs(live_nodes, weight, proj);
 290                 }
 291                 return;
 292         }
 293
 294         if (!arch_irn_consider_in_reg_alloc(cls, node))
 295                 return;
 296
 297         req = arch_get_register_req_out(node);
 298         if (req->type & arch_register_req_type_limited) {
 299                 const unsigned *limited = req->limited;
 300                 float           penalty = weight * DEF_FACTOR;
 301                 give_penalties_for_limits(live_nodes, penalty, limited, node);
 302         }
 303
 304         if (req->type & arch_register_req_type_should_be_same) {
 305                 ir_node           *insn  = skip_Proj(node);
 306                 allocation_info_t *info  = get_allocation_info(node);
 307                 int                arity = get_irn_arity(insn);
 308                 int                i;
 309
 310                 float factor = 1.0f / rbitset_popcnt(&req->other_same, arity);
 311                 for (i = 0; i < arity; ++i) {
 312                         ir_node           *op;
 313                         unsigned           r;
 314                         allocation_info_t *op_info;
 315
 316                         if (!rbitset_is_set(&req->other_same, i))
 317                                 continue;
 318
 319                         op = get_irn_n(insn, i);
 320
 321                         /* if we the value at the should_be_same input doesn't die at the
 322                          * node, then it is no use to propagate the constraints (since a
 323                          * copy will emerge anyway) */
 324                         if (ir_nodeset_contains(live_nodes, op))
 325                                 continue;
 326
 327                         op_info = get_allocation_info(op);
 328                         for (r = 0; r < n_regs; ++r) {
 329                                 op_info->prefs[r] += info->prefs[r] * factor;
 330                         }
 331                 }
 332         }
 333 }
 334
 335 /**
 336  * Walker: Runs an a block calculates the preferences for any
 337  * node and every register from the considered register class.
 338  */
 339 static void analyze_block(ir_node *block, void *data)
 340 {
 341         float         weight = get_block_execfreq(execfreqs, block);
 342         ir_nodeset_t  live_nodes;
 343         ir_node      *node;
 344         (void) data;
 345
 346         ir_nodeset_init(&live_nodes);
 347         be_liveness_end_of_block(lv, cls, block, &live_nodes);
 348
 349         sched_foreach_reverse(block, node) {
 350                 allocation_info_t *info;
 351                 int                i;
 352                 int                arity;
 353
 354                 if (is_Phi(node))
 355                         break;
 356
 357                 check_defs(&live_nodes, weight, node);
 358
 359                 /* mark last uses */
 360                 arity = get_irn_arity(node);
 361
 362                 /* the allocation info node currently only uses 1 unsigned value
 363                    to mark last used inputs. So we will fail for a node with more than
 364                    32 inputs. */
 365                 if (arity >= (int) sizeof(unsigned) * 8) {
 366                         panic("Node with more than %d inputs not supported yet",
 367                                         (int) sizeof(unsigned) * 8);
 368                 }
 369
 370                 info = get_allocation_info(node);
 371                 for (i = 0; i < arity; ++i) {
 372                         ir_node *op = get_irn_n(node, i);
 373                         if (!arch_irn_consider_in_reg_alloc(cls, op))
 374                                 continue;
 375
 376                         /* last usage of a value? */
 377                         if (!ir_nodeset_contains(&live_nodes, op)) {
 378                                 rbitset_set(&info->last_uses, i);
 379                         }
 380                 }
 381
 382                 be_liveness_transfer(cls, node, &live_nodes);
 383
 384                 /* update weights based on usage constraints */
 385                 for (i = 0; i < arity; ++i) {
 386                         const arch_register_req_t *req;
 387                         const unsigned            *limited;
 388                         ir_node                   *op = get_irn_n(node, i);
 389
 390                         if (!arch_irn_consider_in_reg_alloc(cls, op))
 391                                 continue;
 392
 393                         req = arch_get_register_req(node, i);
 394                         if (!(req->type & arch_register_req_type_limited))
 395                                 continue;
 396
 397                         limited = req->limited;
 398                         give_penalties_for_limits(&live_nodes, weight * USE_FACTOR, limited,
 399                                                   op);
 400                 }
 401         }
 402
 403         ir_nodeset_destroy(&live_nodes);
 404 }
 405
 406 /**
 407  * Assign register reg to the given node.
 408  *
 409  * @param node  the node
 410  * @param reg   the register
 411  */
 412 static void use_reg(ir_node *node, const arch_register_t *reg)
 413 {
 414         unsigned r = arch_register_get_index(reg);
 415         assignments[r].value = node;
 416         arch_set_irn_register(node, reg);
 417 }
 418
 419 static void free_reg_of_value(ir_node *node)
 420 {
 421         assignment_t          *assignment;
 422         const arch_register_t *reg;
 423         unsigned               r;
 424
 425         if (!arch_irn_consider_in_reg_alloc(cls, node))
 426                 return;
 427
 428         reg        = arch_get_irn_register(node);
 429         r          = arch_register_get_index(reg);
 430         assignment = &assignments[r];
 431         /* assignment->value may be NULL if a value is used at 2 inputs
 432            so it gets freed twice. */
 433         assert(assignment->value == node || assignment->value == NULL);
 434         assignment->value = NULL;
 435 }
 436
 437 /**
 438  * Compare two register preferences in decreasing order.
 439  */
 440 static int compare_reg_pref(const void *e1, const void *e2)
 441 {
 442         const reg_pref_t *rp1 = (const reg_pref_t*) e1;
 443         const reg_pref_t *rp2 = (const reg_pref_t*) e2;
 444         if (rp1->pref < rp2->pref)
 445                 return 1;
 446         if (rp1->pref > rp2->pref)
 447                 return -1;
 448         return 0;
 449 }
 450
 451 static void fill_sort_candidates(reg_pref_t *regprefs,
 452                                  const allocation_info_t *info)
 453 {
 454         unsigned r;
 455
 456         for (r = 0; r < n_regs; ++r) {
 457                 float pref = info->prefs[r];
 458                 regprefs[r].num  = r;
 459                 regprefs[r].pref = pref;
 460         }
 461         /* TODO: use a stable sort here to avoid unnecessary register jumping */
 462         qsort(regprefs, n_regs, sizeof(regprefs[0]), compare_reg_pref);
 463 }
 464
 465 static bool try_optimistic_split(ir_node *to_split, ir_node *before,
 466                                  float pref, float pref_delta,
 467                                  unsigned *output_regs)
 468 {
 469         const arch_register_t *reg;
 470         ir_node               *block;
 471         ir_node               *copy;
 472         unsigned               r;
 473         unsigned               i;
 474         allocation_info_t     *info = get_allocation_info(to_split);
 475
 476         (void) pref;
 477
 478         /* find the best free position where we could move to */
 479         reg_pref_t *prefs = ALLOCAN(reg_pref_t, n_regs);
 480         fill_sort_candidates(prefs, info);
 481         for (i = 0; i < n_regs; ++i) {
 482                 r = prefs[i].num;
 483                 if (!rbitset_is_set(normal_regs, r))
 484                         continue;
 485                 if (rbitset_is_set(output_regs, r))
 486                         continue;
 487                 if (assignments[r].value == NULL)
 488                         break;
 489         }
 490         if (i >= n_regs) {
 491                 return false;
 492         }
 493         /* TODO: use execfreq somehow... */
 494         float delta = pref_delta + prefs[i].pref;
 495         if (delta < SPLIT_DELTA) {
 496                 DB((dbg, LEVEL_3, "Not doing optimistical split, win %f too low\n",
 497                     delta));
 498                 return false;
 499         }
 500
 501         reg   = arch_register_for_index(cls, r);
 502         block = get_nodes_block(before);
 503         copy = be_new_Copy(cls, block, to_split);
 504         mark_as_copy_of(copy, to_split);
 505         free_reg_of_value(to_split);
 506         use_reg(copy, reg);
 507         sched_add_before(before, copy);
 508
 509         DB((dbg, LEVEL_3,
 510             "Optimistic live-range split %+F move %+F -> %s before %+F (win %f)\n",
 511             copy, to_split, reg->name, before, delta));
 512         return true;
 513 }
 514
 515 /**
 516  * Determine and assign a register for node @p node
 517  */
 518 static void assign_reg(const ir_node *block, ir_node *node,
 519                        unsigned *output_regs)
 520 {
 521         const arch_register_t     *reg;
 522         allocation_info_t         *info;
 523         const arch_register_req_t *req;
 524         reg_pref_t                *reg_prefs;
 525         ir_node                   *in_node;
 526         unsigned                   i;
 527         const unsigned            *allowed_regs;
 528
 529         assert(arch_irn_consider_in_reg_alloc(cls, node));
 530
 531         /* preassigned register? */
 532         reg = arch_get_irn_register(node);
 533         if (reg != NULL) {
 534                 DB((dbg, LEVEL_2, "Preassignment %+F -> %s\n", node, reg->name));
 535                 use_reg(node, reg);
 536                 return;
 537         }
 538
 539         /* give should_be_same boni */
 540         info = get_allocation_info(node);
 541         req  = arch_get_register_req_out(node);
 542
 543         in_node = skip_Proj(node);
 544         if (req->type & arch_register_req_type_should_be_same) {
 545                 float weight = get_block_execfreq(execfreqs, block);
 546                 int   arity  = get_irn_arity(in_node);
 547                 int   i;
 548
 549                 assert(arity <= (int) sizeof(req->other_same) * 8);
 550                 for (i = 0; i < arity; ++i) {
 551                         ir_node               *in;
 552                         const arch_register_t *reg;
 553                         unsigned               r;
 554                         if (!rbitset_is_set(&req->other_same, i))
 555                                 continue;
 556
 557                         in  = get_irn_n(in_node, i);
 558                         reg = arch_get_irn_register(in);
 559                         assert(reg != NULL);
 560                         r = arch_register_get_index(reg);
 561
 562                         /* if the value didn't die here then we should not propagate the
 563                          * should_be_same info */
 564                         if (assignments[r].value == in)
 565                                 continue;
 566
 567                         info->prefs[r] += weight * AFF_SHOULD_BE_SAME;
 568                 }
 569         }
 570
 571         /* create list of register candidates and sort by their preference */
 572         DB((dbg, LEVEL_2, "Candidates for %+F:", node));
 573         reg_prefs = alloca(n_regs * sizeof(reg_prefs[0]));
 574         fill_sort_candidates(reg_prefs, info);
 575         for (i = 0; i < n_regs; ++i) {
 576                 unsigned num = reg_prefs[i].num;
 577                 if (!rbitset_is_set(normal_regs, num))
 578                         continue;
 579
 580                 const arch_register_t *reg = arch_register_for_index(cls, num);
 581                 DB((dbg, LEVEL_2, " %s(%f)", reg->name, reg_prefs[i].pref));
 582         }
 583         DB((dbg, LEVEL_2, "\n"));
 584
 585         allowed_regs = normal_regs;
 586         if (req->type & arch_register_req_type_limited) {
 587                 allowed_regs = req->limited;
 588         }
 589
 590         unsigned r;
 591         for (i = 0; i < n_regs; ++i) {
 592                 r = reg_prefs[i].num;
 593                 if (!rbitset_is_set(allowed_regs, r))
 594                         continue;
 595                 if (assignments[r].value == NULL)
 596                         break;
 597                 if (!is_Phi(node)) {
 598                         float    pref   = reg_prefs[i].pref;
 599                         float    delta  = i+1 < n_regs ? pref - reg_prefs[i+1].pref : 0;
 600                         ir_node *before = skip_Proj(node);
 601                         bool     res    = try_optimistic_split(assignments[r].value, before,
 602                                                                pref, delta,
 603                                                                output_regs);
 604                         if (res)
 605                                 break;
 606                 }
 607         }
 608         if (i >= n_regs) {
 609                 panic("No register left for %+F\n", node);
 610         }
 611
 612         reg = arch_register_for_index(cls, r);
 613         DB((dbg, LEVEL_2, "Assign %+F -> %s\n", node, reg->name));
 614         use_reg(node, reg);
 615 }
 616
 617 /**
 618  * Add an permutation in front of a node and change the assignments
 619  * due to this permutation.
 620  *
 621  * To understand this imagine a permutation like this:
 622  *
 623  * 1 -> 2
 624  * 2 -> 3
 625  * 3 -> 1, 5
 626  * 4 -> 6
 627  * 5
 628  * 6
 629  * 7 -> 7
 630  *
 631  * First we count how many destinations a single value has. At the same time
 632  * we can be sure that each destination register has at most 1 source register
 633  * (it can have 0 which means we don't care what value is in it).
 634  * We ignore all fullfilled permuations (like 7->7)
 635  * In a first pass we create as much copy instructions as possible as they
 636  * are generally cheaper than exchanges. We do this by counting into how many
 637  * destinations a register has to be copied (in the example it's 2 for register
 638  * 3, or 1 for the registers 1,2,4 and 7).
 639  * We can then create a copy into every destination register when the usecount
 640  * of that register is 0 (= noone else needs the value in the register).
 641  *
 642  * After this step we should have cycles left. We implement a cyclic permutation
 643  * of n registers with n-1 transpositions.
 644  *
 645  * @param live_nodes   the set of live nodes, updated due to live range split
 646  * @param before       the node before we add the permutation
 647  * @param permutation  the permutation array indices are the destination
 648  *                     registers, the values in the array are the source
 649  *                     registers.
 650  */
 651 static void permute_values(ir_nodeset_t *live_nodes, ir_node *before,
 652                              unsigned *permutation)
 653 {
 654         unsigned  *n_used = ALLOCANZ(unsigned, n_regs);
 655         ir_node   *block;
 656         unsigned   r;
 657
 658         /* determine how often each source register needs to be read */
 659         for (r = 0; r < n_regs; ++r) {
 660                 unsigned  old_reg = permutation[r];
 661                 ir_node  *value;
 662
 663                 value = assignments[old_reg].value;
 664                 if (value == NULL) {
 665                         /* nothing to do here, reg is not live. Mark it as fixpoint
 666                          * so we ignore it in the next steps */
 667                         permutation[r] = r;
 668                         continue;
 669                 }
 670
 671                 ++n_used[old_reg];
 672         }
 673
 674         block = get_nodes_block(before);
 675
 676         /* step1: create copies where immediately possible */
 677         for (r = 0; r < n_regs; /* empty */) {
 678                 ir_node *copy;
 679                 ir_node *src;
 680                 const arch_register_t *reg;
 681                 unsigned               old_r = permutation[r];
 682
 683                 /* - no need to do anything for fixed points.
 684                    - we can't copy if the value in the dest reg is still needed */
 685                 if (old_r == r || n_used[r] > 0) {
 686                         ++r;
 687                         continue;
 688                 }
 689
 690                 /* create a copy */
 691                 src  = assignments[old_r].value;
 692                 copy = be_new_Copy(cls, block, src);
 693                 sched_add_before(before, copy);
 694                 reg = arch_register_for_index(cls, r);
 695                 DB((dbg, LEVEL_2, "Copy %+F (from %+F, before %+F) -> %s\n",
 696                     copy, src, before, reg->name));
 697                 mark_as_copy_of(copy, src);
 698                 use_reg(copy, reg);
 699
 700                 if (live_nodes != NULL) {
 701                         ir_nodeset_insert(live_nodes, copy);
 702                 }
 703
 704                 /* old register has 1 user less, permutation is resolved */
 705                 assert(arch_register_get_index(arch_get_irn_register(src)) == old_r);
 706                 permutation[r] = r;
 707
 708                 assert(n_used[old_r] > 0);
 709                 --n_used[old_r];
 710                 if (n_used[old_r] == 0) {
 711                         if (live_nodes != NULL) {
 712                                 ir_nodeset_remove(live_nodes, src);
 713                         }
 714                         free_reg_of_value(src);
 715                 }
 716
 717                 /* advance or jump back (if this copy enabled another copy) */
 718                 if (old_r < r && n_used[old_r] == 0) {
 719                         r = old_r;
 720                 } else {
 721                         ++r;
 722                 }
 723         }
 724
 725         /* at this point we only have "cycles" left which we have to resolve with
 726          * perm instructions
 727          * TODO: if we have free registers left, then we should really use copy
 728          * instructions for any cycle longer than 2 registers...
 729          * (this is probably architecture dependent, there might be archs where
 730          *  copies are preferable even for 2-cycles) */
 731
 732         /* create perms with the rest */
 733         for (r = 0; r < n_regs; /* empty */) {
 734                 const arch_register_t *reg;
 735                 unsigned  old_r = permutation[r];
 736                 unsigned  r2;
 737                 ir_node  *in[2];
 738                 ir_node  *perm;
 739                 ir_node  *proj0;
 740                 ir_node  *proj1;
 741
 742                 if (old_r == r) {
 743                         ++r;
 744                         continue;
 745                 }
 746
 747                 /* we shouldn't have copies from 1 value to multiple destinations left*/
 748                 assert(n_used[old_r] == 1);
 749
 750                 /* exchange old_r and r2; after that old_r is a fixed point */
 751                 r2 = permutation[old_r];
 752
 753                 in[0] = assignments[r2].value;
 754                 in[1] = assignments[old_r].value;
 755                 perm = be_new_Perm(cls, block, 2, in);
 756                 sched_add_before(before, perm);
 757                 DB((dbg, LEVEL_2, "Perm %+F (perm %+F,%+F, before %+F)\n",
 758                     perm, in[0], in[1], before));
 759
 760                 proj0 = new_r_Proj(block, perm, get_irn_mode(in[0]), 0);
 761                 mark_as_copy_of(proj0, in[0]);
 762                 reg = arch_register_for_index(cls, old_r);
 763                 use_reg(proj0, reg);
 764
 765                 proj1 = new_r_Proj(block, perm, get_irn_mode(in[1]), 1);
 766                 mark_as_copy_of(proj1, in[1]);
 767                 reg = arch_register_for_index(cls, r2);
 768                 use_reg(proj1, reg);
 769
 770                 /* 1 value is now in the correct register */
 771                 permutation[old_r] = old_r;
 772                 /* the source of r changed to r2 */
 773                 permutation[r] = r2;
 774
 775                 /* if we have reached a fixpoint update data structures */
 776                 if (live_nodes != NULL) {
 777                         ir_nodeset_remove(live_nodes, in[0]);
 778                         ir_nodeset_remove(live_nodes, in[1]);
 779                         ir_nodeset_remove(live_nodes, proj0);
 780                         ir_nodeset_insert(live_nodes, proj1);
 781                 }
 782         }
 783
 784 #ifdef DEBUG_libfirm
 785         /* now we should only have fixpoints left */
 786         for (r = 0; r < n_regs; ++r) {
 787                 assert(permutation[r] == r);
 788         }
 789 #endif
 790 }
 791
 792 /**
 793  * Free regs for values last used.
 794  *
 795  * @param live_nodes   set of live nodes, will be updated
 796  * @param node         the node to consider
 797  */
 798 static void free_last_uses(ir_nodeset_t *live_nodes, ir_node *node)
 799 {
 800         allocation_info_t     *info      = get_allocation_info(node);
 801         const unsigned        *last_uses = &info->last_uses;
 802         int                    arity     = get_irn_arity(node);
 803         int                    i;
 804
 805         for (i = 0; i < arity; ++i) {
 806                 ir_node *op;
 807
 808                 /* check if one operand is the last use */
 809                 if (!rbitset_is_set(last_uses, i))
 810                         continue;
 811
 812                 op = get_irn_n(node, i);
 813                 free_reg_of_value(op);
 814                 ir_nodeset_remove(live_nodes, op);
 815         }
 816 }
 817
 818 /**
 819  * change inputs of a node to the current value (copies/perms)
 820  */
 821 static void rewire_inputs(ir_node *node)
 822 {
 823         int i;
 824         int arity = get_irn_arity(node);
 825
 826         for (i = 0; i < arity; ++i) {
 827                 ir_node           *op = get_irn_n(node, i);
 828                 allocation_info_t *info;
 829
 830                 if (!arch_irn_consider_in_reg_alloc(cls, op))
 831                         continue;
 832
 833                 info = get_allocation_info(op);
 834                 info = get_allocation_info(info->original_value);
 835                 if (info->current_value != op) {
 836                         set_irn_n(node, i, info->current_value);
 837                 }
 838         }
 839 }
 840
 841 /**
 842  * Create a bitset of registers occupied with value living through an
 843  * instruction
 844  */
 845 static void determine_live_through_regs(unsigned *bitset, ir_node *node)
 846 {
 847         const allocation_info_t *info = get_allocation_info(node);
 848         unsigned r;
 849         int i;
 850         int arity;
 851
 852         /* mark all used registers as potentially live-through */
 853         for (r = 0; r < n_regs; ++r) {
 854                 const assignment_t *assignment = &assignments[r];
 855                 if (assignment->value == NULL)
 856                         continue;
 857                 if (!rbitset_is_set(normal_regs, r))
 858                         continue;
 859
 860                 rbitset_set(bitset, r);
 861         }
 862
 863         /* remove registers of value dying at the instruction */
 864         arity = get_irn_arity(node);
 865         for (i = 0; i < arity; ++i) {
 866                 ir_node               *op;
 867                 const arch_register_t *reg;
 868
 869                 if (!rbitset_is_set(&info->last_uses, i))
 870                         continue;
 871
 872                 op  = get_irn_n(node, i);
 873                 reg = arch_get_irn_register(op);
 874                 rbitset_clear(bitset, arch_register_get_index(reg));
 875         }
 876 }
 877
 878 /**
 879  * Enforce constraints at a node by live range splits.
 880  *
 881  * @param  live_nodes  the set of live nodes, might be changed
 882  * @param  node        the current node
 883  */
 884 static void enforce_constraints(ir_nodeset_t *live_nodes, ir_node *node,
 885                                 unsigned *output_regs)
 886 {
 887         int arity = get_irn_arity(node);
 888         int i, dummy, res;
 889         hungarian_problem_t *bp;
 890         unsigned l, r;
 891         unsigned *assignment;
 892
 893         /* construct a list of register occupied by live-through values */
 894         unsigned *live_through_regs = NULL;
 895
 896         /* see if any use constraints are not met */
 897         bool good = true;
 898         for (i = 0; i < arity; ++i) {
 899                 ir_node                   *op = get_irn_n(node, i);
 900                 const arch_register_t     *reg;
 901                 const arch_register_req_t *req;
 902                 const unsigned            *limited;
 903                 unsigned                  r;
 904
 905                 if (!arch_irn_consider_in_reg_alloc(cls, op))
 906                         continue;
 907
 908                 /* are there any limitations for the i'th operand? */
 909                 req = arch_get_register_req(node, i);
 910                 if (!(req->type & arch_register_req_type_limited))
 911                         continue;
 912
 913                 limited = req->limited;
 914                 reg     = arch_get_irn_register(op);
 915                 r       = arch_register_get_index(reg);
 916                 if (!rbitset_is_set(limited, r)) {
 917                         /* found an assignment outside the limited set */
 918                         good = false;
 919                         break;
 920                 }
 921         }
 922
 923         /* is any of the live-throughs using a constrained output register? */
 924         if (get_irn_mode(node) == mode_T) {
 925                 const ir_edge_t *edge;
 926
 927                 foreach_out_edge(node, edge) {
 928                         ir_node *proj = get_edge_src_irn(edge);
 929                         const arch_register_req_t *req;
 930
 931                         if (!arch_irn_consider_in_reg_alloc(cls, proj))
 932                                 continue;
 933
 934                         req = arch_get_register_req_out(proj);
 935                         if (!(req->type & arch_register_req_type_limited))
 936                                 continue;
 937
 938                         if (live_through_regs == NULL) {
 939                                 rbitset_alloca(live_through_regs, n_regs);
 940                                 determine_live_through_regs(live_through_regs, node);
 941                         }
 942
 943                         rbitset_or(output_regs, req->limited, n_regs);
 944                         if (rbitsets_have_common(req->limited, live_through_regs, n_regs)) {
 945                                 good = false;
 946                         }
 947                 }
 948         } else {
 949                 if (arch_irn_consider_in_reg_alloc(cls, node)) {
 950                         const arch_register_req_t *req = arch_get_register_req_out(node);
 951                         if (req->type & arch_register_req_type_limited) {
 952                                 rbitset_alloca(live_through_regs, n_regs);
 953                                 determine_live_through_regs(live_through_regs, node);
 954                                 if (rbitsets_have_common(req->limited, live_through_regs, n_regs)) {
 955                                         good = false;
 956                                         rbitset_or(output_regs, req->limited, n_regs);
 957                                 }
 958                         }
 959                 }
 960         }
 961
 962         if (good)
 963                 return;
 964
 965         /* create these arrays if we haven't yet */
 966         if (live_through_regs == NULL) {
 967                 rbitset_alloca(live_through_regs, n_regs);
 968         }
 969
 970         /* at this point we have to construct a bipartite matching problem to see
 971          * which values should go to which registers
 972          * Note: We're building the matrix in "reverse" - source registers are
 973          *       right, destinations left because this will produce the solution
 974          *       in the format required for permute_values.
 975          */
 976         bp = hungarian_new(n_regs, n_regs, HUNGARIAN_MATCH_PERFECT);
 977
 978         /* add all combinations, then remove not allowed ones */
 979         for (l = 0; l < n_regs; ++l) {
 980                 if (!rbitset_is_set(normal_regs, l)) {
 981                         hungarian_add(bp, l, l, 1);
 982                         continue;
 983                 }
 984
 985                 for (r = 0; r < n_regs; ++r) {
 986                         if (!rbitset_is_set(normal_regs, r))
 987                                 continue;
 988                         /* livethrough values may not use constrainted output registers */
 989                         if (rbitset_is_set(live_through_regs, l)
 990                                         && rbitset_is_set(output_regs, r))
 991                                 continue;
 992
 993                         hungarian_add(bp, r, l, l == r ? 9 : 8);
 994                 }
 995         }
 996
 997         for (i = 0; i < arity; ++i) {
 998                 ir_node                   *op = get_irn_n(node, i);
 999                 const arch_register_t     *reg;
1000                 const arch_register_req_t *req;
1001                 const unsigned            *limited;
1002                 unsigned                   current_reg;
1003
1004                 if (!arch_irn_consider_in_reg_alloc(cls, op))
1005                         continue;
1006
1007                 req = arch_get_register_req(node, i);
1008                 if (!(req->type & arch_register_req_type_limited))
1009                         continue;
1010
1011                 limited     = req->limited;
1012                 reg         = arch_get_irn_register(op);
1013                 current_reg = arch_register_get_index(reg);
1014                 for (r = 0; r < n_regs; ++r) {
1015                         if (rbitset_is_set(limited, r))
1016                                 continue;
1017                         hungarian_remv(bp, r, current_reg);
1018                 }
1019         }
1020
1021         //hungarian_print_costmatrix(bp, 1);
1022         hungarian_prepare_cost_matrix(bp, HUNGARIAN_MODE_MAXIMIZE_UTIL);
1023
1024         assignment = ALLOCAN(unsigned, n_regs);
1025         res = hungarian_solve(bp, (int*) assignment, &dummy, 0);
1026         assert(res == 0);
1027
1028 #if 0
1029         fprintf(stderr, "Swap result:");
1030         for (i = 0; i < (int) n_regs; ++i) {
1031                 fprintf(stderr, " %d", assignment[i]);
1032         }
1033         fprintf(stderr, "\n");
1034 #endif
1035
1036         hungarian_free(bp);
1037
1038         permute_values(live_nodes, node, assignment);
1039 }
1040
1041 /** test wether a node @p n is a copy of the value of node @p of */
1042 static bool is_copy_of(ir_node *value, ir_node *test_value)
1043 {
1044         allocation_info_t *test_info;
1045         allocation_info_t *info;
1046
1047         if (value == test_value)
1048                 return true;
1049
1050         info      = get_allocation_info(value);
1051         test_info = get_allocation_info(test_value);
1052         return test_info->original_value == info->original_value;
1053 }
1054
1055 /**
1056  * find a value in the end-assignment of a basic block
1057  * @returns the index into the assignment array if found
1058  *          -1 if not found
1059  */
1060 static int find_value_in_block_info(block_info_t *info, ir_node *value)
1061 {
1062         unsigned      r;
1063         assignment_t *assignments = info->assignments;
1064         for (r = 0; r < n_regs; ++r) {
1065                 const assignment_t *assignment = &assignments[r];
1066                 ir_node            *a_value    = assignment->value;
1067
1068                 if (a_value == NULL)
1069                         continue;
1070                 if (is_copy_of(a_value, value))
1071                         return (int) r;
1072         }
1073
1074         return -1;
1075 }
1076
1077 /**
1078  * Create the necessary permutations at the end of a basic block to fullfill
1079  * the register assignment for phi-nodes in the next block
1080  */
1081 static void add_phi_permutations(ir_node *block, int p)
1082 {
1083         unsigned  r;
1084         unsigned *permutation;
1085         assignment_t *old_assignments;
1086         bool      need_permutation;
1087         ir_node  *node;
1088         ir_node  *pred = get_Block_cfgpred_block(block, p);
1089
1090         block_info_t *pred_info = get_block_info(pred);
1091
1092         /* predecessor not processed yet? nothing to do */
1093         if (!pred_info->processed)
1094                 return;
1095
1096         permutation = ALLOCAN(unsigned, n_regs);
1097         for (r = 0; r < n_regs; ++r) {
1098                 permutation[r] = r;
1099         }
1100
1101         /* check phi nodes */
1102         need_permutation = false;
1103         node = sched_first(block);
1104         for ( ; is_Phi(node); node = sched_next(node)) {
1105                 const arch_register_t *reg;
1106                 int                    regn;
1107                 int                    a;
1108                 ir_node               *op;
1109
1110                 if (!arch_irn_consider_in_reg_alloc(cls, node))
1111                         continue;
1112
1113                 op = get_Phi_pred(node, p);
1114                 if (!arch_irn_consider_in_reg_alloc(cls, op))
1115                         continue;
1116
1117                 a  = find_value_in_block_info(pred_info, op);
1118                 assert(a >= 0);
1119
1120                 reg  = arch_get_irn_register(node);
1121                 regn = arch_register_get_index(reg);
1122                 if (regn != a) {
1123                         permutation[regn] = a;
1124                         need_permutation  = true;
1125                 }
1126         }
1127
1128         if (need_permutation) {
1129                 /* permute values at end of predecessor */
1130                 old_assignments = assignments;
1131                 assignments     = pred_info->assignments;
1132                 permute_values(NULL, be_get_end_of_block_insertion_point(pred),
1133                                                  permutation);
1134                 assignments = old_assignments;
1135         }
1136
1137         /* change phi nodes to use the copied values */
1138         node = sched_first(block);
1139         for ( ; is_Phi(node); node = sched_next(node)) {
1140                 int      a;
1141                 ir_node *op;
1142
1143                 if (!arch_irn_consider_in_reg_alloc(cls, node))
1144                         continue;
1145
1146                 op = get_Phi_pred(node, p);
1147                 /* no need to do anything for Unknown inputs */
1148                 if (!arch_irn_consider_in_reg_alloc(cls, op))
1149                         continue;
1150
1151                 /* we have permuted all values into the correct registers so we can
1152                    simply query which value occupies the phis register in the
1153                    predecessor */
1154                 a  = arch_register_get_index(arch_get_irn_register(node));
1155                 op = pred_info->assignments[a].value;
1156                 set_Phi_pred(node, p, op);
1157         }
1158 }
1159
1160 /**
1161  * Set preferences for a phis register based on the registers used on the
1162  * phi inputs.
1163  */
1164 static void adapt_phi_prefs(ir_node *phi)
1165 {
1166         int i;
1167         int arity = get_irn_arity(phi);
1168         ir_node           *block = get_nodes_block(phi);
1169         allocation_info_t *info  = get_allocation_info(phi);
1170
1171         for (i = 0; i < arity; ++i) {
1172                 ir_node               *op  = get_irn_n(phi, i);
1173                 const arch_register_t *reg = arch_get_irn_register(op);
1174                 ir_node               *pred;
1175                 ir_node               *pred_block;
1176                 block_info_t          *pred_block_info;
1177                 float                  weight;
1178                 unsigned               r;
1179
1180                 if (reg == NULL)
1181                         continue;
1182                 /* we only give the bonus if the predecessor already has register
1183                  * assigned, otherwise we only see a dummy value
1184                  * and any conclusions about its register are useless */
1185                 pred_block = get_Block_cfgpred_block(block, i);
1186                 pred_block_info = get_block_info(pred_block);
1187                 if (!pred_block_info->processed)
1188                         continue;
1189
1190                 /* give bonus for already assigned register */
1191                 pred   = get_Block_cfgpred_block(block, i);
1192                 weight = get_block_execfreq(execfreqs, pred);
1193                 r      = arch_register_get_index(reg);
1194                 info->prefs[r] += weight * AFF_PHI;
1195         }
1196 }
1197
1198 /**
1199  * After a phi has been assigned a register propagate preference inputs
1200  * to the phi inputs.
1201  */
1202 static void propagate_phi_register(ir_node *phi)
1203 {
1204         int                    i;
1205         ir_node               *block = get_nodes_block(phi);
1206         int                    arity = get_irn_arity(phi);
1207         const arch_register_t *reg   = arch_get_irn_register(phi);
1208         unsigned               r     = arch_register_get_index(reg);
1209
1210         for (i = 0; i < arity; ++i) {
1211                 ir_node           *op   = get_Phi_pred(phi, i);
1212                 allocation_info_t *info = get_allocation_info(op);
1213                 ir_node           *pred;
1214                 float              weight;
1215
1216                 /* already a register assigned? then we can't influence it anyway */
1217                 /* TODO: what about splits which we might still do... */
1218                 if (arch_get_irn_register(op) != NULL)
1219                         continue;
1220
1221                 pred   = get_Block_cfgpred_block(block, i);
1222                 weight = get_block_execfreq(execfreqs, pred);
1223
1224                 /* promote the prefered register */
1225                 info->prefs[r] += AFF_PHI * weight;
1226         }
1227 }
1228
1229 /**
1230  * Walker: assign registers to all nodes of a block that
1231  * need registers from the currently considered register class.
1232  */
1233 static void allocate_coalesce_block(ir_node *block, void *data)
1234 {
1235         int                    i;
1236         ir_nodeset_t           live_nodes;
1237         ir_nodeset_iterator_t  iter;
1238         ir_node               *node, *start;
1239         int                    n_preds;
1240         block_info_t          *block_info;
1241         block_info_t         **pred_block_infos;
1242         ir_node              **phi_ins;
1243         unsigned              *output_regs; /**< collects registers which must not
1244                                                                                      be used for optimistic splits */
1245
1246         (void) data;
1247         DB((dbg, LEVEL_2, "* Block %+F\n", block));
1248
1249         /* clear assignments */
1250         block_info  = get_block_info(block);
1251         assignments = block_info->assignments;
1252
1253         ir_nodeset_init(&live_nodes);
1254
1255         /* gather regalloc infos of predecessor blocks */
1256         n_preds             = get_Block_n_cfgpreds(block);
1257         pred_block_infos    = ALLOCAN(block_info_t*, n_preds);
1258         for (i = 0; i < n_preds; ++i) {
1259                 ir_node      *pred      = get_Block_cfgpred_block(block, i);
1260                 block_info_t *pred_info = get_block_info(pred);
1261                 pred_block_infos[i]     = pred_info;
1262         }
1263
1264         phi_ins = ALLOCAN(ir_node*, n_preds);
1265
1266         /* collect live-in nodes and preassigned values */
1267         be_lv_foreach(lv, block, be_lv_state_in, i) {
1268                 const arch_register_t *reg;
1269                 int                    p;
1270                 bool                   need_phi = false;
1271
1272                 node = be_lv_get_irn(lv, block, i);
1273                 if (!arch_irn_consider_in_reg_alloc(cls, node))
1274                         continue;
1275
1276                 /* check all predecessors for this value, if it is not everywhere the
1277                    same or unknown then we have to construct a phi
1278                    (we collect the potential phi inputs here) */
1279                 for (p = 0; p < n_preds; ++p) {
1280                         block_info_t *pred_info = pred_block_infos[p];
1281
1282                         if (!pred_info->processed) {
1283                                 /* use node for now, it will get fixed later */
1284                                 phi_ins[p] = node;
1285                                 need_phi   = true;
1286                         } else {
1287                                 int a = find_value_in_block_info(pred_info, node);
1288
1289                                 /* must live out of predecessor */
1290                                 assert(a >= 0);
1291                                 phi_ins[p] = pred_info->assignments[a].value;
1292                                 /* different value from last time? then we need a phi */
1293                                 if (p > 0 && phi_ins[p-1] != phi_ins[p]) {
1294                                         need_phi = true;
1295                                 }
1296                         }
1297                 }
1298
1299                 if (need_phi) {
1300                         ir_mode                   *mode = get_irn_mode(node);
1301                         const arch_register_req_t *req  = get_default_req_current_cls();
1302                         ir_node                   *phi;
1303                         int                        i;
1304
1305                         phi = new_r_Phi(block, n_preds, phi_ins, mode);
1306                         be_set_phi_reg_req(phi, req);
1307
1308                         DB((dbg, LEVEL_3, "Create Phi %+F (for %+F) -", phi, node));
1309 #ifdef DEBUG_libfirm
1310                         for (i = 0; i < n_preds; ++i) {
1311                                 DB((dbg, LEVEL_3, " %+F", phi_ins[i]));
1312                         }
1313                         DB((dbg, LEVEL_3, "\n"));
1314 #endif
1315                         mark_as_copy_of(phi, node);
1316                         sched_add_after(block, phi);
1317
1318                         node = phi;
1319                 } else {
1320                         allocation_info_t *info = get_allocation_info(node);
1321                         info->current_value = phi_ins[0];
1322
1323                         /* Grab 1 of the inputs we constructed (might not be the same as
1324                          * "node" as we could see the same copy of the value in all
1325                          * predecessors */
1326                         node = phi_ins[0];
1327                 }
1328
1329                 /* if the node already has a register assigned use it */
1330                 reg = arch_get_irn_register(node);
1331                 if (reg != NULL) {
1332                         /* TODO: consult pred-block infos here. The value could be copied
1333                            away in some/all predecessor blocks. We need to construct
1334                            phi-nodes in this case.
1335                            We even need to construct some Phi_0 like constructs in cases
1336                            where the predecessor allocation is not determined yet. */
1337                         use_reg(node, reg);
1338                 }
1339
1340                 /* remember that this node is live at the beginning of the block */
1341                 ir_nodeset_insert(&live_nodes, node);
1342         }
1343
1344         rbitset_alloca(output_regs, n_regs);
1345
1346         /* handle phis... */
1347         node = sched_first(block);
1348         for ( ; is_Phi(node); node = sched_next(node)) {
1349                 const arch_register_t *reg;
1350
1351                 if (!arch_irn_consider_in_reg_alloc(cls, node))
1352                         continue;
1353
1354                 /* fill in regs already assigned */
1355                 reg = arch_get_irn_register(node);
1356                 if (reg != NULL) {
1357                         use_reg(node, reg);
1358                 } else {
1359                         adapt_phi_prefs(node);
1360                         assign_reg(block, node, output_regs);
1361                         propagate_phi_register(node);
1362                 }
1363         }
1364         start = node;
1365
1366         /* assign regs for live-in values */
1367         foreach_ir_nodeset(&live_nodes, node, iter) {
1368                 const arch_register_t *reg = arch_get_irn_register(node);
1369                 if (reg != NULL)
1370                         continue;
1371
1372                 assign_reg(block, node, output_regs);
1373                 /* shouldn't happen if we color in dominance order */
1374                 assert (!is_Phi(node));
1375         }
1376
1377         /* assign instructions in the block */
1378         for (node = start; !sched_is_end(node); node = sched_next(node)) {
1379                 unsigned r;
1380
1381                 rewire_inputs(node);
1382
1383                 /* enforce use constraints */
1384                 rbitset_clear_all(output_regs, n_regs);
1385                 enforce_constraints(&live_nodes, node, output_regs);
1386                 /* we may not use registers occupied here for optimistic splits */
1387                 for (r = 0; r < n_regs; ++r) {
1388                         if (assignments[r].value != NULL)
1389                                 rbitset_set(output_regs, r);
1390                 }
1391
1392                 rewire_inputs(node);
1393
1394                 /* free registers of values last used at this instruction */
1395                 free_last_uses(&live_nodes, node);
1396
1397                 /* assign output registers */
1398                 /* TODO: 2 phases: first: pre-assigned ones, 2nd real regs */
1399                 if (get_irn_mode(node) == mode_T) {
1400                         const ir_edge_t *edge;
1401                         foreach_out_edge(node, edge) {
1402                                 ir_node *proj = get_edge_src_irn(edge);
1403                                 if (!arch_irn_consider_in_reg_alloc(cls, proj))
1404                                         continue;
1405                                 assign_reg(block, proj, output_regs);
1406                         }
1407                 } else if (arch_irn_consider_in_reg_alloc(cls, node)) {
1408                         assign_reg(block, node, output_regs);
1409                 }
1410         }
1411
1412         ir_nodeset_destroy(&live_nodes);
1413         assignments = NULL;
1414
1415         block_info->processed = true;
1416
1417         /* permute values at end of predecessor blocks in case of phi-nodes */
1418         if (n_preds > 1) {
1419                 int p;
1420                 for (p = 0; p < n_preds; ++p) {
1421                         add_phi_permutations(block, p);
1422                 }
1423         }
1424
1425         /* if we have exactly 1 successor then we might be able to produce phi
1426            copies now */
1427         if (get_irn_n_edges_kind(block, EDGE_KIND_BLOCK) == 1) {
1428                 const ir_edge_t *edge
1429                         = get_irn_out_edge_first_kind(block, EDGE_KIND_BLOCK);
1430                 ir_node      *succ      = get_edge_src_irn(edge);
1431                 int           p         = get_edge_src_pos(edge);
1432                 block_info_t *succ_info = get_block_info(succ);
1433
1434                 if (succ_info->processed) {
1435                         add_phi_permutations(succ, p);
1436                 }
1437         }
1438 }
1439
1440 /**
1441  * Run the register allocator for the current register class.
1442  */
1443 static void be_straight_alloc_cls(void)
1444 {
1445         lv = be_assure_liveness(birg);
1446         be_liveness_assure_sets(lv);
1447         be_liveness_assure_chk(lv);
1448
1449         ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK | IR_RESOURCE_IRN_VISITED);
1450         inc_irg_visited(irg);
1451
1452         DB((dbg, LEVEL_2, "=== Allocating registers of %s ===\n", cls->name));
1453
1454         irg_block_walk_graph(irg, NULL, analyze_block, NULL);
1455         /* we need some dominance pre-order walk to ensure we see all
1456          *  definitions/create copies before we encounter their users */
1457         dom_tree_walk_irg(irg, allocate_coalesce_block, NULL, NULL);
1458
1459         ir_free_resources(irg, IR_RESOURCE_IRN_LINK | IR_RESOURCE_IRN_VISITED);
1460 }
1461
1462 static void dump(int mask, ir_graph *irg, const char *suffix,
1463                  void (*dumper)(ir_graph *, const char *))
1464 {
1465         if(birg->main_env->options->dump_flags & mask)
1466                 be_dump(irg, suffix, dumper);
1467 }
1468
1469 /**
1470  * Run the spiller on the current graph.
1471  */
1472 static void spill(void)
1473 {
1474         /* make sure all nodes show their real register pressure */
1475         BE_TIMER_PUSH(t_ra_constr);
1476         be_pre_spill_prepare_constr(birg, cls);
1477         BE_TIMER_POP(t_ra_constr);
1478
1479         dump(DUMP_RA, irg, "-spillprepare", dump_ir_block_graph_sched);
1480
1481         /* spill */
1482         BE_TIMER_PUSH(t_ra_spill);
1483         be_do_spill(birg, cls);
1484         BE_TIMER_POP(t_ra_spill);
1485
1486         BE_TIMER_PUSH(t_ra_spill_apply);
1487         check_for_memory_operands(irg);
1488         BE_TIMER_POP(t_ra_spill_apply);
1489
1490         dump(DUMP_RA, irg, "-spill", dump_ir_block_graph_sched);
1491 }
1492
1493 /**
1494  * The straight register allocator for a whole procedure.
1495  */
1496 static void be_straight_alloc(be_irg_t *new_birg)
1497 {
1498         const arch_env_t *arch_env = new_birg->main_env->arch_env;
1499         int   n_cls                = arch_env_get_n_reg_class(arch_env);
1500         int   c;
1501
1502         obstack_init(&obst);
1503
1504         birg      = new_birg;
1505         irg       = be_get_birg_irg(birg);
1506         execfreqs = birg->exec_freq;
1507
1508         /* TODO: extract some of the stuff from bechordal allocator, like
1509          * statistics, time measurements, etc. and use them here too */
1510
1511         for (c = 0; c < n_cls; ++c) {
1512                 cls             = arch_env_get_reg_class(arch_env, c);
1513                 default_cls_req = NULL;
1514                 if (arch_register_class_flags(cls) & arch_register_class_flag_manual_ra)
1515                         continue;
1516
1517                 stat_ev_ctx_push_str("regcls", cls->name);
1518
1519                 n_regs      = arch_register_class_n_regs(cls);
1520                 normal_regs = rbitset_malloc(n_regs);
1521                 be_abi_set_non_ignore_regs(birg->abi, cls, normal_regs);
1522
1523                 spill();
1524
1525                 /* verify schedule and register pressure */
1526                 BE_TIMER_PUSH(t_verify);
1527                 if (birg->main_env->options->vrfy_option == BE_VRFY_WARN) {
1528                         be_verify_schedule(birg);
1529                         be_verify_register_pressure(birg, cls, irg);
1530                 } else if (birg->main_env->options->vrfy_option == BE_VRFY_ASSERT) {
1531                         assert(be_verify_schedule(birg) && "Schedule verification failed");
1532                         assert(be_verify_register_pressure(birg, cls, irg)
1533                                 && "Register pressure verification failed");
1534                 }
1535                 BE_TIMER_POP(t_verify);
1536
1537                 BE_TIMER_PUSH(t_ra_color);
1538                 be_straight_alloc_cls();
1539                 BE_TIMER_POP(t_ra_color);
1540
1541                 /* we most probably constructed new Phis so liveness info is invalid
1542                  * now */
1543                 /* TODO: test liveness_introduce */
1544                 be_liveness_invalidate(lv);
1545                 free(normal_regs);
1546
1547                 stat_ev_ctx_pop("regcls");
1548         }
1549
1550         BE_TIMER_PUSH(t_ra_spill_apply);
1551         be_abi_fix_stack_nodes(birg->abi);
1552         BE_TIMER_POP(t_ra_spill_apply);
1553
1554         BE_TIMER_PUSH(t_verify);
1555         if (birg->main_env->options->vrfy_option == BE_VRFY_WARN) {
1556                 be_verify_register_allocation(birg);
1557         } else if (birg->main_env->options->vrfy_option == BE_VRFY_ASSERT) {
1558                 assert(be_verify_register_allocation(birg)
1559                                 && "Register allocation invalid");
1560         }
1561         BE_TIMER_POP(t_verify);
1562
1563         obstack_free(&obst, NULL);
1564 }
1565
1566 /**
1567  * Initializes this module.
1568  */
1569 void be_init_straight_alloc(void)
1570 {
1571         static be_ra_t be_ra_straight = {
1572                 be_straight_alloc,
1573         };
1574
1575         FIRM_DBG_REGISTER(dbg, "firm.be.straightalloc");
1576
1577         be_register_allocator("straight", &be_ra_straight);
1578 }
1579
1580 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_straight_alloc);