6 ms·

Managing register allocation by hand is unlikely to provide significant speedups, considering that modern register allocators are "pretty good." However, if you

by rinon 13y ago

Managing register allocation by hand is unlikely to provide significant speedups, considering that modern register allocators are "pretty good." However, if you are wanting to optimize for SIMD, this can be easily done with vector instructions in IR, without needing to worry about register allocation at all.

mjn 13y ago
At least as of a few years ago, the x264 team claimed they didn't use C intrinsics for their inline asm because automatic register allocation wasn't very good: http://x264dev.multimedia.cx/archives/191#comment-1763 http://x264dev.multimedia.cx/archives/191#comment-1763 (exchange between comments 3 and 4). Sure, you can write SIMD in LLVM IR, but to do it efficiently you need some knowledge of the target. Should you use i32, or rework your code to use more i16, or throw in some parallel i64 multiplications? Those aren't really portable choices, unless you have a really good auto-vectorizer, in which case the advantage of writing in asm at all disappears, since you can just rely on auto-vectorized C.
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 ago
  Actually, register allocation on SSA graphs can be done optimally in polynomial time, as the graphs are all chordal.
  - cliffbean 13y ago
    Don'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 ago
      What? "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 ago
        I'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 ago
        http://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 ago
    Which is fine if you don't mind the quadratic increase in IR size.
haberman 13y ago
LuaJIT has a hand-written assembly language interpreter, which is one of the fastest dynamic language interpreters around. According to its author, register allocation is a significant part of why the hand-written assembly is faster: http://lua-users.org/lists/lua-l/2011-02/msg00742.html http://lua-users.org/lists/lua-l/2011-02/msg00742.html
- duaneb 13y ago
  That issue is pretty rare—a tight 'loop' where you don't know where you're coming from (aka the previous instruction) or where the next 'loop' iteration goes (aka the next instruction). Because this code block is bounded by indirect jumps, it's virtually impossible to register allocate without agreeing on a mini ABI for this scenario. Not surprisingly, this is unusual enough it's inexpressible in C. However, there are things that provide a middle ground, like computed GOTOs, which both the ocaml and python interpreter use now for bytecode evaluation. Of course, I suspect if you pass luajit an unusual program (say, an unusual distribution of instructions), it would actually perform worse. Register allocation is np-complete, so ultimately with modern programs it's dependent on really good heuristics, and C wasn't written to be a bytecode evaluator.
  - haberman 13y ago
    > Of course, I suspect if you pass luajit an unusual program (say, an unusual distribution of instructions), it would actually perform worse. I think that's unlikely. The LuaJIT interpreter keeps all important state in registers; this is not affected by the sequencing of bytecodes.
    - duaneb 13y ago
      > The LuaJIT interpreter keeps all important state in registers; this is not affected by the sequencing of bytecodes. Except on register-starved architectures like, say, i686.
pcwalton 13y ago
haberman beat me to it, but register allocation algorithms fall down in very branchy control flow like dispatch loops, basically for two reasons: (1) to make compile times reasonable they tend to have to approximate in this case: (2) compilers don't really know the hot paths in such code like a human would, and will likely make suboptimal spilling decisions as a result.
- DannyBee 13y ago
  1. This is only true in JIT's and similar things that strongly depend on linear time register allocation. LLVM happens to now use a greedy allocator that still tries to prioritize time over allocation optimality. 2. This is just a bad compiler then. Good static profiling is actually quite good, and quite accurate, in most cases. This includes value and other forms of profiling, rather than just simple static edge estimation based on heuristics. Usually, the thing that gets hurt is not spill placement, but bad inlining decisions. For diamond shaped switch statement interpreter loops with simple bodies, the real issue is that most greedy/linear allocators are not great at live range splitting. Compilers like LLVM (and to some degree, GCC), move all the variable allocations up to the beginning of the function to make life easy by removing scopes (otherwise you have really really crazy edge cases performing hoisting/sinking optimizations), and then for those that don't get mem2reg'd, can't prove they aren't live all at the same time during the switch due to the loop. Then they make bad choices about which of these variables should stay in registers because their value profiling infrastructures are non-existent. Proper region analysis, allocation regions, and better optimistic live range splitting would go a long way towards fixing this, but it's not worth it. There is little to no sense in optimizing LLVM for the very uncommon case of interpreter loops (particularly when one of the goals of LLVM is to ... replace interpreters). So the basic answer is: It's not really a problem anyone cares to solve, not "it's a really hard problem to solve".
  - qznc 13y ago
    Nevertheless, register allocation is still an NP-complete problem and even in AOT compilation everything above O(n^3) is too slow (unless you just compile kernels for embedded software). Actually, it is not the register allocation itself, which is NP-complete [0]. Avoiding spills and copys is the hard part. [0] https://pp.info.uni-karlsruhe.de/publication.php?id=buchwald11cc https://pp.info.uni-karlsruhe.de/publication.php?id=buchwald...

