gcc/ira-build.c

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