[Bug target/33826] New: GCC generates wrong code for infinitely recursive functions

[Bug target/33826] New: GCC generates wrong code for infinitely recursive functions

[tbm at cyrius dot com]

[ forwarded from http://bugs.debian.org/445536 ]

From: Samuel Tardieu <sam@rfc1149.net>

% cat > t.c << EOF
void foo()
{ foo(); }
EOF

% gcc -O -S -o - -fomit-frame-pointer -Wall t.c
        .file   "t.c"
        .text
.globl foo
        .type   foo, @function
foo:
        rep ; ret
        .size   foo, .-foo
        .ident  "GCC: (GNU) 4.2.1 (Debian 4.2.1-5)"
        .section        .note.GNU-stack,"",@progbits

As far as I know, there are two acceptable behaviours for function foo():
  - loop indefinitely (if tail recursion is used)
  - overflow the stack (if tail recursion is not used)

As soon as -O is used on x86-32, GCC generates code that just returns
("rep ; ret").

Note that the bug is also present with the following Ada program:

procedure U is
begin
   U;
end U;

although the Ada front-end warns about a possibly infinite recursion. The
very same code gets generated.

This may be platform-specific and generates bogus code with any non-O0
optimization level.


-- 
           Summary: GCC generates wrong code for infinitely recursive
                    functions
           Product: gcc
           Version: 4.2.2
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: target
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: tbm at cyrius dot com
GCC target triplet: x86_64-linux-gnu


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

[Bug tree-optimization/33826] [4.1/4.2/4.3 Regression] GCC generates wrong code for infinitely recursive functions

[rguenth at gcc dot gnu dot org]

------- Comment #1 from rguenth at gcc dot gnu dot org  2007-10-20 10:03 -------
foo is analyzed to be const by ipa-pure-const and so the self-recursive call
is DCEd.  Now one could argue that foo indeed _is_ const, for example

unsigned foo(unsigned i)
{
  if (i == 1)
    return 1;
  return foo(i-1) + 1; 
}

is a perfectly const tail-recursive way of returning i.  We'd no longer DCE

void bar(void)
{
  foo(5);
}

I'd argue that a stack overflow is nothing that the C standard describes and
that we are of course not supposed to solve the halting problem to decide
that non-halting functions are not pure/const.  As we handle simple
non-terminating cases like

void foo(void)
{
  while (1) ;
}

we probably can handle the simple self-recursion as well.  Even if this
wouldn't be a complete solution.


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |rguenth at gcc dot gnu dot
                   |                            |org
             Status|UNCONFIRMED                 |NEW
          Component|target                      |tree-optimization
     Ever Confirmed|0                           |1
           Keywords|                            |wrong-code
   Last reconfirmed|0000-00-00 00:00:00         |2007-10-20 10:03:01
               date|                            |
            Summary|GCC generates wrong code for|[4.1/4.2/4.3 Regression] GCC
                   |infinitely recursive        |generates wrong code for
                   |functions                   |infinitely recursive
                   |                            |functions
   Target Milestone|---                         |4.2.3


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

[Bug tree-optimization/33826] [4.1/4.2/4.3 Regression] GCC generates wrong code for infinitely recursive functions

[mmitchel at gcc dot gnu dot org]

-- 

mmitchel at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Priority|P3                          |P1


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

[Bug tree-optimization/33826] [4.1/4.2/4.3 Regression] GCC generates wrong code for infinitely recursive functions

[steven at gcc dot gnu dot org]

------- Comment #2 from steven at gcc dot gnu dot org  2007-11-05 21:38 -------
It seems to me that a recursive function can never be safely treated as
const/pure. In fact, any function in an SCC in the call graph could result in
an endless loop and is therefore not const/pure. I'm assuming here that hanging
in an infinite loop is a "side-effect", and I understand this is a debatable
assumption.


-- 

steven at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |zadeck at gcc dot gnu dot
                   |                            |org


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

[Bug tree-optimization/33826] [4.1/4.2/4.3 Regression] GCC generates wrong code for infinitely recursive functions

[zadeck at naturalbridge dot com]

------- Comment #3 from zadeck at naturalbridge dot com  2007-11-05 22:16 -------
Subject: Re:  [4.1/4.2/4.3 Regression] GCC generates
 wrong code for infinitely recursive functions

steven at gcc dot gnu dot org wrote:
> ------- Comment #2 from steven at gcc dot gnu dot org  2007-11-05 21:38 -------
> It seems to me that a recursive function can never be safely treated as
> const/pure. In fact, any function in an SCC in the call graph could result in
> an endless loop and is therefore not const/pure. I'm assuming here that hanging
> in an infinite loop is a "side-effect", and I understand this is a debatable
> assumption.
>
>
>   
I have never been happy with how the "edge" cases of programs that are
designed to do undefined behavior are used to define what is correct and
what is not correct for well defined programs. 

So i am unconvinced by steven's argument. 

If someone either can turn this into a program that gets the wrong
answer on a program that has a defined behavior with a language that gcc
supports, then i will take this bug seriously. 

Kenny


-- 


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

[Bug tree-optimization/33826] [4.1/4.2/4.3 Regression] GCC generates wrong code for infinitely recursive functions

[ebotcazou at gcc dot gnu dot org]

------- Comment #4 from ebotcazou at gcc dot gnu dot org  2007-11-05 23:06 -------
> If someone either can turn this into a program that gets the wrong
> answer on a program that has a defined behavior with a language that gcc
> supports, then i will take this bug seriously. 

There is already an Ada testcase in the report; if compiled in full conformance
mode (with -fstack-check), it should exhaust the stack and raise Storage_Error
on the x86.  Of course this should not have P1 priority.


-- 

ebotcazou at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |ebotcazou at gcc dot gnu dot
                   |                            |org


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

[Bug tree-optimization/33826] [4.1/4.2/4.3 Regression] GCC generates wrong code for infinitely recursive functions

[sam at rfc1149 dot net]

------- Comment #5 from sam at rfc1149 dot net  2007-11-06 18:50 -------
Eric: do you mean that tail recursive calls are not allowed with -fstack-check?

With the current trunk, the code is ok with -O3 (tail-recursive call) and still
buggy with -O ("rep ret" on x86). This is even stranger :)


