@@ -303,18 +303,21 @@ private:
Hence this is an RAII class for temporarily disabling complexity-checking
in the region_model_manager, for use within
- epath_finder::explore_feasible_paths. */
+ epath_finder::explore_feasible_paths.
-class auto_disable_complexity_checks
+ We also disable the creation of unknown_svalue instances during feasibility
+ checking, instead creating unique svalues, to avoid paradoxes in paths. */
+
+class auto_checking_feasibility
{
public:
- auto_disable_complexity_checks (region_model_manager *mgr) : m_mgr (mgr)
+ auto_checking_feasibility (region_model_manager *mgr) : m_mgr (mgr)
{
- m_mgr->disable_complexity_check ();
+ m_mgr->begin_checking_feasibility ();
}
- ~auto_disable_complexity_checks ()
+ ~auto_checking_feasibility ()
{
- m_mgr->enable_complexity_check ();
+ m_mgr->end_checking_feasibility ();
}
private:
region_model_manager *m_mgr;
@@ -406,7 +409,7 @@ epath_finder::explore_feasible_paths (const exploded_node *target_enode,
exploded_path *best_path = NULL;
{
- auto_disable_complexity_checks sentinel (mgr);
+ auto_checking_feasibility sentinel (mgr);
while (process_worklist_item (&worklist, tg, &fg, target_enode, diag_idx,
&best_path))
@@ -73,7 +73,7 @@ region_model_manager::region_model_manager (logger *logger)
m_stack_region (alloc_region_id (), &m_root_region),
m_heap_region (alloc_region_id (), &m_root_region),
m_unknown_NULL (NULL),
- m_check_complexity (true),
+ m_checking_feasibility (false),
m_max_complexity (0, 0),
m_code_region (alloc_region_id (), &m_root_region),
m_fndecls_map (), m_labels_map (),
@@ -166,7 +166,7 @@ region_model_manager::too_complex_p (const complexity &c) const
bool
region_model_manager::reject_if_too_complex (svalue *sval)
{
- if (!m_check_complexity)
+ if (m_checking_feasibility)
return false;
const complexity &c = sval->get_complexity ();
@@ -238,6 +238,11 @@ region_model_manager::get_or_create_int_cst (tree type, poly_int64 val)
const svalue *
region_model_manager::get_or_create_unknown_svalue (tree type)
{
+ /* Don't create unknown values when doing feasibility testing;
+ instead, create a unique svalue. */
+ if (m_checking_feasibility)
+ return create_unique_svalue (type);
+
/* Special-case NULL, so that the hash_map can use NULL as the
"empty" value. */
if (type == NULL_TREE)
@@ -255,6 +260,16 @@ region_model_manager::get_or_create_unknown_svalue (tree type)
return sval;
}
+/* Return a freshly-allocated svalue of TYPE, owned by this manager. */
+
+const svalue *
+region_model_manager::create_unique_svalue (tree type)
+{
+ svalue *sval = new placeholder_svalue (type, "unique");
+ m_managed_dynamic_svalues.safe_push (sval);
+ return sval;
+}
+
/* Return the svalue * for the initial value of REG, creating it if
necessary. */
@@ -584,6 +599,42 @@ region_model_manager::maybe_fold_binop (tree type, enum tree_code op,
cst1, arg1))
return sval;
}
+ if (arg0->get_type () == boolean_type_node
+ && arg1->get_type () == boolean_type_node)
+ {
+ /* If the LHS are both _Bool, then... */
+ /* ..."(1 & x) -> x". */
+ if (cst0 && !zerop (cst0))
+ return get_or_create_cast (type, arg1);
+ /* ..."(x & 1) -> x". */
+ if (cst1 && !zerop (cst1))
+ return get_or_create_cast (type, arg0);
+ /* ..."(0 & x) -> 0". */
+ if (cst0 && zerop (cst0))
+ return get_or_create_int_cst (type, 0);
+ /* ..."(x & 0) -> 0". */
+ if (cst1 && zerop (cst1))
+ return get_or_create_int_cst (type, 0);
+ }
+ break;
+ case BIT_IOR_EXPR:
+ if (arg0->get_type () == boolean_type_node
+ && arg1->get_type () == boolean_type_node)
+ {
+ /* If the LHS are both _Bool, then... */
+ /* ..."(1 | x) -> 1". */
+ if (cst0 && !zerop (cst0))
+ return get_or_create_int_cst (type, 1);
+ /* ..."(x | 1) -> 1". */
+ if (cst1 && !zerop (cst1))
+ return get_or_create_int_cst (type, 1);
+ /* ..."(0 | x) -> x". */
+ if (cst0 && zerop (cst0))
+ return get_or_create_cast (type, arg1);
+ /* ..."(x | 0) -> x". */
+ if (cst1 && zerop (cst1))
+ return get_or_create_cast (type, arg0);
+ }
break;
case TRUTH_ANDIF_EXPR:
case TRUTH_AND_EXPR:
@@ -4555,6 +4555,39 @@ test_binop_svalue_folding ()
= mgr.get_or_create_binop (integer_type_node, PLUS_EXPR,
x_init_plus_one, cst_sval[1]);
ASSERT_EQ (x_init_plus_one_plus_one, x_init_plus_two);
+
+ /* Verify various binops on booleans. */
+ {
+ const svalue *sval_true = mgr.get_or_create_int_cst (boolean_type_node, 1);
+ const svalue *sval_false = mgr.get_or_create_int_cst (boolean_type_node, 0);
+ const svalue *sval_unknown
+ = mgr.get_or_create_unknown_svalue (boolean_type_node);
+ const placeholder_svalue sval_placeholder (boolean_type_node, "v");
+ for (auto op : {BIT_IOR_EXPR, TRUTH_OR_EXPR})
+ {
+ ASSERT_EQ (mgr.get_or_create_binop (boolean_type_node, op,
+ sval_true, sval_unknown),
+ sval_true);
+ ASSERT_EQ (mgr.get_or_create_binop (boolean_type_node, op,
+ sval_false, sval_unknown),
+ sval_unknown);
+ ASSERT_EQ (mgr.get_or_create_binop (boolean_type_node, op,
+ sval_false, &sval_placeholder),
+ &sval_placeholder);
+ }
+ for (auto op : {BIT_AND_EXPR, TRUTH_AND_EXPR})
+ {
+ ASSERT_EQ (mgr.get_or_create_binop (boolean_type_node, op,
+ sval_false, sval_unknown),
+ sval_false);
+ ASSERT_EQ (mgr.get_or_create_binop (boolean_type_node, op,
+ sval_true, sval_unknown),
+ sval_unknown);
+ ASSERT_EQ (mgr.get_or_create_binop (boolean_type_node, op,
+ sval_true, &sval_placeholder),
+ &sval_placeholder);
+ }
+ }
}
/* Verify that sub_svalues are folded as expected. */
@@ -286,6 +286,11 @@ public:
const svalue *maybe_get_char_from_string_cst (tree string_cst,
tree byte_offset_cst);
+ /* Dynamically-allocated svalue instances.
+ The number of these within the analysis can grow arbitrarily.
+ They are still owned by the manager. */
+ const svalue *create_unique_svalue (tree type);
+
/* region consolidation. */
const stack_region * get_stack_region () const { return &m_stack_region; }
const heap_region *get_heap_region () const { return &m_heap_region; }
@@ -332,8 +337,8 @@ public:
void log_stats (logger *logger, bool show_objs) const;
- void enable_complexity_check (void) { m_check_complexity = true; }
- void disable_complexity_check (void) { m_check_complexity = false; }
+ void begin_checking_feasibility (void) { m_checking_feasibility = true; }
+ void end_checking_feasibility (void) { m_checking_feasibility = false; }
logger *get_logger () const { return m_logger; }
@@ -429,7 +434,12 @@ private:
asm_output_svalue *> asm_output_values_map_t;
asm_output_values_map_t m_asm_output_values_map;
- bool m_check_complexity;
+ bool m_checking_feasibility;
+
+ /* "Dynamically-allocated" svalue instances.
+ The number of these within the analysis can grow arbitrarily.
+ They are still owned by the manager. */
+ auto_delete_vec<svalue> m_managed_dynamic_svalues;
/* Maximum complexity of svalues that weren't rejected. */
complexity m_max_complexity;
new file mode 100644
@@ -0,0 +1,110 @@
+/* { dg-additional-options "-O2 -Wno-analyzer-too-complex" } */
+/* TODO: remove the need for -Wno-analyzer-too-complex. */
+
+struct lisp;
+union vectorlike_header { long size; };
+
+static struct lisp *
+make_lisp_ptr (void *ptr, int type)
+{
+ char *p = ptr;
+ void *q = p + type;
+ return q;
+}
+
+static _Bool
+TAGGEDP (struct lisp *a, unsigned tag)
+{
+ return ! (((unsigned) (long) a - tag) & 7);
+}
+
+static _Bool
+VECTORLIKEP (struct lisp *x)
+{
+ return TAGGEDP (x, 5);
+}
+
+extern _Bool
+PSEUDOVECTOR_TYPEP (union vectorlike_header const *a, int code);
+
+static _Bool
+PSEUDOVECTORP (struct lisp *a, int code)
+{
+ if (! VECTORLIKEP (a))
+ return 0;
+ else
+ return PSEUDOVECTOR_TYPEP ((union vectorlike_header *) ((char *) a - 5),
+ code);
+}
+
+struct Lisp_Overlay
+{
+ union vectorlike_header header;
+ struct lisp *end;
+ struct Lisp_Overlay *next;
+};
+
+static _Bool
+OVERLAYP (struct lisp *x)
+{
+ return PSEUDOVECTORP (x, 4);
+}
+
+static struct Lisp_Overlay *
+XOVERLAY (struct lisp *a)
+{
+ void *r = (char *) a - 5;
+ return r;
+}
+struct buffer { struct Lisp_Overlay *overlays_before; };
+
+long marker_position (struct lisp *);
+
+void
+fix_overlays_before (struct buffer *bp, long prev, long pos)
+{
+ struct Lisp_Overlay *tail = bp->overlays_before, *parent = 0, *right_pair;
+ struct lisp *tem;
+ long end;
+ while (tail
+ && (tem = make_lisp_ptr (tail, 5),
+ (end = marker_position (XOVERLAY (tem)->end)) >= pos))
+ {
+ parent = tail;
+ tail = tail->next;
+ }
+ if (!tail || end < prev || !tail->next) /* { dg-bogus "use of uninitialized value 'end'" "uninit" { xfail *-*-* } } */
+ /* { dg-bogus "dereference of NULL 'tail'" "null deref" { target *-*-* } .-1 } */
+ return;
+ right_pair = parent;
+ parent = tail;
+ tail = tail->next;
+ while (tail)
+ {
+ tem = make_lisp_ptr (tail, 5);
+ end = marker_position (XOVERLAY (tem)->end);
+ if (end == pos)
+ {
+ struct Lisp_Overlay *found = tail;
+ tail = found->next;
+ parent->next = tail;
+ if (!right_pair)
+ {
+ found->next = bp->overlays_before;
+ bp->overlays_before = found;
+ }
+ else
+ {
+ found->next = right_pair->next;
+ right_pair->next = found;
+ }
+ }
+ else if (end == prev)
+ {
+ parent = tail;
+ tail = tail->next;
+ }
+ else
+ break;
+ }
+}