Name
Abstract | ||
|---|---|---|
A system called BURS that is based on term rewrite systems and a search algorithm A are combined to produce a code generator that generates opti- mal code. The theory underlying BURS is re-developed, formalised and explained in this work. The search algorithm uses a cost heuristic that is derived from the term rewrite system to direct the search. The advantage of us ing a search algorithm is that we need to compute only those costs that may be part of an optimal rewrite sequence. Compiler building is a time-consuming and error-prone activity. Building the front- end (i.e. scanner, parser and intermediate-code generator ) is straightforward—the theory is well established, and there is ample tool support. The mai n problem lies with the back-end, namely the code generator and optimiser—there is little theory and even less tool support. Generating a code generator from an abstract s pecification, also called automatic code generation, remains a very difficult problem. Pattern matching and selection is a general class of code-generation technique that has been studied in many forms. The most successful form uses a code generator that works predominantly bottom-up; a so-called bottom-up pattern matcher (BUPM). A variation of this technique is based on term rewrite systems . This technique, popularised under the name BURS, and developed by Pelegr´ i-Llopart and G raham (31), has arguably been considered the state of the art in automatic code genera tion. BURS, which stands for bottom-up rewrite system, has an underlying theory that is poorly understood. The theory has received virtually no attention in the literatur e since its initial publication (30). The only research that has been carried out in this technique has been on improved table- compression methods. Many researchers who claim to use BURS theory (e.g. (32, 14)) generally use 'weaker' tree grammars instead of term rewrit e systems, or equate BURS with a system that does a static cost analysis (e.g. (13)). We argue that a static cost analysis is neither necessary nor sufficient to warrant a BURS label, and that a system that is based on tree grammars cannot be a BURS. In this work we present an outline of formal BURS theory. Due to space restrictions, we present the full theory in (29). This formalisation of BURS contrasts with the semi- formal work of Pelegr´ i-Llopart and Graham. But there are ot her important differences in our work. We do not, for example, use instruction costs to do static pattern selection, and we do not use dynamic programming. Instead we use a heuristic search algorithm that only needs to dynamically compute costs for those patterns that may contribute to |
Year | DOI | Venue |
|---|---|---|
1996 | 10.1007/3-540-61053-7_60 | CC |
Keywords | Field | DocType |
search algorithms,code generation,term rewrite syste ms,formal techniques,compiler generators,cost analysis,search algorithm,front end,pattern matching,heuristic search,bottom up | Heuristic,Search algorithm,Programming language,Computer science,Code generation,Theoretical computer science,Code (cryptography) | Conference |
ISBN | Citations | PageRank |
3-540-61053-7 | 4 | 0.53 |
References | Authors | |
22 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Albert Nymeyer | 1 | 106 | 9.98 |
| Joost-Pieter Katoen | 2 | 4444 | 289.65 |
| Ymte Westra | 3 | 4 | 0.53 |
| Henk Alblas | 4 | 86 | 8.79 |