LCOV - code coverage report
Current view: top level - gcc/rtl-ssa - accesses.cc (source / functions) Coverage Total Hit
Test: gcc.info Lines: 58.0 % 876 508
Test Date: 2024-03-23 14:05:01 Functions: 48.8 % 84 41
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-2024 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                 :   492977029 : use_info::check_integrity ()
     177                 :             : {
     178                 :  1511967565 :   auto subsequence_id = [](use_info *use)
     179                 :             :     {
     180                 :   509495268 :       if (use->is_in_nondebug_insn ())
     181                 :             :         return 1;
     182                 :   163861492 :       if (use->is_in_debug_insn ())
     183                 :    78642869 :         return 2;
     184                 :             :       return 3;
     185                 :             :     };
     186                 :             : 
     187                 :   492977029 :   use_info *prev = prev_use ();
     188                 :   492977029 :   use_info *next = next_use ();
     189                 :             : 
     190                 :   839831694 :   if (prev && subsequence_id (prev) > subsequence_id (this))
     191                 :             :     return false;
     192                 :   696930231 :   if (next && subsequence_id (next) < subsequence_id (this))
     193                 :             :     return false;
     194                 :   492977029 :   if (m_is_last_nondebug_insn_use != calculate_is_last_nondebug_insn_use ())
     195                 :             :     return false;
     196                 :             : 
     197                 :   492977029 :   if (!prev && last_use ()->next_use ())
     198                 :             :     return false;
     199                 :   492977029 :   if (!next)
     200                 :   302821929 :     if (use_info *use = last_nondebug_insn_use ())
     201                 :   278718761 :       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                 :             : clobber_info *
     398                 :           8 : clobber_group::prev_clobber (insn_info *insn) const
     399                 :             : {
     400                 :           8 :   auto &tree = const_cast<clobber_tree &> (m_clobber_tree);
     401                 :           8 :   int comparison = lookup_clobber (tree, insn);
     402                 :           8 :   if (comparison <= 0)
     403                 :          16 :     return dyn_cast<clobber_info *> (tree.root ()->prev_def ());
     404                 :           0 :   return tree.root ();
     405                 :             : }
     406                 :             : 
     407                 :             : // See the comment above the declaration.
     408                 :             : clobber_info *
     409                 :           8 : clobber_group::next_clobber (insn_info *insn) const
     410                 :             : {
     411                 :           8 :   auto &tree = const_cast<clobber_tree &> (m_clobber_tree);
     412                 :           8 :   int comparison = lookup_clobber (tree, insn);
     413                 :           8 :   if (comparison >= 0)
     414                 :          16 :     return dyn_cast<clobber_info *> (tree.root ()->next_def ());
     415                 :           0 :   return tree.root ();
     416                 :             : }
     417                 :             : 
     418                 :             : // See the comment above the declaration.
     419                 :             : void
     420                 :           0 : clobber_group::print (pretty_printer *pp) const
     421                 :             : {
     422                 :           0 :   auto print_clobber = [](pretty_printer *pp, const def_info *clobber)
     423                 :             :     {
     424                 :           0 :       pp_access (pp, clobber);
     425                 :             :     };
     426                 :           0 :   pp_string (pp, "grouped clobber");
     427                 :           0 :   for (const def_info *clobber : clobbers ())
     428                 :             :     {
     429                 :           0 :       pp_newline_and_indent (pp, 2);
     430                 :           0 :       print_clobber (pp, clobber);
     431                 :           0 :       pp_indentation (pp) -= 2;
     432                 :             :     }
     433                 :           0 :   pp_newline_and_indent (pp, 2);
     434                 :           0 :   pp_string (pp, "splay tree");
     435                 :           0 :   pp_newline_and_indent (pp, 2);
     436                 :           0 :   m_clobber_tree.print (pp, print_clobber);
     437                 :           0 :   pp_indentation (pp) -= 4;
     438                 :           0 : }
     439                 :             : 
     440                 :             : // See the comment above the declaration.
     441                 :             : def_info *
     442                 :      120966 : def_lookup::prev_def (insn_info *insn) const
     443                 :             : {
     444                 :      120966 :   if (mux && comparison == 0)
     445                 :           8 :     if (auto *node = mux.dyn_cast<def_node *> ())
     446                 :           8 :       if (auto *group = dyn_cast<clobber_group *> (node))
     447                 :           8 :         if (clobber_info *clobber = group->prev_clobber (insn))
     448                 :             :           return clobber;
     449                 :             : 
     450                 :      120958 :   return last_def_of_prev_group ();
     451                 :             : }
     452                 :             : 
     453                 :             : // See the comment above the declaration.
     454                 :             : def_info *
     455                 :      120966 : def_lookup::next_def (insn_info *insn) const
     456                 :             : {
     457                 :      120966 :   if (mux && comparison == 0)
     458                 :           8 :     if (auto *node = mux.dyn_cast<def_node *> ())
     459                 :           8 :       if (auto *group = dyn_cast<clobber_group *> (node))
     460                 :           8 :         if (clobber_info *clobber = group->next_clobber (insn))
     461                 :             :           return clobber;
     462                 :             : 
     463                 :      120958 :   return first_def_of_next_group ();
     464                 :             : }
     465                 :             : 
     466                 :             : // Return a clobber_group for CLOBBER, creating one if CLOBBER doesn't
     467                 :             : // already belong to a group.
     468                 :             : clobber_group *
     469                 :    30616521 : function_info::need_clobber_group (clobber_info *clobber)
     470                 :             : {
     471                 :    30616521 :   if (clobber->is_in_group ())
     472                 :    24563597 :     return clobber->group ();
     473                 :     6052924 :   return allocate<clobber_group> (clobber);
     474                 :             : }
     475                 :             : 
     476                 :             : // Return a def_node for inserting DEF into the associated resource's
     477                 :             : // splay tree.  Use a clobber_group if DEF is a clobber and a set_node
     478                 :             : // otherwise.
     479                 :             : def_node *
     480                 :    10474159 : function_info::need_def_node (def_info *def)
     481                 :             : {
     482                 :    10474159 :   if (auto *clobber = dyn_cast<clobber_info *> (def))
     483                 :     1809581 :     return need_clobber_group (clobber);
     484                 :     8664578 :   return allocate<set_node> (as_a<set_info *> (def));
     485                 :             : }
     486                 :             : 
     487                 :             : // LAST is the last thing to define LAST->resource (), and is where any
     488                 :             : // splay tree root for LAST->resource () is stored.  Require such a splay tree
     489                 :             : // to exist, creating a new one if necessary.  Return the root of the tree.
     490                 :             : //
     491                 :             : // The caller must call LAST->set_splay_root after it has finished with
     492                 :             : // the splay tree.
     493                 :             : def_splay_tree
     494                 :     1622338 : function_info::need_def_splay_tree (def_info *last)
     495                 :             : {
     496                 :     1622338 :   if (def_node *root = last->splay_root ())
     497                 :     1327832 :     return root;
     498                 :             : 
     499                 :             :   // Use a left-spine rooted at the last node.
     500                 :      294506 :   def_node *root = need_def_node (last);
     501                 :      294506 :   def_node *parent = root;
     502                 :    19096639 :   while (def_info *prev = first_def (parent)->prev_def ())
     503                 :             :     {
     504                 :    10140120 :       def_node *node = need_def_node (prev);
     505                 :    10140120 :       def_splay_tree::insert_child (parent, 0, node);
     506                 :    10140120 :       parent = node;
     507                 :    10140120 :     }
     508                 :      294506 :   return root;
     509                 :             : }
     510                 :             : 
     511                 :             : // Search TREE for either:
     512                 :             : //
     513                 :             : // - a set_info at INSN or
     514                 :             : // - a clobber_group whose range includes INSN
     515                 :             : //
     516                 :             : // If such a node exists, install it as the root of TREE and return 0.
     517                 :             : // Otherwise arbitrarily choose between:
     518                 :             : //
     519                 :             : // (1) Installing the closest preceding node as the root and returning 1.
     520                 :             : // (2) Installing the closest following node as the root and returning -1.
     521                 :             : //
     522                 :             : // Note that this routine should not be used to check whether INSN
     523                 :             : // itself defines a resource; that can be checked more cheaply using
     524                 :             : // find_access_index.
     525                 :             : int
     526                 :     1652937 : rtl_ssa::lookup_def (def_splay_tree &tree, insn_info *insn)
     527                 :             : {
     528                 :    16895162 :   auto go_left = [&](def_node *node)
     529                 :             :     {
     530                 :    26002499 :       return *insn < *first_def (node)->insn ();
     531                 :     1652937 :     };
     532                 :     5371179 :   auto go_right = [&](def_node *node)
     533                 :             :     {
     534                 :     7436484 :       return *insn > *last_def (node)->insn ();
     535                 :     1652937 :     };
     536                 :     1652937 :   return tree.lookup (go_left, go_right);
     537                 :             : }
     538                 :             : 
     539                 :             : // Search TREE for a clobber in INSN.  If such a clobber exists, install
     540                 :             : // it as the root of TREE and return 0.  Otherwise arbitrarily choose between:
     541                 :             : //
     542                 :             : // (1) Installing the closest preceding clobber as the root and returning 1.
     543                 :             : // (2) Installing the closest following clobber as the root and returning -1.
     544                 :             : int
     545                 :      149499 : rtl_ssa::lookup_clobber (clobber_tree &tree, insn_info *insn)
     546                 :             : {
     547                 :      694092 :   auto compare = [&](clobber_info *clobber)
     548                 :             :     {
     549                 :      544593 :       return insn->compare_with (clobber->insn ());
     550                 :      149499 :     };
     551                 :      149499 :   return tree.lookup (compare);
     552                 :             : }
     553                 :             : 
     554                 :             : // Search for a definition of RESOURCE at INSN and return the result of
     555                 :             : // the search as a def_lookup.  See the comment above the class for more
     556                 :             : // details.
     557                 :             : def_lookup
     558                 :     1841763 : function_info::find_def (resource_info resource, insn_info *insn)
     559                 :             : {
     560                 :     1841763 :   def_info *first = m_defs[resource.regno + 1];
     561                 :     1841763 :   if (!first)
     562                 :             :     // There are no nodes.  The comparison result is pretty meaningless
     563                 :             :     // in this case.
     564                 :         477 :     return { nullptr, -1 };
     565                 :             : 
     566                 :             :   // See whether the first node matches.
     567                 :     1841286 :   auto first_result = clobber_group_or_single_def (first);
     568                 :     1841286 :   if (*insn <= *last_def (first_result)->insn ())
     569                 :             :     {
     570                 :      155249 :       int comparison = (*insn >= *first->insn () ? 0 : -1);
     571                 :      155249 :       return { first_result, comparison };
     572                 :             :     }
     573                 :             : 
     574                 :             :   // See whether the last node matches.
     575                 :     1686037 :   def_info *last = first->last_def ();
     576                 :     1686037 :   auto last_result = clobber_group_or_single_def (last);
     577                 :     2599946 :   if (*insn >= *first_def (last_result)->insn ())
     578                 :             :     {
     579                 :      351407 :       int comparison = (*insn <= *last->insn () ? 0 : 1);
     580                 :      351407 :       return { last_result, comparison };
     581                 :             :     }
     582                 :             : 
     583                 :             :   // Resort to using a splay tree to search for the result.
     584                 :     1334630 :   def_splay_tree tree = need_def_splay_tree (last);
     585                 :     1334630 :   int comparison = lookup_def (tree, insn);
     586                 :     1334630 :   last->set_splay_root (tree.root ());
     587                 :     1334630 :   return { tree.root (), comparison };
     588                 :             : }
     589                 :             : 
     590                 :             : // Add DEF to the function's list of definitions of DEF->resource (),
     591                 :             : // inserting DEF immediately before BEFORE.  DEF is not currently in the list.
     592                 :             : void
     593                 :      162779 : function_info::insert_def_before (def_info *def, def_info *before)
     594                 :             : {
     595                 :      325558 :   gcc_checking_assert (!def->has_def_links ()
     596                 :             :                        && *before->insn () > *def->insn ());
     597                 :             : 
     598                 :      162779 :   def->copy_prev_from (before);
     599                 :      162779 :   if (def_info *prev = def->prev_def ())
     600                 :             :     {
     601                 :      147492 :       gcc_checking_assert (*prev->insn () < *def->insn ());
     602                 :      147492 :       prev->set_next_def (def);
     603                 :             :     }
     604                 :             :   else
     605                 :       15287 :     m_defs[def->regno () + 1] = def;
     606                 :             : 
     607                 :      162779 :   def->set_next_def (before);
     608                 :      162779 :   before->set_prev_def (def);
     609                 :      162779 : }
     610                 :             : 
     611                 :             : // Add DEF to the function's list of definitions of DEF->resource (),
     612                 :             : // inserting DEF immediately after AFTER.  DEF is not currently in the list.
     613                 :             : void
     614                 :    27317167 : function_info::insert_def_after (def_info *def, def_info *after)
     615                 :             : {
     616                 :    54634334 :   gcc_checking_assert (!def->has_def_links ()
     617                 :             :                        && *after->insn () < *def->insn ());
     618                 :             : 
     619                 :    27317167 :   def->copy_next_from (after);
     620                 :    27317167 :   if (def_info *next = def->next_def ())
     621                 :             :     {
     622                 :      140216 :       gcc_checking_assert (*next->insn () > *def->insn ());
     623                 :      140216 :       next->set_prev_def (def);
     624                 :             :     }
     625                 :             :   else
     626                 :    27176951 :     m_defs[def->regno () + 1]->set_last_def (def);
     627                 :             : 
     628                 :    27317167 :   def->set_prev_def (after);
     629                 :    27317167 :   after->set_next_def (def);
     630                 :    27317167 : }
     631                 :             : 
     632                 :             : // Remove DEF from the function's list of definitions of DEF->resource ().
     633                 :             : void
     634                 :     3671050 : function_info::remove_def_from_list (def_info *def)
     635                 :             : {
     636                 :     3671050 :   def_info *prev = def->prev_def ();
     637                 :     3671050 :   def_info *next = def->next_def ();
     638                 :             : 
     639                 :     3671050 :   if (next)
     640                 :     1641764 :     next->copy_prev_from (def);
     641                 :             :   else
     642                 :     2029286 :     m_defs[def->regno () + 1]->set_last_def (prev);
     643                 :             : 
     644                 :     3671050 :   if (prev)
     645                 :     3655758 :     prev->copy_next_from (def);
     646                 :             :   else
     647                 :       15292 :     m_defs[def->regno () + 1] = next;
     648                 :             : 
     649                 :     3671050 :   def->clear_def_links ();
     650                 :     3671050 : }
     651                 :             : 
     652                 :             : // Add CLOBBER to GROUP and insert it into the function's list of
     653                 :             : // accesses to CLOBBER->resource ().  CLOBBER is not currently part
     654                 :             : // of an active group and is not currently in the list.
     655                 :             : void
     656                 :      149483 : function_info::add_clobber (clobber_info *clobber, clobber_group *group)
     657                 :             : {
     658                 :             :   // Search for either the previous or next clobber in the group.
     659                 :             :   // The result is less than zero if CLOBBER should come before NEIGHBOR
     660                 :             :   // or greater than zero if CLOBBER should come after NEIGHBOR.
     661                 :      149483 :   int comparison = lookup_clobber (group->m_clobber_tree, clobber->insn ());
     662                 :      149483 :   gcc_checking_assert (comparison != 0);
     663                 :      149483 :   clobber_info *neighbor = group->m_clobber_tree.root ();
     664                 :             : 
     665                 :             :   // Since HEIGHBOR is now the root of the splay tree, its group needs
     666                 :             :   // to be up-to-date.
     667                 :      149483 :   neighbor->update_group (group);
     668                 :             : 
     669                 :             :   // If CLOBBER comes before NEIGHBOR, insert CLOBBER to NEIGHBOR's left,
     670                 :             :   // otherwise insert CLOBBER to NEIGHBOR's right.
     671                 :      149483 :   clobber_info::splay_tree::insert_child (neighbor, comparison > 0, clobber);
     672                 :      149483 :   clobber->set_group (group);
     673                 :             : 
     674                 :             :   // Insert the clobber into the function-wide list and update the
     675                 :             :   // bounds of the group.
     676                 :      149483 :   if (comparison > 0)
     677                 :             :     {
     678                 :        1991 :       insert_def_after (clobber, neighbor);
     679                 :        1991 :       if (neighbor == group->last_clobber ())
     680                 :           0 :         group->set_last_clobber (clobber);
     681                 :             :     }
     682                 :             :   else
     683                 :             :     {
     684                 :      147492 :       insert_def_before (clobber, neighbor);
     685                 :      147492 :       if (neighbor == group->first_clobber ())
     686                 :           0 :         group->set_first_clobber (clobber);
     687                 :             :     }
     688                 :      149483 : }
     689                 :             : 
     690                 :             : // Remove CLOBBER from GROUP, given that GROUP contains other clobbers too.
     691                 :             : // Also remove CLOBBER from the function's list of accesses to
     692                 :             : // CLOBBER->resource ().
     693                 :             : void
     694                 :      268910 : function_info::remove_clobber (clobber_info *clobber, clobber_group *group)
     695                 :             : {
     696                 :      268910 :   if (clobber == group->first_clobber ())
     697                 :             :     {
     698                 :      144480 :       auto *new_first = as_a<clobber_info *> (clobber->next_def ());
     699                 :       72240 :       group->set_first_clobber (new_first);
     700                 :       72240 :       new_first->update_group (group);
     701                 :             :     }
     702                 :      196670 :   else if (clobber == group->last_clobber ())
     703                 :             :     {
     704                 :       92464 :       auto *new_last = as_a<clobber_info *> (clobber->prev_def ());
     705                 :       46232 :       group->set_last_clobber (new_last);
     706                 :       46232 :       new_last->update_group (group);
     707                 :             :     }
     708                 :             : 
     709                 :      268910 :   clobber_info *replacement = clobber_info::splay_tree::remove_node (clobber);
     710                 :      268910 :   if (clobber == group->m_clobber_tree.root ())
     711                 :             :     {
     712                 :      116203 :       group->m_clobber_tree = replacement;
     713                 :      116203 :       replacement->update_group (group);
     714                 :             :     }
     715                 :      268910 :   clobber->set_group (nullptr);
     716                 :             : 
     717                 :      268910 :   remove_def_from_list (clobber);
     718                 :      268910 : }
     719                 :             : 
     720                 :             : // Add CLOBBER immediately before the first clobber in GROUP, given that
     721                 :             : // CLOBBER is not currently part of any group.
     722                 :             : void
     723                 :       71417 : function_info::prepend_clobber_to_group (clobber_info *clobber,
     724                 :             :                                          clobber_group *group)
     725                 :             : {
     726                 :       71417 :   clobber_info *next = group->first_clobber ();
     727                 :       71417 :   clobber_info::splay_tree::insert_child (next, 0, clobber);
     728                 :       71417 :   group->set_first_clobber (clobber);
     729                 :       71417 :   clobber->set_group (group);
     730                 :       71417 : }
     731                 :             : 
     732                 :             : // Add CLOBBER immediately after the last clobber in GROUP, given that
     733                 :             : // CLOBBER is not currently part of any group.
     734                 :             : void
     735                 :    28735523 : function_info::append_clobber_to_group (clobber_info *clobber,
     736                 :             :                                         clobber_group *group)
     737                 :             : {
     738                 :    28735523 :   clobber_info *prev = group->last_clobber ();
     739                 :    28735523 :   clobber_info::splay_tree::insert_child (prev, 1, clobber);
     740                 :    28735523 :   group->set_last_clobber (clobber);
     741                 :    28735523 :   clobber->set_group (group);
     742                 :    28735523 : }
     743                 :             : 
     744                 :             : // Put CLOBBER1 and CLOBBER2 into the same clobber_group, given that
     745                 :             : // CLOBBER1 occurs immediately before CLOBBER2 and that the two clobbers
     746                 :             : // are not currently in the same group.  LAST is the last definition of
     747                 :             : // the associated resource, and is where any splay tree is stored.
     748                 :             : void
     749                 :          20 : function_info::merge_clobber_groups (clobber_info *clobber1,
     750                 :             :                                      clobber_info *clobber2,
     751                 :             :                                      def_info *last)
     752                 :             : {
     753                 :          20 :   if (clobber1->is_in_group () && clobber2->is_in_group ())
     754                 :             :     {
     755                 :           0 :       clobber_group *group1 = clobber1->group ();
     756                 :           0 :       clobber_group *group2 = clobber2->group ();
     757                 :           0 :       gcc_checking_assert (clobber1 == group1->last_clobber ()
     758                 :             :                            && clobber2 == group2->first_clobber ());
     759                 :             : 
     760                 :           0 :       if (def_splay_tree tree = last->splay_root ())
     761                 :             :         {
     762                 :             :           // Remove GROUP2 from the splay tree.
     763                 :           0 :           int comparison = lookup_def (tree, clobber2->insn ());
     764                 :           0 :           gcc_checking_assert (comparison == 0);
     765                 :           0 :           tree.remove_root ();
     766                 :           0 :           last->set_splay_root (tree.root ());
     767                 :             :         }
     768                 :             : 
     769                 :             :       // Splice the trees together.
     770                 :           0 :       group1->m_clobber_tree.splice_next_tree (group2->m_clobber_tree);
     771                 :             : 
     772                 :             :       // Bring the two extremes of GROUP2 under GROUP1.  Any other
     773                 :             :       // clobbers in the group are updated lazily on demand.
     774                 :           0 :       clobber2->set_group (group1);
     775                 :           0 :       group2->last_clobber ()->set_group (group1);
     776                 :           0 :       group1->set_last_clobber (group2->last_clobber ());
     777                 :             : 
     778                 :             :       // Record that GROUP2 is no more.
     779                 :           0 :       group2->set_first_clobber (nullptr);
     780                 :           0 :       group2->set_last_clobber (nullptr);
     781                 :           0 :       group2->m_clobber_tree = nullptr;
     782                 :             :     }
     783                 :             :   else
     784                 :             :     {
     785                 :             :       // In this case there can be no active splay tree.
     786                 :          20 :       gcc_assert (!last->splay_root ());
     787                 :          20 :       if (clobber2->is_in_group ())
     788                 :           0 :         prepend_clobber_to_group (clobber1, clobber2->group ());
     789                 :             :       else
     790                 :          20 :         append_clobber_to_group (clobber2, need_clobber_group (clobber1));
     791                 :             :     }
     792                 :          20 : }
     793                 :             : 
     794                 :             : // GROUP spans INSN, and INSN now sets the resource that GROUP clobbers.
     795                 :             : // Split GROUP around INSN and return the clobber that comes immediately
     796                 :             : // before INSN.
     797                 :             : //
     798                 :             : // The resource that GROUP clobbers is known to have an associated
     799                 :             : // splay tree.
     800                 :             : clobber_info *
     801                 :           0 : function_info::split_clobber_group (clobber_group *group, insn_info *insn)
     802                 :             : {
     803                 :             :   // Search for either the previous or next clobber in the group.
     804                 :             :   // The result is less than zero if CLOBBER should come before NEIGHBOR
     805                 :             :   // or greater than zero if CLOBBER should come after NEIGHBOR.
     806                 :           0 :   clobber_tree &tree1 = group->m_clobber_tree;
     807                 :           0 :   int comparison = lookup_clobber (tree1, insn);
     808                 :           0 :   gcc_checking_assert (comparison != 0);
     809                 :           0 :   clobber_info *neighbor = tree1.root ();
     810                 :             : 
     811                 :           0 :   clobber_tree tree2;
     812                 :           0 :   clobber_info *prev;
     813                 :           0 :   clobber_info *next;
     814                 :           0 :   if (comparison > 0)
     815                 :             :     {
     816                 :             :       // NEIGHBOR is the last clobber in what will become the first group.
     817                 :           0 :       tree2 = tree1.split_after_root ();
     818                 :           0 :       prev = neighbor;
     819                 :           0 :       next = as_a<clobber_info *> (prev->next_def ());
     820                 :             :     }
     821                 :             :   else
     822                 :             :     {
     823                 :             :       // NEIGHBOR is the first clobber in what will become the second group.
     824                 :           0 :       tree2 = neighbor;
     825                 :           0 :       tree1 = tree2.split_before_root ();
     826                 :           0 :       next = neighbor;
     827                 :           0 :       prev = as_a<clobber_info *> (next->prev_def ());
     828                 :             :     }
     829                 :             : 
     830                 :             :   // Use GROUP to hold PREV and earlier clobbers.  Create a new group for
     831                 :             :   // NEXT onwards.
     832                 :           0 :   clobber_info *last_clobber = group->last_clobber ();
     833                 :           0 :   clobber_group *group1 = group;
     834                 :           0 :   clobber_group *group2 = allocate<clobber_group> (next);
     835                 :             : 
     836                 :             :   // Finish setting up GROUP1, making sure that the roots and extremities
     837                 :             :   // have a correct group pointer.  Leave the rest to be updated lazily.
     838                 :           0 :   group1->set_last_clobber (prev);
     839                 :           0 :   tree1->set_group (group1);
     840                 :           0 :   prev->set_group (group1);
     841                 :             : 
     842                 :             :   // Finish setting up GROUP2, with the same approach as for GROUP1.
     843                 :           0 :   group2->set_first_clobber (next);
     844                 :           0 :   group2->set_last_clobber (last_clobber);
     845                 :           0 :   next->set_group (group2);
     846                 :           0 :   tree2->set_group (group2);
     847                 :           0 :   last_clobber->set_group (group2);
     848                 :             : 
     849                 :             :   // Insert GROUP2 into the splay tree as an immediate successor of GROUP1.
     850                 :           0 :   def_splay_tree::insert_child (group1, 1, group2);
     851                 :             : 
     852                 :           0 :   return prev;
     853                 :             : }
     854                 :             : 
     855                 :             : // Add DEF to the end of the function's list of definitions of
     856                 :             : // DEF->resource ().  There is known to be no associated splay tree yet.
     857                 :             : void
     858                 :   166270617 : function_info::append_def (def_info *def)
     859                 :             : {
     860                 :   166270617 :   gcc_checking_assert (!def->has_def_links ());
     861                 :   166270617 :   def_info **head = &m_defs[def->regno () + 1];
     862                 :   166270617 :   def_info *first = *head;
     863                 :   166270617 :   if (!first)
     864                 :             :     {
     865                 :             :       // This is the only definition of the resource.
     866                 :    68487216 :       def->set_last_def (def);
     867                 :    68487216 :       *head = def;
     868                 :    68487216 :       return;
     869                 :             :     }
     870                 :             : 
     871                 :    97783401 :   def_info *prev = first->last_def ();
     872                 :    97783401 :   gcc_checking_assert (!prev->splay_root ());
     873                 :             : 
     874                 :             :   // Maintain the invariant that two clobbers must not appear in
     875                 :             :   // neighboring nodes of the splay tree.
     876                 :    97783401 :   auto *clobber = dyn_cast<clobber_info *> (def);
     877                 :    97783401 :   auto *prev_clobber = dyn_cast<clobber_info *> (prev);
     878                 :    97783401 :   if (clobber && prev_clobber)
     879                 :    28691892 :     append_clobber_to_group (clobber, need_clobber_group (prev_clobber));
     880                 :             : 
     881                 :    97783401 :   prev->set_next_def (def);
     882                 :    97783401 :   def->set_prev_def (prev);
     883                 :    97783401 :   first->set_last_def (def);
     884                 :             : }
     885                 :             : 
     886                 :             : // Add DEF to the function's list of definitions of DEF->resource ().
     887                 :             : // Also insert it into the associated splay tree, if there is one.
     888                 :             : // DEF is not currently part of the list and is not in the splay tree.
     889                 :             : void
     890                 :    27483490 : function_info::add_def (def_info *def)
     891                 :             : {
     892                 :    54966980 :   gcc_checking_assert (!def->has_def_links ()
     893                 :             :                        && !def->m_is_temp
     894                 :             :                        && !def->m_has_been_superceded);
     895                 :    27483490 :   def_info **head = &m_defs[def->regno () + 1];
     896                 :    27483490 :   def_info *first = *head;
     897                 :    27483490 :   if (!first)
     898                 :             :     {
     899                 :             :       // This is the only definition of the resource.
     900                 :        3544 :       def->set_last_def (def);
     901                 :        3544 :       *head = def;
     902                 :        3544 :       return;
     903                 :             :     }
     904                 :             : 
     905                 :    27479946 :   def_info *last = first->last_def ();
     906                 :    27479946 :   insn_info *insn = def->insn ();
     907                 :             : 
     908                 :    27479946 :   int comparison;
     909                 :    27479946 :   def_node *root = nullptr;
     910                 :    27479946 :   def_info *prev = nullptr;
     911                 :    27479946 :   def_info *next = nullptr;
     912                 :    27479946 :   if (*insn > *last->insn ())
     913                 :             :     {
     914                 :             :       // This definition comes after all other definitions.
     915                 :    27176951 :       comparison = 1;
     916                 :    27176951 :       if (def_splay_tree tree = last->splay_root ())
     917                 :             :         {
     918                 :        2490 :           tree.splay_max_node ();
     919                 :        2490 :           root = tree.root ();
     920                 :        2490 :           last->set_splay_root (root);
     921                 :             :         }
     922                 :    27176951 :       prev = last;
     923                 :             :     }
     924                 :      302995 :   else if (*insn < *first->insn ())
     925                 :             :     {
     926                 :             :       // This definition comes before all other definitions.
     927                 :       15287 :       comparison = -1;
     928                 :       15287 :       if (def_splay_tree tree = last->splay_root ())
     929                 :             :         {
     930                 :        1206 :           tree.splay_min_node ();
     931                 :        1206 :           root = tree.root ();
     932                 :        1206 :           last->set_splay_root (root);
     933                 :             :         }
     934                 :       15287 :       next = first;
     935                 :             :     }
     936                 :             :   else
     937                 :             :     {
     938                 :             :       // Search the splay tree for an insertion point.
     939                 :      287708 :       def_splay_tree tree = need_def_splay_tree (last);
     940                 :      287708 :       comparison = lookup_def (tree, insn);
     941                 :      287708 :       root = tree.root ();
     942                 :      287708 :       last->set_splay_root (root);
     943                 :             : 
     944                 :             :       // Deal with cases in which we found an overlapping live range.
     945                 :      287708 :       if (comparison == 0)
     946                 :             :         {
     947                 :      149483 :           auto *group = as_a<clobber_group *> (tree.root ());
     948                 :      149483 :           if (auto *clobber = dyn_cast<clobber_info *> (def))
     949                 :             :             {
     950                 :      149483 :               add_clobber (clobber, group);
     951                 :      149483 :               return;
     952                 :             :             }
     953                 :           0 :           prev = split_clobber_group (group, insn);
     954                 :      138225 :           next = prev->next_def ();
     955                 :             :         }
     956                 :             :       // COMPARISON is < 0 if DEF comes before ROOT or > 0 if DEF comes
     957                 :             :       // after ROOT.
     958                 :      138225 :       else if (comparison < 0)
     959                 :             :         {
     960                 :       79441 :           next = first_def (root);
     961                 :       79441 :           prev = next->prev_def ();
     962                 :             :         }
     963                 :             :       else
     964                 :             :         {
     965                 :       58784 :           prev = last_def (root);
     966                 :      197009 :           next = prev->next_def ();
     967                 :             :         }
     968                 :             :     }
     969                 :             : 
     970                 :             :   // See if we should merge CLOBBER with a neighboring clobber.
     971                 :    27330463 :   auto *clobber = dyn_cast<clobber_info *> (def);
     972                 :    27330463 :   auto *prev_clobber = safe_dyn_cast<clobber_info *> (prev);
     973                 :    27330463 :   auto *next_clobber = safe_dyn_cast<clobber_info *> (next);
     974                 :             :   // We shouldn't have consecutive clobber_groups.
     975                 :    27330463 :   gcc_checking_assert (!(clobber && prev_clobber && next_clobber));
     976                 :    27330463 :   if (clobber && prev_clobber)
     977                 :       43611 :     append_clobber_to_group (clobber, need_clobber_group (prev_clobber));
     978                 :    27286852 :   else if (clobber && next_clobber)
     979                 :       71417 :     prepend_clobber_to_group (clobber, need_clobber_group (next_clobber));
     980                 :    27215435 :   else if (root)
     981                 :             :     {
     982                 :             :       // If DEF comes before ROOT, insert DEF to ROOT's left,
     983                 :             :       // otherwise insert DEF to ROOT's right.
     984                 :       39533 :       def_node *node = need_def_node (def);
     985                 :       39533 :       def_splay_tree::insert_child (root, comparison >= 0, node);
     986                 :             :     }
     987                 :    27330463 :   if (prev)
     988                 :    27315176 :     insert_def_after (def, prev);
     989                 :             :   else
     990                 :       15287 :     insert_def_before (def, next);
     991                 :             : }
     992                 :             : 
     993                 :             : // Remove DEF from the function's list of definitions of DEF->resource ().
     994                 :             : // Also remove DEF from the associated splay tree, if there is one.
     995                 :             : void
     996                 :     3674580 : function_info::remove_def (def_info *def)
     997                 :             : {
     998                 :     3674580 :   def_info **head = &m_defs[def->regno () + 1];
     999                 :     3674580 :   def_info *first = *head;
    1000                 :     3674580 :   gcc_checking_assert (first);
    1001                 :     3674580 :   if (first->is_last_def ())
    1002                 :             :     {
    1003                 :             :       // DEF is the only definition of the resource.
    1004                 :        3530 :       gcc_checking_assert (first == def);
    1005                 :        3530 :       *head = nullptr;
    1006                 :        3530 :       def->clear_def_links ();
    1007                 :        3530 :       return;
    1008                 :             :     }
    1009                 :             : 
    1010                 :             :   // If CLOBBER belongs to a clobber_group that contains other clobbers
    1011                 :             :   // too, then we need to update the clobber_group and the list, but any
    1012                 :             :   // splay tree that contains the clobber_group is unaffected.
    1013                 :     3671050 :   if (auto *clobber = dyn_cast<clobber_info *> (def))
    1014                 :      349992 :     if (clobber->is_in_group ())
    1015                 :             :       {
    1016                 :      299549 :         clobber_group *group = clobber->group ();
    1017                 :      299549 :         if (group->first_clobber () != group->last_clobber ())
    1018                 :             :           {
    1019                 :      268910 :             remove_clobber (clobber, group);
    1020                 :      268910 :             return;
    1021                 :             :           }
    1022                 :             :       }
    1023                 :             : 
    1024                 :             :   // If we've created a splay tree for this resource, remove the entry
    1025                 :             :   // for DEF.
    1026                 :     3402140 :   def_info *last = first->last_def ();
    1027                 :     3402140 :   if (def_splay_tree tree = last->splay_root ())
    1028                 :             :     {
    1029                 :       30599 :       int comparison = lookup_def (tree, def->insn ());
    1030                 :       30599 :       gcc_checking_assert (comparison == 0);
    1031                 :       30599 :       tree.remove_root ();
    1032                 :       30599 :       last->set_splay_root (tree.root ());
    1033                 :             :     }
    1034                 :             : 
    1035                 :             :   // If the definition came between two clobbers, merge them into a single
    1036                 :             :   // group.
    1037                 :     3402140 :   auto *prev_clobber = safe_dyn_cast<clobber_info *> (def->prev_def ());
    1038                 :     3402140 :   auto *next_clobber = safe_dyn_cast<clobber_info *> (def->next_def ());
    1039                 :     3402140 :   if (prev_clobber && next_clobber)
    1040                 :          20 :     merge_clobber_groups (prev_clobber, next_clobber, last);
    1041                 :             : 
    1042                 :     3402140 :   remove_def_from_list (def);
    1043                 :             : }
    1044                 :             : 
    1045                 :             : // Require DEF to have a splay tree that contains all non-phi uses.
    1046                 :             : void
    1047                 :     1236620 : function_info::need_use_splay_tree (set_info *def)
    1048                 :             : {
    1049                 :     1236620 :   if (!def->m_use_tree)
    1050                 :     9866542 :     for (use_info *use : def->all_insn_uses ())
    1051                 :             :       {
    1052                 :     8920460 :         auto *use_node = allocate<splay_tree_node<use_info *>> (use);
    1053                 :     8920460 :         def->m_use_tree.insert_max_node (use_node);
    1054                 :             :       }
    1055                 :     1236620 : }
    1056                 :             : 
    1057                 :             : // Compare two instructions by their position in a use splay tree.  Return >0
    1058                 :             : // if INSN1 comes after INSN2, <0 if INSN1 comes before INSN2, or 0 if they are
    1059                 :             : // the same instruction.
    1060                 :             : static inline int
    1061                 :   322916577 : compare_use_insns (insn_info *insn1, insn_info *insn2)
    1062                 :             : {
    1063                 :             :   // Debug instructions go after nondebug instructions.
    1064                 :   322916577 :   int diff = insn1->is_debug_insn () - insn2->is_debug_insn ();
    1065                 :   322916577 :   if (diff != 0)
    1066                 :             :     return diff;
    1067                 :   304082063 :   return insn1->compare_with (insn2);
    1068                 :             : }
    1069                 :             : 
    1070                 :             : // Search TREE for a use in INSN.  If such a use exists, install it as
    1071                 :             : // the root of TREE and return 0.  Otherwise arbitrarily choose between:
    1072                 :             : //
    1073                 :             : // (1) Installing the closest preceding use as the root and returning 1.
    1074                 :             : // (2) Installing the closest following use as the root and returning -1.
    1075                 :             : int
    1076                 :     1612925 : rtl_ssa::lookup_use (splay_tree<use_info *> &tree, insn_info *insn)
    1077                 :             : {
    1078                 :    13879914 :   auto compare = [&](splay_tree_node<use_info *> *node)
    1079                 :             :     {
    1080                 :    12266989 :       return compare_use_insns (insn, node->value ()->insn ());
    1081                 :     1612925 :     };
    1082                 :     1612925 :   return tree.lookup (compare);
    1083                 :             : }
    1084                 :             : 
    1085                 :             : // Add USE to USE->def ()'s list of uses. inserting USE immediately before
    1086                 :             : // BEFORE.  USE is not currently in the list.
    1087                 :             : //
    1088                 :             : // This routine should not be used for inserting phi uses.
    1089                 :             : void
    1090                 :     5357068 : function_info::insert_use_before (use_info *use, use_info *before)
    1091                 :             : {
    1092                 :    10714136 :   gcc_checking_assert (!use->has_use_links () && use->is_in_any_insn ());
    1093                 :             : 
    1094                 :     5357068 :   set_info *def = use->def ();
    1095                 :             : 
    1096                 :     5357068 :   use->copy_prev_from (before);
    1097                 :     5357068 :   use->set_next_use (before);
    1098                 :             : 
    1099                 :     5357068 :   if (use_info *prev = use->prev_use ())
    1100                 :      371330 :     prev->set_next_use (use);
    1101                 :             :   else
    1102                 :     4993903 :     use->def ()->set_first_use (use);
    1103                 :             : 
    1104                 :     5357068 :   before->set_prev_use (use);
    1105                 :     5357068 :   if (use->is_in_nondebug_insn () && before->is_in_debug_insn_or_phi ())
    1106                 :     9364718 :     def->last_use ()->set_last_nondebug_insn_use (use);
    1107                 :             : 
    1108                 :     5357068 :   gcc_checking_assert (use->check_integrity () && before->check_integrity ());
    1109                 :     5357068 : }
    1110                 :             : 
    1111                 :             : // Add USE to USE->def ()'s list of uses. inserting USE immediately after
    1112                 :             : // AFTER.  USE is not currently in the list.
    1113                 :             : //
    1114                 :             : // This routine should not be used for inserting phi uses.
    1115                 :             : void
    1116                 :   153319642 : function_info::insert_use_after (use_info *use, use_info *after)
    1117                 :             : {
    1118                 :   153319642 :   set_info *def = use->def ();
    1119                 :   306639284 :   gcc_checking_assert (after->is_in_any_insn ()
    1120                 :             :                        && !use->has_use_links ()
    1121                 :             :                        && use->is_in_any_insn ());
    1122                 :             : 
    1123                 :   153319642 :   use->set_prev_use (after);
    1124                 :   153319642 :   use->copy_next_from (after);
    1125                 :             : 
    1126                 :   153319642 :   after->set_next_use (use);
    1127                 :             : 
    1128                 :   153319642 :   if (use_info *next = use->next_use ())
    1129                 :             :     {
    1130                 :             :       // The last node doesn't change, but we might need to update its
    1131                 :             :       // last_nondebug_insn_use record.
    1132                 :    25830061 :       if (use->is_in_nondebug_insn () && next->is_in_debug_insn_or_phi ())
    1133                 :    50171558 :         def->last_use ()->set_last_nondebug_insn_use (use);
    1134                 :    25830061 :       next->set_prev_use (use);
    1135                 :             :     }
    1136                 :             :   else
    1137                 :             :     {
    1138                 :             :       // USE is now the last node.
    1139                 :   127489581 :       if (use->is_in_nondebug_insn ())
    1140                 :   115166928 :         use->set_last_nondebug_insn_use (use);
    1141                 :   127489581 :       def->first_use ()->set_last_use (use);
    1142                 :             :     }
    1143                 :             : 
    1144                 :   153319642 :   gcc_checking_assert (use->check_integrity () && after->check_integrity ());
    1145                 :   153319642 : }
    1146                 :             : 
    1147                 :             : // If USE has a known definition, add USE to that definition's list of uses.
    1148                 :             : // Also update the associated splay tree, if any.
    1149                 :             : void
    1150                 :   342847639 : function_info::add_use (use_info *use)
    1151                 :             : {
    1152                 :   685695278 :   gcc_checking_assert (!use->has_use_links ()
    1153                 :             :                        && !use->m_is_temp
    1154                 :             :                        && !use->m_has_been_superceded);
    1155                 :             : 
    1156                 :   342847639 :   set_info *def = use->def ();
    1157                 :   342847639 :   if (!def)
    1158                 :   341611019 :     return;
    1159                 :             : 
    1160                 :   325813524 :   use_info *first = def->first_use ();
    1161                 :   325813524 :   if (!first)
    1162                 :             :     {
    1163                 :             :       // This is the only use of the definition.
    1164                 :   132923750 :       use->set_last_use (use);
    1165                 :   132923750 :       if (use->is_in_nondebug_insn ())
    1166                 :   116939585 :         use->set_last_nondebug_insn_use (use);
    1167                 :             : 
    1168                 :   132923750 :       def->set_first_use (use);
    1169                 :             : 
    1170                 :   132923750 :       gcc_checking_assert (use->check_integrity ());
    1171                 :             :       return;
    1172                 :             :     }
    1173                 :             : 
    1174                 :   192889774 :   if (use->is_in_phi ())
    1175                 :             :     {
    1176                 :             :       // Add USE at the end of the list, as the new first phi.
    1177                 :    34213064 :       use_info *last = first->last_use ();
    1178                 :             : 
    1179                 :    34213064 :       use->set_prev_use (last);
    1180                 :    34213064 :       use->copy_next_from (last);
    1181                 :             : 
    1182                 :    34213064 :       last->set_next_use (use);
    1183                 :    34213064 :       first->set_last_use (use);
    1184                 :             : 
    1185                 :    34213064 :       gcc_checking_assert (use->check_integrity ());
    1186                 :             :       return;
    1187                 :             :     }
    1188                 :             : 
    1189                 :             :   // If there is currently no splay tree for this definition, see if can
    1190                 :             :   // get away with a pure list-based update.
    1191                 :   158676710 :   insn_info *insn = use->insn ();
    1192                 :   316589841 :   auto quick_path = [&]()
    1193                 :             :     {
    1194                 :             :       // Check if USE should come before all current uses.
    1195                 :   157913131 :       if (first->is_in_phi () || compare_use_insns (insn, first->insn ()) < 0)
    1196                 :             :         {
    1197                 :     4983778 :           insert_use_before (use, first);
    1198                 :     4983778 :           return true;
    1199                 :             :         }
    1200                 :             : 
    1201                 :             :       // Check if USE should come after all current uses in the same
    1202                 :             :       // subsequence (i.e. the list of nondebug insn uses or the list
    1203                 :             :       // of debug insn uses).
    1204                 :   152929353 :       use_info *last = first->last_use ();
    1205                 :   152929353 :       if (use->is_in_debug_insn ())
    1206                 :             :         {
    1207                 :    12436512 :           if (last->is_in_phi ())
    1208                 :             :             return false;
    1209                 :             :         }
    1210                 :             :       else
    1211                 :   140492841 :         last = last->last_nondebug_insn_use ();
    1212                 :             : 
    1213                 :   152805343 :       if (compare_use_insns (insn, last->insn ()) > 0)
    1214                 :             :         {
    1215                 :   152456312 :           insert_use_after (use, last);
    1216                 :   152456312 :           return true;
    1217                 :             :         }
    1218                 :             : 
    1219                 :             :       return false;
    1220                 :   158676710 :     };
    1221                 :   158676710 :   if (!def->m_use_tree && quick_path ())
    1222                 :             :     return;
    1223                 :             : 
    1224                 :             :   // Search the splay tree for an insertion point.  COMPARISON is less
    1225                 :             :   // than zero if USE should come before NEIGHBOR, or greater than zero
    1226                 :             :   // if USE should come after NEIGHBOR.
    1227                 :     1236620 :   need_use_splay_tree (def);
    1228                 :     1236620 :   int comparison = lookup_use (def->m_use_tree, insn);
    1229                 :     1236620 :   gcc_checking_assert (comparison != 0);
    1230                 :     1236620 :   splay_tree_node<use_info *> *neighbor = def->m_use_tree.root ();
    1231                 :             : 
    1232                 :             :   // If USE comes before NEIGHBOR, insert USE to NEIGHBOR's left,
    1233                 :             :   // otherwise insert USE to NEIGHBOR's right.
    1234                 :     1236620 :   auto *use_node = allocate<splay_tree_node<use_info *>> (use);
    1235                 :     1236620 :   def->m_use_tree.insert_child (neighbor, comparison > 0, use_node);
    1236                 :     1236620 :   if (comparison > 0)
    1237                 :      863330 :     insert_use_after (use, neighbor->value ());
    1238                 :             :   else
    1239                 :      373290 :     insert_use_before (use, neighbor->value ());
    1240                 :             : }
    1241                 :             : 
    1242                 :             : void
    1243                 :           0 : function_info::reparent_use (use_info *use, set_info *new_def)
    1244                 :             : {
    1245                 :           0 :   remove_use (use);
    1246                 :           0 :   use->set_def (new_def);
    1247                 :           0 :   add_use (use);
    1248                 :           0 : }
    1249                 :             : 
    1250                 :             : // If USE has a known definition, remove USE from that definition's list
    1251                 :             : // of uses.  Also remove if it from the associated splay tree, if any.
    1252                 :             : void
    1253                 :     9682610 : function_info::remove_use (use_info *use)
    1254                 :             : {
    1255                 :     9682610 :   set_info *def = use->def ();
    1256                 :     9682610 :   if (!def)
    1257                 :             :     return;
    1258                 :             : 
    1259                 :             :   // Remove USE from the splay tree.
    1260                 :     9679305 :   if (def->m_use_tree && use->is_in_any_insn ())
    1261                 :             :     {
    1262                 :      376305 :       int comparison = lookup_use (def->m_use_tree, use->insn ());
    1263                 :      376305 :       gcc_checking_assert (comparison == 0);
    1264                 :      376305 :       def->m_use_tree.remove_root ();
    1265                 :             :     }
    1266                 :             : 
    1267                 :     9679305 :   use_info *prev = use->prev_use ();
    1268                 :     9679305 :   use_info *next = use->next_use ();
    1269                 :             : 
    1270                 :     9679305 :   use_info *first = def->first_use ();
    1271                 :     9679305 :   use_info *last = first->last_use ();
    1272                 :     9679305 :   if (last->last_nondebug_insn_use () == use)
    1273                 :     2507397 :     last->set_last_nondebug_insn_use (prev);
    1274                 :             : 
    1275                 :     9679305 :   if (next)
    1276                 :     3251814 :     next->copy_prev_from (use);
    1277                 :             :   else
    1278                 :     6427491 :     first->set_last_use (prev);
    1279                 :             : 
    1280                 :     9679305 :   if (prev)
    1281                 :     5234981 :     prev->copy_next_from (use);
    1282                 :             :   else
    1283                 :     8888648 :     def->set_first_use (next);
    1284                 :             : 
    1285                 :     9679305 :   use->clear_use_links ();
    1286                 :     9679305 :   gcc_checking_assert ((!prev || prev->check_integrity ())
    1287                 :             :                        && (!next || next->check_integrity ()));
    1288                 :             : }
    1289                 :             : 
    1290                 :             : // Allocate a temporary clobber_info for register REGNO in insn INSN,
    1291                 :             : // including it in the region of the obstack governed by WATERMARK.
    1292                 :             : // Return a new def_array that contains OLD_DEFS and the new clobber.
    1293                 :             : //
    1294                 :             : // OLD_DEFS is known not to define REGNO.
    1295                 :             : def_array
    1296                 :     1600060 : function_info::insert_temp_clobber (obstack_watermark &watermark,
    1297                 :             :                                     insn_info *insn, unsigned int regno,
    1298                 :             :                                     def_array old_defs)
    1299                 :             : {
    1300                 :     1600060 :   gcc_checking_assert (watermark == &m_temp_obstack);
    1301                 :     1600060 :   auto *clobber = allocate_temp<clobber_info> (insn, regno);
    1302                 :     1600060 :   clobber->m_is_temp = true;
    1303                 :     1600060 :   return insert_access (watermark, clobber, old_defs);
    1304                 :             : }
    1305                 :             : 
    1306                 :             : // See the comment above the declaration.
    1307                 :             : bool
    1308                 :     2304363 : function_info::remains_available_at_insn (const set_info *set,
    1309                 :             :                                           insn_info *insn)
    1310                 :             : {
    1311                 :     2304363 :   auto *ebb = set->ebb ();
    1312                 :     2304363 :   gcc_checking_assert (ebb == insn->ebb ());
    1313                 :             : 
    1314                 :     2304363 :   def_info *next_def = set->next_def ();
    1315                 :     2217477 :   if (next_def && *next_def->insn () < *insn)
    1316                 :             :     return false;
    1317                 :             : 
    1318                 :     1753237 :   if (HARD_REGISTER_NUM_P (set->regno ())
    1319                 :     1753237 :       && TEST_HARD_REG_BIT (m_clobbered_by_calls, set->regno ()))
    1320                 :        1135 :     for (ebb_call_clobbers_info *call_group : ebb->call_clobbers ())
    1321                 :             :       {
    1322                 :         524 :         if (!call_group->clobbers (set->resource ()))
    1323                 :           0 :           continue;
    1324                 :             : 
    1325                 :         524 :         insn_info *call_insn = next_call_clobbers (*call_group, insn);
    1326                 :         524 :         if (call_insn && *call_insn < *insn)
    1327                 :      551126 :           return false;
    1328                 :             :       }
    1329                 :             : 
    1330                 :             :   return true;
    1331                 :             : }
    1332                 :             : 
    1333                 :             : // See the comment above the declaration.
    1334                 :             : bool
    1335                 :      343836 : function_info::remains_available_on_exit (const set_info *set, bb_info *bb)
    1336                 :             : {
    1337                 :      343836 :   if (HARD_REGISTER_NUM_P (set->regno ())
    1338                 :      343836 :       && TEST_HARD_REG_BIT (m_clobbered_by_calls, set->regno ()))
    1339                 :             :     {
    1340                 :         316 :       insn_info *search_insn = (set->bb () == bb
    1341                 :         316 :                                 ? set->insn ()
    1342                 :           0 :                                 : bb->head_insn ());
    1343                 :         341 :       for (ebb_call_clobbers_info *call_group : bb->ebb ()->call_clobbers ())
    1344                 :             :         {
    1345                 :          50 :           if (!call_group->clobbers (set->resource ()))
    1346                 :           0 :             continue;
    1347                 :             : 
    1348                 :          50 :           insn_info *insn = next_call_clobbers (*call_group, search_insn);
    1349                 :          50 :           if (insn && insn->bb () == bb)
    1350                 :       71732 :             return false;
    1351                 :             :         }
    1352                 :             :     }
    1353                 :             : 
    1354                 :      343811 :   return (set->is_last_def ()
    1355                 :      676886 :           || *set->next_def ()->insn () > *bb->end_insn ());
    1356                 :             : }
    1357                 :             : 
    1358                 :             : // A subroutine of make_uses_available.  Try to make USE's definition
    1359                 :             : // available at the head of BB.  WILL_BE_DEBUG_USE is true if the
    1360                 :             : // definition will be used only in debug instructions.
    1361                 :             : //
    1362                 :             : // On success:
    1363                 :             : //
    1364                 :             : // - If the use would have the same def () as USE, return USE.
    1365                 :             : //
    1366                 :             : // - If BB already has a degenerate phi for the same definition,
    1367                 :             : //   return a temporary use of that phi.
    1368                 :             : //
    1369                 :             : // - Otherwise, the use would need a new degenerate phi.  Allocate a
    1370                 :             : //   temporary phi and return a temporary use of it.
    1371                 :             : //
    1372                 :             : // Return null on failure.
    1373                 :             : use_info *
    1374                 :    10564485 : function_info::make_use_available (use_info *use, bb_info *bb,
    1375                 :             :                                    bool will_be_debug_use)
    1376                 :             : {
    1377                 :    10564485 :   set_info *def = use->def ();
    1378                 :    10564485 :   if (!def)
    1379                 :             :     return use;
    1380                 :             : 
    1381                 :    10564473 :   if (is_single_dominating_def (def))
    1382                 :             :     return use;
    1383                 :             : 
    1384                 :     4474311 :   if (def->ebb () == bb->ebb ())
    1385                 :             :     {
    1386                 :     2304363 :       if (remains_available_at_insn (def, bb->head_insn ()))
    1387                 :             :         return use;
    1388                 :             :       return nullptr;
    1389                 :             :     }
    1390                 :             : 
    1391                 :     2169948 :   basic_block cfg_bb = bb->cfg_bb ();
    1392                 :     2169948 :   bb_info *use_bb = use->bb ();
    1393                 :     2169948 :   if (single_pred_p (cfg_bb)
    1394                 :     1427867 :       && single_pred (cfg_bb) == use_bb->cfg_bb ()
    1395                 :     2513784 :       && remains_available_on_exit (def, use_bb))
    1396                 :             :     {
    1397                 :      272104 :       if (will_be_debug_use)
    1398                 :             :         return use;
    1399                 :             : 
    1400                 :      237619 :       resource_info resource = use->resource ();
    1401                 :      237619 :       set_info *ultimate_def = look_through_degenerate_phi (def);
    1402                 :             : 
    1403                 :             :       // See if there is already a (degenerate) phi for DEF.
    1404                 :      237619 :       insn_info *phi_insn = bb->ebb ()->phi_insn ();
    1405                 :      237619 :       phi_info *phi;
    1406                 :      237619 :       def_lookup dl = find_def (resource, phi_insn);
    1407                 :      237619 :       if (set_info *set = dl.matching_set ())
    1408                 :             :         {
    1409                 :             :           // There is an existing phi.
    1410                 :      116653 :           phi = as_a<phi_info *> (set);
    1411                 :      116653 :           gcc_checking_assert (phi->input_value (0) == ultimate_def);
    1412                 :             :         }
    1413                 :             :       else
    1414                 :             :         {
    1415                 :             :           // Create a temporary placeholder phi.  This will become
    1416                 :             :           // permanent if the change is later committed.
    1417                 :      120966 :           phi = allocate_temp<phi_info> (phi_insn, resource, 0);
    1418                 :      120966 :           auto *input = allocate_temp<use_info> (phi, resource, ultimate_def);
    1419                 :      120966 :           input->m_is_temp = true;
    1420                 :      120966 :           phi->m_is_temp = true;
    1421                 :      120966 :           phi->make_degenerate (input);
    1422                 :      120966 :           if (def_info *prev = dl.prev_def (phi_insn))
    1423                 :      120966 :             phi->set_prev_def (prev);
    1424                 :      120966 :           if (def_info *next = dl.next_def (phi_insn))
    1425                 :      106580 :             phi->set_next_def (next);
    1426                 :             :         }
    1427                 :             : 
    1428                 :             :       // Create a temporary use of the phi at the head of the first
    1429                 :             :       // block, since we know for sure that it's available there.
    1430                 :      237619 :       insn_info *use_insn = bb->ebb ()->first_bb ()->head_insn ();
    1431                 :      237619 :       auto *new_use = allocate_temp<use_info> (use_insn, resource, phi);
    1432                 :      237619 :       new_use->m_is_temp = true;
    1433                 :      237619 :       return new_use;
    1434                 :             :     }
    1435                 :             :   return nullptr;
    1436                 :             : }
    1437                 :             : 
    1438                 :             : // See the comment above the declaration.
    1439                 :             : use_array
    1440                 :     6855655 : function_info::make_uses_available (obstack_watermark &watermark,
    1441                 :             :                                     use_array uses, bb_info *bb,
    1442                 :             :                                     bool will_be_debug_uses)
    1443                 :             : {
    1444                 :     6855655 :   unsigned int num_uses = uses.size ();
    1445                 :     6855655 :   if (num_uses == 0)
    1446                 :      334028 :     return uses;
    1447                 :             : 
    1448                 :     6521627 :   auto **new_uses = XOBNEWVEC (watermark, access_info *, num_uses);
    1449                 :    14637142 :   for (unsigned int i = 0; i < num_uses; ++i)
    1450                 :             :     {
    1451                 :    10564485 :       use_info *use = make_use_available (uses[i], bb, will_be_debug_uses);
    1452                 :    10564485 :       if (!use)
    1453                 :     2448970 :         return use_array (access_array::invalid ());
    1454                 :     8115515 :       new_uses[i] = use;
    1455                 :             :     }
    1456                 :     4072657 :   return use_array (new_uses, num_uses);
    1457                 :             : }
    1458                 :             : 
    1459                 :             : set_info *
    1460                 :           0 : function_info::create_set (obstack_watermark &watermark,
    1461                 :             :                            insn_info *insn,
    1462                 :             :                            resource_info resource)
    1463                 :             : {
    1464                 :           0 :   auto set = change_alloc<set_info> (watermark, insn, resource);
    1465                 :           0 :   set->m_is_temp = true;
    1466                 :           0 :   return set;
    1467                 :             : }
    1468                 :             : 
    1469                 :             : use_info *
    1470                 :           0 : function_info::create_use (obstack_watermark &watermark,
    1471                 :             :                            insn_info *insn,
    1472                 :             :                            set_info *set)
    1473                 :             : {
    1474                 :           0 :   auto use = change_alloc<use_info> (watermark, insn, set->resource (), set);
    1475                 :           0 :   use->m_is_temp = true;
    1476                 :           0 :   return use;
    1477                 :             : }
    1478                 :             : 
    1479                 :             : // Return true if ACCESS1 can represent ACCESS2 and if ACCESS2 can
    1480                 :             : // represent ACCESS1.
    1481                 :             : static bool
    1482                 :     5325119 : can_merge_accesses (access_info *access1, access_info *access2)
    1483                 :             : {
    1484                 :     5325119 :   if (access1 == access2)
    1485                 :             :     return true;
    1486                 :             : 
    1487                 :     5325119 :   auto *use1 = dyn_cast<use_info *> (access1);
    1488                 :     5325119 :   auto *use2 = dyn_cast<use_info *> (access2);
    1489                 :     5325119 :   return use1 && use2 && use1->def () == use2->def ();
    1490                 :             : }
    1491                 :             : 
    1492                 :             : // See the comment above the declaration.
    1493                 :             : access_array
    1494                 :    29784569 : rtl_ssa::merge_access_arrays_base (obstack_watermark &watermark,
    1495                 :             :                                    access_array accesses1,
    1496                 :             :                                    access_array accesses2)
    1497                 :             : {
    1498                 :    29784569 :   if (accesses1.empty ())
    1499                 :           0 :     return accesses2;
    1500                 :    29784569 :   if (accesses2.empty ())
    1501                 :     4041122 :     return accesses1;
    1502                 :             : 
    1503                 :    25743447 :   auto i1 = accesses1.begin ();
    1504                 :    25743447 :   auto end1 = accesses1.end ();
    1505                 :    25743447 :   auto i2 = accesses2.begin ();
    1506                 :    25743447 :   auto end2 = accesses2.end ();
    1507                 :             : 
    1508                 :    25743447 :   access_array_builder builder (watermark);
    1509                 :    25743447 :   builder.reserve (accesses1.size () + accesses2.size ());
    1510                 :             : 
    1511                 :   101371525 :   while (i1 != end1 && i2 != end2)
    1512                 :             :     {
    1513                 :    51447719 :       access_info *access1 = *i1;
    1514                 :    51447719 :       access_info *access2 = *i2;
    1515                 :             : 
    1516                 :    51447719 :       unsigned int regno1 = access1->regno ();
    1517                 :    51447719 :       unsigned int regno2 = access2->regno ();
    1518                 :    51447719 :       if (regno1 == regno2)
    1519                 :             :         {
    1520                 :     5325119 :           if (!can_merge_accesses (access1, access2))
    1521                 :     1563088 :             return access_array::invalid ();
    1522                 :             : 
    1523                 :     3762031 :           builder.quick_push (access1);
    1524                 :     3762031 :           ++i1;
    1525                 :     3762031 :           ++i2;
    1526                 :             :         }
    1527                 :    46122600 :       else if (regno1 < regno2)
    1528                 :             :         {
    1529                 :    27260261 :           builder.quick_push (access1);
    1530                 :    27260261 :           ++i1;
    1531                 :             :         }
    1532                 :             :       else
    1533                 :             :         {
    1534                 :    18862339 :           builder.quick_push (access2);
    1535                 :    18862339 :           ++i2;
    1536                 :             :         }
    1537                 :             :     }
    1538                 :    39116490 :   for (; i1 != end1; ++i1)
    1539                 :    14936131 :     builder.quick_push (*i1);
    1540                 :    37999366 :   for (; i2 != end2; ++i2)
    1541                 :    13819007 :     builder.quick_push (*i2);
    1542                 :             : 
    1543                 :    24180359 :   return builder.finish ();
    1544                 :    25743447 : }
    1545                 :             : 
    1546                 :             : // See the comment above the declaration.
    1547                 :             : access_array
    1548                 :     1600060 : rtl_ssa::insert_access_base (obstack_watermark &watermark,
    1549                 :             :                              access_info *access1, access_array accesses2)
    1550                 :             : {
    1551                 :     1600060 :   access_array_builder builder (watermark);
    1552                 :     1600060 :   builder.reserve (1 + accesses2.size ());
    1553                 :             : 
    1554                 :     1600060 :   unsigned int regno1 = access1->regno ();
    1555                 :     1600060 :   auto i2 = accesses2.begin ();
    1556                 :     1600060 :   auto end2 = accesses2.end ();
    1557                 :     2946596 :   while (i2 != end2)
    1558                 :             :     {
    1559                 :     1601911 :       access_info *access2 = *i2;
    1560                 :             : 
    1561                 :     1601911 :       unsigned int regno2 = access2->regno ();
    1562                 :     1601911 :       if (regno1 == regno2)
    1563                 :             :         {
    1564                 :           0 :           if (!can_merge_accesses (access1, access2))
    1565                 :           0 :             return access_array::invalid ();
    1566                 :             : 
    1567                 :           0 :           builder.quick_push (access1);
    1568                 :           0 :           access1 = nullptr;
    1569                 :           0 :           ++i2;
    1570                 :           0 :           break;
    1571                 :             :         }
    1572                 :     1601911 :       else if (regno1 < regno2)
    1573                 :             :         {
    1574                 :      255375 :           builder.quick_push (access1);
    1575                 :      255375 :           access1 = nullptr;
    1576                 :      255375 :           break;
    1577                 :             :         }
    1578                 :             :       else
    1579                 :             :         {
    1580                 :     1346536 :           builder.quick_push (access2);
    1581                 :     1346536 :           ++i2;
    1582                 :             :         }
    1583                 :             :     }
    1584                 :      255375 :   if (access1)
    1585                 :     1344685 :     builder.quick_push (access1);
    1586                 :     1855435 :   for (; i2 != end2; ++i2)
    1587                 :      255375 :     builder.quick_push (*i2);
    1588                 :             : 
    1589                 :     1600060 :   return builder.finish ();
    1590                 :     1600060 : }
    1591                 :             : 
    1592                 :             : // See the comment above the declaration.
    1593                 :             : use_array
    1594                 :           0 : rtl_ssa::remove_uses_of_def (obstack_watermark &watermark, use_array uses,
    1595                 :             :                              def_info *def)
    1596                 :             : {
    1597                 :           0 :   access_array_builder uses_builder (watermark);
    1598                 :           0 :   uses_builder.reserve (uses.size ());
    1599                 :           0 :   for (use_info *use : uses)
    1600                 :           0 :     if (use->def () != def)
    1601                 :           0 :       uses_builder.quick_push (use);
    1602                 :           0 :   return use_array (uses_builder.finish ());
    1603                 :           0 : }
    1604                 :             : 
    1605                 :             : // See the comment above the declaration.
    1606                 :             : access_array
    1607                 :    41285067 : rtl_ssa::remove_note_accesses_base (obstack_watermark &watermark,
    1608                 :             :                                     access_array accesses)
    1609                 :             : {
    1610                 :    43223441 :   auto predicate = [](access_info *a) {
    1611                 :     1938374 :     return !a->only_occurs_in_notes ();
    1612                 :             :   };
    1613                 :             : 
    1614                 :    92730977 :   for (access_info *access : accesses)
    1615                 :    52154713 :     if (access->only_occurs_in_notes ())
    1616                 :      708803 :       return filter_accesses (watermark, accesses, predicate);
    1617                 :             : 
    1618                 :    40576264 :   return accesses;
    1619                 :             : }
    1620                 :             : 
    1621                 :             : // See the comment above the declaration.
    1622                 :             : bool
    1623                 :           0 : rtl_ssa::accesses_reference_same_resource (access_array accesses1,
    1624                 :             :                                            access_array accesses2)
    1625                 :             : {
    1626                 :           0 :   auto i1 = accesses1.begin ();
    1627                 :           0 :   auto end1 = accesses1.end ();
    1628                 :           0 :   auto i2 = accesses2.begin ();
    1629                 :           0 :   auto end2 = accesses2.end ();
    1630                 :             : 
    1631                 :           0 :   while (i1 != end1 && i2 != end2)
    1632                 :             :     {
    1633                 :           0 :       access_info *access1 = *i1;
    1634                 :           0 :       access_info *access2 = *i2;
    1635                 :             : 
    1636                 :           0 :       unsigned int regno1 = access1->regno ();
    1637                 :           0 :       unsigned int regno2 = access2->regno ();
    1638                 :           0 :       if (regno1 == regno2)
    1639                 :             :         return true;
    1640                 :             : 
    1641                 :           0 :       if (regno1 < regno2)
    1642                 :           0 :         ++i1;
    1643                 :             :       else
    1644                 :           0 :         ++i2;
    1645                 :             :     }
    1646                 :             :   return false;
    1647                 :             : }
    1648                 :             : 
    1649                 :             : // See the comment above the declaration.
    1650                 :             : bool
    1651                 :           0 : rtl_ssa::insn_clobbers_resources (insn_info *insn, access_array accesses)
    1652                 :             : {
    1653                 :           0 :   if (accesses_reference_same_resource (insn->defs (), accesses))
    1654                 :             :     return true;
    1655                 :             : 
    1656                 :           0 :   if (insn->is_call () && accesses_include_hard_registers (accesses))
    1657                 :             :     {
    1658                 :           0 :       function_abi abi = insn_callee_abi (insn->rtl ());
    1659                 :           0 :       for (const access_info *access : accesses)
    1660                 :             :         {
    1661                 :           0 :           if (!HARD_REGISTER_NUM_P (access->regno ()))
    1662                 :             :             break;
    1663                 :           0 :           if (abi.clobbers_reg_p (access->mode (), access->regno ()))
    1664                 :           0 :             return true;
    1665                 :             :         }
    1666                 :             :     }
    1667                 :             : 
    1668                 :             :   return false;
    1669                 :             : }
    1670                 :             : 
    1671                 :             : // Print RESOURCE to PP.
    1672                 :             : void
    1673                 :           0 : rtl_ssa::pp_resource (pretty_printer *pp, resource_info resource)
    1674                 :             : {
    1675                 :           0 :   resource.print (pp);
    1676                 :           0 : }
    1677                 :             : 
    1678                 :             : // Print ACCESS to PP.  FLAGS is a bitmask of PP_ACCESS_* flags.
    1679                 :             : void
    1680                 :           0 : rtl_ssa::pp_access (pretty_printer *pp, const access_info *access,
    1681                 :             :                     unsigned int flags)
    1682                 :             : {
    1683                 :           0 :   if (!access)
    1684                 :           0 :     pp_string (pp, "<null>");
    1685                 :           0 :   else if (auto *phi = dyn_cast<const phi_info *> (access))
    1686                 :           0 :     phi->print (pp, flags);
    1687                 :           0 :   else if (auto *set = dyn_cast<const set_info *> (access))
    1688                 :           0 :     set->print (pp, flags);
    1689                 :           0 :   else if (auto *clobber = dyn_cast<const clobber_info *> (access))
    1690                 :           0 :     clobber->print (pp, flags);
    1691                 :           0 :   else if (auto *use = dyn_cast<const use_info *> (access))
    1692                 :           0 :     use->print (pp, flags);
    1693                 :             :   else
    1694                 :             :     pp_string (pp, "??? Unknown access");
    1695                 :           0 : }
    1696                 :             : 
    1697                 :             : // Print ACCESSES to PP.  FLAGS is a bitmask of PP_ACCESS_* flags.
    1698                 :             : void
    1699                 :           0 : rtl_ssa::pp_accesses (pretty_printer *pp, access_array accesses,
    1700                 :             :                       unsigned int flags)
    1701                 :             : {
    1702                 :           0 :   if (accesses.empty ())
    1703                 :           0 :     pp_string (pp, "none");
    1704                 :             :   else
    1705                 :             :     {
    1706                 :           0 :       bool is_first = true;
    1707                 :           0 :       for (access_info *access : accesses)
    1708                 :             :         {
    1709                 :           0 :           if (is_first)
    1710                 :             :             is_first = false;
    1711                 :             :           else
    1712                 :           0 :             pp_newline_and_indent (pp, 0);
    1713                 :           0 :           pp_access (pp, access, flags);
    1714                 :             :         }
    1715                 :             :     }
    1716                 :           0 : }
    1717                 :             : 
    1718                 :             : // Print NODE to PP.
    1719                 :             : void
    1720                 :           0 : rtl_ssa::pp_def_node (pretty_printer *pp, const def_node *node)
    1721                 :             : {
    1722                 :           0 :   if (!node)
    1723                 :           0 :     pp_string (pp, "<null>");
    1724                 :           0 :   else if (auto *group = dyn_cast<const clobber_group *> (node))
    1725                 :           0 :     group->print (pp);
    1726                 :           0 :   else if (auto *set = dyn_cast<const set_node *> (node))
    1727                 :           0 :     set->print (pp);
    1728                 :             :   else
    1729                 :           0 :     pp_string (pp, "??? Unknown def node");
    1730                 :           0 : }
    1731                 :             : 
    1732                 :             : // Print MUX to PP.
    1733                 :             : void
    1734                 :           0 : rtl_ssa::pp_def_mux (pretty_printer *pp, def_mux mux)
    1735                 :             : {
    1736                 :           0 :   if (auto *node = mux.dyn_cast<def_node *> ())
    1737                 :           0 :     pp_def_node (pp, node);
    1738                 :             :   else
    1739                 :           0 :     pp_access (pp, mux.as_a<def_info *> ());
    1740                 :           0 : }
    1741                 :             : 
    1742                 :             : // Print DL to PP.
    1743                 :             : void
    1744                 :           0 : rtl_ssa::pp_def_lookup (pretty_printer *pp, def_lookup dl)
    1745                 :             : {
    1746                 :           0 :   pp_string (pp, "comparison result of ");
    1747                 :           0 :   pp_decimal_int (pp, dl.comparison);
    1748                 :           0 :   pp_string (pp, " for ");
    1749                 :           0 :   pp_newline_and_indent (pp, 0);
    1750                 :           0 :   pp_def_mux (pp, dl.mux);
    1751                 :           0 : }
    1752                 :             : 
    1753                 :             : // Dump RESOURCE to FILE.
    1754                 :             : void
    1755                 :           0 : dump (FILE *file, resource_info resource)
    1756                 :             : {
    1757                 :           0 :   dump_using (file, pp_resource, resource);
    1758                 :           0 : }
    1759                 :             : 
    1760                 :             : // Dump ACCESS to FILE.  FLAGS is a bitmask of PP_ACCESS_* flags.
    1761                 :             : void
    1762                 :           0 : dump (FILE *file, const access_info *access, unsigned int flags)
    1763                 :             : {
    1764                 :           0 :   dump_using (file, pp_access, access, flags);
    1765                 :           0 : }
    1766                 :             : 
    1767                 :             : // Dump ACCESSES to FILE.  FLAGS is a bitmask of PP_ACCESS_* flags.
    1768                 :             : void
    1769                 :           0 : dump (FILE *file, access_array accesses, unsigned int flags)
    1770                 :             : {
    1771                 :           0 :   dump_using (file, pp_accesses, accesses, flags);
    1772                 :           0 : }
    1773                 :             : 
    1774                 :             : // Print NODE to FILE.
    1775                 :             : void
    1776                 :           0 : dump (FILE *file, const def_node *node)
    1777                 :             : {
    1778                 :           0 :   dump_using (file, pp_def_node, node);
    1779                 :           0 : }
    1780                 :             : 
    1781                 :             : // Print MUX to FILE.
    1782                 :             : void
    1783                 :           0 : dump (FILE *file, def_mux mux)
    1784                 :             : {
    1785                 :           0 :   dump_using (file, pp_def_mux, mux);
    1786                 :           0 : }
    1787                 :             : 
    1788                 :             : // Print RESULT to FILE.
    1789                 :             : void
    1790                 :           0 : dump (FILE *file, def_lookup result)
    1791                 :             : {
    1792                 :           0 :   dump_using (file, pp_def_lookup, result);
    1793                 :           0 : }
    1794                 :             : 
    1795                 :             : // Debug interfaces to the dump routines above.
    1796                 :           0 : void debug (const resource_info &x) { dump (stderr, x); }
    1797                 :           0 : void debug (const access_info *x) { dump (stderr, x); }
    1798                 :           0 : void debug (const access_array &x) { dump (stderr, x); }
    1799                 :           0 : void debug (const def_node *x) { dump (stderr, x); }
    1800                 :           0 : void debug (const def_mux &x) { dump (stderr, x); }
    1801                 :           0 : void debug (const def_lookup &x) { dump (stderr, x); }
        

Generated by: LCOV version 2.0-1

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,rust,m2 --enable-host-shared. GCC test suite is run with the built compiler.