gcc/ira-build.c

   1 /* Building internal representation for IRA.
   2    Copyright (C) 2006-2021 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 "sparseset.h"
  35 #include "cfgloop.h"
  36
  37 static ira_copy_t find_allocno_copy (ira_allocno_t, ira_allocno_t, rtx_insn *,
  38                                      ira_loop_tree_node_t);
  39
  40 /* The root of the loop tree corresponding to the all function.  */
  41 ira_loop_tree_node_t ira_loop_tree_root;
  42
  43 /* Height of the loop tree.  */
  44 int ira_loop_tree_height;
  45
  46 /* All nodes representing basic blocks are referred through the
  47    following array.  We cannot use basic block member `aux' for this
  48    because it is used for insertion of insns on edges.  */
  49 ira_loop_tree_node_t ira_bb_nodes;
  50
  51 /* All nodes representing loops are referred through the following
  52    array.  */
  53 ira_loop_tree_node_t ira_loop_nodes;
  54
  55 /* And size of the ira_loop_nodes array.  */
  56 unsigned int ira_loop_nodes_count;
  57
  58 /* Map regno -> allocnos with given regno (see comments for
  59    allocno member `next_regno_allocno').  */
  60 ira_allocno_t *ira_regno_allocno_map;
  61
  62 /* Array of references to all allocnos.  The order number of the
  63    allocno corresponds to the index in the array.  Removed allocnos
  64    have NULL element value.  */
  65 ira_allocno_t *ira_allocnos;
  66
  67 /* Sizes of the previous array.  */
  68 int ira_allocnos_num;
  69
  70 /* Count of conflict record structures we've created, used when creating
  71    a new conflict id.  */
  72 int ira_objects_num;
  73
  74 /* Map a conflict id to its conflict record.  */
  75 ira_object_t *ira_object_id_map;
  76
  77 /* Array of references to all allocno preferences.  The order number
  78    of the preference corresponds to the index in the array.  */
  79 ira_pref_t *ira_prefs;
  80
  81 /* Size of the previous array.  */
  82 int ira_prefs_num;
  83
  84 /* Array of references to all copies.  The order number of the copy
  85    corresponds to the index in the array.  Removed copies have NULL
  86    element value.  */
  87 ira_copy_t *ira_copies;
  88
  89 /* Size of the previous array.  */
  90 int ira_copies_num;
  91
  92 \f
  93
  94 /* LAST_BASIC_BLOCK before generating additional insns because of live
  95    range splitting.  Emitting insns on a critical edge creates a new
  96    basic block.  */
  97 static int last_basic_block_before_change;
  98
  99 /* Initialize some members in loop tree node NODE.  Use LOOP_NUM for
 100    the member loop_num.  */
 101 static void
 102 init_loop_tree_node (struct ira_loop_tree_node *node, int loop_num)
 103 {
 104   int max_regno = max_reg_num ();
 105
 106   node->regno_allocno_map
 107     = (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t) * max_regno);
 108   memset (node->regno_allocno_map, 0, sizeof (ira_allocno_t) * max_regno);
 109   memset (node->reg_pressure, 0, sizeof (node->reg_pressure));
 110   node->all_allocnos = ira_allocate_bitmap ();
 111   node->modified_regnos = ira_allocate_bitmap ();
 112   node->border_allocnos = ira_allocate_bitmap ();
 113   node->local_copies = ira_allocate_bitmap ();
 114   node->loop_num = loop_num;
 115   node->children = NULL;
 116   node->subloops = NULL;
 117 }
 118
 119
 120 /* The following function allocates the loop tree nodes.  If
 121    CURRENT_LOOPS is NULL, the nodes corresponding to the loops (except
 122    the root which corresponds the all function) will be not allocated
 123    but nodes will still be allocated for basic blocks.  */
 124 static void
 125 create_loop_tree_nodes (void)
 126 {
 127   unsigned int i, j;
 128   bool skip_p;
 129   edge_iterator ei;
 130   edge e;
 131   loop_p loop;
 132
 133   ira_bb_nodes
 134     = ((struct ira_loop_tree_node *)
 135        ira_allocate (sizeof (struct ira_loop_tree_node)
 136                      * last_basic_block_for_fn (cfun)));
 137   last_basic_block_before_change = last_basic_block_for_fn (cfun);
 138   for (i = 0; i < (unsigned int) last_basic_block_for_fn (cfun); i++)
 139     {
 140       ira_bb_nodes[i].regno_allocno_map = NULL;
 141       memset (ira_bb_nodes[i].reg_pressure, 0,
 142               sizeof (ira_bb_nodes[i].reg_pressure));
 143       ira_bb_nodes[i].all_allocnos = NULL;
 144       ira_bb_nodes[i].modified_regnos = NULL;
 145       ira_bb_nodes[i].border_allocnos = NULL;
 146       ira_bb_nodes[i].local_copies = NULL;
 147     }
 148   if (current_loops == NULL)
 149     {
 150       ira_loop_nodes_count = 1;
 151       ira_loop_nodes = ((struct ira_loop_tree_node *)
 152                         ira_allocate (sizeof (struct ira_loop_tree_node)));
 153       init_loop_tree_node (ira_loop_nodes, 0);
 154       return;
 155     }
 156   ira_loop_nodes_count = number_of_loops (cfun);
 157   ira_loop_nodes = ((struct ira_loop_tree_node *)
 158                     ira_allocate (sizeof (struct ira_loop_tree_node)
 159                                   * ira_loop_nodes_count));
 160   FOR_EACH_VEC_SAFE_ELT (get_loops (cfun), i, loop)
 161     {
 162       if (loop_outer (loop) != NULL)
 163         {
 164           ira_loop_nodes[i].regno_allocno_map = NULL;
 165           skip_p = false;
 166           FOR_EACH_EDGE (e, ei, loop->header->preds)
 167             if (e->src != loop->latch
 168                 && (e->flags & EDGE_ABNORMAL) && EDGE_CRITICAL_P (e))
 169               {
 170                 skip_p = true;
 171                 break;
 172               }
 173           if (skip_p)
 174             continue;
 175           auto_vec<edge> edges = get_loop_exit_edges (loop);
 176           FOR_EACH_VEC_ELT (edges, j, e)
 177             if ((e->flags & EDGE_ABNORMAL) && EDGE_CRITICAL_P (e))
 178               {
 179                 skip_p = true;
 180                 break;
 181               }
 182           if (skip_p)
 183             continue;
 184         }
 185       init_loop_tree_node (&ira_loop_nodes[i], loop->num);
 186     }
 187 }
 188
 189 /* The function returns TRUE if there are more one allocation
 190    region.  */
 191 static bool
 192 more_one_region_p (void)
 193 {
 194   unsigned int i;
 195   loop_p loop;
 196
 197   if (current_loops != NULL)
 198     FOR_EACH_VEC_SAFE_ELT (get_loops (cfun), i, loop)
 199       if (ira_loop_nodes[i].regno_allocno_map != NULL
 200           && ira_loop_tree_root != &ira_loop_nodes[i])
 201         return true;
 202   return false;
 203 }
 204
 205 /* Free the loop tree node of a loop.  */
 206 static void
 207 finish_loop_tree_node (ira_loop_tree_node_t loop)
 208 {
 209   if (loop->regno_allocno_map != NULL)
 210     {
 211       ira_assert (loop->bb == NULL);
 212       ira_free_bitmap (loop->local_copies);
 213       ira_free_bitmap (loop->border_allocnos);
 214       ira_free_bitmap (loop->modified_regnos);
 215       ira_free_bitmap (loop->all_allocnos);
 216       ira_free (loop->regno_allocno_map);
 217       loop->regno_allocno_map = NULL;
 218     }
 219 }
 220
 221 /* Free the loop tree nodes.  */
 222 static void
 223 finish_loop_tree_nodes (void)
 224 {
 225   unsigned int i;
 226
 227   for (i = 0; i < ira_loop_nodes_count; i++)
 228     finish_loop_tree_node (&ira_loop_nodes[i]);
 229   ira_free (ira_loop_nodes);
 230   for (i = 0; i < (unsigned int) last_basic_block_before_change; i++)
 231     {
 232       if (ira_bb_nodes[i].local_copies != NULL)
 233         ira_free_bitmap (ira_bb_nodes[i].local_copies);
 234       if (ira_bb_nodes[i].border_allocnos != NULL)
 235         ira_free_bitmap (ira_bb_nodes[i].border_allocnos);
 236       if (ira_bb_nodes[i].modified_regnos != NULL)
 237         ira_free_bitmap (ira_bb_nodes[i].modified_regnos);
 238       if (ira_bb_nodes[i].all_allocnos != NULL)
 239         ira_free_bitmap (ira_bb_nodes[i].all_allocnos);
 240       if (ira_bb_nodes[i].regno_allocno_map != NULL)
 241         ira_free (ira_bb_nodes[i].regno_allocno_map);
 242     }
 243   ira_free (ira_bb_nodes);
 244 }
 245
 246 \f
 247
 248 /* The following recursive function adds LOOP to the loop tree
 249    hierarchy.  LOOP is added only once.  If LOOP is NULL we adding
 250    loop designating the whole function when CFG loops are not
 251    built.  */
 252 static void
 253 add_loop_to_tree (class loop *loop)
 254 {
 255   int loop_num;
 256   class loop *parent;
 257   ira_loop_tree_node_t loop_node, parent_node;
 258
 259   /* We cannot use loop node access macros here because of potential
 260      checking and because the nodes are not initialized enough
 261      yet.  */
 262   if (loop != NULL && loop_outer (loop) != NULL)
 263     add_loop_to_tree (loop_outer (loop));
 264   loop_num = loop != NULL ? loop->num : 0;
 265   if (ira_loop_nodes[loop_num].regno_allocno_map != NULL
 266       && ira_loop_nodes[loop_num].children == NULL)
 267     {
 268       /* We have not added loop node to the tree yet.  */
 269       loop_node = &ira_loop_nodes[loop_num];
 270       loop_node->loop = loop;
 271       loop_node->bb = NULL;
 272       if (loop == NULL)
 273         parent = NULL;
 274       else
 275         {
 276           for (parent = loop_outer (loop);
 277                parent != NULL;
 278                parent = loop_outer (parent))
 279             if (ira_loop_nodes[parent->num].regno_allocno_map != NULL)
 280               break;
 281         }
 282       if (parent == NULL)
 283         {
 284           loop_node->next = NULL;
 285           loop_node->subloop_next = NULL;
 286           loop_node->parent = NULL;
 287         }
 288       else
 289         {
 290           parent_node = &ira_loop_nodes[parent->num];
 291           loop_node->next = parent_node->children;
 292           parent_node->children = loop_node;
 293           loop_node->subloop_next = parent_node->subloops;
 294           parent_node->subloops = loop_node;
 295           loop_node->parent = parent_node;
 296         }
 297     }
 298 }
 299
 300 /* The following recursive function sets up levels of nodes of the
 301    tree given its root LOOP_NODE.  The enumeration starts with LEVEL.
 302    The function returns maximal value of level in the tree + 1.  */
 303 static int
 304 setup_loop_tree_level (ira_loop_tree_node_t loop_node, int level)
 305 {
 306   int height, max_height;
 307   ira_loop_tree_node_t subloop_node;
 308
 309   ira_assert (loop_node->bb == NULL);
 310   loop_node->level = level;
 311   max_height = level + 1;
 312   for (subloop_node = loop_node->subloops;
 313        subloop_node != NULL;
 314        subloop_node = subloop_node->subloop_next)
 315     {
 316       ira_assert (subloop_node->bb == NULL);
 317       height = setup_loop_tree_level (subloop_node, level + 1);
 318       if (height > max_height)
 319         max_height = height;
 320     }
 321   return max_height;
 322 }
 323
 324 /* Create the loop tree.  The algorithm is designed to provide correct
 325    order of loops (they are ordered by their last loop BB) and basic
 326    blocks in the chain formed by member next.  */
 327 static void
 328 form_loop_tree (void)
 329 {
 330   basic_block bb;
 331   class loop *parent;
 332   ira_loop_tree_node_t bb_node, loop_node;
 333
 334   /* We cannot use loop/bb node access macros because of potential
 335      checking and because the nodes are not initialized enough
 336      yet.  */
 337   FOR_EACH_BB_FN (bb, cfun)
 338     {
 339       bb_node = &ira_bb_nodes[bb->index];
 340       bb_node->bb = bb;
 341       bb_node->loop = NULL;
 342       bb_node->subloops = NULL;
 343       bb_node->children = NULL;
 344       bb_node->subloop_next = NULL;
 345       bb_node->next = NULL;
 346       if (current_loops == NULL)
 347         parent = NULL;
 348       else
 349         {
 350           for (parent = bb->loop_father;
 351                parent != NULL;
 352                parent = loop_outer (parent))
 353             if (ira_loop_nodes[parent->num].regno_allocno_map != NULL)
 354               break;
 355         }
 356       add_loop_to_tree (parent);
 357       loop_node = &ira_loop_nodes[parent == NULL ? 0 : parent->num];
 358       bb_node->next = loop_node->children;
 359       bb_node->parent = loop_node;
 360       loop_node->children = bb_node;
 361     }
 362   ira_loop_tree_root = IRA_LOOP_NODE_BY_INDEX (0);
 363   ira_loop_tree_height = setup_loop_tree_level (ira_loop_tree_root, 0);
 364   ira_assert (ira_loop_tree_root->regno_allocno_map != NULL);
 365 }
 366
 367 \f
 368
 369 /* Rebuild IRA_REGNO_ALLOCNO_MAP and REGNO_ALLOCNO_MAPs of the loop
 370    tree nodes.  */
 371 static void
 372 rebuild_regno_allocno_maps (void)
 373 {
 374   unsigned int l;
 375   int max_regno, regno;
 376   ira_allocno_t a;
 377   ira_loop_tree_node_t loop_tree_node;
 378   loop_p loop;
 379   ira_allocno_iterator ai;
 380
 381   ira_assert (current_loops != NULL);
 382   max_regno = max_reg_num ();
 383   FOR_EACH_VEC_SAFE_ELT (get_loops (cfun), l, loop)
 384     if (ira_loop_nodes[l].regno_allocno_map != NULL)
 385       {
 386         ira_free (ira_loop_nodes[l].regno_allocno_map);
 387         ira_loop_nodes[l].regno_allocno_map
 388           = (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t)
 389                                             * max_regno);
 390         memset (ira_loop_nodes[l].regno_allocno_map, 0,
 391                 sizeof (ira_allocno_t) * max_regno);
 392       }
 393   ira_free (ira_regno_allocno_map);
 394   ira_regno_allocno_map
 395     = (ira_allocno_t *) ira_allocate (max_regno * sizeof (ira_allocno_t));
 396   memset (ira_regno_allocno_map, 0, max_regno * sizeof (ira_allocno_t));
 397   FOR_EACH_ALLOCNO (a, ai)
 398     {
 399       if (ALLOCNO_CAP_MEMBER (a) != NULL)
 400         /* Caps are not in the regno allocno maps.  */
 401         continue;
 402       regno = ALLOCNO_REGNO (a);
 403       loop_tree_node = ALLOCNO_LOOP_TREE_NODE (a);
 404       ALLOCNO_NEXT_REGNO_ALLOCNO (a) = ira_regno_allocno_map[regno];
 405       ira_regno_allocno_map[regno] = a;
 406       if (loop_tree_node->regno_allocno_map[regno] == NULL)
 407         /* Remember that we can create temporary allocnos to break
 408            cycles in register shuffle.  */
 409         loop_tree_node->regno_allocno_map[regno] = a;
 410     }
 411 }
 412 \f
 413
 414 /* Pools for allocnos, allocno live ranges and objects.  */
 415 static object_allocator<live_range> live_range_pool ("live ranges");
 416 static object_allocator<ira_allocno> allocno_pool ("allocnos");
 417 static object_allocator<ira_object> object_pool ("objects");
 418
 419 /* Vec containing references to all created allocnos.  It is a
 420    container of array allocnos.  */
 421 static vec<ira_allocno_t> allocno_vec;
 422
 423 /* Vec containing references to all created ira_objects.  It is a
 424    container of ira_object_id_map.  */
 425 static vec<ira_object_t> ira_object_id_map_vec;
 426
 427 /* Initialize data concerning allocnos.  */
 428 static void
 429 initiate_allocnos (void)
 430 {
 431   allocno_vec.create (max_reg_num () * 2);
 432   ira_allocnos = NULL;
 433   ira_allocnos_num = 0;
 434   ira_objects_num = 0;
 435   ira_object_id_map_vec.create (max_reg_num () * 2);
 436   ira_object_id_map = NULL;
 437   ira_regno_allocno_map
 438     = (ira_allocno_t *) ira_allocate (max_reg_num ()
 439                                       * sizeof (ira_allocno_t));
 440   memset (ira_regno_allocno_map, 0, max_reg_num () * sizeof (ira_allocno_t));
 441 }
 442
 443 /* Create and return an object corresponding to a new allocno A.  */
 444 static ira_object_t
 445 ira_create_object (ira_allocno_t a, int subword)
 446 {
 447   enum reg_class aclass = ALLOCNO_CLASS (a);
 448   ira_object_t obj = object_pool.allocate ();
 449
 450   OBJECT_ALLOCNO (obj) = a;
 451   OBJECT_SUBWORD (obj) = subword;
 452   OBJECT_CONFLICT_ID (obj) = ira_objects_num;
 453   OBJECT_CONFLICT_VEC_P (obj) = false;
 454   OBJECT_CONFLICT_ARRAY (obj) = NULL;
 455   OBJECT_NUM_CONFLICTS (obj) = 0;
 456   OBJECT_CONFLICT_HARD_REGS (obj) = ira_no_alloc_regs;
 457   OBJECT_TOTAL_CONFLICT_HARD_REGS (obj) = ira_no_alloc_regs;
 458   OBJECT_CONFLICT_HARD_REGS (obj) |= ~reg_class_contents[aclass];
 459   OBJECT_TOTAL_CONFLICT_HARD_REGS (obj) |= ~reg_class_contents[aclass];
 460   OBJECT_MIN (obj) = INT_MAX;
 461   OBJECT_MAX (obj) = -1;
 462   OBJECT_LIVE_RANGES (obj) = NULL;
 463
 464   ira_object_id_map_vec.safe_push (obj);
 465   ira_object_id_map
 466     = ira_object_id_map_vec.address ();
 467   ira_objects_num = ira_object_id_map_vec.length ();
 468
 469   return obj;
 470 }
 471
 472 /* Create and return the allocno corresponding to REGNO in
 473    LOOP_TREE_NODE.  Add the allocno to the list of allocnos with the
 474    same regno if CAP_P is FALSE.  */
 475 ira_allocno_t
 476 ira_create_allocno (int regno, bool cap_p,
 477                     ira_loop_tree_node_t loop_tree_node)
 478 {
 479   ira_allocno_t a;
 480
 481   a = allocno_pool.allocate ();
 482   ALLOCNO_REGNO (a) = regno;
 483   ALLOCNO_LOOP_TREE_NODE (a) = loop_tree_node;
 484   if (! cap_p)
 485     {
 486       ALLOCNO_NEXT_REGNO_ALLOCNO (a) = ira_regno_allocno_map[regno];
 487       ira_regno_allocno_map[regno] = a;
 488       if (loop_tree_node->regno_allocno_map[regno] == NULL)
 489         /* Remember that we can create temporary allocnos to break
 490            cycles in register shuffle on region borders (see
 491            ira-emit.c).  */
 492         loop_tree_node->regno_allocno_map[regno] = a;
 493     }
 494   ALLOCNO_CAP (a) = NULL;
 495   ALLOCNO_CAP_MEMBER (a) = NULL;
 496   ALLOCNO_NUM (a) = ira_allocnos_num;
 497   bitmap_set_bit (loop_tree_node->all_allocnos, ALLOCNO_NUM (a));
 498   ALLOCNO_NREFS (a) = 0;
 499   ALLOCNO_FREQ (a) = 0;
 500   ALLOCNO_HARD_REGNO (a) = -1;
 501   ALLOCNO_CALL_FREQ (a) = 0;
 502   ALLOCNO_CALLS_CROSSED_NUM (a) = 0;
 503   ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a) = 0;
 504   ALLOCNO_CROSSED_CALLS_ABIS (a) = 0;
 505   CLEAR_HARD_REG_SET (ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS (a));
 506 #ifdef STACK_REGS
 507   ALLOCNO_NO_STACK_REG_P (a) = false;
 508   ALLOCNO_TOTAL_NO_STACK_REG_P (a) = false;
 509 #endif
 510   ALLOCNO_DONT_REASSIGN_P (a) = false;
 511   ALLOCNO_BAD_SPILL_P (a) = false;
 512   ALLOCNO_ASSIGNED_P (a) = false;
 513   ALLOCNO_MODE (a) = (regno < 0 ? VOIDmode : PSEUDO_REGNO_MODE (regno));
 514   ALLOCNO_WMODE (a) = ALLOCNO_MODE (a);
 515   ALLOCNO_PREFS (a) = NULL;
 516   ALLOCNO_COPIES (a) = NULL;
 517   ALLOCNO_HARD_REG_COSTS (a) = NULL;
 518   ALLOCNO_CONFLICT_HARD_REG_COSTS (a) = NULL;
 519   ALLOCNO_UPDATED_HARD_REG_COSTS (a) = NULL;
 520   ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) = NULL;
 521   ALLOCNO_CLASS (a) = NO_REGS;
 522   ALLOCNO_UPDATED_CLASS_COST (a) = 0;
 523   ALLOCNO_CLASS_COST (a) = 0;
 524   ALLOCNO_MEMORY_COST (a) = 0;
 525   ALLOCNO_UPDATED_MEMORY_COST (a) = 0;
 526   ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a) = 0;
 527   ALLOCNO_NUM_OBJECTS (a) = 0;
 528
 529   ALLOCNO_ADD_DATA (a) = NULL;
 530   allocno_vec.safe_push (a);
 531   ira_allocnos = allocno_vec.address ();
 532   ira_allocnos_num = allocno_vec.length ();
 533
 534   return a;
 535 }
 536
 537 /* Set up register class for A and update its conflict hard
 538    registers.  */
 539 void
 540 ira_set_allocno_class (ira_allocno_t a, enum reg_class aclass)
 541 {
 542   ira_allocno_object_iterator oi;
 543   ira_object_t obj;
 544
 545   ALLOCNO_CLASS (a) = aclass;
 546   FOR_EACH_ALLOCNO_OBJECT (a, obj, oi)
 547     {
 548       OBJECT_CONFLICT_HARD_REGS (obj) |= ~reg_class_contents[aclass];
 549       OBJECT_TOTAL_CONFLICT_HARD_REGS (obj) |= ~reg_class_contents[aclass];
 550     }
 551 }
 552
 553 /* Determine the number of objects we should associate with allocno A
 554    and allocate them.  */
 555 void
 556 ira_create_allocno_objects (ira_allocno_t a)
 557 {
 558   machine_mode mode = ALLOCNO_MODE (a);
 559   enum reg_class aclass = ALLOCNO_CLASS (a);
 560   int n = ira_reg_class_max_nregs[aclass][mode];
 561   int i;
 562
 563   if (n != 2 || maybe_ne (GET_MODE_SIZE (mode), n * UNITS_PER_WORD))
 564     n = 1;
 565
 566   ALLOCNO_NUM_OBJECTS (a) = n;
 567   for (i = 0; i < n; i++)
 568     ALLOCNO_OBJECT (a, i) = ira_create_object (a, i);
 569 }
 570
 571 /* For each allocno, set ALLOCNO_NUM_OBJECTS and create the
 572    ALLOCNO_OBJECT structures.  This must be called after the allocno
 573    classes are known.  */
 574 static void
 575 create_allocno_objects (void)
 576 {
 577   ira_allocno_t a;
 578   ira_allocno_iterator ai;
 579
 580   FOR_EACH_ALLOCNO (a, ai)
 581     ira_create_allocno_objects (a);
 582 }
 583
 584 /* Merge hard register conflict information for all objects associated with
 585    allocno TO into the corresponding objects associated with FROM.
 586    If TOTAL_ONLY is true, we only merge OBJECT_TOTAL_CONFLICT_HARD_REGS.  */
 587 static void
 588 merge_hard_reg_conflicts (ira_allocno_t from, ira_allocno_t to,
 589                           bool total_only)
 590 {
 591   int i;
 592   gcc_assert (ALLOCNO_NUM_OBJECTS (to) == ALLOCNO_NUM_OBJECTS (from));
 593   for (i = 0; i < ALLOCNO_NUM_OBJECTS (to); i++)
 594     {
 595       ira_object_t from_obj = ALLOCNO_OBJECT (from, i);
 596       ira_object_t to_obj = ALLOCNO_OBJECT (to, i);
 597
 598       if (!total_only)
 599         OBJECT_CONFLICT_HARD_REGS (to_obj)
 600           |= OBJECT_CONFLICT_HARD_REGS (from_obj);
 601       OBJECT_TOTAL_CONFLICT_HARD_REGS (to_obj)
 602         |= OBJECT_TOTAL_CONFLICT_HARD_REGS (from_obj);
 603     }
 604 #ifdef STACK_REGS
 605   if (!total_only && ALLOCNO_NO_STACK_REG_P (from))
 606     ALLOCNO_NO_STACK_REG_P (to) = true;
 607   if (ALLOCNO_TOTAL_NO_STACK_REG_P (from))
 608     ALLOCNO_TOTAL_NO_STACK_REG_P (to) = true;
 609 #endif
 610 }
 611
 612 /* Update hard register conflict information for all objects associated with
 613    A to include the regs in SET.  */
 614 void
 615 ior_hard_reg_conflicts (ira_allocno_t a, const_hard_reg_set set)
 616 {
 617   ira_allocno_object_iterator i;
 618   ira_object_t obj;
 619
 620   FOR_EACH_ALLOCNO_OBJECT (a, obj, i)
 621     {
 622       OBJECT_CONFLICT_HARD_REGS (obj) |= set;
 623       OBJECT_TOTAL_CONFLICT_HARD_REGS (obj) |= set;
 624     }
 625 }
 626
 627 /* Return TRUE if a conflict vector with NUM elements is more
 628    profitable than a conflict bit vector for OBJ.  */
 629 bool
 630 ira_conflict_vector_profitable_p (ira_object_t obj, int num)
 631 {
 632   int nbytes;
 633   int max = OBJECT_MAX (obj);
 634   int min = OBJECT_MIN (obj);
 635
 636   if (max < min)
 637     /* We prefer a bit vector in such case because it does not result
 638        in allocation.  */
 639     return false;
 640
 641   nbytes = (max - min) / 8 + 1;
 642   STATIC_ASSERT (sizeof (ira_object_t) <= 8);
 643   /* Don't use sizeof (ira_object_t), use constant 8.  Size of ira_object_t (a
 644      pointer) is different on 32-bit and 64-bit targets.  Usage sizeof
 645      (ira_object_t) can result in different code generation by GCC built as 32-
 646      and 64-bit program.  In any case the profitability is just an estimation
 647      and border cases are rare.  */
 648   return (2 * 8 /* sizeof (ira_object_t) */ * (num + 1) < 3 * nbytes);
 649 }
 650
 651 /* Allocates and initialize the conflict vector of OBJ for NUM
 652    conflicting objects.  */
 653 void
 654 ira_allocate_conflict_vec (ira_object_t obj, int num)
 655 {
 656   int size;
 657   ira_object_t *vec;
 658
 659   ira_assert (OBJECT_CONFLICT_ARRAY (obj) == NULL);
 660   num++; /* for NULL end marker  */
 661   size = sizeof (ira_object_t) * num;
 662   OBJECT_CONFLICT_ARRAY (obj) = ira_allocate (size);
 663   vec = (ira_object_t *) OBJECT_CONFLICT_ARRAY (obj);
 664   vec[0] = NULL;
 665   OBJECT_NUM_CONFLICTS (obj) = 0;
 666   OBJECT_CONFLICT_ARRAY_SIZE (obj) = size;
 667   OBJECT_CONFLICT_VEC_P (obj) = true;
 668 }
 669
 670 /* Allocate and initialize the conflict bit vector of OBJ.  */
 671 static void
 672 allocate_conflict_bit_vec (ira_object_t obj)
 673 {
 674   unsigned int size;
 675
 676   ira_assert (OBJECT_CONFLICT_ARRAY (obj) == NULL);
 677   size = ((OBJECT_MAX (obj) - OBJECT_MIN (obj) + IRA_INT_BITS)
 678           / IRA_INT_BITS * sizeof (IRA_INT_TYPE));
 679   OBJECT_CONFLICT_ARRAY (obj) = ira_allocate (size);
 680   memset (OBJECT_CONFLICT_ARRAY (obj), 0, size);
 681   OBJECT_CONFLICT_ARRAY_SIZE (obj) = size;
 682   OBJECT_CONFLICT_VEC_P (obj) = false;
 683 }
 684
 685 /* Allocate and initialize the conflict vector or conflict bit vector
 686    of OBJ for NUM conflicting allocnos whatever is more profitable.  */
 687 void
 688 ira_allocate_object_conflicts (ira_object_t obj, int num)
 689 {
 690   if (ira_conflict_vector_profitable_p (obj, num))
 691     ira_allocate_conflict_vec (obj, num);
 692   else
 693     allocate_conflict_bit_vec (obj);
 694 }
 695
 696 /* Add OBJ2 to the conflicts of OBJ1.  */
 697 static void
 698 add_to_conflicts (ira_object_t obj1, ira_object_t obj2)
 699 {
 700   int num;
 701   unsigned int size;
 702
 703   if (OBJECT_CONFLICT_VEC_P (obj1))
 704     {
 705       ira_object_t *vec = OBJECT_CONFLICT_VEC (obj1);
 706       int curr_num = OBJECT_NUM_CONFLICTS (obj1);
 707       num = curr_num + 2;
 708       if (OBJECT_CONFLICT_ARRAY_SIZE (obj1) < num * sizeof (ira_object_t))
 709         {
 710           ira_object_t *newvec;
 711           size = (3 * num / 2 + 1) * sizeof (ira_allocno_t);
 712           newvec = (ira_object_t *) ira_allocate (size);
 713           memcpy (newvec, vec, curr_num * sizeof (ira_object_t));
 714           ira_free (vec);
 715           vec = newvec;
 716           OBJECT_CONFLICT_ARRAY (obj1) = vec;
 717           OBJECT_CONFLICT_ARRAY_SIZE (obj1) = size;
 718         }
 719       vec[num - 2] = obj2;
 720       vec[num - 1] = NULL;
 721       OBJECT_NUM_CONFLICTS (obj1)++;
 722     }
 723   else
 724     {
 725       int nw, added_head_nw, id;
 726       IRA_INT_TYPE *vec = OBJECT_CONFLICT_BITVEC (obj1);
 727
 728       id = OBJECT_CONFLICT_ID (obj2);
 729       if (OBJECT_MIN (obj1) > id)
 730         {
 731           /* Expand head of the bit vector.  */
 732           added_head_nw = (OBJECT_MIN (obj1) - id - 1) / IRA_INT_BITS + 1;
 733           nw = (OBJECT_MAX (obj1) - OBJECT_MIN (obj1)) / IRA_INT_BITS + 1;
 734           size = (nw + added_head_nw) * sizeof (IRA_INT_TYPE);
 735           if (OBJECT_CONFLICT_ARRAY_SIZE (obj1) >= size)
 736             {
 737               memmove ((char *) vec + added_head_nw * sizeof (IRA_INT_TYPE),
 738                        vec, nw * sizeof (IRA_INT_TYPE));
 739               memset (vec, 0, added_head_nw * sizeof (IRA_INT_TYPE));
 740             }
 741           else
 742             {
 743               size
 744                 = (3 * (nw + added_head_nw) / 2 + 1) * sizeof (IRA_INT_TYPE);
 745               vec = (IRA_INT_TYPE *) ira_allocate (size);
 746               memcpy ((char *) vec + added_head_nw * sizeof (IRA_INT_TYPE),
 747                       OBJECT_CONFLICT_ARRAY (obj1), nw * sizeof (IRA_INT_TYPE));
 748               memset (vec, 0, added_head_nw * sizeof (IRA_INT_TYPE));
 749               memset ((char *) vec
 750                       + (nw + added_head_nw) * sizeof (IRA_INT_TYPE),
 751                       0, size - (nw + added_head_nw) * sizeof (IRA_INT_TYPE));
 752               ira_free (OBJECT_CONFLICT_ARRAY (obj1));
 753               OBJECT_CONFLICT_ARRAY (obj1) = vec;
 754               OBJECT_CONFLICT_ARRAY_SIZE (obj1) = size;
 755             }
 756           OBJECT_MIN (obj1) -= added_head_nw * IRA_INT_BITS;
 757         }
 758       else if (OBJECT_MAX (obj1) < id)
 759         {
 760           nw = (id - OBJECT_MIN (obj1)) / IRA_INT_BITS + 1;
 761           size = nw * sizeof (IRA_INT_TYPE);
 762           if (OBJECT_CONFLICT_ARRAY_SIZE (obj1) < size)
 763             {
 764               /* Expand tail of the bit vector.  */
 765               size = (3 * nw / 2 + 1) * sizeof (IRA_INT_TYPE);
 766               vec = (IRA_INT_TYPE *) ira_allocate (size);
 767               memcpy (vec, OBJECT_CONFLICT_ARRAY (obj1), OBJECT_CONFLICT_ARRAY_SIZE (obj1));
 768               memset ((char *) vec + OBJECT_CONFLICT_ARRAY_SIZE (obj1),
 769                       0, size - OBJECT_CONFLICT_ARRAY_SIZE (obj1));
 770               ira_free (OBJECT_CONFLICT_ARRAY (obj1));
 771               OBJECT_CONFLICT_ARRAY (obj1) = vec;
 772               OBJECT_CONFLICT_ARRAY_SIZE (obj1) = size;
 773             }
 774           OBJECT_MAX (obj1) = id;
 775         }
 776       SET_MINMAX_SET_BIT (vec, id, OBJECT_MIN (obj1), OBJECT_MAX (obj1));
 777     }
 778 }
 779
 780 /* Add OBJ1 to the conflicts of OBJ2 and vice versa.  */
 781 static void
 782 ira_add_conflict (ira_object_t obj1, ira_object_t obj2)
 783 {
 784   add_to_conflicts (obj1, obj2);
 785   add_to_conflicts (obj2, obj1);
 786 }
 787
 788 /* Clear all conflicts of OBJ.  */
 789 static void
 790 clear_conflicts (ira_object_t obj)
 791 {
 792   if (OBJECT_CONFLICT_VEC_P (obj))
 793     {
 794       OBJECT_NUM_CONFLICTS (obj) = 0;
 795       OBJECT_CONFLICT_VEC (obj)[0] = NULL;
 796     }
 797   else if (OBJECT_CONFLICT_ARRAY_SIZE (obj) != 0)
 798     {
 799       int nw;
 800
 801       nw = (OBJECT_MAX (obj) - OBJECT_MIN (obj)) / IRA_INT_BITS + 1;
 802       memset (OBJECT_CONFLICT_BITVEC (obj), 0, nw * sizeof (IRA_INT_TYPE));
 803     }
 804 }
 805
 806 /* The array used to find duplications in conflict vectors of
 807    allocnos.  */
 808 static int *conflict_check;
 809
 810 /* The value used to mark allocation presence in conflict vector of
 811    the current allocno.  */
 812 static int curr_conflict_check_tick;
 813
 814 /* Remove duplications in conflict vector of OBJ.  */
 815 static void
 816 compress_conflict_vec (ira_object_t obj)
 817 {
 818   ira_object_t *vec, conflict_obj;
 819   int i, j;
 820
 821   ira_assert (OBJECT_CONFLICT_VEC_P (obj));
 822   vec = OBJECT_CONFLICT_VEC (obj);
 823   curr_conflict_check_tick++;
 824   for (i = j = 0; (conflict_obj = vec[i]) != NULL; i++)
 825     {
 826       int id = OBJECT_CONFLICT_ID (conflict_obj);
 827       if (conflict_check[id] != curr_conflict_check_tick)
 828         {
 829           conflict_check[id] = curr_conflict_check_tick;
 830           vec[j++] = conflict_obj;
 831         }
 832     }
 833   OBJECT_NUM_CONFLICTS (obj) = j;
 834   vec[j] = NULL;
 835 }
 836
 837 /* Remove duplications in conflict vectors of all allocnos.  */
 838 static void
 839 compress_conflict_vecs (void)
 840 {
 841   ira_object_t obj;
 842   ira_object_iterator oi;
 843
 844   conflict_check = (int *) ira_allocate (sizeof (int) * ira_objects_num);
 845   memset (conflict_check, 0, sizeof (int) * ira_objects_num);
 846   curr_conflict_check_tick = 0;
 847   FOR_EACH_OBJECT (obj, oi)
 848     {
 849       if (OBJECT_CONFLICT_VEC_P (obj))
 850         compress_conflict_vec (obj);
 851     }
 852   ira_free (conflict_check);
 853 }
 854
 855 /* This recursive function outputs allocno A and if it is a cap the
 856    function outputs its members.  */
 857 void
 858 ira_print_expanded_allocno (ira_allocno_t a)
 859 {
 860   basic_block bb;
 861
 862   fprintf (ira_dump_file, " a%d(r%d", ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
 863   if ((bb = ALLOCNO_LOOP_TREE_NODE (a)->bb) != NULL)
 864     fprintf (ira_dump_file, ",b%d", bb->index);
 865   else
 866     fprintf (ira_dump_file, ",l%d", ALLOCNO_LOOP_TREE_NODE (a)->loop_num);
 867   if (ALLOCNO_CAP_MEMBER (a) != NULL)
 868     {
 869       fprintf (ira_dump_file, ":");
 870       ira_print_expanded_allocno (ALLOCNO_CAP_MEMBER (a));
 871     }
 872   fprintf (ira_dump_file, ")");
 873 }
 874
 875 /* Create and return the cap representing allocno A in the
 876    parent loop.  */
 877 static ira_allocno_t
 878 create_cap_allocno (ira_allocno_t a)
 879 {
 880   ira_allocno_t cap;
 881   ira_loop_tree_node_t parent;
 882   enum reg_class aclass;
 883
 884   parent = ALLOCNO_LOOP_TREE_NODE (a)->parent;
 885   cap = ira_create_allocno (ALLOCNO_REGNO (a), true, parent);
 886   ALLOCNO_MODE (cap) = ALLOCNO_MODE (a);
 887   ALLOCNO_WMODE (cap) = ALLOCNO_WMODE (a);
 888   aclass = ALLOCNO_CLASS (a);
 889   ira_set_allocno_class (cap, aclass);
 890   ira_create_allocno_objects (cap);
 891   ALLOCNO_CAP_MEMBER (cap) = a;
 892   ALLOCNO_CAP (a) = cap;
 893   ALLOCNO_CLASS_COST (cap) = ALLOCNO_CLASS_COST (a);
 894   ALLOCNO_MEMORY_COST (cap) = ALLOCNO_MEMORY_COST (a);
 895   ira_allocate_and_copy_costs
 896     (&ALLOCNO_HARD_REG_COSTS (cap), aclass, ALLOCNO_HARD_REG_COSTS (a));
 897   ira_allocate_and_copy_costs
 898     (&ALLOCNO_CONFLICT_HARD_REG_COSTS (cap), aclass,
 899      ALLOCNO_CONFLICT_HARD_REG_COSTS (a));
 900   ALLOCNO_BAD_SPILL_P (cap) = ALLOCNO_BAD_SPILL_P (a);
 901   ALLOCNO_NREFS (cap) = ALLOCNO_NREFS (a);
 902   ALLOCNO_FREQ (cap) = ALLOCNO_FREQ (a);
 903   ALLOCNO_CALL_FREQ (cap) = ALLOCNO_CALL_FREQ (a);
 904
 905   merge_hard_reg_conflicts (a, cap, false);
 906
 907   ALLOCNO_CALLS_CROSSED_NUM (cap) = ALLOCNO_CALLS_CROSSED_NUM (a);
 908   ALLOCNO_CHEAP_CALLS_CROSSED_NUM (cap) = ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a);
 909   ALLOCNO_CROSSED_CALLS_ABIS (cap) = ALLOCNO_CROSSED_CALLS_ABIS (a);
 910   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                                   const 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
1971       ira_assert (current_loops != NULL);
1972       FOR_EACH_EDGE (e, ei, loop_node->loop->header->preds)
1973         if (e->src != loop_node->loop->latch)
1974           create_loop_allocnos (e);
1975
1976       auto_vec<edge> edges = get_loop_exit_edges (loop_node->loop);
1977       FOR_EACH_VEC_ELT (edges, i, e)
1978         create_loop_allocnos (e);
1979     }
1980 }
1981
1982 /* Propagate information about allocnos modified inside the loop given
1983    by its LOOP_TREE_NODE to its parent.  */
1984 static void
1985 propagate_modified_regnos (ira_loop_tree_node_t loop_tree_node)
1986 {
1987   if (loop_tree_node == ira_loop_tree_root)
1988     return;
1989   ira_assert (loop_tree_node->bb == NULL);
1990   bitmap_ior_into (loop_tree_node->parent->modified_regnos,
1991                    loop_tree_node->modified_regnos);
1992 }
1993
1994 /* Propagate new info about allocno A (see comments about accumulated
1995    info in allocno definition) to the corresponding allocno on upper
1996    loop tree level.  So allocnos on upper levels accumulate
1997    information about the corresponding allocnos in nested regions.
1998    The new info means allocno info finally calculated in this
1999    file.  */
2000 static void
2001 propagate_allocno_info (void)
2002 {
2003   int i;
2004   ira_allocno_t a, parent_a;
2005   ira_loop_tree_node_t parent;
2006   enum reg_class aclass;
2007
2008   if (flag_ira_region != IRA_REGION_ALL
2009       && flag_ira_region != IRA_REGION_MIXED)
2010     return;
2011   for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--)
2012     for (a = ira_regno_allocno_map[i];
2013          a != NULL;
2014          a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
2015       if ((parent = ALLOCNO_LOOP_TREE_NODE (a)->parent) != NULL
2016           && (parent_a = parent->regno_allocno_map[i]) != NULL
2017           /* There are no caps yet at this point.  So use
2018              border_allocnos to find allocnos for the propagation.  */
2019           && bitmap_bit_p (ALLOCNO_LOOP_TREE_NODE (a)->border_allocnos,
2020                            ALLOCNO_NUM (a)))
2021         {
2022           if (! ALLOCNO_BAD_SPILL_P (a))
2023             ALLOCNO_BAD_SPILL_P (parent_a) = false;
2024           ALLOCNO_NREFS (parent_a) += ALLOCNO_NREFS (a);
2025           ALLOCNO_FREQ (parent_a) += ALLOCNO_FREQ (a);
2026           ALLOCNO_CALL_FREQ (parent_a) += ALLOCNO_CALL_FREQ (a);
2027           merge_hard_reg_conflicts (a, parent_a, true);
2028           ALLOCNO_CALLS_CROSSED_NUM (parent_a)
2029             += ALLOCNO_CALLS_CROSSED_NUM (a);
2030           ALLOCNO_CHEAP_CALLS_CROSSED_NUM (parent_a)
2031             += ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a);
2032           ALLOCNO_CROSSED_CALLS_ABIS (parent_a)
2033             |= ALLOCNO_CROSSED_CALLS_ABIS (a);
2034           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 cannot deal with such edges.  */
2165 static bool
2166 loop_with_complex_edge_p (class loop *loop)
2167 {
2168   int i;
2169   edge_iterator ei;
2170   edge e;
2171   bool res;
2172
2173   FOR_EACH_EDGE (e, ei, loop->header->preds)
2174     if (e->flags & EDGE_EH)
2175       return true;
2176   auto_vec<edge> edges = get_loop_exit_edges (loop);
2177   res = false;
2178   FOR_EACH_VEC_ELT (edges, i, e)
2179     if (e->flags & EDGE_COMPLEX)
2180       {
2181         res = true;
2182         break;
2183       }
2184   return res;
2185 }
2186 #endif
2187
2188 /* Sort loops for marking them for removal.  We put already marked
2189    loops first, then less frequent loops next, and then outer loops
2190    next.  */
2191 static int
2192 loop_compare_func (const void *v1p, const void *v2p)
2193 {
2194   int diff;
2195   ira_loop_tree_node_t l1 = *(const ira_loop_tree_node_t *) v1p;
2196   ira_loop_tree_node_t l2 = *(const ira_loop_tree_node_t *) v2p;
2197
2198   ira_assert (l1->parent != NULL && l2->parent != NULL);
2199   if (l1->to_remove_p && ! l2->to_remove_p)
2200     return -1;
2201   if (! l1->to_remove_p && l2->to_remove_p)
2202     return 1;
2203   if ((diff = l1->loop->header->count.to_frequency (cfun)
2204               - l2->loop->header->count.to_frequency (cfun)) != 0)
2205     return diff;
2206   if ((diff = (int) loop_depth (l1->loop) - (int) loop_depth (l2->loop)) != 0)
2207     return diff;
2208   /* Make sorting stable.  */
2209   return l1->loop_num - l2->loop_num;
2210 }
2211
2212 /* Mark loops which should be removed from regional allocation.  We
2213    remove a loop with low register pressure inside another loop with
2214    register pressure.  In this case a separate allocation of the loop
2215    hardly helps (for irregular register file architecture it could
2216    help by choosing a better hard register in the loop but we prefer
2217    faster allocation even in this case).  We also remove cheap loops
2218    if there are more than param_ira_max_loops_num of them.  Loop with EH
2219    exit or enter edges are removed too because the allocation might
2220    require put pseudo moves on the EH edges (we could still do this
2221    for pseudos with caller saved hard registers in some cases but it
2222    is impossible to say here or during top-down allocation pass what
2223    hard register the pseudos get finally).  */
2224 static void
2225 mark_loops_for_removal (void)
2226 {
2227   int i, n;
2228   ira_loop_tree_node_t *sorted_loops;
2229   loop_p loop;
2230
2231   ira_assert (current_loops != NULL);
2232   sorted_loops
2233     = (ira_loop_tree_node_t *) ira_allocate (sizeof (ira_loop_tree_node_t)
2234                                              * number_of_loops (cfun));
2235   for (n = i = 0; vec_safe_iterate (get_loops (cfun), i, &loop); i++)
2236     if (ira_loop_nodes[i].regno_allocno_map != NULL)
2237       {
2238         if (ira_loop_nodes[i].parent == NULL)
2239           {
2240             /* Don't remove the root.  */
2241             ira_loop_nodes[i].to_remove_p = false;
2242             continue;
2243           }
2244         sorted_loops[n++] = &ira_loop_nodes[i];
2245         ira_loop_nodes[i].to_remove_p
2246           = ((low_pressure_loop_node_p (ira_loop_nodes[i].parent)
2247               && low_pressure_loop_node_p (&ira_loop_nodes[i]))
2248 #ifdef STACK_REGS
2249              || loop_with_complex_edge_p (ira_loop_nodes[i].loop)
2250 #endif
2251              );
2252       }
2253   qsort (sorted_loops, n, sizeof (ira_loop_tree_node_t), loop_compare_func);
2254   for (i = 0; i < n - param_ira_max_loops_num; i++)
2255     {
2256       sorted_loops[i]->to_remove_p = true;
2257       if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
2258         fprintf
2259           (ira_dump_file,
2260            "  Mark loop %d (header %d, freq %d, depth %d) for removal (%s)\n",
2261            sorted_loops[i]->loop_num, sorted_loops[i]->loop->header->index,
2262            sorted_loops[i]->loop->header->count.to_frequency (cfun),
2263            loop_depth (sorted_loops[i]->loop),
2264            low_pressure_loop_node_p (sorted_loops[i]->parent)
2265            && low_pressure_loop_node_p (sorted_loops[i])
2266            ? "low pressure" : "cheap loop");
2267     }
2268   ira_free (sorted_loops);
2269 }
2270
2271 /* Mark all loops but root for removing.  */
2272 static void
2273 mark_all_loops_for_removal (void)
2274 {
2275   int i;
2276   loop_p loop;
2277
2278   ira_assert (current_loops != NULL);
2279   FOR_EACH_VEC_SAFE_ELT (get_loops (cfun), i, loop)
2280     if (ira_loop_nodes[i].regno_allocno_map != NULL)
2281       {
2282         if (ira_loop_nodes[i].parent == NULL)
2283           {
2284             /* Don't remove the root.  */
2285             ira_loop_nodes[i].to_remove_p = false;
2286             continue;
2287           }
2288         ira_loop_nodes[i].to_remove_p = true;
2289         if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
2290           fprintf
2291             (ira_dump_file,
2292              "  Mark loop %d (header %d, freq %d, depth %d) for removal\n",
2293              ira_loop_nodes[i].loop_num,
2294              ira_loop_nodes[i].loop->header->index,
2295              ira_loop_nodes[i].loop->header->count.to_frequency (cfun),
2296              loop_depth (ira_loop_nodes[i].loop));
2297       }
2298 }
2299
2300 /* Definition of vector of loop tree nodes.  */
2301
2302 /* Vec containing references to all removed loop tree nodes.  */
2303 static vec<ira_loop_tree_node_t> removed_loop_vec;
2304
2305 /* Vec containing references to all children of loop tree nodes.  */
2306 static vec<ira_loop_tree_node_t> children_vec;
2307
2308 /* Remove subregions of NODE if their separate allocation will not
2309    improve the result.  */
2310 static void
2311 remove_uneccesary_loop_nodes_from_loop_tree (ira_loop_tree_node_t node)
2312 {
2313   unsigned int start;
2314   bool remove_p;
2315   ira_loop_tree_node_t subnode;
2316
2317   remove_p = node->to_remove_p;
2318   if (! remove_p)
2319     children_vec.safe_push (node);
2320   start = children_vec.length ();
2321   for (subnode = node->children; subnode != NULL; subnode = subnode->next)
2322     if (subnode->bb == NULL)
2323       remove_uneccesary_loop_nodes_from_loop_tree (subnode);
2324     else
2325       children_vec.safe_push (subnode);
2326   node->children = node->subloops = NULL;
2327   if (remove_p)
2328     {
2329       removed_loop_vec.safe_push (node);
2330       return;
2331     }
2332   while (children_vec.length () > start)
2333     {
2334       subnode = children_vec.pop ();
2335       subnode->parent = node;
2336       subnode->next = node->children;
2337       node->children = subnode;
2338       if (subnode->bb == NULL)
2339         {
2340           subnode->subloop_next = node->subloops;
2341           node->subloops = subnode;
2342         }
2343     }
2344 }
2345
2346 /* Return TRUE if NODE is inside PARENT.  */
2347 static bool
2348 loop_is_inside_p (ira_loop_tree_node_t node, ira_loop_tree_node_t parent)
2349 {
2350   for (node = node->parent; node != NULL; node = node->parent)
2351     if (node == parent)
2352       return true;
2353   return false;
2354 }
2355
2356 /* Sort allocnos according to their order in regno allocno list.  */
2357 static int
2358 regno_allocno_order_compare_func (const void *v1p, const void *v2p)
2359 {
2360   ira_allocno_t a1 = *(const ira_allocno_t *) v1p;
2361   ira_allocno_t a2 = *(const ira_allocno_t *) v2p;
2362   ira_loop_tree_node_t n1 = ALLOCNO_LOOP_TREE_NODE (a1);
2363   ira_loop_tree_node_t n2 = ALLOCNO_LOOP_TREE_NODE (a2);
2364
2365   if (loop_is_inside_p (n1, n2))
2366     return -1;
2367   else if (loop_is_inside_p (n2, n1))
2368     return 1;
2369   /* If allocnos are equally good, sort by allocno numbers, so that
2370      the results of qsort leave nothing to chance.  We put allocnos
2371      with higher number first in the list because it is the original
2372      order for allocnos from loops on the same levels.  */
2373   return ALLOCNO_NUM (a2) - ALLOCNO_NUM (a1);
2374 }
2375
2376 /* This array is used to sort allocnos to restore allocno order in
2377    the regno allocno list.  */
2378 static ira_allocno_t *regno_allocnos;
2379
2380 /* Restore allocno order for REGNO in the regno allocno list.  */
2381 static void
2382 ira_rebuild_regno_allocno_list (int regno)
2383 {
2384   int i, n;
2385   ira_allocno_t a;
2386
2387   for (n = 0, a = ira_regno_allocno_map[regno];
2388        a != NULL;
2389        a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
2390     regno_allocnos[n++] = a;
2391   ira_assert (n > 0);
2392   qsort (regno_allocnos, n, sizeof (ira_allocno_t),
2393          regno_allocno_order_compare_func);
2394   for (i = 1; i < n; i++)
2395     ALLOCNO_NEXT_REGNO_ALLOCNO (regno_allocnos[i - 1]) = regno_allocnos[i];
2396   ALLOCNO_NEXT_REGNO_ALLOCNO (regno_allocnos[n - 1]) = NULL;
2397   ira_regno_allocno_map[regno] = regno_allocnos[0];
2398   if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
2399     fprintf (ira_dump_file, " Rebuilding regno allocno list for %d\n", regno);
2400 }
2401
2402 /* Propagate info from allocno FROM_A to allocno A.  */
2403 static void
2404 propagate_some_info_from_allocno (ira_allocno_t a, ira_allocno_t from_a)
2405 {
2406   enum reg_class aclass;
2407
2408   merge_hard_reg_conflicts (from_a, a, false);
2409   ALLOCNO_NREFS (a) += ALLOCNO_NREFS (from_a);
2410   ALLOCNO_FREQ (a) += ALLOCNO_FREQ (from_a);
2411   ALLOCNO_CALL_FREQ (a) += ALLOCNO_CALL_FREQ (from_a);
2412   ALLOCNO_CALLS_CROSSED_NUM (a) += ALLOCNO_CALLS_CROSSED_NUM (from_a);
2413   ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a)
2414     += ALLOCNO_CHEAP_CALLS_CROSSED_NUM (from_a);
2415   ALLOCNO_CROSSED_CALLS_ABIS (a) |= ALLOCNO_CROSSED_CALLS_ABIS (from_a);
2416   ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS (a)
2417     |= ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS (from_a);
2418
2419   ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a)
2420     += ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (from_a);
2421   if (! ALLOCNO_BAD_SPILL_P (from_a))
2422     ALLOCNO_BAD_SPILL_P (a) = false;
2423   aclass = ALLOCNO_CLASS (from_a);
2424   ira_assert (aclass == ALLOCNO_CLASS (a));
2425   ira_allocate_and_accumulate_costs (&ALLOCNO_HARD_REG_COSTS (a), aclass,
2426                                      ALLOCNO_HARD_REG_COSTS (from_a));
2427   ira_allocate_and_accumulate_costs (&ALLOCNO_CONFLICT_HARD_REG_COSTS (a),
2428                                      aclass,
2429                                      ALLOCNO_CONFLICT_HARD_REG_COSTS (from_a));
2430   ALLOCNO_CLASS_COST (a) += ALLOCNO_CLASS_COST (from_a);
2431   ALLOCNO_MEMORY_COST (a) += ALLOCNO_MEMORY_COST (from_a);
2432 }
2433
2434 /* Remove allocnos from loops removed from the allocation
2435    consideration.  */
2436 static void
2437 remove_unnecessary_allocnos (void)
2438 {
2439   int regno;
2440   bool merged_p, rebuild_p;
2441   ira_allocno_t a, prev_a, next_a, parent_a;
2442   ira_loop_tree_node_t a_node, parent;
2443
2444   merged_p = false;
2445   regno_allocnos = NULL;
2446   for (regno = max_reg_num () - 1; regno >= FIRST_PSEUDO_REGISTER; regno--)
2447     {
2448       rebuild_p = false;
2449       for (prev_a = NULL, a = ira_regno_allocno_map[regno];
2450            a != NULL;
2451            a = next_a)
2452         {
2453           next_a = ALLOCNO_NEXT_REGNO_ALLOCNO (a);
2454           a_node = ALLOCNO_LOOP_TREE_NODE (a);
2455           if (! a_node->to_remove_p)
2456             prev_a = a;
2457           else
2458             {
2459               for (parent = a_node->parent;
2460                    (parent_a = parent->regno_allocno_map[regno]) == NULL
2461                      && parent->to_remove_p;
2462                    parent = parent->parent)
2463                 ;
2464               if (parent_a == NULL)
2465                 {
2466                   /* There are no allocnos with the same regno in
2467                      upper region -- just move the allocno to the
2468                      upper region.  */
2469                   prev_a = a;
2470                   ALLOCNO_LOOP_TREE_NODE (a) = parent;
2471                   parent->regno_allocno_map[regno] = a;
2472                   bitmap_set_bit (parent->all_allocnos, ALLOCNO_NUM (a));
2473                   rebuild_p = true;
2474                 }
2475               else
2476                 {
2477                   /* Remove the allocno and update info of allocno in
2478                      the upper region.  */
2479                   if (prev_a == NULL)
2480                     ira_regno_allocno_map[regno] = next_a;
2481                   else
2482                     ALLOCNO_NEXT_REGNO_ALLOCNO (prev_a) = next_a;
2483                   move_allocno_live_ranges (a, parent_a);
2484                   merged_p = true;
2485                   propagate_some_info_from_allocno (parent_a, a);
2486                   /* Remove it from the corresponding regno allocno
2487                      map to avoid info propagation of subsequent
2488                      allocno into this already removed allocno.  */
2489                   a_node->regno_allocno_map[regno] = NULL;
2490                   ira_remove_allocno_prefs (a);
2491                   finish_allocno (a);
2492                 }
2493             }
2494         }
2495       if (rebuild_p)
2496         /* We need to restore the order in regno allocno list.  */
2497         {
2498           if (regno_allocnos == NULL)
2499             regno_allocnos
2500               = (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t)
2501                                                 * ira_allocnos_num);
2502           ira_rebuild_regno_allocno_list (regno);
2503         }
2504     }
2505   if (merged_p)
2506     ira_rebuild_start_finish_chains ();
2507   if (regno_allocnos != NULL)
2508     ira_free (regno_allocnos);
2509 }
2510
2511 /* Remove allocnos from all loops but the root.  */
2512 static void
2513 remove_low_level_allocnos (void)
2514 {
2515   int regno;
2516   bool merged_p, propagate_p;
2517   ira_allocno_t a, top_a;
2518   ira_loop_tree_node_t a_node, parent;
2519   ira_allocno_iterator ai;
2520
2521   merged_p = false;
2522   FOR_EACH_ALLOCNO (a, ai)
2523     {
2524       a_node = ALLOCNO_LOOP_TREE_NODE (a);
2525       if (a_node == ira_loop_tree_root || ALLOCNO_CAP_MEMBER (a) != NULL)
2526         continue;
2527       regno = ALLOCNO_REGNO (a);
2528       if ((top_a = ira_loop_tree_root->regno_allocno_map[regno]) == NULL)
2529         {
2530           ALLOCNO_LOOP_TREE_NODE (a) = ira_loop_tree_root;
2531           ira_loop_tree_root->regno_allocno_map[regno] = a;
2532           continue;
2533         }
2534       propagate_p = a_node->parent->regno_allocno_map[regno] == NULL;
2535       /* Remove the allocno and update info of allocno in the upper
2536          region.  */
2537       move_allocno_live_ranges (a, top_a);
2538       merged_p = true;
2539       if (propagate_p)
2540         propagate_some_info_from_allocno (top_a, a);
2541     }
2542   FOR_EACH_ALLOCNO (a, ai)
2543     {
2544       a_node = ALLOCNO_LOOP_TREE_NODE (a);
2545       if (a_node == ira_loop_tree_root)
2546         continue;
2547       parent = a_node->parent;
2548       regno = ALLOCNO_REGNO (a);
2549       if (ALLOCNO_CAP_MEMBER (a) != NULL)
2550         ira_assert (ALLOCNO_CAP (a) != NULL);
2551       else if (ALLOCNO_CAP (a) == NULL)
2552         ira_assert (parent->regno_allocno_map[regno] != NULL);
2553     }
2554   FOR_EACH_ALLOCNO (a, ai)
2555     {
2556       regno = ALLOCNO_REGNO (a);
2557       if (ira_loop_tree_root->regno_allocno_map[regno] == a)
2558         {
2559           ira_object_t obj;
2560           ira_allocno_object_iterator oi;
2561
2562           ira_regno_allocno_map[regno] = a;
2563           ALLOCNO_NEXT_REGNO_ALLOCNO (a) = NULL;
2564           ALLOCNO_CAP_MEMBER (a) = NULL;
2565           FOR_EACH_ALLOCNO_OBJECT (a, obj, oi)
2566             OBJECT_CONFLICT_HARD_REGS (obj)
2567               = OBJECT_TOTAL_CONFLICT_HARD_REGS (obj);
2568 #ifdef STACK_REGS
2569           if (ALLOCNO_TOTAL_NO_STACK_REG_P (a))
2570             ALLOCNO_NO_STACK_REG_P (a) = true;
2571 #endif
2572         }
2573       else
2574         {
2575           ira_remove_allocno_prefs (a);
2576           finish_allocno (a);
2577         }
2578     }
2579   if (merged_p)
2580     ira_rebuild_start_finish_chains ();
2581 }
2582
2583 /* Remove loops from consideration.  We remove all loops except for
2584    root if ALL_P or loops for which a separate allocation will not
2585    improve the result.  We have to do this after allocno creation and
2586    their costs and allocno class evaluation because only after that
2587    the register pressure can be known and is calculated.  */
2588 static void
2589 remove_unnecessary_regions (bool all_p)
2590 {
2591   if (current_loops == NULL)
2592     return;
2593   if (all_p)
2594     mark_all_loops_for_removal ();
2595   else
2596     mark_loops_for_removal ();
2597   children_vec.create (last_basic_block_for_fn (cfun)
2598                        + number_of_loops (cfun));
2599   removed_loop_vec.create (last_basic_block_for_fn (cfun)
2600                            + number_of_loops (cfun));
2601   remove_uneccesary_loop_nodes_from_loop_tree (ira_loop_tree_root);
2602   children_vec.release ();
2603   if (all_p)
2604     remove_low_level_allocnos ();
2605   else
2606     remove_unnecessary_allocnos ();
2607   while (removed_loop_vec.length () > 0)
2608     finish_loop_tree_node (removed_loop_vec.pop ());
2609   removed_loop_vec.release ();
2610 }
2611
2612 \f
2613
2614 /* At this point true value of allocno attribute bad_spill_p means
2615    that there is an insn where allocno occurs and where the allocno
2616    cannot be used as memory.  The function updates the attribute, now
2617    it can be true only for allocnos which cannot be used as memory in
2618    an insn and in whose live ranges there is other allocno deaths.
2619    Spilling allocnos with true value will not improve the code because
2620    it will not make other allocnos colorable and additional reloads
2621    for the corresponding pseudo will be generated in reload pass for
2622    each insn it occurs.
2623
2624    This is a trick mentioned in one classic article of Chaitin etc
2625    which is frequently omitted in other implementations of RA based on
2626    graph coloring.  */
2627 static void
2628 update_bad_spill_attribute (void)
2629 {
2630   int i;
2631   ira_allocno_t a;
2632   ira_allocno_iterator ai;
2633   ira_allocno_object_iterator aoi;
2634   ira_object_t obj;
2635   live_range_t r;
2636   enum reg_class aclass;
2637   bitmap_head dead_points[N_REG_CLASSES];
2638
2639   for (i = 0; i < ira_allocno_classes_num; i++)
2640     {
2641       aclass = ira_allocno_classes[i];
2642       bitmap_initialize (&dead_points[aclass], &reg_obstack);
2643     }
2644   FOR_EACH_ALLOCNO (a, ai)
2645     {
2646       aclass = ALLOCNO_CLASS (a);
2647       if (aclass == NO_REGS)
2648         continue;
2649       FOR_EACH_ALLOCNO_OBJECT (a, obj, aoi)
2650         for (r = OBJECT_LIVE_RANGES (obj); r != NULL; r = r->next)
2651           bitmap_set_bit (&dead_points[aclass], r->finish);
2652     }
2653   FOR_EACH_ALLOCNO (a, ai)
2654     {
2655       aclass = ALLOCNO_CLASS (a);
2656       if (aclass == NO_REGS)
2657         continue;
2658       if (! ALLOCNO_BAD_SPILL_P (a))
2659         continue;
2660       FOR_EACH_ALLOCNO_OBJECT (a, obj, aoi)
2661         {
2662           for (r = OBJECT_LIVE_RANGES (obj); r != NULL; r = r->next)
2663             {
2664               for (i = r->start + 1; i < r->finish; i++)
2665                 if (bitmap_bit_p (&dead_points[aclass], i))
2666                   break;
2667               if (i < r->finish)
2668                 break;
2669             }
2670           if (r != NULL)
2671             {
2672               ALLOCNO_BAD_SPILL_P (a) = false;
2673               break;
2674             }
2675         }
2676     }
2677   for (i = 0; i < ira_allocno_classes_num; i++)
2678     {
2679       aclass = ira_allocno_classes[i];
2680       bitmap_clear (&dead_points[aclass]);
2681     }
2682 }
2683
2684 \f
2685
2686 /* Set up minimal and maximal live range points for allocnos.  */
2687 static void
2688 setup_min_max_allocno_live_range_point (void)
2689 {
2690   int i;
2691   ira_allocno_t a, parent_a, cap;
2692   ira_allocno_iterator ai;
2693 #ifdef ENABLE_IRA_CHECKING
2694   ira_object_iterator oi;
2695   ira_object_t obj;
2696 #endif
2697   live_range_t r;
2698   ira_loop_tree_node_t parent;
2699
2700   FOR_EACH_ALLOCNO (a, ai)
2701     {
2702       int n = ALLOCNO_NUM_OBJECTS (a);
2703
2704       for (i = 0; i < n; i++)
2705         {
2706           ira_object_t obj = ALLOCNO_OBJECT (a, i);
2707           r = OBJECT_LIVE_RANGES (obj);
2708           if (r == NULL)
2709             continue;
2710           OBJECT_MAX (obj) = r->finish;
2711           for (; r->next != NULL; r = r->next)
2712             ;
2713           OBJECT_MIN (obj) = r->start;
2714         }
2715     }
2716   for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--)
2717     for (a = ira_regno_allocno_map[i];
2718          a != NULL;
2719          a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
2720       {
2721         int j;
2722         int n = ALLOCNO_NUM_OBJECTS (a);
2723
2724         for (j = 0; j < n; j++)
2725           {
2726             ira_object_t obj = ALLOCNO_OBJECT (a, j);
2727             ira_object_t parent_obj;
2728
2729             if (OBJECT_MAX (obj) < 0)
2730               {
2731                 /* The object is not used and hence does not live.  */
2732                 ira_assert (OBJECT_LIVE_RANGES (obj) == NULL);
2733                 OBJECT_MAX (obj) = 0;
2734                 OBJECT_MIN (obj) = 1;
2735                 continue;
2736               }
2737             ira_assert (ALLOCNO_CAP_MEMBER (a) == NULL);
2738             /* Accumulation of range info.  */
2739             if (ALLOCNO_CAP (a) != NULL)
2740               {
2741                 for (cap = ALLOCNO_CAP (a); cap != NULL; cap = ALLOCNO_CAP (cap))
2742                   {
2743                     ira_object_t cap_obj = ALLOCNO_OBJECT (cap, j);
2744                     if (OBJECT_MAX (cap_obj) < OBJECT_MAX (obj))
2745                       OBJECT_MAX (cap_obj) = OBJECT_MAX (obj);
2746                     if (OBJECT_MIN (cap_obj) > OBJECT_MIN (obj))
2747                       OBJECT_MIN (cap_obj) = OBJECT_MIN (obj);
2748                   }
2749                 continue;
2750               }
2751             if ((parent = ALLOCNO_LOOP_TREE_NODE (a)->parent) == NULL)
2752               continue;
2753             parent_a = parent->regno_allocno_map[i];
2754             parent_obj = ALLOCNO_OBJECT (parent_a, j);
2755             if (OBJECT_MAX (parent_obj) < OBJECT_MAX (obj))
2756               OBJECT_MAX (parent_obj) = OBJECT_MAX (obj);
2757             if (OBJECT_MIN (parent_obj) > OBJECT_MIN (obj))
2758               OBJECT_MIN (parent_obj) = OBJECT_MIN (obj);
2759           }
2760       }
2761 #ifdef ENABLE_IRA_CHECKING
2762   FOR_EACH_OBJECT (obj, oi)
2763     {
2764       if ((OBJECT_MIN (obj) >= 0 && OBJECT_MIN (obj) <= ira_max_point)
2765           && (OBJECT_MAX (obj) >= 0 && OBJECT_MAX (obj) <= ira_max_point))
2766         continue;
2767       gcc_unreachable ();
2768     }
2769 #endif
2770 }
2771
2772 /* Sort allocnos according to their live ranges.  Allocnos with
2773    smaller allocno class are put first unless we use priority
2774    coloring.  Allocnos with the same class are ordered according
2775    their start (min).  Allocnos with the same start are ordered
2776    according their finish (max).  */
2777 static int
2778 object_range_compare_func (const void *v1p, const void *v2p)
2779 {
2780   int diff;
2781   ira_object_t obj1 = *(const ira_object_t *) v1p;
2782   ira_object_t obj2 = *(const ira_object_t *) v2p;
2783   ira_allocno_t a1 = OBJECT_ALLOCNO (obj1);
2784   ira_allocno_t a2 = OBJECT_ALLOCNO (obj2);
2785
2786   if ((diff = OBJECT_MIN (obj1) - OBJECT_MIN (obj2)) != 0)
2787     return diff;
2788   if ((diff = OBJECT_MAX (obj1) - OBJECT_MAX (obj2)) != 0)
2789      return diff;
2790   return ALLOCNO_NUM (a1) - ALLOCNO_NUM (a2);
2791 }
2792
2793 /* Sort ira_object_id_map and set up conflict id of allocnos.  */
2794 static void
2795 sort_conflict_id_map (void)
2796 {
2797   int i, num;
2798   ira_allocno_t a;
2799   ira_allocno_iterator ai;
2800
2801   num = 0;
2802   FOR_EACH_ALLOCNO (a, ai)
2803     {
2804       ira_allocno_object_iterator oi;
2805       ira_object_t obj;
2806
2807       FOR_EACH_ALLOCNO_OBJECT (a, obj, oi)
2808         ira_object_id_map[num++] = obj;
2809     }
2810   if (num > 1)
2811     qsort (ira_object_id_map, num, sizeof (ira_object_t),
2812            object_range_compare_func);
2813   for (i = 0; i < num; i++)
2814     {
2815       ira_object_t obj = ira_object_id_map[i];
2816
2817       gcc_assert (obj != NULL);
2818       OBJECT_CONFLICT_ID (obj) = i;
2819     }
2820   for (i = num; i < ira_objects_num; i++)
2821     ira_object_id_map[i] = NULL;
2822 }
2823
2824 /* Set up minimal and maximal conflict ids of allocnos with which
2825    given allocno can conflict.  */
2826 static void
2827 setup_min_max_conflict_allocno_ids (void)
2828 {
2829   int aclass;
2830   int i, j, min, max, start, finish, first_not_finished, filled_area_start;
2831   int *live_range_min, *last_lived;
2832   int word0_min, word0_max;
2833   ira_allocno_t a;
2834   ira_allocno_iterator ai;
2835
2836   live_range_min = (int *) ira_allocate (sizeof (int) * ira_objects_num);
2837   aclass = -1;
2838   first_not_finished = -1;
2839   for (i = 0; i < ira_objects_num; i++)
2840     {
2841       ira_object_t obj = ira_object_id_map[i];
2842
2843       if (obj == NULL)
2844         continue;
2845
2846       a = OBJECT_ALLOCNO (obj);
2847
2848       if (aclass < 0)
2849         {
2850           aclass = ALLOCNO_CLASS (a);
2851           min = i;
2852           first_not_finished = i;
2853         }
2854       else
2855         {
2856           start = OBJECT_MIN (obj);
2857           /* If we skip an allocno, the allocno with smaller ids will
2858              be also skipped because of the secondary sorting the
2859              range finishes (see function
2860              object_range_compare_func).  */
2861           while (first_not_finished < i
2862                  && start > OBJECT_MAX (ira_object_id_map
2863                                         [first_not_finished]))
2864             first_not_finished++;
2865           min = first_not_finished;
2866         }
2867       if (min == i)
2868         /* We could increase min further in this case but it is good
2869            enough.  */
2870         min++;
2871       live_range_min[i] = OBJECT_MIN (obj);
2872       OBJECT_MIN (obj) = min;
2873     }
2874   last_lived = (int *) ira_allocate (sizeof (int) * ira_max_point);
2875   aclass = -1;
2876   filled_area_start = -1;
2877   for (i = ira_objects_num - 1; i >= 0; i--)
2878     {
2879       ira_object_t obj = ira_object_id_map[i];
2880
2881       if (obj == NULL)
2882         continue;
2883
2884       a = OBJECT_ALLOCNO (obj);
2885       if (aclass < 0)
2886         {
2887           aclass = ALLOCNO_CLASS (a);
2888           for (j = 0; j < ira_max_point; j++)
2889             last_lived[j] = -1;
2890           filled_area_start = ira_max_point;
2891         }
2892       min = live_range_min[i];
2893       finish = OBJECT_MAX (obj);
2894       max = last_lived[finish];
2895       if (max < 0)
2896         /* We could decrease max further in this case but it is good
2897            enough.  */
2898         max = OBJECT_CONFLICT_ID (obj) - 1;
2899       OBJECT_MAX (obj) = max;
2900       /* In filling, we can go further A range finish to recognize
2901          intersection quickly because if the finish of subsequently
2902          processed allocno (it has smaller conflict id) range is
2903          further A range finish than they are definitely intersected
2904          (the reason for this is the allocnos with bigger conflict id
2905          have their range starts not smaller than allocnos with
2906          smaller ids.  */
2907       for (j = min; j < filled_area_start; j++)
2908         last_lived[j] = i;
2909       filled_area_start = min;
2910     }
2911   ira_free (last_lived);
2912   ira_free (live_range_min);
2913
2914   /* For allocnos with more than one object, we may later record extra conflicts in
2915      subobject 0 that we cannot really know about here.
2916      For now, simply widen the min/max range of these subobjects.  */
2917
2918   word0_min = INT_MAX;
2919   word0_max = INT_MIN;
2920
2921   FOR_EACH_ALLOCNO (a, ai)
2922     {
2923       int n = ALLOCNO_NUM_OBJECTS (a);
2924       ira_object_t obj0;
2925
2926       if (n < 2)
2927         continue;
2928       obj0 = ALLOCNO_OBJECT (a, 0);
2929       if (OBJECT_CONFLICT_ID (obj0) < word0_min)
2930         word0_min = OBJECT_CONFLICT_ID (obj0);
2931       if (OBJECT_CONFLICT_ID (obj0) > word0_max)
2932         word0_max = OBJECT_CONFLICT_ID (obj0);
2933     }
2934   FOR_EACH_ALLOCNO (a, ai)
2935     {
2936       int n = ALLOCNO_NUM_OBJECTS (a);
2937       ira_object_t obj0;
2938
2939       if (n < 2)
2940         continue;
2941       obj0 = ALLOCNO_OBJECT (a, 0);
2942       if (OBJECT_MIN (obj0) > word0_min)
2943         OBJECT_MIN (obj0) = word0_min;
2944       if (OBJECT_MAX (obj0) < word0_max)
2945         OBJECT_MAX (obj0) = word0_max;
2946     }
2947 }
2948
2949 \f
2950
2951 static void
2952 create_caps (void)
2953 {
2954   ira_allocno_t a;
2955   ira_allocno_iterator ai;
2956   ira_loop_tree_node_t loop_tree_node;
2957
2958   FOR_EACH_ALLOCNO (a, ai)
2959     {
2960       if (ALLOCNO_LOOP_TREE_NODE (a) == ira_loop_tree_root)
2961         continue;
2962       if (ALLOCNO_CAP_MEMBER (a) != NULL)
2963         create_cap_allocno (a);
2964       else if (ALLOCNO_CAP (a) == NULL)
2965         {
2966           loop_tree_node = ALLOCNO_LOOP_TREE_NODE (a);
2967           if (!bitmap_bit_p (loop_tree_node->border_allocnos, ALLOCNO_NUM (a)))
2968             create_cap_allocno (a);
2969         }
2970     }
2971 }
2972
2973 \f
2974
2975 /* The page contains code transforming more one region internal
2976    representation (IR) to one region IR which is necessary for reload.
2977    This transformation is called IR flattening.  We might just rebuild
2978    the IR for one region but we don't do it because it takes a lot of
2979    time.  */
2980
2981 /* Map: regno -> allocnos which will finally represent the regno for
2982    IR with one region.  */
2983 static ira_allocno_t *regno_top_level_allocno_map;
2984
2985 /* Find the allocno that corresponds to A at a level one higher up in the
2986    loop tree.  Returns NULL if A is a cap, or if it has no parent.  */
2987 ira_allocno_t
2988 ira_parent_allocno (ira_allocno_t a)
2989 {
2990   ira_loop_tree_node_t parent;
2991
2992   if (ALLOCNO_CAP (a) != NULL)
2993     return NULL;
2994
2995   parent = ALLOCNO_LOOP_TREE_NODE (a)->parent;
2996   if (parent == NULL)
2997     return NULL;
2998
2999   return parent->regno_allocno_map[ALLOCNO_REGNO (a)];
3000 }
3001
3002 /* Find the allocno that corresponds to A at a level one higher up in the
3003    loop tree.  If ALLOCNO_CAP is set for A, return that.  */
3004 ira_allocno_t
3005 ira_parent_or_cap_allocno (ira_allocno_t a)
3006 {
3007   if (ALLOCNO_CAP (a) != NULL)
3008     return ALLOCNO_CAP (a);
3009
3010   return ira_parent_allocno (a);
3011 }
3012
3013 /* Process all allocnos originated from pseudo REGNO and copy live
3014    ranges, hard reg conflicts, and allocno stack reg attributes from
3015    low level allocnos to final allocnos which are destinations of
3016    removed stores at a loop exit.  Return true if we copied live
3017    ranges.  */
3018 static bool
3019 copy_info_to_removed_store_destinations (int regno)
3020 {
3021   ira_allocno_t a;
3022   ira_allocno_t parent_a = NULL;
3023   ira_loop_tree_node_t parent;
3024   bool merged_p;
3025
3026   merged_p = false;
3027   for (a = ira_regno_allocno_map[regno];
3028        a != NULL;
3029        a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
3030     {
3031       if (a != regno_top_level_allocno_map[REGNO (allocno_emit_reg (a))])
3032         /* This allocno will be removed.  */
3033         continue;
3034
3035       /* Caps will be removed.  */
3036       ira_assert (ALLOCNO_CAP_MEMBER (a) == NULL);
3037       for (parent = ALLOCNO_LOOP_TREE_NODE (a)->parent;
3038            parent != NULL;
3039            parent = parent->parent)
3040         if ((parent_a = parent->regno_allocno_map[regno]) == NULL
3041             || (parent_a
3042                 == regno_top_level_allocno_map[REGNO
3043                                                (allocno_emit_reg (parent_a))]
3044                 && ALLOCNO_EMIT_DATA (parent_a)->mem_optimized_dest_p))
3045           break;
3046       if (parent == NULL || parent_a == NULL)
3047         continue;
3048
3049       copy_allocno_live_ranges (a, parent_a);
3050       merge_hard_reg_conflicts (a, parent_a, true);
3051
3052       ALLOCNO_CALL_FREQ (parent_a) += ALLOCNO_CALL_FREQ (a);
3053       ALLOCNO_CALLS_CROSSED_NUM (parent_a)
3054         += ALLOCNO_CALLS_CROSSED_NUM (a);
3055       ALLOCNO_CHEAP_CALLS_CROSSED_NUM (parent_a)
3056         += ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a);
3057       ALLOCNO_CROSSED_CALLS_ABIS (parent_a)
3058         |= ALLOCNO_CROSSED_CALLS_ABIS (a);
3059       ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS (parent_a)
3060         |= ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS (a);
3061       ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (parent_a)
3062         += ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a);
3063       merged_p = true;
3064     }
3065   return merged_p;
3066 }
3067
3068 /* Flatten the IR.  In other words, this function transforms IR as if
3069    it were built with one region (without loops).  We could make it
3070    much simpler by rebuilding IR with one region, but unfortunately it
3071    takes a lot of time.  MAX_REGNO_BEFORE_EMIT and
3072    IRA_MAX_POINT_BEFORE_EMIT are correspondingly MAX_REG_NUM () and
3073    IRA_MAX_POINT before emitting insns on the loop borders.  */
3074 void
3075 ira_flattening (int max_regno_before_emit, int ira_max_point_before_emit)
3076 {
3077   int i, j;
3078   bool keep_p;
3079   int hard_regs_num;
3080   bool new_pseudos_p, merged_p, mem_dest_p;
3081   unsigned int n;
3082   enum reg_class aclass;
3083   ira_allocno_t a, parent_a, first, second, node_first, node_second;
3084   ira_copy_t cp;
3085   ira_loop_tree_node_t node;
3086   live_range_t r;
3087   ira_allocno_iterator ai;
3088   ira_copy_iterator ci;
3089
3090   regno_top_level_allocno_map
3091     = (ira_allocno_t *) ira_allocate (max_reg_num ()
3092                                       * sizeof (ira_allocno_t));
3093   memset (regno_top_level_allocno_map, 0,
3094           max_reg_num () * sizeof (ira_allocno_t));
3095   new_pseudos_p = merged_p = false;
3096   FOR_EACH_ALLOCNO (a, ai)
3097     {
3098       ira_allocno_object_iterator oi;
3099       ira_object_t obj;
3100
3101       if (ALLOCNO_CAP_MEMBER (a) != NULL)
3102         /* Caps are not in the regno allocno maps and they are never
3103            will be transformed into allocnos existing after IR
3104            flattening.  */
3105         continue;
3106       FOR_EACH_ALLOCNO_OBJECT (a, obj, oi)
3107         OBJECT_TOTAL_CONFLICT_HARD_REGS (obj)
3108           = OBJECT_CONFLICT_HARD_REGS (obj);
3109 #ifdef STACK_REGS
3110       ALLOCNO_TOTAL_NO_STACK_REG_P (a) = ALLOCNO_NO_STACK_REG_P (a);
3111 #endif
3112     }
3113   /* Fix final allocno attributes.  */
3114   for (i = max_regno_before_emit - 1; i >= FIRST_PSEUDO_REGISTER; i--)
3115     {
3116       mem_dest_p = false;
3117       for (a = ira_regno_allocno_map[i];
3118            a != NULL;
3119            a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
3120         {
3121           ira_emit_data_t parent_data, data = ALLOCNO_EMIT_DATA (a);
3122
3123           ira_assert (ALLOCNO_CAP_MEMBER (a) == NULL);
3124           if (data->somewhere_renamed_p)
3125             new_pseudos_p = true;
3126           parent_a = ira_parent_allocno (a);
3127           if (parent_a == NULL)
3128             {
3129               ALLOCNO_COPIES (a) = NULL;
3130               regno_top_level_allocno_map[REGNO (data->reg)] = a;
3131               continue;
3132             }
3133           ira_assert (ALLOCNO_CAP_MEMBER (parent_a) == NULL);
3134
3135           if (data->mem_optimized_dest != NULL)
3136             mem_dest_p = true;
3137           parent_data = ALLOCNO_EMIT_DATA (parent_a);
3138           if (REGNO (data->reg) == REGNO (parent_data->reg))
3139             {
3140               merge_hard_reg_conflicts (a, parent_a, true);
3141               move_allocno_live_ranges (a, parent_a);
3142               merged_p = true;
3143               parent_data->mem_optimized_dest_p
3144                 = (parent_data->mem_optimized_dest_p
3145                    || data->mem_optimized_dest_p);
3146               continue;
3147             }
3148           new_pseudos_p = true;
3149           for (;;)
3150             {
3151               ALLOCNO_NREFS (parent_a) -= ALLOCNO_NREFS (a);
3152               ALLOCNO_FREQ (parent_a) -= ALLOCNO_FREQ (a);
3153               ALLOCNO_CALL_FREQ (parent_a) -= ALLOCNO_CALL_FREQ (a);
3154               ALLOCNO_CALLS_CROSSED_NUM (parent_a)
3155                 -= ALLOCNO_CALLS_CROSSED_NUM (a);
3156               ALLOCNO_CHEAP_CALLS_CROSSED_NUM (parent_a)
3157                 -= ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a);
3158               /* Assume that ALLOCNO_CROSSED_CALLS_ABIS and
3159                  ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS stay the same.
3160                  We'd need to rebuild the IR to do better.  */
3161               ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (parent_a)
3162                 -= ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a);
3163               ira_assert (ALLOCNO_CALLS_CROSSED_NUM (parent_a) >= 0
3164                           && ALLOCNO_NREFS (parent_a) >= 0
3165                           && ALLOCNO_FREQ (parent_a) >= 0);
3166               aclass = ALLOCNO_CLASS (parent_a);
3167               hard_regs_num = ira_class_hard_regs_num[aclass];
3168               if (ALLOCNO_HARD_REG_COSTS (a) != NULL
3169                   && ALLOCNO_HARD_REG_COSTS (parent_a) != NULL)
3170                 for (j = 0; j < hard_regs_num; j++)
3171                   ALLOCNO_HARD_REG_COSTS (parent_a)[j]
3172                     -= ALLOCNO_HARD_REG_COSTS (a)[j];
3173               if (ALLOCNO_CONFLICT_HARD_REG_COSTS (a) != NULL
3174                   && ALLOCNO_CONFLICT_HARD_REG_COSTS (parent_a) != NULL)
3175                 for (j = 0; j < hard_regs_num; j++)
3176                   ALLOCNO_CONFLICT_HARD_REG_COSTS (parent_a)[j]
3177                     -= ALLOCNO_CONFLICT_HARD_REG_COSTS (a)[j];
3178               ALLOCNO_CLASS_COST (parent_a)
3179                 -= ALLOCNO_CLASS_COST (a);
3180               ALLOCNO_MEMORY_COST (parent_a) -= ALLOCNO_MEMORY_COST (a);
3181               parent_a = ira_parent_allocno (parent_a);
3182               if (parent_a == NULL)
3183                 break;
3184             }
3185           ALLOCNO_COPIES (a) = NULL;
3186           regno_top_level_allocno_map[REGNO (data->reg)] = a;
3187         }
3188       if (mem_dest_p && copy_info_to_removed_store_destinations (i))
3189         merged_p = true;
3190     }
3191   ira_assert (new_pseudos_p || ira_max_point_before_emit == ira_max_point);
3192   if (merged_p || ira_max_point_before_emit != ira_max_point)
3193     ira_rebuild_start_finish_chains ();
3194   if (new_pseudos_p)
3195     {
3196       sparseset objects_live;
3197
3198       /* Rebuild conflicts.  */
3199       FOR_EACH_ALLOCNO (a, ai)
3200         {
3201           ira_allocno_object_iterator oi;
3202           ira_object_t obj;
3203
3204           if (a != regno_top_level_allocno_map[REGNO (allocno_emit_reg (a))]
3205               || ALLOCNO_CAP_MEMBER (a) != NULL)
3206             continue;
3207           FOR_EACH_ALLOCNO_OBJECT (a, obj, oi)
3208             {
3209               for (r = OBJECT_LIVE_RANGES (obj); r != NULL; r = r->next)
3210                 ira_assert (r->object == obj);
3211               clear_conflicts (obj);
3212             }
3213         }
3214       objects_live = sparseset_alloc (ira_objects_num);
3215       for (i = 0; i < ira_max_point; i++)
3216         {
3217           for (r = ira_start_point_ranges[i]; r != NULL; r = r->start_next)
3218             {
3219               ira_object_t obj = r->object;
3220
3221               a = OBJECT_ALLOCNO (obj);
3222               if (a != regno_top_level_allocno_map[REGNO (allocno_emit_reg (a))]
3223                   || ALLOCNO_CAP_MEMBER (a) != NULL)
3224                 continue;
3225
3226               aclass = ALLOCNO_CLASS (a);
3227               EXECUTE_IF_SET_IN_SPARSESET (objects_live, n)
3228                 {
3229                   ira_object_t live_obj = ira_object_id_map[n];
3230                   ira_allocno_t live_a = OBJECT_ALLOCNO (live_obj);
3231                   enum reg_class live_aclass = ALLOCNO_CLASS (live_a);
3232
3233                   if (ira_reg_classes_intersect_p[aclass][live_aclass]
3234                       /* Don't set up conflict for the allocno with itself.  */
3235                       && live_a != a)
3236                     ira_add_conflict (obj, live_obj);
3237                 }
3238               sparseset_set_bit (objects_live, OBJECT_CONFLICT_ID (obj));
3239             }
3240
3241           for (r = ira_finish_point_ranges[i]; r != NULL; r = r->finish_next)
3242             sparseset_clear_bit (objects_live, OBJECT_CONFLICT_ID (r->object));
3243         }
3244       sparseset_free (objects_live);
3245       compress_conflict_vecs ();
3246     }
3247   /* Mark some copies for removing and change allocnos in the rest
3248      copies.  */
3249   FOR_EACH_COPY (cp, ci)
3250     {
3251       if (ALLOCNO_CAP_MEMBER (cp->first) != NULL
3252           || ALLOCNO_CAP_MEMBER (cp->second) != NULL)
3253         {
3254           if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL)
3255             fprintf
3256               (ira_dump_file, "      Remove cp%d:%c%dr%d-%c%dr%d\n",
3257                cp->num, ALLOCNO_CAP_MEMBER (cp->first) != NULL ? 'c' : 'a',
3258                ALLOCNO_NUM (cp->first),
3259                REGNO (allocno_emit_reg (cp->first)),
3260                ALLOCNO_CAP_MEMBER (cp->second) != NULL ? 'c' : 'a',
3261                ALLOCNO_NUM (cp->second),
3262                REGNO (allocno_emit_reg (cp->second)));
3263           cp->loop_tree_node = NULL;
3264           continue;
3265         }
3266       first
3267         = regno_top_level_allocno_map[REGNO (allocno_emit_reg (cp->first))];
3268       second
3269         = regno_top_level_allocno_map[REGNO (allocno_emit_reg (cp->second))];
3270       node = cp->loop_tree_node;
3271       if (node == NULL)
3272         keep_p = true; /* It copy generated in ira-emit.c.  */
3273       else
3274         {
3275           /* Check that the copy was not propagated from level on
3276              which we will have different pseudos.  */
3277           node_first = node->regno_allocno_map[ALLOCNO_REGNO (cp->first)];
3278           node_second = node->regno_allocno_map[ALLOCNO_REGNO (cp->second)];
3279           keep_p = ((REGNO (allocno_emit_reg (first))
3280                      == REGNO (allocno_emit_reg (node_first)))
3281                      && (REGNO (allocno_emit_reg (second))
3282                          == REGNO (allocno_emit_reg (node_second))));
3283         }
3284       if (keep_p)
3285         {
3286           cp->loop_tree_node = ira_loop_tree_root;
3287           cp->first = first;
3288           cp->second = second;
3289         }
3290       else
3291         {
3292           cp->loop_tree_node = NULL;
3293           if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL)
3294             fprintf (ira_dump_file, "      Remove cp%d:a%dr%d-a%dr%d\n",
3295                      cp->num, ALLOCNO_NUM (cp->first),
3296                      REGNO (allocno_emit_reg (cp->first)),
3297                      ALLOCNO_NUM (cp->second),
3298                      REGNO (allocno_emit_reg (cp->second)));
3299         }
3300     }
3301   /* Remove unnecessary allocnos on lower levels of the loop tree.  */
3302   FOR_EACH_ALLOCNO (a, ai)
3303     {
3304       if (a != regno_top_level_allocno_map[REGNO (allocno_emit_reg (a))]
3305           || ALLOCNO_CAP_MEMBER (a) != NULL)
3306         {
3307           if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL)
3308             fprintf (ira_dump_file, "      Remove a%dr%d\n",
3309                      ALLOCNO_NUM (a), REGNO (allocno_emit_reg (a)));
3310           ira_remove_allocno_prefs (a);
3311           finish_allocno (a);
3312           continue;
3313         }
3314       ALLOCNO_LOOP_TREE_NODE (a) = ira_loop_tree_root;
3315       ALLOCNO_REGNO (a) = REGNO (allocno_emit_reg (a));
3316       ALLOCNO_CAP (a) = NULL;
3317       /* Restore updated costs for assignments from reload.  */
3318       ALLOCNO_UPDATED_MEMORY_COST (a) = ALLOCNO_MEMORY_COST (a);
3319       ALLOCNO_UPDATED_CLASS_COST (a) = ALLOCNO_CLASS_COST (a);
3320       if (! ALLOCNO_ASSIGNED_P (a))
3321         ira_free_allocno_updated_costs (a);
3322       ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL);
3323       ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) == NULL);
3324     }
3325   /* Remove unnecessary copies.  */
3326   FOR_EACH_COPY (cp, ci)
3327     {
3328       if (cp->loop_tree_node == NULL)
3329         {
3330           ira_copies[cp->num] = NULL;
3331           finish_copy (cp);
3332           continue;
3333         }
3334       ira_assert
3335         (ALLOCNO_LOOP_TREE_NODE (cp->first) == ira_loop_tree_root
3336          && ALLOCNO_LOOP_TREE_NODE (cp->second) == ira_loop_tree_root);
3337       add_allocno_copy_to_list (cp);
3338       swap_allocno_copy_ends_if_necessary (cp);
3339     }
3340   rebuild_regno_allocno_maps ();
3341   if (ira_max_point != ira_max_point_before_emit)
3342     ira_compress_allocno_live_ranges ();
3343   ira_free (regno_top_level_allocno_map);
3344 }
3345
3346 \f
3347
3348 #ifdef ENABLE_IRA_CHECKING
3349 /* Check creation of all allocnos.  Allocnos on lower levels should
3350    have allocnos or caps on all upper levels.  */
3351 static void
3352 check_allocno_creation (void)
3353 {
3354   ira_allocno_t a;
3355   ira_allocno_iterator ai;
3356   ira_loop_tree_node_t loop_tree_node;
3357
3358   FOR_EACH_ALLOCNO (a, ai)
3359     {
3360       loop_tree_node = ALLOCNO_LOOP_TREE_NODE (a);
3361       ira_assert (bitmap_bit_p (loop_tree_node->all_allocnos,
3362                                 ALLOCNO_NUM (a)));
3363       if (loop_tree_node == ira_loop_tree_root)
3364         continue;
3365       if (ALLOCNO_CAP_MEMBER (a) != NULL)
3366         ira_assert (ALLOCNO_CAP (a) != NULL);
3367       else if (ALLOCNO_CAP (a) == NULL)
3368         ira_assert (loop_tree_node->parent
3369                     ->regno_allocno_map[ALLOCNO_REGNO (a)] != NULL
3370                     && bitmap_bit_p (loop_tree_node->border_allocnos,
3371                                      ALLOCNO_NUM (a)));
3372     }
3373 }
3374 #endif
3375
3376 /* Identify allocnos which prefer a register class with a single hard register.
3377    Adjust ALLOCNO_CONFLICT_HARD_REG_COSTS so that conflicting allocnos are
3378    less likely to use the preferred singleton register.  */
3379 static void
3380 update_conflict_hard_reg_costs (void)
3381 {
3382   ira_allocno_t a;
3383   ira_allocno_iterator ai;
3384   int i, index, min;
3385
3386   FOR_EACH_ALLOCNO (a, ai)
3387     {
3388       reg_class_t aclass = ALLOCNO_CLASS (a);
3389       reg_class_t pref = reg_preferred_class (ALLOCNO_REGNO (a));
3390       int singleton = ira_class_singleton[pref][ALLOCNO_MODE (a)];
3391       if (singleton < 0)
3392         continue;
3393       index = ira_class_hard_reg_index[(int) aclass][singleton];
3394       if (index < 0)
3395         continue;
3396       if (ALLOCNO_CONFLICT_HARD_REG_COSTS (a) == NULL
3397           || ALLOCNO_HARD_REG_COSTS (a) == NULL)
3398         continue;
3399       min = INT_MAX;
3400       for (i = ira_class_hard_regs_num[(int) aclass] - 1; i >= 0; i--)
3401         if (ALLOCNO_HARD_REG_COSTS (a)[i] > ALLOCNO_CLASS_COST (a)
3402             && min > ALLOCNO_HARD_REG_COSTS (a)[i])
3403           min = ALLOCNO_HARD_REG_COSTS (a)[i];
3404       if (min == INT_MAX)
3405         continue;
3406       ira_allocate_and_set_costs (&ALLOCNO_CONFLICT_HARD_REG_COSTS (a),
3407                                   aclass, 0);
3408       ALLOCNO_CONFLICT_HARD_REG_COSTS (a)[index]
3409         -= min - ALLOCNO_CLASS_COST (a);
3410     }
3411 }
3412
3413 /* Create a internal representation (IR) for IRA (allocnos, copies,
3414    loop tree nodes).  The function returns TRUE if we generate loop
3415    structure (besides nodes representing all function and the basic
3416    blocks) for regional allocation.  A true return means that we
3417    really need to flatten IR before the reload.  */
3418 bool
3419 ira_build (void)
3420 {
3421   bool loops_p;
3422
3423   df_analyze ();
3424   initiate_cost_vectors ();
3425   initiate_allocnos ();
3426   initiate_prefs ();
3427   initiate_copies ();
3428   create_loop_tree_nodes ();
3429   form_loop_tree ();
3430   create_allocnos ();
3431   ira_costs ();
3432   create_allocno_objects ();
3433   ira_create_allocno_live_ranges ();
3434   remove_unnecessary_regions (false);
3435   ira_compress_allocno_live_ranges ();
3436   update_bad_spill_attribute ();
3437   loops_p = more_one_region_p ();
3438   if (loops_p)
3439     {
3440       propagate_allocno_info ();
3441       create_caps ();
3442     }
3443   ira_tune_allocno_costs ();
3444 #ifdef ENABLE_IRA_CHECKING
3445   check_allocno_creation ();
3446 #endif
3447   setup_min_max_allocno_live_range_point ();
3448   sort_conflict_id_map ();
3449   setup_min_max_conflict_allocno_ids ();
3450   ira_build_conflicts ();
3451   update_conflict_hard_reg_costs ();
3452   if (! ira_conflicts_p)
3453     {
3454       ira_allocno_t a;
3455       ira_allocno_iterator ai;
3456
3457       /* Remove all regions but root one.  */
3458       if (loops_p)
3459         {
3460           remove_unnecessary_regions (true);
3461           loops_p = false;
3462         }
3463       /* We don't save hard registers around calls for fast allocation
3464          -- add caller clobbered registers as conflicting ones to
3465          allocno crossing calls.  */
3466       FOR_EACH_ALLOCNO (a, ai)
3467         if (ALLOCNO_CALLS_CROSSED_NUM (a) != 0)
3468           ior_hard_reg_conflicts (a, ira_need_caller_save_regs (a));
3469     }
3470   if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
3471     print_copies (ira_dump_file);
3472   if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
3473     print_prefs (ira_dump_file);
3474   if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
3475     {
3476       int n, nr, nr_big;
3477       ira_allocno_t a;
3478       live_range_t r;
3479       ira_allocno_iterator ai;
3480
3481       n = 0;
3482       nr = 0;
3483       nr_big = 0;
3484       FOR_EACH_ALLOCNO (a, ai)
3485         {
3486           int j, nobj = ALLOCNO_NUM_OBJECTS (a);
3487
3488           if (nobj > 1)
3489             nr_big++;
3490           for (j = 0; j < nobj; j++)
3491             {
3492               ira_object_t obj = ALLOCNO_OBJECT (a, j);
3493               n += OBJECT_NUM_CONFLICTS (obj);
3494               for (r = OBJECT_LIVE_RANGES (obj); r != NULL; r = r->next)
3495                 nr++;
3496             }
3497         }
3498       fprintf (ira_dump_file, "  regions=%d, blocks=%d, points=%d\n",
3499                current_loops == NULL ? 1 : number_of_loops (cfun),
3500                n_basic_blocks_for_fn (cfun), ira_max_point);
3501       fprintf (ira_dump_file,
3502                "    allocnos=%d (big %d), copies=%d, conflicts=%d, ranges=%d\n",
3503                ira_allocnos_num, nr_big, ira_copies_num, n, nr);
3504     }
3505   return loops_p;
3506 }
3507
3508 /* Release the data created by function ira_build.  */
3509 void
3510 ira_destroy (void)
3511 {
3512   finish_loop_tree_nodes ();
3513   finish_prefs ();
3514   finish_copies ();
3515   finish_allocnos ();
3516   finish_cost_vectors ();
3517   ira_finish_allocno_live_ranges ();
3518 }