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>

13 files changed, 640 insertions, 3 deletions

diff --git a/gcc/analyzer/analyzer.cc b/gcc/analyzer/analyzer.cc
index b845b86..5578877 100644
--- a/gcc/analyzer/analyzer.cc
+++ b/gcc/analyzer/analyzer.cc
@@ -131,6 +131,7 @@ maybe_reconstruct_from_def_stmt (tree ssa_name,
     {
     default:
       gcc_unreachable ();
+    case GIMPLE_ASM:
     case GIMPLE_NOP:
     case GIMPLE_PHI:
       /* Can't handle these.  */
diff --git a/gcc/analyzer/analyzer.h b/gcc/analyzer/analyzer.h
index 8de5d60..896b350 100644
--- a/gcc/analyzer/analyzer.h
+++ b/gcc/analyzer/analyzer.h
@@ -53,6 +53,7 @@ class svalue;
   class widening_svalue;
   class compound_svalue;
   class conjured_svalue;
+  class asm_output_svalue;
 typedef hash_set<const svalue *> svalue_set;
 class region;
   class frame_region;
@@ -77,6 +78,7 @@ class call_details;
 struct rejected_constraint;
 class constraint_manager;
 class equiv_class;
+class reachable_regions;
 
 class pending_diagnostic;
 class state_change_event;
diff --git a/gcc/analyzer/complexity.cc b/gcc/analyzer/complexity.cc
index ece4272..ae9f982 100644
--- a/gcc/analyzer/complexity.cc
+++ b/gcc/analyzer/complexity.cc
@@ -90,6 +90,22 @@ complexity::from_pair (const complexity &c1, const complexity &c2)
 		     MAX (c1.m_max_depth, c2.m_max_depth) + 1);
 }
 
+/* Get complexity for a new node that references the svalues in VEC.  */
+
+complexity
+complexity::from_vec_svalue (const vec<const svalue *> &vec)
+{
+  unsigned num_nodes = 0;
+  unsigned max_depth = 0;
+  for (auto iter_sval : vec)
+    {
+      const complexity &iter_c = iter_sval->get_complexity ();
+      num_nodes += iter_c.m_num_nodes;
+      max_depth = MAX (max_depth, iter_c.m_max_depth);
+    }
+  return complexity (num_nodes + 1, max_depth + 1);
+}
+
 } // namespace ana
 
 #endif /* #if ENABLE_ANALYZER */
diff --git a/gcc/analyzer/complexity.h b/gcc/analyzer/complexity.h
index 459987e..85c0372 100644
--- a/gcc/analyzer/complexity.h
+++ b/gcc/analyzer/complexity.h
@@ -36,6 +36,7 @@ struct complexity
   complexity (const region *reg);
   complexity (const svalue *sval);
   static complexity from_pair (const complexity &c1, const complexity &c);
+  static complexity from_vec_svalue (const vec<const svalue *> &vec);
 
   /* The total number of svalues and regions in the tree of this
      entity, including the entity itself.  */
