<html><head><meta http-equiv="Content-Type" content="text/html charset=utf-8"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><br class=""><div><blockquote type="cite" class=""><div class="">On Aug 1, 2017, at 10:28 AM, Daniel Berlin 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 dir="ltr" class=""><div class="gmail_extra"><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="auto" class=""><div dir="auto" class=""><div dir="auto" style="font-family:sans-serif" class=""><br class=""></div><div dir="auto" style="font-family:sans-serif" class=""><br class=""></div><div dir="auto" style="font-family:sans-serif" class="">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 class=""> <br class=""></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="auto" class=""><div dir="auto" class=""><div dir="auto" style="font-family:sans-serif" class=""> I can elaborate further, but</div><div dir="auto" style="font-family:sans-serif" class="">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 class=""> <br class=""></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="auto" class=""><div dir="auto" class=""><div dir="auto" style="font-family:sans-serif" class="">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" class="">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" class="">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 class=""><br class=""></div><div class="">First, you'd have to reduce them in both directions to prove that ;)</div><div class=""><br class=""></div><div class="">All that's been shown is that you can reduce it to a hard problem.</div><div class="">You can also reduce it to 3-sat., but that doesn't mean anything unless you can reduce 3-sat to it.</div><div class=""><br class=""></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="auto" class=""><div dir="auto" class=""><div dir="auto" style="font-family:sans-serif" class="">5. The actual problem the outliner is trying to solve is actually more like finding subgraphs that are isomorphic, making the problem even harder (something like "given dags A and B does there exist a subgraph of A that is isomorphic to a subgraph of B")</div><div dir="auto" style="font-family:sans-serif" class=""><br class=""></div></div></div></blockquote><div class=""><br class=""></div><div class="">This assumes, strongly, that this reduction is the way to do it, and also that SSA/etc imparts no structure in the reduction that enables you to solve it faster (IE restricts the types of graphs, etc)</div><div class=""> <br class=""></div><div class="">FWIW, the exact argument above holds for value numbering, and since the days of kildall, it was believed not solvable in a complete fashion in less than exponential time due to the need to do graph isomorphism on large value graphs at join points.</div><div class=""><br class=""></div><div class="">Except, much like RA and other things, it turns out this is not right for SSA, and in the past few years, it was proved you could do complete value numbering in polynomial time on SSA.</div><div class=""><br class=""></div><div class="">So with all due respect to quentin, i don't buy it yet.</div></div></div></div></div></blockquote><div><br class=""></div><div>FWIW, I didn’t make any claim on actual complexity (I think? :)). We just didn't try it and didn’t have time to fit that into the schedule of an outliner for an internship.</div><div><br class=""></div>What I am saying is that I am not responsible of how people quote me :).</div><div><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="">Without more, i'd bet using similar techniques to solve value numbering in polynomial time to SSA could be applied here.</div><div class=""><br class=""></div><div class="">This is because the complete polynomial value numbering techniques are in fact, value graph isomorphism ....</div><div class=""><br class=""></div><div class="">So i'd assume the opposite (it can be done in polynomial time) without more.</div></div></div></div></div></blockquote><div><br class=""></div><div>I would believe so FWIW.</div><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=""><br class=""></div></div></div></div>
_______________________________________________<br class="">LLVM Developers mailing list<br class=""><a href="mailto:llvm-dev@lists.llvm.org" class="">llvm-dev@lists.llvm.org</a><br class="">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev<br class=""></div></blockquote></div><br class=""></body></html>