On Tue, Oct 15, 2013 at 6:57 AM Richard Biener <rguent...@suse.de> wrote:
>
>
> This is an alternate fix (see
> http://gcc.gnu.org/ml/gcc-patches/2013-09/msg00234.html for the other
> one) for the various PRs that show that LIM exposes undefined
> signed overflow on paths where it wasn't executed before LIM
> ultimately leading to a miscompilation.
>
> For this fix we rewrite invariant stmts to use unsigned arithmetic
> when it is one of the operations that SCEV and niter analysis
> handles (thus not division or absolute). The other fix instead
> disables invariant motion for those expressions.
>
> Bootstrapped and tested on x86_64-unknown-linux-gnu.
>
> The issue is also present on the 4.8 branch, so either patch
> should be backported in the end. I will try to benchmark
> both tomorrow (unless somebody beats me on that).
>
> Any preference or other suggestions?
>
> Thanks,
> Richard.
>
> 2013-10-15 Richard Biener <rguent...@suse.de>
>
> PR tree-optimization/58143
> * tree-ssa-loop-im.c (arith_code_with_undefined_signed_overflow):
> New function.
> (rewrite_to_defined_overflow): Likewise.
> (move_computations_dom_walker::before_dom): Rewrite stmts
> with undefined signed overflow that are not always executed
> into unsigned arithmetic.
>
> * gcc.dg/torture/pr58143-1.c: New testcase.
> * gcc.dg/torture/pr58143-2.c: Likewise.
> * gcc.dg/torture/pr58143-3.c: Likewise.
>
> Index: gcc/tree-ssa-loop-im.c
> ===================================================================
> *** gcc/tree-ssa-loop-im.c (revision 203600)
> --- gcc/tree-ssa-loop-im.c (working copy)
> *************** public:
> *** 1117,1122 ****
> --- 1117,1183 ----
> 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. */
> *************** move_computations_dom_walker::before_dom
> *** 1247,1253 ****
> }
> }
> gsi_remove (&bsi, false);
> ! gsi_insert_on_edge (e, stmt);
> }
> }
>
> --- 1308,1328 ----
> }
> }
> gsi_remove (&bsi, false);
> ! /* In case this is a stmt that is not unconditionally executed
> ! when the target loop header is executed and the stmt may
> ! invoke undefined integer or pointer overflow rewrite it to
> ! unsigned arithmetic. */
> ! if (is_gimple_assign (stmt)
> ! && INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_lhs (stmt)))
> ! && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (gimple_assign_lhs (stmt)))
> ! && arith_code_with_undefined_signed_overflow
> ! (gimple_assign_rhs_code (stmt))
I was trying to consolidate the checks into a single function which
checked before calling rewrite_to_defined_overflow and noticed that
this above check and the comment disagree. The comment talks about
pointers but pointers are not handled in the code.
If we do pointers also for rewrite_to_defined_overflow;
gcc.c-torture/execute/pr111422.c starts to fail at -O3 as the
workaround for the stack reuse issue is no longer working for some
reason.
Should we fix the comment and not call rewrite_to_defined_overflow for
pointers or is the fix to add the check for pointers and xfail
pr111422.c for -O3 and open a new bug?
Thanks,
Andrew
> ! && (!ALWAYS_EXECUTED_IN (bb)
> ! || !(ALWAYS_EXECUTED_IN (bb) == level
> ! || flow_loop_nested_p (ALWAYS_EXECUTED_IN (bb), level))))
> ! gsi_insert_seq_on_edge (e, rewrite_to_defined_overflow (stmt));
> ! else
> ! gsi_insert_on_edge (e, stmt);
> }
> }
>
> Index: gcc/testsuite/gcc.dg/torture/pr58143-1.c
> ===================================================================
> *** gcc/testsuite/gcc.dg/torture/pr58143-1.c (revision 0)
> --- gcc/testsuite/gcc.dg/torture/pr58143-1.c (working copy)
> ***************
> *** 0 ****
> --- 1,51 ----
> + /* { dg-do run } */
> + /* { dg-additional-options "-fstrict-overflow" } */
> +
> + extern void abort (void);
> +
> + int a, b, c, d, e, f, g, h = 1, i;
> +
> + int foo (int p)
> + {
> + return p < 0 && a < - __INT_MAX__ - 1 - p ? 0 : 1;
> + }
> +
> + int *bar ()
> + {
> + int j;
> + i = h ? 0 : 1 % h;
> + for (j = 0; j < 1; j++)
> + for (d = 0; d; d++)
> + for (e = 1; e;)
> + return 0;
> + return 0;
> + }
> +
> + int baz ()
> + {
> + for (; b >= 0; b--)
> + for (c = 1; c >= 0; c--)
> + {
> + int *k = &c;
> + for (;;)
> + {
> + for (f = 0; f < 1; f++)
> + {
> + g = foo (*k);
> + bar ();
> + }
> + if (*k)
> + break;
> + return 0;
> + }
> + }
> + return 0;
> + }
> +
> + int main ()
> + {
> + baz ();
> + if (b != 0)
> + abort ();
> + return 0;
> + }
> Index: gcc/testsuite/gcc.dg/torture/pr58143-2.c
> ===================================================================
> *** gcc/testsuite/gcc.dg/torture/pr58143-2.c (revision 0)
> --- gcc/testsuite/gcc.dg/torture/pr58143-2.c (working copy)
> ***************
> *** 0 ****
> --- 1,34 ----
> + /* { dg-do run } */
> + /* { dg-additional-options "-fstrict-overflow" } */
> +
> + int a, b, d, e, f, *g, h, i;
> + volatile int c;
> +
> + char foo (unsigned char p)
> + {
> + return p + 1;
> + }
> +
> + int bar ()
> + {
> + for (h = 0; h < 3; h = foo (h))
> + {
> + c;
> + for (f = 0; f < 1; f++)
> + {
> + i = a && 0 < -__INT_MAX__ - h ? 0 : 1;
> + if (e)
> + for (; d;)
> + b = 0;
> + else
> + g = 0;
> + }
> + }
> + return 0;
> + }
> +
> + int main ()
> + {
> + bar ();
> + return 0;
> + }
> Index: gcc/testsuite/gcc.dg/torture/pr58143-3.c
> ===================================================================
> *** gcc/testsuite/gcc.dg/torture/pr58143-3.c (revision 0)
> --- gcc/testsuite/gcc.dg/torture/pr58143-3.c (working copy)
> ***************
> *** 0 ****
> --- 1,18 ----
> + /* { dg-do run } */
> + /* { dg-additional-options "-fstrict-overflow" } */
> +
> + int a, b, c, d, e;
> +
> + int
> + main ()
> + {
> + for (b = 4; b > -30; b--)
> + for (; c;)
> + for (;;)
> + {
> + e = a > __INT_MAX__ - b;
> + if (d)
> + break;
> + }
> + return 0;
> + }