-- 

sam at rfc1149 dot net changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |sam at rfc1149 dot net


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

[Bug tree-optimization/33826] [4.1/4.2/4.3 Regression] GCC generates wrong code for infinitely recursive functions

[ebotcazou at gcc dot gnu dot org]

------- Comment #6 from ebotcazou at gcc dot gnu dot org  2007-11-06 19:04 -------
> Eric: do you mean that tail recursive calls are not allowed with -fstack-check?

No, they are allowed.  Optimizing the Ada testcase into an infinite loop is OK
if you don't consume the stack.


-- 


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

[Bug tree-optimization/33826] [4.1/4.2/4.3 Regression] GCC generates wrong code for infinitely recursive functions

[zadeck at naturalbridge dot com]

------- Comment #7 from zadeck at naturalbridge dot com  2007-11-06 21:21 -------
Subject: Re:  [4.1/4.2/4.3 Regression] GCC generates
 wrong code for infinitely recursive functions

ebotcazou at gcc dot gnu dot org wrote:
> ------- Comment #6 from ebotcazou at gcc dot gnu dot org  2007-11-06 19:04 -------
>   
>> Eric: do you mean that tail recursive calls are not allowed with -fstack-check?
>>     
>
> No, they are allowed.  Optimizing the Ada testcase into an infinite loop is OK
> if you don't consume the stack.
>
>
>   
I just talked to mark mitchell who was wearing his official language
lawyer hat at the time.  He said i had to fix it.  i will submit a patch
in the next day or so.


-- 


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

[Bug tree-optimization/33826] [4.1/4.2/4.3 Regression] GCC generates wrong code for infinitely recursive functions

[ebotcazou at gcc dot gnu dot org]

------- Comment #8 from ebotcazou at gcc dot gnu dot org  2007-11-06 21:33 -------
> I just talked to mark mitchell who was wearing his official language
> lawyer hat at the time.  He said i had to fix it.  i will submit a patch
> in the next day or so.

Thanks in advance.


-- 


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

[Bug tree-optimization/33826] [4.1/4.2/4.3 Regression] GCC generates wrong code for infinitely recursive functions

[zadeck at naturalbridge dot com]

------- Comment #9 from zadeck at naturalbridge dot com  2007-11-06 21:52 -------
Subject: Re:  [4.1/4.2/4.3 Regression] GCC generates
 wrong code for infinitely recursive functions

ebotcazou at gcc dot gnu dot org wrote:
> ------- Comment #8 from ebotcazou at gcc dot gnu dot org  2007-11-06 21:33 -------
>   
>> I just talked to mark mitchell who was wearing his official language
>> lawyer hat at the time.  He said i had to fix it.  i will submit a patch
>> in the next day or so.
>>     
>
> Thanks in advance.
>
>
>   
I am only snarly about this because i do not want to give up marking
recurrences as pure or const.  That will, in the long run, cost us. 

Mark and i talked about adding another bit to the tree so that we could
support non recursive and recursive pure and const functions.  the
recursive ones could still be cse'd but not dce'd.  This is not
appropriate for stage 3.


-- 


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

[Bug tree-optimization/33826] [4.1/4.2/4.3 Regression] GCC generates wrong code for infinitely recursive functions