diff --git a/gcc/analyzer/engine.cc b/gcc/analyzer/engine.cc
index ee625fb..ecd4265 100644
--- a/gcc/analyzer/engine.cc
+++ b/gcc/analyzer/engine.cc
@@ -3718,6 +3718,8 @@ feasibility_state::maybe_update_for_edge (logger *logger,
 
       if (const gassign *assign = dyn_cast <const gassign *> (stmt))
 	m_model.on_assignment (assign, NULL);
+      else if (const gasm *asm_stmt = dyn_cast <const gasm *> (stmt))
+	m_model.on_asm_stmt (asm_stmt, NULL);
       else if (const gcall *call = dyn_cast <const gcall *> (stmt))
 	{
 	  bool terminate_path;
diff --git a/gcc/analyzer/region-model-asm.cc b/gcc/analyzer/region-model-asm.cc
new file mode 100644
index 0000000..3efc3fd
--- /dev/null
+++ b/gcc/analyzer/region-model-asm.cc
@@ -0,0 +1,303 @@
+/* Handling inline asm in the analyzer.
+   Copyright (C) 2021 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/>.  */
+
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "tree.h"
+#include "function.h"
+#include "basic-block.h"
+#include "gimple.h"
+#include "gimple-iterator.h"
+#include "diagnostic-core.h"
+#include "pretty-print.h"
+#include "tristate.h"
+#include "selftest.h"
+#include "json.h"
+#include "analyzer/analyzer.h"
+#include "analyzer/analyzer-logging.h"
+#include "options.h"
+#include "analyzer/call-string.h"
+#include "analyzer/program-point.h"
+#include "analyzer/store.h"
+#include "analyzer/region-model.h"
+#include "analyzer/region-model-reachability.h"
+#include "stmt.h"
+
+#if ENABLE_ANALYZER
+
+namespace ana {
+
+/* Minimal asm support for the analyzer.
+
+   The objective of this code is to:
+   - minimize false positives from the analyzer on the Linux kernel
+   (which makes heavy use of inline asm), whilst
+   - avoiding having to "teach" the compiler anything about specific strings
+   in asm statements.
+
+   Specifically, we want to:
+
+   (a) mark asm outputs and certain other regions as having been written to,
+       to avoid false postives from -Wanalyzer-use-of-uninitialized-value.
+
+   (b) identify some of these stmts as "deterministic" so that we can
+       write consistent outputs given consistent inputs, so that we can
+       avoid false positives for paths in which an asm is invoked twice
+       with the same inputs and is expected to emit the same output.
+
+   This file implements heuristics for achieving the above.  */
+
+/* Determine if ASM_STMT is deterministic, in the sense of (b) above.
+
+   Consider this x86 function taken from the Linux kernel
+   (arch/x86/include/asm/barrier.h):
+
+     static inline unsigned long array_index_mask_nospec(unsigned long index,
+							 unsigned long size)
+     {
+       unsigned long mask;
+
+       asm volatile ("cmp %1,%2; sbb %0,%0;"
+		     :"=r" (mask)
+		     :"g"(size),"r" (index)
+		     :"cc");
+       return mask;
+     }
+
+   The above is a mitigation for Spectre-variant-1 attacks, for clamping
+   an array access to within the range of [0, size] if the CPU speculates
+   past the array bounds.
+
+   However, it is ultimately used to implement wdev_to_wvif:
+
+     static inline struct wfx_vif *
+     wdev_to_wvif(struct wfx_dev *wdev, int vif_id)
+     {
+       vif_id = array_index_nospec(vif_id, ARRAY_SIZE(wdev->vif));
+       if (!wdev->vif[vif_id]) {
+	 return NULL;
+       }
+       return (struct wfx_vif *)wdev->vif[vif_id]->drv_priv;
+     }
+
+   which is used by:
+
+     if (wdev_to_wvif(wvif->wdev, 1))
+       return wdev_to_wvif(wvif->wdev, 1)->vif;
+
+   The code has been written to assume that wdev_to_wvif is deterministic,
+   and won't change from returning non-NULL at the "if" clause to
+   returning NULL at the "->vif" dereference.
+
+   By treating the above specific "asm volatile" as deterministic we avoid
+   a false positive from -Wanalyzer-null-dereference.  */
+
+static bool
+deterministic_p (const gasm *asm_stmt)
+{
+  /* Assume something volatile with no inputs is querying
+     changeable state e.g. rdtsc.  */
+  if (gimple_asm_ninputs (asm_stmt) == 0
+      && gimple_asm_volatile_p (asm_stmt))
+    return false;
+
+  /* Otherwise assume it's purely a function of its inputs.  */
+  return true;
+}
+
+/* Update this model for the asm STMT, using CTXT to report any
+   diagnostics.
+
+   Compare with cfgexpand.c: expand_asm_stmt.  */
+
+void
+region_model::on_asm_stmt (const gasm *stmt, region_model_context *ctxt)
+{
+  logger *logger = ctxt ? ctxt->get_logger () : NULL;
+  LOG_SCOPE (logger);
+
+  const unsigned noutputs = gimple_asm_noutputs (stmt);
+  const unsigned ninputs = gimple_asm_ninputs (stmt);
+
+  auto_vec<tree> output_tvec;
+  auto_vec<tree> input_tvec;
+  auto_vec<const char *> constraints;
+
+  /* Copy the gimple vectors into new vectors that we can manipulate.  */
+  output_tvec.safe_grow (noutputs, true);
+  input_tvec.safe_grow (ninputs, true);
+  constraints.safe_grow (noutputs + ninputs, true);
+
+  for (unsigned i = 0; i < noutputs; ++i)
+    {
+      tree t = gimple_asm_output_op (stmt, i);
+      output_tvec[i] = TREE_VALUE (t);
+      constraints[i] = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (t)));
+    }
+  for (unsigned i = 0; i < ninputs; i++)
+    {
+      tree t = gimple_asm_input_op (stmt, i);
+      input_tvec[i] = TREE_VALUE (t);
+      constraints[i + noutputs]
+	= TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (t)));
+    }
+
+  /* Determine which regions are reachable from the inputs
+     to this stmt.  */
+  reachable_regions reachable_regs (this);
+
+  int num_errors = 0;
+
+  auto_vec<const region *> output_regions (noutputs);
+  for (unsigned i = 0; i < noutputs; ++i)
+    {
+      tree val = output_tvec[i];
+      const char *constraint;
+      bool is_inout;
+      bool allows_reg;
+      bool allows_mem;
+
+      const region *dst_reg = get_lvalue (val, ctxt);
+      output_regions.quick_push (dst_reg);
+      reachable_regs.add (dst_reg, true);
+
+      /* Try to parse the output constraint.  If that fails, there's
+	 no point in going further.  */
+      constraint = constraints[i];
+      if (!parse_output_constraint (&constraint, i, ninputs, noutputs,
+				    &allows_mem, &allows_reg, &is_inout))
+	{
+	  if (logger)
+	    logger->log ("error parsing constraint for output %i: %qs",
+			 i, constraint);
+	  num_errors++;
+	  continue;
+	}
+
+      if (logger)
+	{
+	  logger->log ("output %i: %qs %qE"
+		       " is_inout: %i allows_reg: %i allows_mem: %i",
+		       i, constraint, val,
+		       (int)is_inout, (int)allows_reg, (int)allows_mem);
+	  logger->start_log_line ();
+	  logger->log_partial ("  region: ");
+	  dst_reg->dump_to_pp (logger->get_printer (), true);
+	  logger->end_log_line ();
+	}
+
+    }
+
+  /* Ideally should combine with inout_svals to determine the
+     "effective inputs" and use this for the asm_output_svalue.  */
+
+  auto_vec<const svalue *> input_svals (ninputs);
+  for (unsigned i = 0; i < ninputs; i++)
+    {
+      tree val = input_tvec[i];
+      const char *constraint = constraints[i + noutputs];
+      bool allows_reg, allows_mem;
+      if (! parse_input_constraint (&constraint, i, ninputs, noutputs, 0,
+				    constraints.address (),
+				    &allows_mem, &allows_reg))
+	{
+	  if (logger)
+	    logger->log ("error parsing constraint for input %i: %qs",
+			 i, constraint);
+	  num_errors++;
+	  continue;
+	}
+
+      tree src_expr = input_tvec[i];
+      const svalue *src_sval = get_rvalue (src_expr, ctxt);
+      check_for_poison (src_sval, src_expr, ctxt);
+      input_svals.quick_push (src_sval);
+      reachable_regs.handle_sval (src_sval);
+
+      if (logger)
+	{
+	  logger->log ("input %i: %qs %qE"
+		       " allows_reg: %i allows_mem: %i",
+		       i, constraint, val,
+		       (int)allows_reg, (int)allows_mem);
+	  logger->start_log_line ();
+	  logger->log_partial ("  sval: ");
+	  src_sval->dump_to_pp (logger->get_printer (), true);
+	  logger->end_log_line ();
+	}
+    }
+
+  if (num_errors > 0)
+    gcc_unreachable ();
+
+  if (logger)
+    {
+      logger->log ("reachability: ");
+      reachable_regs.dump_to_pp (logger->get_printer ());
+      logger->end_log_line ();
+    }
+
+  /* Given the regions that were reachable from the inputs we
+     want to clobber them.
+     This is similar to region_model::handle_unrecognized_call,
+     but the unknown call policies seems too aggressive (e.g. purging state
+     from anything that's ever escaped).  Instead, clobber any clusters
+     that were reachable in *this* asm stmt, rather than those that
+     escaped, and we don't treat the values as having escaped.
+     We also assume that asm stmts don't affect sm-state.  */
+  for (auto iter = reachable_regs.begin_mutable_base_regs ();
+       iter != reachable_regs.end_mutable_base_regs (); ++iter)
+    {
+      const region *base_reg = *iter;
+      if (base_reg->symbolic_for_unknown_ptr_p ())
+	continue;
+
+      binding_cluster *cluster = m_store.get_or_create_cluster (base_reg);
+      cluster->on_asm (stmt, m_mgr->get_store_manager ());
+    }
+
+  /* Update the outputs.  */
+  for (unsigned output_idx = 0; output_idx < noutputs; output_idx++)
+    {
+      tree dst_expr = output_tvec[output_idx];
+      const region *dst_reg = output_regions[output_idx];
+
+      const svalue *sval;
+      if (deterministic_p (stmt)
+	  && input_svals.length () <= asm_output_svalue::MAX_INPUTS)
+	sval = m_mgr->get_or_create_asm_output_svalue (TREE_TYPE (dst_expr),
+						       stmt,
+						       output_idx,
+						       input_svals);
+      else
+	{
+	  sval = m_mgr->get_or_create_conjured_svalue (TREE_TYPE (dst_expr),
+						       stmt,
+						       dst_reg);
+	  purge_state_involving (sval, ctxt);
+	}
+      set_value (dst_reg, sval, ctxt);
+    }
+}
+
+} // namespace ana
+
+#endif /* #if ENABLE_ANALYZER */
diff --git a/gcc/analyzer/region-model-manager.cc b/gcc/analyzer/region-model-manager.cc
index 14c57d8..9e4644f 100644
--- a/gcc/analyzer/region-model-manager.cc
+++ b/gcc/analyzer/region-model-manager.cc
@@ -1087,6 +1087,51 @@ region_model_manager::get_or_create_conjured_svalue (tree type,
   return conjured_sval;
 }
 
