[LLVMdev] Shrink Wrapping - RFC and initial implementation

[Evan Cheng]

On Feb 26, 2009, at 2:02 PM, John Mosby wrote:

> Hello LLVMdev,
>
> I have been working with LLVM for just over a year now, mainly in  
> the area of compilation for HDLs like SystemVerilog and SystemC.
> Most of this work dealt with translation to LLVM IR, representing  
> concurrent languages with LLVM and using LLVM analyses and transforms
> for compiling onto proprietary simulation acceleration hardware. All  
> of this work used the C back end exclusively, since I wanted a  
> transparent
> and easily debuggable flow.

Welcome to the community.

>
> To learn more about the code generator, I decided to try  
> implementing shrink wrapping, a reasonably self-contained back end  
> transformation pass.
>
> I now have a preliminary implemenation of shrink wrapping, done as  
> an option to prologue/epilogue insertion under the switch --shrink- 
> wrap.

Nice.

> It is limited to X86 presently since that is the only target I have  
> access to at the moment.

What part of this is target dependent? Is this due to emitPrologue /  
emitEpilogue being target specific?

>
> The main features are:
>   - Placing callee saved register (CSR) spills and restores in the  
> CFG to tightly surround uses
>      so that execution paths that do not use CSRs do not pay the  
> spill/restore penalty.
>
>   - Avoiding placment of spills/restores in loops: if a CSR is used  
> inside a loop(nest), the spills
>      are placed in the loop preheader, and restores are placed in  
> the loop exit nodes (the
>      successors of the loop _exiting_ nodes).
>
>   - Covering paths without CSR uses: e.g. if a restore is placed in  
> a join block, a matching spill
>      is added to the end of all immediate predecessor blocks that  
> are not reached by a spill.
>      Similarly for saves placed in branch blocks.

Sounds great. It would help everyone if you can show some examples code.

>
>
> Since I ran into a non-trivial issue in developing this pass, I  
> would like to submit my implementation as a "RFC + code/tests"
> rather than a typical contribution, and get people's opinions on how  
> to proceed.
>
> The issue is that the code generator assumes all spills and restores  
> of callee saved registers must be placed in the entry and return  
> blocks resp.
> Shink wrapping violates this assumption, with the result that the  
> frame offsets computed by PEI for frame-relative operands may be  
> incorrect.

I am not sure how this would happen. Why would frame offsets be  
affected by where these instructions are placed?

>
> My limited implementation uses a workaround that adjusts the  
> generation of prologue code and the frame indices used by
> the target eliminateFrameIndex() when necessary. I am looking at  
> several approaches, but I would like input from anyone who
> has an opinion.
>

I think to do this right for every target is a big job. I'd like to  
see prologue / epilogue related stuff be moved out of  
TargetRegisterInfo. Shrink wrapping will only happen when the targets  
buy-in, i.e. providing the right hooks.

When is shrink wrapping happening? Is it possible to do it after CSR  
spills and restores are inserted but before FI are lowered into sp /  
fp +/- offset?

> Finally, I realize that shrink wrapping is probably not high  
> priority in the larger scheme of LLVM development, so I'm not  
> expecting
> a huge response, but any ideas are certainly welcome.

It's actually a fairly useful optimization. It can really help a class  
of functions, e.g. functions with early returns.

>
> The patch and a test tarball are attached. I include basic tests  
> that are run with the supplied Makefile.

Some comments:

1. The code needs some refactoring. :-) It's a big chunk of code so  
it's hard to digest.
2. There doesn't seem to be a way to turn off shrink wrapping. Please  
make sure it's optional. When it's not being done, PEI should not  
require dominator, etc.

 From what I can see this is a very good first step. I look forward to  
seeing its completion.

Evan


>
> Thanks,
> John Mosby
> <shrink-wrapping.patch><test- 
> sw.tar.gz>_______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev