Inter-procedural Control Flow Analysis of First Order Programs with Tail Call Optimization

Saumya Debray Todd Proebsting
Department of Computer Science
University of Arizona
Tucson, AZ 85721, U.S.A.

Note to the Reader : Originally, the abstract for this paper was as follows:

The analysis of control flow
Involves finding where returns may go.
How this can be done
With items LR(0) and (1)
Is what in this paper we show.

Of all the abstracts I've written, this is my favorite; it's certainly the most succinct, and the only one that has any semblance of rhyme and meter. However, it was felt that this was unsuitable a Serious Journal like TOPLAS, so we ended up rewriting the abstract to that given below.
-SKD

Abstract

Knowledge of low-level control flow is essential for many compiler optimizations. In systems with tail-call optimization, the determination of interprocedural control flow is complicated by the fact that because of tail-call optimization, control flow at procedure returns is not readily evident from the call graph of the program. This article shows how interprocedural control-flow analysis of first-order programs can be carried out using well-known concepts from parsing theory. In particular, we show that context-insensitive (or zeroth-order) control-flow analysis corresponds to the notion of FOLLOW sets in context-free grammars, while context-sensitive (or first-order) control-flow analysis corresponds to the notion of LR(1) items. The control-flow information so obtained can be used to improve the precision of interprocedural dataflow analyses as well as to extend certain low-level code optimizations across procedure boundaries.