M. Bravenboer and E. Visser. Rewriting Strategies for Instruction Selection. In S. Tison, editor, Rewriting Techniques and Applications (RTA'02), volume 2378 of Lecture Notes in Computer Science, pages 237--251, Copenhagen, Denmark, July 2002. Springer-Verlag. (pdf).


Instruction selection (mapping IR trees to machine instructions) can be expressed by means of rewrite rules. Typically, such sets of rewrite rules are highly ambiguous. Therefore, standard rewriting engines based on fixed, exhaustive strategies are not appropriate for the execution of instruction selection. Code generator generators use special purpose implementations employing dynamic programming. In this paper we show how rewriting strategies for instruction selection can be encoded concisely in Stratego, a language for program transformation based on the paradigm of programmable rewriting strategies. This embedding obviates the need for a language dedicated to code generation, and makes it easy to combine code generation with other optimizations.


  author    = {Martin Bravenboer and Eelco Visser},
  title     = {Rewriting Strategies for Instruction Selection},
  booktitle = {Rewriting Techniques and Applications (RTA'02)},
  pages     = {237-251},
  year      = 2002,
  editor    = {S. Tison},
  volume    = 2378,
  series    = {Lecture Notes in Computer Science},
  address   = {Copenhagen, Denmark},
  month     = {July},
  publisher = {Springer-Verlag},
  urlpdf    = {http://www.cs.uu.nl/people/visser/ftp/BV02.pdf},
  pubcat    = {conference},

CategoryPaper | StrategoPublications