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.
- On regular tree languages and deterministic pushdown automata
- A new algorithm for linear regular tree pattern matching
- Code generation based on formal BURS theory and heuristic search
- Computing all subtree repeats in ordered trees
- An optimal algorithm for computing all subtree repeats in trees
- TWO RELATED ALGORITHMS FOR ROOT-TO-FRONTIER TREE PATTERN MATCHING
- scientific article; zbMATH DE number 4155861 (Why is no real title available?)
- scientific article; zbMATH DE number 2090076 (Why is no real title available?)
- Automatically generating instruction selectors using declarative machine descriptions
- Resourceable, retargetable, modular instruction selection using a machine-independent, type-based tiling of low-level intermediate code
- Implementation and Application of Automata
- Hasse diagrams for classes of deterministic bottom-up tree-to-tree-series transformations
- Weighted tree automata and weighted logics
- Compositions of tree series transformations
- Code selection by inversion of order-sorted derivors
This page was built for publication: Tree automata for code selection
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1342507)
