Todd A Proebsting

Interests

No activities entered.

Courses

Scholarly Contributions

Journals/Publications

• Hanson, D. R., & Proebsting, T. A. (2004). A research C# compiler. Software - Practice and Experience, 34(13), 1211-1224.
  More info

  Abstract: C# is the new flagship language in the Microsoft .NET platform. C# is an attractive vehicle for language design research not only because it shares many characteristics with Java, the current language of choice for such research, but also because it is likely to see wide use. Language research needs a large investment in infrastructure, even for relatively small studies. This paper describes a new C# compiler designed specifically to provide that infrastructure. The overall design is deceptively simple. The parser is generated automatically from a possibly ambiguous grammar, accepts C# source, perhaps with new features, and produces an abstract syntax tree, or AST. Subsequent phases - dubbed visitors - traverse the AST, perhaps modifying it, annotating it or emitting output, and pass it along to the next visitor. Visitors are specified entirely at compilation time and are loaded dynamically as needed. There is no fixed set of visitors, and visitors are completely unconstrained. Some visitors perform traditional compilation phases, but the more interesting ones do code analysis, emit non-traditional data such as XML, and display data structures for debugging. Indeed, most usage to date has been for tools, not for language design experiments. Such experiments use source-to-source transformations or extend existing visitors to handle new language features. These approaches are illustrated by adding a statement that switches on a type instead of a value, which can be implemented in a few hundred lines. The compiler also exemplifies the value of dynamic loading and of type reflection. Copyright © 2004 John Wiley & Sons, Ltd.
• Hanson, D. R., & Proebsting, T. A. (2001). Dynamic variables. Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), 264-273.
  More info

  Abstract: Most programming languages use static scope rules for associating uses of identifiers with their declarations. Static scope helps catch errors at compile time, and it can be implemented efficiently. Some popular languages-Perl, Tcl, TeX, and Postscript-offer dynamic scope, because dynamic scope works well for variables that "customize" the execution environment, for example. Programmers must simulate dynamic scope to implement this kind of usage in statically scoped languages. This paper describes the design and implementation of imperative language constructs for introducing and referencing dynamically scoped variables-dynamic variables for short. The design is a minimalist one, because dynamic variables are best used sparingly, much like exceptions. The facility does, however, cater to the typical uses for dynamic scope, and it provides a cleaner mechanism for so-called thread-local variables. A particularly simple implementation suffices for languages without exception handling. For language s with exception handling, a more efficient implementation builds on existing compiler infrastructure. Exception handling can be viewed as a control construct with dynamic scope. Likewise, dynamic variables are a data construct with dynamic scope.
• Hanson, D. R., & Proebsting, T. A. (2001). Dynamic variables. SIGPLAN Notices (ACM Special Interest Group on Programming Languages), 36(5), 264-270.
  More info

  Abstract: Most programming languages use static scope rules for associating uses of identifiers with their declarations. Static scope helps catch errors at compile time, and it can be implemented efficiently. Some popular languages - Perl, Tcl, TeX, and Postscript - offer dynamic scope, because dynamic scope works well for variables that "customize" the execution environment, for example. Programmers must simulate dynamic scope to implement this kind of usage in statically scoped languages. This paper describes the design and implementation of imperative language constructs for introducing and referencing dynamically scoped variables - dynamic variables for short. The design is a minimalist one, because dynamic variables are best used sparingly, much like exceptions. The facility does, however, cater to the typical uses for dynamic scope, and it provides a cleaner mechanism for so-called thread-local variables. A particularly simple implementation suffices for languages without exception handling. For languages with exception handling, a more efficient implementation builds on existing compiler infrastructure. Exception handling can be viewed as a control construct with dynamic scope. Likewise, dynamic variables are a data construct with dynamic scope. © 2001 ACM.
• Hartman, J., Peterson, L., Bavier, A., Bigot, P., Bridges, P., Montz, B., Piltz, R., Proebsting, T., & Spatscheck, O. (2000). Experiences building a communication-oriented JavaOS. Software - Practice and Experience, 30(10), 1107-1126.
  More info

  Abstract: Mobile code makes it easier to maintain, debug, update, and customize a system. Active networks are one of the more interesting applications of mobile code: code is injected into the nodes of a network to customize the network's functionality, such as routing, and to add new features, such as special-purpose congestion control and filtering algorithms. The challenge is to develop a communication-oriented platform for such systems. We refer to mobile code targeted at low-level, communication-oriented systems like active networks as liquid software, the key distinction being that liquid software is focused on the efficient transfer of data, not high-performance computation. To this end, we have designed and implemented Joust, which consists of a complete re-implementation of the Java virtual machine (including both the runtime system and a just-in-time compiler), running on the Scout operating system (a configurable, communication-oriented OS). The result is a configurable, high-performance platform for running liquid software. We present the results of implementing two different applications of liquid software on Joust, including a prototype architecture for active networks.
