Tree automata for code selection (Q1342507)

Besides register allocation and instruction scheduling, the selection of instructions is one subtask of code generation within compilers. It is especially important for CISC architectures where there are usually many possibilities to generate code for the same piece of program. However, with the increasing complexity of RISC architectures the problem reappears. The paper systematically presents the basic theory behind code selection and exhibits the connections both of tree pattern matching and tree parsing algorithms to finite tree automata. The code selection problem is equivalent to finding a cheapest computation of a nondeterminisitc tree automaton with costs. For this problem efficient methods are presented. Since the computed tree automata are usually quite large, general methods for the implementation of tree automata are presented. Especially, the method of Kron is generalized to arbitrary tree automata. This makes it possible to write efficient generators of efficient code selectors. The results are also of interest for other areas. Both tree pattern matching and tree parsing are useful for checking the syntactic applicability of tree transformation rules. Especially tree pattern matching is used for the implementation of term rewriting systems.