Initial commit of analyzer

This patch adds a static analysis pass to the middle-end, focusing
for this release on C code, and malloc/free issues in particular.

See:
 https://gcc.gnu.org/wiki/DavidMalcolm/StaticAnalyzer

gcc/ChangeLog:
	* Makefile.in (lang_opt_files): Add analyzer.opt.
	(ANALYZER_OBJS): New.
	(OBJS): Add digraph.o, graphviz.o, ordered-hash-map-tests.o,
	tristate.o and ANALYZER_OBJS.
	(TEXI_GCCINT_FILES): Add analyzer.texi.
	* common.opt (-fanalyzer): New driver option.
	* config.in: Regenerate.
	* configure: Regenerate.
	* configure.ac (--disable-analyzer, ENABLE_ANALYZER): New option.
	(gccdepdir): Also create depdir for "analyzer" subdir.
	* digraph.cc: New file.
	* digraph.h: New file.
	* doc/analyzer.texi: New file.
	* doc/gccint.texi ("Static Analyzer") New menu item.
	(analyzer.texi): Include it.
	* doc/invoke.texi ("Static Analyzer Options"): New list and new section.
	("Warning Options"): Add static analysis warnings to the list.
	(-Wno-analyzer-double-fclose): New option.
	(-Wno-analyzer-double-free): New option.
	(-Wno-analyzer-exposure-through-output-file): New option.
	(-Wno-analyzer-file-leak): New option.
	(-Wno-analyzer-free-of-non-heap): New option.
	(-Wno-analyzer-malloc-leak): New option.
	(-Wno-analyzer-possible-null-argument): New option.
	(-Wno-analyzer-possible-null-dereference): New option.
	(-Wno-analyzer-null-argument): New option.
	(-Wno-analyzer-null-dereference): New option.
	(-Wno-analyzer-stale-setjmp-buffer): New option.
	(-Wno-analyzer-tainted-array-index): New option.
	(-Wno-analyzer-use-after-free): New option.
	(-Wno-analyzer-use-of-pointer-in-stale-stack-frame): New option.
	(-Wno-analyzer-use-of-uninitialized-value): New option.
	(-Wanalyzer-too-complex): New option.
	(-fanalyzer-call-summaries): New warning.
	(-fanalyzer-checker=): New warning.
	(-fanalyzer-fine-grained): New warning.
	(-fno-analyzer-state-merge): New warning.
	(-fno-analyzer-state-purge): New warning.
	(-fanalyzer-transitivity): New warning.
	(-fanalyzer-verbose-edges): New warning.
	(-fanalyzer-verbose-state-changes): New warning.
	(-fanalyzer-verbosity=): New warning.
	(-fdump-analyzer): New warning.
	(-fdump-analyzer-callgraph): New warning.
	(-fdump-analyzer-exploded-graph): New warning.
	(-fdump-analyzer-exploded-nodes): New warning.
	(-fdump-analyzer-exploded-nodes-2): New warning.
	(-fdump-analyzer-exploded-nodes-3): New warning.
	(-fdump-analyzer-supergraph): New warning.
	* doc/sourcebuild.texi (dg-require-dot): New.
	(dg-check-dot): New.
	* gdbinit.in (break-on-saved-diagnostic): New command.
	* graphviz.cc: New file.
	* graphviz.h: New file.
	* ordered-hash-map-tests.cc: New file.
	* ordered-hash-map.h: New file.
	* passes.def (pass_analyzer): Add before
	pass_ipa_whole_program_visibility.
	* selftest-run-tests.c (selftest::run_tests): Call
	selftest::ordered_hash_map_tests_cc_tests.
	* selftest.h (selftest::ordered_hash_map_tests_cc_tests): New
	decl.
	* shortest-paths.h: New file.
	* timevar.def (TV_ANALYZER): New timevar.
	(TV_ANALYZER_SUPERGRAPH): Likewise.
	(TV_ANALYZER_STATE_PURGE): Likewise.
	(TV_ANALYZER_PLAN): Likewise.
	(TV_ANALYZER_SCC): Likewise.
	(TV_ANALYZER_WORKLIST): Likewise.
	(TV_ANALYZER_DUMP): Likewise.
	(TV_ANALYZER_DIAGNOSTICS): Likewise.
	(TV_ANALYZER_SHORTEST_PATHS): Likewise.
	* tree-pass.h (make_pass_analyzer): New decl.
	* tristate.cc: New file.
	* tristate.h: New file.

