llvm dev - Dec 2016 - distinct DISubprograms hindering sharing inlined subprogram descriptions

Branching off from a discussion of improvements to DIGlobalVariable
representations that Adrian's working on - got me thinking about related
changes that have already been made to DISubprogram.

To reduce duplicate debug info when things like linkonce_odr functions were
deduplicated in LTO linking, the relationship between a CU and DISubprogram
was inverted (instead of a CU maintaining a list of subprograms,
subprograms specify which CU they come from - and the llvm::Function
references the DISubprogram, so if the llvm::Function goes away, so does
the associated DISubprogram)

I'm not sure if this caused a regression, but at least seems to miss a
possible improvement:

During IR linking (for LTO, ThinLTO, etc) these distinct DISubprogram
definitions (& their CU link, even if they weren't marked
'distinct', the
CU link would cause them to effectively be so) remain separate - this means
that inlined versions in one CU don't refer to an existing subprogram
definition in another CU.

To demonstrate:
inl.h:
void f1();
inline __attribute__((always_inline)) void f2() {
  f1();
}
inl1.cpp:
#include "inl.h"
void c1() {
  f2();
}
inl2.cpp:
#include "inl.h"
void c2() {
  f2();
}

Compile to IR, llvm-link the result. The DWARF you get is basically the
same as the DWARF you'd get without linking:

DW_TAG_compile_unit
  DW_AT_name "inl1.cpp"
  DW_TAG_subprogram #0
    DW_AT_name "f2"
  DW_TAG_subprogram
    DW_AT_name "c1"
    DW_TAG_inlined_subroutine
      DW_TAG_abstract_origin #0 "f2"
DW_TAG_compile_unit
  DW_AT_name "inl2.cpp"
  DW_TAG_subprogram #1
    DW_AT_name "f2"
  DW_TAG_subprogram
    DW_AT_name "c2"
    DW_TAG_inlined_subroutine
      DW_TAG_abstract_origin #1 "f2"

Instead of something more like this:

DW_TAG_compile_unit
  DW_AT_name "inl1.cpp"
  DW_TAG_subprogram #0
    DW_AT_name "f2"
  DW_TAG_subprogram
    DW_AT_name "c1"
    DW_TAG_inlined_subroutine
      DW_TAG_abstract_origin #0 "f2"
DW_TAG_compile_unit
  DW_AT_name "inl2.cpp"
  DW_TAG_subprogram
    DW_AT_name "c2"
    DW_TAG_inlined_subroutine
      DW_TAG_abstract_origin #0 "f2"

(note that only one abstract definition of f2 is produced here)

Any thoughts? I imagine this is probably worth a reasonable amount of
savings in an optimized build. Not huge, but not nothing. (probably not the
top of anyone's list though, I realize)

Should we remove the CU link from a non-internal linkage subprogram (& this
may have an effect on the GV representation issue originally being
discussed) and just emit it into whichever CU happens to need it first?

This might be slightly sub-optimal, due to, say, the namespace being
foreign to that CU. But it's how we do types currently, I think? So at
least it'd be consistent and probably cheap enough/better.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20161215/c191b937/attachment-0001.html>

Trying to wrap my brain around this, so a few questions below. =)

