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