gcc/ira-build.c

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