gcc/ira-emit.c

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