[committed][PATCH] Simplify relationals into simple equality conditionals in DOM

[Jeff Law <law at redhat dot com>]

A short while ago Martin Liska posted a patch that lowered certain
switch statements into cascading conditionals.

His work tripped two regressions in the testsuite, both cases where we
did not optimize as well as we should have.

Upon investigation I realized a simple improvement to DOM would fix
things up.  Further testing showed that the situation occurred
reasonably often in practice and that the situation did occur even when
VRP was enabled.

What we want to do is detect cases where we have something like this in
the expression hash table

TRUE = (i <= 1)

And we're presented with the condition we want to optimize like (i >= 1)

The only value of i that satisfies both is i == 1  So we can change the
conditional to (i == 1).

The simplified conditional is useful because it exposes a constant in
one arm of the conditional which we can propagate.  Furthermore the
equality test is easier for tree-ssa-uninit.c to consume.

The implementation is pretty simple.  For  X GE/LE Y we lookup X LE/GE Y
and if we get a hit then we know we can optimize the conditional to X ==
Y.  If Y is a constant, we can handle GT/LT with trivial canonicalization.

The testcase I've added is potentially overly simplistic -- it'll likely
be compromised by work from Aldy or Andrew at some point.   We'll likely
have to reduce a new testcase at that time.

Bootstrapped and regression tested on x86_64.  Also verified the new
test passes on ppc64le.   Installing on the trunk.

Jeff

commit 2cea47f2d18143e46f33eb9a968af0ab1159b1ee
Author: law <law@138bc75d-0d04-0410-961f-82ee72b054a4>
Date:   Sun Oct 1 15:22:39 2017 +0000

            * tree-ssa-dom.c (optimize_stmt): Make this a method within the
            dom_opt_dom_walker class with direct access to private members.
            Add comments.  Call test_for_singularity.
            (dom_opt_dom_walker::before_dom_children): Corresponding changes.
            (dom_opt_dom_walker::after_dom_children): Do not lazily initialize
            m_dummy_cond anymore.
            (class dom_opt_dom_walker): Initialize m_dummy_cond member in the
            class ctor.
            (pass_dominator:execute): Build the dummy_cond here and pass it
            to the dom_opt_dom_walker ctor.
            (test_for_singularity): New function.
    
            * gcc.dg/tree-ssa/ssa-dom-simplify-1.c: New test.
    
    2017-09-30  Paolo Carlini  <paolo.carlini@oracle.com>
    
    git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@253329 138bc75d-0d04-0410-961f-82ee72b054a4

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index d1c3e9fa409..93dcaedbb4a 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,17 @@
+2017-10-01  Jeff Law  <law@redhat.com>
+
+	* tree-ssa-dom.c (optimize_stmt): Make this a method within the
+	dom_opt_dom_walker class with direct access to private members.
+	Add comments.  Call test_for_singularity.
+	(dom_opt_dom_walker::before_dom_children): Corresponding changes.
+	(dom_opt_dom_walker::after_dom_children): Do not lazily initialize
+	m_dummy_cond anymore.
+	(class dom_opt_dom_walker): Initialize m_dummy_cond member in the
+	class ctor.
+	(pass_dominator:execute): Build the dummy_cond here and pass it
+	to the dom_opt_dom_walker ctor. 
+	(test_for_singularity): New function.
+
 2017-09-30  Krister Walfridsson  <krister.walfridsson@gmail.com>
 	    Maya Rashish  <coypu@sdf.org>
 
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index 40f59343fe1..d12fbdd86a5 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,3 +1,7 @@
+2017-10-01  Jeff Law  <law@redhat.com>
+
+	* gcc.dg/tree-ssa/ssa-dom-simplify-1.c: New test.
+
 2017-10-01  Dominique d'Humieres  <dominiq@lps.ens.fr>
 
 	PR fortran/61450
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-simplify-1.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-simplify-1.c
new file mode 100644
index 00000000000..23741b60f65
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-simplify-1.c
@@ -0,0 +1,18 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -w -fdump-tree-dom2" } */
+
+extern void frob (void);
+extern void frob (void);
+
+void
+rhs_to_tree (int x, int z)
+{
+  if (x >= 4)
+    frob ();
+  if (x >= 3)
+    frob ();
+}
+
+/* The second conditional should change into a simple equality test.  */
+/* { dg-final { scan-tree-dump-times "if \\(x_\[0-9\]+\\(D\\) == 3\\)" 1 "dom2"} } */
+
diff --git a/gcc/tree-ssa-dom.c b/gcc/tree-ssa-dom.c
index d91766e902e..06be69a530c 100644
--- a/gcc/tree-ssa-dom.c
+++ b/gcc/tree-ssa-dom.c
@@ -103,9 +103,6 @@ struct opt_stats_d
 static struct opt_stats_d opt_stats;
 
 /* Local functions.  */
