[gcc r17-182] analyzer: use concrete_binding_map for compound_svalue (PR analyzer/123145)
David Malcolm
dmalcolm@gcc.gnu.org
Tue Apr 28 23:14:02 GMT 2026
https://gcc.gnu.org/g:3a8301ae70cb7a3935eb786ff7f20463bf5a71ab
commit r17-182-g3a8301ae70cb7a3935eb786ff7f20463bf5a71ab
Author: David Malcolm <dmalcolm@redhat.com>
Date: Thu Jan 15 14:17:08 2026 -0500
analyzer: use concrete_binding_map for compound_svalue (PR analyzer/123145)
A compound_svalue can only have concrete bindings. Capture this in the
type system by splitting out the concrete parts of class binding_map
into a new class concrete_binding_map, and use the latter for
compound_svalue. This also allows some simplifications and
optimizations, where we can use bit_range rather than binding keys.
No functional change intended.
gcc/analyzer/ChangeLog:
PR analyzer/123145
* access-diagram.cc
(compound_svalue_spatial_item::compound_svalue_spatial_item):
Update for compound_svalue using concrete_binding_map rather than
binding_map.
* bounds-checking.cc (strip_types): Likewise.
* call-summary.cc
(call_summary_replay::convert_svalue_from_summary_1): Update for
reimplementation of class binding_map.
(call_summary_replay::convert_svalue_from_summary_1): Likewise.
* infinite-recursion.cc (contains_unknown_p): Update for
compound_svalue using concrete_binding_map rather than
binding_map.
* program-state.cc (sm_state_map::impl_set_state): Likewise.
* region-model-manager.cc (maybe_undo_optimize_bit_field_compare):
Likewise.
(maybe_undo_optimize_bit_field_compare): Avoid building a
concrete_binding key by using get_any_exact_binding.
(region_model_manager::get_or_create_compound_svalue): New
overload, consuming a concrete_binding_map &&.
* region-model-manager.h
(region_model_manager::get_or_create_compound_svalue): New decl
for the above.
* region-model-reachability.cc (reachable_regions::handle_sval):
Update for compound_svalue using concrete_binding_map rather than
binding_map.
(reachable_regions::handle_parm): Likewise.
* region-model.cc (region_model::scan_for_null_terminator_1): Port
from binding_map to concrete_binding_map.
(exposure_through_uninit_copy::calc_num_uninit_bits): Update for
compound_svalue using concrete_binding_map rather than
binding_map.
(contains_uninit_p): Likewise.
* region.cc (decl_region::calc_svalue_for_constructor): Port from
binding_map to concrete_binding_map.
(decl_region::get_svalue_for_initializer): Update call to
get_or_create_compound_svalue.
* store.cc (concrete_binding_map::dump_to_pp): New.
(concrete_binding_map::dump): New.
(concrete_binding_map::add_to_tree_widget): New.
(concrete_binding_map::validate): New.
(binding_map::cmp): Convert to...
(concrete_binding_map::cmp): ...this.
(concrete_binding_map::get_any_exact_binding): New.
(concrete_binding_map::calc_complexity): New.
(concrete_binding_map::remove_overlapping_binding): New.
(concrete_binding_map::remove_overlapping_bindings): New.
(concrete_binding_map::get_overlapping_bindings): New.
(binding_map::put): Update for change to m_concrete.
(binding_map::validate): Likewise.
(binding_map::apply_ctor_to_region): Convert to...
(concrete_binding_map::apply_ctor_to_region): ...this.
(binding_map::apply_ctor_val_to_range): Convert to...
(concrete_binding_map::apply_ctor_val_to_range): ...this.
(binding_map::apply_ctor_pair_to_child_region): Convert to...
(concrete_binding_map::apply_ctor_pair_to_child_region): ...this.
(binding_map::remove_overlapping_bindings): Move part of
implementation to
concrete_binding_map::remove_overlapping_binding.
(binding_cluster::bind_compound_sval): Simplify using
concrete_binding_map.
(binding_cluster::maybe_get_compound_binding): Likewise.
(store::replay_call_summary_cluster): Update for change
to compound_svalue.
* store.h: Include "analyzer/complexity.h".
(class concrete_binding_map): New, based on
binding_map::concrete_bindings_t.
(binding_map::concrete_bindings_t): Use concrete_binding_map.
(binding_map::empty_p): Update for above.
(binding_map::apply_ctor_to_region): Drop decl.
(binding_map::cmp): Likewise.
(binding_map::apply_ctor_val_to_range): Likewise.
(binding_map::apply_ctor_pair_to_child_region): Likewise.
* svalue.cc (svalue::cmp_ptr): Update for change to
compound_svalue.
(compound_svalue::compound_svalue): Port from binding_map to
concrete_binding_map.
(compound_svalue::accept): Likewise.
(compound_svalue::calc_complexity): Drop.
(compound_svalue::maybe_fold_bits_within): Port from binding_map
to concrete_binding_map.
* svalue.h (class compound_svalue): Update leading comment. Port
from binding_map to concrete_binding_map.
Signed-off-by: David Malcolm <dmalcolm@redhat.com>
Diff:
---
gcc/analyzer/access-diagram.cc | 23 +-
gcc/analyzer/bounds-checking.cc | 13 +-
gcc/analyzer/call-summary.cc | 42 ++-
gcc/analyzer/infinite-recursion.cc | 2 +-
gcc/analyzer/program-state.cc | 2 +-
gcc/analyzer/region-model-manager.cc | 33 ++-
gcc/analyzer/region-model-manager.h | 4 +-
gcc/analyzer/region-model-reachability.cc | 4 +-
gcc/analyzer/region-model.cc | 15 +-
gcc/analyzer/region.cc | 8 +-
gcc/analyzer/store.cc | 419 +++++++++++++++++++-----------
gcc/analyzer/store.h | 131 ++++++++--
gcc/analyzer/svalue.cc | 150 +++++------
gcc/analyzer/svalue.h | 28 +-
14 files changed, 538 insertions(+), 336 deletions(-)
diff --git a/gcc/analyzer/access-diagram.cc b/gcc/analyzer/access-diagram.cc
index 9f412b5ec76c..6a3ad635f0c0 100644
--- a/gcc/analyzer/access-diagram.cc
+++ b/gcc/analyzer/access-diagram.cc
@@ -1212,23 +1212,18 @@ public:
: svalue_spatial_item (sval, bits, kind),
m_compound_sval (sval)
{
- const binding_map &map = m_compound_sval.get_map ();
+ const concrete_binding_map &map = m_compound_sval.get_concrete_bindings ();
auto_vec <const binding_key *> binding_keys;
for (auto iter : map)
{
- const binding_key *key = iter.m_key;
- const svalue *bound_sval = iter.m_sval;
- if (const concrete_binding *concrete_key
- = key->dyn_cast_concrete_binding ())
- {
- access_range range (nullptr,
- concrete_key->get_bit_range ());
- if (std::unique_ptr<spatial_item> child
- = make_existing_svalue_spatial_item (bound_sval,
- range,
- theme))
- m_children.push_back (std::move (child));
- }
+ const bit_range &key = iter.first;
+ const svalue *bound_sval = iter.second;
+ access_range range (nullptr, key);
+ if (std::unique_ptr<spatial_item> child
+ = make_existing_svalue_spatial_item (bound_sval,
+ range,
+ theme))
+ m_children.push_back (std::move (child));
}
}
diff --git a/gcc/analyzer/bounds-checking.cc b/gcc/analyzer/bounds-checking.cc
index 8d78581a3df9..f9b5165a7cbc 100644
--- a/gcc/analyzer/bounds-checking.cc
+++ b/gcc/analyzer/bounds-checking.cc
@@ -1334,14 +1334,15 @@ strip_types (const svalue *sval,
case SK_COMPOUND:
{
const compound_svalue *compound_sval = (const compound_svalue *)sval;
- binding_map typeless_map (*mgr.get_store_manager ());
- for (auto iter : compound_sval->get_map ())
+ concrete_binding_map typeless_map;
+ for (auto iter : compound_sval->get_concrete_bindings ())
{
- const binding_key *key = iter.m_key;
- const svalue *bound_sval = iter.m_sval;
- typeless_map.put (key, strip_types (bound_sval, mgr));
+ const bit_range &bits = iter.first;
+ const svalue *bound_sval = iter.second;
+ typeless_map.insert (bits, strip_types (bound_sval, mgr));
}
- return mgr.get_or_create_compound_svalue (NULL_TREE, typeless_map);
+ return mgr.get_or_create_compound_svalue (NULL_TREE,
+ std::move (typeless_map));
}
case SK_CONJURED:
return sval;
diff --git a/gcc/analyzer/call-summary.cc b/gcc/analyzer/call-summary.cc
index 7a3d4aac7c68..9220958afcaa 100644
--- a/gcc/analyzer/call-summary.cc
+++ b/gcc/analyzer/call-summary.cc
@@ -421,19 +421,12 @@ call_summary_replay::convert_svalue_from_summary_1 (const svalue *summary_sval)
const compound_svalue *compound_summary_sval
= as_a <const compound_svalue *> (summary_sval);
region_model_manager *mgr = get_manager ();
- store_manager *store_mgr = mgr->get_store_manager ();
- binding_map caller_map (*store_mgr);
- auto_vec <const binding_key *> summary_keys;
- for (auto kv : *compound_summary_sval)
- summary_keys.safe_push (kv.m_key);
- summary_keys.qsort (binding_key::cmp_ptrs);
- for (auto key : summary_keys)
+ concrete_binding_map caller_map;
+ for (auto iter_summary : *compound_summary_sval)
{
- gcc_assert (key->concrete_p ());
/* No remapping is needed for concrete binding keys. */
-
- const svalue *bound_summary_sval
- = compound_summary_sval->get_map ().get (key);
+ const bit_range &summary_bits = iter_summary.first;
+ const svalue *bound_summary_sval = iter_summary.second;
const svalue *caller_sval
= convert_svalue_from_summary (bound_summary_sval);
if (!caller_sval)
@@ -442,31 +435,26 @@ call_summary_replay::convert_svalue_from_summary_1 (const svalue *summary_sval)
if (const compound_svalue *inner_compound_sval
= caller_sval->dyn_cast_compound_svalue ())
{
- const concrete_binding *outer_key
- = as_a <const concrete_binding *> (key);
+ const bit_range &outer_key = summary_bits;
for (auto inner_kv : *inner_compound_sval)
{
// These should already be mapped to the caller.
- const binding_key *inner_key = inner_kv.m_key;
- const svalue *inner_sval = inner_kv.m_sval;
- gcc_assert (inner_key->concrete_p ());
- const concrete_binding *concrete_key
- = as_a <const concrete_binding *> (inner_key);
+ const bit_range &inner_key = inner_kv.first;
+ const svalue *inner_sval = inner_kv.second;
bit_offset_t effective_start
- = (concrete_key->get_start_bit_offset ()
- + outer_key->get_start_bit_offset ());
- const concrete_binding *effective_concrete_key
- = store_mgr->get_concrete_binding
- (effective_start,
- concrete_key->get_size_in_bits ());
- caller_map.put (effective_concrete_key, inner_sval);
+ = (inner_key.get_start_bit_offset ()
+ + outer_key.get_start_bit_offset ());
+ const bit_range effective_concrete_key
+ (effective_start,
+ summary_bits.m_size_in_bits);
+ caller_map.insert (effective_concrete_key, inner_sval);
}
}
else
- caller_map.put (key, caller_sval);
+ caller_map.insert (summary_bits, caller_sval);
}
return mgr->get_or_create_compound_svalue (summary_sval->get_type (),
- caller_map);
+ std::move (caller_map));
}
break;
case SK_CONJURED:
diff --git a/gcc/analyzer/infinite-recursion.cc b/gcc/analyzer/infinite-recursion.cc
index 64eeb95de66e..c1dc6e49b9b4 100644
--- a/gcc/analyzer/infinite-recursion.cc
+++ b/gcc/analyzer/infinite-recursion.cc
@@ -396,7 +396,7 @@ contains_unknown_p (const svalue *sval)
if (const compound_svalue *compound_sval
= sval->dyn_cast_compound_svalue ())
for (auto iter : *compound_sval)
- if (iter.m_sval->get_kind () == SK_UNKNOWN)
+ if (iter.second->get_kind () == SK_UNKNOWN)
return true;
return false;
}
diff --git a/gcc/analyzer/program-state.cc b/gcc/analyzer/program-state.cc
index 08d6b5599504..5ebaafb2661f 100644
--- a/gcc/analyzer/program-state.cc
+++ b/gcc/analyzer/program-state.cc
@@ -565,7 +565,7 @@ sm_state_map::impl_set_state (const svalue *sval,
for (auto iter = compound_sval->begin ();
iter != compound_sval->end (); ++iter)
{
- const svalue *inner_sval = iter.get_svalue ();
+ const svalue *inner_sval = iter->second;
if (inner_sval->can_have_associated_state_p ())
impl_set_state (inner_sval, state, origin, ext_state);
}
diff --git a/gcc/analyzer/region-model-manager.cc b/gcc/analyzer/region-model-manager.cc
index c4f91ecd6884..ba7f9db507b6 100644
--- a/gcc/analyzer/region-model-manager.cc
+++ b/gcc/analyzer/region-model-manager.cc
@@ -639,7 +639,7 @@ maybe_undo_optimize_bit_field_compare (tree type,
if (!INTEGRAL_TYPE_P (type))
return nullptr;
- const binding_map &map = compound_sval->get_map ();
+ const concrete_binding_map &map = compound_sval->get_concrete_bindings ();
unsigned HOST_WIDE_INT mask = TREE_INT_CST_LOW (cst);
/* If "mask" is a contiguous range of set bits, see if the
compound_sval has a value for those bits. */
@@ -651,11 +651,13 @@ maybe_undo_optimize_bit_field_compare (tree type,
if (BYTES_BIG_ENDIAN)
bound_bits = bit_range (BITS_PER_UNIT - bits.get_next_bit_offset (),
bits.m_size_in_bits);
- const concrete_binding *conc
- = get_store_manager ()->get_concrete_binding (bound_bits);
- const svalue *sval = map.get (conc);
+ const svalue *sval = map.get_any_exact_binding (bound_bits);
if (!sval)
- return nullptr;
+ {
+ /* In theory we could also look for bindings that straddle the
+ bit range. For simplicity, bail out on this case. */
+ return nullptr;
+ }
/* We have a value;
shift it by the correct number of bits. */
@@ -1406,7 +1408,26 @@ get_or_create_widening_svalue (tree type,
const svalue *
region_model_manager::get_or_create_compound_svalue (tree type,
- const binding_map &map)
+ concrete_binding_map &&map)
+{
+ compound_svalue::key_t tmp_key (type, &map);
+ if (compound_svalue **slot = m_compound_values_map.get (tmp_key))
+ return *slot;
+ compound_svalue *compound_sval
+ = new compound_svalue (alloc_symbol_id (), type, std::move (map));
+ RETURN_UNKNOWN_IF_TOO_COMPLEX (compound_sval);
+ /* Use make_key rather than reusing the key, so that we use a
+ ptr to compound_sval's binding_map, rather than the MAP param. */
+ m_compound_values_map.put (compound_sval->make_key (), compound_sval);
+ return compound_sval;
+}
+
+/* Return the svalue * of type TYPE for the compound values in MAP,
+ creating it if necessary. */
+
+const svalue *
+region_model_manager::get_or_create_compound_svalue (tree type,
+ const concrete_binding_map &map)
{
compound_svalue::key_t tmp_key (type, &map);
if (compound_svalue **slot = m_compound_values_map.get (tmp_key))
diff --git a/gcc/analyzer/region-model-manager.h b/gcc/analyzer/region-model-manager.h
index 44122ec05f61..02b5125c435b 100644
--- a/gcc/analyzer/region-model-manager.h
+++ b/gcc/analyzer/region-model-manager.h
@@ -77,7 +77,9 @@ public:
const svalue *base_svalue,
const svalue *iter_svalue);
const svalue *get_or_create_compound_svalue (tree type,
- const binding_map &map);
+ concrete_binding_map &&map);
+ const svalue *get_or_create_compound_svalue (tree type,
+ const concrete_binding_map &map);
const svalue *get_or_create_conjured_svalue (tree type, const gimple *stmt,
const region *id_reg,
const conjured_purge &p,
diff --git a/gcc/analyzer/region-model-reachability.cc b/gcc/analyzer/region-model-reachability.cc
index 19b96b982809..e9e8edfcc1a7 100644
--- a/gcc/analyzer/region-model-reachability.cc
+++ b/gcc/analyzer/region-model-reachability.cc
@@ -172,7 +172,7 @@ reachable_regions::handle_sval (const svalue *sval)
for (auto iter = compound_sval->begin ();
iter != compound_sval->end (); ++iter)
{
- const svalue *iter_sval = iter.get_svalue ();
+ const svalue *iter_sval = iter->second;
handle_sval (iter_sval);
}
}
@@ -238,7 +238,7 @@ reachable_regions::handle_parm (const svalue *sval, tree param_type)
for (auto iter = compound_sval->begin ();
iter != compound_sval->end (); ++iter)
{
- const svalue *iter_sval = iter.get_svalue ();
+ const svalue *iter_sval = iter->second;
handle_sval (iter_sval);
}
}
diff --git a/gcc/analyzer/region-model.cc b/gcc/analyzer/region-model.cc
index d46b130b00d9..6e25029d9d25 100644
--- a/gcc/analyzer/region-model.cc
+++ b/gcc/analyzer/region-model.cc
@@ -4701,7 +4701,6 @@ region_model::scan_for_null_terminator_1 (const region *reg,
region_model_context *ctxt) const
{
logger *logger = ctxt ? ctxt->get_logger () : nullptr;
- store_manager *store_mgr = m_mgr->get_store_manager ();
region_offset offset = reg->get_offset (m_mgr);
if (offset.symbolic_p ())
@@ -4764,7 +4763,7 @@ region_model::scan_for_null_terminator_1 (const region *reg,
logger->end_log_line ();
}
- binding_map result (*store_mgr);
+ concrete_binding_map result;
while (1)
{
@@ -4809,9 +4808,7 @@ region_model::scan_for_null_terminator_1 (const region *reg,
if (out_sval)
{
byte_range bytes_to_write (dst_byte_offset, fragment_bytes_read);
- const binding_key *key
- = store_mgr->get_concrete_binding (bytes_to_write);
- result.put (key, sval);
+ result.insert (bytes_to_write, sval);
}
src_byte_offset += fragment_bytes_read;
@@ -4821,7 +4818,7 @@ region_model::scan_for_null_terminator_1 (const region *reg,
{
if (out_sval)
*out_sval = m_mgr->get_or_create_compound_svalue (NULL_TREE,
- result);
+ std::move (result));
if (logger)
logger->log ("got terminator");
return m_mgr->get_or_create_int_cst (size_type_node,
@@ -7203,7 +7200,7 @@ private:
= as_a <const compound_svalue *> (m_copied_sval);
bit_size_t result = 0;
/* Find keys for uninit svals. */
- for (auto iter : compound_sval->get_map ().get_concrete_bindings ())
+ for (auto iter : compound_sval->get_concrete_bindings ())
{
const svalue *sval = iter.second;
if (const poisoned_svalue *psval
@@ -7252,7 +7249,7 @@ private:
{
/* Find keys for uninit svals. */
auto_vec<bit_range> uninit_bit_ranges;
- for (auto iter : compound_sval->get_map ().get_concrete_bindings ())
+ for (auto iter : compound_sval->get_concrete_bindings ())
{
const svalue *sval = iter.second;
if (const poisoned_svalue *psval
@@ -7462,7 +7459,7 @@ contains_uninit_p (const svalue *sval)
for (auto iter = compound_sval->begin ();
iter != compound_sval->end (); ++iter)
{
- const svalue *inner_sval = iter.get_svalue ();
+ const svalue *inner_sval = iter->second;
if (const poisoned_svalue *psval
= inner_sval->dyn_cast_poisoned_svalue ())
if (psval->get_poison_kind () == poison_kind::uninit)
diff --git a/gcc/analyzer/region.cc b/gcc/analyzer/region.cc
index 5631c4e87e08..b03c79ffa72c 100644
--- a/gcc/analyzer/region.cc
+++ b/gcc/analyzer/region.cc
@@ -1713,15 +1713,15 @@ const svalue *
decl_region::calc_svalue_for_constructor (tree ctor,
region_model_manager *mgr) const
{
- /* Create a binding map, applying ctor to it, using this
+ /* Create a concrete_binding_map, applying ctor to it, using this
decl_region as the base region when building child regions
for offset calculations. */
- binding_map map (*mgr->get_store_manager ());
+ concrete_binding_map map;
if (!map.apply_ctor_to_region (this, ctor, mgr))
return mgr->get_or_create_unknown_svalue (get_type ());
/* Return a compound svalue for the map we built. */
- return mgr->get_or_create_compound_svalue (get_type (), map);
+ return mgr->get_or_create_compound_svalue (get_type (), std::move (map));
}
/* Get an svalue for CTOR, a CONSTRUCTOR for this region's decl. */
@@ -1778,7 +1778,7 @@ decl_region::get_svalue_for_initializer (region_model_manager *mgr) const
binding_cluster c (*mgr->get_store_manager (), this);
c.zero_fill_region (mgr->get_store_manager (), this);
return mgr->get_or_create_compound_svalue (TREE_TYPE (m_decl),
- c.get_map ());
+ c.get_map ().get_concrete_bindings ());
}
/* LTO can write out error_mark_node as the DECL_INITIAL for simple scalar
diff --git a/gcc/analyzer/store.cc b/gcc/analyzer/store.cc
index 878536eb42b4..d198aec9d2b8 100644
--- a/gcc/analyzer/store.cc
+++ b/gcc/analyzer/store.cc
@@ -618,6 +618,234 @@ simplify_for_binding (const svalue *sval)
return sval;
}
+/* class concrete_binding_map. */
+
+/* Dump a representation of this concrete_binding_map to PP.
+ SIMPLE controls how values and regions are to be printed.
+ If MULTILINE, then split the dump over multiple lines and
+ use whitespace for readability, otherwise put all on one line. */
+
+void
+concrete_binding_map::dump_to_pp (pretty_printer *pp, bool simple, bool multiline) const
+{
+ bool first = true;
+ for (auto iter : *this)
+ {
+ const bit_range &bits = iter.first;
+ const svalue *value = iter.second;
+ if (multiline)
+ {
+ pp_string (pp, " bits: {");
+ bits.dump_to_pp (pp);
+ pp_string (pp, "}");
+ pp_newline (pp);
+ pp_string (pp, " value: ");
+ if (tree t = value->get_type ())
+ dump_quoted_tree (pp, t);
+ pp_string (pp, " {");
+ value->dump_to_pp (pp, simple);
+ pp_string (pp, "}");
+ pp_newline (pp);
+ }
+ else
+ {
+ if (first)
+ first = false;
+ else
+ pp_string (pp, ", ");
+ pp_string (pp, "bits: {");
+ bits.dump_to_pp (pp);
+ pp_string (pp, "}, value: {");
+ value->dump_to_pp (pp, simple);
+ pp_string (pp, "}");
+ }
+ }
+}
+
+void
+concrete_binding_map::dump (bool simple) const
+{
+ tree_dump_pretty_printer pp (stderr);
+ dump_to_pp (&pp, simple, true);
+ pp_newline (&pp);
+}
+
+void
+concrete_binding_map::add_to_tree_widget (text_art::tree_widget &parent_widget,
+ const text_art::dump_widget_info &dwi) const
+{
+ for (auto iter : *this)
+ {
+ const bit_range &bits = iter.first;
+ const svalue *sval = iter.second;
+
+ pretty_printer the_pp;
+ pretty_printer * const pp = &the_pp;
+ pp_format_decoder (pp) = default_tree_printer;
+ pp_show_color (pp) = true;
+ const bool simple = true;
+
+ bits.dump_to_pp (pp);
+ pp_string (pp, ": ");
+ if (tree t = sval->get_type ())
+ dump_quoted_tree (pp, t);
+ pp_string (pp, " {");
+ sval->dump_to_pp (pp, simple);
+ pp_string (pp, "}");
+
+ parent_widget.add_child (text_art::tree_widget::make (dwi, pp));
+ }
+}
+
+void
+concrete_binding_map::validate () const
+{
+ for (auto iter = m_map.begin (); iter != m_map.end (); ++iter)
+ {
+ /* Ensure we don't nest compound svalues
+ within concrete_binding_map instances. */
+ const svalue *sval = iter->second;
+ gcc_assert (sval->get_kind () != SK_COMPOUND);
+
+ /* Check for overlapping concrete bindings. */
+ auto next (iter);
+ ++next;
+ if (next != m_map.end ())
+ {
+ /* Verify they are in order, and do not overlap. */
+ const bit_range &iter_bits = iter->first;
+ const bit_range &next_bits = next->first;
+ gcc_assert (iter_bits.get_start_bit_offset ()
+ < next_bits.get_start_bit_offset ());
+ gcc_assert (iter_bits.get_last_bit_offset ()
+ < next_bits.get_start_bit_offset ());
+ gcc_assert (iter_bits.get_next_bit_offset ()
+ <= next_bits.get_start_bit_offset ());
+ }
+ }
+}
+
+/* Comparator for imposing an order on concrete_binding_map instances. */
+
+int
+concrete_binding_map::cmp (const concrete_binding_map &map1,
+ const concrete_binding_map &map2)
+{
+ if (int size_cmp = map1.size () - map2.size ())
+ return size_cmp;
+
+ auto iter1 = map1.begin ();
+ auto iter2 = map2.begin ();
+ while (iter1 != map1.end ())
+ {
+ gcc_assert (iter2 != map2.end ());
+ if (int bit_cmp = bit_range::cmp (iter1->first, iter2->first))
+ return bit_cmp;
+ if (int sval_cmp = svalue::cmp_ptr (iter1->second, iter2->second))
+ return sval_cmp;
+ ++iter1;
+ ++iter2;
+ }
+ return 0;
+}
+
+/* Get the svalue bound precisely to BITS, if any, otherwise
+ return nullptr. */
+
+const svalue *
+concrete_binding_map::get_any_exact_binding (const bit_range &bits) const
+{
+ auto iter = m_map.find (bits);
+ if (iter == m_map.end ())
+ return nullptr;
+ return iter->second;
+}
+
+/* Calculate what the complexity of a compound_svalue instance for this
+ map will be, based on the bound svalues. */
+
+complexity
+concrete_binding_map::calc_complexity () const
+{
+ unsigned num_child_nodes = 0;
+ unsigned max_child_depth = 0;
+ for (auto iter : m_map)
+ {
+ const complexity &sval_c = iter.second->get_complexity ();
+ num_child_nodes += sval_c.m_num_nodes;
+ max_child_depth = MAX (max_child_depth, sval_c.m_max_depth);
+ }
+ return complexity (num_child_nodes + 1, max_child_depth + 1);
+}
+
+void
+concrete_binding_map::
+remove_overlapping_binding (store_manager *mgr,
+ const bit_range &bits_to_drop,
+ const bit_range &affected_bound_bits,
+ const svalue &old_sval)
+{
+ gcc_assert (bits_to_drop.intersects_p (affected_bound_bits));
+
+ /* Remove existing binding. */
+ erase (affected_bound_bits);
+
+ if (affected_bound_bits.get_start_bit_offset ()
+ < bits_to_drop.get_start_bit_offset ())
+ {
+ /* We have a truncated prefix. */
+ bit_range prefix_bits (affected_bound_bits.get_start_bit_offset (),
+ (bits_to_drop.get_start_bit_offset ()
+ - affected_bound_bits.get_start_bit_offset ()));
+ bit_range rel_prefix (0, prefix_bits.m_size_in_bits);
+ const svalue *prefix_sval
+ = old_sval.extract_bit_range (NULL_TREE,
+ rel_prefix,
+ mgr->get_svalue_manager ());
+ insert (prefix_bits, prefix_sval);
+ }
+
+ if (affected_bound_bits.get_next_bit_offset ()
+ > bits_to_drop.get_next_bit_offset ())
+ {
+ /* We have a truncated suffix. */
+ bit_range suffix_bits (bits_to_drop.get_next_bit_offset (),
+ (affected_bound_bits.get_next_bit_offset ()
+ - bits_to_drop.get_next_bit_offset ()));
+ bit_range rel_suffix (bits_to_drop.get_next_bit_offset ()
+ - affected_bound_bits.get_start_bit_offset (),
+ suffix_bits.m_size_in_bits);
+ const svalue *suffix_sval
+ = old_sval.extract_bit_range (NULL_TREE,
+ rel_suffix,
+ mgr->get_svalue_manager ());
+ insert (suffix_bits, suffix_sval);
+ }
+}
+
+void
+concrete_binding_map::
+remove_overlapping_bindings (store_manager *mgr,
+ const bit_range &bits_to_drop)
+{
+ auto bindings = get_overlapping_bindings (bits_to_drop);
+ for (auto iter : bindings)
+ remove_overlapping_binding (mgr, bits_to_drop, iter.first, iter.second);
+}
+
+std::vector<std::pair<bit_range, const svalue &>>
+concrete_binding_map::get_overlapping_bindings (const bit_range &bits)
+{
+ std::vector<std::pair<bit_range, const svalue &>> result;
+ for (auto iter : m_map)
+ if (iter.first.intersects_p (bits))
+ {
+ gcc_assert (iter.second);
+ result.push_back ({iter.first, *iter.second});
+ }
+ return result;
+}
+
/* class binding_map::const_iterator. */
bool
@@ -838,7 +1066,7 @@ binding_map::put (const binding_key *key, const svalue *sval)
if (iter != m_concrete.end ())
(*iter).second = sval;
else
- m_concrete.insert ({bits, sval});
+ m_concrete.insert (bits, sval);
}
}
@@ -974,24 +1202,7 @@ binding_map::validate () const
/* We can't have both concrete and symbolic keys. */
gcc_assert (num_concrete == 0 || num_symbolic == 0);
- /* Check for overlapping concrete bindings. */
- for (auto iter = m_concrete.begin (); iter != m_concrete.end (); ++iter)
- {
- auto next (iter);
- ++next;
- if (next != m_concrete.end ())
- {
- /* Verify they are in order, and do not overlap. */
- const bit_range &iter_bits = iter->first;
- const bit_range &next_bits = next->first;
- gcc_assert (iter_bits.get_start_bit_offset ()
- < next_bits.get_start_bit_offset ());
- gcc_assert (iter_bits.get_last_bit_offset ()
- < next_bits.get_start_bit_offset ());
- gcc_assert (iter_bits.get_next_bit_offset ()
- <= next_bits.get_start_bit_offset ());
- }
- }
+ m_concrete.validate ();
}
/* Return a new json::object of the form
@@ -1052,39 +1263,6 @@ binding_map::add_to_tree_widget (text_art::tree_widget &parent_widget,
}
}
-
-/* Comparator for imposing an order on binding_maps. */
-
-int
-binding_map::cmp (const binding_map &map1, const binding_map &map2)
-{
- if (int count_cmp = map1.elements () - map2.elements ())
- return count_cmp;
-
- auto_vec <const binding_key *> keys1 (map1.elements ());
- for (auto iter : map1)
- keys1.quick_push (iter.m_key);
- keys1.qsort (binding_key::cmp_ptrs);
-
- auto_vec <const binding_key *> keys2 (map2.elements ());
- for (auto iter : map2)
- keys2.quick_push (iter.m_key);
- keys2.qsort (binding_key::cmp_ptrs);
-
- for (size_t i = 0; i < keys1.length (); i++)
- {
- const binding_key *k1 = keys1[i];
- const binding_key *k2 = keys2[i];
- if (int key_cmp = binding_key::cmp (k1, k2))
- return key_cmp;
- gcc_assert (k1 == k2);
- if (int sval_cmp = svalue::cmp_ptr (map1.get (k1), map2.get (k2)))
- return sval_cmp;
- }
-
- return 0;
-}
-
/* Get the child region of PARENT_REG based upon INDEX within a
CONSTRUCTOR. */
@@ -1157,8 +1335,8 @@ get_svalue_for_ctor_val (tree val, region_model_manager *mgr)
to hitting a complexity limit). */
bool
-binding_map::apply_ctor_to_region (const region *parent_reg, tree ctor,
- region_model_manager *mgr)
+concrete_binding_map::apply_ctor_to_region (const region *parent_reg, tree ctor,
+ region_model_manager *mgr)
{
gcc_assert (parent_reg);
gcc_assert (TREE_CODE (ctor) == CONSTRUCTOR);
@@ -1218,10 +1396,10 @@ binding_map::apply_ctor_to_region (const region *parent_reg, tree ctor,
to hitting a complexity limit). */
bool
-binding_map::apply_ctor_val_to_range (const region *parent_reg,
- region_model_manager *mgr,
- tree min_index, tree max_index,
- tree val)
+concrete_binding_map::apply_ctor_val_to_range (const region *parent_reg,
+ region_model_manager *mgr,
+ tree min_index, tree max_index,
+ tree val)
{
gcc_assert (TREE_CODE (min_index) == INTEGER_CST);
gcc_assert (TREE_CODE (max_index) == INTEGER_CST);
@@ -1245,10 +1423,6 @@ binding_map::apply_ctor_val_to_range (const region *parent_reg,
= max_element_key->dyn_cast_concrete_binding ();
bit_size_t range_size_in_bits
= max_element_ckey->get_next_bit_offset () - start_bit_offset;
- const concrete_binding *range_key
- = smgr->get_concrete_binding (start_bit_offset, range_size_in_bits);
- if (range_key->symbolic_p ())
- return false;
/* Get the value. */
if (TREE_CODE (val) == CONSTRUCTOR)
@@ -1256,7 +1430,8 @@ binding_map::apply_ctor_val_to_range (const region *parent_reg,
const svalue *sval = get_svalue_for_ctor_val (val, mgr);
/* Bind the value to the range. */
- put (range_key, sval);
+ const bit_range affected_bits (start_bit_offset, range_size_in_bits);
+ insert (affected_bits, sval);
return true;
}
@@ -1266,9 +1441,9 @@ binding_map::apply_ctor_val_to_range (const region *parent_reg,
to hitting a complexity limit). */
bool
-binding_map::apply_ctor_pair_to_child_region (const region *parent_reg,
- region_model_manager *mgr,
- tree index, tree val)
+concrete_binding_map::apply_ctor_pair_to_child_region (const region *parent_reg,
+ region_model_manager *mgr,
+ tree index, tree val)
{
const region *child_reg
= get_subregion_within_ctor_for_ctor_pair (parent_reg, index, val, mgr);
@@ -1309,7 +1484,8 @@ binding_map::apply_ctor_pair_to_child_region (const region *parent_reg,
(child_parent_offset, sval_bit_size);
}
gcc_assert (k->concrete_p ());
- put (k, sval);
+ auto conc_key = as_a <const concrete_binding *> (k);
+ insert (conc_key->get_bit_range (), sval);
return true;
}
}
@@ -1477,42 +1653,9 @@ binding_map::remove_overlapping_bindings (store_manager *mgr,
const bit_range &drop_bits = drop_ckey->get_bit_range ();
const bit_range &iter_bits = iter_ckey->get_bit_range ();
-
- if (iter_bits.get_start_bit_offset ()
- < drop_bits.get_start_bit_offset ())
- {
- /* We have a truncated prefix. */
- bit_range prefix_bits (iter_bits.get_start_bit_offset (),
- (drop_bits.get_start_bit_offset ()
- - iter_bits.get_start_bit_offset ()));
- const concrete_binding *prefix_key
- = mgr->get_concrete_binding (prefix_bits);
- bit_range rel_prefix (0, prefix_bits.m_size_in_bits);
- const svalue *prefix_sval
- = old_sval->extract_bit_range (NULL_TREE,
- rel_prefix,
- mgr->get_svalue_manager ());
- put (prefix_key, prefix_sval);
- }
-
- if (iter_bits.get_next_bit_offset ()
- > drop_bits.get_next_bit_offset ())
- {
- /* We have a truncated suffix. */
- bit_range suffix_bits (drop_bits.get_next_bit_offset (),
- (iter_bits.get_next_bit_offset ()
- - drop_bits.get_next_bit_offset ()));
- const concrete_binding *suffix_key
- = mgr->get_concrete_binding (suffix_bits);
- bit_range rel_suffix (drop_bits.get_next_bit_offset ()
- - iter_bits.get_start_bit_offset (),
- suffix_bits.m_size_in_bits);
- const svalue *suffix_sval
- = old_sval->extract_bit_range (NULL_TREE,
- rel_suffix,
- mgr->get_svalue_manager ());
- put (suffix_key, suffix_sval);
- }
+ gcc_assert (old_sval);
+ m_concrete.remove_overlapping_binding (mgr, drop_bits, iter_bits,
+ *old_sval);
}
}
}
@@ -1753,22 +1896,15 @@ binding_cluster::bind_compound_sval (store_manager *mgr,
for (auto iter : *compound_sval)
{
- const binding_key *iter_key = iter.m_key;
- const svalue *iter_sval = iter.m_sval;
-
- if (const concrete_binding *concrete_key
- = iter_key->dyn_cast_concrete_binding ())
- {
- bit_offset_t effective_start
- = (concrete_key->get_start_bit_offset ()
- + reg_offset.get_bit_offset ());
- const concrete_binding *effective_concrete_key
- = mgr->get_concrete_binding (effective_start,
- concrete_key->get_size_in_bits ());
- bind_key (effective_concrete_key, iter_sval);
- }
- else
- gcc_unreachable ();
+ const bit_range &iter_bits = iter.first;
+ const svalue *iter_sval = iter.second;
+
+ bit_offset_t effective_start
+ = (iter_bits.get_start_bit_offset ()
+ + reg_offset.get_bit_offset ());
+ const bit_range affected_bits (effective_start,
+ iter_bits.m_size_in_bits);
+ bind_key (mgr->get_concrete_binding (affected_bits), iter_sval);
}
}
@@ -2060,8 +2196,8 @@ binding_cluster::maybe_get_compound_binding (store_manager *mgr,
perhaps we should have a spatial-organized data structure for
concrete keys, though. */
- binding_map result_map (*mgr);
- binding_map default_map (*mgr);
+ concrete_binding_map result_map;
+ concrete_binding_map default_map;
/* Set up default values in default_map. */
const svalue *default_sval;
@@ -2077,10 +2213,10 @@ binding_cluster::maybe_get_compound_binding (store_manager *mgr,
= default_key->dyn_cast_concrete_binding ();
if (!concrete_default_key)
return nullptr;
- const concrete_binding *default_key_relative_to_reg
- = mgr->get_concrete_binding (0, concrete_default_key->get_size_in_bits ());
+ const bit_range default_key_relative_to_reg
+ (0, concrete_default_key->get_size_in_bits ());
- default_map.put (default_key_relative_to_reg, default_sval);
+ default_map.insert (default_key_relative_to_reg, default_sval);
for (auto iter : m_map)
{
@@ -2111,19 +2247,12 @@ binding_cluster::maybe_get_compound_binding (store_manager *mgr,
if (reg_range.contains_p (bound_range, &subrange))
{
/* We have a bound range fully within REG.
- Add it to map, offsetting accordingly. */
-
- /* Get offset of KEY relative to REG, rather than to
- the cluster. */
- const concrete_binding *offset_concrete_key
- = mgr->get_concrete_binding (subrange);
- result_map.put (offset_concrete_key, sval);
+ Add it to result_map, offsetting accordingly. */
+ result_map.insert (subrange, sval);
/* Clobber default_map, removing/trimming/spliting where
it overlaps with offset_concrete_key. */
- default_map.remove_overlapping_bindings (mgr,
- offset_concrete_key,
- nullptr, nullptr, false);
+ default_map.remove_overlapping_bindings (mgr, subrange);
}
else if (bound_range.contains_p (reg_range, &subrange))
{
@@ -2148,16 +2277,11 @@ binding_cluster::maybe_get_compound_binding (store_manager *mgr,
bound_subrange,
mgr->get_svalue_manager ());
- /* Get key for overlap, relative to the REG. */
- const concrete_binding *overlap_concrete_key
- = mgr->get_concrete_binding (reg_subrange);
- result_map.put (overlap_concrete_key, overlap_sval);
+ result_map.insert (reg_subrange, overlap_sval);
/* Clobber default_map, removing/trimming/spliting where
it overlaps with overlap_concrete_key. */
- default_map.remove_overlapping_bindings (mgr,
- overlap_concrete_key,
- nullptr, nullptr, false);
+ default_map.remove_overlapping_bindings (mgr, reg_subrange);
}
}
else
@@ -2165,18 +2289,19 @@ binding_cluster::maybe_get_compound_binding (store_manager *mgr,
return nullptr;
}
- if (result_map.elements () == 0)
+ if (result_map.size () == 0)
return nullptr;
/* Merge any bindings from default_map into result_map. */
for (auto iter : default_map)
{
- const binding_key *key = iter.m_key;
- const svalue *sval = iter.m_sval;
- result_map.put (key, sval);
+ const bit_range &key = iter.first;
+ const svalue *sval = iter.second;
+ result_map.insert (key, sval);
}
- return sval_mgr->get_or_create_compound_svalue (reg->get_type (), result_map);
+ return sval_mgr->get_or_create_compound_svalue (reg->get_type (),
+ std::move (result_map));
}
/* Remove, truncate, and/or split any bindings within this map that
@@ -3845,7 +3970,7 @@ store::replay_call_summary_cluster (call_summary_replay &r,
if (!summary_sval)
summary_sval = reg_mgr->get_or_create_compound_svalue
(summary_base_reg->get_type (),
- summary_cluster->get_map ());
+ summary_cluster->get_map ().get_concrete_bindings ());
const svalue *caller_sval
= r.convert_svalue_from_summary (summary_sval);
if (!caller_sval)
diff --git a/gcc/analyzer/store.h b/gcc/analyzer/store.h
index e562e5479ed0..021a438222fd 100644
--- a/gcc/analyzer/store.h
+++ b/gcc/analyzer/store.h
@@ -22,6 +22,7 @@ along with GCC; see the file COPYING3. If not see
#define GCC_ANALYZER_STORE_H
#include "text-art/tree-widget.h"
+#include "analyzer/complexity.h"
/* Implementation of the region-based ternary model described in:
"A Memory Model for Static Analysis of C Programs"
@@ -513,11 +514,115 @@ template <> struct default_hash_traits<ana::symbolic_binding>
namespace ana {
-/* A mapping from binding_keys to svalues, for use by binding_cluster
- and compound_svalue.
- We store a map from concrete keys to svalues, which is ordered by
- the start offset.
- We also store a vector of (symbolic key, svalue) pairs, but for now
+/* A mapping from concrete bit_ranges to svalues, for use by
+ binding_cluster and compound_svalue.
+ The keys are ordered by the start offset, and must not overlap
+ The bound svalues may not be compound_svalues, so that we don't
+ nest these (for canonicalization). */
+
+class concrete_binding_map
+{
+public:
+ using map_t = std::map<bit_range, const svalue *>;
+ using const_iterator = map_t::const_iterator;
+ using iterator = map_t::iterator;
+
+ void clear () { m_map.clear (); }
+ bool empty_p () const { return m_map.empty (); }
+
+ bool
+ operator== (const concrete_binding_map &other) const
+ {
+ return m_map == other.m_map;
+ }
+ bool
+ operator!= (const concrete_binding_map &other) const
+ {
+ return m_map != other.m_map;
+ }
+
+ const_iterator begin () const { return m_map.begin (); }
+ const_iterator end () const { return m_map.end (); }
+ iterator begin () { return m_map.begin (); }
+ iterator end () { return m_map.end (); }
+
+ size_t size () const { return m_map.size (); }
+
+ void dump_to_pp (pretty_printer *pp, bool simple, bool multiline) const;
+ void dump (bool simple) const;
+
+ void add_to_tree_widget (text_art::tree_widget &parent_widget,
+ const text_art::dump_widget_info &dwi) const;
+
+ void validate () const;
+
+ static int
+ cmp (const concrete_binding_map &map1,
+ const concrete_binding_map &map2);
+
+ void
+ insert (const bit_range &bits, const svalue *sval)
+ {
+ m_map.insert ({bits, sval});
+ }
+
+ void
+ insert (const byte_range &bytes, const svalue *sval)
+ {
+ m_map.insert ({bytes.as_bit_range (), sval});
+ }
+
+ void
+ erase (const bit_range &bits)
+ {
+ m_map.erase (bits);
+ }
+
+ const svalue *
+ get_any_exact_binding (const bit_range &bits) const;
+
+ const_iterator
+ find (const bit_range &bits) const
+ {
+ return m_map.find (bits);
+ }
+ iterator
+ find (const bit_range &bits)
+ {
+ return m_map.find (bits);
+ }
+
+ complexity calc_complexity () const;
+
+ bool apply_ctor_to_region (const region *parent_reg, tree ctor,
+ region_model_manager *mgr);
+
+ void remove_overlapping_binding (store_manager *mgr,
+ const bit_range &bits_to_drop,
+ const bit_range &affected_bound_bits,
+ const svalue &old_sval);
+
+ void remove_overlapping_bindings (store_manager *mgr,
+ const bit_range &bits);
+
+private:
+ std::vector<std::pair<bit_range, const svalue &>>
+ get_overlapping_bindings (const bit_range &bits);
+
+ bool apply_ctor_val_to_range (const region *parent_reg,
+ region_model_manager *mgr,
+ tree min_index, tree max_index,
+ tree val);
+ bool apply_ctor_pair_to_child_region (const region *parent_reg,
+ region_model_manager *mgr,
+ tree index, tree val);
+
+ map_t m_map;
+};
+
+/* A mapping from binding_keys to svalues, for use by binding_cluster.
+ We store bindings at concrete bit ranges via a concrete_binding_map,
+ along with a vector of (symbolic key, svalue) pairs, but for now
this has maximum length of 1. */
class binding_map
@@ -534,7 +639,7 @@ public:
const region *m_region;
const svalue *m_sval;
};
- using concrete_bindings_t = std::map<bit_range, const svalue *>;
+ using concrete_bindings_t = concrete_binding_map;
using symbolic_bindings_t = std::vector<symbolic_binding>;
struct binding_pair
@@ -632,7 +737,7 @@ public:
bool empty_p () const
{
- return m_concrete.empty () && m_symbolic.empty ();
+ return m_concrete.empty_p () && m_symbolic.empty ();
}
const_iterator_t begin () const;
@@ -651,11 +756,6 @@ public:
void add_to_tree_widget (text_art::tree_widget &parent_widget,
const text_art::dump_widget_info &dwi) const;
- bool apply_ctor_to_region (const region *parent_reg, tree ctor,
- region_model_manager *mgr);
-
- static int cmp (const binding_map &map1, const binding_map &map2);
-
void remove_overlapping_bindings (store_manager *mgr,
const binding_key *drop_key,
uncertainty_t *uncertainty,
@@ -671,13 +771,6 @@ public:
private:
void get_overlapping_bindings (const binding_key *key,
auto_vec<const binding_key *> *out);
- bool apply_ctor_val_to_range (const region *parent_reg,
- region_model_manager *mgr,
- tree min_index, tree max_index,
- tree val);
- bool apply_ctor_pair_to_child_region (const region *parent_reg,
- region_model_manager *mgr,
- tree index, tree val);
store_manager &m_store_mgr;
concrete_bindings_t m_concrete;
diff --git a/gcc/analyzer/svalue.cc b/gcc/analyzer/svalue.cc
index 74c2c0dbd4a3..52e853fdc8a9 100644
--- a/gcc/analyzer/svalue.cc
+++ b/gcc/analyzer/svalue.cc
@@ -678,8 +678,9 @@ svalue::cmp_ptr (const svalue *sval1, const svalue *sval2)
{
const compound_svalue *compound_sval1 = (const compound_svalue *)sval1;
const compound_svalue *compound_sval2 = (const compound_svalue *)sval2;
- return binding_map::cmp (compound_sval1->get_map (),
- compound_sval2->get_map ());
+ return concrete_binding_map::cmp
+ (compound_sval1->get_concrete_bindings (),
+ compound_sval2->get_concrete_bindings ());
}
break;
case SK_CONJURED:
@@ -2349,19 +2350,29 @@ unmergeable_svalue::implicitly_live_p (const svalue_set *live_svalues,
compound_svalue::compound_svalue (symbol::id_t id,
tree type,
- const binding_map &map)
-: svalue (calc_complexity (map), id, type), m_map (map)
+ concrete_binding_map &&map)
+: svalue (map.calc_complexity (), id, type), m_map (std::move (map))
{
#if CHECKING_P
for (auto iter : *this)
{
- /* All keys within the underlying binding_map are required to be concrete,
- not symbolic. */
- const binding_key *key = iter.m_key;
- gcc_assert (key->concrete_p ());
+ /* We don't nest compound svalues. */
+ const svalue *sval = iter.second;
+ gcc_assert (sval->get_kind () != SK_COMPOUND);
+ }
+#endif
+}
+compound_svalue::compound_svalue (symbol::id_t id,
+ tree type,
+ const concrete_binding_map &map)
+: svalue (map.calc_complexity (), id, type), m_map (map)
+{
+#if CHECKING_P
+ for (auto iter : *this)
+ {
/* We don't nest compound svalues. */
- const svalue *sval = iter.m_sval;
+ const svalue *sval = iter.second;
gcc_assert (sval->get_kind () != SK_COMPOUND);
}
#endif
@@ -2424,30 +2435,10 @@ void
compound_svalue::accept (visitor *v) const
{
for (auto iter : m_map)
- {
- //iter.first.accept (v);
- iter.m_sval->accept (v);
- }
+ iter.second->accept (v);
v->visit_compound_svalue (this);
}
-/* Calculate what the complexity of a compound_svalue instance for MAP
- will be, based on the svalues bound within MAP. */
-
-complexity
-compound_svalue::calc_complexity (const binding_map &map)
-{
- unsigned num_child_nodes = 0;
- unsigned max_child_depth = 0;
- for (auto iter : map)
- {
- const complexity &sval_c = iter.m_sval->get_complexity ();
- num_child_nodes += sval_c.m_num_nodes;
- max_child_depth = MAX (max_child_depth, sval_c.m_max_depth);
- }
- return complexity (num_child_nodes + 1, max_child_depth + 1);
-}
-
/* Implementation of svalue::maybe_fold_bits_within vfunc
for compound_svalue. */
@@ -2456,65 +2447,56 @@ compound_svalue::maybe_fold_bits_within (tree type,
const bit_range &bits,
region_model_manager *mgr) const
{
- binding_map result_map (*mgr->get_store_manager ());
+ concrete_binding_map result_map;
for (auto iter : m_map)
{
- const binding_key *key = iter.m_key;
- if (const concrete_binding *conc_key
- = key->dyn_cast_concrete_binding ())
+ const bit_range &iter_bits = iter.first;
+
+ /* Ignore concrete bindings outside BITS. */
+ if (!iter_bits.intersects_p (bits))
+ continue;
+
+ const svalue *sval = iter.second;
+ /* Get the position of iter_bits relative to BITS. */
+ bit_range result_location (iter_bits.get_start_bit_offset ()
+ - bits.get_start_bit_offset (),
+ iter_bits.m_size_in_bits);
+ /* If iter_bits starts after BITS, trim off leading bits
+ from the svalue and adjust binding location. */
+ if (result_location.m_start_bit_offset < 0)
{
- /* Ignore concrete bindings outside BITS. */
- if (!conc_key->get_bit_range ().intersects_p (bits))
- continue;
-
- const svalue *sval = iter.m_sval;
- /* Get the position of conc_key relative to BITS. */
- bit_range result_location (conc_key->get_start_bit_offset ()
- - bits.get_start_bit_offset (),
- conc_key->get_size_in_bits ());
- /* If conc_key starts after BITS, trim off leading bits
- from the svalue and adjust binding location. */
- if (result_location.m_start_bit_offset < 0)
- {
- bit_size_t leading_bits_to_drop
- = -result_location.m_start_bit_offset;
- result_location = bit_range
- (0, result_location.m_size_in_bits - leading_bits_to_drop);
- bit_range bits_within_sval (leading_bits_to_drop,
- result_location.m_size_in_bits);
- /* Trim off leading bits from iter_sval. */
- sval = mgr->get_or_create_bits_within (NULL_TREE,
- bits_within_sval,
- sval);
- }
- /* If conc_key finishes after BITS, trim off trailing bits
- from the svalue and adjust binding location. */
- if (conc_key->get_next_bit_offset ()
- > bits.get_next_bit_offset ())
- {
- bit_size_t trailing_bits_to_drop
- = (conc_key->get_next_bit_offset ()
- - bits.get_next_bit_offset ());
- result_location = bit_range
- (result_location.m_start_bit_offset,
- result_location.m_size_in_bits - trailing_bits_to_drop);
- bit_range bits_within_sval (0,
- result_location.m_size_in_bits);
- /* Trim off leading bits from iter_sval. */
- sval = mgr->get_or_create_bits_within (NULL_TREE,
- bits_within_sval,
- sval);
- }
- const concrete_binding *offset_conc_key
- = mgr->get_store_manager ()->get_concrete_binding
- (result_location);
- result_map.put (offset_conc_key, sval);
+ bit_size_t leading_bits_to_drop
+ = -result_location.m_start_bit_offset;
+ result_location = bit_range
+ (0, result_location.m_size_in_bits - leading_bits_to_drop);
+ bit_range bits_within_sval (leading_bits_to_drop,
+ result_location.m_size_in_bits);
+ /* Trim off leading bits from iter_sval. */
+ sval = mgr->get_or_create_bits_within (NULL_TREE,
+ bits_within_sval,
+ sval);
}
- else
- /* If we have any symbolic keys we can't get it as bits. */
- return nullptr;
+ /* If iter_bits finishes after BITS, trim off trailing bits
+ from the svalue and adjust binding location. */
+ if (iter_bits.get_next_bit_offset ()
+ > bits.get_next_bit_offset ())
+ {
+ bit_size_t trailing_bits_to_drop
+ = (iter_bits.get_next_bit_offset ()
+ - bits.get_next_bit_offset ());
+ result_location = bit_range
+ (result_location.m_start_bit_offset,
+ result_location.m_size_in_bits - trailing_bits_to_drop);
+ bit_range bits_within_sval (0,
+ result_location.m_size_in_bits);
+ /* Trim off leading bits from iter_sval. */
+ sval = mgr->get_or_create_bits_within (NULL_TREE,
+ bits_within_sval,
+ sval);
+ }
+ result_map.insert (result_location, sval);
}
- return mgr->get_or_create_compound_svalue (type, result_map);
+ return mgr->get_or_create_compound_svalue (type, std::move (result_map));
}
/* class conjured_svalue : public svalue. */
diff --git a/gcc/analyzer/svalue.h b/gcc/analyzer/svalue.h
index 72b1542d730e..a3fc41056c45 100644
--- a/gcc/analyzer/svalue.h
+++ b/gcc/analyzer/svalue.h
@@ -1402,15 +1402,13 @@ template <> struct default_hash_traits<widening_svalue::key_t>
namespace ana {
/* Concrete subclass of svalue representing a mapping of bit-ranges
- to svalues, analogous to a cluster within the store.
+ to svalues, analogous to a cluster within the store, but without
+ symbolic keys.
This is for use in places where we want to represent a store-like
mapping, but are required to use an svalue, such as when handling
compound assignments and compound return values.
- All keys within the underlying binding_map are required to be concrete,
- not symbolic.
-
Instances of this class shouldn't be bound as-is into the store;
instead they should be unpacked. Similarly, they should not be
nested. */
@@ -1418,15 +1416,15 @@ namespace ana {
class compound_svalue : public svalue
{
public:
- typedef binding_map::const_iterator_t const_iterator_t;
- typedef binding_map::iterator_t iterator_t;
+ typedef concrete_binding_map::const_iterator const_iterator_t;
+ typedef concrete_binding_map::iterator iterator_t;
/* A support class for uniquifying instances of compound_svalue.
- Note that to avoid copies, keys store pointers to binding_maps,
- rather than the maps themselves. */
+ Note that to avoid copies, keys store pointers to
+ concrete_binding_map, rather than the maps themselves. */
struct key_t
{
- key_t (tree type, const binding_map *map_ptr)
+ key_t (tree type, const concrete_binding_map *map_ptr)
: m_type (type), m_map_ptr (map_ptr)
{}
@@ -1450,10 +1448,11 @@ public:
bool is_empty () const { return m_type == reinterpret_cast<tree> (2); }
tree m_type;
- const binding_map *m_map_ptr;
+ const concrete_binding_map *m_map_ptr;
};
- compound_svalue (symbol::id_t id, tree type, const binding_map &map);
+ compound_svalue (symbol::id_t id, tree type, concrete_binding_map &&map);
+ compound_svalue (symbol::id_t id, tree type, const concrete_binding_map &map);
enum svalue_kind get_kind () const final override { return SK_COMPOUND; }
const compound_svalue *dyn_cast_compound_svalue () const final override
@@ -1471,7 +1470,8 @@ public:
void accept (visitor *v) const final override;
- const binding_map &get_map () const { return m_map; }
+ const concrete_binding_map &
+ get_concrete_bindings () const { return m_map; }
const_iterator_t begin () const { return m_map.begin (); }
const_iterator_t end () const { return m_map.end (); }
@@ -1489,9 +1489,7 @@ public:
region_model_manager *mgr) const final override;
private:
- static complexity calc_complexity (const binding_map &map);
-
- binding_map m_map;
+ concrete_binding_map m_map;
};
} // namespace ana
More information about the Gcc-cvs
mailing list