MURAL - Maynooth University Research Archive Library

    Fast and flexible instruction selection with on-demand tree-parsing automata

    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.

    Download (655kB) | Preview

    Share your research

    Twitter Facebook LinkedIn GooglePlus Email more...

    Add this article to your Mendeley library


    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.

    Item Type: Article
    Additional Information: Also available in PLDI '06 Proceedings of the 27th ACM SIGPLAN Conference on Programming Language Design and Implementation. Pages 52-60. ISBN 1-59593-320-4
    Keywords: instruction selection; tree parsing;
    Academic Unit: Faculty of Science and Engineering > Research Institutes > Hamilton Institute
    Item ID: 10195
    Identification Number:
    Depositing User: Hamilton Editor
    Date Deposited: 08 Nov 2018 17:23
    Journal or Publication Title: ACM SIGPLAN Notices - Proceedings of the 2006 PLDI Conference
    Publisher: ACM
    Refereed: Yes
    Use Licence: This item is available under a Creative Commons Attribution Non Commercial Share Alike Licence (CC BY-NC-SA). Details of this licence are available here

    Repository Staff Only(login required)

    View Item Item control page


    Downloads per month over past year

    Origin of downloads