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