gcc/ira-build.c

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