tree-ssa-ifcombine.c: Include rtl.h and tm_p.h.

2013-10-29  Andrew Pinski <apinski@cavium.com>

        * tree-ssa-ifcombine.c: Include rtl.h and tm_p.h.
        (ifcombine_ifandif): Handle cases where
        maybe_fold_and_comparisons fails, combining the branches
        anyways.
        (tree_ssa_ifcombine): Inverse the order of
        the basic block walk, increases the number of combinings.
        * gimple.h (gsi_start_nondebug_after_labels_bb): New function.

2013-10-29  Andrew Pinski <apinski@cavium.com>
            Zhenqiang Chen  <zhenqiang.chen@linaro.org>

        * gcc.dg/tree-ssa/ssa-ifcombine-ccmp-1.c: New test case.
        * gcc.dg/tree-ssa/ssa-ifcombine-ccmp-2.c: New test case.
        * gcc.dg/tree-ssa/ssa-ifcombine-ccmp-3.c: New test case.
        * gcc.dg/tree-ssa/ssa-ifcombine-ccmp-4.c: New test case.
        * gcc.dg/tree-ssa/ssa-ifcombine-ccmp-5.c: New test case.
        * gcc.dg/tree-ssa/ssa-ifcombine-ccmp-6.c: New test case.
        * gcc.dg/tree-ssa/phi-opt-9.c: Use a function call to prevent
        conditional move to be used.
        * gcc.dg/tree-ssa/ssa-dom-thread-3.c: Remove.


Co-Authored-By: Zhenqiang Chen <zhenqiang.chen@linaro.org>

From-SVN: r204194

12 files changed, 182 insertions, 51 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index ba0bf86..01a0b49 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,13 @@
+2013-10-29  Andrew Pinski <apinski@cavium.com>
+
+	* tree-ssa-ifcombine.c: Include rtl.h and tm_p.h.
+	(ifcombine_ifandif): Handle cases where
+	maybe_fold_and_comparisons fails, combining the branches
+	anyways.
+	(tree_ssa_ifcombine): Inverse the order of
+	the basic block walk, increases the number of combinings.
+	* gimple.h (gsi_start_nondebug_after_labels_bb): New function.
+
 2013-10-29  Mike Stump  <mikestump@comcast.net>
 
 	* machmode.def (PARTIAL_INT_MODE): Add precision and name.
diff --git a/gcc/gimple.h b/gcc/gimple.h
index e34411d..b0fb861 100644
--- a/gcc/gimple.h
+++ b/gcc/gimple.h
@@ -5533,6 +5533,20 @@ gsi_start_nondebug_bb (basic_block bb)
   return i;
 }
 
+/* Return a new iterator pointing to the first non-debug non-label statement in
+   basic block BB.  */
+
+static inline gimple_stmt_iterator
+gsi_start_nondebug_after_labels_bb (basic_block bb)
+{
+  gimple_stmt_iterator i = gsi_after_labels (bb);
+
+  if (!gsi_end_p (i) && is_gimple_debug (gsi_stmt (i)))
+    gsi_next_nondebug (&i);
+
+  return i;
+}
+
 /* Return a new iterator pointing to the last non-debug statement in
    basic block BB.  */
 
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index bed2cda..8bad787 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,3 +1,16 @@
+2013-10-29  Andrew Pinski <apinski@cavium.com>
+            Zhenqiang Chen  <zhenqiang.chen@linaro.org>
+
+	* gcc.dg/tree-ssa/ssa-ifcombine-ccmp-1.c: New test case.
+	* gcc.dg/tree-ssa/ssa-ifcombine-ccmp-2.c: New test case.
+	* gcc.dg/tree-ssa/ssa-ifcombine-ccmp-3.c: New test case.
+	* gcc.dg/tree-ssa/ssa-ifcombine-ccmp-4.c: New test case.
+	* gcc.dg/tree-ssa/ssa-ifcombine-ccmp-5.c: New test case.
+	* gcc.dg/tree-ssa/ssa-ifcombine-ccmp-6.c: New test case.
+	* gcc.dg/tree-ssa/phi-opt-9.c: Use a function call to prevent
+	conditional move to be used.
+	* gcc.dg/tree-ssa/ssa-dom-thread-3.c: Remove.
+
 2013-10-29  Tobias Burnus  <burnus@net-b.de>
 
 	PR fortran/44350
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/phi-opt-9.c b/gcc/testsuite/gcc.dg/tree-ssa/phi-opt-9.c
index dccea7b..a224788 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/phi-opt-9.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/phi-opt-9.c
@@ -2,13 +2,14 @@
 /* { dg-options "-O -fdump-tree-optimized" } */
 
 int g(int,int);
