gcc/ira-build.c

   1 /* Building internal representation for IRA.
   2    Copyright (C) 2006, 2007, 2008, 2009, 2010
   3    Free Software Foundation, Inc.
   4    Contributed by Vladimir Makarov <vmakarov@redhat.com>.
   5
   6 This file is part of GCC.
   7
   8 GCC is free software; you can redistribute it and/or modify it under
   9 the terms of the GNU General Public License as published by the Free
  10 Software Foundation; either version 3, or (at your option) any later
  11 version.
  12
  13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  15 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  16 for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with GCC; see the file COPYING3.  If not see
  20 <http://www.gnu.org/licenses/>.  */
  21
  22 #include "config.h"
  23 #include "system.h"
  24 #include "coretypes.h"
  25 #include "tm.h"
  26 #include "rtl.h"
  27 #include "tm_p.h"
  28 #include "target.h"
  29 #include "regs.h"
  30 #include "flags.h"
  31 #include "hard-reg-set.h"
  32 #include "basic-block.h"
  33 #include "insn-config.h"
  34 #include "recog.h"
  35 #include "toplev.h"
  36 #include "params.h"
  37 #include "df.h"
  38 #include "output.h"
  39 #include "reload.h"
  40 #include "sparseset.h"
  41 #include "ira-int.h"
  42 #include "emit-rtl.h"  /* FIXME: Can go away once crtl is moved to rtl.h.  */
  43
  44 static ira_copy_t find_allocno_copy (ira_allocno_t, ira_allocno_t, rtx,
  45                                      ira_loop_tree_node_t);
  46
  47 /* The root of the loop tree corresponding to the all function.  */
  48 ira_loop_tree_node_t ira_loop_tree_root;
  49
  50 /* Height of the loop tree.  */
  51 int ira_loop_tree_height;
  52
  53 /* All nodes representing basic blocks are referred through the
  54    following array.  We can not use basic block member `aux' for this
  55    because it is used for insertion of insns on edges.  */
  56 ira_loop_tree_node_t ira_bb_nodes;
  57
  58 /* All nodes representing loops are referred through the following
  59    array.  */
  60 ira_loop_tree_node_t ira_loop_nodes;
  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 /* Map conflict id -> allocno with given conflict id (see comments for
  75    allocno member `conflict_id').  */
  76 ira_allocno_t *ira_conflict_id_allocno_map;
  77
  78 /* Array of references to all copies.  The order number of the copy
  79    corresponds to the index in the array.  Removed copies have NULL
  80    element value.  */
  81 ira_copy_t *ira_copies;
  82
  83 /* Size of the previous array.  */
  84 int ira_copies_num;
  85
  86 \f
  87
  88 /* LAST_BASIC_BLOCK before generating additional insns because of live
  89    range splitting.  Emitting insns on a critical edge creates a new
  90    basic block.  */
  91 static int last_basic_block_before_change;
  92
  93 /* The following function allocates the loop tree nodes.  If LOOPS_P
  94    is FALSE, the nodes corresponding to the loops (except the root
  95    which corresponds the all function) will be not allocated but nodes
  96    will still be allocated for basic blocks.  */
  97 static void
  98 create_loop_tree_nodes (bool loops_p)
  99 {
 100   unsigned int i, j;
 101   int max_regno;
 102   bool skip_p;
 103   edge_iterator ei;
 104   edge e;
 105   VEC (edge, heap) *edges;
 106   loop_p loop;
 107
 108   ira_bb_nodes
 109     = ((struct ira_loop_tree_node *)
 110        ira_allocate (sizeof (struct ira_loop_tree_node) * last_basic_block));
 111   last_basic_block_before_change = last_basic_block;
 112   for (i = 0; i < (unsigned int) last_basic_block; i++)
 113     {
 114       ira_bb_nodes[i].regno_allocno_map = NULL;
 115       memset (ira_bb_nodes[i].reg_pressure, 0,
 116               sizeof (ira_bb_nodes[i].reg_pressure));
 117       ira_bb_nodes[i].all_allocnos = NULL;
 118       ira_bb_nodes[i].modified_regnos = NULL;
 119       ira_bb_nodes[i].border_allocnos = NULL;
 120       ira_bb_nodes[i].local_copies = NULL;
 121     }
 122   ira_loop_nodes = ((struct ira_loop_tree_node *)
 123                     ira_allocate (sizeof (struct ira_loop_tree_node)
 124                                   * VEC_length (loop_p, ira_loops.larray)));
 125   max_regno = max_reg_num ();
 126   for (i = 0; VEC_iterate (loop_p, ira_loops.larray, i, loop); i++)
 127     {
 128       if (loop != ira_loops.tree_root)
 129         {
 130           ira_loop_nodes[i].regno_allocno_map = NULL;
 131           if (! loops_p)
 132             continue;
 133           skip_p = false;
 134           FOR_EACH_EDGE (e, ei, loop->header->preds)
 135             if (e->src != loop->latch
 136                 && (e->flags & EDGE_ABNORMAL) && EDGE_CRITICAL_P (e))
 137               {
 138                 skip_p = true;
 139                 break;
 140               }
 141           if (skip_p)
 142             continue;
 143           edges = get_loop_exit_edges (loop);
 144           for (j = 0; VEC_iterate (edge, edges, j, e); j++)
 145             if ((e->flags & EDGE_ABNORMAL) && EDGE_CRITICAL_P (e))
 146               {
 147                 skip_p = true;
 148                 break;
 149               }
 150           VEC_free (edge, heap, edges);
 151           if (skip_p)
 152             continue;
 153         }
 154       ira_loop_nodes[i].regno_allocno_map
 155         = (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t) * max_regno);
 156       memset (ira_loop_nodes[i].regno_allocno_map, 0,
 157               sizeof (ira_allocno_t) * max_regno);
 158       memset (ira_loop_nodes[i].reg_pressure, 0,
 159               sizeof (ira_loop_nodes[i].reg_pressure));
 160       ira_loop_nodes[i].all_allocnos = ira_allocate_bitmap ();
 161       ira_loop_nodes[i].modified_regnos = ira_allocate_bitmap ();
 162       ira_loop_nodes[i].border_allocnos = ira_allocate_bitmap ();
 163       ira_loop_nodes[i].local_copies = ira_allocate_bitmap ();
 164     }
 165 }
 166
 167 /* The function returns TRUE if there are more one allocation
 168    region.  */
 169 static bool
 170 more_one_region_p (void)
 171 {
 172   unsigned int i;
 173   loop_p loop;
 174
 175   for (i = 0; VEC_iterate (loop_p, ira_loops.larray, i, loop); i++)
 176     if (ira_loop_nodes[i].regno_allocno_map != NULL
 177         && ira_loop_tree_root != &ira_loop_nodes[i])
 178       return true;
 179   return false;
 180 }
 181
 182 /* Free the loop tree node of a loop.  */
 183 static void
 184 finish_loop_tree_node (ira_loop_tree_node_t loop)
 185 {
 186   if (loop->regno_allocno_map != NULL)
 187     {
 188       ira_assert (loop->bb == NULL);
 189       ira_free_bitmap (loop->local_copies);
 190       ira_free_bitmap (loop->border_allocnos);
 191       ira_free_bitmap (loop->modified_regnos);
 192       ira_free_bitmap (loop->all_allocnos);
 193       ira_free (loop->regno_allocno_map);
 194       loop->regno_allocno_map = NULL;
 195     }
 196 }
 197
 198 /* Free the loop tree nodes.  */
 199 static void
 200 finish_loop_tree_nodes (void)
 201 {
 202   unsigned int i;
 203   loop_p loop;
 204
 205   for (i = 0; VEC_iterate (loop_p, ira_loops.larray, i, loop); i++)
 206     finish_loop_tree_node (&ira_loop_nodes[i]);
 207   ira_free (ira_loop_nodes);
 208   for (i = 0; i < (unsigned int) last_basic_block_before_change; i++)
 209     {
 210       if (ira_bb_nodes[i].local_copies != NULL)
 211         ira_free_bitmap (ira_bb_nodes[i].local_copies);
 212       if (ira_bb_nodes[i].border_allocnos != NULL)
 213         ira_free_bitmap (ira_bb_nodes[i].border_allocnos);
 214       if (ira_bb_nodes[i].modified_regnos != NULL)
 215         ira_free_bitmap (ira_bb_nodes[i].modified_regnos);
 216       if (ira_bb_nodes[i].all_allocnos != NULL)
 217         ira_free_bitmap (ira_bb_nodes[i].all_allocnos);
 218       if (ira_bb_nodes[i].regno_allocno_map != NULL)
 219         ira_free (ira_bb_nodes[i].regno_allocno_map);
 220     }
 221   ira_free (ira_bb_nodes);
 222 }
 223
 224 \f
 225
 226 /* The following recursive function adds LOOP to the loop tree
 227    hierarchy.  LOOP is added only once.  */
 228 static void
 229 add_loop_to_tree (struct loop *loop)
 230 {
 231   struct loop *parent;
 232   ira_loop_tree_node_t loop_node, parent_node;
 233
 234   /* We can not use loop node access macros here because of potential
 235      checking and because the nodes are not initialized enough
 236      yet.  */
 237   if (loop_outer (loop) != NULL)
 238     add_loop_to_tree (loop_outer (loop));
 239   if (ira_loop_nodes[loop->num].regno_allocno_map != NULL
 240       && ira_loop_nodes[loop->num].children == NULL)
 241     {
 242       /* We have not added loop node to the tree yet.  */
 243       loop_node = &ira_loop_nodes[loop->num];
 244       loop_node->loop = loop;
 245       loop_node->bb = NULL;
 246       for (parent = loop_outer (loop);
 247            parent != NULL;
 248            parent = loop_outer (parent))
 249         if (ira_loop_nodes[parent->num].regno_allocno_map != NULL)
 250           break;
 251       if (parent == NULL)
 252         {
 253           loop_node->next = NULL;
 254           loop_node->subloop_next = NULL;
 255           loop_node->parent = NULL;
 256         }
 257       else
 258         {
 259           parent_node = &ira_loop_nodes[parent->num];
 260           loop_node->next = parent_node->children;
 261           parent_node->children = loop_node;
 262           loop_node->subloop_next = parent_node->subloops;
 263           parent_node->subloops = loop_node;
 264           loop_node->parent = parent_node;
 265         }
 266     }
 267 }
 268
 269 /* The following recursive function sets up levels of nodes of the
 270    tree given its root LOOP_NODE.  The enumeration starts with LEVEL.
 271    The function returns maximal value of level in the tree + 1.  */
 272 static int
 273 setup_loop_tree_level (ira_loop_tree_node_t loop_node, int level)
 274 {
 275   int height, max_height;
 276   ira_loop_tree_node_t subloop_node;
 277
 278   ira_assert (loop_node->bb == NULL);
 279   loop_node->level = level;
 280   max_height = level + 1;
 281   for (subloop_node = loop_node->subloops;
 282        subloop_node != NULL;
 283        subloop_node = subloop_node->subloop_next)
 284     {
 285       ira_assert (subloop_node->bb == NULL);
 286       height = setup_loop_tree_level (subloop_node, level + 1);
 287       if (height > max_height)
 288         max_height = height;
 289     }
 290   return max_height;
 291 }
 292
 293 /* Create the loop tree.  The algorithm is designed to provide correct
 294    order of loops (they are ordered by their last loop BB) and basic
 295    blocks in the chain formed by member next.  */
 296 static void
 297 form_loop_tree (void)
 298 {
 299   unsigned int i;
 300   basic_block bb;
 301   struct loop *parent;
 302   ira_loop_tree_node_t bb_node, loop_node;
 303   loop_p loop;
 304
 305   /* We can not use loop/bb node access macros because of potential
 306      checking and because the nodes are not initialized enough
 307      yet.  */
 308   for (i = 0; VEC_iterate (loop_p, ira_loops.larray, i, loop); i++)
 309      if (ira_loop_nodes[i].regno_allocno_map != NULL)
 310        {
 311          ira_loop_nodes[i].children = NULL;
 312          ira_loop_nodes[i].subloops = NULL;
 313        }
 314   FOR_EACH_BB (bb)
 315     {
 316       bb_node = &ira_bb_nodes[bb->index];
 317       bb_node->bb = bb;
 318       bb_node->loop = NULL;
 319       bb_node->subloops = NULL;
 320       bb_node->children = NULL;
 321       bb_node->subloop_next = NULL;
 322       bb_node->next = NULL;
 323       for (parent = bb->loop_father;
 324            parent != NULL;
 325            parent = loop_outer (parent))
 326         if (ira_loop_nodes[parent->num].regno_allocno_map != NULL)
 327           break;
 328       add_loop_to_tree (parent);
 329       loop_node = &ira_loop_nodes[parent->num];
 330       bb_node->next = loop_node->children;
 331       bb_node->parent = loop_node;
 332       loop_node->children = bb_node;
 333     }
 334   ira_loop_tree_root = IRA_LOOP_NODE_BY_INDEX (ira_loops.tree_root->num);
 335   ira_loop_tree_height = setup_loop_tree_level (ira_loop_tree_root, 0);
 336   ira_assert (ira_loop_tree_root->regno_allocno_map != NULL);
 337 }
 338
 339 \f
 340
 341 /* Rebuild IRA_REGNO_ALLOCNO_MAP and REGNO_ALLOCNO_MAPs of the loop
 342    tree nodes.  */
 343 static void
 344 rebuild_regno_allocno_maps (void)
 345 {
 346   unsigned int l;
 347   int max_regno, regno;
 348   ira_allocno_t a;
 349   ira_loop_tree_node_t loop_tree_node;
 350   loop_p loop;
 351   ira_allocno_iterator ai;
 352
 353   max_regno = max_reg_num ();
 354   for (l = 0; VEC_iterate (loop_p, ira_loops.larray, l, loop); l++)
 355     if (ira_loop_nodes[l].regno_allocno_map != NULL)
 356       {
 357         ira_free (ira_loop_nodes[l].regno_allocno_map);
 358         ira_loop_nodes[l].regno_allocno_map
 359           = (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t)
 360                                             * max_regno);
 361         memset (ira_loop_nodes[l].regno_allocno_map, 0,
 362                 sizeof (ira_allocno_t) * max_regno);
 363       }
 364   ira_free (ira_regno_allocno_map);
 365   ira_regno_allocno_map
 366     = (ira_allocno_t *) ira_allocate (max_regno * sizeof (ira_allocno_t));
 367   memset (ira_regno_allocno_map, 0, max_regno * sizeof (ira_allocno_t));
 368   FOR_EACH_ALLOCNO (a, ai)
 369     {
 370       if (ALLOCNO_CAP_MEMBER (a) != NULL)
 371         /* Caps are not in the regno allocno maps.  */
 372         continue;
 373       regno = ALLOCNO_REGNO (a);
 374       loop_tree_node = ALLOCNO_LOOP_TREE_NODE (a);
 375       ALLOCNO_NEXT_REGNO_ALLOCNO (a) = ira_regno_allocno_map[regno];
 376       ira_regno_allocno_map[regno] = a;
 377       if (loop_tree_node->regno_allocno_map[regno] == NULL)
 378         /* Remember that we can create temporary allocnos to break
 379            cycles in register shuffle.  */
 380         loop_tree_node->regno_allocno_map[regno] = a;
 381     }
 382 }
 383
 384 \f
 385
 386 /* Pools for allocnos and allocno live ranges.  */
 387 static alloc_pool allocno_pool, allocno_live_range_pool;
 388
 389 /* Vec containing references to all created allocnos.  It is a
 390    container of array allocnos.  */
 391 static VEC(ira_allocno_t,heap) *allocno_vec;
 392
 393 /* Vec containing references to all created allocnos.  It is a
 394    container of ira_conflict_id_allocno_map.  */
 395 static VEC(ira_allocno_t,heap) *ira_conflict_id_allocno_map_vec;
 396
 397 /* Initialize data concerning allocnos.  */
 398 static void
 399 initiate_allocnos (void)
 400 {
 401   allocno_live_range_pool
 402     = create_alloc_pool ("allocno live ranges",
 403                          sizeof (struct ira_allocno_live_range), 100);
 404   allocno_pool
 405     = create_alloc_pool ("allocnos", sizeof (struct ira_allocno), 100);
 406   allocno_vec = VEC_alloc (ira_allocno_t, heap, max_reg_num () * 2);
 407   ira_allocnos = NULL;
 408   ira_allocnos_num = 0;
 409   ira_conflict_id_allocno_map_vec
 410     = VEC_alloc (ira_allocno_t, heap, max_reg_num () * 2);
 411   ira_conflict_id_allocno_map = NULL;
 412   ira_regno_allocno_map
 413     = (ira_allocno_t *) ira_allocate (max_reg_num () * sizeof (ira_allocno_t));
 414   memset (ira_regno_allocno_map, 0, max_reg_num () * sizeof (ira_allocno_t));
 415 }
 416
 417 /* Create and return the allocno corresponding to REGNO in
 418    LOOP_TREE_NODE.  Add the allocno to the list of allocnos with the
 419    same regno if CAP_P is FALSE.  */
 420 ira_allocno_t
 421 ira_create_allocno (int regno, bool cap_p, ira_loop_tree_node_t loop_tree_node)
 422 {
 423   ira_allocno_t a;
 424
 425   a = (ira_allocno_t) pool_alloc (allocno_pool);
 426   ALLOCNO_REGNO (a) = regno;
 427   ALLOCNO_LOOP_TREE_NODE (a) = loop_tree_node;
 428   if (! cap_p)
 429     {
 430       ALLOCNO_NEXT_REGNO_ALLOCNO (a) = ira_regno_allocno_map[regno];
 431       ira_regno_allocno_map[regno] = a;
 432       if (loop_tree_node->regno_allocno_map[regno] == NULL)
 433         /* Remember that we can create temporary allocnos to break
 434            cycles in register shuffle on region borders (see
 435            ira-emit.c).  */
 436         loop_tree_node->regno_allocno_map[regno] = a;
 437     }
 438   ALLOCNO_CAP (a) = NULL;
 439   ALLOCNO_CAP_MEMBER (a) = NULL;
 440   ALLOCNO_NUM (a) = ira_allocnos_num;
 441   bitmap_set_bit (loop_tree_node->all_allocnos, ALLOCNO_NUM (a));
 442   ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a) = NULL;
 443   ALLOCNO_CONFLICT_ALLOCNOS_NUM (a) = 0;
 444   COPY_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (a), ira_no_alloc_regs);
 445   COPY_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a), ira_no_alloc_regs);
 446   ALLOCNO_NREFS (a) = 0;
 447   ALLOCNO_FREQ (a) = 0;
 448   ALLOCNO_HARD_REGNO (a) = -1;
 449   ALLOCNO_CALL_FREQ (a) = 0;
 450   ALLOCNO_CALLS_CROSSED_NUM (a) = 0;
 451 #ifdef STACK_REGS
 452   ALLOCNO_NO_STACK_REG_P (a) = false;
 453   ALLOCNO_TOTAL_NO_STACK_REG_P (a) = false;
 454 #endif
 455   ALLOCNO_MEM_OPTIMIZED_DEST (a) = NULL;
 456   ALLOCNO_MEM_OPTIMIZED_DEST_P (a) = false;
 457   ALLOCNO_SOMEWHERE_RENAMED_P (a) = false;
 458   ALLOCNO_CHILD_RENAMED_P (a) = false;
 459   ALLOCNO_DONT_REASSIGN_P (a) = false;
 460   ALLOCNO_BAD_SPILL_P (a) = false;
 461   ALLOCNO_IN_GRAPH_P (a) = false;
 462   ALLOCNO_ASSIGNED_P (a) = false;
 463   ALLOCNO_MAY_BE_SPILLED_P (a) = false;
 464   ALLOCNO_SPLAY_REMOVED_P (a) = false;
 465   ALLOCNO_CONFLICT_VEC_P (a) = false;
 466   ALLOCNO_MODE (a) = (regno < 0 ? VOIDmode : PSEUDO_REGNO_MODE (regno));
 467   ALLOCNO_COPIES (a) = NULL;
 468   ALLOCNO_HARD_REG_COSTS (a) = NULL;
 469   ALLOCNO_CONFLICT_HARD_REG_COSTS (a) = NULL;
 470   ALLOCNO_UPDATED_HARD_REG_COSTS (a) = NULL;
 471   ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) = NULL;
 472   ALLOCNO_LEFT_CONFLICTS_SIZE (a) = -1;
 473   ALLOCNO_COVER_CLASS (a) = NO_REGS;
 474   ALLOCNO_UPDATED_COVER_CLASS_COST (a) = 0;
 475   ALLOCNO_COVER_CLASS_COST (a) = 0;
 476   ALLOCNO_MEMORY_COST (a) = 0;
 477   ALLOCNO_UPDATED_MEMORY_COST (a) = 0;
 478   ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a) = 0;
 479   ALLOCNO_NEXT_BUCKET_ALLOCNO (a) = NULL;
 480   ALLOCNO_PREV_BUCKET_ALLOCNO (a) = NULL;
 481   ALLOCNO_FIRST_COALESCED_ALLOCNO (a) = a;
 482   ALLOCNO_NEXT_COALESCED_ALLOCNO (a) = a;
 483   ALLOCNO_LIVE_RANGES (a) = NULL;
 484   ALLOCNO_MIN (a) = INT_MAX;
 485   ALLOCNO_MAX (a) = -1;
 486   ALLOCNO_CONFLICT_ID (a) = ira_allocnos_num;
 487   VEC_safe_push (ira_allocno_t, heap, allocno_vec, a);
 488   ira_allocnos = VEC_address (ira_allocno_t, allocno_vec);
 489   ira_allocnos_num = VEC_length (ira_allocno_t, allocno_vec);
 490   VEC_safe_push (ira_allocno_t, heap, ira_conflict_id_allocno_map_vec, a);
 491   ira_conflict_id_allocno_map
 492     = VEC_address (ira_allocno_t, ira_conflict_id_allocno_map_vec);
 493   return a;
 494 }
 495
 496 /* Set up cover class for A and update its conflict hard registers.  */
 497 void
 498 ira_set_allocno_cover_class (ira_allocno_t a, enum reg_class cover_class)
 499 {
 500   ALLOCNO_COVER_CLASS (a) = cover_class;
 501   IOR_COMPL_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (a),
 502                           reg_class_contents[cover_class]);
 503   IOR_COMPL_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a),
 504                           reg_class_contents[cover_class]);
 505 }
 506
 507 /* Merge hard register conflicts from allocno FROM into allocno TO.  If
 508    TOTAL_ONLY is true, we ignore ALLOCNO_CONFLICT_HARD_REGS.  */
 509 static void
 510 merge_hard_reg_conflicts (ira_allocno_t from, ira_allocno_t to,
 511                           bool total_only)
 512 {
 513   if (!total_only)
 514     IOR_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (to),
 515                       ALLOCNO_CONFLICT_HARD_REGS (from));
 516   IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (to),
 517                     ALLOCNO_TOTAL_CONFLICT_HARD_REGS (from));
 518 #ifdef STACK_REGS
 519   if (!total_only && ALLOCNO_NO_STACK_REG_P (from))
 520     ALLOCNO_NO_STACK_REG_P (to) = true;
 521   if (ALLOCNO_TOTAL_NO_STACK_REG_P (from))
 522     ALLOCNO_TOTAL_NO_STACK_REG_P (to) = true;
 523 #endif
 524 }
 525
 526 /* Return TRUE if the conflict vector with NUM elements is more
 527    profitable than conflict bit vector for A.  */
 528 bool
 529 ira_conflict_vector_profitable_p (ira_allocno_t a, int num)
 530 {
 531   int nw;
 532
 533   if (ALLOCNO_MAX (a) < ALLOCNO_MIN (a))
 534     /* We prefer bit vector in such case because it does not result in
 535        allocation.  */
 536     return false;
 537
 538   nw = (ALLOCNO_MAX (a) - ALLOCNO_MIN (a) + IRA_INT_BITS) / IRA_INT_BITS;
 539   return (2 * sizeof (ira_allocno_t) * (num + 1)
 540           < 3 * nw * sizeof (IRA_INT_TYPE));
 541 }
 542
 543 /* Allocates and initialize the conflict vector of A for NUM
 544    conflicting allocnos.  */
 545 void
 546 ira_allocate_allocno_conflict_vec (ira_allocno_t a, int num)
 547 {
 548   int size;
 549   ira_allocno_t *vec;
 550
 551   ira_assert (ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a) == NULL);
 552   num++; /* for NULL end marker  */
 553   size = sizeof (ira_allocno_t) * num;
 554   ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a) = ira_allocate (size);
 555   vec = (ira_allocno_t *) ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a);
 556   vec[0] = NULL;
 557   ALLOCNO_CONFLICT_ALLOCNOS_NUM (a) = 0;
 558   ALLOCNO_CONFLICT_ALLOCNO_ARRAY_SIZE (a) = size;
 559   ALLOCNO_CONFLICT_VEC_P (a) = true;
 560 }
 561
 562 /* Allocate and initialize the conflict bit vector of A.  */
 563 static void
 564 allocate_allocno_conflict_bit_vec (ira_allocno_t a)
 565 {
 566   unsigned int size;
 567
 568   ira_assert (ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a) == NULL);
 569   size = ((ALLOCNO_MAX (a) - ALLOCNO_MIN (a) + IRA_INT_BITS)
 570           / IRA_INT_BITS * sizeof (IRA_INT_TYPE));
 571   ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a) = ira_allocate (size);
 572   memset (ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a), 0, size);
 573   ALLOCNO_CONFLICT_ALLOCNO_ARRAY_SIZE (a) = size;
 574   ALLOCNO_CONFLICT_VEC_P (a) = false;
 575 }
 576
 577 /* Allocate and initialize the conflict vector or conflict bit vector
 578    of A for NUM conflicting allocnos whatever is more profitable.  */
 579 void
 580 ira_allocate_allocno_conflicts (ira_allocno_t a, int num)
 581 {
 582   if (ira_conflict_vector_profitable_p (a, num))
 583     ira_allocate_allocno_conflict_vec (a, num);
 584   else
 585     allocate_allocno_conflict_bit_vec (a);
 586 }
 587
 588 /* Add A2 to the conflicts of A1.  */
 589 static void
 590 add_to_allocno_conflicts (ira_allocno_t a1, ira_allocno_t a2)
 591 {
 592   int num;
 593   unsigned int size;
 594
 595   if (ALLOCNO_CONFLICT_VEC_P (a1))
 596     {
 597       ira_allocno_t *vec;
 598
 599       num = ALLOCNO_CONFLICT_ALLOCNOS_NUM (a1) + 2;
 600       if (ALLOCNO_CONFLICT_ALLOCNO_ARRAY_SIZE (a1)
 601           >=  num * sizeof (ira_allocno_t))
 602         vec = (ira_allocno_t *) ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a1);
 603       else
 604         {
 605           size = (3 * num / 2 + 1) * sizeof (ira_allocno_t);
 606           vec = (ira_allocno_t *) ira_allocate (size);
 607           memcpy (vec, ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a1),
 608                   sizeof (ira_allocno_t) * ALLOCNO_CONFLICT_ALLOCNOS_NUM (a1));
 609           ira_free (ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a1));
 610           ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a1) = vec;
 611           ALLOCNO_CONFLICT_ALLOCNO_ARRAY_SIZE (a1) = size;
 612         }
 613       vec[num - 2] = a2;
 614       vec[num - 1] = NULL;
 615       ALLOCNO_CONFLICT_ALLOCNOS_NUM (a1)++;
 616     }
 617   else
 618     {
 619       int nw, added_head_nw, id;
 620       IRA_INT_TYPE *vec;
 621
 622       id = ALLOCNO_CONFLICT_ID (a2);
 623       vec = (IRA_INT_TYPE *) ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a1);
 624       if (ALLOCNO_MIN (a1) > id)
 625         {
 626           /* Expand head of the bit vector.  */
 627           added_head_nw = (ALLOCNO_MIN (a1) - id - 1) / IRA_INT_BITS + 1;
 628           nw = (ALLOCNO_MAX (a1) - ALLOCNO_MIN (a1)) / IRA_INT_BITS + 1;
 629           size = (nw + added_head_nw) * sizeof (IRA_INT_TYPE);
 630           if (ALLOCNO_CONFLICT_ALLOCNO_ARRAY_SIZE (a1) >= size)
 631             {
 632               memmove ((char *) vec + added_head_nw * sizeof (IRA_INT_TYPE),
 633                        vec, nw * sizeof (IRA_INT_TYPE));
 634               memset (vec, 0, added_head_nw * sizeof (IRA_INT_TYPE));
 635             }
 636           else
 637             {
 638               size
 639                 = (3 * (nw + added_head_nw) / 2 + 1) * sizeof (IRA_INT_TYPE);
 640               vec = (IRA_INT_TYPE *) ira_allocate (size);
 641               memcpy ((char *) vec + added_head_nw * sizeof (IRA_INT_TYPE),
 642                       ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a1),
 643                       nw * sizeof (IRA_INT_TYPE));
 644               memset (vec, 0, added_head_nw * sizeof (IRA_INT_TYPE));
 645               memset ((char *) vec
 646                       + (nw + added_head_nw) * sizeof (IRA_INT_TYPE),
 647                       0, size - (nw + added_head_nw) * sizeof (IRA_INT_TYPE));
 648               ira_free (ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a1));
 649               ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a1) = vec;
 650               ALLOCNO_CONFLICT_ALLOCNO_ARRAY_SIZE (a1) = size;
 651             }
 652           ALLOCNO_MIN (a1) -= added_head_nw * IRA_INT_BITS;
 653         }
 654       else if (ALLOCNO_MAX (a1) < id)
 655         {
 656           nw = (id - ALLOCNO_MIN (a1)) / IRA_INT_BITS + 1;
 657           size = nw * sizeof (IRA_INT_TYPE);
 658           if (ALLOCNO_CONFLICT_ALLOCNO_ARRAY_SIZE (a1) < size)
 659             {
 660               /* Expand tail of the bit vector.  */
 661               size = (3 * nw / 2 + 1) * sizeof (IRA_INT_TYPE);
 662               vec = (IRA_INT_TYPE *) ira_allocate (size);
 663               memcpy (vec, ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a1),
 664                       ALLOCNO_CONFLICT_ALLOCNO_ARRAY_SIZE (a1));
 665               memset ((char *) vec + ALLOCNO_CONFLICT_ALLOCNO_ARRAY_SIZE (a1),
 666                       0, size - ALLOCNO_CONFLICT_ALLOCNO_ARRAY_SIZE (a1));
 667               ira_free (ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a1));
 668               ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a1) = vec;
 669               ALLOCNO_CONFLICT_ALLOCNO_ARRAY_SIZE (a1) = size;
 670             }
 671           ALLOCNO_MAX (a1) = id;
 672         }
 673       SET_ALLOCNO_SET_BIT (vec, id, ALLOCNO_MIN (a1), ALLOCNO_MAX (a1));
 674     }
 675 }
 676
 677 /* Add A1 to the conflicts of A2 and vise versa.  */
 678 void
 679 ira_add_allocno_conflict (ira_allocno_t a1, ira_allocno_t a2)
 680 {
 681   add_to_allocno_conflicts (a1, a2);
 682   add_to_allocno_conflicts (a2, a1);
 683 }
 684
 685 /* Clear all conflicts of allocno A.  */
 686 static void
 687 clear_allocno_conflicts (ira_allocno_t a)
 688 {
 689   if (ALLOCNO_CONFLICT_VEC_P (a))
 690     {
 691       ALLOCNO_CONFLICT_ALLOCNOS_NUM (a) = 0;
 692       ((ira_allocno_t *) ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a))[0] = NULL;
 693     }
 694   else if (ALLOCNO_CONFLICT_ALLOCNO_ARRAY_SIZE (a) != 0)
 695     {
 696       int nw;
 697
 698       nw = (ALLOCNO_MAX (a) - ALLOCNO_MIN (a)) / IRA_INT_BITS + 1;
 699       memset (ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a), 0,
 700               nw * sizeof (IRA_INT_TYPE));
 701     }
 702 }
 703
 704 /* The array used to find duplications in conflict vectors of
 705    allocnos.  */
 706 static int *allocno_conflict_check;
 707
 708 /* The value used to mark allocation presence in conflict vector of
 709    the current allocno.  */
 710 static int curr_allocno_conflict_check_tick;
 711
 712 /* Remove duplications in conflict vector of A.  */
 713 static void
 714 compress_allocno_conflict_vec (ira_allocno_t a)
 715 {
 716   ira_allocno_t *vec, conflict_a;
 717   int i, j;
 718
 719   ira_assert (ALLOCNO_CONFLICT_VEC_P (a));
 720   vec = (ira_allocno_t *) ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a);
 721   curr_allocno_conflict_check_tick++;
 722   for (i = j = 0; (conflict_a = vec[i]) != NULL; i++)
 723     {
 724       if (allocno_conflict_check[ALLOCNO_NUM (conflict_a)]
 725           != curr_allocno_conflict_check_tick)
 726         {
 727           allocno_conflict_check[ALLOCNO_NUM (conflict_a)]
 728             = curr_allocno_conflict_check_tick;
 729           vec[j++] = conflict_a;
 730         }
 731     }
 732   ALLOCNO_CONFLICT_ALLOCNOS_NUM (a) = j;
 733   vec[j] = NULL;
 734 }
 735
 736 /* Remove duplications in conflict vectors of all allocnos.  */
 737 static void
 738 compress_conflict_vecs (void)
 739 {
 740   ira_allocno_t a;
 741   ira_allocno_iterator ai;
 742
 743   allocno_conflict_check
 744     = (int *) ira_allocate (sizeof (int) * ira_allocnos_num);
 745   memset (allocno_conflict_check, 0, sizeof (int) * ira_allocnos_num);
 746   curr_allocno_conflict_check_tick = 0;
 747   FOR_EACH_ALLOCNO (a, ai)
 748     if (ALLOCNO_CONFLICT_VEC_P (a))
 749       compress_allocno_conflict_vec (a);
 750   ira_free (allocno_conflict_check);
 751 }
 752
 753 /* This recursive function outputs allocno A and if it is a cap the
 754    function outputs its members.  */
 755 void
 756 ira_print_expanded_allocno (ira_allocno_t a)
 757 {
 758   basic_block bb;
 759
 760   fprintf (ira_dump_file, " a%d(r%d", ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
 761   if ((bb = ALLOCNO_LOOP_TREE_NODE (a)->bb) != NULL)
 762     fprintf (ira_dump_file, ",b%d", bb->index);
 763   else
 764     fprintf (ira_dump_file, ",l%d", ALLOCNO_LOOP_TREE_NODE (a)->loop->num);
 765   if (ALLOCNO_CAP_MEMBER (a) != NULL)
 766     {
 767       fprintf (ira_dump_file, ":");
 768       ira_print_expanded_allocno (ALLOCNO_CAP_MEMBER (a));
 769     }
 770   fprintf (ira_dump_file, ")");
 771 }
 772
 773 /* Create and return the cap representing allocno A in the
 774    parent loop.  */
 775 static ira_allocno_t
 776 create_cap_allocno (ira_allocno_t a)
 777 {
 778   ira_allocno_t cap;
 779   ira_loop_tree_node_t parent;
 780   enum reg_class cover_class;
 781
 782   ira_assert (ALLOCNO_FIRST_COALESCED_ALLOCNO (a) == a
 783               && ALLOCNO_NEXT_COALESCED_ALLOCNO (a) == a);
 784   parent = ALLOCNO_LOOP_TREE_NODE (a)->parent;
 785   cap = ira_create_allocno (ALLOCNO_REGNO (a), true, parent);
 786   ALLOCNO_MODE (cap) = ALLOCNO_MODE (a);
 787   cover_class = ALLOCNO_COVER_CLASS (a);
 788   ira_set_allocno_cover_class (cap, cover_class);
 789   ALLOCNO_AVAILABLE_REGS_NUM (cap) = ALLOCNO_AVAILABLE_REGS_NUM (a);
 790   ALLOCNO_CAP_MEMBER (cap) = a;
 791   ALLOCNO_CAP (a) = cap;
 792   ALLOCNO_COVER_CLASS_COST (cap) = ALLOCNO_COVER_CLASS_COST (a);
 793   ALLOCNO_MEMORY_COST (cap) = ALLOCNO_MEMORY_COST (a);
 794   ira_allocate_and_copy_costs
 795     (&ALLOCNO_HARD_REG_COSTS (cap), cover_class, ALLOCNO_HARD_REG_COSTS (a));
 796   ira_allocate_and_copy_costs
 797     (&ALLOCNO_CONFLICT_HARD_REG_COSTS (cap), cover_class,
 798      ALLOCNO_CONFLICT_HARD_REG_COSTS (a));
 799   ALLOCNO_BAD_SPILL_P (cap) = ALLOCNO_BAD_SPILL_P (a);
 800   ALLOCNO_NREFS (cap) = ALLOCNO_NREFS (a);
 801   ALLOCNO_FREQ (cap) = ALLOCNO_FREQ (a);
 802   ALLOCNO_CALL_FREQ (cap) = ALLOCNO_CALL_FREQ (a);
 803   merge_hard_reg_conflicts (a, cap, false);
 804   ALLOCNO_CALLS_CROSSED_NUM (cap) = ALLOCNO_CALLS_CROSSED_NUM (a);
 805   if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
 806     {
 807       fprintf (ira_dump_file, "    Creating cap ");
 808       ira_print_expanded_allocno (cap);
 809       fprintf (ira_dump_file, "\n");
 810     }
 811   return cap;
 812 }
 813
 814 /* Create and return allocno live range with given attributes.  */
 815 allocno_live_range_t
 816 ira_create_allocno_live_range (ira_allocno_t a, int start, int finish,
 817                                allocno_live_range_t next)
 818 {
 819   allocno_live_range_t p;
 820
 821   p = (allocno_live_range_t) pool_alloc (allocno_live_range_pool);
 822   p->allocno = a;
 823   p->start = start;
 824   p->finish = finish;
 825   p->next = next;
 826   return p;
 827 }
 828
 829 /* Copy allocno live range R and return the result.  */
 830 static allocno_live_range_t
 831 copy_allocno_live_range (allocno_live_range_t r)
 832 {
 833   allocno_live_range_t p;
 834
 835   p = (allocno_live_range_t) pool_alloc (allocno_live_range_pool);
 836   *p = *r;
 837   return p;
 838 }
 839
 840 /* Copy allocno live range list given by its head R and return the
 841    result.  */
 842 allocno_live_range_t
 843 ira_copy_allocno_live_range_list (allocno_live_range_t r)
 844 {
 845   allocno_live_range_t p, first, last;
 846
 847   if (r == NULL)
 848     return NULL;
 849   for (first = last = NULL; r != NULL; r = r->next)
 850     {
 851       p = copy_allocno_live_range (r);
 852       if (first == NULL)
 853         first = p;
 854       else
 855         last->next = p;
 856       last = p;
 857     }
 858   return first;
 859 }
 860
 861 /* Merge ranges R1 and R2 and returns the result.  The function
 862    maintains the order of ranges and tries to minimize number of the
 863    result ranges.  */
 864 allocno_live_range_t
 865 ira_merge_allocno_live_ranges (allocno_live_range_t r1,
 866                                allocno_live_range_t r2)
 867 {
 868   allocno_live_range_t first, last, temp;
 869
 870   if (r1 == NULL)
 871     return r2;
 872   if (r2 == NULL)
 873     return r1;
 874   for (first = last = NULL; r1 != NULL && r2 != NULL;)
 875     {
 876       if (r1->start < r2->start)
 877         {
 878           temp = r1;
 879           r1 = r2;
 880           r2 = temp;
 881         }
 882       if (r1->start <= r2->finish + 1)
 883         {
 884           /* Intersected ranges: merge r1 and r2 into r1.  */
 885           r1->start = r2->start;
 886           if (r1->finish < r2->finish)
 887             r1->finish = r2->finish;
 888           temp = r2;
 889           r2 = r2->next;
 890           ira_finish_allocno_live_range (temp);
 891           if (r2 == NULL)
 892             {
 893               /* To try to merge with subsequent ranges in r1.  */
 894               r2 = r1->next;
 895               r1->next = NULL;
 896             }
 897         }
 898       else
 899         {
 900           /* Add r1 to the result.  */
 901           if (first == NULL)
 902             first = last = r1;
 903           else
 904             {
 905               last->next = r1;
 906               last = r1;
 907             }
 908           r1 = r1->next;
 909           if (r1 == NULL)
 910             {
 911               /* To try to merge with subsequent ranges in r2.  */
 912               r1 = r2->next;
 913               r2->next = NULL;
 914             }
 915         }
 916     }
 917   if (r1 != NULL)
 918     {
 919       if (first == NULL)
 920         first = r1;
 921       else
 922         last->next = r1;
 923       ira_assert (r1->next == NULL);
 924     }
 925   else if (r2 != NULL)
 926     {
 927       if (first == NULL)
 928         first = r2;
 929       else
 930         last->next = r2;
 931       ira_assert (r2->next == NULL);
 932     }
 933   else
 934     {
 935       ira_assert (last->next == NULL);
 936     }
 937   return first;
 938 }
 939
 940 /* Return TRUE if live ranges R1 and R2 intersect.  */
 941 bool
 942 ira_allocno_live_ranges_intersect_p (allocno_live_range_t r1,
 943                                      allocno_live_range_t r2)
 944 {
 945   /* Remember the live ranges are always kept ordered.  */
 946   while (r1 != NULL && r2 != NULL)
 947     {
 948       if (r1->start > r2->finish)
 949         r1 = r1->next;
 950       else if (r2->start > r1->finish)
 951         r2 = r2->next;
 952       else
 953         return true;
 954     }
 955   return false;
 956 }
 957
 958 /* Free allocno live range R.  */
 959 void
 960 ira_finish_allocno_live_range (allocno_live_range_t r)
 961 {
 962   pool_free (allocno_live_range_pool, r);
 963 }
 964
 965 /* Free list of allocno live ranges starting with R.  */
 966 void
 967 ira_finish_allocno_live_range_list (allocno_live_range_t r)
 968 {
 969   allocno_live_range_t next_r;
 970
 971   for (; r != NULL; r = next_r)
 972     {
 973       next_r = r->next;
 974       ira_finish_allocno_live_range (r);
 975     }
 976 }
 977
 978 /* Free updated register costs of allocno A.  */
 979 void
 980 ira_free_allocno_updated_costs (ira_allocno_t a)
 981 {
 982   enum reg_class cover_class;
 983
 984   cover_class = ALLOCNO_COVER_CLASS (a);
 985   if (ALLOCNO_UPDATED_HARD_REG_COSTS (a) != NULL)
 986     ira_free_cost_vector (ALLOCNO_UPDATED_HARD_REG_COSTS (a), cover_class);
 987   ALLOCNO_UPDATED_HARD_REG_COSTS (a) = NULL;
 988   if (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) != NULL)
 989     ira_free_cost_vector (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a),
 990                           cover_class);
 991   ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) = NULL;
 992 }
 993
 994 /* Free the memory allocated for allocno A.  */
 995 static void
 996 finish_allocno (ira_allocno_t a)
 997 {
 998   enum reg_class cover_class = ALLOCNO_COVER_CLASS (a);
 999
1000   ira_allocnos[ALLOCNO_NUM (a)] = NULL;
1001   ira_conflict_id_allocno_map[ALLOCNO_CONFLICT_ID (a)] = NULL;
1002   if (ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a) != NULL)
1003     ira_free (ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a));
1004   if (ALLOCNO_HARD_REG_COSTS (a) != NULL)
1005     ira_free_cost_vector (ALLOCNO_HARD_REG_COSTS (a), cover_class);
1006   if (ALLOCNO_CONFLICT_HARD_REG_COSTS (a) != NULL)
1007     ira_free_cost_vector (ALLOCNO_CONFLICT_HARD_REG_COSTS (a), cover_class);
1008   if (ALLOCNO_UPDATED_HARD_REG_COSTS (a) != NULL)
1009     ira_free_cost_vector (ALLOCNO_UPDATED_HARD_REG_COSTS (a), cover_class);
1010   if (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) != NULL)
1011     ira_free_cost_vector (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a),
1012                           cover_class);
1013   ira_finish_allocno_live_range_list (ALLOCNO_LIVE_RANGES (a));
1014   pool_free (allocno_pool, a);
1015 }
1016
1017 /* Free the memory allocated for all allocnos.  */
1018 static void
1019 finish_allocnos (void)
1020 {
1021   ira_allocno_t a;
1022   ira_allocno_iterator ai;
1023
1024   FOR_EACH_ALLOCNO (a, ai)
1025     finish_allocno (a);
1026   ira_free (ira_regno_allocno_map);
1027   VEC_free (ira_allocno_t, heap, ira_conflict_id_allocno_map_vec);
1028   VEC_free (ira_allocno_t, heap, allocno_vec);
1029   free_alloc_pool (allocno_pool);
1030   free_alloc_pool (allocno_live_range_pool);
1031 }
1032
1033 \f
1034
1035 /* Pools for copies.  */
1036 static alloc_pool copy_pool;
1037
1038 /* Vec containing references to all created copies.  It is a
1039    container of array ira_copies.  */
1040 static VEC(ira_copy_t,heap) *copy_vec;
1041
1042 /* The function initializes data concerning allocno copies.  */
1043 static void
1044 initiate_copies (void)
1045 {
1046   copy_pool
1047     = create_alloc_pool ("copies", sizeof (struct ira_allocno_copy), 100);
1048   copy_vec = VEC_alloc (ira_copy_t, heap, get_max_uid ());
1049   ira_copies = NULL;
1050   ira_copies_num = 0;
1051 }
1052
1053 /* Return copy connecting A1 and A2 and originated from INSN of
1054    LOOP_TREE_NODE if any.  */
1055 static ira_copy_t
1056 find_allocno_copy (ira_allocno_t a1, ira_allocno_t a2, rtx insn,
1057                    ira_loop_tree_node_t loop_tree_node)
1058 {
1059   ira_copy_t cp, next_cp;
1060   ira_allocno_t another_a;
1061
1062   for (cp = ALLOCNO_COPIES (a1); cp != NULL; cp = next_cp)
1063     {
1064       if (cp->first == a1)
1065         {
1066           next_cp = cp->next_first_allocno_copy;
1067           another_a = cp->second;
1068         }
1069       else if (cp->second == a1)
1070         {
1071           next_cp = cp->next_second_allocno_copy;
1072           another_a = cp->first;
1073         }
1074       else
1075         gcc_unreachable ();
1076       if (another_a == a2 && cp->insn == insn
1077           && cp->loop_tree_node == loop_tree_node)
1078         return cp;
1079     }
1080   return NULL;
1081 }
1082
1083 /* Create and return copy with given attributes LOOP_TREE_NODE, FIRST,
1084    SECOND, FREQ, CONSTRAINT_P, and INSN.  */
1085 ira_copy_t
1086 ira_create_copy (ira_allocno_t first, ira_allocno_t second, int freq,
1087                  bool constraint_p, rtx insn,
1088                  ira_loop_tree_node_t loop_tree_node)
1089 {
1090   ira_copy_t cp;
1091
1092   cp = (ira_copy_t) pool_alloc (copy_pool);
1093   cp->num = ira_copies_num;
1094   cp->first = first;
1095   cp->second = second;
1096   cp->freq = freq;
1097   cp->constraint_p = constraint_p;
1098   cp->insn = insn;
1099   cp->loop_tree_node = loop_tree_node;
1100   VEC_safe_push (ira_copy_t, heap, copy_vec, cp);
1101   ira_copies = VEC_address (ira_copy_t, copy_vec);
1102   ira_copies_num = VEC_length (ira_copy_t, copy_vec);
1103   return cp;
1104 }
1105
1106 /* Attach a copy CP to allocnos involved into the copy.  */
1107 void
1108 ira_add_allocno_copy_to_list (ira_copy_t cp)
1109 {
1110   ira_allocno_t first = cp->first, second = cp->second;
1111
1112   cp->prev_first_allocno_copy = NULL;
1113   cp->prev_second_allocno_copy = NULL;
1114   cp->next_first_allocno_copy = ALLOCNO_COPIES (first);
1115   if (cp->next_first_allocno_copy != NULL)
1116     {
1117       if (cp->next_first_allocno_copy->first == first)
1118         cp->next_first_allocno_copy->prev_first_allocno_copy = cp;
1119       else
1120         cp->next_first_allocno_copy->prev_second_allocno_copy = cp;
1121     }
1122   cp->next_second_allocno_copy = ALLOCNO_COPIES (second);
1123   if (cp->next_second_allocno_copy != NULL)
1124     {
1125       if (cp->next_second_allocno_copy->second == second)
1126         cp->next_second_allocno_copy->prev_second_allocno_copy = cp;
1127       else
1128         cp->next_second_allocno_copy->prev_first_allocno_copy = cp;
1129     }
1130   ALLOCNO_COPIES (first) = cp;
1131   ALLOCNO_COPIES (second) = cp;
1132 }
1133
1134 /* Detach a copy CP from allocnos involved into the copy.  */
1135 void
1136 ira_remove_allocno_copy_from_list (ira_copy_t cp)
1137 {
1138   ira_allocno_t first = cp->first, second = cp->second;
1139   ira_copy_t prev, next;
1140
1141   next = cp->next_first_allocno_copy;
1142   prev = cp->prev_first_allocno_copy;
1143   if (prev == NULL)
1144     ALLOCNO_COPIES (first) = next;
1145   else if (prev->first == first)
1146     prev->next_first_allocno_copy = next;
1147   else
1148     prev->next_second_allocno_copy = next;
1149   if (next != NULL)
1150     {
1151       if (next->first == first)
1152         next->prev_first_allocno_copy = prev;
1153       else
1154         next->prev_second_allocno_copy = prev;
1155     }
1156   cp->prev_first_allocno_copy = cp->next_first_allocno_copy = NULL;
1157
1158   next = cp->next_second_allocno_copy;
1159   prev = cp->prev_second_allocno_copy;
1160   if (prev == NULL)
1161     ALLOCNO_COPIES (second) = next;
1162   else if (prev->second == second)
1163     prev->next_second_allocno_copy = next;
1164   else
1165     prev->next_first_allocno_copy = next;
1166   if (next != NULL)
1167     {
1168       if (next->second == second)
1169         next->prev_second_allocno_copy = prev;
1170       else
1171         next->prev_first_allocno_copy = prev;
1172     }
1173   cp->prev_second_allocno_copy = cp->next_second_allocno_copy = NULL;
1174 }
1175
1176 /* Make a copy CP a canonical copy where number of the
1177    first allocno is less than the second one.  */
1178 void
1179 ira_swap_allocno_copy_ends_if_necessary (ira_copy_t cp)
1180 {
1181   ira_allocno_t temp;
1182   ira_copy_t temp_cp;
1183
1184   if (ALLOCNO_NUM (cp->first) <= ALLOCNO_NUM (cp->second))
1185     return;
1186
1187   temp = cp->first;
1188   cp->first = cp->second;
1189   cp->second = temp;
1190
1191   temp_cp = cp->prev_first_allocno_copy;
1192   cp->prev_first_allocno_copy = cp->prev_second_allocno_copy;
1193   cp->prev_second_allocno_copy = temp_cp;
1194
1195   temp_cp = cp->next_first_allocno_copy;
1196   cp->next_first_allocno_copy = cp->next_second_allocno_copy;
1197   cp->next_second_allocno_copy = temp_cp;
1198 }
1199
1200 /* Create (or update frequency if the copy already exists) and return
1201    the copy of allocnos FIRST and SECOND with frequency FREQ
1202    corresponding to move insn INSN (if any) and originated from
1203    LOOP_TREE_NODE.  */
1204 ira_copy_t
1205 ira_add_allocno_copy (ira_allocno_t first, ira_allocno_t second, int freq,
1206                       bool constraint_p, rtx insn,
1207                       ira_loop_tree_node_t loop_tree_node)
1208 {
1209   ira_copy_t cp;
1210
1211   if ((cp = find_allocno_copy (first, second, insn, loop_tree_node)) != NULL)
1212     {
1213       cp->freq += freq;
1214       return cp;
1215     }
1216   cp = ira_create_copy (first, second, freq, constraint_p, insn,
1217                         loop_tree_node);
1218   ira_assert (first != NULL && second != NULL);
1219   ira_add_allocno_copy_to_list (cp);
1220   ira_swap_allocno_copy_ends_if_necessary (cp);
1221   return cp;
1222 }
1223
1224 /* Print info about copy CP into file F.  */
1225 static void
1226 print_copy (FILE *f, ira_copy_t cp)
1227 {
1228   fprintf (f, "  cp%d:a%d(r%d)<->a%d(r%d)@%d:%s\n", cp->num,
1229            ALLOCNO_NUM (cp->first), ALLOCNO_REGNO (cp->first),
1230            ALLOCNO_NUM (cp->second), ALLOCNO_REGNO (cp->second), cp->freq,
1231            cp->insn != NULL
1232            ? "move" : cp->constraint_p ? "constraint" : "shuffle");
1233 }
1234
1235 /* Print info about copy CP into stderr.  */
1236 void
1237 ira_debug_copy (ira_copy_t cp)
1238 {
1239   print_copy (stderr, cp);
1240 }
1241
1242 /* Print info about all copies into file F.  */
1243 static void
1244 print_copies (FILE *f)
1245 {
1246   ira_copy_t cp;
1247   ira_copy_iterator ci;
1248
1249   FOR_EACH_COPY (cp, ci)
1250     print_copy (f, cp);
1251 }
1252
1253 /* Print info about all copies into stderr.  */
1254 void
1255 ira_debug_copies (void)
1256 {
1257   print_copies (stderr);
1258 }
1259
1260 /* Print info about copies involving allocno A into file F.  */
1261 static void
1262 print_allocno_copies (FILE *f, ira_allocno_t a)
1263 {
1264   ira_allocno_t another_a;
1265   ira_copy_t cp, next_cp;
1266
1267   fprintf (f, " a%d(r%d):", ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
1268   for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
1269     {
1270       if (cp->first == a)
1271         {
1272           next_cp = cp->next_first_allocno_copy;
1273           another_a = cp->second;
1274         }
1275       else if (cp->second == a)
1276         {
1277           next_cp = cp->next_second_allocno_copy;
1278           another_a = cp->first;
1279         }
1280       else
1281         gcc_unreachable ();
1282       fprintf (f, " cp%d:a%d(r%d)@%d", cp->num,
1283                ALLOCNO_NUM (another_a), ALLOCNO_REGNO (another_a), cp->freq);
1284     }
1285   fprintf (f, "\n");
1286 }
1287
1288 /* Print info about copies involving allocno A into stderr.  */
1289 void
1290 ira_debug_allocno_copies (ira_allocno_t a)
1291 {
1292   print_allocno_copies (stderr, a);
1293 }
1294
1295 /* The function frees memory allocated for copy CP.  */
1296 static void
1297 finish_copy (ira_copy_t cp)
1298 {
1299   pool_free (copy_pool, cp);
1300 }
1301
1302
1303 /* Free memory allocated for all copies.  */
1304 static void
1305 finish_copies (void)
1306 {
1307   ira_copy_t cp;
1308   ira_copy_iterator ci;
1309
1310   FOR_EACH_COPY (cp, ci)
1311     finish_copy (cp);
1312   VEC_free (ira_copy_t, heap, copy_vec);
1313   free_alloc_pool (copy_pool);
1314 }
1315
1316 \f
1317
1318 /* Pools for cost vectors.  It is defined only for cover classes.  */
1319 static alloc_pool cost_vector_pool[N_REG_CLASSES];
1320
1321 /* The function initiates work with hard register cost vectors.  It
1322    creates allocation pool for each cover class.  */
1323 static void
1324 initiate_cost_vectors (void)
1325 {
1326   int i;
1327   enum reg_class cover_class;
1328
1329   for (i = 0; i < ira_reg_class_cover_size; i++)
1330     {
1331       cover_class = ira_reg_class_cover[i];
1332       cost_vector_pool[cover_class]
1333         = create_alloc_pool ("cost vectors",
1334                              sizeof (int)
1335                              * ira_class_hard_regs_num[cover_class],
1336                              100);
1337     }
1338 }
1339
1340 /* Allocate and return a cost vector VEC for COVER_CLASS.  */
1341 int *
1342 ira_allocate_cost_vector (enum reg_class cover_class)
1343 {
1344   return (int *) pool_alloc (cost_vector_pool[cover_class]);
1345 }
1346
1347 /* Free a cost vector VEC for COVER_CLASS.  */
1348 void
1349 ira_free_cost_vector (int *vec, enum reg_class cover_class)
1350 {
1351   ira_assert (vec != NULL);
1352   pool_free (cost_vector_pool[cover_class], vec);
1353 }
1354
1355 /* Finish work with hard register cost vectors.  Release allocation
1356    pool for each cover class.  */
1357 static void
1358 finish_cost_vectors (void)
1359 {
1360   int i;
1361   enum reg_class cover_class;
1362
1363   for (i = 0; i < ira_reg_class_cover_size; i++)
1364     {
1365       cover_class = ira_reg_class_cover[i];
1366       free_alloc_pool (cost_vector_pool[cover_class]);
1367     }
1368 }
1369
1370 \f
1371
1372 /* The current loop tree node and its regno allocno map.  */
1373 ira_loop_tree_node_t ira_curr_loop_tree_node;
1374 ira_allocno_t *ira_curr_regno_allocno_map;
1375
1376 /* This recursive function traverses loop tree with root LOOP_NODE
1377    calling non-null functions PREORDER_FUNC and POSTORDER_FUNC
1378    correspondingly in preorder and postorder.  The function sets up
1379    IRA_CURR_LOOP_TREE_NODE and IRA_CURR_REGNO_ALLOCNO_MAP.  If BB_P,
1380    basic block nodes of LOOP_NODE is also processed (before its
1381    subloop nodes).  */
1382 void
1383 ira_traverse_loop_tree (bool bb_p, ira_loop_tree_node_t loop_node,
1384                         void (*preorder_func) (ira_loop_tree_node_t),
1385                         void (*postorder_func) (ira_loop_tree_node_t))
1386 {
1387   ira_loop_tree_node_t subloop_node;
1388
1389   ira_assert (loop_node->bb == NULL);
1390   ira_curr_loop_tree_node = loop_node;
1391   ira_curr_regno_allocno_map = ira_curr_loop_tree_node->regno_allocno_map;
1392
1393   if (preorder_func != NULL)
1394     (*preorder_func) (loop_node);
1395
1396   if (bb_p)
1397     for (subloop_node = loop_node->children;
1398          subloop_node != NULL;
1399          subloop_node = subloop_node->next)
1400       if (subloop_node->bb != NULL)
1401         {
1402           if (preorder_func != NULL)
1403             (*preorder_func) (subloop_node);
1404
1405           if (postorder_func != NULL)
1406             (*postorder_func) (subloop_node);
1407         }
1408
1409   for (subloop_node = loop_node->subloops;
1410        subloop_node != NULL;
1411        subloop_node = subloop_node->subloop_next)
1412     {
1413       ira_assert (subloop_node->bb == NULL);
1414       ira_traverse_loop_tree (bb_p, subloop_node,
1415                               preorder_func, postorder_func);
1416     }
1417
1418   ira_curr_loop_tree_node = loop_node;
1419   ira_curr_regno_allocno_map = ira_curr_loop_tree_node->regno_allocno_map;
1420
1421   if (postorder_func != NULL)
1422     (*postorder_func) (loop_node);
1423 }
1424
1425 \f
1426
1427 /* The basic block currently being processed.  */
1428 static basic_block curr_bb;
1429
1430 /* This recursive function creates allocnos corresponding to
1431    pseudo-registers containing in X.  True OUTPUT_P means that X is
1432    a lvalue.  */
1433 static void
1434 create_insn_allocnos (rtx x, bool output_p)
1435 {
1436   int i, j;
1437   const char *fmt;
1438   enum rtx_code code = GET_CODE (x);
1439
1440   if (code == REG)
1441     {
1442       int regno;
1443
1444       if ((regno = REGNO (x)) >= FIRST_PSEUDO_REGISTER)
1445         {
1446           ira_allocno_t a;
1447
1448           if ((a = ira_curr_regno_allocno_map[regno]) == NULL)
1449             a = ira_create_allocno (regno, false, ira_curr_loop_tree_node);
1450
1451           ALLOCNO_NREFS (a)++;
1452           ALLOCNO_FREQ (a) += REG_FREQ_FROM_BB (curr_bb);
1453           if (output_p)
1454             bitmap_set_bit (ira_curr_loop_tree_node->modified_regnos, regno);
1455         }
1456       return;
1457     }
1458   else if (code == SET)
1459     {
1460       create_insn_allocnos (SET_DEST (x), true);
1461       create_insn_allocnos (SET_SRC (x), false);
1462       return;
1463     }
1464   else if (code == CLOBBER)
1465     {
1466       create_insn_allocnos (XEXP (x, 0), true);
1467       return;
1468     }
1469   else if (code == MEM)
1470     {
1471       create_insn_allocnos (XEXP (x, 0), false);
1472       return;
1473     }
1474   else if (code == PRE_DEC || code == POST_DEC || code == PRE_INC ||
1475            code == POST_INC || code == POST_MODIFY || code == PRE_MODIFY)
1476     {
1477       create_insn_allocnos (XEXP (x, 0), true);
1478       create_insn_allocnos (XEXP (x, 0), false);
1479       return;
1480     }
1481
1482   fmt = GET_RTX_FORMAT (code);
1483   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1484     {
1485       if (fmt[i] == 'e')
1486         create_insn_allocnos (XEXP (x, i), output_p);
1487       else if (fmt[i] == 'E')
1488         for (j = 0; j < XVECLEN (x, i); j++)
1489           create_insn_allocnos (XVECEXP (x, i, j), output_p);
1490     }
1491 }
1492
1493 /* Create allocnos corresponding to pseudo-registers living in the
1494    basic block represented by the corresponding loop tree node
1495    BB_NODE.  */
1496 static void
1497 create_bb_allocnos (ira_loop_tree_node_t bb_node)
1498 {
1499   basic_block bb;
1500   rtx insn;
1501   unsigned int i;
1502   bitmap_iterator bi;
1503
1504   curr_bb = bb = bb_node->bb;
1505   ira_assert (bb != NULL);
1506   FOR_BB_INSNS_REVERSE (bb, insn)
1507     if (NONDEBUG_INSN_P (insn))
1508       create_insn_allocnos (PATTERN (insn), false);
1509   /* It might be a allocno living through from one subloop to
1510      another.  */
1511   EXECUTE_IF_SET_IN_REG_SET (DF_LR_IN (bb), FIRST_PSEUDO_REGISTER, i, bi)
1512     if (ira_curr_regno_allocno_map[i] == NULL)
1513       ira_create_allocno (i, false, ira_curr_loop_tree_node);
1514 }
1515
1516 /* Create allocnos corresponding to pseudo-registers living on edge E
1517    (a loop entry or exit).  Also mark the allocnos as living on the
1518    loop border. */
1519 static void
1520 create_loop_allocnos (edge e)
1521 {
1522   unsigned int i;
1523   bitmap live_in_regs, border_allocnos;
1524   bitmap_iterator bi;
1525   ira_loop_tree_node_t parent;
1526
1527   live_in_regs = DF_LR_IN (e->dest);
1528   border_allocnos = ira_curr_loop_tree_node->border_allocnos;
1529   EXECUTE_IF_SET_IN_REG_SET (DF_LR_OUT (e->src),
1530                              FIRST_PSEUDO_REGISTER, i, bi)
1531     if (bitmap_bit_p (live_in_regs, i))
1532       {
1533         if (ira_curr_regno_allocno_map[i] == NULL)
1534           {
1535             /* The order of creations is important for right
1536                ira_regno_allocno_map.  */
1537             if ((parent = ira_curr_loop_tree_node->parent) != NULL
1538                 && parent->regno_allocno_map[i] == NULL)
1539               ira_create_allocno (i, false, parent);
1540             ira_create_allocno (i, false, ira_curr_loop_tree_node);
1541           }
1542         bitmap_set_bit (border_allocnos,
1543                         ALLOCNO_NUM (ira_curr_regno_allocno_map[i]));
1544       }
1545 }
1546
1547 /* Create allocnos corresponding to pseudo-registers living in loop
1548    represented by the corresponding loop tree node LOOP_NODE.  This
1549    function is called by ira_traverse_loop_tree.  */
1550 static void
1551 create_loop_tree_node_allocnos (ira_loop_tree_node_t loop_node)
1552 {
1553   if (loop_node->bb != NULL)
1554     create_bb_allocnos (loop_node);
1555   else if (loop_node != ira_loop_tree_root)
1556     {
1557       int i;
1558       edge_iterator ei;
1559       edge e;
1560       VEC (edge, heap) *edges;
1561
1562       FOR_EACH_EDGE (e, ei, loop_node->loop->header->preds)
1563         if (e->src != loop_node->loop->latch)
1564           create_loop_allocnos (e);
1565
1566       edges = get_loop_exit_edges (loop_node->loop);
1567       for (i = 0; VEC_iterate (edge, edges, i, e); i++)
1568         create_loop_allocnos (e);
1569       VEC_free (edge, heap, edges);
1570     }
1571 }
1572
1573 /* Propagate information about allocnos modified inside the loop given
1574    by its LOOP_TREE_NODE to its parent.  */
1575 static void
1576 propagate_modified_regnos (ira_loop_tree_node_t loop_tree_node)
1577 {
1578   if (loop_tree_node == ira_loop_tree_root)
1579     return;
1580   ira_assert (loop_tree_node->bb == NULL);
1581   bitmap_ior_into (loop_tree_node->parent->modified_regnos,
1582                    loop_tree_node->modified_regnos);
1583 }
1584
1585 /* Propagate new info about allocno A (see comments about accumulated
1586    info in allocno definition) to the corresponding allocno on upper
1587    loop tree level.  So allocnos on upper levels accumulate
1588    information about the corresponding allocnos in nested regions.
1589    The new info means allocno info finally calculated in this
1590    file.  */
1591 static void
1592 propagate_allocno_info (void)
1593 {
1594   int i;
1595   ira_allocno_t a, parent_a;
1596   ira_loop_tree_node_t parent;
1597   enum reg_class cover_class;
1598
1599   if (flag_ira_region != IRA_REGION_ALL
1600       && flag_ira_region != IRA_REGION_MIXED)
1601     return;
1602   for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--)
1603     for (a = ira_regno_allocno_map[i];
1604          a != NULL;
1605          a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
1606       if ((parent = ALLOCNO_LOOP_TREE_NODE (a)->parent) != NULL
1607           && (parent_a = parent->regno_allocno_map[i]) != NULL
1608           /* There are no caps yet at this point.  So use
1609              border_allocnos to find allocnos for the propagation.  */
1610           && bitmap_bit_p (ALLOCNO_LOOP_TREE_NODE (a)->border_allocnos,
1611                            ALLOCNO_NUM (a)))
1612         {
1613           if (! ALLOCNO_BAD_SPILL_P (a))
1614             ALLOCNO_BAD_SPILL_P (parent_a) = false;
1615           ALLOCNO_NREFS (parent_a) += ALLOCNO_NREFS (a);
1616           ALLOCNO_FREQ (parent_a) += ALLOCNO_FREQ (a);
1617           ALLOCNO_CALL_FREQ (parent_a) += ALLOCNO_CALL_FREQ (a);
1618           merge_hard_reg_conflicts (a, parent_a, true);
1619           ALLOCNO_CALLS_CROSSED_NUM (parent_a)
1620             += ALLOCNO_CALLS_CROSSED_NUM (a);
1621           ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (parent_a)
1622             += ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a);
1623           cover_class = ALLOCNO_COVER_CLASS (a);
1624           ira_assert (cover_class == ALLOCNO_COVER_CLASS (parent_a));
1625           ira_allocate_and_accumulate_costs
1626             (&ALLOCNO_HARD_REG_COSTS (parent_a), cover_class,
1627              ALLOCNO_HARD_REG_COSTS (a));
1628           ira_allocate_and_accumulate_costs
1629             (&ALLOCNO_CONFLICT_HARD_REG_COSTS (parent_a),
1630              cover_class,
1631              ALLOCNO_CONFLICT_HARD_REG_COSTS (a));
1632           ALLOCNO_COVER_CLASS_COST (parent_a)
1633             += ALLOCNO_COVER_CLASS_COST (a);
1634           ALLOCNO_MEMORY_COST (parent_a) += ALLOCNO_MEMORY_COST (a);
1635         }
1636 }
1637
1638 /* Create allocnos corresponding to pseudo-registers in the current
1639    function.  Traverse the loop tree for this.  */
1640 static void
1641 create_allocnos (void)
1642 {
1643   /* We need to process BB first to correctly link allocnos by member
1644      next_regno_allocno.  */
1645   ira_traverse_loop_tree (true, ira_loop_tree_root,
1646                           create_loop_tree_node_allocnos, NULL);
1647   if (optimize)
1648     ira_traverse_loop_tree (false, ira_loop_tree_root, NULL,
1649                             propagate_modified_regnos);
1650 }
1651
1652 \f
1653
1654 /* The page contains function to remove some regions from a separate
1655    register allocation.  We remove regions whose separate allocation
1656    will hardly improve the result.  As a result we speed up regional
1657    register allocation.  */
1658
1659 /* The function changes allocno in range list given by R onto A.  */
1660 static void
1661 change_allocno_in_range_list (allocno_live_range_t r, ira_allocno_t a)
1662 {
1663   for (; r != NULL; r = r->next)
1664     r->allocno = a;
1665 }
1666
1667 /* Move all live ranges associated with allocno FROM to allocno TO.  */
1668 static void
1669 move_allocno_live_ranges (ira_allocno_t from, ira_allocno_t to)
1670 {
1671   allocno_live_range_t lr = ALLOCNO_LIVE_RANGES (from);
1672
1673   if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL)
1674     {
1675       fprintf (ira_dump_file,
1676                "      Moving ranges of a%dr%d to a%dr%d: ",
1677                ALLOCNO_NUM (from), ALLOCNO_REGNO (from),
1678                ALLOCNO_NUM (to), ALLOCNO_REGNO (to));
1679       ira_print_live_range_list (ira_dump_file, lr);
1680     }
1681   change_allocno_in_range_list (lr, to);
1682   ALLOCNO_LIVE_RANGES (to)
1683     = ira_merge_allocno_live_ranges (lr, ALLOCNO_LIVE_RANGES (to));
1684   ALLOCNO_LIVE_RANGES (from) = NULL;
1685 }
1686
1687 /* Copy all live ranges associated with allocno FROM to allocno TO.  */
1688 static void
1689 copy_allocno_live_ranges (ira_allocno_t from, ira_allocno_t to)
1690 {
1691   allocno_live_range_t lr = ALLOCNO_LIVE_RANGES (from);
1692
1693   if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL)
1694     {
1695       fprintf (ira_dump_file,
1696                "      Copying ranges of a%dr%d to a%dr%d: ",
1697                ALLOCNO_NUM (from), ALLOCNO_REGNO (from),
1698                ALLOCNO_NUM (to), ALLOCNO_REGNO (to));
1699       ira_print_live_range_list (ira_dump_file, lr);
1700     }
1701   lr = ira_copy_allocno_live_range_list (lr);
1702   change_allocno_in_range_list (lr, to);
1703   ALLOCNO_LIVE_RANGES (to)
1704     = ira_merge_allocno_live_ranges (lr, ALLOCNO_LIVE_RANGES (to));
1705 }
1706
1707 /* Return TRUE if NODE represents a loop with low register
1708    pressure.  */
1709 static bool
1710 low_pressure_loop_node_p (ira_loop_tree_node_t node)
1711 {
1712   int i;
1713   enum reg_class cover_class;
1714
1715   if (node->bb != NULL)
1716     return false;
1717
1718   for (i = 0; i < ira_reg_class_cover_size; i++)
1719     {
1720       cover_class = ira_reg_class_cover[i];
1721       if (node->reg_pressure[cover_class]
1722           > ira_available_class_regs[cover_class])
1723         return false;
1724     }
1725   return true;
1726 }
1727
1728 /* Sort loops for marking them for removal.  We put already marked
1729    loops first, then less frequent loops next, and then outer loops
1730    next.  */
1731 static int
1732 loop_compare_func (const void *v1p, const void *v2p)
1733 {
1734   int diff;
1735   ira_loop_tree_node_t l1 = *(const ira_loop_tree_node_t *) v1p;
1736   ira_loop_tree_node_t l2 = *(const ira_loop_tree_node_t *) v2p;
1737
1738   ira_assert (l1->parent != NULL && l2->parent != NULL);
1739   if (l1->to_remove_p && ! l2->to_remove_p)
1740     return -1;
1741   if (! l1->to_remove_p && l2->to_remove_p)
1742     return 1;
1743   if ((diff = l1->loop->header->frequency - l2->loop->header->frequency) != 0)
1744     return diff;
1745   if ((diff = (int) loop_depth (l1->loop) - (int) loop_depth (l2->loop)) != 0)
1746     return diff;
1747   /* Make sorting stable.  */
1748   return l1->loop->num - l2->loop->num;
1749 }
1750
1751
1752 /* Mark loops which should be removed from regional allocation.  We
1753    remove a loop with low register pressure inside another loop with
1754    register pressure.  In this case a separate allocation of the loop
1755    hardly helps (for irregular register file architecture it could
1756    help by choosing a better hard register in the loop but we prefer
1757    faster allocation even in this case).  We also remove cheap loops
1758    if there are more than IRA_MAX_LOOPS_NUM of them.  */
1759 static void
1760 mark_loops_for_removal (void)
1761 {
1762   int i, n;
1763   ira_loop_tree_node_t *sorted_loops;
1764   loop_p loop;
1765
1766   sorted_loops
1767     = (ira_loop_tree_node_t *) ira_allocate (sizeof (ira_loop_tree_node_t)
1768                                              * VEC_length (loop_p,
1769                                                            ira_loops.larray));
1770   for (n = i = 0; VEC_iterate (loop_p, ira_loops.larray, i, loop); i++)
1771     if (ira_loop_nodes[i].regno_allocno_map != NULL)
1772       {
1773         if (ira_loop_nodes[i].parent == NULL)
1774           {
1775             /* Don't remove the root.  */
1776             ira_loop_nodes[i].to_remove_p = false;
1777             continue;
1778           }
1779         sorted_loops[n++] = &ira_loop_nodes[i];
1780         ira_loop_nodes[i].to_remove_p
1781           = (low_pressure_loop_node_p (ira_loop_nodes[i].parent)
1782              && low_pressure_loop_node_p (&ira_loop_nodes[i]));
1783       }
1784   qsort (sorted_loops, n, sizeof (ira_loop_tree_node_t), loop_compare_func);
1785   for (i = 0; n - i + 1 > IRA_MAX_LOOPS_NUM; i++)
1786     {
1787       sorted_loops[i]->to_remove_p = true;
1788       if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
1789         fprintf
1790           (ira_dump_file,
1791            "  Mark loop %d (header %d, freq %d, depth %d) for removal (%s)\n",
1792            sorted_loops[i]->loop->num, sorted_loops[i]->loop->header->index,
1793            sorted_loops[i]->loop->header->frequency,
1794            loop_depth (sorted_loops[i]->loop),
1795            low_pressure_loop_node_p (sorted_loops[i]->parent)
1796            && low_pressure_loop_node_p (sorted_loops[i])
1797            ? "low pressure" : "cheap loop");
1798     }
1799   ira_free (sorted_loops);
1800 }
1801
1802 /* Mark all loops but root for removing.  */
1803 static void
1804 mark_all_loops_for_removal (void)
1805 {
1806   int i;
1807   loop_p loop;
1808
1809   for (i = 0; VEC_iterate (loop_p, ira_loops.larray, i, loop); i++)
1810     if (ira_loop_nodes[i].regno_allocno_map != NULL)
1811       {
1812         if (ira_loop_nodes[i].parent == NULL)
1813           {
1814             /* Don't remove the root.  */
1815             ira_loop_nodes[i].to_remove_p = false;
1816             continue;
1817           }
1818         ira_loop_nodes[i].to_remove_p = true;
1819         if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
1820           fprintf
1821             (ira_dump_file,
1822              "  Mark loop %d (header %d, freq %d, depth %d) for removal\n",
1823              ira_loop_nodes[i].loop->num,
1824              ira_loop_nodes[i].loop->header->index,
1825              ira_loop_nodes[i].loop->header->frequency,
1826              loop_depth (ira_loop_nodes[i].loop));
1827       }
1828 }
1829
1830 /* Definition of vector of loop tree nodes.  */
1831 DEF_VEC_P(ira_loop_tree_node_t);
1832 DEF_VEC_ALLOC_P(ira_loop_tree_node_t, heap);
1833
1834 /* Vec containing references to all removed loop tree nodes.  */
1835 static VEC(ira_loop_tree_node_t,heap) *removed_loop_vec;
1836
1837 /* Vec containing references to all children of loop tree nodes.  */
1838 static VEC(ira_loop_tree_node_t,heap) *children_vec;
1839
1840 /* Remove subregions of NODE if their separate allocation will not
1841    improve the result.  */
1842 static void
1843 remove_uneccesary_loop_nodes_from_loop_tree (ira_loop_tree_node_t node)
1844 {
1845   unsigned int start;
1846   bool remove_p;
1847   ira_loop_tree_node_t subnode;
1848
1849   remove_p = node->to_remove_p;
1850   if (! remove_p)
1851     VEC_safe_push (ira_loop_tree_node_t, heap, children_vec, node);
1852   start = VEC_length (ira_loop_tree_node_t, children_vec);
1853   for (subnode = node->children; subnode != NULL; subnode = subnode->next)
1854     if (subnode->bb == NULL)
1855       remove_uneccesary_loop_nodes_from_loop_tree (subnode);
1856     else
1857       VEC_safe_push (ira_loop_tree_node_t, heap, children_vec, subnode);
1858   node->children = node->subloops = NULL;
1859   if (remove_p)
1860     {
1861       VEC_safe_push (ira_loop_tree_node_t, heap, removed_loop_vec, node);
1862       return;
1863     }
1864   while (VEC_length (ira_loop_tree_node_t, children_vec) > start)
1865     {
1866       subnode = VEC_pop (ira_loop_tree_node_t, children_vec);
1867       subnode->parent = node;
1868       subnode->next = node->children;
1869       node->children = subnode;
1870       if (subnode->bb == NULL)
1871         {
1872           subnode->subloop_next = node->subloops;
1873           node->subloops = subnode;
1874         }
1875     }
1876 }
1877
1878 /* Return TRUE if NODE is inside PARENT.  */
1879 static bool
1880 loop_is_inside_p (ira_loop_tree_node_t node, ira_loop_tree_node_t parent)
1881 {
1882   for (node = node->parent; node != NULL; node = node->parent)
1883     if (node == parent)
1884       return true;
1885   return false;
1886 }
1887
1888 /* Sort allocnos according to their order in regno allocno list.  */
1889 static int
1890 regno_allocno_order_compare_func (const void *v1p, const void *v2p)
1891 {
1892   ira_allocno_t a1 = *(const ira_allocno_t *) v1p;
1893   ira_allocno_t a2 = *(const ira_allocno_t *) v2p;
1894   ira_loop_tree_node_t n1 = ALLOCNO_LOOP_TREE_NODE (a1);
1895   ira_loop_tree_node_t n2 = ALLOCNO_LOOP_TREE_NODE (a2);
1896
1897   if (loop_is_inside_p (n1, n2))
1898     return -1;
1899   else if (loop_is_inside_p (n2, n1))
1900     return 1;
1901   /* If allocnos are equally good, sort by allocno numbers, so that
1902      the results of qsort leave nothing to chance.  We put allocnos
1903      with higher number first in the list because it is the original
1904      order for allocnos from loops on the same levels.  */
1905   return ALLOCNO_NUM (a2) - ALLOCNO_NUM (a1);
1906 }
1907
1908 /* This array is used to sort allocnos to restore allocno order in
1909    the regno allocno list.  */
1910 static ira_allocno_t *regno_allocnos;
1911
1912 /* Restore allocno order for REGNO in the regno allocno list.  */
1913 static void
1914 ira_rebuild_regno_allocno_list (int regno)
1915 {
1916   int i, n;
1917   ira_allocno_t a;
1918
1919   for (n = 0, a = ira_regno_allocno_map[regno];
1920        a != NULL;
1921        a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
1922     regno_allocnos[n++] = a;
1923   ira_assert (n > 0);
1924   qsort (regno_allocnos, n, sizeof (ira_allocno_t),
1925          regno_allocno_order_compare_func);
1926   for (i = 1; i < n; i++)
1927     ALLOCNO_NEXT_REGNO_ALLOCNO (regno_allocnos[i - 1]) = regno_allocnos[i];
1928   ALLOCNO_NEXT_REGNO_ALLOCNO (regno_allocnos[n - 1]) = NULL;
1929   ira_regno_allocno_map[regno] = regno_allocnos[0];
1930   if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
1931     fprintf (ira_dump_file, " Rebuilding regno allocno list for %d\n", regno);
1932 }
1933
1934 /* Propagate info from allocno FROM_A to allocno A.  */
1935 static void
1936 propagate_some_info_from_allocno (ira_allocno_t a, ira_allocno_t from_a)
1937 {
1938   enum reg_class cover_class;
1939
1940   merge_hard_reg_conflicts (from_a, a, false);
1941   ALLOCNO_NREFS (a) += ALLOCNO_NREFS (from_a);
1942   ALLOCNO_FREQ (a) += ALLOCNO_FREQ (from_a);
1943   ALLOCNO_CALL_FREQ (a) += ALLOCNO_CALL_FREQ (from_a);
1944   ALLOCNO_CALLS_CROSSED_NUM (a) += ALLOCNO_CALLS_CROSSED_NUM (from_a);
1945   ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a)
1946     += ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (from_a);
1947   if (! ALLOCNO_BAD_SPILL_P (from_a))
1948     ALLOCNO_BAD_SPILL_P (a) = false;
1949   cover_class = ALLOCNO_COVER_CLASS (from_a);
1950   ira_assert (cover_class == ALLOCNO_COVER_CLASS (a));
1951   ira_allocate_and_accumulate_costs (&ALLOCNO_HARD_REG_COSTS (a), cover_class,
1952                                      ALLOCNO_HARD_REG_COSTS (from_a));
1953   ira_allocate_and_accumulate_costs (&ALLOCNO_CONFLICT_HARD_REG_COSTS (a),
1954                                      cover_class,
1955                                      ALLOCNO_CONFLICT_HARD_REG_COSTS (from_a));
1956   ALLOCNO_COVER_CLASS_COST (a) += ALLOCNO_COVER_CLASS_COST (from_a);
1957   ALLOCNO_MEMORY_COST (a) += ALLOCNO_MEMORY_COST (from_a);
1958 }
1959
1960 /* Remove allocnos from loops removed from the allocation
1961    consideration.  */
1962 static void
1963 remove_unnecessary_allocnos (void)
1964 {
1965   int regno;
1966   bool merged_p, rebuild_p;
1967   ira_allocno_t a, prev_a, next_a, parent_a;
1968   ira_loop_tree_node_t a_node, parent;
1969
1970   merged_p = false;
1971   regno_allocnos = NULL;
1972   for (regno = max_reg_num () - 1; regno >= FIRST_PSEUDO_REGISTER; regno--)
1973     {
1974       rebuild_p = false;
1975       for (prev_a = NULL, a = ira_regno_allocno_map[regno];
1976            a != NULL;
1977            a = next_a)
1978         {
1979           next_a = ALLOCNO_NEXT_REGNO_ALLOCNO (a);
1980           a_node = ALLOCNO_LOOP_TREE_NODE (a);
1981           if (! a_node->to_remove_p)
1982             prev_a = a;
1983           else
1984             {
1985               for (parent = a_node->parent;
1986                    (parent_a = parent->regno_allocno_map[regno]) == NULL
1987                      && parent->to_remove_p;
1988                    parent = parent->parent)
1989                 ;
1990               if (parent_a == NULL)
1991                 {
1992                   /* There are no allocnos with the same regno in
1993                      upper region -- just move the allocno to the
1994                      upper region.  */
1995                   prev_a = a;
1996                   ALLOCNO_LOOP_TREE_NODE (a) = parent;
1997                   parent->regno_allocno_map[regno] = a;
1998                   bitmap_set_bit (parent->all_allocnos, ALLOCNO_NUM (a));
1999                   rebuild_p = true;
2000                 }
2001               else
2002                 {
2003                   /* Remove the allocno and update info of allocno in
2004                      the upper region.  */
2005                   if (prev_a == NULL)
2006                     ira_regno_allocno_map[regno] = next_a;
2007                   else
2008                     ALLOCNO_NEXT_REGNO_ALLOCNO (prev_a) = next_a;
2009                   move_allocno_live_ranges (a, parent_a);
2010                   merged_p = true;
2011                   propagate_some_info_from_allocno (parent_a, a);
2012                   /* Remove it from the corresponding regno allocno
2013                      map to avoid info propagation of subsequent
2014                      allocno into this already removed allocno.  */
2015                   a_node->regno_allocno_map[regno] = NULL;
2016                   finish_allocno (a);
2017                 }
2018             }
2019         }
2020       if (rebuild_p)
2021         /* We need to restore the order in regno allocno list.  */
2022         {
2023           if (regno_allocnos == NULL)
2024             regno_allocnos
2025               = (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t)
2026                                                 * ira_allocnos_num);
2027           ira_rebuild_regno_allocno_list (regno);
2028         }
2029     }
2030   if (merged_p)
2031     ira_rebuild_start_finish_chains ();
2032   if (regno_allocnos != NULL)
2033     ira_free (regno_allocnos);
2034 }
2035
2036 /* Remove allocnos from all loops but the root.  */
2037 static void
2038 remove_low_level_allocnos (void)
2039 {
2040   int regno;
2041   bool merged_p, propagate_p;
2042   ira_allocno_t a, top_a;
2043   ira_loop_tree_node_t a_node, parent;
2044   ira_allocno_iterator ai;
2045
2046   merged_p = false;
2047   FOR_EACH_ALLOCNO (a, ai)
2048     {
2049       a_node = ALLOCNO_LOOP_TREE_NODE (a);
2050       if (a_node == ira_loop_tree_root || ALLOCNO_CAP_MEMBER (a) != NULL)
2051         continue;
2052       regno = ALLOCNO_REGNO (a);
2053       if ((top_a = ira_loop_tree_root->regno_allocno_map[regno]) == NULL)
2054         {
2055           ALLOCNO_LOOP_TREE_NODE (a) = ira_loop_tree_root;
2056           ira_loop_tree_root->regno_allocno_map[regno] = a;
2057           continue;
2058         }
2059       propagate_p = a_node->parent->regno_allocno_map[regno] == NULL;
2060       /* Remove the allocno and update info of allocno in the upper
2061          region.  */
2062       move_allocno_live_ranges (a, top_a);
2063       merged_p = true;
2064       if (propagate_p)
2065         propagate_some_info_from_allocno (top_a, a);
2066     }
2067   FOR_EACH_ALLOCNO (a, ai)
2068     {
2069       a_node = ALLOCNO_LOOP_TREE_NODE (a);
2070       if (a_node == ira_loop_tree_root)
2071         continue;
2072       parent = a_node->parent;
2073       regno = ALLOCNO_REGNO (a);
2074       if (ALLOCNO_CAP_MEMBER (a) != NULL)
2075         ira_assert (ALLOCNO_CAP (a) != NULL);
2076       else if (ALLOCNO_CAP (a) == NULL)
2077         ira_assert (parent->regno_allocno_map[regno] != NULL);
2078     }
2079   FOR_EACH_ALLOCNO (a, ai)
2080     {
2081       regno = ALLOCNO_REGNO (a);
2082       if (ira_loop_tree_root->regno_allocno_map[regno] == a)
2083         {
2084           ira_regno_allocno_map[regno] = a;
2085           ALLOCNO_NEXT_REGNO_ALLOCNO (a) = NULL;
2086           ALLOCNO_CAP_MEMBER (a) = NULL;
2087           COPY_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (a),
2088                              ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a));
2089 #ifdef STACK_REGS
2090           if (ALLOCNO_TOTAL_NO_STACK_REG_P (a))
2091             ALLOCNO_NO_STACK_REG_P (a) = true;
2092 #endif
2093         }
2094       else
2095         finish_allocno (a);
2096     }
2097   if (merged_p)
2098     ira_rebuild_start_finish_chains ();
2099 }
2100
2101 /* Remove loops from consideration.  We remove all loops except for
2102    root if ALL_P or loops for which a separate allocation will not
2103    improve the result.  We have to do this after allocno creation and
2104    their costs and cover class evaluation because only after that the
2105    register pressure can be known and is calculated.  */
2106 static void
2107 remove_unnecessary_regions (bool all_p)
2108 {
2109   if (all_p)
2110     mark_all_loops_for_removal ();
2111   else
2112     mark_loops_for_removal ();
2113   children_vec
2114     = VEC_alloc (ira_loop_tree_node_t, heap,
2115                  last_basic_block + VEC_length (loop_p, ira_loops.larray));
2116   removed_loop_vec
2117     = VEC_alloc (ira_loop_tree_node_t, heap,
2118                  last_basic_block + VEC_length (loop_p, ira_loops.larray));
2119   remove_uneccesary_loop_nodes_from_loop_tree (ira_loop_tree_root) ;
2120   VEC_free (ira_loop_tree_node_t, heap, children_vec);
2121   if (all_p)
2122     remove_low_level_allocnos ();
2123   else
2124     remove_unnecessary_allocnos ();
2125   while (VEC_length (ira_loop_tree_node_t, removed_loop_vec) > 0)
2126     finish_loop_tree_node (VEC_pop (ira_loop_tree_node_t, removed_loop_vec));
2127   VEC_free (ira_loop_tree_node_t, heap, removed_loop_vec);
2128 }
2129
2130 \f
2131
2132 /* At this point true value of allocno attribute bad_spill_p means
2133    that there is an insn where allocno occurs and where the allocno
2134    can not be used as memory.  The function updates the attribute, now
2135    it can be true only for allocnos which can not be used as memory in
2136    an insn and in whose live ranges there is other allocno deaths.
2137    Spilling allocnos with true value will not improve the code because
2138    it will not make other allocnos colorable and additional reloads
2139    for the corresponding pseudo will be generated in reload pass for
2140    each insn it occurs.
2141
2142    This is a trick mentioned in one classic article of Chaitin etc
2143    which is frequently omitted in other implementations of RA based on
2144    graph coloring.  */
2145 static void
2146 update_bad_spill_attribute (void)
2147 {
2148   int i;
2149   ira_allocno_t a;
2150   ira_allocno_iterator ai;
2151   allocno_live_range_t r;
2152   enum reg_class cover_class;
2153   bitmap_head dead_points[N_REG_CLASSES];
2154
2155   for (i = 0; i < ira_reg_class_cover_size; i++)
2156     {
2157       cover_class = ira_reg_class_cover[i];
2158       bitmap_initialize (&dead_points[cover_class], &reg_obstack);
2159     }
2160   FOR_EACH_ALLOCNO (a, ai)
2161     {
2162       cover_class = ALLOCNO_COVER_CLASS (a);
2163       if (cover_class == NO_REGS)
2164         continue;
2165       for (r = ALLOCNO_LIVE_RANGES (a); r != NULL; r = r->next)
2166         bitmap_set_bit (&dead_points[cover_class], r->finish);
2167     }
2168   FOR_EACH_ALLOCNO (a, ai)
2169     {
2170       cover_class = ALLOCNO_COVER_CLASS (a);
2171       if (cover_class == NO_REGS)
2172         continue;
2173       if (! ALLOCNO_BAD_SPILL_P (a))
2174         continue;
2175       for (r = ALLOCNO_LIVE_RANGES (a); r != NULL; r = r->next)
2176         {
2177           for (i = r->start + 1; i < r->finish; i++)
2178             if (bitmap_bit_p (&dead_points[cover_class], i))
2179               break;
2180           if (i < r->finish)
2181             break;
2182         }
2183       if (r != NULL)
2184         ALLOCNO_BAD_SPILL_P (a) = false;
2185     }
2186   for (i = 0; i < ira_reg_class_cover_size; i++)
2187     {
2188       cover_class = ira_reg_class_cover[i];
2189       bitmap_clear (&dead_points[cover_class]);
2190     }
2191 }
2192
2193 \f
2194
2195 /* Set up minimal and maximal live range points for allocnos.  */
2196 static void
2197 setup_min_max_allocno_live_range_point (void)
2198 {
2199   int i;
2200   ira_allocno_t a, parent_a, cap;
2201   ira_allocno_iterator ai;
2202   allocno_live_range_t r;
2203   ira_loop_tree_node_t parent;
2204
2205   FOR_EACH_ALLOCNO (a, ai)
2206     {
2207       r = ALLOCNO_LIVE_RANGES (a);
2208       if (r == NULL)
2209         continue;
2210       ALLOCNO_MAX (a) = r->finish;
2211       for (; r->next != NULL; r = r->next)
2212         ;
2213       ALLOCNO_MIN (a) = r->start;
2214     }
2215   for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--)
2216     for (a = ira_regno_allocno_map[i];
2217          a != NULL;
2218          a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
2219       {
2220         if (ALLOCNO_MAX (a) < 0)
2221           continue;
2222         ira_assert (ALLOCNO_CAP_MEMBER (a) == NULL);
2223         /* Accumulation of range info.  */
2224         if (ALLOCNO_CAP (a) != NULL)
2225           {
2226             for (cap = ALLOCNO_CAP (a); cap != NULL; cap = ALLOCNO_CAP (cap))
2227               {
2228                 if (ALLOCNO_MAX (cap) < ALLOCNO_MAX (a))
2229                   ALLOCNO_MAX (cap) = ALLOCNO_MAX (a);
2230                 if (ALLOCNO_MIN (cap) > ALLOCNO_MIN (a))
2231                   ALLOCNO_MIN (cap) = ALLOCNO_MIN (a);
2232               }
2233             continue;
2234           }
2235         if ((parent = ALLOCNO_LOOP_TREE_NODE (a)->parent) == NULL)
2236           continue;
2237         parent_a = parent->regno_allocno_map[i];
2238         if (ALLOCNO_MAX (parent_a) < ALLOCNO_MAX (a))
2239           ALLOCNO_MAX (parent_a) = ALLOCNO_MAX (a);
2240         if (ALLOCNO_MIN (parent_a) > ALLOCNO_MIN (a))
2241           ALLOCNO_MIN (parent_a) = ALLOCNO_MIN (a);
2242       }
2243 #ifdef ENABLE_IRA_CHECKING
2244   FOR_EACH_ALLOCNO (a, ai)
2245     {
2246       if ((0 <= ALLOCNO_MIN (a) && ALLOCNO_MIN (a) <= ira_max_point)
2247           && (0 <= ALLOCNO_MAX (a) && ALLOCNO_MAX (a) <= ira_max_point))
2248         continue;
2249       gcc_unreachable ();
2250     }
2251 #endif
2252 }
2253
2254 /* Sort allocnos according to their live ranges.  Allocnos with
2255    smaller cover class are put first unless we use priority coloring.
2256    Allocnos with the same cove class are ordered according their start
2257    (min).  Allocnos with the same start are ordered according their
2258    finish (max).  */
2259 static int
2260 allocno_range_compare_func (const void *v1p, const void *v2p)
2261 {
2262   int diff;
2263   ira_allocno_t a1 = *(const ira_allocno_t *) v1p;
2264   ira_allocno_t a2 = *(const ira_allocno_t *) v2p;
2265
2266   if (flag_ira_algorithm != IRA_ALGORITHM_PRIORITY
2267       && (diff = ALLOCNO_COVER_CLASS (a1) - ALLOCNO_COVER_CLASS (a2)) != 0)
2268     return diff;
2269   if ((diff = ALLOCNO_MIN (a1) - ALLOCNO_MIN (a2)) != 0)
2270     return diff;
2271   if ((diff = ALLOCNO_MAX (a1) - ALLOCNO_MAX (a2)) != 0)
2272      return diff;
2273   return ALLOCNO_NUM (a1) - ALLOCNO_NUM (a2);
2274 }
2275
2276 /* Sort ira_conflict_id_allocno_map and set up conflict id of
2277    allocnos.  */
2278 static void
2279 sort_conflict_id_allocno_map (void)
2280 {
2281   int i, num;
2282   ira_allocno_t a;
2283   ira_allocno_iterator ai;
2284
2285   num = 0;
2286   FOR_EACH_ALLOCNO (a, ai)
2287     ira_conflict_id_allocno_map[num++] = a;
2288   qsort (ira_conflict_id_allocno_map, num, sizeof (ira_allocno_t),
2289          allocno_range_compare_func);
2290   for (i = 0; i < num; i++)
2291     if ((a = ira_conflict_id_allocno_map[i]) != NULL)
2292       ALLOCNO_CONFLICT_ID (a) = i;
2293   for (i = num; i < ira_allocnos_num; i++)
2294     ira_conflict_id_allocno_map[i] = NULL;
2295 }
2296
2297 /* Set up minimal and maximal conflict ids of allocnos with which
2298    given allocno can conflict.  */
2299 static void
2300 setup_min_max_conflict_allocno_ids (void)
2301 {
2302   int cover_class;
2303   int i, j, min, max, start, finish, first_not_finished, filled_area_start;
2304   int *live_range_min, *last_lived;
2305   ira_allocno_t a;
2306
2307   live_range_min = (int *) ira_allocate (sizeof (int) * ira_allocnos_num);
2308   cover_class = -1;
2309   first_not_finished = -1;
2310   for (i = 0; i < ira_allocnos_num; i++)
2311     {
2312       a = ira_conflict_id_allocno_map[i];
2313       if (a == NULL)
2314         continue;
2315       if (cover_class < 0
2316           || (flag_ira_algorithm != IRA_ALGORITHM_PRIORITY
2317               && cover_class != (int) ALLOCNO_COVER_CLASS (a)))
2318         {
2319           cover_class = ALLOCNO_COVER_CLASS (a);
2320           min = i;
2321           first_not_finished = i;
2322         }
2323       else
2324         {
2325           start = ALLOCNO_MIN (a);
2326           /* If we skip an allocno, the allocno with smaller ids will
2327              be also skipped because of the secondary sorting the
2328              range finishes (see function
2329              allocno_range_compare_func).  */
2330           while (first_not_finished < i
2331                  && start > ALLOCNO_MAX (ira_conflict_id_allocno_map
2332                                          [first_not_finished]))
2333             first_not_finished++;
2334           min = first_not_finished;
2335         }
2336       if (min == i)
2337         /* We could increase min further in this case but it is good
2338            enough.  */
2339         min++;
2340       live_range_min[i] = ALLOCNO_MIN (a);
2341       ALLOCNO_MIN (a) = min;
2342     }
2343   last_lived = (int *) ira_allocate (sizeof (int) * ira_max_point);
2344   cover_class = -1;
2345   filled_area_start = -1;
2346   for (i = ira_allocnos_num - 1; i >= 0; i--)
2347     {
2348       a = ira_conflict_id_allocno_map[i];
2349       if (a == NULL)
2350         continue;
2351       if (cover_class < 0
2352           || (flag_ira_algorithm != IRA_ALGORITHM_PRIORITY
2353               && cover_class != (int) ALLOCNO_COVER_CLASS (a)))
2354         {
2355           cover_class = ALLOCNO_COVER_CLASS (a);
2356           for (j = 0; j < ira_max_point; j++)
2357             last_lived[j] = -1;
2358           filled_area_start = ira_max_point;
2359         }
2360       min = live_range_min[i];
2361       finish = ALLOCNO_MAX (a);
2362       max = last_lived[finish];
2363       if (max < 0)
2364         /* We could decrease max further in this case but it is good
2365            enough.  */
2366         max = ALLOCNO_CONFLICT_ID (a) - 1;
2367       ALLOCNO_MAX (a) = max;
2368       /* In filling, we can go further A range finish to recognize
2369          intersection quickly because if the finish of subsequently
2370          processed allocno (it has smaller conflict id) range is
2371          further A range finish than they are definitely intersected
2372          (the reason for this is the allocnos with bigger conflict id
2373          have their range starts not smaller than allocnos with
2374          smaller ids.  */
2375       for (j = min; j < filled_area_start; j++)
2376         last_lived[j] = i;
2377       filled_area_start = min;
2378     }
2379   ira_free (last_lived);
2380   ira_free (live_range_min);
2381 }
2382
2383 \f
2384
2385 static void
2386 create_caps (void)
2387 {
2388   ira_allocno_t a;
2389   ira_allocno_iterator ai;
2390   ira_loop_tree_node_t loop_tree_node;
2391
2392   FOR_EACH_ALLOCNO (a, ai)
2393     {
2394       if (ALLOCNO_LOOP_TREE_NODE (a) == ira_loop_tree_root)
2395         continue;
2396       if (ALLOCNO_CAP_MEMBER (a) != NULL)
2397         create_cap_allocno (a);
2398       else if (ALLOCNO_CAP (a) == NULL)
2399         {
2400           loop_tree_node = ALLOCNO_LOOP_TREE_NODE (a);
2401           if (!bitmap_bit_p (loop_tree_node->border_allocnos, ALLOCNO_NUM (a)))
2402             create_cap_allocno (a);
2403         }
2404     }
2405 }
2406
2407 \f
2408
2409 /* The page contains code transforming more one region internal
2410    representation (IR) to one region IR which is necessary for reload.
2411    This transformation is called IR flattening.  We might just rebuild
2412    the IR for one region but we don't do it because it takes a lot of
2413    time.  */
2414
2415 /* Map: regno -> allocnos which will finally represent the regno for
2416    IR with one region.  */
2417 static ira_allocno_t *regno_top_level_allocno_map;
2418
2419 /* Find the allocno that corresponds to A at a level one higher up in the
2420    loop tree.  Returns NULL if A is a cap, or if it has no parent.  */
2421 ira_allocno_t
2422 ira_parent_allocno (ira_allocno_t a)
2423 {
2424   ira_loop_tree_node_t parent;
2425
2426   if (ALLOCNO_CAP (a) != NULL)
2427     return NULL;
2428
2429   parent = ALLOCNO_LOOP_TREE_NODE (a)->parent;
2430   if (parent == NULL)
2431     return NULL;
2432
2433   return parent->regno_allocno_map[ALLOCNO_REGNO (a)];
2434 }
2435
2436 /* Find the allocno that corresponds to A at a level one higher up in the
2437    loop tree.  If ALLOCNO_CAP is set for A, return that.  */
2438 ira_allocno_t
2439 ira_parent_or_cap_allocno (ira_allocno_t a)
2440 {
2441   if (ALLOCNO_CAP (a) != NULL)
2442     return ALLOCNO_CAP (a);
2443
2444   return ira_parent_allocno (a);
2445 }
2446
2447 /* Process all allocnos originated from pseudo REGNO and copy live
2448    ranges, hard reg conflicts, and allocno stack reg attributes from
2449    low level allocnos to final allocnos which are destinations of
2450    removed stores at a loop exit.  Return true if we copied live
2451    ranges.  */
2452 static bool
2453 copy_info_to_removed_store_destinations (int regno)
2454 {
2455   ira_allocno_t a;
2456   ira_allocno_t parent_a = NULL;
2457   ira_loop_tree_node_t parent;
2458   bool merged_p;
2459
2460   merged_p = false;
2461   for (a = ira_regno_allocno_map[regno];
2462        a != NULL;
2463        a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
2464     {
2465       if (a != regno_top_level_allocno_map[REGNO (ALLOCNO_REG (a))])
2466         /* This allocno will be removed.  */
2467         continue;
2468       /* Caps will be removed.  */
2469       ira_assert (ALLOCNO_CAP_MEMBER (a) == NULL);
2470       for (parent = ALLOCNO_LOOP_TREE_NODE (a)->parent;
2471            parent != NULL;
2472            parent = parent->parent)
2473         if ((parent_a = parent->regno_allocno_map[regno]) == NULL
2474             || (parent_a == regno_top_level_allocno_map[REGNO (ALLOCNO_REG
2475                                                                (parent_a))]
2476                 && ALLOCNO_MEM_OPTIMIZED_DEST_P (parent_a)))
2477           break;
2478       if (parent == NULL || parent_a == NULL)
2479         continue;
2480       copy_allocno_live_ranges (a, parent_a);
2481       merge_hard_reg_conflicts (a, parent_a, true);
2482       ALLOCNO_CALL_FREQ (parent_a) += ALLOCNO_CALL_FREQ (a);
2483       ALLOCNO_CALLS_CROSSED_NUM (parent_a)
2484         += ALLOCNO_CALLS_CROSSED_NUM (a);
2485       ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (parent_a)
2486         += ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a);
2487       merged_p = true;
2488     }
2489   return merged_p;
2490 }
2491
2492 /* Flatten the IR.  In other words, this function transforms IR as if
2493    it were built with one region (without loops).  We could make it
2494    much simpler by rebuilding IR with one region, but unfortunately it
2495    takes a lot of time.  MAX_REGNO_BEFORE_EMIT and
2496    IRA_MAX_POINT_BEFORE_EMIT are correspondingly MAX_REG_NUM () and
2497    IRA_MAX_POINT before emitting insns on the loop borders.  */
2498 void
2499 ira_flattening (int max_regno_before_emit, int ira_max_point_before_emit)
2500 {
2501   int i, j, num;
2502   bool keep_p;
2503   int hard_regs_num;
2504   bool new_pseudos_p, merged_p, mem_dest_p;
2505   unsigned int n;
2506   enum reg_class cover_class;
2507   ira_allocno_t a, parent_a, first, second, node_first, node_second;
2508   ira_copy_t cp;
2509   ira_loop_tree_node_t node;
2510   allocno_live_range_t r;
2511   ira_allocno_iterator ai;
2512   ira_copy_iterator ci;
2513   sparseset allocnos_live;
2514
2515   regno_top_level_allocno_map
2516     = (ira_allocno_t *) ira_allocate (max_reg_num () * sizeof (ira_allocno_t));
2517   memset (regno_top_level_allocno_map, 0,
2518           max_reg_num () * sizeof (ira_allocno_t));
2519   new_pseudos_p = merged_p = false;
2520   FOR_EACH_ALLOCNO (a, ai)
2521     {
2522       if (ALLOCNO_CAP_MEMBER (a) != NULL)
2523         /* Caps are not in the regno allocno maps and they are never
2524            will be transformed into allocnos existing after IR
2525            flattening.  */
2526         continue;
2527       COPY_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a),
2528                          ALLOCNO_CONFLICT_HARD_REGS (a));
2529 #ifdef STACK_REGS
2530       ALLOCNO_TOTAL_NO_STACK_REG_P (a) = ALLOCNO_NO_STACK_REG_P (a);
2531 #endif
2532     }
2533   /* Fix final allocno attributes.  */
2534   for (i = max_regno_before_emit - 1; i >= FIRST_PSEUDO_REGISTER; i--)
2535     {
2536       mem_dest_p = false;
2537       for (a = ira_regno_allocno_map[i];
2538            a != NULL;
2539            a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
2540         {
2541           ira_assert (ALLOCNO_CAP_MEMBER (a) == NULL);
2542           if (ALLOCNO_SOMEWHERE_RENAMED_P (a))
2543             new_pseudos_p = true;
2544           parent_a = ira_parent_allocno (a);
2545           if (parent_a == NULL)
2546             {
2547               ALLOCNO_COPIES (a) = NULL;
2548               regno_top_level_allocno_map[REGNO (ALLOCNO_REG (a))] = a;
2549               continue;
2550             }
2551           ira_assert (ALLOCNO_CAP_MEMBER (parent_a) == NULL);
2552
2553           if (ALLOCNO_MEM_OPTIMIZED_DEST (a) != NULL)
2554             mem_dest_p = true;
2555           if (REGNO (ALLOCNO_REG (a)) == REGNO (ALLOCNO_REG (parent_a)))
2556             {
2557               merge_hard_reg_conflicts (a, parent_a, true);
2558               move_allocno_live_ranges (a, parent_a);
2559               merged_p = true;
2560               ALLOCNO_MEM_OPTIMIZED_DEST_P (parent_a)
2561                 = (ALLOCNO_MEM_OPTIMIZED_DEST_P (parent_a)
2562                    || ALLOCNO_MEM_OPTIMIZED_DEST_P (a));
2563               continue;
2564             }
2565           new_pseudos_p = true;
2566           for (;;)
2567             {
2568               ALLOCNO_NREFS (parent_a) -= ALLOCNO_NREFS (a);
2569               ALLOCNO_FREQ (parent_a) -= ALLOCNO_FREQ (a);
2570               ALLOCNO_CALL_FREQ (parent_a) -= ALLOCNO_CALL_FREQ (a);
2571               ALLOCNO_CALLS_CROSSED_NUM (parent_a)
2572                 -= ALLOCNO_CALLS_CROSSED_NUM (a);
2573               ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (parent_a)
2574                 -= ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a);
2575               ira_assert (ALLOCNO_CALLS_CROSSED_NUM (parent_a) >= 0
2576                           && ALLOCNO_NREFS (parent_a) >= 0
2577                           && ALLOCNO_FREQ (parent_a) >= 0);
2578               cover_class = ALLOCNO_COVER_CLASS (parent_a);
2579               hard_regs_num = ira_class_hard_regs_num[cover_class];
2580               if (ALLOCNO_HARD_REG_COSTS (a) != NULL
2581                   && ALLOCNO_HARD_REG_COSTS (parent_a) != NULL)
2582                 for (j = 0; j < hard_regs_num; j++)
2583                   ALLOCNO_HARD_REG_COSTS (parent_a)[j]
2584                     -= ALLOCNO_HARD_REG_COSTS (a)[j];
2585               if (ALLOCNO_CONFLICT_HARD_REG_COSTS (a) != NULL
2586                   && ALLOCNO_CONFLICT_HARD_REG_COSTS (parent_a) != NULL)
2587                 for (j = 0; j < hard_regs_num; j++)
2588                   ALLOCNO_CONFLICT_HARD_REG_COSTS (parent_a)[j]
2589                     -= ALLOCNO_CONFLICT_HARD_REG_COSTS (a)[j];
2590               ALLOCNO_COVER_CLASS_COST (parent_a)
2591                 -= ALLOCNO_COVER_CLASS_COST (a);
2592               ALLOCNO_MEMORY_COST (parent_a) -= ALLOCNO_MEMORY_COST (a);
2593               parent_a = ira_parent_allocno (parent_a);
2594               if (parent_a == NULL)
2595                 break;
2596             }
2597           ALLOCNO_COPIES (a) = NULL;
2598           regno_top_level_allocno_map[REGNO (ALLOCNO_REG (a))] = a;
2599         }
2600       if (mem_dest_p && copy_info_to_removed_store_destinations (i))
2601         merged_p = true;
2602     }
2603   ira_assert (new_pseudos_p || ira_max_point_before_emit == ira_max_point);
2604   if (merged_p || ira_max_point_before_emit != ira_max_point)
2605     ira_rebuild_start_finish_chains ();
2606   if (new_pseudos_p)
2607     {
2608       /* Rebuild conflicts.  */
2609       FOR_EACH_ALLOCNO (a, ai)
2610         {
2611           if (a != regno_top_level_allocno_map[REGNO (ALLOCNO_REG (a))]
2612               || ALLOCNO_CAP_MEMBER (a) != NULL)
2613             continue;
2614           for (r = ALLOCNO_LIVE_RANGES (a); r != NULL; r = r->next)
2615             ira_assert (r->allocno == a);
2616           clear_allocno_conflicts (a);
2617         }
2618       allocnos_live = sparseset_alloc (ira_allocnos_num);
2619       for (i = 0; i < ira_max_point; i++)
2620         {
2621           for (r = ira_start_point_ranges[i]; r != NULL; r = r->start_next)
2622             {
2623               a = r->allocno;
2624               if (a != regno_top_level_allocno_map[REGNO (ALLOCNO_REG (a))]
2625                   || ALLOCNO_CAP_MEMBER (a) != NULL)
2626                 continue;
2627               num = ALLOCNO_NUM (a);
2628               cover_class = ALLOCNO_COVER_CLASS (a);
2629               sparseset_set_bit (allocnos_live, num);
2630               EXECUTE_IF_SET_IN_SPARSESET (allocnos_live, n)
2631                 {
2632                   ira_allocno_t live_a = ira_allocnos[n];
2633
2634                   if (ira_reg_classes_intersect_p
2635                       [cover_class][ALLOCNO_COVER_CLASS (live_a)]
2636                       /* Don't set up conflict for the allocno with itself.  */
2637                       && num != (int) n)
2638                     ira_add_allocno_conflict (a, live_a);
2639                 }
2640             }
2641
2642           for (r = ira_finish_point_ranges[i]; r != NULL; r = r->finish_next)
2643             sparseset_clear_bit (allocnos_live, ALLOCNO_NUM (r->allocno));
2644         }
2645       sparseset_free (allocnos_live);
2646       compress_conflict_vecs ();
2647     }
2648   /* Mark some copies for removing and change allocnos in the rest
2649      copies.  */
2650   FOR_EACH_COPY (cp, ci)
2651     {
2652       if (ALLOCNO_CAP_MEMBER (cp->first) != NULL
2653           || ALLOCNO_CAP_MEMBER (cp->second) != NULL)
2654         {
2655           if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL)
2656             fprintf
2657               (ira_dump_file, "      Remove cp%d:%c%dr%d-%c%dr%d\n",
2658                cp->num, ALLOCNO_CAP_MEMBER (cp->first) != NULL ? 'c' : 'a',
2659                ALLOCNO_NUM (cp->first), REGNO (ALLOCNO_REG (cp->first)),
2660                ALLOCNO_CAP_MEMBER (cp->second) != NULL ? 'c' : 'a',
2661                ALLOCNO_NUM (cp->second), REGNO (ALLOCNO_REG (cp->second)));
2662           cp->loop_tree_node = NULL;
2663           continue;
2664         }
2665       first = regno_top_level_allocno_map[REGNO (ALLOCNO_REG (cp->first))];
2666       second = regno_top_level_allocno_map[REGNO (ALLOCNO_REG (cp->second))];
2667       node = cp->loop_tree_node;
2668       if (node == NULL)
2669         keep_p = true; /* It copy generated in ira-emit.c.  */
2670       else
2671         {
2672           /* Check that the copy was not propagated from level on
2673              which we will have different pseudos.  */
2674           node_first = node->regno_allocno_map[ALLOCNO_REGNO (cp->first)];
2675           node_second = node->regno_allocno_map[ALLOCNO_REGNO (cp->second)];
2676           keep_p = ((REGNO (ALLOCNO_REG (first))
2677                      == REGNO (ALLOCNO_REG (node_first)))
2678                      && (REGNO (ALLOCNO_REG (second))
2679                          == REGNO (ALLOCNO_REG (node_second))));
2680         }
2681       if (keep_p)
2682         {
2683           cp->loop_tree_node = ira_loop_tree_root;
2684           cp->first = first;
2685           cp->second = second;
2686         }
2687       else
2688         {
2689           cp->loop_tree_node = NULL;
2690           if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL)
2691             fprintf (ira_dump_file, "      Remove cp%d:a%dr%d-a%dr%d\n",
2692                      cp->num, ALLOCNO_NUM (cp->first),
2693                      REGNO (ALLOCNO_REG (cp->first)), ALLOCNO_NUM (cp->second),
2694                      REGNO (ALLOCNO_REG (cp->second)));
2695         }
2696     }
2697   /* Remove unnecessary allocnos on lower levels of the loop tree.  */
2698   FOR_EACH_ALLOCNO (a, ai)
2699     {
2700       if (a != regno_top_level_allocno_map[REGNO (ALLOCNO_REG (a))]
2701           || ALLOCNO_CAP_MEMBER (a) != NULL)
2702         {
2703           if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL)
2704             fprintf (ira_dump_file, "      Remove a%dr%d\n",
2705                      ALLOCNO_NUM (a), REGNO (ALLOCNO_REG (a)));
2706           finish_allocno (a);
2707           continue;
2708         }
2709       ALLOCNO_LOOP_TREE_NODE (a) = ira_loop_tree_root;
2710       ALLOCNO_REGNO (a) = REGNO (ALLOCNO_REG (a));
2711       ALLOCNO_CAP (a) = NULL;
2712       /* Restore updated costs for assignments from reload.  */
2713       ALLOCNO_UPDATED_MEMORY_COST (a) = ALLOCNO_MEMORY_COST (a);
2714       ALLOCNO_UPDATED_COVER_CLASS_COST (a) = ALLOCNO_COVER_CLASS_COST (a);
2715       if (! ALLOCNO_ASSIGNED_P (a))
2716         ira_free_allocno_updated_costs (a);
2717       ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL);
2718       ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) == NULL);
2719     }
2720   /* Remove unnecessary copies.  */
2721   FOR_EACH_COPY (cp, ci)
2722     {
2723       if (cp->loop_tree_node == NULL)
2724         {
2725           ira_copies[cp->num] = NULL;
2726           finish_copy (cp);
2727           continue;
2728         }
2729       ira_assert
2730         (ALLOCNO_LOOP_TREE_NODE (cp->first) == ira_loop_tree_root
2731          && ALLOCNO_LOOP_TREE_NODE (cp->second) == ira_loop_tree_root);
2732       ira_add_allocno_copy_to_list (cp);
2733       ira_swap_allocno_copy_ends_if_necessary (cp);
2734     }
2735   rebuild_regno_allocno_maps ();
2736   if (ira_max_point != ira_max_point_before_emit)
2737     ira_compress_allocno_live_ranges ();
2738   ira_free (regno_top_level_allocno_map);
2739 }
2740
2741 \f
2742
2743 #ifdef ENABLE_IRA_CHECKING
2744 /* Check creation of all allocnos.  Allocnos on lower levels should
2745    have allocnos or caps on all upper levels.  */
2746 static void
2747 check_allocno_creation (void)
2748 {
2749   ira_allocno_t a;
2750   ira_allocno_iterator ai;
2751   ira_loop_tree_node_t loop_tree_node;
2752
2753   FOR_EACH_ALLOCNO (a, ai)
2754     {
2755       loop_tree_node = ALLOCNO_LOOP_TREE_NODE (a);
2756       ira_assert (bitmap_bit_p (loop_tree_node->all_allocnos,
2757                                 ALLOCNO_NUM (a)));
2758       if (loop_tree_node == ira_loop_tree_root)
2759         continue;
2760       if (ALLOCNO_CAP_MEMBER (a) != NULL)
2761         ira_assert (ALLOCNO_CAP (a) != NULL);
2762       else if (ALLOCNO_CAP (a) == NULL)
2763         ira_assert (loop_tree_node->parent
2764                     ->regno_allocno_map[ALLOCNO_REGNO (a)] != NULL
2765                     && bitmap_bit_p (loop_tree_node->border_allocnos,
2766                                      ALLOCNO_NUM (a)));
2767     }
2768 }
2769 #endif
2770
2771 /* Identify allocnos which prefer a register class with a single hard register.
2772    Adjust ALLOCNO_CONFLICT_HARD_REG_COSTS so that conflicting allocnos are
2773    less likely to use the preferred singleton register.  */
2774 static void
2775 update_conflict_hard_reg_costs (void)
2776 {
2777   ira_allocno_t a;
2778   ira_allocno_iterator ai;
2779   int i, index, min;
2780
2781   FOR_EACH_ALLOCNO (a, ai)
2782     {
2783       enum reg_class cover_class = ALLOCNO_COVER_CLASS (a);
2784       enum reg_class pref = reg_preferred_class (ALLOCNO_REGNO (a));
2785
2786       if (reg_class_size[pref] != 1)
2787         continue;
2788       index = (ira_class_hard_reg_index[cover_class]
2789                [ira_class_hard_regs[pref][0]]);
2790       if (index < 0)
2791         continue;
2792       if (ALLOCNO_CONFLICT_HARD_REG_COSTS (a) == NULL
2793           || ALLOCNO_HARD_REG_COSTS (a) == NULL)
2794         continue;
2795       min = INT_MAX;
2796       for (i = ira_class_hard_regs_num[cover_class] - 1; i >= 0; i--)
2797         if (ALLOCNO_HARD_REG_COSTS (a)[i] > ALLOCNO_COVER_CLASS_COST (a)
2798             && min > ALLOCNO_HARD_REG_COSTS (a)[i])
2799           min = ALLOCNO_HARD_REG_COSTS (a)[i];
2800       if (min == INT_MAX)
2801         continue;
2802       ira_allocate_and_set_costs (&ALLOCNO_CONFLICT_HARD_REG_COSTS (a),
2803                                   cover_class, 0);
2804       ALLOCNO_CONFLICT_HARD_REG_COSTS (a)[index]
2805         -= min - ALLOCNO_COVER_CLASS_COST (a);
2806     }
2807 }
2808
2809 /* Create a internal representation (IR) for IRA (allocnos, copies,
2810    loop tree nodes).  If LOOPS_P is FALSE the nodes corresponding to
2811    the loops (except the root which corresponds the all function) and
2812    correspondingly allocnos for the loops will be not created.  Such
2813    parameter value is used for Chaitin-Briggs coloring.  The function
2814    returns TRUE if we generate loop structure (besides nodes
2815    representing all function and the basic blocks) for regional
2816    allocation.  A true return means that we really need to flatten IR
2817    before the reload.  */
2818 bool
2819 ira_build (bool loops_p)
2820 {
2821   df_analyze ();
2822
2823   initiate_cost_vectors ();
2824   initiate_allocnos ();
2825   initiate_copies ();
2826   create_loop_tree_nodes (loops_p);
2827   form_loop_tree ();
2828   create_allocnos ();
2829   ira_costs ();
2830   ira_create_allocno_live_ranges ();
2831   remove_unnecessary_regions (false);
2832   ira_compress_allocno_live_ranges ();
2833   update_bad_spill_attribute ();
2834   loops_p = more_one_region_p ();
2835   if (loops_p)
2836     {
2837       propagate_allocno_info ();
2838       create_caps ();
2839     }
2840   ira_tune_allocno_costs_and_cover_classes ();
2841 #ifdef ENABLE_IRA_CHECKING
2842   check_allocno_creation ();
2843 #endif
2844   setup_min_max_allocno_live_range_point ();
2845   sort_conflict_id_allocno_map ();
2846   setup_min_max_conflict_allocno_ids ();
2847   ira_build_conflicts ();
2848   update_conflict_hard_reg_costs ();
2849   if (! ira_conflicts_p)
2850     {
2851       ira_allocno_t a;
2852       ira_allocno_iterator ai;
2853
2854       /* Remove all regions but root one.  */
2855       if (loops_p)
2856         {
2857           remove_unnecessary_regions (true);
2858           loops_p = false;
2859         }
2860       /* We don't save hard registers around calls for fast allocation
2861          -- add caller clobbered registers as conflicting ones to
2862          allocno crossing calls.  */
2863       FOR_EACH_ALLOCNO (a, ai)
2864         if (ALLOCNO_CALLS_CROSSED_NUM (a) != 0)
2865           {
2866             IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a),
2867                               call_used_reg_set);
2868             IOR_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (a),
2869                               call_used_reg_set);
2870           }
2871     }
2872   if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
2873     print_copies (ira_dump_file);
2874   if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
2875     {
2876       int n, nr;
2877       ira_allocno_t a;
2878       allocno_live_range_t r;
2879       ira_allocno_iterator ai;
2880
2881       n = 0;
2882       FOR_EACH_ALLOCNO (a, ai)
2883         n += ALLOCNO_CONFLICT_ALLOCNOS_NUM (a);
2884       nr = 0;
2885       FOR_EACH_ALLOCNO (a, ai)
2886         for (r = ALLOCNO_LIVE_RANGES (a); r != NULL; r = r->next)
2887           nr++;
2888       fprintf (ira_dump_file, "  regions=%d, blocks=%d, points=%d\n",
2889                VEC_length (loop_p, ira_loops.larray), n_basic_blocks,
2890                ira_max_point);
2891       fprintf (ira_dump_file,
2892                "    allocnos=%d, copies=%d, conflicts=%d, ranges=%d\n",
2893                ira_allocnos_num, ira_copies_num, n, nr);
2894     }
2895   return loops_p;
2896 }
2897
2898 /* Release the data created by function ira_build.  */
2899 void
2900 ira_destroy (void)
2901 {
2902   finish_loop_tree_nodes ();
2903   finish_copies ();
2904   finish_allocnos ();
2905   finish_cost_vectors ();
2906   ira_finish_allocno_live_ranges ();
2907 }