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