gcc/ira-build.c

   1 /* Building allocnos for IRA.
   2    Copyright (C) 2006, 2007
   3    Free Software Foundation, Inc.
   4    Contributed by Vladimir Makarov <vmakarov@redhat.com>.
   5
   6 This file is part of GCC.
   7
   8 GCC is free software; you can redistribute it and/or modify it under
   9 the terms of the GNU General Public License as published by the Free
  10 Software Foundation; either version 2, or (at your option) any later
  11 version.
  12
  13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  15 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  16 for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with GCC; see the file COPYING.  If not, write to the Free
  20 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
  21 02110-1301, USA.  */
  22
  23 #include "config.h"
  24 #include "system.h"
  25 #include "coretypes.h"
  26 #include "tm.h"
  27 #include "rtl.h"
  28 #include "tm_p.h"
  29 #include "target.h"
  30 #include "regs.h"
  31 #include "flags.h"
  32 #include "hard-reg-set.h"
  33 #include "basic-block.h"
  34 #include "insn-config.h"
  35 #include "recog.h"
  36 #include "toplev.h"
  37 #include "params.h"
  38 #include "df.h"
  39 #include "output.h"
  40 #include "reload.h"
  41 #include "ira-int.h"
  42
  43 static void create_loop_tree_nodes (int);
  44 static void finish_loop_tree_nodes (void);
  45 static void add_loop_to_tree (struct loop *);
  46 static int setup_loop_tree_level (loop_tree_node_t, int);
  47 static void form_loop_tree (void);
  48
  49 static void rebuild_regno_allocno_maps (void);
  50
  51 static void initiate_calls (void);
  52 static void expand_calls (void);
  53 static void compress_calls (void);
  54 static void finish_calls (void);
  55
  56 static void initiate_allocnos (void);
  57 static void check_allocno_conflict_vec (allocno_t, int);
  58 static void add_to_allocno_conflict_vec (allocno_t, allocno_t);
  59 static allocno_t create_cap_allocno (allocno_t);
  60 static void propagate_info_to_cap (allocno_t);
  61 static allocno_live_range_t copy_allocno_live_range (allocno_live_range_t);
  62 static allocno_live_range_t
  63   copy_allocno_live_range_list (allocno_live_range_t);
  64
  65 static void finish_allocno (allocno_t);
  66 static void finish_allocnos (void);
  67
  68 static void initiate_copies (void);
  69 static void finish_copy (copy_t);
  70 static void finish_copies (void);
  71
  72 static void create_insn_allocnos (rtx, int);
  73 static void create_bb_allocnos (loop_tree_node_t);
  74 static void create_loop_allocnos (edge);
  75 static void create_loop_tree_node_allocnos (loop_tree_node_t);
  76 static void create_allocnos (void);
  77
  78 static void create_loop_tree_node_caps (loop_tree_node_t);
  79 static void propagate_info_to_loop_tree_node_caps (loop_tree_node_t);
  80 static allocno_live_range_t merge_ranges (allocno_live_range_t,
  81                                           allocno_live_range_t);
  82 static loop_tree_node_t common_loop_tree_node_dominator (loop_tree_node_t,
  83                                                          loop_tree_node_t);
  84 static void check_and_add_conflicts (allocno_t, allocno_t *);
  85 static void add_conflict_with_underlying_allocnos (allocno_t,
  86                                                    loop_tree_node_t, int);
  87
  88 /* All natural loops.  */
  89 struct loops ira_loops;
  90
  91 /* The root of the loop tree corresponding to the all function.  */
  92 loop_tree_node_t ira_loop_tree_root;
  93
  94 /* Height of the loop tree.  */
  95 int ira_loop_tree_height;
  96
  97 /* All basic block data are referred through the following array.  We
  98    can not use member `aux' for this because it is used for insertion
  99    of insns on edges.  */
 100 loop_tree_node_t ira_bb_nodes;
 101
 102 /* All loop data are referred through the following array.  */
 103 loop_tree_node_t ira_loop_nodes;
 104
 105 /* Map regno -> allocnos.  */
 106 allocno_t *regno_allocno_map;
 107
 108 /* Array of references to all allocnos and their size.  The order
 109    number of the allocno corresponds to the index in the array.  */
 110 allocno_t *allocnos;
 111 int allocnos_num;
 112
 113 /* Array of references to copies and its size.  The order number of
 114    the copy corresponds to the index in the array.  */
 115 copy_t *copies;
 116 int copies_num;
 117
 118 \f
 119
 120 /* LAST_BASIC_BLOCK before generating additional insns because of live
 121    range splitting.  Emitting insns on a critical edge creates a new
 122    basic block.  */
 123 static int last_basic_block_before_change;
 124
 125 /* The following function creates the loop tree nodes.  If LOOPS_P is
 126    zero, the nodes corresponding to the loops (except the root which
 127    corresponds the all function) will be not created (it will be done
 128    only for basic blocks).  */
 129 static void
 130 create_loop_tree_nodes (int loops_p)
 131 {
 132   unsigned int i, j;
 133   int max_regno, skip_p;
 134   edge_iterator ei;
 135   edge e;
 136   VEC (edge, heap) *edges;
 137   loop_p loop;
 138
 139   ira_bb_nodes
 140     = ira_allocate (sizeof (struct loop_tree_node) * last_basic_block);
 141   last_basic_block_before_change = last_basic_block;
 142   for (i = 0; i < (unsigned int) last_basic_block; i++)
 143     {
 144       ira_bb_nodes [i].regno_allocno_map = NULL;
 145       memset (ira_bb_nodes [i].reg_pressure, 0,
 146               sizeof (ira_bb_nodes [i].reg_pressure));
 147       ira_bb_nodes [i].mentioned_allocnos = NULL;
 148       ira_bb_nodes [i].modified_regnos = NULL;
 149       ira_bb_nodes [i].border_allocnos = NULL;
 150       ira_bb_nodes [i].local_copies = NULL;
 151     }
 152   ira_loop_nodes = ira_allocate (sizeof (struct loop_tree_node)
 153                                  * VEC_length (loop_p, ira_loops.larray));
 154   max_regno = max_reg_num ();
 155   for (i = 0; VEC_iterate (loop_p, ira_loops.larray, i, loop); i++)
 156     {
 157       if (loop != ira_loops.tree_root)
 158         {
 159           ira_loop_nodes [i].regno_allocno_map = NULL;
 160           if (! loops_p)
 161             continue;
 162           skip_p = FALSE;
 163           FOR_EACH_EDGE (e, ei, loop->header->preds)
 164             if (e->src != loop->latch
 165                 && (e->flags & EDGE_ABNORMAL) && EDGE_CRITICAL_P (e))
 166               {
 167                 skip_p = TRUE;
 168                 break;
 169               }
 170           if (skip_p)
 171             continue;
 172           edges = get_loop_exit_edges (loop);
 173           for (j = 0; VEC_iterate (edge, edges, j, e); j++)
 174             if ((e->flags & EDGE_ABNORMAL) && EDGE_CRITICAL_P (e))
 175               {
 176                 skip_p = TRUE;
 177                 break;
 178               }
 179           VEC_free (edge, heap, edges);
 180           if (skip_p)
 181             continue;
 182         }
 183       ira_loop_nodes [i].regno_allocno_map
 184         = ira_allocate (sizeof (allocno_t) * max_regno);
 185       memset (ira_loop_nodes [i].regno_allocno_map, 0,
 186               sizeof (allocno_t) * max_regno);
 187       memset (ira_loop_nodes [i].reg_pressure, 0,
 188               sizeof (ira_loop_nodes [i].reg_pressure));
 189       ira_loop_nodes [i].mentioned_allocnos = ira_allocate_bitmap ();
 190       ira_loop_nodes [i].modified_regnos = ira_allocate_bitmap ();
 191       ira_loop_nodes [i].border_allocnos = ira_allocate_bitmap ();
 192       ira_loop_nodes [i].local_copies = ira_allocate_bitmap ();
 193     }
 194 }
 195
 196 /* The function frees the loop tree nodes.  */
 197 static void
 198 finish_loop_tree_nodes (void)
 199 {
 200   unsigned int i;
 201   loop_p loop;
 202
 203   for (i = 0; VEC_iterate (loop_p, ira_loops.larray, i, loop); i++)
 204     if (ira_loop_nodes [i].regno_allocno_map != NULL)
 205       {
 206         ira_free_bitmap (ira_loop_nodes [i].local_copies);
 207         ira_free_bitmap (ira_loop_nodes [i].border_allocnos);
 208         ira_free_bitmap (ira_loop_nodes [i].modified_regnos);
 209         ira_free_bitmap (ira_loop_nodes [i].mentioned_allocnos);
 210         ira_free (ira_loop_nodes [i].regno_allocno_map);
 211       }
 212   ira_free (ira_loop_nodes);
 213   for (i = 0; i < (unsigned int) last_basic_block_before_change; i++)
 214     {
 215       if (ira_bb_nodes [i].local_copies != NULL)
 216         ira_free_bitmap (ira_bb_nodes [i].local_copies);
 217       if (ira_bb_nodes [i].border_allocnos != NULL)
 218         ira_free_bitmap (ira_bb_nodes [i].border_allocnos);
 219       if (ira_bb_nodes [i].modified_regnos != NULL)
 220         ira_free_bitmap (ira_bb_nodes [i].modified_regnos);
 221       if (ira_bb_nodes [i].mentioned_allocnos != NULL)
 222         ira_free_bitmap (ira_bb_nodes [i].mentioned_allocnos);
 223       if (ira_bb_nodes [i].regno_allocno_map != NULL)
 224         ira_free (ira_bb_nodes [i].regno_allocno_map);
 225     }
 226   ira_free (ira_bb_nodes);
 227 }
 228
 229 \f
 230
 231 /* The following recursive functions adds loop to the loop tree
 232    hierarchy.  The loop is added only once.  */
 233 static void
 234 add_loop_to_tree (struct loop *loop)
 235 {
 236   struct loop *father;
 237   loop_tree_node_t loop_node, father_node;
 238
 239   /* Can not use loop node access macros because of potential checking
 240      and because the nodes are not initialized yet.  */
 241   if (loop_outer (loop) != NULL)
 242     add_loop_to_tree (loop_outer (loop));
 243   if (ira_loop_nodes [loop->num].regno_allocno_map != NULL
 244       && ira_loop_nodes [loop->num].inner == NULL)
 245     {
 246       /* We have not added loop node to the tree yet.  */
 247       loop_node = &ira_loop_nodes [loop->num];
 248       loop_node->loop = loop;
 249       loop_node->bb = NULL;
 250       for (father = loop_outer (loop);
 251            father != NULL;
 252            father = loop_outer (father))
 253         if (ira_loop_nodes [father->num].regno_allocno_map != NULL)
 254           break;
 255       if (father == NULL)
 256         {
 257           loop_node->next = NULL;
 258           loop_node->father = NULL;
 259         }
 260       else
 261         {
 262           father_node = &ira_loop_nodes [father->num];
 263           loop_node->next = father_node->inner;
 264           father_node->inner = loop_node;
 265           loop_node->father = father_node;
 266         }
 267     }
 268 }
 269
 270 /* Enumerate loops in loop with root LOOP_NODE starting with LEVEL and
 271    return maximal value of level in the tree + 1.  */
 272 static int
 273 setup_loop_tree_level (loop_tree_node_t loop_node, int level)
 274 {
 275   int height, max_height;
 276   loop_tree_node_t subloop_node;
 277
 278   ira_assert (loop_node->bb == NULL);
 279   loop_node->level = level;
 280   max_height = level + 1;
 281   for (subloop_node = loop_node->inner;
 282        subloop_node != NULL;
 283        subloop_node = subloop_node->next)
 284     if (subloop_node->bb == NULL)
 285       {
 286         height = setup_loop_tree_level (subloop_node, level + 1);
 287         if (height > max_height)
 288           max_height = height;
 289       }
 290   return max_height;
 291 }
 292
 293 /* The following function creates the loop tree.  The algorithm is
 294    designed to provide correct order of loops (by the last loop BB)
 295    and basic blocks in chain formed by next.  */
 296 static void
 297 form_loop_tree (void)
 298 {
 299   unsigned int i;
 300   basic_block bb;
 301   struct loop *father;
 302   loop_tree_node_t bb_node, loop_node;
 303   loop_p loop;
 304
 305   /* Can not use loop/bb node access macros because of potential
 306      checking and the nodes are not initialized yet.  */
 307   for (i = 0; VEC_iterate (loop_p, ira_loops.larray, i, loop); i++)
 308      if (ira_loop_nodes [i].regno_allocno_map != NULL)
 309        ira_loop_nodes [i].inner = NULL;
 310   FOR_EACH_BB_REVERSE (bb)
 311     {
 312       bb_node = &ira_bb_nodes [bb->index];
 313       bb_node->bb = bb;
 314       bb_node->loop = NULL;
 315       bb_node->inner = NULL;
 316       bb_node->next = NULL;
 317       for (father = bb->loop_father;
 318            father != NULL;
 319            father = loop_outer (father))
 320         if (ira_loop_nodes [father->num].regno_allocno_map != NULL)
 321           break;
 322       add_loop_to_tree (father);
 323       loop_node = &ira_loop_nodes [father->num];
 324       bb_node->next = loop_node->inner;
 325       bb_node->father = loop_node;
 326       loop_node->inner = bb_node;
 327     }
 328   ira_loop_tree_root = IRA_LOOP_NODE_BY_INDEX (ira_loops.tree_root->num);
 329   ira_loop_tree_height = setup_loop_tree_level (ira_loop_tree_root, 0);
 330   ira_assert (ira_loop_tree_root->regno_allocno_map != NULL);
 331 }
 332
 333 \f
 334
 335 /* The function rebuilds REGNO_ALLOCNO_MAP and REGNO_ALLOCNO_MAPs of
 336    the loops using only allocno info.  */
 337 static void
 338 rebuild_regno_allocno_maps (void)
 339 {
 340   unsigned int l;
 341   int i, max_regno, regno;
 342   allocno_t a;
 343   loop_tree_node_t loop_tree_node;
 344   loop_p loop;
 345
 346   max_regno = max_reg_num ();
 347   for (l = 0; VEC_iterate (loop_p, ira_loops.larray, l, loop); l++)
 348     if (ira_loop_nodes [l].regno_allocno_map != NULL)
 349       {
 350         ira_free (ira_loop_nodes [l].regno_allocno_map);
 351         ira_loop_nodes [l].regno_allocno_map
 352           = ira_allocate (sizeof (allocno_t) * max_regno);
 353         memset (ira_loop_nodes [l].regno_allocno_map, 0,
 354                 sizeof (allocno_t) * max_regno);
 355       }
 356   ira_free (regno_allocno_map);
 357   regno_allocno_map = ira_allocate (max_regno * sizeof (allocno_t));
 358   memset (regno_allocno_map, 0, max_regno * sizeof (allocno_t));
 359   for (i = 0; i < allocnos_num; i++)
 360     {
 361       a = allocnos [i];
 362       if (ALLOCNO_CAP_MEMBER (a) != NULL)
 363         continue;
 364       regno = ALLOCNO_REGNO (a);
 365       loop_tree_node = ALLOCNO_LOOP_TREE_NODE (a);
 366       ALLOCNO_NEXT_REGNO_ALLOCNO (a) = regno_allocno_map [regno];
 367       regno_allocno_map [regno] = a;
 368       if (loop_tree_node->regno_allocno_map [regno] == NULL)
 369         /* Remember that we can create temporary allocnos to break
 370            cycles in register shuffle.  */
 371         loop_tree_node->regno_allocno_map [regno] = a;
 372     }
 373 }
 374
 375 \f
 376
 377 /* Array of vectors containing calls intersected by pseudo-registers.  */
 378 VEC(rtx, heap) **regno_calls;
 379
 380 /* The length of the previous array.  */
 381 static int regno_calls_num;
 382
 383 /* The function initializes array of vectors containing calls
 384    intersected by pseudo-registers.  */
 385 static void
 386 initiate_calls (void)
 387 {
 388   regno_calls_num = max_reg_num () * 3 / 2;
 389   regno_calls = ira_allocate (regno_calls_num * sizeof (VEC(rtx, heap) *));
 390   memset (regno_calls, 0, regno_calls_num * sizeof (VEC(rtx, heap) *));
 391 }
 392
 393 /* The function expands array of vectors containing calls for all
 394    pseudo-registers.  */
 395 static void
 396 expand_calls (void)
 397 {
 398   int max_regno = max_reg_num ();
 399
 400   if (max_regno > regno_calls_num)
 401     {
 402       regno_calls = ira_reallocate (regno_calls,
 403                                     max_regno * sizeof (VEC(rtx, heap) *));
 404       memset (regno_calls + regno_calls_num, 0,
 405               (max_regno - regno_calls_num) * sizeof (VEC(rtx, heap) *));
 406       regno_calls_num = max_regno;
 407     }
 408 }
 409
 410 /* The function removes NULL elements from vectors containing calls
 411    intersected by pseudo-registers.  */
 412 static void
 413 compress_calls (void)
 414 {
 415   int regno, curr, length, last;
 416   rtx *allocno_calls;
 417
 418   for (regno = 0; regno < regno_calls_num; regno++)
 419     {
 420       allocno_calls = VEC_address (rtx, regno_calls [regno]);
 421       length = VEC_length (rtx, regno_calls [regno]);
 422       for (last = curr = 0; curr < length; curr++)
 423         if (allocno_calls [curr] != NULL_RTX)
 424           allocno_calls [last++] = allocno_calls [curr];
 425       VEC_truncate (rtx, regno_calls [regno], last);
 426     }
 427 }
 428
 429 /* The function adds CALL to REGNO's vector of intersected calls.  */
 430 int
 431 add_regno_call (int regno, rtx call)
 432 {
 433   int result;
 434
 435   gcc_assert (regno < regno_calls_num);
 436   if (regno_calls [regno] == NULL)
 437     regno_calls [regno] = VEC_alloc (rtx, heap, 10);
 438   result = VEC_length (rtx, regno_calls [regno]);
 439   VEC_safe_push (rtx, heap, regno_calls [regno], call);
 440   return result;
 441 }
 442
 443 /* The function frees array of vectors containing calls
 444    intersected by pseudo-registers.  */
 445 static void
 446 finish_calls (void)
 447 {
 448   int i;
 449
 450   for (i = 0; i < regno_calls_num; i++)
 451     VEC_free (rtx, heap, regno_calls [i]);
 452   ira_free (regno_calls);
 453 }
 454
 455 \f
 456
 457 /* Varray containing references to all created allocnos.  It is a
 458    container of array allocnos.  */
 459 static varray_type allocno_varray;
 460
 461 /* The function initializes data concerning allocnos.  */
 462 static void
 463 initiate_allocnos (void)
 464 {
 465   VARRAY_GENERIC_PTR_NOGC_INIT
 466     (allocno_varray, max_reg_num () * 2, "allocnos");
 467   allocnos = NULL;
 468   allocnos_num = 0;
 469   regno_allocno_map = ira_allocate (max_reg_num () * sizeof (allocno_t));
 470   memset (regno_allocno_map, 0, max_reg_num () * sizeof (allocno_t));
 471 }
 472
 473 /* The function creates and returns allocno corresponding to REGNO in
 474    LOOP_TREE_NODE.  Add the allocno to the list of allocnos with the
 475    same regno if ! CAP_P.  */
 476 allocno_t
 477 create_allocno (int regno, int cap_p, loop_tree_node_t loop_tree_node)
 478 {
 479   allocno_t a;
 480
 481   a = pool_alloc (allocno_pool);
 482   ALLOCNO_REGNO (a) = regno;
 483   ALLOCNO_LOOP_TREE_NODE (a) = loop_tree_node;
 484   if (! cap_p)
 485     {
 486       ALLOCNO_NEXT_REGNO_ALLOCNO (a) = regno_allocno_map [regno];
 487       regno_allocno_map [regno] = a;
 488       if (loop_tree_node->regno_allocno_map [regno] == NULL)
 489         /* Remember that we can create temporary allocnos to break
 490            cycles in register shuffle.  */
 491         loop_tree_node->regno_allocno_map [regno] = a;
 492     }
 493   ALLOCNO_CAP (a) = NULL;
 494   ALLOCNO_CAP_MEMBER (a) = NULL;
 495   ALLOCNO_NUM (a) = allocnos_num;
 496   ALLOCNO_CONFLICT_ALLOCNO_VEC (a) = NULL;
 497   ALLOCNO_CONFLICT_ALLOCNOS_NUM (a) = 0;
 498   ALLOCNO_TOTAL_CONFLICT_ALLOCNOS_NUM (a) = 0;
 499   CLEAR_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (a));
 500   CLEAR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a));
 501   ALLOCNO_NREFS (a) = 0;
 502   ALLOCNO_FREQ (a) = 1;
 503   ALLOCNO_HARD_REGNO (a) = -1;
 504   ALLOCNO_CALL_FREQ (a) = 0;
 505   ALLOCNO_CALLS_CROSSED_NUM (a) = 0;
 506   ALLOCNO_CALLS_CROSSED_START (a) = -1;
 507 #ifdef STACK_REGS
 508   ALLOCNO_NO_STACK_REG_P (a) = FALSE;
 509   ALLOCNO_TOTAL_NO_STACK_REG_P (a) = FALSE;
 510 #endif
 511   ALLOCNO_MEM_OPTIMIZED_DEST (a) = NULL;
 512   ALLOCNO_MEM_OPTIMIZED_DEST_P (a) = FALSE;
 513   ALLOCNO_IN_GRAPH_P (a) = FALSE;
 514   ALLOCNO_ASSIGNED_P (a) = FALSE;
 515   ALLOCNO_MAY_BE_SPILLED_P (a) = FALSE;
 516   ALLOCNO_MODE (a) = (regno < 0 ? VOIDmode : PSEUDO_REGNO_MODE (regno));
 517   ALLOCNO_COPIES (a) = NULL;
 518   ALLOCNO_HARD_REG_COSTS (a) = NULL;
 519   ALLOCNO_CONFLICT_HARD_REG_COSTS (a) = NULL;
 520   ALLOCNO_UPDATED_HARD_REG_COSTS (a) = NULL;
 521   ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) = NULL;
 522   ALLOCNO_LEFT_CONFLICTS_NUM (a) = -1;
 523   ALLOCNO_COVER_CLASS (a) = NO_REGS;
 524   ALLOCNO_BEST_CLASS (a) = NO_REGS;
 525   ALLOCNO_COVER_CLASS_COST (a) = 0;
 526   ALLOCNO_UPDATED_MEMORY_COST (a) = 0;
 527   ALLOCNO_NEXT_BUCKET_ALLOCNO (a) = NULL;
 528   ALLOCNO_PREV_BUCKET_ALLOCNO (a) = NULL;
 529   ALLOCNO_FIRST_COALESCED_ALLOCNO (a) = a;
 530   ALLOCNO_NEXT_COALESCED_ALLOCNO (a) = a;
 531   ALLOCNO_LIVE_RANGES (a) = NULL;
 532   VARRAY_PUSH_GENERIC_PTR (allocno_varray, a);
 533   allocnos = (allocno_t *) &VARRAY_GENERIC_PTR (allocno_varray, 0);
 534   allocnos_num = VARRAY_ACTIVE_SIZE (allocno_varray);
 535   return a;
 536 }
 537
 538 /* The function returns index of A2 in conflict vector of A1, or -1 if
 539    it is absent.  */
 540 int
 541 allocno_conflict_index (allocno_t a1, allocno_t a2)
 542 {
 543   int i;
 544   allocno_t conflict_allocno, *allocno_vec;
 545
 546   allocno_vec = ALLOCNO_CONFLICT_ALLOCNO_VEC (a1);
 547   for (i = 0; (conflict_allocno = allocno_vec [i]) != NULL; i++)
 548     if (conflict_allocno == a2)
 549       return i;
 550   return -1;
 551 }
 552
 553 /* The function allocates conflict vector of A for NUM allocnos.  */
 554 void
 555 allocate_allocno_conflicts (allocno_t a, int num)
 556 {
 557   ira_assert (ALLOCNO_CONFLICT_ALLOCNO_VEC (a) == NULL);
 558   ALLOCNO_CONFLICT_ALLOCNO_VEC (a)
 559     = ira_allocate (sizeof (allocno_t) * (num + 1));
 560   ALLOCNO_CONFLICT_ALLOCNO_VEC (a) [0] = NULL;
 561   ALLOCNO_CONFLICT_ALLOCNOS_NUM (a) = 0;
 562   ALLOCNO_TOTAL_CONFLICT_ALLOCNOS_NUM (a) = 0;
 563   ALLOCNO_CONFLICT_ALLOCNO_VEC_SIZE (a) = num;
 564 }
 565
 566 /* The function checks that conflict vector of A has enough space to
 567    contain NUM allocno references.  If the space is not enough, the
 568    function expands the conflict vector.  */
 569 static void
 570 check_allocno_conflict_vec (allocno_t a, int num)
 571 {
 572   int size;
 573   allocno_t *vec;
 574
 575   ira_assert (ALLOCNO_CONFLICT_ALLOCNO_VEC (a) != NULL);
 576   if (ALLOCNO_CONFLICT_ALLOCNO_VEC_SIZE (a) >= num)
 577     return;
 578   size = 3 * num / 2 + 1;
 579   vec = ira_allocate (sizeof (allocno_t) * (size + 1));
 580   memcpy (vec, ALLOCNO_CONFLICT_ALLOCNO_VEC (a),
 581           sizeof (allocno_t)
 582           * (ALLOCNO_TOTAL_CONFLICT_ALLOCNOS_NUM (a) + 1));
 583   ira_free (ALLOCNO_CONFLICT_ALLOCNO_VEC (a));
 584   ALLOCNO_CONFLICT_ALLOCNO_VEC (a) = vec;
 585   ALLOCNO_CONFLICT_ALLOCNO_VEC_SIZE (a) = size;
 586 }
 587
 588 /* The function adds A2 to conflict vector of A1.  */
 589 static void
 590 add_to_allocno_conflict_vec (allocno_t a1, allocno_t a2)
 591 {
 592   int size;
 593   allocno_t *vec;
 594
 595   size = ALLOCNO_TOTAL_CONFLICT_ALLOCNOS_NUM (a1);
 596   check_allocno_conflict_vec (a1, size + 1);
 597   vec = ALLOCNO_CONFLICT_ALLOCNO_VEC (a1);
 598   vec [size] = a2;
 599   vec [size + 1] = NULL;
 600   ALLOCNO_TOTAL_CONFLICT_ALLOCNOS_NUM (a1)++;
 601 }
 602
 603 /* The function adds A1 to conflict vector of A2 and vise versa.  */
 604 void
 605 add_allocno_conflict (allocno_t a1, allocno_t a2)
 606 {
 607   add_to_allocno_conflict_vec (a1, a2);
 608   add_to_allocno_conflict_vec (a2, a1);
 609 }
 610
 611 /* This recursive function outputs allocno A and if it is cap the
 612    function outputs members.  */
 613 void
 614 print_expanded_allocno (allocno_t a)
 615 {
 616   basic_block bb;
 617
 618   fprintf (ira_dump_file, " a%d(r%d", ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
 619   if ((bb = ALLOCNO_LOOP_TREE_NODE (a)->bb) != NULL)
 620     fprintf (ira_dump_file, ",b%d", bb->index);
 621   else
 622     fprintf (ira_dump_file, ",l%d", ALLOCNO_LOOP_TREE_NODE (a)->loop->num);
 623   if (ALLOCNO_CAP_MEMBER (a) != NULL)
 624     {
 625       fprintf (ira_dump_file, ":");
 626       print_expanded_allocno (ALLOCNO_CAP_MEMBER (a));
 627     }
 628   fprintf (ira_dump_file, ")");
 629 }
 630
 631 /* The function creates and returns cap representing allocno A in the
 632    father loop.  */
 633 static allocno_t
 634 create_cap_allocno (allocno_t a)
 635 {
 636   allocno_t cap;
 637   loop_tree_node_t father;
 638
 639   ira_assert (ALLOCNO_FIRST_COALESCED_ALLOCNO (a) == a
 640               && ALLOCNO_NEXT_COALESCED_ALLOCNO (a) == a);
 641   father = ALLOCNO_LOOP_TREE_NODE (a)->father;
 642   cap = create_allocno (ALLOCNO_REGNO (a), TRUE, father);
 643   /* We just need to set a mode giving the same size.  */
 644   ALLOCNO_MODE (cap) = ALLOCNO_MODE (a);
 645   ALLOCNO_COVER_CLASS (cap) = ALLOCNO_COVER_CLASS (a);
 646   ALLOCNO_BEST_CLASS (cap) = ALLOCNO_BEST_CLASS (a);
 647   ALLOCNO_AVAILABLE_REGS_NUM (cap) = ALLOCNO_AVAILABLE_REGS_NUM (a);
 648   ALLOCNO_CAP_MEMBER (cap) = a;
 649   bitmap_set_bit (father->mentioned_allocnos, ALLOCNO_NUM (cap));
 650   ALLOCNO_CAP (a) = cap;
 651   ALLOCNO_COVER_CLASS_COST (cap) = ALLOCNO_COVER_CLASS_COST (a);
 652   ALLOCNO_UPDATED_MEMORY_COST (cap) = ALLOCNO_UPDATED_MEMORY_COST (a);
 653   if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
 654     {
 655       fprintf (ira_dump_file, "    Creating cap ");
 656       print_expanded_allocno (cap);
 657       fprintf (ira_dump_file, "\n");
 658     }
 659   return cap;
 660 }
 661
 662 /* The function propagate info obtained during conflicts building to
 663    CAP.  */
 664 static void
 665 propagate_info_to_cap (allocno_t cap)
 666 {
 667   int i, regno, hard_regs_num, conflicts_num;
 668   int *reg_costs, *conflict_reg_costs;
 669   allocno_t a, conflict_allocno, conflict_father_allocno;
 670   allocno_t another_a, father_a;
 671   allocno_t *allocno_vec;
 672   loop_tree_node_t father;
 673   copy_t cp, next_cp;
 674
 675   ira_assert (ALLOCNO_FIRST_COALESCED_ALLOCNO (cap) == cap
 676               && ALLOCNO_NEXT_COALESCED_ALLOCNO (cap) == cap
 677               && ALLOCNO_CONFLICT_ALLOCNO_VEC (cap) == NULL
 678               && ALLOCNO_CALLS_CROSSED_NUM (cap) == 0);
 679   a = ALLOCNO_CAP_MEMBER (cap);
 680   father = ALLOCNO_LOOP_TREE_NODE (cap);
 681   hard_regs_num = class_hard_regs_num [ALLOCNO_COVER_CLASS (cap)];
 682   ALLOCNO_HARD_REG_COSTS (cap) = reg_costs
 683     = ira_allocate (hard_regs_num * sizeof (int));
 684   memcpy (reg_costs, ALLOCNO_HARD_REG_COSTS (a), hard_regs_num * sizeof (int));
 685   ALLOCNO_CONFLICT_HARD_REG_COSTS (cap) = conflict_reg_costs
 686     = ira_allocate (hard_regs_num * sizeof (int));
 687   memcpy (conflict_reg_costs, ALLOCNO_CONFLICT_HARD_REG_COSTS (a),
 688           hard_regs_num * sizeof (int));
 689   ALLOCNO_UPDATED_HARD_REG_COSTS (cap)
 690     = ira_allocate (hard_regs_num * sizeof (int));
 691   ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (cap)
 692     = ira_allocate (hard_regs_num * sizeof (int));
 693   ALLOCNO_NREFS (cap) = ALLOCNO_NREFS (a);
 694   ALLOCNO_FREQ (cap) = ALLOCNO_FREQ (a);
 695   ALLOCNO_CALL_FREQ (cap) = ALLOCNO_CALL_FREQ (a);
 696   IOR_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (cap),
 697                     ALLOCNO_CONFLICT_HARD_REGS (a));
 698   IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (cap),
 699                     ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a));
 700   ALLOCNO_CALLS_CROSSED_NUM (cap) = ALLOCNO_CALLS_CROSSED_NUM (a);
 701   ALLOCNO_CALLS_CROSSED_START (cap) = ALLOCNO_CALLS_CROSSED_START (a);
 702 #ifdef STACK_REGS
 703   ALLOCNO_NO_STACK_REG_P (cap) = ALLOCNO_NO_STACK_REG_P (a);
 704   ALLOCNO_TOTAL_NO_STACK_REG_P (cap) = ALLOCNO_TOTAL_NO_STACK_REG_P (a);
 705 #endif
 706   /* Add copies to the cap.  */
 707   for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
 708     {
 709       if (cp->first == a)
 710         {
 711           next_cp = cp->next_first_allocno_copy;
 712           another_a = cp->second;
 713         }
 714       else if (cp->second == a)
 715         {
 716           next_cp = cp->next_second_allocno_copy;
 717           another_a = cp->first;
 718         }
 719       else
 720         gcc_unreachable ();
 721       father_a = father->regno_allocno_map [ALLOCNO_REGNO (another_a)];
 722       if (father_a == NULL)
 723         father_a = ALLOCNO_CAP (another_a);
 724       if (father_a != NULL)
 725         /* Upper level allocno might be not existing because it is
 726            not mentioned or lived on the border.  It is just
 727            living on bb start of the loop.  */
 728         add_allocno_copy (cap, father_a, cp->freq, cp->move_insn,
 729                           cp->loop_tree_node);
 730     }
 731   allocno_vec = ALLOCNO_CONFLICT_ALLOCNO_VEC (a);
 732   if (allocno_vec != NULL)
 733     {
 734       conflicts_num = 0;
 735       for (i = 0;
 736            (conflict_allocno = allocno_vec [i]) != NULL;
 737            i++)
 738         conflicts_num++;
 739       allocate_allocno_conflicts (cap, conflicts_num);
 740       for (conflicts_num = i = 0;
 741            (conflict_allocno = allocno_vec [i]) != NULL;
 742            i++)
 743         {
 744           regno = ALLOCNO_REGNO (conflict_allocno);
 745           conflict_father_allocno = father->regno_allocno_map [regno];
 746           if (conflict_father_allocno == NULL)
 747             conflict_father_allocno = ALLOCNO_CAP (conflict_allocno);
 748           if (conflict_father_allocno != NULL
 749               && (ALLOCNO_CONFLICT_ALLOCNO_VEC (conflict_father_allocno)
 750                   != NULL))
 751             add_allocno_conflict (cap, conflict_father_allocno);
 752         }
 753     }
 754   if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
 755     {
 756       fprintf (ira_dump_file, "    Propagate info to cap ");
 757       print_expanded_allocno (cap);
 758       allocno_vec = ALLOCNO_CONFLICT_ALLOCNO_VEC (cap);
 759       if (allocno_vec != NULL)
 760         {
 761           fprintf (ira_dump_file, "\n      Conflicts:");
 762           for (i = 0; (conflict_allocno = allocno_vec [i]) != NULL; i++)
 763             {
 764               fprintf (ira_dump_file, " a%d(r%d,",
 765                        ALLOCNO_NUM (conflict_allocno),
 766                        ALLOCNO_REGNO (conflict_allocno));
 767               ira_assert
 768                 (ALLOCNO_LOOP_TREE_NODE (conflict_allocno)->bb == NULL);
 769               fprintf (ira_dump_file, "l%d)",
 770                        ALLOCNO_LOOP_TREE_NODE (conflict_allocno)->loop->num);
 771             }
 772         }
 773       fprintf (ira_dump_file, "\n");
 774     }
 775 }
 776
 777
 778 /* Create and return allocno live range with give attributes.  */
 779 allocno_live_range_t
 780 create_allocno_live_range (allocno_t a, int start, int finish,
 781                            allocno_live_range_t next)
 782 {
 783   allocno_live_range_t p;
 784
 785   p = pool_alloc (allocno_live_range_pool);
 786   p->allocno = a;
 787   p->start = start;
 788   p->finish = finish;
 789   p->next = next;
 790   return p;
 791 }
 792
 793 /* Create and return allocno live range with give attributes.  */
 794 allocno_live_range_t
 795 copy_allocno_live_range (allocno_live_range_t r)
 796 {
 797   allocno_live_range_t p;
 798
 799   p = pool_alloc (allocno_live_range_pool);
 800   *p = *r;
 801   return p;
 802 }
 803
 804 /* Create and return allocno live range with give attributes.  */
 805 allocno_live_range_t
 806 copy_allocno_live_range_list (allocno_live_range_t r)
 807 {
 808   allocno_live_range_t p, first, last;
 809
 810   if (r == NULL)
 811     return NULL;
 812   for (first = last = NULL; r != NULL; r = r->next)
 813     {
 814       p = copy_allocno_live_range (r);
 815       if (first == NULL)
 816         first = p;
 817       else
 818         last->next = p;
 819       last = p;
 820     }
 821   return first;
 822 }
 823
 824 /* Free allocno live range R.  */
 825 void
 826 finish_allocno_live_range (allocno_live_range_t r)
 827 {
 828   pool_free (allocno_live_range_pool, r);
 829 }
 830
 831 /* The function frees memory allocated for allocno A.  */
 832 static void
 833 finish_allocno (allocno_t a)
 834 {
 835   allocno_live_range_t r, next_r;
 836
 837   if (ALLOCNO_CONFLICT_ALLOCNO_VEC (a) != NULL)
 838     ira_free (ALLOCNO_CONFLICT_ALLOCNO_VEC (a));
 839   if (ALLOCNO_HARD_REG_COSTS (a) != NULL)
 840     ira_free (ALLOCNO_HARD_REG_COSTS (a));
 841   if (ALLOCNO_CONFLICT_HARD_REG_COSTS (a) != NULL)
 842     ira_free (ALLOCNO_CONFLICT_HARD_REG_COSTS (a));
 843   if (ALLOCNO_UPDATED_HARD_REG_COSTS (a) != NULL)
 844     ira_free (ALLOCNO_UPDATED_HARD_REG_COSTS (a));
 845   if (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) != NULL)
 846     ira_free (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a));
 847   for (r = ALLOCNO_LIVE_RANGES (a); r != NULL; r = next_r)
 848     {
 849       next_r = r->next;
 850       finish_allocno_live_range (r);
 851     }
 852   pool_free (allocno_pool, a);
 853 }
 854
 855 /* The function frees memory allocated for all allocnos.  */
 856 static void
 857 finish_allocnos (void)
 858 {
 859   int i;
 860
 861   for (i = 0; i < allocnos_num; i++)
 862     finish_allocno (allocnos [i]);
 863   ira_free (regno_allocno_map);
 864   VARRAY_FREE (allocno_varray);
 865 }
 866
 867 \f
 868
 869 /* Varray containing references to all created copies.  It is a
 870    container of array copies.  */
 871 static varray_type copy_varray;
 872
 873 /* The function initializes data concerning allocno copies.  */
 874 static void
 875 initiate_copies (void)
 876 {
 877   VARRAY_GENERIC_PTR_NOGC_INIT (copy_varray, get_max_uid (), "copies");
 878   copies = NULL;
 879   copies_num = 0;
 880 }
 881
 882 /* The function creates and returns created in LOOP_TREE_NODE copy of
 883    allocnos FIRST and SECOND with frequency FREQ, move insn
 884    MOVE_INSN.  */
 885 copy_t
 886 create_copy (allocno_t first, allocno_t second, int freq, rtx move_insn,
 887              loop_tree_node_t loop_tree_node)
 888 {
 889   copy_t cp;
 890
 891   cp = pool_alloc (copy_pool);
 892   cp->num = copies_num;
 893   cp->first = first;
 894   cp->second = second;
 895   cp->freq = freq;
 896   cp->move_insn = move_insn;
 897   cp->loop_tree_node = loop_tree_node;
 898   VARRAY_PUSH_GENERIC_PTR (copy_varray, cp);
 899   copies = (copy_t *) &VARRAY_GENERIC_PTR (copy_varray, 0);
 900   copies_num = VARRAY_ACTIVE_SIZE (copy_varray);
 901   return cp;
 902 }
 903
 904 /* The function attaches copy CP to allocnos involved into the copy.  */
 905 void
 906 add_allocno_copy_to_list (copy_t cp)
 907 {
 908   allocno_t first = cp->first, second = cp->second;
 909
 910   cp->prev_first_allocno_copy = NULL;
 911   cp->prev_second_allocno_copy = NULL;
 912   cp->next_first_allocno_copy = ALLOCNO_COPIES (first);
 913   if (cp->next_first_allocno_copy != NULL)
 914     {
 915       if (cp->next_first_allocno_copy->first == first)
 916         cp->next_first_allocno_copy->prev_first_allocno_copy = cp;
 917       else
 918         cp->next_first_allocno_copy->prev_second_allocno_copy = cp;
 919     }
 920   cp->next_second_allocno_copy = ALLOCNO_COPIES (second);
 921   if (cp->next_second_allocno_copy != NULL)
 922     {
 923       if (cp->next_second_allocno_copy->second == second)
 924         cp->next_second_allocno_copy->prev_second_allocno_copy = cp;
 925       else
 926         cp->next_second_allocno_copy->prev_first_allocno_copy = cp;
 927     }
 928   ALLOCNO_COPIES (first) = cp;
 929   ALLOCNO_COPIES (second) = cp;
 930 }
 931
 932 /* The function detaches copy CP from allocnos involved into the copy.  */
 933 void
 934 remove_allocno_copy_from_list (copy_t cp)
 935 {
 936   allocno_t first = cp->first, second = cp->second;
 937   copy_t prev, next;
 938
 939   next = cp->next_first_allocno_copy;
 940   prev = cp->prev_first_allocno_copy;
 941   if (prev == NULL)
 942     ALLOCNO_COPIES (first) = next;
 943   else if (prev->first == first)
 944     prev->next_first_allocno_copy = next;
 945   else
 946     prev->next_second_allocno_copy = next;
 947   if (next != NULL)
 948     {
 949       if (next->first == first)
 950         next->prev_first_allocno_copy = prev;
 951       else
 952         next->prev_second_allocno_copy = prev;
 953     }
 954   cp->prev_first_allocno_copy = cp->next_first_allocno_copy = NULL;
 955
 956   next = cp->next_second_allocno_copy;
 957   prev = cp->prev_second_allocno_copy;
 958   if (prev == NULL)
 959     ALLOCNO_COPIES (second) = next;
 960   else if (prev->second == second)
 961     prev->next_second_allocno_copy = next;
 962   else
 963     prev->next_first_allocno_copy = next;
 964   if (next != NULL)
 965     {
 966       if (next->second == second)
 967         next->prev_second_allocno_copy = prev;
 968       else
 969         next->prev_first_allocno_copy = prev;
 970     }
 971   cp->prev_second_allocno_copy = cp->next_second_allocno_copy = NULL;
 972 }
 973
 974 /* The function makes copy CP a canonical copy where number of the
 975    first allocno is less than the second one.  */
 976 void
 977 swap_allocno_copy_ends_if_necessary (copy_t cp)
 978 {
 979   allocno_t temp;
 980   copy_t temp_cp;
 981
 982   if (ALLOCNO_NUM (cp->first) <= ALLOCNO_NUM (cp->second))
 983     return;
 984
 985   temp = cp->first;
 986   cp->first = cp->second;
 987   cp->second = temp;
 988
 989   temp_cp = cp->prev_first_allocno_copy;
 990   cp->prev_first_allocno_copy = cp->prev_second_allocno_copy;
 991   cp->prev_second_allocno_copy = temp_cp;
 992
 993   temp_cp = cp->next_first_allocno_copy;
 994   cp->next_first_allocno_copy = cp->next_second_allocno_copy;
 995   cp->next_second_allocno_copy = temp_cp;
 996 }
 997
 998 /* The function creates and returns new copy of allocnos FIRST and
 999    SECOND with frequency FREQ corresponding to move insn INSN (if
1000    any) and originated from LOOP_TREE_NODE.  */
1001 copy_t
1002 add_allocno_copy (allocno_t first, allocno_t second, int freq, rtx insn,
1003                   loop_tree_node_t loop_tree_node)
1004 {
1005   copy_t cp;
1006
1007   cp = create_copy (first, second, freq, insn, loop_tree_node);
1008   ira_assert (first != NULL && second != NULL);
1009   add_allocno_copy_to_list (cp);
1010   swap_allocno_copy_ends_if_necessary (cp);
1011   return cp;
1012 }
1013
1014 /* The function frees memory allocated for copy CP.  */
1015 static void
1016 finish_copy (copy_t cp)
1017 {
1018   pool_free (copy_pool, cp);
1019 }
1020
1021
1022 /* The function frees memory allocated for all copies.  */
1023 static void
1024 finish_copies (void)
1025 {
1026   int i;
1027
1028   for (i = 0; i < copies_num; i++)
1029     finish_copy (copies [i]);
1030   VARRAY_FREE (copy_varray);
1031 }
1032
1033 \f
1034
1035 /* The current loop tree node and its map.  */
1036 loop_tree_node_t ira_curr_loop_tree_node;
1037 allocno_t *ira_curr_regno_allocno_map;
1038
1039 /* The recursive function traverses loop tree node with root LOOP_NODE
1040    calling non-null functions PREORDER_FUNC and POSTORDER_FUNC
1041    correspondingly in preorder and postorder.  The function sets up
1042    IRA_CURR_LOOP_TREE_NODE.  If BB_FIRST_P, BB of LOOP_NODE is
1043    processed before its subloops.  */
1044 void
1045 traverse_loop_tree (int bb_first_p, loop_tree_node_t loop_node,
1046                     void (*preorder_func) (loop_tree_node_t),
1047                     void (*postorder_func) (loop_tree_node_t))
1048 {
1049   loop_tree_node_t subloop_node;
1050
1051   if (loop_node->bb == NULL)
1052     {
1053       ira_curr_loop_tree_node = loop_node;
1054       ira_curr_regno_allocno_map = ira_curr_loop_tree_node->regno_allocno_map;
1055     }
1056   if (preorder_func != NULL)
1057     (*preorder_func) (loop_node);
1058
1059   for (subloop_node = loop_node->inner;
1060        subloop_node != NULL;
1061        subloop_node = subloop_node->next)
1062     if (! bb_first_p || subloop_node->bb != NULL)
1063       {
1064         traverse_loop_tree (bb_first_p, subloop_node,
1065                             preorder_func, postorder_func);
1066         ira_curr_loop_tree_node = loop_node;
1067         ira_curr_regno_allocno_map
1068           = ira_curr_loop_tree_node->regno_allocno_map;
1069       }
1070
1071   if (bb_first_p)
1072     for (subloop_node = loop_node->inner;
1073          subloop_node != NULL;
1074          subloop_node = subloop_node->next)
1075       if (subloop_node->bb == NULL)
1076         {
1077           traverse_loop_tree (bb_first_p, subloop_node,
1078                               preorder_func, postorder_func);
1079           ira_curr_loop_tree_node = loop_node;
1080           ira_curr_regno_allocno_map
1081             = ira_curr_loop_tree_node->regno_allocno_map;
1082         }
1083
1084   if (postorder_func != NULL)
1085     (*postorder_func) (loop_node);
1086 }
1087
1088 \f
1089
1090 /* The current basic block.  */
1091 static basic_block curr_bb;
1092
1093 /* This recursive function creates allocnos corresponding to
1094    pseudo-registers containing in X.  Nonzero OUTPUT_P means that X is
1095    lvalue.  */
1096 static void
1097 create_insn_allocnos (rtx x, int output_p)
1098 {
1099   int i, j;
1100   const char *fmt;
1101   enum rtx_code code = GET_CODE (x);
1102
1103   if (code == REG)
1104     {
1105       int regno;
1106
1107       if ((regno = REGNO (x)) >= FIRST_PSEUDO_REGISTER)
1108         {
1109           allocno_t a;
1110
1111           if ((a = ira_curr_loop_tree_node->regno_allocno_map [regno]) == NULL)
1112             a = create_allocno (regno, FALSE, ira_curr_loop_tree_node);
1113
1114           ALLOCNO_NREFS (a)++;
1115           ALLOCNO_FREQ (a) += REG_FREQ_FROM_BB (curr_bb);
1116           bitmap_set_bit (ira_curr_loop_tree_node->mentioned_allocnos,
1117                           ALLOCNO_NUM (a));
1118           if (output_p)
1119             bitmap_set_bit (ira_curr_loop_tree_node->modified_regnos, regno);
1120         }
1121       return;
1122     }
1123   else if (code == SET)
1124     {
1125       create_insn_allocnos (SET_DEST (x), TRUE);
1126       create_insn_allocnos (SET_SRC (x), FALSE);
1127       return;
1128     }
1129   else if (code == CLOBBER)
1130     {
1131       create_insn_allocnos (XEXP (x, 0), TRUE);
1132       return;
1133     }
1134   else if (code == MEM)
1135     {
1136       create_insn_allocnos (XEXP (x, 0), FALSE);
1137       return;
1138     }
1139   else if (code == PRE_DEC || code == POST_DEC || code == PRE_INC ||
1140            code == POST_INC || code == POST_MODIFY || code == PRE_MODIFY)
1141     {
1142       create_insn_allocnos (XEXP (x, 0), TRUE);
1143       create_insn_allocnos (XEXP (x, 0), FALSE);
1144       return;
1145     }
1146
1147   fmt = GET_RTX_FORMAT (code);
1148   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1149     {
1150       if (fmt[i] == 'e')
1151         create_insn_allocnos (XEXP (x, i), output_p);
1152       else if (fmt[i] == 'E')
1153         for (j = 0; j < XVECLEN (x, i); j++)
1154           create_insn_allocnos (XVECEXP (x, i, j), output_p);
1155     }
1156 }
1157
1158 /* The function creates allocnos corresponding to pseudo-registers
1159    living in basic blocks represented by the corresponding loop tree
1160    node BB_NODE.  */
1161 static void
1162 create_bb_allocnos (loop_tree_node_t bb_node)
1163 {
1164   basic_block bb;
1165   rtx insn;
1166   unsigned int i;
1167   bitmap_iterator bi;
1168   allocno_t *map;
1169
1170   curr_bb = bb = bb_node->bb;
1171   ira_assert (bb != NULL);
1172   FOR_BB_INSNS (bb, insn)
1173     if (INSN_P (insn))
1174       create_insn_allocnos (PATTERN (insn), FALSE);
1175   /* It might be a allocno living through from one subloop to
1176      another.  */
1177   map = ira_curr_loop_tree_node->regno_allocno_map;
1178   EXECUTE_IF_SET_IN_REG_SET (DF_LR_IN (bb), FIRST_PSEUDO_REGISTER, i, bi)
1179     if (map [i] == NULL)
1180       create_allocno (i, FALSE, ira_curr_loop_tree_node);
1181 }
1182
1183 /* The function creates allocnos corresponding to pseudo-registers
1184    living on edge E (a loop enter or exit).  It also finds allocnos
1185    living on the loop border. */
1186 static void
1187 create_loop_allocnos (edge e)
1188 {
1189   unsigned int i;
1190   bitmap live_in_regs, border_allocnos;
1191   bitmap_iterator bi;
1192   allocno_t *map;
1193
1194   live_in_regs = DF_LR_IN (e->dest);
1195   map = ira_curr_loop_tree_node->regno_allocno_map;
1196   border_allocnos = ira_curr_loop_tree_node->border_allocnos;
1197   EXECUTE_IF_SET_IN_REG_SET (DF_LR_OUT (e->src),
1198                              FIRST_PSEUDO_REGISTER, i, bi)
1199     if (bitmap_bit_p (live_in_regs, i))
1200       {
1201         if (map [i] == NULL)
1202           create_allocno (i, FALSE, ira_curr_loop_tree_node);
1203         bitmap_set_bit (border_allocnos, ALLOCNO_NUM (map [i]));
1204       }
1205 }
1206
1207 /* The function creates allocnos corresponding to pseudo-registers
1208    living in loop represented by the corresponding loop tree node
1209    LOOP_NODE.  */
1210 static void
1211 create_loop_tree_node_allocnos (loop_tree_node_t loop_node)
1212 {
1213   if (loop_node->bb != NULL)
1214     create_bb_allocnos (loop_node);
1215   else if (loop_node != ira_loop_tree_root)
1216     {
1217       int i;
1218       edge_iterator ei;
1219       edge e;
1220       VEC (edge, heap) *edges;
1221
1222       FOR_EACH_EDGE (e, ei, loop_node->loop->header->preds)
1223         if (e->src != loop_node->loop->latch)
1224           create_loop_allocnos (e);
1225
1226       edges = get_loop_exit_edges (loop_node->loop);
1227       for (i = 0; VEC_iterate (edge, edges, i, e); i++)
1228         create_loop_allocnos (e);
1229       VEC_free (edge, heap, edges);
1230     }
1231 }
1232
1233 /* The function creates allocnos corresponding to pseudo-registers in
1234    the current function.  The function traverses the loop tree for
1235    this.  */
1236 static void
1237 create_allocnos (void)
1238 {
1239   int i;
1240   allocno_t a, father_a;
1241   loop_tree_node_t father;
1242
1243   /* We need to process BB first to correctly link allocnos by
1244      next_regno_allocno field.  */
1245   traverse_loop_tree (TRUE, ira_loop_tree_root,
1246                       create_loop_tree_node_allocnos, NULL);
1247   if (flag_ira_algorithm != IRA_ALGORITHM_REGIONAL
1248       && flag_ira_algorithm != IRA_ALGORITHM_MIXED)
1249     return;
1250   /* Propagate number of references and frequencies for regional
1251      register allocator.  */
1252   for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--)
1253     for (a = regno_allocno_map [i];
1254          a != NULL;
1255          a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
1256       if ((father = ALLOCNO_LOOP_TREE_NODE (a)->father) != NULL
1257           && (father_a = father->regno_allocno_map [i]) != NULL)
1258         {
1259           ALLOCNO_NREFS (father_a) += ALLOCNO_NREFS (a);
1260           ALLOCNO_FREQ (father_a) += ALLOCNO_FREQ (a);
1261         }
1262 }
1263
1264 \f
1265
1266 /* Bitmap of allocnos living only inside the current loop.  */
1267 static bitmap local_allocnos_bitmap;
1268
1269 /* The function creates caps representing allocnos living only inside
1270    the loop given by LOOP_NODE on higher loop level.  */
1271 static void
1272 create_loop_tree_node_caps (loop_tree_node_t loop_node)
1273 {
1274   unsigned int i;
1275   bitmap_iterator bi;
1276   loop_tree_node_t father;
1277
1278   if (loop_node->bb != NULL || loop_node == ira_loop_tree_root)
1279     return;
1280   bitmap_and_compl (local_allocnos_bitmap, loop_node->mentioned_allocnos,
1281                     loop_node->border_allocnos);
1282   father = loop_node->father;
1283   EXECUTE_IF_SET_IN_BITMAP (local_allocnos_bitmap, 0, i, bi)
1284     if (father->regno_allocno_map [ALLOCNO_REGNO (allocnos [i])] == NULL)
1285       create_cap_allocno (allocnos [i]);
1286 }
1287
1288 /* The function propagate info to caps mentioned in LOOP_NODE.  */
1289 static void
1290 propagate_info_to_loop_tree_node_caps (loop_tree_node_t loop_node)
1291 {
1292   unsigned int i;
1293   bitmap_iterator bi;
1294   allocno_t a;
1295
1296   if (loop_node->bb != NULL)
1297     return;
1298   EXECUTE_IF_SET_IN_BITMAP (loop_node->mentioned_allocnos, 0, i, bi)
1299     {
1300       a = allocnos [i];
1301       if (ALLOCNO_CAP_MEMBER (a) != NULL)
1302         propagate_info_to_cap (a);
1303     }
1304 }
1305
1306 \f
1307
1308 /* The function merges ranges R1 and R2 and returns the result.  */
1309 static allocno_live_range_t
1310 merge_ranges (allocno_live_range_t r1, allocno_live_range_t r2)
1311 {
1312   allocno_live_range_t first, last, temp;
1313
1314   if (r1 == NULL)
1315     return r2;
1316   if (r2 == NULL)
1317     return r1;
1318   for (first = last = NULL; r1 != NULL && r2 != NULL;)
1319     {
1320       if (r1->start < r2->start)
1321         {
1322           temp = r1;
1323           r1 = r2;
1324           r2 = temp;
1325         }
1326       if (r1->start <= r2->finish + 1)
1327         {
1328           /* Intersected ranges: merge r1 and r2 into r1.  */
1329           r1->start = r2->start;
1330           if (r1->finish < r2->finish)
1331             r1->finish = r2->finish;
1332           temp = r2;
1333           r2 = r2->next;
1334           finish_allocno_live_range (temp);
1335           if (r2 == NULL)
1336             {
1337               /* To try to merge with subsequent ranges in r1.  */
1338               r2 = r1->next;
1339               r1->next = NULL;
1340             }
1341         }
1342       else
1343         {
1344           /* Add r1 to the result.  */
1345           if (first == NULL)
1346             first = last = r1;
1347           else
1348             {
1349               last->next = r1;
1350               last = r1;
1351             }
1352           r1 = r1->next;
1353           if (r1 == NULL)
1354             {
1355               /* To try to merge with subsequent ranges in r2.  */
1356               r1 = r2->next;
1357               r2->next = NULL;
1358             }
1359         }
1360     }
1361   if (r1 != NULL)
1362     {
1363       if (first == NULL)
1364         first = r1;
1365       else
1366         last->next = r1;
1367       ira_assert (r1->next == NULL);
1368     }
1369   else if (r2 != NULL)
1370     {
1371       if (first == NULL)
1372         first = r2;
1373       else
1374         last->next = r2;
1375       ira_assert (r2->next == NULL);
1376     }
1377   else
1378     ira_assert (last->next == NULL);
1379   return first;
1380 }
1381
1382 /* The function returns immediate common dominator of two loop tree
1383    nodes N1 and N2.  */
1384 static loop_tree_node_t
1385 common_loop_tree_node_dominator (loop_tree_node_t n1, loop_tree_node_t n2)
1386 {
1387   ira_assert (n1 != NULL && n2 != NULL);
1388   if (n1 == n2)
1389     return n1;
1390   if (n1->level < n2->level)
1391     return common_loop_tree_node_dominator (n1, n2->father);
1392   else if (n1->level > n2->level)
1393     return common_loop_tree_node_dominator (n1->father, n2);
1394   else
1395     return common_loop_tree_node_dominator (n1->father, n2->father);
1396 }
1397
1398 /* Map: regno -> allocnos which will finally represent the regno for
1399    IR with one region.  */
1400 static allocno_t *regno_top_level_allocno_map;
1401
1402
1403 /* The function check conflicts A with allocnos from CONFLICT_VECT and
1404    add them (more accurately corresponding final IR allocnos) if it is
1405    necessary.  */
1406 static void
1407 check_and_add_conflicts (allocno_t a, allocno_t *conflict_vec)
1408 {
1409   allocno_t conflict_a;
1410   int i;
1411
1412   for (i = 0; (conflict_a = conflict_vec [i]) != NULL; i++)
1413     {
1414       conflict_a
1415         = regno_top_level_allocno_map [REGNO (ALLOCNO_REG (conflict_a))];
1416       if (allocno_conflict_p (conflict_a, a)
1417           && allocno_conflict_index (conflict_a, a) < 0)
1418         {
1419           ira_assert (allocno_conflict_index (a, conflict_a) < 0);
1420           add_to_allocno_conflict_vec (conflict_a, a);
1421           add_to_allocno_conflict_vec (a, conflict_a);
1422           if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1423             fprintf (ira_dump_file,
1424                      "      Add underlying conflict a%dr%d-a%dr%d\n",
1425                      ALLOCNO_NUM (a), REGNO (ALLOCNO_REG (a)),
1426                      ALLOCNO_NUM (conflict_a),\
1427                      REGNO (ALLOCNO_REG (conflict_a)));
1428         }
1429     }
1430 }
1431
1432 /* This recursive function checks and adds (if necessary) conflicts
1433    with A processing conflicts of allocnos corresponding to A in
1434    subloops.  If GO_DEEPER_P is false, the function stops to go deeper
1435    in loop tree when allocno which will represent allocno in final IR
1436    is achieved. */
1437 static void
1438 add_conflict_with_underlying_allocnos (allocno_t a,
1439                                        loop_tree_node_t loop_node,
1440                                        int go_deeper_p)
1441 {
1442   loop_tree_node_t subloop_node;
1443   allocno_t subloop_a;
1444
1445   for (subloop_node = loop_node->inner;
1446        subloop_node != NULL;
1447        subloop_node = subloop_node->next)
1448     {
1449       if (subloop_node->bb != NULL)
1450         continue;
1451       subloop_a = subloop_node->regno_allocno_map [ALLOCNO_REGNO (a)];
1452       if (subloop_a == NULL)
1453         continue;
1454       if (! go_deeper_p
1455           && subloop_a == regno_top_level_allocno_map [REGNO (ALLOCNO_REG
1456                                                               (subloop_a))])
1457         continue;
1458       check_and_add_conflicts (a, ALLOCNO_CONFLICT_ALLOCNO_VEC (subloop_a));
1459       add_conflict_with_underlying_allocnos (a, subloop_node, go_deeper_p);
1460     }
1461 }
1462
1463 /* The function flattens IR.  In other words, the function transforms
1464    IR as it were build with one region (without loops).  We could make
1465    it much simpler by rebuilding IR with one region, but unfortunately
1466    it takes a lot of time.  */
1467 void
1468 ira_flattening (int max_regno_before_emit, int max_point_before_emit)
1469 {
1470   int i, j, k, free, propagate_p, stop_p, keep_p, hard_regs_num;
1471   unsigned int n;
1472   enum reg_class cover_class;
1473   rtx call, *allocno_calls;
1474   allocno_t a, father_a, conflict_a, first, second, node_first, node_second;
1475   allocno_t dominator_a, *allocno_vec;
1476   copy_t cp;
1477   loop_tree_node_t father, node, dominator;
1478   allocno_live_range_t r;
1479   bitmap live_allocnos;
1480   bitmap_iterator bi;
1481
1482   regno_top_level_allocno_map
1483     = ira_allocate (max_reg_num () * sizeof (allocno_t));
1484   memset (regno_top_level_allocno_map, 0, max_reg_num () * sizeof (allocno_t));
1485   expand_calls ();
1486   /* Updating accumulated attributes.  */
1487   for (i = max_regno_before_emit - 1; i >= FIRST_PSEUDO_REGISTER; i--)
1488     {
1489       propagate_p = FALSE;
1490       for (a = regno_allocno_map [i];
1491            a != NULL;
1492            a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
1493         {
1494           if (ALLOCNO_CAP_MEMBER (a) == NULL
1495               && (unsigned int) ALLOCNO_REGNO (a) != REGNO (ALLOCNO_REG (a))
1496               && ALLOCNO_CALLS_CROSSED_NUM (a) != 0)
1497             {
1498               allocno_calls = (VEC_address (rtx,
1499                                             regno_calls [ALLOCNO_REGNO (a)])
1500                                + ALLOCNO_CALLS_CROSSED_START (a));
1501               for (j = ALLOCNO_CALLS_CROSSED_NUM (a) - 1; j >= 0; j--)
1502                 {
1503                   call = allocno_calls [j];
1504                   if (call == NULL_RTX)
1505                     continue;
1506                   add_regno_call (REGNO (ALLOCNO_REG (a)), call);
1507                   allocno_calls [j] = NULL_RTX;
1508                 }
1509             }
1510           if ((father = ALLOCNO_LOOP_TREE_NODE (a)->father) == NULL
1511               || (father_a = father->regno_allocno_map [ALLOCNO_REGNO (a)])
1512               == NULL)
1513             {
1514               ALLOCNO_COPIES (a) = NULL;
1515               regno_top_level_allocno_map [REGNO (ALLOCNO_REG (a))] = a;
1516               continue;
1517             }
1518           if (propagate_p)
1519             {
1520               COPY_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (father_a),
1521                                  ALLOCNO_CONFLICT_HARD_REGS (father_a));
1522               IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (father_a),
1523                                 ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a));
1524 #ifdef STACK_REGS
1525               ALLOCNO_TOTAL_NO_STACK_REG_P (father_a)
1526                 = (ALLOCNO_NO_STACK_REG_P (father_a)
1527                    || ALLOCNO_TOTAL_NO_STACK_REG_P (a));
1528 #endif
1529             }
1530           if (REGNO (ALLOCNO_REG (a)) == REGNO (ALLOCNO_REG (father_a)))
1531             {
1532               if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1533                 {
1534                   fprintf (ira_dump_file,
1535                            "      Moving ranges of a%dr%d to a%dr%d: ",
1536                            ALLOCNO_NUM (a), REGNO (ALLOCNO_REG (a)),
1537                            ALLOCNO_NUM (father_a),
1538                            REGNO (ALLOCNO_REG (father_a)));
1539                   print_live_range_list (ira_dump_file,
1540                                          ALLOCNO_LIVE_RANGES (a));
1541                 }
1542               ALLOCNO_LIVE_RANGES (father_a)
1543                 = merge_ranges (ALLOCNO_LIVE_RANGES (a),
1544                                 ALLOCNO_LIVE_RANGES (father_a));
1545               ALLOCNO_LIVE_RANGES (a) = NULL;
1546               ALLOCNO_MEM_OPTIMIZED_DEST_P (father_a)
1547                 = (ALLOCNO_MEM_OPTIMIZED_DEST_P (father_a)
1548                    || ALLOCNO_MEM_OPTIMIZED_DEST_P (a));
1549               continue;
1550             }
1551           propagate_p = TRUE;
1552           first = ALLOCNO_MEM_OPTIMIZED_DEST (a) == NULL ? NULL : a;
1553           for (;;)
1554             {
1555               if (first == NULL
1556                   && ALLOCNO_MEM_OPTIMIZED_DEST (father_a) != NULL)
1557                 first = father_a;
1558               ALLOCNO_NREFS (father_a) -= ALLOCNO_NREFS (a);
1559               ALLOCNO_FREQ (father_a) -= ALLOCNO_FREQ (a);
1560               ALLOCNO_CALL_FREQ (father_a) -= ALLOCNO_CALL_FREQ (a);
1561               cover_class = ALLOCNO_COVER_CLASS (father_a);
1562               hard_regs_num = class_hard_regs_num [cover_class];
1563               for (j = 0; j < hard_regs_num; j++)
1564                 {
1565                   ALLOCNO_HARD_REG_COSTS (father_a) [j]
1566                     -= ALLOCNO_HARD_REG_COSTS (a) [j];
1567                   ALLOCNO_CONFLICT_HARD_REG_COSTS (father_a) [j]
1568                     -= ALLOCNO_CONFLICT_HARD_REG_COSTS (a) [j];
1569                 }
1570               ALLOCNO_COVER_CLASS_COST (father_a)
1571                 -= ALLOCNO_COVER_CLASS_COST (a);
1572               ALLOCNO_MEMORY_COST (father_a) -= ALLOCNO_MEMORY_COST (a);
1573               if ((father = ALLOCNO_LOOP_TREE_NODE (father_a)->father) == NULL
1574                   || (father_a = (father->regno_allocno_map
1575                                   [ALLOCNO_REGNO (father_a)])) == NULL)
1576                 break;
1577             }
1578           if (first != NULL)
1579             {
1580               father_a = ALLOCNO_MEM_OPTIMIZED_DEST (first);
1581               dominator = common_loop_tree_node_dominator
1582                           (ALLOCNO_LOOP_TREE_NODE (father_a),
1583                            ALLOCNO_LOOP_TREE_NODE (first));
1584               dominator_a = dominator->regno_allocno_map [ALLOCNO_REGNO (a)];
1585               ira_assert (father_a != NULL);
1586               stop_p = first != a;
1587               /* Remember that exit can be to a grandparent (not only
1588                  a parent) or a child of grandparent.  */
1589               for (first = a;;)
1590                 {
1591                   if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1592                     {
1593                       fprintf
1594                         (ira_dump_file,
1595                          "      Coping ranges of a%dr%d to a%dr%d: ",
1596                          ALLOCNO_NUM (first), REGNO (ALLOCNO_REG (first)),
1597                          ALLOCNO_NUM (father_a),
1598                          REGNO (ALLOCNO_REG (father_a)));
1599                       print_live_range_list (ira_dump_file,
1600                                              ALLOCNO_LIVE_RANGES (first));
1601                     }
1602                   ALLOCNO_LIVE_RANGES (father_a)
1603                     = merge_ranges (copy_allocno_live_range_list
1604                                     (ALLOCNO_LIVE_RANGES (first)),
1605                                     ALLOCNO_LIVE_RANGES (father_a));
1606                   if (stop_p)
1607                     break;
1608                   father = ALLOCNO_LOOP_TREE_NODE (first)->father;
1609                   ira_assert (father != NULL);
1610                   first = father->regno_allocno_map [ALLOCNO_REGNO (a)];
1611                   ira_assert (first != NULL);
1612                   if (first == dominator_a)
1613                     break;
1614                 }
1615             }
1616           ALLOCNO_COPIES (a) = NULL;
1617           regno_top_level_allocno_map [REGNO (ALLOCNO_REG (a))] = a;
1618         }
1619     }
1620   /* Fix final allocnos attributes concerning calls.  */
1621   compress_calls ();
1622   for (i = 0; i < allocnos_num; i++)
1623     {
1624       a = allocnos [i];
1625       if (a != regno_top_level_allocno_map [REGNO (ALLOCNO_REG (a))]
1626           || ALLOCNO_CAP_MEMBER (a) != NULL)
1627         continue;
1628       ALLOCNO_CALLS_CROSSED_START (a) = 0;
1629       ALLOCNO_CALLS_CROSSED_NUM (a)
1630         = VEC_length (rtx, regno_calls [REGNO (ALLOCNO_REG (a))]);
1631     }
1632   /* Mark copies for removing and change allocnos in copies.  */
1633   for (i = 0; i < copies_num; i++)
1634     {
1635       cp = copies [i];
1636       if (ALLOCNO_CAP_MEMBER (cp->first) != NULL
1637           || ALLOCNO_CAP_MEMBER (cp->second) != NULL)
1638         {
1639           if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1640             fprintf
1641               (ira_dump_file, "      Remove cp%d:%c%dr%d-%c%dr%d\n",
1642                cp->num, ALLOCNO_CAP_MEMBER (cp->first) != NULL ? 'c' : 'a',
1643                ALLOCNO_NUM (cp->first), REGNO (ALLOCNO_REG (cp->first)),
1644                ALLOCNO_CAP_MEMBER (cp->second) != NULL ? 'c' : 'a',
1645                ALLOCNO_NUM (cp->second), REGNO (ALLOCNO_REG (cp->second)));
1646           cp->loop_tree_node = NULL;
1647           continue;
1648         }
1649       first = regno_top_level_allocno_map [REGNO (ALLOCNO_REG (cp->first))];
1650       second = regno_top_level_allocno_map [REGNO (ALLOCNO_REG (cp->second))];
1651       node = cp->loop_tree_node;
1652       if (node == NULL)
1653         keep_p = TRUE; /* It copy generated in ira-emit.c.  */
1654       else
1655         {
1656           /* Check that the copy was not propagated from level on
1657              which we will have different pseudos.  */
1658           node_first = node->regno_allocno_map [ALLOCNO_REGNO (cp->first)];
1659           node_second = node->regno_allocno_map [ALLOCNO_REGNO (cp->second)];
1660           keep_p = ((REGNO (ALLOCNO_REG (first))
1661                      == REGNO (ALLOCNO_REG (node_first)))
1662                      && (REGNO (ALLOCNO_REG (second))
1663                          == REGNO (ALLOCNO_REG (node_second))));
1664         }
1665       if (keep_p)
1666         {
1667           cp->loop_tree_node = ira_loop_tree_root;
1668           cp->first = first;
1669           cp->second = second;
1670         }
1671       else
1672         {
1673           cp->loop_tree_node = NULL;
1674           if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1675             fprintf (ira_dump_file, "      Remove cp%d:a%dr%d-a%dr%d\n",
1676                      cp->num, ALLOCNO_NUM (cp->first),
1677                      REGNO (ALLOCNO_REG (cp->first)), ALLOCNO_NUM (cp->second),
1678                      REGNO (ALLOCNO_REG (cp->second)));
1679         }
1680     }
1681   /* Add conflicting allocnos from lower levels.  If we have a situation
1682         A1----conflict---B1
1683         A2----conflict---B2
1684
1685      and A1 and A2 will be presented by themselves in final IR and B1
1686      and B2 will be presented by B1, then we need to check conflict A2
1687      and B1.
1688
1689      There is another situation when we should check and add conflicts
1690      too.  It should be done when we removed restoring allocno value
1691      at the loop exits because the allocno value is stored in memory
1692      and the value is not changed in the loop.  In this case the
1693      allocno lives in the loop and can conflict with allocnos inside
1694      the loop.  */
1695   for (i = 0; i < allocnos_num; i++)
1696     {
1697       a = allocnos [i];
1698       if (a != regno_top_level_allocno_map [REGNO (ALLOCNO_REG (a))]
1699           || ALLOCNO_CAP_MEMBER (a) != NULL)
1700         continue;
1701       add_conflict_with_underlying_allocnos (a, ALLOCNO_LOOP_TREE_NODE (a),
1702                                              FALSE);
1703       if ((first = ALLOCNO_MEM_OPTIMIZED_DEST (a)) != NULL)
1704         {
1705           first = regno_top_level_allocno_map [REGNO (ALLOCNO_REG (first))];
1706           check_and_add_conflicts
1707             (first, ALLOCNO_CONFLICT_ALLOCNO_VEC (a));
1708           add_conflict_with_underlying_allocnos
1709             (first, ALLOCNO_LOOP_TREE_NODE (a), TRUE);
1710         }
1711     }
1712   /* Change allocnos regno, conflicting allocnos, and range allocnos.  */
1713   for (i = 0; i < allocnos_num; i++)
1714     {
1715       a = allocnos [i];
1716       if (a != regno_top_level_allocno_map [REGNO (ALLOCNO_REG (a))]
1717           || ALLOCNO_CAP_MEMBER (a) != NULL)
1718         continue;
1719       ALLOCNO_LOOP_TREE_NODE (a) = ira_loop_tree_root;
1720       ALLOCNO_REGNO (a) = REGNO (ALLOCNO_REG (a));
1721       allocno_vec = ALLOCNO_CONFLICT_ALLOCNO_VEC (a);
1722       for (j = 0; (conflict_a = allocno_vec [j]) != NULL; j++)
1723         allocno_vec [j]
1724           = regno_top_level_allocno_map [REGNO (ALLOCNO_REG (conflict_a))];
1725       for (r = ALLOCNO_LIVE_RANGES (a); r != NULL; r = r->next)
1726         r->allocno = a;
1727     }
1728   /* Remove allocnos on lower levels of the loop tree and
1729      enumerate allocnos.  */
1730   for (free = 0, i = 0; i < allocnos_num; i++)
1731     {
1732       a = allocnos [i];
1733       if (ALLOCNO_LOOP_TREE_NODE (a) != ira_loop_tree_root
1734           || ALLOCNO_CAP_MEMBER (a) != NULL)
1735         {
1736           if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1737             fprintf (ira_dump_file, "      Remove a%dr%d\n",
1738                      ALLOCNO_NUM (a), REGNO (ALLOCNO_REG (a)));
1739           finish_allocno (a);
1740           continue;
1741         }
1742       ALLOCNO_CAP (a) = NULL;
1743       /* Remove conflicts.  */
1744       allocno_vec = ALLOCNO_CONFLICT_ALLOCNO_VEC (a);
1745       for (k = j = ALLOCNO_CONFLICT_ALLOCNOS_NUM (a);
1746            (conflict_a = allocno_vec [j]) != NULL;
1747            j++)
1748         {
1749           if (allocno_conflict_p (a, conflict_a))
1750             allocno_vec [k++] = conflict_a;
1751           else
1752             {
1753               if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1754                 fprintf (ira_dump_file,
1755                          "      Remove conflict a%dr%d - a%dr%d\n",
1756                          ALLOCNO_NUM (a), REGNO (ALLOCNO_REG (a)),
1757                          ALLOCNO_NUM (conflict_a),
1758                          REGNO (ALLOCNO_REG (conflict_a)));
1759
1760             }
1761         }
1762       allocno_vec [k] = NULL;
1763       ALLOCNO_TOTAL_CONFLICT_ALLOCNOS_NUM (a) = k;
1764       if (i == free)
1765         {
1766           free++;
1767           continue;
1768         }
1769       if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1770         fprintf (ira_dump_file, "      Enumerate a%dr%d to a%d\n",
1771                  ALLOCNO_NUM (a), REGNO (ALLOCNO_REG (a)), free);
1772       ALLOCNO_NUM (a) = free;
1773       allocnos [free++] = a;
1774     }
1775   for (i = free; i < allocnos_num; i++)
1776     VARRAY_POP (allocno_varray);
1777   allocnos = (allocno_t *) &VARRAY_GENERIC_PTR (allocno_varray, 0);
1778   allocnos_num = VARRAY_ACTIVE_SIZE (allocno_varray);
1779   /* Remove unnecessary copies, and enumerate copies.  */
1780   for (free = i = 0; i < copies_num; i++)
1781     {
1782       cp = copies [i];
1783       if (cp->loop_tree_node == NULL)
1784         {
1785           finish_copy (cp);
1786           continue;
1787         }
1788       ira_assert
1789         (ALLOCNO_LOOP_TREE_NODE (cp->first) == ira_loop_tree_root
1790          && ALLOCNO_LOOP_TREE_NODE (cp->second) == ira_loop_tree_root);
1791       add_allocno_copy_to_list (cp);
1792       swap_allocno_copy_ends_if_necessary (cp);
1793       if (i == free)
1794         {
1795           free++;
1796           continue;
1797         }
1798       if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1799         fprintf (ira_dump_file,
1800                  "      Enumerate cp%d to cp%d\n", cp->num, free);
1801       cp->num = free;
1802       copies [free++] = cp;
1803     }
1804   for (i = free; i < copies_num; i++)
1805     VARRAY_POP (copy_varray);
1806   copies = (copy_t *) &VARRAY_GENERIC_PTR (copy_varray, 0);
1807   copies_num = VARRAY_ACTIVE_SIZE (copy_varray);
1808   rebuild_regno_allocno_maps ();
1809   rebuild_start_finish_chains ();
1810   ira_free (regno_top_level_allocno_map);
1811   live_allocnos = ira_allocate_bitmap ();
1812   for (i = max_point_before_emit; i < max_point; i++)
1813     {
1814       for (r = start_point_ranges [i]; r != NULL; r = r->start_next)
1815         {
1816           a = r->allocno;
1817           j = ALLOCNO_NUM (a);
1818           EXECUTE_IF_SET_IN_BITMAP (live_allocnos, 0, n, bi)
1819             {
1820               if (n == (unsigned int) j)
1821                 continue;
1822               conflict_a = allocnos [n];
1823               if (ALLOCNO_COVER_CLASS (a) == ALLOCNO_COVER_CLASS (conflict_a))
1824                 {
1825                   if (allocno_conflict_index (a, conflict_a) < 0)
1826                     {
1827                       if (internal_flag_ira_verbose > 3
1828                           && ira_dump_file != NULL)
1829                         fprintf
1830                           (ira_dump_file,
1831                            "      Add a%dr%d to conflict vec of a%dr%d\n",
1832                            ALLOCNO_NUM (conflict_a),
1833                            REGNO (ALLOCNO_REG (conflict_a)),
1834                            ALLOCNO_NUM (a), REGNO (ALLOCNO_REG (a)));
1835                       add_to_allocno_conflict_vec (a, conflict_a);
1836                     }
1837                   if (allocno_conflict_index (conflict_a, a) < 0)
1838                     {
1839                       if (internal_flag_ira_verbose > 3
1840                           && ira_dump_file != NULL)
1841                         fprintf
1842                           (ira_dump_file,
1843                            "      Add a%dr%d to conflict vec of a%dr%d\n",
1844                            ALLOCNO_NUM (a), REGNO (ALLOCNO_REG (a)),
1845                            ALLOCNO_NUM (conflict_a),
1846                            REGNO (ALLOCNO_REG (conflict_a)));
1847                       add_to_allocno_conflict_vec (conflict_a, a);
1848                     }
1849                 }
1850             }
1851           bitmap_set_bit (live_allocnos, j);
1852         }
1853
1854       for (r = finish_point_ranges [i]; r != NULL; r = r->finish_next)
1855         bitmap_clear_bit (live_allocnos, ALLOCNO_NUM (r->allocno));
1856     }
1857   ira_free_bitmap (live_allocnos);
1858 }
1859
1860 \f
1861
1862 /* This entry function creates internal representation for IRA
1863    (allocnos, copies, loop tree nodes).  If LOOPS_P is zero the nodes
1864    corresponding to the loops (except the root which corresponds the
1865    all function) and correspondingly allocnos for the loops will be
1866    not created (it will be done only for basic blocks).  Such value is
1867    used for Chaitin-Briggs and Chow's priority coloring.  The function
1868    returns nonzero if we generates loop structure (besides node
1869    representing all function) for regional allocation.  */
1870 int
1871 ira_build (int loops_p)
1872 {
1873   unsigned int i;
1874   loop_p loop;
1875
1876   df_analyze ();
1877
1878   CLEAR_HARD_REG_SET (cfun->emit->call_used_regs);
1879   initiate_calls ();
1880   initiate_allocnos ();
1881   initiate_copies ();
1882   ira_assert (current_loops == NULL);
1883   flow_loops_find (&ira_loops);
1884   current_loops = &ira_loops;
1885   create_loop_tree_nodes (loops_p);
1886   form_loop_tree ();
1887   create_allocnos ();
1888   ira_costs ();
1889   if (flag_ira_algorithm == IRA_ALGORITHM_REGIONAL
1890       || flag_ira_algorithm == IRA_ALGORITHM_MIXED)
1891     {
1892       local_allocnos_bitmap = ira_allocate_bitmap ();
1893       traverse_loop_tree (FALSE, ira_loop_tree_root, NULL,
1894                           create_loop_tree_node_caps);
1895       ira_free_bitmap (local_allocnos_bitmap);
1896     }
1897   create_allocno_live_ranges ();
1898   ira_build_conflicts ();
1899   if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
1900     {
1901       int i, n, nr;
1902       allocno_live_range_t r;
1903
1904       for (nr = n = i = 0; i < allocnos_num; i++)
1905           n += ALLOCNO_TOTAL_CONFLICT_ALLOCNOS_NUM (allocnos [i]);
1906       for (nr = i = 0; i < allocnos_num; i++)
1907         for (r = ALLOCNO_LIVE_RANGES (allocnos [i]); r != NULL; r = r->next)
1908             nr++;
1909       fprintf (ira_dump_file, "  regions=%d, blocks=%d, points=%d\n",
1910                VEC_length (loop_p, ira_loops.larray), n_basic_blocks,
1911                max_point);
1912       fprintf (ira_dump_file,
1913                "    allocnos=%d, copies=%d, conflicts=%d, ranges=%d\n",
1914                allocnos_num, copies_num, n, nr);
1915     }
1916   if (flag_ira_algorithm == IRA_ALGORITHM_REGIONAL
1917       || flag_ira_algorithm == IRA_ALGORITHM_MIXED)
1918     traverse_loop_tree (FALSE, ira_loop_tree_root, NULL,
1919                         propagate_info_to_loop_tree_node_caps);
1920   tune_allocno_costs_and_cover_classes ();
1921   if (flag_ira_algorithm == IRA_ALGORITHM_REGIONAL
1922       || flag_ira_algorithm == IRA_ALGORITHM_MIXED)
1923     {
1924       for (i = 0; VEC_iterate (loop_p, ira_loops.larray, i, loop); i++)
1925         if (ira_loop_nodes [i].regno_allocno_map != NULL
1926             && ira_loop_tree_root != &ira_loop_nodes [i])
1927           return TRUE;
1928     }
1929   return FALSE;
1930 }
1931
1932 /* The function releases data created by function ira_build.  */
1933 void
1934 ira_destroy (void)
1935 {
1936   basic_block bb;
1937
1938   finish_loop_tree_nodes ();
1939 #if 0
1940   ira_assert  (current_loops == &ira_loops);
1941 #endif
1942   flow_loops_free (&ira_loops);
1943   free_dominance_info (CDI_DOMINATORS);
1944   FOR_ALL_BB (bb)
1945     bb->loop_father = NULL;
1946   current_loops = NULL;
1947   finish_copies ();
1948   finish_allocnos ();
1949   finish_calls ();
1950   finish_allocno_live_ranges ();
1951 }