contrib/gcc-4.4/gcc/ira-emit.c

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