-static edge optimize_stmt (basic_block, gimple_stmt_iterator,
-			   class const_and_copies *,
-			   class avail_exprs_stack *);
 static void record_equality (tree, tree, class const_and_copies *);
 static void record_equivalences_from_phis (basic_block);
 static void record_equivalences_from_incoming_edge (basic_block,
@@ -572,11 +569,12 @@ class dom_opt_dom_walker : public dom_walker
 public:
   dom_opt_dom_walker (cdi_direction direction,
 		      class const_and_copies *const_and_copies,
-		      class avail_exprs_stack *avail_exprs_stack)
+		      class avail_exprs_stack *avail_exprs_stack,
+		      gcond *dummy_cond)
     : dom_walker (direction, true),
       m_const_and_copies (const_and_copies),
       m_avail_exprs_stack (avail_exprs_stack),
-      m_dummy_cond (NULL) {}
+      m_dummy_cond (dummy_cond) { }
 
   virtual edge before_dom_children (basic_block);
   virtual void after_dom_children (basic_block);
@@ -587,7 +585,14 @@ private:
   class const_and_copies *m_const_and_copies;
   class avail_exprs_stack *m_avail_exprs_stack;
 
+  /* Dummy condition to avoid creating lots of throw away statements.  */
   gcond *m_dummy_cond;
+
+  /* Optimize a single statement within a basic block using the
+     various tables mantained by DOM.  Returns the taken edge if
+     the statement is a conditional with a statically determined
+     value.  */
+  edge optimize_stmt (basic_block, gimple_stmt_iterator);
 };
 
 /* Jump threading, redundancy elimination and const/copy propagation.
@@ -684,10 +689,12 @@ pass_dominator::execute (function *fun)
   FOR_EACH_BB_FN (bb, fun)
     record_edge_info (bb);
 
+  gcond *dummy_cond = gimple_build_cond (NE_EXPR, integer_zero_node,
+					 integer_zero_node, NULL, NULL);
+
   /* Recursively walk the dominator tree optimizing statements.  */
-  dom_opt_dom_walker walker (CDI_DOMINATORS,
-			     const_and_copies,
-			     avail_exprs_stack);
+  dom_opt_dom_walker walker (CDI_DOMINATORS, const_and_copies,
+			     avail_exprs_stack, dummy_cond);
   walker.walk (fun->cfg->x_entry_block_ptr);
 
   /* Look for blocks where we cleared EDGE_EXECUTABLE on an outgoing
@@ -1348,8 +1355,7 @@ dom_opt_dom_walker::before_dom_children (basic_block bb)
 
   edge taken_edge = NULL;
   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
-    taken_edge
-      = optimize_stmt (bb, gsi, m_const_and_copies, m_avail_exprs_stack);
+    taken_edge = this->optimize_stmt (bb, gsi);
 
   /* Now prepare to process dominated blocks.  */
   record_edge_info (bb);
