[gcc r12-1480] analyzer: add class region_to_value_map

[gcc r12-1480] analyzer: add class region_to_value_map

[David Malcolm]

https://gcc.gnu.org/g:d726a57b993e00294891e2a05d5868c89bb75b76

commit r12-1480-gd726a57b993e00294891e2a05d5868c89bb75b76
Author: David Malcolm <dmalcolm@redhat.com>
Date:   Tue Jun 15 09:30:18 2021 -0400

    analyzer: add class region_to_value_map
    
    Add a class for associating symbolic values with regions, for use
    initially for recording the sizes of dynamically-allocated regions,
    though this also could potentially be used for e.g. tracking strlen()
    values.
    
    gcc/analyzer/ChangeLog:
            * region-model.cc (region_to_value_map::operator=): New.
            (region_to_value_map::operator==): New.
            (region_to_value_map::dump_to_pp): New.
            (region_to_value_map::dump): New.
            (region_to_value_map::can_merge_with_p): New.
            * region-model.h (class region_to_value_map): New class.
    
    Signed-off-by: David Malcolm <dmalcolm@redhat.com>

Diff:
---
 gcc/analyzer/region-model.cc | 110 +++++++++++++++++++++++++++++++++++++++++++
 gcc/analyzer/region-model.h  |  45 ++++++++++++++++++
 2 files changed, 155 insertions(+)

diff --git a/gcc/analyzer/region-model.cc b/gcc/analyzer/region-model.cc
index 4b9620d9887..43f991a2a29 100644
--- a/gcc/analyzer/region-model.cc
+++ b/gcc/analyzer/region-model.cc
@@ -110,6 +110,116 @@ print_quoted_type (pretty_printer *pp, tree t)
   pp_end_quote (pp, pp_show_color (pp));
 }
 
+/* class region_to_value_map.  */
+
+/* Assignment operator for region_to_value_map.  */
+
+region_to_value_map &
+region_to_value_map::operator= (const region_to_value_map &other)
+{
+  m_hash_map.empty ();
+  for (auto iter : other.m_hash_map)
+    {
+      const region *reg = iter.first;
+      const svalue *sval = iter.second;
+      m_hash_map.put (reg, sval);
+    }
+  return *this;
+}
+
+/* Equality operator for region_to_value_map.  */
+
+bool
+region_to_value_map::operator== (const region_to_value_map &other) const
+{
+  if (m_hash_map.elements () != other.m_hash_map.elements ())
+    return false;
+
+  for (auto iter : *this)
+    {
+      const region *reg = iter.first;
+      const svalue *sval = iter.second;
+      const svalue * const *other_slot = other.get (reg);
+      if (other_slot == NULL)
+	return false;
+      if (sval != *other_slot)
+	return false;
+    }
+
+  return true;
+}
+
+/* Dump this object to PP.  */
+
+void
+region_to_value_map::dump_to_pp (pretty_printer *pp, bool simple,
+				 bool multiline) const
+{
+  auto_vec<const region *> regs;
+  for (iterator iter = begin (); iter != end (); ++iter)
+    regs.safe_push ((*iter).first);
+  regs.qsort (region::cmp_ptr_ptr);
+  if (multiline)
+    pp_newline (pp);
+  else
+    pp_string (pp, " {");
+  unsigned i;
+  const region *reg;
+  FOR_EACH_VEC_ELT (regs, i, reg)
+    {
+      if (multiline)
+	pp_string (pp, "  ");
+      else if (i > 0)
+	pp_string (pp, ", ");
+      reg->dump_to_pp (pp, simple);
+      pp_string (pp, ": ");
+      const svalue *sval = *get (reg);
+      sval->dump_to_pp (pp, true);
+      if (multiline)
+	pp_newline (pp);
+    }
+  if (!multiline)
+    pp_string (pp, "}");
+}
+
+/* Dump this object to stderr.  */
+
+DEBUG_FUNCTION void
+region_to_value_map::dump (bool simple) const
+{
+  pretty_printer pp;
+  pp_format_decoder (&pp) = default_tree_printer;
+  pp_show_color (&pp) = pp_show_color (global_dc->printer);
+  pp.buffer->stream = stderr;
+  dump_to_pp (&pp, simple, true);
+  pp_newline (&pp);
+  pp_flush (&pp);
+}
+
+
+/* Attempt to merge THIS with OTHER, writing the result
+   to OUT.
+
+   For now, write (region, value) mappings that are in common between THIS
+   and OTHER to OUT, effectively taking the intersection, rather than
+   rejecting differences.  */
+
+bool
+region_to_value_map::can_merge_with_p (const region_to_value_map &other,
+				       region_to_value_map *out) const
+{
+  for (auto iter : *this)
+    {
+      const region *iter_reg = iter.first;
+      const svalue *iter_sval = iter.second;
+      const svalue * const * other_slot = other.get (iter_reg);
+      if (other_slot)
+	if (iter_sval == *other_slot)
+	  out->put (iter_reg, iter_sval);
+    }
+  return true;
+}
+
 /* class region_model.  */
 
 /* Ctor for region_model: construct an "empty" model.  */
diff --git a/gcc/analyzer/region-model.h b/gcc/analyzer/region-model.h
index e251a5b245c..0afcb8635a9 100644
--- a/gcc/analyzer/region-model.h
+++ b/gcc/analyzer/region-model.h
@@ -128,6 +128,51 @@ one_way_id_map<T>::update (T *id) const
   *id = get_dst_for_src (*id);
 }
 
+/* A mapping from region to svalue for use when tracking state.  */
+
+class region_to_value_map
+{
+public:
+  typedef hash_map<const region *, const svalue *> hash_map_t;
+  typedef hash_map_t::iterator iterator;
+
+  region_to_value_map () : m_hash_map () {}
+  region_to_value_map (const region_to_value_map &other)
+  : m_hash_map (other.m_hash_map) {}
+  region_to_value_map &operator= (const region_to_value_map &other);
+
+  bool operator== (const region_to_value_map &other) const;
+  bool operator!= (const region_to_value_map &other) const
+  {
+    return !(*this == other);
+  }
+
+  iterator begin () const { return m_hash_map.begin (); }
+  iterator end () const { return m_hash_map.end (); }
+
+  const svalue * const *get (const region *reg) const
+  {
+    return const_cast <hash_map_t &> (m_hash_map).get (reg);
+  }
+  void put (const region *reg, const svalue *sval)
+  {
+    m_hash_map.put (reg, sval);
+  }
+  void remove (const region *reg)
+  {
+    m_hash_map.remove (reg);
+  }
+
+  void dump_to_pp (pretty_printer *pp, bool simple, bool multiline) const;
+  void dump (bool simple) const;
+
+  bool can_merge_with_p (const region_to_value_map &other,
+			 region_to_value_map *out) const;
+
+private:
+  hash_map_t m_hash_map;
+};
+
 /* Various operations delete information from a region_model.
 
    This struct tracks how many of each kind of entity were purged (e.g.