gcc/ira-build.c

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