@@ -1367,10 +1373,6 @@ dom_opt_dom_walker::before_dom_children (basic_block bb)
 void
 dom_opt_dom_walker::after_dom_children (basic_block bb)
 {
-  if (! m_dummy_cond)
-    m_dummy_cond = gimple_build_cond (NE_EXPR, integer_zero_node,
-				      integer_zero_node, NULL, NULL);
-
   thread_outgoing_edges (bb, m_dummy_cond, m_const_and_copies,
 			 m_avail_exprs_stack,
 			 simplify_stmt_for_jump_threading);
@@ -1700,8 +1702,99 @@ cprop_into_stmt (gimple *stmt)
     }
 }
 
-/* Optimize the statement in block BB pointed to by iterator SI
-   using equivalences from CONST_AND_COPIES and AVAIL_EXPRS_STACK.
+/* If STMT contains a relational test, try to convert it into an
+   equality test if there is only a single value which can ever
+   make the test true.
+
+   For example, if the expression hash table contains:
+
+    TRUE = (i <= 1)
+
+   And we have a test within statement of i >= 1, then we can safely
+   rewrite the test as i == 1 since there only a single value where
+   the test is true.
+
+   This is similar to code in VRP.  */
+
+static void
+test_for_singularity (gimple *stmt, gcond *dummy_cond,
+		      avail_exprs_stack *avail_exprs_stack)
+{
+  /* We want to support gimple conditionals as well as assignments
+     where the RHS contains a conditional.  */
+  if (is_gimple_assign (stmt) || gimple_code (stmt) == GIMPLE_COND)
+    {
+      enum tree_code code = ERROR_MARK;
+      tree lhs, rhs;
+
+      /* Extract the condition of interest from both forms we support.  */
+      if (is_gimple_assign (stmt))
+	{
+	  code = gimple_assign_rhs_code (stmt);
+	  lhs = gimple_assign_rhs1 (stmt);
+	  rhs = gimple_assign_rhs2 (stmt);
+	}
+      else if (gimple_code (stmt) == GIMPLE_COND)
+	{
+	  code = gimple_cond_code (as_a <gcond *> (stmt));
+	  lhs = gimple_cond_lhs (as_a <gcond *> (stmt));
+	  rhs = gimple_cond_rhs (as_a <gcond *> (stmt));
+	}
+
+      /* We're looking for a relational test using LE/GE.  Also note we can
+	 canonicalize LT/GT tests against constants into LE/GT tests.  */
+      if (code == LE_EXPR || code == GE_EXPR
+	  || ((code == LT_EXPR || code == GT_EXPR)
+	       && TREE_CODE (rhs) == INTEGER_CST))
+	{
+	  /* For LT_EXPR and GT_EXPR, canonicalize to LE_EXPR and GE_EXPR.  */
+	  if (code == LT_EXPR)
+	    rhs = fold_build2 (MINUS_EXPR, TREE_TYPE (rhs),
+			       rhs, build_int_cst (TREE_TYPE (rhs), 1));
+
+	  if (code == GT_EXPR)
+	    rhs = fold_build2 (PLUS_EXPR, TREE_TYPE (rhs),
+			       rhs, build_int_cst (TREE_TYPE (rhs), 1));
+
+	  /* Determine the code we want to check for in the hash table.  */
+	  enum tree_code test_code;
+	  if (code == GE_EXPR || code == GT_EXPR)
+	    test_code = LE_EXPR;
+	  else
+	    test_code = GE_EXPR;
+
+	  /* Update the dummy statement so we can query the hash tables.  */
+	  gimple_cond_set_code (dummy_cond, test_code);
+	  gimple_cond_set_lhs (dummy_cond, lhs);
+	  gimple_cond_set_rhs (dummy_cond, rhs);
+	  tree cached_lhs
+	    = avail_exprs_stack->lookup_avail_expr (dummy_cond, false, false);
+
+	  /* If the lookup returned 1 (true), then the expression we
+	     queried was in the hash table.  As a result there is only
+	     one value that makes the original conditional true.  Update
+	     STMT accordingly.  */
+	  if (cached_lhs && integer_onep (cached_lhs))
+	    {
+	      if (is_gimple_assign (stmt))
+		{
+		  gimple_assign_set_rhs_code (stmt, EQ_EXPR);
+		  gimple_assign_set_rhs2 (stmt, rhs);
+		  gimple_set_modified (stmt, true);
+		}
+	      else
+		{
+		  gimple_set_modified (stmt, true);
+		  gimple_cond_set_code (as_a <gcond *> (stmt), EQ_EXPR);
+		  gimple_cond_set_rhs (as_a <gcond *> (stmt), rhs);
+		  gimple_set_modified (stmt, true);
+		}
+	    }
+	}
+    }
+}
+
+/* Optimize the statement in block BB pointed to by iterator SI.
 
    We try to perform some simplistic global redundancy elimination and
    constant propagation:
@@ -1714,12 +1807,15 @@ cprop_into_stmt (gimple *stmt)
    2- Constant values and copy assignments.  This is used to do very
       simplistic constant and copy propagation.  When a constant or copy
       assignment is found, we map the value on the RHS of the assignment to
-      the variable in the LHS in the CONST_AND_COPIES table.  */
+      the variable in the LHS in the CONST_AND_COPIES table.
 
