5 ms·
Register allocators use heuristics that are “pretty good” for most usage, but sometimes fail spectacularly in edge cases with very high pressure. Register allo
by stephencanon 13y ago
Register allocators use heuristics that are “pretty good” for most usage, but sometimes fail spectacularly in edge cases with very high pressure. Register allocation is, after all, NP-complete. Even when it doesn't fail completely, if you’re tuning a load-store-bound computation, a few extra register spill-fill pairs can easily halve the throughput that you achieve.
That said, for most programmers, most of the time: use intrinsics and let the compiler handle register allocation.
- DannyBee 13y agoActually, register allocation on SSA graphs can be done optimally in polynomial time, as the graphs are all chordal.
- cliffbean 13y agoDon't be pedantic. Splitting the problem into parts and saying that the one part which happens to have the name that other people use to refer to the whole problem is easy doesn't make the whole problem easy.
- DannyBee 13y agoWhat? "Register allocators use heuristics that are “pretty good” for most usage, but sometimes fail spectacularly in edge cases with very high pressure. Register allocation is, after all, NP-complete. " The specific problem he referred to was the heuristics failing spectacularly in high pressure. In SSA form, they have no need to use heuristics, and if they don't want to, don't. They can optimally choose registers. This will not fail. Yes, there are other parts to register allocation. The most common NP complete part referred to, and referred to by the parent (AFAICT), was register choosing. This is not NP complete to do optimally in compilers using SSA form. Period. There may be other parts to the register allocation pass that use heuristics, and fall down, but most of those are not NP complete on SSA either.
- aidenn0 13y agoI'm not super familiar with all the recent literature on SSA, but it always seemed to me that while you could optimally allocate registers for the SSA representation, the SSA representation often contains dead Φs, and fully eliminating the Φs may not be doable in polynomial time.
- DannyBee 13y agohttp://www.cs.ucla.edu/~palsberg/paper/cc09.pdf http://www.cs.ucla.edu/~palsberg/paper/cc09.pdf spill free phi elimination in polynomial time :) There are other algorithms that may coalesce more phis, and can be done in linear time, but do not have such guarantee. If your concern is dead phis, all dead phis (where dead is defined as unused, or only used by dead instructions) can be eliminated in linear time by performing a single linear time backwards-DCE pass on the graph. This will get all phis and instructions that are dead, or only used by instructions that are themselves dead. If your concern is useless phis and instructions (for lack of a better term, there are papers, and they use the word "dead" differently, so i'm defining a term here for you), where you define useless as "side-effects do not matter", such that in *a = 5 c = a *a = 5 c = a the second store and assignment is useless, This type of elimination is O(N^3) normally, and unproven bounds in SSA (AFAIK).
- aidenn0 13y agoThanks for that info; I have more reading to do. The actual work I get paid to do isn't on an SSA compiler, so keeping up-to-date on SSA is more of a hobby.
- aidenn0 13y agoWhich is fine if you don't mind the quadratic increase in IR size.