Finding out if a binding is externally visible

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
9 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Finding out if a binding is externally visible

Sebastian Graf
Hi all,

I'm tinkering around with GHCs Call Arity Analysis and Demand Analysis as part of my Master's thesis. The usage analysis part is what I'm interested in in particular.

After quite some time spent debugging absent errors, I noticed that certain top-level bindings aren't exported, but still visible in other modules through generated RULE pragmas (e.g. through class instance specialization). These bindings were considered absent in my combined analysis, explaining the very sporadic absent errors I was getting.

Is there some function that tells me if an identifier is 'externally visible' in that sense? I think https://downloads.haskell.org/~ghc/8.0.1/docs/html/libraries/ghc-8.0.1/GHC.html#v:isExternalName is what I'm after, but I want to be sure. Does that function already work when the Ids are still local?

Greetings,
Sebastian

_______________________________________________
ghc-devs mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Finding out if a binding is externally visible

Sebastian Graf
I just stumbled over Note [ExportFlag on binders] in Var.hs, which indicates this might be a bug, right?

On Sun, May 28, 2017 at 5:52 PM, Sebastian Graf <[hidden email]> wrote:
Hi all,

I'm tinkering around with GHCs Call Arity Analysis and Demand Analysis as part of my Master's thesis. The usage analysis part is what I'm interested in in particular.

After quite some time spent debugging absent errors, I noticed that certain top-level bindings aren't exported, but still visible in other modules through generated RULE pragmas (e.g. through class instance specialization). These bindings were considered absent in my combined analysis, explaining the very sporadic absent errors I was getting.

Is there some function that tells me if an identifier is 'externally visible' in that sense? I think https://downloads.haskell.org/~ghc/8.0.1/docs/html/libraries/ghc-8.0.1/GHC.html#v:isExternalName is what I'm after, but I want to be sure. Does that function already work when the Ids are still local?

Greetings,
Sebastian


_______________________________________________
ghc-devs mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Finding out if a binding is externally visible

Joachim Breitner-2
In reply to this post by Sebastian Graf
Hi Sebastian,

welcome on this list!

Am Sonntag, den 28.05.2017, 17:52 +0200 schrieb Sebastian Graf:
> Is there some function that tells me if an identifier is 'externally
> visible' in that sense? I think https://downloads.haskell.org/~ghc/8.
> 0.1/docs/html/libraries/ghc-8.0.1/GHC.html#v:isExternalName is what
> I'm after, but I want to be sure. Does that function already work
> when the Ids are still local?

I would expect

    isExportedId :: Var -> Bool

to do precisely that.

Greetings,
Joachim

--
Joachim “nomeata” Breitner
  [hidden email]https://www.joachim-breitner.de/
  XMPP: [hidden email] • OpenPGP-Key: 0xF0FBF51F
  Debian Developer: [hidden email]
_______________________________________________
ghc-devs mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs

signature.asc (849 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Finding out if a binding is externally visible

Sebastian Graf

welcome on this list!

Thanks :)

     isExportedId :: Var -> Bool

That's what I have been using so far, but I found that said RULE pragmas mentioned non-exported identifiers. Or maybe it was just some temporary build system mess-up, I'll work on a reproduction...

On Sun, May 28, 2017 at 10:33 PM, Joachim Breitner <[hidden email]> wrote:
Hi Sebastian,

welcome on this list!

Am Sonntag, den 28.05.2017, 17:52 +0200 schrieb Sebastian Graf:
> Is there some function that tells me if an identifier is 'externally
> visible' in that sense? I think https://downloads.haskell.org/~ghc/8.
> 0.1/docs/html/libraries/ghc-8.0.1/GHC.html#v:isExternalName is what
> I'm after, but I want to be sure. Does that function already work
> when the Ids are still local?

I would expect

    isExportedId :: Var -> Bool

to do precisely that.

Greetings,
Joachim

