[LLVMdev] NP-hard problems in the LLVM optimizer?

[David Blaikie]

On Mon, Jan 12, 2015 at 7:30 AM, Daniel Berlin <dberlin at dberlin.org> wrote:

>
>
> On Mon, Jan 12, 2015 at 4:09 AM, Nicola Gigante <nicola.gigante at gmail.com>
> wrote:
>
>> Hi all.
>>
>> I’ve heard a couple of times that some of the problems solved by various
>> passes in the optimizer are indeed NP-hard, even though the instances
>> are small enough to be tractable (and very quickly).
>>
>> Is this true?
>
>
> Some are NP-Hard, some are NP-complete.
>
>
>> If so, which are these problems?
>> Register allocation? Instruction scheduling?
>>
> Depends on how you define register allocation (IE optimal register
> coloring, optimal spilling, optimal copy coalescing, optimal
> dematerialization, etc), but even some of the subtasks are np-complete for
> normal programs.
>
> You can also prove that strict SSA programs have some properties that make
> some of these subtasks *not* NP-complete when taken in isolation, for
> example, register coloring can be done optimally because strict SSA
> programs produce chordal graphs, *despite* the fact that register coloring
> is an NP-complete problem in general.
>
> But in general, even the simple task of "figuring out the smallest number
> of registers it takes to color a given register interference graph" is
> NP-complete
>
> Scheduling is also full of NP-complete and np-hard problems.
> Even if you restrict scheduling instructions to assume a fixed 2-cycle
> latency (IE no funky pipeline constraints, etc), it's *still* np hard (see
> http://dl.acm.org/citation.cfm?id=155183.155190)
>
>
>
>
>> Are they solved exactly or by approximations?
>>
>
> Approximations in some cases, not trying in others (IE not even
> approximating optimal, or considering optimal in the formulation, but just
> trying to do something that seems to turn out good in practice. I wouldn't
> call these approximations since they are not related to solving the NP
> complete problems, just generating good code).
>
> The only case i'm aware of using real exact/approximation solutions is
> PBQP, which solves a subclass of the NP complete problem it attacks in
> linear time.
>
I believe it uses heuristics to approximate an optimal answer in the rest,
> but don't quote me on that :)
>

Yep, that's the general idea. Optimal for some simple graphs,
domain-specific heuristic for the complex parts.


> Or not solved at all (the need of solving them is avoided in some way)?
>>
>
> It only avoids them in the sense that it simply ignores optimality as a
> constraint.
>
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150112/5ff6949f/attachment.html>