<html><head><meta http-equiv="Content-Type" content="text/html; charset=utf-8"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class=""><div dir="auto" style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class=""><br class=""><div>I think that, given previous discussion on the topic, we might want a split like this:<br class=""><div class=""><div class=""><div class=""><br class=""></div><div class="">(1) Search structure</div><div class=""><br class=""></div><div class="">Suffix tree or suffix array.</div><div class=""><br class=""></div><div class="">(2) Numbering/mapping/congruence scheme</div><div class=""><br class=""></div><div class="">Every outliner should implement a function that maps instructions (or whatever structure you want to outline, crazy thoughts…) to integers. That should be passed to the search structure, which will return a list of repeated sequences.</div><div class=""><br class=""></div><div class="">The MachineOutliner currently has an “InstructionMapper” struct in it. I think we can probably build on that struct so that we can choose different mapping schemes.</div><div class=""><br class=""></div><div class="">(3) Cost model/candidate selection scheme</div><div class=""><br class=""></div><div class="">Every outliner should implement a function that returns the outlining cost or benefit of a candidate. In the MachineOutliner, this is a joint effort between the pass and the target.</div><div class=""><br class=""></div><div class="">(4) Outlining scheme</div><div class=""><br class=""></div><div class="">Every outliner should implement a function that actually performs outlining. That is, we should have a function that replaces each instance of a repeated sequence of instructions with a call to a newly-created function. In the MachineOutliner, the method by which we do this is decided on by the target.</div><div class=""><br class=""></div><div class="">So, we at the very least might want an interface that implements something like</div><div class=""><br class=""></div><div class="">unsigned mapInstructions(…);</div><div class="">unsigned getOutliningCost(…);</div><div class="">unsigned findCandidates(…);</div><div class="">bool outline(…);</div><div class=""><br class=""></div><div class="">The MachineOutliner is *almost* set up like this. So, I think it should be pretty easy to build the split this way without a lot of adaptation. The only place I can see it being somewhat tricky is maybe with all of the target-specified information in the MachineOutliner. I think this is pretty similar to what River has already suggested, though.</div><div class=""><br class=""></div><div class="">I think it would probably be easier to move forward by pulling stuff out of the MachineOutliner instead of replacing all of that code with new stuff. However, that being said, if there’s an improvement to both passes by changing the infrastructure, I’m not opposed to experimenting with changes!</div><div class=""><br class=""></div><div class="">It would probably be easier to try to mostly pull stuff from the MachineOutliner though, since it’s already been in tree for a while and has been tested quite a bit.</div><div class=""><br class=""></div><div class="">- Jessica</div><div class=""><br class=""></div></div></div><blockquote type="cite" class=""><div class="">On Sep 26, 2017, at 5:24 PM, Gerolf Hoflehner via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org" class="">llvm-dev@lists.llvm.org</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><div style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class=""><blockquote type="cite" class=""><div class=""><br class="Apple-interchange-newline">On Sep 21, 2017, at 8:02 PM, River Riddle <<a href="mailto:riddleriver@gmail.com" class="">riddleriver@gmail.com</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><div dir="ltr" class="">Hey Gerolf,<br class=""><div class="gmail_extra"><br class=""><div class="gmail_quote">On Thu, Sep 21, 2017 at 7:10 PM, Gerolf Hoflehner<span class="Apple-converted-space"> </span><span dir="ltr" class=""><<a href="mailto:ghoflehner@apple.com" target="_blank" class="">ghoflehner@apple.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-style: solid; border-left-color: rgb(204, 204, 204); padding-left: 1ex;"><div class="" style="word-wrap: break-word; line-break: after-white-space;"><div dir="auto" class="" style="word-wrap: break-word; line-break: after-white-space;">In general I would love to see an outliner at the IR level also. But rather than a comparison vs. the machine outliner I would like to learn more about how the core data structures between the outliners will be shared.</div></div></blockquote><div class=""> </div><div class="">The only structure that needs to be shared is a struct defining what an outlining candidate looks like.</div><div class=""> </div><blockquote class="gmail_quote" style="margin: 0px 0px 0px 0.8ex; border-left-width: 1px; border-left-style: solid; border-left-color: rgb(204, 204, 204); padding-left: 1ex;"><div class="" style="word-wrap: break-word; line-break: after-white-space;"><div dir="auto" class="" style="word-wrap: break-word; line-break: after-white-space;">In particular for matching/pruning it seems to be a reasonable approach.</div></div></blockquote><div class=""> </div><div class="">When I get around to posting the real patches there are two utility functions that allow for finding candidates and pruning a candidate list. The only thing necessary to use these utilities is a vector containing the unsigned value number of the instructions. All of the utilities are IR agnostic.</div><div class=""> </div><blockquote class="gmail_quote" style="margin: 0px 0px 0px 0.8ex; border-left-width: 1px; border-left-style: solid; border-left-color: rgb(204, 204, 204); padding-left: 1ex;"><div class="" style="word-wrap: break-word; line-break: after-white-space;"><div dir="auto" class="" style="word-wrap: break-word; line-break: after-white-space;">A few more remarks/questions are below also.</div><div dir="auto" class="" style="word-wrap: break-word; line-break: after-white-space;"><br class=""></div><div dir="auto" class="" style="word-wrap: break-word; line-break: after-white-space;">Thanks</div><div dir="auto" class="" style="word-wrap: break-word; line-break: after-white-space;">Gerolf</div><div dir="auto" class="" style="word-wrap: break-word; line-break: after-white-space;"><br class=""></div><div dir="auto" class="" style="word-wrap: break-word; line-break: after-white-space;"><div class=""><div class=""><div class="m_724739231848866907h5"><br class=""><blockquote type="cite" class=""><div class="">On Sep 5, 2017, at 4:16 PM, River Riddle via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank" class="">llvm-dev@lists.llvm.org</a>> wrote:</div><br class="m_724739231848866907m_8050443851449696450Apple-interchange-newline"><div class=""><div dir="ltr" class=""><span id="m_724739231848866907m_8050443851449696450gmail-docs-internal-guid-a13201fd-543a-33e0-60b3-3e86acafde79" class=""><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">Hey Everybody,</span></div><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"> A little while ago I posted an RFC(<a href="http://lists.llvm.org/pipermail/llvm-dev/2017-July/115666.html" target="_blank" class="">http://lists.llvm.org/pipe<wbr class="">rmail/llvm-dev/2017-July/11566<wbr class="">6.html</a>) with the proposition of adding a new outliner at the IR level. There was some confusion and many questions regarding the proposal which I’d like to address here:</span></div><p dir="ltr" class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"> </span></p><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">Note about nomenclature:</span></div><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"> Candidate: A repeated sequence of instructions within a module.</span></div><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"> Occurrence: One instance of a candidate sequence.</span></div><br class=""><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; font-weight: 700; vertical-align: baseline; white-space: pre-wrap;">-- Accompanied Graph Data -- </span></div><br class=""><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">Graph data is referenced in the sections below, any reference to Graph[*Number*] is referencing the numbered graph in the following document:</span></div><br class=""><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><a href="https://goo.gl/QDiVHU" target="_blank" class=""><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">https://goo.gl/QDiVHU</span></a></div><br class=""><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 12pt; font-family: "Times New Roman"; background-color: transparent; font-weight: 700; vertical-align: baseline; white-space: pre-wrap;">---- Performance ----</span></div><p dir="ltr" class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"> </span></p><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">I have tested the IR outliner and current Machine outliner on a wide variety of benchmarks. The results include total % reduction of both geomean and total size. It also includes individual results for each test in each respective benchmark.</span></div><p dir="ltr" class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"> </span></p><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"> The configurations tested are:</span></div><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">·</span><span class="" style="font-size: 7pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"> </span><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">Early+Late IR outlining</span></div><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">·</span><span class="" style="font-size: 7pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"> </span><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">Late IR outlining</span></div><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">·</span><span class="" style="font-size: 7pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"> </span><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">Machine outlining</span></div><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">·</span><span class="" style="font-size: 7pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"> </span><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">Early+Late+Machine outlining</span></div><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">·</span><span class="" style="font-size: 7pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"> </span><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">Late+Machine outlining</span></div><br class=""><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">NOTE: For fairness in comparisons with the Machine Outliner, all IR outliner runs also include (-mno-red-zone, outlining from linkonce_odr/weak_odr functions).</span></div><p dir="ltr" class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"> </span></p><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"> The code size benchmarking results provided are:</span></div><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">* LLVM Test Suite</span></div><ul class="" style="margin-top: 0pt; margin-bottom: 0pt;"><li dir="ltr" class="" style="list-style-type: circle; font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline;"><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">X86_64, X86*, AArch64, Arm1176jzf-s*, Arm1176jzf-s-thumb*</span></div></li></ul><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">* Spec 2006</span></div><ul class="" style="margin-top: 0pt; margin-bottom: 0pt;"><li dir="ltr" class="" style="list-style-type: circle; font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline;"><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">X86_64, X86*, AArch64, Arm1176jzf-s*, Arm1176jzf-s-thumb*</span></div></li></ul><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">* Clang</span></div><ul class="" style="margin-top: 0pt; margin-bottom: 0pt;"><li dir="ltr" class="" style="list-style-type: circle; font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline;"><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">X86_64(Mac OS) </span></div></li></ul><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">* llvm-tblgen</span></div><ul class="" style="margin-top: 0pt; margin-bottom: 0pt;"><li dir="ltr" class="" style="list-style-type: circle; font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline;"><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">X86_64(Mac OS) </span><span class="" style="font-size: 11pt; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"><span class="m_724739231848866907m_8050443851449696450gmail-Apple-tab-span" style="white-space: pre-wrap;"> </span></span></div></li></ul><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">* CSiBE</span></div><ul class="" style="margin-top: 0pt; margin-bottom: 0pt;"><li dir="ltr" class="" style="list-style-type: circle; font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline;"><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">AArch64</span></div></li></ul><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">* The machine outliner currently only supports X86_64 and AArch64.</span></div><p dir="ltr" class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"> </span></p><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">Full Code Size Results:</span></div><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><a href="https://goo.gl/ZBjHCG" target="_blank" class=""><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">https://goo.gl/ZBjHCG</span></a></div><p dir="ltr" class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"> </span></p><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 12pt; font-family: "Times New Roman"; background-color: transparent; font-weight: 700; vertical-align: baseline; white-space: pre-wrap;">--- Algorithmic differences with the Machine Outliner ----</span></div><br class=""><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"> </span><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"><span class="m_724739231848866907m_8050443851449696450gmail-Apple-tab-span" style="white-space: pre-wrap;"> </span></span><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">There was a lot of confusion on how exactly the algorithm I am proposing differs from what is available in the Machine Outliner. The similarities of the two outliners lie in the usage of a string matching algorithm and candidate pruning. The first step in the algorithm is to basically do the same common substring / pruning algorithm the post-RA MO uses but with a specially chosen congruence relation. I’d like to delve into the differences between the two:</span></div><p dir="ltr" class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"> </span></p><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; font-weight: 700; vertical-align: baseline; white-space: pre-wrap;">Congruence Detection:</span></div><p dir="ltr" class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"> </span></p><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">-</span><span class="" style="font-size: 7pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"> </span><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">Machine Outliner</span></div><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"> The machine outliner has the advantage of having this problem already taken care of by the register allocator, it simply checks to see if the two machine instructions are identical.</span></div><p dir="ltr" class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"> </span></p><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">-</span><span class="" style="font-size: 7pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"> </span><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">IR Outliner</span></div><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"> In the IR outliner we work on semantic equivalence, i.e. we care the operations being performed are equivalent and not the values. This creates a need to add verification that we do have exact equivalence when we need it, e.g. ShuffleVector’s shuffle mask, not taking the address of InlineASM, etc.</span></div><p dir="ltr" class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"> </span></p><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">A quick example of semantic equivalence:</span></div><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">%1 = add i32 1, i32 2</span></div><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">%2 = add i32 2, i32 3</span></div><p dir="ltr" class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"> </span></p><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">These two instructions are not identical because the values of the operands are not identical. They are, however, semantically equivalent because they both perform the add operation.</span></div><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">This can be seen by simply removing the operand values used in the calculations:</span></div><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">%1 = add i32 , i32</span></div><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">%2 = add i32 , i32</span></div><p dir="ltr" class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"> </span></p><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; font-weight: 700; vertical-align: baseline; white-space: pre-wrap;">Occurrence Verification:</span></div><p dir="ltr" class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; font-weight: 700; vertical-align: baseline; white-space: pre-wrap;"> </span></p><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">-</span><span class="" style="font-size: 7pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"> </span><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">Machine Outliner</span></div><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"> At the post RA level you don’t need to do any kind of special verification for candidate occurrences because you don’t have to deal with the concept of inputs.</span></div><p dir="ltr" class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"> </span></p><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">-</span><span class="" style="font-size: 7pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"> </span><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">IR Outliner</span></div><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"> At the IR/preRA level we need to do complex verification to make sure that the occurrences within a candidate have the same internal inputs. If two occurrences have different internal inputs then we need some form of control flow to maintain correctness. By internal inputs I mean the operands of instructions that come from an instruction within the occurrence, e.g.</span></div><p dir="ltr" class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"> </span></p><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">%2 = …</span></div><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">// Start outlining occurrence.</span></div><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">%3 = …</span></div><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">%4 = sub %3, %2 // The first operand is an internal input, the second is external.</span></div><p dir="ltr" class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"> </span></p><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">If there is any confusion about why we need control flow for internal inputs I am more than happy to provide examples and more detailed explanations.</span></div><p dir="ltr" class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"> </span></p><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">Aside from internal inputs we also need to verify that the functions we are outlining from have compatible attributes.</span></div><p dir="ltr" class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"> </span></p><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; font-weight: 700; vertical-align: baseline; white-space: pre-wrap;">Cost Modeling:</span></div><p dir="ltr" class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; font-weight: 700; vertical-align: baseline; white-space: pre-wrap;"> </span></p><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">-</span><span class="" style="font-size: 7pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"> </span><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">Machine Outliner</span></div><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">At the MIR level the cost information is extremely accurate. So cost modeling is composed of effectively counting the number of instructions and adding some frame/setup cost.</span></div><p dir="ltr" class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"> </span></p><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">-</span><span class="" style="font-size: 7pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"> </span><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">IR Outliner</span></div><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">At the IR level we are working with estimates for the costs of certain instructions. We try to match the IR cost to the MIR cost as closely as possible and in practice we can get fairly close(Graph[1]).</span></div><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"> Taking this a step further we need to estimate the cost/setup of having x amount of parameters and y outputs, as well as the register pressure from both the call and the potentially outlined function.</span></div><p dir="ltr" class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"> </span></p><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; font-weight: 700; vertical-align: baseline; white-space: pre-wrap;">Parameterization Optimizations:</span></div><p dir="ltr" class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; font-weight: 700; vertical-align: baseline; white-space: pre-wrap;"> </span></p><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">-</span><span class="" style="font-size: 7pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"> </span><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">Machine Outliner</span></div><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">The Machine outliner uses exact equivalence, which does not allow for any form of parameterization.</span></div><p dir="ltr" class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"> </span></p><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">-</span><span class="" style="font-size: 7pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"> </span><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">IR Outliner</span></div><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"> </span><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"><span class="m_724739231848866907m_8050443851449696450gmail-Apple-tab-span" style="white-space: pre-wrap;"> </span></span><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">Being at the IR level requires us to tackle parameterization, which then brings several optimizations to help lower the cost of parameterizing a sequence.</span></div><p dir="ltr" class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"> </span></p><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">* Constant Folding</span></div><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"> </span><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"><span class="m_724739231848866907m_8050443851449696450gmail-Apple-tab-span" style="white-space: pre-wrap;"> </span></span><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">The IR outliner will identify constant inputs and fold them.</span></div><p dir="ltr" class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"> </span></p><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">* Congruent Input Condensing</span></div><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"> </span><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"><span class="m_724739231848866907m_8050443851449696450gmail-Apple-tab-span" style="white-space: pre-wrap;"> </span></span><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">The outliner identifies the congruent sets of parameters for a function. Example:</span></div><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"> </span><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"><span class="m_724739231848866907m_8050443851449696450gmail-Apple-tab-span" style="white-space: pre-wrap;"> </span></span><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">void fn(int, int); -> void fn(int);</span></div><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"> </span><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"><span class="m_724739231848866907m_8050443851449696450gmail-Apple-tab-span" style="white-space: pre-wrap;"> </span></span><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">fn(1, 1); </span><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"><span class="m_724739231848866907m_8050443851449696450gmail-Apple-tab-span" style="white-space: pre-wrap;"> </span></span><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">-> fn(1);</span></div><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"> </span><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"><span class="m_724739231848866907m_8050443851449696450gmail-Apple-tab-span" style="white-space: pre-wrap;"> </span></span><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">fn(%1, %1); </span><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"><span class="m_724739231848866907m_8050443851449696450gmail-Apple-tab-span" style="white-space: pre-wrap;"> </span></span><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">-> fn(%1);</span></div><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">Parameters 1 and 2 were found to be the same for each callsite of the function, so we condensed the congruent parameters.</span></div><p dir="ltr" class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"> </span></p><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">* Input Partitioning</span></div><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"> </span><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"><span class="m_724739231848866907m_8050443851449696450gmail-Apple-tab-span" style="white-space: pre-wrap;"> </span></span><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">The outliner partitions candidates that have a parameter that can be constant folded. Example:</span></div><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"> </span><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"><span class="m_724739231848866907m_8050443851449696450gmail-Apple-tab-span" style="white-space: pre-wrap;"> </span></span><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">fn(1);</span></div><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"> </span><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"><span class="m_724739231848866907m_8050443851449696450gmail-Apple-tab-span" style="white-space: pre-wrap;"> </span></span><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">fn(1);</span></div><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"> </span><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"><span class="m_724739231848866907m_8050443851449696450gmail-Apple-tab-span" style="white-space: pre-wrap;"> </span></span><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">fn(%1);</span></div><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">Occurrences 1 and 2 in the above candidate can have parameter 1 folded. We create a new candidate containing just occurrences 1 and 2 as it may be more profitable than the original candidate.</span></div><p dir="ltr" class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"> </span></p><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">* Constant int condensing</span></div><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"> </span><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"><span class="m_724739231848866907m_8050443851449696450gmail-Apple-tab-span" style="white-space: pre-wrap;"> </span></span><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">The outliner identifies constant int parameters and checks to see if, for each occurrence, they are an equal distance from other constant int parameters. If so it removes all but one of the parameters and represents the others as an add from the base. Example:</span></div><p dir="ltr" class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"> </span></p><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"> </span><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"><span class="m_724739231848866907m_8050443851449696450gmail-Apple-tab-span" style="white-space: pre-wrap;"> </span></span><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">void fn(int a, int b);</span></div><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"> </span><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"><span class="m_724739231848866907m_8050443851449696450gmail-Apple-tab-span" style="white-space: pre-wrap;"> </span></span><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">fn(1, 2);</span></div><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"> </span><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"><span class="m_724739231848866907m_8050443851449696450gmail-Apple-tab-span" style="white-space: pre-wrap;"> </span></span><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">fn(3, 4);</span></div><p dir="ltr" class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"> </span></p><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">In the above, parameters 1 and 2 are always a distance of 1 apart. We can redefine our function as:</span></div><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"> </span><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"><span class="m_724739231848866907m_8050443851449696450gmail-Apple-tab-span" style="white-space: pre-wrap;"> </span></span><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">void fn(int a) {</span></div><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"> </span><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"><span class="m_724739231848866907m_8050443851449696450gmail-Apple-tab-span" style="white-space: pre-wrap;"> </span></span><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"> int b = a + 1;</span></div><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"> </span><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"><span class="m_724739231848866907m_8050443851449696450gmail-Apple-tab-span" style="white-space: pre-wrap;"> </span></span><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"> …</span></div><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"> </span><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"><span class="m_724739231848866907m_8050443851449696450gmail-Apple-tab-span" style="white-space: pre-wrap;"> </span></span><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">}</span></div><p dir="ltr" class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"> </span></p><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; font-weight: 700; vertical-align: baseline; white-space: pre-wrap;">Register Usage:</span></div><br class=""><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">-</span><span class="" style="font-size: 7pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"> </span><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">Machine Outliner</span></div><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">The MO works post RA with exact equivalence, so the most it will compute is if it needs to save the link register on arm64.</span></div><p dir="ltr" class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"> </span></p><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">-</span><span class="" style="font-size: 7pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"> </span><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">IR Outliner</span></div><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">The IR outliner needs to compute register usage for the new outlined function as well as the usage after generating a function call with x parameters and y outputs at each program point z.</span></div><p dir="ltr" class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"> </span></p><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; font-weight: 700; vertical-align: baseline; white-space: pre-wrap;">Outlining:</span></div><p dir="ltr" class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; font-weight: 700; vertical-align: baseline; white-space: pre-wrap;"> </span></p><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">-</span><span class="" style="font-size: 7pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"> </span><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">Machine Outliner</span></div><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"> </span><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"><span class="m_724739231848866907m_8050443851449696450gmail-Apple-tab-span" style="white-space: pre-wrap;"> </span></span><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">At the MIR level we clone the outlined instructions into a new function, create some prologue/epilogue for the function, and then generate a call.</span></div><p dir="ltr" class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"> </span></p><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">-</span><span class="" style="font-size: 7pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"> </span><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">IR Outliner</span></div><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"> </span><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"><span class="m_724739231848866907m_8050443851449696450gmail-Apple-tab-span" style="white-space: pre-wrap;"> </span></span><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">At the IR level we also have to handle the parameters/outputs of the candidate. Here we need to merge all of the metadata of outlined instructions/outlined functions. We also need to identify congruent sets of parameters between call sites and then folding the amount of parameters that are needed for the call.</span></div><p dir="ltr" class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"> </span></p><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; font-weight: 700; vertical-align: baseline; white-space: pre-wrap;">Suffix Array vs Suffix Tree+LCP:</span></div><br class=""><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"> </span><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"><span class="m_724739231848866907m_8050443851449696450gmail-Apple-tab-span" style="white-space: pre-wrap;"> </span></span><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">The two structures should compute the same result, but there is a non obvious benefit that we get from the suffix array. With the suffix array approach we identify candidates that shares common occurrences albeit with a different length. This is very useful for complex verification/analysis, e.g. at the IR or pre RA level. This allows us to cache the work when we calculating inputs or verifying the internal inputs of occurrences. Although this won't be an issue if/when we switch to a common interface for candidate selection.</span></div><p dir="ltr" class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"> </span></p><p dir="ltr" class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"> </span></p><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 12pt; font-family: "Times New Roman"; background-color: transparent; font-weight: 700; vertical-align: baseline; white-space: pre-wrap;">---- A replacement for the Machine Outliner? Not exactly ----</span></div><p dir="ltr" class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 12pt; font-family: "Times New Roman"; background-color: transparent; font-weight: 700; vertical-align: baseline; white-space: pre-wrap;"> </span></p><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">The IR outliner was never intended as a replacement for the machine outliner and the two can coexist. The outliners tend to catch very different cases: the machine outliner tends to favor very small candidate lengths. Using a build of llvm-tblgen, the machine outliner gets ~52% of its benefit from outlined functions of 2-3 instructions. The IR outliner tends to favor large candidate lengths(2-20+), often composed of function calls. 52% of the benefit for the IR outliner in the llvm-tblgen example is found in outlined functions with final lengths up to 17. Data for example runs of both can be found in the graph data file and is summarized in Graph[2].</span></div><p dir="ltr" class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"> </span></p><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"> Included in the performance data are metrics showing the performance of using both the IR outliner and machine outliner. The data indicates that you can achieve up to, and exceed, 2% reduction of both geomean and total size by using both. </span></div><p dir="ltr" class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"> </span></p><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 12pt; font-family: "Times New Roman"; background-color: transparent; font-weight: 700; vertical-align: baseline; white-space: pre-wrap;">---- Pros/Cons of IR----</span></div><br class=""><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">The current algorithm is implemented at the IR level, but there are trade offs to placing this transformation anywhere in the pipeline(IR/preRa/postRA).</span></div><p dir="ltr" class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"> </span></p><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">-- Less Precise Cost Modeling:</span></div><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"> Being at the IR level creates a need to estimate the size cost of any given instruction.</span></div><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">- How much does this imprecision affect the benefit estimation?</span></div><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">- Included in the data : Graph[1]: is the difference between our estimated function size and the actual size in the binary. It shows that we get very close and tend to be on the conservative side.</span></div><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">- Estimation causes the IR outliner to be conservative. Which means that we are losing out on potential benefit by overestimating cost.</span></div><br class=""><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">-- Higher Level of Abstraction:</span></div><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">- The outliners are essentially string matching algorithms. Being at a higher level of abstraction naturally gives more opportunities for equivalence. As an example, call instructions are handled naturally at the IR level.</span></div><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">- Will a preRA outliner be able to have the same relaxation in congruence matching? E.g will it be able to match tail and non tail function calls?</span></div><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">- Being at the IR level means that we lose out on some instruction lowering idioms, e.g. constant expressions, bitwise rotation([shl, lshr, or] -> [rot]), etc.</span></div><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt; margin-left: 36pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">- This is evident in the results for test suite for aarch64, in which the machine outliner outperforms the IR outliner due in part to the large amount of global accesses in the tests.</span></div><br class=""><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">-- Maintainability:</span></div><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">- The IR level in general is much more maintainable.</span></div></span></div></div></blockquote></div></div>Why so? How did you measure that? What is your measure for “maintainable?"</div></div></div></blockquote><div class=""><br class=""></div><div class="">The IR level, currently, has much better documentation, is more mature, and AFAIK most developers are familiar with it. It's definitely subjective to some degree. </div><div class=""> </div><blockquote class="gmail_quote" style="margin: 0px 0px 0px 0.8ex; border-left-width: 1px; border-left-style: solid; border-left-color: rgb(204, 204, 204); padding-left: 1ex;"><div class="" style="word-wrap: break-word; line-break: after-white-space;"><div dir="auto" class="" style="word-wrap: break-word; line-break: after-white-space;"><div class=""><span class=""><br class=""><blockquote type="cite" class=""><div class=""><div dir="ltr" class=""><span id="m_724739231848866907m_8050443851449696450gmail-docs-internal-guid-a13201fd-543a-33e0-60b3-3e86acafde79" class=""><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">- We don’t have to be as conservative about certain ABI characteristics. This allows for the IR outliner to work without the need for any extra work(special options) from the users. For example, the machine outliner requires ‘noredzone’ but the IR outliner does not. </span></div><br class=""><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">-- Pipeline Flexibility:</span></div><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">- As shown in the performance data below, we can get up to 2x performance by working pre function simplification. Though working pre simplification means the outliner must gamble between the benefits of outlining vs simplification.</span></div><br class=""><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">-- Loss of control:</span></div><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">- The machine level can have more control over the outlining process. We could have optimized parameterization, alignment handling, etc.</span></div><p dir="ltr" class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"> </span></p><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 12pt; font-family: "Times New Roman"; background-color: transparent; font-weight: 700; vertical-align: baseline; white-space: pre-wrap;">---- Adapting the algorithm to pre-RA IR ----</span></div><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">The analysis portion of the IR outliner is already IR agnostic for the most part. It works on indices into the congruency vector for instructions and their inputs/outputs. This would mean that a preRA outliner would only have to define the MIR specific portions: Congruency detection, cost analysis, parameter/output optimizations, and the outlining of beneficial candidates.</span></div></span></div></div></blockquote></span>That should apply the other way around too: take the MO outliner and adapt. No?</div></div></div></blockquote><div class=""><br class=""></div><div class="">This is one of the things that the comparison helps to illustrate. If you take the utilities that I mentioned above and port the current MO outliner to use them, the resultant file is < 300 lines. It works on exact equivalence, so all of the interesting parts of the algorithm, besides legality detection and frame cost, are already taken care of by register allocation. The only remaining parts are the value numbering and outlining, but those are IR specific and have to be rewritten anyways.</div></div></div></div></div></blockquote><div class=""><br class=""></div>Is this how you propose to move forward with the commit? Start with the utilities, then work with Jessica on the MO port, and finally work on IR equivalence, signatures etc.? This would seem like a sensitive approach to me, build upon what is there already and thus demonstrate the robustness of the new framework<br class=""><blockquote type="cite" class=""><div class=""><div dir="ltr" class=""><div class="gmail_extra"><div class="gmail_quote"><div class=""> </div><div class=""> The IR implementation started at roughly this point, but exact equivalence at the IR level doesn't really amount to much. This outliner adds the logic for verification/analysis/optimization for when we don't have exact equivalence. It's better to start from here because these are the real problems that are going to have to be solved if an outliner is to exist anywhere other than post RA.</div></div></div></div></div></blockquote><div class=""><br class=""></div>I understand your urge since the problems are hard and interesting, but they are also solvable. Sharing (big) parts of the source base among the outliners reduces maintenance overhead. This is easier to achieve when tackled from the start. <br class=""><blockquote type="cite" class=""><div class=""><div dir="ltr" class=""><div class="gmail_extra"><div class="gmail_quote"><div class=""><br class=""></div><div class="">Thanks,</div><div class=""> River Riddle</div><div class=""><br class=""></div><div class=""> </div><blockquote class="gmail_quote" style="margin: 0px 0px 0px 0.8ex; border-left-width: 1px; border-left-style: solid; border-left-color: rgb(204, 204, 204); padding-left: 1ex;"><div class="" style="word-wrap: break-word; line-break: after-white-space;"><div dir="auto" class="" style="word-wrap: break-word; line-break: after-white-space;"><div class=""><blockquote type="cite" class=""><div class=""><span class=""><div dir="ltr" class=""><span id="m_724739231848866907m_8050443851449696450gmail-docs-internal-guid-a13201fd-543a-33e0-60b3-3e86acafde79" class=""><br class=""><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; font-weight: 700; vertical-align: baseline; white-space: pre-wrap;">-- Implementation -- </span></div><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><a href="https://github.com/River707/llvm/blob/outliner/lib/Transforms/IPO/CodeSizeOutliner.cpp" target="_blank" class=""><span class="" style="font-size: 11pt; font-family: Arial; vertical-align: baseline; white-space: pre-wrap;">https://github.com/River707/ll<wbr class="">vm/blob/outliner/lib/Transform<wbr class="">s/IPO/CodeSizeOutliner.cpp</span></a></div><br class=""><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">All feedback/comments/discussion welcome and appreciated!</span></div><br class=""><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;">Thanks,</span></div><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"> River Riddle</span></div><div class=""><span class="" style="font-size: 11pt; font-family: "Times New Roman"; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;"><br class=""></span></div></span></div></span>______________________________<wbr class="">_________________<br class="">LLVM Developers mailing list<br class=""><a href="mailto:llvm-dev@lists.llvm.org" target="_blank" class="">llvm-dev@lists.llvm.org</a><br class=""><a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" target="_blank" class="">http://lists.llvm.org/cgi-bin/<wbr class="">mailman/listinfo/llvm-dev</a><br class=""></div></blockquote></div><br class=""></div></div></blockquote></div><br class=""></div></div></div></blockquote></div><br class="" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px;"><span style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; float: none; display: inline !important;" class="">_______________________________________________</span><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class=""><span style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; float: none; display: inline !important;" class="">LLVM Developers mailing list</span><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class=""><span style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; float: none; display: inline !important;" class=""><a href="mailto:llvm-dev@lists.llvm.org" class="">llvm-dev@lists.llvm.org</a></span><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class=""><span style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; float: none; display: inline !important;" class=""><a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" class="">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a></span></div></blockquote></div><br class=""></div></body></html>