| Message ID | 20140110202811.GF892@tucnak.redhat.com |
|---|---|
| State | New |
| Headers | show |
On Fri, 10 Jan 2014, Jakub Jelinek wrote: > Hi! > > If folded_casts is true, sccp can introduce undefined behavior even when > there was none in the original loop, e.g. all actual additions performed in > unsigned type and then cast back to signed. > > The following patch fixes that by turning the arithmetic stmts added by sccp > use unsigned operations if folded_casts and def's type has undefined > overflow behavior. > > Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk? > > 2014-01-10 Jakub Jelinek <jakub@redhat.com> > > PR tree-optimization/59387 > * tree-scalar-evolution.c: Include gimple-fold.h and gimplify-me.h. > (scev_const_prop): If folded_casts and type has undefined overflow, > use force_gimple_operand instead of force_gimple_operand_gsi and > for each added stmt if it is assign with > arith_code_with_undefined_signed_overflow, call > rewrite_to_defined_overflow. > * tree-ssa-loop-im.c: Don't include gimplify-me.h, include > gimple-fold.h instead. > (arith_code_with_undefined_signed_overflow, > rewrite_to_defined_overflow): Moved to ... > * gimple-fold.c (arith_code_with_undefined_signed_overflow, > rewrite_to_defined_overflow): ... here. No longer static. > Include gimplify-me.h. > * gimple-fold.h (arith_code_with_undefined_signed_overflow, > rewrite_to_defined_overflow): New prototypes. > > * gcc.c-torture/execute/pr59387.c: New test. > > --- gcc/tree-scalar-evolution.c.jj 2014-01-08 17:44:57.596582925 +0100 > +++ gcc/tree-scalar-evolution.c 2014-01-10 15:46:55.355915072 +0100 > @@ -286,6 +286,8 @@ along with GCC; see the file COPYING3. > #include "dumpfile.h" > #include "params.h" > #include "tree-ssa-propagate.h" > +#include "gimple-fold.h" > +#include "gimplify-me.h" > > static tree analyze_scalar_evolution_1 (struct loop *, tree, tree); > static tree analyze_scalar_evolution_for_address_of (struct loop *loop, > @@ -3409,7 +3411,7 @@ scev_const_prop (void) > { > edge exit; > tree def, rslt, niter; > - gimple_stmt_iterator bsi; > + gimple_stmt_iterator gsi; > > /* If we do not know exact number of iterations of the loop, we cannot > replace the final value. */ > @@ -3424,7 +3426,7 @@ scev_const_prop (void) > /* Ensure that it is possible to insert new statements somewhere. */ > if (!single_pred_p (exit->dest)) > split_loop_exit_edge (exit); > - bsi = gsi_after_labels (exit->dest); > + gsi = gsi_after_labels (exit->dest); > > ex_loop = superloop_at_depth (loop, > loop_depth (exit->dest->loop_father) + 1); > @@ -3447,7 +3449,9 @@ scev_const_prop (void) > continue; > } > > - def = analyze_scalar_evolution_in_loop (ex_loop, loop, def, NULL); > + bool folded_casts; > + def = analyze_scalar_evolution_in_loop (ex_loop, loop, def, > + &folded_casts); > def = compute_overall_effect_of_inner_loop (ex_loop, def); > if (!tree_does_not_contain_chrecs (def) > || chrec_contains_symbols_defined_in_loop (def, ex_loop->num) > @@ -3485,10 +3489,38 @@ scev_const_prop (void) > def = unshare_expr (def); > remove_phi_node (&psi, false); > > - def = force_gimple_operand_gsi (&bsi, def, false, NULL_TREE, > - true, GSI_SAME_STMT); > + if (TREE_CODE (def) == INTEGER_CST && TREE_OVERFLOW (def)) TREE_OVERFLOW_P (), but it seems to me that the SCEV machinery should do this at a good place (like where it finally records the result into its cache before returning it, at set_and_end: of analyze_scalar_evolution_1). > + def = drop_tree_overflow (def); > + > + /* If def's type has undefined overflow and there were folded > + casts, rewrite all stmts added for def into arithmetics > + with defined overflow behavior. */ > + if (folded_casts && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (def))) > + { > + gimple_seq stmts; > + gimple_stmt_iterator gsi2; > + def = force_gimple_operand (def, &stmts, true, NULL_TREE); > + gsi2 = gsi_start (stmts); > + while (!gsi_end_p (gsi2)) > + { > + gimple stmt = gsi_stmt (gsi2); > + gsi_next (&gsi2); > + if (is_gimple_assign (stmt) > + && arith_code_with_undefined_signed_overflow > + (gimple_assign_rhs_code (stmt))) > + gsi_insert_seq_before (&gsi, > + rewrite_to_defined_overflow (stmt), > + GSI_SAME_STMT); Hmm, stmt is still in the 'stmts' sequence here, I think you should gsi_remove it before inserting it elsewhere. > + else > + gsi_insert_before (&gsi, stmt, GSI_SAME_STMT); Also applies here, of course. Otherwise ok. Thanks, Richard. > + } > + } > + else > + def = force_gimple_operand_gsi (&gsi, def, false, NULL_TREE, > + true, GSI_SAME_STMT); > + > ass = gimple_build_assign (rslt, def); > - gsi_insert_before (&bsi, ass, GSI_SAME_STMT); > + gsi_insert_before (&gsi, ass, GSI_SAME_STMT); > if (dump_file) > { > print_gimple_stmt (dump_file, ass, 0, 0); > --- gcc/tree-ssa-loop-im.c.jj 2014-01-03 11:40:29.000000000 +0100 > +++ gcc/tree-ssa-loop-im.c 2014-01-10 15:34:32.512734315 +0100 > @@ -35,7 +35,6 @@ along with GCC; see the file COPYING3. > #include "gimple.h" > #include "gimplify.h" > #include "gimple-iterator.h" > -#include "gimplify-me.h" > #include "gimple-ssa.h" > #include "tree-cfg.h" > #include "tree-phinodes.h" > @@ -53,6 +52,7 @@ along with GCC; see the file COPYING3. > #include "tree-affine.h" > #include "tree-ssa-propagate.h" > #include "trans-mem.h" > +#include "gimple-fold.h" > > /* TODO: Support for predicated code motion. I.e. > > @@ -1135,67 +1135,6 @@ public: > unsigned int todo_; > }; > > -/* Return true if CODE is an operation that when operating on signed > - integer types involves undefined behavior on overflow and the > - operation can be expressed with unsigned arithmetic. */ > - > -static bool > -arith_code_with_undefined_signed_overflow (tree_code code) > -{ > - switch (code) > - { > - case PLUS_EXPR: > - case MINUS_EXPR: > - case MULT_EXPR: > - case NEGATE_EXPR: > - case POINTER_PLUS_EXPR: > - return true; > - default: > - return false; > - } > -} > - > -/* Rewrite STMT, an assignment with a signed integer or pointer arithmetic > - operation that can be transformed to unsigned arithmetic by converting > - its operand, carrying out the operation in the corresponding unsigned > - type and converting the result back to the original type. > - > - Returns a sequence of statements that replace STMT and also contain > - a modified form of STMT itself. */ > - > -static gimple_seq > -rewrite_to_defined_overflow (gimple stmt) > -{ > - if (dump_file && (dump_flags & TDF_DETAILS)) > - { > - fprintf (dump_file, "rewriting stmt with undefined signed " > - "overflow "); > - print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); > - } > - > - tree lhs = gimple_assign_lhs (stmt); > - tree type = unsigned_type_for (TREE_TYPE (lhs)); > - gimple_seq stmts = NULL; > - for (unsigned i = 1; i < gimple_num_ops (stmt); ++i) > - { > - gimple_seq stmts2 = NULL; > - gimple_set_op (stmt, i, > - force_gimple_operand (fold_convert (type, > - gimple_op (stmt, i)), > - &stmts2, true, NULL_TREE)); > - gimple_seq_add_seq (&stmts, stmts2); > - } > - gimple_assign_set_lhs (stmt, make_ssa_name (type, stmt)); > - if (gimple_assign_rhs_code (stmt) == POINTER_PLUS_EXPR) > - gimple_assign_set_rhs_code (stmt, PLUS_EXPR); > - gimple_seq_add_stmt (&stmts, stmt); > - gimple cvt = gimple_build_assign_with_ops > - (NOP_EXPR, lhs, gimple_assign_lhs (stmt), NULL_TREE); > - gimple_seq_add_stmt (&stmts, cvt); > - > - return stmts; > -} > - > /* Hoist the statements in basic block BB out of the loops prescribed by > data stored in LIM_DATA structures associated with each statement. Callback > for walk_dominator_tree. */ > --- gcc/gimple-fold.c.jj 2014-01-09 21:08:41.000000000 +0100 > +++ gcc/gimple-fold.c 2014-01-10 15:34:02.274882625 +0100 > @@ -51,6 +51,7 @@ along with GCC; see the file COPYING3. > #include "gimple-pretty-print.h" > #include "tree-ssa-address.h" > #include "langhooks.h" > +#include "gimplify-me.h" > > /* Return true when DECL can be referenced from current unit. > FROM_DECL (if non-null) specify constructor of variable DECL was taken from. > @@ -3548,3 +3549,64 @@ gimple_fold_indirect_ref (tree t) > > return NULL_TREE; > } > + > +/* Return true if CODE is an operation that when operating on signed > + integer types involves undefined behavior on overflow and the > + operation can be expressed with unsigned arithmetic. */ > + > +bool > +arith_code_with_undefined_signed_overflow (tree_code code) > +{ > + switch (code) > + { > + case PLUS_EXPR: > + case MINUS_EXPR: > + case MULT_EXPR: > + case NEGATE_EXPR: > + case POINTER_PLUS_EXPR: > + return true; > + default: > + return false; > + } > +} > + > +/* Rewrite STMT, an assignment with a signed integer or pointer arithmetic > + operation that can be transformed to unsigned arithmetic by converting > + its operand, carrying out the operation in the corresponding unsigned > + type and converting the result back to the original type. > + > + Returns a sequence of statements that replace STMT and also contain > + a modified form of STMT itself. */ > + > +gimple_seq > +rewrite_to_defined_overflow (gimple stmt) > +{ > + if (dump_file && (dump_flags & TDF_DETAILS)) > + { > + fprintf (dump_file, "rewriting stmt with undefined signed " > + "overflow "); > + print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); > + } > + > + tree lhs = gimple_assign_lhs (stmt); > + tree type = unsigned_type_for (TREE_TYPE (lhs)); > + gimple_seq stmts = NULL; > + for (unsigned i = 1; i < gimple_num_ops (stmt); ++i) > + { > + gimple_seq stmts2 = NULL; > + gimple_set_op (stmt, i, > + force_gimple_operand (fold_convert (type, > + gimple_op (stmt, i)), > + &stmts2, true, NULL_TREE)); > + gimple_seq_add_seq (&stmts, stmts2); > + } > + gimple_assign_set_lhs (stmt, make_ssa_name (type, stmt)); > + if (gimple_assign_rhs_code (stmt) == POINTER_PLUS_EXPR) > + gimple_assign_set_rhs_code (stmt, PLUS_EXPR); > + gimple_seq_add_stmt (&stmts, stmt); > + gimple cvt = gimple_build_assign_with_ops > + (NOP_EXPR, lhs, gimple_assign_lhs (stmt), NULL_TREE); > + gimple_seq_add_stmt (&stmts, cvt); > + > + return stmts; > +} > --- gcc/gimple-fold.h.jj 2014-01-03 11:40:57.000000000 +0100 > +++ gcc/gimple-fold.h 2014-01-10 15:25:32.705493146 +0100 > @@ -40,5 +40,7 @@ extern tree fold_const_aggregate_ref (tr > extern tree gimple_get_virt_method_for_binfo (HOST_WIDE_INT, tree); > extern bool gimple_val_nonnegative_real_p (tree); > extern tree gimple_fold_indirect_ref (tree); > +extern bool arith_code_with_undefined_signed_overflow (tree_code); > +extern gimple_seq rewrite_to_defined_overflow (gimple); > > #endif /* GCC_GIMPLE_FOLD_H */ > --- gcc/testsuite/gcc.c-torture/execute/pr59387.c.jj 2014-01-10 14:36:03.476754070 +0100 > +++ gcc/testsuite/gcc.c-torture/execute/pr59387.c 2014-01-10 14:36:03.476754070 +0100 > @@ -0,0 +1,19 @@ > +/* PR tree-optimization/59387 */ > + > +int a, *d, **e = &d, f; > +char c; > +struct S { int f1; } b; > + > +int > +main () > +{ > + for (a = -19; a; a++) > + { > + for (b.f1 = 0; b.f1 < 24; b.f1++) > + c--; > + *e = &f; > + if (!d) > + return 0; > + } > + return 0; > +} > > Jakub > >
--- gcc/tree-scalar-evolution.c.jj 2014-01-08 17:44:57.596582925 +0100 +++ gcc/tree-scalar-evolution.c 2014-01-10 15:46:55.355915072 +0100 @@ -286,6 +286,8 @@ along with GCC; see the file COPYING3. #include "dumpfile.h" #include "params.h" #include "tree-ssa-propagate.h" +#include "gimple-fold.h" +#include "gimplify-me.h" static tree analyze_scalar_evolution_1 (struct loop *, tree, tree); static tree analyze_scalar_evolution_for_address_of (struct loop *loop, @@ -3409,7 +3411,7 @@ scev_const_prop (void) { edge exit; tree def, rslt, niter; - gimple_stmt_iterator bsi; + gimple_stmt_iterator gsi; /* If we do not know exact number of iterations of the loop, we cannot replace the final value. */ @@ -3424,7 +3426,7 @@ scev_const_prop (void) /* Ensure that it is possible to insert new statements somewhere. */ if (!single_pred_p (exit->dest)) split_loop_exit_edge (exit); - bsi = gsi_after_labels (exit->dest); + gsi = gsi_after_labels (exit->dest); ex_loop = superloop_at_depth (loop, loop_depth (exit->dest->loop_father) + 1); @@ -3447,7 +3449,9 @@ scev_const_prop (void) continue; } - def = analyze_scalar_evolution_in_loop (ex_loop, loop, def, NULL); + bool folded_casts; + def = analyze_scalar_evolution_in_loop (ex_loop, loop, def, + &folded_casts); def = compute_overall_effect_of_inner_loop (ex_loop, def); if (!tree_does_not_contain_chrecs (def) || chrec_contains_symbols_defined_in_loop (def, ex_loop->num) @@ -3485,10 +3489,38 @@ scev_const_prop (void) def = unshare_expr (def); remove_phi_node (&psi, false); - def = force_gimple_operand_gsi (&bsi, def, false, NULL_TREE, - true, GSI_SAME_STMT); + if (TREE_CODE (def) == INTEGER_CST && TREE_OVERFLOW (def)) + def = drop_tree_overflow (def); + + /* If def's type has undefined overflow and there were folded + casts, rewrite all stmts added for def into arithmetics + with defined overflow behavior. */ + if (folded_casts && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (def))) + { + gimple_seq stmts; + gimple_stmt_iterator gsi2; + def = force_gimple_operand (def, &stmts, true, NULL_TREE); + gsi2 = gsi_start (stmts); + while (!gsi_end_p (gsi2)) + { + gimple stmt = gsi_stmt (gsi2); + gsi_next (&gsi2); + if (is_gimple_assign (stmt) + && arith_code_with_undefined_signed_overflow + (gimple_assign_rhs_code (stmt))) + gsi_insert_seq_before (&gsi, + rewrite_to_defined_overflow (stmt), + GSI_SAME_STMT); + else + gsi_insert_before (&gsi, stmt, GSI_SAME_STMT); + } + } + else + def = force_gimple_operand_gsi (&gsi, def, false, NULL_TREE, + true, GSI_SAME_STMT); + ass = gimple_build_assign (rslt, def); - gsi_insert_before (&bsi, ass, GSI_SAME_STMT); + gsi_insert_before (&gsi, ass, GSI_SAME_STMT); if (dump_file) { print_gimple_stmt (dump_file, ass, 0, 0); --- gcc/tree-ssa-loop-im.c.jj 2014-01-03 11:40:29.000000000 +0100 +++ gcc/tree-ssa-loop-im.c 2014-01-10 15:34:32.512734315 +0100 @@ -35,7 +35,6 @@ along with GCC; see the file COPYING3. #include "gimple.h" #include "gimplify.h" #include "gimple-iterator.h" -#include "gimplify-me.h" #include "gimple-ssa.h" #include "tree-cfg.h" #include "tree-phinodes.h" @@ -53,6 +52,7 @@ along with GCC; see the file COPYING3. #include "tree-affine.h" #include "tree-ssa-propagate.h" #include "trans-mem.h" +#include "gimple-fold.h" /* TODO: Support for predicated code motion. I.e. @@ -1135,67 +1135,6 @@ public: unsigned int todo_; }; -/* Return true if CODE is an operation that when operating on signed - integer types involves undefined behavior on overflow and the - operation can be expressed with unsigned arithmetic. */ - -static bool -arith_code_with_undefined_signed_overflow (tree_code code) -{ - switch (code) - { - case PLUS_EXPR: - case MINUS_EXPR: - case MULT_EXPR: - case NEGATE_EXPR: - case POINTER_PLUS_EXPR: - return true; - default: - return false; - } -} - -/* Rewrite STMT, an assignment with a signed integer or pointer arithmetic - operation that can be transformed to unsigned arithmetic by converting - its operand, carrying out the operation in the corresponding unsigned - type and converting the result back to the original type. - - Returns a sequence of statements that replace STMT and also contain - a modified form of STMT itself. */ - -static gimple_seq -rewrite_to_defined_overflow (gimple stmt) -{ - if (dump_file && (dump_flags & TDF_DETAILS)) - { - fprintf (dump_file, "rewriting stmt with undefined signed " - "overflow "); - print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); - } - - tree lhs = gimple_assign_lhs (stmt); - tree type = unsigned_type_for (TREE_TYPE (lhs)); - gimple_seq stmts = NULL; - for (unsigned i = 1; i < gimple_num_ops (stmt); ++i) - { - gimple_seq stmts2 = NULL; - gimple_set_op (stmt, i, - force_gimple_operand (fold_convert (type, - gimple_op (stmt, i)), - &stmts2, true, NULL_TREE)); - gimple_seq_add_seq (&stmts, stmts2); - } - gimple_assign_set_lhs (stmt, make_ssa_name (type, stmt)); - if (gimple_assign_rhs_code (stmt) == POINTER_PLUS_EXPR) - gimple_assign_set_rhs_code (stmt, PLUS_EXPR); - gimple_seq_add_stmt (&stmts, stmt); - gimple cvt = gimple_build_assign_with_ops - (NOP_EXPR, lhs, gimple_assign_lhs (stmt), NULL_TREE); - gimple_seq_add_stmt (&stmts, cvt); - - return stmts; -} - /* Hoist the statements in basic block BB out of the loops prescribed by data stored in LIM_DATA structures associated with each statement. Callback for walk_dominator_tree. */ --- gcc/gimple-fold.c.jj 2014-01-09 21:08:41.000000000 +0100 +++ gcc/gimple-fold.c 2014-01-10 15:34:02.274882625 +0100 @@ -51,6 +51,7 @@ along with GCC; see the file COPYING3. #include "gimple-pretty-print.h" #include "tree-ssa-address.h" #include "langhooks.h" +#include "gimplify-me.h" /* Return true when DECL can be referenced from current unit. FROM_DECL (if non-null) specify constructor of variable DECL was taken from. @@ -3548,3 +3549,64 @@ gimple_fold_indirect_ref (tree t) return NULL_TREE; } + +/* Return true if CODE is an operation that when operating on signed + integer types involves undefined behavior on overflow and the + operation can be expressed with unsigned arithmetic. */ + +bool +arith_code_with_undefined_signed_overflow (tree_code code) +{ + switch (code) + { + case PLUS_EXPR: + case MINUS_EXPR: + case MULT_EXPR: + case NEGATE_EXPR: + case POINTER_PLUS_EXPR: + return true; + default: + return false; + } +} + +/* Rewrite STMT, an assignment with a signed integer or pointer arithmetic + operation that can be transformed to unsigned arithmetic by converting + its operand, carrying out the operation in the corresponding unsigned + type and converting the result back to the original type. + + Returns a sequence of statements that replace STMT and also contain + a modified form of STMT itself. */ + +gimple_seq +rewrite_to_defined_overflow (gimple stmt) +{ + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "rewriting stmt with undefined signed " + "overflow "); + print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); + } + + tree lhs = gimple_assign_lhs (stmt); + tree type = unsigned_type_for (TREE_TYPE (lhs)); + gimple_seq stmts = NULL; + for (unsigned i = 1; i < gimple_num_ops (stmt); ++i) + { + gimple_seq stmts2 = NULL; + gimple_set_op (stmt, i, + force_gimple_operand (fold_convert (type, + gimple_op (stmt, i)), + &stmts2, true, NULL_TREE)); + gimple_seq_add_seq (&stmts, stmts2); + } + gimple_assign_set_lhs (stmt, make_ssa_name (type, stmt)); + if (gimple_assign_rhs_code (stmt) == POINTER_PLUS_EXPR) + gimple_assign_set_rhs_code (stmt, PLUS_EXPR); + gimple_seq_add_stmt (&stmts, stmt); + gimple cvt = gimple_build_assign_with_ops + (NOP_EXPR, lhs, gimple_assign_lhs (stmt), NULL_TREE); + gimple_seq_add_stmt (&stmts, cvt); + + return stmts; +} --- gcc/gimple-fold.h.jj 2014-01-03 11:40:57.000000000 +0100 +++ gcc/gimple-fold.h 2014-01-10 15:25:32.705493146 +0100 @@ -40,5 +40,7 @@ extern tree fold_const_aggregate_ref (tr extern tree gimple_get_virt_method_for_binfo (HOST_WIDE_INT, tree); extern bool gimple_val_nonnegative_real_p (tree); extern tree gimple_fold_indirect_ref (tree); +extern bool arith_code_with_undefined_signed_overflow (tree_code); +extern gimple_seq rewrite_to_defined_overflow (gimple); #endif /* GCC_GIMPLE_FOLD_H */ --- gcc/testsuite/gcc.c-torture/execute/pr59387.c.jj 2014-01-10 14:36:03.476754070 +0100 +++ gcc/testsuite/gcc.c-torture/execute/pr59387.c 2014-01-10 14:36:03.476754070 +0100 @@ -0,0 +1,19 @@ +/* PR tree-optimization/59387 */ + +int a, *d, **e = &d, f; +char c; +struct S { int f1; } b; + +int +main () +{ + for (a = -19; a; a++) + { + for (b.f1 = 0; b.f1 < 24; b.f1++) + c--; + *e = &f; + if (!d) + return 0; + } + return 0; +}