THE UNIVERSITY OF CHICAGO SELF-ADJUSTING MACHINES A DISSERTATION SUBMITTED TO THE FACULTY OF THE DIVISION OF THE PHYSICAL SCIENCES IN CANDIDACY FOR THE DEGREE OF DOCTOR OF PHILOSOPHY DEPARTMENT OF COMPUTER SCIENCE BY MATTHEW ARTHUR HAMMER CHICAGO, ILLINOIS DECEMBER 2012 Copyright (cid:13)c 2012 by Matthew Arthur Hammer All Rights Reserved For my parents, for my sister, for my friends, and for Nikita We are the Other, all arising together, Self adjusting Self. Table of Contents List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viii List of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . x Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xi Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiii 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1 Problem statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2 Challenges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.3 Thesis and contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.4 Technical results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.4.1 Contexts of concern . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.4.2 Abstract machine design . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.4.3 Compiler and run-time system design . . . . . . . . . . . . . . . . . . 13 1.4.4 Efficient stack-based execution . . . . . . . . . . . . . . . . . . . . . 14 1.4.5 Efficient memory management . . . . . . . . . . . . . . . . . . . . . 16 1.4.6 Simple programming model . . . . . . . . . . . . . . . . . . . . . . . 17 1.5 Chapter outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 1.6 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 1.6.1 Self-adjusting structures . . . . . . . . . . . . . . . . . . . . . . . . . 22 1.6.2 Tools and techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 1.6.3 Limitations of high-level languages . . . . . . . . . . . . . . . . . . . 32 1.6.4 Low-level languages . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 2 Related work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 2.1 Incremental computation: Early work . . . . . . . . . . . . . . . . . . . . . . 40 2.2 Self-adjusting computation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 2.3 Incremental computation: Contemporary work . . . . . . . . . . . . . . . . 50 2.4 Garbage collection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 3 Surface Language . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 3.1 Programming model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 3.2 Modifiable memory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 3.3 The outer level . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 3.4 The inner level . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 3.5 Resource interaction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 3.6 Example: Reducing Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 3.7 Example: Reducing Arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 3.8 Type qualifiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 3.9 Foreign level . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 v 4 Abstract machines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 4.1 Introduction to IL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 4.2 Example programs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 4.3 IL: a self-adjusting intermediate language . . . . . . . . . . . . . . . . . . . 83 4.4 Consistency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 4.5 Destination-Passing Style . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 4.6 Cost Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 5 Compilation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 5.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 5.2 Multiple levels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 5.3 Run-time interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 5.4 Program representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 5.5 Static analyses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129 5.6 Translation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134 5.7 Normalization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143 5.8 Optimizations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153 5.9 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156 6 Run-time system . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160 6.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160 6.2 Memory management . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164 6.3 Basic structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171 6.4 Trace nodes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173 6.5 Self-adjusting machine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175 6.5.1 Interfaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176 6.5.2 Internal structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178 6.5.3 Outer-level target code . . . . . . . . . . . . . . . . . . . . . . . . . . 180 6.5.4 Inner-level target code . . . . . . . . . . . . . . . . . . . . . . . . . . 182 6.5.5 Internal machine operations . . . . . . . . . . . . . . . . . . . . . . . 185 6.5.6 Cost analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191 7 Empirical evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193 7.1 Experimental setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193 7.2 Experimental results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197 7.3 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200 8 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 206 8.1 Future directions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 206 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210 A Surface language code listings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218 vi B Run-time system listings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226 C Abstract machine proofs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232 C.1 Proofs for Consistency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232 C.2 Proofs for DPS Conversion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 269 C.2.1 DPS Conversion Preserves Extensional Semantics . . . . . . . . . . . 269 C.2.2 DPS Conversion Produces CSA Programs . . . . . . . . . . . . . . . . 272 C.3 Cost Semantics Proofs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 277 vii List of Figures 1.1 The operational knot of self-adjusting computation. . . . . . . . . . . . . . . . . 29 1.2 Multi-language comparison with quicksort. . . . . . . . . . . . . . . . . . . . . 32 1.3 GC cost for quicksort in SML. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 2.1 max(x,y) expressed with modal, one-shot modifiable references. . . . . . . . . 44 3.1 Type declarations for expression trees in C. . . . . . . . . . . . . . . . . . . . . 67 3.2 The eval function in C. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 3.3 Example input trees (left) and corresponding execution traces (right). . . . . . 68 3.4 Iteratively compute the maximum of an array. . . . . . . . . . . . . . . . . . . . 70 3.5 Snapshots of the array from Figure 3.4. . . . . . . . . . . . . . . . . . . . . . . . 70 4.1 The eval CEAL function of Figure 3.2, translated into in IL. . . . . . . . . . . . 75 4.2 Three versions of IL code for the for loop in Figure 3.4; highlighting indicates their slight differences. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 4.3 IL syntax. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 4.4 Common machine components. . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 4.5 Stepping relation for reference machine (−→r ). . . . . . . . . . . . . . . . . . . 87 4.6 Stepping relation for store instructions (−→s ). . . . . . . . . . . . . . . . . . . . 88 4.7 Traces, trace actions and trace contexts. . . . . . . . . . . . . . . . . . . . . . . 89 4.8 Tracing transition modes, across push actions. . . . . . . . . . . . . . . . . . . . 90 4.9 Tracing machine: commands and transitions. . . . . . . . . . . . . . . . . . . . 91 4.10 Stepping relation for tracing machine (−→t ): Evaluation. . . . . . . . . . . . . . 94 4.11 Stepping relation for tracing machine (−→t ): Revaluation and propagation. . . . 95 4.12 Stepping relation for tracing machine (−→t ): Undoing the trace. . . . . . . . . . 95 4.13 Destination-passing-style (DPS) conversion. . . . . . . . . . . . . . . . . . . . . 103 5.1 The TRACE_HOOK_CLOSURE signature. . . . . . . . . . . . . . . . . . . . . . . . . 118 5.2 The TRACE_NODE_ATTRIBUTES signature. . . . . . . . . . . . . . . . . . . . . . . 119 5.3 The TRACE_NODE_DESCRIPTOR signature. . . . . . . . . . . . . . . . . . . . . . . 122 5.4 The sytnax of CL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124 5.5 Rooted CFG. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147 5.6 Dominator tree. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147 5.7 Normalized CFG. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147 5.8 Pseudo-code for the NORMALIZE algorithm . . . . . . . . . . . . . . . . . . . . 148 5.9 The Trace_action module. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154 6.1 The BASEMM signature. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171 6.2 The TRACE_NODE signature. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174 6.3 The SELF_ADJUSTING_MACHINE signature. . . . . . . . . . . . . . . . . . . . . . . 176 6.4 The Self_adj_machine module. . . . . . . . . . . . . . . . . . . . . . . . . . . . 179 6.5 The create function. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181 viii 6.6 The cycle function. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181 6.7 The destroy function. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182 6.8 The frame_push function. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182 6.9 The frame_pop function. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183 6.10 The frame_memo function. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185 6.11 The load_root function. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186 6.12 The revoke_until function. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186 6.13 The frame_prop function. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188 6.14 The frame_load function. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190 6.15 The frame_jump function. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190 7.1 Comparison of benchmark targets. . . . . . . . . . . . . . . . . . . . . . . . . . 197 7.2 DeltaML versus stages two and three (“CEAL” and “SASM”). . . . . . . . . . . . 198 A.1 The List module. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219 A.2 The List_map module. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220 A.3 The List_util module. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221 A.4 The modules List_pred1 and List_pred2 . . . . . . . . . . . . . . . . . . . . . 222 A.5 The coin module. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222 A.6 The List_reduce module. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223 A.7 The List_msort module. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224 A.8 The List_qsort module. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225 B.1 The Cell module . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226 B.2 The MODREF signature: An interface to modifiable references. . . . . . . . . . . . 227 B.3 The Oneshot_modref module: Single-write modifiable references . . . . . . . . 228 B.4 The Multwr_modref module: Declarations. . . . . . . . . . . . . . . . . . . . . . 229 B.5 The Multwr_modref.Read module: Read trace hooks. . . . . . . . . . . . . . . . 230 B.6 The Multwr_modref.Write module: Write trace hooks. . . . . . . . . . . . . . . 231 ix List of Tables 1.1 Self-adjusting trees and computations: Parallel Concepts . . . . . . . . . . . . . 24 1.2 Self-adjusting trees and computations: Contrasting Concepts . . . . . . . . . . . 25 1.3 Low-level versus high-level languages . . . . . . . . . . . . . . . . . . . . . . . 36 5.1 Functions versus blocks in CL . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126 5.2 Translation of IL to CL: traced operations and control-flow . . . . . . . . . . . . 138 5.3 Translation of IL to CL: push and pop forms . . . . . . . . . . . . . . . . . . . . 140 5.4 Translation of IL to CL: memo and update forms . . . . . . . . . . . . . . . . . 141 7.1 Targets and their optimizations (Section 5.8). . . . . . . . . . . . . . . . . . . . 196 7.2 Summary of benchmark results, opt targets . . . . . . . . . . . . . . . . . . . . 196 x