[LLVMdev] Shrink Wrapping - RFC and initial implementation

[Evan Cheng]

On Mar 13, 2009, at 10:43 AM, John Mosby wrote:

>
> I started to reduce the traversals, then decided to work on edge  
> splitting because I believe it may be needed to finish shrink  
> wrapping.

Hmm. I don't think edge splitting would be required for correctness,  
right? There is always a common predecessor / successor. For the first  
pass, we should not be shooting to optimal solution.

>
> I will return to that work and see if I can reduce the traversals,  
> which for this approach (computing Antic, Avail) will decrease the  
> constant factor in the runtime bound, which is linear in the size of  
> the Machine IR.
>
> 11. Can you explain a bit more about AnticIn, AvailIn, etc.?
>
> I am working on a document, currently hosted at github, which will  
> present the details of the implementation, examples, etc.
>
> I looked at two approaches to determine spill/restore placements:
>
> 1. Try to use live intervals of CSRs that might be available when  
> PEI runs.
>     The idea here is that each CSR used in a function will have one  
> or more
>     defs which dominate one or more uses. Live intervals might lead  
> me to
>     the MBBs in which to place spills/restores.
>
> 2. Use "anticipatibility" (Antic{In,Out} sets) to find the points  
> from which all
>     outgoing paths contain defs or uses of a CSR, and use  
> "availability"
>     (Avail{In,Out} sets) to find the points such that all incoming  
> paths contain
>     defs or uses of a CSR. We place a spill for a CSR at the  
> earliest point
>     leading to a sequence of uses (a contiguous set of blocks  
> containing uses),
>     so a block B will get a spill for CSR R if R is anticipatable at  
> B and _not_
>     anticipatable at any predecessor of B. If R is used and  
> redefined in a block,
>     we have to avoid placing another spill in that block, (it was  
> spilled earlier),
>     so in addition to the above condition, R must not be available  
> at B.
>     Determining restore placement is the mirror image of spill  
> placement.
>
> I went with approach 2 despite the apparent complexity because the  
> data flow
> info is actually straightforward to compute, and I did not have to  
> first synthesize
> LiveIntervals (read a ton of code) to get the pass working. I am  
> putting this information
> into my temp. wiki page in hopes of getting it into the dev wiki  
> when that is available.

I think it's the right choice.

>
> I am now looking at live intervals in connection with RA and code  
> motion (other possible projects),
> and am trying to answer my question of whether live intervals could  
> help shrink wrapping.

>
> Let me know if you think using live interval info would be worth  
> investigating for shrink wrapping.


The various passes currently do not compute / update live intervals  
for fixed stack slots so it's not appropriate for this. That's why the  
stack slot coloring pass does not color those slots. It would be a  
nice enhancement to add (but for a different reason). :-)

>
> 12.
> Let's worry about edge splitting for a later time. :-)
>
> Agreed. I am still working through the mechanics to understand how  
> to do it and ramifications.
>
> 13. After the code is cleaned up, we should consider checking it in  
> and try it out as llcbeta. Do you have any idea of its compile time  
> impact?
>
> Thanks,
>
> Evan
>
> I'm working on characterizing the runtime and vm overhead, I don't  
> yet have a detailed picture.
> My plan is to do the cleanups, put together a few larger test cases,  
> go back and run regressions,
> then the test suite. With the larger focussed test cases, I will get  
> usable numbers for compile times, and
> the test suite will extend the coverage.
> Please let me know if there is a simpler or more standard way to  
> tackle this for a new pass.

I would just run the test suite once the code is cleaned up. There are  
enough tests to give us a good idea about the compile time / run time  
impact. Since shrink wrapping will be guarded by a command line  
option, you can just run the test suite with ENABLE_LLCBETA. It will  
report everything we need to know.


>
> What about EH and shrink wrapping? Should I disable shrink wrapping  
> in EH contexts?

I am not sure. If tests using EH fails, we can just disable shrink  
wrapping for functions with EH.

>
> I have held off looking at maintaining debug info integrity, let me  
> know if I should look at that or if it can wait a bit.

It's not an immediate problem since -O0 -g means "fast" codegen and  
shrink wrapping is not run. We can worry about this later.

Thanks,

Evan

>
> Thanks again,
> John
>
>
>
>
>
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20090317/29703487/attachment.html>