1. 12
  1. 2

    Survey on Instruction Selection is still the best resource on instruction selection. Take a look if you are interested in the background.

    1. 2


      I’m currently rewriting the backend/instruction-selection infra in my compiler, and there are some really interesting similarities and differences.

      My primary IR (high-level, SSA) is lowered to lower-level IR before code generation, but the instructions in the latter are effectively micro-instructions, when compared with assembly. The backend’s job is to synthesize these ‘microinstructions’ into native machine instructions—that is, it’s almost always a many-to-one (or many-to-many) correspondence—and specify what registers it needs. It can also specify constraints for those registers; e.g., the first output register has to be the same as the first input register (because the ir uses three-operand arithmetic instructions where some architectures only have two-operand forms).

      I also use SSA for virtual registers (though not, obviously, physical registers). This is because after instruction selection and before register allocation, registers have to be garbage collected. The IR is very limited, so sometimes it allocates registers it doesn’t actually need. For instance:

      ldri r0, 15  ; load register with immediate
      add r1, r0, r2
      add r4, r3, r1

      On x86 this should just generate the code:

      lea r4, [r3 + r2 + 15]

      So r0 and r1 are completely superfluous (assuming they’re not used elsewhere), and thus they (and their corresponding ldri and add genesis instructions) can be removed. But if registers can be mutated, then it’s harder both to match that pattern and to tell when a register can be GCed.

      An additional optimization I haven’t addressed yet is the case when a register isn’t GCed. To use the above example, if r1 turned out to be necessary for something else, it would be more efficient to compile to this:

      lea r4, [r3 + r1]

      (Maybe. Or maybe not, because of false dependencies.)

      SSA helps again here, because at code generation time you can check if the virtual register r1 got mapped to a physical register and use it if so; you won’t have to worry if it has a different value. The only potential roadblock is that the lea instruction didn’t specify a dependency on r1, so if I want to do instruction scheduling after selection, the initialization of r1 might get moved after the lea. (Or it might still be before, but its live range might end and a different register take its place.)

      Perhaps it can specify a weak dependency (à la weak reference) on r1; meaning, if r1 is alive then its initialization can’t be moved after the lea; but the dependency of the lea on r1 won’t be considered when GCing. Still have to think more about that, though.