LCOV - code coverage report
Current view: top level - gcc - ira-build.c (source / functions) Hit Total Coverage
Test: gcc.info Lines: 1361 1903 71.5 %
Date: 2020-04-04 11:58:09 Functions: 82 116 70.7 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 0 0 -

           Branch data     Line data    Source code
       1                 :            : /* Building internal representation for IRA.
       2                 :            :    Copyright (C) 2006-2020 Free Software Foundation, Inc.
       3                 :            :    Contributed by Vladimir Makarov <vmakarov@redhat.com>.
       4                 :            : 
       5                 :            : This file is part of GCC.
       6                 :            : 
       7                 :            : GCC is free software; you can redistribute it and/or modify it under
       8                 :            : the terms of the GNU General Public License as published by the Free
       9                 :            : Software Foundation; either version 3, or (at your option) any later
      10                 :            : version.
      11                 :            : 
      12                 :            : GCC is distributed in the hope that it will be useful, but WITHOUT ANY
      13                 :            : WARRANTY; without even the implied warranty of MERCHANTABILITY or
      14                 :            : FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
      15                 :            : for more details.
      16                 :            : 
      17                 :            : You should have received a copy of the GNU General Public License
      18                 :            : along with GCC; see the file COPYING3.  If not see
      19                 :            : <http://www.gnu.org/licenses/>.  */
      20                 :            : 
      21                 :            : #include "config.h"
      22                 :            : #include "system.h"
      23                 :            : #include "coretypes.h"
      24                 :            : #include "backend.h"
      25                 :            : #include "target.h"
      26                 :            : #include "rtl.h"
      27                 :            : #include "predict.h"
      28                 :            : #include "df.h"
      29                 :            : #include "insn-config.h"
      30                 :            : #include "regs.h"
      31                 :            : #include "memmodel.h"
      32                 :            : #include "ira.h"
      33                 :            : #include "ira-int.h"
      34                 :            : #include "sparseset.h"
      35                 :            : #include "cfgloop.h"
      36                 :            : 
      37                 :            : static ira_copy_t find_allocno_copy (ira_allocno_t, ira_allocno_t, rtx_insn *,
      38                 :            :                                      ira_loop_tree_node_t);
      39                 :            : 
      40                 :            : /* The root of the loop tree corresponding to the all function.  */
      41                 :            : ira_loop_tree_node_t ira_loop_tree_root;
      42                 :            : 
      43                 :            : /* Height of the loop tree.  */
      44                 :            : int ira_loop_tree_height;
      45                 :            : 
      46                 :            : /* All nodes representing basic blocks are referred through the
      47                 :            :    following array.  We cannot use basic block member `aux' for this
      48                 :            :    because it is used for insertion of insns on edges.  */
      49                 :            : ira_loop_tree_node_t ira_bb_nodes;
      50                 :            : 
      51                 :            : /* All nodes representing loops are referred through the following
      52                 :            :    array.  */
      53                 :            : ira_loop_tree_node_t ira_loop_nodes;
      54                 :            : 
      55                 :            : /* And size of the ira_loop_nodes array.  */
      56                 :            : unsigned int ira_loop_nodes_count;
      57                 :            : 
      58                 :            : /* Map regno -> allocnos with given regno (see comments for
      59                 :            :    allocno member `next_regno_allocno').  */
      60                 :            : ira_allocno_t *ira_regno_allocno_map;
      61                 :            : 
      62                 :            : /* Array of references to all allocnos.  The order number of the
      63                 :            :    allocno corresponds to the index in the array.  Removed allocnos
      64                 :            :    have NULL element value.  */
      65                 :            : ira_allocno_t *ira_allocnos;
      66                 :            : 
      67                 :            : /* Sizes of the previous array.  */
      68                 :            : int ira_allocnos_num;
      69                 :            : 
      70                 :            : /* Count of conflict record structures we've created, used when creating
      71                 :            :    a new conflict id.  */
      72                 :            : int ira_objects_num;
      73                 :            : 
      74                 :            : /* Map a conflict id to its conflict record.  */
      75                 :            : ira_object_t *ira_object_id_map;
      76                 :            : 
      77                 :            : /* Array of references to all allocno preferences.  The order number
      78                 :            :    of the preference corresponds to the index in the array.  */
      79                 :            : ira_pref_t *ira_prefs;
      80                 :            : 
      81                 :            : /* Size of the previous array.  */
      82                 :            : int ira_prefs_num;
      83                 :            : 
      84                 :            : /* Array of references to all copies.  The order number of the copy
      85                 :            :    corresponds to the index in the array.  Removed copies have NULL
      86                 :            :    element value.  */
      87                 :            : ira_copy_t *ira_copies;
      88                 :            : 
      89                 :            : /* Size of the previous array.  */
      90                 :            : int ira_copies_num;
      91                 :            : 
      92                 :            : 
      93                 :            : 
      94                 :            : /* LAST_BASIC_BLOCK before generating additional insns because of live
      95                 :            :    range splitting.  Emitting insns on a critical edge creates a new
      96                 :            :    basic block.  */
      97                 :            : static int last_basic_block_before_change;
      98                 :            : 
      99                 :            : /* Initialize some members in loop tree node NODE.  Use LOOP_NUM for
     100                 :            :    the member loop_num.  */
     101                 :            : static void
     102                 :    1269780 : init_loop_tree_node (struct ira_loop_tree_node *node, int loop_num)
     103                 :            : {
     104                 :    1269780 :   int max_regno = max_reg_num ();
     105                 :            : 
     106                 :    1269780 :   node->regno_allocno_map
     107                 :    1269780 :     = (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t) * max_regno);
     108                 :    1269780 :   memset (node->regno_allocno_map, 0, sizeof (ira_allocno_t) * max_regno);
     109                 :    1269780 :   memset (node->reg_pressure, 0, sizeof (node->reg_pressure));
     110                 :    1269780 :   node->all_allocnos = ira_allocate_bitmap ();
     111                 :    1269780 :   node->modified_regnos = ira_allocate_bitmap ();
     112                 :    1269780 :   node->border_allocnos = ira_allocate_bitmap ();
     113                 :    1269780 :   node->local_copies = ira_allocate_bitmap ();
     114                 :    1269780 :   node->loop_num = loop_num;
     115                 :    1269780 :   node->children = NULL;
     116                 :    1269780 :   node->subloops = NULL;
     117                 :    1269780 : }
     118                 :            : 
     119                 :            : 
     120                 :            : /* The following function allocates the loop tree nodes.  If
     121                 :            :    CURRENT_LOOPS is NULL, the nodes corresponding to the loops (except
     122                 :            :    the root which corresponds the all function) will be not allocated
     123                 :            :    but nodes will still be allocated for basic blocks.  */
     124                 :            : static void
     125                 :     944096 : create_loop_tree_nodes (void)
     126                 :            : {
     127                 :     944096 :   unsigned int i, j;
     128                 :     944096 :   bool skip_p;
     129                 :     944096 :   edge_iterator ei;
     130                 :     944096 :   edge e;
     131                 :     944096 :   vec<edge> edges;
     132                 :     944096 :   loop_p loop;
     133                 :            : 
     134                 :     944096 :   ira_bb_nodes
     135                 :     944096 :     = ((struct ira_loop_tree_node *)
     136                 :     944096 :        ira_allocate (sizeof (struct ira_loop_tree_node)
     137                 :     944096 :                      * last_basic_block_for_fn (cfun)));
     138                 :     944096 :   last_basic_block_before_change = last_basic_block_for_fn (cfun);
     139                 :   11912000 :   for (i = 0; i < (unsigned int) last_basic_block_for_fn (cfun); i++)
     140                 :            :     {
     141                 :   10967900 :       ira_bb_nodes[i].regno_allocno_map = NULL;
     142                 :   10967900 :       memset (ira_bb_nodes[i].reg_pressure, 0,
     143                 :            :               sizeof (ira_bb_nodes[i].reg_pressure));
     144                 :   10967900 :       ira_bb_nodes[i].all_allocnos = NULL;
     145                 :   10967900 :       ira_bb_nodes[i].modified_regnos = NULL;
     146                 :   10967900 :       ira_bb_nodes[i].border_allocnos = NULL;
     147                 :   10967900 :       ira_bb_nodes[i].local_copies = NULL;
     148                 :            :     }
     149                 :     944096 :   if (current_loops == NULL)
     150                 :            :     {
     151                 :     283761 :       ira_loop_nodes_count = 1;
     152                 :     567522 :       ira_loop_nodes = ((struct ira_loop_tree_node *)
     153                 :     283761 :                         ira_allocate (sizeof (struct ira_loop_tree_node)));
     154                 :     283761 :       init_loop_tree_node (ira_loop_nodes, 0);
     155                 :     283761 :       return;
     156                 :            :     }
     157                 :     660335 :   ira_loop_nodes_count = number_of_loops (cfun);
     158                 :    1320670 :   ira_loop_nodes = ((struct ira_loop_tree_node *)
     159                 :     660335 :                     ira_allocate (sizeof (struct ira_loop_tree_node)
     160                 :     660335 :                                   * ira_loop_nodes_count));
     161                 :    2316940 :   FOR_EACH_VEC_SAFE_ELT (get_loops (cfun), i, loop)
     162                 :            :     {
     163                 :    1332210 :       if (loop_outer (loop) != NULL)
     164                 :            :         {
     165                 :     335939 :           ira_loop_nodes[i].regno_allocno_map = NULL;
     166                 :     335939 :           skip_p = false;
     167                 :    1048250 :           FOR_EACH_EDGE (e, ei, loop->header->preds)
     168                 :     712308 :             if (e->src != loop->latch
     169                 :     712308 :                 && (e->flags & EDGE_ABNORMAL) && EDGE_CRITICAL_P (e))
     170                 :            :               {
     171                 :            :                 skip_p = true;
     172                 :            :                 break;
     173                 :            :               }
     174                 :     335939 :           if (skip_p)
     175                 :          0 :             continue;
     176                 :     335939 :           edges = get_loop_exit_edges (loop);
     177                 :    1265520 :           FOR_EACH_VEC_ELT (edges, j, e)
     178                 :     618744 :             if ((e->flags & EDGE_ABNORMAL) && EDGE_CRITICAL_P (e))
     179                 :            :               {
     180                 :            :                 skip_p = true;
     181                 :            :                 break;
     182                 :            :               }
     183                 :     335939 :           edges.release ();
     184                 :     335939 :           if (skip_p)
     185                 :      10251 :             continue;
     186                 :            :         }
     187                 :     986023 :       init_loop_tree_node (&ira_loop_nodes[i], loop->num);
     188                 :            :     }
     189                 :            : }
     190                 :            : 
     191                 :            : /* The function returns TRUE if there are more one allocation
     192                 :            :    region.  */
     193                 :            : static bool
     194                 :     944096 : more_one_region_p (void)
     195                 :            : {
     196                 :     944096 :   unsigned int i;
     197                 :     944096 :   loop_p loop;
     198                 :            : 
     199                 :     944096 :   if (current_loops != NULL)
     200                 :    1547040 :     FOR_EACH_VEC_SAFE_ELT (get_loops (cfun), i, loop)
     201                 :     912128 :       if (ira_loop_nodes[i].regno_allocno_map != NULL
     202                 :     685755 :           && ira_loop_tree_root != &ira_loop_nodes[i])
     203                 :            :         return true;
     204                 :            :   return false;
     205                 :            : }
     206                 :            : 
     207                 :            : /* Free the loop tree node of a loop.  */
     208                 :            : static void
     209                 :    1501280 : finish_loop_tree_node (ira_loop_tree_node_t loop)
     210                 :            : {
     211                 :    1501280 :   if (loop->regno_allocno_map != NULL)
     212                 :            :     {
     213                 :    1269780 :       ira_assert (loop->bb == NULL);
     214                 :    1269780 :       ira_free_bitmap (loop->local_copies);
     215                 :    1269780 :       ira_free_bitmap (loop->border_allocnos);
     216                 :    1269780 :       ira_free_bitmap (loop->modified_regnos);
     217                 :    1269780 :       ira_free_bitmap (loop->all_allocnos);
     218                 :    1269780 :       ira_free (loop->regno_allocno_map);
     219                 :    1269780 :       loop->regno_allocno_map = NULL;
     220                 :            :     }
     221                 :    1501280 : }
     222                 :            : 
     223                 :            : /* Free the loop tree nodes.  */
     224                 :            : static void
     225                 :     944096 : finish_loop_tree_nodes (void)
     226                 :            : {
     227                 :     944096 :   unsigned int i;
     228                 :            : 
     229                 :    2224130 :   for (i = 0; i < ira_loop_nodes_count; i++)
     230                 :    1280040 :     finish_loop_tree_node (&ira_loop_nodes[i]);
     231                 :     944096 :   ira_free (ira_loop_nodes);
     232                 :   11912000 :   for (i = 0; i < (unsigned int) last_basic_block_before_change; i++)
     233                 :            :     {
     234                 :   10967900 :       if (ira_bb_nodes[i].local_copies != NULL)
     235                 :          0 :         ira_free_bitmap (ira_bb_nodes[i].local_copies);
     236                 :   10967900 :       if (ira_bb_nodes[i].border_allocnos != NULL)
     237                 :          0 :         ira_free_bitmap (ira_bb_nodes[i].border_allocnos);
     238                 :   10967900 :       if (ira_bb_nodes[i].modified_regnos != NULL)
     239                 :          0 :         ira_free_bitmap (ira_bb_nodes[i].modified_regnos);
     240                 :   10967900 :       if (ira_bb_nodes[i].all_allocnos != NULL)
     241                 :          0 :         ira_free_bitmap (ira_bb_nodes[i].all_allocnos);
     242                 :   10967900 :       if (ira_bb_nodes[i].regno_allocno_map != NULL)
     243                 :          0 :         ira_free (ira_bb_nodes[i].regno_allocno_map);
     244                 :            :     }
     245                 :     944096 :   ira_free (ira_bb_nodes);
     246                 :     944096 : }
     247                 :            : 
     248                 :            : 
     249                 :            : 
     250                 :            : /* The following recursive function adds LOOP to the loop tree
     251                 :            :    hierarchy.  LOOP is added only once.  If LOOP is NULL we adding
     252                 :            :    loop designating the whole function when CFG loops are not
     253                 :            :    built.  */
     254                 :            : static void
     255                 :   10968900 : add_loop_to_tree (class loop *loop)
     256                 :            : {
     257                 :   10968900 :   int loop_num;
     258                 :   10968900 :   class loop *parent;
     259                 :   10968900 :   ira_loop_tree_node_t loop_node, parent_node;
     260                 :            : 
     261                 :            :   /* We cannot use loop node access macros here because of potential
     262                 :            :      checking and because the nodes are not initialized enough
     263                 :            :      yet.  */
     264                 :   12861800 :   if (loop != NULL && loop_outer (loop) != NULL)
     265                 :    1892870 :     add_loop_to_tree (loop_outer (loop));
     266                 :   10968900 :   loop_num = loop != NULL ? loop->num : 0;
     267                 :   10968900 :   if (ira_loop_nodes[loop_num].regno_allocno_map != NULL
     268                 :   10960300 :       && ira_loop_nodes[loop_num].children == NULL)
     269                 :            :     {
     270                 :            :       /* We have not added loop node to the tree yet.  */
     271                 :    1269780 :       loop_node = &ira_loop_nodes[loop_num];
     272                 :    1269780 :       loop_node->loop = loop;
     273                 :    1269780 :       loop_node->bb = NULL;
     274                 :    1269780 :       if (loop == NULL)
     275                 :            :         parent = NULL;
     276                 :            :       else
     277                 :            :         {
     278                 :     986023 :           for (parent = loop_outer (loop);
     279                 :     988367 :                parent != NULL;
     280                 :       4688 :                parent = loop_outer (parent))
     281                 :     328032 :             if (ira_loop_nodes[parent->num].regno_allocno_map != NULL)
     282                 :            :               break;
     283                 :            :         }
     284                 :     986023 :       if (parent == NULL)
     285                 :            :         {
     286                 :     944096 :           loop_node->next = NULL;
     287                 :     944096 :           loop_node->subloop_next = NULL;
     288                 :     944096 :           loop_node->parent = NULL;
     289                 :            :         }
     290                 :            :       else
     291                 :            :         {
     292                 :     325688 :           parent_node = &ira_loop_nodes[parent->num];
     293                 :     325688 :           loop_node->next = parent_node->children;
     294                 :     325688 :           parent_node->children = loop_node;
     295                 :     325688 :           loop_node->subloop_next = parent_node->subloops;
     296                 :     325688 :           parent_node->subloops = loop_node;
     297                 :     325688 :           loop_node->parent = parent_node;
     298                 :            :         }
     299                 :            :     }
     300                 :   10968900 : }
     301                 :            : 
     302                 :            : /* The following recursive function sets up levels of nodes of the
     303                 :            :    tree given its root LOOP_NODE.  The enumeration starts with LEVEL.
     304                 :            :    The function returns maximal value of level in the tree + 1.  */
     305                 :            : static int
     306                 :    1269780 : setup_loop_tree_level (ira_loop_tree_node_t loop_node, int level)
     307                 :            : {
     308                 :    1269780 :   int height, max_height;
     309                 :    1269780 :   ira_loop_tree_node_t subloop_node;
     310                 :            : 
     311                 :    1269780 :   ira_assert (loop_node->bb == NULL);
     312                 :    1269780 :   loop_node->level = level;
     313                 :    1269780 :   max_height = level + 1;
     314                 :    1269780 :   for (subloop_node = loop_node->subloops;
     315                 :    1595470 :        subloop_node != NULL;
     316                 :     325688 :        subloop_node = subloop_node->subloop_next)
     317                 :            :     {
     318                 :     325688 :       ira_assert (subloop_node->bb == NULL);
     319                 :     325688 :       height = setup_loop_tree_level (subloop_node, level + 1);
     320                 :     325688 :       if (height > max_height)
     321                 :            :         max_height = height;
     322                 :            :     }
     323                 :    1269780 :   return max_height;
     324                 :            : }
     325                 :            : 
     326                 :            : /* Create the loop tree.  The algorithm is designed to provide correct
     327                 :            :    order of loops (they are ordered by their last loop BB) and basic
     328                 :            :    blocks in the chain formed by member next.  */
     329                 :            : static void
     330                 :     944096 : form_loop_tree (void)
     331                 :            : {
     332                 :     944096 :   basic_block bb;
     333                 :     944096 :   class loop *parent;
     334                 :     944096 :   ira_loop_tree_node_t bb_node, loop_node;
     335                 :            : 
     336                 :            :   /* We cannot use loop/bb node access macros because of potential
     337                 :            :      checking and because the nodes are not initialized enough
     338                 :            :      yet.  */
     339                 :   10020200 :   FOR_EACH_BB_FN (bb, cfun)
     340                 :            :     {
     341                 :    9076070 :       bb_node = &ira_bb_nodes[bb->index];
     342                 :    9076070 :       bb_node->bb = bb;
     343                 :    9076070 :       bb_node->loop = NULL;
     344                 :    9076070 :       bb_node->subloops = NULL;
     345                 :    9076070 :       bb_node->children = NULL;
     346                 :    9076070 :       bb_node->subloop_next = NULL;
     347                 :    9076070 :       bb_node->next = NULL;
     348                 :    9076070 :       if (current_loops == NULL)
     349                 :            :         parent = NULL;
     350                 :            :       else
     351                 :            :         {
     352                 :    6776020 :           for (parent = bb->loop_father;
     353                 :    6989890 :                parent != NULL;
     354                 :     427750 :                parent = loop_outer (parent))
     355                 :    6989890 :             if (ira_loop_nodes[parent->num].regno_allocno_map != NULL)
     356                 :            :               break;
     357                 :            :         }
     358                 :    9076070 :       add_loop_to_tree (parent);
     359                 :    9076070 :       loop_node = &ira_loop_nodes[parent == NULL ? 0 : parent->num];
     360                 :    9076070 :       bb_node->next = loop_node->children;
     361                 :    9076070 :       bb_node->parent = loop_node;
     362                 :    9076070 :       loop_node->children = bb_node;
     363                 :            :     }
     364                 :     944096 :   ira_loop_tree_root = IRA_LOOP_NODE_BY_INDEX (0);
     365                 :     944096 :   ira_loop_tree_height = setup_loop_tree_level (ira_loop_tree_root, 0);
     366                 :     944096 :   ira_assert (ira_loop_tree_root->regno_allocno_map != NULL);
     367                 :     944096 : }
     368                 :            : 
     369                 :            : 
     370                 :            : 
     371                 :            : /* Rebuild IRA_REGNO_ALLOCNO_MAP and REGNO_ALLOCNO_MAPs of the loop
     372                 :            :    tree nodes.  */
     373                 :            : static void
     374                 :          0 : rebuild_regno_allocno_maps (void)
     375                 :            : {
     376                 :          0 :   unsigned int l;
     377                 :          0 :   int max_regno, regno;
     378                 :          0 :   ira_allocno_t a;
     379                 :          0 :   ira_loop_tree_node_t loop_tree_node;
     380                 :          0 :   loop_p loop;
     381                 :          0 :   ira_allocno_iterator ai;
     382                 :            : 
     383                 :          0 :   ira_assert (current_loops != NULL);
     384                 :          0 :   max_regno = max_reg_num ();
     385                 :          0 :   FOR_EACH_VEC_SAFE_ELT (get_loops (cfun), l, loop)
     386                 :          0 :     if (ira_loop_nodes[l].regno_allocno_map != NULL)
     387                 :            :       {
     388                 :          0 :         ira_free (ira_loop_nodes[l].regno_allocno_map);
     389                 :          0 :         ira_loop_nodes[l].regno_allocno_map
     390                 :          0 :           = (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t)
     391                 :          0 :                                             * max_regno);
     392                 :          0 :         memset (ira_loop_nodes[l].regno_allocno_map, 0,
     393                 :            :                 sizeof (ira_allocno_t) * max_regno);
     394                 :            :       }
     395                 :          0 :   ira_free (ira_regno_allocno_map);
     396                 :          0 :   ira_regno_allocno_map
     397                 :          0 :     = (ira_allocno_t *) ira_allocate (max_regno * sizeof (ira_allocno_t));
     398                 :          0 :   memset (ira_regno_allocno_map, 0, max_regno * sizeof (ira_allocno_t));
     399                 :          0 :   FOR_EACH_ALLOCNO (a, ai)
     400                 :            :     {
     401                 :          0 :       if (ALLOCNO_CAP_MEMBER (a) != NULL)
     402                 :            :         /* Caps are not in the regno allocno maps.  */
     403                 :          0 :         continue;
     404                 :          0 :       regno = ALLOCNO_REGNO (a);
     405                 :          0 :       loop_tree_node = ALLOCNO_LOOP_TREE_NODE (a);
     406                 :          0 :       ALLOCNO_NEXT_REGNO_ALLOCNO (a) = ira_regno_allocno_map[regno];
     407                 :          0 :       ira_regno_allocno_map[regno] = a;
     408                 :          0 :       if (loop_tree_node->regno_allocno_map[regno] == NULL)
     409                 :            :         /* Remember that we can create temporary allocnos to break
     410                 :            :            cycles in register shuffle.  */
     411                 :          0 :         loop_tree_node->regno_allocno_map[regno] = a;
     412                 :            :     }
     413                 :          0 : }
     414                 :            : 
     415                 :            : 
     416                 :            : /* Pools for allocnos, allocno live ranges and objects.  */
     417                 :            : static object_allocator<live_range> live_range_pool ("live ranges");
     418                 :            : static object_allocator<ira_allocno> allocno_pool ("allocnos");
     419                 :            : static object_allocator<ira_object> object_pool ("objects");
     420                 :            : 
     421                 :            : /* Vec containing references to all created allocnos.  It is a
     422                 :            :    container of array allocnos.  */
     423                 :            : static vec<ira_allocno_t> allocno_vec;
     424                 :            : 
     425                 :            : /* Vec containing references to all created ira_objects.  It is a
     426                 :            :    container of ira_object_id_map.  */
     427                 :            : static vec<ira_object_t> ira_object_id_map_vec;
     428                 :            : 
     429                 :            : /* Initialize data concerning allocnos.  */
     430                 :            : static void
     431                 :     944096 : initiate_allocnos (void)
     432                 :            : {
     433                 :     944096 :   allocno_vec.create (max_reg_num () * 2);
     434                 :     944096 :   ira_allocnos = NULL;
     435                 :     944096 :   ira_allocnos_num = 0;
     436                 :     944096 :   ira_objects_num = 0;
     437                 :     944096 :   ira_object_id_map_vec.create (max_reg_num () * 2);
     438                 :     944096 :   ira_object_id_map = NULL;
     439                 :     944096 :   ira_regno_allocno_map
     440                 :     944096 :     = (ira_allocno_t *) ira_allocate (max_reg_num ()
     441                 :            :                                       * sizeof (ira_allocno_t));
     442                 :     944096 :   memset (ira_regno_allocno_map, 0, max_reg_num () * sizeof (ira_allocno_t));
     443                 :     944096 : }
     444                 :            : 
     445                 :            : /* Create and return an object corresponding to a new allocno A.  */
     446                 :            : static ira_object_t
     447                 :   24658600 : ira_create_object (ira_allocno_t a, int subword)
     448                 :            : {
     449                 :   24658600 :   enum reg_class aclass = ALLOCNO_CLASS (a);
     450                 :   24658600 :   ira_object_t obj = object_pool.allocate ();
     451                 :            : 
     452                 :   24658600 :   OBJECT_ALLOCNO (obj) = a;
     453                 :   24658600 :   OBJECT_SUBWORD (obj) = subword;
     454                 :   24658600 :   OBJECT_CONFLICT_ID (obj) = ira_objects_num;
     455                 :   24658600 :   OBJECT_CONFLICT_VEC_P (obj) = false;
     456                 :   24658600 :   OBJECT_CONFLICT_ARRAY (obj) = NULL;
     457                 :   24658600 :   OBJECT_NUM_CONFLICTS (obj) = 0;
     458                 :   24658600 :   OBJECT_CONFLICT_HARD_REGS (obj) = ira_no_alloc_regs;
     459                 :   24658600 :   OBJECT_TOTAL_CONFLICT_HARD_REGS (obj) = ira_no_alloc_regs;
     460                 :   49317100 :   OBJECT_CONFLICT_HARD_REGS (obj) |= ~reg_class_contents[aclass];
     461                 :   49317100 :   OBJECT_TOTAL_CONFLICT_HARD_REGS (obj) |= ~reg_class_contents[aclass];
     462                 :   24658600 :   OBJECT_MIN (obj) = INT_MAX;
     463                 :   24658600 :   OBJECT_MAX (obj) = -1;
     464                 :   24658600 :   OBJECT_LIVE_RANGES (obj) = NULL;
     465                 :            : 
     466                 :   24658600 :   ira_object_id_map_vec.safe_push (obj);
     467                 :   24658600 :   ira_object_id_map
     468                 :   24658600 :     = ira_object_id_map_vec.address ();
     469                 :   24658600 :   ira_objects_num = ira_object_id_map_vec.length ();
     470                 :            : 
     471                 :   24658600 :   return obj;
     472                 :            : }
     473                 :            : 
     474                 :            : /* Create and return the allocno corresponding to REGNO in
     475                 :            :    LOOP_TREE_NODE.  Add the allocno to the list of allocnos with the
     476                 :            :    same regno if CAP_P is FALSE.  */
     477                 :            : ira_allocno_t
     478                 :   24105500 : ira_create_allocno (int regno, bool cap_p,
     479                 :            :                     ira_loop_tree_node_t loop_tree_node)
     480                 :            : {
     481                 :   24105500 :   ira_allocno_t a;
     482                 :            : 
     483                 :   24105500 :   a = allocno_pool.allocate ();
     484                 :   24105500 :   ALLOCNO_REGNO (a) = regno;
     485                 :   24105500 :   ALLOCNO_LOOP_TREE_NODE (a) = loop_tree_node;
     486                 :   24105500 :   if (! cap_p)
     487                 :            :     {
     488                 :   21304500 :       ALLOCNO_NEXT_REGNO_ALLOCNO (a) = ira_regno_allocno_map[regno];
     489                 :   21304500 :       ira_regno_allocno_map[regno] = a;
     490                 :   21304500 :       if (loop_tree_node->regno_allocno_map[regno] == NULL)
     491                 :            :         /* Remember that we can create temporary allocnos to break
     492                 :            :            cycles in register shuffle on region borders (see
     493                 :            :            ira-emit.c).  */
     494                 :   21302000 :         loop_tree_node->regno_allocno_map[regno] = a;
     495                 :            :     }
     496                 :   24105500 :   ALLOCNO_CAP (a) = NULL;
     497                 :   24105500 :   ALLOCNO_CAP_MEMBER (a) = NULL;
     498                 :   24105500 :   ALLOCNO_NUM (a) = ira_allocnos_num;
     499                 :   24105500 :   bitmap_set_bit (loop_tree_node->all_allocnos, ALLOCNO_NUM (a));
     500                 :   24105500 :   ALLOCNO_NREFS (a) = 0;
     501                 :   24105500 :   ALLOCNO_FREQ (a) = 0;
     502                 :   24105500 :   ALLOCNO_HARD_REGNO (a) = -1;
     503                 :   24105500 :   ALLOCNO_CALL_FREQ (a) = 0;
     504                 :   24105500 :   ALLOCNO_CALLS_CROSSED_NUM (a) = 0;
     505                 :   24105500 :   ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a) = 0;
     506                 :   24105500 :   ALLOCNO_CROSSED_CALLS_ABIS (a) = 0;
     507                 :   24105500 :   CLEAR_HARD_REG_SET (ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS (a));
     508                 :            : #ifdef STACK_REGS
     509                 :   24105500 :   ALLOCNO_NO_STACK_REG_P (a) = false;
     510                 :   24105500 :   ALLOCNO_TOTAL_NO_STACK_REG_P (a) = false;
     511                 :            : #endif
     512                 :   24105500 :   ALLOCNO_DONT_REASSIGN_P (a) = false;
     513                 :   24105500 :   ALLOCNO_BAD_SPILL_P (a) = false;
     514                 :   24105500 :   ALLOCNO_ASSIGNED_P (a) = false;
     515                 :   24105500 :   ALLOCNO_MODE (a) = (regno < 0 ? VOIDmode : PSEUDO_REGNO_MODE (regno));
     516                 :   24105500 :   ALLOCNO_WMODE (a) = ALLOCNO_MODE (a);
     517                 :   24105500 :   ALLOCNO_PREFS (a) = NULL;
     518                 :   24105500 :   ALLOCNO_COPIES (a) = NULL;
     519                 :   24105500 :   ALLOCNO_HARD_REG_COSTS (a) = NULL;
     520                 :   24105500 :   ALLOCNO_CONFLICT_HARD_REG_COSTS (a) = NULL;
     521                 :   24105500 :   ALLOCNO_UPDATED_HARD_REG_COSTS (a) = NULL;
     522                 :   24105500 :   ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) = NULL;
     523                 :   24105500 :   ALLOCNO_CLASS (a) = NO_REGS;
     524                 :   24105500 :   ALLOCNO_UPDATED_CLASS_COST (a) = 0;
     525                 :   24105500 :   ALLOCNO_CLASS_COST (a) = 0;
     526                 :   24105500 :   ALLOCNO_MEMORY_COST (a) = 0;
     527                 :   24105500 :   ALLOCNO_UPDATED_MEMORY_COST (a) = 0;
     528                 :   24105500 :   ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a) = 0;
     529                 :   24105500 :   ALLOCNO_NUM_OBJECTS (a) = 0;
     530                 :            : 
     531                 :   24105500 :   ALLOCNO_ADD_DATA (a) = NULL;
     532                 :   24105500 :   allocno_vec.safe_push (a);
     533                 :   24105500 :   ira_allocnos = allocno_vec.address ();
     534                 :   24105500 :   ira_allocnos_num = allocno_vec.length ();
     535                 :            : 
     536                 :   24105500 :   return a;
     537                 :            : }
     538                 :            : 
     539                 :            : /* Set up register class for A and update its conflict hard
     540                 :            :    registers.  */
     541                 :            : void
     542                 :   24105500 : ira_set_allocno_class (ira_allocno_t a, enum reg_class aclass)
     543                 :            : {
     544                 :   24105500 :   ira_allocno_object_iterator oi;
     545                 :   24105500 :   ira_object_t obj;
     546                 :            : 
     547                 :   24105500 :   ALLOCNO_CLASS (a) = aclass;
     548                 :   24105500 :   FOR_EACH_ALLOCNO_OBJECT (a, obj, oi)
     549                 :            :     {
     550                 :          0 :       OBJECT_CONFLICT_HARD_REGS (obj) |= ~reg_class_contents[aclass];
     551                 :          0 :       OBJECT_TOTAL_CONFLICT_HARD_REGS (obj) |= ~reg_class_contents[aclass];
     552                 :            :     }
     553                 :   24105500 : }
     554                 :            : 
     555                 :            : /* Determine the number of objects we should associate with allocno A
     556                 :            :    and allocate them.  */
     557                 :            : void
     558                 :   24105500 : ira_create_allocno_objects (ira_allocno_t a)
     559                 :            : {
     560                 :   24105500 :   machine_mode mode = ALLOCNO_MODE (a);
     561                 :   24105500 :   enum reg_class aclass = ALLOCNO_CLASS (a);
     562                 :   24105500 :   int n = ira_reg_class_max_nregs[aclass][mode];
     563                 :   24105500 :   int i;
     564                 :            : 
     565                 :   24838500 :   if (n != 2 || maybe_ne (GET_MODE_SIZE (mode), n * UNITS_PER_WORD))
     566                 :            :     n = 1;
     567                 :            : 
     568                 :   24105500 :   ALLOCNO_NUM_OBJECTS (a) = n;
     569                 :   48764100 :   for (i = 0; i < n; i++)
     570                 :   24658600 :     ALLOCNO_OBJECT (a, i) = ira_create_object (a, i);
     571                 :   24105500 : }
     572                 :            : 
     573                 :            : /* For each allocno, set ALLOCNO_NUM_OBJECTS and create the
     574                 :            :    ALLOCNO_OBJECT structures.  This must be called after the allocno
     575                 :            :    classes are known.  */
     576                 :            : static void
     577                 :     944096 : create_allocno_objects (void)
     578                 :            : {
     579                 :     944096 :   ira_allocno_t a;
     580                 :     944096 :   ira_allocno_iterator ai;
     581                 :            : 
     582                 :   22246100 :   FOR_EACH_ALLOCNO (a, ai)
     583                 :   21302000 :     ira_create_allocno_objects (a);
     584                 :     944096 : }
     585                 :            : 
     586                 :            : /* Merge hard register conflict information for all objects associated with
     587                 :            :    allocno TO into the corresponding objects associated with FROM.
     588                 :            :    If TOTAL_ONLY is true, we only merge OBJECT_TOTAL_CONFLICT_HARD_REGS.  */
     589                 :            : static void
     590                 :    6141280 : merge_hard_reg_conflicts (ira_allocno_t from, ira_allocno_t to,
     591                 :            :                           bool total_only)
     592                 :            : {
     593                 :    6141280 :   int i;
     594                 :    6141280 :   gcc_assert (ALLOCNO_NUM_OBJECTS (to) == ALLOCNO_NUM_OBJECTS (from));
     595                 :   12350500 :   for (i = 0; i < ALLOCNO_NUM_OBJECTS (to); i++)
     596                 :            :     {
     597                 :    6209240 :       ira_object_t from_obj = ALLOCNO_OBJECT (from, i);
     598                 :    6209240 :       ira_object_t to_obj = ALLOCNO_OBJECT (to, i);
     599                 :            : 
     600                 :    6209240 :       if (!total_only)
     601                 :            :         OBJECT_CONFLICT_HARD_REGS (to_obj)
     602                 :   12057600 :           |= OBJECT_CONFLICT_HARD_REGS (from_obj);
     603                 :    6209240 :       OBJECT_TOTAL_CONFLICT_HARD_REGS (to_obj)
     604                 :   12418500 :         |= OBJECT_TOTAL_CONFLICT_HARD_REGS (from_obj);
     605                 :            :     }
     606                 :            : #ifdef STACK_REGS
     607                 :    6141280 :   if (!total_only && ALLOCNO_NO_STACK_REG_P (from))
     608                 :      19737 :     ALLOCNO_NO_STACK_REG_P (to) = true;
     609                 :    6141280 :   if (ALLOCNO_TOTAL_NO_STACK_REG_P (from))
     610                 :      31706 :     ALLOCNO_TOTAL_NO_STACK_REG_P (to) = true;
     611                 :            : #endif
     612                 :    6141280 : }
     613                 :            : 
     614                 :            : /* Update hard register conflict information for all objects associated with
     615                 :            :    A to include the regs in SET.  */
     616                 :            : void
     617                 :    2331050 : ior_hard_reg_conflicts (ira_allocno_t a, const_hard_reg_set set)
     618                 :            : {
     619                 :    2331050 :   ira_allocno_object_iterator i;
     620                 :    2331050 :   ira_object_t obj;
     621                 :            : 
     622                 :    2331050 :   FOR_EACH_ALLOCNO_OBJECT (a, obj, i)
     623                 :            :     {
     624                 :    2376180 :       OBJECT_CONFLICT_HARD_REGS (obj) |= set;
     625                 :   11835800 :       OBJECT_TOTAL_CONFLICT_HARD_REGS (obj) |= set;
     626                 :            :     }
     627                 :    2331050 : }
     628                 :            : 
     629                 :            : /* Return TRUE if a conflict vector with NUM elements is more
     630                 :            :    profitable than a conflict bit vector for OBJ.  */
     631                 :            : bool
     632                 :   17244100 : ira_conflict_vector_profitable_p (ira_object_t obj, int num)
     633                 :            : {
     634                 :   17244100 :   int nw;
     635                 :   17244100 :   int max = OBJECT_MAX (obj);
     636                 :   17244100 :   int min = OBJECT_MIN (obj);
     637                 :            : 
     638                 :   17244100 :   if (max < min)
     639                 :            :     /* We prefer a bit vector in such case because it does not result
     640                 :            :        in allocation.  */
     641                 :            :     return false;
     642                 :            : 
     643                 :   16411200 :   nw = (max - min + IRA_INT_BITS) / IRA_INT_BITS;
     644                 :   16411200 :   return (2 * sizeof (ira_object_t) * (num + 1)
     645                 :   16411200 :           < 3 * nw * sizeof (IRA_INT_TYPE));
     646                 :            : }
     647                 :            : 
     648                 :            : /* Allocates and initialize the conflict vector of OBJ for NUM
     649                 :            :    conflicting objects.  */
     650                 :            : void
     651                 :    4441780 : ira_allocate_conflict_vec (ira_object_t obj, int num)
     652                 :            : {
     653                 :    4441780 :   int size;
     654                 :    4441780 :   ira_object_t *vec;
     655                 :            : 
     656                 :    4441780 :   ira_assert (OBJECT_CONFLICT_ARRAY (obj) == NULL);
     657                 :    4441780 :   num++; /* for NULL end marker  */
     658                 :    4441780 :   size = sizeof (ira_object_t) * num;
     659                 :    4441780 :   OBJECT_CONFLICT_ARRAY (obj) = ira_allocate (size);
     660                 :    4441780 :   vec = (ira_object_t *) OBJECT_CONFLICT_ARRAY (obj);
     661                 :    4441780 :   vec[0] = NULL;
     662                 :    4441780 :   OBJECT_NUM_CONFLICTS (obj) = 0;
     663                 :    4441780 :   OBJECT_CONFLICT_ARRAY_SIZE (obj) = size;
     664                 :    4441780 :   OBJECT_CONFLICT_VEC_P (obj) = true;
     665                 :    4441780 : }
     666                 :            : 
     667                 :            : /* Allocate and initialize the conflict bit vector of OBJ.  */
     668                 :            : static void
     669                 :       1830 : allocate_conflict_bit_vec (ira_object_t obj)
     670                 :            : {
     671                 :       1830 :   unsigned int size;
     672                 :            : 
     673                 :       1830 :   ira_assert (OBJECT_CONFLICT_ARRAY (obj) == NULL);
     674                 :       1830 :   size = ((OBJECT_MAX (obj) - OBJECT_MIN (obj) + IRA_INT_BITS)
     675                 :       1830 :           / IRA_INT_BITS * sizeof (IRA_INT_TYPE));
     676                 :       1830 :   OBJECT_CONFLICT_ARRAY (obj) = ira_allocate (size);
     677                 :       1830 :   memset (OBJECT_CONFLICT_ARRAY (obj), 0, size);
     678                 :       1830 :   OBJECT_CONFLICT_ARRAY_SIZE (obj) = size;
     679                 :       1830 :   OBJECT_CONFLICT_VEC_P (obj) = false;
     680                 :       1830 : }
     681                 :            : 
     682                 :            : /* Allocate and initialize the conflict vector or conflict bit vector
     683                 :            :    of OBJ for NUM conflicting allocnos whatever is more profitable.  */
     684                 :            : void
     685                 :       2538 : ira_allocate_object_conflicts (ira_object_t obj, int num)
     686                 :            : {
     687                 :       2538 :   if (ira_conflict_vector_profitable_p (obj, num))
     688                 :        708 :     ira_allocate_conflict_vec (obj, num);
     689                 :            :   else
     690                 :       1830 :     allocate_conflict_bit_vec (obj);
     691                 :       2538 : }
     692                 :            : 
     693                 :            : /* Add OBJ2 to the conflicts of OBJ1.  */
     694                 :            : static void
     695                 :          0 : add_to_conflicts (ira_object_t obj1, ira_object_t obj2)
     696                 :            : {
     697                 :          0 :   int num;
     698                 :          0 :   unsigned int size;
     699                 :            : 
     700                 :          0 :   if (OBJECT_CONFLICT_VEC_P (obj1))
     701                 :            :     {
     702                 :          0 :       ira_object_t *vec = OBJECT_CONFLICT_VEC (obj1);
     703                 :          0 :       int curr_num = OBJECT_NUM_CONFLICTS (obj1);
     704                 :          0 :       num = curr_num + 2;
     705                 :          0 :       if (OBJECT_CONFLICT_ARRAY_SIZE (obj1) < num * sizeof (ira_object_t))
     706                 :            :         {
     707                 :          0 :           ira_object_t *newvec;
     708                 :          0 :           size = (3 * num / 2 + 1) * sizeof (ira_allocno_t);
     709                 :          0 :           newvec = (ira_object_t *) ira_allocate (size);
     710                 :          0 :           memcpy (newvec, vec, curr_num * sizeof (ira_object_t));
     711                 :          0 :           ira_free (vec);
     712                 :          0 :           vec = newvec;
     713                 :          0 :           OBJECT_CONFLICT_ARRAY (obj1) = vec;
     714                 :          0 :           OBJECT_CONFLICT_ARRAY_SIZE (obj1) = size;
     715                 :            :         }
     716                 :          0 :       vec[num - 2] = obj2;
     717                 :          0 :       vec[num - 1] = NULL;
     718                 :          0 :       OBJECT_NUM_CONFLICTS (obj1)++;
     719                 :            :     }
     720                 :            :   else
     721                 :            :     {
     722                 :          0 :       int nw, added_head_nw, id;
     723                 :          0 :       IRA_INT_TYPE *vec = OBJECT_CONFLICT_BITVEC (obj1);
     724                 :            : 
     725                 :          0 :       id = OBJECT_CONFLICT_ID (obj2);
     726                 :          0 :       if (OBJECT_MIN (obj1) > id)
     727                 :            :         {
     728                 :            :           /* Expand head of the bit vector.  */
     729                 :          0 :           added_head_nw = (OBJECT_MIN (obj1) - id - 1) / IRA_INT_BITS + 1;
     730                 :          0 :           nw = (OBJECT_MAX (obj1) - OBJECT_MIN (obj1)) / IRA_INT_BITS + 1;
     731                 :          0 :           size = (nw + added_head_nw) * sizeof (IRA_INT_TYPE);
     732                 :          0 :           if (OBJECT_CONFLICT_ARRAY_SIZE (obj1) >= size)
     733                 :            :             {
     734                 :          0 :               memmove ((char *) vec + added_head_nw * sizeof (IRA_INT_TYPE),
     735                 :          0 :                        vec, nw * sizeof (IRA_INT_TYPE));
     736                 :          0 :               memset (vec, 0, added_head_nw * sizeof (IRA_INT_TYPE));
     737                 :            :             }
     738                 :            :           else
     739                 :            :             {
     740                 :          0 :               size
     741                 :          0 :                 = (3 * (nw + added_head_nw) / 2 + 1) * sizeof (IRA_INT_TYPE);
     742                 :          0 :               vec = (IRA_INT_TYPE *) ira_allocate (size);
     743                 :          0 :               memcpy ((char *) vec + added_head_nw * sizeof (IRA_INT_TYPE),
     744                 :          0 :                       OBJECT_CONFLICT_ARRAY (obj1), nw * sizeof (IRA_INT_TYPE));
     745                 :          0 :               memset (vec, 0, added_head_nw * sizeof (IRA_INT_TYPE));
     746                 :          0 :               memset ((char *) vec
     747                 :            :                       + (nw + added_head_nw) * sizeof (IRA_INT_TYPE),
     748                 :          0 :                       0, size - (nw + added_head_nw) * sizeof (IRA_INT_TYPE));
     749                 :          0 :               ira_free (OBJECT_CONFLICT_ARRAY (obj1));
     750                 :          0 :               OBJECT_CONFLICT_ARRAY (obj1) = vec;
     751                 :          0 :               OBJECT_CONFLICT_ARRAY_SIZE (obj1) = size;
     752                 :            :             }
     753                 :          0 :           OBJECT_MIN (obj1) -= added_head_nw * IRA_INT_BITS;
     754                 :            :         }
     755                 :          0 :       else if (OBJECT_MAX (obj1) < id)
     756                 :            :         {
     757                 :          0 :           nw = (id - OBJECT_MIN (obj1)) / IRA_INT_BITS + 1;
     758                 :          0 :           size = nw * sizeof (IRA_INT_TYPE);
     759                 :          0 :           if (OBJECT_CONFLICT_ARRAY_SIZE (obj1) < size)
     760                 :            :             {
     761                 :            :               /* Expand tail of the bit vector.  */
     762                 :          0 :               size = (3 * nw / 2 + 1) * sizeof (IRA_INT_TYPE);
     763                 :          0 :               vec = (IRA_INT_TYPE *) ira_allocate (size);
     764                 :          0 :               memcpy (vec, OBJECT_CONFLICT_ARRAY (obj1), OBJECT_CONFLICT_ARRAY_SIZE (obj1));
     765                 :          0 :               memset ((char *) vec + OBJECT_CONFLICT_ARRAY_SIZE (obj1),
     766                 :          0 :                       0, size - OBJECT_CONFLICT_ARRAY_SIZE (obj1));
     767                 :          0 :               ira_free (OBJECT_CONFLICT_ARRAY (obj1));
     768                 :          0 :               OBJECT_CONFLICT_ARRAY (obj1) = vec;
     769                 :          0 :               OBJECT_CONFLICT_ARRAY_SIZE (obj1) = size;
     770                 :            :             }
     771                 :          0 :           OBJECT_MAX (obj1) = id;
     772                 :            :         }
     773                 :          0 :       SET_MINMAX_SET_BIT (vec, id, OBJECT_MIN (obj1), OBJECT_MAX (obj1));
     774                 :            :     }
     775                 :          0 : }
     776                 :            : 
     777                 :            : /* Add OBJ1 to the conflicts of OBJ2 and vice versa.  */
     778                 :            : static void
     779                 :          0 : ira_add_conflict (ira_object_t obj1, ira_object_t obj2)
     780                 :            : {
     781                 :          0 :   add_to_conflicts (obj1, obj2);
     782                 :          0 :   add_to_conflicts (obj2, obj1);
     783                 :          0 : }
     784                 :            : 
     785                 :            : /* Clear all conflicts of OBJ.  */
     786                 :            : static void
     787                 :          0 : clear_conflicts (ira_object_t obj)
     788                 :            : {
     789                 :          0 :   if (OBJECT_CONFLICT_VEC_P (obj))
     790                 :            :     {
     791                 :          0 :       OBJECT_NUM_CONFLICTS (obj) = 0;
     792                 :          0 :       OBJECT_CONFLICT_VEC (obj)[0] = NULL;
     793                 :            :     }
     794                 :          0 :   else if (OBJECT_CONFLICT_ARRAY_SIZE (obj) != 0)
     795                 :            :     {
     796                 :          0 :       int nw;
     797                 :            : 
     798                 :          0 :       nw = (OBJECT_MAX (obj) - OBJECT_MIN (obj)) / IRA_INT_BITS + 1;
     799                 :          0 :       memset (OBJECT_CONFLICT_BITVEC (obj), 0, nw * sizeof (IRA_INT_TYPE));
     800                 :            :     }
     801                 :          0 : }
     802                 :            : 
     803                 :            : /* The array used to find duplications in conflict vectors of
     804                 :            :    allocnos.  */
     805                 :            : static int *conflict_check;
     806                 :            : 
     807                 :            : /* The value used to mark allocation presence in conflict vector of
     808                 :            :    the current allocno.  */
     809                 :            : static int curr_conflict_check_tick;
     810                 :            : 
     811                 :            : /* Remove duplications in conflict vector of OBJ.  */
     812                 :            : static void
     813                 :          0 : compress_conflict_vec (ira_object_t obj)
     814                 :            : {
     815                 :          0 :   ira_object_t *vec, conflict_obj;
     816                 :          0 :   int i, j;
     817                 :            : 
     818                 :          0 :   ira_assert (OBJECT_CONFLICT_VEC_P (obj));
     819                 :          0 :   vec = OBJECT_CONFLICT_VEC (obj);
     820                 :          0 :   curr_conflict_check_tick++;
     821                 :          0 :   for (i = j = 0; (conflict_obj = vec[i]) != NULL; i++)
     822                 :            :     {
     823                 :          0 :       int id = OBJECT_CONFLICT_ID (conflict_obj);
     824                 :          0 :       if (conflict_check[id] != curr_conflict_check_tick)
     825                 :            :         {
     826                 :          0 :           conflict_check[id] = curr_conflict_check_tick;
     827                 :          0 :           vec[j++] = conflict_obj;
     828                 :            :         }
     829                 :            :     }
     830                 :          0 :   OBJECT_NUM_CONFLICTS (obj) = j;
     831                 :          0 :   vec[j] = NULL;
     832                 :          0 : }
     833                 :            : 
     834                 :            : /* Remove duplications in conflict vectors of all allocnos.  */
     835                 :            : static void
     836                 :          0 : compress_conflict_vecs (void)
     837                 :            : {
     838                 :          0 :   ira_object_t obj;
     839                 :          0 :   ira_object_iterator oi;
     840                 :            : 
     841                 :          0 :   conflict_check = (int *) ira_allocate (sizeof (int) * ira_objects_num);
     842                 :          0 :   memset (conflict_check, 0, sizeof (int) * ira_objects_num);
     843                 :          0 :   curr_conflict_check_tick = 0;
     844                 :          0 :   FOR_EACH_OBJECT (obj, oi)
     845                 :            :     {
     846                 :          0 :       if (OBJECT_CONFLICT_VEC_P (obj))
     847                 :          0 :         compress_conflict_vec (obj);
     848                 :            :     }
     849                 :          0 :   ira_free (conflict_check);
     850                 :          0 : }
     851                 :            : 
     852                 :            : /* This recursive function outputs allocno A and if it is a cap the
     853                 :            :    function outputs its members.  */
     854                 :            : void
     855                 :       1097 : ira_print_expanded_allocno (ira_allocno_t a)
     856                 :            : {
     857                 :       1097 :   basic_block bb;
     858                 :            : 
     859                 :       1097 :   fprintf (ira_dump_file, " a%d(r%d", ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
     860                 :       1097 :   if ((bb = ALLOCNO_LOOP_TREE_NODE (a)->bb) != NULL)
     861                 :          0 :     fprintf (ira_dump_file, ",b%d", bb->index);
     862                 :            :   else
     863                 :       1097 :     fprintf (ira_dump_file, ",l%d", ALLOCNO_LOOP_TREE_NODE (a)->loop_num);
     864                 :       1097 :   if (ALLOCNO_CAP_MEMBER (a) != NULL)
     865                 :            :     {
     866                 :          0 :       fprintf (ira_dump_file, ":");
     867                 :          0 :       ira_print_expanded_allocno (ALLOCNO_CAP_MEMBER (a));
     868                 :            :     }
     869                 :       1097 :   fprintf (ira_dump_file, ")");
     870                 :       1097 : }
     871                 :            : 
     872                 :            : /* Create and return the cap representing allocno A in the
     873                 :            :    parent loop.  */
     874                 :            : static ira_allocno_t
     875                 :    2800960 : create_cap_allocno (ira_allocno_t a)
     876                 :            : {
     877                 :    2800960 :   ira_allocno_t cap;
     878                 :    2800960 :   ira_loop_tree_node_t parent;
     879                 :    2800960 :   enum reg_class aclass;
     880                 :            : 
     881                 :    2800960 :   parent = ALLOCNO_LOOP_TREE_NODE (a)->parent;
     882                 :    2800960 :   cap = ira_create_allocno (ALLOCNO_REGNO (a), true, parent);
     883                 :    2800960 :   ALLOCNO_MODE (cap) = ALLOCNO_MODE (a);
     884                 :    2800960 :   ALLOCNO_WMODE (cap) = ALLOCNO_WMODE (a);
     885                 :    2800960 :   aclass = ALLOCNO_CLASS (a);
     886                 :    2800960 :   ira_set_allocno_class (cap, aclass);
     887                 :    2800960 :   ira_create_allocno_objects (cap);
     888                 :    2800960 :   ALLOCNO_CAP_MEMBER (cap) = a;
     889                 :    2800960 :   ALLOCNO_CAP (a) = cap;
     890                 :    2800960 :   ALLOCNO_CLASS_COST (cap) = ALLOCNO_CLASS_COST (a);
     891                 :    2800960 :   ALLOCNO_MEMORY_COST (cap) = ALLOCNO_MEMORY_COST (a);
     892                 :    2800960 :   ira_allocate_and_copy_costs
     893                 :    2800960 :     (&ALLOCNO_HARD_REG_COSTS (cap), aclass, ALLOCNO_HARD_REG_COSTS (a));
     894                 :    2800960 :   ira_allocate_and_copy_costs
     895                 :    2800960 :     (&ALLOCNO_CONFLICT_HARD_REG_COSTS (cap), aclass,
     896                 :            :      ALLOCNO_CONFLICT_HARD_REG_COSTS (a));
     897                 :    2800960 :   ALLOCNO_BAD_SPILL_P (cap) = ALLOCNO_BAD_SPILL_P (a);
     898                 :    2800960 :   ALLOCNO_NREFS (cap) = ALLOCNO_NREFS (a);
     899                 :    2800960 :   ALLOCNO_FREQ (cap) = ALLOCNO_FREQ (a);
     900                 :    2800960 :   ALLOCNO_CALL_FREQ (cap) = ALLOCNO_CALL_FREQ (a);
     901                 :            : 
     902                 :    2800960 :   merge_hard_reg_conflicts (a, cap, false);
     903                 :            : 
     904                 :    2800960 :   ALLOCNO_CALLS_CROSSED_NUM (cap) = ALLOCNO_CALLS_CROSSED_NUM (a);
     905                 :    2800960 :   ALLOCNO_CHEAP_CALLS_CROSSED_NUM (cap) = ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a);
     906                 :    2800960 :   ALLOCNO_CROSSED_CALLS_ABIS (cap) = ALLOCNO_CROSSED_CALLS_ABIS (a);
     907                 :    2800960 :   ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS (cap)
     908                 :    2800960 :     = ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS (a);
     909                 :    2800960 :   if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
     910                 :            :     {
     911                 :          0 :       fprintf (ira_dump_file, "    Creating cap ");
     912                 :          0 :       ira_print_expanded_allocno (cap);
     913                 :          0 :       fprintf (ira_dump_file, "\n");
     914                 :            :     }
     915                 :    2800960 :   return cap;
     916                 :            : }
     917                 :            : 
     918                 :            : /* Create and return a live range for OBJECT with given attributes.  */
     919                 :            : live_range_t
     920                 :   35331400 : ira_create_live_range (ira_object_t obj, int start, int finish,
     921                 :            :                        live_range_t next)
     922                 :            : {
     923                 :   35331400 :   live_range_t p;
     924                 :            : 
     925                 :   35331400 :   p = live_range_pool.allocate ();
     926                 :   35331400 :   p->object = obj;
     927                 :   35331400 :   p->start = start;
     928                 :   35331400 :   p->finish = finish;
     929                 :   35331400 :   p->next = next;
     930                 :   35331400 :   return p;
     931                 :            : }
     932                 :            : 
     933                 :            : /* Create a new live range for OBJECT and queue it at the head of its
     934                 :            :    live range list.  */
     935                 :            : void
     936                 :   35331400 : ira_add_live_range_to_object (ira_object_t object, int start, int finish)
     937                 :            : {
     938                 :   35331400 :   live_range_t p;
     939                 :   35331400 :   p = ira_create_live_range (object, start, finish,
     940                 :            :                              OBJECT_LIVE_RANGES (object));
     941                 :   35331400 :   OBJECT_LIVE_RANGES (object) = p;
     942                 :   35331400 : }
     943                 :            : 
     944                 :            : /* Copy allocno live range R and return the result.  */
     945                 :            : static live_range_t
     946                 :          0 : copy_live_range (live_range_t r)
     947                 :            : {
     948                 :          0 :   live_range_t p;
     949                 :            : 
     950                 :          0 :   p = live_range_pool.allocate ();
     951                 :          0 :   *p = *r;
     952                 :          0 :   return p;
     953                 :            : }
     954                 :            : 
     955                 :            : /* Copy allocno live range list given by its head R and return the
     956                 :            :    result.  */
     957                 :            : live_range_t
     958                 :          0 : ira_copy_live_range_list (live_range_t r)
     959                 :            : {
     960                 :          0 :   live_range_t p, first, last;
     961                 :            : 
     962                 :          0 :   if (r == NULL)
     963                 :            :     return NULL;
     964                 :          0 :   for (first = last = NULL; r != NULL; r = r->next)
     965                 :            :     {
     966                 :          0 :       p = copy_live_range (r);
     967                 :          0 :       if (first == NULL)
     968                 :            :         first = p;
     969                 :            :       else
     970                 :          0 :         last->next = p;
     971                 :          0 :       last = p;
     972                 :            :     }
     973                 :            :   return first;
     974                 :            : }
     975                 :            : 
     976                 :            : /* Merge ranges R1 and R2 and returns the result.  The function
     977                 :            :    maintains the order of ranges and tries to minimize number of the
     978                 :            :    result ranges.  */
     979                 :            : live_range_t
     980                 :    1196020 : ira_merge_live_ranges (live_range_t r1, live_range_t r2)
     981                 :            : {
     982                 :    1196020 :   live_range_t first, last;
     983                 :            : 
     984                 :    1196020 :   if (r1 == NULL)
     985                 :            :     return r2;
     986                 :    1196020 :   if (r2 == NULL)
     987                 :            :     return r1;
     988                 :    5741470 :   for (first = last = NULL; r1 != NULL && r2 != NULL;)
     989                 :            :     {
     990                 :    4546500 :       if (r1->start < r2->start)
     991                 :    3131900 :         std::swap (r1, r2);
     992                 :    4546500 :       if (r1->start <= r2->finish + 1)
     993                 :            :         {
     994                 :            :           /* Intersected ranges: merge r1 and r2 into r1.  */
     995                 :     440936 :           r1->start = r2->start;
     996                 :     440936 :           if (r1->finish < r2->finish)
     997                 :          0 :             r1->finish = r2->finish;
     998                 :     440936 :           live_range_t temp = r2;
     999                 :     440936 :           r2 = r2->next;
    1000                 :     440936 :           ira_finish_live_range (temp);
    1001                 :     440936 :           if (r2 == NULL)
    1002                 :            :             {
    1003                 :            :               /* To try to merge with subsequent ranges in r1.  */
    1004                 :     417971 :               r2 = r1->next;
    1005                 :     417971 :               r1->next = NULL;
    1006                 :            :             }
    1007                 :            :         }
    1008                 :            :       else
    1009                 :            :         {
    1010                 :            :           /* Add r1 to the result.  */
    1011                 :    4105570 :           if (first == NULL)
    1012                 :            :             first = last = r1;
    1013                 :            :           else
    1014                 :            :             {
    1015                 :    3102750 :               last->next = r1;
    1016                 :    3102750 :               last = r1;
    1017                 :            :             }
    1018                 :    4105570 :           r1 = r1->next;
    1019                 :    4105570 :           if (r1 == NULL)
    1020                 :            :             {
    1021                 :            :               /* To try to merge with subsequent ranges in r2.  */
    1022                 :    3877070 :               r1 = r2->next;
    1023                 :    3877070 :               r2->next = NULL;
    1024                 :            :             }
    1025                 :            :         }
    1026                 :            :     }
    1027                 :    1194970 :   if (r1 != NULL)
    1028                 :            :     {
    1029                 :     194029 :       if (first == NULL)
    1030                 :            :         first = r1;
    1031                 :            :       else
    1032                 :       1876 :         last->next = r1;
    1033                 :     194029 :       ira_assert (r1->next == NULL);
    1034                 :            :     }
    1035                 :    1000940 :   else if (r2 != NULL)
    1036                 :            :     {
    1037                 :    1000940 :       if (first == NULL)
    1038                 :            :         first = r2;
    1039                 :            :       else
    1040                 :    1000940 :         last->next = r2;
    1041                 :    1000940 :       ira_assert (r2->next == NULL);
    1042                 :            :     }
    1043                 :            :   else
    1044                 :            :     {
    1045                 :          0 :       ira_assert (last->next == NULL);
    1046                 :            :     }
    1047                 :            :   return first;
    1048                 :            : }
    1049                 :            : 
    1050                 :            : /* Return TRUE if live ranges R1 and R2 intersect.  */
    1051                 :            : bool
    1052                 :   14323500 : ira_live_ranges_intersect_p (live_range_t r1, live_range_t r2)
    1053                 :            : {
    1054                 :            :   /* Remember the live ranges are always kept ordered.  */
    1055                 :   30959400 :   while (r1 != NULL && r2 != NULL)
    1056                 :            :     {
    1057                 :   17358700 :       if (r1->start > r2->finish)
    1058                 :   13416900 :         r1 = r1->next;
    1059                 :    3941790 :       else if (r2->start > r1->finish)
    1060                 :    3219030 :         r2 = r2->next;
    1061                 :            :       else
    1062                 :            :         return true;
    1063                 :            :     }
    1064                 :            :   return false;
    1065                 :            : }
    1066                 :            : 
    1067                 :            : /* Free allocno live range R.  */
    1068                 :            : void
    1069                 :   35331400 : ira_finish_live_range (live_range_t r)
    1070                 :            : {
    1071                 :   35331400 :   live_range_pool.remove (r);
    1072                 :   35331400 : }
    1073                 :            : 
    1074                 :            : /* Free list of allocno live ranges starting with R.  */
    1075                 :            : void
    1076                 :   24658600 : ira_finish_live_range_list (live_range_t r)
    1077                 :            : {
    1078                 :   56141800 :   live_range_t next_r;
    1079                 :            : 
    1080                 :   56141800 :   for (; r != NULL; r = next_r)
    1081                 :            :     {
    1082                 :   31483300 :       next_r = r->next;
    1083                 :   31483300 :       ira_finish_live_range (r);
    1084                 :            :     }
    1085                 :   24658600 : }
    1086                 :            : 
    1087                 :            : /* Free updated register costs of allocno A.  */
    1088                 :            : void
    1089                 :   37258500 : ira_free_allocno_updated_costs (ira_allocno_t a)
    1090                 :            : {
    1091                 :   37258500 :   enum reg_class aclass;
    1092                 :            : 
    1093                 :   37258500 :   aclass = ALLOCNO_CLASS (a);
    1094                 :   37258500 :   if (ALLOCNO_UPDATED_HARD_REG_COSTS (a) != NULL)
    1095                 :    9686030 :     ira_free_cost_vector (ALLOCNO_UPDATED_HARD_REG_COSTS (a), aclass);
    1096                 :   37258500 :   ALLOCNO_UPDATED_HARD_REG_COSTS (a) = NULL;
    1097                 :   37258500 :   if (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) != NULL)
    1098                 :    6714570 :     ira_free_cost_vector (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a),
    1099                 :            :                           aclass);
    1100                 :   37258500 :   ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) = NULL;
    1101                 :   37258500 : }
    1102                 :            : 
    1103                 :            : /* Free and nullify all cost vectors allocated earlier for allocno
    1104                 :            :    A.  */
    1105                 :            : static void
    1106                 :   24105500 : ira_free_allocno_costs (ira_allocno_t a)
    1107                 :            : {
    1108                 :   24105500 :   enum reg_class aclass = ALLOCNO_CLASS (a);
    1109                 :   24105500 :   ira_object_t obj;
    1110                 :   24105500 :   ira_allocno_object_iterator oi;
    1111                 :            : 
    1112                 :   24105500 :   FOR_EACH_ALLOCNO_OBJECT (a, obj, oi)
    1113                 :            :     {
    1114                 :   24658600 :       ira_finish_live_range_list (OBJECT_LIVE_RANGES (obj));
    1115                 :   24658600 :       ira_object_id_map[OBJECT_CONFLICT_ID (obj)] = NULL;
    1116                 :   24658600 :       if (OBJECT_CONFLICT_ARRAY (obj) != NULL)
    1117                 :   16411200 :         ira_free (OBJECT_CONFLICT_ARRAY (obj));
    1118                 :   73422600 :       object_pool.remove (obj);
    1119                 :            :     }
    1120                 :            : 
    1121                 :   24105500 :   ira_allocnos[ALLOCNO_NUM (a)] = NULL;
    1122                 :   24105500 :   if (ALLOCNO_HARD_REG_COSTS (a) != NULL)
    1123                 :    7081310 :     ira_free_cost_vector (ALLOCNO_HARD_REG_COSTS (a), aclass);
    1124                 :   24105500 :   if (ALLOCNO_CONFLICT_HARD_REG_COSTS (a) != NULL)
    1125                 :     902421 :     ira_free_cost_vector (ALLOCNO_CONFLICT_HARD_REG_COSTS (a), aclass);
    1126                 :   24105500 :   if (ALLOCNO_UPDATED_HARD_REG_COSTS (a) != NULL)
    1127                 :          0 :     ira_free_cost_vector (ALLOCNO_UPDATED_HARD_REG_COSTS (a), aclass);
    1128                 :   24105500 :   if (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) != NULL)
    1129                 :          0 :     ira_free_cost_vector (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a),
    1130                 :            :                           aclass);
    1131                 :   24105500 :   ALLOCNO_HARD_REG_COSTS (a) = NULL;
    1132                 :   24105500 :   ALLOCNO_CONFLICT_HARD_REG_COSTS (a) = NULL;
    1133                 :   24105500 :   ALLOCNO_UPDATED_HARD_REG_COSTS (a) = NULL;
    1134                 :   24105500 :   ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) = NULL;
    1135                 :   24105500 : }
    1136                 :            : 
    1137                 :            : /* Free the memory allocated for allocno A.  */
    1138                 :            : static void
    1139                 :   24105500 : finish_allocno (ira_allocno_t a)
    1140                 :            : {
    1141                 :          0 :   ira_free_allocno_costs (a);
    1142                 :   24105500 :   allocno_pool.remove (a);
    1143                 :   24105500 : }
    1144                 :            : 
    1145                 :            : /* Free the memory allocated for all allocnos.  */
    1146                 :            : static void
    1147                 :     944096 : finish_allocnos (void)
    1148                 :            : {
    1149                 :     944096 :   ira_allocno_t a;
    1150                 :     944096 :   ira_allocno_iterator ai;
    1151                 :            : 
    1152                 :     944096 :   FOR_EACH_ALLOCNO (a, ai)
    1153                 :   46768300 :     finish_allocno (a);
    1154                 :     944096 :   ira_free (ira_regno_allocno_map);
    1155                 :     944096 :   ira_object_id_map_vec.release ();
    1156                 :     944096 :   allocno_vec.release ();
    1157                 :     944096 :   allocno_pool.release ();
    1158                 :     944096 :   object_pool.release ();
    1159                 :     944096 :   live_range_pool.release ();
    1160                 :     944096 : }
    1161                 :            : 
    1162                 :            : 
    1163                 :            : 
    1164                 :            : /* Pools for allocno preferences.  */
    1165                 :            : static object_allocator <ira_allocno_pref> pref_pool ("prefs");
    1166                 :            : 
    1167                 :            : /* Vec containing references to all created preferences.  It is a
    1168                 :            :    container of array ira_prefs.  */
    1169                 :            : static vec<ira_pref_t> pref_vec;
    1170                 :            : 
    1171                 :            : /* The function initializes data concerning allocno prefs.  */
    1172                 :            : static void
    1173                 :     944096 : initiate_prefs (void)
    1174                 :            : {
    1175                 :     944096 :   pref_vec.create (get_max_uid ());
    1176                 :     944096 :   ira_prefs = NULL;
    1177                 :     944096 :   ira_prefs_num = 0;
    1178                 :     944096 : }
    1179                 :            : 
    1180                 :            : /* Return pref for A and HARD_REGNO if any.  */
    1181                 :            : static ira_pref_t
    1182                 :    5145740 : find_allocno_pref (ira_allocno_t a, int hard_regno)
    1183                 :            : {
    1184                 :    5145740 :   ira_pref_t pref;
    1185                 :            : 
    1186                 :    5163140 :   for (pref = ALLOCNO_PREFS (a); pref != NULL; pref = pref->next_pref)
    1187                 :     265046 :     if (pref->allocno == a && pref->hard_regno == hard_regno)
    1188                 :          0 :       return pref;
    1189                 :            :   return NULL;
    1190                 :            : }
    1191                 :            : 
    1192                 :            : /* Create and return pref with given attributes A, HARD_REGNO, and FREQ.  */
    1193                 :            : ira_pref_t
    1194                 :    4898100 : ira_create_pref (ira_allocno_t a, int hard_regno, int freq)
    1195                 :            : {
    1196                 :    4898100 :   ira_pref_t pref;
    1197                 :            : 
    1198                 :    4898100 :   pref = pref_pool.allocate ();
    1199                 :    4898100 :   pref->num = ira_prefs_num;
    1200                 :    4898100 :   pref->allocno = a;
    1201                 :    4898100 :   pref->hard_regno = hard_regno;
    1202                 :    4898100 :   pref->freq = freq;
    1203                 :    4898100 :   pref_vec.safe_push (pref);
    1204                 :    4898100 :   ira_prefs = pref_vec.address ();
    1205                 :    4898100 :   ira_prefs_num = pref_vec.length ();
    1206                 :    4898100 :   return pref;
    1207                 :            : }
    1208                 :            : 
    1209                 :            : /* Attach a pref PREF to the corresponding allocno.  */
    1210                 :            : static void
    1211                 :    4898100 : add_allocno_pref_to_list (ira_pref_t pref)
    1212                 :            : {
    1213                 :    4898100 :   ira_allocno_t a = pref->allocno;
    1214                 :            : 
    1215                 :    4898100 :   pref->next_pref = ALLOCNO_PREFS (a);
    1216                 :    4898100 :   ALLOCNO_PREFS (a) = pref;
    1217                 :    4898100 : }
    1218                 :            : 
    1219                 :            : /* Create (or update frequency if the pref already exists) the pref of
    1220                 :            :    allocnos A preferring HARD_REGNO with frequency FREQ.  */
    1221                 :            : void
    1222                 :    5176620 : ira_add_allocno_pref (ira_allocno_t a, int hard_regno, int freq)
    1223                 :            : {
    1224                 :    5176620 :   ira_pref_t pref;
    1225                 :            : 
    1226                 :    5176620 :   if (freq <= 0)
    1227                 :            :     return;
    1228                 :   10291500 :   if ((pref = find_allocno_pref (a, hard_regno)) != NULL)
    1229                 :            :     {
    1230                 :     247648 :       pref->freq += freq;
    1231                 :     247648 :       return;
    1232                 :            :     }
    1233                 :    4898100 :   pref = ira_create_pref (a, hard_regno, freq);
    1234                 :    4898100 :   ira_assert (a != NULL);
    1235                 :    4898100 :   add_allocno_pref_to_list (pref);
    1236                 :            : }
    1237                 :            : 
    1238                 :            : /* Print info about PREF into file F.  */
    1239                 :            : static void
    1240                 :        196 : print_pref (FILE *f, ira_pref_t pref)
    1241                 :            : {
    1242                 :        196 :   fprintf (f, "  pref%d:a%d(r%d)<-hr%d@%d\n", pref->num,
    1243                 :        196 :            ALLOCNO_NUM (pref->allocno), ALLOCNO_REGNO (pref->allocno),
    1244                 :            :            pref->hard_regno, pref->freq);
    1245                 :        196 : }
    1246                 :            : 
    1247                 :            : /* Print info about PREF into stderr.  */
    1248                 :            : void
    1249                 :          0 : ira_debug_pref (ira_pref_t pref)
    1250                 :            : {
    1251                 :          0 :   print_pref (stderr, pref);
    1252                 :          0 : }
    1253                 :            : 
    1254                 :            : /* Print info about all prefs into file F.  */
    1255                 :            : static void
    1256                 :        102 : print_prefs (FILE *f)
    1257                 :            : {
    1258                 :        102 :   ira_pref_t pref;
    1259                 :        102 :   ira_pref_iterator pi;
    1260                 :            : 
    1261                 :        298 :   FOR_EACH_PREF (pref, pi)
    1262                 :        196 :     print_pref (f, pref);
    1263                 :        102 : }
    1264                 :            : 
    1265                 :            : /* Print info about all prefs into stderr.  */
    1266                 :            : void
    1267                 :          0 : ira_debug_prefs (void)
    1268                 :            : {
    1269                 :          0 :   print_prefs (stderr);
    1270                 :          0 : }
    1271                 :            : 
    1272                 :            : /* Print info about prefs involving allocno A into file F.  */
    1273                 :            : static void
    1274                 :          0 : print_allocno_prefs (FILE *f, ira_allocno_t a)
    1275                 :            : {
    1276                 :          0 :   ira_pref_t pref;
    1277                 :            : 
    1278                 :          0 :   fprintf (f, " a%d(r%d):", ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
    1279                 :          0 :   for (pref = ALLOCNO_PREFS (a); pref != NULL; pref = pref->next_pref)
    1280                 :          0 :     fprintf (f, " pref%d:hr%d@%d", pref->num, pref->hard_regno, pref->freq);
    1281                 :          0 :   fprintf (f, "\n");
    1282                 :          0 : }
    1283                 :            : 
    1284                 :            : /* Print info about prefs involving allocno A into stderr.  */
    1285                 :            : void
    1286                 :          0 : ira_debug_allocno_prefs (ira_allocno_t a)
    1287                 :            : {
    1288                 :          0 :   print_allocno_prefs (stderr, a);
    1289                 :          0 : }
    1290                 :            : 
    1291                 :            : /* The function frees memory allocated for PREF.  */
    1292                 :            : static void
    1293                 :    4898100 : finish_pref (ira_pref_t pref)
    1294                 :            : {
    1295                 :    4898100 :   ira_prefs[pref->num] = NULL;
    1296                 :          0 :   pref_pool.remove (pref);
    1297                 :    4493860 : }
    1298                 :            : 
    1299                 :            : /* Remove PREF from the list of allocno prefs and free memory for
    1300                 :            :    it.  */
    1301                 :            : void
    1302                 :     377069 : ira_remove_pref (ira_pref_t pref)
    1303                 :            : {
    1304                 :     377069 :   ira_pref_t cpref, prev;
    1305                 :            : 
    1306                 :     377069 :   if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
    1307                 :         14 :     fprintf (ira_dump_file, " Removing pref%d:hr%d@%d\n",
    1308                 :            :              pref->num, pref->hard_regno, pref->freq);
    1309                 :     377069 :   for (prev = NULL, cpref = ALLOCNO_PREFS (pref->allocno);
    1310                 :     378028 :        cpref != NULL;
    1311                 :        959 :        prev = cpref, cpref = cpref->next_pref)
    1312                 :     378028 :     if (cpref == pref)
    1313                 :            :       break;
    1314                 :     377069 :   ira_assert (cpref != NULL);
    1315                 :     377069 :   if (prev == NULL)
    1316                 :     376110 :     ALLOCNO_PREFS (pref->allocno) = pref->next_pref;
    1317                 :            :   else
    1318                 :        959 :     prev->next_pref = pref->next_pref;
    1319                 :     377069 :   finish_pref (pref);
    1320                 :     377069 : }
    1321                 :            : 
    1322                 :            : /* Remove all prefs of allocno A.  */
    1323                 :            : void
    1324                 :    1193380 : ira_remove_allocno_prefs (ira_allocno_t a)
    1325                 :            : {
    1326                 :    1193380 :   ira_pref_t pref, next_pref;
    1327                 :            : 
    1328                 :    1220540 :   for (pref = ALLOCNO_PREFS (a); pref != NULL; pref = next_pref)
    1329                 :            :     {
    1330                 :      27165 :       next_pref = pref->next_pref;
    1331                 :      27165 :       finish_pref (pref);
    1332                 :            :     }
    1333                 :    1193380 :   ALLOCNO_PREFS (a) = NULL;
    1334                 :    1193380 : }
    1335                 :            : 
    1336                 :            : /* Free memory allocated for all prefs.  */
    1337                 :            : static void
    1338                 :     944096 : finish_prefs (void)
    1339                 :            : {
    1340                 :     944096 :   ira_pref_t pref;
    1341                 :     944096 :   ira_pref_iterator pi;
    1342                 :            : 
    1343                 :     944096 :   FOR_EACH_PREF (pref, pi)
    1344                 :    9931820 :     finish_pref (pref);
    1345                 :     944096 :   pref_vec.release ();
    1346                 :     944096 :   pref_pool.release ();
    1347                 :     944096 : }
    1348                 :            : 
    1349                 :            : 
    1350                 :            : 
    1351                 :            : /* Pools for copies.  */
    1352                 :            : static object_allocator<ira_allocno_copy> copy_pool ("copies");
    1353                 :            : 
    1354                 :            : /* Vec containing references to all created copies.  It is a
    1355                 :            :    container of array ira_copies.  */
    1356                 :            : static vec<ira_copy_t> copy_vec;
    1357                 :            : 
    1358                 :            : /* The function initializes data concerning allocno copies.  */
    1359                 :            : static void
    1360                 :     944096 : initiate_copies (void)
    1361                 :            : {
    1362                 :     944096 :   copy_vec.create (get_max_uid ());
    1363                 :     944096 :   ira_copies = NULL;
    1364                 :     944096 :   ira_copies_num = 0;
    1365                 :     944096 : }
    1366                 :            : 
    1367                 :            : /* Return copy connecting A1 and A2 and originated from INSN of
    1368                 :            :    LOOP_TREE_NODE if any.  */
    1369                 :            : static ira_copy_t
    1370                 :    6379840 : find_allocno_copy (ira_allocno_t a1, ira_allocno_t a2, rtx_insn *insn,
    1371                 :            :                    ira_loop_tree_node_t loop_tree_node)
    1372                 :            : {
    1373                 :    6379840 :   ira_copy_t cp, next_cp;
    1374                 :    6379840 :   ira_allocno_t another_a;
    1375                 :            : 
    1376                 :   11100300 :   for (cp = ALLOCNO_COPIES (a1); cp != NULL; cp = next_cp)
    1377                 :            :     {
    1378                 :    4750460 :       if (cp->first == a1)
    1379                 :            :         {
    1380                 :    3704840 :           next_cp = cp->next_first_allocno_copy;
    1381                 :    3704840 :           another_a = cp->second;
    1382                 :            :         }
    1383                 :    1045610 :       else if (cp->second == a1)
    1384                 :            :         {
    1385                 :    1045610 :           next_cp = cp->next_second_allocno_copy;
    1386                 :    1045610 :           another_a = cp->first;
    1387                 :            :         }
    1388                 :            :       else
    1389                 :          0 :         gcc_unreachable ();
    1390                 :    4750460 :       if (another_a == a2 && cp->insn == insn
    1391                 :      35441 :           && cp->loop_tree_node == loop_tree_node)
    1392                 :      30040 :         return cp;
    1393                 :            :     }
    1394                 :            :   return NULL;
    1395                 :            : }
    1396                 :            : 
    1397                 :            : /* Create and return copy with given attributes LOOP_TREE_NODE, FIRST,
    1398                 :            :    SECOND, FREQ, CONSTRAINT_P, and INSN.  */
    1399                 :            : ira_copy_t
    1400                 :    6349800 : ira_create_copy (ira_allocno_t first, ira_allocno_t second, int freq,
    1401                 :            :                  bool constraint_p, rtx_insn *insn,
    1402                 :            :                  ira_loop_tree_node_t loop_tree_node)
    1403                 :            : {
    1404                 :    6349800 :   ira_copy_t cp;
    1405                 :            : 
    1406                 :    6349800 :   cp = copy_pool.allocate ();
    1407                 :    6349800 :   cp->num = ira_copies_num;
    1408                 :    6349800 :   cp->first = first;
    1409                 :    6349800 :   cp->second = second;
    1410                 :    6349800 :   cp->freq = freq;
    1411                 :    6349800 :   cp->constraint_p = constraint_p;
    1412                 :    6349800 :   cp->insn = insn;
    1413                 :    6349800 :   cp->loop_tree_node = loop_tree_node;
    1414                 :    6349800 :   copy_vec.safe_push (cp);
    1415                 :    6349800 :   ira_copies = copy_vec.address ();
    1416                 :    6349800 :   ira_copies_num = copy_vec.length ();
    1417                 :    6349800 :   return cp;
    1418                 :            : }
    1419                 :            : 
    1420                 :            : /* Attach a copy CP to allocnos involved into the copy.  */
    1421                 :            : static void
    1422                 :    6349800 : add_allocno_copy_to_list (ira_copy_t cp)
    1423                 :            : {
    1424                 :    6349800 :   ira_allocno_t first = cp->first, second = cp->second;
    1425                 :            : 
    1426                 :    6349800 :   cp->prev_first_allocno_copy = NULL;
    1427                 :    6349800 :   cp->prev_second_allocno_copy = NULL;
    1428                 :    6349800 :   cp->next_first_allocno_copy = ALLOCNO_COPIES (first);
    1429                 :    6349800 :   if (cp->next_first_allocno_copy != NULL)
    1430                 :            :     {
    1431                 :    2058790 :       if (cp->next_first_allocno_copy->first == first)
    1432                 :    1460910 :         cp->next_first_allocno_copy->prev_first_allocno_copy = cp;
    1433                 :            :       else
    1434                 :     597884 :         cp->next_first_allocno_copy->prev_second_allocno_copy = cp;
    1435                 :            :     }
    1436                 :    6349800 :   cp->next_second_allocno_copy = ALLOCNO_COPIES (second);
    1437                 :    6349800 :   if (cp->next_second_allocno_copy != NULL)
    1438                 :            :     {
    1439                 :    1788990 :       if (cp->next_second_allocno_copy->second == second)
    1440                 :     336962 :         cp->next_second_allocno_copy->prev_second_allocno_copy = cp;
    1441                 :            :       else
    1442                 :    1452030 :         cp->next_second_allocno_copy->prev_first_allocno_copy = cp;
    1443                 :            :     }
    1444                 :    6349800 :   ALLOCNO_COPIES (first) = cp;
    1445                 :    6349800 :   ALLOCNO_COPIES (second) = cp;
    1446                 :    6349800 : }
    1447                 :            : 
    1448                 :            : /* Make a copy CP a canonical copy where number of the
    1449                 :            :    first allocno is less than the second one.  */
    1450                 :            : static void
    1451                 :    6349800 : swap_allocno_copy_ends_if_necessary (ira_copy_t cp)
    1452                 :            : {
    1453                 :          0 :   if (ALLOCNO_NUM (cp->first) <= ALLOCNO_NUM (cp->second))
    1454                 :            :     return;
    1455                 :            : 
    1456                 :    4128870 :   std::swap (cp->first, cp->second);
    1457                 :    4128870 :   std::swap (cp->prev_first_allocno_copy, cp->prev_second_allocno_copy);
    1458                 :    4128870 :   std::swap (cp->next_first_allocno_copy, cp->next_second_allocno_copy);
    1459                 :            : }
    1460                 :            : 
    1461                 :            : /* Create (or update frequency if the copy already exists) and return
    1462                 :            :    the copy of allocnos FIRST and SECOND with frequency FREQ
    1463                 :            :    corresponding to move insn INSN (if any) and originated from
    1464                 :            :    LOOP_TREE_NODE.  */
    1465                 :            : ira_copy_t
    1466                 :    6379840 : ira_add_allocno_copy (ira_allocno_t first, ira_allocno_t second, int freq,
    1467                 :            :                       bool constraint_p, rtx_insn *insn,
    1468                 :            :                       ira_loop_tree_node_t loop_tree_node)
    1469                 :            : {
    1470                 :    6379840 :   ira_copy_t cp;
    1471                 :            : 
    1472                 :    6379840 :   if ((cp = find_allocno_copy (first, second, insn, loop_tree_node)) != NULL)
    1473                 :            :     {
    1474                 :      30040 :       cp->freq += freq;
    1475                 :      30040 :       return cp;
    1476                 :            :     }
    1477                 :    6349800 :   cp = ira_create_copy (first, second, freq, constraint_p, insn,
    1478                 :            :                         loop_tree_node);
    1479                 :    6349800 :   ira_assert (first != NULL && second != NULL);
    1480                 :    6349800 :   add_allocno_copy_to_list (cp);
    1481                 :    6349800 :   swap_allocno_copy_ends_if_necessary (cp);
    1482                 :            :   return cp;
    1483                 :            : }
    1484                 :            : 
    1485                 :            : /* Print info about copy CP into file F.  */
    1486                 :            : static void
    1487                 :        226 : print_copy (FILE *f, ira_copy_t cp)
    1488                 :            : {
    1489                 :        452 :   fprintf (f, "  cp%d:a%d(r%d)<->a%d(r%d)@%d:%s\n", cp->num,
    1490                 :        226 :            ALLOCNO_NUM (cp->first), ALLOCNO_REGNO (cp->first),
    1491                 :        226 :            ALLOCNO_NUM (cp->second), ALLOCNO_REGNO (cp->second), cp->freq,
    1492                 :        226 :            cp->insn != NULL
    1493                 :        128 :            ? "move" : cp->constraint_p ? "constraint" : "shuffle");
    1494                 :        226 : }
    1495                 :            : 
    1496                 :            : DEBUG_FUNCTION void
    1497                 :          0 : debug (ira_allocno_copy &ref)
    1498                 :            : {
    1499                 :          0 :   print_copy (stderr, &ref);
    1500                 :          0 : }
    1501                 :            : 
    1502                 :            : DEBUG_FUNCTION void
    1503                 :          0 : debug (ira_allocno_copy *ptr)
    1504                 :            : {
    1505                 :          0 :   if (ptr)
    1506                 :          0 :     debug (*ptr);
    1507                 :            :   else
    1508                 :          0 :     fprintf (stderr, "<nil>\n");
    1509                 :          0 : }
    1510                 :            : 
    1511                 :            : /* Print info about copy CP into stderr.  */
    1512                 :            : void
    1513                 :          0 : ira_debug_copy (ira_copy_t cp)
    1514                 :            : {
    1515                 :          0 :   print_copy (stderr, cp);
    1516                 :          0 : }
    1517                 :            : 
    1518                 :            : /* Print info about all copies into file F.  */
    1519                 :            : static void
    1520                 :        102 : print_copies (FILE *f)
    1521                 :            : {
    1522                 :        102 :   ira_copy_t cp;
    1523                 :        102 :   ira_copy_iterator ci;
    1524                 :            : 
    1525                 :        328 :   FOR_EACH_COPY (cp, ci)
    1526                 :        226 :     print_copy (f, cp);
    1527                 :        102 : }
    1528                 :            : 
    1529                 :            : /* Print info about all copies into stderr.  */
    1530                 :            : void
    1531                 :          0 : ira_debug_copies (void)
    1532                 :            : {
    1533                 :          0 :   print_copies (stderr);
    1534                 :          0 : }
    1535                 :            : 
    1536                 :            : /* Print info about copies involving allocno A into file F.  */
    1537                 :            : static void
    1538                 :          0 : print_allocno_copies (FILE *f, ira_allocno_t a)
    1539                 :            : {
    1540                 :          0 :   ira_allocno_t another_a;
    1541                 :          0 :   ira_copy_t cp, next_cp;
    1542                 :            : 
    1543                 :          0 :   fprintf (f, " a%d(r%d):", ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
    1544                 :          0 :   for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
    1545                 :            :     {
    1546                 :          0 :       if (cp->first == a)
    1547                 :            :         {
    1548                 :          0 :           next_cp = cp->next_first_allocno_copy;
    1549                 :          0 :           another_a = cp->second;
    1550                 :            :         }
    1551                 :          0 :       else if (cp->second == a)
    1552                 :            :         {
    1553                 :          0 :           next_cp = cp->next_second_allocno_copy;
    1554                 :          0 :           another_a = cp->first;
    1555                 :            :         }
    1556                 :            :       else
    1557                 :          0 :         gcc_unreachable ();
    1558                 :          0 :       fprintf (f, " cp%d:a%d(r%d)@%d", cp->num,
    1559                 :            :                ALLOCNO_NUM (another_a), ALLOCNO_REGNO (another_a), cp->freq);
    1560                 :            :     }
    1561                 :          0 :   fprintf (f, "\n");
    1562                 :          0 : }
    1563                 :            : 
    1564                 :            : DEBUG_FUNCTION void
    1565                 :          0 : debug (ira_allocno &ref)
    1566                 :            : {
    1567                 :          0 :   print_allocno_copies (stderr, &ref);
    1568                 :          0 : }
    1569                 :            : 
    1570                 :            : DEBUG_FUNCTION void
    1571                 :          0 : debug (ira_allocno *ptr)
    1572                 :            : {
    1573                 :          0 :   if (ptr)
    1574                 :          0 :     debug (*ptr);
    1575                 :            :   else
    1576                 :          0 :     fprintf (stderr, "<nil>\n");
    1577                 :          0 : }
    1578                 :            : 
    1579                 :            : 
    1580                 :            : /* Print info about copies involving allocno A into stderr.  */
    1581                 :            : void
    1582                 :          0 : ira_debug_allocno_copies (ira_allocno_t a)
    1583                 :            : {
    1584                 :          0 :   print_allocno_copies (stderr, a);
    1585                 :          0 : }
    1586                 :            : 
    1587                 :            : /* The function frees memory allocated for copy CP.  */
    1588                 :            : static void
    1589                 :    6349800 : finish_copy (ira_copy_t cp)
    1590                 :            : {
    1591                 :          0 :   copy_pool.remove (cp);
    1592                 :    6349800 : }
    1593                 :            : 
    1594                 :            : 
    1595                 :            : /* Free memory allocated for all copies.  */
    1596                 :            : static void
    1597                 :     944096 : finish_copies (void)
    1598                 :            : {
    1599                 :     944096 :   ira_copy_t cp;
    1600                 :     944096 :   ira_copy_iterator ci;
    1601                 :            : 
    1602                 :     944096 :   FOR_EACH_COPY (cp, ci)
    1603                 :   13643700 :     finish_copy (cp);
    1604                 :     944096 :   copy_vec.release ();
    1605                 :     944096 :   copy_pool.release ();
    1606                 :     944096 : }
    1607                 :            : 
    1608                 :            : 
    1609                 :            : 
    1610                 :            : /* Pools for cost vectors.  It is defined only for allocno classes.  */
    1611                 :            : static pool_allocator *cost_vector_pool[N_REG_CLASSES];
    1612                 :            : 
    1613                 :            : /* The function initiates work with hard register cost vectors.  It
    1614                 :            :    creates allocation pool for each allocno class.  */
    1615                 :            : static void
    1616                 :     944096 : initiate_cost_vectors (void)
    1617                 :            : {
    1618                 :     944096 :   int i;
    1619                 :     944096 :   enum reg_class aclass;
    1620                 :            : 
    1621                 :   24461500 :   for (i = 0; i < ira_allocno_classes_num; i++)
    1622                 :            :     {
    1623                 :   23517400 :       aclass = ira_allocno_classes[i];
    1624                 :   23517400 :       cost_vector_pool[aclass] = new pool_allocator
    1625                 :   23517400 :         ("cost vectors", sizeof (int) * (ira_class_hard_regs_num[aclass]));
    1626                 :            :     }
    1627                 :     944096 : }
    1628                 :            : 
    1629                 :            : /* Allocate and return a cost vector VEC for ACLASS.  */
    1630                 :            : int *
    1631                 :   24384300 : ira_allocate_cost_vector (reg_class_t aclass)
    1632                 :            : {
    1633                 :   24384300 :   return (int*) cost_vector_pool[(int) aclass]->allocate ();
    1634                 :            : }
    1635                 :            : 
    1636                 :            : /* Free a cost vector VEC for ACLASS.  */
    1637                 :            : void
    1638                 :   24384300 : ira_free_cost_vector (int *vec, reg_class_t aclass)
    1639                 :            : {
    1640                 :   24384300 :   ira_assert (vec != NULL);
    1641                 :   24384300 :   cost_vector_pool[(int) aclass]->remove (vec);
    1642                 :   24384300 : }
    1643                 :            : 
    1644                 :            : /* Finish work with hard register cost vectors.  Release allocation
    1645                 :            :    pool for each allocno class.  */
    1646                 :            : static void
    1647                 :     944096 : finish_cost_vectors (void)
    1648                 :            : {
    1649                 :     944096 :   int i;
    1650                 :     944096 :   enum reg_class aclass;
    1651                 :            : 
    1652                 :   24461500 :   for (i = 0; i < ira_allocno_classes_num; i++)
    1653                 :            :     {
    1654                 :   23517400 :       aclass = ira_allocno_classes[i];
    1655                 :   47034800 :       delete cost_vector_pool[aclass];
    1656                 :            :     }
    1657                 :     944096 : }
    1658                 :            : 
    1659                 :            : 
    1660                 :            : 
    1661                 :            : /* Compute a post-ordering of the reverse control flow of the loop body
    1662                 :            :    designated by the children nodes of LOOP_NODE, whose body nodes in
    1663                 :            :    pre-order are input as LOOP_PREORDER.  Return a VEC with a post-order
    1664                 :            :    of the reverse loop body.
    1665                 :            : 
    1666                 :            :    For the post-order of the reverse CFG, we visit the basic blocks in
    1667                 :            :    LOOP_PREORDER array in the reverse order of where they appear.
    1668                 :            :    This is important: We do not just want to compute a post-order of
    1669                 :            :    the reverse CFG, we want to make a best-guess for a visiting order that
    1670                 :            :    minimizes the number of chain elements per allocno live range.  If the
    1671                 :            :    blocks would be visited in a different order, we would still compute a
    1672                 :            :    correct post-ordering but it would be less likely that two nodes
    1673                 :            :    connected by an edge in the CFG are neighbors in the topsort.  */
    1674                 :            : 
    1675                 :            : static vec<ira_loop_tree_node_t>
    1676                 :    1269780 : ira_loop_tree_body_rev_postorder (ira_loop_tree_node_t loop_node ATTRIBUTE_UNUSED,
    1677                 :            :                                   vec<ira_loop_tree_node_t> loop_preorder)
    1678                 :            : {
    1679                 :    1269780 :   vec<ira_loop_tree_node_t> topsort_nodes = vNULL;
    1680                 :    1269780 :   unsigned int n_loop_preorder;
    1681                 :            : 
    1682                 :    1269780 :   n_loop_preorder = loop_preorder.length ();
    1683                 :    1269780 :   if (n_loop_preorder != 0)
    1684                 :            :     {
    1685                 :    1269780 :       ira_loop_tree_node_t subloop_node;
    1686                 :    1269780 :       unsigned int i;
    1687                 :    2539570 :       auto_vec<ira_loop_tree_node_t> dfs_stack;
    1688                 :            : 
    1689                 :            :       /* This is a bit of strange abuse of the BB_VISITED flag:  We use
    1690                 :            :          the flag to mark blocks we still have to visit to add them to
    1691                 :            :          our post-order.  Define an alias to avoid confusion.  */
    1692                 :            : #define BB_TO_VISIT BB_VISITED
    1693                 :            : 
    1694                 :   10345900 :       FOR_EACH_VEC_ELT (loop_preorder, i, subloop_node)
    1695                 :            :         {
    1696                 :    9076070 :           gcc_checking_assert (! (subloop_node->bb->flags & BB_TO_VISIT));
    1697                 :    9076070 :           subloop_node->bb->flags |= BB_TO_VISIT;
    1698                 :            :         }
    1699                 :            : 
    1700                 :    1269780 :       topsort_nodes.create (n_loop_preorder);
    1701                 :    1269780 :       dfs_stack.create (n_loop_preorder);
    1702                 :            : 
    1703                 :   10345900 :       FOR_EACH_VEC_ELT_REVERSE (loop_preorder, i, subloop_node)
    1704                 :            :         {
    1705                 :    9076070 :           if (! (subloop_node->bb->flags & BB_TO_VISIT))
    1706                 :    2358120 :             continue;
    1707                 :            : 
    1708                 :    6717960 :           subloop_node->bb->flags &= ~BB_TO_VISIT;
    1709                 :    6717960 :           dfs_stack.quick_push (subloop_node);
    1710                 :   17327300 :           while (! dfs_stack.is_empty ())
    1711                 :            :             {
    1712                 :   10609300 :               edge e;
    1713                 :   10609300 :               edge_iterator ei;
    1714                 :            : 
    1715                 :   10609300 :               ira_loop_tree_node_t n = dfs_stack.last ();
    1716                 :   26462200 :               FOR_EACH_EDGE (e, ei, n->bb->preds)
    1717                 :            :                 {
    1718                 :   15852900 :                   ira_loop_tree_node_t pred_node;
    1719                 :   15852900 :                   basic_block pred_bb = e->src;
    1720                 :            : 
    1721                 :   15852900 :                   if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
    1722                 :     944096 :                     continue;
    1723                 :            : 
    1724                 :   14908800 :                   pred_node = IRA_BB_NODE_BY_INDEX (pred_bb->index);
    1725                 :   14908800 :                   if (pred_node != n
    1726                 :   14786700 :                       && (pred_node->bb->flags & BB_TO_VISIT))
    1727                 :            :                     {
    1728                 :    2358120 :                       pred_node->bb->flags &= ~BB_TO_VISIT;
    1729                 :   18211000 :                       dfs_stack.quick_push (pred_node);
    1730                 :            :                     }
    1731                 :            :                 }
    1732                 :   10609300 :               if (n == dfs_stack.last ())
    1733                 :            :                 {
    1734                 :    9076070 :                   dfs_stack.pop ();
    1735                 :   19685400 :                   topsort_nodes.quick_push (n);
    1736                 :            :                 }
    1737                 :            :             }
    1738                 :            :         }
    1739                 :            : 
    1740                 :            : #undef BB_TO_VISIT
    1741                 :            :     }
    1742                 :            : 
    1743                 :    2539570 :   gcc_assert (topsort_nodes.length () == n_loop_preorder);
    1744                 :    1269780 :   return topsort_nodes;
    1745                 :            : }
    1746                 :            : 
    1747                 :            : /* The current loop tree node and its regno allocno map.  */
    1748                 :            : ira_loop_tree_node_t ira_curr_loop_tree_node;
    1749                 :            : ira_allocno_t *ira_curr_regno_allocno_map;
    1750                 :            : 
    1751                 :            : /* This recursive function traverses loop tree with root LOOP_NODE
    1752                 :            :    calling non-null functions PREORDER_FUNC and POSTORDER_FUNC
    1753                 :            :    correspondingly in preorder and postorder.  The function sets up
    1754                 :            :    IRA_CURR_LOOP_TREE_NODE and IRA_CURR_REGNO_ALLOCNO_MAP.  If BB_P,
    1755                 :            :    basic block nodes of LOOP_NODE is also processed (before its
    1756                 :            :    subloop nodes).
    1757                 :            :    
    1758                 :            :    If BB_P is set and POSTORDER_FUNC is given, the basic blocks in
    1759                 :            :    the loop are passed in the *reverse* post-order of the *reverse*
    1760                 :            :    CFG.  This is only used by ira_create_allocno_live_ranges, which
    1761                 :            :    wants to visit basic blocks in this order to minimize the number
    1762                 :            :    of elements per live range chain.
    1763                 :            :    Note that the loop tree nodes are still visited in the normal,
    1764                 :            :    forward post-order of  the loop tree.  */
    1765                 :            : 
    1766                 :            : void
    1767                 :    8500730 : ira_traverse_loop_tree (bool bb_p, ira_loop_tree_node_t loop_node,
    1768                 :            :                         void (*preorder_func) (ira_loop_tree_node_t),
    1769                 :            :                         void (*postorder_func) (ira_loop_tree_node_t))
    1770                 :            : {
    1771                 :    8500730 :   ira_loop_tree_node_t subloop_node;
    1772                 :            : 
    1773                 :    8500730 :   ira_assert (loop_node->bb == NULL);
    1774                 :    8500730 :   ira_curr_loop_tree_node = loop_node;
    1775                 :    8500730 :   ira_curr_regno_allocno_map = ira_curr_loop_tree_node->regno_allocno_map;
    1776                 :            : 
    1777                 :    8500730 :   if (preorder_func != NULL)
    1778                 :    6216720 :     (*preorder_func) (loop_node);
    1779                 :            : 
    1780                 :    8500730 :   if (bb_p)
    1781                 :            :     {
    1782                 :   13387000 :       auto_vec<ira_loop_tree_node_t> loop_preorder;
    1783                 :    6693510 :       unsigned int i;
    1784                 :            : 
    1785                 :            :       /* Add all nodes to the set of nodes to visit.  The IRA loop tree
    1786                 :            :          is set up such that nodes in the loop body appear in a pre-order
    1787                 :            :          of their place in the CFG.  */
    1788                 :    6693510 :       for (subloop_node = loop_node->children;
    1789                 :   58024700 :            subloop_node != NULL;
    1790                 :   51331200 :            subloop_node = subloop_node->next)
    1791                 :   51331200 :         if (subloop_node->bb != NULL)
    1792                 :   49517800 :           loop_preorder.safe_push (subloop_node);
    1793                 :            : 
    1794                 :    6693510 :       if (preorder_func != NULL)
    1795                 :   51289200 :         FOR_EACH_VEC_ELT (loop_preorder, i, subloop_node)
    1796                 :   40441700 :           (*preorder_func) (subloop_node);
    1797                 :            : 
    1798                 :    6693510 :       if (postorder_func != NULL)
    1799                 :            :         {
    1800                 :    1269780 :           vec<ira_loop_tree_node_t> loop_rev_postorder =
    1801                 :    1269780 :             ira_loop_tree_body_rev_postorder (loop_node, loop_preorder);
    1802                 :   11615600 :           FOR_EACH_VEC_ELT_REVERSE (loop_rev_postorder, i, subloop_node)
    1803                 :    9076070 :             (*postorder_func) (subloop_node);
    1804                 :    7963300 :           loop_rev_postorder.release ();
    1805                 :            :         }
    1806                 :            :     }
    1807                 :            : 
    1808                 :    8500730 :   for (subloop_node = loop_node->subloops;
    1809                 :   10744200 :        subloop_node != NULL;
    1810                 :    2243500 :        subloop_node = subloop_node->subloop_next)
    1811                 :            :     {
    1812                 :    2243500 :       ira_assert (subloop_node->bb == NULL);
    1813                 :    2243500 :       ira_traverse_loop_tree (bb_p, subloop_node,
    1814                 :            :                               preorder_func, postorder_func);
    1815                 :            :     }
    1816                 :            : 
    1817                 :    8500730 :   ira_curr_loop_tree_node = loop_node;
    1818                 :    8500730 :   ira_curr_regno_allocno_map = ira_curr_loop_tree_node->regno_allocno_map;
    1819                 :            : 
    1820                 :    8500730 :   if (postorder_func != NULL)
    1821                 :    2284020 :     (*postorder_func) (loop_node);
    1822                 :    8500730 : }
    1823                 :            : 
    1824                 :            : 
    1825                 :            : 
    1826                 :            : /* The basic block currently being processed.  */
    1827                 :            : static basic_block curr_bb;
    1828                 :            : 
    1829                 :            : /* This recursive function creates allocnos corresponding to
    1830                 :            :    pseudo-registers containing in X.  True OUTPUT_P means that X is
    1831                 :            :    an lvalue.  PARENT corresponds to the parent expression of X.  */
    1832                 :            : static void
    1833                 :  285291000 : create_insn_allocnos (rtx x, rtx outer, bool output_p)
    1834                 :            : {
    1835                 :  285291000 :   int i, j;
    1836                 :  285291000 :   const char *fmt;
    1837                 :  285291000 :   enum rtx_code code = GET_CODE (x);
    1838                 :            : 
    1839                 :  285291000 :   if (code == REG)
    1840                 :            :     {
    1841                 :   93187400 :       int regno;
    1842                 :            : 
    1843                 :   93187400 :       if ((regno = REGNO (x)) >= FIRST_PSEUDO_REGISTER)
    1844                 :            :         {
    1845                 :   50626400 :           ira_allocno_t a;
    1846                 :            : 
    1847                 :   50626400 :           if ((a = ira_curr_regno_allocno_map[regno]) == NULL)
    1848                 :            :             {
    1849                 :   17487900 :               a = ira_create_allocno (regno, false, ira_curr_loop_tree_node);
    1850                 :   17487900 :               if (outer != NULL && GET_CODE (outer) == SUBREG)
    1851                 :            :                 {
    1852                 :     711080 :                   machine_mode wmode = GET_MODE (outer);
    1853                 :     711080 :                   if (partial_subreg_p (ALLOCNO_WMODE (a), wmode))
    1854                 :      88330 :                     ALLOCNO_WMODE (a) = wmode;
    1855                 :            :                 }
    1856                 :            :             }
    1857                 :            : 
    1858                 :   50626400 :           ALLOCNO_NREFS (a)++;
    1859                 :   50626400 :           ALLOCNO_FREQ (a) += REG_FREQ_FROM_BB (curr_bb);
    1860                 :   50626400 :           if (output_p)
    1861                 :   20403400 :             bitmap_set_bit (ira_curr_loop_tree_node->modified_regnos, regno);
    1862                 :            :         }
    1863                 :   93187400 :       return;
    1864                 :            :     }
    1865                 :  192104000 :   else if (code == SET)
    1866                 :            :     {
    1867                 :   49215100 :       create_insn_allocnos (SET_DEST (x), NULL, true);
    1868                 :   49215100 :       create_insn_allocnos (SET_SRC (x), NULL, false);
    1869                 :   49215100 :       return;
    1870                 :            :     }
    1871                 :  142889000 :   else if (code == CLOBBER)
    1872                 :            :     {
    1873                 :    6766260 :       create_insn_allocnos (XEXP (x, 0), NULL, true);
    1874                 :    6766260 :       return;
    1875                 :            :     }
    1876                 :  136122000 :   else if (code == MEM)
    1877                 :            :     {
    1878                 :   22582000 :       create_insn_allocnos (XEXP (x, 0), NULL, false);
    1879                 :   22582000 :       return;
    1880                 :            :     }
    1881                 :  113540000 :   else if (code == PRE_DEC || code == POST_DEC || code == PRE_INC ||
    1882                 :  111516000 :            code == POST_INC || code == POST_MODIFY || code == PRE_MODIFY)
    1883                 :            :     {
    1884                 :    2097180 :       create_insn_allocnos (XEXP (x, 0), NULL, true);
    1885                 :    2097180 :       create_insn_allocnos (XEXP (x, 0), NULL, false);
    1886                 :    2097180 :       return;
    1887                 :            :     }
    1888                 :            : 
    1889                 :  111443000 :   fmt = GET_RTX_FORMAT (code);
    1890                 :  268793000 :   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
    1891                 :            :     {
    1892                 :  157350000 :       if (fmt[i] == 'e')
    1893                 :   84400800 :         create_insn_allocnos (XEXP (x, i), x, output_p);
    1894                 :   72949400 :       else if (fmt[i] == 'E')
    1895                 :   25249300 :         for (j = 0; j < XVECLEN (x, i); j++)
    1896                 :   16730000 :           create_insn_allocnos (XVECEXP (x, i, j), x, output_p);
    1897                 :            :     }
    1898                 :            : }
    1899                 :            : 
    1900                 :            : /* Create allocnos corresponding to pseudo-registers living in the
    1901                 :            :    basic block represented by the corresponding loop tree node
    1902                 :            :    BB_NODE.  */
    1903                 :            : static void
    1904                 :    9076070 : create_bb_allocnos (ira_loop_tree_node_t bb_node)
    1905                 :            : {
    1906                 :    9076070 :   basic_block bb;
    1907                 :    9076070 :   rtx_insn *insn;
    1908                 :    9076070 :   unsigned int i;
    1909                 :    9076070 :   bitmap_iterator bi;
    1910                 :            : 
    1911                 :    9076070 :   curr_bb = bb = bb_node->bb;
    1912                 :    9076070 :   ira_assert (bb != NULL);
    1913                 :  202752000 :   FOR_BB_INSNS_REVERSE (bb, insn)
    1914                 :   96838000 :     if (NONDEBUG_INSN_P (insn))
    1915                 :   52187500 :       create_insn_allocnos (PATTERN (insn), NULL, false);
    1916                 :            :   /* It might be a allocno living through from one subloop to
    1917                 :            :      another.  */
    1918                 :   64858700 :   EXECUTE_IF_SET_IN_REG_SET (df_get_live_in (bb), FIRST_PSEUDO_REGISTER, i, bi)
    1919                 :   55782600 :     if (ira_curr_regno_allocno_map[i] == NULL)
    1920                 :     474701 :       ira_create_allocno (i, false, ira_curr_loop_tree_node);
    1921                 :    9076070 : }
    1922                 :            : 
    1923                 :            : /* Create allocnos corresponding to pseudo-registers living on edge E
    1924                 :            :    (a loop entry or exit).  Also mark the allocnos as living on the
    1925                 :            :    loop border. */
    1926                 :            : static void
    1927                 :     968475 : create_loop_allocnos (edge e)
    1928                 :            : {
    1929                 :     968475 :   unsigned int i;
    1930                 :     968475 :   bitmap live_in_regs, border_allocnos;
    1931                 :     968475 :   bitmap_iterator bi;
    1932                 :     968475 :   ira_loop_tree_node_t parent;
    1933                 :            : 
    1934                 :     968475 :   live_in_regs = df_get_live_in (e->dest);
    1935                 :     968475 :   border_allocnos = ira_curr_loop_tree_node->border_allocnos;
    1936                 :   11839400 :   EXECUTE_IF_SET_IN_REG_SET (df_get_live_out (e->src),
    1937                 :            :                              FIRST_PSEUDO_REGISTER, i, bi)
    1938                 :   10870900 :     if (bitmap_bit_p (live_in_regs, i))
    1939                 :            :       {
    1940                 :    6899480 :         if (ira_curr_regno_allocno_map[i] == NULL)
    1941                 :            :           {
    1942                 :            :             /* The order of creations is important for right
    1943                 :            :                ira_regno_allocno_map.  */
    1944                 :    3339210 :             if ((parent = ira_curr_loop_tree_node->parent) != NULL
    1945                 :    3339210 :                 && parent->regno_allocno_map[i] == NULL)
    1946                 :        142 :               ira_create_allocno (i, false, parent);
    1947                 :    3339210 :             ira_create_allocno (i, false, ira_curr_loop_tree_node);
    1948                 :            :           }
    1949                 :    6899480 :         bitmap_set_bit (border_allocnos,
    1950                 :    6899480 :                         ALLOCNO_NUM (ira_curr_regno_allocno_map[i]));
    1951                 :            :       }
    1952                 :     968475 : }
    1953                 :            : 
    1954                 :            : /* Create allocnos corresponding to pseudo-registers living in loop
    1955                 :            :    represented by the corresponding loop tree node LOOP_NODE.  This
    1956                 :            :    function is called by ira_traverse_loop_tree.  */
    1957                 :            : static void
    1958                 :   10345900 : create_loop_tree_node_allocnos (ira_loop_tree_node_t loop_node)
    1959                 :            : {
    1960                 :   10345900 :   if (loop_node->bb != NULL)
    1961                 :    9076070 :     create_bb_allocnos (loop_node);
    1962                 :    1269780 :   else if (loop_node != ira_loop_tree_root)
    1963                 :            :     {
    1964                 :     325688 :       int i;
    1965                 :     325688 :       edge_iterator ei;
    1966                 :     325688 :       edge e;
    1967                 :     325688 :       vec<edge> edges;
    1968                 :            : 
    1969                 :     325688 :       ira_assert (current_loops != NULL);
    1970                 :    1016160 :       FOR_EACH_EDGE (e, ei, loop_node->loop->header->preds)
    1971                 :     690469 :         if (e->src != loop_node->loop->latch)
    1972                 :     373216 :           create_loop_allocnos (e);
    1973                 :            : 
    1974                 :     325688 :       edges = get_loop_exit_edges (loop_node->loop);
    1975                 :     920947 :       FOR_EACH_VEC_ELT (edges, i, e)
    1976                 :     595259 :         create_loop_allocnos (e);
    1977                 :     646773 :       edges.release ();
    1978                 :            :     }
    1979                 :   10345900 : }
    1980                 :            : 
    1981                 :            : /* Propagate information about allocnos modified inside the loop given
    1982                 :            :    by its LOOP_TREE_NODE to its parent.  */
    1983                 :            : static void
    1984                 :    1014230 : propagate_modified_regnos (ira_loop_tree_node_t loop_tree_node)
    1985                 :            : {
    1986                 :    1014230 :   if (loop_tree_node == ira_loop_tree_root)
    1987                 :            :     return;
    1988                 :     325683 :   ira_assert (loop_tree_node->bb == NULL);
    1989                 :     325683 :   bitmap_ior_into (loop_tree_node->parent->modified_regnos,
    1990                 :     325683 :                    loop_tree_node->modified_regnos);
    1991                 :            : }
    1992                 :            : 
    1993                 :            : /* Propagate new info about allocno A (see comments about accumulated
    1994                 :            :    info in allocno definition) to the corresponding allocno on upper
    1995                 :            :    loop tree level.  So allocnos on upper levels accumulate
    1996                 :            :    information about the corresponding allocnos in nested regions.
    1997                 :            :    The new info means allocno info finally calculated in this
    1998                 :            :    file.  */
    1999                 :            : static void
    2000                 :      25420 : propagate_allocno_info (void)
    2001                 :            : {
    2002                 :      25420 :   int i;
    2003                 :      25420 :   ira_allocno_t a, parent_a;
    2004                 :      25420 :   ira_loop_tree_node_t parent;
    2005                 :      25420 :   enum reg_class aclass;
    2006                 :            : 
    2007                 :      25420 :   if (flag_ira_region != IRA_REGION_ALL
    2008                 :      25420 :       && flag_ira_region != IRA_REGION_MIXED)
    2009                 :            :     return;
    2010                 :    6798660 :   for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--)
    2011                 :    6773240 :     for (a = ira_regno_allocno_map[i];
    2012                 :   11993500 :          a != NULL;
    2013                 :    5220300 :          a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
    2014                 :    5220300 :       if ((parent = ALLOCNO_LOOP_TREE_NODE (a)->parent) != NULL
    2015                 :    3460270 :           && (parent_a = parent->regno_allocno_map[i]) != NULL
    2016                 :            :           /* There are no caps yet at this point.  So use
    2017                 :            :              border_allocnos to find allocnos for the propagation.  */
    2018                 :    7373550 :           && bitmap_bit_p (ALLOCNO_LOOP_TREE_NODE (a)->border_allocnos,
    2019                 :            :                            ALLOCNO_NUM (a)))
    2020                 :            :         {
    2021                 :    2146940 :           if (! ALLOCNO_BAD_SPILL_P (a))
    2022                 :    2059190 :             ALLOCNO_BAD_SPILL_P (parent_a) = false;
    2023                 :    2146940 :           ALLOCNO_NREFS (parent_a) += ALLOCNO_NREFS (a);
    2024                 :    2146940 :           ALLOCNO_FREQ (parent_a) += ALLOCNO_FREQ (a);
    2025                 :    2146940 :           ALLOCNO_CALL_FREQ (parent_a) += ALLOCNO_CALL_FREQ (a);
    2026                 :    2146940 :           merge_hard_reg_conflicts (a, parent_a, true);
    2027                 :    2146940 :           ALLOCNO_CALLS_CROSSED_NUM (parent_a)
    2028                 :    2146940 :             += ALLOCNO_CALLS_CROSSED_NUM (a);
    2029                 :    2146940 :           ALLOCNO_CHEAP_CALLS_CROSSED_NUM (parent_a)
    2030                 :    2146940 :             += ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a);
    2031                 :    2146940 :           ALLOCNO_CROSSED_CALLS_ABIS (parent_a)
    2032                 :    2146940 :             |= ALLOCNO_CROSSED_CALLS_ABIS (a);
    2033                 :    2146940 :           ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS (parent_a)
    2034                 :    2146940 :             |= ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS (a);
    2035                 :    2146940 :           ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (parent_a)
    2036                 :    2146940 :             += ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a);
    2037                 :    2146940 :           aclass = ALLOCNO_CLASS (a);
    2038                 :    2146940 :           ira_assert (aclass == ALLOCNO_CLASS (parent_a));
    2039                 :    2146940 :           ira_allocate_and_accumulate_costs
    2040                 :    2146940 :             (&ALLOCNO_HARD_REG_COSTS (parent_a), aclass,
    2041                 :            :              ALLOCNO_HARD_REG_COSTS (a));
    2042                 :    2146940 :           ira_allocate_and_accumulate_costs
    2043                 :    2146940 :             (&ALLOCNO_CONFLICT_HARD_REG_COSTS (parent_a),
    2044                 :            :              aclass,
    2045                 :            :              ALLOCNO_CONFLICT_HARD_REG_COSTS (a));
    2046                 :    2146940 :           ALLOCNO_CLASS_COST (parent_a)
    2047                 :    2146940 :             += ALLOCNO_CLASS_COST (a);
    2048                 :    2146940 :           ALLOCNO_MEMORY_COST (parent_a) += ALLOCNO_MEMORY_COST (a);
    2049                 :            :         }
    2050                 :            : }
    2051                 :            : 
    2052                 :            : /* Create allocnos corresponding to pseudo-registers in the current
    2053                 :            :    function.  Traverse the loop tree for this.  */
    2054                 :            : static void
    2055                 :     944096 : create_allocnos (void)
    2056                 :            : {
    2057                 :            :   /* We need to process BB first to correctly link allocnos by member
    2058                 :            :      next_regno_allocno.  */
    2059                 :     944096 :   ira_traverse_loop_tree (true, ira_loop_tree_root,
    2060                 :            :                           create_loop_tree_node_allocnos, NULL);
    2061                 :     944096 :   if (optimize)
    2062                 :     688548 :     ira_traverse_loop_tree (false, ira_loop_tree_root, NULL,
    2063                 :            :                             propagate_modified_regnos);
    2064                 :     944096 : }
    2065                 :            : 
    2066                 :            : 
    2067                 :            : 
    2068                 :            : /* The page contains function to remove some regions from a separate
    2069                 :            :    register allocation.  We remove regions whose separate allocation
    2070                 :            :    will hardly improve the result.  As a result we speed up regional
    2071                 :            :    register allocation.  */
    2072                 :            : 
    2073                 :            : /* The function changes the object in range list given by R to OBJ.  */
    2074                 :            : static void
    2075                 :          0 : change_object_in_range_list (live_range_t r, ira_object_t obj)
    2076                 :            : {
    2077                 :          0 :   for (; r != NULL; r = r->next)
    2078                 :    1290960 :     r->object = obj;
    2079                 :          0 : }
    2080                 :            : 
    2081                 :            : /* Move all live ranges associated with allocno FROM to allocno TO.  */
    2082                 :            : static void
    2083                 :    1193380 : move_allocno_live_ranges (ira_allocno_t from, ira_allocno_t to)
    2084                 :            : {
    2085                 :    1193380 :   int i;
    2086                 :    1193380 :   int n = ALLOCNO_NUM_OBJECTS (from);
    2087                 :            : 
    2088                 :    1193380 :   gcc_assert (n == ALLOCNO_NUM_OBJECTS (to));
    2089                 :            : 
    2090                 :    2389400 :   for (i = 0; i < n; i++)
    2091                 :            :     {
    2092                 :    1196020 :       ira_object_t from_obj = ALLOCNO_OBJECT (from, i);
    2093                 :    1196020 :       ira_object_t to_obj = ALLOCNO_OBJECT (to, i);
    2094                 :    1196020 :       live_range_t lr = OBJECT_LIVE_RANGES (from_obj);
    2095                 :            : 
    2096                 :    1196020 :       if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL)
    2097                 :            :         {
    2098                 :        138 :           fprintf (ira_dump_file,
    2099                 :            :                    "      Moving ranges of a%dr%d to a%dr%d: ",
    2100                 :            :                    ALLOCNO_NUM (from), ALLOCNO_REGNO (from),
    2101                 :            :                    ALLOCNO_NUM (to), ALLOCNO_REGNO (to));
    2102                 :        138 :           ira_print_live_range_list (ira_dump_file, lr);
    2103                 :            :         }
    2104                 :    2486990 :       change_object_in_range_list (lr, to_obj);
    2105                 :    1196020 :       OBJECT_LIVE_RANGES (to_obj)
    2106                 :    1196020 :         = ira_merge_live_ranges (lr, OBJECT_LIVE_RANGES (to_obj));
    2107                 :    1196020 :       OBJECT_LIVE_RANGES (from_obj) = NULL;
    2108                 :            :     }
    2109                 :    1193380 : }
    2110                 :            : 
    2111                 :            : static void
    2112                 :          0 : copy_allocno_live_ranges (ira_allocno_t from, ira_allocno_t to)
    2113                 :            : {
    2114                 :          0 :   int i;
    2115                 :          0 :   int n = ALLOCNO_NUM_OBJECTS (from);
    2116                 :            : 
    2117                 :          0 :   gcc_assert (n == ALLOCNO_NUM_OBJECTS (to));
    2118                 :            : 
    2119                 :          0 :   for (i = 0; i < n; i++)
    2120                 :            :     {
    2121                 :          0 :       ira_object_t from_obj = ALLOCNO_OBJECT (from, i);
    2122                 :          0 :       ira_object_t to_obj = ALLOCNO_OBJECT (to, i);
    2123                 :          0 :       live_range_t lr = OBJECT_LIVE_RANGES (from_obj);
    2124                 :            : 
    2125                 :          0 :       if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL)
    2126                 :            :         {
    2127                 :          0 :           fprintf (ira_dump_file, "      Copying ranges of a%dr%d to a%dr%d: ",
    2128                 :            :                    ALLOCNO_NUM (from), ALLOCNO_REGNO (from),
    2129                 :            :                    ALLOCNO_NUM (to), ALLOCNO_REGNO (to));
    2130                 :          0 :           ira_print_live_range_list (ira_dump_file, lr);
    2131                 :            :         }
    2132                 :          0 :       lr = ira_copy_live_range_list (lr);
    2133                 :          0 :       change_object_in_range_list (lr, to_obj);
    2134                 :          0 :       OBJECT_LIVE_RANGES (to_obj)
    2135                 :          0 :         = ira_merge_live_ranges (lr, OBJECT_LIVE_RANGES (to_obj));
    2136                 :            :     }
    2137                 :          0 : }
    2138                 :            : 
    2139                 :            : /* Return TRUE if NODE represents a loop with low register
    2140                 :            :    pressure.  */
    2141                 :            : static bool
    2142                 :     545785 : low_pressure_loop_node_p (ira_loop_tree_node_t node)
    2143                 :            : {
    2144                 :     545785 :   int i;
    2145                 :     545785 :   enum reg_class pclass;
    2146                 :            : 
    2147                 :          0 :   if (node->bb != NULL)
    2148                 :            :     return false;
    2149                 :            : 
    2150                 :    2326610 :   for (i = 0; i < ira_pressure_classes_num; i++)
    2151                 :            :     {
    2152                 :    1886420 :       pclass = ira_pressure_classes[i];
    2153                 :    1886420 :       if (node->reg_pressure[pclass] > ira_class_hard_regs_num[pclass]
    2154                 :     105591 :           && ira_class_hard_regs_num[pclass] > 1)
    2155                 :            :         return false;
    2156                 :            :     }
    2157                 :            :   return true;
    2158                 :            : }
    2159                 :            : 
    2160                 :            : #ifdef STACK_REGS
    2161                 :            : /* Return TRUE if LOOP has a complex enter or exit edge.  We don't
    2162                 :            :    form a region from such loop if the target use stack register
    2163                 :            :    because reg-stack.c cannot deal with such edges.  */
    2164                 :            : static bool
    2165                 :     105591 : loop_with_complex_edge_p (class loop *loop)
    2166                 :            : {
    2167                 :     105591 :   int i;
    2168                 :     105591 :   edge_iterator ei;
    2169                 :     105591 :   edge e;
    2170                 :     105591 :   vec<edge> edges;
    2171                 :     105591 :   bool res;
    2172                 :            : 
    2173                 :     335937 :   FOR_EACH_EDGE (e, ei, loop->header->preds)
    2174                 :     230346 :     if (e->flags & EDGE_EH)
    2175                 :            :       return true;
    2176                 :     105591 :   edges = get_loop_exit_edges (loop);
    2177                 :     105591 :   res = false;
    2178                 :     319529 :   FOR_EACH_VEC_ELT (edges, i, e)
    2179                 :     214228 :     if (e->flags & EDGE_COMPLEX)
    2180                 :            :       {
    2181                 :            :         res = true;
    2182                 :            :         break;
    2183                 :            :       }
    2184                 :     105591 :   edges.release ();
    2185                 :            :   return res;
    2186                 :            : }
    2187                 :            : #endif
    2188                 :            : 
    2189                 :            : /* Sort loops for marking them for removal.  We put already marked
    2190                 :            :    loops first, then less frequent loops next, and then outer loops
    2191                 :            :    next.  */
    2192                 :            : static int
    2193                 :    3186740 : loop_compare_func (const void *v1p, const void *v2p)
    2194                 :            : {
    2195                 :    3186740 :   int diff;
    2196                 :    3186740 :   ira_loop_tree_node_t l1 = *(const ira_loop_tree_node_t *) v1p;
    2197                 :    3186740 :   ira_loop_tree_node_t l2 = *(const ira_loop_tree_node_t *) v2p;
    2198                 :            : 
    2199                 :    3186740 :   ira_assert (l1->parent != NULL && l2->parent != NULL);
    2200                 :    3186740 :   if (l1->to_remove_p && ! l2->to_remove_p)
    2201                 :            :     return -1;
    2202                 :    3150600 :   if (! l1->to_remove_p && l2->to_remove_p)
    2203                 :            :     return 1;
    2204                 :    6239930 :   if ((diff = l1->loop->header->count.to_frequency (cfun)
    2205                 :    3119970 :               - l2->loop->header->count.to_frequency (cfun)) != 0)
    2206                 :            :     return diff;
    2207                 :    3485120 :   if ((diff = (int) loop_depth (l1->loop) - (int) loop_depth (l2->loop)) != 0)
    2208                 :            :     return diff;
    2209                 :            :   /* Make sorting stable.  */
    2210                 :     923906 :   return l1->loop_num - l2->loop_num;
    2211                 :            : }
    2212                 :            : 
    2213                 :            : /* Mark loops which should be removed from regional allocation.  We
    2214                 :            :    remove a loop with low register pressure inside another loop with
    2215                 :            :    register pressure.  In this case a separate allocation of the loop
    2216                 :            :    hardly helps (for irregular register file architecture it could
    2217                 :            :    help by choosing a better hard register in the loop but we prefer
    2218                 :            :    faster allocation even in this case).  We also remove cheap loops
    2219                 :            :    if there are more than param_ira_max_loops_num of them.  Loop with EH
    2220                 :            :    exit or enter edges are removed too because the allocation might
    2221                 :            :    require put pseudo moves on the EH edges (we could still do this
    2222                 :            :    for pseudos with caller saved hard registers in some cases but it
    2223                 :            :    is impossible to say here or during top-down allocation pass what
    2224                 :            :    hard register the pseudos get finally).  */
    2225                 :            : static void
    2226                 :     660335 : mark_loops_for_removal (void)
    2227                 :            : {
    2228                 :     660335 :   int i, n;
    2229                 :     660335 :   ira_loop_tree_node_t *sorted_loops;
    2230                 :     660335 :   loop_p loop;
    2231                 :            : 
    2232                 :     660335 :   ira_assert (current_loops != NULL);
    2233                 :     660335 :   sorted_loops
    2234                 :     660335 :     = (ira_loop_tree_node_t *) ira_allocate (sizeof (ira_loop_tree_node_t)
    2235                 :     660335 :                                              * number_of_loops (cfun));
    2236                 :    2316940 :   for (n = i = 0; vec_safe_iterate (get_loops (cfun), i, &loop); i++)
    2237                 :     996274 :     if (ira_loop_nodes[i].regno_allocno_map != NULL)
    2238                 :            :       {
    2239                 :     986023 :         if (ira_loop_nodes[i].parent == NULL)
    2240                 :            :           {
    2241                 :            :             /* Don't remove the root.  */
    2242                 :     660335 :             ira_loop_nodes[i].to_remove_p = false;
    2243                 :     660335 :             continue;
    2244                 :            :           }
    2245                 :     325688 :         sorted_loops[n++] = &ira_loop_nodes[i];
    2246                 :     651376 :         ira_loop_nodes[i].to_remove_p
    2247                 :     651376 :           = ((low_pressure_loop_node_p (ira_loop_nodes[i].parent)
    2248                 :     440194 :               && low_pressure_loop_node_p (&ira_loop_nodes[i]))
    2249                 :            : #ifdef STACK_REGS
    2250                 :     325688 :              || loop_with_complex_edge_p (ira_loop_nodes[i].loop)
    2251                 :            : #endif
    2252                 :            :              );
    2253                 :            :       }
    2254                 :     660335 :   qsort (sorted_loops, n, sizeof (ira_loop_tree_node_t), loop_compare_func);
    2255                 :     662840 :   for (i = 0; i < n - param_ira_max_loops_num; i++)
    2256                 :            :     {
    2257                 :       2505 :       sorted_loops[i]->to_remove_p = true;
    2258                 :       2505 :       if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
    2259                 :          0 :         fprintf
    2260                 :          0 :           (ira_dump_file,
    2261                 :            :            "  Mark loop %d (header %d, freq %d, depth %d) for removal (%s)\n",
    2262                 :          0 :            sorted_loops[i]->loop_num, sorted_loops[i]->loop->header->index,
    2263                 :          0 :            sorted_loops[i]->loop->header->count.to_frequency (cfun),
    2264                 :          0 :            loop_depth (sorted_loops[i]->loop),
    2265                 :          0 :            low_pressure_loop_node_p (sorted_loops[i]->parent)
    2266                 :          0 :            && low_pressure_loop_node_p (sorted_loops[i])
    2267                 :            :            ? "low pressure" : "cheap loop");
    2268                 :            :     }
    2269                 :     660335 :   ira_free (sorted_loops);
    2270                 :     660335 : }
    2271                 :            : 
    2272                 :            : /* Mark all loops but root for removing.  */
    2273                 :            : static void
    2274                 :          0 : mark_all_loops_for_removal (void)
    2275                 :            : {
    2276                 :          0 :   int i;
    2277                 :          0 :   loop_p loop;
    2278                 :            : 
    2279                 :          0 :   ira_assert (current_loops != NULL);
    2280                 :          0 :   FOR_EACH_VEC_SAFE_ELT (get_loops (cfun), i, loop)
    2281                 :          0 :     if (ira_loop_nodes[i].regno_allocno_map != NULL)
    2282                 :            :       {
    2283                 :          0 :         if (ira_loop_nodes[i].parent == NULL)
    2284                 :            :           {
    2285                 :            :             /* Don't remove the root.  */
    2286                 :          0 :             ira_loop_nodes[i].to_remove_p = false;
    2287                 :          0 :             continue;
    2288                 :            :           }
    2289                 :          0 :         ira_loop_nodes[i].to_remove_p = true;
    2290                 :          0 :         if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
    2291                 :          0 :           fprintf
    2292                 :          0 :             (ira_dump_file,
    2293                 :            :              "  Mark loop %d (header %d, freq %d, depth %d) for removal\n",
    2294                 :            :              ira_loop_nodes[i].loop_num,
    2295                 :          0 :              ira_loop_nodes[i].loop->header->index,
    2296                 :          0 :              ira_loop_nodes[i].loop->header->count.to_frequency (cfun),
    2297                 :          0 :              loop_depth (ira_loop_nodes[i].loop));
    2298                 :            :       }
    2299                 :          0 : }
    2300                 :            : 
    2301                 :            : /* Definition of vector of loop tree nodes.  */
    2302                 :            : 
    2303                 :            : /* Vec containing references to all removed loop tree nodes.  */
    2304                 :            : static vec<ira_loop_tree_node_t> removed_loop_vec;
    2305                 :            : 
    2306                 :            : /* Vec containing references to all children of loop tree nodes.  */
    2307                 :            : static vec<ira_loop_tree_node_t> children_vec;
    2308                 :            : 
    2309                 :            : /* Remove subregions of NODE if their separate allocation will not
    2310                 :            :    improve the result.  */
    2311                 :            : static void
    2312                 :     986023 : remove_uneccesary_loop_nodes_from_loop_tree (ira_loop_tree_node_t node)
    2313                 :            : {
    2314                 :     986023 :   unsigned int start;
    2315                 :     986023 :   bool remove_p;
    2316                 :     986023 :   ira_loop_tree_node_t subnode;
    2317                 :            : 
    2318                 :     986023 :   remove_p = node->to_remove_p;
    2319                 :     986023 :   if (! remove_p)
    2320                 :     764778 :     children_vec.safe_push (node);
    2321                 :     986023 :   start = children_vec.length ();
    2322                 :    8087730 :   for (subnode = node->children; subnode != NULL; subnode = subnode->next)
    2323                 :    7101700 :     if (subnode->bb == NULL)
    2324                 :     325688 :       remove_uneccesary_loop_nodes_from_loop_tree (subnode);
    2325                 :            :     else
    2326                 :    6776020 :       children_vec.safe_push (subnode);
    2327                 :     986023 :   node->children = node->subloops = NULL;
    2328                 :     986023 :   if (remove_p)
    2329                 :            :     {
    2330                 :     221245 :       removed_loop_vec.safe_push (node);
    2331                 :     221245 :       return;
    2332                 :            :     }
    2333                 :   15290500 :   while (children_vec.length () > start)
    2334                 :            :     {
    2335                 :    6880460 :       subnode = children_vec.pop ();
    2336                 :    6880460 :       subnode->parent = node;
    2337                 :    6880460 :       subnode->next = node->children;
    2338                 :    6880460 :       node->children = subnode;
    2339                 :    6880460 :       if (subnode->bb == NULL)
    2340                 :            :         {
    2341                 :     104443 :           subnode->subloop_next = node->subloops;
    2342                 :     104443 :           node->subloops = subnode;
    2343                 :            :         }
    2344                 :            :     }
    2345                 :            : }
    2346                 :            : 
    2347                 :            : /* Return TRUE if NODE is inside PARENT.  */
    2348                 :            : static bool
    2349                 :       3918 : loop_is_inside_p (ira_loop_tree_node_t node, ira_loop_tree_node_t parent)
    2350                 :            : {
    2351                 :       6723 :   for (node = node->parent; node != NULL; node = node->parent)
    2352                 :       4773 :     if (node == parent)
    2353                 :            :       return true;
    2354                 :            :   return false;
    2355                 :            : }
    2356                 :            : 
    2357                 :            : /* Sort allocnos according to their order in regno allocno list.  */
    2358                 :            : static int
    2359                 :       2423 : regno_allocno_order_compare_func (const void *v1p, const void *v2p)
    2360                 :            : {
    2361                 :       2423 :   ira_allocno_t a1 = *(const ira_allocno_t *) v1p;
    2362                 :       2423 :   ira_allocno_t a2 = *(const ira_allocno_t *) v2p;
    2363                 :       2423 :   ira_loop_tree_node_t n1 = ALLOCNO_LOOP_TREE_NODE (a1);
    2364                 :       2423 :   ira_loop_tree_node_t n2 = ALLOCNO_LOOP_TREE_NODE (a2);
    2365                 :            : 
    2366                 :       4846 :   if (loop_is_inside_p (n1, n2))
    2367                 :            :     return -1;
    2368                 :       2990 :   else if (loop_is_inside_p (n2, n1))
    2369                 :            :     return 1;
    2370                 :            :   /* If allocnos are equally good, sort by allocno numbers, so that
    2371                 :            :      the results of qsort leave nothing to chance.  We put allocnos
    2372                 :            :      with higher number first in the list because it is the original
    2373                 :            :      order for allocnos from loops on the same levels.  */
    2374                 :        455 :   return ALLOCNO_NUM (a2) - ALLOCNO_NUM (a1);
    2375                 :            : }
    2376                 :            : 
    2377                 :            : /* This array is used to sort allocnos to restore allocno order in
    2378                 :            :    the regno allocno list.  */
    2379                 :            : static ira_allocno_t *regno_allocnos;
    2380                 :            : 
    2381                 :            : /* Restore allocno order for REGNO in the regno allocno list.  */
    2382                 :            : static void
    2383                 :     898560 : ira_rebuild_regno_allocno_list (int regno)
    2384                 :            : {
    2385                 :     898560 :   int i, n;
    2386                 :     898560 :   ira_allocno_t a;
    2387                 :            : 
    2388                 :     898560 :   for (n = 0, a = ira_regno_allocno_map[regno];
    2389                 :    1797530 :        a != NULL;
    2390                 :     898966 :        a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
    2391                 :     898966 :     regno_allocnos[n++] = a;
    2392                 :     898560 :   ira_assert (n > 0);
    2393                 :     898560 :   qsort (regno_allocnos, n, sizeof (ira_allocno_t),
    2394                 :            :          regno_allocno_order_compare_func);
    2395                 :     898966 :   for (i = 1; i < n; i++)
    2396                 :        406 :     ALLOCNO_NEXT_REGNO_ALLOCNO (regno_allocnos[i - 1]) = regno_allocnos[i];
    2397                 :     898560 :   ALLOCNO_NEXT_REGNO_ALLOCNO (regno_allocnos[n - 1]) = NULL;
    2398                 :     898560 :   ira_regno_allocno_map[regno] = regno_allocnos[0];
    2399                 :     898560 :   if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
    2400                 :         67 :     fprintf (ira_dump_file, " Rebuilding regno allocno list for %d\n", regno);
    2401                 :     898560 : }
    2402                 :            : 
    2403                 :            : /* Propagate info from allocno FROM_A to allocno A.  */
    2404                 :            : static void
    2405                 :    1193380 : propagate_some_info_from_allocno (ira_allocno_t a, ira_allocno_t from_a)
    2406                 :            : {
    2407                 :    1193380 :   enum reg_class aclass;
    2408                 :            : 
    2409                 :    1193380 :   merge_hard_reg_conflicts (from_a, a, false);
    2410                 :    1193380 :   ALLOCNO_NREFS (a) += ALLOCNO_NREFS (from_a);
    2411                 :    1193380 :   ALLOCNO_FREQ (a) += ALLOCNO_FREQ (from_a);
    2412                 :    1193380 :   ALLOCNO_CALL_FREQ (a) += ALLOCNO_CALL_FREQ (from_a);
    2413                 :    1193380 :   ALLOCNO_CALLS_CROSSED_NUM (a) += ALLOCNO_CALLS_CROSSED_NUM (from_a);
    2414                 :    1193380 :   ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a)
    2415                 :    1193380 :     += ALLOCNO_CHEAP_CALLS_CROSSED_NUM (from_a);
    2416                 :    1193380 :   ALLOCNO_CROSSED_CALLS_ABIS (a) |= ALLOCNO_CROSSED_CALLS_ABIS (from_a);
    2417                 :    1193380 :   ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS (a)
    2418                 :    1193380 :     |= ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS (from_a);
    2419                 :            : 
    2420                 :    1193380 :   ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a)
    2421                 :    1193380 :     += ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (from_a);
    2422                 :    1193380 :   if (! ALLOCNO_BAD_SPILL_P (from_a))
    2423                 :     852124 :     ALLOCNO_BAD_SPILL_P (a) = false;
    2424                 :    1193380 :   aclass = ALLOCNO_CLASS (from_a);
    2425                 :    1193380 :   ira_assert (aclass == ALLOCNO_CLASS (a));
    2426                 :    1193380 :   ira_allocate_and_accumulate_costs (&ALLOCNO_HARD_REG_COSTS (a), aclass,
    2427                 :            :                                      ALLOCNO_HARD_REG_COSTS (from_a));
    2428                 :    1193380 :   ira_allocate_and_accumulate_costs (&ALLOCNO_CONFLICT_HARD_REG_COSTS (a),
    2429                 :            :                                      aclass,
    2430                 :            :                                      ALLOCNO_CONFLICT_HARD_REG_COSTS (from_a));
    2431                 :    1193380 :   ALLOCNO_CLASS_COST (a) += ALLOCNO_CLASS_COST (from_a);
    2432                 :    1193380 :   ALLOCNO_MEMORY_COST (a) += ALLOCNO_MEMORY_COST (from_a);
    2433                 :    1193380 : }
    2434                 :            : 
    2435                 :            : /* Remove allocnos from loops removed from the allocation
    2436                 :            :    consideration.  */
    2437                 :            : static void
    2438                 :     660335 : remove_unnecessary_allocnos (void)
    2439                 :            : {
    2440                 :     660335 :   int regno;
    2441                 :     660335 :   bool merged_p, rebuild_p;
    2442                 :     660335 :   ira_allocno_t a, prev_a, next_a, parent_a;
    2443                 :     660335 :   ira_loop_tree_node_t a_node, parent;
    2444                 :            : 
    2445                 :     660335 :   merged_p = false;
    2446                 :     660335 :   regno_allocnos = NULL;
    2447                 :   31604100 :   for (regno = max_reg_num () - 1; regno >= FIRST_PSEUDO_REGISTER; regno--)
    2448                 :            :     {
    2449                 :   30943800 :       rebuild_p = false;
    2450                 :   30943800 :       for (prev_a = NULL, a = ira_regno_allocno_map[regno];
    2451                 :   45890300 :            a != NULL;
    2452                 :            :            a = next_a)
    2453                 :            :         {
    2454                 :   14946500 :           next_a = ALLOCNO_NEXT_REGNO_ALLOCNO (a);
    2455                 :   14946500 :           a_node = ALLOCNO_LOOP_TREE_NODE (a);
    2456                 :   14946500 :           if (! a_node->to_remove_p)
    2457                 :            :             prev_a = a;
    2458                 :            :           else
    2459                 :            :             {
    2460                 :    2091940 :               for (parent = a_node->parent;
    2461                 :    2291320 :                    (parent_a = parent->regno_allocno_map[regno]) == NULL
    2462                 :    2291320 :                      && parent->to_remove_p;
    2463                 :     199385 :                    parent = parent->parent)
    2464                 :            :                 ;
    2465                 :    2091940 :               if (parent_a == NULL)
    2466                 :            :                 {
    2467                 :            :                   /* There are no allocnos with the same regno in
    2468                 :            :                      upper region -- just move the allocno to the
    2469                 :            :                      upper region.  */
    2470                 :     898560 :                   prev_a = a;
    2471                 :     898560 :                   ALLOCNO_LOOP_TREE_NODE (a) = parent;
    2472                 :     898560 :                   parent->regno_allocno_map[regno] = a;
    2473                 :     898560 :                   bitmap_set_bit (parent->all_allocnos, ALLOCNO_NUM (a));
    2474                 :     898560 :                   rebuild_p = true;
    2475                 :            :                 }
    2476                 :            :               else
    2477                 :            :                 {
    2478                 :            :                   /* Remove the allocno and update info of allocno in
    2479                 :            :                      the upper region.  */
    2480                 :    1193380 :                   if (prev_a == NULL)
    2481                 :    1165320 :                     ira_regno_allocno_map[regno] = next_a;
    2482                 :            :                   else
    2483                 :      28057 :                     ALLOCNO_NEXT_REGNO_ALLOCNO (prev_a) = next_a;
    2484                 :    1193380 :                   move_allocno_live_ranges (a, parent_a);
    2485                 :    1193380 :                   merged_p = true;
    2486                 :    1193380 :                   propagate_some_info_from_allocno (parent_a, a);
    2487                 :            :                   /* Remove it from the corresponding regno allocno
    2488                 :            :                      map to avoid info propagation of subsequent
    2489                 :            :                      allocno into this already removed allocno.  */
    2490                 :    1193380 :                   a_node->regno_allocno_map[regno] = NULL;
    2491                 :    1193380 :                   ira_remove_allocno_prefs (a);
    2492                 :   47083700 :                   finish_allocno (a);
    2493                 :            :                 }
    2494                 :            :             }
    2495                 :            :         }
    2496                 :   30943800 :       if (rebuild_p)
    2497                 :            :         /* We need to restore the order in regno allocno list.  */
    2498                 :            :         {
    2499                 :     898560 :           if (regno_allocnos == NULL)
    2500                 :      80437 :             regno_allocnos
    2501                 :      80437 :               = (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t)
    2502                 :      80437 :                                                 * ira_allocnos_num);
    2503                 :     898560 :           ira_rebuild_regno_allocno_list (regno);
    2504                 :            :         }
    2505                 :            :     }
    2506                 :     660335 :   if (merged_p)
    2507                 :      99411 :     ira_rebuild_start_finish_chains ();
    2508                 :     660335 :   if (regno_allocnos != NULL)
    2509                 :      80437 :     ira_free (regno_allocnos);
    2510                 :     660335 : }
    2511                 :            : 
    2512                 :            : /* Remove allocnos from all loops but the root.  */
    2513                 :            : static void
    2514                 :          0 : remove_low_level_allocnos (void)
    2515                 :            : {
    2516                 :          0 :   int regno;
    2517                 :          0 :   bool merged_p, propagate_p;
    2518                 :          0 :   ira_allocno_t a, top_a;
    2519                 :          0 :   ira_loop_tree_node_t a_node, parent;
    2520                 :          0 :   ira_allocno_iterator ai;
    2521                 :            : 
    2522                 :          0 :   merged_p = false;
    2523                 :          0 :   FOR_EACH_ALLOCNO (a, ai)
    2524                 :            :     {
    2525                 :          0 :       a_node = ALLOCNO_LOOP_TREE_NODE (a);
    2526                 :          0 :       if (a_node == ira_loop_tree_root || ALLOCNO_CAP_MEMBER (a) != NULL)
    2527                 :          0 :         continue;
    2528                 :          0 :       regno = ALLOCNO_REGNO (a);
    2529                 :          0 :       if ((top_a = ira_loop_tree_root->regno_allocno_map[regno]) == NULL)
    2530                 :            :         {
    2531                 :          0 :           ALLOCNO_LOOP_TREE_NODE (a) = ira_loop_tree_root;
    2532                 :          0 :           ira_loop_tree_root->regno_allocno_map[regno] = a;
    2533                 :          0 :           continue;
    2534                 :            :         }
    2535                 :          0 :       propagate_p = a_node->parent->regno_allocno_map[regno] == NULL;
    2536                 :            :       /* Remove the allocno and update info of allocno in the upper
    2537                 :            :          region.  */
    2538                 :          0 :       move_allocno_live_ranges (a, top_a);
    2539                 :          0 :       merged_p = true;
    2540                 :          0 :       if (propagate_p)
    2541                 :          0 :         propagate_some_info_from_allocno (top_a, a);
    2542                 :            :     }
    2543                 :          0 :   FOR_EACH_ALLOCNO (a, ai)
    2544                 :            :     {
    2545                 :          0 :       a_node = ALLOCNO_LOOP_TREE_NODE (a);
    2546                 :          0 :       if (a_node == ira_loop_tree_root)
    2547                 :          0 :         continue;
    2548                 :          0 :       parent = a_node->parent;
    2549                 :          0 :       regno = ALLOCNO_REGNO (a);
    2550                 :          0 :       if (ALLOCNO_CAP_MEMBER (a) != NULL)
    2551                 :          0 :         ira_assert (ALLOCNO_CAP (a) != NULL);
    2552                 :          0 :       else if (ALLOCNO_CAP (a) == NULL)
    2553                 :          0 :         ira_assert (parent->regno_allocno_map[regno] != NULL);
    2554                 :            :     }
    2555                 :          0 :   FOR_EACH_ALLOCNO (a, ai)
    2556                 :            :     {
    2557                 :          0 :       regno = ALLOCNO_REGNO (a);
    2558                 :          0 :       if (ira_loop_tree_root->regno_allocno_map[regno] == a)
    2559                 :            :         {
    2560                 :          0 :           ira_object_t obj;
    2561                 :          0 :           ira_allocno_object_iterator oi;
    2562                 :            : 
    2563                 :          0 :           ira_regno_allocno_map[regno] = a;
    2564                 :          0 :           ALLOCNO_NEXT_REGNO_ALLOCNO (a) = NULL;
    2565                 :          0 :           ALLOCNO_CAP_MEMBER (a) = NULL;
    2566                 :          0 :           FOR_EACH_ALLOCNO_OBJECT (a, obj, oi)
    2567                 :          0 :             OBJECT_CONFLICT_HARD_REGS (obj)
    2568                 :          0 :               = OBJECT_TOTAL_CONFLICT_HARD_REGS (obj);
    2569                 :            : #ifdef STACK_REGS
    2570                 :          0 :           if (ALLOCNO_TOTAL_NO_STACK_REG_P (a))
    2571                 :          0 :             ALLOCNO_NO_STACK_REG_P (a) = true;
    2572                 :            : #endif
    2573                 :            :         }
    2574                 :            :       else
    2575                 :            :         {
    2576                 :          0 :           ira_remove_allocno_prefs (a);
    2577                 :          0 :           finish_allocno (a);
    2578                 :            :         }
    2579                 :            :     }
    2580                 :          0 :   if (merged_p)
    2581                 :          0 :     ira_rebuild_start_finish_chains ();
    2582                 :          0 : }
    2583                 :            : 
    2584                 :            : /* Remove loops from consideration.  We remove all loops except for
    2585                 :            :    root if ALL_P or loops for which a separate allocation will not
    2586                 :            :    improve the result.  We have to do this after allocno creation and
    2587                 :            :    their costs and allocno class evaluation because only after that
    2588                 :            :    the register pressure can be known and is calculated.  */
    2589                 :            : static void
    2590                 :     944096 : remove_unnecessary_regions (bool all_p)
    2591                 :            : {
    2592                 :     944096 :   if (current_loops == NULL)
    2593                 :            :     return;
    2594                 :     660335 :   if (all_p)
    2595                 :          0 :     mark_all_loops_for_removal ();
    2596                 :            :   else
    2597                 :     660335 :     mark_loops_for_removal ();
    2598                 :    1981000 :   children_vec.create (last_basic_block_for_fn (cfun)
    2599                 :    1320670 :                        + number_of_loops (cfun));
    2600                 :    1981000 :   removed_loop_vec.create (last_basic_block_for_fn (cfun)
    2601                 :    1320670 :                            + number_of_loops (cfun));
    2602                 :     660335 :   remove_uneccesary_loop_nodes_from_loop_tree (ira_loop_tree_root);
    2603                 :     660335 :   children_vec.release ();
    2604                 :     660335 :   if (all_p)
    2605                 :          0 :     remove_low_level_allocnos ();
    2606                 :            :   else
    2607                 :     660335 :     remove_unnecessary_allocnos ();
    2608                 :     881580 :   while (removed_loop_vec.length () > 0)
    2609                 :     221245 :     finish_loop_tree_node (removed_loop_vec.pop ());
    2610                 :     660335 :   removed_loop_vec.release ();
    2611                 :            : }
    2612                 :            : 
    2613                 :            : 
    2614                 :            : 
    2615                 :            : /* At this point true value of allocno attribute bad_spill_p means
    2616                 :            :    that there is an insn where allocno occurs and where the allocno
    2617                 :            :    cannot be used as memory.  The function updates the attribute, now
    2618                 :            :    it can be true only for allocnos which cannot be used as memory in
    2619                 :            :    an insn and in whose live ranges there is other allocno deaths.
    2620                 :            :    Spilling allocnos with true value will not improve the code because
    2621                 :            :    it will not make other allocnos colorable and additional reloads
    2622                 :            :    for the corresponding pseudo will be generated in reload pass for
    2623                 :            :    each insn it occurs.
    2624                 :            : 
    2625                 :            :    This is a trick mentioned in one classic article of Chaitin etc
    2626                 :            :    which is frequently omitted in other implementations of RA based on
    2627                 :            :    graph coloring.  */
    2628                 :            : static void
    2629                 :     944096 : update_bad_spill_attribute (void)
    2630                 :            : {
    2631                 :     944096 :   int i;
    2632                 :     944096 :   ira_allocno_t a;
    2633                 :     944096 :   ira_allocno_iterator ai;
    2634                 :     944096 :   ira_allocno_object_iterator aoi;
    2635                 :     944096 :   ira_object_t obj;
    2636                 :     944096 :   live_range_t r;
    2637                 :     944096 :   enum reg_class aclass;
    2638                 :   28322900 :   bitmap_head dead_points[N_REG_CLASSES];
    2639                 :            : 
    2640                 :   24461500 :   for (i = 0; i < ira_allocno_classes_num; i++)
    2641                 :            :     {
    2642                 :   23517400 :       aclass = ira_allocno_classes[i];
    2643                 :   23517400 :       bitmap_initialize (&dead_points[aclass], &reg_obstack);
    2644                 :            :     }
    2645                 :   62214000 :   FOR_EACH_ALLOCNO (a, ai)
    2646                 :            :     {
    2647                 :   20108600 :       aclass = ALLOCNO_CLASS (a);
    2648                 :   20108600 :       if (aclass == NO_REGS)
    2649                 :     848308 :         continue;
    2650                 :   60101500 :       FOR_EACH_ALLOCNO_OBJECT (a, obj, aoi)
    2651                 :   45042700 :         for (r = OBJECT_LIVE_RANGES (obj); r != NULL; r = r->next)
    2652                 :   25254200 :           bitmap_set_bit (&dead_points[aclass], r->finish);
    2653                 :            :     }
    2654                 :   65622800 :   FOR_EACH_ALLOCNO (a, ai)
    2655                 :            :     {
    2656                 :   20108600 :       aclass = ALLOCNO_CLASS (a);
    2657                 :   20108600 :       if (aclass == NO_REGS)
    2658                 :     848308 :         continue;
    2659                 :   19260300 :       if (! ALLOCNO_BAD_SPILL_P (a))
    2660                 :   13092400 :         continue;
    2661                 :   31566300 :       FOR_EACH_ALLOCNO_OBJECT (a, obj, aoi)
    2662                 :            :         {
    2663                 :   11012400 :           for (r = OBJECT_LIVE_RANGES (obj); r != NULL; r = r->next)
    2664                 :            :             {
    2665                 :    9880390 :               for (i = r->start + 1; i < r->finish; i++)
    2666                 :    5125810 :                 if (bitmap_bit_p (&dead_points[aclass], i))
    2667                 :            :                   break;
    2668                 :    6666740 :               if (i < r->finish)
    2669                 :            :                 break;
    2670                 :            :             }
    2671                 :    6257840 :           if (r != NULL)
    2672                 :            :             {
    2673                 :    1912160 :               ALLOCNO_BAD_SPILL_P (a) = false;
    2674                 :    1912160 :               break;
    2675                 :            :             }
    2676                 :            :         }
    2677                 :            :     }
    2678                 :   24461500 :   for (i = 0; i < ira_allocno_classes_num; i++)
    2679                 :            :     {
    2680                 :   23517400 :       aclass = ira_allocno_classes[i];
    2681                 :   23517400 :       bitmap_clear (&dead_points[aclass]);
    2682                 :            :     }
    2683                 :     944096 : }
    2684                 :            : 
    2685                 :            : 
    2686                 :            : 
    2687                 :            : /* Set up minimal and maximal live range points for allocnos.  */
    2688                 :            : static void
    2689                 :     944096 : setup_min_max_allocno_live_range_point (void)
    2690                 :            : {
    2691                 :     944096 :   int i;
    2692                 :     944096 :   ira_allocno_t a, parent_a, cap;
    2693                 :     944096 :   ira_allocno_iterator ai;
    2694                 :            : #ifdef ENABLE_IRA_CHECKING
    2695                 :     944096 :   ira_object_iterator oi;
    2696                 :     944096 :   ira_object_t obj;
    2697                 :            : #endif
    2698                 :     944096 :   live_range_t r;
    2699                 :     944096 :   ira_loop_tree_node_t parent;
    2700                 :            : 
    2701                 :   23853700 :   FOR_EACH_ALLOCNO (a, ai)
    2702                 :            :     {
    2703                 :   22909600 :       int n = ALLOCNO_NUM_OBJECTS (a);
    2704                 :            : 
    2705                 :   46369600 :       for (i = 0; i < n; i++)
    2706                 :            :         {
    2707                 :   23460000 :           ira_object_t obj = ALLOCNO_OBJECT (a, i);
    2708                 :   23460000 :           r = OBJECT_LIVE_RANGES (obj);
    2709                 :   23460000 :           if (r == NULL)
    2710                 :    2829140 :             continue;
    2711                 :   20630900 :           OBJECT_MAX (obj) = r->finish;
    2712                 :   26226800 :           for (; r->next != NULL; r = r->next)
    2713                 :            :             ;
    2714                 :   20630900 :           OBJECT_MIN (obj) = r->start;
    2715                 :            :         }
    2716                 :            :     }
    2717                 :   41089400 :   for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--)
    2718                 :   40145300 :     for (a = ira_regno_allocno_map[i];
    2719                 :   60253900 :          a != NULL;
    2720                 :   20108600 :          a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
    2721                 :            :       {
    2722                 :   20108600 :         int j;
    2723                 :   20108600 :         int n = ALLOCNO_NUM_OBJECTS (a);
    2724                 :            : 
    2725                 :   40745400 :         for (j = 0; j < n; j++)
    2726                 :            :           {
    2727                 :   20636800 :             ira_object_t obj = ALLOCNO_OBJECT (a, j);
    2728                 :   20636800 :             ira_object_t parent_obj;
    2729                 :            : 
    2730                 :   20636800 :             if (OBJECT_MAX (obj) < 0)
    2731                 :            :               {
    2732                 :            :                 /* The object is not used and hence does not live.  */
    2733                 :          0 :                 ira_assert (OBJECT_LIVE_RANGES (obj) == NULL);
    2734                 :          0 :                 OBJECT_MAX (obj) = 0;
    2735                 :          0 :                 OBJECT_MIN (obj) = 1;
    2736                 :          0 :                 continue;
    2737                 :            :               }
    2738                 :   20636800 :             ira_assert (ALLOCNO_CAP_MEMBER (a) == NULL);
    2739                 :            :             /* Accumulation of range info.  */
    2740                 :   20636800 :             if (ALLOCNO_CAP (a) != NULL)
    2741                 :            :               {
    2742                 :    4148810 :                 for (cap = ALLOCNO_CAP (a); cap != NULL; cap = ALLOCNO_CAP (cap))
    2743                 :            :                   {
    2744                 :    2823190 :                     ira_object_t cap_obj = ALLOCNO_OBJECT (cap, j);
    2745                 :    2823190 :                     if (OBJECT_MAX (cap_obj) < OBJECT_MAX (obj))
    2746                 :    2823190 :                       OBJECT_MAX (cap_obj) = OBJECT_MAX (obj);
    2747                 :    2823190 :                     if (OBJECT_MIN (cap_obj) > OBJECT_MIN (obj))
    2748                 :    2823190 :                       OBJECT_MIN (cap_obj) = OBJECT_MIN (obj);
    2749                 :            :                   }
    2750                 :    1325620 :                 continue;
    2751                 :            :               }
    2752                 :   19311200 :             if ((parent = ALLOCNO_LOOP_TREE_NODE (a)->parent) == NULL)
    2753                 :   17121200 :               continue;
    2754                 :    2190030 :             parent_a = parent->regno_allocno_map[i];
    2755                 :    2190030 :             parent_obj = ALLOCNO_OBJECT (parent_a, j);
    2756                 :    2190030 :             if (OBJECT_MAX (parent_obj) < OBJECT_MAX (obj))
    2757                 :    1393360 :               OBJECT_MAX (parent_obj) = OBJECT_MAX (obj);
    2758                 :    2190030 :             if (OBJECT_MIN (parent_obj) > OBJECT_MIN (obj))
    2759                 :       5991 :               OBJECT_MIN (parent_obj) = OBJECT_MIN (obj);
    2760                 :            :           }
    2761                 :            :       }
    2762                 :            : #ifdef ENABLE_IRA_CHECKING
    2763                 :   24404100 :   FOR_EACH_OBJECT (obj, oi)
    2764                 :            :     {
    2765                 :   23460000 :       if ((OBJECT_MIN (obj) >= 0 && OBJECT_MIN (obj) <= ira_max_point)
    2766                 :   23460000 :           && (OBJECT_MAX (obj) >= 0 && OBJECT_MAX (obj) <= ira_max_point))
    2767                 :   23460000 :         continue;
    2768                 :          0 :       gcc_unreachable ();
    2769                 :            :     }
    2770                 :            : #endif
    2771                 :     944096 : }
    2772                 :            : 
    2773                 :            : /* Sort allocnos according to their live ranges.  Allocnos with
    2774                 :            :    smaller allocno class are put first unless we use priority
    2775                 :            :    coloring.  Allocnos with the same class are ordered according
    2776                 :            :    their start (min).  Allocnos with the same start are ordered
    2777                 :            :    according their finish (max).  */
    2778                 :            : static int
    2779                 :  822910000 : object_range_compare_func (const void *v1p, const void *v2p)
    2780                 :            : {
    2781                 :  822910000 :   int diff;
    2782                 :  822910000 :   ira_object_t obj1 = *(const ira_object_t *) v1p;
    2783                 :  822910000 :   ira_object_t obj2 = *(const ira_object_t *) v2p;
    2784                 :  822910000 :   ira_allocno_t a1 = OBJECT_ALLOCNO (obj1);
    2785                 :  822910000 :   ira_allocno_t a2 = OBJECT_ALLOCNO (obj2);
    2786                 :            : 
    2787                 :  822910000 :   if ((diff = OBJECT_MIN (obj1) - OBJECT_MIN (obj2)) != 0)
    2788                 :            :     return diff;
    2789                 :  145472000 :   if ((diff = OBJECT_MAX (obj1) - OBJECT_MAX (obj2)) != 0)
    2790                 :            :      return diff;
    2791                 :  118438000 :   return ALLOCNO_NUM (a1) - ALLOCNO_NUM (a2);
    2792                 :            : }
    2793                 :            : 
    2794                 :            : /* Sort ira_object_id_map and set up conflict id of allocnos.  */
    2795                 :            : static void
    2796                 :     944096 : sort_conflict_id_map (void)
    2797                 :            : {
    2798                 :     944096 :   int i, num;
    2799                 :     944096 :   ira_allocno_t a;
    2800                 :     944096 :   ira_allocno_iterator ai;
    2801                 :            : 
    2802                 :     944096 :   num = 0;
    2803                 :     944096 :   FOR_EACH_ALLOCNO (a, ai)
    2804                 :            :     {
    2805                 :   22909600 :       ira_allocno_object_iterator oi;
    2806                 :   22909600 :       ira_object_t obj;
    2807                 :            : 
    2808                 :   70223300 :       FOR_EACH_ALLOCNO_OBJECT (a, obj, oi)
    2809                 :   23460000 :         ira_object_id_map[num++] = obj;
    2810                 :            :     }
    2811                 :     944096 :   if (num > 1)
    2812                 :     779967 :     qsort (ira_object_id_map, num, sizeof (ira_object_t),
    2813                 :            :            object_range_compare_func);
    2814                 :   24404100 :   for (i = 0; i < num; i++)
    2815                 :            :     {
    2816                 :   23460000 :       ira_object_t obj = ira_object_id_map[i];
    2817                 :            : 
    2818                 :   23460000 :       gcc_assert (obj != NULL);
    2819                 :   23460000 :       OBJECT_CONFLICT_ID (obj) = i;
    2820                 :            :     }
    2821                 :    2140120 :   for (i = num; i < ira_objects_num; i++)
    2822                 :    1196020 :     ira_object_id_map[i] = NULL;
    2823                 :     944096 : }
    2824                 :            : 
    2825                 :            : /* Set up minimal and maximal conflict ids of allocnos with which
    2826                 :            :    given allocno can conflict.  */
    2827                 :            : static void
    2828                 :     944096 : setup_min_max_conflict_allocno_ids (void)
    2829                 :            : {
    2830                 :     944096 :   int aclass;
    2831                 :     944096 :   int i, j, min, max, start, finish, first_not_finished, filled_area_start;
    2832                 :     944096 :   int *live_range_min, *last_lived;
    2833                 :     944096 :   int word0_min, word0_max;
    2834                 :     944096 :   ira_allocno_t a;
    2835                 :     944096 :   ira_allocno_iterator ai;
    2836                 :            : 
    2837                 :     944096 :   live_range_min = (int *) ira_allocate (sizeof (int) * ira_objects_num);
    2838                 :     944096 :   aclass = -1;
    2839                 :     944096 :   first_not_finished = -1;
    2840                 :   25600100 :   for (i = 0; i < ira_objects_num; i++)
    2841                 :            :     {
    2842                 :   24656000 :       ira_object_t obj = ira_object_id_map[i];
    2843                 :            : 
    2844                 :   24656000 :       if (obj == NULL)
    2845                 :    1196020 :         continue;
    2846                 :            : 
    2847                 :   23460000 :       a = OBJECT_ALLOCNO (obj);
    2848                 :            : 
    2849                 :   23460000 :       if (aclass < 0)
    2850                 :            :         {
    2851                 :     815446 :           aclass = ALLOCNO_CLASS (a);
    2852                 :     815446 :           min = i;
    2853                 :     815446 :           first_not_finished = i;
    2854                 :            :         }
    2855                 :            :       else
    2856                 :            :         {
    2857                 :   22644600 :           start = OBJECT_MIN (obj);
    2858                 :            :           /* If we skip an allocno, the allocno with smaller ids will
    2859                 :            :              be also skipped because of the secondary sorting the
    2860                 :            :              range finishes (see function
    2861                 :            :              object_range_compare_func).  */
    2862                 :   32442300 :           while (first_not_finished < i
    2863                 :   32442300 :                  && start > OBJECT_MAX (ira_object_id_map
    2864                 :            :                                         [first_not_finished]))
    2865                 :    9797700 :             first_not_finished++;
    2866                 :            :           min = first_not_finished;
    2867                 :            :         }
    2868                 :   23460000 :       if (min == i)
    2869                 :            :         /* We could increase min further in this case but it is good
    2870                 :            :            enough.  */
    2871                 :    4632850 :         min++;
    2872                 :   23460000 :       live_range_min[i] = OBJECT_MIN (obj);
    2873                 :   23460000 :       OBJECT_MIN (obj) = min;
    2874                 :            :     }
    2875                 :     944096 :   last_lived = (int *) ira_allocate (sizeof (int) * ira_max_point);
    2876                 :     944096 :   aclass = -1;
    2877                 :     944096 :   filled_area_start = -1;
    2878                 :   25600100 :   for (i = ira_objects_num - 1; i >= 0; i--)
    2879                 :            :     {
    2880                 :   24656000 :       ira_object_t obj = ira_object_id_map[i];
    2881                 :            : 
    2882                 :   24656000 :       if (obj == NULL)
    2883                 :    1196020 :         continue;
    2884                 :            : 
    2885                 :   23460000 :       a = OBJECT_ALLOCNO (obj);
    2886                 :   23460000 :       if (aclass < 0)
    2887                 :            :         {
    2888                 :     815446 :           aclass = ALLOCNO_CLASS (a);
    2889                 :   30023400 :           for (j = 0; j < ira_max_point; j++)
    2890                 :   29208000 :             last_lived[j] = -1;
    2891                 :            :           filled_area_start = ira_max_point;
    2892                 :            :         }
    2893                 :   23460000 :       min = live_range_min[i];
    2894                 :   23460000 :       finish = OBJECT_MAX (obj);
    2895                 :   23460000 :       max = last_lived[finish];
    2896                 :   23460000 :       if (max < 0)
    2897                 :            :         /* We could decrease max further in this case but it is good
    2898                 :            :            enough.  */
    2899                 :    9956300 :         max = OBJECT_CONFLICT_ID (obj) - 1;
    2900                 :   23460000 :       OBJECT_MAX (obj) = max;
    2901                 :            :       /* In filling, we can go further A range finish to recognize
    2902                 :            :          intersection quickly because if the finish of subsequently
    2903                 :            :          processed allocno (it has smaller conflict id) range is
    2904                 :            :          further A range finish than they are definitely intersected
    2905                 :            :          (the reason for this is the allocnos with bigger conflict id
    2906                 :            :          have their range starts not smaller than allocnos with
    2907                 :            :          smaller ids.  */
    2908                 :   52668000 :       for (j = min; j < filled_area_start; j++)
    2909                 :   29208000 :         last_lived[j] = i;
    2910                 :            :       filled_area_start = min;
    2911                 :            :     }
    2912                 :     944096 :   ira_free (last_lived);
    2913                 :     944096 :   ira_free (live_range_min);
    2914                 :            : 
    2915                 :            :   /* For allocnos with more than one object, we may later record extra conflicts in
    2916                 :            :      subobject 0 that we cannot really know about here.
    2917                 :            :      For now, simply widen the min/max range of these subobjects.  */
    2918                 :            : 
    2919                 :     944096 :   word0_min = INT_MAX;
    2920                 :     944096 :   word0_max = INT_MIN;
    2921                 :            : 
    2922                 :   24797800 :   FOR_EACH_ALLOCNO (a, ai)
    2923                 :            :     {
    2924                 :   22909600 :       int n = ALLOCNO_NUM_OBJECTS (a);
    2925                 :   22909600 :       ira_object_t obj0;
    2926                 :            : 
    2927                 :   22909600 :       if (n < 2)
    2928                 :   22359100 :         continue;
    2929                 :     550432 :       obj0 = ALLOCNO_OBJECT (a, 0);
    2930                 :     550432 :       if (OBJECT_CONFLICT_ID (obj0) < word0_min)
    2931                 :            :         word0_min = OBJECT_CONFLICT_ID (obj0);
    2932                 :     550432 :       if (OBJECT_CONFLICT_ID (obj0) > word0_max)
    2933                 :            :         word0_max = OBJECT_CONFLICT_ID (obj0);
    2934                 :            :     }
    2935                 :   23853700 :   FOR_EACH_ALLOCNO (a, ai)
    2936                 :            :     {
    2937                 :   22909600 :       int n = ALLOCNO_NUM_OBJECTS (a);
    2938                 :   22909600 :       ira_object_t obj0;
    2939                 :            : 
    2940                 :   22909600 :       if (n < 2)
    2941                 :   22359100 :         continue;
    2942                 :     550432 :       obj0 = ALLOCNO_OBJECT (a, 0);
    2943                 :     550432 :       if (OBJECT_MIN (obj0) > word0_min)
    2944                 :     258199 :         OBJECT_MIN (obj0) = word0_min;
    2945                 :     550432 :       if (OBJECT_MAX (obj0) < word0_max)
    2946                 :     384730 :         OBJECT_MAX (obj0) = word0_max;
    2947                 :            :     }
    2948                 :     944096 : }
    2949                 :            : 
    2950                 :            : 
    2951                 :            : 
    2952                 :            : static void
    2953                 :      25420 : create_caps (void)
    2954                 :            : {
    2955                 :      25420 :   ira_allocno_t a;
    2956                 :      25420 :   ira_allocno_iterator ai;
    2957                 :      25420 :   ira_loop_tree_node_t loop_tree_node;
    2958                 :            : 
    2959                 :    8046680 :   FOR_EACH_ALLOCNO (a, ai)
    2960                 :            :     {
    2961                 :    8021260 :       if (ALLOCNO_LOOP_TREE_NODE (a) == ira_loop_tree_root)
    2962                 :    3073360 :         continue;
    2963                 :    4947900 :       if (ALLOCNO_CAP_MEMBER (a) != NULL)
    2964                 :    1487630 :         create_cap_allocno (a);
    2965                 :    3460270 :       else if (ALLOCNO_CAP (a) == NULL)
    2966                 :            :         {
    2967                 :    3460270 :           loop_tree_node = ALLOCNO_LOOP_TREE_NODE (a);
    2968                 :    3460270 :           if (!bitmap_bit_p (loop_tree_node->border_allocnos, ALLOCNO_NUM (a)))
    2969                 :    1313340 :             create_cap_allocno (a);
    2970                 :            :         }
    2971                 :            :     }
    2972                 :      25420 : }
    2973                 :            : 
    2974                 :            : 
    2975                 :            : 
    2976                 :            : /* The page contains code transforming more one region internal
    2977                 :            :    representation (IR) to one region IR which is necessary for reload.
    2978                 :            :    This transformation is called IR flattening.  We might just rebuild
    2979                 :            :    the IR for one region but we don't do it because it takes a lot of
    2980                 :            :    time.  */
    2981                 :            : 
    2982                 :            : /* Map: regno -> allocnos which will finally represent the regno for
    2983                 :            :    IR with one region.  */
    2984                 :            : static ira_allocno_t *regno_top_level_allocno_map;
    2985                 :            : 
    2986                 :            : /* Find the allocno that corresponds to A at a level one higher up in the
    2987                 :            :    loop tree.  Returns NULL if A is a cap, or if it has no parent.  */
    2988                 :            : ira_allocno_t
    2989                 :  186758000 : ira_parent_allocno (ira_allocno_t a)
    2990                 :            : {
    2991                 :  186758000 :   ira_loop_tree_node_t parent;
    2992                 :            : 
    2993                 :  186758000 :   if (ALLOCNO_CAP (a) != NULL)
    2994                 :            :     return NULL;
    2995                 :            : 
    2996                 :  186758000 :   parent = ALLOCNO_LOOP_TREE_NODE (a)->parent;
    2997                 :  186758000 :   if (parent == NULL)
    2998                 :            :     return NULL;
    2999                 :            : 
    3000                 :  174346000 :   return parent->regno_allocno_map[ALLOCNO_REGNO (a)];
    3001                 :            : }
    3002                 :            : 
    3003                 :            : /* Find the allocno that corresponds to A at a level one higher up in the
    3004                 :            :    loop tree.  If ALLOCNO_CAP is set for A, return that.  */
    3005                 :            : ira_allocno_t
    3006                 :  336672000 : ira_parent_or_cap_allocno (ira_allocno_t a)
    3007                 :            : {
    3008                 :  336672000 :   if (ALLOCNO_CAP (a) != NULL)
    3009                 :            :     return ALLOCNO_CAP (a);
    3010                 :            : 
    3011                 :  186758000 :   return ira_parent_allocno (a);
    3012                 :            : }
    3013                 :            : 
    3014                 :            : /* Process all allocnos originated from pseudo REGNO and copy live
    3015                 :            :    ranges, hard reg conflicts, and allocno stack reg attributes from
    3016                 :            :    low level allocnos to final allocnos which are destinations of
    3017                 :            :    removed stores at a loop exit.  Return true if we copied live
    3018                 :            :    ranges.  */
    3019                 :            : static bool
    3020                 :          0 : copy_info_to_removed_store_destinations (int regno)
    3021                 :            : {
    3022                 :          0 :   ira_allocno_t a;
    3023                 :          0 :   ira_allocno_t parent_a = NULL;
    3024                 :          0 :   ira_loop_tree_node_t parent;
    3025                 :          0 :   bool merged_p;
    3026                 :            : 
    3027                 :          0 :   merged_p = false;
    3028                 :          0 :   for (a = ira_regno_allocno_map[regno];
    3029                 :          0 :        a != NULL;
    3030                 :          0 :        a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
    3031                 :            :     {
    3032                 :          0 :       if (a != regno_top_level_allocno_map[REGNO (allocno_emit_reg (a))])
    3033                 :            :         /* This allocno will be removed.  */
    3034                 :          0 :         continue;
    3035                 :            : 
    3036                 :            :       /* Caps will be removed.  */
    3037                 :          0 :       ira_assert (ALLOCNO_CAP_MEMBER (a) == NULL);
    3038                 :          0 :       for (parent = ALLOCNO_LOOP_TREE_NODE (a)->parent;
    3039                 :          0 :            parent != NULL;
    3040                 :          0 :            parent = parent->parent)
    3041                 :          0 :         if ((parent_a = parent->regno_allocno_map[regno]) == NULL
    3042                 :          0 :             || (parent_a
    3043                 :          0 :                 == regno_top_level_allocno_map[REGNO
    3044                 :          0 :                                                (allocno_emit_reg (parent_a))]
    3045                 :          0 :                 && ALLOCNO_EMIT_DATA (parent_a)->mem_optimized_dest_p))
    3046                 :            :           break;
    3047                 :          0 :       if (parent == NULL || parent_a == NULL)
    3048                 :          0 :         continue;
    3049                 :            : 
    3050                 :          0 :       copy_allocno_live_ranges (a, parent_a);
    3051                 :          0 :       merge_hard_reg_conflicts (a, parent_a, true);
    3052                 :            : 
    3053                 :          0 :       ALLOCNO_CALL_FREQ (parent_a) += ALLOCNO_CALL_FREQ (a);
    3054                 :          0 :       ALLOCNO_CALLS_CROSSED_NUM (parent_a)
    3055                 :          0 :         += ALLOCNO_CALLS_CROSSED_NUM (a);
    3056                 :          0 :       ALLOCNO_CHEAP_CALLS_CROSSED_NUM (parent_a)
    3057                 :          0 :         += ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a);
    3058                 :          0 :       ALLOCNO_CROSSED_CALLS_ABIS (parent_a)
    3059                 :          0 :         |= ALLOCNO_CROSSED_CALLS_ABIS (a);
    3060                 :          0 :       ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS (parent_a)
    3061                 :          0 :         |= ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS (a);
    3062                 :          0 :       ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (parent_a)
    3063                 :          0 :         += ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a);
    3064                 :          0 :       merged_p = true;
    3065                 :            :     }
    3066                 :          0 :   return merged_p;
    3067                 :            : }
    3068                 :            : 
    3069                 :            : /* Flatten the IR.  In other words, this function transforms IR as if
    3070                 :            :    it were built with one region (without loops).  We could make it
    3071                 :            :    much simpler by rebuilding IR with one region, but unfortunately it
    3072                 :            :    takes a lot of time.  MAX_REGNO_BEFORE_EMIT and
    3073                 :            :    IRA_MAX_POINT_BEFORE_EMIT are correspondingly MAX_REG_NUM () and
    3074                 :            :    IRA_MAX_POINT before emitting insns on the loop borders.  */
    3075                 :            : void
    3076                 :          0 : ira_flattening (int max_regno_before_emit, int ira_max_point_before_emit)
    3077                 :            : {
    3078                 :          0 :   int i, j;
    3079                 :          0 :   bool keep_p;
    3080                 :          0 :   int hard_regs_num;
    3081                 :          0 :   bool new_pseudos_p, merged_p, mem_dest_p;
    3082                 :          0 :   unsigned int n;
    3083                 :          0 :   enum reg_class aclass;
    3084                 :          0 :   ira_allocno_t a, parent_a, first, second, node_first, node_second;
    3085                 :          0 :   ira_copy_t cp;
    3086                 :          0 :   ira_loop_tree_node_t node;
    3087                 :          0 :   live_range_t r;
    3088                 :          0 :   ira_allocno_iterator ai;
    3089                 :          0 :   ira_copy_iterator ci;
    3090                 :            : 
    3091                 :          0 :   regno_top_level_allocno_map
    3092                 :          0 :     = (ira_allocno_t *) ira_allocate (max_reg_num ()
    3093                 :            :                                       * sizeof (ira_allocno_t));
    3094                 :          0 :   memset (regno_top_level_allocno_map, 0,
    3095                 :          0 :           max_reg_num () * sizeof (ira_allocno_t));
    3096                 :          0 :   new_pseudos_p = merged_p = false;
    3097                 :          0 :   FOR_EACH_ALLOCNO (a, ai)
    3098                 :            :     {
    3099                 :          0 :       ira_allocno_object_iterator oi;
    3100                 :          0 :       ira_object_t obj;
    3101                 :            : 
    3102                 :          0 :       if (ALLOCNO_CAP_MEMBER (a) != NULL)
    3103                 :            :         /* Caps are not in the regno allocno maps and they are never
    3104                 :            :            will be transformed into allocnos existing after IR
    3105                 :            :            flattening.  */
    3106                 :          0 :         continue;
    3107                 :          0 :       FOR_EACH_ALLOCNO_OBJECT (a, obj, oi)
    3108                 :          0 :         OBJECT_TOTAL_CONFLICT_HARD_REGS (obj)
    3109                 :          0 :           = OBJECT_CONFLICT_HARD_REGS (obj);
    3110                 :            : #ifdef STACK_REGS
    3111                 :          0 :       ALLOCNO_TOTAL_NO_STACK_REG_P (a) = ALLOCNO_NO_STACK_REG_P (a);
    3112                 :            : #endif
    3113                 :            :     }
    3114                 :            :   /* Fix final allocno attributes.  */
    3115                 :          0 :   for (i = max_regno_before_emit - 1; i >= FIRST_PSEUDO_REGISTER; i--)
    3116                 :            :     {
    3117                 :          0 :       mem_dest_p = false;
    3118                 :          0 :       for (a = ira_regno_allocno_map[i];
    3119                 :          0 :            a != NULL;
    3120                 :          0 :            a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
    3121                 :            :         {
    3122                 :          0 :           ira_emit_data_t parent_data, data = ALLOCNO_EMIT_DATA (a);
    3123                 :            : 
    3124                 :          0 :           ira_assert (ALLOCNO_CAP_MEMBER (a) == NULL);
    3125                 :          0 :           if (data->somewhere_renamed_p)
    3126                 :          0 :             new_pseudos_p = true;
    3127                 :          0 :           parent_a = ira_parent_allocno (a);
    3128                 :          0 :           if (parent_a == NULL)
    3129                 :            :             {
    3130                 :          0 :               ALLOCNO_COPIES (a) = NULL;
    3131                 :          0 :               regno_top_level_allocno_map[REGNO (data->reg)] = a;
    3132                 :          0 :               continue;
    3133                 :            :             }
    3134                 :          0 :           ira_assert (ALLOCNO_CAP_MEMBER (parent_a) == NULL);
    3135                 :            : 
    3136                 :          0 :           if (data->mem_optimized_dest != NULL)
    3137                 :          0 :             mem_dest_p = true;
    3138                 :          0 :           parent_data = ALLOCNO_EMIT_DATA (parent_a);
    3139                 :          0 :           if (REGNO (data->reg) == REGNO (parent_data->reg))
    3140                 :            :             {
    3141                 :          0 :               merge_hard_reg_conflicts (a, parent_a, true);
    3142                 :          0 :               move_allocno_live_ranges (a, parent_a);
    3143                 :          0 :               merged_p = true;
    3144                 :          0 :               parent_data->mem_optimized_dest_p
    3145                 :          0 :                 = (parent_data->mem_optimized_dest_p
    3146                 :          0 :                    || data->mem_optimized_dest_p);
    3147                 :          0 :               continue;
    3148                 :            :             }
    3149                 :          0 :           new_pseudos_p = true;
    3150                 :          0 :           for (;;)
    3151                 :            :             {
    3152                 :          0 :               ALLOCNO_NREFS (parent_a) -= ALLOCNO_NREFS (a);
    3153                 :          0 :               ALLOCNO_FREQ (parent_a) -= ALLOCNO_FREQ (a);
    3154                 :          0 :               ALLOCNO_CALL_FREQ (parent_a) -= ALLOCNO_CALL_FREQ (a);
    3155                 :          0 :               ALLOCNO_CALLS_CROSSED_NUM (parent_a)
    3156                 :          0 :                 -= ALLOCNO_CALLS_CROSSED_NUM (a);
    3157                 :          0 :               ALLOCNO_CHEAP_CALLS_CROSSED_NUM (parent_a)
    3158                 :          0 :                 -= ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a);
    3159                 :            :               /* Assume that ALLOCNO_CROSSED_CALLS_ABIS and
    3160                 :            :                  ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS stay the same.
    3161                 :            :                  We'd need to rebuild the IR to do better.  */
    3162                 :          0 :               ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (parent_a)
    3163                 :          0 :                 -= ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a);
    3164                 :          0 :               ira_assert (ALLOCNO_CALLS_CROSSED_NUM (parent_a) >= 0
    3165                 :            :                           && ALLOCNO_NREFS (parent_a) >= 0
    3166                 :            :                           && ALLOCNO_FREQ (parent_a) >= 0);
    3167                 :          0 :               aclass = ALLOCNO_CLASS (parent_a);
    3168                 :          0 :               hard_regs_num = ira_class_hard_regs_num[aclass];
    3169                 :          0 :               if (ALLOCNO_HARD_REG_COSTS (a) != NULL
    3170                 :          0 :                   && ALLOCNO_HARD_REG_COSTS (parent_a) != NULL)
    3171                 :          0 :                 for (j = 0; j < hard_regs_num; j++)
    3172                 :          0 :                   ALLOCNO_HARD_REG_COSTS (parent_a)[j]
    3173                 :          0 :                     -= ALLOCNO_HARD_REG_COSTS (a)[j];
    3174                 :          0 :               if (ALLOCNO_CONFLICT_HARD_REG_COSTS (a) != NULL
    3175                 :          0 :                   && ALLOCNO_CONFLICT_HARD_REG_COSTS (parent_a) != NULL)
    3176                 :          0 :                 for (j = 0; j < hard_regs_num; j++)
    3177                 :          0 :                   ALLOCNO_CONFLICT_HARD_REG_COSTS (parent_a)[j]
    3178                 :          0 :                     -= ALLOCNO_CONFLICT_HARD_REG_COSTS (a)[j];
    3179                 :          0 :               ALLOCNO_CLASS_COST (parent_a)
    3180                 :          0 :                 -= ALLOCNO_CLASS_COST (a);
    3181                 :          0 :               ALLOCNO_MEMORY_COST (parent_a) -= ALLOCNO_MEMORY_COST (a);
    3182                 :          0 :               parent_a = ira_parent_allocno (parent_a);
    3183                 :          0 :               if (parent_a == NULL)
    3184                 :            :                 break;
    3185                 :            :             }
    3186                 :          0 :           ALLOCNO_COPIES (a) = NULL;
    3187                 :          0 :           regno_top_level_allocno_map[REGNO (data->reg)] = a;
    3188                 :            :         }
    3189                 :          0 :       if (mem_dest_p && copy_info_to_removed_store_destinations (i))
    3190                 :            :         merged_p = true;
    3191                 :            :     }
    3192                 :          0 :   ira_assert (new_pseudos_p || ira_max_point_before_emit == ira_max_point);
    3193                 :          0 :   if (merged_p || ira_max_point_before_emit != ira_max_point)
    3194                 :          0 :     ira_rebuild_start_finish_chains ();
    3195                 :          0 :   if (new_pseudos_p)
    3196                 :            :     {
    3197                 :            :       sparseset objects_live;
    3198                 :            : 
    3199                 :            :       /* Rebuild conflicts.  */
    3200                 :          0 :       FOR_EACH_ALLOCNO (a, ai)
    3201                 :            :         {
    3202                 :          0 :           ira_allocno_object_iterator oi;
    3203                 :          0 :           ira_object_t obj;
    3204                 :            : 
    3205                 :          0 :           if (a != regno_top_level_allocno_map[REGNO (allocno_emit_reg (a))]
    3206                 :          0 :               || ALLOCNO_CAP_MEMBER (a) != NULL)
    3207                 :          0 :             continue;
    3208                 :          0 :           FOR_EACH_ALLOCNO_OBJECT (a, obj, oi)
    3209                 :            :             {
    3210                 :          0 :               for (r = OBJECT_LIVE_RANGES (obj); r != NULL; r = r->next)
    3211                 :          0 :                 ira_assert (r->object == obj);
    3212                 :          0 :               clear_conflicts (obj);
    3213                 :            :             }
    3214                 :            :         }
    3215                 :          0 :       objects_live = sparseset_alloc (ira_objects_num);
    3216                 :          0 :       for (i = 0; i < ira_max_point; i++)
    3217                 :            :         {
    3218                 :          0 :           for (r = ira_start_point_ranges[i]; r != NULL; r = r->start_next)
    3219                 :            :             {
    3220                 :          0 :               ira_object_t obj = r->object;
    3221                 :            : 
    3222                 :          0 :               a = OBJECT_ALLOCNO (obj);
    3223                 :          0 :               if (a != regno_top_level_allocno_map[REGNO (allocno_emit_reg (a))]
    3224                 :          0 :                   || ALLOCNO_CAP_MEMBER (a) != NULL)
    3225                 :          0 :                 continue;
    3226                 :            : 
    3227                 :          0 :               aclass = ALLOCNO_CLASS (a);
    3228                 :          0 :               EXECUTE_IF_SET_IN_SPARSESET (objects_live, n)
    3229                 :            :                 {
    3230                 :          0 :                   ira_object_t live_obj = ira_object_id_map[n];
    3231                 :          0 :                   ira_allocno_t live_a = OBJECT_ALLOCNO (live_obj);
    3232                 :          0 :                   enum reg_class live_aclass = ALLOCNO_CLASS (live_a);
    3233                 :            : 
    3234                 :          0 :                   if (ira_reg_classes_intersect_p[aclass][live_aclass]
    3235                 :            :                       /* Don't set up conflict for the allocno with itself.  */
    3236                 :          0 :                       && live_a != a)
    3237                 :          0 :                     ira_add_conflict (obj, live_obj);
    3238                 :            :                 }
    3239                 :          0 :               sparseset_set_bit (objects_live, OBJECT_CONFLICT_ID (obj));
    3240                 :            :             }
    3241                 :            : 
    3242                 :          0 :           for (r = ira_finish_point_ranges[i]; r != NULL; r = r->finish_next)
    3243                 :          0 :             sparseset_clear_bit (objects_live, OBJECT_CONFLICT_ID (r->object));
    3244                 :            :         }
    3245                 :          0 :       sparseset_free (objects_live);
    3246                 :          0 :       compress_conflict_vecs ();
    3247                 :            :     }
    3248                 :            :   /* Mark some copies for removing and change allocnos in the rest
    3249                 :            :      copies.  */
    3250                 :          0 :   FOR_EACH_COPY (cp, ci)
    3251                 :            :     {
    3252                 :          0 :       if (ALLOCNO_CAP_MEMBER (cp->first) != NULL
    3253                 :          0 :           || ALLOCNO_CAP_MEMBER (cp->second) != NULL)
    3254                 :            :         {
    3255                 :          0 :           if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL)
    3256                 :          0 :             fprintf
    3257                 :          0 :               (ira_dump_file, "      Remove cp%d:%c%dr%d-%c%dr%d\n",
    3258                 :            :                cp->num, ALLOCNO_CAP_MEMBER (cp->first) != NULL ? 'c' : 'a',
    3259                 :            :                ALLOCNO_NUM (cp->first),
    3260                 :          0 :                REGNO (allocno_emit_reg (cp->first)),
    3261                 :          0 :                ALLOCNO_CAP_MEMBER (cp->second) != NULL ? 'c' : 'a',
    3262                 :            :                ALLOCNO_NUM (cp->second),
    3263                 :          0 :                REGNO (allocno_emit_reg (cp->second)));
    3264                 :          0 :           cp->loop_tree_node = NULL;
    3265                 :          0 :           continue;
    3266                 :            :         }
    3267                 :          0 :       first
    3268                 :          0 :         = regno_top_level_allocno_map[REGNO (allocno_emit_reg (cp->first))];
    3269                 :          0 :       second
    3270                 :          0 :         = regno_top_level_allocno_map[REGNO (allocno_emit_reg (cp->second))];
    3271                 :          0 :       node = cp->loop_tree_node;
    3272                 :          0 :       if (node == NULL)
    3273                 :            :         keep_p = true; /* It copy generated in ira-emit.c.  */
    3274                 :            :       else
    3275                 :            :         {
    3276                 :            :           /* Check that the copy was not propagated from level on
    3277                 :            :              which we will have different pseudos.  */
    3278                 :          0 :           node_first = node->regno_allocno_map[ALLOCNO_REGNO (cp->first)];
    3279                 :          0 :           node_second = node->regno_allocno_map[ALLOCNO_REGNO (cp->second)];
    3280                 :          0 :           keep_p = ((REGNO (allocno_emit_reg (first))
    3281                 :          0 :                      == REGNO (allocno_emit_reg (node_first)))
    3282                 :          0 :                      && (REGNO (allocno_emit_reg (second))
    3283                 :          0 :                          == REGNO (allocno_emit_reg (node_second))));
    3284                 :            :         }
    3285                 :          0 :       if (keep_p)
    3286                 :            :         {
    3287                 :          0 :           cp->loop_tree_node = ira_loop_tree_root;
    3288                 :          0 :           cp->first = first;
    3289                 :          0 :           cp->second = second;
    3290                 :            :         }
    3291                 :            :       else
    3292                 :            :         {
    3293                 :          0 :           cp->loop_tree_node = NULL;
    3294                 :          0 :           if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL)
    3295                 :          0 :             fprintf (ira_dump_file, "      Remove cp%d:a%dr%d-a%dr%d\n",
    3296                 :            :                      cp->num, ALLOCNO_NUM (cp->first),
    3297                 :          0 :                      REGNO (allocno_emit_reg (cp->first)),
    3298                 :            :                      ALLOCNO_NUM (cp->second),
    3299                 :          0 :                      REGNO (allocno_emit_reg (cp->second)));
    3300                 :            :         }
    3301                 :            :     }
    3302                 :            :   /* Remove unnecessary allocnos on lower levels of the loop tree.  */
    3303                 :          0 :   FOR_EACH_ALLOCNO (a, ai)
    3304                 :            :     {
    3305                 :          0 :       if (a != regno_top_level_allocno_map[REGNO (allocno_emit_reg (a))]
    3306                 :          0 :           || ALLOCNO_CAP_MEMBER (a) != NULL)
    3307                 :            :         {
    3308                 :          0 :           if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL)
    3309                 :          0 :             fprintf (ira_dump_file, "      Remove a%dr%d\n",
    3310                 :          0 :                      ALLOCNO_NUM (a), REGNO (allocno_emit_reg (a)));
    3311                 :          0 :           ira_remove_allocno_prefs (a);
    3312                 :          0 :           finish_allocno (a);
    3313                 :          0 :           continue;
    3314                 :            :         }
    3315                 :          0 :       ALLOCNO_LOOP_TREE_NODE (a) = ira_loop_tree_root;
    3316                 :          0 :       ALLOCNO_REGNO (a) = REGNO (allocno_emit_reg (a));
    3317                 :          0 :       ALLOCNO_CAP (a) = NULL;
    3318                 :            :       /* Restore updated costs for assignments from reload.  */
    3319                 :          0 :       ALLOCNO_UPDATED_MEMORY_COST (a) = ALLOCNO_MEMORY_COST (a);
    3320                 :          0 :       ALLOCNO_UPDATED_CLASS_COST (a) = ALLOCNO_CLASS_COST (a);
    3321                 :          0 :       if (! ALLOCNO_ASSIGNED_P (a))
    3322                 :          0 :         ira_free_allocno_updated_costs (a);
    3323                 :          0 :       ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL);
    3324                 :          0 :       ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) == NULL);
    3325                 :            :     }
    3326                 :            :   /* Remove unnecessary copies.  */
    3327                 :          0 :   FOR_EACH_COPY (cp, ci)
    3328                 :            :     {
    3329                 :          0 :       if (cp->loop_tree_node == NULL)
    3330                 :            :         {
    3331                 :          0 :           ira_copies[cp->num] = NULL;
    3332                 :          0 :           finish_copy (cp);
    3333                 :          0 :           continue;
    3334                 :            :         }
    3335                 :          0 :       ira_assert
    3336                 :            :         (ALLOCNO_LOOP_TREE_NODE (cp->first) == ira_loop_tree_root
    3337                 :            :          && ALLOCNO_LOOP_TREE_NODE (cp->second) == ira_loop_tree_root);
    3338                 :          0 :       add_allocno_copy_to_list (cp);
    3339                 :          0 :       swap_allocno_copy_ends_if_necessary (cp);
    3340                 :            :     }
    3341                 :          0 :   rebuild_regno_allocno_maps ();
    3342                 :          0 :   if (ira_max_point != ira_max_point_before_emit)
    3343                 :          0 :     ira_compress_allocno_live_ranges ();
    3344                 :          0 :   ira_free (regno_top_level_allocno_map);
    3345                 :          0 : }
    3346                 :            : 
    3347                 :            : 
    3348                 :            : 
    3349                 :            : #ifdef ENABLE_IRA_CHECKING
    3350                 :            : /* Check creation of all allocnos.  Allocnos on lower levels should
    3351                 :            :    have allocnos or caps on all upper levels.  */
    3352                 :            : static void
    3353                 :     944096 : check_allocno_creation (void)
    3354                 :            : {
    3355                 :     944096 :   ira_allocno_t a;
    3356                 :     944096 :   ira_allocno_iterator ai;
    3357                 :     944096 :   ira_loop_tree_node_t loop_tree_node;
    3358                 :            : 
    3359                 :   23853700 :   FOR_EACH_ALLOCNO (a, ai)
    3360                 :            :     {
    3361                 :   22909600 :       loop_tree_node = ALLOCNO_LOOP_TREE_NODE (a);
    3362                 :   22909600 :       ira_assert (bitmap_bit_p (loop_tree_node->all_allocnos,
    3363                 :            :                                 ALLOCNO_NUM (a)));
    3364                 :   22909600 :       if (loop_tree_node == ira_loop_tree_root)
    3365                 :   17961700 :         continue;
    3366                 :    4947900 :       if (ALLOCNO_CAP_MEMBER (a) != NULL)
    3367                 :    1487630 :         ira_assert (ALLOCNO_CAP (a) != NULL);
    3368                 :    3460270 :       else if (ALLOCNO_CAP (a) == NULL)
    3369                 :    2146940 :         ira_assert (loop_tree_node->parent
    3370                 :            :                     ->regno_allocno_map[ALLOCNO_REGNO (a)] != NULL
    3371                 :            :                     && bitmap_bit_p (loop_tree_node->border_allocnos,
    3372                 :            :                                      ALLOCNO_NUM (a)));
    3373                 :            :     }
    3374                 :     944096 : }
    3375                 :            : #endif
    3376                 :            : 
    3377                 :            : /* Identify allocnos which prefer a register class with a single hard register.
    3378                 :            :    Adjust ALLOCNO_CONFLICT_HARD_REG_COSTS so that conflicting allocnos are
    3379                 :            :    less likely to use the preferred singleton register.  */
    3380                 :            : static void
    3381                 :     944096 : update_conflict_hard_reg_costs (void)
    3382                 :            : {
    3383                 :     944096 :   ira_allocno_t a;
    3384                 :     944096 :   ira_allocno_iterator ai;
    3385                 :     944096 :   int i, index, min;
    3386                 :            : 
    3387                 :   23853700 :   FOR_EACH_ALLOCNO (a, ai)
    3388                 :            :     {
    3389                 :   22909600 :       reg_class_t aclass = ALLOCNO_CLASS (a);
    3390                 :   22909600 :       reg_class_t pref = reg_preferred_class (ALLOCNO_REGNO (a));
    3391                 :   22909600 :       int singleton = ira_class_singleton[pref][ALLOCNO_MODE (a)];
    3392                 :   22909600 :       if (singleton < 0)
    3393                 :   17823700 :         continue;
    3394                 :    5085910 :       index = ira_class_hard_reg_index[(int) aclass][singleton];
    3395                 :    5085910 :       if (index < 0)
    3396                 :          0 :         continue;
    3397                 :    5085910 :       if (ALLOCNO_CONFLICT_HARD_REG_COSTS (a) == NULL
    3398                 :     644124 :           || ALLOCNO_HARD_REG_COSTS (a) == NULL)
    3399                 :    4542050 :         continue;
    3400                 :     543858 :       min = INT_MAX;
    3401                 :    8490750 :       for (i = ira_class_hard_regs_num[(int) aclass] - 1; i >= 0; i--)
    3402                 :    7946890 :         if (ALLOCNO_HARD_REG_COSTS (a)[i] > ALLOCNO_CLASS_COST (a)
    3403                 :            :             && min > ALLOCNO_HARD_REG_COSTS (a)[i])
    3404                 :            :           min = ALLOCNO_HARD_REG_COSTS (a)[i];
    3405                 :     543858 :       if (min == INT_MAX)
    3406                 :       6250 :         continue;
    3407                 :     537608 :       ira_allocate_and_set_costs (&ALLOCNO_CONFLICT_HARD_REG_COSTS (a),
    3408                 :            :                                   aclass, 0);
    3409                 :     537608 :       ALLOCNO_CONFLICT_HARD_REG_COSTS (a)[index]
    3410                 :     537608 :         -= min - ALLOCNO_CLASS_COST (a);
    3411                 :            :     }
    3412                 :     944096 : }
    3413                 :            : 
    3414                 :            : /* Create a internal representation (IR) for IRA (allocnos, copies,
    3415                 :            :    loop tree nodes).  The function returns TRUE if we generate loop
    3416                 :            :    structure (besides nodes representing all function and the basic
    3417                 :            :    blocks) for regional allocation.  A true return means that we
    3418                 :            :    really need to flatten IR before the reload.  */
    3419                 :            : bool
    3420                 :     944096 : ira_build (void)
    3421                 :            : {
    3422                 :     944096 :   bool loops_p;
    3423                 :            : 
    3424                 :     944096 :   df_analyze ();
    3425                 :     944096 :   initiate_cost_vectors ();
    3426                 :     944096 :   initiate_allocnos ();
    3427                 :     944096 :   initiate_prefs ();
    3428                 :     944096 :   initiate_copies ();
    3429                 :     944096 :   create_loop_tree_nodes ();
    3430                 :     944096 :   form_loop_tree ();
    3431                 :     944096 :   create_allocnos ();
    3432                 :     944096 :   ira_costs ();
    3433                 :     944096 :   create_allocno_objects ();
    3434                 :     944096 :   ira_create_allocno_live_ranges ();
    3435                 :     944096 :   remove_unnecessary_regions (false);
    3436                 :     944096 :   ira_compress_allocno_live_ranges ();
    3437                 :     944096 :   update_bad_spill_attribute ();
    3438                 :     944096 :   loops_p = more_one_region_p ();
    3439                 :     944096 :   if (loops_p)
    3440                 :            :     {
    3441                 :      25420 :       propagate_allocno_info ();
    3442                 :      25420 :       create_caps ();
    3443                 :            :     }
    3444                 :     944096 :   ira_tune_allocno_costs ();
    3445                 :            : #ifdef ENABLE_IRA_CHECKING
    3446                 :     944096 :   check_allocno_creation ();
    3447                 :            : #endif
    3448                 :     944096 :   setup_min_max_allocno_live_range_point ();
    3449                 :     944096 :   sort_conflict_id_map ();
    3450                 :     944096 :   setup_min_max_conflict_allocno_ids ();
    3451                 :     944096 :   ira_build_conflicts ();
    3452                 :     944096 :   update_conflict_hard_reg_costs ();
    3453                 :     944096 :   if (! ira_conflicts_p)
    3454                 :            :     {
    3455                 :     255548 :       ira_allocno_t a;
    3456                 :     255548 :       ira_allocno_iterator ai;
    3457                 :            : 
    3458                 :            :       /* Remove all regions but root one.  */
    3459                 :     255548 :       if (loops_p)
    3460                 :            :         {
    3461                 :          0 :           remove_unnecessary_regions (true);
    3462                 :          0 :           loops_p = false;
    3463                 :            :         }
    3464                 :            :       /* We don't save hard registers around calls for fast allocation
    3465                 :            :          -- add caller clobbered registers as conflicting ones to
    3466                 :            :          allocno crossing calls.  */
    3467                 :    6210730 :       FOR_EACH_ALLOCNO (a, ai)
    3468                 :    5955180 :         if (ALLOCNO_CALLS_CROSSED_NUM (a) != 0)
    3469                 :     116661 :           ior_hard_reg_conflicts (a, ira_need_caller_save_regs (a));
    3470                 :            :     }
    3471                 :     944096 :   if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
    3472                 :        102 :     print_copies (ira_dump_file);
    3473                 :     944096 :   if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
    3474                 :        102 :     print_prefs (ira_dump_file);
    3475                 :     944096 :   if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
    3476                 :            :     {
    3477                 :            :       int n, nr, nr_big;
    3478                 :            :       ira_allocno_t a;
    3479                 :            :       live_range_t r;
    3480                 :            :       ira_allocno_iterator ai;
    3481                 :            : 
    3482                 :            :       n = 0;
    3483                 :            :       nr = 0;
    3484                 :            :       nr_big = 0;
    3485                 :        792 :       FOR_EACH_ALLOCNO (a, ai)
    3486                 :            :         {
    3487                 :        690 :           int j, nobj = ALLOCNO_NUM_OBJECTS (a);
    3488                 :            : 
    3489                 :        690 :           if (nobj > 1)
    3490                 :          0 :             nr_big++;
    3491                 :       1380 :           for (j = 0; j < nobj; j++)
    3492                 :            :             {
    3493                 :        690 :               ira_object_t obj = ALLOCNO_OBJECT (a, j);
    3494                 :        690 :               n += OBJECT_NUM_CONFLICTS (obj);
    3495                 :       1549 :               for (r = OBJECT_LIVE_RANGES (obj); r != NULL; r = r->next)
    3496                 :        859 :                 nr++;
    3497                 :            :             }
    3498                 :            :         }
    3499                 :        204 :       fprintf (ira_dump_file, "  regions=%d, blocks=%d, points=%d\n",
    3500                 :        137 :                current_loops == NULL ? 1 : number_of_loops (cfun),
    3501                 :        102 :                n_basic_blocks_for_fn (cfun), ira_max_point);
    3502                 :        102 :       fprintf (ira_dump_file,
    3503                 :            :                "    allocnos=%d (big %d), copies=%d, conflicts=%d, ranges=%d\n",
    3504                 :            :                ira_allocnos_num, nr_big, ira_copies_num, n, nr);
    3505                 :            :     }
    3506                 :     944096 :   return loops_p;
    3507                 :            : }
    3508                 :            : 
    3509                 :            : /* Release the data created by function ira_build.  */
    3510                 :            : void
    3511                 :     944096 : ira_destroy (void)
    3512                 :            : {
    3513                 :     944096 :   finish_loop_tree_nodes ();
    3514                 :     944096 :   finish_prefs ();
    3515                 :     944096 :   finish_copies ();
    3516                 :     944096 :   finish_allocnos ();
    3517                 :     944096 :   finish_cost_vectors ();
    3518                 :     944096 :   ira_finish_allocno_live_ranges ();
    3519                 :     944096 : }

Generated by: LCOV version 1.0

LCOV profile is generated on x86_64 machine using following configure options: configure --disable-bootstrap --enable-coverage=opt --enable-languages=c,c++,fortran,go,jit,lto --enable-host-shared. GCC test suite is run with the built compiler.