ABSTRACT
The tupling transformation strategy can be used to merge loops together by combining recursive calls and also to eliminate redundant calls for a class of programs. The clever (and difficult) step of this transformation strategy is to find an appropriate tuple of calls, called the eureka tuple, which would allow each set of calls to be computed recursively from its previous set. In many cases, this transformation can produce super-linear speedup.
In this paper, we present an analysis method which could find eureka tuples for a wide range of functional programs. Our work extends that of a number of past techniques which have used dependency graphs of function calls for analysing redundancy patterns. Our main contribution is the use of appropriate call orderings based on recursion parameters to systematically search for eureka tuples in dependency graphs. They allow us to construct sequences of tuples, called the continuous sequences of tuples, whereby the existence of a matched pair of tuples in the sequence corresponds to a suitable eureka tuple.
An extension of the basic analysis method which uses trees, instead of sequences, of tuples will also be presented. The basic and extended analysis methods will be shown to be applicable to a wide range of programs. They can be guaranteed to terminate by either bounding the search or by applying suitable restrictions on the class of applicable programs. The latter approach yields a safe automated procedure for tupling transformation.
Index Terms
- Towards an automated tupling strategy
Recommendations
Tupling calculation eliminates multiple data traversals
Tupling is a well-known transformation tactic to obtain new efficient recursive functions by grouping some recursive functions into a tuple. It may be applied to eliminate multiple traversals over the common data structure. The major difficulty in ...
Tupling calculation eliminates multiple data traversals
ICFP '97: Proceedings of the second ACM SIGPLAN international conference on Functional programmingTupling is a well-known transformation tactic to obtain new efficient recursive functions by grouping some recursive functions into a tuple. It may be applied to eliminate multiple traversals over the common data structure. The major difficulty in ...
Redundant Call Elimination via Tupling
Program Transformation: Theoretical Foundations and Basic Techniques. Part 2Redundant call elimination has been an important program optimisation process as it can produce super-linear speedup in optimised programs. In this paper, we investigate use of the tupling transformation in achieving this optimisation over a first-order ...
Comments