LCOV - code coverage report
Current view: top level - gcc/analyzer - region-model-reachability.cc (source / functions) Coverage Total Hit
Test: gcc.info Lines: 78.2 % 165 129
Test Date: 2026-11-14 16:39:50 Functions: 69.2 % 13 9
Legend: Lines:     hit not hit

            Line data    Source code
       1              : /* Finding reachable regions and values.
       2              :    Copyright (C) 2020-2026 Free Software Foundation, Inc.
       3              :    Contributed by David Malcolm <dmalcolm@redhat.com>.
       4              : 
       5              : This file is part of GCC.
       6              : 
       7              : GCC is free software; you can redistribute it and/or modify it
       8              : under the terms of the GNU General Public License as published by
       9              : the Free Software Foundation; either version 3, or (at your option)
      10              : any later version.
      11              : 
      12              : GCC is distributed in the hope that it will be useful, but
      13              : WITHOUT ANY WARRANTY; without even the implied warranty of
      14              : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
      15              : General Public License 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 "analyzer/common.h"
      22              : 
      23              : #include "ordered-hash-map.h"
      24              : #include "diagnostic.h"
      25              : #include "tree-diagnostic.h"
      26              : 
      27              : #include "analyzer/analyzer-logging.h"
      28              : #include "analyzer/call-string.h"
      29              : #include "analyzer/program-point.h"
      30              : #include "analyzer/store.h"
      31              : #include "analyzer/region-model.h"
      32              : #include "analyzer/region-model-reachability.h"
      33              : #include "analyzer/liveness-context.h"
      34              : 
      35              : #if ENABLE_ANALYZER
      36              : 
      37              : namespace ana {
      38              : 
      39              : static bool
      40     99352736 : recurse_into_children_p (const symbolic::value_node &val)
      41              : {
      42              :   /* Don't recurse into children for cropped bit vectors:
      43              :      the values aren't complete, so aren't live.  */
      44     99352736 :   if (auto *bv = val.dyn_cast_bit_vector ())
      45     23123418 :     if (bv->get_kind () == symbolic::bit_vector::kind::cropped)
      46        52399 :       return false;
      47              :   return true;
      48              : }
      49              : 
      50       904435 : reachable_regions::reachable_regions (region_model *model)
      51       904435 : : m_model (model), m_store (model->get_store ()),
      52       904435 :   m_reachable_base_regs (), m_mutable_base_regs ()
      53              : {
      54       904435 : }
      55              : 
      56              : /* Callback called for each cluster when initializing this object.  */
      57              : 
      58              : void
      59      5189414 : reachable_regions::init_cluster_cb (const region *base_reg,
      60              :                                     reachable_regions *this_ptr)
      61              : {
      62      5189414 :   this_ptr->init_cluster (base_reg);
      63      5189414 : }
      64              : 
      65              : /* Called for each cluster when initializing this object.  */
      66              : void
      67      5189414 : reachable_regions::init_cluster (const region *base_reg)
      68              : {
      69              :   /* Mark any globals as mutable (and traverse what they point to).  */
      70      5189414 :   const region *parent = base_reg->get_parent_region ();
      71      5189414 :   gcc_assert (parent);
      72      5189414 :   if (parent->get_kind () == RK_GLOBALS)
      73       408091 :     add (base_reg, true);
      74              : 
      75              :   /* Mark any clusters that already escaped in previous unknown calls
      76              :      as mutable (and traverse what they currently point to).  */
      77      5189414 :   if (m_store->escaped_p (base_reg))
      78      1207928 :     add (base_reg, true);
      79              : 
      80      5189414 :   if (const symbolic_region *sym_reg = base_reg->dyn_cast_symbolic_region ())
      81              :     {
      82      1098350 :       const svalue *ptr = sym_reg->get_pointer ();
      83      1098350 :       symbolic::liveness_context liveness_ctxt (value_set (), *m_model);
      84      1098350 :       if (ptr->implicitly_live_p (liveness_ctxt))
      85       902073 :         add (base_reg, true);
      86      1098350 :       switch (ptr->get_kind ())
      87              :         {
      88              :         default:
      89              :           break;
      90       893646 :         case SK_INITIAL:
      91       893646 :           {
      92              :             /* If BASE_REG is *INIT_VAL(REG) for some other REG, see if REG is
      93              :                unbound and untouched.  If so, then add BASE_REG as a root.  */
      94       893646 :             const initial_svalue *init_sval
      95       893646 :               = as_a <const initial_svalue *> (ptr);
      96       893646 :             const region *init_sval_reg = init_sval->get_region ();
      97       893646 :             const region *other_base_reg = init_sval_reg->get_base_region ();
      98       893646 :             const binding_cluster *other_cluster
      99       893646 :               = m_store->get_cluster (other_base_reg);
     100       893646 :             if (other_cluster == nullptr
     101       893646 :                 || !other_cluster->touched_p ())
     102       877222 :               add (base_reg, true);
     103              :           }
     104              :           break;
     105              : 
     106            0 :         case SK_UNKNOWN:
     107            0 :           {
     108              :             /* If this cluster is due to dereferencing an unknown pointer,
     109              :                any values written through the pointer could still
     110              :                be live.  */
     111            0 :             add (base_reg, true);
     112              :           }
     113            0 :           break;
     114              :         }
     115      1098350 :     }
     116      5189414 : }
     117              : 
     118              :   /* Lazily mark the cluster containing REG as being reachable, recursively
     119              :      adding clusters reachable from REG's cluster.  */
     120              : void
     121      8975548 : reachable_regions::add (const region *reg, bool is_mutable)
     122              : {
     123      8975548 :   gcc_assert (reg);
     124              : 
     125      8975548 :   const region *base_reg = const_cast <region *> (reg->get_base_region ());
     126      8975548 :   gcc_assert (base_reg);
     127              : 
     128              :   /* Bail out if this cluster is already in the sets at the IS_MUTABLE
     129              :      level of mutability.  */
     130      8975548 :   if (!is_mutable && m_reachable_base_regs.contains (base_reg))
     131      3715133 :     return;
     132      8851942 :   m_reachable_base_regs.add (base_reg);
     133              : 
     134      8851942 :   if (is_mutable)
     135              :     {
     136      5723659 :       if (m_mutable_base_regs.contains (base_reg))
     137              :         return;
     138              :       else
     139      2132132 :         m_mutable_base_regs.add (base_reg);
     140              :     }
     141              : 
     142              :   /* Add values within the cluster.  If any are pointers, add the pointee.  */
     143      5260415 :   if (binding_cluster *bind_cluster = m_store->get_cluster (base_reg))
     144              :     {
     145      4999099 :       bind_cluster->for_each_value
     146      4999099 :         ([] (const symbolic::value_node &val,
     147              :              void *user_data) -> iter_result
     148              :          {
     149              :            ((reachable_regions *)user_data)->handle_value (val);
     150              :            return iter_result::keep_going;
     151              :          },
     152              :          this);
     153              :     }
     154              : }
     155              : 
     156              : void
     157            0 : reachable_regions::handle_sval_cb (const svalue *sval,
     158              :                                    reachable_regions *this_ptr)
     159              : {
     160            0 :   this_ptr->handle_value (*sval);
     161            0 : }
     162              : 
     163              : /* Add VAL.  If it is a pointer, add the pointed-to region.  */
     164              : 
     165              : void
     166     23502881 : reachable_regions::handle_value (const symbolic::value_node &val)
     167              : {
     168    122855617 :   auto cb = [] (const symbolic::value_node &val, void *user_data) -> bool
     169              :   {
     170     99352736 :     reachable_regions *rr = (reachable_regions *)user_data;
     171     99352736 :     if (!rr->m_reachable_svals.contains (&val))
     172              :       {
     173      9353598 :         rr->m_reachable_svals.insert (&val);
     174      9353598 :         rr->handle_value (val);
     175              :       }
     176              : 
     177     99352736 :     return recurse_into_children_p (val);
     178              :   };
     179              : 
     180     23502881 :   symbolic::value_node_visitor v {cb, this};
     181     23502881 :   val.accept_node_visitor (v);
     182              : 
     183     23502881 :   m_mutable_svals.insert (&val);
     184              : 
     185     23502881 :   if (auto sval = val.dyn_cast_svalue ())
     186              :     {
     187     13522980 :       if (auto *bit_vec_sval = sval->dyn_cast_svalue_from_bit_vector ())
     188      1334600 :         handle_value (bit_vec_sval->get_bit_vector ());
     189              : 
     190     13522980 :       if (auto *ptr = sval->maybe_get_symbolic_pointer ())
     191              :         {
     192              :           /* Use const-ness of pointer type to affect mutability.  */
     193      2344128 :           bool ptr_is_mutable = true;
     194      2344128 :           if (sval->get_type ()
     195      2344128 :               && TREE_CODE (sval->get_type ()) == POINTER_TYPE
     196      4684838 :               && TYPE_READONLY (TREE_TYPE (sval->get_type ())))
     197              :             {
     198              :               ptr_is_mutable = false;
     199              :             }
     200              :           else
     201              :             {
     202      2321528 :               m_mutable_svals.insert (sval);
     203              :             }
     204      2344128 :           add (&ptr->get_base_region (), ptr_is_mutable);
     205              :         }
     206     13522980 :       if (const svalue *cast = sval->maybe_undo_cast ())
     207      2095073 :         handle_value (*cast);
     208              : 
     209              :       /* If SVAL is the result of a reversible operation, then the operands
     210              :          are reachable.  */
     211     13522980 :       switch (sval->get_kind ())
     212              :         {
     213              :         default:
     214              :           break;
     215      2161680 :         case SK_UNARYOP:
     216      2161680 :           {
     217      2161680 :             const unaryop_svalue *unaryop_sval = (const unaryop_svalue *)sval;
     218      2161680 :             switch (unaryop_sval->get_op ())
     219              :               {
     220              :               default:
     221              :                 break;
     222        56868 :               case NEGATE_EXPR:
     223        56868 :                 handle_value (*unaryop_sval->get_arg ());
     224        56868 :                 break;
     225              :               }
     226              :           }
     227              :           break;
     228      3287237 :         case SK_BINOP:
     229      3287237 :           {
     230      3287237 :             const binop_svalue *binop_sval = (const binop_svalue *)sval;
     231      3287237 :             switch (binop_sval->get_op ())
     232              :               {
     233              :               default:
     234              :                 break;
     235       264880 :               case POINTER_PLUS_EXPR:
     236       264880 :                 handle_value (*binop_sval->get_arg0 ());
     237       264880 :                 handle_value (*binop_sval->get_arg1 ());
     238       264880 :                 break;
     239              :               }
     240              :           }
     241              :         }
     242              :     }
     243              : 
     244     23502881 :   if (auto *bv = val.dyn_cast_bit_vector ())
     245      9979901 :     if (auto *from_svalue = bv->dyn_cast_bit_vector_from_svalue ())
     246      4917453 :       handle_value (from_svalue->get_svalue ());
     247     23502881 : }
     248              : 
     249              : /* Add SVAL.  If it is a pointer, add the pointed-to region.
     250              :    Use PARAM_TYPE for determining mutability.  */
     251              : 
     252              : void
     253        19424 : reachable_regions::handle_parm (const svalue *sval, tree param_type)
     254              : {
     255        19424 :   bool is_mutable = true;
     256        19424 :   if (param_type
     257        17932 :       && TREE_CODE (param_type) == POINTER_TYPE
     258        31853 :       &&  TYPE_READONLY (TREE_TYPE (param_type)))
     259         3125 :     is_mutable = false;
     260        19424 :   if (is_mutable)
     261        16299 :     m_mutable_svals.insert (sval);
     262              :   else
     263         3125 :     m_reachable_svals.insert (sval);
     264        19424 :   if (const region *base_reg = sval->maybe_get_deref_base_region ())
     265         8467 :     add (base_reg, is_mutable);
     266        19424 :   if (auto *sval_from_bv = sval->dyn_cast_svalue_from_bit_vector ())
     267              :     {
     268         2088 :       auto &bv = sval_from_bv->get_bit_vector ();
     269         2088 :       if (auto *concat_bv = bv.dyn_cast_concat_bit_vector ())
     270          233 :         for (auto child_bv : *concat_bv)
     271          202 :           if (auto *bv_from_sval = child_bv->dyn_cast_bit_vector_from_svalue ())
     272          186 :             handle_value (bv_from_sval->get_svalue ());
     273              :     }
     274        19424 :   if (const svalue *cast = sval->maybe_undo_cast ())
     275          313 :     handle_value (*cast);
     276        19424 : }
     277              : 
     278              : /* Update the store to mark the clusters that were found to be mutable
     279              :    as having escaped.
     280              :    Notify CTXT about escaping function_decls.  */
     281              : 
     282              : void
     283        17547 : reachable_regions::mark_escaped_clusters (region_model_context *ctxt)
     284              : {
     285        17547 :   auto_vec<const function_region *> escaped_fn_regs
     286        17547 :     (m_mutable_base_regs.elements ());
     287        41144 :   for (hash_set<const region *>::iterator iter = m_mutable_base_regs.begin ();
     288        41144 :        iter != m_mutable_base_regs.end (); ++iter)
     289              :     {
     290        23597 :       const region *base_reg = *iter;
     291        23597 :       m_store->mark_as_escaped (base_reg,
     292        23597 :                                 m_model->get_baseline_state ());
     293              : 
     294              :       /* If we have a function that's escaped, potentially add
     295              :          it to the worklist.  */
     296        23597 :       if (const function_region *fn_reg = base_reg->dyn_cast_function_region ())
     297          615 :         escaped_fn_regs.quick_push (fn_reg);
     298              :     }
     299        17547 :   if (ctxt)
     300              :     {
     301              :       /* Sort to ensure deterministic results.  */
     302        12166 :       escaped_fn_regs.qsort (region::cmp_ptr_ptr);
     303        12166 :       unsigned i;
     304        12166 :       const function_region *fn_reg;
     305        27764 :       FOR_EACH_VEC_ELT (escaped_fn_regs, i, fn_reg)
     306          309 :         ctxt->on_escaped_function (fn_reg->get_fndecl ());
     307              :     }
     308        17547 : }
     309              : 
     310              : /* Dump SET to PP, sorting it to avoid churn when comparing dumps.  */
     311              : 
     312              : template <typename T>
     313              : static void
     314            0 : dump_set (const hash_set<const T *> &set, pretty_printer *pp)
     315              : {
     316            0 :   auto_vec<const T *> elements (set.elements ());
     317            0 :   for (typename hash_set<const T *>::iterator iter = set.begin ();
     318            0 :        iter != set.end (); ++iter)
     319            0 :     elements.quick_push (*iter);
     320              : 
     321            0 :   elements.qsort (T::cmp_ptr_ptr);
     322              : 
     323              :   unsigned i;
     324              :   const T *element;
     325            0 :   FOR_EACH_VEC_ELT (elements, i, element)
     326              :     {
     327            0 :       pp_string (pp, "  ");
     328            0 :       element->dump_to_pp (pp, true);
     329            0 :       pp_newline (pp);
     330              :     }
     331            0 : }
     332              : 
     333              : /* Dump a multiline representation of this object to PP.  */
     334              : 
     335              : void
     336            0 : reachable_regions::dump_to_pp (pretty_printer *pp) const
     337              : {
     338            0 :   pp_string (pp, "reachable clusters: ");
     339            0 :   pp_newline (pp);
     340            0 :   dump_set (m_reachable_base_regs, pp);
     341              : 
     342            0 :   pp_string (pp, "mutable clusters: ");
     343            0 :   pp_newline (pp);
     344            0 :   dump_set (m_mutable_base_regs, pp);
     345              : 
     346            0 :   pp_string (pp, "reachable svals: ");
     347            0 :   pp_newline (pp);
     348            0 :   m_reachable_svals.dump_to_pp (pp);
     349              : 
     350            0 :   pp_string (pp, "mutable svals: ");
     351            0 :   pp_newline (pp);
     352            0 :   m_mutable_svals.dump_to_pp (pp);
     353            0 : }
     354              : 
     355              : /* Dump a multiline representation of this object to stderr.  */
     356              : 
     357              : DEBUG_FUNCTION void
     358            0 : reachable_regions::dump () const
     359              : {
     360            0 :   tree_dump_pretty_printer pp (stderr);
     361            0 :   dump_to_pp (&pp);
     362            0 : }
     363              : 
     364              : } // namespace ana
     365              : 
     366              : #endif /* #if ENABLE_ANALYZER */
        

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.