<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>