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