gcc/ira-build.c

   1 /* Building internal representation for IRA.
   2    Copyright (C) 2006-2017 Free Software Foundation, Inc.
   3    Contributed by Vladimir Makarov <vmakarov@redhat.com>.
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify it under
   8 the terms of the GNU General Public License as published by the Free
   9 Software Foundation; either version 3, or (at your option) any later
  10 version.
  11
  12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15 for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING3.  If not see
  19 <http://www.gnu.org/licenses/>.  */
  20
  21 #include "config.h"
  22 #include "system.h"
  23 #include "coretypes.h"
  24 #include "backend.h"
  25 #include "target.h"
  26 #include "rtl.h"
  27 #include "predict.h"
  28 #include "df.h"
  29 #include "insn-config.h"
  30 #include "regs.h"
  31 #include "memmodel.h"
  32 #include "ira.h"
  33 #include "ira-int.h"
  34 #include "params.h"
  35 #include "sparseset.h"
  36 #include "cfgloop.h"
  37
  38 static ira_copy_t find_allocno_copy (ira_allocno_t, ira_allocno_t, rtx_insn *,
  39                                      ira_loop_tree_node_t);
  40
  41 /* The root of the loop tree corresponding to the all function.  */
  42 ira_loop_tree_node_t ira_loop_tree_root;
  43
  44 /* Height of the loop tree.  */
  45 int ira_loop_tree_height;
  46
  47 /* All nodes representing basic blocks are referred through the
  48    following array.  We can not use basic block member `aux' for this
  49    because it is used for insertion of insns on edges.  */
  50 ira_loop_tree_node_t ira_bb_nodes;
  51
  52 /* All nodes representing loops are referred through the following
  53    array.  */
  54 ira_loop_tree_node_t ira_loop_nodes;
  55
  56 /* And size of the ira_loop_nodes array.  */
  57 unsigned int ira_loop_nodes_count;
  58
  59 /* Map regno -> allocnos with given regno (see comments for
  60    allocno member `next_regno_allocno').  */
  61 ira_allocno_t *ira_regno_allocno_map;
  62
  63 /* Array of references to all allocnos.  The order number of the
  64    allocno corresponds to the index in the array.  Removed allocnos
  65    have NULL element value.  */
  66 ira_allocno_t *ira_allocnos;
  67
  68 /* Sizes of the previous array.  */
  69 int ira_allocnos_num;
  70
  71 /* Count of conflict record structures we've created, used when creating
  72    a new conflict id.  */
  73 int ira_objects_num;
  74
  75 /* Map a conflict id to its conflict record.  */
  76 ira_object_t *ira_object_id_map;
  77
  78 /* Array of references to all allocno preferences.  The order number
  79    of the preference corresponds to the index in the array.  */
  80 ira_pref_t *ira_prefs;
  81
  82 /* Size of the previous array.  */
  83 int ira_prefs_num;
  84
  85 /* Array of references to all copies.  The order number of the copy
  86    corresponds to the index in the array.  Removed copies have NULL
  87    element value.  */
  88 ira_copy_t *ira_copies;
  89
  90 /* Size of the previous array.  */
  91 int ira_copies_num;
  92
  93 \f
  94
  95 /* LAST_BASIC_BLOCK before generating additional insns because of live
  96    range splitting.  Emitting insns on a critical edge creates a new
  97    basic block.  */
  98 static int last_basic_block_before_change;
  99
 100 /* Initialize some members in loop tree node NODE.  Use LOOP_NUM for
 101    the member loop_num.  */
 102 static void
 103 init_loop_tree_node (struct ira_loop_tree_node *node, int loop_num)
 104 {
 105   int max_regno = max_reg_num ();
 106
 107   node->regno_allocno_map
 108     = (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t) * max_regno);
 109   memset (node->regno_allocno_map, 0, sizeof (ira_allocno_t) * max_regno);
 110   memset (node->reg_pressure, 0, sizeof (node->reg_pressure));
 111   node->all_allocnos = ira_allocate_bitmap ();
 112   node->modified_regnos = ira_allocate_bitmap ();
 113   node->border_allocnos = ira_allocate_bitmap ();
 114   node->local_copies = ira_allocate_bitmap ();
 115   node->loop_num = loop_num;
 116   node->children = NULL;
 117   node->subloops = NULL;
 118 }
 119
 120
 121 /* The following function allocates the loop tree nodes.  If
 122    CURRENT_LOOPS is NULL, the nodes corresponding to the loops (except
 123    the root which corresponds the all function) will be not allocated
 124    but nodes will still be allocated for basic blocks.  */
 125 static void
 126 create_loop_tree_nodes (void)
 127 {
 128   unsigned int i, j;
 129   bool skip_p;
 130   edge_iterator ei;
 131   edge e;
 132   vec<edge> edges;
 133   loop_p loop;
 134
 135   ira_bb_nodes
 136     = ((struct ira_loop_tree_node *)
 137        ira_allocate (sizeof (struct ira_loop_tree_node)
 138                      * last_basic_block_for_fn (cfun)));
 139   last_basic_block_before_change = last_basic_block_for_fn (cfun);
 140   for (i = 0; i < (unsigned int) last_basic_block_for_fn (cfun); i++)
 141     {
 142       ira_bb_nodes[i].regno_allocno_map = NULL;
 143       memset (ira_bb_nodes[i].reg_pressure, 0,
 144               sizeof (ira_bb_nodes[i].reg_pressure));
 145       ira_bb_nodes[i].all_allocnos = NULL;
 146       ira_bb_nodes[i].modified_regnos = NULL;
 147       ira_bb_nodes[i].border_allocnos = NULL;
 148       ira_bb_nodes[i].local_copies = NULL;
 149     }
 150   if (current_loops == NULL)
 151     {
 152       ira_loop_nodes_count = 1;
 153       ira_loop_nodes = ((struct ira_loop_tree_node *)
 154                         ira_allocate (sizeof (struct ira_loop_tree_node)));
 155       init_loop_tree_node (ira_loop_nodes, 0);
 156       return;
 157     }
 158   ira_loop_nodes_count = number_of_loops (cfun);
 159   ira_loop_nodes = ((struct ira_loop_tree_node *)
 160                     ira_allocate (sizeof (struct ira_loop_tree_node)
 161                                   * ira_loop_nodes_count));
 162   FOR_EACH_VEC_SAFE_ELT (get_loops (cfun), i, loop)
 163     {
 164       if (loop_outer (loop) != NULL)
 165         {
 166           ira_loop_nodes[i].regno_allocno_map = NULL;
 167           skip_p = false;
 168           FOR_EACH_EDGE (e, ei, loop->header->preds)
 169             if (e->src != loop->latch
 170                 && (e->flags & EDGE_ABNORMAL) && EDGE_CRITICAL_P (e))
 171               {
 172                 skip_p = true;
 173                 break;
 174               }
 175           if (skip_p)
 176             continue;
 177           edges = get_loop_exit_edges (loop);
 178           FOR_EACH_VEC_ELT (edges, j, e)
 179             if ((e->flags & EDGE_ABNORMAL) && EDGE_CRITICAL_P (e))
 180               {
 181                 skip_p = true;
 182                 break;
 183               }
 184           edges.release ();
 185           if (skip_p)
 186             continue;
 187         }
 188       init_loop_tree_node (&ira_loop_nodes[i], loop->num);
 189     }
 190 }
 191
 192 /* The function returns TRUE if there are more one allocation
 193    region.  */
 194 static bool
 195 more_one_region_p (void)
 196 {
 197   unsigned int i;
 198   loop_p loop;
 199
 200   if (current_loops != NULL)
 201     FOR_EACH_VEC_SAFE_ELT (get_loops (cfun), i, loop)
 202       if (ira_loop_nodes[i].regno_allocno_map != NULL
 203           && ira_loop_tree_root != &ira_loop_nodes[i])
 204         return true;
 205   return false;
 206 }
 207
 208 /* Free the loop tree node of a loop.  */
 209 static void
 210 finish_loop_tree_node (ira_loop_tree_node_t loop)
 211 {
 212   if (loop->regno_allocno_map != NULL)
 213     {
 214       ira_assert (loop->bb == NULL);
 215       ira_free_bitmap (loop->local_copies);
 216       ira_free_bitmap (loop->border_allocnos);
 217       ira_free_bitmap (loop->modified_regnos);
 218       ira_free_bitmap (loop->all_allocnos);
 219       ira_free (loop->regno_allocno_map);
 220       loop->regno_allocno_map = NULL;
 221     }
 222 }
 223
 224 /* Free the loop tree nodes.  */
 225 static void
 226 finish_loop_tree_nodes (void)
 227 {
 228   unsigned int i;
 229
 230   for (i = 0; i < ira_loop_nodes_count; i++)
 231     finish_loop_tree_node (&ira_loop_nodes[i]);
 232   ira_free (ira_loop_nodes);
 233   for (i = 0; i < (unsigned int) last_basic_block_before_change; i++)
 234     {
 235       if (ira_bb_nodes[i].local_copies != NULL)
 236         ira_free_bitmap (ira_bb_nodes[i].local_copies);
 237       if (ira_bb_nodes[i].border_allocnos != NULL)
 238         ira_free_bitmap (ira_bb_nodes[i].border_allocnos);
 239       if (ira_bb_nodes[i].modified_regnos != NULL)
 240         ira_free_bitmap (ira_bb_nodes[i].modified_regnos);
 241       if (ira_bb_nodes[i].all_allocnos != NULL)
 242         ira_free_bitmap (ira_bb_nodes[i].all_allocnos);
 243       if (ira_bb_nodes[i].regno_allocno_map != NULL)
 244         ira_free (ira_bb_nodes[i].regno_allocno_map);
 245     }
 246   ira_free (ira_bb_nodes);
 247 }
 248
 249 \f
 250
 251 /* The following recursive function adds LOOP to the loop tree
 252    hierarchy.  LOOP is added only once.  If LOOP is NULL we adding
 253    loop designating the whole function when CFG loops are not
 254    built.  */
 255 static void
 256 add_loop_to_tree (struct loop *loop)
 257 {
 258   int loop_num;
 259   struct loop *parent;
 260   ira_loop_tree_node_t loop_node, parent_node;
 261
 262   /* We can not use loop node access macros here because of potential
 263      checking and because the nodes are not initialized enough
 264      yet.  */
 265   if (loop != NULL && loop_outer (loop) != NULL)
 266     add_loop_to_tree (loop_outer (loop));
 267   loop_num = loop != NULL ? loop->num : 0;
 268   if (ira_loop_nodes[loop_num].regno_allocno_map != NULL
 269       && ira_loop_nodes[loop_num].children == NULL)
 270     {
 271       /* We have not added loop node to the tree yet.  */
 272       loop_node = &ira_loop_nodes[loop_num];
 273       loop_node->loop = loop;
 274       loop_node->bb = NULL;
 275       if (loop == NULL)
 276         parent = NULL;
 277       else
 278         {
 279           for (parent = loop_outer (loop);
 280                parent != NULL;
 281                parent = loop_outer (parent))
 282             if (ira_loop_nodes[parent->num].regno_allocno_map != NULL)
 283               break;
 284         }
 285       if (parent == NULL)
 286         {
 287           loop_node->next = NULL;
 288           loop_node->subloop_next = NULL;
 289           loop_node->parent = NULL;
 290         }
 291       else
 292         {
 293           parent_node = &ira_loop_nodes[parent->num];
 294           loop_node->next = parent_node->children;
 295           parent_node->children = loop_node;
 296           loop_node->subloop_next = parent_node->subloops;
 297           parent_node->subloops = loop_node;
 298           loop_node->parent = parent_node;
 299         }
 300     }
 301 }
 302
 303 /* The following recursive function sets up levels of nodes of the
 304    tree given its root LOOP_NODE.  The enumeration starts with LEVEL.
 305    The function returns maximal value of level in the tree + 1.  */
 306 static int
 307 setup_loop_tree_level (ira_loop_tree_node_t loop_node, int level)
 308 {
 309   int height, max_height;
 310   ira_loop_tree_node_t subloop_node;
 311
 312   ira_assert (loop_node->bb == NULL);
 313   loop_node->level = level;
 314   max_height = level + 1;
 315   for (subloop_node = loop_node->subloops;
 316        subloop_node != NULL;
 317        subloop_node = subloop_node->subloop_next)
 318     {
 319       ira_assert (subloop_node->bb == NULL);
 320       height = setup_loop_tree_level (subloop_node, level + 1);
 321       if (height > max_height)
 322         max_height = height;
 323     }
 324   return max_height;
 325 }
 326
 327 /* Create the loop tree.  The algorithm is designed to provide correct
 328    order of loops (they are ordered by their last loop BB) and basic
 329    blocks in the chain formed by member next.  */
 330 static void
 331 form_loop_tree (void)
 332 {
 333   basic_block bb;
 334   struct loop *parent;
 335   ira_loop_tree_node_t bb_node, loop_node;
 336
 337   /* We can not use loop/bb node access macros because of potential
 338      checking and because the nodes are not initialized enough
 339      yet.  */
 340   FOR_EACH_BB_FN (bb, cfun)
 341     {
 342       bb_node = &ira_bb_nodes[bb->index];
 343       bb_node->bb = bb;
 344       bb_node->loop = NULL;
 345       bb_node->subloops = NULL;
 346       bb_node->children = NULL;
 347       bb_node->subloop_next = NULL;
 348       bb_node->next = NULL;
 349       if (current_loops == NULL)
 350         parent = NULL;
 351       else
 352         {
 353           for (parent = bb->loop_father;
 354                parent != NULL;
 355                parent = loop_outer (parent))
 356             if (ira_loop_nodes[parent->num].regno_allocno_map != NULL)
 357               break;
 358         }
 359       add_loop_to_tree (parent);
 360       loop_node = &ira_loop_nodes[parent == NULL ? 0 : parent->num];
 361       bb_node->next = loop_node->children;
 362       bb_node->parent = loop_node;
 363       loop_node->children = bb_node;
 364     }
 365   ira_loop_tree_root = IRA_LOOP_NODE_BY_INDEX (0);
 366   ira_loop_tree_height = setup_loop_tree_level (ira_loop_tree_root, 0);
 367   ira_assert (ira_loop_tree_root->regno_allocno_map != NULL);
 368 }
 369
 370 \f
 371
 372 /* Rebuild IRA_REGNO_ALLOCNO_MAP and REGNO_ALLOCNO_MAPs of the loop
 373    tree nodes.  */
 374 static void
 375 rebuild_regno_allocno_maps (void)
 376 {
 377   unsigned int l;
 378   int max_regno, regno;
 379   ira_allocno_t a;
 380   ira_loop_tree_node_t loop_tree_node;
 381   loop_p loop;
 382   ira_allocno_iterator ai;
 383
 384   ira_assert (current_loops != NULL);
 385   max_regno = max_reg_num ();
 386   FOR_EACH_VEC_SAFE_ELT (get_loops (cfun), l, loop)
 387     if (ira_loop_nodes[l].regno_allocno_map != NULL)
 388       {
 389         ira_free (ira_loop_nodes[l].regno_allocno_map);
 390         ira_loop_nodes[l].regno_allocno_map
 391           = (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t)
 392                                             * max_regno);
 393         memset (ira_loop_nodes[l].regno_allocno_map, 0,
 394                 sizeof (ira_allocno_t) * max_regno);
 395       }
 396   ira_free (ira_regno_allocno_map);
 397   ira_regno_allocno_map
 398     = (ira_allocno_t *) ira_allocate (max_regno * sizeof (ira_allocno_t));
 399   memset (ira_regno_allocno_map, 0, max_regno * sizeof (ira_allocno_t));
 400   FOR_EACH_ALLOCNO (a, ai)
 401     {
 402       if (ALLOCNO_CAP_MEMBER (a) != NULL)
 403         /* Caps are not in the regno allocno maps.  */
 404         continue;
 405       regno = ALLOCNO_REGNO (a);
 406       loop_tree_node = ALLOCNO_LOOP_TREE_NODE (a);
 407       ALLOCNO_NEXT_REGNO_ALLOCNO (a) = ira_regno_allocno_map[regno];
 408       ira_regno_allocno_map[regno] = a;
 409       if (loop_tree_node->regno_allocno_map[regno] == NULL)
 410         /* Remember that we can create temporary allocnos to break
 411            cycles in register shuffle.  */
 412         loop_tree_node->regno_allocno_map[regno] = a;
 413     }
 414 }
 415 \f
 416
 417 /* Pools for allocnos, allocno live ranges and objects.  */
 418 static object_allocator<live_range> live_range_pool ("live ranges");
 419 static object_allocator<ira_allocno> allocno_pool ("allocnos");
 420 static object_allocator<ira_object> object_pool ("objects");
 421
 422 /* Vec containing references to all created allocnos.  It is a
 423    container of array allocnos.  */
 424 static vec<ira_allocno_t> allocno_vec;
 425
 426 /* Vec containing references to all created ira_objects.  It is a
 427    container of ira_object_id_map.  */
 428 static vec<ira_object_t> ira_object_id_map_vec;
 429
 430 /* Initialize data concerning allocnos.  */
 431 static void
 432 initiate_allocnos (void)
 433 {
 434   allocno_vec.create (max_reg_num () * 2);
 435   ira_allocnos = NULL;
 436   ira_allocnos_num = 0;
 437   ira_objects_num = 0;
 438   ira_object_id_map_vec.create (max_reg_num () * 2);
 439   ira_object_id_map = NULL;
 440   ira_regno_allocno_map
 441     = (ira_allocno_t *) ira_allocate (max_reg_num ()
 442                                       * sizeof (ira_allocno_t));
 443   memset (ira_regno_allocno_map, 0, max_reg_num () * sizeof (ira_allocno_t));
 444 }
 445
 446 /* Create and return an object corresponding to a new allocno A.  */
 447 static ira_object_t
 448 ira_create_object (ira_allocno_t a, int subword)
 449 {
 450   enum reg_class aclass = ALLOCNO_CLASS (a);
 451   ira_object_t obj = object_pool.allocate ();
 452
 453   OBJECT_ALLOCNO (obj) = a;
 454   OBJECT_SUBWORD (obj) = subword;
 455   OBJECT_CONFLICT_ID (obj) = ira_objects_num;
 456   OBJECT_CONFLICT_VEC_P (obj) = false;
 457   OBJECT_CONFLICT_ARRAY (obj) = NULL;
 458   OBJECT_NUM_CONFLICTS (obj) = 0;
 459   COPY_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (obj), ira_no_alloc_regs);
 460   COPY_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj), ira_no_alloc_regs);
 461   IOR_COMPL_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (obj),
 462                           reg_class_contents[aclass]);
 463   IOR_COMPL_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj),
 464                           reg_class_contents[aclass]);
 465   OBJECT_MIN (obj) = INT_MAX;
 466   OBJECT_MAX (obj) = -1;
 467   OBJECT_LIVE_RANGES (obj) = NULL;
 468
 469   ira_object_id_map_vec.safe_push (obj);
 470   ira_object_id_map
 471     = ira_object_id_map_vec.address ();
 472   ira_objects_num = ira_object_id_map_vec.length ();
 473
 474   return obj;
 475 }
 476
 477 /* Create and return the allocno corresponding to REGNO in
 478    LOOP_TREE_NODE.  Add the allocno to the list of allocnos with the
 479    same regno if CAP_P is FALSE.  */
 480 ira_allocno_t
 481 ira_create_allocno (int regno, bool cap_p,
 482                     ira_loop_tree_node_t loop_tree_node)
 483 {
 484   ira_allocno_t a;
 485
 486   a = allocno_pool.allocate ();
 487   ALLOCNO_REGNO (a) = regno;
 488   ALLOCNO_LOOP_TREE_NODE (a) = loop_tree_node;
 489   if (! cap_p)
 490     {
 491       ALLOCNO_NEXT_REGNO_ALLOCNO (a) = ira_regno_allocno_map[regno];
 492       ira_regno_allocno_map[regno] = a;
 493       if (loop_tree_node->regno_allocno_map[regno] == NULL)
 494         /* Remember that we can create temporary allocnos to break
 495            cycles in register shuffle on region borders (see
 496            ira-emit.c).  */
 497         loop_tree_node->regno_allocno_map[regno] = a;
 498     }
 499   ALLOCNO_CAP (a) = NULL;
 500   ALLOCNO_CAP_MEMBER (a) = NULL;
 501   ALLOCNO_NUM (a) = ira_allocnos_num;
 502   bitmap_set_bit (loop_tree_node->all_allocnos, ALLOCNO_NUM (a));
 503   ALLOCNO_NREFS (a) = 0;
 504   ALLOCNO_FREQ (a) = 0;
 505   ALLOCNO_HARD_REGNO (a) = -1;
 506   ALLOCNO_CALL_FREQ (a) = 0;
 507   ALLOCNO_CALLS_CROSSED_NUM (a) = 0;
 508   ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a) = 0;
 509   CLEAR_HARD_REG_SET (ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS (a));
 510 #ifdef STACK_REGS
 511   ALLOCNO_NO_STACK_REG_P (a) = false;
 512   ALLOCNO_TOTAL_NO_STACK_REG_P (a) = false;
 513 #endif
 514   ALLOCNO_DONT_REASSIGN_P (a) = false;
 515   ALLOCNO_BAD_SPILL_P (a) = false;
 516   ALLOCNO_ASSIGNED_P (a) = false;
 517   ALLOCNO_MODE (a) = (regno < 0 ? VOIDmode : PSEUDO_REGNO_MODE (regno));
 518   ALLOCNO_WMODE (a) = ALLOCNO_MODE (a);
 519   ALLOCNO_PREFS (a) = NULL;
 520   ALLOCNO_COPIES (a) = NULL;
 521   ALLOCNO_HARD_REG_COSTS (a) = NULL;
 522   ALLOCNO_CONFLICT_HARD_REG_COSTS (a) = NULL;
 523   ALLOCNO_UPDATED_HARD_REG_COSTS (a) = NULL;
 524   ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) = NULL;
 525   ALLOCNO_CLASS (a) = NO_REGS;
 526   ALLOCNO_UPDATED_CLASS_COST (a) = 0;
 527   ALLOCNO_CLASS_COST (a) = 0;
 528   ALLOCNO_MEMORY_COST (a) = 0;
 529   ALLOCNO_UPDATED_MEMORY_COST (a) = 0;
 530   ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a) = 0;
 531   ALLOCNO_NUM_OBJECTS (a) = 0;
 532
 533   ALLOCNO_ADD_DATA (a) = NULL;
 534   allocno_vec.safe_push (a);
 535   ira_allocnos = allocno_vec.address ();
 536   ira_allocnos_num = allocno_vec.length ();
 537
 538   return a;
 539 }
 540
 541 /* Set up register class for A and update its conflict hard
 542    registers.  */
 543 void
 544 ira_set_allocno_class (ira_allocno_t a, enum reg_class aclass)
 545 {
 546   ira_allocno_object_iterator oi;
 547   ira_object_t obj;
 548
 549   ALLOCNO_CLASS (a) = aclass;
 550   FOR_EACH_ALLOCNO_OBJECT (a, obj, oi)
 551     {
 552       IOR_COMPL_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (obj),
 553                               reg_class_contents[aclass]);
 554       IOR_COMPL_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj),
 555                               reg_class_contents[aclass]);
 556     }
 557 }
 558
 559 /* Determine the number of objects we should associate with allocno A
 560    and allocate them.  */
 561 void
 562 ira_create_allocno_objects (ira_allocno_t a)
 563 {
 564   machine_mode mode = ALLOCNO_MODE (a);
 565   enum reg_class aclass = ALLOCNO_CLASS (a);
 566   int n = ira_reg_class_max_nregs[aclass][mode];
 567   int i;
 568
 569   if (GET_MODE_SIZE (mode) != 2 * UNITS_PER_WORD || n != 2)
 570     n = 1;
 571
 572   ALLOCNO_NUM_OBJECTS (a) = n;
 573   for (i = 0; i < n; i++)
 574     ALLOCNO_OBJECT (a, i) = ira_create_object (a, i);
 575 }
 576
 577 /* For each allocno, set ALLOCNO_NUM_OBJECTS and create the
 578    ALLOCNO_OBJECT structures.  This must be called after the allocno
 579    classes are known.  */
 580 static void
 581 create_allocno_objects (void)
 582 {
 583   ira_allocno_t a;
 584   ira_allocno_iterator ai;
 585
 586   FOR_EACH_ALLOCNO (a, ai)
 587     ira_create_allocno_objects (a);
 588 }
 589
 590 /* Merge hard register conflict information for all objects associated with
 591    allocno TO into the corresponding objects associated with FROM.
 592    If TOTAL_ONLY is true, we only merge OBJECT_TOTAL_CONFLICT_HARD_REGS.  */
 593 static void
 594 merge_hard_reg_conflicts (ira_allocno_t from, ira_allocno_t to,
 595                           bool total_only)
 596 {
 597   int i;
 598   gcc_assert (ALLOCNO_NUM_OBJECTS (to) == ALLOCNO_NUM_OBJECTS (from));
 599   for (i = 0; i < ALLOCNO_NUM_OBJECTS (to); i++)
 600     {
 601       ira_object_t from_obj = ALLOCNO_OBJECT (from, i);
 602       ira_object_t to_obj = ALLOCNO_OBJECT (to, i);
 603
 604       if (!total_only)
 605         IOR_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (to_obj),
 606                           OBJECT_CONFLICT_HARD_REGS (from_obj));
 607       IOR_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (to_obj),
 608                         OBJECT_TOTAL_CONFLICT_HARD_REGS (from_obj));
 609     }
 610 #ifdef STACK_REGS
 611   if (!total_only && ALLOCNO_NO_STACK_REG_P (from))
 612     ALLOCNO_NO_STACK_REG_P (to) = true;
 613   if (ALLOCNO_TOTAL_NO_STACK_REG_P (from))
 614     ALLOCNO_TOTAL_NO_STACK_REG_P (to) = true;
 615 #endif
 616 }
 617
 618 /* Update hard register conflict information for all objects associated with
 619    A to include the regs in SET.  */
 620 void
 621 ior_hard_reg_conflicts (ira_allocno_t a, HARD_REG_SET *set)
 622 {
 623   ira_allocno_object_iterator i;
 624   ira_object_t obj;
 625
 626   FOR_EACH_ALLOCNO_OBJECT (a, obj, i)
 627     {
 628       IOR_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (obj), *set);
 629       IOR_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj), *set);
 630     }
 631 }
 632
 633 /* Return TRUE if a conflict vector with NUM elements is more
 634    profitable than a conflict bit vector for OBJ.  */
 635 bool
 636 ira_conflict_vector_profitable_p (ira_object_t obj, int num)
 637 {
 638   int nw;
 639   int max = OBJECT_MAX (obj);
 640   int min = OBJECT_MIN (obj);
 641
 642   if (max < min)
 643     /* We prefer a bit vector in such case because it does not result
 644        in allocation.  */
 645     return false;
 646
 647   nw = (max - min + IRA_INT_BITS) / IRA_INT_BITS;
 648   return (2 * sizeof (ira_object_t) * (num + 1)
 649           < 3 * nw * sizeof (IRA_INT_TYPE));
 650 }
 651
 652 /* Allocates and initialize the conflict vector of OBJ for NUM
 653    conflicting objects.  */
 654 void
 655 ira_allocate_conflict_vec (ira_object_t obj, int num)
 656 {
 657   int size;
 658   ira_object_t *vec;
 659
 660   ira_assert (OBJECT_CONFLICT_ARRAY (obj) == NULL);
 661   num++; /* for NULL end marker  */
 662   size = sizeof (ira_object_t) * num;
 663   OBJECT_CONFLICT_ARRAY (obj) = ira_allocate (size);
 664   vec = (ira_object_t *) OBJECT_CONFLICT_ARRAY (obj);
 665   vec[0] = NULL;
 666   OBJECT_NUM_CONFLICTS (obj) = 0;
 667   OBJECT_CONFLICT_ARRAY_SIZE (obj) = size;
 668   OBJECT_CONFLICT_VEC_P (obj) = true;
 669 }
 670
 671 /* Allocate and initialize the conflict bit vector of OBJ.  */
 672 static void
 673 allocate_conflict_bit_vec (ira_object_t obj)
 674 {
 675   unsigned int size;
 676
 677   ira_assert (OBJECT_CONFLICT_ARRAY (obj) == NULL);
 678   size = ((OBJECT_MAX (obj) - OBJECT_MIN (obj) + IRA_INT_BITS)
 679           / IRA_INT_BITS * sizeof (IRA_INT_TYPE));
 680   OBJECT_CONFLICT_ARRAY (obj) = ira_allocate (size);
 681   memset (OBJECT_CONFLICT_ARRAY (obj), 0, size);
 682   OBJECT_CONFLICT_ARRAY_SIZE (obj) = size;
 683   OBJECT_CONFLICT_VEC_P (obj) = false;
 684 }
 685
 686 /* Allocate and initialize the conflict vector or conflict bit vector
 687    of OBJ for NUM conflicting allocnos whatever is more profitable.  */
 688 void
 689 ira_allocate_object_conflicts (ira_object_t obj, int num)
 690 {
 691   if (ira_conflict_vector_profitable_p (obj, num))
 692     ira_allocate_conflict_vec (obj, num);
 693   else
 694     allocate_conflict_bit_vec (obj);
 695 }
 696
 697 /* Add OBJ2 to the conflicts of OBJ1.  */
 698 static void
 699 add_to_conflicts (ira_object_t obj1, ira_object_t obj2)
 700 {
 701   int num;
 702   unsigned int size;
 703
 704   if (OBJECT_CONFLICT_VEC_P (obj1))
 705     {
 706       ira_object_t *vec = OBJECT_CONFLICT_VEC (obj1);
 707       int curr_num = OBJECT_NUM_CONFLICTS (obj1);
 708       num = curr_num + 2;
 709       if (OBJECT_CONFLICT_ARRAY_SIZE (obj1) < num * sizeof (ira_object_t))
 710         {
 711           ira_object_t *newvec;
 712           size = (3 * num / 2 + 1) * sizeof (ira_allocno_t);
 713           newvec = (ira_object_t *) ira_allocate (size);
 714           memcpy (newvec, vec, curr_num * sizeof (ira_object_t));
 715           ira_free (vec);
 716           vec = newvec;
 717           OBJECT_CONFLICT_ARRAY (obj1) = vec;
 718           OBJECT_CONFLICT_ARRAY_SIZE (obj1) = size;
 719         }
 720       vec[num - 2] = obj2;
 721       vec[num - 1] = NULL;
 722       OBJECT_NUM_CONFLICTS (obj1)++;
 723     }
 724   else
 725     {
 726       int nw, added_head_nw, id;
 727       IRA_INT_TYPE *vec = OBJECT_CONFLICT_BITVEC (obj1);
 728
 729       id = OBJECT_CONFLICT_ID (obj2);
 730       if (OBJECT_MIN (obj1) > id)
 731         {
 732           /* Expand head of the bit vector.  */
 733           added_head_nw = (OBJECT_MIN (obj1) - id - 1) / IRA_INT_BITS + 1;
 734           nw = (OBJECT_MAX (obj1) - OBJECT_MIN (obj1)) / IRA_INT_BITS + 1;
 735           size = (nw + added_head_nw) * sizeof (IRA_INT_TYPE);
 736           if (OBJECT_CONFLICT_ARRAY_SIZE (obj1) >= size)
 737             {
 738               memmove ((char *) vec + added_head_nw * sizeof (IRA_INT_TYPE),
 739                        vec, nw * sizeof (IRA_INT_TYPE));
 740               memset (vec, 0, added_head_nw * sizeof (IRA_INT_TYPE));
 741             }
 742           else
 743             {
 744               size
 745                 = (3 * (nw + added_head_nw) / 2 + 1) * sizeof (IRA_INT_TYPE);
 746               vec = (IRA_INT_TYPE *) ira_allocate (size);
 747               memcpy ((char *) vec + added_head_nw * sizeof (IRA_INT_TYPE),
 748                       OBJECT_CONFLICT_ARRAY (obj1), nw * sizeof (IRA_INT_TYPE));
 749               memset (vec, 0, added_head_nw * sizeof (IRA_INT_TYPE));
 750               memset ((char *) vec
 751                       + (nw + added_head_nw) * sizeof (IRA_INT_TYPE),
 752                       0, size - (nw + added_head_nw) * sizeof (IRA_INT_TYPE));
 753               ira_free (OBJECT_CONFLICT_ARRAY (obj1));
 754               OBJECT_CONFLICT_ARRAY (obj1) = vec;
 755               OBJECT_CONFLICT_ARRAY_SIZE (obj1) = size;
 756             }
 757           OBJECT_MIN (obj1) -= added_head_nw * IRA_INT_BITS;
 758         }
 759       else if (OBJECT_MAX (obj1) < id)
 760         {
 761           nw = (id - OBJECT_MIN (obj1)) / IRA_INT_BITS + 1;
 762           size = nw * sizeof (IRA_INT_TYPE);
 763           if (OBJECT_CONFLICT_ARRAY_SIZE (obj1) < size)
 764             {
 765               /* Expand tail of the bit vector.  */
 766               size = (3 * nw / 2 + 1) * sizeof (IRA_INT_TYPE);
 767               vec = (IRA_INT_TYPE *) ira_allocate (size);
 768               memcpy (vec, OBJECT_CONFLICT_ARRAY (obj1), OBJECT_CONFLICT_ARRAY_SIZE (obj1));
 769               memset ((char *) vec + OBJECT_CONFLICT_ARRAY_SIZE (obj1),
 770                       0, size - OBJECT_CONFLICT_ARRAY_SIZE (obj1));
 771               ira_free (OBJECT_CONFLICT_ARRAY (obj1));
 772               OBJECT_CONFLICT_ARRAY (obj1) = vec;
 773               OBJECT_CONFLICT_ARRAY_SIZE (obj1) = size;
 774             }
 775           OBJECT_MAX (obj1) = id;
 776         }
 777       SET_MINMAX_SET_BIT (vec, id, OBJECT_MIN (obj1), OBJECT_MAX (obj1));
 778     }
 779 }
 780
 781 /* Add OBJ1 to the conflicts of OBJ2 and vice versa.  */
 782 static void
 783 ira_add_conflict (ira_object_t obj1, ira_object_t obj2)
 784 {
 785   add_to_conflicts (obj1, obj2);
 786   add_to_conflicts (obj2, obj1);
 787 }
 788
 789 /* Clear all conflicts of OBJ.  */
 790 static void
 791 clear_conflicts (ira_object_t obj)
 792 {
 793   if (OBJECT_CONFLICT_VEC_P (obj))
 794     {
 795       OBJECT_NUM_CONFLICTS (obj) = 0;
 796       OBJECT_CONFLICT_VEC (obj)[0] = NULL;
 797     }
 798   else if (OBJECT_CONFLICT_ARRAY_SIZE (obj) != 0)
 799     {
 800       int nw;
 801
 802       nw = (OBJECT_MAX (obj) - OBJECT_MIN (obj)) / IRA_INT_BITS + 1;
 803       memset (OBJECT_CONFLICT_BITVEC (obj), 0, nw * sizeof (IRA_INT_TYPE));
 804     }
 805 }
 806
 807 /* The array used to find duplications in conflict vectors of
 808    allocnos.  */
 809 static int *conflict_check;
 810
 811 /* The value used to mark allocation presence in conflict vector of
 812    the current allocno.  */
 813 static int curr_conflict_check_tick;
 814
 815 /* Remove duplications in conflict vector of OBJ.  */
 816 static void
 817 compress_conflict_vec (ira_object_t obj)
 818 {
 819   ira_object_t *vec, conflict_obj;
 820   int i, j;
 821
 822   ira_assert (OBJECT_CONFLICT_VEC_P (obj));
 823   vec = OBJECT_CONFLICT_VEC (obj);
 824   curr_conflict_check_tick++;
 825   for (i = j = 0; (conflict_obj = vec[i]) != NULL; i++)
 826     {
 827       int id = OBJECT_CONFLICT_ID (conflict_obj);
 828       if (conflict_check[id] != curr_conflict_check_tick)
 829         {
 830           conflict_check[id] = curr_conflict_check_tick;
 831           vec[j++] = conflict_obj;
 832         }
 833     }
 834   OBJECT_NUM_CONFLICTS (obj) = j;
 835   vec[j] = NULL;
 836 }
 837
 838 /* Remove duplications in conflict vectors of all allocnos.  */
 839 static void
 840 compress_conflict_vecs (void)
 841 {
 842   ira_object_t obj;
 843   ira_object_iterator oi;
 844
 845   conflict_check = (int *) ira_allocate (sizeof (int) * ira_objects_num);
 846   memset (conflict_check, 0, sizeof (int) * ira_objects_num);
 847   curr_conflict_check_tick = 0;
 848   FOR_EACH_OBJECT (obj, oi)
 849     {
 850       if (OBJECT_CONFLICT_VEC_P (obj))
 851         compress_conflict_vec (obj);
 852     }
 853   ira_free (conflict_check);
 854 }
 855
 856 /* This recursive function outputs allocno A and if it is a cap the
 857    function outputs its members.  */
 858 void
 859 ira_print_expanded_allocno (ira_allocno_t a)
 860 {
 861   basic_block bb;
 862
 863   fprintf (ira_dump_file, " a%d(r%d", ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
 864   if ((bb = ALLOCNO_LOOP_TREE_NODE (a)->bb) != NULL)
 865     fprintf (ira_dump_file, ",b%d", bb->index);
 866   else
 867     fprintf (ira_dump_file, ",l%d", ALLOCNO_LOOP_TREE_NODE (a)->loop_num);
 868   if (ALLOCNO_CAP_MEMBER (a) != NULL)
 869     {
 870       fprintf (ira_dump_file, ":");
 871       ira_print_expanded_allocno (ALLOCNO_CAP_MEMBER (a));
 872     }
 873   fprintf (ira_dump_file, ")");
 874 }
 875
 876 /* Create and return the cap representing allocno A in the
 877    parent loop.  */
 878 static ira_allocno_t
 879 create_cap_allocno (ira_allocno_t a)
 880 {
 881   ira_allocno_t cap;
 882   ira_loop_tree_node_t parent;
 883   enum reg_class aclass;
 884
 885   parent = ALLOCNO_LOOP_TREE_NODE (a)->parent;
 886   cap = ira_create_allocno (ALLOCNO_REGNO (a), true, parent);
 887   ALLOCNO_MODE (cap) = ALLOCNO_MODE (a);
 888   ALLOCNO_WMODE (cap) = ALLOCNO_WMODE (a);
 889   aclass = ALLOCNO_CLASS (a);
 890   ira_set_allocno_class (cap, aclass);
 891   ira_create_allocno_objects (cap);
 892   ALLOCNO_CAP_MEMBER (cap) = a;
 893   ALLOCNO_CAP (a) = cap;
 894   ALLOCNO_CLASS_COST (cap) = ALLOCNO_CLASS_COST (a);
 895   ALLOCNO_MEMORY_COST (cap) = ALLOCNO_MEMORY_COST (a);
 896   ira_allocate_and_copy_costs
 897     (&ALLOCNO_HARD_REG_COSTS (cap), aclass, ALLOCNO_HARD_REG_COSTS (a));
 898   ira_allocate_and_copy_costs
 899     (&ALLOCNO_CONFLICT_HARD_REG_COSTS (cap), aclass,
 900      ALLOCNO_CONFLICT_HARD_REG_COSTS (a));
 901   ALLOCNO_BAD_SPILL_P (cap) = ALLOCNO_BAD_SPILL_P (a);
 902   ALLOCNO_NREFS (cap) = ALLOCNO_NREFS (a);
 903   ALLOCNO_FREQ (cap) = ALLOCNO_FREQ (a);
 904   ALLOCNO_CALL_FREQ (cap) = ALLOCNO_CALL_FREQ (a);
 905
 906   merge_hard_reg_conflicts (a, cap, false);
 907
 908   ALLOCNO_CALLS_CROSSED_NUM (cap) = ALLOCNO_CALLS_CROSSED_NUM (a);
 909   ALLOCNO_CHEAP_CALLS_CROSSED_NUM (cap) = ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a);
 910   IOR_HARD_REG_SET (ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS (cap),
 911                     ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS (a));
 912   if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
 913     {
 914       fprintf (ira_dump_file, "    Creating cap ");
 915       ira_print_expanded_allocno (cap);
 916       fprintf (ira_dump_file, "\n");
 917     }
 918   return cap;
 919 }
 920
 921 /* Create and return a live range for OBJECT with given attributes.  */
 922 live_range_t
 923 ira_create_live_range (ira_object_t obj, int start, int finish,
 924                        live_range_t next)
 925 {
 926   live_range_t p;
 927
 928   p = live_range_pool.allocate ();
 929   p->object = obj;
 930   p->start = start;
 931   p->finish = finish;
 932   p->next = next;
 933   return p;
 934 }
 935
 936 /* Create a new live range for OBJECT and queue it at the head of its
 937    live range list.  */
 938 void
 939 ira_add_live_range_to_object (ira_object_t object, int start, int finish)
 940 {
 941   live_range_t p;
 942   p = ira_create_live_range (object, start, finish,
 943                              OBJECT_LIVE_RANGES (object));
 944   OBJECT_LIVE_RANGES (object) = p;
 945 }
 946
 947 /* Copy allocno live range R and return the result.  */
 948 static live_range_t
 949 copy_live_range (live_range_t r)
 950 {
 951   live_range_t p;
 952
 953   p = live_range_pool.allocate ();
 954   *p = *r;
 955   return p;
 956 }
 957
 958 /* Copy allocno live range list given by its head R and return the
 959    result.  */
 960 live_range_t
 961 ira_copy_live_range_list (live_range_t r)
 962 {
 963   live_range_t p, first, last;
 964
 965   if (r == NULL)
 966     return NULL;
 967   for (first = last = NULL; r != NULL; r = r->next)
 968     {
 969       p = copy_live_range (r);
 970       if (first == NULL)
 971         first = p;
 972       else
 973         last->next = p;
 974       last = p;
 975     }
 976   return first;
 977 }
 978
 979 /* Merge ranges R1 and R2 and returns the result.  The function
 980    maintains the order of ranges and tries to minimize number of the
 981    result ranges.  */
 982 live_range_t
 983 ira_merge_live_ranges (live_range_t r1, live_range_t r2)
 984 {
 985   live_range_t first, last;
 986
 987   if (r1 == NULL)
 988     return r2;
 989   if (r2 == NULL)
 990     return r1;
 991   for (first = last = NULL; r1 != NULL && r2 != NULL;)
 992     {
 993       if (r1->start < r2->start)
 994         std::swap (r1, r2);
 995       if (r1->start <= r2->finish + 1)
 996         {
 997           /* Intersected ranges: merge r1 and r2 into r1.  */
 998           r1->start = r2->start;
 999           if (r1->finish < r2->finish)
1000             r1->finish = r2->finish;
1001           live_range_t temp = r2;
1002           r2 = r2->next;
1003           ira_finish_live_range (temp);
1004           if (r2 == NULL)
1005             {
1006               /* To try to merge with subsequent ranges in r1.  */
1007               r2 = r1->next;
1008               r1->next = NULL;
1009             }
1010         }
1011       else
1012         {
1013           /* Add r1 to the result.  */
1014           if (first == NULL)
1015             first = last = r1;
1016           else
1017             {
1018               last->next = r1;
1019               last = r1;
1020             }
1021           r1 = r1->next;
1022           if (r1 == NULL)
1023             {
1024               /* To try to merge with subsequent ranges in r2.  */
1025               r1 = r2->next;
1026               r2->next = NULL;
1027             }
1028         }
1029     }
1030   if (r1 != NULL)
1031     {
1032       if (first == NULL)
1033         first = r1;
1034       else
1035         last->next = r1;
1036       ira_assert (r1->next == NULL);
1037     }
1038   else if (r2 != NULL)
1039     {
1040       if (first == NULL)
1041         first = r2;
1042       else
1043         last->next = r2;
1044       ira_assert (r2->next == NULL);
1045     }
1046   else
1047     {
1048       ira_assert (last->next == NULL);
1049     }
1050   return first;
1051 }
1052
1053 /* Return TRUE if live ranges R1 and R2 intersect.  */
1054 bool
1055 ira_live_ranges_intersect_p (live_range_t r1, live_range_t r2)
1056 {
1057   /* Remember the live ranges are always kept ordered.  */
1058   while (r1 != NULL && r2 != NULL)
1059     {
1060       if (r1->start > r2->finish)
1061         r1 = r1->next;
1062       else if (r2->start > r1->finish)
1063         r2 = r2->next;
1064       else
1065         return true;
1066     }
1067   return false;
1068 }
1069
1070 /* Free allocno live range R.  */
1071 void
1072 ira_finish_live_range (live_range_t r)
1073 {
1074   live_range_pool.remove (r);
1075 }
1076
1077 /* Free list of allocno live ranges starting with R.  */
1078 void
1079 ira_finish_live_range_list (live_range_t r)
1080 {
1081   live_range_t next_r;
1082
1083   for (; r != NULL; r = next_r)
1084     {
1085       next_r = r->next;
1086       ira_finish_live_range (r);
1087     }
1088 }
1089
1090 /* Free updated register costs of allocno A.  */
1091 void
1092 ira_free_allocno_updated_costs (ira_allocno_t a)
1093 {
1094   enum reg_class aclass;
1095
1096   aclass = ALLOCNO_CLASS (a);
1097   if (ALLOCNO_UPDATED_HARD_REG_COSTS (a) != NULL)
1098     ira_free_cost_vector (ALLOCNO_UPDATED_HARD_REG_COSTS (a), aclass);
1099   ALLOCNO_UPDATED_HARD_REG_COSTS (a) = NULL;
1100   if (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) != NULL)
1101     ira_free_cost_vector (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a),
1102                           aclass);
1103   ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) = NULL;
1104 }
1105
1106 /* Free and nullify all cost vectors allocated earlier for allocno
1107    A.  */
1108 static void
1109 ira_free_allocno_costs (ira_allocno_t a)
1110 {
1111   enum reg_class aclass = ALLOCNO_CLASS (a);
1112   ira_object_t obj;
1113   ira_allocno_object_iterator oi;
1114
1115   FOR_EACH_ALLOCNO_OBJECT (a, obj, oi)
1116     {
1117       ira_finish_live_range_list (OBJECT_LIVE_RANGES (obj));
1118       ira_object_id_map[OBJECT_CONFLICT_ID (obj)] = NULL;
1119       if (OBJECT_CONFLICT_ARRAY (obj) != NULL)
1120         ira_free (OBJECT_CONFLICT_ARRAY (obj));
1121       object_pool.remove (obj);
1122     }
1123
1124   ira_allocnos[ALLOCNO_NUM (a)] = NULL;
1125   if (ALLOCNO_HARD_REG_COSTS (a) != NULL)
1126     ira_free_cost_vector (ALLOCNO_HARD_REG_COSTS (a), aclass);
1127   if (ALLOCNO_CONFLICT_HARD_REG_COSTS (a) != NULL)
1128     ira_free_cost_vector (ALLOCNO_CONFLICT_HARD_REG_COSTS (a), aclass);
1129   if (ALLOCNO_UPDATED_HARD_REG_COSTS (a) != NULL)
1130     ira_free_cost_vector (ALLOCNO_UPDATED_HARD_REG_COSTS (a), aclass);
1131   if (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) != NULL)
1132     ira_free_cost_vector (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a),
1133                           aclass);
1134   ALLOCNO_HARD_REG_COSTS (a) = NULL;
1135   ALLOCNO_CONFLICT_HARD_REG_COSTS (a) = NULL;
1136   ALLOCNO_UPDATED_HARD_REG_COSTS (a) = NULL;
1137   ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) = NULL;
1138 }
1139
1140 /* Free the memory allocated for allocno A.  */
1141 static void
1142 finish_allocno (ira_allocno_t a)
1143 {
1144   ira_free_allocno_costs (a);
1145   allocno_pool.remove (a);
1146 }
1147
1148 /* Free the memory allocated for all allocnos.  */
1149 static void
1150 finish_allocnos (void)
1151 {
1152   ira_allocno_t a;
1153   ira_allocno_iterator ai;
1154
1155   FOR_EACH_ALLOCNO (a, ai)
1156     finish_allocno (a);
1157   ira_free (ira_regno_allocno_map);
1158   ira_object_id_map_vec.release ();
1159   allocno_vec.release ();
1160   allocno_pool.release ();
1161   object_pool.release ();
1162   live_range_pool.release ();
1163 }
1164
1165 \f
1166
1167 /* Pools for allocno preferences.  */
1168 static object_allocator <ira_allocno_pref> pref_pool ("prefs");
1169
1170 /* Vec containing references to all created preferences.  It is a
1171    container of array ira_prefs.  */
1172 static vec<ira_pref_t> pref_vec;
1173
1174 /* The function initializes data concerning allocno prefs.  */
1175 static void
1176 initiate_prefs (void)
1177 {
1178   pref_vec.create (get_max_uid ());
1179   ira_prefs = NULL;
1180   ira_prefs_num = 0;
1181 }
1182
1183 /* Return pref for A and HARD_REGNO if any.  */
1184 static ira_pref_t
1185 find_allocno_pref (ira_allocno_t a, int hard_regno)
1186 {
1187   ira_pref_t pref;
1188
1189   for (pref = ALLOCNO_PREFS (a); pref != NULL; pref = pref->next_pref)
1190     if (pref->allocno == a && pref->hard_regno == hard_regno)
1191       return pref;
1192   return NULL;
1193 }
1194
1195 /* Create and return pref with given attributes A, HARD_REGNO, and FREQ.  */
1196 ira_pref_t
1197 ira_create_pref (ira_allocno_t a, int hard_regno, int freq)
1198 {
1199   ira_pref_t pref;
1200
1201   pref = pref_pool.allocate ();
1202   pref->num = ira_prefs_num;
1203   pref->allocno = a;
1204   pref->hard_regno = hard_regno;
1205   pref->freq = freq;
1206   pref_vec.safe_push (pref);
1207   ira_prefs = pref_vec.address ();
1208   ira_prefs_num = pref_vec.length ();
1209   return pref;
1210 }
1211
1212 /* Attach a pref PREF to the corresponding allocno.  */
1213 static void
1214 add_allocno_pref_to_list (ira_pref_t pref)
1215 {
1216   ira_allocno_t a = pref->allocno;
1217
1218   pref->next_pref = ALLOCNO_PREFS (a);
1219   ALLOCNO_PREFS (a) = pref;
1220 }
1221
1222 /* Create (or update frequency if the pref already exists) the pref of
1223    allocnos A preferring HARD_REGNO with frequency FREQ.  */
1224 void
1225 ira_add_allocno_pref (ira_allocno_t a, int hard_regno, int freq)
1226 {
1227   ira_pref_t pref;
1228
1229   if (freq <= 0)
1230     return;
1231   if ((pref = find_allocno_pref (a, hard_regno)) != NULL)
1232     {
1233       pref->freq += freq;
1234       return;
1235     }
1236   pref = ira_create_pref (a, hard_regno, freq);
1237   ira_assert (a != NULL);
1238   add_allocno_pref_to_list (pref);
1239 }
1240
1241 /* Print info about PREF into file F.  */
1242 static void
1243 print_pref (FILE *f, ira_pref_t pref)
1244 {
1245   fprintf (f, "  pref%d:a%d(r%d)<-hr%d@%d\n", pref->num,
1246            ALLOCNO_NUM (pref->allocno), ALLOCNO_REGNO (pref->allocno),
1247            pref->hard_regno, pref->freq);
1248 }
1249
1250 /* Print info about PREF into stderr.  */
1251 void
1252 ira_debug_pref (ira_pref_t pref)
1253 {
1254   print_pref (stderr, pref);
1255 }
1256
1257 /* Print info about all prefs into file F.  */
1258 static void
1259 print_prefs (FILE *f)
1260 {
1261   ira_pref_t pref;
1262   ira_pref_iterator pi;
1263
1264   FOR_EACH_PREF (pref, pi)
1265     print_pref (f, pref);
1266 }
1267
1268 /* Print info about all prefs into stderr.  */
1269 void
1270 ira_debug_prefs (void)
1271 {
1272   print_prefs (stderr);
1273 }
1274
1275 /* Print info about prefs involving allocno A into file F.  */
1276 static void
1277 print_allocno_prefs (FILE *f, ira_allocno_t a)
1278 {
1279   ira_pref_t pref;
1280
1281   fprintf (f, " a%d(r%d):", ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
1282   for (pref = ALLOCNO_PREFS (a); pref != NULL; pref = pref->next_pref)
1283     fprintf (f, " pref%d:hr%d@%d", pref->num, pref->hard_regno, pref->freq);
1284   fprintf (f, "\n");
1285 }
1286
1287 /* Print info about prefs involving allocno A into stderr.  */
1288 void
1289 ira_debug_allocno_prefs (ira_allocno_t a)
1290 {
1291   print_allocno_prefs (stderr, a);
1292 }
1293
1294 /* The function frees memory allocated for PREF.  */
1295 static void
1296 finish_pref (ira_pref_t pref)
1297 {
1298   ira_prefs[pref->num] = NULL;
1299   pref_pool.remove (pref);
1300 }
1301
1302 /* Remove PREF from the list of allocno prefs and free memory for
1303    it.  */
1304 void
1305 ira_remove_pref (ira_pref_t pref)
1306 {
1307   ira_pref_t cpref, prev;
1308
1309   if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
1310     fprintf (ira_dump_file, " Removing pref%d:hr%d@%d\n",
1311              pref->num, pref->hard_regno, pref->freq);
1312   for (prev = NULL, cpref = ALLOCNO_PREFS (pref->allocno);
1313        cpref != NULL;
1314        prev = cpref, cpref = cpref->next_pref)
1315     if (cpref == pref)
1316       break;
1317   ira_assert (cpref != NULL);
1318   if (prev == NULL)
1319     ALLOCNO_PREFS (pref->allocno) = pref->next_pref;
1320   else
1321     prev->next_pref = pref->next_pref;
1322   finish_pref (pref);
1323 }
1324
1325 /* Remove all prefs of allocno A.  */
1326 void
1327 ira_remove_allocno_prefs (ira_allocno_t a)
1328 {
1329   ira_pref_t pref, next_pref;
1330
1331   for (pref = ALLOCNO_PREFS (a); pref != NULL; pref = next_pref)
1332     {
1333       next_pref = pref->next_pref;
1334       finish_pref (pref);
1335     }
1336   ALLOCNO_PREFS (a) = NULL;
1337 }
1338
1339 /* Free memory allocated for all prefs.  */
1340 static void
1341 finish_prefs (void)
1342 {
1343   ira_pref_t pref;
1344   ira_pref_iterator pi;
1345
1346   FOR_EACH_PREF (pref, pi)
1347     finish_pref (pref);
1348   pref_vec.release ();
1349   pref_pool.release ();
1350 }
1351
1352 \f
1353
1354 /* Pools for copies.  */
1355 static object_allocator<ira_allocno_copy> copy_pool ("copies");
1356
1357 /* Vec containing references to all created copies.  It is a
1358    container of array ira_copies.  */
1359 static vec<ira_copy_t> copy_vec;
1360
1361 /* The function initializes data concerning allocno copies.  */
1362 static void
1363 initiate_copies (void)
1364 {
1365   copy_vec.create (get_max_uid ());
1366   ira_copies = NULL;
1367   ira_copies_num = 0;
1368 }
1369
1370 /* Return copy connecting A1 and A2 and originated from INSN of
1371    LOOP_TREE_NODE if any.  */
1372 static ira_copy_t
1373 find_allocno_copy (ira_allocno_t a1, ira_allocno_t a2, rtx_insn *insn,
1374                    ira_loop_tree_node_t loop_tree_node)
1375 {
1376   ira_copy_t cp, next_cp;
1377   ira_allocno_t another_a;
1378
1379   for (cp = ALLOCNO_COPIES (a1); cp != NULL; cp = next_cp)
1380     {
1381       if (cp->first == a1)
1382         {
1383           next_cp = cp->next_first_allocno_copy;
1384           another_a = cp->second;
1385         }
1386       else if (cp->second == a1)
1387         {
1388           next_cp = cp->next_second_allocno_copy;
1389           another_a = cp->first;
1390         }
1391       else
1392         gcc_unreachable ();
1393       if (another_a == a2 && cp->insn == insn
1394           && cp->loop_tree_node == loop_tree_node)
1395         return cp;
1396     }
1397   return NULL;
1398 }
1399
1400 /* Create and return copy with given attributes LOOP_TREE_NODE, FIRST,
1401    SECOND, FREQ, CONSTRAINT_P, and INSN.  */
1402 ira_copy_t
1403 ira_create_copy (ira_allocno_t first, ira_allocno_t second, int freq,
1404                  bool constraint_p, rtx_insn *insn,
1405                  ira_loop_tree_node_t loop_tree_node)
1406 {
1407   ira_copy_t cp;
1408
1409   cp = copy_pool.allocate ();
1410   cp->num = ira_copies_num;
1411   cp->first = first;
1412   cp->second = second;
1413   cp->freq = freq;
1414   cp->constraint_p = constraint_p;
1415   cp->insn = insn;
1416   cp->loop_tree_node = loop_tree_node;
1417   copy_vec.safe_push (cp);
1418   ira_copies = copy_vec.address ();
1419   ira_copies_num = copy_vec.length ();
1420   return cp;
1421 }
1422
1423 /* Attach a copy CP to allocnos involved into the copy.  */
1424 static void
1425 add_allocno_copy_to_list (ira_copy_t cp)
1426 {
1427   ira_allocno_t first = cp->first, second = cp->second;
1428
1429   cp->prev_first_allocno_copy = NULL;
1430   cp->prev_second_allocno_copy = NULL;
1431   cp->next_first_allocno_copy = ALLOCNO_COPIES (first);
1432   if (cp->next_first_allocno_copy != NULL)
1433     {
1434       if (cp->next_first_allocno_copy->first == first)
1435         cp->next_first_allocno_copy->prev_first_allocno_copy = cp;
1436       else
1437         cp->next_first_allocno_copy->prev_second_allocno_copy = cp;
1438     }
1439   cp->next_second_allocno_copy = ALLOCNO_COPIES (second);
1440   if (cp->next_second_allocno_copy != NULL)
1441     {
1442       if (cp->next_second_allocno_copy->second == second)
1443         cp->next_second_allocno_copy->prev_second_allocno_copy = cp;
1444       else
1445         cp->next_second_allocno_copy->prev_first_allocno_copy = cp;
1446     }
1447   ALLOCNO_COPIES (first) = cp;
1448   ALLOCNO_COPIES (second) = cp;
1449 }
1450
1451 /* Make a copy CP a canonical copy where number of the
1452    first allocno is less than the second one.  */
1453 static void
1454 swap_allocno_copy_ends_if_necessary (ira_copy_t cp)
1455 {
1456   if (ALLOCNO_NUM (cp->first) <= ALLOCNO_NUM (cp->second))
1457     return;
1458
1459   std::swap (cp->first, cp->second);
1460   std::swap (cp->prev_first_allocno_copy, cp->prev_second_allocno_copy);
1461   std::swap (cp->next_first_allocno_copy, cp->next_second_allocno_copy);
1462 }
1463
1464 /* Create (or update frequency if the copy already exists) and return
1465    the copy of allocnos FIRST and SECOND with frequency FREQ
1466    corresponding to move insn INSN (if any) and originated from
1467    LOOP_TREE_NODE.  */
1468 ira_copy_t
1469 ira_add_allocno_copy (ira_allocno_t first, ira_allocno_t second, int freq,
1470                       bool constraint_p, rtx_insn *insn,
1471                       ira_loop_tree_node_t loop_tree_node)
1472 {
1473   ira_copy_t cp;
1474
1475   if ((cp = find_allocno_copy (first, second, insn, loop_tree_node)) != NULL)
1476     {
1477       cp->freq += freq;
1478       return cp;
1479     }
1480   cp = ira_create_copy (first, second, freq, constraint_p, insn,
1481                         loop_tree_node);
1482   ira_assert (first != NULL && second != NULL);
1483   add_allocno_copy_to_list (cp);
1484   swap_allocno_copy_ends_if_necessary (cp);
1485   return cp;
1486 }
1487
1488 /* Print info about copy CP into file F.  */
1489 static void
1490 print_copy (FILE *f, ira_copy_t cp)
1491 {
1492   fprintf (f, "  cp%d:a%d(r%d)<->a%d(r%d)@%d:%s\n", cp->num,
1493            ALLOCNO_NUM (cp->first), ALLOCNO_REGNO (cp->first),
1494            ALLOCNO_NUM (cp->second), ALLOCNO_REGNO (cp->second), cp->freq,
1495            cp->insn != NULL
1496            ? "move" : cp->constraint_p ? "constraint" : "shuffle");
1497 }
1498
1499 DEBUG_FUNCTION void
1500 debug (ira_allocno_copy &ref)
1501 {
1502   print_copy (stderr, &ref);
1503 }
1504
1505 DEBUG_FUNCTION void
1506 debug (ira_allocno_copy *ptr)
1507 {
1508   if (ptr)
1509     debug (*ptr);
1510   else
1511     fprintf (stderr, "<nil>\n");
1512 }
1513
1514 /* Print info about copy CP into stderr.  */
1515 void
1516 ira_debug_copy (ira_copy_t cp)
1517 {
1518   print_copy (stderr, cp);
1519 }
1520
1521 /* Print info about all copies into file F.  */
1522 static void
1523 print_copies (FILE *f)
1524 {
1525   ira_copy_t cp;
1526   ira_copy_iterator ci;
1527
1528   FOR_EACH_COPY (cp, ci)
1529     print_copy (f, cp);
1530 }
1531
1532 /* Print info about all copies into stderr.  */
1533 void
1534 ira_debug_copies (void)
1535 {
1536   print_copies (stderr);
1537 }
1538
1539 /* Print info about copies involving allocno A into file F.  */
1540 static void
1541 print_allocno_copies (FILE *f, ira_allocno_t a)
1542 {
1543   ira_allocno_t another_a;
1544   ira_copy_t cp, next_cp;
1545
1546   fprintf (f, " a%d(r%d):", ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
1547   for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
1548     {
1549       if (cp->first == a)
1550         {
1551           next_cp = cp->next_first_allocno_copy;
1552           another_a = cp->second;
1553         }
1554       else if (cp->second == a)
1555         {
1556           next_cp = cp->next_second_allocno_copy;
1557           another_a = cp->first;
1558         }
1559       else
1560         gcc_unreachable ();
1561       fprintf (f, " cp%d:a%d(r%d)@%d", cp->num,
1562                ALLOCNO_NUM (another_a), ALLOCNO_REGNO (another_a), cp->freq);
1563     }
1564   fprintf (f, "\n");
1565 }
1566
1567 DEBUG_FUNCTION void
1568 debug (ira_allocno &ref)
1569 {
1570   print_allocno_copies (stderr, &ref);
1571 }
1572
1573 DEBUG_FUNCTION void
1574 debug (ira_allocno *ptr)
1575 {
1576   if (ptr)
1577     debug (*ptr);
1578   else
1579     fprintf (stderr, "<nil>\n");
1580 }
1581
1582
1583 /* Print info about copies involving allocno A into stderr.  */
1584 void
1585 ira_debug_allocno_copies (ira_allocno_t a)
1586 {
1587   print_allocno_copies (stderr, a);
1588 }
1589
1590 /* The function frees memory allocated for copy CP.  */
1591 static void
1592 finish_copy (ira_copy_t cp)
1593 {
1594   copy_pool.remove (cp);
1595 }
1596
1597
1598 /* Free memory allocated for all copies.  */
1599 static void
1600 finish_copies (void)
1601 {
1602   ira_copy_t cp;
1603   ira_copy_iterator ci;
1604
1605   FOR_EACH_COPY (cp, ci)
1606     finish_copy (cp);
1607   copy_vec.release ();
1608   copy_pool.release ();
1609 }
1610
1611 \f
1612
1613 /* Pools for cost vectors.  It is defined only for allocno classes.  */
1614 static pool_allocator *cost_vector_pool[N_REG_CLASSES];
1615
1616 /* The function initiates work with hard register cost vectors.  It
1617    creates allocation pool for each allocno class.  */
1618 static void
1619 initiate_cost_vectors (void)
1620 {
1621   int i;
1622   enum reg_class aclass;
1623
1624   for (i = 0; i < ira_allocno_classes_num; i++)
1625     {
1626       aclass = ira_allocno_classes[i];
1627       cost_vector_pool[aclass] = new pool_allocator
1628         ("cost vectors", sizeof (int) * (ira_class_hard_regs_num[aclass]));
1629     }
1630 }
1631
1632 /* Allocate and return a cost vector VEC for ACLASS.  */
1633 int *
1634 ira_allocate_cost_vector (reg_class_t aclass)
1635 {
1636   return (int*) cost_vector_pool[(int) aclass]->allocate ();
1637 }
1638
1639 /* Free a cost vector VEC for ACLASS.  */
1640 void
1641 ira_free_cost_vector (int *vec, reg_class_t aclass)
1642 {
1643   ira_assert (vec != NULL);
1644   cost_vector_pool[(int) aclass]->remove (vec);
1645 }
1646
1647 /* Finish work with hard register cost vectors.  Release allocation
1648    pool for each allocno class.  */
1649 static void
1650 finish_cost_vectors (void)
1651 {
1652   int i;
1653   enum reg_class aclass;
1654
1655   for (i = 0; i < ira_allocno_classes_num; i++)
1656     {
1657       aclass = ira_allocno_classes[i];
1658       delete cost_vector_pool[aclass];
1659     }
1660 }
1661
1662 \f
1663
1664 /* Compute a post-ordering of the reverse control flow of the loop body
1665    designated by the children nodes of LOOP_NODE, whose body nodes in
1666    pre-order are input as LOOP_PREORDER.  Return a VEC with a post-order
1667    of the reverse loop body.
1668
1669    For the post-order of the reverse CFG, we visit the basic blocks in
1670    LOOP_PREORDER array in the reverse order of where they appear.
1671    This is important: We do not just want to compute a post-order of
1672    the reverse CFG, we want to make a best-guess for a visiting order that
1673    minimizes the number of chain elements per allocno live range.  If the
1674    blocks would be visited in a different order, we would still compute a
1675    correct post-ordering but it would be less likely that two nodes
1676    connected by an edge in the CFG are neighbors in the topsort.  */
1677
1678 static vec<ira_loop_tree_node_t>
1679 ira_loop_tree_body_rev_postorder (ira_loop_tree_node_t loop_node ATTRIBUTE_UNUSED,
1680                                   vec<ira_loop_tree_node_t> loop_preorder)
1681 {
1682   vec<ira_loop_tree_node_t> topsort_nodes = vNULL;
1683   unsigned int n_loop_preorder;
1684
1685   n_loop_preorder = loop_preorder.length ();
1686   if (n_loop_preorder != 0)
1687     {
1688       ira_loop_tree_node_t subloop_node;
1689       unsigned int i;
1690       auto_vec<ira_loop_tree_node_t> dfs_stack;
1691
1692       /* This is a bit of strange abuse of the BB_VISITED flag:  We use
1693          the flag to mark blocks we still have to visit to add them to
1694          our post-order.  Define an alias to avoid confusion.  */
1695 #define BB_TO_VISIT BB_VISITED
1696
1697       FOR_EACH_VEC_ELT (loop_preorder, i, subloop_node)
1698         {
1699           gcc_checking_assert (! (subloop_node->bb->flags & BB_TO_VISIT));
1700           subloop_node->bb->flags |= BB_TO_VISIT;
1701         }
1702
1703       topsort_nodes.create (n_loop_preorder);
1704       dfs_stack.create (n_loop_preorder);
1705
1706       FOR_EACH_VEC_ELT_REVERSE (loop_preorder, i, subloop_node)
1707         {
1708           if (! (subloop_node->bb->flags & BB_TO_VISIT))
1709             continue;
1710
1711           subloop_node->bb->flags &= ~BB_TO_VISIT;
1712           dfs_stack.quick_push (subloop_node);
1713           while (! dfs_stack.is_empty ())
1714             {
1715               edge e;
1716               edge_iterator ei;
1717
1718               ira_loop_tree_node_t n = dfs_stack.last ();
1719               FOR_EACH_EDGE (e, ei, n->bb->preds)
1720                 {
1721                   ira_loop_tree_node_t pred_node;
1722                   basic_block pred_bb = e->src;
1723
1724                   if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1725                     continue;
1726
1727                   pred_node = IRA_BB_NODE_BY_INDEX (pred_bb->index);
1728                   if (pred_node != n
1729                       && (pred_node->bb->flags & BB_TO_VISIT))
1730                     {
1731                       pred_node->bb->flags &= ~BB_TO_VISIT;
1732                       dfs_stack.quick_push (pred_node);
1733                     }
1734                 }
1735               if (n == dfs_stack.last ())
1736                 {
1737                   dfs_stack.pop ();
1738                   topsort_nodes.quick_push (n);
1739                 }
1740             }
1741         }
1742
1743 #undef BB_TO_VISIT
1744     }
1745
1746   gcc_assert (topsort_nodes.length () == n_loop_preorder);
1747   return topsort_nodes;
1748 }
1749
1750 /* The current loop tree node and its regno allocno map.  */
1751 ira_loop_tree_node_t ira_curr_loop_tree_node;
1752 ira_allocno_t *ira_curr_regno_allocno_map;
1753
1754 /* This recursive function traverses loop tree with root LOOP_NODE
1755    calling non-null functions PREORDER_FUNC and POSTORDER_FUNC
1756    correspondingly in preorder and postorder.  The function sets up
1757    IRA_CURR_LOOP_TREE_NODE and IRA_CURR_REGNO_ALLOCNO_MAP.  If BB_P,
1758    basic block nodes of LOOP_NODE is also processed (before its
1759    subloop nodes).
1760
1761    If BB_P is set and POSTORDER_FUNC is given, the basic blocks in
1762    the loop are passed in the *reverse* post-order of the *reverse*
1763    CFG.  This is only used by ira_create_allocno_live_ranges, which
1764    wants to visit basic blocks in this order to minimize the number
1765    of elements per live range chain.
1766    Note that the loop tree nodes are still visited in the normal,
1767    forward post-order of  the loop tree.  */
1768
1769 void
1770 ira_traverse_loop_tree (bool bb_p, ira_loop_tree_node_t loop_node,
1771                         void (*preorder_func) (ira_loop_tree_node_t),
1772                         void (*postorder_func) (ira_loop_tree_node_t))
1773 {
1774   ira_loop_tree_node_t subloop_node;
1775
1776   ira_assert (loop_node->bb == NULL);
1777   ira_curr_loop_tree_node = loop_node;
1778   ira_curr_regno_allocno_map = ira_curr_loop_tree_node->regno_allocno_map;
1779
1780   if (preorder_func != NULL)
1781     (*preorder_func) (loop_node);
1782
1783   if (bb_p)
1784     {
1785       auto_vec<ira_loop_tree_node_t> loop_preorder;
1786       unsigned int i;
1787
1788       /* Add all nodes to the set of nodes to visit.  The IRA loop tree
1789          is set up such that nodes in the loop body appear in a pre-order
1790          of their place in the CFG.  */
1791       for (subloop_node = loop_node->children;
1792            subloop_node != NULL;
1793            subloop_node = subloop_node->next)
1794         if (subloop_node->bb != NULL)
1795           loop_preorder.safe_push (subloop_node);
1796
1797       if (preorder_func != NULL)
1798         FOR_EACH_VEC_ELT (loop_preorder, i, subloop_node)
1799           (*preorder_func) (subloop_node);
1800
1801       if (postorder_func != NULL)
1802         {
1803           vec<ira_loop_tree_node_t> loop_rev_postorder =
1804             ira_loop_tree_body_rev_postorder (loop_node, loop_preorder);
1805           FOR_EACH_VEC_ELT_REVERSE (loop_rev_postorder, i, subloop_node)
1806             (*postorder_func) (subloop_node);
1807           loop_rev_postorder.release ();
1808         }
1809     }
1810
1811   for (subloop_node = loop_node->subloops;
1812        subloop_node != NULL;
1813        subloop_node = subloop_node->subloop_next)
1814     {
1815       ira_assert (subloop_node->bb == NULL);
1816       ira_traverse_loop_tree (bb_p, subloop_node,
1817                               preorder_func, postorder_func);
1818     }
1819
1820   ira_curr_loop_tree_node = loop_node;
1821   ira_curr_regno_allocno_map = ira_curr_loop_tree_node->regno_allocno_map;
1822
1823   if (postorder_func != NULL)
1824     (*postorder_func) (loop_node);
1825 }
1826
1827 \f
1828
1829 /* The basic block currently being processed.  */
1830 static basic_block curr_bb;
1831
1832 /* This recursive function creates allocnos corresponding to
1833    pseudo-registers containing in X.  True OUTPUT_P means that X is
1834    an lvalue.  PARENT corresponds to the parent expression of X.  */
1835 static void
1836 create_insn_allocnos (rtx x, rtx outer, bool output_p)
1837 {
1838   int i, j;
1839   const char *fmt;
1840   enum rtx_code code = GET_CODE (x);
1841
1842   if (code == REG)
1843     {
1844       int regno;
1845
1846       if ((regno = REGNO (x)) >= FIRST_PSEUDO_REGISTER)
1847         {
1848           ira_allocno_t a;
1849
1850           if ((a = ira_curr_regno_allocno_map[regno]) == NULL)
1851             {
1852               a = ira_create_allocno (regno, false, ira_curr_loop_tree_node);
1853               if (outer != NULL && GET_CODE (outer) == SUBREG)
1854                 {
1855                   machine_mode wmode = GET_MODE (outer);
1856                   if (partial_subreg_p (ALLOCNO_WMODE (a), wmode))
1857                     ALLOCNO_WMODE (a) = wmode;
1858                 }
1859             }
1860
1861           ALLOCNO_NREFS (a)++;
1862           ALLOCNO_FREQ (a) += REG_FREQ_FROM_BB (curr_bb);
1863           if (output_p)
1864             bitmap_set_bit (ira_curr_loop_tree_node->modified_regnos, regno);
1865         }
1866       return;
1867     }
1868   else if (code == SET)
1869     {
1870       create_insn_allocnos (SET_DEST (x), NULL, true);
1871       create_insn_allocnos (SET_SRC (x), NULL, false);
1872       return;
1873     }
1874   else if (code == CLOBBER)
1875     {
1876       create_insn_allocnos (XEXP (x, 0), NULL, true);
1877       return;
1878     }
1879   else if (code == MEM)
1880     {
1881       create_insn_allocnos (XEXP (x, 0), NULL, false);
1882       return;
1883     }
1884   else if (code == PRE_DEC || code == POST_DEC || code == PRE_INC ||
1885            code == POST_INC || code == POST_MODIFY || code == PRE_MODIFY)
1886     {
1887       create_insn_allocnos (XEXP (x, 0), NULL, true);
1888       create_insn_allocnos (XEXP (x, 0), NULL, false);
1889       return;
1890     }
1891
1892   fmt = GET_RTX_FORMAT (code);
1893   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1894     {
1895       if (fmt[i] == 'e')
1896         create_insn_allocnos (XEXP (x, i), x, output_p);
1897       else if (fmt[i] == 'E')
1898         for (j = 0; j < XVECLEN (x, i); j++)
1899           create_insn_allocnos (XVECEXP (x, i, j), x, output_p);
1900     }
1901 }
1902
1903 /* Create allocnos corresponding to pseudo-registers living in the
1904    basic block represented by the corresponding loop tree node
1905    BB_NODE.  */
1906 static void
1907 create_bb_allocnos (ira_loop_tree_node_t bb_node)
1908 {
1909   basic_block bb;
1910   rtx_insn *insn;
1911   unsigned int i;
1912   bitmap_iterator bi;
1913
1914   curr_bb = bb = bb_node->bb;
1915   ira_assert (bb != NULL);
1916   FOR_BB_INSNS_REVERSE (bb, insn)
1917     if (NONDEBUG_INSN_P (insn))
1918       create_insn_allocnos (PATTERN (insn), NULL, false);
1919   /* It might be a allocno living through from one subloop to
1920      another.  */
1921   EXECUTE_IF_SET_IN_REG_SET (df_get_live_in (bb), FIRST_PSEUDO_REGISTER, i, bi)
1922     if (ira_curr_regno_allocno_map[i] == NULL)
1923       ira_create_allocno (i, false, ira_curr_loop_tree_node);
1924 }
1925
1926 /* Create allocnos corresponding to pseudo-registers living on edge E
1927    (a loop entry or exit).  Also mark the allocnos as living on the
1928    loop border. */
1929 static void
1930 create_loop_allocnos (edge e)
1931 {
1932   unsigned int i;
1933   bitmap live_in_regs, border_allocnos;
1934   bitmap_iterator bi;
1935   ira_loop_tree_node_t parent;
1936
1937   live_in_regs = df_get_live_in (e->dest);
1938   border_allocnos = ira_curr_loop_tree_node->border_allocnos;
1939   EXECUTE_IF_SET_IN_REG_SET (df_get_live_out (e->src),
1940                              FIRST_PSEUDO_REGISTER, i, bi)
1941     if (bitmap_bit_p (live_in_regs, i))
1942       {
1943         if (ira_curr_regno_allocno_map[i] == NULL)
1944           {
1945             /* The order of creations is important for right
1946                ira_regno_allocno_map.  */
1947             if ((parent = ira_curr_loop_tree_node->parent) != NULL
1948                 && parent->regno_allocno_map[i] == NULL)
1949               ira_create_allocno (i, false, parent);
1950             ira_create_allocno (i, false, ira_curr_loop_tree_node);
1951           }
1952         bitmap_set_bit (border_allocnos,
1953                         ALLOCNO_NUM (ira_curr_regno_allocno_map[i]));
1954       }
1955 }
1956
1957 /* Create allocnos corresponding to pseudo-registers living in loop
1958    represented by the corresponding loop tree node LOOP_NODE.  This
1959    function is called by ira_traverse_loop_tree.  */
1960 static void
1961 create_loop_tree_node_allocnos (ira_loop_tree_node_t loop_node)
1962 {
1963   if (loop_node->bb != NULL)
1964     create_bb_allocnos (loop_node);
1965   else if (loop_node != ira_loop_tree_root)
1966     {
1967       int i;
1968       edge_iterator ei;
1969       edge e;
1970       vec<edge> edges;
1971
1972       ira_assert (current_loops != NULL);
1973       FOR_EACH_EDGE (e, ei, loop_node->loop->header->preds)
1974         if (e->src != loop_node->loop->latch)
1975           create_loop_allocnos (e);
1976
1977       edges = get_loop_exit_edges (loop_node->loop);
1978       FOR_EACH_VEC_ELT (edges, i, e)
1979         create_loop_allocnos (e);
1980       edges.release ();
1981     }
1982 }
1983
1984 /* Propagate information about allocnos modified inside the loop given
1985    by its LOOP_TREE_NODE to its parent.  */
1986 static void
1987 propagate_modified_regnos (ira_loop_tree_node_t loop_tree_node)
1988 {
1989   if (loop_tree_node == ira_loop_tree_root)
1990     return;
1991   ira_assert (loop_tree_node->bb == NULL);
1992   bitmap_ior_into (loop_tree_node->parent->modified_regnos,
1993                    loop_tree_node->modified_regnos);
1994 }
1995
1996 /* Propagate new info about allocno A (see comments about accumulated
1997    info in allocno definition) to the corresponding allocno on upper
1998    loop tree level.  So allocnos on upper levels accumulate
1999    information about the corresponding allocnos in nested regions.
2000    The new info means allocno info finally calculated in this
2001    file.  */
2002 static void
2003 propagate_allocno_info (void)
2004 {
2005   int i;
2006   ira_allocno_t a, parent_a;
2007   ira_loop_tree_node_t parent;
2008   enum reg_class aclass;
2009
2010   if (flag_ira_region != IRA_REGION_ALL
2011       && flag_ira_region != IRA_REGION_MIXED)
2012     return;
2013   for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--)
2014     for (a = ira_regno_allocno_map[i];
2015          a != NULL;
2016          a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
2017       if ((parent = ALLOCNO_LOOP_TREE_NODE (a)->parent) != NULL
2018           && (parent_a = parent->regno_allocno_map[i]) != NULL
2019           /* There are no caps yet at this point.  So use
2020              border_allocnos to find allocnos for the propagation.  */
2021           && bitmap_bit_p (ALLOCNO_LOOP_TREE_NODE (a)->border_allocnos,
2022                            ALLOCNO_NUM (a)))
2023         {
2024           if (! ALLOCNO_BAD_SPILL_P (a))
2025             ALLOCNO_BAD_SPILL_P (parent_a) = false;
2026           ALLOCNO_NREFS (parent_a) += ALLOCNO_NREFS (a);
2027           ALLOCNO_FREQ (parent_a) += ALLOCNO_FREQ (a);
2028           ALLOCNO_CALL_FREQ (parent_a) += ALLOCNO_CALL_FREQ (a);
2029           merge_hard_reg_conflicts (a, parent_a, true);
2030           ALLOCNO_CALLS_CROSSED_NUM (parent_a)
2031             += ALLOCNO_CALLS_CROSSED_NUM (a);
2032           ALLOCNO_CHEAP_CALLS_CROSSED_NUM (parent_a)
2033             += ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a);
2034           IOR_HARD_REG_SET (ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS (parent_a),
2035                             ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS (a));
2036           ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (parent_a)
2037             += ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a);
2038           aclass = ALLOCNO_CLASS (a);
2039           ira_assert (aclass == ALLOCNO_CLASS (parent_a));
2040           ira_allocate_and_accumulate_costs
2041             (&ALLOCNO_HARD_REG_COSTS (parent_a), aclass,
2042              ALLOCNO_HARD_REG_COSTS (a));
2043           ira_allocate_and_accumulate_costs
2044             (&ALLOCNO_CONFLICT_HARD_REG_COSTS (parent_a),
2045              aclass,
2046              ALLOCNO_CONFLICT_HARD_REG_COSTS (a));
2047           ALLOCNO_CLASS_COST (parent_a)
2048             += ALLOCNO_CLASS_COST (a);
2049           ALLOCNO_MEMORY_COST (parent_a) += ALLOCNO_MEMORY_COST (a);
2050         }
2051 }
2052
2053 /* Create allocnos corresponding to pseudo-registers in the current
2054    function.  Traverse the loop tree for this.  */
2055 static void
2056 create_allocnos (void)
2057 {
2058   /* We need to process BB first to correctly link allocnos by member
2059      next_regno_allocno.  */
2060   ira_traverse_loop_tree (true, ira_loop_tree_root,
2061                           create_loop_tree_node_allocnos, NULL);
2062   if (optimize)
2063     ira_traverse_loop_tree (false, ira_loop_tree_root, NULL,
2064                             propagate_modified_regnos);
2065 }
2066
2067 \f
2068
2069 /* The page contains function to remove some regions from a separate
2070    register allocation.  We remove regions whose separate allocation
2071    will hardly improve the result.  As a result we speed up regional
2072    register allocation.  */
2073
2074 /* The function changes the object in range list given by R to OBJ.  */
2075 static void
2076 change_object_in_range_list (live_range_t r, ira_object_t obj)
2077 {
2078   for (; r != NULL; r = r->next)
2079     r->object = obj;
2080 }
2081
2082 /* Move all live ranges associated with allocno FROM to allocno TO.  */
2083 static void
2084 move_allocno_live_ranges (ira_allocno_t from, ira_allocno_t to)
2085 {
2086   int i;
2087   int n = ALLOCNO_NUM_OBJECTS (from);
2088
2089   gcc_assert (n == ALLOCNO_NUM_OBJECTS (to));
2090
2091   for (i = 0; i < n; i++)
2092     {
2093       ira_object_t from_obj = ALLOCNO_OBJECT (from, i);
2094       ira_object_t to_obj = ALLOCNO_OBJECT (to, i);
2095       live_range_t lr = OBJECT_LIVE_RANGES (from_obj);
2096
2097       if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL)
2098         {
2099           fprintf (ira_dump_file,
2100                    "      Moving ranges of a%dr%d to a%dr%d: ",
2101                    ALLOCNO_NUM (from), ALLOCNO_REGNO (from),
2102                    ALLOCNO_NUM (to), ALLOCNO_REGNO (to));
2103           ira_print_live_range_list (ira_dump_file, lr);
2104         }
2105       change_object_in_range_list (lr, to_obj);
2106       OBJECT_LIVE_RANGES (to_obj)
2107         = ira_merge_live_ranges (lr, OBJECT_LIVE_RANGES (to_obj));
2108       OBJECT_LIVE_RANGES (from_obj) = NULL;
2109     }
2110 }
2111
2112 static void
2113 copy_allocno_live_ranges (ira_allocno_t from, ira_allocno_t to)
2114 {
2115   int i;
2116   int n = ALLOCNO_NUM_OBJECTS (from);
2117
2118   gcc_assert (n == ALLOCNO_NUM_OBJECTS (to));
2119
2120   for (i = 0; i < n; i++)
2121     {
2122       ira_object_t from_obj = ALLOCNO_OBJECT (from, i);
2123       ira_object_t to_obj = ALLOCNO_OBJECT (to, i);
2124       live_range_t lr = OBJECT_LIVE_RANGES (from_obj);
2125
2126       if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL)
2127         {
2128           fprintf (ira_dump_file, "      Copying ranges of a%dr%d to a%dr%d: ",
2129                    ALLOCNO_NUM (from), ALLOCNO_REGNO (from),
2130                    ALLOCNO_NUM (to), ALLOCNO_REGNO (to));
2131           ira_print_live_range_list (ira_dump_file, lr);
2132         }
2133       lr = ira_copy_live_range_list (lr);
2134       change_object_in_range_list (lr, to_obj);
2135       OBJECT_LIVE_RANGES (to_obj)
2136         = ira_merge_live_ranges (lr, OBJECT_LIVE_RANGES (to_obj));
2137     }
2138 }
2139
2140 /* Return TRUE if NODE represents a loop with low register
2141    pressure.  */
2142 static bool
2143 low_pressure_loop_node_p (ira_loop_tree_node_t node)
2144 {
2145   int i;
2146   enum reg_class pclass;
2147
2148   if (node->bb != NULL)
2149     return false;
2150
2151   for (i = 0; i < ira_pressure_classes_num; i++)
2152     {
2153       pclass = ira_pressure_classes[i];
2154       if (node->reg_pressure[pclass] > ira_class_hard_regs_num[pclass]
2155           && ira_class_hard_regs_num[pclass] > 1)
2156         return false;
2157     }
2158   return true;
2159 }
2160
2161 #ifdef STACK_REGS
2162 /* Return TRUE if LOOP has a complex enter or exit edge.  We don't
2163    form a region from such loop if the target use stack register
2164    because reg-stack.c can not deal with such edges.  */
2165 static bool
2166 loop_with_complex_edge_p (struct loop *loop)
2167 {
2168   int i;
2169   edge_iterator ei;
2170   edge e;
2171   vec<edge> edges;
2172   bool res;
2173
2174   FOR_EACH_EDGE (e, ei, loop->header->preds)
2175     if (e->flags & EDGE_EH)
2176       return true;
2177   edges = get_loop_exit_edges (loop);
2178   res = false;
2179   FOR_EACH_VEC_ELT (edges, i, e)
2180     if (e->flags & EDGE_COMPLEX)
2181       {
2182         res = true;
2183         break;
2184       }
2185   edges.release ();
2186   return res;
2187 }
2188 #endif
2189
2190 /* Sort loops for marking them for removal.  We put already marked
2191    loops first, then less frequent loops next, and then outer loops
2192    next.  */
2193 static int
2194 loop_compare_func (const void *v1p, const void *v2p)
2195 {
2196   int diff;
2197   ira_loop_tree_node_t l1 = *(const ira_loop_tree_node_t *) v1p;
2198   ira_loop_tree_node_t l2 = *(const ira_loop_tree_node_t *) v2p;
2199
2200   ira_assert (l1->parent != NULL && l2->parent != NULL);
2201   if (l1->to_remove_p && ! l2->to_remove_p)
2202     return -1;
2203   if (! l1->to_remove_p && l2->to_remove_p)
2204     return 1;
2205   if ((diff = l1->loop->header->count.to_frequency (cfun)
2206               - l2->loop->header->count.to_frequency (cfun)) != 0)
2207     return diff;
2208   if ((diff = (int) loop_depth (l1->loop) - (int) loop_depth (l2->loop)) != 0)
2209     return diff;
2210   /* Make sorting stable.  */
2211   return l1->loop_num - l2->loop_num;
2212 }
2213
2214 /* Mark loops which should be removed from regional allocation.  We
2215    remove a loop with low register pressure inside another loop with
2216    register pressure.  In this case a separate allocation of the loop
2217    hardly helps (for irregular register file architecture it could
2218    help by choosing a better hard register in the loop but we prefer
2219    faster allocation even in this case).  We also remove cheap loops
2220    if there are more than IRA_MAX_LOOPS_NUM of them.  Loop with EH
2221    exit or enter edges are removed too because the allocation might
2222    require put pseudo moves on the EH edges (we could still do this
2223    for pseudos with caller saved hard registers in some cases but it
2224    is impossible to say here or during top-down allocation pass what
2225    hard register the pseudos get finally).  */
2226 static void
2227 mark_loops_for_removal (void)
2228 {
2229   int i, n;
2230   ira_loop_tree_node_t *sorted_loops;
2231   loop_p loop;
2232
2233   ira_assert (current_loops != NULL);
2234   sorted_loops
2235     = (ira_loop_tree_node_t *) ira_allocate (sizeof (ira_loop_tree_node_t)
2236                                              * number_of_loops (cfun));
2237   for (n = i = 0; vec_safe_iterate (get_loops (cfun), i, &loop); i++)
2238     if (ira_loop_nodes[i].regno_allocno_map != NULL)
2239       {
2240         if (ira_loop_nodes[i].parent == NULL)
2241           {
2242             /* Don't remove the root.  */
2243             ira_loop_nodes[i].to_remove_p = false;
2244             continue;
2245           }
2246         sorted_loops[n++] = &ira_loop_nodes[i];
2247         ira_loop_nodes[i].to_remove_p
2248           = ((low_pressure_loop_node_p (ira_loop_nodes[i].parent)
2249               && low_pressure_loop_node_p (&ira_loop_nodes[i]))
2250 #ifdef STACK_REGS
2251              || loop_with_complex_edge_p (ira_loop_nodes[i].loop)
2252 #endif
2253              );
2254       }
2255   qsort (sorted_loops, n, sizeof (ira_loop_tree_node_t), loop_compare_func);
2256   for (i = 0; i < n - IRA_MAX_LOOPS_NUM; i++)
2257     {
2258       sorted_loops[i]->to_remove_p = true;
2259       if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
2260         fprintf
2261           (ira_dump_file,
2262            "  Mark loop %d (header %d, freq %d, depth %d) for removal (%s)\n",
2263            sorted_loops[i]->loop_num, sorted_loops[i]->loop->header->index,
2264            sorted_loops[i]->loop->header->count.to_frequency (cfun),
2265            loop_depth (sorted_loops[i]->loop),
2266            low_pressure_loop_node_p (sorted_loops[i]->parent)
2267            && low_pressure_loop_node_p (sorted_loops[i])
2268            ? "low pressure" : "cheap loop");
2269     }
2270   ira_free (sorted_loops);
2271 }
2272
2273 /* Mark all loops but root for removing.  */
2274 static void
2275 mark_all_loops_for_removal (void)
2276 {
2277   int i;
2278   loop_p loop;
2279
2280   ira_assert (current_loops != NULL);
2281   FOR_EACH_VEC_SAFE_ELT (get_loops (cfun), i, loop)
2282     if (ira_loop_nodes[i].regno_allocno_map != NULL)
2283       {
2284         if (ira_loop_nodes[i].parent == NULL)
2285           {
2286             /* Don't remove the root.  */
2287             ira_loop_nodes[i].to_remove_p = false;
2288             continue;
2289           }
2290         ira_loop_nodes[i].to_remove_p = true;
2291         if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
2292           fprintf
2293             (ira_dump_file,
2294              "  Mark loop %d (header %d, freq %d, depth %d) for removal\n",
2295              ira_loop_nodes[i].loop_num,
2296              ira_loop_nodes[i].loop->header->index,
2297              ira_loop_nodes[i].loop->header->count.to_frequency (cfun),
2298              loop_depth (ira_loop_nodes[i].loop));
2299       }
2300 }
2301
2302 /* Definition of vector of loop tree nodes.  */
2303
2304 /* Vec containing references to all removed loop tree nodes.  */
2305 static vec<ira_loop_tree_node_t> removed_loop_vec;
2306
2307 /* Vec containing references to all children of loop tree nodes.  */
2308 static vec<ira_loop_tree_node_t> children_vec;
2309
2310 /* Remove subregions of NODE if their separate allocation will not
2311    improve the result.  */
2312 static void
2313 remove_uneccesary_loop_nodes_from_loop_tree (ira_loop_tree_node_t node)
2314 {
2315   unsigned int start;
2316   bool remove_p;
2317   ira_loop_tree_node_t subnode;
2318
2319   remove_p = node->to_remove_p;
2320   if (! remove_p)
2321     children_vec.safe_push (node);
2322   start = children_vec.length ();
2323   for (subnode = node->children; subnode != NULL; subnode = subnode->next)
2324     if (subnode->bb == NULL)
2325       remove_uneccesary_loop_nodes_from_loop_tree (subnode);
2326     else
2327       children_vec.safe_push (subnode);
2328   node->children = node->subloops = NULL;
2329   if (remove_p)
2330     {
2331       removed_loop_vec.safe_push (node);
2332       return;
2333     }
2334   while (children_vec.length () > start)
2335     {
2336       subnode = children_vec.pop ();
2337       subnode->parent = node;
2338       subnode->next = node->children;
2339       node->children = subnode;
2340       if (subnode->bb == NULL)
2341         {
2342           subnode->subloop_next = node->subloops;
2343           node->subloops = subnode;
2344         }
2345     }
2346 }
2347
2348 /* Return TRUE if NODE is inside PARENT.  */
2349 static bool
2350 loop_is_inside_p (ira_loop_tree_node_t node, ira_loop_tree_node_t parent)
2351 {
2352   for (node = node->parent; node != NULL; node = node->parent)
2353     if (node == parent)
2354       return true;
2355   return false;
2356 }
2357
2358 /* Sort allocnos according to their order in regno allocno list.  */
2359 static int
2360 regno_allocno_order_compare_func (const void *v1p, const void *v2p)
2361 {
2362   ira_allocno_t a1 = *(const ira_allocno_t *) v1p;
2363   ira_allocno_t a2 = *(const ira_allocno_t *) v2p;
2364   ira_loop_tree_node_t n1 = ALLOCNO_LOOP_TREE_NODE (a1);
2365   ira_loop_tree_node_t n2 = ALLOCNO_LOOP_TREE_NODE (a2);
2366
2367   if (loop_is_inside_p (n1, n2))
2368     return -1;
2369   else if (loop_is_inside_p (n2, n1))
2370     return 1;
2371   /* If allocnos are equally good, sort by allocno numbers, so that
2372      the results of qsort leave nothing to chance.  We put allocnos
2373      with higher number first in the list because it is the original
2374      order for allocnos from loops on the same levels.  */
2375   return ALLOCNO_NUM (a2) - ALLOCNO_NUM (a1);
2376 }
2377
2378 /* This array is used to sort allocnos to restore allocno order in
2379    the regno allocno list.  */
2380 static ira_allocno_t *regno_allocnos;
2381
2382 /* Restore allocno order for REGNO in the regno allocno list.  */
2383 static void
2384 ira_rebuild_regno_allocno_list (int regno)
2385 {
2386   int i, n;
2387   ira_allocno_t a;
2388
2389   for (n = 0, a = ira_regno_allocno_map[regno];
2390        a != NULL;
2391        a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
2392     regno_allocnos[n++] = a;
2393   ira_assert (n > 0);
2394   qsort (regno_allocnos, n, sizeof (ira_allocno_t),
2395          regno_allocno_order_compare_func);
2396   for (i = 1; i < n; i++)
2397     ALLOCNO_NEXT_REGNO_ALLOCNO (regno_allocnos[i - 1]) = regno_allocnos[i];
2398   ALLOCNO_NEXT_REGNO_ALLOCNO (regno_allocnos[n - 1]) = NULL;
2399   ira_regno_allocno_map[regno] = regno_allocnos[0];
2400   if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
2401     fprintf (ira_dump_file, " Rebuilding regno allocno list for %d\n", regno);
2402 }
2403
2404 /* Propagate info from allocno FROM_A to allocno A.  */
2405 static void
2406 propagate_some_info_from_allocno (ira_allocno_t a, ira_allocno_t from_a)
2407 {
2408   enum reg_class aclass;
2409
2410   merge_hard_reg_conflicts (from_a, a, false);
2411   ALLOCNO_NREFS (a) += ALLOCNO_NREFS (from_a);
2412   ALLOCNO_FREQ (a) += ALLOCNO_FREQ (from_a);
2413   ALLOCNO_CALL_FREQ (a) += ALLOCNO_CALL_FREQ (from_a);
2414   ALLOCNO_CALLS_CROSSED_NUM (a) += ALLOCNO_CALLS_CROSSED_NUM (from_a);
2415   ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a)
2416     += ALLOCNO_CHEAP_CALLS_CROSSED_NUM (from_a);
2417   IOR_HARD_REG_SET (ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS (a),
2418                     ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS (from_a));
2419
2420   ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a)
2421     += ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (from_a);
2422   if (! ALLOCNO_BAD_SPILL_P (from_a))
2423     ALLOCNO_BAD_SPILL_P (a) = false;
2424   aclass = ALLOCNO_CLASS (from_a);
2425   ira_assert (aclass == ALLOCNO_CLASS (a));
2426   ira_allocate_and_accumulate_costs (&ALLOCNO_HARD_REG_COSTS (a), aclass,
2427                                      ALLOCNO_HARD_REG_COSTS (from_a));
2428   ira_allocate_and_accumulate_costs (&ALLOCNO_CONFLICT_HARD_REG_COSTS (a),
2429                                      aclass,
2430                                      ALLOCNO_CONFLICT_HARD_REG_COSTS (from_a));
2431   ALLOCNO_CLASS_COST (a) += ALLOCNO_CLASS_COST (from_a);
2432   ALLOCNO_MEMORY_COST (a) += ALLOCNO_MEMORY_COST (from_a);
2433 }
2434
2435 /* Remove allocnos from loops removed from the allocation
2436    consideration.  */
2437 static void
2438 remove_unnecessary_allocnos (void)
2439 {
2440   int regno;
2441   bool merged_p, rebuild_p;
2442   ira_allocno_t a, prev_a, next_a, parent_a;
2443   ira_loop_tree_node_t a_node, parent;
2444
2445   merged_p = false;
2446   regno_allocnos = NULL;
2447   for (regno = max_reg_num () - 1; regno >= FIRST_PSEUDO_REGISTER; regno--)
2448     {
2449       rebuild_p = false;
2450       for (prev_a = NULL, a = ira_regno_allocno_map[regno];
2451            a != NULL;
2452            a = next_a)
2453         {
2454           next_a = ALLOCNO_NEXT_REGNO_ALLOCNO (a);
2455           a_node = ALLOCNO_LOOP_TREE_NODE (a);
2456           if (! a_node->to_remove_p)
2457             prev_a = a;
2458           else
2459             {
2460               for (parent = a_node->parent;
2461                    (parent_a = parent->regno_allocno_map[regno]) == NULL
2462                      && parent->to_remove_p;
2463                    parent = parent->parent)
2464                 ;
2465               if (parent_a == NULL)
2466                 {
2467                   /* There are no allocnos with the same regno in
2468                      upper region -- just move the allocno to the
2469                      upper region.  */
2470                   prev_a = a;
2471                   ALLOCNO_LOOP_TREE_NODE (a) = parent;
2472                   parent->regno_allocno_map[regno] = a;
2473                   bitmap_set_bit (parent->all_allocnos, ALLOCNO_NUM (a));
2474                   rebuild_p = true;
2475                 }
2476               else
2477                 {
2478                   /* Remove the allocno and update info of allocno in
2479                      the upper region.  */
2480                   if (prev_a == NULL)
2481                     ira_regno_allocno_map[regno] = next_a;
2482                   else
2483                     ALLOCNO_NEXT_REGNO_ALLOCNO (prev_a) = next_a;
2484                   move_allocno_live_ranges (a, parent_a);
2485                   merged_p = true;
2486                   propagate_some_info_from_allocno (parent_a, a);
2487                   /* Remove it from the corresponding regno allocno
2488                      map to avoid info propagation of subsequent
2489                      allocno into this already removed allocno.  */
2490                   a_node->regno_allocno_map[regno] = NULL;
2491                   ira_remove_allocno_prefs (a);
2492                   finish_allocno (a);
2493                 }
2494             }
2495         }
2496       if (rebuild_p)
2497         /* We need to restore the order in regno allocno list.  */
2498         {
2499           if (regno_allocnos == NULL)
2500             regno_allocnos
2501               = (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t)
2502                                                 * ira_allocnos_num);
2503           ira_rebuild_regno_allocno_list (regno);
2504         }
2505     }
2506   if (merged_p)
2507     ira_rebuild_start_finish_chains ();
2508   if (regno_allocnos != NULL)
2509     ira_free (regno_allocnos);
2510 }
2511
2512 /* Remove allocnos from all loops but the root.  */
2513 static void
2514 remove_low_level_allocnos (void)
2515 {
2516   int regno;
2517   bool merged_p, propagate_p;
2518   ira_allocno_t a, top_a;
2519   ira_loop_tree_node_t a_node, parent;
2520   ira_allocno_iterator ai;
2521
2522   merged_p = false;
2523   FOR_EACH_ALLOCNO (a, ai)
2524     {
2525       a_node = ALLOCNO_LOOP_TREE_NODE (a);
2526       if (a_node == ira_loop_tree_root || ALLOCNO_CAP_MEMBER (a) != NULL)
2527         continue;
2528       regno = ALLOCNO_REGNO (a);
2529       if ((top_a = ira_loop_tree_root->regno_allocno_map[regno]) == NULL)
2530         {
2531           ALLOCNO_LOOP_TREE_NODE (a) = ira_loop_tree_root;
2532           ira_loop_tree_root->regno_allocno_map[regno] = a;
2533           continue;
2534         }
2535       propagate_p = a_node->parent->regno_allocno_map[regno] == NULL;
2536       /* Remove the allocno and update info of allocno in the upper
2537          region.  */
2538       move_allocno_live_ranges (a, top_a);
2539       merged_p = true;
2540       if (propagate_p)
2541         propagate_some_info_from_allocno (top_a, a);
2542     }
2543   FOR_EACH_ALLOCNO (a, ai)
2544     {
2545       a_node = ALLOCNO_LOOP_TREE_NODE (a);
2546       if (a_node == ira_loop_tree_root)
2547         continue;
2548       parent = a_node->parent;
2549       regno = ALLOCNO_REGNO (a);
2550       if (ALLOCNO_CAP_MEMBER (a) != NULL)
2551         ira_assert (ALLOCNO_CAP (a) != NULL);
2552       else if (ALLOCNO_CAP (a) == NULL)
2553         ira_assert (parent->regno_allocno_map[regno] != NULL);
2554     }
2555   FOR_EACH_ALLOCNO (a, ai)
2556     {
2557       regno = ALLOCNO_REGNO (a);
2558       if (ira_loop_tree_root->regno_allocno_map[regno] == a)
2559         {
2560           ira_object_t obj;
2561           ira_allocno_object_iterator oi;
2562
2563           ira_regno_allocno_map[regno] = a;
2564           ALLOCNO_NEXT_REGNO_ALLOCNO (a) = NULL;
2565           ALLOCNO_CAP_MEMBER (a) = NULL;
2566           FOR_EACH_ALLOCNO_OBJECT (a, obj, oi)
2567             COPY_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (obj),
2568                                OBJECT_TOTAL_CONFLICT_HARD_REGS (obj));
2569 #ifdef STACK_REGS
2570           if (ALLOCNO_TOTAL_NO_STACK_REG_P (a))
2571             ALLOCNO_NO_STACK_REG_P (a) = true;
2572 #endif
2573         }
2574       else
2575         {
2576           ira_remove_allocno_prefs (a);
2577           finish_allocno (a);
2578         }
2579     }
2580   if (merged_p)
2581     ira_rebuild_start_finish_chains ();
2582 }
2583
2584 /* Remove loops from consideration.  We remove all loops except for
2585    root if ALL_P or loops for which a separate allocation will not
2586    improve the result.  We have to do this after allocno creation and
2587    their costs and allocno class evaluation because only after that
2588    the register pressure can be known and is calculated.  */
2589 static void
2590 remove_unnecessary_regions (bool all_p)
2591 {
2592   if (current_loops == NULL)
2593     return;
2594   if (all_p)
2595     mark_all_loops_for_removal ();
2596   else
2597     mark_loops_for_removal ();
2598   children_vec.create (last_basic_block_for_fn (cfun)
2599                        + number_of_loops (cfun));
2600   removed_loop_vec.create (last_basic_block_for_fn (cfun)
2601                            + number_of_loops (cfun));
2602   remove_uneccesary_loop_nodes_from_loop_tree (ira_loop_tree_root);
2603   children_vec.release ();
2604   if (all_p)
2605     remove_low_level_allocnos ();
2606   else
2607     remove_unnecessary_allocnos ();
2608   while (removed_loop_vec.length () > 0)
2609     finish_loop_tree_node (removed_loop_vec.pop ());
2610   removed_loop_vec.release ();
2611 }
2612
2613 \f
2614
2615 /* At this point true value of allocno attribute bad_spill_p means
2616    that there is an insn where allocno occurs and where the allocno
2617    can not be used as memory.  The function updates the attribute, now
2618    it can be true only for allocnos which can not be used as memory in
2619    an insn and in whose live ranges there is other allocno deaths.
2620    Spilling allocnos with true value will not improve the code because
2621    it will not make other allocnos colorable and additional reloads
2622    for the corresponding pseudo will be generated in reload pass for
2623    each insn it occurs.
2624
2625    This is a trick mentioned in one classic article of Chaitin etc
2626    which is frequently omitted in other implementations of RA based on
2627    graph coloring.  */
2628 static void
2629 update_bad_spill_attribute (void)
2630 {
2631   int i;
2632   ira_allocno_t a;
2633   ira_allocno_iterator ai;
2634   ira_allocno_object_iterator aoi;
2635   ira_object_t obj;
2636   live_range_t r;
2637   enum reg_class aclass;
2638   bitmap_head dead_points[N_REG_CLASSES];
2639
2640   for (i = 0; i < ira_allocno_classes_num; i++)
2641     {
2642       aclass = ira_allocno_classes[i];
2643       bitmap_initialize (&dead_points[aclass], &reg_obstack);
2644     }
2645   FOR_EACH_ALLOCNO (a, ai)
2646     {
2647       aclass = ALLOCNO_CLASS (a);
2648       if (aclass == NO_REGS)
2649         continue;
2650       FOR_EACH_ALLOCNO_OBJECT (a, obj, aoi)
2651         for (r = OBJECT_LIVE_RANGES (obj); r != NULL; r = r->next)
2652           bitmap_set_bit (&dead_points[aclass], r->finish);
2653     }
2654   FOR_EACH_ALLOCNO (a, ai)
2655     {
2656       aclass = ALLOCNO_CLASS (a);
2657       if (aclass == NO_REGS)
2658         continue;
2659       if (! ALLOCNO_BAD_SPILL_P (a))
2660         continue;
2661       FOR_EACH_ALLOCNO_OBJECT (a, obj, aoi)
2662         {
2663           for (r = OBJECT_LIVE_RANGES (obj); r != NULL; r = r->next)
2664             {
2665               for (i = r->start + 1; i < r->finish; i++)
2666                 if (bitmap_bit_p (&dead_points[aclass], i))
2667                   break;
2668               if (i < r->finish)
2669                 break;
2670             }
2671           if (r != NULL)
2672             {
2673               ALLOCNO_BAD_SPILL_P (a) = false;
2674               break;
2675             }
2676         }
2677     }
2678   for (i = 0; i < ira_allocno_classes_num; i++)
2679     {
2680       aclass = ira_allocno_classes[i];
2681       bitmap_clear (&dead_points[aclass]);
2682     }
2683 }
2684
2685 \f
2686
2687 /* Set up minimal and maximal live range points for allocnos.  */
2688 static void
2689 setup_min_max_allocno_live_range_point (void)
2690 {
2691   int i;
2692   ira_allocno_t a, parent_a, cap;
2693   ira_allocno_iterator ai;
2694 #ifdef ENABLE_IRA_CHECKING
2695   ira_object_iterator oi;
2696   ira_object_t obj;
2697 #endif
2698   live_range_t r;
2699   ira_loop_tree_node_t parent;
2700
2701   FOR_EACH_ALLOCNO (a, ai)
2702     {
2703       int n = ALLOCNO_NUM_OBJECTS (a);
2704
2705       for (i = 0; i < n; i++)
2706         {
2707           ira_object_t obj = ALLOCNO_OBJECT (a, i);
2708           r = OBJECT_LIVE_RANGES (obj);
2709           if (r == NULL)
2710             continue;
2711           OBJECT_MAX (obj) = r->finish;
2712           for (; r->next != NULL; r = r->next)
2713             ;
2714           OBJECT_MIN (obj) = r->start;
2715         }
2716     }
2717   for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--)
2718     for (a = ira_regno_allocno_map[i];
2719          a != NULL;
2720          a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
2721       {
2722         int j;
2723         int n = ALLOCNO_NUM_OBJECTS (a);
2724
2725         for (j = 0; j < n; j++)
2726           {
2727             ira_object_t obj = ALLOCNO_OBJECT (a, j);
2728             ira_object_t parent_obj;
2729
2730             if (OBJECT_MAX (obj) < 0)
2731               continue;
2732             ira_assert (ALLOCNO_CAP_MEMBER (a) == NULL);
2733             /* Accumulation of range info.  */
2734             if (ALLOCNO_CAP (a) != NULL)
2735               {
2736                 for (cap = ALLOCNO_CAP (a); cap != NULL; cap = ALLOCNO_CAP (cap))
2737                   {
2738                     ira_object_t cap_obj = ALLOCNO_OBJECT (cap, j);
2739                     if (OBJECT_MAX (cap_obj) < OBJECT_MAX (obj))
2740                       OBJECT_MAX (cap_obj) = OBJECT_MAX (obj);
2741                     if (OBJECT_MIN (cap_obj) > OBJECT_MIN (obj))
2742                       OBJECT_MIN (cap_obj) = OBJECT_MIN (obj);
2743                   }
2744                 continue;
2745               }
2746             if ((parent = ALLOCNO_LOOP_TREE_NODE (a)->parent) == NULL)
2747               continue;
2748             parent_a = parent->regno_allocno_map[i];
2749             parent_obj = ALLOCNO_OBJECT (parent_a, j);
2750             if (OBJECT_MAX (parent_obj) < OBJECT_MAX (obj))
2751               OBJECT_MAX (parent_obj) = OBJECT_MAX (obj);
2752             if (OBJECT_MIN (parent_obj) > OBJECT_MIN (obj))
2753               OBJECT_MIN (parent_obj) = OBJECT_MIN (obj);
2754           }
2755       }
2756 #ifdef ENABLE_IRA_CHECKING
2757   FOR_EACH_OBJECT (obj, oi)
2758     {
2759       if ((0 <= OBJECT_MIN (obj) && OBJECT_MIN (obj) <= ira_max_point)
2760           && (0 <= OBJECT_MAX (obj) && OBJECT_MAX (obj) <= ira_max_point))
2761         continue;
2762       gcc_unreachable ();
2763     }
2764 #endif
2765 }
2766
2767 /* Sort allocnos according to their live ranges.  Allocnos with
2768    smaller allocno class are put first unless we use priority
2769    coloring.  Allocnos with the same class are ordered according
2770    their start (min).  Allocnos with the same start are ordered
2771    according their finish (max).  */
2772 static int
2773 object_range_compare_func (const void *v1p, const void *v2p)
2774 {
2775   int diff;
2776   ira_object_t obj1 = *(const ira_object_t *) v1p;
2777   ira_object_t obj2 = *(const ira_object_t *) v2p;
2778   ira_allocno_t a1 = OBJECT_ALLOCNO (obj1);
2779   ira_allocno_t a2 = OBJECT_ALLOCNO (obj2);
2780
2781   if ((diff = OBJECT_MIN (obj1) - OBJECT_MIN (obj2)) != 0)
2782     return diff;
2783   if ((diff = OBJECT_MAX (obj1) - OBJECT_MAX (obj2)) != 0)
2784      return diff;
2785   return ALLOCNO_NUM (a1) - ALLOCNO_NUM (a2);
2786 }
2787
2788 /* Sort ira_object_id_map and set up conflict id of allocnos.  */
2789 static void
2790 sort_conflict_id_map (void)
2791 {
2792   int i, num;
2793   ira_allocno_t a;
2794   ira_allocno_iterator ai;
2795
2796   num = 0;
2797   FOR_EACH_ALLOCNO (a, ai)
2798     {
2799       ira_allocno_object_iterator oi;
2800       ira_object_t obj;
2801
2802       FOR_EACH_ALLOCNO_OBJECT (a, obj, oi)
2803         ira_object_id_map[num++] = obj;
2804     }
2805   if (num > 1)
2806     qsort (ira_object_id_map, num, sizeof (ira_object_t),
2807            object_range_compare_func);
2808   for (i = 0; i < num; i++)
2809     {
2810       ira_object_t obj = ira_object_id_map[i];
2811
2812       gcc_assert (obj != NULL);
2813       OBJECT_CONFLICT_ID (obj) = i;
2814     }
2815   for (i = num; i < ira_objects_num; i++)
2816     ira_object_id_map[i] = NULL;
2817 }
2818
2819 /* Set up minimal and maximal conflict ids of allocnos with which
2820    given allocno can conflict.  */
2821 static void
2822 setup_min_max_conflict_allocno_ids (void)
2823 {
2824   int aclass;
2825   int i, j, min, max, start, finish, first_not_finished, filled_area_start;
2826   int *live_range_min, *last_lived;
2827   int word0_min, word0_max;
2828   ira_allocno_t a;
2829   ira_allocno_iterator ai;
2830
2831   live_range_min = (int *) ira_allocate (sizeof (int) * ira_objects_num);
2832   aclass = -1;
2833   first_not_finished = -1;
2834   for (i = 0; i < ira_objects_num; i++)
2835     {
2836       ira_object_t obj = ira_object_id_map[i];
2837
2838       if (obj == NULL)
2839         continue;
2840
2841       a = OBJECT_ALLOCNO (obj);
2842
2843       if (aclass < 0)
2844         {
2845           aclass = ALLOCNO_CLASS (a);
2846           min = i;
2847           first_not_finished = i;
2848         }
2849       else
2850         {
2851           start = OBJECT_MIN (obj);
2852           /* If we skip an allocno, the allocno with smaller ids will
2853              be also skipped because of the secondary sorting the
2854              range finishes (see function
2855              object_range_compare_func).  */
2856           while (first_not_finished < i
2857                  && start > OBJECT_MAX (ira_object_id_map
2858                                         [first_not_finished]))
2859             first_not_finished++;
2860           min = first_not_finished;
2861         }
2862       if (min == i)
2863         /* We could increase min further in this case but it is good
2864            enough.  */
2865         min++;
2866       live_range_min[i] = OBJECT_MIN (obj);
2867       OBJECT_MIN (obj) = min;
2868     }
2869   last_lived = (int *) ira_allocate (sizeof (int) * ira_max_point);
2870   aclass = -1;
2871   filled_area_start = -1;
2872   for (i = ira_objects_num - 1; i >= 0; i--)
2873     {
2874       ira_object_t obj = ira_object_id_map[i];
2875
2876       if (obj == NULL)
2877         continue;
2878
2879       a = OBJECT_ALLOCNO (obj);
2880       if (aclass < 0)
2881         {
2882           aclass = ALLOCNO_CLASS (a);
2883           for (j = 0; j < ira_max_point; j++)
2884             last_lived[j] = -1;
2885           filled_area_start = ira_max_point;
2886         }
2887       min = live_range_min[i];
2888       finish = OBJECT_MAX (obj);
2889       max = last_lived[finish];
2890       if (max < 0)
2891         /* We could decrease max further in this case but it is good
2892            enough.  */
2893         max = OBJECT_CONFLICT_ID (obj) - 1;
2894       OBJECT_MAX (obj) = max;
2895       /* In filling, we can go further A range finish to recognize
2896          intersection quickly because if the finish of subsequently
2897          processed allocno (it has smaller conflict id) range is
2898          further A range finish than they are definitely intersected
2899          (the reason for this is the allocnos with bigger conflict id
2900          have their range starts not smaller than allocnos with
2901          smaller ids.  */
2902       for (j = min; j < filled_area_start; j++)
2903         last_lived[j] = i;
2904       filled_area_start = min;
2905     }
2906   ira_free (last_lived);
2907   ira_free (live_range_min);
2908
2909   /* For allocnos with more than one object, we may later record extra conflicts in
2910      subobject 0 that we cannot really know about here.
2911      For now, simply widen the min/max range of these subobjects.  */
2912
2913   word0_min = INT_MAX;
2914   word0_max = INT_MIN;
2915
2916   FOR_EACH_ALLOCNO (a, ai)
2917     {
2918       int n = ALLOCNO_NUM_OBJECTS (a);
2919       ira_object_t obj0;
2920
2921       if (n < 2)
2922         continue;
2923       obj0 = ALLOCNO_OBJECT (a, 0);
2924       if (OBJECT_CONFLICT_ID (obj0) < word0_min)
2925         word0_min = OBJECT_CONFLICT_ID (obj0);
2926       if (OBJECT_CONFLICT_ID (obj0) > word0_max)
2927         word0_max = OBJECT_CONFLICT_ID (obj0);
2928     }
2929   FOR_EACH_ALLOCNO (a, ai)
2930     {
2931       int n = ALLOCNO_NUM_OBJECTS (a);
2932       ira_object_t obj0;
2933
2934       if (n < 2)
2935         continue;
2936       obj0 = ALLOCNO_OBJECT (a, 0);
2937       if (OBJECT_MIN (obj0) > word0_min)
2938         OBJECT_MIN (obj0) = word0_min;
2939       if (OBJECT_MAX (obj0) < word0_max)
2940         OBJECT_MAX (obj0) = word0_max;
2941     }
2942 }
2943
2944 \f
2945
2946 static void
2947 create_caps (void)
2948 {
2949   ira_allocno_t a;
2950   ira_allocno_iterator ai;
2951   ira_loop_tree_node_t loop_tree_node;
2952
2953   FOR_EACH_ALLOCNO (a, ai)
2954     {
2955       if (ALLOCNO_LOOP_TREE_NODE (a) == ira_loop_tree_root)
2956         continue;
2957       if (ALLOCNO_CAP_MEMBER (a) != NULL)
2958         create_cap_allocno (a);
2959       else if (ALLOCNO_CAP (a) == NULL)
2960         {
2961           loop_tree_node = ALLOCNO_LOOP_TREE_NODE (a);
2962           if (!bitmap_bit_p (loop_tree_node->border_allocnos, ALLOCNO_NUM (a)))
2963             create_cap_allocno (a);
2964         }
2965     }
2966 }
2967
2968 \f
2969
2970 /* The page contains code transforming more one region internal
2971    representation (IR) to one region IR which is necessary for reload.
2972    This transformation is called IR flattening.  We might just rebuild
2973    the IR for one region but we don't do it because it takes a lot of
2974    time.  */
2975
2976 /* Map: regno -> allocnos which will finally represent the regno for
2977    IR with one region.  */
2978 static ira_allocno_t *regno_top_level_allocno_map;
2979
2980 /* Find the allocno that corresponds to A at a level one higher up in the
2981    loop tree.  Returns NULL if A is a cap, or if it has no parent.  */
2982 ira_allocno_t
2983 ira_parent_allocno (ira_allocno_t a)
2984 {
2985   ira_loop_tree_node_t parent;
2986
2987   if (ALLOCNO_CAP (a) != NULL)
2988     return NULL;
2989
2990   parent = ALLOCNO_LOOP_TREE_NODE (a)->parent;
2991   if (parent == NULL)
2992     return NULL;
2993
2994   return parent->regno_allocno_map[ALLOCNO_REGNO (a)];
2995 }
2996
2997 /* Find the allocno that corresponds to A at a level one higher up in the
2998    loop tree.  If ALLOCNO_CAP is set for A, return that.  */
2999 ira_allocno_t
3000 ira_parent_or_cap_allocno (ira_allocno_t a)
3001 {
3002   if (ALLOCNO_CAP (a) != NULL)
3003     return ALLOCNO_CAP (a);
3004
3005   return ira_parent_allocno (a);
3006 }
3007
3008 /* Process all allocnos originated from pseudo REGNO and copy live
3009    ranges, hard reg conflicts, and allocno stack reg attributes from
3010    low level allocnos to final allocnos which are destinations of
3011    removed stores at a loop exit.  Return true if we copied live
3012    ranges.  */
3013 static bool
3014 copy_info_to_removed_store_destinations (int regno)
3015 {
3016   ira_allocno_t a;
3017   ira_allocno_t parent_a = NULL;
3018   ira_loop_tree_node_t parent;
3019   bool merged_p;
3020
3021   merged_p = false;
3022   for (a = ira_regno_allocno_map[regno];
3023        a != NULL;
3024        a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
3025     {
3026       if (a != regno_top_level_allocno_map[REGNO (allocno_emit_reg (a))])
3027         /* This allocno will be removed.  */
3028         continue;
3029
3030       /* Caps will be removed.  */
3031       ira_assert (ALLOCNO_CAP_MEMBER (a) == NULL);
3032       for (parent = ALLOCNO_LOOP_TREE_NODE (a)->parent;
3033            parent != NULL;
3034            parent = parent->parent)
3035         if ((parent_a = parent->regno_allocno_map[regno]) == NULL
3036             || (parent_a
3037                 == regno_top_level_allocno_map[REGNO
3038                                                (allocno_emit_reg (parent_a))]
3039                 && ALLOCNO_EMIT_DATA (parent_a)->mem_optimized_dest_p))
3040           break;
3041       if (parent == NULL || parent_a == NULL)
3042         continue;
3043
3044       copy_allocno_live_ranges (a, parent_a);
3045       merge_hard_reg_conflicts (a, parent_a, true);
3046
3047       ALLOCNO_CALL_FREQ (parent_a) += ALLOCNO_CALL_FREQ (a);
3048       ALLOCNO_CALLS_CROSSED_NUM (parent_a)
3049         += ALLOCNO_CALLS_CROSSED_NUM (a);
3050       ALLOCNO_CHEAP_CALLS_CROSSED_NUM (parent_a)
3051         += ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a);
3052       IOR_HARD_REG_SET (ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS (parent_a),
3053                         ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS (a));
3054       ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (parent_a)
3055         += ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a);
3056       merged_p = true;
3057     }
3058   return merged_p;
3059 }
3060
3061 /* Flatten the IR.  In other words, this function transforms IR as if
3062    it were built with one region (without loops).  We could make it
3063    much simpler by rebuilding IR with one region, but unfortunately it
3064    takes a lot of time.  MAX_REGNO_BEFORE_EMIT and
3065    IRA_MAX_POINT_BEFORE_EMIT are correspondingly MAX_REG_NUM () and
3066    IRA_MAX_POINT before emitting insns on the loop borders.  */
3067 void
3068 ira_flattening (int max_regno_before_emit, int ira_max_point_before_emit)
3069 {
3070   int i, j;
3071   bool keep_p;
3072   int hard_regs_num;
3073   bool new_pseudos_p, merged_p, mem_dest_p;
3074   unsigned int n;
3075   enum reg_class aclass;
3076   ira_allocno_t a, parent_a, first, second, node_first, node_second;
3077   ira_copy_t cp;
3078   ira_loop_tree_node_t node;
3079   live_range_t r;
3080   ira_allocno_iterator ai;
3081   ira_copy_iterator ci;
3082
3083   regno_top_level_allocno_map
3084     = (ira_allocno_t *) ira_allocate (max_reg_num ()
3085                                       * sizeof (ira_allocno_t));
3086   memset (regno_top_level_allocno_map, 0,
3087           max_reg_num () * sizeof (ira_allocno_t));
3088   new_pseudos_p = merged_p = false;
3089   FOR_EACH_ALLOCNO (a, ai)
3090     {
3091       ira_allocno_object_iterator oi;
3092       ira_object_t obj;
3093
3094       if (ALLOCNO_CAP_MEMBER (a) != NULL)
3095         /* Caps are not in the regno allocno maps and they are never
3096            will be transformed into allocnos existing after IR
3097            flattening.  */
3098         continue;
3099       FOR_EACH_ALLOCNO_OBJECT (a, obj, oi)
3100         COPY_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj),
3101                            OBJECT_CONFLICT_HARD_REGS (obj));
3102 #ifdef STACK_REGS
3103       ALLOCNO_TOTAL_NO_STACK_REG_P (a) = ALLOCNO_NO_STACK_REG_P (a);
3104 #endif
3105     }
3106   /* Fix final allocno attributes.  */
3107   for (i = max_regno_before_emit - 1; i >= FIRST_PSEUDO_REGISTER; i--)
3108     {
3109       mem_dest_p = false;
3110       for (a = ira_regno_allocno_map[i];
3111            a != NULL;
3112            a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
3113         {
3114           ira_emit_data_t parent_data, data = ALLOCNO_EMIT_DATA (a);
3115
3116           ira_assert (ALLOCNO_CAP_MEMBER (a) == NULL);
3117           if (data->somewhere_renamed_p)
3118             new_pseudos_p = true;
3119           parent_a = ira_parent_allocno (a);
3120           if (parent_a == NULL)
3121             {
3122               ALLOCNO_COPIES (a) = NULL;
3123               regno_top_level_allocno_map[REGNO (data->reg)] = a;
3124               continue;
3125             }
3126           ira_assert (ALLOCNO_CAP_MEMBER (parent_a) == NULL);
3127
3128           if (data->mem_optimized_dest != NULL)
3129             mem_dest_p = true;
3130           parent_data = ALLOCNO_EMIT_DATA (parent_a);
3131           if (REGNO (data->reg) == REGNO (parent_data->reg))
3132             {
3133               merge_hard_reg_conflicts (a, parent_a, true);
3134               move_allocno_live_ranges (a, parent_a);
3135               merged_p = true;
3136               parent_data->mem_optimized_dest_p
3137                 = (parent_data->mem_optimized_dest_p
3138                    || data->mem_optimized_dest_p);
3139               continue;
3140             }
3141           new_pseudos_p = true;
3142           for (;;)
3143             {
3144               ALLOCNO_NREFS (parent_a) -= ALLOCNO_NREFS (a);
3145               ALLOCNO_FREQ (parent_a) -= ALLOCNO_FREQ (a);
3146               ALLOCNO_CALL_FREQ (parent_a) -= ALLOCNO_CALL_FREQ (a);
3147               ALLOCNO_CALLS_CROSSED_NUM (parent_a)
3148                 -= ALLOCNO_CALLS_CROSSED_NUM (a);
3149               ALLOCNO_CHEAP_CALLS_CROSSED_NUM (parent_a)
3150                 -= ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a);
3151               ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (parent_a)
3152                 -= ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a);
3153               ira_assert (ALLOCNO_CALLS_CROSSED_NUM (parent_a) >= 0
3154                           && ALLOCNO_NREFS (parent_a) >= 0
3155                           && ALLOCNO_FREQ (parent_a) >= 0);
3156               aclass = ALLOCNO_CLASS (parent_a);
3157               hard_regs_num = ira_class_hard_regs_num[aclass];
3158               if (ALLOCNO_HARD_REG_COSTS (a) != NULL
3159                   && ALLOCNO_HARD_REG_COSTS (parent_a) != NULL)
3160                 for (j = 0; j < hard_regs_num; j++)
3161                   ALLOCNO_HARD_REG_COSTS (parent_a)[j]
3162                     -= ALLOCNO_HARD_REG_COSTS (a)[j];
3163               if (ALLOCNO_CONFLICT_HARD_REG_COSTS (a) != NULL
3164                   && ALLOCNO_CONFLICT_HARD_REG_COSTS (parent_a) != NULL)
3165                 for (j = 0; j < hard_regs_num; j++)
3166                   ALLOCNO_CONFLICT_HARD_REG_COSTS (parent_a)[j]
3167                     -= ALLOCNO_CONFLICT_HARD_REG_COSTS (a)[j];
3168               ALLOCNO_CLASS_COST (parent_a)
3169                 -= ALLOCNO_CLASS_COST (a);
3170               ALLOCNO_MEMORY_COST (parent_a) -= ALLOCNO_MEMORY_COST (a);
3171               parent_a = ira_parent_allocno (parent_a);
3172               if (parent_a == NULL)
3173                 break;
3174             }
3175           ALLOCNO_COPIES (a) = NULL;
3176           regno_top_level_allocno_map[REGNO (data->reg)] = a;
3177         }
3178       if (mem_dest_p && copy_info_to_removed_store_destinations (i))
3179         merged_p = true;
3180     }
3181   ira_assert (new_pseudos_p || ira_max_point_before_emit == ira_max_point);
3182   if (merged_p || ira_max_point_before_emit != ira_max_point)
3183     ira_rebuild_start_finish_chains ();
3184   if (new_pseudos_p)
3185     {
3186       sparseset objects_live;
3187
3188       /* Rebuild conflicts.  */
3189       FOR_EACH_ALLOCNO (a, ai)
3190         {
3191           ira_allocno_object_iterator oi;
3192           ira_object_t obj;
3193
3194           if (a != regno_top_level_allocno_map[REGNO (allocno_emit_reg (a))]
3195               || ALLOCNO_CAP_MEMBER (a) != NULL)
3196             continue;
3197           FOR_EACH_ALLOCNO_OBJECT (a, obj, oi)
3198             {
3199               for (r = OBJECT_LIVE_RANGES (obj); r != NULL; r = r->next)
3200                 ira_assert (r->object == obj);
3201               clear_conflicts (obj);
3202             }
3203         }
3204       objects_live = sparseset_alloc (ira_objects_num);
3205       for (i = 0; i < ira_max_point; i++)
3206         {
3207           for (r = ira_start_point_ranges[i]; r != NULL; r = r->start_next)
3208             {
3209               ira_object_t obj = r->object;
3210
3211               a = OBJECT_ALLOCNO (obj);
3212               if (a != regno_top_level_allocno_map[REGNO (allocno_emit_reg (a))]
3213                   || ALLOCNO_CAP_MEMBER (a) != NULL)
3214                 continue;
3215
3216               aclass = ALLOCNO_CLASS (a);
3217               EXECUTE_IF_SET_IN_SPARSESET (objects_live, n)
3218                 {
3219                   ira_object_t live_obj = ira_object_id_map[n];
3220                   ira_allocno_t live_a = OBJECT_ALLOCNO (live_obj);
3221                   enum reg_class live_aclass = ALLOCNO_CLASS (live_a);
3222
3223                   if (ira_reg_classes_intersect_p[aclass][live_aclass]
3224                       /* Don't set up conflict for the allocno with itself.  */
3225                       && live_a != a)
3226                     ira_add_conflict (obj, live_obj);
3227                 }
3228               sparseset_set_bit (objects_live, OBJECT_CONFLICT_ID (obj));
3229             }
3230
3231           for (r = ira_finish_point_ranges[i]; r != NULL; r = r->finish_next)
3232             sparseset_clear_bit (objects_live, OBJECT_CONFLICT_ID (r->object));
3233         }
3234       sparseset_free (objects_live);
3235       compress_conflict_vecs ();
3236     }
3237   /* Mark some copies for removing and change allocnos in the rest
3238      copies.  */
3239   FOR_EACH_COPY (cp, ci)
3240     {
3241       if (ALLOCNO_CAP_MEMBER (cp->first) != NULL
3242           || ALLOCNO_CAP_MEMBER (cp->second) != NULL)
3243         {
3244           if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL)
3245             fprintf
3246               (ira_dump_file, "      Remove cp%d:%c%dr%d-%c%dr%d\n",
3247                cp->num, ALLOCNO_CAP_MEMBER (cp->first) != NULL ? 'c' : 'a',
3248                ALLOCNO_NUM (cp->first),
3249                REGNO (allocno_emit_reg (cp->first)),
3250                ALLOCNO_CAP_MEMBER (cp->second) != NULL ? 'c' : 'a',
3251                ALLOCNO_NUM (cp->second),
3252                REGNO (allocno_emit_reg (cp->second)));
3253           cp->loop_tree_node = NULL;
3254           continue;
3255         }
3256       first
3257         = regno_top_level_allocno_map[REGNO (allocno_emit_reg (cp->first))];
3258       second
3259         = regno_top_level_allocno_map[REGNO (allocno_emit_reg (cp->second))];
3260       node = cp->loop_tree_node;
3261       if (node == NULL)
3262         keep_p = true; /* It copy generated in ira-emit.c.  */
3263       else
3264         {
3265           /* Check that the copy was not propagated from level on
3266              which we will have different pseudos.  */
3267           node_first = node->regno_allocno_map[ALLOCNO_REGNO (cp->first)];
3268           node_second = node->regno_allocno_map[ALLOCNO_REGNO (cp->second)];
3269           keep_p = ((REGNO (allocno_emit_reg (first))
3270                      == REGNO (allocno_emit_reg (node_first)))
3271                      && (REGNO (allocno_emit_reg (second))
3272                          == REGNO (allocno_emit_reg (node_second))));
3273         }
3274       if (keep_p)
3275         {
3276           cp->loop_tree_node = ira_loop_tree_root;
3277           cp->first = first;
3278           cp->second = second;
3279         }
3280       else
3281         {
3282           cp->loop_tree_node = NULL;
3283           if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL)
3284             fprintf (ira_dump_file, "      Remove cp%d:a%dr%d-a%dr%d\n",
3285                      cp->num, ALLOCNO_NUM (cp->first),
3286                      REGNO (allocno_emit_reg (cp->first)),
3287                      ALLOCNO_NUM (cp->second),
3288                      REGNO (allocno_emit_reg (cp->second)));
3289         }
3290     }
3291   /* Remove unnecessary allocnos on lower levels of the loop tree.  */
3292   FOR_EACH_ALLOCNO (a, ai)
3293     {
3294       if (a != regno_top_level_allocno_map[REGNO (allocno_emit_reg (a))]
3295           || ALLOCNO_CAP_MEMBER (a) != NULL)
3296         {
3297           if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL)
3298             fprintf (ira_dump_file, "      Remove a%dr%d\n",
3299                      ALLOCNO_NUM (a), REGNO (allocno_emit_reg (a)));
3300           ira_remove_allocno_prefs (a);
3301           finish_allocno (a);
3302           continue;
3303         }
3304       ALLOCNO_LOOP_TREE_NODE (a) = ira_loop_tree_root;
3305       ALLOCNO_REGNO (a) = REGNO (allocno_emit_reg (a));
3306       ALLOCNO_CAP (a) = NULL;
3307       /* Restore updated costs for assignments from reload.  */
3308       ALLOCNO_UPDATED_MEMORY_COST (a) = ALLOCNO_MEMORY_COST (a);
3309       ALLOCNO_UPDATED_CLASS_COST (a) = ALLOCNO_CLASS_COST (a);
3310       if (! ALLOCNO_ASSIGNED_P (a))
3311         ira_free_allocno_updated_costs (a);
3312       ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL);
3313       ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) == NULL);
3314     }
3315   /* Remove unnecessary copies.  */
3316   FOR_EACH_COPY (cp, ci)
3317     {
3318       if (cp->loop_tree_node == NULL)
3319         {
3320           ira_copies[cp->num] = NULL;
3321           finish_copy (cp);
3322           continue;
3323         }
3324       ira_assert
3325         (ALLOCNO_LOOP_TREE_NODE (cp->first) == ira_loop_tree_root
3326          && ALLOCNO_LOOP_TREE_NODE (cp->second) == ira_loop_tree_root);
3327       add_allocno_copy_to_list (cp);
3328       swap_allocno_copy_ends_if_necessary (cp);
3329     }
3330   rebuild_regno_allocno_maps ();
3331   if (ira_max_point != ira_max_point_before_emit)
3332     ira_compress_allocno_live_ranges ();
3333   ira_free (regno_top_level_allocno_map);
3334 }
3335
3336 \f
3337
3338 #ifdef ENABLE_IRA_CHECKING
3339 /* Check creation of all allocnos.  Allocnos on lower levels should
3340    have allocnos or caps on all upper levels.  */
3341 static void
3342 check_allocno_creation (void)
3343 {
3344   ira_allocno_t a;
3345   ira_allocno_iterator ai;
3346   ira_loop_tree_node_t loop_tree_node;
3347
3348   FOR_EACH_ALLOCNO (a, ai)
3349     {
3350       loop_tree_node = ALLOCNO_LOOP_TREE_NODE (a);
3351       ira_assert (bitmap_bit_p (loop_tree_node->all_allocnos,
3352                                 ALLOCNO_NUM (a)));
3353       if (loop_tree_node == ira_loop_tree_root)
3354         continue;
3355       if (ALLOCNO_CAP_MEMBER (a) != NULL)
3356         ira_assert (ALLOCNO_CAP (a) != NULL);
3357       else if (ALLOCNO_CAP (a) == NULL)
3358         ira_assert (loop_tree_node->parent
3359                     ->regno_allocno_map[ALLOCNO_REGNO (a)] != NULL
3360                     && bitmap_bit_p (loop_tree_node->border_allocnos,
3361                                      ALLOCNO_NUM (a)));
3362     }
3363 }
3364 #endif
3365
3366 /* Identify allocnos which prefer a register class with a single hard register.
3367    Adjust ALLOCNO_CONFLICT_HARD_REG_COSTS so that conflicting allocnos are
3368    less likely to use the preferred singleton register.  */
3369 static void
3370 update_conflict_hard_reg_costs (void)
3371 {
3372   ira_allocno_t a;
3373   ira_allocno_iterator ai;
3374   int i, index, min;
3375
3376   FOR_EACH_ALLOCNO (a, ai)
3377     {
3378       reg_class_t aclass = ALLOCNO_CLASS (a);
3379       reg_class_t pref = reg_preferred_class (ALLOCNO_REGNO (a));
3380       int singleton = ira_class_singleton[pref][ALLOCNO_MODE (a)];
3381       if (singleton < 0)
3382         continue;
3383       index = ira_class_hard_reg_index[(int) aclass][singleton];
3384       if (index < 0)
3385         continue;
3386       if (ALLOCNO_CONFLICT_HARD_REG_COSTS (a) == NULL
3387           || ALLOCNO_HARD_REG_COSTS (a) == NULL)
3388         continue;
3389       min = INT_MAX;
3390       for (i = ira_class_hard_regs_num[(int) aclass] - 1; i >= 0; i--)
3391         if (ALLOCNO_HARD_REG_COSTS (a)[i] > ALLOCNO_CLASS_COST (a)
3392             && min > ALLOCNO_HARD_REG_COSTS (a)[i])
3393           min = ALLOCNO_HARD_REG_COSTS (a)[i];
3394       if (min == INT_MAX)
3395         continue;
3396       ira_allocate_and_set_costs (&ALLOCNO_CONFLICT_HARD_REG_COSTS (a),
3397                                   aclass, 0);
3398       ALLOCNO_CONFLICT_HARD_REG_COSTS (a)[index]
3399         -= min - ALLOCNO_CLASS_COST (a);
3400     }
3401 }
3402
3403 /* Create a internal representation (IR) for IRA (allocnos, copies,
3404    loop tree nodes).  The function returns TRUE if we generate loop
3405    structure (besides nodes representing all function and the basic
3406    blocks) for regional allocation.  A true return means that we
3407    really need to flatten IR before the reload.  */
3408 bool
3409 ira_build (void)
3410 {
3411   bool loops_p;
3412
3413   df_analyze ();
3414   initiate_cost_vectors ();
3415   initiate_allocnos ();
3416   initiate_prefs ();
3417   initiate_copies ();
3418   create_loop_tree_nodes ();
3419   form_loop_tree ();
3420   create_allocnos ();
3421   ira_costs ();
3422   create_allocno_objects ();
3423   ira_create_allocno_live_ranges ();
3424   remove_unnecessary_regions (false);
3425   ira_compress_allocno_live_ranges ();
3426   update_bad_spill_attribute ();
3427   loops_p = more_one_region_p ();
3428   if (loops_p)
3429     {
3430       propagate_allocno_info ();
3431       create_caps ();
3432     }
3433   ira_tune_allocno_costs ();
3434 #ifdef ENABLE_IRA_CHECKING
3435   check_allocno_creation ();
3436 #endif
3437   setup_min_max_allocno_live_range_point ();
3438   sort_conflict_id_map ();
3439   setup_min_max_conflict_allocno_ids ();
3440   ira_build_conflicts ();
3441   update_conflict_hard_reg_costs ();
3442   if (! ira_conflicts_p)
3443     {
3444       ira_allocno_t a;
3445       ira_allocno_iterator ai;
3446
3447       /* Remove all regions but root one.  */
3448       if (loops_p)
3449         {
3450           remove_unnecessary_regions (true);
3451           loops_p = false;
3452         }
3453       /* We don't save hard registers around calls for fast allocation
3454          -- add caller clobbered registers as conflicting ones to
3455          allocno crossing calls.  */
3456       FOR_EACH_ALLOCNO (a, ai)
3457         if (ALLOCNO_CALLS_CROSSED_NUM (a) != 0)
3458           ior_hard_reg_conflicts (a, &call_used_reg_set);
3459     }
3460   if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
3461     print_copies (ira_dump_file);
3462   if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
3463     print_prefs (ira_dump_file);
3464   if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
3465     {
3466       int n, nr, nr_big;
3467       ira_allocno_t a;
3468       live_range_t r;
3469       ira_allocno_iterator ai;
3470
3471       n = 0;
3472       nr = 0;
3473       nr_big = 0;
3474       FOR_EACH_ALLOCNO (a, ai)
3475         {
3476           int j, nobj = ALLOCNO_NUM_OBJECTS (a);
3477
3478           if (nobj > 1)
3479             nr_big++;
3480           for (j = 0; j < nobj; j++)
3481             {
3482               ira_object_t obj = ALLOCNO_OBJECT (a, j);
3483               n += OBJECT_NUM_CONFLICTS (obj);
3484               for (r = OBJECT_LIVE_RANGES (obj); r != NULL; r = r->next)
3485                 nr++;
3486             }
3487         }
3488       fprintf (ira_dump_file, "  regions=%d, blocks=%d, points=%d\n",
3489                current_loops == NULL ? 1 : number_of_loops (cfun),
3490                n_basic_blocks_for_fn (cfun), ira_max_point);
3491       fprintf (ira_dump_file,
3492                "    allocnos=%d (big %d), copies=%d, conflicts=%d, ranges=%d\n",
3493                ira_allocnos_num, nr_big, ira_copies_num, n, nr);
3494     }
3495   return loops_p;
3496 }
3497
3498 /* Release the data created by function ira_build.  */
3499 void
3500 ira_destroy (void)
3501 {
3502   finish_loop_tree_nodes ();
3503   finish_prefs ();
3504   finish_copies ();
3505   finish_allocnos ();
3506   finish_cost_vectors ();
3507   ira_finish_allocno_live_ranges ();
3508 }