Changes in Hoopl

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

Changes in Hoopl

Jan Stolarek
Me and Simon PJ had some discussion about modifying Hoopl. I summarized that discussion on a wiki page:

http://ghc.haskell.org/trac/ghc/wiki/Hoopl/Cleanup

I'd like to implement changes once there's a consensus on which changes exactly do we want in Hoopl.

Janek



Reply | Threaded
Open this post in threaded view
|

Changes in Hoopl

David Luposchainsky
Hey Janek,

as a remark, Hoopl is the only library in GHC that defines its own "<*>"
operation, which will clash with the AMP. Hoopl's <*> is conceptually
just `mappend`, so if you're doing a large-scale refactoring of the
module maybe consider adding a suitable Monoid instance to replace <*>
with <> before it even becomes a problem.

David



Reply | Threaded
Open this post in threaded view
|

Changes in Hoopl

Simon Marlow-7
In reply to this post by Jan Stolarek
Hi Jan,

On 22/08/13 14:01, Jan Stolarek wrote:
> Me and Simon PJ had some discussion about modifying Hoopl. I summarized that discussion on a wiki page:
>
> http://ghc.haskell.org/trac/ghc/wiki/Hoopl/Cleanup
>
> I'd like to implement changes once there's a consensus on which changes exactly do we want in Hoopl.

I'm all for cleaning up Hoopl.  It's definitely a bit of a mess in places.

