An Updated Framework for Compilation Goals: * Simplify compiler (# lines of code) * Speed up compiler * Speed up compiled code Unifying disparate analyses: * Abstract interpretation * Constraint graph solution Information sources: * Code and data profiling * Static models * User interface Maintaining information: * Dependence maintenance * Knowledge representation * Consistency * Incrementality * Better CFG / DFG abstractions Information sinks: * Program specialization * Automatic implementation selection * Optimizations * User interface Control structure: * Explicit goals, tactics, and strategy * Compilation as search * Online vs. offline compilation * Assessing benefit per compilation time * Compiler directed profiling Learning and extensibility: * Making representations simple and explicit * Taking direction from user * Revising and creating static models * Optimizations as schemas * Learning applicability and utility * Forming compound transformations * Discovering interactions ----------------------------- * Structure of a typical compiler A typical compiler is structured as a sequence of transformations that operate on various representations of a program. It is large and difficult to construct and maintain. It is unintelligent, in that it uses relatively local and inaccurate information, chooses from among a small set of options, and does not examine its decisions after making them. By looking at compilation from a more sophisticated point of view, it may be possible to repair these defects. Using approaches learned from computer architecture, programming language semantics, and artificial intelligence, compilers can be made less monolithic and more powerful. These approaches include: * Abstract interpretation By providing a single set of support mechanisms for abstract interpretation, various kinds of information can be extracted from a program and various transformations can be applied simply and uniformly. * Constraint set solution Using program information, a compiler makes choices under a set of constraints. Examples include register allocation, type inference, data placement, and thread partitioning. These typically distinct operations can be unified through a general mechanism for solving systems of constraints. The process of constraint solution may possibly be made more efficient by providing further information about the system under consideration. It is also valuable to consider different methods of constraint solution for different systems of constraints (real, integer, boolean, equalities, inequalities, etcetera). * Automatic implementation selection The most general implementation of a programming language feature is not efficient for simple cases. For example, consider choosing representations for environments or continuations. A compiler does not take an implementation or specification and transform it into a more efficient one. Rather, it serves as an intelligent librarian and manages a set of parametrized system and user-specified alternative implementations for commonly used abstractions. Abstract data types are essential to automatic implementation selection because we need precise knowledge of the interface between client and abstraction. The compiler needs to prove that a structure is used in a limit set of ways so that it may adjust the implementation (or even the interface) appropriately. It may also be possible for a program simplifier to eliminate operations entirely using identies such as (car (cons a b)) = a, etcetera. A general implementation can be partially evaluated with respect to one or more of its inputs to produce a specialized implementation. That is, we can derive a family of specialized implementations from a single general implementation. Consider the example of a store in which only three locations are used. We should be able to implement it as a triple. * Partial evaluation / Program Specialization We should first note that program specialization is not a monolithic operation. It is more like a compiler that uses many techniques: * inlining and unrolling * constant propagation and folding * arity reduction (dead argument elimination) * algebraic identities (x*0 = 0, etc) There are two difficulties with the control of this process: * what data to specialize on * how much specialization to perform Hopefully, we can use dynamic information to control the amount of specialization. That is, we transform as long as the program runs faster. As for what data to specialize on, we can use all of our sources of information. * Dynamic information There is a continuum of information available as a program runs. Later information is more accurate but also more expensive to collect. We can perform both code and data profiling. Code profiling shows which pieces of code execute most often and thus deserve the most attention via program transformation. Data profiling tells us which data values appear most often. These may be used for specialization. * Sources of information We can obtain information by * static analysis * dynamic analysis * code and data profiling * user interaction * Types of information We can categorize information along several axes: * Data dependent vs. Data independent * Certain vs. uncertain * Relative vs. absolute There are undoubtedly others, both orthogonal and non-orthogonal. Data dependent: Procedure A always calls procedure B when its argument is 5. Data independent: Procedure A always calls procedure B Certain: Procedure A always calls procedure B. Uncertain: Procedure A often calls procedure B. Absolute: Procedure A is always called. Relative: Procedure A is always called if procedure B is called. Dynamic data can be certain: "procedure A was called with argument 5." * Knowledge representation We can use a knowledge representation system to maintain information about compilation in general and about decisions made while compiling particular programs. Also, a knowledge representation system improves modularity by providing a place for new data when it is acquired. We can say "allocate a slot for X", rather than having to pre-allocate it and maintain it through computations that have nothing to do with it. In order to think, a compiler must have memory. Especially in order to do better in the future than it is doing now. Also, in order to be fast, it must cache various computations. * Consistency The information that a compiler maintains must be kept consistent as the program changes and as assumptions are made and retracted. We have: * source code * intermediate representation * object code * results of static analysis * dynamic information Notice that Scheme has difficulty even maintaining consistency between the editor's representation of the program and the interpreter's. * Incrementality For efficiency, when we make a small change in one representation, we'd like to make as small a change as possible in others. The easiest way get a job done is not to do it at all. Compilers regularly re-do 90% of the work done on the last compilation. We can speed up by not doing work! Languages with per-procedure compilation have solved this problem but use only restricted information. Incrementality is an engineering issue, but the question it raises is fundamental: can we make a given computation incremental? How local is the change in information? * User interface Compilers presently don't talk to the user and discuss what changes to make to the code in order to improve performance or alter functionality. Suppose you knew that a certain variable value was large. Building the compiler on a knowledge representation system could improve user interaction greatly. Except when the user chooses to interact with it, a compiler should be invisible. All the user needs to know is that his code runs. * Dependency maintenance Negative information must be maintained as well. Why did you garbage collect this object? There were no references to it. When is that assumption invalidated? For example, why did the compiler inline the value of this variable? Well, no assignments to it occur. Why did you do X? Because none of the 50,000 reasons not to was found, and I felt like it. Well, you can't record 50,000 reasons; you have to summarize. * CFG / DFG data abstractions Is there an intermediate level between a program and control flow / data flow graph, a language which reflects program semantics and in which optimizations can be written more easily? Operations on a program graph must maintain all structure which has been built into the graph. Therefore, each operation must know about all that structure, which breaks modularity. Can we simplify the structure and build transforms out of basic operators which preserve the graph? * Semantics Without an extremely clear semantic framework, a compiler becomes a tangle of detail without apparent intent. Scheme is particularly difficult because the control flow graph is not finite, and a very clear knowledge of the compile-time approximations to run-time environments is required (see Olin Shivers's work). * Information comes out of phases, not just into them Morry Katz and Daniel Weise's specializer tells you what information it used. A phase could also suggest what information would be useful. The costs and values of getting various pieces of information could be considered. * "Anytime" program execution If a compiler is given a long time to work, it can do better. If it is given a short time, it can't do as well. Can it account for amount of execution time improvement per amount of compile time? For instance, it can use idle machine cycles to perform experiments in optimizing specific programs. * Theories A compiler is a set of theories about language constructs and object machines. This theory is built from knowledge of various forms, both declarative and procedural. Often the procedural knowledge can be cast in a common form such as program specialization or constraint graph solution. This work is a reconsideration and reformulation of the theories used to build compilers. * Algorithms In some places in a compiler, an actual algorithm is necessary to compute a structure satisfying various properties. Many times, this algorithm is of a general form captured by one of the other categories. But sometimes, it is clear from properties of the language being compiled or of the object machine that a particular algorithm is exactly the right thing with which to build the theory. Sometimes a specific form of procedural knowledge is needed to build the proper theory. But what is expensive about optimization? Deciding when an optimization can be applied, or applying it? * Learning compilers A compiler can learn which optimizations to apply where and when. It can learn which choices for implementation selection are best and which procedures to specialize on what inputs. It can accumulate this knowledge over the lives of individual programs and over the life of the compiler. Learning means noticing new relationships and incorporating them into the compiler's knowledge base. Gary Drescher's work provides an excellent framework for a learning compiler. How to learn the interactions between various optimizations? A compiler can work "off-line" to compile your code or it can work "on-line" while the program is running. Then the expenditure in compile time must be worth the decrease in run time. However, it is expensive to gather, and a compiler must learn why given choices were effective and be able to make them again without having to experiment all over again. Notice that "dependency noticing" is a very deep form of learning. By accumulating knowledge, the compiler can improve its performance over time. * Generic representations The operations do calculations which can be cached and incrementally updated (check Alphonse from PLDI!). Also, different graph representations can be switched back and forth like polar and rectangular for complex numbers. This may waste time, but efficiency ruins everything. * Extensibility Mike Eisenberg writes about "programmable applications." I should think that a compiler would want to be one of them. Extensibility can be new knowledge about optimizations, new optimizations, or new implementations of data types. It can be new schemas in Drescher's sense. So it's a matter of incorporating this knowledge into an existing framework (and having a framework general enough to accept this information). The language which the compiler speaks to itself should be similar to the language spoken with the user. The two should be able to cooperate. The user can also teach the compiler. The set of objects which the compiler manipulates should be relatively small, and it should be able to learn new ones. The user should be able to understand all the objects which the compiler uses. All these objects should have very clear semantics. * Self-knowledge A program can (probably) only improve its performance to the extent that it knows itself, i.e., has explicit representations of its goals. Ken Haase's work on self-representing discovery systems begins to expresses this idea. A compiler needs an overall control strategy in order to decide how to spend its time. * Compilation as search If we view compilation as making a sequence of choices and can explicitly make each one, then we can perfom heuristic search over the resulting tree using data of various forms: user input, static models, dynamic information. For example, optimization can focus on "the ten percent of the code which takes ninety percent of the time." Use dependency directed backtracking... The compiler can maintain a record of decisions involved in the compilation of a particular program. When modification of compilation choices does not result in increased performance, decisions can be revoked according to knowledge about interactions between choices. This knowledge can be accumulated automatically by experiment. Morry and Daniel's specializer tells you what information it used. * Parallelism These comments are incidental, rather than essential. In essence, the problems of sequential compilation are magnified in a parallel machine because the performance of parallel code can vary greatly and is difficult to predict. * Hardware considerations At present, code optimization assumes that a transformation will be useful under a known set of circumstances that can be checked at compile time. However, the interactions of various parts of a computer architecture are impossible to foresee, and different hardware conditions can affect the optimality of compiled code. These considerations imply that decisions can be most accurately based on data collected during execution.