+/* Subroutine of region_model_manager::get_or_create_asm_output_svalue.
+   Return a folded svalue, or NULL.  */
+
+const svalue *
+region_model_manager::
+maybe_fold_asm_output_svalue (tree type,
+			      const vec<const svalue *> &inputs)
+{
+  /* Unknown inputs should lead to unknown results.  */
+  for (const auto &iter : inputs)
+    if (iter->get_kind () == SK_UNKNOWN)
+      return get_or_create_unknown_svalue (type);
+
+  return NULL;
+}
+
+/* Return the svalue * of type TYPE for OUTPUT_IDX of the deterministic
+   asm stmt ASM_STMT, given INPUTS as inputs.  */
+
+const svalue *
+region_model_manager::
+get_or_create_asm_output_svalue (tree type,
+				 const gasm *asm_stmt,
+				 unsigned output_idx,
+				 const vec<const svalue *> &inputs)
+{
+  gcc_assert (inputs.length () <= asm_output_svalue::MAX_INPUTS);
+
+  if (const svalue *folded
+	= maybe_fold_asm_output_svalue (type, inputs))
+    return folded;
+
+  const char *asm_string = gimple_asm_string (asm_stmt);
+  const unsigned noutputs = gimple_asm_noutputs (asm_stmt);
+
+  asm_output_svalue::key_t key (type, asm_string, output_idx, inputs);
+  if (asm_output_svalue **slot = m_asm_output_values_map.get (key))
+    return *slot;
+  asm_output_svalue *asm_output_sval
+    = new asm_output_svalue (type, asm_string, output_idx, noutputs, inputs);
+  RETURN_UNKNOWN_IF_TOO_COMPLEX (asm_output_sval);
+  m_asm_output_values_map.put (key, asm_output_sval);
+  return asm_output_sval;
+}
+
 /* Given STRING_CST, a STRING_CST and BYTE_OFFSET_CST a constant,
    attempt to get the character at that offset, returning either
    the svalue for the character constant, or NULL if unsuccessful.  */
