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.

    [img]
    Preview
    Download (655kB) | Preview


    Share your research

    Twitter Facebook LinkedIn GooglePlus Email more...



    Add this article to your Mendeley library


    Abstract

    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: https://doi.org/10.1145/1133255.1133988
    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
    URI:

    Repository Staff Only(login required)

    View Item Item control page

    Downloads

    Downloads per month over past year