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;
 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                 ira_allocno_t new_allocno;
 719                 ira_object_t new_obj;
 720
 721                 set_move = hard_regno_last_set[hard_regno + i];
 722                 /* It does not matter what loop_tree_node (of TO or
 723                    FROM) to use for the new allocno because of
 724                    subsequent IRA internal representation
 725                    flattening.  */
 726                 new_allocno
 727                   = ira_create_allocno (ALLOCNO_REGNO (set_move->to), false,
 728                                         ALLOCNO_LOOP_TREE_NODE (set_move->to));
 729                 ALLOCNO_MODE (new_allocno) = ALLOCNO_MODE (set_move->to);
 730                 ira_set_allocno_cover_class
 731                   (new_allocno, ALLOCNO_COVER_CLASS (set_move->to));
 732                 ira_create_allocno_object (new_allocno);
 733                 ALLOCNO_ASSIGNED_P (new_allocno) = true;
 734                 ALLOCNO_HARD_REGNO (new_allocno) = -1;
 735                 ALLOCNO_REG (new_allocno)
 736                   = create_new_reg (ALLOCNO_REG (set_move->to));
 737
 738                 new_obj = ALLOCNO_OBJECT (new_allocno);
 739
 740                 /* Make it possibly conflicting with all earlier
 741                    created allocnos.  Cases where temporary allocnos
 742                    created to remove the cycles are quite rare.  */
 743                 OBJECT_MIN (new_obj) = 0;
 744                 OBJECT_MAX (new_obj) = ira_objects_num - 1;
 745                 new_move = create_move (set_move->to, new_allocno);
 746                 set_move->to = new_allocno;
 747                 VEC_safe_push (move_t, heap, move_vec, new_move);
 748                 ira_move_loops_num++;
 749                 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
 750                   fprintf (ira_dump_file,
 751                            "    Creating temporary allocno a%dr%d\n",
 752                            ALLOCNO_NUM (new_allocno),
 753                            REGNO (ALLOCNO_REG (new_allocno)));
 754               }
 755         }
 756       if ((hard_regno = ALLOCNO_HARD_REGNO (to)) < 0)
 757         continue;
 758       nregs = hard_regno_nregs[hard_regno][ALLOCNO_MODE (to)];
 759       for (i = 0; i < nregs; i++)
 760         {
 761           hard_regno_last_set[hard_regno + i] = move;
 762           hard_regno_last_set_check[hard_regno + i] = curr_tick;
 763         }
 764     }
 765   for (i = (int) VEC_length (move_t, move_vec) - 1; i >= 0; i--)
 766     {
 767       move = VEC_index (move_t, move_vec, i);
 768       move->next = NULL;
 769       last->next = move;
 770       last = move;
 771     }
 772   return first;
 773 }
 774
 775 /* Generate RTX move insns from the move list LIST.  This updates
 776    allocation cost using move execution frequency FREQ.  */
 777 static rtx
 778 emit_move_list (move_t list, int freq)
 779 {
 780   int cost;
 781   rtx result, insn;
 782   enum machine_mode mode;
 783   enum reg_class cover_class;
 784
 785   start_sequence ();
 786   for (; list != NULL; list = list->next)
 787     {
 788       start_sequence ();
 789       emit_move_insn (ALLOCNO_REG (list->to), ALLOCNO_REG (list->from));
 790       list->insn = get_insns ();
 791       end_sequence ();
 792       /* The reload needs to have set up insn codes.  If the reload
 793          sets up insn codes by itself, it may fail because insns will
 794          have hard registers instead of pseudos and there may be no
 795          machine insn with given hard registers.  */
 796       for (insn = list->insn; insn != NULL_RTX; insn = NEXT_INSN (insn))
 797         recog_memoized (insn);
 798       emit_insn (list->insn);
 799       mode = ALLOCNO_MODE (list->to);
 800       cover_class = ALLOCNO_COVER_CLASS (list->to);
 801       cost = 0;
 802       if (ALLOCNO_HARD_REGNO (list->to) < 0)
 803         {
 804           if (ALLOCNO_HARD_REGNO (list->from) >= 0)
 805             {
 806               cost = ira_memory_move_cost[mode][cover_class][0] * freq;
 807               ira_store_cost += cost;
 808             }
 809         }
 810       else if (ALLOCNO_HARD_REGNO (list->from) < 0)
 811         {
 812           if (ALLOCNO_HARD_REGNO (list->to) >= 0)
 813             {
 814               cost = ira_memory_move_cost[mode][cover_class][0] * freq;
 815               ira_load_cost += cost;
 816             }
 817         }
 818       else
 819         {
 820           cost = (ira_get_register_move_cost (mode, cover_class, cover_class)
 821                   * freq);
 822           ira_shuffle_cost += cost;
 823         }
 824       ira_overall_cost += cost;
 825     }
 826   result = get_insns ();
 827   end_sequence ();
 828   return result;
 829 }
 830
 831 /* Generate RTX move insns from move lists attached to basic blocks
 832    and edges.  */
 833 static void
 834 emit_moves (void)
 835 {
 836   basic_block bb;
 837   edge_iterator ei;
 838   edge e;
 839   rtx insns, tmp;
 840
 841   FOR_EACH_BB (bb)
 842     {
 843       if (at_bb_start[bb->index] != NULL)
 844         {
 845           at_bb_start[bb->index] = modify_move_list (at_bb_start[bb->index]);
 846           insns = emit_move_list (at_bb_start[bb->index],
 847                                   REG_FREQ_FROM_BB (bb));
 848           tmp = BB_HEAD (bb);
 849           if (LABEL_P (tmp))
 850             tmp = NEXT_INSN (tmp);
 851           if (NOTE_INSN_BASIC_BLOCK_P (tmp))
 852             tmp = NEXT_INSN (tmp);
 853           if (tmp == BB_HEAD (bb))
 854             emit_insn_before (insns, tmp);
 855           else if (tmp != NULL_RTX)
 856             emit_insn_after (insns, PREV_INSN (tmp));
 857           else
 858             emit_insn_after (insns, get_last_insn ());
 859         }
 860
 861       if (at_bb_end[bb->index] != NULL)
 862         {
 863           at_bb_end[bb->index] = modify_move_list (at_bb_end[bb->index]);
 864           insns = emit_move_list (at_bb_end[bb->index], REG_FREQ_FROM_BB (bb));
 865           ira_assert (! control_flow_insn_p (BB_END (bb)));
 866           emit_insn_after (insns, BB_END (bb));
 867         }
 868
 869       FOR_EACH_EDGE (e, ei, bb->succs)
 870         {
 871           if (e->aux == NULL)
 872             continue;
 873           ira_assert ((e->flags & EDGE_ABNORMAL) == 0
 874                       || ! EDGE_CRITICAL_P (e));
 875           e->aux = modify_move_list ((move_t) e->aux);
 876           insert_insn_on_edge
 877             (emit_move_list ((move_t) e->aux,
 878                              REG_FREQ_FROM_EDGE_FREQ (EDGE_FREQUENCY (e))),
 879              e);
 880           if (e->src->next_bb != e->dest)
 881             ira_additional_jumps_num++;
 882         }
 883     }
 884 }
 885
 886 /* Update costs of A and corresponding allocnos on upper levels on the
 887    loop tree from reading (if READ_P) or writing A on an execution
 888    path with FREQ.  */
 889 static void
 890 update_costs (ira_allocno_t a, bool read_p, int freq)
 891 {
 892   ira_loop_tree_node_t parent;
 893
 894   for (;;)
 895     {
 896       ALLOCNO_NREFS (a)++;
 897       ALLOCNO_FREQ (a) += freq;
 898       ALLOCNO_MEMORY_COST (a)
 899         += (ira_memory_move_cost[ALLOCNO_MODE (a)][ALLOCNO_COVER_CLASS (a)]
 900             [read_p ? 1 : 0] * freq);
 901       if (ALLOCNO_CAP (a) != NULL)
 902         a = ALLOCNO_CAP (a);
 903       else if ((parent = ALLOCNO_LOOP_TREE_NODE (a)->parent) == NULL
 904                || (a = parent->regno_allocno_map[ALLOCNO_REGNO (a)]) == NULL)
 905         break;
 906     }
 907 }
 908
 909 /* Process moves from LIST with execution FREQ to add ranges, copies,
 910    and modify costs for allocnos involved in the moves.  All regnos
 911    living through the list is in LIVE_THROUGH, and the loop tree node
 912    used to find corresponding allocnos is NODE.  */
 913 static void
 914 add_range_and_copies_from_move_list (move_t list, ira_loop_tree_node_t node,
 915                                      bitmap live_through, int freq)
 916 {
 917   int start, n;
 918   unsigned int regno;
 919   move_t move;
 920   ira_allocno_t a;
 921   ira_copy_t cp;
 922   live_range_t r;
 923   bitmap_iterator bi;
 924   HARD_REG_SET hard_regs_live;
 925
 926   if (list == NULL)
 927     return;
 928   n = 0;
 929   EXECUTE_IF_SET_IN_BITMAP (live_through, FIRST_PSEUDO_REGISTER, regno, bi)
 930     n++;
 931   REG_SET_TO_HARD_REG_SET (hard_regs_live, live_through);
 932   /* This is a trick to guarantee that new ranges is not merged with
 933      the old ones.  */
 934   ira_max_point++;
 935   start = ira_max_point;
 936   for (move = list; move != NULL; move = move->next)
 937     {
 938       ira_allocno_t from = move->from;
 939       ira_allocno_t to = move->to;
 940       ira_object_t from_obj = ALLOCNO_OBJECT (from);
 941       ira_object_t to_obj = ALLOCNO_OBJECT (to);
 942       if (OBJECT_CONFLICT_ARRAY (to_obj) == NULL)
 943         {
 944           if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
 945             fprintf (ira_dump_file, "    Allocate conflicts for a%dr%d\n",
 946                      ALLOCNO_NUM (to), REGNO (ALLOCNO_REG (to)));
 947           ira_allocate_object_conflicts (to_obj, n);
 948         }
 949       bitmap_clear_bit (live_through, ALLOCNO_REGNO (from));
 950       bitmap_clear_bit (live_through, ALLOCNO_REGNO (to));
 951       IOR_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (from_obj), hard_regs_live);
 952       IOR_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (to_obj), hard_regs_live);
 953       IOR_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (from_obj), hard_regs_live);
 954       IOR_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (to_obj), hard_regs_live);
 955       update_costs (from, true, freq);
 956       update_costs (to, false, freq);
 957       cp = ira_add_allocno_copy (from, to, freq, false, move->insn, NULL);
 958       if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
 959         fprintf (ira_dump_file, "    Adding cp%d:a%dr%d-a%dr%d\n",
 960                  cp->num, ALLOCNO_NUM (cp->first),
 961                  REGNO (ALLOCNO_REG (cp->first)), ALLOCNO_NUM (cp->second),
 962                  REGNO (ALLOCNO_REG (cp->second)));
 963       r = ALLOCNO_LIVE_RANGES (from);
 964       if (r == NULL || r->finish >= 0)
 965         {
 966           ALLOCNO_LIVE_RANGES (from)
 967             = ira_create_allocno_live_range (from, start, ira_max_point, r);
 968           if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
 969             fprintf (ira_dump_file,
 970                      "    Adding range [%d..%d] to allocno a%dr%d\n",
 971                      start, ira_max_point, ALLOCNO_NUM (from),
 972                      REGNO (ALLOCNO_REG (from)));
 973         }
 974       else
 975         {
 976           r->finish = ira_max_point;
 977           if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
 978             fprintf (ira_dump_file,
 979                      "    Adding range [%d..%d] to allocno a%dr%d\n",
 980                      r->start, ira_max_point, ALLOCNO_NUM (from),
 981                      REGNO (ALLOCNO_REG (from)));
 982         }
 983       ira_max_point++;
 984       ALLOCNO_LIVE_RANGES (to)
 985         = ira_create_allocno_live_range (to, ira_max_point, -1,
 986                                          ALLOCNO_LIVE_RANGES (to));
 987       ira_max_point++;
 988     }
 989   for (move = list; move != NULL; move = move->next)
 990     {
 991       r = ALLOCNO_LIVE_RANGES (move->to);
 992       if (r->finish < 0)
 993         {
 994           r->finish = ira_max_point - 1;
 995           if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
 996             fprintf (ira_dump_file,
 997                      "    Adding range [%d..%d] to allocno a%dr%d\n",
 998                      r->start, r->finish, ALLOCNO_NUM (move->to),
 999                      REGNO (ALLOCNO_REG (move->to)));
1000         }
1001     }
1002   EXECUTE_IF_SET_IN_BITMAP (live_through, FIRST_PSEUDO_REGISTER, regno, bi)
1003     {
1004       ira_allocno_t to;
1005       a = node->regno_allocno_map[regno];
1006       if ((to = ALLOCNO_MEM_OPTIMIZED_DEST (a)) != NULL)
1007         a = to;
1008       ALLOCNO_LIVE_RANGES (a)
1009         = ira_create_allocno_live_range (a, start, ira_max_point - 1,
1010                                          ALLOCNO_LIVE_RANGES (a));
1011       if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
1012         fprintf
1013           (ira_dump_file,
1014            "    Adding range [%d..%d] to live through %s allocno a%dr%d\n",
1015            start, ira_max_point - 1,
1016            to != NULL ? "upper level" : "",
1017            ALLOCNO_NUM (a), REGNO (ALLOCNO_REG (a)));
1018     }
1019 }
1020
1021 /* Process all move list to add ranges, conflicts, copies, and modify
1022    costs for allocnos involved in the moves.  */
1023 static void
1024 add_ranges_and_copies (void)
1025 {
1026   basic_block bb;
1027   edge_iterator ei;
1028   edge e;
1029   ira_loop_tree_node_t node;
1030   bitmap live_through;
1031
1032   live_through = ira_allocate_bitmap ();
1033   FOR_EACH_BB (bb)
1034     {
1035       /* It does not matter what loop_tree_node (of source or
1036          destination block) to use for searching allocnos by their
1037          regnos because of subsequent IR flattening.  */
1038       node = IRA_BB_NODE (bb)->parent;
1039       bitmap_copy (live_through, DF_LR_IN (bb));
1040       add_range_and_copies_from_move_list
1041         (at_bb_start[bb->index], node, live_through, REG_FREQ_FROM_BB (bb));
1042       bitmap_copy (live_through, DF_LR_OUT (bb));
1043       add_range_and_copies_from_move_list
1044         (at_bb_end[bb->index], node, live_through, REG_FREQ_FROM_BB (bb));
1045       FOR_EACH_EDGE (e, ei, bb->succs)
1046         {
1047           bitmap_and (live_through, DF_LR_IN (e->dest), DF_LR_OUT (bb));
1048           add_range_and_copies_from_move_list
1049             ((move_t) e->aux, node, live_through,
1050              REG_FREQ_FROM_EDGE_FREQ (EDGE_FREQUENCY (e)));
1051         }
1052     }
1053   ira_free_bitmap (live_through);
1054 }
1055
1056 /* The entry function changes code and generates shuffling allocnos on
1057    region borders for the regional (LOOPS_P is TRUE in this case)
1058    register allocation.  */
1059 void
1060 ira_emit (bool loops_p)
1061 {
1062   basic_block bb;
1063   rtx insn;
1064   edge_iterator ei;
1065   edge e;
1066   ira_allocno_t a;
1067   ira_allocno_iterator ai;
1068
1069   FOR_EACH_ALLOCNO (a, ai)
1070     ALLOCNO_REG (a) = regno_reg_rtx[ALLOCNO_REGNO (a)];
1071   if (! loops_p)
1072     return;
1073   at_bb_start = (move_t *) ira_allocate (sizeof (move_t) * last_basic_block);
1074   memset (at_bb_start, 0, sizeof (move_t) * last_basic_block);
1075   at_bb_end = (move_t *) ira_allocate (sizeof (move_t) * last_basic_block);
1076   memset (at_bb_end, 0, sizeof (move_t) * last_basic_block);
1077   local_allocno_bitmap = ira_allocate_bitmap ();
1078   used_regno_bitmap = ira_allocate_bitmap ();
1079   renamed_regno_bitmap = ira_allocate_bitmap ();
1080   max_regno_before_changing = max_reg_num ();
1081   ira_traverse_loop_tree (true, ira_loop_tree_root, change_loop, NULL);
1082   set_allocno_somewhere_renamed_p ();
1083   ira_free_bitmap (used_regno_bitmap);
1084   ira_free_bitmap (renamed_regno_bitmap);
1085   ira_free_bitmap (local_allocno_bitmap);
1086   setup_entered_from_non_parent_p ();
1087   FOR_EACH_BB (bb)
1088     {
1089       at_bb_start[bb->index] = NULL;
1090       at_bb_end[bb->index] = NULL;
1091       FOR_EACH_EDGE (e, ei, bb->succs)
1092         if (e->dest != EXIT_BLOCK_PTR)
1093           generate_edge_moves (e);
1094     }
1095   allocno_last_set
1096     = (move_t *) ira_allocate (sizeof (move_t) * max_reg_num ());
1097   allocno_last_set_check
1098     = (int *) ira_allocate (sizeof (int) * max_reg_num ());
1099   memset (allocno_last_set_check, 0, sizeof (int) * max_reg_num ());
1100   memset (hard_regno_last_set_check, 0, sizeof (hard_regno_last_set_check));
1101   curr_tick = 0;
1102   FOR_EACH_BB (bb)
1103     unify_moves (bb, true);
1104   FOR_EACH_BB (bb)
1105     unify_moves (bb, false);
1106   move_vec = VEC_alloc (move_t, heap, ira_allocnos_num);
1107   emit_moves ();
1108   add_ranges_and_copies ();
1109   /* Clean up: */
1110   FOR_EACH_BB (bb)
1111     {
1112       free_move_list (at_bb_start[bb->index]);
1113       free_move_list (at_bb_end[bb->index]);
1114       FOR_EACH_EDGE (e, ei, bb->succs)
1115         {
1116           free_move_list ((move_t) e->aux);
1117           e->aux = NULL;
1118         }
1119     }
1120   VEC_free (move_t, heap, move_vec);
1121   ira_free (allocno_last_set_check);
1122   ira_free (allocno_last_set);
1123   commit_edge_insertions ();
1124   /* Fix insn codes.  It is necessary to do it before reload because
1125      reload assumes initial insn codes defined.  The insn codes can be
1126      invalidated by CFG infrastructure for example in jump
1127      redirection.  */
1128   FOR_EACH_BB (bb)
1129     FOR_BB_INSNS_REVERSE (bb, insn)
1130       if (INSN_P (insn))
1131         recog_memoized (insn);
1132   ira_free (at_bb_end);
1133   ira_free (at_bb_start);
1134 }