@@ -1505,6 +1550,9 @@ region_model_manager::log_stats (logger *logger, bool show_objs) const
   log_uniq_map (logger, show_objs, "widening_svalue", m_widening_values_map);
   log_uniq_map (logger, show_objs, "compound_svalue", m_compound_values_map);
   log_uniq_map (logger, show_objs, "conjured_svalue", m_conjured_values_map);
+  log_uniq_map (logger, show_objs, "asm_output_svalue",
+		m_asm_output_values_map);
+
   logger->log ("max accepted svalue num_nodes: %i",
 	       m_max_complexity.m_num_nodes);
   logger->log ("max accepted svalue max_depth: %i",
diff --git a/gcc/analyzer/region-model.cc b/gcc/analyzer/region-model.cc
index 1bc411b..58da7e3 100644
--- a/gcc/analyzer/region-model.cc
+++ b/gcc/analyzer/region-model.cc
@@ -980,7 +980,10 @@ region_model::on_stmt_pre (const gimple *stmt,
       break;
 
     case GIMPLE_ASM:
-      /* No-op for now.  */
+      {
+	const gasm *asm_stmt = as_a <const gasm *> (stmt);
+	on_asm_stmt (asm_stmt, ctxt);
+      }
       break;
 
     case GIMPLE_CALL:
diff --git a/gcc/analyzer/region-model.h b/gcc/analyzer/region-model.h
index d07ce9c..30f02a0 100644
--- a/gcc/analyzer/region-model.h
+++ b/gcc/analyzer/region-model.h
@@ -221,6 +221,7 @@ public:
   virtual void visit_widening_svalue (const widening_svalue *) {}
   virtual void visit_compound_svalue (const compound_svalue *) {}
   virtual void visit_conjured_svalue (const conjured_svalue *) {}
+  virtual void visit_asm_output_svalue (const asm_output_svalue *) {}
 
   virtual void visit_region (const region *) {}
 };
@@ -274,6 +275,11 @@ public:
 					       const binding_map &map);
   const svalue *get_or_create_conjured_svalue (tree type, const gimple *stmt,
 					       const region *id_reg);
