[llvm-dev] [RFC] Add IR level interprocedural outliner for code size. (original) (raw)
Jessica Paquette via llvm-dev llvm-dev at lists.llvm.org
Tue Aug 1 13:29:11 PDT 2017
- Previous message: [llvm-dev] [RFC] Add IR level interprocedural outliner for code size.
- Next message: [llvm-dev] [RFC] Add IR level interprocedural outliner for code size.
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
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>
- Previous message: [llvm-dev] [RFC] Add IR level interprocedural outliner for code size.
- Next message: [llvm-dev] [RFC] Add IR level interprocedural outliner for code size.
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]