Automated Generation of Decoders for Irregular Instruction Sets Using Information-Theoretic Decision Tree Construction Algorithms

Instruction decoders are indispensable components of the System-on-Chip design flow and major constituents of instruction set simulators and processor toolchains. The complex and lengthy process of manual decoder design can be greatly alleviated by automated decoder generation tools based on high level instruction definitions. Unfortunately, automatic generation is challenged by the rising complexity of instruction sets as well as irregularities such as non-uniform opcodes, logic propositions on bit fields and multiple or nested specializations. The few available state-of-the-art decoder generation tools either cannot handle irregularities altogether or produce inadequate results, either functionally or w.r.t. performance. Moreover, they are largely ad hoc and do not bear on any of the well-established work on decision tree generation. This paper presents a sophisticated decision-tree algorithm for the problem of generating decoders for irregular instruction sets. Our algorithm has produced fully automated, functionally correct and cost-aware decoders for the SPARC, MIPS32 and ARMv7 instruction sets. Our results prove the application of information-theoretic concepts to decoder generation a most promising approach.