analyzer: initial implementation of asm support [PR101570]

gcc/ChangeLog:
	PR analyzer/101570
	* Makefile.in (ANALYZER_OBJS): Add analyzer/region-model-asm.o.

gcc/analyzer/ChangeLog:
	PR analyzer/101570
	* analyzer.cc (maybe_reconstruct_from_def_stmt): Add GIMPLE_ASM
	case.
	* analyzer.h (class asm_output_svalue): New forward decl.
	(class reachable_regions): New forward decl.
	* complexity.cc (complexity::from_vec_svalue): New.
	* complexity.h (complexity::from_vec_svalue): New decl.
	* engine.cc (feasibility_state::maybe_update_for_edge): Handle
	asm stmts by calling on_asm_stmt.
	* region-model-asm.cc: New file.
	* region-model-manager.cc
	(region_model_manager::maybe_fold_asm_output_svalue): New.
	(region_model_manager::get_or_create_asm_output_svalue): New.
	(region_model_manager::log_stats): Log m_asm_output_values_map.
	* region-model.cc (region_model::on_stmt_pre): Handle GIMPLE_ASM.
	* region-model.h (visitor::visit_asm_output_svalue): New.
	(region_model_manager::get_or_create_asm_output_svalue): New decl.
	(region_model_manager::maybe_fold_asm_output_svalue): New decl.
	(region_model_manager::asm_output_values_map_t): New typedef.
	(region_model_manager::m_asm_output_values_map): New field.
	(region_model::on_asm_stmt): New.
	* store.cc (binding_cluster::on_asm): New.
	* store.h (binding_cluster::on_asm): New decl.
	* svalue.cc (svalue::cmp_ptr): Handle SK_ASM_OUTPUT.
	(asm_output_svalue::dump_to_pp): New.
	(asm_output_svalue::dump_input): New.
	(asm_output_svalue::input_idx_to_asm_idx): New.
	(asm_output_svalue::accept): New.
	* svalue.h (enum svalue_kind): Add SK_ASM_OUTPUT.
	(svalue::dyn_cast_asm_output_svalue): New.
	(class asm_output_svalue): New.
	(is_a_helper <const asm_output_svalue *>::test): New.
	(struct default_hash_traits<asm_output_svalue::key_t>): New.

gcc/testsuite/ChangeLog:
	PR analyzer/101570
	* gcc.dg/analyzer/asm-x86-1.c: New test.
	* gcc.dg/analyzer/asm-x86-lp64-1.c: New test.
	* gcc.dg/analyzer/asm-x86-lp64-2.c: New test.
	* gcc.dg/analyzer/pr101570.c: New test.
	* gcc.dg/analyzer/torture/asm-x86-linux-array_index_mask_nospec.c:
	New test.
	* gcc.dg/analyzer/torture/asm-x86-linux-cpuid-paravirt-1.c: New
	test.
	* gcc.dg/analyzer/torture/asm-x86-linux-cpuid-paravirt-2.c: New
	test.
	* gcc.dg/analyzer/torture/asm-x86-linux-cpuid.c: New test.
	* gcc.dg/analyzer/torture/asm-x86-linux-rdmsr-paravirt.c: New
	test.
	* gcc.dg/analyzer/torture/asm-x86-linux-rdmsr.c: New test.
	* gcc.dg/analyzer/torture/asm-x86-linux-wfx_get_ps_timeout-full.c:
	New test.
	* gcc.dg/analyzer/torture/asm-x86-linux-wfx_get_ps_timeout-reduced.c:
	New test.

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

1 files changed, 143 insertions, 2 deletions

diff --git a/gcc/analyzer/svalue.h b/gcc/analyzer/svalue.h
index debe439..63f7d15 100644
--- a/gcc/analyzer/svalue.h
+++ b/gcc/analyzer/svalue.h
@@ -47,7 +47,8 @@ enum svalue_kind
   SK_PLACEHOLDER,
   SK_WIDENING,
   SK_COMPOUND,
-  SK_CONJURED
+  SK_CONJURED,
+  SK_ASM_OUTPUT
 };
 
 /* svalue and its subclasses.
@@ -74,7 +75,9 @@ enum svalue_kind
      widening_svalue (SK_WIDENING): a merger of two svalues (possibly
        in an iteration).
      compound_svalue (SK_COMPOUND): a mapping of bit-ranges to svalues
-     conjured_svalue (SK_CONJURED): a value arising from a stmt.  */
+     conjured_svalue (SK_CONJURED): a value arising from a stmt
+     asm_output_svalue (SK_ASM_OUTPUT): an output from a deterministic
+       asm stmt.  */
 
 /* An abstract base class representing a value held by a region of memory.  */
 
@@ -124,6 +127,8 @@ public:
   dyn_cast_compound_svalue () const { return NULL; }
   virtual const conjured_svalue *
   dyn_cast_conjured_svalue () const { return NULL; }
+  virtual const asm_output_svalue *
+  dyn_cast_asm_output_svalue () const { return NULL; }
 
   tree maybe_get_constant () const;
   const region *maybe_get_region () const;
