Optimal linear regular tree pattern matching using pushdown automata

Abstract

Code generation is a difficult and complex phase of compiler writing. Most problems associated with the code generation phase are NP-complete; therefore, heuristics have been employed to solve them. Instruction selection is one of the few sub-problems of code generation that has a polynomial-time solution. Among the various methods available for performing instruction selection, tree pattern matching has gained prominence due to its usefulness in designing efficient tools for retargetable code generation. This thesis presents the design and implementation of one such tool. The input specification to the tool is in the form of a regular tree grammar augmented with costs. The tool produces, as output, a deterministic pushdown automaton, encoded in the form of tables. The traversal of the intermediate tree code and the reporting of matches can be viewed as a parsing problem, for which the automaton can be employed. The use of the automaton can be extended to select an optimal instruction sequence, by virtue of the fact that cost information, obtained during a preprocessing phase, can be stored in its finite state control. The tool can thus be used for either static or dynamic cost computation. The limitations of the tool are also analyzed in the thesis.