1 Pro(cid:12)le-Driven Compilation by Alan Dain Samples Abstract As the size and complexity of software continues to grow, it will be neces- sary for software construction systems to collect, maintain, and utilize much more information about programs than systems do now. This dissertation explores com- piler utilization of pro(cid:12)le data. Several widely held assumptions about collecting pro(cid:12)le data are not true. It isnot true that the optimalinstrumentationproblemhasbeen solved, and itisnot true that counting traversals of the arcs of a program (cid:13)ow graph is more expensive and complex than counting executions of basic blocks. There are simple program (cid:13)ow graphs for which (cid:12)nding optimal instrumentations is possibly exponential. An algorithm is presented that computes instrumentations of a program to count arc traversals (and therefore basic block counts also). Such instrumentations impose 10% to 20% overhead on the execution of a program, often less than the overhead required for collecting basic block execution counts. An algorithm called Greedy Sewing improves the behavior of programs on machines with instruction caches. By moving basic blocks physically closer together if they are executed close together in time, miss rates in instruction caches can be reduced up to 50%. Arc-count pro(cid:12)le data not only allows the compiler to know which basic blocks to move closer together, it also allows those situations that will have little or no e(cid:11)ect on the (cid:12)nal performance of the reorganized program to be ignored. Such a low-level compiler optimization would be di(cid:14)cult to do without arc-count pro(cid:12)le data. The primary contribution of this work is the development of TypeSet- ter, a programming system that utilizes pro(cid:12)le data to select implementations of program abstractions. The system integrates the development, evaluation, and se- lection of alternative implementations of programming abstractions into a package that is transparent to the programmer. Unlike previous systems, TypeSetter does not require programmers to know details of the compiler implementation. Experi- ence indicatesthat the TypeSetter approach to system synthesis has considerable bene(cid:12)t, and will continue to be a promising avenue of research. ii Acknowledgements My heartfelt appreciation goes (cid:12)rst and foremost to my wife Pat for being patient (almost) every time I reported that I needed just six more months, nine at the most. That she could continue to be encouraging and excited about my work is almost more than I can understand. This dissertation is dedicated to her. Whatever I have accomplished, it is because I have stood on the shoulders of two of the most loving giants I shall ever know. My dreams could not even have been dreamt without the many accomplishments achieved by my parents. I simply cannot (cid:12)nd the words that su(cid:14)ciently express my thanks and admiration. I am grateful to Bruce MacLennan for more than he can possibly know. I thank him most for his friendship, his intellect, and encouragment. A lot of him, Gail, and Kimmie are in these pages. Thank you! I may never have started on this task without the inspiration and down- rightprodding(goading?) ofDickHammingandhisperspectiveon thetrue meaning of a Ph.D. \[W]e greatly appreciated the valuable suggestions by ... Sue Graham, ... and, especially, Paul Hil(cid:12)nger | the reviewers who provided most of the comments thatkept usbusy forsolongproducingthe(cid:12)naldraft." [13]I amparticularlypleased that I never had to make use of Paul’s dimes. I also thank Stuart Dreyfus for his work on my thesis committee. If I acknowledged everyone the way I want to, these acknowledgements could easily become longer than the dissertation itself. Therefore, I hope a simple thanks su(cid:14)ces for everyone who has helped me achieve this goal. Special thanks to Dr. Rodney Farrow, the uno(cid:14)cial fourth member of my committee, and to Dr. Wendy Sinclair-Brownforhelpingmesee earlyon whatwas reallyimportant; thanks to Michelle and Allen for their valuable friendship; to Dave Ungar, Richard Probst, and other members of the Stiletto Club; to Eduardo and Vicki; to Michael and Karen; to Charlie and Kendall; to Doug; and especiallyto Toni, Mara, and everyone in 508-20 for putting up with me and helping me during the Final Days. This dissertation was supported in part by an AT&T Bell Laboratories Scholarship, and by the Defense Advanced Research Projects Agency (DoD), mon- itored by Space and Naval Warfare Systems Command under Contract N00039-88- C-0292. Their support is very gratefully acknowledged. iii Contents List of Figures v List of Tables vii 1 Introduction 1 1.1 Past uses of pro(cid:12)le data : : : : : : : : : : : : : : : : : : : : : : : : : 2 1.2 Research Contributions : : : : : : : : : : : : : : : : : : : : : : : : : : 5 2 Pro(cid:12)ling Techniques 6 2.1 Pro(cid:12)ling techniques : : : : : : : : : : : : : : : : : : : : : : : : : : : : 6 2.1.1 Monitoring : : : : : : : : : : : : : : : : : : : : : : : : : : : : 7 2.1.2 Tracing : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 8 2.1.3 Counting: : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 9 2.2 E(cid:14)cient Counting : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 9 2.2.1 Basic block counts : : : : : : : : : : : : : : : : : : : : : : : : 12 2.2.2 Arc counts : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 12 2.2.3 The ‘optimal’ algorithms are not optimal : : : : : : : : : : : : 17 2.3 Empirical data : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 19 2.4 Counter-example : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 21 2.5 Problems with counting : : : : : : : : : : : : : : : : : : : : : : : : : 24 2.6 Conclusions : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 25 3 A Low-level Use: Code Reorganization for Instruction Cache Per- formance 27 3.1 Instruction cache utilization : : : : : : : : : : : : : : : : : : : : : : : 27 3.2 Greedy Sewing : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 30 3.3 Results : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 34 3.3.1 The Programs and Traces : : : : : : : : : : : : : : : : : : : : 34 3.3.2 Miss Rates : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 38 3.3.3 Performance improvement : : : : : : : : : : : : : : : : : : : : 41 3.4 Limitations : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 42 3.5 Conclusions : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 47 iv 4 A High-level use: Implementation selection of abstract data types 48 4.1 The Problem : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 48 4.2 Previous work : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 53 4.3 TypeSetter: The System : : : : : : : : : : : : : : : : : : : : : : : 58 4.3.1 Formalities : : : : : : : : : : : : : : : : : : : : : : : : : : : : 58 4.3.2 The ideal system : : : : : : : : : : : : : : : : : : : : : : : : : 59 4.3.3 ADTs : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 60 4.3.4 Iterators : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 66 4.3.5 Optional parameters : : : : : : : : : : : : : : : : : : : : : : : 66 4.3.6 Alternative implementations : : : : : : : : : : : : : : : : : : : 68 4.3.7 Feasibility functions : : : : : : : : : : : : : : : : : : : : : : : 71 4.3.8 Evaluation functions : : : : : : : : : : : : : : : : : : : : : : : 71 4.4 TypeSetter: The Implementation : : : : : : : : : : : : : : : : : : : 73 4.4.1 The Implementation Selection Algorithm : : : : : : : : : : : : 75 4.4.2 Code sharing : : : : : : : : : : : : : : : : : : : : : : : : : : : 83 4.4.3 Re(cid:12)nements : : : : : : : : : : : : : : : : : : : : : : : : : : : : 84 4.5 Examples : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 85 4.5.1 Small example : : : : : : : : : : : : : : : : : : : : : : : : : : : 86 4.5.2 MINOPT : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 93 4.5.3 Implementing Therblig : : : : : : : : : : : : : : : : : : : : : 94 5 Conclusion 102 5.1 Problems and future work : : : : : : : : : : : : : : : : : : : : : : : : 103 5.2 Summary : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 106 A The Knuth-Stevenson Algorithm 112 B Therblig 123 v List of Figures 2.1 Block counts are insu(cid:14)cient. The sub-graph on the right is the same as the sub-graph on the left with the addition of an arc from block C to block A. Knowing the execution counts of the blocks does not allow the derivation of the arc counts. : : : : : : : : : : : : : : : : : : 10 2.2 Another graph with cheaper instrumentation. : : : : : : : : : : : : : 15 2.3 A program (cid:13)ow-graph for which MINARC is not optimal : : : : : : : 16 2.4 The problem con(cid:12)guration : : : : : : : : : : : : : : : : : : : : : : : : 17 2.5 ISPLIT vs. ISPLITCHEAP : : : : : : : : : : : : : : : : : : : : : : : 18 2.6 The problem con(cid:12)guration.: : : : : : : : : : : : : : : : : : : : : : : : 22 2.7 Case 1: Estimating that the most frequent arc is split expensively. : : 22 2.8 Cases 2 and 3: Estimating that the least frequent arc is split expen- sively, or that both arcs are split expensively. : : : : : : : : : : : : : : 23 2.9 Case 4: Estimating that neither arc is split expensively. : : : : : : : : 23 3.1 Removing cache contention by reorganizing : : : : : : : : : : : : : : : 28 3.2 Improving cache utilization by reorganizing : : : : : : : : : : : : : : 29 3.3 Two threads from if-then-else : : : : : : : : : : : : : : : : : : : : : : 32 3.4 Pseudo-inlining : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 34 3.5 Scrunch miss rates and percent improvement : : : : : : : : : : : : : : 38 3.6 Tro(cid:11) miss rates and percent improvement : : : : : : : : : : : : : : : 39 3.7 Cc1 miss rates and percent improvement : : : : : : : : : : : : : : : : 40 3.8 Scrunch performance for K = 2, 3, 4, 5, 6, 7, 10, 15, 20, and 25 : : : : 43 3.9 Tro(cid:11) performance for K = 2, 3, 4, 5, 6, 7, 10, 15, 20, and 25 : : : : : 44 3.10 Cc1 performance for K = 2, 3, 4, 5, 6, 7, 10, 15, 20, and 25 : : : : : : 45 4.1 Low’s algorithm : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 54 4.2 Possible implementations of sets ((cid:3) in prototype) : : : : : : : : : : : 61 4.3 Speci(cid:12)cation of List ADT : : : : : : : : : : : : : : : : : : : : : : : : 62 4.4 Possible implementations of lists ((cid:3) in prototype) : : : : : : : : : : : 63 4.5 Speci(cid:12)cation of Map ADT : : : : : : : : : : : : : : : : : : : : : : : : 64 4.6 Possible implementations of maps ((cid:3) in prototype) : : : : : : : : : : : 65 4.7 TypeSetter optionals. : : : : : : : : : : : : : : : : : : : : : : : : : 69 4.8 Pro(cid:12)ling implementation of add : : : : : : : : : : : : : : : : : : : : : 70 vi 4.9 An alternative implementation of add : : : : : : : : : : : : : : : : : : 71 4.10 Feasibility function for implementation Set bm : : : : : : : : : : : : : 72 4.11 Evaluation function for add : : : : : : : : : : : : : : : : : : : : : : : 72 4.12 Set union using linked lists : : : : : : : : : : : : : : : : : : : : : : : : 74 4.13 Steps to process a User program : : : : : : : : : : : : : : : : : : : : : 76 4.14 Steps to process implementations and build Therblig : : : : : : : : 77 4.15 Main routine for choosing representations : : : : : : : : : : : : : : : : 79 4.16 Routine assignable for choosing the implementation of an abstract function : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 80 4.17 Mapping parameters onto implemented functions’ signature : : : : : : 80 4.18 Finding compatible function implementations : : : : : : : : : : : : : 81 4.19 Miscellaneous functions : : : : : : : : : : : : : : : : : : : : : : : : : : 82 4.20 Mappingparametersontoimplementedfunctions’signaturewithequiv- alence classes : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 82 4.21 Declarations of generic Set functions : : : : : : : : : : : : : : : : : : 83 4.22 Declarations of generic Set functions : : : : : : : : : : : : : : : : : : 84 4.23 Declarations of generic Set functions : : : : : : : : : : : : : : : : : : 84 4.24 Small example : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 87 4.25 The call sites sorted by pro(cid:12)ling estimates of importance : : : : : : : 88 4.26 The actual pro(cid:12)ling implementation for the add function for Sets : : 89 4.27 Estimates of the cost of the intersection function : : : : : : : : : : : : 89 4.28 Estimates of the cost of the add function on line 54 : : : : : : : : : : 90 4.29 TypeSetter’s assignment of types to the program : : : : : : : : : : 91 4.30 Results from the example with LOOPCOUNT=10 : : : : : : : : : : 92 4.31 The sorted call sites of Set functions from one Therblig run : : : : 98 vii List of Tables 2.1 Pro(cid:12)ling overhead : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 20 2.2 Comparison of pro(cid:12)le data size requirements : : : : : : : : : : : : : : 21 3.1 Summary of traces: number of instruction words fetched : : : : : : : 37 3.2 Summary of traces: number of basic blocks : : : : : : : : : : : : : : : 37 4.1 Small example running times with various implementation assign- ments for cSet : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 92 4.2 Running times for the K-S algorithm. : : : : : : : : : : : : : : : : : : 94 4.3 Variable assignments based on pro(cid:12)leof three runs of Therblig with p = 0 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 99 4.4 Variable assignments based on the pro(cid:12)le of three runs of Therblig with p = 1 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 100 4.5 Variable assignments based on the pro(cid:12)le of three runs of Therblig with p = :9 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 100 4.6 Therblig running times with various implementation assignments : 101 1 Chapter 1 Introduction The ‘ideal system of the future’ will keep pro(cid:12)les associated with source programs, using the frequency counts in virtually all phases of a pro- gram’s life. :::[I]f it is to be a frequently used program the high counts initspro(cid:12)leoftensuggestbasicimprovementsthatcanbemade. Anopti- mizingcompilercan alsomake very e(cid:11)ective use of the pro(cid:12)le, sinceit of- ten su(cid:14)ces to do time-consumingoptimizationon only one-tenth or one- twentiethofaprogram. [28] In spite of the fact that Knuth made this pronouncement twenty years ago, and in spite of the fact that programmers routinely ‘optimize’ programs by hand based on pro(cid:12)le data, Knuth’s Dictum (as we will call it) still has not been fully implemented in an automated pro(cid:12)ling system nor shown to be undesirable. This dissertation examines the issues surrounding the utilization of pro(cid:12)le data in the compilation of source code. This is a larger subject than that of gen- erating or collecting pro(cid:12)le data. It requires asking, at a minimum, the following questions: Given that pro(cid:12)le data exists for a program, how might a compiler make use of that data to produce better executable code? What kinds of pro(cid:12)le data can be generated/collected? What kinds of pro(cid:12)le data are useful? How expensive is this pro(cid:12)ling?. We start with two hypotheses: 1. Collecting pro(cid:12)le data need not be prohibitively expensive. 2. Compilerscanpro(cid:12)tablyusepro(cid:12)ledataatalllevelsofthecompilationprocess. Compilersthat emit pro(cid:12)lingcode have been at least partiallyimplementedby most modernsystems. But nosystemsofwhichI amawareutilizea program’spro(cid:12)ledata throughout the compilation process. Furthermore, while these hypotheses might be accepted in a general way, there are still some misconceptions about the cost of pro(cid:12)ling, and room for improvement in the pro(cid:12)ling algorithms themselves. 2 1.1 Past uses of pro(cid:12)le data The collection and use of pro(cid:12)le data has a long history, beginning with Knuth’s 1971 paper [28]. In this paper, the term ‘pro(cid:12)le’ was (cid:12)rst used, and de(cid:12)ned to be the collection of execution frequency counts taken during executions of a pro- gram. Since that time, the term ‘pro(cid:12)le data’ has come to mean any quantitative information gathered about the run-time behavior of a program, including execu- tion counts of the program and its sub-parts, reference counts of the program’s data objects, and real-time measures of algorithm executions. Knuth’s examinationof execution pro(cid:12)les of running user programs uncov- ered two facts: (1) Mostprogrammersdo notknow where their programsspendmost of the time; and (2) even when programmers analyze their programs, they stilldon’t know where their programsspend mostof the timedue to the fact that programmers almostnever have accessto su(cid:14)cientinformationaboutsystemand libraryfunctions to deduce the runtime resources they consume. For example, a major culprit in the FORTRAN environment in which Knuth did his study was the formatting routines in the I/O statements. Another result of Knuth’s study was the rule-of-thumb that said that 90% of a program’s time is spent in 10% of the code, variously called the 90-10, or 80-20, rule. Knuth never used either of these numbers but reported that in his studies 50% of the time was spent in 4% of the code. In fact, the actual numbers are di(cid:11)erent for each program. The 90-10 rule, or whatever you want to call it, is one of the guidingprincipleson which manualprogram optimizationis based: (cid:12)nd that section of your program that takes most of the runtime resources, and either modify the algorithm itself (e.g., change a bubble-sort into a quick-sort) or make the existing algorithmmoree(cid:14)cient at the lowlevel(e.g., hoistcommonexpressionsout ofloops, dostrength reductionontheindexvariables,turnrepeatedarrayindexingoperations into pointer operations, etc.). After Knuth’s 1971 paper, Dan Ingalls published two papers describing descendantsoftheFORDAPpro(cid:12)letoolusedbyKnuth. FORDAPwasabasic-block counting pro(cid:12)ler. The (cid:12)rst technical report [23] gives details of how the FORTRAN Execution Time Estimator (FETE) adds execution time estimates to the frequency count displays of FORDAP. This enhancement was prompted by the obvious fact that not all statements are created equal. For example, the FORTRAN statement A = B(I) will execute at vastly di(cid:11)erent speeds depending on whether B is an array or a function. FETE used a value based on ‘weights’ assigned to expression operators and statement classesto give a rough estimate of the execution time. FETE was not sophisticated enough to handle calls on user functions. If, in the example above, B is not an array but a call on a function, FETE will count it as an array reference unless B is a standard FORTRAN function. 3 Ingalls’second paper [22] describesFORTUNE, which issimplya renamed, product version of FETE. FORTUNE and FETE modi(cid:12)ed the source program so that it contained FORTRAN statements incrementing elements of an array of coun- ters. These counting statements were placed essentially at the beginnings of basic blocks. Theanalyzerreportedstatementexecutioncountsandestimatesofexecution time for each statement. Prof [5], a pro(cid:12)le collector for C, Pascal, and FORTRAN programs on the UNIX system is an example of pro(cid:12)ling tools in current use. Prof samples the program counter via timer interrupts to estimate the amount of time spent between thesymbolsoftheprogram. Prof’susabilityhasbeenenhancedbyGprof,aprogram developed at Berkeley by Graham, Kessler and McKusick [16]. Gprof explicitly concentratesonprocedurecalls,providingbothfrequenciesforcallsthroughcounting and estimates of the time spent in each procedure. Timing estimates are derived by sampling the program counter, as in prof. After the user’s program has run, a separately invoked post-pass analyzer distributes timing estimates to the program’s procedures based on the static and dynamic call graphs. There has been a smallamount of research publishedabout the best way to pro(cid:12)le a program. In the (cid:12)rst volume of his Art of Programming series, Knuth gives the algorithmfor determininga minimalinstrumentationof a program for collecting the execution counts of arcs. Knuth and Stevenson [30] (about which more will be said later) published the de(cid:12)nitive algorithm for (cid:12)nding a minimal instrumentation of a program that counts the execution of its basic blocks. Cheung [7] concurrently developed algorithmsfor (cid:12)nding minimalinstrumentationsthat count the frequency of execution paths through a program. A paper by Sarkar [42], without referencing this body of work, developed an algorithmfor instrumenting a program based on its dependence graph. Therehasbeensomeresearchintothepotentialusesofpro(cid:12)ledata. Gilbert Hansen’sresearch[17]isanearlyinvestigationintobehavior-drivenoptimization. He hypothesizedthat, forcertainclassesofsoftware,theoptimizationofaprogramcould be done at run-time more economically than at compile-time. Instead of the usual compile-a-(cid:12)le paradigm that most compiler systems utilize, Hansen’s \adaptive" compiler consisted of two \phases". The (cid:12)rst phase generated an interpretable form of a FORTRAN program in a fast, one-pass compilation(it produced ‘quads’ as the interpretableform). Thesecondpartconsistedofaninterpreterandoptimizerloaded with the compiled program. When the interpreter detected that a basic block was being executed su(cid:14)ciently often, interpretation was suspended while the optimizer wasinvokedto compilethe basicblocktoalowerlevel. Ifa basicblockwere executed often enough, it would eventually be compiled down to machine language. The one-pass compiler annotated each basic block with information about its sizeand complexityso the interpreter could predict pro(cid:12)table optimizations. The system was designed to expend e(cid:11)ort only on optimizations that had a high proba- bility of paying for themselves through improved execution of the program. There