--
Joachim “nomeata” Breitner
  [hidden email]https://www.joachim-breitner.de/
  XMPP: [hidden email] • OpenPGP-Key: 0xF0FBF51F
  Debian Developer: [hidden email]

_______________________________________________
ghc-devs mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs



_______________________________________________
ghc-devs mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Finding out if a binding is externally visible

Sebastian Graf
OK, I attached an example for a specialization of Show for a special case of a custom type, like Ratio in GHC.Real. My invokation with a custom GHC (8.0-based) was like this:

    $ <ghc> Module.hs -ddump-simpl -O -fforce-recomp

At the begin of the log, I listed all exported top-level identifiers, the only interesting of which is `$fShowRatio :: Show a => Show (Ratio a)`, the default implementation. Note that at the bottom, there are RULEs stating the specialization for `Show Integer`, but that the specialized dictionary `$fShowRatio_$s$fShowRatio :: Show (Ratio Integer)` isn't otherwise reachable from any exported top-level identifier. Same goes for any of the specialized dictionary methods.

Now consider what happens if we request a `Show (Ratio Integer)` dictionary in another module: GHC finds the exported default dictionary `$fShowRatio :: Show a => Show (Ratio a)`, but then applies a specialization RULE that will effectively use the presumably absent `$fShowRatio_$s$fShowRatio :: Show (Ratio Integer)`.

In my case, my custom GHC would substitute away the `showString " % "` for an `absentError "lvl [Char]"` and crash in subtle ways. The only reason this isn't happening for GHC master is that DmdAnal does consider all top-level arguments to be used, instead of only the exported ones (which is what CallArity does).

On Sun, May 28, 2017 at 11:53 PM, Sebastian Graf <[hidden email]> wrote:

welcome on this list!

Thanks :)

     isExportedId :: Var -> Bool

That's what I have been using so far, but I found that said RULE pragmas mentioned non-exported identifiers. Or maybe it was just some temporary build system mess-up, I'll work on a reproduction...

On Sun, May 28, 2017 at 10:33 PM, Joachim Breitner <[hidden email]> wrote:
Hi Sebastian,

welcome on this list!

Am Sonntag, den 28.05.2017, 17:52 +0200 schrieb Sebastian Graf:
> Is there some function that tells me if an identifier is 'externally
> visible' in that sense? I think https://downloads.haskell.org/~ghc/8.
> 0.1/docs/html/libraries/ghc-8.0.1/GHC.html#v:isExternalName is what
> I'm after, but I want to be sure. Does that function already work
> when the Ids are still local?

I would expect

    isExportedId :: Var -> Bool

to do precisely that.

Greetings,
Joachim

--
Joachim “nomeata” Breitner
  [hidden email]https://www.joachim-breitner.de/
  XMPP: [hidden email] • OpenPGP-Key: 0xF0FBF51F
  Debian Developer: [hidden email]

_______________________________________________
ghc-devs mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs




_______________________________________________
ghc-devs mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs

log.txt (18K) Download Attachment
Module.hs (302 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Finding out if a binding is externally visible

Sebastian Graf
Also I should add that this is probably not just happening for ids mentioned by RULEs, but also for Unfoldings. E.g. although wrappers are exported, associated workers are not, but still visible through unfoldings. It's not as bad as with RULEs since they are still reachable, but it might make for weird results... And also contradicts Note [ExportFlag on binders] in Var.hs as I understand it.

On Mon, May 29, 2017 at 10:40 AM, Sebastian Graf <[hidden email]> wrote:
OK, I attached an example for a specialization of Show for a special case of a custom type, like Ratio in GHC.Real. My invokation with a custom GHC (8.0-based) was like this:

    $ <ghc> Module.hs -ddump-simpl -O -fforce-recomp

At the begin of the log, I listed all exported top-level identifiers, the only interesting of which is `$fShowRatio :: Show a => Show (Ratio a)`, the default implementation. Note that at the bottom, there are RULEs stating the specialization for `Show Integer`, but that the specialized dictionary `$fShowRatio_$s$fShowRatio :: Show (Ratio Integer)` isn't otherwise reachable from any exported top-level identifier. Same goes for any of the specialized dictionary methods.

Now consider what happens if we request a `Show (Ratio Integer)` dictionary in another module: GHC finds the exported default dictionary `$fShowRatio :: Show a => Show (Ratio a)`, but then applies a specialization RULE that will effectively use the presumably absent `$fShowRatio_$s$fShowRatio :: Show (Ratio Integer)`.

In my case, my custom GHC would substitute away the `showString " % "` for an `absentError "lvl [Char]"` and crash in subtle ways. The only reason this isn't happening for GHC master is that DmdAnal does consider all top-level arguments to be used, instead of only the exported ones (which is what CallArity does).

On Sun, May 28, 2017 at 11:53 PM, Sebastian Graf <[hidden email]> wrote:

welcome on this list!

Thanks :)

     isExportedId :: Var -> Bool

