1 /* Classes for modeling the state of memory.
2 Copyright (C) 2019-2021 Free Software Foundation, Inc.
3 Contributed by David Malcolm <dmalcolm@redhat.com>.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it
8 under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
12 GCC is distributed in the hope that it will be useful, but
13 WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
23 #include "coretypes.h"
26 #include "basic-block.h"
28 #include "gimple-iterator.h"
29 #include "diagnostic-core.h"
34 #include "stringpool.h"
37 #include "fold-const.h"
38 #include "tree-pretty-print.h"
39 #include "diagnostic-color.h"
40 #include "diagnostic-metadata.h"
46 #include "analyzer/analyzer.h"
47 #include "analyzer/analyzer-logging.h"
48 #include "ordered-hash-map.h"
53 #include "analyzer/supergraph.h"
55 #include "analyzer/call-string.h"
56 #include "analyzer/program-point.h"
57 #include "analyzer/store.h"
58 #include "analyzer/region-model.h"
59 #include "analyzer/constraint-manager.h"
60 #include "diagnostic-event-id.h"
61 #include "analyzer/sm.h"
62 #include "diagnostic-event-id.h"
63 #include "analyzer/sm.h"
64 #include "analyzer/pending-diagnostic.h"
65 #include "analyzer/region-model-reachability.h"
66 #include "analyzer/analyzer-selftests.h"
67 #include "analyzer/program-state.h"
68 #include "stor-layout.h"
70 #include "tree-object-size.h"
76 /* Dump T to PP in language-independent form, for debugging/logging/dumping
80 dump_tree (pretty_printer
*pp
, tree t
)
82 dump_generic_node (pp
, t
, 0, TDF_SLIM
, 0);
85 /* Dump T to PP in language-independent form in quotes, for
86 debugging/logging/dumping purposes. */
89 dump_quoted_tree (pretty_printer
*pp
, tree t
)
91 pp_begin_quote (pp
, pp_show_color (pp
));
93 pp_end_quote (pp
, pp_show_color (pp
));
96 /* Equivalent to pp_printf (pp, "%qT", t), to avoid nesting pp_printf
97 calls within other pp_printf calls.
99 default_tree_printer handles 'T' and some other codes by calling
100 dump_generic_node (pp, t, 0, TDF_SLIM, 0);
101 dump_generic_node calls pp_printf in various places, leading to
104 Ideally pp_printf could be made to be reentrant, but in the meantime
105 this function provides a workaround. */
108 print_quoted_type (pretty_printer
*pp
, tree t
)
110 pp_begin_quote (pp
, pp_show_color (pp
));
111 dump_generic_node (pp
, t
, 0, TDF_SLIM
, 0);
112 pp_end_quote (pp
, pp_show_color (pp
));
115 /* class region_to_value_map. */
117 /* Assignment operator for region_to_value_map. */
119 region_to_value_map
&
120 region_to_value_map::operator= (const region_to_value_map
&other
)
123 for (auto iter
: other
.m_hash_map
)
125 const region
*reg
= iter
.first
;
126 const svalue
*sval
= iter
.second
;
127 m_hash_map
.put (reg
, sval
);
132 /* Equality operator for region_to_value_map. */
135 region_to_value_map::operator== (const region_to_value_map
&other
) const
137 if (m_hash_map
.elements () != other
.m_hash_map
.elements ())
140 for (auto iter
: *this)
142 const region
*reg
= iter
.first
;
143 const svalue
*sval
= iter
.second
;
144 const svalue
* const *other_slot
= other
.get (reg
);
145 if (other_slot
== NULL
)
147 if (sval
!= *other_slot
)
154 /* Dump this object to PP. */
157 region_to_value_map::dump_to_pp (pretty_printer
*pp
, bool simple
,
158 bool multiline
) const
160 auto_vec
<const region
*> regs
;
161 for (iterator iter
= begin (); iter
!= end (); ++iter
)
162 regs
.safe_push ((*iter
).first
);
163 regs
.qsort (region::cmp_ptr_ptr
);
167 pp_string (pp
, " {");
170 FOR_EACH_VEC_ELT (regs
, i
, reg
)
175 pp_string (pp
, ", ");
176 reg
->dump_to_pp (pp
, simple
);
177 pp_string (pp
, ": ");
178 const svalue
*sval
= *get (reg
);
179 sval
->dump_to_pp (pp
, true);
187 /* Dump this object to stderr. */
190 region_to_value_map::dump (bool simple
) const
193 pp_format_decoder (&pp
) = default_tree_printer
;
194 pp_show_color (&pp
) = pp_show_color (global_dc
->printer
);
195 pp
.buffer
->stream
= stderr
;
196 dump_to_pp (&pp
, simple
, true);
202 /* Attempt to merge THIS with OTHER, writing the result
205 For now, write (region, value) mappings that are in common between THIS
206 and OTHER to OUT, effectively taking the intersection, rather than
207 rejecting differences. */
210 region_to_value_map::can_merge_with_p (const region_to_value_map
&other
,
211 region_to_value_map
*out
) const
213 for (auto iter
: *this)
215 const region
*iter_reg
= iter
.first
;
216 const svalue
*iter_sval
= iter
.second
;
217 const svalue
* const * other_slot
= other
.get (iter_reg
);
219 if (iter_sval
== *other_slot
)
220 out
->put (iter_reg
, iter_sval
);
225 /* Purge any state involving SVAL. */
228 region_to_value_map::purge_state_involving (const svalue
*sval
)
230 auto_vec
<const region
*> to_purge
;
231 for (auto iter
: *this)
233 const region
*iter_reg
= iter
.first
;
234 const svalue
*iter_sval
= iter
.second
;
235 if (iter_reg
->involves_p (sval
) || iter_sval
->involves_p (sval
))
236 to_purge
.safe_push (iter_reg
);
238 for (auto iter
: to_purge
)
239 m_hash_map
.remove (iter
);
242 /* class region_model. */
244 /* Ctor for region_model: construct an "empty" model. */
246 region_model::region_model (region_model_manager
*mgr
)
247 : m_mgr (mgr
), m_store (), m_current_frame (NULL
),
250 m_constraints
= new constraint_manager (mgr
);
253 /* region_model's copy ctor. */
255 region_model::region_model (const region_model
&other
)
256 : m_mgr (other
.m_mgr
), m_store (other
.m_store
),
257 m_constraints (new constraint_manager (*other
.m_constraints
)),
258 m_current_frame (other
.m_current_frame
),
259 m_dynamic_extents (other
.m_dynamic_extents
)
263 /* region_model's dtor. */
265 region_model::~region_model ()
267 delete m_constraints
;
270 /* region_model's assignment operator. */
273 region_model::operator= (const region_model
&other
)
275 /* m_mgr is const. */
276 gcc_assert (m_mgr
== other
.m_mgr
);
278 m_store
= other
.m_store
;
280 delete m_constraints
;
281 m_constraints
= new constraint_manager (*other
.m_constraints
);
283 m_current_frame
= other
.m_current_frame
;
285 m_dynamic_extents
= other
.m_dynamic_extents
;
290 /* Equality operator for region_model.
292 Amongst other things this directly compares the stores and the constraint
293 managers, so for this to be meaningful both this and OTHER should
294 have been canonicalized. */
297 region_model::operator== (const region_model
&other
) const
299 /* We can only compare instances that use the same manager. */
300 gcc_assert (m_mgr
== other
.m_mgr
);
302 if (m_store
!= other
.m_store
)
305 if (*m_constraints
!= *other
.m_constraints
)
308 if (m_current_frame
!= other
.m_current_frame
)
311 if (m_dynamic_extents
!= other
.m_dynamic_extents
)
314 gcc_checking_assert (hash () == other
.hash ());
319 /* Generate a hash value for this region_model. */
322 region_model::hash () const
324 hashval_t result
= m_store
.hash ();
325 result
^= m_constraints
->hash ();
329 /* Dump a representation of this model to PP, showing the
330 stack, the store, and any constraints.
331 Use SIMPLE to control how svalues and regions are printed. */
334 region_model::dump_to_pp (pretty_printer
*pp
, bool simple
,
335 bool multiline
) const
338 pp_printf (pp
, "stack depth: %i", get_stack_depth ());
342 pp_string (pp
, " {");
343 for (const frame_region
*iter_frame
= m_current_frame
; iter_frame
;
344 iter_frame
= iter_frame
->get_calling_frame ())
348 else if (iter_frame
!= m_current_frame
)
349 pp_string (pp
, ", ");
350 pp_printf (pp
, "frame (index %i): ", iter_frame
->get_index ());
351 iter_frame
->dump_to_pp (pp
, simple
);
360 pp_string (pp
, ", {");
361 m_store
.dump_to_pp (pp
, simple
, multiline
,
362 m_mgr
->get_store_manager ());
366 /* Dump constraints. */
367 pp_string (pp
, "constraint_manager:");
371 pp_string (pp
, " {");
372 m_constraints
->dump_to_pp (pp
, multiline
);
376 /* Dump sizes of dynamic regions, if any are known. */
377 if (!m_dynamic_extents
.is_empty ())
379 pp_string (pp
, "dynamic_extents:");
380 m_dynamic_extents
.dump_to_pp (pp
, simple
, multiline
);
384 /* Dump a representation of this model to FILE. */
387 region_model::dump (FILE *fp
, bool simple
, bool multiline
) const
390 pp_format_decoder (&pp
) = default_tree_printer
;
391 pp_show_color (&pp
) = pp_show_color (global_dc
->printer
);
392 pp
.buffer
->stream
= fp
;
393 dump_to_pp (&pp
, simple
, multiline
);
398 /* Dump a multiline representation of this model to stderr. */
401 region_model::dump (bool simple
) const
403 dump (stderr
, simple
, true);
406 /* Dump a multiline representation of this model to stderr. */
409 region_model::debug () const
414 /* Assert that this object is valid. */
417 region_model::validate () const
422 /* Canonicalize the store and constraints, to maximize the chance of
423 equality between region_model instances. */
426 region_model::canonicalize ()
428 m_store
.canonicalize (m_mgr
->get_store_manager ());
429 m_constraints
->canonicalize ();
432 /* Return true if this region_model is in canonical form. */
435 region_model::canonicalized_p () const
437 region_model
copy (*this);
438 copy
.canonicalize ();
439 return *this == copy
;
442 /* See the comment for store::loop_replay_fixup. */
445 region_model::loop_replay_fixup (const region_model
*dst_state
)
447 m_store
.loop_replay_fixup (dst_state
->get_store (), m_mgr
);
450 /* A subclass of pending_diagnostic for complaining about uses of
453 class poisoned_value_diagnostic
454 : public pending_diagnostic_subclass
<poisoned_value_diagnostic
>
457 poisoned_value_diagnostic (tree expr
, enum poison_kind pkind
)
458 : m_expr (expr
), m_pkind (pkind
)
461 const char *get_kind () const FINAL OVERRIDE
{ return "poisoned_value_diagnostic"; }
463 bool use_of_uninit_p () const FINAL OVERRIDE
465 return m_pkind
== POISON_KIND_UNINIT
;
468 bool operator== (const poisoned_value_diagnostic
&other
) const
470 return m_expr
== other
.m_expr
;
473 bool emit (rich_location
*rich_loc
) FINAL OVERRIDE
479 case POISON_KIND_UNINIT
:
481 diagnostic_metadata m
;
482 m
.add_cwe (457); /* "CWE-457: Use of Uninitialized Variable". */
483 return warning_meta (rich_loc
, m
,
484 OPT_Wanalyzer_use_of_uninitialized_value
,
485 "use of uninitialized value %qE",
489 case POISON_KIND_FREED
:
491 diagnostic_metadata m
;
492 m
.add_cwe (416); /* "CWE-416: Use After Free". */
493 return warning_meta (rich_loc
, m
,
494 OPT_Wanalyzer_use_after_free
,
495 "use after %<free%> of %qE",
499 case POISON_KIND_POPPED_STACK
:
501 /* TODO: which CWE? */
504 OPT_Wanalyzer_use_of_pointer_in_stale_stack_frame
,
505 "dereferencing pointer %qE to within stale stack frame",
512 label_text
describe_final_event (const evdesc::final_event
&ev
) FINAL OVERRIDE
518 case POISON_KIND_UNINIT
:
519 return ev
.formatted_print ("use of uninitialized value %qE here",
521 case POISON_KIND_FREED
:
522 return ev
.formatted_print ("use after %<free%> of %qE here",
524 case POISON_KIND_POPPED_STACK
:
525 return ev
.formatted_print
526 ("dereferencing pointer %qE to within stale stack frame",
533 enum poison_kind m_pkind
;
536 /* A subclass of pending_diagnostic for complaining about shifts
537 by negative counts. */
539 class shift_count_negative_diagnostic
540 : public pending_diagnostic_subclass
<shift_count_negative_diagnostic
>
543 shift_count_negative_diagnostic (const gassign
*assign
, tree count_cst
)
544 : m_assign (assign
), m_count_cst (count_cst
)
547 const char *get_kind () const FINAL OVERRIDE
549 return "shift_count_negative_diagnostic";
552 bool operator== (const shift_count_negative_diagnostic
&other
) const
554 return (m_assign
== other
.m_assign
555 && same_tree_p (m_count_cst
, other
.m_count_cst
));
558 bool emit (rich_location
*rich_loc
) FINAL OVERRIDE
560 return warning_at (rich_loc
, OPT_Wanalyzer_shift_count_negative
,
561 "shift by negative count (%qE)", m_count_cst
);
564 label_text
describe_final_event (const evdesc::final_event
&ev
) FINAL OVERRIDE
566 return ev
.formatted_print ("shift by negative amount here (%qE)", m_count_cst
);
570 const gassign
*m_assign
;
574 /* A subclass of pending_diagnostic for complaining about shifts
575 by counts >= the width of the operand type. */
577 class shift_count_overflow_diagnostic
578 : public pending_diagnostic_subclass
<shift_count_overflow_diagnostic
>
581 shift_count_overflow_diagnostic (const gassign
*assign
,
582 int operand_precision
,
584 : m_assign (assign
), m_operand_precision (operand_precision
),
585 m_count_cst (count_cst
)
588 const char *get_kind () const FINAL OVERRIDE
590 return "shift_count_overflow_diagnostic";
593 bool operator== (const shift_count_overflow_diagnostic
&other
) const
595 return (m_assign
== other
.m_assign
596 && m_operand_precision
== other
.m_operand_precision
597 && same_tree_p (m_count_cst
, other
.m_count_cst
));
600 bool emit (rich_location
*rich_loc
) FINAL OVERRIDE
602 return warning_at (rich_loc
, OPT_Wanalyzer_shift_count_overflow
,
603 "shift by count (%qE) >= precision of type (%qi)",
604 m_count_cst
, m_operand_precision
);
607 label_text
describe_final_event (const evdesc::final_event
&ev
) FINAL OVERRIDE
609 return ev
.formatted_print ("shift by count %qE here", m_count_cst
);
613 const gassign
*m_assign
;
614 int m_operand_precision
;
618 /* If ASSIGN is a stmt that can be modelled via
619 set_value (lhs_reg, SVALUE, CTXT)
620 for some SVALUE, get the SVALUE.
621 Otherwise return NULL. */
624 region_model::get_gassign_result (const gassign
*assign
,
625 region_model_context
*ctxt
)
627 tree lhs
= gimple_assign_lhs (assign
);
628 tree rhs1
= gimple_assign_rhs1 (assign
);
629 enum tree_code op
= gimple_assign_rhs_code (assign
);
635 case POINTER_PLUS_EXPR
:
637 /* e.g. "_1 = a_10(D) + 12;" */
639 tree offset
= gimple_assign_rhs2 (assign
);
641 const svalue
*ptr_sval
= get_rvalue (ptr
, ctxt
);
642 const svalue
*offset_sval
= get_rvalue (offset
, ctxt
);
643 /* Quoting tree.def, "the second operand [of a POINTER_PLUS_EXPR]
644 is an integer of type sizetype". */
645 offset_sval
= m_mgr
->get_or_create_cast (size_type_node
, offset_sval
);
647 const svalue
*sval_binop
648 = m_mgr
->get_or_create_binop (TREE_TYPE (lhs
), op
,
649 ptr_sval
, offset_sval
);
654 case POINTER_DIFF_EXPR
:
656 /* e.g. "_1 = p_2(D) - q_3(D);". */
657 tree rhs2
= gimple_assign_rhs2 (assign
);
658 const svalue
*rhs1_sval
= get_rvalue (rhs1
, ctxt
);
659 const svalue
*rhs2_sval
= get_rvalue (rhs2
, ctxt
);
661 // TODO: perhaps fold to zero if they're known to be equal?
663 const svalue
*sval_binop
664 = m_mgr
->get_or_create_binop (TREE_TYPE (lhs
), op
,
665 rhs1_sval
, rhs2_sval
);
670 /* Assignments of the form
671 set_value (lvalue (LHS), rvalue (EXPR))
673 We already have the lvalue for the LHS above, as "lhs_reg". */
674 case ADDR_EXPR
: /* LHS = &RHS; */
676 case COMPONENT_REF
: /* LHS = op0.op1; */
683 case SSA_NAME
: /* LHS = VAR; */
684 case VAR_DECL
: /* LHS = VAR; */
685 case PARM_DECL
:/* LHS = VAR; */
688 return get_rvalue (rhs1
, ctxt
);
698 case VIEW_CONVERT_EXPR
:
701 const svalue
*rhs_sval
= get_rvalue (rhs1
, ctxt
);
702 const svalue
*sval_unaryop
703 = m_mgr
->get_or_create_unaryop (TREE_TYPE (lhs
), op
, rhs_sval
);
716 tree rhs2
= gimple_assign_rhs2 (assign
);
718 const svalue
*rhs1_sval
= get_rvalue (rhs1
, ctxt
);
719 const svalue
*rhs2_sval
= get_rvalue (rhs2
, ctxt
);
721 if (TREE_TYPE (lhs
) == boolean_type_node
)
723 /* Consider constraints between svalues. */
724 tristate t
= eval_condition (rhs1_sval
, op
, rhs2_sval
);
726 return m_mgr
->get_or_create_constant_svalue
727 (t
.is_true () ? boolean_true_node
: boolean_false_node
);
730 /* Otherwise, generate a symbolic binary op. */
731 const svalue
*sval_binop
732 = m_mgr
->get_or_create_binop (TREE_TYPE (lhs
), op
,
733 rhs1_sval
, rhs2_sval
);
741 case MULT_HIGHPART_EXPR
:
764 tree rhs2
= gimple_assign_rhs2 (assign
);
766 const svalue
*rhs1_sval
= get_rvalue (rhs1
, ctxt
);
767 const svalue
*rhs2_sval
= get_rvalue (rhs2
, ctxt
);
769 if (ctxt
&& (op
== LSHIFT_EXPR
|| op
== RSHIFT_EXPR
))
771 /* "INT34-C. Do not shift an expression by a negative number of bits
772 or by greater than or equal to the number of bits that exist in
774 if (const tree rhs2_cst
= rhs2_sval
->maybe_get_constant ())
775 if (TREE_CODE (rhs2_cst
) == INTEGER_CST
)
777 if (tree_int_cst_sgn (rhs2_cst
) < 0)
778 ctxt
->warn (new shift_count_negative_diagnostic
780 else if (compare_tree_int (rhs2_cst
,
781 TYPE_PRECISION (TREE_TYPE (rhs1
)))
783 ctxt
->warn (new shift_count_overflow_diagnostic
784 (assign
, TYPE_PRECISION (TREE_TYPE (rhs1
)),
789 const svalue
*sval_binop
790 = m_mgr
->get_or_create_binop (TREE_TYPE (lhs
), op
,
791 rhs1_sval
, rhs2_sval
);
795 /* Vector expressions. In theory we could implement these elementwise,
796 but for now, simply return unknown values. */
797 case VEC_DUPLICATE_EXPR
:
798 case VEC_SERIES_EXPR
:
801 case VEC_WIDEN_MULT_HI_EXPR
:
802 case VEC_WIDEN_MULT_LO_EXPR
:
803 case VEC_WIDEN_MULT_EVEN_EXPR
:
804 case VEC_WIDEN_MULT_ODD_EXPR
:
805 case VEC_UNPACK_HI_EXPR
:
806 case VEC_UNPACK_LO_EXPR
:
807 case VEC_UNPACK_FLOAT_HI_EXPR
:
808 case VEC_UNPACK_FLOAT_LO_EXPR
:
809 case VEC_UNPACK_FIX_TRUNC_HI_EXPR
:
810 case VEC_UNPACK_FIX_TRUNC_LO_EXPR
:
811 case VEC_PACK_TRUNC_EXPR
:
812 case VEC_PACK_SAT_EXPR
:
813 case VEC_PACK_FIX_TRUNC_EXPR
:
814 case VEC_PACK_FLOAT_EXPR
:
815 case VEC_WIDEN_LSHIFT_HI_EXPR
:
816 case VEC_WIDEN_LSHIFT_LO_EXPR
:
817 return m_mgr
->get_or_create_unknown_svalue (TREE_TYPE (lhs
));
821 /* Check for SVAL being poisoned, adding a warning to CTXT.
822 Return SVAL, or, if a warning is added, another value, to avoid
823 repeatedly complaining about the same poisoned value in followup code. */
826 region_model::check_for_poison (const svalue
*sval
,
828 region_model_context
*ctxt
) const
833 if (const poisoned_svalue
*poisoned_sval
= sval
->dyn_cast_poisoned_svalue ())
835 /* If we have an SSA name for a temporary, we don't want to print
837 Poisoned values are shared by type, and so we can't reconstruct
838 the tree other than via the def stmts, using
839 fixup_tree_for_diagnostic. */
840 tree diag_arg
= fixup_tree_for_diagnostic (expr
);
841 enum poison_kind pkind
= poisoned_sval
->get_poison_kind ();
842 if (ctxt
->warn (new poisoned_value_diagnostic (diag_arg
, pkind
)))
844 /* We only want to report use of a poisoned value at the first
845 place it gets used; return an unknown value to avoid generating
846 a chain of followup warnings. */
847 sval
= m_mgr
->get_or_create_unknown_svalue (sval
->get_type ());
856 /* Update this model for the ASSIGN stmt, using CTXT to report any
860 region_model::on_assignment (const gassign
*assign
, region_model_context
*ctxt
)
862 tree lhs
= gimple_assign_lhs (assign
);
863 tree rhs1
= gimple_assign_rhs1 (assign
);
865 const region
*lhs_reg
= get_lvalue (lhs
, ctxt
);
867 /* Most assignments are handled by:
868 set_value (lhs_reg, SVALUE, CTXT)
870 if (const svalue
*sval
= get_gassign_result (assign
, ctxt
))
872 tree expr
= get_diagnostic_tree_for_gassign (assign
);
873 check_for_poison (sval
, expr
, ctxt
);
874 set_value (lhs_reg
, sval
, ctxt
);
878 enum tree_code op
= gimple_assign_rhs_code (assign
);
884 sorry_at (assign
->location
, "unhandled assignment op: %qs",
885 get_tree_code_name (op
));
886 const svalue
*unknown_sval
887 = m_mgr
->get_or_create_unknown_svalue (TREE_TYPE (lhs
));
888 set_value (lhs_reg
, unknown_sval
, ctxt
);
894 if (TREE_CLOBBER_P (rhs1
))
896 /* e.g. "x ={v} {CLOBBER};" */
897 clobber_region (lhs_reg
);
901 /* Any CONSTRUCTOR that survives to this point is either
902 just a zero-init of everything, or a vector. */
903 if (!CONSTRUCTOR_NO_CLEARING (rhs1
))
904 zero_fill_region (lhs_reg
);
908 FOR_EACH_CONSTRUCTOR_ELT (CONSTRUCTOR_ELTS (rhs1
), ix
, index
, val
)
910 gcc_assert (TREE_CODE (TREE_TYPE (rhs1
)) == VECTOR_TYPE
);
912 index
= build_int_cst (integer_type_node
, ix
);
913 gcc_assert (TREE_CODE (index
) == INTEGER_CST
);
914 const svalue
*index_sval
915 = m_mgr
->get_or_create_constant_svalue (index
);
916 gcc_assert (index_sval
);
917 const region
*sub_reg
918 = m_mgr
->get_element_region (lhs_reg
,
921 const svalue
*val_sval
= get_rvalue (val
, ctxt
);
922 set_value (sub_reg
, val_sval
, ctxt
);
930 /* e.g. "struct s2 x = {{'A', 'B', 'C', 'D'}};". */
931 const svalue
*rhs_sval
= get_rvalue (rhs1
, ctxt
);
932 m_store
.set_value (m_mgr
->get_store_manager(), lhs_reg
, rhs_sval
,
933 ctxt
? ctxt
->get_uncertainty () : NULL
);
939 /* A pending_diagnostic subclass for implementing "__analyzer_dump_path". */
941 class dump_path_diagnostic
942 : public pending_diagnostic_subclass
<dump_path_diagnostic
>
945 bool emit (rich_location
*richloc
) FINAL OVERRIDE
947 inform (richloc
, "path");
951 const char *get_kind () const FINAL OVERRIDE
{ return "dump_path_diagnostic"; }
953 bool operator== (const dump_path_diagnostic
&) const
959 /* Handle the pre-sm-state part of STMT, modifying this object in-place.
960 Write true to *OUT_TERMINATE_PATH if the path should be terminated.
961 Write true to *OUT_UNKNOWN_SIDE_EFFECTS if the stmt has unknown
965 region_model::on_stmt_pre (const gimple
*stmt
,
966 bool *out_terminate_path
,
967 bool *out_unknown_side_effects
,
968 region_model_context
*ctxt
)
970 switch (gimple_code (stmt
))
978 const gassign
*assign
= as_a
<const gassign
*> (stmt
);
979 on_assignment (assign
, ctxt
);
985 const gasm
*asm_stmt
= as_a
<const gasm
*> (stmt
);
986 on_asm_stmt (asm_stmt
, ctxt
);
992 /* Track whether we have a gcall to a function that's not recognized by
993 anything, for which we don't have a function body, or for which we
994 don't know the fndecl. */
995 const gcall
*call
= as_a
<const gcall
*> (stmt
);
997 /* Debugging/test support. */
998 if (is_special_named_call_p (call
, "__analyzer_describe", 2))
999 impl_call_analyzer_describe (call
, ctxt
);
1000 else if (is_special_named_call_p (call
, "__analyzer_dump_capacity", 1))
1001 impl_call_analyzer_dump_capacity (call
, ctxt
);
1002 else if (is_special_named_call_p (call
, "__analyzer_dump_path", 0))
1004 /* Handle the builtin "__analyzer_dump_path" by queuing a
1005 diagnostic at this exploded_node. */
1006 ctxt
->warn (new dump_path_diagnostic ());
1008 else if (is_special_named_call_p (call
, "__analyzer_dump_region_model",
1011 /* Handle the builtin "__analyzer_dump_region_model" by dumping
1012 the region model's state to stderr. */
1015 else if (is_special_named_call_p (call
, "__analyzer_eval", 1))
1016 impl_call_analyzer_eval (call
, ctxt
);
1017 else if (is_special_named_call_p (call
, "__analyzer_break", 0))
1019 /* Handle the builtin "__analyzer_break" by triggering a
1021 /* TODO: is there a good cross-platform way to do this? */
1024 else if (is_special_named_call_p (call
,
1025 "__analyzer_dump_exploded_nodes",
1028 /* This is handled elsewhere. */
1031 *out_unknown_side_effects
= on_call_pre (call
, ctxt
,
1032 out_terminate_path
);
1038 const greturn
*return_
= as_a
<const greturn
*> (stmt
);
1039 on_return (return_
, ctxt
);
1045 /* Update this model for the CALL stmt, using CTXT to report any
1046 diagnostics - the first half.
1048 Updates to the region_model that should be made *before* sm-states
1049 are updated are done here; other updates to the region_model are done
1050 in region_model::on_call_post.
1052 Return true if the function call has unknown side effects (it wasn't
1053 recognized and we don't have a body for it, or are unable to tell which
1056 Write true to *OUT_TERMINATE_PATH if this execution path should be
1057 terminated (e.g. the function call terminates the process). */
1060 region_model::on_call_pre (const gcall
*call
, region_model_context
*ctxt
,
1061 bool *out_terminate_path
)
1063 call_details
cd (call
, this, ctxt
);
1065 bool unknown_side_effects
= false;
1067 /* Some of the cases below update the lhs of the call based on the
1068 return value, but not all. Provide a default value, which may
1069 get overwritten below. */
1070 if (tree lhs
= gimple_call_lhs (call
))
1072 const region
*lhs_region
= get_lvalue (lhs
, ctxt
);
1074 = m_mgr
->get_or_create_conjured_svalue (TREE_TYPE (lhs
), call
,
1076 purge_state_involving (sval
, ctxt
);
1077 set_value (lhs_region
, sval
, ctxt
);
1080 if (gimple_call_internal_p (call
))
1082 switch (gimple_call_internal_fn (call
))
1086 case IFN_BUILTIN_EXPECT
:
1087 impl_call_builtin_expect (cd
);
1089 case IFN_UBSAN_BOUNDS
:
1094 if (tree callee_fndecl
= get_fndecl_for_call (call
, ctxt
))
1096 /* The various impl_call_* member functions are implemented
1097 in region-model-impl-calls.cc.
1098 Having them split out into separate functions makes it easier
1099 to put breakpoints on the handling of specific functions. */
1101 if (fndecl_built_in_p (callee_fndecl
, BUILT_IN_NORMAL
)
1102 && gimple_builtin_call_types_compatible_p (call
, callee_fndecl
))
1103 switch (DECL_UNCHECKED_FUNCTION_CODE (callee_fndecl
))
1106 if (!DECL_PURE_P (callee_fndecl
))
1107 unknown_side_effects
= true;
1109 case BUILT_IN_ALLOCA
:
1110 case BUILT_IN_ALLOCA_WITH_ALIGN
:
1111 impl_call_alloca (cd
);
1113 case BUILT_IN_CALLOC
:
1114 impl_call_calloc (cd
);
1116 case BUILT_IN_EXPECT
:
1117 case BUILT_IN_EXPECT_WITH_PROBABILITY
:
1118 impl_call_builtin_expect (cd
);
1121 /* Handle in "on_call_post". */
1123 case BUILT_IN_MALLOC
:
1124 impl_call_malloc (cd
);
1126 case BUILT_IN_MEMCPY
:
1127 case BUILT_IN_MEMCPY_CHK
:
1128 impl_call_memcpy (cd
);
1130 case BUILT_IN_MEMSET
:
1131 case BUILT_IN_MEMSET_CHK
:
1132 impl_call_memset (cd
);
1135 case BUILT_IN_REALLOC
:
1137 case BUILT_IN_STRCHR
:
1138 impl_call_strchr (cd
);
1140 case BUILT_IN_STRCPY
:
1141 case BUILT_IN_STRCPY_CHK
:
1142 impl_call_strcpy (cd
);
1144 case BUILT_IN_STRLEN
:
1145 impl_call_strlen (cd
);
1148 case BUILT_IN_STACK_SAVE
:
1149 case BUILT_IN_STACK_RESTORE
:
1152 /* Stdio builtins. */
1153 case BUILT_IN_FPRINTF
:
1154 case BUILT_IN_FPRINTF_UNLOCKED
:
1156 case BUILT_IN_PUTC_UNLOCKED
:
1157 case BUILT_IN_FPUTC
:
1158 case BUILT_IN_FPUTC_UNLOCKED
:
1159 case BUILT_IN_FPUTS
:
1160 case BUILT_IN_FPUTS_UNLOCKED
:
1161 case BUILT_IN_FWRITE
:
1162 case BUILT_IN_FWRITE_UNLOCKED
:
1163 case BUILT_IN_PRINTF
:
1164 case BUILT_IN_PRINTF_UNLOCKED
:
1165 case BUILT_IN_PUTCHAR
:
1166 case BUILT_IN_PUTCHAR_UNLOCKED
:
1168 case BUILT_IN_PUTS_UNLOCKED
:
1169 case BUILT_IN_VFPRINTF
:
1170 case BUILT_IN_VPRINTF
:
1171 /* These stdio builtins have external effects that are out
1172 of scope for the analyzer: we only want to model the effects
1173 on the return value. */
1176 else if (is_named_call_p (callee_fndecl
, "malloc", call
, 1))
1178 impl_call_malloc (cd
);
1181 else if (is_named_call_p (callee_fndecl
, "calloc", call
, 2))
1183 impl_call_calloc (cd
);
1186 else if (is_named_call_p (callee_fndecl
, "alloca", call
, 1))
1188 impl_call_alloca (cd
);
1191 else if (is_named_call_p (callee_fndecl
, "realloc", call
, 2))
1193 impl_call_realloc (cd
);
1196 else if (is_named_call_p (callee_fndecl
, "error"))
1198 if (impl_call_error (cd
, 3, out_terminate_path
))
1201 unknown_side_effects
= true;
1203 else if (is_named_call_p (callee_fndecl
, "error_at_line"))
1205 if (impl_call_error (cd
, 5, out_terminate_path
))
1208 unknown_side_effects
= true;
1210 else if (is_named_call_p (callee_fndecl
, "fgets", call
, 3)
1211 || is_named_call_p (callee_fndecl
, "fgets_unlocked", call
, 3))
1213 impl_call_fgets (cd
);
1216 else if (is_named_call_p (callee_fndecl
, "fread", call
, 4))
1218 impl_call_fread (cd
);
1221 else if (is_named_call_p (callee_fndecl
, "getchar", call
, 0))
1223 /* No side-effects (tracking stream state is out-of-scope
1224 for the analyzer). */
1226 else if (is_named_call_p (callee_fndecl
, "memset", call
, 3)
1227 && POINTER_TYPE_P (cd
.get_arg_type (0)))
1229 impl_call_memset (cd
);
1232 else if (is_named_call_p (callee_fndecl
, "strchr", call
, 2)
1233 && POINTER_TYPE_P (cd
.get_arg_type (0)))
1235 impl_call_strchr (cd
);
1238 else if (is_named_call_p (callee_fndecl
, "strlen", call
, 1)
1239 && POINTER_TYPE_P (cd
.get_arg_type (0)))
1241 impl_call_strlen (cd
);
1244 else if (is_named_call_p (callee_fndecl
, "operator new", call
, 1))
1246 impl_call_operator_new (cd
);
1249 else if (is_named_call_p (callee_fndecl
, "operator new []", call
, 1))
1251 impl_call_operator_new (cd
);
1254 else if (is_named_call_p (callee_fndecl
, "operator delete", call
, 1)
1255 || is_named_call_p (callee_fndecl
, "operator delete", call
, 2)
1256 || is_named_call_p (callee_fndecl
, "operator delete []", call
, 1))
1258 /* Handle in "on_call_post". */
1260 else if (!fndecl_has_gimple_body_p (callee_fndecl
)
1261 && !DECL_PURE_P (callee_fndecl
)
1262 && !fndecl_built_in_p (callee_fndecl
))
1263 unknown_side_effects
= true;
1266 unknown_side_effects
= true;
1268 return unknown_side_effects
;
1271 /* Update this model for the CALL stmt, using CTXT to report any
1272 diagnostics - the second half.
1274 Updates to the region_model that should be made *after* sm-states
1275 are updated are done here; other updates to the region_model are done
1276 in region_model::on_call_pre.
1278 If UNKNOWN_SIDE_EFFECTS is true, also call handle_unrecognized_call
1282 region_model::on_call_post (const gcall
*call
,
1283 bool unknown_side_effects
,
1284 region_model_context
*ctxt
)
1286 if (tree callee_fndecl
= get_fndecl_for_call (call
, ctxt
))
1288 call_details
cd (call
, this, ctxt
);
1289 if (is_named_call_p (callee_fndecl
, "free", call
, 1))
1291 impl_call_free (cd
);
1294 if (is_named_call_p (callee_fndecl
, "operator delete", call
, 1)
1295 || is_named_call_p (callee_fndecl
, "operator delete", call
, 2)
1296 || is_named_call_p (callee_fndecl
, "operator delete []", call
, 1))
1298 impl_call_operator_delete (cd
);
1301 /* Was this fndecl referenced by
1302 __attribute__((malloc(FOO)))? */
1303 if (lookup_attribute ("*dealloc", DECL_ATTRIBUTES (callee_fndecl
)))
1305 impl_deallocation_call (cd
);
1308 if (fndecl_built_in_p (callee_fndecl
, BUILT_IN_NORMAL
)
1309 && gimple_builtin_call_types_compatible_p (call
, callee_fndecl
))
1310 switch (DECL_UNCHECKED_FUNCTION_CODE (callee_fndecl
))
1314 case BUILT_IN_REALLOC
:
1315 impl_call_realloc (cd
);
1320 if (unknown_side_effects
)
1321 handle_unrecognized_call (call
, ctxt
);
1324 /* Purge state involving SVAL from this region_model, using CTXT
1325 (if non-NULL) to purge other state in a program_state.
1327 For example, if we're at the def-stmt of an SSA name, then we need to
1328 purge any state for svalues that involve that SSA name. This avoids
1329 false positives in loops, since a symbolic value referring to the
1330 SSA name will be referring to the previous value of that SSA name.
1333 while ((e = hashmap_iter_next(&iter))) {
1334 struct oid2strbuf *e_strbuf = (struct oid2strbuf *)e;
1335 free (e_strbuf->value);
1337 at the def-stmt of e_8:
1338 e_8 = hashmap_iter_next (&iter);
1339 we should purge the "freed" state of:
1340 INIT_VAL(CAST_REG(‘struct oid2strbuf’, (*INIT_VAL(e_8))).value)
1341 which is the "e_strbuf->value" value from the previous iteration,
1342 or we will erroneously report a double-free - the "e_8" within it
1343 refers to the previous value. */
1346 region_model::purge_state_involving (const svalue
*sval
,
1347 region_model_context
*ctxt
)
1349 if (!sval
->can_have_associated_state_p ())
1351 m_store
.purge_state_involving (sval
, m_mgr
);
1352 m_constraints
->purge_state_involving (sval
);
1353 m_dynamic_extents
.purge_state_involving (sval
);
1355 ctxt
->purge_state_involving (sval
);
1358 /* Handle a call CALL to a function with unknown behavior.
1360 Traverse the regions in this model, determining what regions are
1361 reachable from pointer arguments to CALL and from global variables,
1364 Set all reachable regions to new unknown values and purge sm-state
1365 from their values, and from values that point to them. */
1368 region_model::handle_unrecognized_call (const gcall
*call
,
1369 region_model_context
*ctxt
)
1371 tree fndecl
= get_fndecl_for_call (call
, ctxt
);
1373 reachable_regions
reachable_regs (this);
1375 /* Determine the reachable regions and their mutability. */
1377 /* Add globals and regions that already escaped in previous
1379 m_store
.for_each_cluster (reachable_regions::init_cluster_cb
,
1382 /* Params that are pointers. */
1383 tree iter_param_types
= NULL_TREE
;
1385 iter_param_types
= TYPE_ARG_TYPES (TREE_TYPE (fndecl
));
1386 for (unsigned arg_idx
= 0; arg_idx
< gimple_call_num_args (call
); arg_idx
++)
1388 /* Track expected param type, where available. */
1389 tree param_type
= NULL_TREE
;
1390 if (iter_param_types
)
1392 param_type
= TREE_VALUE (iter_param_types
);
1393 gcc_assert (param_type
);
1394 iter_param_types
= TREE_CHAIN (iter_param_types
);
1397 tree parm
= gimple_call_arg (call
, arg_idx
);
1398 const svalue
*parm_sval
= get_rvalue (parm
, ctxt
);
1399 reachable_regs
.handle_parm (parm_sval
, param_type
);
1403 uncertainty_t
*uncertainty
= ctxt
? ctxt
->get_uncertainty () : NULL
;
1405 /* Purge sm-state for the svalues that were reachable,
1406 both in non-mutable and mutable form. */
1407 for (svalue_set::iterator iter
1408 = reachable_regs
.begin_reachable_svals ();
1409 iter
!= reachable_regs
.end_reachable_svals (); ++iter
)
1411 const svalue
*sval
= (*iter
);
1413 ctxt
->on_unknown_change (sval
, false);
1415 for (svalue_set::iterator iter
1416 = reachable_regs
.begin_mutable_svals ();
1417 iter
!= reachable_regs
.end_mutable_svals (); ++iter
)
1419 const svalue
*sval
= (*iter
);
1421 ctxt
->on_unknown_change (sval
, true);
1423 uncertainty
->on_mutable_sval_at_unknown_call (sval
);
1426 /* Mark any clusters that have escaped. */
1427 reachable_regs
.mark_escaped_clusters (ctxt
);
1429 /* Update bindings for all clusters that have escaped, whether above,
1431 m_store
.on_unknown_fncall (call
, m_mgr
->get_store_manager ());
1433 /* Purge dynamic extents from any regions that have escaped mutably:
1434 realloc could have been called on them. */
1435 for (hash_set
<const region
*>::iterator
1436 iter
= reachable_regs
.begin_mutable_base_regs ();
1437 iter
!= reachable_regs
.end_mutable_base_regs ();
1440 const region
*base_reg
= (*iter
);
1441 unset_dynamic_extents (base_reg
);
1445 /* Traverse the regions in this model, determining what regions are
1446 reachable from the store and populating *OUT.
1448 If EXTRA_SVAL is non-NULL, treat it as an additional "root"
1449 for reachability (for handling return values from functions when
1450 analyzing return of the only function on the stack).
1452 If UNCERTAINTY is non-NULL, treat any svalues that were recorded
1453 within it as being maybe-bound as additional "roots" for reachability.
1455 Find svalues that haven't leaked. */
1458 region_model::get_reachable_svalues (svalue_set
*out
,
1459 const svalue
*extra_sval
,
1460 const uncertainty_t
*uncertainty
)
1462 reachable_regions
reachable_regs (this);
1464 /* Add globals and regions that already escaped in previous
1466 m_store
.for_each_cluster (reachable_regions::init_cluster_cb
,
1470 reachable_regs
.handle_sval (extra_sval
);
1473 for (uncertainty_t::iterator iter
1474 = uncertainty
->begin_maybe_bound_svals ();
1475 iter
!= uncertainty
->end_maybe_bound_svals (); ++iter
)
1476 reachable_regs
.handle_sval (*iter
);
1478 /* Get regions for locals that have explicitly bound values. */
1479 for (store::cluster_map_t::iterator iter
= m_store
.begin ();
1480 iter
!= m_store
.end (); ++iter
)
1482 const region
*base_reg
= (*iter
).first
;
1483 if (const region
*parent
= base_reg
->get_parent_region ())
1484 if (parent
->get_kind () == RK_FRAME
)
1485 reachable_regs
.add (base_reg
, false);
1488 /* Populate *OUT based on the values that were reachable. */
1489 for (svalue_set::iterator iter
1490 = reachable_regs
.begin_reachable_svals ();
1491 iter
!= reachable_regs
.end_reachable_svals (); ++iter
)
1495 /* Update this model for the RETURN_STMT, using CTXT to report any
1499 region_model::on_return (const greturn
*return_stmt
, region_model_context
*ctxt
)
1501 tree callee
= get_current_function ()->decl
;
1502 tree lhs
= DECL_RESULT (callee
);
1503 tree rhs
= gimple_return_retval (return_stmt
);
1506 copy_region (get_lvalue (lhs
, ctxt
), get_lvalue (rhs
, ctxt
), ctxt
);
1509 /* Update this model for a call and return of setjmp/sigsetjmp at CALL within
1510 ENODE, using CTXT to report any diagnostics.
1512 This is for the initial direct invocation of setjmp/sigsetjmp (which returns
1513 0), as opposed to any second return due to longjmp/sigsetjmp. */
1516 region_model::on_setjmp (const gcall
*call
, const exploded_node
*enode
,
1517 region_model_context
*ctxt
)
1519 const svalue
*buf_ptr
= get_rvalue (gimple_call_arg (call
, 0), ctxt
);
1520 const region
*buf_reg
= deref_rvalue (buf_ptr
, gimple_call_arg (call
, 0),
1523 /* Create a setjmp_svalue for this call and store it in BUF_REG's
1527 setjmp_record
r (enode
, call
);
1529 = m_mgr
->get_or_create_setjmp_svalue (r
, buf_reg
->get_type ());
1530 set_value (buf_reg
, sval
, ctxt
);
1533 /* Direct calls to setjmp return 0. */
1534 if (tree lhs
= gimple_call_lhs (call
))
1536 const svalue
*new_sval
1537 = m_mgr
->get_or_create_int_cst (TREE_TYPE (lhs
), 0);
1538 const region
*lhs_reg
= get_lvalue (lhs
, ctxt
);
1539 set_value (lhs_reg
, new_sval
, ctxt
);
1543 /* Update this region_model for rewinding from a "longjmp" at LONGJMP_CALL
1544 to a "setjmp" at SETJMP_CALL where the final stack depth should be
1545 SETJMP_STACK_DEPTH. Pop any stack frames. Leak detection is *not*
1546 done, and should be done by the caller. */
1549 region_model::on_longjmp (const gcall
*longjmp_call
, const gcall
*setjmp_call
,
1550 int setjmp_stack_depth
, region_model_context
*ctxt
)
1552 /* Evaluate the val, using the frame of the "longjmp". */
1553 tree fake_retval
= gimple_call_arg (longjmp_call
, 1);
1554 const svalue
*fake_retval_sval
= get_rvalue (fake_retval
, ctxt
);
1556 /* Pop any frames until we reach the stack depth of the function where
1557 setjmp was called. */
1558 gcc_assert (get_stack_depth () >= setjmp_stack_depth
);
1559 while (get_stack_depth () > setjmp_stack_depth
)
1560 pop_frame (NULL
, NULL
, ctxt
);
1562 gcc_assert (get_stack_depth () == setjmp_stack_depth
);
1564 /* Assign to LHS of "setjmp" in new_state. */
1565 if (tree lhs
= gimple_call_lhs (setjmp_call
))
1567 /* Passing 0 as the val to longjmp leads to setjmp returning 1. */
1568 const svalue
*zero_sval
1569 = m_mgr
->get_or_create_int_cst (TREE_TYPE (fake_retval
), 0);
1570 tristate eq_zero
= eval_condition (fake_retval_sval
, EQ_EXPR
, zero_sval
);
1571 /* If we have 0, use 1. */
1572 if (eq_zero
.is_true ())
1574 const svalue
*one_sval
1575 = m_mgr
->get_or_create_int_cst (TREE_TYPE (fake_retval
), 1);
1576 fake_retval_sval
= one_sval
;
1580 /* Otherwise note that the value is nonzero. */
1581 m_constraints
->add_constraint (fake_retval_sval
, NE_EXPR
, zero_sval
);
1584 /* Decorate the return value from setjmp as being unmergeable,
1585 so that we don't attempt to merge states with it as zero
1586 with states in which it's nonzero, leading to a clean distinction
1587 in the exploded_graph betweeen the first return and the second
1589 fake_retval_sval
= m_mgr
->get_or_create_unmergeable (fake_retval_sval
);
1591 const region
*lhs_reg
= get_lvalue (lhs
, ctxt
);
1592 set_value (lhs_reg
, fake_retval_sval
, ctxt
);
1596 /* Update this region_model for a phi stmt of the form
1597 LHS = PHI <...RHS...>.
1598 where RHS is for the appropriate edge.
1599 Get state from OLD_STATE so that all of the phi stmts for a basic block
1600 are effectively handled simultaneously. */
1603 region_model::handle_phi (const gphi
*phi
,
1605 const region_model
&old_state
,
1606 region_model_context
*ctxt
)
1608 /* For now, don't bother tracking the .MEM SSA names. */
1609 if (tree var
= SSA_NAME_VAR (lhs
))
1610 if (TREE_CODE (var
) == VAR_DECL
)
1611 if (VAR_DECL_IS_VIRTUAL_OPERAND (var
))
1614 const svalue
*src_sval
= old_state
.get_rvalue (rhs
, ctxt
);
1615 const region
*dst_reg
= old_state
.get_lvalue (lhs
, ctxt
);
1617 set_value (dst_reg
, src_sval
, ctxt
);
1620 ctxt
->on_phi (phi
, rhs
);
1623 /* Implementation of region_model::get_lvalue; the latter adds type-checking.
1625 Get the id of the region for PV within this region_model,
1626 emitting any diagnostics to CTXT. */
1629 region_model::get_lvalue_1 (path_var pv
, region_model_context
*ctxt
) const
1631 tree expr
= pv
.m_tree
;
1635 switch (TREE_CODE (expr
))
1638 return m_mgr
->get_region_for_unexpected_tree_code (ctxt
, expr
,
1639 dump_location_t ());
1643 tree array
= TREE_OPERAND (expr
, 0);
1644 tree index
= TREE_OPERAND (expr
, 1);
1646 const region
*array_reg
= get_lvalue (array
, ctxt
);
1647 const svalue
*index_sval
= get_rvalue (index
, ctxt
);
1648 return m_mgr
->get_element_region (array_reg
,
1649 TREE_TYPE (TREE_TYPE (array
)),
1656 tree ptr
= TREE_OPERAND (expr
, 0);
1657 tree offset
= TREE_OPERAND (expr
, 1);
1658 const svalue
*ptr_sval
= get_rvalue (ptr
, ctxt
);
1659 const svalue
*offset_sval
= get_rvalue (offset
, ctxt
);
1660 const region
*star_ptr
= deref_rvalue (ptr_sval
, ptr
, ctxt
);
1661 return m_mgr
->get_offset_region (star_ptr
,
1668 return m_mgr
->get_region_for_fndecl (expr
);
1671 return m_mgr
->get_region_for_label (expr
);
1674 /* Handle globals. */
1675 if (is_global_var (expr
))
1676 return m_mgr
->get_region_for_global (expr
);
1684 gcc_assert (TREE_CODE (expr
) == SSA_NAME
1685 || TREE_CODE (expr
) == PARM_DECL
1686 || TREE_CODE (expr
) == VAR_DECL
1687 || TREE_CODE (expr
) == RESULT_DECL
);
1689 int stack_index
= pv
.m_stack_depth
;
1690 const frame_region
*frame
= get_frame_at_index (stack_index
);
1692 return frame
->get_region_for_local (m_mgr
, expr
);
1698 tree obj
= TREE_OPERAND (expr
, 0);
1699 tree field
= TREE_OPERAND (expr
, 1);
1700 const region
*obj_reg
= get_lvalue (obj
, ctxt
);
1701 return m_mgr
->get_field_region (obj_reg
, field
);
1706 return m_mgr
->get_region_for_string (expr
);
1710 /* Assert that SRC_TYPE can be converted to DST_TYPE as a no-op. */
1713 assert_compat_types (tree src_type
, tree dst_type
)
1715 if (src_type
&& dst_type
&& !VOID_TYPE_P (dst_type
))
1718 if (!(useless_type_conversion_p (src_type
, dst_type
)))
1719 internal_error ("incompatible types: %qT and %qT", src_type
, dst_type
);
1724 /* Return true if SRC_TYPE can be converted to DST_TYPE as a no-op. */
1727 compat_types_p (tree src_type
, tree dst_type
)
1729 if (src_type
&& dst_type
&& !VOID_TYPE_P (dst_type
))
1730 if (!(useless_type_conversion_p (src_type
, dst_type
)))
1735 /* Get the region for PV within this region_model,
1736 emitting any diagnostics to CTXT. */
1739 region_model::get_lvalue (path_var pv
, region_model_context
*ctxt
) const
1741 if (pv
.m_tree
== NULL_TREE
)
1744 const region
*result_reg
= get_lvalue_1 (pv
, ctxt
);
1745 assert_compat_types (result_reg
->get_type (), TREE_TYPE (pv
.m_tree
));
1749 /* Get the region for EXPR within this region_model (assuming the most
1750 recent stack frame if it's a local). */
1753 region_model::get_lvalue (tree expr
, region_model_context
*ctxt
) const
1755 return get_lvalue (path_var (expr
, get_stack_depth () - 1), ctxt
);
1758 /* Implementation of region_model::get_rvalue; the latter adds type-checking.
1760 Get the value of PV within this region_model,
1761 emitting any diagnostics to CTXT. */
1764 region_model::get_rvalue_1 (path_var pv
, region_model_context
*ctxt
) const
1766 gcc_assert (pv
.m_tree
);
1768 switch (TREE_CODE (pv
.m_tree
))
1771 return m_mgr
->get_or_create_unknown_svalue (TREE_TYPE (pv
.m_tree
));
1776 tree expr
= pv
.m_tree
;
1777 tree op0
= TREE_OPERAND (expr
, 0);
1778 const region
*expr_reg
= get_lvalue (op0
, ctxt
);
1779 return m_mgr
->get_ptr_svalue (TREE_TYPE (expr
), expr_reg
);
1785 tree expr
= pv
.m_tree
;
1786 tree op0
= TREE_OPERAND (expr
, 0);
1787 const region
*reg
= get_lvalue (op0
, ctxt
);
1788 tree num_bits
= TREE_OPERAND (expr
, 1);
1789 tree first_bit_offset
= TREE_OPERAND (expr
, 2);
1790 gcc_assert (TREE_CODE (num_bits
) == INTEGER_CST
);
1791 gcc_assert (TREE_CODE (first_bit_offset
) == INTEGER_CST
);
1792 bit_range
bits (TREE_INT_CST_LOW (first_bit_offset
),
1793 TREE_INT_CST_LOW (num_bits
));
1794 return get_rvalue_for_bits (TREE_TYPE (expr
), reg
, bits
, ctxt
);
1803 const region
*reg
= get_lvalue (pv
, ctxt
);
1804 return get_store_value (reg
, ctxt
);
1809 case VIEW_CONVERT_EXPR
:
1811 tree expr
= pv
.m_tree
;
1812 tree arg
= TREE_OPERAND (expr
, 0);
1813 const svalue
*arg_sval
= get_rvalue (arg
, ctxt
);
1814 const svalue
*sval_unaryop
1815 = m_mgr
->get_or_create_unaryop (TREE_TYPE (expr
), TREE_CODE (expr
),
1817 return sval_unaryop
;
1825 return m_mgr
->get_or_create_constant_svalue (pv
.m_tree
);
1827 case POINTER_PLUS_EXPR
:
1829 tree expr
= pv
.m_tree
;
1830 tree ptr
= TREE_OPERAND (expr
, 0);
1831 tree offset
= TREE_OPERAND (expr
, 1);
1832 const svalue
*ptr_sval
= get_rvalue (ptr
, ctxt
);
1833 const svalue
*offset_sval
= get_rvalue (offset
, ctxt
);
1834 const svalue
*sval_binop
1835 = m_mgr
->get_or_create_binop (TREE_TYPE (expr
), POINTER_PLUS_EXPR
,
1836 ptr_sval
, offset_sval
);
1844 tree expr
= pv
.m_tree
;
1845 tree arg0
= TREE_OPERAND (expr
, 0);
1846 tree arg1
= TREE_OPERAND (expr
, 1);
1847 const svalue
*arg0_sval
= get_rvalue (arg0
, ctxt
);
1848 const svalue
*arg1_sval
= get_rvalue (arg1
, ctxt
);
1849 const svalue
*sval_binop
1850 = m_mgr
->get_or_create_binop (TREE_TYPE (expr
), TREE_CODE (expr
),
1851 arg0_sval
, arg1_sval
);
1858 const region
*ref_reg
= get_lvalue (pv
, ctxt
);
1859 return get_store_value (ref_reg
, ctxt
);
1863 tree expr
= OBJ_TYPE_REF_EXPR (pv
.m_tree
);
1864 return get_rvalue (expr
, ctxt
);
1869 /* Get the value of PV within this region_model,
1870 emitting any diagnostics to CTXT. */
1873 region_model::get_rvalue (path_var pv
, region_model_context
*ctxt
) const
1875 if (pv
.m_tree
== NULL_TREE
)
1878 const svalue
*result_sval
= get_rvalue_1 (pv
, ctxt
);
1880 assert_compat_types (result_sval
->get_type (), TREE_TYPE (pv
.m_tree
));
1882 result_sval
= check_for_poison (result_sval
, pv
.m_tree
, ctxt
);
1887 /* Get the value of EXPR within this region_model (assuming the most
1888 recent stack frame if it's a local). */
1891 region_model::get_rvalue (tree expr
, region_model_context
*ctxt
) const
1893 return get_rvalue (path_var (expr
, get_stack_depth () - 1), ctxt
);
1896 /* Return true if this model is on a path with "main" as the entrypoint
1897 (as opposed to one in which we're merely analyzing a subset of the
1898 path through the code). */
1901 region_model::called_from_main_p () const
1903 if (!m_current_frame
)
1905 /* Determine if the oldest stack frame in this model is for "main". */
1906 const frame_region
*frame0
= get_frame_at_index (0);
1907 gcc_assert (frame0
);
1908 return id_equal (DECL_NAME (frame0
->get_function ()->decl
), "main");
1911 /* Subroutine of region_model::get_store_value for when REG is (or is within)
1912 a global variable that hasn't been touched since the start of this path
1913 (or was implicitly touched due to a call to an unknown function). */
1916 region_model::get_initial_value_for_global (const region
*reg
) const
1918 /* Get the decl that REG is for (or is within). */
1919 const decl_region
*base_reg
1920 = reg
->get_base_region ()->dyn_cast_decl_region ();
1921 gcc_assert (base_reg
);
1922 tree decl
= base_reg
->get_decl ();
1924 /* Special-case: to avoid having to explicitly update all previously
1925 untracked globals when calling an unknown fn, they implicitly have
1926 an unknown value if an unknown call has occurred, unless this is
1927 static to-this-TU and hasn't escaped. Globals that have escaped
1928 are explicitly tracked, so we shouldn't hit this case for them. */
1929 if (m_store
.called_unknown_fn_p ()
1930 && TREE_PUBLIC (decl
)
1931 && !TREE_READONLY (decl
))
1932 return m_mgr
->get_or_create_unknown_svalue (reg
->get_type ());
1934 /* If we are on a path from the entrypoint from "main" and we have a
1935 global decl defined in this TU that hasn't been touched yet, then
1936 the initial value of REG can be taken from the initialization value
1938 if (called_from_main_p () || TREE_READONLY (decl
))
1940 /* Attempt to get the initializer value for base_reg. */
1941 if (const svalue
*base_reg_init
1942 = base_reg
->get_svalue_for_initializer (m_mgr
))
1944 if (reg
== base_reg
)
1945 return base_reg_init
;
1948 /* Get the value for REG within base_reg_init. */
1949 binding_cluster
c (base_reg
);
1950 c
.bind (m_mgr
->get_store_manager (), base_reg
, base_reg_init
);
1952 = c
.get_any_binding (m_mgr
->get_store_manager (), reg
);
1955 if (reg
->get_type ())
1956 sval
= m_mgr
->get_or_create_cast (reg
->get_type (),
1964 /* Otherwise, return INIT_VAL(REG). */
1965 return m_mgr
->get_or_create_initial_value (reg
);
1968 /* Get a value for REG, looking it up in the store, or otherwise falling
1969 back to "initial" or "unknown" values.
1970 Use CTXT to report any warnings associated with reading from REG. */
1973 region_model::get_store_value (const region
*reg
,
1974 region_model_context
*ctxt
) const
1976 check_region_for_read (reg
, ctxt
);
1978 /* Special-case: handle var_decls in the constant pool. */
1979 if (const decl_region
*decl_reg
= reg
->dyn_cast_decl_region ())
1980 if (const svalue
*sval
= decl_reg
->maybe_get_constant_value (m_mgr
))
1984 = m_store
.get_any_binding (m_mgr
->get_store_manager (), reg
);
1987 if (reg
->get_type ())
1988 sval
= m_mgr
->get_or_create_cast (reg
->get_type (), sval
);
1992 /* Special-case: read at a constant index within a STRING_CST. */
1993 if (const offset_region
*offset_reg
= reg
->dyn_cast_offset_region ())
1994 if (tree byte_offset_cst
1995 = offset_reg
->get_byte_offset ()->maybe_get_constant ())
1996 if (const string_region
*str_reg
1997 = reg
->get_parent_region ()->dyn_cast_string_region ())
1999 tree string_cst
= str_reg
->get_string_cst ();
2000 if (const svalue
*char_sval
2001 = m_mgr
->maybe_get_char_from_string_cst (string_cst
,
2003 return m_mgr
->get_or_create_cast (reg
->get_type (), char_sval
);
2006 /* Special-case: read the initial char of a STRING_CST. */
2007 if (const cast_region
*cast_reg
= reg
->dyn_cast_cast_region ())
2008 if (const string_region
*str_reg
2009 = cast_reg
->get_original_region ()->dyn_cast_string_region ())
2011 tree string_cst
= str_reg
->get_string_cst ();
2012 tree byte_offset_cst
= build_int_cst (integer_type_node
, 0);
2013 if (const svalue
*char_sval
2014 = m_mgr
->maybe_get_char_from_string_cst (string_cst
,
2016 return m_mgr
->get_or_create_cast (reg
->get_type (), char_sval
);
2019 /* Otherwise we implicitly have the initial value of the region
2020 (if the cluster had been touched, binding_cluster::get_any_binding,
2021 would have returned UNKNOWN, and we would already have returned
2024 /* Handle globals. */
2025 if (reg
->get_base_region ()->get_parent_region ()->get_kind ()
2027 return get_initial_value_for_global (reg
);
2029 return m_mgr
->get_or_create_initial_value (reg
);
2032 /* Return false if REG does not exist, true if it may do.
2033 This is for detecting regions within the stack that don't exist anymore
2034 after frames are popped. */
2037 region_model::region_exists_p (const region
*reg
) const
2039 /* If within a stack frame, check that the stack frame is live. */
2040 if (const frame_region
*enclosing_frame
= reg
->maybe_get_frame_region ())
2042 /* Check that the current frame is the enclosing frame, or is called
2044 for (const frame_region
*iter_frame
= get_current_frame (); iter_frame
;
2045 iter_frame
= iter_frame
->get_calling_frame ())
2046 if (iter_frame
== enclosing_frame
)
2054 /* Get a region for referencing PTR_SVAL, creating a region if need be, and
2055 potentially generating warnings via CTXT.
2056 PTR_SVAL must be of pointer type.
2057 PTR_TREE if non-NULL can be used when emitting diagnostics. */
2060 region_model::deref_rvalue (const svalue
*ptr_sval
, tree ptr_tree
,
2061 region_model_context
*ctxt
) const
2063 gcc_assert (ptr_sval
);
2064 gcc_assert (POINTER_TYPE_P (ptr_sval
->get_type ()));
2066 /* If we're dereferencing PTR_SVAL, assume that it is non-NULL; add this
2067 as a constraint. This suppresses false positives from
2068 -Wanalyzer-null-dereference for the case where we later have an
2069 if (PTR_SVAL) that would occur if we considered the false branch
2070 and transitioned the malloc state machine from start->null. */
2071 tree null_ptr_cst
= build_int_cst (ptr_sval
->get_type (), 0);
2072 const svalue
*null_ptr
= m_mgr
->get_or_create_constant_svalue (null_ptr_cst
);
2073 m_constraints
->add_constraint (ptr_sval
, NE_EXPR
, null_ptr
);
2075 switch (ptr_sval
->get_kind ())
2082 const region_svalue
*region_sval
2083 = as_a
<const region_svalue
*> (ptr_sval
);
2084 return region_sval
->get_pointee ();
2089 const binop_svalue
*binop_sval
2090 = as_a
<const binop_svalue
*> (ptr_sval
);
2091 switch (binop_sval
->get_op ())
2093 case POINTER_PLUS_EXPR
:
2095 /* If we have a symbolic value expressing pointer arithmentic,
2096 try to convert it to a suitable region. */
2097 const region
*parent_region
2098 = deref_rvalue (binop_sval
->get_arg0 (), NULL_TREE
, ctxt
);
2099 const svalue
*offset
= binop_sval
->get_arg1 ();
2100 tree type
= TREE_TYPE (ptr_sval
->get_type ());
2101 return m_mgr
->get_offset_region (parent_region
, type
, offset
);
2113 tree ptr
= get_representative_tree (ptr_sval
);
2114 /* If we can't get a representative tree for PTR_SVAL
2115 (e.g. if it hasn't been bound into the store), then
2116 fall back on PTR_TREE, if non-NULL. */
2121 const poisoned_svalue
*poisoned_sval
2122 = as_a
<const poisoned_svalue
*> (ptr_sval
);
2123 enum poison_kind pkind
= poisoned_sval
->get_poison_kind ();
2124 ctxt
->warn (new poisoned_value_diagnostic (ptr
, pkind
));
2131 return m_mgr
->get_symbolic_region (ptr_sval
);
2134 /* Attempt to get BITS within any value of REG, as TYPE.
2135 In particular, extract values from compound_svalues for the case
2136 where there's a concrete binding at BITS.
2137 Return an unknown svalue if we can't handle the given case.
2138 Use CTXT to report any warnings associated with reading from REG. */
2141 region_model::get_rvalue_for_bits (tree type
,
2143 const bit_range
&bits
,
2144 region_model_context
*ctxt
) const
2146 const svalue
*sval
= get_store_value (reg
, ctxt
);
2147 return m_mgr
->get_or_create_bits_within (type
, bits
, sval
);
2150 /* A subclass of pending_diagnostic for complaining about writes to
2151 constant regions of memory. */
2153 class write_to_const_diagnostic
2154 : public pending_diagnostic_subclass
<write_to_const_diagnostic
>
2157 write_to_const_diagnostic (const region
*reg
, tree decl
)
2158 : m_reg (reg
), m_decl (decl
)
2161 const char *get_kind () const FINAL OVERRIDE
2163 return "write_to_const_diagnostic";
2166 bool operator== (const write_to_const_diagnostic
&other
) const
2168 return (m_reg
== other
.m_reg
2169 && m_decl
== other
.m_decl
);
2172 bool emit (rich_location
*rich_loc
) FINAL OVERRIDE
2174 auto_diagnostic_group d
;
2176 switch (m_reg
->get_kind ())
2179 warned
= warning_at (rich_loc
, OPT_Wanalyzer_write_to_const
,
2180 "write to %<const%> object %qE", m_decl
);
2183 warned
= warning_at (rich_loc
, OPT_Wanalyzer_write_to_const
,
2184 "write to function %qE", m_decl
);
2187 warned
= warning_at (rich_loc
, OPT_Wanalyzer_write_to_const
,
2188 "write to label %qE", m_decl
);
2192 inform (DECL_SOURCE_LOCATION (m_decl
), "declared here");
2196 label_text
describe_final_event (const evdesc::final_event
&ev
) FINAL OVERRIDE
2198 switch (m_reg
->get_kind ())
2201 return ev
.formatted_print ("write to %<const%> object %qE here", m_decl
);
2203 return ev
.formatted_print ("write to function %qE here", m_decl
);
2205 return ev
.formatted_print ("write to label %qE here", m_decl
);
2210 const region
*m_reg
;
2214 /* A subclass of pending_diagnostic for complaining about writes to
2217 class write_to_string_literal_diagnostic
2218 : public pending_diagnostic_subclass
<write_to_string_literal_diagnostic
>
2221 write_to_string_literal_diagnostic (const region
*reg
)
2225 const char *get_kind () const FINAL OVERRIDE
2227 return "write_to_string_literal_diagnostic";
2230 bool operator== (const write_to_string_literal_diagnostic
&other
) const
2232 return m_reg
== other
.m_reg
;
2235 bool emit (rich_location
*rich_loc
) FINAL OVERRIDE
2237 return warning_at (rich_loc
, OPT_Wanalyzer_write_to_string_literal
,
2238 "write to string literal");
2239 /* Ideally we would show the location of the STRING_CST as well,
2240 but it is not available at this point. */
2243 label_text
describe_final_event (const evdesc::final_event
&ev
) FINAL OVERRIDE
2245 return ev
.formatted_print ("write to string literal here");
2249 const region
*m_reg
;
2252 /* Use CTXT to warn If DEST_REG is a region that shouldn't be written to. */
2255 region_model::check_for_writable_region (const region
* dest_reg
,
2256 region_model_context
*ctxt
) const
2258 /* Fail gracefully if CTXT is NULL. */
2262 const region
*base_reg
= dest_reg
->get_base_region ();
2263 switch (base_reg
->get_kind ())
2269 const function_region
*func_reg
= as_a
<const function_region
*> (base_reg
);
2270 tree fndecl
= func_reg
->get_fndecl ();
2271 ctxt
->warn (new write_to_const_diagnostic (func_reg
, fndecl
));
2276 const label_region
*label_reg
= as_a
<const label_region
*> (base_reg
);
2277 tree label
= label_reg
->get_label ();
2278 ctxt
->warn (new write_to_const_diagnostic (label_reg
, label
));
2283 const decl_region
*decl_reg
= as_a
<const decl_region
*> (base_reg
);
2284 tree decl
= decl_reg
->get_decl ();
2285 /* Warn about writes to const globals.
2286 Don't warn for writes to const locals, and params in particular,
2287 since we would warn in push_frame when setting them up (e.g the
2288 "this" param is "T* const"). */
2289 if (TREE_READONLY (decl
)
2290 && is_global_var (decl
))
2291 ctxt
->warn (new write_to_const_diagnostic (dest_reg
, decl
));
2295 ctxt
->warn (new write_to_string_literal_diagnostic (dest_reg
));
2300 /* Get the capacity of REG in bytes. */
2303 region_model::get_capacity (const region
*reg
) const
2305 switch (reg
->get_kind ())
2311 const decl_region
*decl_reg
= as_a
<const decl_region
*> (reg
);
2312 tree decl
= decl_reg
->get_decl ();
2313 if (TREE_CODE (decl
) == SSA_NAME
)
2315 tree type
= TREE_TYPE (decl
);
2316 tree size
= TYPE_SIZE (type
);
2317 return get_rvalue (size
, NULL
);
2321 tree size
= decl_init_size (decl
, false);
2323 return get_rvalue (size
, NULL
);
2328 /* Look through sized regions to get at the capacity
2329 of the underlying regions. */
2330 return get_capacity (reg
->get_parent_region ());
2333 if (const svalue
*recorded
= get_dynamic_extents (reg
))
2336 return m_mgr
->get_or_create_unknown_svalue (sizetype
);
2339 /* If CTXT is non-NULL, use it to warn about any problems accessing REG,
2340 using DIR to determine if this access is a read or write. */
2343 region_model::check_region_access (const region
*reg
,
2344 enum access_direction dir
,
2345 region_model_context
*ctxt
) const
2347 /* Fail gracefully if CTXT is NULL. */
2351 check_region_for_taint (reg
, dir
, ctxt
);
2358 /* Currently a no-op. */
2361 check_for_writable_region (reg
, ctxt
);
2366 /* If CTXT is non-NULL, use it to warn about any problems writing to REG. */
2369 region_model::check_region_for_write (const region
*dest_reg
,
2370 region_model_context
*ctxt
) const
2372 check_region_access (dest_reg
, DIR_WRITE
, ctxt
);
2375 /* If CTXT is non-NULL, use it to warn about any problems reading from REG. */
2378 region_model::check_region_for_read (const region
*src_reg
,
2379 region_model_context
*ctxt
) const
2381 check_region_access (src_reg
, DIR_READ
, ctxt
);
2384 /* Set the value of the region given by LHS_REG to the value given
2386 Use CTXT to report any warnings associated with writing to LHS_REG. */
2389 region_model::set_value (const region
*lhs_reg
, const svalue
*rhs_sval
,
2390 region_model_context
*ctxt
)
2392 gcc_assert (lhs_reg
);
2393 gcc_assert (rhs_sval
);
2395 check_region_for_write (lhs_reg
, ctxt
);
2397 m_store
.set_value (m_mgr
->get_store_manager(), lhs_reg
, rhs_sval
,
2398 ctxt
? ctxt
->get_uncertainty () : NULL
);
2401 /* Set the value of the region given by LHS to the value given by RHS. */
2404 region_model::set_value (tree lhs
, tree rhs
, region_model_context
*ctxt
)
2406 const region
*lhs_reg
= get_lvalue (lhs
, ctxt
);
2407 const svalue
*rhs_sval
= get_rvalue (rhs
, ctxt
);
2408 gcc_assert (lhs_reg
);
2409 gcc_assert (rhs_sval
);
2410 set_value (lhs_reg
, rhs_sval
, ctxt
);
2413 /* Remove all bindings overlapping REG within the store. */
2416 region_model::clobber_region (const region
*reg
)
2418 m_store
.clobber_region (m_mgr
->get_store_manager(), reg
);
2421 /* Remove any bindings for REG within the store. */
2424 region_model::purge_region (const region
*reg
)
2426 m_store
.purge_region (m_mgr
->get_store_manager(), reg
);
2429 /* Fill REG with SVAL. */
2432 region_model::fill_region (const region
*reg
, const svalue
*sval
)
2434 m_store
.fill_region (m_mgr
->get_store_manager(), reg
, sval
);
2437 /* Zero-fill REG. */
2440 region_model::zero_fill_region (const region
*reg
)
2442 m_store
.zero_fill_region (m_mgr
->get_store_manager(), reg
);
2445 /* Mark REG as having unknown content. */
2448 region_model::mark_region_as_unknown (const region
*reg
,
2449 uncertainty_t
*uncertainty
)
2451 m_store
.mark_region_as_unknown (m_mgr
->get_store_manager(), reg
,
2455 /* Determine what is known about the condition "LHS_SVAL OP RHS_SVAL" within
2459 region_model::eval_condition (const svalue
*lhs
,
2461 const svalue
*rhs
) const
2463 /* For now, make no attempt to capture constraints on floating-point
2465 if ((lhs
->get_type () && FLOAT_TYPE_P (lhs
->get_type ()))
2466 || (rhs
->get_type () && FLOAT_TYPE_P (rhs
->get_type ())))
2467 return tristate::unknown ();
2469 tristate ts
= eval_condition_without_cm (lhs
, op
, rhs
);
2473 /* Otherwise, try constraints. */
2474 return m_constraints
->eval_condition (lhs
, op
, rhs
);
2477 /* Determine what is known about the condition "LHS_SVAL OP RHS_SVAL" within
2478 this model, without resorting to the constraint_manager.
2480 This is exposed so that impl_region_model_context::on_state_leak can
2481 check for equality part-way through region_model::purge_unused_svalues
2482 without risking creating new ECs. */
2485 region_model::eval_condition_without_cm (const svalue
*lhs
,
2487 const svalue
*rhs
) const
2492 /* See what we know based on the values. */
2494 /* For now, make no attempt to capture constraints on floating-point
2496 if ((lhs
->get_type () && FLOAT_TYPE_P (lhs
->get_type ()))
2497 || (rhs
->get_type () && FLOAT_TYPE_P (rhs
->get_type ())))
2498 return tristate::unknown ();
2500 /* Unwrap any unmergeable values. */
2501 lhs
= lhs
->unwrap_any_unmergeable ();
2502 rhs
= rhs
->unwrap_any_unmergeable ();
2506 /* If we have the same svalue, then we have equality
2507 (apart from NaN-handling).
2508 TODO: should this definitely be the case for poisoned values? */
2509 /* Poisoned and unknown values are "unknowable". */
2510 if (lhs
->get_kind () == SK_POISONED
2511 || lhs
->get_kind () == SK_UNKNOWN
)
2512 return tristate::TS_UNKNOWN
;
2519 return tristate::TS_TRUE
;
2524 return tristate::TS_FALSE
;
2527 /* For other ops, use the logic below. */
2532 /* If we have a pair of region_svalues, compare them. */
2533 if (const region_svalue
*lhs_ptr
= lhs
->dyn_cast_region_svalue ())
2534 if (const region_svalue
*rhs_ptr
= rhs
->dyn_cast_region_svalue ())
2536 tristate res
= region_svalue::eval_condition (lhs_ptr
, op
, rhs_ptr
);
2537 if (res
.is_known ())
2539 /* Otherwise, only known through constraints. */
2542 /* If we have a pair of constants, compare them. */
2543 if (const constant_svalue
*cst_lhs
= lhs
->dyn_cast_constant_svalue ())
2544 if (const constant_svalue
*cst_rhs
= rhs
->dyn_cast_constant_svalue ())
2545 return constant_svalue::eval_condition (cst_lhs
, op
, cst_rhs
);
2547 /* Handle comparison against zero. */
2548 if (const constant_svalue
*cst_rhs
= rhs
->dyn_cast_constant_svalue ())
2549 if (zerop (cst_rhs
->get_constant ()))
2551 if (const region_svalue
*ptr
= lhs
->dyn_cast_region_svalue ())
2553 /* A region_svalue is a non-NULL pointer, except in certain
2554 special cases (see the comment for region::non_null_p). */
2555 const region
*pointee
= ptr
->get_pointee ();
2556 if (pointee
->non_null_p ())
2566 return tristate::TS_FALSE
;
2571 return tristate::TS_TRUE
;
2575 else if (const binop_svalue
*binop
= lhs
->dyn_cast_binop_svalue ())
2577 /* Treat offsets from a non-NULL pointer as being non-NULL. This
2578 isn't strictly true, in that eventually ptr++ will wrap
2579 around and be NULL, but it won't occur in practise and thus
2580 can be used to suppress effectively false positives that we
2581 shouldn't warn for. */
2582 if (binop
->get_op () == POINTER_PLUS_EXPR
)
2585 = eval_condition_without_cm (binop
->get_arg0 (),
2587 if (lhs_ts
.is_known ())
2593 /* Handle rejection of equality for comparisons of the initial values of
2594 "external" values (such as params) with the address of locals. */
2595 if (const initial_svalue
*init_lhs
= lhs
->dyn_cast_initial_svalue ())
2596 if (const region_svalue
*rhs_ptr
= rhs
->dyn_cast_region_svalue ())
2598 tristate res
= compare_initial_and_pointer (init_lhs
, rhs_ptr
);
2599 if (res
.is_known ())
2602 if (const initial_svalue
*init_rhs
= rhs
->dyn_cast_initial_svalue ())
2603 if (const region_svalue
*lhs_ptr
= lhs
->dyn_cast_region_svalue ())
2605 tristate res
= compare_initial_and_pointer (init_rhs
, lhs_ptr
);
2606 if (res
.is_known ())
2610 if (const widening_svalue
*widen_lhs
= lhs
->dyn_cast_widening_svalue ())
2611 if (tree rhs_cst
= rhs
->maybe_get_constant ())
2613 tristate res
= widen_lhs
->eval_condition_without_cm (op
, rhs_cst
);
2614 if (res
.is_known ())
2618 return tristate::TS_UNKNOWN
;
2621 /* Subroutine of region_model::eval_condition_without_cm, for rejecting
2622 equality of INIT_VAL(PARM) with &LOCAL. */
2625 region_model::compare_initial_and_pointer (const initial_svalue
*init
,
2626 const region_svalue
*ptr
) const
2628 const region
*pointee
= ptr
->get_pointee ();
2630 /* If we have a pointer to something within a stack frame, it can't be the
2631 initial value of a param. */
2632 if (pointee
->maybe_get_frame_region ())
2633 if (init
->initial_value_of_param_p ())
2634 return tristate::TS_FALSE
;
2636 return tristate::TS_UNKNOWN
;
2639 /* Handle various constraints of the form:
2640 LHS: ((bool)INNER_LHS INNER_OP INNER_RHS))
2644 LHS: CAST([long]int, ((bool)INNER_LHS INNER_OP INNER_RHS))
2647 by adding constraints for INNER_LHS INNEROP INNER_RHS.
2649 Return true if this function can fully handle the constraint; if
2650 so, add the implied constraint(s) and write true to *OUT if they
2651 are consistent with existing constraints, or write false to *OUT
2652 if they contradicts existing constraints.
2654 Return false for cases that this function doeesn't know how to handle.
2656 For example, if we're checking a stored conditional, we'll have
2658 LHS: CAST(long int, (&HEAP_ALLOCATED_REGION(8)!=(int *)0B))
2661 which this function can turn into an add_constraint of:
2662 (&HEAP_ALLOCATED_REGION(8) != (int *)0B)
2664 Similarly, optimized && and || conditionals lead to e.g.
2666 becoming gimple like this:
2670 On the "_3 is false" branch we can have constraints of the form:
2671 ((&HEAP_ALLOCATED_REGION(8)!=(int *)0B)
2672 | (&HEAP_ALLOCATED_REGION(10)!=(int *)0B))
2674 which implies that both _1 and _2 are false,
2675 which this function can turn into a pair of add_constraints of
2676 (&HEAP_ALLOCATED_REGION(8)!=(int *)0B)
2678 (&HEAP_ALLOCATED_REGION(10)!=(int *)0B). */
2681 region_model::add_constraints_from_binop (const svalue
*outer_lhs
,
2682 enum tree_code outer_op
,
2683 const svalue
*outer_rhs
,
2685 region_model_context
*ctxt
)
2687 while (const svalue
*cast
= outer_lhs
->maybe_undo_cast ())
2689 const binop_svalue
*binop_sval
= outer_lhs
->dyn_cast_binop_svalue ();
2692 if (!outer_rhs
->all_zeroes_p ())
2695 const svalue
*inner_lhs
= binop_sval
->get_arg0 ();
2696 enum tree_code inner_op
= binop_sval
->get_op ();
2697 const svalue
*inner_rhs
= binop_sval
->get_arg1 ();
2699 if (outer_op
!= NE_EXPR
&& outer_op
!= EQ_EXPR
)
2703 - "OUTER_LHS != false" (i.e. OUTER is true), or
2704 - "OUTER_LHS == false" (i.e. OUTER is false). */
2705 bool is_true
= outer_op
== NE_EXPR
;
2715 /* ...and "(inner_lhs OP inner_rhs) == 0"
2716 then (inner_lhs OP inner_rhs) must have the same
2717 logical value as LHS. */
2719 inner_op
= invert_tree_comparison (inner_op
, false /* honor_nans */);
2720 *out
= add_constraint (inner_lhs
, inner_op
, inner_rhs
, ctxt
);
2728 /* ...and "(inner_lhs & inner_rhs) != 0"
2729 then both inner_lhs and inner_rhs must be true. */
2730 const svalue
*false_sval
2731 = m_mgr
->get_or_create_constant_svalue (boolean_false_node
);
2732 bool sat1
= add_constraint (inner_lhs
, NE_EXPR
, false_sval
, ctxt
);
2733 bool sat2
= add_constraint (inner_rhs
, NE_EXPR
, false_sval
, ctxt
);
2734 *out
= sat1
&& sat2
;
2742 /* ...and "(inner_lhs | inner_rhs) == 0"
2743 i.e. "(inner_lhs | inner_rhs)" is false
2744 then both inner_lhs and inner_rhs must be false. */
2745 const svalue
*false_sval
2746 = m_mgr
->get_or_create_constant_svalue (boolean_false_node
);
2747 bool sat1
= add_constraint (inner_lhs
, EQ_EXPR
, false_sval
, ctxt
);
2748 bool sat2
= add_constraint (inner_rhs
, EQ_EXPR
, false_sval
, ctxt
);
2749 *out
= sat1
&& sat2
;
2756 /* Attempt to add the constraint "LHS OP RHS" to this region_model.
2757 If it is consistent with existing constraints, add it, and return true.
2758 Return false if it contradicts existing constraints.
2759 Use CTXT for reporting any diagnostics associated with the accesses. */
2762 region_model::add_constraint (tree lhs
, enum tree_code op
, tree rhs
,
2763 region_model_context
*ctxt
)
2765 /* For now, make no attempt to capture constraints on floating-point
2767 if (FLOAT_TYPE_P (TREE_TYPE (lhs
)) || FLOAT_TYPE_P (TREE_TYPE (rhs
)))
2770 const svalue
*lhs_sval
= get_rvalue (lhs
, ctxt
);
2771 const svalue
*rhs_sval
= get_rvalue (rhs
, ctxt
);
2773 return add_constraint (lhs_sval
, op
, rhs_sval
, ctxt
);
2776 /* Attempt to add the constraint "LHS OP RHS" to this region_model.
2777 If it is consistent with existing constraints, add it, and return true.
2778 Return false if it contradicts existing constraints.
2779 Use CTXT for reporting any diagnostics associated with the accesses. */
2782 region_model::add_constraint (const svalue
*lhs
,
2785 region_model_context
*ctxt
)
2787 tristate t_cond
= eval_condition (lhs
, op
, rhs
);
2789 /* If we already have the condition, do nothing. */
2790 if (t_cond
.is_true ())
2793 /* Reject a constraint that would contradict existing knowledge, as
2795 if (t_cond
.is_false ())
2799 if (add_constraints_from_binop (lhs
, op
, rhs
, &out
, ctxt
))
2802 /* Store the constraint. */
2803 m_constraints
->add_constraint (lhs
, op
, rhs
);
2805 /* Notify the context, if any. This exists so that the state machines
2806 in a program_state can be notified about the condition, and so can
2807 set sm-state for e.g. unchecked->checked, both for cfg-edges, and
2808 when synthesizing constraints as above. */
2810 ctxt
->on_condition (lhs
, op
, rhs
);
2812 /* If we have ®ION == NULL, then drop dynamic extents for REGION (for
2813 the case where REGION is heap-allocated and thus could be NULL). */
2814 if (tree rhs_cst
= rhs
->maybe_get_constant ())
2815 if (op
== EQ_EXPR
&& zerop (rhs_cst
))
2816 if (const region_svalue
*region_sval
= lhs
->dyn_cast_region_svalue ())
2817 unset_dynamic_extents (region_sval
->get_pointee ());
2822 /* As above, but when returning false, if OUT is non-NULL, write a
2823 new rejected_constraint to *OUT. */
2826 region_model::add_constraint (tree lhs
, enum tree_code op
, tree rhs
,
2827 region_model_context
*ctxt
,
2828 rejected_constraint
**out
)
2830 bool sat
= add_constraint (lhs
, op
, rhs
, ctxt
);
2832 *out
= new rejected_op_constraint (*this, lhs
, op
, rhs
);
2836 /* Determine what is known about the condition "LHS OP RHS" within
2838 Use CTXT for reporting any diagnostics associated with the accesses. */
2841 region_model::eval_condition (tree lhs
,
2844 region_model_context
*ctxt
)
2846 /* For now, make no attempt to model constraints on floating-point
2848 if (FLOAT_TYPE_P (TREE_TYPE (lhs
)) || FLOAT_TYPE_P (TREE_TYPE (rhs
)))
2849 return tristate::unknown ();
2851 return eval_condition (get_rvalue (lhs
, ctxt
), op
, get_rvalue (rhs
, ctxt
));
2854 /* Implementation of region_model::get_representative_path_var.
2855 Attempt to return a path_var that represents SVAL, or return NULL_TREE.
2856 Use VISITED to prevent infinite mutual recursion with the overload for
2860 region_model::get_representative_path_var_1 (const svalue
*sval
,
2861 svalue_set
*visited
) const
2865 /* Prevent infinite recursion. */
2866 if (visited
->contains (sval
))
2867 return path_var (NULL_TREE
, 0);
2868 visited
->add (sval
);
2870 /* Handle casts by recursion into get_representative_path_var. */
2871 if (const svalue
*cast_sval
= sval
->maybe_undo_cast ())
2873 path_var result
= get_representative_path_var (cast_sval
, visited
);
2874 tree orig_type
= sval
->get_type ();
2875 /* If necessary, wrap the result in a cast. */
2876 if (result
.m_tree
&& orig_type
)
2877 result
.m_tree
= build1 (NOP_EXPR
, orig_type
, result
.m_tree
);
2881 auto_vec
<path_var
> pvs
;
2882 m_store
.get_representative_path_vars (this, visited
, sval
, &pvs
);
2884 if (tree cst
= sval
->maybe_get_constant ())
2885 pvs
.safe_push (path_var (cst
, 0));
2887 /* Handle string literals and various other pointers. */
2888 if (const region_svalue
*ptr_sval
= sval
->dyn_cast_region_svalue ())
2890 const region
*reg
= ptr_sval
->get_pointee ();
2891 if (path_var pv
= get_representative_path_var (reg
, visited
))
2892 return path_var (build1 (ADDR_EXPR
,
2898 /* If we have a sub_svalue, look for ways to represent the parent. */
2899 if (const sub_svalue
*sub_sval
= sval
->dyn_cast_sub_svalue ())
2901 const svalue
*parent_sval
= sub_sval
->get_parent ();
2902 const region
*subreg
= sub_sval
->get_subregion ();
2903 if (path_var parent_pv
2904 = get_representative_path_var (parent_sval
, visited
))
2905 if (const field_region
*field_reg
= subreg
->dyn_cast_field_region ())
2906 return path_var (build3 (COMPONENT_REF
,
2909 field_reg
->get_field (),
2911 parent_pv
.m_stack_depth
);
2914 /* Handle binops. */
2915 if (const binop_svalue
*binop_sval
= sval
->dyn_cast_binop_svalue ())
2917 = get_representative_path_var (binop_sval
->get_arg0 (), visited
))
2919 = get_representative_path_var (binop_sval
->get_arg1 (), visited
))
2920 return path_var (build2 (binop_sval
->get_op (),
2922 lhs_pv
.m_tree
, rhs_pv
.m_tree
),
2923 lhs_pv
.m_stack_depth
);
2925 if (pvs
.length () < 1)
2926 return path_var (NULL_TREE
, 0);
2928 pvs
.qsort (readability_comparator
);
2932 /* Attempt to return a path_var that represents SVAL, or return NULL_TREE.
2933 Use VISITED to prevent infinite mutual recursion with the overload for
2936 This function defers to get_representative_path_var_1 to do the work;
2937 it adds verification that get_representative_path_var_1 returned a tree
2938 of the correct type. */
2941 region_model::get_representative_path_var (const svalue
*sval
,
2942 svalue_set
*visited
) const
2945 return path_var (NULL_TREE
, 0);
2947 tree orig_type
= sval
->get_type ();
2949 path_var result
= get_representative_path_var_1 (sval
, visited
);
2951 /* Verify that the result has the same type as SVAL, if any. */
2952 if (result
.m_tree
&& orig_type
)
2953 gcc_assert (TREE_TYPE (result
.m_tree
) == orig_type
);
2958 /* Attempt to return a tree that represents SVAL, or return NULL_TREE.
2960 Strip off any top-level cast, to avoid messages like
2961 double-free of '(void *)ptr'
2962 from analyzer diagnostics. */
2965 region_model::get_representative_tree (const svalue
*sval
) const
2968 tree expr
= get_representative_path_var (sval
, &visited
).m_tree
;
2970 /* Strip off any top-level cast. */
2971 if (expr
&& TREE_CODE (expr
) == NOP_EXPR
)
2972 expr
= TREE_OPERAND (expr
, 0);
2974 return fixup_tree_for_diagnostic (expr
);
2977 /* Implementation of region_model::get_representative_path_var.
2979 Attempt to return a path_var that represents REG, or return
2981 For example, a region for a field of a local would be a path_var
2982 wrapping a COMPONENT_REF.
2983 Use VISITED to prevent infinite mutual recursion with the overload for
2987 region_model::get_representative_path_var_1 (const region
*reg
,
2988 svalue_set
*visited
) const
2990 switch (reg
->get_kind ())
3001 /* Regions that represent memory spaces are not expressible as trees. */
3002 return path_var (NULL_TREE
, 0);
3006 const function_region
*function_reg
3007 = as_a
<const function_region
*> (reg
);
3008 return path_var (function_reg
->get_fndecl (), 0);
3012 const label_region
*label_reg
= as_a
<const label_region
*> (reg
);
3013 return path_var (label_reg
->get_label (), 0);
3018 const symbolic_region
*symbolic_reg
3019 = as_a
<const symbolic_region
*> (reg
);
3020 const svalue
*pointer
= symbolic_reg
->get_pointer ();
3021 path_var pointer_pv
= get_representative_path_var (pointer
, visited
);
3023 return path_var (NULL_TREE
, 0);
3024 tree offset
= build_int_cst (pointer
->get_type (), 0);
3025 return path_var (build2 (MEM_REF
,
3029 pointer_pv
.m_stack_depth
);
3033 const decl_region
*decl_reg
= as_a
<const decl_region
*> (reg
);
3034 return path_var (decl_reg
->get_decl (), decl_reg
->get_stack_depth ());
3038 const field_region
*field_reg
= as_a
<const field_region
*> (reg
);
3040 = get_representative_path_var (reg
->get_parent_region (), visited
);
3042 return path_var (NULL_TREE
, 0);
3043 return path_var (build3 (COMPONENT_REF
,
3046 field_reg
->get_field (),
3048 parent_pv
.m_stack_depth
);
3053 const element_region
*element_reg
3054 = as_a
<const element_region
*> (reg
);
3056 = get_representative_path_var (reg
->get_parent_region (), visited
);
3058 return path_var (NULL_TREE
, 0);
3060 = get_representative_path_var (element_reg
->get_index (), visited
);
3062 return path_var (NULL_TREE
, 0);
3063 return path_var (build4 (ARRAY_REF
,
3065 parent_pv
.m_tree
, index_pv
.m_tree
,
3066 NULL_TREE
, NULL_TREE
),
3067 parent_pv
.m_stack_depth
);
3072 const offset_region
*offset_reg
3073 = as_a
<const offset_region
*> (reg
);
3075 = get_representative_path_var (reg
->get_parent_region (), visited
);
3077 return path_var (NULL_TREE
, 0);
3079 = get_representative_path_var (offset_reg
->get_byte_offset (),
3081 if (!offset_pv
|| TREE_CODE (offset_pv
.m_tree
) != INTEGER_CST
)
3082 return path_var (NULL_TREE
, 0);
3083 tree addr_parent
= build1 (ADDR_EXPR
,
3084 build_pointer_type (reg
->get_type ()),
3086 return path_var (build2 (MEM_REF
,
3088 addr_parent
, offset_pv
.m_tree
),
3089 parent_pv
.m_stack_depth
);
3093 return path_var (NULL_TREE
, 0);
3098 = get_representative_path_var (reg
->get_parent_region (), visited
);
3100 return path_var (NULL_TREE
, 0);
3101 return path_var (build1 (NOP_EXPR
,
3104 parent_pv
.m_stack_depth
);
3107 case RK_HEAP_ALLOCATED
:
3109 /* No good way to express heap-allocated/alloca regions as trees. */
3110 return path_var (NULL_TREE
, 0);
3114 const string_region
*string_reg
= as_a
<const string_region
*> (reg
);
3115 return path_var (string_reg
->get_string_cst (), 0);
3119 return path_var (NULL_TREE
, 0);
3123 /* Attempt to return a path_var that represents REG, or return
3125 For example, a region for a field of a local would be a path_var
3126 wrapping a COMPONENT_REF.
3127 Use VISITED to prevent infinite mutual recursion with the overload for
3130 This function defers to get_representative_path_var_1 to do the work;
3131 it adds verification that get_representative_path_var_1 returned a tree
3132 of the correct type. */
3135 region_model::get_representative_path_var (const region
*reg
,
3136 svalue_set
*visited
) const
3138 path_var result
= get_representative_path_var_1 (reg
, visited
);
3140 /* Verify that the result has the same type as REG, if any. */
3141 if (result
.m_tree
&& reg
->get_type ())
3142 gcc_assert (TREE_TYPE (result
.m_tree
) == reg
->get_type ());
3147 /* Update this model for any phis in SNODE, assuming we came from
3148 LAST_CFG_SUPEREDGE. */
3151 region_model::update_for_phis (const supernode
*snode
,
3152 const cfg_superedge
*last_cfg_superedge
,
3153 region_model_context
*ctxt
)
3155 gcc_assert (last_cfg_superedge
);
3157 /* Copy this state and pass it to handle_phi so that all of the phi stmts
3158 are effectively handled simultaneously. */
3159 const region_model
old_state (*this);
3161 for (gphi_iterator gpi
= const_cast<supernode
*>(snode
)->start_phis ();
3162 !gsi_end_p (gpi
); gsi_next (&gpi
))
3164 gphi
*phi
= gpi
.phi ();
3166 tree src
= last_cfg_superedge
->get_phi_arg (phi
);
3167 tree lhs
= gimple_phi_result (phi
);
3169 /* Update next_state based on phi and old_state. */
3170 handle_phi (phi
, lhs
, src
, old_state
, ctxt
);
3174 /* Attempt to update this model for taking EDGE (where the last statement
3175 was LAST_STMT), returning true if the edge can be taken, false
3177 When returning false, if OUT is non-NULL, write a new rejected_constraint
3180 For CFG superedges where LAST_STMT is a conditional or a switch
3181 statement, attempt to add the relevant conditions for EDGE to this
3182 model, returning true if they are feasible, or false if they are
3185 For call superedges, push frame information and store arguments
3188 For return superedges, pop frame information and store return
3189 values into any lhs.
3191 Rejection of call/return superedges happens elsewhere, in
3192 program_point::on_edge (i.e. based on program point, rather
3193 than program state). */
3196 region_model::maybe_update_for_edge (const superedge
&edge
,
3197 const gimple
*last_stmt
,
3198 region_model_context
*ctxt
,
3199 rejected_constraint
**out
)
3201 /* Handle frame updates for interprocedural edges. */
3202 switch (edge
.m_kind
)
3207 case SUPEREDGE_CALL
:
3209 const call_superedge
*call_edge
= as_a
<const call_superedge
*> (&edge
);
3210 update_for_call_superedge (*call_edge
, ctxt
);
3214 case SUPEREDGE_RETURN
:
3216 const return_superedge
*return_edge
3217 = as_a
<const return_superedge
*> (&edge
);
3218 update_for_return_superedge (*return_edge
, ctxt
);
3222 case SUPEREDGE_INTRAPROCEDURAL_CALL
:
3224 const callgraph_superedge
*cg_sedge
3225 = as_a
<const callgraph_superedge
*> (&edge
);
3226 update_for_call_summary (*cg_sedge
, ctxt
);
3231 if (last_stmt
== NULL
)
3234 /* Apply any constraints for conditionals/switch statements. */
3236 if (const gcond
*cond_stmt
= dyn_cast
<const gcond
*> (last_stmt
))
3238 const cfg_superedge
*cfg_sedge
= as_a
<const cfg_superedge
*> (&edge
);
3239 return apply_constraints_for_gcond (*cfg_sedge
, cond_stmt
, ctxt
, out
);
3242 if (const gswitch
*switch_stmt
= dyn_cast
<const gswitch
*> (last_stmt
))
3244 const switch_cfg_superedge
*switch_sedge
3245 = as_a
<const switch_cfg_superedge
*> (&edge
);
3246 return apply_constraints_for_gswitch (*switch_sedge
, switch_stmt
,
3250 /* Apply any constraints due to an exception being thrown. */
3251 if (const cfg_superedge
*cfg_sedge
= dyn_cast
<const cfg_superedge
*> (&edge
))
3252 if (cfg_sedge
->get_flags () & EDGE_EH
)
3253 return apply_constraints_for_exception (last_stmt
, ctxt
, out
);
3258 /* Push a new frame_region on to the stack region.
3259 Populate the frame_region with child regions for the function call's
3260 parameters, using values from the arguments at the callsite in the
3264 region_model::update_for_gcall (const gcall
*call_stmt
,
3265 region_model_context
*ctxt
,
3268 /* Build a vec of argument svalues, using the current top
3269 frame for resolving tree expressions. */
3270 auto_vec
<const svalue
*> arg_svals (gimple_call_num_args (call_stmt
));
3272 for (unsigned i
= 0; i
< gimple_call_num_args (call_stmt
); i
++)
3274 tree arg
= gimple_call_arg (call_stmt
, i
);
3275 arg_svals
.quick_push (get_rvalue (arg
, ctxt
));
3280 /* Get the function * from the gcall. */
3281 tree fn_decl
= get_fndecl_for_call (call_stmt
,ctxt
);
3282 callee
= DECL_STRUCT_FUNCTION (fn_decl
);
3285 push_frame (callee
, &arg_svals
, ctxt
);
3288 /* Pop the top-most frame_region from the stack, and copy the return
3289 region's values (if any) into the region for the lvalue of the LHS of
3290 the call (if any). */
3293 region_model::update_for_return_gcall (const gcall
*call_stmt
,
3294 region_model_context
*ctxt
)
3296 /* Get the region for the result of the call, within the caller frame. */
3297 const region
*result_dst_reg
= NULL
;
3298 tree lhs
= gimple_call_lhs (call_stmt
);
3301 /* Normally we access the top-level frame, which is:
3302 path_var (expr, get_stack_depth () - 1)
3303 whereas here we need the caller frame, hence "- 2" here. */
3304 gcc_assert (get_stack_depth () >= 2);
3305 result_dst_reg
= get_lvalue (path_var (lhs
, get_stack_depth () - 2),
3309 pop_frame (result_dst_reg
, NULL
, ctxt
);
3312 /* Extract calling information from the superedge and update the model for the
3316 region_model::update_for_call_superedge (const call_superedge
&call_edge
,
3317 region_model_context
*ctxt
)
3319 const gcall
*call_stmt
= call_edge
.get_call_stmt ();
3320 update_for_gcall (call_stmt
, ctxt
, call_edge
.get_callee_function ());
3323 /* Extract calling information from the return superedge and update the model
3324 for the returning call */
3327 region_model::update_for_return_superedge (const return_superedge
&return_edge
,
3328 region_model_context
*ctxt
)
3330 const gcall
*call_stmt
= return_edge
.get_call_stmt ();
3331 update_for_return_gcall (call_stmt
, ctxt
);
3334 /* Update this region_model with a summary of the effect of calling
3335 and returning from CG_SEDGE.
3337 TODO: Currently this is extremely simplistic: we merely set the
3338 return value to "unknown". A proper implementation would e.g. update
3339 sm-state, and presumably be reworked to support multiple outcomes. */
3342 region_model::update_for_call_summary (const callgraph_superedge
&cg_sedge
,
3343 region_model_context
*ctxt
)
3345 /* For now, set any return value to "unknown". */
3346 const gcall
*call_stmt
= cg_sedge
.get_call_stmt ();
3347 tree lhs
= gimple_call_lhs (call_stmt
);
3349 mark_region_as_unknown (get_lvalue (lhs
, ctxt
),
3350 ctxt
? ctxt
->get_uncertainty () : NULL
);
3352 // TODO: actually implement some kind of summary here
3355 /* Given a true or false edge guarded by conditional statement COND_STMT,
3356 determine appropriate constraints for the edge to be taken.
3358 If they are feasible, add the constraints and return true.
3360 Return false if the constraints contradict existing knowledge
3361 (and so the edge should not be taken).
3362 When returning false, if OUT is non-NULL, write a new rejected_constraint
3366 region_model::apply_constraints_for_gcond (const cfg_superedge
&sedge
,
3367 const gcond
*cond_stmt
,
3368 region_model_context
*ctxt
,
3369 rejected_constraint
**out
)
3371 ::edge cfg_edge
= sedge
.get_cfg_edge ();
3372 gcc_assert (cfg_edge
!= NULL
);
3373 gcc_assert (cfg_edge
->flags
& (EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
));
3375 enum tree_code op
= gimple_cond_code (cond_stmt
);
3376 tree lhs
= gimple_cond_lhs (cond_stmt
);
3377 tree rhs
= gimple_cond_rhs (cond_stmt
);
3378 if (cfg_edge
->flags
& EDGE_FALSE_VALUE
)
3379 op
= invert_tree_comparison (op
, false /* honor_nans */);
3380 return add_constraint (lhs
, op
, rhs
, ctxt
, out
);
3383 /* Given an EDGE guarded by SWITCH_STMT, determine appropriate constraints
3384 for the edge to be taken.
3386 If they are feasible, add the constraints and return true.
3388 Return false if the constraints contradict existing knowledge
3389 (and so the edge should not be taken).
3390 When returning false, if OUT is non-NULL, write a new rejected_constraint
3394 region_model::apply_constraints_for_gswitch (const switch_cfg_superedge
&edge
,
3395 const gswitch
*switch_stmt
,
3396 region_model_context
*ctxt
,
3397 rejected_constraint
**out
)
3399 bounded_ranges_manager
*ranges_mgr
= get_range_manager ();
3400 const bounded_ranges
*all_cases_ranges
3401 = ranges_mgr
->get_or_create_ranges_for_switch (&edge
, switch_stmt
);
3402 tree index
= gimple_switch_index (switch_stmt
);
3403 const svalue
*index_sval
= get_rvalue (index
, ctxt
);
3404 bool sat
= m_constraints
->add_bounded_ranges (index_sval
, all_cases_ranges
);
3406 *out
= new rejected_ranges_constraint (*this, index
, all_cases_ranges
);
3410 /* Apply any constraints due to an exception being thrown at LAST_STMT.
3412 If they are feasible, add the constraints and return true.
3414 Return false if the constraints contradict existing knowledge
3415 (and so the edge should not be taken).
3416 When returning false, if OUT is non-NULL, write a new rejected_constraint
3420 region_model::apply_constraints_for_exception (const gimple
*last_stmt
,
3421 region_model_context
*ctxt
,
3422 rejected_constraint
**out
)
3424 gcc_assert (last_stmt
);
3425 if (const gcall
*call
= dyn_cast
<const gcall
*> (last_stmt
))
3426 if (tree callee_fndecl
= get_fndecl_for_call (call
, ctxt
))
3427 if (is_named_call_p (callee_fndecl
, "operator new", call
, 1)
3428 || is_named_call_p (callee_fndecl
, "operator new []", call
, 1))
3430 /* We have an exception thrown from operator new.
3431 Add a constraint that the result was NULL, to avoid a false
3432 leak report due to the result being lost when following
3434 if (tree lhs
= gimple_call_lhs (call
))
3435 return add_constraint (lhs
, EQ_EXPR
, null_pointer_node
, ctxt
, out
);
3441 /* For use with push_frame when handling a top-level call within the analysis.
3442 PARAM has a defined but unknown initial value.
3443 Anything it points to has escaped, since the calling context "knows"
3444 the pointer, and thus calls to unknown functions could read/write into
3448 region_model::on_top_level_param (tree param
,
3449 region_model_context
*ctxt
)
3451 if (POINTER_TYPE_P (TREE_TYPE (param
)))
3453 const region
*param_reg
= get_lvalue (param
, ctxt
);
3454 const svalue
*init_ptr_sval
3455 = m_mgr
->get_or_create_initial_value (param_reg
);
3456 const region
*pointee_reg
= m_mgr
->get_symbolic_region (init_ptr_sval
);
3457 m_store
.mark_as_escaped (pointee_reg
);
3461 /* Update this region_model to reflect pushing a frame onto the stack
3464 If ARG_SVALS is non-NULL, use it to populate the parameters
3466 Otherwise, the params have their initial_svalues.
3468 Return the frame_region for the new frame. */
3471 region_model::push_frame (function
*fun
, const vec
<const svalue
*> *arg_svals
,
3472 region_model_context
*ctxt
)
3474 m_current_frame
= m_mgr
->get_frame_region (m_current_frame
, fun
);
3477 /* Arguments supplied from a caller frame. */
3478 tree fndecl
= fun
->decl
;
3480 for (tree iter_parm
= DECL_ARGUMENTS (fndecl
); iter_parm
;
3481 iter_parm
= DECL_CHAIN (iter_parm
), ++idx
)
3483 /* If there's a mismatching declaration, the call stmt might
3484 not have enough args. Handle this case by leaving the
3485 rest of the params as uninitialized. */
3486 if (idx
>= arg_svals
->length ())
3488 tree parm_lval
= iter_parm
;
3489 if (tree parm_default_ssa
= ssa_default_def (fun
, iter_parm
))
3490 parm_lval
= parm_default_ssa
;
3491 const region
*parm_reg
= get_lvalue (parm_lval
, ctxt
);
3492 const svalue
*arg_sval
= (*arg_svals
)[idx
];
3493 set_value (parm_reg
, arg_sval
, ctxt
);
3498 /* Otherwise we have a top-level call within the analysis. The params
3499 have defined but unknown initial values.
3500 Anything they point to has escaped. */
3501 tree fndecl
= fun
->decl
;
3502 for (tree iter_parm
= DECL_ARGUMENTS (fndecl
); iter_parm
;
3503 iter_parm
= DECL_CHAIN (iter_parm
))
3505 if (tree parm_default_ssa
= ssa_default_def (fun
, iter_parm
))
3506 on_top_level_param (parm_default_ssa
, ctxt
);
3508 on_top_level_param (iter_parm
, ctxt
);
3512 return m_current_frame
;
3515 /* Get the function of the top-most frame in this region_model's stack.
3516 There must be such a frame. */
3519 region_model::get_current_function () const
3521 const frame_region
*frame
= get_current_frame ();
3523 return frame
->get_function ();
3526 /* Pop the topmost frame_region from this region_model's stack;
3528 If RESULT_DST_REG is non-null, copy any return value from the frame
3529 into RESULT_DST_REG's region.
3530 If OUT_RESULT is non-null, copy any return value from the frame
3533 Purge the frame region and all its descendent regions.
3534 Convert any pointers that point into such regions into
3535 POISON_KIND_POPPED_STACK svalues. */
3538 region_model::pop_frame (const region
*result_dst_reg
,
3539 const svalue
**out_result
,
3540 region_model_context
*ctxt
)
3542 gcc_assert (m_current_frame
);
3544 /* Evaluate the result, within the callee frame. */
3545 const frame_region
*frame_reg
= m_current_frame
;
3546 tree fndecl
= m_current_frame
->get_function ()->decl
;
3547 tree result
= DECL_RESULT (fndecl
);
3548 if (result
&& TREE_TYPE (result
) != void_type_node
)
3552 /* Copy the result to RESULT_DST_REG. */
3553 copy_region (result_dst_reg
,
3554 get_lvalue (result
, ctxt
),
3558 *out_result
= get_rvalue (result
, ctxt
);
3561 /* Pop the frame. */
3562 m_current_frame
= m_current_frame
->get_calling_frame ();
3564 unbind_region_and_descendents (frame_reg
,POISON_KIND_POPPED_STACK
);
3567 /* Get the number of frames in this region_model's stack. */
3570 region_model::get_stack_depth () const
3572 const frame_region
*frame
= get_current_frame ();
3574 return frame
->get_stack_depth ();
3579 /* Get the frame_region with the given index within the stack.
3580 The frame_region must exist. */
3582 const frame_region
*
3583 region_model::get_frame_at_index (int index
) const
3585 const frame_region
*frame
= get_current_frame ();
3587 gcc_assert (index
>= 0);
3588 gcc_assert (index
<= frame
->get_index ());
3589 while (index
!= frame
->get_index ())
3591 frame
= frame
->get_calling_frame ();
3597 /* Unbind svalues for any regions in REG and below.
3598 Find any pointers to such regions; convert them to
3599 poisoned values of kind PKIND.
3600 Also purge any dynamic extents. */
3603 region_model::unbind_region_and_descendents (const region
*reg
,
3604 enum poison_kind pkind
)
3606 /* Gather a set of base regions to be unbound. */
3607 hash_set
<const region
*> base_regs
;
3608 for (store::cluster_map_t::iterator iter
= m_store
.begin ();
3609 iter
!= m_store
.end (); ++iter
)
3611 const region
*iter_base_reg
= (*iter
).first
;
3612 if (iter_base_reg
->descendent_of_p (reg
))
3613 base_regs
.add (iter_base_reg
);
3615 for (hash_set
<const region
*>::iterator iter
= base_regs
.begin ();
3616 iter
!= base_regs
.end (); ++iter
)
3617 m_store
.purge_cluster (*iter
);
3619 /* Find any pointers to REG or its descendents; convert to poisoned. */
3620 poison_any_pointers_to_descendents (reg
, pkind
);
3622 /* Purge dynamic extents of any base regions in REG and below
3623 (e.g. VLAs and alloca stack regions). */
3624 for (auto iter
: m_dynamic_extents
)
3626 const region
*iter_reg
= iter
.first
;
3627 if (iter_reg
->descendent_of_p (reg
))
3628 unset_dynamic_extents (iter_reg
);
3632 /* Implementation of BindingVisitor.
3633 Update the bound svalues for regions below REG to use poisoned
3636 struct bad_pointer_finder
3638 bad_pointer_finder (const region
*reg
, enum poison_kind pkind
,
3639 region_model_manager
*mgr
)
3640 : m_reg (reg
), m_pkind (pkind
), m_mgr (mgr
), m_count (0)
3643 void on_binding (const binding_key
*, const svalue
*&sval
)
3645 if (const region_svalue
*ptr_sval
= sval
->dyn_cast_region_svalue ())
3647 const region
*ptr_dst
= ptr_sval
->get_pointee ();
3648 /* Poison ptrs to descendents of REG, but not to REG itself,
3649 otherwise double-free detection doesn't work (since sm-state
3650 for "free" is stored on the original ptr svalue). */
3651 if (ptr_dst
->descendent_of_p (m_reg
)
3652 && ptr_dst
!= m_reg
)
3654 sval
= m_mgr
->get_or_create_poisoned_svalue (m_pkind
,
3661 const region
*m_reg
;
3662 enum poison_kind m_pkind
;
3663 region_model_manager
*const m_mgr
;
3667 /* Find any pointers to REG or its descendents; convert them to
3668 poisoned values of kind PKIND.
3669 Return the number of pointers that were poisoned. */
3672 region_model::poison_any_pointers_to_descendents (const region
*reg
,
3673 enum poison_kind pkind
)
3675 bad_pointer_finder
bv (reg
, pkind
, m_mgr
);
3676 m_store
.for_each_binding (bv
);
3680 /* Attempt to merge THIS with OTHER_MODEL, writing the result
3681 to OUT_MODEL. Use POINT to distinguish values created as a
3682 result of merging. */
3685 region_model::can_merge_with_p (const region_model
&other_model
,
3686 const program_point
&point
,
3687 region_model
*out_model
,
3688 const extrinsic_state
*ext_state
,
3689 const program_state
*state_a
,
3690 const program_state
*state_b
) const
3692 gcc_assert (out_model
);
3693 gcc_assert (m_mgr
== other_model
.m_mgr
);
3694 gcc_assert (m_mgr
== out_model
->m_mgr
);
3696 if (m_current_frame
!= other_model
.m_current_frame
)
3698 out_model
->m_current_frame
= m_current_frame
;
3700 model_merger
m (this, &other_model
, point
, out_model
,
3701 ext_state
, state_a
, state_b
);
3703 if (!store::can_merge_p (&m_store
, &other_model
.m_store
,
3704 &out_model
->m_store
, m_mgr
->get_store_manager (),
3708 if (!m_dynamic_extents
.can_merge_with_p (other_model
.m_dynamic_extents
,
3709 &out_model
->m_dynamic_extents
))
3712 /* Merge constraints. */
3713 constraint_manager::merge (*m_constraints
,
3714 *other_model
.m_constraints
,
3715 out_model
->m_constraints
);
3720 /* Attempt to get the fndecl used at CALL, if known, or NULL_TREE
3724 region_model::get_fndecl_for_call (const gcall
*call
,
3725 region_model_context
*ctxt
)
3727 tree fn_ptr
= gimple_call_fn (call
);
3728 if (fn_ptr
== NULL_TREE
)
3730 const svalue
*fn_ptr_sval
= get_rvalue (fn_ptr
, ctxt
);
3731 if (const region_svalue
*fn_ptr_ptr
3732 = fn_ptr_sval
->dyn_cast_region_svalue ())
3734 const region
*reg
= fn_ptr_ptr
->get_pointee ();
3735 if (const function_region
*fn_reg
= reg
->dyn_cast_function_region ())
3737 tree fn_decl
= fn_reg
->get_fndecl ();
3738 cgraph_node
*node
= cgraph_node::get (fn_decl
);
3741 const cgraph_node
*ultimate_node
= node
->ultimate_alias_target ();
3743 return ultimate_node
->decl
;
3750 /* Would be much simpler to use a lambda here, if it were supported. */
3752 struct append_ssa_names_cb_data
3754 const region_model
*model
;
3755 auto_vec
<const decl_region
*> *out
;
3758 /* Populate *OUT with all decl_regions for SSA names in the current
3759 frame that have clusters within the store. */
3763 get_ssa_name_regions_for_current_frame (auto_vec
<const decl_region
*> *out
)
3766 append_ssa_names_cb_data data
;
3769 m_store
.for_each_cluster (append_ssa_names_cb
, &data
);
3772 /* Implementation detail of get_ssa_name_regions_for_current_frame. */
3775 region_model::append_ssa_names_cb (const region
*base_reg
,
3776 append_ssa_names_cb_data
*cb_data
)
3778 if (base_reg
->get_parent_region () != cb_data
->model
->m_current_frame
)
3780 if (const decl_region
*decl_reg
= base_reg
->dyn_cast_decl_region ())
3782 if (TREE_CODE (decl_reg
->get_decl ()) == SSA_NAME
)
3783 cb_data
->out
->safe_push (decl_reg
);
3787 /* Return a new region describing a heap-allocated block of memory.
3788 Use CTXT to complain about tainted sizes. */
3791 region_model::create_region_for_heap_alloc (const svalue
*size_in_bytes
,
3792 region_model_context
*ctxt
)
3794 const region
*reg
= m_mgr
->create_region_for_heap_alloc ();
3795 if (compat_types_p (size_in_bytes
->get_type (), size_type_node
))
3796 set_dynamic_extents (reg
, size_in_bytes
, ctxt
);
3800 /* Return a new region describing a block of memory allocated within the
3802 Use CTXT to complain about tainted sizes. */
3805 region_model::create_region_for_alloca (const svalue
*size_in_bytes
,
3806 region_model_context
*ctxt
)
3808 const region
*reg
= m_mgr
->create_region_for_alloca (m_current_frame
);
3809 if (compat_types_p (size_in_bytes
->get_type (), size_type_node
))
3810 set_dynamic_extents (reg
, size_in_bytes
, ctxt
);
3814 /* Record that the size of REG is SIZE_IN_BYTES.
3815 Use CTXT to complain about tainted sizes. */
3818 region_model::set_dynamic_extents (const region
*reg
,
3819 const svalue
*size_in_bytes
,
3820 region_model_context
*ctxt
)
3822 assert_compat_types (size_in_bytes
->get_type (), size_type_node
);
3824 check_dynamic_size_for_taint (reg
->get_memory_space (), size_in_bytes
,
3826 m_dynamic_extents
.put (reg
, size_in_bytes
);
3829 /* Get the recording of REG in bytes, or NULL if no dynamic size was
3833 region_model::get_dynamic_extents (const region
*reg
) const
3835 if (const svalue
* const *slot
= m_dynamic_extents
.get (reg
))
3840 /* Unset any recorded dynamic size of REG. */
3843 region_model::unset_dynamic_extents (const region
*reg
)
3845 m_dynamic_extents
.remove (reg
);
3848 /* class noop_region_model_context : public region_model_context. */
3851 noop_region_model_context::bifurcate (custom_edge_info
*info
)
3857 noop_region_model_context::terminate_path ()
3861 /* struct model_merger. */
3863 /* Dump a multiline representation of this merger to PP. */
3866 model_merger::dump_to_pp (pretty_printer
*pp
, bool simple
) const
3868 pp_string (pp
, "model A:");
3870 m_model_a
->dump_to_pp (pp
, simple
, true);
3873 pp_string (pp
, "model B:");
3875 m_model_b
->dump_to_pp (pp
, simple
, true);
3878 pp_string (pp
, "merged model:");
3880 m_merged_model
->dump_to_pp (pp
, simple
, true);
3884 /* Dump a multiline representation of this merger to FILE. */
3887 model_merger::dump (FILE *fp
, bool simple
) const
3890 pp_format_decoder (&pp
) = default_tree_printer
;
3891 pp_show_color (&pp
) = pp_show_color (global_dc
->printer
);
3892 pp
.buffer
->stream
= fp
;
3893 dump_to_pp (&pp
, simple
);
3897 /* Dump a multiline representation of this merger to stderr. */
3900 model_merger::dump (bool simple
) const
3902 dump (stderr
, simple
);
3905 /* Return true if it's OK to merge SVAL with other svalues. */
3908 model_merger::mergeable_svalue_p (const svalue
*sval
) const
3912 /* Reject merging svalues that have non-purgable sm-state,
3913 to avoid falsely reporting memory leaks by merging them
3914 with something else. For example, given a local var "p",
3915 reject the merger of a:
3916 store_a mapping "p" to a malloc-ed ptr
3918 store_b mapping "p" to a NULL ptr. */
3920 if (!m_state_a
->can_purge_p (*m_ext_state
, sval
))
3923 if (!m_state_b
->can_purge_p (*m_ext_state
, sval
))
3931 /* Dump RMODEL fully to stderr (i.e. without summarization). */
3934 debug (const region_model
&rmodel
)
3936 rmodel
.dump (false);
3939 /* class rejected_op_constraint : public rejected_constraint. */
3942 rejected_op_constraint::dump_to_pp (pretty_printer
*pp
) const
3944 region_model
m (m_model
);
3945 const svalue
*lhs_sval
= m
.get_rvalue (m_lhs
, NULL
);
3946 const svalue
*rhs_sval
= m
.get_rvalue (m_rhs
, NULL
);
3947 lhs_sval
->dump_to_pp (pp
, true);
3948 pp_printf (pp
, " %s ", op_symbol_code (m_op
));
3949 rhs_sval
->dump_to_pp (pp
, true);
3952 /* class rejected_ranges_constraint : public rejected_constraint. */
3955 rejected_ranges_constraint::dump_to_pp (pretty_printer
*pp
) const
3957 region_model
m (m_model
);
3958 const svalue
*sval
= m
.get_rvalue (m_expr
, NULL
);
3959 sval
->dump_to_pp (pp
, true);
3960 pp_string (pp
, " in ");
3961 m_ranges
->dump_to_pp (pp
, true);
3966 /* Dump the managed objects by class to LOGGER, and the per-class totals. */
3969 engine::log_stats (logger
*logger
) const
3971 m_mgr
.log_stats (logger
, true);
3978 namespace selftest
{
3980 /* Build a constant tree of the given type from STR. */
3983 build_real_cst_from_string (tree type
, const char *str
)
3985 REAL_VALUE_TYPE real
;
3986 real_from_string (&real
, str
);
3987 return build_real (type
, real
);
3990 /* Append various "interesting" constants to OUT (e.g. NaN). */
3993 append_interesting_constants (auto_vec
<tree
> *out
)
3995 out
->safe_push (build_int_cst (integer_type_node
, 0));
3996 out
->safe_push (build_int_cst (integer_type_node
, 42));
3997 out
->safe_push (build_int_cst (unsigned_type_node
, 0));
3998 out
->safe_push (build_int_cst (unsigned_type_node
, 42));
3999 out
->safe_push (build_real_cst_from_string (float_type_node
, "QNaN"));
4000 out
->safe_push (build_real_cst_from_string (float_type_node
, "-QNaN"));
4001 out
->safe_push (build_real_cst_from_string (float_type_node
, "SNaN"));
4002 out
->safe_push (build_real_cst_from_string (float_type_node
, "-SNaN"));
4003 out
->safe_push (build_real_cst_from_string (float_type_node
, "0.0"));
4004 out
->safe_push (build_real_cst_from_string (float_type_node
, "-0.0"));
4005 out
->safe_push (build_real_cst_from_string (float_type_node
, "Inf"));
4006 out
->safe_push (build_real_cst_from_string (float_type_node
, "-Inf"));
4009 /* Verify that tree_cmp is a well-behaved comparator for qsort, even
4010 if the underlying constants aren't comparable. */
4013 test_tree_cmp_on_constants ()
4015 auto_vec
<tree
> csts
;
4016 append_interesting_constants (&csts
);
4018 /* Try sorting every triple. */
4019 const unsigned num
= csts
.length ();
4020 for (unsigned i
= 0; i
< num
; i
++)
4021 for (unsigned j
= 0; j
< num
; j
++)
4022 for (unsigned k
= 0; k
< num
; k
++)
4024 auto_vec
<tree
> v (3);
4025 v
.quick_push (csts
[i
]);
4026 v
.quick_push (csts
[j
]);
4027 v
.quick_push (csts
[k
]);
4032 /* Implementation detail of the ASSERT_CONDITION_* macros. */
4035 assert_condition (const location
&loc
,
4036 region_model
&model
,
4037 const svalue
*lhs
, tree_code op
, const svalue
*rhs
,
4040 tristate actual
= model
.eval_condition (lhs
, op
, rhs
);
4041 ASSERT_EQ_AT (loc
, actual
, expected
);
4044 /* Implementation detail of the ASSERT_CONDITION_* macros. */
4047 assert_condition (const location
&loc
,
4048 region_model
&model
,
4049 tree lhs
, tree_code op
, tree rhs
,
4052 tristate actual
= model
.eval_condition (lhs
, op
, rhs
, NULL
);
4053 ASSERT_EQ_AT (loc
, actual
, expected
);
4056 /* Implementation detail of ASSERT_DUMP_TREE_EQ. */
4059 assert_dump_tree_eq (const location
&loc
, tree t
, const char *expected
)
4061 auto_fix_quotes sentinel
;
4063 pp_format_decoder (&pp
) = default_tree_printer
;
4065 ASSERT_STREQ_AT (loc
, pp_formatted_text (&pp
), expected
);
4068 /* Assert that dump_tree (T) is EXPECTED. */
4070 #define ASSERT_DUMP_TREE_EQ(T, EXPECTED) \
4071 SELFTEST_BEGIN_STMT \
4072 assert_dump_tree_eq ((SELFTEST_LOCATION), (T), (EXPECTED)); \
4075 /* Implementation detail of ASSERT_DUMP_EQ. */
4078 assert_dump_eq (const location
&loc
,
4079 const region_model
&model
,
4081 const char *expected
)
4083 auto_fix_quotes sentinel
;
4085 pp_format_decoder (&pp
) = default_tree_printer
;
4087 model
.dump_to_pp (&pp
, summarize
, true);
4088 ASSERT_STREQ_AT (loc
, pp_formatted_text (&pp
), expected
);
4091 /* Assert that MODEL.dump_to_pp (SUMMARIZE) is EXPECTED. */
4093 #define ASSERT_DUMP_EQ(MODEL, SUMMARIZE, EXPECTED) \
4094 SELFTEST_BEGIN_STMT \
4095 assert_dump_eq ((SELFTEST_LOCATION), (MODEL), (SUMMARIZE), (EXPECTED)); \
4098 /* Smoketest for region_model::dump_to_pp. */
4103 region_model_manager mgr
;
4104 region_model
model (&mgr
);
4106 ASSERT_DUMP_EQ (model
, false,
4108 "m_called_unknown_fn: FALSE\n"
4109 "constraint_manager:\n"
4112 ASSERT_DUMP_EQ (model
, true,
4114 "m_called_unknown_fn: FALSE\n"
4115 "constraint_manager:\n"
4120 /* Helper function for selftests. Create a struct or union type named NAME,
4121 with the fields given by the FIELD_DECLS in FIELDS.
4122 If IS_STRUCT is true create a RECORD_TYPE (aka a struct), otherwise
4123 create a UNION_TYPE. */
4126 make_test_compound_type (const char *name
, bool is_struct
,
4127 const auto_vec
<tree
> *fields
)
4129 tree t
= make_node (is_struct
? RECORD_TYPE
: UNION_TYPE
);
4130 TYPE_NAME (t
) = get_identifier (name
);
4133 tree fieldlist
= NULL
;
4136 FOR_EACH_VEC_ELT (*fields
, i
, field
)
4138 gcc_assert (TREE_CODE (field
) == FIELD_DECL
);
4139 DECL_CONTEXT (field
) = t
;
4140 fieldlist
= chainon (field
, fieldlist
);
4142 fieldlist
= nreverse (fieldlist
);
4143 TYPE_FIELDS (t
) = fieldlist
;
4149 /* Selftest fixture for creating the type "struct coord {int x; int y; };". */
4155 auto_vec
<tree
> fields
;
4156 m_x_field
= build_decl (UNKNOWN_LOCATION
, FIELD_DECL
,
4157 get_identifier ("x"), integer_type_node
);
4158 fields
.safe_push (m_x_field
);
4159 m_y_field
= build_decl (UNKNOWN_LOCATION
, FIELD_DECL
,
4160 get_identifier ("y"), integer_type_node
);
4161 fields
.safe_push (m_y_field
);
4162 m_coord_type
= make_test_compound_type ("coord", true, &fields
);
4170 /* Verify usage of a struct. */
4177 tree c
= build_global_decl ("c", ct
.m_coord_type
);
4178 tree c_x
= build3 (COMPONENT_REF
, TREE_TYPE (ct
.m_x_field
),
4179 c
, ct
.m_x_field
, NULL_TREE
);
4180 tree c_y
= build3 (COMPONENT_REF
, TREE_TYPE (ct
.m_y_field
),
4181 c
, ct
.m_y_field
, NULL_TREE
);
4183 tree int_17
= build_int_cst (integer_type_node
, 17);
4184 tree int_m3
= build_int_cst (integer_type_node
, -3);
4186 region_model_manager mgr
;
4187 region_model
model (&mgr
);
4188 model
.set_value (c_x
, int_17
, NULL
);
4189 model
.set_value (c_y
, int_m3
, NULL
);
4191 /* Verify get_offset for "c.x". */
4193 const region
*c_x_reg
= model
.get_lvalue (c_x
, NULL
);
4194 region_offset offset
= c_x_reg
->get_offset ();
4195 ASSERT_EQ (offset
.get_base_region (), model
.get_lvalue (c
, NULL
));
4196 ASSERT_EQ (offset
.get_bit_offset (), 0);
4199 /* Verify get_offset for "c.y". */
4201 const region
*c_y_reg
= model
.get_lvalue (c_y
, NULL
);
4202 region_offset offset
= c_y_reg
->get_offset ();
4203 ASSERT_EQ (offset
.get_base_region (), model
.get_lvalue (c
, NULL
));
4204 ASSERT_EQ (offset
.get_bit_offset (), INT_TYPE_SIZE
);
4208 /* Verify usage of an array element. */
4213 tree tlen
= size_int (10);
4214 tree arr_type
= build_array_type (char_type_node
, build_index_type (tlen
));
4216 tree a
= build_global_decl ("a", arr_type
);
4218 region_model_manager mgr
;
4219 region_model
model (&mgr
);
4220 tree int_0
= build_int_cst (integer_type_node
, 0);
4221 tree a_0
= build4 (ARRAY_REF
, char_type_node
,
4222 a
, int_0
, NULL_TREE
, NULL_TREE
);
4223 tree char_A
= build_int_cst (char_type_node
, 'A');
4224 model
.set_value (a_0
, char_A
, NULL
);
4227 /* Verify that region_model::get_representative_tree works as expected. */
4230 test_get_representative_tree ()
4232 region_model_manager mgr
;
4236 tree string_cst
= build_string (4, "foo");
4237 region_model
m (&mgr
);
4238 const svalue
*str_sval
= m
.get_rvalue (string_cst
, NULL
);
4239 tree rep
= m
.get_representative_tree (str_sval
);
4240 ASSERT_EQ (rep
, string_cst
);
4243 /* String literal. */
4245 tree string_cst_ptr
= build_string_literal (4, "foo");
4246 region_model
m (&mgr
);
4247 const svalue
*str_sval
= m
.get_rvalue (string_cst_ptr
, NULL
);
4248 tree rep
= m
.get_representative_tree (str_sval
);
4249 ASSERT_DUMP_TREE_EQ (rep
, "&\"foo\"[0]");
4252 /* Value of an element within an array. */
4254 tree tlen
= size_int (10);
4255 tree arr_type
= build_array_type (char_type_node
, build_index_type (tlen
));
4256 tree a
= build_global_decl ("a", arr_type
);
4257 placeholder_svalue
test_sval (char_type_node
, "test value");
4259 /* Value of a[3]. */
4261 test_region_model_context ctxt
;
4262 region_model
model (&mgr
);
4263 tree int_3
= build_int_cst (integer_type_node
, 3);
4264 tree a_3
= build4 (ARRAY_REF
, char_type_node
,
4265 a
, int_3
, NULL_TREE
, NULL_TREE
);
4266 const region
*a_3_reg
= model
.get_lvalue (a_3
, &ctxt
);
4267 model
.set_value (a_3_reg
, &test_sval
, &ctxt
);
4268 tree rep
= model
.get_representative_tree (&test_sval
);
4269 ASSERT_DUMP_TREE_EQ (rep
, "a[3]");
4272 /* Value of a[0]. */
4274 test_region_model_context ctxt
;
4275 region_model
model (&mgr
);
4276 tree idx
= build_int_cst (integer_type_node
, 0);
4277 tree a_0
= build4 (ARRAY_REF
, char_type_node
,
4278 a
, idx
, NULL_TREE
, NULL_TREE
);
4279 const region
*a_0_reg
= model
.get_lvalue (a_0
, &ctxt
);
4280 model
.set_value (a_0_reg
, &test_sval
, &ctxt
);
4281 tree rep
= model
.get_representative_tree (&test_sval
);
4282 ASSERT_DUMP_TREE_EQ (rep
, "a[0]");
4286 /* Value of a field within a struct. */
4290 tree c
= build_global_decl ("c", ct
.m_coord_type
);
4291 tree c_x
= build3 (COMPONENT_REF
, TREE_TYPE (ct
.m_x_field
),
4292 c
, ct
.m_x_field
, NULL_TREE
);
4293 tree c_y
= build3 (COMPONENT_REF
, TREE_TYPE (ct
.m_y_field
),
4294 c
, ct
.m_y_field
, NULL_TREE
);
4296 test_region_model_context ctxt
;
4298 /* Value of initial field. */
4300 region_model
m (&mgr
);
4301 const region
*c_x_reg
= m
.get_lvalue (c_x
, &ctxt
);
4302 placeholder_svalue
test_sval_x (integer_type_node
, "test x val");
4303 m
.set_value (c_x_reg
, &test_sval_x
, &ctxt
);
4304 tree rep
= m
.get_representative_tree (&test_sval_x
);
4305 ASSERT_DUMP_TREE_EQ (rep
, "c.x");
4308 /* Value of non-initial field. */
4310 region_model
m (&mgr
);
4311 const region
*c_y_reg
= m
.get_lvalue (c_y
, &ctxt
);
4312 placeholder_svalue
test_sval_y (integer_type_node
, "test y val");
4313 m
.set_value (c_y_reg
, &test_sval_y
, &ctxt
);
4314 tree rep
= m
.get_representative_tree (&test_sval_y
);
4315 ASSERT_DUMP_TREE_EQ (rep
, "c.y");
4320 /* Verify that calling region_model::get_rvalue repeatedly on the same
4321 tree constant retrieves the same svalue *. */
4324 test_unique_constants ()
4326 tree int_0
= build_int_cst (integer_type_node
, 0);
4327 tree int_42
= build_int_cst (integer_type_node
, 42);
4329 test_region_model_context ctxt
;
4330 region_model_manager mgr
;
4331 region_model
model (&mgr
);
4332 ASSERT_EQ (model
.get_rvalue (int_0
, &ctxt
), model
.get_rvalue (int_0
, &ctxt
));
4333 ASSERT_EQ (model
.get_rvalue (int_42
, &ctxt
),
4334 model
.get_rvalue (int_42
, &ctxt
));
4335 ASSERT_NE (model
.get_rvalue (int_0
, &ctxt
), model
.get_rvalue (int_42
, &ctxt
));
4336 ASSERT_EQ (ctxt
.get_num_diagnostics (), 0);
4338 /* A "(const int)42" will be a different tree from "(int)42)"... */
4339 tree const_int_type_node
4340 = build_qualified_type (integer_type_node
, TYPE_QUAL_CONST
);
4341 tree const_int_42
= build_int_cst (const_int_type_node
, 42);
4342 ASSERT_NE (int_42
, const_int_42
);
4343 /* It should have a different const_svalue. */
4344 const svalue
*int_42_sval
= model
.get_rvalue (int_42
, &ctxt
);
4345 const svalue
*const_int_42_sval
= model
.get_rvalue (const_int_42
, &ctxt
);
4346 ASSERT_NE (int_42_sval
, const_int_42_sval
);
4347 /* But they should compare as equal. */
4348 ASSERT_CONDITION_TRUE (model
, int_42_sval
, EQ_EXPR
, const_int_42_sval
);
4349 ASSERT_CONDITION_FALSE (model
, int_42_sval
, NE_EXPR
, const_int_42_sval
);
4352 /* Verify that each type gets its own singleton unknown_svalue within a
4353 region_model_manager, and that NULL_TREE gets its own singleton. */
4356 test_unique_unknowns ()
4358 region_model_manager mgr
;
4359 const svalue
*unknown_int
4360 = mgr
.get_or_create_unknown_svalue (integer_type_node
);
4361 /* Repeated calls with the same type should get the same "unknown"
4363 const svalue
*unknown_int_2
4364 = mgr
.get_or_create_unknown_svalue (integer_type_node
);
4365 ASSERT_EQ (unknown_int
, unknown_int_2
);
4367 /* Different types (or the NULL type) should have different
4369 const svalue
*unknown_NULL_type
= mgr
.get_or_create_unknown_svalue (NULL
);
4370 ASSERT_NE (unknown_NULL_type
, unknown_int
);
4372 /* Repeated calls with NULL for the type should get the same "unknown"
4374 const svalue
*unknown_NULL_type_2
= mgr
.get_or_create_unknown_svalue (NULL
);
4375 ASSERT_EQ (unknown_NULL_type
, unknown_NULL_type_2
);
4378 /* Verify that initial_svalue are handled as expected. */
4381 test_initial_svalue_folding ()
4383 region_model_manager mgr
;
4384 tree x
= build_global_decl ("x", integer_type_node
);
4385 tree y
= build_global_decl ("y", integer_type_node
);
4387 test_region_model_context ctxt
;
4388 region_model
model (&mgr
);
4389 const svalue
*x_init
= model
.get_rvalue (x
, &ctxt
);
4390 const svalue
*y_init
= model
.get_rvalue (y
, &ctxt
);
4391 ASSERT_NE (x_init
, y_init
);
4392 const region
*x_reg
= model
.get_lvalue (x
, &ctxt
);
4393 ASSERT_EQ (x_init
, mgr
.get_or_create_initial_value (x_reg
));
4397 /* Verify that unary ops are folded as expected. */
4400 test_unaryop_svalue_folding ()
4402 region_model_manager mgr
;
4403 tree x
= build_global_decl ("x", integer_type_node
);
4404 tree y
= build_global_decl ("y", integer_type_node
);
4406 test_region_model_context ctxt
;
4407 region_model
model (&mgr
);
4408 const svalue
*x_init
= model
.get_rvalue (x
, &ctxt
);
4409 const svalue
*y_init
= model
.get_rvalue (y
, &ctxt
);
4410 const region
*x_reg
= model
.get_lvalue (x
, &ctxt
);
4411 ASSERT_EQ (x_init
, mgr
.get_or_create_initial_value (x_reg
));
4413 /* "(int)x" -> "x". */
4414 ASSERT_EQ (x_init
, mgr
.get_or_create_cast (integer_type_node
, x_init
));
4416 /* "(void *)x" -> something other than "x". */
4417 ASSERT_NE (x_init
, mgr
.get_or_create_cast (ptr_type_node
, x_init
));
4419 /* "!(x == y)" -> "x != y". */
4420 ASSERT_EQ (mgr
.get_or_create_unaryop
4421 (boolean_type_node
, TRUTH_NOT_EXPR
,
4422 mgr
.get_or_create_binop (boolean_type_node
, EQ_EXPR
,
4424 mgr
.get_or_create_binop (boolean_type_node
, NE_EXPR
,
4426 /* "!(x > y)" -> "x <= y". */
4427 ASSERT_EQ (mgr
.get_or_create_unaryop
4428 (boolean_type_node
, TRUTH_NOT_EXPR
,
4429 mgr
.get_or_create_binop (boolean_type_node
, GT_EXPR
,
4431 mgr
.get_or_create_binop (boolean_type_node
, LE_EXPR
,
4435 /* Verify that binops on constant svalues are folded. */
4438 test_binop_svalue_folding ()
4441 tree cst_int
[NUM_CSTS
];
4442 region_model_manager mgr
;
4443 const svalue
*cst_sval
[NUM_CSTS
];
4444 for (int i
= 0; i
< NUM_CSTS
; i
++)
4446 cst_int
[i
] = build_int_cst (integer_type_node
, i
);
4447 cst_sval
[i
] = mgr
.get_or_create_constant_svalue (cst_int
[i
]);
4448 ASSERT_EQ (cst_sval
[i
]->get_kind (), SK_CONSTANT
);
4449 ASSERT_EQ (cst_sval
[i
]->maybe_get_constant (), cst_int
[i
]);
4452 for (int i
= 0; i
< NUM_CSTS
; i
++)
4453 for (int j
= 0; j
< NUM_CSTS
; j
++)
4456 ASSERT_NE (cst_sval
[i
], cst_sval
[j
]);
4457 if (i
+ j
< NUM_CSTS
)
4460 = mgr
.get_or_create_binop (integer_type_node
, PLUS_EXPR
,
4461 cst_sval
[i
], cst_sval
[j
]);
4462 ASSERT_EQ (sum
, cst_sval
[i
+ j
]);
4466 const svalue
*difference
4467 = mgr
.get_or_create_binop (integer_type_node
, MINUS_EXPR
,
4468 cst_sval
[i
], cst_sval
[j
]);
4469 ASSERT_EQ (difference
, cst_sval
[i
- j
]);
4471 if (i
* j
< NUM_CSTS
)
4473 const svalue
*product
4474 = mgr
.get_or_create_binop (integer_type_node
, MULT_EXPR
,
4475 cst_sval
[i
], cst_sval
[j
]);
4476 ASSERT_EQ (product
, cst_sval
[i
* j
]);
4478 const svalue
*eq
= mgr
.get_or_create_binop (integer_type_node
, EQ_EXPR
,
4479 cst_sval
[i
], cst_sval
[j
]);
4480 ASSERT_EQ (eq
, i
== j
? cst_sval
[1] : cst_sval
[0]);
4481 const svalue
*neq
= mgr
.get_or_create_binop (integer_type_node
, NE_EXPR
,
4482 cst_sval
[i
], cst_sval
[j
]);
4483 ASSERT_EQ (neq
, i
!= j
? cst_sval
[1] : cst_sval
[0]);
4487 tree x
= build_global_decl ("x", integer_type_node
);
4489 test_region_model_context ctxt
;
4490 region_model
model (&mgr
);
4491 const svalue
*x_init
= model
.get_rvalue (x
, &ctxt
);
4493 /* PLUS_EXPR folding. */
4494 const svalue
*x_init_plus_zero
4495 = mgr
.get_or_create_binop (integer_type_node
, PLUS_EXPR
,
4496 x_init
, cst_sval
[0]);
4497 ASSERT_EQ (x_init_plus_zero
, x_init
);
4498 const svalue
*zero_plus_x_init
4499 = mgr
.get_or_create_binop (integer_type_node
, PLUS_EXPR
,
4500 cst_sval
[0], x_init
);
4501 ASSERT_EQ (zero_plus_x_init
, x_init
);
4503 /* MULT_EXPR folding. */
4504 const svalue
*x_init_times_zero
4505 = mgr
.get_or_create_binop (integer_type_node
, MULT_EXPR
,
4506 x_init
, cst_sval
[0]);
4507 ASSERT_EQ (x_init_times_zero
, cst_sval
[0]);
4508 const svalue
*zero_times_x_init
4509 = mgr
.get_or_create_binop (integer_type_node
, MULT_EXPR
,
4510 cst_sval
[0], x_init
);
4511 ASSERT_EQ (zero_times_x_init
, cst_sval
[0]);
4513 const svalue
*x_init_times_one
4514 = mgr
.get_or_create_binop (integer_type_node
, MULT_EXPR
,
4515 x_init
, cst_sval
[1]);
4516 ASSERT_EQ (x_init_times_one
, x_init
);
4517 const svalue
*one_times_x_init
4518 = mgr
.get_or_create_binop (integer_type_node
, MULT_EXPR
,
4519 cst_sval
[1], x_init
);
4520 ASSERT_EQ (one_times_x_init
, x_init
);
4523 // TODO: do we want to use the match-and-simplify DSL for this?
4525 /* Verify that binops put any constants on the RHS. */
4526 const svalue
*four_times_x_init
4527 = mgr
.get_or_create_binop (integer_type_node
, MULT_EXPR
,
4528 cst_sval
[4], x_init
);
4529 const svalue
*x_init_times_four
4530 = mgr
.get_or_create_binop (integer_type_node
, MULT_EXPR
,
4531 x_init
, cst_sval
[4]);
4532 ASSERT_EQ (four_times_x_init
, x_init_times_four
);
4533 const binop_svalue
*binop
= four_times_x_init
->dyn_cast_binop_svalue ();
4534 ASSERT_EQ (binop
->get_op (), MULT_EXPR
);
4535 ASSERT_EQ (binop
->get_arg0 (), x_init
);
4536 ASSERT_EQ (binop
->get_arg1 (), cst_sval
[4]);
4538 /* Verify that ((x + 1) + 1) == (x + 2). */
4539 const svalue
*x_init_plus_one
4540 = mgr
.get_or_create_binop (integer_type_node
, PLUS_EXPR
,
4541 x_init
, cst_sval
[1]);
4542 const svalue
*x_init_plus_two
4543 = mgr
.get_or_create_binop (integer_type_node
, PLUS_EXPR
,
4544 x_init
, cst_sval
[2]);
4545 const svalue
*x_init_plus_one_plus_one
4546 = mgr
.get_or_create_binop (integer_type_node
, PLUS_EXPR
,
4547 x_init_plus_one
, cst_sval
[1]);
4548 ASSERT_EQ (x_init_plus_one_plus_one
, x_init_plus_two
);
4551 /* Verify that sub_svalues are folded as expected. */
4554 test_sub_svalue_folding ()
4557 tree c
= build_global_decl ("c", ct
.m_coord_type
);
4558 tree c_x
= build3 (COMPONENT_REF
, TREE_TYPE (ct
.m_x_field
),
4559 c
, ct
.m_x_field
, NULL_TREE
);
4561 region_model_manager mgr
;
4562 region_model
model (&mgr
);
4563 test_region_model_context ctxt
;
4564 const region
*c_x_reg
= model
.get_lvalue (c_x
, &ctxt
);
4566 /* Verify that sub_svalue of "unknown" simply
4567 yields an unknown. */
4569 const svalue
*unknown
= mgr
.get_or_create_unknown_svalue (ct
.m_coord_type
);
4570 const svalue
*sub
= mgr
.get_or_create_sub_svalue (TREE_TYPE (ct
.m_x_field
),
4572 ASSERT_EQ (sub
->get_kind (), SK_UNKNOWN
);
4573 ASSERT_EQ (sub
->get_type (), TREE_TYPE (ct
.m_x_field
));
4576 /* Test that region::descendent_of_p works as expected. */
4579 test_descendent_of_p ()
4581 region_model_manager mgr
;
4582 const region
*stack
= mgr
.get_stack_region ();
4583 const region
*heap
= mgr
.get_heap_region ();
4584 const region
*code
= mgr
.get_code_region ();
4585 const region
*globals
= mgr
.get_globals_region ();
4587 /* descendent_of_p should return true when used on the region itself. */
4588 ASSERT_TRUE (stack
->descendent_of_p (stack
));
4589 ASSERT_FALSE (stack
->descendent_of_p (heap
));
4590 ASSERT_FALSE (stack
->descendent_of_p (code
));
4591 ASSERT_FALSE (stack
->descendent_of_p (globals
));
4593 tree x
= build_global_decl ("x", integer_type_node
);
4594 const region
*x_reg
= mgr
.get_region_for_global (x
);
4595 ASSERT_TRUE (x_reg
->descendent_of_p (globals
));
4597 /* A cast_region should be a descendent of the original region. */
4598 const region
*cast_reg
= mgr
.get_cast_region (x_reg
, ptr_type_node
);
4599 ASSERT_TRUE (cast_reg
->descendent_of_p (x_reg
));
4602 /* Verify that simple assignments work as expected. */
4607 tree int_0
= build_int_cst (integer_type_node
, 0);
4608 tree x
= build_global_decl ("x", integer_type_node
);
4609 tree y
= build_global_decl ("y", integer_type_node
);
4611 /* "x == 0", then use of y, then "y = 0;". */
4612 region_model_manager mgr
;
4613 region_model
model (&mgr
);
4614 ADD_SAT_CONSTRAINT (model
, x
, EQ_EXPR
, int_0
);
4615 ASSERT_CONDITION_UNKNOWN (model
, y
, EQ_EXPR
, int_0
);
4616 model
.set_value (model
.get_lvalue (y
, NULL
),
4617 model
.get_rvalue (int_0
, NULL
),
4619 ASSERT_CONDITION_TRUE (model
, y
, EQ_EXPR
, int_0
);
4620 ASSERT_CONDITION_TRUE (model
, y
, EQ_EXPR
, x
);
4623 /* Verify that compound assignments work as expected. */
4626 test_compound_assignment ()
4630 tree c
= build_global_decl ("c", ct
.m_coord_type
);
4631 tree c_x
= build3 (COMPONENT_REF
, TREE_TYPE (ct
.m_x_field
),
4632 c
, ct
.m_x_field
, NULL_TREE
);
4633 tree c_y
= build3 (COMPONENT_REF
, TREE_TYPE (ct
.m_y_field
),
4634 c
, ct
.m_y_field
, NULL_TREE
);
4635 tree d
= build_global_decl ("d", ct
.m_coord_type
);
4636 tree d_x
= build3 (COMPONENT_REF
, TREE_TYPE (ct
.m_x_field
),
4637 d
, ct
.m_x_field
, NULL_TREE
);
4638 tree d_y
= build3 (COMPONENT_REF
, TREE_TYPE (ct
.m_y_field
),
4639 d
, ct
.m_y_field
, NULL_TREE
);
4641 tree int_17
= build_int_cst (integer_type_node
, 17);
4642 tree int_m3
= build_int_cst (integer_type_node
, -3);
4644 region_model_manager mgr
;
4645 region_model
model (&mgr
);
4646 model
.set_value (c_x
, int_17
, NULL
);
4647 model
.set_value (c_y
, int_m3
, NULL
);
4650 model
.copy_region (model
.get_lvalue (d
, NULL
), model
.get_lvalue (c
, NULL
),
4652 /* Check that the fields have the same svalues. */
4653 ASSERT_EQ (model
.get_rvalue (c_x
, NULL
), model
.get_rvalue (d_x
, NULL
));
4654 ASSERT_EQ (model
.get_rvalue (c_y
, NULL
), model
.get_rvalue (d_y
, NULL
));
4657 /* Verify the details of pushing and popping stack frames. */
4660 test_stack_frames ()
4662 tree int_42
= build_int_cst (integer_type_node
, 42);
4663 tree int_10
= build_int_cst (integer_type_node
, 10);
4664 tree int_5
= build_int_cst (integer_type_node
, 5);
4665 tree int_0
= build_int_cst (integer_type_node
, 0);
4667 auto_vec
<tree
> param_types
;
4668 tree parent_fndecl
= make_fndecl (integer_type_node
,
4671 allocate_struct_function (parent_fndecl
, true);
4673 tree child_fndecl
= make_fndecl (integer_type_node
,
4676 allocate_struct_function (child_fndecl
, true);
4678 /* "a" and "b" in the parent frame. */
4679 tree a
= build_decl (UNKNOWN_LOCATION
, PARM_DECL
,
4680 get_identifier ("a"),
4682 tree b
= build_decl (UNKNOWN_LOCATION
, PARM_DECL
,
4683 get_identifier ("b"),
4685 /* "x" and "y" in a child frame. */
4686 tree x
= build_decl (UNKNOWN_LOCATION
, PARM_DECL
,
4687 get_identifier ("x"),
4689 tree y
= build_decl (UNKNOWN_LOCATION
, PARM_DECL
,
4690 get_identifier ("y"),
4694 tree p
= build_global_decl ("p", ptr_type_node
);
4697 tree q
= build_global_decl ("q", ptr_type_node
);
4699 region_model_manager mgr
;
4700 test_region_model_context ctxt
;
4701 region_model
model (&mgr
);
4703 /* Push stack frame for "parent_fn". */
4704 const region
*parent_frame_reg
4705 = model
.push_frame (DECL_STRUCT_FUNCTION (parent_fndecl
),
4707 ASSERT_EQ (model
.get_current_frame (), parent_frame_reg
);
4708 ASSERT_TRUE (model
.region_exists_p (parent_frame_reg
));
4709 const region
*a_in_parent_reg
= model
.get_lvalue (a
, &ctxt
);
4710 model
.set_value (a_in_parent_reg
,
4711 model
.get_rvalue (int_42
, &ctxt
),
4713 ASSERT_EQ (a_in_parent_reg
->maybe_get_frame_region (), parent_frame_reg
);
4715 model
.add_constraint (b
, LT_EXPR
, int_10
, &ctxt
);
4716 ASSERT_EQ (model
.eval_condition (b
, LT_EXPR
, int_10
, &ctxt
),
4717 tristate (tristate::TS_TRUE
));
4719 /* Push stack frame for "child_fn". */
4720 const region
*child_frame_reg
4721 = model
.push_frame (DECL_STRUCT_FUNCTION (child_fndecl
), NULL
, &ctxt
);
4722 ASSERT_EQ (model
.get_current_frame (), child_frame_reg
);
4723 ASSERT_TRUE (model
.region_exists_p (child_frame_reg
));
4724 const region
*x_in_child_reg
= model
.get_lvalue (x
, &ctxt
);
4725 model
.set_value (x_in_child_reg
,
4726 model
.get_rvalue (int_0
, &ctxt
),
4728 ASSERT_EQ (x_in_child_reg
->maybe_get_frame_region (), child_frame_reg
);
4730 model
.add_constraint (y
, NE_EXPR
, int_5
, &ctxt
);
4731 ASSERT_EQ (model
.eval_condition (y
, NE_EXPR
, int_5
, &ctxt
),
4732 tristate (tristate::TS_TRUE
));
4734 /* Point a global pointer at a local in the child frame: p = &x. */
4735 const region
*p_in_globals_reg
= model
.get_lvalue (p
, &ctxt
);
4736 model
.set_value (p_in_globals_reg
,
4737 mgr
.get_ptr_svalue (ptr_type_node
, x_in_child_reg
),
4739 ASSERT_EQ (p_in_globals_reg
->maybe_get_frame_region (), NULL
);
4741 /* Point another global pointer at p: q = &p. */
4742 const region
*q_in_globals_reg
= model
.get_lvalue (q
, &ctxt
);
4743 model
.set_value (q_in_globals_reg
,
4744 mgr
.get_ptr_svalue (ptr_type_node
, p_in_globals_reg
),
4747 /* Test region::descendent_of_p. */
4748 ASSERT_TRUE (child_frame_reg
->descendent_of_p (child_frame_reg
));
4749 ASSERT_TRUE (x_in_child_reg
->descendent_of_p (child_frame_reg
));
4750 ASSERT_FALSE (a_in_parent_reg
->descendent_of_p (child_frame_reg
));
4752 /* Pop the "child_fn" frame from the stack. */
4753 model
.pop_frame (NULL
, NULL
, &ctxt
);
4754 ASSERT_FALSE (model
.region_exists_p (child_frame_reg
));
4755 ASSERT_TRUE (model
.region_exists_p (parent_frame_reg
));
4757 /* Verify that p (which was pointing at the local "x" in the popped
4758 frame) has been poisoned. */
4759 const svalue
*new_p_sval
= model
.get_rvalue (p
, NULL
);
4760 ASSERT_EQ (new_p_sval
->get_kind (), SK_POISONED
);
4761 ASSERT_EQ (new_p_sval
->dyn_cast_poisoned_svalue ()->get_poison_kind (),
4762 POISON_KIND_POPPED_STACK
);
4764 /* Verify that q still points to p, in spite of the region
4766 const svalue
*new_q_sval
= model
.get_rvalue (q
, &ctxt
);
4767 ASSERT_EQ (new_q_sval
->get_kind (), SK_REGION
);
4768 ASSERT_EQ (new_q_sval
->maybe_get_region (),
4769 model
.get_lvalue (p
, &ctxt
));
4771 /* Verify that top of stack has been updated. */
4772 ASSERT_EQ (model
.get_current_frame (), parent_frame_reg
);
4774 /* Verify locals in parent frame. */
4775 /* Verify "a" still has its value. */
4776 const svalue
*new_a_sval
= model
.get_rvalue (a
, &ctxt
);
4777 ASSERT_EQ (new_a_sval
->get_kind (), SK_CONSTANT
);
4778 ASSERT_EQ (new_a_sval
->dyn_cast_constant_svalue ()->get_constant (),
4780 /* Verify "b" still has its constraint. */
4781 ASSERT_EQ (model
.eval_condition (b
, LT_EXPR
, int_10
, &ctxt
),
4782 tristate (tristate::TS_TRUE
));
4785 /* Verify that get_representative_path_var works as expected, that
4786 we can map from regions to parms and back within a recursive call
4790 test_get_representative_path_var ()
4792 auto_vec
<tree
> param_types
;
4793 tree fndecl
= make_fndecl (integer_type_node
,
4796 allocate_struct_function (fndecl
, true);
4799 tree n
= build_decl (UNKNOWN_LOCATION
, PARM_DECL
,
4800 get_identifier ("n"),
4803 region_model_manager mgr
;
4804 test_region_model_context ctxt
;
4805 region_model
model (&mgr
);
4807 /* Push 5 stack frames for "factorial", each with a param */
4808 auto_vec
<const region
*> parm_regs
;
4809 auto_vec
<const svalue
*> parm_svals
;
4810 for (int depth
= 0; depth
< 5; depth
++)
4812 const region
*frame_n_reg
4813 = model
.push_frame (DECL_STRUCT_FUNCTION (fndecl
), NULL
, &ctxt
);
4814 const region
*parm_n_reg
= model
.get_lvalue (path_var (n
, depth
), &ctxt
);
4815 parm_regs
.safe_push (parm_n_reg
);
4817 ASSERT_EQ (parm_n_reg
->get_parent_region (), frame_n_reg
);
4818 const svalue
*sval_n
= mgr
.get_or_create_initial_value (parm_n_reg
);
4819 parm_svals
.safe_push (sval_n
);
4822 /* Verify that we can recognize that the regions are the parms,
4824 for (int depth
= 0; depth
< 5; depth
++)
4828 ASSERT_EQ (model
.get_representative_path_var (parm_regs
[depth
],
4830 path_var (n
, depth
+ 1));
4832 /* ...and that we can lookup lvalues for locals for all frames,
4833 not just the top. */
4834 ASSERT_EQ (model
.get_lvalue (path_var (n
, depth
), NULL
),
4836 /* ...and that we can locate the svalues. */
4839 ASSERT_EQ (model
.get_representative_path_var (parm_svals
[depth
],
4841 path_var (n
, depth
+ 1));
4846 /* Ensure that region_model::operator== works as expected. */
4851 tree int_42
= build_int_cst (integer_type_node
, 42);
4852 tree int_17
= build_int_cst (integer_type_node
, 17);
4854 /* Verify that "empty" region_model instances are equal to each other. */
4855 region_model_manager mgr
;
4856 region_model
model0 (&mgr
);
4857 region_model
model1 (&mgr
);
4858 ASSERT_EQ (model0
, model1
);
4860 /* Verify that setting state in model1 makes the models non-equal. */
4861 tree x
= build_global_decl ("x", integer_type_node
);
4862 model0
.set_value (x
, int_42
, NULL
);
4863 ASSERT_EQ (model0
.get_rvalue (x
, NULL
)->maybe_get_constant (), int_42
);
4864 ASSERT_NE (model0
, model1
);
4866 /* Verify the copy-ctor. */
4867 region_model
model2 (model0
);
4868 ASSERT_EQ (model0
, model2
);
4869 ASSERT_EQ (model2
.get_rvalue (x
, NULL
)->maybe_get_constant (), int_42
);
4870 ASSERT_NE (model1
, model2
);
4872 /* Verify that models obtained from copy-ctor are independently editable
4873 w/o affecting the original model. */
4874 model2
.set_value (x
, int_17
, NULL
);
4875 ASSERT_NE (model0
, model2
);
4876 ASSERT_EQ (model2
.get_rvalue (x
, NULL
)->maybe_get_constant (), int_17
);
4877 ASSERT_EQ (model0
.get_rvalue (x
, NULL
)->maybe_get_constant (), int_42
);
4880 /* Verify that region models for
4887 test_canonicalization_2 ()
4889 tree int_42
= build_int_cst (integer_type_node
, 42);
4890 tree int_113
= build_int_cst (integer_type_node
, 113);
4891 tree x
= build_global_decl ("x", integer_type_node
);
4892 tree y
= build_global_decl ("y", integer_type_node
);
4894 region_model_manager mgr
;
4895 region_model
model0 (&mgr
);
4896 model0
.set_value (model0
.get_lvalue (x
, NULL
),
4897 model0
.get_rvalue (int_42
, NULL
),
4899 model0
.set_value (model0
.get_lvalue (y
, NULL
),
4900 model0
.get_rvalue (int_113
, NULL
),
4903 region_model
model1 (&mgr
);
4904 model1
.set_value (model1
.get_lvalue (y
, NULL
),
4905 model1
.get_rvalue (int_113
, NULL
),
4907 model1
.set_value (model1
.get_lvalue (x
, NULL
),
4908 model1
.get_rvalue (int_42
, NULL
),
4911 ASSERT_EQ (model0
, model1
);
4914 /* Verify that constraints for
4918 are equal after canonicalization. */
4921 test_canonicalization_3 ()
4923 tree int_3
= build_int_cst (integer_type_node
, 3);
4924 tree int_42
= build_int_cst (integer_type_node
, 42);
4925 tree x
= build_global_decl ("x", integer_type_node
);
4926 tree y
= build_global_decl ("y", integer_type_node
);
4928 region_model_manager mgr
;
4929 region_model
model0 (&mgr
);
4930 model0
.add_constraint (x
, GT_EXPR
, int_3
, NULL
);
4931 model0
.add_constraint (y
, GT_EXPR
, int_42
, NULL
);
4933 region_model
model1 (&mgr
);
4934 model1
.add_constraint (y
, GT_EXPR
, int_42
, NULL
);
4935 model1
.add_constraint (x
, GT_EXPR
, int_3
, NULL
);
4937 model0
.canonicalize ();
4938 model1
.canonicalize ();
4939 ASSERT_EQ (model0
, model1
);
4942 /* Verify that we can canonicalize a model containing NaN and other real
4946 test_canonicalization_4 ()
4948 auto_vec
<tree
> csts
;
4949 append_interesting_constants (&csts
);
4951 region_model_manager mgr
;
4952 region_model
model (&mgr
);
4954 for (tree cst
: csts
)
4955 model
.get_rvalue (cst
, NULL
);
4957 model
.canonicalize ();
4960 /* Assert that if we have two region_model instances
4961 with values VAL_A and VAL_B for EXPR that they are
4962 mergable. Write the merged model to *OUT_MERGED_MODEL,
4963 and the merged svalue ptr to *OUT_MERGED_SVALUE.
4964 If VAL_A or VAL_B are NULL_TREE, don't populate EXPR
4965 for that region_model. */
4968 assert_region_models_merge (tree expr
, tree val_a
, tree val_b
,
4969 region_model
*out_merged_model
,
4970 const svalue
**out_merged_svalue
)
4972 program_point
point (program_point::origin ());
4973 test_region_model_context ctxt
;
4974 region_model_manager
*mgr
= out_merged_model
->get_manager ();
4975 region_model
model0 (mgr
);
4976 region_model
model1 (mgr
);
4978 model0
.set_value (model0
.get_lvalue (expr
, &ctxt
),
4979 model0
.get_rvalue (val_a
, &ctxt
),
4982 model1
.set_value (model1
.get_lvalue (expr
, &ctxt
),
4983 model1
.get_rvalue (val_b
, &ctxt
),
4986 /* They should be mergeable. */
4987 ASSERT_TRUE (model0
.can_merge_with_p (model1
, point
, out_merged_model
));
4988 *out_merged_svalue
= out_merged_model
->get_rvalue (expr
, &ctxt
);
4991 /* Verify that we can merge region_model instances. */
4994 test_state_merging ()
4996 tree int_42
= build_int_cst (integer_type_node
, 42);
4997 tree int_113
= build_int_cst (integer_type_node
, 113);
4998 tree x
= build_global_decl ("x", integer_type_node
);
4999 tree y
= build_global_decl ("y", integer_type_node
);
5000 tree z
= build_global_decl ("z", integer_type_node
);
5001 tree p
= build_global_decl ("p", ptr_type_node
);
5003 tree addr_of_y
= build1 (ADDR_EXPR
, ptr_type_node
, y
);
5004 tree addr_of_z
= build1 (ADDR_EXPR
, ptr_type_node
, z
);
5006 auto_vec
<tree
> param_types
;
5007 tree test_fndecl
= make_fndecl (integer_type_node
, "test_fn", param_types
);
5008 allocate_struct_function (test_fndecl
, true);
5011 tree a
= build_decl (UNKNOWN_LOCATION
, PARM_DECL
,
5012 get_identifier ("a"),
5014 tree addr_of_a
= build1 (ADDR_EXPR
, ptr_type_node
, a
);
5016 /* Param "q", a pointer. */
5017 tree q
= build_decl (UNKNOWN_LOCATION
, PARM_DECL
,
5018 get_identifier ("q"),
5021 program_point
point (program_point::origin ());
5022 region_model_manager mgr
;
5025 region_model
model0 (&mgr
);
5026 region_model
model1 (&mgr
);
5027 region_model
merged (&mgr
);
5028 /* Verify empty models can be merged. */
5029 ASSERT_TRUE (model0
.can_merge_with_p (model1
, point
, &merged
));
5030 ASSERT_EQ (model0
, merged
);
5033 /* Verify that we can merge two contradictory constraints on the
5034 value for a global. */
5035 /* TODO: verify that the merged model doesn't have a value for
5038 region_model
model0 (&mgr
);
5039 region_model
model1 (&mgr
);
5040 region_model
merged (&mgr
);
5041 test_region_model_context ctxt
;
5042 model0
.add_constraint (x
, EQ_EXPR
, int_42
, &ctxt
);
5043 model1
.add_constraint (x
, EQ_EXPR
, int_113
, &ctxt
);
5044 ASSERT_TRUE (model0
.can_merge_with_p (model1
, point
, &merged
));
5045 ASSERT_NE (model0
, merged
);
5046 ASSERT_NE (model1
, merged
);
5049 /* Verify handling of a PARM_DECL. */
5051 test_region_model_context ctxt
;
5052 region_model
model0 (&mgr
);
5053 region_model
model1 (&mgr
);
5054 ASSERT_EQ (model0
.get_stack_depth (), 0);
5055 model0
.push_frame (DECL_STRUCT_FUNCTION (test_fndecl
), NULL
, &ctxt
);
5056 ASSERT_EQ (model0
.get_stack_depth (), 1);
5057 model1
.push_frame (DECL_STRUCT_FUNCTION (test_fndecl
), NULL
, &ctxt
);
5059 placeholder_svalue
test_sval (integer_type_node
, "test sval");
5060 model0
.set_value (model0
.get_lvalue (a
, &ctxt
), &test_sval
, &ctxt
);
5061 model1
.set_value (model1
.get_lvalue (a
, &ctxt
), &test_sval
, &ctxt
);
5062 ASSERT_EQ (model0
, model1
);
5064 /* They should be mergeable, and the result should be the same. */
5065 region_model
merged (&mgr
);
5066 ASSERT_TRUE (model0
.can_merge_with_p (model1
, point
, &merged
));
5067 ASSERT_EQ (model0
, merged
);
5068 /* In particular, "a" should have the placeholder value. */
5069 ASSERT_EQ (merged
.get_rvalue (a
, &ctxt
), &test_sval
);
5072 /* Verify handling of a global. */
5074 test_region_model_context ctxt
;
5075 region_model
model0 (&mgr
);
5076 region_model
model1 (&mgr
);
5078 placeholder_svalue
test_sval (integer_type_node
, "test sval");
5079 model0
.set_value (model0
.get_lvalue (x
, &ctxt
), &test_sval
, &ctxt
);
5080 model1
.set_value (model1
.get_lvalue (x
, &ctxt
), &test_sval
, &ctxt
);
5081 ASSERT_EQ (model0
, model1
);
5083 /* They should be mergeable, and the result should be the same. */
5084 region_model
merged (&mgr
);
5085 ASSERT_TRUE (model0
.can_merge_with_p (model1
, point
, &merged
));
5086 ASSERT_EQ (model0
, merged
);
5087 /* In particular, "x" should have the placeholder value. */
5088 ASSERT_EQ (merged
.get_rvalue (x
, &ctxt
), &test_sval
);
5091 /* Use global-handling to verify various combinations of values. */
5093 /* Two equal constant values. */
5095 region_model
merged (&mgr
);
5096 const svalue
*merged_x_sval
;
5097 assert_region_models_merge (x
, int_42
, int_42
, &merged
, &merged_x_sval
);
5099 /* In particular, there should be a constant value for "x". */
5100 ASSERT_EQ (merged_x_sval
->get_kind (), SK_CONSTANT
);
5101 ASSERT_EQ (merged_x_sval
->dyn_cast_constant_svalue ()->get_constant (),
5105 /* Two non-equal constant values. */
5107 region_model
merged (&mgr
);
5108 const svalue
*merged_x_sval
;
5109 assert_region_models_merge (x
, int_42
, int_113
, &merged
, &merged_x_sval
);
5111 /* In particular, there should be a "widening" value for "x". */
5112 ASSERT_EQ (merged_x_sval
->get_kind (), SK_WIDENING
);
5115 /* Initial and constant. */
5117 region_model
merged (&mgr
);
5118 const svalue
*merged_x_sval
;
5119 assert_region_models_merge (x
, NULL_TREE
, int_113
, &merged
, &merged_x_sval
);
5121 /* In particular, there should be an unknown value for "x". */
5122 ASSERT_EQ (merged_x_sval
->get_kind (), SK_UNKNOWN
);
5125 /* Constant and initial. */
5127 region_model
merged (&mgr
);
5128 const svalue
*merged_x_sval
;
5129 assert_region_models_merge (x
, int_42
, NULL_TREE
, &merged
, &merged_x_sval
);
5131 /* In particular, there should be an unknown value for "x". */
5132 ASSERT_EQ (merged_x_sval
->get_kind (), SK_UNKNOWN
);
5135 /* Unknown and constant. */
5138 /* Pointers: NULL and NULL. */
5141 /* Pointers: NULL and non-NULL. */
5144 /* Pointers: non-NULL and non-NULL: ptr to a local. */
5146 region_model
model0 (&mgr
);
5147 model0
.push_frame (DECL_STRUCT_FUNCTION (test_fndecl
), NULL
, NULL
);
5148 model0
.set_value (model0
.get_lvalue (p
, NULL
),
5149 model0
.get_rvalue (addr_of_a
, NULL
), NULL
);
5151 region_model
model1 (model0
);
5152 ASSERT_EQ (model0
, model1
);
5154 /* They should be mergeable, and the result should be the same. */
5155 region_model
merged (&mgr
);
5156 ASSERT_TRUE (model0
.can_merge_with_p (model1
, point
, &merged
));
5157 ASSERT_EQ (model0
, merged
);
5160 /* Pointers: non-NULL and non-NULL: ptr to a global. */
5162 region_model
merged (&mgr
);
5163 /* p == &y in both input models. */
5164 const svalue
*merged_p_sval
;
5165 assert_region_models_merge (p
, addr_of_y
, addr_of_y
, &merged
,
5168 /* We should get p == &y in the merged model. */
5169 ASSERT_EQ (merged_p_sval
->get_kind (), SK_REGION
);
5170 const region_svalue
*merged_p_ptr
5171 = merged_p_sval
->dyn_cast_region_svalue ();
5172 const region
*merged_p_star_reg
= merged_p_ptr
->get_pointee ();
5173 ASSERT_EQ (merged_p_star_reg
, merged
.get_lvalue (y
, NULL
));
5176 /* Pointers: non-NULL ptrs to different globals: should be unknown. */
5178 region_model
merged (&mgr
);
5179 /* x == &y vs x == &z in the input models; these are actually casts
5180 of the ptrs to "int". */
5181 const svalue
*merged_x_sval
;
5183 assert_region_models_merge (x
, addr_of_y
, addr_of_z
, &merged
,
5186 /* We should get x == unknown in the merged model. */
5187 ASSERT_EQ (merged_x_sval
->get_kind (), SK_UNKNOWN
);
5190 /* Pointers: non-NULL and non-NULL: ptr to a heap region. */
5192 test_region_model_context ctxt
;
5193 region_model
model0 (&mgr
);
5194 tree size
= build_int_cst (size_type_node
, 1024);
5195 const svalue
*size_sval
= mgr
.get_or_create_constant_svalue (size
);
5196 const region
*new_reg
5197 = model0
.create_region_for_heap_alloc (size_sval
, &ctxt
);
5198 const svalue
*ptr_sval
= mgr
.get_ptr_svalue (ptr_type_node
, new_reg
);
5199 model0
.set_value (model0
.get_lvalue (p
, &ctxt
),
5202 region_model
model1 (model0
);
5204 ASSERT_EQ (model0
, model1
);
5206 region_model
merged (&mgr
);
5207 ASSERT_TRUE (model0
.can_merge_with_p (model1
, point
, &merged
));
5209 /* The merged model ought to be identical. */
5210 ASSERT_EQ (model0
, merged
);
5213 /* Two regions sharing the same placeholder svalue should continue sharing
5214 it after self-merger. */
5216 test_region_model_context ctxt
;
5217 region_model
model0 (&mgr
);
5218 placeholder_svalue
placeholder_sval (integer_type_node
, "test");
5219 model0
.set_value (model0
.get_lvalue (x
, &ctxt
),
5220 &placeholder_sval
, &ctxt
);
5221 model0
.set_value (model0
.get_lvalue (y
, &ctxt
), &placeholder_sval
, &ctxt
);
5222 region_model
model1 (model0
);
5224 /* They should be mergeable, and the result should be the same. */
5225 region_model
merged (&mgr
);
5226 ASSERT_TRUE (model0
.can_merge_with_p (model1
, point
, &merged
));
5227 ASSERT_EQ (model0
, merged
);
5229 /* In particular, we should have x == y. */
5230 ASSERT_EQ (merged
.eval_condition (x
, EQ_EXPR
, y
, &ctxt
),
5231 tristate (tristate::TS_TRUE
));
5235 region_model
model0 (&mgr
);
5236 region_model
model1 (&mgr
);
5237 test_region_model_context ctxt
;
5238 model0
.add_constraint (x
, EQ_EXPR
, int_42
, &ctxt
);
5239 model1
.add_constraint (x
, NE_EXPR
, int_42
, &ctxt
);
5240 region_model
merged (&mgr
);
5241 ASSERT_TRUE (model0
.can_merge_with_p (model1
, point
, &merged
));
5245 region_model
model0 (&mgr
);
5246 region_model
model1 (&mgr
);
5247 test_region_model_context ctxt
;
5248 model0
.add_constraint (x
, EQ_EXPR
, int_42
, &ctxt
);
5249 model1
.add_constraint (x
, NE_EXPR
, int_42
, &ctxt
);
5250 model1
.add_constraint (x
, EQ_EXPR
, int_113
, &ctxt
);
5251 region_model
merged (&mgr
);
5252 ASSERT_TRUE (model0
.can_merge_with_p (model1
, point
, &merged
));
5255 // TODO: what can't we merge? need at least one such test
5257 /* TODO: various things
5260 - every combination, but in particular
5266 test_region_model_context ctxt
;
5267 region_model
model0 (&mgr
);
5269 const region
*x_reg
= model0
.get_lvalue (x
, &ctxt
);
5270 const region
*x_as_ptr
= mgr
.get_cast_region (x_reg
, ptr_type_node
);
5271 model0
.set_value (x_as_ptr
, model0
.get_rvalue (addr_of_y
, &ctxt
), &ctxt
);
5273 region_model
model1 (model0
);
5274 ASSERT_EQ (model1
, model0
);
5276 /* They should be mergeable, and the result should be the same. */
5277 region_model
merged (&mgr
);
5278 ASSERT_TRUE (model0
.can_merge_with_p (model1
, point
, &merged
));
5281 /* Verify that we can merge a model in which a local in an older stack
5282 frame points to a local in a more recent stack frame. */
5284 region_model
model0 (&mgr
);
5285 model0
.push_frame (DECL_STRUCT_FUNCTION (test_fndecl
), NULL
, NULL
);
5286 const region
*q_in_first_frame
= model0
.get_lvalue (q
, NULL
);
5288 /* Push a second frame. */
5289 const region
*reg_2nd_frame
5290 = model0
.push_frame (DECL_STRUCT_FUNCTION (test_fndecl
), NULL
, NULL
);
5292 /* Have a pointer in the older frame point to a local in the
5293 more recent frame. */
5294 const svalue
*sval_ptr
= model0
.get_rvalue (addr_of_a
, NULL
);
5295 model0
.set_value (q_in_first_frame
, sval_ptr
, NULL
);
5297 /* Verify that it's pointing at the newer frame. */
5298 const region
*reg_pointee
= sval_ptr
->maybe_get_region ();
5299 ASSERT_EQ (reg_pointee
->get_parent_region (), reg_2nd_frame
);
5301 model0
.canonicalize ();
5303 region_model
model1 (model0
);
5304 ASSERT_EQ (model0
, model1
);
5306 /* They should be mergeable, and the result should be the same
5307 (after canonicalization, at least). */
5308 region_model
merged (&mgr
);
5309 ASSERT_TRUE (model0
.can_merge_with_p (model1
, point
, &merged
));
5310 merged
.canonicalize ();
5311 ASSERT_EQ (model0
, merged
);
5314 /* Verify that we can merge a model in which a local points to a global. */
5316 region_model
model0 (&mgr
);
5317 model0
.push_frame (DECL_STRUCT_FUNCTION (test_fndecl
), NULL
, NULL
);
5318 model0
.set_value (model0
.get_lvalue (q
, NULL
),
5319 model0
.get_rvalue (addr_of_y
, NULL
), NULL
);
5321 region_model
model1 (model0
);
5322 ASSERT_EQ (model0
, model1
);
5324 /* They should be mergeable, and the result should be the same
5325 (after canonicalization, at least). */
5326 region_model
merged (&mgr
);
5327 ASSERT_TRUE (model0
.can_merge_with_p (model1
, point
, &merged
));
5328 ASSERT_EQ (model0
, merged
);
5332 /* Verify that constraints are correctly merged when merging region_model
5336 test_constraint_merging ()
5338 tree int_0
= build_int_cst (integer_type_node
, 0);
5339 tree int_5
= build_int_cst (integer_type_node
, 5);
5340 tree x
= build_global_decl ("x", integer_type_node
);
5341 tree y
= build_global_decl ("y", integer_type_node
);
5342 tree z
= build_global_decl ("z", integer_type_node
);
5343 tree n
= build_global_decl ("n", integer_type_node
);
5345 region_model_manager mgr
;
5346 test_region_model_context ctxt
;
5348 /* model0: 0 <= (x == y) < n. */
5349 region_model
model0 (&mgr
);
5350 model0
.add_constraint (x
, EQ_EXPR
, y
, &ctxt
);
5351 model0
.add_constraint (x
, GE_EXPR
, int_0
, NULL
);
5352 model0
.add_constraint (x
, LT_EXPR
, n
, NULL
);
5354 /* model1: z != 5 && (0 <= x < n). */
5355 region_model
model1 (&mgr
);
5356 model1
.add_constraint (z
, NE_EXPR
, int_5
, NULL
);
5357 model1
.add_constraint (x
, GE_EXPR
, int_0
, NULL
);
5358 model1
.add_constraint (x
, LT_EXPR
, n
, NULL
);
5360 /* They should be mergeable; the merged constraints should
5361 be: (0 <= x < n). */
5362 program_point
point (program_point::origin ());
5363 region_model
merged (&mgr
);
5364 ASSERT_TRUE (model0
.can_merge_with_p (model1
, point
, &merged
));
5366 ASSERT_EQ (merged
.eval_condition (x
, GE_EXPR
, int_0
, &ctxt
),
5367 tristate (tristate::TS_TRUE
));
5368 ASSERT_EQ (merged
.eval_condition (x
, LT_EXPR
, n
, &ctxt
),
5369 tristate (tristate::TS_TRUE
));
5371 ASSERT_EQ (merged
.eval_condition (z
, NE_EXPR
, int_5
, &ctxt
),
5372 tristate (tristate::TS_UNKNOWN
));
5373 ASSERT_EQ (merged
.eval_condition (x
, LT_EXPR
, y
, &ctxt
),
5374 tristate (tristate::TS_UNKNOWN
));
5377 /* Verify that widening_svalue::eval_condition_without_cm works as
5381 test_widening_constraints ()
5383 program_point
point (program_point::origin ());
5384 tree int_0
= build_int_cst (integer_type_node
, 0);
5385 tree int_m1
= build_int_cst (integer_type_node
, -1);
5386 tree int_1
= build_int_cst (integer_type_node
, 1);
5387 tree int_256
= build_int_cst (integer_type_node
, 256);
5388 region_model_manager mgr
;
5389 test_region_model_context ctxt
;
5390 const svalue
*int_0_sval
= mgr
.get_or_create_constant_svalue (int_0
);
5391 const svalue
*int_1_sval
= mgr
.get_or_create_constant_svalue (int_1
);
5392 const svalue
*w_zero_then_one_sval
5393 = mgr
.get_or_create_widening_svalue (integer_type_node
, point
,
5394 int_0_sval
, int_1_sval
);
5395 const widening_svalue
*w_zero_then_one
5396 = w_zero_then_one_sval
->dyn_cast_widening_svalue ();
5397 ASSERT_EQ (w_zero_then_one
->get_direction (),
5398 widening_svalue::DIR_ASCENDING
);
5399 ASSERT_EQ (w_zero_then_one
->eval_condition_without_cm (LT_EXPR
, int_m1
),
5400 tristate::TS_FALSE
);
5401 ASSERT_EQ (w_zero_then_one
->eval_condition_without_cm (LT_EXPR
, int_0
),
5402 tristate::TS_FALSE
);
5403 ASSERT_EQ (w_zero_then_one
->eval_condition_without_cm (LT_EXPR
, int_1
),
5404 tristate::TS_UNKNOWN
);
5405 ASSERT_EQ (w_zero_then_one
->eval_condition_without_cm (LT_EXPR
, int_256
),
5406 tristate::TS_UNKNOWN
);
5408 ASSERT_EQ (w_zero_then_one
->eval_condition_without_cm (LE_EXPR
, int_m1
),
5409 tristate::TS_FALSE
);
5410 ASSERT_EQ (w_zero_then_one
->eval_condition_without_cm (LE_EXPR
, int_0
),
5411 tristate::TS_UNKNOWN
);
5412 ASSERT_EQ (w_zero_then_one
->eval_condition_without_cm (LE_EXPR
, int_1
),
5413 tristate::TS_UNKNOWN
);
5414 ASSERT_EQ (w_zero_then_one
->eval_condition_without_cm (LE_EXPR
, int_256
),
5415 tristate::TS_UNKNOWN
);
5417 ASSERT_EQ (w_zero_then_one
->eval_condition_without_cm (GT_EXPR
, int_m1
),
5419 ASSERT_EQ (w_zero_then_one
->eval_condition_without_cm (GT_EXPR
, int_0
),
5420 tristate::TS_UNKNOWN
);
5421 ASSERT_EQ (w_zero_then_one
->eval_condition_without_cm (GT_EXPR
, int_1
),
5422 tristate::TS_UNKNOWN
);
5423 ASSERT_EQ (w_zero_then_one
->eval_condition_without_cm (GT_EXPR
, int_256
),
5424 tristate::TS_UNKNOWN
);
5426 ASSERT_EQ (w_zero_then_one
->eval_condition_without_cm (GE_EXPR
, int_m1
),
5428 ASSERT_EQ (w_zero_then_one
->eval_condition_without_cm (GE_EXPR
, int_0
),
5430 ASSERT_EQ (w_zero_then_one
->eval_condition_without_cm (GE_EXPR
, int_1
),
5431 tristate::TS_UNKNOWN
);
5432 ASSERT_EQ (w_zero_then_one
->eval_condition_without_cm (GE_EXPR
, int_256
),
5433 tristate::TS_UNKNOWN
);
5435 ASSERT_EQ (w_zero_then_one
->eval_condition_without_cm (EQ_EXPR
, int_m1
),
5436 tristate::TS_FALSE
);
5437 ASSERT_EQ (w_zero_then_one
->eval_condition_without_cm (EQ_EXPR
, int_0
),
5438 tristate::TS_UNKNOWN
);
5439 ASSERT_EQ (w_zero_then_one
->eval_condition_without_cm (EQ_EXPR
, int_1
),
5440 tristate::TS_UNKNOWN
);
5441 ASSERT_EQ (w_zero_then_one
->eval_condition_without_cm (EQ_EXPR
, int_256
),
5442 tristate::TS_UNKNOWN
);
5444 ASSERT_EQ (w_zero_then_one
->eval_condition_without_cm (NE_EXPR
, int_m1
),
5446 ASSERT_EQ (w_zero_then_one
->eval_condition_without_cm (NE_EXPR
, int_0
),
5447 tristate::TS_UNKNOWN
);
5448 ASSERT_EQ (w_zero_then_one
->eval_condition_without_cm (NE_EXPR
, int_1
),
5449 tristate::TS_UNKNOWN
);
5450 ASSERT_EQ (w_zero_then_one
->eval_condition_without_cm (NE_EXPR
, int_256
),
5451 tristate::TS_UNKNOWN
);
5454 /* Verify merging constraints for states simulating successive iterations
5457 for (i = 0; i < 256; i++)
5464 i_11 = PHI <i_15(2), i_23(3)>
5474 and thus these ops (and resultant states):
5477 add_constraint (i_11 <= 255) [for the true edge]
5478 {i_11: 0} [constraint was a no-op]
5482 {i_11: WIDENED (at phi, 0, 1)}
5483 add_constraint (i_11 <= 255) [for the true edge]
5484 {i_11: WIDENED (at phi, 0, 1); WIDENED <= 255}
5486 {i_23: (WIDENED (at phi, 0, 1) + 1); WIDENED <= 255}
5487 i_11 = PHI(); merge with state at phi above
5488 {i_11: WIDENED (at phi, 0, 1); WIDENED <= 256}
5489 [changing meaning of "WIDENED" here]
5491 T: {i_11: WIDENED (at phi, 0, 1); WIDENED <= 255}; cache hit
5498 program_point
point (program_point::origin ());
5500 tree int_0
= build_int_cst (integer_type_node
, 0);
5501 tree int_1
= build_int_cst (integer_type_node
, 1);
5502 tree int_256
= build_int_cst (integer_type_node
, 256);
5503 tree int_257
= build_int_cst (integer_type_node
, 257);
5504 tree i
= build_global_decl ("i", integer_type_node
);
5506 region_model_manager mgr
;
5507 test_region_model_context ctxt
;
5510 region_model
model0 (&mgr
);
5511 model0
.set_value (i
, int_0
, &ctxt
);
5514 region_model
model1 (&mgr
);
5515 model1
.set_value (i
, int_1
, &ctxt
);
5517 /* Should merge "i" to a widened value. */
5518 region_model
model2 (&mgr
);
5519 ASSERT_TRUE (model1
.can_merge_with_p (model0
, point
, &model2
));
5520 const svalue
*merged_i
= model2
.get_rvalue (i
, &ctxt
);
5521 ASSERT_EQ (merged_i
->get_kind (), SK_WIDENING
);
5522 const widening_svalue
*w
= merged_i
->dyn_cast_widening_svalue ();
5523 ASSERT_EQ (w
->get_direction (), widening_svalue::DIR_ASCENDING
);
5525 /* Add constraint: i < 256 */
5526 model2
.add_constraint (i
, LT_EXPR
, int_256
, &ctxt
);
5527 ASSERT_EQ (model2
.eval_condition (i
, LT_EXPR
, int_256
, &ctxt
),
5528 tristate (tristate::TS_TRUE
));
5529 ASSERT_EQ (model2
.eval_condition (i
, GE_EXPR
, int_0
, &ctxt
),
5530 tristate (tristate::TS_TRUE
));
5532 /* Try merging with the initial state. */
5533 region_model
model3 (&mgr
);
5534 ASSERT_TRUE (model2
.can_merge_with_p (model0
, point
, &model3
));
5535 /* Merging the merged value with the initial value should be idempotent,
5536 so that the analysis converges. */
5537 ASSERT_EQ (model3
.get_rvalue (i
, &ctxt
), merged_i
);
5538 /* Merger of 0 and a widening value with constraint < CST
5539 should retain the constraint, even though it was implicit
5541 ASSERT_EQ (model3
.eval_condition (i
, LT_EXPR
, int_256
, &ctxt
),
5542 tristate (tristate::TS_TRUE
));
5543 /* ...and we should have equality: the analysis should have converged. */
5544 ASSERT_EQ (model3
, model2
);
5546 /* "i_23 = i_11 + 1;" */
5547 region_model
model4 (model3
);
5548 ASSERT_EQ (model4
, model2
);
5549 model4
.set_value (i
, build2 (PLUS_EXPR
, integer_type_node
, i
, int_1
), &ctxt
);
5550 const svalue
*plus_one
= model4
.get_rvalue (i
, &ctxt
);
5551 ASSERT_EQ (plus_one
->get_kind (), SK_BINOP
);
5553 /* Try merging with the "i: 1" state. */
5554 region_model
model5 (&mgr
);
5555 ASSERT_TRUE (model4
.can_merge_with_p (model1
, point
, &model5
));
5556 ASSERT_EQ (model5
.get_rvalue (i
, &ctxt
), plus_one
);
5557 ASSERT_EQ (model5
, model4
);
5559 /* "i_11 = PHI();" merge with state at phi above.
5560 For i, we should have a merger of WIDENING with WIDENING + 1,
5561 and this should be WIDENING again. */
5562 region_model
model6 (&mgr
);
5563 ASSERT_TRUE (model5
.can_merge_with_p (model2
, point
, &model6
));
5564 const svalue
*merged_widening
= model6
.get_rvalue (i
, &ctxt
);
5565 ASSERT_EQ (merged_widening
->get_kind (), SK_WIDENING
);
5567 ASSERT_CONDITION_TRUE (model6
, i
, LT_EXPR
, int_257
);
5570 /* Verify that if we mark a pointer to a malloc-ed region as non-NULL,
5571 all cast pointers to that region are also known to be non-NULL. */
5574 test_malloc_constraints ()
5576 region_model_manager mgr
;
5577 region_model
model (&mgr
);
5578 tree p
= build_global_decl ("p", ptr_type_node
);
5579 tree char_star
= build_pointer_type (char_type_node
);
5580 tree q
= build_global_decl ("q", char_star
);
5581 tree null_ptr
= build_int_cst (ptr_type_node
, 0);
5583 const svalue
*size_in_bytes
5584 = mgr
.get_or_create_unknown_svalue (size_type_node
);
5585 const region
*reg
= model
.create_region_for_heap_alloc (size_in_bytes
, NULL
);
5586 const svalue
*sval
= mgr
.get_ptr_svalue (ptr_type_node
, reg
);
5587 model
.set_value (model
.get_lvalue (p
, NULL
), sval
, NULL
);
5588 model
.set_value (q
, p
, NULL
);
5590 ASSERT_CONDITION_UNKNOWN (model
, p
, NE_EXPR
, null_ptr
);
5591 ASSERT_CONDITION_UNKNOWN (model
, p
, EQ_EXPR
, null_ptr
);
5592 ASSERT_CONDITION_UNKNOWN (model
, q
, NE_EXPR
, null_ptr
);
5593 ASSERT_CONDITION_UNKNOWN (model
, q
, EQ_EXPR
, null_ptr
);
5595 model
.add_constraint (p
, NE_EXPR
, null_ptr
, NULL
);
5597 ASSERT_CONDITION_TRUE (model
, p
, NE_EXPR
, null_ptr
);
5598 ASSERT_CONDITION_FALSE (model
, p
, EQ_EXPR
, null_ptr
);
5599 ASSERT_CONDITION_TRUE (model
, q
, NE_EXPR
, null_ptr
);
5600 ASSERT_CONDITION_FALSE (model
, q
, EQ_EXPR
, null_ptr
);
5603 /* Smoketest of getting and setting the value of a variable. */
5609 tree i
= build_global_decl ("i", integer_type_node
);
5611 tree int_17
= build_int_cst (integer_type_node
, 17);
5612 tree int_m3
= build_int_cst (integer_type_node
, -3);
5614 region_model_manager mgr
;
5615 region_model
model (&mgr
);
5617 const region
*i_reg
= model
.get_lvalue (i
, NULL
);
5618 ASSERT_EQ (i_reg
->get_kind (), RK_DECL
);
5620 /* Reading "i" should give a symbolic "initial value". */
5621 const svalue
*sval_init
= model
.get_rvalue (i
, NULL
);
5622 ASSERT_EQ (sval_init
->get_kind (), SK_INITIAL
);
5623 ASSERT_EQ (sval_init
->dyn_cast_initial_svalue ()->get_region (), i_reg
);
5624 /* ..and doing it again should give the same "initial value". */
5625 ASSERT_EQ (model
.get_rvalue (i
, NULL
), sval_init
);
5628 model
.set_value (i
, int_17
, NULL
);
5629 ASSERT_EQ (model
.get_rvalue (i
, NULL
),
5630 model
.get_rvalue (int_17
, NULL
));
5633 model
.set_value (i
, int_m3
, NULL
);
5634 ASSERT_EQ (model
.get_rvalue (i
, NULL
),
5635 model
.get_rvalue (int_m3
, NULL
));
5637 /* Verify get_offset for "i". */
5639 region_offset offset
= i_reg
->get_offset ();
5640 ASSERT_EQ (offset
.get_base_region (), i_reg
);
5641 ASSERT_EQ (offset
.get_bit_offset (), 0);
5648 /* "int arr[10];" */
5649 tree tlen
= size_int (10);
5651 = build_array_type (integer_type_node
, build_index_type (tlen
));
5652 tree arr
= build_global_decl ("arr", arr_type
);
5655 tree i
= build_global_decl ("i", integer_type_node
);
5657 tree int_0
= build_int_cst (integer_type_node
, 0);
5658 tree int_1
= build_int_cst (integer_type_node
, 1);
5660 tree arr_0
= build4 (ARRAY_REF
, integer_type_node
,
5661 arr
, int_0
, NULL_TREE
, NULL_TREE
);
5662 tree arr_1
= build4 (ARRAY_REF
, integer_type_node
,
5663 arr
, int_1
, NULL_TREE
, NULL_TREE
);
5664 tree arr_i
= build4 (ARRAY_REF
, integer_type_node
,
5665 arr
, i
, NULL_TREE
, NULL_TREE
);
5667 tree int_17
= build_int_cst (integer_type_node
, 17);
5668 tree int_42
= build_int_cst (integer_type_node
, 42);
5669 tree int_m3
= build_int_cst (integer_type_node
, -3);
5671 region_model_manager mgr
;
5672 region_model
model (&mgr
);
5673 /* "arr[0] = 17;". */
5674 model
.set_value (arr_0
, int_17
, NULL
);
5675 /* "arr[1] = -3;". */
5676 model
.set_value (arr_1
, int_m3
, NULL
);
5678 ASSERT_EQ (model
.get_rvalue (arr_0
, NULL
), model
.get_rvalue (int_17
, NULL
));
5679 ASSERT_EQ (model
.get_rvalue (arr_1
, NULL
), model
.get_rvalue (int_m3
, NULL
));
5681 /* Overwrite a pre-existing binding: "arr[1] = 42;". */
5682 model
.set_value (arr_1
, int_42
, NULL
);
5683 ASSERT_EQ (model
.get_rvalue (arr_1
, NULL
), model
.get_rvalue (int_42
, NULL
));
5685 /* Verify get_offset for "arr[0]". */
5687 const region
*arr_0_reg
= model
.get_lvalue (arr_0
, NULL
);
5688 region_offset offset
= arr_0_reg
->get_offset ();
5689 ASSERT_EQ (offset
.get_base_region (), model
.get_lvalue (arr
, NULL
));
5690 ASSERT_EQ (offset
.get_bit_offset (), 0);
5693 /* Verify get_offset for "arr[1]". */
5695 const region
*arr_1_reg
= model
.get_lvalue (arr_1
, NULL
);
5696 region_offset offset
= arr_1_reg
->get_offset ();
5697 ASSERT_EQ (offset
.get_base_region (), model
.get_lvalue (arr
, NULL
));
5698 ASSERT_EQ (offset
.get_bit_offset (), INT_TYPE_SIZE
);
5701 /* "arr[i] = i;" - this should remove the earlier bindings. */
5702 model
.set_value (arr_i
, i
, NULL
);
5703 ASSERT_EQ (model
.get_rvalue (arr_i
, NULL
), model
.get_rvalue (i
, NULL
));
5704 ASSERT_EQ (model
.get_rvalue (arr_0
, NULL
)->get_kind (), SK_UNKNOWN
);
5706 /* "arr[0] = 17;" - this should remove the arr[i] binding. */
5707 model
.set_value (arr_0
, int_17
, NULL
);
5708 ASSERT_EQ (model
.get_rvalue (arr_0
, NULL
), model
.get_rvalue (int_17
, NULL
));
5709 ASSERT_EQ (model
.get_rvalue (arr_i
, NULL
)->get_kind (), SK_UNKNOWN
);
5712 /* Smoketest of dereferencing a pointer via MEM_REF. */
5722 tree x
= build_global_decl ("x", integer_type_node
);
5723 tree int_star
= build_pointer_type (integer_type_node
);
5724 tree p
= build_global_decl ("p", int_star
);
5726 tree int_17
= build_int_cst (integer_type_node
, 17);
5727 tree addr_of_x
= build1 (ADDR_EXPR
, int_star
, x
);
5728 tree offset_0
= build_int_cst (integer_type_node
, 0);
5729 tree star_p
= build2 (MEM_REF
, integer_type_node
, p
, offset_0
);
5731 region_model_manager mgr
;
5732 region_model
model (&mgr
);
5735 model
.set_value (x
, int_17
, NULL
);
5738 model
.set_value (p
, addr_of_x
, NULL
);
5740 const svalue
*sval
= model
.get_rvalue (star_p
, NULL
);
5741 ASSERT_EQ (sval
->maybe_get_constant (), int_17
);
5744 /* Test for a POINTER_PLUS_EXPR followed by a MEM_REF.
5745 Analogous to this code:
5746 void test_6 (int a[10])
5748 __analyzer_eval (a[3] == 42); [should be UNKNOWN]
5750 __analyzer_eval (a[3] == 42); [should be TRUE]
5752 from data-model-1.c, which looks like this at the gimple level:
5753 # __analyzer_eval (a[3] == 42); [should be UNKNOWN]
5754 int *_1 = a_10(D) + 12; # POINTER_PLUS_EXPR
5755 int _2 = *_1; # MEM_REF
5756 _Bool _3 = _2 == 42;
5758 __analyzer_eval (_4);
5761 int *_5 = a_10(D) + 12; # POINTER_PLUS_EXPR
5764 # __analyzer_eval (a[3] == 42); [should be TRUE]
5765 int *_6 = a_10(D) + 12; # POINTER_PLUS_EXPR
5766 int _7 = *_6; # MEM_REF
5767 _Bool _8 = _7 == 42;
5769 __analyzer_eval (_9); */
5772 test_POINTER_PLUS_EXPR_then_MEM_REF ()
5774 tree int_star
= build_pointer_type (integer_type_node
);
5775 tree a
= build_global_decl ("a", int_star
);
5776 tree offset_12
= build_int_cst (size_type_node
, 12);
5777 tree pointer_plus_expr
= build2 (POINTER_PLUS_EXPR
, int_star
, a
, offset_12
);
5778 tree offset_0
= build_int_cst (integer_type_node
, 0);
5779 tree mem_ref
= build2 (MEM_REF
, integer_type_node
,
5780 pointer_plus_expr
, offset_0
);
5781 region_model_manager mgr
;
5782 region_model
m (&mgr
);
5784 tree int_42
= build_int_cst (integer_type_node
, 42);
5785 m
.set_value (mem_ref
, int_42
, NULL
);
5786 ASSERT_EQ (m
.get_rvalue (mem_ref
, NULL
)->maybe_get_constant (), int_42
);
5789 /* Verify that malloc works. */
5794 tree int_star
= build_pointer_type (integer_type_node
);
5795 tree p
= build_global_decl ("p", int_star
);
5796 tree n
= build_global_decl ("n", integer_type_node
);
5797 tree n_times_4
= build2 (MULT_EXPR
, size_type_node
,
5798 n
, build_int_cst (size_type_node
, 4));
5800 region_model_manager mgr
;
5801 test_region_model_context ctxt
;
5802 region_model
model (&mgr
);
5804 /* "p = malloc (n * 4);". */
5805 const svalue
*size_sval
= model
.get_rvalue (n_times_4
, &ctxt
);
5806 const region
*reg
= model
.create_region_for_heap_alloc (size_sval
, &ctxt
);
5807 const svalue
*ptr
= mgr
.get_ptr_svalue (int_star
, reg
);
5808 model
.set_value (model
.get_lvalue (p
, &ctxt
), ptr
, &ctxt
);
5809 ASSERT_EQ (model
.get_capacity (reg
), size_sval
);
5812 /* Verify that alloca works. */
5817 auto_vec
<tree
> param_types
;
5818 tree fndecl
= make_fndecl (integer_type_node
,
5821 allocate_struct_function (fndecl
, true);
5824 tree int_star
= build_pointer_type (integer_type_node
);
5825 tree p
= build_global_decl ("p", int_star
);
5826 tree n
= build_global_decl ("n", integer_type_node
);
5827 tree n_times_4
= build2 (MULT_EXPR
, size_type_node
,
5828 n
, build_int_cst (size_type_node
, 4));
5830 region_model_manager mgr
;
5831 test_region_model_context ctxt
;
5832 region_model
model (&mgr
);
5834 /* Push stack frame. */
5835 const region
*frame_reg
5836 = model
.push_frame (DECL_STRUCT_FUNCTION (fndecl
),
5838 /* "p = alloca (n * 4);". */
5839 const svalue
*size_sval
= model
.get_rvalue (n_times_4
, &ctxt
);
5840 const region
*reg
= model
.create_region_for_alloca (size_sval
, &ctxt
);
5841 ASSERT_EQ (reg
->get_parent_region (), frame_reg
);
5842 const svalue
*ptr
= mgr
.get_ptr_svalue (int_star
, reg
);
5843 model
.set_value (model
.get_lvalue (p
, &ctxt
), ptr
, &ctxt
);
5844 ASSERT_EQ (model
.get_capacity (reg
), size_sval
);
5846 /* Verify that the pointers to the alloca region are replaced by
5847 poisoned values when the frame is popped. */
5848 model
.pop_frame (NULL
, NULL
, &ctxt
);
5849 ASSERT_EQ (model
.get_rvalue (p
, NULL
)->get_kind (), SK_POISONED
);
5852 /* Verify that svalue::involves_p works. */
5857 region_model_manager mgr
;
5858 tree int_star
= build_pointer_type (integer_type_node
);
5859 tree p
= build_global_decl ("p", int_star
);
5860 tree q
= build_global_decl ("q", int_star
);
5862 test_region_model_context ctxt
;
5863 region_model
model (&mgr
);
5864 const svalue
*p_init
= model
.get_rvalue (p
, &ctxt
);
5865 const svalue
*q_init
= model
.get_rvalue (q
, &ctxt
);
5867 ASSERT_TRUE (p_init
->involves_p (p_init
));
5868 ASSERT_FALSE (p_init
->involves_p (q_init
));
5870 const region
*star_p_reg
= mgr
.get_symbolic_region (p_init
);
5871 const region
*star_q_reg
= mgr
.get_symbolic_region (q_init
);
5873 const svalue
*init_star_p
= mgr
.get_or_create_initial_value (star_p_reg
);
5874 const svalue
*init_star_q
= mgr
.get_or_create_initial_value (star_q_reg
);
5876 ASSERT_TRUE (init_star_p
->involves_p (p_init
));
5877 ASSERT_FALSE (p_init
->involves_p (init_star_p
));
5878 ASSERT_FALSE (init_star_p
->involves_p (q_init
));
5879 ASSERT_TRUE (init_star_q
->involves_p (q_init
));
5880 ASSERT_FALSE (init_star_q
->involves_p (p_init
));
5883 /* Run all of the selftests within this file. */
5886 analyzer_region_model_cc_tests ()
5888 test_tree_cmp_on_constants ();
5892 test_get_representative_tree ();
5893 test_unique_constants ();
5894 test_unique_unknowns ();
5895 test_initial_svalue_folding ();
5896 test_unaryop_svalue_folding ();
5897 test_binop_svalue_folding ();
5898 test_sub_svalue_folding ();
5899 test_descendent_of_p ();
5901 test_compound_assignment ();
5902 test_stack_frames ();
5903 test_get_representative_path_var ();
5905 test_canonicalization_2 ();
5906 test_canonicalization_3 ();
5907 test_canonicalization_4 ();
5908 test_state_merging ();
5909 test_constraint_merging ();
5910 test_widening_constraints ();
5911 test_iteration_1 ();
5912 test_malloc_constraints ();
5916 test_POINTER_PLUS_EXPR_then_MEM_REF ();
5922 } // namespace selftest
5924 #endif /* CHECKING_P */
5928 #endif /* #if ENABLE_ANALYZER */