LCOV - code coverage report
Current view: top level - gcc/rtl-ssa - movement.h (source / functions) Hit Total Coverage
Test: gcc.info Lines: 65 88 73.9 %
Date: 2021-07-31 13:02:41 Functions: 5 7 71.4 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 0 0 -

           Branch data     Line data    Source code
       1                 :            : // RTL SSA utilities relating to instruction movement               -*- 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                 :            : namespace rtl_ssa {
      21                 :            : 
      22                 :            : // Restrict movement range RANGE so that the instruction is placed later
      23                 :            : // than INSN.  (The movement range is the range of instructions after which
      24                 :            : // an instruction can be placed.)
      25                 :            : inline insn_range_info
      26                 :   97310309 : move_later_than (insn_range_info range, insn_info *insn)
      27                 :            : {
      28                 :   97310309 :   return { later_insn (range.first, insn), range.last };
      29                 :            : }
      30                 :            : 
      31                 :            : // Restrict movement range RANGE so that the instruction is placed no earlier
      32                 :            : // than INSN.  (The movement range is the range of instructions after which
      33                 :            : // an instruction can be placed.)
      34                 :            : inline insn_range_info
      35                 :            : move_no_earlier_than (insn_range_info range, insn_info *insn)
      36                 :            : {
      37                 :            :   insn_info *first = later_insn (range.first, insn->prev_nondebug_insn ());
      38                 :            :   return { first, range.last };
      39                 :            : }
      40                 :            : 
      41                 :            : // Restrict movement range RANGE so that the instruction is placed no later
      42                 :            : // than INSN.  (The movement range is the range of instructions after which
      43                 :            : // an instruction can be placed.)
      44                 :            : inline insn_range_info
      45                 :            : move_no_later_than (insn_range_info range, insn_info *insn)
      46                 :            : {
      47                 :            :   return { range.first, earlier_insn (range.last, insn) };
      48                 :            : }
      49                 :            : 
      50                 :            : // Restrict movement range RANGE so that the instruction is placed earlier
      51                 :            : // than INSN.  (The movement range is the range of instructions after which
      52                 :            : // an instruction can be placed.)
      53                 :            : inline insn_range_info
      54                 :   54012970 : move_earlier_than (insn_range_info range, insn_info *insn)
      55                 :            : {
      56                 :   54012970 :   insn_info *last = earlier_insn (range.last, insn->prev_nondebug_insn ());
      57                 :   54012970 :   return { range.first, last };
      58                 :            : }
      59                 :            : 
      60                 :            : // Return true if it is possible to insert a new instruction after INSN.
      61                 :            : inline bool
      62                 :          0 : can_insert_after (insn_info *insn)
      63                 :            : {
      64                 :          0 :   return insn->is_bb_head () || (insn->is_real () && !insn->is_jump ());
      65                 :            : }
      66                 :            : 
      67                 :            : // Try to restrict move range MOVE_RANGE so that it is possible to
      68                 :            : // insert INSN after both of the end points.  Return true on success,
      69                 :            : // otherwise leave MOVE_RANGE in an invalid state.
      70                 :            : inline bool
      71                 :   21317928 : canonicalize_move_range (insn_range_info &move_range, insn_info *insn)
      72                 :            : {
      73                 :   21317928 :   while (move_range.first != insn && !can_insert_after (move_range.first))
      74                 :          0 :     move_range.first = move_range.first->next_nondebug_insn ();
      75                 :   21317928 :   while (move_range.last != insn && !can_insert_after (move_range.last))
      76                 :          0 :     move_range.last = move_range.last->prev_nondebug_insn ();
      77                 :   21317928 :   return bool (move_range);
      78                 :            : }
      79                 :            : 
      80                 :            : // Try to restrict movement range MOVE_RANGE of INSN so that it can set
      81                 :            : // or clobber REGNO.  Assume that if:
      82                 :            : //
      83                 :            : // - an instruction I2 contains another access A to REGNO; and
      84                 :            : // - IGNORE (I2) is true
      85                 :            : //
      86                 :            : // then either:
      87                 :            : //
      88                 :            : // - A will be removed; or
      89                 :            : // - something will ensure that the new definition of REGNO does not
      90                 :            : //   interfere with A, without this having to be enforced by I1's move range.
      91                 :            : //
      92                 :            : // Return true on success, otherwise leave MOVE_RANGE in an invalid state.
      93                 :            : //
      94                 :            : // This function only works correctly for instructions that remain within
      95                 :            : // the same extended basic block.
      96                 :            : template<typename IgnorePredicate>
      97                 :            : bool
      98                 :          0 : restrict_movement_for_dead_range (insn_range_info &move_range,
      99                 :            :                                   unsigned int regno, insn_info *insn,
     100                 :            :                                   IgnorePredicate ignore)
     101                 :            : {
     102                 :            :   // Find a definition at or neighboring INSN.
     103                 :          0 :   resource_info resource = full_register (regno);
     104                 :          0 :   def_lookup dl = crtl->ssa->find_def (resource, insn);
     105                 :            : 
     106                 :          0 :   def_info *prev = dl.prev_def ();
     107                 :          0 :   ebb_info *ebb = insn->ebb ();
     108                 :          0 :   if (!prev || prev->ebb () != ebb)
     109                 :            :     {
     110                 :            :       // REGNO is not defined or used in EBB before INSN, but it
     111                 :            :       // might be live on entry.  To keep complexity under control,
     112                 :            :       // handle only these cases:
     113                 :            :       //
     114                 :            :       // - If the register is not live on entry to EBB, the register is
     115                 :            :       //   free from the start of EBB to the first definition in EBB.
     116                 :            :       //
     117                 :            :       // - Otherwise, if the register is live on entry to BB, refuse
     118                 :            :       //   to allocate the register.  We could in principle try to move
     119                 :            :       //   the instruction to later blocks in the EBB, but it's rarely
     120                 :            :       //   worth the effort, and could lead to linear complexity.
     121                 :            :       //
     122                 :            :       // - Otherwise, don't allow INSN to move earlier than its current
     123                 :            :       //   block.  Again, we could in principle look backwards to find where
     124                 :            :       //   REGNO dies, but it's rarely worth the effort.
     125                 :          0 :       bb_info *bb = insn->bb ();
     126                 :            :       insn_info *limit;
     127                 :          0 :       if (!bitmap_bit_p (DF_LR_IN (ebb->first_bb ()->cfg_bb ()), regno))
     128                 :          0 :         limit = ebb->phi_insn ();
     129                 :          0 :       else if (bitmap_bit_p (DF_LR_IN (bb->cfg_bb ()), regno))
     130                 :            :         return false;
     131                 :            :       else
     132                 :          0 :         limit = bb->head_insn ();
     133                 :          0 :       move_range = move_later_than (move_range, limit);
     134                 :            :     }
     135                 :            :   else
     136                 :            :     {
     137                 :            :       // Stop the instruction moving beyond the previous relevant access
     138                 :            :       // to REGNO.
     139                 :            :       access_info *prev_access
     140                 :          0 :         = last_access_ignoring (prev, ignore_clobbers::YES, ignore);
     141                 :          0 :       if (prev_access)
     142                 :          0 :         move_range = move_later_than (move_range, access_insn (prev_access));
     143                 :            :     }
     144                 :            : 
     145                 :            :   // Stop the instruction moving beyond the next relevant definition of REGNO.
     146                 :          0 :   def_info *next = first_def_ignoring (dl.matching_or_next_def (),
     147                 :            :                                        ignore_clobbers::YES, ignore);
     148                 :          0 :   if (next)
     149                 :          0 :     move_range = move_earlier_than (move_range, next->insn ());
     150                 :            : 
     151                 :          0 :   return canonicalize_move_range (move_range, insn);
     152                 :            : }
     153                 :            : 
     154                 :            : // Try to restrict movement range MOVE_RANGE so that it is possible for the
     155                 :            : // instruction being moved ("instruction I1") to perform all the definitions
     156                 :            : // in DEFS while still preserving dependencies between those definitions
     157                 :            : // and surrounding instructions.  Assume that if:
     158                 :            : //
     159                 :            : // - DEFS contains a definition D of resource R;
     160                 :            : // - an instruction I2 contains another access A to R; and
     161                 :            : // - IGNORE (I2) is true
     162                 :            : //
     163                 :            : // then either:
     164                 :            : //
     165                 :            : // - A will be removed; or
     166                 :            : // - something will ensure that D and A maintain their current order,
     167                 :            : //   without this having to be enforced by I1's move range.
     168                 :            : //
     169                 :            : // Return true on success, otherwise leave MOVE_RANGE in an invalid state.
     170                 :            : //
     171                 :            : // This function only works correctly for instructions that remain within
     172                 :            : // the same extended basic block.
     173                 :            : template<typename IgnorePredicate>
     174                 :            : bool
     175                 :   19063115 : restrict_movement_for_defs_ignoring (insn_range_info &move_range,
     176                 :            :                                      def_array defs, IgnorePredicate ignore)
     177                 :            : {
     178                 :   46816627 :   for (def_info *def : defs)
     179                 :            :     {
     180                 :            :       // If the definition is a clobber, we can move it with respect
     181                 :            :       // to other clobbers.
     182                 :            :       //
     183                 :            :       // ??? We could also do this if a definition and all its uses
     184                 :            :       // are being moved at once.
     185                 :   27753512 :       bool is_clobber = is_a<clobber_info *> (def);
     186                 :            : 
     187                 :            :       // Search back for the first unfiltered use or definition of the
     188                 :            :       // same resource.
     189                 :            :       access_info *access;
     190                 :   27753512 :       access = prev_access_ignoring (def, ignore_clobbers (is_clobber),
     191                 :            :                                      ignore);
     192                 :   27753512 :       if (access)
     193                 :   15535126 :         move_range = move_later_than (move_range, access_insn (access));
     194                 :            : 
     195                 :            :       // Search forward for the first unfiltered use of DEF,
     196                 :            :       // or the first unfiltered definition that follows DEF.
     197                 :            :       //
     198                 :            :       // We don't need to consider uses of following definitions, since
     199                 :            :       // if IGNORE (D->insn ()) is true for some definition D, the caller
     200                 :            :       // is guarantees that either
     201                 :            :       //
     202                 :            :       // - D will be removed, and thus its uses will be removed; or
     203                 :            :       // - D will occur after DEF, and thus D's uses will also occur
     204                 :            :       //   after DEF.
     205                 :            :       //
     206                 :            :       // This is purely a simplification: we could also process D's uses,
     207                 :            :       // but we don't need to.
     208                 :   27753512 :       access = next_access_ignoring (def, ignore_clobbers (is_clobber),
     209                 :            :                                      ignore);
     210                 :   27753512 :       if (access)
     211                 :   21644791 :         move_range = move_earlier_than (move_range, access_insn (access));
     212                 :            : 
     213                 :            :       // If DEF sets a hard register, take any call clobbers
     214                 :            :       // into account.
     215                 :   27753512 :       unsigned int regno = def->regno ();
     216                 :   27753512 :       if (!HARD_REGISTER_NUM_P (regno) || is_clobber)
     217                 :   20509847 :         continue;
     218                 :            : 
     219                 :    7243665 :       ebb_info *ebb = def->ebb ();
     220                 :   12798078 :       for (ebb_call_clobbers_info *call_group : ebb->call_clobbers ())
     221                 :            :         {
     222                 :    5554413 :           if (!call_group->clobbers (def->resource ()))
     223                 :     460797 :             continue;
     224                 :            : 
     225                 :            :           // Exit now if we've already failed, and if the splay accesses
     226                 :            :           // below would be wasted work.
     227                 :    5093616 :           if (!move_range)
     228                 :   19063115 :             return false;
     229                 :            : 
     230                 :            :           insn_info *insn;
     231                 :    5093616 :           insn = prev_call_clobbers_ignoring (*call_group, def->insn (),
     232                 :            :                                               ignore);
     233                 :    5093616 :           if (insn)
     234                 :    2387720 :             move_range = move_later_than (move_range, insn);
     235                 :            : 
     236                 :    5093616 :           insn = next_call_clobbers_ignoring (*call_group, def->insn (),
     237                 :            :                                               ignore);
     238                 :    5093616 :           if (insn)
     239                 :    3317864 :             move_range = move_earlier_than (move_range, insn);
     240                 :            :         }
     241                 :            :     }
     242                 :            : 
     243                 :            :   // Make sure that we don't move stores between basic blocks, since we
     244                 :            :   // don't have enough information to tell whether it's safe.
     245                 :   19063115 :   if (def_info *def = memory_access (defs))
     246                 :            :     {
     247                 :    5247308 :       move_range = move_later_than (move_range, def->bb ()->head_insn ());
     248                 :    5247308 :       move_range = move_earlier_than (move_range, def->bb ()->end_insn ());
     249                 :            :     }
     250                 :            : 
     251                 :   19063115 :   return bool (move_range);
     252                 :            : }
     253                 :            : 
     254                 :            : // Like restrict_movement_for_defs_ignoring, but for the uses in USES.
     255                 :            : template<typename IgnorePredicate>
     256                 :            : bool
     257                 :   20322709 : restrict_movement_for_uses_ignoring (insn_range_info &move_range,
     258                 :            :                                      use_array uses, IgnorePredicate ignore)
     259                 :            : {
     260                 :   84555372 :   for (const use_info *use : uses)
     261                 :            :     {
     262                 :            :       // Ignore uses of undefined values.
     263                 :   64237496 :       set_info *set = use->def ();
     264                 :   64237496 :       if (!set)
     265                 :        753 :         continue;
     266                 :            : 
     267                 :            :       // Ignore uses by debug instructions.  Debug instructions are
     268                 :            :       // never supposed to move, and uses by debug instructions are
     269                 :            :       // never supposed to be transferred elsewhere, so we know that
     270                 :            :       // the caller must be changing the uses on the debug instruction
     271                 :            :       // and checking whether all new uses are available at the debug
     272                 :            :       // instruction's original location.
     273                 :   64236743 :       if (use->is_in_debug_insn ())
     274                 :    2070761 :         continue;
     275                 :            : 
     276                 :            :       // If the used value is defined by an instruction I2 for which
     277                 :            :       // IGNORE (I2) is true, the caller guarantees that I2 will occur
     278                 :            :       // before change.insn ().  Otherwise, make sure that the use occurs
     279                 :            :       // after the definition.
     280                 :   62165982 :       insn_info *insn = set->insn ();
     281                 :   62165982 :       if (!ignore (insn))
     282                 :   62165982 :         move_range = move_later_than (move_range, insn);
     283                 :            : 
     284                 :            :       // Search forward for the first unfiltered definition that follows SET.
     285                 :            :       //
     286                 :            :       // We don't need to consider the uses of these definitions, since
     287                 :            :       // if IGNORE (D->insn ()) is true for some definition D, the caller
     288                 :            :       // is guarantees that either
     289                 :            :       //
     290                 :            :       // - D will be removed, and thus its uses will be removed; or
     291                 :            :       // - D will occur after USE, and thus D's uses will also occur
     292                 :            :       //   after USE.
     293                 :            :       //
     294                 :            :       // This is purely a simplification: we could also process D's uses,
     295                 :            :       // but we don't need to.
     296                 :            :       def_info *def;
     297                 :   83271971 :       def = first_def_ignoring (set->next_def (), ignore_clobbers::NO,
     298                 :            :                                 ignore);
     299                 :   62165982 :       if (def)
     300                 :   20435540 :         move_range = move_earlier_than (move_range, def->insn ());
     301                 :            : 
     302                 :            :       // If USE uses a hard register, take any call clobbers into account too.
     303                 :            :       // SET will necessarily occur after any previous call clobber, so we
     304                 :            :       // only need to check for later clobbers.
     305                 :   62165982 :       unsigned int regno = use->regno ();
     306                 :   62165982 :       if (!HARD_REGISTER_NUM_P (regno))
     307                 :   47629707 :         continue;
     308                 :            : 
     309                 :   14536275 :       ebb_info *ebb = use->ebb ();
     310                 :   27423275 :       for (ebb_call_clobbers_info *call_group : ebb->call_clobbers ())
     311                 :            :         {
     312                 :   12891833 :           if (!call_group->clobbers (use->resource ()))
     313                 :    4982324 :             continue;
     314                 :            : 
     315                 :    7909509 :           if (!move_range)
     316                 :   20322709 :             return false;
     317                 :            : 
     318                 :    7904676 :           insn_info *insn = next_call_clobbers_ignoring (*call_group,
     319                 :            :                                                          use->insn (), ignore);
     320                 :    7904676 :           if (insn)
     321                 :    3367467 :             move_range = move_earlier_than (move_range, insn);
     322                 :            :         }
     323                 :            :     }
     324                 :            : 
     325                 :            :   // Make sure that we don't move loads into an earlier basic block.
     326                 :            :   //
     327                 :            :   // ??? It would be good to relax this for loads that can be safely
     328                 :            :   // speculated.
     329                 :   20317876 :   if (use_info *use = memory_access (uses))
     330                 :    9719360 :     move_range = move_later_than (move_range, use->bb ()->head_insn ());
     331                 :            : 
     332                 :   20317876 :   return bool (move_range);
     333                 :            : }
     334                 :            : 
     335                 :            : }

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.