Summary: | [4.0 Regression] LIM is pulling out a pure function even though there is something which can modify global memory | ||
---|---|---|---|
Product: | gcc | Reporter: | Andrew Pinski <pinskia> |
Component: | tree-optimization | Assignee: | Not yet assigned to anyone <unassigned> |
Status: | RESOLVED FIXED | ||
Severity: | critical | CC: | dnovillo, drow, gcc-bugs, ian, jakub, rakdver, schwab, steven |
Priority: | P1 | Keywords: | wrong-code |
Version: | 4.0.0 | ||
Target Milestone: | 4.0.0 | ||
Host: | Target: | ||
Build: | Known to work: | ||
Known to fail: | Last reconfirmed: | 2005-02-09 07:03:08 | |
Attachments: | Quick patch to handle pure/const calls like memory references |
Description
Andrew Pinski
2005-02-08 19:03:28 UTC
Here's another related testcase. If you uncomment the store to global_int, LIM will move only func_const out of the loop. With them both commented out, however, the pure call gets moved out of the loop. func_other may modify global memory, though, so the pure call can not be moved. int func_pure (void) __attribute__ ((pure)); int func_const (void) __attribute__ ((const)); void func_other (int); int global_int; int func_loop (int arg) { while (arg--) { // global_int = arg; func_other (func_pure ()); } } int func_loop_2 (int arg) { while (arg--) { // global_int = arg; func_other (func_const ()); } } Here's another one. This may be a different bug. Suppose we have two pure functions, one which checks whether a library is present and one which fetches some piece of data from the library. Code looks like this: int func_loop_3 (int arg) { int var = 0; while (arg--) { if (func_pure ()) var = func_pure_2 (); } return var; } LIM will move _both_ pure calls out of the loop. I think that it is valid for a pure call to segfault in a condition when it would not normally have been called; if the implementation of func_pure always returns zero, I don't think that func_pure_2 should ever be called in the above. (In reply to comment #2) > Here's another one. This may be a different bug. Yes that is a different (but related) bug. The problem is now, what is definition of pure functions (for that testcase). Take the following: int *a; int *func_pure () __attribute__((pure)); int func_pure_2 () __attribute__((pure)); int *func_pure() { return a; } int func_pure_2() { return *a;} int i; int func_loop_3 (int arg) { int var = 0; i = 1; while (arg--) { if (func_pure ()) var = func_pure_2 (); } return var; } void abort (void); int main() { int i; i = func_loop_3 (10); if (i) abort (); } Is func_pure_2 really pure and if it is, then we should change it so we can trap on it. Confirmed via Daniel Berline via IRC and Drow via this bug. wrong-code, the worst kind we have... Zdenek, a tree-ssa-loop-im problem, apparently... Function that may trap is not pure; in particular func_pure_2 cannot be considered pure. The remaining testcases are real bugs, however. That's a pretty useless definition of pure functions - they may read global memory, but not dereference any pointers which are invalid at any point in the life of the program? Subject: Re: [4.0 Regression] LIM is pulling out a pure function even though there is something which can modify global memory
> That's a pretty useless definition of pure functions - they may read global
> memory, but not dereference any pointers which are invalid at any point in
> the life of the program?
sorry, but allowing pure functions to trap would make them even more
useless. For example it would be forbidden to remove calls to them
(no dce), possibilities for code motion would be severely limited,
etc. Hopefully with interprocedural alias analysis pure specifier
will become less needed.
I've suggested when talking to someone else about this that they should be assumed not to trap at the points where they are called. That would allow calls to them to be removed, although still limit code motion. It's a pity there's no rigorous definition of the current meaning of pure. The definition of pure states that such a function may depend upon global variables. I guess you are saying that func_pure_2 is not pure because the global variable a may not be a valid memory address? I disagree. If the programmer declares that func_pure_2 is pure, then the programmer is promising the compiler that the variable a holds a valid memory address. The attribute is not a statement of something which the compiler can deduce for itself; it is a promise by the programmer. Given that promise, the compiler is fully entitled and expected to hoist function calls out of loops which do not modify global variables, etc. If that causes a bug, it is a bug in the code, not in the compiler. I agree that it would be nice if the compiler could do a better job of analyzing whether a function is const/pure, but until then we should trust the programmer. Subject: Re: [4.0 Regression] LIM is pulling
out a pure function even though there is something which can modify global
memory
On Sun, 13 Feb 2005, drow at gcc dot gnu dot org wrote:
> I've suggested when talking to someone else about this that they should be
> assumed not to trap at the points where they are called. That would allow
> calls to them to be removed, although still limit code motion.
>
> It's a pity there's no rigorous definition of the current meaning of pure.
I would say that a pure function is a pure but not necessarily total
function of its arguments and those parts of the state of the machine
visible to it: you can move or remove calls to pure functions as long as
in the abstract machine the function would have been called with the
particular machine state with which it does get called. So strlen is pure
and "if (s) strlen(s);" is valid and the strlen call can't be moved before
the test for NULL. Similarly a const function is a pure but not
necessarily total function of the values of its arguments only: so a
square root function which doesn't set errno or floating point exception
flags could be "const" and a call to it should not be moved before a test
that the argument is nonnegative.
Where there are optimizations depending on the function being total - not
trapping even if you call it with arguments with which the program never
calls it in the abstract machine model - perhaps an additional attribute
"total" should be added which can be used in conjunction with "const" or
"pure". (Though I'm not sure how many real functions are going to be
"pure" and "total" but not "const".)
Just got hit by this too on subversion. Distilled testcase is: typedef __SIZE_TYPE__ size_t; extern size_t strlen (const char *s); extern int strncmp (const char *s1, const char *s2, size_t n); extern void abort (void); const char *a[16] = { "a", "bc", "de", "fgh" }; int foo (char *x, const char *y, size_t n) { size_t i, j = 0; for (i = 0; i < n; i++) { if (strncmp (x + j, a[i], strlen (a[i])) != 0) return 2; j += strlen (a[i]); if (y) j += strlen (y); } return 0; } int main (void) { if (foo ("abcde", (const char *) 0, 3) != 0) abort (); return 0; } With Zdenek's definition of pure the only pure functions in builtins.def would be is*/to*, none of the string/memory functions could be. But the documentation explicitely mentions strlen and memcmp as pure functions. OK, I agree that definition of ``pure'' needs to be changed in order to be useful (and to match the expectations); obviously, any function that is not total does not match the current definition. What I find somewhat troublesome is that the "upgraded" definition of pure puts some of obligation on user of the function, rather than function itself. The definition matching the expected semantics would need to be something like "Pure function is guaranteed to be always called in such a way that it has no side effects." Created attachment 8227 [details]
Quick patch to handle pure/const calls like memory references
Subject: Bug 19828 CVSROOT: /cvs/gcc Module name: gcc Changes by: jakub@gcc.gnu.org 2005-02-19 09:26:09 Modified files: gcc : ChangeLog tree-ssa-loop-im.c gcc/testsuite : ChangeLog Added files: gcc/testsuite/gcc.c-torture/execute: 20050218-1.c gcc/testsuite/gcc.dg/tree-ssa: loop-7.c Log message: PR tree-optimization/19828 * tree-ssa-loop-im.c: Add a TODO comment. (movement_possibility): Return MOVE_PRESERVE_EXECUTION for calls without side-effects. * gcc.dg/tree-ssa/loop-7.c: New test. * gcc.c-torture/execute/20050218-1.c: New test. Patches: http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/ChangeLog.diff?cvsroot=gcc&r1=2.7535&r2=2.7536 http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/tree-ssa-loop-im.c.diff?cvsroot=gcc&r1=2.27&r2=2.28 http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/testsuite/ChangeLog.diff?cvsroot=gcc&r1=1.5052&r2=1.5053 http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/testsuite/gcc.c-torture/execute/20050218-1.c.diff?cvsroot=gcc&r1=NONE&r2=1.1 http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/testsuite/gcc.dg/tree-ssa/loop-7.c.diff?cvsroot=gcc&r1=NONE&r2=1.1 Fixed. |