gcc/ira-build.c

   1 /* Building internal representation for IRA.
   2    Copyright (C) 2006-2013 Free Software Foundation, Inc.
   3    Contributed by Vladimir Makarov <vmakarov@redhat.com>.
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify it under
   8 the terms of the GNU General Public License as published by the Free
   9 Software Foundation; either version 3, or (at your option) any later
  10 version.
  11
  12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15 for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING3.  If not see
  19 <http://www.gnu.org/licenses/>.  */
  20
  21 #include "config.h"
  22 #include "system.h"
  23 #include "coretypes.h"
  24 #include "tm.h"
  25 #include "rtl.h"
  26 #include "tm_p.h"
  27 #include "target.h"
  28 #include "regs.h"
  29 #include "flags.h"
  30 #include "hard-reg-set.h"
  31 #include "basic-block.h"
  32 #include "insn-config.h"
  33 #include "recog.h"
  34 #include "diagnostic-core.h"
  35 #include "params.h"
  36 #include "df.h"
  37 #include "reload.h"
  38 #include "sparseset.h"
  39 #include "ira-int.h"
  40 #include "emit-rtl.h"  /* FIXME: Can go away once crtl is moved to rtl.h.  */
  41
  42 static ira_copy_t find_allocno_copy (ira_allocno_t, ira_allocno_t, rtx,
  43                                      ira_loop_tree_node_t);
  44
  45 /* The root of the loop tree corresponding to the all function.  */
  46 ira_loop_tree_node_t ira_loop_tree_root;
  47
  48 /* Height of the loop tree.  */
  49 int ira_loop_tree_height;
  50
  51 /* All nodes representing basic blocks are referred through the
  52    following array.  We can not use basic block member `aux' for this
  53    because it is used for insertion of insns on edges.  */
  54 ira_loop_tree_node_t ira_bb_nodes;
  55
  56 /* All nodes representing loops are referred through the following
  57    array.  */
  58 ira_loop_tree_node_t ira_loop_nodes;
  59
  60 /* And size of the ira_loop_nodes array.  */
  61 unsigned int ira_loop_nodes_count;
  62
  63 /* Map regno -> allocnos with given regno (see comments for
  64    allocno member `next_regno_allocno').  */
  65 ira_allocno_t *ira_regno_allocno_map;
  66
  67 /* Array of references to all allocnos.  The order number of the
  68    allocno corresponds to the index in the array.  Removed allocnos
  69    have NULL element value.  */
  70 ira_allocno_t *ira_allocnos;
  71
  72 /* Sizes of the previous array.  */
  73 int ira_allocnos_num;
  74
  75 /* Count of conflict record structures we've created, used when creating
  76    a new conflict id.  */
  77 int ira_objects_num;
  78
  79 /* Map a conflict id to its conflict record.  */
  80 ira_object_t *ira_object_id_map;
  81
  82 /* Array of references to all copies.  The order number of the copy
  83    corresponds to the index in the array.  Removed copies have NULL
  84    element value.  */
  85 ira_copy_t *ira_copies;
  86
  87 /* Size of the previous array.  */
  88 int ira_copies_num;
  89
  90 \f
  91
  92 /* LAST_BASIC_BLOCK before generating additional insns because of live
  93    range splitting.  Emitting insns on a critical edge creates a new
  94    basic block.  */
  95 static int last_basic_block_before_change;
  96
  97 /* Initialize some members in loop tree node NODE.  Use LOOP_NUM for
  98    the member loop_num.  */
  99 static void
 100 init_loop_tree_node (struct ira_loop_tree_node *node, int loop_num)
 101 {
 102   int max_regno = max_reg_num ();
 103
 104   node->regno_allocno_map
 105     = (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t) * max_regno);
 106   memset (node->regno_allocno_map, 0, sizeof (ira_allocno_t) * max_regno);
 107   memset (node->reg_pressure, 0, sizeof (node->reg_pressure));
 108   node->all_allocnos = ira_allocate_bitmap ();
 109   node->modified_regnos = ira_allocate_bitmap ();
 110   node->border_allocnos = ira_allocate_bitmap ();
 111   node->local_copies = ira_allocate_bitmap ();
 112   node->loop_num = loop_num;
 113   node->children = NULL;
 114   node->subloops = NULL;
 115 }
 116
 117
 118 /* The following function allocates the loop tree nodes.  If
 119    CURRENT_LOOPS is NULL, the nodes corresponding to the loops (except
 120    the root which corresponds the all function) will be not allocated
 121    but nodes will still be allocated for basic blocks.  */
 122 static void
 123 create_loop_tree_nodes (void)
 124 {
 125   unsigned int i, j;
 126   bool skip_p;
 127   edge_iterator ei;
 128   edge e;
 129   vec<edge> edges;
 130   loop_p loop;
 131
 132   ira_bb_nodes
 133     = ((struct ira_loop_tree_node *)
 134        ira_allocate (sizeof (struct ira_loop_tree_node) * last_basic_block));
 135   last_basic_block_before_change = last_basic_block;
 136   for (i = 0; i < (unsigned int) last_basic_block; i++)
 137     {
 138       ira_bb_nodes[i].regno_allocno_map = NULL;
 139       memset (ira_bb_nodes[i].reg_pressure, 0,
 140               sizeof (ira_bb_nodes[i].reg_pressure));
 141       ira_bb_nodes[i].all_allocnos = NULL;
 142       ira_bb_nodes[i].modified_regnos = NULL;
 143       ira_bb_nodes[i].border_allocnos = NULL;
 144       ira_bb_nodes[i].local_copies = NULL;
 145     }
 146   if (current_loops == NULL)
 147     {
 148       ira_loop_nodes_count = 1;
 149       ira_loop_nodes = ((struct ira_loop_tree_node *)
 150                         ira_allocate (sizeof (struct ira_loop_tree_node)));
 151       init_loop_tree_node (ira_loop_nodes, 0);
 152       return;
 153     }
 154   ira_loop_nodes_count = number_of_loops ();
 155   ira_loop_nodes = ((struct ira_loop_tree_node *)
 156                     ira_allocate (sizeof (struct ira_loop_tree_node)
 157                                   * ira_loop_nodes_count));
 158   FOR_EACH_VEC_SAFE_ELT (get_loops (), i, loop)
 159     {
 160       if (loop_outer (loop) != NULL)
 161         {
 162           ira_loop_nodes[i].regno_allocno_map = NULL;
 163           skip_p = false;
 164           FOR_EACH_EDGE (e, ei, loop->header->preds)
 165             if (e->src != loop->latch
 166                 && (e->flags & EDGE_ABNORMAL) && EDGE_CRITICAL_P (e))
 167               {
 168                 skip_p = true;
 169                 break;
 170               }
 171           if (skip_p)
 172             continue;
 173           edges = get_loop_exit_edges (loop);
 174           FOR_EACH_VEC_ELT (edges, j, e)
 175             if ((e->flags & EDGE_ABNORMAL) && EDGE_CRITICAL_P (e))
 176               {
 177                 skip_p = true;
 178                 break;
 179               }
 180           edges.release ();
 181           if (skip_p)
 182             continue;
 183         }
 184       init_loop_tree_node (&ira_loop_nodes[i], loop->num);
 185     }
 186 }
 187
 188 /* The function returns TRUE if there are more one allocation
 189    region.  */
 190 static bool
 191 more_one_region_p (void)
 192 {
 193   unsigned int i;
 194   loop_p loop;
 195
 196   if (current_loops != NULL)
 197     FOR_EACH_VEC_SAFE_ELT (get_loops (), i, loop)
 198       if (ira_loop_nodes[i].regno_allocno_map != NULL
 199           && ira_loop_tree_root != &ira_loop_nodes[i])
 200         return true;
 201   return false;
 202 }
 203
 204 /* Free the loop tree node of a loop.  */
 205 static void
 206 finish_loop_tree_node (ira_loop_tree_node_t loop)
 207 {
 208   if (loop->regno_allocno_map != NULL)
 209     {
 210       ira_assert (loop->bb == NULL);
 211       ira_free_bitmap (loop->local_copies);
 212       ira_free_bitmap (loop->border_allocnos);
 213       ira_free_bitmap (loop->modified_regnos);
 214       ira_free_bitmap (loop->all_allocnos);
 215       ira_free (loop->regno_allocno_map);
 216       loop->regno_allocno_map = NULL;
 217     }
 218 }
 219
 220 /* Free the loop tree nodes.  */
 221 static void
 222 finish_loop_tree_nodes (void)
 223 {
 224   unsigned int i;
 225
 226   for (i = 0; i < ira_loop_nodes_count; i++)
 227     finish_loop_tree_node (&ira_loop_nodes[i]);
 228   ira_free (ira_loop_nodes);
 229   for (i = 0; i < (unsigned int) last_basic_block_before_change; i++)
 230     {
 231       if (ira_bb_nodes[i].local_copies != NULL)
 232         ira_free_bitmap (ira_bb_nodes[i].local_copies);
 233       if (ira_bb_nodes[i].border_allocnos != NULL)
 234         ira_free_bitmap (ira_bb_nodes[i].border_allocnos);
 235       if (ira_bb_nodes[i].modified_regnos != NULL)
 236         ira_free_bitmap (ira_bb_nodes[i].modified_regnos);
 237       if (ira_bb_nodes[i].all_allocnos != NULL)
 238         ira_free_bitmap (ira_bb_nodes[i].all_allocnos);
 239       if (ira_bb_nodes[i].regno_allocno_map != NULL)
 240         ira_free (ira_bb_nodes[i].regno_allocno_map);
 241     }
 242   ira_free (ira_bb_nodes);
 243 }
 244
 245 \f
 246
 247 /* The following recursive function adds LOOP to the loop tree
 248    hierarchy.  LOOP is added only once.  If LOOP is NULL we adding
 249    loop designating the whole function when CFG loops are not
 250    built.  */
 251 static void
 252 add_loop_to_tree (struct loop *loop)
 253 {
 254   int loop_num;
 255   struct loop *parent;
 256   ira_loop_tree_node_t loop_node, parent_node;
 257
 258   /* We can not use loop node access macros here because of potential
 259      checking and because the nodes are not initialized enough
 260      yet.  */
 261   if (loop != NULL && loop_outer (loop) != NULL)
 262     add_loop_to_tree (loop_outer (loop));
 263   loop_num = loop != NULL ? loop->num : 0;
 264   if (ira_loop_nodes[loop_num].regno_allocno_map != NULL
 265       && ira_loop_nodes[loop_num].children == NULL)
 266     {
 267       /* We have not added loop node to the tree yet.  */
 268       loop_node = &ira_loop_nodes[loop_num];
 269       loop_node->loop = loop;
 270       loop_node->bb = NULL;
 271       if (loop == NULL)
 272         parent = NULL;
 273       else
 274         {
 275           for (parent = loop_outer (loop);
 276                parent != NULL;
 277                parent = loop_outer (parent))
 278             if (ira_loop_nodes[parent->num].regno_allocno_map != NULL)
 279               break;
 280         }
 281       if (parent == NULL)
 282         {
 283           loop_node->next = NULL;
 284           loop_node->subloop_next = NULL;
 285           loop_node->parent = NULL;
 286         }
 287       else
 288         {
 289           parent_node = &ira_loop_nodes[parent->num];
 290           loop_node->next = parent_node->children;
 291           parent_node->children = loop_node;
 292           loop_node->subloop_next = parent_node->subloops;
 293           parent_node->subloops = loop_node;
 294           loop_node->parent = parent_node;
 295         }
 296     }
 297 }
 298
 299 /* The following recursive function sets up levels of nodes of the
 300    tree given its root LOOP_NODE.  The enumeration starts with LEVEL.
 301    The function returns maximal value of level in the tree + 1.  */
 302 static int
 303 setup_loop_tree_level (ira_loop_tree_node_t loop_node, int level)
 304 {
 305   int height, max_height;
 306   ira_loop_tree_node_t subloop_node;
 307
 308   ira_assert (loop_node->bb == NULL);
 309   loop_node->level = level;
 310   max_height = level + 1;
 311   for (subloop_node = loop_node->subloops;
 312        subloop_node != NULL;
 313        subloop_node = subloop_node->subloop_next)
 314     {
 315       ira_assert (subloop_node->bb == NULL);
 316       height = setup_loop_tree_level (subloop_node, level + 1);
 317       if (height > max_height)
 318         max_height = height;
 319     }
 320   return max_height;
 321 }
 322
 323 /* Create the loop tree.  The algorithm is designed to provide correct
 324    order of loops (they are ordered by their last loop BB) and basic
 325    blocks in the chain formed by member next.  */
 326 static void
 327 form_loop_tree (void)
 328 {
 329   basic_block bb;
 330   struct loop *parent;
 331   ira_loop_tree_node_t bb_node, loop_node;
 332
 333   /* We can not use loop/bb node access macros because of potential
 334      checking and because the nodes are not initialized enough
 335      yet.  */
 336   FOR_EACH_BB (bb)
 337     {
 338       bb_node = &ira_bb_nodes[bb->index];
 339       bb_node->bb = bb;
 340       bb_node->loop = NULL;
 341       bb_node->subloops = NULL;
 342       bb_node->children = NULL;
 343       bb_node->subloop_next = NULL;
 344       bb_node->next = NULL;
 345       if (current_loops == NULL)
 346         parent = NULL;
 347       else
 348         {
 349           for (parent = bb->loop_father;
 350                parent != NULL;
 351                parent = loop_outer (parent))
 352             if (ira_loop_nodes[parent->num].regno_allocno_map != NULL)
 353               break;
 354         }
 355       add_loop_to_tree (parent);
 356       loop_node = &ira_loop_nodes[parent == NULL ? 0 : parent->num];
 357       bb_node->next = loop_node->children;
 358       bb_node->parent = loop_node;
 359       loop_node->children = bb_node;
 360     }
 361   ira_loop_tree_root = IRA_LOOP_NODE_BY_INDEX (0);
 362   ira_loop_tree_height = setup_loop_tree_level (ira_loop_tree_root, 0);
 363   ira_assert (ira_loop_tree_root->regno_allocno_map != NULL);
 364 }
 365
 366 \f
 367
 368 /* Rebuild IRA_REGNO_ALLOCNO_MAP and REGNO_ALLOCNO_MAPs of the loop
 369    tree nodes.  */
 370 static void
 371 rebuild_regno_allocno_maps (void)
 372 {
 373   unsigned int l;
 374   int max_regno, regno;
 375   ira_allocno_t a;
 376   ira_loop_tree_node_t loop_tree_node;
 377   loop_p loop;
 378   ira_allocno_iterator ai;
 379
 380   ira_assert (current_loops != NULL);
 381   max_regno = max_reg_num ();
 382   FOR_EACH_VEC_SAFE_ELT (get_loops (), l, loop)
 383     if (ira_loop_nodes[l].regno_allocno_map != NULL)
 384       {
 385         ira_free (ira_loop_nodes[l].regno_allocno_map);
 386         ira_loop_nodes[l].regno_allocno_map
 387           = (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t)
 388                                             * max_regno);
 389         memset (ira_loop_nodes[l].regno_allocno_map, 0,
 390                 sizeof (ira_allocno_t) * max_regno);
 391       }
 392   ira_free (ira_regno_allocno_map);
 393   ira_regno_allocno_map
 394     = (ira_allocno_t *) ira_allocate (max_regno * sizeof (ira_allocno_t));
 395   memset (ira_regno_allocno_map, 0, max_regno * sizeof (ira_allocno_t));
 396   FOR_EACH_ALLOCNO (a, ai)
 397     {
 398       if (ALLOCNO_CAP_MEMBER (a) != NULL)
 399         /* Caps are not in the regno allocno maps.  */
 400         continue;
 401       regno = ALLOCNO_REGNO (a);
 402       loop_tree_node = ALLOCNO_LOOP_TREE_NODE (a);
 403       ALLOCNO_NEXT_REGNO_ALLOCNO (a) = ira_regno_allocno_map[regno];
 404       ira_regno_allocno_map[regno] = a;
 405       if (loop_tree_node->regno_allocno_map[regno] == NULL)
 406         /* Remember that we can create temporary allocnos to break
 407            cycles in register shuffle.  */
 408         loop_tree_node->regno_allocno_map[regno] = a;
 409     }
 410 }
 411 \f
 412
 413 /* Pools for allocnos, allocno live ranges and objects.  */
 414 static alloc_pool allocno_pool, live_range_pool, object_pool;
 415
 416 /* Vec containing references to all created allocnos.  It is a
 417    container of array allocnos.  */
 418 static vec<ira_allocno_t> allocno_vec;
 419
 420 /* Vec containing references to all created ira_objects.  It is a
 421    container of ira_object_id_map.  */
 422 static vec<ira_object_t> ira_object_id_map_vec;
 423
 424 /* Initialize data concerning allocnos.  */
 425 static void
 426 initiate_allocnos (void)
 427 {
 428   live_range_pool
 429     = create_alloc_pool ("live ranges",
 430                          sizeof (struct live_range), 100);
 431   allocno_pool
 432     = create_alloc_pool ("allocnos", sizeof (struct ira_allocno), 100);
 433   object_pool
 434     = create_alloc_pool ("objects", sizeof (struct ira_object), 100);
 435   allocno_vec.create (max_reg_num () * 2);
 436   ira_allocnos = NULL;
 437   ira_allocnos_num = 0;
 438   ira_objects_num = 0;
 439   ira_object_id_map_vec.create (max_reg_num () * 2);
 440   ira_object_id_map = NULL;
 441   ira_regno_allocno_map
 442     = (ira_allocno_t *) ira_allocate (max_reg_num ()
 443                                       * sizeof (ira_allocno_t));
 444   memset (ira_regno_allocno_map, 0, max_reg_num () * sizeof (ira_allocno_t));
 445 }
 446
 447 /* Create and return an object corresponding to a new allocno A.  */
 448 static ira_object_t
 449 ira_create_object (ira_allocno_t a, int subword)
 450 {
 451   enum reg_class aclass = ALLOCNO_CLASS (a);
 452   ira_object_t obj = (ira_object_t) pool_alloc (object_pool);
 453
 454   OBJECT_ALLOCNO (obj) = a;
 455   OBJECT_SUBWORD (obj) = subword;
 456   OBJECT_CONFLICT_ID (obj) = ira_objects_num;
 457   OBJECT_CONFLICT_VEC_P (obj) = false;
 458   OBJECT_CONFLICT_ARRAY (obj) = NULL;
 459   OBJECT_NUM_CONFLICTS (obj) = 0;
 460   COPY_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (obj), ira_no_alloc_regs);
 461   COPY_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj), ira_no_alloc_regs);
 462   IOR_COMPL_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (obj),
 463                           reg_class_contents[aclass]);
 464   IOR_COMPL_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj),
 465                           reg_class_contents[aclass]);
 466   OBJECT_MIN (obj) = INT_MAX;
 467   OBJECT_MAX (obj) = -1;
 468   OBJECT_LIVE_RANGES (obj) = NULL;
 469
 470   ira_object_id_map_vec.safe_push (obj);
 471   ira_object_id_map
 472     = ira_object_id_map_vec.address ();
 473   ira_objects_num = ira_object_id_map_vec.length ();
 474
 475   return obj;
 476 }
 477
 478 /* Create and return the allocno corresponding to REGNO in
 479    LOOP_TREE_NODE.  Add the allocno to the list of allocnos with the
 480    same regno if CAP_P is FALSE.  */
 481 ira_allocno_t
 482 ira_create_allocno (int regno, bool cap_p,
 483                     ira_loop_tree_node_t loop_tree_node)
 484 {
 485   ira_allocno_t a;
 486
 487   a = (ira_allocno_t) pool_alloc (allocno_pool);
 488   ALLOCNO_REGNO (a) = regno;
 489   ALLOCNO_LOOP_TREE_NODE (a) = loop_tree_node;
 490   if (! cap_p)
 491     {
 492       ALLOCNO_NEXT_REGNO_ALLOCNO (a) = ira_regno_allocno_map[regno];
 493       ira_regno_allocno_map[regno] = a;
 494       if (loop_tree_node->regno_allocno_map[regno] == NULL)
 495         /* Remember that we can create temporary allocnos to break
 496            cycles in register shuffle on region borders (see
 497            ira-emit.c).  */
 498         loop_tree_node->regno_allocno_map[regno] = a;
 499     }
 500   ALLOCNO_CAP (a) = NULL;
 501   ALLOCNO_CAP_MEMBER (a) = NULL;
 502   ALLOCNO_NUM (a) = ira_allocnos_num;
 503   bitmap_set_bit (loop_tree_node->all_allocnos, ALLOCNO_NUM (a));
 504   ALLOCNO_NREFS (a) = 0;
 505   ALLOCNO_FREQ (a) = 0;
 506   ALLOCNO_HARD_REGNO (a) = -1;
 507   ALLOCNO_CALL_FREQ (a) = 0;
 508   ALLOCNO_CALLS_CROSSED_NUM (a) = 0;
 509   ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a) = 0;
 510 #ifdef STACK_REGS
 511   ALLOCNO_NO_STACK_REG_P (a) = false;
 512   ALLOCNO_TOTAL_NO_STACK_REG_P (a) = false;
 513 #endif
 514   ALLOCNO_DONT_REASSIGN_P (a) = false;
 515   ALLOCNO_BAD_SPILL_P (a) = false;
 516   ALLOCNO_ASSIGNED_P (a) = false;
 517   ALLOCNO_MODE (a) = (regno < 0 ? VOIDmode : PSEUDO_REGNO_MODE (regno));
 518   ALLOCNO_COPIES (a) = NULL;
 519   ALLOCNO_HARD_REG_COSTS (a) = NULL;
 520   ALLOCNO_CONFLICT_HARD_REG_COSTS (a) = NULL;
 521   ALLOCNO_UPDATED_HARD_REG_COSTS (a) = NULL;
 522   ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) = NULL;
 523   ALLOCNO_CLASS (a) = NO_REGS;
 524   ALLOCNO_UPDATED_CLASS_COST (a) = 0;
 525   ALLOCNO_CLASS_COST (a) = 0;
 526   ALLOCNO_MEMORY_COST (a) = 0;
 527   ALLOCNO_UPDATED_MEMORY_COST (a) = 0;
 528   ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a) = 0;
 529   ALLOCNO_NUM_OBJECTS (a) = 0;
 530
 531   ALLOCNO_ADD_DATA (a) = NULL;
 532   allocno_vec.safe_push (a);
 533   ira_allocnos = allocno_vec.address ();
 534   ira_allocnos_num = allocno_vec.length ();
 535
 536   return a;
 537 }
 538
 539 /* Set up register class for A and update its conflict hard
 540    registers.  */
 541 void
 542 ira_set_allocno_class (ira_allocno_t a, enum reg_class aclass)
 543 {
 544   ira_allocno_object_iterator oi;
 545   ira_object_t obj;
 546
 547   ALLOCNO_CLASS (a) = aclass;
 548   FOR_EACH_ALLOCNO_OBJECT (a, obj, oi)
 549     {
 550       IOR_COMPL_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (obj),
 551                               reg_class_contents[aclass]);
 552       IOR_COMPL_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj),
 553                               reg_class_contents[aclass]);
 554     }
 555 }
 556
 557 /* Determine the number of objects we should associate with allocno A
 558    and allocate them.  */
 559 void
 560 ira_create_allocno_objects (ira_allocno_t a)
 561 {
 562   enum machine_mode mode = ALLOCNO_MODE (a);
 563   enum reg_class aclass = ALLOCNO_CLASS (a);
 564   int n = ira_reg_class_max_nregs[aclass][mode];
 565   int i;
 566
 567   if (GET_MODE_SIZE (mode) != 2 * UNITS_PER_WORD || n != 2)
 568     n = 1;
 569
 570   ALLOCNO_NUM_OBJECTS (a) = n;
 571   for (i = 0; i < n; i++)
 572     ALLOCNO_OBJECT (a, i) = ira_create_object (a, i);
 573 }
 574
 575 /* For each allocno, set ALLOCNO_NUM_OBJECTS and create the
 576    ALLOCNO_OBJECT structures.  This must be called after the allocno
 577    classes are known.  */
 578 static void
 579 create_allocno_objects (void)
 580 {
 581   ira_allocno_t a;
 582   ira_allocno_iterator ai;
 583
 584   FOR_EACH_ALLOCNO (a, ai)
 585     ira_create_allocno_objects (a);
 586 }
 587
 588 /* Merge hard register conflict information for all objects associated with
 589    allocno TO into the corresponding objects associated with FROM.
 590    If TOTAL_ONLY is true, we only merge OBJECT_TOTAL_CONFLICT_HARD_REGS.  */
 591 static void
 592 merge_hard_reg_conflicts (ira_allocno_t from, ira_allocno_t to,
 593                           bool total_only)
 594 {
 595   int i;
 596   gcc_assert (ALLOCNO_NUM_OBJECTS (to) == ALLOCNO_NUM_OBJECTS (from));
 597   for (i = 0; i < ALLOCNO_NUM_OBJECTS (to); i++)
 598     {
 599       ira_object_t from_obj = ALLOCNO_OBJECT (from, i);
 600       ira_object_t to_obj = ALLOCNO_OBJECT (to, i);
 601
 602       if (!total_only)
 603         IOR_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (to_obj),
 604                           OBJECT_CONFLICT_HARD_REGS (from_obj));
 605       IOR_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (to_obj),
 606                         OBJECT_TOTAL_CONFLICT_HARD_REGS (from_obj));
 607     }
 608 #ifdef STACK_REGS
 609   if (!total_only && ALLOCNO_NO_STACK_REG_P (from))
 610     ALLOCNO_NO_STACK_REG_P (to) = true;
 611   if (ALLOCNO_TOTAL_NO_STACK_REG_P (from))
 612     ALLOCNO_TOTAL_NO_STACK_REG_P (to) = true;
 613 #endif
 614 }
 615
 616 /* Update hard register conflict information for all objects associated with
 617    A to include the regs in SET.  */
 618 void
 619 ior_hard_reg_conflicts (ira_allocno_t a, HARD_REG_SET *set)
 620 {
 621   ira_allocno_object_iterator i;
 622   ira_object_t obj;
 623
 624   FOR_EACH_ALLOCNO_OBJECT (a, obj, i)
 625     {
 626       IOR_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (obj), *set);
 627       IOR_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj), *set);
 628     }
 629 }
 630
 631 /* Return TRUE if a conflict vector with NUM elements is more
 632    profitable than a conflict bit vector for OBJ.  */
 633 bool
 634 ira_conflict_vector_profitable_p (ira_object_t obj, int num)
 635 {
 636   int nw;
 637   int max = OBJECT_MAX (obj);
 638   int min = OBJECT_MIN (obj);
 639
 640   if (max < min)
 641     /* We prefer a bit vector in such case because it does not result
 642        in allocation.  */
 643     return false;
 644
 645   nw = (max - min + IRA_INT_BITS) / IRA_INT_BITS;
 646   return (2 * sizeof (ira_object_t) * (num + 1)
 647           < 3 * nw * sizeof (IRA_INT_TYPE));
 648 }
 649
 650 /* Allocates and initialize the conflict vector of OBJ for NUM
 651    conflicting objects.  */
 652 void
 653 ira_allocate_conflict_vec (ira_object_t obj, int num)
 654 {
 655   int size;
 656   ira_object_t *vec;
 657
 658   ira_assert (OBJECT_CONFLICT_ARRAY (obj) == NULL);
 659   num++; /* for NULL end marker  */
 660   size = sizeof (ira_object_t) * num;
 661   OBJECT_CONFLICT_ARRAY (obj) = ira_allocate (size);
 662   vec = (ira_object_t *) OBJECT_CONFLICT_ARRAY (obj);
 663   vec[0] = NULL;
 664   OBJECT_NUM_CONFLICTS (obj) = 0;
 665   OBJECT_CONFLICT_ARRAY_SIZE (obj) = size;
 666   OBJECT_CONFLICT_VEC_P (obj) = true;
 667 }
 668
 669 /* Allocate and initialize the conflict bit vector of OBJ.  */
 670 static void
 671 allocate_conflict_bit_vec (ira_object_t obj)
 672 {
 673   unsigned int size;
 674
 675   ira_assert (OBJECT_CONFLICT_ARRAY (obj) == NULL);
 676   size = ((OBJECT_MAX (obj) - OBJECT_MIN (obj) + IRA_INT_BITS)
 677           / IRA_INT_BITS * sizeof (IRA_INT_TYPE));
 678   OBJECT_CONFLICT_ARRAY (obj) = ira_allocate (size);
 679   memset (OBJECT_CONFLICT_ARRAY (obj), 0, size);
 680   OBJECT_CONFLICT_ARRAY_SIZE (obj) = size;
 681   OBJECT_CONFLICT_VEC_P (obj) = false;
 682 }
 683
 684 /* Allocate and initialize the conflict vector or conflict bit vector
 685    of OBJ for NUM conflicting allocnos whatever is more profitable.  */
 686 void
 687 ira_allocate_object_conflicts (ira_object_t obj, int num)
 688 {
 689   if (ira_conflict_vector_profitable_p (obj, num))
 690     ira_allocate_conflict_vec (obj, num);
 691   else
 692     allocate_conflict_bit_vec (obj);
 693 }
 694
 695 /* Add OBJ2 to the conflicts of OBJ1.  */
 696 static void
 697 add_to_conflicts (ira_object_t obj1, ira_object_t obj2)
 698 {
 699   int num;
 700   unsigned int size;
 701
 702   if (OBJECT_CONFLICT_VEC_P (obj1))
 703     {
 704       ira_object_t *vec = OBJECT_CONFLICT_VEC (obj1);
 705       int curr_num = OBJECT_NUM_CONFLICTS (obj1);
 706       num = curr_num + 2;
 707       if (OBJECT_CONFLICT_ARRAY_SIZE (obj1) < num * sizeof (ira_object_t))
 708         {
 709           ira_object_t *newvec;
 710           size = (3 * num / 2 + 1) * sizeof (ira_allocno_t);
 711           newvec = (ira_object_t *) ira_allocate (size);
 712           memcpy (newvec, vec, curr_num * sizeof (ira_object_t));
 713           ira_free (vec);
 714           vec = newvec;
 715           OBJECT_CONFLICT_ARRAY (obj1) = vec;
 716           OBJECT_CONFLICT_ARRAY_SIZE (obj1) = size;
 717         }
 718       vec[num - 2] = obj2;
 719       vec[num - 1] = NULL;
 720       OBJECT_NUM_CONFLICTS (obj1)++;
 721     }
 722   else
 723     {
 724       int nw, added_head_nw, id;
 725       IRA_INT_TYPE *vec = OBJECT_CONFLICT_BITVEC (obj1);
 726
 727       id = OBJECT_CONFLICT_ID (obj2);
 728       if (OBJECT_MIN (obj1) > id)
 729         {
 730           /* Expand head of the bit vector.  */
 731           added_head_nw = (OBJECT_MIN (obj1) - id - 1) / IRA_INT_BITS + 1;
 732           nw = (OBJECT_MAX (obj1) - OBJECT_MIN (obj1)) / IRA_INT_BITS + 1;
 733           size = (nw + added_head_nw) * sizeof (IRA_INT_TYPE);
 734           if (OBJECT_CONFLICT_ARRAY_SIZE (obj1) >= size)
 735             {
 736               memmove ((char *) vec + added_head_nw * sizeof (IRA_INT_TYPE),
 737                        vec, nw * sizeof (IRA_INT_TYPE));
 738               memset (vec, 0, added_head_nw * sizeof (IRA_INT_TYPE));
 739             }
 740           else
 741             {
 742               size
 743                 = (3 * (nw + added_head_nw) / 2 + 1) * sizeof (IRA_INT_TYPE);
 744               vec = (IRA_INT_TYPE *) ira_allocate (size);
 745               memcpy ((char *) vec + added_head_nw * sizeof (IRA_INT_TYPE),
 746                       OBJECT_CONFLICT_ARRAY (obj1), nw * sizeof (IRA_INT_TYPE));
 747               memset (vec, 0, added_head_nw * sizeof (IRA_INT_TYPE));
 748               memset ((char *) vec
 749                       + (nw + added_head_nw) * sizeof (IRA_INT_TYPE),
 750                       0, size - (nw + added_head_nw) * sizeof (IRA_INT_TYPE));
 751               ira_free (OBJECT_CONFLICT_ARRAY (obj1));
 752               OBJECT_CONFLICT_ARRAY (obj1) = vec;
 753               OBJECT_CONFLICT_ARRAY_SIZE (obj1) = size;
 754             }
 755           OBJECT_MIN (obj1) -= added_head_nw * IRA_INT_BITS;
 756         }
 757       else if (OBJECT_MAX (obj1) < id)
 758         {
 759           nw = (id - OBJECT_MIN (obj1)) / IRA_INT_BITS + 1;
 760           size = nw * sizeof (IRA_INT_TYPE);
 761           if (OBJECT_CONFLICT_ARRAY_SIZE (obj1) < size)
 762             {
 763               /* Expand tail of the bit vector.  */
 764               size = (3 * nw / 2 + 1) * sizeof (IRA_INT_TYPE);
 765               vec = (IRA_INT_TYPE *) ira_allocate (size);
 766               memcpy (vec, OBJECT_CONFLICT_ARRAY (obj1), OBJECT_CONFLICT_ARRAY_SIZE (obj1));
 767               memset ((char *) vec + OBJECT_CONFLICT_ARRAY_SIZE (obj1),
 768                       0, size - OBJECT_CONFLICT_ARRAY_SIZE (obj1));
 769               ira_free (OBJECT_CONFLICT_ARRAY (obj1));
 770               OBJECT_CONFLICT_ARRAY (obj1) = vec;
 771               OBJECT_CONFLICT_ARRAY_SIZE (obj1) = size;
 772             }
 773           OBJECT_MAX (obj1) = id;
 774         }
 775       SET_MINMAX_SET_BIT (vec, id, OBJECT_MIN (obj1), OBJECT_MAX (obj1));
 776     }
 777 }
 778
 779 /* Add OBJ1 to the conflicts of OBJ2 and vice versa.  */
 780 static void
 781 ira_add_conflict (ira_object_t obj1, ira_object_t obj2)
 782 {
 783   add_to_conflicts (obj1, obj2);
 784   add_to_conflicts (obj2, obj1);
 785 }
 786
 787 /* Clear all conflicts of OBJ.  */
 788 static void
 789 clear_conflicts (ira_object_t obj)
 790 {
 791   if (OBJECT_CONFLICT_VEC_P (obj))
 792     {
 793       OBJECT_NUM_CONFLICTS (obj) = 0;
 794       OBJECT_CONFLICT_VEC (obj)[0] = NULL;
 795     }
 796   else if (OBJECT_CONFLICT_ARRAY_SIZE (obj) != 0)
 797     {
 798       int nw;
 799
 800       nw = (OBJECT_MAX (obj) - OBJECT_MIN (obj)) / IRA_INT_BITS + 1;
 801       memset (OBJECT_CONFLICT_BITVEC (obj), 0, nw * sizeof (IRA_INT_TYPE));
 802     }
 803 }
 804
 805 /* The array used to find duplications in conflict vectors of
 806    allocnos.  */
 807 static int *conflict_check;
 808
 809 /* The value used to mark allocation presence in conflict vector of
 810    the current allocno.  */
 811 static int curr_conflict_check_tick;
 812
 813 /* Remove duplications in conflict vector of OBJ.  */
 814 static void
 815 compress_conflict_vec (ira_object_t obj)
 816 {
 817   ira_object_t *vec, conflict_obj;
 818   int i, j;
 819
 820   ira_assert (OBJECT_CONFLICT_VEC_P (obj));
 821   vec = OBJECT_CONFLICT_VEC (obj);
 822   curr_conflict_check_tick++;
 823   for (i = j = 0; (conflict_obj = vec[i]) != NULL; i++)
 824     {
 825       int id = OBJECT_CONFLICT_ID (conflict_obj);
 826       if (conflict_check[id] != curr_conflict_check_tick)
 827         {
 828           conflict_check[id] = curr_conflict_check_tick;
 829           vec[j++] = conflict_obj;
 830         }
 831     }
 832   OBJECT_NUM_CONFLICTS (obj) = j;
 833   vec[j] = NULL;
 834 }
 835
 836 /* Remove duplications in conflict vectors of all allocnos.  */
 837 static void
 838 compress_conflict_vecs (void)
 839 {
 840   ira_object_t obj;
 841   ira_object_iterator oi;
 842
 843   conflict_check = (int *) ira_allocate (sizeof (int) * ira_objects_num);
 844   memset (conflict_check, 0, sizeof (int) * ira_objects_num);
 845   curr_conflict_check_tick = 0;
 846   FOR_EACH_OBJECT (obj, oi)
 847     {
 848       if (OBJECT_CONFLICT_VEC_P (obj))
 849         compress_conflict_vec (obj);
 850     }
 851   ira_free (conflict_check);
 852 }
 853
 854 /* This recursive function outputs allocno A and if it is a cap the
 855    function outputs its members.  */
 856 void
 857 ira_print_expanded_allocno (ira_allocno_t a)
 858 {
 859   basic_block bb;
 860
 861   fprintf (ira_dump_file, " a%d(r%d", ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
 862   if ((bb = ALLOCNO_LOOP_TREE_NODE (a)->bb) != NULL)
 863     fprintf (ira_dump_file, ",b%d", bb->index);
 864   else
 865     fprintf (ira_dump_file, ",l%d", ALLOCNO_LOOP_TREE_NODE (a)->loop_num);
 866   if (ALLOCNO_CAP_MEMBER (a) != NULL)
 867     {
 868       fprintf (ira_dump_file, ":");
 869       ira_print_expanded_allocno (ALLOCNO_CAP_MEMBER (a));
 870     }
 871   fprintf (ira_dump_file, ")");
 872 }
 873
 874 /* Create and return the cap representing allocno A in the
 875    parent loop.  */
 876 static ira_allocno_t
 877 create_cap_allocno (ira_allocno_t a)
 878 {
 879   ira_allocno_t cap;
 880   ira_loop_tree_node_t parent;
 881   enum reg_class aclass;
 882
 883   parent = ALLOCNO_LOOP_TREE_NODE (a)->parent;
 884   cap = ira_create_allocno (ALLOCNO_REGNO (a), true, parent);
 885   ALLOCNO_MODE (cap) = ALLOCNO_MODE (a);
 886   aclass = ALLOCNO_CLASS (a);
 887   ira_set_allocno_class (cap, aclass);
 888   ira_create_allocno_objects (cap);
 889   ALLOCNO_CAP_MEMBER (cap) = a;
 890   ALLOCNO_CAP (a) = cap;
 891   ALLOCNO_CLASS_COST (cap) = ALLOCNO_CLASS_COST (a);
 892   ALLOCNO_MEMORY_COST (cap) = ALLOCNO_MEMORY_COST (a);
 893   ira_allocate_and_copy_costs
 894     (&ALLOCNO_HARD_REG_COSTS (cap), aclass, ALLOCNO_HARD_REG_COSTS (a));
 895   ira_allocate_and_copy_costs
 896     (&ALLOCNO_CONFLICT_HARD_REG_COSTS (cap), aclass,
 897      ALLOCNO_CONFLICT_HARD_REG_COSTS (a));
 898   ALLOCNO_BAD_SPILL_P (cap) = ALLOCNO_BAD_SPILL_P (a);
 899   ALLOCNO_NREFS (cap) = ALLOCNO_NREFS (a);
 900   ALLOCNO_FREQ (cap) = ALLOCNO_FREQ (a);
 901   ALLOCNO_CALL_FREQ (cap) = ALLOCNO_CALL_FREQ (a);
 902
 903   merge_hard_reg_conflicts (a, cap, false);
 904
 905   ALLOCNO_CALLS_CROSSED_NUM (cap) = ALLOCNO_CALLS_CROSSED_NUM (a);
 906   ALLOCNO_CHEAP_CALLS_CROSSED_NUM (cap) = ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a);
 907   if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
 908     {
 909       fprintf (ira_dump_file, "    Creating cap ");
 910       ira_print_expanded_allocno (cap);
 911       fprintf (ira_dump_file, "\n");
 912     }
 913   return cap;
 914 }
 915
 916 /* Create and return a live range for OBJECT with given attributes.  */
 917 live_range_t
 918 ira_create_live_range (ira_object_t obj, int start, int finish,
 919                        live_range_t next)
 920 {
 921   live_range_t p;
 922
 923   p = (live_range_t) pool_alloc (live_range_pool);
 924   p->object = obj;
 925   p->start = start;
 926   p->finish = finish;
 927   p->next = next;
 928   return p;
 929 }
 930
 931 /* Create a new live range for OBJECT and queue it at the head of its
 932    live range list.  */
 933 void
 934 ira_add_live_range_to_object (ira_object_t object, int start, int finish)
 935 {
 936   live_range_t p;
 937   p = ira_create_live_range (object, start, finish,
 938                              OBJECT_LIVE_RANGES (object));
 939   OBJECT_LIVE_RANGES (object) = p;
 940 }
 941
 942 /* Copy allocno live range R and return the result.  */
 943 static live_range_t
 944 copy_live_range (live_range_t r)
 945 {
 946   live_range_t p;
 947
 948   p = (live_range_t) pool_alloc (live_range_pool);
 949   *p = *r;
 950   return p;
 951 }
 952
 953 /* Copy allocno live range list given by its head R and return the
 954    result.  */
 955 live_range_t
 956 ira_copy_live_range_list (live_range_t r)
 957 {
 958   live_range_t p, first, last;
 959
 960   if (r == NULL)
 961     return NULL;
 962   for (first = last = NULL; r != NULL; r = r->next)
 963     {
 964       p = copy_live_range (r);
 965       if (first == NULL)
 966         first = p;
 967       else
 968         last->next = p;
 969       last = p;
 970     }
 971   return first;
 972 }
 973
 974 /* Merge ranges R1 and R2 and returns the result.  The function
 975    maintains the order of ranges and tries to minimize number of the
 976    result ranges.  */
 977 live_range_t
 978 ira_merge_live_ranges (live_range_t r1, live_range_t r2)
 979 {
 980   live_range_t first, last, temp;
 981
 982   if (r1 == NULL)
 983     return r2;
 984   if (r2 == NULL)
 985     return r1;
 986   for (first = last = NULL; r1 != NULL && r2 != NULL;)
 987     {
 988       if (r1->start < r2->start)
 989         {
 990           temp = r1;
 991           r1 = r2;
 992           r2 = temp;
 993         }
 994       if (r1->start <= r2->finish + 1)
 995         {
 996           /* Intersected ranges: merge r1 and r2 into r1.  */
 997           r1->start = r2->start;
 998           if (r1->finish < r2->finish)
 999             r1->finish = r2->finish;
1000           temp = r2;
1001           r2 = r2->next;
1002           ira_finish_live_range (temp);
1003           if (r2 == NULL)
1004             {
1005               /* To try to merge with subsequent ranges in r1.  */
1006               r2 = r1->next;
1007               r1->next = NULL;
1008             }
1009         }
1010       else
1011         {
1012           /* Add r1 to the result.  */
1013           if (first == NULL)
1014             first = last = r1;
1015           else
1016             {
1017               last->next = r1;
1018               last = r1;
1019             }
1020           r1 = r1->next;
1021           if (r1 == NULL)
1022             {
1023               /* To try to merge with subsequent ranges in r2.  */
1024               r1 = r2->next;
1025               r2->next = NULL;
1026             }
1027         }
1028     }
1029   if (r1 != NULL)
1030     {
1031       if (first == NULL)
1032         first = r1;
1033       else
1034         last->next = r1;
1035       ira_assert (r1->next == NULL);
1036     }
1037   else if (r2 != NULL)
1038     {
1039       if (first == NULL)
1040         first = r2;
1041       else
1042         last->next = r2;
1043       ira_assert (r2->next == NULL);
1044     }
1045   else
1046     {
1047       ira_assert (last->next == NULL);
1048     }
1049   return first;
1050 }
1051
1052 /* Return TRUE if live ranges R1 and R2 intersect.  */
1053 bool
1054 ira_live_ranges_intersect_p (live_range_t r1, live_range_t r2)
1055 {
1056   /* Remember the live ranges are always kept ordered.  */
1057   while (r1 != NULL && r2 != NULL)
1058     {
1059       if (r1->start > r2->finish)
1060         r1 = r1->next;
1061       else if (r2->start > r1->finish)
1062         r2 = r2->next;
1063       else
1064         return true;
1065     }
1066   return false;
1067 }
1068
1069 /* Free allocno live range R.  */
1070 void
1071 ira_finish_live_range (live_range_t r)
1072 {
1073   pool_free (live_range_pool, r);
1074 }
1075
1076 /* Free list of allocno live ranges starting with R.  */
1077 void
1078 ira_finish_live_range_list (live_range_t r)
1079 {
1080   live_range_t next_r;
1081
1082   for (; r != NULL; r = next_r)
1083     {
1084       next_r = r->next;
1085       ira_finish_live_range (r);
1086     }
1087 }
1088
1089 /* Free updated register costs of allocno A.  */
1090 void
1091 ira_free_allocno_updated_costs (ira_allocno_t a)
1092 {
1093   enum reg_class aclass;
1094
1095   aclass = ALLOCNO_CLASS (a);
1096   if (ALLOCNO_UPDATED_HARD_REG_COSTS (a) != NULL)
1097     ira_free_cost_vector (ALLOCNO_UPDATED_HARD_REG_COSTS (a), aclass);
1098   ALLOCNO_UPDATED_HARD_REG_COSTS (a) = NULL;
1099   if (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) != NULL)
1100     ira_free_cost_vector (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a),
1101                           aclass);
1102   ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) = NULL;
1103 }
1104
1105 /* Free and nullify all cost vectors allocated earlier for allocno
1106    A.  */
1107 static void
1108 ira_free_allocno_costs (ira_allocno_t a)
1109 {
1110   enum reg_class aclass = ALLOCNO_CLASS (a);
1111   ira_object_t obj;
1112   ira_allocno_object_iterator oi;
1113
1114   FOR_EACH_ALLOCNO_OBJECT (a, obj, oi)
1115     {
1116       ira_finish_live_range_list (OBJECT_LIVE_RANGES (obj));
1117       ira_object_id_map[OBJECT_CONFLICT_ID (obj)] = NULL;
1118       if (OBJECT_CONFLICT_ARRAY (obj) != NULL)
1119         ira_free (OBJECT_CONFLICT_ARRAY (obj));
1120       pool_free (object_pool, obj);
1121     }
1122
1123   ira_allocnos[ALLOCNO_NUM (a)] = NULL;
1124   if (ALLOCNO_HARD_REG_COSTS (a) != NULL)
1125     ira_free_cost_vector (ALLOCNO_HARD_REG_COSTS (a), aclass);
1126   if (ALLOCNO_CONFLICT_HARD_REG_COSTS (a) != NULL)
1127     ira_free_cost_vector (ALLOCNO_CONFLICT_HARD_REG_COSTS (a), aclass);
1128   if (ALLOCNO_UPDATED_HARD_REG_COSTS (a) != NULL)
1129     ira_free_cost_vector (ALLOCNO_UPDATED_HARD_REG_COSTS (a), aclass);
1130   if (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) != NULL)
1131     ira_free_cost_vector (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a),
1132                           aclass);
1133   ALLOCNO_HARD_REG_COSTS (a) = NULL;
1134   ALLOCNO_CONFLICT_HARD_REG_COSTS (a) = NULL;
1135   ALLOCNO_UPDATED_HARD_REG_COSTS (a) = NULL;
1136   ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) = NULL;
1137 }
1138
1139 /* Free the memory allocated for allocno A.  */
1140 static void
1141 finish_allocno (ira_allocno_t a)
1142 {
1143   ira_free_allocno_costs (a);
1144   pool_free (allocno_pool, a);
1145 }
1146
1147 /* Free the memory allocated for all allocnos.  */
1148 static void
1149 finish_allocnos (void)
1150 {
1151   ira_allocno_t a;
1152   ira_allocno_iterator ai;
1153
1154   FOR_EACH_ALLOCNO (a, ai)
1155     finish_allocno (a);
1156   ira_free (ira_regno_allocno_map);
1157   ira_object_id_map_vec.release ();
1158   allocno_vec.release ();
1159   free_alloc_pool (allocno_pool);
1160   free_alloc_pool (object_pool);
1161   free_alloc_pool (live_range_pool);
1162 }
1163
1164 \f
1165
1166 /* Pools for copies.  */
1167 static alloc_pool copy_pool;
1168
1169 /* Vec containing references to all created copies.  It is a
1170    container of array ira_copies.  */
1171 static vec<ira_copy_t> copy_vec;
1172
1173 /* The function initializes data concerning allocno copies.  */
1174 static void
1175 initiate_copies (void)
1176 {
1177   copy_pool
1178     = create_alloc_pool ("copies", sizeof (struct ira_allocno_copy), 100);
1179   copy_vec.create (get_max_uid ());
1180   ira_copies = NULL;
1181   ira_copies_num = 0;
1182 }
1183
1184 /* Return copy connecting A1 and A2 and originated from INSN of
1185    LOOP_TREE_NODE if any.  */
1186 static ira_copy_t
1187 find_allocno_copy (ira_allocno_t a1, ira_allocno_t a2, rtx insn,
1188                    ira_loop_tree_node_t loop_tree_node)
1189 {
1190   ira_copy_t cp, next_cp;
1191   ira_allocno_t another_a;
1192
1193   for (cp = ALLOCNO_COPIES (a1); cp != NULL; cp = next_cp)
1194     {
1195       if (cp->first == a1)
1196         {
1197           next_cp = cp->next_first_allocno_copy;
1198           another_a = cp->second;
1199         }
1200       else if (cp->second == a1)
1201         {
1202           next_cp = cp->next_second_allocno_copy;
1203           another_a = cp->first;
1204         }
1205       else
1206         gcc_unreachable ();
1207       if (another_a == a2 && cp->insn == insn
1208           && cp->loop_tree_node == loop_tree_node)
1209         return cp;
1210     }
1211   return NULL;
1212 }
1213
1214 /* Create and return copy with given attributes LOOP_TREE_NODE, FIRST,
1215    SECOND, FREQ, CONSTRAINT_P, and INSN.  */
1216 ira_copy_t
1217 ira_create_copy (ira_allocno_t first, ira_allocno_t second, int freq,
1218                  bool constraint_p, rtx insn,
1219                  ira_loop_tree_node_t loop_tree_node)
1220 {
1221   ira_copy_t cp;
1222
1223   cp = (ira_copy_t) pool_alloc (copy_pool);
1224   cp->num = ira_copies_num;
1225   cp->first = first;
1226   cp->second = second;
1227   cp->freq = freq;
1228   cp->constraint_p = constraint_p;
1229   cp->insn = insn;
1230   cp->loop_tree_node = loop_tree_node;
1231   copy_vec.safe_push (cp);
1232   ira_copies = copy_vec.address ();
1233   ira_copies_num = copy_vec.length ();
1234   return cp;
1235 }
1236
1237 /* Attach a copy CP to allocnos involved into the copy.  */
1238 void
1239 ira_add_allocno_copy_to_list (ira_copy_t cp)
1240 {
1241   ira_allocno_t first = cp->first, second = cp->second;
1242
1243   cp->prev_first_allocno_copy = NULL;
1244   cp->prev_second_allocno_copy = NULL;
1245   cp->next_first_allocno_copy = ALLOCNO_COPIES (first);
1246   if (cp->next_first_allocno_copy != NULL)
1247     {
1248       if (cp->next_first_allocno_copy->first == first)
1249         cp->next_first_allocno_copy->prev_first_allocno_copy = cp;
1250       else
1251         cp->next_first_allocno_copy->prev_second_allocno_copy = cp;
1252     }
1253   cp->next_second_allocno_copy = ALLOCNO_COPIES (second);
1254   if (cp->next_second_allocno_copy != NULL)
1255     {
1256       if (cp->next_second_allocno_copy->second == second)
1257         cp->next_second_allocno_copy->prev_second_allocno_copy = cp;
1258       else
1259         cp->next_second_allocno_copy->prev_first_allocno_copy = cp;
1260     }
1261   ALLOCNO_COPIES (first) = cp;
1262   ALLOCNO_COPIES (second) = cp;
1263 }
1264
1265 /* Make a copy CP a canonical copy where number of the
1266    first allocno is less than the second one.  */
1267 void
1268 ira_swap_allocno_copy_ends_if_necessary (ira_copy_t cp)
1269 {
1270   ira_allocno_t temp;
1271   ira_copy_t temp_cp;
1272
1273   if (ALLOCNO_NUM (cp->first) <= ALLOCNO_NUM (cp->second))
1274     return;
1275
1276   temp = cp->first;
1277   cp->first = cp->second;
1278   cp->second = temp;
1279
1280   temp_cp = cp->prev_first_allocno_copy;
1281   cp->prev_first_allocno_copy = cp->prev_second_allocno_copy;
1282   cp->prev_second_allocno_copy = temp_cp;
1283
1284   temp_cp = cp->next_first_allocno_copy;
1285   cp->next_first_allocno_copy = cp->next_second_allocno_copy;
1286   cp->next_second_allocno_copy = temp_cp;
1287 }
1288
1289 /* Create (or update frequency if the copy already exists) and return
1290    the copy of allocnos FIRST and SECOND with frequency FREQ
1291    corresponding to move insn INSN (if any) and originated from
1292    LOOP_TREE_NODE.  */
1293 ira_copy_t
1294 ira_add_allocno_copy (ira_allocno_t first, ira_allocno_t second, int freq,
1295                       bool constraint_p, rtx insn,
1296                       ira_loop_tree_node_t loop_tree_node)
1297 {
1298   ira_copy_t cp;
1299
1300   if ((cp = find_allocno_copy (first, second, insn, loop_tree_node)) != NULL)
1301     {
1302       cp->freq += freq;
1303       return cp;
1304     }
1305   cp = ira_create_copy (first, second, freq, constraint_p, insn,
1306                         loop_tree_node);
1307   ira_assert (first != NULL && second != NULL);
1308   ira_add_allocno_copy_to_list (cp);
1309   ira_swap_allocno_copy_ends_if_necessary (cp);
1310   return cp;
1311 }
1312
1313 /* Print info about copy CP into file F.  */
1314 static void
1315 print_copy (FILE *f, ira_copy_t cp)
1316 {
1317   fprintf (f, "  cp%d:a%d(r%d)<->a%d(r%d)@%d:%s\n", cp->num,
1318            ALLOCNO_NUM (cp->first), ALLOCNO_REGNO (cp->first),
1319            ALLOCNO_NUM (cp->second), ALLOCNO_REGNO (cp->second), cp->freq,
1320            cp->insn != NULL
1321            ? "move" : cp->constraint_p ? "constraint" : "shuffle");
1322 }
1323
1324 /* Print info about copy CP into stderr.  */
1325 void
1326 ira_debug_copy (ira_copy_t cp)
1327 {
1328   print_copy (stderr, cp);
1329 }
1330
1331 /* Print info about all copies into file F.  */
1332 static void
1333 print_copies (FILE *f)
1334 {
1335   ira_copy_t cp;
1336   ira_copy_iterator ci;
1337
1338   FOR_EACH_COPY (cp, ci)
1339     print_copy (f, cp);
1340 }
1341
1342 /* Print info about all copies into stderr.  */
1343 void
1344 ira_debug_copies (void)
1345 {
1346   print_copies (stderr);
1347 }
1348
1349 /* Print info about copies involving allocno A into file F.  */
1350 static void
1351 print_allocno_copies (FILE *f, ira_allocno_t a)
1352 {
1353   ira_allocno_t another_a;
1354   ira_copy_t cp, next_cp;
1355
1356   fprintf (f, " a%d(r%d):", ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
1357   for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
1358     {
1359       if (cp->first == a)
1360         {
1361           next_cp = cp->next_first_allocno_copy;
1362           another_a = cp->second;
1363         }
1364       else if (cp->second == a)
1365         {
1366           next_cp = cp->next_second_allocno_copy;
1367           another_a = cp->first;
1368         }
1369       else
1370         gcc_unreachable ();
1371       fprintf (f, " cp%d:a%d(r%d)@%d", cp->num,
1372                ALLOCNO_NUM (another_a), ALLOCNO_REGNO (another_a), cp->freq);
1373     }
1374   fprintf (f, "\n");
1375 }
1376
1377 /* Print info about copies involving allocno A into stderr.  */
1378 void
1379 ira_debug_allocno_copies (ira_allocno_t a)
1380 {
1381   print_allocno_copies (stderr, a);
1382 }
1383
1384 /* The function frees memory allocated for copy CP.  */
1385 static void
1386 finish_copy (ira_copy_t cp)
1387 {
1388   pool_free (copy_pool, cp);
1389 }
1390
1391
1392 /* Free memory allocated for all copies.  */
1393 static void
1394 finish_copies (void)
1395 {
1396   ira_copy_t cp;
1397   ira_copy_iterator ci;
1398
1399   FOR_EACH_COPY (cp, ci)
1400     finish_copy (cp);
1401   copy_vec.release ();
1402   free_alloc_pool (copy_pool);
1403 }
1404
1405 \f
1406
1407 /* Pools for cost vectors.  It is defined only for allocno classes.  */
1408 static alloc_pool cost_vector_pool[N_REG_CLASSES];
1409
1410 /* The function initiates work with hard register cost vectors.  It
1411    creates allocation pool for each allocno class.  */
1412 static void
1413 initiate_cost_vectors (void)
1414 {
1415   int i;
1416   enum reg_class aclass;
1417
1418   for (i = 0; i < ira_allocno_classes_num; i++)
1419     {
1420       aclass = ira_allocno_classes[i];
1421       cost_vector_pool[aclass]
1422         = create_alloc_pool ("cost vectors",
1423                              sizeof (int) * ira_class_hard_regs_num[aclass],
1424                              100);
1425     }
1426 }
1427
1428 /* Allocate and return a cost vector VEC for ACLASS.  */
1429 int *
1430 ira_allocate_cost_vector (reg_class_t aclass)
1431 {
1432   return (int *) pool_alloc (cost_vector_pool[(int) aclass]);
1433 }
1434
1435 /* Free a cost vector VEC for ACLASS.  */
1436 void
1437 ira_free_cost_vector (int *vec, reg_class_t aclass)
1438 {
1439   ira_assert (vec != NULL);
1440   pool_free (cost_vector_pool[(int) aclass], vec);
1441 }
1442
1443 /* Finish work with hard register cost vectors.  Release allocation
1444    pool for each allocno class.  */
1445 static void
1446 finish_cost_vectors (void)
1447 {
1448   int i;
1449   enum reg_class aclass;
1450
1451   for (i = 0; i < ira_allocno_classes_num; i++)
1452     {
1453       aclass = ira_allocno_classes[i];
1454       free_alloc_pool (cost_vector_pool[aclass]);
1455     }
1456 }
1457
1458 \f
1459
1460 /* Compute a post-ordering of the reverse control flow of the loop body
1461    designated by the children nodes of LOOP_NODE, whose body nodes in
1462    pre-order are input as LOOP_PREORDER.  Return a VEC with a post-order
1463    of the reverse loop body.
1464
1465    For the post-order of the reverse CFG, we visit the basic blocks in
1466    LOOP_PREORDER array in the reverse order of where they appear.
1467    This is important: We do not just want to compute a post-order of
1468    the reverse CFG, we want to make a best-guess for a visiting order that
1469    minimizes the number of chain elements per allocno live range.  If the
1470    blocks would be visited in a different order, we would still compute a
1471    correct post-ordering but it would be less likely that two nodes
1472    connected by an edge in the CFG are neighbours in the topsort.  */
1473
1474 static vec<ira_loop_tree_node_t>
1475 ira_loop_tree_body_rev_postorder (ira_loop_tree_node_t loop_node ATTRIBUTE_UNUSED,
1476                                   vec<ira_loop_tree_node_t> loop_preorder)
1477 {
1478   vec<ira_loop_tree_node_t> topsort_nodes = vNULL;
1479   unsigned int n_loop_preorder;
1480
1481   n_loop_preorder = loop_preorder.length ();
1482   if (n_loop_preorder != 0)
1483     {
1484       ira_loop_tree_node_t subloop_node;
1485       unsigned int i;
1486       vec<ira_loop_tree_node_t> dfs_stack;
1487
1488       /* This is a bit of strange abuse of the BB_VISITED flag:  We use
1489          the flag to mark blocks we still have to visit to add them to
1490          our post-order.  Define an alias to avoid confusion.  */
1491 #define BB_TO_VISIT BB_VISITED
1492
1493       FOR_EACH_VEC_ELT (loop_preorder, i, subloop_node)
1494         {
1495           gcc_checking_assert (! (subloop_node->bb->flags & BB_TO_VISIT));
1496           subloop_node->bb->flags |= BB_TO_VISIT;
1497         }
1498
1499       topsort_nodes.create (n_loop_preorder);
1500       dfs_stack.create (n_loop_preorder);
1501
1502       FOR_EACH_VEC_ELT_REVERSE (loop_preorder, i, subloop_node)
1503         {
1504           if (! (subloop_node->bb->flags & BB_TO_VISIT))
1505             continue;
1506
1507           subloop_node->bb->flags &= ~BB_TO_VISIT;
1508           dfs_stack.quick_push (subloop_node);
1509           while (! dfs_stack.is_empty ())
1510             {
1511               edge e;
1512               edge_iterator ei;
1513
1514               ira_loop_tree_node_t n = dfs_stack.last ();
1515               FOR_EACH_EDGE (e, ei, n->bb->preds)
1516                 {
1517                   ira_loop_tree_node_t pred_node;
1518                   basic_block pred_bb = e->src;
1519
1520                   if (e->src == ENTRY_BLOCK_PTR)
1521                     continue;
1522
1523                   pred_node = IRA_BB_NODE_BY_INDEX (pred_bb->index);
1524                   if (pred_node != n
1525                       && (pred_node->bb->flags & BB_TO_VISIT))
1526                     {
1527                       pred_node->bb->flags &= ~BB_TO_VISIT;
1528                       dfs_stack.quick_push (pred_node);
1529                     }
1530                 }
1531               if (n == dfs_stack.last ())
1532                 {
1533                   dfs_stack.pop ();
1534                   topsort_nodes.quick_push (n);
1535                 }
1536             }
1537         }
1538
1539 #undef BB_TO_VISIT
1540       dfs_stack.release ();
1541     }
1542
1543   gcc_assert (topsort_nodes.length () == n_loop_preorder);
1544   return topsort_nodes;
1545 }
1546
1547 /* The current loop tree node and its regno allocno map.  */
1548 ira_loop_tree_node_t ira_curr_loop_tree_node;
1549 ira_allocno_t *ira_curr_regno_allocno_map;
1550
1551 /* This recursive function traverses loop tree with root LOOP_NODE
1552    calling non-null functions PREORDER_FUNC and POSTORDER_FUNC
1553    correspondingly in preorder and postorder.  The function sets up
1554    IRA_CURR_LOOP_TREE_NODE and IRA_CURR_REGNO_ALLOCNO_MAP.  If BB_P,
1555    basic block nodes of LOOP_NODE is also processed (before its
1556    subloop nodes).
1557
1558    If BB_P is set and POSTORDER_FUNC is given, the basic blocks in
1559    the loop are passed in the *reverse* post-order of the *reverse*
1560    CFG.  This is only used by ira_create_allocno_live_ranges, which
1561    wants to visit basic blocks in this order to minimize the number
1562    of elements per live range chain.
1563    Note that the loop tree nodes are still visited in the normal,
1564    forward post-order of  the loop tree.  */
1565
1566 void
1567 ira_traverse_loop_tree (bool bb_p, ira_loop_tree_node_t loop_node,
1568                         void (*preorder_func) (ira_loop_tree_node_t),
1569                         void (*postorder_func) (ira_loop_tree_node_t))
1570 {
1571   ira_loop_tree_node_t subloop_node;
1572
1573   ira_assert (loop_node->bb == NULL);
1574   ira_curr_loop_tree_node = loop_node;
1575   ira_curr_regno_allocno_map = ira_curr_loop_tree_node->regno_allocno_map;
1576
1577   if (preorder_func != NULL)
1578     (*preorder_func) (loop_node);
1579
1580   if (bb_p)
1581     {
1582       vec<ira_loop_tree_node_t>
1583           loop_preorder = vNULL;
1584       unsigned int i;
1585
1586       /* Add all nodes to the set of nodes to visit.  The IRA loop tree
1587          is set up such that nodes in the loop body appear in a pre-order
1588          of their place in the CFG.  */
1589       for (subloop_node = loop_node->children;
1590            subloop_node != NULL;
1591            subloop_node = subloop_node->next)
1592         if (subloop_node->bb != NULL)
1593           loop_preorder.safe_push (subloop_node);
1594
1595       if (preorder_func != NULL)
1596         FOR_EACH_VEC_ELT (loop_preorder, i, subloop_node)
1597           (*preorder_func) (subloop_node);
1598
1599       if (postorder_func != NULL)
1600         {
1601           vec<ira_loop_tree_node_t> loop_rev_postorder =
1602             ira_loop_tree_body_rev_postorder (loop_node, loop_preorder);
1603           FOR_EACH_VEC_ELT_REVERSE (loop_rev_postorder, i, subloop_node)
1604             (*postorder_func) (subloop_node);
1605           loop_rev_postorder.release ();
1606         }
1607
1608       loop_preorder.release ();
1609     }
1610
1611   for (subloop_node = loop_node->subloops;
1612        subloop_node != NULL;
1613        subloop_node = subloop_node->subloop_next)
1614     {
1615       ira_assert (subloop_node->bb == NULL);
1616       ira_traverse_loop_tree (bb_p, subloop_node,
1617                               preorder_func, postorder_func);
1618     }
1619
1620   ira_curr_loop_tree_node = loop_node;
1621   ira_curr_regno_allocno_map = ira_curr_loop_tree_node->regno_allocno_map;
1622
1623   if (postorder_func != NULL)
1624     (*postorder_func) (loop_node);
1625 }
1626
1627 \f
1628
1629 /* The basic block currently being processed.  */
1630 static basic_block curr_bb;
1631
1632 /* This recursive function creates allocnos corresponding to
1633    pseudo-registers containing in X.  True OUTPUT_P means that X is
1634    a lvalue.  */
1635 static void
1636 create_insn_allocnos (rtx x, bool output_p)
1637 {
1638   int i, j;
1639   const char *fmt;
1640   enum rtx_code code = GET_CODE (x);
1641
1642   if (code == REG)
1643     {
1644       int regno;
1645
1646       if ((regno = REGNO (x)) >= FIRST_PSEUDO_REGISTER)
1647         {
1648           ira_allocno_t a;
1649
1650           if ((a = ira_curr_regno_allocno_map[regno]) == NULL)
1651             a = ira_create_allocno (regno, false, ira_curr_loop_tree_node);
1652
1653           ALLOCNO_NREFS (a)++;
1654           ALLOCNO_FREQ (a) += REG_FREQ_FROM_BB (curr_bb);
1655           if (output_p)
1656             bitmap_set_bit (ira_curr_loop_tree_node->modified_regnos, regno);
1657         }
1658       return;
1659     }
1660   else if (code == SET)
1661     {
1662       create_insn_allocnos (SET_DEST (x), true);
1663       create_insn_allocnos (SET_SRC (x), false);
1664       return;
1665     }
1666   else if (code == CLOBBER)
1667     {
1668       create_insn_allocnos (XEXP (x, 0), true);
1669       return;
1670     }
1671   else if (code == MEM)
1672     {
1673       create_insn_allocnos (XEXP (x, 0), false);
1674       return;
1675     }
1676   else if (code == PRE_DEC || code == POST_DEC || code == PRE_INC ||
1677            code == POST_INC || code == POST_MODIFY || code == PRE_MODIFY)
1678     {
1679       create_insn_allocnos (XEXP (x, 0), true);
1680       create_insn_allocnos (XEXP (x, 0), false);
1681       return;
1682     }
1683
1684   fmt = GET_RTX_FORMAT (code);
1685   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1686     {
1687       if (fmt[i] == 'e')
1688         create_insn_allocnos (XEXP (x, i), output_p);
1689       else if (fmt[i] == 'E')
1690         for (j = 0; j < XVECLEN (x, i); j++)
1691           create_insn_allocnos (XVECEXP (x, i, j), output_p);
1692     }
1693 }
1694
1695 /* Create allocnos corresponding to pseudo-registers living in the
1696    basic block represented by the corresponding loop tree node
1697    BB_NODE.  */
1698 static void
1699 create_bb_allocnos (ira_loop_tree_node_t bb_node)
1700 {
1701   basic_block bb;
1702   rtx insn;
1703   unsigned int i;
1704   bitmap_iterator bi;
1705
1706   curr_bb = bb = bb_node->bb;
1707   ira_assert (bb != NULL);
1708   FOR_BB_INSNS_REVERSE (bb, insn)
1709     if (NONDEBUG_INSN_P (insn))
1710       create_insn_allocnos (PATTERN (insn), false);
1711   /* It might be a allocno living through from one subloop to
1712      another.  */
1713   EXECUTE_IF_SET_IN_REG_SET (df_get_live_in (bb), FIRST_PSEUDO_REGISTER, i, bi)
1714     if (ira_curr_regno_allocno_map[i] == NULL)
1715       ira_create_allocno (i, false, ira_curr_loop_tree_node);
1716 }
1717
1718 /* Create allocnos corresponding to pseudo-registers living on edge E
1719    (a loop entry or exit).  Also mark the allocnos as living on the
1720    loop border. */
1721 static void
1722 create_loop_allocnos (edge e)
1723 {
1724   unsigned int i;
1725   bitmap live_in_regs, border_allocnos;
1726   bitmap_iterator bi;
1727   ira_loop_tree_node_t parent;
1728
1729   live_in_regs = df_get_live_in (e->dest);
1730   border_allocnos = ira_curr_loop_tree_node->border_allocnos;
1731   EXECUTE_IF_SET_IN_REG_SET (df_get_live_out (e->src),
1732                              FIRST_PSEUDO_REGISTER, i, bi)
1733     if (bitmap_bit_p (live_in_regs, i))
1734       {
1735         if (ira_curr_regno_allocno_map[i] == NULL)
1736           {
1737             /* The order of creations is important for right
1738                ira_regno_allocno_map.  */
1739             if ((parent = ira_curr_loop_tree_node->parent) != NULL
1740                 && parent->regno_allocno_map[i] == NULL)
1741               ira_create_allocno (i, false, parent);
1742             ira_create_allocno (i, false, ira_curr_loop_tree_node);
1743           }
1744         bitmap_set_bit (border_allocnos,
1745                         ALLOCNO_NUM (ira_curr_regno_allocno_map[i]));
1746       }
1747 }
1748
1749 /* Create allocnos corresponding to pseudo-registers living in loop
1750    represented by the corresponding loop tree node LOOP_NODE.  This
1751    function is called by ira_traverse_loop_tree.  */
1752 static void
1753 create_loop_tree_node_allocnos (ira_loop_tree_node_t loop_node)
1754 {
1755   if (loop_node->bb != NULL)
1756     create_bb_allocnos (loop_node);
1757   else if (loop_node != ira_loop_tree_root)
1758     {
1759       int i;
1760       edge_iterator ei;
1761       edge e;
1762       vec<edge> edges;
1763
1764       ira_assert (current_loops != NULL);
1765       FOR_EACH_EDGE (e, ei, loop_node->loop->header->preds)
1766         if (e->src != loop_node->loop->latch)
1767           create_loop_allocnos (e);
1768
1769       edges = get_loop_exit_edges (loop_node->loop);
1770       FOR_EACH_VEC_ELT (edges, i, e)
1771         create_loop_allocnos (e);
1772       edges.release ();
1773     }
1774 }
1775
1776 /* Propagate information about allocnos modified inside the loop given
1777    by its LOOP_TREE_NODE to its parent.  */
1778 static void
1779 propagate_modified_regnos (ira_loop_tree_node_t loop_tree_node)
1780 {
1781   if (loop_tree_node == ira_loop_tree_root)
1782     return;
1783   ira_assert (loop_tree_node->bb == NULL);
1784   bitmap_ior_into (loop_tree_node->parent->modified_regnos,
1785                    loop_tree_node->modified_regnos);
1786 }
1787
1788 /* Propagate new info about allocno A (see comments about accumulated
1789    info in allocno definition) to the corresponding allocno on upper
1790    loop tree level.  So allocnos on upper levels accumulate
1791    information about the corresponding allocnos in nested regions.
1792    The new info means allocno info finally calculated in this
1793    file.  */
1794 static void
1795 propagate_allocno_info (void)
1796 {
1797   int i;
1798   ira_allocno_t a, parent_a;
1799   ira_loop_tree_node_t parent;
1800   enum reg_class aclass;
1801
1802   if (flag_ira_region != IRA_REGION_ALL
1803       && flag_ira_region != IRA_REGION_MIXED)
1804     return;
1805   for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--)
1806     for (a = ira_regno_allocno_map[i];
1807          a != NULL;
1808          a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
1809       if ((parent = ALLOCNO_LOOP_TREE_NODE (a)->parent) != NULL
1810           && (parent_a = parent->regno_allocno_map[i]) != NULL
1811           /* There are no caps yet at this point.  So use
1812              border_allocnos to find allocnos for the propagation.  */
1813           && bitmap_bit_p (ALLOCNO_LOOP_TREE_NODE (a)->border_allocnos,
1814                            ALLOCNO_NUM (a)))
1815         {
1816           if (! ALLOCNO_BAD_SPILL_P (a))
1817             ALLOCNO_BAD_SPILL_P (parent_a) = false;
1818           ALLOCNO_NREFS (parent_a) += ALLOCNO_NREFS (a);
1819           ALLOCNO_FREQ (parent_a) += ALLOCNO_FREQ (a);
1820           ALLOCNO_CALL_FREQ (parent_a) += ALLOCNO_CALL_FREQ (a);
1821           merge_hard_reg_conflicts (a, parent_a, true);
1822           ALLOCNO_CALLS_CROSSED_NUM (parent_a)
1823             += ALLOCNO_CALLS_CROSSED_NUM (a);
1824           ALLOCNO_CHEAP_CALLS_CROSSED_NUM (parent_a)
1825             += ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a);
1826           ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (parent_a)
1827             += ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a);
1828           aclass = ALLOCNO_CLASS (a);
1829           ira_assert (aclass == ALLOCNO_CLASS (parent_a));
1830           ira_allocate_and_accumulate_costs
1831             (&ALLOCNO_HARD_REG_COSTS (parent_a), aclass,
1832              ALLOCNO_HARD_REG_COSTS (a));
1833           ira_allocate_and_accumulate_costs
1834             (&ALLOCNO_CONFLICT_HARD_REG_COSTS (parent_a),
1835              aclass,
1836              ALLOCNO_CONFLICT_HARD_REG_COSTS (a));
1837           ALLOCNO_CLASS_COST (parent_a)
1838             += ALLOCNO_CLASS_COST (a);
1839           ALLOCNO_MEMORY_COST (parent_a) += ALLOCNO_MEMORY_COST (a);
1840         }
1841 }
1842
1843 /* Create allocnos corresponding to pseudo-registers in the current
1844    function.  Traverse the loop tree for this.  */
1845 static void
1846 create_allocnos (void)
1847 {
1848   /* We need to process BB first to correctly link allocnos by member
1849      next_regno_allocno.  */
1850   ira_traverse_loop_tree (true, ira_loop_tree_root,
1851                           create_loop_tree_node_allocnos, NULL);
1852   if (optimize)
1853     ira_traverse_loop_tree (false, ira_loop_tree_root, NULL,
1854                             propagate_modified_regnos);
1855 }
1856
1857 \f
1858
1859 /* The page contains function to remove some regions from a separate
1860    register allocation.  We remove regions whose separate allocation
1861    will hardly improve the result.  As a result we speed up regional
1862    register allocation.  */
1863
1864 /* The function changes the object in range list given by R to OBJ.  */
1865 static void
1866 change_object_in_range_list (live_range_t r, ira_object_t obj)
1867 {
1868   for (; r != NULL; r = r->next)
1869     r->object = obj;
1870 }
1871
1872 /* Move all live ranges associated with allocno FROM to allocno TO.  */
1873 static void
1874 move_allocno_live_ranges (ira_allocno_t from, ira_allocno_t to)
1875 {
1876   int i;
1877   int n = ALLOCNO_NUM_OBJECTS (from);
1878
1879   gcc_assert (n == ALLOCNO_NUM_OBJECTS (to));
1880
1881   for (i = 0; i < n; i++)
1882     {
1883       ira_object_t from_obj = ALLOCNO_OBJECT (from, i);
1884       ira_object_t to_obj = ALLOCNO_OBJECT (to, i);
1885       live_range_t lr = OBJECT_LIVE_RANGES (from_obj);
1886
1887       if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL)
1888         {
1889           fprintf (ira_dump_file,
1890                    "      Moving ranges of a%dr%d to a%dr%d: ",
1891                    ALLOCNO_NUM (from), ALLOCNO_REGNO (from),
1892                    ALLOCNO_NUM (to), ALLOCNO_REGNO (to));
1893           ira_print_live_range_list (ira_dump_file, lr);
1894         }
1895       change_object_in_range_list (lr, to_obj);
1896       OBJECT_LIVE_RANGES (to_obj)
1897         = ira_merge_live_ranges (lr, OBJECT_LIVE_RANGES (to_obj));
1898       OBJECT_LIVE_RANGES (from_obj) = NULL;
1899     }
1900 }
1901
1902 static void
1903 copy_allocno_live_ranges (ira_allocno_t from, ira_allocno_t to)
1904 {
1905   int i;
1906   int n = ALLOCNO_NUM_OBJECTS (from);
1907
1908   gcc_assert (n == ALLOCNO_NUM_OBJECTS (to));
1909
1910   for (i = 0; i < n; i++)
1911     {
1912       ira_object_t from_obj = ALLOCNO_OBJECT (from, i);
1913       ira_object_t to_obj = ALLOCNO_OBJECT (to, i);
1914       live_range_t lr = OBJECT_LIVE_RANGES (from_obj);
1915
1916       if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL)
1917         {
1918           fprintf (ira_dump_file, "      Copying ranges of a%dr%d to a%dr%d: ",
1919                    ALLOCNO_NUM (from), ALLOCNO_REGNO (from),
1920                    ALLOCNO_NUM (to), ALLOCNO_REGNO (to));
1921           ira_print_live_range_list (ira_dump_file, lr);
1922         }
1923       lr = ira_copy_live_range_list (lr);
1924       change_object_in_range_list (lr, to_obj);
1925       OBJECT_LIVE_RANGES (to_obj)
1926         = ira_merge_live_ranges (lr, OBJECT_LIVE_RANGES (to_obj));
1927     }
1928 }
1929
1930 /* Return TRUE if NODE represents a loop with low register
1931    pressure.  */
1932 static bool
1933 low_pressure_loop_node_p (ira_loop_tree_node_t node)
1934 {
1935   int i;
1936   enum reg_class pclass;
1937
1938   if (node->bb != NULL)
1939     return false;
1940
1941   for (i = 0; i < ira_pressure_classes_num; i++)
1942     {
1943       pclass = ira_pressure_classes[i];
1944       if (node->reg_pressure[pclass] > ira_class_hard_regs_num[pclass]
1945           && ira_class_hard_regs_num[pclass] > 1)
1946         return false;
1947     }
1948   return true;
1949 }
1950
1951 #ifdef STACK_REGS
1952 /* Return TRUE if LOOP has a complex enter or exit edge.  We don't
1953    form a region from such loop if the target use stack register
1954    because reg-stack.c can not deal with such edges.  */
1955 static bool
1956 loop_with_complex_edge_p (struct loop *loop)
1957 {
1958   int i;
1959   edge_iterator ei;
1960   edge e;
1961   vec<edge> edges;
1962   bool res;
1963
1964   FOR_EACH_EDGE (e, ei, loop->header->preds)
1965     if (e->flags & EDGE_EH)
1966       return true;
1967   edges = get_loop_exit_edges (loop);
1968   res = false;
1969   FOR_EACH_VEC_ELT (edges, i, e)
1970     if (e->flags & EDGE_COMPLEX)
1971       {
1972         res = true;
1973         break;
1974       }
1975   edges.release ();
1976   return res;
1977 }
1978 #endif
1979
1980 /* Sort loops for marking them for removal.  We put already marked
1981    loops first, then less frequent loops next, and then outer loops
1982    next.  */
1983 static int
1984 loop_compare_func (const void *v1p, const void *v2p)
1985 {
1986   int diff;
1987   ira_loop_tree_node_t l1 = *(const ira_loop_tree_node_t *) v1p;
1988   ira_loop_tree_node_t l2 = *(const ira_loop_tree_node_t *) v2p;
1989
1990   ira_assert (l1->parent != NULL && l2->parent != NULL);
1991   if (l1->to_remove_p && ! l2->to_remove_p)
1992     return -1;
1993   if (! l1->to_remove_p && l2->to_remove_p)
1994     return 1;
1995   if ((diff = l1->loop->header->frequency - l2->loop->header->frequency) != 0)
1996     return diff;
1997   if ((diff = (int) loop_depth (l1->loop) - (int) loop_depth (l2->loop)) != 0)
1998     return diff;
1999   /* Make sorting stable.  */
2000   return l1->loop_num - l2->loop_num;
2001 }
2002
2003 /* Mark loops which should be removed from regional allocation.  We
2004    remove a loop with low register pressure inside another loop with
2005    register pressure.  In this case a separate allocation of the loop
2006    hardly helps (for irregular register file architecture it could
2007    help by choosing a better hard register in the loop but we prefer
2008    faster allocation even in this case).  We also remove cheap loops
2009    if there are more than IRA_MAX_LOOPS_NUM of them.  Loop with EH
2010    exit or enter edges are removed too because the allocation might
2011    require put pseudo moves on the EH edges (we could still do this
2012    for pseudos with caller saved hard registers in some cases but it
2013    is impossible to say here or during top-down allocation pass what
2014    hard register the pseudos get finally).  */
2015 static void
2016 mark_loops_for_removal (void)
2017 {
2018   int i, n;
2019   ira_loop_tree_node_t *sorted_loops;
2020   loop_p loop;
2021
2022   ira_assert (current_loops != NULL);
2023   sorted_loops
2024     = (ira_loop_tree_node_t *) ira_allocate (sizeof (ira_loop_tree_node_t)
2025                                              * number_of_loops ());
2026   for (n = i = 0; vec_safe_iterate (get_loops (), i, &loop); i++)
2027     if (ira_loop_nodes[i].regno_allocno_map != NULL)
2028       {
2029         if (ira_loop_nodes[i].parent == NULL)
2030           {
2031             /* Don't remove the root.  */
2032             ira_loop_nodes[i].to_remove_p = false;
2033             continue;
2034           }
2035         sorted_loops[n++] = &ira_loop_nodes[i];
2036         ira_loop_nodes[i].to_remove_p
2037           = ((low_pressure_loop_node_p (ira_loop_nodes[i].parent)
2038               && low_pressure_loop_node_p (&ira_loop_nodes[i]))
2039 #ifdef STACK_REGS
2040              || loop_with_complex_edge_p (ira_loop_nodes[i].loop)
2041 #endif
2042              );
2043       }
2044   qsort (sorted_loops, n, sizeof (ira_loop_tree_node_t), loop_compare_func);
2045   for (i = 0; n - i + 1 > IRA_MAX_LOOPS_NUM; i++)
2046     {
2047       sorted_loops[i]->to_remove_p = true;
2048       if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
2049         fprintf
2050           (ira_dump_file,
2051            "  Mark loop %d (header %d, freq %d, depth %d) for removal (%s)\n",
2052            sorted_loops[i]->loop_num, sorted_loops[i]->loop->header->index,
2053            sorted_loops[i]->loop->header->frequency,
2054            loop_depth (sorted_loops[i]->loop),
2055            low_pressure_loop_node_p (sorted_loops[i]->parent)
2056            && low_pressure_loop_node_p (sorted_loops[i])
2057            ? "low pressure" : "cheap loop");
2058     }
2059   ira_free (sorted_loops);
2060 }
2061
2062 /* Mark all loops but root for removing.  */
2063 static void
2064 mark_all_loops_for_removal (void)
2065 {
2066   int i;
2067   loop_p loop;
2068
2069   ira_assert (current_loops != NULL);
2070   FOR_EACH_VEC_SAFE_ELT (get_loops (), i, loop)
2071     if (ira_loop_nodes[i].regno_allocno_map != NULL)
2072       {
2073         if (ira_loop_nodes[i].parent == NULL)
2074           {
2075             /* Don't remove the root.  */
2076             ira_loop_nodes[i].to_remove_p = false;
2077             continue;
2078           }
2079         ira_loop_nodes[i].to_remove_p = true;
2080         if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
2081           fprintf
2082             (ira_dump_file,
2083              "  Mark loop %d (header %d, freq %d, depth %d) for removal\n",
2084              ira_loop_nodes[i].loop_num,
2085              ira_loop_nodes[i].loop->header->index,
2086              ira_loop_nodes[i].loop->header->frequency,
2087              loop_depth (ira_loop_nodes[i].loop));
2088       }
2089 }
2090
2091 /* Definition of vector of loop tree nodes.  */
2092
2093 /* Vec containing references to all removed loop tree nodes.  */
2094 static vec<ira_loop_tree_node_t> removed_loop_vec;
2095
2096 /* Vec containing references to all children of loop tree nodes.  */
2097 static vec<ira_loop_tree_node_t> children_vec;
2098
2099 /* Remove subregions of NODE if their separate allocation will not
2100    improve the result.  */
2101 static void
2102 remove_uneccesary_loop_nodes_from_loop_tree (ira_loop_tree_node_t node)
2103 {
2104   unsigned int start;
2105   bool remove_p;
2106   ira_loop_tree_node_t subnode;
2107
2108   remove_p = node->to_remove_p;
2109   if (! remove_p)
2110     children_vec.safe_push (node);
2111   start = children_vec.length ();
2112   for (subnode = node->children; subnode != NULL; subnode = subnode->next)
2113     if (subnode->bb == NULL)
2114       remove_uneccesary_loop_nodes_from_loop_tree (subnode);
2115     else
2116       children_vec.safe_push (subnode);
2117   node->children = node->subloops = NULL;
2118   if (remove_p)
2119     {
2120       removed_loop_vec.safe_push (node);
2121       return;
2122     }
2123   while (children_vec.length () > start)
2124     {
2125       subnode = children_vec.pop ();
2126       subnode->parent = node;
2127       subnode->next = node->children;
2128       node->children = subnode;
2129       if (subnode->bb == NULL)
2130         {
2131           subnode->subloop_next = node->subloops;
2132           node->subloops = subnode;
2133         }
2134     }
2135 }
2136
2137 /* Return TRUE if NODE is inside PARENT.  */
2138 static bool
2139 loop_is_inside_p (ira_loop_tree_node_t node, ira_loop_tree_node_t parent)
2140 {
2141   for (node = node->parent; node != NULL; node = node->parent)
2142     if (node == parent)
2143       return true;
2144   return false;
2145 }
2146
2147 /* Sort allocnos according to their order in regno allocno list.  */
2148 static int
2149 regno_allocno_order_compare_func (const void *v1p, const void *v2p)
2150 {
2151   ira_allocno_t a1 = *(const ira_allocno_t *) v1p;
2152   ira_allocno_t a2 = *(const ira_allocno_t *) v2p;
2153   ira_loop_tree_node_t n1 = ALLOCNO_LOOP_TREE_NODE (a1);
2154   ira_loop_tree_node_t n2 = ALLOCNO_LOOP_TREE_NODE (a2);
2155
2156   if (loop_is_inside_p (n1, n2))
2157     return -1;
2158   else if (loop_is_inside_p (n2, n1))
2159     return 1;
2160   /* If allocnos are equally good, sort by allocno numbers, so that
2161      the results of qsort leave nothing to chance.  We put allocnos
2162      with higher number first in the list because it is the original
2163      order for allocnos from loops on the same levels.  */
2164   return ALLOCNO_NUM (a2) - ALLOCNO_NUM (a1);
2165 }
2166
2167 /* This array is used to sort allocnos to restore allocno order in
2168    the regno allocno list.  */
2169 static ira_allocno_t *regno_allocnos;
2170
2171 /* Restore allocno order for REGNO in the regno allocno list.  */
2172 static void
2173 ira_rebuild_regno_allocno_list (int regno)
2174 {
2175   int i, n;
2176   ira_allocno_t a;
2177
2178   for (n = 0, a = ira_regno_allocno_map[regno];
2179        a != NULL;
2180        a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
2181     regno_allocnos[n++] = a;
2182   ira_assert (n > 0);
2183   qsort (regno_allocnos, n, sizeof (ira_allocno_t),
2184          regno_allocno_order_compare_func);
2185   for (i = 1; i < n; i++)
2186     ALLOCNO_NEXT_REGNO_ALLOCNO (regno_allocnos[i - 1]) = regno_allocnos[i];
2187   ALLOCNO_NEXT_REGNO_ALLOCNO (regno_allocnos[n - 1]) = NULL;
2188   ira_regno_allocno_map[regno] = regno_allocnos[0];
2189   if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
2190     fprintf (ira_dump_file, " Rebuilding regno allocno list for %d\n", regno);
2191 }
2192
2193 /* Propagate info from allocno FROM_A to allocno A.  */
2194 static void
2195 propagate_some_info_from_allocno (ira_allocno_t a, ira_allocno_t from_a)
2196 {
2197   enum reg_class aclass;
2198
2199   merge_hard_reg_conflicts (from_a, a, false);
2200   ALLOCNO_NREFS (a) += ALLOCNO_NREFS (from_a);
2201   ALLOCNO_FREQ (a) += ALLOCNO_FREQ (from_a);
2202   ALLOCNO_CALL_FREQ (a) += ALLOCNO_CALL_FREQ (from_a);
2203   ALLOCNO_CALLS_CROSSED_NUM (a) += ALLOCNO_CALLS_CROSSED_NUM (from_a);
2204   ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a)
2205     += ALLOCNO_CHEAP_CALLS_CROSSED_NUM (from_a);
2206   ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a)
2207     += ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (from_a);
2208   if (! ALLOCNO_BAD_SPILL_P (from_a))
2209     ALLOCNO_BAD_SPILL_P (a) = false;
2210   aclass = ALLOCNO_CLASS (from_a);
2211   ira_assert (aclass == ALLOCNO_CLASS (a));
2212   ira_allocate_and_accumulate_costs (&ALLOCNO_HARD_REG_COSTS (a), aclass,
2213                                      ALLOCNO_HARD_REG_COSTS (from_a));
2214   ira_allocate_and_accumulate_costs (&ALLOCNO_CONFLICT_HARD_REG_COSTS (a),
2215                                      aclass,
2216                                      ALLOCNO_CONFLICT_HARD_REG_COSTS (from_a));
2217   ALLOCNO_CLASS_COST (a) += ALLOCNO_CLASS_COST (from_a);
2218   ALLOCNO_MEMORY_COST (a) += ALLOCNO_MEMORY_COST (from_a);
2219 }
2220
2221 /* Remove allocnos from loops removed from the allocation
2222    consideration.  */
2223 static void
2224 remove_unnecessary_allocnos (void)
2225 {
2226   int regno;
2227   bool merged_p, rebuild_p;
2228   ira_allocno_t a, prev_a, next_a, parent_a;
2229   ira_loop_tree_node_t a_node, parent;
2230
2231   merged_p = false;
2232   regno_allocnos = NULL;
2233   for (regno = max_reg_num () - 1; regno >= FIRST_PSEUDO_REGISTER; regno--)
2234     {
2235       rebuild_p = false;
2236       for (prev_a = NULL, a = ira_regno_allocno_map[regno];
2237            a != NULL;
2238            a = next_a)
2239         {
2240           next_a = ALLOCNO_NEXT_REGNO_ALLOCNO (a);
2241           a_node = ALLOCNO_LOOP_TREE_NODE (a);
2242           if (! a_node->to_remove_p)
2243             prev_a = a;
2244           else
2245             {
2246               for (parent = a_node->parent;
2247                    (parent_a = parent->regno_allocno_map[regno]) == NULL
2248                      && parent->to_remove_p;
2249                    parent = parent->parent)
2250                 ;
2251               if (parent_a == NULL)
2252                 {
2253                   /* There are no allocnos with the same regno in
2254                      upper region -- just move the allocno to the
2255                      upper region.  */
2256                   prev_a = a;
2257                   ALLOCNO_LOOP_TREE_NODE (a) = parent;
2258                   parent->regno_allocno_map[regno] = a;
2259                   bitmap_set_bit (parent->all_allocnos, ALLOCNO_NUM (a));
2260                   rebuild_p = true;
2261                 }
2262               else
2263                 {
2264                   /* Remove the allocno and update info of allocno in
2265                      the upper region.  */
2266                   if (prev_a == NULL)
2267                     ira_regno_allocno_map[regno] = next_a;
2268                   else
2269                     ALLOCNO_NEXT_REGNO_ALLOCNO (prev_a) = next_a;
2270                   move_allocno_live_ranges (a, parent_a);
2271                   merged_p = true;
2272                   propagate_some_info_from_allocno (parent_a, a);
2273                   /* Remove it from the corresponding regno allocno
2274                      map to avoid info propagation of subsequent
2275                      allocno into this already removed allocno.  */
2276                   a_node->regno_allocno_map[regno] = NULL;
2277                   finish_allocno (a);
2278                 }
2279             }
2280         }
2281       if (rebuild_p)
2282         /* We need to restore the order in regno allocno list.  */
2283         {
2284           if (regno_allocnos == NULL)
2285             regno_allocnos
2286               = (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t)
2287                                                 * ira_allocnos_num);
2288           ira_rebuild_regno_allocno_list (regno);
2289         }
2290     }
2291   if (merged_p)
2292     ira_rebuild_start_finish_chains ();
2293   if (regno_allocnos != NULL)
2294     ira_free (regno_allocnos);
2295 }
2296
2297 /* Remove allocnos from all loops but the root.  */
2298 static void
2299 remove_low_level_allocnos (void)
2300 {
2301   int regno;
2302   bool merged_p, propagate_p;
2303   ira_allocno_t a, top_a;
2304   ira_loop_tree_node_t a_node, parent;
2305   ira_allocno_iterator ai;
2306
2307   merged_p = false;
2308   FOR_EACH_ALLOCNO (a, ai)
2309     {
2310       a_node = ALLOCNO_LOOP_TREE_NODE (a);
2311       if (a_node == ira_loop_tree_root || ALLOCNO_CAP_MEMBER (a) != NULL)
2312         continue;
2313       regno = ALLOCNO_REGNO (a);
2314       if ((top_a = ira_loop_tree_root->regno_allocno_map[regno]) == NULL)
2315         {
2316           ALLOCNO_LOOP_TREE_NODE (a) = ira_loop_tree_root;
2317           ira_loop_tree_root->regno_allocno_map[regno] = a;
2318           continue;
2319         }
2320       propagate_p = a_node->parent->regno_allocno_map[regno] == NULL;
2321       /* Remove the allocno and update info of allocno in the upper
2322          region.  */
2323       move_allocno_live_ranges (a, top_a);
2324       merged_p = true;
2325       if (propagate_p)
2326         propagate_some_info_from_allocno (top_a, a);
2327     }
2328   FOR_EACH_ALLOCNO (a, ai)
2329     {
2330       a_node = ALLOCNO_LOOP_TREE_NODE (a);
2331       if (a_node == ira_loop_tree_root)
2332         continue;
2333       parent = a_node->parent;
2334       regno = ALLOCNO_REGNO (a);
2335       if (ALLOCNO_CAP_MEMBER (a) != NULL)
2336         ira_assert (ALLOCNO_CAP (a) != NULL);
2337       else if (ALLOCNO_CAP (a) == NULL)
2338         ira_assert (parent->regno_allocno_map[regno] != NULL);
2339     }
2340   FOR_EACH_ALLOCNO (a, ai)
2341     {
2342       regno = ALLOCNO_REGNO (a);
2343       if (ira_loop_tree_root->regno_allocno_map[regno] == a)
2344         {
2345           ira_object_t obj;
2346           ira_allocno_object_iterator oi;
2347
2348           ira_regno_allocno_map[regno] = a;
2349           ALLOCNO_NEXT_REGNO_ALLOCNO (a) = NULL;
2350           ALLOCNO_CAP_MEMBER (a) = NULL;
2351           FOR_EACH_ALLOCNO_OBJECT (a, obj, oi)
2352             COPY_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (obj),
2353                                OBJECT_TOTAL_CONFLICT_HARD_REGS (obj));
2354 #ifdef STACK_REGS
2355           if (ALLOCNO_TOTAL_NO_STACK_REG_P (a))
2356             ALLOCNO_NO_STACK_REG_P (a) = true;
2357 #endif
2358         }
2359       else
2360         finish_allocno (a);
2361     }
2362   if (merged_p)
2363     ira_rebuild_start_finish_chains ();
2364 }
2365
2366 /* Remove loops from consideration.  We remove all loops except for
2367    root if ALL_P or loops for which a separate allocation will not
2368    improve the result.  We have to do this after allocno creation and
2369    their costs and allocno class evaluation because only after that
2370    the register pressure can be known and is calculated.  */
2371 static void
2372 remove_unnecessary_regions (bool all_p)
2373 {
2374   if (current_loops == NULL)
2375     return;
2376   if (all_p)
2377     mark_all_loops_for_removal ();
2378   else
2379     mark_loops_for_removal ();
2380   children_vec.create(last_basic_block + number_of_loops ());
2381   removed_loop_vec.create(last_basic_block + number_of_loops ());
2382   remove_uneccesary_loop_nodes_from_loop_tree (ira_loop_tree_root);
2383   children_vec.release ();
2384   if (all_p)
2385     remove_low_level_allocnos ();
2386   else
2387     remove_unnecessary_allocnos ();
2388   while (removed_loop_vec.length () > 0)
2389     finish_loop_tree_node (removed_loop_vec.pop ());
2390   removed_loop_vec.release ();
2391 }
2392
2393 \f
2394
2395 /* At this point true value of allocno attribute bad_spill_p means
2396    that there is an insn where allocno occurs and where the allocno
2397    can not be used as memory.  The function updates the attribute, now
2398    it can be true only for allocnos which can not be used as memory in
2399    an insn and in whose live ranges there is other allocno deaths.
2400    Spilling allocnos with true value will not improve the code because
2401    it will not make other allocnos colorable and additional reloads
2402    for the corresponding pseudo will be generated in reload pass for
2403    each insn it occurs.
2404
2405    This is a trick mentioned in one classic article of Chaitin etc
2406    which is frequently omitted in other implementations of RA based on
2407    graph coloring.  */
2408 static void
2409 update_bad_spill_attribute (void)
2410 {
2411   int i;
2412   ira_allocno_t a;
2413   ira_allocno_iterator ai;
2414   ira_allocno_object_iterator aoi;
2415   ira_object_t obj;
2416   live_range_t r;
2417   enum reg_class aclass;
2418   bitmap_head dead_points[N_REG_CLASSES];
2419
2420   for (i = 0; i < ira_allocno_classes_num; i++)
2421     {
2422       aclass = ira_allocno_classes[i];
2423       bitmap_initialize (&dead_points[aclass], &reg_obstack);
2424     }
2425   FOR_EACH_ALLOCNO (a, ai)
2426     {
2427       aclass = ALLOCNO_CLASS (a);
2428       if (aclass == NO_REGS)
2429         continue;
2430       FOR_EACH_ALLOCNO_OBJECT (a, obj, aoi)
2431         for (r = OBJECT_LIVE_RANGES (obj); r != NULL; r = r->next)
2432           bitmap_set_bit (&dead_points[aclass], r->finish);
2433     }
2434   FOR_EACH_ALLOCNO (a, ai)
2435     {
2436       aclass = ALLOCNO_CLASS (a);
2437       if (aclass == NO_REGS)
2438         continue;
2439       if (! ALLOCNO_BAD_SPILL_P (a))
2440         continue;
2441       FOR_EACH_ALLOCNO_OBJECT (a, obj, aoi)
2442         {
2443           for (r = OBJECT_LIVE_RANGES (obj); r != NULL; r = r->next)
2444             {
2445               for (i = r->start + 1; i < r->finish; i++)
2446                 if (bitmap_bit_p (&dead_points[aclass], i))
2447                   break;
2448               if (i < r->finish)
2449                 break;
2450             }
2451           if (r != NULL)
2452             {
2453               ALLOCNO_BAD_SPILL_P (a) = false;
2454               break;
2455             }
2456         }
2457     }
2458   for (i = 0; i < ira_allocno_classes_num; i++)
2459     {
2460       aclass = ira_allocno_classes[i];
2461       bitmap_clear (&dead_points[aclass]);
2462     }
2463 }
2464
2465 \f
2466
2467 /* Set up minimal and maximal live range points for allocnos.  */
2468 static void
2469 setup_min_max_allocno_live_range_point (void)
2470 {
2471   int i;
2472   ira_allocno_t a, parent_a, cap;
2473   ira_allocno_iterator ai;
2474 #ifdef ENABLE_IRA_CHECKING
2475   ira_object_iterator oi;
2476   ira_object_t obj;
2477 #endif
2478   live_range_t r;
2479   ira_loop_tree_node_t parent;
2480
2481   FOR_EACH_ALLOCNO (a, ai)
2482     {
2483       int n = ALLOCNO_NUM_OBJECTS (a);
2484
2485       for (i = 0; i < n; i++)
2486         {
2487           ira_object_t obj = ALLOCNO_OBJECT (a, i);
2488           r = OBJECT_LIVE_RANGES (obj);
2489           if (r == NULL)
2490             continue;
2491           OBJECT_MAX (obj) = r->finish;
2492           for (; r->next != NULL; r = r->next)
2493             ;
2494           OBJECT_MIN (obj) = r->start;
2495         }
2496     }
2497   for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--)
2498     for (a = ira_regno_allocno_map[i];
2499          a != NULL;
2500          a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
2501       {
2502         int j;
2503         int n = ALLOCNO_NUM_OBJECTS (a);
2504
2505         for (j = 0; j < n; j++)
2506           {
2507             ira_object_t obj = ALLOCNO_OBJECT (a, j);
2508             ira_object_t parent_obj;
2509
2510             if (OBJECT_MAX (obj) < 0)
2511               continue;
2512             ira_assert (ALLOCNO_CAP_MEMBER (a) == NULL);
2513             /* Accumulation of range info.  */
2514             if (ALLOCNO_CAP (a) != NULL)
2515               {
2516                 for (cap = ALLOCNO_CAP (a); cap != NULL; cap = ALLOCNO_CAP (cap))
2517                   {
2518                     ira_object_t cap_obj = ALLOCNO_OBJECT (cap, j);
2519                     if (OBJECT_MAX (cap_obj) < OBJECT_MAX (obj))
2520                       OBJECT_MAX (cap_obj) = OBJECT_MAX (obj);
2521                     if (OBJECT_MIN (cap_obj) > OBJECT_MIN (obj))
2522                       OBJECT_MIN (cap_obj) = OBJECT_MIN (obj);
2523                   }
2524                 continue;
2525               }
2526             if ((parent = ALLOCNO_LOOP_TREE_NODE (a)->parent) == NULL)
2527               continue;
2528             parent_a = parent->regno_allocno_map[i];
2529             parent_obj = ALLOCNO_OBJECT (parent_a, j);
2530             if (OBJECT_MAX (parent_obj) < OBJECT_MAX (obj))
2531               OBJECT_MAX (parent_obj) = OBJECT_MAX (obj);
2532             if (OBJECT_MIN (parent_obj) > OBJECT_MIN (obj))
2533               OBJECT_MIN (parent_obj) = OBJECT_MIN (obj);
2534           }
2535       }
2536 #ifdef ENABLE_IRA_CHECKING
2537   FOR_EACH_OBJECT (obj, oi)
2538     {
2539       if ((0 <= OBJECT_MIN (obj) && OBJECT_MIN (obj) <= ira_max_point)
2540           && (0 <= OBJECT_MAX (obj) && OBJECT_MAX (obj) <= ira_max_point))
2541         continue;
2542       gcc_unreachable ();
2543     }
2544 #endif
2545 }
2546
2547 /* Sort allocnos according to their live ranges.  Allocnos with
2548    smaller allocno class are put first unless we use priority
2549    coloring.  Allocnos with the same class are ordered according
2550    their start (min).  Allocnos with the same start are ordered
2551    according their finish (max).  */
2552 static int
2553 object_range_compare_func (const void *v1p, const void *v2p)
2554 {
2555   int diff;
2556   ira_object_t obj1 = *(const ira_object_t *) v1p;
2557   ira_object_t obj2 = *(const ira_object_t *) v2p;
2558   ira_allocno_t a1 = OBJECT_ALLOCNO (obj1);
2559   ira_allocno_t a2 = OBJECT_ALLOCNO (obj2);
2560
2561   if ((diff = OBJECT_MIN (obj1) - OBJECT_MIN (obj2)) != 0)
2562     return diff;
2563   if ((diff = OBJECT_MAX (obj1) - OBJECT_MAX (obj2)) != 0)
2564      return diff;
2565   return ALLOCNO_NUM (a1) - ALLOCNO_NUM (a2);
2566 }
2567
2568 /* Sort ira_object_id_map and set up conflict id of allocnos.  */
2569 static void
2570 sort_conflict_id_map (void)
2571 {
2572   int i, num;
2573   ira_allocno_t a;
2574   ira_allocno_iterator ai;
2575
2576   num = 0;
2577   FOR_EACH_ALLOCNO (a, ai)
2578     {
2579       ira_allocno_object_iterator oi;
2580       ira_object_t obj;
2581
2582       FOR_EACH_ALLOCNO_OBJECT (a, obj, oi)
2583         ira_object_id_map[num++] = obj;
2584     }
2585   qsort (ira_object_id_map, num, sizeof (ira_object_t),
2586          object_range_compare_func);
2587   for (i = 0; i < num; i++)
2588     {
2589       ira_object_t obj = ira_object_id_map[i];
2590
2591       gcc_assert (obj != NULL);
2592       OBJECT_CONFLICT_ID (obj) = i;
2593     }
2594   for (i = num; i < ira_objects_num; i++)
2595     ira_object_id_map[i] = NULL;
2596 }
2597
2598 /* Set up minimal and maximal conflict ids of allocnos with which
2599    given allocno can conflict.  */
2600 static void
2601 setup_min_max_conflict_allocno_ids (void)
2602 {
2603   int aclass;
2604   int i, j, min, max, start, finish, first_not_finished, filled_area_start;
2605   int *live_range_min, *last_lived;
2606   int word0_min, word0_max;
2607   ira_allocno_t a;
2608   ira_allocno_iterator ai;
2609
2610   live_range_min = (int *) ira_allocate (sizeof (int) * ira_objects_num);
2611   aclass = -1;
2612   first_not_finished = -1;
2613   for (i = 0; i < ira_objects_num; i++)
2614     {
2615       ira_object_t obj = ira_object_id_map[i];
2616
2617       if (obj == NULL)
2618         continue;
2619
2620       a = OBJECT_ALLOCNO (obj);
2621
2622       if (aclass < 0)
2623         {
2624           aclass = ALLOCNO_CLASS (a);
2625           min = i;
2626           first_not_finished = i;
2627         }
2628       else
2629         {
2630           start = OBJECT_MIN (obj);
2631           /* If we skip an allocno, the allocno with smaller ids will
2632              be also skipped because of the secondary sorting the
2633              range finishes (see function
2634              object_range_compare_func).  */
2635           while (first_not_finished < i
2636                  && start > OBJECT_MAX (ira_object_id_map
2637                                         [first_not_finished]))
2638             first_not_finished++;
2639           min = first_not_finished;
2640         }
2641       if (min == i)
2642         /* We could increase min further in this case but it is good
2643            enough.  */
2644         min++;
2645       live_range_min[i] = OBJECT_MIN (obj);
2646       OBJECT_MIN (obj) = min;
2647     }
2648   last_lived = (int *) ira_allocate (sizeof (int) * ira_max_point);
2649   aclass = -1;
2650   filled_area_start = -1;
2651   for (i = ira_objects_num - 1; i >= 0; i--)
2652     {
2653       ira_object_t obj = ira_object_id_map[i];
2654
2655       if (obj == NULL)
2656         continue;
2657
2658       a = OBJECT_ALLOCNO (obj);
2659       if (aclass < 0)
2660         {
2661           aclass = ALLOCNO_CLASS (a);
2662           for (j = 0; j < ira_max_point; j++)
2663             last_lived[j] = -1;
2664           filled_area_start = ira_max_point;
2665         }
2666       min = live_range_min[i];
2667       finish = OBJECT_MAX (obj);
2668       max = last_lived[finish];
2669       if (max < 0)
2670         /* We could decrease max further in this case but it is good
2671            enough.  */
2672         max = OBJECT_CONFLICT_ID (obj) - 1;
2673       OBJECT_MAX (obj) = max;
2674       /* In filling, we can go further A range finish to recognize
2675          intersection quickly because if the finish of subsequently
2676          processed allocno (it has smaller conflict id) range is
2677          further A range finish than they are definitely intersected
2678          (the reason for this is the allocnos with bigger conflict id
2679          have their range starts not smaller than allocnos with
2680          smaller ids.  */
2681       for (j = min; j < filled_area_start; j++)
2682         last_lived[j] = i;
2683       filled_area_start = min;
2684     }
2685   ira_free (last_lived);
2686   ira_free (live_range_min);
2687
2688   /* For allocnos with more than one object, we may later record extra conflicts in
2689      subobject 0 that we cannot really know about here.
2690      For now, simply widen the min/max range of these subobjects.  */
2691
2692   word0_min = INT_MAX;
2693   word0_max = INT_MIN;
2694
2695   FOR_EACH_ALLOCNO (a, ai)
2696     {
2697       int n = ALLOCNO_NUM_OBJECTS (a);
2698       ira_object_t obj0;
2699
2700       if (n < 2)
2701         continue;
2702       obj0 = ALLOCNO_OBJECT (a, 0);
2703       if (OBJECT_CONFLICT_ID (obj0) < word0_min)
2704         word0_min = OBJECT_CONFLICT_ID (obj0);
2705       if (OBJECT_CONFLICT_ID (obj0) > word0_max)
2706         word0_max = OBJECT_CONFLICT_ID (obj0);
2707     }
2708   FOR_EACH_ALLOCNO (a, ai)
2709     {
2710       int n = ALLOCNO_NUM_OBJECTS (a);
2711       ira_object_t obj0;
2712
2713       if (n < 2)
2714         continue;
2715       obj0 = ALLOCNO_OBJECT (a, 0);
2716       if (OBJECT_MIN (obj0) > word0_min)
2717         OBJECT_MIN (obj0) = word0_min;
2718       if (OBJECT_MAX (obj0) < word0_max)
2719         OBJECT_MAX (obj0) = word0_max;
2720     }
2721 }
2722
2723 \f
2724
2725 static void
2726 create_caps (void)
2727 {
2728   ira_allocno_t a;
2729   ira_allocno_iterator ai;
2730   ira_loop_tree_node_t loop_tree_node;
2731
2732   FOR_EACH_ALLOCNO (a, ai)
2733     {
2734       if (ALLOCNO_LOOP_TREE_NODE (a) == ira_loop_tree_root)
2735         continue;
2736       if (ALLOCNO_CAP_MEMBER (a) != NULL)
2737         create_cap_allocno (a);
2738       else if (ALLOCNO_CAP (a) == NULL)
2739         {
2740           loop_tree_node = ALLOCNO_LOOP_TREE_NODE (a);
2741           if (!bitmap_bit_p (loop_tree_node->border_allocnos, ALLOCNO_NUM (a)))
2742             create_cap_allocno (a);
2743         }
2744     }
2745 }
2746
2747 \f
2748
2749 /* The page contains code transforming more one region internal
2750    representation (IR) to one region IR which is necessary for reload.
2751    This transformation is called IR flattening.  We might just rebuild
2752    the IR for one region but we don't do it because it takes a lot of
2753    time.  */
2754
2755 /* Map: regno -> allocnos which will finally represent the regno for
2756    IR with one region.  */
2757 static ira_allocno_t *regno_top_level_allocno_map;
2758
2759 /* Find the allocno that corresponds to A at a level one higher up in the
2760    loop tree.  Returns NULL if A is a cap, or if it has no parent.  */
2761 ira_allocno_t
2762 ira_parent_allocno (ira_allocno_t a)
2763 {
2764   ira_loop_tree_node_t parent;
2765
2766   if (ALLOCNO_CAP (a) != NULL)
2767     return NULL;
2768
2769   parent = ALLOCNO_LOOP_TREE_NODE (a)->parent;
2770   if (parent == NULL)
2771     return NULL;
2772
2773   return parent->regno_allocno_map[ALLOCNO_REGNO (a)];
2774 }
2775
2776 /* Find the allocno that corresponds to A at a level one higher up in the
2777    loop tree.  If ALLOCNO_CAP is set for A, return that.  */
2778 ira_allocno_t
2779 ira_parent_or_cap_allocno (ira_allocno_t a)
2780 {
2781   if (ALLOCNO_CAP (a) != NULL)
2782     return ALLOCNO_CAP (a);
2783
2784   return ira_parent_allocno (a);
2785 }
2786
2787 /* Process all allocnos originated from pseudo REGNO and copy live
2788    ranges, hard reg conflicts, and allocno stack reg attributes from
2789    low level allocnos to final allocnos which are destinations of
2790    removed stores at a loop exit.  Return true if we copied live
2791    ranges.  */
2792 static bool
2793 copy_info_to_removed_store_destinations (int regno)
2794 {
2795   ira_allocno_t a;
2796   ira_allocno_t parent_a = NULL;
2797   ira_loop_tree_node_t parent;
2798   bool merged_p;
2799
2800   merged_p = false;
2801   for (a = ira_regno_allocno_map[regno];
2802        a != NULL;
2803        a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
2804     {
2805       if (a != regno_top_level_allocno_map[REGNO (allocno_emit_reg (a))])
2806         /* This allocno will be removed.  */
2807         continue;
2808
2809       /* Caps will be removed.  */
2810       ira_assert (ALLOCNO_CAP_MEMBER (a) == NULL);
2811       for (parent = ALLOCNO_LOOP_TREE_NODE (a)->parent;
2812            parent != NULL;
2813            parent = parent->parent)
2814         if ((parent_a = parent->regno_allocno_map[regno]) == NULL
2815             || (parent_a
2816                 == regno_top_level_allocno_map[REGNO
2817                                                (allocno_emit_reg (parent_a))]
2818                 && ALLOCNO_EMIT_DATA (parent_a)->mem_optimized_dest_p))
2819           break;
2820       if (parent == NULL || parent_a == NULL)
2821         continue;
2822
2823       copy_allocno_live_ranges (a, parent_a);
2824       merge_hard_reg_conflicts (a, parent_a, true);
2825
2826       ALLOCNO_CALL_FREQ (parent_a) += ALLOCNO_CALL_FREQ (a);
2827       ALLOCNO_CALLS_CROSSED_NUM (parent_a)
2828         += ALLOCNO_CALLS_CROSSED_NUM (a);
2829       ALLOCNO_CHEAP_CALLS_CROSSED_NUM (parent_a)
2830         += ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a);
2831       ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (parent_a)
2832         += ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a);
2833       merged_p = true;
2834     }
2835   return merged_p;
2836 }
2837
2838 /* Flatten the IR.  In other words, this function transforms IR as if
2839    it were built with one region (without loops).  We could make it
2840    much simpler by rebuilding IR with one region, but unfortunately it
2841    takes a lot of time.  MAX_REGNO_BEFORE_EMIT and
2842    IRA_MAX_POINT_BEFORE_EMIT are correspondingly MAX_REG_NUM () and
2843    IRA_MAX_POINT before emitting insns on the loop borders.  */
2844 void
2845 ira_flattening (int max_regno_before_emit, int ira_max_point_before_emit)
2846 {
2847   int i, j;
2848   bool keep_p;
2849   int hard_regs_num;
2850   bool new_pseudos_p, merged_p, mem_dest_p;
2851   unsigned int n;
2852   enum reg_class aclass;
2853   ira_allocno_t a, parent_a, first, second, node_first, node_second;
2854   ira_copy_t cp;
2855   ira_loop_tree_node_t node;
2856   live_range_t r;
2857   ira_allocno_iterator ai;
2858   ira_copy_iterator ci;
2859
2860   regno_top_level_allocno_map
2861     = (ira_allocno_t *) ira_allocate (max_reg_num ()
2862                                       * sizeof (ira_allocno_t));
2863   memset (regno_top_level_allocno_map, 0,
2864           max_reg_num () * sizeof (ira_allocno_t));
2865   new_pseudos_p = merged_p = false;
2866   FOR_EACH_ALLOCNO (a, ai)
2867     {
2868       ira_allocno_object_iterator oi;
2869       ira_object_t obj;
2870
2871       if (ALLOCNO_CAP_MEMBER (a) != NULL)
2872         /* Caps are not in the regno allocno maps and they are never
2873            will be transformed into allocnos existing after IR
2874            flattening.  */
2875         continue;
2876       FOR_EACH_ALLOCNO_OBJECT (a, obj, oi)
2877         COPY_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj),
2878                            OBJECT_CONFLICT_HARD_REGS (obj));
2879 #ifdef STACK_REGS
2880       ALLOCNO_TOTAL_NO_STACK_REG_P (a) = ALLOCNO_NO_STACK_REG_P (a);
2881 #endif
2882     }
2883   /* Fix final allocno attributes.  */
2884   for (i = max_regno_before_emit - 1; i >= FIRST_PSEUDO_REGISTER; i--)
2885     {
2886       mem_dest_p = false;
2887       for (a = ira_regno_allocno_map[i];
2888            a != NULL;
2889            a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
2890         {
2891           ira_emit_data_t parent_data, data = ALLOCNO_EMIT_DATA (a);
2892
2893           ira_assert (ALLOCNO_CAP_MEMBER (a) == NULL);
2894           if (data->somewhere_renamed_p)
2895             new_pseudos_p = true;
2896           parent_a = ira_parent_allocno (a);
2897           if (parent_a == NULL)
2898             {
2899               ALLOCNO_COPIES (a) = NULL;
2900               regno_top_level_allocno_map[REGNO (data->reg)] = a;
2901               continue;
2902             }
2903           ira_assert (ALLOCNO_CAP_MEMBER (parent_a) == NULL);
2904
2905           if (data->mem_optimized_dest != NULL)
2906             mem_dest_p = true;
2907           parent_data = ALLOCNO_EMIT_DATA (parent_a);
2908           if (REGNO (data->reg) == REGNO (parent_data->reg))
2909             {
2910               merge_hard_reg_conflicts (a, parent_a, true);
2911               move_allocno_live_ranges (a, parent_a);
2912               merged_p = true;
2913               parent_data->mem_optimized_dest_p
2914                 = (parent_data->mem_optimized_dest_p
2915                    || data->mem_optimized_dest_p);
2916               continue;
2917             }
2918           new_pseudos_p = true;
2919           for (;;)
2920             {
2921               ALLOCNO_NREFS (parent_a) -= ALLOCNO_NREFS (a);
2922               ALLOCNO_FREQ (parent_a) -= ALLOCNO_FREQ (a);
2923               ALLOCNO_CALL_FREQ (parent_a) -= ALLOCNO_CALL_FREQ (a);
2924               ALLOCNO_CALLS_CROSSED_NUM (parent_a)
2925                 -= ALLOCNO_CALLS_CROSSED_NUM (a);
2926               ALLOCNO_CHEAP_CALLS_CROSSED_NUM (parent_a)
2927                 -= ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a);
2928               ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (parent_a)
2929                 -= ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a);
2930               ira_assert (ALLOCNO_CALLS_CROSSED_NUM (parent_a) >= 0
2931                           && ALLOCNO_NREFS (parent_a) >= 0
2932                           && ALLOCNO_FREQ (parent_a) >= 0);
2933               aclass = ALLOCNO_CLASS (parent_a);
2934               hard_regs_num = ira_class_hard_regs_num[aclass];
2935               if (ALLOCNO_HARD_REG_COSTS (a) != NULL
2936                   && ALLOCNO_HARD_REG_COSTS (parent_a) != NULL)
2937                 for (j = 0; j < hard_regs_num; j++)
2938                   ALLOCNO_HARD_REG_COSTS (parent_a)[j]
2939                     -= ALLOCNO_HARD_REG_COSTS (a)[j];
2940               if (ALLOCNO_CONFLICT_HARD_REG_COSTS (a) != NULL
2941                   && ALLOCNO_CONFLICT_HARD_REG_COSTS (parent_a) != NULL)
2942                 for (j = 0; j < hard_regs_num; j++)
2943                   ALLOCNO_CONFLICT_HARD_REG_COSTS (parent_a)[j]
2944                     -= ALLOCNO_CONFLICT_HARD_REG_COSTS (a)[j];
2945               ALLOCNO_CLASS_COST (parent_a)
2946                 -= ALLOCNO_CLASS_COST (a);
2947               ALLOCNO_MEMORY_COST (parent_a) -= ALLOCNO_MEMORY_COST (a);
2948               parent_a = ira_parent_allocno (parent_a);
2949               if (parent_a == NULL)
2950                 break;
2951             }
2952           ALLOCNO_COPIES (a) = NULL;
2953           regno_top_level_allocno_map[REGNO (data->reg)] = a;
2954         }
2955       if (mem_dest_p && copy_info_to_removed_store_destinations (i))
2956         merged_p = true;
2957     }
2958   ira_assert (new_pseudos_p || ira_max_point_before_emit == ira_max_point);
2959   if (merged_p || ira_max_point_before_emit != ira_max_point)
2960     ira_rebuild_start_finish_chains ();
2961   if (new_pseudos_p)
2962     {
2963       sparseset objects_live;
2964
2965       /* Rebuild conflicts.  */
2966       FOR_EACH_ALLOCNO (a, ai)
2967         {
2968           ira_allocno_object_iterator oi;
2969           ira_object_t obj;
2970
2971           if (a != regno_top_level_allocno_map[REGNO (allocno_emit_reg (a))]
2972               || ALLOCNO_CAP_MEMBER (a) != NULL)
2973             continue;
2974           FOR_EACH_ALLOCNO_OBJECT (a, obj, oi)
2975             {
2976               for (r = OBJECT_LIVE_RANGES (obj); r != NULL; r = r->next)
2977                 ira_assert (r->object == obj);
2978               clear_conflicts (obj);
2979             }
2980         }
2981       objects_live = sparseset_alloc (ira_objects_num);
2982       for (i = 0; i < ira_max_point; i++)
2983         {
2984           for (r = ira_start_point_ranges[i]; r != NULL; r = r->start_next)
2985             {
2986               ira_object_t obj = r->object;
2987
2988               a = OBJECT_ALLOCNO (obj);
2989               if (a != regno_top_level_allocno_map[REGNO (allocno_emit_reg (a))]
2990                   || ALLOCNO_CAP_MEMBER (a) != NULL)
2991                 continue;
2992
2993               aclass = ALLOCNO_CLASS (a);
2994               sparseset_set_bit (objects_live, OBJECT_CONFLICT_ID (obj));
2995               EXECUTE_IF_SET_IN_SPARSESET (objects_live, n)
2996                 {
2997                   ira_object_t live_obj = ira_object_id_map[n];
2998                   ira_allocno_t live_a = OBJECT_ALLOCNO (live_obj);
2999                   enum reg_class live_aclass = ALLOCNO_CLASS (live_a);
3000
3001                   if (ira_reg_classes_intersect_p[aclass][live_aclass]
3002                       /* Don't set up conflict for the allocno with itself.  */
3003                       && live_a != a)
3004                     ira_add_conflict (obj, live_obj);
3005                 }
3006             }
3007
3008           for (r = ira_finish_point_ranges[i]; r != NULL; r = r->finish_next)
3009             sparseset_clear_bit (objects_live, OBJECT_CONFLICT_ID (r->object));
3010         }
3011       sparseset_free (objects_live);
3012       compress_conflict_vecs ();
3013     }
3014   /* Mark some copies for removing and change allocnos in the rest
3015      copies.  */
3016   FOR_EACH_COPY (cp, ci)
3017     {
3018       if (ALLOCNO_CAP_MEMBER (cp->first) != NULL
3019           || ALLOCNO_CAP_MEMBER (cp->second) != NULL)
3020         {
3021           if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL)
3022             fprintf
3023               (ira_dump_file, "      Remove cp%d:%c%dr%d-%c%dr%d\n",
3024                cp->num, ALLOCNO_CAP_MEMBER (cp->first) != NULL ? 'c' : 'a',
3025                ALLOCNO_NUM (cp->first),
3026                REGNO (allocno_emit_reg (cp->first)),
3027                ALLOCNO_CAP_MEMBER (cp->second) != NULL ? 'c' : 'a',
3028                ALLOCNO_NUM (cp->second),
3029                REGNO (allocno_emit_reg (cp->second)));
3030           cp->loop_tree_node = NULL;
3031           continue;
3032         }
3033       first
3034         = regno_top_level_allocno_map[REGNO (allocno_emit_reg (cp->first))];
3035       second
3036         = regno_top_level_allocno_map[REGNO (allocno_emit_reg (cp->second))];
3037       node = cp->loop_tree_node;
3038       if (node == NULL)
3039         keep_p = true; /* It copy generated in ira-emit.c.  */
3040       else
3041         {
3042           /* Check that the copy was not propagated from level on
3043              which we will have different pseudos.  */
3044           node_first = node->regno_allocno_map[ALLOCNO_REGNO (cp->first)];
3045           node_second = node->regno_allocno_map[ALLOCNO_REGNO (cp->second)];
3046           keep_p = ((REGNO (allocno_emit_reg (first))
3047                      == REGNO (allocno_emit_reg (node_first)))
3048                      && (REGNO (allocno_emit_reg (second))
3049                          == REGNO (allocno_emit_reg (node_second))));
3050         }
3051       if (keep_p)
3052         {
3053           cp->loop_tree_node = ira_loop_tree_root;
3054           cp->first = first;
3055           cp->second = second;
3056         }
3057       else
3058         {
3059           cp->loop_tree_node = NULL;
3060           if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL)
3061             fprintf (ira_dump_file, "      Remove cp%d:a%dr%d-a%dr%d\n",
3062                      cp->num, ALLOCNO_NUM (cp->first),
3063                      REGNO (allocno_emit_reg (cp->first)),
3064                      ALLOCNO_NUM (cp->second),
3065                      REGNO (allocno_emit_reg (cp->second)));
3066         }
3067     }
3068   /* Remove unnecessary allocnos on lower levels of the loop tree.  */
3069   FOR_EACH_ALLOCNO (a, ai)
3070     {
3071       if (a != regno_top_level_allocno_map[REGNO (allocno_emit_reg (a))]
3072           || ALLOCNO_CAP_MEMBER (a) != NULL)
3073         {
3074           if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL)
3075             fprintf (ira_dump_file, "      Remove a%dr%d\n",
3076                      ALLOCNO_NUM (a), REGNO (allocno_emit_reg (a)));
3077           finish_allocno (a);
3078           continue;
3079         }
3080       ALLOCNO_LOOP_TREE_NODE (a) = ira_loop_tree_root;
3081       ALLOCNO_REGNO (a) = REGNO (allocno_emit_reg (a));
3082       ALLOCNO_CAP (a) = NULL;
3083       /* Restore updated costs for assignments from reload.  */
3084       ALLOCNO_UPDATED_MEMORY_COST (a) = ALLOCNO_MEMORY_COST (a);
3085       ALLOCNO_UPDATED_CLASS_COST (a) = ALLOCNO_CLASS_COST (a);
3086       if (! ALLOCNO_ASSIGNED_P (a))
3087         ira_free_allocno_updated_costs (a);
3088       ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL);
3089       ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) == NULL);
3090     }
3091   /* Remove unnecessary copies.  */
3092   FOR_EACH_COPY (cp, ci)
3093     {
3094       if (cp->loop_tree_node == NULL)
3095         {
3096           ira_copies[cp->num] = NULL;
3097           finish_copy (cp);
3098           continue;
3099         }
3100       ira_assert
3101         (ALLOCNO_LOOP_TREE_NODE (cp->first) == ira_loop_tree_root
3102          && ALLOCNO_LOOP_TREE_NODE (cp->second) == ira_loop_tree_root);
3103       ira_add_allocno_copy_to_list (cp);
3104       ira_swap_allocno_copy_ends_if_necessary (cp);
3105     }
3106   rebuild_regno_allocno_maps ();
3107   if (ira_max_point != ira_max_point_before_emit)
3108     ira_compress_allocno_live_ranges ();
3109   ira_free (regno_top_level_allocno_map);
3110 }
3111
3112 \f
3113
3114 #ifdef ENABLE_IRA_CHECKING
3115 /* Check creation of all allocnos.  Allocnos on lower levels should
3116    have allocnos or caps on all upper levels.  */
3117 static void
3118 check_allocno_creation (void)
3119 {
3120   ira_allocno_t a;
3121   ira_allocno_iterator ai;
3122   ira_loop_tree_node_t loop_tree_node;
3123
3124   FOR_EACH_ALLOCNO (a, ai)
3125     {
3126       loop_tree_node = ALLOCNO_LOOP_TREE_NODE (a);
3127       ira_assert (bitmap_bit_p (loop_tree_node->all_allocnos,
3128                                 ALLOCNO_NUM (a)));
3129       if (loop_tree_node == ira_loop_tree_root)
3130         continue;
3131       if (ALLOCNO_CAP_MEMBER (a) != NULL)
3132         ira_assert (ALLOCNO_CAP (a) != NULL);
3133       else if (ALLOCNO_CAP (a) == NULL)
3134         ira_assert (loop_tree_node->parent
3135                     ->regno_allocno_map[ALLOCNO_REGNO (a)] != NULL
3136                     && bitmap_bit_p (loop_tree_node->border_allocnos,
3137                                      ALLOCNO_NUM (a)));
3138     }
3139 }
3140 #endif
3141
3142 /* Identify allocnos which prefer a register class with a single hard register.
3143    Adjust ALLOCNO_CONFLICT_HARD_REG_COSTS so that conflicting allocnos are
3144    less likely to use the preferred singleton register.  */
3145 static void
3146 update_conflict_hard_reg_costs (void)
3147 {
3148   ira_allocno_t a;
3149   ira_allocno_iterator ai;
3150   int i, index, min;
3151
3152   FOR_EACH_ALLOCNO (a, ai)
3153     {
3154       reg_class_t aclass = ALLOCNO_CLASS (a);
3155       reg_class_t pref = reg_preferred_class (ALLOCNO_REGNO (a));
3156       int singleton = ira_class_singleton[pref][ALLOCNO_MODE (a)];
3157       if (singleton < 0)
3158         continue;
3159       index = ira_class_hard_reg_index[(int) aclass][singleton];
3160       if (index < 0)
3161         continue;
3162       if (ALLOCNO_CONFLICT_HARD_REG_COSTS (a) == NULL
3163           || ALLOCNO_HARD_REG_COSTS (a) == NULL)
3164         continue;
3165       min = INT_MAX;
3166       for (i = ira_class_hard_regs_num[(int) aclass] - 1; i >= 0; i--)
3167         if (ALLOCNO_HARD_REG_COSTS (a)[i] > ALLOCNO_CLASS_COST (a)
3168             && min > ALLOCNO_HARD_REG_COSTS (a)[i])
3169           min = ALLOCNO_HARD_REG_COSTS (a)[i];
3170       if (min == INT_MAX)
3171         continue;
3172       ira_allocate_and_set_costs (&ALLOCNO_CONFLICT_HARD_REG_COSTS (a),
3173                                   aclass, 0);
3174       ALLOCNO_CONFLICT_HARD_REG_COSTS (a)[index]
3175         -= min - ALLOCNO_CLASS_COST (a);
3176     }
3177 }
3178
3179 /* Create a internal representation (IR) for IRA (allocnos, copies,
3180    loop tree nodes).  The function returns TRUE if we generate loop
3181    structure (besides nodes representing all function and the basic
3182    blocks) for regional allocation.  A true return means that we
3183    really need to flatten IR before the reload.  */
3184 bool
3185 ira_build (void)
3186 {
3187   bool loops_p;
3188
3189   df_analyze ();
3190   initiate_cost_vectors ();
3191   initiate_allocnos ();
3192   initiate_copies ();
3193   create_loop_tree_nodes ();
3194   form_loop_tree ();
3195   create_allocnos ();
3196   ira_costs ();
3197   create_allocno_objects ();
3198   ira_create_allocno_live_ranges ();
3199   remove_unnecessary_regions (false);
3200   ira_compress_allocno_live_ranges ();
3201   update_bad_spill_attribute ();
3202   loops_p = more_one_region_p ();
3203   if (loops_p)
3204     {
3205       propagate_allocno_info ();
3206       create_caps ();
3207     }
3208   ira_tune_allocno_costs ();
3209 #ifdef ENABLE_IRA_CHECKING
3210   check_allocno_creation ();
3211 #endif
3212   setup_min_max_allocno_live_range_point ();
3213   sort_conflict_id_map ();
3214   setup_min_max_conflict_allocno_ids ();
3215   ira_build_conflicts ();
3216   update_conflict_hard_reg_costs ();
3217   if (! ira_conflicts_p)
3218     {
3219       ira_allocno_t a;
3220       ira_allocno_iterator ai;
3221
3222       /* Remove all regions but root one.  */
3223       if (loops_p)
3224         {
3225           remove_unnecessary_regions (true);
3226           loops_p = false;
3227         }
3228       /* We don't save hard registers around calls for fast allocation
3229          -- add caller clobbered registers as conflicting ones to
3230          allocno crossing calls.  */
3231       FOR_EACH_ALLOCNO (a, ai)
3232         if (ALLOCNO_CALLS_CROSSED_NUM (a) != 0)
3233           ior_hard_reg_conflicts (a, &call_used_reg_set);
3234     }
3235   if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
3236     print_copies (ira_dump_file);
3237   if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
3238     {
3239       int n, nr, nr_big;
3240       ira_allocno_t a;
3241       live_range_t r;
3242       ira_allocno_iterator ai;
3243
3244       n = 0;
3245       nr = 0;
3246       nr_big = 0;
3247       FOR_EACH_ALLOCNO (a, ai)
3248         {
3249           int j, nobj = ALLOCNO_NUM_OBJECTS (a);
3250
3251           if (nobj > 1)
3252             nr_big++;
3253           for (j = 0; j < nobj; j++)
3254             {
3255               ira_object_t obj = ALLOCNO_OBJECT (a, j);
3256               n += OBJECT_NUM_CONFLICTS (obj);
3257               for (r = OBJECT_LIVE_RANGES (obj); r != NULL; r = r->next)
3258                 nr++;
3259             }
3260         }
3261       fprintf (ira_dump_file, "  regions=%d, blocks=%d, points=%d\n",
3262                current_loops == NULL ? 1 : number_of_loops (),
3263                n_basic_blocks, ira_max_point);
3264       fprintf (ira_dump_file,
3265                "    allocnos=%d (big %d), copies=%d, conflicts=%d, ranges=%d\n",
3266                ira_allocnos_num, nr_big, ira_copies_num, n, nr);
3267     }
3268   return loops_p;
3269 }
3270
3271 /* Release the data created by function ira_build.  */
3272 void
3273 ira_destroy (void)
3274 {
3275   finish_loop_tree_nodes ();
3276   finish_copies ();
3277   finish_allocnos ();
3278   finish_cost_vectors ();
3279   ira_finish_allocno_live_ranges ();
3280 }