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].mentioned_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].mentioned_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->mentioned_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].mentioned_allocnos != NULL)
 216         ira_free_bitmap (ira_bb_nodes[i].mentioned_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_REVERSE (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   ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a) = NULL;
 441   ALLOCNO_CONFLICT_ALLOCNOS_NUM (a) = 0;
 442   COPY_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (a), ira_no_alloc_regs);
 443   COPY_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a), ira_no_alloc_regs);
 444   ALLOCNO_NREFS (a) = 0;
 445   ALLOCNO_FREQ (a) = 1;
 446   ALLOCNO_HARD_REGNO (a) = -1;
 447   ALLOCNO_CALL_FREQ (a) = 0;
 448   ALLOCNO_CALLS_CROSSED_NUM (a) = 0;
 449 #ifdef STACK_REGS
 450   ALLOCNO_NO_STACK_REG_P (a) = false;
 451   ALLOCNO_TOTAL_NO_STACK_REG_P (a) = false;
 452 #endif
 453   ALLOCNO_MEM_OPTIMIZED_DEST (a) = NULL;
 454   ALLOCNO_MEM_OPTIMIZED_DEST_P (a) = false;
 455   ALLOCNO_SOMEWHERE_RENAMED_P (a) = false;
 456   ALLOCNO_CHILD_RENAMED_P (a) = false;
 457   ALLOCNO_DONT_REASSIGN_P (a) = false;
 458   ALLOCNO_IN_GRAPH_P (a) = false;
 459   ALLOCNO_ASSIGNED_P (a) = false;
 460   ALLOCNO_MAY_BE_SPILLED_P (a) = false;
 461   ALLOCNO_SPLAY_REMOVED_P (a) = false;
 462   ALLOCNO_CONFLICT_VEC_P (a) = false;
 463   ALLOCNO_MODE (a) = (regno < 0 ? VOIDmode : PSEUDO_REGNO_MODE (regno));
 464   ALLOCNO_COPIES (a) = NULL;
 465   ALLOCNO_HARD_REG_COSTS (a) = NULL;
 466   ALLOCNO_CONFLICT_HARD_REG_COSTS (a) = NULL;
 467   ALLOCNO_UPDATED_HARD_REG_COSTS (a) = NULL;
 468   ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) = NULL;
 469   ALLOCNO_LEFT_CONFLICTS_NUM (a) = -1;
 470   ALLOCNO_COVER_CLASS (a) = NO_REGS;
 471   ALLOCNO_COVER_CLASS_COST (a) = 0;
 472   ALLOCNO_MEMORY_COST (a) = 0;
 473   ALLOCNO_UPDATED_MEMORY_COST (a) = 0;
 474   ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a) = 0;
 475   ALLOCNO_NEXT_BUCKET_ALLOCNO (a) = NULL;
 476   ALLOCNO_PREV_BUCKET_ALLOCNO (a) = NULL;
 477   ALLOCNO_FIRST_COALESCED_ALLOCNO (a) = a;
 478   ALLOCNO_NEXT_COALESCED_ALLOCNO (a) = a;
 479   ALLOCNO_LIVE_RANGES (a) = NULL;
 480   ALLOCNO_MIN (a) = INT_MAX;
 481   ALLOCNO_MAX (a) = -1;
 482   ALLOCNO_CONFLICT_ID (a) = ira_allocnos_num;
 483   VEC_safe_push (ira_allocno_t, heap, allocno_vec, a);
 484   ira_allocnos = VEC_address (ira_allocno_t, allocno_vec);
 485   ira_allocnos_num = VEC_length (ira_allocno_t, allocno_vec);
 486   VEC_safe_push (ira_allocno_t, heap, ira_conflict_id_allocno_map_vec, a);
 487   ira_conflict_id_allocno_map
 488     = VEC_address (ira_allocno_t, ira_conflict_id_allocno_map_vec);
 489   return a;
 490 }
 491
 492 /* Set up cover class for A and update its conflict hard registers.  */
 493 void
 494 ira_set_allocno_cover_class (ira_allocno_t a, enum reg_class cover_class)
 495 {
 496   ALLOCNO_COVER_CLASS (a) = cover_class;
 497   IOR_COMPL_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (a),
 498                           reg_class_contents[cover_class]);
 499   IOR_COMPL_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a),
 500                           reg_class_contents[cover_class]);
 501 }
 502
 503 /* Return TRUE if the conflict vector with NUM elements is more
 504    profitable than conflict bit vector for A.  */
 505 bool
 506 ira_conflict_vector_profitable_p (ira_allocno_t a, int num)
 507 {
 508   int nw;
 509
 510   if (ALLOCNO_MAX (a) < ALLOCNO_MIN (a))
 511     /* We prefer bit vector in such case because it does not result in
 512        allocation.  */
 513     return false;
 514
 515   nw = (ALLOCNO_MAX (a) - ALLOCNO_MIN (a) + IRA_INT_BITS) / IRA_INT_BITS;
 516   return (2 * sizeof (ira_allocno_t) * (num + 1)
 517           < 3 * nw * sizeof (IRA_INT_TYPE));
 518 }
 519
 520 /* Allocates and initialize the conflict vector of A for NUM
 521    conflicting allocnos.  */
 522 void
 523 ira_allocate_allocno_conflict_vec (ira_allocno_t a, int num)
 524 {
 525   int size;
 526   ira_allocno_t *vec;
 527
 528   ira_assert (ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a) == NULL);
 529   num++; /* for NULL end marker  */
 530   size = sizeof (ira_allocno_t) * num;
 531   ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a) = ira_allocate (size);
 532   vec = (ira_allocno_t *) ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a);
 533   vec[0] = NULL;
 534   ALLOCNO_CONFLICT_ALLOCNOS_NUM (a) = 0;
 535   ALLOCNO_CONFLICT_ALLOCNO_ARRAY_SIZE (a) = size;
 536   ALLOCNO_CONFLICT_VEC_P (a) = true;
 537 }
 538
 539 /* Allocate and initialize the conflict bit vector of A.  */
 540 static void
 541 allocate_allocno_conflict_bit_vec (ira_allocno_t a)
 542 {
 543   unsigned int size;
 544
 545   ira_assert (ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a) == NULL);
 546   size = ((ALLOCNO_MAX (a) - ALLOCNO_MIN (a) + IRA_INT_BITS)
 547           / IRA_INT_BITS * sizeof (IRA_INT_TYPE));
 548   ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a) = ira_allocate (size);
 549   memset (ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a), 0, size);
 550   ALLOCNO_CONFLICT_ALLOCNO_ARRAY_SIZE (a) = size;
 551   ALLOCNO_CONFLICT_VEC_P (a) = false;
 552 }
 553
 554 /* Allocate and initialize the conflict vector or conflict bit vector
 555    of A for NUM conflicting allocnos whatever is more profitable.  */
 556 void
 557 ira_allocate_allocno_conflicts (ira_allocno_t a, int num)
 558 {
 559   if (ira_conflict_vector_profitable_p (a, num))
 560     ira_allocate_allocno_conflict_vec (a, num);
 561   else
 562     allocate_allocno_conflict_bit_vec (a);
 563 }
 564
 565 /* Add A2 to the conflicts of A1.  */
 566 static void
 567 add_to_allocno_conflicts (ira_allocno_t a1, ira_allocno_t a2)
 568 {
 569   int num;
 570   unsigned int size;
 571
 572   if (ALLOCNO_CONFLICT_VEC_P (a1))
 573     {
 574       ira_allocno_t *vec;
 575
 576       num = ALLOCNO_CONFLICT_ALLOCNOS_NUM (a1) + 2;
 577       if (ALLOCNO_CONFLICT_ALLOCNO_ARRAY_SIZE (a1)
 578           >=  num * sizeof (ira_allocno_t))
 579         vec = (ira_allocno_t *) ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a1);
 580       else
 581         {
 582           size = (3 * num / 2 + 1) * sizeof (ira_allocno_t);
 583           vec = (ira_allocno_t *) ira_allocate (size);
 584           memcpy (vec, ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a1),
 585                   sizeof (ira_allocno_t) * ALLOCNO_CONFLICT_ALLOCNOS_NUM (a1));
 586           ira_free (ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a1));
 587           ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a1) = vec;
 588           ALLOCNO_CONFLICT_ALLOCNO_ARRAY_SIZE (a1) = size;
 589         }
 590       vec[num - 2] = a2;
 591       vec[num - 1] = NULL;
 592       ALLOCNO_CONFLICT_ALLOCNOS_NUM (a1)++;
 593     }
 594   else
 595     {
 596       int nw, added_head_nw, id;
 597       IRA_INT_TYPE *vec;
 598
 599       id = ALLOCNO_CONFLICT_ID (a2);
 600       vec = (IRA_INT_TYPE *) ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a1);
 601       if (ALLOCNO_MIN (a1) > id)
 602         {
 603           /* Expand head of the bit vector.  */
 604           added_head_nw = (ALLOCNO_MIN (a1) - id - 1) / IRA_INT_BITS + 1;
 605           nw = (ALLOCNO_MAX (a1) - ALLOCNO_MIN (a1)) / IRA_INT_BITS + 1;
 606           size = (nw + added_head_nw) * sizeof (IRA_INT_TYPE);
 607           if (ALLOCNO_CONFLICT_ALLOCNO_ARRAY_SIZE (a1) >= size)
 608             {
 609               memmove ((char *) vec + added_head_nw * sizeof (IRA_INT_TYPE),
 610                        vec, nw * sizeof (IRA_INT_TYPE));
 611               memset (vec, 0, added_head_nw * sizeof (IRA_INT_TYPE));
 612             }
 613           else
 614             {
 615               size
 616                 = (3 * (nw + added_head_nw) / 2 + 1) * sizeof (IRA_INT_TYPE);
 617               vec = (IRA_INT_TYPE *) ira_allocate (size);
 618               memcpy ((char *) vec + added_head_nw * sizeof (IRA_INT_TYPE),
 619                       ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a1),
 620                       nw * sizeof (IRA_INT_TYPE));
 621               memset (vec, 0, added_head_nw * sizeof (IRA_INT_TYPE));
 622               memset ((char *) vec
 623                       + (nw + added_head_nw) * sizeof (IRA_INT_TYPE),
 624                       0, size - (nw + added_head_nw) * sizeof (IRA_INT_TYPE));
 625               ira_free (ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a1));
 626               ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a1) = vec;
 627               ALLOCNO_CONFLICT_ALLOCNO_ARRAY_SIZE (a1) = size;
 628             }
 629           ALLOCNO_MIN (a1) -= added_head_nw * IRA_INT_BITS;
 630         }
 631       else if (ALLOCNO_MAX (a1) < id)
 632         {
 633           nw = (id - ALLOCNO_MIN (a1)) / IRA_INT_BITS + 1;
 634           size = nw * sizeof (IRA_INT_TYPE);
 635           if (ALLOCNO_CONFLICT_ALLOCNO_ARRAY_SIZE (a1) < size)
 636             {
 637               /* Expand tail of the bit vector.  */
 638               size = (3 * nw / 2 + 1) * sizeof (IRA_INT_TYPE);
 639               vec = (IRA_INT_TYPE *) ira_allocate (size);
 640               memcpy (vec, ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a1),
 641                       ALLOCNO_CONFLICT_ALLOCNO_ARRAY_SIZE (a1));
 642               memset ((char *) vec + ALLOCNO_CONFLICT_ALLOCNO_ARRAY_SIZE (a1),
 643                       0, size - ALLOCNO_CONFLICT_ALLOCNO_ARRAY_SIZE (a1));
 644               ira_free (ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a1));
 645               ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a1) = vec;
 646               ALLOCNO_CONFLICT_ALLOCNO_ARRAY_SIZE (a1) = size;
 647             }
 648           ALLOCNO_MAX (a1) = id;
 649         }
 650       SET_ALLOCNO_SET_BIT (vec, id, ALLOCNO_MIN (a1), ALLOCNO_MAX (a1));
 651     }
 652 }
 653
 654 /* Add A1 to the conflicts of A2 and vise versa.  */
 655 void
 656 ira_add_allocno_conflict (ira_allocno_t a1, ira_allocno_t a2)
 657 {
 658   add_to_allocno_conflicts (a1, a2);
 659   add_to_allocno_conflicts (a2, a1);
 660 }
 661
 662 /* Clear all conflicts of allocno A.  */
 663 static void
 664 clear_allocno_conflicts (ira_allocno_t a)
 665 {
 666   if (ALLOCNO_CONFLICT_VEC_P (a))
 667     {
 668       ALLOCNO_CONFLICT_ALLOCNOS_NUM (a) = 0;
 669       ((ira_allocno_t *) ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a))[0] = NULL;
 670     }
 671   else if (ALLOCNO_CONFLICT_ALLOCNO_ARRAY_SIZE (a) != 0)
 672     {
 673       int nw;
 674
 675       nw = (ALLOCNO_MAX (a) - ALLOCNO_MIN (a)) / IRA_INT_BITS + 1;
 676       memset (ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a), 0,
 677               nw * sizeof (IRA_INT_TYPE));
 678     }
 679 }
 680
 681 /* The array used to find duplications in conflict vectors of
 682    allocnos.  */
 683 static int *allocno_conflict_check;
 684
 685 /* The value used to mark allocation presence in conflict vector of
 686    the current allocno.  */
 687 static int curr_allocno_conflict_check_tick;
 688
 689 /* Remove duplications in conflict vector of A.  */
 690 static void
 691 compress_allocno_conflict_vec (ira_allocno_t a)
 692 {
 693   ira_allocno_t *vec, conflict_a;
 694   int i, j;
 695
 696   ira_assert (ALLOCNO_CONFLICT_VEC_P (a));
 697   vec = (ira_allocno_t *) ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a);
 698   curr_allocno_conflict_check_tick++;
 699   for (i = j = 0; (conflict_a = vec[i]) != NULL; i++)
 700     {
 701       if (allocno_conflict_check[ALLOCNO_NUM (conflict_a)]
 702           != curr_allocno_conflict_check_tick)
 703         {
 704           allocno_conflict_check[ALLOCNO_NUM (conflict_a)]
 705             = curr_allocno_conflict_check_tick;
 706           vec[j++] = conflict_a;
 707         }
 708     }
 709   ALLOCNO_CONFLICT_ALLOCNOS_NUM (a) = j;
 710   vec[j] = NULL;
 711 }
 712
 713 /* Remove duplications in conflict vectors of all allocnos.  */
 714 static void
 715 compress_conflict_vecs (void)
 716 {
 717   ira_allocno_t a;
 718   ira_allocno_iterator ai;
 719
 720   allocno_conflict_check
 721     = (int *) ira_allocate (sizeof (int) * ira_allocnos_num);
 722   memset (allocno_conflict_check, 0, sizeof (int) * ira_allocnos_num);
 723   curr_allocno_conflict_check_tick = 0;
 724   FOR_EACH_ALLOCNO (a, ai)
 725     if (ALLOCNO_CONFLICT_VEC_P (a))
 726       compress_allocno_conflict_vec (a);
 727   ira_free (allocno_conflict_check);
 728 }
 729
 730 /* This recursive function outputs allocno A and if it is a cap the
 731    function outputs its members.  */
 732 void
 733 ira_print_expanded_allocno (ira_allocno_t a)
 734 {
 735   basic_block bb;
 736
 737   fprintf (ira_dump_file, " a%d(r%d", ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
 738   if ((bb = ALLOCNO_LOOP_TREE_NODE (a)->bb) != NULL)
 739     fprintf (ira_dump_file, ",b%d", bb->index);
 740   else
 741     fprintf (ira_dump_file, ",l%d", ALLOCNO_LOOP_TREE_NODE (a)->loop->num);
 742   if (ALLOCNO_CAP_MEMBER (a) != NULL)
 743     {
 744       fprintf (ira_dump_file, ":");
 745       ira_print_expanded_allocno (ALLOCNO_CAP_MEMBER (a));
 746     }
 747   fprintf (ira_dump_file, ")");
 748 }
 749
 750 /* Create and return the cap representing allocno A in the
 751    parent loop.  */
 752 static ira_allocno_t
 753 create_cap_allocno (ira_allocno_t a)
 754 {
 755   ira_allocno_t cap;
 756   ira_loop_tree_node_t parent;
 757   enum reg_class cover_class;
 758
 759   ira_assert (ALLOCNO_FIRST_COALESCED_ALLOCNO (a) == a
 760               && ALLOCNO_NEXT_COALESCED_ALLOCNO (a) == a);
 761   parent = ALLOCNO_LOOP_TREE_NODE (a)->parent;
 762   cap = ira_create_allocno (ALLOCNO_REGNO (a), true, parent);
 763   ALLOCNO_MODE (cap) = ALLOCNO_MODE (a);
 764   cover_class = ALLOCNO_COVER_CLASS (a);
 765   ira_set_allocno_cover_class (cap, cover_class);
 766   ALLOCNO_AVAILABLE_REGS_NUM (cap) = ALLOCNO_AVAILABLE_REGS_NUM (a);
 767   ALLOCNO_CAP_MEMBER (cap) = a;
 768   bitmap_set_bit (parent->mentioned_allocnos, ALLOCNO_NUM (cap));
 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           bitmap_set_bit (ira_curr_loop_tree_node->mentioned_allocnos,
1294                           ALLOCNO_NUM (a));
1295           if (output_p)
1296             bitmap_set_bit (ira_curr_loop_tree_node->modified_regnos, regno);
1297         }
1298       return;
1299     }
1300   else if (code == SET)
1301     {
1302       create_insn_allocnos (SET_DEST (x), true);
1303       create_insn_allocnos (SET_SRC (x), false);
1304       return;
1305     }
1306   else if (code == CLOBBER)
1307     {
1308       create_insn_allocnos (XEXP (x, 0), true);
1309       return;
1310     }
1311   else if (code == MEM)
1312     {
1313       create_insn_allocnos (XEXP (x, 0), false);
1314       return;
1315     }
1316   else if (code == PRE_DEC || code == POST_DEC || code == PRE_INC ||
1317            code == POST_INC || code == POST_MODIFY || code == PRE_MODIFY)
1318     {
1319       create_insn_allocnos (XEXP (x, 0), true);
1320       create_insn_allocnos (XEXP (x, 0), false);
1321       return;
1322     }
1323
1324   fmt = GET_RTX_FORMAT (code);
1325   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1326     {
1327       if (fmt[i] == 'e')
1328         create_insn_allocnos (XEXP (x, i), output_p);
1329       else if (fmt[i] == 'E')
1330         for (j = 0; j < XVECLEN (x, i); j++)
1331           create_insn_allocnos (XVECEXP (x, i, j), output_p);
1332     }
1333 }
1334
1335 /* Create allocnos corresponding to pseudo-registers living in the
1336    basic block represented by the corresponding loop tree node
1337    BB_NODE.  */
1338 static void
1339 create_bb_allocnos (ira_loop_tree_node_t bb_node)
1340 {
1341   basic_block bb;
1342   rtx insn;
1343   unsigned int i;
1344   bitmap_iterator bi;
1345
1346   curr_bb = bb = bb_node->bb;
1347   ira_assert (bb != NULL);
1348   FOR_BB_INSNS (bb, insn)
1349     if (INSN_P (insn))
1350       create_insn_allocnos (PATTERN (insn), false);
1351   /* It might be a allocno living through from one subloop to
1352      another.  */
1353   EXECUTE_IF_SET_IN_REG_SET (DF_LR_IN (bb), FIRST_PSEUDO_REGISTER, i, bi)
1354     if (ira_curr_regno_allocno_map[i] == NULL)
1355       ira_create_allocno (i, false, ira_curr_loop_tree_node);
1356 }
1357
1358 /* Create allocnos corresponding to pseudo-registers living on edge E
1359    (a loop entry or exit).  Also mark the allocnos as living on the
1360    loop border. */
1361 static void
1362 create_loop_allocnos (edge e)
1363 {
1364   unsigned int i;
1365   bitmap live_in_regs, border_allocnos;
1366   bitmap_iterator bi;
1367   ira_loop_tree_node_t parent;
1368
1369   live_in_regs = DF_LR_IN (e->dest);
1370   border_allocnos = ira_curr_loop_tree_node->border_allocnos;
1371   EXECUTE_IF_SET_IN_REG_SET (DF_LR_OUT (e->src),
1372                              FIRST_PSEUDO_REGISTER, i, bi)
1373     if (bitmap_bit_p (live_in_regs, i))
1374       {
1375         if (ira_curr_regno_allocno_map[i] == NULL)
1376           {
1377             /* The order of creations is important for right
1378                ira_regno_allocno_map.  */
1379             if ((parent = ira_curr_loop_tree_node->parent) != NULL
1380                 && parent->regno_allocno_map[i] == NULL)
1381               ira_create_allocno (i, false, parent);
1382             ira_create_allocno (i, false, ira_curr_loop_tree_node);
1383           }
1384         bitmap_set_bit (border_allocnos,
1385                         ALLOCNO_NUM (ira_curr_regno_allocno_map[i]));
1386       }
1387 }
1388
1389 /* Create allocnos corresponding to pseudo-registers living in loop
1390    represented by the corresponding loop tree node LOOP_NODE.  This
1391    function is called by ira_traverse_loop_tree.  */
1392 static void
1393 create_loop_tree_node_allocnos (ira_loop_tree_node_t loop_node)
1394 {
1395   if (loop_node->bb != NULL)
1396     create_bb_allocnos (loop_node);
1397   else if (loop_node != ira_loop_tree_root)
1398     {
1399       int i;
1400       edge_iterator ei;
1401       edge e;
1402       VEC (edge, heap) *edges;
1403
1404       FOR_EACH_EDGE (e, ei, loop_node->loop->header->preds)
1405         if (e->src != loop_node->loop->latch)
1406           create_loop_allocnos (e);
1407
1408       edges = get_loop_exit_edges (loop_node->loop);
1409       for (i = 0; VEC_iterate (edge, edges, i, e); i++)
1410         create_loop_allocnos (e);
1411       VEC_free (edge, heap, edges);
1412     }
1413 }
1414
1415 /* Propagate information about allocnos modified inside the loop given
1416    by its LOOP_TREE_NODE to its parent.  */
1417 static void
1418 propagate_modified_regnos (ira_loop_tree_node_t loop_tree_node)
1419 {
1420   if (loop_tree_node == ira_loop_tree_root)
1421     return;
1422   ira_assert (loop_tree_node->bb == NULL);
1423   bitmap_ior_into (loop_tree_node->parent->modified_regnos,
1424                    loop_tree_node->modified_regnos);
1425 }
1426
1427 /* Propagate new info about allocno A (see comments about accumulated
1428    info in allocno definition) to the corresponding allocno on upper
1429    loop tree level.  So allocnos on upper levels accumulate
1430    information about the corresponding allocnos in nested regions.
1431    The new info means allocno info finally calculated in this
1432    file.  */
1433 static void
1434 propagate_allocno_info (void)
1435 {
1436   int i;
1437   ira_allocno_t a, parent_a;
1438   ira_loop_tree_node_t parent;
1439   enum reg_class cover_class;
1440
1441   if (flag_ira_algorithm != IRA_ALGORITHM_REGIONAL
1442       && flag_ira_algorithm != IRA_ALGORITHM_MIXED)
1443     return;
1444   for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--)
1445     for (a = ira_regno_allocno_map[i];
1446          a != NULL;
1447          a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
1448       if ((parent = ALLOCNO_LOOP_TREE_NODE (a)->parent) != NULL
1449           && (parent_a = parent->regno_allocno_map[i]) != NULL
1450           /* There are no caps yet at this point.  So use
1451              border_allocnos to find allocnos for the propagation.  */
1452           && bitmap_bit_p (ALLOCNO_LOOP_TREE_NODE (a)->border_allocnos,
1453                            ALLOCNO_NUM (a)))
1454         {
1455           ALLOCNO_NREFS (parent_a) += ALLOCNO_NREFS (a);
1456           ALLOCNO_FREQ (parent_a) += ALLOCNO_FREQ (a);
1457           ALLOCNO_CALL_FREQ (parent_a) += ALLOCNO_CALL_FREQ (a);
1458 #ifdef STACK_REGS
1459           if (ALLOCNO_TOTAL_NO_STACK_REG_P (a))
1460             ALLOCNO_TOTAL_NO_STACK_REG_P (parent_a) = true;
1461 #endif
1462           IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (parent_a),
1463                             ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a));
1464           ALLOCNO_CALLS_CROSSED_NUM (parent_a)
1465             += ALLOCNO_CALLS_CROSSED_NUM (a);
1466           ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (parent_a)
1467             += ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a);
1468           cover_class = ALLOCNO_COVER_CLASS (a);
1469           ira_assert (cover_class == ALLOCNO_COVER_CLASS (parent_a));
1470           ira_allocate_and_accumulate_costs
1471             (&ALLOCNO_HARD_REG_COSTS (parent_a), cover_class,
1472              ALLOCNO_HARD_REG_COSTS (a));
1473           ira_allocate_and_accumulate_costs
1474             (&ALLOCNO_CONFLICT_HARD_REG_COSTS (parent_a),
1475              cover_class,
1476              ALLOCNO_CONFLICT_HARD_REG_COSTS (a));
1477           ALLOCNO_COVER_CLASS_COST (parent_a)
1478             += ALLOCNO_COVER_CLASS_COST (a);
1479           ALLOCNO_MEMORY_COST (parent_a) += ALLOCNO_MEMORY_COST (a);
1480           ALLOCNO_UPDATED_MEMORY_COST (parent_a)
1481             += ALLOCNO_UPDATED_MEMORY_COST (a);
1482         }
1483 }
1484
1485 /* Create allocnos corresponding to pseudo-registers in the current
1486    function.  Traverse the loop tree for this.  */
1487 static void
1488 create_allocnos (void)
1489 {
1490   /* We need to process BB first to correctly link allocnos by member
1491      next_regno_allocno.  */
1492   ira_traverse_loop_tree (true, ira_loop_tree_root,
1493                           create_loop_tree_node_allocnos, NULL);
1494   if (optimize)
1495     ira_traverse_loop_tree (false, ira_loop_tree_root, NULL,
1496                             propagate_modified_regnos);
1497 }
1498
1499 \f
1500
1501 /* The page contains function to remove some regions from a separate
1502    register allocation.  We remove regions whose separate allocation
1503    will hardly improve the result.  As a result we speed up regional
1504    register allocation.  */
1505
1506 /* Merge ranges R1 and R2 and returns the result.  The function
1507    maintains the order of ranges and tries to minimize number of the
1508    result ranges.  */
1509 static allocno_live_range_t
1510 merge_ranges (allocno_live_range_t r1, allocno_live_range_t r2)
1511 {
1512   allocno_live_range_t first, last, temp;
1513
1514   if (r1 == NULL)
1515     return r2;
1516   if (r2 == NULL)
1517     return r1;
1518   for (first = last = NULL; r1 != NULL && r2 != NULL;)
1519     {
1520       if (r1->start < r2->start)
1521         {
1522           temp = r1;
1523           r1 = r2;
1524           r2 = temp;
1525         }
1526       if (r1->start <= r2->finish + 1)
1527         {
1528           /* Intersected ranges: merge r1 and r2 into r1.  */
1529           r1->start = r2->start;
1530           if (r1->finish < r2->finish)
1531             r1->finish = r2->finish;
1532           temp = r2;
1533           r2 = r2->next;
1534           ira_finish_allocno_live_range (temp);
1535           if (r2 == NULL)
1536             {
1537               /* To try to merge with subsequent ranges in r1.  */
1538               r2 = r1->next;
1539               r1->next = NULL;
1540             }
1541         }
1542       else
1543         {
1544           /* Add r1 to the result.  */
1545           if (first == NULL)
1546             first = last = r1;
1547           else
1548             {
1549               last->next = r1;
1550               last = r1;
1551             }
1552           r1 = r1->next;
1553           if (r1 == NULL)
1554             {
1555               /* To try to merge with subsequent ranges in r2.  */
1556               r1 = r2->next;
1557               r2->next = NULL;
1558             }
1559         }
1560     }
1561   if (r1 != NULL)
1562     {
1563       if (first == NULL)
1564         first = r1;
1565       else
1566         last->next = r1;
1567       ira_assert (r1->next == NULL);
1568     }
1569   else if (r2 != NULL)
1570     {
1571       if (first == NULL)
1572         first = r2;
1573       else
1574         last->next = r2;
1575       ira_assert (r2->next == NULL);
1576     }
1577   else
1578     {
1579       ira_assert (last->next == NULL);
1580     }
1581   return first;
1582 }
1583
1584 /* The function changes allocno in range list given by R onto A.  */
1585 static void
1586 change_allocno_in_range_list (allocno_live_range_t r, ira_allocno_t a)
1587 {
1588   for (; r != NULL; r = r->next)
1589     r->allocno = a;
1590 }
1591
1592 /* Return TRUE if NODE represents a loop with low register
1593    pressure.  */
1594 static bool
1595 low_pressure_loop_node_p (ira_loop_tree_node_t node)
1596 {
1597   int i;
1598   enum reg_class cover_class;
1599
1600   if (node->bb != NULL)
1601     return false;
1602
1603   for (i = 0; i < ira_reg_class_cover_size; i++)
1604     {
1605       cover_class = ira_reg_class_cover[i];
1606       if (node->reg_pressure[cover_class]
1607           > ira_available_class_regs[cover_class])
1608         return false;
1609     }
1610   return true;
1611 }
1612
1613 /* Return TRUE if NODE represents a loop with should be removed from
1614    regional allocation.  We remove a loop with low register pressure
1615    inside another loop with register pressure.  In this case a
1616    separate allocation of the loop hardly helps (for irregular
1617    register file architecture it could help by choosing a better hard
1618    register in the loop but we prefer faster allocation even in this
1619    case).  */
1620 static bool
1621 loop_node_to_be_removed_p (ira_loop_tree_node_t node)
1622 {
1623   return (node->parent != NULL && low_pressure_loop_node_p (node->parent)
1624           && low_pressure_loop_node_p (node));
1625 }
1626
1627 /* Definition of vector of loop tree nodes.  */
1628 DEF_VEC_P(ira_loop_tree_node_t);
1629 DEF_VEC_ALLOC_P(ira_loop_tree_node_t, heap);
1630
1631 /* Vec containing references to all removed loop tree nodes.  */
1632 static VEC(ira_loop_tree_node_t,heap) *removed_loop_vec;
1633
1634 /* Vec containing references to all children of loop tree nodes.  */
1635 static VEC(ira_loop_tree_node_t,heap) *children_vec;
1636
1637 /* Remove subregions of NODE if their separate allocation will not
1638    improve the result.  */
1639 static void
1640 remove_uneccesary_loop_nodes_from_loop_tree (ira_loop_tree_node_t node)
1641 {
1642   unsigned int start;
1643   bool remove_p;
1644   ira_loop_tree_node_t subnode;
1645
1646   remove_p = loop_node_to_be_removed_p (node);
1647   if (! remove_p)
1648     VEC_safe_push (ira_loop_tree_node_t, heap, children_vec, node);
1649   start = VEC_length (ira_loop_tree_node_t, children_vec);
1650   for (subnode = node->children; subnode != NULL; subnode = subnode->next)
1651     if (subnode->bb == NULL)
1652       remove_uneccesary_loop_nodes_from_loop_tree (subnode);
1653     else
1654       VEC_safe_push (ira_loop_tree_node_t, heap, children_vec, subnode);
1655   node->children = node->subloops = NULL;
1656   if (remove_p)
1657     {
1658       VEC_safe_push (ira_loop_tree_node_t, heap, removed_loop_vec, node);
1659       return;
1660     }
1661   while (VEC_length (ira_loop_tree_node_t, children_vec) > start)
1662     {
1663       subnode = VEC_pop (ira_loop_tree_node_t, children_vec);
1664       subnode->parent = node;
1665       subnode->next = node->children;
1666       node->children = subnode;
1667       if (subnode->bb == NULL)
1668         {
1669           subnode->subloop_next = node->subloops;
1670           node->subloops = subnode;
1671         }
1672     }
1673 }
1674
1675 /* Remove allocnos from loops removed from the allocation
1676    consideration.  */
1677 static void
1678 remove_unnecessary_allocnos (void)
1679 {
1680   int regno;
1681   bool merged_p;
1682   enum reg_class cover_class;
1683   ira_allocno_t a, prev_a, next_a, parent_a;
1684   ira_loop_tree_node_t a_node, parent;
1685   allocno_live_range_t r;
1686
1687   merged_p = false;
1688   for (regno = max_reg_num () - 1; regno >= FIRST_PSEUDO_REGISTER; regno--)
1689     for (prev_a = NULL, a = ira_regno_allocno_map[regno];
1690          a != NULL;
1691          a = next_a)
1692       {
1693         next_a = ALLOCNO_NEXT_REGNO_ALLOCNO (a);
1694         a_node = ALLOCNO_LOOP_TREE_NODE (a);
1695         if (! loop_node_to_be_removed_p (a_node))
1696           prev_a = a;
1697         else
1698           {
1699             for (parent = a_node->parent;
1700                  (parent_a = parent->regno_allocno_map[regno]) == NULL
1701                    && loop_node_to_be_removed_p (parent);
1702                  parent = parent->parent)
1703               ;
1704             if (parent_a == NULL)
1705               {
1706                 /* There are no allocnos with the same regno in upper
1707                    region -- just move the allocno to the upper
1708                    region.  */
1709                 prev_a = a;
1710                 ALLOCNO_LOOP_TREE_NODE (a) = parent;
1711                 parent->regno_allocno_map[regno] = a;
1712                 bitmap_set_bit (parent->mentioned_allocnos, ALLOCNO_NUM (a));
1713               }
1714             else
1715               {
1716                 /* Remove the allocno and update info of allocno in
1717                    the upper region.  */
1718                 if (prev_a == NULL)
1719                   ira_regno_allocno_map[regno] = next_a;
1720                 else
1721                   ALLOCNO_NEXT_REGNO_ALLOCNO (prev_a) = next_a;
1722                 r = ALLOCNO_LIVE_RANGES (a);
1723                 change_allocno_in_range_list (r, parent_a);
1724                 ALLOCNO_LIVE_RANGES (parent_a)
1725                   = merge_ranges (r, ALLOCNO_LIVE_RANGES (parent_a));
1726                 merged_p = true;
1727                 ALLOCNO_LIVE_RANGES (a) = NULL;
1728                 IOR_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (parent_a),
1729                                   ALLOCNO_CONFLICT_HARD_REGS (a));
1730 #ifdef STACK_REGS
1731                 if (ALLOCNO_NO_STACK_REG_P (a))
1732                   ALLOCNO_NO_STACK_REG_P (parent_a) = true;
1733 #endif
1734                 ALLOCNO_NREFS (parent_a) += ALLOCNO_NREFS (a);
1735                 ALLOCNO_FREQ (parent_a) += ALLOCNO_FREQ (a);
1736                 ALLOCNO_CALL_FREQ (parent_a) += ALLOCNO_CALL_FREQ (a);
1737                 IOR_HARD_REG_SET
1738                   (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (parent_a),
1739                    ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a));
1740                 ALLOCNO_CALLS_CROSSED_NUM (parent_a)
1741                   += ALLOCNO_CALLS_CROSSED_NUM (a);
1742                 ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (parent_a)
1743                   += ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a);
1744 #ifdef STACK_REGS
1745                 if (ALLOCNO_TOTAL_NO_STACK_REG_P (a))
1746                   ALLOCNO_TOTAL_NO_STACK_REG_P (parent_a) = true;
1747 #endif
1748                 cover_class = ALLOCNO_COVER_CLASS (a);
1749                 ira_assert (cover_class == ALLOCNO_COVER_CLASS (parent_a));
1750                 ira_allocate_and_accumulate_costs
1751                   (&ALLOCNO_HARD_REG_COSTS (parent_a), cover_class,
1752                    ALLOCNO_HARD_REG_COSTS (a));
1753                 ira_allocate_and_accumulate_costs
1754                   (&ALLOCNO_CONFLICT_HARD_REG_COSTS (parent_a),
1755                    cover_class,
1756                    ALLOCNO_CONFLICT_HARD_REG_COSTS (a));
1757                 ALLOCNO_COVER_CLASS_COST (parent_a)
1758                   += ALLOCNO_COVER_CLASS_COST (a);
1759                 ALLOCNO_MEMORY_COST (parent_a) += ALLOCNO_MEMORY_COST (a);
1760                 ALLOCNO_UPDATED_MEMORY_COST (parent_a)
1761                   += ALLOCNO_UPDATED_MEMORY_COST (a);
1762                 finish_allocno (a);
1763               }
1764           }
1765       }
1766   if (merged_p)
1767     ira_rebuild_start_finish_chains ();
1768 }
1769
1770 /* Remove loops from consideration.  We remove loops for which a
1771    separate allocation will not improve the result.  We have to do
1772    this after allocno creation and their costs and cover class
1773    evaluation because only after that the register pressure can be
1774    known and is calculated.  */
1775 static void
1776 remove_unnecessary_regions (void)
1777 {
1778   children_vec
1779     = VEC_alloc (ira_loop_tree_node_t, heap,
1780                  last_basic_block + VEC_length (loop_p, ira_loops.larray));
1781   removed_loop_vec
1782     = VEC_alloc (ira_loop_tree_node_t, heap,
1783                  last_basic_block + VEC_length (loop_p, ira_loops.larray));
1784   remove_uneccesary_loop_nodes_from_loop_tree (ira_loop_tree_root) ;
1785   VEC_free (ira_loop_tree_node_t, heap, children_vec);
1786   remove_unnecessary_allocnos ();
1787   while (VEC_length (ira_loop_tree_node_t, removed_loop_vec) > 0)
1788     finish_loop_tree_node (VEC_pop (ira_loop_tree_node_t, removed_loop_vec));
1789   VEC_free (ira_loop_tree_node_t, heap, removed_loop_vec);
1790 }
1791
1792 \f
1793
1794 /* Set up minimal and maximal live range points for allocnos.  */
1795 static void
1796 setup_min_max_allocno_live_range_point (void)
1797 {
1798   int i;
1799   ira_allocno_t a, parent_a, cap;
1800   ira_allocno_iterator ai;
1801   allocno_live_range_t r;
1802   ira_loop_tree_node_t parent;
1803
1804   FOR_EACH_ALLOCNO (a, ai)
1805     {
1806       r = ALLOCNO_LIVE_RANGES (a);
1807       if (r == NULL)
1808         continue;
1809       ALLOCNO_MAX (a) = r->finish;
1810       for (; r->next != NULL; r = r->next)
1811         ;
1812       ALLOCNO_MIN (a) = r->start;
1813     }
1814   for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--)
1815     for (a = ira_regno_allocno_map[i];
1816          a != NULL;
1817          a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
1818       {
1819         if (ALLOCNO_MAX (a) < 0)
1820           continue;
1821         ira_assert (ALLOCNO_CAP_MEMBER (a) == NULL);
1822         /* Accumulation of range info.  */
1823         if (ALLOCNO_CAP (a) != NULL)
1824           {
1825             for (cap = ALLOCNO_CAP (a); cap != NULL; cap = ALLOCNO_CAP (cap))
1826               {
1827                 if (ALLOCNO_MAX (cap) < ALLOCNO_MAX (a))
1828                   ALLOCNO_MAX (cap) = ALLOCNO_MAX (a);
1829                 if (ALLOCNO_MIN (cap) > ALLOCNO_MIN (a))
1830                   ALLOCNO_MIN (cap) = ALLOCNO_MIN (a);
1831               }
1832             continue;
1833           }
1834         if ((parent = ALLOCNO_LOOP_TREE_NODE (a)->parent) == NULL)
1835           continue;
1836         parent_a = parent->regno_allocno_map[i];
1837         if (ALLOCNO_MAX (parent_a) < ALLOCNO_MAX (a))
1838           ALLOCNO_MAX (parent_a) = ALLOCNO_MAX (a);
1839         if (ALLOCNO_MIN (parent_a) > ALLOCNO_MIN (a))
1840           ALLOCNO_MIN (parent_a) = ALLOCNO_MIN (a);
1841       }
1842 #ifdef ENABLE_IRA_CHECKING
1843   FOR_EACH_ALLOCNO (a, ai)
1844     {
1845       if ((0 <= ALLOCNO_MIN (a) && ALLOCNO_MIN (a) <= ira_max_point)
1846           && (0 <= ALLOCNO_MAX (a) && ALLOCNO_MAX (a) <= ira_max_point))
1847         continue;
1848       gcc_unreachable ();
1849     }
1850 #endif
1851 }
1852
1853 /* Sort allocnos according to their live ranges.  Allocnos with
1854    smaller cover class are put first.  Allocnos with the same cove
1855    class are ordered according their start (min).  Allocnos with the
1856    same start are ordered according their finish (max).  */
1857 static int
1858 allocno_range_compare_func (const void *v1p, const void *v2p)
1859 {
1860   int diff;
1861   ira_allocno_t a1 = *(const ira_allocno_t *) v1p;
1862   ira_allocno_t a2 = *(const ira_allocno_t *) v2p;
1863
1864   if ((diff = ALLOCNO_COVER_CLASS (a1) - ALLOCNO_COVER_CLASS (a2)) != 0)
1865     return diff;
1866   if ((diff = ALLOCNO_MIN (a1) - ALLOCNO_MIN (a2)) != 0)
1867     return diff;
1868   if ((diff = ALLOCNO_MAX (a1) - ALLOCNO_MAX (a2)) != 0)
1869      return diff;
1870   return ALLOCNO_NUM (a1) - ALLOCNO_NUM (a2);
1871 }
1872
1873 /* Sort ira_conflict_id_allocno_map and set up conflict id of
1874    allocnos.  */
1875 static void
1876 sort_conflict_id_allocno_map (void)
1877 {
1878   int i, num;
1879   ira_allocno_t a;
1880   ira_allocno_iterator ai;
1881
1882   num = 0;
1883   FOR_EACH_ALLOCNO (a, ai)
1884     ira_conflict_id_allocno_map[num++] = a;
1885   qsort (ira_conflict_id_allocno_map, num, sizeof (ira_allocno_t),
1886          allocno_range_compare_func);
1887   for (i = 0; i < num; i++)
1888     if ((a = ira_conflict_id_allocno_map[i]) != NULL)
1889       ALLOCNO_CONFLICT_ID (a) = i;
1890   for (i = num; i < ira_allocnos_num; i++)
1891     ira_conflict_id_allocno_map[i] = NULL;
1892 }
1893
1894 /* Set up minimal and maximal conflict ids of allocnos with which
1895    given allocno can conflict.  */
1896 static void
1897 setup_min_max_conflict_allocno_ids (void)
1898 {
1899   enum reg_class cover_class;
1900   int i, j, min, max, start, finish, first_not_finished, filled_area_start;
1901   int *live_range_min, *last_lived;
1902   ira_allocno_t a;
1903
1904   live_range_min = (int *) ira_allocate (sizeof (int) * ira_allocnos_num);
1905   cover_class = -1;
1906   first_not_finished = -1;
1907   for (i = 0; i < ira_allocnos_num; i++)
1908     {
1909       a = ira_conflict_id_allocno_map[i];
1910       if (a == NULL)
1911         continue;
1912       if (cover_class != ALLOCNO_COVER_CLASS (a))
1913         {
1914           cover_class = ALLOCNO_COVER_CLASS (a);
1915           min = i;
1916           first_not_finished = i;
1917         }
1918       else
1919         {
1920           start = ALLOCNO_MIN (a);
1921           /* If we skip an allocno, the allocno with smaller ids will
1922              be also skipped because of the secondary sorting the
1923              range finishes (see function
1924              allocno_range_compare_func).  */
1925           while (first_not_finished < i
1926                  && start > ALLOCNO_MAX (ira_conflict_id_allocno_map
1927                                          [first_not_finished]))
1928             first_not_finished++;
1929           min = first_not_finished;
1930         }
1931       if (min == i)
1932         /* We could increase min further in this case but it is good
1933            enough.  */
1934         min++;
1935       live_range_min[i] = ALLOCNO_MIN (a);
1936       ALLOCNO_MIN (a) = min;
1937     }
1938   last_lived = (int *) ira_allocate (sizeof (int) * ira_max_point);
1939   cover_class = -1;
1940   filled_area_start = -1;
1941   for (i = ira_allocnos_num - 1; i >= 0; i--)
1942     {
1943       a = ira_conflict_id_allocno_map[i];
1944       if (a == NULL)
1945         continue;
1946       if (cover_class != ALLOCNO_COVER_CLASS (a))
1947         {
1948           cover_class = ALLOCNO_COVER_CLASS (a);
1949           for (j = 0; j < ira_max_point; j++)
1950             last_lived[j] = -1;
1951           filled_area_start = ira_max_point;
1952         }
1953       min = live_range_min[i];
1954       finish = ALLOCNO_MAX (a);
1955       max = last_lived[finish];
1956       if (max < 0)
1957         /* We could decrease max further in this case but it is good
1958            enough.  */
1959         max = ALLOCNO_CONFLICT_ID (a) - 1;
1960       ALLOCNO_MAX (a) = max;
1961       /* In filling, we can go further A range finish to recognize
1962          intersection quickly because if the finish of subsequently
1963          processed allocno (it has smaller conflict id) range is
1964          further A range finish than they are definitely intersected
1965          (the reason for this is the allocnos with bigger conflict id
1966          have their range starts not smaller than allocnos with
1967          smaller ids.  */
1968       for (j = min; j < filled_area_start; j++)
1969         last_lived[j] = i;
1970       filled_area_start = min;
1971     }
1972   ira_free (last_lived);
1973   ira_free (live_range_min);
1974 }
1975
1976 \f
1977
1978 static void
1979 create_caps (void)
1980 {
1981   ira_allocno_t a;
1982   ira_allocno_iterator ai;
1983   ira_loop_tree_node_t loop_tree_node;
1984
1985   FOR_EACH_ALLOCNO (a, ai)
1986     {
1987       if (ALLOCNO_LOOP_TREE_NODE (a) == ira_loop_tree_root)
1988         continue;
1989       if (ALLOCNO_CAP_MEMBER (a) != NULL)
1990         create_cap_allocno (a);
1991       else if (ALLOCNO_CAP (a) == NULL)
1992         {
1993           loop_tree_node = ALLOCNO_LOOP_TREE_NODE (a);
1994           if (!bitmap_bit_p (loop_tree_node->border_allocnos, ALLOCNO_NUM (a)))
1995             create_cap_allocno (a);
1996         }
1997     }
1998 }
1999
2000 \f
2001
2002 /* The page contains code transforming more one region internal
2003    representation (IR) to one region IR which is necessary for reload.
2004    This transformation is called IR flattening.  We might just rebuild
2005    the IR for one region but we don't do it because it takes a lot of
2006    time.  */
2007
2008 /* This recursive function returns immediate common dominator of two
2009    loop tree nodes N1 and N2.  */
2010 static ira_loop_tree_node_t
2011 common_loop_tree_node_dominator (ira_loop_tree_node_t n1,
2012                                  ira_loop_tree_node_t n2)
2013 {
2014   ira_assert (n1 != NULL && n2 != NULL);
2015   if (n1 == n2)
2016     return n1;
2017   if (n1->level < n2->level)
2018     return common_loop_tree_node_dominator (n1, n2->parent);
2019   else if (n1->level > n2->level)
2020     return common_loop_tree_node_dominator (n1->parent, n2);
2021   else
2022     return common_loop_tree_node_dominator (n1->parent, n2->parent);
2023 }
2024
2025 /* Flatten the IR.  In other words, this function transforms IR as if
2026    it were built with one region (without loops).  We could make it
2027    much simpler by rebuilding IR with one region, but unfortunately it
2028    takes a lot of time.  MAX_REGNO_BEFORE_EMIT and
2029    IRA_MAX_POINT_BEFORE_EMIT are correspondingly MAX_REG_NUM () and
2030    IRA_MAX_POINT before emitting insns on the loop borders.  */
2031 void
2032 ira_flattening (int max_regno_before_emit, int ira_max_point_before_emit)
2033 {
2034   int i, j, num;
2035   bool propagate_p, stop_p, keep_p;
2036   int hard_regs_num;
2037   bool new_pseudos_p, merged_p;
2038   unsigned int n;
2039   enum reg_class cover_class;
2040   ira_allocno_t a, parent_a, first, second, node_first, node_second;
2041   ira_allocno_t dominator_a;
2042   ira_copy_t cp;
2043   ira_loop_tree_node_t parent, node, dominator;
2044   allocno_live_range_t r;
2045   ira_allocno_iterator ai;
2046   ira_copy_iterator ci;
2047   sparseset allocnos_live;
2048   /* Map: regno -> allocnos which will finally represent the regno for
2049      IR with one region.  */
2050   ira_allocno_t *regno_top_level_allocno_map;
2051   bool *allocno_propagated_p;
2052
2053   regno_top_level_allocno_map
2054     = (ira_allocno_t *) ira_allocate (max_reg_num () * sizeof (ira_allocno_t));
2055   memset (regno_top_level_allocno_map, 0,
2056           max_reg_num () * sizeof (ira_allocno_t));
2057   allocno_propagated_p
2058     = (bool *) ira_allocate (ira_allocnos_num * sizeof (bool));
2059   memset (allocno_propagated_p, 0, ira_allocnos_num * sizeof (bool));
2060   new_pseudos_p = merged_p = false;
2061   /* Fix final allocno attributes.  */
2062   for (i = max_regno_before_emit - 1; i >= FIRST_PSEUDO_REGISTER; i--)
2063     {
2064       propagate_p = false;
2065       for (a = ira_regno_allocno_map[i];
2066            a != NULL;
2067            a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
2068         {
2069           ira_assert (ALLOCNO_CAP_MEMBER (a) == NULL);
2070           if (ALLOCNO_SOMEWHERE_RENAMED_P (a))
2071             new_pseudos_p = true;
2072           if (ALLOCNO_CAP (a) != NULL
2073               || (parent = ALLOCNO_LOOP_TREE_NODE (a)->parent) == NULL
2074               || ((parent_a = parent->regno_allocno_map[ALLOCNO_REGNO (a)])
2075                   == NULL))
2076             {
2077               ALLOCNO_COPIES (a) = NULL;
2078               regno_top_level_allocno_map[REGNO (ALLOCNO_REG (a))] = a;
2079               continue;
2080             }
2081           ira_assert (ALLOCNO_CAP_MEMBER (parent_a) == NULL);
2082           if (propagate_p)
2083             {
2084               if (!allocno_propagated_p [ALLOCNO_NUM (parent_a)])
2085                 COPY_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (parent_a),
2086                                    ALLOCNO_CONFLICT_HARD_REGS (parent_a));
2087               IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (parent_a),
2088                                 ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a));
2089 #ifdef STACK_REGS
2090               if (!allocno_propagated_p [ALLOCNO_NUM (parent_a)])
2091                 ALLOCNO_TOTAL_NO_STACK_REG_P (parent_a)
2092                   = ALLOCNO_NO_STACK_REG_P (parent_a);
2093               ALLOCNO_TOTAL_NO_STACK_REG_P (parent_a)
2094                 = (ALLOCNO_TOTAL_NO_STACK_REG_P (parent_a)
2095                    || ALLOCNO_TOTAL_NO_STACK_REG_P (a));
2096 #endif
2097               allocno_propagated_p [ALLOCNO_NUM (parent_a)] = true;
2098             }
2099           if (REGNO (ALLOCNO_REG (a)) == REGNO (ALLOCNO_REG (parent_a)))
2100             {
2101               if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL)
2102                 {
2103                   fprintf (ira_dump_file,
2104                            "      Moving ranges of a%dr%d to a%dr%d: ",
2105                            ALLOCNO_NUM (a), REGNO (ALLOCNO_REG (a)),
2106                            ALLOCNO_NUM (parent_a),
2107                            REGNO (ALLOCNO_REG (parent_a)));
2108                   ira_print_live_range_list (ira_dump_file,
2109                                              ALLOCNO_LIVE_RANGES (a));
2110                 }
2111               change_allocno_in_range_list (ALLOCNO_LIVE_RANGES (a), parent_a);
2112               ALLOCNO_LIVE_RANGES (parent_a)
2113                 = merge_ranges (ALLOCNO_LIVE_RANGES (a),
2114                                 ALLOCNO_LIVE_RANGES (parent_a));
2115               merged_p = true;
2116               ALLOCNO_LIVE_RANGES (a) = NULL;
2117               ALLOCNO_MEM_OPTIMIZED_DEST_P (parent_a)
2118                 = (ALLOCNO_MEM_OPTIMIZED_DEST_P (parent_a)
2119                    || ALLOCNO_MEM_OPTIMIZED_DEST_P (a));
2120               continue;
2121             }
2122           new_pseudos_p = true;
2123           propagate_p = true;
2124           first = ALLOCNO_MEM_OPTIMIZED_DEST (a) == NULL ? NULL : a;
2125           stop_p = false;
2126           for (;;)
2127             {
2128               if (first == NULL
2129                   && ALLOCNO_MEM_OPTIMIZED_DEST (parent_a) != NULL)
2130                 first = parent_a;
2131               ALLOCNO_NREFS (parent_a) -= ALLOCNO_NREFS (a);
2132               ALLOCNO_FREQ (parent_a) -= ALLOCNO_FREQ (a);
2133               if (first != NULL
2134                   && ALLOCNO_MEM_OPTIMIZED_DEST (first) == parent_a)
2135                 stop_p = true;
2136               else if (!stop_p)
2137                 {
2138                   ALLOCNO_CALL_FREQ (parent_a) -= ALLOCNO_CALL_FREQ (a);
2139                   ALLOCNO_CALLS_CROSSED_NUM (parent_a)
2140                     -= ALLOCNO_CALLS_CROSSED_NUM (a);
2141                   ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (parent_a)
2142                     -= ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a);
2143                 }
2144               ira_assert (ALLOCNO_CALLS_CROSSED_NUM (parent_a) >= 0
2145                           && ALLOCNO_NREFS (parent_a) >= 0
2146                           && ALLOCNO_FREQ (parent_a) >= 0);
2147               cover_class = ALLOCNO_COVER_CLASS (parent_a);
2148               hard_regs_num = ira_class_hard_regs_num[cover_class];
2149               if (ALLOCNO_HARD_REG_COSTS (a) != NULL
2150                   && ALLOCNO_HARD_REG_COSTS (parent_a) != NULL)
2151                 for (j = 0; j < hard_regs_num; j++)
2152                   ALLOCNO_HARD_REG_COSTS (parent_a)[j]
2153                     -= ALLOCNO_HARD_REG_COSTS (a)[j];
2154               if (ALLOCNO_CONFLICT_HARD_REG_COSTS (a) != NULL
2155                   && ALLOCNO_CONFLICT_HARD_REG_COSTS (parent_a) != NULL)
2156                 for (j = 0; j < hard_regs_num; j++)
2157                   ALLOCNO_CONFLICT_HARD_REG_COSTS (parent_a)[j]
2158                     -= ALLOCNO_CONFLICT_HARD_REG_COSTS (a)[j];
2159               ALLOCNO_COVER_CLASS_COST (parent_a)
2160                 -= ALLOCNO_COVER_CLASS_COST (a);
2161               ALLOCNO_MEMORY_COST (parent_a) -= ALLOCNO_MEMORY_COST (a);
2162               if (ALLOCNO_CAP (parent_a) != NULL
2163                   || (parent
2164                       = ALLOCNO_LOOP_TREE_NODE (parent_a)->parent) == NULL
2165                   || (parent_a = (parent->regno_allocno_map
2166                                   [ALLOCNO_REGNO (parent_a)])) == NULL)
2167                 break;
2168             }
2169           if (first != NULL)
2170             {
2171               parent_a = ALLOCNO_MEM_OPTIMIZED_DEST (first);
2172               dominator = common_loop_tree_node_dominator
2173                           (ALLOCNO_LOOP_TREE_NODE (parent_a),
2174                            ALLOCNO_LOOP_TREE_NODE (first));
2175               dominator_a = dominator->regno_allocno_map[ALLOCNO_REGNO (a)];
2176               ira_assert (parent_a != NULL);
2177               stop_p = first != a;
2178               /* Remember that exit can be to a grandparent (not only
2179                  to a parent) or a child of the grandparent.  */
2180               for (first = a;;)
2181                 {
2182                   if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL)
2183                     {
2184                       fprintf
2185                         (ira_dump_file,
2186                          "      Coping ranges of a%dr%d to a%dr%d: ",
2187                          ALLOCNO_NUM (first), REGNO (ALLOCNO_REG (first)),
2188                          ALLOCNO_NUM (parent_a),
2189                          REGNO (ALLOCNO_REG (parent_a)));
2190                       ira_print_live_range_list (ira_dump_file,
2191                                                  ALLOCNO_LIVE_RANGES (first));
2192                     }
2193                   r = copy_allocno_live_range_list (ALLOCNO_LIVE_RANGES
2194                                                     (first));
2195                   change_allocno_in_range_list (r, parent_a);
2196                   ALLOCNO_LIVE_RANGES (parent_a)
2197                     = merge_ranges (r, ALLOCNO_LIVE_RANGES (parent_a));
2198                   merged_p = true;
2199                   if (stop_p)
2200                     break;
2201                   parent = ALLOCNO_LOOP_TREE_NODE (first)->parent;
2202                   ira_assert (parent != NULL);
2203                   first = parent->regno_allocno_map[ALLOCNO_REGNO (a)];
2204                   ira_assert (first != NULL);
2205                   if (first == dominator_a)
2206                     break;
2207                 }
2208             }
2209           ALLOCNO_COPIES (a) = NULL;
2210           regno_top_level_allocno_map[REGNO (ALLOCNO_REG (a))] = a;
2211         }
2212     }
2213   ira_free (allocno_propagated_p);
2214   ira_assert (new_pseudos_p || ira_max_point_before_emit == ira_max_point);
2215   if (merged_p || ira_max_point_before_emit != ira_max_point)
2216     ira_rebuild_start_finish_chains ();
2217   if (new_pseudos_p)
2218     {
2219       /* Rebuild conflicts.  */
2220       FOR_EACH_ALLOCNO (a, ai)
2221         {
2222           if (a != regno_top_level_allocno_map[REGNO (ALLOCNO_REG (a))]
2223               || ALLOCNO_CAP_MEMBER (a) != NULL)
2224             continue;
2225           for (r = ALLOCNO_LIVE_RANGES (a); r != NULL; r = r->next)
2226             ira_assert (r->allocno == a);
2227           clear_allocno_conflicts (a);
2228         }
2229       allocnos_live = sparseset_alloc (ira_allocnos_num);
2230       for (i = 0; i < ira_max_point; i++)
2231         {
2232           for (r = ira_start_point_ranges[i]; r != NULL; r = r->start_next)
2233             {
2234               a = r->allocno;
2235               if (a != regno_top_level_allocno_map[REGNO (ALLOCNO_REG (a))]
2236                   || ALLOCNO_CAP_MEMBER (a) != NULL)
2237                 continue;
2238               num = ALLOCNO_NUM (a);
2239               cover_class = ALLOCNO_COVER_CLASS (a);
2240               sparseset_set_bit (allocnos_live, num);
2241               EXECUTE_IF_SET_IN_SPARSESET (allocnos_live, n)
2242                 {
2243                   ira_allocno_t live_a = ira_allocnos[n];
2244
2245                   if (cover_class == ALLOCNO_COVER_CLASS (live_a)
2246                       /* Don't set up conflict for the allocno with itself.  */
2247                       && num != (int) n)
2248                     ira_add_allocno_conflict (a, live_a);
2249                 }
2250             }
2251
2252           for (r = ira_finish_point_ranges[i]; r != NULL; r = r->finish_next)
2253             sparseset_clear_bit (allocnos_live, ALLOCNO_NUM (r->allocno));
2254         }
2255       sparseset_free (allocnos_live);
2256       compress_conflict_vecs ();
2257     }
2258   /* Mark some copies for removing and change allocnos in the rest
2259      copies.  */
2260   FOR_EACH_COPY (cp, ci)
2261     {
2262       if (ALLOCNO_CAP_MEMBER (cp->first) != NULL
2263           || ALLOCNO_CAP_MEMBER (cp->second) != NULL)
2264         {
2265           if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL)
2266             fprintf
2267               (ira_dump_file, "      Remove cp%d:%c%dr%d-%c%dr%d\n",
2268                cp->num, ALLOCNO_CAP_MEMBER (cp->first) != NULL ? 'c' : 'a',
2269                ALLOCNO_NUM (cp->first), REGNO (ALLOCNO_REG (cp->first)),
2270                ALLOCNO_CAP_MEMBER (cp->second) != NULL ? 'c' : 'a',
2271                ALLOCNO_NUM (cp->second), REGNO (ALLOCNO_REG (cp->second)));
2272           cp->loop_tree_node = NULL;
2273           continue;
2274         }
2275       first = regno_top_level_allocno_map[REGNO (ALLOCNO_REG (cp->first))];
2276       second = regno_top_level_allocno_map[REGNO (ALLOCNO_REG (cp->second))];
2277       node = cp->loop_tree_node;
2278       if (node == NULL)
2279         keep_p = true; /* It copy generated in ira-emit.c.  */
2280       else
2281         {
2282           /* Check that the copy was not propagated from level on
2283              which we will have different pseudos.  */
2284           node_first = node->regno_allocno_map[ALLOCNO_REGNO (cp->first)];
2285           node_second = node->regno_allocno_map[ALLOCNO_REGNO (cp->second)];
2286           keep_p = ((REGNO (ALLOCNO_REG (first))
2287                      == REGNO (ALLOCNO_REG (node_first)))
2288                      && (REGNO (ALLOCNO_REG (second))
2289                          == REGNO (ALLOCNO_REG (node_second))));
2290         }
2291       if (keep_p)
2292         {
2293           cp->loop_tree_node = ira_loop_tree_root;
2294           cp->first = first;
2295           cp->second = second;
2296         }
2297       else
2298         {
2299           cp->loop_tree_node = NULL;
2300           if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL)
2301             fprintf (ira_dump_file, "      Remove cp%d:a%dr%d-a%dr%d\n",
2302                      cp->num, ALLOCNO_NUM (cp->first),
2303                      REGNO (ALLOCNO_REG (cp->first)), ALLOCNO_NUM (cp->second),
2304                      REGNO (ALLOCNO_REG (cp->second)));
2305         }
2306     }
2307   /* Remove unnecessary allocnos on lower levels of the loop tree.  */
2308   FOR_EACH_ALLOCNO (a, ai)
2309     {
2310       if (a != regno_top_level_allocno_map[REGNO (ALLOCNO_REG (a))]
2311           || ALLOCNO_CAP_MEMBER (a) != NULL)
2312         {
2313           if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL)
2314             fprintf (ira_dump_file, "      Remove a%dr%d\n",
2315                      ALLOCNO_NUM (a), REGNO (ALLOCNO_REG (a)));
2316           finish_allocno (a);
2317           continue;
2318         }
2319       ALLOCNO_LOOP_TREE_NODE (a) = ira_loop_tree_root;
2320       ALLOCNO_REGNO (a) = REGNO (ALLOCNO_REG (a));
2321       ALLOCNO_CAP (a) = NULL;
2322       ALLOCNO_UPDATED_MEMORY_COST (a) = ALLOCNO_MEMORY_COST (a);
2323       if (! ALLOCNO_ASSIGNED_P (a))
2324         ira_free_allocno_updated_costs (a);
2325       ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL);
2326       ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) == NULL);
2327     }
2328   /* Remove unnecessary copies.  */
2329   FOR_EACH_COPY (cp, ci)
2330     {
2331       if (cp->loop_tree_node == NULL)
2332         {
2333           ira_copies[cp->num] = NULL;
2334           finish_copy (cp);
2335           continue;
2336         }
2337       ira_assert
2338         (ALLOCNO_LOOP_TREE_NODE (cp->first) == ira_loop_tree_root
2339          && ALLOCNO_LOOP_TREE_NODE (cp->second) == ira_loop_tree_root);
2340       ira_add_allocno_copy_to_list (cp);
2341       ira_swap_allocno_copy_ends_if_necessary (cp);
2342     }
2343   rebuild_regno_allocno_maps ();
2344   ira_free (regno_top_level_allocno_map);
2345 }
2346
2347 \f
2348
2349 #ifdef ENABLE_IRA_CHECKING
2350 /* Check creation of all allocnos.  Allocnos on lower levels should
2351    have allocnos or caps on all upper levels.  */
2352 static void
2353 check_allocno_creation (void)
2354 {
2355   ira_allocno_t a;
2356   ira_allocno_iterator ai;
2357   ira_loop_tree_node_t loop_tree_node;
2358
2359   FOR_EACH_ALLOCNO (a, ai)
2360     {
2361       if (ALLOCNO_LOOP_TREE_NODE (a) == ira_loop_tree_root)
2362         continue;
2363       if (ALLOCNO_CAP_MEMBER (a) != NULL)
2364         {
2365           ira_assert (ALLOCNO_CAP (a) != NULL);
2366         }
2367       else if (ALLOCNO_CAP (a) == NULL)
2368         {
2369           loop_tree_node = ALLOCNO_LOOP_TREE_NODE (a);
2370           ira_assert (loop_tree_node->parent
2371                       ->regno_allocno_map[ALLOCNO_REGNO (a)] != NULL
2372                       && bitmap_bit_p (loop_tree_node->border_allocnos,
2373                                        ALLOCNO_NUM (a)));
2374         }
2375     }
2376 }
2377 #endif
2378
2379 /* Create a internal representation (IR) for IRA (allocnos, copies,
2380    loop tree nodes).  If LOOPS_P is FALSE the nodes corresponding to
2381    the loops (except the root which corresponds the all function) and
2382    correspondingly allocnos for the loops will be not created.  Such
2383    parameter value is used for Chaitin-Briggs coloring.  The function
2384    returns TRUE if we generate loop structure (besides nodes
2385    representing all function and the basic blocks) for regional
2386    allocation.  A true return means that we really need to flatten IR
2387    before the reload.  */
2388 bool
2389 ira_build (bool loops_p)
2390 {
2391   df_analyze ();
2392
2393   initiate_cost_vectors ();
2394   initiate_allocnos ();
2395   initiate_copies ();
2396   create_loop_tree_nodes (loops_p);
2397   form_loop_tree ();
2398   create_allocnos ();
2399   ira_costs ();
2400   ira_create_allocno_live_ranges ();
2401   remove_unnecessary_regions ();
2402   loops_p = more_one_region_p ();
2403   if (loops_p)
2404     {
2405       propagate_allocno_info ();
2406       create_caps ();
2407     }
2408   ira_tune_allocno_costs_and_cover_classes ();
2409 #ifdef ENABLE_IRA_CHECKING
2410   check_allocno_creation ();
2411 #endif
2412   setup_min_max_allocno_live_range_point ();
2413   sort_conflict_id_allocno_map ();
2414   setup_min_max_conflict_allocno_ids ();
2415   ira_build_conflicts ();
2416   if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
2417     {
2418       int n, nr;
2419       ira_allocno_t a;
2420       allocno_live_range_t r;
2421       ira_allocno_iterator ai;
2422
2423       n = 0;
2424       FOR_EACH_ALLOCNO (a, ai)
2425         n += ALLOCNO_CONFLICT_ALLOCNOS_NUM (a);
2426       nr = 0;
2427       FOR_EACH_ALLOCNO (a, ai)
2428         for (r = ALLOCNO_LIVE_RANGES (a); r != NULL; r = r->next)
2429           nr++;
2430       fprintf (ira_dump_file, "  regions=%d, blocks=%d, points=%d\n",
2431                VEC_length (loop_p, ira_loops.larray), n_basic_blocks,
2432                ira_max_point);
2433       fprintf (ira_dump_file,
2434                "    allocnos=%d, copies=%d, conflicts=%d, ranges=%d\n",
2435                ira_allocnos_num, ira_copies_num, n, nr);
2436     }
2437   return loops_p;
2438 }
2439
2440 /* Release the data created by function ira_build.  */
2441 void
2442 ira_destroy (void)
2443 {
2444   finish_loop_tree_nodes ();
2445   finish_copies ();
2446   finish_allocnos ();
2447   finish_cost_vectors ();
2448   ira_finish_allocno_live_ranges ();
2449 }