SDCC currently has two register allocators. One of them is optimal when optimizing for code size. This register allocator is used by default on the hc08, s08, z80, z180, ez80_z80, r2k, and r3ka ports. For the gbz80, stm8,pdk13, pdk14 and pdk15 ports it is the only available register allocator. Even though it runs in polynomial time, it can be quite slow; therefore the --max-allocs-per-node command line option can be used for a trade-off between compilation speed and quality of the generated code: Lower values result in faster compilation, higher values can result in better code being generated.
It first creates a tree-decomposition of the control-flow graph, and then uses dynamic programming bottom-up along the tree-decomposition. Optimality is achieved through the use of a cost function, which gives cost for instructions under register assignments. The cost function is target-specific and has to be implemented for each port; in all current SDCC ports the cost function is integrated into code generation.
For more details on how this register allocator works, see: Philipp Klaus Krause, ”Optimal Register Allocation in Polynomial Time”, Compiler Construction - 22nd International Conference, CC 2013, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2013. Proceedings, Lecture Notes in Computer Science, volume 7791, pp. 1-20. Springer, 2013. Also: Philipp Klaus Krause, ”Bytewise Register Allocation”, Proceedings of the 18th International Workshop on Software and Compilers for Embedded Systems, SCOPES ’15, pp 22–27. Association for Computing Machinery, 2015.