LCOV - code coverage report
Current view: top level - gcc/rtl-ssa - functions.cc (source / functions) Coverage Total Hit
Test: gcc.info Lines: 87.8 % 123 108
Test Date: 2025-02-01 13:18:56 Functions: 60.0 % 10 6
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: - 0 0

             Branch data     Line data    Source code
       1                 :             : // Implementation of function-related RTL SSA functions             -*- 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                 :     3861376 : function_info::function_info (function *fn)
      36                 :     7722752 :   : m_fn (fn), m_clobbered_by_calls ()
      37                 :             : {
      38                 :             :   // Force the alignment to be obstack_alignment.  Everything else is normal.
      39                 :     3861376 :   obstack_specify_allocation (&m_obstack, OBSTACK_CHUNK_SIZE,
      40                 :             :                               obstack_alignment, obstack_chunk_alloc,
      41                 :             :                               obstack_chunk_free);
      42                 :     3861376 :   obstack_specify_allocation (&m_temp_obstack, OBSTACK_CHUNK_SIZE,
      43                 :             :                               obstack_alignment, obstack_chunk_alloc,
      44                 :             :                               obstack_chunk_free);
      45                 :             : 
      46                 :             :   // Record the start of the obstacks.
      47                 :     3861376 :   m_obstack_start = XOBNEWVAR (&m_obstack, char, 0);
      48                 :     3861376 :   m_temp_obstack_start = XOBNEWVAR (&m_temp_obstack, char, 0);
      49                 :             : 
      50                 :     3861376 :   init_function_data ();
      51                 :     3861376 :   process_all_blocks ();
      52                 :     3861376 :   simplify_phis ();
      53                 :     3861376 : }
      54                 :             : 
      55                 :     3861376 : function_info::~function_info ()
      56                 :             : {
      57                 :             :   // Anything using the temporary obstack should free it afterwards,
      58                 :             :   // preferably via temp_watermark ().
      59                 :     3861376 :   gcc_assert (XOBNEWVAR (&m_temp_obstack, char, 0) == m_temp_obstack_start);
      60                 :             : 
      61                 :     3861376 :   obstack_free (&m_temp_obstack, nullptr);
      62                 :     3861376 :   obstack_free (&m_obstack, nullptr);
      63                 :     3861376 : }
      64                 :             : 
      65                 :             : // See the comment above the declaration.
      66                 :             : void
      67                 :           0 : function_info::print (pretty_printer *pp) const
      68                 :             : {
      69                 :           0 :   pp_string (pp, "Function: ");
      70                 :           0 :   pp_string (pp, function_name (m_fn));
      71                 :           0 :   for (ebb_info *ebb : ebbs ())
      72                 :             :     {
      73                 :           0 :       pp_newline (pp);
      74                 :           0 :       pp_newline_and_indent (pp, 0);
      75                 :           0 :       pp_ebb (pp, ebb);
      76                 :             :     }
      77                 :           0 : }
      78                 :             : 
      79                 :             : // Initialize all member variables in preparation for (re)building
      80                 :             : // SSA form from scratch.
      81                 :             : void
      82                 :     3861376 : function_info::init_function_data ()
      83                 :             : {
      84                 :     3861376 :   m_next_artificial_uid = -1;
      85                 :     3861376 :   m_next_phi_uid = 0;
      86                 :     3861376 :   m_num_regs = max_reg_num ();
      87                 :     3861376 :   m_defs.safe_grow_cleared (m_num_regs + 1);
      88                 :     3861376 :   m_bbs.safe_grow_cleared (last_basic_block_for_fn (m_fn));
      89                 :     3861376 :   m_first_bb = nullptr;
      90                 :     3861376 :   m_last_bb = nullptr;
      91                 :     3861376 :   m_first_insn = nullptr;
      92                 :     3861376 :   m_last_insn = nullptr;
      93                 :     3861376 :   m_last_nondebug_insn = nullptr;
      94                 :     3861376 :   m_free_phis = nullptr;
      95                 :     3861376 : }
      96                 :             : 
      97                 :             : // The initial phase of the phi simplification process.  The cumulative
      98                 :             : // effect of the initial phase is to set up ASSUMED_VALUES such that,
      99                 :             : // for a phi P with uid ID:
     100                 :             : //
     101                 :             : // - if we think all inputs to P have the same value, ASSUMED_VALUES[ID]
     102                 :             : //   is that value
     103                 :             : //
     104                 :             : // - otherwise, ASSUMED_VALUES[ID] is P.
     105                 :             : //
     106                 :             : // This has already been done for phis with a lower uid than PHI,
     107                 :             : // initially making optimistic assumptions about backedge inputs.
     108                 :             : // Now do the same for PHI.  If this might invalidate any assumptions
     109                 :             : // made for earlier phis, add the uids of those phis to WORKLIST.
     110                 :             : void
     111                 :    53630841 : function_info::simplify_phi_setup (phi_info *phi, set_info **assumed_values,
     112                 :             :                                    bitmap worklist)
     113                 :             : {
     114                 :             :   // If all non-backedge inputs have the same value, set NEW_VALUE
     115                 :             :   // to that value.  Otherwise set NEW_VALUE to PHI, to indicate
     116                 :             :   // that PHI cannot be simplified.
     117                 :    53630841 :   unsigned int phi_uid = phi->uid ();
     118                 :    53630841 :   bool is_first_input = true;
     119                 :    53630841 :   set_info *new_value = nullptr;
     120                 :    53630841 :   machine_mode phi_mode = phi->mode ();
     121                 :   196454701 :   for (use_info *input : phi->inputs ())
     122                 :             :     {
     123                 :    89193019 :       set_info *def = input->def ();
     124                 :             : 
     125                 :    89193019 :       if (auto *input_phi = safe_dyn_cast<phi_info *> (def))
     126                 :             :         {
     127                 :             :           // Ignore backedges for now.
     128                 :    20596753 :           unsigned int input_phi_uid = input_phi->uid ();
     129                 :    20596753 :           if (phi_uid <= input_phi_uid)
     130                 :     1926788 :             continue;
     131                 :             : 
     132                 :    18669965 :           def = assumed_values[input_phi_uid];
     133                 :             :         }
     134                 :             : 
     135                 :             :       // Compare this definition with previous ones.
     136                 :    87266231 :       if (is_first_input)
     137                 :             :         {
     138                 :             :           new_value = def;
     139                 :             :           is_first_input = false;
     140                 :             :         }
     141                 :    33635390 :       else if (new_value != def)
     142                 :    31962116 :         new_value = phi;
     143                 :             : 
     144                 :             :       // If the input has a known mode (i.e. not BLKmode), make sure
     145                 :             :       // that the phi's mode is at least as large.
     146                 :    87266231 :       if (def)
     147                 :    87228498 :         phi_mode = combine_modes (phi_mode, def->mode ());
     148                 :             :     }
     149                 :    53630841 :   if (phi->mode () != phi_mode)
     150                 :    17532102 :     phi->set_mode (phi_mode);
     151                 :             : 
     152                 :             :   // Since we use a reverse postorder traversal, no phi can consist
     153                 :             :   // entirely of backedges.
     154                 :    53630841 :   gcc_checking_assert (!is_first_input);
     155                 :    53630841 :   assumed_values[phi_uid] = new_value;
     156                 :             : 
     157                 :             :   // See whether any assumptions for earlier phis are now invalid.
     158                 :    53630841 :   simplify_phi_propagate (phi, assumed_values, nullptr, worklist);
     159                 :    53630841 : }
     160                 :             : 
     161                 :             : // The propagation phase of the phi simplification process, with
     162                 :             : // ASSUMED_VALUES as described above simplify_phi_setup.  Iteratively
     163                 :             : // update the phis that use PHI based on PHI's entry in ASSUMED_VALUES.
     164                 :             : // If CURR_WORKLIST is null, consider only phi uses with a lower uid
     165                 :             : // than PHI, otherwise consider all phi uses.
     166                 :             : //
     167                 :             : // If a phi with a higher uid than PHI needs updating, add its uid to
     168                 :             : // CURR_WORKLIST; if a phi with a lower uid than PHI needs updating,
     169                 :             : // add its uid to NEXT_WORKLIST.
     170                 :             : void
     171                 :    55465662 : function_info::simplify_phi_propagate (phi_info *phi,
     172                 :             :                                        set_info **assumed_values,
     173                 :             :                                        bitmap curr_worklist,
     174                 :             :                                        bitmap next_worklist)
     175                 :             : {
     176                 :             :   // Go through each phi user of PHI to see whether it needs updating.
     177                 :    55465662 :   unsigned int phi_uid = phi->uid ();
     178                 :    55465662 :   machine_mode phi_mode = phi->mode ();
     179                 :    55465662 :   set_info *phi_value = assumed_values[phi_uid];
     180                 :   134861542 :   for (use_info *use : phi->phi_uses ())
     181                 :             :     {
     182                 :    23930218 :       phi_info *user_phi = use->phi ();
     183                 :             : 
     184                 :             :       // Propagate the phi's new mode to all phi users.  Insn uses should
     185                 :             :       // not be updated, since their modes reflect a property of the insns
     186                 :             :       // rather than the phi.
     187                 :    23930218 :       if (use->mode () != phi_mode)
     188                 :    12976506 :         use->set_mode (phi_mode);
     189                 :             : 
     190                 :    23930218 :       if (user_phi == phi)
     191                 :      901211 :         continue;
     192                 :             : 
     193                 :             :       // If this is a phi we should be looking at, see whether it needs
     194                 :             :       // an update.
     195                 :    23029007 :       unsigned int user_phi_uid = user_phi->uid ();
     196                 :    23029007 :       if (user_phi_uid < phi_uid || curr_worklist)
     197                 :             :         {
     198                 :     4359042 :           bool needs_update = false;
     199                 :             : 
     200                 :             :           // Make sure that USER_PHI's mode is at least as big as PHI_MODE.
     201                 :     4359042 :           machine_mode user_phi_mode = user_phi->mode ();
     202                 :     4359042 :           machine_mode new_mode = combine_modes (user_phi_mode, phi_mode);
     203                 :     4359042 :           if (user_phi_mode != new_mode)
     204                 :             :             {
     205                 :         986 :               user_phi->set_mode (new_mode);
     206                 :         986 :               needs_update = true;
     207                 :             :             }
     208                 :             : 
     209                 :             :           // If USER_PHI optimistically assumed an incorrect value,
     210                 :             :           // adjust it now.
     211                 :     4359042 :           if (assumed_values[user_phi_uid] != user_phi
     212                 :     2005044 :               && assumed_values[user_phi_uid] != phi_value)
     213                 :             :             {
     214                 :     1834763 :               assumed_values[user_phi_uid] = user_phi;
     215                 :     1834763 :               needs_update = true;
     216                 :             :             }
     217                 :             : 
     218                 :     4359042 :           if (needs_update)
     219                 :             :             {
     220                 :     1834821 :               if (user_phi_uid < phi_uid)
     221                 :      879752 :                 bitmap_set_bit (next_worklist, user_phi_uid);
     222                 :             :               else
     223                 :      955069 :                 bitmap_set_bit (curr_worklist, user_phi_uid);
     224                 :             :             }
     225                 :             :         }
     226                 :             :     }
     227                 :    55465662 : }
     228                 :             : 
     229                 :             : // Update the modes of all phis so that they are at least as big as
     230                 :             : // all inputs.  Remove any non-degenerate phis whose inputs are all equal.
     231                 :             : void
     232                 :     3861376 : function_info::simplify_phis ()
     233                 :             : {
     234                 :     3861376 :   auto temps = temp_watermark ();
     235                 :             : 
     236                 :             :   // See the comment above simplify_phi_setup for details about this array.
     237                 :     3861376 :   auto *assumed_values = XOBNEWVEC (&m_temp_obstack, set_info *,
     238                 :             :                                     m_next_phi_uid);
     239                 :             : 
     240                 :             :   // An array of all phis, indexed by uid.
     241                 :     3861376 :   auto *phis = XOBNEWVEC (&m_temp_obstack, phi_info *, m_next_phi_uid);
     242                 :             : 
     243                 :             :   // Which phi uids are actually in use.
     244                 :     3861376 :   auto_sbitmap valid_phi_uids (m_next_phi_uid);
     245                 :     3861376 :   bitmap_clear (valid_phi_uids);
     246                 :             : 
     247                 :             :   // Bitmaps used for the main double-queue propagation phase.
     248                 :     3861376 :   auto_bitmap worklist1;
     249                 :     3861376 :   auto_bitmap worklist2;
     250                 :     3861376 :   bitmap curr_worklist = worklist1;
     251                 :     3861376 :   bitmap next_worklist = worklist2;
     252                 :             : 
     253                 :             :   // Perform the set-up phase; see simplify_phi_setup for details.
     254                 :    61458466 :   for (ebb_info *ebb : ebbs ())
     255                 :    82429386 :     for (phi_info *phi : ebb->phis ())
     256                 :             :       {
     257                 :    53630841 :         bitmap_set_bit (valid_phi_uids, phi->uid ());
     258                 :    53630841 :         phis[phi->uid ()] = phi;
     259                 :    53630841 :         simplify_phi_setup (phi, assumed_values, curr_worklist);
     260                 :             :       }
     261                 :             : 
     262                 :             :   // Iteratively process any phis that need updating; see
     263                 :             :   // simplify_phi_propagate for details.  Using a double queue
     264                 :             :   // should reduce the number of times that any given phi node
     265                 :             :   // needs to be revisited.
     266                 :     4080987 :   while (!bitmap_empty_p (curr_worklist))
     267                 :             :     {
     268                 :     1834821 :       do
     269                 :             :         {
     270                 :     1834821 :           unsigned int uid = bitmap_first_set_bit (curr_worklist);
     271                 :     1834821 :           bitmap_clear_bit (curr_worklist, uid);
     272                 :     1834821 :           simplify_phi_propagate (phis[uid], assumed_values,
     273                 :             :                                   curr_worklist, next_worklist);
     274                 :             :         }
     275                 :     1834821 :       while (!bitmap_empty_p (curr_worklist));
     276                 :             :       std::swap (next_worklist, curr_worklist);
     277                 :             :     }
     278                 :             : 
     279                 :             :   // Make sure that assumed_values is a transitive closure.  This ensures
     280                 :             :   // that each use_info is only updated once.
     281                 :     3861376 :   if (flag_checking)
     282                 :    57496748 :     for (unsigned int i = 0; i < m_next_phi_uid; ++i)
     283                 :    53635436 :       if (bitmap_bit_p (valid_phi_uids, i))
     284                 :   107264427 :         if (auto *new_phi = safe_dyn_cast<phi_info *> (assumed_values[i]))
     285                 :    26338446 :           gcc_assert (assumed_values[new_phi->uid ()] == new_phi);
     286                 :             : 
     287                 :             :   // Update any phis that turned out to be equivalent to a single input.
     288                 :    57497059 :   for (unsigned int i = 0; i < m_next_phi_uid; ++i)
     289                 :    53635683 :     if (bitmap_bit_p (valid_phi_uids, i) && phis[i] != assumed_values[i])
     290                 :    33956367 :       replace_phi (phis[i], assumed_values[i]);
     291                 :     3861376 : }
     292                 :             : 
     293                 :             : // Print a description of FUNCTION to PP.
     294                 :             : void
     295                 :           0 : rtl_ssa::pp_function (pretty_printer *pp, const function_info *function)
     296                 :             : {
     297                 :           0 :   function->print (pp);
     298                 :           0 : }
     299                 :             : 
     300                 :             : // Print a description of FUNCTION to FILE.
     301                 :             : void
     302                 :           0 : dump (FILE *file, const function_info *function)
     303                 :             : {
     304                 :           0 :   dump_using (file, pp_function, function);
     305                 :           0 : }
     306                 :             : 
     307                 :             : // Debug interface to the dump routine above.
     308                 :           0 : void debug (const function_info *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.