Improve stack slot reuse

[ilovepi]

When compared to GCC and MSVC, Clang/LLVM is not doing a good job of reusing stack space. Most of that boils down to inefficiencies/inaccuracies in the way we do stack coloring. Today, LLVM supports two kinds of stack coloring. One focuses on local variables(StackColoring), and the other on register spills(StackSlotColoring). For the most part, the two transforms use the same algorithm, but are implemented separately for historical reasons. In the stack slot coloring code, there is a comment indicating that we should unify the two (https://github.com/llvm/llvm-project/blob/644899addd8fd789c93e9a0f0727d37eb1b29c55/llvm/lib/CodeGen/StackColoring.cpp#L15). However, after discussing this idea at the Dev Meeting last year, I’m not sure how practical it is to actually do that.

In our discussion it was noted that several developers had already to solve this and failed. Though it seems straightforward to unify the two passes, in practice this has proven more difficult to achieve, since there are many subtle interactions with other parts of code generation. One of the key issues people remembered was that there are some long standing issues with the accuracy of lifetime insertion, and previous attempts to unify these passes has been difficult because of it. The inaccuracy here wasn’t just a conservative approximation, but would sometimes be wrong, leading to miscompilation/stack corruption. Keeping the two transforms separate has kept things working for now.

Given that the above approach seems to require more significant effort, we should probably focus on improving the quality of the lifetime annotations in the short term, and start discussing how we can improve the architecture/analysis to do better in the long-term. To start, #68746 points out that currently, we do a poor job annotating the lifetimes of temporaries. This is made more complex by some recent changes at the language level. https://github.com/llvm/llvm-project/issues/68746#issuecomment-1828337003 outlines some steps we can take to alleviate that. I believe that enough progress has been made in clang to revive https://reviews.llvm.org/D74094#4647616, though @AaronBallman would have to confirm that.

We also have some other open issues around slot reuse, such as #57725, and several more going further back (though I'm not sure if they are still relevant). I think these should be reevaluated, and that we should try to determine their root cause, should they persist.

This is something I'd like to start looking at more seriously in the next few months, and I'd like to coordinate efforts here w/ the rest of the community.

A few questions I have are: 1) if anyone else has looked at this (IIRC @preames gave me a lot of the background context at last year's dev meeting)? 2) if they're aware of other's working on this? 3) if this is a priority for anyone else? 4) are there other approaches we should consider?

cc'ing some relevant folks: @petrhosek @nickdesaulniers @topperc @hiraditya

[efriedma-quic]

See #51838 and #45725 for past discussion of the general brokenness of lifetime.start/lifetime.end. (Nothing relevant has changed since then.)

[hiraditya]

IMO it'll be better to just write a global stack coloring algorithm and then remove the other two.