gcc/ira-build.c

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