<html><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; "><br><div><div>On Mar 13, 2009, at 10:43 AM, John Mosby wrote:</div><br class="Apple-interchange-newline"><blockquote type="cite"><div><div class="gmail_quote"><div><br></div><div>I started to reduce the traversals, then decided to work on edge splitting because I believe it may be needed to finish shrink wrapping.</div></div></div></blockquote><div><br></div>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.</div><div><br><blockquote type="cite"><div><div class="gmail_quote"><div><br></div><div>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.</div>
<div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;"><div style="word-wrap:break-word"><div><div><div><div><div><div><div><div><div></div></div></div></div></div>
<div>11. Can you explain a bit more about AnticIn, AvailIn, etc.?</div></div></div></div></div></div></blockquote><div><br></div><div>I am working on a document, currently hosted at github, which will present the details of the implementation, examples, etc.</div>
<div><br></div><div>I looked at two approaches to determine spill/restore placements:</div><div><br></div><div>1. Try to use live intervals of CSRs that might be available when PEI runs.</div><div> The idea here is that each CSR used in a function will have one or more</div>
<div> defs which dominate one or more uses. Live intervals might lead me to</div><div> the MBBs in which to place spills/restores.</div><div><br></div><div>2. Use "anticipatibility" (Antic{In,Out} sets) to find the points from which all</div>
<div> outgoing paths contain defs or uses of a CSR, and use "availability"</div><div> (Avail{In,Out} sets) to find the points such that all incoming paths contain</div><div> defs or uses of a CSR. We place a spill for a CSR at the earliest point</div>
<div> leading to a sequence of uses (a contiguous set of blocks containing uses),</div><div> so a block B will get a spill for CSR R if R is anticipatable at B and _not_</div><div> anticipatable at any predecessor of B. If R is used and redefined in a block,</div>
<div> we have to avoid placing another spill in that block, (it was spilled earlier),</div><div> so in addition to the above condition, R must not be available at B.</div><div> Determining restore placement is the mirror image of spill placement.</div>
<div><br></div><div>I went with approach 2 despite the apparent complexity because the data flow</div><div>info is actually straightforward to compute, and I did not have to first synthesize</div><div>LiveIntervals (read a ton of code) to get the pass working. I am putting this information</div>
<div>into my temp. wiki page in hopes of getting it into the dev wiki when that is available.</div></div></div></blockquote><div><br></div>I think it's the right choice.</div><div><br><blockquote type="cite"><div><div class="gmail_quote"><div><br></div><div>I am now looking at live intervals in connection with RA and code motion (other possible projects),</div>
<div>and am trying to answer my question of whether live intervals could help shrink wrapping.</div></div></div></blockquote></div><div><blockquote type="cite"><div><div class="gmail_quote"><div><br></div><div>Let me know if you think using live interval info would be worth investigating for shrink wrapping.</div></div></div></blockquote><div><br></div><div><br></div><div>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). :-)</div><div><br></div><blockquote type="cite"><div><div class="gmail_quote">
<div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;"><div style="word-wrap:break-word"><div><div><div><div><div></div><div>12.</div><div>Let's worry about edge splitting for a later time. :-)</div>
</div></div></div></div></div></blockquote><div><br></div><div>Agreed. I am still working through the mechanics to understand how to do it and ramifications.</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
<div style="word-wrap:break-word"><div><div><div><div><div></div></div></div></div></div><div>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?</div>
<div><br></div><div>Thanks,</div><div><br></div><div>Evan</div></div></blockquote><div><br></div><div>I'm working on characterizing the runtime and vm overhead, I don't yet have a detailed picture.</div><div>My plan is to do the cleanups, put together a few larger test cases, go back and run regressions,</div>
<div>then the test suite. With the larger focussed test cases, I will get usable numbers for compile times, and</div><div>the test suite will extend the coverage.</div><div>Please let me know if there is a simpler or more standard way to tackle this for a new pass.</div></div></div></blockquote><div><br></div>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.</div><div><br></div><div><br><blockquote type="cite"><div><div class="gmail_quote">
<div><br></div><div>What about EH and shrink wrapping? Should I disable shrink wrapping in EH contexts?</div></div></div></blockquote><div><br></div>I am not sure. If tests using EH fails, we can just disable shrink wrapping for functions with EH.</div><div><br><blockquote type="cite"><div><div class="gmail_quote"><div><br></div><div>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.</div></div></div></blockquote><div><br></div>It's not an immediate problem since -O0 -g means "fast" codegen and shrink wrapping is not run. We can worry about this later.</div><div><br></div><div>Thanks,</div><div><br></div><div>Evan</div><div><br><blockquote type="cite"><div><div class="gmail_quote">
<div><br></div><div>Thanks again,</div><div>John</div><div><br></div><div><br></div><div><br></div><div><br></div><div><br></div><div> </div></div></div>
_______________________________________________<br>LLVM Developers mailing list<br><a href="mailto:LLVMdev@cs.uiuc.edu">LLVMdev@cs.uiuc.edu</a> <a href="http://llvm.cs.uiuc.edu">http://llvm.cs.uiuc.edu</a><br><a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a><br></blockquote></div><br></body></html>