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

>
>
> 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?
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170801/4571147f/attachment.html>

> On Aug 1, 2017, at 12:01 PM, Daniel Berlin <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

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

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>