[PATCH] Fix PR58143 and dups

[Bernd Edlinger]

Hi,

On Tue, 15 Oct 2013 15:57:16, Richard Biener 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.
>

Thanks.

Your patch looks good to me.

Although this approach also has a price:
That is rewriting the statement from signed to unsigned arithmetic
may masquerade the possible undefined behaviour to the loop optimization.

Bernd.


> 2013-10-15 Richard Biener <rguenther@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))
> ! && (!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;
> + }