LCOV - code coverage report
Current view: top level - gcc/rtl-ssa - functions.cc (source / functions) Hit Total Coverage
Test: gcc.info Lines: 106 123 86.2 %
Date: 2021-11-27 14:51:55 Functions: 6 10 60.0 %
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-2021 Free Software Foundation, Inc.
       3                 :            : //
       4                 :            : // This file is part of GCC.
       5                 :            : //
       6                 :            : // GCC is free software; you can redistribute it and/or modify it under
       7                 :            : // the terms of the GNU General Public License as published by the Free
       8                 :            : // Software Foundation; either version 3, or (at your option) any later
       9                 :            : // version.
      10                 :            : //
      11                 :            : // GCC is distributed in the hope that it will be useful, but WITHOUT ANY
      12                 :            : // WARRANTY; without even the implied warranty of MERCHANTABILITY or
      13                 :            : // FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
      14                 :            : // for more details.
      15                 :            : //
      16                 :            : // You should have received a copy of the GNU General Public License
      17                 :            : // along with GCC; see the file COPYING3.  If not see
      18                 :            : // <http://www.gnu.org/licenses/>.
      19                 :            : 
      20                 :            : #define INCLUDE_ALGORITHM
      21                 :            : #define INCLUDE_FUNCTIONAL
      22                 :            : #include "config.h"
      23                 :            : #include "system.h"
      24                 :            : #include "coretypes.h"
      25                 :            : #include "backend.h"
      26                 :            : #include "rtl.h"
      27                 :            : #include "df.h"
      28                 :            : #include "rtl-ssa.h"
      29                 :            : #include "rtl-ssa/internals.h"
      30                 :            : #include "rtl-ssa/internals.inl"
      31                 :            : 
      32                 :            : using namespace rtl_ssa;
      33                 :            : 
      34                 :    1697958 : function_info::function_info (function *fn)
      35                 :    1697958 :   : m_fn (fn)
      36                 :            : {
      37                 :            :   // Force the alignment to be obstack_alignment.  Everything else is normal.
      38                 :    1697958 :   obstack_specify_allocation (&m_obstack, OBSTACK_CHUNK_SIZE,
      39                 :            :                               obstack_alignment, obstack_chunk_alloc,
      40                 :            :                               obstack_chunk_free);
      41                 :    1697958 :   obstack_specify_allocation (&m_temp_obstack, OBSTACK_CHUNK_SIZE,
      42                 :            :                               obstack_alignment, obstack_chunk_alloc,
      43                 :            :                               obstack_chunk_free);
      44                 :            : 
      45                 :            :   // Record the start of the obstacks.
      46                 :    1697958 :   m_obstack_start = XOBNEWVAR (&m_obstack, char, 0);
      47                 :    1697958 :   m_temp_obstack_start = XOBNEWVAR (&m_temp_obstack, char, 0);
      48                 :            : 
      49                 :    1697958 :   init_function_data ();
      50                 :    1697958 :   process_all_blocks ();
      51                 :    1697958 :   simplify_phis ();
      52                 :    1697958 : }
      53                 :            : 
      54                 :    1697958 : function_info::~function_info ()
      55                 :            : {
      56                 :            :   // Anything using the temporary obstack should free it afterwards,
      57                 :            :   // preferably via temp_watermark ().
      58                 :    1697958 :   gcc_assert (XOBNEWVAR (&m_temp_obstack, char, 0) == m_temp_obstack_start);
      59                 :            : 
      60                 :    1697958 :   obstack_free (&m_temp_obstack, nullptr);
      61                 :    1697958 :   obstack_free (&m_obstack, nullptr);
      62                 :    1697958 : }
      63                 :            : 
      64                 :            : // See the comment above the declaration.
      65                 :            : void
      66                 :          0 : function_info::print (pretty_printer *pp) const
      67                 :            : {
      68                 :          0 :   pp_string (pp, "Function: ");
      69                 :          0 :   pp_string (pp, function_name (m_fn));
      70                 :          0 :   for (ebb_info *ebb : ebbs ())
      71                 :            :     {
      72                 :          0 :       pp_newline (pp);
      73                 :          0 :       pp_newline_and_indent (pp, 0);
      74                 :          0 :       pp_ebb (pp, ebb);
      75                 :            :     }
      76                 :          0 : }
      77                 :            : 
      78                 :            : // Initialize all member variables in preparation for (re)building
      79                 :            : // SSA form from scratch.
      80                 :            : void
      81                 :    1697958 : function_info::init_function_data ()
      82                 :            : {
      83                 :    1697958 :   m_next_artificial_uid = -1;
      84                 :    1697958 :   m_next_phi_uid = 0;
      85                 :    1697958 :   m_num_regs = max_reg_num ();
      86                 :    1697958 :   m_defs.safe_grow_cleared (m_num_regs + 1);
      87                 :    1697958 :   m_bbs.safe_grow_cleared (last_basic_block_for_fn (m_fn));
      88                 :    1697958 :   m_first_bb = nullptr;
      89                 :    1697958 :   m_last_bb = nullptr;
      90                 :    1697958 :   m_first_insn = nullptr;
      91                 :    1697958 :   m_last_insn = nullptr;
      92                 :    1697958 :   m_last_nondebug_insn = nullptr;
      93                 :    1697958 :   m_free_phis = nullptr;
      94                 :    1697958 : }
      95                 :            : 
      96                 :            : // The initial phase of the phi simplification process.  The cumulative
      97                 :            : // effect of the initial phase is to set up ASSUMED_VALUES such that,
      98                 :            : // for a phi P with uid ID:
      99                 :            : //
     100                 :            : // - if we think all inputs to P have the same value, ASSUMED_VALUES[ID]
     101                 :            : //   is that value
     102                 :            : //
     103                 :            : // - otherwise, ASSUMED_VALUES[ID] is P.
     104                 :            : //
     105                 :            : // This has already been done for phis with a lower uid than PHI,
     106                 :            : // initially making optimistic assumptions about backedge inputs.
     107                 :            : // Now do the same for PHI.  If this might invalidate any assumptions
     108                 :            : // made for earlier phis, add the uids of those phis to WORKLIST.
     109                 :            : void
     110                 :   20503609 : function_info::simplify_phi_setup (phi_info *phi, set_info **assumed_values,
     111                 :            :                                    bitmap worklist)
     112                 :            : {
     113                 :            :   // If all non-backedge inputs have the same value, set NEW_VALUE
     114                 :            :   // to that value.  Otherwise set NEW_VALUE to PHI, to indicate
     115                 :            :   // that PHI cannot be simplified.
     116                 :   20503609 :   unsigned int phi_uid = phi->uid ();
     117                 :   20503609 :   bool is_first_input = true;
     118                 :   20503609 :   set_info *new_value = nullptr;
     119                 :   20503609 :   machine_mode phi_mode = phi->mode ();
     120                 :   74412936 :   for (use_info *input : phi->inputs ())
     121                 :            :     {
     122                 :   33405718 :       set_info *def = input->def ();
     123                 :            : 
     124                 :   33405718 :       if (auto *input_phi = safe_dyn_cast<phi_info *> (def))
     125                 :            :         {
     126                 :            :           // Ignore backedges for now.
     127                 :    6994448 :           unsigned int input_phi_uid = input_phi->uid ();
     128                 :    6994448 :           if (phi_uid <= input_phi_uid)
     129                 :     756429 :             continue;
     130                 :            : 
     131                 :    6238019 :           def = assumed_values[input_phi_uid];
     132                 :            :         }
     133                 :            : 
     134                 :            :       // Compare this definition with previous ones.
     135                 :   32649289 :       if (is_first_input)
     136                 :            :         {
     137                 :            :           new_value = def;
     138                 :            :           is_first_input = false;
     139                 :            :         }
     140                 :   12145680 :       else if (new_value != def)
     141                 :   11647502 :         new_value = phi;
     142                 :            : 
     143                 :            :       // If the input has a known mode (i.e. not BLKmode), make sure
     144                 :            :       // that the phi's mode is at least as large.
     145                 :   32649289 :       if (def)
     146                 :   45699990 :         phi_mode = combine_modes (phi_mode, def->mode ());
     147                 :            :     }
     148                 :   20503609 :   if (phi->mode () != phi_mode)
     149                 :    6405316 :     phi->set_mode (phi_mode);
     150                 :            : 
     151                 :            :   // Since we use a reverse postorder traversal, no phi can consist
     152                 :            :   // entirely of backedges.
     153                 :   20503609 :   gcc_checking_assert (!is_first_input);
     154                 :   20503609 :   assumed_values[phi_uid] = new_value;
     155                 :            : 
     156                 :            :   // See whether any assumptions for earlier phis are now invalid.
     157                 :   20503609 :   simplify_phi_propagate (phi, assumed_values, nullptr, worklist);
     158                 :   20503609 : }
     159                 :            : 
     160                 :            : // The propagation phase of the phi simplification process, with
     161                 :            : // ASSUMED_VALUES as described above simplify_phi_setup.  Iteratively
     162                 :            : // update the phis that use PHI based on PHI's entry in ASSUMED_VALUES.
     163                 :            : // If CURR_WORKLIST is null, consider only phi uses with a lower uid
     164                 :            : // than PHI, otherwise consider all phi uses.
     165                 :            : //
     166                 :            : // If a phi with a higher uid than PHI needs updating, add its uid to
     167                 :            : // CURR_WORKLIST; if a phi with a lower uid than PHI needs updating,
     168                 :            : // add its uid to NEXT_WORKLIST.
     169                 :            : void
     170                 :   21211004 : function_info::simplify_phi_propagate (phi_info *phi,
     171                 :            :                                        set_info **assumed_values,
     172                 :            :                                        bitmap curr_worklist,
     173                 :            :                                        bitmap next_worklist)
     174                 :            : {
     175                 :            :   // Go through each phi user of PHI to see whether it needs updating.
     176                 :   21211004 :   unsigned int phi_uid = phi->uid ();
     177                 :   21211004 :   machine_mode phi_mode = phi->mode ();
     178                 :   21211004 :   set_info *phi_value = assumed_values[phi_uid];
     179                 :   48681199 :   for (use_info *use : phi->phi_uses ())
     180                 :            :     {
     181                 :    8019458 :       phi_info *user_phi = use->phi ();
     182                 :            : 
     183                 :            :       // Propagate the phi's new mode to all phi users.  Insn uses should
     184                 :            :       // not be updated, since their modes reflect a property of the insns
     185                 :            :       // rather than the phi.
     186                 :    8019458 :       if (use->mode () != phi_mode)
     187                 :    4094318 :         use->set_mode (phi_mode);
     188                 :            : 
     189                 :    8019458 :       if (user_phi == phi)
     190                 :     339263 :         continue;
     191                 :            : 
     192                 :            :       // If this is a phi we should be looking at, see whether it needs
     193                 :            :       // an update.
     194                 :    7680195 :       unsigned int user_phi_uid = user_phi->uid ();
     195                 :    7680195 :       if (user_phi_uid < phi_uid || curr_worklist)
     196                 :            :         {
     197                 :    1442176 :           bool needs_update = false;
     198                 :            : 
     199                 :            :           // Make sure that USER_PHI's mode is at least as big as PHI_MODE.
     200                 :    1442176 :           machine_mode user_phi_mode = user_phi->mode ();
     201                 :    1442176 :           machine_mode new_mode = combine_modes (user_phi_mode, phi_mode);
     202                 :    1442176 :           if (user_phi_mode != new_mode)
     203                 :            :             {
     204                 :          0 :               user_phi->set_mode (new_mode);
     205                 :          0 :               needs_update = true;
     206                 :            :             }
     207                 :            : 
     208                 :            :           // If USER_PHI optimistically assumed an incorrect value,
     209                 :            :           // adjust it now.
     210                 :    1442176 :           if (assumed_values[user_phi_uid] != user_phi
     211                 :     774774 :               && assumed_values[user_phi_uid] != phi_value)
     212                 :            :             {
     213                 :     707395 :               assumed_values[user_phi_uid] = user_phi;
     214                 :     707395 :               needs_update = true;
     215                 :            :             }
     216                 :            : 
     217                 :    1442176 :           if (needs_update)
     218                 :            :             {
     219                 :     707395 :               if (user_phi_uid < phi_uid)
     220                 :     378866 :                 bitmap_set_bit (next_worklist, user_phi_uid);
     221                 :            :               else
     222                 :     328529 :                 bitmap_set_bit (curr_worklist, user_phi_uid);
     223                 :            :             }
     224                 :            :         }
     225                 :            :     }
     226                 :   21211004 : }
     227                 :            : 
     228                 :            : // Update the modes of all phis so that they are at least as big as
     229                 :            : // all inputs.  Remove any non-degenerate phis whose inputs are all equal.
     230                 :            : void
     231                 :    1697958 : function_info::simplify_phis ()
     232                 :            : {
     233                 :    1697958 :   auto temps = temp_watermark ();
     234                 :            : 
     235                 :            :   // See the comment above simplify_phi_setup for details about this array.
     236                 :    1697958 :   auto *assumed_values = XOBNEWVEC (&m_temp_obstack, set_info *,
     237                 :            :                                     m_next_phi_uid);
     238                 :            : 
     239                 :            :   // An array of all phis, indexed by uid.
     240                 :    1697958 :   auto *phis = XOBNEWVEC (&m_temp_obstack, phi_info *, m_next_phi_uid);
     241                 :            : 
     242                 :            :   // Which phi uids are actually in use.
     243                 :    1697958 :   auto_sbitmap valid_phi_uids (m_next_phi_uid);
     244                 :    1697958 :   bitmap_clear (valid_phi_uids);
     245                 :            : 
     246                 :            :   // Bitmaps used for the main double-queue propagation phase.
     247                 :    1697958 :   auto_bitmap worklist1;
     248                 :    1697958 :   auto_bitmap worklist2;
     249                 :    1697958 :   bitmap curr_worklist = worklist1;
     250                 :    1697958 :   bitmap next_worklist = worklist2;
     251                 :            : 
     252                 :            :   // Perform the set-up phase; see simplify_phi_setup for details.
     253                 :   25718742 :   for (ebb_info *ebb : ebbs ())
     254                 :   32514001 :     for (phi_info *phi : ebb->phis ())
     255                 :            :       {
     256                 :   20503609 :         bitmap_set_bit (valid_phi_uids, phi->uid ());
     257                 :   20503609 :         phis[phi->uid ()] = phi;
     258                 :   20503609 :         simplify_phi_setup (phi, assumed_values, curr_worklist);
     259                 :            :       }
     260                 :            : 
     261                 :            :   // Iteratively process any phis that need updating; see
     262                 :            :   // simplify_phi_propagate for details.  Using a double queue
     263                 :            :   // should reduce the number of times that any given phi node
     264                 :            :   // needs to be revisited.
     265                 :    1799938 :   while (!bitmap_empty_p (curr_worklist))
     266                 :            :     {
     267                 :     707395 :       do
     268                 :            :         {
     269                 :     707395 :           unsigned int uid = bitmap_first_set_bit (curr_worklist);
     270                 :     707395 :           bitmap_clear_bit (curr_worklist, uid);
     271                 :     707395 :           simplify_phi_propagate (phis[uid], assumed_values,
     272                 :            :                                   curr_worklist, next_worklist);
     273                 :            :         }
     274                 :     707395 :       while (!bitmap_empty_p (curr_worklist));
     275                 :            :       std::swap (next_worklist, curr_worklist);
     276                 :            :     }
     277                 :            : 
     278                 :            :   // Make sure that assumed_values is a transitive closure.  This ensures
     279                 :            :   // that each use_info is only updated once.
     280                 :    1697958 :   if (flag_checking)
     281                 :   22206216 :     for (unsigned int i = 0; i < m_next_phi_uid; ++i)
     282                 :   20508278 :       if (bitmap_bit_p (valid_phi_uids, i))
     283                 :   41011389 :         if (auto *new_phi = safe_dyn_cast<phi_info *> (assumed_values[i]))
     284                 :    9914589 :           gcc_assert (assumed_values[new_phi->uid ()] == new_phi);
     285                 :            : 
     286                 :            :   // Update any phis that turned out to be equivalent to a single input.
     287                 :   22206346 :   for (unsigned int i = 0; i < m_next_phi_uid; ++i)
     288                 :   20508388 :     if (bitmap_bit_p (valid_phi_uids, i) && phis[i] != assumed_values[i])
     289                 :   13061704 :       replace_phi (phis[i], assumed_values[i]);
     290                 :    1697958 : }
     291                 :            : 
     292                 :            : // Print a description of FUNCTION to PP.
     293                 :            : void
     294                 :          0 : rtl_ssa::pp_function (pretty_printer *pp, const function_info *function)
     295                 :            : {
     296                 :          0 :   function->print (pp);
     297                 :          0 : }
     298                 :            : 
     299                 :            : // Print a description of FUNCTION to FILE.
     300                 :            : void
     301                 :          0 : dump (FILE *file, const function_info *function)
     302                 :            : {
     303                 :          0 :   dump_using (file, pp_function, function);
     304                 :          0 : }
     305                 :            : 
     306                 :            : // Debug interface to the dump routine above.
     307                 :          0 : void debug (const function_info *x) { dump (stderr, x); }

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

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