Some more questions about Cmm pipeline

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

Some more questions about Cmm pipeline

Jan Stolarek
Hi Simon,

I have two questions about the Cmm pipeline:

1. I implemented a pass that replaces tail calls with a copy of the entry block we're calling to. This is slightly extended version of loopification which will hopefully enable further optimisations. Then I noticed that loopification pass used to be implemented (cmm/CmmOpt.hs, line 418) but was commented out (d92bd17ffd8715f77fd49de0fed6e39c8d0ec28b). There's also a comment: "XXX: revisit if we actually want to do this". What was the motivation for removing loopification? Is there a reason why we might not want to do it?

2. There is a module cmm/CmmRewriteAssignments.hs, which is not used at the moment. What was the motivation for disabling that pass?

Janek


Reply | Threaded
Open this post in threaded view
|

Some more questions about Cmm pipeline

Simon Marlow-7
1. Was a quick hack that I did sometime in the past, it probably didn't
work fully. Nowadays LLVM does loopification, so its not clear whether
there's any benefit to doing it in cmm (but maybe there's some other payoff
that we can get by doing it earlier).

2. Is Edward Yang's optimisation pass. Disabled because it is crazy
expensive; I wrote CmmSink instead which does most of the same things and a
few more. We should remove the code now that we're not going to use it.
On 11 Jul 2013 11:37, "Jan Stolarek" <jan.stolarek at p.lodz.pl> wrote:

> Hi Simon,
>
> I have two questions about the Cmm pipeline:
>
> 1. I implemented a pass that replaces tail calls with a copy of the entry
> block we're calling to. This is slightly extended version of loopification
> which will hopefully enable further optimisations. Then I noticed that
> loopification pass used to be implemented (cmm/CmmOpt.hs, line 418) but was
> commented out (d92bd17ffd8715f77fd49de0fed6e39c8d0ec28b). There's also a
> comment: "XXX: revisit if we actually want to do this". What was the
> motivation for removing loopification? Is there a reason why we might not
> want to do it?
>
> 2. There is a module cmm/CmmRewriteAssignments.hs, which is not used at
> the moment. What was the motivation for disabling that pass?
>
> Janek
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/ghc-devs/attachments/20130711/d1b73ffb/attachment.htm>

Reply | Threaded
Open this post in threaded view
|

Some more questions about Cmm pipeline

Jan Stolarek
Thank you both for explanations. I will try to clean up the code of Cmm pipeline a little bit.

Janek

----- Oryginalna wiadomo?? -----
Od: "Simon Marlow" <marlowsd at gmail.com>
Do: "Jan Stolarek" <jan.stolarek at p.lodz.pl>
DW: ghc-devs at haskell.org
Wys?ane: czwartek, 11 lipiec 2013 17:52:49
Temat: Re: Some more questions about Cmm pipeline