• Proebsting, T. A., & Townsend, G. M. (2000). New implementation of the Icon language. Software - Practice and Experience, 30(8), 925-972.
  More info

  Abstract: Jcon is a new, full-featured, Java-based implementation of the Icon programming language. The compiler, written in Icon, generates an intermediate representation that is optimized and then used to produce classfiles of Java bytecode. A four-chunk control-flow model handles goal-directed evaluation and produces constructs not expressible as Java code. The runtime system, written in Java, finds object-oriented programming a great advantage in implementing a dynamically typed language, with method calls replacing many conditional tests. An all-encompassing descriptor class supports values, references, and suspended operations. The procedure call interface is simple and incurs overhead for generator support only when actually needed. Performance is somewhat disappointing, and some limitations are annoying, but in general Java provides a good implementation platform.
• Fraser, C. W., & Proebsting, T. A. (1999). Finite-state code generation. Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), 270-280.
  More info

  Abstract: This paper describes GBURG, which generates tiny, fast code generators based on finite-state machine pattern matching. The code generators translate postfix intermediate code into machine instructions in one pass (except, of course, for backpatching addresses). A stack-based virtual machine - known as the Lean Virtual Machine (LVM) - tuned for fast code generation is also described. GBURG translates the two-page LVM-to-x86 specification into a code generator that fits entirely in an 8 KB I-cache and that emits x86 code at 3.6 MB/sec on a 266-MHz P6. Our just-in-time code generator translates and executes small benchmarks at speeds within a factor of two of executables derived from the conventional compile-time code generator on which it is based.
• Fraser, C. W., & Proebsting, T. A. (1999). Finite-state code generation. SIGPLAN Notices (ACM Special Interest Group on Programming Languages), 34(5), 270-280.
  More info

  Abstract: This paper describes GBURG, which generates tiny, fast code generators based on finite-state machine pattern matching. The code generators translate postfix intermediate code into machine instructions in one pass (except, of course, for backpatching addresses). A stack-based virtual machine - known as the Lean Virtual Machine (LVM) - tuned for fast code generation is also described. GBURG translates the two-page LVM-to-x86 specification into a code generator that fits entirely in an 8 KB I-cache and that emits x86 code at 3.6 MB/sec on a 266-MHz P6. Our just-in-time code generator translates and executes small benchmarks at speeds within a factor of two of executables derived from the conventional compile-time code generator on which it is based. © 1999 ACM.
• Hartman, J. J., Bigot, P. A., Bridges, P., Montz, B., Piltz, R., Spatscheck, O., Proebsting, T. A., Peterson, L. L., & Bavier, A. (1999). Joust: A platform for liquid software. Computer, 32(4).
  More info

  Abstract: Computer network research has recently focused on the feasibility of running mobile code on the intermediate nodes that forward packets through a network. A Java-based platform for liquid software, called Joust, that is specifically designed to support low-level, communication-oriented systems and to avoid the limitations of general purpose operating systems. The Scout operating system, its runtime system, and its just-in-time (JIT) compiler is described.
• Bhamidipaty, A., & Proebsting, T. A. (1998). Very fast YACC-compatible parsers (for very little effort). Software - Practice and Experience, 28(2), 181-190.
  More info

  Abstract: We have developed a yacc-compatible parser generator that creates parsers that are 2.0 to 6.0 times faster than those generated by yacc or bison. Our tool, mule, creates directly-executable, hard-coded parsers in ANSI C; yacc produces interpreted, table-driven parsers. Two attributes distinguish mule from other parser generators that create hard-coded LR parsers: mule is compatible with yacc (including yaccs peculiar error recovery mechanisms), and mule does absolutely none of the complex automata analysis of previous hard-coded-parser generators. Mule creates simple, fast parsers after very little analysis. ©1997 by John Wiley & Sons, Ltd.
• Kannan, S., & Proebsting, T. (1998). Register Allocation in Structured Programs. Journal of Algorithms, 29(2), 223-237.
  More info

  Abstract: In this article we look at the register allocation problem. In the literature this problem is frequently reduced to the general graph coloring problem and the solutions to the problem are obtained from graph coloring heuristics. Hence, no algorithm with a good performance guarantee is known. Here we show that when attention is restricted to structured programs which we define to be programs whose control-flow graphs are series-parallel, there is an efficient algorithm that produces a solution which is within a factor of 2 of the optimal solution. We note that even with the previous restriction the resulting coloring problem is NP-complete. We also consider how to delete a minimum number of edges from arbitrary control-flow graphs to make them series-parallel and to apply our algorithm. We show that this problem is MaxSNP hard. However, we define the notion of an approximate articulation point and we give efficient algorithms to find approximate articulation points. We present a heuristic for the edge deletion problem based on this notion which seems to work well when the given graph is close to series-parallel. © 1998 Academic Press.
