[Bug tree-optimization/19828] New: [4.0 Regression] LIM is pulling out a pure function even though there is something which can modify global memory

[Bug tree-optimization/19828] New: [4.0 Regression] LIM is pulling out a pure function even though there is something which can modify global memory

[pinskia at gcc dot gnu dot org]

Take the following program, it should run and work correct and not call abort but with -O1/-O2 on the 
mainline we call abort because LIM pulls out the call to f of the loop but should not because f1 can 
modify the global memory (and does).  If I uncomment the store to the global memory in the function 
containing the loop we get the correct code as LIM sees that the call to f has a VUSE and call to f1 has a 
V_MAY_DEF.

int f(void) __attribute__((pure));
int lll;
int f() { return lll; }
int f1() { lll++; return lll % 2;}
int g(void)
{
  int k, l;
  k=0;
//lll = 0;
  for(l =0;l<10;l++)
    if (f1 ())
     k = f();
  return k;
}
void abort ();

int main(void)
{
  if (g() != 9)
   abort ();
}

-- 
           Summary: [4.0 Regression] LIM is pulling out a pure function even
                    though there is something which can modify global memory
           Product: gcc
           Version: 4.0.0
            Status: UNCONFIRMED
          Keywords: wrong-code
          Severity: normal
          Priority: P2
         Component: tree-optimization
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: pinskia at gcc dot gnu dot org
                CC: dnovillo at gcc dot gnu dot org,drow at gcc dot gnu dot
                    org,gcc-bugs at gcc dot gnu dot org


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19828

[Bug tree-optimization/19828] [4.0 Regression] LIM is pulling out a pure function even though there is something which can modify global memory

[pinskia at gcc dot gnu dot org]

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |4.0.0


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19828

[Bug tree-optimization/19828] [4.0 Regression] LIM is pulling out a pure function even though there is something which can modify global memory

[ian at airs dot com]

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |ian at airs dot com


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19828

[Bug tree-optimization/19828] [4.0 Regression] LIM is pulling out a pure function even though there is something which can modify global memory

[drow at gcc dot gnu dot org]

------- Additional Comments From drow at gcc dot gnu dot org  2005-02-08 19:27 -------
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 ());
    }
}


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19828

[Bug tree-optimization/19828] [4.0 Regression] LIM is pulling out a pure function even though there is something which can modify global memory

[drow at gcc dot gnu dot org]

------- Additional Comments From drow at gcc dot gnu dot org  2005-02-08 19:36 -------
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.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19828

[Bug tree-optimization/19828] [4.0 Regression] LIM is pulling out a pure function even though there is something which can modify global memory

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-02-08 20:02 -------
(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.

-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19828

[Bug tree-optimization/19828] [4.0 Regression] LIM is pulling out a pure function even though there is something which can modify global memory

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-02-09 07:03 -------
Confirmed via Daniel Berline via IRC and Drow via this bug.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|                            |1
   Last reconfirmed|0000-00-00 00:00:00         |2005-02-09 07:03:08
               date|                            |


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19828

[Bug tree-optimization/19828] [4.0 Regression] LIM is pulling out a pure function even though there is something which can modify global memory

[steven at gcc dot gnu dot org]

------- Additional Comments From steven at gcc dot gnu dot org  2005-02-10 10:58 -------
wrong-code, the worst kind we have... 

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
           Severity|normal                      |critical
           Priority|P2                          |P1


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19828

[Bug tree-optimization/19828] [4.0 Regression] LIM is pulling out a pure function even though there is something which can modify global memory

[steven at gcc dot gnu dot org]

------- Additional Comments From steven at gcc dot gnu dot org  2005-02-12 14:52 -------
Zdenek, a tree-ssa-loop-im problem, apparently... 

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |rakdver at gcc dot gnu dot
                   |                            |org, steven at gcc dot gnu
                   |                            |dot org


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19828

[Bug tree-optimization/19828] [4.0 Regression] LIM is pulling out a pure function even though there is something which can modify global memory

[rakdver at gcc dot gnu dot org]

------- Additional Comments From rakdver at gcc dot gnu dot org  2005-02-13 19:50 -------
Function that may trap is not pure; in particular func_pure_2 cannot
be considered pure.  The remaining testcases are real bugs, however.

-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19828

[Bug tree-optimization/19828] [4.0 Regression] LIM is pulling out a pure function even though there is something which can modify global memory

[drow at gcc dot gnu dot org]

------- Additional Comments From drow at gcc dot gnu dot org  2005-02-13 20:05 -------
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?


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19828

[Bug tree-optimization/19828] [4.0 Regression] LIM is pulling out a pure function even though there is something which can modify global memory

[rakdver at atrey dot karlin dot mff dot cuni dot cz]

------- Additional Comments From rakdver at atrey dot karlin dot mff dot cuni dot cz  2005-02-13 20:11 -------
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.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19828

[Bug tree-optimization/19828] [4.0 Regression] LIM is pulling out a pure function even though there is something which can modify global memory

[drow at gcc dot gnu dot org]

------- Additional Comments From drow at gcc dot gnu dot org  2005-02-13 20:13 -------
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.

-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19828

[Bug tree-optimization/19828] [4.0 Regression] LIM is pulling out a pure function even though there is something which can modify global memory

[ian at airs dot com]

------- Additional Comments From ian at airs dot com  2005-02-13 20:27 -------
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.

-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19828

[Bug tree-optimization/19828] [4.0 Regression] LIM is pulling out a pure function even though there is something which can modify global memory

[joseph at codesourcery dot com]

------- Additional Comments From joseph at codesourcery dot com  2005-02-13 20:38 -------
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".)



-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19828

[Bug tree-optimization/19828] [4.0 Regression] LIM is pulling out a pure function even though there is something which can modify global memory

[jakub at gcc dot gnu dot org]

------- Additional Comments From jakub at gcc dot gnu dot org  2005-02-18 15:55 -------
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.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |jakub at redhat dot com


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19828

[Bug tree-optimization/19828] [4.0 Regression] LIM is pulling out a pure function even though there is something which can modify global memory

[rakdver at gcc dot gnu dot org]

------- Additional Comments From rakdver at gcc dot gnu dot org  2005-02-18 16:16 -------
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."

-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19828

[Bug tree-optimization/19828] [4.0 Regression] LIM is pulling out a pure function even though there is something which can modify global memory

[cvs-commit at gcc dot gnu dot org]

------- Additional Comments From cvs-commit at gcc dot gnu dot org  2005-02-19 09:26 -------
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



-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19828

[Bug tree-optimization/19828] [4.0 Regression] LIM is pulling out a pure function even though there is something which can modify global memory

[jakub at gcc dot gnu dot org]

------- Additional Comments From jakub at gcc dot gnu dot org  2005-02-19 09:33 -------
Fixed.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
         Resolution|                            |FIXED


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19828

[Bug tree-optimization/19828] [4.0 Regression] LIM is pulling out a pure function even though there is something which can modify global memory

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-02-20 15:52 -------
Note the testcase in comment 1 is not fixed yet, see PR 20100.

-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19828