gcc/ira-build.c

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