Profiling can provide the information needed to identify performance bottlenecks in a program, but the programmer must understand its relation to the program source in order to use this information. This is di#cult due to the tremendous volume of data collected. Moreover, program transformations such as macro expansion and procedure inlining can obscure the relationship between the source and object code. Higher-order programs present additional challenges due to complex control flow and because they often consist of many small, often anonymous, procedures whose individual performance properties may be less interesting than their characteristics as a group. To address these challenges we have implemented a profiler and interactive profile visualizer and integrated them into an optimizing Scheme compiler. The profiler instruments target code and maintains correlation with the original source despite compiler optimizations that can eliminate, duplicate, or move code. The visualizer oper...

A flow analysis collects data-flow and control-flow information about programs. A compiler can use this information to enable optimizations. The analysis described in this article unifies and extends previous work on flow analysis for higher-order languages supporting assignment and control operators. The analysis is abstract interpretation based and is parameterized over two polyvariance operators and a projection operator. These operators are used to regulate the speed and accuracy of the analysis. An implementation of the analysis is incorporated into and used in a production Scheme compiler. The analysis can process any legal Scheme program without modification. Others have demonstrated that a 0CFA analysis can enables the optimizations, but a 0CFA analysis is O ( n ) 3 ). An O ( n ) instantiation of our analysis successfully enables the optimization of closure representations and procedure calls. Experiments with the cheaper instantiation show that it is as effective as 0CFA for these optimizations.

An interprocedural flow analysis can justify inlining in higher-order languages. In principle, more inlining can be performed as analysis accuracy improves. This paper compares four flow analyses to determine how effectively they justify inlining in practice. The paper makes two contributions. First, the relative merits of the flow analyses are measured with all other variables held constant. The four analyses include two monovariant and two polyvariant analyses that cover a wide range of the accuracy/cost spectrum. Our measurements show that the effectiveness of the inliner improves slightly as analysis accuracy improves, but the improvement is offset by the compile-time cost of the accurate analyses. The second contribution is an improvement to the previously reported inlining algorithm used in our experiments. The improvement causes flow information provided by a polyvariant analysis to be selectively merged. By merging flow information depending on the inlining context, the algorithm is able to expose additional opportunities for inlining. This merging technique can be used in any program transformer justified by a polyvariant flow analysis. The revised algorithm is fully implemented in a production Scheme compiler.

A flow analysis collects data-flow and control-flow information about programs. A compiler can use this information to enable optimizations. The analysis described in this article unifies and extends previous work on flow analyses for higher-order languages supporting assignment and control operators. The analysis is abstract interpretation based and is parameterized over two polyvariance operators and a projection operator. These operators are used to regulate the speed and accuracy of the analysis. An implementation of the analysis is incorporated into and used in a production Scheme compiler. The analysis can process any legal Scheme program without modification. Others have demonstrated that a 0CFA analysis can enable optimizations, but a 0CFA analysis is O(n3). An O(n) instantiation of our analysis successfully enables the optimization of closure representations and procedure calls. Experiments with the cheaper instantiation show that it is as effective as 0CFA for these optimizations.

This paper presents an optimized general-purpose algorithm for polyvariant, static analyses of higher-order applicative programs. A polyvariant analysis is a very accurate form of analysis that produces many more abstract descriptions for a program than does a conventional analysis. It may also compute intermediate abstract descriptions that are irrelevant to the final result of the analysis. The optimized algorithm addresses this overhead while preserving the accuracy of the analysis. The algorithm is also parameterized over both the abstract domain and degree of polyvariance. We have implemented an instance of our algorithm and evaluated its performance compared to the unoptimized algorithm. Our implementation runs significantly faster on average than the other algorithm for benchmarks reported here.