@@ -1394,4 +1399,140 @@ template <> struct default_hash_traits<conjured_svalue::key_t>
   static const bool empty_zero_p = true;
 };
 
+namespace ana {
+
+/* An output from a deterministic asm stmt, where we want to identify a
+   particular unknown value, rather than resorting to the unknown_value
+   singleton.
+
+   Comparisons of variables that share the same asm_output_svalue are known
+   to be equal, even if we don't know what the value is.  */
+
+class asm_output_svalue : public svalue
+{
+public:
+  /* Imposing an upper limit and using a (small) array allows key_t
+     to avoid memory management.  */
+  static const unsigned MAX_INPUTS = 2;
+
+  /* A support class for uniquifying instances of asm_output_svalue.  */
+  struct key_t
+  {
+    key_t (tree type,
+	   const char *asm_string,
+	   unsigned output_idx,
+	   const vec<const svalue *> &inputs)
+    : m_type (type), m_asm_string (asm_string), m_output_idx (output_idx),
+      m_num_inputs (inputs.length ())
+    {
+      gcc_assert (inputs.length () <= MAX_INPUTS);
+      for (unsigned i = 0; i < m_num_inputs; i++)
+	m_input_arr[i] = inputs[i];
+    }
+
+    hashval_t hash () const
+    {
+      inchash::hash hstate;
+      hstate.add_ptr (m_type);
+      /* We don't bother hashing m_asm_str.  */
+      hstate.add_int (m_output_idx);
+      for (unsigned i = 0; i < m_num_inputs; i++)
+	hstate.add_ptr (m_input_arr[i]);
+      return hstate.end ();
+    }
+
+    bool operator== (const key_t &other) const
+    {
+      if (!(m_type == other.m_type
+	    && 0 == (strcmp (m_asm_string, other.m_asm_string))
+	    && m_output_idx == other.m_output_idx
+	    && m_num_inputs == other.m_num_inputs))
+	return false;
+      for (unsigned i = 0; i < m_num_inputs; i++)
+	if (m_input_arr[i] != other.m_input_arr[i])
+	  return false;
+      return true;
+    }
+
+    /* Use m_asm_string to mark empty/deleted, as m_type can be NULL for
+       legitimate instances.  */
+    void mark_deleted () { m_asm_string = reinterpret_cast<const char *> (1); }
+    void mark_empty () { m_asm_string = NULL; }
+    bool is_deleted () const
+    {
+      return m_asm_string == reinterpret_cast<const char *> (1);
+    }
+    bool is_empty () const { return m_asm_string == NULL; }
+
+    tree m_type;
+    const char *m_asm_string;
+    unsigned m_output_idx;
+    unsigned m_num_inputs;
+    const svalue *m_input_arr[MAX_INPUTS];
+  };
+
+  asm_output_svalue (tree type,
+		     const char *asm_string,
+		     unsigned output_idx,
+		     unsigned num_outputs,
+		     const vec<const svalue *> &inputs)
+  : svalue (complexity::from_vec_svalue (inputs), type),
+    m_asm_string (asm_string),
+    m_output_idx (output_idx),
+    m_num_outputs (num_outputs),
+    m_num_inputs (inputs.length ())
+  {
+    gcc_assert (inputs.length () <= MAX_INPUTS);
+    for (unsigned i = 0; i < m_num_inputs; i++)
+      m_input_arr[i] = inputs[i];
+  }
+
+  enum svalue_kind get_kind () const FINAL OVERRIDE { return SK_ASM_OUTPUT; }
+  const asm_output_svalue *
+  dyn_cast_asm_output_svalue () const FINAL OVERRIDE
+  {
+    return this;
+  }
+
+  void dump_to_pp (pretty_printer *pp, bool simple) const FINAL OVERRIDE;
+  void accept (visitor *v) const FINAL OVERRIDE;
+
+  const char *get_asm_string () const { return m_asm_string; }
+  unsigned get_output_idx () const { return m_output_idx; }
+  unsigned get_num_inputs () const { return m_num_inputs; }
+  const svalue *get_input (unsigned idx) const { return m_input_arr[idx]; }
+
+ private:
+  void dump_input (pretty_printer *pp,
+		   unsigned input_idx,
+		   const svalue *sval,
+		   bool simple) const;
+  unsigned input_idx_to_asm_idx (unsigned input_idx) const;
+
+  const char *m_asm_string;
+  unsigned m_output_idx;
+
+  /* We capture this so that we can offset the input indices
+     to match the %0, %1, %2 in the asm_string when dumping.  */
+  unsigned m_num_outputs;
+
+  unsigned m_num_inputs;
+  const svalue *m_input_arr[MAX_INPUTS];
+};
+
+} // namespace ana
+
+template <>
+template <>
+inline bool
+is_a_helper <const asm_output_svalue *>::test (const svalue *sval)
+{
+  return sval->get_kind () == SK_ASM_OUTPUT;
+}
+
+template <> struct default_hash_traits<asm_output_svalue::key_t>
+: public member_function_hash_traits<asm_output_svalue::key_t>
+{
+  static const bool empty_zero_p = true;
+};
 #endif /* GCC_ANALYZER_SVALUE_H */