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

[Daniel Berlin via llvm-dev]

On Tue, Aug 1, 2017 at 10:44 AM, River Riddle <riddleriver at gmail.com> wrote:

> Hey Dan,
>
> On Tue, Aug 1, 2017 at 10:28 AM, Daniel Berlin via llvm-dev <
> llvm-dev at lists.llvm.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.
>> You can also reduce it to 3-sat., but that doesn't mean anything unless
>> you can reduce 3-sat to it.
>>
>> 5. The actual problem the outliner is trying to solve is actually more
>>> like finding subgraphs that are isomorphic, making the problem even harder
>>> (something like "given dags A and B does there exist a subgraph of A that
>>> is isomorphic to a subgraph of B")
>>>
>>>
>> This assumes, strongly, that this reduction is the way to do it, and also
>> that SSA/etc imparts no structure in the reduction that enables you to
>> solve it faster (IE restricts the types of graphs, etc)
>>
>> FWIW, the exact argument above holds for value numbering, and since the
>> days of kildall, it was believed not solvable in a complete fashion in less
>> than exponential time due to the need to do graph isomorphism on large
>> value graphs at join points.
>>
>> Except, much like RA and other things, it turns out this is not right for
>> SSA, and in the past few years, it was proved you could do complete  value
>> numbering in polynomial time on SSA.
>>
>> So with all due respect to quentin, i don't buy it yet.
>>
>> Without more, i'd bet using similar techniques to solve value numbering
>> in polynomial time to SSA could be applied here.
>>
>> This is because the complete polynomial value numbering techniques are in
>> fact, value graph isomorphism ....
>>
>> So i'd assume the opposite (it can be done in polynomial time) without
>> more.
>>
>
> If you are willing to point me in the right direction, I am more than
> willing to implement/adapt to this type of solution for candidate selection.
> Thanks,
>  River Riddle
>

Though i'm happy to have this tangent discussion because i think it's
interesting, realistically, I'm not sure it's worth it ATM when you've got
stuff that works pretty well.  So i'm going to drop off and let you
concentrate on *this* patch, because i think that's what we should start
with, realistically.

I just don't want us to declare it "impossible" without actual  proof.  Ken
Zadeck told me when he first tried to show that he could solve
"thought-to-be-N^3" dataflow problems in linear time, the response get got
was "that's impossible and i can prove it", and it turns out they were
wrong :)
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170801/e73c73fe/attachment.html>