analyzer: fix feasibility false +ve with overly complex svalues

gcc/analyzer/ChangeLog:
	* diagnostic-manager.cc
	(class auto_disable_complexity_checks): New.
	(epath_finder::explore_feasible_paths): Use it to disable
	complexity checks whilst processing the worklist.
	* region-model-manager.cc
	(region_model_manager::region_model_manager): Initialize
	m_check_complexity.
	(region_model_manager::reject_if_too_complex): Bail if
	m_check_complexity is false.
	* region-model.h
	(region_model_manager::enable_complexity_check): New.
	(region_model_manager::disable_complexity_check): New.
	(region_model_manager::m_check_complexity): New.

gcc/testsuite/ChangeLog:
	* gcc.dg/analyzer/feasibility-3.c: New test.

Signed-off-by: David Malcolm <dmalcolm@redhat.com>

4 files changed, 182 insertions, 7 deletions

diff --git a/gcc/analyzer/diagnostic-manager.cc b/gcc/analyzer/diagnostic-manager.cc
index 631fef6ad78..ef3df324365 100644
--- a/gcc/analyzer/diagnostic-manager.cc
+++ b/gcc/analyzer/diagnostic-manager.cc
@@ -292,6 +292,34 @@ private:
   const shortest_paths<eg_traits, exploded_path> &m_sep;
 };
 
+/* When we're building the exploded graph we want to simplify
+   overly-complicated symbolic values down to "UNKNOWN" to try to avoid
+   state explosions and unbounded chains of exploration.
+
+   However, when we're building the feasibility graph for a diagnostic
+   (actually a tree), we don't want UNKNOWN values, as conditions on them
+   are also unknown: we don't want to have a contradiction such as a path
+   where (VAL != 0) and then (VAL == 0) along the same path.
+
+   Hence this is an RAII class for temporarily disabling complexity-checking
+   in the region_model_manager, for use within
+   epath_finder::explore_feasible_paths.  */
+
+class auto_disable_complexity_checks
+{
+public:
+  auto_disable_complexity_checks (region_model_manager *mgr) : m_mgr (mgr)
+  {
+    m_mgr->disable_complexity_check ();
+  }
+  ~auto_disable_complexity_checks ()
+  {
+    m_mgr->enable_complexity_check ();
+  }
+private:
+  region_model_manager *m_mgr;
+};
+
 /* Attempt to find the shortest feasible path from the origin to
    TARGET_ENODE by iteratively building a feasible_graph, in which
    every path to a feasible_node is feasible by construction.
@@ -344,6 +372,8 @@ epath_finder::explore_feasible_paths (const exploded_node *target_enode,
   logger *logger = get_logger ();
   LOG_SCOPE (logger);
 
+  region_model_manager *mgr = m_eg.get_engine ()->get_model_manager ();
+
   /* Determine the shortest path to TARGET_ENODE from each node in
      the exploded graph.  */
   shortest_paths<eg_traits, exploded_path> sep
