Solving regular tree grammar based constraints

Abstract. This paper describes the precise specication, design, analy-sis, implementation, and measurements of an eÆcient algorithm for solv-ing regular tree grammar based constraints. The particular constraints are for dead-code elimination on recursive data, but the method used for the algorithm design and complexity analysis is general and applies to other program analysis problems as well. The method is centered around Paige's nite dierencing, i.e., computing expensive set expressions incre-mentally, and allows the algorithm to be derived and analyzed formally and implemented easily. We propose higher-level transformations that make the derived algorithm concise and allow its complexity to be an-alyzed accurately. Although a rough analysis shows that the worst-case time complexity is cubic in program size, an accurate analysis shows that it is linear in the number of live program points and in other parame-ters, including mainly the arity of data constructors and the number of selector applications into whose arguments the value constructed at a program point might ow. These parameters explain the performance of the analysis in practice. Our implementation also runs two to ten times as fast as a previous implementation of an informally designed algorithm.