diff options
Diffstat (limited to 'gcc/analyzer/svalue.h')
| -rw-r--r-- | gcc/analyzer/svalue.h | 448 |
1 files changed, 416 insertions, 32 deletions
diff --git a/gcc/analyzer/svalue.h b/gcc/analyzer/svalue.h index 672a89c..63f7d15 100644 --- a/gcc/analyzer/svalue.h +++ b/gcc/analyzer/svalue.h @@ -41,11 +41,14 @@ enum svalue_kind SK_UNARYOP, SK_BINOP, SK_SUB, + SK_REPEATED, + SK_BITS_WITHIN, SK_UNMERGEABLE, SK_PLACEHOLDER, SK_WIDENING, SK_COMPOUND, - SK_CONJURED + SK_CONJURED, + SK_ASM_OUTPUT }; /* svalue and its subclasses. @@ -63,13 +66,18 @@ 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. widening_svalue (SK_WIDENING): a merger of two svalues (possibly in an iteration). compound_svalue (SK_COMPOUND): a mapping of bit-ranges to svalues - conjured_svalue (SK_CONJURED): a value arising from a stmt. */ + conjured_svalue (SK_CONJURED): a value arising from a stmt + asm_output_svalue (SK_ASM_OUTPUT): an output from a deterministic + asm stmt. */ /* An abstract base class representing a value held by a region of memory. */ @@ -107,6 +115,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 * @@ -115,8 +127,11 @@ public: dyn_cast_compound_svalue () const { return NULL; } virtual const conjured_svalue * dyn_cast_conjured_svalue () const { return NULL; } + virtual const asm_output_svalue * + dyn_cast_asm_output_svalue () const { return NULL; } tree maybe_get_constant () const; + const region *maybe_get_region () const; const svalue *maybe_undo_cast () const; const svalue *unwrap_any_unmergeable () const; @@ -136,6 +151,25 @@ public: static int cmp_ptr (const svalue *, const svalue *); static int cmp_ptr_ptr (const void *, const void *); + 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; + + virtual bool all_zeroes_p () const; + + /* Can this svalue be involved in constraints and sm-state? + Most can, but UNKNOWN and POISONED svalues are singletons + per-type and thus it's meaningless for them to "have state". */ + virtual bool can_have_associated_state_p () const { return true; } + protected: svalue (complexity c, tree type) : m_complexity (c), m_type (type) @@ -173,9 +207,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; @@ -220,7 +254,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 { @@ -251,6 +285,13 @@ 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; + + bool all_zeroes_p () const FINAL OVERRIDE; + private: tree m_cst_expr; }; @@ -283,12 +324,23 @@ 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; + + /* Unknown values are singletons per-type, so can't have state. */ + bool can_have_associated_state_p () const FINAL OVERRIDE { return false; } }; /* An enum describing a particular kind of "poisoned" value. */ enum poison_kind { + /* For use to describe uninitialized memory. */ + POISON_KIND_UNINIT, + /* For use to describe freed memory. */ POISON_KIND_FREED, @@ -325,9 +377,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; @@ -343,8 +395,16 @@ 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; + enum poison_kind get_poison_kind () const { return m_kind; } + /* Poisoned svalues are singletons per-type, so can't have state. */ + bool can_have_associated_state_p () const FINAL OVERRIDE { return false; } + private: enum poison_kind m_kind; }; @@ -362,7 +422,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 { @@ -424,9 +484,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; @@ -465,7 +525,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 { @@ -546,9 +606,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; @@ -558,6 +618,7 @@ public: unaryop_svalue (tree type, enum tree_code op, const svalue *arg) : svalue (complexity (arg), type), m_op (op), m_arg (arg) { + gcc_assert (arg->can_have_associated_state_p ()); } enum svalue_kind get_kind () const FINAL OVERRIDE { return SK_UNARYOP; } @@ -572,6 +633,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; @@ -590,7 +656,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 { @@ -628,9 +694,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; @@ -645,6 +711,8 @@ public: type), m_op (op), m_arg0 (arg0), m_arg1 (arg1) { + gcc_assert (arg0->can_have_associated_state_p ()); + gcc_assert (arg1->can_have_associated_state_p ()); } enum svalue_kind get_kind () const FINAL OVERRIDE { return SK_BINOP; } @@ -681,7 +749,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 { @@ -717,9 +785,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; @@ -760,7 +828,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 FINAL OVERRIDE; + + 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 { @@ -840,7 +1083,7 @@ public: template <> template <> inline bool -is_a_helper <placeholder_svalue *>::test (svalue *sval) +is_a_helper <const placeholder_svalue *>::test (const svalue *sval) { return sval->get_kind () == SK_PLACEHOLDER; } @@ -886,9 +1129,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; @@ -911,6 +1154,8 @@ public: m_point (point.get_function_point ()), m_base_sval (base_sval), m_iter_sval (iter_sval) { + gcc_assert (base_sval->can_have_associated_state_p ()); + gcc_assert (iter_sval->can_have_associated_state_p ()); } enum svalue_kind get_kind () const FINAL OVERRIDE { return SK_WIDENING; } @@ -942,7 +1187,7 @@ public: template <> template <> inline bool -is_a_helper <widening_svalue *>::test (svalue *sval) +is_a_helper <const widening_svalue *>::test (const svalue *sval) { return sval->get_kind () == SK_WIDENING; } @@ -950,7 +1195,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 { @@ -998,9 +1243,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; @@ -1027,6 +1272,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); @@ -1038,7 +1288,7 @@ public: template <> template <> inline bool -is_a_helper <compound_svalue *>::test (svalue *sval) +is_a_helper <const compound_svalue *>::test (const svalue *sval) { return sval->get_kind () == SK_COMPOUND; } @@ -1046,7 +1296,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 { @@ -1071,8 +1321,6 @@ namespace ana { class conjured_svalue : public svalue { public: - typedef binding_map::iterator_t iterator_t; - /* A support class for uniquifying instances of conjured_svalue. */ struct key_t { @@ -1140,7 +1388,7 @@ public: template <> template <> inline bool -is_a_helper <conjured_svalue *>::test (svalue *sval) +is_a_helper <const conjured_svalue *>::test (const svalue *sval) { return sval->get_kind () == SK_CONJURED; } @@ -1151,4 +1399,140 @@ template <> struct default_hash_traits<conjured_svalue::key_t> static const bool empty_zero_p = true; }; +namespace ana { + +/* An output from a deterministic asm stmt, where we want to identify a + particular unknown value, rather than resorting to the unknown_value + singleton. + + Comparisons of variables that share the same asm_output_svalue are known + to be equal, even if we don't know what the value is. */ + +class asm_output_svalue : public svalue +{ +public: + /* Imposing an upper limit and using a (small) array allows key_t + to avoid memory management. */ + static const unsigned MAX_INPUTS = 2; + + /* A support class for uniquifying instances of asm_output_svalue. */ + struct key_t + { + key_t (tree type, + const char *asm_string, + unsigned output_idx, + const vec<const svalue *> &inputs) + : m_type (type), m_asm_string (asm_string), m_output_idx (output_idx), + m_num_inputs (inputs.length ()) + { + gcc_assert (inputs.length () <= MAX_INPUTS); + for (unsigned i = 0; i < m_num_inputs; i++) + m_input_arr[i] = inputs[i]; + } + + hashval_t hash () const + { + inchash::hash hstate; + hstate.add_ptr (m_type); + /* We don't bother hashing m_asm_str. */ + hstate.add_int (m_output_idx); + for (unsigned i = 0; i < m_num_inputs; i++) + hstate.add_ptr (m_input_arr[i]); + return hstate.end (); + } + + bool operator== (const key_t &other) const + { + if (!(m_type == other.m_type + && 0 == (strcmp (m_asm_string, other.m_asm_string)) + && m_output_idx == other.m_output_idx + && m_num_inputs == other.m_num_inputs)) + return false; + for (unsigned i = 0; i < m_num_inputs; i++) + if (m_input_arr[i] != other.m_input_arr[i]) + return false; + return true; + } + + /* Use m_asm_string to mark empty/deleted, as m_type can be NULL for + legitimate instances. */ + void mark_deleted () { m_asm_string = reinterpret_cast<const char *> (1); } + void mark_empty () { m_asm_string = NULL; } + bool is_deleted () const + { + return m_asm_string == reinterpret_cast<const char *> (1); + } + bool is_empty () const { return m_asm_string == NULL; } + + tree m_type; + const char *m_asm_string; + unsigned m_output_idx; + unsigned m_num_inputs; + const svalue *m_input_arr[MAX_INPUTS]; + }; + + asm_output_svalue (tree type, + const char *asm_string, + unsigned output_idx, + unsigned num_outputs, + const vec<const svalue *> &inputs) + : svalue (complexity::from_vec_svalue (inputs), type), + m_asm_string (asm_string), + m_output_idx (output_idx), + m_num_outputs (num_outputs), + m_num_inputs (inputs.length ()) + { + gcc_assert (inputs.length () <= MAX_INPUTS); + for (unsigned i = 0; i < m_num_inputs; i++) + m_input_arr[i] = inputs[i]; + } + + enum svalue_kind get_kind () const FINAL OVERRIDE { return SK_ASM_OUTPUT; } + const asm_output_svalue * + dyn_cast_asm_output_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 char *get_asm_string () const { return m_asm_string; } + unsigned get_output_idx () const { return m_output_idx; } + unsigned get_num_inputs () const { return m_num_inputs; } + const svalue *get_input (unsigned idx) const { return m_input_arr[idx]; } + + private: + void dump_input (pretty_printer *pp, + unsigned input_idx, + const svalue *sval, + bool simple) const; + unsigned input_idx_to_asm_idx (unsigned input_idx) const; + + const char *m_asm_string; + unsigned m_output_idx; + + /* We capture this so that we can offset the input indices + to match the %0, %1, %2 in the asm_string when dumping. */ + unsigned m_num_outputs; + + unsigned m_num_inputs; + const svalue *m_input_arr[MAX_INPUTS]; +}; + +} // namespace ana + +template <> +template <> +inline bool +is_a_helper <const asm_output_svalue *>::test (const svalue *sval) +{ + return sval->get_kind () == SK_ASM_OUTPUT; +} + +template <> struct default_hash_traits<asm_output_svalue::key_t> +: public member_function_hash_traits<asm_output_svalue::key_t> +{ + static const bool empty_zero_p = true; +}; #endif /* GCC_ANALYZER_SVALUE_H */ |