I read through your wiki page and I'm not entirely clear about what
changes you're proposing.  e.g. it's probably true that in forward
analysis if you specify facts for all the input labels then fact_bot is
never used (though I'm not 100% sure about that).  But you don't say
what you want to do with that observation.  Could you list the API
changes you want to make?

Cheers,
        Simon




Reply | Threaded
Open this post in threaded view
|

Changes in Hoopl

Jan Stolarek
> But you don't say what you want to do with that observation.
> Could you list the API changes you want to make?

Sure, I'll write down the exact changes I'm thinking of, but probably next week - I'll let you know that I updated the wiki page.

Janek



Reply | Threaded
Open this post in threaded view
|

Changes in Hoopl

Simon Peyton Jones
In reply to this post by Simon Marlow-7
I have elaborated (more clearly I hope)

S

| -----Original Message-----
| From: Simon Marlow [mailto:marlowsd at gmail.com]
| Sent: 22 August 2013 15:14
| To: Jan Stolarek
| Cc: ghc-devs; Simon Peyton-Jones; nr at cs.tufts.edu; dias at cs.tufts.edu;
| Edward Z. Yang
| Subject: Re: Changes in Hoopl
|
| Hi Jan,
|
| On 22/08/13 14:01, Jan Stolarek wrote:
| > Me and Simon PJ had some discussion about modifying Hoopl. I
| summarized that discussion on a wiki page:
| >
| > http://ghc.haskell.org/trac/ghc/wiki/Hoopl/Cleanup
| >
| > I'd like to implement changes once there's a consensus on which
| changes exactly do we want in Hoopl.
|
| I'm all for cleaning up Hoopl.  It's definitely a bit of a mess in
| places.
|
| I read through your wiki page and I'm not entirely clear about what
| changes you're proposing.  e.g. it's probably true that in forward
| analysis if you specify facts for all the input labels then fact_bot is
| never used (though I'm not 100% sure about that).  But you don't say
| what you want to do with that observation.  Could you list the API
| changes you want to make?
|
| Cheers,
| Simon


Reply | Threaded
Open this post in threaded view
|

Changes in Hoopl

Jan Stolarek
Simon, you give this example:

   L1: ...blah blah...
       CondBranch e L1 L2

   L2: blah blah

and say that "(...) on the first iteration, we don't have any fact from L1. So for backwards analysis the client really must give us a bottom element. " I think this example does not actually demonstrate that we must have a bottom element, because if we have fact from L2 then we still don't need bottom in the same way we don't need it in forward analysis. We need bottom only when all entry facts are unknown.

Janek

----- Oryginalna wiadomo?? -----
Od: "Simon Peyton-Jones" <simonpj at microsoft.com>
Do: "Simon Marlow" <marlowsd at gmail.com>, "Jan Stolarek" <jan.stolarek at p.lodz.pl>
DW: "ghc-devs" <ghc-devs at haskell.org>, nr at cs.tufts.edu, dias at cs.tufts.edu, "Edward Z. Yang" <ezyang at mit.edu>
Wys?ane: czwartek, 22 sierpie? 2013 17:44:11
Temat: RE: Changes in Hoopl

I have elaborated (more clearly I hope)

S

| -----Original Message-----
| From: Simon Marlow [mailto:marlowsd at gmail.com]
| Sent: 22 August 2013 15:14
| To: Jan Stolarek
| Cc: ghc-devs; Simon Peyton-Jones; nr at cs.tufts.edu; dias at cs.tufts.edu;
| Edward Z. Yang
| Subject: Re: Changes in Hoopl
|
| Hi Jan,
|
| On 22/08/13 14:01, Jan Stolarek wrote:
| > Me and Simon PJ had some discussion about modifying Hoopl. I
| summarized that discussion on a wiki page:
| >
| > http://ghc.haskell.org/trac/ghc/wiki/Hoopl/Cleanup
| >
| > I'd like to implement changes once there's a consensus on which
| changes exactly do we want in Hoopl.
|
| I'm all for cleaning up Hoopl.  It's definitely a bit of a mess in
| places.
|
| I read through your wiki page and I'm not entirely clear about what
| changes you're proposing.  e.g. it's probably true that in forward
| analysis if you specify facts for all the input labels then fact_bot is
| never used (though I'm not 100% sure about that).  But you don't say
| what you want to do with that observation.  Could you list the API
| changes you want to make?
|
| Cheers,
| Simon




Reply | Threaded
Open this post in threaded view
|

Changes in Hoopl

Simon Marlow-7
In reply to this post by Simon Peyton Jones
The proposed changes look fine to me.

A couple of thoughts:

1. This adds a new constraint on the dataflow algorithm, namely that it
must traverse the blocks in the correct order.  I think that's a *good*
thing, because we definitely want to traverse blocks in the right order
for performance reasons, and now if we get it wrong the algorithm will
crash.  I got the order wrong more than once while working on hoopl, and
the only consequence was that things were slower than necessary.

2. Has anyone tried implementing this change?  I'm slightly concerned
that having a difference between forward and backward analyses might
lead to divergence in some of the shared parts of the internals of the
algorithm.  But maybe it will work out ok.  Do please measure
performance carefully though.

Cheers,
        Simon


On 22/08/13 17:44, Simon Peyton-Jones wrote:

> I have elaborated (more clearly I hope)
>
> S
>
> | -----Original Message-----
> | From: Simon Marlow [mailto:marlowsd at gmail.com]
> | Sent: 22 August 2013 15:14
> | To: Jan Stolarek
> | Cc: ghc-devs; Simon Peyton-Jones; nr at cs.tufts.edu; dias at cs.tufts.edu;
> | Edward Z. Yang
> | Subject: Re: Changes in Hoopl
> |
> | Hi Jan,
> |
> | On 22/08/13 14:01, Jan Stolarek wrote:
> | > Me and Simon PJ had some discussion about modifying Hoopl. I
> | summarized that discussion on a wiki page:
> | >
> | > http://ghc.haskell.org/trac/ghc/wiki/Hoopl/Cleanup
> | >
> | > I'd like to implement changes once there's a consensus on which
> | changes exactly do we want in Hoopl.
> |
> | I'm all for cleaning up Hoopl.  It's definitely a bit of a mess in
> | places.
> |
> | I read through your wiki page and I'm not entirely clear about what
> | changes you're proposing.  e.g. it's probably true that in forward
> | analysis if you specify facts for all the input labels then fact_bot is
> | never used (though I'm not 100% sure about that).  But you don't say
> | what you want to do with that observation.  Could you list the API
> | changes you want to make?
> |
> | Cheers,
> | Simon
>




Reply | Threaded
Open this post in threaded view
|

Changes in Hoopl

Jan Stolarek
> 1. This adds a new constraint on the dataflow algorithm, namely that it
> must traverse the blocks in the correct order.
I don't follow. From what I've seen in the code Hoopl orders blocks using depth-first traversal.
For backwards analysis it reverses that order. I don't think that proposed changes will affect
this. What did I miss?

> 2. Has anyone tried implementing this change?  I'm slightly concerned
> that having a difference between forward and backward analyses might
> lead to divergence in some of the shared parts of the internals of the
> algorithm.
If it turns out that forward and backward cases have to diverge to implement this change, will
that be acceptable? GHC's specialized Hoopl module (compiler/cmm/Hoopl/Dataflow) already has
separate functions for handling forward and backward analysis.

Janek



Reply | Threaded
Open this post in threaded view
|

Changes in Hoopl

Simon Marlow-7
On 26/08/13 10:00, Jan Stolarek wrote:
>> 1. This adds a new constraint on the dataflow algorithm, namely that it
>> must traverse the blocks in the correct order.
> I don't follow. From what I've seen in the code Hoopl orders blocks using depth-first traversal.
> For backwards analysis it reverses that order. I don't think that proposed changes will affect
> this. What did I miss?

You didn't miss anything.  The new constraint is that forwards analysis
*must* process blocks in this order, whereas previously it didn't have to.

>> 2. Has anyone tried implementing this change?  I'm slightly concerned
>> that having a difference between forward and backward analyses might
>> lead to divergence in some of the shared parts of the internals of the
>> algorithm.
> If it turns out that forward and backward cases have to diverge to implement this change, will
> that be acceptable? GHC's specialized Hoopl module (compiler/cmm/Hoopl/Dataflow) already has
> separate functions for handling forward and backward analysis.

But they share the core fixpoint algorithm underneath: fixpoint,
fixpointAnal, and some auxiliary functions.  It's not a big deal.  This
code is heavily tuned though, so keep an eye on performance.

Cheers,
        Simon