gcc/analyzer/ChangeLog:
	* ChangeLog: New file.
	* analyzer-selftests.cc: New file.
	* analyzer-selftests.h: New file.
	* analyzer.opt: New file.
	* analysis-plan.cc: New file.
	* analysis-plan.h: New file.
	* analyzer-logging.cc: New file.
	* analyzer-logging.h: New file.
	* analyzer-pass.cc: New file.
	* analyzer.cc: New file.
	* analyzer.h: New file.
	* call-string.cc: New file.
	* call-string.h: New file.
	* checker-path.cc: New file.
	* checker-path.h: New file.
	* constraint-manager.cc: New file.
	* constraint-manager.h: New file.
	* diagnostic-manager.cc: New file.
	* diagnostic-manager.h: New file.
	* engine.cc: New file.
	* engine.h: New file.
	* exploded-graph.h: New file.
	* pending-diagnostic.cc: New file.
	* pending-diagnostic.h: New file.
	* program-point.cc: New file.
	* program-point.h: New file.
	* program-state.cc: New file.
	* program-state.h: New file.
	* region-model.cc: New file.
	* region-model.h: New file.
	* sm-file.cc: New file.
	* sm-malloc.cc: New file.
	* sm-malloc.dot: New file.
	* sm-pattern-test.cc: New file.
	* sm-sensitive.cc: New file.
	* sm-signal.cc: New file.
	* sm-taint.cc: New file.
	* sm.cc: New file.
	* sm.h: New file.
	* state-purge.cc: New file.
	* state-purge.h: New file.
	* supergraph.cc: New file.
	* supergraph.h: New file.