-static edge
-optimize_stmt (basic_block bb, gimple_stmt_iterator si,
-	       class const_and_copies *const_and_copies,
-	       class avail_exprs_stack *avail_exprs_stack)
+   3- Very simple redundant store elimination is performed.
+
+   4- We can simpify a condition to a constant or from a relational
+      condition to an equality condition.  */
+
+edge
+dom_opt_dom_walker::optimize_stmt (basic_block bb, gimple_stmt_iterator si)
 {
   gimple *stmt, *old_stmt;
   bool may_optimize_p;
@@ -1832,8 +1928,8 @@ optimize_stmt (basic_block bb, gimple_stmt_iterator si,
 	}
 
       update_stmt_if_modified (stmt);
-      eliminate_redundant_computations (&si, const_and_copies,
-					avail_exprs_stack);
+      eliminate_redundant_computations (&si, m_const_and_copies,
+					m_avail_exprs_stack);
       stmt = gsi_stmt (si);
 
       /* Perform simple redundant store elimination.  */
@@ -1855,8 +1951,8 @@ optimize_stmt (basic_block bb, gimple_stmt_iterator si,
 	  else
 	    new_stmt = gimple_build_assign (rhs, lhs);
 	  gimple_set_vuse (new_stmt, gimple_vuse (stmt));
-	  cached_lhs = avail_exprs_stack->lookup_avail_expr (new_stmt, false,
-							     false);
+	  cached_lhs = m_avail_exprs_stack->lookup_avail_expr (new_stmt, false,
+							       false);
 	  if (cached_lhs && operand_equal_p (rhs, cached_lhs, 0))
 	    {
 	      basic_block bb = gimple_bb (stmt);
@@ -1871,11 +1967,16 @@ optimize_stmt (basic_block bb, gimple_stmt_iterator si,
 	      return retval;
 	    }
 	}
+
+      /* If this statement was not redundant, we may still be able to simplify
+	 it, which may in turn allow other part of DOM or other passes to do
+	 a better job.  */
+      test_for_singularity (stmt, m_dummy_cond, m_avail_exprs_stack);
     }
 
   /* Record any additional equivalences created by this statement.  */
   if (is_gimple_assign (stmt))
-    record_equivalences_from_stmt (stmt, may_optimize_p, avail_exprs_stack);
+    record_equivalences_from_stmt (stmt, may_optimize_p, m_avail_exprs_stack);
 
   /* If STMT is a COND_EXPR or SWITCH_EXPR and it was modified, then we may
      know where it goes.  */