On Thu, Dec 15, 2016 at 10:54 AM, David Blaikie <dblaikie at gmail.com>
wrote:
> Branching off from a discussion of improvements to DIGlobalVariable
> representations that Adrian's working on - got me thinking about
related
> changes that have already been made to DISubprogram.
>
> To reduce duplicate debug info when things like linkonce_odr functions
> were deduplicated in LTO linking, the relationship between a CU and
> DISubprogram was inverted (instead of a CU maintaining a list of
> subprograms, subprograms specify which CU they come from - and the
> llvm::Function references the DISubprogram, so if the llvm::Function goes
> away, so does the associated DISubprogram)
>
> I'm not sure if this caused a regression, but at least seems to miss a
> possible improvement:
>
> During IR linking (for LTO, ThinLTO, etc) these distinct DISubprogram
> definitions (& their CU link, even if they weren't marked
'distinct', the
> CU link would cause them to effectively be so) remain separate - this means
> that inlined versions in one CU don't refer to an existing subprogram
> definition in another CU.
>
> To demonstrate:
> inl.h:
> void f1();
> inline __attribute__((always_inline)) void f2() {
>   f1();
> }
> inl1.cpp:
> #include "inl.h"
> void c1() {
>   f2();
> }
> inl2.cpp:
> #include "inl.h"
> void c2() {
>   f2();
> }
>
> Compile to IR, llvm-link the result. The DWARF you get is basically the
> same as the DWARF you'd get without linking:
>
> DW_TAG_compile_unit
>   DW_AT_name "inl1.cpp"
>   DW_TAG_subprogram #0
>     DW_AT_name "f2"
>   DW_TAG_subprogram
>     DW_AT_name "c1"
>     DW_TAG_inlined_subroutine
>       DW_TAG_abstract_origin #0 "f2"
> DW_TAG_compile_unit
>   DW_AT_name "inl2.cpp"
>   DW_TAG_subprogram #1
>     DW_AT_name "f2"
>   DW_TAG_subprogram
>     DW_AT_name "c2"
>     DW_TAG_inlined_subroutine
>       DW_TAG_abstract_origin #1 "f2"
>
> Instead of something more like this:
>
> DW_TAG_compile_unit
>   DW_AT_name "inl1.cpp"
>   DW_TAG_subprogram #0
>     DW_AT_name "f2"
>   DW_TAG_subprogram
>     DW_AT_name "c1"
>     DW_TAG_inlined_subroutine
>       DW_TAG_abstract_origin #0 "f2"
> DW_TAG_compile_unit
>   DW_AT_name "inl2.cpp"
>   DW_TAG_subprogram
>     DW_AT_name "c2"
>     DW_TAG_inlined_subroutine
>       DW_TAG_abstract_origin #0 "f2"
>
> (note that only one abstract definition of f2 is produced here)
>
I think I understand what you are saying. Essentially, having the SP->CU
link allows the SP to be deduplicated when multiple *outline* copies of the
corresponding function are deduplicated. But not when the multiple copies
are inlined, as it looks like we need all the copies, right?

