gcc/ira-build.c

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