Institutions | About Us | Help | Gaeilge
rian logo


Mark
Go Back
Fast and flexible instruction selection with on-demand tree-parsing automata
Ertl, Anton; Casey, Kevin; Gregg, David
Tree parsing as supported by code generator generators like BEG, burg, iburg, lburg and ml-burg is a popular instruction selection method. There are two existing approaches for implementing tree parsing: dynamic programming, and tree-parsing automata; each approach has its advantages and disadvantages. We propose a new implementation approach that combines the advantages of both existing approaches: we start out with dynamic programming at compile time, but at every step we generate a state for a tree-parsing automaton, which is used the next time a tree matching the state is found, turning the instruction selector into a fast tree-parsing automaton. We have implemented this approach in the Gforth code generator. The implementation required little effort and reduced the startup time of Gforth by up to a factor of 2.5.
Keyword(s): instruction selection; tree parsing
Publication Date:
2006
Type: Journal article
Peer-Reviewed: Yes
Institution: Maynooth University
Citation(s): Ertl, Anton and Casey, Kevin and Gregg, David (2006) Fast and flexible instruction selection with on-demand tree-parsing automata. ACM SIGPLAN Notices - Proceedings of the 2006 PLDI Conference, 41 (6). pp. 52-60.
Publisher(s): ACM
File Format(s): other
Related Link(s): http://eprints.maynoothuniversity.ie/10195/1/KC-Fast-2006.pdf
First Indexed: 2018-11-09 06:00:35 Last Updated: 2018-11-09 06:00:35