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