by rinon 13y ago

mjn 13y ago

At least as of a few years ago, the x264 team claimed they didn't use C intrinsics for their inline asm because automatic register allocation wasn't very good: http://x264dev.multimedia.cx/archives/191#comment-1763 http://x264dev.multimedia.cx/archives/191#comment-1763 (exchange between comments 3 and 4). Sure, you can write SIMD in LLVM IR, but to do it efficiently you need some knowledge of the target. Should you use i32, or rework your code to use more i16, or throw in some parallel i64 multiplications? Those aren't really portable choices, unless you have a really good auto-vectorizer, in which case the advantage of writing in asm at all disappears, since you can just rely on auto-vectorized C.

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 ago
Actually, register allocation on SSA graphs can be done optimally in polynomial time, as the graphs are all chordal.
- cliffbean 13y ago
  Don'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 ago
    What? "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 ago
      I'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 ago
        http://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 ago
  Which is fine if you don't mind the quadratic increase in IR size.

haberman 13y ago

LuaJIT has a hand-written assembly language interpreter, which is one of the fastest dynamic language interpreters around. According to its author, register allocation is a significant part of why the hand-written assembly is faster: http://lua-users.org/lists/lua-l/2011-02/msg00742.html http://lua-users.org/lists/lua-l/2011-02/msg00742.html

duaneb 13y ago
That issue is pretty rare—a tight 'loop' where you don't know where you're coming from (aka the previous instruction) or where the next 'loop' iteration goes (aka the next instruction). Because this code block is bounded by indirect jumps, it's virtually impossible to register allocate without agreeing on a mini ABI for this scenario. Not surprisingly, this is unusual enough it's inexpressible in C. However, there are things that provide a middle ground, like computed GOTOs, which both the ocaml and python interpreter use now for bytecode evaluation. Of course, I suspect if you pass luajit an unusual program (say, an unusual distribution of instructions), it would actually perform worse. Register allocation is np-complete, so ultimately with modern programs it's dependent on really good heuristics, and C wasn't written to be a bytecode evaluator.
- haberman 13y ago
  > Of course, I suspect if you pass luajit an unusual program (say, an unusual distribution of instructions), it would actually perform worse. I think that's unlikely. The LuaJIT interpreter keeps all important state in registers; this is not affected by the sequencing of bytecodes.
  - duaneb 13y ago
    > The LuaJIT interpreter keeps all important state in registers; this is not affected by the sequencing of bytecodes. Except on register-starved architectures like, say, i686.

pcwalton 13y ago

haberman beat me to it, but register allocation algorithms fall down in very branchy control flow like dispatch loops, basically for two reasons: (1) to make compile times reasonable they tend to have to approximate in this case: (2) compilers don't really know the hot paths in such code like a human would, and will likely make suboptimal spilling decisions as a result.

DannyBee 13y ago
1. This is only true in JIT's and similar things that strongly depend on linear time register allocation. LLVM happens to now use a greedy allocator that still tries to prioritize time over allocation optimality. 2. This is just a bad compiler then. Good static profiling is actually quite good, and quite accurate, in most cases. This includes value and other forms of profiling, rather than just simple static edge estimation based on heuristics. Usually, the thing that gets hurt is not spill placement, but bad inlining decisions. For diamond shaped switch statement interpreter loops with simple bodies, the real issue is that most greedy/linear allocators are not great at live range splitting. Compilers like LLVM (and to some degree, GCC), move all the variable allocations up to the beginning of the function to make life easy by removing scopes (otherwise you have really really crazy edge cases performing hoisting/sinking optimizations), and then for those that don't get mem2reg'd, can't prove they aren't live all at the same time during the switch due to the loop. Then they make bad choices about which of these variables should stay in registers because their value profiling infrastructures are non-existent. Proper region analysis, allocation regions, and better optimistic live range splitting would go a long way towards fixing this, but it's not worth it. There is little to no sense in optimizing LLVM for the very uncommon case of interpreter loops (particularly when one of the goals of LLVM is to ... replace interpreters). So the basic answer is: It's not really a problem anyone cares to solve, not "it's a really hard problem to solve".
- qznc 13y ago
  Nevertheless, register allocation is still an NP-complete problem and even in AOT compilation everything above O(n^3) is too slow (unless you just compile kernels for embedded software). Actually, it is not the register allocation itself, which is NP-complete [0]. Avoiding spills and copys is the hard part. [0] https://pp.info.uni-karlsruhe.de/publication.php?id=buchwald11cc https://pp.info.uni-karlsruhe.de/publication.php?id=buchwald...