That's what I have been using so far, but I found that said RULE pragmas mentioned non-exported identifiers. Or maybe it was just some temporary build system mess-up, I'll work on a reproduction...

On Sun, May 28, 2017 at 10:33 PM, Joachim Breitner <[hidden email]> wrote:
Hi Sebastian,

welcome on this list!

Am Sonntag, den 28.05.2017, 17:52 +0200 schrieb Sebastian Graf:
> Is there some function that tells me if an identifier is 'externally
> visible' in that sense? I think https://downloads.haskell.org/~ghc/8.
> 0.1/docs/html/libraries/ghc-8.0.1/GHC.html#v:isExternalName is what
> I'm after, but I want to be sure. Does that function already work
> when the Ids are still local?

I would expect

    isExportedId :: Var -> Bool

to do precisely that.

Greetings,
Joachim

--
Joachim “nomeata” Breitner
  [hidden email]https://www.joachim-breitner.de/
  XMPP: [hidden email] • OpenPGP-Key: 0xF0FBF51F
  Debian Developer: [hidden email]

_______________________________________________
ghc-devs mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs





_______________________________________________
ghc-devs mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Finding out if a binding is externally visible

Joachim Breitner-2
In reply to this post by Sebastian Graf
Hi,

Am Montag, den 29.05.2017, 10:40 +0200 schrieb Sebastian Graf:
> Note that at the bottom,
> there are RULEs stating the specialization for `Show Integer`, but
> that the specialized dictionary `$fShowRatio_$s$fShowRatio :: Show
> (Ratio Integer)` isn't otherwise reachable from any exported top-
> level identifier. Same goes for any of the specialized dictionary
> methods.

At least the Occurrence Analyzer keeps things referenced from RULES
alive:

    initial_uds = addManyOccsSet emptyDetails
                            (rulesFreeVars imp_rules `unionVarSet`
                             vectsFreeVars vects `unionVarSet`
                             vectVars)
    -- The RULES and VECTORISE declarations keep things alive!

So maybe the isExportedId is not the full truths that we are looking
for here… which would mean that CallArity might be buggy in that
respect.

This does not contradict Note [ExportFlag on binders] – these IDs do
not need to be marked Exported, as they are kept alive by the RULE.
Would we drop, for whatever reason, the RULE, we would drop the id.

> In my case, my custom GHC would substitute away the `showString " %
> "` for an `absentError "lvl [Char]"` and crash in subtle ways. The
> only reason this isn't happening for GHC master is that DmdAnal does
> consider all top-level arguments to be used, instead of only the
> exported ones (which is what CallArity does).

It seems that CallArity is wrong here, and DmdAnal is right. The way
out is probably to have CallArity take RULES properly into account.

Greetings,
Joachim
--
Joachim “nomeata” Breitner
  [hidden email]https://www.joachim-breitner.de/
  XMPP: [hidden email] • OpenPGP-Key: 0xF0FBF51F
  Debian Developer: [hidden email]
_______________________________________________
ghc-devs mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs

