《A NANOPASS FRAMEWORK FOR COMMERCIAL COMPILER DEVELOPMENT》

【实例截图】

【核心代码】

Contents
List of Tables ix
List of Figures x
Chapter 1. Introduction 1
Chapter 2. The Nanopass Framework 9
2.1. Introduction 9
2.2. The Prototype Framework 11
2.3. New Framework Specification 14
2.4. Comparison with the Prototype Nanopass Framework 51
2.5. Related Work 56
Chapter 3. Evaluating the Nanopass Framework 59
3.1. Introduction 59
3.2. Transitioning a Class Compiler 60
3.3. Recreating a Commercial Compiler 60
3.4. Comparing Nanopass Passes with Traditional Passes 64
3.5. Comparing the Speed of Generated Code 74
3.6. Comparing Compilation Speed 75
Chapter 4. Cross-library Optimization 93
4.1. Introduction 93
4.2. Background 96
4.3. The library-group Form 102
4.4. Automatic Cross-Library Optimization 113
4.5. Empirical Evaluation 115
4.6. Related Work 117
4.7. Future Work 119
4.8. Conclusion 120
vii
Chapter 5. Closure Optimization 122
5.1. Introduction 122
5.2. The Optimizations 123
5.3. The Algorithm 131
5.4. Results 141
5.5. Related Work 145
5.6. Conclusion 146
Chapter 6. Conclusion and Future Work 147
Bibliography 153
viii
List of Tables
3.1 Comparing line and character counts for original and nanopass versions of cpsrc. 65
3.2 Run time of the nanopass version of cpsrc relative to the original version. 66
3.3 Comparing line and character counts for the original and nanopass versions of cp0. 70
3.4 Run time of the nanopass version of cp0 relative to the original version. 70
3.5 Normalized run times of the similix and softscheme benchmarks. 74
3.6 Percentage of back-end time for each of three dummy passes, one after the initial back-end
pass, one after the primitive expansion pass, and one after the instruction selection pass. 87
5.1 Eliminated closures (Closure), free-variables (FV), memory references (Mem. Ref.), and
allocation (Alloc.) by closure optimization type. 143
ix
List of Figures
2.1 Comparing a language definition between the prototype and new nanopass frameworks. 52
2.2 Comparing language extension between the prototype and new nanopass frameworks. 52
2.3 Comparing pass definitions between the prototype and new nanopass frameworks. 53
3.1 Normalized run time of cpsrc pass for R6RS benchmarks. 67
3.2 Normalized run time of cpsrc pass for new benchmarks. 68
3.3 Normalized run time of cpsrc pass for benchmarks. 69
3.4 Normalized run time of cp0 pass for the R6RS benchmarks. 71
3.5 Normalized run time of cp0 pass for the source optimizer benchmarks. 72
3.6 Normalized run time of cp0 pass for the Chez Scheme benchmarks. 73
3.7 Normalized run-time performance of the R6RS benchmarks. 76
3.8 Normalized run-time performance of the source optimizer benchmarks. 77
3.9 Normalized run-time performance of the Chez Scheme benchmarks. 78
3.10 Normalized compile-time performance of the R6RS benchmarks. 80
3.11 Normalized compile-time performance of the source optimizer benchmarks. 81
3.12 Normalized compile-time performance of the Chez Scheme benchmarks. 82
3.13 Normalized compile times vs. the size of the expanded source code. 83
3.14 Normalized front-end compile-time performance of the R6RS benchmarks. 85
3.15 Normalized front-end compile-time performance of the source optimizer benchmarks. 88
3.16 Normalized front-end compile-time performance of the Chez Scheme benchmarks. 89
3.17 Normalized back-end compile-time performance of the R6RS benchmarks. 90
3.18 Normalized back-end compile-time performance of the source optimizer benchmarks. 91
3.19 Normalized back-end compile-time performance of the Chez Scheme benchmarks. 92
4.1 The (tree) library, which implements a tree data structure. 98
x
4.2 The (tree constants) library, which defines a mechanism for creating constant trees
and a few constant trees of its own. 99
4.3 A program that uses the (tree) and (tree constants) libraries. 99
4.4 Library records for the (tree) and (tree constants) libraries and a program record for
our program. 101
4.5 A nested letrec* for the library group that includes the (tree) library, the
(tree constants) library, and our program, with indicating code that has been
omitted for brevity. 107
4.6 A nested letrec* for our library group that includes the (tree) library, the
(tree constants) library, and our program, with library-global references replaced
by local-variable references. 108
4.7 The final invoke code expansion target for the library group that includes the (tree)
library, the (tree constants) library, and our program. 109
4.8 Three simple libraries, (A), (B), and (C), with simple dependencies. 109
4.9 A library-group form containing the (A) and (C) libraries. 110
4.10 Expansion of library group marking (A) as invoked and invoking (B). 110
4.11 Final expansion for correct library group with the (A) and (C) libraries. 110
4.12 Library and program records for the library group, showing the shared invoke code run
when either the (tree) or (tree constant) library is invoked or when the top-level
program is run. 111
4.13 Final expansion of the library group containing the (tree) library, the (tree constants)
library, and our program. 112
5.1 Function f with a self-reference in its closure. 128
5.2 Mutual references for the even? and odd? closures. 128
5.3 Mutual references for the even? and odd? closures, with z free in even?. 129
5.4 The core intermediate language. 134
5.5 Intermediate language after uncovering free variables. 134
5.6 Intermediate language after uncovering known calls. 134
5.7 Intermediate language after computing strongly connected sets. 134
5.8 Intermediate language after choosing subsets for sharing. 134
xi
5.9 Final output intermediate language. 134
5.10 Closure-related primitives. 135