Implicit hints: Embedding hint bits in programs without ISA changes

There is a large gap in knowledge about a program between the compiler, which can afford expensive analysis, and the processor, which by nature is constrained in the types of analysis it can perform. To increase processor performance, ISAs have been extended with hint bits to communicate some of the compiler´s knowledge to the processor. In this paper, we propose and analyze a technique for adding or removing hints to a processor without changing the ISA, i.e. without breaking binary compatibility. Our technique exploits the freedom of allocating values to registers. We divide the registers in disjoint sets and assign one hint value to each set of registers. We implement our technique in the GCC compiler. Evaluation on two very different instruction sets, the Alpha ISA and the x86-64 ISA, shows that these hints can be encoded with high accuracy, although the accuracy varies strongly between instruction sets. We demonstrate that it is possible to encode multiple hints in register names and that the quality of register allocation is not degraded.