Premium
Fast graph‐based instruction selection for multi‐output instructions
Author(s) -
Youn Jonghee M.,
Lee Jongwon,
Paek Yunheung,
Lee Jongeun,
Scharwaechter Hanno,
Leupers Rainer
Publication year - 2011
Publication title -
software: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.437
H-Index - 70
eISSN - 1097-024X
pISSN - 0038-0644
DOI - 10.1002/spe.1034
Subject(s) - computer science , exploit , compiler , instruction set , graph , parallel computing , computer architecture , code (set theory) , set (abstract data type) , selection (genetic algorithm) , architecture , optimizing compiler , microarchitecture , theoretical computer science , programming language , artificial intelligence , art , computer security , visual arts
A multi‐output instruction (MOI) is an instruction that produces multiple outputs to its destination locations. Such inherently parallel instructions are becoming more and more popular in embedded processors, due to the advances in application‐specific architectures. In order to provide high‐level programmability and thus guarantee widespread acceptance, sophisticated compiler support for these programmable cores is necessary. However, traditional tree‐based approaches for instruction selection, although very fast, fail to exploit MOIs mainly because of the fundamental limitation of the tree representation. In fact, to generate optimal code with MOIs requires a more general graph‐based formulation of the instruction selection problem, which is at least NP‐complete. In this paper we present a new methodology to automatically generate from simple instruction set descriptions, graph‐based code selectors that can effectively utilize all provided instructions including MOIs. Our experimental results using a set of benchmarks on a target processor with various MOIs of up to two outputs demonstrate that our generated code selectors can quickly and effectively exploit many MOIs at the application level, and therefore are highly desirable both for architecture exploration and as code generators after architecture is fixed. Copyright © 2010 John Wiley & Sons, Ltd.