[llvm-dev] RFC: Shrink wrapping vs SplitCSR

Wed May 3 10:50:18 PDT 2017

Hi Kit,

> On May 2, 2017, at 7:54 PM, Kit Barton via llvm-dev <llvm-dev at lists.llvm.org> wrote:
> 
> 
> Hi all, 
> 
> We've seen several examples recently of performance opportunities on
> POWER if we can improve the location of save/restore code for
> callee-saved registers. Both Nemanja and myself have discussed this with
> several people, and it seems that there are two possibilities for
> improving this:
> 
>  1. Extend shrink wrapping to make the analysis of callee-saved
>     registers more precise. 
>  2. Focus on enabling and (possibly) improving SplitCSR. 
> 
> I would like opinions from people on the preferred way to proceed. 
> 
> I am leaning toward improving shrink wrapping, at least as a short-term
> solution. However, I fully admit that this is because I am familiar with
> the shrink wrapping code and completely naive about SplitCSR and what
> work would be necessary to get this working well.
> 
> My proposal would be to implement the flow sensitive analysis described
> by Fred Chow (PLDI '88) and make the necessary extensions in shrink
> wrapping to handle multiple save/restore points. At that point we can do
> an evaluation to understand the improvements it provides and the impact
> on compile time. Once we have these results, we can look at the best way
> to enable it (e.g., option, target opt-in, higher opts, etc.). 

Back in 2009, there was an implementation of Fred Chow’s algorithm, that has been removed in r193749, because it was unused and untested.

I have been working on a new implementation of Fred Chow’s algorithm for a while now.

It seems that this algorithm has been avoided because of the compile time impact that was not worth compared to the performance improvement.

The main reason is that there are probably loops in the CFG. In my implementation, we decided that we never want to save / restore inside a loop, so we consider loops as a single block. We are using scc_iterators instead of MachineLoopInfo in order to handle irreducible loops as well, that are not handled by the current SW implementation. That way, we can compute the anticipation / availability attributes in linear time.

In terms of correctness, there is one test on X86 that still fails, and two others on AArch64, because of the way compact unwinding encodes register saves.

In terms of compile-time, there are no regressions on CTMark.

In terms of code-size, we get a 0.8% increase on X86_64 and AArch64, mostly because we cannot use push / pop anymore.

For now, we only worked on shrink-wrapping CSRs, but keep the stack setup in the entry block / return blocks, which can give worse results in some cases compared to the current shrink-wrapping pass. I am currently working on fixing this.

For execution-time, not many improvements showed up due to the stack setup and the transformation of push/pop -> mov $reg, (mem)/mov (mem), $reg which can be partially solved.

In terms of what the algorithm can do, and how it can outperform the current one, I got some stats based on where we save / restore, along with the block frequency (with PGO), and we can see a theoretical 8% improvement.

I put an early review here a while ago: https://reviews.llvm.org/D30808, and I will update it soon. As you can see, all the PrologEpilogInserter and (X86|AArch64)TargetFrameLowering code look horribly hacky, because so many things assume the stack setup and callee saved saves will stick together. Fixing all those assumptions is going to be the most tricky part of shrink-wrapping, not the algorithm itself.

There are some cases where the current shrink-wrapping is better, and that’s in cases like in the Fig.3 of Chow’s paper, and that can be probably solved by using something similar to what’s described in this paper: Post Register Allocation Spill Code Optimization by Christopher Lupo and Kent D. Wilken, which uses the PST to optimize saves / restores placement along with a cost model.

Cheers,

-- 
Francis Visoiu Mistrih

> 
> Thoughts?
> 
> Kit
> 
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev