Implement intraprocedural dataflow for ipa-modref EAF analyser

diff --git a/gcc/ipa-modref.c b/gcc/ipa-modref.c
index db071d2212f..188c41aeb50 100644
--- a/gcc/ipa-modref.c
+++ b/gcc/ipa-modref.c
@@ -1456,14 +1456,32 @@  class modref_lattice
 public:
   /* EAF flags of the SSA name.  */
   eaf_flags_t flags;
-  /* DFS bookkkeeping: we don't do real dataflow yet.  */
+  /* Used during DFS walk to mark names where final value was determined
+     without need for dataflow.  */
   bool known;
+  /* Used during DFS walk to mark open vertices (for cycle detection).  */
   bool open;
+  /* Set during DFS walk for names that needs dataflow propagation.  */
+  bool do_dataflow;
+  /* Used during the iterative dataflow.  */
+  bool changed;
 
   /* When doing IPA analysis we can not merge in callee escape points;
      Only remember them and do the merging at IPA propagation time.  */
   vec <escape_point, va_heap, vl_ptr> escape_points;
 
+  /* Representation of a graph for dataaflow.  This graph is built on-demand
+     using modref_eaf_analysis::analyze_ssa and later solved by
+     modref_eaf_analysis::propagate.
+     Each edge represents the fact that flags of current lattice should be
+     propagated to lattice of SSA_NAME.  */
+  struct propagate_edge
+  {
+    int ssa_name;
+    bool deref;
+  };
+  vec <propagate_edge, va_heap, vl_ptr> propagate_to;
+
   void init ();
   void release ();
   bool merge (const modref_lattice &with);
@@ -1495,6 +1513,7 @@  void
 modref_lattice::release ()
 {
   escape_points.release ();
+  propagate_to.release ();
 }
 
 /* Dump lattice to OUT; indent with INDENT spaces.  */
