gcc/ira-build.cc

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