The value dependence graph (VDG) is a sparse dataflow-like representation that simplifies program analysis and transformation. It is a functional representation that represents control flow as data flow and makes explicit all machine quantities, such as stores and I/O channels. We are developing a compiler that builds a VDG representing a program, analyzes and transforms the VDG, then produces a control flow graph (CFG) [ASU86] from the optimized VDG. This framework simplifies transformations and improves upon several published results. For example, it enables more powerful code motion than [CLZ86, FOW87], eliminates as many redundancies as [AWZ88, RWZ88] (except for redundant loops), and provides important information to the code scheduler [BR91]. We exhibit a fast, one-pass method for elimination of partial redundancies that never performs redundant code motion [KFS92, DS93] and is simpler than the classical [MR79, Dha91] or SSA [RWZ88] methods. These results accrue from eliminating the CFG from the analysis/transformation phases and using demand dependences in preference to control dependences.

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.

Abstract A common technique for improving the speed of program specialization is to specialize the program specializer itself on the program to be specialized, creating a custom program generator . Much research has been devoted to the problem of generating efficient program generators, which do not perform reductions at program generation time which could instead have been performed when the program generator was constructed. The conventional wisdom holds that only program specializers using binding-time approximations can be specialized into such efficient program generators. This paper argues that this is not the case, and demonstrates that the specialization of a nontrivial online program specializer similar to the original ‘naive MIX’ can indeed yield an efficient program generator. The key to our argument is that, while the use of binding-time information at program generator generation time is necessary for the construction of an efficient custom specializer, the use of explicit binding-time approximation techniques is not. This allows us to distinguish the problem at hand (i.e. the use of binding-time information during program generator generation) from particular solutions to that problem (i.e. offline specialization). We show that, given a careful choice of specializer data structures, and sufficiently powerful specialization techniques, binding-time information can be inferred and utilized without explicit approximations. This allows the construction of efficient, optimizing program generators from online program specializers.

1 Introduction As the size and complexity of digital circuits grows, so does need for logic simulation. Recent research has focused on compiled simulation because it provides substantially better performance than interpretive methods. In compiled simulation, a program is generated from the circuit to be simulated. Running this program, called a compiled simulator, then simulates the circuit. Compiled simulation executes much more rapidly than interpreted simulation because the overhead of tranversing and interpreting the data structure that describes the circuit is done only once, when the compiled simulator is created.

article Free Access Share on Using types to avoid redundant specialization Authors: Erik Ruf Computer Systems Laboratory, Stanford University, Stanford, CA Computer Systems Laboratory, Stanford University, Stanford, CAView Profile , Daniel Weise Computer Systems Laboratory, Stanford University, Stanford, CA Computer Systems Laboratory, Stanford University, Stanford, CAView Profile Authors Info & Claims ACM SIGPLAN NoticesVolume 26Issue 9Sept. 1991 pp 321–333https://doi.org/10.1145/115866.115902Published:01 May 1991Publication History 16citation228DownloadsMetricsTotal Citations16Total Downloads228Last 12 Months22Last 6 weeks1 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

The ideas behind Silica Pithecus, a program for verifying synchronous digital MOS VLSI circuits, are described. Silica Pithecus accepts the schematic of an MOS VLSI circuit, declarations of the logical relationships between the input signals, and a specification of the intended digital behavior of the circuit. If the circuit fails to meet its specification, Silica Pithecus returns to the designer the reason it fails to do so. Unlike previous verification systems, which used digital models of MOS components, Silica Pithecus employs a realistic electrical model. It operates hierarchically, interactively, and incrementally. The key idea is to generate and use constraints for verification. Constraints are predicates that restrict the input signals a circuit accepts. Employing explicit constraints has many benefits. First, they enable hierarchical verification, which allows large circuits to be verified. Second, errors can be pinpointed and explained to the designer. Third, all constraints (at the electrical level) can be algorithmically and automatically generated.>

This report describes the ideas behind Silica Pithecus, a program which verifies synchronous digital MOS VLSI circuits. Silica Pithecus accepts the schematic of an MOS VLSI circuit, declarations of the logical relationships between the inputs signals (e.g., which inputs are mutually exclusive), and a specification of the intended digital behavior of the circuit. If the circuit fails to meet its specification Silica Pithecus returns to the designer the precise reason it fails to do so. Unlike previous verification systems, Silica Pithecus employs a realistic electrical model. It also automatically generates the constraints on the inputs of a circuit which ensure the circuit will exhibit its intended digital behavior. These constraints are necessary for hierarchical verification. Silica Pithecus operates hierarchically, interactively, and incrementally.