gcc/ira-build.c

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