Complete and Practical Universal Instruction Selection

Gabriel Hjort Blindell, Mats Carlsson, Roberto Castañeda Lozano, Christian Schulte

Research output: Contribution to journalArticlepeer-review

Abstract / Description of output

In code generation, instruction selection chooses processor instructions to implement a program under compilation where code quality crucially depends on the choice of instructions. Using methods from combinatorial optimization, this paper proposes an expressive model that integrates global instruction selection with global code motion. The model introduces (1) handling of memory computations and function calls, (2) a method for inserting additional jump instructions where necessary, (3) a dependency-based technique to ensure correct combinations of instructions, (4) value reuse to improve code quality, and (5) an objective function that reduces compilation time and increases scalability by exploiting bounding techniques. The approach is demonstrated to be complete and practical, competitive with LLVM, and potentially optimal (w.r.t.the model) for medium-sized functions. The results show that combinatorial optimization for instruction selection is well-suited to exploit the potential of modern processors in embedded systems.
Original languageEnglish
Article number119
Pages (from-to)119:1-119:18
Number of pages18
JournalACM Transactions on Embedded Computing Systems
Issue number5s
Publication statusPublished - 27 Sept 2017

Keywords / Materials (for Non-textual outputs)

  • instruction selection
  • combinatorial optimization
  • code generation
  • constraint programming


Dive into the research topics of 'Complete and Practical Universal Instruction Selection'. Together they form a unique fingerprint.

Cite this