gcc/ira-build.c

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