Owen Kaser
C. R. Ramakrishnan
Abstract
Procedure inlining can be used to convert mutual recursion to direct recursion. This allows use of optimization techniques that are most easily applied to directly recursive procedures, in addition to the well-known benefits of inlining. We present tight (necessary and sufficient) conditions under which inlining can transform all mutual recursion to direct recursion, and those under which heuristics to eliminate mutual recursion always terminate. We also present a technique to eliminate mutually recursive circuits that consist of only tail calls. From this, we conclude that tail recursion elimination should be interleaved with inlining.
- BALL, J. 1982. Program improvement by the selective integration of procedure calls. Ph.D. thesis, Univ. of Rochester, Rochester, N.Y. Google Scholar
- CHANG, P., MAHLKE, S., CHEN, W., AND HWU, W. 1992. Profile-guided automatic inline expansion for C programs. Softw. Prac. Exp. 25, 5, 349-369. Google Scholar
- DAVIDSON, J., AND HOLLER, A. 1988. A study of a C function inliner. Soflw. Prac. Exp. 18, 8, 775-790. Google Scholar
- HARTLEY, S. 1988. Compile-time program restructuring in multiprogrammed virtual memory systems. IEEE Trans. Softw. Eng. 14, 11, 1640-1644. Google Scholar
- Hwu, W., AND CHANG, P. 1989a. Achieving high instruction cache performance with an optimizing compiler. In Proceedings of the 16th Annual Symposzum on Computer Architecture. ACM, New York, 242-251. Google Scholar
- Hwu, W., AND CHANG, P. 1989b. Inline function expansion for compiling C programs. In Procee&ngs of the SIGPLAN "89 Conference on Programming Language Design and Implementation. ACM, New York, 246-255. Google Scholar
- KASER, O. 1993. Inlining to reduce stack space. In the International Symposium on Programming Language Implementation and Logic Programming. Lecture Notes in Computer Science, vol. 714. Springer-Verlag, New York. Google Scholar
- KASER, O., PAWAGI, S., RAMAKRISHNAN, C., RAMAKRISHNAN, I., AND SEKAR, R. 1992a. Fast parallel implementations of lazy languages--the EQUALS experience. In Proceedings of the ACM Conference on LISP and Functional Programming. ACM, New York, 335-344. Google Scholar
- KASER, O., RAMAKRISHNAN, C., AND PAWAGI, S. 1992b. A new approach to inlining. Tech. Rep. 92/06, State Univ. of New York, Stony Brook, N.Y.Google Scholar
- MCFARLING, S. 1991. Procedure merging with instruction caches. In Proceedings of the SIG- PLAN '91 Conference on Programming Language Design and Implementation. ACM, New York, 71-79. Google Scholar
- PLUMER, L. 1990. Termination proofs for logic programs based on predicate inequalities. In Proceedings of the 7th international Conference on Logic Programming. 634-648. Google Scholar
- SCHEIFLER, R. 1977. An analysis of inline substitution for a structured programming language. Commun. ACM 20, 647-654. Google Scholar
- SKIENA, S. 1985. Compiler optimization by detecting recursive subprograms. In the 1985 ACM Annual Conference. ACM, New York, 403-411. Google Scholar
- THULASIRAMAN, K., AND SWAMI, M. 1992. Graphs: Theory and Algorithms. John Wiley and Sons, New York. Google Scholar
- WALTP.R, K. 1976. RecurMon analysi~ for compiler optimization. Commun. ACM 19, 514-516. Google Scholar
Index Terms
- On the conversion of indirect to direct recursion
Recommendations
A note on “On the conversion of indirect to direct recursion”
In the article “On the Conversion of Indirect to Direct Recursion”(ACM Lett. Program. Lang. 2, 1-4. pp. 151-164), a method was introduced to convert indirect to direct recursion. It was claimed that for any call graph, there is a mutual-recursion ...
A gentle introduction to mutual recursion
ITiCSE '08Recursion is an important topic in computer science curricula. It is related to the acquisition of competences regarding problem decomposition, functional abstraction and the concept of induction. In comparison with direct recursion, mutual recursion is ...
A gentle introduction to mutual recursion
ITiCSE '08: Proceedings of the 13th annual conference on Innovation and technology in computer science educationRecursion is an important topic in computer science curricula. It is related to the acquisition of competences regarding problem decomposition, functional abstraction and the concept of induction. In comparison with direct recursion, mutual recursion is ...
Reviews
R. Clayton
Inline expansion replaces a call to a procedure with the procedure's body. Inline expansion, among other benefits, eliminates procedure call overhead and improves addressing locality. Recursion presents a problem, since a recursive call has an infinite inline expansion. In direct recursion, a procedure contains a call to itself; in indirect recursion, procedure A calls procedure B which (calls procedure C which…) calls procedure A. Direct recursion is preferred over indirect recursion because direct recursion is simpler to eliminate or simulate, and some program analyses can handle only direct recursion. The authors develop a nontrivial condition indicating when it is possible to convert indirect recursion to direct recursion, and give an algorithm for the conversion. They examine the interactions between expansion and tail-call elimination and show that the special case of indirect recursion involving only tail recursion can always be converted to direct recursion. The authors also show that the termination rule of not expanding directly recursive procedures is not by itself strong enough to avoid infinite expansion. The assumptions used in the paper are modest, the data structures used are common to compilers, and the analysis techniques are not expensive. The paper itself is short and clear.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments