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 #include <math.h>
  53
  54 #include "error.h"
  55 #include "execfreq.h"
  56 #include "ircons.h"
  57 #include "irdom.h"
  58 #include "iredges_t.h"
  59 #include "irgraph_t.h"
  60 #include "irgwalk.h"
  61 #include "irnode_t.h"
  62 #include "irprintf.h"
  63 #include "obst.h"
  64 #include "raw_bitset.h"
  65 #include "unionfind.h"
  66 #include "pdeq.h"
  67 #include "hungarian.h"
  68
  69 #include "beabi.h"
  70 #include "bechordal_t.h"
  71 #include "be.h"
  72 #include "beirg.h"
  73 #include "belive_t.h"
  74 #include "bemodule.h"
  75 #include "benode_t.h"
  76 #include "bera.h"
  77 #include "besched.h"
  78 #include "bespill.h"
  79 #include "bespillutil.h"
  80 #include "beverify.h"
  81 #include "beutil.h"
  82
  83 #define USE_FACTOR         1.0f
  84 #define DEF_FACTOR         1.0f
  85 #define NEIGHBOR_FACTOR    0.2f
  86 #define AFF_SHOULD_BE_SAME 0.5f
  87 #define AFF_PHI            1.0f
  88 #define SPLIT_DELTA        1.0f
  89
  90 DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;)
  91
  92 static struct obstack               obst;
  93 static be_irg_t                    *birg;
  94 static ir_graph                    *irg;
  95 static const arch_register_class_t *cls;
  96 static const arch_register_req_t   *default_cls_req;
  97 static be_lv_t                     *lv;
  98 static const ir_exec_freq          *execfreqs;
  99 static unsigned                     n_regs;
 100 static unsigned                    *normal_regs;
 101 static int                         *congruence_classes;
 102 static ir_node                    **block_order;
 103 static int                          n_block_order;
 104
 105 /** currently active assignments (while processing a basic block)
 106  * maps registers to values(their current copies) */
 107 static ir_node **assignments;
 108
 109 /**
 110  * allocation information: last_uses, register preferences
 111  * the information is per firm-node.
 112  */
 113 struct allocation_info_t {
 114         unsigned  last_uses;      /**< bitset indicating last uses (input pos) */
 115         ir_node  *current_value;  /**< copy of the value that should be used */
 116         ir_node  *original_value; /**< for copies point to original value */
 117         float     prefs[0];       /**< register preferences */
 118 };
 119 typedef struct allocation_info_t allocation_info_t;
 120
 121 /** helper datastructure used when sorting register preferences */
 122 struct reg_pref_t {
 123         unsigned num;
 124         float    pref;
 125 };
 126 typedef struct reg_pref_t reg_pref_t;
 127
 128 /** per basic-block information */
 129 struct block_info_t {
 130         bool     processed;       /**< indicate wether block is processed */
 131         ir_node *assignments[0];  /**< register assignments at end of block */
 132 };
 133 typedef struct block_info_t block_info_t;
 134
 135 /**
 136  * Get the allocation info for a node.
 137  * The info is allocated on the first visit of a node.
 138  */
 139 static allocation_info_t *get_allocation_info(ir_node *node)
 140 {
 141         allocation_info_t *info = get_irn_link(node);
 142         if (info == NULL) {
 143                 info = OALLOCFZ(&obst, allocation_info_t, prefs, n_regs);
 144                 info->current_value  = node;
 145                 info->original_value = node;
 146                 set_irn_link(node, info);
 147         }
 148
 149         return info;
 150 }
 151
 152 /**
 153  * Get allocation information for a basic block
 154  */
 155 static block_info_t *get_block_info(ir_node *block)
 156 {
 157         block_info_t *info = get_irn_link(block);
 158
 159         assert(is_Block(block));
 160         if (info == NULL) {
 161                 info = OALLOCFZ(&obst, block_info_t, assignments, n_regs);
 162                 set_irn_link(block, info);
 163         }
 164
 165         return info;
 166 }
 167
 168 /**
 169  * Get default register requirement for the current register class
 170  */
 171 static const arch_register_req_t *get_default_req_current_cls(void)
 172 {
 173         if (default_cls_req == NULL) {
 174                 struct obstack      *obst = get_irg_obstack(irg);
 175                 arch_register_req_t *req  = OALLOCZ(obst, arch_register_req_t);
 176
 177                 req->type = arch_register_req_type_normal;
 178                 req->cls  = cls;
 179
 180                 default_cls_req = req;
 181         }
 182         return default_cls_req;
 183 }
 184
 185 /**
 186  * Link the allocation info of a node to a copy.
 187  * Afterwards, both nodes uses the same allocation info.
 188  * Copy must not have an allocation info assigned yet.
 189  *
 190  * @param copy   the node that gets the allocation info assigned
 191  * @param value  the original node
 192  */
 193 static void mark_as_copy_of(ir_node *copy, ir_node *value)
 194 {
 195         ir_node           *original;
 196         allocation_info_t *info      = get_allocation_info(value);
 197         allocation_info_t *copy_info = get_allocation_info(copy);
 198
 199         /* find original value */
 200         original = info->original_value;
 201         if (original != value) {
 202                 info = get_allocation_info(original);
 203         }
 204
 205         assert(info->original_value == original);
 206         info->current_value = copy;
 207
 208         /* the copy should not be linked to something else yet */
 209         assert(copy_info->original_value == copy);
 210         copy_info->original_value = original;
 211
 212         /* copy over allocation preferences */
 213         memcpy(copy_info->prefs, info->prefs, n_regs * sizeof(copy_info->prefs[0]));
 214 }
 215
 216 /**
 217  * Calculate the penalties for every register on a node and its live neighbors.
 218  *
 219  * @param live_nodes  the set of live nodes at the current position, may be NULL
 220  * @param penalty     the penalty to subtract from
 221  * @param limited     a raw bitset containing the limited set for the node
 222  * @param node        the node
 223  */
 224 static void give_penalties_for_limits(const ir_nodeset_t *live_nodes,
 225                                       float penalty, const unsigned* limited,
 226                                       ir_node *node)
 227 {
 228         ir_nodeset_iterator_t iter;
 229         unsigned              r;
 230         allocation_info_t     *info = get_allocation_info(node);
 231         ir_node               *neighbor;
 232
 233         /* give penalty for all forbidden regs */
 234         for (r = 0; r < n_regs; ++r) {
 235                 if (rbitset_is_set(limited, r))
 236                         continue;
 237
 238                 info->prefs[r] -= penalty;
 239         }
 240
 241         /* all other live values should get a penalty for allowed regs */
 242         if (live_nodes == NULL)
 243                 return;
 244
 245         /* TODO: reduce penalty if there are multiple allowed registers... */
 246         penalty *= NEIGHBOR_FACTOR;
 247         foreach_ir_nodeset(live_nodes, neighbor, iter) {
 248                 allocation_info_t *neighbor_info;
 249
 250                 /* TODO: if op is used on multiple inputs we might not do a
 251                  * continue here */
 252                 if (neighbor == node)
 253                         continue;
 254
 255                 neighbor_info = get_allocation_info(neighbor);
 256                 for (r = 0; r < n_regs; ++r) {
 257                         if (!rbitset_is_set(limited, r))
 258                                 continue;
 259
 260                         neighbor_info->prefs[r] -= penalty;
 261                 }
 262         }
 263 }
 264
 265 /**
 266  * Calculate the preferences of a definition for the current register class.
 267  * If the definition uses a limited set of registers, reduce the preferences
 268  * for the limited register on the node and its neighbors.
 269  *
 270  * @param live_nodes  the set of live nodes at the current node
 271  * @param weight      the weight
 272  * @param node        the current node
 273  */
 274 static void check_defs(const ir_nodeset_t *live_nodes, float weight,
 275                        ir_node *node)
 276 {
 277         const arch_register_req_t *req;
 278
 279         if (get_irn_mode(node) == mode_T) {
 280                 const ir_edge_t *edge;
 281                 foreach_out_edge(node, edge) {
 282                         ir_node *proj = get_edge_src_irn(edge);
 283                         check_defs(live_nodes, weight, proj);
 284                 }
 285                 return;
 286         }
 287
 288         if (!arch_irn_consider_in_reg_alloc(cls, node))
 289                 return;
 290
 291         req = arch_get_register_req_out(node);
 292         if (req->type & arch_register_req_type_limited) {
 293                 const unsigned *limited = req->limited;
 294                 float           penalty = weight * DEF_FACTOR;
 295                 give_penalties_for_limits(live_nodes, penalty, limited, node);
 296         }
 297
 298         if (req->type & arch_register_req_type_should_be_same) {
 299                 ir_node           *insn  = skip_Proj(node);
 300                 allocation_info_t *info  = get_allocation_info(node);
 301                 int                arity = get_irn_arity(insn);
 302                 int                i;
 303
 304                 float factor = 1.0f / rbitset_popcnt(&req->other_same, arity);
 305                 for (i = 0; i < arity; ++i) {
 306                         ir_node           *op;
 307                         unsigned           r;
 308                         allocation_info_t *op_info;
 309
 310                         if (!rbitset_is_set(&req->other_same, i))
 311                                 continue;
 312
 313                         op = get_irn_n(insn, i);
 314
 315                         /* if we the value at the should_be_same input doesn't die at the
 316                          * node, then it is no use to propagate the constraints (since a
 317                          * copy will emerge anyway) */
 318                         if (ir_nodeset_contains(live_nodes, op))
 319                                 continue;
 320
 321                         op_info = get_allocation_info(op);
 322                         for (r = 0; r < n_regs; ++r) {
 323                                 op_info->prefs[r] += info->prefs[r] * factor;
 324                         }
 325                 }
 326         }
 327 }
 328
 329 /**
 330  * Walker: Runs an a block calculates the preferences for any
 331  * node and every register from the considered register class.
 332  */
 333 static void analyze_block(ir_node *block, void *data)
 334 {
 335         float         weight = get_block_execfreq(execfreqs, block);
 336         ir_nodeset_t  live_nodes;
 337         ir_node      *node;
 338         (void) data;
 339
 340         ir_nodeset_init(&live_nodes);
 341         be_liveness_end_of_block(lv, cls, block, &live_nodes);
 342
 343         sched_foreach_reverse(block, node) {
 344                 allocation_info_t *info;
 345                 int                i;
 346                 int                arity;
 347
 348                 if (is_Phi(node))
 349                         break;
 350
 351                 check_defs(&live_nodes, weight, node);
 352
 353                 /* mark last uses */
 354                 arity = get_irn_arity(node);
 355
 356                 /* the allocation info node currently only uses 1 unsigned value
 357                    to mark last used inputs. So we will fail for a node with more than
 358                    32 inputs. */
 359                 if (arity >= (int) sizeof(unsigned) * 8) {
 360                         panic("Node with more than %d inputs not supported yet",
 361                                         (int) sizeof(unsigned) * 8);
 362                 }
 363
 364                 info = get_allocation_info(node);
 365                 for (i = 0; i < arity; ++i) {
 366                         ir_node *op = get_irn_n(node, i);
 367                         if (!arch_irn_consider_in_reg_alloc(cls, op))
 368                                 continue;
 369
 370                         /* last usage of a value? */
 371                         if (!ir_nodeset_contains(&live_nodes, op)) {
 372                                 rbitset_set(&info->last_uses, i);
 373                         }
 374                 }
 375
 376                 be_liveness_transfer(cls, node, &live_nodes);
 377
 378                 /* update weights based on usage constraints */
 379                 for (i = 0; i < arity; ++i) {
 380                         const arch_register_req_t *req;
 381                         const unsigned            *limited;
 382                         ir_node                   *op = get_irn_n(node, i);
 383
 384                         if (!arch_irn_consider_in_reg_alloc(cls, op))
 385                                 continue;
 386
 387                         req = arch_get_register_req(node, i);
 388                         if (!(req->type & arch_register_req_type_limited))
 389                                 continue;
 390
 391                         limited = req->limited;
 392                         give_penalties_for_limits(&live_nodes, weight * USE_FACTOR, limited,
 393                                                   op);
 394                 }
 395         }
 396
 397         ir_nodeset_destroy(&live_nodes);
 398 }
 399
 400 static void congruence_def(ir_nodeset_t *live_nodes, ir_node *node)
 401 {
 402         if (get_irn_mode(node) == mode_T) {
 403                 const ir_edge_t *edge;
 404                 foreach_out_edge(node, edge) {
 405                         ir_node *def = get_edge_src_irn(edge);
 406                         congruence_def(live_nodes, def);
 407                 }
 408                 return;
 409         }
 410
 411         if (!arch_irn_consider_in_reg_alloc(cls, node))
 412                 return;
 413
 414         /* should be same constraint? */
 415         const arch_register_req_t *req = arch_get_register_req_out(node);
 416         if (req->type & arch_register_req_type_should_be_same) {
 417                 ir_node *insn  = skip_Proj(node);
 418                 int      arity = get_irn_arity(insn);
 419                 int      i;
 420                 unsigned node_idx = get_irn_idx(node);
 421                 node_idx          = uf_find(congruence_classes, node_idx);
 422
 423                 for (i = 0; i < arity; ++i) {
 424                         ir_node               *live;
 425                         ir_node               *op;
 426                         int                    op_idx;
 427                         ir_nodeset_iterator_t  iter;
 428
 429                         if (!rbitset_is_set(&req->other_same, i))
 430                                 continue;
 431
 432                         op     = get_irn_n(insn, i);
 433                         op_idx = get_irn_idx(op);
 434                         op_idx = uf_find(congruence_classes, op_idx);
 435
 436                         /* do we interfere with the value */
 437                         bool interferes = false;
 438                         foreach_ir_nodeset(live_nodes, live, iter) {
 439                                 int lv_idx = get_irn_idx(live);
 440                                 lv_idx     = uf_find(congruence_classes, lv_idx);
 441                                 if (lv_idx == op_idx) {
 442                                         interferes = true;
 443                                         break;
 444                                 }
 445                         }
 446                         /* don't put in same affinity class if we interfere */
 447                         if (interferes)
 448                                 continue;
 449
 450                         node_idx = uf_union(congruence_classes, node_idx, op_idx);
 451                         DB((dbg, LEVEL_3, "Merge %+F and %+F congruence classes\n",
 452                             node, op));
 453                         /* one should_be_same is enough... */
 454                         break;
 455                 }
 456         }
 457 }
 458
 459 static void create_congurence_class(ir_node *block, void *data)
 460 {
 461         ir_nodeset_t  live_nodes;
 462         ir_node      *node;
 463
 464         (void) data;
 465         ir_nodeset_init(&live_nodes);
 466         be_liveness_end_of_block(lv, cls, block, &live_nodes);
 467
 468         /* check should be same constraints */
 469         sched_foreach_reverse(block, node) {
 470                 if (is_Phi(node))
 471                         break;
 472
 473                 congruence_def(&live_nodes, node);
 474                 be_liveness_transfer(cls, node, &live_nodes);
 475         }
 476
 477         /* check phi congruence classes */
 478         sched_foreach_reverse_from(node, node) {
 479                 int i;
 480                 int arity;
 481                 int node_idx;
 482                 assert(is_Phi(node));
 483
 484                 if (!arch_irn_consider_in_reg_alloc(cls, node))
 485                         continue;
 486
 487                 node_idx = get_irn_idx(node);
 488                 node_idx = uf_find(congruence_classes, node_idx);
 489
 490                 arity = get_irn_arity(node);
 491                 for (i = 0; i < arity; ++i) {
 492                         ir_nodeset_iterator_t  iter;
 493                         ir_node *live;
 494                         ir_node *phi;
 495                         ir_node *op     = get_Phi_pred(node, i);
 496                         int      op_idx = get_irn_idx(op);
 497                         op_idx = uf_find(congruence_classes, op_idx);
 498
 499                         /* do we interfere with the value */
 500                         bool interferes = false;
 501                         foreach_ir_nodeset(&live_nodes, live, iter) {
 502                                 int lv_idx = get_irn_idx(live);
 503                                 lv_idx     = uf_find(congruence_classes, lv_idx);
 504                                 if (lv_idx == op_idx) {
 505                                         interferes = true;
 506                                         break;
 507                                 }
 508                         }
 509                         /* don't put in same affinity class if we interfere */
 510                         if (interferes)
 511                                 continue;
 512                         /* any other phi has the same input? */
 513                         sched_foreach(block, phi) {
 514                                 ir_node *oop;
 515                                 int      oop_idx;
 516                                 if (!is_Phi(phi))
 517                                         break;
 518                                 if (!arch_irn_consider_in_reg_alloc(cls, phi))
 519                                         continue;
 520                                 oop = get_Phi_pred(phi, i);
 521                                 if (oop == op)
 522                                         continue;
 523                                 oop_idx = get_irn_idx(oop);
 524                                 oop_idx = uf_find(congruence_classes, oop_idx);
 525                                 if (oop_idx == op_idx) {
 526                                         interferes = true;
 527                                         break;
 528                                 }
 529                         }
 530                         if (interferes)
 531                                 continue;
 532
 533                         node_idx = uf_union(congruence_classes, node_idx, op_idx);
 534                         DB((dbg, LEVEL_3, "Merge %+F and %+F congruence classes\n",
 535                             node, op));
 536                 }
 537         }
 538 }
 539
 540 static void merge_congruence_prefs(ir_node *node, void *data)
 541 {
 542         allocation_info_t *info;
 543         allocation_info_t *head_info;
 544         unsigned node_idx = get_irn_idx(node);
 545         unsigned node_set = uf_find(congruence_classes, node_idx);
 546         unsigned r;
 547
 548         (void) data;
 549
 550         /* head of congruence class or not in any class */
 551         if (node_set == node_idx)
 552                 return;
 553
 554         if (!arch_irn_consider_in_reg_alloc(cls, node))
 555                 return;
 556
 557         head_info = get_allocation_info(get_idx_irn(irg, node_set));
 558         info      = get_allocation_info(node);
 559
 560         for (r = 0; r < n_regs; ++r) {
 561                 head_info->prefs[r] += info->prefs[r];
 562         }
 563 }
 564
 565 static void set_congruence_prefs(ir_node *node, void *data)
 566 {
 567         allocation_info_t *info;
 568         allocation_info_t *head_info;
 569         unsigned node_idx = get_irn_idx(node);
 570         unsigned node_set = uf_find(congruence_classes, node_idx);
 571
 572         (void) data;
 573
 574         /* head of congruence class or not in any class */
 575         if (node_set == node_idx)
 576                 return;
 577
 578         if (!arch_irn_consider_in_reg_alloc(cls, node))
 579                 return;
 580
 581         head_info = get_allocation_info(get_idx_irn(irg, node_set));
 582         info      = get_allocation_info(node);
 583
 584         memcpy(info->prefs, head_info->prefs, n_regs * sizeof(info->prefs[0]));
 585 }
 586
 587 static void combine_congruence_classes(void)
 588 {
 589         size_t n = get_irg_last_idx(irg);
 590         congruence_classes = XMALLOCN(int, n);
 591         uf_init(congruence_classes, n);
 592
 593         /* create congruence classes */
 594         irg_block_walk_graph(irg, create_congurence_class, NULL, NULL);
 595         /* merge preferences */
 596         irg_walk_graph(irg, merge_congruence_prefs, NULL, NULL);
 597         irg_walk_graph(irg, set_congruence_prefs, NULL, NULL);
 598 }
 599
 600
 601
 602
 603
 604 /**
 605  * Assign register reg to the given node.
 606  *
 607  * @param node  the node
 608  * @param reg   the register
 609  */
 610 static void use_reg(ir_node *node, const arch_register_t *reg)
 611 {
 612         unsigned r = arch_register_get_index(reg);
 613         assignments[r] = node;
 614         arch_set_irn_register(node, reg);
 615 }
 616
 617 static void free_reg_of_value(ir_node *node)
 618 {
 619         const arch_register_t *reg;
 620         unsigned               r;
 621
 622         if (!arch_irn_consider_in_reg_alloc(cls, node))
 623                 return;
 624
 625         reg        = arch_get_irn_register(node);
 626         r          = arch_register_get_index(reg);
 627         /* assignment->value may be NULL if a value is used at 2 inputs
 628            so it gets freed twice. */
 629         assert(assignments[r] == node || assignments[r] == NULL);
 630         assignments[r] = NULL;
 631 }
 632
 633 /**
 634  * Compare two register preferences in decreasing order.
 635  */
 636 static int compare_reg_pref(const void *e1, const void *e2)
 637 {
 638         const reg_pref_t *rp1 = (const reg_pref_t*) e1;
 639         const reg_pref_t *rp2 = (const reg_pref_t*) e2;
 640         if (rp1->pref < rp2->pref)
 641                 return 1;
 642         if (rp1->pref > rp2->pref)
 643                 return -1;
 644         return 0;
 645 }
 646
 647 static void fill_sort_candidates(reg_pref_t *regprefs,
 648                                  const allocation_info_t *info)
 649 {
 650         unsigned r;
 651
 652         for (r = 0; r < n_regs; ++r) {
 653                 float pref = info->prefs[r];
 654                 regprefs[r].num  = r;
 655                 regprefs[r].pref = pref;
 656         }
 657         /* TODO: use a stable sort here to avoid unnecessary register jumping */
 658         qsort(regprefs, n_regs, sizeof(regprefs[0]), compare_reg_pref);
 659 }
 660
 661 static bool try_optimistic_split(ir_node *to_split, ir_node *before,
 662                                  float pref, float pref_delta,
 663                                  unsigned *output_regs)
 664 {
 665         const arch_register_t *reg;
 666         ir_node               *original_insn;
 667         ir_node               *block;
 668         ir_node               *copy;
 669         unsigned               r;
 670         unsigned               i;
 671         allocation_info_t     *info = get_allocation_info(to_split);
 672         reg_pref_t            *prefs;
 673         float                  delta;
 674         float                  split_threshold;
 675
 676         (void) pref;
 677
 678         /* stupid hack: don't optimisticallt split don't spill nodes...
 679          * (so we don't split away the values produced because of
 680          *  must_be_different constraints) */
 681         original_insn = skip_Proj(info->original_value);
 682         if (arch_irn_get_flags(original_insn) & arch_irn_flags_dont_spill)
 683                 return false;
 684
 685         /* find the best free position where we could move to */
 686         prefs = ALLOCAN(reg_pref_t, n_regs);
 687         fill_sort_candidates(prefs, info);
 688         for (i = 0; i < n_regs; ++i) {
 689                 r = prefs[i].num;
 690                 if (!rbitset_is_set(normal_regs, r))
 691                         continue;
 692                 if (rbitset_is_set(output_regs, r))
 693                         continue;
 694                 if (assignments[r] == NULL)
 695                         break;
 696         }
 697         if (i >= n_regs) {
 698                 return false;
 699         }
 700         /* TODO: use execfreq somehow... */
 701         block = get_nodes_block(before);
 702         delta = pref_delta + prefs[i].pref;
 703         split_threshold = get_block_execfreq(execfreqs, block) * SPLIT_DELTA;
 704         if (delta < split_threshold) {
 705                 DB((dbg, LEVEL_3, "Not doing optimistical split, win %f too low\n",
 706                     delta));
 707                 return false;
 708         }
 709
 710         reg   = arch_register_for_index(cls, r);
 711         copy = be_new_Copy(cls, block, to_split);
 712         mark_as_copy_of(copy, to_split);
 713         free_reg_of_value(to_split);
 714         use_reg(copy, reg);
 715         sched_add_before(before, copy);
 716
 717         DB((dbg, LEVEL_3,
 718             "Optimistic live-range split %+F move %+F -> %s before %+F (win %f)\n",
 719             copy, to_split, reg->name, before, delta));
 720         return true;
 721 }
 722
 723 /**
 724  * Determine and assign a register for node @p node
 725  */
 726 static void assign_reg(const ir_node *block, ir_node *node,
 727                        unsigned *output_regs)
 728 {
 729         const arch_register_t     *reg;
 730         allocation_info_t         *info;
 731         const arch_register_req_t *req;
 732         reg_pref_t                *reg_prefs;
 733         ir_node                   *in_node;
 734         unsigned                   i;
 735         const unsigned            *allowed_regs;
 736         unsigned                   r;
 737
 738         assert(arch_irn_consider_in_reg_alloc(cls, node));
 739
 740         /* preassigned register? */
 741         reg = arch_get_irn_register(node);
 742         if (reg != NULL) {
 743                 DB((dbg, LEVEL_2, "Preassignment %+F -> %s\n", node, reg->name));
 744                 use_reg(node, reg);
 745                 return;
 746         }
 747
 748         /* give should_be_same boni */
 749         info = get_allocation_info(node);
 750         req  = arch_get_register_req_out(node);
 751
 752         in_node = skip_Proj(node);
 753         if (req->type & arch_register_req_type_should_be_same) {
 754                 float weight = get_block_execfreq(execfreqs, block);
 755                 int   arity  = get_irn_arity(in_node);
 756                 int   i;
 757
 758                 assert(arity <= (int) sizeof(req->other_same) * 8);
 759                 for (i = 0; i < arity; ++i) {
 760                         ir_node               *in;
 761                         const arch_register_t *reg;
 762                         unsigned               r;
 763                         if (!rbitset_is_set(&req->other_same, i))
 764                                 continue;
 765
 766                         in  = get_irn_n(in_node, i);
 767                         reg = arch_get_irn_register(in);
 768                         assert(reg != NULL);
 769                         r = arch_register_get_index(reg);
 770
 771                         /* if the value didn't die here then we should not propagate the
 772                          * should_be_same info */
 773                         if (assignments[r] == in)
 774                                 continue;
 775
 776                         info->prefs[r] += weight * AFF_SHOULD_BE_SAME;
 777                 }
 778         }
 779
 780         /* create list of register candidates and sort by their preference */
 781         DB((dbg, LEVEL_2, "Candidates for %+F:", node));
 782         reg_prefs = alloca(n_regs * sizeof(reg_prefs[0]));
 783         fill_sort_candidates(reg_prefs, info);
 784         for (i = 0; i < n_regs; ++i) {
 785                 unsigned num = reg_prefs[i].num;
 786                 const arch_register_t *reg;
 787
 788                 if (!rbitset_is_set(normal_regs, num))
 789                         continue;
 790
 791                 reg = arch_register_for_index(cls, num);
 792                 DB((dbg, LEVEL_2, " %s(%f)", reg->name, reg_prefs[i].pref));
 793         }
 794         DB((dbg, LEVEL_2, "\n"));
 795
 796         allowed_regs = normal_regs;
 797         if (req->type & arch_register_req_type_limited) {
 798                 allowed_regs = req->limited;
 799         }
 800
 801         for (i = 0; i < n_regs; ++i) {
 802                 r = reg_prefs[i].num;
 803                 if (!rbitset_is_set(allowed_regs, r))
 804                         continue;
 805                 if (assignments[r] == NULL)
 806                         break;
 807                 if (!is_Phi(node)) {
 808                         float    pref   = reg_prefs[i].pref;
 809                         float    delta  = i+1 < n_regs ? pref - reg_prefs[i+1].pref : 0;
 810                         ir_node *before = skip_Proj(node);
 811                         bool     res    = try_optimistic_split(assignments[r], before,
 812                                                                pref, delta,
 813                                                                output_regs);
 814                         if (res)
 815                                 break;
 816                 }
 817         }
 818         if (i >= n_regs) {
 819                 panic("No register left for %+F\n", node);
 820         }
 821
 822         reg = arch_register_for_index(cls, r);
 823         DB((dbg, LEVEL_2, "Assign %+F -> %s\n", node, reg->name));
 824         use_reg(node, reg);
 825 }
 826
 827 /**
 828  * Add an permutation in front of a node and change the assignments
 829  * due to this permutation.
 830  *
 831  * To understand this imagine a permutation like this:
 832  *
 833  * 1 -> 2
 834  * 2 -> 3
 835  * 3 -> 1, 5
 836  * 4 -> 6
 837  * 5
 838  * 6
 839  * 7 -> 7
 840  *
 841  * First we count how many destinations a single value has. At the same time
 842  * we can be sure that each destination register has at most 1 source register
 843  * (it can have 0 which means we don't care what value is in it).
 844  * We ignore all fullfilled permuations (like 7->7)
 845  * In a first pass we create as much copy instructions as possible as they
 846  * are generally cheaper than exchanges. We do this by counting into how many
 847  * destinations a register has to be copied (in the example it's 2 for register
 848  * 3, or 1 for the registers 1,2,4 and 7).
 849  * We can then create a copy into every destination register when the usecount
 850  * of that register is 0 (= noone else needs the value in the register).
 851  *
 852  * After this step we should have cycles left. We implement a cyclic permutation
 853  * of n registers with n-1 transpositions.
 854  *
 855  * @param live_nodes   the set of live nodes, updated due to live range split
 856  * @param before       the node before we add the permutation
 857  * @param permutation  the permutation array indices are the destination
 858  *                     registers, the values in the array are the source
 859  *                     registers.
 860  */
 861 static void permute_values(ir_nodeset_t *live_nodes, ir_node *before,
 862                              unsigned *permutation)
 863 {
 864         unsigned  *n_used = ALLOCANZ(unsigned, n_regs);
 865         ir_node   *block;
 866         unsigned   r;
 867
 868         /* determine how often each source register needs to be read */
 869         for (r = 0; r < n_regs; ++r) {
 870                 unsigned  old_reg = permutation[r];
 871                 ir_node  *value;
 872
 873                 value = assignments[old_reg];
 874                 if (value == NULL) {
 875                         /* nothing to do here, reg is not live. Mark it as fixpoint
 876                          * so we ignore it in the next steps */
 877                         permutation[r] = r;
 878                         continue;
 879                 }
 880
 881                 ++n_used[old_reg];
 882         }
 883
 884         block = get_nodes_block(before);
 885
 886         /* step1: create copies where immediately possible */
 887         for (r = 0; r < n_regs; /* empty */) {
 888                 ir_node *copy;
 889                 ir_node *src;
 890                 const arch_register_t *reg;
 891                 unsigned               old_r = permutation[r];
 892
 893                 /* - no need to do anything for fixed points.
 894                    - we can't copy if the value in the dest reg is still needed */
 895                 if (old_r == r || n_used[r] > 0) {
 896                         ++r;
 897                         continue;
 898                 }
 899
 900                 /* create a copy */
 901                 src  = assignments[old_r];
 902                 copy = be_new_Copy(cls, block, src);
 903                 sched_add_before(before, copy);
 904                 reg = arch_register_for_index(cls, r);
 905                 DB((dbg, LEVEL_2, "Copy %+F (from %+F, before %+F) -> %s\n",
 906                     copy, src, before, reg->name));
 907                 mark_as_copy_of(copy, src);
 908                 use_reg(copy, reg);
 909
 910                 if (live_nodes != NULL) {
 911                         ir_nodeset_insert(live_nodes, copy);
 912                 }
 913
 914                 /* old register has 1 user less, permutation is resolved */
 915                 assert(arch_register_get_index(arch_get_irn_register(src)) == old_r);
 916                 permutation[r] = r;
 917
 918                 assert(n_used[old_r] > 0);
 919                 --n_used[old_r];
 920                 if (n_used[old_r] == 0) {
 921                         if (live_nodes != NULL) {
 922                                 ir_nodeset_remove(live_nodes, src);
 923                         }
 924                         free_reg_of_value(src);
 925                 }
 926
 927                 /* advance or jump back (if this copy enabled another copy) */
 928                 if (old_r < r && n_used[old_r] == 0) {
 929                         r = old_r;
 930                 } else {
 931                         ++r;
 932                 }
 933         }
 934
 935         /* at this point we only have "cycles" left which we have to resolve with
 936          * perm instructions
 937          * TODO: if we have free registers left, then we should really use copy
 938          * instructions for any cycle longer than 2 registers...
 939          * (this is probably architecture dependent, there might be archs where
 940          *  copies are preferable even for 2-cycles) */
 941
 942         /* create perms with the rest */
 943         for (r = 0; r < n_regs; /* empty */) {
 944                 const arch_register_t *reg;
 945                 unsigned  old_r = permutation[r];
 946                 unsigned  r2;
 947                 ir_node  *in[2];
 948                 ir_node  *perm;
 949                 ir_node  *proj0;
 950                 ir_node  *proj1;
 951
 952                 if (old_r == r) {
 953                         ++r;
 954                         continue;
 955                 }
 956
 957                 /* we shouldn't have copies from 1 value to multiple destinations left*/
 958                 assert(n_used[old_r] == 1);
 959
 960                 /* exchange old_r and r2; after that old_r is a fixed point */
 961                 r2 = permutation[old_r];
 962
 963                 in[0] = assignments[r2];
 964                 in[1] = assignments[old_r];
 965                 perm = be_new_Perm(cls, block, 2, in);
 966                 sched_add_before(before, perm);
 967                 DB((dbg, LEVEL_2, "Perm %+F (perm %+F,%+F, before %+F)\n",
 968                     perm, in[0], in[1], before));
 969
 970                 proj0 = new_r_Proj(block, perm, get_irn_mode(in[0]), 0);
 971                 mark_as_copy_of(proj0, in[0]);
 972                 reg = arch_register_for_index(cls, old_r);
 973                 use_reg(proj0, reg);
 974
 975                 proj1 = new_r_Proj(block, perm, get_irn_mode(in[1]), 1);
 976                 mark_as_copy_of(proj1, in[1]);
 977                 reg = arch_register_for_index(cls, r2);
 978                 use_reg(proj1, reg);
 979
 980                 /* 1 value is now in the correct register */
 981                 permutation[old_r] = old_r;
 982                 /* the source of r changed to r2 */
 983                 permutation[r] = r2;
 984
 985                 /* if we have reached a fixpoint update data structures */
 986                 if (live_nodes != NULL) {
 987                         ir_nodeset_remove(live_nodes, in[0]);
 988                         ir_nodeset_remove(live_nodes, in[1]);
 989                         ir_nodeset_remove(live_nodes, proj0);
 990                         ir_nodeset_insert(live_nodes, proj1);
 991                 }
 992         }
 993
 994 #ifdef DEBUG_libfirm
 995         /* now we should only have fixpoints left */
 996         for (r = 0; r < n_regs; ++r) {
 997                 assert(permutation[r] == r);
 998         }
 999 #endif
1000 }
1001
1002 /**
1003  * Free regs for values last used.
1004  *
1005  * @param live_nodes   set of live nodes, will be updated
1006  * @param node         the node to consider
1007  */
1008 static void free_last_uses(ir_nodeset_t *live_nodes, ir_node *node)
1009 {
1010         allocation_info_t     *info      = get_allocation_info(node);
1011         const unsigned        *last_uses = &info->last_uses;
1012         int                    arity     = get_irn_arity(node);
1013         int                    i;
1014
1015         for (i = 0; i < arity; ++i) {
1016                 ir_node *op;
1017
1018                 /* check if one operand is the last use */
1019                 if (!rbitset_is_set(last_uses, i))
1020                         continue;
1021
1022                 op = get_irn_n(node, i);
1023                 free_reg_of_value(op);
1024                 ir_nodeset_remove(live_nodes, op);
1025         }
1026 }
1027
1028 /**
1029  * change inputs of a node to the current value (copies/perms)
1030  */
1031 static void rewire_inputs(ir_node *node)
1032 {
1033         int i;
1034         int arity = get_irn_arity(node);
1035
1036         for (i = 0; i < arity; ++i) {
1037                 ir_node           *op = get_irn_n(node, i);
1038                 allocation_info_t *info;
1039
1040                 if (!arch_irn_consider_in_reg_alloc(cls, op))
1041                         continue;
1042
1043                 info = get_allocation_info(op);
1044                 info = get_allocation_info(info->original_value);
1045                 if (info->current_value != op) {
1046                         set_irn_n(node, i, info->current_value);
1047                 }
1048         }
1049 }
1050
1051 /**
1052  * Create a bitset of registers occupied with value living through an
1053  * instruction
1054  */
1055 static void determine_live_through_regs(unsigned *bitset, ir_node *node)
1056 {
1057         const allocation_info_t *info = get_allocation_info(node);
1058         unsigned r;
1059         int i;
1060         int arity;
1061
1062         /* mark all used registers as potentially live-through */
1063         for (r = 0; r < n_regs; ++r) {
1064                 if (assignments[r] == NULL)
1065                         continue;
1066                 if (!rbitset_is_set(normal_regs, r))
1067                         continue;
1068
1069                 rbitset_set(bitset, r);
1070         }
1071
1072         /* remove registers of value dying at the instruction */
1073         arity = get_irn_arity(node);
1074         for (i = 0; i < arity; ++i) {
1075                 ir_node               *op;
1076                 const arch_register_t *reg;
1077
1078                 if (!rbitset_is_set(&info->last_uses, i))
1079                         continue;
1080
1081                 op  = get_irn_n(node, i);
1082                 reg = arch_get_irn_register(op);
1083                 rbitset_clear(bitset, arch_register_get_index(reg));
1084         }
1085 }
1086
1087 /**
1088  * Enforce constraints at a node by live range splits.
1089  *
1090  * @param  live_nodes  the set of live nodes, might be changed
1091  * @param  node        the current node
1092  */
1093 static void enforce_constraints(ir_nodeset_t *live_nodes, ir_node *node,
1094                                 unsigned *output_regs)
1095 {
1096         int arity = get_irn_arity(node);
1097         int i, res;
1098         hungarian_problem_t *bp;
1099         unsigned l, r;
1100         unsigned *assignment;
1101
1102         /* construct a list of register occupied by live-through values */
1103         unsigned *live_through_regs = NULL;
1104
1105         /* see if any use constraints are not met */
1106         bool good = true;
1107         for (i = 0; i < arity; ++i) {
1108                 ir_node                   *op = get_irn_n(node, i);
1109                 const arch_register_t     *reg;
1110                 const arch_register_req_t *req;
1111                 const unsigned            *limited;
1112                 unsigned                  r;
1113
1114                 if (!arch_irn_consider_in_reg_alloc(cls, op))
1115                         continue;
1116
1117                 /* are there any limitations for the i'th operand? */
1118                 req = arch_get_register_req(node, i);
1119                 if (!(req->type & arch_register_req_type_limited))
1120                         continue;
1121
1122                 limited = req->limited;
1123                 reg     = arch_get_irn_register(op);
1124                 r       = arch_register_get_index(reg);
1125                 if (!rbitset_is_set(limited, r)) {
1126                         /* found an assignment outside the limited set */
1127                         good = false;
1128                         break;
1129                 }
1130         }
1131
1132         /* is any of the live-throughs using a constrained output register? */
1133         if (get_irn_mode(node) == mode_T) {
1134                 const ir_edge_t *edge;
1135
1136                 foreach_out_edge(node, edge) {
1137                         ir_node *proj = get_edge_src_irn(edge);
1138                         const arch_register_req_t *req;
1139
1140                         if (!arch_irn_consider_in_reg_alloc(cls, proj))
1141                                 continue;
1142
1143                         req = arch_get_register_req_out(proj);
1144                         if (!(req->type & arch_register_req_type_limited))
1145                                 continue;
1146
1147                         if (live_through_regs == NULL) {
1148                                 rbitset_alloca(live_through_regs, n_regs);
1149                                 determine_live_through_regs(live_through_regs, node);
1150                         }
1151
1152                         rbitset_or(output_regs, req->limited, n_regs);
1153                         if (rbitsets_have_common(req->limited, live_through_regs, n_regs)) {
1154                                 good = false;
1155                         }
1156                 }
1157         } else {
1158                 if (arch_irn_consider_in_reg_alloc(cls, node)) {
1159                         const arch_register_req_t *req = arch_get_register_req_out(node);
1160                         if (req->type & arch_register_req_type_limited) {
1161                                 rbitset_alloca(live_through_regs, n_regs);
1162                                 determine_live_through_regs(live_through_regs, node);
1163                                 if (rbitsets_have_common(req->limited, live_through_regs, n_regs)) {
1164                                         good = false;
1165                                         rbitset_or(output_regs, req->limited, n_regs);
1166                                 }
1167                         }
1168                 }
1169         }
1170
1171         if (good)
1172                 return;
1173
1174         /* create these arrays if we haven't yet */
1175         if (live_through_regs == NULL) {
1176                 rbitset_alloca(live_through_regs, n_regs);
1177         }
1178
1179         /* at this point we have to construct a bipartite matching problem to see
1180          * which values should go to which registers
1181          * Note: We're building the matrix in "reverse" - source registers are
1182          *       right, destinations left because this will produce the solution
1183          *       in the format required for permute_values.
1184          */
1185         bp = hungarian_new(n_regs, n_regs, HUNGARIAN_MATCH_PERFECT);
1186
1187         /* add all combinations, then remove not allowed ones */
1188         for (l = 0; l < n_regs; ++l) {
1189                 if (!rbitset_is_set(normal_regs, l)) {
1190                         hungarian_add(bp, l, l, 1);
1191                         continue;
1192                 }
1193
1194                 for (r = 0; r < n_regs; ++r) {
1195                         if (!rbitset_is_set(normal_regs, r))
1196                                 continue;
1197                         /* livethrough values may not use constrainted output registers */
1198                         if (rbitset_is_set(live_through_regs, l)
1199                                         && rbitset_is_set(output_regs, r))
1200                                 continue;
1201
1202                         hungarian_add(bp, r, l, l == r ? 9 : 8);
1203                 }
1204         }
1205
1206         for (i = 0; i < arity; ++i) {
1207                 ir_node                   *op = get_irn_n(node, i);
1208                 const arch_register_t     *reg;
1209                 const arch_register_req_t *req;
1210                 const unsigned            *limited;
1211                 unsigned                   current_reg;
1212
1213                 if (!arch_irn_consider_in_reg_alloc(cls, op))
1214                         continue;
1215
1216                 req = arch_get_register_req(node, i);
1217                 if (!(req->type & arch_register_req_type_limited))
1218                         continue;
1219
1220                 limited     = req->limited;
1221                 reg         = arch_get_irn_register(op);
1222                 current_reg = arch_register_get_index(reg);
1223                 for (r = 0; r < n_regs; ++r) {
1224                         if (rbitset_is_set(limited, r))
1225                                 continue;
1226                         hungarian_remv(bp, r, current_reg);
1227                 }
1228         }
1229
1230         //hungarian_print_cost_matrix(bp, 1);
1231         hungarian_prepare_cost_matrix(bp, HUNGARIAN_MODE_MAXIMIZE_UTIL);
1232
1233         assignment = ALLOCAN(unsigned, n_regs);
1234         res = hungarian_solve(bp, (int*) assignment, NULL, 0);
1235         assert(res == 0);
1236
1237 #if 0
1238         fprintf(stderr, "Swap result:");
1239         for (i = 0; i < (int) n_regs; ++i) {
1240                 fprintf(stderr, " %d", assignment[i]);
1241         }
1242         fprintf(stderr, "\n");
1243 #endif
1244
1245         hungarian_free(bp);
1246
1247         permute_values(live_nodes, node, assignment);
1248 }
1249
1250 /** test wether a node @p n is a copy of the value of node @p of */
1251 static bool is_copy_of(ir_node *value, ir_node *test_value)
1252 {
1253         allocation_info_t *test_info;
1254         allocation_info_t *info;
1255
1256         if (value == test_value)
1257                 return true;
1258
1259         info      = get_allocation_info(value);
1260         test_info = get_allocation_info(test_value);
1261         return test_info->original_value == info->original_value;
1262 }
1263
1264 /**
1265  * find a value in the end-assignment of a basic block
1266  * @returns the index into the assignment array if found
1267  *          -1 if not found
1268  */
1269 static int find_value_in_block_info(block_info_t *info, ir_node *value)
1270 {
1271         unsigned   r;
1272         ir_node  **assignments = info->assignments;
1273         for (r = 0; r < n_regs; ++r) {
1274                 ir_node *a_value = assignments[r];
1275
1276                 if (a_value == NULL)
1277                         continue;
1278                 if (is_copy_of(a_value, value))
1279                         return (int) r;
1280         }
1281
1282         return -1;
1283 }
1284
1285 /**
1286  * Create the necessary permutations at the end of a basic block to fullfill
1287  * the register assignment for phi-nodes in the next block
1288  */
1289 static void add_phi_permutations(ir_node *block, int p)
1290 {
1291         unsigned   r;
1292         unsigned  *permutation;
1293         ir_node  **old_assignments;
1294         bool       need_permutation;
1295         ir_node   *node;
1296         ir_node   *pred = get_Block_cfgpred_block(block, p);
1297
1298         block_info_t *pred_info = get_block_info(pred);
1299
1300         /* predecessor not processed yet? nothing to do */
1301         if (!pred_info->processed)
1302                 return;
1303
1304         permutation = ALLOCAN(unsigned, n_regs);
1305         for (r = 0; r < n_regs; ++r) {
1306                 permutation[r] = r;
1307         }
1308
1309         /* check phi nodes */
1310         need_permutation = false;
1311         node = sched_first(block);
1312         for ( ; is_Phi(node); node = sched_next(node)) {
1313                 const arch_register_t *reg;
1314                 int                    regn;
1315                 int                    a;
1316                 ir_node               *op;
1317
1318                 if (!arch_irn_consider_in_reg_alloc(cls, node))
1319                         continue;
1320
1321                 op = get_Phi_pred(node, p);
1322                 if (!arch_irn_consider_in_reg_alloc(cls, op))
1323                         continue;
1324
1325                 a  = find_value_in_block_info(pred_info, op);
1326                 assert(a >= 0);
1327
1328                 reg  = arch_get_irn_register(node);
1329                 regn = arch_register_get_index(reg);
1330                 if (regn != a) {
1331                         permutation[regn] = a;
1332                         need_permutation  = true;
1333                 }
1334         }
1335
1336         if (need_permutation) {
1337                 /* permute values at end of predecessor */
1338                 old_assignments = assignments;
1339                 assignments     = pred_info->assignments;
1340                 permute_values(NULL, be_get_end_of_block_insertion_point(pred),
1341                                                  permutation);
1342                 assignments = old_assignments;
1343         }
1344
1345         /* change phi nodes to use the copied values */
1346         node = sched_first(block);
1347         for ( ; is_Phi(node); node = sched_next(node)) {
1348                 int      a;
1349                 ir_node *op;
1350
1351                 if (!arch_irn_consider_in_reg_alloc(cls, node))
1352                         continue;
1353
1354                 op = get_Phi_pred(node, p);
1355                 /* no need to do anything for Unknown inputs */
1356                 if (!arch_irn_consider_in_reg_alloc(cls, op))
1357                         continue;
1358
1359                 /* we have permuted all values into the correct registers so we can
1360                    simply query which value occupies the phis register in the
1361                    predecessor */
1362                 a  = arch_register_get_index(arch_get_irn_register(node));
1363                 op = pred_info->assignments[a];
1364                 set_Phi_pred(node, p, op);
1365         }
1366 }
1367
1368 /**
1369  * Set preferences for a phis register based on the registers used on the
1370  * phi inputs.
1371  */
1372 static void adapt_phi_prefs(ir_node *phi)
1373 {
1374         int i;
1375         int arity = get_irn_arity(phi);
1376         ir_node           *block = get_nodes_block(phi);
1377         allocation_info_t *info  = get_allocation_info(phi);
1378
1379         for (i = 0; i < arity; ++i) {
1380                 ir_node               *op  = get_irn_n(phi, i);
1381                 const arch_register_t *reg = arch_get_irn_register(op);
1382                 ir_node               *pred_block;
1383                 block_info_t          *pred_block_info;
1384                 float                  weight;
1385                 unsigned               r;
1386
1387                 if (reg == NULL)
1388                         continue;
1389                 /* we only give the bonus if the predecessor already has registers
1390                  * assigned, otherwise we only see a dummy value
1391                  * and any conclusions about its register are useless */
1392                 pred_block = get_Block_cfgpred_block(block, i);
1393                 pred_block_info = get_block_info(pred_block);
1394                 if (!pred_block_info->processed)
1395                         continue;
1396
1397                 /* give bonus for already assigned register */
1398                 weight = get_block_execfreq(execfreqs, pred_block);
1399                 r      = arch_register_get_index(reg);
1400                 info->prefs[r] += weight * AFF_PHI;
1401         }
1402 }
1403
1404 /**
1405  * After a phi has been assigned a register propagate preference inputs
1406  * to the phi inputs.
1407  */
1408 static void propagate_phi_register(ir_node *phi, unsigned r)
1409 {
1410         int                    i;
1411         ir_node               *block = get_nodes_block(phi);
1412         int                    arity = get_irn_arity(phi);
1413
1414         for (i = 0; i < arity; ++i) {
1415                 ir_node           *op         = get_Phi_pred(phi, i);
1416                 allocation_info_t *info       = get_allocation_info(op);
1417                 ir_node           *pred_block = get_Block_cfgpred_block(block, i);
1418                 float              weight
1419                         = get_block_execfreq(execfreqs, pred_block) * AFF_PHI;
1420
1421                 if (info->prefs[r] >= weight)
1422                         continue;
1423
1424                 /* promote the prefered register */
1425                 info->prefs[r] = AFF_PHI * weight;
1426                 if (is_Phi(op))
1427                         propagate_phi_register(op, r);
1428         }
1429 }
1430
1431 static void assign_phi_registers(ir_node *block)
1432 {
1433         int                  n_phis = 0;
1434         int                  n;
1435         int                  res;
1436         int                 *assignment;
1437         ir_node             *node;
1438         hungarian_problem_t *bp;
1439
1440         /* count phi nodes */
1441         sched_foreach(block, node) {
1442                 if (!is_Phi(node))
1443                         break;
1444                 if (!arch_irn_consider_in_reg_alloc(cls, node))
1445                         continue;
1446                 ++n_phis;
1447         }
1448
1449         if (n_phis == 0)
1450                 return;
1451
1452         /* build a bipartite matching problem for all phi nodes */
1453         bp = hungarian_new(n_phis, n_regs, HUNGARIAN_MATCH_PERFECT);
1454         n  = 0;
1455         sched_foreach(block, node) {
1456                 unsigned r;
1457
1458                 allocation_info_t *info;
1459                 if (!is_Phi(node))
1460                         break;
1461                 if (!arch_irn_consider_in_reg_alloc(cls, node))
1462                         continue;
1463
1464                 /* give boni for predecessor colorings */
1465                 adapt_phi_prefs(node);
1466                 /* add stuff to bipartite problem */
1467                 info = get_allocation_info(node);
1468                 DB((dbg, LEVEL_3, "Prefs for %+F: ", node));
1469                 for (r = 0; r < n_regs; ++r) {
1470                         float costs;
1471
1472                         if (!rbitset_is_set(normal_regs, r))
1473                                 continue;
1474
1475                         costs = info->prefs[r];
1476                         costs = costs < 0 ? -logf(-costs+1) : logf(costs+1);
1477                         costs *= 100;
1478                         costs += 10000;
1479                         hungarian_add(bp, n, r, costs);
1480                         DB((dbg, LEVEL_3, " %s(%f)", arch_register_for_index(cls, r)->name,
1481                                                 info->prefs[r]));
1482                 }
1483                 DB((dbg, LEVEL_3, "\n"));
1484                 ++n;
1485         }
1486
1487         //hungarian_print_cost_matrix(bp, 7);
1488         hungarian_prepare_cost_matrix(bp, HUNGARIAN_MODE_MAXIMIZE_UTIL);
1489
1490         assignment = ALLOCAN(int, n_regs);
1491         res        = hungarian_solve(bp, assignment, NULL, 0);
1492         assert(res == 0);
1493
1494         /* apply results */
1495         n = 0;
1496         sched_foreach(block, node) {
1497                 unsigned               r;
1498                 const arch_register_t *reg;
1499
1500                 if (!is_Phi(node))
1501                         break;
1502                 if (!arch_irn_consider_in_reg_alloc(cls, node))
1503                         continue;
1504
1505                 r   = assignment[n++];
1506                 assert(rbitset_is_set(normal_regs, r));
1507                 reg = arch_register_for_index(cls, r);
1508                 DB((dbg, LEVEL_2, "Assign %+F -> %s\n", node, reg->name));
1509                 use_reg(node, reg);
1510
1511                 /* adapt preferences for phi inputs */
1512                 propagate_phi_register(node, r);
1513         }
1514 }
1515
1516 /**
1517  * Walker: assign registers to all nodes of a block that
1518  * need registers from the currently considered register class.
1519  */
1520 static void allocate_coalesce_block(ir_node *block, void *data)
1521 {
1522         int                    i;
1523         ir_nodeset_t           live_nodes;
1524         ir_nodeset_iterator_t  iter;
1525         ir_node               *node;
1526         int                    n_preds;
1527         block_info_t          *block_info;
1528         block_info_t         **pred_block_infos;
1529         ir_node              **phi_ins;
1530         unsigned              *output_regs; /**< collects registers which must not
1531                                                                                      be used for optimistic splits */
1532
1533         (void) data;
1534         DB((dbg, LEVEL_2, "* Block %+F\n", block));
1535
1536         /* clear assignments */
1537         block_info  = get_block_info(block);
1538         assignments = block_info->assignments;
1539
1540         ir_nodeset_init(&live_nodes);
1541
1542         /* gather regalloc infos of predecessor blocks */
1543         n_preds             = get_Block_n_cfgpreds(block);
1544         pred_block_infos    = ALLOCAN(block_info_t*, n_preds);
1545         for (i = 0; i < n_preds; ++i) {
1546                 ir_node      *pred      = get_Block_cfgpred_block(block, i);
1547                 block_info_t *pred_info = get_block_info(pred);
1548                 pred_block_infos[i]     = pred_info;
1549         }
1550
1551         phi_ins = ALLOCAN(ir_node*, n_preds);
1552
1553         /* collect live-in nodes and preassigned values */
1554         be_lv_foreach(lv, block, be_lv_state_in, i) {
1555                 const arch_register_t *reg;
1556                 int                    p;
1557                 bool                   need_phi = false;
1558
1559                 node = be_lv_get_irn(lv, block, i);
1560                 if (!arch_irn_consider_in_reg_alloc(cls, node))
1561                         continue;
1562
1563                 /* check all predecessors for this value, if it is not everywhere the
1564                    same or unknown then we have to construct a phi
1565                    (we collect the potential phi inputs here) */
1566                 for (p = 0; p < n_preds; ++p) {
1567                         block_info_t *pred_info = pred_block_infos[p];
1568
1569                         if (!pred_info->processed) {
1570                                 /* use node for now, it will get fixed later */
1571                                 phi_ins[p] = node;
1572                                 need_phi   = true;
1573                         } else {
1574                                 int a = find_value_in_block_info(pred_info, node);
1575
1576                                 /* must live out of predecessor */
1577                                 assert(a >= 0);
1578                                 phi_ins[p] = pred_info->assignments[a];
1579                                 /* different value from last time? then we need a phi */
1580                                 if (p > 0 && phi_ins[p-1] != phi_ins[p]) {
1581                                         need_phi = true;
1582                                 }
1583                         }
1584                 }
1585
1586                 if (need_phi) {
1587                         ir_mode                   *mode = get_irn_mode(node);
1588                         const arch_register_req_t *req  = get_default_req_current_cls();
1589                         ir_node                   *phi;
1590                         int                        i;
1591
1592                         phi = new_r_Phi(block, n_preds, phi_ins, mode);
1593                         be_set_phi_reg_req(phi, req);
1594
1595                         DB((dbg, LEVEL_3, "Create Phi %+F (for %+F) -", phi, node));
1596 #ifdef DEBUG_libfirm
1597                         for (i = 0; i < n_preds; ++i) {
1598                                 DB((dbg, LEVEL_3, " %+F", phi_ins[i]));
1599                         }
1600                         DB((dbg, LEVEL_3, "\n"));
1601 #endif
1602                         mark_as_copy_of(phi, node);
1603                         sched_add_after(block, phi);
1604
1605                         node = phi;
1606                 } else {
1607                         allocation_info_t *info = get_allocation_info(node);
1608                         info->current_value = phi_ins[0];
1609
1610                         /* Grab 1 of the inputs we constructed (might not be the same as
1611                          * "node" as we could see the same copy of the value in all
1612                          * predecessors */
1613                         node = phi_ins[0];
1614                 }
1615
1616                 /* if the node already has a register assigned use it */
1617                 reg = arch_get_irn_register(node);
1618                 if (reg != NULL) {
1619                         /* TODO: consult pred-block infos here. The value could be copied
1620                            away in some/all predecessor blocks. We need to construct
1621                            phi-nodes in this case.
1622                            We even need to construct some Phi_0 like constructs in cases
1623                            where the predecessor allocation is not determined yet. */
1624                         use_reg(node, reg);
1625                 }
1626
1627                 /* remember that this node is live at the beginning of the block */
1628                 ir_nodeset_insert(&live_nodes, node);
1629         }
1630
1631         rbitset_alloca(output_regs, n_regs);
1632
1633         /* handle phis... */
1634         assign_phi_registers(block);
1635
1636         /* assign regs for live-in values */
1637         foreach_ir_nodeset(&live_nodes, node, iter) {
1638                 const arch_register_t *reg = arch_get_irn_register(node);
1639                 if (reg != NULL)
1640                         continue;
1641
1642                 assign_reg(block, node, output_regs);
1643                 /* shouldn't happen if we color in dominance order */
1644                 assert (!is_Phi(node));
1645         }
1646
1647         /* assign instructions in the block */
1648         sched_foreach(block, node) {
1649                 unsigned r;
1650
1651                 /* phis are already assigned */
1652                 if (is_Phi(node))
1653                         continue;
1654
1655                 rewire_inputs(node);
1656
1657                 /* enforce use constraints */
1658                 rbitset_clear_all(output_regs, n_regs);
1659                 enforce_constraints(&live_nodes, node, output_regs);
1660                 /* we may not use registers occupied here for optimistic splits */
1661                 for (r = 0; r < n_regs; ++r) {
1662                         if (assignments[r] != NULL)
1663                                 rbitset_set(output_regs, r);
1664                 }
1665
1666                 rewire_inputs(node);
1667
1668                 /* free registers of values last used at this instruction */
1669                 free_last_uses(&live_nodes, node);
1670
1671                 /* assign output registers */
1672                 /* TODO: 2 phases: first: pre-assigned ones, 2nd real regs */
1673                 if (get_irn_mode(node) == mode_T) {
1674                         const ir_edge_t *edge;
1675                         foreach_out_edge(node, edge) {
1676                                 ir_node *proj = get_edge_src_irn(edge);
1677                                 if (!arch_irn_consider_in_reg_alloc(cls, proj))
1678                                         continue;
1679                                 assign_reg(block, proj, output_regs);
1680                         }
1681                 } else if (arch_irn_consider_in_reg_alloc(cls, node)) {
1682                         assign_reg(block, node, output_regs);
1683                 }
1684         }
1685
1686         ir_nodeset_destroy(&live_nodes);
1687         assignments = NULL;
1688
1689         block_info->processed = true;
1690
1691         /* permute values at end of predecessor blocks in case of phi-nodes */
1692         if (n_preds > 1) {
1693                 int p;
1694                 for (p = 0; p < n_preds; ++p) {
1695                         add_phi_permutations(block, p);
1696                 }
1697         }
1698
1699         /* if we have exactly 1 successor then we might be able to produce phi
1700            copies now */
1701         if (get_irn_n_edges_kind(block, EDGE_KIND_BLOCK) == 1) {
1702                 const ir_edge_t *edge
1703                         = get_irn_out_edge_first_kind(block, EDGE_KIND_BLOCK);
1704                 ir_node      *succ      = get_edge_src_irn(edge);
1705                 int           p         = get_edge_src_pos(edge);
1706                 block_info_t *succ_info = get_block_info(succ);
1707
1708                 if (succ_info->processed) {
1709                         add_phi_permutations(succ, p);
1710                 }
1711         }
1712 }
1713
1714 typedef struct block_costs_t block_costs_t;
1715 struct block_costs_t {
1716         float costs;   /**< costs of the block */
1717         int   dfs_num; /**< depth first search number (to detect backedges) */
1718 };
1719
1720 static int cmp_block_costs(const void *d1, const void *d2)
1721 {
1722         const ir_node       * const *block1 = d1;
1723         const ir_node       * const *block2 = d2;
1724         const block_costs_t *info1  = get_irn_link(*block1);
1725         const block_costs_t *info2  = get_irn_link(*block2);
1726         return QSORT_CMP(info2->costs, info1->costs);
1727 }
1728
1729 static void determine_block_order(void)
1730 {
1731         int i;
1732         ir_node **blocklist = be_get_cfgpostorder(irg);
1733         int       n_blocks  = ARR_LEN(blocklist);
1734         int       dfs_num   = 0;
1735
1736         /* clear block links... */
1737         for (i = 0; i < n_blocks; ++i) {
1738                 ir_node *block = blocklist[i];
1739                 set_irn_link(block, NULL);
1740         }
1741
1742         /* walk blocks in reverse postorder, the costs for each block are the
1743          * sum of the costs of its predecessors (excluding the costs on backedges
1744          * which we can't determine) */
1745         for (i = n_blocks-1; i >= 0; --i) {
1746                 block_costs_t *cost_info;
1747                 ir_node *block = blocklist[i];
1748
1749                 float execfreq   = get_block_execfreq(execfreqs, block);
1750                 float costs      = execfreq;
1751                 int   n_cfgpreds = get_Block_n_cfgpreds(block);
1752                 int   p;
1753                 for (p = 0; p < n_cfgpreds; ++p) {
1754                         ir_node       *pred_block = get_Block_cfgpred_block(block, p);
1755                         block_costs_t *pred_costs = get_irn_link(pred_block);
1756                         /* we don't have any info for backedges */
1757                         if (pred_costs == NULL)
1758                                 continue;
1759                         costs += pred_costs->costs;
1760                 }
1761
1762                 cost_info          = OALLOCZ(&obst, block_costs_t);
1763                 cost_info->costs   = costs;
1764                 cost_info->dfs_num = dfs_num++;
1765                 set_irn_link(block, cost_info);
1766         }
1767
1768         /* sort array by block costs */
1769         qsort(blocklist, n_blocks, sizeof(blocklist[0]), cmp_block_costs);
1770
1771         ir_reserve_resources(irg, IR_RESOURCE_BLOCK_VISITED);
1772         inc_irg_block_visited(irg);
1773
1774         pdeq     *worklist = new_pdeq();
1775         ir_node **order    = XMALLOCN(ir_node*, n_blocks);
1776         int       order_p  = 0;
1777         for (i = 0; i < n_blocks; ++i) {
1778                 ir_node       *block = blocklist[i];
1779                 if (Block_block_visited(block))
1780                         continue;
1781
1782                 /* continually add predecessors with highest costs to worklist
1783                  * (without using backedges) */
1784                 do {
1785                         block_costs_t *info       = get_irn_link(block);
1786                         ir_node       *best_pred  = NULL;
1787                         float          best_costs = -1;
1788                         int            n_cfgpred  = get_Block_n_cfgpreds(block);
1789                         int            i;
1790
1791                         pdeq_putr(worklist, block);
1792                         mark_Block_block_visited(block);
1793                         for (i = 0; i < n_cfgpred; ++i) {
1794                                 ir_node       *pred_block = get_Block_cfgpred_block(block, i);
1795                                 block_costs_t *pred_info  = get_irn_link(pred_block);
1796
1797                                 /* ignore backedges */
1798                                 if (pred_info->dfs_num > info->dfs_num)
1799                                         continue;
1800
1801                                 if (info->costs > best_costs) {
1802                                         best_costs = info->costs;
1803                                         best_pred  = pred_block;
1804                                 }
1805                         }
1806                         block = best_pred;
1807                 } while(block != NULL && !Block_block_visited(block));
1808
1809                 /* now put all nodes in the worklist in our final order */
1810                 while (!pdeq_empty(worklist)) {
1811                         ir_node *pblock = pdeq_getr(worklist);
1812                         assert(order_p < n_blocks);
1813                         order[order_p++] = pblock;
1814                 }
1815         }
1816         assert(order_p == n_blocks);
1817         del_pdeq(worklist);
1818
1819         ir_free_resources(irg, IR_RESOURCE_BLOCK_VISITED);
1820
1821         DEL_ARR_F(blocklist);
1822
1823         obstack_free(&obst, NULL);
1824         obstack_init(&obst);
1825
1826         block_order   = order;
1827         n_block_order = n_blocks;
1828 }
1829
1830 /**
1831  * Run the register allocator for the current register class.
1832  */
1833 static void be_straight_alloc_cls(void)
1834 {
1835         int i;
1836
1837         lv = be_assure_liveness(birg);
1838         be_liveness_assure_sets(lv);
1839         be_liveness_assure_chk(lv);
1840
1841         ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK);
1842
1843         DB((dbg, LEVEL_2, "=== Allocating registers of %s ===\n", cls->name));
1844
1845         be_clear_links(irg);
1846         irg_block_walk_graph(irg, NULL, analyze_block, NULL);
1847         combine_congruence_classes();
1848
1849         for (i = 0; i < n_block_order; ++i) {
1850                 ir_node *block = block_order[i];
1851                 allocate_coalesce_block(block, NULL);
1852         }
1853
1854         ir_free_resources(irg, IR_RESOURCE_IRN_LINK);
1855 }
1856
1857 static void dump(int mask, ir_graph *irg, const char *suffix,
1858                  void (*dumper)(ir_graph *, const char *))
1859 {
1860         if(birg->main_env->options->dump_flags & mask)
1861                 be_dump(irg, suffix, dumper);
1862 }
1863
1864 /**
1865  * Run the spiller on the current graph.
1866  */
1867 static void spill(void)
1868 {
1869         /* make sure all nodes show their real register pressure */
1870         BE_TIMER_PUSH(t_ra_constr);
1871         be_pre_spill_prepare_constr(birg, cls);
1872         BE_TIMER_POP(t_ra_constr);
1873
1874         dump(DUMP_RA, irg, "-spillprepare", dump_ir_block_graph_sched);
1875
1876         /* spill */
1877         BE_TIMER_PUSH(t_ra_spill);
1878         be_do_spill(birg, cls);
1879         BE_TIMER_POP(t_ra_spill);
1880
1881         BE_TIMER_PUSH(t_ra_spill_apply);
1882         check_for_memory_operands(irg);
1883         BE_TIMER_POP(t_ra_spill_apply);
1884
1885         dump(DUMP_RA, irg, "-spill", dump_ir_block_graph_sched);
1886 }
1887
1888 /**
1889  * The straight register allocator for a whole procedure.
1890  */
1891 static void be_straight_alloc(be_irg_t *new_birg)
1892 {
1893         const arch_env_t *arch_env = new_birg->main_env->arch_env;
1894         int   n_cls                = arch_env_get_n_reg_class(arch_env);
1895         int   c;
1896
1897         obstack_init(&obst);
1898
1899         birg      = new_birg;
1900         irg       = be_get_birg_irg(birg);
1901         execfreqs = birg->exec_freq;
1902
1903         /* determine a good coloring order */
1904         determine_block_order();
1905
1906         for (c = 0; c < n_cls; ++c) {
1907                 cls             = arch_env_get_reg_class(arch_env, c);
1908                 default_cls_req = NULL;
1909                 if (arch_register_class_flags(cls) & arch_register_class_flag_manual_ra)
1910                         continue;
1911
1912                 stat_ev_ctx_push_str("regcls", cls->name);
1913
1914                 n_regs      = arch_register_class_n_regs(cls);
1915                 normal_regs = rbitset_malloc(n_regs);
1916                 be_abi_set_non_ignore_regs(birg->abi, cls, normal_regs);
1917
1918                 spill();
1919
1920                 /* verify schedule and register pressure */
1921                 BE_TIMER_PUSH(t_verify);
1922                 if (birg->main_env->options->vrfy_option == BE_VRFY_WARN) {
1923                         be_verify_schedule(birg);
1924                         be_verify_register_pressure(birg, cls, irg);
1925                 } else if (birg->main_env->options->vrfy_option == BE_VRFY_ASSERT) {
1926                         assert(be_verify_schedule(birg) && "Schedule verification failed");
1927                         assert(be_verify_register_pressure(birg, cls, irg)
1928                                 && "Register pressure verification failed");
1929                 }
1930                 BE_TIMER_POP(t_verify);
1931
1932                 BE_TIMER_PUSH(t_ra_color);
1933                 be_straight_alloc_cls();
1934                 BE_TIMER_POP(t_ra_color);
1935
1936                 /* we most probably constructed new Phis so liveness info is invalid
1937                  * now */
1938                 /* TODO: test liveness_introduce */
1939                 be_liveness_invalidate(lv);
1940                 free(normal_regs);
1941
1942                 stat_ev_ctx_pop("regcls");
1943         }
1944
1945         BE_TIMER_PUSH(t_ra_spill_apply);
1946         be_abi_fix_stack_nodes(birg->abi);
1947         BE_TIMER_POP(t_ra_spill_apply);
1948
1949         BE_TIMER_PUSH(t_verify);
1950         if (birg->main_env->options->vrfy_option == BE_VRFY_WARN) {
1951                 be_verify_register_allocation(birg);
1952         } else if (birg->main_env->options->vrfy_option == BE_VRFY_ASSERT) {
1953                 assert(be_verify_register_allocation(birg)
1954                                 && "Register allocation invalid");
1955         }
1956         BE_TIMER_POP(t_verify);
1957
1958         obstack_free(&obst, NULL);
1959 }
1960
1961 /**
1962  * Initializes this module.
1963  */
1964 void be_init_straight_alloc(void)
1965 {
1966         static be_ra_t be_ra_straight = {
1967                 be_straight_alloc,
1968         };
1969
1970         FIRM_DBG_REGISTER(dbg, "firm.be.straightalloc");
1971
1972         be_register_allocator("straight", &be_ra_straight);
1973 }
1974
1975 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_straight_alloc);