<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 8:24:11 PM<br><b>Subject: </b>Re: [llvm-dev] [RFC] Interprocedural MIR-level outlining pass<br><div dir="ltr"><div class="gmail_extra"><div class="gmail_quote">On Wed, Aug 31, 2016 at 5:36 PM, Hal Finkel <span dir="ltr"><<a href="mailto:hfinkel@anl.gov" target="_blank">hfinkel@anl.gov</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><div style="font-family: arial,helvetica,sans-serif; font-size: 10pt; color: rgb(0, 0, 0);"><br><hr><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" <<a href="mailto:dberlin@dberlin.org" target="_blank">dberlin@dberlin.org</a>><br><b>To: </b>"Hal Finkel" <<a href="mailto:hfinkel@anl.gov" target="_blank">hfinkel@anl.gov</a>><br><b>Cc: </b>"Andrey Bokhanko" <<a href="mailto:andreybokhanko@gmail.com" target="_blank">andreybokhanko@gmail.com</a>>, "llvm-dev" <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>><br><b>Sent: </b>Wednesday, August 31, 2016 7:02:57 PM<span class="gmail-"><br><b>Subject: </b>Re: [llvm-dev] [RFC] Interprocedural MIR-level outlining pass<br><br></span><span class="gmail-"><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>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></span></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.<span style="font-family: arial,sans-serif; font-size: small; color: rgb(34, 34, 34);"> </span></div></div></blockquote><blockquote class="gmail_quote" style="margin: 0px 0px 0px 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;"><div><div style="font-family: arial,helvetica,sans-serif; font-size: 10pt; color: rgb(0, 0, 0);"><br></div></div></blockquote></div><div class="gmail_quote"><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><div style="font-family: arial,helvetica,sans-serif; font-size: 10pt; color: rgb(0, 0, 0);">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<span style="font-family: arial,sans-serif; font-size: small; color: rgb(34, 34, 34);"> </span></div></div></blockquote><blockquote class="gmail_quote" style="margin: 0px 0px 0px 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;"><div><div style="font-family: arial,helvetica,sans-serif; font-size: 10pt; color: rgb(0, 0, 0);">t = q - r<br><br></div></div></blockquote><div>Doing literally nothing but building a standard VN dag (IE with normal equivalence), </div><div>The dag here will contain:</div><div> <br></div><div>V1 = VN Expression of E + E</div><div>V2 = V1</div><div>s = VN expression of V1 + V2 (you can substitute V1 if you like or not)</div><div>x = VN expression of V1 - V2 (ditto)</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><div style="font-family: arial,helvetica,sans-serif; font-size: 10pt; color: rgb(0, 0, 0);">and:<br><br>u = E + E<br>
v = E - E<br>
w = u + v<br>
x = u - v</div></div></blockquote><div><br></div><div><br></div><div>The dag here would contain</div><div>V1 = E + E</div><div>V2 = E - E</div><div>w = VN expression of V1 + V2</div><div>x = VN expression of V1 - V2</div><div id="DWT1524"><br></div></div></div></div></blockquote>Okay, I understand this. V2 here, of course, is different from V2 in the instruction sequence above.<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 class="gmail_extra"><div class="gmail_quote"><div></div><div><br></div><div>So what's the issue you are worried about here, precisely?</div><div><br></div><div>If you extend this example to be longer, the answer does not change.</div><div><br></div><div id="DWT1525">If you make it so one example is longer than the other, you can still discover this by normal graph isomorphism algorithms.</div></div></div></div></blockquote>Alright, I think this is where we're talking past each other. I thought you were saying that using the VN DAG somehow makes this part easier (compared, say, to running on the SSA use/def graph). If you're not claiming that, then I think we're on the same page.<br><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 class="gmail_extra"><div class="gmail_quote"><div></div><div>If you literally only care about the operation being performed, you can make that work too.</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><div style="font-family: arial,helvetica,sans-serif; font-size: 10pt; color: rgb(0, 0, 0);">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></div></div></blockquote><div><br></div><div>So let's back up. In your scheme, how do you think you do that now, precisely?</div><div>What is the algorithm you use to discover the property you are trying to find?<br></div><div><br></div></div></div></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>