Common Lisp the Language, 2nd Edition

Next: Constraint Cycles Up: Optimization Previous: Optimization

A.3.1. Basic Restrictions

The transformation of series expressions into loops is required to occur at some time before compiled code is actually run. Optimization may or may not be applied to interpreted code. If any of the restrictions described below are violated, optimization is not possible. In this situation, a warning message is issued at the time optimization is attempted and the code is left unoptimized. This is not a fatal error and does not prevent the correct results from being computed. However, given the large improvements in efficiency to be gained, it is well worth fixing any violations that occur. This is usually easy to do.

[Variable]
*suppress-series-warnings*

If this variable is set (or bound) to anything other than its default value of nil, warnings about conditions that block the optimization of series expressions are suppressed.

Before the restrictions on series expressions are discussed, it will be useful to define precisely what is meant by the term series expression. This term is semantic rather than syntactic in nature. Imagine a program converted from Lisp code into a data flow graph. In a data flow graph, functions are represented as boxes, and both control flow and data flow are represented as arrows between the boxes. Constructs such as let and setq are converted into patterns of data flow arcs. Control constructs such as if and loop are converted into patterns of control flow arcs. Suppose further that all loops have been converted into tail recursions so that the graph is acyclic.

A series expression is a subgraph of the data flow graph for a program that contains a group of interacting series functions. More specifically, given a call f on a series function, the series expression E containing it is defined as follows. E contains f. Every function using a series created by a function in E is in E. Every function computing a series used by a function in E is in E. Finally, suppose that two functions g and h are in E and that there is a data flow path consisting of series and/or non-series data flow arcs from g to h. Every function touched by this path (be it a series function or not) is in E.

For optimization to be possible, series expressions have to be statically analyzable. As with most other optimization processes, a series expression cannot be transformed into a loop at compile time, unless it can be determined at compile time exactly what computation is being performed. This places a number of relatively minor limits on what can be written. For example, for optimization to be possible the type arguments to higher-order functions such as map-fn and collecting-fn have to be quoted constants. Similarly, the numeric arguments to chunk have to be constants. In addition, if funcall is used to call a series function, the function called has to be of the form (function ...).

For optimization to be possible, every series created within a series expression must be used solely inside the expression. If a series is transmitted outside of the expression that creates it, it has to be physically represented as a whole. This is incompatible with the transformations required to pipeline the creating expression. To avoid this problem, a series must not be returned as a result of a series expression as a whole, assigned to a free variable, assigned to a special variable, or stored in a data structure. A corollary of the last point is that when defining new optimizable series functions, series cannot be passed into &rest arguments. Further, optimization is blocked if a series is passed as an argument to an ordinary Lisp function. Series can be passed only to the series functions in section A.2 and to new series functions defined using the declaration optimizable-series-function.

For optimization to be possible, series expressions must correspond to straight-line computations. That is to say, the data flow graph corresponding to a series expression cannot contain any conditional branches. (Complex control flow is incompatible with pipelining.) Optimization is possible in the presence of standard straight-line forms such as progn, funcall, setq, lambda, let, let*, and multiple-value-bind as long as none of the variables bound are special. There is also no problem with macros as long as they expand into series functions and straight-line forms. However, optimization is blocked by forms that specify complex control flow (i.e., conditionals if, cond, etc., looping constructs loop, do, etc., or branching constructs tagbody, go, catch, etc.).

In the first example below, optimization is blocked, because the if form is inside the series expression. In the second example, however, optimization is possible, because although the if feeds data to the series expression, it is not inside the corresponding subgraph. Both of the expressions below produce the same value, but the second one is much more efficient.

(collect (if flag (scan x) (scan y)))  ;Warning message issued 
(collect (scan (if flag x y)))

Next: Constraint Cycles Up: Optimization Previous: Optimization

AI.Repository@cs.cmu.edu