@@ -1587,7 +1606,7 @@  bool
 modref_lattice::merge (const modref_lattice &with)
 {
   if (!with.known)
-    return merge (0);
+    do_dataflow = true;
 
   bool changed = merge (with.flags);
 
@@ -1608,7 +1627,7 @@  bool
 modref_lattice::merge_deref (const modref_lattice &with, bool ignore_stores)
 {
   if (!with.known)
-    return merge (0);
+    do_dataflow = true;
 
   bool changed = merge (deref_flags (with.flags, ignore_stores));
 
@@ -1646,13 +1665,24 @@  modref_lattice::merge_direct_store ()
   return merge (~(EAF_UNUSED | EAF_NOCLOBBER));
 }
 
-/* Analyzer of EAF flags.  */
+/* Analyzer of EAF flags.
+   This is genrally dataflow problem over the SSA graph, however we only
+   care about flags of few selected ssa names (arguments, return slot and
+   static chain).  So we first call analyze_ssa_name on all relevant names
+   and perform a DFS walk to discover SSA names where flags needs to be
+   determined.  For acyclic graphs we try to determine final flags during
+   this walk.  Once cycles or recursin depth is met we enlist SSA names
+   for dataflow which is done by propagate call.
+
+   After propagation the flags can be obtained using get_ssa_name_flags.  */
 
 class modref_eaf_analysis
 {
 public:
-  /* Compute flags for NAME.  */
+  /* Mark NAME as relevant for analysis.  */
   void analyze_ssa_name (tree name);
+  /* Dataflow slover.  */
+  void propagate ();
   /* Return flags computed earlier for NAME.  */
   int get_ssa_name_flags (tree name)
   {
@@ -1673,7 +1703,7 @@  public:
   ~modref_eaf_analysis ()
   {
     gcc_checking_assert (!m_depth);
-    if (m_ipa)
+    if (m_ipa || m_names_to_propagate.length ())
       for (unsigned int i = 0; i < num_ssa_names; i++)
 	m_lattice[i].release ();
   }
@@ -1685,6 +1715,8 @@  private:
   int m_depth;
   /* Propagation lattice for individual ssa names.  */
   auto_vec<modref_lattice> m_lattice;
+  auto_vec<tree> m_deferred_names;
+  auto_vec<int> m_names_to_propagate;
 
   void merge_with_ssa_name (tree dest, tree src, bool deref);
   void merge_call_lhs_flags (gcall *call, int arg, tree name, bool deref);
@@ -1773,26 +1805,27 @@  modref_eaf_analysis::analyze_ssa_name (tree name)
   int index = SSA_NAME_VERSION (name);
 
   /* See if value is already computed.  */
-  if (m_lattice[index].known)
+  if (m_lattice[index].known || m_lattice[index].do_dataflow)
    return;
   if (m_lattice[index].open)
     {
       if (dump_file)
 	fprintf (dump_file,
-		 "%*sGiving up on a cycle in SSA graph\n",
+		 "%*sCycle in SSA graph\n",
 		 m_depth * 4, "");
       return;
     }
+  /* Recursion guard.  */
+  m_lattice[index].init ();
   if (m_depth == param_modref_max_depth)
     {
       if (dump_file)
 	fprintf (dump_file,
-		 "%*sGiving up on max depth\n",
+		 "%*sMax recursion depth reached; postponing\n",
 		 m_depth * 4, "");
+      m_deferred_names.safe_push (name);
       return;
     }
-  /* Recursion guard.  */
-  m_lattice[index].init ();
 
   if (dump_file)
     {
@@ -2072,7 +2105,8 @@  modref_eaf_analysis::analyze_ssa_name (tree name)
       m_lattice[index].dump (dump_file, m_depth * 4 + 2);
     }
   m_lattice[index].open = false;
-  m_lattice[index].known = true;
+  if (!m_lattice[index].do_dataflow)
+    m_lattice[index].known = true;
 }
 
 /* Propagate info from SRC to DEST.  If DEREF it true, assume that SRC
@@ -2084,6 +2118,10 @@  modref_eaf_analysis::merge_with_ssa_name (tree dest, tree src, bool deref)
   int index = SSA_NAME_VERSION (dest);
   int src_index = SSA_NAME_VERSION (src);
 
+  /* Merging lattice with itself is a no-op.  */
+  if (!deref && src == dest)
+    return;
+
   m_depth++;
   analyze_ssa_name (src);
   m_depth--;
@@ -2091,6 +2129,157 @@  modref_eaf_analysis::merge_with_ssa_name (tree dest, tree src, bool deref)
     m_lattice[index].merge_deref (m_lattice[src_index], false);
   else
     m_lattice[index].merge (m_lattice[src_index]);
+
+  /* If we failed to produce final solution add an edge to the dataflow
+     graph.  */
+  if (!m_lattice[src_index].known)
+    {
+      modref_lattice::propagate_edge e = {index, deref};
+
+      if (!m_lattice[src_index].propagate_to.length ())
+	m_names_to_propagate.safe_push (src_index);
+      m_lattice[src_index].propagate_to.safe_push (e);
+      m_lattice[src_index].changed = true;
+      m_lattice[src_index].do_dataflow = true;
+      if (dump_file)
+	fprintf (dump_file,
+		 "%*sWill propgate from ssa_name %i to %i%s\n",
+		 m_depth * 4 + 4,
+		 "", src_index, index, deref ? " (deref)" : "");
+    }
+}
+
+/* In the case we deferred some SSA names, reprocess them.  In the case some
+   dataflow edges were introduced, do the actual iterative dataflow.  */
+
+void
+modref_eaf_analysis::propagate ()
+{
+  int iterations = 0;
+  size_t i;
+  int index;
+  bool changed = true;
+
+  while (m_deferred_names.length ())
+    {
+      tree name = m_deferred_names.pop ();
+      m_lattice[SSA_NAME_VERSION (name)].open = false;
+      if (dump_file)
+	fprintf (dump_file, "Analyzing deferred SSA name\n");
+      analyze_ssa_name (name);
+    }
+
+  if (!m_names_to_propagate.length ())
+    return;
+  if (dump_file)
+    fprintf (dump_file, "Propagating EAF flags\n");
+
+  /* Compute reverse postorder.  */
+  auto_vec <int> rpo;
+  struct stack_entry
+  {
+    int name;
+    unsigned pos;
+  };
+  auto_vec <struct stack_entry> stack;
+  int pos = m_names_to_propagate.length () - 1;
+
+  rpo.safe_grow (m_names_to_propagate.length (), true);
+  stack.reserve_exact (m_names_to_propagate.length ());
+
+  /* We reuse known flag for RPO DFS walk bookeeping.  */
+  if (flag_checking)
+    FOR_EACH_VEC_ELT (m_names_to_propagate, i, index)
+      gcc_assert (!m_lattice[index].known && m_lattice[index].changed);
+
+  FOR_EACH_VEC_ELT (m_names_to_propagate, i, index)
+    {
+      if (!m_lattice[index].known)
+	{
+	  stack_entry e = {index, 0};
+
+	  stack.quick_push (e);
+	  m_lattice[index].known = true;
+	}
+      while (stack.length ())
+ 	{
+	  bool found = false;
+	  int index1 = stack.last ().name;
+
+	  while (stack.last ().pos < m_lattice[index1].propagate_to.length ())
+	    {
+	      int index2 = m_lattice[index1]
+		      .propagate_to[stack.last ().pos].ssa_name;
+
+	      stack.last ().pos++;
+	      if (!m_lattice[index2].known
+		  && m_lattice[index2].propagate_to.length ())
+		{
+		  stack_entry e = {index2, 0};
+
+		  stack.quick_push (e);
+		  m_lattice[index2].known = true;
+		  found = true;
+		  break;
+		}
+	    }
+	  if (!found
+	      && stack.last ().pos == m_lattice[index1].propagate_to.length ())
+	    {
+	      rpo[pos--] = index1;
+	      stack.pop ();
+	    }
+	}
+    }
+
+  /* Perform itrative dataflow.  */
+  while (changed)
+    {
+      changed = false;
+      iterations++;
+      if (dump_file)
+	fprintf (dump_file, " iteration %i\n", iterations);
+      FOR_EACH_VEC_ELT (rpo, i, index)
+	{
+	  if (m_lattice[index].changed)
+	    {
+	      size_t j;
+
+	      m_lattice[index].changed = false;
+	      if (dump_file)
+		fprintf (dump_file, "  Visiting ssa name %i\n", index);
+	      for (j = 0; j < m_lattice[index].propagate_to.length (); j++)
+		{
+		  bool ch;
+		  int target = m_lattice[index].propagate_to[j].ssa_name;
+		  bool deref = m_lattice[index].propagate_to[j].deref;
+
+		  if (dump_file)
+		    fprintf (dump_file, "   Propagating flags of ssa name"
+			     " %i to %i%s\n",
+			     index, target, deref ? " (deref)" : "");
+		  m_lattice[target].known = true;
+		  if (!m_lattice[index].propagate_to[j].deref)
+		    ch = m_lattice[target].merge (m_lattice[index]);
+		  else
+		    ch = m_lattice[target].merge_deref (m_lattice[index],
+							false);
+		  if (!ch)
+		    continue;
+		  if (dump_file)
+		    {
+		      fprintf (dump_file, "   New lattice: ");
+		      m_lattice[target].dump (dump_file);
+		    }
+		  if (target <= (int)i)
+		    changed = true;
+		  m_lattice[target].changed = true;
+		}
+	    }
+	}
+    }
+  if (dump_file)
+    fprintf (dump_file, "EAF flags propagated in %i iterations\n", iterations);
 }
 
 /* Record escape points of PARM_INDEX according to LATTICE.  */
@@ -2151,6 +2340,23 @@  analyze_parms (modref_summary *summary, modref_summary_lto *summary_lto,
 
   modref_eaf_analysis eaf_analysis (ipa);
 
+  /* Determine all SSA names we need to know flags for.  */
+  for (tree parm = DECL_ARGUMENTS (current_function_decl); parm;
+       parm = TREE_CHAIN (parm))
+    {
+      tree name = ssa_default_def (cfun, parm);
+      if (name)
+	eaf_analysis.analyze_ssa_name (name);
+    }
+  if (retslot)
+    eaf_analysis.analyze_ssa_name (retslot);
+  if (static_chain)
+    eaf_analysis.analyze_ssa_name (static_chain);
+
+  /* Do the dataflow.  */
+  eaf_analysis.propagate ();
+
+  /* Store results to summaries.  */
   for (tree parm = DECL_ARGUMENTS (current_function_decl); parm; parm_index++,
        parm = TREE_CHAIN (parm))
     {
@@ -2175,7 +2381,6 @@  analyze_parms (modref_summary *summary, modref_summary_lto *summary_lto,
 	    }
 	  continue;
 	}
-      eaf_analysis.analyze_ssa_name (name);
       int flags = eaf_analysis.get_ssa_name_flags (name);
 
       /* Eliminate useless flags so we do not end up storing unnecessary
@@ -2204,7 +2409,6 @@  analyze_parms (modref_summary *summary, modref_summary_lto *summary_lto,
     }
   if (retslot)
     {
-      eaf_analysis.analyze_ssa_name (retslot);
       int flags = eaf_analysis.get_ssa_name_flags (retslot);
 
       flags = remove_useless_eaf_flags (flags, ecf_flags, false);
@@ -2220,7 +2424,6 @@  analyze_parms (modref_summary *summary, modref_summary_lto *summary_lto,
     }
   if (static_chain)
     {
-      eaf_analysis.analyze_ssa_name (static_chain);
       int flags = eaf_analysis.get_ssa_name_flags (static_chain);
 
       flags = remove_useless_eaf_flags (flags, ecf_flags, false);
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/modref-11.c b/gcc/testsuite/gcc.dg/tree-ssa/modref-11.c
new file mode 100644
index 00000000000..de9ad16879f
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/modref-11.c
@@ -0,0 +1,13 @@ 
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-modref1"  } */
+struct linkedlist {
+  struct linkedlist *next;
+};
+struct linkedlist *
+find_last (struct linkedlist *l)
+{
+  while (l->next)
+   l = l->next;
+  return l;
+}
+/* { dg-final { scan-tree-dump "noclobber noescape nodirectescape" "modref1"} } */