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         /* Remove unnecessary stores at the region exit.  We should do
 315            this for readonly memory for sure and this is guaranteed by
 316            that we never generate moves on region borders (see
 317            checking ira_reg_equiv_invariant_p in function
 318            change_loop).  */
 319         if (ALLOCNO_HARD_REGNO (dest_allocno) < 0
 320             && ALLOCNO_HARD_REGNO (src_allocno) >= 0
 321             && not_modified_p (src_allocno, dest_allocno))
 322           {
 323             ALLOCNO_MEM_OPTIMIZED_DEST (src_allocno) = dest_allocno;
 324             ALLOCNO_MEM_OPTIMIZED_DEST_P (dest_allocno) = true;
 325             if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
 326               fprintf (ira_dump_file, "      Remove r%d:a%d->a%d(mem)\n",
 327                        regno, ALLOCNO_NUM (src_allocno),
 328                        ALLOCNO_NUM (dest_allocno));
 329             continue;
 330           }
 331         move = create_move (dest_allocno, src_allocno);
 332         add_to_edge_list (e, move, true);
 333     }
 334 }
 335
 336 /* Bitmap of allocnos local for the current loop.  */
 337 static bitmap local_allocno_bitmap;
 338
 339 /* This bitmap is used to find that we need to generate and to use a
 340    new pseudo-register when processing allocnos with the same original
 341    regno.  */
 342 static bitmap used_regno_bitmap;
 343
 344 /* This bitmap contains regnos of allocnos which were renamed locally
 345    because the allocnos correspond to disjoint live ranges in loops
 346    with a common parent.  */
 347 static bitmap renamed_regno_bitmap;
 348
 349 /* Change (if necessary) pseudo-registers inside loop given by loop
 350    tree node NODE.  */
 351 static void
 352 change_loop (ira_loop_tree_node_t node)
 353 {
 354   bitmap_iterator bi;
 355   unsigned int i;
 356   int regno;
 357   bool used_p;
 358   ira_allocno_t allocno, parent_allocno, *map;
 359   rtx insn, original_reg;
 360   enum reg_class cover_class;
 361   ira_loop_tree_node_t parent;
 362
 363   if (node != ira_loop_tree_root)
 364     {
 365
 366       if (node->bb != NULL)
 367         {
 368           FOR_BB_INSNS (node->bb, insn)
 369             if (INSN_P (insn) && change_regs (&insn))
 370               {
 371                 df_insn_rescan (insn);
 372                 df_notes_rescan (insn);
 373               }
 374           return;
 375         }
 376
 377       if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
 378         fprintf (ira_dump_file,
 379                  "      Changing RTL for loop %d (header bb%d)\n",
 380                  node->loop->num, node->loop->header->index);
 381
 382       parent = ira_curr_loop_tree_node->parent;
 383       map = parent->regno_allocno_map;
 384       EXECUTE_IF_SET_IN_REG_SET (ira_curr_loop_tree_node->border_allocnos,
 385                                  0, i, bi)
 386         {
 387           allocno = ira_allocnos[i];
 388           regno = ALLOCNO_REGNO (allocno);
 389           cover_class = ALLOCNO_COVER_CLASS (allocno);
 390           parent_allocno = map[regno];
 391           ira_assert (regno < ira_reg_equiv_len);
 392           /* We generate the same hard register move because the
 393              reload pass can put an allocno into memory in this case
 394              we will have live range splitting.  If it does not happen
 395              such the same hard register moves will be removed.  The
 396              worst case when the both allocnos are put into memory by
 397              the reload is very rare.  */
 398           if (parent_allocno != NULL
 399               && (ALLOCNO_HARD_REGNO (allocno)
 400                   == ALLOCNO_HARD_REGNO (parent_allocno))
 401               && (ALLOCNO_HARD_REGNO (allocno) < 0
 402                   || (parent->reg_pressure[cover_class] + 1
 403                       <= ira_available_class_regs[cover_class])
 404                   || TEST_HARD_REG_BIT (ira_prohibited_mode_move_regs
 405                                         [ALLOCNO_MODE (allocno)],
 406                                         ALLOCNO_HARD_REGNO (allocno))
 407                   /* don't create copies because reload can spill an
 408                      allocno set by copy although the allocno will not
 409                      get memory slot.  */
 410                   || ira_reg_equiv_invariant_p[regno]
 411                   || ira_reg_equiv_const[regno] != NULL_RTX))
 412             continue;
 413           original_reg = ALLOCNO_REG (allocno);
 414           if (parent_allocno == NULL
 415               || REGNO (ALLOCNO_REG (parent_allocno)) == REGNO (original_reg))
 416             {
 417               if (internal_flag_ira_verbose > 3 && ira_dump_file)
 418                 fprintf (ira_dump_file, "  %i vs parent %i:",
 419                          ALLOCNO_HARD_REGNO (allocno),
 420                          ALLOCNO_HARD_REGNO (parent_allocno));
 421               set_allocno_reg (allocno, create_new_reg (original_reg));
 422             }
 423         }
 424     }
 425   /* Rename locals: Local allocnos with same regno in different loops
 426      might get the different hard register.  So we need to change
 427      ALLOCNO_REG.  */
 428   bitmap_and_compl (local_allocno_bitmap,
 429                     ira_curr_loop_tree_node->all_allocnos,
 430                     ira_curr_loop_tree_node->border_allocnos);
 431   EXECUTE_IF_SET_IN_REG_SET (local_allocno_bitmap, 0, i, bi)
 432     {
 433       allocno = ira_allocnos[i];
 434       regno = ALLOCNO_REGNO (allocno);
 435       if (ALLOCNO_CAP_MEMBER (allocno) != NULL)
 436         continue;
 437       used_p = bitmap_bit_p (used_regno_bitmap, regno);
 438       bitmap_set_bit (used_regno_bitmap, regno);
 439       ALLOCNO_SOMEWHERE_RENAMED_P (allocno) = true;
 440       if (! used_p)
 441         continue;
 442       bitmap_set_bit (renamed_regno_bitmap, regno);
 443       set_allocno_reg (allocno, create_new_reg (ALLOCNO_REG (allocno)));
 444     }
 445 }
 446
 447 /* Process to set up flag somewhere_renamed_p.  */
 448 static void
 449 set_allocno_somewhere_renamed_p (void)
 450 {
 451   unsigned int regno;
 452   ira_allocno_t allocno;
 453   ira_allocno_iterator ai;
 454
 455   FOR_EACH_ALLOCNO (allocno, ai)
 456     {
 457       regno = ALLOCNO_REGNO (allocno);
 458       if (bitmap_bit_p (renamed_regno_bitmap, regno)
 459           && REGNO (ALLOCNO_REG (allocno)) == regno)
 460         ALLOCNO_SOMEWHERE_RENAMED_P (allocno) = true;
 461     }
 462 }
 463
 464 /* Return TRUE if move lists on all edges given in vector VEC are
 465    equal.  */
 466 static bool
 467 eq_edge_move_lists_p (VEC(edge,gc) *vec)
 468 {
 469   move_t list;
 470   int i;
 471
 472   list = (move_t) EDGE_I (vec, 0)->aux;
 473   for (i = EDGE_COUNT (vec) - 1; i > 0; i--)
 474     if (! eq_move_lists_p (list, (move_t) EDGE_I (vec, i)->aux))
 475       return false;
 476   return true;
 477 }
 478
 479 /* Look at all entry edges (if START_P) or exit edges of basic block
 480    BB and put move lists at the BB start or end if it is possible.  In
 481    other words, this decreases code duplication of allocno moves.  */
 482 static void
 483 unify_moves (basic_block bb, bool start_p)
 484 {
 485   int i;
 486   edge e;
 487   move_t list;
 488   VEC(edge,gc) *vec;
 489
 490   vec = (start_p ? bb->preds : bb->succs);
 491   if (EDGE_COUNT (vec) == 0 || ! eq_edge_move_lists_p (vec))
 492     return;
 493   e = EDGE_I (vec, 0);
 494   list = (move_t) e->aux;
 495   if (! start_p && control_flow_insn_p (BB_END (bb)))
 496     return;
 497   e->aux = NULL;
 498   for (i = EDGE_COUNT (vec) - 1; i > 0; i--)
 499     {
 500       e = EDGE_I (vec, i);
 501       free_move_list ((move_t) e->aux);
 502       e->aux = NULL;
 503     }
 504   if (start_p)
 505     at_bb_start[bb->index] = list;
 506   else
 507     at_bb_end[bb->index] = list;
 508 }
 509
 510 /* Last move (in move sequence being processed) setting up the
 511    corresponding hard register.  */
 512 static move_t hard_regno_last_set[FIRST_PSEUDO_REGISTER];
 513
 514 /* If the element value is equal to CURR_TICK then the corresponding
 515    element in `hard_regno_last_set' is defined and correct.  */
 516 static int hard_regno_last_set_check[FIRST_PSEUDO_REGISTER];
 517
 518 /* Last move (in move sequence being processed) setting up the
 519    corresponding allocno.  */
 520 static move_t *allocno_last_set;
 521
 522 /* If the element value is equal to CURR_TICK then the corresponding
 523    element in . `allocno_last_set' is defined and correct.  */
 524 static int *allocno_last_set_check;
 525
 526 /* Definition of vector of moves.  */
 527 DEF_VEC_P(move_t);
 528 DEF_VEC_ALLOC_P(move_t, heap);
 529
 530 /* This vec contains moves sorted topologically (depth-first) on their
 531    dependency graph.  */
 532 static VEC(move_t,heap) *move_vec;
 533
 534 /* The variable value is used to check correctness of values of
 535    elements of arrays `hard_regno_last_set' and
 536    `allocno_last_set_check'.  */
 537 static int curr_tick;
 538
 539 /* This recursive function traverses dependencies of MOVE and produces
 540    topological sorting (in depth-first order).  */
 541 static void
 542 traverse_moves (move_t move)
 543 {
 544   int i;
 545
 546   if (move->visited_p)
 547     return;
 548   move->visited_p = true;
 549   for (i = move->deps_num - 1; i >= 0; i--)
 550     traverse_moves (move->deps[i]);
 551   VEC_safe_push (move_t, heap, move_vec, move);
 552 }
 553
 554 /* Remove unnecessary moves in the LIST, makes topological sorting,
 555    and removes cycles on hard reg dependencies by introducing new
 556    allocnos assigned to memory and additional moves.  It returns the
 557    result move list.  */
 558 static move_t
 559 modify_move_list (move_t list)
 560 {
 561   int i, n, nregs, hard_regno;
 562   ira_allocno_t to, from, new_allocno;
 563   move_t move, new_move, set_move, first, last;
 564
 565   if (list == NULL)
 566     return NULL;
 567   /* Creat move deps.  */
 568   curr_tick++;
 569   for (move = list; move != NULL; move = move->next)
 570     {
 571       to = move->to;
 572       if ((hard_regno = ALLOCNO_HARD_REGNO (to)) < 0)
 573         continue;
 574       nregs = hard_regno_nregs[hard_regno][ALLOCNO_MODE (to)];
 575       for (i = 0; i < nregs; i++)
 576         {
 577           hard_regno_last_set[hard_regno + i] = move;
 578           hard_regno_last_set_check[hard_regno + i] = curr_tick;
 579         }
 580     }
 581   for (move = list; move != NULL; move = move->next)
 582     {
 583       from = move->from;
 584       to = move->to;
 585       if ((hard_regno = ALLOCNO_HARD_REGNO (from)) >= 0)
 586         {
 587           nregs = hard_regno_nregs[hard_regno][ALLOCNO_MODE (from)];
 588           for (n = i = 0; i < nregs; i++)
 589             if (hard_regno_last_set_check[hard_regno + i] == curr_tick
 590                 && (ALLOCNO_REGNO (hard_regno_last_set[hard_regno + i]->to)
 591                     != ALLOCNO_REGNO (from)))
 592               n++;
 593           move->deps = (move_t *) ira_allocate (n * sizeof (move_t));
 594           for (n = i = 0; i < nregs; i++)
 595             if (hard_regno_last_set_check[hard_regno + i] == curr_tick
 596                 && (ALLOCNO_REGNO (hard_regno_last_set[hard_regno + i]->to)
 597                     != ALLOCNO_REGNO (from)))
 598               move->deps[n++] = hard_regno_last_set[hard_regno + i];
 599           move->deps_num = n;
 600         }
 601     }
 602   /* Toplogical sorting:  */
 603   VEC_truncate (move_t, move_vec, 0);
 604   for (move = list; move != NULL; move = move->next)
 605     traverse_moves (move);
 606   last = NULL;
 607   for (i = (int) VEC_length (move_t, move_vec) - 1; i >= 0; i--)
 608     {
 609       move = VEC_index (move_t, move_vec, i);
 610       move->next = NULL;
 611       if (last != NULL)
 612         last->next = move;
 613       last = move;
 614     }
 615   first = VEC_last (move_t, move_vec);
 616   /* Removing cycles:  */
 617   curr_tick++;
 618   VEC_truncate (move_t, move_vec, 0);
 619   for (move = first; move != NULL; move = move->next)
 620     {
 621       from = move->from;
 622       to = move->to;
 623       if ((hard_regno = ALLOCNO_HARD_REGNO (from)) >= 0)
 624         {
 625           nregs = hard_regno_nregs[hard_regno][ALLOCNO_MODE (from)];
 626           for (i = 0; i < nregs; i++)
 627             if (hard_regno_last_set_check[hard_regno + i] == curr_tick
 628                 && ALLOCNO_HARD_REGNO
 629                    (hard_regno_last_set[hard_regno + i]->to) >= 0)
 630               {
 631                 set_move = hard_regno_last_set[hard_regno + i];
 632                 /* It does not matter what loop_tree_node (of TO or
 633                    FROM) to use for the new allocno because of
 634                    subsequent IRA internal representation
 635                    flattening.  */
 636                 new_allocno
 637                   = ira_create_allocno (ALLOCNO_REGNO (set_move->to), false,
 638                                         ALLOCNO_LOOP_TREE_NODE (set_move->to));
 639                 ALLOCNO_MODE (new_allocno) = ALLOCNO_MODE (set_move->to);
 640                 ira_set_allocno_cover_class
 641                   (new_allocno, ALLOCNO_COVER_CLASS (set_move->to));
 642                 ALLOCNO_ASSIGNED_P (new_allocno) = true;
 643                 ALLOCNO_HARD_REGNO (new_allocno) = -1;
 644                 ALLOCNO_REG (new_allocno)
 645                   = create_new_reg (ALLOCNO_REG (set_move->to));
 646                 ALLOCNO_CONFLICT_ID (new_allocno) = ALLOCNO_NUM (new_allocno);
 647                 /* Make it possibly conflicting with all earlier
 648                    created allocnos.  Cases where temporary allocnos
 649                    created to remove the cycles are quite rare.  */
 650                 ALLOCNO_MIN (new_allocno) = 0;
 651                 ALLOCNO_MAX (new_allocno) = ira_allocnos_num - 1;
 652                 new_move = create_move (set_move->to, new_allocno);
 653                 set_move->to = new_allocno;
 654                 VEC_safe_push (move_t, heap, move_vec, new_move);
 655                 ira_move_loops_num++;
 656                 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
 657                   fprintf (ira_dump_file,
 658                            "    Creating temporary allocno a%dr%d\n",
 659                            ALLOCNO_NUM (new_allocno),
 660                            REGNO (ALLOCNO_REG (new_allocno)));
 661               }
 662         }
 663       if ((hard_regno = ALLOCNO_HARD_REGNO (to)) < 0)
 664         continue;
 665       nregs = hard_regno_nregs[hard_regno][ALLOCNO_MODE (to)];
 666       for (i = 0; i < nregs; i++)
 667         {
 668           hard_regno_last_set[hard_regno + i] = move;
 669           hard_regno_last_set_check[hard_regno + i] = curr_tick;
 670         }
 671     }
 672   for (i = (int) VEC_length (move_t, move_vec) - 1; i >= 0; i--)
 673     {
 674       move = VEC_index (move_t, move_vec, i);
 675       move->next = NULL;
 676       last->next = move;
 677       last = move;
 678     }
 679   return first;
 680 }
 681
 682 /* Generate RTX move insns from the move list LIST.  This updates
 683    allocation cost using move execution frequency FREQ.  */
 684 static rtx
 685 emit_move_list (move_t list, int freq)
 686 {
 687   int cost;
 688   rtx result, insn;
 689   enum machine_mode mode;
 690   enum reg_class cover_class;
 691
 692   start_sequence ();
 693   for (; list != NULL; list = list->next)
 694     {
 695       start_sequence ();
 696       emit_move_insn (ALLOCNO_REG (list->to), ALLOCNO_REG (list->from));
 697       list->insn = get_insns ();
 698       end_sequence ();
 699       /* The reload needs to have set up insn codes.  If the reload
 700          sets up insn codes by itself, it may fail because insns will
 701          have hard registers instead of pseudos and there may be no
 702          machine insn with given hard registers.  */
 703       for (insn = list->insn; insn != NULL_RTX; insn = NEXT_INSN (insn))
 704         recog_memoized (insn);
 705       emit_insn (list->insn);
 706       mode = ALLOCNO_MODE (list->to);
 707       cover_class = ALLOCNO_COVER_CLASS (list->to);
 708       cost = 0;
 709       if (ALLOCNO_HARD_REGNO (list->to) < 0)
 710         {
 711           if (ALLOCNO_HARD_REGNO (list->from) >= 0)
 712             {
 713               cost = ira_memory_move_cost[mode][cover_class][0] * freq;
 714               ira_store_cost += cost;
 715             }
 716         }
 717       else if (ALLOCNO_HARD_REGNO (list->from) < 0)
 718         {
 719           if (ALLOCNO_HARD_REGNO (list->to) >= 0)
 720             {
 721               cost = ira_memory_move_cost[mode][cover_class][0] * freq;
 722               ira_load_cost += cost;
 723             }
 724         }
 725       else
 726         {
 727           cost = ira_register_move_cost[mode][cover_class][cover_class] * freq;
 728           ira_shuffle_cost += cost;
 729         }
 730       ira_overall_cost += cost;
 731     }
 732   result = get_insns ();
 733   end_sequence ();
 734   return result;
 735 }
 736
 737 /* Generate RTX move insns from move lists attached to basic blocks
 738    and edges.  */
 739 static void
 740 emit_moves (void)
 741 {
 742   basic_block bb;
 743   edge_iterator ei;
 744   edge e;
 745   rtx insns, tmp;
 746
 747   FOR_EACH_BB (bb)
 748     {
 749       if (at_bb_start[bb->index] != NULL)
 750         {
 751           at_bb_start[bb->index] = modify_move_list (at_bb_start[bb->index]);
 752           insns = emit_move_list (at_bb_start[bb->index],
 753                                   REG_FREQ_FROM_BB (bb));
 754           tmp = BB_HEAD (bb);
 755           if (LABEL_P (tmp))
 756             tmp = NEXT_INSN (tmp);
 757           if (NOTE_INSN_BASIC_BLOCK_P (tmp))
 758             tmp = NEXT_INSN (tmp);
 759           if (tmp == BB_HEAD (bb))
 760             emit_insn_before (insns, tmp);
 761           else if (tmp != NULL_RTX)
 762             emit_insn_after (insns, PREV_INSN (tmp));
 763           else
 764             emit_insn_after (insns, get_last_insn ());
 765         }
 766
 767       if (at_bb_end[bb->index] != NULL)
 768         {
 769           at_bb_end[bb->index] = modify_move_list (at_bb_end[bb->index]);
 770           insns = emit_move_list (at_bb_end[bb->index], REG_FREQ_FROM_BB (bb));
 771           ira_assert (! control_flow_insn_p (BB_END (bb)));
 772           emit_insn_after (insns, BB_END (bb));
 773         }
 774
 775       FOR_EACH_EDGE (e, ei, bb->succs)
 776         {
 777           if (e->aux == NULL)
 778             continue;
 779           ira_assert ((e->flags & EDGE_ABNORMAL) == 0
 780                       || ! EDGE_CRITICAL_P (e));
 781           e->aux = modify_move_list ((move_t) e->aux);
 782           insert_insn_on_edge
 783             (emit_move_list ((move_t) e->aux,
 784                              REG_FREQ_FROM_EDGE_FREQ (EDGE_FREQUENCY (e))),
 785              e);
 786           if (e->src->next_bb != e->dest)
 787             ira_additional_jumps_num++;
 788         }
 789     }
 790 }
 791
 792 /* Update costs of A and corresponding allocnos on upper levels on the
 793    loop tree from reading (if READ_P) or writing A on an execution
 794    path with FREQ.  */
 795 static void
 796 update_costs (ira_allocno_t a, bool read_p, int freq)
 797 {
 798   ira_loop_tree_node_t parent;
 799
 800   for (;;)
 801     {
 802       ALLOCNO_NREFS (a)++;
 803       ALLOCNO_FREQ (a) += freq;
 804       ALLOCNO_MEMORY_COST (a)
 805         += (ira_memory_move_cost[ALLOCNO_MODE (a)][ALLOCNO_COVER_CLASS (a)]
 806             [read_p ? 1 : 0] * freq);
 807       if (ALLOCNO_CAP (a) != NULL)
 808         a = ALLOCNO_CAP (a);
 809       else if ((parent = ALLOCNO_LOOP_TREE_NODE (a)->parent) == NULL
 810                || (a = parent->regno_allocno_map[ALLOCNO_REGNO (a)]) == NULL)
 811         break;
 812     }
 813 }
 814
 815 /* Process moves from LIST with execution FREQ to add ranges, copies,
 816    and modify costs for allocnos involved in the moves.  All regnos
 817    living through the list is in LIVE_THROUGH, and the loop tree node
 818    used to find corresponding allocnos is NODE.  */
 819 static void
 820 add_range_and_copies_from_move_list (move_t list, ira_loop_tree_node_t node,
 821                                      bitmap live_through, int freq)
 822 {
 823   int start, n;
 824   unsigned int regno;
 825   move_t move;
 826   ira_allocno_t to, from, a;
 827   ira_copy_t cp;
 828   allocno_live_range_t r;
 829   bitmap_iterator bi;
 830   HARD_REG_SET hard_regs_live;
 831
 832   if (list == NULL)
 833     return;
 834   n = 0;
 835   EXECUTE_IF_SET_IN_BITMAP (live_through, FIRST_PSEUDO_REGISTER, regno, bi)
 836     n++;
 837   REG_SET_TO_HARD_REG_SET (hard_regs_live, live_through);
 838   /* This is a trick to guarantee that new ranges is not merged with
 839      the old ones.  */
 840   ira_max_point++;
 841   start = ira_max_point;
 842   for (move = list; move != NULL; move = move->next)
 843     {
 844       from = move->from;
 845       to = move->to;
 846       if (ALLOCNO_CONFLICT_ALLOCNO_ARRAY (to) == NULL)
 847         {
 848           if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
 849             fprintf (ira_dump_file, "    Allocate conflicts for a%dr%d\n",
 850                      ALLOCNO_NUM (to), REGNO (ALLOCNO_REG (to)));
 851           ira_allocate_allocno_conflicts (to, n);
 852         }
 853       bitmap_clear_bit (live_through, ALLOCNO_REGNO (from));
 854       bitmap_clear_bit (live_through, ALLOCNO_REGNO (to));
 855       IOR_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (from), hard_regs_live);
 856       IOR_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (to), hard_regs_live);
 857       IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (from),
 858                         hard_regs_live);
 859       IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (to), hard_regs_live);
 860       update_costs (from, true, freq);
 861       update_costs (to, false, freq);
 862       cp = ira_add_allocno_copy (from, to, freq, move->insn, NULL);
 863       if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
 864         fprintf (ira_dump_file, "    Adding cp%d:a%dr%d-a%dr%d\n",
 865                  cp->num, ALLOCNO_NUM (cp->first),
 866                  REGNO (ALLOCNO_REG (cp->first)), ALLOCNO_NUM (cp->second),
 867                  REGNO (ALLOCNO_REG (cp->second)));
 868       r = ALLOCNO_LIVE_RANGES (from);
 869       if (r == NULL || r->finish >= 0)
 870         {
 871           ALLOCNO_LIVE_RANGES (from)
 872             = ira_create_allocno_live_range (from, start, ira_max_point, r);
 873           if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
 874             fprintf (ira_dump_file,
 875                      "    Adding range [%d..%d] to allocno a%dr%d\n",
 876                      start, ira_max_point, ALLOCNO_NUM (from),
 877                      REGNO (ALLOCNO_REG (from)));
 878         }
 879       else
 880         r->finish = ira_max_point;
 881       ira_max_point++;
 882       ALLOCNO_LIVE_RANGES (to)
 883         = ira_create_allocno_live_range (to, ira_max_point, -1,
 884                                          ALLOCNO_LIVE_RANGES (to));
 885       ira_max_point++;
 886     }
 887   for (move = list; move != NULL; move = move->next)
 888     {
 889       r = ALLOCNO_LIVE_RANGES (move->to);
 890       if (r->finish < 0)
 891         {
 892           r->finish = ira_max_point - 1;
 893           if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
 894             fprintf (ira_dump_file,
 895                      "    Adding range [%d..%d] to allocno a%dr%d\n",
 896                      r->start, r->finish, ALLOCNO_NUM (move->to),
 897                      REGNO (ALLOCNO_REG (move->to)));
 898         }
 899     }
 900   EXECUTE_IF_SET_IN_BITMAP (live_through, FIRST_PSEUDO_REGISTER, regno, bi)
 901     {
 902       a = node->regno_allocno_map[regno];
 903       if (ALLOCNO_MEM_OPTIMIZED_DEST (a) == NULL)
 904         {
 905           ALLOCNO_LIVE_RANGES (a)
 906             = ira_create_allocno_live_range (a, start, ira_max_point - 1,
 907                                              ALLOCNO_LIVE_RANGES (a));
 908           if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
 909             fprintf
 910               (ira_dump_file,
 911                "    Adding range [%d..%d] to live through allocno a%dr%d\n",
 912                start, ira_max_point - 1, ALLOCNO_NUM (a),
 913                REGNO (ALLOCNO_REG (a)));
 914         }
 915     }
 916 }
 917
 918 /* Process all move list to add ranges, conflicts, copies, and modify
 919    costs for allocnos involved in the moves.  */
 920 static void
 921 add_ranges_and_copies (void)
 922 {
 923   basic_block bb;
 924   edge_iterator ei;
 925   edge e;
 926   ira_loop_tree_node_t node;
 927   bitmap live_through;
 928
 929   live_through = ira_allocate_bitmap ();
 930   FOR_EACH_BB (bb)
 931     {
 932       /* It does not matter what loop_tree_node (of source or
 933          destination block) to use for searching allocnos by their
 934          regnos because of subsequent IR flattening.  */
 935       node = IRA_BB_NODE (bb)->parent;
 936       bitmap_copy (live_through, DF_LR_IN (bb));
 937       add_range_and_copies_from_move_list
 938         (at_bb_start[bb->index], node, live_through, REG_FREQ_FROM_BB (bb));
 939       bitmap_copy (live_through, DF_LR_OUT (bb));
 940       add_range_and_copies_from_move_list
 941         (at_bb_end[bb->index], node, live_through, REG_FREQ_FROM_BB (bb));
 942       FOR_EACH_EDGE (e, ei, bb->succs)
 943         {
 944           bitmap_and (live_through, DF_LR_IN (e->dest), DF_LR_OUT (bb));
 945           add_range_and_copies_from_move_list
 946             ((move_t) e->aux, node, live_through,
 947              REG_FREQ_FROM_EDGE_FREQ (EDGE_FREQUENCY (e)));
 948         }
 949     }
 950   ira_free_bitmap (live_through);
 951 }
 952
 953 /* The entry function changes code and generates shuffling allocnos on
 954    region borders for the regional (LOOPS_P is TRUE in this case)
 955    register allocation.  */
 956 void
 957 ira_emit (bool loops_p)
 958 {
 959   basic_block bb;
 960   edge_iterator ei;
 961   edge e;
 962   ira_allocno_t a;
 963   ira_allocno_iterator ai;
 964
 965   FOR_EACH_ALLOCNO (a, ai)
 966     ALLOCNO_REG (a) = regno_reg_rtx[ALLOCNO_REGNO (a)];
 967   if (! loops_p)
 968     return;
 969   at_bb_start = (move_t *) ira_allocate (sizeof (move_t) * last_basic_block);
 970   memset (at_bb_start, 0, sizeof (move_t) * last_basic_block);
 971   at_bb_end = (move_t *) ira_allocate (sizeof (move_t) * last_basic_block);
 972   memset (at_bb_end, 0, sizeof (move_t) * last_basic_block);
 973   local_allocno_bitmap = ira_allocate_bitmap ();
 974   used_regno_bitmap = ira_allocate_bitmap ();
 975   renamed_regno_bitmap = ira_allocate_bitmap ();
 976   max_regno_before_changing = max_reg_num ();
 977   ira_traverse_loop_tree (true, ira_loop_tree_root, change_loop, NULL);
 978   set_allocno_somewhere_renamed_p ();
 979   ira_free_bitmap (used_regno_bitmap);
 980   ira_free_bitmap (renamed_regno_bitmap);
 981   ira_free_bitmap (local_allocno_bitmap);
 982   FOR_EACH_BB (bb)
 983     {
 984       at_bb_start[bb->index] = NULL;
 985       at_bb_end[bb->index] = NULL;
 986       FOR_EACH_EDGE (e, ei, bb->succs)
 987         if (e->dest != EXIT_BLOCK_PTR)
 988           generate_edge_moves (e);
 989     }
 990   allocno_last_set
 991     = (move_t *) ira_allocate (sizeof (move_t) * max_reg_num ());
 992   allocno_last_set_check
 993     = (int *) ira_allocate (sizeof (int) * max_reg_num ());
 994   memset (allocno_last_set_check, 0, sizeof (int) * max_reg_num ());
 995   memset (hard_regno_last_set_check, 0, sizeof (hard_regno_last_set_check));
 996   curr_tick = 0;
 997   FOR_EACH_BB (bb)
 998     unify_moves (bb, true);
 999   FOR_EACH_BB (bb)
1000     unify_moves (bb, false);
1001   move_vec = VEC_alloc (move_t, heap, ira_allocnos_num);
1002   emit_moves ();
1003   add_ranges_and_copies ();
1004   /* Clean up: */
1005   FOR_EACH_BB (bb)
1006     {
1007       free_move_list (at_bb_start[bb->index]);
1008       free_move_list (at_bb_end[bb->index]);
1009       FOR_EACH_EDGE (e, ei, bb->succs)
1010         {
1011           free_move_list ((move_t) e->aux);
1012           e->aux = NULL;
1013         }
1014     }
1015   VEC_free (move_t, heap, move_vec);
1016   ira_free (allocno_last_set_check);
1017   ira_free (allocno_last_set);
1018   commit_edge_insertions ();
1019   ira_free (at_bb_end);
1020   ira_free (at_bb_start);
1021 }