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