1. Was a quick hack that I did sometime in the past, it probably didn't work fully. Nowadays LLVM does loopification, so its not clear whether there's any benefit to doing it in cmm (but maybe there's some other payoff that we can get by doing it earlier).

2. Is Edward Yang's optimisation pass. Disabled because it is crazy expensive; I wrote CmmSink instead which does most of the same things and a few more. We should remove the code now that we're not going to use it.
On 11 Jul 2013 11:37, "Jan Stolarek" < jan.stolarek at p.lodz.pl > wrote:


Hi Simon,

I have two questions about the Cmm pipeline:

1. I implemented a pass that replaces tail calls with a copy of the entry block we're calling to. This is slightly extended version of loopification which will hopefully enable further optimisations. Then I noticed that loopification pass used to be implemented (cmm/CmmOpt.hs, line 418) but was commented out (d92bd17ffd8715f77fd49de0fed6e39c8d0ec28b). There's also a comment: "XXX: revisit if we actually want to do this". What was the motivation for removing loopification? Is there a reason why we might not want to do it?

2. There is a module cmm/CmmRewriteAssignments.hs, which is not used at the moment. What was the motivation for disabling that pass?

Janek


Reply | Threaded
Open this post in threaded view
|

Some more questions about Cmm pipeline

Jan Stolarek
In reply to this post by Simon Marlow-7
I have two more questions:

3. I will be doing copy propagation within a procedure graph, after which I will need to run dead code elimination. My understanding of CmmLive is that it computes liveness analysis at the entry to each basic block, which implies I will not be able to use information generated by CmmLive for dead code elimination within a block. Is that correct?

4. Speaking of unused code, there is a disabled CmmSink pass just before stack layout is done. Can I remove that commented fragment or are there plans to re-enable this pass at some point in the future?

Janek

----- Oryginalna wiadomo?? -----
Od: "Simon Marlow" <marlowsd at gmail.com>
Do: "Jan Stolarek" <jan.stolarek at p.lodz.pl>
DW: ghc-devs at haskell.org
Wys?ane: czwartek, 11 lipiec 2013 17:52:49
Temat: Re: Some more questions about Cmm pipeline



1. Was a quick hack that I did sometime in the past, it probably didn't work fully. Nowadays LLVM does loopification, so its not clear whether there's any benefit to doing it in cmm (but maybe there's some other payoff that we can get by doing it earlier).

2. Is Edward Yang's optimisation pass. Disabled because it is crazy expensive; I wrote CmmSink instead which does most of the same things and a few more. We should remove the code now that we're not going to use it.
On 11 Jul 2013 11:37, "Jan Stolarek" < jan.stolarek at p.lodz.pl > wrote:


Hi Simon,

I have two questions about the Cmm pipeline:

1. I implemented a pass that replaces tail calls with a copy of the entry block we're calling to. This is slightly extended version of loopification which will hopefully enable further optimisations. Then I noticed that loopification pass used to be implemented (cmm/CmmOpt.hs, line 418) but was commented out (d92bd17ffd8715f77fd49de0fed6e39c8d0ec28b). There's also a comment: "XXX: revisit if we actually want to do this". What was the motivation for removing loopification? Is there a reason why we might not want to do it?

2. There is a module cmm/CmmRewriteAssignments.hs, which is not used at the moment. What was the motivation for disabling that pass?

Janek


Reply | Threaded
Open this post in threaded view
|

Some more questions about Cmm pipeline

Simon Peyton Jones
It looks to me that CmmLive.removeDeadAssignments does indeed do dead code elimination.  It's best to do it in one Hoopl pass: compute liveness and eliminate dead code.

However, we want to eliminate dead assignments to stack locations too, so the liveness info need to be augmented with stack areas.

Simon

| -----Original Message-----
| From: ghc-devs-bounces at haskell.org [mailto:ghc-devs-bounces at haskell.org]
| On Behalf Of Jan Stolarek
| Sent: 12 July 2013 09:20
| To: Simon Marlow
| Cc: ghc-devs at haskell.org
| Subject: Re: Some more questions about Cmm pipeline
|
| I have two more questions:
|
| 3. I will be doing copy propagation within a procedure graph, after
| which I will need to run dead code elimination. My understanding of
| CmmLive is that it computes liveness analysis at the entry to each basic
| block, which implies I will not be able to use information generated by
| CmmLive for dead code elimination within a block. Is that correct?
|
| 4. Speaking of unused code, there is a disabled CmmSink pass just before
| stack layout is done. Can I remove that commented fragment or are there
| plans to re-enable this pass at some point in the future?
|
| Janek
|
| ----- Oryginalna wiadomo?? -----
| Od: "Simon Marlow" <marlowsd at gmail.com>
| Do: "Jan Stolarek" <jan.stolarek at p.lodz.pl>
| DW: ghc-devs at haskell.org
| Wys?ane: czwartek, 11 lipiec 2013 17:52:49
| Temat: Re: Some more questions about Cmm pipeline
|
|
|
| 1. Was a quick hack that I did sometime in the past, it probably didn't
| work fully. Nowadays LLVM does loopification, so its not clear whether
| there's any benefit to doing it in cmm (but maybe there's some other
| payoff that we can get by doing it earlier).
|
| 2. Is Edward Yang's optimisation pass. Disabled because it is crazy
| expensive; I wrote CmmSink instead which does most of the same things
| and a few more. We should remove the code now that we're not going to
| use it.
| On 11 Jul 2013 11:37, "Jan Stolarek" < jan.stolarek at p.lodz.pl > wrote:
|
|
| Hi Simon,
|
| I have two questions about the Cmm pipeline:
|
| 1. I implemented a pass that replaces tail calls with a copy of the
| entry block we're calling to. This is slightly extended version of
| loopification which will hopefully enable further optimisations. Then I
| noticed that loopification pass used to be implemented (cmm/CmmOpt.hs,
| line 418) but was commented out
| (d92bd17ffd8715f77fd49de0fed6e39c8d0ec28b). There's also a comment:
| "XXX: revisit if we actually want to do this". What was the motivation
| for removing loopification? Is there a reason why we might not want to
| do it?
|
| 2. There is a module cmm/CmmRewriteAssignments.hs, which is not used at
| the moment. What was the motivation for disabling that pass?
|
| Janek
|
| _______________________________________________
| ghc-devs mailing list
| ghc-devs at haskell.org
| http://www.haskell.org/mailman/listinfo/ghc-devs

Reply | Threaded
Open this post in threaded view
|

Some more questions about Cmm pipeline

Simon Marlow-7
CmmSink removes dead assignments (though not in loops), which is why
it's commented out.  A single removeDeadAssigments pass costs about 5%
of compilation time, and in the vast majority of code does nothing over
what CmmSink already does.

The CmmSink pass before stack layout is disabled because I never got
around to measuring it to determine whether it is a good idea or not.
By all means do that!  It *ought* to work, but the Cmm before stack
layout looks a lot different compared with the Cmm after stack layout,
so you might encounter cases that we haven't had to deal with in CmmSink
yet.  If this pass is useful at all, it should probably only be in -O2.

I'd like to make two suggestions:

1. PLEASE make sure that you're carefully measuring compilation time
when making changes to the code generator.  Expensive optimisations need
to go in -O2 (at least).  The current bag of -O optimisations is a
carefully balanced tradeoff between compilation time and code quality.
We get all the low-hanging fruit that we can get cheaply, and try to do
as much in each pass as possible.  CmmSink is a bag of
cheap-but-important optimisations, determined by peering at lots of Cmm
code looking for stupid stuff.

2. I suggest driving the whole thing by finding examples that are being
compiled obviously badly.  It's very easy to guess wrong about what
optimisations are important (trust me, I've made this mistake many
times!).  Furthermore, think carefully about how much effort you want to
put into Cmm optimisation against what we can already get for free with
-fllvm.

I've no doubt there's scope here, but let's start with some motivating
examples first.

Cheers,
        Simon


On 12/07/13 09:32, Simon Peyton-Jones wrote:

> It looks to me that CmmLive.removeDeadAssignments does indeed do dead code elimination.  It's best to do it in one Hoopl pass: compute liveness and eliminate dead code.
>
> However, we want to eliminate dead assignments to stack locations too, so the liveness info need to be augmented with stack areas.
>
> Simon
>
> | -----Original Message-----
> | From: ghc-devs-bounces at haskell.org [mailto:ghc-devs-bounces at haskell.org]
> | On Behalf Of Jan Stolarek
> | Sent: 12 July 2013 09:20
> | To: Simon Marlow
> | Cc: ghc-devs at haskell.org
> | Subject: Re: Some more questions about Cmm pipeline
> |
> | I have two more questions:
> |
> | 3. I will be doing copy propagation within a procedure graph, after
> | which I will need to run dead code elimination. My understanding of
> | CmmLive is that it computes liveness analysis at the entry to each basic
> | block, which implies I will not be able to use information generated by
> | CmmLive for dead code elimination within a block. Is that correct?
> |
> | 4. Speaking of unused code, there is a disabled CmmSink pass just before
> | stack layout is done. Can I remove that commented fragment or are there
> | plans to re-enable this pass at some point in the future?
> |
> | Janek
> |
> | ----- Oryginalna wiadomo?? -----
> | Od: "Simon Marlow" <marlowsd at gmail.com>
> | Do: "Jan Stolarek" <jan.stolarek at p.lodz.pl>
> | DW: ghc-devs at haskell.org
> | Wys?ane: czwartek, 11 lipiec 2013 17:52:49
> | Temat: Re: Some more questions about Cmm pipeline
> |
> |
> |
> | 1. Was a quick hack that I did sometime in the past, it probably didn't
> | work fully. Nowadays LLVM does loopification, so its not clear whether
> | there's any benefit to doing it in cmm (but maybe there's some other
> | payoff that we can get by doing it earlier).
> |
> | 2. Is Edward Yang's optimisation pass. Disabled because it is crazy
> | expensive; I wrote CmmSink instead which does most of the same things
> | and a few more. We should remove the code now that we're not going to
> | use it.
> | On 11 Jul 2013 11:37, "Jan Stolarek" < jan.stolarek at p.lodz.pl > wrote:
> |
> |
> | Hi Simon,
> |
> | I have two questions about the Cmm pipeline:
> |
> | 1. I implemented a pass that replaces tail calls with a copy of the
> | entry block we're calling to. This is slightly extended version of
> | loopification which will hopefully enable further optimisations. Then I
> | noticed that loopification pass used to be implemented (cmm/CmmOpt.hs,
> | line 418) but was commented out
> | (d92bd17ffd8715f77fd49de0fed6e39c8d0ec28b). There's also a comment:
> | "XXX: revisit if we actually want to do this". What was the motivation
> | for removing loopification? Is there a reason why we might not want to
> | do it?
> |
> | 2. There is a module cmm/CmmRewriteAssignments.hs, which is not used at
> | the moment. What was the motivation for disabling that pass?
> |
> | Janek
> |
> | _______________________________________________
> | ghc-devs mailing list
> | ghc-devs at haskell.org
> | http://www.haskell.org/mailman/listinfo/ghc-devs
>



Reply | Threaded
Open this post in threaded view
|

Some more questions about Cmm pipeline

Jan Stolarek
Thank you for detailed response.

> 1. PLEASE make sure that you're carefully measuring compilation time
> when making changes to the code generator.
Noted.

> Furthermore, think carefully about how much effort you want to
> put into Cmm optimisation against what we can already get for free with
> -fllvm.
I think the ultimate goal is to modify Cmm generation in order to enable more LLVM optimisations.

Janek