gcc/ira-emit.c

   1 /* Integrated Register Allocator.  Changing code and generating moves.
   2    Copyright (C) 2006, 2007, 2008, 2009, 2010, 2011
   3    Free Software Foundation, Inc.
   4    Contributed by Vladimir Makarov <vmakarov@redhat.com>.
   5
   6 This file is part of GCC.
   7
   8 GCC is free software; you can redistribute it and/or modify it under
   9 the terms of the GNU General Public License as published by the Free
  10 Software Foundation; either version 3, or (at your option) any later
  11 version.
  12
  13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  15 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  16 for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with GCC; see the file COPYING3.  If not see
  20 <http://www.gnu.org/licenses/>.  */
  21
  22 /* When we have more one region, we need to change the original RTL
  23    code after coloring.  Let us consider two allocnos representing the
  24    same pseudo-register outside and inside a region respectively.
  25    They can get different hard-registers.  The reload pass works on
  26    pseudo registers basis and there is no way to say the reload that
  27    pseudo could be in different registers and it is even more
  28    difficult to say in what places of the code the pseudo should have
  29    particular hard-registers.  So in this case IRA has to create and
  30    use a new pseudo-register inside the region and adds code to move
  31    allocno values on the region's borders.  This is done by the code
  32    in this file.
  33
  34    The code makes top-down traversal of the regions and generate new
  35    pseudos and the move code on the region borders.  In some
  36    complicated cases IRA can create a new pseudo used temporarily to
  37    move allocno values when a swap of values stored in two
  38    hard-registers is needed (e.g. two allocnos representing different
  39    pseudos outside region got respectively hard registers 1 and 2 and
  40    the corresponding allocnos inside the region got respectively hard
  41    registers 2 and 1).  At this stage, the new pseudo is marked as
  42    spilled.
  43
  44    IRA still creates the pseudo-register and the moves on the region
  45    borders even when the both corresponding allocnos were assigned to
  46    the same hard-register.  It is done because, if the reload pass for
  47    some reason spills a pseudo-register representing the original
  48    pseudo outside or inside the region, the effect will be smaller
  49    because another pseudo will still be in the hard-register.  In most
  50    cases, this is better then spilling the original pseudo in its
  51    whole live-range.  If reload does not change the allocation for the
  52    two pseudo-registers, the trivial move will be removed by
  53    post-reload optimizations.
  54
  55    IRA does not generate a new pseudo and moves for the allocno values
  56    if the both allocnos representing an original pseudo inside and
  57    outside region assigned to the same hard register when the register
  58    pressure in the region for the corresponding pressure class is less
  59    than number of available hard registers for given pressure class.
  60
  61    IRA also does some optimizations to remove redundant moves which is
  62    transformed into stores by the reload pass on CFG edges
  63    representing exits from the region.
  64
  65    IRA tries to reduce duplication of code generated on CFG edges
  66    which are enters and exits to/from regions by moving some code to
  67    the edge sources or destinations when it is possible.  */
  68
  69 #include "config.h"
  70 #include "system.h"
  71 #include "coretypes.h"
  72 #include "tm.h"
  73 #include "regs.h"
  74 #include "rtl.h"
  75 #include "tm_p.h"
  76 #include "target.h"
  77 #include "flags.h"
  78 #include "obstack.h"
  79 #include "bitmap.h"
  80 #include "hard-reg-set.h"
  81 #include "basic-block.h"
  82 #include "expr.h"
  83 #include "recog.h"
  84 #include "params.h"
  85 #include "timevar.h"
  86 #include "tree-pass.h"
  87 #include "output.h"
  88 #include "reload.h"
  89 #include "df.h"
  90 #include "ira-int.h"
  91
  92
  93 /* Data used to emit live range split insns and to flattening IR.  */
  94 ira_emit_data_t ira_allocno_emit_data;
  95
  96 /* Definitions for vectors of pointers.  */
  97 typedef void *void_p;
  98 DEF_VEC_P (void_p);
  99 DEF_VEC_ALLOC_P (void_p,heap);
 100
 101 /* Pointers to data allocated for allocnos being created during
 102    emitting.  Usually there are quite few such allocnos because they
 103    are created only for resolving loop in register shuffling.  */
 104 static VEC(void_p, heap) *new_allocno_emit_data_vec;
 105
 106 /* Allocate and initiate the emit data.  */
 107 void
 108 ira_initiate_emit_data (void)
 109 {
 110   ira_allocno_t a;
 111   ira_allocno_iterator ai;
 112
 113   ira_allocno_emit_data
 114     = (ira_emit_data_t) ira_allocate (ira_allocnos_num
 115                                       * sizeof (struct ira_emit_data));
 116   memset (ira_allocno_emit_data, 0,
 117           ira_allocnos_num * sizeof (struct ira_emit_data));
 118   FOR_EACH_ALLOCNO (a, ai)
 119     ALLOCNO_ADD_DATA (a) = ira_allocno_emit_data + ALLOCNO_NUM (a);
 120   new_allocno_emit_data_vec = VEC_alloc (void_p, heap, 50);
 121
 122 }
 123
 124 /* Free the emit data.  */
 125 void
 126 ira_finish_emit_data (void)
 127 {
 128   void_p p;
 129   ira_allocno_t a;
 130   ira_allocno_iterator ai;
 131
 132   ira_free (ira_allocno_emit_data);
 133   FOR_EACH_ALLOCNO (a, ai)
 134     ALLOCNO_ADD_DATA (a) = NULL;
 135   for (;VEC_length (void_p, new_allocno_emit_data_vec) != 0;)
 136     {
 137       p = VEC_pop (void_p, new_allocno_emit_data_vec);
 138       ira_free (p);
 139     }
 140   VEC_free (void_p, heap, new_allocno_emit_data_vec);
 141 }
 142
 143 /* Create and return a new allocno with given REGNO and
 144    LOOP_TREE_NODE.  Allocate emit data for it.  */
 145 static ira_allocno_t
 146 create_new_allocno (int regno, ira_loop_tree_node_t loop_tree_node)
 147 {
 148   ira_allocno_t a;
 149
 150   a = ira_create_allocno (regno, false, loop_tree_node);
 151   ALLOCNO_ADD_DATA (a) = ira_allocate (sizeof (struct ira_emit_data));
 152   memset (ALLOCNO_ADD_DATA (a), 0, sizeof (struct ira_emit_data));
 153   VEC_safe_push (void_p, heap, new_allocno_emit_data_vec, ALLOCNO_ADD_DATA (a));
 154   return a;
 155 }
 156
 157 \f
 158
 159 /* See comments below.  */
 160 typedef struct move *move_t;
 161
 162 /* The structure represents an allocno move.  Both allocnos have the
 163    same origional regno but different allocation.  */
 164 struct move
 165 {
 166   /* The allocnos involved in the move.  */
 167   ira_allocno_t from, to;
 168   /* The next move in the move sequence.  */
 169   move_t next;
 170   /* Used for finding dependencies.  */
 171   bool visited_p;
 172   /* The size of the following array. */
 173   int deps_num;
 174   /* Moves on which given move depends on.  Dependency can be cyclic.
 175      It means we need a temporary to generates the moves.  Sequence
 176      A1->A2, B1->B2 where A1 and B2 are assigned to reg R1 and A2 and
 177      B1 are assigned to reg R2 is an example of the cyclic
 178      dependencies.  */
 179   move_t *deps;
 180   /* First insn generated for the move.  */
 181   rtx insn;
 182 };
 183
 184 /* Array of moves (indexed by BB index) which should be put at the
 185    start/end of the corresponding basic blocks.  */
 186 static move_t *at_bb_start, *at_bb_end;
 187
 188 /* Max regno before renaming some pseudo-registers.  For example, the
 189    same pseudo-register can be renamed in a loop if its allocation is
 190    different outside the loop.  */
 191 static int max_regno_before_changing;
 192
 193 /* Return new move of allocnos TO and FROM.  */
 194 static move_t
 195 create_move (ira_allocno_t to, ira_allocno_t from)
 196 {
 197   move_t move;
 198
 199   move = (move_t) ira_allocate (sizeof (struct move));
 200   move->deps = NULL;
 201   move->deps_num = 0;
 202   move->to = to;
 203   move->from = from;
 204   move->next = NULL;
 205   move->insn = NULL_RTX;
 206   move->visited_p = false;
 207   return move;
 208 }
 209
 210 /* Free memory for MOVE and its dependencies.  */
 211 static void
 212 free_move (move_t move)
 213 {
 214   if (move->deps != NULL)
 215     ira_free (move->deps);
 216   ira_free (move);
 217 }
 218
 219 /* Free memory for list of the moves given by its HEAD.  */
 220 static void
 221 free_move_list (move_t head)
 222 {
 223   move_t next;
 224
 225   for (; head != NULL; head = next)
 226     {
 227       next = head->next;
 228       free_move (head);
 229     }
 230 }
 231
 232 /* Return TRUE if the move list LIST1 and LIST2 are equal (two
 233    moves are equal if they involve the same allocnos).  */
 234 static bool
 235 eq_move_lists_p (move_t list1, move_t list2)
 236 {
 237   for (; list1 != NULL && list2 != NULL;
 238        list1 = list1->next, list2 = list2->next)
 239     if (list1->from != list2->from || list1->to != list2->to)
 240       return false;
 241   return list1 == list2;
 242 }
 243
 244 /* Print move list LIST into file F.  */
 245 static void
 246 print_move_list (FILE *f, move_t list)
 247 {
 248   for (; list != NULL; list = list->next)
 249     fprintf (f, " a%dr%d->a%dr%d",
 250              ALLOCNO_NUM (list->from), ALLOCNO_REGNO (list->from),
 251              ALLOCNO_NUM (list->to), ALLOCNO_REGNO (list->to));
 252   fprintf (f, "\n");
 253 }
 254
 255 extern void ira_debug_move_list (move_t list);
 256
 257 /* Print move list LIST into stderr.  */
 258 void
 259 ira_debug_move_list (move_t list)
 260 {
 261   print_move_list (stderr, list);
 262 }
 263
 264 /* This recursive function changes pseudo-registers in *LOC if it is
 265    necessary.  The function returns TRUE if a change was done.  */
 266 static bool
 267 change_regs (rtx *loc)
 268 {
 269   int i, regno, result = false;
 270   const char *fmt;
 271   enum rtx_code code;
 272   rtx reg;
 273
 274   if (*loc == NULL_RTX)
 275     return false;
 276   code = GET_CODE (*loc);
 277   if (code == REG)
 278     {
 279       regno = REGNO (*loc);
 280       if (regno < FIRST_PSEUDO_REGISTER)
 281         return false;
 282       if (regno >= max_regno_before_changing)
 283         /* It is a shared register which was changed already.  */
 284         return false;
 285       if (ira_curr_regno_allocno_map[regno] == NULL)
 286         return false;
 287       reg = allocno_emit_reg (ira_curr_regno_allocno_map[regno]);
 288       if (reg == *loc)
 289         return false;
 290       *loc = reg;
 291       return true;
 292     }
 293
 294   fmt = GET_RTX_FORMAT (code);
 295   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
 296     {
 297       if (fmt[i] == 'e')
 298         result = change_regs (&XEXP (*loc, i)) || result;
 299       else if (fmt[i] == 'E')
 300         {
 301           int j;
 302
 303           for (j = XVECLEN (*loc, i) - 1; j >= 0; j--)
 304             result = change_regs (&XVECEXP (*loc, i, j)) || result;
 305         }
 306     }
 307   return result;
 308 }
 309
 310 /* Attach MOVE to the edge E.  The move is attached to the head of the
 311    list if HEAD_P is TRUE.  */
 312 static void
 313 add_to_edge_list (edge e, move_t move, bool head_p)
 314 {
 315   move_t last;
 316
 317   if (head_p || e->aux == NULL)
 318     {
 319       move->next = (move_t) e->aux;
 320       e->aux = move;
 321     }
 322   else
 323     {
 324       for (last = (move_t) e->aux; last->next != NULL; last = last->next)
 325         ;
 326       last->next = move;
 327       move->next = NULL;
 328     }
 329 }
 330
 331 /* Create and return new pseudo-register with the same attributes as
 332    ORIGINAL_REG.  */
 333 static rtx
 334 create_new_reg (rtx original_reg)
 335 {
 336   rtx new_reg;
 337
 338   new_reg = gen_reg_rtx (GET_MODE (original_reg));
 339   ORIGINAL_REGNO (new_reg) = ORIGINAL_REGNO (original_reg);
 340   REG_USERVAR_P (new_reg) = REG_USERVAR_P (original_reg);
 341   REG_POINTER (new_reg) = REG_POINTER (original_reg);
 342   REG_ATTRS (new_reg) = REG_ATTRS (original_reg);
 343   if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
 344     fprintf (ira_dump_file, "      Creating newreg=%i from oldreg=%i\n",
 345              REGNO (new_reg), REGNO (original_reg));
 346   return new_reg;
 347 }
 348
 349 /* Return TRUE if loop given by SUBNODE inside the loop given by
 350    NODE.  */
 351 static bool
 352 subloop_tree_node_p (ira_loop_tree_node_t subnode, ira_loop_tree_node_t node)
 353 {
 354   for (; subnode != NULL; subnode = subnode->parent)
 355     if (subnode == node)
 356       return true;
 357   return false;
 358 }
 359
 360 /* Set up member `reg' to REG for allocnos which has the same regno as
 361    ALLOCNO and which are inside the loop corresponding to ALLOCNO. */
 362 static void
 363 set_allocno_reg (ira_allocno_t allocno, rtx reg)
 364 {
 365   int regno;
 366   ira_allocno_t a;
 367   ira_loop_tree_node_t node;
 368
 369   node = ALLOCNO_LOOP_TREE_NODE (allocno);
 370   for (a = ira_regno_allocno_map[ALLOCNO_REGNO (allocno)];
 371        a != NULL;
 372        a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
 373     if (subloop_tree_node_p (ALLOCNO_LOOP_TREE_NODE (a), node))
 374       ALLOCNO_EMIT_DATA (a)->reg = reg;
 375   for (a = ALLOCNO_CAP (allocno); a != NULL; a = ALLOCNO_CAP (a))
 376     ALLOCNO_EMIT_DATA (a)->reg = reg;
 377   regno = ALLOCNO_REGNO (allocno);
 378   for (a = allocno;;)
 379     {
 380       if (a == NULL || (a = ALLOCNO_CAP (a)) == NULL)
 381         {
 382           node = node->parent;
 383           if (node == NULL)
 384             break;
 385           a = node->regno_allocno_map[regno];
 386         }
 387       if (a == NULL)
 388         continue;
 389       if (ALLOCNO_EMIT_DATA (a)->child_renamed_p)
 390         break;
 391       ALLOCNO_EMIT_DATA (a)->child_renamed_p = true;
 392     }
 393 }
 394
 395 /* Return true if there is an entry to given loop not from its parent
 396    (or grandparent) block.  For example, it is possible for two
 397    adjacent loops inside another loop.  */
 398 static bool
 399 entered_from_non_parent_p (ira_loop_tree_node_t loop_node)
 400 {
 401   ira_loop_tree_node_t bb_node, src_loop_node, parent;
 402   edge e;
 403   edge_iterator ei;
 404
 405   for (bb_node = loop_node->children;
 406        bb_node != NULL;
 407        bb_node = bb_node->next)
 408     if (bb_node->bb != NULL)
 409       {
 410         FOR_EACH_EDGE (e, ei, bb_node->bb->preds)
 411           if (e->src != ENTRY_BLOCK_PTR
 412               && (src_loop_node = IRA_BB_NODE (e->src)->parent) != loop_node)
 413             {
 414               for (parent = src_loop_node->parent;
 415                    parent != NULL;
 416                    parent = parent->parent)
 417                 if (parent == loop_node)
 418                   break;
 419               if (parent != NULL)
 420                 /* That is an exit from a nested loop -- skip it.  */
 421                 continue;
 422               for (parent = loop_node->parent;
 423                    parent != NULL;
 424                    parent = parent->parent)
 425                 if (src_loop_node == parent)
 426                   break;
 427               if (parent == NULL)
 428                 return true;
 429             }
 430       }
 431   return false;
 432 }
 433
 434 /* Set up ENTERED_FROM_NON_PARENT_P for each loop region.  */
 435 static void
 436 setup_entered_from_non_parent_p (void)
 437 {
 438   unsigned int i;
 439   loop_p loop;
 440
 441   FOR_EACH_VEC_ELT (loop_p, ira_loops.larray, i, loop)
 442     if (ira_loop_nodes[i].regno_allocno_map != NULL)
 443       ira_loop_nodes[i].entered_from_non_parent_p
 444         = entered_from_non_parent_p (&ira_loop_nodes[i]);
 445 }
 446
 447 /* Return TRUE if move of SRC_ALLOCNO (assigned to hard register) to
 448    DEST_ALLOCNO (assigned to memory) can be removed beacuse it does
 449    not change value of the destination.  One possible reason for this
 450    is the situation when SRC_ALLOCNO is not modified in the
 451    corresponding loop.  */
 452 static bool
 453 store_can_be_removed_p (ira_allocno_t src_allocno, ira_allocno_t dest_allocno)
 454 {
 455   int regno, orig_regno;
 456   ira_allocno_t a;
 457   ira_loop_tree_node_t node;
 458
 459   ira_assert (ALLOCNO_CAP_MEMBER (src_allocno) == NULL
 460               && ALLOCNO_CAP_MEMBER (dest_allocno) == NULL);
 461   orig_regno = ALLOCNO_REGNO (src_allocno);
 462   regno = REGNO (allocno_emit_reg (dest_allocno));
 463   for (node = ALLOCNO_LOOP_TREE_NODE (src_allocno);
 464        node != NULL;
 465        node = node->parent)
 466     {
 467       a = node->regno_allocno_map[orig_regno];
 468       ira_assert (a != NULL);
 469       if (REGNO (allocno_emit_reg (a)) == (unsigned) regno)
 470         /* We achieved the destination and everything is ok.  */
 471         return true;
 472       else if (bitmap_bit_p (node->modified_regnos, orig_regno))
 473         return false;
 474       else if (node->entered_from_non_parent_p)
 475         /* If there is a path from a destination loop block to the
 476            source loop header containing basic blocks of non-parents
 477            (grandparents) of the source loop, we should have checked
 478            modifications of the pseudo on this path too to decide
 479            about possibility to remove the store.  It could be done by
 480            solving a data-flow problem.  Unfortunately such global
 481            solution would complicate IR flattening.  Therefore we just
 482            prohibit removal of the store in such complicated case.  */
 483         return false;
 484     }
 485   /* It is actually a loop entry -- do not remove the store.  */
 486   return false;
 487 }
 488
 489 /* Generate and attach moves to the edge E.  This looks at the final
 490    regnos of allocnos living on the edge with the same original regno
 491    to figure out when moves should be generated.  */
 492 static void
 493 generate_edge_moves (edge e)
 494 {
 495   ira_loop_tree_node_t src_loop_node, dest_loop_node;
 496   unsigned int regno;
 497   bitmap_iterator bi;
 498   ira_allocno_t src_allocno, dest_allocno, *src_map, *dest_map;
 499   move_t move;
 500
 501   src_loop_node = IRA_BB_NODE (e->src)->parent;
 502   dest_loop_node = IRA_BB_NODE (e->dest)->parent;
 503   e->aux = NULL;
 504   if (src_loop_node == dest_loop_node)
 505     return;
 506   src_map = src_loop_node->regno_allocno_map;
 507   dest_map = dest_loop_node->regno_allocno_map;
 508   EXECUTE_IF_SET_IN_REG_SET (DF_LR_IN (e->dest),
 509                              FIRST_PSEUDO_REGISTER, regno, bi)
 510     if (bitmap_bit_p (DF_LR_OUT (e->src), regno))
 511       {
 512         src_allocno = src_map[regno];
 513         dest_allocno = dest_map[regno];
 514         if (REGNO (allocno_emit_reg (src_allocno))
 515             == REGNO (allocno_emit_reg (dest_allocno)))
 516           continue;
 517         /* Remove unnecessary stores at the region exit.  We should do
 518            this for readonly memory for sure and this is guaranteed by
 519            that we never generate moves on region borders (see
 520            checking ira_reg_equiv_invariant_p in function
 521            change_loop).  */
 522         if (ALLOCNO_HARD_REGNO (dest_allocno) < 0
 523             && ALLOCNO_HARD_REGNO (src_allocno) >= 0
 524             && store_can_be_removed_p (src_allocno, dest_allocno))
 525           {
 526             ALLOCNO_EMIT_DATA (src_allocno)->mem_optimized_dest = dest_allocno;
 527             ALLOCNO_EMIT_DATA (dest_allocno)->mem_optimized_dest_p = true;
 528             if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
 529               fprintf (ira_dump_file, "      Remove r%d:a%d->a%d(mem)\n",
 530                        regno, ALLOCNO_NUM (src_allocno),
 531                        ALLOCNO_NUM (dest_allocno));
 532             continue;
 533           }
 534         move = create_move (dest_allocno, src_allocno);
 535         add_to_edge_list (e, move, true);
 536     }
 537 }
 538
 539 /* Bitmap of allocnos local for the current loop.  */
 540 static bitmap local_allocno_bitmap;
 541
 542 /* This bitmap is used to find that we need to generate and to use a
 543    new pseudo-register when processing allocnos with the same original
 544    regno.  */
 545 static bitmap used_regno_bitmap;
 546
 547 /* This bitmap contains regnos of allocnos which were renamed locally
 548    because the allocnos correspond to disjoint live ranges in loops
 549    with a common parent.  */
 550 static bitmap renamed_regno_bitmap;
 551
 552 /* Change (if necessary) pseudo-registers inside loop given by loop
 553    tree node NODE.  */
 554 static void
 555 change_loop (ira_loop_tree_node_t node)
 556 {
 557   bitmap_iterator bi;
 558   unsigned int i;
 559   int regno;
 560   bool used_p;
 561   ira_allocno_t allocno, parent_allocno, *map;
 562   rtx insn, original_reg;
 563   enum reg_class aclass, pclass;
 564   ira_loop_tree_node_t parent;
 565
 566   if (node != ira_loop_tree_root)
 567     {
 568
 569       if (node->bb != NULL)
 570         {
 571           FOR_BB_INSNS (node->bb, insn)
 572             if (INSN_P (insn) && change_regs (&insn))
 573               {
 574                 df_insn_rescan (insn);
 575                 df_notes_rescan (insn);
 576               }
 577           return;
 578         }
 579
 580       if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
 581         fprintf (ira_dump_file,
 582                  "      Changing RTL for loop %d (header bb%d)\n",
 583                  node->loop->num, node->loop->header->index);
 584
 585       parent = ira_curr_loop_tree_node->parent;
 586       map = parent->regno_allocno_map;
 587       EXECUTE_IF_SET_IN_REG_SET (ira_curr_loop_tree_node->border_allocnos,
 588                                  0, i, bi)
 589         {
 590           allocno = ira_allocnos[i];
 591           regno = ALLOCNO_REGNO (allocno);
 592           aclass = ALLOCNO_CLASS (allocno);
 593           pclass = ira_pressure_class_translate[aclass];
 594           parent_allocno = map[regno];
 595           ira_assert (regno < ira_reg_equiv_len);
 596           /* We generate the same hard register move because the
 597              reload pass can put an allocno into memory in this case
 598              we will have live range splitting.  If it does not happen
 599              such the same hard register moves will be removed.  The
 600              worst case when the both allocnos are put into memory by
 601              the reload is very rare.  */
 602           if (parent_allocno != NULL
 603               && (ALLOCNO_HARD_REGNO (allocno)
 604                   == ALLOCNO_HARD_REGNO (parent_allocno))
 605               && (ALLOCNO_HARD_REGNO (allocno) < 0
 606                   || (parent->reg_pressure[pclass] + 1
 607                       <= ira_available_class_regs[pclass])
 608                   || TEST_HARD_REG_BIT (ira_prohibited_mode_move_regs
 609                                         [ALLOCNO_MODE (allocno)],
 610                                         ALLOCNO_HARD_REGNO (allocno))
 611                   /* don't create copies because reload can spill an
 612                      allocno set by copy although the allocno will not
 613                      get memory slot.  */
 614                   || ira_reg_equiv_invariant_p[regno]
 615                   || ira_reg_equiv_const[regno] != NULL_RTX))
 616             continue;
 617           original_reg = allocno_emit_reg (allocno);
 618           if (parent_allocno == NULL
 619               || (REGNO (allocno_emit_reg (parent_allocno))
 620                   == REGNO (original_reg)))
 621             {
 622               if (internal_flag_ira_verbose > 3 && ira_dump_file)
 623                 fprintf (ira_dump_file, "  %i vs parent %i:",
 624                          ALLOCNO_HARD_REGNO (allocno),
 625                          ALLOCNO_HARD_REGNO (parent_allocno));
 626               set_allocno_reg (allocno, create_new_reg (original_reg));
 627             }
 628         }
 629     }
 630   /* Rename locals: Local allocnos with same regno in different loops
 631      might get the different hard register.  So we need to change
 632      ALLOCNO_REG.  */
 633   bitmap_and_compl (local_allocno_bitmap,
 634                     ira_curr_loop_tree_node->all_allocnos,
 635                     ira_curr_loop_tree_node->border_allocnos);
 636   EXECUTE_IF_SET_IN_REG_SET (local_allocno_bitmap, 0, i, bi)
 637     {
 638       allocno = ira_allocnos[i];
 639       regno = ALLOCNO_REGNO (allocno);
 640       if (ALLOCNO_CAP_MEMBER (allocno) != NULL)
 641         continue;
 642       used_p = !bitmap_set_bit (used_regno_bitmap, regno);
 643       ALLOCNO_EMIT_DATA (allocno)->somewhere_renamed_p = true;
 644       if (! used_p)
 645         continue;
 646       bitmap_set_bit (renamed_regno_bitmap, regno);
 647       set_allocno_reg (allocno, create_new_reg (allocno_emit_reg (allocno)));
 648     }
 649 }
 650
 651 /* Process to set up flag somewhere_renamed_p.  */
 652 static void
 653 set_allocno_somewhere_renamed_p (void)
 654 {
 655   unsigned int regno;
 656   ira_allocno_t allocno;
 657   ira_allocno_iterator ai;
 658
 659   FOR_EACH_ALLOCNO (allocno, ai)
 660     {
 661       regno = ALLOCNO_REGNO (allocno);
 662       if (bitmap_bit_p (renamed_regno_bitmap, regno)
 663           && REGNO (allocno_emit_reg (allocno)) == regno)
 664         ALLOCNO_EMIT_DATA (allocno)->somewhere_renamed_p = true;
 665     }
 666 }
 667
 668 /* Return TRUE if move lists on all edges given in vector VEC are
 669    equal.  */
 670 static bool
 671 eq_edge_move_lists_p (VEC(edge,gc) *vec)
 672 {
 673   move_t list;
 674   int i;
 675
 676   list = (move_t) EDGE_I (vec, 0)->aux;
 677   for (i = EDGE_COUNT (vec) - 1; i > 0; i--)
 678     if (! eq_move_lists_p (list, (move_t) EDGE_I (vec, i)->aux))
 679       return false;
 680   return true;
 681 }
 682
 683 /* Look at all entry edges (if START_P) or exit edges of basic block
 684    BB and put move lists at the BB start or end if it is possible.  In
 685    other words, this decreases code duplication of allocno moves.  */
 686 static void
 687 unify_moves (basic_block bb, bool start_p)
 688 {
 689   int i;
 690   edge e;
 691   move_t list;
 692   VEC(edge,gc) *vec;
 693
 694   vec = (start_p ? bb->preds : bb->succs);
 695   if (EDGE_COUNT (vec) == 0 || ! eq_edge_move_lists_p (vec))
 696     return;
 697   e = EDGE_I (vec, 0);
 698   list = (move_t) e->aux;
 699   if (! start_p && control_flow_insn_p (BB_END (bb)))
 700     return;
 701   e->aux = NULL;
 702   for (i = EDGE_COUNT (vec) - 1; i > 0; i--)
 703     {
 704       e = EDGE_I (vec, i);
 705       free_move_list ((move_t) e->aux);
 706       e->aux = NULL;
 707     }
 708   if (start_p)
 709     at_bb_start[bb->index] = list;
 710   else
 711     at_bb_end[bb->index] = list;
 712 }
 713
 714 /* Last move (in move sequence being processed) setting up the
 715    corresponding hard register.  */
 716 static move_t hard_regno_last_set[FIRST_PSEUDO_REGISTER];
 717
 718 /* If the element value is equal to CURR_TICK then the corresponding
 719    element in `hard_regno_last_set' is defined and correct.  */
 720 static int hard_regno_last_set_check[FIRST_PSEUDO_REGISTER];
 721
 722 /* Last move (in move sequence being processed) setting up the
 723    corresponding allocno.  */
 724 static move_t *allocno_last_set;
 725
 726 /* If the element value is equal to CURR_TICK then the corresponding
 727    element in . `allocno_last_set' is defined and correct.  */
 728 static int *allocno_last_set_check;
 729
 730 /* Definition of vector of moves.  */
 731 DEF_VEC_P(move_t);
 732 DEF_VEC_ALLOC_P(move_t, heap);
 733
 734 /* This vec contains moves sorted topologically (depth-first) on their
 735    dependency graph.  */
 736 static VEC(move_t,heap) *move_vec;
 737
 738 /* The variable value is used to check correctness of values of
 739    elements of arrays `hard_regno_last_set' and
 740    `allocno_last_set_check'.  */
 741 static int curr_tick;
 742
 743 /* This recursive function traverses dependencies of MOVE and produces
 744    topological sorting (in depth-first order).  */
 745 static void
 746 traverse_moves (move_t move)
 747 {
 748   int i;
 749
 750   if (move->visited_p)
 751     return;
 752   move->visited_p = true;
 753   for (i = move->deps_num - 1; i >= 0; i--)
 754     traverse_moves (move->deps[i]);
 755   VEC_safe_push (move_t, heap, move_vec, move);
 756 }
 757
 758 /* Remove unnecessary moves in the LIST, makes topological sorting,
 759    and removes cycles on hard reg dependencies by introducing new
 760    allocnos assigned to memory and additional moves.  It returns the
 761    result move list.  */
 762 static move_t
 763 modify_move_list (move_t list)
 764 {
 765   int i, n, nregs, hard_regno;
 766   ira_allocno_t to, from;
 767   move_t move, new_move, set_move, first, last;
 768
 769   if (list == NULL)
 770     return NULL;
 771   /* Creat move deps.  */
 772   curr_tick++;
 773   for (move = list; move != NULL; move = move->next)
 774     {
 775       to = move->to;
 776       if ((hard_regno = ALLOCNO_HARD_REGNO (to)) < 0)
 777         continue;
 778       nregs = hard_regno_nregs[hard_regno][ALLOCNO_MODE (to)];
 779       for (i = 0; i < nregs; i++)
 780         {
 781           hard_regno_last_set[hard_regno + i] = move;
 782           hard_regno_last_set_check[hard_regno + i] = curr_tick;
 783         }
 784     }
 785   for (move = list; move != NULL; move = move->next)
 786     {
 787       from = move->from;
 788       to = move->to;
 789       if ((hard_regno = ALLOCNO_HARD_REGNO (from)) >= 0)
 790         {
 791           nregs = hard_regno_nregs[hard_regno][ALLOCNO_MODE (from)];
 792           for (n = i = 0; i < nregs; i++)
 793             if (hard_regno_last_set_check[hard_regno + i] == curr_tick
 794                 && (ALLOCNO_REGNO (hard_regno_last_set[hard_regno + i]->to)
 795                     != ALLOCNO_REGNO (from)))
 796               n++;
 797           move->deps = (move_t *) ira_allocate (n * sizeof (move_t));
 798           for (n = i = 0; i < nregs; i++)
 799             if (hard_regno_last_set_check[hard_regno + i] == curr_tick
 800                 && (ALLOCNO_REGNO (hard_regno_last_set[hard_regno + i]->to)
 801                     != ALLOCNO_REGNO (from)))
 802               move->deps[n++] = hard_regno_last_set[hard_regno + i];
 803           move->deps_num = n;
 804         }
 805     }
 806   /* Toplogical sorting:  */
 807   VEC_truncate (move_t, move_vec, 0);
 808   for (move = list; move != NULL; move = move->next)
 809     traverse_moves (move);
 810   last = NULL;
 811   for (i = (int) VEC_length (move_t, move_vec) - 1; i >= 0; i--)
 812     {
 813       move = VEC_index (move_t, move_vec, i);
 814       move->next = NULL;
 815       if (last != NULL)
 816         last->next = move;
 817       last = move;
 818     }
 819   first = VEC_last (move_t, move_vec);
 820   /* Removing cycles:  */
 821   curr_tick++;
 822   VEC_truncate (move_t, move_vec, 0);
 823   for (move = first; move != NULL; move = move->next)
 824     {
 825       from = move->from;
 826       to = move->to;
 827       if ((hard_regno = ALLOCNO_HARD_REGNO (from)) >= 0)
 828         {
 829           nregs = hard_regno_nregs[hard_regno][ALLOCNO_MODE (from)];
 830           for (i = 0; i < nregs; i++)
 831             if (hard_regno_last_set_check[hard_regno + i] == curr_tick
 832                 && ALLOCNO_HARD_REGNO
 833                    (hard_regno_last_set[hard_regno + i]->to) >= 0)
 834               {
 835                 int n, j;
 836                 ira_allocno_t new_allocno;
 837
 838                 set_move = hard_regno_last_set[hard_regno + i];
 839                 /* It does not matter what loop_tree_node (of TO or
 840                    FROM) to use for the new allocno because of
 841                    subsequent IRA internal representation
 842                    flattening.  */
 843                 new_allocno
 844                   = create_new_allocno (ALLOCNO_REGNO (set_move->to),
 845                                         ALLOCNO_LOOP_TREE_NODE (set_move->to));
 846                 ALLOCNO_MODE (new_allocno) = ALLOCNO_MODE (set_move->to);
 847                 ira_set_allocno_class (new_allocno,
 848                                        ALLOCNO_CLASS (set_move->to));
 849                 ira_create_allocno_objects (new_allocno);
 850                 ALLOCNO_ASSIGNED_P (new_allocno) = true;
 851                 ALLOCNO_HARD_REGNO (new_allocno) = -1;
 852                 ALLOCNO_EMIT_DATA (new_allocno)->reg
 853                   = create_new_reg (allocno_emit_reg (set_move->to));
 854
 855                 /* Make it possibly conflicting with all earlier
 856                    created allocnos.  Cases where temporary allocnos
 857                    created to remove the cycles are quite rare.  */
 858                 n = ALLOCNO_NUM_OBJECTS (new_allocno);
 859                 gcc_assert (n == ALLOCNO_NUM_OBJECTS (set_move->to));
 860                 for (j = 0; j < n; j++)
 861                   {
 862                     ira_object_t new_obj = ALLOCNO_OBJECT (new_allocno, j);
 863
 864                     OBJECT_MIN (new_obj) = 0;
 865                     OBJECT_MAX (new_obj) = ira_objects_num - 1;
 866                   }
 867
 868                 new_move = create_move (set_move->to, new_allocno);
 869                 set_move->to = new_allocno;
 870                 VEC_safe_push (move_t, heap, move_vec, new_move);
 871                 ira_move_loops_num++;
 872                 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
 873                   fprintf (ira_dump_file,
 874                            "    Creating temporary allocno a%dr%d\n",
 875                            ALLOCNO_NUM (new_allocno),
 876                            REGNO (allocno_emit_reg (new_allocno)));
 877               }
 878         }
 879       if ((hard_regno = ALLOCNO_HARD_REGNO (to)) < 0)
 880         continue;
 881       nregs = hard_regno_nregs[hard_regno][ALLOCNO_MODE (to)];
 882       for (i = 0; i < nregs; i++)
 883         {
 884           hard_regno_last_set[hard_regno + i] = move;
 885           hard_regno_last_set_check[hard_regno + i] = curr_tick;
 886         }
 887     }
 888   for (i = (int) VEC_length (move_t, move_vec) - 1; i >= 0; i--)
 889     {
 890       move = VEC_index (move_t, move_vec, i);
 891       move->next = NULL;
 892       last->next = move;
 893       last = move;
 894     }
 895   return first;
 896 }
 897
 898 /* Generate RTX move insns from the move list LIST.  This updates
 899    allocation cost using move execution frequency FREQ.  */
 900 static rtx
 901 emit_move_list (move_t list, int freq)
 902 {
 903   int cost, regno;
 904   rtx result, insn, set, to;
 905   enum machine_mode mode;
 906   enum reg_class aclass;
 907
 908   start_sequence ();
 909   for (; list != NULL; list = list->next)
 910     {
 911       start_sequence ();
 912       emit_move_insn (allocno_emit_reg (list->to),
 913                       allocno_emit_reg (list->from));
 914       list->insn = get_insns ();
 915       end_sequence ();
 916       for (insn = list->insn; insn != NULL_RTX; insn = NEXT_INSN (insn))
 917         {
 918           /* The reload needs to have set up insn codes.  If the
 919              reload sets up insn codes by itself, it may fail because
 920              insns will have hard registers instead of pseudos and
 921              there may be no machine insn with given hard
 922              registers.  */
 923           recog_memoized (insn);
 924           /* Add insn to equiv init insn list if it is necessary.
 925              Otherwise reload will not remove this insn if it decides
 926              to use the equivalence.  */
 927           if ((set = single_set (insn)) != NULL_RTX)
 928             {
 929               to = SET_DEST (set);
 930               if (GET_CODE (to) == SUBREG)
 931                 to = SUBREG_REG (to);
 932               ira_assert (REG_P (to));
 933               regno = REGNO (to);
 934               if (regno >= ira_reg_equiv_len
 935                   || (! ira_reg_equiv_invariant_p[regno]
 936                       && ira_reg_equiv_const[regno] == NULL_RTX))
 937                 continue; /* regno has no equivalence.  */
 938               ira_assert ((int) VEC_length (reg_equivs_t, reg_equivs)
 939                           >= ira_reg_equiv_len);
 940               reg_equiv_init (regno)
 941                 = gen_rtx_INSN_LIST (VOIDmode, insn, reg_equiv_init (regno));
 942             }
 943         }
 944       emit_insn (list->insn);
 945       mode = ALLOCNO_MODE (list->to);
 946       aclass = ALLOCNO_CLASS (list->to);
 947       cost = 0;
 948       if (ALLOCNO_HARD_REGNO (list->to) < 0)
 949         {
 950           if (ALLOCNO_HARD_REGNO (list->from) >= 0)
 951             {
 952               cost = ira_memory_move_cost[mode][aclass][0] * freq;
 953               ira_store_cost += cost;
 954             }
 955         }
 956       else if (ALLOCNO_HARD_REGNO (list->from) < 0)
 957         {
 958           if (ALLOCNO_HARD_REGNO (list->to) >= 0)
 959             {
 960               cost = ira_memory_move_cost[mode][aclass][0] * freq;
 961               ira_load_cost += cost;
 962             }
 963         }
 964       else
 965         {
 966           ira_init_register_move_cost_if_necessary (mode);
 967           cost = ira_register_move_cost[mode][aclass][aclass] * freq;
 968           ira_shuffle_cost += cost;
 969         }
 970       ira_overall_cost += cost;
 971     }
 972   result = get_insns ();
 973   end_sequence ();
 974   return result;
 975 }
 976
 977 /* Generate RTX move insns from move lists attached to basic blocks
 978    and edges.  */
 979 static void
 980 emit_moves (void)
 981 {
 982   basic_block bb;
 983   edge_iterator ei;
 984   edge e;
 985   rtx insns, tmp;
 986
 987   FOR_EACH_BB (bb)
 988     {
 989       if (at_bb_start[bb->index] != NULL)
 990         {
 991           at_bb_start[bb->index] = modify_move_list (at_bb_start[bb->index]);
 992           insns = emit_move_list (at_bb_start[bb->index],
 993                                   REG_FREQ_FROM_BB (bb));
 994           tmp = BB_HEAD (bb);
 995           if (LABEL_P (tmp))
 996             tmp = NEXT_INSN (tmp);
 997           if (NOTE_INSN_BASIC_BLOCK_P (tmp))
 998             tmp = NEXT_INSN (tmp);
 999           if (tmp == BB_HEAD (bb))
1000             emit_insn_before (insns, tmp);
1001           else if (tmp != NULL_RTX)
1002             emit_insn_after (insns, PREV_INSN (tmp));
1003           else
1004             emit_insn_after (insns, get_last_insn ());
1005         }
1006
1007       if (at_bb_end[bb->index] != NULL)
1008         {
1009           at_bb_end[bb->index] = modify_move_list (at_bb_end[bb->index]);
1010           insns = emit_move_list (at_bb_end[bb->index], REG_FREQ_FROM_BB (bb));
1011           ira_assert (! control_flow_insn_p (BB_END (bb)));
1012           emit_insn_after (insns, BB_END (bb));
1013         }
1014
1015       FOR_EACH_EDGE (e, ei, bb->succs)
1016         {
1017           if (e->aux == NULL)
1018             continue;
1019           ira_assert ((e->flags & EDGE_ABNORMAL) == 0
1020                       || ! EDGE_CRITICAL_P (e));
1021           e->aux = modify_move_list ((move_t) e->aux);
1022           insert_insn_on_edge
1023             (emit_move_list ((move_t) e->aux,
1024                              REG_FREQ_FROM_EDGE_FREQ (EDGE_FREQUENCY (e))),
1025              e);
1026           if (e->src->next_bb != e->dest)
1027             ira_additional_jumps_num++;
1028         }
1029     }
1030 }
1031
1032 /* Update costs of A and corresponding allocnos on upper levels on the
1033    loop tree from reading (if READ_P) or writing A on an execution
1034    path with FREQ.  */
1035 static void
1036 update_costs (ira_allocno_t a, bool read_p, int freq)
1037 {
1038   ira_loop_tree_node_t parent;
1039
1040   for (;;)
1041     {
1042       ALLOCNO_NREFS (a)++;
1043       ALLOCNO_FREQ (a) += freq;
1044       ALLOCNO_MEMORY_COST (a)
1045         += (ira_memory_move_cost[ALLOCNO_MODE (a)][ALLOCNO_CLASS (a)]
1046             [read_p ? 1 : 0] * freq);
1047       if (ALLOCNO_CAP (a) != NULL)
1048         a = ALLOCNO_CAP (a);
1049       else if ((parent = ALLOCNO_LOOP_TREE_NODE (a)->parent) == NULL
1050                || (a = parent->regno_allocno_map[ALLOCNO_REGNO (a)]) == NULL)
1051         break;
1052     }
1053 }
1054
1055 /* Process moves from LIST with execution FREQ to add ranges, copies,
1056    and modify costs for allocnos involved in the moves.  All regnos
1057    living through the list is in LIVE_THROUGH, and the loop tree node
1058    used to find corresponding allocnos is NODE.  */
1059 static void
1060 add_range_and_copies_from_move_list (move_t list, ira_loop_tree_node_t node,
1061                                      bitmap live_through, int freq)
1062 {
1063   int start, n;
1064   unsigned int regno;
1065   move_t move;
1066   ira_allocno_t a;
1067   ira_copy_t cp;
1068   live_range_t r;
1069   bitmap_iterator bi;
1070   HARD_REG_SET hard_regs_live;
1071
1072   if (list == NULL)
1073     return;
1074   n = 0;
1075   EXECUTE_IF_SET_IN_BITMAP (live_through, FIRST_PSEUDO_REGISTER, regno, bi)
1076     n++;
1077   REG_SET_TO_HARD_REG_SET (hard_regs_live, live_through);
1078   /* This is a trick to guarantee that new ranges is not merged with
1079      the old ones.  */
1080   ira_max_point++;
1081   start = ira_max_point;
1082   for (move = list; move != NULL; move = move->next)
1083     {
1084       ira_allocno_t from = move->from;
1085       ira_allocno_t to = move->to;
1086       int nr, i;
1087
1088       bitmap_clear_bit (live_through, ALLOCNO_REGNO (from));
1089       bitmap_clear_bit (live_through, ALLOCNO_REGNO (to));
1090
1091       nr = ALLOCNO_NUM_OBJECTS (to);
1092       for (i = 0; i < nr; i++)
1093         {
1094           ira_object_t to_obj = ALLOCNO_OBJECT (to, i);
1095           if (OBJECT_CONFLICT_ARRAY (to_obj) == NULL)
1096             {
1097               if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
1098                 fprintf (ira_dump_file, "    Allocate conflicts for a%dr%d\n",
1099                          ALLOCNO_NUM (to), REGNO (allocno_emit_reg (to)));
1100               ira_allocate_object_conflicts (to_obj, n);
1101             }
1102         }
1103       ior_hard_reg_conflicts (from, &hard_regs_live);
1104       ior_hard_reg_conflicts (to, &hard_regs_live);
1105
1106       update_costs (from, true, freq);
1107       update_costs (to, false, freq);
1108       cp = ira_add_allocno_copy (from, to, freq, false, move->insn, NULL);
1109       if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
1110         fprintf (ira_dump_file, "    Adding cp%d:a%dr%d-a%dr%d\n",
1111                  cp->num, ALLOCNO_NUM (cp->first),
1112                  REGNO (allocno_emit_reg (cp->first)),
1113                  ALLOCNO_NUM (cp->second),
1114                  REGNO (allocno_emit_reg (cp->second)));
1115
1116       nr = ALLOCNO_NUM_OBJECTS (from);
1117       for (i = 0; i < nr; i++)
1118         {
1119           ira_object_t from_obj = ALLOCNO_OBJECT (from, i);
1120           r = OBJECT_LIVE_RANGES (from_obj);
1121           if (r == NULL || r->finish >= 0)
1122             {
1123               ira_add_live_range_to_object (from_obj, start, ira_max_point);
1124               if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
1125                 fprintf (ira_dump_file,
1126                          "    Adding range [%d..%d] to allocno a%dr%d\n",
1127                          start, ira_max_point, ALLOCNO_NUM (from),
1128                          REGNO (allocno_emit_reg (from)));
1129             }
1130           else
1131             {
1132               r->finish = ira_max_point;
1133               if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
1134                 fprintf (ira_dump_file,
1135                          "    Adding range [%d..%d] to allocno a%dr%d\n",
1136                          r->start, ira_max_point, ALLOCNO_NUM (from),
1137                          REGNO (allocno_emit_reg (from)));
1138             }
1139         }
1140       ira_max_point++;
1141       nr = ALLOCNO_NUM_OBJECTS (to);
1142       for (i = 0; i < nr; i++)
1143         {
1144           ira_object_t to_obj = ALLOCNO_OBJECT (to, i);
1145           ira_add_live_range_to_object (to_obj, ira_max_point, -1);
1146         }
1147       ira_max_point++;
1148     }
1149   for (move = list; move != NULL; move = move->next)
1150     {
1151       int nr, i;
1152       nr = ALLOCNO_NUM_OBJECTS (move->to);
1153       for (i = 0; i < nr; i++)
1154         {
1155           ira_object_t to_obj = ALLOCNO_OBJECT (move->to, i);
1156           r = OBJECT_LIVE_RANGES (to_obj);
1157           if (r->finish < 0)
1158             {
1159               r->finish = ira_max_point - 1;
1160               if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
1161                 fprintf (ira_dump_file,
1162                          "    Adding range [%d..%d] to allocno a%dr%d\n",
1163                          r->start, r->finish, ALLOCNO_NUM (move->to),
1164                          REGNO (allocno_emit_reg (move->to)));
1165             }
1166         }
1167     }
1168   EXECUTE_IF_SET_IN_BITMAP (live_through, FIRST_PSEUDO_REGISTER, regno, bi)
1169     {
1170       ira_allocno_t to;
1171       int nr, i;
1172
1173       a = node->regno_allocno_map[regno];
1174       if ((to = ALLOCNO_EMIT_DATA (a)->mem_optimized_dest) != NULL)
1175         a = to;
1176       nr = ALLOCNO_NUM_OBJECTS (a);
1177       for (i = 0; i < nr; i++)
1178         {
1179           ira_object_t obj = ALLOCNO_OBJECT (a, i);
1180           ira_add_live_range_to_object (obj, start, ira_max_point - 1);
1181         }
1182       if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
1183         fprintf
1184           (ira_dump_file,
1185            "    Adding range [%d..%d] to live through %s allocno a%dr%d\n",
1186            start, ira_max_point - 1,
1187            to != NULL ? "upper level" : "",
1188            ALLOCNO_NUM (a), REGNO (allocno_emit_reg (a)));
1189     }
1190 }
1191
1192 /* Process all move list to add ranges, conflicts, copies, and modify
1193    costs for allocnos involved in the moves.  */
1194 static void
1195 add_ranges_and_copies (void)
1196 {
1197   basic_block bb;
1198   edge_iterator ei;
1199   edge e;
1200   ira_loop_tree_node_t node;
1201   bitmap live_through;
1202
1203   live_through = ira_allocate_bitmap ();
1204   FOR_EACH_BB (bb)
1205     {
1206       /* It does not matter what loop_tree_node (of source or
1207          destination block) to use for searching allocnos by their
1208          regnos because of subsequent IR flattening.  */
1209       node = IRA_BB_NODE (bb)->parent;
1210       bitmap_copy (live_through, DF_LR_IN (bb));
1211       add_range_and_copies_from_move_list
1212         (at_bb_start[bb->index], node, live_through, REG_FREQ_FROM_BB (bb));
1213       bitmap_copy (live_through, DF_LR_OUT (bb));
1214       add_range_and_copies_from_move_list
1215         (at_bb_end[bb->index], node, live_through, REG_FREQ_FROM_BB (bb));
1216       FOR_EACH_EDGE (e, ei, bb->succs)
1217         {
1218           bitmap_and (live_through, DF_LR_IN (e->dest), DF_LR_OUT (bb));
1219           add_range_and_copies_from_move_list
1220             ((move_t) e->aux, node, live_through,
1221              REG_FREQ_FROM_EDGE_FREQ (EDGE_FREQUENCY (e)));
1222         }
1223     }
1224   ira_free_bitmap (live_through);
1225 }
1226
1227 /* The entry function changes code and generates shuffling allocnos on
1228    region borders for the regional (LOOPS_P is TRUE in this case)
1229    register allocation.  */
1230 void
1231 ira_emit (bool loops_p)
1232 {
1233   basic_block bb;
1234   rtx insn;
1235   edge_iterator ei;
1236   edge e;
1237   ira_allocno_t a;
1238   ira_allocno_iterator ai;
1239
1240   FOR_EACH_ALLOCNO (a, ai)
1241     ALLOCNO_EMIT_DATA (a)->reg = regno_reg_rtx[ALLOCNO_REGNO (a)];
1242   if (! loops_p)
1243     return;
1244   at_bb_start = (move_t *) ira_allocate (sizeof (move_t) * last_basic_block);
1245   memset (at_bb_start, 0, sizeof (move_t) * last_basic_block);
1246   at_bb_end = (move_t *) ira_allocate (sizeof (move_t) * last_basic_block);
1247   memset (at_bb_end, 0, sizeof (move_t) * last_basic_block);
1248   local_allocno_bitmap = ira_allocate_bitmap ();
1249   used_regno_bitmap = ira_allocate_bitmap ();
1250   renamed_regno_bitmap = ira_allocate_bitmap ();
1251   max_regno_before_changing = max_reg_num ();
1252   ira_traverse_loop_tree (true, ira_loop_tree_root, change_loop, NULL);
1253   set_allocno_somewhere_renamed_p ();
1254   ira_free_bitmap (used_regno_bitmap);
1255   ira_free_bitmap (renamed_regno_bitmap);
1256   ira_free_bitmap (local_allocno_bitmap);
1257   setup_entered_from_non_parent_p ();
1258   FOR_EACH_BB (bb)
1259     {
1260       at_bb_start[bb->index] = NULL;
1261       at_bb_end[bb->index] = NULL;
1262       FOR_EACH_EDGE (e, ei, bb->succs)
1263         if (e->dest != EXIT_BLOCK_PTR)
1264           generate_edge_moves (e);
1265     }
1266   allocno_last_set
1267     = (move_t *) ira_allocate (sizeof (move_t) * max_reg_num ());
1268   allocno_last_set_check
1269     = (int *) ira_allocate (sizeof (int) * max_reg_num ());
1270   memset (allocno_last_set_check, 0, sizeof (int) * max_reg_num ());
1271   memset (hard_regno_last_set_check, 0, sizeof (hard_regno_last_set_check));
1272   curr_tick = 0;
1273   FOR_EACH_BB (bb)
1274     unify_moves (bb, true);
1275   FOR_EACH_BB (bb)
1276     unify_moves (bb, false);
1277   move_vec = VEC_alloc (move_t, heap, ira_allocnos_num);
1278   emit_moves ();
1279   add_ranges_and_copies ();
1280   /* Clean up: */
1281   FOR_EACH_BB (bb)
1282     {
1283       free_move_list (at_bb_start[bb->index]);
1284       free_move_list (at_bb_end[bb->index]);
1285       FOR_EACH_EDGE (e, ei, bb->succs)
1286         {
1287           free_move_list ((move_t) e->aux);
1288           e->aux = NULL;
1289         }
1290     }
1291   VEC_free (move_t, heap, move_vec);
1292   ira_free (allocno_last_set_check);
1293   ira_free (allocno_last_set);
1294   commit_edge_insertions ();
1295   /* Fix insn codes.  It is necessary to do it before reload because
1296      reload assumes initial insn codes defined.  The insn codes can be
1297      invalidated by CFG infrastructure for example in jump
1298      redirection.  */
1299   FOR_EACH_BB (bb)
1300     FOR_BB_INSNS_REVERSE (bb, insn)
1301       if (INSN_P (insn))
1302         recog_memoized (insn);
1303   ira_free (at_bb_end);
1304   ira_free (at_bb_start);
1305 }