signature.asc (849 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Finding out if a binding is externally visible

Sebastian Graf
Occurrence Analyzer
 
Ahh, good thinking. 

Do Unfoldings qualify in the same way? Currently, workers all get usage C^w(C^1(...(U))) instead of U in the combined analysis, because they are also not regarded 'externally visible'. There are a lot more one-shot lambdas as a consequence, some of which might not be intuitive: As I understand, the simplifier may inline and share an eta-reduced version of an unfolding from another module at any point. This will not produce incorrect code, but it's a decision that should be made consciously and documented appropriately. 

So, what binders do I have to consider as 'roots' apart from exports, RULEs, VECTORISE and possibly Unfoldings? That should be pretty much everything relevant, if the occurence analyser gets away with it, right?

On Mon, May 29, 2017 at 5:08 PM, Joachim Breitner <[hidden email]> wrote:
Hi,

Am Montag, den 29.05.2017, 10:40 +0200 schrieb Sebastian Graf:
> Note that at the bottom,
> there are RULEs stating the specialization for `Show Integer`, but
> that the specialized dictionary `$fShowRatio_$s$fShowRatio :: Show
> (Ratio Integer)` isn't otherwise reachable from any exported top-
> level identifier. Same goes for any of the specialized dictionary
> methods.

At least the Occurrence Analyzer keeps things referenced from RULES
alive:

    initial_uds = addManyOccsSet emptyDetails
                            (rulesFreeVars imp_rules `unionVarSet`
                             vectsFreeVars vects `unionVarSet`
                             vectVars)
    -- The RULES and VECTORISE declarations keep things alive!

So maybe the isExportedId is not the full truths that we are looking
for here… which would mean that CallArity might be buggy in that
respect.

This does not contradict Note [ExportFlag on binders] – these IDs do
not need to be marked Exported, as they are kept alive by the RULE.
Would we drop, for whatever reason, the RULE, we would drop the id.

> In my case, my custom GHC would substitute away the `showString " %
> "` for an `absentError "lvl [Char]"` and crash in subtle ways. The
> only reason this isn't happening for GHC master is that DmdAnal does
> consider all top-level arguments to be used, instead of only the
> exported ones (which is what CallArity does).

It seems that CallArity is wrong here, and DmdAnal is right. The way
out is probably to have CallArity take RULES properly into account.

Greetings,
Joachim
--
Joachim “nomeata” Breitner
  [hidden email]https://www.joachim-breitner.de/
  XMPP: [hidden email] • OpenPGP-Key: 0xF0FBF51F
  Debian Developer: [hidden email]

_______________________________________________
ghc-devs mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs



_______________________________________________
ghc-devs mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Finding out if a binding is externally visible

Joachim Breitner-2
Hi,

Am Montag, den 29.05.2017, 17:28 +0200 schrieb Sebastian Graf:
> > Occurrence Analyzer
> Ahh, good thinking. 
>
> Do Unfoldings qualify in the same way?

Unfoldings are kept alive together with the thing they unfold (so that
you can remove an unfolding together with its Id should that get
unused). And for most analyses, it makes sense to consider them an
alternative RHS, so if you have

f [Unfolding = \x -> bar x]
f = \x -> foo x

then that is a bit like

f x = case coinToss of True -> bar x
                       False -> foo x

> So, what binders do I have to consider as 'roots' apart from exports,
> RULEs, VECTORISE and possibly Unfoldings? That should be pretty much
> everything relevant, if the occurence analyser gets away with it,
> right?

If the occurence analyser gets away with it, then so do you :-)

But Unfoldings are not roots; they are referenced by the ID they
unfold.

(I wonder if the same can be said for non-orphan RULES, but maybe that
is just too much a corner case.)

Greetings,
Joachim


--
Joachim “nomeata” Breitner
  [hidden email]https://www.joachim-breitner.de/
  XMPP: [hidden email] • OpenPGP-Key: 0xF0FBF51F
  Debian Developer: [hidden email]
_______________________________________________
ghc-devs mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs

signature.asc (849 bytes) Download Attachment
Loading...