(An) analysis for the bottom-up tree pattern matching using dynamic programming at compile-time

Abstract

Bottom-up tree pattern matching scheme is widely accepted by modern code generator generators, and draws more attention for obtaining an efficient code generator. For the flexible expression of the tree grammars and the larger class of tree grammars, the bottom-up tree pattern matching scheme allows the arbitrary cost values and performs dynamic programming at compile-time. Thus, the dynamic programming process make the code generator be slow. In this dissertation, we propose two efficient methods of constructing states in the bottom-up tree pattern matching scheme that performs dynamic programming. The bottom-up tree pattern matching scheme with DP traverses the IR tree twice. In the first traversal, the scheme annotates a state for each node of the IR tree in a bottom-up direction. A state can be extracted by checking sequentially all tree patterns over the given set at each node. In the second traversal, the scheme will find the least-cost cover in a top-down direction. Then a target code is produced by executing the semantic actions from the rewrite rules used for the least-cost cover. To get the efficiency of the matching scheme, the decision tree of a set of rules is introduced, which specify the order of tree patterns to be checked. The check of one pattern might make the matching scheme avoid some unfruitful patterns. The decision tree is formulated by analyzing the relations between tree patterns. However, Finding optimal decision tree is an NP-complete problem that requires heuristic solution. We propose an heuristic. The other method of getting the efficiency transforms the set of patterns into the match sets. The match set is the set of fruitful patterns for extracting a state. The match sets and match set transition tables can be constructed at compile-compile time and are also formulated by analyzing the relations between tree patterns. The proposed methods are derived from the analysis of relations over tree patterns. The relevant analyses ar...