gcc/ira-emit.c

   1 /* Integrated Register Allocator.  Changing code and generating moves.
   2    Copyright (C) 2006, 2007, 2008
   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
  23 #include "config.h"
  24 #include "system.h"
  25 #include "coretypes.h"
  26 #include "tm.h"
  27 #include "regs.h"
  28 #include "rtl.h"
  29 #include "tm_p.h"
  30 #include "target.h"
  31 #include "flags.h"
  32 #include "obstack.h"
  33 #include "bitmap.h"
  34 #include "hard-reg-set.h"
  35 #include "basic-block.h"
  36 #include "expr.h"
  37 #include "recog.h"
  38 #include "params.h"
  39 #include "timevar.h"
  40 #include "tree-pass.h"
  41 #include "output.h"
  42 #include "reload.h"
  43 #include "errors.h"
  44 #include "df.h"
  45 #include "ira-int.h"
  46
  47
  48 typedef struct move *move_t;
  49
  50 /* The structure represents an allocno move.  Both allocnos have the
  51    same origional regno but different allocation.  */
  52 struct move
  53 {
  54   /* The allocnos involved in the move.  */
  55   ira_allocno_t from, to;
  56   /* The next move in the move sequence.  */
  57   move_t next;
  58   /* Used for finding dependencies.  */
  59   bool visited_p;
  60   /* The size of the following array. */
  61   int deps_num;
  62   /* Moves on which given move depends on.  Dependency can be cyclic.
  63      It means we need a temporary to generates the moves.  Sequence
  64      A1->A2, B1->B2 where A1 and B2 are assigned to reg R1 and A2 and
  65      B1 are assigned to reg R2 is an example of the cyclic
  66      dependencies.  */
  67   move_t *deps;
  68   /* First insn generated for the move.  */
  69   rtx insn;
  70 };
  71
  72 /* Array of moves (indexed by BB index) which should be put at the
  73    start/end of the corresponding basic blocks.  */
  74 static move_t *at_bb_start, *at_bb_end;
  75
  76 /* Max regno before renaming some pseudo-registers.  For example, the
  77    same pseudo-register can be renamed in a loop if its allocation is
  78    different outside the loop.  */
  79 static int max_regno_before_changing;
  80
  81 /* Return new move of allocnos TO and FROM.  */
  82 static move_t
  83 create_move (ira_allocno_t to, ira_allocno_t from)
  84 {
  85   move_t move;
  86
  87   move = (move_t) ira_allocate (sizeof (struct move));
  88   move->deps = NULL;
  89   move->deps_num = 0;
  90   move->to = to;
  91   move->from = from;
  92   move->next = NULL;
  93   move->insn = NULL_RTX;
  94   move->visited_p = false;
  95   return move;
  96 }
  97
  98 /* Free memory for MOVE and its dependencies.  */
  99 static void
 100 free_move (move_t move)
 101 {
 102   if (move->deps != NULL)
 103     ira_free (move->deps);
 104   ira_free (move);
 105 }
 106
 107 /* Free memory for list of the moves given by its HEAD.  */
 108 static void
 109 free_move_list (move_t head)
 110 {
 111   move_t next;
 112
 113   for (; head != NULL; head = next)
 114     {
 115       next = head->next;
 116       free_move (head);
 117     }
 118 }
 119
 120 /* Return TRUE if the the move list LIST1 and LIST2 are equal (two
 121    moves are equal if they involve the same allocnos).  */
 122 static bool
 123 eq_move_lists_p (move_t list1, move_t list2)
 124 {
 125   for (; list1 != NULL && list2 != NULL;
 126        list1 = list1->next, list2 = list2->next)
 127     if (list1->from != list2->from || list1->to != list2->to)
 128       return false;
 129   return list1 == list2;
 130 }
 131
 132 /* This recursive function changes pseudo-registers in *LOC if it is
 133    necessary.  The function returns TRUE if a change was done.  */
 134 static bool
 135 change_regs (rtx *loc)
 136 {
 137   int i, regno, result = false;
 138   const char *fmt;
 139   enum rtx_code code;
 140
 141   if (*loc == NULL_RTX)
 142     return false;
 143   code = GET_CODE (*loc);
 144   if (code == REG)
 145     {
 146       regno = REGNO (*loc);
 147       if (regno < FIRST_PSEUDO_REGISTER)
 148         return false;
 149       if (regno >= max_regno_before_changing)
 150         /* It is a shared register which was changed already.  */
 151         return false;
 152       if (ira_curr_regno_allocno_map[regno] == NULL)
 153         return false;
 154       *loc = ALLOCNO_REG (ira_curr_regno_allocno_map[regno]);
 155       return true;
 156     }
 157
 158   fmt = GET_RTX_FORMAT (code);
 159   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
 160     {
 161       if (fmt[i] == 'e')
 162         result = change_regs (&XEXP (*loc, i)) || result;
 163       else if (fmt[i] == 'E')
 164         {
 165           int j;
 166
 167           for (j = XVECLEN (*loc, i) - 1; j >= 0; j--)
 168             result = change_regs (&XVECEXP (*loc, i, j)) || result;
 169         }
 170     }
 171   return result;
 172 }
 173
 174 /* Attach MOVE to the edge E.  The move is attached to the head of the
 175    list if HEAD_P is TRUE.  */
 176 static void
 177 add_to_edge_list (edge e, move_t move, bool head_p)
 178 {
 179   move_t last;
 180
 181   if (head_p || e->aux == NULL)
 182     {
 183       move->next = (move_t) e->aux;
 184       e->aux = move;
 185     }
 186   else
 187     {
 188       for (last = (move_t) e->aux; last->next != NULL; last = last->next)
 189         ;
 190       last->next = move;
 191       move->next = NULL;
 192     }
 193 }
 194
 195 /* Create and return new pseudo-register with the same attributes as
 196    ORIGINAL_REG.  */
 197 static rtx
 198 create_new_reg (rtx original_reg)
 199 {
 200   rtx new_reg;
 201
 202   new_reg = gen_reg_rtx (GET_MODE (original_reg));
 203   ORIGINAL_REGNO (new_reg) = ORIGINAL_REGNO (original_reg);
 204   REG_USERVAR_P (new_reg) = REG_USERVAR_P (original_reg);
 205   REG_POINTER (new_reg) = REG_POINTER (original_reg);
 206   REG_ATTRS (new_reg) = REG_ATTRS (original_reg);
 207   if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
 208     fprintf (ira_dump_file, "      Creating newreg=%i from oldreg=%i\n",
 209              REGNO (new_reg), REGNO (original_reg));
 210   return new_reg;
 211 }
 212
 213 /* Return TRUE if loop given by SUBNODE inside the loop given by
 214    NODE.  */
 215 static bool
 216 subloop_tree_node_p (ira_loop_tree_node_t subnode, ira_loop_tree_node_t node)
 217 {
 218   for (; subnode != NULL; subnode = subnode->parent)
 219     if (subnode == node)
 220       return true;
 221   return false;
 222 }
 223
 224 /* Set up member `reg' to REG for allocnos which has the same regno as
 225    ALLOCNO and which are inside the loop corresponding to ALLOCNO. */
 226 static void
 227 set_allocno_reg (ira_allocno_t allocno, rtx reg)
 228 {
 229   int regno;
 230   ira_allocno_t a;
 231   ira_loop_tree_node_t node;
 232
 233   node = ALLOCNO_LOOP_TREE_NODE (allocno);
 234   for (a = ira_regno_allocno_map[ALLOCNO_REGNO (allocno)];
 235        a != NULL;
 236        a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
 237     if (subloop_tree_node_p (ALLOCNO_LOOP_TREE_NODE (a), node))
 238       ALLOCNO_REG (a) = reg;
 239   for (a = ALLOCNO_CAP (allocno); a != NULL; a = ALLOCNO_CAP (a))
 240     ALLOCNO_REG (a) = reg;
 241   regno = ALLOCNO_REGNO (allocno);
 242   for (a = allocno;;)
 243     {
 244       if (a == NULL || (a = ALLOCNO_CAP (a)) == NULL)
 245         {
 246           node = node->parent;
 247           if (node == NULL)
 248             break;
 249           a = node->regno_allocno_map[regno];
 250         }
 251       if (a == NULL)
 252         continue;
 253       if (ALLOCNO_CHILD_RENAMED_P (a))
 254         break;
 255       ALLOCNO_CHILD_RENAMED_P (a) = true;
 256     }
 257 }
 258
 259 /* Return TRUE if move of SRC_ALLOCNO to DEST_ALLOCNO does not change
 260    value of the destination.  One possible reason for this is the
 261    situation when SRC_ALLOCNO is not modified in the corresponding
 262    loop.  */
 263 static bool
 264 not_modified_p (ira_allocno_t src_allocno, ira_allocno_t dest_allocno)
 265 {
 266   int regno, orig_regno;
 267   ira_allocno_t a;
 268   ira_loop_tree_node_t node;
 269
 270   ira_assert (ALLOCNO_CAP_MEMBER (src_allocno) == NULL
 271               && ALLOCNO_CAP_MEMBER (dest_allocno) == NULL);
 272   orig_regno = ALLOCNO_REGNO (src_allocno);
 273   regno = REGNO (ALLOCNO_REG (dest_allocno));
 274   for (node = ALLOCNO_LOOP_TREE_NODE (src_allocno);
 275        node != NULL;
 276        node = node->parent)
 277     if ((a = node->regno_allocno_map[orig_regno]) == NULL)
 278       break;
 279     else if (REGNO (ALLOCNO_REG (a)) == (unsigned) regno)
 280       return true;
 281     else if (bitmap_bit_p (node->modified_regnos, orig_regno))
 282       return false;
 283   return node != NULL;
 284 }
 285
 286 /* Generate and attach moves to the edge E.  This looks at the final
 287    regnos of allocnos living on the edge with the same original regno
 288    to figure out when moves should be generated.  */
 289 static void
 290 generate_edge_moves (edge e)
 291 {
 292   ira_loop_tree_node_t src_loop_node, dest_loop_node;
 293   unsigned int regno;
 294   bitmap_iterator bi;
 295   ira_allocno_t src_allocno, dest_allocno, *src_map, *dest_map;
 296   move_t move;
 297
 298   src_loop_node = IRA_BB_NODE (e->src)->parent;
 299   dest_loop_node = IRA_BB_NODE (e->dest)->parent;
 300   e->aux = NULL;
 301   if (src_loop_node == dest_loop_node)
 302     return;
 303   src_map = src_loop_node->regno_allocno_map;
 304   dest_map = dest_loop_node->regno_allocno_map;
 305   EXECUTE_IF_SET_IN_REG_SET (DF_LR_IN (e->dest),
 306                              FIRST_PSEUDO_REGISTER, regno, bi)
 307     if (bitmap_bit_p (DF_LR_OUT (e->src), regno))
 308       {
 309         src_allocno = src_map[regno];
 310         dest_allocno = dest_map[regno];
 311         if (REGNO (ALLOCNO_REG (src_allocno))
 312             == REGNO (ALLOCNO_REG (dest_allocno)))
 313           continue;
 314         /* Actually it is not a optimization we need this code because
 315            the memory (remember about equivalent memory) might be ROM
 316            (or placed in read only section).  */
 317         if (ALLOCNO_HARD_REGNO (dest_allocno) < 0
 318             && ALLOCNO_HARD_REGNO (src_allocno) >= 0
 319             && not_modified_p (src_allocno, dest_allocno))
 320           {
 321             ALLOCNO_MEM_OPTIMIZED_DEST (src_allocno) = dest_allocno;
 322             ALLOCNO_MEM_OPTIMIZED_DEST_P (dest_allocno) = true;
 323             if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
 324               fprintf (ira_dump_file, "      Remove r%d:a%d->a%d(mem)\n",
 325                        regno, ALLOCNO_NUM (src_allocno),
 326                        ALLOCNO_NUM (dest_allocno));
 327             continue;
 328           }
 329         move = create_move (dest_allocno, src_allocno);
 330         add_to_edge_list (e, move, true);
 331     }
 332 }
 333
 334 /* Bitmap of allocnos local for the current loop.  */
 335 static bitmap local_allocno_bitmap;
 336
 337 /* This bitmap is used to find that we need to generate and to use a
 338    new pseudo-register when processing allocnos with the same original
 339    regno.  */
 340 static bitmap used_regno_bitmap;
 341
 342 /* This bitmap contains regnos of allocnos which were renamed locally
 343    because the allocnos correspond to disjoint live ranges in loops
 344    with a common parent.  */
 345 static bitmap renamed_regno_bitmap;
 346
 347 /* Change (if necessary) pseudo-registers inside loop given by loop
 348    tree node NODE.  */
 349 static void
 350 change_loop (ira_loop_tree_node_t node)
 351 {
 352   bitmap_iterator bi;
 353   unsigned int i;
 354   int regno;
 355   bool used_p;
 356   ira_allocno_t allocno, parent_allocno, *map;
 357   rtx insn, original_reg;
 358   enum reg_class cover_class;
 359   ira_loop_tree_node_t parent;
 360
 361   if (node != ira_loop_tree_root)
 362     {
 363
 364       if (node->bb != NULL)
 365         {
 366           FOR_BB_INSNS (node->bb, insn)
 367             if (INSN_P (insn) && change_regs (&insn))
 368               {
 369                 df_insn_rescan (insn);
 370                 df_notes_rescan (insn);
 371               }
 372           return;
 373         }
 374
 375       if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
 376         fprintf (ira_dump_file,
 377                  "      Changing RTL for loop %d (header bb%d)\n",
 378                  node->loop->num, node->loop->header->index);
 379
 380       parent = ira_curr_loop_tree_node->parent;
 381       map = parent->regno_allocno_map;
 382       EXECUTE_IF_SET_IN_REG_SET (ira_curr_loop_tree_node->border_allocnos,
 383                                  0, i, bi)
 384         {
 385           allocno = ira_allocnos[i];
 386           regno = ALLOCNO_REGNO (allocno);
 387           cover_class = ALLOCNO_COVER_CLASS (allocno);
 388           parent_allocno = map[regno];
 389           ira_assert (regno < ira_reg_equiv_len);
 390           /* We generate the same hard register move because the
 391              reload pass can put an allocno into memory in this case
 392              we will have live range splitting.  If it does not happen
 393              such the same hard register moves will be removed.  The
 394              worst case when the both allocnos are put into memory by
 395              the reload is very rare.  */
 396           if (parent_allocno != NULL
 397               && (ALLOCNO_HARD_REGNO (allocno)
 398                   == ALLOCNO_HARD_REGNO (parent_allocno))
 399               && (ALLOCNO_HARD_REGNO (allocno) < 0
 400                   || (parent->reg_pressure[cover_class] + 1
 401                       <= ira_available_class_regs[cover_class])
 402                   || TEST_HARD_REG_BIT (ira_prohibited_mode_move_regs
 403                                         [ALLOCNO_MODE (allocno)],
 404                                         ALLOCNO_HARD_REGNO (allocno))
 405                   /* don't create copies because reload can spill an
 406                      allocno set by copy although the allocno will not
 407                      get memory slot.  */
 408                   || ira_reg_equiv_invariant_p[regno]
 409                   || ira_reg_equiv_const[regno] != NULL_RTX))
 410             continue;
 411           original_reg = ALLOCNO_REG (allocno);
 412           if (parent_allocno == NULL
 413               || REGNO (ALLOCNO_REG (parent_allocno)) == REGNO (original_reg))
 414             {
 415               if (internal_flag_ira_verbose > 3 && ira_dump_file)
 416                 fprintf (ira_dump_file, "  %i vs parent %i:",
 417                          ALLOCNO_HARD_REGNO (allocno),
 418                          ALLOCNO_HARD_REGNO (parent_allocno));
 419               set_allocno_reg (allocno, create_new_reg (original_reg));
 420             }
 421         }
 422     }
 423   /* Rename locals: Local allocnos with same regno in different loops
 424      might get the different hard register.  So we need to change
 425      ALLOCNO_REG.  */
 426   bitmap_and_compl (local_allocno_bitmap,
 427                     ira_curr_loop_tree_node->all_allocnos,
 428                     ira_curr_loop_tree_node->border_allocnos);
 429   EXECUTE_IF_SET_IN_REG_SET (local_allocno_bitmap, 0, i, bi)
 430     {
 431       allocno = ira_allocnos[i];
 432       regno = ALLOCNO_REGNO (allocno);
 433       if (ALLOCNO_CAP_MEMBER (allocno) != NULL)
 434         continue;
 435       used_p = bitmap_bit_p (used_regno_bitmap, regno);
 436       bitmap_set_bit (used_regno_bitmap, regno);
 437       ALLOCNO_SOMEWHERE_RENAMED_P (allocno) = true;
 438       if (! used_p)
 439         continue;
 440       bitmap_set_bit (renamed_regno_bitmap, regno);
 441       set_allocno_reg (allocno, create_new_reg (ALLOCNO_REG (allocno)));
 442     }
 443 }
 444
 445 /* Process to set up flag somewhere_renamed_p.  */
 446 static void
 447 set_allocno_somewhere_renamed_p (void)
 448 {
 449   unsigned int regno;
 450   ira_allocno_t allocno;
 451   ira_allocno_iterator ai;
 452
 453   FOR_EACH_ALLOCNO (allocno, ai)
 454     {
 455       regno = ALLOCNO_REGNO (allocno);
 456       if (bitmap_bit_p (renamed_regno_bitmap, regno)
 457           && REGNO (ALLOCNO_REG (allocno)) == regno)
 458         ALLOCNO_SOMEWHERE_RENAMED_P (allocno) = true;
 459     }
 460 }
 461
 462 /* Return TRUE if move lists on all edges given in vector VEC are
 463    equal.  */
 464 static bool
 465 eq_edge_move_lists_p (VEC(edge,gc) *vec)
 466 {
 467   move_t list;
 468   int i;
 469
 470   list = (move_t) EDGE_I (vec, 0)->aux;
 471   for (i = EDGE_COUNT (vec) - 1; i > 0; i--)
 472     if (! eq_move_lists_p (list, (move_t) EDGE_I (vec, i)->aux))
 473       return false;
 474   return true;
 475 }
 476
 477 /* Look at all entry edges (if START_P) or exit edges of basic block
 478    BB and put move lists at the BB start or end if it is possible.  In
 479    other words, this decreases code duplication of allocno moves.  */
 480 static void
 481 unify_moves (basic_block bb, bool start_p)
 482 {
 483   int i;
 484   edge e;
 485   move_t list;
 486   VEC(edge,gc) *vec;
 487
 488   vec = (start_p ? bb->preds : bb->succs);
 489   if (EDGE_COUNT (vec) == 0 || ! eq_edge_move_lists_p (vec))
 490     return;
 491   e = EDGE_I (vec, 0);
 492   list = (move_t) e->aux;
 493   if (! start_p && control_flow_insn_p (BB_END (bb)))
 494     return;
 495   e->aux = NULL;
 496   for (i = EDGE_COUNT (vec) - 1; i > 0; i--)
 497     {
 498       e = EDGE_I (vec, i);
 499       free_move_list ((move_t) e->aux);
 500       e->aux = NULL;
 501     }
 502   if (start_p)
 503     at_bb_start[bb->index] = list;
 504   else
 505     at_bb_end[bb->index] = list;
 506 }
 507
 508 /* Last move (in move sequence being processed) setting up the
 509    corresponding hard register.  */
 510 static move_t hard_regno_last_set[FIRST_PSEUDO_REGISTER];
 511
 512 /* If the element value is equal to CURR_TICK then the corresponding
 513    element in `hard_regno_last_set' is defined and correct.  */
 514 static int hard_regno_last_set_check[FIRST_PSEUDO_REGISTER];
 515
 516 /* Last move (in move sequence being processed) setting up the
 517    corresponding allocno.  */
 518 static move_t *allocno_last_set;
 519
 520 /* If the element value is equal to CURR_TICK then the corresponding
 521    element in . `allocno_last_set' is defined and correct.  */
 522 static int *allocno_last_set_check;
 523
 524 /* Definition of vector of moves.  */
 525 DEF_VEC_P(move_t);
 526 DEF_VEC_ALLOC_P(move_t, heap);
 527
 528 /* This vec contains moves sorted topologically (depth-first) on their
 529    dependency graph.  */
 530 static VEC(move_t,heap) *move_vec;
 531
 532 /* The variable value is used to check correctness of values of
 533    elements of arrays `hard_regno_last_set' and
 534    `allocno_last_set_check'.  */
 535 static int curr_tick;
 536
 537 /* This recursive function traverses dependencies of MOVE and produces
 538    topological sorting (in depth-first order).  */
 539 static void
 540 traverse_moves (move_t move)
 541 {
 542   int i;
 543
 544   if (move->visited_p)
 545     return;
 546   move->visited_p = true;
 547   for (i = move->deps_num - 1; i >= 0; i--)
 548     traverse_moves (move->deps[i]);
 549   VEC_safe_push (move_t, heap, move_vec, move);
 550 }
 551
 552 /* Remove unnecessary moves in the LIST, makes topological sorting,
 553    and removes cycles on hard reg dependencies by introducing new
 554    allocnos assigned to memory and additional moves.  It returns the
 555    result move list.  */
 556 static move_t
 557 modify_move_list (move_t list)
 558 {
 559   int i, n, nregs, hard_regno;
 560   ira_allocno_t to, from, new_allocno;
 561   move_t move, new_move, set_move, first, last;
 562
 563   if (list == NULL)
 564     return NULL;
 565   /* Creat move deps.  */
 566   curr_tick++;
 567   for (move = list; move != NULL; move = move->next)
 568     {
 569       to = move->to;
 570       if ((hard_regno = ALLOCNO_HARD_REGNO (to)) < 0)
 571         continue;
 572       nregs = hard_regno_nregs[hard_regno][ALLOCNO_MODE (to)];
 573       for (i = 0; i < nregs; i++)
 574         {
 575           hard_regno_last_set[hard_regno + i] = move;
 576           hard_regno_last_set_check[hard_regno + i] = curr_tick;
 577         }
 578     }
 579   for (move = list; move != NULL; move = move->next)
 580     {
 581       from = move->from;
 582       to = move->to;
 583       if ((hard_regno = ALLOCNO_HARD_REGNO (from)) >= 0)
 584         {
 585           nregs = hard_regno_nregs[hard_regno][ALLOCNO_MODE (from)];
 586           for (n = i = 0; i < nregs; i++)
 587             if (hard_regno_last_set_check[hard_regno + i] == curr_tick
 588                 && (ALLOCNO_REGNO (hard_regno_last_set[hard_regno + i]->to)
 589                     != ALLOCNO_REGNO (from)))
 590               n++;
 591           move->deps = (move_t *) ira_allocate (n * sizeof (move_t));
 592           for (n = i = 0; i < nregs; i++)
 593             if (hard_regno_last_set_check[hard_regno + i] == curr_tick
 594                 && (ALLOCNO_REGNO (hard_regno_last_set[hard_regno + i]->to)
 595                     != ALLOCNO_REGNO (from)))
 596               move->deps[n++] = hard_regno_last_set[hard_regno + i];
 597           move->deps_num = n;
 598         }
 599     }
 600   /* Toplogical sorting:  */
 601   VEC_truncate (move_t, move_vec, 0);
 602   for (move = list; move != NULL; move = move->next)
 603     traverse_moves (move);
 604   last = NULL;
 605   for (i = (int) VEC_length (move_t, move_vec) - 1; i >= 0; i--)
 606     {
 607       move = VEC_index (move_t, move_vec, i);
 608       move->next = NULL;
 609       if (last != NULL)
 610         last->next = move;
 611       last = move;
 612     }
 613   first = VEC_last (move_t, move_vec);
 614   /* Removing cycles:  */
 615   curr_tick++;
 616   VEC_truncate (move_t, move_vec, 0);
 617   for (move = first; move != NULL; move = move->next)
 618     {
 619       from = move->from;
 620       to = move->to;
 621       if ((hard_regno = ALLOCNO_HARD_REGNO (from)) >= 0)
 622         {
 623           nregs = hard_regno_nregs[hard_regno][ALLOCNO_MODE (from)];
 624           for (i = 0; i < nregs; i++)
 625             if (hard_regno_last_set_check[hard_regno + i] == curr_tick
 626                 && ALLOCNO_HARD_REGNO
 627                    (hard_regno_last_set[hard_regno + i]->to) >= 0)
 628               {
 629                 set_move = hard_regno_last_set[hard_regno + i];
 630                 /* It does not matter what loop_tree_node (of TO or
 631                    FROM) to use for the new allocno because of
 632                    subsequent IRA internal representation
 633                    flattening.  */
 634                 new_allocno
 635                   = ira_create_allocno (ALLOCNO_REGNO (set_move->to), false,
 636                                         ALLOCNO_LOOP_TREE_NODE (set_move->to));
 637                 ALLOCNO_MODE (new_allocno) = ALLOCNO_MODE (set_move->to);
 638                 ira_set_allocno_cover_class
 639                   (new_allocno, ALLOCNO_COVER_CLASS (set_move->to));
 640                 ALLOCNO_ASSIGNED_P (new_allocno) = true;
 641                 ALLOCNO_HARD_REGNO (new_allocno) = -1;
 642                 ALLOCNO_REG (new_allocno)
 643                   = create_new_reg (ALLOCNO_REG (set_move->to));
 644                 ALLOCNO_CONFLICT_ID (new_allocno) = ALLOCNO_NUM (new_allocno);
 645                 /* Make it possibly conflicting with all earlier
 646                    created allocnos.  Cases where temporary allocnos
 647                    created to remove the cycles are quite rare.  */
 648                 ALLOCNO_MIN (new_allocno) = 0;
 649                 ALLOCNO_MAX (new_allocno) = ira_allocnos_num - 1;
 650                 new_move = create_move (set_move->to, new_allocno);
 651                 set_move->to = new_allocno;
 652                 VEC_safe_push (move_t, heap, move_vec, new_move);
 653                 ira_move_loops_num++;
 654                 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
 655                   fprintf (ira_dump_file,
 656                            "    Creating temporary allocno a%dr%d\n",
 657                            ALLOCNO_NUM (new_allocno),
 658                            REGNO (ALLOCNO_REG (new_allocno)));
 659               }
 660         }
 661       if ((hard_regno = ALLOCNO_HARD_REGNO (to)) < 0)
 662         continue;
 663       nregs = hard_regno_nregs[hard_regno][ALLOCNO_MODE (to)];
 664       for (i = 0; i < nregs; i++)
 665         {
 666           hard_regno_last_set[hard_regno + i] = move;
 667           hard_regno_last_set_check[hard_regno + i] = curr_tick;
 668         }
 669     }
 670   for (i = (int) VEC_length (move_t, move_vec) - 1; i >= 0; i--)
 671     {
 672       move = VEC_index (move_t, move_vec, i);
 673       move->next = NULL;
 674       last->next = move;
 675       last = move;
 676     }
 677   return first;
 678 }
 679
 680 /* Generate RTX move insns from the move list LIST.  This updates
 681    allocation cost using move execution frequency FREQ.  */
 682 static rtx
 683 emit_move_list (move_t list, int freq)
 684 {
 685   int cost;
 686   rtx result, insn;
 687   enum machine_mode mode;
 688   enum reg_class cover_class;
 689
 690   start_sequence ();
 691   for (; list != NULL; list = list->next)
 692     {
 693       start_sequence ();
 694       emit_move_insn (ALLOCNO_REG (list->to), ALLOCNO_REG (list->from));
 695       list->insn = get_insns ();
 696       end_sequence ();
 697       /* The reload needs to have set up insn codes.  If the reload
 698          sets up insn codes by itself, it may fail because insns will
 699          have hard registers instead of pseudos and there may be no
 700          machine insn with given hard registers.  */
 701       for (insn = list->insn; insn != NULL_RTX; insn = NEXT_INSN (insn))
 702         recog_memoized (insn);
 703       emit_insn (list->insn);
 704       mode = ALLOCNO_MODE (list->to);
 705       cover_class = ALLOCNO_COVER_CLASS (list->to);
 706       cost = 0;
 707       if (ALLOCNO_HARD_REGNO (list->to) < 0)
 708         {
 709           if (ALLOCNO_HARD_REGNO (list->from) >= 0)
 710             {
 711               cost = ira_memory_move_cost[mode][cover_class][0] * freq;
 712               ira_store_cost += cost;
 713             }
 714         }
 715       else if (ALLOCNO_HARD_REGNO (list->from) < 0)
 716         {
 717           if (ALLOCNO_HARD_REGNO (list->to) >= 0)
 718             {
 719               cost = ira_memory_move_cost[mode][cover_class][0] * freq;
 720               ira_load_cost += cost;
 721             }
 722         }
 723       else
 724         {
 725           cost = ira_register_move_cost[mode][cover_class][cover_class] * freq;
 726           ira_shuffle_cost += cost;
 727         }
 728       ira_overall_cost += cost;
 729     }
 730   result = get_insns ();
 731   end_sequence ();
 732   return result;
 733 }
 734
 735 /* Generate RTX move insns from move lists attached to basic blocks
 736    and edges.  */
 737 static void
 738 emit_moves (void)
 739 {
 740   basic_block bb;
 741   edge_iterator ei;
 742   edge e;
 743   rtx insns, tmp;
 744
 745   FOR_EACH_BB (bb)
 746     {
 747       if (at_bb_start[bb->index] != NULL)
 748         {
 749           at_bb_start[bb->index] = modify_move_list (at_bb_start[bb->index]);
 750           insns = emit_move_list (at_bb_start[bb->index],
 751                                   REG_FREQ_FROM_BB (bb));
 752           tmp = BB_HEAD (bb);
 753           if (LABEL_P (tmp))
 754             tmp = NEXT_INSN (tmp);
 755           if (NOTE_INSN_BASIC_BLOCK_P (tmp))
 756             tmp = NEXT_INSN (tmp);
 757           if (tmp == BB_HEAD (bb))
 758             emit_insn_before (insns, tmp);
 759           else if (tmp != NULL_RTX)
 760             emit_insn_after (insns, PREV_INSN (tmp));
 761           else
 762             emit_insn_after (insns, get_last_insn ());
 763         }
 764
 765       if (at_bb_end[bb->index] != NULL)
 766         {
 767           at_bb_end[bb->index] = modify_move_list (at_bb_end[bb->index]);
 768           insns = emit_move_list (at_bb_end[bb->index], REG_FREQ_FROM_BB (bb));
 769           ira_assert (! control_flow_insn_p (BB_END (bb)));
 770           emit_insn_after (insns, BB_END (bb));
 771         }
 772
 773       FOR_EACH_EDGE (e, ei, bb->succs)
 774         {
 775           if (e->aux == NULL)
 776             continue;
 777           ira_assert ((e->flags & EDGE_ABNORMAL) == 0
 778                       || ! EDGE_CRITICAL_P (e));
 779           e->aux = modify_move_list ((move_t) e->aux);
 780           insert_insn_on_edge
 781             (emit_move_list ((move_t) e->aux,
 782                              REG_FREQ_FROM_EDGE_FREQ (EDGE_FREQUENCY (e))),
 783              e);
 784           if (e->src->next_bb != e->dest)
 785             ira_additional_jumps_num++;
 786         }
 787     }
 788 }
 789
 790 /* Update costs of A and corresponding allocnos on upper levels on the
 791    loop tree from reading (if READ_P) or writing A on an execution
 792    path with FREQ.  */
 793 static void
 794 update_costs (ira_allocno_t a, bool read_p, int freq)
 795 {
 796   ira_loop_tree_node_t parent;
 797
 798   for (;;)
 799     {
 800       ALLOCNO_NREFS (a)++;
 801       ALLOCNO_FREQ (a) += freq;
 802       ALLOCNO_MEMORY_COST (a)
 803         += (ira_memory_move_cost[ALLOCNO_MODE (a)][ALLOCNO_COVER_CLASS (a)]
 804             [read_p ? 1 : 0] * freq);
 805       if (ALLOCNO_CAP (a) != NULL)
 806         a = ALLOCNO_CAP (a);
 807       else if ((parent = ALLOCNO_LOOP_TREE_NODE (a)->parent) == NULL
 808                || (a = parent->regno_allocno_map[ALLOCNO_REGNO (a)]) == NULL)
 809         break;
 810     }
 811 }
 812
 813 /* Process moves from LIST with execution FREQ to add ranges, copies,
 814    and modify costs for allocnos involved in the moves.  All regnos
 815    living through the list is in LIVE_THROUGH, and the loop tree node
 816    used to find corresponding allocnos is NODE.  */
 817 static void
 818 add_range_and_copies_from_move_list (move_t list, ira_loop_tree_node_t node,
 819                                      bitmap live_through, int freq)
 820 {
 821   int start, n;
 822   unsigned int regno;
 823   move_t move;
 824   ira_allocno_t to, from, a;
 825   ira_copy_t cp;
 826   allocno_live_range_t r;
 827   bitmap_iterator bi;
 828   HARD_REG_SET hard_regs_live;
 829
 830   if (list == NULL)
 831     return;
 832   n = 0;
 833   EXECUTE_IF_SET_IN_BITMAP (live_through, FIRST_PSEUDO_REGISTER, regno, bi)
 834     n++;
 835   REG_SET_TO_HARD_REG_SET (hard_regs_live, live_through);
 836   /* This is a trick to guarantee that new ranges is not merged with
 837      the old ones.  */
 838   ira_max_point++;
 839   start = ira_max_point;
 840   for (move = list; move != NULL; move = move->next)
 841     {
 842       from = move->from;
 843       to = move->to;
 844       if (ALLOCNO_CONFLICT_ALLOCNO_ARRAY (to) == NULL)
 845         {
 846           if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
 847             fprintf (ira_dump_file, "    Allocate conflicts for a%dr%d\n",
 848                      ALLOCNO_NUM (to), REGNO (ALLOCNO_REG (to)));
 849           ira_allocate_allocno_conflicts (to, n);
 850         }
 851       bitmap_clear_bit (live_through, ALLOCNO_REGNO (from));
 852       bitmap_clear_bit (live_through, ALLOCNO_REGNO (to));
 853       IOR_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (from), hard_regs_live);
 854       IOR_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (to), hard_regs_live);
 855       IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (from),
 856                         hard_regs_live);
 857       IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (to), hard_regs_live);
 858       update_costs (from, true, freq);
 859       update_costs (to, false, freq);
 860       cp = ira_add_allocno_copy (from, to, freq, move->insn, NULL);
 861       if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
 862         fprintf (ira_dump_file, "    Adding cp%d:a%dr%d-a%dr%d\n",
 863                  cp->num, ALLOCNO_NUM (cp->first),
 864                  REGNO (ALLOCNO_REG (cp->first)), ALLOCNO_NUM (cp->second),
 865                  REGNO (ALLOCNO_REG (cp->second)));
 866       r = ALLOCNO_LIVE_RANGES (from);
 867       if (r == NULL || r->finish >= 0)
 868         {
 869           ALLOCNO_LIVE_RANGES (from)
 870             = ira_create_allocno_live_range (from, start, ira_max_point, r);
 871           if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
 872             fprintf (ira_dump_file,
 873                      "    Adding range [%d..%d] to allocno a%dr%d\n",
 874                      start, ira_max_point, ALLOCNO_NUM (from),
 875                      REGNO (ALLOCNO_REG (from)));
 876         }
 877       else
 878         r->finish = ira_max_point;
 879       ira_max_point++;
 880       ALLOCNO_LIVE_RANGES (to)
 881         = ira_create_allocno_live_range (to, ira_max_point, -1,
 882                                          ALLOCNO_LIVE_RANGES (to));
 883       ira_max_point++;
 884     }
 885   for (move = list; move != NULL; move = move->next)
 886     {
 887       r = ALLOCNO_LIVE_RANGES (move->to);
 888       if (r->finish < 0)
 889         {
 890           r->finish = ira_max_point - 1;
 891           if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
 892             fprintf (ira_dump_file,
 893                      "    Adding range [%d..%d] to allocno a%dr%d\n",
 894                      r->start, r->finish, ALLOCNO_NUM (move->to),
 895                      REGNO (ALLOCNO_REG (move->to)));
 896         }
 897     }
 898   EXECUTE_IF_SET_IN_BITMAP (live_through, FIRST_PSEUDO_REGISTER, regno, bi)
 899     {
 900       a = node->regno_allocno_map[regno];
 901       if (ALLOCNO_MEM_OPTIMIZED_DEST (a) == NULL)
 902         {
 903           ALLOCNO_LIVE_RANGES (a)
 904             = ira_create_allocno_live_range (a, start, ira_max_point - 1,
 905                                              ALLOCNO_LIVE_RANGES (a));
 906           if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
 907             fprintf
 908               (ira_dump_file,
 909                "    Adding range [%d..%d] to live through allocno a%dr%d\n",
 910                start, ira_max_point - 1, ALLOCNO_NUM (a),
 911                REGNO (ALLOCNO_REG (a)));
 912         }
 913     }
 914 }
 915
 916 /* Process all move list to add ranges, conflicts, copies, and modify
 917    costs for allocnos involved in the moves.  */
 918 static void
 919 add_ranges_and_copies (void)
 920 {
 921   basic_block bb;
 922   edge_iterator ei;
 923   edge e;
 924   ira_loop_tree_node_t node;
 925   bitmap live_through;
 926
 927   live_through = ira_allocate_bitmap ();
 928   FOR_EACH_BB (bb)
 929     {
 930       /* It does not matter what loop_tree_node (of source or
 931          destination block) to use for searching allocnos by their
 932          regnos because of subsequent IR flattening.  */
 933       node = IRA_BB_NODE (bb)->parent;
 934       bitmap_copy (live_through, DF_LR_IN (bb));
 935       add_range_and_copies_from_move_list
 936         (at_bb_start[bb->index], node, live_through, REG_FREQ_FROM_BB (bb));
 937       bitmap_copy (live_through, DF_LR_OUT (bb));
 938       add_range_and_copies_from_move_list
 939         (at_bb_end[bb->index], node, live_through, REG_FREQ_FROM_BB (bb));
 940       FOR_EACH_EDGE (e, ei, bb->succs)
 941         {
 942           bitmap_and (live_through, DF_LR_IN (e->dest), DF_LR_OUT (bb));
 943           add_range_and_copies_from_move_list
 944             ((move_t) e->aux, node, live_through,
 945              REG_FREQ_FROM_EDGE_FREQ (EDGE_FREQUENCY (e)));
 946         }
 947     }
 948   ira_free_bitmap (live_through);
 949 }
 950
 951 /* The entry function changes code and generates shuffling allocnos on
 952    region borders for the regional (LOOPS_P is TRUE in this case)
 953    register allocation.  */
 954 void
 955 ira_emit (bool loops_p)
 956 {
 957   basic_block bb;
 958   edge_iterator ei;
 959   edge e;
 960   ira_allocno_t a;
 961   ira_allocno_iterator ai;
 962
 963   FOR_EACH_ALLOCNO (a, ai)
 964     ALLOCNO_REG (a) = regno_reg_rtx[ALLOCNO_REGNO (a)];
 965   if (! loops_p)
 966     return;
 967   at_bb_start = (move_t *) ira_allocate (sizeof (move_t) * last_basic_block);
 968   memset (at_bb_start, 0, sizeof (move_t) * last_basic_block);
 969   at_bb_end = (move_t *) ira_allocate (sizeof (move_t) * last_basic_block);
 970   memset (at_bb_end, 0, sizeof (move_t) * last_basic_block);
 971   local_allocno_bitmap = ira_allocate_bitmap ();
 972   used_regno_bitmap = ira_allocate_bitmap ();
 973   renamed_regno_bitmap = ira_allocate_bitmap ();
 974   max_regno_before_changing = max_reg_num ();
 975   ira_traverse_loop_tree (true, ira_loop_tree_root, change_loop, NULL);
 976   set_allocno_somewhere_renamed_p ();
 977   ira_free_bitmap (used_regno_bitmap);
 978   ira_free_bitmap (renamed_regno_bitmap);
 979   ira_free_bitmap (local_allocno_bitmap);
 980   FOR_EACH_BB (bb)
 981     {
 982       at_bb_start[bb->index] = NULL;
 983       at_bb_end[bb->index] = NULL;
 984       FOR_EACH_EDGE (e, ei, bb->succs)
 985         if (e->dest != EXIT_BLOCK_PTR)
 986           generate_edge_moves (e);
 987     }
 988   allocno_last_set
 989     = (move_t *) ira_allocate (sizeof (move_t) * max_reg_num ());
 990   allocno_last_set_check
 991     = (int *) ira_allocate (sizeof (int) * max_reg_num ());
 992   memset (allocno_last_set_check, 0, sizeof (int) * max_reg_num ());
 993   memset (hard_regno_last_set_check, 0, sizeof (hard_regno_last_set_check));
 994   curr_tick = 0;
 995   FOR_EACH_BB (bb)
 996     unify_moves (bb, true);
 997   FOR_EACH_BB (bb)
 998     unify_moves (bb, false);
 999   move_vec = VEC_alloc (move_t, heap, ira_allocnos_num);
1000   emit_moves ();
1001   add_ranges_and_copies ();
1002   /* Clean up: */
1003   FOR_EACH_BB (bb)
1004     {
1005       free_move_list (at_bb_start[bb->index]);
1006       free_move_list (at_bb_end[bb->index]);
1007       FOR_EACH_EDGE (e, ei, bb->succs)
1008         {
1009           free_move_list ((move_t) e->aux);
1010           e->aux = NULL;
1011         }
1012     }
1013   VEC_free (move_t, heap, move_vec);
1014   ira_free (allocno_last_set_check);
1015   ira_free (allocno_last_set);
1016   commit_edge_insertions ();
1017   ira_free (at_bb_end);
1018   ira_free (at_bb_start);
1019 }