BURG < Transform

BURG is a system for CodeGeneration from IntermediateRepresentation^? expression trees developed by ChristopherFraser, ToddProebsting and others in the early 90's.

Papers

C. W. Fraser, D. R. Hanson, and T. A. Proebsting. Engineering a simple, efficient code-generator generator. ACM Letters on Programming Languages and Systems, 1(3):213--226, September 1992.

C. W. Fraser, R. R. Henry, and T. A. Proebsting. BURG---fast optimal instruction selection and tree parsing. ACM SIGPLAN Notices, 27(4):68--76, April 1992.

T. A. Proebsting. BURS automata generation. ACM Transactions on Programming Languages and Systems, 17(3):461--486, May 1995.

Description

BURG is a system for code generation from intermediate expression trees. A mapping from intermediate representation trees to machine instruction is defined by means of a tree grammar. A production of the form n -> t (c) defines a mapping of tree pattern t to non-terminal n at cost c. Associated with each production is an action to take when the production is selected. For example, ToddProebsting gives the following example grammar:

  [1] goal -> reg            (0)  [5] reg  -> Plus(reg, reg) (2)
  [2] reg  -> Reg            (0)  [6] addr -> reg            (0)
  [3] reg  -> Int            (1)  [7] addr -> Int            (0)
  [4] reg  -> Fetch(addr)    (2)  [8] addr -> Plus(reg, Int) (0)

According to this grammar, the term Fetch(Fetch(Plus(Reg,Int))) has two coverings corresponding to the derivations 4(4(6(5(2,3)))) and 4(4(8(2))).

As illustrated by this example, more than one covering of a tree is possible, corresponding to different ways to generate code. Each node can have several different parses because of overlapping patterns and chain rules. The costs associated with the productions express the cost of executing the associated machine instruction. The goal of a code generator is to find the lowest cost covering (i.e., lowest execution time) of an intermediate representation expression tree.

According to bottom-up rewriting theory (BURS) an intermediate representation tree can be translated to a sequence of instructions using the following strategy. In a bottom-up traversal all lowest-cost patterns that match each node are computed and associated with the node. This involves matching the righ-hand sides of the productions to the tree, taking into account earlier matches for sub-trees. Instructions are then selected in a top-down traversal that is driven by the goal non-terminal for the root of the tree.

This restricted form of rewriting can also be applied for simple type inference problems, for checking tree formats, and for tree simplifications.

-- EelcoVisser - 30 Apr 2001

CategorySystem

Revision: r1.2 - 18 Sep 2001 - 06:27 - TWikiGuest

Transform > BURG