+  const svalue *
+  get_or_create_asm_output_svalue (tree type,
+				   const gasm *asm_stmt,
+				   unsigned output_idx,
+				   const vec<const svalue *> &inputs);
 
   const svalue *maybe_get_char_from_string_cst (tree string_cst,
 						tree byte_offset_cst);
@@ -346,6 +352,8 @@ private:
   const svalue *maybe_undo_optimize_bit_field_compare (tree type,
 						       const compound_svalue *compound_sval,
 						       tree cst, const svalue *arg1);
+  const svalue *maybe_fold_asm_output_svalue (tree type,
+					      const vec<const svalue *> &inputs);
 
   unsigned m_next_region_id;
   root_region m_root_region;
@@ -410,6 +418,10 @@ private:
 		   conjured_svalue *> conjured_values_map_t;
   conjured_values_map_t m_conjured_values_map;
 
+  typedef hash_map<asm_output_svalue::key_t,
+		   asm_output_svalue *> asm_output_values_map_t;
+  asm_output_values_map_t m_asm_output_values_map;
+
   bool m_check_complexity;
 
   /* Maximum complexity of svalues that weren't rejected.  */
@@ -537,6 +549,7 @@ class region_model
   void on_assignment (const gassign *stmt, region_model_context *ctxt);
   const svalue *get_gassign_result (const gassign *assign,
 				    region_model_context *ctxt);
+  void on_asm_stmt (const gasm *asm_stmt, region_model_context *ctxt);
   bool on_call_pre (const gcall *stmt, region_model_context *ctxt,
 		    bool *out_terminate_path);
   void on_call_post (const gcall *stmt,
diff --git a/gcc/analyzer/store.cc b/gcc/analyzer/store.cc
index 8ee414d..eac1295 100644
--- a/gcc/analyzer/store.cc
+++ b/gcc/analyzer/store.cc
@@ -1796,6 +1796,23 @@ binding_cluster::on_unknown_fncall (const gcall *call,
     }
 }
 
+/* Mark this cluster as having been clobbered by STMT.  */
+
+void
+binding_cluster::on_asm (const gasm *stmt,
+			 store_manager *mgr)
+{
+  m_map.empty ();
+
+  /* Bind it to a new "conjured" value using CALL.  */
+  const svalue *sval
+    = mgr->get_svalue_manager ()->get_or_create_conjured_svalue
+    (m_base_region->get_type (), stmt, m_base_region);
+  bind (mgr, m_base_region, sval);
+
+  m_touched = true;
+}
+
 /* Return true if this binding_cluster has no information
    i.e. if there are no bindings, and it hasn't been marked as having
    escaped, or touched symbolically.  */
diff --git a/gcc/analyzer/store.h b/gcc/analyzer/store.h
index bc58694..b75691e 100644
--- a/gcc/analyzer/store.h
+++ b/gcc/analyzer/store.h
@@ -603,6 +603,7 @@ public:
 
   void mark_as_escaped ();
   void on_unknown_fncall (const gcall *call, store_manager *mgr);