gcc/testsuite/ChangeLog:
	* gcc.dg/analyzer/CVE-2005-1689-minimal.c: New test.
	* gcc.dg/analyzer/abort.c: New test.
	* gcc.dg/analyzer/alloca-leak.c: New test.
	* gcc.dg/analyzer/analyzer-decls.h: New header.
	* gcc.dg/analyzer/analyzer-verbosity-0.c: New test.
	* gcc.dg/analyzer/analyzer-verbosity-1.c: New test.
	* gcc.dg/analyzer/analyzer-verbosity-2.c: New test.
	* gcc.dg/analyzer/analyzer.exp: New suite.
	* gcc.dg/analyzer/attribute-nonnull.c: New test.
	* gcc.dg/analyzer/call-summaries-1.c: New test.
	* gcc.dg/analyzer/conditionals-2.c: New test.
	* gcc.dg/analyzer/conditionals-3.c: New test.
	* gcc.dg/analyzer/conditionals-notrans.c: New test.
	* gcc.dg/analyzer/conditionals-trans.c: New test.
	* gcc.dg/analyzer/data-model-1.c: New test.
	* gcc.dg/analyzer/data-model-2.c: New test.
	* gcc.dg/analyzer/data-model-3.c: New test.
	* gcc.dg/analyzer/data-model-4.c: New test.
	* gcc.dg/analyzer/data-model-5.c: New test.
	* gcc.dg/analyzer/data-model-5b.c: New test.
	* gcc.dg/analyzer/data-model-5c.c: New test.
	* gcc.dg/analyzer/data-model-5d.c: New test.
	* gcc.dg/analyzer/data-model-6.c: New test.
	* gcc.dg/analyzer/data-model-7.c: New test.
	* gcc.dg/analyzer/data-model-8.c: New test.
	* gcc.dg/analyzer/data-model-9.c: New test.
	* gcc.dg/analyzer/data-model-11.c: New test.
	* gcc.dg/analyzer/data-model-12.c: New test.
	* gcc.dg/analyzer/data-model-13.c: New test.
	* gcc.dg/analyzer/data-model-14.c: New test.
	* gcc.dg/analyzer/data-model-15.c: New test.
	* gcc.dg/analyzer/data-model-16.c: New test.
	* gcc.dg/analyzer/data-model-17.c: New test.
	* gcc.dg/analyzer/data-model-18.c: New test.
	* gcc.dg/analyzer/data-model-19.c: New test.
	* gcc.dg/analyzer/data-model-path-1.c: New test.
	* gcc.dg/analyzer/disabling.c: New test.
	* gcc.dg/analyzer/dot-output.c: New test.
	* gcc.dg/analyzer/double-free-lto-1-a.c: New test.
	* gcc.dg/analyzer/double-free-lto-1-b.c: New test.
	* gcc.dg/analyzer/double-free-lto-1.h: New header.
	* gcc.dg/analyzer/equivalence.c: New test.
	* gcc.dg/analyzer/explode-1.c: New test.
	* gcc.dg/analyzer/explode-2.c: New test.
	* gcc.dg/analyzer/factorial.c: New test.
	* gcc.dg/analyzer/fibonacci.c: New test.
	* gcc.dg/analyzer/fields.c: New test.
	* gcc.dg/analyzer/file-1.c: New test.
	* gcc.dg/analyzer/file-2.c: New test.
	* gcc.dg/analyzer/function-ptr-1.c: New test.
	* gcc.dg/analyzer/function-ptr-2.c: New test.
	* gcc.dg/analyzer/function-ptr-3.c: New test.
	* gcc.dg/analyzer/gzio-2.c: New test.
	* gcc.dg/analyzer/gzio-3.c: New test.
	* gcc.dg/analyzer/gzio-3a.c: New test.
	* gcc.dg/analyzer/gzio.c: New test.
	* gcc.dg/analyzer/infinite-recursion.c: New test.
	* gcc.dg/analyzer/loop-2.c: New test.
	* gcc.dg/analyzer/loop-2a.c: New test.
	* gcc.dg/analyzer/loop-3.c: New test.
	* gcc.dg/analyzer/loop-4.c: New test.
	* gcc.dg/analyzer/loop.c: New test.
	* gcc.dg/analyzer/malloc-1.c: New test.
	* gcc.dg/analyzer/malloc-2.c: New test.
	* gcc.dg/analyzer/malloc-3.c: New test.
	* gcc.dg/analyzer/malloc-callbacks.c: New test.
	* gcc.dg/analyzer/malloc-dce.c: New test.
	* gcc.dg/analyzer/malloc-dedupe-1.c: New test.
	* gcc.dg/analyzer/malloc-ipa-1.c: New test.
	* gcc.dg/analyzer/malloc-ipa-10.c: New test.
	* gcc.dg/analyzer/malloc-ipa-11.c: New test.
	* gcc.dg/analyzer/malloc-ipa-12.c: New test.
	* gcc.dg/analyzer/malloc-ipa-13.c: New test.
	* gcc.dg/analyzer/malloc-ipa-2.c: New test.
	* gcc.dg/analyzer/malloc-ipa-3.c: New test.
	* gcc.dg/analyzer/malloc-ipa-4.c: New test.
	* gcc.dg/analyzer/malloc-ipa-5.c: New test.
	* gcc.dg/analyzer/malloc-ipa-6.c: New test.
	* gcc.dg/analyzer/malloc-ipa-7.c: New test.
	* gcc.dg/analyzer/malloc-ipa-8-double-free.c: New test.
	* gcc.dg/analyzer/malloc-ipa-8-lto-a.c: New test.
	* gcc.dg/analyzer/malloc-ipa-8-lto-b.c: New test.
	* gcc.dg/analyzer/malloc-ipa-8-lto-c.c: New test.
	* gcc.dg/analyzer/malloc-ipa-8-lto.h: New test.
	* gcc.dg/analyzer/malloc-ipa-8-unchecked.c: New test.
	* gcc.dg/analyzer/malloc-ipa-9.c: New test.
	* gcc.dg/analyzer/malloc-macro-inline-events.c: New test.
	* gcc.dg/analyzer/malloc-macro-separate-events.c: New test.
	* gcc.dg/analyzer/malloc-macro.h: New header.
	* gcc.dg/analyzer/malloc-many-paths-1.c: New test.
	* gcc.dg/analyzer/malloc-many-paths-2.c: New test.
	* gcc.dg/analyzer/malloc-many-paths-3.c: New test.
	* gcc.dg/analyzer/malloc-paths-1.c: New test.
	* gcc.dg/analyzer/malloc-paths-10.c: New test.
	* gcc.dg/analyzer/malloc-paths-2.c: New test.
	* gcc.dg/analyzer/malloc-paths-3.c: New test.
	* gcc.dg/analyzer/malloc-paths-4.c: New test.
	* gcc.dg/analyzer/malloc-paths-5.c: New test.
	* gcc.dg/analyzer/malloc-paths-6.c: New test.
	* gcc.dg/analyzer/malloc-paths-7.c: New test.
	* gcc.dg/analyzer/malloc-paths-8.c: New test.
	* gcc.dg/analyzer/malloc-paths-9.c: New test.
	* gcc.dg/analyzer/malloc-vs-local-1a.c: New test.
	* gcc.dg/analyzer/malloc-vs-local-1b.c: New test.
	* gcc.dg/analyzer/malloc-vs-local-2.c: New test.
	* gcc.dg/analyzer/malloc-vs-local-3.c: New test.
	* gcc.dg/analyzer/malloc-vs-local-4.c: New test.
	* gcc.dg/analyzer/operations.c: New test.
	* gcc.dg/analyzer/params-2.c: New test.
	* gcc.dg/analyzer/params.c: New test.
	* gcc.dg/analyzer/paths-1.c: New test.
	* gcc.dg/analyzer/paths-1a.c: New test.
	* gcc.dg/analyzer/paths-2.c: New test.
	* gcc.dg/analyzer/paths-3.c: New test.
	* gcc.dg/analyzer/paths-4.c: New test.
	* gcc.dg/analyzer/paths-5.c: New test.
	* gcc.dg/analyzer/paths-6.c: New test.
	* gcc.dg/analyzer/paths-7.c: New test.
	* gcc.dg/analyzer/pattern-test-1.c: New test.
	* gcc.dg/analyzer/pattern-test-2.c: New test.
	* gcc.dg/analyzer/pointer-merging.c: New test.
	* gcc.dg/analyzer/pr61861.c: New test.
	* gcc.dg/analyzer/pragma-1.c: New test.
	* gcc.dg/analyzer/scope-1.c: New test.
	* gcc.dg/analyzer/sensitive-1.c: New test.
	* gcc.dg/analyzer/setjmp-1.c: New test.
	* gcc.dg/analyzer/setjmp-2.c: New test.
	* gcc.dg/analyzer/setjmp-3.c: New test.
	* gcc.dg/analyzer/setjmp-4.c: New test.
	* gcc.dg/analyzer/setjmp-5.c: New test.
	* gcc.dg/analyzer/setjmp-6.c: New test.
	* gcc.dg/analyzer/setjmp-7.c: New test.
	* gcc.dg/analyzer/setjmp-7a.c: New test.
	* gcc.dg/analyzer/setjmp-8.c: New test.
	* gcc.dg/analyzer/setjmp-9.c: New test.
	* gcc.dg/analyzer/signal-1.c: New test.
	* gcc.dg/analyzer/signal-2.c: New test.
	* gcc.dg/analyzer/signal-3.c: New test.
	* gcc.dg/analyzer/signal-4a.c: New test.
	* gcc.dg/analyzer/signal-4b.c: New test.
	* gcc.dg/analyzer/strcmp-1.c: New test.
	* gcc.dg/analyzer/switch.c: New test.
	* gcc.dg/analyzer/taint-1.c: New test.
	* gcc.dg/analyzer/zlib-1.c: New test.
	* gcc.dg/analyzer/zlib-2.c: New test.
	* gcc.dg/analyzer/zlib-3.c: New test.
	* gcc.dg/analyzer/zlib-4.c: New test.
	* gcc.dg/analyzer/zlib-5.c: New test.
	* gcc.dg/analyzer/zlib-6.c: New test.
	* lib/gcc-defs.exp (dg-check-dot): New procedure.
	* lib/target-supports.exp (check_dot_available): New procedure.
	(check_effective_target_analyzer): New.
	* lib/target-supports-dg.exp (dg-require-dot): New procedure.

