[llvm-dev] Function with multi return path?

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

[llvm-dev] Function with multi return path?

Gerolf Hoflehner via llvm-dev
Hi folks,

I'm new to LLVM and non-expert in hardware architecture, so my question might be dumb.

I'm looking for the possibility to define/call a function with multi return path, it might look like this:

```
; Define a function with 1 alternate return path
define i32 @f(i1 %i) fork 1 {
  br i1 %i, label %noraml, label %alternate
noraml:
  ...
  setpath ret i32 42 ; take normal return path
  br %cleanup
alternate:
  ...
  setpath fork 0 ; take the alternate return path
  br %cleanup
cleanup: ; preds = %noraml, %alternate
  ...
  unwind ; return to the caller
}
```

And at the call side:
```
  %ret = call @f(i1 %i) fork [%otherwise]
  ...
otherwise:
  ...
```

Ideally, the callee sets the return address so it returns directly to the desired location in the caller w/o the caller taking extra switch.

The idea is to implement some non-local control flow w/o extra overhead at each call side.

I know LLVM doesn't have something like this currently, but is it possible to implement?

_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [llvm-dev] Function with multi return path?

Gerolf Hoflehner via llvm-dev
The closest thing LLVM has to this is the invoke instruction used for exception handling. Using it requires reusing or building a lot of EH runtime support, though. invoke only supports a single alternative return destination (the landingpad), but you can use the selector value to switch over multiple language level alternative return destinations.

On Wed, May 31, 2017 at 11:57 PM, TONGARI J via llvm-dev <[hidden email]> wrote:
Hi folks,

I'm new to LLVM and non-expert in hardware architecture, so my question might be dumb.

I'm looking for the possibility to define/call a function with multi return path, it might look like this:

```
; Define a function with 1 alternate return path
define i32 @f(i1 %i) fork 1 {
  br i1 %i, label %noraml, label %alternate
noraml:
  ...
  setpath ret i32 42 ; take normal return path
  br %cleanup
alternate:
  ...
  setpath fork 0 ; take the alternate return path
  br %cleanup
cleanup: ; preds = %noraml, %alternate
  ...
  unwind ; return to the caller
}
```

And at the call side:
```
  %ret = call @f(i1 %i) fork [%otherwise]
  ...
otherwise:
  ...
```

Ideally, the callee sets the return address so it returns directly to the desired location in the caller w/o the caller taking extra switch.

The idea is to implement some non-local control flow w/o extra overhead at each call side.

I know LLVM doesn't have something like this currently, but is it possible to implement?

_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev



_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [llvm-dev] Function with multi return path?

jamboree
This post has NOT been accepted by the mailing list yet.
Hi Reid,

I'm aware of the invoke instruction and landingpad. But it's too heavy weight for control flow. It's quite expensive to take the exceptional path in C++.

What I want is a more lightweight approach, to pass the return address to the callee, and let the callee jump to that address directly.
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [llvm-dev] Function with multi return path?

Gerolf Hoflehner via llvm-dev
In reply to this post by Gerolf Hoflehner via llvm-dev
Hi Reid,

I'm aware of the invoke instruction and landingpad. But it's too heavy
weight for control flow. It's quite expensive to take the exceptional path
in C++.

What I want is a more lightweight approach, to pass the return address to
the callee, and let the callee jump to that address directly.

_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [llvm-dev] Function with multi return path?

Gerolf Hoflehner via llvm-dev
On 2 Jun 2017, at 03:38, TONGARI J via llvm-dev <[hidden email]> wrote:
>
> I'm aware of the invoke instruction and landingpad. But it's too heavy
> weight for control flow. It's quite expensive to take the exceptional path
> in C++.
>
> What I want is a more lightweight approach, to pass the return address to
> the callee, and let the callee jump to that address directly.

The best way of implementing this is likely to be to use a custom calling convention along with invoke.  The invoke instruction will handle the semantics correctly in the IR, but you’ll need to modify the back end to understand that it should generate the call site differently and not emit unwind tables.

David

_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [llvm-dev] Function with multi return path?

