<html><head><style type='text/css'>p { margin: 0; }</style></head><body><div style='font-family: arial,helvetica,sans-serif; font-size: 10pt; color: #000000'><br><hr id="zwchr"><blockquote style="border-left: 2px solid rgb(16, 16, 255); margin-left: 5px; padding-left: 5px; color: rgb(0, 0, 0); font-weight: normal; font-style: normal; text-decoration: none; font-family: Helvetica,Arial,sans-serif; font-size: 12pt;"><b>From: </b>"Daniel Berlin" <dberlin@dberlin.org><br><b>To: </b>"Hal Finkel" <hfinkel@anl.gov><br><b>Cc: </b>"Andrey Bokhanko" <andreybokhanko@gmail.com>, "llvm-dev" <llvm-dev@lists.llvm.org><br><b>Sent: </b>Wednesday, August 31, 2016 7:02:57 PM<br><b>Subject: </b>Re: [llvm-dev] [RFC] Interprocedural MIR-level outlining pass<br><br><div dir="ltr">(and in particular, the definition of equivalence used by code folding to make the dags is STH like "two VNDAG expressions are equivalent if their operands come from VNDAG expressions with the same opcode")<div><br></div><div>Thus,</div><div><br></div><div>VN2 = VN0 + VN1</div><div>VN3 = VN1 + VN2<br></div><div><br></div><div>is considered equivalent to</div><div><br></div><div>VN2 = VN0 + VN5</div><div>VN3 = VN1 + VN2</div><div><br></div><div>Despite the fact that this is completely illegal for straight redundancy elimination.</div><div><br></div><div><br></div><div id="DWT11869">But again, as I said if y'all want to make a pass that basically generates a new type of expression DAG, have fun :)</div></div></blockquote>I don't think that anyone wants to do anything unnecessary, or re-invent any wheels. I'm just trying to understand what you're saying.<br><br>Regarding you example above, I certainly see how you might do this simply by defining an equivalence class over all "external" inputs. I don't think this is sufficient, however, for what is needed here. The problem is that we need to recognize maximal structurally-similar subgraphs, and I don't see how what you're proposing does that (even if you have some scheme where you don't hash every part of each instruction). Maybe if you had some stream-based similarity-preserving hash function, but that's another matter.<br><br>Let's say we have this:<br><br>q = a + b<br>r = c + d<br>s = q + r<br>t = q - r<br><br>and later we have:<br><br>u = e + f<br>v = g - h<br>w = u + v<br>x = u - v<br><br>Now, what I want to recognize is that the latter two instructions in each group are structurally similar. Even if I define an equivalence class over external inputs, in this case, E = { a, b, c, d, e, f, g, h}, then I have:<br><br>q = E + E<br>
r = E + E<br>
s = q + r<br>
t = q - r<br><br>and:<br><br>u = E + E<br>
v = E - E<br>
w = u + v<br>
x = u - v<br><br>but then r and v are still different, so how to we find that {s, t} can be abstracted into a function, because we've found the isomorphism { s -> w, t -> x }, and then thus reuse that function to evaluate {w, x}?<br><br>Thanks again,<br>Hal<br><blockquote style="border-left: 2px solid rgb(16, 16, 255); margin-left: 5px; padding-left: 5px; color: rgb(0, 0, 0); font-weight: normal; font-style: normal; text-decoration: none; font-family: Helvetica,Arial,sans-serif; font-size: 12pt;"><div dir="ltr"><div></div><div><br></div><div>(I'm going to just leave this thread be now)</div><div id="DWT12024"><br></div><div><br></div></div><div class="gmail_extra"><br><div class="gmail_quote">On Wed, Aug 31, 2016 at 4:17 PM, 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: 0pt 0pt 0pt 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=""><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;"><div style="font-family: arial,helvetica,sans-serif; font-size: 10pt; color: rgb(0, 0, 0);"><br>Yes, this was exactly my point. We want to recognize structurally-equivalent sequences of instructions on inequivalent operands.<br></div></blockquote><div><br></div></span><div>Yes, and my point is "none of the vn and vn-dag generating algorithms care".</div><div><br></div><div>you can define equivalent to be "structural", you can define it to be "these two variables are equivalent if they both start with "a"", you can define it however you want.</div><div>They will still give you the dags you want.</div><div><br></div><div>This is as simple as substituting a hash and equality function.</div><div><br></div><div>To whit: Actual compilers do it this way.</div><div><br></div><div>So i'm entirely unsure why there is such an argument that it hard or impossible, or even strange.</div><div><br></div><div>It is in fact quite easy, the same way GCC has had the VN pass that produces expression DAG output, and had it used to code hoisting, to do PRE, to do folding, to do whatever. It has been used for all of these thing.</div><div><br></div><div>Some of these use a more standard VN definition of equivalence that is useful for redundancy elimination.</div><div>Some of them use one that is meant for folding (and would be illegal to use for straight redundancy elimination).</div><div><br></div><div>If you want to build a pass that basically does the same thing, it seems silly, but feel free!<br></div><div><br></div><div><br></div><div><br><br></div></div></div></div>
</blockquote></div><br></div>
</blockquote><br><br><br>-- <br><div><span name="x"></span>Hal Finkel<br>Assistant Computational Scientist<br>Leadership Computing Facility<br>Argonne National Laboratory<span name="x"></span><br></div></div></body></html>