+  void on_asm (const gasm *stmt, store_manager *mgr);
 
   bool escaped_p () const { return m_escaped; }
   bool touched_p () const { return m_touched; }
diff --git a/gcc/analyzer/svalue.cc b/gcc/analyzer/svalue.cc
index a1e6f50..6913161 100644
--- a/gcc/analyzer/svalue.cc
+++ b/gcc/analyzer/svalue.cc
@@ -508,6 +508,29 @@ svalue::cmp_ptr (const svalue *sval1, const svalue *sval2)
 				conjured_sval2->get_id_region ());
       }
       break;
+    case SK_ASM_OUTPUT:
+      {
+	const asm_output_svalue *asm_output_sval1
+	  = (const asm_output_svalue *)sval1;
+	const asm_output_svalue *asm_output_sval2
+	  = (const asm_output_svalue *)sval2;
+	if (int asm_string_cmp = strcmp (asm_output_sval1->get_asm_string (),
+					 asm_output_sval2->get_asm_string ()))
+	  return asm_string_cmp;
+	if (int output_idx_cmp = ((int)asm_output_sval1->get_output_idx ()
+				  - (int)asm_output_sval2->get_output_idx ()))
+	  return output_idx_cmp;
+	if (int cmp = ((int)asm_output_sval1->get_num_inputs ()
+		       - (int)asm_output_sval2->get_num_inputs ()))
+	  return cmp;
+	for (unsigned i = 0; i < asm_output_sval1->get_num_inputs (); i++)
+	  if (int input_cmp
+	      = svalue::cmp_ptr (asm_output_sval1->get_input (i),
+				 asm_output_sval2->get_input (i)))
+	    return input_cmp;
+	return 0;
+      }
+      break;
     }
 }
 
@@ -1794,6 +1817,72 @@ conjured_svalue::accept (visitor *v) const
   m_id_reg->accept (v);
 }
 
+/* class asm_output_svalue : public svalue.  */
+
+/* Implementation of svalue::dump_to_pp vfunc for asm_output_svalue.  */
+
+void
+asm_output_svalue::dump_to_pp (pretty_printer *pp, bool simple) const
+{
+  if (simple)
+    {
+      pp_printf (pp, "ASM_OUTPUT(%qs, %%%i, {",
+		 get_asm_string (),
+		 get_output_idx ());
+      for (unsigned i = 0; i < m_num_inputs; i++)
+	{
+	  if (i > 0)
+	    pp_string (pp, ", ");
+	  dump_input (pp, 0, m_input_arr[i], simple);
+	}
+      pp_string (pp, "})");
+    }
+  else
+    {
+      pp_printf (pp, "asm_output_svalue (%qs, %%%i, {",
+		 get_asm_string (),
+		 get_output_idx ());
+      for (unsigned i = 0; i < m_num_inputs; i++)
+	{
+	  if (i > 0)
+	    pp_string (pp, ", ");
+	  dump_input (pp, 0, m_input_arr[i], simple);
+	}
+      pp_string (pp, "})");
+    }
+}
+
+/* Subroutine of asm_output_svalue::dump_to_pp.  */
+
+void
+asm_output_svalue::dump_input (pretty_printer *pp,
+			       unsigned input_idx,
+			       const svalue *sval,
+			       bool simple) const
+{
+  pp_printf (pp, "%%%i: ", input_idx_to_asm_idx (input_idx));
+  sval->dump_to_pp (pp, simple);
+}
+
+/* Convert INPUT_IDX from an index into the array of inputs
+   into the index of all operands for the asm stmt.  */
+
+unsigned
+asm_output_svalue::input_idx_to_asm_idx (unsigned input_idx) const
+{
+  return input_idx + m_num_outputs;
+}
+
+/* Implementation of svalue::accept vfunc for asm_output_svalue.  */
+
+void
+asm_output_svalue::accept (visitor *v) const
+{
+  v->visit_asm_output_svalue (this);
+  for (unsigned i = 0; i < m_num_inputs; i++)
+    m_input_arr[i]->accept (v);
+}
+
 } // namespace ana
 
 #endif /* #if ENABLE_ANALYZER */
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 */