new llvm IR callbr instruction useful for proc-point splitting?

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

new llvm IR callbr instruction useful for proc-point splitting?

George Colpitts
Hi

I hope this question isn't too dumb. llvm has a new callbr instruction to implement asm-goto

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

Re: new llvm IR callbr instruction useful for proc-point splitting?

Kavon Farvardin
Yes, callbr is part of the discussion on removing proc-point splitting! 

Soon there will be an announcement about a new working group dedicated to LLVM issues such as this one on this mailing list. Anyone interested is welcome to join our meetings.

We're currently gathering our notes together first, but you can have a look here for a preview: https://gitlab.haskell.org/ghc/ghc/wikis/commentary/compiler/LLVM-Backend-Optimization


On Sun, 2019-06-23 at 12:00 -0300, George Colpitts wrote:
Hi

I hope this question isn't too dumb. llvm has a new callbr instruction to implement asm-goto
_______________________________________________
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

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

Re: new llvm IR callbr instruction useful for proc-point splitting?

Ben Gamari-2
Kavon Farvardin <[hidden email]> writes:

> Yes, callbr is part of the discussion on removing proc-point splitting!
> Soon there will be an announcement about a new working group dedicated to LLVM
> issues such as this one on this mailing list. Anyone interested is welcome to
> join our meetings.
> We're currently gathering our notes together first, but you can have a look here
> for a preview:
> https://gitlab.haskell.org/ghc/ghc/wikis/commentary/compiler/LLVM-Backend-Optimization

I, for one, would love to see us try using the native stack register for
reasons entirely separate from performance. Namely, it would make using
existing debugging and performance analysis tools (e.g. perf) much
easier.

I believe that Andreas Klebinger has also suggested moving return point
info tables away from code. It would be interesting to get an estimate
of the size of this effect on performance.

Cheers,

- Ben


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

