On Sat, Jul 6, 2013 at 9:42 PM, Marc Glisse <marc.gli...@inria.fr> wrote: > Hello, > > the first attached patch does not bootstrap and has at least 2 main issues. > The second patch does pass bootstrap+testsuite, but I liked the first > more... > > First, the fold-const bit causes an assertion failure (building libjava) in > combine_cond_expr_cond, which calls: > > t = fold_binary_loc (gimple_location (stmt), code, type, op0, op1); > > and then checks: > > /* Require that we got a boolean type out if we put one in. */ > gcc_assert (TREE_CODE (TREE_TYPE (t)) == TREE_CODE (type)); > > which makes sense... Note that the 2 relevant types are:
well, the check is probably old and can be relaxed to also allow all compatible types. > (gdb) call debug_tree((tree)0x7ffff5e78930) > <integer_type 0x7ffff5e78930 jboolean asm_written public unsigned type_3 QI > size <integer_cst 0x7ffff64dcfa0 type <integer_type 0x7ffff64f60a8 > bitsizetype> constant 8> > unit size <integer_cst 0x7ffff64dcfc0 type <integer_type 0x7ffff64f6000 > sizetype> constant 1> > align 8 symtab -169408800 alias set -1 canonical type 0x7ffff6635c78 > precision 1 min <integer_cst 0x7ffff66321e0 0> max <integer_cst > 0x7ffff6632200 1> > pointer_to_this <pointer_type 0x7ffff5a1e540> chain <integer_type > 0x7ffff6635dc8>> > (gdb) call debug_tree(type) > <boolean_type 0x7ffff64f69d8 bool sizes-gimplified asm_written public > unsigned QI > size <integer_cst 0x7ffff64dcfa0 type <integer_type 0x7ffff64f60a8 > bitsizetype> constant 8> > unit size <integer_cst 0x7ffff64dcfc0 type <integer_type 0x7ffff64f6000 > sizetype> constant 1> > align 8 symtab -170348640 alias set 19 canonical type 0x7ffff64f69d8 > precision 1 min <integer_cst 0x7ffff64f92a0 0> max <integer_cst > 0x7ffff64f92e0 1> > pointer_to_this <pointer_type 0x7ffff5912dc8>> > > I need to relax the conditions on the vec?-1:0 optimization because with > vectors we often end up with several types that are equivalent. Can you > think of a good way to do it? In the second patch I limit the transformation > to vectors and hope it doesn't cause as much trouble there... > > > > Second, the way the forwprop transformation is done, it can be necessary to > run the forwprop pass several times in a row, which is not nice. It takes: > > stmt_cond > stmt_binop > > and produces: > > stmt_folded > stmt_cond2 > > But one of the arguments of stmt_folded could be an ssa_name defined by a > cond_expr, which could now be propagated into stmt_folded (there may be > other new possible transformations). However, that cond_expr has already > been visited and won't be again. The combine part of the pass uses a PLF to > revisit statements, but the forwprop part doesn't have any specific > mechanism. forwprop is designed to re-process stmts it has folded to catch cascading effects. Now, as it as both a forward and a backward run you don't catch 2nd-order effects with iterating them. On my TODO is to only do one kind, either forward or backward propagation. > The workarounds I can think of are: > - manually check if some of the arguments of stmt_folded are cond_expr and > recursively call the function on them; > - move the transformation to the combine part of the pass; this it is. > - setup some system to revisit all earlier statements? > > I went with the second option in the second patch, but this limitation of > forward propagation seems strange to me. > > > (s/combine_binop_with_condition/forward_propagate_condition/ for the first > patch) Btw, as for the patch I don't like that you basically feed everything into fold. Yes, I know we do that for conditions because that's quite important and nobody has re-written the condition folding as gimple pattern matcher. I doubt that this transform is important enough to warrant another exception ;) Richard. > 2013-07-06 Marc Glisse <marc.gli...@inria.fr> > > PR tree-optimization/57755 > gcc/ > * tree-ssa-forwprop.c (combine_binop_with_condition): New function. > (ssa_forward_propagate_and_combine): Call it. > * fold-const.c (fold_ternary_loc): In gimple form, don't check for > type equality. > > gcc/testsuite/ > * g++.dg/tree-ssa/pr57755.C: New testcase. > > (this message does not supersede > http://gcc.gnu.org/ml/gcc-patches/2013-06/msg01624.html ) > > -- > Marc Glisse > Index: fold-const.c > =================================================================== > --- fold-const.c (revision 200736) > +++ fold-const.c (working copy) > @@ -14124,21 +14124,23 @@ fold_ternary_loc (location_t loc, enum t > > /* Convert A ? 1 : 0 to simply A. */ > if ((code == VEC_COND_EXPR ? integer_all_onesp (op1) > : (integer_onep (op1) > && !VECTOR_TYPE_P (type))) > && integer_zerop (op2) > /* If we try to convert OP0 to our type, the > call to fold will try to move the conversion inside > a COND, which will recurse. In that case, the COND_EXPR > is probably the best choice, so leave it alone. */ > - && type == TREE_TYPE (arg0)) > + && (type == TREE_TYPE (arg0) > + || (in_gimple_form > + && useless_type_conversion_p (type, TREE_TYPE (arg0))))) > return pedantic_non_lvalue_loc (loc, arg0); > > /* Convert A ? 0 : 1 to !A. This prefers the use of NOT_EXPR > over COND_EXPR in cases such as floating point comparisons. */ > if (integer_zerop (op1) > && (code == VEC_COND_EXPR ? integer_all_onesp (op2) > : (integer_onep (op2) > && !VECTOR_TYPE_P (type))) > && truth_value_p (TREE_CODE (arg0))) > return pedantic_non_lvalue_loc (loc, > Index: tree-ssa-forwprop.c > =================================================================== > --- tree-ssa-forwprop.c (revision 200736) > +++ tree-ssa-forwprop.c (working copy) > @@ -1135,20 +1135,135 @@ forward_propagate_comparison (gimple_stm > > /* Remove defining statements. */ > return remove_prop_source_from_use (name); > > bailout: > gsi_next (defgsi); > return false; > } > > > +/* Forward propagate the condition defined in *DEFGSI to uses in > + binary operations. > + Returns true if stmt is now unused. Advance DEFGSI to the next > + statement. */ > + > +static bool > +forward_propagate_condition (gimple_stmt_iterator *defgsi) > +{ > + gimple stmt = gsi_stmt (*defgsi); > + tree name = gimple_assign_lhs (stmt); > + enum tree_code defcode = gimple_assign_rhs_code (stmt); > + gimple_stmt_iterator gsi; > + enum tree_code code; > + tree lhs, type; > + gimple use_stmt; > + > + /* Don't propagate ssa names that occur in abnormal phis. */ > + if ((TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME > + && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_assign_rhs1 (stmt))) > + || (TREE_CODE (gimple_assign_rhs2 (stmt)) == SSA_NAME > + && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_assign_rhs2 (stmt))) > + || (TREE_CODE (gimple_assign_rhs3 (stmt)) == SSA_NAME > + && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_assign_rhs3 (stmt)))) > + goto bailout; > + > + /* Do not un-cse, but propagate through copies. */ > + use_stmt = get_prop_dest_stmt (name, &name); > + if (!use_stmt > + || !is_gimple_assign (use_stmt) > + || gimple_has_side_effects (stmt) > + || gimple_has_side_effects (use_stmt)) > + goto bailout; > + > + gsi = gsi_for_stmt (use_stmt); > + code = gimple_assign_rhs_code (use_stmt); > + lhs = gimple_assign_lhs (use_stmt); > + type = TREE_TYPE (lhs); > + > + if (TREE_CODE_CLASS (code) == tcc_binary > + || TREE_CODE_CLASS (code) == tcc_comparison) > + { > + bool cond_is_left = false; > + bool trueok = false; > + bool falseok = false; > + if (name == gimple_assign_rhs1 (use_stmt)) > + cond_is_left = true; > + else > + gcc_assert (name == gimple_assign_rhs2 (use_stmt)); > + tree true_op, false_op; > + if (cond_is_left) > + { > + true_op = fold_build2_loc (gimple_location (stmt), code, type, > + gimple_assign_rhs2 (stmt), > + gimple_assign_rhs2 (use_stmt)); > + false_op = fold_build2_loc (gimple_location (stmt), code, type, > + gimple_assign_rhs3 (stmt), > + gimple_assign_rhs2 (use_stmt)); > + } > + else > + { > + true_op = fold_build2_loc (gimple_location (stmt), code, type, > + gimple_assign_rhs1 (use_stmt), > + gimple_assign_rhs2 (stmt)); > + false_op = fold_build2_loc (gimple_location (stmt), code, type, > + gimple_assign_rhs1 (use_stmt), > + gimple_assign_rhs3 (stmt)); > + } > + > + if (is_gimple_val (true_op)) > + trueok = true; > + if (is_gimple_val (false_op)) > + falseok = true; > + /* At least one of them has to simplify, or it isn't worth it. */ > + if (!trueok && !falseok) > + goto bailout; > + if (!trueok) > + { > + if (!valid_gimple_rhs_p (true_op)) > + goto bailout; > + gimple g = gimple_build_assign (make_ssa_name (type, NULL), > true_op); > + true_op = gimple_assign_lhs (g); > + gsi_insert_before (&gsi, g, GSI_SAME_STMT); > + } > + if (!falseok) > + { > + if (!valid_gimple_rhs_p (false_op)) > + goto bailout; > + gimple g = gimple_build_assign (make_ssa_name (type, NULL), > false_op); > + false_op = gimple_assign_lhs (g); > + gsi_insert_before (&gsi, g, GSI_SAME_STMT); > + } > + > + gimple_assign_set_rhs_with_ops_1 (&gsi, defcode, > + gimple_assign_rhs1 (stmt), > + true_op, false_op); > + } > + else > + goto bailout; > + > + fold_stmt (&gsi); > + update_stmt (gsi_stmt (gsi)); > + > + /* When we remove stmt now the iterator defgsi goes off it's current > + sequence, hence advance it now. */ > + gsi_next (defgsi); > + > + /* Remove defining statements. */ > + return remove_prop_source_from_use (name); > + > +bailout: > + gsi_next (defgsi); > + return false; > +} > + > + > /* GSI_P points to a statement which performs a narrowing integral > conversion. > > Look for cases like: > > t = x & c; > y = (T) t; > > Turn them into: > > @@ -3382,20 +3497,25 @@ ssa_forward_propagate_and_combine (void) > gsi_next (&gsi); > } > else > gsi_next (&gsi); > } > else if (TREE_CODE_CLASS (code) == tcc_comparison) > { > if (forward_propagate_comparison (&gsi)) > cfg_changed = true; > } > + else if (code == COND_EXPR || code == VEC_COND_EXPR) > + { > + if (forward_propagate_condition (&gsi)) > + cfg_changed = true; > + } > else > gsi_next (&gsi); > } > > /* Combine stmts with the stmts defining their operands. > Note we update GSI within the loop as necessary. */ > for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi);) > { > gimple stmt = gsi_stmt (gsi); > bool changed = false; > Index: testsuite/g++.dg/tree-ssa/pr57755.c > =================================================================== > --- testsuite/g++.dg/tree-ssa/pr57755.c (revision 0) > +++ testsuite/g++.dg/tree-ssa/pr57755.c (revision 0) > @@ -0,0 +1,23 @@ > +/* { dg-do compile } */ > +/* { dg-options "-O -fdump-tree-forwprop1" } */ > +typedef int vec __attribute__((vector_size(4*sizeof(int)))); > + > +vec f(vec a,vec b){ > + vec z=a!=a; > + vec o=z+1; > + vec c=(a>3)?o:z; > + vec d=(b>2)?o:z; > + vec e=c&d; > + return e!=0; > +} > + > +vec g(vec a,vec b){ > + vec z=a!=a; > + vec c=(a<=42)?b:z; > + return b&c; > +} > + > +/* { dg-final { scan-tree-dump-times "VEC_COND_EXPR" 2 "forwprop1" } } */ > +/* { dg-final { scan-tree-dump-not "!=" "forwprop1" } } */ > +/* { dg-final { scan-tree-dump-not "&" "forwprop1" } } */ > +/* { dg-final { cleanup-tree-dump "forwprop1" } } */ > > Property changes on: testsuite/g++.dg/tree-ssa/pr57755.c > ___________________________________________________________________ > Added: svn:eol-style > + native > Added: svn:keywords > + Author Date Id Revision URL > > > Index: testsuite/g++.dg/tree-ssa/pr57755.C > =================================================================== > --- testsuite/g++.dg/tree-ssa/pr57755.C (revision 0) > +++ testsuite/g++.dg/tree-ssa/pr57755.C (revision 0) > @@ -0,0 +1,23 @@ > +/* { dg-do compile } */ > +/* { dg-options "-O -fdump-tree-forwprop1" } */ > +typedef int vec __attribute__((vector_size(4*sizeof(int)))); > + > +vec f(vec a,vec b){ > + vec z=a!=a; > + vec o=z+1; > + vec c=(a>3)?o:z; > + vec d=(b>2)?o:z; > + vec e=c&d; > + return e!=0; > +} > + > +vec g(vec a,vec b){ > + vec z=a!=a; > + vec c=(a<=42)?b:z; > + return b&c; > +} > + > +/* { dg-final { scan-tree-dump-times "VEC_COND_EXPR" 2 "forwprop1" } } */ > +/* { dg-final { scan-tree-dump-not "!=" "forwprop1" } } */ > +/* { dg-final { scan-tree-dump-not "&" "forwprop1" } } */ > +/* { dg-final { cleanup-tree-dump "forwprop1" } } */ > > Property changes on: testsuite/g++.dg/tree-ssa/pr57755.C > ___________________________________________________________________ > Added: svn:keywords > + Author Date Id Revision URL > Added: svn:eol-style > + native > > Index: fold-const.c > =================================================================== > --- fold-const.c (revision 200736) > +++ fold-const.c (working copy) > @@ -14124,21 +14124,23 @@ fold_ternary_loc (location_t loc, enum t > > /* Convert A ? 1 : 0 to simply A. */ > if ((code == VEC_COND_EXPR ? integer_all_onesp (op1) > : (integer_onep (op1) > && !VECTOR_TYPE_P (type))) > && integer_zerop (op2) > /* If we try to convert OP0 to our type, the > call to fold will try to move the conversion inside > a COND, which will recurse. In that case, the COND_EXPR > is probably the best choice, so leave it alone. */ > - && type == TREE_TYPE (arg0)) > + && (type == TREE_TYPE (arg0) > + || (in_gimple_form && code == VEC_COND_EXPR > + && useless_type_conversion_p (type, TREE_TYPE (arg0))))) > return pedantic_non_lvalue_loc (loc, arg0); > > /* Convert A ? 0 : 1 to !A. This prefers the use of NOT_EXPR > over COND_EXPR in cases such as floating point comparisons. */ > if (integer_zerop (op1) > && (code == VEC_COND_EXPR ? integer_all_onesp (op2) > : (integer_onep (op2) > && !VECTOR_TYPE_P (type))) > && truth_value_p (TREE_CODE (arg0))) > return pedantic_non_lvalue_loc (loc, > Index: tree-ssa-forwprop.c > =================================================================== > --- tree-ssa-forwprop.c (revision 200736) > +++ tree-ssa-forwprop.c (working copy) > @@ -1135,20 +1135,131 @@ forward_propagate_comparison (gimple_stm > > /* Remove defining statements. */ > return remove_prop_source_from_use (name); > > bailout: > gsi_next (defgsi); > return false; > } > > > +/* Combine the binary operation defined in *GSI with one of its arguments > + that is a condition. > + Returns 1 if there were any changes made, 2 if cfg-cleanup needs to > + run. Else it returns 0. */ > + > +static int > +combine_binop_with_condition (gimple_stmt_iterator *gsi) > +{ > + gimple stmt = gsi_stmt (*gsi); > + tree type = TREE_TYPE (gimple_assign_lhs (stmt)); > + enum tree_code code = gimple_assign_rhs_code (stmt); > + tree rhs1 = gimple_assign_rhs1 (stmt); > + tree rhs2 = gimple_assign_rhs2 (stmt); > + gimple def_stmt; > + enum tree_code defcode; > + bool trueok = false; > + bool falseok = false; > + tree true_op, false_op; > + location_t loc = gimple_location (stmt); > + > + if (TREE_CODE (rhs1) != SSA_NAME) > + goto second_op; > + > + def_stmt = get_prop_source_stmt (rhs1, true, NULL); > + if (!def_stmt || !can_propagate_from (def_stmt)) > + goto second_op; > + > + defcode = gimple_assign_rhs_code (def_stmt); > + if (defcode != COND_EXPR && defcode != VEC_COND_EXPR) > + goto second_op; > + > + true_op = fold_build2_loc (loc, code, type, gimple_assign_rhs2 > (def_stmt), > + gimple_assign_rhs2 (stmt)); > + false_op = fold_build2_loc (loc, code, type, gimple_assign_rhs3 > (def_stmt), > + gimple_assign_rhs2 (stmt)); > + > + if (is_gimple_val (true_op)) > + trueok = true; > + if (is_gimple_val (false_op)) > + falseok = true; > + /* At least one of them has to simplify, or it isn't worth it. */ > + if (!trueok && !falseok) > + goto second_op; > + if (!trueok) > + { > + if (!valid_gimple_rhs_p (true_op)) > + goto second_op; > + gimple g = gimple_build_assign (make_ssa_name (type, NULL), true_op); > + true_op = gimple_assign_lhs (g); > + gsi_insert_before (gsi, g, GSI_SAME_STMT); > + } > + if (!falseok) > + { > + if (!valid_gimple_rhs_p (false_op)) > + goto second_op; > + gimple g = gimple_build_assign (make_ssa_name (type, NULL), > false_op); > + false_op = gimple_assign_lhs (g); > + gsi_insert_before (gsi, g, GSI_SAME_STMT); > + } > + goto finish; > + > +second_op: > + if (TREE_CODE (rhs2) != SSA_NAME) > + return 0; > + > + def_stmt = get_prop_source_stmt (rhs2, true, NULL); > + if (!def_stmt || !can_propagate_from (def_stmt)) > + return 0; > + > + defcode = gimple_assign_rhs_code (def_stmt); > + if (defcode != COND_EXPR && defcode != VEC_COND_EXPR) > + return 0; > + > + true_op = fold_build2_loc (loc, code, type, gimple_assign_rhs1 (stmt), > + gimple_assign_rhs2 (def_stmt)); > + false_op = fold_build2_loc (loc, code, type, gimple_assign_rhs1 (stmt), > + gimple_assign_rhs3 (def_stmt)); > + > + trueok = is_gimple_val (true_op); > + falseok = is_gimple_val (false_op); > + /* At least one of them has to simplify, or it isn't worth it. */ > + if (!trueok && !falseok) > + return 0; > + if (!trueok) > + { > + if (!valid_gimple_rhs_p (true_op)) > + return 0; > + gimple g = gimple_build_assign (make_ssa_name (type, NULL), true_op); > + true_op = gimple_assign_lhs (g); > + gsi_insert_before (gsi, g, GSI_SAME_STMT); > + } > + if (!falseok) > + { > + if (!valid_gimple_rhs_p (false_op)) > + return 0; > + gimple g = gimple_build_assign (make_ssa_name (type, NULL), > false_op); > + false_op = gimple_assign_lhs (g); > + gsi_insert_before (gsi, g, GSI_SAME_STMT); > + } > +finish: > + gimple_assign_set_rhs_with_ops_1 (gsi, defcode, gimple_assign_rhs1 > (def_stmt), > + true_op, false_op); > + > + fold_stmt (gsi); > + update_stmt (gsi_stmt (*gsi)); > + > + /* Remove defining statements. */ > + return remove_prop_source_from_use (gimple_assign_lhs (def_stmt)) + 1; > +} > + > + > /* GSI_P points to a statement which performs a narrowing integral > conversion. > > Look for cases like: > > t = x & c; > y = (T) t; > > Turn them into: > > @@ -3403,21 +3514,35 @@ ssa_forward_propagate_and_combine (void) > /* Mark stmt as potentially needing revisiting. */ > gimple_set_plf (stmt, GF_PLF_1, false); > > switch (gimple_code (stmt)) > { > case GIMPLE_ASSIGN: > { > tree rhs1 = gimple_assign_rhs1 (stmt); > enum tree_code code = gimple_assign_rhs_code (stmt); > > - if ((code == BIT_NOT_EXPR > + /* Something (associate_plusminus?) doesn't set "changed" > + properly, so we can't put this at the end with > + if (!changed && ...). */ > + if (TREE_CODE_CLASS (code) == tcc_binary > + || TREE_CODE_CLASS (code) == tcc_comparison) > + { > + int did_something; > + did_something = combine_binop_with_condition (&gsi); > + if (did_something == 2) > + cfg_changed = true; > + changed = did_something != 0; > + } > + if (changed) > + ; > + else if ((code == BIT_NOT_EXPR > || code == NEGATE_EXPR) > && TREE_CODE (rhs1) == SSA_NAME) > changed = simplify_not_neg_expr (&gsi); > else if (code == COND_EXPR > || code == VEC_COND_EXPR) > { > /* In this case the entire COND_EXPR is in rhs1. */ > if (forward_propagate_into_cond (&gsi) > || combine_cond_exprs (&gsi)) > { >