• Ernst, J., Evans, W., Fraser, C. W., Lucco, S., & Proebsting, T. A. (1997). Code Compression. SIGPLAN Notices (ACM Special Interest Group on Programming Languages), 32(5), 358-365.
  More info

  Abstract: Current research in compiler optimization counts mainly CPU time and perhaps the first cache level or two. This view has been important but is becoming myopic, at least from a system-wide viewpoint, as the ratio of network and disk speeds to CPU speeds grows exponentially. For example, we have seen the CPU idle for most of the time during paging, so compressing pages can increase total performance even though the CPU must decompress or interpret the page contents. Another profile shows that many functions are called just once, so reduced paging could pay for their interpretation overhead. This paper describes: • Measurements that show how code compression can save space and total time in some important real-world scenarios. • A compressed executable representation that is roughly the same size as gzipped x86 programs and can be interpreted without decompression. It can also be compiled to high-quality machine code at 2.5 megabytes per second on a 120MHz Pentium processor • A compressed "wire" representation that must be decompressed before execution but is, for example, roughly 21% the size of SPARC code when compressing gcc.
• Ernst, J., Evans, W., Fraser, C. W., Lucco, S., & Proebsting, T. A. (1997). Code compression. Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), 358-365.
  More info

  Abstract: Current research in compiler optimization counts mainly CPU time and perhaps the first cache level or two. This view has been important but is becoming myopic, at least from a system-wide viewpoint, as the ratio of network and disk speeds to CPU speeds grows exponentially. For example, we have seen the CPU idle for most of the time during paging, so compressing pages can increase total performance even though the CPU must decompress or interpret the page contents. Another profile shows that many functions are called just once, so reduced paging could pay for their interpretation overhead. This paper describes: Measurements that show how code compression can save space and total time in some important real-world scenarios. A compressed executable representation that is roughly the same size as gzipped x86 programs and can be interpreted without decompression. It can also be compiled to high-quality machine code at 2.5 megabytes per second on a 120 MHz Pentium processor. A compressed `wire' representation that must be decompressed before execution but is, for example, roughly 21% the size of SPARC code when compressing gcc.
• Proebsting, T. A. (1997). Simple Translation of Goal-Directed Evaluation. SIGPLAN Notices (ACM Special Interest Group on Programming Languages), 32(5), 1-6.
  More info

  Abstract: This paper presents a simple, powerful and flexible technique for reasoning about and translating the goal-directed evaluation of programming language constructs that either succeed (and generate sequences of values) or fail. The technique generalizes the Byrd Box, a well-known device for describing Prolog backtracking.
• Proebsting, T. A. (1997). Simple translation of goal-directed evaluation. Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), 1-6.
  More info

  Abstract: This paper presents a simple, powerful and flexible technique for reasoning about and translating the goal-directed evaluation of programming language constructs that either succeed (and generate sequences of values) or fail. The technique generalizes the Byrd Box, a well-known device for describing Prolog backtracking.
• Proebsting, T. A., & Fischer, C. N. (1996). Demand-Driven Register Allocation. ACM Transactions on Programming Languages and Systems, 18(6), 683-710.
  More info

  Abstract: A new global register allocation technique, demand-driven register allocation, is described. Demand-driven register allocation quantifies the costs and benefits of allocating variables to registers over live ranges so that high-quality allocations can be made. Local allocation is done first, and then global allocation is done iteratively beginning in the the most deeply nested loops. Because local allocation precedes global allocation, demand-driven allocation does not interfere with the use of well-known, high-quality local register allocation and instruction-scheduling techniques.
• Proebsting, T. A., & Watterson, S. A. (1996). Filter fusion. Conference Record of the Annual ACM Symposium on Principles of Programming Languages, 119-130.
  More info

  Abstract: Filter Fusion is a new compiler optimization that eliminates the overhead of a modular design of independent filters, and automates the integration of arbitrary, independently designed filters. The Filter Fusion compiler (FCC) composes of filters and produces code that is as efficient as hand-integrated code. While Filter Fusion is well suited for systems software applications, no assumptions about its problem domain are made. FCC places few restrictions on the filters it integrates. It also handles arbitrary control flow and data manipulations within each filter.
• Kurlander, S. M., Proebsting, T. A., & Fischer, C. N. (1995). Efficient instruction scheduling for delayed-load architectures. ACM Transactions on Programming Languages and Systems, 17(5), 740-776.
  More info

  Abstract: A fast, optimal code-scheduling algorithm for processors with a delayed load of one instruction cycle is described. The algorithm minimizes both execution time and register use and runs in time proportional to the size of the expression-tree. An extension that spills registers when too few registers are available is also presented. The algorithm also performs very well for delayed loads of greater than one instruction cycle. A heuristic that schedules DAGs and is based on our optimal expression-tree-scheduling algorithm is presented and compared with Goodman and Hsu's algorithm Integrated Prepass Scheduling (IPS). Both schedulers perform well on benchmarks with small basic blocks, but on large basic blocks our scheduler outperforms IPS and is significantly faster.
• Montz, A. B., Mosberger, D., O'Malley, S. W., Peterson, L. L., & Proebsting, T. A. (1995). Scout: A communications-oriented operating system. Proceedings of the Workshop on Hot Topics in Operating Systems - HOTOS, 58-61.
  More info

  Abstract: Scout is new communication-centric operating system. The principle scout abstraction (the path) is an attempt to capture all of the operating system infrastructure necessary to insure that a given network connection can achieve high and predictable performance in the face of other connections and other system loads.
• Proebsting, T. A. (1995). BURS automata generation. ACM Transactions on Programming Languages and Systems, 17(3), 461-486.
  More info

  Abstract: A simple and efficient algorithm for generating bottom-up rewrite system (BURS) tables is described. A small code-generator generator implementation produces BURS tables efficiently, even for complex instruction set descriptions. The algorithm does not require novel data structures or complicated algorithmic techniques. Previously published methods for on-the-fly elimination of states are generalized and simplified to create a new method, triangle trimming, that is employed in the algorithm. A prototype implementation, burg, generates BURS tables very efficiently.
• Proebsting, T. A. (1995). Optimizing an ANSI C interpreter with superoperators. Conference Record of the Annual ACM Symposium on Principles of Programming Languages, 322-332.
  More info

  Abstract: This paper introduces superoperators, an optimization technique for bytecoded interpreters. Superoperators are virtual machine operations automatically synthesized from smaller operations to avoid costly per-operation overheads. Superoperators decrease executable size and can double or triple the speed of interpreted programs. The paper describes a simple and effective heuristic for inferring powerful superoperators from the usage patterns of simple operators. The paper describes the design and implementation of a hybrid translator/interpreter that employs superoperators. From a specification of the superoperators (either automatically inferred or manually chosen), the system builds an efficient implementation of the virtual machine in assembly language. The system is easily retargetable and currently runs on the MIPS R3000 and the SPARC.
• Proebsting, T. A., & Fraser, C. W. (1994). Detecting pipeline structural hazards quickly. Conference Record of the Annual ACM Symposium on Principles of Programming Languages, 280-286.
  More info

  Abstract: This paper describes a method for detecting structural hazards 5-80 times faster than its predecessors, which generally have simulated the pipeline at compile time. It accepts a compact specification of the pipeline and creates a finite-state automation that can detect structural hazards in one table lookup per instruction.
• Fraser, C. W., Hanson, D. R., & Proebsting, T. A. (1992). Engineering a simple, efficient code-generator generator. ACM letters on programming languages and systems, 1(3), 213-226.
  More info

  Abstract: Many code-generator generators use tree pattern matching and dynamic programming. This paper describes a simple program that generates matchers that are fast, compact, and easy to understand. It is simpler than common alternatives: 200-700 lines of Icon or 950 lines of C versus 3000 lines of C for Twig and 5000 for burg. Its matchers run up to 25 times faster than Twig's. They are necessarily slower than burg's BURS (bottom-up rewrite system) matchers, but they are more flexible and still practical.
• Proebsting, T. A. (1992). Simple and efficient BURS table generation. SIGPLAN Notices (ACM Special Interest Group on Programming Languages), 331-340.
  More info

  Abstract: A simple and efficient algorithm for generating bottom-up rewrite system (BURS) tables is described. A small prototype implementation produces tables 10 to 30 times more quickly than the best current techniques. The algorithm does not require novel data structures or complicated algorithmic techniques. Previously published methods for on-the-fly elimination of states are generalized and simplified to create a new method, triangle trimming, that is employed in the algorithm.
• Proebsting, T. A., & Fischer, C. N. (1992). Probabilistic register allocation. SIGPLAN Notices (ACM Special Interest Group on Programming Languages), 300-310.
  More info

  Abstract: A new global register allocation technique, probabilistic register allocation, is described. Probabilistic register allocation quantifies the costs and benefits of allocating variables to registers over live ranges so that excellent allocation choices can be made. Local allocation is done first, and then global allocation is done iteratively beginning in the the most deeply nested loops. Because local allocation precedes global allocation, probabilistic allocation does not interfere with the use of well-known, high-quality local register allocation and instruction scheduling techniques.