| Message ID | 20121109184142.597e9d2c@spoyarek |
|---|---|
| State | New |
| Headers | show |
On Fri, Nov 9, 2012 at 5:11 AM, Siddhesh Poyarekar <siddhesh@redhat.com> wrote: > > I understand that the behaviour is undefined, but this is easily > avoidable by skipping removal of the exits if it results in an infinite > loop. Attached patch does exactly that. I don't mind saying that GCC should define cases that the language standards leave undefined. But that does not seem to be what this patch does. I don't see why this is a good idea. It seems to produce a program that is unpredictable in a different way. How does that help the user? If anything an infinite loop might be better, since it is more obvious that something is wrong. Unless I misunderstand. Ian
> On Fri, Nov 9, 2012 at 5:11 AM, Siddhesh Poyarekar <siddhesh@redhat.com> wrote: > > > > I understand that the behaviour is undefined, but this is easily > > avoidable by skipping removal of the exits if it results in an infinite > > loop. Attached patch does exactly that. > > I don't mind saying that GCC should define cases that the language > standards leave undefined. But that does not seem to be what this > patch does. I don't see why this is a good idea. It seems to produce > a program that is unpredictable in a different way. How does that > help the user? If anything an infinite loop might be better, since it > is more obvious that something is wrong. Unless I misunderstand. I think resonable thing to do is to output warning in this case "Loop reaches undefined effect before any of the exit conditions are satisfied; turned into infinite loop" or something along these lines? We can probably even get the location info of the statement that implied the loop bound. This is particularly simple case where undefined code is now handled differently. What I am more worried about is the case where we wire in __builtin_unreachable that will stay reachable and the resulting program will die in difficult to debug way. I was thinking about adding similar warning when __builtin_unreachable starts to be unconditional. Honza
On Fri, 9 Nov 2012 17:34:26 +0100, Jan wrote: > > I don't mind saying that GCC should define cases that the language > > standards leave undefined. But that does not seem to be what this > > patch does. I don't see why this is a good idea. It seems to > > produce a program that is unpredictable in a different way. How > > does that help the user? If anything an infinite loop might be > > better, since it is more obvious that something is wrong. Unless I > > misunderstand. > > I think resonable thing to do is to output warning in this case > "Loop reaches undefined effect before any of the exit conditions are > satisfied; turned into infinite loop" or something along these > lines? We can probably even get the location info of the statement > that implied the loop bound. I had reckoned that the behaviour could be reverted to what was before while I figure out a way to get the warning in place for both cases, i.e. with tree-vrp (where max_loop_iterations now causes the loop to be folded away in -O2) and this unroll case (in -O1). I'll look at getting a warning for the tree-vrp case separately if the infinite loop behaviour needs to be retained. An infinite loop without the warning breaks diagnostic apps like valgrind since they are no longer in a position to detect this. The user would then have to somehow conclude that their loop loops infinitely because they have a beyond-array-bounds access in it. However, the infinite loop could be OK if there is an explicit warning telling the user that it's going to happen. I already have some rough code in place to do the warning against the loop header, so I'll clean it up to issue a warning for all exit points beyond the upper bound when we see that no exits remain. It will break a few existing test cases though - I had posted a patch to fix those earlier today: http://gcc.gnu.org/ml/gcc-patches/2012-11/msg00722.html Thanks, Siddhesh
On Fri, 9 Nov 2012 22:51:45 +0530, Siddhesh wrote: > I had reckoned that the behaviour could be reverted to what was before > while I figure out a way to get the warning in place for both cases, > i.e. with tree-vrp (where max_loop_iterations now causes the loop to > be folded away in -O2) and this unroll case (in -O1). I'll look at > getting a warning for the tree-vrp case separately if the infinite > loop behaviour needs to be retained. I'm sorry, I won't be able to get this done today. The patch causes a regression with torture/pr49518.c where it gives out the warning when it shouldn't. I had seen this warning earlier (with the earlier behaviour of not removing the exits) and fixed it, but it has reappeared now, perhaps due to some recent patch that removes more exits or something else. I'll get back on this late next week since I'll be offline for most of the week (it's holiday season here in India). Siddhesh
diff --git a/gcc/tree-ssa-loop-ivcanon.c b/gcc/tree-ssa-loop-ivcanon.c index 601223b..04bcd86 100644 --- a/gcc/tree-ssa-loop-ivcanon.c +++ b/gcc/tree-ssa-loop-ivcanon.c @@ -525,10 +525,22 @@ static bool remove_redundant_iv_tests (struct loop *loop) { struct nb_iter_bound *elt; - bool changed = false; + loop_exit *exit; + VEC(gimple, stack) *exit_stmts = VEC_alloc (gimple, stack, 16); + VEC(edge, stack) *exit_edges = VEC_alloc (edge, stack, 16); + int exits_left = 0, num_exits = 0; if (!loop->any_upper_bound) - return false; + goto out; + + /* Count our exits. */ + for (exit = loop->exits->next; exit->e; exit = exit->next) + num_exits++; + + if (num_exits == 0) + goto out; + + exits_left = num_exits; for (elt = loop->bounds; elt; elt = elt->next) { /* Exit is pointless if it won't be taken before loop reaches @@ -555,21 +567,40 @@ remove_redundant_iv_tests (struct loop *loop) || !loop->nb_iterations_upper_bound.ult (tree_to_double_int (niter.niter))) continue; - + + exits_left--; + + VEC_safe_push (gimple, stack, exit_stmts, elt->stmt); + VEC_safe_push (edge, stack, exit_edges, exit_edge); + } + } + + /* Don't remove the exits if it leaves us with an infinite loop. */ + if (exits_left > 0) + { + while (VEC_length (gimple, exit_stmts)) + { + gimple stmt = VEC_pop (gimple, exit_stmts); + edge exit_edge = VEC_pop (edge, exit_edges); + if (dump_file && (dump_flags & TDF_DETAILS)) { fprintf (dump_file, "Removed pointless exit: "); - print_gimple_stmt (dump_file, elt->stmt, 0, 0); + print_gimple_stmt (dump_file, stmt, 0, 0); } if (exit_edge->flags & EDGE_TRUE_VALUE) - gimple_cond_make_false (elt->stmt); + gimple_cond_make_false (stmt); else - gimple_cond_make_true (elt->stmt); - update_stmt (elt->stmt); - changed = true; + gimple_cond_make_true (stmt); + update_stmt (stmt); } } - return changed; + +out: + VEC_free (gimple, stack, exit_stmts); + VEC_free (edge, stack, exit_edges); + + return (exits_left && exits_left < num_exits); } /* Stores loops that will be unlooped after we process whole loop tree. */
Hi, r193098 introduced a change to the loop unroll behaviour, where exits beyond nb_iterations_upper_bound were removed as being redundant. This assumption is not true for an undefined behaviour, which is when a loop causes access beyond bounds of an array. In such a case, all exits are removed and the result is an infinite loop. Essentially, the following program results in an infinite loop with -O: int d[16]; int main (void) { int k, satd = 0, dd; for (dd=d[k=0]; k<16;) { satd += (dd < 0 ? -dd : dd); ++k; dd=d[k]; } return satd; } I understand that the behaviour is undefined, but this is easily avoidable by skipping removal of the exits if it results in an infinite loop. Attached patch does exactly that. I guess a further improvement to this (if the patch approach is valid) would be to issue a warning to the user based on this analysis. I am trying to figure out a way to call the remove_redundant_iv_tests function safely in tree-vrp so that even -O2 does not produce an infinite loop for the above program (it has since r186592) and prints the warning instead. Simply calling it after max_loop_iterations causes a regression in the testsuite that I haven't figured out yet. I have tested the patch on x86_64 for C language and the testsuite reports no regressions. In fact, it seems to have fixed a previous failure in gcc.dg/vect/slp-perm-9.c. Regards, Siddhesh ChangeLog: 2012-11-09 Siddhesh Poyarekar <siddhesh@redhat.com> PR tree-optimization/55079 * gcc/tree-ssa-loop-ivcanon.c (remove_redundant_iv_tests): Avoid removing all exits of the loop.