<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: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-"><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><div>Only one direction is needed to prove it is GI-hard. I think you are thinking about proving it GI-complete. Solving a GI-hard problem in polynomial time proves that GI is in P which would be a major breakthrough in CS.</div><div> </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="ltr"><div class="gmail_extra"><div class="gmail_quote"><span class="gmail-"><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">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"><br></div></div></div></blockquote><div><br></div></span><div>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> <br></div><div>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><br></div><div>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></div></div></blockquote><div><br></div><div>Can you explain what structure SSA imbues besides just modeling a dag? The description I gave above is phrased solely in terms of a data flow graph (dag of say `add` instructions) in a single BB; there are no phi nodes or anything.</div><div><br></div><div>I'm thinking something like:</div><div><br></div><div>For each vertex v (with label %foo) in the dag in topological order:</div><div> append to the BB an instruction `add  %foo <- %bar, %baz, %qux, ...` where `%bar, %baz, %qux, ...` are the labels of all instructions u such that an edge u->v exists.</div><div><br></div><div>The BB generated this way is guaranteed to be SSA.<br></div><div><br></div><div>(for simplicity I've assumed an N-ary add instruction, but it is obvious you can isomorphically desugar that into two-operand instructions)</div><div><br></div><div><br></div><div>  </div><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="ltr"><div class="gmail_extra"><div class="gmail_quote"><div><br></div><div>So with all due respect to quentin, i don't buy it yet.</div><div><br></div><div>Without more, i'd bet using similar techniques to solve value numbering in polynomial time to SSA could be applied here.</div><div><br></div><div>This is because the complete polynomial value numbering techniques are in fact, value graph isomorphism ....</div></div></div></div></blockquote><div><br></div><div>My understanding is that standard complete GVN algorithms are looking for:<br></div><div><br></div><div><div>%0 = ...</div><div>add %1 <- %0, %0</div><div>add %2 <- %1, %1</div><div>add %3 <- %2, %2</div><div>...</div></div><div><div>add %1 <- %0, %0</div><div>add %2 <- %1, %1</div><div>add %3 <- %2, %2</div><div>...</div></div><div><br></div><div>and identifying the repeated</div><div>```</div><div>add %1 <- %0, %0</div><div>add %2 <- %1, %1</div><div>add %3 <- %2, %2</div><div>```</div><div><br></div><div><br></div><div>However, a code folding outliner like the one discussed here wants to be able to identify the two sequences as equivalent even if the second run of adds doesn't start with %0 is as an input.</div><div><br></div><div><div><div>%0 = ...</div><div>add %1 <- %0, %0</div><div>add %2 <- %1, %1</div><div>add %3 <- %2, %2</div><div>...</div></div><div>%foo0 = ...</div><div><div>add %foo1 <- %foo0, %foo0</div><div>add %foo2 <- %foo1, %foo1</div><div>add %foo3 <- %foo2, %foo2</div><div>...</div></div></div><div><br></div><div>A code folding outliner wants to find:</div><div><br></div><div>outlinedFunc(%arg) {</div><div><div>add %1 <- %arg, %arg</div><div>add %2 <- %1, %1</div><div>add %3 <- %2, %2</div></div><div>}</div><div><br></div><div>In other words, I think the algorithms you are thinking of prove equivalent *values* whereas what the code folding outliner is looking for is equivalent *computations* (which may have different inputs at the different sites they occur and so do not necessarily have identical values at run time). For example, %3 and %foo3 have different values at runtime.</div><div><br></div><div>As another example</div><div><br></div><div>%0 = ...</div><div>add %1 <- %0, %0</div><div>mul %2 <- %1, %1</div><div>add %3 <- %2, %2</div><div><br></div><div><div>%foo0 = ...</div><div>add %foo1 <- %foo0, %foo0</div><div>mul %foo2 <- %foo1, %foo1</div></div><div><br></div><div><div>%bar1 = ...</div><div>mul %bar2 <- %bar1, %bar1</div><div>add %bar3 <- %bar2, %bar2</div></div><div><br></div><div>The algorithm we want for the code folding outliner should identify that</div><div>```</div><div><div>add %1 <- %0, %0</div><div>mul %2 <- %1, %1</div></div><div>```</div><div>is the same computation as the `foo` computation</div><div>and</div><div>```</div><div><div>mul %2 <- %1, %1</div><div>add %3 <- %2, %2</div></div><div>```</div><div>is the same computation as the `bar` computation.</div><div><br></div><div><br></div><div><br></div><div>Or to put it yet another way, if you have:</div><div><div><div><br></div><div>foo(a,b,c) {</div><div> a single BB with data flow graph G</div><div>}</div><div><br></div><div>bar(d,e,f) {</div><div> a single BB with a graph isomorphic to G subject to d=b e=a c=f<br>}</div><div><br></div><div>This is easy to do with a standard VN algorithm if you knew a priori knew d=b e=a c=f and just initialized the initial congruence classes right. The hard part manifests itself I think in terms of discovering that correspondence. (and in general the number of such live-in values to the subgraphs being compared is O(the size of the graph), so the algorithm must be polynomial in the number of such live-in values).</div></div><div><br></div><div>How does the algorithm you are thinking of infer the equivalence of those live-in values?</div></div><div><br></div><div><br></div><div><br></div><div>Sorry for really digging in here, but I've actually thought about this a lot since we talked about this at the social and I can't seem to find a problem with my reasoning for the GI-hard proof and am genuinely curious.</div><div><br></div><div>-- Sean Silva</div><div><br></div><div> </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="ltr"><div class="gmail_extra"><div class="gmail_quote"><div><br></div><div>So i'd assume the opposite (it can be done in polynomial time) without more.</div><div><br></div><div><br></div></div></div></div>
</blockquote></div><br></div></div>