gcc/ira-build.c

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