Optimal code generation for expression trees: an application BURS theory
Optimal code generation for expression trees: an application BURS theory
复制标题
表达式树的最优代码生成：BURS 理论的应用
DOI：
10.1145/73560.73586
复制
发表时间：
1988
期刊：
影响因子：
--
通讯作者：
S. Graham
中科院分区：
文献类型：
--
作者：
Eduardo Pelegrí;S. Graham
<斜体>重写系统</斜体>是<斜体>重写规则</斜体>的集合，其形式为α β，其中α和β是树模式。可以通过将成本与每个重写规则相关联，以及通过将重写序列的成本定义为序列中所有重写规则的成本之和来扩展重写系统。重写系统 R 的 REACHABILITY 问题是，给定输入树 T 和固定目标 G 树，确定 R 中是否存在重写序列，将 T 重写为 G，如果存在，则获取一个这样的序列。 C-REACHABILITY 问题类似，只是获得的序列必须在所有将 <italic>T</italic> 写入 <italic>G</italic> 的序列中具有最小成本。
本文介绍了一类称为自下而上重写系统（BURS）的重写系统，以及一种用于解决该类成员可达性的表驱动算法。然后修改该算法以解决 C-REACHABILITY 问题，并专门用于 BURS 的子类，以便将所有成本操作编码到表中，并且在求解时不会显式执行。该子类扩展了<斜体>简单机器语法</斜体>[AGH84]，通过允许其他类型的重写规则（例如交换性变换）来重写用于描述代码生成的目标机器体系结构的系统。
基于求解 C-REACHABILITY 的表驱动代码生成器已经实现并通过多种机器描述进行了测试。代码生成器比基于 Graham-Glanville 技术 [AGH84]（非最佳技术）的同类求解器更快地求解 C-REACHABILITY，但只需要稍大的表。代码生成器的运行速度比最近提出的解决 C-REACHABILITY 的方案要快得多，后者使用模式匹配并在求解时显式处理成本 [AGT86、HeD87、WeW86]。 BURS 理论概括并统一了 Henry/Damron [HeD87] 和 Weisgerber/Wilhelm [WeW86] 的自下而上的方法。
A <italic>Rewrite System</italic> is a collection of <italic>rewrite rules</italic> of the form α β where α and β are tree patterns. A rewrite system can be extended by associating a cost with each rewrite rule, and by defining the cost of a rewrite sequence as the sum of the costs of all the rewrite rules in the sequence. The REACHABILITY problem for a rewrite system <italic>R</italic> is, given an input tree <italic>T</italic> and a fixed <italic>goal</italic> tree <italic>G</italic>, to determine if there exists a rewrite sequence in <italic>R</italic>, rewriting <italic>T</italic> into <italic>G</italic> and, if so, to obtain one such sequence. The C-REACHABILITY problem is similar except that the obtained sequence must have minimal cost among all those sequences writing <italic>T</italic> into <italic>G</italic>.
This paper introduces a class of rewrite systems called Bottom-Up Rewrite Systems (BURS), and a table-driven algorithm to solve REACHABILITY for member of the class. This algorithm is then modified to solve C-REACHABILITY and specialized for a subclass of BURS so that all cost manipulation is encoded into the tables and is not performed explicitly at solving time. The subclass extends the <italic>simple machine grammars</italic> [AGH84], rewrite systems used to describe target machine architectures for code generation, by allowing additional types of rewrite rules such as commutativity transformations.
A table-driven code generator based on solving C-REACHABILITY has been implemented and tested with several machine descriptions. The code generator solves C-REACHABILITY faster than a comparable solver based on Graham-Glanville techniques [AGH84] (a non-optimal technique), yet requires only slightly larger tables. The code generator runs much faster than recent proposals to solve C-REACHABILITY that use pattern matching and deal with costs explicitly at solving time [AGT86, HeD87, WeW86]. The BURS theory generalizes and unifies the bottom-up approaches of Henry/Damron [HeD87] and Weisgerber/Wilhelm [WeW86].