[LLVMdev] Shrink Wrapping - RFC and initial implementation

[John Mosby]

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.

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.
It is limited to X86 presently since that is the only target I have access
to at the moment.

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.


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.

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.

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.

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

Thanks,
John Mosby
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20090226/4b4da3a6/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: shrink-wrapping.patch
Type: application/octet-stream
Size: 43255 bytes
Desc: not available
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20090226/4b4da3a6/attachment.obj>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: test-sw.tar.gz
Type: application/x-gzip
Size: 2272 bytes
Desc: not available
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20090226/4b4da3a6/attachment.bin>