presentation: Next-gen Haskell Compilation Techniques - ghc-devs - Haskell.org

newer
Large Haddock submodule merge...

presentation: Next-gen Haskell Compilation Techniques

older
How to get dwarf stack trace of...

Csaba Hruska

9 Jan 2021 9 Jan '21

6:30 p.m.

Hello, I did an online presentation about Haskell related (futuristic) compilation techniques. The application of these methods is also the main motivation of my work with the grin compiler project and ghc-wpc. video: https://www.youtube.com/watch?v=jyaR8E325ok slides: https://docs.google.com/presentation/d/1g_-bHgeD7lV4AYybnvjgkWa9GKuP6QFUyd26... Regards, Csaba

Attachments:

attachment.html (text/html — 685 bytes)

Reply

Sign in to reply online Use email software

Show replies by date

Sebastian Graf

10 Jan 10 Jan

7:58 a.m.

Hi Csaba, Thanks for your presentation, that's a nice high-level overview of what you're up to. A few thoughts: - Whole-program optimization sounds great, but also very ambitious, given the amount of code GHC generates today. I'd be amazed to see advances in that area, though, and your >100-module CFA performance incites hope! - I wonder if going through GRIN results in a more efficient mapping to hardware. I recently found that the code GHC generates is dominated by administrative traffic from and to the heap [1]. I suspect that you can have big wins here if you manage to convey better call stack, heap and alias information to LLVM. - The Control Analysis+specialisation approach sounds pretty similar to doing Constructor Specialisation [2] for Lambdas (cf. 6.2) if you also inline the function for which you specialise afterwards. I sunk many hours into making that work reliably, fast and without code bloat in the past, to no avail. Frankly, if you can do it in GRIN, I don't see why we couldn't do it in Core. But maybe we can learn from the GRIN implementation afterwards and maybe rethink SpecConstr. Maybe the key is not to inline the function for which we specialise? But then you don't gain that much... - I follow the Counting Immutable Beans [3] stuff quite closely (Sebastian is a colleague of mine) and hope that it is applicable to Haskell some day. But I think using Perceus, like any purely RC-based memory management scheme, means that you can't have cycles in your heap, so no loopy thunks (such as constant-space `ones = 1:ones`) and mutability. I think that makes a pretty huge difference for many use cases. Sebastian also told me that they have to adapt their solutions to the cycle restriction from time to time, so far always successfully. But it comes at a cost: You have to adapt the code you want to write into a form that works. I only read the slides, apologies if some of my points were invalidated by something you said. Keep up the good work! Cheers, Sebastian [1] https://gitlab.haskell.org/ghc/ghc/-/issues/19113 [2] https://www.microsoft.com/en-us/research/wp-content/uploads/2016/07/spec-con... [3] https://arxiv.org/abs/1908.05647 Am So., 10. Jan. 2021 um 00:31 Uhr schrieb Csaba Hruska < csaba.hruska@gmail.com>:

Hello, I did an online presentation about Haskell related (futuristic) compilation techniques. The application of these methods is also the main motivation of my work with the grin compiler project and ghc-wpc.

video: https://www.youtube.com/watch?v=jyaR8E325ok slides: https://docs.google.com/presentation/d/1g_-bHgeD7lV4AYybnvjgkWa9GKuP6QFUyd26...

Regards, Csaba _______________________________________________ ghc-devs mailing list ghc-devs@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs

Reply

Sign in to reply online Use email software

Csaba Hruska

11 Jan 11 Jan

7:18 a.m.

Hi Sebastian, Thanks for your feedback. I know that CIB and Perceus have issues with cycles, but these systems are still in development so who knows what will be the conclusion. I may not emphasize in the talk, but the goal of the grin compiler project is to build a compiler pipeline that allows easy experimentation of different compilation techniques. Anything between whole program compilation to per module incremental codegen. So the whole program compilation is not really a requirement but an option. Cheers, Csaba On Sun, Jan 10, 2021 at 1:58 PM Sebastian Graf wrote:

Hi Csaba,

Thanks for your presentation, that's a nice high-level overview of what you're up to.

A few thoughts:

- Whole-program optimization sounds great, but also very ambitious, given the amount of code GHC generates today. I'd be amazed to see advances in that area, though, and your >100-module CFA performance incites hope! - I wonder if going through GRIN results in a more efficient mapping to hardware. I recently found that the code GHC generates is dominated by administrative traffic from and to the heap [1]. I suspect that you can have big wins here if you manage to convey better call stack, heap and alias information to LLVM. - The Control Analysis+specialisation approach sounds pretty similar to doing Constructor Specialisation [2] for Lambdas (cf. 6.2) if you also inline the function for which you specialise afterwards. I sunk many hours into making that work reliably, fast and without code bloat in the past, to no avail. Frankly, if you can do it in GRIN, I don't see why we couldn't do it in Core. But maybe we can learn from the GRIN implementation afterwards and maybe rethink SpecConstr. Maybe the key is not to inline the function for which we specialise? But then you don't gain that much... - I follow the Counting Immutable Beans [3] stuff quite closely (Sebastian is a colleague of mine) and hope that it is applicable to Haskell some day. But I think using Perceus, like any purely RC-based memory management scheme, means that you can't have cycles in your heap, so no loopy thunks (such as constant-space `ones = 1:ones`) and mutability. I think that makes a pretty huge difference for many use cases. Sebastian also told me that they have to adapt their solutions to the cycle restriction from time to time, so far always successfully. But it comes at a cost: You have to adapt the code you want to write into a form that works.

I only read the slides, apologies if some of my points were invalidated by something you said.

Keep up the good work! Cheers, Sebastian

[1] https://gitlab.haskell.org/ghc/ghc/-/issues/19113 [2] https://www.microsoft.com/en-us/research/wp-content/uploads/2016/07/spec-con... [3] https://arxiv.org/abs/1908.05647

Am So., 10. Jan. 2021 um 00:31 Uhr schrieb Csaba Hruska < csaba.hruska@gmail.com>:

...
Hello, I did an online presentation about Haskell related (futuristic) compilation techniques. The application of these methods is also the main motivation of my work with the grin compiler project and ghc-wpc.

video: https://www.youtube.com/watch?v=jyaR8E325ok slides: https://docs.google.com/presentation/d/1g_-bHgeD7lV4AYybnvjgkWa9GKuP6QFUyd26...

Regards, Csaba _______________________________________________ ghc-devs mailing list ghc-devs@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs

Reply

Sign in to reply online Use email software

Simon Peyton Jones

7:51 a.m.

I may not emphasize in the talk, but the goal of the grin compiler project is to build a compiler pipeline that allows easy experimentation of different compilation techniques. Anything between whole program compilation to per module incremental codegen. So the whole program compilation is not really a requirement but an option. Right - but some optimisations absolutely require whole-program analysis, don't they? I'm thinking of flow analyses that support defunctionalisation, when you must know all the lambdas that could be bound to `f` in the definition of `map` for example. Such optimisations are powerful, but brittle because they are simply inapplicable without whole-program analysis. Or maybe you can find ways to make them more resilient. Simon From: ghc-devs On Behalf Of Csaba Hruska Sent: 11 January 2021 12:19 To: Sebastian Graf Cc: GHC developers Subject: Re: presentation: Next-gen Haskell Compilation Techniques Hi Sebastian, Thanks for your feedback. I know that CIB and Perceus have issues with cycles, but these systems are still in development so who knows what will be the conclusion. I may not emphasize in the talk, but the goal of the grin compiler project is to build a compiler pipeline that allows easy experimentation of different compilation techniques. Anything between whole program compilation to per module incremental codegen. So the whole program compilation is not really a requirement but an option. Cheers, Csaba On Sun, Jan 10, 2021 at 1:58 PM Sebastian Graf mailto:sgraf1337@gmail.com> wrote: Hi Csaba, Thanks for your presentation, that's a nice high-level overview of what you're up to. A few thoughts: * Whole-program optimization sounds great, but also very ambitious, given the amount of code GHC generates today. I'd be amazed to see advances in that area, though, and your >100-module CFA performance incites hope! * I wonder if going through GRIN results in a more efficient mapping to hardware. I recently found that the code GHC generates is dominated by administrative traffic from and to the heap [1]. I suspect that you can have big wins here if you manage to convey better call stack, heap and alias information to LLVM. * The Control Analysis+specialisation approach sounds pretty similar to doing Constructor Specialisation [2] for Lambdas (cf. 6.2) if you also inline the function for which you specialise afterwards. I sunk many hours into making that work reliably, fast and without code bloat in the past, to no avail. Frankly, if you can do it in GRIN, I don't see why we couldn't do it in Core. But maybe we can learn from the GRIN implementation afterwards and maybe rethink SpecConstr. Maybe the key is not to inline the function for which we specialise? But then you don't gain that much... * I follow the Counting Immutable Beans [3] stuff quite closely (Sebastian is a colleague of mine) and hope that it is applicable to Haskell some day. But I think using Perceus, like any purely RC-based memory management scheme, means that you can't have cycles in your heap, so no loopy thunks (such as constant-space `ones = 1:ones`) and mutability. I think that makes a pretty huge difference for many use cases. Sebastian also told me that they have to adapt their solutions to the cycle restriction from time to time, so far always successfully. But it comes at a cost: You have to adapt the code you want to write into a form that works. I only read the slides, apologies if some of my points were invalidated by something you said. Keep up the good work! Cheers, Sebastian [1] https://gitlab.haskell.org/ghc/ghc/-/issues/19113 https://nam06.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgitlab.haskell.org%2Fghc%2Fghc%2F-%2Fissues%2F19113&data=04%7C01%7Csimonpj%40microsoft.com%7C0a889669aa404e4b938008d8b62b23f0%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C637459644503167010%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sdata=0W9ejmKCDKpuBT0mEArvIwAmHDUS4QI9kc5j%2BhGUX5I%3D&reserved=0 [2] https://www.microsoft.com/en-us/research/wp-content/uploads/2016/07/spec-con...https://nam06.safelinks.protection.outlook.com/?url=https%3A%2F%2Fwww.microsoft.com%2Fen-us%2Fresearch%2Fwp-content%2Fuploads%2F2016%2F07%2Fspec-constr.pdf&data=04%7C01%7Csimonpj%40microsoft.com%7C0a889669aa404e4b938008d8b62b23f0%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C637459644503177005%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sdata=8wJJXOpNuaQpjOWBTwbQ0upeOj1LLXSUD86cn8TbKI8%3D&reserved=0 [3] https://arxiv.org/abs/1908.05647 https://nam06.safelinks.protection.outlook.com/?url=https%3A%2F%2Farxiv.org%2Fabs%2F1908.05647&data=04%7C01%7Csimonpj%40microsoft.com%7C0a889669aa404e4b938008d8b62b23f0%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C637459644503186998%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sdata=LCFO8R5SZT0KveoB9GyPcMpwbhU9DTLOnYhxD%2FZNXxU%3D&reserved=0 Am So., 10. Jan. 2021 um 00:31 Uhr schrieb Csaba Hruska mailto:csaba.hruska@gmail.com>: Hello, I did an online presentation about Haskell related (futuristic) compilation techniques. The application of these methods is also the main motivation of my work with the grin compiler project and ghc-wpc. video: https://www.youtube.com/watch?v=jyaR8E325ok https://nam06.safelinks.protection.outlook.com/?url=https%3A%2F%2Fwww.youtube.com%2Fwatch%3Fv%3DjyaR8E325ok&data=04%7C01%7Csimonpj%40microsoft.com%7C0a889669aa404e4b938008d8b62b23f0%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C637459644503196994%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sdata=dbxjJKAKqZJZ2jdYE2aR6ymQIp9awCmOHwsBAHLz9AM%3D&reserved=0 slides: https://docs.google.com/presentation/d/1g_-bHgeD7lV4AYybnvjgkWa9GKuP6QFUyd26...https://nam06.safelinks.protection.outlook.com/?url=https%3A%2F%2Fdocs.google.com%2Fpresentation%2Fd%2F1g_-bHgeD7lV4AYybnvjgkWa9GKuP6QFUyd26zpqXssQ%2Fedit%3Fusp%3Dsharing&data=04%7C01%7Csimonpj%40microsoft.com%7C0a889669aa404e4b938008d8b62b23f0%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C637459644503196994%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sdata=UHHOI6Nr80zuDrFDPVUz6wsNXKlxY06%2B5tG%2BCxf847I%3D&reserved=0 Regards, Csaba _______________________________________________ ghc-devs mailing list ghc-devs@haskell.orgmailto:ghc-devs@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs https://nam06.safelinks.protection.outlook.com/?url=http%3A%2F%2Fmail.haskell.org%2Fcgi-bin%2Fmailman%2Flistinfo%2Fghc-devs&data=04%7C01%7Csimonpj%40microsoft.com%7C0a889669aa404e4b938008d8b62b23f0%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C637459644503206993%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sdata=%2BAdAJUowngbDQt7BMX43JegOeUNMfh%2B00VYYBVyTPN0%3D&reserved=0

