LCOV - code coverage report
Current view: top level - gcc - gimple-range-path.cc (source / functions) Coverage Total Hit
Test: gcc.info Lines: 87.4 % 356 311
Test Date: 2026-11-14 16:39:50 Functions: 94.1 % 34 32
Legend: Lines:     hit not hit

            Line data    Source code
       1              : /* Basic block path solver.
       2              :    Copyright (C) 2021-2026 Free Software Foundation, Inc.
       3              :    Contributed by Aldy Hernandez <aldyh@redhat.com>.
       4              : 
       5              : This file is part of GCC.
       6              : 
       7              : GCC is free software; you can redistribute it and/or modify it under
       8              : the terms of the GNU General Public License as published by the Free
       9              : Software Foundation; either version 3, or (at your option) any later
      10              : version.
      11              : 
      12              : GCC is distributed in the hope that it will be useful, but WITHOUT ANY
      13              : WARRANTY; without even the implied warranty of MERCHANTABILITY or
      14              : FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
      15              :  for more details.
      16              : 
      17              : You should have received a copy of the GNU General Public License
      18              : along with GCC; see the file COPYING3.  If not see
      19              : <http://www.gnu.org/licenses/>.  */
      20              : 
      21              : #include "config.h"
      22              : #include "system.h"
      23              : #include "coretypes.h"
      24              : #include "backend.h"
      25              : #include "tree.h"
      26              : #include "gimple.h"
      27              : #include "cfganal.h"
      28              : #include "value-range.h"
      29              : #include "gimple-range.h"
      30              : #include "tree-pretty-print.h"
      31              : #include "gimple-range-path.h"
      32              : #include "ssa.h"
      33              : #include "tree-cfg.h"
      34              : #include "gimple-iterator.h"
      35              : 
      36       818907 : path_range_query::path_range_query (gimple_ranger &ranger,
      37              :                                     const vec<basic_block> &path,
      38              :                                     const bitmap_head *dependencies,
      39              :                                     bool resolve)
      40       818907 :   : m_cache (),
      41       818907 :     m_ranger (ranger),
      42       818907 :     m_resolve (resolve)
      43              : {
      44       818907 :   share_query (ranger);
      45              :   // Override the relation oracle with a local path relation oracle.
      46       818907 :   m_relation = new path_oracle (&(m_ranger.relation ()));
      47              : 
      48       818907 :   reset_path (path, dependencies);
      49       818907 : }
      50              : 
      51      8581814 : path_range_query::path_range_query (gimple_ranger &ranger, bool resolve)
      52      8581814 :   : m_cache (),
      53      8581814 :     m_ranger (ranger),
      54      8581814 :     m_resolve (resolve)
      55              : {
      56      8581814 :   share_query (ranger);
      57              :   // Override the relation oracle with a local path relation oracle.
      58      8581814 :   m_relation = new path_oracle (&(m_ranger.relation ()));
      59      8581814 : }
      60              : 
      61     16675176 : path_range_query::~path_range_query ()
      62              : {
      63      9400721 :   delete m_relation;
      64      9400721 :   m_relation = NULL;
      65     16675176 : }
      66              : 
      67              : // Return TRUE if NAME is an exit dependency for the path.
      68              : 
      69              : bool
      70    144053616 : path_range_query::exit_dependency_p (tree name)
      71              : {
      72    144053616 :   return (TREE_CODE (name) == SSA_NAME
      73    144053616 :           && bitmap_bit_p (m_exit_dependencies, SSA_NAME_VERSION (name)));
      74              : }
      75              : 
      76              : // If NAME has a cache entry, return it in R, and return TRUE.
      77              : 
      78              : inline bool
      79    408704045 : path_range_query::get_cache (vrange &r, tree name)
      80              : {
      81    408704045 :   if (!gimple_range_ssa_p (name))
      82     80028771 :     return get_global_range_query ()->range_of_expr (r, name);
      83              : 
      84    328675274 :   return m_cache.get_range (r, name);
      85              : }
      86              : 
      87              : void
      88            0 : path_range_query::dump (FILE *dump_file)
      89              : {
      90            0 :   push_dump_file save (dump_file, dump_flags & ~TDF_DETAILS);
      91              : 
      92            0 :   if (m_path.is_empty ())
      93            0 :     return;
      94              : 
      95            0 :   unsigned i;
      96            0 :   bitmap_iterator bi;
      97              : 
      98            0 :   dump_ranger (dump_file, m_path);
      99              : 
     100            0 :   fprintf (dump_file, "Exit dependencies:\n");
     101            0 :   EXECUTE_IF_SET_IN_BITMAP (m_exit_dependencies, 0, i, bi)
     102              :     {
     103            0 :       tree name = ssa_name (i);
     104            0 :       print_generic_expr (dump_file, name, TDF_SLIM);
     105            0 :       fprintf (dump_file, "\n");
     106              :     }
     107              : 
     108            0 :   m_cache.dump (dump_file);
     109            0 : }
     110              : 
     111              : void
     112            0 : path_range_query::debug ()
     113              : {
     114            0 :   dump (stderr);
     115            0 : }
     116              : 
     117              : // Return TRUE if NAME is defined outside the current path.
     118              : 
     119              : bool
     120     69264887 : path_range_query::defined_outside_path (tree name)
     121              : {
     122     69264887 :   gimple *def = SSA_NAME_DEF_STMT (name);
     123     69264887 :   basic_block bb = gimple_bb (def);
     124              : 
     125     69264887 :   return !bb || !m_path.contains (bb);
     126              : }
     127              : 
     128              : // Return the range of NAME on entry to the path.
     129              : 
     130              : void
     131     25875898 : path_range_query::range_on_path_entry (vrange &r, tree name)
     132              : {
     133     25875898 :   gcc_checking_assert (defined_outside_path (name));
     134     25875898 :   basic_block entry = entry_bb ();
     135     25875898 :   m_ranger.range_on_entry (r, entry, name);
     136     25875898 : }
     137              : 
     138              : // Return the range of NAME at the end of the path being analyzed.
     139              : 
     140              : bool
     141    285736728 : path_range_query::internal_range_of_expr (vrange &r, tree name, gimple *stmt)
     142              : {
     143    285736728 :   if (!r.supports_type_p (TREE_TYPE (name)))
     144              :     return false;
     145              : 
     146    285736728 :   if (get_cache (r, name))
     147              :     return true;
     148              : 
     149     65245969 :   if (m_resolve && defined_outside_path (name))
     150              :     {
     151     24106982 :       range_on_path_entry (r, name);
     152     24106982 :       m_cache.set_range (name, r);
     153     24106982 :       return true;
     154              :     }
     155              : 
     156              :   // We can be called from match.pd or elsewhere, with a context statement
     157              :   // that can be anywhere on the path.  Since we can only compute ranges
     158              :   // mid flight at the current path position, check that's the case,
     159              :   // otherwise fall through to the global range.
     160     41138987 :   if (stmt
     161     41013495 :       && gimple_bb (stmt) == curr_bb ()
     162     82152482 :       && range_defined_in_block (r, name, gimple_bb (stmt)))
     163              :     {
     164     21405739 :       if (TREE_CODE (name) == SSA_NAME)
     165              :         {
     166     21405739 :           value_range glob (TREE_TYPE (name));
     167     21405739 :           gimple_range_global (glob, name);
     168     21405739 :           r.intersect (glob);
     169     21405739 :         }
     170              : 
     171     21405739 :       m_cache.set_range (name, r);
     172     21405739 :       return true;
     173              :     }
     174              : 
     175     19733248 :   gimple_range_global (r, name);
     176     19733248 :   return true;
     177              : }
     178              : 
     179              : bool
     180    285736728 : path_range_query::range_of_expr (vrange &r, tree name, gimple *stmt)
     181              : {
     182    285736728 :   if (internal_range_of_expr (r, name, stmt))
     183              :     {
     184    285736728 :       if (r.undefined_p ())
     185       251674 :         m_undefined_path = true;
     186              : 
     187              :       return true;
     188              :     }
     189              :   return false;
     190              : }
     191              : 
     192              : bool
     193     28262671 : path_range_query::unreachable_path_p ()
     194              : {
     195     28262671 :   return m_undefined_path;
     196              : }
     197              : 
     198              : // Reset the current path to PATH.
     199              : 
     200              : void
     201     37922898 : path_range_query::reset_path (const vec<basic_block> &path,
     202              :                               const bitmap_head *dependencies)
     203              : {
     204     37922898 :   gcc_checking_assert (path.length () > 1);
     205              : 
     206              :   // Use truncate/safe_splice instead of copy() to avoid repeated mallocs here.
     207     37922898 :   m_path.truncate (0);
     208     37922898 :   m_path.safe_splice (path);
     209              : 
     210     37922898 :   m_pos = m_path.length () - 1;
     211     37922898 :   m_undefined_path = false;
     212     37922898 :   m_cache.clear ();
     213              : 
     214     37922898 :   compute_ranges (dependencies);
     215     37922898 : }
     216              : 
     217              : bool
     218    276575463 : path_range_query::ssa_defined_in_bb (tree name, basic_block bb)
     219              : {
     220    276575463 :   return (TREE_CODE (name) == SSA_NAME
     221    271973484 :           && SSA_NAME_DEF_STMT (name)
     222    548548947 :           && gimple_bb (SSA_NAME_DEF_STMT (name)) == bb);
     223              : }
     224              : 
     225              : // Return the range of the result of PHI in R.
     226              : //
     227              : // Since PHIs are calculated in parallel at the beginning of the
     228              : // block, we must be careful to never save anything to the cache here.
     229              : // It is the caller's responsibility to adjust the cache.  Also,
     230              : // calculating the PHI's range must not trigger additional lookups.
     231              : 
     232              : void
     233     22606967 : path_range_query::ssa_range_in_phi (vrange &r, gphi *phi)
     234              : {
     235     22606967 :   tree name = gimple_phi_result (phi);
     236              : 
     237     45213934 :   if (at_entry ())
     238              :     {
     239      3804009 :       if (m_resolve && m_ranger.range_of_expr (r, name, phi))
     240              :         return;
     241              : 
     242              :       // Try to fold the phi exclusively with global values.
     243              :       // This will get things like PHI <5(99), 6(88)>.  We do this by
     244              :       // calling range_of_expr with no context.
     245      1787046 :       unsigned nargs = gimple_phi_num_args (phi);
     246      1787046 :       value_range arg_range (TREE_TYPE (name));
     247      1787046 :       r.set_undefined ();
     248      7763441 :       for (size_t i = 0; i < nargs; ++i)
     249              :         {
     250      4189349 :           tree arg = gimple_phi_arg_def (phi, i);
     251      4189349 :           if (m_ranger.range_of_expr (arg_range, arg, /*stmt=*/NULL))
     252      4189349 :             r.union_ (arg_range);
     253              :           else
     254              :             {
     255            0 :               r.set_varying (TREE_TYPE (name));
     256            0 :               return;
     257              :             }
     258              :         }
     259              :       return;
     260      1787046 :     }
     261              : 
     262     18802958 :   basic_block bb = gimple_bb (phi);
     263     18802958 :   basic_block prev = prev_bb ();
     264     18802958 :   edge e_in = find_edge (prev, bb);
     265              :   // The incoming edge the path supplies is never abnormal, so the
     266              :   // argument on it is a valid value for the PHI result even when the
     267              :   // result occurs in an abnormal PHI.
     268     18802958 :   gcc_checking_assert (!(e_in->flags & EDGE_ABNORMAL));
     269     18802958 :   tree arg = PHI_ARG_DEF_FROM_EDGE (phi, e_in);
     270              :   // Avoid using the cache for ARGs defined in this block, as
     271              :   // that could create an ordering problem.
     272     18802958 :   if (ssa_defined_in_bb (arg, bb) || !get_cache (r, arg))
     273              :     {
     274      4990486 :       if (m_resolve)
     275              :         {
     276      2880805 :           value_range tmp (TREE_TYPE (name));
     277              :           // Using both the range on entry to the path, and the
     278              :           // range on this edge yields significantly better
     279              :           // results.
     280      2880805 :           if (TREE_CODE (arg) == SSA_NAME
     281      2880805 :               && defined_outside_path (arg))
     282      1768916 :             range_on_path_entry (r, arg);
     283              :           else
     284      1111889 :             r.set_varying (TREE_TYPE (name));
     285      2880805 :           m_ranger.range_on_edge (tmp, e_in, arg);
     286      2880805 :           r.intersect (tmp);
     287      2880805 :           return;
     288      2880805 :         }
     289      2109681 :       r.set_varying (TREE_TYPE (name));
     290              :     }
     291              : }
     292              : 
     293              : // If NAME is defined in BB, set R to the range of NAME, and return
     294              : // TRUE.  Otherwise, return FALSE.
     295              : 
     296              : bool
     297    231021488 : path_range_query::range_defined_in_block (vrange &r, tree name, basic_block bb)
     298              : {
     299              :   // Ranges can only be calculated at the current path position, both
     300              :   // while pre-computing the cache and when answering questions at the
     301              :   // path exit afterwards.
     302    231021488 :   gcc_assert (bb == curr_bb ());
     303              : 
     304    231021488 :   gimple *def_stmt = SSA_NAME_DEF_STMT (name);
     305    231021488 :   basic_block def_bb = gimple_bb (def_stmt);
     306              : 
     307    231021488 :   if (def_bb != bb)
     308              :     return false;
     309              : 
     310     81453212 :   if (get_cache (r, name))
     311              :     return true;
     312              : 
     313     79653756 :   if (gimple_code (def_stmt) == GIMPLE_PHI)
     314     22606967 :     ssa_range_in_phi (r, as_a<gphi *> (def_stmt));
     315              :   else
     316              :     {
     317     57046789 :       if (name)
     318     57046789 :         get_path_oracle ()->killing_def (name);
     319              : 
     320     57046789 :       if (!range_of_stmt (r, def_stmt, name))
     321        15590 :         r.set_varying (TREE_TYPE (name));
     322              :     }
     323              : 
     324     79653756 :   if (bb && POINTER_TYPE_P (TREE_TYPE (name)))
     325     12271117 :     infer_oracle ().maybe_adjust_range (r, name, bb);
     326              : 
     327     79653756 :   if (DEBUG_PATH_RANGER && (bb || !r.varying_p ()))
     328              :     {
     329            0 :       fprintf (dump_file, "range_defined_in_block (BB%d) for ", bb ? bb->index : -1);
     330            0 :       print_generic_expr (dump_file, name, TDF_SLIM);
     331            0 :       fprintf (dump_file, " is ");
     332            0 :       r.dump (dump_file);
     333            0 :       fprintf (dump_file, "\n");
     334              :     }
     335              : 
     336              :   return true;
     337              : }
     338              : 
     339              : // Compute ranges defined in the PHIs in this block.
     340              : 
     341              : void
     342    103467147 : path_range_query::compute_ranges_in_phis (basic_block bb)
     343              : {
     344              :   // PHIs must be resolved simultaneously on entry to the block
     345              :   // because any dependencies must be satisfied with values on entry.
     346              :   // Thus, we calculate all PHIs first, and then update the cache at
     347              :   // the end.
     348              : 
     349    202041471 :   for (auto iter = gsi_start_phis (bb); !gsi_end_p (iter); gsi_next (&iter))
     350              :     {
     351     98574324 :       gphi *phi = iter.phi ();
     352     98574324 :       tree name = gimple_phi_result (phi);
     353              : 
     354     98574324 :       if (!exit_dependency_p (name))
     355     77806064 :         continue;
     356              : 
     357     20768260 :       value_range r (TREE_TYPE (name));
     358     20768260 :       if (range_defined_in_block (r, name, bb))
     359     20768260 :         m_cache.set_range (name, r);
     360     20768260 :     }
     361    103467147 : }
     362              : 
     363              : // Return TRUE if relations may be invalidated after crossing edge E.
     364              : 
     365              : bool
     366     45212056 : path_range_query::relations_may_be_invalidated (edge e)
     367              : {
     368              :   // As soon as the path crosses a back edge, we can encounter
     369              :   // definitions of SSA_NAMEs that may have had a use in the path
     370              :   // already, so this will then be a new definition.  The relation
     371              :   // code is all designed around seeing things in dominator order, and
     372              :   // crossing a back edge in the path violates this assumption.
     373     45212056 :   return (e->flags & EDGE_DFS_BACK);
     374              : }
     375              : 
     376              : // Compute ranges defined in the current block, or exported to the
     377              : // next block.
     378              : 
     379              : void
     380    103467147 : path_range_query::compute_ranges_in_block (basic_block bb)
     381              : {
     382    103467147 :   bitmap_iterator bi;
     383    103467147 :   unsigned i;
     384              : 
     385    163666778 :   if (m_resolve && !at_entry ())
     386     37949690 :     compute_phi_relations (bb, prev_bb ());
     387              : 
     388              :   // Force recalculation of any names in the cache that are defined in
     389              :   // this block.  This can happen on interdependent SSA/phis in loops.
     390    355934555 :   EXECUTE_IF_SET_IN_BITMAP (m_exit_dependencies, 0, i, bi)
     391              :     {
     392    252467408 :       tree name = ssa_name (i);
     393    252467408 :       if (ssa_defined_in_bb (name, bb))
     394     60047473 :         m_cache.clear_range (name);
     395              :     }
     396              : 
     397              :   // Solve dependencies defined in this block, starting with the PHIs...
     398    103467147 :   compute_ranges_in_phis (bb);
     399              :   // ...and then the rest of the dependencies.
     400    355934555 :   EXECUTE_IF_SET_IN_BITMAP (m_exit_dependencies, 0, i, bi)
     401              :     {
     402    252467408 :       tree name = ssa_name (i);
     403    252467408 :       value_range r (TREE_TYPE (name));
     404              : 
     405    252467408 :       if (gimple_code (SSA_NAME_DEF_STMT (name)) != GIMPLE_PHI
     406    252467408 :           && range_defined_in_block (r, name, bb))
     407     39279213 :         m_cache.set_range (name, r);
     408    252467408 :     }
     409              : 
     410    103467147 :   if (at_exit ())
     411     37922898 :     return;
     412              : 
     413              :   // Solve dependencies that are exported to the next block.
     414     65544249 :   basic_block next = next_bb ();
     415     65544249 :   edge e = find_edge (bb, next);
     416              : 
     417     65544249 :   if (m_resolve && relations_may_be_invalidated (e))
     418              :     {
     419      2185684 :       if (DEBUG_PATH_RANGER)
     420            0 :         fprintf (dump_file,
     421              :                  "Resetting relations as they may be invalidated in %d->%d.\n",
     422            0 :                  e->src->index, e->dest->index);
     423              : 
     424      2185684 :       path_oracle *p = get_path_oracle ();
     425              :       // ?? Instead of nuking the root oracle altogether, we could
     426              :       // reset the path oracle to search for relations from the top of
     427              :       // the loop with the root oracle.  Something for future development.
     428      2185684 :       p->reset_path ();
     429              :     }
     430              : 
     431     65544249 :   bitmap exports = gori_ssa ()->exports (bb);
     432     82016890 :   EXECUTE_IF_AND_IN_BITMAP (m_exit_dependencies, exports, 0, i, bi)
     433              :     {
     434     16472641 :       tree name = ssa_name (i);
     435     16472641 :       value_range r (TREE_TYPE (name));
     436     16472641 :       if (gori ().edge_range_p (r, e, name, *this))
     437              :         {
     438     14718544 :           value_range cached_range (TREE_TYPE (name));
     439     14718544 :           if (get_cache (cached_range, name))
     440     11684962 :             r.intersect (cached_range);
     441              : 
     442     14718544 :           m_cache.set_range (name, r);
     443     14718544 :           if (DEBUG_PATH_RANGER)
     444              :             {
     445            0 :               fprintf (dump_file, "edge_range_p for ");
     446            0 :               print_generic_expr (dump_file, name, TDF_SLIM);
     447            0 :               fprintf (dump_file, " on edge %d->%d ",
     448            0 :                        e->src->index, e->dest->index);
     449            0 :               fprintf (dump_file, "is ");
     450            0 :               r.dump (dump_file);
     451            0 :               fprintf (dump_file, "\n");
     452              :             }
     453     14718544 :         }
     454     16472641 :     }
     455              : 
     456     65544249 :   if (m_resolve)
     457     37949690 :     compute_outgoing_relations (bb, next);
     458              : }
     459              : 
     460              : // Adjust all pointer exit dependencies in BB with non-null information.
     461              : 
     462              : void
     463    103467147 : path_range_query::adjust_for_non_null_uses (basic_block bb)
     464              : {
     465              :   // If there are no pointer exit dependencies with an inferred range, there's
     466              :   // nothing to do.
     467    103467147 :   if (m_pointer_exit_dependencies.is_empty ()
     468     22794784 :       || !infer_oracle ().has_range_p (bb))
     469    100011768 :     return;
     470              : 
     471      3455379 :   prange r;
     472              : 
     473     19021964 :   for (tree name : m_pointer_exit_dependencies)
     474              :     {
     475      8655827 :       if (get_cache (r, name))
     476              :         {
     477      3737813 :           if (!r.contains_zero_p ())
     478      2114805 :             continue;
     479              :         }
     480              :       else
     481      4918014 :         r.set_varying (TREE_TYPE (name));
     482              : 
     483      6541022 :       if (infer_oracle ().maybe_adjust_range (r, name, bb))
     484       825373 :         m_cache.set_range (name, r);
     485              :     }
     486      3455379 : }
     487              : 
     488              : // If NAME is a supported SSA_NAME, add it to the bitmap in dependencies.
     489              : 
     490              : bool
     491       166683 : path_range_query::add_to_exit_dependencies (tree name, bitmap dependencies)
     492              : {
     493       166683 :   if (TREE_CODE (name) == SSA_NAME
     494       166683 :       && value_range::supports_type_p (TREE_TYPE (name)))
     495       166683 :     return bitmap_set_bit (dependencies, SSA_NAME_VERSION (name));
     496              :   return false;
     497              : }
     498              : 
     499              : // Add to DEPENDENCIES the operands used to define NAME along PATH,
     500              : // and push the new ones onto WORKLIST.
     501              : 
     502              : void
     503      1529604 : path_range_query::add_dependencies_of (tree name,
     504              :                                        const vec<basic_block> &path,
     505              :                                        bitmap dependencies,
     506              :                                        vec<tree> &worklist)
     507              : {
     508      1529604 :   gimple *def_stmt = SSA_NAME_DEF_STMT (name);
     509      1529604 :   if (SSA_NAME_IS_DEFAULT_DEF (name)
     510      1529604 :       || !path.contains (gimple_bb (def_stmt)))
     511              :     return;
     512              : 
     513      1199843 :   if (gphi *phi = dyn_cast <gphi *> (def_stmt))
     514              :     {
     515      1938799 :       for (size_t i = 0; i < gimple_phi_num_args (phi); ++i)
     516              :         {
     517      1295251 :           edge e = gimple_phi_arg_edge (phi, i);
     518      1295251 :           tree arg = gimple_phi_arg (phi, i)->def;
     519              : 
     520      1295251 :           if (TREE_CODE (arg) == SSA_NAME
     521       819118 :               && path.contains (e->src)
     522      1456402 :               && bitmap_set_bit (dependencies, SSA_NAME_VERSION (arg)))
     523       150314 :             worklist.safe_push (arg);
     524              :         }
     525              :     }
     526       556295 :   else if (gassign *ass = dyn_cast <gassign *> (def_stmt))
     527              :     {
     528       518826 :       tree ssa[3];
     529       518826 :       unsigned count = gimple_range_ssa_names (ssa, 3, ass);
     530      1204335 :       for (unsigned j = 0; j < count; ++j)
     531       166683 :         if (add_to_exit_dependencies (ssa[j], dependencies))
     532        93575 :           worklist.safe_push (ssa[j]);
     533              :     }
     534              : }
     535              : 
     536              : // Close DEPENDENCIES along PATH over add_dependencies_of.
     537              : 
     538              : void
     539       818907 : path_range_query::close_dependencies (const vec<basic_block> &path,
     540              :                                       bitmap dependencies)
     541              : {
     542       818907 :   auto_vec<tree> worklist (bitmap_count_bits (dependencies));
     543       818907 :   bitmap_iterator bi;
     544       818907 :   unsigned i;
     545      2104622 :   EXECUTE_IF_SET_IN_BITMAP (dependencies, 0, i, bi)
     546              :     {
     547      1285715 :       tree name = ssa_name (i);
     548      1285715 :       worklist.quick_push (name);
     549              :     }
     550              : 
     551      3166467 :   while (!worklist.is_empty ())
     552      1529604 :     add_dependencies_of (worklist.pop (), path, dependencies, worklist);
     553       818907 : }
     554              : 
     555              : // Compute the exit dependencies to PATH.  These are essentially the
     556              : // SSA names used to calculate the final conditional along the path.
     557              : 
     558              : void
     559       818907 : path_range_query::compute_exit_dependencies (bitmap dependencies)
     560              : {
     561              :   // Start with the imports from the exit block...
     562       818907 :   basic_block exit = m_path[0];
     563       818907 :   bitmap_copy (dependencies, gori_ssa ()->imports (exit));
     564              : 
     565              :   // ...and add any operands used to define these imports.
     566       818907 :   close_dependencies (m_path, dependencies);
     567              : 
     568              :   // Exported booleans along the path, may help conditionals.
     569       818907 :   if (m_resolve)
     570      2688073 :     for (unsigned i = 0; i < m_path.length (); ++i)
     571              :       {
     572      1869166 :         basic_block bb = m_path[i];
     573      1869166 :         tree name;
     574      3805469 :         FOR_EACH_GORI_EXPORT_NAME (gori_ssa (), bb, name)
     575      1936303 :           if (TREE_CODE (TREE_TYPE (name)) == BOOLEAN_TYPE)
     576        58459 :             bitmap_set_bit (dependencies, SSA_NAME_VERSION (name));
     577              :       }
     578       818907 : }
     579              : 
     580              : // Compute the ranges for DEPENDENCIES along PATH.
     581              : //
     582              : // DEPENDENCIES are path exit dependencies.  They are the set of SSA
     583              : // names, any of which could potentially change the value of the final
     584              : // conditional in PATH.  If none is given, the exit dependencies are
     585              : // calculated from the final conditional in the path.
     586              : 
     587              : void
     588     37922898 : path_range_query::compute_ranges (const bitmap_head *dependencies)
     589              : {
     590     37922898 :   if (DEBUG_PATH_RANGER)
     591            0 :     fprintf (dump_file, "\n==============================================\n");
     592              : 
     593     37922898 :   if (dependencies)
     594     37103991 :     bitmap_copy (m_exit_dependencies, dependencies);
     595              :   else
     596       818907 :     compute_exit_dependencies (m_exit_dependencies);
     597              : 
     598              :   // The oracle carries state from any previously solved path, so it has
     599              :   // to be reset even in non-resolving mode.
     600     37922898 :   path_oracle *p = get_path_oracle ();
     601     37922898 :   p->reset_path (&(m_ranger.relation ()));
     602              : 
     603              :   // Collect the pointer exit dependencies once per path.
     604     37922898 :   m_pointer_exit_dependencies.truncate (0);
     605     37922898 :   {
     606     37922898 :     bitmap_iterator bi;
     607     37922898 :     unsigned i;
     608    127389525 :     EXECUTE_IF_SET_IN_BITMAP (m_exit_dependencies, 0, i, bi)
     609              :       {
     610     89466627 :         tree name = ssa_name (i);
     611     89466627 :         if (POINTER_TYPE_P (TREE_TYPE (name)))
     612              :           {
     613              :             // Querying the infer oracle here is what populates its
     614              :             // per-block summaries, so that adjust_for_non_null_uses can
     615              :             // skip a block with no inferred range in it at all.
     616     17323859 :             infer_oracle ().has_range_p (entry_bb (), name);
     617     17323859 :             m_pointer_exit_dependencies.safe_push (name);
     618              :           }
     619              :       }
     620              :   }
     621              : 
     622     37922898 :   if (DEBUG_PATH_RANGER)
     623              :     {
     624            0 :       fprintf (dump_file, "path_range_query: compute_ranges for path: ");
     625            0 :       for (unsigned i = m_path.length (); i > 0; --i)
     626              :         {
     627            0 :           basic_block bb = m_path[i - 1];
     628            0 :           fprintf (dump_file, "%d", bb->index);
     629            0 :           if (i > 1)
     630            0 :             fprintf (dump_file, "->");
     631              :         }
     632            0 :       fprintf (dump_file, "\n");
     633              :     }
     634              : 
     635    169011396 :   while (1)
     636              :     {
     637    103467147 :       basic_block bb = curr_bb ();
     638              : 
     639    103467147 :       compute_ranges_in_block (bb);
     640    103467147 :       adjust_for_non_null_uses (bb);
     641              : 
     642    103467147 :       if (at_exit ())
     643              :         break;
     644              : 
     645     65544249 :       move_next ();
     646     65544249 :     }
     647              : 
     648     37922898 :   if (DEBUG_PATH_RANGER)
     649              :     {
     650            0 :       get_path_oracle ()->dump (dump_file);
     651            0 :       dump (dump_file);
     652              :     }
     653     37922898 : }
     654              : 
     655              : // A folding aid used to register and query relations along a path.
     656              : // When queried, it returns relations as they would appear on exit to
     657              : // the path.
     658              : //
     659              : // Relations are registered on entry so the path_oracle knows which
     660              : // block to query the root oracle at when a relation lies outside the
     661              : // path.  However, when queried we return the relation on exit to the
     662              : // path, since the root_oracle ignores the registered.
     663              : 
     664              : class jt_fur_source : public fur_depend
     665              : {
     666              : public:
     667              :   jt_fur_source (gimple *s, path_range_query *, const vec<basic_block> &);
     668              :   relation_kind query_relation (tree op1, tree op2) override;
     669              :   bool register_relation (gimple *, relation_kind, tree op1, tree op2) override;
     670              :   bool register_relation (edge, relation_kind, tree op1, tree op2) override;
     671              : private:
     672              :   basic_block m_entry;
     673              : };
     674              : 
     675     82130785 : jt_fur_source::jt_fur_source (gimple *s,
     676              :                               path_range_query *query,
     677              :                               const vec<basic_block> &path)
     678     82130785 :   : fur_depend (s, query)
     679              : {
     680     82130785 :   gcc_checking_assert (!path.is_empty ());
     681              : 
     682     82130785 :   m_entry = path[path.length () - 1];
     683     82130785 : }
     684              : 
     685              : // Ignore statement and register relation on entry to path.  Return false if
     686              : // no new relation is registered.
     687              : 
     688              : bool
     689     11445722 : jt_fur_source::register_relation (gimple *, relation_kind k, tree op1, tree op2)
     690              : {
     691     11445722 :   return m_query->relation ().record (m_entry, k, op1, op2);
     692              : }
     693              : 
     694              : // Ignore edge and register relation on entry to path.  Return false if no
     695              : // new relation is registered.
     696              : 
     697              : bool
     698     16078225 : jt_fur_source::register_relation (edge, relation_kind k, tree op1, tree op2)
     699              : {
     700     16078225 :   return m_query->relation ().record (m_entry, k, op1, op2);
     701              : }
     702              : 
     703              : relation_kind
     704     39945508 : jt_fur_source::query_relation (tree op1, tree op2)
     705              : {
     706     39945508 :   if (TREE_CODE (op1) != SSA_NAME || TREE_CODE (op2) != SSA_NAME)
     707              :     return VREL_VARYING;
     708              : 
     709     14256761 :   return m_query->relation ().query (m_entry, op1, op2);
     710              : }
     711              : 
     712              : // Return the range of STMT at the end of the path being analyzed.
     713              : 
     714              : bool
     715     96191172 : path_range_query::range_of_stmt (vrange &r, gimple *stmt, tree)
     716              : {
     717     96191172 :   tree type = gimple_range_type (stmt);
     718              : 
     719     96191172 :   if (!type || !r.supports_type_p (type))
     720              :     return false;
     721              : 
     722              :   // If resolving unknowns, fold the statement making use of any
     723              :   // relations along the path.
     724     96175582 :   if (m_resolve)
     725              :     {
     726     58162942 :       fold_using_range f;
     727     58162942 :       jt_fur_source src (stmt, this, m_path);
     728     58162942 :       if (!f.fold_stmt (r, stmt, src))
     729         5018 :         r.set_varying (type);
     730              :     }
     731              :   // Otherwise, fold without relations.
     732     38012640 :   else if (!fold_range (r, stmt, this))
     733            0 :     r.set_varying (type);
     734              : 
     735              :   return true;
     736              : }
     737              : 
     738              : // If possible, register the relation on the incoming edge E into PHI.
     739              : 
     740              : void
     741      9605629 : path_range_query::maybe_register_phi_relation (gphi *phi, edge e)
     742              : {
     743      9605629 :   tree arg = gimple_phi_arg_def (phi, e->dest_idx);
     744              : 
     745      9605629 :   if (!gimple_range_ssa_p (arg))
     746              :     return;
     747              : 
     748      7262366 :   if (relations_may_be_invalidated (e))
     749              :     return;
     750              : 
     751      5305097 :   basic_block bb = gimple_bb (phi);
     752      5305097 :   tree result = gimple_phi_result (phi);
     753              : 
     754              :   // Avoid recording the equivalence if the arg is defined in this
     755              :   // block, as that could create an ordering problem.
     756      5305097 :   if (ssa_defined_in_bb (arg, bb))
     757              :     return;
     758              : 
     759      5305097 :   if (dump_file && (dump_flags & TDF_DETAILS))
     760           66 :     fprintf (dump_file, "maybe_register_phi_relation in bb%d:", bb->index);
     761              : 
     762      5305097 :   get_path_oracle ()->killing_def (result);
     763      5305097 :   m_relation->record (entry_bb (), VREL_EQ, arg, result);
     764              : }
     765              : 
     766              : // Compute relations for each PHI in BB.  For example:
     767              : //
     768              : //   x_5 = PHI<y_9(5),...>
     769              : //
     770              : // If the path flows through BB5, we can register that x_5 == y_9.
     771              : 
     772              : void
     773     37949690 : path_range_query::compute_phi_relations (basic_block bb, basic_block prev)
     774              : {
     775     37949690 :   if (prev == NULL)
     776              :     return;
     777              : 
     778     37949690 :   edge e_in = find_edge (prev, bb);
     779              : 
     780     83428982 :   for (gphi_iterator iter = gsi_start_phis (bb); !gsi_end_p (iter);
     781     45479292 :        gsi_next (&iter))
     782              :     {
     783     45479292 :       gphi *phi = iter.phi ();
     784     45479292 :       tree result = gimple_phi_result (phi);
     785     45479292 :       unsigned nargs = gimple_phi_num_args (phi);
     786              : 
     787     45479292 :       if (!exit_dependency_p (result))
     788     35873663 :         continue;
     789              : 
     790     17247741 :       for (size_t i = 0; i < nargs; ++i)
     791     17247741 :         if (e_in == gimple_phi_arg_edge (phi, i))
     792              :           {
     793      9605629 :             maybe_register_phi_relation (phi, e_in);
     794      9605629 :             break;
     795              :           }
     796              :     }
     797              : }
     798              : 
     799              : // Compute outgoing relations from BB to NEXT.
     800              : 
     801              : void
     802     37949690 : path_range_query::compute_outgoing_relations (basic_block bb, basic_block next)
     803              : {
     804     75899380 :   if (gcond *cond = safe_dyn_cast <gcond *> (*gsi_last_bb (bb)))
     805              :     {
     806     23967843 :       int_range<2> r;
     807     23967843 :       edge e0 = EDGE_SUCC (bb, 0);
     808     23967843 :       edge e1 = EDGE_SUCC (bb, 1);
     809              : 
     810     23967843 :       if (e0->dest == next)
     811     10276498 :         gcond_edge_range (r, e0);
     812     13691345 :       else if (e1->dest == next)
     813     13691345 :         gcond_edge_range (r, e1);
     814              :       else
     815            0 :         gcc_unreachable ();
     816              : 
     817     23967843 :       jt_fur_source src (NULL, this, m_path);
     818     23967843 :       src.register_outgoing_edges (cond, r, e0, e1);
     819     23967843 :     }
     820     37949690 : }
        

Generated by: LCOV version 2.5.0-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.