On Tue, Oct 29, 2013 at 3:28 AM, Richard Biener
<[email protected]> wrote:
> On Sun, Oct 27, 2013 at 7:55 PM, Andrew Pinski <[email protected]> wrote:
>> On Sat, Oct 26, 2013 at 4:49 PM, Andrew Pinski <[email protected]> wrote:
>>> On Sat, Oct 26, 2013 at 2:30 PM, Andrew Pinski <[email protected]> wrote:
>>>> On Fri, Oct 18, 2013 at 2:21 AM, Zhenqiang Chen
>>>> <[email protected]> wrote:
>>>>> On 18 October 2013 00:58, Jeff Law <[email protected]> wrote:
>>>>>> On 10/17/13 05:03, Richard Biener wrote:
>>>>>>>>>
>>>>>>>>> Is it OK for trunk?
>>>>>>>>
>>>>>>>>
>>>>>>>> I had a much simpler change which did basically the same from 4.7 (I
>>>>>>>> can update it if people think this is a better approach).
>>>>>>>
>>>>>>>
>>>>>>> I like that more (note you can now use is_gimple_condexpr as predicate
>>>>>>> for force_gimple_operand).
>>>>>>
>>>>>> The obvious question is whether or not Andrew's simpler change picks up
>>>>>> as
>>>>>> many transformations as Zhenqiang's change. If not are the things missed
>>>>>> important.
>>>>>>
>>>>>> Zhenqiang, can you do some testing of your change vs Andrew P.'s change?
>>>>>
>>>>> Here is a rough compare:
>>>>>
>>>>> 1) Andrew P.'s change can not handle ssa-ifcombine-ccmp-3.c (included
>>>>> in my patch). Root cause is that it does not skip "LABEL". The guard
>>>>> to do this opt should be the same the bb_has_overhead_p in my patch.
>>>>
>>>> This should be an easy change, I am working on this right now.
>>>>
>>>>>
>>>>> 2) Andrew P.'s change always generate TRUTH_AND_EXPR, which is not
>>>>> efficient for "||". e.g. For ssa-ifcombine-ccmp-6.c, it will generate
>>>>>
>>>>> _3 = a_2(D) > 0;
>>>>> _5 = b_4(D) > 0;
>>>>> _6 = _3 | _5;
>>>>> _9 = c_7(D) <= 0;
>>>>> _10 = ~_6;
>>>>> _11 = _9 & _10;
>>>>> if (_11 == 0)
>>>>>
>>>>> With my patch, it will generate
>>>>>
>>>>> _3 = a_2(D) > 0;
>>>>> _5 = b_4(D) > 0;
>>>>> _6 = _3 | _5;
>>>>> _9 = c_7(D) > 0;
>>>>> _10 = _6 | _9;
>>>>> if (_10 != 0)
>>>>
>>>> As mentioned otherwise, this seems like a missed optimization inside
>>>> forwprop. When I originally wrote this code there used to be two
>>>> cases one for & and one for |, but this was removed sometime and I
>>>> just made the code evolve with that.
>>>
>>> Actually I can make a small patch (3 lines) to my current patch which
>>> causes tree-ssa-ifcombine.c to produce the behavior of your patch.
>>>
>>> if (result_inv)
>>> {
>>> t = fold_build1 (TRUTH_NOT_EXPR, TREE_TYPE (t), t);
>>> result_inv = false;
>>> }
>>>
>>> I will submit a new patch after some testing of my current patch which
>>> fixes items 1 and 2.
>>
>>
>> Here is my latest patch which adds the testcases from Zhenqiang's
>> patch and fixes item 1 and 2.
>>
>> OK? Bootstrapped and tested on x86_64-linux-gnu with no regressions.
>
> 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)
>
>
> vertical space before the comment missing.
>
> @@ -631,7 +669,7 @@ 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)
> + for (i = n_basic_blocks - NUM_FIXED_BLOCKS -1; i >= 0; i--)
> {
> basic_block bb = bbs[i];
> gimple stmt = last_stmt (bb);
>
> The original code matches what phiopt does which even has a comment:
>
> /* 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 before the predecessor.
> This ensures that we collapse inner ifs before visiting the
> outer ones, and also that we do not try to visit a removed
> block. */
> bb_order = single_pred_before_succ_order ();
> n = n_basic_blocks - NUM_FIXED_BLOCKS;
>
> for (i = 0; i < n; i++)
>
> so if the reverse order is better here (and in phiopt?) then it at least
> needs a comment explaining why.
>
> Otherwise the patch looks good, but please iterate with Jeff over
> the dom testcase issue.
Here is what I applied in the end; Jeff told me just to remove the
testcase. I added the comment trying to explain why it was the
opposite order of PHI-opt.
Thanks,
Andrew Pinski
ChangeLog:
* 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.
testsuite/ChangeLog:
* 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.
>
> Thanks,
> Richard.
>
>> Thanks,
>> Andrew Pinski
>>
>> ChangeLog:
>> * 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.
>>
>>
>> testsuite/ChangeLog:
>>
>> * 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 check for "one or more
>> intermediate".
>>
>>
>>
>>
>>>
>>> Thanks,
>>> Andrew Pinski
>>>
>>>
>>>>
>>>>>
>>>>> 3) The good thing of Andrew P.'s change is that "Inverse the order of
>>>>> the basic block walk" so it can do combine recursively.
>>>>>
>>>>> But I think we need some heuristic to control the number of ifs. Move
>>>>> too much compares from
>>>>> the inner_bb to outer_bb is not good.
>>>>
>>>>
>>>> I think this depends on the target. For MIPS we don't want an upper
>>>> bound as integer comparisons go directly to GPRs. I wrote this patch
>>>> with MIPS in mind as that was the target I was working on.
>>>>
>>>>>
>>>>> 4) Another good thing of Andrew P.'s change is that it reuses some
>>>>> existing functions. So it looks much simple.
>>>>
>>>>
>>>> Thanks,
>>>> Andrew Pinski
>>>>
>>>>>
>>>>>>>
>>>>>>> With that we should be able to kill the fold-const.c transform?
>>>>>>
>>>>>> That would certainly be nice and an excellent follow-up for Zhenqiang.
>>>>>
>>>>> That's my final goal to "kill the fold-const.c transform". I think we
>>>>> may combine the two changes to make a "simple" and "good" patch.
>>>>>
>>>>> Thanks!
>>>>> -Zhenqiang
Index: testsuite/gcc.dg/tree-ssa/ssa-ifcombine-ccmp-1.c
===================================================================
--- testsuite/gcc.dg/tree-ssa/ssa-ifcombine-ccmp-1.c (revision 0)
+++ testsuite/gcc.dg/tree-ssa/ssa-ifcombine-ccmp-1.c (revision 0)
@@ -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" } } */
Index: testsuite/gcc.dg/tree-ssa/ssa-dom-thread-3.c
===================================================================
--- testsuite/gcc.dg/tree-ssa/ssa-dom-thread-3.c (revision 204133)
+++ testsuite/gcc.dg/tree-ssa/ssa-dom-thread-3.c (working copy)
@@ -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" } } */
-
Index: testsuite/gcc.dg/tree-ssa/ssa-ifcombine-ccmp-2.c
===================================================================
--- testsuite/gcc.dg/tree-ssa/ssa-ifcombine-ccmp-2.c (revision 0)
+++ testsuite/gcc.dg/tree-ssa/ssa-ifcombine-ccmp-2.c (revision 0)
@@ -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" } } */
Index: testsuite/gcc.dg/tree-ssa/ssa-ifcombine-ccmp-3.c
===================================================================
--- testsuite/gcc.dg/tree-ssa/ssa-ifcombine-ccmp-3.c (revision 0)
+++ testsuite/gcc.dg/tree-ssa/ssa-ifcombine-ccmp-3.c (revision 0)
@@ -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" } } */
Index: testsuite/gcc.dg/tree-ssa/ssa-ifcombine-ccmp-4.c
===================================================================
--- testsuite/gcc.dg/tree-ssa/ssa-ifcombine-ccmp-4.c (revision 0)
+++ testsuite/gcc.dg/tree-ssa/ssa-ifcombine-ccmp-4.c (revision 0)
@@ -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" } } */
Index: testsuite/gcc.dg/tree-ssa/phi-opt-9.c
===================================================================
--- testsuite/gcc.dg/tree-ssa/phi-opt-9.c (revision 204133)
+++ testsuite/gcc.dg/tree-ssa/phi-opt-9.c (working copy)
@@ -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;
Index: testsuite/gcc.dg/tree-ssa/ssa-ifcombine-ccmp-5.c
===================================================================
--- testsuite/gcc.dg/tree-ssa/ssa-ifcombine-ccmp-5.c (revision 0)
+++ testsuite/gcc.dg/tree-ssa/ssa-ifcombine-ccmp-5.c (revision 0)
@@ -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" } } */
Index: testsuite/gcc.dg/tree-ssa/ssa-ifcombine-ccmp-6.c
===================================================================
--- testsuite/gcc.dg/tree-ssa/ssa-ifcombine-ccmp-6.c (revision 0)
+++ testsuite/gcc.dg/tree-ssa/ssa-ifcombine-ccmp-6.c (revision 0)
@@ -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" } } */
Index: tree-ssa-ifcombine.c
===================================================================
--- tree-ssa-ifcombine.c (revision 204133)
+++ tree-ssa-ifcombine.c (working copy)
@@ -22,6 +22,10 @@ along with GCC; see the file COPYING3.
#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.
#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_con
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);
Index: gimple.h
===================================================================
--- gimple.h (revision 204133)
+++ gimple.h (working copy)
@@ -5534,6 +5534,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. */