@@ -363,8 +393,7 @@ epath_finder::explore_feasible_paths (const exploded_node *target_enode,
 
   /* Populate the worklist with the origin node.  */
   {
-    feasibility_state init_state (m_eg.get_engine ()->get_model_manager (),
-				  m_eg.get_supergraph ());
+    feasibility_state init_state (mgr, m_eg.get_supergraph ());
     feasible_node *origin = fg.add_node (m_eg.get_origin (), init_state, 0);
     worklist.add_node (origin);
   }
@@ -376,11 +405,15 @@ epath_finder::explore_feasible_paths (const exploded_node *target_enode,
   /* Set this if we find a feasible path to TARGET_ENODE.  */
   exploded_path *best_path = NULL;
 
-  while (process_worklist_item (&worklist, tg, &fg, target_enode, diag_idx,
-				&best_path))
-    {
-      /* Empty; the work is done within process_worklist_item.  */
-    }
+  {
+    auto_disable_complexity_checks sentinel (mgr);
+
+    while (process_worklist_item (&worklist, tg, &fg, target_enode, diag_idx,
+				  &best_path))
+      {
+	/* Empty; the work is done within process_worklist_item.  */
+      }
+  }
 
   if (logger)
     {
diff --git a/gcc/analyzer/region-model-manager.cc b/gcc/analyzer/region-model-manager.cc
index fccb93ea5d1..14c57d8e0d8 100644
--- a/gcc/analyzer/region-model-manager.cc
+++ b/gcc/analyzer/region-model-manager.cc
@@ -71,6 +71,7 @@ region_model_manager::region_model_manager ()
   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_max_complexity (0, 0),
   m_code_region (alloc_region_id (), &m_root_region),
   m_fndecls_map (), m_labels_map (),
@@ -160,6 +161,9 @@ region_model_manager::too_complex_p (const complexity &c) const
 bool
 region_model_manager::reject_if_too_complex (svalue *sval)
 {
+  if (!m_check_complexity)
+    return false;
+
   const complexity &c = sval->get_complexity ();
   if (!too_complex_p (c))
     {
diff --git a/gcc/analyzer/region-model.h b/gcc/analyzer/region-model.h
index cc39929db26..1c7a3865346 100644
--- a/gcc/analyzer/region-model.h
+++ b/gcc/analyzer/region-model.h
@@ -323,6 +323,9 @@ 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; }
+
 private:
   bool too_complex_p (const complexity &c) const;
   bool reject_if_too_complex (svalue *sval);
@@ -407,6 +410,8 @@ private:
 		   conjured_svalue *> conjured_values_map_t;
   conjured_values_map_t m_conjured_values_map;
 
+  bool m_check_complexity;
+
   /* Maximum complexity of svalues that weren't rejected.  */
   complexity m_max_complexity;
 
diff --git a/gcc/testsuite/gcc.dg/analyzer/feasibility-3.c b/gcc/testsuite/gcc.dg/analyzer/feasibility-3.c
new file mode 100644
index 00000000000..0c0bd14fa54
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/analyzer/feasibility-3.c
@@ -0,0 +1,133 @@
+/* Reduced and adapted from Linux: fs/proc/inode.c: proc_reg_open
+   (GPL v2.0).  */
+
+/* Types.  */
+
+typedef unsigned char u8;
+typedef _Bool bool;
+typedef unsigned int gfp_t;
+
+struct file;
+struct kmem_cache;
+struct proc_dir_entry;
+
+struct inode { /* [...snip...] */ };
+
+enum {
+ PROC_ENTRY_PERMANENT = 1U << 0,
+};
+
+struct proc_ops {
+ /* [...snip...] */
+ int (*proc_open)(struct inode *, struct file *);
+ /* [...snip...] */
+ int (*proc_release)(struct inode *, struct file *);
+ /* [...snip...] */
+};
+
+struct proc_dir_entry {
+ /* [...snip...] */
+ struct completion *pde_unload_completion;
+ /* [...snip...] */
+ union {
+  const struct proc_ops *proc_ops;
+  const struct file_operations *proc_dir_ops;
+ };
+ /* [...snip...] */
+ u8 flags;
+ /* [...snip...] */
+};
+
+struct pde_opener {
+ /* [...snip...] */
+ struct file *file;
+ /* [...snip...] */
+};
+
+struct proc_inode {
+ /* [...snip...] */
+ struct proc_dir_entry *pde;
+ /* [...snip...] */
+ struct inode vfs_inode;
+};
+
+/* Data.  */
+
+static struct kmem_cache *pde_opener_cache __attribute__((__section__(".data..ro_after_init")));
+
+/* Functions. */
+
+void *kmem_cache_alloc(struct kmem_cache *, gfp_t flags) __attribute__((__malloc__));
+void kmem_cache_free(struct kmem_cache *, void *);
+
+static inline bool pde_is_permanent(const struct proc_dir_entry *pde)
+{
+ return pde->flags & PROC_ENTRY_PERMANENT;
+}
+
+static inline struct proc_inode *PROC_I(const struct inode *inode)
+{
+  void *__mptr = (void *)(inode);
+  return ((struct proc_inode *)(__mptr - __builtin_offsetof(struct proc_inode, vfs_inode)));
+}
+
+static inline struct proc_dir_entry *PDE(const struct inode *inode)
+{
+ return PROC_I(inode)->pde;
+}
+
+/* We don't want to emit bogus use of uninitialized value 'pdeo'
+   warnings from -Wanalyzer-use-of-uninitialized-value in this function;
+   these would require following infeasible paths in which "release" is
+   first NULL (to avoid the initialization of "pdeo") and then is non-NULL
+   (to access "pdeo").
+
+   "release" is sufficiently complicated in this function to hit the
+   complexity limit for symbolic values during enode exploration.  */
+
+static int proc_reg_open(struct inode *inode, struct file *file)
+{
+ struct proc_dir_entry *pde = PDE(inode);
+ int rv = 0;
+ typeof(((struct proc_ops*)0)->proc_open) open;
+ typeof(((struct proc_ops*)0)->proc_release) release;
+ struct pde_opener *pdeo;
+
+ if (pde_is_permanent(pde)) {
+  open = pde->proc_ops->proc_open;
+  if (open)
+   rv = open(inode, file);
+  return rv;
+ }
+
+ /* [...snip...] */
+
+ release = pde->proc_ops->proc_release;
+ if (release) {
+  pdeo = kmem_cache_alloc(pde_opener_cache,
+			  ((( gfp_t)(0x400u|0x800u))
+			   | (( gfp_t)0x40u)
+			   | (( gfp_t)0x80u)));
+  if (!pdeo) {
+   rv = -12;
+   goto out_unuse;
+  }
+ }
+
+ open = pde->proc_ops->proc_open;
+ if (open)
+  rv = open(inode, file);
+
+ if (release) {
+  if (rv == 0) {
+
+   pdeo->file = file; /* { dg-bogus "uninit" } */
+   /* [...snip...] */
+  } else
+   kmem_cache_free(pde_opener_cache, pdeo); /* { dg-bogus "uninit" } */
+ }
+
+out_unuse:
+ /* [...snip...] */
+ return rv;
+}