waashk/dblp huggingface dataset:
accurate static estimators for program optimization. determining the relative execution frequency of program regions is essential for many important optimization techniques, including register allocation, function inlining, and instruction scheduling. estimates derived from profiling with sample inputs are generally regarded as the most accurate source of this information; static (compile-time) estimates are considered to be distinctly inferior. if static estimates were shown to be competitive, however, their convenience would outweigh minor gains from profiling, and they would provide a sound basis for optimization when profiling is impossible.we use quantitative metrics to compare estimates from static analysis to those derived from profiles. for c programs, simple techniques for predicting branches and loop counts suffice to estimate intraprocedural frequency patterns with high accuracy. to determine inter-procedural estimates successfully, we combine function-level information with a markov model of control flow over the call graph to produce arc and basic block frequency estimates for the entire program.for a suite of 14 programs, including the c programs from the spec92 benchmark suite, we demonstrate that static estimates are competitive with those derived from profiles. using simple heuristics, we can determine the most frequently executed blocks in each function with 81% accuracy. with the markov model, we identify 80% of the frequently called functions. combining the two techniques, we identify 76% of the most frequently executed call sites.
practical data breakpoints: design and implementation. a data breakpoint associates debugging actions with programmer-specified conditions on the memory state of an executing program. data breakpoints provide a means for discovering program bugs that are tedious or impossible to isolate using control breakpoints alone. in practice, programmers rarely use data breakpoints, because they are either unimplemented or prohibitively slow in available debugging software. in this paper, we present the design and implementation of a practical data breakpoint facility. a data breakpoint facility must monitor all memory updates performed by the program being debugged. we implemented and evaluated two complementary techniques for reducing the overhead of monitoring memory updates. first, we checked write instructions by inserting checking code directly into the program being debugged. the checks use a segmented bitmap data structure that minimizes address lookup complexity. second, we developed data flow algorithms that eliminate checks on some classes of write instructions but may increase the complexity of the remaining checks. we evaluated these techniques on the sparc using the spec benchmarks. checking each write instruction using a segmented bitmap achieved an average overhead of 42%. this overhead is independent of the number of breakpoints in use. data flow analysis eliminated an average of 79% of the dynamic write checks. for scientific programs such the nas kernels, analysis reduced write checks by a factor of ten or more. on the sparc these optimizations reduced the average overhead to 25%.
register windows versus register allocation. a large register set can be exploited by keeping variables and constants in registers instead of in memory. hardware register windows and compile-time or link-time global register allocation are ways to do this. a measure of the effectiveness of any of these register management schemes is how thoroughly they remove loads and stores. this measure must also count extra loads and stores executed because of window overflow or conflicts between procedures.by combining profiling, instrumentation, and in-line simulation, we measured the effectiveness of several register management schemes. these included compile-time and link-time schemes for allocating registers, and register window schemes using fixed-size or variable-sized windows. link-time allocation based on profile information was the clear winner in some cases and did about as well as windows in the rest. even link-time allocation based on an estimated profile was about as good as windows. variable-sized windows sometimes did better than fixed-sized windows, but the difference was usually small.register windows require extra logic in the data path, which may slow the machine cycle slightly, and often use more chip real estate for additional registers. proponents of windows suppose that they trade these drawbacks for a reduction in the number of memory references they must make. our results show that this tradeoff should be made the other way. keep the hardware simple, because a link-time register allocator can nearly duplicate the improvement in memory reference frequency. then the cycle time can be as small as possible, resulting in faster programs overall.
predicting program behavior using real or estimated profiles. there is a growing interest in optimizations that depend on or benefit from an execution profile that tells where time is spent. how well does a profile from one run describe the behavior of a different run, and how does this compare with the behavior predicted by static analysis of the program? this paper defines two abstract measures of how well a profile predicts actual behavior. according to these measures, real profiles indeed do better than estimated profiles, usually. a perfect profile from an earlier run with the same data set, however, does better still, sometimes by a factor of two. unfortunately, using such a profile is unrealistic, and can lead to inflated expectations of a profile-driven optimization.
functional reactive programming from first principles. functional reactive programming, or frp, is a general framework for programming hybrid systems in a high-level, declarative manner. the key ideas in frp are its notions of behaviors and events. behaviors are time-varying, reactive values, while events are time-ordered sequences of discrete-time event occurrences. frp is the essence of fran, a domain-specific language embedded in haskell for programming reactive animations, but frp is now also being used in vision, robotics and other control systems applications. in this paper we explore the formal semantics of frp and how it relates to an implementation based on streams that represent (and therefore only approximate) continuous behaviors. we show that, in the limit as the sampling interval goes to zero, the implementation is faithful to the formal, continuous semantics, but only when certain constraints on behaviors are observed. we explore the nature of these constraints, which vary amongst the frp primitives. our results show both the power and limitations of this approach to language design and implementation. as an example of a limitation, we show that streams are incapable of representing instantaneous predicate events over behaviors.
precise compile-time performance prediction for superscalar-based computers. optimizing compilers (particularly parallel compilers) are constrained by their ability to predict performance consequences of the transformations they apply. many factors, such as unknowns in control structures, dynamic behavior of programs, and complexity of the underlying hardware, make it very difficult for compilers to estimate the performance of the transformations accurately and efficiently. in this paper, we present a performance prediction framework that combines several innovative approaches to solve this problem. first, the framework employs a detailed, architecture-specific, but portable, cost model that can be used to estimate the cost of straight line code efficiently. second, aggregated costs of loops and conditional statements are computed and represented symbolically. this avoids unnecessary, premature guesses and preserves the precision of the prediction. third, symbolic comparison allows compilers to choose the best transformation dynamically and systematically. some methodologies for applying the framework to optimizing parallel compilers to support automatic, performance-guided program restructuring are discussed.
parametric analysis for adaptive computation offloading. many programs can be invoked under different execution options, input parameters and data files. such different execution contexts may lead to strikingly different execution instances. the optimal code generation may be sensitive to the execution instances. in this paper, we show how to use parametric program analysis to deal with this issue for the optimization problem of computation offloading.computation offloading has been shown to be an effective way to improve performance and energy saving on mobile devices. optimal program partitioning for computation offloading depends on the tradeoff between the computation workload and the communication cost. the computation workload and communication requirement may change with different execution instances. optimal decisions on program partitioning must be made at run time when sufficient information about workload and communication requirement becomes available.our cost analysis obtains program computation workload and communication cost expressed as functions of run-time parameters, and our parametric partitioning algorithm finds the optimal program partitioning corresponding to different ranges of run-time parameters. at run time, the transformed program self-schedules its tasks on either the mobile device or the server, based on the optimal program partitioning that corresponds to the current values of run-time parameters. experimental results on an hp ipaq handheld device show that different run-time parameters can lead to quite different program partitioning decisions.
reverse if-conversion. in this paper we present a set of isomorphic control transformations that allow the compiler to apply local scheduling techniques to acyclic subgraphs of the control flow graph. thus, the code motion complexities of global scheduling are eliminated. this approach relies on a new technique, reverse if-conversion (ric), that transforms scheduled if-converted code back to the control flow graph representation. this paper presents the predicate internal representation, the algorithms for ric, and the correctness of ric. in addition, the scheduling issues are addressed and an application to software pipelining is presented.
efficient interpretation of synchronizable series expressions. the benefits of programming in a functional style are well known. for example, algorithms which are expressed as compositions of functions operating on series/vectors/streams of data elements are much easier to understand and modify than equivalent algorithms expressed as loops. unfortunately, many programmers hesitate to use series expressions because they are typically implemented very inefficiently-the prime source of inefficiency being the creation of intermediate series objects.a restricted class of series expressions, obviously synchronizable series expressions, is defined which can be evaluated very efficiently because they do not require the creation of any intermediate series objects. a common lisp macro package has been implemented which supports obviously synchronizable series expressions. using this macro package, programmers can obtain the advantages of expressing computations as series expressions without incurring any runtime overhead. obviously synchronizable series expressions could be straightforwardly supported in any programming language.
program analysis using binary relations. this paper presents a method called relational constraint for finding binary relations among the variables and constants of a program. the method constructs a table of binary relations and treats the program as a collection of constraints on tuples of relations in the table. an experimental optimizer called thinner uses this method to analyze programs of size n in o(n2) time.
programmable syntax macros. lisp has shown that a programmable syntax macro system acts as an adjunct to the compiler that gives the programmer important and powerful abstraction facilities not provided by the language. unlike simple token substitution macros, such as are provided by cpp (the c preprocessor), syntax macros operate on abstract syntax trees (asts). programmable syntax macro systems have not yet been developed for syntactically rich languages such as c because rich concrete syntax requires the manual construction of syntactically valid program fragments, which is a tedious, difficult, and error prone process. also, using two languages, one for writing the program, and one for writing macros, is another source of complexity. this research solves these problems by having the macro language be a minimal extension of the programming language, by introducing explicit code template operators into the macro language, and by using a type system to guarantee, at macro definition time, that all macros and macro functions only produce syntactically valid program fragments. the code template operators make the language context sensitive, which requires changes to the parser. the parser must perform type analysis in order to parse macro definitions, or to parse user code that invokes macros.
cloning-based context-sensitive pointer alias analysis using binary decision diagrams. this paper presents the first scalable context-sensitive, inclusion-based pointer alias analysis for java programs. our approach to context sensitivity is to create a clone of a method for every context of interest, and run a context-insensitive algorithm over the expanded call graph to get context-sensitive results. for precision, we generate a clone for every acyclic path through a program's call graph, treating methods in a strongly connected component as a single node. normally, this formulation is hopelessly intractable as a call graph often has 10 14 acyclic paths or more. we show that these exponential relations can be computed efficiently using binary decision diagrams (bdds). key to the scalability of the technique is a context numbering scheme that exposes the commonalities across contexts. we applied our algorithm to the most popular applications available on sourceforge, and found that the largest programs, with hundreds of thousands of java bytecodes, can be analyzed in under 20 minutes.this paper shows that pointer analysis, and many other queries and algorithms, can be described succinctly and declaratively using datalog, a logic programming language. we have developed a system called bddbddb that automatically translates datalog programs into highly efficient bdd implementations. we used this approach to develop a variety of context-sensitive algorithms including side effect analysis, type analysis, and escape analysis.
run-time code generation and modal-ml. this paper presents a typed programming language and compiler for run-time code generation. the language, called ml', extends ml with modal operators in the style of the mini-ml'e language of davies and pfenning. ml' allows programmers to use types to specify precisely the stages of computation in a program. the types also guide the compiler in generating target code that exploits the staging information through the use of run-time code generation. the target machine is currently a version of the categorical abstract machine, called the ccam, which we have extended with facilities for run-time code generation.this approach allows the programmer to express the staging that he wants directly to the compiler. it also provides a typed framework in which to verify the correctness of his staging intentions, and to discuss his staging decisions with other programmers. finally, it supports in a natural way multiple stages of run-time specialization, so that dynamically generated code can be used in the generation of yet further specialized code.this paper presents an overview of the language, with several examples of programs that illustrate key concepts and programming techniques. then, it discusses the ccam and the compilation of ml' programs into ccam code. finally, the results of some experiments are shown, to demonstrate the benefits of this style of run-time code generation for some applications.
optimal instruction scheduling using integer programming. this paper presents a new approach to local instruction scheduling based on integer programming that produces optimal instruction schedules in a reasonable time, even for very large basic blocks. the new approach first uses a set of graph transformations to simplify the data-dependency graph while preserving the optimality of the final schedule. the simplified graph results in a simplified integer program which can be solved much faster. a new integer-programming formulation is then applied to the simplified graph. various techniques are used to simplify the formulation, resulting in fewer integer-program variables, fewer integer-program constraints and fewer terms in some of the remaining constraints, thus reducing integer-program solution time. the new formulation also uses certain adaptively added constraints (cuts) to reduce solution time. the proposed optimal instruction scheduler is built within the gnu compiler collection (gcc) and is evaluated experimentally using the spec95 floating point benchmarks. although optimal scheduling for the target processor is considered intractable, all of the benchmarks' basic blocks are optimally scheduled, including blocks with up to 1000 instructions, while total compile time increases by only 14%.
efficient context-sensitive pointer analysis for c programs. this paper proposes an efficient technique for context-sensitive pointer analysis that is applicable to real c programs. for efficiency, we summarize the effects of procedures using partial transfer functions. a partial transfer function (ptf) describes the behavior of a procedure assuming that certain alias relationships hold when it is called. we can reuse a ptf in many calling contexts as long as the aliases among the inputs to the procedure are the same. our empirical results demonstrate that this technique is successful&mdash;a single ptf per procedure is usually sufficient to obtain completely context-sensitive results. because many c programs use features such as type casts and pointer arithmetic to circumvent the high-level type system, our algorithm is based on a low-level representation of memory locations that safely handles all the features of c. we have implemented our algorithm in the suif compiler system and we show that it runs efficiently for a set of c benchmarks.
demonic memories for process histories. demonic memory is a form of reconstructive memory for process histories. as a process executes, its states are regularly checkpointed, generating a history of the process at low time resolution. following the initial generation, any prior state of the process can be reconstructed by starting from a checkpointed state and re-executing the process up through the desired state, thereby exploiting the redundancy between the states of a process and the description of that process (i.e., a computer program). the reconstruction of states is automatic and transparent. the history of a process may be examined as though it were a large two-dimensional array, or address space-time, with a normal address space as one axis and steps of process time as the other. an attempt to examine a state that is not physically stored triggers a &ldquo;demon&rdquo; which reconstructs that memory state before access is allowed. regeneration requires an exact description of the original execution of the process. if the original process execution depends on non-deterministic events (e.g., user input), these events are recorded in an exception list, and are replayed at the proper points during re-execution. while more efficient than explicitly storing all state changes, such a checkpointing system is still prohibitively expensive for many applications; each copy (or snapshot) of the system's state may be very large, and many snapshots may be required. demonic memory saves both space and time by using a virtual copy mechanism. (virtual copies share unchanging data with the objects that they are copies of, only storing differences from a prototype or original [mibk86].) in demonic memory, the snapshot at each checkpoint is a virtual copy of the preceding checkpoint's snapshot. hence it is called a virtual snapshot. in order to make the virtual snapshot mechanism efficient, state information is initially saved in relatively large units of space and time, on the order of pages and seconds, with single-word/single-step regeneration undertaken only as needed. this permits the costs of indexing and lookup operations to be amortized over many locations.
debugging of globally optimized programs using data flow analysis. advanced processor and machine architectures need optimizing compilers to be efficiently programmed in high level languages. therefore the need for source level debuggers that can handle optimized programs is rising. one difficulty in debugging optimized code arises from the problem to determine the values of source code variables. to ensure correct debugger behaviour with optimized programs, the debugger not only has to determine the variable's storage location or associated register. it must also verify that the variable is current, i.e. the value determined from that location is really the value that the variable would have in unoptimized code. we will deduce requirements on algorithms for currentness determination and present an algorithm meeting this requirements that is more general than previous work. we will also give first experiences with an implementation. to our knowledge this is the first implementation of a currentness determination algorithm for globally optimized code.
beyond induction variables. induction variable detection is usually closely tied to the strength reduction optimization. this paper studies induction variable analysis from a different perspective, that of finding induction variables for data dependence analysis. while classical induction variable analysis techniques have been used successfully up to now, we have found a simple algorithm based on the static single assignment form of a program that finds all linear induction variables in a loop. moreover, this algorithm is easily extended to find induction variables in multiple nested loops, to find nonlinear induction variables, and to classify other integer scalar assignments in loops, such as monotonic, periodic and wrap-around variables. some of these other variables are now classified using ad hoc pattern recognition, while others are not analyzed by current compilers. giving a unified approach improves the speed of compilers and allows a more general classification scheme. we also show how to use these variables in data dependence testing.
a concurrent compiler for modula-2+. in this paper we describe a collection of techniques for the design and implementation of concurrent compilers. we begin by describing a technique for dividing a source program into many streams so that each stream can be compiled concurrently. we discuss several compiler design issues unique to concurrent compilers including source program partitioning, symbol table management, compiler task scheduling and information flow constraints. the application of our techniques is illustrated by a complete design for a concurrent modula-2+ compiler. after describing the structure of this compiler's performance that demonstrates that significant improvements in compilation time can be achieved through the use of concurrency.