@@ -126,6 +126,8 @@ class call_summary_replay;
struct per_function_data;
struct interesting_t;
+class feasible_node;
+
/* Forward decls of functions. */
extern void dump_tree (pretty_printer *pp, tree t);
@@ -88,6 +88,7 @@ public:
std::unique_ptr<exploded_path>
get_best_epath (const exploded_node *target_enode,
+ const pending_diagnostic &pd,
const char *desc, unsigned diag_idx,
std::unique_ptr<feasibility_problem> *out_problem);
@@ -96,12 +97,14 @@ private:
std::unique_ptr<exploded_path>
explore_feasible_paths (const exploded_node *target_enode,
+ const pending_diagnostic &pd,
const char *desc, unsigned diag_idx);
bool
process_worklist_item (feasible_worklist *worklist,
const trimmed_graph &tg,
feasible_graph *fg,
const exploded_node *target_enode,
+ const pending_diagnostic &pd,
unsigned diag_idx,
std::unique_ptr<exploded_path> *out_best_path) const;
void dump_trimmed_graph (const exploded_node *target_enode,
@@ -138,6 +141,7 @@ private:
std::unique_ptr<exploded_path>
epath_finder::get_best_epath (const exploded_node *enode,
+ const pending_diagnostic &pd,
const char *desc, unsigned diag_idx,
std::unique_ptr<feasibility_problem> *out_problem)
{
@@ -161,7 +165,7 @@ epath_finder::get_best_epath (const exploded_node *enode,
if (logger)
logger->log ("trying to find shortest feasible path");
if (std::unique_ptr<exploded_path> epath
- = explore_feasible_paths (enode, desc, diag_idx))
+ = explore_feasible_paths (enode, pd, desc, diag_idx))
{
if (logger)
logger->log ("accepting %qs at EN: %i, SN: %i (sd: %i)"
@@ -374,6 +378,7 @@ private:
std::unique_ptr<exploded_path>
epath_finder::explore_feasible_paths (const exploded_node *target_enode,
+ const pending_diagnostic &pd,
const char *desc, unsigned diag_idx)
{
logger *logger = get_logger ();
@@ -415,8 +420,8 @@ epath_finder::explore_feasible_paths (const exploded_node *target_enode,
{
auto_checking_feasibility sentinel (mgr);
- while (process_worklist_item (&worklist, tg, &fg, target_enode, diag_idx,
- &best_path))
+ while (process_worklist_item (&worklist, tg, &fg, target_enode, pd,
+ diag_idx, &best_path))
{
/* Empty; the work is done within process_worklist_item. */
}
@@ -449,7 +454,10 @@ epath_finder::explore_feasible_paths (const exploded_node *target_enode,
Return false if the processing of the worklist should stop
(either due to reaching TARGET_ENODE, or hitting a limit).
Write to *OUT_BEST_PATH if stopping due to finding a feasible path
- to TARGET_ENODE. */
+ to TARGET_ENODE.
+ Use PD to provide additional restrictions on feasibility of
+ the final path in the feasible_graph before converting to
+ an exploded_path. */
bool
epath_finder::
@@ -457,6 +465,7 @@ process_worklist_item (feasible_worklist *worklist,
const trimmed_graph &tg,
feasible_graph *fg,
const exploded_node *target_enode,
+ const pending_diagnostic &pd,
unsigned diag_idx,
std::unique_ptr<exploded_path> *out_best_path) const
{
@@ -514,6 +523,13 @@ process_worklist_item (feasible_worklist *worklist,
" (length: %i)",
target_enode->m_index, diag_idx,
succ_fnode->get_path_length ());
+ if (!pd.check_valid_fpath_p (succ_fnode))
+ {
+ if (logger)
+ logger->log ("rejecting feasible path due to"
+ " pending_diagnostic");
+ return false;
+ }
*out_best_path = fg->make_epath (succ_fnode);
if (flag_dump_analyzer_feasibility)
dump_feasible_path (target_enode, diag_idx, *fg, *succ_fnode);
@@ -808,7 +824,7 @@ saved_diagnostic::calc_best_epath (epath_finder *pf)
LOG_SCOPE (logger);
m_problem = NULL;
- m_best_epath = pf->get_best_epath (m_enode, m_d->get_kind (), m_idx,
+ m_best_epath = pf->get_best_epath (m_enode, *m_d, m_d->get_kind (), m_idx,
&m_problem);
/* Handle failure to find a feasible path. */
@@ -62,6 +62,7 @@ along with GCC; see the file COPYING3. If not see
#include "analyzer/exploded-graph.h"
#include "make-unique.h"
#include "analyzer/checker-path.h"
+#include "analyzer/feasible-graph.h"
/* A subclass of pending_diagnostic for complaining about suspected
infinite recursion. */
@@ -199,7 +200,106 @@ public:
NULL, NULL, NULL));
}
+ /* Reject paths in which conjured svalues have affected control flow
+ since m_prev_entry_enode. */
+
+ bool check_valid_fpath_p (const feasible_node *final_fnode)
+ const final override
+ {
+ /* Reject paths in which calls with unknown side effects have occurred
+ since m_prev_entry_enode.
+ Find num calls with side effects. Walk backward until we reach the
+ pref */
+ gcc_assert (final_fnode->get_inner_node () == m_new_entry_enode);
+
+ /* FG is actually a tree. Walk backwards from FINAL_FNODE until we
+ reach the prev_entry_enode (or the origin). */
+ const feasible_node *iter_fnode = final_fnode;
+ while (iter_fnode->get_inner_node ()->m_index != 0)
+ {
+ gcc_assert (iter_fnode->m_preds.length () == 1);
+
+ feasible_edge *pred_fedge
+ = static_cast <feasible_edge *> (iter_fnode->m_preds[0]);
+
+ /* Determine if conjured svalues have affected control flow
+ since the prev entry node. */
+ if (fedge_uses_conjured_svalue_p (pred_fedge))
+ /* If so, then reject this diagnostic. */
+ return false;
+ iter_fnode = static_cast <feasible_node *> (pred_fedge->m_src);
+ if (iter_fnode->get_inner_node () == m_prev_entry_enode)
+ /* Accept this diagnostic. */
+ return true;
+ }
+
+ /* We shouldn't get here; if we do, reject the diagnostic. */
+ gcc_unreachable ();
+ return false;
+ }
+
private:
+ /* Return true iff control flow along FEDGE was affected by
+ a conjured_svalue. */
+ static bool fedge_uses_conjured_svalue_p (feasible_edge *fedge)
+ {
+ const exploded_edge *eedge = fedge->get_inner_edge ();
+ const superedge *sedge = eedge->m_sedge;
+ if (!sedge)
+ return false;
+ const cfg_superedge *cfg_sedge = sedge->dyn_cast_cfg_superedge ();
+ if (!cfg_sedge)
+ return false;
+ const gimple *last_stmt = sedge->m_src->get_last_stmt ();
+ if (!last_stmt)
+ return false;
+
+ const feasible_node *dst_fnode
+ = static_cast<const feasible_node *> (fedge->m_dest);
+ const region_model &model = dst_fnode->get_state ().get_model ();
+
+ if (const gcond *cond_stmt = dyn_cast <const gcond *> (last_stmt))
+ {
+ if (expr_uses_conjured_svalue_p (model, gimple_cond_lhs (cond_stmt)))
+ return true;
+ if (expr_uses_conjured_svalue_p (model, gimple_cond_rhs (cond_stmt)))
+ return true;
+ }
+ else if (const gswitch *switch_stmt
+ = dyn_cast <const gswitch *> (last_stmt))
+ {
+ if (expr_uses_conjured_svalue_p (model,
+ gimple_switch_index (switch_stmt)))
+ return true;
+ }
+ return false;
+ }
+
+ /* Return true iff EXPR is affected by a conjured_svalue. */
+ static bool expr_uses_conjured_svalue_p (const region_model &model,
+ tree expr)
+ {
+ class conjured_svalue_finder : public visitor
+ {
+ public:
+ conjured_svalue_finder () : m_found_conjured_svalues (false)
+ {
+ }
+ void
+ visit_conjured_svalue (const conjured_svalue *) final override
+ {
+ m_found_conjured_svalues = true;
+ }
+
+ bool m_found_conjured_svalues;
+ };
+
+ const svalue *sval = model.get_rvalue (expr, NULL);
+ conjured_svalue_finder v;
+ sval->accept (&v);
+ return v.m_found_conjured_svalues;
+ }
+
const exploded_node *m_prev_entry_enode;
const exploded_node *m_new_entry_enode;
tree m_callee_fndecl;
@@ -347,6 +347,15 @@ class pending_diagnostic
{
/* Default no-op implementation. */
}
+
+ /* Vfunc to give diagnostic subclasses the opportunity to reject diagnostics
+ by imposing their own additional feasibility checks on the path to a
+ given feasible_node. */
+ virtual bool check_valid_fpath_p (const feasible_node *) const
+ {
+ /* Default implementation: accept this path. */
+ return true;
+ }
};
/* A template to make it easier to make subclasses of pending_diagnostic.
new file mode 100644
@@ -0,0 +1,145 @@
+/* Reduced from qemu-7.2.0's qobject/json-parser.c, which
+ is licensed under LGPLv2.1 or later. */
+
+/* { dg-additional-options "-fno-analyzer-call-summaries -Wno-analyzer-too-complex" } */
+
+#define NULL ((void *)0)
+typedef __builtin_va_list va_list;
+
+typedef struct _GQueue GQueue;
+typedef struct Error Error;
+typedef struct QList QList;
+typedef struct QObject QObject;
+
+struct QObjectBase_ {
+ /* [...snip...] */
+};
+
+
+struct QObject {
+ struct QObjectBase_ base;
+};
+
+#define QOBJECT(obj) ((QObject *)obj)
+#define qobject_unref(OBJ) /* [...snip...] */
+
+typedef struct QTailQLink {
+ void *tql_next;
+ struct QTailQLink *tql_prev;
+} QTailQLink;
+
+struct QList {
+ struct QObjectBase_ base;
+ union {
+ struct QListEntry *tqh_first;
+ QTailQLink tqh_circ;
+ } head;
+};
+QList *qlist_new(void);
+void qlist_append_obj(QList *qlist, QObject *obj);
+
+typedef enum json_token_type {
+ /* [...snip...] */
+ JSON_LSQUARE,
+ JSON_RSQUARE,
+ /* [...snip...] */
+ JSON_COMMA,
+ /* [...snip...] */
+ JSON_KEYWORD,
+ /* [...snip...] */
+} JSONTokenType;
+typedef struct JSONToken JSONToken;
+
+struct JSONToken {
+ JSONTokenType type;
+ int x;
+ int y;
+ char str[];
+};
+
+typedef struct JSONParserContext {
+ Error *err;
+ JSONToken *current;
+ GQueue *buf;
+ va_list *ap;
+} JSONParserContext;
+static QObject *parse_value(JSONParserContext *ctxt);
+
+JSONToken *parser_context_pop_token(JSONParserContext *ctxt);
+JSONToken *parser_context_peek_token(JSONParserContext *ctxt);
+
+static QObject *parse_array(JSONParserContext *ctxt) {
+ QList *list = NULL;
+ JSONToken *token, *peek;
+
+ token = parser_context_pop_token(ctxt);
+
+ list = qlist_new();
+
+ peek = parser_context_peek_token(ctxt);
+ if (peek == NULL) {
+ goto out;
+ }
+
+ if (peek->type != JSON_RSQUARE) {
+ QObject *obj;
+
+ obj = parse_value(ctxt); /* { dg-bogus "infinite recursion" } */
+ if (obj == NULL) {
+ goto out;
+ }
+
+ qlist_append_obj(list, obj);
+
+ token = parser_context_pop_token(ctxt);
+ if (token == NULL) {
+ goto out;
+ }
+
+ while (token->type != JSON_RSQUARE) {
+ if (token->type != JSON_COMMA) {
+ goto out;
+ }
+
+ obj = parse_value(ctxt);
+ if (obj == NULL) {
+ goto out;
+ }
+
+ qlist_append_obj(list, obj);
+
+ token = parser_context_pop_token(ctxt);
+ if (token == NULL) {
+ goto out;
+ }
+ }
+ } else {
+ (void)parser_context_pop_token(ctxt);
+ }
+
+ return QOBJECT(list);
+
+out:
+ qobject_unref(list);
+ return NULL;
+}
+
+QObject *parse_keyword(JSONParserContext *ctxt);
+
+QObject *parse_value(JSONParserContext *ctxt) {
+ JSONToken *token;
+
+ token = parser_context_peek_token(ctxt);
+ if (token == NULL) {
+ return NULL;
+ }
+
+ switch (token->type) {
+ case JSON_LSQUARE:
+ return parse_array(ctxt); /* { dg-bogus "infinite recursion" } */
+ case JSON_KEYWORD:
+ return parse_keyword(ctxt);
+ default:
+ return NULL;
+ }
+}
new file mode 100644
@@ -0,0 +1,113 @@
+struct st1;
+
+int foo (struct st1 *p);
+int bar (struct st1 *p);
+
+void test_1 (struct st1 *p)
+{
+ test_1 (p); /* { dg-warning "infinite recursion" } */
+}
+
+void test_2_if (struct st1 *p)
+{
+ if (foo (p))
+ test_2_if (p); /* { dg-bogus "infinite recursion" } */
+}
+
+void test_2_switch (struct st1 *p)
+{
+ switch (foo (p))
+ {
+ case 0 ... 9:
+ test_2_switch (p); /* { dg-bogus "infinite recursion" } */
+ break;
+ default:
+ break;
+ }
+}
+
+void test_2_if_compound (struct st1 *p)
+{
+ if ((foo (p) + bar (p)) >= 0)
+ test_2_if_compound (p); /* { dg-bogus "infinite recursion" } */
+}
+
+void test_3 (struct st1 *p)
+{
+ foo (p);
+ test_3 (p); /* { dg-warning "infinite recursion" } */
+ /* The content of *p never affects control flow, so we should
+ report this. */
+}
+
+struct st2
+{
+ int i;
+};
+
+void test_4 (struct st2 *p)
+{
+ if (p->i > 0)
+ test_4 (p); /* { dg-warning "infinite recursion" } */
+}
+
+void test_5 (struct st2 *p)
+{
+ if (p->i-- > 0)
+ test_5 (p); /* { dg-bogus "infinite recursion" } */
+}
+
+/* Mixtures of heap allocation and recursion. It's not clear what we
+ should do for such cases, but make sure we don't ICE. */
+
+void test_6 (struct st2 *p)
+{
+ struct st2 *q = __builtin_malloc (p->i);
+ if (!q)
+ return;
+ q->i = p->i;
+ test_6 (q);
+ __builtin_free (q);
+}
+
+void test_7 (struct st2 *p)
+{
+ struct st2 *q = __builtin_malloc (p->i);
+ q->i = p->i; /* { dg-warning "dereference of possibly-NULL 'q'" } */
+ test_7 (q);
+ __builtin_free (q);
+}
+
+void test_switch_1 (int i)
+{
+ int j;
+ switch (i)
+ {
+ case 0:
+ j = 1066;
+ break;
+ case 1:
+ j = 1776;
+ break;
+ default:
+ j = 1492;
+ break;
+ }
+ test_switch_1 (j); /* { dg-warning "infinite recursion" "" { xfail *-*-* } } */
+}
+
+void test_switch_2 (int i)
+{
+ switch (i)
+ {
+ case 0:
+ test_switch_2 (1066);
+ break;
+ case 1:
+ test_switch_2 (1776);
+ break;
+ default:
+ test_switch_2 (1492); /* { dg-warning "infinite recursion" "" { xfail *-*-* } } */
+ break;
+ }
+}
new file mode 100644
@@ -0,0 +1,322 @@
+/* Reduced from qemu-7.2.0's qobject/json-parser.c, which
+ is licensed under LGPLv2.1 or later. */
+
+/* { dg-additional-options "-fno-analyzer-call-summaries -Wno-analyzer-too-complex" } */
+
+#define NULL ((void *)0)
+typedef __builtin_va_list va_list;
+typedef __SIZE_TYPE__ size_t;
+
+typedef struct _GString GString;
+typedef struct _GQueue GQueue;
+typedef struct Error Error;
+typedef struct QDict QDict;
+typedef struct QList QList;
+typedef struct QObject QObject;
+typedef struct QString QString;
+
+typedef enum QType {
+ /* [...snip...] */
+ QTYPE_QSTRING,
+ /* [...snip...] */
+} QType;
+
+struct QObjectBase_ {
+ QType type;
+};
+
+struct QObject {
+ struct QObjectBase_ base;
+};
+
+#define QOBJECT(obj) ((QObject *)obj)
+#define qobject_unref(OBJ) /* [...snip...] */
+
+void qobject_ref_impl(QObject *obj);
+QType qobject_type(const QObject *obj);
+QObject *qobject_check_type(const QObject *obj, QType type);
+
+typedef struct QTailQLink {
+ void *tql_next;
+ struct QTailQLink *tql_prev;
+} QTailQLink;
+
+typedef struct QDictEntry {
+ char *key;
+ QObject *value;
+ struct {
+ struct QDictEntry *le_next;
+ struct QDictEntry **le_prev;
+ } next;
+} QDictEntry;
+
+struct QDict {
+ struct QObjectBase_ base;
+ size_t size;
+ struct {
+ struct QDictEntry *lh_first;
+ } table[512];
+};
+
+QDict *qdict_new(void);
+void qdict_put_obj(QDict *qdict, const char *key, QObject *value);
+int qdict_haskey(const QDict *qdict, const char *key);
+typedef struct QListEntry {
+ QObject *value;
+ union {
+ struct QListEntry *tqe_next;
+ QTailQLink tqe_circ;
+ } next;
+} QListEntry;
+
+struct QList {
+ struct QObjectBase_ base;
+ union {
+ struct QListEntry *tqh_first;
+ QTailQLink tqh_circ;
+ } head;
+};
+QList *qlist_new(void);
+void qlist_append_obj(QList *qlist, QObject *obj);
+
+struct QString {
+ struct QObjectBase_ base;
+ const char *string;
+};
+QString *qstring_from_str(const char *str);
+const char *qstring_get_str(const QString *qstring);
+
+typedef enum json_token_type {
+ JSON_ERROR = 0,
+
+ JSON_LCURLY = 100,
+ JSON_MIN = JSON_LCURLY,
+ JSON_RCURLY,
+ JSON_LSQUARE,
+ JSON_RSQUARE,
+ JSON_COLON,
+ JSON_COMMA,
+ JSON_INTEGER,
+ JSON_FLOAT,
+ JSON_KEYWORD,
+ JSON_STRING,
+ JSON_INTERP,
+ JSON_END_OF_INPUT,
+ JSON_MAX = JSON_END_OF_INPUT
+} JSONTokenType;
+typedef struct JSONToken JSONToken;
+
+struct JSONToken {
+ JSONTokenType type;
+ int x;
+ int y;
+ char str[];
+};
+
+typedef struct JSONParserContext {
+ Error *err;
+ JSONToken *current;
+ GQueue *buf;
+ va_list *ap;
+} JSONParserContext;
+static QObject *parse_value(JSONParserContext *ctxt);
+
+void __attribute__((__format__(gnu_printf, 3, 4)))
+parse_error(JSONParserContext *ctxt, JSONToken *token, const char *msg, ...);
+
+JSONToken *parser_context_pop_token(JSONParserContext *ctxt);
+JSONToken *parser_context_peek_token(JSONParserContext *ctxt);
+
+static int parse_pair(JSONParserContext *ctxt, QDict *dict) {
+ QObject *key_obj = NULL;
+ QString *key;
+ QObject *value;
+ JSONToken *peek, *token;
+
+ peek = parser_context_peek_token(ctxt);
+ if (peek == NULL) {
+ parse_error(ctxt, NULL, "premature EOI");
+ goto out;
+ }
+
+ key_obj = parse_value(ctxt); /* { dg-bogus "infinite recursion" } */
+ key = ((QString *)qobject_check_type(key_obj, QTYPE_QSTRING));
+ if (!key) {
+ parse_error(ctxt, peek, "key is not a string in object");
+ goto out;
+ }
+
+ token = parser_context_pop_token(ctxt);
+ if (token == NULL) {
+ parse_error(ctxt, NULL, "premature EOI");
+ goto out;
+ }
+
+ if (token->type != JSON_COLON) {
+ parse_error(ctxt, token, "missing : in object pair");
+ goto out;
+ }
+
+ value = parse_value(ctxt);
+ if (value == NULL) {
+ parse_error(ctxt, token, "Missing value in dict");
+ goto out;
+ }
+
+ if (qdict_haskey(dict, qstring_get_str(key))) {
+ parse_error(ctxt, token, "duplicate key");
+ goto out;
+ }
+
+ qdict_put_obj(dict, qstring_get_str(key), value);
+
+ qobject_unref(key_obj);
+ return 0;
+
+out:
+ qobject_unref(key_obj);
+ return -1;
+}
+
+static QObject *parse_object(JSONParserContext *ctxt) {
+ QDict *dict = NULL;
+ JSONToken *token, *peek;
+
+ token = parser_context_pop_token(ctxt);
+
+ dict = qdict_new();
+
+ peek = parser_context_peek_token(ctxt);
+ if (peek == NULL) {
+ parse_error(ctxt, NULL, "premature EOI");
+ goto out;
+ }
+
+ if (peek->type != JSON_RCURLY) {
+ if (parse_pair(ctxt, dict) == -1) {
+ goto out;
+ }
+
+ token = parser_context_pop_token(ctxt);
+ if (token == NULL) {
+ parse_error(ctxt, NULL, "premature EOI");
+ goto out;
+ }
+
+ while (token->type != JSON_RCURLY) {
+ if (token->type != JSON_COMMA) {
+ parse_error(ctxt, token, "expected separator in dict");
+ goto out;
+ }
+
+ if (parse_pair(ctxt, dict) == -1) {
+ goto out;
+ }
+
+ token = parser_context_pop_token(ctxt);
+ if (token == NULL) {
+ parse_error(ctxt, NULL, "premature EOI");
+ goto out;
+ }
+ }
+ } else {
+ (void)parser_context_pop_token(ctxt);
+ }
+
+ return QOBJECT(dict);
+
+out:
+ qobject_unref (dict);
+ return NULL;
+}
+
+static QObject *parse_array(JSONParserContext *ctxt) {
+ QList *list = NULL;
+ JSONToken *token, *peek;
+
+ token = parser_context_pop_token(ctxt);
+
+ list = qlist_new();
+
+ peek = parser_context_peek_token(ctxt);
+ if (peek == NULL) {
+ parse_error(ctxt, NULL, "premature EOI");
+ goto out;
+ }
+
+ if (peek->type != JSON_RSQUARE) {
+ QObject *obj;
+
+ obj = parse_value(ctxt); /* { dg-bogus "infinite recursion" } */
+ if (obj == NULL) {
+ parse_error(ctxt, token, "expecting value");
+ goto out;
+ }
+
+ qlist_append_obj(list, obj);
+
+ token = parser_context_pop_token(ctxt);
+ if (token == NULL) {
+ parse_error(ctxt, NULL, "premature EOI");
+ goto out;
+ }
+
+ while (token->type != JSON_RSQUARE) {
+ if (token->type != JSON_COMMA) {
+ parse_error(ctxt, token, "expected separator in list");
+ goto out;
+ }
+
+ obj = parse_value(ctxt);
+ if (obj == NULL) {
+ parse_error(ctxt, token, "expecting value");
+ goto out;
+ }
+
+ qlist_append_obj(list, obj);
+
+ token = parser_context_pop_token(ctxt);
+ if (token == NULL) {
+ parse_error(ctxt, NULL, "premature EOI");
+ goto out;
+ }
+ }
+ } else {
+ (void)parser_context_pop_token(ctxt);
+ }
+
+ return QOBJECT(list);
+
+out:
+ qobject_unref(list);
+ return NULL;
+}
+
+QObject *parse_keyword(JSONParserContext *ctxt);
+QObject *parse_literal(JSONParserContext *ctxt);
+
+QObject *parse_value(JSONParserContext *ctxt) {
+ JSONToken *token;
+
+ token = parser_context_peek_token(ctxt);
+ if (token == NULL) {
+ parse_error(ctxt, NULL, "premature EOI");
+ return NULL;
+ }
+
+ switch (token->type) {
+ case JSON_LCURLY:
+ return parse_object(ctxt); /* { dg-bogus "infinite recursion" } */
+ case JSON_LSQUARE:
+ return parse_array(ctxt); /* { dg-bogus "infinite recursion" } */
+ case JSON_INTEGER:
+ case JSON_FLOAT:
+ case JSON_STRING:
+ return parse_literal(ctxt);
+ case JSON_KEYWORD:
+ return parse_keyword(ctxt);
+ default:
+ parse_error(ctxt, token, "expecting value");
+ return NULL;
+ }
+}