[Bug tree-optimization/30927] New: tree-nested creates pointless static chains and trampolines when the callgraph is non-trivial

[Bug tree-optimization/30927] New: tree-nested creates pointless static chains and trampolines when the callgraph is non-trivial

[baldrick at gcc dot gnu dot org]

If a nested subroutine calls another nested subroutine that follows it
lexically, then convert_all_function_calls will force the called function to
take a static chain even though it may not need one.  The most trivial example
of this is a recursive nested subroutine, as in example n1.c:

void n1(void) { void a(void) { a(); } }

$ gcc -c n1.c -fdump-tree-nested
$ grep chain n1.c.*nested
  a () [static-chain: CHAIN.1];
A pointless static chain has been created.

Here's an example n2.c in which the caller and callee disagree about whether a
static chain is needed or not: the caller thinks it is needed, the callee does
not.

void n2(void) {
  auto void a(void);
  void b(void) { a(); }
  void a(void) {}
}

This might seem fairly harmless, but can become expensive when trampolines are
needlessly created.  Example n3.c:

void n3(void) {
  auto void a(void *);
  void b(void) { a(b); }
  void a(void *f) {}
}
$ gcc -c n3.c -fdump-tree-nested
$ grep trampoline n3.c.*nested
  struct __builtin_trampoline * D.1631;
  D.1632 = __builtin_adjust_trampoline (D.1631);
  __builtin_init_trampoline (&FRAME.0.b, b, &FRAME.0);

In Ada, nested subroutines are widely used, and unneeded static chains are
frequently being created by gcc: I first noticed this problem while
bootstrapping the compiler with a patch that happened to print a warning in
case n2.c: the warning fired hundreds of times during the Ada build.  The most
common reason for this seems to be due to the instantiation of generic packages
inside library level procedures.


-- 
           Summary: tree-nested creates pointless static chains and
                    trampolines when the callgraph is non-trivial
           Product: gcc
           Version: 4.3.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: baldrick at gcc dot gnu dot org


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

[Bug tree-optimization/30927] tree-nested creates pointless static chains and trampolines when the callgraph is non-trivial

[ebotcazou at gcc dot gnu dot org]

------- Comment #1 from ebotcazou at gcc dot gnu dot org  2007-02-22 17:40 -------
Try this: http://gcc.gnu.org/ml/gcc-patches/2006-03/msg01201.html


-- 

ebotcazou at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |ebotcazou at gcc dot gnu dot
                   |                            |org
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|0                           |1
   Last reconfirmed|0000-00-00 00:00:00         |2007-02-22 17:40:25
               date|                            |


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

[Bug tree-optimization/30927] tree-nested creates pointless static chains and trampolines when the callgraph is non-trivial

[baldrick at gcc dot gnu dot org]

------- Comment #2 from baldrick at gcc dot gnu dot org  2007-03-15 14:49 -------
Created an attachment (id=13208)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=13208&action=view)
Proposed fix

Bootstraps with all languages including Ada.  Does not introduce any new
testsuite failures.  I'd appreciate it if the ACT people could pass it
through their regression test suite.  I don't know if this interacts
correctly with OMP because I don't understand OMP.


-- 


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

[Bug tree-optimization/30927] tree-nested creates pointless static chains and trampolines when the callgraph is non-trivial

[ebotcazou at gcc dot gnu dot org]

------- Comment #3 from ebotcazou at gcc dot gnu dot org  2007-03-15 15:12 -------
> Bootstraps with all languages including Ada.  Does not introduce any new
> testsuite failures.  I'd appreciate it if the ACT people could pass it
> through their regression test suite.  I don't know if this interacts
> correctly with OMP because I don't understand OMP.

What would it buy us over the patch I previously posted?


-- 


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

[Bug tree-optimization/30927] tree-nested creates pointless static chains and trampolines when the callgraph is non-trivial

[baldrick at free dot fr]

------- Comment #4 from baldrick at free dot fr  2007-03-15 15:16 -------
Subject: Re:  tree-nested creates pointless static chains and trampolines when
the callgraph is non-trivial

> > Bootstraps with all languages including Ada.  Does not introduce any new
> > testsuite failures.  I'd appreciate it if the ACT people could pass it
> > through their regression test suite.  I don't know if this interacts
> > correctly with OMP because I don't understand OMP.
> 
> What would it buy us over the patch I previously posted?

