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 #ifdef STACK_REGS
1810 /* Return TRUE if LOOP has a complex enter or exit edge.  We don't
1811    form a region from such loop if the target use stack register
1812    because reg-stack.c can not deal with such edges.  */
1813 static bool
1814 loop_with_complex_edge_p (struct loop *loop)
1815 {
1816   int i;
1817   edge_iterator ei;
1818   edge e;
1819   VEC (edge, heap) *edges;
1820
1821   FOR_EACH_EDGE (e, ei, loop->header->preds)
1822     if (e->flags & EDGE_EH)
1823       return true;
1824   edges = get_loop_exit_edges (loop);
1825   FOR_EACH_VEC_ELT (edge, edges, i, e)
1826     if (e->flags & EDGE_COMPLEX)
1827       return true;
1828   return false;
1829 }
1830 #endif
1831
1832 /* Sort loops for marking them for removal.  We put already marked
1833    loops first, then less frequent loops next, and then outer loops
1834    next.  */
1835 static int
1836 loop_compare_func (const void *v1p, const void *v2p)
1837 {
1838   int diff;
1839   ira_loop_tree_node_t l1 = *(const ira_loop_tree_node_t *) v1p;
1840   ira_loop_tree_node_t l2 = *(const ira_loop_tree_node_t *) v2p;
1841
1842   ira_assert (l1->parent != NULL && l2->parent != NULL);
1843   if (l1->to_remove_p && ! l2->to_remove_p)
1844     return -1;
1845   if (! l1->to_remove_p && l2->to_remove_p)
1846     return 1;
1847   if ((diff = l1->loop->header->frequency - l2->loop->header->frequency) != 0)
1848     return diff;
1849   if ((diff = (int) loop_depth (l1->loop) - (int) loop_depth (l2->loop)) != 0)
1850     return diff;
1851   /* Make sorting stable.  */
1852   return l1->loop->num - l2->loop->num;
1853 }
1854
1855 /* Mark loops which should be removed from regional allocation.  We
1856    remove a loop with low register pressure inside another loop with
1857    register pressure.  In this case a separate allocation of the loop
1858    hardly helps (for irregular register file architecture it could
1859    help by choosing a better hard register in the loop but we prefer
1860    faster allocation even in this case).  We also remove cheap loops
1861    if there are more than IRA_MAX_LOOPS_NUM of them.  Loop with EH
1862    exit or enter edges are removed too because the allocation might
1863    require put pseudo moves on the EH edges (we could still do this
1864    for pseudos with caller saved hard registers in some cases but it
1865    is impossible to say here or during top-down allocation pass what
1866    hard register the pseudos get finally).  */
1867 static void
1868 mark_loops_for_removal (void)
1869 {
1870   int i, n;
1871   ira_loop_tree_node_t *sorted_loops;
1872   loop_p loop;
1873
1874   sorted_loops
1875     = (ira_loop_tree_node_t *) ira_allocate (sizeof (ira_loop_tree_node_t)
1876                                              * VEC_length (loop_p,
1877                                                            ira_loops.larray));
1878   for (n = i = 0; VEC_iterate (loop_p, ira_loops.larray, i, loop); i++)
1879     if (ira_loop_nodes[i].regno_allocno_map != NULL)
1880       {
1881         if (ira_loop_nodes[i].parent == NULL)
1882           {
1883             /* Don't remove the root.  */
1884             ira_loop_nodes[i].to_remove_p = false;
1885             continue;
1886           }
1887         sorted_loops[n++] = &ira_loop_nodes[i];
1888         ira_loop_nodes[i].to_remove_p
1889           = ((low_pressure_loop_node_p (ira_loop_nodes[i].parent)
1890               && low_pressure_loop_node_p (&ira_loop_nodes[i]))
1891 #ifdef STACK_REGS
1892              || loop_with_complex_edge_p (ira_loop_nodes[i].loop)
1893 #endif
1894              );
1895       }
1896   qsort (sorted_loops, n, sizeof (ira_loop_tree_node_t), loop_compare_func);
1897   for (i = 0; n - i + 1 > IRA_MAX_LOOPS_NUM; i++)
1898     {
1899       sorted_loops[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 (%s)\n",
1904            sorted_loops[i]->loop->num, sorted_loops[i]->loop->header->index,
1905            sorted_loops[i]->loop->header->frequency,
1906            loop_depth (sorted_loops[i]->loop),
1907            low_pressure_loop_node_p (sorted_loops[i]->parent)
1908            && low_pressure_loop_node_p (sorted_loops[i])
1909            ? "low pressure" : "cheap loop");
1910     }
1911   ira_free (sorted_loops);
1912 }
1913
1914 /* Mark all loops but root for removing.  */
1915 static void
1916 mark_all_loops_for_removal (void)
1917 {
1918   int i;
1919   loop_p loop;
1920
1921   FOR_EACH_VEC_ELT (loop_p, ira_loops.larray, i, loop)
1922     if (ira_loop_nodes[i].regno_allocno_map != NULL)
1923       {
1924         if (ira_loop_nodes[i].parent == NULL)
1925           {
1926             /* Don't remove the root.  */
1927             ira_loop_nodes[i].to_remove_p = false;
1928             continue;
1929           }
1930         ira_loop_nodes[i].to_remove_p = true;
1931         if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
1932           fprintf
1933             (ira_dump_file,
1934              "  Mark loop %d (header %d, freq %d, depth %d) for removal\n",
1935              ira_loop_nodes[i].loop->num,
1936              ira_loop_nodes[i].loop->header->index,
1937              ira_loop_nodes[i].loop->header->frequency,
1938              loop_depth (ira_loop_nodes[i].loop));
1939       }
1940 }
1941
1942 /* Definition of vector of loop tree nodes.  */
1943 DEF_VEC_P(ira_loop_tree_node_t);
1944 DEF_VEC_ALLOC_P(ira_loop_tree_node_t, heap);
1945
1946 /* Vec containing references to all removed loop tree nodes.  */
1947 static VEC(ira_loop_tree_node_t,heap) *removed_loop_vec;
1948
1949 /* Vec containing references to all children of loop tree nodes.  */
1950 static VEC(ira_loop_tree_node_t,heap) *children_vec;
1951
1952 /* Remove subregions of NODE if their separate allocation will not
1953    improve the result.  */
1954 static void
1955 remove_uneccesary_loop_nodes_from_loop_tree (ira_loop_tree_node_t node)
1956 {
1957   unsigned int start;
1958   bool remove_p;
1959   ira_loop_tree_node_t subnode;
1960
1961   remove_p = node->to_remove_p;
1962   if (! remove_p)
1963     VEC_safe_push (ira_loop_tree_node_t, heap, children_vec, node);
1964   start = VEC_length (ira_loop_tree_node_t, children_vec);
1965   for (subnode = node->children; subnode != NULL; subnode = subnode->next)
1966     if (subnode->bb == NULL)
1967       remove_uneccesary_loop_nodes_from_loop_tree (subnode);
1968     else
1969       VEC_safe_push (ira_loop_tree_node_t, heap, children_vec, subnode);
1970   node->children = node->subloops = NULL;
1971   if (remove_p)
1972     {
1973       VEC_safe_push (ira_loop_tree_node_t, heap, removed_loop_vec, node);
1974       return;
1975     }
1976   while (VEC_length (ira_loop_tree_node_t, children_vec) > start)
1977     {
1978       subnode = VEC_pop (ira_loop_tree_node_t, children_vec);
1979       subnode->parent = node;
1980       subnode->next = node->children;
1981       node->children = subnode;
1982       if (subnode->bb == NULL)
1983         {
1984           subnode->subloop_next = node->subloops;
1985           node->subloops = subnode;
1986         }
1987     }
1988 }
1989
1990 /* Return TRUE if NODE is inside PARENT.  */
1991 static bool
1992 loop_is_inside_p (ira_loop_tree_node_t node, ira_loop_tree_node_t parent)
1993 {
1994   for (node = node->parent; node != NULL; node = node->parent)
1995     if (node == parent)
1996       return true;
1997   return false;
1998 }
1999
2000 /* Sort allocnos according to their order in regno allocno list.  */
2001 static int
2002 regno_allocno_order_compare_func (const void *v1p, const void *v2p)
2003 {
2004   ira_allocno_t a1 = *(const ira_allocno_t *) v1p;
2005   ira_allocno_t a2 = *(const ira_allocno_t *) v2p;
2006   ira_loop_tree_node_t n1 = ALLOCNO_LOOP_TREE_NODE (a1);
2007   ira_loop_tree_node_t n2 = ALLOCNO_LOOP_TREE_NODE (a2);
2008
2009   if (loop_is_inside_p (n1, n2))
2010     return -1;
2011   else if (loop_is_inside_p (n2, n1))
2012     return 1;
2013   /* If allocnos are equally good, sort by allocno numbers, so that
2014      the results of qsort leave nothing to chance.  We put allocnos
2015      with higher number first in the list because it is the original
2016      order for allocnos from loops on the same levels.  */
2017   return ALLOCNO_NUM (a2) - ALLOCNO_NUM (a1);
2018 }
2019
2020 /* This array is used to sort allocnos to restore allocno order in
2021    the regno allocno list.  */
2022 static ira_allocno_t *regno_allocnos;
2023
2024 /* Restore allocno order for REGNO in the regno allocno list.  */
2025 static void
2026 ira_rebuild_regno_allocno_list (int regno)
2027 {
2028   int i, n;
2029   ira_allocno_t a;
2030
2031   for (n = 0, a = ira_regno_allocno_map[regno];
2032        a != NULL;
2033        a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
2034     regno_allocnos[n++] = a;
2035   ira_assert (n > 0);
2036   qsort (regno_allocnos, n, sizeof (ira_allocno_t),
2037          regno_allocno_order_compare_func);
2038   for (i = 1; i < n; i++)
2039     ALLOCNO_NEXT_REGNO_ALLOCNO (regno_allocnos[i - 1]) = regno_allocnos[i];
2040   ALLOCNO_NEXT_REGNO_ALLOCNO (regno_allocnos[n - 1]) = NULL;
2041   ira_regno_allocno_map[regno] = regno_allocnos[0];
2042   if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
2043     fprintf (ira_dump_file, " Rebuilding regno allocno list for %d\n", regno);
2044 }
2045
2046 /* Propagate info from allocno FROM_A to allocno A.  */
2047 static void
2048 propagate_some_info_from_allocno (ira_allocno_t a, ira_allocno_t from_a)
2049 {
2050   enum reg_class aclass;
2051
2052   merge_hard_reg_conflicts (from_a, a, false);
2053   ALLOCNO_NREFS (a) += ALLOCNO_NREFS (from_a);
2054   ALLOCNO_FREQ (a) += ALLOCNO_FREQ (from_a);
2055   ALLOCNO_CALL_FREQ (a) += ALLOCNO_CALL_FREQ (from_a);
2056   ALLOCNO_CALLS_CROSSED_NUM (a) += ALLOCNO_CALLS_CROSSED_NUM (from_a);
2057   ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a)
2058     += ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (from_a);
2059   if (! ALLOCNO_BAD_SPILL_P (from_a))
2060     ALLOCNO_BAD_SPILL_P (a) = false;
2061   aclass = ALLOCNO_CLASS (from_a);
2062   ira_assert (aclass == ALLOCNO_CLASS (a));
2063   ira_allocate_and_accumulate_costs (&ALLOCNO_HARD_REG_COSTS (a), aclass,
2064                                      ALLOCNO_HARD_REG_COSTS (from_a));
2065   ira_allocate_and_accumulate_costs (&ALLOCNO_CONFLICT_HARD_REG_COSTS (a),
2066                                      aclass,
2067                                      ALLOCNO_CONFLICT_HARD_REG_COSTS (from_a));
2068   ALLOCNO_CLASS_COST (a) += ALLOCNO_CLASS_COST (from_a);
2069   ALLOCNO_MEMORY_COST (a) += ALLOCNO_MEMORY_COST (from_a);
2070 }
2071
2072 /* Remove allocnos from loops removed from the allocation
2073    consideration.  */
2074 static void
2075 remove_unnecessary_allocnos (void)
2076 {
2077   int regno;
2078   bool merged_p, rebuild_p;
2079   ira_allocno_t a, prev_a, next_a, parent_a;
2080   ira_loop_tree_node_t a_node, parent;
2081
2082   merged_p = false;
2083   regno_allocnos = NULL;
2084   for (regno = max_reg_num () - 1; regno >= FIRST_PSEUDO_REGISTER; regno--)
2085     {
2086       rebuild_p = false;
2087       for (prev_a = NULL, a = ira_regno_allocno_map[regno];
2088            a != NULL;
2089            a = next_a)
2090         {
2091           next_a = ALLOCNO_NEXT_REGNO_ALLOCNO (a);
2092           a_node = ALLOCNO_LOOP_TREE_NODE (a);
2093           if (! a_node->to_remove_p)
2094             prev_a = a;
2095           else
2096             {
2097               for (parent = a_node->parent;
2098                    (parent_a = parent->regno_allocno_map[regno]) == NULL
2099                      && parent->to_remove_p;
2100                    parent = parent->parent)
2101                 ;
2102               if (parent_a == NULL)
2103                 {
2104                   /* There are no allocnos with the same regno in
2105                      upper region -- just move the allocno to the
2106                      upper region.  */
2107                   prev_a = a;
2108                   ALLOCNO_LOOP_TREE_NODE (a) = parent;
2109                   parent->regno_allocno_map[regno] = a;
2110                   bitmap_set_bit (parent->all_allocnos, ALLOCNO_NUM (a));
2111                   rebuild_p = true;
2112                 }
2113               else
2114                 {
2115                   /* Remove the allocno and update info of allocno in
2116                      the upper region.  */
2117                   if (prev_a == NULL)
2118                     ira_regno_allocno_map[regno] = next_a;
2119                   else
2120                     ALLOCNO_NEXT_REGNO_ALLOCNO (prev_a) = next_a;
2121                   move_allocno_live_ranges (a, parent_a);
2122                   merged_p = true;
2123                   propagate_some_info_from_allocno (parent_a, a);
2124                   /* Remove it from the corresponding regno allocno
2125                      map to avoid info propagation of subsequent
2126                      allocno into this already removed allocno.  */
2127                   a_node->regno_allocno_map[regno] = NULL;
2128                   finish_allocno (a);
2129                 }
2130             }
2131         }
2132       if (rebuild_p)
2133         /* We need to restore the order in regno allocno list.  */
2134         {
2135           if (regno_allocnos == NULL)
2136             regno_allocnos
2137               = (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t)
2138                                                 * ira_allocnos_num);
2139           ira_rebuild_regno_allocno_list (regno);
2140         }
2141     }
2142   if (merged_p)
2143     ira_rebuild_start_finish_chains ();
2144   if (regno_allocnos != NULL)
2145     ira_free (regno_allocnos);
2146 }
2147
2148 /* Remove allocnos from all loops but the root.  */
2149 static void
2150 remove_low_level_allocnos (void)
2151 {
2152   int regno;
2153   bool merged_p, propagate_p;
2154   ira_allocno_t a, top_a;
2155   ira_loop_tree_node_t a_node, parent;
2156   ira_allocno_iterator ai;
2157
2158   merged_p = false;
2159   FOR_EACH_ALLOCNO (a, ai)
2160     {
2161       a_node = ALLOCNO_LOOP_TREE_NODE (a);
2162       if (a_node == ira_loop_tree_root || ALLOCNO_CAP_MEMBER (a) != NULL)
2163         continue;
2164       regno = ALLOCNO_REGNO (a);
2165       if ((top_a = ira_loop_tree_root->regno_allocno_map[regno]) == NULL)
2166         {
2167           ALLOCNO_LOOP_TREE_NODE (a) = ira_loop_tree_root;
2168           ira_loop_tree_root->regno_allocno_map[regno] = a;
2169           continue;
2170         }
2171       propagate_p = a_node->parent->regno_allocno_map[regno] == NULL;
2172       /* Remove the allocno and update info of allocno in the upper
2173          region.  */
2174       move_allocno_live_ranges (a, top_a);
2175       merged_p = true;
2176       if (propagate_p)
2177         propagate_some_info_from_allocno (top_a, a);
2178     }
2179   FOR_EACH_ALLOCNO (a, ai)
2180     {
2181       a_node = ALLOCNO_LOOP_TREE_NODE (a);
2182       if (a_node == ira_loop_tree_root)
2183         continue;
2184       parent = a_node->parent;
2185       regno = ALLOCNO_REGNO (a);
2186       if (ALLOCNO_CAP_MEMBER (a) != NULL)
2187         ira_assert (ALLOCNO_CAP (a) != NULL);
2188       else if (ALLOCNO_CAP (a) == NULL)
2189         ira_assert (parent->regno_allocno_map[regno] != NULL);
2190     }
2191   FOR_EACH_ALLOCNO (a, ai)
2192     {
2193       regno = ALLOCNO_REGNO (a);
2194       if (ira_loop_tree_root->regno_allocno_map[regno] == a)
2195         {
2196           ira_object_t obj;
2197           ira_allocno_object_iterator oi;
2198
2199           ira_regno_allocno_map[regno] = a;
2200           ALLOCNO_NEXT_REGNO_ALLOCNO (a) = NULL;
2201           ALLOCNO_CAP_MEMBER (a) = NULL;
2202           FOR_EACH_ALLOCNO_OBJECT (a, obj, oi)
2203             COPY_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (obj),
2204                                OBJECT_TOTAL_CONFLICT_HARD_REGS (obj));
2205 #ifdef STACK_REGS
2206           if (ALLOCNO_TOTAL_NO_STACK_REG_P (a))
2207             ALLOCNO_NO_STACK_REG_P (a) = true;
2208 #endif
2209         }
2210       else
2211         finish_allocno (a);
2212     }
2213   if (merged_p)
2214     ira_rebuild_start_finish_chains ();
2215 }
2216
2217 /* Remove loops from consideration.  We remove all loops except for
2218    root if ALL_P or loops for which a separate allocation will not
2219    improve the result.  We have to do this after allocno creation and
2220    their costs and allocno class evaluation because only after that
2221    the register pressure can be known and is calculated.  */
2222 static void
2223 remove_unnecessary_regions (bool all_p)
2224 {
2225   if (all_p)
2226     mark_all_loops_for_removal ();
2227   else
2228     mark_loops_for_removal ();
2229   children_vec
2230     = VEC_alloc (ira_loop_tree_node_t, heap,
2231                  last_basic_block + VEC_length (loop_p, ira_loops.larray));
2232   removed_loop_vec
2233     = VEC_alloc (ira_loop_tree_node_t, heap,
2234                  last_basic_block + VEC_length (loop_p, ira_loops.larray));
2235   remove_uneccesary_loop_nodes_from_loop_tree (ira_loop_tree_root) ;
2236   VEC_free (ira_loop_tree_node_t, heap, children_vec);
2237   if (all_p)
2238     remove_low_level_allocnos ();
2239   else
2240     remove_unnecessary_allocnos ();
2241   while (VEC_length (ira_loop_tree_node_t, removed_loop_vec) > 0)
2242     finish_loop_tree_node (VEC_pop (ira_loop_tree_node_t, removed_loop_vec));
2243   VEC_free (ira_loop_tree_node_t, heap, removed_loop_vec);
2244 }
2245
2246 \f
2247
2248 /* At this point true value of allocno attribute bad_spill_p means
2249    that there is an insn where allocno occurs and where the allocno
2250    can not be used as memory.  The function updates the attribute, now
2251    it can be true only for allocnos which can not be used as memory in
2252    an insn and in whose live ranges there is other allocno deaths.
2253    Spilling allocnos with true value will not improve the code because
2254    it will not make other allocnos colorable and additional reloads
2255    for the corresponding pseudo will be generated in reload pass for
2256    each insn it occurs.
2257
2258    This is a trick mentioned in one classic article of Chaitin etc
2259    which is frequently omitted in other implementations of RA based on
2260    graph coloring.  */
2261 static void
2262 update_bad_spill_attribute (void)
2263 {
2264   int i;
2265   ira_allocno_t a;
2266   ira_allocno_iterator ai;
2267   ira_allocno_object_iterator aoi;
2268   ira_object_t obj;
2269   live_range_t r;
2270   enum reg_class aclass;
2271   bitmap_head dead_points[N_REG_CLASSES];
2272
2273   for (i = 0; i < ira_allocno_classes_num; i++)
2274     {
2275       aclass = ira_allocno_classes[i];
2276       bitmap_initialize (&dead_points[aclass], &reg_obstack);
2277     }
2278   FOR_EACH_ALLOCNO (a, ai)
2279     {
2280       aclass = ALLOCNO_CLASS (a);
2281       if (aclass == NO_REGS)
2282         continue;
2283       FOR_EACH_ALLOCNO_OBJECT (a, obj, aoi)
2284         for (r = OBJECT_LIVE_RANGES (obj); r != NULL; r = r->next)
2285           bitmap_set_bit (&dead_points[aclass], r->finish);
2286     }
2287   FOR_EACH_ALLOCNO (a, ai)
2288     {
2289       aclass = ALLOCNO_CLASS (a);
2290       if (aclass == NO_REGS)
2291         continue;
2292       if (! ALLOCNO_BAD_SPILL_P (a))
2293         continue;
2294       FOR_EACH_ALLOCNO_OBJECT (a, obj, aoi)
2295         {
2296           for (r = OBJECT_LIVE_RANGES (obj); r != NULL; r = r->next)
2297             {
2298               for (i = r->start + 1; i < r->finish; i++)
2299                 if (bitmap_bit_p (&dead_points[aclass], i))
2300                   break;
2301               if (i < r->finish)
2302                 break;
2303             }
2304           if (r != NULL)
2305             {
2306               ALLOCNO_BAD_SPILL_P (a) = false;
2307               break;
2308             }
2309         }
2310     }
2311   for (i = 0; i < ira_allocno_classes_num; i++)
2312     {
2313       aclass = ira_allocno_classes[i];
2314       bitmap_clear (&dead_points[aclass]);
2315     }
2316 }
2317
2318 \f
2319
2320 /* Set up minimal and maximal live range points for allocnos.  */
2321 static void
2322 setup_min_max_allocno_live_range_point (void)
2323 {
2324   int i;
2325   ira_allocno_t a, parent_a, cap;
2326   ira_allocno_iterator ai;
2327 #ifdef ENABLE_IRA_CHECKING
2328   ira_object_iterator oi;
2329   ira_object_t obj;
2330 #endif
2331   live_range_t r;
2332   ira_loop_tree_node_t parent;
2333
2334   FOR_EACH_ALLOCNO (a, ai)
2335     {
2336       int n = ALLOCNO_NUM_OBJECTS (a);
2337
2338       for (i = 0; i < n; i++)
2339         {
2340           ira_object_t obj = ALLOCNO_OBJECT (a, i);
2341           r = OBJECT_LIVE_RANGES (obj);
2342           if (r == NULL)
2343             continue;
2344           OBJECT_MAX (obj) = r->finish;
2345           for (; r->next != NULL; r = r->next)
2346             ;
2347           OBJECT_MIN (obj) = r->start;
2348         }
2349     }
2350   for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--)
2351     for (a = ira_regno_allocno_map[i];
2352          a != NULL;
2353          a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
2354       {
2355         int j;
2356         int n = ALLOCNO_NUM_OBJECTS (a);
2357
2358         for (j = 0; j < n; j++)
2359           {
2360             ira_object_t obj = ALLOCNO_OBJECT (a, j);
2361             ira_object_t parent_obj;
2362
2363             if (OBJECT_MAX (obj) < 0)
2364               continue;
2365             ira_assert (ALLOCNO_CAP_MEMBER (a) == NULL);
2366             /* Accumulation of range info.  */
2367             if (ALLOCNO_CAP (a) != NULL)
2368               {
2369                 for (cap = ALLOCNO_CAP (a); cap != NULL; cap = ALLOCNO_CAP (cap))
2370                   {
2371                     ira_object_t cap_obj = ALLOCNO_OBJECT (cap, j);
2372                     if (OBJECT_MAX (cap_obj) < OBJECT_MAX (obj))
2373                       OBJECT_MAX (cap_obj) = OBJECT_MAX (obj);
2374                     if (OBJECT_MIN (cap_obj) > OBJECT_MIN (obj))
2375                       OBJECT_MIN (cap_obj) = OBJECT_MIN (obj);
2376                   }
2377                 continue;
2378               }
2379             if ((parent = ALLOCNO_LOOP_TREE_NODE (a)->parent) == NULL)
2380               continue;
2381             parent_a = parent->regno_allocno_map[i];
2382             parent_obj = ALLOCNO_OBJECT (parent_a, j);
2383             if (OBJECT_MAX (parent_obj) < OBJECT_MAX (obj))
2384               OBJECT_MAX (parent_obj) = OBJECT_MAX (obj);
2385             if (OBJECT_MIN (parent_obj) > OBJECT_MIN (obj))
2386               OBJECT_MIN (parent_obj) = OBJECT_MIN (obj);
2387           }
2388       }
2389 #ifdef ENABLE_IRA_CHECKING
2390   FOR_EACH_OBJECT (obj, oi)
2391     {
2392       if ((0 <= OBJECT_MIN (obj) && OBJECT_MIN (obj) <= ira_max_point)
2393           && (0 <= OBJECT_MAX (obj) && OBJECT_MAX (obj) <= ira_max_point))
2394         continue;
2395       gcc_unreachable ();
2396     }
2397 #endif
2398 }
2399
2400 /* Sort allocnos according to their live ranges.  Allocnos with
2401    smaller allocno class are put first unless we use priority
2402    coloring.  Allocnos with the same class are ordered according
2403    their start (min).  Allocnos with the same start are ordered
2404    according their finish (max).  */
2405 static int
2406 object_range_compare_func (const void *v1p, const void *v2p)
2407 {
2408   int diff;
2409   ira_object_t obj1 = *(const ira_object_t *) v1p;
2410   ira_object_t obj2 = *(const ira_object_t *) v2p;
2411   ira_allocno_t a1 = OBJECT_ALLOCNO (obj1);
2412   ira_allocno_t a2 = OBJECT_ALLOCNO (obj2);
2413
2414   if ((diff = OBJECT_MIN (obj1) - OBJECT_MIN (obj2)) != 0)
2415     return diff;
2416   if ((diff = OBJECT_MAX (obj1) - OBJECT_MAX (obj2)) != 0)
2417      return diff;
2418   return ALLOCNO_NUM (a1) - ALLOCNO_NUM (a2);
2419 }
2420
2421 /* Sort ira_object_id_map and set up conflict id of allocnos.  */
2422 static void
2423 sort_conflict_id_map (void)
2424 {
2425   int i, num;
2426   ira_allocno_t a;
2427   ira_allocno_iterator ai;
2428
2429   num = 0;
2430   FOR_EACH_ALLOCNO (a, ai)
2431     {
2432       ira_allocno_object_iterator oi;
2433       ira_object_t obj;
2434
2435       FOR_EACH_ALLOCNO_OBJECT (a, obj, oi)
2436         ira_object_id_map[num++] = obj;
2437     }
2438   qsort (ira_object_id_map, num, sizeof (ira_object_t),
2439          object_range_compare_func);
2440   for (i = 0; i < num; i++)
2441     {
2442       ira_object_t obj = ira_object_id_map[i];
2443
2444       gcc_assert (obj != NULL);
2445       OBJECT_CONFLICT_ID (obj) = i;
2446     }
2447   for (i = num; i < ira_objects_num; i++)
2448     ira_object_id_map[i] = NULL;
2449 }
2450
2451 /* Set up minimal and maximal conflict ids of allocnos with which
2452    given allocno can conflict.  */
2453 static void
2454 setup_min_max_conflict_allocno_ids (void)
2455 {
2456   int aclass;
2457   int i, j, min, max, start, finish, first_not_finished, filled_area_start;
2458   int *live_range_min, *last_lived;
2459   int word0_min, word0_max;
2460   ira_allocno_t a;
2461   ira_allocno_iterator ai;
2462
2463   live_range_min = (int *) ira_allocate (sizeof (int) * ira_objects_num);
2464   aclass = -1;
2465   first_not_finished = -1;
2466   for (i = 0; i < ira_objects_num; i++)
2467     {
2468       ira_object_t obj = ira_object_id_map[i];
2469
2470       if (obj == NULL)
2471         continue;
2472
2473       a = OBJECT_ALLOCNO (obj);
2474
2475       if (aclass < 0)
2476         {
2477           aclass = ALLOCNO_CLASS (a);
2478           min = i;
2479           first_not_finished = i;
2480         }
2481       else
2482         {
2483           start = OBJECT_MIN (obj);
2484           /* If we skip an allocno, the allocno with smaller ids will
2485              be also skipped because of the secondary sorting the
2486              range finishes (see function
2487              object_range_compare_func).  */
2488           while (first_not_finished < i
2489                  && start > OBJECT_MAX (ira_object_id_map
2490                                         [first_not_finished]))
2491             first_not_finished++;
2492           min = first_not_finished;
2493         }
2494       if (min == i)
2495         /* We could increase min further in this case but it is good
2496            enough.  */
2497         min++;
2498       live_range_min[i] = OBJECT_MIN (obj);
2499       OBJECT_MIN (obj) = min;
2500     }
2501   last_lived = (int *) ira_allocate (sizeof (int) * ira_max_point);
2502   aclass = -1;
2503   filled_area_start = -1;
2504   for (i = ira_objects_num - 1; i >= 0; i--)
2505     {
2506       ira_object_t obj = ira_object_id_map[i];
2507
2508       if (obj == NULL)
2509         continue;
2510
2511       a = OBJECT_ALLOCNO (obj);
2512       if (aclass < 0)
2513         {
2514           aclass = ALLOCNO_CLASS (a);
2515           for (j = 0; j < ira_max_point; j++)
2516             last_lived[j] = -1;
2517           filled_area_start = ira_max_point;
2518         }
2519       min = live_range_min[i];
2520       finish = OBJECT_MAX (obj);
2521       max = last_lived[finish];
2522       if (max < 0)
2523         /* We could decrease max further in this case but it is good
2524            enough.  */
2525         max = OBJECT_CONFLICT_ID (obj) - 1;
2526       OBJECT_MAX (obj) = max;
2527       /* In filling, we can go further A range finish to recognize
2528          intersection quickly because if the finish of subsequently
2529          processed allocno (it has smaller conflict id) range is
2530          further A range finish than they are definitely intersected
2531          (the reason for this is the allocnos with bigger conflict id
2532          have their range starts not smaller than allocnos with
2533          smaller ids.  */
2534       for (j = min; j < filled_area_start; j++)
2535         last_lived[j] = i;
2536       filled_area_start = min;
2537     }
2538   ira_free (last_lived);
2539   ira_free (live_range_min);
2540
2541   /* For allocnos with more than one object, we may later record extra conflicts in
2542      subobject 0 that we cannot really know about here.
2543      For now, simply widen the min/max range of these subobjects.  */
2544
2545   word0_min = INT_MAX;
2546   word0_max = INT_MIN;
2547
2548   FOR_EACH_ALLOCNO (a, ai)
2549     {
2550       int n = ALLOCNO_NUM_OBJECTS (a);
2551       ira_object_t obj0;
2552
2553       if (n < 2)
2554         continue;
2555       obj0 = ALLOCNO_OBJECT (a, 0);
2556       if (OBJECT_CONFLICT_ID (obj0) < word0_min)
2557         word0_min = OBJECT_CONFLICT_ID (obj0);
2558       if (OBJECT_CONFLICT_ID (obj0) > word0_max)
2559         word0_max = OBJECT_CONFLICT_ID (obj0);
2560     }
2561   FOR_EACH_ALLOCNO (a, ai)
2562     {
2563       int n = ALLOCNO_NUM_OBJECTS (a);
2564       ira_object_t obj0;
2565
2566       if (n < 2)
2567         continue;
2568       obj0 = ALLOCNO_OBJECT (a, 0);
2569       if (OBJECT_MIN (obj0) > word0_min)
2570         OBJECT_MIN (obj0) = word0_min;
2571       if (OBJECT_MAX (obj0) < word0_max)
2572         OBJECT_MAX (obj0) = word0_max;
2573     }
2574 }
2575
2576 \f
2577
2578 static void
2579 create_caps (void)
2580 {
2581   ira_allocno_t a;
2582   ira_allocno_iterator ai;
2583   ira_loop_tree_node_t loop_tree_node;
2584
2585   FOR_EACH_ALLOCNO (a, ai)
2586     {
2587       if (ALLOCNO_LOOP_TREE_NODE (a) == ira_loop_tree_root)
2588         continue;
2589       if (ALLOCNO_CAP_MEMBER (a) != NULL)
2590         create_cap_allocno (a);
2591       else if (ALLOCNO_CAP (a) == NULL)
2592         {
2593           loop_tree_node = ALLOCNO_LOOP_TREE_NODE (a);
2594           if (!bitmap_bit_p (loop_tree_node->border_allocnos, ALLOCNO_NUM (a)))
2595             create_cap_allocno (a);
2596         }
2597     }
2598 }
2599
2600 \f
2601
2602 /* The page contains code transforming more one region internal
2603    representation (IR) to one region IR which is necessary for reload.
2604    This transformation is called IR flattening.  We might just rebuild
2605    the IR for one region but we don't do it because it takes a lot of
2606    time.  */
2607
2608 /* Map: regno -> allocnos which will finally represent the regno for
2609    IR with one region.  */
2610 static ira_allocno_t *regno_top_level_allocno_map;
2611
2612 /* Find the allocno that corresponds to A at a level one higher up in the
2613    loop tree.  Returns NULL if A is a cap, or if it has no parent.  */
2614 ira_allocno_t
2615 ira_parent_allocno (ira_allocno_t a)
2616 {
2617   ira_loop_tree_node_t parent;
2618
2619   if (ALLOCNO_CAP (a) != NULL)
2620     return NULL;
2621
2622   parent = ALLOCNO_LOOP_TREE_NODE (a)->parent;
2623   if (parent == NULL)
2624     return NULL;
2625
2626   return parent->regno_allocno_map[ALLOCNO_REGNO (a)];
2627 }
2628
2629 /* Find the allocno that corresponds to A at a level one higher up in the
2630    loop tree.  If ALLOCNO_CAP is set for A, return that.  */
2631 ira_allocno_t
2632 ira_parent_or_cap_allocno (ira_allocno_t a)
2633 {
2634   if (ALLOCNO_CAP (a) != NULL)
2635     return ALLOCNO_CAP (a);
2636
2637   return ira_parent_allocno (a);
2638 }
2639
2640 /* Process all allocnos originated from pseudo REGNO and copy live
2641    ranges, hard reg conflicts, and allocno stack reg attributes from
2642    low level allocnos to final allocnos which are destinations of
2643    removed stores at a loop exit.  Return true if we copied live
2644    ranges.  */
2645 static bool
2646 copy_info_to_removed_store_destinations (int regno)
2647 {
2648   ira_allocno_t a;
2649   ira_allocno_t parent_a = NULL;
2650   ira_loop_tree_node_t parent;
2651   bool merged_p;
2652
2653   merged_p = false;
2654   for (a = ira_regno_allocno_map[regno];
2655        a != NULL;
2656        a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
2657     {
2658       if (a != regno_top_level_allocno_map[REGNO (allocno_emit_reg (a))])
2659         /* This allocno will be removed.  */
2660         continue;
2661
2662       /* Caps will be removed.  */
2663       ira_assert (ALLOCNO_CAP_MEMBER (a) == NULL);
2664       for (parent = ALLOCNO_LOOP_TREE_NODE (a)->parent;
2665            parent != NULL;
2666            parent = parent->parent)
2667         if ((parent_a = parent->regno_allocno_map[regno]) == NULL
2668             || (parent_a
2669                 == regno_top_level_allocno_map[REGNO
2670                                                (allocno_emit_reg (parent_a))]
2671                 && ALLOCNO_EMIT_DATA (parent_a)->mem_optimized_dest_p))
2672           break;
2673       if (parent == NULL || parent_a == NULL)
2674         continue;
2675
2676       copy_allocno_live_ranges (a, parent_a);
2677       merge_hard_reg_conflicts (a, parent_a, true);
2678
2679       ALLOCNO_CALL_FREQ (parent_a) += ALLOCNO_CALL_FREQ (a);
2680       ALLOCNO_CALLS_CROSSED_NUM (parent_a)
2681         += ALLOCNO_CALLS_CROSSED_NUM (a);
2682       ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (parent_a)
2683         += ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a);
2684       merged_p = true;
2685     }
2686   return merged_p;
2687 }
2688
2689 /* Flatten the IR.  In other words, this function transforms IR as if
2690    it were built with one region (without loops).  We could make it
2691    much simpler by rebuilding IR with one region, but unfortunately it
2692    takes a lot of time.  MAX_REGNO_BEFORE_EMIT and
2693    IRA_MAX_POINT_BEFORE_EMIT are correspondingly MAX_REG_NUM () and
2694    IRA_MAX_POINT before emitting insns on the loop borders.  */
2695 void
2696 ira_flattening (int max_regno_before_emit, int ira_max_point_before_emit)
2697 {
2698   int i, j;
2699   bool keep_p;
2700   int hard_regs_num;
2701   bool new_pseudos_p, merged_p, mem_dest_p;
2702   unsigned int n;
2703   enum reg_class aclass;
2704   ira_allocno_t a, parent_a, first, second, node_first, node_second;
2705   ira_copy_t cp;
2706   ira_loop_tree_node_t node;
2707   live_range_t r;
2708   ira_allocno_iterator ai;
2709   ira_copy_iterator ci;
2710
2711   regno_top_level_allocno_map
2712     = (ira_allocno_t *) ira_allocate (max_reg_num ()
2713                                       * sizeof (ira_allocno_t));
2714   memset (regno_top_level_allocno_map, 0,
2715           max_reg_num () * sizeof (ira_allocno_t));
2716   new_pseudos_p = merged_p = false;
2717   FOR_EACH_ALLOCNO (a, ai)
2718     {
2719       ira_allocno_object_iterator oi;
2720       ira_object_t obj;
2721
2722       if (ALLOCNO_CAP_MEMBER (a) != NULL)
2723         /* Caps are not in the regno allocno maps and they are never
2724            will be transformed into allocnos existing after IR
2725            flattening.  */
2726         continue;
2727       FOR_EACH_ALLOCNO_OBJECT (a, obj, oi)
2728         COPY_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj),
2729                            OBJECT_CONFLICT_HARD_REGS (obj));
2730 #ifdef STACK_REGS
2731       ALLOCNO_TOTAL_NO_STACK_REG_P (a) = ALLOCNO_NO_STACK_REG_P (a);
2732 #endif
2733     }
2734   /* Fix final allocno attributes.  */
2735   for (i = max_regno_before_emit - 1; i >= FIRST_PSEUDO_REGISTER; i--)
2736     {
2737       mem_dest_p = false;
2738       for (a = ira_regno_allocno_map[i];
2739            a != NULL;
2740            a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
2741         {
2742           ira_emit_data_t parent_data, data = ALLOCNO_EMIT_DATA (a);
2743
2744           ira_assert (ALLOCNO_CAP_MEMBER (a) == NULL);
2745           if (data->somewhere_renamed_p)
2746             new_pseudos_p = true;
2747           parent_a = ira_parent_allocno (a);
2748           if (parent_a == NULL)
2749             {
2750               ALLOCNO_COPIES (a) = NULL;
2751               regno_top_level_allocno_map[REGNO (data->reg)] = a;
2752               continue;
2753             }
2754           ira_assert (ALLOCNO_CAP_MEMBER (parent_a) == NULL);
2755
2756           if (data->mem_optimized_dest != NULL)
2757             mem_dest_p = true;
2758           parent_data = ALLOCNO_EMIT_DATA (parent_a);
2759           if (REGNO (data->reg) == REGNO (parent_data->reg))
2760             {
2761               merge_hard_reg_conflicts (a, parent_a, true);
2762               move_allocno_live_ranges (a, parent_a);
2763               merged_p = true;
2764               parent_data->mem_optimized_dest_p
2765                 = (parent_data->mem_optimized_dest_p
2766                    || data->mem_optimized_dest_p);
2767               continue;
2768             }
2769           new_pseudos_p = true;
2770           for (;;)
2771             {
2772               ALLOCNO_NREFS (parent_a) -= ALLOCNO_NREFS (a);
2773               ALLOCNO_FREQ (parent_a) -= ALLOCNO_FREQ (a);
2774               ALLOCNO_CALL_FREQ (parent_a) -= ALLOCNO_CALL_FREQ (a);
2775               ALLOCNO_CALLS_CROSSED_NUM (parent_a)
2776                 -= ALLOCNO_CALLS_CROSSED_NUM (a);
2777               ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (parent_a)
2778                 -= ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a);
2779               ira_assert (ALLOCNO_CALLS_CROSSED_NUM (parent_a) >= 0
2780                           && ALLOCNO_NREFS (parent_a) >= 0
2781                           && ALLOCNO_FREQ (parent_a) >= 0);
2782               aclass = ALLOCNO_CLASS (parent_a);
2783               hard_regs_num = ira_class_hard_regs_num[aclass];
2784               if (ALLOCNO_HARD_REG_COSTS (a) != NULL
2785                   && ALLOCNO_HARD_REG_COSTS (parent_a) != NULL)
2786                 for (j = 0; j < hard_regs_num; j++)
2787                   ALLOCNO_HARD_REG_COSTS (parent_a)[j]
2788                     -= ALLOCNO_HARD_REG_COSTS (a)[j];
2789               if (ALLOCNO_CONFLICT_HARD_REG_COSTS (a) != NULL
2790                   && ALLOCNO_CONFLICT_HARD_REG_COSTS (parent_a) != NULL)
2791                 for (j = 0; j < hard_regs_num; j++)
2792                   ALLOCNO_CONFLICT_HARD_REG_COSTS (parent_a)[j]
2793                     -= ALLOCNO_CONFLICT_HARD_REG_COSTS (a)[j];
2794               ALLOCNO_CLASS_COST (parent_a)
2795                 -= ALLOCNO_CLASS_COST (a);
2796               ALLOCNO_MEMORY_COST (parent_a) -= ALLOCNO_MEMORY_COST (a);
2797               parent_a = ira_parent_allocno (parent_a);
2798               if (parent_a == NULL)
2799                 break;
2800             }
2801           ALLOCNO_COPIES (a) = NULL;
2802           regno_top_level_allocno_map[REGNO (data->reg)] = a;
2803         }
2804       if (mem_dest_p && copy_info_to_removed_store_destinations (i))
2805         merged_p = true;
2806     }
2807   ira_assert (new_pseudos_p || ira_max_point_before_emit == ira_max_point);
2808   if (merged_p || ira_max_point_before_emit != ira_max_point)
2809     ira_rebuild_start_finish_chains ();
2810   if (new_pseudos_p)
2811     {
2812       sparseset objects_live;
2813
2814       /* Rebuild conflicts.  */
2815       FOR_EACH_ALLOCNO (a, ai)
2816         {
2817           ira_allocno_object_iterator oi;
2818           ira_object_t obj;
2819
2820           if (a != regno_top_level_allocno_map[REGNO (allocno_emit_reg (a))]
2821               || ALLOCNO_CAP_MEMBER (a) != NULL)
2822             continue;
2823           FOR_EACH_ALLOCNO_OBJECT (a, obj, oi)
2824             {
2825               for (r = OBJECT_LIVE_RANGES (obj); r != NULL; r = r->next)
2826                 ira_assert (r->object == obj);
2827               clear_conflicts (obj);
2828             }
2829         }
2830       objects_live = sparseset_alloc (ira_objects_num);
2831       for (i = 0; i < ira_max_point; i++)
2832         {
2833           for (r = ira_start_point_ranges[i]; r != NULL; r = r->start_next)
2834             {
2835               ira_object_t obj = r->object;
2836
2837               a = OBJECT_ALLOCNO (obj);
2838               if (a != regno_top_level_allocno_map[REGNO (allocno_emit_reg (a))]
2839                   || ALLOCNO_CAP_MEMBER (a) != NULL)
2840                 continue;
2841
2842               aclass = ALLOCNO_CLASS (a);
2843               sparseset_set_bit (objects_live, OBJECT_CONFLICT_ID (obj));
2844               EXECUTE_IF_SET_IN_SPARSESET (objects_live, n)
2845                 {
2846                   ira_object_t live_obj = ira_object_id_map[n];
2847                   ira_allocno_t live_a = OBJECT_ALLOCNO (live_obj);
2848                   enum reg_class live_aclass = ALLOCNO_CLASS (live_a);
2849
2850                   if (ira_reg_classes_intersect_p[aclass][live_aclass]
2851                       /* Don't set up conflict for the allocno with itself.  */
2852                       && live_a != a)
2853                     ira_add_conflict (obj, live_obj);
2854                 }
2855             }
2856
2857           for (r = ira_finish_point_ranges[i]; r != NULL; r = r->finish_next)
2858             sparseset_clear_bit (objects_live, OBJECT_CONFLICT_ID (r->object));
2859         }
2860       sparseset_free (objects_live);
2861       compress_conflict_vecs ();
2862     }
2863   /* Mark some copies for removing and change allocnos in the rest
2864      copies.  */
2865   FOR_EACH_COPY (cp, ci)
2866     {
2867       if (ALLOCNO_CAP_MEMBER (cp->first) != NULL
2868           || ALLOCNO_CAP_MEMBER (cp->second) != NULL)
2869         {
2870           if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL)
2871             fprintf
2872               (ira_dump_file, "      Remove cp%d:%c%dr%d-%c%dr%d\n",
2873                cp->num, ALLOCNO_CAP_MEMBER (cp->first) != NULL ? 'c' : 'a',
2874                ALLOCNO_NUM (cp->first),
2875                REGNO (allocno_emit_reg (cp->first)),
2876                ALLOCNO_CAP_MEMBER (cp->second) != NULL ? 'c' : 'a',
2877                ALLOCNO_NUM (cp->second),
2878                REGNO (allocno_emit_reg (cp->second)));
2879           cp->loop_tree_node = NULL;
2880           continue;
2881         }
2882       first
2883         = regno_top_level_allocno_map[REGNO (allocno_emit_reg (cp->first))];
2884       second
2885         = regno_top_level_allocno_map[REGNO (allocno_emit_reg (cp->second))];
2886       node = cp->loop_tree_node;
2887       if (node == NULL)
2888         keep_p = true; /* It copy generated in ira-emit.c.  */
2889       else
2890         {
2891           /* Check that the copy was not propagated from level on
2892              which we will have different pseudos.  */
2893           node_first = node->regno_allocno_map[ALLOCNO_REGNO (cp->first)];
2894           node_second = node->regno_allocno_map[ALLOCNO_REGNO (cp->second)];
2895           keep_p = ((REGNO (allocno_emit_reg (first))
2896                      == REGNO (allocno_emit_reg (node_first)))
2897                      && (REGNO (allocno_emit_reg (second))
2898                          == REGNO (allocno_emit_reg (node_second))));
2899         }
2900       if (keep_p)
2901         {
2902           cp->loop_tree_node = ira_loop_tree_root;
2903           cp->first = first;
2904           cp->second = second;
2905         }
2906       else
2907         {
2908           cp->loop_tree_node = NULL;
2909           if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL)
2910             fprintf (ira_dump_file, "      Remove cp%d:a%dr%d-a%dr%d\n",
2911                      cp->num, ALLOCNO_NUM (cp->first),
2912                      REGNO (allocno_emit_reg (cp->first)),
2913                      ALLOCNO_NUM (cp->second),
2914                      REGNO (allocno_emit_reg (cp->second)));
2915         }
2916     }
2917   /* Remove unnecessary allocnos on lower levels of the loop tree.  */
2918   FOR_EACH_ALLOCNO (a, ai)
2919     {
2920       if (a != regno_top_level_allocno_map[REGNO (allocno_emit_reg (a))]
2921           || ALLOCNO_CAP_MEMBER (a) != NULL)
2922         {
2923           if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL)
2924             fprintf (ira_dump_file, "      Remove a%dr%d\n",
2925                      ALLOCNO_NUM (a), REGNO (allocno_emit_reg (a)));
2926           finish_allocno (a);
2927           continue;
2928         }
2929       ALLOCNO_LOOP_TREE_NODE (a) = ira_loop_tree_root;
2930       ALLOCNO_REGNO (a) = REGNO (allocno_emit_reg (a));
2931       ALLOCNO_CAP (a) = NULL;
2932       /* Restore updated costs for assignments from reload.  */
2933       ALLOCNO_UPDATED_MEMORY_COST (a) = ALLOCNO_MEMORY_COST (a);
2934       ALLOCNO_UPDATED_CLASS_COST (a) = ALLOCNO_CLASS_COST (a);
2935       if (! ALLOCNO_ASSIGNED_P (a))
2936         ira_free_allocno_updated_costs (a);
2937       ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL);
2938       ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) == NULL);
2939     }
2940   /* Remove unnecessary copies.  */
2941   FOR_EACH_COPY (cp, ci)
2942     {
2943       if (cp->loop_tree_node == NULL)
2944         {
2945           ira_copies[cp->num] = NULL;
2946           finish_copy (cp);
2947           continue;
2948         }
2949       ira_assert
2950         (ALLOCNO_LOOP_TREE_NODE (cp->first) == ira_loop_tree_root
2951          && ALLOCNO_LOOP_TREE_NODE (cp->second) == ira_loop_tree_root);
2952       ira_add_allocno_copy_to_list (cp);
2953       ira_swap_allocno_copy_ends_if_necessary (cp);
2954     }
2955   rebuild_regno_allocno_maps ();
2956   if (ira_max_point != ira_max_point_before_emit)
2957     ira_compress_allocno_live_ranges ();
2958   ira_free (regno_top_level_allocno_map);
2959 }
2960
2961 \f
2962
2963 #ifdef ENABLE_IRA_CHECKING
2964 /* Check creation of all allocnos.  Allocnos on lower levels should
2965    have allocnos or caps on all upper levels.  */
2966 static void
2967 check_allocno_creation (void)
2968 {
2969   ira_allocno_t a;
2970   ira_allocno_iterator ai;
2971   ira_loop_tree_node_t loop_tree_node;
2972
2973   FOR_EACH_ALLOCNO (a, ai)
2974     {
2975       loop_tree_node = ALLOCNO_LOOP_TREE_NODE (a);
2976       ira_assert (bitmap_bit_p (loop_tree_node->all_allocnos,
2977                                 ALLOCNO_NUM (a)));
2978       if (loop_tree_node == ira_loop_tree_root)
2979         continue;
2980       if (ALLOCNO_CAP_MEMBER (a) != NULL)
2981         ira_assert (ALLOCNO_CAP (a) != NULL);
2982       else if (ALLOCNO_CAP (a) == NULL)
2983         ira_assert (loop_tree_node->parent
2984                     ->regno_allocno_map[ALLOCNO_REGNO (a)] != NULL
2985                     && bitmap_bit_p (loop_tree_node->border_allocnos,
2986                                      ALLOCNO_NUM (a)));
2987     }
2988 }
2989 #endif
2990
2991 /* Identify allocnos which prefer a register class with a single hard register.
2992    Adjust ALLOCNO_CONFLICT_HARD_REG_COSTS so that conflicting allocnos are
2993    less likely to use the preferred singleton register.  */
2994 static void
2995 update_conflict_hard_reg_costs (void)
2996 {
2997   ira_allocno_t a;
2998   ira_allocno_iterator ai;
2999   int i, index, min;
3000
3001   FOR_EACH_ALLOCNO (a, ai)
3002     {
3003       reg_class_t aclass = ALLOCNO_CLASS (a);
3004       reg_class_t pref = reg_preferred_class (ALLOCNO_REGNO (a));
3005
3006       if (reg_class_size[(int) pref] != 1)
3007         continue;
3008       index = ira_class_hard_reg_index[(int) aclass]
3009                                       [ira_class_hard_regs[(int) pref][0]];
3010       if (index < 0)
3011         continue;
3012       if (ALLOCNO_CONFLICT_HARD_REG_COSTS (a) == NULL
3013           || ALLOCNO_HARD_REG_COSTS (a) == NULL)
3014         continue;
3015       min = INT_MAX;
3016       for (i = ira_class_hard_regs_num[(int) aclass] - 1; i >= 0; i--)
3017         if (ALLOCNO_HARD_REG_COSTS (a)[i] > ALLOCNO_CLASS_COST (a)
3018             && min > ALLOCNO_HARD_REG_COSTS (a)[i])
3019           min = ALLOCNO_HARD_REG_COSTS (a)[i];
3020       if (min == INT_MAX)
3021         continue;
3022       ira_allocate_and_set_costs (&ALLOCNO_CONFLICT_HARD_REG_COSTS (a),
3023                                   aclass, 0);
3024       ALLOCNO_CONFLICT_HARD_REG_COSTS (a)[index]
3025         -= min - ALLOCNO_CLASS_COST (a);
3026     }
3027 }
3028
3029 /* Create a internal representation (IR) for IRA (allocnos, copies,
3030    loop tree nodes).  If LOOPS_P is FALSE the nodes corresponding to
3031    the loops (except the root which corresponds the all function) and
3032    correspondingly allocnos for the loops will be not created.  Such
3033    parameter value is used for Chaitin-Briggs coloring.  The function
3034    returns TRUE if we generate loop structure (besides nodes
3035    representing all function and the basic blocks) for regional
3036    allocation.  A true return means that we really need to flatten IR
3037    before the reload.  */
3038 bool
3039 ira_build (bool loops_p)
3040 {
3041   df_analyze ();
3042
3043   initiate_cost_vectors ();
3044   initiate_allocnos ();
3045   initiate_copies ();
3046   create_loop_tree_nodes (loops_p);
3047   form_loop_tree ();
3048   create_allocnos ();
3049   ira_costs ();
3050   create_allocno_objects ();
3051   ira_create_allocno_live_ranges ();
3052   remove_unnecessary_regions (false);
3053   ira_compress_allocno_live_ranges ();
3054   update_bad_spill_attribute ();
3055   loops_p = more_one_region_p ();
3056   if (loops_p)
3057     {
3058       propagate_allocno_info ();
3059       create_caps ();
3060     }
3061   ira_tune_allocno_costs ();
3062 #ifdef ENABLE_IRA_CHECKING
3063   check_allocno_creation ();
3064 #endif
3065   setup_min_max_allocno_live_range_point ();
3066   sort_conflict_id_map ();
3067   setup_min_max_conflict_allocno_ids ();
3068   ira_build_conflicts ();
3069   update_conflict_hard_reg_costs ();
3070   if (! ira_conflicts_p)
3071     {
3072       ira_allocno_t a;
3073       ira_allocno_iterator ai;
3074
3075       /* Remove all regions but root one.  */
3076       if (loops_p)
3077         {
3078           remove_unnecessary_regions (true);
3079           loops_p = false;
3080         }
3081       /* We don't save hard registers around calls for fast allocation
3082          -- add caller clobbered registers as conflicting ones to
3083          allocno crossing calls.  */
3084       FOR_EACH_ALLOCNO (a, ai)
3085         if (ALLOCNO_CALLS_CROSSED_NUM (a) != 0)
3086           ior_hard_reg_conflicts (a, &call_used_reg_set);
3087     }
3088   if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
3089     print_copies (ira_dump_file);
3090   if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
3091     {
3092       int n, nr, nr_big;
3093       ira_allocno_t a;
3094       live_range_t r;
3095       ira_allocno_iterator ai;
3096
3097       n = 0;
3098       nr = 0;
3099       nr_big = 0;
3100       FOR_EACH_ALLOCNO (a, ai)
3101         {
3102           int j, nobj = ALLOCNO_NUM_OBJECTS (a);
3103
3104           if (nobj > 1)
3105             nr_big++;
3106           for (j = 0; j < nobj; j++)
3107             {
3108               ira_object_t obj = ALLOCNO_OBJECT (a, j);
3109               n += OBJECT_NUM_CONFLICTS (obj);
3110               for (r = OBJECT_LIVE_RANGES (obj); r != NULL; r = r->next)
3111                 nr++;
3112             }
3113         }
3114       fprintf (ira_dump_file, "  regions=%d, blocks=%d, points=%d\n",
3115                VEC_length (loop_p, ira_loops.larray), n_basic_blocks,
3116                ira_max_point);
3117       fprintf (ira_dump_file,
3118                "    allocnos=%d (big %d), copies=%d, conflicts=%d, ranges=%d\n",
3119                ira_allocnos_num, nr_big, ira_copies_num, n, nr);
3120     }
3121   return loops_p;
3122 }
3123
3124 /* Release the data created by function ira_build.  */
3125 void
3126 ira_destroy (void)
3127 {
3128   finish_loop_tree_nodes ();
3129   finish_copies ();
3130   finish_allocnos ();
3131   finish_cost_vectors ();
3132   ira_finish_allocno_live_ranges ();
3133 }