gcc/analyzer/region-model-reachability.cc

   1 /* Finding reachable regions and values.
   2    Copyright (C) 2020 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 "config.h"
  22 #include "system.h"
  23 #include "coretypes.h"
  24 #include "tree.h"
  25 #include "function.h"
  26 #include "basic-block.h"
  27 #include "gimple.h"
  28 #include "gimple-iterator.h"
  29 #include "diagnostic-core.h"
  30 #include "graphviz.h"
  31 #include "options.h"
  32 #include "cgraph.h"
  33 #include "tree-dfa.h"
  34 #include "stringpool.h"
  35 #include "convert.h"
  36 #include "target.h"
  37 #include "fold-const.h"
  38 #include "tree-pretty-print.h"
  39 #include "tristate.h"
  40 #include "bitmap.h"
  41 #include "selftest.h"
  42 #include "function.h"
  43 #include "analyzer/analyzer.h"
  44 #include "analyzer/analyzer-logging.h"
  45 #include "ordered-hash-map.h"
  46 #include "options.h"
  47 #include "cgraph.h"
  48 #include "cfg.h"
  49 #include "digraph.h"
  50 #include "json.h"
  51 #include "analyzer/call-string.h"
  52 #include "analyzer/program-point.h"
  53 #include "analyzer/store.h"
  54 #include "analyzer/region-model.h"
  55 #include "analyzer/region-model-reachability.h"
  56
  57 #if ENABLE_ANALYZER
  58
  59 namespace ana {
  60
  61 reachable_regions::reachable_regions (region_model *model,
  62                                       region_model_manager *mgr)
  63 : m_model (model), m_store (model->get_store ()), m_mgr (mgr),
  64   m_reachable_base_regs (), m_mutable_base_regs ()
  65 {
  66 }
  67
  68 /* Callback called for each cluster when initializing this object.  */
  69
  70 void
  71 reachable_regions::init_cluster_cb (const region *base_reg,
  72                                     reachable_regions *this_ptr)
  73 {
  74   this_ptr->init_cluster (base_reg);
  75 }
  76
  77 /* Called for each cluster when initializing this object.  */
  78 void
  79 reachable_regions::init_cluster (const region *base_reg)
  80 {
  81   /* Mark any globals as mutable (and traverse what they point to).  */
  82   const region *parent = base_reg->get_parent_region ();
  83   gcc_assert (parent);
  84   if (parent->get_kind () == RK_GLOBALS)
  85     add (base_reg, true);
  86
  87   /* Mark any clusters that already escaped in previous unknown calls
  88      as mutable (and traverse what they currently point to).  */
  89   if (m_store->escaped_p (base_reg))
  90     add (base_reg, true);
  91
  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   if (const symbolic_region *sym_reg = base_reg->dyn_cast_symbolic_region ())
  95     {
  96       const svalue *ptr = sym_reg->get_pointer ();
  97       if (const initial_svalue *init_sval = ptr->dyn_cast_initial_svalue ())
  98         {
  99           const region *init_sval_reg = init_sval->get_region ();
 100           const region *other_base_reg = init_sval_reg->get_base_region ();
 101           const binding_cluster *other_cluster
 102             = m_store->get_cluster (other_base_reg);
 103           if (other_cluster == NULL
 104               || !other_cluster->touched_p ())
 105             add (base_reg, true);
 106         }
 107     }
 108 }
 109
 110   /* Lazily mark the cluster containing REG as being reachable, recursively
 111      adding clusters reachable from REG's cluster.  */
 112 void
 113 reachable_regions::add (const region *reg, bool is_mutable)
 114 {
 115   gcc_assert (reg);
 116
 117   const region *base_reg = const_cast <region *> (reg->get_base_region ());
 118   gcc_assert (base_reg);
 119
 120   /* Bail out if this cluster is already in the sets at the IS_MUTABLE
 121      level of mutability.  */
 122   if (!is_mutable && m_reachable_base_regs.contains (base_reg))
 123     return;
 124   m_reachable_base_regs.add (base_reg);
 125
 126   if (is_mutable)
 127     {
 128       if (m_mutable_base_regs.contains (base_reg))
 129         return;
 130       else
 131         m_mutable_base_regs.add (base_reg);
 132     }
 133
 134   /* Add values within the cluster.  If any are pointers, add the pointee.  */
 135   if (binding_cluster *bind_cluster = m_store->get_cluster (base_reg))
 136     bind_cluster->for_each_value (handle_sval_cb, this);
 137   else
 138     handle_sval (m_model->get_store_value (reg));
 139 }
 140
 141 void
 142 reachable_regions::handle_sval_cb (const svalue *sval,
 143                                    reachable_regions *this_ptr)
 144 {
 145   this_ptr->handle_sval (sval);
 146 }
 147
 148 /* Add SVAL.  If it is a pointer, add the pointed-to region.  */
 149
 150 void
 151 reachable_regions::handle_sval (const svalue *sval)
 152 {
 153   m_reachable_svals.add (sval);
 154   if (const region_svalue *ptr = sval->dyn_cast_region_svalue ())
 155     {
 156       const region *pointee = ptr->get_pointee ();
 157       /* Use const-ness of pointer type to affect mutability.  */
 158       bool ptr_is_mutable = true;
 159       if (ptr->get_type ()
 160           && TREE_CODE (ptr->get_type ()) == POINTER_TYPE
 161           && TYPE_READONLY (TREE_TYPE (ptr->get_type ())))
 162         {
 163           ptr_is_mutable = false;
 164         }
 165       else
 166         {
 167           m_mutable_svals.add (sval);
 168         }
 169       add (pointee, ptr_is_mutable);
 170     }
 171   /* Treat all svalues within a compound_svalue as reachable.  */
 172   if (const compound_svalue *compound_sval
 173       = sval->dyn_cast_compound_svalue ())
 174     {
 175       for (compound_svalue::iterator_t iter = compound_sval->begin ();
 176            iter != compound_sval->end (); ++iter)
 177         {
 178           const svalue *iter_sval = (*iter).second;
 179           handle_sval (iter_sval);
 180         }
 181     }
 182   if (const svalue *cast = sval->maybe_undo_cast ())
 183     handle_sval (cast);
 184 }
 185
 186 /* Add SVAL.  If it is a pointer, add the pointed-to region.
 187    Use PARAM_TYPE for determining mutability.  */
 188
 189 void
 190 reachable_regions::handle_parm (const svalue *sval, tree param_type)
 191 {
 192   bool is_mutable = true;
 193   if (param_type
 194       && TREE_CODE (param_type) == POINTER_TYPE
 195       &&  TYPE_READONLY (TREE_TYPE (param_type)))
 196     is_mutable = false;
 197   if (is_mutable)
 198     m_mutable_svals.add (sval);
 199   else
 200     m_reachable_svals.add (sval);
 201   if (const region_svalue *parm_ptr
 202       = sval->dyn_cast_region_svalue ())
 203     {
 204       const region *pointee_reg = parm_ptr->get_pointee ();
 205       add (pointee_reg, is_mutable);
 206     }
 207 }
 208
 209 /* Update the store to mark the clusters that were found to be mutable
 210    as having escaped.
 211    Notify CTXT about escaping function_decls.  */
 212
 213 void
 214 reachable_regions::mark_escaped_clusters (region_model_context *ctxt)
 215 {
 216   gcc_assert (ctxt);
 217   for (hash_set<const region *>::iterator iter = m_mutable_base_regs.begin ();
 218        iter != m_mutable_base_regs.end (); ++iter)
 219     {
 220       const region *base_reg = *iter;
 221       m_store->mark_as_escaped (base_reg);
 222
 223       /* If we have a function that's escaped, potentially add
 224          it to the worklist.  */
 225       if (const function_region *fn_reg = base_reg->dyn_cast_function_region ())
 226         ctxt->on_escaped_function (fn_reg->get_fndecl ());
 227     }
 228 }
 229
 230 /* Dump SET to PP, sorting it to avoid churn when comparing dumps.  */
 231
 232 template <typename T>
 233 static void
 234 dump_set (const hash_set<const T *> &set, pretty_printer *pp)
 235 {
 236   auto_vec<const T *> elements (set.elements ());
 237   for (typename hash_set<const T *>::iterator iter = set.begin ();
 238        iter != set.end (); ++iter)
 239     elements.quick_push (*iter);
 240
 241   elements.qsort (T::cmp_ptr_ptr);
 242
 243   unsigned i;
 244   const T *element;
 245   FOR_EACH_VEC_ELT (elements, i, element)
 246     {
 247       pp_string (pp, "  ");
 248       element->dump_to_pp (pp, true);
 249       pp_newline (pp);
 250     }
 251 }
 252
 253 /* Dump a multiline representation of this object to PP.  */
 254
 255 void
 256 reachable_regions::dump_to_pp (pretty_printer *pp) const
 257 {
 258   pp_string (pp, "reachable clusters: ");
 259   pp_newline (pp);
 260   dump_set (m_reachable_base_regs, pp);
 261
 262   pp_string (pp, "mutable clusters: ");
 263   pp_newline (pp);
 264   dump_set (m_mutable_base_regs, pp);
 265
 266   pp_string (pp, "reachable svals: ");
 267   pp_newline (pp);
 268   dump_set (m_reachable_svals, pp);
 269
 270   pp_string (pp, "mutable svals: ");
 271   pp_newline (pp);
 272   dump_set (m_mutable_svals, pp);
 273 }
 274
 275 /* Dump a multiline representation of this object to stderr.  */
 276
 277 DEBUG_FUNCTION void
 278 reachable_regions::dump () const
 279 {
 280   pretty_printer pp;
 281   pp_format_decoder (&pp) = default_tree_printer;
 282   pp_show_color (&pp) = pp_show_color (global_dc->printer);
 283   pp.buffer->stream = stderr;
 284   dump_to_pp (&pp);
 285   pp_flush (&pp);
 286 }
 287
 288 } // namespace ana
 289
 290 #endif /* #if ENABLE_ANALYZER */