diff mbox

[PR,lto/66752] Fix missed FSM jump thread

Message ID 55B15321.4040003@redhat.com
State New
Headers show

Commit Message

Jeff Law July 23, 2015, 8:48 p.m. UTC
This patch gives the FSM jump threading code the opportunity to find 
known values when we have a condition like (x != 0).  Previously it just 
allowed naked SSA_NAMES (which is what appears in a SWITCH_EXPR).  This 
patch allows us to thread a COND_EXPR.

Basically given (x != 0), we just ask the FSM bits to do their thing on 
(x) and the right things just happen.

This exposed two bugs.

First, if the FSM bits thread a gimple conditional, they need to make 
sure to clean up the edge flags on the sole remaining edge.  One of the 
new tests checks this (triggered a checking failure because of the 
lingering edge flags).

Second, when building up the FSM path, we failed to check the partial 
path against nodes we'd already visited and add the nodes from the 
partial path to the list of nodes we had visited.  This can result in 
the same node appearing multiple times in a path (reached from different 
preds in fact).  That triggered another failure which is tested by one 
of the new tests.

Of course I'm also including a test for pr 66752's missed optimization :-0

Bootstrapped and regression tested on x86_64-unknown-linux.  Installed 
on the trunk.

Jeff
diff mbox

Patch

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 93647bb..26f93fb 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,15 @@ 
+2015-01-12  Jeff Law  <law@redhat.com>
+
+	PR lto/66752
+	* tree-ssa-threadedge.c (simplify_conrol_stmt_condition): If we are
+	unable to find X NE 0 in the tables, return X as the simplified
+	condition.
+	(fsm_find_control_statement_thread_paths): If nodes in NEXT_PATH are
+	in VISISTED_BBS, then return failure.  Else add nodes from NEXT_PATH
+	to VISISTED_BBS.  */
+	* tree-ssa-threadupdate.c (duplicate_thread_path): Fix up edge flags
+	after removing the control flow statement and unnecessary edges.
+
 2015-07-23  Bernd Edlinger  <bernd.edlinger@hotmail.de>
 
 	* tree-pass.h (get_current_pass_name): Removed.
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index 6bbc2e6..d8742d3 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,3 +1,10 @@ 
+2015-07-23  Jeff Law  <law@redhat.com>
+
+	PR lto/66752
+	* gcc.dg/tree-ssa/pr66752-2.c: New test.
+	* gcc.dg/torture/pr66752-1.c: New test
+	* g++.dg/torture/pr66752-2.C: New test.
+
 2015-07-23  Marek Polacek  <polacek@redhat.com>
 
 	PR c++/66572