Reply

Sign in to reply online Use email software

Csaba Hruska

8:17 a.m.

Sure, some require whole-program analysis. But I really do not worry about it, because what I'd like to build is an engineering vehicle. Where a single optimization idea could be built in several ways with different tradeoffs. Then the sweet spot could be found after an in depth investigation of the problem domain. I.e. removing all indirect calls surely require whole program defunctionalization, but a significant reduction of indirect calls could be achieved with other techniques that does not require whole program analysis. But it is totally valuable to compare the two approaches just to know the tradeoffs even if only one of them is applicable in practice. Csaba On Mon, Jan 11, 2021 at 1:51 PM Simon Peyton Jones wrote:

I may not emphasize in the talk, but the goal of the grin compiler project is to build a compiler pipeline that allows easy experimentation of different compilation techniques. Anything between whole program compilation to per module incremental codegen. So the whole program compilation is not really a requirement but an option.

Right – but *some* optimisations absolutely require whole-program analysis, don’t they? I’m thinking of flow analyses that support defunctionalisation, when you must know all the lambdas that could be bound to `f` in the definition of `map` for example.

Such optimisations are powerful, but brittle because they are simply inapplicable without whole-program analysis. Or maybe you can find ways to make them more resilient.

Simon

*From:* ghc-devs *On Behalf Of *Csaba Hruska *Sent:* 11 January 2021 12:19 *To:* Sebastian Graf *Cc:* GHC developers *Subject:* Re: presentation: Next-gen Haskell Compilation Techniques

Hi Sebastian,

Thanks for your feedback.

I know that CIB and Perceus have issues with cycles, but these systems are still in development so who knows what will be the conclusion.

I may not emphasize in the talk, but the goal of the grin compiler project is to build a compiler pipeline that allows easy experimentation of different compilation techniques. Anything between whole program compilation to per module incremental codegen. So the whole program compilation is not really a requirement but an option.

Cheers,

Csaba

On Sun, Jan 10, 2021 at 1:58 PM Sebastian Graf wrote:

Hi Csaba,

Thanks for your presentation, that's a nice high-level overview of what you're up to.

A few thoughts:

- Whole-program optimization sounds great, but also very ambitious, given the amount of code GHC generates today. I'd be amazed to see advances in that area, though, and your >100-module CFA performance incites hope! - I wonder if going through GRIN results in a more efficient mapping to hardware. I recently found that the code GHC generates is dominated by administrative traffic from and to the heap [1]. I suspect that you can have big wins here if you manage to convey better call stack, heap and alias information to LLVM. - The Control Analysis+specialisation approach sounds pretty similar to doing Constructor Specialisation [2] for Lambdas (cf. 6.2) if you also inline the function for which you specialise afterwards. I sunk many hours into making that work reliably, fast and without code bloat in the past, to no avail. Frankly, if you can do it in GRIN, I don't see why we couldn't do it in Core. But maybe we can learn from the GRIN implementation afterwards and maybe rethink SpecConstr. Maybe the key is not to inline the function for which we specialise? But then you don't gain that much... - I follow the Counting Immutable Beans [3] stuff quite closely (Sebastian is a colleague of mine) and hope that it is applicable to Haskell some day. But I think using Perceus, like any purely RC-based memory management scheme, means that you can't have cycles in your heap, so no loopy thunks (such as constant-space `ones = 1:ones`) and mutability. I think that makes a pretty huge difference for many use cases. Sebastian also told me that they have to adapt their solutions to the cycle restriction from time to time, so far always successfully. But it comes at a cost: You have to adapt the code you want to write into a form that works.

