
<html><head><meta http-equiv="Content-Type" content="text/html charset=utf-8"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class="">Hi Sean,<div class=""><br class=""><div><blockquote type="cite" class=""><div class="">On Jul 24, 2017, at 9:02 PM, Sean Silva <<a href="mailto:chisophugis@gmail.com" class="">chisophugis@gmail.com</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><br class="Apple-interchange-newline"><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class=""><div class="gmail_quote" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;">On Mon, Jul 24, 2017 at 6:24 PM, Quentin Colombet via llvm-dev<span class="Apple-converted-space"> </span><span dir="ltr" class=""><<a href="mailto:llvm-dev@lists.llvm.org" target="_blank" class="">llvm-dev@lists.llvm.org</a>></span><span class="Apple-converted-space"> </span>wrote:<br class=""><blockquote class="gmail_quote" style="margin: 0px 0px 0px 0.8ex; border-left-width: 1px; border-left-color: rgb(204, 204, 204); border-left-style: solid; padding-left: 1ex;"><div style="word-wrap: break-word;" class="">Hi River,<div class=""><br class=""></div><div class="">Thanks for the detailed explanation.</div><div class=""><br class=""></div><div class="">If people are okay for you to move forward, like I said to Andrey, I won’t oppose. I feel sad we have to split our effort on outlining technology, but I certainly don’t pretend to know what is best!</div><div class="">The bottom line is if people are happy with that going in, the conversation on the details can continue in parallel.</div><div class=""><br class=""></div><div class=""><div class=""><span class=""><blockquote type="cite" class=""><div class="">On Jul 24, 2017, at 4:56 PM, River Riddle <<a href="mailto:riddleriver@gmail.com" target="_blank" class="">riddleriver@gmail.com</a>> wrote:</div><br class="m_-5390041256162452728Apple-interchange-newline"><div class=""><div dir="ltr" class="">Hey Quentin,<div class=""> Sorry I missed the last question. Currently it doesn't do continual outlining, but it's definitely a possibility.<br class=""></div></div></div></blockquote><div class=""><br class=""></div></span><div class="">Ok, that means we probably won’t have the very bad runtime problems I had in mind with adding a lot of indirections. </div><span class=""><br class=""><blockquote type="cite" class=""><div class=""><div dir="ltr" class=""><div class="">Thanks,</div><div class="">River Riddle</div></div><div class="gmail_extra"><br class=""><div class="gmail_quote">On Mon, Jul 24, 2017 at 4:36 PM, River Riddle<span class="Apple-converted-space"> </span><span dir="ltr" class=""><<a href="mailto:riddleriver@gmail.com" target="_blank" class="">riddleriver@gmail.com</a>></span><span class="Apple-converted-space"> </span>wrote:<br class=""><blockquote class="gmail_quote" style="margin: 0px 0px 0px 0.8ex; border-left-width: 1px; border-left-color: rgb(204, 204, 204); border-left-style: solid; padding-left: 1ex;"><div dir="ltr" class="">Hi Quentin,<div class=""> <span class="Apple-converted-space"> </span>I understand your points and I believe that some meaning is being lost via email. For performance it's true that that cost isn't necessarily modeled, there is currently only support for using profile data to avoid mitigate that. I was working under the assumption, possibly incorrectly, that at Oz we favor small code over anything else including runtime performance. This is why we only run at Os if we have profile data, and even then we are very conservative about what we outline from. </div><div class=""> <span class="Apple-converted-space"> </span>I also understand that some target hooks may be required for certain things, it happens for other IR level passes as well. I just want to minimize that behavior as much as I can, though thats a personal choice.</div><div class="">As for a motivating reason to push for this, it actually solves some of the problems that you brought up in the post for the original Machine Outliner RFC. If I can quote you:</div><div class=""><br class=""></div><div class="">"<span style="font-family: Arial, Helvetica, sans-serif; font-size: 13px;" class="">So basically, better cost model. That's one part of the story.</span></div><div style="margin: 0px; padding: 0px; border: 0px; font-family: Arial, Helvetica, sans-serif; font-size: 13px;" class=""><br class=""></div><div style="margin: 0px; padding: 0px; border: 0px; font-family: Arial, Helvetica, sans-serif; font-size: 13px;" class="">The other part is at the LLVM IR level or before register allocation identifying similar code sequence is much harder, at least with a suffix tree like algorithm. Basically the problem is how do we name our instructions such that we can match them.</div><div style="margin: 0px; padding: 0px; border: 0px; font-family: Arial, Helvetica, sans-serif; font-size: 13px;" class="">Let me take an example.</div><div style="margin: 0px; padding: 0px; border: 0px; font-family: Arial, Helvetica, sans-serif; font-size: 13px;" class="">foo() {</div><div style="margin: 0px; padding: 0px; border: 0px; font-family: Arial, Helvetica, sans-serif; font-size: 13px;" class="">/* bunch of code */</div><div style="margin: 0px; padding: 0px; border: 0px; font-family: Arial, Helvetica, sans-serif; font-size: 13px;" class="">a = add b, c;</div><div style="margin: 0px; padding: 0px; border: 0px; font-family: Arial, Helvetica, sans-serif; font-size: 13px;" class="">d = add e, f; </div><div style="margin: 0px; padding: 0px; border: 0px; font-family: Arial, Helvetica, sans-serif; font-size: 13px;" class="">}</div><div style="margin: 0px; padding: 0px; border: 0px; font-family: Arial, Helvetica, sans-serif; font-size: 13px;" class=""><br class=""></div><div style="margin: 0px; padding: 0px; border: 0px; font-family: Arial, Helvetica, sans-serif; font-size: 13px;" class="">bar() {</div><div style="margin: 0px; padding: 0px; border: 0px; font-family: Arial, Helvetica, sans-serif; font-size: 13px;" class="">d = add e, g;</div><div style="margin: 0px; padding: 0px; border: 0px; font-family: Arial, Helvetica, sans-serif; font-size: 13px;" class="">f = add c, w;</div><div style="margin: 0px; padding: 0px; border: 0px; font-family: Arial, Helvetica, sans-serif; font-size: 13px;" class="">}</div><div style="margin: 0px; padding: 0px; border: 0px; font-family: Arial, Helvetica, sans-serif; font-size: 13px;" class=""><br class=""></div><div style="margin: 0px; padding: 0px; border: 0px; font-family: Arial, Helvetica, sans-serif; font-size: 13px;" class="">With proper renaming, we can outline both adds in one function. The difficulty is to recognize that they are semantically equivalent to give them the same identifier in the suffix tree. I won’t get into the details but it gets tricky quickly. We were thinking of reusing GVN to have such identifier if we wanted to do the outlining at IR level but solving this problem is hard."</div><div style="margin: 0px; padding: 0px; border: 0px; font-family: Arial, Helvetica, sans-serif; font-size: 13px;" class=""><br class=""></div><div style="margin: 0px; padding: 0px; border: 0px; font-family: Arial, Helvetica, sans-serif; font-size: 13px;" class="">This outliner will catch your case, it is actually one of the easiest cases for it to catch. The outliner can recognize semantically equivalent instructions and can be expanded to catch even more.</div></div></blockquote></div></div></div></blockquote><div class=""><br class=""></div></span><div class="">Interesting, could you explain how you do that?</div><div class="">I didn’t see it in the original post.</div><span class=""><br class=""><blockquote type="cite" class=""><div class=""><div class="gmail_extra"><div class="gmail_quote"><blockquote class="gmail_quote" style="margin: 0px 0px 0px 0.8ex; border-left-width: 1px; border-left-color: rgb(204, 204, 204); border-left-style: solid; padding-left: 1ex;"><div dir="ltr" class=""><div style="margin: 0px; padding: 0px; border: 0px; font-family: Arial, Helvetica, sans-serif; font-size: 13px;" class=""><br class=""></div><div style="margin: 0px; padding: 0px; border: 0px; font-family: Arial, Helvetica, sans-serif; font-size: 13px;" class="">As for the cost model it is quite simple:</div><div style="margin: 0px; padding: 0px; border: 0px; font-family: Arial, Helvetica, sans-serif; font-size: 13px;" class=""> - We identify all of the external inputs into the sequence. For estimating the benefit we constant fold and condense the inputs so that we can get the set of *unique* inputs into the sequence. </div></div></blockquote></div></div></div></blockquote><div class=""><br class=""></div></span><div class="">Ok, those are your parameters. How do you account for the cost of setting up those parameters?</div><span class=""><br class=""><blockquote type="cite" class=""><div class=""><div class="gmail_extra"><div class="gmail_quote"><blockquote class="gmail_quote" style="margin: 0px 0px 0px 0.8ex; border-left-width: 1px; border-left-color: rgb(204, 204, 204); border-left-style: solid; padding-left: 1ex;"><div dir="ltr" class=""><div style="margin: 0px; padding: 0px; border: 0px; font-family: Arial, Helvetica, sans-serif; font-size: 13px;" class=""> - We also identify outputs from the sequence, instructions that have external references. We add the cost of storing/loading/passing output parameter to the outlined function.</div></div></blockquote></div></div></div></blockquote><div class=""><br class=""></div></span><div class="">Ok, those are your return values (or your output parameter). I see the cost computation you do on those, but it still miss the general parameter setup cost.</div><span class=""><br class=""><blockquote type="cite" class=""><div class=""><div class="gmail_extra"><div class="gmail_quote"><blockquote class="gmail_quote" style="margin: 0px 0px 0px 0.8ex; border-left-width: 1px; border-left-color: rgb(204, 204, 204); border-left-style: solid; padding-left: 1ex;"><div dir="ltr" class=""><div style="margin: 0px; padding: 0px; border: 0px; font-family: Arial, Helvetica, sans-serif; font-size: 13px;" class=""> - We identify one output to promote to a return value for the function. This can end up reducing an output parameter that is passed to our outlined function.</div></div></blockquote></div></div></div></blockquote><div class=""><br class=""></div></span><div class="">How do you choose that one?</div><span class=""><br class=""><blockquote type="cite" class=""><div class=""><div class="gmail_extra"><div class="gmail_quote"><blockquote class="gmail_quote" style="margin: 0px 0px 0px 0.8ex; border-left-width: 1px; border-left-color: rgb(204, 204, 204); border-left-style: solid; padding-left: 1ex;"><div dir="ltr" class=""><div style="margin: 0px; padding: 0px; border: 0px; font-family: Arial, Helvetica, sans-serif; font-size: 13px;" class=""> - We estimate the cost of the sequence of instructions by mostly using TTI.</div></div></blockquote></div></div></div></blockquote><div class=""><br class=""></div></span><div class="">Sounds sensible. (Although I am not a fan of the whole TTI thing :)).</div><span class=""><br class=""><blockquote type="cite" class=""><div class=""><div class="gmail_extra"><div class="gmail_quote"><blockquote class="gmail_quote" style="margin: 0px 0px 0px 0.8ex; border-left-width: 1px; border-left-color: rgb(204, 204, 204); border-left-style: solid; padding-left: 1ex;"><div dir="ltr" class=""><div style="margin: 0px; padding: 0px; border: 0px; font-family: Arial, Helvetica, sans-serif; font-size: 13px;" class=""> - With the above we can estimate the cost per occurrence as well as the cost for the new function. Of course these are mostly estimates, we lean towards the conservative side to be safe. <br class=""></div></div></blockquote></div></div></div></blockquote><div class=""><br class=""></div></span><div class="">Conservative in what sense? Put differently how do you know your cost is conservative?</div><span class=""><br class=""><blockquote type="cite" class=""><div class=""><div class="gmail_extra"><div class="gmail_quote"><blockquote class="gmail_quote" style="margin: 0px 0px 0px 0.8ex; border-left-width: 1px; border-left-color: rgb(204, 204, 204); border-left-style: solid; padding-left: 1ex;"><div dir="ltr" class=""><div style="margin: 0px; padding: 0px; border: 0px; font-family: Arial, Helvetica, sans-serif; font-size: 13px;" class=""> - Finally we can compute an estimated benefit for the sequence taking into account benefit per occurrence and the estimated cost of the new function.</div></div></blockquote></div></div></div></blockquote><div class=""><br class=""></div></span>Make sense.</div><div class=""><span class=""><br class=""><blockquote type="cite" class=""><div class=""><div class="gmail_extra"><div class="gmail_quote"><blockquote class="gmail_quote" style="margin: 0px 0px 0px 0.8ex; border-left-width: 1px; border-left-color: rgb(204, 204, 204); border-left-style: solid; padding-left: 1ex;"><div dir="ltr" class=""><div style="margin: 0px; padding: 0px; border: 0px; font-family: Arial, Helvetica, sans-serif; font-size: 13px;" class=""><br class=""></div><div style="margin: 0px; padding: 0px; border: 0px; font-family: Arial, Helvetica, sans-serif; font-size: 13px;" class="">There is definitely room for improvement in the cost model. I do not believe its the best but its shown to be somewhat reliable for most cases. It has benefits and it has regressions, as does the machine outliner.</div></div></blockquote></div></div></div></blockquote><div class=""><br class=""></div></span><div class="">Regressions in what sense?</div><div class="">Do you actually have functions that are bigger?</div><div class=""><br class=""></div><div class="">To clarify, AFAIR, the machine outliner does not have such regressions per say. The outliner does perfectly what the cost model predicted: functions are individually smaller. Code size grow may happen because of padding in the object file (and getting in the way of some linker optimization).</div></div></div></div></blockquote><div class=""><br class=""></div><div class=""><br class=""></div><div class="">The current MIR outliner doesn't take into account instruction encoding length either. Considering that on x86 instructions can commonly be both 1 and 10+ bytes long, the variability from not modeling that is probably comparable to the inaccuracy of estimating a fixed cost for an LLVM IR instruction w.r.t. its lowering to machine code.</div></div></div></blockquote><div><br class=""></div><div>Right, I forgot about x86, AArch64 being the primary target when we did that :).</div><div>Frankly, there is nothing hard doing the estimate on the actual encoding at this stage of the IR. The reasons why we didn’t do it were:</div><div>1. AArch64 does not have differences</div><div>2. It takes some (compile) time to compute that information and given we didn’t need it for AArch64 we didn’t do it.</div><br class=""><blockquote type="cite" class=""><div class=""><div class="gmail_quote" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;"><div class=""><br class=""></div><div class="">As a simple example, many commonly used x86 instructions encode as over 5 bytes, which is the size of a call instruction. So an outlined function that consists of a single instruction can be profitable. IIRC there was about 5% code size saving just from outlining single instructions (that encode at >5 bytes) at machine code level on the test case I looked at (I mentined it in a comment on one of Jessica's patches IIRC).</div></div></div></blockquote><div><br class=""></div><div>Good point!</div><br class=""><blockquote type="cite" class=""><div class=""><div class="gmail_quote" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;"><div class=""><br class=""></div><div class="">Do we have a way to get an instruction's exact encoded length for the MIR outliner?</div></div></div></blockquote><div><br class=""></div><div>Not right now, IIRC, but I would say that’s half a day effort at most. To be fair, I haven’t followed the development of the code base since Jessica’s internship. Jessica would know the details for sure.</div><div><br class=""></div><div>Cheers,</div><div>-Quentin</div><br class=""><blockquote type="cite" class=""><div class=""><div class="gmail_quote" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;"><div class=""><br class=""></div><div class="">-- Sean Silva</div><div class=""> </div></div></div></blockquote></div></div></body></html>