gcc/ira-build.c

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