signature.asc (497 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: new llvm IR callbr instruction useful for proc-point splitting?

Ben Gamari-2
In reply to this post by Kavon Farvardin
Kavon Farvardin <[hidden email]> writes:

> Yes, callbr is part of the discussion on removing proc-point splitting!
> Soon there will be an announcement about a new working group dedicated to LLVM
> issues such as this one on this mailing list. Anyone interested is welcome to
> join our meetings.
> We're currently gathering our notes together first, but you can have a look here
> for a preview:
> https://gitlab.haskell.org/ghc/ghc/wikis/commentary/compiler/LLVM-Backend-Optimization

Hi Kavon,

What ever happened to this? It came up during the GHC call and we
realized that none of us knew what the state of the proposal was. Is
this Wiki page still reflective of the current state of play?

Cheers,

- Ben


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

signature.asc (497 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: new llvm IR callbr instruction useful for proc-point splitting?

Kavon Farvardin
Hi Ben,

The Wiki now has a link to the Google Doc that Michal and I were working on to compile all of the notes into one place.

The key progress made on this front has been in evaluating the trade-offs of the design space being considered by GHC, but tested within Manticore.

I'm drafting a message today for the LLVM mailing list regarding one of our first options: defining a GHC ABI to redefine which stack-pointer register is used. 

Once we have additional answers to the question "how much effort is it to add a GHC ABI to LLVM?", we can then then start a discussion on whether GHC wants to change instead by moving to a native stack-pointer register (to take advantage of existing debugging and profiling tools, etc).

Ideally, we would then make a decision on which option to take and someone (perhaps a GSoC student with mentorship from myself and others) with spare time can work on it.

Cheers,
Kavon

On Wed, 2019-12-04 at 11:38 -0500, Ben Gamari wrote:
Kavon Farvardin <[hidden email]> writes:

Yes, callbr is part of the discussion on removing proc-point splitting! 
Soon there will be an announcement about a new working group dedicated to LLVM
issues such as this one on this mailing list. Anyone interested is welcome to
join our meetings.
We're currently gathering our notes together first, but you can have a look here
for a preview: 
https://gitlab.haskell.org/ghc/ghc/wikis/commentary/compiler/LLVM-Backend-Optimization

Hi Kavon,

What ever happened to this? It came up during the GHC call and we
realized that none of us knew what the state of the proposal was. Is
this Wiki page still reflective of the current state of play?

Cheers,

- Ben



_______________________________________________
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
|

RE: new llvm IR callbr instruction useful for proc-point splitting?

GHC - devs mailing list

Thanks Kavon.

 

What news of CpsCall in LLVM?  That seems crucial.

 

I didn’t know of an effort to use a different SP register.  I seriously doubt that, with GHC’s use of zillions of small, heap-allocated stacks that move around during GHC, we’ll be able to leverage profiling or debugging tools in a serious way. But perhaps I need education.

 

Simon

 

From: ghc-devs <[hidden email]> On Behalf Of Kavon Farvardin
Sent: 04 December 2019 19:32
To: Ben Gamari <[hidden email]>
Cc: GHC developers <[hidden email]>
Subject: Re: new llvm IR callbr instruction useful for proc-point splitting?

 

Hi Ben,

 

The Wiki now has a link to the Google Doc that Michal and I were working on to compile all of the notes into one place.

 

The key progress made on this front has been in evaluating the trade-offs of the design space being considered by GHC, but tested within Manticore.

 

I'm drafting a message today for the LLVM mailing list regarding one of our first options: defining a GHC ABI to redefine which stack-pointer register is used. 

 

Once we have additional answers to the question "how much effort is it to add a GHC ABI to LLVM?", we can then then start a discussion on whether GHC wants to change instead by moving to a native stack-pointer register (to take advantage of existing debugging and profiling tools, etc).

 

Ideally, we would then make a decision on which option to take and someone (perhaps a GSoC student with mentorship from myself and others) with spare time can work on it.

 

Cheers,

Kavon

 

On Wed, 2019-12-04 at 11:38 -0500, Ben Gamari wrote:

Kavon Farvardin <[hidden email]> writes:
 
Yes, callbr is part of the discussion on removing proc-point splitting! 
Soon there will be an announcement about a new working group dedicated to LLVM
issues such as this one on this mailing list. Anyone interested is welcome to
join our meetings.
We're currently gathering our notes together first, but you can have a look here
for a preview: 
https://gitlab.haskell.org/ghc/ghc/wikis/commentary/compiler/LLVM-Backend-Optimization
 
Hi Kavon,
 
What ever happened to this? It came up during the GHC call and we
realized that none of us knew what the state of the proposal was. Is
this Wiki page still reflective of the current state of play?
 
Cheers,
 
- Ben
 
 

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

Re: new llvm IR callbr instruction useful for proc-point splitting?

George Colpitts

Kavin is definitely the right guy to answer this but as he mentioned the Wiki now has a link to the Google Doc, i.e. https://docs.google.com/document/d/1Pn2_TDBJwSBKkjFlT-blwygH10z37TPxIqcKTOOf2mg/edit#. Simon, have you had a chance to read that?

If I understand that doc correctly the original hope of a CPS call intrinsic in LLVM has been abandoned. Excerpts from the doc:

First approach -- “CPS call” intrinsic in LLVM

...
Current ideas
...

CPS call

LLVM recently added callbr instruction that looks similar to what we need to get CPS calls to work (the instruction allows to reify the return address as a parameter to a call and specify the successor blocks where the call might jump back to).




On Wed, Dec 4, 2019 at 6:16 PM Simon Peyton Jones via ghc-devs <[hidden email]> wrote:

Thanks Kavon.

 

What news of CpsCall in LLVM?  That seems crucial.

 

I didn’t know of an effort to use a different SP register.  I seriously doubt that, with GHC’s use of zillions of small, heap-allocated stacks that move around during GHC, we’ll be able to leverage profiling or debugging tools in a serious way. But perhaps I need education.

 

Simon

 

From: ghc-devs <[hidden email]> On Behalf Of Kavon Farvardin
Sent: 04 December 2019 19:32
To: Ben Gamari <[hidden email]>
Cc: GHC developers <[hidden email]>
Subject: Re: new llvm IR callbr instruction useful for proc-point splitting?

 

Hi Ben,

 

The Wiki now has a link to the Google Doc that Michal and I were working on to compile all of the notes into one place.

 

The key progress made on this front has been in evaluating the trade-offs of the design space being considered by GHC, but tested within Manticore.

 

I'm drafting a message today for the LLVM mailing list regarding one of our first options: defining a GHC ABI to redefine which stack-pointer register is used. 

 

Once we have additional answers to the question "how much effort is it to add a GHC ABI to LLVM?", we can then then start a discussion on whether GHC wants to change instead by moving to a native stack-pointer register (to take advantage of existing debugging and profiling tools, etc).

 

Ideally, we would then make a decision on which option to take and someone (perhaps a GSoC student with mentorship from myself and others) with spare time can work on it.

 

Cheers,

Kavon

 

On Wed, 2019-12-04 at 11:38 -0500, Ben Gamari wrote:

Kavon Farvardin <[hidden email]> writes:
 
Yes, callbr is part of the discussion on removing proc-point splitting! 
Soon there will be an announcement about a new working group dedicated to LLVM
issues such as this one on this mailing list. Anyone interested is welcome to
join our meetings.
We're currently gathering our notes together first, but you can have a look here
for a preview: 
https://gitlab.haskell.org/ghc/ghc/wikis/commentary/compiler/LLVM-Backend-Optimization
 
Hi Kavon,
 
What ever happened to this? It came up during the GHC call and we
realized that none of us knew what the state of the proposal was. Is
this Wiki page still reflective of the current state of play?
 
Cheers,
 
- Ben
 
 
_______________________________________________
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
|

Re: new llvm IR callbr instruction useful for proc-point splitting?

Kavon Farvardin
In reply to this post by GHC - devs mailing list


On Wed, 2019-12-04 at 22:16 +0000, Simon Peyton Jones wrote:

Thanks Kavon.

 

What news of CpsCall in LLVM?  That seems crucial.


CPSCall is in essence equivalent to an existing construct in LLVM for GC support called "statepoints." The difference is that CPSCall expects the front-end to allocate the stack frame, whereas statepoints are hooked into LLVM's stack-allocation infrastructure.

While our usage of CPSCall is correct by construction to not require LLVM's stack-allocation, LLVM's code generator has free-reign to generate stack spills across a CPSCall for values that one can trivially rematerialize. I don't think it's sustainable to work around that already deeply-ingrained behavior (however silly it may be!), so instead the plan is to extend LLVM's statepoints to be compatible with GHC's runtime system.

How we go about doing this depends on our desires: do we want to also use the native SP register or not? Some earlier investigation revealed that even on Windows, one could use a native SP that points to a heap-allocated object, provided ~512bytes of space is left beyond the SP for the kernel's interrupt handler. The implementation of Go does this, despite the Windows ABI forbidding it.

 

I didn’t know of an effort to use a different SP register.  I seriously doubt that, with GHC’s use of zillions of small, heap-allocated stacks that move around during GHC, we’ll be able to leverage profiling or debugging tools in a serious way. But perhaps I need education.


Existing debugging and profiling tools (e.g., gdb and Linux perf) can become more useful for GHC if they understood how to walk the call stack, regardless of whether the frame moves in memory. One way to do this is to emit call-frame information (CFI) [1,2] in the output assembly that describes the location and layout of the frame as it changes. This would work regardless of the SP register chosen and even if the return address is kept in register. An alternative to using CFI is to use a the canonical SP register and layout, since the default "CFI" assumed by these tools is the OS's ABI.

CFI is the most robust solution for GHC, since some functions allocate more than one frame per invocation to save on code size when applying a curried function (the Making a Fast Curry paper). This is of course orthogonal to the proc-point splitting concern.

I believe Ben originally brought up this desire to use a native SP even for the native backend, because the work of switching to gives us both automatic CFI support and some branch-predictor performance benefits on x86-64. That's likely to be a big overhaul though, so I'm personally in favor of extending LLVM's statepoints to be compatible with GHC and concurrently but separately adding CFI support for the native backend.




 

Simon

 

From: ghc-devs <[hidden email]> On Behalf Of Kavon Farvardin
Sent: 04 December 2019 19:32
To: Ben Gamari <[hidden email]>
Cc: GHC developers <[hidden email]>
Subject: Re: new llvm IR callbr instruction useful for proc-point splitting?

 

Hi Ben,

 

The Wiki now has a link to the Google Doc that Michal and I were working on to compile all of the notes into one place.

 

The key progress made on this front has been in evaluating the trade-offs of the design space being considered by GHC, but tested within Manticore.

 

I'm drafting a message today for the LLVM mailing list regarding one of our first options: defining a GHC ABI to redefine which stack-pointer register is used. 

 

Once we have additional answers to the question "how much effort is it to add a GHC ABI to LLVM?", we can then then start a discussion on whether GHC wants to change instead by moving to a native stack-pointer register (to take advantage of existing debugging and profiling tools, etc).

 

Ideally, we would then make a decision on which option to take and someone (perhaps a GSoC student with mentorship from myself and others) with spare time can work on it.

 

Cheers,

Kavon

 

On Wed, 2019-12-04 at 11:38 -0500, Ben Gamari wrote:

Kavon Farvardin <[hidden email]> writes:
 
Yes, callbr is part of the discussion on removing proc-point splitting! 
Soon there will be an announcement about a new working group dedicated to LLVM
issues such as this one on this mailing list. Anyone interested is welcome to
join our meetings.
We're currently gathering our notes together first, but you can have a look here
for a preview: 
https://gitlab.haskell.org/ghc/ghc/wikis/commentary/compiler/LLVM-Backend-Optimization
 
Hi Kavon,
 
What ever happened to this? It came up during the GHC call and we
realized that none of us knew what the state of the proposal was. Is
this Wiki page still reflective of the current state of play?
 
Cheers,
 
- Ben
 
 

_______________________________________________
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
|

RE: new llvm IR callbr instruction useful for proc-point splitting?

Ben Gamari-3
In reply to this post by GHC - devs mailing list
Simon Peyton Jones <[hidden email]> writes:

> Thanks Kavon.
>
> What news of CpsCall in LLVM?  That seems crucial.
>
> I didn’t know of an effort to use a different SP register. I seriously
> doubt that, with GHC’s use of zillions of small, heap-allocated stacks
> that move around during GHC, we’ll be able to leverage profiling or
> debugging tools in a serious way. But perhaps I need education.
>
I don't see there being a problem here:

 * DWARF debugging information is expressive enough to capture GHC's
   underflow frame concept, so unwinding across stack
   chunks shouldn't be problematic.

 * The fact that the stacks move shouldn't be a problem since
   either:

    * You are using gdb, which must pause the process to look at the stack
      anyways

    * You are using statistical sampling profiling (e.g. perf on Linux)
      which pauses the thread being sampled while capturing the stack
      state.

      If you sample during a GC then you won't capture any Haskell stack
      chunks so the fact that stacks might move isn't problematic; if
      you sample during mutator execution then the stack is guaranteed to
      be stationary.

Cheers,

- Ben


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

signature.asc (497 bytes) Download Attachment