Compiling pattern matching to in-place modifications
summary
Prototype compiles pattern-match rewrite rules on tree-shaped ADTs stored as arrays only into in-place memory moves, not pointer rewrites. It cuts trees into BFS layers (phi_k), expresses move dependencies as linear relations, hands them to an ILP scheduling step and then emits C loops via a polyhedral scanner (Quillere algorithm). The prototype produces correct sequential code for non-recursive, guard-free rules and plans to add recursion, guards and parallel code generation.
AI-written summary · about
chapters (10)
- 0:00Intro
- 1:29A Language to Describe Structural Transformations
- 2:17Stepl: Compute Subtree Movements on Pull Up
- 3:02Use Layers to Subdivide Memory Movements on Pull Up
- 3:34Layer-aware movements (1/2) on Pull Up
- 5:00Characterizing Memory Movements of Pull Up (Source)
- 5:34Characterizing Memory Movements of Pull Up (Dependencies)
- 6:02Scheduling as an Integer Linear Program Problem
- 6:38From Schedule to Code
- 6:53Conclusion & Future Work
related talks
23mHigher order Patterns in Rewrite Rules
29mPredicate Dispatch
01h 00m“Using Compile-time Code Generation to build an LLVM IR Pattern Matcher”
29mTrieste: A C++ DSL for Flexible Tree Rewriting (Tool paper)
29mSafe Pattern Generation for Multi-Stage Programming
23mPattern-matching on mutable values: danger!
25mAUTOMAP: Inferring Rank-Polymorphic Function Applications with Integer Linear Programming
51mSimple, Extensible Pattern Matching in C++14