gcc/ira-build.c

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