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.

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, Tel, 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.

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. Copyright © 2000 John Wiley & Sons, Ltd.

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. Copyright © 2000 John Wiley & Sons, Ltd.

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. 1 Introduction To execute virtual machine (VM) code on a client processor typically requires either a VM interpreter or a just-in-time (JIT) translator. Conventional wisdom dictates that the space/time tradeo# favors the interpreter approac...

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; yacc produces interpreted, table-driven parsers. Two attributes distinguish mule from other parser generators that create hard-coded LR parsers; mule is compatible wtih yacc (including yacc's 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. © 1998 John Wiley & Sons, Ltd.

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.

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.

Knowledge of low-level control flow is essential for many compiler optimizations. In systems with tail-call optimization, the determination of interprocedural control flow is complicated by the fact that because of tail-call optimization, control flow at procedure returns is not readily evident from the call graph of the program. This article shows how interprocedural control-flow analysis of first-order programs can be carried out using well-known concepts from parsing theory. In particular, we show that context-insensitive ( or zeroth-order) control-flow analysis corresponds to the notion of FOLLOW sets in context-free grammars, while context-sensitive (or first-order) control-flow analysis corresponds to the notion of LR(1) items. The control-flow information so obtained can be used to improve the precision of interprocedural dataflow analyses as well as to extend certain low-level code optimizations across procedure boundaries.

Article Free AccessFilter fusion Share on Authors: Todd A. Proebsting Department of Computer Science, University of Arizona, Tucson, AZ Department of Computer Science, University of Arizona, Tucson, AZView Profile , Scott A. Watterson Department of Computer Science, University of Arizona, Tucson, AZ Department of Computer Science, University of Arizona, Tucson, AZView Profile Authors Info & Claims POPL '96: Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languagesJanuary 1996 Pages 119–130https://doi.org/10.1145/237721.237760Online:01 January 1996Publication History 32citation32DownloadsMetricsTotal Citations32Total Downloads32Last 12 Months3Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

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 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.

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.

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.

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.

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.

Dynamic code generation allows aggressive optimization through the use of runtime information. Previous systems typically relied on ad hoc code generators that were not designed for retargetability, and did not shield the client from machine-specific details. We present a system, dcg, that allows clients to specify dynamically generated code in a machine-independent manner. Our one-pass code generator is easily retargeted and extremely efficient (code generation costs approximately 350 instructions per generated instruction). Experiments show that dynamic code generation increases some application speeds by over an order of magnitude.

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 finitestate automaton that can detect structural hazards in one table lookup per instruction. The automaton maintains an integer state that encodes all potential structural hazards for all instructions in the pipe. It accepts an instruction type and a state and either reports a hazard or produces the state that folds in the new instruction and advances the pipeline by one cy-

USC is a new stub compiler that generates stubs that perform many data conversion operations. USC is flexible and can be used in situations where previously only manual code generation was possible. USC generated code is up to 20 times faster than code generated by traditional argument marshaling schemes such as ASN.1 and Sun XDR. This paper presents the design of USC and a comprehensive set of experiments that compares USC performance with the best manually generated code and traditional stub compilers.

Abstract An O(n2) algorithm for splitting a case statement's jump table into the minimum number of subtables (of a given density) is presented. Previously, the problem was thought to be NP‐complete.

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 the on-the-fly elimination of states are generalized and simplified to create a new method, triangle trimming, that is employed in the algorithm.

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 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.

Article Linear-time, optimal code scheduling for delayed-load architectures Share on Authors: Todd A. Proebsting University of Wisconsin-Madison, Dept. of Computer Sciences, 1210 W. Dayton St., Madison, WI University of Wisconsin-Madison, Dept. of Computer Sciences, 1210 W. Dayton St., Madison, WIView Profile , Charles N. Fischer University of Wisconsin-Madison, Dept. of Computer Sciences, 1210 W. Dayton St., Madison, WI University of Wisconsin-Madison, Dept. of Computer Sciences, 1210 W. Dayton St., Madison, WIView Profile Authors Info & Claims PLDI '91: Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementationMay 1991 Pages 256–267https://doi.org/10.1145/113445.113467Online:01 May 1991Publication History 28citation670DownloadsMetricsTotal Citations28Total Downloads670Last 12 Months11Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access