[zadeck at naturalbridge dot com]

------- Comment #10 from zadeck at naturalbridge dot com  2007-11-07 18:44 -------
Subject: Re:  [4.1/4.2/4.3 Regression] GCC generates
 wrong code for infinitely recursive functions

This patch keeps recursive functions from being marked as pure or const.

Full testing in progress on x86-64.  But the code seems to work properly.

Ok to commit when the full testing is finished?

Kenny

2007-11-07  Kenneth Zadeck <zadeck@naturalbridge.com>

    PR middle-end/33826
    * ipa-pure-const (static_execute): Added code to keep recursive
    functions from being marked as pure or const.
    * ipa-utils (searchc): Fixed comment.

2007-11-07  Kenneth Zadeck <zadeck@naturalbridge.com>

    PR middle-end/33826
    * gcc.dg/pr33826.c: New.


Index: testsuite/gcc.dg/pr33826.c
===================================================================
--- testsuite/gcc.dg/pr33826.c  (revision 0)
+++ testsuite/gcc.dg/pr33826.c  (revision 0)
@@ -0,0 +1,40 @@
+/* Regression test for PR middle-end/33826 */
+/* Verify that recursive functions cannot be pure or const.  */
+
+/* { dg-do compile } */
+/* { dg-options "-O1 -fdump-ipa-pure-const" } */
+
+int recurese1 (int i)
+{
+  return recurse1 (i+1);
+}
+
+int recurse2a (int i)
+{
+  return recurse2b (i+1);
+}
+
+int recurse2b (int i)
+{
+  return recurse2a (i+1);
+}
+
+int norecurse1a (int i)
+{
+  return norecurse1b (i+1);
+}
+
+int norecurse1b (int i)
+{
+  return i+1;
+}
+
+/* { dg-final { scan-ipa-dump "found to be const: norecurse1a" "pure-const" }
} */
+/* { dg-final { scan-ipa-dump "found to be const: norecurse1b" "pure-const" }
} */
+/* { dg-final { scan-ipa-dump-not "found to be pure: recurse1" "pure-const" }
} */
+/* { dg-final { scan-ipa-dump-not "found to be pure: recurse2a" "pure-const" }
} */
+/* { dg-final { scan-ipa-dump-not "found to be pure: recurse2b" "pure-const" }
} */
+/* { dg-final { scan-ipa-dump-not "found to be const: recurse1" "pure-const" }
} */
+/* { dg-final { scan-ipa-dump-not "found to be const: recurse2a" "pure-const"
} } */
+/* { dg-final { scan-ipa-dump-not "found to be const: recurse2b" "pure-const"
} } */
+/* { dg-final { cleanup-ipa-dump "pure-const" } } */
Index: ipa-pure-const.c
===================================================================
--- ipa-pure-const.c    (revision 129944)
+++ ipa-pure-const.c    (working copy)
@@ -644,6 +644,7 @@ static_execute (void)
   for (i = 0; i < order_pos; i++ )
     {
       enum pure_const_state_e pure_const_state = IPA_CONST;
+      int count = 0;
       node = order[i];

       /* Find the worst state for any node in the cycle.  */
@@ -660,11 +661,40 @@ static_execute (void)
          if (!w_l->state_set_in_source)
            {
              struct cgraph_edge *e;
+             count++;
+
+             /* FIXME!!!  Because of pr33826, we cannot have either
+                immediate or transitive recursive functions marked as
+                pure or const because dce can delete a function that
+                is in reality an infinite loop.  A better solution
+                than just outlawing them is to add another bit the
+                functions to distinguish recursive from non recursive
+                pure and const function.  This would allow the
+                recursive ones to be cse'd but not dce'd.  In this
+                same vein, we could allow functions with loops to
+                also be cse'd but not dce'd.
+
+                Unfortunately we are late in stage 3, and the fix
+                described above is is not appropriate.  */
+             if (count > 1)
+               {
+                 pure_const_state = IPA_NEITHER;
+                 break;
+               }
+                   
              for (e = w->callees; e; e = e->next_callee) 
                {
                  struct cgraph_node *y = e->callee;
                  /* Only look at the master nodes and skip external nodes.  */
                  y = cgraph_master_clone (y);
+
+                 /* Check for immediate recursive functions.  See the
+                    FIXME above.  */
+                 if (w == y)
+                   {
+                     pure_const_state = IPA_NEITHER;
+                     break;
+                   }
                  if (y)
                    {
                      funct_state y_l = get_function_state (y);
Index: ipa-utils.c
===================================================================
--- ipa-utils.c (revision 129944)
+++ ipa-utils.c (working copy)
@@ -76,7 +76,7 @@ struct searchc_env {
    has been customized for cgraph_nodes.  The env parameter is because
    it is recursive and there are no nested functions here.  This
    function should only be called from itself or
-   cgraph_reduced_inorder.  ENV is a stack env and would be
+   ipa_utils_reduced_inorder.  ENV is a stack env and would be
    unnecessary if C had nested functions.  V is the node to start
    searching from.  */



-- 


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

[Bug tree-optimization/33826] [4.1/4.2/4.3 Regression] GCC generates wrong code for infinitely recursive functions

[zadeck at naturalbridge dot com]

------- Comment #11 from zadeck at naturalbridge dot com  2007-11-08 01:23 -------
Subject: Re:  [4.1/4.2/4.3 Regression] GCC generates
 wrong code for infinitely recursive functions

zadeck at naturalbridge dot com wrote:
> ------- Comment #10 from zadeck at naturalbridge dot com  2007-11-07 18:44 -------
> Subject: Re:  [4.1/4.2/4.3 Regression] GCC generates
>  wrong code for infinitely recursive functions
>
> This patch keeps recursive functions from being marked as pure or const.
>
> Full testing in progress on x86-64.  But the code seems to work properly.
>
> Ok to commit when the full testing is finished?
>
> Kenny
>
> 2007-11-07  Kenneth Zadeck <zadeck@naturalbridge.com>
>
>     PR middle-end/33826
>     * ipa-pure-const (static_execute): Added code to keep recursive
>     functions from being marked as pure or const.
>     * ipa-utils (searchc): Fixed comment.
>
> 2007-11-07  Kenneth Zadeck <zadeck@naturalbridge.com>
>
>     PR middle-end/33826
>     * gcc.dg/pr33826.c: New.
>
>   
The tests finished and i had to remove some of the testing in
gcc.dg/tree-ssa/20030714-1.c
that depends on recursive functions being marked as pure or const.

i actually think that this testcase is stupid and recommend removing it
outright.

2007-11-07  Kenneth Zadeck <zadeck@naturalbridge.com>

    PR middle-end/33826
    * gcc.dg/pr33826.c: New.
    * gcc.dg/tree-ssa/20030714-1.c: Removed two tests that depend on
    recursive functions being marked pure or const.

Ok to commit?

Kenny
Index: testsuite/gcc.dg/pr33826.c
===================================================================
--- testsuite/gcc.dg/pr33826.c  (revision 0)
+++ testsuite/gcc.dg/pr33826.c  (revision 0)
@@ -0,0 +1,40 @@
+/* Regression test for PR middle-end/33826 */
+/* Verify that recursive functions cannot be pure or const.  */
+
+/* { dg-do compile } */
+/* { dg-options "-O1 -fdump-ipa-pure-const" } */
+
+int recurese1 (int i)
+{
+  return recurse1 (i+1);
+}
+
+int recurse2a (int i)
+{
+  return recurse2b (i+1);
+}
+
+int recurse2b (int i)
+{
+  return recurse2a (i+1);
+}
+
+int norecurse1a (int i)
+{
+  return norecurse1b (i+1);
+}
+
+int norecurse1b (int i)
+{
+  return i+1;
+}
+
+/* { dg-final { scan-ipa-dump "found to be const: norecurse1a" "pure-const" }
} */
+/* { dg-final { scan-ipa-dump "found to be const: norecurse1b" "pure-const" }
} */
+/* { dg-final { scan-ipa-dump-not "found to be pure: recurse1" "pure-const" }
} */
+/* { dg-final { scan-ipa-dump-not "found to be pure: recurse2a" "pure-const" }
} */
+/* { dg-final { scan-ipa-dump-not "found to be pure: recurse2b" "pure-const" }
} */
+/* { dg-final { scan-ipa-dump-not "found to be const: recurse1" "pure-const" }
} */
+/* { dg-final { scan-ipa-dump-not "found to be const: recurse2a" "pure-const"
} } */
+/* { dg-final { scan-ipa-dump-not "found to be const: recurse2b" "pure-const"
} } */
+/* { dg-final { cleanup-ipa-dump "pure-const" } } */
Index: testsuite/gcc.dg/tree-ssa/20030714-1.c
===================================================================
--- testsuite/gcc.dg/tree-ssa/20030714-1.c      (revision 129944)
+++ testsuite/gcc.dg/tree-ssa/20030714-1.c      (working copy)
@@ -34,13 +34,6 @@ find_base_value (src)
 }


-/* There should be four IF conditionals.  */
-/* { dg-final { scan-tree-dump-times "if " 4 "dom3"} } */
-
 /* There should be no casts to short unsigned int.  */
 /* { dg-final { scan-tree-dump-times "\\(short unsigned int\\)" 0 "dom3"} } */

-/* There should be two loads of ->code.  */
-/* { dg-final { scan-tree-dump-times "->code" 2 "dom3"} } */
-
-/* { dg-final { cleanup-tree-dump "dom3" } } */
Index: ipa-pure-const.c
===================================================================
--- ipa-pure-const.c    (revision 129944)
+++ ipa-pure-const.c    (working copy)
@@ -644,6 +644,7 @@ static_execute (void)
   for (i = 0; i < order_pos; i++ )
     {
       enum pure_const_state_e pure_const_state = IPA_CONST;
+      int count = 0;
       node = order[i];

       /* Find the worst state for any node in the cycle.  */
@@ -660,11 +661,40 @@ static_execute (void)
          if (!w_l->state_set_in_source)
            {
              struct cgraph_edge *e;
+             count++;
+
+             /* FIXME!!!  Because of pr33826, we cannot have either
+                immediate or transitive recursive functions marked as
+                pure or const because dce can delete a function that
+                is in reality an infinite loop.  A better solution
+                than just outlawing them is to add another bit the
+                functions to distinguish recursive from non recursive
+                pure and const function.  This would allow the
+                recursive ones to be cse'd but not dce'd.  In this
+                same vein, we could allow functions with loops to
+                also be cse'd but not dce'd.
+
+                Unfortunately we are late in stage 3, and the fix
+                described above is is not appropriate.  */
+             if (count > 1)
+               {
+                 pure_const_state = IPA_NEITHER;
+                 break;
+               }
+                   
              for (e = w->callees; e; e = e->next_callee) 
                {
                  struct cgraph_node *y = e->callee;
                  /* Only look at the master nodes and skip external nodes.  */
                  y = cgraph_master_clone (y);
+
+                 /* Check for immediate recursive functions.  See the
+                    FIXME above.  */
+                 if (w == y)
+                   {
+                     pure_const_state = IPA_NEITHER;
+                     break;
+                   }
                  if (y)
                    {
                      funct_state y_l = get_function_state (y);
Index: ipa-utils.c
===================================================================
--- ipa-utils.c (revision 129944)
+++ ipa-utils.c (working copy)
@@ -76,7 +76,7 @@ struct searchc_env {
    has been customized for cgraph_nodes.  The env parameter is because
    it is recursive and there are no nested functions here.  This
    function should only be called from itself or
-   cgraph_reduced_inorder.  ENV is a stack env and would be
+   ipa_utils_reduced_inorder.  ENV is a stack env and would be
    unnecessary if C had nested functions.  V is the node to start
    searching from.  */



-- 


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

[Bug tree-optimization/33826] [4.1/4.2/4.3 Regression] GCC generates wrong code for infinitely recursive functions

[richard dot guenther at gmail dot com]

------- Comment #12 from richard dot guenther at gmail dot com  2007-11-08 09:08 -------
Subject: Re:  [4.1/4.2/4.3 Regression] GCC generates wrong code for infinitely
recursive functions

On 11/7/07, Kenneth Zadeck <zadeck@naturalbridge.com> wrote:
> This patch keeps recursive functions from being marked as pure or const.
>
> Full testing in progress on x86-64.  But the code seems to work properly.
>
> Ok to commit when the full testing is finished?

Ok.

Thanks,
Richard.

> Kenny
>
> 2007-11-07  Kenneth Zadeck <zadeck@naturalbridge.com>
>
>     PR middle-end/33826
>     * ipa-pure-const (static_execute): Added code to keep recursive
>     functions from being marked as pure or const.
>     * ipa-utils (searchc): Fixed comment.
>
> 2007-11-07  Kenneth Zadeck <zadeck@naturalbridge.com>
>
>     PR middle-end/33826
>     * gcc.dg/pr33826.c: New.
>
>
>
>


-- 


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

[Bug tree-optimization/33826] [4.1/4.2/4.3 Regression] GCC generates wrong code for infinitely recursive functions

[zadeck at gcc dot gnu dot org]

------- Comment #13 from zadeck at gcc dot gnu dot org  2007-11-08 16:46 -------
Subject: Bug 33826

Author: zadeck
Date: Thu Nov  8 16:45:53 2007
New Revision: 130006

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=130006
Log:
2007-11-07  Kenneth Zadeck <zadeck@naturalbridge.com>

        PR middle-end/33826
        * ipa-pure-const (static_execute): Added code to keep recursive
        functions from being marked as pure or const.
        * ipa-utils (searchc): Fixed comment.
2007-11-08  Kenneth Zadeck <zadeck@naturalbridge.com>

        PR middle-end/33826
        * gcc.dg/pr33826.c: New.
        * gcc.dg/tree-ssa/20030714-1.c: Removed two tests that depend on 
        recursive functions being marked pure or const.         


Added:
    trunk/gcc/testsuite/gcc.dg/pr33826.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/ipa-pure-const.c
    trunk/gcc/ipa-utils.c
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/testsuite/gcc.dg/tree-ssa/20030714-1.c


-- 


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

[Bug tree-optimization/33826] [4.1/4.2/4.3 Regression] GCC generates wrong code for infinitely recursive functions

[zadeck at naturalbridge dot com]

------- Comment #14 from zadeck at naturalbridge dot com  2007-11-08 16:48 -------
Subject: Re:  [4.1/4.2/4.3 Regression] GCC generates
 wrong code for infinitely recursive functions

Richard Guenther wrote:
> On 11/7/07, Kenneth Zadeck <zadeck@naturalbridge.com> wrote:
>   
>> This patch keeps recursive functions from being marked as pure or const.
>>
>> Full testing in progress on x86-64.  But the code seems to work properly.
>>
>> Ok to commit when the full testing is finished?
>>     
>
> Ok.
>
> Thanks,
> Richard.
>
>   
>> Kenny
>>
>> 2007-11-07  Kenneth Zadeck <zadeck@naturalbridge.com>
>>
>>     PR middle-end/33826
>>     * ipa-pure-const (static_execute): Added code to keep recursive
>>     functions from being marked as pure or const.
>>     * ipa-utils (searchc): Fixed comment.
>>
>> 2007-11-07  Kenneth Zadeck <zadeck@naturalbridge.com>
>>
>>     PR middle-end/33826
>>     * gcc.dg/pr33826.c: New.
>>
>>
>>
>>
>>     
committed as revision 130006.

kenny

Index: testsuite/gcc.dg/pr33826.c
===================================================================
--- testsuite/gcc.dg/pr33826.c  (revision 0)
+++ testsuite/gcc.dg/pr33826.c  (revision 0)
@@ -0,0 +1,40 @@
+/* Regression test for PR middle-end/33826 */
+/* Verify that recursive functions cannot be pure or const.  */
+
+/* { dg-do compile } */
+/* { dg-options "-O1 -fdump-ipa-pure-const" } */
+
+int recurese1 (int i)
+{
+  return recurse1 (i+1);
+}
+
+int recurse2a (int i)
+{
+  return recurse2b (i+1);
+}
+
+int recurse2b (int i)
+{
+  return recurse2a (i+1);
+}
+
+int norecurse1a (int i)
+{
+  return norecurse1b (i+1);
+}
+
+int norecurse1b (int i)
+{
+  return i+1;
+}
+
+/* { dg-final { scan-ipa-dump "found to be const: norecurse1a" "pure-const" }
} */
+/* { dg-final { scan-ipa-dump "found to be const: norecurse1b" "pure-const" }
} */
+/* { dg-final { scan-ipa-dump-not "found to be pure: recurse1" "pure-const" }
} */
+/* { dg-final { scan-ipa-dump-not "found to be pure: recurse2a" "pure-const" }
} */
+/* { dg-final { scan-ipa-dump-not "found to be pure: recurse2b" "pure-const" }
} */
+/* { dg-final { scan-ipa-dump-not "found to be const: recurse1" "pure-const" }
} */
+/* { dg-final { scan-ipa-dump-not "found to be const: recurse2a" "pure-const"
} } */
+/* { dg-final { scan-ipa-dump-not "found to be const: recurse2b" "pure-const"
} } */
+/* { dg-final { cleanup-ipa-dump "pure-const" } } */
Index: testsuite/gcc.dg/tree-ssa/20030714-1.c
===================================================================
--- testsuite/gcc.dg/tree-ssa/20030714-1.c      (revision 129944)
+++ testsuite/gcc.dg/tree-ssa/20030714-1.c      (working copy)
@@ -34,13 +34,6 @@ find_base_value (src)
 }


-/* There should be four IF conditionals.  */
-/* { dg-final { scan-tree-dump-times "if " 4 "dom3"} } */
-
 /* There should be no casts to short unsigned int.  */
 /* { dg-final { scan-tree-dump-times "\\(short unsigned int\\)" 0 "dom3"} } */

-/* There should be two loads of ->code.  */
-/* { dg-final { scan-tree-dump-times "->code" 2 "dom3"} } */
-
-/* { dg-final { cleanup-tree-dump "dom3" } } */
Index: ipa-pure-const.c
===================================================================
--- ipa-pure-const.c    (revision 129944)
+++ ipa-pure-const.c    (working copy)
@@ -644,6 +644,7 @@ static_execute (void)
   for (i = 0; i < order_pos; i++ )
     {
       enum pure_const_state_e pure_const_state = IPA_CONST;
+      int count = 0;
       node = order[i];

       /* Find the worst state for any node in the cycle.  */
@@ -660,11 +661,40 @@ static_execute (void)
          if (!w_l->state_set_in_source)
            {
              struct cgraph_edge *e;
+             count++;
+
+             /* FIXME!!!  Because of pr33826, we cannot have either
+                immediate or transitive recursive functions marked as
+                pure or const because dce can delete a function that
+                is in reality an infinite loop.  A better solution
+                than just outlawing them is to add another bit the
+                functions to distinguish recursive from non recursive
+                pure and const function.  This would allow the
+                recursive ones to be cse'd but not dce'd.  In this
+                same vein, we could allow functions with loops to
+                also be cse'd but not dce'd.
+
+                Unfortunately we are late in stage 3, and the fix
+                described above is is not appropriate.  */
+             if (count > 1)
+               {
+                 pure_const_state = IPA_NEITHER;
+                 break;
+               }
+                   
              for (e = w->callees; e; e = e->next_callee) 
                {
                  struct cgraph_node *y = e->callee;
                  /* Only look at the master nodes and skip external nodes.  */
                  y = cgraph_master_clone (y);
+
+                 /* Check for immediate recursive functions.  See the
+                    FIXME above.  */
+                 if (w == y)
+                   {
+                     pure_const_state = IPA_NEITHER;
+                     break;
+                   }
                  if (y)
                    {
                      funct_state y_l = get_function_state (y);
Index: ipa-utils.c
===================================================================
--- ipa-utils.c (revision 129944)
+++ ipa-utils.c (working copy)
@@ -76,7 +76,7 @@ struct searchc_env {
    has been customized for cgraph_nodes.  The env parameter is because
    it is recursive and there are no nested functions here.  This
    function should only be called from itself or
-   cgraph_reduced_inorder.  ENV is a stack env and would be
+   ipa_utils_reduced_inorder.  ENV is a stack env and would be
    unnecessary if C had nested functions.  V is the node to start
    searching from.  */



-- 


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

[Bug tree-optimization/33826] [4.1/4.2/4.3 Regression] GCC generates wrong code for infinitely recursive functions

[zadeck at naturalbridge dot com]

------- Comment #15 from zadeck at naturalbridge dot com  2007-11-08 16:49 -------
fixed


-- 

zadeck at naturalbridge dot com changed:

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


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

[Bug tree-optimization/33826] [4.1/4.2/4.3 Regression] GCC generates wrong code for infinitely recursive functions

[ghazi at gcc dot gnu dot org]

------- Comment #16 from ghazi at gcc dot gnu dot org  2008-01-09 18:42 -------
Ken - Your testcase (gcc.dg/pr33826.c) fails on i686 with -fpic/-fpic.  If I
make the definitions static, it doesn't seem to help.  Real bug, or skip with
pic?

http://gcc.gnu.org/ml/gcc-testresults/2008-01/msg00366.html


-- 

ghazi at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |ghazi at gcc dot gnu dot org


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

[Bug tree-optimization/33826] [4.1/4.2/4.3 Regression] GCC generates wrong code for infinitely recursive functions

[zadeck at naturalbridge dot com]

------- Comment #17 from zadeck at naturalbridge dot com  2008-01-09 20:49 -------
Subject: Re:  [4.1/4.2/4.3 Regression] GCC generates
 wrong code for infinitely recursive functions

ghazi at gcc dot gnu dot org wrote:
> ------- Comment #16 from ghazi at gcc dot gnu dot org  2008-01-09 18:42 -------
> Ken - Your testcase (gcc.dg/pr33826.c) fails on i686 with -fpic/-fpic.  If I
> make the definitions static, it doesn't seem to help.  Real bug, or skip with
> pic?
>
> http://gcc.gnu.org/ml/gcc-testresults/2008-01/msg00366.html
>
>
>   
it looks like this test should not be run with -fpic. 

kenny


-- 


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

[Bug tree-optimization/33826] [4.1/4.2/4.3 Regression] GCC generates wrong code for infinitely recursive functions

[ghazi at gcc dot gnu dot org]

------- Comment #18 from ghazi at gcc dot gnu dot org  2008-01-11 03:57 -------
Thanks Kenny, patch posted here:
http://gcc.gnu.org/ml/gcc-patches/2008-01/msg00445.html


-- 


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

[Bug tree-optimization/33826] [4.1/4.2/4.3 Regression] GCC generates wrong code for infinitely recursive functions

[zadeck at naturalbridge dot com]

------- Comment #19 from zadeck at naturalbridge dot com  2008-01-11 13:09 -------
Subject: Re:  [4.1/4.2/4.3 Regression] GCC generates
 wrong code for infinitely recursive functions

ghazi at gcc dot gnu dot org wrote:
> ------- Comment #18 from ghazi at gcc dot gnu dot org  2008-01-11 03:57 -------
> Thanks Kenny, patch posted here:
> http://gcc.gnu.org/ml/gcc-patches/2008-01/msg00445.html
>
>
>   
ok to commit.

kenny


-- 


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

[Bug tree-optimization/33826] [4.1/4.2 Regression] GCC generates wrong code for infinitely recursive functions

[rguenth at gcc dot gnu dot org]

------- Comment #20 from rguenth at gcc dot gnu dot org  2008-01-23 21:35 -------
Not fixed on the branches.


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|RESOLVED                    |REOPENED
      Known to work|                            |4.3.0
         Resolution|FIXED                       |
            Summary|[4.1/4.2/4.3 Regression] GCC|[4.1/4.2 Regression] GCC
                   |generates wrong code for    |generates wrong code for
                   |infinitely recursive        |infinitely recursive
                   |functions                   |functions


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

[Bug tree-optimization/33826] [4.1/4.2 Regression] GCC generates wrong code for infinitely recursive functions

[ghazi at gcc dot gnu dot org]

------- Comment #21 from ghazi at gcc dot gnu dot org  2008-01-24 20:09 -------
Subject: Bug 33826

Author: ghazi
Date: Thu Jan 24 20:09:05 2008
New Revision: 131805

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=131805
Log:
        Backport:
        2008-01-10  Kaveh R. Ghazi  <ghazi@caip.rutgers.edu>

        * gcc.dg/pr33826.c: Require nonpic.

        2007-11-07  Kenneth Zadeck <zadeck@naturalbridge.com>

        PR middle-end/33826
        * ipa-pure-const (static_execute): Added code to keep recursive
        functions from being marked as pure or const.
        * ipa-utils (searchc): Fixed comment.

        2007-11-08  Kenneth Zadeck <zadeck@naturalbridge.com>

        PR middle-end/33826
        * gcc.dg/pr33826.c: New.
        * gcc.dg/tree-ssa/20030714-1.c: Removed two tests that depend on 
        recursive functions being marked pure or const.


Added:
    branches/gcc-4_2-branch/gcc/testsuite/gcc.dg/pr33826.c
Modified:
    branches/gcc-4_2-branch/gcc/ChangeLog
    branches/gcc-4_2-branch/gcc/ipa-pure-const.c
    branches/gcc-4_2-branch/gcc/ipa-utils.c
    branches/gcc-4_2-branch/gcc/testsuite/ChangeLog
    branches/gcc-4_2-branch/gcc/testsuite/gcc.dg/tree-ssa/20030714-1.c


-- 


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

[Bug tree-optimization/33826] [4.1/4.2 Regression] GCC generates wrong code for infinitely recursive functions

[ghazi at gcc dot gnu dot org]

------- Comment #22 from ghazi at gcc dot gnu dot org  2008-01-24 20:34 -------
Subject: Bug 33826

Author: ghazi
Date: Thu Jan 24 20:33:54 2008
New Revision: 131807

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=131807
Log:
        Backport:
        2008-01-10  Kaveh R. Ghazi  <ghazi@caip.rutgers.edu>

        * gcc.dg/pr33826.c: Require nonpic.

        2007-11-07  Kenneth Zadeck <zadeck@naturalbridge.com>

        PR middle-end/33826
        * ipa-pure-const (static_execute): Added code to keep recursive
        functions from being marked as pure or const.
        * ipa-utils (searchc): Fixed comment.

        2007-11-08  Kenneth Zadeck <zadeck@naturalbridge.com>

        PR middle-end/33826
        * gcc.dg/pr33826.c: New.
        * gcc.dg/tree-ssa/20030714-1.c: Removed two tests that depend on 
        recursive functions being marked pure or const.



Added:
    branches/gcc-4_1-branch/gcc/testsuite/gcc.dg/pr33826.c
Modified:
    branches/gcc-4_1-branch/gcc/ChangeLog
    branches/gcc-4_1-branch/gcc/ipa-pure-const.c
    branches/gcc-4_1-branch/gcc/ipa-utils.c
    branches/gcc-4_1-branch/gcc/testsuite/ChangeLog
    branches/gcc-4_1-branch/gcc/testsuite/gcc.dg/tree-ssa/20030714-1.c


-- 


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

[Bug tree-optimization/33826] [4.1/4.2 Regression] GCC generates wrong code for infinitely recursive functions

[ghazi at gcc dot gnu dot org]

------- Comment #23 from ghazi at gcc dot gnu dot org  2008-01-24 21:35 -------
Fixed on branches.


-- 

ghazi at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|REOPENED                    |RESOLVED
      Known to work|4.3.0                       |4.3.0 4.2.3 4.1.3
         Resolution|                            |FIXED


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