LCOV - code coverage report
Current view: top level - gcc/rtl-ssa - accesses.cc (source / functions) Coverage Total Hit
Test: gcc.info Lines: 67.8 % 883 599
Test Date: 2025-02-01 13:18:56 Functions: 52.9 % 87 46
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-2025 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                 :             : #define INCLUDE_ARRAY
      23                 :             : #include "config.h"
      24                 :             : #include "system.h"
      25                 :             : #include "coretypes.h"
      26                 :             : #include "backend.h"
      27                 :             : #include "rtl.h"
      28                 :             : #include "df.h"
      29                 :             : #include "rtl-ssa.h"
      30                 :             : #include "rtl-ssa/internals.h"
      31                 :             : #include "rtl-ssa/internals.inl"
      32                 :             : 
      33                 :             : using namespace rtl_ssa;
      34                 :             : 
      35                 :             : // This clobber belongs to a clobber_group but m_group appears to be
      36                 :             : // out of date.  Update it and return the new (correct) value.
      37                 :             : clobber_group *
      38                 :        1097 : clobber_info::recompute_group ()
      39                 :             : {
      40                 :        1097 :   using splay_tree = clobber_info::splay_tree;
      41                 :             : 
      42                 :             :   // Splay this clobber to the root of the tree while searching for a node
      43                 :             :   // that has the correct group.  The root always has the correct group,
      44                 :             :   // so the search always breaks early and does not install this clobber
      45                 :             :   // as the root.
      46                 :        1097 :   clobber_info *cursor = m_parent;
      47                 :        2480 :   auto find_group = [](clobber_info *node, unsigned int)
      48                 :             :     {
      49                 :        1383 :       return node->m_group->has_been_superceded () ? nullptr : node->m_group;
      50                 :             :     };
      51                 :        1097 :   clobber_group *group = splay_tree::splay_and_search (this, nullptr,
      52                 :             :                                                        find_group);
      53                 :        1097 :   gcc_checking_assert (m_parent);
      54                 :             : 
      55                 :             :   // If the previous splay operation did anything, this clobber is now an
      56                 :             :   // ancestor of CURSOR, and all the nodes inbetween have a stale group.
      57                 :             :   // Since we have visited the nodes, we might as well update them too.
      58                 :             :   //
      59                 :             :   // If the previous splay operation did nothing, start the update from
      60                 :             :   // this clobber instead.  In that case we change at most two clobbers:
      61                 :             :   // this clobber and possibly its parent.
      62                 :        1097 :   if (cursor == m_parent)
      63                 :        1077 :     cursor = this;
      64                 :             : 
      65                 :             :   // Walk up the tree from CURSOR updating clobbers that need it.
      66                 :             :   // This walk always includes this clobber.
      67                 :        2460 :   while (cursor->m_group != group)
      68                 :             :     {
      69                 :        1363 :       cursor->m_group = group;
      70                 :        1363 :       cursor = cursor->m_parent;
      71                 :             :     }
      72                 :             : 
      73                 :        1097 :   gcc_checking_assert (m_group == group);
      74                 :        1097 :   return group;
      75                 :             : }
      76                 :             : 
      77                 :             : // See the comment above the declaration.
      78                 :             : void
      79                 :           0 : resource_info::print_identifier (pretty_printer *pp) const
      80                 :             : {
      81                 :           0 :   if (is_mem ())
      82                 :           0 :     pp_string (pp, "mem");
      83                 :             :   else
      84                 :             :     {
      85                 :           0 :       char tmp[3 * sizeof (regno) + 2];
      86                 :           0 :       snprintf (tmp, sizeof (tmp), "r%d", regno);
      87                 :           0 :       pp_string (pp, tmp);
      88                 :             :     }
      89                 :           0 : }
      90                 :             : 
      91                 :             : // See the comment above the declaration.
      92                 :             : void
      93                 :           0 : resource_info::print_context (pretty_printer *pp) const
      94                 :             : {
      95                 :           0 :   if (HARD_REGISTER_NUM_P (regno))
      96                 :             :     {
      97                 :           0 :       if (const char *name = reg_names[regno])
      98                 :             :         {
      99                 :           0 :           pp_space (pp);
     100                 :           0 :           pp_left_paren (pp);
     101                 :           0 :           pp_string (pp, name);
     102                 :           0 :           if (mode != E_BLKmode)
     103                 :             :             {
     104                 :           0 :               pp_colon (pp);
     105                 :           0 :               pp_string (pp, GET_MODE_NAME (mode));
     106                 :             :             }
     107                 :           0 :           pp_right_paren (pp);
     108                 :             :         }
     109                 :             :     }
     110                 :           0 :   else if (is_reg ())
     111                 :             :     {
     112                 :           0 :       pp_space (pp);
     113                 :           0 :       pp_left_paren (pp);
     114                 :           0 :       if (mode != E_BLKmode)
     115                 :             :         {
     116                 :           0 :           pp_string (pp, GET_MODE_NAME (mode));
     117                 :           0 :           pp_space (pp);
     118                 :             :         }
     119                 :           0 :       pp_string (pp, "pseudo");
     120                 :           0 :       pp_right_paren (pp);
     121                 :             :     }
     122                 :           0 : }
     123                 :             : 
     124                 :             : // See the comment above the declaration.
     125                 :             : void
     126                 :           0 : resource_info::print (pretty_printer *pp) const
     127                 :             : {
     128                 :           0 :   print_identifier (pp);
     129                 :           0 :   print_context (pp);
     130                 :           0 : }
     131                 :             : 
     132                 :             : // Some properties can naturally be described using adjectives that attach
     133                 :             : // to nouns like "use" or "definition".  Print such adjectives to PP.
     134                 :             : void
     135                 :           0 : access_info::print_prefix_flags (pretty_printer *pp) const
     136                 :             : {
     137                 :           0 :   if (m_is_temp)
     138                 :           0 :     pp_string (pp, "temporary ");
     139                 :           0 :   if (m_has_been_superceded)
     140                 :           0 :     pp_string (pp, "superceded ");
     141                 :           0 : }
     142                 :             : 
     143                 :             : // Print properties not handled by print_prefix_flags to PP, putting
     144                 :             : // each property on a new line indented by two extra spaces.
     145                 :             : void
     146                 :           0 : access_info::print_properties_on_new_lines (pretty_printer *pp) const
     147                 :             : {
     148                 :           0 :   if (m_is_pre_post_modify)
     149                 :             :     {
     150                 :           0 :       pp_newline_and_indent (pp, 2);
     151                 :           0 :       pp_string (pp, "set by a pre/post-modify");
     152                 :           0 :       pp_indentation (pp) -= 2;
     153                 :             :     }
     154                 :           0 :   if (m_includes_address_uses)
     155                 :             :     {
     156                 :           0 :       pp_newline_and_indent (pp, 2);
     157                 :           0 :       pp_string (pp, "appears inside an address");
     158                 :           0 :       pp_indentation (pp) -= 2;
     159                 :             :     }
     160                 :           0 :   if (m_includes_read_writes)
     161                 :             :     {
     162                 :           0 :       pp_newline_and_indent (pp, 2);
     163                 :           0 :       pp_string (pp, "appears in a read/write context");
     164                 :           0 :       pp_indentation (pp) -= 2;
     165                 :             :     }
     166                 :           0 :   if (m_includes_subregs)
     167                 :             :     {
     168                 :           0 :       pp_newline_and_indent (pp, 2);
     169                 :           0 :       pp_string (pp, "appears inside a subreg");
     170                 :           0 :       pp_indentation (pp) -= 2;
     171                 :             :     }
     172                 :           0 : }
     173                 :             : 
     174                 :             : // Return true if there are no known issues with the integrity of the
     175                 :             : // link information.
     176                 :             : inline bool
     177                 :   975269119 : use_info::check_integrity ()
     178                 :             : {
     179                 :  2960654255 :   auto subsequence_id = [](use_info *use)
     180                 :             :     {
     181                 :   992692568 :       if (use->is_in_nondebug_insn ())
     182                 :             :         return 1;
     183                 :   370635656 :       if (use->is_in_debug_insn ())
     184                 :   182812267 :         return 2;
     185                 :             :       return 3;
     186                 :             :     };
     187                 :             : 
     188                 :   975269119 :   use_info *prev = prev_use ();
     189                 :   975269119 :   use_info *next = next_use ();
     190                 :             : 
     191                 :  1655392253 :   if (prev && subsequence_id (prev) > subsequence_id (this))
     192                 :             :     return false;
     193                 :  1386939074 :   if (next && subsequence_id (next) < subsequence_id (this))
     194                 :             :     return false;
     195                 :   975269119 :   if (m_is_last_nondebug_insn_use != calculate_is_last_nondebug_insn_use ())
     196                 :             :     return false;
     197                 :             : 
     198                 :   975269119 :   if (!prev && last_use ()->next_use ())
     199                 :             :     return false;
     200                 :   975269119 :   if (!next)
     201                 :   597386804 :     if (use_info *use = last_nondebug_insn_use ())
     202                 :   546984767 :       if (!use->m_is_last_nondebug_insn_use)
     203                 :           0 :         return false;
     204                 :             : 
     205                 :             :   return true;
     206                 :             : }
     207                 :             : 
     208                 :             : // See the comment above the declaration.
     209                 :             : void
     210                 :           0 : use_info::print_location (pretty_printer *pp) const
     211                 :             : {
     212                 :           0 :   if (is_in_phi ())
     213                 :           0 :     pp_access (pp, phi (), PP_ACCESS_INCLUDE_LOCATION);
     214                 :             :   else
     215                 :           0 :     insn ()->print_identifier_and_location (pp);
     216                 :           0 : }
     217                 :             : 
     218                 :             : // See the comment above the declaration.
     219                 :             : void
     220                 :           0 : use_info::print_def (pretty_printer *pp) const
     221                 :             : {
     222                 :           0 :   if (const set_info *set = def ())
     223                 :           0 :     pp_access (pp, set, 0);
     224                 :             :   else
     225                 :             :     {
     226                 :           0 :       pp_string (pp, "undefined ");
     227                 :           0 :       resource ().print (pp);
     228                 :             :     }
     229                 :           0 : }
     230                 :             : 
     231                 :             : // See the comment above the declaration.
     232                 :             : void
     233                 :           0 : use_info::print (pretty_printer *pp, unsigned int flags) const
     234                 :             : {
     235                 :           0 :   print_prefix_flags (pp);
     236                 :             : 
     237                 :           0 :   const set_info *set = def ();
     238                 :           0 :   if (set && set->mode () != mode ())
     239                 :             :     {
     240                 :           0 :       pp_string (pp, GET_MODE_NAME (mode ()));
     241                 :           0 :       pp_space (pp);
     242                 :             :     }
     243                 :             : 
     244                 :           0 :   pp_string (pp, "use of ");
     245                 :           0 :   print_def (pp);
     246                 :           0 :   if (flags & PP_ACCESS_INCLUDE_LOCATION)
     247                 :             :     {
     248                 :           0 :       pp_string (pp, " by ");
     249                 :           0 :       print_location (pp);
     250                 :             :     }
     251                 :           0 :   if (set && (flags & PP_ACCESS_INCLUDE_LINKS))
     252                 :             :     {
     253                 :           0 :       pp_newline_and_indent (pp, 2);
     254                 :           0 :       pp_string (pp, "defined in ");
     255                 :           0 :       set->insn ()->print_location (pp);
     256                 :           0 :       pp_indentation (pp) -= 2;
     257                 :             :     }
     258                 :           0 :   if (flags & PP_ACCESS_INCLUDE_PROPERTIES)
     259                 :           0 :     print_properties_on_new_lines (pp);
     260                 :           0 : }
     261                 :             : 
     262                 :             : // See the comment above the declaration.
     263                 :             : void
     264                 :           0 : def_info::print_identifier (pretty_printer *pp) const
     265                 :             : {
     266                 :           0 :   resource ().print_identifier (pp);
     267                 :           0 :   pp_colon (pp);
     268                 :           0 :   insn ()->print_identifier (pp);
     269                 :           0 :   resource ().print_context (pp);
     270                 :           0 : }
     271                 :             : 
     272                 :             : // See the comment above the declaration.
     273                 :             : void
     274                 :           0 : def_info::print_location (pretty_printer *pp) const
     275                 :             : {
     276                 :           0 :   insn ()->print_identifier_and_location (pp);
     277                 :           0 : }
     278                 :             : 
     279                 :             : // See the comment above the declaration.
     280                 :             : void
     281                 :           0 : clobber_info::print (pretty_printer *pp, unsigned int flags) const
     282                 :             : {
     283                 :           0 :   print_prefix_flags (pp);
     284                 :           0 :   if (is_call_clobber ())
     285                 :           0 :     pp_string (pp, "call ");
     286                 :           0 :   pp_string (pp, "clobber ");
     287                 :           0 :   print_identifier (pp);
     288                 :           0 :   if (flags & PP_ACCESS_INCLUDE_LOCATION)
     289                 :             :     {
     290                 :           0 :       pp_string (pp, " in ");
     291                 :           0 :       insn ()->print_location (pp);
     292                 :             :     }
     293                 :           0 :   if (flags & PP_ACCESS_INCLUDE_PROPERTIES)
     294                 :           0 :     print_properties_on_new_lines (pp);
     295                 :           0 : }
     296                 :             : 
     297                 :             : // See the comment above the declaration.
     298                 :             : void
     299                 :           0 : set_info::print_uses_on_new_lines (pretty_printer *pp) const
     300                 :             : {
     301                 :           0 :   for (const use_info *use : all_uses ())
     302                 :             :     {
     303                 :           0 :       pp_newline_and_indent (pp, 2);
     304                 :           0 :       if (use->is_live_out_use ())
     305                 :             :         {
     306                 :           0 :           pp_string (pp, "live out from ");
     307                 :           0 :           use->insn ()->print_location (pp);
     308                 :             :         }
     309                 :             :       else
     310                 :             :         {
     311                 :           0 :           pp_string (pp, "used by ");
     312                 :           0 :           use->print_location (pp);
     313                 :             :         }
     314                 :           0 :       pp_indentation (pp) -= 2;
     315                 :             :     }
     316                 :           0 :   if (m_use_tree)
     317                 :             :     {
     318                 :           0 :       pp_newline_and_indent (pp, 2);
     319                 :           0 :       pp_string (pp, "splay tree:");
     320                 :           0 :       pp_newline_and_indent (pp, 2);
     321                 :           0 :       auto print_use = [](pretty_printer *pp,
     322                 :             :                           splay_tree_node<use_info *> *node)
     323                 :             :         {
     324                 :           0 :           pp_string (pp, "use by ");
     325                 :           0 :           node->value ()->print_location (pp);
     326                 :           0 :         };
     327                 :           0 :       m_use_tree.print (pp, m_use_tree.root (), print_use);
     328                 :           0 :       pp_indentation (pp) -= 4;
     329                 :             :     }
     330                 :           0 : }
     331                 :             : 
     332                 :             : // See the comment above the declaration.
     333                 :             : void
     334                 :           0 : set_info::print (pretty_printer *pp, unsigned int flags) const
     335                 :             : {
     336                 :           0 :   print_prefix_flags (pp);
     337                 :           0 :   pp_string (pp, "set ");
     338                 :           0 :   print_identifier (pp);
     339                 :           0 :   if (flags & PP_ACCESS_INCLUDE_LOCATION)
     340                 :             :     {
     341                 :           0 :       pp_string (pp, " in ");
     342                 :           0 :       insn ()->print_location (pp);
     343                 :             :     }
     344                 :           0 :   if (flags & PP_ACCESS_INCLUDE_PROPERTIES)
     345                 :           0 :     print_properties_on_new_lines (pp);
     346                 :           0 :   if (flags & PP_ACCESS_INCLUDE_LINKS)
     347                 :           0 :     print_uses_on_new_lines (pp);
     348                 :           0 : }
     349                 :             : 
     350                 :             : // See the comment above the declaration.
     351                 :             : void
     352                 :           0 : phi_info::print (pretty_printer *pp, unsigned int flags) const
     353                 :             : {
     354                 :           0 :   print_prefix_flags (pp);
     355                 :           0 :   pp_string (pp, "phi node ");
     356                 :           0 :   print_identifier (pp);
     357                 :           0 :   if (flags & PP_ACCESS_INCLUDE_LOCATION)
     358                 :             :     {
     359                 :           0 :       pp_string (pp, " in ");
     360                 :           0 :       insn ()->print_location (pp);
     361                 :             :     }
     362                 :             : 
     363                 :           0 :   if (flags & PP_ACCESS_INCLUDE_PROPERTIES)
     364                 :           0 :     print_properties_on_new_lines (pp);
     365                 :             : 
     366                 :           0 :   if (flags & PP_ACCESS_INCLUDE_LINKS)
     367                 :             :     {
     368                 :           0 :       basic_block cfg_bb = bb ()->cfg_bb ();
     369                 :           0 :       pp_newline_and_indent (pp, 2);
     370                 :           0 :       pp_string (pp, "inputs:");
     371                 :           0 :       unsigned int i = 0;
     372                 :           0 :       for (const use_info *input : inputs ())
     373                 :             :         {
     374                 :           0 :           basic_block pred_cfg_bb = EDGE_PRED (cfg_bb, i)->src;
     375                 :           0 :           pp_newline_and_indent (pp, 2);
     376                 :           0 :           pp_string (pp, "bb");
     377                 :           0 :           pp_decimal_int (pp, pred_cfg_bb->index);
     378                 :           0 :           pp_colon (pp);
     379                 :           0 :           pp_space (pp);
     380                 :           0 :           input->print_def (pp);
     381                 :           0 :           pp_indentation (pp) -= 2;
     382                 :           0 :           i += 1;
     383                 :             :         }
     384                 :           0 :       pp_indentation (pp) -= 2;
     385                 :             : 
     386                 :           0 :       print_uses_on_new_lines (pp);
     387                 :             :     }
     388                 :           0 : }
     389                 :             : 
     390                 :             : // See the comment above the declaration.
     391                 :             : void
     392                 :           0 : set_node::print (pretty_printer *pp) const
     393                 :             : {
     394                 :           0 :   pp_access (pp, first_def ());
     395                 :           0 : }
     396                 :             : 
     397                 :             : // See the comment above the declaration.
     398                 :             : clobber_info *
     399                 :          11 : clobber_group::prev_clobber (insn_info *insn) const
     400                 :             : {
     401                 :          11 :   auto &tree = const_cast<clobber_tree &> (m_clobber_tree);
     402                 :          11 :   int comparison = lookup_clobber (tree, insn);
     403                 :          11 :   if (comparison <= 0)
     404                 :          22 :     return dyn_cast<clobber_info *> (tree.root ()->prev_def ());
     405                 :           0 :   return tree.root ();
     406                 :             : }
     407                 :             : 
     408                 :             : // See the comment above the declaration.
     409                 :             : clobber_info *
     410                 :          11 : clobber_group::next_clobber (insn_info *insn) const
     411                 :             : {
     412                 :          11 :   auto &tree = const_cast<clobber_tree &> (m_clobber_tree);
     413                 :          11 :   int comparison = lookup_clobber (tree, insn);
     414                 :          11 :   if (comparison >= 0)
     415                 :          22 :     return dyn_cast<clobber_info *> (tree.root ()->next_def ());
     416                 :           0 :   return tree.root ();
     417                 :             : }
     418                 :             : 
     419                 :             : // See the comment above the declaration.
     420                 :             : void
     421                 :           0 : clobber_group::print (pretty_printer *pp) const
     422                 :             : {
     423                 :           0 :   auto print_clobber = [](pretty_printer *pp, const def_info *clobber)
     424                 :             :     {
     425                 :           0 :       pp_access (pp, clobber);
     426                 :             :     };
     427                 :           0 :   pp_string (pp, "grouped clobber");
     428                 :           0 :   for (const def_info *clobber : clobbers ())
     429                 :             :     {
     430                 :           0 :       pp_newline_and_indent (pp, 2);
     431                 :           0 :       print_clobber (pp, clobber);
     432                 :           0 :       pp_indentation (pp) -= 2;
     433                 :             :     }
     434                 :           0 :   pp_newline_and_indent (pp, 2);
     435                 :           0 :   pp_string (pp, "splay tree");
     436                 :           0 :   pp_newline_and_indent (pp, 2);
     437                 :           0 :   m_clobber_tree.print (pp, print_clobber);
     438                 :           0 :   pp_indentation (pp) -= 4;
     439                 :           0 : }
     440                 :             : 
     441                 :             : // See the comment above the declaration.
     442                 :             : def_info *
     443                 :      163406 : def_lookup::prev_def (insn_info *insn) const
     444                 :             : {
     445                 :      163406 :   if (mux && comparison == 0)
     446                 :          11 :     if (auto *node = mux.dyn_cast<def_node *> ())
     447                 :          11 :       if (auto *group = dyn_cast<clobber_group *> (node))
     448                 :          11 :         if (clobber_info *clobber = group->prev_clobber (insn))
     449                 :             :           return clobber;
     450                 :             : 
     451                 :      163395 :   return last_def_of_prev_group ();
     452                 :             : }
     453                 :             : 
     454                 :             : // See the comment above the declaration.
     455                 :             : def_info *
     456                 :      163406 : def_lookup::next_def (insn_info *insn) const
     457                 :             : {
     458                 :      163406 :   if (mux && comparison == 0)
     459                 :          11 :     if (auto *node = mux.dyn_cast<def_node *> ())
     460                 :          11 :       if (auto *group = dyn_cast<clobber_group *> (node))
     461                 :          11 :         if (clobber_info *clobber = group->next_clobber (insn))
     462                 :             :           return clobber;
     463                 :             : 
     464                 :      163395 :   return first_def_of_next_group ();
     465                 :             : }
     466                 :             : 
     467                 :             : // Return a clobber_group for CLOBBER, creating one if CLOBBER doesn't
     468                 :             : // already belong to a group.
     469                 :             : clobber_group *
     470                 :    59299412 : function_info::need_clobber_group (clobber_info *clobber)
     471                 :             : {
     472                 :    59299412 :   if (clobber->is_in_group ())
     473                 :    47263111 :     return clobber->group ();
     474                 :    12036301 :   return allocate<clobber_group> (clobber);
     475                 :             : }
     476                 :             : 
     477                 :             : // Return a def_node for inserting DEF into the associated resource's
     478                 :             : // splay tree.  Use a clobber_group if DEF is a clobber and a set_node
     479                 :             : // otherwise.
     480                 :             : def_node *
     481                 :    19302538 : function_info::need_def_node (def_info *def)
     482                 :             : {
     483                 :    19302538 :   if (auto *clobber = dyn_cast<clobber_info *> (def))
     484                 :     3828789 :     return need_clobber_group (clobber);
     485                 :    15473749 :   return allocate<set_node> (as_a<set_info *> (def));
     486                 :             : }
     487                 :             : 
     488                 :             : // LAST is the last thing to define LAST->resource (), and is where any
     489                 :             : // splay tree root for LAST->resource () is stored.  Require such a splay tree
     490                 :             : // to exist, creating a new one if necessary.  Return the root of the tree.
     491                 :             : //
     492                 :             : // The caller must call LAST->set_splay_root after it has finished with
     493                 :             : // the splay tree.
     494                 :             : def_splay_tree
     495                 :     2361996 : function_info::need_def_splay_tree (def_info *last)
     496                 :             : {
     497                 :     2361996 :   if (def_node *root = last->splay_root ())
     498                 :     1868873 :     return root;
     499                 :             : 
     500                 :             :   // Use a left-spine rooted at the last node.
     501                 :      493123 :   def_node *root = need_def_node (last);
     502                 :      493123 :   def_node *parent = root;
     503                 :    34618255 :   while (def_info *prev = first_def (parent)->prev_def ())
     504                 :             :     {
     505                 :    18660272 :       def_node *node = need_def_node (prev);
     506                 :    18660272 :       def_splay_tree::insert_child (parent, 0, node);
     507                 :    18660272 :       parent = node;
     508                 :    18660272 :     }
     509                 :      493123 :   return root;
     510                 :             : }
     511                 :             : 
     512                 :             : // Search TREE for either:
     513                 :             : //
     514                 :             : // - a set_info at INSN or
     515                 :             : // - a clobber_group whose range includes INSN
     516                 :             : //
     517                 :             : // If such a node exists, install it as the root of TREE and return 0.
     518                 :             : // Otherwise arbitrarily choose between:
     519                 :             : //
     520                 :             : // (1) Installing the closest preceding node as the root and returning 1.
     521                 :             : // (2) Installing the closest following node as the root and returning -1.
     522                 :             : //
     523                 :             : // Note that this routine should not be used to check whether INSN
     524                 :             : // itself defines a resource; that can be checked more cheaply using
     525                 :             : // find_access_index.
     526                 :             : int
     527                 :     2458831 : rtl_ssa::lookup_def (def_splay_tree &tree, insn_info *insn)
     528                 :             : {
     529                 :    28381603 :   auto go_left = [&](def_node *node)
     530                 :             :     {
     531                 :    44191541 :       return *insn < *first_def (node)->insn ();
     532                 :     2458831 :     };
     533                 :     8092789 :   auto go_right = [&](def_node *node)
     534                 :             :     {
     535                 :    11267916 :       return *insn > *last_def (node)->insn ();
     536                 :     2458831 :     };
     537                 :     2458831 :   return tree.lookup (go_left, go_right);
     538                 :             : }
     539                 :             : 
     540                 :             : // Search TREE for a clobber in INSN.  If such a clobber exists, install
     541                 :             : // it as the root of TREE and return 0.  Otherwise arbitrarily choose between:
     542                 :             : //
     543                 :             : // (1) Installing the closest preceding clobber as the root and returning 1.
     544                 :             : // (2) Installing the closest following clobber as the root and returning -1.
     545                 :             : int
     546                 :      338619 : rtl_ssa::lookup_clobber (clobber_tree &tree, insn_info *insn)
     547                 :             : {
     548                 :     1582767 :   auto compare = [&](clobber_info *clobber)
     549                 :             :     {
     550                 :     1244148 :       return insn->compare_with (clobber->insn ());
     551                 :      338619 :     };
     552                 :      338619 :   return tree.lookup (compare);
     553                 :             : }
     554                 :             : 
     555                 :             : // Search for a definition of RESOURCE at INSN and return the result of
     556                 :             : // the search as a def_lookup.  See the comment above the class for more
     557                 :             : // details.
     558                 :             : def_lookup
     559                 :     2138359 : function_info::find_def (resource_info resource, insn_info *insn)
     560                 :             : {
     561                 :     2138359 :   def_info *first = m_defs[resource.regno + 1];
     562                 :     2138359 :   if (!first)
     563                 :             :     // There are no nodes.  The comparison result is pretty meaningless
     564                 :             :     // in this case.
     565                 :         695 :     return { nullptr, -1 };
     566                 :             : 
     567                 :             :   // See whether the first node matches.
     568                 :     2137664 :   auto first_result = clobber_group_or_single_def (first);
     569                 :     2137664 :   if (*insn <= *last_def (first_result)->insn ())
     570                 :             :     {
     571                 :      181934 :       int comparison = (*insn >= *first->insn () ? 0 : -1);
     572                 :      181934 :       return { first_result, comparison };
     573                 :             :     }
     574                 :             : 
     575                 :             :   // See whether the last node matches.
     576                 :     1955730 :   def_info *last = first->last_def ();
     577                 :     1955730 :   auto last_result = clobber_group_or_single_def (last);
     578                 :     2993743 :   if (*insn >= *first_def (last_result)->insn ())
     579                 :             :     {
     580                 :      379861 :       int comparison = (*insn <= *last->insn () ? 0 : 1);
     581                 :      379861 :       return { last_result, comparison };
     582                 :             :     }
     583                 :             : 
     584                 :             :   // Resort to using a splay tree to search for the result.
     585                 :     1575869 :   def_splay_tree tree = need_def_splay_tree (last);
     586                 :     1575869 :   int comparison = lookup_def (tree, insn);
     587                 :     1575869 :   last->set_splay_root (tree.root ());
     588                 :     1575869 :   return { tree.root (), comparison };
     589                 :             : }
     590                 :             : 
     591                 :             : // Add DEF to the function's list of definitions of DEF->resource (),
     592                 :             : // inserting DEF immediately before BEFORE.  DEF is not currently in the list.
     593                 :             : void
     594                 :      378522 : function_info::insert_def_before (def_info *def, def_info *before)
     595                 :             : {
     596                 :      757044 :   gcc_checking_assert (!def->has_def_links ()
     597                 :             :                        && *before->insn () > *def->insn ());
     598                 :             : 
     599                 :      378522 :   def->copy_prev_from (before);
     600                 :      378522 :   if (def_info *prev = def->prev_def ())
     601                 :             :     {
     602                 :      311884 :       gcc_checking_assert (*prev->insn () < *def->insn ());
     603                 :      311884 :       prev->set_next_def (def);
     604                 :             :     }
     605                 :             :   else
     606                 :       66638 :     m_defs[def->regno () + 1] = def;
     607                 :             : 
     608                 :      378522 :   def->set_next_def (before);
     609                 :      378522 :   before->set_prev_def (def);
     610                 :      378522 : }
     611                 :             : 
     612                 :             : // Add DEF to the function's list of definitions of DEF->resource (),
     613                 :             : // inserting DEF immediately after AFTER.  DEF is not currently in the list.
     614                 :             : void
     615                 :    57965005 : function_info::insert_def_after (def_info *def, def_info *after)
     616                 :             : {
     617                 :   115930010 :   gcc_checking_assert (!def->has_def_links ()
     618                 :             :                        && *after->insn () < *def->insn ());
     619                 :             : 
     620                 :    57965005 :   def->copy_next_from (after);
     621                 :    57965005 :   if (def_info *next = def->next_def ())
     622                 :             :     {
     623                 :      474243 :       gcc_checking_assert (*next->insn () > *def->insn ());
     624                 :      474243 :       next->set_prev_def (def);
     625                 :             :     }
     626                 :             :   else
     627                 :    57490762 :     m_defs[def->regno () + 1]->set_last_def (def);
     628                 :             : 
     629                 :    57965005 :   def->set_prev_def (after);
     630                 :    57965005 :   after->set_next_def (def);
     631                 :    57965005 : }
     632                 :             : 
     633                 :             : // Remove DEF from the function's list of definitions of DEF->resource ().
     634                 :             : void
     635                 :     8346857 : function_info::remove_def_from_list (def_info *def)
     636                 :             : {
     637                 :     8346857 :   def_info *prev = def->prev_def ();
     638                 :     8346857 :   def_info *next = def->next_def ();
     639                 :             : 
     640                 :     8346857 :   if (next)
     641                 :     4428651 :     next->copy_prev_from (def);
     642                 :             :   else
     643                 :     3918206 :     m_defs[def->regno () + 1]->set_last_def (prev);
     644                 :             : 
     645                 :     8346857 :   if (prev)
     646                 :     8188866 :     prev->copy_next_from (def);
     647                 :             :   else
     648                 :      157991 :     m_defs[def->regno () + 1] = next;
     649                 :             : 
     650                 :     8346857 :   def->clear_def_links ();
     651                 :     8346857 : }
     652                 :             : 
     653                 :             : // Add CLOBBER to GROUP and insert it into the function's list of
     654                 :             : // accesses to CLOBBER->resource ().  CLOBBER is not currently part
     655                 :             : // of an active group and is not currently in the list.
     656                 :             : void
     657                 :      338594 : function_info::add_clobber (clobber_info *clobber, clobber_group *group)
     658                 :             : {
     659                 :             :   // Search for either the previous or next clobber in the group.
     660                 :             :   // The result is less than zero if CLOBBER should come before NEIGHBOR
     661                 :             :   // or greater than zero if CLOBBER should come after NEIGHBOR.
     662                 :      338594 :   int comparison = lookup_clobber (group->m_clobber_tree, clobber->insn ());
     663                 :      338594 :   gcc_checking_assert (comparison != 0);
     664                 :      338594 :   clobber_info *neighbor = group->m_clobber_tree.root ();
     665                 :             : 
     666                 :             :   // Since HEIGHBOR is now the root of the splay tree, its group needs
     667                 :             :   // to be up-to-date.
     668                 :      338594 :   neighbor->update_group (group);
     669                 :             : 
     670                 :             :   // If CLOBBER comes before NEIGHBOR, insert CLOBBER to NEIGHBOR's left,
     671                 :             :   // otherwise insert CLOBBER to NEIGHBOR's right.
     672                 :      338594 :   clobber_info::splay_tree::insert_child (neighbor, comparison > 0, clobber);
     673                 :      338594 :   clobber->set_group (group);
     674                 :             : 
     675                 :             :   // Insert the clobber into the function-wide list and update the
     676                 :             :   // bounds of the group.
     677                 :      338594 :   if (comparison > 0)
     678                 :             :     {
     679                 :       26710 :       insert_def_after (clobber, neighbor);
     680                 :       26710 :       if (neighbor == group->last_clobber ())
     681                 :           0 :         group->set_last_clobber (clobber);
     682                 :             :     }
     683                 :             :   else
     684                 :             :     {
     685                 :      311884 :       insert_def_before (clobber, neighbor);
     686                 :      311884 :       if (neighbor == group->first_clobber ())
     687                 :           0 :         group->set_first_clobber (clobber);
     688                 :             :     }
     689                 :      338594 : }
     690                 :             : 
     691                 :             : // Remove CLOBBER from GROUP, given that GROUP contains other clobbers too.
     692                 :             : // Also remove CLOBBER from the function's list of accesses to
     693                 :             : // CLOBBER->resource ().
     694                 :             : void
     695                 :      794006 : function_info::remove_clobber (clobber_info *clobber, clobber_group *group)
     696                 :             : {
     697                 :      794006 :   if (clobber == group->first_clobber ())
     698                 :             :     {
     699                 :      532040 :       auto *new_first = as_a<clobber_info *> (clobber->next_def ());
     700                 :      266020 :       group->set_first_clobber (new_first);
     701                 :      266020 :       new_first->update_group (group);
     702                 :             :     }
     703                 :      527986 :   else if (clobber == group->last_clobber ())
     704                 :             :     {
     705                 :      304486 :       auto *new_last = as_a<clobber_info *> (clobber->prev_def ());
     706                 :      152243 :       group->set_last_clobber (new_last);
     707                 :      152243 :       new_last->update_group (group);
     708                 :             :     }
     709                 :             : 
     710                 :      794006 :   clobber_info *replacement = clobber_info::splay_tree::remove_node (clobber);
     711                 :      794006 :   if (clobber == group->m_clobber_tree.root ())
     712                 :             :     {
     713                 :      337986 :       group->m_clobber_tree = replacement;
     714                 :      337986 :       replacement->update_group (group);
     715                 :             :     }
     716                 :      794006 :   clobber->set_group (nullptr);
     717                 :             : 
     718                 :      794006 :   remove_def_from_list (clobber);
     719                 :      794006 : }
     720                 :             : 
     721                 :             : // Add CLOBBER immediately before the first clobber in GROUP, given that
     722                 :             : // CLOBBER is not currently part of any group.
     723                 :             : void
     724                 :      216694 : function_info::prepend_clobber_to_group (clobber_info *clobber,
     725                 :             :                                          clobber_group *group)
     726                 :             : {
     727                 :      216694 :   clobber_info *next = group->first_clobber ();
     728                 :      216694 :   clobber_info::splay_tree::insert_child (next, 0, clobber);
     729                 :      216694 :   group->set_first_clobber (clobber);
     730                 :      216694 :   clobber->set_group (group);
     731                 :      216694 : }
     732                 :             : 
     733                 :             : // Add CLOBBER immediately after the last clobber in GROUP, given that
     734                 :             : // CLOBBER is not currently part of any group.
     735                 :             : void
     736                 :    55253993 : function_info::append_clobber_to_group (clobber_info *clobber,
     737                 :             :                                         clobber_group *group)
     738                 :             : {
     739                 :    55253993 :   clobber_info *prev = group->last_clobber ();
     740                 :    55253993 :   clobber_info::splay_tree::insert_child (prev, 1, clobber);
     741                 :    55253993 :   group->set_last_clobber (clobber);
     742                 :    55253993 :   clobber->set_group (group);
     743                 :    55253993 : }
     744                 :             : 
     745                 :             : // Put CLOBBER1 and CLOBBER2 into the same clobber_group, given that
     746                 :             : // CLOBBER1 occurs immediately before CLOBBER2 and that the two clobbers
     747                 :             : // are not currently in the same group.  LAST is the last definition of
     748                 :             : // the associated resource, and is where any splay tree is stored.
     749                 :             : void
     750                 :        1268 : function_info::merge_clobber_groups (clobber_info *clobber1,
     751                 :             :                                      clobber_info *clobber2,
     752                 :             :                                      def_info *last)
     753                 :             : {
     754                 :        1268 :   if (clobber1->is_in_group () && clobber2->is_in_group ())
     755                 :             :     {
     756                 :         528 :       clobber_group *group1 = clobber1->group ();
     757                 :         528 :       clobber_group *group2 = clobber2->group ();
     758                 :         528 :       gcc_checking_assert (clobber1 == group1->last_clobber ()
     759                 :             :                            && clobber2 == group2->first_clobber ());
     760                 :             : 
     761                 :         528 :       if (def_splay_tree tree = last->splay_root ())
     762                 :             :         {
     763                 :             :           // Remove GROUP2 from the splay tree.
     764                 :         170 :           int comparison = lookup_def (tree, clobber2->insn ());
     765                 :         170 :           gcc_checking_assert (comparison == 0);
     766                 :         170 :           tree.remove_root ();
     767                 :         170 :           last->set_splay_root (tree.root ());
     768                 :             :         }
     769                 :             : 
     770                 :             :       // Splice the trees together.
     771                 :         528 :       group1->m_clobber_tree.splice_next_tree (group2->m_clobber_tree);
     772                 :             : 
     773                 :             :       // Bring the two extremes of GROUP2 under GROUP1.  Any other
     774                 :             :       // clobbers in the group are updated lazily on demand.
     775                 :         528 :       clobber2->set_group (group1);
     776                 :         528 :       group2->last_clobber ()->set_group (group1);
     777                 :         528 :       group1->set_last_clobber (group2->last_clobber ());
     778                 :             : 
     779                 :             :       // Record that GROUP2 is no more.
     780                 :         528 :       group2->set_first_clobber (nullptr);
     781                 :         528 :       group2->set_last_clobber (nullptr);
     782                 :         528 :       group2->m_clobber_tree = nullptr;
     783                 :             :     }
     784                 :             :   else
     785                 :             :     {
     786                 :             :       // In this case there can be no active splay tree.
     787                 :         740 :       gcc_assert (!last->splay_root ());
     788                 :         740 :       if (clobber2->is_in_group ())
     789                 :          64 :         prepend_clobber_to_group (clobber1, clobber2->group ());
     790                 :             :       else
     791                 :         676 :         append_clobber_to_group (clobber2, need_clobber_group (clobber1));
     792                 :             :     }
     793                 :        1268 : }
     794                 :             : 
     795                 :             : // GROUP spans INSN, and INSN now sets the resource that GROUP clobbers.
     796                 :             : // Split GROUP around INSN, to form two new groups.  The first of the
     797                 :             : // returned groups comes before INSN and the second comes after INSN.
     798                 :             : //
     799                 :             : // The caller is responsible for updating the def_splay_tree and chaining
     800                 :             : // the defs together.
     801                 :             : std::array<clobber_group *, 2>
     802                 :           3 : function_info::split_clobber_group (clobber_group *group, insn_info *insn)
     803                 :             : {
     804                 :             :   // Search for either the previous or next clobber in the group.
     805                 :             :   // The result is less than zero if CLOBBER should come before NEIGHBOR
     806                 :             :   // or greater than zero if CLOBBER should come after NEIGHBOR.
     807                 :           3 :   clobber_tree &tree1 = group->m_clobber_tree;
     808                 :           3 :   int comparison = lookup_clobber (tree1, insn);
     809                 :           3 :   gcc_checking_assert (comparison != 0);
     810                 :           3 :   clobber_info *neighbor = tree1.root ();
     811                 :             : 
     812                 :           3 :   clobber_tree tree2;
     813                 :           3 :   clobber_info *prev;
     814                 :           3 :   clobber_info *next;
     815                 :           3 :   if (comparison > 0)
     816                 :             :     {
     817                 :             :       // NEIGHBOR is the last clobber in what will become the first group.
     818                 :           0 :       tree2 = tree1.split_after_root ();
     819                 :           0 :       prev = neighbor;
     820                 :           0 :       next = as_a<clobber_info *> (prev->next_def ());
     821                 :             :     }
     822                 :             :   else
     823                 :             :     {
     824                 :             :       // NEIGHBOR is the first clobber in what will become the second group.
     825                 :           3 :       tree2 = neighbor;
     826                 :           3 :       tree1 = tree2.split_before_root ();
     827                 :           3 :       next = neighbor;
     828                 :           6 :       prev = as_a<clobber_info *> (next->prev_def ());
     829                 :             :     }
     830                 :             : 
     831                 :             :   // Create a new group for each side of the split.  We need to invalidate
     832                 :             :   // the old group so that clobber_info::group can tell whether a lazy
     833                 :             :   // update is needed.
     834                 :           3 :   clobber_info *first_clobber = group->first_clobber ();
     835                 :           3 :   clobber_info *last_clobber = group->last_clobber ();
     836                 :           3 :   auto *group1 = allocate<clobber_group> (first_clobber, prev, tree1.root ());
     837                 :           3 :   auto *group2 = allocate<clobber_group> (next, last_clobber, tree2.root ());
     838                 :             : 
     839                 :             :   // Invalidate the old group.
     840                 :           3 :   group->set_last_clobber (nullptr);
     841                 :             : 
     842                 :           3 :   return { group1, group2 };
     843                 :             : }
     844                 :             : 
     845                 :             : // Add DEF to the end of the function's list of definitions of
     846                 :             : // DEF->resource ().  There is known to be no associated splay tree yet.
     847                 :             : void
     848                 :   326195893 : function_info::append_def (def_info *def)
     849                 :             : {
     850                 :   326195893 :   gcc_checking_assert (!def->has_def_links ());
     851                 :   326195893 :   def_info **head = &m_defs[def->regno () + 1];
     852                 :   326195893 :   def_info *first = *head;
     853                 :   326195893 :   if (!first)
     854                 :             :     {
     855                 :             :       // This is the only definition of the resource.
     856                 :   112086757 :       def->set_last_def (def);
     857                 :   112086757 :       *head = def;
     858                 :   112086757 :       return;
     859                 :             :     }
     860                 :             : 
     861                 :   214109136 :   def_info *prev = first->last_def ();
     862                 :   214109136 :   gcc_checking_assert (!prev->splay_root ());
     863                 :             : 
     864                 :             :   // Maintain the invariant that two clobbers must not appear in
     865                 :             :   // neighboring nodes of the splay tree.
     866                 :   214109136 :   auto *clobber = dyn_cast<clobber_info *> (def);
     867                 :   214109136 :   auto *prev_clobber = dyn_cast<clobber_info *> (prev);
     868                 :   214109136 :   if (clobber && prev_clobber)
     869                 :    55099120 :     append_clobber_to_group (clobber, need_clobber_group (prev_clobber));
     870                 :             : 
     871                 :   214109136 :   prev->set_next_def (def);
     872                 :   214109136 :   def->set_prev_def (prev);
     873                 :   214109136 :   first->set_last_def (def);
     874                 :             : }
     875                 :             : 
     876                 :             : // Add DEF to the function's list of definitions of DEF->resource ().
     877                 :             : // Also insert it into the associated splay tree, if there is one.
     878                 :             : // DEF is not currently part of the list and is not in the splay tree.
     879                 :             : void
     880                 :    58359164 : function_info::add_def (def_info *def)
     881                 :             : {
     882                 :   116718328 :   gcc_checking_assert (!def->has_def_links ()
     883                 :             :                        && !def->m_is_temp
     884                 :             :                        && !def->m_has_been_superceded);
     885                 :    58359164 :   def_info **head = &m_defs[def->regno () + 1];
     886                 :    58359164 :   def_info *first = *head;
     887                 :    58359164 :   if (!first)
     888                 :             :     {
     889                 :             :       // This is the only definition of the resource.
     890                 :       15637 :       def->set_last_def (def);
     891                 :       15637 :       *head = def;
     892                 :       15637 :       return;
     893                 :             :     }
     894                 :             : 
     895                 :    58343527 :   def_info *last = first->last_def ();
     896                 :    58343527 :   insn_info *insn = def->insn ();
     897                 :             : 
     898                 :    58343527 :   int comparison;
     899                 :    58343527 :   def_node *neighbor = nullptr;
     900                 :    58343527 :   def_info *prev = nullptr;
     901                 :    58343527 :   def_info *next = nullptr;
     902                 :    58343527 :   if (*insn > *last->insn ())
     903                 :             :     {
     904                 :             :       // This definition comes after all other definitions.
     905                 :    57490762 :       comparison = 1;
     906                 :    57490762 :       if (def_splay_tree tree = last->splay_root ())
     907                 :             :         {
     908                 :       15290 :           tree.splay_max_node ();
     909                 :       15290 :           last->set_splay_root (tree.root ());
     910                 :       15290 :           neighbor = tree.root ();
     911                 :             :         }
     912                 :    57490762 :       prev = last;
     913                 :             :     }
     914                 :      852765 :   else if (*insn < *first->insn ())
     915                 :             :     {
     916                 :             :       // This definition comes before all other definitions.
     917                 :       66638 :       comparison = -1;
     918                 :       66638 :       if (def_splay_tree tree = last->splay_root ())
     919                 :             :         {
     920                 :       13227 :           tree.splay_min_node ();
     921                 :       13227 :           last->set_splay_root (tree.root ());
     922                 :       13227 :           neighbor = tree.root ();
     923                 :             :         }
     924                 :       66638 :       next = first;
     925                 :             :     }
     926                 :             :   else
     927                 :             :     {
     928                 :             :       // Search the splay tree for an insertion point.
     929                 :      786127 :       def_splay_tree tree = need_def_splay_tree (last);
     930                 :      786127 :       comparison = lookup_def (tree, insn);
     931                 :      786127 :       last->set_splay_root (tree.root ());
     932                 :      786127 :       neighbor = tree.root ();
     933                 :             : 
     934                 :             :       // Deal with cases in which we found an overlapping live range.
     935                 :      786127 :       if (comparison == 0)
     936                 :             :         {
     937                 :      338597 :           auto *group = as_a<clobber_group *> (tree.root ());
     938                 :      338597 :           if (auto *clobber = dyn_cast<clobber_info *> (def))
     939                 :             :             {
     940                 :      338594 :               add_clobber (clobber, group);
     941                 :      338594 :               return;
     942                 :             :             }
     943                 :           3 :           auto new_groups = split_clobber_group (group, insn);
     944                 :             : 
     945                 :             :           // Insert the two new groups immediately after GROUP.
     946                 :           3 :           def_splay_tree::insert_child (group, 1, new_groups[1]);
     947                 :           3 :           def_splay_tree::insert_child (group, 1, new_groups[0]);
     948                 :             : 
     949                 :             :           // Remove GROUP.
     950                 :           3 :           tree.remove_root ();
     951                 :           3 :           last->set_splay_root (tree.root ());
     952                 :             : 
     953                 :           3 :           prev = new_groups[0]->last_clobber ();
     954                 :           3 :           next = new_groups[1]->first_clobber ();
     955                 :             : 
     956                 :             :           // DEF comes after the first group.  (new_groups[1] and -1 would
     957                 :             :           // also work.)
     958                 :           3 :           neighbor = new_groups[0];
     959                 :           3 :           comparison = 1;
     960                 :             :         }
     961                 :             :       // COMPARISON is < 0 if DEF comes before NEIGHBOR or > 0 if DEF comes
     962                 :             :       // after NEIGHBOR.
     963                 :      447530 :       else if (comparison < 0)
     964                 :             :         {
     965                 :      218941 :           next = first_def (neighbor);
     966                 :      666474 :           prev = next->prev_def ();
     967                 :             :         }
     968                 :             :       else
     969                 :             :         {
     970                 :      228589 :           prev = last_def (neighbor);
     971                 :      676122 :           next = prev->next_def ();
     972                 :             :         }
     973                 :             :     }
     974                 :             : 
     975                 :             :   // See if we should merge CLOBBER with a neighboring clobber.
     976                 :    58004933 :   auto *clobber = dyn_cast<clobber_info *> (def);
     977                 :    58004933 :   auto *prev_clobber = safe_dyn_cast<clobber_info *> (prev);
     978                 :    58004933 :   auto *next_clobber = safe_dyn_cast<clobber_info *> (next);
     979                 :             :   // We shouldn't have consecutive clobber_groups.
     980                 :    58004933 :   gcc_checking_assert (!(clobber && prev_clobber && next_clobber));
     981                 :    58004933 :   if (clobber && prev_clobber)
     982                 :      154197 :     append_clobber_to_group (clobber, need_clobber_group (prev_clobber));
     983                 :    57850736 :   else if (clobber && next_clobber)
     984                 :      216630 :     prepend_clobber_to_group (clobber, need_clobber_group (next_clobber));
     985                 :    57634106 :   else if (neighbor)
     986                 :             :     {
     987                 :             :       // If DEF comes before NEIGHBOR, insert DEF to NEIGHBOR's left,
     988                 :             :       // otherwise insert DEF to NEIGHBOR's right.
     989                 :      149143 :       def_node *node = need_def_node (def);
     990                 :      149143 :       def_splay_tree::insert_child (neighbor, comparison >= 0, node);
     991                 :             :     }
     992                 :    58004933 :   if (prev)
     993                 :    57938295 :     insert_def_after (def, prev);
     994                 :             :   else
     995                 :       66638 :     insert_def_before (def, next);
     996                 :             : }
     997                 :             : 
     998                 :             : // Remove DEF from the function's list of definitions of DEF->resource ().
     999                 :             : // Also remove DEF from the associated splay tree, if there is one.
    1000                 :             : void
    1001                 :    10028029 : function_info::remove_def (def_info *def)
    1002                 :             : {
    1003                 :    10028029 :   def_info **head = &m_defs[def->regno () + 1];
    1004                 :    10028029 :   def_info *first = *head;
    1005                 :    10028029 :   gcc_checking_assert (first);
    1006                 :    10028029 :   if (first->is_last_def ())
    1007                 :             :     {
    1008                 :             :       // DEF is the only definition of the resource.
    1009                 :     1681172 :       gcc_checking_assert (first == def);
    1010                 :     1681172 :       *head = nullptr;
    1011                 :     1681172 :       def->clear_def_links ();
    1012                 :     1681172 :       return;
    1013                 :             :     }
    1014                 :             : 
    1015                 :             :   // If CLOBBER belongs to a clobber_group that contains other clobbers
    1016                 :             :   // too, then we need to update the clobber_group and the list, but any
    1017                 :             :   // splay tree that contains the clobber_group is unaffected.
    1018                 :     8346857 :   if (auto *clobber = dyn_cast<clobber_info *> (def))
    1019                 :     1023613 :     if (clobber->is_in_group ())
    1020                 :             :       {
    1021                 :      885351 :         clobber_group *group = clobber->group ();
    1022                 :      885351 :         if (group->first_clobber () != group->last_clobber ())
    1023                 :             :           {
    1024                 :      794006 :             remove_clobber (clobber, group);
    1025                 :      794006 :             return;
    1026                 :             :           }
    1027                 :             :       }
    1028                 :             : 
    1029                 :             :   // If we've created a splay tree for this resource, remove the entry
    1030                 :             :   // for DEF.
    1031                 :     7552851 :   def_info *last = first->last_def ();
    1032                 :     7552851 :   if (def_splay_tree tree = last->splay_root ())
    1033                 :             :     {
    1034                 :       96665 :       int comparison = lookup_def (tree, def->insn ());
    1035                 :       96665 :       gcc_checking_assert (comparison == 0);
    1036                 :       96665 :       tree.remove_root ();
    1037                 :       96665 :       last->set_splay_root (tree.root ());
    1038                 :             :     }
    1039                 :             : 
    1040                 :             :   // If the definition came between two clobbers, merge them into a single
    1041                 :             :   // group.
    1042                 :     7552851 :   auto *prev_clobber = safe_dyn_cast<clobber_info *> (def->prev_def ());
    1043                 :     7552851 :   auto *next_clobber = safe_dyn_cast<clobber_info *> (def->next_def ());
    1044                 :     7552851 :   if (prev_clobber && next_clobber)
    1045                 :        1268 :     merge_clobber_groups (prev_clobber, next_clobber, last);
    1046                 :             : 
    1047                 :     7552851 :   remove_def_from_list (def);
    1048                 :             : }
    1049                 :             : 
    1050                 :             : // Require DEF to have a splay tree that contains all non-phi uses.
    1051                 :             : void
    1052                 :     3802016 : function_info::need_use_splay_tree (set_info *def)
    1053                 :             : {
    1054                 :     3802016 :   if (!def->m_use_tree)
    1055                 :    33548689 :     for (use_info *use : def->all_insn_uses ())
    1056                 :             :       {
    1057                 :    30764113 :         auto *use_node = allocate<splay_tree_node<use_info *>> (use);
    1058                 :    30764113 :         def->m_use_tree.insert_max_node (use_node);
    1059                 :             :       }
    1060                 :     3802016 : }
    1061                 :             : 
    1062                 :             : // Compare two instructions by their position in a use splay tree.  Return >0
    1063                 :             : // if INSN1 comes after INSN2, <0 if INSN1 comes before INSN2, or 0 if they are
    1064                 :             : // the same instruction.
    1065                 :             : static inline int
    1066                 :   631115802 : compare_use_insns (insn_info *insn1, insn_info *insn2)
    1067                 :             : {
    1068                 :             :   // Debug instructions go after nondebug instructions.
    1069                 :   631115802 :   int diff = insn1->is_debug_insn () - insn2->is_debug_insn ();
    1070                 :   631115802 :   if (diff != 0)
    1071                 :             :     return diff;
    1072                 :   583802701 :   return insn1->compare_with (insn2);
    1073                 :             : }
    1074                 :             : 
    1075                 :             : // Search TREE for a use in INSN.  If such a use exists, install it as
    1076                 :             : // the root of TREE and return 0.  Otherwise arbitrarily choose between:
    1077                 :             : //
    1078                 :             : // (1) Installing the closest preceding use as the root and returning 1.
    1079                 :             : // (2) Installing the closest following use as the root and returning -1.
    1080                 :             : int
    1081                 :     5339706 : rtl_ssa::lookup_use (splay_tree<use_info *> &tree, insn_info *insn)
    1082                 :             : {
    1083                 :    51094344 :   auto compare = [&](splay_tree_node<use_info *> *node)
    1084                 :             :     {
    1085                 :    45754638 :       return compare_use_insns (insn, node->value ()->insn ());
    1086                 :     5339706 :     };
    1087                 :     5339706 :   return tree.lookup (compare);
    1088                 :             : }
    1089                 :             : 
    1090                 :             : // Add USE to USE->def ()'s list of uses. inserting USE immediately before
    1091                 :             : // BEFORE.  USE is not currently in the list.
    1092                 :             : //
    1093                 :             : // This routine should not be used for inserting phi uses.
    1094                 :             : void
    1095                 :    13611200 : function_info::insert_use_before (use_info *use, use_info *before)
    1096                 :             : {
    1097                 :    27222400 :   gcc_checking_assert (!use->has_use_links () && use->is_in_any_insn ());
    1098                 :             : 
    1099                 :    13611200 :   set_info *def = use->def ();
    1100                 :             : 
    1101                 :    13611200 :   use->copy_prev_from (before);
    1102                 :    13611200 :   use->set_next_use (before);
    1103                 :             : 
    1104                 :    13611200 :   if (use_info *prev = use->prev_use ())
    1105                 :     1461585 :     prev->set_next_use (use);
    1106                 :             :   else
    1107                 :    12177845 :     use->def ()->set_first_use (use);
    1108                 :             : 
    1109                 :    13611200 :   before->set_prev_use (use);
    1110                 :    13611200 :   if (use->is_in_nondebug_insn () && before->is_in_debug_insn_or_phi ())
    1111                 :    22196982 :     def->last_use ()->set_last_nondebug_insn_use (use);
    1112                 :             : 
    1113                 :    13611200 :   gcc_checking_assert (use->check_integrity () && before->check_integrity ());
    1114                 :    13611200 : }
    1115                 :             : 
    1116                 :             : // Add USE to USE->def ()'s list of uses. inserting USE immediately after
    1117                 :             : // AFTER.  USE is not currently in the list.
    1118                 :             : //
    1119                 :             : // This routine should not be used for inserting phi uses.
    1120                 :             : void
    1121                 :   287783109 : function_info::insert_use_after (use_info *use, use_info *after)
    1122                 :             : {
    1123                 :   287783109 :   set_info *def = use->def ();
    1124                 :   575566218 :   gcc_checking_assert (after->is_in_any_insn ()
    1125                 :             :                        && !use->has_use_links ()
    1126                 :             :                        && use->is_in_any_insn ());
    1127                 :             : 
    1128                 :   287783109 :   use->set_prev_use (after);
    1129                 :   287783109 :   use->copy_next_from (after);
    1130                 :             : 
    1131                 :   287783109 :   after->set_next_use (use);
    1132                 :             : 
    1133                 :   287783109 :   if (use_info *next = use->next_use ())
    1134                 :             :     {
    1135                 :             :       // The last node doesn't change, but we might need to update its
    1136                 :             :       // last_nondebug_insn_use record.
    1137                 :    55344602 :       if (use->is_in_nondebug_insn () && next->is_in_debug_insn_or_phi ())
    1138                 :   106648060 :         def->last_use ()->set_last_nondebug_insn_use (use);
    1139                 :    55344602 :       next->set_prev_use (use);
    1140                 :             :     }
    1141                 :             :   else
    1142                 :             :     {
    1143                 :             :       // USE is now the last node.
    1144                 :   232438507 :       if (use->is_in_nondebug_insn ())
    1145                 :   203672234 :         use->set_last_nondebug_insn_use (use);
    1146                 :   232438507 :       def->first_use ()->set_last_use (use);
    1147                 :             :     }
    1148                 :             : 
    1149                 :   287783109 :   gcc_checking_assert (use->check_integrity () && after->check_integrity ());
    1150                 :   287783109 : }
    1151                 :             : 
    1152                 :             : // If USE has a known definition, add USE to that definition's list of uses.
    1153                 :             : // Also update the associated splay tree, if any.
    1154                 :             : void
    1155                 :   683140278 : function_info::add_use (use_info *use)
    1156                 :             : {
    1157                 :  1366280556 :   gcc_checking_assert (!use->has_use_links ()
    1158                 :             :                        && !use->m_is_temp
    1159                 :             :                        && !use->m_has_been_superceded);
    1160                 :             : 
    1161                 :   683140278 :   set_info *def = use->def ();
    1162                 :   683140278 :   if (!def)
    1163                 :   679338262 :     return;
    1164                 :             : 
    1165                 :   645806577 :   use_info *first = def->first_use ();
    1166                 :   645806577 :   if (!first)
    1167                 :             :     {
    1168                 :             :       // This is the only use of the definition.
    1169                 :   272225828 :       use->set_last_use (use);
    1170                 :   272225828 :       if (use->is_in_nondebug_insn ())
    1171                 :   238901009 :         use->set_last_nondebug_insn_use (use);
    1172                 :             : 
    1173                 :   272225828 :       def->set_first_use (use);
    1174                 :             : 
    1175                 :   272225828 :       gcc_checking_assert (use->check_integrity ());
    1176                 :             :       return;
    1177                 :             :     }
    1178                 :             : 
    1179                 :   373580749 :   if (use->is_in_phi ())
    1180                 :             :     {
    1181                 :             :       // Add USE at the end of the list, as the new first phi.
    1182                 :    72186440 :       use_info *last = first->last_use ();
    1183                 :             : 
    1184                 :    72186440 :       use->set_prev_use (last);
    1185                 :    72186440 :       use->copy_next_from (last);
    1186                 :             : 
    1187                 :    72186440 :       last->set_next_use (use);
    1188                 :    72186440 :       first->set_last_use (use);
    1189                 :             : 
    1190                 :    72186440 :       gcc_checking_assert (use->check_integrity ());
    1191                 :             :       return;
    1192                 :             :     }
    1193                 :             : 
    1194                 :             :   // If there is currently no splay tree for this definition, see if can
    1195                 :             :   // get away with a pure list-based update.
    1196                 :   301394309 :   insn_info *insn = use->insn ();
    1197                 :   600378890 :   auto quick_path = [&]()
    1198                 :             :     {
    1199                 :             :       // Check if USE should come before all current uses.
    1200                 :   298984581 :       if (first->is_in_phi () || compare_use_insns (insn, first->insn ()) < 0)
    1201                 :             :         {
    1202                 :    12052866 :           insert_use_before (use, first);
    1203                 :    12052866 :           return true;
    1204                 :             :         }
    1205                 :             : 
    1206                 :             :       // Check if USE should come after all current uses in the same
    1207                 :             :       // subsequence (i.e. the list of nondebug insn uses or the list
    1208                 :             :       // of debug insn uses).
    1209                 :   286931715 :       use_info *last = first->last_use ();
    1210                 :   286931715 :       if (use->is_in_debug_insn ())
    1211                 :             :         {
    1212                 :    29100103 :           if (last->is_in_phi ())
    1213                 :             :             return false;
    1214                 :             :         }
    1215                 :             :       else
    1216                 :   257831612 :         last = last->last_nondebug_insn_use ();
    1217                 :             : 
    1218                 :   286595749 :       if (compare_use_insns (insn, last->insn ()) > 0)
    1219                 :             :         {
    1220                 :   285539427 :           insert_use_after (use, last);
    1221                 :   285539427 :           return true;
    1222                 :             :         }
    1223                 :             : 
    1224                 :             :       return false;
    1225                 :   301394309 :     };
    1226                 :   301394309 :   if (!def->m_use_tree && quick_path ())
    1227                 :             :     return;
    1228                 :             : 
    1229                 :             :   // Search the splay tree for an insertion point.  COMPARISON is less
    1230                 :             :   // than zero if USE should come before NEIGHBOR, or greater than zero
    1231                 :             :   // if USE should come after NEIGHBOR.
    1232                 :     3802016 :   need_use_splay_tree (def);
    1233                 :     3802016 :   int comparison = lookup_use (def->m_use_tree, insn);
    1234                 :     3802016 :   gcc_checking_assert (comparison != 0);
    1235                 :     3802016 :   use_info *neighbor = def->m_use_tree.root ()->value ();
    1236                 :             : 
    1237                 :             :   // If USE comes before NEIGHBOR, insert USE to NEIGHBOR's left,
    1238                 :             :   // otherwise insert USE to NEIGHBOR's right.
    1239                 :     3802016 :   auto *use_node = allocate<splay_tree_node<use_info *>> (use);
    1240                 :     3802016 :   def->m_use_tree.insert_relative (comparison, use_node);
    1241                 :     3802016 :   if (comparison > 0)
    1242                 :     2243682 :     insert_use_after (use, neighbor);
    1243                 :             :   else
    1244                 :     1558334 :     insert_use_before (use, neighbor);
    1245                 :             : }
    1246                 :             : 
    1247                 :             : void
    1248                 :           0 : function_info::reparent_use (use_info *use, set_info *new_def)
    1249                 :             : {
    1250                 :           0 :   remove_use (use);
    1251                 :           0 :   use->set_def (new_def);
    1252                 :           0 :   add_use (use);
    1253                 :           0 : }
    1254                 :             : 
    1255                 :             : // If USE has a known definition, remove USE from that definition's list
    1256                 :             : // of uses.  Also remove if it from the associated splay tree, if any.
    1257                 :             : void
    1258                 :    30385822 : function_info::remove_use (use_info *use)
    1259                 :             : {
    1260                 :    30385822 :   set_info *def = use->def ();
    1261                 :    30385822 :   if (!def)
    1262                 :             :     return;
    1263                 :             : 
    1264                 :             :   // Remove USE from the splay tree.
    1265                 :    30301408 :   if (def->m_use_tree && use->is_in_any_insn ())
    1266                 :             :     {
    1267                 :     1537690 :       int comparison = lookup_use (def->m_use_tree, use->insn ());
    1268                 :     1537690 :       gcc_checking_assert (comparison == 0);
    1269                 :     1537690 :       def->m_use_tree.remove_root ();
    1270                 :             :     }
    1271                 :             : 
    1272                 :    30301408 :   use_info *prev = use->prev_use ();
    1273                 :    30301408 :   use_info *next = use->next_use ();
    1274                 :             : 
    1275                 :    30301408 :   use_info *first = def->first_use ();
    1276                 :    30301408 :   use_info *last = first->last_use ();
    1277                 :    30301408 :   if (last->last_nondebug_insn_use () == use)
    1278                 :     9481554 :     last->set_last_nondebug_insn_use (prev);
    1279                 :             : 
    1280                 :    30301408 :   if (next)
    1281                 :    12886356 :     next->copy_prev_from (use);
    1282                 :             :   else
    1283                 :    17415052 :     first->set_last_use (prev);
    1284                 :             : 
    1285                 :    30301408 :   if (prev)
    1286                 :    15181877 :     prev->copy_next_from (use);
    1287                 :             :   else
    1288                 :    30239062 :     def->set_first_use (next);
    1289                 :             : 
    1290                 :    30301408 :   use->clear_use_links ();
    1291                 :    30301408 :   gcc_checking_assert ((!prev || prev->check_integrity ())
    1292                 :             :                        && (!next || next->check_integrity ()));
    1293                 :             : }
    1294                 :             : 
    1295                 :             : // Allocate a temporary clobber_info for register REGNO in insn INSN,
    1296                 :             : // including it in the region of the obstack governed by WATERMARK.
    1297                 :             : // Return a new def_array that contains OLD_DEFS and the new clobber.
    1298                 :             : //
    1299                 :             : // OLD_DEFS is known not to define REGNO.
    1300                 :             : def_array
    1301                 :     1835951 : function_info::insert_temp_clobber (obstack_watermark &watermark,
    1302                 :             :                                     insn_info *insn, unsigned int regno,
    1303                 :             :                                     def_array old_defs)
    1304                 :             : {
    1305                 :     1835951 :   gcc_checking_assert (watermark == &m_temp_obstack);
    1306                 :     1835951 :   auto *clobber = allocate_temp<clobber_info> (insn, regno);
    1307                 :     1835951 :   clobber->m_is_temp = true;
    1308                 :     1835951 :   return insert_access (watermark, clobber, old_defs);
    1309                 :             : }
    1310                 :             : 
    1311                 :             : // See the comment above the declaration.
    1312                 :             : bool
    1313                 :     4251728 : function_info::remains_available_at_insn (const set_info *set,
    1314                 :             :                                           insn_info *insn)
    1315                 :             : {
    1316                 :     4251728 :   auto *ebb = set->ebb ();
    1317                 :     4251728 :   gcc_checking_assert (ebb == insn->ebb ());
    1318                 :             : 
    1319                 :     4251728 :   def_info *next_def = set->next_def ();
    1320                 :     3959736 :   if (next_def && *next_def->insn () < *insn)
    1321                 :             :     return false;
    1322                 :             : 
    1323                 :     3634769 :   if (HARD_REGISTER_NUM_P (set->regno ())
    1324                 :     3634769 :       && TEST_HARD_REG_BIT (m_clobbered_by_calls, set->regno ()))
    1325                 :      278541 :     for (ebb_call_clobbers_info *call_group : ebb->call_clobbers ())
    1326                 :             :       {
    1327                 :       53086 :         if (!call_group->clobbers (set->resource ()))
    1328                 :         876 :           continue;
    1329                 :             : 
    1330                 :       52210 :         insn_info *call_insn = next_call_clobbers (*call_group, insn);
    1331                 :       52210 :         if (call_insn && *call_insn < *insn)
    1332                 :      616959 :           return false;
    1333                 :             :       }
    1334                 :             : 
    1335                 :             :   return true;
    1336                 :             : }
    1337                 :             : 
    1338                 :             : // See the comment above the declaration.
    1339                 :             : bool
    1340                 :      418423 : function_info::remains_available_on_exit (const set_info *set, bb_info *bb)
    1341                 :             : {
    1342                 :      418423 :   if (HARD_REGISTER_NUM_P (set->regno ())
    1343                 :      418423 :       && TEST_HARD_REG_BIT (m_clobbered_by_calls, set->regno ()))
    1344                 :             :     {
    1345                 :       33456 :       insn_info *search_insn = (set->bb () == bb
    1346                 :       33456 :                                 ? set->insn ()
    1347                 :        2091 :                                 : bb->head_insn ());
    1348                 :       41503 :       for (ebb_call_clobbers_info *call_group : bb->ebb ()->call_clobbers ())
    1349                 :             :         {
    1350                 :       10528 :           if (!call_group->clobbers (set->resource ()))
    1351                 :           4 :             continue;
    1352                 :             : 
    1353                 :       10524 :           insn_info *insn = next_call_clobbers (*call_group, search_insn);
    1354                 :       10524 :           if (insn && insn->bb () == bb)
    1355                 :       88757 :             return false;
    1356                 :             :         }
    1357                 :             :     }
    1358                 :             : 
    1359                 :      415942 :   return (set->is_last_def ()
    1360                 :      814864 :           || *set->next_def ()->insn () > *bb->end_insn ());
    1361                 :             : }
    1362                 :             : 
    1363                 :             : // A subroutine of make_uses_available.  Try to make USE's definition
    1364                 :             : // available at the head of BB.  WILL_BE_DEBUG_USE is true if the
    1365                 :             : // definition will be used only in debug instructions.
    1366                 :             : //
    1367                 :             : // On success:
    1368                 :             : //
    1369                 :             : // - If the use would have the same def () as USE, return USE.
    1370                 :             : //
    1371                 :             : // - If BB already has a degenerate phi for the same definition,
    1372                 :             : //   return a temporary use of that phi.
    1373                 :             : //
    1374                 :             : // - Otherwise, the use would need a new degenerate phi.  Allocate a
    1375                 :             : //   temporary phi and return a temporary use of it.
    1376                 :             : //
    1377                 :             : // Return null on failure.
    1378                 :             : use_info *
    1379                 :    17772315 : function_info::make_use_available (use_info *use, bb_info *bb,
    1380                 :             :                                    bool will_be_debug_use)
    1381                 :             : {
    1382                 :    17772315 :   set_info *def = use->def ();
    1383                 :    17772315 :   if (!def)
    1384                 :             :     return use;
    1385                 :             : 
    1386                 :    17720965 :   if (is_single_dominating_def (def))
    1387                 :             :     return use;
    1388                 :             : 
    1389                 :     7130178 :   if (def->ebb () == bb->ebb ())
    1390                 :             :     {
    1391                 :     4251728 :       if (remains_available_at_insn (def, bb->head_insn ()))
    1392                 :             :         return use;
    1393                 :             :       return nullptr;
    1394                 :             :     }
    1395                 :             : 
    1396                 :     2878450 :   basic_block cfg_bb = bb->cfg_bb ();
    1397                 :     2878450 :   bb_info *use_bb = use->bb ();
    1398                 :     2878450 :   if (single_pred_p (cfg_bb)
    1399                 :     1765979 :       && single_pred (cfg_bb) == use_bb->cfg_bb ()
    1400                 :     3296873 :       && remains_available_on_exit (def, use_bb))
    1401                 :             :     {
    1402                 :      329666 :       if (will_be_debug_use)
    1403                 :             :         return use;
    1404                 :             : 
    1405                 :      290642 :       resource_info resource = use->resource ();
    1406                 :      290642 :       set_info *ultimate_def = look_through_degenerate_phi (def);
    1407                 :             : 
    1408                 :             :       // See if there is already a (degenerate) phi for DEF.
    1409                 :      290642 :       insn_info *phi_insn = bb->ebb ()->phi_insn ();
    1410                 :      290642 :       phi_info *phi;
    1411                 :      290642 :       def_lookup dl = find_def (resource, phi_insn);
    1412                 :      290642 :       if (set_info *set = dl.matching_set ())
    1413                 :             :         {
    1414                 :             :           // There is an existing phi.
    1415                 :      127236 :           phi = as_a<phi_info *> (set);
    1416                 :      127236 :           gcc_checking_assert (phi->input_value (0) == ultimate_def);
    1417                 :             :         }
    1418                 :             :       else
    1419                 :             :         {
    1420                 :             :           // Create a temporary placeholder phi.  This will become
    1421                 :             :           // permanent if the change is later committed.
    1422                 :      163406 :           phi = allocate_temp<phi_info> (phi_insn, resource, 0);
    1423                 :      163406 :           auto *input = allocate_temp<use_info> (phi, resource, ultimate_def);
    1424                 :      163406 :           input->m_is_temp = true;
    1425                 :      163406 :           phi->m_is_temp = true;
    1426                 :      163406 :           phi->make_degenerate (input);
    1427                 :      163406 :           if (def_info *prev = dl.prev_def (phi_insn))
    1428                 :      163406 :             phi->set_prev_def (prev);
    1429                 :      163406 :           if (def_info *next = dl.next_def (phi_insn))
    1430                 :      142532 :             phi->set_next_def (next);
    1431                 :             :         }
    1432                 :             : 
    1433                 :             :       // Create a temporary use of the phi at the head of the first
    1434                 :             :       // block, since we know for sure that it's available there.
    1435                 :      290642 :       insn_info *use_insn = bb->ebb ()->first_bb ()->head_insn ();
    1436                 :      290642 :       auto *new_use = allocate_temp<use_info> (use_insn, resource, phi);
    1437                 :      290642 :       new_use->m_is_temp = true;
    1438                 :      290642 :       return new_use;
    1439                 :             :     }
    1440                 :             :   return nullptr;
    1441                 :             : }
    1442                 :             : 
    1443                 :             : // See the comment above the declaration.
    1444                 :             : use_array
    1445                 :    11190946 : function_info::make_uses_available (obstack_watermark &watermark,
    1446                 :             :                                     use_array uses, bb_info *bb,
    1447                 :             :                                     bool will_be_debug_uses)
    1448                 :             : {
    1449                 :    11190946 :   unsigned int num_uses = uses.size ();
    1450                 :    11190946 :   if (num_uses == 0)
    1451                 :      367726 :     return uses;
    1452                 :             : 
    1453                 :    10823220 :   auto **new_uses = XOBNEWVEC (watermark, access_info *, num_uses);
    1454                 :    25429792 :   for (unsigned int i = 0; i < num_uses; ++i)
    1455                 :             :     {
    1456                 :    17772315 :       use_info *use = make_use_available (uses[i], bb, will_be_debug_uses);
    1457                 :    17772315 :       if (!use)
    1458                 :     3165743 :         return use_array (access_array::invalid ());
    1459                 :    14606572 :       new_uses[i] = use;
    1460                 :             :     }
    1461                 :     7657477 :   return use_array (new_uses, num_uses);
    1462                 :             : }
    1463                 :             : 
    1464                 :             : set_info *
    1465                 :           0 : function_info::create_set (obstack_watermark &watermark,
    1466                 :             :                            insn_info *insn,
    1467                 :             :                            resource_info resource)
    1468                 :             : {
    1469                 :           0 :   auto set = change_alloc<set_info> (watermark, insn, resource);
    1470                 :           0 :   set->m_is_temp = true;
    1471                 :           0 :   return set;
    1472                 :             : }
    1473                 :             : 
    1474                 :             : use_info *
    1475                 :           0 : function_info::create_use (obstack_watermark &watermark,
    1476                 :             :                            insn_info *insn,
    1477                 :             :                            set_info *set)
    1478                 :             : {
    1479                 :           0 :   auto use = change_alloc<use_info> (watermark, insn, set->resource (), set);
    1480                 :           0 :   use->m_is_temp = true;
    1481                 :           0 :   return use;
    1482                 :             : }
    1483                 :             : 
    1484                 :             : // Return true if ACCESS1 can represent ACCESS2 and if ACCESS2 can
    1485                 :             : // represent ACCESS1.
    1486                 :             : static bool
    1487                 :     9204913 : can_merge_accesses (access_info *access1, access_info *access2)
    1488                 :             : {
    1489                 :     9204913 :   if (access1 == access2)
    1490                 :             :     return true;
    1491                 :             : 
    1492                 :     9204913 :   auto *use1 = dyn_cast<use_info *> (access1);
    1493                 :     9204913 :   auto *use2 = dyn_cast<use_info *> (access2);
    1494                 :     9204913 :   return use1 && use2 && use1->def () == use2->def ();
    1495                 :             : }
    1496                 :             : 
    1497                 :             : // See the comment above the declaration.
    1498                 :             : access_array
    1499                 :    56634472 : rtl_ssa::merge_access_arrays_base (obstack_watermark &watermark,
    1500                 :             :                                    access_array accesses1,
    1501                 :             :                                    access_array accesses2)
    1502                 :             : {
    1503                 :    56634472 :   if (accesses1.empty ())
    1504                 :     2104835 :     return accesses2;
    1505                 :    54529637 :   if (accesses2.empty ())
    1506                 :    14557422 :     return accesses1;
    1507                 :             : 
    1508                 :    39972215 :   auto i1 = accesses1.begin ();
    1509                 :    39972215 :   auto end1 = accesses1.end ();
    1510                 :    39972215 :   auto i2 = accesses2.begin ();
    1511                 :    39972215 :   auto end2 = accesses2.end ();
    1512                 :             : 
    1513                 :    39972215 :   access_array_builder builder (watermark);
    1514                 :    39972215 :   builder.reserve (accesses1.size () + accesses2.size ());
    1515                 :             : 
    1516                 :   149807212 :   while (i1 != end1 && i2 != end2)
    1517                 :             :     {
    1518                 :    72196837 :       access_info *access1 = *i1;
    1519                 :    72196837 :       access_info *access2 = *i2;
    1520                 :             : 
    1521                 :    72196837 :       unsigned int regno1 = access1->regno ();
    1522                 :    72196837 :       unsigned int regno2 = access2->regno ();
    1523                 :    72196837 :       if (regno1 == regno2)
    1524                 :             :         {
    1525                 :     9204913 :           if (!can_merge_accesses (access1, access2))
    1526                 :     2334055 :             return access_array::invalid ();
    1527                 :             : 
    1528                 :     6870858 :           builder.quick_push (access1);
    1529                 :     6870858 :           ++i1;
    1530                 :     6870858 :           ++i2;
    1531                 :             :         }
    1532                 :    62991924 :       else if (regno1 < regno2)
    1533                 :             :         {
    1534                 :    35656261 :           builder.quick_push (access1);
    1535                 :    35656261 :           ++i1;
    1536                 :             :         }
    1537                 :             :       else
    1538                 :             :         {
    1539                 :    27335663 :           builder.quick_push (access2);
    1540                 :    27335663 :           ++i2;
    1541                 :             :         }
    1542                 :             :     }
    1543                 :    62500821 :   for (; i1 != end1; ++i1)
    1544                 :    24862661 :     builder.quick_push (*i1);
    1545                 :    57267560 :   for (; i2 != end2; ++i2)
    1546                 :    19629400 :     builder.quick_push (*i2);
    1547                 :             : 
    1548                 :    37638160 :   return builder.finish ();
    1549                 :    39972215 : }
    1550                 :             : 
    1551                 :             : // See the comment above the declaration.
    1552                 :             : access_array
    1553                 :     1835951 : rtl_ssa::insert_access_base (obstack_watermark &watermark,
    1554                 :             :                              access_info *access1, access_array accesses2)
    1555                 :             : {
    1556                 :     1835951 :   access_array_builder builder (watermark);
    1557                 :     1835951 :   builder.reserve (1 + accesses2.size ());
    1558                 :             : 
    1559                 :     1835951 :   unsigned int regno1 = access1->regno ();
    1560                 :     1835951 :   auto i2 = accesses2.begin ();
    1561                 :     1835951 :   auto end2 = accesses2.end ();
    1562                 :     3342669 :   while (i2 != end2)
    1563                 :             :     {
    1564                 :     1837886 :       access_info *access2 = *i2;
    1565                 :             : 
    1566                 :     1837886 :       unsigned int regno2 = access2->regno ();
    1567                 :     1837886 :       if (regno1 == regno2)
    1568                 :             :         {
    1569                 :           0 :           if (!can_merge_accesses (access1, access2))
    1570                 :           0 :             return access_array::invalid ();
    1571                 :             : 
    1572                 :           0 :           builder.quick_push (access1);
    1573                 :           0 :           access1 = nullptr;
    1574                 :           0 :           ++i2;
    1575                 :           0 :           break;
    1576                 :             :         }
    1577                 :     1837886 :       else if (regno1 < regno2)
    1578                 :             :         {
    1579                 :      331168 :           builder.quick_push (access1);
    1580                 :      331168 :           access1 = nullptr;
    1581                 :      331168 :           break;
    1582                 :             :         }
    1583                 :             :       else
    1584                 :             :         {
    1585                 :     1506718 :           builder.quick_push (access2);
    1586                 :     1506718 :           ++i2;
    1587                 :             :         }
    1588                 :             :     }
    1589                 :      331168 :   if (access1)
    1590                 :     1504783 :     builder.quick_push (access1);
    1591                 :     2167119 :   for (; i2 != end2; ++i2)
    1592                 :      331168 :     builder.quick_push (*i2);
    1593                 :             : 
    1594                 :     1835951 :   return builder.finish ();
    1595                 :     1835951 : }
    1596                 :             : 
    1597                 :             : // See the comment above the declaration.
    1598                 :             : use_array
    1599                 :    25806107 : rtl_ssa::remove_uses_of_def (obstack_watermark &watermark, use_array uses,
    1600                 :             :                              def_info *def)
    1601                 :             : {
    1602                 :    25806107 :   access_array_builder uses_builder (watermark);
    1603                 :    25806107 :   uses_builder.reserve (uses.size ());
    1604                 :    70800809 :   for (use_info *use : uses)
    1605                 :    44994702 :     if (use->def () != def)
    1606                 :    19188595 :       uses_builder.quick_push (use);
    1607                 :    25806107 :   return use_array (uses_builder.finish ());
    1608                 :    25806107 : }
    1609                 :             : 
    1610                 :             : // See the comment above the declaration.
    1611                 :             : access_array
    1612                 :    42720224 : rtl_ssa::remove_note_accesses_base (obstack_watermark &watermark,
    1613                 :             :                                     access_array accesses)
    1614                 :             : {
    1615                 :    44817712 :   auto predicate = [](access_info *a) {
    1616                 :     2097488 :     return !a->only_occurs_in_notes ();
    1617                 :             :   };
    1618                 :             : 
    1619                 :    96014062 :   for (access_info *access : accesses)
    1620                 :    54052779 :     if (access->only_occurs_in_notes ())
    1621                 :      758941 :       return filter_accesses (watermark, accesses, predicate);
    1622                 :             : 
    1623                 :    41961283 :   return accesses;
    1624                 :             : }
    1625                 :             : 
    1626                 :             : // See the comment above the declaration.
    1627                 :             : bool
    1628                 :     7629213 : rtl_ssa::accesses_reference_same_resource (access_array accesses1,
    1629                 :             :                                            access_array accesses2)
    1630                 :             : {
    1631                 :     7629213 :   auto i1 = accesses1.begin ();
    1632                 :     7629213 :   auto end1 = accesses1.end ();
    1633                 :     7629213 :   auto i2 = accesses2.begin ();
    1634                 :     7629213 :   auto end2 = accesses2.end ();
    1635                 :             : 
    1636                 :    16528268 :   while (i1 != end1 && i2 != end2)
    1637                 :             :     {
    1638                 :     9470699 :       access_info *access1 = *i1;
    1639                 :     9470699 :       access_info *access2 = *i2;
    1640                 :             : 
    1641                 :     9470699 :       unsigned int regno1 = access1->regno ();
    1642                 :     9470699 :       unsigned int regno2 = access2->regno ();
    1643                 :     9470699 :       if (regno1 == regno2)
    1644                 :             :         return true;
    1645                 :             : 
    1646                 :     8899055 :       if (regno1 < regno2)
    1647                 :     4472247 :         ++i1;
    1648                 :             :       else
    1649                 :     4426808 :         ++i2;
    1650                 :             :     }
    1651                 :             :   return false;
    1652                 :             : }
    1653                 :             : 
    1654                 :             : // See the comment above the declaration.
    1655                 :             : bool
    1656                 :     7629213 : rtl_ssa::insn_clobbers_resources (insn_info *insn, access_array accesses)
    1657                 :             : {
    1658                 :     7629213 :   if (accesses_reference_same_resource (insn->defs (), accesses))
    1659                 :             :     return true;
    1660                 :             : 
    1661                 :     7057569 :   if (insn->is_call () && accesses_include_hard_registers (accesses))
    1662                 :             :     {
    1663                 :         644 :       function_abi abi = insn_callee_abi (insn->rtl ());
    1664                 :         698 :       for (const access_info *access : accesses)
    1665                 :             :         {
    1666                 :         644 :           if (!HARD_REGISTER_NUM_P (access->regno ()))
    1667                 :             :             break;
    1668                 :         644 :           if (abi.clobbers_reg_p (access->mode (), access->regno ()))
    1669                 :         590 :             return true;
    1670                 :             :         }
    1671                 :             :     }
    1672                 :             : 
    1673                 :             :   return false;
    1674                 :             : }
    1675                 :             : 
    1676                 :             : // Print RESOURCE to PP.
    1677                 :             : void
    1678                 :           0 : rtl_ssa::pp_resource (pretty_printer *pp, resource_info resource)
    1679                 :             : {
    1680                 :           0 :   resource.print (pp);
    1681                 :           0 : }
    1682                 :             : 
    1683                 :             : // Print ACCESS to PP.  FLAGS is a bitmask of PP_ACCESS_* flags.
    1684                 :             : void
    1685                 :           0 : rtl_ssa::pp_access (pretty_printer *pp, const access_info *access,
    1686                 :             :                     unsigned int flags)
    1687                 :             : {
    1688                 :           0 :   if (!access)
    1689                 :           0 :     pp_string (pp, "<null>");
    1690                 :           0 :   else if (auto *phi = dyn_cast<const phi_info *> (access))
    1691                 :           0 :     phi->print (pp, flags);
    1692                 :           0 :   else if (auto *set = dyn_cast<const set_info *> (access))
    1693                 :           0 :     set->print (pp, flags);
    1694                 :           0 :   else if (auto *clobber = dyn_cast<const clobber_info *> (access))
    1695                 :           0 :     clobber->print (pp, flags);
    1696                 :           0 :   else if (auto *use = dyn_cast<const use_info *> (access))
    1697                 :           0 :     use->print (pp, flags);
    1698                 :             :   else
    1699                 :             :     pp_string (pp, "??? Unknown access");
    1700                 :           0 : }
    1701                 :             : 
    1702                 :             : // Print ACCESSES to PP.  FLAGS is a bitmask of PP_ACCESS_* flags.
    1703                 :             : void
    1704                 :           0 : rtl_ssa::pp_accesses (pretty_printer *pp, access_array accesses,
    1705                 :             :                       unsigned int flags)
    1706                 :             : {
    1707                 :           0 :   if (accesses.empty ())
    1708                 :           0 :     pp_string (pp, "none");
    1709                 :             :   else
    1710                 :             :     {
    1711                 :           0 :       bool is_first = true;
    1712                 :           0 :       for (access_info *access : accesses)
    1713                 :             :         {
    1714                 :           0 :           if (is_first)
    1715                 :             :             is_first = false;
    1716                 :             :           else
    1717                 :           0 :             pp_newline_and_indent (pp, 0);
    1718                 :           0 :           pp_access (pp, access, flags);
    1719                 :             :         }
    1720                 :             :     }
    1721                 :           0 : }
    1722                 :             : 
    1723                 :             : // Print NODE to PP.
    1724                 :             : void
    1725                 :           0 : rtl_ssa::pp_def_node (pretty_printer *pp, const def_node *node)
    1726                 :             : {
    1727                 :           0 :   if (!node)
    1728                 :           0 :     pp_string (pp, "<null>");
    1729                 :           0 :   else if (auto *group = dyn_cast<const clobber_group *> (node))
    1730                 :           0 :     group->print (pp);
    1731                 :           0 :   else if (auto *set = dyn_cast<const set_node *> (node))
    1732                 :           0 :     set->print (pp);
    1733                 :             :   else
    1734                 :           0 :     pp_string (pp, "??? Unknown def node");
    1735                 :           0 : }
    1736                 :             : 
    1737                 :             : // Print MUX to PP.
    1738                 :             : void
    1739                 :           0 : rtl_ssa::pp_def_mux (pretty_printer *pp, def_mux mux)
    1740                 :             : {
    1741                 :           0 :   if (auto *node = mux.dyn_cast<def_node *> ())
    1742                 :           0 :     pp_def_node (pp, node);
    1743                 :             :   else
    1744                 :           0 :     pp_access (pp, mux.as_a<def_info *> ());
    1745                 :           0 : }
    1746                 :             : 
    1747                 :             : // Print DL to PP.
    1748                 :             : void
    1749                 :           0 : rtl_ssa::pp_def_lookup (pretty_printer *pp, def_lookup dl)
    1750                 :             : {
    1751                 :           0 :   pp_string (pp, "comparison result of ");
    1752                 :           0 :   pp_decimal_int (pp, dl.comparison);
    1753                 :           0 :   pp_string (pp, " for ");
    1754                 :           0 :   pp_newline_and_indent (pp, 0);
    1755                 :           0 :   pp_def_mux (pp, dl.mux);
    1756                 :           0 : }
    1757                 :             : 
    1758                 :             : // Print TREE to PP.
    1759                 :             : void
    1760                 :           0 : rtl_ssa::pp_def_splay_tree (pretty_printer *pp, def_splay_tree tree)
    1761                 :             : {
    1762                 :           0 :   tree.print (pp, pp_def_node);
    1763                 :           0 : }
    1764                 :             : 
    1765                 :             : // Dump RESOURCE to FILE.
    1766                 :             : void
    1767                 :           0 : dump (FILE *file, resource_info resource)
    1768                 :             : {
    1769                 :           0 :   dump_using (file, pp_resource, resource);
    1770                 :           0 : }
    1771                 :             : 
    1772                 :             : // Dump ACCESS to FILE.  FLAGS is a bitmask of PP_ACCESS_* flags.
    1773                 :             : void
    1774                 :           0 : dump (FILE *file, const access_info *access, unsigned int flags)
    1775                 :             : {
    1776                 :           0 :   dump_using (file, pp_access, access, flags);
    1777                 :           0 : }
    1778                 :             : 
    1779                 :             : // Dump ACCESSES to FILE.  FLAGS is a bitmask of PP_ACCESS_* flags.
    1780                 :             : void
    1781                 :           0 : dump (FILE *file, access_array accesses, unsigned int flags)
    1782                 :             : {
    1783                 :           0 :   dump_using (file, pp_accesses, accesses, flags);
    1784                 :           0 : }
    1785                 :             : 
    1786                 :             : // Print NODE to FILE.
    1787                 :             : void
    1788                 :           0 : dump (FILE *file, const def_node *node)
    1789                 :             : {
    1790                 :           0 :   dump_using (file, pp_def_node, node);
    1791                 :           0 : }
    1792                 :             : 
    1793                 :             : // Print MUX to FILE.
    1794                 :             : void
    1795                 :           0 : dump (FILE *file, def_mux mux)
    1796                 :             : {
    1797                 :           0 :   dump_using (file, pp_def_mux, mux);
    1798                 :           0 : }
    1799                 :             : 
    1800                 :             : // Print RESULT to FILE.
    1801                 :             : void
    1802                 :           0 : dump (FILE *file, def_lookup result)
    1803                 :             : {
    1804                 :           0 :   dump_using (file, pp_def_lookup, result);
    1805                 :           0 : }
    1806                 :             : 
    1807                 :             : // Print TREE to FILE.
    1808                 :             : void
    1809                 :           0 : dump (FILE *file, def_splay_tree tree)
    1810                 :             : {
    1811                 :           0 :   dump_using (file, pp_def_splay_tree, tree);
    1812                 :           0 : }
    1813                 :             : 
    1814                 :             : // Debug interfaces to the dump routines above.
    1815                 :           0 : void debug (const resource_info &x) { dump (stderr, x); }
    1816                 :           0 : void debug (const access_info *x) { dump (stderr, x); }
    1817                 :           0 : void debug (const access_array &x) { dump (stderr, x); }
    1818                 :           0 : void debug (const def_node *x) { dump (stderr, x); }
    1819                 :           0 : void debug (const def_mux &x) { dump (stderr, x); }
    1820                 :           0 : void debug (const def_lookup &x) { dump (stderr, x); }
    1821                 :           0 : void debug (const def_splay_tree &x) { dump (stderr, x); }
        

Generated by: LCOV version 2.1-beta

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.