I only read the slides, apologies if some of my points were invalidated by something you said.

Keep up the good work!

Cheers,

Sebastian

[1] https://gitlab.haskell.org/ghc/ghc/-/issues/19113 https://nam06.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgitlab.haskell.org%2Fghc%2Fghc%2F-%2Fissues%2F19113&data=04%7C01%7Csimonpj%40microsoft.com%7C0a889669aa404e4b938008d8b62b23f0%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C637459644503167010%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sdata=0W9ejmKCDKpuBT0mEArvIwAmHDUS4QI9kc5j%2BhGUX5I%3D&reserved=0

[2] https://www.microsoft.com/en-us/research/wp-content/uploads/2016/07/spec-con... https://nam06.safelinks.protection.outlook.com/?url=https%3A%2F%2Fwww.microsoft.com%2Fen-us%2Fresearch%2Fwp-content%2Fuploads%2F2016%2F07%2Fspec-constr.pdf&data=04%7C01%7Csimonpj%40microsoft.com%7C0a889669aa404e4b938008d8b62b23f0%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C637459644503177005%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sdata=8wJJXOpNuaQpjOWBTwbQ0upeOj1LLXSUD86cn8TbKI8%3D&reserved=0

[3] https://arxiv.org/abs/1908.05647 https://nam06.safelinks.protection.outlook.com/?url=https%3A%2F%2Farxiv.org%2Fabs%2F1908.05647&data=04%7C01%7Csimonpj%40microsoft.com%7C0a889669aa404e4b938008d8b62b23f0%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C637459644503186998%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sdata=LCFO8R5SZT0KveoB9GyPcMpwbhU9DTLOnYhxD%2FZNXxU%3D&reserved=0

Am So., 10. Jan. 2021 um 00:31 Uhr schrieb Csaba Hruska < csaba.hruska@gmail.com>:

Hello,

I did an online presentation about Haskell related (futuristic) compilation techniques.

The application of these methods is also the main motivation of my work with the grin compiler project and ghc-wpc.

video: https://www.youtube.com/watch?v=jyaR8E325ok https://nam06.safelinks.protection.outlook.com/?url=https%3A%2F%2Fwww.youtube.com%2Fwatch%3Fv%3DjyaR8E325ok&data=04%7C01%7Csimonpj%40microsoft.com%7C0a889669aa404e4b938008d8b62b23f0%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C637459644503196994%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sdata=dbxjJKAKqZJZ2jdYE2aR6ymQIp9awCmOHwsBAHLz9AM%3D&reserved=0

slides: https://docs.google.com/presentation/d/1g_-bHgeD7lV4AYybnvjgkWa9GKuP6QFUyd26... https://nam06.safelinks.protection.outlook.com/?url=https%3A%2F%2Fdocs.google.com%2Fpresentation%2Fd%2F1g_-bHgeD7lV4AYybnvjgkWa9GKuP6QFUyd26zpqXssQ%2Fedit%3Fusp%3Dsharing&data=04%7C01%7Csimonpj%40microsoft.com%7C0a889669aa404e4b938008d8b62b23f0%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C637459644503196994%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sdata=UHHOI6Nr80zuDrFDPVUz6wsNXKlxY06%2B5tG%2BCxf847I%3D&reserved=0

Regards,

Csaba

_______________________________________________ ghc-devs mailing list ghc-devs@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs https://nam06.safelinks.protection.outlook.com/?url=http%3A%2F%2Fmail.haskell.org%2Fcgi-bin%2Fmailman%2Flistinfo%2Fghc-devs&data=04%7C01%7Csimonpj%40microsoft.com%7C0a889669aa404e4b938008d8b62b23f0%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C637459644503206993%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sdata=%2BAdAJUowngbDQt7BMX43JegOeUNMfh%2B00VYYBVyTPN0%3D&reserved=0

Reply

Sign in to reply online Use email software

John Ericson

9:09 a.m.

