Nested ADJCALLSTACK UP/DOWN allowed?

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`?*

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

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!

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 <llvm-dev@lists.llvm.org> 於 2018年10月22日 週一 上午5:51寫道:

Hi Shiva,

thanks for the info and the patch! It at the very least fixes my
minimized example.

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