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, r2k, r3ka, gbz80 and stm8 ports. 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.