Great presentation, Csaba! I definitely strongly agree in broad terms that these are the overlooked big questions we should be asking. On the is last point, not only can we find a middle ground we like best, we can also do the full spectrum. I know something that many people I've talked to would like is a "compilation server" of sorts that just keeps on optimizing, building up a bigger database of knowledge of spitting out better binaries the longer you keep it running. If I understand correctly, a datalog-based method with very good properties re incrementality and monotonicity should be the perfect architecture for this. Cheers, John On 1/11/21 8:17 AM, Csaba Hruska wrote:

Sure, some require whole-program analysis. But I really do not worry about it, because what I'd like to build is an engineering vehicle. Where a single optimization idea could be built in several ways with different tradeoffs. Then the sweet spot could be found after an in depth investigation of the problem domain. I.e. removing all indirect calls surely require whole program defunctionalization, but a significant reduction of indirect calls could be achieved with other techniques that does not require whole program analysis. But it is totally valuable to compare the two approaches just to know the tradeoffs even if only one of them is applicable in practice.

Csaba

On Mon, Jan 11, 2021 at 1:51 PM Simon Peyton Jones mailto:simonpj@microsoft.com> wrote:

I may not emphasize in the talk, but the goal of the grin compiler project is to build a compiler pipeline that allows easy experimentation of different compilation techniques. Anything between whole program compilation to per module incremental codegen. So the whole program compilation is not really a requirement but an option.

Right – but /some/ optimisations absolutely require whole-program analysis, don’t they? I’m thinking of flow analyses that support defunctionalisation, when you must know all the lambdas that could be bound to `f` in the definition of `map` for example.

Such optimisations are powerful, but brittle because they are simply inapplicable without whole-program analysis. Or maybe you can find ways to make them more resilient.

Simon

*From:*ghc-devs mailto:ghc-devs-bounces@haskell.org> *On Behalf Of *Csaba Hruska *Sent:* 11 January 2021 12:19 *To:* Sebastian Graf mailto:sgraf1337@gmail.com> *Cc:* GHC developers mailto:ghc-devs@haskell.org> *Subject:* Re: presentation: Next-gen Haskell Compilation Techniques

Hi Sebastian,

Thanks for your feedback.

I know that CIB and Perceus have issues with cycles, but these systems are still in development so who knows what will be the conclusion.

I may not emphasize in the talk, but the goal of the grin compiler project is to build a compiler pipeline that allows easy experimentation of different compilation techniques. Anything between whole program compilation to per module incremental codegen. So the whole program compilation is not really a requirement but an option.

Cheers,

Csaba

On Sun, Jan 10, 2021 at 1:58 PM Sebastian Graf mailto:sgraf1337@gmail.com> wrote:

Hi Csaba,

Thanks for your presentation, that's a nice high-level overview of what you're up to.

A few thoughts:

* Whole-program optimization sounds great, but also very ambitious, given the amount of code GHC generates today. I'd be amazed to see advances in that area, though, and your >100-module CFA performance incites hope! * I wonder if going through GRIN results in a more efficient mapping to hardware. I recently found that the code GHC generates is dominated by administrative traffic from and to the heap [1]. I suspect that you can have big wins here if you manage to convey better call stack, heap and alias information to LLVM. * The Control Analysis+specialisation approach sounds pretty similar to doing Constructor Specialisation [2] for Lambdas (cf. 6.2) if you also inline the function for which you specialise afterwards. I sunk many hours into making that work reliably, fast and without code bloat in the past, to no avail. Frankly, if you can do it in GRIN, I don't see why we couldn't do it in Core. But maybe we can learn from the GRIN implementation afterwards and maybe rethink SpecConstr. Maybe the key is not to inline the function for which we specialise? But then you don't gain that much... * I follow the Counting Immutable Beans [3] stuff quite closely (Sebastian is a colleague of mine) and hope that it is applicable to Haskell some day. But I think using Perceus, like any purely RC-based memory management scheme, means that you can't have cycles in your heap, so no loopy thunks (such as constant-space `ones = 1:ones`) and mutability. I think that makes a pretty huge difference for many use cases. Sebastian also told me that they have to adapt their solutions to the cycle restriction from time to time, so far always successfully. But it comes at a cost: You have to adapt the code you want to write into a form that works.

