<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">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:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div class="gmail_extra"><div class="gmail_quote"><span class=""><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;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:0 0 0 .8ex;border-left:1px #ccc solid;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:0 0 0 .8ex;border-left:1px #ccc solid;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></div></div></blockquote><div>In particular, Quentin has not actually shown that every possible DFG can be generated by SSA IR (without affecting the time/space class) , or that every possible DFG can be converted to SSA IR (ditto).</div><div>While i believe the latter is possible (Though SSA is not a linear space transform, even though it is a linear time one. I believe it is at worst an N^2 transform, and not an exponential space one), i'm significantly less sure about the former, and it seems quite wrong to me without thinking about it too hard.</div><div>(it seems it would imply SSA is a lot more powerful than it is).</div><div><br></div><div>I'm also pretty sure i've seen papers that prove the former is false.</div><div><br></div><div><br></div><div><br></div></div></div></div>