A compiler's optimizer operates over abstract syntax trees (ASTs), continuously applying rewrite rules to replace subtrees of the AST with more efficient ones. Especially on large source repositories, even simply finding opportunities for a rewrite can be expensive, as optimizer traverses the AST naively. In this paper, we leverage the need to repeatedly find rewrites, and explore options for making the search faster through indexing and incremental view maintenance (IVM). Concretely, we consider bolt-on approaches that make use of embedded IVM systems like DBToaster, as well as two new approaches: Label-indexing and TreeToaster, an AST-specialized form of IVM. We integrate these approaches into an existing just-in-time data structure compiler and show experimentally that TreeToaster can significantly improve performance with minimal memory overheads.

翻译：编译器的优化对抽象语法树( ASTs) 进行操作, 不断应用重写规则以更有效率的树取代 AST 子树 。 特别是在大型源库中, 简单地寻找重写的机会可能非常昂贵, 因为优化者会天真地翻翻 AST 。 在本文中, 我们利用反复查找重写文件的需要, 并探索通过索引和递增视图维护( IVM) 来加快搜索速度的选项。 具体地说, 我们考虑使用嵌入的 IVM 系统( 如 DBToaster ) 以及两种新办法( label- 索引和 TreeToaster ) 。 我们将这些方法整合到现有的实时数据结构编译器中, 实验性地显示, TreaToster 可以用最小的记忆管理器大大改进性能 。