[llvm-dev] Nested ADJCALLSTACK UP/DOWN allowed?

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

[llvm-dev] Nested ADJCALLSTACK UP/DOWN allowed?

David Jones via llvm-dev
Hi all,

I once again ran into an issue / assertion while playing around with
the experimental LLVM AVR backend. This time, however I'm not sure if
the issue is with LLVM in general or with the AVR backend. I believe
that where the issue is boils down to the following question (which I
don't know / couldn't find the answer to):

*Are nested `ADJCALLSTACK` `UP`/`DOWN` instructions allowed / supposed
to be supported? i.e. is `down/down/up/up` supposed to be a valid
sequence of instructions or only `down/up/down/up`?*

---

If the answer is that they are _not_ supposed to be nested, then I
believe that the issue is with LLVM in general. Assuming that this is
the case, or for those interested, I have included a summary of the
original issue [0] below.

Consider the SUnit DAG of compiling [1] with `llc -O1` before [2] and
after [3] `PrescheduleNodesWithMultipleUses` is run on it. Notice how
the dependencies have been rearranged so that `SU2` now depends on the
stores rather than the `CopyFromReg`s, which also means that both
`ADJCALLSTACKUP`s need to be scheduled before `SU2`. This
transformation causes the issue below.

The actual symptoms:

The first assertion I hit was `Assertion failed: (BestRC && "Couldn't
find the register class"), function getMinimalPhysRegClass,
TargetRegisterInfo.cpp:203` in
`ScheduleDAGRRList::PickNodeToScheduleBottomUp`, which was triggered
because the `MVT` being passed in was "Glue" (for which there
obviously is no register class, at least if I understand everything
correctly).

We are getting "Glue" as the `MVT` because `getPhysicalRegisterVT`,
which is called to produce it, is returning bad data due to a
"missing" assertion. Note that I'm kind of guessing how the code in
`getPhysicalRegisterVT` is supposed to behave, in particular I'm
guessing that the `for`-loop is only supposed to terminate from the
`break` and not due to running out of elements to iterate over. I'm
somewhat confident in this guess since adding an assertion like in [5]
does not cause any tests in the test suite to fail. It does, however,
trigger instead of the assertion above.

In any case, what is happening to produce the "Glue" is that the
register passed in is 53, which is not a real register but one passed
the end of valid register IDs. As I understand the code, this is
sometime called a "CallResource". This means that the `for`-loop in
`getPhysicalRegisterVT` never breaks and thus `NumRes` is one passed
the end of the data about "implicit defs", which just happens to be
"Glue".

Anyway, that's how I understand the issue currently. Thanks for
reading, especially if you've made it this far.

[0]: https://github.com/avr-rust/rust/issues/111
[1]: https://gist.github.com/501819422631149c3ab2b8cc0b15c98d
[2]: https://user-images.githubusercontent.com/1178249/47268656-bb872c00-d553-11e8-9c0e-be30c4cac595.png
[3]: https://user-images.githubusercontent.com/1178249/47256523-31bb5e00-d482-11e8-84a8-25a546aba654.png
[4]: https://gist.github.com/2255d0d389b30edbaea43e26bbdbdd1c

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

Re: [llvm-dev] Nested ADJCALLSTACK UP/DOWN allowed?

David Jones via llvm-dev
The answer is probably: Nobody knows  (though I’d be happy to hear if someone remembers older design motivations/discussions).
The last time I looked at the issue:

- I could not find a good reason why we should forbid it. That said:
- The machine verifier seems to reject it today, so at the very least one would need to fix that and review whether existing code makes assumptions about there being no nesting.
- I could not find a good reason why we would need it either; it should always be possible to do calls sequentially and not nest the call frame preparations and I could not think of any reason why this would be worse.
- The reason that brought me looking into the whole issue was some pattern getting turned into a compiler library call late. Back then I sidestepped the whole discussion by stopping to emit ADJCALLSTACK UP/DOWN of zero byte call frames (https://reviews.llvm.org/D42006) so they wouldn’t nest anymore for the helpers functions in question…

- Matthias


On Oct 21, 2018, at 8:49 AM, Tim Neumann via llvm-dev <[hidden email]> wrote:

Hi all,

I once again ran into an issue / assertion while playing around with
the experimental LLVM AVR backend. This time, however I'm not sure if
the issue is with LLVM in general or with the AVR backend. I believe
that where the issue is boils down to the following question (which I
don't know / couldn't find the answer to):

*Are nested `ADJCALLSTACK` `UP`/`DOWN` instructions allowed / supposed
to be supported? i.e. is `down/down/up/up` supposed to be a valid
sequence of instructions or only `down/up/down/up`?*

---

If the answer is that they are _not_ supposed to be nested, then I
believe that the issue is with LLVM in general. Assuming that this is
the case, or for those interested, I have included a summary of the
original issue [0] below.

Consider the SUnit DAG of compiling [1] with `llc -O1` before [2] and
after [3] `PrescheduleNodesWithMultipleUses` is run on it. Notice how
the dependencies have been rearranged so that `SU2` now depends on the
stores rather than the `CopyFromReg`s, which also means that both
`ADJCALLSTACKUP`s need to be scheduled before `SU2`. This
transformation causes the issue below.

The actual symptoms:

The first assertion I hit was `Assertion failed: (BestRC && "Couldn't
find the register class"), function getMinimalPhysRegClass,
TargetRegisterInfo.cpp:203` in
`ScheduleDAGRRList::PickNodeToScheduleBottomUp`, which was triggered
because the `MVT` being passed in was "Glue" (for which there
obviously is no register class, at least if I understand everything
correctly).

We are getting "Glue" as the `MVT` because `getPhysicalRegisterVT`,
which is called to produce it, is returning bad data due to a
"missing" assertion. Note that I'm kind of guessing how the code in
`getPhysicalRegisterVT` is supposed to behave, in particular I'm
guessing that the `for`-loop is only supposed to terminate from the
`break` and not due to running out of elements to iterate over. I'm
somewhat confident in this guess since adding an assertion like in [5]
does not cause any tests in the test suite to fail. It does, however,
trigger instead of the assertion above.

In any case, what is happening to produce the "Glue" is that the
register passed in is 53, which is not a real register but one passed
the end of valid register IDs. As I understand the code, this is
sometime called a "CallResource". This means that the `for`-loop in
`getPhysicalRegisterVT` never breaks and thus `NumRes` is one passed
the end of the data about "implicit defs", which just happens to be
"Glue".

Anyway, that's how I understand the issue currently. Thanks for
reading, especially if you've made it this far.

[0]: https://github.com/avr-rust/rust/issues/111
[1]: https://gist.github.com/501819422631149c3ab2b8cc0b15c98d
[2]: https://user-images.githubusercontent.com/1178249/47268656-bb872c00-d553-11e8-9c0e-be30c4cac595.png
[3]: https://user-images.githubusercontent.com/1178249/47256523-31bb5e00-d482-11e8-84a8-25a546aba654.png
[4]: https://gist.github.com/2255d0d389b30edbaea43e26bbdbdd1c

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

Re: [llvm-dev] Nested ADJCALLSTACK UP/DOWN allowed?

David Jones via llvm-dev
> The reason that brought me looking into the whole issue was some pattern getting turned into a compiler library call late. Back then I sidestepped the whole discussion by stopping to emit ADJCALLSTACK UP/DOWN of zero byte call frames (https://reviews.llvm.org/D42006) so they wouldn’t nest anymore for the helpers functions in question…

Adding a similar patch to AVR fixes at least my minimizedreproduction,
I haven't gotten around to trying it on other code yet.

Thanks for all the info!
_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|

Re: [llvm-dev] Nested ADJCALLSTACK UP/DOWN allowed?

David Jones via llvm-dev
Hi Tim,

ADJCALLSTACKUP`s can't interleave probably because ADJCALLSTACKUP`s
may lower to SP adjustment instructions by
eliminateCallFramePseudoInstr when there exist variable sized objects.
Interleaving ADJCALLSTACKUP`s may cause the instructions accessing
variable sized objects with the incorrect offset.
So instruction scheduler creates CallResource artificial registers as
a glue to avoid interleaving while scheduling.
We encounter the same issue and find out that one of the
ADJCALLSTACKUP has been pre-scheduled by
PrescheduleNodesWithMultipleUses as you mention in
https://github.com/avr-rust/rust/issues/111#issuecomment-431603807.
The ADJCALLSTACKUP hoist too early in the code sequence and hold
CallResource too long which make other ADJCALLSTACKUP/DOWN can't be
scheduled. When there is no other nodes can be scheduled, the
scheduler will try to rename the register by creating copies, but
CallResource isn't a real register which triggers the error.
It seems that PrescheduleNodesWithMultipleUses is a heuristic
optimization method for better scheduling result, but hoisting
ADJCALLSTACKUP won't have benefit. There're several conditions that
PrescheduleNodesWithMultipleUses won't pre-schedule the node. I think
ADJCALLSTACKUP should be one of them because it will increase the
lifetime of CallResource. I have tried to push a patch on
https://reviews.llvm.org/D53485. Hopefully, it could be helpful.

Best,
Shiva
Tim Neumann via llvm-dev <[hidden email]> 於 2018年10月22日 週一 上午5:51寫道:

>
> > The reason that brought me looking into the whole issue was some pattern getting turned into a compiler library call late. Back then I sidestepped the whole discussion by stopping to emit ADJCALLSTACK UP/DOWN of zero byte call frames (https://reviews.llvm.org/D42006) so they wouldn’t nest anymore for the helpers functions in question…
>
> Adding a similar patch to AVR fixes at least my minimizedreproduction,
> I haven't gotten around to trying it on other code yet.
>
> Thanks for all the info!
> _______________________________________________
> 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
|

Re: [llvm-dev] Nested ADJCALLSTACK UP/DOWN allowed?

David Jones via llvm-dev
Hi Shiva,

thanks for the info and the patch! It at the very least fixes my
minimized example.
On Mon, Oct 22, 2018 at 8:03 AM Shiva Chen <[hidden email]> wrote:

>
> Hi Tim,
>
> ADJCALLSTACKUP`s can't interleave probably because ADJCALLSTACKUP`s
> may lower to SP adjustment instructions by
> eliminateCallFramePseudoInstr when there exist variable sized objects.
> Interleaving ADJCALLSTACKUP`s may cause the instructions accessing
> variable sized objects with the incorrect offset.
> So instruction scheduler creates CallResource artificial registers as
> a glue to avoid interleaving while scheduling.
> We encounter the same issue and find out that one of the
> ADJCALLSTACKUP has been pre-scheduled by
> PrescheduleNodesWithMultipleUses as you mention in
> https://github.com/avr-rust/rust/issues/111#issuecomment-431603807.
> The ADJCALLSTACKUP hoist too early in the code sequence and hold
> CallResource too long which make other ADJCALLSTACKUP/DOWN can't be
> scheduled. When there is no other nodes can be scheduled, the
> scheduler will try to rename the register by creating copies, but
> CallResource isn't a real register which triggers the error.
> It seems that PrescheduleNodesWithMultipleUses is a heuristic
> optimization method for better scheduling result, but hoisting
> ADJCALLSTACKUP won't have benefit. There're several conditions that
> PrescheduleNodesWithMultipleUses won't pre-schedule the node. I think
> ADJCALLSTACKUP should be one of them because it will increase the
> lifetime of CallResource. I have tried to push a patch on
> https://reviews.llvm.org/D53485. Hopefully, it could be helpful.
>
> Best,
> Shiva
> Tim Neumann via llvm-dev <[hidden email]> 於 2018年10月22日 週一 上午5:51寫道:
> >
> > > The reason that brought me looking into the whole issue was some pattern getting turned into a compiler library call late. Back then I sidestepped the whole discussion by stopping to emit ADJCALLSTACK UP/DOWN of zero byte call frames (https://reviews.llvm.org/D42006) so they wouldn’t nest anymore for the helpers functions in question…
> >
> > Adding a similar patch to AVR fixes at least my minimizedreproduction,
> > I haven't gotten around to trying it on other code yet.
> >
> > Thanks for all the info!
> > _______________________________________________
> > 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
|

Re: [llvm-dev] Nested ADJCALLSTACK UP/DOWN allowed?

David Jones via llvm-dev
In reply to this post by David Jones via llvm-dev
On Oct 21, 2018, at 8:49 AM, Tim Neumann via llvm-dev <[hidden email]> wrote:
> I once again ran into an issue / assertion while playing around with
> the experimental LLVM AVR backend. This time, however I'm not sure if
> the issue is with LLVM in general or with the AVR backend. I believe
> that where the issue is boils down to the following question (which I
> don't know / couldn't find the answer to):
>
> *Are nested `ADJCALLSTACK` `UP`/`DOWN` instructions allowed / supposed
> to be supported? i.e. is `down/down/up/up` supposed to be a valid
> sequence of instructions or only `down/up/down/up`?*

It has been a very long time since I’ve worked on this area, but back in the day, the answer was “no” this was not supported or intended to be supported.  Call sequences were supposed to be linearized w.r.t. each other, at least before regalloc.

The implementation may have evolved though.

-Chris

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