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_EACH_VEC_ELT (loop_p, ira_loops.larray, i, loop)
 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_set_bit (used_regno_bitmap, regno);
 525       ALLOCNO_SOMEWHERE_RENAMED_P (allocno) = true;
 526       if (! used_p)
 527         continue;
 528       bitmap_set_bit (renamed_regno_bitmap, regno);
 529       set_allocno_reg (allocno, create_new_reg (ALLOCNO_REG (allocno)));
 530     }
 531 }
 532
 533 /* Process to set up flag somewhere_renamed_p.  */
 534 static void
 535 set_allocno_somewhere_renamed_p (void)
 536 {
 537   unsigned int regno;
 538   ira_allocno_t allocno;
 539   ira_allocno_iterator ai;
 540
 541   FOR_EACH_ALLOCNO (allocno, ai)
 542     {
 543       regno = ALLOCNO_REGNO (allocno);
 544       if (bitmap_bit_p (renamed_regno_bitmap, regno)
 545           && REGNO (ALLOCNO_REG (allocno)) == regno)
 546         ALLOCNO_SOMEWHERE_RENAMED_P (allocno) = true;
 547     }
 548 }
 549
 550 /* Return TRUE if move lists on all edges given in vector VEC are
 551    equal.  */
 552 static bool
 553 eq_edge_move_lists_p (VEC(edge,gc) *vec)
 554 {
 555   move_t list;
 556   int i;
 557
 558   list = (move_t) EDGE_I (vec, 0)->aux;
 559   for (i = EDGE_COUNT (vec) - 1; i > 0; i--)
 560     if (! eq_move_lists_p (list, (move_t) EDGE_I (vec, i)->aux))
 561       return false;
 562   return true;
 563 }
 564
 565 /* Look at all entry edges (if START_P) or exit edges of basic block
 566    BB and put move lists at the BB start or end if it is possible.  In
 567    other words, this decreases code duplication of allocno moves.  */
 568 static void
 569 unify_moves (basic_block bb, bool start_p)
 570 {
 571   int i;
 572   edge e;
 573   move_t list;
 574   VEC(edge,gc) *vec;
 575
 576   vec = (start_p ? bb->preds : bb->succs);
 577   if (EDGE_COUNT (vec) == 0 || ! eq_edge_move_lists_p (vec))
 578     return;
 579   e = EDGE_I (vec, 0);
 580   list = (move_t) e->aux;
 581   if (! start_p && control_flow_insn_p (BB_END (bb)))
 582     return;
 583   e->aux = NULL;
 584   for (i = EDGE_COUNT (vec) - 1; i > 0; i--)
 585     {
 586       e = EDGE_I (vec, i);
 587       free_move_list ((move_t) e->aux);
 588       e->aux = NULL;
 589     }
 590   if (start_p)
 591     at_bb_start[bb->index] = list;
 592   else
 593     at_bb_end[bb->index] = list;
 594 }
 595
 596 /* Last move (in move sequence being processed) setting up the
 597    corresponding hard register.  */
 598 static move_t hard_regno_last_set[FIRST_PSEUDO_REGISTER];
 599
 600 /* If the element value is equal to CURR_TICK then the corresponding
 601    element in `hard_regno_last_set' is defined and correct.  */
 602 static int hard_regno_last_set_check[FIRST_PSEUDO_REGISTER];
 603
 604 /* Last move (in move sequence being processed) setting up the
 605    corresponding allocno.  */
 606 static move_t *allocno_last_set;
 607
 608 /* If the element value is equal to CURR_TICK then the corresponding
 609    element in . `allocno_last_set' is defined and correct.  */
 610 static int *allocno_last_set_check;
 611
 612 /* Definition of vector of moves.  */
 613 DEF_VEC_P(move_t);
 614 DEF_VEC_ALLOC_P(move_t, heap);
 615
 616 /* This vec contains moves sorted topologically (depth-first) on their
 617    dependency graph.  */
 618 static VEC(move_t,heap) *move_vec;
 619
 620 /* The variable value is used to check correctness of values of
 621    elements of arrays `hard_regno_last_set' and
 622    `allocno_last_set_check'.  */
 623 static int curr_tick;
 624
 625 /* This recursive function traverses dependencies of MOVE and produces
 626    topological sorting (in depth-first order).  */
 627 static void
 628 traverse_moves (move_t move)
 629 {
 630   int i;
 631
 632   if (move->visited_p)
 633     return;
 634   move->visited_p = true;
 635   for (i = move->deps_num - 1; i >= 0; i--)
 636     traverse_moves (move->deps[i]);
 637   VEC_safe_push (move_t, heap, move_vec, move);
 638 }
 639
 640 /* Remove unnecessary moves in the LIST, makes topological sorting,
 641    and removes cycles on hard reg dependencies by introducing new
 642    allocnos assigned to memory and additional moves.  It returns the
 643    result move list.  */
 644 static move_t
 645 modify_move_list (move_t list)
 646 {
 647   int i, n, nregs, hard_regno;
 648   ira_allocno_t to, from;
 649   move_t move, new_move, set_move, first, last;
 650
 651   if (list == NULL)
 652     return NULL;
 653   /* Creat move deps.  */
 654   curr_tick++;
 655   for (move = list; move != NULL; move = move->next)
 656     {
 657       to = move->to;
 658       if ((hard_regno = ALLOCNO_HARD_REGNO (to)) < 0)
 659         continue;
 660       nregs = hard_regno_nregs[hard_regno][ALLOCNO_MODE (to)];
 661       for (i = 0; i < nregs; i++)
 662         {
 663           hard_regno_last_set[hard_regno + i] = move;
 664           hard_regno_last_set_check[hard_regno + i] = curr_tick;
 665         }
 666     }
 667   for (move = list; move != NULL; move = move->next)
 668     {
 669       from = move->from;
 670       to = move->to;
 671       if ((hard_regno = ALLOCNO_HARD_REGNO (from)) >= 0)
 672         {
 673           nregs = hard_regno_nregs[hard_regno][ALLOCNO_MODE (from)];
 674           for (n = i = 0; i < nregs; i++)
 675             if (hard_regno_last_set_check[hard_regno + i] == curr_tick
 676                 && (ALLOCNO_REGNO (hard_regno_last_set[hard_regno + i]->to)
 677                     != ALLOCNO_REGNO (from)))
 678               n++;
 679           move->deps = (move_t *) ira_allocate (n * sizeof (move_t));
 680           for (n = i = 0; i < nregs; i++)
 681             if (hard_regno_last_set_check[hard_regno + i] == curr_tick
 682                 && (ALLOCNO_REGNO (hard_regno_last_set[hard_regno + i]->to)
 683                     != ALLOCNO_REGNO (from)))
 684               move->deps[n++] = hard_regno_last_set[hard_regno + i];
 685           move->deps_num = n;
 686         }
 687     }
 688   /* Toplogical sorting:  */
 689   VEC_truncate (move_t, move_vec, 0);
 690   for (move = list; move != NULL; move = move->next)
 691     traverse_moves (move);
 692   last = NULL;
 693   for (i = (int) VEC_length (move_t, move_vec) - 1; i >= 0; i--)
 694     {
 695       move = VEC_index (move_t, move_vec, i);
 696       move->next = NULL;
 697       if (last != NULL)
 698         last->next = move;
 699       last = move;
 700     }
 701   first = VEC_last (move_t, move_vec);
 702   /* Removing cycles:  */
 703   curr_tick++;
 704   VEC_truncate (move_t, move_vec, 0);
 705   for (move = first; move != NULL; move = move->next)
 706     {
 707       from = move->from;
 708       to = move->to;
 709       if ((hard_regno = ALLOCNO_HARD_REGNO (from)) >= 0)
 710         {
 711           nregs = hard_regno_nregs[hard_regno][ALLOCNO_MODE (from)];
 712           for (i = 0; i < nregs; i++)
 713             if (hard_regno_last_set_check[hard_regno + i] == curr_tick
 714                 && ALLOCNO_HARD_REGNO
 715                    (hard_regno_last_set[hard_regno + i]->to) >= 0)
 716               {
 717                 int n, j;
 718                 ira_allocno_t new_allocno;
 719
 720                 set_move = hard_regno_last_set[hard_regno + i];
 721                 /* It does not matter what loop_tree_node (of TO or
 722                    FROM) to use for the new allocno because of
 723                    subsequent IRA internal representation
 724                    flattening.  */
 725                 new_allocno
 726                   = ira_create_allocno (ALLOCNO_REGNO (set_move->to), false,
 727                                         ALLOCNO_LOOP_TREE_NODE (set_move->to));
 728                 ALLOCNO_MODE (new_allocno) = ALLOCNO_MODE (set_move->to);
 729                 ira_set_allocno_cover_class
 730                   (new_allocno, ALLOCNO_COVER_CLASS (set_move->to));
 731                 ira_create_allocno_objects (new_allocno);
 732                 ALLOCNO_ASSIGNED_P (new_allocno) = true;
 733                 ALLOCNO_HARD_REGNO (new_allocno) = -1;
 734                 ALLOCNO_REG (new_allocno)
 735                   = create_new_reg (ALLOCNO_REG (set_move->to));
 736
 737                 /* Make it possibly conflicting with all earlier
 738                    created allocnos.  Cases where temporary allocnos
 739                    created to remove the cycles are quite rare.  */
 740                 n = ALLOCNO_NUM_OBJECTS (new_allocno);
 741                 gcc_assert (n == ALLOCNO_NUM_OBJECTS (set_move->to));
 742                 for (j = 0; j < n; j++)
 743                   {
 744                     ira_object_t new_obj = ALLOCNO_OBJECT (new_allocno, j);
 745
 746                     OBJECT_MIN (new_obj) = 0;
 747                     OBJECT_MAX (new_obj) = ira_objects_num - 1;
 748                   }
 749
 750                 new_move = create_move (set_move->to, new_allocno);
 751                 set_move->to = new_allocno;
 752                 VEC_safe_push (move_t, heap, move_vec, new_move);
 753                 ira_move_loops_num++;
 754                 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
 755                   fprintf (ira_dump_file,
 756                            "    Creating temporary allocno a%dr%d\n",
 757                            ALLOCNO_NUM (new_allocno),
 758                            REGNO (ALLOCNO_REG (new_allocno)));
 759               }
 760         }
 761       if ((hard_regno = ALLOCNO_HARD_REGNO (to)) < 0)
 762         continue;
 763       nregs = hard_regno_nregs[hard_regno][ALLOCNO_MODE (to)];
 764       for (i = 0; i < nregs; i++)
 765         {
 766           hard_regno_last_set[hard_regno + i] = move;
 767           hard_regno_last_set_check[hard_regno + i] = curr_tick;
 768         }
 769     }
 770   for (i = (int) VEC_length (move_t, move_vec) - 1; i >= 0; i--)
 771     {
 772       move = VEC_index (move_t, move_vec, i);
 773       move->next = NULL;
 774       last->next = move;
 775       last = move;
 776     }
 777   return first;
 778 }
 779
 780 /* Generate RTX move insns from the move list LIST.  This updates
 781    allocation cost using move execution frequency FREQ.  */
 782 static rtx
 783 emit_move_list (move_t list, int freq)
 784 {
 785   int cost;
 786   rtx result, insn;
 787   enum machine_mode mode;
 788   enum reg_class cover_class;
 789
 790   start_sequence ();
 791   for (; list != NULL; list = list->next)
 792     {
 793       start_sequence ();
 794       emit_move_insn (ALLOCNO_REG (list->to), ALLOCNO_REG (list->from));
 795       list->insn = get_insns ();
 796       end_sequence ();
 797       /* The reload needs to have set up insn codes.  If the reload
 798          sets up insn codes by itself, it may fail because insns will
 799          have hard registers instead of pseudos and there may be no
 800          machine insn with given hard registers.  */
 801       for (insn = list->insn; insn != NULL_RTX; insn = NEXT_INSN (insn))
 802         recog_memoized (insn);
 803       emit_insn (list->insn);
 804       mode = ALLOCNO_MODE (list->to);
 805       cover_class = ALLOCNO_COVER_CLASS (list->to);
 806       cost = 0;
 807       if (ALLOCNO_HARD_REGNO (list->to) < 0)
 808         {
 809           if (ALLOCNO_HARD_REGNO (list->from) >= 0)
 810             {
 811               cost = ira_memory_move_cost[mode][cover_class][0] * freq;
 812               ira_store_cost += cost;
 813             }
 814         }
 815       else if (ALLOCNO_HARD_REGNO (list->from) < 0)
 816         {
 817           if (ALLOCNO_HARD_REGNO (list->to) >= 0)
 818             {
 819               cost = ira_memory_move_cost[mode][cover_class][0] * freq;
 820               ira_load_cost += cost;
 821             }
 822         }
 823       else
 824         {
 825           cost = (ira_get_register_move_cost (mode, cover_class, cover_class)
 826                   * freq);
 827           ira_shuffle_cost += cost;
 828         }
 829       ira_overall_cost += cost;
 830     }
 831   result = get_insns ();
 832   end_sequence ();
 833   return result;
 834 }
 835
 836 /* Generate RTX move insns from move lists attached to basic blocks
 837    and edges.  */
 838 static void
 839 emit_moves (void)
 840 {
 841   basic_block bb;
 842   edge_iterator ei;
 843   edge e;
 844   rtx insns, tmp;
 845
 846   FOR_EACH_BB (bb)
 847     {
 848       if (at_bb_start[bb->index] != NULL)
 849         {
 850           at_bb_start[bb->index] = modify_move_list (at_bb_start[bb->index]);
 851           insns = emit_move_list (at_bb_start[bb->index],
 852                                   REG_FREQ_FROM_BB (bb));
 853           tmp = BB_HEAD (bb);
 854           if (LABEL_P (tmp))
 855             tmp = NEXT_INSN (tmp);
 856           if (NOTE_INSN_BASIC_BLOCK_P (tmp))
 857             tmp = NEXT_INSN (tmp);
 858           if (tmp == BB_HEAD (bb))
 859             emit_insn_before (insns, tmp);
 860           else if (tmp != NULL_RTX)
 861             emit_insn_after (insns, PREV_INSN (tmp));
 862           else
 863             emit_insn_after (insns, get_last_insn ());
 864         }
 865
 866       if (at_bb_end[bb->index] != NULL)
 867         {
 868           at_bb_end[bb->index] = modify_move_list (at_bb_end[bb->index]);
 869           insns = emit_move_list (at_bb_end[bb->index], REG_FREQ_FROM_BB (bb));
 870           ira_assert (! control_flow_insn_p (BB_END (bb)));
 871           emit_insn_after (insns, BB_END (bb));
 872         }
 873
 874       FOR_EACH_EDGE (e, ei, bb->succs)
 875         {
 876           if (e->aux == NULL)
 877             continue;
 878           ira_assert ((e->flags & EDGE_ABNORMAL) == 0
 879                       || ! EDGE_CRITICAL_P (e));
 880           e->aux = modify_move_list ((move_t) e->aux);
 881           insert_insn_on_edge
 882             (emit_move_list ((move_t) e->aux,
 883                              REG_FREQ_FROM_EDGE_FREQ (EDGE_FREQUENCY (e))),
 884              e);
 885           if (e->src->next_bb != e->dest)
 886             ira_additional_jumps_num++;
 887         }
 888     }
 889 }
 890
 891 /* Update costs of A and corresponding allocnos on upper levels on the
 892    loop tree from reading (if READ_P) or writing A on an execution
 893    path with FREQ.  */
 894 static void
 895 update_costs (ira_allocno_t a, bool read_p, int freq)
 896 {
 897   ira_loop_tree_node_t parent;
 898
 899   for (;;)
 900     {
 901       ALLOCNO_NREFS (a)++;
 902       ALLOCNO_FREQ (a) += freq;
 903       ALLOCNO_MEMORY_COST (a)
 904         += (ira_memory_move_cost[ALLOCNO_MODE (a)][ALLOCNO_COVER_CLASS (a)]
 905             [read_p ? 1 : 0] * freq);
 906       if (ALLOCNO_CAP (a) != NULL)
 907         a = ALLOCNO_CAP (a);
 908       else if ((parent = ALLOCNO_LOOP_TREE_NODE (a)->parent) == NULL
 909                || (a = parent->regno_allocno_map[ALLOCNO_REGNO (a)]) == NULL)
 910         break;
 911     }
 912 }
 913
 914 /* Process moves from LIST with execution FREQ to add ranges, copies,
 915    and modify costs for allocnos involved in the moves.  All regnos
 916    living through the list is in LIVE_THROUGH, and the loop tree node
 917    used to find corresponding allocnos is NODE.  */
 918 static void
 919 add_range_and_copies_from_move_list (move_t list, ira_loop_tree_node_t node,
 920                                      bitmap live_through, int freq)
 921 {
 922   int start, n;
 923   unsigned int regno;
 924   move_t move;
 925   ira_allocno_t a;
 926   ira_copy_t cp;
 927   live_range_t r;
 928   bitmap_iterator bi;
 929   HARD_REG_SET hard_regs_live;
 930
 931   if (list == NULL)
 932     return;
 933   n = 0;
 934   EXECUTE_IF_SET_IN_BITMAP (live_through, FIRST_PSEUDO_REGISTER, regno, bi)
 935     n++;
 936   REG_SET_TO_HARD_REG_SET (hard_regs_live, live_through);
 937   /* This is a trick to guarantee that new ranges is not merged with
 938      the old ones.  */
 939   ira_max_point++;
 940   start = ira_max_point;
 941   for (move = list; move != NULL; move = move->next)
 942     {
 943       ira_allocno_t from = move->from;
 944       ira_allocno_t to = move->to;
 945       int nr, i;
 946
 947       bitmap_clear_bit (live_through, ALLOCNO_REGNO (from));
 948       bitmap_clear_bit (live_through, ALLOCNO_REGNO (to));
 949
 950       nr = ALLOCNO_NUM_OBJECTS (to);
 951       for (i = 0; i < nr; i++)
 952         {
 953           ira_object_t to_obj = ALLOCNO_OBJECT (to, i);
 954           if (OBJECT_CONFLICT_ARRAY (to_obj) == NULL)
 955             {
 956               if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
 957                 fprintf (ira_dump_file, "    Allocate conflicts for a%dr%d\n",
 958                          ALLOCNO_NUM (to), REGNO (ALLOCNO_REG (to)));
 959               ira_allocate_object_conflicts (to_obj, n);
 960             }
 961         }
 962       ior_hard_reg_conflicts (from, &hard_regs_live);
 963       ior_hard_reg_conflicts (to, &hard_regs_live);
 964
 965       update_costs (from, true, freq);
 966       update_costs (to, false, freq);
 967       cp = ira_add_allocno_copy (from, to, freq, false, move->insn, NULL);
 968       if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
 969         fprintf (ira_dump_file, "    Adding cp%d:a%dr%d-a%dr%d\n",
 970                  cp->num, ALLOCNO_NUM (cp->first),
 971                  REGNO (ALLOCNO_REG (cp->first)), ALLOCNO_NUM (cp->second),
 972                  REGNO (ALLOCNO_REG (cp->second)));
 973
 974       nr = ALLOCNO_NUM_OBJECTS (from);
 975       for (i = 0; i < nr; i++)
 976         {
 977           ira_object_t from_obj = ALLOCNO_OBJECT (from, i);
 978           r = OBJECT_LIVE_RANGES (from_obj);
 979           if (r == NULL || r->finish >= 0)
 980             {
 981               ira_add_live_range_to_object (from_obj, start, ira_max_point);
 982               if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
 983                 fprintf (ira_dump_file,
 984                          "    Adding range [%d..%d] to allocno a%dr%d\n",
 985                          start, ira_max_point, ALLOCNO_NUM (from),
 986                          REGNO (ALLOCNO_REG (from)));
 987             }
 988           else
 989             {
 990               r->finish = ira_max_point;
 991               if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
 992                 fprintf (ira_dump_file,
 993                          "    Adding range [%d..%d] to allocno a%dr%d\n",
 994                          r->start, ira_max_point, ALLOCNO_NUM (from),
 995                          REGNO (ALLOCNO_REG (from)));
 996             }
 997         }
 998       ira_max_point++;
 999       nr = ALLOCNO_NUM_OBJECTS (to);
1000       for (i = 0; i < nr; i++)
1001         {
1002           ira_object_t to_obj = ALLOCNO_OBJECT (to, i);
1003           ira_add_live_range_to_object (to_obj, ira_max_point, -1);
1004         }
1005       ira_max_point++;
1006     }
1007   for (move = list; move != NULL; move = move->next)
1008     {
1009       int nr, i;
1010       nr = ALLOCNO_NUM_OBJECTS (move->to);
1011       for (i = 0; i < nr; i++)
1012         {
1013           ira_object_t to_obj = ALLOCNO_OBJECT (move->to, i);
1014           r = OBJECT_LIVE_RANGES (to_obj);
1015           if (r->finish < 0)
1016             {
1017               r->finish = ira_max_point - 1;
1018               if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
1019                 fprintf (ira_dump_file,
1020                          "    Adding range [%d..%d] to allocno a%dr%d\n",
1021                          r->start, r->finish, ALLOCNO_NUM (move->to),
1022                          REGNO (ALLOCNO_REG (move->to)));
1023             }
1024         }
1025     }
1026   EXECUTE_IF_SET_IN_BITMAP (live_through, FIRST_PSEUDO_REGISTER, regno, bi)
1027     {
1028       ira_allocno_t to;
1029       int nr, i;
1030
1031       a = node->regno_allocno_map[regno];
1032       if ((to = ALLOCNO_MEM_OPTIMIZED_DEST (a)) != NULL)
1033         a = to;
1034       nr = ALLOCNO_NUM_OBJECTS (a);
1035       for (i = 0; i < nr; i++)
1036         {
1037           ira_object_t obj = ALLOCNO_OBJECT (a, i);
1038           ira_add_live_range_to_object (obj, start, ira_max_point - 1);
1039         }
1040       if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
1041         fprintf
1042           (ira_dump_file,
1043            "    Adding range [%d..%d] to live through %s allocno a%dr%d\n",
1044            start, ira_max_point - 1,
1045            to != NULL ? "upper level" : "",
1046            ALLOCNO_NUM (a), REGNO (ALLOCNO_REG (a)));
1047     }
1048 }
1049
1050 /* Process all move list to add ranges, conflicts, copies, and modify
1051    costs for allocnos involved in the moves.  */
1052 static void
1053 add_ranges_and_copies (void)
1054 {
1055   basic_block bb;
1056   edge_iterator ei;
1057   edge e;
1058   ira_loop_tree_node_t node;
1059   bitmap live_through;
1060
1061   live_through = ira_allocate_bitmap ();
1062   FOR_EACH_BB (bb)
1063     {
1064       /* It does not matter what loop_tree_node (of source or
1065          destination block) to use for searching allocnos by their
1066          regnos because of subsequent IR flattening.  */
1067       node = IRA_BB_NODE (bb)->parent;
1068       bitmap_copy (live_through, DF_LR_IN (bb));
1069       add_range_and_copies_from_move_list
1070         (at_bb_start[bb->index], node, live_through, REG_FREQ_FROM_BB (bb));
1071       bitmap_copy (live_through, DF_LR_OUT (bb));
1072       add_range_and_copies_from_move_list
1073         (at_bb_end[bb->index], node, live_through, REG_FREQ_FROM_BB (bb));
1074       FOR_EACH_EDGE (e, ei, bb->succs)
1075         {
1076           bitmap_and (live_through, DF_LR_IN (e->dest), DF_LR_OUT (bb));
1077           add_range_and_copies_from_move_list
1078             ((move_t) e->aux, node, live_through,
1079              REG_FREQ_FROM_EDGE_FREQ (EDGE_FREQUENCY (e)));
1080         }
1081     }
1082   ira_free_bitmap (live_through);
1083 }
1084
1085 /* The entry function changes code and generates shuffling allocnos on
1086    region borders for the regional (LOOPS_P is TRUE in this case)
1087    register allocation.  */
1088 void
1089 ira_emit (bool loops_p)
1090 {
1091   basic_block bb;
1092   rtx insn;
1093   edge_iterator ei;
1094   edge e;
1095   ira_allocno_t a;
1096   ira_allocno_iterator ai;
1097
1098   FOR_EACH_ALLOCNO (a, ai)
1099     ALLOCNO_REG (a) = regno_reg_rtx[ALLOCNO_REGNO (a)];
1100   if (! loops_p)
1101     return;
1102   at_bb_start = (move_t *) ira_allocate (sizeof (move_t) * last_basic_block);
1103   memset (at_bb_start, 0, sizeof (move_t) * last_basic_block);
1104   at_bb_end = (move_t *) ira_allocate (sizeof (move_t) * last_basic_block);
1105   memset (at_bb_end, 0, sizeof (move_t) * last_basic_block);
1106   local_allocno_bitmap = ira_allocate_bitmap ();
1107   used_regno_bitmap = ira_allocate_bitmap ();
1108   renamed_regno_bitmap = ira_allocate_bitmap ();
1109   max_regno_before_changing = max_reg_num ();
1110   ira_traverse_loop_tree (true, ira_loop_tree_root, change_loop, NULL);
1111   set_allocno_somewhere_renamed_p ();
1112   ira_free_bitmap (used_regno_bitmap);
1113   ira_free_bitmap (renamed_regno_bitmap);
1114   ira_free_bitmap (local_allocno_bitmap);
1115   setup_entered_from_non_parent_p ();
1116   FOR_EACH_BB (bb)
1117     {
1118       at_bb_start[bb->index] = NULL;
1119       at_bb_end[bb->index] = NULL;
1120       FOR_EACH_EDGE (e, ei, bb->succs)
1121         if (e->dest != EXIT_BLOCK_PTR)
1122           generate_edge_moves (e);
1123     }
1124   allocno_last_set
1125     = (move_t *) ira_allocate (sizeof (move_t) * max_reg_num ());
1126   allocno_last_set_check
1127     = (int *) ira_allocate (sizeof (int) * max_reg_num ());
1128   memset (allocno_last_set_check, 0, sizeof (int) * max_reg_num ());
1129   memset (hard_regno_last_set_check, 0, sizeof (hard_regno_last_set_check));
1130   curr_tick = 0;
1131   FOR_EACH_BB (bb)
1132     unify_moves (bb, true);
1133   FOR_EACH_BB (bb)
1134     unify_moves (bb, false);
1135   move_vec = VEC_alloc (move_t, heap, ira_allocnos_num);
1136   emit_moves ();
1137   add_ranges_and_copies ();
1138   /* Clean up: */
1139   FOR_EACH_BB (bb)
1140     {
1141       free_move_list (at_bb_start[bb->index]);
1142       free_move_list (at_bb_end[bb->index]);
1143       FOR_EACH_EDGE (e, ei, bb->succs)
1144         {
1145           free_move_list ((move_t) e->aux);
1146           e->aux = NULL;
1147         }
1148     }
1149   VEC_free (move_t, heap, move_vec);
1150   ira_free (allocno_last_set_check);
1151   ira_free (allocno_last_set);
1152   commit_edge_insertions ();
1153   /* Fix insn codes.  It is necessary to do it before reload because
1154      reload assumes initial insn codes defined.  The insn codes can be
1155      invalidated by CFG infrastructure for example in jump
1156      redirection.  */
1157   FOR_EACH_BB (bb)
1158     FOR_BB_INSNS_REVERSE (bb, insn)
1159       if (INSN_P (insn))
1160         recog_memoized (insn);
1161   ira_free (at_bb_end);
1162   ira_free (at_bb_start);
1163 }