I didn't receive your previous comment - my bugzilla email settings were
wrong.  I am now reading your patch - thanks for pointing it out!

Ciao,

Duncan.


-- 


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

[Bug tree-optimization/30927] tree-nested creates pointless static chains and trampolines when the callgraph is non-trivial

[baldrick at free dot fr]

------- Comment #5 from baldrick at free dot fr  2007-03-15 15:34 -------
Subject: Re:  tree-nested creates pointless static chains and trampolines when
the callgraph is non-trivial

> > Bootstraps with all languages including Ada.  Does not introduce any new
> > testsuite failures.  I'd appreciate it if the ACT people could pass it
> > through their regression test suite.  I don't know if this interacts
> > correctly with OMP because I don't understand OMP.
> 
> What would it buy us over the patch I previously posted?

If I understand right the two patches do different things.  Consider
the following example:

     void X(void) {
       void D(void) { D(); };
       D();
     }

The nested function is reachable, so presumably your patch doesn't
change the behaviour of tree-nested in this case, i.e. D gets a
static chain even though it doesn't need one.  My patch makes sure
that D doesn't get a static chain.  It doesn't try to do anything
about unreachable functions.  In fact I noticed that unreachable
functions can generate a pointless "nonlocal frame structure", but
decided not to attempt a fix because it seemed much more complicated
to do!

By the way, I see that you added a hash table for going from the
context to the nesting_info.  I was too lazy to do that, instead
I do a linear list walk to find it.  Do you think it matters?

Ciao,

Duncan.


-- 


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

[Bug tree-optimization/30927] tree-nested creates pointless static chains and trampolines when the callgraph is non-trivial

[baldrick at gcc dot gnu dot org]

------- Comment #6 from baldrick at gcc dot gnu dot org  2007-03-15 19:45 -------
(In reply to comment #1)
> Try this: http://gcc.gnu.org/ml/gcc-patches/2006-03/msg01201.html

I don't think you need to consider FDESC_EXPR when constructing
the callgraph.  It seems only to be used for vtables; and since
none of the rest of tree-nested checks for it, I guess either the
rest of tree-nested is wrong or it's not needed.


-- 


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

[Bug tree-optimization/30927] tree-nested creates pointless static chains and trampolines when the callgraph is non-trivial

[ebotcazou at gcc dot gnu dot org]

------- Comment #7 from ebotcazou at gcc dot gnu dot org  2007-03-21 09:31 -------
> If I understand right the two patches do different things.  Consider
> the following example:
> 
>      void X(void) {
>        void D(void) { D(); };
>        D();
>      }
> 
> The nested function is reachable, so presumably your patch doesn't
> change the behaviour of tree-nested in this case, i.e. D gets a
> static chain even though it doesn't need one.  My patch makes sure
> that D doesn't get a static chain.

Indeed, we still unnecessarily build a static chain for D.

Your solution seems to be somewhat complex though.  Can't we get away with
an iterative propagation algorithm for the DECL_NO_STATIC_CHAIN flag?

> By the way, I see that you added a hash table for going from the
> context to the nesting_info.  I was too lazy to do that, instead
> I do a linear list walk to find it.  Do you think it matters?

No real idea in practice, but we try to avoid potentially quadratic stuff
in the compiler as a general policy.


-- 


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

[Bug tree-optimization/30927] tree-nested creates pointless static chains and trampolines when the callgraph is non-trivial

[baldrick at gcc dot gnu dot org]

------- Comment #8 from baldrick at gcc dot gnu dot org  2008-01-10 18:25 -------
> Your solution seems to be somewhat complex though.  Can't we get away with
> an iterative propagation algorithm for the DECL_NO_STATIC_CHAIN flag?

Yes, but it is less efficient: in the worst case the number of node
visits goes up by a factor of the nesting depth.  Since this depth
is sure to be fairly small (typically 2 or 3) this probably is of
no consequence.  I am now working on a revised patch.


-- 


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

[Bug tree-optimization/30927] tree-nested creates pointless static chains and trampolines when the callgraph is non-trivial

[rth at gcc dot gnu dot org]

------- Comment #9 from rth at gcc dot gnu dot org  2009-09-16 18:55 -------
Fixed here:

http://gcc.gnu.org/ml/gcc-patches/2009-09/msg01069.html


-- 

rth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
      Known to work|                            |4.5.0
         Resolution|                            |FIXED
   Target Milestone|---                         |4.5.0


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