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