LCOV - code coverage report
Current view: top level - gcc/rtl-ssa - accesses.cc (source / functions) Hit Total Coverage
Test: gcc.info Lines: 459 784 58.5 %
Date: 2021-11-27 14:51:55 Functions: 34 72 47.2 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 0 0 -

           Branch data     Line data    Source code
       1                 :            : // Implementation of access-related functions for RTL SSA           -*- C++ -*-
       2                 :            : // Copyright (C) 2020-2021 Free Software Foundation, Inc.
       3                 :            : //
       4                 :            : // This file is part of GCC.
       5                 :            : //
       6                 :            : // GCC is free software; you can redistribute it and/or modify it under
       7                 :            : // the terms of the GNU General Public License as published by the Free
       8                 :            : // Software Foundation; either version 3, or (at your option) any later
       9                 :            : // version.
      10                 :            : //
      11                 :            : // GCC is distributed in the hope that it will be useful, but WITHOUT ANY
      12                 :            : // WARRANTY; without even the implied warranty of MERCHANTABILITY or
      13                 :            : // FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
      14                 :            : // for more details.
      15                 :            : //
      16                 :            : // You should have received a copy of the GNU General Public License
      17                 :            : // along with GCC; see the file COPYING3.  If not see
      18                 :            : // <http://www.gnu.org/licenses/>.
      19                 :            : 
      20                 :            : #define INCLUDE_ALGORITHM
      21                 :            : #define INCLUDE_FUNCTIONAL
      22                 :            : #include "config.h"
      23                 :            : #include "system.h"
      24                 :            : #include "coretypes.h"
      25                 :            : #include "backend.h"
      26                 :            : #include "rtl.h"
      27                 :            : #include "df.h"
      28                 :            : #include "rtl-ssa.h"
      29                 :            : #include "rtl-ssa/internals.h"
      30                 :            : #include "rtl-ssa/internals.inl"
      31                 :            : 
      32                 :            : using namespace rtl_ssa;
      33                 :            : 
      34                 :            : // This clobber belongs to a clobber_group but m_group appears to be
      35                 :            : // out of date.  Update it and return the new (correct) value.
      36                 :            : clobber_group *
      37                 :          0 : clobber_info::recompute_group ()
      38                 :            : {
      39                 :          0 :   using splay_tree = clobber_info::splay_tree;
      40                 :            : 
      41                 :            :   // Splay this clobber to the root of the tree while searching for a node
      42                 :            :   // that has the correct group.  The root always has the correct group,
      43                 :            :   // so the search always breaks early and does not install this clobber
      44                 :            :   // as the root.
      45                 :          0 :   clobber_info *cursor = m_parent;
      46                 :          0 :   auto find_group = [](clobber_info *node, unsigned int)
      47                 :            :     {
      48                 :          0 :       return node->m_group->has_been_superceded () ? nullptr : node->m_group;
      49                 :            :     };
      50                 :          0 :   clobber_group *group = splay_tree::splay_and_search (this, nullptr,
      51                 :            :                                                        find_group);
      52                 :          0 :   gcc_checking_assert (m_parent);
      53                 :            : 
      54                 :            :   // If the previous splay operation did anything, this clobber is now an
      55                 :            :   // ancestor of CURSOR, and all the nodes inbetween have a stale group.
      56                 :            :   // Since we have visited the nodes, we might as well update them too.
      57                 :            :   //
      58                 :            :   // If the previous splay operation did nothing, start the update from
      59                 :            :   // this clobber instead.  In that case we change at most two clobbers:
      60                 :            :   // this clobber and possibly its parent.
      61                 :          0 :   if (cursor == m_parent)
      62                 :          0 :     cursor = this;
      63                 :            : 
      64                 :            :   // Walk up the tree from CURSOR updating clobbers that need it.
      65                 :            :   // This walk always includes this clobber.
      66                 :          0 :   while (cursor->m_group != group)
      67                 :            :     {
      68                 :          0 :       cursor->m_group = group;
      69                 :          0 :       cursor = cursor->m_parent;
      70                 :            :     }
      71                 :            : 
      72                 :          0 :   gcc_checking_assert (m_group == group);
      73                 :          0 :   return group;
      74                 :            : }
      75                 :            : 
      76                 :            : // See the comment above the declaration.
      77                 :            : void
      78                 :          0 : resource_info::print_identifier (pretty_printer *pp) const
      79                 :            : {
      80                 :          0 :   if (is_mem ())
      81                 :          0 :     pp_string (pp, "mem");
      82                 :            :   else
      83                 :            :     {
      84                 :          0 :       char tmp[3 * sizeof (regno) + 2];
      85                 :          0 :       snprintf (tmp, sizeof (tmp), "r%d", regno);
      86                 :          0 :       pp_string (pp, tmp);
      87                 :            :     }
      88                 :          0 : }
      89                 :            : 
      90                 :            : // See the comment above the declaration.
      91                 :            : void
      92                 :          0 : resource_info::print_context (pretty_printer *pp) const
      93                 :            : {
      94                 :          0 :   if (HARD_REGISTER_NUM_P (regno))
      95                 :            :     {
      96                 :          0 :       if (const char *name = reg_names[regno])
      97                 :            :         {
      98                 :          0 :           pp_space (pp);
      99                 :          0 :           pp_left_paren (pp);
     100                 :          0 :           pp_string (pp, name);
     101                 :          0 :           if (mode != E_BLKmode)
     102                 :            :             {
     103                 :          0 :               pp_colon (pp);
     104                 :          0 :               pp_string (pp, GET_MODE_NAME (mode));
     105                 :            :             }
     106                 :          0 :           pp_right_paren (pp);
     107                 :            :         }
     108                 :            :     }
     109                 :          0 :   else if (is_reg ())
     110                 :            :     {
     111                 :          0 :       pp_space (pp);
     112                 :          0 :       pp_left_paren (pp);
     113                 :          0 :       if (mode != E_BLKmode)
     114                 :            :         {
     115                 :          0 :           pp_string (pp, GET_MODE_NAME (mode));
     116                 :          0 :           pp_space (pp);
     117                 :            :         }
     118                 :          0 :       pp_string (pp, "pseudo");
     119                 :          0 :       pp_right_paren (pp);
     120                 :            :     }
     121                 :          0 : }
     122                 :            : 
     123                 :            : // See the comment above the declaration.
     124                 :            : void
     125                 :          0 : resource_info::print (pretty_printer *pp) const
     126                 :            : {
     127                 :          0 :   print_identifier (pp);
     128                 :          0 :   print_context (pp);
     129                 :          0 : }
     130                 :            : 
     131                 :            : // Some properties can naturally be described using adjectives that attach
     132                 :            : // to nouns like "use" or "definition".  Print such adjectives to PP.
     133                 :            : void
     134                 :          0 : access_info::print_prefix_flags (pretty_printer *pp) const
     135                 :            : {
     136                 :          0 :   if (m_is_temp)
     137                 :          0 :     pp_string (pp, "temporary ");
     138                 :          0 :   if (m_has_been_superceded)
     139                 :          0 :     pp_string (pp, "superceded ");
     140                 :          0 : }
     141                 :            : 
     142                 :            : // Print properties not handled by print_prefix_flags to PP, putting
     143                 :            : // each property on a new line indented by two extra spaces.
     144                 :            : void
     145                 :          0 : access_info::print_properties_on_new_lines (pretty_printer *pp) const
     146                 :            : {
     147                 :          0 :   if (m_is_pre_post_modify)
     148                 :            :     {
     149                 :          0 :       pp_newline_and_indent (pp, 2);
     150                 :          0 :       pp_string (pp, "set by a pre/post-modify");
     151                 :          0 :       pp_indentation (pp) -= 2;
     152                 :            :     }
     153                 :          0 :   if (m_includes_address_uses)
     154                 :            :     {
     155                 :          0 :       pp_newline_and_indent (pp, 2);
     156                 :          0 :       pp_string (pp, "appears inside an address");
     157                 :          0 :       pp_indentation (pp) -= 2;
     158                 :            :     }
     159                 :          0 :   if (m_includes_read_writes)
     160                 :            :     {
     161                 :          0 :       pp_newline_and_indent (pp, 2);
     162                 :          0 :       pp_string (pp, "appears in a read/write context");
     163                 :          0 :       pp_indentation (pp) -= 2;
     164                 :            :     }
     165                 :          0 :   if (m_includes_subregs)
     166                 :            :     {
     167                 :          0 :       pp_newline_and_indent (pp, 2);
     168                 :          0 :       pp_string (pp, "appears inside a subreg");
     169                 :          0 :       pp_indentation (pp) -= 2;
     170                 :            :     }
     171                 :          0 : }
     172                 :            : 
     173                 :            : // Return true if there are no known issues with the integrity of the
     174                 :            : // link information.
     175                 :            : inline bool
     176                 :  404353723 : use_info::check_integrity ()
     177                 :            : {
     178                 : 1230931155 :   auto subsequence_id = [](use_info *use)
     179                 :            :     {
     180                 :  413288716 :       if (use->is_in_nondebug_insn ())
     181                 :            :         return 1;
     182                 :  122302090 :       if (use->is_in_debug_insn ())
     183                 :   78435497 :         return 2;
     184                 :            :       return 3;
     185                 :            :     };
     186                 :            : 
     187                 :  404353723 :   use_info *prev = prev_use ();
     188                 :  404353723 :   use_info *next = next_use ();
     189                 :            : 
     190                 :  712187030 :   if (prev && subsequence_id (prev) > subsequence_id (this))
     191                 :            :     return false;
     192                 :  568483329 :   if (next && subsequence_id (next) < subsequence_id (this))
     193                 :            :     return false;
     194                 :  404353723 :   if (m_is_last_nondebug_insn_use != calculate_is_last_nondebug_insn_use ())
     195                 :            :     return false;
     196                 :            : 
     197                 :  404353723 :   if (!prev && last_use ()->next_use ())
     198                 :            :     return false;
     199                 :  404353723 :   if (!next)
     200                 :  250188588 :     if (use_info *use = last_nondebug_insn_use ())
     201                 :  229726054 :       if (!use->m_is_last_nondebug_insn_use)
     202                 :          0 :         return false;
     203                 :            : 
     204                 :            :   return true;
     205                 :            : }
     206                 :            : 
     207                 :            : // See the comment above the declaration.
     208                 :            : void
     209                 :          0 : use_info::print_location (pretty_printer *pp) const
     210                 :            : {
     211                 :          0 :   if (is_in_phi ())
     212                 :          0 :     pp_access (pp, phi (), PP_ACCESS_INCLUDE_LOCATION);
     213                 :            :   else
     214                 :          0 :     insn ()->print_identifier_and_location (pp);
     215                 :          0 : }
     216                 :            : 
     217                 :            : // See the comment above the declaration.
     218                 :            : void
     219                 :          0 : use_info::print_def (pretty_printer *pp) const
     220                 :            : {
     221                 :          0 :   if (const set_info *set = def ())
     222                 :          0 :     pp_access (pp, set, 0);
     223                 :            :   else
     224                 :            :     {
     225                 :          0 :       pp_string (pp, "undefined ");
     226                 :          0 :       resource ().print (pp);
     227                 :            :     }
     228                 :          0 : }
     229                 :            : 
     230                 :            : // See the comment above the declaration.
     231                 :            : void
     232                 :          0 : use_info::print (pretty_printer *pp, unsigned int flags) const
     233                 :            : {
     234                 :          0 :   print_prefix_flags (pp);
     235                 :            : 
     236                 :          0 :   const set_info *set = def ();
     237                 :          0 :   if (set && set->mode () != mode ())
     238                 :            :     {
     239                 :          0 :       pp_string (pp, GET_MODE_NAME (mode ()));
     240                 :          0 :       pp_space (pp);
     241                 :            :     }
     242                 :            : 
     243                 :          0 :   pp_string (pp, "use of ");
     244                 :          0 :   print_def (pp);
     245                 :          0 :   if (flags & PP_ACCESS_INCLUDE_LOCATION)
     246                 :            :     {
     247                 :          0 :       pp_string (pp, " by ");
     248                 :          0 :       print_location (pp);
     249                 :            :     }
     250                 :          0 :   if (set && (flags & PP_ACCESS_INCLUDE_LINKS))
     251                 :            :     {
     252                 :          0 :       pp_newline_and_indent (pp, 2);
     253                 :          0 :       pp_string (pp, "defined in ");
     254                 :          0 :       set->insn ()->print_location (pp);
     255                 :          0 :       pp_indentation (pp) -= 2;
     256                 :            :     }
     257                 :          0 :   if (flags & PP_ACCESS_INCLUDE_PROPERTIES)
     258                 :          0 :     print_properties_on_new_lines (pp);
     259                 :          0 : }
     260                 :            : 
     261                 :            : // See the comment above the declaration.
     262                 :            : void
     263                 :          0 : def_info::print_identifier (pretty_printer *pp) const
     264                 :            : {
     265                 :          0 :   resource ().print_identifier (pp);
     266                 :          0 :   pp_colon (pp);
     267                 :          0 :   insn ()->print_identifier (pp);
     268                 :          0 :   resource ().print_context (pp);
     269                 :          0 : }
     270                 :            : 
     271                 :            : // See the comment above the declaration.
     272                 :            : void
     273                 :          0 : def_info::print_location (pretty_printer *pp) const
     274                 :            : {
     275                 :          0 :   insn ()->print_identifier_and_location (pp);
     276                 :          0 : }
     277                 :            : 
     278                 :            : // See the comment above the declaration.
     279                 :            : void
     280                 :          0 : clobber_info::print (pretty_printer *pp, unsigned int flags) const
     281                 :            : {
     282                 :          0 :   print_prefix_flags (pp);
     283                 :          0 :   if (is_call_clobber ())
     284                 :          0 :     pp_string (pp, "call ");
     285                 :          0 :   pp_string (pp, "clobber ");
     286                 :          0 :   print_identifier (pp);
     287                 :          0 :   if (flags & PP_ACCESS_INCLUDE_LOCATION)
     288                 :            :     {
     289                 :          0 :       pp_string (pp, " in ");
     290                 :          0 :       insn ()->print_location (pp);
     291                 :            :     }
     292                 :          0 :   if (flags & PP_ACCESS_INCLUDE_PROPERTIES)
     293                 :          0 :     print_properties_on_new_lines (pp);
     294                 :          0 : }
     295                 :            : 
     296                 :            : // See the comment above the declaration.
     297                 :            : void
     298                 :          0 : set_info::print_uses_on_new_lines (pretty_printer *pp) const
     299                 :            : {
     300                 :          0 :   for (const use_info *use : all_uses ())
     301                 :            :     {
     302                 :          0 :       pp_newline_and_indent (pp, 2);
     303                 :          0 :       if (use->is_live_out_use ())
     304                 :            :         {
     305                 :          0 :           pp_string (pp, "live out from ");
     306                 :          0 :           use->insn ()->print_location (pp);
     307                 :            :         }
     308                 :            :       else
     309                 :            :         {
     310                 :          0 :           pp_string (pp, "used by ");
     311                 :          0 :           use->print_location (pp);
     312                 :            :         }
     313                 :          0 :       pp_indentation (pp) -= 2;
     314                 :            :     }
     315                 :          0 :   if (m_use_tree)
     316                 :            :     {
     317                 :          0 :       pp_newline_and_indent (pp, 2);
     318                 :          0 :       pp_string (pp, "splay tree:");
     319                 :          0 :       pp_newline_and_indent (pp, 2);
     320                 :          0 :       auto print_use = [](pretty_printer *pp,
     321                 :            :                           splay_tree_node<use_info *> *node)
     322                 :            :         {
     323                 :          0 :           pp_string (pp, "use by ");
     324                 :          0 :           node->value ()->print_location (pp);
     325                 :          0 :         };
     326                 :          0 :       m_use_tree.print (pp, m_use_tree.root (), print_use);
     327                 :          0 :       pp_indentation (pp) -= 4;
     328                 :            :     }
     329                 :          0 : }
     330                 :            : 
     331                 :            : // See the comment above the declaration.
     332                 :            : void
     333                 :          0 : set_info::print (pretty_printer *pp, unsigned int flags) const
     334                 :            : {
     335                 :          0 :   print_prefix_flags (pp);
     336                 :          0 :   pp_string (pp, "set ");
     337                 :          0 :   print_identifier (pp);
     338                 :          0 :   if (flags & PP_ACCESS_INCLUDE_LOCATION)
     339                 :            :     {
     340                 :          0 :       pp_string (pp, " in ");
     341                 :          0 :       insn ()->print_location (pp);
     342                 :            :     }
     343                 :          0 :   if (flags & PP_ACCESS_INCLUDE_PROPERTIES)
     344                 :          0 :     print_properties_on_new_lines (pp);
     345                 :          0 :   if (flags & PP_ACCESS_INCLUDE_LINKS)
     346                 :          0 :     print_uses_on_new_lines (pp);
     347                 :          0 : }
     348                 :            : 
     349                 :            : // See the comment above the declaration.
     350                 :            : void
     351                 :          0 : phi_info::print (pretty_printer *pp, unsigned int flags) const
     352                 :            : {
     353                 :          0 :   print_prefix_flags (pp);
     354                 :          0 :   pp_string (pp, "phi node ");
     355                 :          0 :   print_identifier (pp);
     356                 :          0 :   if (flags & PP_ACCESS_INCLUDE_LOCATION)
     357                 :            :     {
     358                 :          0 :       pp_string (pp, " in ");
     359                 :          0 :       insn ()->print_location (pp);
     360                 :            :     }
     361                 :            : 
     362                 :          0 :   if (flags & PP_ACCESS_INCLUDE_PROPERTIES)
     363                 :          0 :     print_properties_on_new_lines (pp);
     364                 :            : 
     365                 :          0 :   if (flags & PP_ACCESS_INCLUDE_LINKS)
     366                 :            :     {
     367                 :          0 :       basic_block cfg_bb = bb ()->cfg_bb ();
     368                 :          0 :       pp_newline_and_indent (pp, 2);
     369                 :          0 :       pp_string (pp, "inputs:");
     370                 :          0 :       unsigned int i = 0;
     371                 :          0 :       for (const use_info *input : inputs ())
     372                 :            :         {
     373                 :          0 :           basic_block pred_cfg_bb = EDGE_PRED (cfg_bb, i)->src;
     374                 :          0 :           pp_newline_and_indent (pp, 2);
     375                 :          0 :           pp_string (pp, "bb");
     376                 :          0 :           pp_decimal_int (pp, pred_cfg_bb->index);
     377                 :          0 :           pp_colon (pp);
     378                 :          0 :           pp_space (pp);
     379                 :          0 :           input->print_def (pp);
     380                 :          0 :           pp_indentation (pp) -= 2;
     381                 :          0 :           i += 1;
     382                 :            :         }
     383                 :          0 :       pp_indentation (pp) -= 2;
     384                 :            : 
     385                 :          0 :       print_uses_on_new_lines (pp);
     386                 :            :     }
     387                 :          0 : }
     388                 :            : 
     389                 :            : // See the comment above the declaration.
     390                 :            : void
     391                 :          0 : set_node::print (pretty_printer *pp) const
     392                 :            : {
     393                 :          0 :   pp_access (pp, first_def ());
     394                 :          0 : }
     395                 :            : 
     396                 :            : // See the comment above the declaration.
     397                 :            : void
     398                 :          0 : clobber_group::print (pretty_printer *pp) const
     399                 :            : {
     400                 :          0 :   auto print_clobber = [](pretty_printer *pp, const def_info *clobber)
     401                 :            :     {
     402                 :          0 :       pp_access (pp, clobber);
     403                 :            :     };
     404                 :          0 :   pp_string (pp, "grouped clobber");
     405                 :          0 :   for (const def_info *clobber : clobbers ())
     406                 :            :     {
     407                 :          0 :       pp_newline_and_indent (pp, 2);
     408                 :          0 :       print_clobber (pp, clobber);
     409                 :          0 :       pp_indentation (pp) -= 2;
     410                 :            :     }
     411                 :          0 :   pp_newline_and_indent (pp, 2);
     412                 :          0 :   pp_string (pp, "splay tree");
     413                 :          0 :   pp_newline_and_indent (pp, 2);
     414                 :          0 :   m_clobber_tree.print (pp, print_clobber);
     415                 :          0 :   pp_indentation (pp) -= 4;
     416                 :          0 : }
     417                 :            : 
     418                 :            : // Return a clobber_group for CLOBBER, creating one if CLOBBER doesn't
     419                 :            : // already belong to a group.
     420                 :            : clobber_group *
     421                 :   21719588 : function_info::need_clobber_group (clobber_info *clobber)
     422                 :            : {
     423                 :   21719588 :   if (clobber->is_in_group ())
     424                 :   17356251 :     return clobber->group ();
     425                 :    4363337 :   return allocate<clobber_group> (clobber);
     426                 :            : }
     427                 :            : 
     428                 :            : // Return a def_node for inserting DEF into the associated resource's
     429                 :            : // splay tree.  Use a clobber_group if DEF is a clobber and a set_node
     430                 :            : // otherwise.
     431                 :            : def_node *
     432                 :    6096886 : function_info::need_def_node (def_info *def)
     433                 :            : {
     434                 :    6096886 :   if (auto *clobber = dyn_cast<clobber_info *> (def))
     435                 :     741340 :     return need_clobber_group (clobber);
     436                 :    5355546 :   return allocate<set_node> (as_a<set_info *> (def));
     437                 :            : }
     438                 :            : 
     439                 :            : // LAST is the last thing to define LAST->resource (), and is where any
     440                 :            : // splay tree root for LAST->resource () is stored.  Require such a splay tree
     441                 :            : // to exist, creating a new one if necessary.  Return the root of the tree.
     442                 :            : //
     443                 :            : // The caller must call LAST->set_splay_root after it has finished with
     444                 :            : // the splay tree.
     445                 :            : def_splay_tree
     446                 :     418499 : function_info::need_def_splay_tree (def_info *last)
     447                 :            : {
     448                 :     418499 :   if (def_node *root = last->splay_root ())
     449                 :     271115 :     return root;
     450                 :            : 
     451                 :            :   // Use a left-spine rooted at the last node.
     452                 :     147384 :   def_node *root = need_def_node (last);
     453                 :     147384 :   def_node *parent = root;
     454                 :   11428182 :   while (def_info *prev = first_def (parent)->prev_def ())
     455                 :            :     {
     456                 :    5926098 :       def_node *node = need_def_node (prev);
     457                 :    5926098 :       def_splay_tree::insert_child (parent, 0, node);
     458                 :    5926098 :       parent = node;
     459                 :    5926098 :     }
     460                 :     147384 :   return root;
     461                 :            : }
     462                 :            : 
     463                 :            : // Search TREE for either:
     464                 :            : //
     465                 :            : // - a set_info at INSN or
     466                 :            : // - a clobber_group whose range includes INSN
     467                 :            : //
     468                 :            : // If such a node exists, install it as the root of TREE and return 0.
     469                 :            : // Otherwise arbitrarily choose between:
     470                 :            : //
     471                 :            : // (1) Installing the closest preceding node as the root and returning 1.
     472                 :            : // (2) Installing the closest following node as the root and returning -1.
     473                 :            : //
     474                 :            : // Note that this routine should not be used to check whether INSN
     475                 :            : // itself defines a resource; that can be checked more cheaply using
     476                 :            : // find_access_index.
     477                 :            : int
     478                 :     432606 : rtl_ssa::lookup_def (def_splay_tree &tree, insn_info *insn)
     479                 :            : {
     480                 :    6791041 :   auto go_left = [&](def_node *node)
     481                 :            :     {
     482                 :   11635509 :       return *insn < *first_def (node)->insn ();
     483                 :     432606 :     };
     484                 :    1309870 :   auto go_right = [&](def_node *node)
     485                 :            :     {
     486                 :    1754528 :       return *insn > *last_def (node)->insn ();
     487                 :     432606 :     };
     488                 :     432606 :   return tree.lookup (go_left, go_right);
     489                 :            : }
     490                 :            : 
     491                 :            : // Search TREE for a clobber in INSN.  If such a clobber exists, install
     492                 :            : // it as the root of TREE and return 0.  Otherwise arbitrarily choose between:
     493                 :            : //
     494                 :            : // (1) Installing the closest preceding clobber as the root and returning 1.
     495                 :            : // (2) Installing the closest following clobber as the root and returning -1.
     496                 :            : int
     497                 :     124849 : rtl_ssa::lookup_clobber (clobber_tree &tree, insn_info *insn)
     498                 :            : {
     499                 :     555941 :   auto compare = [&](clobber_info *clobber)
     500                 :            :     {
     501                 :     431092 :       return insn->compare_with (clobber->insn ());
     502                 :     124849 :     };
     503                 :     124849 :   return tree.lookup (compare);
     504                 :            : }
     505                 :            : 
     506                 :            : // Search for a definition of RESOURCE at INSN and return the result of
     507                 :            : // the search as a def_lookup.  See the comment above the class for more
     508                 :            : // details.
     509                 :            : def_lookup
     510                 :     196933 : function_info::find_def (resource_info resource, insn_info *insn)
     511                 :            : {
     512                 :     196933 :   def_info *first = m_defs[resource.regno + 1];
     513                 :     196933 :   if (!first)
     514                 :            :     // There are no nodes.  The comparison result is pretty meaningless
     515                 :            :     // in this case.
     516                 :          0 :     return { nullptr, -1 };
     517                 :            : 
     518                 :            :   // See whether the first node matches.
     519                 :     196933 :   auto first_result = clobber_group_or_single_def (first);
     520                 :     196933 :   if (*insn <= *last_def (first_result)->insn ())
     521                 :            :     {
     522                 :          0 :       int comparison = (*insn >= *first->insn () ? 0 : -1);
     523                 :          0 :       return { first_result, comparison };
     524                 :            :     }
     525                 :            : 
     526                 :            :   // See whether the last node matches.
     527                 :     196933 :   def_info *last = first->last_def ();
     528                 :     196933 :   auto last_result = clobber_group_or_single_def (last);
     529                 :     196941 :   if (*insn >= *first_def (last_result)->insn ())
     530                 :            :     {
     531                 :       8680 :       int comparison = (*insn <= *last->insn () ? 0 : 1);
     532                 :       8680 :       return { last_result, comparison };
     533                 :            :     }
     534                 :            : 
     535                 :            :   // Resort to using a splay tree to search for the result.
     536                 :     188253 :   def_splay_tree tree = need_def_splay_tree (last);
     537                 :     188253 :   int comparison = lookup_def (tree, insn);
     538                 :     188253 :   last->set_splay_root (tree.root ());
     539                 :     188253 :   return { tree.root (), comparison };
     540                 :            : }
     541                 :            : 
     542                 :            : // Add DEF to the function's list of definitions of DEF->resource (),
     543                 :            : // inserting DEF immediately before BEFORE.  DEF is not currently in the list.
     544                 :            : void
     545                 :     133552 : function_info::insert_def_before (def_info *def, def_info *before)
     546                 :            : {
     547                 :     267104 :   gcc_checking_assert (!def->has_def_links ()
     548                 :            :                        && *before->insn () > *def->insn ());
     549                 :            : 
     550                 :     133552 :   def->copy_prev_from (before);
     551                 :     133552 :   if (def_info *prev = def->prev_def ())
     552                 :            :     {
     553                 :     122980 :       gcc_checking_assert (*prev->insn () < *def->insn ());
     554                 :     122980 :       prev->set_next_def (def);
     555                 :            :     }
     556                 :            :   else
     557                 :      10572 :     m_defs[def->regno () + 1] = def;
     558                 :            : 
     559                 :     133552 :   def->set_next_def (before);
     560                 :     133552 :   before->set_prev_def (def);
     561                 :     133552 : }
     562                 :            : 
     563                 :            : // Add DEF to the function's list of definitions of DEF->resource (),
     564                 :            : // inserting DEF immediately after AFTER.  DEF is not currently in the list.
     565                 :            : void
     566                 :   22276563 : function_info::insert_def_after (def_info *def, def_info *after)
     567                 :            : {
     568                 :   44553126 :   gcc_checking_assert (!def->has_def_links ()
     569                 :            :                        && *after->insn () < *def->insn ());
     570                 :            : 
     571                 :   22276563 :   def->copy_next_from (after);
     572                 :   22276563 :   if (def_info *next = def->next_def ())
     573                 :            :     {
     574                 :     107266 :       gcc_checking_assert (*next->insn () > *def->insn ());
     575                 :     107266 :       next->set_prev_def (def);
     576                 :            :     }
     577                 :            :   else
     578                 :   22169297 :     m_defs[def->regno () + 1]->set_last_def (def);
     579                 :            : 
     580                 :   22276563 :   def->set_prev_def (after);
     581                 :   22276563 :   after->set_next_def (def);
     582                 :   22276563 : }
     583                 :            : 
     584                 :            : // Remove DEF from the function's list of definitions of DEF->resource ().
     585                 :            : void
     586                 :    3005788 : function_info::remove_def_from_list (def_info *def)
     587                 :            : {
     588                 :    3005788 :   def_info *prev = def->prev_def ();
     589                 :    3005788 :   def_info *next = def->next_def ();
     590                 :            : 
     591                 :    1337085 :   if (next)
     592                 :    1337085 :     next->copy_prev_from (def);
     593                 :            :   else
     594                 :    1668703 :     m_defs[def->regno () + 1]->set_last_def (prev);
     595                 :            : 
     596                 :    3005788 :   if (prev)
     597                 :    2995206 :     prev->copy_next_from (def);
     598                 :            :   else
     599                 :      10582 :     m_defs[def->regno () + 1] = next;
     600                 :            : 
     601                 :    3005788 :   def->clear_def_links ();
     602                 :    3005788 : }
     603                 :            : 
     604                 :            : // Add CLOBBER to GROUP and insert it into the function's list of
     605                 :            : // accesses to CLOBBER->resource ().  CLOBBER is not currently part
     606                 :            : // of an active group and is not currently in the list.
     607                 :            : void
     608                 :     124841 : function_info::add_clobber (clobber_info *clobber, clobber_group *group)
     609                 :            : {
     610                 :            :   // Search for either the previous or next clobber in the group.
     611                 :            :   // The result is less than zero if CLOBBER should come before NEIGHBOR
     612                 :            :   // or greater than zero if CLOBBER should come after NEIGHBOR.
     613                 :     124841 :   int comparison = lookup_clobber (group->m_clobber_tree, clobber->insn ());
     614                 :     124841 :   gcc_checking_assert (comparison != 0);
     615                 :     124841 :   clobber_info *neighbor = group->m_clobber_tree.root ();
     616                 :            : 
     617                 :            :   // Since HEIGHBOR is now the root of the splay tree, its group needs
     618                 :            :   // to be up-to-date.
     619                 :     124841 :   neighbor->update_group (group);
     620                 :            : 
     621                 :            :   // If CLOBBER comes before NEIGHBOR, insert CLOBBER to NEIGHBOR's left,
     622                 :            :   // otherwise insert CLOBBER to NEIGHBOR's right.
     623                 :     124841 :   clobber_info::splay_tree::insert_child (neighbor, comparison > 0, clobber);
     624                 :     124841 :   clobber->set_group (group);
     625                 :            : 
     626                 :            :   // Insert the clobber into the function-wide list and update the
     627                 :            :   // bounds of the group.
     628                 :     124841 :   if (comparison > 0)
     629                 :            :     {
     630                 :       1861 :       insert_def_after (clobber, neighbor);
     631                 :       1861 :       if (neighbor == group->last_clobber ())
     632                 :          0 :         group->set_last_clobber (clobber);
     633                 :            :     }
     634                 :            :   else
     635                 :            :     {
     636                 :     122980 :       insert_def_before (clobber, neighbor);
     637                 :     122980 :       if (neighbor == group->first_clobber ())
     638                 :          0 :         group->set_first_clobber (clobber);
     639                 :            :     }
     640                 :     124841 : }
     641                 :            : 
     642                 :            : // Remove CLOBBER from GROUP, given that GROUP contains other clobbers too.
     643                 :            : // Also remove CLOBBER from the function's list of accesses to
     644                 :            : // CLOBBER->resource ().
     645                 :            : void
     646                 :     225779 : function_info::remove_clobber (clobber_info *clobber, clobber_group *group)
     647                 :            : {
     648                 :     225779 :   if (clobber == group->first_clobber ())
     649                 :            :     {
     650                 :     118868 :       auto *new_first = as_a<clobber_info *> (clobber->next_def ());
     651                 :      59434 :       group->set_first_clobber (new_first);
     652                 :      59434 :       new_first->update_group (group);
     653                 :            :     }
     654                 :     166345 :   else if (clobber == group->last_clobber ())
     655                 :            :     {
     656                 :      72430 :       auto *new_last = as_a<clobber_info *> (clobber->prev_def ());
     657                 :      36215 :       group->set_last_clobber (new_last);
     658                 :      36215 :       new_last->update_group (group);
     659                 :            :     }
     660                 :            : 
     661                 :     225779 :   clobber_info *replacement = clobber_info::splay_tree::remove_node (clobber);
     662                 :     225779 :   if (clobber == group->m_clobber_tree.root ())
     663                 :            :     {
     664                 :      95080 :       group->m_clobber_tree = replacement;
     665                 :      95080 :       replacement->update_group (group);
     666                 :            :     }
     667                 :     225779 :   clobber->set_group (nullptr);
     668                 :            : 
     669                 :     225779 :   remove_def_from_list (clobber);
     670                 :     225779 : }
     671                 :            : 
     672                 :            : // Add CLOBBER immediately before the first clobber in GROUP, given that
     673                 :            : // CLOBBER is not currently part of any group.
     674                 :            : void
     675                 :      58890 : function_info::prepend_clobber_to_group (clobber_info *clobber,
     676                 :            :                                          clobber_group *group)
     677                 :            : {
     678                 :      58890 :   clobber_info *next = group->first_clobber ();
     679                 :      58890 :   clobber_info::splay_tree::insert_child (next, 0, clobber);
     680                 :      58890 :   group->set_first_clobber (clobber);
     681                 :      58890 :   clobber->set_group (group);
     682                 :      58890 : }
     683                 :            : 
     684                 :            : // Add CLOBBER immediately after the last clobber in GROUP, given that
     685                 :            : // CLOBBER is not currently part of any group.
     686                 :            : void
     687                 :   20919358 : function_info::append_clobber_to_group (clobber_info *clobber,
     688                 :            :                                         clobber_group *group)
     689                 :            : {
     690                 :   20919358 :   clobber_info *prev = group->last_clobber ();
     691                 :   20919358 :   clobber_info::splay_tree::insert_child (prev, 1, clobber);
     692                 :   20919358 :   group->set_last_clobber (clobber);
     693                 :   20919358 :   clobber->set_group (group);
     694                 :   20919358 : }
     695                 :            : 
     696                 :            : // Put CLOBBER1 and CLOBBER2 into the same clobber_group, given that
     697                 :            : // CLOBBER1 occurs immediately before CLOBBER2 and that the two clobbers
     698                 :            : // are not currently in the same group.  LAST is the last definition of
     699                 :            : // the associated resource, and is where any splay tree is stored.
     700                 :            : void
     701                 :          8 : function_info::merge_clobber_groups (clobber_info *clobber1,
     702                 :            :                                      clobber_info *clobber2,
     703                 :            :                                      def_info *last)
     704                 :            : {
     705                 :          8 :   if (clobber1->is_in_group () && clobber2->is_in_group ())
     706                 :            :     {
     707                 :          0 :       clobber_group *group1 = clobber1->group ();
     708                 :          0 :       clobber_group *group2 = clobber2->group ();
     709                 :          0 :       gcc_checking_assert (clobber1 == group1->last_clobber ()
     710                 :            :                            && clobber2 == group2->first_clobber ());
     711                 :            : 
     712                 :          0 :       if (def_splay_tree tree = last->splay_root ())
     713                 :            :         {
     714                 :            :           // Remove GROUP2 from the splay tree.
     715                 :          0 :           int comparison = lookup_def (tree, clobber2->insn ());
     716                 :          0 :           gcc_checking_assert (comparison == 0);
     717                 :          0 :           tree.remove_root ();
     718                 :          0 :           last->set_splay_root (tree.root ());
     719                 :            :         }
     720                 :            : 
     721                 :            :       // Splice the trees together.
     722                 :          0 :       group1->m_clobber_tree.splice_next_tree (group2->m_clobber_tree);
     723                 :            : 
     724                 :            :       // Bring the two extremes of GROUP2 under GROUP1.  Any other
     725                 :            :       // clobbers in the group are updated lazily on demand.
     726                 :          0 :       clobber2->set_group (group1);
     727                 :          0 :       group2->last_clobber ()->set_group (group1);
     728                 :          0 :       group1->set_last_clobber (group2->last_clobber ());
     729                 :            : 
     730                 :            :       // Record that GROUP2 is no more.
     731                 :          0 :       group2->set_first_clobber (nullptr);
     732                 :          0 :       group2->set_last_clobber (nullptr);
     733                 :          0 :       group2->m_clobber_tree = nullptr;
     734                 :            :     }
     735                 :            :   else
     736                 :            :     {
     737                 :            :       // In this case there can be no active splay tree.
     738                 :          8 :       gcc_assert (!last->splay_root ());
     739                 :          8 :       if (clobber2->is_in_group ())
     740                 :          0 :         prepend_clobber_to_group (clobber1, clobber2->group ());
     741                 :            :       else
     742                 :          8 :         append_clobber_to_group (clobber2, need_clobber_group (clobber1));
     743                 :            :     }
     744                 :          8 : }
     745                 :            : 
     746                 :            : // GROUP spans INSN, and INSN now sets the resource that GROUP clobbers.
     747                 :            : // Split GROUP around INSN and return the clobber that comes immediately
     748                 :            : // before INSN.
     749                 :            : clobber_info *
     750                 :          8 : function_info::split_clobber_group (clobber_group *group, insn_info *insn)
     751                 :            : {
     752                 :            :   // Search for either the previous or next clobber in the group.
     753                 :            :   // The result is less than zero if CLOBBER should come before NEIGHBOR
     754                 :            :   // or greater than zero if CLOBBER should come after NEIGHBOR.
     755                 :          8 :   int comparison = lookup_clobber (group->m_clobber_tree, insn);
     756                 :          8 :   gcc_checking_assert (comparison != 0);
     757                 :          8 :   clobber_info *neighbor = group->m_clobber_tree.root ();
     758                 :            : 
     759                 :          8 :   clobber_tree tree1, tree2;
     760                 :          8 :   clobber_info *prev;
     761                 :          8 :   clobber_info *next;
     762                 :          8 :   if (comparison > 0)
     763                 :            :     {
     764                 :            :       // NEIGHBOR is the last clobber in what will become the first group.
     765                 :          0 :       tree1 = neighbor;
     766                 :          0 :       tree2 = tree1.split_after_root ();
     767                 :          0 :       prev = neighbor;
     768                 :          0 :       next = as_a<clobber_info *> (prev->next_def ());
     769                 :            :     }
     770                 :            :   else
     771                 :            :     {
     772                 :            :       // NEIGHBOR is the first clobber in what will become the second group.
     773                 :          8 :       tree2 = neighbor;
     774                 :          8 :       tree1 = tree2.split_before_root ();
     775                 :          8 :       next = neighbor;
     776                 :         16 :       prev = as_a<clobber_info *> (next->prev_def ());
     777                 :            :     }
     778                 :            : 
     779                 :            :   // Use GROUP to hold PREV and earlier clobbers.  Create a new group for
     780                 :            :   // NEXT onwards.
     781                 :          8 :   clobber_info *last_clobber = group->last_clobber ();
     782                 :          8 :   clobber_group *group1 = group;
     783                 :          8 :   clobber_group *group2 = allocate<clobber_group> (next);
     784                 :            : 
     785                 :            :   // Finish setting up GROUP1, making sure that the roots and extremities
     786                 :            :   // have a correct group pointer.  Leave the rest to be updated lazily.
     787                 :          8 :   group1->set_last_clobber (prev);
     788                 :          8 :   tree1->set_group (group1);
     789                 :          8 :   prev->set_group (group1);
     790                 :            : 
     791                 :            :   // Finish setting up GROUP2, with the same approach as for GROUP1.
     792                 :          8 :   group2->set_first_clobber (next);
     793                 :          8 :   group2->set_last_clobber (last_clobber);
     794                 :          8 :   next->set_group (group2);
     795                 :          8 :   tree2->set_group (group2);
     796                 :          8 :   last_clobber->set_group (group2);
     797                 :            : 
     798                 :          8 :   return prev;
     799                 :            : }
     800                 :            : 
     801                 :            : // Add DEF to the end of the function's list of definitions of
     802                 :            : // DEF->resource ().  There is known to be no associated splay tree yet.
     803                 :            : void
     804                 :  136282249 : function_info::append_def (def_info *def)
     805                 :            : {
     806                 :  136282249 :   gcc_checking_assert (!def->has_def_links ());
     807                 :  136282249 :   def_info **head = &m_defs[def->regno () + 1];
     808                 :  136282249 :   def_info *first = *head;
     809                 :  136282249 :   if (!first)
     810                 :            :     {
     811                 :            :       // This is the only definition of the resource.
     812                 :   56392755 :       def->set_last_def (def);
     813                 :   56392755 :       *head = def;
     814                 :   56392755 :       return;
     815                 :            :     }
     816                 :            : 
     817                 :   79889494 :   def_info *prev = first->last_def ();
     818                 :   79889494 :   gcc_checking_assert (!prev->splay_root ());
     819                 :            : 
     820                 :            :   // Maintain the invariant that two clobbers must not appear in
     821                 :            :   // neighboring nodes of the splay tree.
     822                 :   79889494 :   auto *clobber = dyn_cast<clobber_info *> (def);
     823                 :   79889494 :   auto *prev_clobber = dyn_cast<clobber_info *> (prev);
     824                 :   79889494 :   if (clobber && prev_clobber)
     825                 :   20885604 :     append_clobber_to_group (clobber, need_clobber_group (prev_clobber));
     826                 :            : 
     827                 :   79889494 :   prev->set_next_def (def);
     828                 :   79889494 :   def->set_prev_def (prev);
     829                 :   79889494 :   first->set_last_def (def);
     830                 :            : }
     831                 :            : 
     832                 :            : // Add DEF to the function's list of definitions of DEF->resource ().
     833                 :            : // Also insert it into the associated splay tree, if there is one.
     834                 :            : // DEF is not currently part of the list and is not in the splay tree.
     835                 :            : void
     836                 :   22414600 : function_info::add_def (def_info *def)
     837                 :            : {
     838                 :   44829200 :   gcc_checking_assert (!def->has_def_links ()
     839                 :            :                        && !def->m_is_temp
     840                 :            :                        && !def->m_has_been_superceded);
     841                 :   22414600 :   def_info **head = &m_defs[def->regno () + 1];
     842                 :   22414600 :   def_info *first = *head;
     843                 :   22414600 :   if (!first)
     844                 :            :     {
     845                 :            :       // This is the only definition of the resource.
     846                 :       4485 :       def->set_last_def (def);
     847                 :       4485 :       *head = def;
     848                 :       4485 :       return;
     849                 :            :     }
     850                 :            : 
     851                 :   22410115 :   def_info *last = first->last_def ();
     852                 :   22410115 :   insn_info *insn = def->insn ();
     853                 :            : 
     854                 :   22410115 :   int comparison;
     855                 :   22410115 :   def_node *root = nullptr;
     856                 :   22410115 :   def_info *prev = nullptr;
     857                 :   22410115 :   def_info *next = nullptr;
     858                 :   22410115 :   if (*insn > *last->insn ())
     859                 :            :     {
     860                 :            :       // This definition comes after all other definitions.
     861                 :   22169297 :       comparison = 1;
     862                 :   22169297 :       if (def_splay_tree tree = last->splay_root ())
     863                 :            :         {
     864                 :       1320 :           tree.splay_max_node ();
     865                 :       1320 :           root = tree.root ();
     866                 :       1320 :           last->set_splay_root (root);
     867                 :            :         }
     868                 :   22169297 :       prev = last;
     869                 :            :     }
     870                 :     240818 :   else if (*insn < *first->insn ())
     871                 :            :     {
     872                 :            :       // This definition comes before all other definitions.
     873                 :      10572 :       comparison = -1;
     874                 :      10572 :       if (def_splay_tree tree = last->splay_root ())
     875                 :            :         {
     876                 :        758 :           tree.splay_min_node ();
     877                 :        758 :           root = tree.root ();
     878                 :        758 :           last->set_splay_root (root);
     879                 :            :         }
     880                 :      10572 :       next = first;
     881                 :            :     }
     882                 :            :   else
     883                 :            :     {
     884                 :            :       // Search the splay tree for an insertion point.
     885                 :     230246 :       def_splay_tree tree = need_def_splay_tree (last);
     886                 :     230246 :       comparison = lookup_def (tree, insn);
     887                 :     230246 :       root = tree.root ();
     888                 :     230246 :       last->set_splay_root (root);
     889                 :            : 
     890                 :            :       // Deal with cases in which we found an overlapping live range.
     891                 :     230246 :       if (comparison == 0)
     892                 :            :         {
     893                 :     124849 :           auto *group = as_a<clobber_group *> (tree.root ());
     894                 :     124849 :           if (auto *clobber = dyn_cast<clobber_info *> (def))
     895                 :            :             {
     896                 :     124841 :               add_clobber (clobber, group);
     897                 :     124841 :               return;
     898                 :            :             }
     899                 :          8 :           prev = split_clobber_group (group, insn);
     900                 :     105413 :           next = prev->next_def ();
     901                 :            :         }
     902                 :            :       // COMPARISON is < 0 if DEF comes before ROOT or > 0 if DEF comes
     903                 :            :       // after ROOT.
     904                 :     105397 :       else if (comparison < 0)
     905                 :            :         {
     906                 :      45250 :           next = first_def (root);
     907                 :      45250 :           prev = next->prev_def ();
     908                 :            :         }
     909                 :            :       else
     910                 :            :         {
     911                 :      60147 :           prev = last_def (root);
     912                 :     165552 :           next = prev->next_def ();
     913                 :            :         }
     914                 :            :     }
     915                 :            : 
     916                 :            :   // See if we should merge CLOBBER with a neighboring clobber.
     917                 :   22285274 :   auto *clobber = dyn_cast<clobber_info *> (def);
     918                 :   22285274 :   auto *prev_clobber = safe_dyn_cast<clobber_info *> (prev);
     919                 :   22285274 :   auto *next_clobber = safe_dyn_cast<clobber_info *> (next);
     920                 :            :   // We shouldn't have consecutive clobber_groups.
     921                 :   22285274 :   gcc_checking_assert (!(clobber && prev_clobber && next_clobber));
     922                 :   22285274 :   if (clobber && prev_clobber)
     923                 :      33746 :     append_clobber_to_group (clobber, need_clobber_group (prev_clobber));
     924                 :   22251528 :   else if (clobber && next_clobber)
     925                 :      58890 :     prepend_clobber_to_group (clobber, need_clobber_group (next_clobber));
     926                 :   22192638 :   else if (root)
     927                 :            :     {
     928                 :            :       // If DEF comes before ROOT, insert DEF to ROOT's left,
     929                 :            :       // otherwise insert DEF to ROOT's right.
     930                 :      23404 :       def_node *node = need_def_node (def);
     931                 :      23404 :       def_splay_tree::insert_child (root, comparison >= 0, node);
     932                 :            :     }
     933                 :   22285274 :   if (prev)
     934                 :   22274702 :     insert_def_after (def, prev);
     935                 :            :   else
     936                 :      10572 :     insert_def_before (def, next);
     937                 :            : }
     938                 :            : 
     939                 :            : // Remove DEF from the function's list of definitions of DEF->resource ().
     940                 :            : // Also remove DEF from the associated splay tree, if there is one.
     941                 :            : void
     942                 :    3010274 : function_info::remove_def (def_info *def)
     943                 :            : {
     944                 :    3010274 :   def_info **head = &m_defs[def->regno () + 1];
     945                 :    3010274 :   def_info *first = *head;
     946                 :    3010274 :   gcc_checking_assert (first);
     947                 :    3010274 :   if (first->is_last_def ())
     948                 :            :     {
     949                 :            :       // DEF is the only definition of the resource.
     950                 :       4486 :       gcc_checking_assert (first == def);
     951                 :       4486 :       *head = nullptr;
     952                 :       4486 :       def->clear_def_links ();
     953                 :       4486 :       return;
     954                 :            :     }
     955                 :            : 
     956                 :            :   // If CLOBBER belongs to a clobber_group that contains other clobbers
     957                 :            :   // too, then we need to update the clobber_group and the list, but any
     958                 :            :   // splay tree that contains the clobber_group is unaffected.
     959                 :    3005788 :   if (auto *clobber = dyn_cast<clobber_info *> (def))
     960                 :     306818 :     if (clobber->is_in_group ())
     961                 :            :       {
     962                 :     239902 :         clobber_group *group = clobber->group ();
     963                 :     239902 :         if (group->first_clobber () != group->last_clobber ())
     964                 :            :           {
     965                 :     225779 :             remove_clobber (clobber, group);
     966                 :     225779 :             return;
     967                 :            :           }
     968                 :            :       }
     969                 :            : 
     970                 :            :   // If we've created a splay tree for this resource, remove the entry
     971                 :            :   // for DEF.
     972                 :    2780009 :   def_info *last = first->last_def ();
     973                 :    2780009 :   if (def_splay_tree tree = last->splay_root ())
     974                 :            :     {
     975                 :      14107 :       int comparison = lookup_def (tree, def->insn ());
     976                 :      14107 :       gcc_checking_assert (comparison == 0);
     977                 :      14107 :       tree.remove_root ();
     978                 :      14107 :       last->set_splay_root (tree.root ());
     979                 :            :     }
     980                 :            : 
     981                 :            :   // If the definition came between two clobbers, merge them into a single
     982                 :            :   // group.
     983                 :    5556876 :   auto *prev_clobber = safe_dyn_cast<clobber_info *> (def->prev_def ());
     984                 :    3893213 :   auto *next_clobber = safe_dyn_cast<clobber_info *> (def->next_def ());
     985                 :    2780009 :   if (prev_clobber && next_clobber)
     986                 :          8 :     merge_clobber_groups (prev_clobber, next_clobber, last);
     987                 :            : 
     988                 :    2780009 :   remove_def_from_list (def);
     989                 :            : }
     990                 :            : 
     991                 :            : // Require DEF to have a splay tree that contains all non-phi uses.
     992                 :            : void
     993                 :     993555 : function_info::need_use_splay_tree (set_info *def)
     994                 :            : {
     995                 :     993555 :   if (!def->m_use_tree)
     996                 :    7978369 :     for (use_info *use : def->all_insn_uses ())
     997                 :            :       {
     998                 :    7251829 :         auto *use_node = allocate<splay_tree_node<use_info *>> (use);
     999                 :    7251829 :         def->m_use_tree.insert_max_node (use_node);
    1000                 :            :       }
    1001                 :     993555 : }
    1002                 :            : 
    1003                 :            : // Compare two instructions by their position in a use splay tree.  Return >0
    1004                 :            : // if INSN1 comes after INSN2, <0 if INSN1 comes before INSN2, or 0 if they are
    1005                 :            : // the same instruction.
    1006                 :            : static inline int
    1007                 :  264247993 : compare_use_insns (insn_info *insn1, insn_info *insn2)
    1008                 :            : {
    1009                 :            :   // Debug instructions go after nondebug instructions.
    1010                 :  264247993 :   int diff = insn1->is_debug_insn () - insn2->is_debug_insn ();
    1011                 :  264247993 :   if (diff != 0)
    1012                 :            :     return diff;
    1013                 :  250414065 :   return insn1->compare_with (insn2);
    1014                 :            : }
    1015                 :            : 
    1016                 :            : // Search TREE for a use in INSN.  If such a use exists, install it as
    1017                 :            : // the root of TREE and return 0.  Otherwise arbitrarily choose between:
    1018                 :            : //
    1019                 :            : // (1) Installing the closest preceding use as the root and returning 1.
    1020                 :            : // (2) Installing the closest following use as the root and returning -1.
    1021                 :            : int
    1022                 :    1343593 : rtl_ssa::lookup_use (splay_tree<use_info *> &tree, insn_info *insn)
    1023                 :            : {
    1024                 :   11358439 :   auto compare = [&](splay_tree_node<use_info *> *node)
    1025                 :            :     {
    1026                 :   10014846 :       return compare_use_insns (insn, node->value ()->insn ());
    1027                 :    1343593 :     };
    1028                 :    1343593 :   return tree.lookup (compare);
    1029                 :            : }
    1030                 :            : 
    1031                 :            : // Add USE to USE->def ()'s list of uses. inserting USE immediately before
    1032                 :            : // BEFORE.  USE is not currently in the list.
    1033                 :            : //
    1034                 :            : // This routine should not be used for inserting phi uses.
    1035                 :            : void
    1036                 :    4711402 : function_info::insert_use_before (use_info *use, use_info *before)
    1037                 :            : {
    1038                 :    9422804 :   gcc_checking_assert (!use->has_use_links () && use->is_in_any_insn ());
    1039                 :            : 
    1040                 :    4711402 :   set_info *def = use->def ();
    1041                 :            : 
    1042                 :    4711402 :   use->copy_prev_from (before);
    1043                 :    4711402 :   use->set_next_use (before);
    1044                 :            : 
    1045                 :    4711402 :   if (use_info *prev = use->prev_use ())
    1046                 :     334257 :     prev->set_next_use (use);
    1047                 :            :   else
    1048                 :    4377145 :     use->def ()->set_first_use (use);
    1049                 :            : 
    1050                 :    4711402 :   before->set_prev_use (use);
    1051                 :    4711402 :   if (use->is_in_nondebug_insn () && before->is_in_debug_insn_or_phi ())
    1052                 :    8246656 :     def->last_use ()->set_last_nondebug_insn_use (use);
    1053                 :            : 
    1054                 :    4711402 :   gcc_checking_assert (use->check_integrity () && before->check_integrity ());
    1055                 :    4711402 : }
    1056                 :            : 
    1057                 :            : // Add USE to USE->def ()'s list of uses. inserting USE immediately after
    1058                 :            : // AFTER.  USE is not currently in the list.
    1059                 :            : //
    1060                 :            : // This routine should not be used for inserting phi uses.
    1061                 :            : void
    1062                 :  125293758 : function_info::insert_use_after (use_info *use, use_info *after)
    1063                 :            : {
    1064                 :  125293758 :   set_info *def = use->def ();
    1065                 :  250587516 :   gcc_checking_assert (after->is_in_any_insn ()
    1066                 :            :                        && !use->has_use_links ()
    1067                 :            :                        && use->is_in_any_insn ());
    1068                 :            : 
    1069                 :  125293758 :   use->set_prev_use (after);
    1070                 :  125293758 :   use->copy_next_from (after);
    1071                 :            : 
    1072                 :  125293758 :   after->set_next_use (use);
    1073                 :            : 
    1074                 :  125293758 :   if (use_info *next = use->next_use ())
    1075                 :            :     {
    1076                 :            :       // The last node doesn't change, but we might need to update its
    1077                 :            :       // last_nondebug_insn_use record.
    1078                 :   19552627 :       if (use->is_in_nondebug_insn () && next->is_in_debug_insn_or_phi ())
    1079                 :   38004726 :         def->last_use ()->set_last_nondebug_insn_use (use);
    1080                 :   19552627 :       next->set_prev_use (use);
    1081                 :            :     }
    1082                 :            :   else
    1083                 :            :     {
    1084                 :            :       // USE is now the last node.
    1085                 :  105741131 :       if (use->is_in_nondebug_insn ())
    1086                 :   96948952 :         use->set_last_nondebug_insn_use (use);
    1087                 :  105741131 :       def->first_use ()->set_last_use (use);
    1088                 :            :     }
    1089                 :            : 
    1090                 :  125293758 :   gcc_checking_assert (use->check_integrity () && after->check_integrity ());
    1091                 :  125293758 : }
    1092                 :            : 
    1093                 :            : // If USE has a known definition, add USE to that definition's list of uses.
    1094                 :            : // Also update the associated splay tree, if any.
    1095                 :            : void
    1096                 :  279953671 : function_info::add_use (use_info *use)
    1097                 :            : {
    1098                 :  559907342 :   gcc_checking_assert (!use->has_use_links ()
    1099                 :            :                        && !use->m_is_temp
    1100                 :            :                        && !use->m_has_been_superceded);
    1101                 :            : 
    1102                 :  279953671 :   set_info *def = use->def ();
    1103                 :  279953671 :   if (!def)
    1104                 :  278960116 :     return;
    1105                 :            : 
    1106                 :  267424450 :   use_info *first = def->first_use ();
    1107                 :  267424450 :   if (!first)
    1108                 :            :     {
    1109                 :            :       // This is the only use of the definition.
    1110                 :  111028438 :       use->set_last_use (use);
    1111                 :  111028438 :       if (use->is_in_nondebug_insn ())
    1112                 :   97356601 :         use->set_last_nondebug_insn_use (use);
    1113                 :            : 
    1114                 :  111028438 :       def->set_first_use (use);
    1115                 :            : 
    1116                 :  111028438 :       gcc_checking_assert (use->check_integrity ());
    1117                 :            :       return;
    1118                 :            :     }
    1119                 :            : 
    1120                 :  156396012 :   if (use->is_in_phi ())
    1121                 :            :     {
    1122                 :            :       // Add USE at the end of the list, as the new first phi.
    1123                 :   26390852 :       use_info *last = first->last_use ();
    1124                 :            : 
    1125                 :   26390852 :       use->set_prev_use (last);
    1126                 :   26390852 :       use->copy_next_from (last);
    1127                 :            : 
    1128                 :   26390852 :       last->set_next_use (use);
    1129                 :   26390852 :       first->set_last_use (use);
    1130                 :            : 
    1131                 :   26390852 :       gcc_checking_assert (use->check_integrity ());
    1132                 :            :       return;
    1133                 :            :     }
    1134                 :            : 
    1135                 :            :   // If there is currently no splay tree for this definition, see if can
    1136                 :            :   // get away with a pure list-based update.
    1137                 :  130005160 :   insn_info *insn = use->insn ();
    1138                 :  259380035 :   auto quick_path = [&]()
    1139                 :            :     {
    1140                 :            :       // Check if USE should come before all current uses.
    1141                 :  254292041 :       if (first->is_in_phi () || compare_use_insns (insn, first->insn ()) < 0)
    1142                 :            :         {
    1143                 :  254011197 :           insert_use_before (use, first);
    1144                 :    4375283 :           return true;
    1145                 :            :         }
    1146                 :            : 
    1147                 :            :       // Check if USE should come after all current uses in the same
    1148                 :            :       // subsequence (i.e. the list of nondebug insn uses or the list
    1149                 :            :       // of debug insn uses).
    1150                 :  124999592 :       use_info *last = first->last_use ();
    1151                 :  124999592 :       if (use->is_in_debug_insn ())
    1152                 :            :         {
    1153                 :    8865078 :           if (last->is_in_phi ())
    1154                 :            :             return false;
    1155                 :            :         }
    1156                 :            :       else
    1157                 :  116134514 :         last = last->last_nondebug_insn_use ();
    1158                 :            : 
    1159                 :  124917166 :       if (compare_use_insns (insn, last->insn ()) > 0)
    1160                 :            :         {
    1161                 :  124636322 :           insert_use_after (use, last);
    1162                 :  124636322 :           return true;
    1163                 :            :         }
    1164                 :            : 
    1165                 :            :       return false;
    1166                 :  130005160 :     };
    1167                 :  130005160 :   if (!def->m_use_tree && quick_path ())
    1168                 :            :     return;
    1169                 :            : 
    1170                 :            :   // Search the splay tree for an insertion point.  COMPARISON is less
    1171                 :            :   // than zero if USE should come before NEIGHBOR, or greater than zero
    1172                 :            :   // if USE should come after NEIGHBOR.
    1173                 :     993555 :   need_use_splay_tree (def);
    1174                 :     993555 :   int comparison = lookup_use (def->m_use_tree, insn);
    1175                 :     993555 :   gcc_checking_assert (comparison != 0);
    1176                 :     993555 :   splay_tree_node<use_info *> *neighbor = def->m_use_tree.root ();
    1177                 :            : 
    1178                 :            :   // If USE comes before NEIGHBOR, insert USE to NEIGHBOR's left,
    1179                 :            :   // otherwise insert USE to NEIGHBOR's right.
    1180                 :     993555 :   auto *use_node = allocate<splay_tree_node<use_info *>> (use);
    1181                 :     993555 :   def->m_use_tree.insert_child (neighbor, comparison > 0, use_node);
    1182                 :     993555 :   if (comparison > 0)
    1183                 :     657436 :     insert_use_after (use, neighbor->value ());
    1184                 :            :   else
    1185                 :     336119 :     insert_use_before (use, neighbor->value ());
    1186                 :            : }
    1187                 :            : 
    1188                 :            : // If USE has a known definition, remove USE from that definition's list
    1189                 :            : // of uses.  Also remove if it from the associated splay tree, if any.
    1190                 :            : void
    1191                 :    7839955 : function_info::remove_use (use_info *use)
    1192                 :            : {
    1193                 :    7839955 :   set_info *def = use->def ();
    1194                 :    7839955 :   if (!def)
    1195                 :            :     return;
    1196                 :            : 
    1197                 :            :   // Remove USE from the splay tree.
    1198                 :    7838678 :   if (def->m_use_tree && use->is_in_any_insn ())
    1199                 :            :     {
    1200                 :     350038 :       int comparison = lookup_use (def->m_use_tree, use->insn ());
    1201                 :     350038 :       gcc_checking_assert (comparison == 0);
    1202                 :     350038 :       def->m_use_tree.remove_root ();
    1203                 :            :     }
    1204                 :            : 
    1205                 :    7838678 :   use_info *prev = use->prev_use ();
    1206                 :    7838678 :   use_info *next = use->next_use ();
    1207                 :            : 
    1208                 :    7838678 :   use_info *first = def->first_use ();
    1209                 :    7838678 :   use_info *last = first->last_use ();
    1210                 :    7838678 :   if (last->last_nondebug_insn_use () == use)
    1211                 :    1983971 :     last->set_last_nondebug_insn_use (prev);
    1212                 :            : 
    1213                 :    7838678 :   if (next)
    1214                 :    2627954 :     next->copy_prev_from (use);
    1215                 :            :   else
    1216                 :    5210724 :     first->set_last_use (prev);
    1217                 :            : 
    1218                 :    7838678 :   if (prev)
    1219                 :    4296159 :     prev->copy_next_from (use);
    1220                 :            :   else
    1221                 :    3542519 :     def->set_first_use (next);
    1222                 :            : 
    1223                 :    7838678 :   use->clear_use_links ();
    1224                 :    7838678 :   gcc_checking_assert ((!prev || prev->check_integrity ())
    1225                 :            :                        && (!next || next->check_integrity ()));
    1226                 :            : }
    1227                 :            : 
    1228                 :            : // Allocate a temporary clobber_info for register REGNO in insn INSN,
    1229                 :            : // including it in the region of the obstack governed by WATERMARK.
    1230                 :            : // Return a new def_array that contains OLD_DEFS and the new clobber.
    1231                 :            : //
    1232                 :            : // OLD_DEFS is known not to define REGNO.
    1233                 :            : def_array
    1234                 :          0 : function_info::insert_temp_clobber (obstack_watermark &watermark,
    1235                 :            :                                     insn_info *insn, unsigned int regno,
    1236                 :            :                                     def_array old_defs)
    1237                 :            : {
    1238                 :          0 :   gcc_checking_assert (watermark == &m_temp_obstack);
    1239                 :          0 :   auto *clobber = allocate_temp<clobber_info> (insn, regno);
    1240                 :          0 :   clobber->m_is_temp = true;
    1241                 :          0 :   return insert_access (watermark, clobber, old_defs);
    1242                 :            : }
    1243                 :            : 
    1244                 :            : // A subroutine of make_uses_available.  Try to make USE's definition
    1245                 :            : // available at the head of BB.  WILL_BE_DEBUG_USE is true if the
    1246                 :            : // definition will be used only in debug instructions.
    1247                 :            : //
    1248                 :            : // On success:
    1249                 :            : //
    1250                 :            : // - If the use would have the same def () as USE, return USE.
    1251                 :            : //
    1252                 :            : // - If BB already has a degenerate phi for the same definition,
    1253                 :            : //   return a temporary use of that phi.
    1254                 :            : //
    1255                 :            : // - Otherwise, the use would need a new degenerate phi.  Allocate a
    1256                 :            : //   temporary phi and return a temporary use of it.
    1257                 :            : //
    1258                 :            : // Return null on failure.
    1259                 :            : use_info *
    1260                 :    8312176 : function_info::make_use_available (use_info *use, bb_info *bb,
    1261                 :            :                                    bool will_be_debug_use)
    1262                 :            : {
    1263                 :    8312176 :   set_info *def = use->def ();
    1264                 :    8312176 :   if (!def)
    1265                 :            :     return use;
    1266                 :            : 
    1267                 :    8312176 :   if (is_single_dominating_def (def))
    1268                 :            :     return use;
    1269                 :            : 
    1270                 :            :   // FIXME: Deliberately limited for fwprop compatibility testing.
    1271                 :    3492477 :   basic_block cfg_bb = bb->cfg_bb ();
    1272                 :    3492477 :   bb_info *use_bb = use->bb ();
    1273                 :    3492477 :   if (single_pred_p (cfg_bb)
    1274                 :    2889257 :       && single_pred (cfg_bb) == use_bb->cfg_bb ()
    1275                 :    5043787 :       && remains_available_on_exit (def, use_bb))
    1276                 :            :     {
    1277                 :    1288231 :       if (def->ebb () == bb->ebb () || will_be_debug_use)
    1278                 :            :         return use;
    1279                 :            : 
    1280                 :     196933 :       resource_info resource = use->resource ();
    1281                 :     196933 :       set_info *ultimate_def = look_through_degenerate_phi (def);
    1282                 :            : 
    1283                 :            :       // See if there is already a (degenerate) phi for DEF.
    1284                 :     196933 :       insn_info *phi_insn = bb->ebb ()->phi_insn ();
    1285                 :     196933 :       phi_info *phi;
    1286                 :     196933 :       def_lookup dl = find_def (resource, phi_insn);
    1287                 :     196933 :       if (set_info *set = dl.matching_set ())
    1288                 :            :         {
    1289                 :            :           // There is an existing phi.
    1290                 :     104758 :           phi = as_a<phi_info *> (set);
    1291                 :     104758 :           gcc_checking_assert (phi->input_value (0) == ultimate_def);
    1292                 :            :         }
    1293                 :            :       else
    1294                 :            :         {
    1295                 :            :           // Create a temporary placeholder phi.  This will become
    1296                 :            :           // permanent if the change is later committed.
    1297                 :      92175 :           phi = allocate_temp<phi_info> (phi_insn, resource, 0);
    1298                 :      92175 :           auto *input = allocate_temp<use_info> (phi, resource, ultimate_def);
    1299                 :      92175 :           input->m_is_temp = true;
    1300                 :      92175 :           phi->m_is_temp = true;
    1301                 :      92175 :           phi->make_degenerate (input);
    1302                 :      92175 :           if (def_info *prev = dl.prev_def ())
    1303                 :      92175 :             phi->set_prev_def (prev);
    1304                 :      92175 :           if (def_info *next = dl.next_def ())
    1305                 :      85374 :             phi->set_next_def (next);
    1306                 :            :         }
    1307                 :            : 
    1308                 :            :       // Create a temporary use of the phi at the head of the first
    1309                 :            :       // block, since we know for sure that it's available there.
    1310                 :     196933 :       insn_info *use_insn = bb->ebb ()->first_bb ()->head_insn ();
    1311                 :     196933 :       auto *new_use = allocate_temp<use_info> (use_insn, resource, phi);
    1312                 :     196933 :       new_use->m_is_temp = true;
    1313                 :     196933 :       return new_use;
    1314                 :            :     }
    1315                 :            :   return nullptr;
    1316                 :            : }
    1317                 :            : 
    1318                 :            : // See the comment above the declaration.
    1319                 :            : use_array
    1320                 :    5385275 : function_info::make_uses_available (obstack_watermark &watermark,
    1321                 :            :                                     use_array uses, bb_info *bb,
    1322                 :            :                                     bool will_be_debug_uses)
    1323                 :            : {
    1324                 :    5385275 :   unsigned int num_uses = uses.size ();
    1325                 :    5385275 :   if (num_uses == 0)
    1326                 :     269446 :     return uses;
    1327                 :            : 
    1328                 :    5115829 :   auto **new_uses = XOBNEWVEC (watermark, access_info *, num_uses);
    1329                 :   11223759 :   for (unsigned int i = 0; i < num_uses; ++i)
    1330                 :            :     {
    1331                 :    8312176 :       use_info *use = make_use_available (uses[i], bb, will_be_debug_uses);
    1332                 :    8312176 :       if (!use)
    1333                 :    2204246 :         return use_array (access_array::invalid ());
    1334                 :    6107930 :       new_uses[i] = use;
    1335                 :            :     }
    1336                 :    2911583 :   return use_array (new_uses, num_uses);
    1337                 :            : }
    1338                 :            : 
    1339                 :            : // Return true if ACCESS1 can represent ACCESS2 and if ACCESS2 can
    1340                 :            : // represent ACCESS1.
    1341                 :            : static bool
    1342                 :    4272599 : can_merge_accesses (access_info *access1, access_info *access2)
    1343                 :            : {
    1344                 :    4272599 :   if (access1 == access2)
    1345                 :            :     return true;
    1346                 :            : 
    1347                 :    4272599 :   auto *use1 = dyn_cast<use_info *> (access1);
    1348                 :    4272599 :   auto *use2 = dyn_cast<use_info *> (access2);
    1349                 :    4272599 :   return use1 && use2 && use1->def () == use2->def ();
    1350                 :            : }
    1351                 :            : 
    1352                 :            : // See the comment above the declaration.
    1353                 :            : access_array
    1354                 :   24376925 : rtl_ssa::merge_access_arrays_base (obstack_watermark &watermark,
    1355                 :            :                                    access_array accesses1,
    1356                 :            :                                    access_array accesses2)
    1357                 :            : {
    1358                 :   24376925 :   if (accesses1.empty ())
    1359                 :          0 :     return accesses2;
    1360                 :   24376925 :   if (accesses2.empty ())
    1361                 :    3360856 :     return accesses1;
    1362                 :            : 
    1363                 :   21016069 :   auto i1 = accesses1.begin ();
    1364                 :   21016069 :   auto end1 = accesses1.end ();
    1365                 :   21016069 :   auto i2 = accesses2.begin ();
    1366                 :   21016069 :   auto end2 = accesses2.end ();
    1367                 :            : 
    1368                 :   21016069 :   access_array_builder builder (watermark);
    1369                 :   21016069 :   builder.reserve (accesses1.size () + accesses2.size ());
    1370                 :            : 
    1371                 :   83970413 :   while (i1 != end1 && i2 != end2)
    1372                 :            :     {
    1373                 :   43236814 :       access_info *access1 = *i1;
    1374                 :   43236814 :       access_info *access2 = *i2;
    1375                 :            : 
    1376                 :   43236814 :       unsigned int regno1 = access1->regno ();
    1377                 :   43236814 :       unsigned int regno2 = access2->regno ();
    1378                 :   43236814 :       if (regno1 == regno2)
    1379                 :            :         {
    1380                 :    4272599 :           if (!can_merge_accesses (access1, access2))
    1381                 :    1298539 :             return access_array::invalid ();
    1382                 :            : 
    1383                 :    2974060 :           builder.quick_push (access1);
    1384                 :    2974060 :           ++i1;
    1385                 :    2974060 :           ++i2;
    1386                 :            :         }
    1387                 :   38964215 :       else if (regno1 < regno2)
    1388                 :            :         {
    1389                 :   23570258 :           builder.quick_push (access1);
    1390                 :   23570258 :           ++i1;
    1391                 :            :         }
    1392                 :            :       else
    1393                 :            :         {
    1394                 :   15393957 :           builder.quick_push (access2);
    1395                 :   15393957 :           ++i2;
    1396                 :            :         }
    1397                 :            :     }
    1398                 :   31842902 :   for (; i1 != end1; ++i1)
    1399                 :   12125372 :     builder.quick_push (*i1);
    1400                 :   31081713 :   for (; i2 != end2; ++i2)
    1401                 :   11364183 :     builder.quick_push (*i2);
    1402                 :            : 
    1403                 :   19717530 :   return builder.finish ();
    1404                 :   24376925 : }
    1405                 :            : 
    1406                 :            : // See the comment above the declaration.
    1407                 :            : access_array
    1408                 :          0 : rtl_ssa::insert_access_base (obstack_watermark &watermark,
    1409                 :            :                              access_info *access1, access_array accesses2)
    1410                 :            : {
    1411                 :          0 :   access_array_builder builder (watermark);
    1412                 :          0 :   builder.reserve (1 + accesses2.size ());
    1413                 :            : 
    1414                 :          0 :   unsigned int regno1 = access1->regno ();
    1415                 :          0 :   auto i2 = accesses2.begin ();
    1416                 :          0 :   auto end2 = accesses2.end ();
    1417                 :          0 :   while (i2 != end2)
    1418                 :            :     {
    1419                 :          0 :       access_info *access2 = *i2;
    1420                 :            : 
    1421                 :          0 :       unsigned int regno2 = access2->regno ();
    1422                 :          0 :       if (regno1 == regno2)
    1423                 :            :         {
    1424                 :          0 :           if (!can_merge_accesses (access1, access2))
    1425                 :          0 :             return access_array::invalid ();
    1426                 :            : 
    1427                 :          0 :           builder.quick_push (access1);
    1428                 :          0 :           access1 = nullptr;
    1429                 :          0 :           ++i2;
    1430                 :          0 :           break;
    1431                 :            :         }
    1432                 :          0 :       else if (regno1 < regno2)
    1433                 :            :         {
    1434                 :          0 :           builder.quick_push (access1);
    1435                 :          0 :           access1 = nullptr;
    1436                 :          0 :           break;
    1437                 :            :         }
    1438                 :            :       else
    1439                 :            :         {
    1440                 :          0 :           builder.quick_push (access2);
    1441                 :          0 :           ++i2;
    1442                 :            :         }
    1443                 :            :     }
    1444                 :          0 :   if (access1)
    1445                 :          0 :     builder.quick_push (access1);
    1446                 :          0 :   for (; i2 != end2; ++i2)
    1447                 :          0 :     builder.quick_push (*i2);
    1448                 :            : 
    1449                 :          0 :   return builder.finish ();
    1450                 :          0 : }
    1451                 :            : 
    1452                 :            : // See the comment above the declaration.
    1453                 :            : access_array
    1454                 :   34388125 : rtl_ssa::remove_note_accesses_base (obstack_watermark &watermark,
    1455                 :            :                                     access_array accesses)
    1456                 :            : {
    1457                 :   77386642 :   for (access_info *access : accesses)
    1458                 :   43547893 :     if (access->only_occurs_in_notes ())
    1459                 :            :       {
    1460                 :     549376 :         access_array_builder builder (watermark);
    1461                 :     549376 :         builder.reserve (accesses.size ());
    1462                 :    2040747 :         for (access_info *access2 : accesses)
    1463                 :    1491371 :           if (!access2->only_occurs_in_notes ())
    1464                 :    1491371 :             builder.quick_push (access2);
    1465                 :     549376 :         return builder.finish ();
    1466                 :     549376 :       }
    1467                 :   33838749 :   return accesses;
    1468                 :            : }
    1469                 :            : 
    1470                 :            : // Print RESOURCE to PP.
    1471                 :            : void
    1472                 :          0 : rtl_ssa::pp_resource (pretty_printer *pp, resource_info resource)
    1473                 :            : {
    1474                 :          0 :   resource.print (pp);
    1475                 :          0 : }
    1476                 :            : 
    1477                 :            : // Print ACCESS to PP.  FLAGS is a bitmask of PP_ACCESS_* flags.
    1478                 :            : void
    1479                 :          0 : rtl_ssa::pp_access (pretty_printer *pp, const access_info *access,
    1480                 :            :                     unsigned int flags)
    1481                 :            : {
    1482                 :          0 :   if (!access)
    1483                 :          0 :     pp_string (pp, "<null>");
    1484                 :          0 :   else if (auto *phi = dyn_cast<const phi_info *> (access))
    1485                 :          0 :     phi->print (pp, flags);
    1486                 :          0 :   else if (auto *set = dyn_cast<const set_info *> (access))
    1487                 :          0 :     set->print (pp, flags);
    1488                 :          0 :   else if (auto *clobber = dyn_cast<const clobber_info *> (access))
    1489                 :          0 :     clobber->print (pp, flags);
    1490                 :          0 :   else if (auto *use = dyn_cast<const use_info *> (access))
    1491                 :          0 :     use->print (pp, flags);
    1492                 :            :   else
    1493                 :          0 :     pp_string (pp, "??? Unknown access");
    1494                 :          0 : }
    1495                 :            : 
    1496                 :            : // Print ACCESSES to PP.  FLAGS is a bitmask of PP_ACCESS_* flags.
    1497                 :            : void
    1498                 :          0 : rtl_ssa::pp_accesses (pretty_printer *pp, access_array accesses,
    1499                 :            :                       unsigned int flags)
    1500                 :            : {
    1501                 :          0 :   if (accesses.empty ())
    1502                 :          0 :     pp_string (pp, "none");
    1503                 :            :   else
    1504                 :            :     {
    1505                 :          0 :       bool is_first = true;
    1506                 :          0 :       for (access_info *access : accesses)
    1507                 :            :         {
    1508                 :          0 :           if (is_first)
    1509                 :            :             is_first = false;
    1510                 :            :           else
    1511                 :          0 :             pp_newline_and_indent (pp, 0);
    1512                 :          0 :           pp_access (pp, access, flags);
    1513                 :            :         }
    1514                 :            :     }
    1515                 :          0 : }
    1516                 :            : 
    1517                 :            : // Print NODE to PP.
    1518                 :            : void
    1519                 :          0 : rtl_ssa::pp_def_node (pretty_printer *pp, const def_node *node)
    1520                 :            : {
    1521                 :          0 :   if (!node)
    1522                 :          0 :     pp_string (pp, "<null>");
    1523                 :          0 :   else if (auto *group = dyn_cast<const clobber_group *> (node))
    1524                 :          0 :     group->print (pp);
    1525                 :          0 :   else if (auto *set = dyn_cast<const set_node *> (node))
    1526                 :          0 :     set->print (pp);
    1527                 :            :   else
    1528                 :          0 :     pp_string (pp, "??? Unknown def node");
    1529                 :          0 : }
    1530                 :            : 
    1531                 :            : // Print MUX to PP.
    1532                 :            : void
    1533                 :          0 : rtl_ssa::pp_def_mux (pretty_printer *pp, def_mux mux)
    1534                 :            : {
    1535                 :          0 :   if (auto *node = mux.dyn_cast<def_node *> ())
    1536                 :          0 :     pp_def_node (pp, node);
    1537                 :            :   else
    1538                 :          0 :     pp_access (pp, mux.as_a<def_info *> ());
    1539                 :          0 : }
    1540                 :            : 
    1541                 :            : // Print DL to PP.
    1542                 :            : void
    1543                 :          0 : rtl_ssa::pp_def_lookup (pretty_printer *pp, def_lookup dl)
    1544                 :            : {
    1545                 :          0 :   pp_string (pp, "comparison result of ");
    1546                 :          0 :   pp_decimal_int (pp, dl.comparison);
    1547                 :          0 :   pp_string (pp, " for ");
    1548                 :          0 :   pp_newline_and_indent (pp, 0);
    1549                 :          0 :   pp_def_mux (pp, dl.mux);
    1550                 :          0 : }
    1551                 :            : 
    1552                 :            : // Dump RESOURCE to FILE.
    1553                 :            : void
    1554                 :          0 : dump (FILE *file, resource_info resource)
    1555                 :            : {
    1556                 :          0 :   dump_using (file, pp_resource, resource);
    1557                 :          0 : }
    1558                 :            : 
    1559                 :            : // Dump ACCESS to FILE.  FLAGS is a bitmask of PP_ACCESS_* flags.
    1560                 :            : void
    1561                 :          0 : dump (FILE *file, const access_info *access, unsigned int flags)
    1562                 :            : {
    1563                 :          0 :   dump_using (file, pp_access, access, flags);
    1564                 :          0 : }
    1565                 :            : 
    1566                 :            : // Dump ACCESSES to FILE.  FLAGS is a bitmask of PP_ACCESS_* flags.
    1567                 :            : void
    1568                 :          0 : dump (FILE *file, access_array accesses, unsigned int flags)
    1569                 :            : {
    1570                 :          0 :   dump_using (file, pp_accesses, accesses, flags);
    1571                 :          0 : }
    1572                 :            : 
    1573                 :            : // Print NODE to FILE.
    1574                 :            : void
    1575                 :          0 : dump (FILE *file, const def_node *node)
    1576                 :            : {
    1577                 :          0 :   dump_using (file, pp_def_node, node);
    1578                 :          0 : }
    1579                 :            : 
    1580                 :            : // Print MUX to FILE.
    1581                 :            : void
    1582                 :          0 : dump (FILE *file, def_mux mux)
    1583                 :            : {
    1584                 :          0 :   dump_using (file, pp_def_mux, mux);
    1585                 :          0 : }
    1586                 :            : 
    1587                 :            : // Print RESULT to FILE.
    1588                 :            : void
    1589                 :          0 : dump (FILE *file, def_lookup result)
    1590                 :            : {
    1591                 :          0 :   dump_using (file, pp_def_lookup, result);
    1592                 :          0 : }
    1593                 :            : 
    1594                 :            : // Debug interfaces to the dump routines above.
    1595                 :          0 : void debug (const resource_info &x) { dump (stderr, x); }
    1596                 :          0 : void debug (const access_info *x) { dump (stderr, x); }
    1597                 :          0 : void debug (const access_array &x) { dump (stderr, x); }
    1598                 :          0 : void debug (const def_node *x) { dump (stderr, x); }
    1599                 :          0 : void debug (const def_mux &x) { dump (stderr, x); }
    1600                 :          0 : void debug (const def_lookup &x) { dump (stderr, x); }

Generated by: LCOV version 1.15+git.20200812.d100e6c

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.