>
> Any thoughts? I imagine this is probably worth a reasonable amount of
> savings in an optimized build. Not huge, but not nothing. (probably not the
> top of anyone's list though, I realize)
>
> Should we remove the CU link from a non-internal linkage subprogram (&
> this may have an effect on the GV representation issue originally being
> discussed) and just emit it into whichever CU happens to need it first?
>
I can see how this would be done in LTO where the compiler has full
visibility. For ThinLTO presumably we would need to do some index-based
marking? Can we at least do something when we import an inlined SP and drop
it since we know it is defined elsewhere?

Thanks,
Teresa

>
> This might be slightly sub-optimal, due to, say, the namespace being
> foreign to that CU. But it's how we do types currently, I think? So at
> least it'd be consistent and probably cheap enough/better.
>


-- 
Teresa Johnson |  Software Engineer |  tejohnson at google.com |  408-460-2413
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20161215/c0ff6ab6/attachment.html>

> On Dec 15, 2016, at 10:54 AM, David Blaikie via llvm-dev <llvm-dev at
lists.llvm.org> wrote:
> 
> Branching off from a discussion of improvements to DIGlobalVariable
representations that Adrian's working on - got me thinking about related
changes that have already been made to DISubprogram.
> 
> To reduce duplicate debug info when things like linkonce_odr functions were
deduplicated in LTO linking, the relationship between a CU and DISubprogram was
inverted (instead of a CU maintaining a list of subprograms, subprograms specify
which CU they come from - and the llvm::Function references the DISubprogram, so
if the llvm::Function goes away, so does the associated DISubprogram)
> 
> I'm not sure if this caused a regression, but at least seems to miss a
possible improvement:
> 
> During IR linking (for LTO, ThinLTO, etc) these distinct DISubprogram
definitions (& their CU link, even if they weren't marked
'distinct', the CU link would cause them to effectively be so) remain
separate - this means that inlined versions in one CU don't refer to an
existing subprogram definition in another CU.
> 
> To demonstrate:
> inl.h:
> void f1();
> inline __attribute__((always_inline)) void f2() {
>   f1();
> }
> inl1.cpp:
> #include "inl.h"
> void c1() {
>   f2();
> }
> inl2.cpp:
> #include "inl.h"
> void c2() {
>   f2();
> }
> 
> Compile to IR, llvm-link the result. The DWARF you get is basically the
same as the DWARF you'd get without linking:
> 
> DW_TAG_compile_unit
>   DW_AT_name "inl1.cpp"
>   DW_TAG_subprogram #0
>     DW_AT_name "f2"
>   DW_TAG_subprogram
>     DW_AT_name "c1"
>     DW_TAG_inlined_subroutine
>       DW_TAG_abstract_origin #0 "f2"
> DW_TAG_compile_unit
>   DW_AT_name "inl2.cpp"
>   DW_TAG_subprogram #1
>     DW_AT_name "f2"
>   DW_TAG_subprogram
>     DW_AT_name "c2"
>     DW_TAG_inlined_subroutine
>       DW_TAG_abstract_origin #1 "f2"
> 
> Instead of something more like this:
> 
> DW_TAG_compile_unit
>   DW_AT_name "inl1.cpp"
>   DW_TAG_subprogram #0
>     DW_AT_name "f2"
>   DW_TAG_subprogram
>     DW_AT_name "c1"
>     DW_TAG_inlined_subroutine
>       DW_TAG_abstract_origin #0 "f2"
> DW_TAG_compile_unit
>   DW_AT_name "inl2.cpp"
>   DW_TAG_subprogram
>     DW_AT_name "c2"
>     DW_TAG_inlined_subroutine
>       DW_TAG_abstract_origin #0 "f2"
> 
> (note that only one abstract definition of f2 is produced here)
> 
> Any thoughts? I imagine this is probably worth a reasonable amount of
savings in an optimized build. Not huge, but not nothing. (probably not the top
of anyone's list though, I realize)
I should see the IR metadata in both cases to really know how it worked before,
but it seems that to be able to merge the two subprogram definitions when
linking, we’d need to be able to have a list of CU per subprogram instead of a
single one, right?
> Should we remove the CU link from a non-internal linkage subprogram (&
this may have an effect on the GV representation issue originally being
discussed) and just emit it into whichever CU happens to need it first?
Looks like this should work as well, but I don’t enough about the way we emit
Dwarf...

— 
Mehdi

On Thu, Dec 15, 2016 at 11:26 AM Teresa Johnson <tejohnson at google.com>
wrote:
> Trying to wrap my brain around this, so a few questions below. =)
>
Sure thing - sorry, did assume a bit too much arcane context here.

>
> On Thu, Dec 15, 2016 at 10:54 AM, David Blaikie <dblaikie at
gmail.com>
> wrote:
>
> Branching off from a discussion of improvements to DIGlobalVariable
> representations that Adrian's working on - got me thinking about
related
> changes that have already been made to DISubprogram.
>
> To reduce duplicate debug info when things like linkonce_odr functions
> were deduplicated in LTO linking, the relationship between a CU and
> DISubprogram was inverted (instead of a CU maintaining a list of
> subprograms, subprograms specify which CU they come from - and the
> llvm::Function references the DISubprogram, so if the llvm::Function goes
> away, so does the associated DISubprogram)
>
> I'm not sure if this caused a regression, but at least seems to miss a
> possible improvement:
>
> During IR linking (for LTO, ThinLTO, etc) these distinct DISubprogram
> definitions (& their CU link, even if they weren't marked
'distinct', the
> CU link would cause them to effectively be so) remain separate - this means
> that inlined versions in one CU don't refer to an existing subprogram
> definition in another CU.
>
> To demonstrate:
> inl.h:
> void f1();
> inline __attribute__((always_inline)) void f2() {
>   f1();
> }
> inl1.cpp:
> #include "inl.h"
> void c1() {
>   f2();
> }
> inl2.cpp:
> #include "inl.h"
> void c2() {
>   f2();
> }
>
> Compile to IR, llvm-link the result. The DWARF you get is basically the
> same as the DWARF you'd get without linking:
>
> DW_TAG_compile_unit
>   DW_AT_name "inl1.cpp"
>   DW_TAG_subprogram #0
>     DW_AT_name "f2"
>   DW_TAG_subprogram
>     DW_AT_name "c1"
>     DW_TAG_inlined_subroutine
>       DW_TAG_abstract_origin #0 "f2"
> DW_TAG_compile_unit
>   DW_AT_name "inl2.cpp"
>   DW_TAG_subprogram #1
>     DW_AT_name "f2"
>   DW_TAG_subprogram
>     DW_AT_name "c2"
>     DW_TAG_inlined_subroutine
>       DW_TAG_abstract_origin #1 "f2"
>
> Instead of something more like this:
>
> DW_TAG_compile_unit
>   DW_AT_name "inl1.cpp"
>   DW_TAG_subprogram #0
>     DW_AT_name "f2"
>   DW_TAG_subprogram
>     DW_AT_name "c1"
>     DW_TAG_inlined_subroutine
>       DW_TAG_abstract_origin #0 "f2"
> DW_TAG_compile_unit
>   DW_AT_name "inl2.cpp"
>   DW_TAG_subprogram
>     DW_AT_name "c2"
>     DW_TAG_inlined_subroutine
>       DW_TAG_abstract_origin #0 "f2"
>
> (note that only one abstract definition of f2 is produced here)
>
>
> I think I understand what you are saying. Essentially, having the SP->CU
> link allows the SP to be deduplicated when multiple *outline* copies of the
> corresponding function are deduplicated. But not when the multiple copies
> are inlined, as it looks like we need all the copies, right?
>
Not quite - having the SP->CU link (well,h onestly, marking the SP as
"distinct" does this, but even if we didn't do that, the SP->CU
link would
still do it) causes SPs /not/ to be deduplicated on IR linking.

Each SP is distinct/not considered duplicate with any other. (if we didn't
mark it 'distinct', the fact that each SP refers to its corresponding CU
would produce the same effect - they wouldn't be deduplicated because they
aren't identical - they refer to different CUs)

For non-inlined cases, this is fine.

Before we inverted the SP<>CU link, what would happen is that all copies
of
the llvm::Function would be dropped, but their SPs would be left around. So
two CUs that both used the same linkonce_odr function (let's say no
inlining actually occurred though) would both have a SP description in the
DWARF - but one would actual have a proper definition (with a high/low PC,
etc) the other would be missing those features, as though the function had
been optimized away (which it sort of had)

So by reversing the link, we got rid of those extra SP descriptions in the
DWARF (and the extra SP descriptions in the metadata - I think they were
duplicate back then because they still had a scope chain leading back to
their CU (maybe we had gotten rid of that chain - if we had, then adding it
back in may've actually caused more metadata, but less DWARF))

>
>
>
> Any thoughts? I imagine this is probably worth a reasonable amount of
> savings in an optimized build. Not huge, but not nothing. (probably not the
> top of anyone's list though, I realize)
>
> Should we remove the CU link from a non-internal linkage subprogram (&
> this may have an effect on the GV representation issue originally being
> discussed) and just emit it into whichever CU happens to need it first?
>
>
> I can see how this would be done in LTO where the compiler has full
> visibility. For ThinLTO presumably we would need to do some index-based
> marking? Can we at least do something when we import an inlined SP and drop
> it since we know it is defined elsewhere?
>
Complete visibility isn't required to benefit here - and unfortunately
there's nothing fancier (that I know of) that we can do to avoid emitting
one definition of each used inline function in each thinlto object file we
produce (we can't say "oh, the name of the function, its mangled name,
the
names and types of its parameters are over in that other object
file/somewhere else" - but we can avoid emitting those descriptions in each
/CU/ that uses the inlined function within a single ThinLTO object)

I can provide some more thorough examples if that'd be helpful :)

>
> Thanks,
> Teresa
>
>
>
> This might be slightly sub-optimal, due to, say, the namespace being
> foreign to that CU. But it's how we do types currently, I think? So at
> least it'd be consistent and probably cheap enough/better.
>
>
>
>
> --
> Teresa Johnson |  Software Engineer |  tejohnson at google.com |
> 408-460-2413 <(408)%20460-2413>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20161215/408d74c5/attachment.html>

On Thu, Dec 15, 2016 at 11:35 AM Mehdi Amini <mehdi.amini at apple.com>
wrote:
>
> > On Dec 15, 2016, at 10:54 AM, David Blaikie via llvm-dev <
> llvm-dev at lists.llvm.org> wrote:
> >
> > Branching off from a discussion of improvements to DIGlobalVariable
> representations that Adrian's working on - got me thinking about
related
> changes that have already been made to DISubprogram.
> >
> > To reduce duplicate debug info when things like linkonce_odr functions
> were deduplicated in LTO linking, the relationship between a CU and
> DISubprogram was inverted (instead of a CU maintaining a list of
> subprograms, subprograms specify which CU they come from - and the
> llvm::Function references the DISubprogram, so if the llvm::Function goes
> away, so does the associated DISubprogram)
> >
> > I'm not sure if this caused a regression, but at least seems to
miss a
> possible improvement:
> >
> > During IR linking (for LTO, ThinLTO, etc) these distinct DISubprogram
> definitions (& their CU link, even if they weren't marked
'distinct', the
> CU link would cause them to effectively be so) remain separate - this means
> that inlined versions in one CU don't refer to an existing subprogram
> definition in another CU.
> >
> > To demonstrate:
> > inl.h:
> > void f1();
> > inline __attribute__((always_inline)) void f2() {
> >   f1();
> > }
> > inl1.cpp:
> > #include "inl.h"
> > void c1() {
> >   f2();
> > }
> > inl2.cpp:
> > #include "inl.h"
> > void c2() {
> >   f2();
> > }
> >
> > Compile to IR, llvm-link the result. The DWARF you get is basically
the
> same as the DWARF you'd get without linking:
> >
> > DW_TAG_compile_unit
> >   DW_AT_name "inl1.cpp"
> >   DW_TAG_subprogram #0
> >     DW_AT_name "f2"
> >   DW_TAG_subprogram
> >     DW_AT_name "c1"
> >     DW_TAG_inlined_subroutine
> >       DW_TAG_abstract_origin #0 "f2"
> > DW_TAG_compile_unit
> >   DW_AT_name "inl2.cpp"
> >   DW_TAG_subprogram #1
> >     DW_AT_name "f2"
> >   DW_TAG_subprogram
> >     DW_AT_name "c2"
> >     DW_TAG_inlined_subroutine
> >       DW_TAG_abstract_origin #1 "f2"
> >
> > Instead of something more like this:
> >
> > DW_TAG_compile_unit
> >   DW_AT_name "inl1.cpp"
> >   DW_TAG_subprogram #0
> >     DW_AT_name "f2"
> >   DW_TAG_subprogram
> >     DW_AT_name "c1"
> >     DW_TAG_inlined_subroutine
> >       DW_TAG_abstract_origin #0 "f2"
> > DW_TAG_compile_unit
> >   DW_AT_name "inl2.cpp"
> >   DW_TAG_subprogram
> >     DW_AT_name "c2"
> >     DW_TAG_inlined_subroutine
> >       DW_TAG_abstract_origin #0 "f2"
> >
> > (note that only one abstract definition of f2 is produced here)
> >
> > Any thoughts? I imagine this is probably worth a reasonable amount of
> savings in an optimized build. Not huge, but not nothing. (probably not the
> top of anyone's list though, I realize)
>
> I should see the IR metadata in both cases to really know how it worked
> before, but it seems that to be able to merge the two subprogram
> definitions when linking, we’d need to be able to have a list of CU per
> subprogram instead of a single one, right?
>
> > Should we remove the CU link from a non-internal linkage subprogram
(&
> this may have an effect on the GV representation issue originally being
> discussed) and just emit it into whichever CU happens to need it first?
>
> Looks like this should work as well, but I don’t enough about the way we
> emit Dwarf...
>
Trying a simple prototype, I think the only thing that went really screwy,
was once we don't have that link, how do we pick which CU to put it in?
Does it matter?

So my really rough prototype (that just used the first CU in the CUMap for
all subprograms) of course ended up with this:

DW_TAG_compile_unit
  DW_TAG_subprogram #0
    DW_AT_name "f2"
  DW_TAG_subprogram
    DW_AT_name "c1"
    DW_TAG_inlined_subroutine
      DW_AT_abstract_origin #0
  DW_TAG_subprogram
    DW_AT_name "c2"
    DW_TAG_inlined_subroutine
      DW_AT_abstract_origin #0
DW_TAG_compile_unit

So I suppose we could use the unit when present - and make it present (&
use distinct) when the function definition has external linkage. There's
nothing we intend to deduplicate there & that means external linkage
definitions will go in the right CU, and inline definitions just go
wherever their first use is.

Hmm - I guess that doesn't quite work for ThinLTO? Oh, maybe it does -
it'd
mean we'd have to drop the CU reference and un-distinct when we import.

Hmm - that might simplify importing greatly - then we wouldn't actually
need to import CUs at all?

Don't know if that's a good thing.

- Dave

>
> —
> Mehdi
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20161215/10215ccf/attachment.html>

A few disjoint thoughts; sorry they're so delayed (I skimmed the responses
below, and I think these are still relevant/not covered elsewhere).

Firstly, why *should* DISubprogram definitions be distinct?  There were two
reasons this was valuable (this was from before there was a cu: link).

- It helped to fix long-standing bugs in the IRLinker, where
uniqued-DISubprograms in different compile units would coalesce.  Now that the
Function <-> DISubprogram connection has been reversed, I'm not
entirely sure it's still a necessary precaution.

- It broke a several uniquing cycles involving DISubprogram.  The existence of
the uniquing cycles meant that affected DISubprograms weren't really
uniqued, anyway (since we don't bother to solve graph isomorphism); and
breaking the cycles sped up the IRLinker and reduced memory waste.  Making
DISubprogram uniqued again would either have no real effect (because distinct
nodes they reference aren't uniqued anymore either) or bring back uniquing
cycles (which would have effects... but not the desired one).

But there ought to be a way to get coalescing in the right places.  We just need
to ensure that the uniqued/coalesced parts of the graph:
- are acyclic, and
- reference only coalesced nodes (note that leaves can happily include the
strangely-coalesced distinct DICompositeType beast I created).

I've been thinking idly whether we can/should break DISubprogram apart into
uniqued (coalesce-able) and distinct parts.  Still being someone ignorant of
DWARF itself (and CodeView, for that matter), I'm not entirely sure.  But...

Here's my understanding of the current uses of DISubprogram (where I'm
using DISubprogramDecl for the usually uniqued declarations, and
DISubprogramDefn for the always distinct definitions):

// !dbg
Function -> DISubprogram

// Declaration (optional, only for member functions).
DISubprogramDefn -> DISubprogramDecl

// Variables:
DISubprogramDefn -> MDNode -> DILocalVariable

// Terminator for scope chains:
DILocalVariable [-> DILocalScope [-> ...]] -> DISubprogramDefn
DILocation [-> DILocalScope [-> ...]] -> DISubprogramDefn
DICompositeType -> DISubprogramDefn // function-local type

// Elements (member functions):
DICompositeType -> MDNode -> DISubprogramDecl
DISubprogramDecl -> DICompositeType
DISubprogramDefn -> DICompositeType

And here are the changes I would consider:

1. Split DISubprogramDecl and DISubprogramDefn into different types.

2. Remove definition-specific fields from DISubprogramDecl.
- variables, a "dangerous" source of uniquing cycles.
- declaration, which it will never have.
- scopeLine, which it will never have.
- unit, which the Defn will have when it's relevant.

3. Make a DISubprogramDecl mandatory for DISubprogramDefn.

4. Remove redundant fields from DISubprogramDefn.
- name and linkageName are on the declaration.
- type is redundant.
- flags is likely redundant?

Nothing so far has made any real changes, I think.  DISubprogramDecl should
coalesce nicely between modules though.

5. Migrate links to point at DISubprogramDecl instead of DISubprogramDefn.
- DILocalVariable scope chain.
- DILocation scope chain.
- DICompositeType scope.

I don't think this will create any uniquing cycles.  DISubprogramDecl
won't point at any of these.  Also, DILocalVariable should start coalescing
with each other.

Since DISubprogramDefn is only referenced from the Function !dbg attachment,
only one should survive function-coalescing.

One open question, since I don't know the backend code, is: can you emit the
"correct" DWARF after step (5)?  I'm hoping you only need the Defn
of the Function that has instructions referencing the
DILocalVariable/DILocation.  In which case, we suddenly get a lot of coalescing.
> On 2016-Dec-15, at 10:54, David Blaikie <dblaikie at gmail.com>
wrote:
> 
> Branching off from a discussion of improvements to DIGlobalVariable
representations that Adrian's working on - got me thinking about related
changes that have already been made to DISubprogram.
> 
> To reduce duplicate debug info when things like linkonce_odr functions were
deduplicated in LTO linking, the relationship between a CU and DISubprogram was
inverted (instead of a CU maintaining a list of subprograms, subprograms specify
which CU they come from - and the llvm::Function references the DISubprogram, so
if the llvm::Function goes away, so does the associated DISubprogram)
> 
> I'm not sure if this caused a regression, but at least seems to miss a
possible improvement:
> 
> During IR linking (for LTO, ThinLTO, etc) these distinct DISubprogram
definitions (& their CU link, even if they weren't marked
'distinct', the CU link would cause them to effectively be so) remain
separate - this means that inlined versions in one CU don't refer to an
existing subprogram definition in another CU.
> 
> To demonstrate:
> inl.h:
> void f1();
> inline __attribute__((always_inline)) void f2() {
>   f1();
> }
> inl1.cpp:
> #include "inl.h"
> void c1() {
>   f2();
> }
> inl2.cpp:
> #include "inl.h"
> void c2() {
>   f2();
> }
> 
> Compile to IR, llvm-link the result. The DWARF you get is basically the
same as the DWARF you'd get without linking:
> 
> DW_TAG_compile_unit
>   DW_AT_name "inl1.cpp"
>   DW_TAG_subprogram #0
>     DW_AT_name "f2"
>   DW_TAG_subprogram
>     DW_AT_name "c1"
>     DW_TAG_inlined_subroutine
>       DW_TAG_abstract_origin #0 "f2"
> DW_TAG_compile_unit
>   DW_AT_name "inl2.cpp"
>   DW_TAG_subprogram #1
>     DW_AT_name "f2"
>   DW_TAG_subprogram
>     DW_AT_name "c2"
>     DW_TAG_inlined_subroutine
>       DW_TAG_abstract_origin #1 "f2"
> 
> Instead of something more like this:
> 
> DW_TAG_compile_unit
>   DW_AT_name "inl1.cpp"
>   DW_TAG_subprogram #0
>     DW_AT_name "f2"
>   DW_TAG_subprogram
>     DW_AT_name "c1"
>     DW_TAG_inlined_subroutine
>       DW_TAG_abstract_origin #0 "f2"
> DW_TAG_compile_unit
>   DW_AT_name "inl2.cpp"
>   DW_TAG_subprogram
>     DW_AT_name "c2"
>     DW_TAG_inlined_subroutine
>       DW_TAG_abstract_origin #0 "f2"
> 
> (note that only one abstract definition of f2 is produced here)
> 
> Any thoughts? I imagine this is probably worth a reasonable amount of
savings in an optimized build. Not huge, but not nothing. (probably not the top
of anyone's list though, I realize)
> 
> Should we remove the CU link from a non-internal linkage subprogram (&
this may have an effect on the GV representation issue originally being
discussed) and just emit it into whichever CU happens to need it first?
> 
> This might be slightly sub-optimal, due to, say, the namespace being
foreign to that CU. But it's how we do types currently, I think? So at least
it'd be consistent and probably cheap enough/better.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20161223/7874e136/attachment-0001.html>

On Fri, Dec 23, 2016 at 11:47 AM Duncan P. N. Exon Smith <
dexonsmith at apple.com> wrote:
> A few disjoint thoughts; sorry they're so delayed (I skimmed the
responses
> below, and I think these are still relevant/not covered elsewhere).
>
> Firstly, why *should* DISubprogram definitions be distinct?  There were
> two reasons this was valuable (this was from before there was a cu: link).
>
> - It helped to fix long-standing bugs in the IRLinker, where
> uniqued-DISubprograms in different compile units would coalesce.
>
Any idea why that ^ was a problem/bugs?

>  Now that the Function <-> DISubprogram connection has been reversed,
I'm
> not entirely sure it's still a necessary precaution.
>
> - It broke a several uniquing cycles involving DISubprogram.  The
> existence of the uniquing cycles meant that affected DISubprograms
weren't
> really uniqued, anyway (since we don't bother to solve graph
isomorphism);
> and breaking the cycles sped up the IRLinker and reduced memory waste.
>
Ah, fair point - my trivial example didn't have any local variables, so
didn't hit this problem. They do indeed form cycles and I haven't
tested,
but seems totally reasonable/likely that that would break my simple example
because cycles break uniquing and all that.

>  Making DISubprogram uniqued again would either have no real effect
> (because distinct nodes they reference aren't uniqued anymore either)
or
> bring back uniquing cycles (which would have effects... but not the desired
> one).
>
> But there ought to be a way to get coalescing in the right places.  We
> just need to ensure that the uniqued/coalesced parts of the graph:
> - are acyclic, and
> - reference only coalesced nodes (note that leaves can happily include the
> strangely-coalesced distinct DICompositeType beast I created).
>
Perhaps before I dive into your suggestion (which, it seems, is to separate
out the definition but let the declaration/locals form cycles - that would
at least be dropped because the definition would only be kept due to it
being referenced from the llvm::Function), what about something simpler:

What if scope chains didn't go all the way to the top (the subprogram) but
stopped short of that?

Now, granted - this was part of the great assertion I added several years
back that caught all kinds of silliness - mostly around inlined call sites
not having debugloc and leading to scope chains that lead to distinct
roots. But the alternative to having and maintaining an invariant - is just
to make things true by construction. All debug info scope chains within a
function with an associated DISubprogram have an implicit last element of
that DISubprogram?

That would mean it'd be harder to catch the bugs I found - but I think most
of them came from that specific inlining situation (I can go back and do
some archaeology and see if there's other exposure where we could sure up
some defenses as well) which can be caught more directly (I forget if the
inliner now catches it itself, or if we enhanced the debug info verifier to
catch it after the inliner runs - if it's the verifier, then that
wouldn't
suffice if we made the change I'm suggesting - and we'd have to hook it
up
in the inliner itself)

Thoughts?

>
> I've been thinking idly whether we can/should break DISubprogram apart
> into uniqued (coalesce-able) and distinct parts.  Still being someone
> ignorant of DWARF itself (and CodeView, for that matter), I'm not
entirely
> sure.  But...
>
> Here's my understanding of the current uses of DISubprogram (where
I'm
> using DISubprogramDecl for the usually uniqued declarations, and
> DISubprogramDefn for the always distinct definitions):
>
> // !dbg
> Function -> DISubprogram
>
> // Declaration (optional, only for member functions).
> DISubprogramDefn -> DISubprogramDecl
>
> // Variables:
> DISubprogramDefn -> MDNode -> DILocalVariable
>
> // Terminator for scope chains:
> DILocalVariable [-> DILocalScope [-> ...]] -> DISubprogramDefn
> DILocation [-> DILocalScope [-> ...]] -> DISubprogramDefn
> DICompositeType -> DISubprogramDefn // function-local type
>
> // Elements (member functions):
> DICompositeType -> MDNode -> DISubprogramDecl
> DISubprogramDecl -> DICompositeType
> DISubprogramDefn -> DICompositeType
>
>
> And here are the changes I would consider:
>
> 1. Split DISubprogramDecl and DISubprogramDefn into different types.
>
> 2. Remove definition-specific fields from DISubprogramDecl.
> - variables, a "dangerous" source of uniquing cycles.
> - declaration, which it will never have.
> - scopeLine, which it will never have.
> - unit, which the Defn will have when it's relevant.
>
> 3. Make a DISubprogramDecl mandatory for DISubprogramDefn.
>
> 4. Remove redundant fields from DISubprogramDefn.
> - name and linkageName are on the declaration.
> - type is redundant.
> - flags is likely redundant?
>
> Nothing so far has made any real changes, I think.  DISubprogramDecl
> should coalesce nicely between modules though.
>
> 5. Migrate links to point at DISubprogramDecl instead of DISubprogramDefn.
> - DILocalVariable scope chain.
> - DILocation scope chain.
> - DICompositeType scope.
>
> I don't think this will create any uniquing cycles.  DISubprogramDecl
> won't point at any of these.  Also, DILocalVariable should start
coalescing
> with each other.
>
> Since DISubprogramDefn is only referenced from the Function !dbg
> attachment, only one should survive function-coalescing.
>
> One open question, since I don't know the backend code, is: can you
emit
> the "correct" DWARF after step (5)?  I'm hoping you only need
the Defn of
> the Function that has instructions referencing the
> DILocalVariable/DILocation.  In which case, we suddenly get a lot of
> coalescing.
>
> On 2016-Dec-15, at 10:54, David Blaikie <dblaikie at gmail.com>
wrote:
>
> Branching off from a discussion of improvements to DIGlobalVariable
> representations that Adrian's working on - got me thinking about
related
> changes that have already been made to DISubprogram.
>
> To reduce duplicate debug info when things like linkonce_odr functions
> were deduplicated in LTO linking, the relationship between a CU and
> DISubprogram was inverted (instead of a CU maintaining a list
> of subprograms, subprograms specify which CU they come from - and the
> llvm::Function references the DISubprogram, so if the llvm::Function goes
> away, so does the associated DISubprogram)
>
> I'm not sure if this caused a regression, but at least seems to miss a
> possible improvement:
>
> During IR linking (for LTO, ThinLTO, etc) these distinct DISubprogram
> definitions (& their CU link, even if they weren't marked
'distinct', the
> CU link would cause them to effectively be so) remain separate - this means
> that inlined versions in one CU don't refer to an existing subprogram
> definition in another CU.
>
> To demonstrate:
> inl.h:
> void f1();
> inline __attribute__((always_inline)) void f2() {
>   f1();
> }
> inl1.cpp:
> #include "inl.h"
> void c1() {
>   f2();
> }
> inl2.cpp:
> #include "inl.h"
> void c2() {
>   f2();
> }
>
> Compile to IR, llvm-link the result. The DWARF you get is basically the
> same as the DWARF you'd get without linking:
>
> DW_TAG_compile_unit
>   DW_AT_name "inl1.cpp"
>   DW_TAG_subprogram #0
>     DW_AT_name "f2"
>   DW_TAG_subprogram
>     DW_AT_name "c1"
>     DW_TAG_inlined_subroutine
>       DW_TAG_abstract_origin #0 "f2"
> DW_TAG_compile_unit
>   DW_AT_name "inl2.cpp"
>   DW_TAG_subprogram #1
>     DW_AT_name "f2"
>   DW_TAG_subprogram
>     DW_AT_name "c2"
>     DW_TAG_inlined_subroutine
>       DW_TAG_abstract_origin #1 "f2"
>
> Instead of something more like this:
>
> DW_TAG_compile_unit
>   DW_AT_name "inl1.cpp"
>   DW_TAG_subprogram #0
>     DW_AT_name "f2"
>   DW_TAG_subprogram
>     DW_AT_name "c1"
>     DW_TAG_inlined_subroutine
>       DW_TAG_abstract_origin #0 "f2"
> DW_TAG_compile_unit
>   DW_AT_name "inl2.cpp"
>   DW_TAG_subprogram
>     DW_AT_name "c2"
>     DW_TAG_inlined_subroutine
>       DW_TAG_abstract_origin #0 "f2"
>
> (note that only one abstract definition of f2 is produced here)
>
> Any thoughts? I imagine this is probably worth a reasonable amount of
> savings in an optimized build. Not huge, but not nothing. (probably not the
> top of anyone's list though, I realize)
>
> Should we remove the CU link from a non-internal linkage subprogram (&
> this may have an effect on the GV representation issue originally being
> discussed) and just emit it into whichever CU happens to need it first?
>
> This might be slightly sub-optimal, due to, say, the namespace being
> foreign to that CU. But it's how we do types currently, I think? So at
> least it'd be consistent and probably cheap enough/better.
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20161223/36bec107/attachment-0001.html>