[llvm-dev] [RFC] Add IR level interprocedural outliner for code size.

[Jessica Paquette via llvm-dev]

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!).

String isomorphism is defined as

“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?”

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.

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!

- Jessica

> On Aug 1, 2017, at 12:20 PM, Quentin Colombet via llvm-dev <llvm-dev at lists.llvm.org> wrote:
> 
> 
>> On Aug 1, 2017, at 12:01 PM, Daniel Berlin <dberlin at dberlin.org <mailto:dberlin at dberlin.org>> wrote:
>> 
>> 
>> 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.
>> 
>> 
>> I'm disappointed you didn't have time to try to solve major open computer science problems in an internship.
>> What are you even doing over there?
>> 
> 
> Heh, I am also wondering :P
> 
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170801/cccff6f5/attachment.html>