Control Flow Analysis in Scheme

Traditional flow analysis techniques, such as the ones typically employed by optimising Fortran compilers, do not work for Scheme-like languages. This paper presents a flow analysis technique- control flow analysis- which is applicable to Scheme-like languages. As a demonstration application, the information gathered by control flow analysis is used to per-form a traditional flow analysis problem, induction variable elimination. Extensions and limitations are discussed. The techniques presented in this paper are backed up by working code. They are applicable not only to Scheme, but also to related languages, such as Common Lisp and ML. 1 The Task Flow analysis is a traditional optimising compiler technique for determining useful information about a program at compile time. Flow analysis determines path invariant facts about points in a program. A flow analysis problem is a question of the form: “What is true at a given point p in my program, in-dependent of the execution path taken to p from the start of the program?” Example domains of interest might be the following: l Range analysis: What is the range of values that a given reference to an integer variable is constrained to he within? Range analysis can be used, for instance, to do array bounds checking at compile time, l Loop invariant detection: Do all possible prior assign-ments to a given variable reference lie outside its contain-ing loop? Over the last thirty years, standard techniques have been de-veloped to answer these questions for the standard imperative, Algol-like languages (e.g., Pascal, C, Ada, Bliss, and chiefly Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the ACM copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Association fo