<html><head><meta http-equiv="Content-Type" content="text/html charset=utf-8"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class=""><div class="">Just to chime in… I do think there is a relationship with string isomorphism (although I haven’t hashed out a proof of it yet!).</div><div class=""><br class=""></div><div class=""><div class="">String isomorphism is defined as</div><div class=""><br class=""></div><div class="">“Given two equal-length strings S1, S2 over a finite alphabet and a permutation group G, is there an element of G that will transform S1 into S2?”</div></div><div class=""><br class=""></div><div class="">It’s known to be quasipolynomial-time. It sounds similar in spirit to the equivalence problem between strings in outlining, given you have 0 parameters to pass. What we want is a structure-preserving transformation between two strings, given a higher-order structure/state that is defined by the entire program. For example, our state might be the values in memory at any given timestep. If we *always* have such a transformation between two strings composed of identical instructions, but different/unknown registers, then those sequences must be safe to outline.</div><div class=""><br class=""></div><div class="">Of course, this is just an observation, and not a claim of equivalence or complexity. Attempting a reduction might be a fun evening project though!</div><div class=""><br class=""></div><div class=""><div class="">- Jessica</div><div class=""><div class=""><br class=""><div class=""><div class=""><div class=""><div class=""><div><blockquote type="cite" class=""><div class="">On Aug 1, 2017, at 12:20 PM, Quentin Colombet 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=""><meta http-equiv="Content-Type" content="text/html charset=utf-8" class=""><div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><br class=""><div class=""><blockquote type="cite" class=""><div class="">On Aug 1, 2017, at 12:01 PM, Daniel Berlin <<a href="mailto:dberlin@dberlin.org" class="">dberlin@dberlin.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 style="word-wrap:break-word" class=""><div class=""><span class=""><div class=""><br class=""></div></span><div class="">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 class=""><br class=""></div></div></div></blockquote><div class=""><br class=""></div><div class="">I'm disappointed you didn't have time to try to solve major open computer science problems in an internship.</div><div class="">What are you even doing over there?<br class=""><br class=""></div></div></div></div>
</div></blockquote><br class=""></div><div class="">Heh, I am also wondering :P</div><br class=""></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=""></div></div></div></div></div></div></div></body></html>