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

[Nicola Gigante]

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? If so, which are these problems? 
Register allocation? Instruction scheduling?

Are they solved exactly or by approximations? 
Or not solved at all (the need of solving them is avoided in some way)?

Greetings,
Nicola