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

[River Riddle via llvm-dev]

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


>
>
>
> _______________________________________________
> 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/758336a2/attachment.html>