gcc-4_9-branch/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 #ifdef STACK_REGS
 519   ALLOCNO_NO_STACK_REG_P (a) = false;
 520   ALLOCNO_TOTAL_NO_STACK_REG_P (a) = false;
 521 #endif
 522   ALLOCNO_DONT_REASSIGN_P (a) = false;
 523   ALLOCNO_BAD_SPILL_P (a) = false;
 524   ALLOCNO_ASSIGNED_P (a) = false;
 525   ALLOCNO_MODE (a) = (regno < 0 ? VOIDmode : PSEUDO_REGNO_MODE (regno));
 526   ALLOCNO_WMODE (a) = ALLOCNO_MODE (a);
 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   ALLOCNO_WMODE (cap) = ALLOCNO_WMODE (a);
 897   aclass = ALLOCNO_CLASS (a);
 898   ira_set_allocno_class (cap, aclass);
 899   ira_create_allocno_objects (cap);
 900   ALLOCNO_CAP_MEMBER (cap) = a;
 901   ALLOCNO_CAP (a) = cap;
 902   ALLOCNO_CLASS_COST (cap) = ALLOCNO_CLASS_COST (a);
 903   ALLOCNO_MEMORY_COST (cap) = ALLOCNO_MEMORY_COST (a);
 904   ira_allocate_and_copy_costs
 905     (&ALLOCNO_HARD_REG_COSTS (cap), aclass, ALLOCNO_HARD_REG_COSTS (a));
 906   ira_allocate_and_copy_costs
 907     (&ALLOCNO_CONFLICT_HARD_REG_COSTS (cap), aclass,
 908      ALLOCNO_CONFLICT_HARD_REG_COSTS (a));
 909   ALLOCNO_BAD_SPILL_P (cap) = ALLOCNO_BAD_SPILL_P (a);
 910   ALLOCNO_NREFS (cap) = ALLOCNO_NREFS (a);
 911   ALLOCNO_FREQ (cap) = ALLOCNO_FREQ (a);
 912   ALLOCNO_CALL_FREQ (cap) = ALLOCNO_CALL_FREQ (a);
 913
 914   merge_hard_reg_conflicts (a, cap, false);
 915
 916   ALLOCNO_CALLS_CROSSED_NUM (cap) = ALLOCNO_CALLS_CROSSED_NUM (a);
 917   ALLOCNO_CHEAP_CALLS_CROSSED_NUM (cap) = ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a);
 918   if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
 919     {
 920       fprintf (ira_dump_file, "    Creating cap ");
 921       ira_print_expanded_allocno (cap);
 922       fprintf (ira_dump_file, "\n");
 923     }
 924   return cap;
 925 }
 926
 927 /* Create and return a live range for OBJECT with given attributes.  */
 928 live_range_t
 929 ira_create_live_range (ira_object_t obj, int start, int finish,
 930                        live_range_t next)
 931 {
 932   live_range_t p;
 933
 934   p = (live_range_t) pool_alloc (live_range_pool);
 935   p->object = obj;
 936   p->start = start;
 937   p->finish = finish;
 938   p->next = next;
 939   return p;
 940 }
 941
 942 /* Create a new live range for OBJECT and queue it at the head of its
 943    live range list.  */
 944 void
 945 ira_add_live_range_to_object (ira_object_t object, int start, int finish)
 946 {
 947   live_range_t p;
 948   p = ira_create_live_range (object, start, finish,
 949                              OBJECT_LIVE_RANGES (object));
 950   OBJECT_LIVE_RANGES (object) = p;
 951 }
 952
 953 /* Copy allocno live range R and return the result.  */
 954 static live_range_t
 955 copy_live_range (live_range_t r)
 956 {
 957   live_range_t p;
 958
 959   p = (live_range_t) pool_alloc (live_range_pool);
 960   *p = *r;
 961   return p;
 962 }
 963
 964 /* Copy allocno live range list given by its head R and return the
 965    result.  */
 966 live_range_t
 967 ira_copy_live_range_list (live_range_t r)
 968 {
 969   live_range_t p, first, last;
 970
 971   if (r == NULL)
 972     return NULL;
 973   for (first = last = NULL; r != NULL; r = r->next)
 974     {
 975       p = copy_live_range (r);
 976       if (first == NULL)
 977         first = p;
 978       else
 979         last->next = p;
 980       last = p;
 981     }
 982   return first;
 983 }
 984
 985 /* Merge ranges R1 and R2 and returns the result.  The function
 986    maintains the order of ranges and tries to minimize number of the
 987    result ranges.  */
 988 live_range_t
 989 ira_merge_live_ranges (live_range_t r1, live_range_t r2)
 990 {
 991   live_range_t first, last, temp;
 992
 993   if (r1 == NULL)
 994     return r2;
 995   if (r2 == NULL)
 996     return r1;
 997   for (first = last = NULL; r1 != NULL && r2 != NULL;)
 998     {
 999       if (r1->start < r2->start)
1000         {
1001           temp = r1;
1002           r1 = r2;
1003           r2 = temp;
1004         }
1005       if (r1->start <= r2->finish + 1)
1006         {
1007           /* Intersected ranges: merge r1 and r2 into r1.  */
1008           r1->start = r2->start;
1009           if (r1->finish < r2->finish)
1010             r1->finish = r2->finish;
1011           temp = r2;
1012           r2 = r2->next;
1013           ira_finish_live_range (temp);
1014           if (r2 == NULL)
1015             {
1016               /* To try to merge with subsequent ranges in r1.  */
1017               r2 = r1->next;
1018               r1->next = NULL;
1019             }
1020         }
1021       else
1022         {
1023           /* Add r1 to the result.  */
1024           if (first == NULL)
1025             first = last = r1;
1026           else
1027             {
1028               last->next = r1;
1029               last = r1;
1030             }
1031           r1 = r1->next;
1032           if (r1 == NULL)
1033             {
1034               /* To try to merge with subsequent ranges in r2.  */
1035               r1 = r2->next;
1036               r2->next = NULL;
1037             }
1038         }
1039     }
1040   if (r1 != NULL)
1041     {
1042       if (first == NULL)
1043         first = r1;
1044       else
1045         last->next = r1;
1046       ira_assert (r1->next == NULL);
1047     }
1048   else if (r2 != NULL)
1049     {
1050       if (first == NULL)
1051         first = r2;
1052       else
1053         last->next = r2;
1054       ira_assert (r2->next == NULL);
1055     }
1056   else
1057     {
1058       ira_assert (last->next == NULL);
1059     }
1060   return first;
1061 }
1062
1063 /* Return TRUE if live ranges R1 and R2 intersect.  */
1064 bool
1065 ira_live_ranges_intersect_p (live_range_t r1, live_range_t r2)
1066 {
1067   /* Remember the live ranges are always kept ordered.  */
1068   while (r1 != NULL && r2 != NULL)
1069     {
1070       if (r1->start > r2->finish)
1071         r1 = r1->next;
1072       else if (r2->start > r1->finish)
1073         r2 = r2->next;
1074       else
1075         return true;
1076     }
1077   return false;
1078 }
1079
1080 /* Free allocno live range R.  */
1081 void
1082 ira_finish_live_range (live_range_t r)
1083 {
1084   pool_free (live_range_pool, r);
1085 }
1086
1087 /* Free list of allocno live ranges starting with R.  */
1088 void
1089 ira_finish_live_range_list (live_range_t r)
1090 {
1091   live_range_t next_r;
1092
1093   for (; r != NULL; r = next_r)
1094     {
1095       next_r = r->next;
1096       ira_finish_live_range (r);
1097     }
1098 }
1099
1100 /* Free updated register costs of allocno A.  */
1101 void
1102 ira_free_allocno_updated_costs (ira_allocno_t a)
1103 {
1104   enum reg_class aclass;
1105
1106   aclass = ALLOCNO_CLASS (a);
1107   if (ALLOCNO_UPDATED_HARD_REG_COSTS (a) != NULL)
1108     ira_free_cost_vector (ALLOCNO_UPDATED_HARD_REG_COSTS (a), aclass);
1109   ALLOCNO_UPDATED_HARD_REG_COSTS (a) = NULL;
1110   if (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) != NULL)
1111     ira_free_cost_vector (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a),
1112                           aclass);
1113   ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) = NULL;
1114 }
1115
1116 /* Free and nullify all cost vectors allocated earlier for allocno
1117    A.  */
1118 static void
1119 ira_free_allocno_costs (ira_allocno_t a)
1120 {
1121   enum reg_class aclass = ALLOCNO_CLASS (a);
1122   ira_object_t obj;
1123   ira_allocno_object_iterator oi;
1124
1125   FOR_EACH_ALLOCNO_OBJECT (a, obj, oi)
1126     {
1127       ira_finish_live_range_list (OBJECT_LIVE_RANGES (obj));
1128       ira_object_id_map[OBJECT_CONFLICT_ID (obj)] = NULL;
1129       if (OBJECT_CONFLICT_ARRAY (obj) != NULL)
1130         ira_free (OBJECT_CONFLICT_ARRAY (obj));
1131       pool_free (object_pool, obj);
1132     }
1133
1134   ira_allocnos[ALLOCNO_NUM (a)] = NULL;
1135   if (ALLOCNO_HARD_REG_COSTS (a) != NULL)
1136     ira_free_cost_vector (ALLOCNO_HARD_REG_COSTS (a), aclass);
1137   if (ALLOCNO_CONFLICT_HARD_REG_COSTS (a) != NULL)
1138     ira_free_cost_vector (ALLOCNO_CONFLICT_HARD_REG_COSTS (a), aclass);
1139   if (ALLOCNO_UPDATED_HARD_REG_COSTS (a) != NULL)
1140     ira_free_cost_vector (ALLOCNO_UPDATED_HARD_REG_COSTS (a), aclass);
1141   if (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) != NULL)
1142     ira_free_cost_vector (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a),
1143                           aclass);
1144   ALLOCNO_HARD_REG_COSTS (a) = NULL;
1145   ALLOCNO_CONFLICT_HARD_REG_COSTS (a) = NULL;
1146   ALLOCNO_UPDATED_HARD_REG_COSTS (a) = NULL;
1147   ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) = NULL;
1148 }
1149
1150 /* Free the memory allocated for allocno A.  */
1151 static void
1152 finish_allocno (ira_allocno_t a)
1153 {
1154   ira_free_allocno_costs (a);
1155   pool_free (allocno_pool, a);
1156 }
1157
1158 /* Free the memory allocated for all allocnos.  */
1159 static void
1160 finish_allocnos (void)
1161 {
1162   ira_allocno_t a;
1163   ira_allocno_iterator ai;
1164
1165   FOR_EACH_ALLOCNO (a, ai)
1166     finish_allocno (a);
1167   ira_free (ira_regno_allocno_map);
1168   ira_object_id_map_vec.release ();
1169   allocno_vec.release ();
1170   free_alloc_pool (allocno_pool);
1171   free_alloc_pool (object_pool);
1172   free_alloc_pool (live_range_pool);
1173 }
1174
1175 \f
1176
1177 /* Pools for allocno preferences.  */
1178 static alloc_pool pref_pool;
1179
1180 /* Vec containing references to all created preferences.  It is a
1181    container of array ira_prefs.  */
1182 static vec<ira_pref_t> pref_vec;
1183
1184 /* The function initializes data concerning allocno prefs.  */
1185 static void
1186 initiate_prefs (void)
1187 {
1188   pref_pool
1189     = create_alloc_pool ("prefs", sizeof (struct ira_allocno_pref), 100);
1190   pref_vec.create (get_max_uid ());
1191   ira_prefs = NULL;
1192   ira_prefs_num = 0;
1193 }
1194
1195 /* Return pref for A and HARD_REGNO if any.  */
1196 static ira_pref_t
1197 find_allocno_pref (ira_allocno_t a, int hard_regno)
1198 {
1199   ira_pref_t pref;
1200
1201   for (pref = ALLOCNO_PREFS (a); pref != NULL; pref = pref->next_pref)
1202     if (pref->allocno == a && pref->hard_regno == hard_regno)
1203       return pref;
1204   return NULL;
1205 }
1206
1207 /* Create and return pref with given attributes A, HARD_REGNO, and FREQ.  */
1208 ira_pref_t
1209 ira_create_pref (ira_allocno_t a, int hard_regno, int freq)
1210 {
1211   ira_pref_t pref;
1212
1213   pref = (ira_pref_t) pool_alloc (pref_pool);
1214   pref->num = ira_prefs_num;
1215   pref->allocno = a;
1216   pref->hard_regno = hard_regno;
1217   pref->freq = freq;
1218   pref_vec.safe_push (pref);
1219   ira_prefs = pref_vec.address ();
1220   ira_prefs_num = pref_vec.length ();
1221   return pref;
1222 }
1223
1224 /* Attach a pref PREF to the cooresponding allocno.  */
1225 static void
1226 add_allocno_pref_to_list (ira_pref_t pref)
1227 {
1228   ira_allocno_t a = pref->allocno;
1229
1230   pref->next_pref = ALLOCNO_PREFS (a);
1231   ALLOCNO_PREFS (a) = pref;
1232 }
1233
1234 /* Create (or update frequency if the pref already exists) the pref of
1235    allocnos A preferring HARD_REGNO with frequency FREQ.  */
1236 void
1237 ira_add_allocno_pref (ira_allocno_t a, int hard_regno, int freq)
1238 {
1239   ira_pref_t pref;
1240
1241   if (freq <= 0)
1242     return;
1243   if ((pref = find_allocno_pref (a, hard_regno)) != NULL)
1244     {
1245       pref->freq += freq;
1246       return;
1247     }
1248   pref = ira_create_pref (a, hard_regno, freq);
1249   ira_assert (a != NULL);
1250   add_allocno_pref_to_list (pref);
1251 }
1252
1253 /* Print info about PREF into file F.  */
1254 static void
1255 print_pref (FILE *f, ira_pref_t pref)
1256 {
1257   fprintf (f, "  pref%d:a%d(r%d)<-hr%d@%d\n", pref->num,
1258            ALLOCNO_NUM (pref->allocno), ALLOCNO_REGNO (pref->allocno),
1259            pref->hard_regno, pref->freq);
1260 }
1261
1262 /* Print info about PREF into stderr.  */
1263 void
1264 ira_debug_pref (ira_pref_t pref)
1265 {
1266   print_pref (stderr, pref);
1267 }
1268
1269 /* Print info about all prefs into file F.  */
1270 static void
1271 print_prefs (FILE *f)
1272 {
1273   ira_pref_t pref;
1274   ira_pref_iterator pi;
1275
1276   FOR_EACH_PREF (pref, pi)
1277     print_pref (f, pref);
1278 }
1279
1280 /* Print info about all prefs into stderr.  */
1281 void
1282 ira_debug_prefs (void)
1283 {
1284   print_prefs (stderr);
1285 }
1286
1287 /* Print info about prefs involving allocno A into file F.  */
1288 static void
1289 print_allocno_prefs (FILE *f, ira_allocno_t a)
1290 {
1291   ira_pref_t pref;
1292
1293   fprintf (f, " a%d(r%d):", ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
1294   for (pref = ALLOCNO_PREFS (a); pref != NULL; pref = pref->next_pref)
1295     fprintf (f, " pref%d:hr%d@%d", pref->num, pref->hard_regno, pref->freq);
1296   fprintf (f, "\n");
1297 }
1298
1299 /* Print info about prefs involving allocno A into stderr.  */
1300 void
1301 ira_debug_allocno_prefs (ira_allocno_t a)
1302 {
1303   print_allocno_prefs (stderr, a);
1304 }
1305
1306 /* The function frees memory allocated for PREF.  */
1307 static void
1308 finish_pref (ira_pref_t pref)
1309 {
1310   ira_prefs[pref->num] = NULL;
1311   pool_free (pref_pool, pref);
1312 }
1313
1314 /* Remove PREF from the list of allocno prefs and free memory for
1315    it.  */
1316 void
1317 ira_remove_pref (ira_pref_t pref)
1318 {
1319   ira_pref_t cpref, prev;
1320
1321   if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
1322     fprintf (ira_dump_file, " Removing pref%d:hr%d@%d\n",
1323              pref->num, pref->hard_regno, pref->freq);
1324   for (prev = NULL, cpref = ALLOCNO_PREFS (pref->allocno);
1325        cpref != NULL;
1326        prev = cpref, cpref = cpref->next_pref)
1327     if (cpref == pref)
1328       break;
1329   ira_assert (cpref != NULL);
1330   if (prev == NULL)
1331     ALLOCNO_PREFS (pref->allocno) = pref->next_pref;
1332   else
1333     prev->next_pref = pref->next_pref;
1334   finish_pref (pref);
1335 }
1336
1337 /* Remove all prefs of allocno A.  */
1338 void
1339 ira_remove_allocno_prefs (ira_allocno_t a)
1340 {
1341   ira_pref_t pref, next_pref;
1342
1343   for (pref = ALLOCNO_PREFS (a); pref != NULL; pref = next_pref)
1344     {
1345       next_pref = pref->next_pref;
1346       finish_pref (pref);
1347     }
1348   ALLOCNO_PREFS (a) = NULL;
1349 }
1350
1351 /* Free memory allocated for all prefs.  */
1352 static void
1353 finish_prefs (void)
1354 {
1355   ira_pref_t pref;
1356   ira_pref_iterator pi;
1357
1358   FOR_EACH_PREF (pref, pi)
1359     finish_pref (pref);
1360   pref_vec.release ();
1361   free_alloc_pool (pref_pool);
1362 }
1363
1364 \f
1365
1366 /* Pools for copies.  */
1367 static alloc_pool copy_pool;
1368
1369 /* Vec containing references to all created copies.  It is a
1370    container of array ira_copies.  */
1371 static vec<ira_copy_t> copy_vec;
1372
1373 /* The function initializes data concerning allocno copies.  */
1374 static void
1375 initiate_copies (void)
1376 {
1377   copy_pool
1378     = create_alloc_pool ("copies", sizeof (struct ira_allocno_copy), 100);
1379   copy_vec.create (get_max_uid ());
1380   ira_copies = NULL;
1381   ira_copies_num = 0;
1382 }
1383
1384 /* Return copy connecting A1 and A2 and originated from INSN of
1385    LOOP_TREE_NODE if any.  */
1386 static ira_copy_t
1387 find_allocno_copy (ira_allocno_t a1, ira_allocno_t a2, rtx insn,
1388                    ira_loop_tree_node_t loop_tree_node)
1389 {
1390   ira_copy_t cp, next_cp;
1391   ira_allocno_t another_a;
1392
1393   for (cp = ALLOCNO_COPIES (a1); cp != NULL; cp = next_cp)
1394     {
1395       if (cp->first == a1)
1396         {
1397           next_cp = cp->next_first_allocno_copy;
1398           another_a = cp->second;
1399         }
1400       else if (cp->second == a1)
1401         {
1402           next_cp = cp->next_second_allocno_copy;
1403           another_a = cp->first;
1404         }
1405       else
1406         gcc_unreachable ();
1407       if (another_a == a2 && cp->insn == insn
1408           && cp->loop_tree_node == loop_tree_node)
1409         return cp;
1410     }
1411   return NULL;
1412 }
1413
1414 /* Create and return copy with given attributes LOOP_TREE_NODE, FIRST,
1415    SECOND, FREQ, CONSTRAINT_P, and INSN.  */
1416 ira_copy_t
1417 ira_create_copy (ira_allocno_t first, ira_allocno_t second, int freq,
1418                  bool constraint_p, rtx insn,
1419                  ira_loop_tree_node_t loop_tree_node)
1420 {
1421   ira_copy_t cp;
1422
1423   cp = (ira_copy_t) pool_alloc (copy_pool);
1424   cp->num = ira_copies_num;
1425   cp->first = first;
1426   cp->second = second;
1427   cp->freq = freq;
1428   cp->constraint_p = constraint_p;
1429   cp->insn = insn;
1430   cp->loop_tree_node = loop_tree_node;
1431   copy_vec.safe_push (cp);
1432   ira_copies = copy_vec.address ();
1433   ira_copies_num = copy_vec.length ();
1434   return cp;
1435 }
1436
1437 /* Attach a copy CP to allocnos involved into the copy.  */
1438 static void
1439 add_allocno_copy_to_list (ira_copy_t cp)
1440 {
1441   ira_allocno_t first = cp->first, second = cp->second;
1442
1443   cp->prev_first_allocno_copy = NULL;
1444   cp->prev_second_allocno_copy = NULL;
1445   cp->next_first_allocno_copy = ALLOCNO_COPIES (first);
1446   if (cp->next_first_allocno_copy != NULL)
1447     {
1448       if (cp->next_first_allocno_copy->first == first)
1449         cp->next_first_allocno_copy->prev_first_allocno_copy = cp;
1450       else
1451         cp->next_first_allocno_copy->prev_second_allocno_copy = cp;
1452     }
1453   cp->next_second_allocno_copy = ALLOCNO_COPIES (second);
1454   if (cp->next_second_allocno_copy != NULL)
1455     {
1456       if (cp->next_second_allocno_copy->second == second)
1457         cp->next_second_allocno_copy->prev_second_allocno_copy = cp;
1458       else
1459         cp->next_second_allocno_copy->prev_first_allocno_copy = cp;
1460     }
1461   ALLOCNO_COPIES (first) = cp;
1462   ALLOCNO_COPIES (second) = cp;
1463 }
1464
1465 /* Make a copy CP a canonical copy where number of the
1466    first allocno is less than the second one.  */
1467 static void
1468 swap_allocno_copy_ends_if_necessary (ira_copy_t cp)
1469 {
1470   ira_allocno_t temp;
1471   ira_copy_t temp_cp;
1472
1473   if (ALLOCNO_NUM (cp->first) <= ALLOCNO_NUM (cp->second))
1474     return;
1475
1476   temp = cp->first;
1477   cp->first = cp->second;
1478   cp->second = temp;
1479
1480   temp_cp = cp->prev_first_allocno_copy;
1481   cp->prev_first_allocno_copy = cp->prev_second_allocno_copy;
1482   cp->prev_second_allocno_copy = temp_cp;
1483
1484   temp_cp = cp->next_first_allocno_copy;
1485   cp->next_first_allocno_copy = cp->next_second_allocno_copy;
1486   cp->next_second_allocno_copy = temp_cp;
1487 }
1488
1489 /* Create (or update frequency if the copy already exists) and return
1490    the copy of allocnos FIRST and SECOND with frequency FREQ
1491    corresponding to move insn INSN (if any) and originated from
1492    LOOP_TREE_NODE.  */
1493 ira_copy_t
1494 ira_add_allocno_copy (ira_allocno_t first, ira_allocno_t second, int freq,
1495                       bool constraint_p, rtx insn,
1496                       ira_loop_tree_node_t loop_tree_node)
1497 {
1498   ira_copy_t cp;
1499
1500   if ((cp = find_allocno_copy (first, second, insn, loop_tree_node)) != NULL)
1501     {
1502       cp->freq += freq;
1503       return cp;
1504     }
1505   cp = ira_create_copy (first, second, freq, constraint_p, insn,
1506                         loop_tree_node);
1507   ira_assert (first != NULL && second != NULL);
1508   add_allocno_copy_to_list (cp);
1509   swap_allocno_copy_ends_if_necessary (cp);
1510   return cp;
1511 }
1512
1513 /* Print info about copy CP into file F.  */
1514 static void
1515 print_copy (FILE *f, ira_copy_t cp)
1516 {
1517   fprintf (f, "  cp%d:a%d(r%d)<->a%d(r%d)@%d:%s\n", cp->num,
1518            ALLOCNO_NUM (cp->first), ALLOCNO_REGNO (cp->first),
1519            ALLOCNO_NUM (cp->second), ALLOCNO_REGNO (cp->second), cp->freq,
1520            cp->insn != NULL
1521            ? "move" : cp->constraint_p ? "constraint" : "shuffle");
1522 }
1523
1524 DEBUG_FUNCTION void
1525 debug (ira_allocno_copy &ref)
1526 {
1527   print_copy (stderr, &ref);
1528 }
1529
1530 DEBUG_FUNCTION void
1531 debug (ira_allocno_copy *ptr)
1532 {
1533   if (ptr)
1534     debug (*ptr);
1535   else
1536     fprintf (stderr, "<nil>\n");
1537 }
1538
1539 /* Print info about copy CP into stderr.  */
1540 void
1541 ira_debug_copy (ira_copy_t cp)
1542 {
1543   print_copy (stderr, cp);
1544 }
1545
1546 /* Print info about all copies into file F.  */
1547 static void
1548 print_copies (FILE *f)
1549 {
1550   ira_copy_t cp;
1551   ira_copy_iterator ci;
1552
1553   FOR_EACH_COPY (cp, ci)
1554     print_copy (f, cp);
1555 }
1556
1557 /* Print info about all copies into stderr.  */
1558 void
1559 ira_debug_copies (void)
1560 {
1561   print_copies (stderr);
1562 }
1563
1564 /* Print info about copies involving allocno A into file F.  */
1565 static void
1566 print_allocno_copies (FILE *f, ira_allocno_t a)
1567 {
1568   ira_allocno_t another_a;
1569   ira_copy_t cp, next_cp;
1570
1571   fprintf (f, " a%d(r%d):", ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
1572   for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
1573     {
1574       if (cp->first == a)
1575         {
1576           next_cp = cp->next_first_allocno_copy;
1577           another_a = cp->second;
1578         }
1579       else if (cp->second == a)
1580         {
1581           next_cp = cp->next_second_allocno_copy;
1582           another_a = cp->first;
1583         }
1584       else
1585         gcc_unreachable ();
1586       fprintf (f, " cp%d:a%d(r%d)@%d", cp->num,
1587                ALLOCNO_NUM (another_a), ALLOCNO_REGNO (another_a), cp->freq);
1588     }
1589   fprintf (f, "\n");
1590 }
1591
1592 DEBUG_FUNCTION void
1593 debug (ira_allocno &ref)
1594 {
1595   print_allocno_copies (stderr, &ref);
1596 }
1597
1598 DEBUG_FUNCTION void
1599 debug (ira_allocno *ptr)
1600 {
1601   if (ptr)
1602     debug (*ptr);
1603   else
1604     fprintf (stderr, "<nil>\n");
1605 }
1606
1607
1608 /* Print info about copies involving allocno A into stderr.  */
1609 void
1610 ira_debug_allocno_copies (ira_allocno_t a)
1611 {
1612   print_allocno_copies (stderr, a);
1613 }
1614
1615 /* The function frees memory allocated for copy CP.  */
1616 static void
1617 finish_copy (ira_copy_t cp)
1618 {
1619   pool_free (copy_pool, cp);
1620 }
1621
1622
1623 /* Free memory allocated for all copies.  */
1624 static void
1625 finish_copies (void)
1626 {
1627   ira_copy_t cp;
1628   ira_copy_iterator ci;
1629
1630   FOR_EACH_COPY (cp, ci)
1631     finish_copy (cp);
1632   copy_vec.release ();
1633   free_alloc_pool (copy_pool);
1634 }
1635
1636 \f
1637
1638 /* Pools for cost vectors.  It is defined only for allocno classes.  */
1639 static alloc_pool cost_vector_pool[N_REG_CLASSES];
1640
1641 /* The function initiates work with hard register cost vectors.  It
1642    creates allocation pool for each allocno class.  */
1643 static void
1644 initiate_cost_vectors (void)
1645 {
1646   int i;
1647   enum reg_class aclass;
1648
1649   for (i = 0; i < ira_allocno_classes_num; i++)
1650     {
1651       aclass = ira_allocno_classes[i];
1652       cost_vector_pool[aclass]
1653         = create_alloc_pool ("cost vectors",
1654                              sizeof (int) * ira_class_hard_regs_num[aclass],
1655                              100);
1656     }
1657 }
1658
1659 /* Allocate and return a cost vector VEC for ACLASS.  */
1660 int *
1661 ira_allocate_cost_vector (reg_class_t aclass)
1662 {
1663   return (int *) pool_alloc (cost_vector_pool[(int) aclass]);
1664 }
1665
1666 /* Free a cost vector VEC for ACLASS.  */
1667 void
1668 ira_free_cost_vector (int *vec, reg_class_t aclass)
1669 {
1670   ira_assert (vec != NULL);
1671   pool_free (cost_vector_pool[(int) aclass], vec);
1672 }
1673
1674 /* Finish work with hard register cost vectors.  Release allocation
1675    pool for each allocno class.  */
1676 static void
1677 finish_cost_vectors (void)
1678 {
1679   int i;
1680   enum reg_class aclass;
1681
1682   for (i = 0; i < ira_allocno_classes_num; i++)
1683     {
1684       aclass = ira_allocno_classes[i];
1685       free_alloc_pool (cost_vector_pool[aclass]);
1686     }
1687 }
1688
1689 \f
1690
1691 /* Compute a post-ordering of the reverse control flow of the loop body
1692    designated by the children nodes of LOOP_NODE, whose body nodes in
1693    pre-order are input as LOOP_PREORDER.  Return a VEC with a post-order
1694    of the reverse loop body.
1695
1696    For the post-order of the reverse CFG, we visit the basic blocks in
1697    LOOP_PREORDER array in the reverse order of where they appear.
1698    This is important: We do not just want to compute a post-order of
1699    the reverse CFG, we want to make a best-guess for a visiting order that
1700    minimizes the number of chain elements per allocno live range.  If the
1701    blocks would be visited in a different order, we would still compute a
1702    correct post-ordering but it would be less likely that two nodes
1703    connected by an edge in the CFG are neighbours in the topsort.  */
1704
1705 static vec<ira_loop_tree_node_t>
1706 ira_loop_tree_body_rev_postorder (ira_loop_tree_node_t loop_node ATTRIBUTE_UNUSED,
1707                                   vec<ira_loop_tree_node_t> loop_preorder)
1708 {
1709   vec<ira_loop_tree_node_t> topsort_nodes = vNULL;
1710   unsigned int n_loop_preorder;
1711
1712   n_loop_preorder = loop_preorder.length ();
1713   if (n_loop_preorder != 0)
1714     {
1715       ira_loop_tree_node_t subloop_node;
1716       unsigned int i;
1717       auto_vec<ira_loop_tree_node_t> dfs_stack;
1718
1719       /* This is a bit of strange abuse of the BB_VISITED flag:  We use
1720          the flag to mark blocks we still have to visit to add them to
1721          our post-order.  Define an alias to avoid confusion.  */
1722 #define BB_TO_VISIT BB_VISITED
1723
1724       FOR_EACH_VEC_ELT (loop_preorder, i, subloop_node)
1725         {
1726           gcc_checking_assert (! (subloop_node->bb->flags & BB_TO_VISIT));
1727           subloop_node->bb->flags |= BB_TO_VISIT;
1728         }
1729
1730       topsort_nodes.create (n_loop_preorder);
1731       dfs_stack.create (n_loop_preorder);
1732
1733       FOR_EACH_VEC_ELT_REVERSE (loop_preorder, i, subloop_node)
1734         {
1735           if (! (subloop_node->bb->flags & BB_TO_VISIT))
1736             continue;
1737
1738           subloop_node->bb->flags &= ~BB_TO_VISIT;
1739           dfs_stack.quick_push (subloop_node);
1740           while (! dfs_stack.is_empty ())
1741             {
1742               edge e;
1743               edge_iterator ei;
1744
1745               ira_loop_tree_node_t n = dfs_stack.last ();
1746               FOR_EACH_EDGE (e, ei, n->bb->preds)
1747                 {
1748                   ira_loop_tree_node_t pred_node;
1749                   basic_block pred_bb = e->src;
1750
1751                   if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1752                     continue;
1753
1754                   pred_node = IRA_BB_NODE_BY_INDEX (pred_bb->index);
1755                   if (pred_node != n
1756                       && (pred_node->bb->flags & BB_TO_VISIT))
1757                     {
1758                       pred_node->bb->flags &= ~BB_TO_VISIT;
1759                       dfs_stack.quick_push (pred_node);
1760                     }
1761                 }
1762               if (n == dfs_stack.last ())
1763                 {
1764                   dfs_stack.pop ();
1765                   topsort_nodes.quick_push (n);
1766                 }
1767             }
1768         }
1769
1770 #undef BB_TO_VISIT
1771     }
1772
1773   gcc_assert (topsort_nodes.length () == n_loop_preorder);
1774   return topsort_nodes;
1775 }
1776
1777 /* The current loop tree node and its regno allocno map.  */
1778 ira_loop_tree_node_t ira_curr_loop_tree_node;
1779 ira_allocno_t *ira_curr_regno_allocno_map;
1780
1781 /* This recursive function traverses loop tree with root LOOP_NODE
1782    calling non-null functions PREORDER_FUNC and POSTORDER_FUNC
1783    correspondingly in preorder and postorder.  The function sets up
1784    IRA_CURR_LOOP_TREE_NODE and IRA_CURR_REGNO_ALLOCNO_MAP.  If BB_P,
1785    basic block nodes of LOOP_NODE is also processed (before its
1786    subloop nodes).
1787
1788    If BB_P is set and POSTORDER_FUNC is given, the basic blocks in
1789    the loop are passed in the *reverse* post-order of the *reverse*
1790    CFG.  This is only used by ira_create_allocno_live_ranges, which
1791    wants to visit basic blocks in this order to minimize the number
1792    of elements per live range chain.
1793    Note that the loop tree nodes are still visited in the normal,
1794    forward post-order of  the loop tree.  */
1795
1796 void
1797 ira_traverse_loop_tree (bool bb_p, ira_loop_tree_node_t loop_node,
1798                         void (*preorder_func) (ira_loop_tree_node_t),
1799                         void (*postorder_func) (ira_loop_tree_node_t))
1800 {
1801   ira_loop_tree_node_t subloop_node;
1802
1803   ira_assert (loop_node->bb == NULL);
1804   ira_curr_loop_tree_node = loop_node;
1805   ira_curr_regno_allocno_map = ira_curr_loop_tree_node->regno_allocno_map;
1806
1807   if (preorder_func != NULL)
1808     (*preorder_func) (loop_node);
1809
1810   if (bb_p)
1811     {
1812       auto_vec<ira_loop_tree_node_t> loop_preorder;
1813       unsigned int i;
1814
1815       /* Add all nodes to the set of nodes to visit.  The IRA loop tree
1816          is set up such that nodes in the loop body appear in a pre-order
1817          of their place in the CFG.  */
1818       for (subloop_node = loop_node->children;
1819            subloop_node != NULL;
1820            subloop_node = subloop_node->next)
1821         if (subloop_node->bb != NULL)
1822           loop_preorder.safe_push (subloop_node);
1823
1824       if (preorder_func != NULL)
1825         FOR_EACH_VEC_ELT (loop_preorder, i, subloop_node)
1826           (*preorder_func) (subloop_node);
1827
1828       if (postorder_func != NULL)
1829         {
1830           vec<ira_loop_tree_node_t> loop_rev_postorder =
1831             ira_loop_tree_body_rev_postorder (loop_node, loop_preorder);
1832           FOR_EACH_VEC_ELT_REVERSE (loop_rev_postorder, i, subloop_node)
1833             (*postorder_func) (subloop_node);
1834           loop_rev_postorder.release ();
1835         }
1836     }
1837
1838   for (subloop_node = loop_node->subloops;
1839        subloop_node != NULL;
1840        subloop_node = subloop_node->subloop_next)
1841     {
1842       ira_assert (subloop_node->bb == NULL);
1843       ira_traverse_loop_tree (bb_p, subloop_node,
1844                               preorder_func, postorder_func);
1845     }
1846
1847   ira_curr_loop_tree_node = loop_node;
1848   ira_curr_regno_allocno_map = ira_curr_loop_tree_node->regno_allocno_map;
1849
1850   if (postorder_func != NULL)
1851     (*postorder_func) (loop_node);
1852 }
1853
1854 \f
1855
1856 /* The basic block currently being processed.  */
1857 static basic_block curr_bb;
1858
1859 /* This recursive function creates allocnos corresponding to
1860    pseudo-registers containing in X.  True OUTPUT_P means that X is
1861    an lvalue.  PARENT corresponds to the parent expression of X.  */
1862 static void
1863 create_insn_allocnos (rtx x, rtx outer, bool output_p)
1864 {
1865   int i, j;
1866   const char *fmt;
1867   enum rtx_code code = GET_CODE (x);
1868
1869   if (code == REG)
1870     {
1871       int regno;
1872
1873       if ((regno = REGNO (x)) >= FIRST_PSEUDO_REGISTER)
1874         {
1875           ira_allocno_t a;
1876
1877           if ((a = ira_curr_regno_allocno_map[regno]) == NULL)
1878             {
1879               a = ira_create_allocno (regno, false, ira_curr_loop_tree_node);
1880               if (outer != NULL && GET_CODE (outer) == SUBREG)
1881                 {
1882                   enum machine_mode wmode = GET_MODE (outer);
1883                   if (GET_MODE_SIZE (wmode) > GET_MODE_SIZE (ALLOCNO_WMODE (a)))
1884                     ALLOCNO_WMODE (a) = wmode;
1885                 }
1886             }
1887
1888           ALLOCNO_NREFS (a)++;
1889           ALLOCNO_FREQ (a) += REG_FREQ_FROM_BB (curr_bb);
1890           if (output_p)
1891             bitmap_set_bit (ira_curr_loop_tree_node->modified_regnos, regno);
1892         }
1893       return;
1894     }
1895   else if (code == SET)
1896     {
1897       create_insn_allocnos (SET_DEST (x), NULL, true);
1898       create_insn_allocnos (SET_SRC (x), NULL, false);
1899       return;
1900     }
1901   else if (code == CLOBBER)
1902     {
1903       create_insn_allocnos (XEXP (x, 0), NULL, true);
1904       return;
1905     }
1906   else if (code == MEM)
1907     {
1908       create_insn_allocnos (XEXP (x, 0), NULL, false);
1909       return;
1910     }
1911   else if (code == PRE_DEC || code == POST_DEC || code == PRE_INC ||
1912            code == POST_INC || code == POST_MODIFY || code == PRE_MODIFY)
1913     {
1914       create_insn_allocnos (XEXP (x, 0), NULL, true);
1915       create_insn_allocnos (XEXP (x, 0), NULL, false);
1916       return;
1917     }
1918
1919   fmt = GET_RTX_FORMAT (code);
1920   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1921     {
1922       if (fmt[i] == 'e')
1923         create_insn_allocnos (XEXP (x, i), x, output_p);
1924       else if (fmt[i] == 'E')
1925         for (j = 0; j < XVECLEN (x, i); j++)
1926           create_insn_allocnos (XVECEXP (x, i, j), x, output_p);
1927     }
1928 }
1929
1930 /* Create allocnos corresponding to pseudo-registers living in the
1931    basic block represented by the corresponding loop tree node
1932    BB_NODE.  */
1933 static void
1934 create_bb_allocnos (ira_loop_tree_node_t bb_node)
1935 {
1936   basic_block bb;
1937   rtx insn;
1938   unsigned int i;
1939   bitmap_iterator bi;
1940
1941   curr_bb = bb = bb_node->bb;
1942   ira_assert (bb != NULL);
1943   FOR_BB_INSNS_REVERSE (bb, insn)
1944     if (NONDEBUG_INSN_P (insn))
1945       create_insn_allocnos (PATTERN (insn), NULL, false);
1946   /* It might be a allocno living through from one subloop to
1947      another.  */
1948   EXECUTE_IF_SET_IN_REG_SET (df_get_live_in (bb), FIRST_PSEUDO_REGISTER, i, bi)
1949     if (ira_curr_regno_allocno_map[i] == NULL)
1950       ira_create_allocno (i, false, ira_curr_loop_tree_node);
1951 }
1952
1953 /* Create allocnos corresponding to pseudo-registers living on edge E
1954    (a loop entry or exit).  Also mark the allocnos as living on the
1955    loop border. */
1956 static void
1957 create_loop_allocnos (edge e)
1958 {
1959   unsigned int i;
1960   bitmap live_in_regs, border_allocnos;
1961   bitmap_iterator bi;
1962   ira_loop_tree_node_t parent;
1963
1964   live_in_regs = df_get_live_in (e->dest);
1965   border_allocnos = ira_curr_loop_tree_node->border_allocnos;
1966   EXECUTE_IF_SET_IN_REG_SET (df_get_live_out (e->src),
1967                              FIRST_PSEUDO_REGISTER, i, bi)
1968     if (bitmap_bit_p (live_in_regs, i))
1969       {
1970         if (ira_curr_regno_allocno_map[i] == NULL)
1971           {
1972             /* The order of creations is important for right
1973                ira_regno_allocno_map.  */
1974             if ((parent = ira_curr_loop_tree_node->parent) != NULL
1975                 && parent->regno_allocno_map[i] == NULL)
1976               ira_create_allocno (i, false, parent);
1977             ira_create_allocno (i, false, ira_curr_loop_tree_node);
1978           }
1979         bitmap_set_bit (border_allocnos,
1980                         ALLOCNO_NUM (ira_curr_regno_allocno_map[i]));
1981       }
1982 }
1983
1984 /* Create allocnos corresponding to pseudo-registers living in loop
1985    represented by the corresponding loop tree node LOOP_NODE.  This
1986    function is called by ira_traverse_loop_tree.  */
1987 static void
1988 create_loop_tree_node_allocnos (ira_loop_tree_node_t loop_node)
1989 {
1990   if (loop_node->bb != NULL)
1991     create_bb_allocnos (loop_node);
1992   else if (loop_node != ira_loop_tree_root)
1993     {
1994       int i;
1995       edge_iterator ei;
1996       edge e;
1997       vec<edge> edges;
1998
1999       ira_assert (current_loops != NULL);
2000       FOR_EACH_EDGE (e, ei, loop_node->loop->header->preds)
2001         if (e->src != loop_node->loop->latch)
2002           create_loop_allocnos (e);
2003
2004       edges = get_loop_exit_edges (loop_node->loop);
2005       FOR_EACH_VEC_ELT (edges, i, e)
2006         create_loop_allocnos (e);
2007       edges.release ();
2008     }
2009 }
2010
2011 /* Propagate information about allocnos modified inside the loop given
2012    by its LOOP_TREE_NODE to its parent.  */
2013 static void
2014 propagate_modified_regnos (ira_loop_tree_node_t loop_tree_node)
2015 {
2016   if (loop_tree_node == ira_loop_tree_root)
2017     return;
2018   ira_assert (loop_tree_node->bb == NULL);
2019   bitmap_ior_into (loop_tree_node->parent->modified_regnos,
2020                    loop_tree_node->modified_regnos);
2021 }
2022
2023 /* Propagate new info about allocno A (see comments about accumulated
2024    info in allocno definition) to the corresponding allocno on upper
2025    loop tree level.  So allocnos on upper levels accumulate
2026    information about the corresponding allocnos in nested regions.
2027    The new info means allocno info finally calculated in this
2028    file.  */
2029 static void
2030 propagate_allocno_info (void)
2031 {
2032   int i;
2033   ira_allocno_t a, parent_a;
2034   ira_loop_tree_node_t parent;
2035   enum reg_class aclass;
2036
2037   if (flag_ira_region != IRA_REGION_ALL
2038       && flag_ira_region != IRA_REGION_MIXED)
2039     return;
2040   for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--)
2041     for (a = ira_regno_allocno_map[i];
2042          a != NULL;
2043          a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
2044       if ((parent = ALLOCNO_LOOP_TREE_NODE (a)->parent) != NULL
2045           && (parent_a = parent->regno_allocno_map[i]) != NULL
2046           /* There are no caps yet at this point.  So use
2047              border_allocnos to find allocnos for the propagation.  */
2048           && bitmap_bit_p (ALLOCNO_LOOP_TREE_NODE (a)->border_allocnos,
2049                            ALLOCNO_NUM (a)))
2050         {
2051           if (! ALLOCNO_BAD_SPILL_P (a))
2052             ALLOCNO_BAD_SPILL_P (parent_a) = false;
2053           ALLOCNO_NREFS (parent_a) += ALLOCNO_NREFS (a);
2054           ALLOCNO_FREQ (parent_a) += ALLOCNO_FREQ (a);
2055           ALLOCNO_CALL_FREQ (parent_a) += ALLOCNO_CALL_FREQ (a);
2056           merge_hard_reg_conflicts (a, parent_a, true);
2057           ALLOCNO_CALLS_CROSSED_NUM (parent_a)
2058             += ALLOCNO_CALLS_CROSSED_NUM (a);
2059           ALLOCNO_CHEAP_CALLS_CROSSED_NUM (parent_a)
2060             += ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a);
2061           ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (parent_a)
2062             += ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a);
2063           aclass = ALLOCNO_CLASS (a);
2064           ira_assert (aclass == ALLOCNO_CLASS (parent_a));
2065           ira_allocate_and_accumulate_costs
2066             (&ALLOCNO_HARD_REG_COSTS (parent_a), aclass,
2067              ALLOCNO_HARD_REG_COSTS (a));
2068           ira_allocate_and_accumulate_costs
2069             (&ALLOCNO_CONFLICT_HARD_REG_COSTS (parent_a),
2070              aclass,
2071              ALLOCNO_CONFLICT_HARD_REG_COSTS (a));
2072           ALLOCNO_CLASS_COST (parent_a)
2073             += ALLOCNO_CLASS_COST (a);
2074           ALLOCNO_MEMORY_COST (parent_a) += ALLOCNO_MEMORY_COST (a);
2075         }
2076 }
2077
2078 /* Create allocnos corresponding to pseudo-registers in the current
2079    function.  Traverse the loop tree for this.  */
2080 static void
2081 create_allocnos (void)
2082 {
2083   /* We need to process BB first to correctly link allocnos by member
2084      next_regno_allocno.  */
2085   ira_traverse_loop_tree (true, ira_loop_tree_root,
2086                           create_loop_tree_node_allocnos, NULL);
2087   if (optimize)
2088     ira_traverse_loop_tree (false, ira_loop_tree_root, NULL,
2089                             propagate_modified_regnos);
2090 }
2091
2092 \f
2093
2094 /* The page contains function to remove some regions from a separate
2095    register allocation.  We remove regions whose separate allocation
2096    will hardly improve the result.  As a result we speed up regional
2097    register allocation.  */
2098
2099 /* The function changes the object in range list given by R to OBJ.  */
2100 static void
2101 change_object_in_range_list (live_range_t r, ira_object_t obj)
2102 {
2103   for (; r != NULL; r = r->next)
2104     r->object = obj;
2105 }
2106
2107 /* Move all live ranges associated with allocno FROM to allocno TO.  */
2108 static void
2109 move_allocno_live_ranges (ira_allocno_t from, ira_allocno_t to)
2110 {
2111   int i;
2112   int n = ALLOCNO_NUM_OBJECTS (from);
2113
2114   gcc_assert (n == ALLOCNO_NUM_OBJECTS (to));
2115
2116   for (i = 0; i < n; i++)
2117     {
2118       ira_object_t from_obj = ALLOCNO_OBJECT (from, i);
2119       ira_object_t to_obj = ALLOCNO_OBJECT (to, i);
2120       live_range_t lr = OBJECT_LIVE_RANGES (from_obj);
2121
2122       if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL)
2123         {
2124           fprintf (ira_dump_file,
2125                    "      Moving ranges of a%dr%d to a%dr%d: ",
2126                    ALLOCNO_NUM (from), ALLOCNO_REGNO (from),
2127                    ALLOCNO_NUM (to), ALLOCNO_REGNO (to));
2128           ira_print_live_range_list (ira_dump_file, lr);
2129         }
2130       change_object_in_range_list (lr, to_obj);
2131       OBJECT_LIVE_RANGES (to_obj)
2132         = ira_merge_live_ranges (lr, OBJECT_LIVE_RANGES (to_obj));
2133       OBJECT_LIVE_RANGES (from_obj) = NULL;
2134     }
2135 }
2136
2137 static void
2138 copy_allocno_live_ranges (ira_allocno_t from, ira_allocno_t to)
2139 {
2140   int i;
2141   int n = ALLOCNO_NUM_OBJECTS (from);
2142
2143   gcc_assert (n == ALLOCNO_NUM_OBJECTS (to));
2144
2145   for (i = 0; i < n; i++)
2146     {
2147       ira_object_t from_obj = ALLOCNO_OBJECT (from, i);
2148       ira_object_t to_obj = ALLOCNO_OBJECT (to, i);
2149       live_range_t lr = OBJECT_LIVE_RANGES (from_obj);
2150
2151       if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL)
2152         {
2153           fprintf (ira_dump_file, "      Copying ranges of a%dr%d to a%dr%d: ",
2154                    ALLOCNO_NUM (from), ALLOCNO_REGNO (from),
2155                    ALLOCNO_NUM (to), ALLOCNO_REGNO (to));
2156           ira_print_live_range_list (ira_dump_file, lr);
2157         }
2158       lr = ira_copy_live_range_list (lr);
2159       change_object_in_range_list (lr, to_obj);
2160       OBJECT_LIVE_RANGES (to_obj)
2161         = ira_merge_live_ranges (lr, OBJECT_LIVE_RANGES (to_obj));
2162     }
2163 }
2164
2165 /* Return TRUE if NODE represents a loop with low register
2166    pressure.  */
2167 static bool
2168 low_pressure_loop_node_p (ira_loop_tree_node_t node)
2169 {
2170   int i;
2171   enum reg_class pclass;
2172
2173   if (node->bb != NULL)
2174     return false;
2175
2176   for (i = 0; i < ira_pressure_classes_num; i++)
2177     {
2178       pclass = ira_pressure_classes[i];
2179       if (node->reg_pressure[pclass] > ira_class_hard_regs_num[pclass]
2180           && ira_class_hard_regs_num[pclass] > 1)
2181         return false;
2182     }
2183   return true;
2184 }
2185
2186 #ifdef STACK_REGS
2187 /* Return TRUE if LOOP has a complex enter or exit edge.  We don't
2188    form a region from such loop if the target use stack register
2189    because reg-stack.c can not deal with such edges.  */
2190 static bool
2191 loop_with_complex_edge_p (struct loop *loop)
2192 {
2193   int i;
2194   edge_iterator ei;
2195   edge e;
2196   vec<edge> edges;
2197   bool res;
2198
2199   FOR_EACH_EDGE (e, ei, loop->header->preds)
2200     if (e->flags & EDGE_EH)
2201       return true;
2202   edges = get_loop_exit_edges (loop);
2203   res = false;
2204   FOR_EACH_VEC_ELT (edges, i, e)
2205     if (e->flags & EDGE_COMPLEX)
2206       {
2207         res = true;
2208         break;
2209       }
2210   edges.release ();
2211   return res;
2212 }
2213 #endif
2214
2215 /* Sort loops for marking them for removal.  We put already marked
2216    loops first, then less frequent loops next, and then outer loops
2217    next.  */
2218 static int
2219 loop_compare_func (const void *v1p, const void *v2p)
2220 {
2221   int diff;
2222   ira_loop_tree_node_t l1 = *(const ira_loop_tree_node_t *) v1p;
2223   ira_loop_tree_node_t l2 = *(const ira_loop_tree_node_t *) v2p;
2224
2225   ira_assert (l1->parent != NULL && l2->parent != NULL);
2226   if (l1->to_remove_p && ! l2->to_remove_p)
2227     return -1;
2228   if (! l1->to_remove_p && l2->to_remove_p)
2229     return 1;
2230   if ((diff = l1->loop->header->frequency - l2->loop->header->frequency) != 0)
2231     return diff;
2232   if ((diff = (int) loop_depth (l1->loop) - (int) loop_depth (l2->loop)) != 0)
2233     return diff;
2234   /* Make sorting stable.  */
2235   return l1->loop_num - l2->loop_num;
2236 }
2237
2238 /* Mark loops which should be removed from regional allocation.  We
2239    remove a loop with low register pressure inside another loop with
2240    register pressure.  In this case a separate allocation of the loop
2241    hardly helps (for irregular register file architecture it could
2242    help by choosing a better hard register in the loop but we prefer
2243    faster allocation even in this case).  We also remove cheap loops
2244    if there are more than IRA_MAX_LOOPS_NUM of them.  Loop with EH
2245    exit or enter edges are removed too because the allocation might
2246    require put pseudo moves on the EH edges (we could still do this
2247    for pseudos with caller saved hard registers in some cases but it
2248    is impossible to say here or during top-down allocation pass what
2249    hard register the pseudos get finally).  */
2250 static void
2251 mark_loops_for_removal (void)
2252 {
2253   int i, n;
2254   ira_loop_tree_node_t *sorted_loops;
2255   loop_p loop;
2256
2257   ira_assert (current_loops != NULL);
2258   sorted_loops
2259     = (ira_loop_tree_node_t *) ira_allocate (sizeof (ira_loop_tree_node_t)
2260                                              * number_of_loops (cfun));
2261   for (n = i = 0; vec_safe_iterate (get_loops (cfun), i, &loop); i++)
2262     if (ira_loop_nodes[i].regno_allocno_map != NULL)
2263       {
2264         if (ira_loop_nodes[i].parent == NULL)
2265           {
2266             /* Don't remove the root.  */
2267             ira_loop_nodes[i].to_remove_p = false;
2268             continue;
2269           }
2270         sorted_loops[n++] = &ira_loop_nodes[i];
2271         ira_loop_nodes[i].to_remove_p
2272           = ((low_pressure_loop_node_p (ira_loop_nodes[i].parent)
2273               && low_pressure_loop_node_p (&ira_loop_nodes[i]))
2274 #ifdef STACK_REGS
2275              || loop_with_complex_edge_p (ira_loop_nodes[i].loop)
2276 #endif
2277              );
2278       }
2279   qsort (sorted_loops, n, sizeof (ira_loop_tree_node_t), loop_compare_func);
2280   for (i = 0; n - i + 1 > IRA_MAX_LOOPS_NUM; i++)
2281     {
2282       sorted_loops[i]->to_remove_p = true;
2283       if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
2284         fprintf
2285           (ira_dump_file,
2286            "  Mark loop %d (header %d, freq %d, depth %d) for removal (%s)\n",
2287            sorted_loops[i]->loop_num, sorted_loops[i]->loop->header->index,
2288            sorted_loops[i]->loop->header->frequency,
2289            loop_depth (sorted_loops[i]->loop),
2290            low_pressure_loop_node_p (sorted_loops[i]->parent)
2291            && low_pressure_loop_node_p (sorted_loops[i])
2292            ? "low pressure" : "cheap loop");
2293     }
2294   ira_free (sorted_loops);
2295 }
2296
2297 /* Mark all loops but root for removing.  */
2298 static void
2299 mark_all_loops_for_removal (void)
2300 {
2301   int i;
2302   loop_p loop;
2303
2304   ira_assert (current_loops != NULL);
2305   FOR_EACH_VEC_SAFE_ELT (get_loops (cfun), i, loop)
2306     if (ira_loop_nodes[i].regno_allocno_map != NULL)
2307       {
2308         if (ira_loop_nodes[i].parent == NULL)
2309           {
2310             /* Don't remove the root.  */
2311             ira_loop_nodes[i].to_remove_p = false;
2312             continue;
2313           }
2314         ira_loop_nodes[i].to_remove_p = true;
2315         if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
2316           fprintf
2317             (ira_dump_file,
2318              "  Mark loop %d (header %d, freq %d, depth %d) for removal\n",
2319              ira_loop_nodes[i].loop_num,
2320              ira_loop_nodes[i].loop->header->index,
2321              ira_loop_nodes[i].loop->header->frequency,
2322              loop_depth (ira_loop_nodes[i].loop));
2323       }
2324 }
2325
2326 /* Definition of vector of loop tree nodes.  */
2327
2328 /* Vec containing references to all removed loop tree nodes.  */
2329 static vec<ira_loop_tree_node_t> removed_loop_vec;
2330
2331 /* Vec containing references to all children of loop tree nodes.  */
2332 static vec<ira_loop_tree_node_t> children_vec;
2333
2334 /* Remove subregions of NODE if their separate allocation will not
2335    improve the result.  */
2336 static void
2337 remove_uneccesary_loop_nodes_from_loop_tree (ira_loop_tree_node_t node)
2338 {
2339   unsigned int start;
2340   bool remove_p;
2341   ira_loop_tree_node_t subnode;
2342
2343   remove_p = node->to_remove_p;
2344   if (! remove_p)
2345     children_vec.safe_push (node);
2346   start = children_vec.length ();
2347   for (subnode = node->children; subnode != NULL; subnode = subnode->next)
2348     if (subnode->bb == NULL)
2349       remove_uneccesary_loop_nodes_from_loop_tree (subnode);
2350     else
2351       children_vec.safe_push (subnode);
2352   node->children = node->subloops = NULL;
2353   if (remove_p)
2354     {
2355       removed_loop_vec.safe_push (node);
2356       return;
2357     }
2358   while (children_vec.length () > start)
2359     {
2360       subnode = children_vec.pop ();
2361       subnode->parent = node;
2362       subnode->next = node->children;
2363       node->children = subnode;
2364       if (subnode->bb == NULL)
2365         {
2366           subnode->subloop_next = node->subloops;
2367           node->subloops = subnode;
2368         }
2369     }
2370 }
2371
2372 /* Return TRUE if NODE is inside PARENT.  */
2373 static bool
2374 loop_is_inside_p (ira_loop_tree_node_t node, ira_loop_tree_node_t parent)
2375 {
2376   for (node = node->parent; node != NULL; node = node->parent)
2377     if (node == parent)
2378       return true;
2379   return false;
2380 }
2381
2382 /* Sort allocnos according to their order in regno allocno list.  */
2383 static int
2384 regno_allocno_order_compare_func (const void *v1p, const void *v2p)
2385 {
2386   ira_allocno_t a1 = *(const ira_allocno_t *) v1p;
2387   ira_allocno_t a2 = *(const ira_allocno_t *) v2p;
2388   ira_loop_tree_node_t n1 = ALLOCNO_LOOP_TREE_NODE (a1);
2389   ira_loop_tree_node_t n2 = ALLOCNO_LOOP_TREE_NODE (a2);
2390
2391   if (loop_is_inside_p (n1, n2))
2392     return -1;
2393   else if (loop_is_inside_p (n2, n1))
2394     return 1;
2395   /* If allocnos are equally good, sort by allocno numbers, so that
2396      the results of qsort leave nothing to chance.  We put allocnos
2397      with higher number first in the list because it is the original
2398      order for allocnos from loops on the same levels.  */
2399   return ALLOCNO_NUM (a2) - ALLOCNO_NUM (a1);
2400 }
2401
2402 /* This array is used to sort allocnos to restore allocno order in
2403    the regno allocno list.  */
2404 static ira_allocno_t *regno_allocnos;
2405
2406 /* Restore allocno order for REGNO in the regno allocno list.  */
2407 static void
2408 ira_rebuild_regno_allocno_list (int regno)
2409 {
2410   int i, n;
2411   ira_allocno_t a;
2412
2413   for (n = 0, a = ira_regno_allocno_map[regno];
2414        a != NULL;
2415        a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
2416     regno_allocnos[n++] = a;
2417   ira_assert (n > 0);
2418   qsort (regno_allocnos, n, sizeof (ira_allocno_t),
2419          regno_allocno_order_compare_func);
2420   for (i = 1; i < n; i++)
2421     ALLOCNO_NEXT_REGNO_ALLOCNO (regno_allocnos[i - 1]) = regno_allocnos[i];
2422   ALLOCNO_NEXT_REGNO_ALLOCNO (regno_allocnos[n - 1]) = NULL;
2423   ira_regno_allocno_map[regno] = regno_allocnos[0];
2424   if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
2425     fprintf (ira_dump_file, " Rebuilding regno allocno list for %d\n", regno);
2426 }
2427
2428 /* Propagate info from allocno FROM_A to allocno A.  */
2429 static void
2430 propagate_some_info_from_allocno (ira_allocno_t a, ira_allocno_t from_a)
2431 {
2432   enum reg_class aclass;
2433
2434   merge_hard_reg_conflicts (from_a, a, false);
2435   ALLOCNO_NREFS (a) += ALLOCNO_NREFS (from_a);
2436   ALLOCNO_FREQ (a) += ALLOCNO_FREQ (from_a);
2437   ALLOCNO_CALL_FREQ (a) += ALLOCNO_CALL_FREQ (from_a);
2438   ALLOCNO_CALLS_CROSSED_NUM (a) += ALLOCNO_CALLS_CROSSED_NUM (from_a);
2439   ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a)
2440     += ALLOCNO_CHEAP_CALLS_CROSSED_NUM (from_a);
2441   ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a)
2442     += ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (from_a);
2443   if (! ALLOCNO_BAD_SPILL_P (from_a))
2444     ALLOCNO_BAD_SPILL_P (a) = false;
2445   aclass = ALLOCNO_CLASS (from_a);
2446   ira_assert (aclass == ALLOCNO_CLASS (a));
2447   ira_allocate_and_accumulate_costs (&ALLOCNO_HARD_REG_COSTS (a), aclass,
2448                                      ALLOCNO_HARD_REG_COSTS (from_a));
2449   ira_allocate_and_accumulate_costs (&ALLOCNO_CONFLICT_HARD_REG_COSTS (a),
2450                                      aclass,
2451                                      ALLOCNO_CONFLICT_HARD_REG_COSTS (from_a));
2452   ALLOCNO_CLASS_COST (a) += ALLOCNO_CLASS_COST (from_a);
2453   ALLOCNO_MEMORY_COST (a) += ALLOCNO_MEMORY_COST (from_a);
2454 }
2455
2456 /* Remove allocnos from loops removed from the allocation
2457    consideration.  */
2458 static void
2459 remove_unnecessary_allocnos (void)
2460 {
2461   int regno;
2462   bool merged_p, rebuild_p;
2463   ira_allocno_t a, prev_a, next_a, parent_a;
2464   ira_loop_tree_node_t a_node, parent;
2465
2466   merged_p = false;
2467   regno_allocnos = NULL;
2468   for (regno = max_reg_num () - 1; regno >= FIRST_PSEUDO_REGISTER; regno--)
2469     {
2470       rebuild_p = false;
2471       for (prev_a = NULL, a = ira_regno_allocno_map[regno];
2472            a != NULL;
2473            a = next_a)
2474         {
2475           next_a = ALLOCNO_NEXT_REGNO_ALLOCNO (a);
2476           a_node = ALLOCNO_LOOP_TREE_NODE (a);
2477           if (! a_node->to_remove_p)
2478             prev_a = a;
2479           else
2480             {
2481               for (parent = a_node->parent;
2482                    (parent_a = parent->regno_allocno_map[regno]) == NULL
2483                      && parent->to_remove_p;
2484                    parent = parent->parent)
2485                 ;
2486               if (parent_a == NULL)
2487                 {
2488                   /* There are no allocnos with the same regno in
2489                      upper region -- just move the allocno to the
2490                      upper region.  */
2491                   prev_a = a;
2492                   ALLOCNO_LOOP_TREE_NODE (a) = parent;
2493                   parent->regno_allocno_map[regno] = a;
2494                   bitmap_set_bit (parent->all_allocnos, ALLOCNO_NUM (a));
2495                   rebuild_p = true;
2496                 }
2497               else
2498                 {
2499                   /* Remove the allocno and update info of allocno in
2500                      the upper region.  */
2501                   if (prev_a == NULL)
2502                     ira_regno_allocno_map[regno] = next_a;
2503                   else
2504                     ALLOCNO_NEXT_REGNO_ALLOCNO (prev_a) = next_a;
2505                   move_allocno_live_ranges (a, parent_a);
2506                   merged_p = true;
2507                   propagate_some_info_from_allocno (parent_a, a);
2508                   /* Remove it from the corresponding regno allocno
2509                      map to avoid info propagation of subsequent
2510                      allocno into this already removed allocno.  */
2511                   a_node->regno_allocno_map[regno] = NULL;
2512                   ira_remove_allocno_prefs (a);
2513                   finish_allocno (a);
2514                 }
2515             }
2516         }
2517       if (rebuild_p)
2518         /* We need to restore the order in regno allocno list.  */
2519         {
2520           if (regno_allocnos == NULL)
2521             regno_allocnos
2522               = (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t)
2523                                                 * ira_allocnos_num);
2524           ira_rebuild_regno_allocno_list (regno);
2525         }
2526     }
2527   if (merged_p)
2528     ira_rebuild_start_finish_chains ();
2529   if (regno_allocnos != NULL)
2530     ira_free (regno_allocnos);
2531 }
2532
2533 /* Remove allocnos from all loops but the root.  */
2534 static void
2535 remove_low_level_allocnos (void)
2536 {
2537   int regno;
2538   bool merged_p, propagate_p;
2539   ira_allocno_t a, top_a;
2540   ira_loop_tree_node_t a_node, parent;
2541   ira_allocno_iterator ai;
2542
2543   merged_p = false;
2544   FOR_EACH_ALLOCNO (a, ai)
2545     {
2546       a_node = ALLOCNO_LOOP_TREE_NODE (a);
2547       if (a_node == ira_loop_tree_root || ALLOCNO_CAP_MEMBER (a) != NULL)
2548         continue;
2549       regno = ALLOCNO_REGNO (a);
2550       if ((top_a = ira_loop_tree_root->regno_allocno_map[regno]) == NULL)
2551         {
2552           ALLOCNO_LOOP_TREE_NODE (a) = ira_loop_tree_root;
2553           ira_loop_tree_root->regno_allocno_map[regno] = a;
2554           continue;
2555         }
2556       propagate_p = a_node->parent->regno_allocno_map[regno] == NULL;
2557       /* Remove the allocno and update info of allocno in the upper
2558          region.  */
2559       move_allocno_live_ranges (a, top_a);
2560       merged_p = true;
2561       if (propagate_p)
2562         propagate_some_info_from_allocno (top_a, a);
2563     }
2564   FOR_EACH_ALLOCNO (a, ai)
2565     {
2566       a_node = ALLOCNO_LOOP_TREE_NODE (a);
2567       if (a_node == ira_loop_tree_root)
2568         continue;
2569       parent = a_node->parent;
2570       regno = ALLOCNO_REGNO (a);
2571       if (ALLOCNO_CAP_MEMBER (a) != NULL)
2572         ira_assert (ALLOCNO_CAP (a) != NULL);
2573       else if (ALLOCNO_CAP (a) == NULL)
2574         ira_assert (parent->regno_allocno_map[regno] != NULL);
2575     }
2576   FOR_EACH_ALLOCNO (a, ai)
2577     {
2578       regno = ALLOCNO_REGNO (a);
2579       if (ira_loop_tree_root->regno_allocno_map[regno] == a)
2580         {
2581           ira_object_t obj;
2582           ira_allocno_object_iterator oi;
2583
2584           ira_regno_allocno_map[regno] = a;
2585           ALLOCNO_NEXT_REGNO_ALLOCNO (a) = NULL;
2586           ALLOCNO_CAP_MEMBER (a) = NULL;
2587           FOR_EACH_ALLOCNO_OBJECT (a, obj, oi)
2588             COPY_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (obj),
2589                                OBJECT_TOTAL_CONFLICT_HARD_REGS (obj));
2590 #ifdef STACK_REGS
2591           if (ALLOCNO_TOTAL_NO_STACK_REG_P (a))
2592             ALLOCNO_NO_STACK_REG_P (a) = true;
2593 #endif
2594         }
2595       else
2596         {
2597           ira_remove_allocno_prefs (a);
2598           finish_allocno (a);
2599         }
2600     }
2601   if (merged_p)
2602     ira_rebuild_start_finish_chains ();
2603 }
2604
2605 /* Remove loops from consideration.  We remove all loops except for
2606    root if ALL_P or loops for which a separate allocation will not
2607    improve the result.  We have to do this after allocno creation and
2608    their costs and allocno class evaluation because only after that
2609    the register pressure can be known and is calculated.  */
2610 static void
2611 remove_unnecessary_regions (bool all_p)
2612 {
2613   if (current_loops == NULL)
2614     return;
2615   if (all_p)
2616     mark_all_loops_for_removal ();
2617   else
2618     mark_loops_for_removal ();
2619   children_vec.create (last_basic_block_for_fn (cfun)
2620                        + number_of_loops (cfun));
2621   removed_loop_vec.create (last_basic_block_for_fn (cfun)
2622                            + number_of_loops (cfun));
2623   remove_uneccesary_loop_nodes_from_loop_tree (ira_loop_tree_root);
2624   children_vec.release ();
2625   if (all_p)
2626     remove_low_level_allocnos ();
2627   else
2628     remove_unnecessary_allocnos ();
2629   while (removed_loop_vec.length () > 0)
2630     finish_loop_tree_node (removed_loop_vec.pop ());
2631   removed_loop_vec.release ();
2632 }
2633
2634 \f
2635
2636 /* At this point true value of allocno attribute bad_spill_p means
2637    that there is an insn where allocno occurs and where the allocno
2638    can not be used as memory.  The function updates the attribute, now
2639    it can be true only for allocnos which can not be used as memory in
2640    an insn and in whose live ranges there is other allocno deaths.
2641    Spilling allocnos with true value will not improve the code because
2642    it will not make other allocnos colorable and additional reloads
2643    for the corresponding pseudo will be generated in reload pass for
2644    each insn it occurs.
2645
2646    This is a trick mentioned in one classic article of Chaitin etc
2647    which is frequently omitted in other implementations of RA based on
2648    graph coloring.  */
2649 static void
2650 update_bad_spill_attribute (void)
2651 {
2652   int i;
2653   ira_allocno_t a;
2654   ira_allocno_iterator ai;
2655   ira_allocno_object_iterator aoi;
2656   ira_object_t obj;
2657   live_range_t r;
2658   enum reg_class aclass;
2659   bitmap_head dead_points[N_REG_CLASSES];
2660
2661   for (i = 0; i < ira_allocno_classes_num; i++)
2662     {
2663       aclass = ira_allocno_classes[i];
2664       bitmap_initialize (&dead_points[aclass], &reg_obstack);
2665     }
2666   FOR_EACH_ALLOCNO (a, ai)
2667     {
2668       aclass = ALLOCNO_CLASS (a);
2669       if (aclass == NO_REGS)
2670         continue;
2671       FOR_EACH_ALLOCNO_OBJECT (a, obj, aoi)
2672         for (r = OBJECT_LIVE_RANGES (obj); r != NULL; r = r->next)
2673           bitmap_set_bit (&dead_points[aclass], r->finish);
2674     }
2675   FOR_EACH_ALLOCNO (a, ai)
2676     {
2677       aclass = ALLOCNO_CLASS (a);
2678       if (aclass == NO_REGS)
2679         continue;
2680       if (! ALLOCNO_BAD_SPILL_P (a))
2681         continue;
2682       FOR_EACH_ALLOCNO_OBJECT (a, obj, aoi)
2683         {
2684           for (r = OBJECT_LIVE_RANGES (obj); r != NULL; r = r->next)
2685             {
2686               for (i = r->start + 1; i < r->finish; i++)
2687                 if (bitmap_bit_p (&dead_points[aclass], i))
2688                   break;
2689               if (i < r->finish)
2690                 break;
2691             }
2692           if (r != NULL)
2693             {
2694               ALLOCNO_BAD_SPILL_P (a) = false;
2695               break;
2696             }
2697         }
2698     }
2699   for (i = 0; i < ira_allocno_classes_num; i++)
2700     {
2701       aclass = ira_allocno_classes[i];
2702       bitmap_clear (&dead_points[aclass]);
2703     }
2704 }
2705
2706 \f
2707
2708 /* Set up minimal and maximal live range points for allocnos.  */
2709 static void
2710 setup_min_max_allocno_live_range_point (void)
2711 {
2712   int i;
2713   ira_allocno_t a, parent_a, cap;
2714   ira_allocno_iterator ai;
2715 #ifdef ENABLE_IRA_CHECKING
2716   ira_object_iterator oi;
2717   ira_object_t obj;
2718 #endif
2719   live_range_t r;
2720   ira_loop_tree_node_t parent;
2721
2722   FOR_EACH_ALLOCNO (a, ai)
2723     {
2724       int n = ALLOCNO_NUM_OBJECTS (a);
2725
2726       for (i = 0; i < n; i++)
2727         {
2728           ira_object_t obj = ALLOCNO_OBJECT (a, i);
2729           r = OBJECT_LIVE_RANGES (obj);
2730           if (r == NULL)
2731             continue;
2732           OBJECT_MAX (obj) = r->finish;
2733           for (; r->next != NULL; r = r->next)
2734             ;
2735           OBJECT_MIN (obj) = r->start;
2736         }
2737     }
2738   for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--)
2739     for (a = ira_regno_allocno_map[i];
2740          a != NULL;
2741          a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
2742       {
2743         int j;
2744         int n = ALLOCNO_NUM_OBJECTS (a);
2745
2746         for (j = 0; j < n; j++)
2747           {
2748             ira_object_t obj = ALLOCNO_OBJECT (a, j);
2749             ira_object_t parent_obj;
2750
2751             if (OBJECT_MAX (obj) < 0)
2752               continue;
2753             ira_assert (ALLOCNO_CAP_MEMBER (a) == NULL);
2754             /* Accumulation of range info.  */
2755             if (ALLOCNO_CAP (a) != NULL)
2756               {
2757                 for (cap = ALLOCNO_CAP (a); cap != NULL; cap = ALLOCNO_CAP (cap))
2758                   {
2759                     ira_object_t cap_obj = ALLOCNO_OBJECT (cap, j);
2760                     if (OBJECT_MAX (cap_obj) < OBJECT_MAX (obj))
2761                       OBJECT_MAX (cap_obj) = OBJECT_MAX (obj);
2762                     if (OBJECT_MIN (cap_obj) > OBJECT_MIN (obj))
2763                       OBJECT_MIN (cap_obj) = OBJECT_MIN (obj);
2764                   }
2765                 continue;
2766               }
2767             if ((parent = ALLOCNO_LOOP_TREE_NODE (a)->parent) == NULL)
2768               continue;
2769             parent_a = parent->regno_allocno_map[i];
2770             parent_obj = ALLOCNO_OBJECT (parent_a, j);
2771             if (OBJECT_MAX (parent_obj) < OBJECT_MAX (obj))
2772               OBJECT_MAX (parent_obj) = OBJECT_MAX (obj);
2773             if (OBJECT_MIN (parent_obj) > OBJECT_MIN (obj))
2774               OBJECT_MIN (parent_obj) = OBJECT_MIN (obj);
2775           }
2776       }
2777 #ifdef ENABLE_IRA_CHECKING
2778   FOR_EACH_OBJECT (obj, oi)
2779     {
2780       if ((0 <= OBJECT_MIN (obj) && OBJECT_MIN (obj) <= ira_max_point)
2781           && (0 <= OBJECT_MAX (obj) && OBJECT_MAX (obj) <= ira_max_point))
2782         continue;
2783       gcc_unreachable ();
2784     }
2785 #endif
2786 }
2787
2788 /* Sort allocnos according to their live ranges.  Allocnos with
2789    smaller allocno class are put first unless we use priority
2790    coloring.  Allocnos with the same class are ordered according
2791    their start (min).  Allocnos with the same start are ordered
2792    according their finish (max).  */
2793 static int
2794 object_range_compare_func (const void *v1p, const void *v2p)
2795 {
2796   int diff;
2797   ira_object_t obj1 = *(const ira_object_t *) v1p;
2798   ira_object_t obj2 = *(const ira_object_t *) v2p;
2799   ira_allocno_t a1 = OBJECT_ALLOCNO (obj1);
2800   ira_allocno_t a2 = OBJECT_ALLOCNO (obj2);
2801
2802   if ((diff = OBJECT_MIN (obj1) - OBJECT_MIN (obj2)) != 0)
2803     return diff;
2804   if ((diff = OBJECT_MAX (obj1) - OBJECT_MAX (obj2)) != 0)
2805      return diff;
2806   return ALLOCNO_NUM (a1) - ALLOCNO_NUM (a2);
2807 }
2808
2809 /* Sort ira_object_id_map and set up conflict id of allocnos.  */
2810 static void
2811 sort_conflict_id_map (void)
2812 {
2813   int i, num;
2814   ira_allocno_t a;
2815   ira_allocno_iterator ai;
2816
2817   num = 0;
2818   FOR_EACH_ALLOCNO (a, ai)
2819     {
2820       ira_allocno_object_iterator oi;
2821       ira_object_t obj;
2822
2823       FOR_EACH_ALLOCNO_OBJECT (a, obj, oi)
2824         ira_object_id_map[num++] = obj;
2825     }
2826   qsort (ira_object_id_map, num, sizeof (ira_object_t),
2827          object_range_compare_func);
2828   for (i = 0; i < num; i++)
2829     {
2830       ira_object_t obj = ira_object_id_map[i];
2831
2832       gcc_assert (obj != NULL);
2833       OBJECT_CONFLICT_ID (obj) = i;
2834     }
2835   for (i = num; i < ira_objects_num; i++)
2836     ira_object_id_map[i] = NULL;
2837 }
2838
2839 /* Set up minimal and maximal conflict ids of allocnos with which
2840    given allocno can conflict.  */
2841 static void
2842 setup_min_max_conflict_allocno_ids (void)
2843 {
2844   int aclass;
2845   int i, j, min, max, start, finish, first_not_finished, filled_area_start;
2846   int *live_range_min, *last_lived;
2847   int word0_min, word0_max;
2848   ira_allocno_t a;
2849   ira_allocno_iterator ai;
2850
2851   live_range_min = (int *) ira_allocate (sizeof (int) * ira_objects_num);
2852   aclass = -1;
2853   first_not_finished = -1;
2854   for (i = 0; i < ira_objects_num; i++)
2855     {
2856       ira_object_t obj = ira_object_id_map[i];
2857
2858       if (obj == NULL)
2859         continue;
2860
2861       a = OBJECT_ALLOCNO (obj);
2862
2863       if (aclass < 0)
2864         {
2865           aclass = ALLOCNO_CLASS (a);
2866           min = i;
2867           first_not_finished = i;
2868         }
2869       else
2870         {
2871           start = OBJECT_MIN (obj);
2872           /* If we skip an allocno, the allocno with smaller ids will
2873              be also skipped because of the secondary sorting the
2874              range finishes (see function
2875              object_range_compare_func).  */
2876           while (first_not_finished < i
2877                  && start > OBJECT_MAX (ira_object_id_map
2878                                         [first_not_finished]))
2879             first_not_finished++;
2880           min = first_not_finished;
2881         }
2882       if (min == i)
2883         /* We could increase min further in this case but it is good
2884            enough.  */
2885         min++;
2886       live_range_min[i] = OBJECT_MIN (obj);
2887       OBJECT_MIN (obj) = min;
2888     }
2889   last_lived = (int *) ira_allocate (sizeof (int) * ira_max_point);
2890   aclass = -1;
2891   filled_area_start = -1;
2892   for (i = ira_objects_num - 1; i >= 0; i--)
2893     {
2894       ira_object_t obj = ira_object_id_map[i];
2895
2896       if (obj == NULL)
2897         continue;
2898
2899       a = OBJECT_ALLOCNO (obj);
2900       if (aclass < 0)
2901         {
2902           aclass = ALLOCNO_CLASS (a);
2903           for (j = 0; j < ira_max_point; j++)
2904             last_lived[j] = -1;
2905           filled_area_start = ira_max_point;
2906         }
2907       min = live_range_min[i];
2908       finish = OBJECT_MAX (obj);
2909       max = last_lived[finish];
2910       if (max < 0)
2911         /* We could decrease max further in this case but it is good
2912            enough.  */
2913         max = OBJECT_CONFLICT_ID (obj) - 1;
2914       OBJECT_MAX (obj) = max;
2915       /* In filling, we can go further A range finish to recognize
2916          intersection quickly because if the finish of subsequently
2917          processed allocno (it has smaller conflict id) range is
2918          further A range finish than they are definitely intersected
2919          (the reason for this is the allocnos with bigger conflict id
2920          have their range starts not smaller than allocnos with
2921          smaller ids.  */
2922       for (j = min; j < filled_area_start; j++)
2923         last_lived[j] = i;
2924       filled_area_start = min;
2925     }
2926   ira_free (last_lived);
2927   ira_free (live_range_min);
2928
2929   /* For allocnos with more than one object, we may later record extra conflicts in
2930      subobject 0 that we cannot really know about here.
2931      For now, simply widen the min/max range of these subobjects.  */
2932
2933   word0_min = INT_MAX;
2934   word0_max = INT_MIN;
2935
2936   FOR_EACH_ALLOCNO (a, ai)
2937     {
2938       int n = ALLOCNO_NUM_OBJECTS (a);
2939       ira_object_t obj0;
2940
2941       if (n < 2)
2942         continue;
2943       obj0 = ALLOCNO_OBJECT (a, 0);
2944       if (OBJECT_CONFLICT_ID (obj0) < word0_min)
2945         word0_min = OBJECT_CONFLICT_ID (obj0);
2946       if (OBJECT_CONFLICT_ID (obj0) > word0_max)
2947         word0_max = OBJECT_CONFLICT_ID (obj0);
2948     }
2949   FOR_EACH_ALLOCNO (a, ai)
2950     {
2951       int n = ALLOCNO_NUM_OBJECTS (a);
2952       ira_object_t obj0;
2953
2954       if (n < 2)
2955         continue;
2956       obj0 = ALLOCNO_OBJECT (a, 0);
2957       if (OBJECT_MIN (obj0) > word0_min)
2958         OBJECT_MIN (obj0) = word0_min;
2959       if (OBJECT_MAX (obj0) < word0_max)
2960         OBJECT_MAX (obj0) = word0_max;
2961     }
2962 }
2963
2964 \f
2965
2966 static void
2967 create_caps (void)
2968 {
2969   ira_allocno_t a;
2970   ira_allocno_iterator ai;
2971   ira_loop_tree_node_t loop_tree_node;
2972
2973   FOR_EACH_ALLOCNO (a, ai)
2974     {
2975       if (ALLOCNO_LOOP_TREE_NODE (a) == ira_loop_tree_root)
2976         continue;
2977       if (ALLOCNO_CAP_MEMBER (a) != NULL)
2978         create_cap_allocno (a);
2979       else if (ALLOCNO_CAP (a) == NULL)
2980         {
2981           loop_tree_node = ALLOCNO_LOOP_TREE_NODE (a);
2982           if (!bitmap_bit_p (loop_tree_node->border_allocnos, ALLOCNO_NUM (a)))
2983             create_cap_allocno (a);
2984         }
2985     }
2986 }
2987
2988 \f
2989
2990 /* The page contains code transforming more one region internal
2991    representation (IR) to one region IR which is necessary for reload.
2992    This transformation is called IR flattening.  We might just rebuild
2993    the IR for one region but we don't do it because it takes a lot of
2994    time.  */
2995
2996 /* Map: regno -> allocnos which will finally represent the regno for
2997    IR with one region.  */
2998 static ira_allocno_t *regno_top_level_allocno_map;
2999
3000 /* Find the allocno that corresponds to A at a level one higher up in the
3001    loop tree.  Returns NULL if A is a cap, or if it has no parent.  */
3002 ira_allocno_t
3003 ira_parent_allocno (ira_allocno_t a)
3004 {
3005   ira_loop_tree_node_t parent;
3006
3007   if (ALLOCNO_CAP (a) != NULL)
3008     return NULL;
3009
3010   parent = ALLOCNO_LOOP_TREE_NODE (a)->parent;
3011   if (parent == NULL)
3012     return NULL;
3013
3014   return parent->regno_allocno_map[ALLOCNO_REGNO (a)];
3015 }
3016
3017 /* Find the allocno that corresponds to A at a level one higher up in the
3018    loop tree.  If ALLOCNO_CAP is set for A, return that.  */
3019 ira_allocno_t
3020 ira_parent_or_cap_allocno (ira_allocno_t a)
3021 {
3022   if (ALLOCNO_CAP (a) != NULL)
3023     return ALLOCNO_CAP (a);
3024
3025   return ira_parent_allocno (a);
3026 }
3027
3028 /* Process all allocnos originated from pseudo REGNO and copy live
3029    ranges, hard reg conflicts, and allocno stack reg attributes from
3030    low level allocnos to final allocnos which are destinations of
3031    removed stores at a loop exit.  Return true if we copied live
3032    ranges.  */
3033 static bool
3034 copy_info_to_removed_store_destinations (int regno)
3035 {
3036   ira_allocno_t a;
3037   ira_allocno_t parent_a = NULL;
3038   ira_loop_tree_node_t parent;
3039   bool merged_p;
3040
3041   merged_p = false;
3042   for (a = ira_regno_allocno_map[regno];
3043        a != NULL;
3044        a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
3045     {
3046       if (a != regno_top_level_allocno_map[REGNO (allocno_emit_reg (a))])
3047         /* This allocno will be removed.  */
3048         continue;
3049
3050       /* Caps will be removed.  */
3051       ira_assert (ALLOCNO_CAP_MEMBER (a) == NULL);
3052       for (parent = ALLOCNO_LOOP_TREE_NODE (a)->parent;
3053            parent != NULL;
3054            parent = parent->parent)
3055         if ((parent_a = parent->regno_allocno_map[regno]) == NULL
3056             || (parent_a
3057                 == regno_top_level_allocno_map[REGNO
3058                                                (allocno_emit_reg (parent_a))]
3059                 && ALLOCNO_EMIT_DATA (parent_a)->mem_optimized_dest_p))
3060           break;
3061       if (parent == NULL || parent_a == NULL)
3062         continue;
3063
3064       copy_allocno_live_ranges (a, parent_a);
3065       merge_hard_reg_conflicts (a, parent_a, true);
3066
3067       ALLOCNO_CALL_FREQ (parent_a) += ALLOCNO_CALL_FREQ (a);
3068       ALLOCNO_CALLS_CROSSED_NUM (parent_a)
3069         += ALLOCNO_CALLS_CROSSED_NUM (a);
3070       ALLOCNO_CHEAP_CALLS_CROSSED_NUM (parent_a)
3071         += ALLOCNO_CHEAP_CALLS_CROSSED_NUM (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 }