1 files changed, 246 insertions, 0 deletions

diff --git a/gcc/analyzer/constraint-manager.h b/gcc/analyzer/constraint-manager.h
new file mode 100644
index 0000000..c6a40f9
--- /dev/null
+++ b/gcc/analyzer/constraint-manager.h
@@ -0,0 +1,246 @@
+/* Tracking equivalence classes and constraints at a point on an execution path.
+   Copyright (C) 2019-2020 Free Software Foundation, Inc.
+   Contributed by David Malcolm <dmalcolm@redhat.com>.
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify it
+under the terms of the GNU General Public License as published by
+the Free Software Foundation; either version 3, or (at your option)
+any later version.
+
+GCC is distributed in the hope that it will be useful, but
+WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING3.  If not see
+<http://www.gnu.org/licenses/>.  */
+
+#ifndef GCC_ANALYZER_CONSTRAINT_MANAGER_H
+#define GCC_ANALYZER_CONSTRAINT_MANAGER_H
+
+class constraint_manager;
+
+/* Abstract base class for specifying how state should be purged.  */
+
+class purge_criteria
+{
+public:
+  virtual ~purge_criteria () {}
+  virtual bool should_purge_p (svalue_id sid) const = 0;
+};
+
+/* An equivalence class within a constraint manager: a set of
+   svalue_ids that are known to all be equal to each other,
+   together with an optional tree constant that they are equal to.  */
+
+class equiv_class
+{
+public:
+  equiv_class ();
+  equiv_class (const equiv_class &other);
+
+  hashval_t hash () const;
+  bool operator== (const equiv_class &other);
+
+  void add (svalue_id sid, const constraint_manager &cm);
+  bool del (svalue_id sid);
+
+  tree get_any_constant () const { return m_constant; }
+
+  svalue_id get_representative () const;
+
+  void remap_svalue_ids (const svalue_id_map &map);
+
+  void canonicalize ();
+
+  void print (pretty_printer *pp) const;
+
+  /* An equivalence class can contain multiple constants (e.g. multiple
+     different zeroes, for different types); these are just for the last
+     constant added.  */
+  tree m_constant;
+  svalue_id m_cst_sid;
+
+  // TODO: should this be a set rather than a vec?
+  auto_vec<svalue_id> m_vars;
+};
+
+/* The various kinds of constraint.  */
+
+enum constraint_op
+{
+  CONSTRAINT_NE,
+  CONSTRAINT_LT,
+  CONSTRAINT_LE
+};
+
+const char *constraint_op_code (enum constraint_op c_op);
+
+/* An ID for an equiv_class within a constraint_manager.  Internally, this
+   is an index into a vector of equiv_class * within the constraint_manager.  */
+
+class equiv_class_id
+{
+public:
+  static equiv_class_id null () { return equiv_class_id (-1); }
+
+  equiv_class_id (unsigned idx) : m_idx (idx) {}
+  const equiv_class &get_obj (const constraint_manager &cm) const;
+  equiv_class &get_obj (constraint_manager &cm) const;
+
+  bool operator== (const equiv_class_id &other) const
+  {
+    return m_idx == other.m_idx;
+  }
+  bool operator!= (const equiv_class_id &other) const
+  {
+    return m_idx != other.m_idx;
+  }
+
+  bool null_p () const { return m_idx == -1; }
+
+  static equiv_class_id from_int (int idx) { return equiv_class_id (idx); }
+  int as_int () const { return m_idx; }
+
+  void print (pretty_printer *pp) const;
+
+  void update_for_removal (equiv_class_id other)
+  {
+    if (m_idx > other.m_idx)
+      m_idx--;
+  }
+
+  int m_idx;
+};
+
+/* A relationship between two equivalence classes in a constraint_manager.  */
+
+class constraint
+{
+ public:
+  constraint (equiv_class_id lhs, enum constraint_op c_op, equiv_class_id rhs)
+  : m_lhs (lhs), m_op (c_op), m_rhs (rhs)
+  {
+    gcc_assert (!lhs.null_p ());
+    gcc_assert (!rhs.null_p ());
+  }
+
+  void print (pretty_printer *pp, const constraint_manager &cm) const;
+
+  hashval_t hash () const;
+  bool operator== (const constraint &other) const;
+
+  /* Is this an ordering, rather than a "!=".  */
+  bool is_ordering_p () const
+  {
+    return m_op != CONSTRAINT_NE;
+  }
+
+  equiv_class_id m_lhs;
+  enum constraint_op m_op;
+  equiv_class_id m_rhs;
+};
+
+/* An abstract base class for use with constraint_manager::for_each_fact.  */
+
+class fact_visitor
+{
+ public:
+  virtual ~fact_visitor () {}
+  virtual void on_fact (svalue_id lhs, enum tree_code, svalue_id rhs) = 0;
+};
+
+/* A collection of equivalence classes and constraints on them.
+
+   Given N svalues, this can be thought of as representing a subset of
+   N-dimensional space.  When we call add_constraint,
+   we are effectively taking an intersection with that constraint.  */
+
+class constraint_manager
+{
+public:
+  constraint_manager () {}
+  constraint_manager (const constraint_manager &other);
+  virtual ~constraint_manager () {}
+
+  virtual constraint_manager *clone (region_model *) const = 0;
+  virtual tree maybe_get_constant (svalue_id sid) const = 0;
+  virtual svalue_id get_sid_for_constant (tree cst) const = 0;
+  virtual int get_num_svalues () const = 0;
+
+  constraint_manager& operator= (const constraint_manager &other);
+
+  hashval_t hash () const;
+  bool operator== (const constraint_manager &other) const;
+  bool operator!= (const constraint_manager &other) const
+  {
+    return !(*this == other);
+  }
+
+  void print (pretty_printer *pp) const;
+  void dump_to_pp (pretty_printer *pp) const;
+  void dump (FILE *fp) const;
+  void dump () const;
+
+  const equiv_class &get_equiv_class_by_index (unsigned idx) const
+  {
+    return *m_equiv_classes[idx];
+  }
+  equiv_class &get_equiv_class_by_index (unsigned idx)
+  {
+    return *m_equiv_classes[idx];
+  }
+
+  equiv_class &get_equiv_class (svalue_id sid)
+  {
+    equiv_class_id ec_id = get_or_add_equiv_class (sid);
+    return ec_id.get_obj (*this);
+  }
+
+  bool add_constraint (svalue_id lhs, enum tree_code op, svalue_id rhs);
+
+  bool add_constraint (equiv_class_id lhs_ec_id,
+		       enum tree_code op,
+		       equiv_class_id rhs_ec_id);
+
+  bool get_equiv_class_by_sid (svalue_id sid, equiv_class_id *out) const;
+  equiv_class_id get_or_add_equiv_class (svalue_id sid);
+  tristate eval_condition (equiv_class_id lhs,
+			   enum tree_code op,
+			   equiv_class_id rhs);
+  tristate eval_condition (svalue_id lhs,
+			   enum tree_code op,
+			   svalue_id rhs);
+
+  void purge (const purge_criteria &p, purge_stats *stats);
+
+  void remap_svalue_ids (const svalue_id_map &map);
+
+  void canonicalize (unsigned num_svalue_ids);
+
+  static void merge (const constraint_manager &cm_a,
+		     const constraint_manager &cm_b,
+		     constraint_manager *out,
+		     const model_merger &merger);
+
+  void for_each_fact (fact_visitor *) const;
+
+  void validate () const;
+
+  auto_delete_vec<equiv_class> m_equiv_classes;
+  auto_vec<constraint> m_constraints;
+
+ private:
+  static void clean_merger_input (const constraint_manager &cm_in,
+				  const one_way_svalue_id_map &map_sid_to_m,
+				  constraint_manager *out);
+
+  void add_constraint_internal (equiv_class_id lhs_id,
+				enum constraint_op c_op,
+				equiv_class_id rhs_id);
+};
+
+#endif /* GCC_ANALYZER_CONSTRAINT_MANAGER_H */