diff --git a/gcc/testsuite/g++.dg/torture/pr66752-2.C b/gcc/testsuite/g++.dg/torture/pr66752-2.C
new file mode 100644
index 0000000..96d3fe9
--- /dev/null
+++ b/gcc/testsuite/g++.dg/torture/pr66752-2.C
@@ -0,0 +1,60 @@ 
+/* { dg-do compile } */
+extern "C"
+{
+  typedef struct _IO_FILE FILE;
+  extern int fprintf (FILE * __restrict __stream,
+		      const char *__restrict __format, ...);
+}
+typedef union tree_node *tree;
+class ipa_polymorphic_call_context
+{
+};
+class ipcp_value_base
+{
+};
+template < typename valtype > class ipcp_value:public ipcp_value_base
+{
+public:valtype value;
+  ipcp_value *next;
+};
+
+template < typename valtype > class ipcp_lattice
+{
+public:ipcp_value < valtype > *values;
+  void print (FILE * f, bool dump_sources, bool dump_benefits);
+};
+
+class ipcp_param_lattices
+{
+public:ipcp_lattice < tree > itself;
+  ipcp_lattice < ipa_polymorphic_call_context > ctxlat;
+};
+template < typename valtype > void ipcp_lattice < valtype >::print (FILE * f,
+								    bool
+								    dump_sources,
+								    bool
+								    dump_benefits)
+{
+  ipcp_value < valtype > *val;
+  bool prev = false;
+  for (val = values; val; val = val->next)
+    {
+      if (dump_benefits && prev)
+	fprintf (f, "               ");
+      else if (!dump_benefits && prev)
+	fprintf (f, ", ");
+      else
+	prev = true;
+      if (dump_sources)
+	fprintf (f, "]");
+      if (dump_benefits)
+	fprintf (f, "shit");
+    }
+}
+
+void
+print_all_lattices (FILE * f, bool dump_sources, bool dump_benefits)
+{
+  struct ipcp_param_lattices *plats;
+  plats->ctxlat.print (f, dump_sources, dump_benefits);
+}
diff --git a/gcc/testsuite/gcc.dg/torture/pr66752-1.c b/gcc/testsuite/gcc.dg/torture/pr66752-1.c
new file mode 100644
index 0000000..a742555
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/torture/pr66752-1.c
@@ -0,0 +1,27 @@ 
+/* { dg-do compile } */
+
+typedef unsigned int size_t;
+struct fde_vector
+{
+  size_t count;
+  const struct dwarf_fde *array[];
+};
+struct object;
+typedef struct dwarf_fde fde;
+typedef int (*fde_compare_t) (struct object *, const fde *, const fde *);
+void
+fde_merge (struct object *ob, fde_compare_t fde_compare,
+	   struct fde_vector *v1, struct fde_vector *v2)
+{
+  size_t i1, i2;
+  const fde *fde2;
+  do
+    {
+      i2--;
+      while (i1 > 0 && fde_compare (ob, v1->array[i1 - 1], fde2) > 0)
+	{
+	  i1--;
+	}
+    }
+  while (i2 > 0);
+}
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr66752-3.c b/gcc/testsuite/gcc.dg/tree-ssa/pr66752-3.c
new file mode 100644
index 0000000..f15b598
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr66752-3.c
@@ -0,0 +1,39 @@ 
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-dom1-details -fdump-tree-optimized" } */
+
+extern int status, pt;
+extern int count;
+void
+foo (int N, int c, int b, int *a)
+{
+  int i, flag;
+  i = b -1;
+  flag = 1;
+  if (status && i < N && a[i] == b) {
+    N--;
+    flag = 0;
+   if (pt)
+     count++;
+  }
+  else    
+    for (i = -1, flag = 1; ++i < N && flag;)
+      if (a[i] == b)
+        {
+          --N;
+          flag = 0;
+          if (i < N)
+            a[i] = a[N];
+           else
+            a[i] = 0;
+          if (pt)
+            count++;
+        }
+ if(status && flag)
+   pt--;
+}
+
+/* There are 3 FSM jump threading opportunities.  */
+/* { dg-final { scan-tree-dump-times "FSM" 3 "dom1"} } */
+
+/* There should be no assignments or references to FLAG.  */
+/* { dg-final { scan-tree-dump-not "flag" "optimized"} } */
diff --git a/gcc/tree-ssa-threadedge.c b/gcc/tree-ssa-threadedge.c
index 7164122..5228951 100644
--- a/gcc/tree-ssa-threadedge.c
+++ b/gcc/tree-ssa-threadedge.c
@@ -553,6 +553,16 @@  simplify_control_stmt_condition (edge e,
           || !is_gimple_min_invariant (cached_lhs))
         cached_lhs = (*simplify) (dummy_cond, stmt);
 
+      /* If we were just testing that an integral type was != 0, and that
+	 failed, just return the first operand.  This gives the FSM code a
+	 chance to optimize the path.  */
+      if (cached_lhs == NULL
+	  && cond_code == NE_EXPR
+	  && INTEGRAL_TYPE_P (TREE_TYPE (op0))
+	  && TREE_CODE (op0) == SSA_NAME
+	  && integer_zerop (op1))
+	return op0;
+
       return cached_lhs;
     }
 
@@ -974,6 +984,21 @@  fsm_find_control_statement_thread_paths (tree expr,
 	  return;
 	}
 
+      /* Make sure we haven't already visited any of the nodes in
+ 	 NEXT_PATH.  Don't add them here to avoid pollution.  */
+      for (unsigned int i = 0; i < next_path->length () - 1; i++)
+	{
+	  if (visited_bbs->contains ((*next_path)[i]))
+	    {
+	      vec_free (next_path);
+	      return;
+	    }
+	}
+
+      /* Now add the nodes to VISISTED_BBS.  */
+      for (unsigned int i = 0; i < next_path->length () - 1; i++)
+	visited_bbs->add ((*next_path)[i]);
+
       /* Append all the nodes from NEXT_PATH to PATH.  */
       vec_safe_splice (path, next_path);
       next_path_length = next_path->length ();
diff --git a/gcc/tree-ssa-threadupdate.c b/gcc/tree-ssa-threadupdate.c
index 31ddf25..62937b4 100644
--- a/gcc/tree-ssa-threadupdate.c
+++ b/gcc/tree-ssa-threadupdate.c
@@ -2480,6 +2480,12 @@  duplicate_thread_path (edge entry, edge exit,
 
   /* Remove the last branch in the jump thread path.  */
   remove_ctrl_stmt_and_useless_edges (region_copy[n_region - 1], exit->dest);
+
+  /* And fixup the flags on the single remaining edge.  */
+  edge fix_e = find_edge (region_copy[n_region - 1], exit->dest);
+  fix_e->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE | EDGE_ABNORMAL);
+  fix_e->flags |= EDGE_FALLTHRU;
+
   edge e = make_edge (region_copy[n_region - 1], exit->dest, EDGE_FALLTHRU);
 
   if (e) {