I only read the slides, apologies if some of my points were invalidated by something you said.

Keep up the good work!

Cheers,

Sebastian

[1] https://gitlab.haskell.org/ghc/ghc/-/issues/19113 https://nam06.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgitlab.haskell.org%2Fghc%2Fghc%2F-%2Fissues%2F19113&data=04%7C01%7Csimonpj%40microsoft.com%7C0a889669aa404e4b938008d8b62b23f0%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C637459644503167010%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sdata=0W9ejmKCDKpuBT0mEArvIwAmHDUS4QI9kc5j%2BhGUX5I%3D&reserved=0

[2] https://www.microsoft.com/en-us/research/wp-content/uploads/2016/07/spec-con... https://nam06.safelinks.protection.outlook.com/?url=https%3A%2F%2Fwww.microsoft.com%2Fen-us%2Fresearch%2Fwp-content%2Fuploads%2F2016%2F07%2Fspec-constr.pdf&data=04%7C01%7Csimonpj%40microsoft.com%7C0a889669aa404e4b938008d8b62b23f0%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C637459644503177005%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sdata=8wJJXOpNuaQpjOWBTwbQ0upeOj1LLXSUD86cn8TbKI8%3D&reserved=0

[3] https://arxiv.org/abs/1908.05647 https://nam06.safelinks.protection.outlook.com/?url=https%3A%2F%2Farxiv.org%2Fabs%2F1908.05647&data=04%7C01%7Csimonpj%40microsoft.com%7C0a889669aa404e4b938008d8b62b23f0%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C637459644503186998%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sdata=LCFO8R5SZT0KveoB9GyPcMpwbhU9DTLOnYhxD%2FZNXxU%3D&reserved=0

Am So., 10. Jan. 2021 um 00:31 Uhr schrieb Csaba Hruska mailto:csaba.hruska@gmail.com>:

Hello,

I did an online presentation about Haskell related (futuristic) compilation techniques.

The application of these methods is also the main motivation of my work with the grin compiler project and ghc-wpc.

video: https://www.youtube.com/watch?v=jyaR8E325ok https://nam06.safelinks.protection.outlook.com/?url=https%3A%2F%2Fwww.youtube.com%2Fwatch%3Fv%3DjyaR8E325ok&data=04%7C01%7Csimonpj%40microsoft.com%7C0a889669aa404e4b938008d8b62b23f0%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C637459644503196994%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sdata=dbxjJKAKqZJZ2jdYE2aR6ymQIp9awCmOHwsBAHLz9AM%3D&reserved=0

slides: https://docs.google.com/presentation/d/1g_-bHgeD7lV4AYybnvjgkWa9GKuP6QFUyd26... https://nam06.safelinks.protection.outlook.com/?url=https%3A%2F%2Fdocs.google.com%2Fpresentation%2Fd%2F1g_-bHgeD7lV4AYybnvjgkWa9GKuP6QFUyd26zpqXssQ%2Fedit%3Fusp%3Dsharing&data=04%7C01%7Csimonpj%40microsoft.com%7C0a889669aa404e4b938008d8b62b23f0%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C637459644503196994%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sdata=UHHOI6Nr80zuDrFDPVUz6wsNXKlxY06%2B5tG%2BCxf847I%3D&reserved=0

Regards,

Csaba

_______________________________________________ ghc-devs mailing list ghc-devs@haskell.org mailto:ghc-devs@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs https://nam06.safelinks.protection.outlook.com/?url=http%3A%2F%2Fmail.haskell.org%2Fcgi-bin%2Fmailman%2Flistinfo%2Fghc-devs&data=04%7C01%7Csimonpj%40microsoft.com%7C0a889669aa404e4b938008d8b62b23f0%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C637459644503206993%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sdata=%2BAdAJUowngbDQt7BMX43JegOeUNMfh%2B00VYYBVyTPN0%3D&reserved=0

_______________________________________________ ghc-devs mailing list ghc-devs@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs

Reply

Sign in to reply online Use email software

1592

Age (days ago)

1594

Last active (days ago)

Download

5 comments

4 participants

tags

participants (4)

Csaba Hruska
John Ericson
Sebastian Graf
Simon Peyton Jones