@@ -46,6 +46,8 @@ class svalue;
class unaryop_svalue;
class binop_svalue;
class sub_svalue;
+ class repeated_svalue;
+ class bits_within_svalue;
class unmergeable_svalue;
class placeholder_svalue;
class widening_svalue;
@@ -60,6 +62,7 @@ class region;
class symbolic_region;
class element_region;
class offset_region;
+ class sized_region;
class cast_region;
class field_region;
class string_region;
@@ -147,6 +150,8 @@ typedef offset_int byte_size_t;
extern bool int_size_in_bits (const_tree type, bit_size_t *out);
+extern tree get_field_at_bit_offset (tree record_type, bit_offset_t bit_offset);
+
/* The location of a region expressesd as an offset relative to a
base region. */
@@ -2275,6 +2275,7 @@ exploded_graph::get_or_create_node (const program_point &point,
if (pruned_state.can_merge_with_p (existing_state, point,
&merged_state))
{
+ merged_state.validate (m_ext_state);
if (logger)
logger->log ("merging new state with that of EN: %i",
existing_enode->m_index);
@@ -2794,6 +2795,7 @@ maybe_process_run_of_before_supernode_enodes (exploded_node *enode)
items.quick_push (it);
const program_state &state = iter_enode->get_state ();
program_state *next_state = &it->m_processed_state;
+ next_state->validate (m_ext_state);
const program_point &iter_point = iter_enode->get_point ();
if (const superedge *iter_sedge = iter_point.get_from_edge ())
{
@@ -2807,6 +2809,7 @@ maybe_process_run_of_before_supernode_enodes (exploded_node *enode)
next_state->m_region_model->update_for_phis
(snode, last_cfg_superedge, &ctxt);
}
+ next_state->validate (m_ext_state);
}
/* Attempt to partition the items into a set of merged states.
@@ -2823,10 +2826,12 @@ maybe_process_run_of_before_supernode_enodes (exploded_node *enode)
unsigned iter_merger_idx;
FOR_EACH_VEC_ELT (merged_states, iter_merger_idx, merged_state)
{
+ merged_state->validate (m_ext_state);
program_state merge (m_ext_state);
if (it_state.can_merge_with_p (*merged_state, next_point, &merge))
{
*merged_state = merge;
+ merged_state->validate (m_ext_state);
it->m_merger_idx = iter_merger_idx;
if (logger)
logger->log ("reusing merger state %i for item %i (EN: %i)",
@@ -1142,6 +1142,7 @@ program_state::validate (const extrinsic_state &ext_state) const
#endif
gcc_assert (m_checker_states.length () == ext_state.get_num_checkers ());
+ m_region_model->validate ();
}
static void
@@ -389,36 +389,15 @@ region_model::impl_call_memset (const call_details &cd)
const region *dest_reg = deref_rvalue (dest_sval, cd.get_arg_tree (0),
cd.get_ctxt ());
- if (tree num_bytes = num_bytes_sval->maybe_get_constant ())
- {
- /* "memset" of zero size is a no-op. */
- if (zerop (num_bytes))
- return true;
-
- /* Set with known amount. */
- byte_size_t reg_size;
- if (dest_reg->get_byte_size (®_size))
- {
- /* Check for an exact size match. */
- if (reg_size == wi::to_offset (num_bytes))
- {
- if (tree cst = fill_value_sval->maybe_get_constant ())
- {
- if (zerop (cst))
- {
- zero_fill_region (dest_reg);
- return true;
- }
- }
- }
- }
- }
-
- check_for_writable_region (dest_reg, cd.get_ctxt ());
-
- /* Otherwise, mark region's contents as unknown. */
- mark_region_as_unknown (dest_reg, cd.get_uncertainty ());
- return false;
+ const svalue *fill_value_u8
+ = m_mgr->get_or_create_cast (unsigned_char_type_node, fill_value_sval);
+
+ const region *sized_dest_reg = m_mgr->get_sized_region (dest_reg,
+ NULL_TREE,
+ num_bytes_sval);
+ check_for_writable_region (sized_dest_reg, cd.get_ctxt ());
+ fill_region (sized_dest_reg, fill_value_u8);
+ return true;
}
/* Handle the on_call_pre part of "operator new". */
@@ -477,7 +477,7 @@ maybe_undo_optimize_bit_field_compare (tree type,
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, BK_direct);
+ = get_store_manager ()->get_concrete_binding (bound_bits);
const svalue *sval = map.get (conc);
if (!sval)
return NULL;
@@ -686,13 +686,13 @@ region_model_manager::maybe_fold_sub_svalue (tree type,
return get_or_create_cast (type, char_sval);
}
- /* SUB(INIT(r)).FIELD -> INIT(r.FIELD)
- i.e.
- Subvalue(InitialValue(R1), FieldRegion(R2, F))
- -> InitialValue(FieldRegion(R1, F)). */
if (const initial_svalue *init_sval
- = parent_svalue->dyn_cast_initial_svalue ())
+ = parent_svalue->dyn_cast_initial_svalue ())
{
+ /* SUB(INIT(r)).FIELD -> INIT(r.FIELD)
+ i.e.
+ Subvalue(InitialValue(R1), FieldRegion(R2, F))
+ -> InitialValue(FieldRegion(R1, F)). */
if (const field_region *field_reg = subregion->dyn_cast_field_region ())
{
const region *field_reg_new
@@ -700,8 +700,24 @@ region_model_manager::maybe_fold_sub_svalue (tree type,
field_reg->get_field ());
return get_or_create_initial_value (field_reg_new);
}
+ /* SUB(INIT(r)[ELEMENT] -> INIT(e[ELEMENT])
+ i.e.
+ Subvalue(InitialValue(R1), ElementRegion(R2, IDX))
+ -> InitialValue(ElementRegion(R1, IDX)). */
+ if (const element_region *element_reg = subregion->dyn_cast_element_region ())
+ {
+ const region *element_reg_new
+ = get_element_region (init_sval->get_region (),
+ element_reg->get_type (),
+ element_reg->get_index ());
+ return get_or_create_initial_value (element_reg_new);
+ }
}
+ if (const repeated_svalue *repeated_sval
+ = parent_svalue->dyn_cast_repeated_svalue ())
+ return get_or_create_cast (type, repeated_sval->get_inner_svalue ());
+
return NULL;
}
@@ -727,6 +743,255 @@ region_model_manager::get_or_create_sub_svalue (tree type,
return sub_sval;
}
+/* Subroutine of region_model_manager::get_or_create_repeated_svalue.
+ Return a folded svalue, or NULL. */
+
+const svalue *
+region_model_manager::maybe_fold_repeated_svalue (tree type,
+ const svalue *outer_size,
+ const svalue *inner_svalue)
+{
+ /* If INNER_SVALUE is the same size as OUTER_SIZE,
+ turn into simply a cast. */
+ if (tree cst_outer_num_bytes = outer_size->maybe_get_constant ())
+ {
+ HOST_WIDE_INT num_bytes_inner_svalue
+ = int_size_in_bytes (inner_svalue->get_type ());
+ if (num_bytes_inner_svalue != -1)
+ if (num_bytes_inner_svalue
+ == (HOST_WIDE_INT)tree_to_uhwi (cst_outer_num_bytes))
+ {
+ if (type)
+ return get_or_create_cast (type, inner_svalue);
+ else
+ return inner_svalue;
+ }
+ }
+
+ /* Handle zero-fill of a specific type. */
+ if (tree cst = inner_svalue->maybe_get_constant ())
+ if (zerop (cst) && type)
+ return get_or_create_cast (type, inner_svalue);
+
+ return NULL;
+}
+
+/* Return the svalue * of type TYPE in which INNER_SVALUE is repeated
+ enough times to be of size OUTER_SIZE, creating it if necessary.
+ e.g. for filling buffers with a constant value. */
+
+const svalue *
+region_model_manager::get_or_create_repeated_svalue (tree type,
+ const svalue *outer_size,
+ const svalue *inner_svalue)
+{
+ if (const svalue *folded
+ = maybe_fold_repeated_svalue (type, outer_size, inner_svalue))
+ return folded;
+
+ repeated_svalue::key_t key (type, outer_size, inner_svalue);
+ if (repeated_svalue **slot = m_repeated_values_map.get (key))
+ return *slot;
+ repeated_svalue *repeated_sval
+ = new repeated_svalue (type, outer_size, inner_svalue);
+ RETURN_UNKNOWN_IF_TOO_COMPLEX (repeated_sval);
+ m_repeated_values_map.put (key, repeated_sval);
+ return repeated_sval;
+}
+
+/* Attempt to get the bit_range for FIELD within a RECORD_TYPE.
+ Return true and write the result to OUT if successful.
+ Return false otherwise. */
+
+static bool
+get_bit_range_for_field (tree field, bit_range *out)
+{
+ bit_size_t bit_size;
+ if (!int_size_in_bits (TREE_TYPE (field), &bit_size))
+ return false;
+ int field_bit_offset = int_bit_position (field);
+ *out = bit_range (field_bit_offset, bit_size);
+ return true;
+}
+
+/* Attempt to get the byte_range for FIELD within a RECORD_TYPE.
+ Return true and write the result to OUT if successful.
+ Return false otherwise. */
+
+static bool
+get_byte_range_for_field (tree field, byte_range *out)
+{
+ bit_range field_bits (0, 0);
+ if (!get_bit_range_for_field (field, &field_bits))
+ return false;
+ return field_bits.as_byte_range (out);
+}
+
+/* Attempt to determine if there is a specific field within RECORD_TYPE
+ at BYTES. If so, return it, and write the location of BYTES relative
+ to the field to *OUT_RANGE_WITHIN_FIELD.
+ Otherwise, return NULL_TREE.
+ For example, given:
+ struct foo { uint32 a; uint32; b};
+ and
+ bytes = {bytes 6-7} (of foo)
+ we have bytes 3-4 of field b. */
+
+static tree
+get_field_at_byte_range (tree record_type, const byte_range &bytes,
+ byte_range *out_range_within_field)
+{
+ bit_offset_t bit_offset = bytes.m_start_byte_offset * BITS_PER_UNIT;
+
+ tree field = get_field_at_bit_offset (record_type, bit_offset);
+ if (!field)
+ return NULL_TREE;
+
+ byte_range field_bytes (0,0);
+ if (!get_byte_range_for_field (field, &field_bytes))
+ return NULL_TREE;
+
+ /* Is BYTES fully within field_bytes? */
+ byte_range bytes_within_field (0,0);
+ if (!field_bytes.contains_p (bytes, &bytes_within_field))
+ return NULL_TREE;
+
+ *out_range_within_field = bytes_within_field;
+ return field;
+}
+
+/* Subroutine of region_model_manager::get_or_create_bits_within.
+ Return a folded svalue, or NULL. */
+
+const svalue *
+region_model_manager::maybe_fold_bits_within_svalue (tree type,
+ const bit_range &bits,
+ const svalue *inner_svalue)
+{
+ tree inner_type = inner_svalue->get_type ();
+ /* Fold:
+ BITS_WITHIN ((0, sizeof (VAL), VAL))
+ to:
+ CAST(TYPE, VAL). */
+ if (bits.m_start_bit_offset == 0 && inner_type)
+ {
+ bit_size_t inner_type_size;
+ if (int_size_in_bits (inner_type, &inner_type_size))
+ if (inner_type_size == bits.m_size_in_bits)
+ {
+ if (type)
+ return get_or_create_cast (type, inner_svalue);
+ else
+ return inner_svalue;
+ }
+ }
+
+ /* Kind-specific folding. */
+ if (const svalue *sval
+ = inner_svalue->maybe_fold_bits_within (type, bits, this))
+ return sval;
+
+ byte_range bytes (0,0);
+ if (bits.as_byte_range (&bytes) && inner_type)
+ switch (TREE_CODE (inner_type))
+ {
+ default:
+ break;
+ case ARRAY_TYPE:
+ {
+ /* Fold:
+ BITS_WITHIN (range, KIND(REG))
+ to:
+ BITS_WITHIN (range - offsetof(ELEMENT), KIND(REG.ELEMENT))
+ if range1 is a byte-range fully within one ELEMENT. */
+ tree element_type = TREE_TYPE (inner_type);
+ HOST_WIDE_INT element_byte_size
+ = int_size_in_bytes (element_type);
+ if (element_byte_size > 0)
+ {
+ HOST_WIDE_INT start_idx
+ = (bytes.get_start_byte_offset ().to_shwi ()
+ / element_byte_size);
+ HOST_WIDE_INT last_idx
+ = (bytes.get_last_byte_offset ().to_shwi ()
+ / element_byte_size);
+ if (start_idx == last_idx)
+ {
+ if (const initial_svalue *initial_sval
+ = inner_svalue->dyn_cast_initial_svalue ())
+ {
+ bit_offset_t start_of_element
+ = start_idx * element_byte_size * BITS_PER_UNIT;
+ bit_range bits_within_element
+ (bits.m_start_bit_offset - start_of_element,
+ bits.m_size_in_bits);
+ const svalue *idx_sval
+ = get_or_create_int_cst (integer_type_node, start_idx);
+ const region *element_reg =
+ get_element_region (initial_sval->get_region (),
+ element_type, idx_sval);
+ const svalue *element_reg_sval
+ = get_or_create_initial_value (element_reg);
+ return get_or_create_bits_within (type,
+ bits_within_element,
+ element_reg_sval);
+ }
+ }
+ }
+ }
+ break;
+ case RECORD_TYPE:
+ {
+ /* Fold:
+ BYTES_WITHIN (range, KIND(REG))
+ to:
+ BYTES_WITHIN (range - offsetof(FIELD), KIND(REG.FIELD))
+ if range1 is fully within FIELD. */
+ byte_range bytes_within_field (0, 0);
+ if (tree field = get_field_at_byte_range (inner_type, bytes,
+ &bytes_within_field))
+ {
+ if (const initial_svalue *initial_sval
+ = inner_svalue->dyn_cast_initial_svalue ())
+ {
+ const region *field_reg =
+ get_field_region (initial_sval->get_region (), field);
+ const svalue *initial_reg_sval
+ = get_or_create_initial_value (field_reg);
+ return get_or_create_bits_within
+ (type,
+ bytes_within_field.as_bit_range (),
+ initial_reg_sval);
+ }
+ }
+ }
+ break;
+ }
+ return NULL;
+}
+
+/* Return the svalue * of type TYPE for extracting BITS from INNER_SVALUE,
+ creating it if necessary. */
+
+const svalue *
+region_model_manager::get_or_create_bits_within (tree type,
+ const bit_range &bits,
+ const svalue *inner_svalue)
+{
+ if (const svalue *folded
+ = maybe_fold_bits_within_svalue (type, bits, inner_svalue))
+ return folded;
+
+ bits_within_svalue::key_t key (type, bits, inner_svalue);
+ if (bits_within_svalue **slot = m_bits_within_values_map.get (key))
+ return *slot;
+ bits_within_svalue *bits_within_sval
+ = new bits_within_svalue (type, bits, inner_svalue);
+ RETURN_UNKNOWN_IF_TOO_COMPLEX (bits_within_sval);
+ m_bits_within_values_map.put (key, bits_within_sval);
+ return bits_within_sval;
+}
+
/* Return the svalue * that decorates ARG as being unmergeable,
creating it if necessary. */
@@ -966,6 +1231,38 @@ region_model_manager::get_offset_region (const region *parent,
return offset_reg;
}
+/* Return the region that describes accessing the subregion of type
+ TYPE of size BYTE_SIZE_SVAL within PARENT, creating it if necessary. */
+
+const region *
+region_model_manager::get_sized_region (const region *parent,
+ tree type,
+ const svalue *byte_size_sval)
+{
+ if (byte_size_sval->get_type () != size_type_node)
+ byte_size_sval = get_or_create_cast (size_type_node, byte_size_sval);
+
+ /* If PARENT is already that size, return it. */
+ const svalue *parent_byte_size_sval = parent->get_byte_size_sval (this);
+ if (tree parent_size_cst = parent_byte_size_sval->maybe_get_constant ())
+ if (tree size_cst = byte_size_sval->maybe_get_constant ())
+ {
+ tree comparison
+ = fold_binary (EQ_EXPR, boolean_type_node, parent_size_cst, size_cst);
+ if (comparison == boolean_true_node)
+ return parent;
+ }
+
+ sized_region::key_t key (parent, type, byte_size_sval);
+ if (sized_region *reg = m_sized_regions.get (key))
+ return reg;
+
+ sized_region *sized_reg
+ = new sized_region (alloc_region_id (), parent, type, byte_size_sval);
+ m_sized_regions.put (key, sized_reg);
+ return sized_reg;
+}
+
/* Return the region that describes accessing PARENT_REGION as if
it were of type TYPE, creating it if necessary. */
@@ -1180,6 +1477,9 @@ region_model_manager::log_stats (logger *logger, bool show_objs) const
log_uniq_map (logger, show_objs, "unaryop_svalue", m_unaryop_values_map);
log_uniq_map (logger, show_objs, "binop_svalue", m_binop_values_map);
log_uniq_map (logger, show_objs, "sub_svalue", m_sub_values_map);
+ log_uniq_map (logger, show_objs, "repeated_svalue", m_repeated_values_map);
+ log_uniq_map (logger, show_objs, "bits_within_svalue",
+ m_bits_within_values_map);
log_uniq_map (logger, show_objs, "unmergeable_svalue",
m_unmergeable_values_map);
log_uniq_map (logger, show_objs, "widening_svalue", m_widening_values_map);
@@ -1198,6 +1498,7 @@ region_model_manager::log_stats (logger *logger, bool show_objs) const
log_uniq_map (logger, show_objs, "field_region", m_field_regions);
log_uniq_map (logger, show_objs, "element_region", m_element_regions);
log_uniq_map (logger, show_objs, "offset_region", m_offset_regions);
+ log_uniq_map (logger, show_objs, "sized_region", m_sized_regions);
log_uniq_map (logger, show_objs, "cast_region", m_cast_regions);
log_uniq_map (logger, show_objs, "frame_region", m_frame_regions);
log_uniq_map (logger, show_objs, "symbolic_region", m_symbolic_regions);
@@ -393,6 +393,14 @@ region_model::debug () const
dump (true);
}
+/* Assert that this object is valid. */
+
+void
+region_model::validate () const
+{
+ m_store.validate ();
+}
+
/* Canonicalize the store and constraints, to maximize the chance of
equality between region_model instances. */
@@ -847,11 +855,9 @@ region_model::on_assignment (const gassign *assign, region_model_context *ctxt)
case STRING_CST:
{
/* e.g. "struct s2 x = {{'A', 'B', 'C', 'D'}};". */
- /* Add a default binding, rather than a direct one, so that array
- access will "inherit" the individual chars. */
const svalue *rhs_sval = get_rvalue (rhs1, ctxt);
m_store.set_value (m_mgr->get_store_manager(), lhs_reg, rhs_sval,
- BK_default, ctxt ? ctxt->get_uncertainty () : NULL);
+ ctxt ? ctxt->get_uncertainty () : NULL);
}
break;
}
@@ -1662,8 +1668,7 @@ region_model::get_initial_value_for_global (const region *reg) const
{
/* Get the value for REG within base_reg_init. */
binding_cluster c (base_reg);
- c.bind (m_mgr->get_store_manager (), base_reg, base_reg_init,
- BK_direct);
+ c.bind (m_mgr->get_store_manager (), base_reg, base_reg_init);
const svalue *sval
= c.get_any_binding (m_mgr->get_store_manager (), reg);
if (sval)
@@ -1854,45 +1859,7 @@ region_model::get_rvalue_for_bits (tree type,
const bit_range &bits) const
{
const svalue *sval = get_store_value (reg);
- if (const compound_svalue *compound_sval = sval->dyn_cast_compound_svalue ())
- {
- const binding_map &map = compound_sval->get_map ();
- binding_map result_map;
- for (auto iter : map)
- {
- const binding_key *key = iter.first;
- if (const concrete_binding *conc_key
- = key->dyn_cast_concrete_binding ())
- {
- /* Ignore concrete bindings outside BITS. */
- if (!conc_key->get_bit_range ().intersects_p (bits))
- continue;
- if ((conc_key->get_start_bit_offset ()
- < bits.get_start_bit_offset ())
- || (conc_key->get_next_bit_offset ()
- > bits.get_next_bit_offset ()))
- {
- /* If we have any concrete keys that aren't fully within BITS,
- then bail out. */
- return m_mgr->get_or_create_unknown_svalue (type);
- }
- const concrete_binding *offset_conc_key
- = m_mgr->get_store_manager ()->get_concrete_binding
- (conc_key->get_start_bit_offset ()
- - bits.get_start_bit_offset (),
- conc_key->get_size_in_bits (),
- conc_key->get_kind ());
- const svalue *sval = iter.second;
- result_map.put (offset_conc_key, sval);
- }
- else
- /* If we have any symbolic keys we can't get it as bits. */
- return m_mgr->get_or_create_unknown_svalue (type);
- }
- return m_mgr->get_or_create_compound_svalue (type, result_map);
- }
-
- return m_mgr->get_or_create_unknown_svalue (type);
+ return m_mgr->get_or_create_bits_within (type, bits, sval);
}
/* A subclass of pending_diagnostic for complaining about writes to
@@ -2035,6 +2002,10 @@ region_model::get_capacity (const region *reg) const
}
}
break;
+ case RK_SIZED:
+ /* Look through sized regions to get at the capacity
+ of the underlying regions. */
+ return get_capacity (reg->get_parent_region ());
}
if (const svalue *recorded = get_dynamic_extents (reg))
@@ -2056,7 +2027,7 @@ region_model::set_value (const region *lhs_reg, const svalue *rhs_sval,
check_for_writable_region (lhs_reg, ctxt);
m_store.set_value (m_mgr->get_store_manager(), lhs_reg, rhs_sval,
- BK_direct, ctxt ? ctxt->get_uncertainty () : NULL);
+ ctxt ? ctxt->get_uncertainty () : NULL);
}
/* Set the value of the region given by LHS to the value given by RHS. */
@@ -2087,6 +2058,14 @@ region_model::purge_region (const region *reg)
m_store.purge_region (m_mgr->get_store_manager(), reg);
}
+/* Fill REG with SVAL. */
+
+void
+region_model::fill_region (const region *reg, const svalue *sval)
+{
+ m_store.fill_region (m_mgr->get_store_manager(), reg, sval);
+}
+
/* Zero-fill REG. */
void
@@ -2711,6 +2690,9 @@ region_model::get_representative_path_var_1 (const region *reg,
parent_pv.m_stack_depth);
}
+ case RK_SIZED:
+ return path_var (NULL_TREE, 0);
+
case RK_CAST:
{
path_var parent_pv
@@ -212,6 +212,8 @@ public:
virtual void visit_unaryop_svalue (const unaryop_svalue *) {}
virtual void visit_binop_svalue (const binop_svalue *) {}
virtual void visit_sub_svalue (const sub_svalue *) {}
+ virtual void visit_repeated_svalue (const repeated_svalue *) {}
+ virtual void visit_bits_within_svalue (const bits_within_svalue *) {}
virtual void visit_unmergeable_svalue (const unmergeable_svalue *) {}
virtual void visit_placeholder_svalue (const placeholder_svalue *) {}
virtual void visit_widening_svalue (const widening_svalue *) {}
@@ -255,6 +257,12 @@ public:
const svalue *get_or_create_sub_svalue (tree type,
const svalue *parent_svalue,
const region *subregion);
+ const svalue *get_or_create_repeated_svalue (tree type,
+ const svalue *outer_size,
+ const svalue *inner_svalue);
+ const svalue *get_or_create_bits_within (tree type,
+ const bit_range &bits,
+ const svalue *inner_svalue);
const svalue *get_or_create_unmergeable (const svalue *arg);
const svalue *get_or_create_widening_svalue (tree type,
const program_point &point,
@@ -286,6 +294,9 @@ public:
const region *get_offset_region (const region *parent,
tree type,
const svalue *byte_offset);
+ const region *get_sized_region (const region *parent,
+ tree type,
+ const svalue *byte_size_sval);
const region *get_cast_region (const region *original_region,
tree type);
const frame_region *get_frame_region (const frame_region *calling_frame,
@@ -321,6 +332,12 @@ private:
const svalue *maybe_fold_sub_svalue (tree type,
const svalue *parent_svalue,
const region *subregion);
+ const svalue *maybe_fold_repeated_svalue (tree type,
+ const svalue *outer_size,
+ const svalue *inner_svalue);
+ const svalue *maybe_fold_bits_within_svalue (tree type,
+ const bit_range &bits,
+ const svalue *inner_svalue);
const svalue *maybe_undo_optimize_bit_field_compare (tree type,
const compound_svalue *compound_sval,
tree cst, const svalue *arg1);
@@ -362,6 +379,14 @@ private:
typedef hash_map<sub_svalue::key_t, sub_svalue *> sub_values_map_t;
sub_values_map_t m_sub_values_map;
+ typedef hash_map<repeated_svalue::key_t,
+ repeated_svalue *> repeated_values_map_t;
+ repeated_values_map_t m_repeated_values_map;
+
+ typedef hash_map<bits_within_svalue::key_t,
+ bits_within_svalue *> bits_within_values_map_t;
+ bits_within_values_map_t m_bits_within_values_map;
+
typedef hash_map<const svalue *,
unmergeable_svalue *> unmergeable_values_map_t;
unmergeable_values_map_t m_unmergeable_values_map;
@@ -402,6 +427,7 @@ private:
consolidation_map<field_region> m_field_regions;
consolidation_map<element_region> m_element_regions;
consolidation_map<offset_region> m_offset_regions;
+ consolidation_map<sized_region> m_sized_regions;
consolidation_map<cast_region> m_cast_regions;
consolidation_map<frame_region> m_frame_regions;
consolidation_map<symbolic_region> m_symbolic_regions;
@@ -575,6 +601,7 @@ class region_model
void set_value (tree lhs, tree rhs, region_model_context *ctxt);
void clobber_region (const region *reg);
void purge_region (const region *reg);
+ void fill_region (const region *reg, const svalue *sval);
void zero_fill_region (const region *reg);
void mark_region_as_unknown (const region *reg, uncertainty_t *uncertainty);
@@ -98,6 +98,7 @@ region::get_base_region () const
case RK_FIELD:
case RK_ELEMENT:
case RK_OFFSET:
+ case RK_SIZED:
iter = iter->get_parent_region ();
continue;
case RK_CAST:
@@ -121,6 +122,7 @@ region::base_region_p () const
case RK_FIELD:
case RK_ELEMENT:
case RK_OFFSET:
+ case RK_SIZED:
case RK_CAST:
return false;
@@ -188,7 +190,8 @@ region::get_offset () const
return *m_cached_offset;
}
-/* If the size of this region (in bytes) is known statically, write it to *OUT
+/* Base class implementation of region::get_byte_size vfunc.
+ If the size of this region (in bytes) is known statically, write it to *OUT
and return true.
Otherwise return false. */
@@ -208,8 +211,29 @@ region::get_byte_size (byte_size_t *out) const
return true;
}
-/* If the size of TYPE (in bits) is constant, write it to *OUT
- and return true.
+/* Base implementation of region::get_byte_size_sval vfunc. */
+
+const svalue *
+region::get_byte_size_sval (region_model_manager *mgr) const
+{
+ tree type = get_type ();
+
+ /* Bail out e.g. for heap-allocated regions. */
+ if (!type)
+ return mgr->get_or_create_unknown_svalue (size_type_node);
+
+ HOST_WIDE_INT bytes = int_size_in_bytes (type);
+ if (bytes == -1)
+ return mgr->get_or_create_unknown_svalue (size_type_node);
+
+ tree byte_size = size_in_bytes (type);
+ if (TREE_TYPE (byte_size) != size_type_node)
+ byte_size = fold_build1 (NOP_EXPR, size_type_node, byte_size);
+ return mgr->get_or_create_constant_svalue (byte_size);
+}
+
+/* Attempt to get the size of TYPE in bits.
+ If successful, return true and write the size to *OUT.
Otherwise return false. */
bool
@@ -249,7 +273,7 @@ region::get_bit_size (bit_size_t *out) const
/* Get the field within RECORD_TYPE at BIT_OFFSET. */
-static tree
+tree
get_field_at_bit_offset (tree record_type, bit_offset_t bit_offset)
{
gcc_assert (TREE_CODE (record_type) == RECORD_TYPE);
@@ -375,18 +399,10 @@ region::calc_offset () const
= (const field_region *)iter_region;
iter_region = iter_region->get_parent_region ();
- /* Compare with e.g. gimple-fold.c's
- fold_nonarray_ctor_reference. */
- tree field = field_reg->get_field ();
- tree byte_offset = DECL_FIELD_OFFSET (field);
- if (TREE_CODE (byte_offset) != INTEGER_CST)
+ bit_offset_t rel_bit_offset;
+ if (!field_reg->get_relative_concrete_offset (&rel_bit_offset))
return region_offset::make_symbolic (iter_region);
- tree field_offset = DECL_FIELD_BIT_OFFSET (field);
- /* Compute bit offset of the field. */
- offset_int bitoffset
- = (wi::to_offset (field_offset)
- + (wi::to_offset (byte_offset) << LOG2_BITS_PER_UNIT));
- accum_bit_offset += bitoffset;
+ accum_bit_offset += rel_bit_offset;
}
continue;
@@ -396,28 +412,10 @@ region::calc_offset () const
= (const element_region *)iter_region;
iter_region = iter_region->get_parent_region ();
- if (tree idx_cst
- = element_reg->get_index ()->maybe_get_constant ())
- {
- gcc_assert (TREE_CODE (idx_cst) == INTEGER_CST);
-
- tree elem_type = element_reg->get_type ();
- offset_int element_idx = wi::to_offset (idx_cst);
-
- /* First, use int_size_in_bytes, to reject the case where we
- have an incomplete type, or a non-constant value. */
- HOST_WIDE_INT hwi_byte_size = int_size_in_bytes (elem_type);
- if (hwi_byte_size > 0)
- {
- offset_int element_bit_size
- = hwi_byte_size << LOG2_BITS_PER_UNIT;
- offset_int element_bit_offset
- = element_idx * element_bit_size;
- accum_bit_offset += element_bit_offset;
- continue;
- }
- }
- return region_offset::make_symbolic (iter_region);
+ bit_offset_t rel_bit_offset;
+ if (!element_reg->get_relative_concrete_offset (&rel_bit_offset))
+ return region_offset::make_symbolic (iter_region);
+ accum_bit_offset += rel_bit_offset;
}
continue;
@@ -427,22 +425,17 @@ region::calc_offset () const
= (const offset_region *)iter_region;
iter_region = iter_region->get_parent_region ();
- if (tree byte_offset_cst
- = offset_reg->get_byte_offset ()->maybe_get_constant ())
- {
- gcc_assert (TREE_CODE (byte_offset_cst) == INTEGER_CST);
- /* Use a signed value for the byte offset, to handle
- negative offsets. */
- HOST_WIDE_INT byte_offset
- = wi::to_offset (byte_offset_cst).to_shwi ();
- HOST_WIDE_INT bit_offset = byte_offset * BITS_PER_UNIT;
- accum_bit_offset += bit_offset;
- }
- else
+ bit_offset_t rel_bit_offset;
+ if (!offset_reg->get_relative_concrete_offset (&rel_bit_offset))
return region_offset::make_symbolic (iter_region);
+ accum_bit_offset += rel_bit_offset;
}
continue;
+ case RK_SIZED:
+ iter_region = iter_region->get_parent_region ();
+ continue;
+
case RK_CAST:
{
const cast_region *cast_reg
@@ -458,6 +451,14 @@ region::calc_offset () const
return region_offset::make_concrete (iter_region, accum_bit_offset);
}
+/* Base implementation of region::get_relative_concrete_offset vfunc. */
+
+bool
+region::get_relative_concrete_offset (bit_offset_t *) const
+{
+ return false;
+}
+
/* Copy from SRC_REG to DST_REG, using CTXT for any issues that occur. */
void
@@ -984,7 +985,7 @@ decl_region::get_svalue_for_initializer (region_model_manager *mgr) const
which can fail if we have a region with unknown size
(e.g. "extern const char arr[];"). */
const binding_key *binding
- = binding_key::make (mgr->get_store_manager (), this, BK_direct);
+ = binding_key::make (mgr->get_store_manager (), this);
if (binding->symbolic_p ())
return NULL;
@@ -1030,6 +1031,26 @@ field_region::dump_to_pp (pretty_printer *pp, bool simple) const
}
}
+/* Implementation of region::get_relative_concrete_offset vfunc
+ for field_region. */
+
+bool
+field_region::get_relative_concrete_offset (bit_offset_t *out) const
+{
+ /* Compare with e.g. gimple-fold.c's
+ fold_nonarray_ctor_reference. */
+ tree byte_offset = DECL_FIELD_OFFSET (m_field);
+ if (TREE_CODE (byte_offset) != INTEGER_CST)
+ return false;
+ tree field_offset = DECL_FIELD_BIT_OFFSET (m_field);
+ /* Compute bit offset of the field. */
+ offset_int bitoffset
+ = (wi::to_offset (field_offset)
+ + (wi::to_offset (byte_offset) << LOG2_BITS_PER_UNIT));
+ *out = bitoffset;
+ return true;
+}
+
/* class element_region : public region. */
/* Implementation of region::accept vfunc for element_region. */
@@ -1067,6 +1088,35 @@ element_region::dump_to_pp (pretty_printer *pp, bool simple) const
}
}
+/* Implementation of region::get_relative_concrete_offset vfunc
+ for element_region. */
+
+bool
+element_region::get_relative_concrete_offset (bit_offset_t *out) const
+{
+ if (tree idx_cst = m_index->maybe_get_constant ())
+ {
+ gcc_assert (TREE_CODE (idx_cst) == INTEGER_CST);
+
+ tree elem_type = get_type ();
+ offset_int element_idx = wi::to_offset (idx_cst);
+
+ /* First, use int_size_in_bytes, to reject the case where we
+ have an incomplete type, or a non-constant value. */
+ HOST_WIDE_INT hwi_byte_size = int_size_in_bytes (elem_type);
+ if (hwi_byte_size > 0)
+ {
+ offset_int element_bit_size
+ = hwi_byte_size << LOG2_BITS_PER_UNIT;
+ offset_int element_bit_offset
+ = element_idx * element_bit_size;
+ *out = element_bit_offset;
+ return true;
+ }
+ }
+ return false;
+}
+
/* class offset_region : public region. */
/* Implementation of region::accept vfunc for offset_region. */
@@ -1103,6 +1153,86 @@ offset_region::dump_to_pp (pretty_printer *pp, bool simple) const
}
}
+/* Implementation of region::get_relative_concrete_offset vfunc
+ for offset_region. */
+
+bool
+offset_region::get_relative_concrete_offset (bit_offset_t *out) const
+{
+ if (tree byte_offset_cst = m_byte_offset->maybe_get_constant ())
+ {
+ gcc_assert (TREE_CODE (byte_offset_cst) == INTEGER_CST);
+ /* Use a signed value for the byte offset, to handle
+ negative offsets. */
+ HOST_WIDE_INT byte_offset
+ = wi::to_offset (byte_offset_cst).to_shwi ();
+ HOST_WIDE_INT bit_offset = byte_offset * BITS_PER_UNIT;
+ *out = bit_offset;
+ return true;
+ }
+ return false;
+}
+
+/* class sized_region : public region. */
+
+/* Implementation of region::accept vfunc for sized_region. */
+
+void
+sized_region::accept (visitor *v) const
+{
+ region::accept (v);
+ m_byte_size_sval->accept (v);
+}
+
+/* Implementation of region::dump_to_pp vfunc for sized_region. */
+
+void
+sized_region::dump_to_pp (pretty_printer *pp, bool simple) const
+{
+ if (simple)
+ {
+ pp_string (pp, "SIZED_REG(");
+ get_parent_region ()->dump_to_pp (pp, simple);
+ pp_string (pp, ", ");
+ m_byte_size_sval->dump_to_pp (pp, simple);
+ pp_string (pp, ")");
+ }
+ else
+ {
+ pp_string (pp, "sized_region(");
+ get_parent_region ()->dump_to_pp (pp, simple);
+ pp_string (pp, ", ");
+ m_byte_size_sval->dump_to_pp (pp, simple);
+ pp_printf (pp, ")");
+ }
+}
+
+/* Implementation of region::get_byte_size vfunc for sized_region. */
+
+bool
+sized_region::get_byte_size (byte_size_t *out) const
+{
+ if (tree cst = m_byte_size_sval->maybe_get_constant ())
+ {
+ gcc_assert (TREE_CODE (cst) == INTEGER_CST);
+ *out = tree_to_uhwi (cst);
+ return true;
+ }
+ return false;
+}
+
+/* Implementation of region::get_bit_size vfunc for sized_region. */
+
+bool
+sized_region::get_bit_size (bit_size_t *out) const
+{
+ byte_size_t byte_size;
+ if (!get_byte_size (&byte_size))
+ return false;
+ *out = byte_size * BITS_PER_UNIT;
+ return true;
+}
+
/* class cast_region : public region. */
/* Implementation of region::accept vfunc for cast_region. */
@@ -43,6 +43,7 @@ enum region_kind
RK_FIELD,
RK_ELEMENT,
RK_OFFSET,
+ RK_SIZED,
RK_CAST,
RK_HEAP_ALLOCATED,
RK_ALLOCA,
@@ -70,6 +71,7 @@ enum region_kind
field_region (RK_FIELD)
element_region (RK_ELEMENT)
offset_region (RK_OFFSET)
+ sized_region (RK_SIZED)
cast_region (RK_CAST)
heap_allocated_region (RK_HEAP_ALLOCATED)
alloca_region (RK_ALLOCA)
@@ -107,6 +109,8 @@ public:
dyn_cast_element_region () const { return NULL; }
virtual const offset_region *
dyn_cast_offset_region () const { return NULL; }
+ virtual const sized_region *
+ dyn_cast_sized_region () const { return NULL; }
virtual const cast_region *
dyn_cast_cast_region () const { return NULL; }
virtual const string_region *
@@ -138,8 +142,25 @@ public:
static int cmp_ptr_ptr (const void *, const void *);
region_offset get_offset () const;
- bool get_byte_size (byte_size_t *out) const;
- bool get_bit_size (bit_size_t *out) const;
+
+ /* Attempt to get the size of this region as a concrete number of bytes.
+ If successful, return true and write the size to *OUT.
+ Otherwise return false. */
+ virtual bool get_byte_size (byte_size_t *out) const;
+
+ /* Attempt to get the size of this region as a concrete number of bits.
+ If successful, return true and write the size to *OUT.
+ Otherwise return false. */
+ virtual bool get_bit_size (bit_size_t *out) const;
+
+ /* Get a symbolic value describing the size of this region in bytes
+ (which could be "unknown"). */
+ virtual const svalue *get_byte_size_sval (region_model_manager *mgr) const;
+
+ /* Attempt to get the offset in bits of this region relative to its parent.
+ If successful, return true and write to *OUT.
+ Otherwise return false. */
+ virtual bool get_relative_concrete_offset (bit_offset_t *out) const;
void
get_subregions_for_binding (region_model_manager *mgr,
@@ -670,6 +691,8 @@ public:
tree get_field () const { return m_field; }
+ bool get_relative_concrete_offset (bit_offset_t *out) const FINAL OVERRIDE;
+
private:
tree m_field;
};
@@ -751,6 +774,9 @@ public:
const svalue *get_index () const { return m_index; }
+ virtual bool
+ get_relative_concrete_offset (bit_offset_t *out) const FINAL OVERRIDE;
+
private:
const svalue *m_index;
};
@@ -833,6 +859,8 @@ public:
const svalue *get_byte_offset () const { return m_byte_offset; }
+ bool get_relative_concrete_offset (bit_offset_t *out) const FINAL OVERRIDE;
+
private:
const svalue *m_byte_offset;
};
@@ -855,6 +883,99 @@ template <> struct default_hash_traits<offset_region::key_t>
namespace ana {
+/* A region that is size BYTES_SIZE_SVAL in size within its parent
+ region (or possibly larger, which would lead to an overflow. */
+
+class sized_region : public region
+{
+public:
+ /* A support class for uniquifying instances of sized_region. */
+ struct key_t
+ {
+ key_t (const region *parent, tree element_type,
+ const svalue *byte_size_sval)
+ : m_parent (parent), m_element_type (element_type),
+ m_byte_size_sval (byte_size_sval)
+ {
+ gcc_assert (byte_size_sval);
+ }
+
+ hashval_t hash () const
+ {
+ inchash::hash hstate;
+ hstate.add_ptr (m_parent);
+ hstate.add_ptr (m_element_type);
+ hstate.add_ptr (m_byte_size_sval);
+ return hstate.end ();
+ }
+
+ bool operator== (const key_t &other) const
+ {
+ return (m_parent == other.m_parent
+ && m_element_type == other.m_element_type
+ && m_byte_size_sval == other.m_byte_size_sval);
+ }
+
+ void mark_deleted () { m_byte_size_sval = reinterpret_cast<const svalue *> (1); }
+ void mark_empty () { m_byte_size_sval = NULL; }
+ bool is_deleted () const
+ {
+ return m_byte_size_sval == reinterpret_cast<const svalue *> (1);
+ }
+ bool is_empty () const { return m_byte_size_sval == NULL; }
+
+ const region *m_parent;
+ tree m_element_type;
+ const svalue *m_byte_size_sval;
+ const svalue *m_end_offset;
+ };
+
+ sized_region (unsigned id, const region *parent, tree type,
+ const svalue *byte_size_sval)
+ : region (complexity::from_pair (parent, byte_size_sval),
+ id, parent, type),
+ m_byte_size_sval (byte_size_sval)
+ {}
+
+ enum region_kind get_kind () const FINAL OVERRIDE { return RK_SIZED; }
+ const sized_region *
+ dyn_cast_sized_region () const FINAL OVERRIDE { return this; }
+
+ void accept (visitor *v) const FINAL OVERRIDE;
+
+ void dump_to_pp (pretty_printer *pp, bool simple) const FINAL OVERRIDE;
+
+ bool get_byte_size (byte_size_t *out) const FINAL OVERRIDE;
+ bool get_bit_size (bit_size_t *out) const FINAL OVERRIDE;
+
+ const svalue *
+ get_byte_size_sval (region_model_manager *) const FINAL OVERRIDE
+ {
+ return m_byte_size_sval;
+ }
+
+private:
+ const svalue *m_byte_size_sval;
+};
+
+} // namespace ana
+
+template <>
+template <>
+inline bool
+is_a_helper <const sized_region *>::test (const region *reg)
+{
+ return reg->get_kind () == RK_SIZED;
+}
+
+template <> struct default_hash_traits<sized_region::key_t>
+: public member_function_hash_traits<sized_region::key_t>
+{
+ static const bool empty_zero_p = true;
+};
+
+namespace ana {
+
/* A region that views another region using a different type. */
class cast_region : public region
@@ -118,52 +118,25 @@ uncertainty_t::dump (bool simple) const
pp_flush (&pp);
}
-/* Get a human-readable string for KIND for dumps. */
-
-const char *binding_kind_to_string (enum binding_kind kind)
-{
- switch (kind)
- {
- default:
- case BK_empty:
- case BK_deleted:
- /* We shouldn't be attempting to print the hash kinds. */
- gcc_unreachable ();
- case BK_direct:
- return "direct";
- case BK_default:
- return "default";
- }
-}
-
/* class binding_key. */
const binding_key *
-binding_key::make (store_manager *mgr, const region *r,
- enum binding_kind kind)
+binding_key::make (store_manager *mgr, const region *r)
{
region_offset offset = r->get_offset ();
if (offset.symbolic_p ())
- return mgr->get_symbolic_binding (r, kind);
+ return mgr->get_symbolic_binding (r);
else
{
bit_size_t bit_size;
if (r->get_bit_size (&bit_size))
return mgr->get_concrete_binding (offset.get_bit_offset (),
- bit_size, kind);
+ bit_size);
else
- return mgr->get_symbolic_binding (r, kind);
+ return mgr->get_symbolic_binding (r);
}
}
-/* Base class implementation of binding_key::dump_to_pp vfunc. */
-
-void
-binding_key::dump_to_pp (pretty_printer *pp, bool /*simple*/) const
-{
- pp_printf (pp, "kind: %s", binding_kind_to_string (m_kind));
-}
-
/* Dump this binding_key to stderr. */
DEBUG_FUNCTION void
@@ -204,11 +177,6 @@ binding_key::cmp_ptrs (const void *p1, const void *p2)
int
binding_key::cmp (const binding_key *k1, const binding_key *k2)
{
- enum binding_kind kind1 = k1->get_kind ();
- enum binding_kind kind2 = k2->get_kind ();
- if (kind1 != kind2)
- return (int)kind1 - (int)kind2;
-
int concrete1 = k1->concrete_p ();
int concrete2 = k2->concrete_p ();
if (int concrete_cmp = concrete1 - concrete2)
@@ -236,7 +204,7 @@ binding_key::cmp (const binding_key *k1, const binding_key *k2)
}
}
-/* struct struct bit_range. */
+/* struct bit_range. */
void
bit_range::dump_to_pp (pretty_printer *pp) const
@@ -267,6 +235,24 @@ bit_range::dump () const
pp_flush (&pp);
}
+/* If OTHER is a subset of this, return true and write
+ to *OUT the relative range of OTHER within this.
+ Otherwise return false. */
+
+bool
+bit_range::contains_p (const bit_range &other, bit_range *out) const
+{
+ if (contains_p (other.get_start_bit_offset ())
+ && contains_p (other.get_last_bit_offset ()))
+ {
+ out->m_start_bit_offset = other.m_start_bit_offset - m_start_bit_offset;
+ out->m_size_in_bits = other.m_size_in_bits;
+ return true;
+ }
+ else
+ return false;
+}
+
int
bit_range::cmp (const bit_range &br1, const bit_range &br2)
{
@@ -371,15 +357,57 @@ byte_range::dump_to_pp (pretty_printer *pp) const
}
}
+/* Dump this object to stderr. */
+
+DEBUG_FUNCTION void
+byte_range::dump () const
+{
+ pretty_printer pp;
+ pp.buffer->stream = stderr;
+ dump_to_pp (&pp);
+ pp_newline (&pp);
+ pp_flush (&pp);
+}
+
+/* If OTHER is a subset of this, return true and write
+ to *OUT the relative range of OTHER within this.
+ Otherwise return false. */
+
+bool
+byte_range::contains_p (const byte_range &other, byte_range *out) const
+{
+ if (contains_p (other.get_start_byte_offset ())
+ && contains_p (other.get_last_byte_offset ()))
+ {
+ out->m_start_byte_offset = other.m_start_byte_offset - m_start_byte_offset;
+ out->m_size_in_bytes = other.m_size_in_bytes;
+ return true;
+ }
+ else
+ return false;
+}
+
+/* qsort comparator for byte ranges. */
+
+int
+byte_range::cmp (const byte_range &br1, const byte_range &br2)
+{
+ /* Order first by offset. */
+ if (int start_cmp = wi::cmps (br1.m_start_byte_offset,
+ br2.m_start_byte_offset))
+ return start_cmp;
+
+ /* ...then by size. */
+ return wi::cmpu (br1.m_size_in_bytes, br2.m_size_in_bytes);
+}
+
/* class concrete_binding : public binding_key. */
/* Implementation of binding_key::dump_to_pp vfunc for concrete_binding. */
void
-concrete_binding::dump_to_pp (pretty_printer *pp, bool simple) const
+concrete_binding::dump_to_pp (pretty_printer *pp, bool) const
{
- binding_key::dump_to_pp (pp, simple);
- pp_string (pp, ", ");
m_bit_range.dump_to_pp (pp);
}
@@ -402,9 +430,6 @@ concrete_binding::cmp_ptr_ptr (const void *p1, const void *p2)
const concrete_binding *b1 = *(const concrete_binding * const *)p1;
const concrete_binding *b2 = *(const concrete_binding * const *)p2;
- if (int kind_cmp = b1->get_kind () - b2->get_kind ())
- return kind_cmp;
-
return bit_range::cmp (b1->m_bit_range, b2->m_bit_range);
}
@@ -413,8 +438,8 @@ concrete_binding::cmp_ptr_ptr (const void *p1, const void *p2)
void
symbolic_binding::dump_to_pp (pretty_printer *pp, bool simple) const
{
- binding_key::dump_to_pp (pp, simple);
- pp_string (pp, ", region: ");
+ //binding_key::dump_to_pp (pp, simple);
+ pp_string (pp, "region: ");
m_region->dump_to_pp (pp, simple);
}
@@ -426,9 +451,6 @@ symbolic_binding::cmp_ptr_ptr (const void *p1, const void *p2)
const symbolic_binding *b1 = *(const symbolic_binding * const *)p1;
const symbolic_binding *b2 = *(const symbolic_binding * const *)p2;
- if (int kind_cmp = b1->get_kind () - b2->get_kind ())
- return kind_cmp;
-
return region::cmp_ids (b1->get_region (), b2->get_region ());
}
@@ -777,8 +799,7 @@ binding_map::apply_ctor_val_to_range (const region *parent_reg,
return false;
bit_offset_t start_bit_offset = min_offset.get_bit_offset ();
store_manager *smgr = mgr->get_store_manager ();
- const binding_key *max_element_key
- = binding_key::make (smgr, max_element, BK_direct);
+ const binding_key *max_element_key = binding_key::make (smgr, max_element);
if (max_element_key->symbolic_p ())
return false;
const concrete_binding *max_element_ckey
@@ -786,8 +807,7 @@ binding_map::apply_ctor_val_to_range (const region *parent_reg,
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,
- BK_direct);
+ = smgr->get_concrete_binding (start_bit_offset, range_size_in_bits);
if (range_key->symbolic_p ())
return false;
@@ -819,8 +839,7 @@ binding_map::apply_ctor_pair_to_child_region (const region *parent_reg,
{
const svalue *sval = get_svalue_for_ctor_val (val, mgr);
const binding_key *k
- = binding_key::make (mgr->get_store_manager (), child_reg,
- BK_direct);
+ = binding_key::make (mgr->get_store_manager (), child_reg);
/* Handle the case where we have an unknown size for child_reg
(e.g. due to it being a trailing field with incomplete array
type. */
@@ -844,7 +863,7 @@ binding_map::apply_ctor_pair_to_child_region (const region *parent_reg,
- parent_base_offset.get_bit_offset ());
/* Create a concrete key for the child within the parent. */
k = mgr->get_store_manager ()->get_concrete_binding
- (child_parent_offset, sval_bit_size, BK_direct);
+ (child_parent_offset, sval_bit_size);
}
gcc_assert (k->concrete_p ());
put (k, sval);
@@ -852,6 +871,166 @@ binding_map::apply_ctor_pair_to_child_region (const region *parent_reg,
}
}
+/* Populate OUT with all bindings within this map that overlap KEY. */
+
+void
+binding_map::get_overlapping_bindings (const binding_key *key,
+ auto_vec<const binding_key *> *out)
+{
+ for (auto iter : *this)
+ {
+ const binding_key *iter_key = iter.first;
+ if (const concrete_binding *ckey
+ = key->dyn_cast_concrete_binding ())
+ {
+ if (const concrete_binding *iter_ckey
+ = iter_key->dyn_cast_concrete_binding ())
+ {
+ if (ckey->overlaps_p (*iter_ckey))
+ out->safe_push (iter_key);
+ }
+ else
+ {
+ /* Assume overlap. */
+ out->safe_push (iter_key);
+ }
+ }
+ else
+ {
+ /* Assume overlap. */
+ out->safe_push (iter_key);
+ }
+ }
+}
+
+/* Remove, truncate, and/or split any bindings within this map that
+ overlap DROP_KEY.
+
+ For example, if we have:
+
+ +------------------------------------+
+ | old binding |
+ +------------------------------------+
+
+ which is to be overwritten with:
+
+ .......+----------------------+.......
+ .......| new binding |.......
+ .......+----------------------+.......
+
+ this function "cuts a hole" out of the old binding:
+
+ +------+......................+------+
+ |prefix| hole for new binding |suffix|
+ +------+......................+------+
+
+ into which the new binding can be added without
+ overlapping the prefix or suffix.
+
+ The prefix and suffix (if added) will be bound to the pertinent
+ parts of the value of the old binding.
+
+ For example, given:
+ struct s5
+ {
+ char arr[8];
+ };
+ void test_5 (struct s5 *p)
+ {
+ struct s5 f = *p;
+ f.arr[3] = 42;
+ }
+ then after the "f = *p;" we have:
+ cluster for: f: INIT_VAL((*INIT_VAL(p_33(D))))
+ and at the "f.arr[3] = 42;" we remove the bindings overlapping
+ "f.arr[3]", replacing it with a prefix (bytes 0-2) and suffix (bytes 4-7)
+ giving:
+ cluster for: f
+ key: {bytes 0-2}
+ value: {BITS_WITHIN(bytes 0-2, inner_val: INIT_VAL((*INIT_VAL(p_33(D))).arr))}
+ key: {bytes 4-7}
+ value: {BITS_WITHIN(bytes 4-7, inner_val: INIT_VAL((*INIT_VAL(p_33(D))).arr))}
+ punching a hole into which the new value can be written at byte 3:
+ cluster for: f
+ key: {bytes 0-2}
+ value: {BITS_WITHIN(bytes 0-2, inner_val: INIT_VAL((*INIT_VAL(p_33(D))).arr))}
+ key: {byte 3}
+ value: 'char' {(char)42}
+ key: {bytes 4-7}
+ value: {BITS_WITHIN(bytes 4-7, inner_val: INIT_VAL((*INIT_VAL(p_33(D))).arr))}
+
+ If UNCERTAINTY is non-NULL, use it to record any svalues that
+ were removed, as being maybe-bound. */
+
+void
+binding_map::remove_overlapping_bindings (store_manager *mgr,
+ const binding_key *drop_key,
+ uncertainty_t *uncertainty)
+{
+ auto_vec<const binding_key *> bindings;
+ get_overlapping_bindings (drop_key, &bindings);
+
+ unsigned i;
+ const binding_key *iter_binding;
+ FOR_EACH_VEC_ELT (bindings, i, iter_binding)
+ {
+ const svalue *old_sval = get (iter_binding);
+ if (uncertainty)
+ uncertainty->on_maybe_bound_sval (old_sval);
+
+ /* Begin by removing the old binding. */
+ m_map.remove (iter_binding);
+
+ /* Now potentially add the prefix and suffix. */
+ if (const concrete_binding *drop_ckey
+ = drop_key->dyn_cast_concrete_binding ())
+ if (const concrete_binding *iter_ckey
+ = iter_binding->dyn_cast_concrete_binding ())
+ {
+ gcc_assert (drop_ckey->overlaps_p (*iter_ckey));
+
+ 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 ());
+ m_map.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 ());
+ m_map.put (suffix_key, suffix_sval);
+ }
+ }
+ }
+}
+
/* class binding_cluster. */
/* binding_cluster's copy ctor. */
@@ -964,6 +1143,27 @@ binding_cluster::dump (bool simple) const
pp_flush (&pp);
}
+/* Assert that this object is valid. */
+
+void
+binding_cluster::validate () const
+{
+ int num_symbolic = 0;
+ int num_concrete = 0;
+ for (auto iter : m_map)
+ {
+ if (iter.first->symbolic_p ())
+ num_symbolic++;
+ else
+ num_concrete++;
+ }
+ /* We shouldn't have more than one symbolic key per cluster
+ (or one would have clobbered the other). */
+ gcc_assert (num_symbolic < 2);
+ /* We can't have both concrete and symbolic keys. */
+ gcc_assert (num_concrete == 0 || num_symbolic == 0);
+}
+
/* Return a new json::object of the form
{"escaped": true/false,
"touched": true/false,
@@ -986,8 +1186,7 @@ binding_cluster::to_json () const
void
binding_cluster::bind (store_manager *mgr,
- const region *reg, const svalue *sval,
- binding_kind kind)
+ const region *reg, const svalue *sval)
{
if (const compound_svalue *compound_sval
= sval->dyn_cast_compound_svalue ())
@@ -996,7 +1195,7 @@ binding_cluster::bind (store_manager *mgr,
return;
}
- const binding_key *binding = binding_key::make (mgr, reg, kind);
+ const binding_key *binding = binding_key::make (mgr, reg);
bind_key (binding, sval);
}
@@ -1045,8 +1244,7 @@ binding_cluster::bind_compound_sval (store_manager *mgr,
+ reg_offset.get_bit_offset ());
const concrete_binding *effective_concrete_key
= mgr->get_concrete_binding (effective_start,
- concrete_key->get_size_in_bits (),
- iter_key->get_kind ());
+ concrete_key->get_size_in_bits ());
bind_key (effective_concrete_key, iter_sval);
}
else
@@ -1069,31 +1267,35 @@ binding_cluster::purge_region (store_manager *mgr, const region *reg)
{
gcc_assert (reg->get_kind () == RK_DECL);
const binding_key *binding
- = binding_key::make (mgr, const_cast<region *> (reg),
- BK_direct);
+ = binding_key::make (mgr, const_cast<region *> (reg));
m_map.remove (binding);
}
-/* Mark REG within this cluster as being filled with zeroes.
- Remove all bindings, add a default binding to zero, and clear the
- TOUCHED flag. */
+/* Clobber REG and fill it with repeated copies of SVAL. */
void
-binding_cluster::zero_fill_region (store_manager *mgr, const region *reg)
+binding_cluster::fill_region (store_manager *mgr,
+ const region *reg,
+ const svalue *sval)
{
clobber_region (mgr, reg);
- /* Add a default binding to zero. */
region_model_manager *sval_mgr = mgr->get_svalue_manager ();
- const svalue *cst_sval
- = sval_mgr->get_or_create_int_cst (integer_type_node, 0);
- const svalue *bound_sval = cst_sval;
- if (reg->get_type ())
- bound_sval = sval_mgr->get_or_create_unaryop (reg->get_type (), NOP_EXPR,
- cst_sval);
- bind (mgr, reg, bound_sval, BK_default);
+ const svalue *byte_size_sval = reg->get_byte_size_sval (sval_mgr);
+ const svalue *fill_sval
+ = sval_mgr->get_or_create_repeated_svalue (reg->get_type (),
+ byte_size_sval, sval);
+ bind (mgr, reg, fill_sval);
+}
+
+/* Clobber REG within this cluster and fill it with zeroes. */
- m_touched = false;
+void
+binding_cluster::zero_fill_region (store_manager *mgr, const region *reg)
+{
+ region_model_manager *sval_mgr = mgr->get_svalue_manager ();
+ const svalue *zero_sval = sval_mgr->get_or_create_int_cst (char_type_node, 0);
+ fill_region (mgr, reg, zero_sval);
}
/* Mark REG within this cluster as being unknown.
@@ -1111,7 +1313,7 @@ binding_cluster::mark_region_as_unknown (store_manager *mgr,
region_model_manager *sval_mgr = mgr->get_svalue_manager ();
const svalue *sval
= sval_mgr->get_or_create_unknown_svalue (reg->get_type ());
- bind (mgr, reg, sval, BK_default);
+ bind (mgr, reg, sval);
}
/* Get any SVAL bound to REG within this cluster via kind KIND,
@@ -1119,10 +1321,9 @@ binding_cluster::mark_region_as_unknown (store_manager *mgr,
const svalue *
binding_cluster::get_binding (store_manager *mgr,
- const region *reg,
- binding_kind kind) const
+ const region *reg) const
{
- const binding_key *reg_binding = binding_key::make (mgr, reg, kind);
+ const binding_key *reg_binding = binding_key::make (mgr, reg);
const svalue *sval = m_map.get (reg_binding);
if (sval)
{
@@ -1140,7 +1341,7 @@ binding_cluster::get_binding (store_manager *mgr,
while (const region *parent_reg = reg->get_parent_region ())
{
const binding_key *parent_reg_binding
- = binding_key::make (mgr, parent_reg, kind);
+ = binding_key::make (mgr, parent_reg);
if (parent_reg_binding == reg_binding
&& sval->get_type ()
&& reg->get_type ()
@@ -1161,7 +1362,7 @@ binding_cluster::get_binding (store_manager *mgr,
FOR_EACH_VEC_ELT_REVERSE (regions, i, iter_reg)
{
region_model_manager *rmm_mgr = mgr->get_svalue_manager ();
- sval = rmm_mgr->get_or_create_sub_svalue (reg->get_type (),
+ sval = rmm_mgr->get_or_create_sub_svalue (iter_reg->get_type (),
sval, iter_reg);
}
}
@@ -1169,21 +1370,20 @@ binding_cluster::get_binding (store_manager *mgr,
return sval;
}
-/* Get any SVAL bound to REG within this cluster via kind KIND,
+/* Get any SVAL bound to REG within this cluster,
either directly for REG, or recursively checking for bindings within
parent regions and extracting subvalues if need be. */
const svalue *
binding_cluster::get_binding_recursive (store_manager *mgr,
- const region *reg,
- enum binding_kind kind) const
+ const region *reg) const
{
- if (const svalue *sval = get_binding (mgr, reg, kind))
+ if (const svalue *sval = get_binding (mgr, reg))
return sval;
if (reg != m_base_region)
if (const region *parent_reg = reg->get_parent_region ())
if (const svalue *parent_sval
- = get_binding_recursive (mgr, parent_reg, kind))
+ = get_binding_recursive (mgr, parent_reg))
{
/* Extract child svalue from parent svalue. */
region_model_manager *rmm_mgr = mgr->get_svalue_manager ();
@@ -1199,18 +1399,11 @@ const svalue *
binding_cluster::get_any_binding (store_manager *mgr,
const region *reg) const
{
- /* Look for a "direct" binding. */
+ /* Look for a direct binding. */
if (const svalue *direct_sval
- = get_binding_recursive (mgr, reg, BK_direct))
+ = get_binding_recursive (mgr, reg))
return direct_sval;
- /* Look for a "default" binding, but not if there's been a symbolic
- write. */
- if (!m_touched)
- if (const svalue *default_sval
- = get_binding_recursive (mgr, reg, BK_default))
- return default_sval;
-
/* If this cluster has been touched by a symbolic write, then the content
of any subregion not currently specifically bound is "UNKNOWN". */
if (m_touched)
@@ -1251,8 +1444,6 @@ const svalue *
binding_cluster::maybe_get_compound_binding (store_manager *mgr,
const region *reg) const
{
- binding_map map;
-
region_offset cluster_offset = m_base_region->get_offset ();
if (cluster_offset.symbolic_p ())
return NULL;
@@ -1260,6 +1451,36 @@ binding_cluster::maybe_get_compound_binding (store_manager *mgr,
if (reg_offset.symbolic_p ())
return NULL;
+ region_model_manager *sval_mgr = mgr->get_svalue_manager ();
+
+ /* We will a build the result map in two parts:
+ (a) result_map, holding the concrete keys from this cluster,
+
+ (b) default_map, holding the initial values for the region
+ (e.g. uninitialized, initializer values, or zero), unless this
+ cluster has been touched.
+
+ We will populate (a), and as we do, clobber (b), trimming and
+ splitting its bindings as necessary.
+ Finally, we will merge (b) into (a), giving a concrete map
+ that merges both the initial values and the bound values from
+ the binding_cluster.
+ Doing it this way reduces N for the O(N^2) intersection-finding,
+ perhaps we should have a spatial-organized data structure for
+ concrete keys, though. */
+
+ binding_map result_map;
+ binding_map default_map;
+
+ /* Set up default values in default_map. */
+ const svalue *default_sval;
+ if (m_touched)
+ default_sval = sval_mgr->get_or_create_unknown_svalue (reg->get_type ());
+ else
+ default_sval = sval_mgr->get_or_create_initial_value (reg);
+ const binding_key *default_key = binding_key::make (mgr, reg);
+ default_map.put (default_key, default_sval);
+
for (map_t::iterator iter = m_map.begin (); iter != m_map.end (); ++iter)
{
const binding_key *key = (*iter).first;
@@ -1268,78 +1489,77 @@ binding_cluster::maybe_get_compound_binding (store_manager *mgr,
if (const concrete_binding *concrete_key
= key->dyn_cast_concrete_binding ())
{
- /* Skip bindings that are outside the bit range of REG. */
- if (concrete_key->get_start_bit_offset ()
- < reg_offset.get_bit_offset ())
- continue;
- bit_size_t reg_bit_size;
- if (reg->get_bit_size (®_bit_size))
- if (concrete_key->get_start_bit_offset ()
- >= reg_offset.get_bit_offset () + reg_bit_size)
- continue;
-
- /* Get offset of KEY relative to REG, rather than to
- the cluster. */
- bit_offset_t relative_start
- = (concrete_key->get_start_bit_offset ()
- - reg_offset.get_bit_offset ());
- const concrete_binding *offset_concrete_key
- = mgr->get_concrete_binding (relative_start,
- concrete_key->get_size_in_bits (),
- key->get_kind ());
- map.put (offset_concrete_key, sval);
- }
- else
- return NULL;
- }
+ const bit_range &bound_range = concrete_key->get_bit_range ();
- if (map.elements () == 0)
- return NULL;
+ bit_size_t reg_bit_size;
+ if (!reg->get_bit_size (®_bit_size))
+ return NULL;
- region_model_manager *sval_mgr = mgr->get_svalue_manager ();
- return sval_mgr->get_or_create_compound_svalue (reg->get_type (), map);
-}
+ bit_range reg_range (reg_offset.get_bit_offset (),
+ reg_bit_size);
+ /* Skip bindings that are outside the bit range of REG. */
+ if (!bound_range.intersects_p (reg_range))
+ continue;
-/* Populate OUT with all bindings within this cluster that overlap REG. */
+ /* We shouldn't have an exact match; that should have been
+ handled already. */
+ gcc_assert (!(reg_range == bound_range));
-void
-binding_cluster::get_overlapping_bindings (store_manager *mgr,
- const region *reg,
- auto_vec<const binding_key *> *out)
-{
- const binding_key *binding
- = binding_key::make (mgr, reg, BK_direct);
- for (map_t::iterator iter = m_map.begin ();
- iter != m_map.end (); ++iter)
- {
- const binding_key *iter_key = (*iter).first;
- if (const concrete_binding *ckey
- = binding->dyn_cast_concrete_binding ())
- {
- if (const concrete_binding *iter_ckey
- = iter_key->dyn_cast_concrete_binding ())
+ bit_range subrange (0, 0);
+ if (reg_range.contains_p (bound_range, &subrange))
{
- if (ckey->overlaps_p (*iter_ckey))
- out->safe_push (iter_key);
+ /* 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);
+
+ /* Clobber default_map, removing/trimming/spliting where
+ it overlaps with offset_concrete_key. */
+ default_map.remove_overlapping_bindings (mgr,
+ offset_concrete_key,
+ NULL);
+ }
+ else if (bound_range.contains_p (reg_range, &subrange))
+ {
+ /* REG is fully within the bound range, but
+ is not equal to it; we're extracting a subvalue. */
+ return sval->extract_bit_range (reg->get_type (),
+ subrange,
+ mgr->get_svalue_manager ());
}
else
{
- /* Assume overlap. */
- out->safe_push (iter_key);
+ /* REG and the bound range partially overlap.
+ We don't handle this case yet. */
+ return NULL;
}
}
else
- {
- /* Assume overlap. */
- out->safe_push (iter_key);
- }
+ /* Can't handle symbolic bindings. */
+ return NULL;
+ }
+
+ if (result_map.elements () == 0)
+ return NULL;
+
+ /* Merge any bindings from default_map into result_map. */
+ for (auto iter : default_map)
+ {
+ const binding_key *key = iter.first;
+ const svalue *sval = iter.second;
+ result_map.put (key, sval);
}
+
+ return sval_mgr->get_or_create_compound_svalue (reg->get_type (), result_map);
}
-/* Remove any bindings within this cluster that overlap REG,
- but retain default bindings that overlap but aren't fully covered
- by REG.
+/* Remove, truncate, and/or split any bindings within this map that
+ overlap REG.
If UNCERTAINTY is non-NULL, use it to record any svalues that
were removed, as being maybe-bound. */
@@ -1348,26 +1568,9 @@ binding_cluster::remove_overlapping_bindings (store_manager *mgr,
const region *reg,
uncertainty_t *uncertainty)
{
- auto_vec<const binding_key *> bindings;
- get_overlapping_bindings (mgr, reg, &bindings);
+ const binding_key *reg_binding = binding_key::make (mgr, reg);
- unsigned i;
- const binding_key *iter_binding;
- FOR_EACH_VEC_ELT (bindings, i, iter_binding)
- {
- /* Don't remove default bindings, unless the default binding
- is fully covered by REG. */
- if (iter_binding->get_kind () == BK_default)
- {
- const binding_key *reg_binding
- = binding_key::make (mgr, reg, BK_default);
- if (reg_binding != iter_binding)
- continue;
- }
- if (uncertainty)
- uncertainty->on_maybe_bound_sval (m_map.get (iter_binding));
- m_map.remove (iter_binding);
- }
+ m_map.remove_overlapping_bindings (mgr, reg_binding, uncertainty);
}
/* Attempt to merge CLUSTER_A and CLUSTER_B into OUT_CLUSTER, using
@@ -1428,6 +1631,8 @@ binding_cluster::can_merge_p (const binding_cluster *cluster_a,
const binding_key *key_b = (*iter_b).first;
keys.add (key_b);
}
+ int num_symbolic_keys = 0;
+ int num_concrete_keys = 0;
for (hash_set<const binding_key *>::iterator iter = keys.begin ();
iter != keys.end (); ++iter)
{
@@ -1435,6 +1640,11 @@ binding_cluster::can_merge_p (const binding_cluster *cluster_a,
const svalue *sval_a = cluster_a->get_any_value (key);
const svalue *sval_b = cluster_b->get_any_value (key);
+ if (key->symbolic_p ())
+ num_symbolic_keys++;
+ else
+ num_concrete_keys++;
+
if (sval_a == sval_b)
{
gcc_assert (sval_a);
@@ -1463,29 +1673,15 @@ binding_cluster::can_merge_p (const binding_cluster *cluster_a,
out_cluster->m_map.put (key, unknown_sval);
}
- /* Handle the case where we get a default binding from one and a direct
- binding from the other. */
- auto_vec<const concrete_binding *> duplicate_keys;
- for (map_t::iterator iter = out_cluster->m_map.begin ();
- iter != out_cluster->m_map.end (); ++iter)
- {
- const concrete_binding *ckey
- = (*iter).first->dyn_cast_concrete_binding ();
- if (!ckey)
- continue;
- if (ckey->get_kind () != BK_direct)
- continue;
- const concrete_binding *def_ckey
- = mgr->get_concrete_binding (ckey->get_start_bit_offset (),
- ckey->get_size_in_bits (),
- BK_default);
- if (out_cluster->m_map.get (def_ckey))
- duplicate_keys.safe_push (def_ckey);
+ /* We can only have at most one symbolic key per cluster,
+ and if we do, we can't have any concrete keys.
+ If this happens, mark the cluster as touched, with no keys. */
+ if (num_symbolic_keys >= 2
+ || (num_concrete_keys > 0 && num_symbolic_keys > 0))
+ {
+ out_cluster->m_touched = true;
+ out_cluster->m_map.empty ();
}
- unsigned i;
- const concrete_binding *key;
- FOR_EACH_VEC_ELT (duplicate_keys, i, key)
- out_cluster->m_map.remove (key);
/* We don't handle other kinds of overlaps yet. */
@@ -1558,7 +1754,7 @@ binding_cluster::on_unknown_fncall (const gcall *call,
const svalue *sval
= mgr->get_svalue_manager ()->get_or_create_conjured_svalue
(m_base_region->get_type (), call, m_base_region);
- bind (mgr, m_base_region, sval, BK_direct);
+ bind (mgr, m_base_region, sval);
m_touched = true;
}
@@ -1665,7 +1861,7 @@ binding_cluster::maybe_get_simple_value (store_manager *mgr) const
if (m_map.elements () != 1)
return NULL;
- const binding_key *key = binding_key::make (mgr, m_base_region, BK_direct);
+ const binding_key *key = binding_key::make (mgr, m_base_region);
return get_any_value (key);
}
@@ -1675,10 +1871,9 @@ binding_cluster::maybe_get_simple_value (store_manager *mgr) const
const concrete_binding *
store_manager::get_concrete_binding (bit_offset_t start_bit_offset,
- bit_offset_t size_in_bits,
- enum binding_kind kind)
+ bit_offset_t size_in_bits)
{
- concrete_binding b (start_bit_offset, size_in_bits, kind);
+ concrete_binding b (start_bit_offset, size_in_bits);
if (concrete_binding *existing = m_concrete_binding_key_mgr.get (b))
return existing;
@@ -1688,10 +1883,9 @@ store_manager::get_concrete_binding (bit_offset_t start_bit_offset,
}
const symbolic_binding *
-store_manager::get_symbolic_binding (const region *reg,
- enum binding_kind kind)
+store_manager::get_symbolic_binding (const region *reg)
{
- symbolic_binding b (reg, kind);
+ symbolic_binding b (reg);
if (symbolic_binding *existing = m_symbolic_binding_key_mgr.get (b))
return existing;
@@ -1952,6 +2146,15 @@ store::dump (bool simple) const
pp_flush (&pp);
}
+/* Assert that this object is valid. */
+
+void
+store::validate () const
+{
+ for (auto iter : m_cluster_map)
+ iter.second->validate ();
+}
+
/* Return a new json::object of the form
{PARENT_REGION_DESC: {BASE_REGION_DESC: object for binding_map,
... for each cluster within parent region},
@@ -2027,7 +2230,7 @@ store::get_any_binding (store_manager *mgr, const region *reg) const
void
store::set_value (store_manager *mgr, const region *lhs_reg,
- const svalue *rhs_sval, enum binding_kind kind,
+ const svalue *rhs_sval,
uncertainty_t *uncertainty)
{
remove_overlapping_bindings (mgr, lhs_reg);
@@ -2054,7 +2257,7 @@ store::set_value (store_manager *mgr, const region *lhs_reg,
else
{
lhs_cluster = get_or_create_cluster (lhs_base_reg);
- lhs_cluster->bind (mgr, lhs_reg, rhs_sval, kind);
+ lhs_cluster->bind (mgr, lhs_reg, rhs_sval);
}
/* Bindings to a cluster can affect other clusters if a symbolic
@@ -2209,16 +2412,26 @@ store::purge_region (store_manager *mgr, const region *reg)
}
}
-/* Zero-fill REG. */
+/* Fill REG with SVAL. */
void
-store::zero_fill_region (store_manager *mgr, const region *reg)
+store::fill_region (store_manager *mgr, const region *reg, const svalue *sval)
{
const region *base_reg = reg->get_base_region ();
if (base_reg->symbolic_for_unknown_ptr_p ())
return;
binding_cluster *cluster = get_or_create_cluster (base_reg);
- cluster->zero_fill_region (mgr, reg);
+ cluster->fill_region (mgr, reg, sval);
+}
+
+/* Zero-fill REG. */
+
+void
+store::zero_fill_region (store_manager *mgr, const region *reg)
+{
+ region_model_manager *sval_mgr = mgr->get_svalue_manager ();
+ const svalue *zero_sval = sval_mgr->get_or_create_int_cst (char_type_node, 0);
+ fill_region (mgr, reg, zero_sval);
}
/* Mark REG as having unknown content. */
@@ -2740,26 +2953,18 @@ test_binding_key_overlap ()
store_manager mgr (NULL);
/* Various 8-bit bindings. */
- const concrete_binding *cb_0_7
- = mgr.get_concrete_binding (0, 8, BK_direct);
- const concrete_binding *cb_8_15
- = mgr.get_concrete_binding (8, 8, BK_direct);
- const concrete_binding *cb_16_23
- = mgr.get_concrete_binding (16, 8, BK_direct);
- const concrete_binding *cb_24_31
- = mgr.get_concrete_binding (24, 8, BK_direct);
+ const concrete_binding *cb_0_7 = mgr.get_concrete_binding (0, 8);
+ const concrete_binding *cb_8_15 = mgr.get_concrete_binding (8, 8);
+ const concrete_binding *cb_16_23 = mgr.get_concrete_binding (16, 8);
+ const concrete_binding *cb_24_31 = mgr.get_concrete_binding (24, 8);
/* 16-bit bindings. */
- const concrete_binding *cb_0_15
- = mgr.get_concrete_binding (0, 16, BK_direct);
- const concrete_binding *cb_8_23
- = mgr.get_concrete_binding (8, 16, BK_direct);
- const concrete_binding *cb_16_31
- = mgr.get_concrete_binding (16, 16, BK_direct);
+ const concrete_binding *cb_0_15 = mgr.get_concrete_binding (0, 16);
+ const concrete_binding *cb_8_23 = mgr.get_concrete_binding (8, 16);
+ const concrete_binding *cb_16_31 = mgr.get_concrete_binding (16, 16);
/* 32-bit binding. */
- const concrete_binding *cb_0_31
- = mgr.get_concrete_binding (0, 32, BK_direct);
+ const concrete_binding *cb_0_31 = mgr.get_concrete_binding (0, 32);
/* Everything should self-overlap. */
ASSERT_OVERLAP (cb_0_7, cb_0_7);
@@ -199,29 +199,6 @@ private:
class byte_range;
class concrete_binding;
-/* An enum for discriminating between "direct" vs "default" levels of
- mapping. */
-
-enum binding_kind
-{
- /* Special-case value for hash support.
- This is the initial entry, so that hash traits can have
- empty_zero_p = true. */
- BK_empty = 0,
-
- /* Special-case value for hash support. */
- BK_deleted,
-
- /* The normal kind of mapping. */
- BK_direct,
-
- /* A lower-priority kind of mapping, for use when inheriting
- default values from a parent region. */
- BK_default
-};
-
-extern const char *binding_kind_to_string (enum binding_kind kind);
-
/* Abstract base class for describing ranges of bits within a binding_map
that can have svalues bound to them. */
@@ -232,10 +209,9 @@ public:
virtual bool concrete_p () const = 0;
bool symbolic_p () const { return !concrete_p (); }
- static const binding_key *make (store_manager *mgr, const region *r,
- enum binding_kind kind);
+ static const binding_key *make (store_manager *mgr, const region *r);
- virtual void dump_to_pp (pretty_printer *pp, bool simple) const;
+ virtual void dump_to_pp (pretty_printer *pp, bool simple) const = 0;
void dump (bool simple) const;
label_text get_desc (bool simple=true) const;
@@ -244,28 +220,6 @@ public:
virtual const concrete_binding *dyn_cast_concrete_binding () const
{ return NULL; }
-
- enum binding_kind get_kind () const { return m_kind; }
-
- void mark_deleted () { m_kind = BK_deleted; }
- void mark_empty () { m_kind = BK_empty; }
- bool is_deleted () const { return m_kind == BK_deleted; }
- bool is_empty () const { return m_kind == BK_empty; }
-
-protected:
- binding_key (enum binding_kind kind) : m_kind (kind) {}
-
- hashval_t impl_hash () const
- {
- return m_kind;
- }
- bool impl_eq (const binding_key &other) const
- {
- return m_kind == other.m_kind;
- }
-
-private:
- enum binding_kind m_kind;
};
/* A concrete range of bits. */
@@ -288,6 +242,10 @@ struct bit_range
{
return m_start_bit_offset + m_size_in_bits;
}
+ bit_offset_t get_last_bit_offset () const
+ {
+ return get_next_bit_offset () - 1;
+ }
bool contains_p (bit_offset_t offset) const
{
@@ -295,6 +253,8 @@ struct bit_range
&& offset < get_next_bit_offset ());
}
+ bool contains_p (const bit_range &other, bit_range *out) const;
+
bool operator== (const bit_range &other) const
{
return (m_start_bit_offset == other.m_start_bit_offset
@@ -327,12 +287,42 @@ struct byte_range
{}
void dump_to_pp (pretty_printer *pp) const;
+ void dump () const;
+
+ bool contains_p (byte_offset_t offset) const
+ {
+ return (offset >= get_start_byte_offset ()
+ && offset < get_next_byte_offset ());
+ }
+ bool contains_p (const byte_range &other, byte_range *out) const;
+
+ bool operator== (const byte_range &other) const
+ {
+ return (m_start_byte_offset == other.m_start_byte_offset
+ && m_size_in_bytes == other.m_size_in_bytes);
+ }
+ byte_offset_t get_start_byte_offset () const
+ {
+ return m_start_byte_offset;
+ }
+ byte_offset_t get_next_byte_offset () const
+ {
+ return m_start_byte_offset + m_size_in_bytes;
+ }
byte_offset_t get_last_byte_offset () const
{
return m_start_byte_offset + m_size_in_bytes - 1;
}
+ bit_range as_bit_range () const
+ {
+ return bit_range (m_start_byte_offset * BITS_PER_UNIT,
+ m_size_in_bytes * BITS_PER_UNIT);
+ }
+
+ static int cmp (const byte_range &br1, const byte_range &br2);
+
byte_offset_t m_start_byte_offset;
byte_size_t m_size_in_bytes;
};
@@ -346,10 +336,8 @@ public:
/* This class is its own key for the purposes of consolidation. */
typedef concrete_binding key_t;
- concrete_binding (bit_offset_t start_bit_offset, bit_size_t size_in_bits,
- enum binding_kind kind)
- : binding_key (kind),
- m_bit_range (start_bit_offset, size_in_bits)
+ concrete_binding (bit_offset_t start_bit_offset, bit_size_t size_in_bits)
+ : m_bit_range (start_bit_offset, size_in_bits)
{}
bool concrete_p () const FINAL OVERRIDE { return true; }
@@ -358,12 +346,10 @@ public:
inchash::hash hstate;
hstate.add_wide_int (m_bit_range.m_start_bit_offset);
hstate.add_wide_int (m_bit_range.m_size_in_bits);
- return hstate.end () ^ binding_key::impl_hash ();
+ return hstate.end ();
}
bool operator== (const concrete_binding &other) const
{
- if (!binding_key::impl_eq (other))
- return false;
return m_bit_range == other.m_bit_range;
}
@@ -392,6 +378,11 @@ public:
static int cmp_ptr_ptr (const void *, const void *);
+ void mark_deleted () { m_bit_range.m_start_bit_offset = -1; }
+ void mark_empty () { m_bit_range.m_start_bit_offset = -2; }
+ bool is_deleted () const { return m_bit_range.m_start_bit_offset == -1; }
+ bool is_empty () const { return m_bit_range.m_start_bit_offset == -2; }
+
private:
bit_range m_bit_range;
};
@@ -401,7 +392,7 @@ private:
template <> struct default_hash_traits<ana::concrete_binding>
: public member_function_hash_traits<ana::concrete_binding>
{
- static const bool empty_zero_p = true;
+ static const bool empty_zero_p = false;
};
namespace ana {
@@ -415,21 +406,16 @@ public:
/* This class is its own key for the purposes of consolidation. */
typedef symbolic_binding key_t;
- symbolic_binding (const region *region, enum binding_kind kind)
- : binding_key (kind),
- m_region (region)
- {}
+ symbolic_binding (const region *region) : m_region (region) {}
bool concrete_p () const FINAL OVERRIDE { return false; }
hashval_t hash () const
{
- return (binding_key::impl_hash () ^ (intptr_t)m_region);
+ return (intptr_t)m_region;
}
bool operator== (const symbolic_binding &other) const
{
- if (!binding_key::impl_eq (other))
- return false;
- return (m_region == other.m_region);
+ return m_region == other.m_region;
}
void dump_to_pp (pretty_printer *pp, bool simple) const FINAL OVERRIDE;
@@ -438,6 +424,12 @@ public:
static int cmp_ptr_ptr (const void *, const void *);
+ void mark_deleted () { m_region = reinterpret_cast<const region *> (1); }
+ void mark_empty () { m_region = NULL; }
+ bool is_deleted () const
+ { return m_region == reinterpret_cast<const region *> (1); }
+ bool is_empty () const { return m_region == NULL; }
+
private:
const region *m_region;
};
@@ -504,7 +496,13 @@ public:
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);
+
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,
@@ -553,22 +551,22 @@ public:
void dump_to_pp (pretty_printer *pp, bool simple, bool multiline) const;
void dump (bool simple) const;
+ void validate () const;
+
json::object *to_json () const;
- void bind (store_manager *mgr, const region *, const svalue *,
- binding_kind kind);
+ void bind (store_manager *mgr, const region *, const svalue *);
void clobber_region (store_manager *mgr, const region *reg);
void purge_region (store_manager *mgr, const region *reg);
+ void fill_region (store_manager *mgr, const region *reg, const svalue *sval);
void zero_fill_region (store_manager *mgr, const region *reg);
void mark_region_as_unknown (store_manager *mgr, const region *reg,
uncertainty_t *uncertainty);
- const svalue *get_binding (store_manager *mgr, const region *reg,
- binding_kind kind) const;
+ const svalue *get_binding (store_manager *mgr, const region *reg) const;
const svalue *get_binding_recursive (store_manager *mgr,
- const region *reg,
- enum binding_kind kind) const;
+ const region *reg) const;
const svalue *get_any_binding (store_manager *mgr,
const region *reg) const;
const svalue *maybe_get_compound_binding (store_manager *mgr,
@@ -630,8 +628,6 @@ public:
private:
const svalue *get_any_value (const binding_key *key) const;
- void get_overlapping_bindings (store_manager *mgr, const region *reg,
- auto_vec<const binding_key *> *out);
void bind_compound_sval (store_manager *mgr,
const region *reg,
const compound_svalue *compound_sval);
@@ -684,6 +680,8 @@ public:
void dump (bool simple) const;
void summarize_to_pp (pretty_printer *pp, bool simple) const;
+ void validate () const;
+
json::object *to_json () const;
const svalue *get_any_binding (store_manager *mgr, const region *reg) const;
@@ -691,10 +689,11 @@ public:
bool called_unknown_fn_p () const { return m_called_unknown_fn; }
void set_value (store_manager *mgr, const region *lhs_reg,
- const svalue *rhs_sval, enum binding_kind kind,
+ const svalue *rhs_sval,
uncertainty_t *uncertainty);
void clobber_region (store_manager *mgr, const region *reg);
void purge_region (store_manager *mgr, const region *reg);
+ void fill_region (store_manager *mgr, const region *reg, const svalue *sval);
void zero_fill_region (store_manager *mgr, const region *reg);
void mark_region_as_unknown (store_manager *mgr, const region *reg,
uncertainty_t *uncertainty);
@@ -773,19 +772,15 @@ public:
/* binding consolidation. */
const concrete_binding *
get_concrete_binding (bit_offset_t start_bit_offset,
- bit_offset_t size_in_bits,
- enum binding_kind kind);
+ bit_offset_t size_in_bits);
const concrete_binding *
- get_concrete_binding (const bit_range &bits,
- enum binding_kind kind)
+ get_concrete_binding (const bit_range &bits)
{
return get_concrete_binding (bits.get_start_bit_offset (),
- bits.m_size_in_bits,
- kind);
+ bits.m_size_in_bits);
}
const symbolic_binding *
- get_symbolic_binding (const region *region,
- enum binding_kind kind);
+ get_symbolic_binding (const region *region);
region_model_manager *get_svalue_manager () const
{
@@ -415,6 +415,27 @@ svalue::cmp_ptr (const svalue *sval1, const svalue *sval2)
sub_sval2->get_subregion ());
}
break;
+ case SK_REPEATED:
+ {
+ const repeated_svalue *repeated_sval1 = (const repeated_svalue *)sval1;
+ const repeated_svalue *repeated_sval2 = (const repeated_svalue *)sval2;
+ return svalue::cmp_ptr (repeated_sval1->get_inner_svalue (),
+ repeated_sval2->get_inner_svalue ());
+ }
+ break;
+ case SK_BITS_WITHIN:
+ {
+ const bits_within_svalue *bits_within_sval1
+ = (const bits_within_svalue *)sval1;
+ const bits_within_svalue *bits_within_sval2
+ = (const bits_within_svalue *)sval2;
+ if (int cmp = bit_range::cmp (bits_within_sval1->get_bits (),
+ bits_within_sval2->get_bits ()))
+ return cmp;
+ return svalue::cmp_ptr (bits_within_sval1->get_inner_svalue (),
+ bits_within_sval2->get_inner_svalue ());
+ }
+ break;
case SK_UNMERGEABLE:
{
const unmergeable_svalue *unmergeable_sval1
@@ -515,6 +536,27 @@ svalue::involves_p (const svalue *other) const
return v.found_p ();
}
+/* Extract SUBRANGE from this value, of type TYPE. */
+
+const svalue *
+svalue::extract_bit_range (tree type,
+ const bit_range &subrange,
+ region_model_manager *mgr) const
+{
+ return mgr->get_or_create_bits_within (type, subrange, this);
+}
+
+/* Base implementation of svalue::maybe_fold_bits_within vfunc. */
+
+const svalue *
+svalue::maybe_fold_bits_within (tree,
+ const bit_range &,
+ region_model_manager *) const
+{
+ /* By default, don't fold. */
+ return NULL;
+}
+
/* class region_svalue : public svalue. */
/* Implementation of svalue::dump_to_pp vfunc for region_svalue. */
@@ -680,6 +722,26 @@ constant_svalue::eval_condition (const constant_svalue *lhs,
return tristate::TS_UNKNOWN;
}
+/* Implementation of svalue::maybe_fold_bits_within vfunc
+ for constant_svalue. */
+
+const svalue *
+constant_svalue::maybe_fold_bits_within (tree type,
+ const bit_range &,
+ region_model_manager *mgr) const
+{
+ /* Bits within an all-zero value are also all zero. */
+ if (zerop (m_cst_expr))
+ {
+ if (type)
+ return mgr->get_or_create_cast (type, this);
+ else
+ return this;
+ }
+ /* Otherwise, don't fold. */
+ return NULL;
+}
+
/* class unknown_svalue : public svalue. */
/* Implementation of svalue::dump_to_pp vfunc for unknown_svalue. */
@@ -711,6 +773,18 @@ unknown_svalue::accept (visitor *v) const
v->visit_unknown_svalue (this);
}
+/* Implementation of svalue::maybe_fold_bits_within vfunc
+ for unknown_svalue. */
+
+const svalue *
+unknown_svalue::maybe_fold_bits_within (tree type,
+ const bit_range &,
+ region_model_manager *mgr) const
+{
+ /* Bits within an unknown_svalue are themselves unknown. */
+ return mgr->get_or_create_unknown_svalue (type);
+}
+
/* Get a string for KIND for use in debug dumps. */
const char *
@@ -892,6 +966,34 @@ unaryop_svalue::implicitly_live_p (const svalue_set *live_svalues,
return get_arg ()->live_p (live_svalues, model);
}
+/* Implementation of svalue::maybe_fold_bits_within vfunc
+ for unaryop_svalue. */
+
+const svalue *
+unaryop_svalue::maybe_fold_bits_within (tree type,
+ const bit_range &,
+ region_model_manager *mgr) const
+{
+ switch (m_op)
+ {
+ default:
+ break;
+ case NOP_EXPR:
+ /* A cast of zero is zero. */
+ if (tree cst = m_arg->maybe_get_constant ())
+ if (zerop (cst))
+ {
+ if (type)
+ return mgr->get_or_create_cast (type, this);
+ else
+ return this;
+ }
+ break;
+ }
+ /* Otherwise, don't fold. */
+ return NULL;
+}
+
/* class binop_svalue : public svalue. */
/* Implementation of svalue::dump_to_pp vfunc for binop_svalue. */
@@ -995,6 +1097,216 @@ sub_svalue::implicitly_live_p (const svalue_set *live_svalues,
return get_parent ()->live_p (live_svalues, model);
}
+/* class repeated_svalue : public svalue. */
+
+/* repeated_svalue'c ctor. */
+
+repeated_svalue::repeated_svalue (tree type,
+ const svalue *outer_size,
+ const svalue *inner_svalue)
+: svalue (complexity::from_pair (outer_size, inner_svalue), type),
+ m_outer_size (outer_size),
+ m_inner_svalue (inner_svalue)
+{
+}
+
+/* Implementation of svalue::dump_to_pp vfunc for repeated_svalue. */
+
+void
+repeated_svalue::dump_to_pp (pretty_printer *pp, bool simple) const
+{
+ if (simple)
+ {
+ pp_string (pp, "REPEATED(");
+ if (get_type ())
+ {
+ print_quoted_type (pp, get_type ());
+ pp_string (pp, ", ");
+ }
+ pp_string (pp, "outer_size: ");
+ m_outer_size->dump_to_pp (pp, simple);
+ pp_string (pp, ", inner_val: ");
+ m_inner_svalue->dump_to_pp (pp, simple);
+ pp_character (pp, ')');
+ }
+ else
+ {
+ pp_string (pp, "repeated_svalue (");
+ if (get_type ())
+ {
+ print_quoted_type (pp, get_type ());
+ pp_string (pp, ", ");
+ }
+ pp_string (pp, "outer_size: ");
+ m_outer_size->dump_to_pp (pp, simple);
+ pp_string (pp, ", inner_val: ");
+ m_inner_svalue->dump_to_pp (pp, simple);
+ pp_character (pp, ')');
+ }
+}
+
+/* Implementation of svalue::accept vfunc for repeated_svalue. */
+
+void
+repeated_svalue::accept (visitor *v) const
+{
+ v->visit_repeated_svalue (this);
+ m_inner_svalue->accept (v);
+}
+
+/* Return true if this value is known to be all zeroes. */
+
+bool
+repeated_svalue::all_zeroes_p () const
+{
+ if (tree cst = m_inner_svalue->maybe_get_constant ())
+ if (zerop (cst))
+ return true;
+ return false;
+}
+
+/* Implementation of svalue::maybe_fold_bits_within vfunc
+ for repeated_svalue. */
+
+const svalue *
+repeated_svalue::maybe_fold_bits_within (tree type,
+ const bit_range &bits,
+ region_model_manager *mgr) const
+{
+ const svalue *innermost_sval = m_inner_svalue;
+ /* Fold
+ BITS_WITHIN (range, REPEATED_SVALUE (ZERO))
+ to:
+ REPEATED_SVALUE (ZERO). */
+ if (all_zeroes_p ())
+ {
+ byte_range bytes (0,0);
+ if (bits.as_byte_range (&bytes))
+ {
+ const svalue *byte_size
+ = mgr->get_or_create_int_cst (size_type_node,
+ bytes.m_size_in_bytes.to_uhwi ());
+ return mgr->get_or_create_repeated_svalue (type, byte_size,
+ innermost_sval);
+ }
+ }
+
+ /* Fold:
+ BITS_WITHIN (range, REPEATED_SVALUE (INNERMOST_SVALUE))
+ to:
+ BITS_WITHIN (range - offset, INNERMOST_SVALUE)
+ if range is fully within one instance of INNERMOST_SVALUE. */
+ if (tree innermost_type = innermost_sval->get_type ())
+ {
+ bit_size_t element_bit_size;
+ if (int_size_in_bits (innermost_type, &element_bit_size)
+ && element_bit_size > 0)
+ {
+ HOST_WIDE_INT start_idx
+ = (bits.get_start_bit_offset ()
+ / element_bit_size).to_shwi ();
+ HOST_WIDE_INT last_idx
+ = (bits.get_last_bit_offset ()
+ / element_bit_size).to_shwi ();
+ if (start_idx == last_idx)
+ {
+ bit_offset_t start_of_element
+ = start_idx * element_bit_size;
+ bit_range range_within_element
+ (bits.m_start_bit_offset - start_of_element,
+ bits.m_size_in_bits);
+ return mgr->get_or_create_bits_within (type,
+ range_within_element,
+ innermost_sval);
+ }
+ }
+ }
+
+ return NULL;
+}
+
+/* class bits_within_svalue : public svalue. */
+
+/* bits_within_svalue'c ctor. */
+
+bits_within_svalue::bits_within_svalue (tree type,
+ const bit_range &bits,
+ const svalue *inner_svalue)
+: svalue (complexity (inner_svalue), type),
+ m_bits (bits),
+ m_inner_svalue (inner_svalue)
+{
+}
+
+/* Implementation of svalue::dump_to_pp vfunc for bits_within_svalue. */
+
+void
+bits_within_svalue::dump_to_pp (pretty_printer *pp, bool simple) const
+{
+ if (simple)
+ {
+ pp_string (pp, "BITS_WITHIN(");
+ if (get_type ())
+ {
+ print_quoted_type (pp, get_type ());
+ pp_string (pp, ", ");
+ }
+ m_bits.dump_to_pp (pp);
+ pp_string (pp, ", inner_val: ");
+ m_inner_svalue->dump_to_pp (pp, simple);
+ pp_character (pp, ')');
+ }
+ else
+ {
+ pp_string (pp, "bits_within_svalue (");
+ if (get_type ())
+ {
+ print_quoted_type (pp, get_type ());
+ pp_string (pp, ", ");
+ }
+ m_bits.dump_to_pp (pp);
+ pp_string (pp, ", inner_val: ");
+ m_inner_svalue->dump_to_pp (pp, simple);
+ pp_character (pp, ')');
+ }
+}
+
+/* Implementation of svalue::maybe_fold_bits_within vfunc
+ for bits_within_svalue. */
+
+const svalue *
+bits_within_svalue::maybe_fold_bits_within (tree type,
+ const bit_range &bits,
+ region_model_manager *mgr) const
+{
+ /* Fold:
+ BITS_WITHIN (range1, BITS_WITHIN (range2, VAL))
+ to:
+ BITS_WITHIN (range1 in range 2, VAL). */
+ bit_range offset_bits (m_bits.get_start_bit_offset ()
+ + bits.m_start_bit_offset,
+ bits.m_size_in_bits);
+ return mgr->get_or_create_bits_within (type, offset_bits, m_inner_svalue);
+}
+
+/* Implementation of svalue::accept vfunc for bits_within_svalue. */
+
+void
+bits_within_svalue::accept (visitor *v) const
+{
+ v->visit_bits_within_svalue (this);
+ m_inner_svalue->accept (v);
+}
+
+/* Implementation of svalue::implicitly_live_p vfunc for bits_within_svalue. */
+
+bool
+bits_within_svalue::implicitly_live_p (const svalue_set *live_svalues,
+ const region_model *model) const
+{
+ return m_inner_svalue->live_p (live_svalues, model);
+}
+
/* class widening_svalue : public svalue. */
/* Implementation of svalue::dump_to_pp vfunc for widening_svalue. */
@@ -1291,6 +1603,75 @@ compound_svalue::calc_complexity (const binding_map &map)
return complexity (num_child_nodes + 1, max_child_depth + 1);
}
+/* Implementation of svalue::maybe_fold_bits_within vfunc
+ for compound_svalue. */
+
+const svalue *
+compound_svalue::maybe_fold_bits_within (tree type,
+ const bit_range &bits,
+ region_model_manager *mgr) const
+{
+ binding_map result_map;
+ for (auto iter : m_map)
+ {
+ const binding_key *key = iter.first;
+ if (const concrete_binding *conc_key
+ = key->dyn_cast_concrete_binding ())
+ {
+ /* Ignore concrete bindings outside BITS. */
+ if (!conc_key->get_bit_range ().intersects_p (bits))
+ continue;
+
+ const svalue *sval = iter.second;
+ /* 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);
+ }
+ else
+ /* If we have any symbolic keys we can't get it as bits. */
+ return NULL;
+ }
+ return mgr->get_or_create_compound_svalue (type, result_map);
+}
+
/* class conjured_svalue : public svalue. */
/* Implementation of svalue::dump_to_pp vfunc for conjured_svalue. */
@@ -41,6 +41,8 @@ enum svalue_kind
SK_UNARYOP,
SK_BINOP,
SK_SUB,
+ SK_REPEATED,
+ SK_BITS_WITHIN,
SK_UNMERGEABLE,
SK_PLACEHOLDER,
SK_WIDENING,
@@ -63,6 +65,9 @@ enum svalue_kind
unaryop_svalue (SK_UNARYOP): unary operation on another svalue
binop_svalue (SK_BINOP): binary operation on two svalues
sub_svalue (SK_SUB): the result of accessing a subregion
+ repeated_svalue (SK_REPEATED): repeating an svalue to fill a larger region
+ bits_within_svalue (SK_BITS_WITHIN): a range of bits/bytes within a larger
+ svalue
unmergeable_svalue (SK_UNMERGEABLE): a value that is so interesting
from a control-flow perspective that it can inhibit state-merging
placeholder_svalue (SK_PLACEHOLDER): for use in selftests.
@@ -107,6 +112,10 @@ public:
dyn_cast_binop_svalue () const { return NULL; }
virtual const sub_svalue *
dyn_cast_sub_svalue () const { return NULL; }
+ virtual const repeated_svalue *
+ dyn_cast_repeated_svalue () const { return NULL; }
+ virtual const bits_within_svalue *
+ dyn_cast_bits_within_svalue () const { return NULL; }
virtual const unmergeable_svalue *
dyn_cast_unmergeable_svalue () const { return NULL; }
virtual const widening_svalue *
@@ -138,6 +147,16 @@ public:
bool involves_p (const svalue *other) const;
+ const svalue *
+ extract_bit_range (tree type,
+ const bit_range &subrange,
+ region_model_manager *mgr) const;
+
+ virtual const svalue *
+ maybe_fold_bits_within (tree type,
+ const bit_range &subrange,
+ region_model_manager *mgr) const;
+
protected:
svalue (complexity c, tree type)
: m_complexity (c), m_type (type)
@@ -175,9 +194,9 @@ public:
}
void mark_deleted () { m_type = reinterpret_cast<tree> (1); }
- void mark_empty () { m_type = NULL_TREE; }
+ void mark_empty () { m_type = reinterpret_cast<tree> (2); }
bool is_deleted () const { return m_type == reinterpret_cast<tree> (1); }
- bool is_empty () const { return m_type == NULL_TREE; }
+ bool is_empty () const { return m_type == reinterpret_cast<tree> (2); }
tree m_type;
const region *m_reg;
@@ -222,7 +241,7 @@ is_a_helper <const region_svalue *>::test (const svalue *sval)
template <> struct default_hash_traits<region_svalue::key_t>
: public member_function_hash_traits<region_svalue::key_t>
{
- static const bool empty_zero_p = true;
+ static const bool empty_zero_p = false;
};
namespace ana {
@@ -253,6 +272,11 @@ public:
enum tree_code op,
const constant_svalue *rhs);
+ const svalue *
+ maybe_fold_bits_within (tree type,
+ const bit_range &subrange,
+ region_model_manager *mgr) const FINAL OVERRIDE;
+
private:
tree m_cst_expr;
};
@@ -285,6 +309,11 @@ public:
void dump_to_pp (pretty_printer *pp, bool simple) const FINAL OVERRIDE;
void accept (visitor *v) const FINAL OVERRIDE;
+
+ const svalue *
+ maybe_fold_bits_within (tree type,
+ const bit_range &subrange,
+ region_model_manager *mgr) const FINAL OVERRIDE;
};
/* An enum describing a particular kind of "poisoned" value. */
@@ -327,9 +356,9 @@ public:
}
void mark_deleted () { m_type = reinterpret_cast<tree> (1); }
- void mark_empty () { m_type = NULL_TREE; }
+ void mark_empty () { m_type = reinterpret_cast<tree> (2); }
bool is_deleted () const { return m_type == reinterpret_cast<tree> (1); }
- bool is_empty () const { return m_type == NULL_TREE; }
+ bool is_empty () const { return m_type == reinterpret_cast<tree> (2); }
enum poison_kind m_kind;
tree m_type;
@@ -364,7 +393,7 @@ is_a_helper <const poisoned_svalue *>::test (const svalue *sval)
template <> struct default_hash_traits<poisoned_svalue::key_t>
: public member_function_hash_traits<poisoned_svalue::key_t>
{
- static const bool empty_zero_p = true;
+ static const bool empty_zero_p = false;
};
namespace ana {
@@ -426,9 +455,9 @@ public:
}
void mark_deleted () { m_type = reinterpret_cast<tree> (1); }
- void mark_empty () { m_type = NULL_TREE; }
+ void mark_empty () { m_type = reinterpret_cast<tree> (2); }
bool is_deleted () const { return m_type == reinterpret_cast<tree> (1); }
- bool is_empty () const { return m_type == NULL_TREE; }
+ bool is_empty () const { return m_type == reinterpret_cast<tree> (2); }
setjmp_record m_record;
tree m_type;
@@ -467,7 +496,7 @@ is_a_helper <const setjmp_svalue *>::test (const svalue *sval)
template <> struct default_hash_traits<setjmp_svalue::key_t>
: public member_function_hash_traits<setjmp_svalue::key_t>
{
- static const bool empty_zero_p = true;
+ static const bool empty_zero_p = false;
};
namespace ana {
@@ -548,9 +577,9 @@ public:
}
void mark_deleted () { m_type = reinterpret_cast<tree> (1); }
- void mark_empty () { m_type = NULL_TREE; }
+ void mark_empty () { m_type = reinterpret_cast<tree> (2); }
bool is_deleted () const { return m_type == reinterpret_cast<tree> (1); }
- bool is_empty () const { return m_type == NULL_TREE; }
+ bool is_empty () const { return m_type == reinterpret_cast<tree> (2); }
tree m_type;
enum tree_code m_op;
@@ -574,6 +603,11 @@ public:
enum tree_code get_op () const { return m_op; }
const svalue *get_arg () const { return m_arg; }
+ const svalue *
+ maybe_fold_bits_within (tree type,
+ const bit_range &subrange,
+ region_model_manager *mgr) const FINAL OVERRIDE;
+
private:
enum tree_code m_op;
const svalue *m_arg;
@@ -592,7 +626,7 @@ is_a_helper <const unaryop_svalue *>::test (const svalue *sval)
template <> struct default_hash_traits<unaryop_svalue::key_t>
: public member_function_hash_traits<unaryop_svalue::key_t>
{
- static const bool empty_zero_p = true;
+ static const bool empty_zero_p = false;
};
namespace ana {
@@ -630,9 +664,9 @@ public:
}
void mark_deleted () { m_type = reinterpret_cast<tree> (1); }
- void mark_empty () { m_type = NULL_TREE; }
+ void mark_empty () { m_type = reinterpret_cast<tree> (2); }
bool is_deleted () const { return m_type == reinterpret_cast<tree> (1); }
- bool is_empty () const { return m_type == NULL_TREE; }
+ bool is_empty () const { return m_type == reinterpret_cast<tree> (2); }
tree m_type;
enum tree_code m_op;
@@ -683,7 +717,7 @@ is_a_helper <const binop_svalue *>::test (const svalue *sval)
template <> struct default_hash_traits<binop_svalue::key_t>
: public member_function_hash_traits<binop_svalue::key_t>
{
- static const bool empty_zero_p = true;
+ static const bool empty_zero_p = false;
};
namespace ana {
@@ -719,9 +753,9 @@ public:
}
void mark_deleted () { m_type = reinterpret_cast<tree> (1); }
- void mark_empty () { m_type = NULL_TREE; }
+ void mark_empty () { m_type = reinterpret_cast<tree> (2); }
bool is_deleted () const { return m_type == reinterpret_cast<tree> (1); }
- bool is_empty () const { return m_type == NULL_TREE; }
+ bool is_empty () const { return m_type == reinterpret_cast<tree> (2); }
tree m_type;
const svalue *m_parent_svalue;
@@ -762,7 +796,182 @@ is_a_helper <const sub_svalue *>::test (const svalue *sval)
template <> struct default_hash_traits<sub_svalue::key_t>
: public member_function_hash_traits<sub_svalue::key_t>
{
- static const bool empty_zero_p = true;
+ static const bool empty_zero_p = false;
+};
+
+namespace ana {
+
+/* Concrete subclass of svalue representing repeating an inner svalue
+ (possibly not a whole number of times) to fill a larger region of
+ type TYPE of size OUTER_SIZE bytes. */
+
+class repeated_svalue : public svalue
+{
+public:
+ /* A support class for uniquifying instances of repeated_svalue. */
+ struct key_t
+ {
+ key_t (tree type,
+ const svalue *outer_size,
+ const svalue *inner_svalue)
+ : m_type (type), m_outer_size (outer_size), m_inner_svalue (inner_svalue)
+ {}
+
+ hashval_t hash () const
+ {
+ inchash::hash hstate;
+ hstate.add_ptr (m_type);
+ hstate.add_ptr (m_outer_size);
+ hstate.add_ptr (m_inner_svalue);
+ return hstate.end ();
+ }
+
+ bool operator== (const key_t &other) const
+ {
+ return (m_type == other.m_type
+ && m_outer_size == other.m_outer_size
+ && m_inner_svalue == other.m_inner_svalue);
+ }
+
+ void mark_deleted () { m_type = reinterpret_cast<tree> (1); }
+ void mark_empty () { m_type = reinterpret_cast<tree> (2); }
+ bool is_deleted () const { return m_type == reinterpret_cast<tree> (1); }
+ bool is_empty () const { return m_type == reinterpret_cast<tree> (2); }
+
+ tree m_type;
+ const svalue *m_outer_size;
+ const svalue *m_inner_svalue;
+ };
+ repeated_svalue (tree type,
+ const svalue *outer_size,
+ const svalue *inner_svalue);
+
+ enum svalue_kind get_kind () const FINAL OVERRIDE { return SK_REPEATED; }
+ const repeated_svalue *dyn_cast_repeated_svalue () const FINAL OVERRIDE
+ {
+ return this;
+ }
+
+ void dump_to_pp (pretty_printer *pp, bool simple) const FINAL OVERRIDE;
+ void accept (visitor *v) const FINAL OVERRIDE;
+
+ const svalue *get_outer_size () const { return m_outer_size; }
+ const svalue *get_inner_svalue () const { return m_inner_svalue; }
+
+ bool all_zeroes_p () const;
+
+ const svalue *
+ maybe_fold_bits_within (tree type,
+ const bit_range &subrange,
+ region_model_manager *mgr) const FINAL OVERRIDE;
+
+ private:
+ const svalue *m_outer_size;
+ const svalue *m_inner_svalue;
+};
+
+} // namespace ana
+
+template <>
+template <>
+inline bool
+is_a_helper <const repeated_svalue *>::test (const svalue *sval)
+{
+ return sval->get_kind () == SK_REPEATED;
+}
+
+template <> struct default_hash_traits<repeated_svalue::key_t>
+: public member_function_hash_traits<repeated_svalue::key_t>
+{
+ static const bool empty_zero_p = false;
+};
+
+namespace ana {
+
+/* A range of bits/bytes within another svalue
+ e.g. bytes 5-39 of INITIAL_SVALUE(R).
+ These can be generated for prefixes and suffixes when part of a binding
+ is clobbered, so that we don't lose too much information. */
+
+class bits_within_svalue : public svalue
+{
+public:
+ /* A support class for uniquifying instances of bits_within_svalue. */
+ struct key_t
+ {
+ key_t (tree type,
+ const bit_range &bits,
+ const svalue *inner_svalue)
+ : m_type (type), m_bits (bits), m_inner_svalue (inner_svalue)
+ {}
+
+ hashval_t hash () const
+ {
+ inchash::hash hstate;
+ hstate.add_ptr (m_type);
+ hstate.add_ptr (m_inner_svalue);
+ return hstate.end ();
+ }
+
+ bool operator== (const key_t &other) const
+ {
+ return (m_type == other.m_type
+ && m_bits == other.m_bits
+ && m_inner_svalue == other.m_inner_svalue);
+ }
+
+ void mark_deleted () { m_type = reinterpret_cast<tree> (1); }
+ void mark_empty () { m_type = reinterpret_cast<tree> (2); }
+ bool is_deleted () const { return m_type == reinterpret_cast<tree> (1); }
+ bool is_empty () const { return m_type == reinterpret_cast<tree> (2); }
+
+ tree m_type;
+ bit_range m_bits;
+ const svalue *m_inner_svalue;
+ };
+ bits_within_svalue (tree type,
+ const bit_range &bits,
+ const svalue *inner_svalue);
+
+ enum svalue_kind get_kind () const FINAL OVERRIDE { return SK_BITS_WITHIN; }
+ const bits_within_svalue *
+ dyn_cast_bits_within_svalue () const FINAL OVERRIDE
+ {
+ return this;
+ }
+
+ void dump_to_pp (pretty_printer *pp, bool simple) const FINAL OVERRIDE;
+ void accept (visitor *v) const FINAL OVERRIDE;
+ bool implicitly_live_p (const svalue_set *,
+ const region_model *) const FINAL OVERRIDE;
+
+ const bit_range &get_bits () const { return m_bits; }
+ const svalue *get_inner_svalue () const { return m_inner_svalue; }
+
+ const svalue *
+ maybe_fold_bits_within (tree type,
+ const bit_range &subrange,
+ region_model_manager *mgr) const FINAL OVERRIDE;
+
+ private:
+ const bit_range m_bits;
+ const svalue *m_inner_svalue;
+};
+
+} // namespace ana
+
+template <>
+template <>
+inline bool
+is_a_helper <const bits_within_svalue *>::test (const svalue *sval)
+{
+ return sval->get_kind () == SK_BITS_WITHIN;
+}
+
+template <> struct default_hash_traits<bits_within_svalue::key_t>
+: public member_function_hash_traits<bits_within_svalue::key_t>
+{
+ static const bool empty_zero_p = false;
};
namespace ana {
@@ -888,9 +1097,9 @@ public:
}
void mark_deleted () { m_type = reinterpret_cast<tree> (1); }
- void mark_empty () { m_type = NULL_TREE; }
+ void mark_empty () { m_type = reinterpret_cast<tree> (2); }
bool is_deleted () const { return m_type == reinterpret_cast<tree> (1); }
- bool is_empty () const { return m_type == NULL_TREE; }
+ bool is_empty () const { return m_type == reinterpret_cast<tree> (2); }
tree m_type;
function_point m_point;
@@ -952,7 +1161,7 @@ is_a_helper <widening_svalue *>::test (svalue *sval)
template <> struct default_hash_traits<widening_svalue::key_t>
: public member_function_hash_traits<widening_svalue::key_t>
{
- static const bool empty_zero_p = true;
+ static const bool empty_zero_p = false;
};
namespace ana {
@@ -1000,9 +1209,9 @@ public:
}
void mark_deleted () { m_type = reinterpret_cast<tree> (1); }
- void mark_empty () { m_type = NULL_TREE; }
+ void mark_empty () { m_type = reinterpret_cast<tree> (2); }
bool is_deleted () const { return m_type == reinterpret_cast<tree> (1); }
- bool is_empty () const { return m_type == NULL_TREE; }
+ bool is_empty () const { return m_type == reinterpret_cast<tree> (2); }
tree m_type;
const binding_map *m_map_ptr;
@@ -1029,6 +1238,11 @@ public:
return key_t (get_type (), &m_map);
}
+ const svalue *
+ maybe_fold_bits_within (tree type,
+ const bit_range &subrange,
+ region_model_manager *mgr) const FINAL OVERRIDE;
+
private:
static complexity calc_complexity (const binding_map &map);
@@ -1048,7 +1262,7 @@ is_a_helper <compound_svalue *>::test (svalue *sval)
template <> struct default_hash_traits<compound_svalue::key_t>
: public member_function_hash_traits<compound_svalue::key_t>
{
- static const bool empty_zero_p = true;
+ static const bool empty_zero_p = false;
};
namespace ana {
new file mode 100644
@@ -0,0 +1,98 @@
+#include "analyzer-decls.h"
+
+struct foo
+{
+ int i;
+ int j;
+};
+
+struct coord
+{
+ int x;
+ int y;
+ int z;
+};
+
+struct foo g;
+
+void test_1 (void)
+{
+ g.i = 42;
+ if (g.j)
+ __analyzer_eval (g.j); /* { dg-warning "TRUE" } */
+ else
+ __analyzer_eval (g.j); /* { dg-warning "FALSE" } */
+ __analyzer_dump_exploded_nodes (0); /* { dg-warning "1 processed enode" } */
+}
+
+void test_2 (void)
+{
+ struct foo f;
+ f.i = 42;
+ if (f.j)
+ __analyzer_eval (f.j); /* { dg-warning "TRUE" } */
+ else
+ __analyzer_eval (f.j); /* { dg-warning "FALSE" } */
+ __analyzer_dump_exploded_nodes (0); /* { dg-warning "1 processed enode" } */
+}
+
+void test_3 (struct foo *p)
+{
+ struct foo f = *p;
+ f.i = 42;
+ if (f.j)
+ __analyzer_eval (f.j); /* { dg-warning "TRUE" } */
+ else
+ __analyzer_eval (f.j); /* { dg-warning "FALSE" } */
+ __analyzer_dump_exploded_nodes (0); /* { dg-warning "1 processed enode" } */
+}
+
+void test_4 (struct coord *p)
+{
+ struct coord f = *p;
+ f.x = 42;
+ __analyzer_eval (f.y == p->y); /* { dg-warning "TRUE" } */
+ __analyzer_eval (f.z == p->z); /* { dg-warning "TRUE" } */
+}
+
+struct s5
+{
+ char arr[8];
+};
+
+void test_5 (struct s5 *p)
+{
+ struct s5 f = *p;
+ f.arr[3] = 42;
+ __analyzer_eval (f.arr[0] == p->arr[0]); /* { dg-warning "TRUE" } */
+ __analyzer_eval (f.arr[1] == p->arr[1]); /* { dg-warning "TRUE" } */
+ __analyzer_eval (f.arr[2] == p->arr[2]); /* { dg-warning "TRUE" } */
+ __analyzer_eval (f.arr[3] == 42); /* { dg-warning "TRUE" } */
+ __analyzer_eval (f.arr[4] == p->arr[4]); /* { dg-warning "TRUE" } */
+ __analyzer_eval (f.arr[5] == p->arr[5]); /* { dg-warning "TRUE" } */
+ __analyzer_eval (f.arr[6] == p->arr[6]); /* { dg-warning "TRUE" } */
+ __analyzer_eval (f.arr[7] == p->arr[7]); /* { dg-warning "TRUE" } */
+}
+
+struct s6
+{
+ int before; /* Give "arr" a nonzero offset. */
+ struct foo arr[4];
+ int after;
+};
+
+void test_6 (struct s6 *p, struct foo *q)
+{
+ struct s6 f = *p;
+ f.arr[1] = *q;
+ __analyzer_eval (f.before == p->before); /* { dg-warning "TRUE" } */
+ __analyzer_eval (f.arr[0].i == p->arr[0].i); /* { dg-warning "TRUE" } */
+ __analyzer_eval (f.arr[0].j == p->arr[0].j); /* { dg-warning "TRUE" } */
+ __analyzer_eval (f.arr[1].i == q->i); /* { dg-warning "TRUE" } */
+ __analyzer_eval (f.arr[1].j == q->j); /* { dg-warning "TRUE" } */
+ __analyzer_eval (f.arr[2].i == p->arr[2].i); /* { dg-warning "TRUE" } */
+ __analyzer_eval (f.arr[2].j == p->arr[2].j); /* { dg-warning "TRUE" } */
+ __analyzer_eval (f.arr[3].i == p->arr[3].i); /* { dg-warning "TRUE" } */
+ __analyzer_eval (f.arr[3].j == p->arr[3].j); /* { dg-warning "TRUE" } */
+ __analyzer_eval (f.after == p->after); /* { dg-warning "TRUE" } */
+}
new file mode 100644
@@ -0,0 +1,72 @@
+#include "analyzer-decls.h"
+
+typedef __SIZE_TYPE__ size_t;
+extern void bzero (void *s, size_t n);
+extern void *memset(void *s, int c, size_t n);
+
+void test_1 (void)
+{
+ char arr[16];
+ bzero (arr, sizeof (arr));
+ __analyzer_eval (arr[0] == 0); /* { dg-warning "TRUE" } */
+ __analyzer_eval (arr[7] == 0); /* { dg-warning "TRUE" } */
+ __analyzer_eval (arr[8] == 0); /* { dg-warning "TRUE" } */
+ __analyzer_eval (arr[9] == 0); /* { dg-warning "TRUE" } */
+ __analyzer_eval (arr[15] == 0); /* { dg-warning "TRUE" } */
+
+ /* Clobber in the middle (with prefix and suffix). */
+ arr[8] = 42;
+ __analyzer_eval (arr[0] == 0); /* { dg-warning "TRUE" } */
+ __analyzer_eval (arr[7] == 0); /* { dg-warning "TRUE" } */
+ __analyzer_eval (arr[8] == 0); /* { dg-warning "FALSE" } */
+ __analyzer_eval (arr[8] == 42); /* { dg-warning "TRUE" } */
+ __analyzer_eval (arr[9] == 0); /* { dg-warning "TRUE" } */
+ __analyzer_eval (arr[15] == 0); /* { dg-warning "TRUE" } */
+}
+
+void test_2 (void)
+{
+ char arr[16];
+ bzero (arr, sizeof (arr));
+ __analyzer_eval (arr[0] == 0); /* { dg-warning "TRUE" } */
+ __analyzer_eval (arr[1] == 0); /* { dg-warning "TRUE" } */
+ __analyzer_eval (arr[15] == 0); /* { dg-warning "TRUE" } */
+
+ /* Clobber at the front (suffix, but no prefix). */
+ arr[0] = 42;
+ __analyzer_eval (arr[0] == 0); /* { dg-warning "FALSE" } */
+ __analyzer_eval (arr[0] == 42); /* { dg-warning "TRUE" } */
+ __analyzer_eval (arr[1] == 0); /* { dg-warning "TRUE" } */
+ __analyzer_eval (arr[15] == 0); /* { dg-warning "TRUE" } */
+}
+
+void test_3 (void)
+{
+ char arr[16];
+ bzero (arr, sizeof (arr));
+ __analyzer_eval (arr[0] == 0); /* { dg-warning "TRUE" } */
+ __analyzer_eval (arr[14] == 0); /* { dg-warning "TRUE" } */
+ __analyzer_eval (arr[15] == 0); /* { dg-warning "TRUE" } */
+
+ /* Clobber at the end (prefix, but no suffix). */
+ arr[15] = 42;
+ __analyzer_eval (arr[0] == 0); /* { dg-warning "TRUE" } */
+ __analyzer_eval (arr[14] == 0); /* { dg-warning "TRUE" } */
+ __analyzer_eval (arr[15] == 0); /* { dg-warning "FALSE" } */
+ __analyzer_eval (arr[15] == 42); /* { dg-warning "TRUE" } */
+}
+
+void test_4 (void)
+{
+ char arr[16];
+ bzero (arr, sizeof (arr));
+ __analyzer_eval (arr[0] == 0); /* { dg-warning "TRUE" } */
+ __analyzer_eval (arr[15] == 0); /* { dg-warning "TRUE" } */
+
+ /* Exact overlap, no prefix or suffix. */
+ memset (arr, 1, 16);
+ __analyzer_eval (arr[0] == 0); /* { dg-warning "FALSE" } */
+ __analyzer_eval (arr[15] == 0); /* { dg-warning "FALSE" } */
+ __analyzer_eval (arr[0] == 1); /* { dg-warning "TRUE" } */
+ __analyzer_eval (arr[15] == 1); /* { dg-warning "TRUE" } */
+}
@@ -503,9 +503,7 @@ void test_26 (struct coord *p, struct coord *q)
the dest value. */
*p = *q;
__analyzer_eval (p->x); /* { dg-warning "UNKNOWN" } */
- __analyzer_eval (p->y == 17); /* { dg-warning "TRUE" "desired" { xfail *-*-* } } */
- /* { dg-warning "UNKNOWN" "status quo" { target *-*-* } .-1 } */
- // TODO(xfail): should have been overwritten with q->y
+ __analyzer_eval (p->y == 17); /* { dg-warning "TRUE" } */
__analyzer_eval (q->x); /* { dg-warning "UNKNOWN" } */
__analyzer_eval (q->y == 17); /* { dg-warning "TRUE" "desired" { xfail *-*-* } } */
@@ -522,19 +520,11 @@ void test_27 (struct coord *p)
void test_28 (struct coord *p)
{
memset (p, 0, sizeof (struct coord) * 10);
- __analyzer_eval (p[0].x == 0); /* { dg-warning "TRUE" "desired" { xfail *-*-* } } */
- /* { dg-warning "UNKNOWN" "status quo" { target *-*-* } .-1 } */
- // TODO(xfail):
- __analyzer_eval (p[0].y == 0); /* { dg-warning "TRUE" "desired" { xfail *-*-* } } */
- /* { dg-warning "UNKNOWN" "status quo" { target *-*-* } .-1 } */
- // TODO(xfail):
+ __analyzer_eval (p[0].x == 0); /* { dg-warning "TRUE" } */
+ __analyzer_eval (p[0].y == 0); /* { dg-warning "TRUE" } */
- __analyzer_eval (p[9].x == 0); /* { dg-warning "TRUE" "desired" { xfail *-*-* } } */
- /* { dg-warning "UNKNOWN" "status quo" { target *-*-* } .-1 } */
- // TODO(xfail):
- __analyzer_eval (p[9].y == 0); /* { dg-warning "TRUE" "desired" { xfail *-*-* } } */
- /* { dg-warning "UNKNOWN" "status quo" { target *-*-* } .-1 } */
- // TODO(xfail):
+ __analyzer_eval (p[9].x == 0); /* { dg-warning "TRUE" } */
+ __analyzer_eval (p[9].y == 0); /* { dg-warning "TRUE" } */
__analyzer_eval (p[10].x == 0); /* { dg-warning "UNKNOWN" } */
__analyzer_eval (p[10].y == 0); /* { dg-warning "UNKNOWN" } */
@@ -1035,8 +1025,8 @@ void test_52 (struct big b)
{
struct big d;
memcpy (&d, &b, sizeof (struct big));
- __analyzer_eval (b.ia[0] == d.ia[0]); /* { dg-warning "TRUE" "desired" { xfail *-*-* } } */
- /* { dg-warning "UNKNOWN" "status quo" { target *-*-* } .-1 } */
+ __analyzer_eval (b.ia[0] == d.ia[0]); /* { dg-warning "TRUE" } */
+ __analyzer_eval (b.ia[1023] == d.ia[1023]); /* { dg-warning "TRUE" } */
}
void test_53 (const char *msg)
@@ -12,7 +12,7 @@ void test (void)
{
void *p0, *p1, *p2, *p3, *p4, *p5, *p6, *p7, *p8;
void **pp;
- while (get ())
+ while (get ()) /* { dg-warning "leak" } */
{
switch (get ())
{
@@ -36,22 +36,16 @@ void test_3 (int val)
{
char buf[256];
memset (buf, 'A', 256);
- /* We currently merely mark such regions as "unknown", so querying
- values within them yields UNKNOWN when ideally it would be TRUE. */
- __analyzer_eval (buf[42] == 'A'); /* { dg-warning "TRUE" "known nonzero" { xfail *-*-* } } */
- /* { dg-bogus "UNKNOWN" "status quo" { xfail *-*-* } .-1 } */
+ __analyzer_eval (buf[42] == 'A'); /* { dg-warning "TRUE" } */
}
/* A "memset" with unknown value. */
-void test_4 (int val)
+void test_4 (char val)
{
char buf[256];
memset (buf, val, 256);
- /* We currently merely mark such regions as "unknown", so querying
- values within them yields UNKNOWN when ideally it would be TRUE. */
- __analyzer_eval (buf[42] == (char)val); /* { dg-warning "TRUE" "known nonzero" { xfail *-*-* } } */
- /* { dg-bogus "UNKNOWN" "status quo" { xfail *-*-* } .-1 } */
+ __analyzer_eval (buf[42] == (char)val); /* { dg-warning "TRUE" } */
}
/* A "memset" with unknown num bytes. */
@@ -98,6 +92,14 @@ void test_6 (int val)
__analyzer_eval (buf[42] == 'A'); /* { dg-warning "TRUE" } */
}
+void test_6b (int val)
+{
+ char buf[256];
+ memset (buf, 'A', sizeof (buf));
+ memset (buf, 'B', get_zero ());
+ __analyzer_eval (buf[42] == 'A'); /* { dg-warning "TRUE" } */
+}
+
/* A "memset" of known size that's not the full buffer. */
void test_7 (void)
@@ -105,10 +107,96 @@ void test_7 (void)
char buf[256];
buf[128] = 'A';
memset (buf, 0, 128);
- /* We currently merely mark the whole region as "unknown", so querying
- values within them yields UNKNOWN. */
- __analyzer_eval (buf[127] == '\0'); /* { dg-warning "TRUE" "known nonzero" { xfail *-*-* } } */
- /* { dg-bogus "UNKNOWN" "status quo" { xfail *-*-* } .-1 } */
- __analyzer_eval (buf[128] == 'A'); /* { dg-warning "TRUE" "known nonzero" { xfail *-*-* } } */
- /* { dg-bogus "UNKNOWN" "status quo" { xfail *-*-* } .-1 } */
+ __analyzer_eval (buf[0] == '\0'); /* { dg-warning "TRUE" } */
+ __analyzer_eval (buf[127] == '\0'); /* { dg-warning "TRUE" } */
+ __analyzer_eval (buf[128] == 'A'); /* { dg-warning "TRUE" } */
+}
+
+void test_8 (void)
+{
+ char buf[20];
+ memset (buf + 0, 0, 1);
+ memset (buf + 1, 1, 1);
+ memset (buf + 2, 2, 1);
+ memset (buf + 3, 3, 1);
+ memset (buf + 4, 4, 2);
+ memset (buf + 6, 6, 2);
+ memset (buf + 8, 8, 4);
+ memset (buf + 12, 12, 8);
+ __analyzer_eval (buf[0] == 0); /* { dg-warning "TRUE" } */
+ __analyzer_eval (buf[1] == 1); /* { dg-warning "TRUE" } */
+ __analyzer_eval (buf[2] == 2); /* { dg-warning "TRUE" } */
+ __analyzer_eval (buf[3] == 3); /* { dg-warning "TRUE" } */
+ __analyzer_eval (buf[4] == 4); /* { dg-warning "TRUE" } */
+ __analyzer_eval (buf[5] == 4); /* { dg-warning "TRUE" } */
+ __analyzer_eval (buf[6] == 6); /* { dg-warning "TRUE" } */
+ __analyzer_eval (buf[7] == 6); /* { dg-warning "TRUE" } */
+ __analyzer_eval (buf[8] == 8); /* { dg-warning "TRUE" } */
+ __analyzer_eval (buf[9] == 8); /* { dg-warning "TRUE" } */
+ __analyzer_eval (buf[10] == 8); /* { dg-warning "TRUE" } */
+ __analyzer_eval (buf[11] == 8); /* { dg-warning "TRUE" } */
+ __analyzer_eval (buf[12] == 12); /* { dg-warning "TRUE" } */
+ __analyzer_eval (buf[13] == 12); /* { dg-warning "TRUE" } */
+ __analyzer_eval (buf[14] == 12); /* { dg-warning "TRUE" } */
+ __analyzer_eval (buf[15] == 12); /* { dg-warning "TRUE" } */
+ __analyzer_eval (buf[16] == 12); /* { dg-warning "TRUE" } */
+ __analyzer_eval (buf[17] == 12); /* { dg-warning "TRUE" } */
+ __analyzer_eval (buf[18] == 12); /* { dg-warning "TRUE" } */
+ __analyzer_eval (buf[19] == 12); /* { dg-warning "TRUE" } */
+}
+
+/* Various overlapping memset calls with different sizes and values. */
+
+void test_9 (void)
+{
+ char buf[8];
+ memset (buf, 0, 8);
+ __analyzer_eval (buf[0] == 0); /* { dg-warning "TRUE" } */
+ __analyzer_eval (buf[1] == 0); /* { dg-warning "TRUE" } */
+ __analyzer_eval (buf[2] == 0); /* { dg-warning "TRUE" } */
+ __analyzer_eval (buf[3] == 0); /* { dg-warning "TRUE" } */
+ __analyzer_eval (buf[4] == 0); /* { dg-warning "TRUE" } */
+ __analyzer_eval (buf[5] == 0); /* { dg-warning "TRUE" } */
+ __analyzer_eval (buf[6] == 0); /* { dg-warning "TRUE" } */
+ __analyzer_eval (buf[7] == 0); /* { dg-warning "TRUE" } */
+
+ memset (buf + 1, 1, 4);
+ __analyzer_eval (buf[0] == 0); /* { dg-warning "TRUE" } */
+ __analyzer_eval (buf[1] == 1); /* { dg-warning "TRUE" } */
+ __analyzer_eval (buf[2] == 1); /* { dg-warning "TRUE" } */
+ __analyzer_eval (buf[3] == 1); /* { dg-warning "TRUE" } */
+ __analyzer_eval (buf[4] == 1); /* { dg-warning "TRUE" } */
+ __analyzer_eval (buf[5] == 0); /* { dg-warning "TRUE" } */
+ __analyzer_eval (buf[6] == 0); /* { dg-warning "TRUE" } */
+ __analyzer_eval (buf[7] == 0); /* { dg-warning "TRUE" } */
+
+ memset (buf + 2, 2, 4);
+ __analyzer_eval (buf[0] == 0); /* { dg-warning "TRUE" } */
+ __analyzer_eval (buf[1] == 1); /* { dg-warning "TRUE" } */
+ __analyzer_eval (buf[2] == 2); /* { dg-warning "TRUE" } */
+ __analyzer_eval (buf[3] == 2); /* { dg-warning "TRUE" } */
+ __analyzer_eval (buf[4] == 2); /* { dg-warning "TRUE" } */
+ __analyzer_eval (buf[5] == 2); /* { dg-warning "TRUE" } */
+ __analyzer_eval (buf[6] == 0); /* { dg-warning "TRUE" } */
+ __analyzer_eval (buf[7] == 0); /* { dg-warning "TRUE" } */
+
+ memset (buf + 4, 3, 3);
+ __analyzer_eval (buf[0] == 0); /* { dg-warning "TRUE" } */
+ __analyzer_eval (buf[1] == 1); /* { dg-warning "TRUE" } */
+ __analyzer_eval (buf[2] == 2); /* { dg-warning "TRUE" } */
+ __analyzer_eval (buf[3] == 2); /* { dg-warning "TRUE" } */
+ __analyzer_eval (buf[4] == 3); /* { dg-warning "TRUE" } */
+ __analyzer_eval (buf[5] == 3); /* { dg-warning "TRUE" } */
+ __analyzer_eval (buf[6] == 3); /* { dg-warning "TRUE" } */
+ __analyzer_eval (buf[7] == 0); /* { dg-warning "TRUE" } */
+
+ memset (buf + 0, 4, 3);
+ __analyzer_eval (buf[0] == 4); /* { dg-warning "TRUE" } */
+ __analyzer_eval (buf[1] == 4); /* { dg-warning "TRUE" } */
+ __analyzer_eval (buf[2] == 4); /* { dg-warning "TRUE" } */
+ __analyzer_eval (buf[3] == 2); /* { dg-warning "TRUE" } */
+ __analyzer_eval (buf[4] == 3); /* { dg-warning "TRUE" } */
+ __analyzer_eval (buf[5] == 3); /* { dg-warning "TRUE" } */
+ __analyzer_eval (buf[6] == 3); /* { dg-warning "TRUE" } */
+ __analyzer_eval (buf[7] == 0); /* { dg-warning "TRUE" } */
}
new file mode 100644
@@ -0,0 +1,107 @@
+/* This is a very simplified version of CVE-2017-18549,
+ a use of uninitialized padding values affecting the Linux kernel
+ (and thus GPLv2).
+
+ It was fixed by e.g. 342ffc26693b528648bdc9377e51e4f2450b4860 on linux-4.13.y
+ in linux-stable. */
+
+#include "analyzer-decls.h"
+#include <string.h>
+
+typedef unsigned int __u32;
+typedef unsigned int u32;
+typedef unsigned char u8;
+
+/* Adapted from include/uapi/linux/types.h */
+
+#define __bitwise
+typedef __u32 __bitwise __le32;
+
+/* Adapted from drivers/scsi/aacraid/aacraid.h */
+
+#define AAC_SENSE_BUFFERSIZE 30
+
+struct aac_srb_reply
+{
+ __le32 status;
+ __le32 srb_status;
+ __le32 scsi_status;
+ __le32 data_xfer_length;
+ __le32 sense_data_size;
+ u8 sense_data[AAC_SENSE_BUFFERSIZE];
+
+ /* Manually added to help verify the fix. */
+ u8 padding[2];
+};
+
+#define ST_OK 0
+#define SRB_STATUS_SUCCESS 0x01
+
+/* Adapted from drivers/scsi/aacraid/commctrl.c */
+
+static int aac_send_raw_srb(/* [...snip...] */)
+{
+ u32 byte_count = 0;
+
+ /* [...snip...] */
+
+ struct aac_srb_reply reply;
+
+ reply.status = ST_OK;
+
+ /* [...snip...] */
+
+ reply.srb_status = SRB_STATUS_SUCCESS;
+ reply.scsi_status = 0;
+ reply.data_xfer_length = byte_count;
+ reply.sense_data_size = 0;
+ memset(reply.sense_data, 0, AAC_SENSE_BUFFERSIZE);
+
+ /* [...snip...] */
+
+ __analyzer_eval (reply.status == ST_OK); /* { dg-warning "TRUE" } */
+ __analyzer_eval (reply.srb_status == SRB_STATUS_SUCCESS); /* { dg-warning "TRUE" } */
+ __analyzer_eval (reply.scsi_status == 0); /* { dg-warning "TRUE" } */
+ __analyzer_eval (reply.data_xfer_length == byte_count); /* { dg-warning "TRUE" } */
+ __analyzer_eval (reply.sense_data_size == 0); /* { dg-warning "TRUE" } */
+ __analyzer_eval (reply.sense_data[0] == 0); /* { dg-warning "TRUE" } */
+ __analyzer_eval (reply.sense_data[AAC_SENSE_BUFFERSIZE - 1] == 0); /* { dg-warning "TRUE" } */
+ /* TODO: the following should be detected as uninitialized, when
+ that diagnostic is reimplemented. */
+ __analyzer_eval (reply.padding[0] == 0); /* { dg-warning "UNKNOWN" } */
+ __analyzer_eval (reply.padding[1] == 0); /* { dg-warning "UNKNOWN" } */
+}
+
+static int aac_send_raw_srb_fixed(/* [...snip...] */)
+{
+ u32 byte_count = 0;
+
+ /* [...snip...] */
+
+ struct aac_srb_reply reply;
+
+ /* This is the fix. */
+ memset(&reply, 0, sizeof(reply));
+
+ reply.status = ST_OK;
+
+ /* [...snip...] */
+
+ reply.srb_status = SRB_STATUS_SUCCESS;
+ reply.scsi_status = 0;
+ reply.data_xfer_length = byte_count;
+ reply.sense_data_size = 0;
+ memset(reply.sense_data, 0, AAC_SENSE_BUFFERSIZE);
+
+ /* [...snip...] */
+
+ __analyzer_eval (reply.status == ST_OK); /* { dg-warning "TRUE" } */
+ __analyzer_eval (reply.srb_status == SRB_STATUS_SUCCESS); /* { dg-warning "TRUE" } */
+ __analyzer_eval (reply.scsi_status == 0); /* { dg-warning "TRUE" } */
+ __analyzer_eval (reply.data_xfer_length == byte_count); /* { dg-warning "TRUE" } */
+ __analyzer_eval (reply.sense_data_size == 0); /* { dg-warning "TRUE" } */
+ __analyzer_eval (reply.sense_data[0] == 0); /* { dg-warning "TRUE" } */
+ __analyzer_eval (reply.sense_data[AAC_SENSE_BUFFERSIZE - 1] == 0); /* { dg-warning "TRUE" } */
+ __analyzer_eval (reply.padding[0] == 0); /* { dg-warning "TRUE" } */
+ __analyzer_eval (reply.padding[1] == 0); /* { dg-warning "TRUE" } */
+}
new file mode 100644
@@ -0,0 +1,11 @@
+/* Merger where "arr" has two different symbolic bindings. */
+
+void test (int i, int j, int flag)
+{
+ int arr[16];
+
+ if (flag)
+ arr[i] = 42;
+ else
+ arr[j] = 17;
+}
I rewrote the way the analyzer's region_model tracks the state of memory in GCC 11 (in 808f4dfeb3a95f50f15e71148e5c1067f90a126d), which introduced a store with a binding_map class, mapping binding keys to symbolic values. The GCC 11 implementation of binding keys has an enum binding_kind, which can be "default" vs "direct"; the idea being that direct bindings take priority over default bindings, where the latter could be used to represent e.g. a zero-fill of a buffer, and the former expresses those subregions that have since been touched. This doesn't work well: it doesn't express the idea of filling different subregions with different values, or a memset that only touches part of a buffer, leading to numerous XFAILs in the memset test cases (and elsewhere). As preparatory work towards tracking uninitialized values, this patch eliminates the enum binding_kind, so that all bindings have equal weight; the order in which they happen is all that matters. If a write happens which partially overwrites an existing binding, the new code can partially overwrite a binding, potentially punching a hole so that an existing binding is split into two parts. The patch adds some new classes: - a new "bits_within_svalue" symbolic value to support extracting parts of an existing value when its binding is partially clobbered - a new "repeated_svalue" symbolic value to better express filling a region with repeated copies of a symbolic value (e.g. constant zero) - a new "sized_region" region to express accessing a subregion with a symbolic size in bytes and it rewrites e.g. how memset is implemented, so that we can precisely track which bits in a region have not been touched. That said, the patch doesn't actually implement "uninitialized" values; I'm saving that for a followup. Successfully bootstrapped & regrtested on x86_64-pc-linux-gnu. Smoketested on powerpc64-unknown-linux-gnu (gcc110 in compile farm) Pushed to trunk as r12-1931-ge61ffa201403e3814a43b176883e176716b1492f. gcc/analyzer/ChangeLog: PR analyzer/95006 * analyzer.h (class repeated_svalue): New forward decl. (class bits_within_svalue): New forward decl. (class sized_region): New forward decl. (get_field_at_bit_offset): New forward decl. * engine.cc (exploded_graph::get_or_create_node): Validate the merged state. (exploded_graph::maybe_process_run_of_before_supernode_enodes): Validate the states at each stage. * program-state.cc (program_state::validate): Validate m_region_model. * region-model-impl-calls.cc (region_model::impl_call_memset): Replace special-case logic for handling constant sizes with a call to fill_region of a sized_region with the given fill value. * region-model-manager.cc (maybe_undo_optimize_bit_field_compare): Drop DK_direct. (region_model_manager::maybe_fold_sub_svalue): Fold element-based subregions of an initial value into initial values of an element. Fold subvalues of repeated svalues. (region_model_manager::maybe_fold_repeated_svalue): New. (region_model_manager::get_or_create_repeated_svalue): New. (get_bit_range_for_field): New. (get_byte_range_for_field): New. (get_field_at_byte_range): New. (region_model_manager::maybe_fold_bits_within_svalue): New. (region_model_manager::get_or_create_bits_within): New. (region_model_manager::get_sized_region): New. (region_model_manager::log_stats): Update for addition of m_repeated_values_map, m_bits_within_values_map, and m_sized_regions. * region-model.cc (region_model::validate): New. (region_model::on_assignment): Drop enum binding_kind. (region_model::get_initial_value_for_global): Likewise. (region_model::get_rvalue_for_bits): Replace body with call to get_or_create_bits_within. (region_model::get_capacity): Handle RK_SIZED. (region_model::set_value): Drop enum binding_kind. (region_model::fill_region): New. (region_model::get_representative_path_var_1): Handle RK_SIZED. * region-model.h (visitor::visit_repeated_svalue): New. (visitor::visit_bits_within_svalue): New. (region_model_manager::get_or_create_repeated_svalue): New decl. (region_model_manager::get_or_create_bits_within): New decl. (region_model_manager::get_sized_region): New decl. (region_model_manager::maybe_fold_repeated_svalue): New decl. (region_model_manager::maybe_fold_bits_within_svalue): New decl. (region_model_manager::repeated_values_map_t): New typedef. (region_model_manager::m_repeated_values_map): New field. (region_model_manager::bits_within_values_map_t): New typedef. (region_model_manager::m_bits_within_values_map): New field. (region_model_manager::m_sized_regions): New field. (region_model::fill_region): New decl. * region.cc (region::get_base_region): Handle RK_SIZED. (region::base_region_p): Likewise. (region::get_byte_size_sval): New. (get_field_at_bit_offset): Make non-static. (region::calc_offset): Move implementation of cases to get_relative_concrete_offset vfunc implementations. Handle RK_SIZED. (region::get_relative_concrete_offset): New. (decl_region::get_svalue_for_initializer): Drop enum binding_kind. (field_region::get_relative_concrete_offset): New, from region::calc_offset. (element_region::get_relative_concrete_offset): Likewise. (offset_region::get_relative_concrete_offset): Likewise. (sized_region::accept): New. (sized_region::dump_to_pp): New. (sized_region::get_byte_size): New. (sized_region::get_bit_size): New. * region.h (enum region_kind): Add RK_SIZED. (region::dyn_cast_sized_region): New. (region::get_byte_size): Make virtual. (region::get_bit_size): Likewise. (region::get_byte_size_sval): New decl. (region::get_relative_concrete_offset): New decl. (field_region::get_relative_concrete_offset): New decl. (element_region::get_relative_concrete_offset): Likewise. (offset_region::get_relative_concrete_offset): Likewise. (class sized_region): New. * store.cc (binding_kind_to_string): Delete. (binding_key::make): Drop enum binding_kind. (binding_key::dump_to_pp): Delete. (binding_key::cmp_ptrs): Drop enum binding_kind. (bit_range::contains_p): New. (byte_range::dump): New. (byte_range::contains_p): New. (byte_range::cmp): New. (concrete_binding::dump_to_pp): Drop enum binding_kind. (concrete_binding::cmp_ptr_ptr): Likewise. (symbolic_binding::dump_to_pp): Likewise. (symbolic_binding::cmp_ptr_ptr): Likewise. (binding_map::apply_ctor_val_to_range): Likewise. (binding_map::apply_ctor_pair_to_child_region): Likewise. (binding_map::get_overlapping_bindings): New. (binding_map::remove_overlapping_bindings): New. (binding_cluster::validate): New. (binding_cluster::bind): Drop enum binding_kind. (binding_cluster::bind_compound_sval): Likewise. (binding_cluster::purge_region): Likewise. (binding_cluster::zero_fill_region): Reimplement in terms of... (binding_cluster::fill_region): New. (binding_cluster::mark_region_as_unknown): Drop enum binding_kind. (binding_cluster::get_binding): Likewise. (binding_cluster::get_binding_recursive): Likewise. (binding_cluster::get_any_binding): Likewise. (binding_cluster::maybe_get_compound_binding): Reimplement. (binding_cluster::get_overlapping_bindings): Delete. (binding_cluster::remove_overlapping_bindings): Reimplement in terms of binding_map::remove_overlapping_bindings. (binding_cluster::can_merge_p): Update for removal of enum binding_kind. (binding_cluster::on_unknown_fncall): Drop enum binding_kind. (binding_cluster::maybe_get_simple_value): Likewise. (store_manager::get_concrete_binding): Likewise. (store_manager::get_symbolic_binding): Likewise. (store::validate): New. (store::set_value): Drop enum binding_kind. (store::zero_fill_region): Reimplement in terms of... (store::fill_region): New. (selftest::test_binding_key_overlap): Drop enum binding_kind. * store.h (enum binding_kind): Delete. (binding_kind_to_string): Delete decl. (binding_key::make): Drop enum binding_kind. (binding_key::dump_to_pp): Make pure virtual. (binding_key::get_kind): Delete. (binding_key::mark_deleted): Delete. (binding_key::mark_empty): Delete. (binding_key::is_deleted): Delete. (binding_key::is_empty): Delete. (binding_key::binding_key): Delete. (binding_key::impl_hash): Delete. (binding_key::impl_eq): Delete. (binding_key::m_kind): Delete. (bit_range::get_last_bit_offset): New. (bit_range::contains_p): New. (byte_range::contains_p): New. (byte_range::operator==): New. (byte_range::get_start_byte_offset): New. (byte_range::get_next_byte_offset): New. (byte_range::get_last_byte_offset): New. (byte_range::as_bit_range): New. (byte_range::cmp): New. (concrete_binding::concrete_binding): Drop enum binding_kind. (concrete_binding::hash): Likewise. (concrete_binding::operator==): Likewise. (concrete_binding::mark_deleted): New. (concrete_binding::mark_empty): New. (concrete_binding::is_deleted): New. (concrete_binding::is_empty): New. (default_hash_traits<ana::concrete_binding>::empty_zero_p): Make false. (symbolic_binding::symbolic_binding): Drop enum binding_kind. (symbolic_binding::hash): Likewise. (symbolic_binding::operator==): Likewise. (symbolic_binding::mark_deleted): New. (symbolic_binding::mark_empty): New. (symbolic_binding::is_deleted): New. (symbolic_binding::is_empty): New. (binding_map::remove_overlapping_bindings): New decl. (binding_map::get_overlapping_bindings): New decl. (binding_cluster::validate): New decl. (binding_cluster::bind): Drop enum binding_kind. (binding_cluster::fill_region): New decl. (binding_cluster::get_binding): Drop enum binding_kind. (binding_cluster::get_binding_recursive): Likewise. (binding_cluster::get_overlapping_bindings): Delete. (store::validate): New decl. (store::set_value): Drop enum binding_kind. (store::fill_region): New decl. (store_manager::get_concrete_binding): Drop enum binding_kind. (store_manager::get_symbolic_binding): Likewise. * svalue.cc (svalue::cmp_ptr): Handle SK_REPEATED and SK_BITS_WITHIN. (svalue::extract_bit_range): New. (svalue::maybe_fold_bits_within): New. (constant_svalue::maybe_fold_bits_within): New. (unknown_svalue::maybe_fold_bits_within): New. (unaryop_svalue::maybe_fold_bits_within): New. (repeated_svalue::repeated_svalue): New. (repeated_svalue::dump_to_pp): New. (repeated_svalue::accept): New. (repeated_svalue::all_zeroes_p): New. (repeated_svalue::maybe_fold_bits_within): New. (bits_within_svalue::bits_within_svalue): New. (bits_within_svalue::dump_to_pp): New. (bits_within_svalue::maybe_fold_bits_within): New. (bits_within_svalue::accept): New. (bits_within_svalue::implicitly_live_p): New. (compound_svalue::maybe_fold_bits_within): New. * svalue.h (enum svalue_kind): Add SK_REPEATED and SK_BITS_WITHIN. (svalue::dyn_cast_repeated_svalue): New. (svalue::dyn_cast_bits_within_svalue): New. (svalue::extract_bit_range): New decl. (svalue::maybe_fold_bits_within): New vfunc decl. (region_svalue::key_t::mark_empty): Use 2 rather than NULL_TREE. (region_svalue::key_t::is_empty): Likewise. (default_hash_traits<region_svalue::key_t>::empty_zero_p): Make false. (constant_svalue::maybe_fold_bits_within): New. (unknown_svalue::maybe_fold_bits_within): New. (poisoned_svalue::key_t::mark_empty): Use 2 rather than NULL_TREE. (poisoned_svalue::key_t::is_empty): Likewise. (default_hash_traits<poisoned_svalue::key_t>::empty_zero_p): Make false. (setjmp_svalue::key_t::mark_empty): Use 2 rather than NULL_TREE. (setjmp_svalue::key_t::is_empty): Likewise. (default_hash_traits<setjmp_svalue::key_t>::empty_zero_p): Make false. (unaryop_svalue::key_t::mark_empty): Use 2 rather than NULL_TREE. (unaryop_svalue::key_t::is_empty): Likewise. (unaryop_svalue::maybe_fold_bits_within): New. (default_hash_traits<unaryop_svalue::key_t>::empty_zero_p): Make false. (binop_svalue::key_t::mark_empty): Use 2 rather than NULL_TREE. (binop_svalue::key_t::is_empty): Likewise. (default_hash_traits<binop_svalue::key_t>::empty_zero_p): Make false. (sub_svalue::key_t::mark_empty): Use 2 rather than NULL_TREE. (sub_svalue::key_t::is_empty): Likewise. (default_hash_traits<sub_svalue::key_t>::empty_zero_p): Make false. (class repeated_svalue): New. (is_a_helper <const repeated_svalue *>::test): New. (struct default_hash_traits<repeated_svalue::key_t>): New. (class bits_within_svalue): New. (is_a_helper <const bits_within_svalue *>::test): New. (struct default_hash_traits<bits_within_svalue::key_t>): New. (widening_svalue::key_t::mark_empty): Use 2 rather than NULL_TREE. (widening_svalue::key_t::is_empty): Likewise. (default_hash_traits<widening_svalue::key_t>::empty_zero_p): Make false. (compound_svalue::key_t::mark_empty): Use 2 rather than NULL_TREE. (compound_svalue::key_t::is_empty): Likewise. (compound_svalue::maybe_fold_bits_within): New. (default_hash_traits<compound_svalue::key_t>::empty_zero_p): Make false. gcc/testsuite/ChangeLog: PR analyzer/95006 * gcc.dg/analyzer/clobbers-1.c: New test. * gcc.dg/analyzer/clobbers-2.c: New test. * gcc.dg/analyzer/data-model-1.c (test_26): Mark xfail as fixed. (test_28): Likewise. (test_52): Likewise. Add coverage for end of buffer. * gcc.dg/analyzer/explode-1.c: Add leak warning. * gcc.dg/analyzer/memset-1.c (test_3): Mark xfail as fixed. (test_4): Use char. Mark xfail as fixed. (test_6b): New. (test_7): Mark xfail as fixed. Add coverage for start of buffer. (test_8): New. (test_9): New. * gcc.dg/analyzer/memset-CVE-2017-18549-1.c: New test. * gcc.dg/analyzer/symbolic-8.c: New test. Signed-off-by: David Malcolm <dmalcolm@redhat.com> --- gcc/analyzer/analyzer.h | 5 + gcc/analyzer/engine.cc | 5 + gcc/analyzer/program-state.cc | 1 + gcc/analyzer/region-model-impl-calls.cc | 39 +- gcc/analyzer/region-model-manager.cc | 313 ++++++++- gcc/analyzer/region-model.cc | 72 +- gcc/analyzer/region-model.h | 27 + gcc/analyzer/region.cc | 230 ++++-- gcc/analyzer/region.h | 125 +++- gcc/analyzer/store.cc | 653 ++++++++++++------ gcc/analyzer/store.h | 157 ++--- gcc/analyzer/svalue.cc | 381 ++++++++++ gcc/analyzer/svalue.h | 262 ++++++- gcc/testsuite/gcc.dg/analyzer/clobbers-1.c | 98 +++ gcc/testsuite/gcc.dg/analyzer/clobbers-2.c | 72 ++ gcc/testsuite/gcc.dg/analyzer/data-model-1.c | 24 +- gcc/testsuite/gcc.dg/analyzer/explode-1.c | 2 +- gcc/testsuite/gcc.dg/analyzer/memset-1.c | 118 +++- .../gcc.dg/analyzer/memset-CVE-2017-18549-1.c | 107 +++ gcc/testsuite/gcc.dg/analyzer/symbolic-8.c | 11 + 20 files changed, 2207 insertions(+), 495 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/analyzer/clobbers-1.c create mode 100644 gcc/testsuite/gcc.dg/analyzer/clobbers-2.c create mode 100644 gcc/testsuite/gcc.dg/analyzer/memset-CVE-2017-18549-1.c create mode 100644 gcc/testsuite/gcc.dg/analyzer/symbolic-8.c