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

[Daniel Berlin via llvm-dev]

On Tue, Aug 1, 2017 at 10:28 AM, Daniel Berlin <dberlin at dberlin.org> wrote:

>
>>
>> Also as a side note, I think in the original MachineOutliner RFC thread
>> there was some confusion as to whether it was possible to solve the code
>> folding outlining problem exactly as a graph problem on SSA using standard
>> value numbering algorithms in polynomial time.
>>
>
>
>> I can elaborate further, but
>> 1. it is easy to see that you can map an arbitrary dag to an isomorphic
>> data flow graph in an SSA IR e.g. in LLVM IR or pre-RA MIR
>>
>
>
>> 2. Given two dags, you can create their respective isomorphic data flow
>> graphs (say, put them into two separate functions)
>> 3. An exact graph based code folding outliner would be able to discover
>> if the two dataflow graphs are isomorphic (that is basically what I mean by
>> exact) and outline them.
>> 4. Thus, graph isomorphism on dags can be solved with such an algorithm
>> and thus the outlining problem is GI-hard and a polynomial time solution
>> would be a big breakthrough in CS.
>>
>
> First, you'd have to reduce them in both directions to prove that ;)
>
> All that's been shown is that you can reduce it to a hard problem.
>
In particular, Quentin has not actually shown that every possible DFG can
be generated by SSA IR (without affecting the time/space class) , or that
every possible DFG can be converted to SSA IR (ditto).
While i believe the latter is possible (Though SSA is not a linear space
transform, even though it is a linear time one. I believe it is at worst an
N^2 transform, and not an exponential space one), i'm significantly less
sure about the former, and it seems quite wrong to me without thinking
about it too hard.
(it seems it would imply SSA is a lot more powerful than it is).

I'm also pretty sure i've seen papers that prove the former is false.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170801/e890e314/attachment-0001.html>