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 /* Print move list LIST into file F.  */
 133 static void
 134 print_move_list (FILE *f, move_t list)
 135 {
 136   for (; list != NULL; list = list->next)
 137     fprintf (f, " a%dr%d->a%dr%d",
 138              ALLOCNO_NUM (list->from), ALLOCNO_REGNO (list->from),
 139              ALLOCNO_NUM (list->to), ALLOCNO_REGNO (list->to));
 140   fprintf (f, "\n");
 141 }
 142
 143 extern void ira_debug_move_list (move_t list);
 144
 145 /* Print move list LIST into stderr.  */
 146 void
 147 ira_debug_move_list (move_t list)
 148 {
 149   print_move_list (stderr, list);
 150 }
 151
 152 /* This recursive function changes pseudo-registers in *LOC if it is
 153    necessary.  The function returns TRUE if a change was done.  */
 154 static bool
 155 change_regs (rtx *loc)
 156 {
 157   int i, regno, result = false;
 158   const char *fmt;
 159   enum rtx_code code;
 160   rtx reg;
 161
 162   if (*loc == NULL_RTX)
 163     return false;
 164   code = GET_CODE (*loc);
 165   if (code == REG)
 166     {
 167       regno = REGNO (*loc);
 168       if (regno < FIRST_PSEUDO_REGISTER)
 169         return false;
 170       if (regno >= max_regno_before_changing)
 171         /* It is a shared register which was changed already.  */
 172         return false;
 173       if (ira_curr_regno_allocno_map[regno] == NULL)
 174         return false;
 175       reg = ALLOCNO_REG (ira_curr_regno_allocno_map[regno]);
 176       if (reg == *loc)
 177         return false;
 178       *loc = reg;
 179       return true;
 180     }
 181
 182   fmt = GET_RTX_FORMAT (code);
 183   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
 184     {
 185       if (fmt[i] == 'e')
 186         result = change_regs (&XEXP (*loc, i)) || result;
 187       else if (fmt[i] == 'E')
 188         {
 189           int j;
 190
 191           for (j = XVECLEN (*loc, i) - 1; j >= 0; j--)
 192             result = change_regs (&XVECEXP (*loc, i, j)) || result;
 193         }
 194     }
 195   return result;
 196 }
 197
 198 /* Attach MOVE to the edge E.  The move is attached to the head of the
 199    list if HEAD_P is TRUE.  */
 200 static void
 201 add_to_edge_list (edge e, move_t move, bool head_p)
 202 {
 203   move_t last;
 204
 205   if (head_p || e->aux == NULL)
 206     {
 207       move->next = (move_t) e->aux;
 208       e->aux = move;
 209     }
 210   else
 211     {
 212       for (last = (move_t) e->aux; last->next != NULL; last = last->next)
 213         ;
 214       last->next = move;
 215       move->next = NULL;
 216     }
 217 }
 218
 219 /* Create and return new pseudo-register with the same attributes as
 220    ORIGINAL_REG.  */
 221 static rtx
 222 create_new_reg (rtx original_reg)
 223 {
 224   rtx new_reg;
 225
 226   new_reg = gen_reg_rtx (GET_MODE (original_reg));
 227   ORIGINAL_REGNO (new_reg) = ORIGINAL_REGNO (original_reg);
 228   REG_USERVAR_P (new_reg) = REG_USERVAR_P (original_reg);
 229   REG_POINTER (new_reg) = REG_POINTER (original_reg);
 230   REG_ATTRS (new_reg) = REG_ATTRS (original_reg);
 231   if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
 232     fprintf (ira_dump_file, "      Creating newreg=%i from oldreg=%i\n",
 233              REGNO (new_reg), REGNO (original_reg));
 234   return new_reg;
 235 }
 236
 237 /* Return TRUE if loop given by SUBNODE inside the loop given by
 238    NODE.  */
 239 static bool
 240 subloop_tree_node_p (ira_loop_tree_node_t subnode, ira_loop_tree_node_t node)
 241 {
 242   for (; subnode != NULL; subnode = subnode->parent)
 243     if (subnode == node)
 244       return true;
 245   return false;
 246 }
 247
 248 /* Set up member `reg' to REG for allocnos which has the same regno as
 249    ALLOCNO and which are inside the loop corresponding to ALLOCNO. */
 250 static void
 251 set_allocno_reg (ira_allocno_t allocno, rtx reg)
 252 {
 253   int regno;
 254   ira_allocno_t a;
 255   ira_loop_tree_node_t node;
 256
 257   node = ALLOCNO_LOOP_TREE_NODE (allocno);
 258   for (a = ira_regno_allocno_map[ALLOCNO_REGNO (allocno)];
 259        a != NULL;
 260        a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
 261     if (subloop_tree_node_p (ALLOCNO_LOOP_TREE_NODE (a), node))
 262       ALLOCNO_REG (a) = reg;
 263   for (a = ALLOCNO_CAP (allocno); a != NULL; a = ALLOCNO_CAP (a))
 264     ALLOCNO_REG (a) = reg;
 265   regno = ALLOCNO_REGNO (allocno);
 266   for (a = allocno;;)
 267     {
 268       if (a == NULL || (a = ALLOCNO_CAP (a)) == NULL)
 269         {
 270           node = node->parent;
 271           if (node == NULL)
 272             break;
 273           a = node->regno_allocno_map[regno];
 274         }
 275       if (a == NULL)
 276         continue;
 277       if (ALLOCNO_CHILD_RENAMED_P (a))
 278         break;
 279       ALLOCNO_CHILD_RENAMED_P (a) = true;
 280     }
 281 }
 282
 283 /* Return true if there is an entry to given loop not from its parent
 284    (or grandparent) block.  For example, it is possible for two
 285    adjacent loops inside another loop.  */
 286 static bool
 287 entered_from_non_parent_p (ira_loop_tree_node_t loop_node)
 288 {
 289   ira_loop_tree_node_t bb_node, src_loop_node, parent;
 290   edge e;
 291   edge_iterator ei;
 292
 293   for (bb_node = loop_node->children; bb_node != NULL; bb_node = bb_node->next)
 294     if (bb_node->bb != NULL)
 295       {
 296         FOR_EACH_EDGE (e, ei, bb_node->bb->preds)
 297           if (e->src != ENTRY_BLOCK_PTR
 298               && (src_loop_node = IRA_BB_NODE (e->src)->parent) != loop_node)
 299             {
 300               for (parent = src_loop_node->parent;
 301                    parent != NULL;
 302                    parent = parent->parent)
 303                 if (parent == loop_node)
 304                   break;
 305               if (parent != NULL)
 306                 /* That is an exit from a nested loop -- skip it.  */
 307                 continue;
 308               for (parent = loop_node->parent;
 309                    parent != NULL;
 310                    parent = parent->parent)
 311                 if (src_loop_node == parent)
 312                   break;
 313               if (parent == NULL)
 314                 return true;
 315             }
 316       }
 317   return false;
 318 }
 319
 320 /* Set up ENTERED_FROM_NON_PARENT_P for each loop region.  */
 321 static void
 322 setup_entered_from_non_parent_p (void)
 323 {
 324   unsigned int i;
 325   loop_p loop;
 326
 327   for (i = 0; VEC_iterate (loop_p, ira_loops.larray, i, loop); i++)
 328     if (ira_loop_nodes[i].regno_allocno_map != NULL)
 329       ira_loop_nodes[i].entered_from_non_parent_p
 330         = entered_from_non_parent_p (&ira_loop_nodes[i]);
 331 }
 332
 333 /* Return TRUE if move of SRC_ALLOCNO (assigned to hard register) to
 334    DEST_ALLOCNO (assigned to memory) can be removed beacuse it does
 335    not change value of the destination.  One possible reason for this
 336    is the situation when SRC_ALLOCNO is not modified in the
 337    corresponding loop.  */
 338 static bool
 339 store_can_be_removed_p (ira_allocno_t src_allocno, ira_allocno_t dest_allocno)
 340 {
 341   int regno, orig_regno;
 342   ira_allocno_t a;
 343   ira_loop_tree_node_t node;
 344
 345   ira_assert (ALLOCNO_CAP_MEMBER (src_allocno) == NULL
 346               && ALLOCNO_CAP_MEMBER (dest_allocno) == NULL);
 347   orig_regno = ALLOCNO_REGNO (src_allocno);
 348   regno = REGNO (ALLOCNO_REG (dest_allocno));
 349   for (node = ALLOCNO_LOOP_TREE_NODE (src_allocno);
 350        node != NULL;
 351        node = node->parent)
 352     {
 353       a = node->regno_allocno_map[orig_regno];
 354       ira_assert (a != NULL);
 355       if (REGNO (ALLOCNO_REG (a)) == (unsigned) regno)
 356         /* We achieved the destination and everything is ok.  */
 357         return true;
 358       else if (bitmap_bit_p (node->modified_regnos, orig_regno))
 359         return false;
 360       else if (node->entered_from_non_parent_p)
 361         /* If there is a path from a destination loop block to the
 362            source loop header containing basic blocks of non-parents
 363            (grandparents) of the source loop, we should have checked
 364            modifications of the pseudo on this path too to decide
 365            about possibility to remove the store.  It could be done by
 366            solving a data-flow problem.  Unfortunately such global
 367            solution would complicate IR flattening.  Therefore we just
 368            prohibit removal of the store in such complicated case.  */
 369         return false;
 370     }
 371   gcc_unreachable ();
 372 }
 373
 374 /* Generate and attach moves to the edge E.  This looks at the final
 375    regnos of allocnos living on the edge with the same original regno
 376    to figure out when moves should be generated.  */
 377 static void
 378 generate_edge_moves (edge e)
 379 {
 380   ira_loop_tree_node_t src_loop_node, dest_loop_node;
 381   unsigned int regno;
 382   bitmap_iterator bi;
 383   ira_allocno_t src_allocno, dest_allocno, *src_map, *dest_map;
 384   move_t move;
 385
 386   src_loop_node = IRA_BB_NODE (e->src)->parent;
 387   dest_loop_node = IRA_BB_NODE (e->dest)->parent;
 388   e->aux = NULL;
 389   if (src_loop_node == dest_loop_node)
 390     return;
 391   src_map = src_loop_node->regno_allocno_map;
 392   dest_map = dest_loop_node->regno_allocno_map;
 393   EXECUTE_IF_SET_IN_REG_SET (DF_LR_IN (e->dest),
 394                              FIRST_PSEUDO_REGISTER, regno, bi)
 395     if (bitmap_bit_p (DF_LR_OUT (e->src), regno))
 396       {
 397         src_allocno = src_map[regno];
 398         dest_allocno = dest_map[regno];
 399         if (REGNO (ALLOCNO_REG (src_allocno))
 400             == REGNO (ALLOCNO_REG (dest_allocno)))
 401           continue;
 402         /* Remove unnecessary stores at the region exit.  We should do
 403            this for readonly memory for sure and this is guaranteed by
 404            that we never generate moves on region borders (see
 405            checking ira_reg_equiv_invariant_p in function
 406            change_loop).  */
 407         if (ALLOCNO_HARD_REGNO (dest_allocno) < 0
 408             && ALLOCNO_HARD_REGNO (src_allocno) >= 0
 409             && store_can_be_removed_p (src_allocno, dest_allocno))
 410           {
 411             ALLOCNO_MEM_OPTIMIZED_DEST (src_allocno) = dest_allocno;
 412             ALLOCNO_MEM_OPTIMIZED_DEST_P (dest_allocno) = true;
 413             if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
 414               fprintf (ira_dump_file, "      Remove r%d:a%d->a%d(mem)\n",
 415                        regno, ALLOCNO_NUM (src_allocno),
 416                        ALLOCNO_NUM (dest_allocno));
 417             continue;
 418           }
 419         move = create_move (dest_allocno, src_allocno);
 420         add_to_edge_list (e, move, true);
 421     }
 422 }
 423
 424 /* Bitmap of allocnos local for the current loop.  */
 425 static bitmap local_allocno_bitmap;
 426
 427 /* This bitmap is used to find that we need to generate and to use a
 428    new pseudo-register when processing allocnos with the same original
 429    regno.  */
 430 static bitmap used_regno_bitmap;
 431
 432 /* This bitmap contains regnos of allocnos which were renamed locally
 433    because the allocnos correspond to disjoint live ranges in loops
 434    with a common parent.  */
 435 static bitmap renamed_regno_bitmap;
 436
 437 /* Change (if necessary) pseudo-registers inside loop given by loop
 438    tree node NODE.  */
 439 static void
 440 change_loop (ira_loop_tree_node_t node)
 441 {
 442   bitmap_iterator bi;
 443   unsigned int i;
 444   int regno;
 445   bool used_p;
 446   ira_allocno_t allocno, parent_allocno, *map;
 447   rtx insn, original_reg;
 448   enum reg_class cover_class;
 449   ira_loop_tree_node_t parent;
 450
 451   if (node != ira_loop_tree_root)
 452     {
 453
 454       if (node->bb != NULL)
 455         {
 456           FOR_BB_INSNS (node->bb, insn)
 457             if (INSN_P (insn) && change_regs (&insn))
 458               {
 459                 df_insn_rescan (insn);
 460                 df_notes_rescan (insn);
 461               }
 462           return;
 463         }
 464
 465       if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
 466         fprintf (ira_dump_file,
 467                  "      Changing RTL for loop %d (header bb%d)\n",
 468                  node->loop->num, node->loop->header->index);
 469
 470       parent = ira_curr_loop_tree_node->parent;
 471       map = parent->regno_allocno_map;
 472       EXECUTE_IF_SET_IN_REG_SET (ira_curr_loop_tree_node->border_allocnos,
 473                                  0, i, bi)
 474         {
 475           allocno = ira_allocnos[i];
 476           regno = ALLOCNO_REGNO (allocno);
 477           cover_class = ALLOCNO_COVER_CLASS (allocno);
 478           parent_allocno = map[regno];
 479           ira_assert (regno < ira_reg_equiv_len);
 480           /* We generate the same hard register move because the
 481              reload pass can put an allocno into memory in this case
 482              we will have live range splitting.  If it does not happen
 483              such the same hard register moves will be removed.  The
 484              worst case when the both allocnos are put into memory by
 485              the reload is very rare.  */
 486           if (parent_allocno != NULL
 487               && (ALLOCNO_HARD_REGNO (allocno)
 488                   == ALLOCNO_HARD_REGNO (parent_allocno))
 489               && (ALLOCNO_HARD_REGNO (allocno) < 0
 490                   || (parent->reg_pressure[cover_class] + 1
 491                       <= ira_available_class_regs[cover_class])
 492                   || TEST_HARD_REG_BIT (ira_prohibited_mode_move_regs
 493                                         [ALLOCNO_MODE (allocno)],
 494                                         ALLOCNO_HARD_REGNO (allocno))
 495                   /* don't create copies because reload can spill an
 496                      allocno set by copy although the allocno will not
 497                      get memory slot.  */
 498                   || ira_reg_equiv_invariant_p[regno]
 499                   || ira_reg_equiv_const[regno] != NULL_RTX))
 500             continue;
 501           original_reg = ALLOCNO_REG (allocno);
 502           if (parent_allocno == NULL
 503               || REGNO (ALLOCNO_REG (parent_allocno)) == REGNO (original_reg))
 504             {
 505               if (internal_flag_ira_verbose > 3 && ira_dump_file)
 506                 fprintf (ira_dump_file, "  %i vs parent %i:",
 507                          ALLOCNO_HARD_REGNO (allocno),
 508                          ALLOCNO_HARD_REGNO (parent_allocno));
 509               set_allocno_reg (allocno, create_new_reg (original_reg));
 510             }
 511         }
 512     }
 513   /* Rename locals: Local allocnos with same regno in different loops
 514      might get the different hard register.  So we need to change
 515      ALLOCNO_REG.  */
 516   bitmap_and_compl (local_allocno_bitmap,
 517                     ira_curr_loop_tree_node->all_allocnos,
 518                     ira_curr_loop_tree_node->border_allocnos);
 519   EXECUTE_IF_SET_IN_REG_SET (local_allocno_bitmap, 0, i, bi)
 520     {
 521       allocno = ira_allocnos[i];
 522       regno = ALLOCNO_REGNO (allocno);
 523       if (ALLOCNO_CAP_MEMBER (allocno) != NULL)
 524         continue;
 525       used_p = bitmap_bit_p (used_regno_bitmap, regno);
 526       bitmap_set_bit (used_regno_bitmap, regno);
 527       ALLOCNO_SOMEWHERE_RENAMED_P (allocno) = true;
 528       if (! used_p)
 529         continue;
 530       bitmap_set_bit (renamed_regno_bitmap, regno);
 531       set_allocno_reg (allocno, create_new_reg (ALLOCNO_REG (allocno)));
 532     }
 533 }
 534
 535 /* Process to set up flag somewhere_renamed_p.  */
 536 static void
 537 set_allocno_somewhere_renamed_p (void)
 538 {
 539   unsigned int regno;
 540   ira_allocno_t allocno;
 541   ira_allocno_iterator ai;
 542
 543   FOR_EACH_ALLOCNO (allocno, ai)
 544     {
 545       regno = ALLOCNO_REGNO (allocno);
 546       if (bitmap_bit_p (renamed_regno_bitmap, regno)
 547           && REGNO (ALLOCNO_REG (allocno)) == regno)
 548         ALLOCNO_SOMEWHERE_RENAMED_P (allocno) = true;
 549     }
 550 }
 551
 552 /* Return TRUE if move lists on all edges given in vector VEC are
 553    equal.  */
 554 static bool
 555 eq_edge_move_lists_p (VEC(edge,gc) *vec)
 556 {
 557   move_t list;
 558   int i;
 559
 560   list = (move_t) EDGE_I (vec, 0)->aux;
 561   for (i = EDGE_COUNT (vec) - 1; i > 0; i--)
 562     if (! eq_move_lists_p (list, (move_t) EDGE_I (vec, i)->aux))
 563       return false;
 564   return true;
 565 }
 566
 567 /* Look at all entry edges (if START_P) or exit edges of basic block
 568    BB and put move lists at the BB start or end if it is possible.  In
 569    other words, this decreases code duplication of allocno moves.  */
 570 static void
 571 unify_moves (basic_block bb, bool start_p)
 572 {
 573   int i;
 574   edge e;
 575   move_t list;
 576   VEC(edge,gc) *vec;
 577
 578   vec = (start_p ? bb->preds : bb->succs);
 579   if (EDGE_COUNT (vec) == 0 || ! eq_edge_move_lists_p (vec))
 580     return;
 581   e = EDGE_I (vec, 0);
 582   list = (move_t) e->aux;
 583   if (! start_p && control_flow_insn_p (BB_END (bb)))
 584     return;
 585   e->aux = NULL;
 586   for (i = EDGE_COUNT (vec) - 1; i > 0; i--)
 587     {
 588       e = EDGE_I (vec, i);
 589       free_move_list ((move_t) e->aux);
 590       e->aux = NULL;
 591     }
 592   if (start_p)
 593     at_bb_start[bb->index] = list;
 594   else
 595     at_bb_end[bb->index] = list;
 596 }
 597
 598 /* Last move (in move sequence being processed) setting up the
 599    corresponding hard register.  */
 600 static move_t hard_regno_last_set[FIRST_PSEUDO_REGISTER];
 601
 602 /* If the element value is equal to CURR_TICK then the corresponding
 603    element in `hard_regno_last_set' is defined and correct.  */
 604 static int hard_regno_last_set_check[FIRST_PSEUDO_REGISTER];
 605
 606 /* Last move (in move sequence being processed) setting up the
 607    corresponding allocno.  */
 608 static move_t *allocno_last_set;
 609
 610 /* If the element value is equal to CURR_TICK then the corresponding
 611    element in . `allocno_last_set' is defined and correct.  */
 612 static int *allocno_last_set_check;
 613
 614 /* Definition of vector of moves.  */
 615 DEF_VEC_P(move_t);
 616 DEF_VEC_ALLOC_P(move_t, heap);
 617
 618 /* This vec contains moves sorted topologically (depth-first) on their
 619    dependency graph.  */
 620 static VEC(move_t,heap) *move_vec;
 621
 622 /* The variable value is used to check correctness of values of
 623    elements of arrays `hard_regno_last_set' and
 624    `allocno_last_set_check'.  */
 625 static int curr_tick;
 626
 627 /* This recursive function traverses dependencies of MOVE and produces
 628    topological sorting (in depth-first order).  */
 629 static void
 630 traverse_moves (move_t move)
 631 {
 632   int i;
 633
 634   if (move->visited_p)
 635     return;
 636   move->visited_p = true;
 637   for (i = move->deps_num - 1; i >= 0; i--)
 638     traverse_moves (move->deps[i]);
 639   VEC_safe_push (move_t, heap, move_vec, move);
 640 }
 641
 642 /* Remove unnecessary moves in the LIST, makes topological sorting,
 643    and removes cycles on hard reg dependencies by introducing new
 644    allocnos assigned to memory and additional moves.  It returns the
 645    result move list.  */
 646 static move_t
 647 modify_move_list (move_t list)
 648 {
 649   int i, n, nregs, hard_regno;
 650   ira_allocno_t to, from, new_allocno;
 651   move_t move, new_move, set_move, first, last;
 652
 653   if (list == NULL)
 654     return NULL;
 655   /* Creat move deps.  */
 656   curr_tick++;
 657   for (move = list; move != NULL; move = move->next)
 658     {
 659       to = move->to;
 660       if ((hard_regno = ALLOCNO_HARD_REGNO (to)) < 0)
 661         continue;
 662       nregs = hard_regno_nregs[hard_regno][ALLOCNO_MODE (to)];
 663       for (i = 0; i < nregs; i++)
 664         {
 665           hard_regno_last_set[hard_regno + i] = move;
 666           hard_regno_last_set_check[hard_regno + i] = curr_tick;
 667         }
 668     }
 669   for (move = list; move != NULL; move = move->next)
 670     {
 671       from = move->from;
 672       to = move->to;
 673       if ((hard_regno = ALLOCNO_HARD_REGNO (from)) >= 0)
 674         {
 675           nregs = hard_regno_nregs[hard_regno][ALLOCNO_MODE (from)];
 676           for (n = i = 0; i < nregs; i++)
 677             if (hard_regno_last_set_check[hard_regno + i] == curr_tick
 678                 && (ALLOCNO_REGNO (hard_regno_last_set[hard_regno + i]->to)
 679                     != ALLOCNO_REGNO (from)))
 680               n++;
 681           move->deps = (move_t *) ira_allocate (n * sizeof (move_t));
 682           for (n = i = 0; i < nregs; i++)
 683             if (hard_regno_last_set_check[hard_regno + i] == curr_tick
 684                 && (ALLOCNO_REGNO (hard_regno_last_set[hard_regno + i]->to)
 685                     != ALLOCNO_REGNO (from)))
 686               move->deps[n++] = hard_regno_last_set[hard_regno + i];
 687           move->deps_num = n;
 688         }
 689     }
 690   /* Toplogical sorting:  */
 691   VEC_truncate (move_t, move_vec, 0);
 692   for (move = list; move != NULL; move = move->next)
 693     traverse_moves (move);
 694   last = NULL;
 695   for (i = (int) VEC_length (move_t, move_vec) - 1; i >= 0; i--)
 696     {
 697       move = VEC_index (move_t, move_vec, i);
 698       move->next = NULL;
 699       if (last != NULL)
 700         last->next = move;
 701       last = move;
 702     }
 703   first = VEC_last (move_t, move_vec);
 704   /* Removing cycles:  */
 705   curr_tick++;
 706   VEC_truncate (move_t, move_vec, 0);
 707   for (move = first; move != NULL; move = move->next)
 708     {
 709       from = move->from;
 710       to = move->to;
 711       if ((hard_regno = ALLOCNO_HARD_REGNO (from)) >= 0)
 712         {
 713           nregs = hard_regno_nregs[hard_regno][ALLOCNO_MODE (from)];
 714           for (i = 0; i < nregs; i++)
 715             if (hard_regno_last_set_check[hard_regno + i] == curr_tick
 716                 && ALLOCNO_HARD_REGNO
 717                    (hard_regno_last_set[hard_regno + i]->to) >= 0)
 718               {
 719                 set_move = hard_regno_last_set[hard_regno + i];
 720                 /* It does not matter what loop_tree_node (of TO or
 721                    FROM) to use for the new allocno because of
 722                    subsequent IRA internal representation
 723                    flattening.  */
 724                 new_allocno
 725                   = ira_create_allocno (ALLOCNO_REGNO (set_move->to), false,
 726                                         ALLOCNO_LOOP_TREE_NODE (set_move->to));
 727                 ALLOCNO_MODE (new_allocno) = ALLOCNO_MODE (set_move->to);
 728                 ira_set_allocno_cover_class
 729                   (new_allocno, ALLOCNO_COVER_CLASS (set_move->to));
 730                 ALLOCNO_ASSIGNED_P (new_allocno) = true;
 731                 ALLOCNO_HARD_REGNO (new_allocno) = -1;
 732                 ALLOCNO_REG (new_allocno)
 733                   = create_new_reg (ALLOCNO_REG (set_move->to));
 734                 ALLOCNO_CONFLICT_ID (new_allocno) = ALLOCNO_NUM (new_allocno);
 735                 /* Make it possibly conflicting with all earlier
 736                    created allocnos.  Cases where temporary allocnos
 737                    created to remove the cycles are quite rare.  */
 738                 ALLOCNO_MIN (new_allocno) = 0;
 739                 ALLOCNO_MAX (new_allocno) = ira_allocnos_num - 1;
 740                 new_move = create_move (set_move->to, new_allocno);
 741                 set_move->to = new_allocno;
 742                 VEC_safe_push (move_t, heap, move_vec, new_move);
 743                 ira_move_loops_num++;
 744                 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
 745                   fprintf (ira_dump_file,
 746                            "    Creating temporary allocno a%dr%d\n",
 747                            ALLOCNO_NUM (new_allocno),
 748                            REGNO (ALLOCNO_REG (new_allocno)));
 749               }
 750         }
 751       if ((hard_regno = ALLOCNO_HARD_REGNO (to)) < 0)
 752         continue;
 753       nregs = hard_regno_nregs[hard_regno][ALLOCNO_MODE (to)];
 754       for (i = 0; i < nregs; i++)
 755         {
 756           hard_regno_last_set[hard_regno + i] = move;
 757           hard_regno_last_set_check[hard_regno + i] = curr_tick;
 758         }
 759     }
 760   for (i = (int) VEC_length (move_t, move_vec) - 1; i >= 0; i--)
 761     {
 762       move = VEC_index (move_t, move_vec, i);
 763       move->next = NULL;
 764       last->next = move;
 765       last = move;
 766     }
 767   return first;
 768 }
 769
 770 /* Generate RTX move insns from the move list LIST.  This updates
 771    allocation cost using move execution frequency FREQ.  */
 772 static rtx
 773 emit_move_list (move_t list, int freq)
 774 {
 775   int cost;
 776   rtx result, insn;
 777   enum machine_mode mode;
 778   enum reg_class cover_class;
 779
 780   start_sequence ();
 781   for (; list != NULL; list = list->next)
 782     {
 783       start_sequence ();
 784       emit_move_insn (ALLOCNO_REG (list->to), ALLOCNO_REG (list->from));
 785       list->insn = get_insns ();
 786       end_sequence ();
 787       /* The reload needs to have set up insn codes.  If the reload
 788          sets up insn codes by itself, it may fail because insns will
 789          have hard registers instead of pseudos and there may be no
 790          machine insn with given hard registers.  */
 791       for (insn = list->insn; insn != NULL_RTX; insn = NEXT_INSN (insn))
 792         recog_memoized (insn);
 793       emit_insn (list->insn);
 794       mode = ALLOCNO_MODE (list->to);
 795       cover_class = ALLOCNO_COVER_CLASS (list->to);
 796       cost = 0;
 797       if (ALLOCNO_HARD_REGNO (list->to) < 0)
 798         {
 799           if (ALLOCNO_HARD_REGNO (list->from) >= 0)
 800             {
 801               cost = ira_memory_move_cost[mode][cover_class][0] * freq;
 802               ira_store_cost += cost;
 803             }
 804         }
 805       else if (ALLOCNO_HARD_REGNO (list->from) < 0)
 806         {
 807           if (ALLOCNO_HARD_REGNO (list->to) >= 0)
 808             {
 809               cost = ira_memory_move_cost[mode][cover_class][0] * freq;
 810               ira_load_cost += cost;
 811             }
 812         }
 813       else
 814         {
 815           cost = ira_register_move_cost[mode][cover_class][cover_class] * 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 }