Gerolf Hoflehner via llvm-dev
2017-06-02 19:51 GMT+08:00 David Chisnall <[hidden email]>:
On 2 Jun 2017, at 03:38, TONGARI J via llvm-dev <[hidden email]> wrote:
>
> I'm aware of the invoke instruction and landingpad. But it's too heavy
> weight for control flow. It's quite expensive to take the exceptional path
> in C++.
>
> What I want is a more lightweight approach, to pass the return address to
> the callee, and let the callee jump to that address directly.

The best way of implementing this is likely to be to use a custom calling convention along with invoke.  The invoke instruction will handle the semantics correctly in the IR, but you’ll need to modify the back end to understand that it should generate the call site differently and not emit unwind tables.
 
A custom calling convention doesn't suffice, there could be more than one alternate paths. And invoke instruction is also not general enough.

_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [llvm-dev] Function with multi return path?

Gerolf Hoflehner via llvm-dev
On 2 Jun 2017, at 15:34, TONGARI J via llvm-dev <[hidden email]> wrote:

>
> 2017-06-02 19:51 GMT+08:00 David Chisnall <[hidden email]>:
> On 2 Jun 2017, at 03:38, TONGARI J via llvm-dev <[hidden email]> wrote:
> >
> > I'm aware of the invoke instruction and landingpad. But it's too heavy
> > weight for control flow. It's quite expensive to take the exceptional path
> > in C++.
> >
> > What I want is a more lightweight approach, to pass the return address to
> > the callee, and let the callee jump to that address directly.
>
> The best way of implementing this is likely to be to use a custom calling convention along with invoke.  The invoke instruction will handle the semantics correctly in the IR, but you’ll need to modify the back end to understand that it should generate the call site differently and not emit unwind tables.
>  
> A custom calling convention doesn't suffice, there could be more than one alternate paths. And invoke instruction is also not general enough.

You could approximate this using the address-of-label extension and passing the address of the return basic block to the function then, in the abnormal return path, jumping to that.  Doing anything else is likely to be very complicated because the live registers at all of the potential landing points will need to agree and you’re likely to cost more in code complexity than you save.

David


_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [llvm-dev] Function with multi return path?

Gerolf Hoflehner via llvm-dev
2017-06-07 22:51 GMT+08:00 David Chisnall <[hidden email]>:
You could approximate this using the address-of-label extension and passing the address of the return basic block to the function then, in the abnormal return path, jumping to that.  Doing anything else is likely to be very complicated because the live registers at all of the potential landing points will need to agree and you’re likely to cost more in code complexity than you save.

I don't think blockaddress/indirectbr supports non-local jump. Does it?
Or do you mean something else?

_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [llvm-dev] Function with multi return path?

Gerolf Hoflehner via llvm-dev
On 7 Jun 2017, at 16:13, TONGARI J via llvm-dev <[hidden email]> wrote:
>
> 2017-06-07 22:51 GMT+08:00 David Chisnall <[hidden email]>:
> You could approximate this using the address-of-label extension and passing the address of the return basic block to the function then, in the abnormal return path, jumping to that.  Doing anything else is likely to be very complicated because the live registers at all of the potential landing points will need to agree and you’re likely to cost more in code complexity than you save.
>
> I don't think blockaddress/indirectbr supports non-local jump. Does it?

No, but you can take the address of the block, pass it to the function, have the function return to the alternate return address and then (in the caller) jump immediately to the address in the return register.  Note that this (along with your original suggestion) will have really poor interaction with any modern branch predictor.

David

_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [llvm-dev] Function with multi return path?

Gerolf Hoflehner via llvm-dev
2017-06-07 23:42 GMT+08:00 David Chisnall <[hidden email]>:
No, but you can take the address of the block, pass it to the function, have the function return to the alternate return address and then (in the caller) jump immediately to the address in the return register.

Yeah, that's the closest way we can get in LLVM at this moment.
 
Note that this (along with your original suggestion) will have really poor interaction with any modern branch predictor.
 
In my idea the caller and callee have full knowledge about the branch destinations, so if the optimizer inlines the callee, it can jump to the alternate destinations w/o indirection.
In case it's not inlined, the normal return path should incur no overhead as well, and for alternate return paths it's just a matter of setting the return register.
But as I said, I'm not an expert so I don't really know whether what I described is implementable in LLVM on all architectures.


_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Loading...