<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Tue, Aug 1, 2017 at 12:28 PM, Sean Silva <span dir="ltr"><<a href="mailto:chisophugis@gmail.com" target="_blank">chisophugis@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote"><span class="gmail-">On Tue, Aug 1, 2017 at 10:28 AM, Daniel Berlin <span dir="ltr"><<a href="mailto:dberlin@dberlin.org" target="_blank">dberlin@dberlin.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div class="gmail_extra"><div class="gmail_quote"><span class="gmail-m_143766248308552232gmail-"><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="auto"><div dir="auto"><div dir="auto" style="font-family:sans-serif"><br></div><div dir="auto" style="font-family:sans-serif"><br></div><div dir="auto" style="font-family:sans-serif">Also as a side note, I think in the original MachineOutliner RFC thread there was some confusion as to whether it was possible to solve the code folding outlining problem exactly as a graph problem on SSA using standard value numbering algorithms in polynomial time.</div></div></div></blockquote><div> <br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="auto"><div dir="auto"><div dir="auto" style="font-family:sans-serif"> I can elaborate further, but</div><div dir="auto" style="font-family:sans-serif">1. it is easy to see that you can map an arbitrary dag to an isomorphic data flow graph in an SSA IR e.g. in LLVM IR or pre-RA MIR</div></div></div></blockquote><div> <br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="auto"><div dir="auto"><div dir="auto" style="font-family:sans-serif">2. Given two dags, you can create their respective isomorphic data flow graphs (say, put them into two separate functions)</div><div dir="auto" style="font-family:sans-serif">3. An exact graph based code folding outliner would be able to discover if the two dataflow graphs are isomorphic (that is basically what I mean by exact) and outline them.</div><div dir="auto" style="font-family:sans-serif">4. Thus, graph isomorphism on dags can be solved with such an algorithm and thus the outlining problem is GI-hard and a polynomial time solution would be a big breakthrough in CS.</div></div></div></blockquote><div><br></div></span><div>First, you'd have to reduce them in both directions to prove that ;)</div><div><br></div><div>All that's been shown is that you can reduce it to a hard problem.</div><div>You can also reduce it to 3-sat., but that doesn't mean anything unless you can reduce 3-sat to it.</div></div></div></div></blockquote><div><br></div></span><div>Only one direction is needed to prove it is GI-hard.</div></div></div></div></blockquote><div><br></div><div>Yes sorry, but you still haven't done it. </div><div>So if you really want to do it, let's start with a definition:<br><br></div><div>"<span style="color:rgb(36,39,41);font-family:Arial,"Helvetica Neue",Helvetica,sans-serif;font-size:15px">The precise definition here is that </span><em style="margin:0px;padding:0px;border:0px;font-variant-numeric:inherit;font-stretch:inherit;font-size:15px;line-height:inherit;font-family:Arial,"Helvetica Neue",Helvetica,sans-serif;vertical-align:baseline;color:rgb(36,39,41)">a problem <code style="margin:0px;padding:1px 5px;border:0px;font-style:inherit;font-variant:inherit;font-weight:inherit;font-stretch:inherit;font-size:13px;line-height:inherit;font-family:Consolas,Menlo,Monaco,"Lucida Console","Liberation Mono","DejaVu Sans Mono","Bitstream Vera Sans Mono","Courier New",monospace,sans-serif;vertical-align:baseline;background-color:rgb(239,240,241);white-space:pre-wrap">X</code> is NP-hard, if there is an NP-complete problem <code style="margin:0px;padding:1px 5px;border:0px;font-style:inherit;font-variant:inherit;font-weight:inherit;font-stretch:inherit;font-size:13px;line-height:inherit;font-family:Consolas,Menlo,Monaco,"Lucida Console","Liberation Mono","DejaVu Sans Mono","Bitstream Vera Sans Mono","Courier New",monospace,sans-serif;vertical-align:baseline;background-color:rgb(239,240,241);white-space:pre-wrap">Y</code>, such that <code style="margin:0px;padding:1px 5px;border:0px;font-style:inherit;font-variant:inherit;font-weight:inherit;font-stretch:inherit;font-size:13px;line-height:inherit;font-family:Consolas,Menlo,Monaco,"Lucida Console","Liberation Mono","DejaVu Sans Mono","Bitstream Vera Sans Mono","Courier New",monospace,sans-serif;vertical-align:baseline;background-color:rgb(239,240,241);white-space:pre-wrap">Y</code> is reducible to <code style="margin:0px;padding:1px 5px;border:0px;font-style:inherit;font-variant:inherit;font-weight:inherit;font-stretch:inherit;font-size:13px;line-height:inherit;font-family:Consolas,Menlo,Monaco,"Lucida Console","Liberation Mono","DejaVu Sans Mono","Bitstream Vera Sans Mono","Courier New",monospace,sans-serif;vertical-align:baseline;background-color:rgb(239,240,241);white-space:pre-wrap">X</code> in polynomial time</em><span style="color:rgb(36,39,41);font-family:Arial,"Helvetica Neue",Helvetica,sans-serif;font-size:15px">."<br></span></div><div class="gmail_quote"><br></div>For this to be GI-hard you must be able to reduce *every* GI problem to one about SSA-based outlining, and you must be able to do so in *polynomial time*.</div><div class="gmail_quote"> <br></div><div class="gmail_quote">The above does not do this.</div><div class="gmail_quote"><br></div><div class="gmail_quote">Things that would need proof:<br><br></div><div class="gmail_quote">1. <span style="font-family:sans-serif">it is easy to see that you can map an arbitrary dag to an isomorphic data flow graph in an SSA IR e.g. in LLVM IR or pre-RA MIR</span></div><div class="gmail_quote"><span style="font-family:sans-serif"><br></span></div><div class="gmail_quote"><span style="font-family:sans-serif">A routine or proof to do this in polynomial time ;)  Please make sure you do an arbitrary dag, and not just rooted DAGs, as isomorphism on rooted DAGs can be solved in linear time ;)</span></div><div class="gmail_quote"><span style="font-family:sans-serif"><br></span></div><div class="gmail_quote"><br></div><div class="gmail_quote"><font face="sans-serif">3. i</font><span style="font-family:sans-serif">n exact graph based code folding outliner would be able to discover if the two dataflow graphs are isomorphic (that is basically what I mean by exact) and outline them.</span></div><div class="gmail_quote"><span style="font-family:sans-serif"><br></span></div><div class="gmail_quote"><span style="font-family:sans-serif">Proof that  code outlining necessarily requires discovering full isomorphism between the graphs.</span></div><div class="gmail_quote"><span style="font-family:sans-serif"><br></span></div><div class="gmail_quote"><span style="font-family:sans-serif">(IE that whatever process code outlining uses must end up doing a thing that would prove isomorphism).</span></div><div class="gmail_quote"><br>Keep in mind that the way we ended up with linear time dataflow was precisely to prove that it did not actually require doing things that reduced to boolean matrix multiplication</div><div class="gmail_quote"><br></div><div class="gmail_quote"><br></div><div class="gmail_quote">But let's take this offline, as it's going to go into a very theoretical route.</div><div class="gmail_quote"><br></div><div class="gmail_quote">I would suggest reading some of the very early papers. Early value numbering, and complete formulations, assume uninterpreted operators and in some cases, operands.  There is also the distinction between whether you are trying to discover the set of equivalent values that already exist in the program vs things that are equivalent to those values vs ....</div><div class="gmail_quote"><br></div><div class="gmail_quote">It's 100% possible to come up with formulations of VN that are still exponential time depending precisely on the details you are giving.</div><div class="gmail_quote"><br></div><div class="gmail_quote">It's also interesting to note that Babai still has his paper on graph isomorphism in quasi-polynomial time, and nobody has found holes in it yet (and since it's in NP but not NP complete, it's little more believable than the standard P = NP fair)</div><div class="gmail_quote"><br></div></div></div>