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