[Back]

P. Thier, M.A. Ertl, A. Krall:
"Fast and Flexible Instruction Selection with Constraints";
Talk: Compiler Construction, Wien; 02-24-2018 - 02-25-2018; in: "Proceedings of the 27th International Conference on Compiler Construction", ACM, (2018), ISBN: 978-1-4503-5644-2; 93 - 103.

Tree-parsing instruction selection as used in, e.g.,
lcc, uses dynamic costs to gain flexibility and
handle situations (such as read-modify-write
instructions) that do not fit into the basic
tree-parsing model. The disadvantage of dynamic
costs is that we can no longer turn the tree grammar
into a tree automaton (as is done by burg) for fast
instruction selection for JIT compilers. In this
paper we introduce constraints that say whether a
tree-grammar rule is applicable or not. While
theoretically less powerful than dynamic costs,
constraints cover the practical uses of dynamic
costs; more importantly, they allow turning the tree
grammar with constraints into a tree automaton (with
instruction-selection-time checks), resulting in
faster instruction selection than with pure
instruction-selection-time dynamic programming. We
integrate constraints in an instruction selector
that matches DAGs with tree rules. We evaluate this
concept in lcc and the CACAO JavaVM JIT compiler,
and see instruction selector speedups by a factor
1.33--1.89.

http://dx.doi.org/10.1145/3178372.3179501

https://publik.tuwien.ac.at/files/publik_277344.pdf