+int h(int);
 int f(int t, int c)
 {
   int d = 0;
   int e = 0;
   if (t)
     {
-      d = c+1;
+      d = h(c);
       e = t;
     }
   else d = 0, e = 0;
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-3.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-3.c
deleted file mode 100644
index 0d53f50..0000000
--- a/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-3.c
+++ /dev/null
@@ -1,48 +0,0 @@
-/* { dg-do compile } */ 
-/* { dg-options "-O2 -fdump-tree-dom1-details -fno-short-enums" } */
-
-extern void abort (void) __attribute__ ((__noreturn__));
-union tree_node;
-typedef union tree_node *tree;
-enum tree_code
-{
-  VAR_DECL,
-  SSA_NAME,
-  MAX_TREE_CODES
-};
-extern unsigned char tree_contains_struct[MAX_TREE_CODES][64];
-struct tree_base
-{
-  enum tree_code code:16;
-};
-enum tree_node_structure_enum
-{
-  TS_DECL_COMMON
-};
-struct tree_ssa_name
-{
-  tree var;
-};
-union tree_node
-{
-  struct tree_base base;
-  struct tree_ssa_name ssa_name;
-};
-long
-expand_one_var (tree var, unsigned char toplevel, unsigned char really_expand)
-{
-  tree origvar = var;
-  var = var->ssa_name.var;
-  if (((enum tree_code) (origvar)->base.code) == SSA_NAME
-      && !((var->base.code != VAR_DECL)))
-    abort ();
-  if ((var->base.code) != VAR_DECL && ((origvar)->base.code) != SSA_NAME)
-    ;
-  else if (tree_contains_struct[(var->base.code)][(TS_DECL_COMMON)] != 1)
-    abort ();
-}
-/* We should thread the jump, through an intermediate block.  */
-/* { dg-final { scan-tree-dump-times "Threaded" 2 "dom1"} } */
-/* { dg-final { scan-tree-dump-times "Registering jump thread: \\(.*\\) incoming edge;  \\(.*\\) joiner;  \\(.*\\) nocopy;" 1 "dom1"} } */
-/* { dg-final { cleanup-tree-dump "dom1" } } */
-
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-ccmp-1.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-ccmp-1.c
new file mode 100644
index 0000000..56c936d
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-ccmp-1.c
@@ -0,0 +1,14 @@
+/* { dg-do compile { target { ! "m68k*-*-* mmix*-*-* mep*-*-* bfin*-*-* v850*-*-* picochip*-*-* moxie*-*-* cris*-*-* m32c*-*-* fr30*-*-* mcore*-*-* powerpc*-*-* xtensa*-*-*"} } } */
+
+/* { dg-options "-O2 -g -fdump-tree-optimized" } */
+/* { dg-additional-options "-mbranch-cost=2" { target avr-*-* } } */
+
+int t (int a, int b)
+{
+  if (a > 0)
+    if (b > 0)
+      return 0;
+  return 1;
+}
+/* { dg-final { scan-tree-dump "\&" "optimized" } } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-ccmp-2.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-ccmp-2.c
new file mode 100644
index 0000000..3273bcc
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-ccmp-2.c
@@ -0,0 +1,17 @@
+/* { dg-do compile { target { ! "m68k*-*-* mmix*-*-* mep*-*-* bfin*-*-* v850*-*-* picochip*-*-* moxie*-*-* cris*-*-* m32c*-*-* fr30*-*-* mcore*-*-* powerpc*-*-* xtensa*-*-*"} } } */
+
+/* { dg-options "-O2 -g -fdump-tree-optimized" } */
+/* { dg-additional-options "-mbranch-cost=2" { target avr-*-* } } */
+
+int t (int a, int b)
+{
+  if (a > 0)
+    goto L1;
+  if (b > 0)
+    goto L1;
+  return 0;
+L1:
+  return 1;
+}
+/* { dg-final { scan-tree-dump "\|" "optimized" } } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-ccmp-3.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-ccmp-3.c
new file mode 100644
index 0000000..500cb01
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-ccmp-3.c
@@ -0,0 +1,20 @@
+/* { dg-do compile { target { ! "m68k*-*-* mmix*-*-* mep*-*-* bfin*-*-* v850*-*-* picochip*-*-* moxie*-*-* cris*-*-* m32c*-*-* fr30*-*-* mcore*-*-* powerpc*-*-* xtensa*-*-*"} } } */
+
+/* { dg-options "-O2 -g -fdump-tree-optimized" } */
+/* { dg-additional-options "-mbranch-cost=2" { target avr-*-* } } */
+
+int t (int a, int b)
+{
+  if (a > 0)
+    goto L1;
+  else
+    goto L2;
+L1:
+  if (b > 0)
+    goto L2;
+  return 5;
+L2:
+  return 6;
+}
+/* { dg-final { scan-tree-dump "\|" "optimized" } } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-ccmp-4.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-ccmp-4.c
new file mode 100644
index 0000000..8b87101
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-ccmp-4.c
@@ -0,0 +1,18 @@
+/* { dg-do compile { target { ! "m68k*-*-* mmix*-*-* mep*-*-* bfin*-*-* v850*-*-* picochip*-*-* moxie*-*-* cris*-*-* m32c*-*-* fr30*-*-* mcore*-*-* powerpc*-*-* xtensa*-*-*"} } } */
+
+/* { dg-options "-O2 -g -fdump-tree-optimized" } */
+/* { dg-additional-options "-mbranch-cost=2" { target avr-*-* } } */
+
+int t (int a, int b)
+{
+  if (a > 0)
+    goto L1;
+  if (b > 0)
+    goto L2;
+L1:
+  return 0;
+L2:
+  return 1;
+}
+/* { dg-final { scan-tree-dump "\&" "optimized" } } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-ccmp-5.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-ccmp-5.c
new file mode 100644
index 0000000..2aa225b
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-ccmp-5.c
@@ -0,0 +1,13 @@
+/* { dg-do compile { target { ! "m68k*-*-* mmix*-*-* mep*-*-* bfin*-*-* v850*-*-* picochip*-*-* moxie*-*-* cris*-*-* m32c*-*-* fr30*-*-* mcore*-*-* powerpc*-*-* xtensa*-*-*"} } } */
+
+/* { dg-options "-O2 -g -fdump-tree-optimized" } */
+/* { dg-additional-options "-mbranch-cost=2" { target avr-*-* } } */
+
+int t (int a, int b, int c)
+{
+  if (a > 0 && b > 0 && c > 0)
+      return 0;
+  return 1;
+}
+/* { dg-final { scan-tree-dump-times "\&" 2 "optimized" } } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-ccmp-6.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-ccmp-6.c
new file mode 100644
index 0000000..659e816
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-ccmp-6.c
@@ -0,0 +1,13 @@
+/* { dg-do compile { target { ! "m68k*-*-* mmix*-*-* mep*-*-* bfin*-*-* v850*-*-* picochip*-*-* moxie*-*-* cris*-*-* m32c*-*-* fr30*-*-* mcore*-*-* powerpc*-*-* xtensa*-*-*"} } } */
+
+/* { dg-options "-O2 -g -fdump-tree-optimized" } */
+/* { dg-additional-options "-mbranch-cost=2" { target avr-*-* } } */
+
+int t (int a, int b, int c)
+{
+  if (a > 0 || b > 0 || c > 0)
+      return 0;
+  return 1;
+}
+/* { dg-final { scan-tree-dump-times "\\|" 2 "optimized" } } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */
diff --git a/gcc/tree-ssa-ifcombine.c b/gcc/tree-ssa-ifcombine.c
index 0b9de25..73ebfe8 100644
--- a/gcc/tree-ssa-ifcombine.c
+++ b/gcc/tree-ssa-ifcombine.c
@@ -22,6 +22,10 @@ along with GCC; see the file COPYING3.  If not see
 #include "system.h"
 #include "coretypes.h"
 #include "tm.h"
+/* rtl is needed only because arm back-end requires it for
+   BRANCH_COST.  */
+#include "rtl.h"
+#include "tm_p.h"
 #include "tree.h"
 #include "basic-block.h"
 #include "tree-pretty-print.h"
@@ -32,6 +36,12 @@ along with GCC; see the file COPYING3.  If not see
 #include "ssa-iterators.h"
 #include "tree-pass.h"
 
+#ifndef LOGICAL_OP_NON_SHORT_CIRCUIT
+#define LOGICAL_OP_NON_SHORT_CIRCUIT \
+  (BRANCH_COST (optimize_function_for_speed_p (cfun), \
+                false) >= 2)
+#endif
+
 /* This pass combines COND_EXPRs to simplify control flow.  It
    currently recognizes bit tests and comparisons in chains that
    represent logical and or logical or of two COND_EXPRs.
@@ -488,7 +498,35 @@ ifcombine_ifandif (basic_block inner_cond_bb, bool inner_inv,
 					    outer_cond_code,
 					    gimple_cond_lhs (outer_cond),
 					    gimple_cond_rhs (outer_cond))))
-	return false;
+	{
+	  tree t1, t2;
+	  gimple_stmt_iterator gsi;
+	  if (!LOGICAL_OP_NON_SHORT_CIRCUIT)
+	    return false;
+	  /* Only do this optimization if the inner bb contains only the conditional. */
+	  if (!gsi_one_before_end_p (gsi_start_nondebug_after_labels_bb (inner_cond_bb)))
+	    return false;
+	  t1 = fold_build2_loc (gimple_location (inner_cond),
+				inner_cond_code,
+				boolean_type_node,
+				gimple_cond_lhs (inner_cond),
+				gimple_cond_rhs (inner_cond));
+	  t2 = fold_build2_loc (gimple_location (outer_cond),
+				outer_cond_code,
+				boolean_type_node,
+				gimple_cond_lhs (outer_cond),
+				gimple_cond_rhs (outer_cond));
+	  t = fold_build2_loc (gimple_location (inner_cond), 
+			       TRUTH_AND_EXPR, boolean_type_node, t1, t2);
+	  if (result_inv)
+	    {
+	      t = fold_build1 (TRUTH_NOT_EXPR, TREE_TYPE (t), t);
+	      result_inv = false;
+	    }
+	  gsi = gsi_for_stmt (inner_cond);
+	  t = force_gimple_operand_gsi_1 (&gsi, t, is_gimple_condexpr, NULL, true,
+					  GSI_SAME_STMT);
+        }
       if (result_inv)
 	t = fold_build1 (TRUTH_NOT_EXPR, TREE_TYPE (t), t);
       t = canonicalize_cond_expr_cond (t);
@@ -631,7 +669,15 @@ tree_ssa_ifcombine (void)
   bbs = single_pred_before_succ_order ();
   calculate_dominance_info (CDI_DOMINATORS);
 
-  for (i = 0; i < n_basic_blocks - NUM_FIXED_BLOCKS; ++i)
+  /* Search every basic block for COND_EXPR we may be able to optimize.
+
+     We walk the blocks in order that guarantees that a block with
+     a single predecessor is processed after the predecessor.
+     This ensures that we collapse outter ifs before visiting the
+     inner ones, and also that we do not try to visit a removed
+     block.  This is opposite of PHI-OPT, because we cascade the
+     combining rather than cascading PHIs. */
+  for (i = n_basic_blocks - NUM_FIXED_BLOCKS - 1; i >= 0; i--)
     {
       basic_block bb = bbs[i];
       gimple stmt = last_stmt (bb);