This chapter presents circuit and design details for clocked circuits (latches and flip-flops) and clock-generating circuits (controlled delay lines and oscillators). We show how the basic circuit elements presented in Chapter 4 can be combined to produce robust timing and clocking elements to implement the timing and synchronization systems of Chapters 9 and 10.

LATCHES AND FLIP-FLOPS

In Section 9.3.4 we discussed the timing properties of clocked storage elements (latches and flip-flops). In this section we will explore various CMOS circuits that implement these elements. Flip-flops are often composed of pairs of latches that are transparent on opposite phases of a single clock; therefore, we will first describe the design of level-sensitive latches and then show how these are arranged into flip-flops.

Level-Sensitive Latches

A latch passes its input to its output (with a small delay) when its clock is asserted; when the clock is deasserted, the input is ignored, and the output presents the most recent value on the input sampled during a narrow window in time around the asserted-to-deasserted clock transition. The fundamental component of a latch is a storage device, and CMOS latches are generally built on the basis of one of two distinctly different storage techniques: capacitive and regenerative, as illustrated in Figure 12-1.

Latches that use capacitive storage are actually sample-and-hold devices that store a continuous (analog) value, and they are said to be “dynamic” because, if the input switch is left open for too long, parasitic leakage currents present in CMOS circuits will eventually corrupt the data stored on the capacitor.

A timing convention governs when a transmitter drives symbols onto the signal line and when they are sampled by the receiver. A timing convention may be periodic, with a new symbol driven on a signal line at regular time intervals, or aperiodic, with new symbols arriving at irregular times. In either case a method is required to encode when the symbol arrives so that the receiver samples each symbol exactly once during its valid period. With periodic signals, if the nominal data rate is known, the receiver may use a local clock source to determine when the next symbol is to arrive. In this case, an occasional transition on the signal line to correct for drift between the transmitter and receiver clocks is all that is needed to encode symbol arrival times. For aperiodic signals, an explicit transition is required to signal the arrival of each symbol. This transition may be on a separate clock line that may be shared among several signals (bundled signaling). Alternatively, this transition may be encoded on the same lines as the signal value, as with dual-rail signaling, giving a timing convention that is insensitive to line-to-line skew.

The rate at which we can send symbols over a line or through a block of combinational logic is limited by the rise time of the transmitter and transmission medium, the sampling window of the receiver, and timing noise or uncertainty.

Digital logic requires a stable, quiet, DC supply voltage while drawing a large AC current with very high-frequency components comparable to signal rise times. It is not unusual for a high-performance digital circuit board to draw over 200 A from the primary power supply with the derivative at the point of use over 200 GA/s. However, with careful design, a power supply network can tolerate large variations in current draw while holding the supply voltage within a specified range (typically ±10% or less).

In this chapter we discuss the characteristics of power supply networks and their loads and explore several methods for providing quiet supplies for high-performance digital systems. We begin by examining the primarily inductive, off-chip power supply network in Section 5.1. The supply and ground are distributed over a network with inductive and resistive components. The current causes IR drops across the resistive components, and the derivative of the current causes Ldi/dt drops across the inductive components. In this section we look at the most commonly used passive method to provide load regulation: bypass capacitors, which supply the high-frequency components of the current demand and thus smooth the current load carried by the inductive components of the distribution network.

Section 5.2 examines active methods to control the power supply. Clamps and shunt regulators smooth the current profile of the load by adding an additional current in parallel with the load current.

Chapters 2–11 have described the fundamental components of a good compiler: a front end, which does lexical analysis, parsing, construction of abstract syntax, type-checking, and translation to intermediate code; and a back end, which does instruction selection, dataflow analysis, and register allocation.

What lessons have we learned? I hope that the reader has learned about the algorithms used in different components of a compiler and the interfaces used to connect the components. But the author has also learned quite a bit from the exercise.

My goal was to describe a good compiler that is, to use Einstein's phrase, “as simple as possible – but no simpler.” I will now discuss the thorny issues that arose in designing Tiger and its compiler.

Nested functions. Tiger has nested functions, requiring some mechanism (such as static links) for implementing access to nonlocal variables. But many programming languages in widespread use −C, C++, Java – do not have nested functions or static links. The Tiger compiler would become simpler without nested functions, for then variables would not escape, and the FindEscape phase would be unnecessary. But there are two reasons for explaining how to compile nonlocal variables. First, there are programming languages where nested functions are extremely useful – these are the functional languages described in Chapter 15.

Over the past decade, there have been several shifts in the way compilers are built. New kinds of programming languages are being used: object-oriented languages with dynamic methods, functional languages with nested scope and first-class function closures; and many of these languages require garbage collection. New machines have large register sets and a high penalty for memory access, and can often run much faster with compiler assistance in scheduling instructions and managing instructions and data for cache locality.

This book is intended as a textbook for a one- or two-semester course in compilers. Students will see the theory behind different components of a compiler, the programming techniques used to put the theory into practice, and the interfaces used to modularize the compiler. To make the interfaces and programming examples clear and concrete, I have written them in the ML programming language. Other editions of this book are available that use the C and Java languages.

Implementation project. The “student project compiler” that I have outlined is reasonably simple, but is organized to demonstrate some important techniques that are now in common use: abstract syntax trees to avoid tangling syntax and semantics, separation of instruction selection from register allocation, copy propagation to give flexibility to earlier phases of the compiler, and containment of target-machine dependencies. Unlike many “student compilers” found in textbooks, this one has a simple but sophisticated back end, allowing good register allocation to be done after instruction selection.

This book describes techniques, data structures, and algorithms for translating programming languages into executable code. A modern compiler is often organized into many phases, each operating on a different abstract “language.” The chapters of this book follow the organization of a compiler, each covering a successive phase.

To illustrate the issues in compiling real programming languages, I show how to compile Tiger, a simple but nontrivial language of the Algol family, with nested scope and heap-allocated records. Programming exercises in each chapter call for the implementation of the corresponding phase; a student who implements all the phases described in Part I of the book will have a working compiler. Tiger is easily modified to be functional or object-oriented (or both), and exercises in Part II show how to do this. Other chapters in Part II cover advanced techniques in program optimization. Appendix A describes the Tiger language.

The interfaces between modules of the compiler are almost as important as the algorithms inside the modules. To describe the interfaces concretely, it is useful to write them down in a real programming language. This book uses the C programming language.

To translate a program from one language into another, a compiler must first pull it apart and understand its structure and meaning, then put it together in a different way. The front end of the compiler performs analysis; the back end does synthesis.

The analysis is usually broken up into

Lexical analysis: breaking the input into individual words or “tokens”;

Syntax analysis: parsing the phrase structure of the program; and

Semantic analysis: calculating the program's meaning.

The lexical analyzer takes a stream of characters and produces a stream of names, keywords, and punctuation marks; it discards white space and comments between the tokens. It would unduly complicate the parser to have to account for possible white space and comments at every possible point; this is the main reason for separating lexical analysis from parsing.

Lexical analysis is not very complicated, but we will attack it with high-powered formalisms and tools, because similar formalisms will be useful in the study of parsing and similar tools have many applications in areas other than compilation.

LEXICAL TOKENS

A lexical token is a sequence of characters that can be treated as a unit in the grammar of a programming language. A programming language classifies lexical tokens into a finite set of token types.

Heap-allocated records that are not reachable by any chain of pointers from program variables are garbage. The memory occupied by garbage should be reclaimed for use in allocating new records. This process is called garbage collection, and is performed not by the compiler but by the runtime system (the support programs linked with the compiled code).

Ideally, we would say that any record that is not dynamically live (will not be used in the future of the computation) is garbage. But, as Section 10.1 explains, it is not always possible to know whether a variable is live. So we will use a conservative approximation: we will require the compiler to guarantee that any live record is reachable; we will ask the compiler to minimize the number of reachable records that are not live; and we will preserve all reachable records, even if some of them might not be live.

Figure 13.1 shows a Tiger program ready to undergo garbage collection (at the point marked garbage-collect here). There are only three program variables in scope: p, q, and r.

MARK-AND-SWEEP COLLECTION

Program variables and heap-allocated records form a directed graph. The variables are roots of this graph. A node n is reachable if there is a path of directed edges r → … → n starting at some root r. A graph-search algorithm such as depth-first search (Algorithm 13.2) can mark all the reachable nodes.

The Translate, Canon, and Codegen phases of the compiler assume that there are an infinite number of registers to hold temporary values and that move instructions cost nothing. The job of the register allocator is to assign the many temporaries to a small number of machine registers, and, where possible, to assign the source and destination of a move to the same register so that the move can be deleted.

From an examination of the control and dataflow graph, we derive an interference graph. Each node in the inteference graph represents a temporary value; each edge (t1, t2) indicates a pair of temporaries that cannot be assigned to the same register. The most common reason for an interference edge is that t1 and t2 are live at the same time. Interference edges can also express other constraints; for example, if a certain instruction a ← b ⊕ c cannot produce results in register r12 on our machine, we can make a interfere with r12.

Next we color the interference graph. We want to use as few colors as possible, but no pair of nodes connected by an edge may be assigned the same color. Graph coloring problems derive from the old mapmakers' rule that adjacent countries on a map should be colored with different colors.

An idealized random access memory (RAM) has N words indexed by integers such that any word can be fetched or stored – using its integer address – equally quickly. Hardware designers can make a big slow memory, or a small fast memory, but a big fast memory is prohibitively expensive. Also, one thing that speeds up access to memory is its nearness to the processor, and a big memory must have some parts far from the processor no matter how much money might be thrown at the problem.

Almost as good as a big fast memory is the combination of a small fast cache memory and a big slow main memory; the program keeps its frequently used data in cache and the rarely used data in main memory, and when it enters a phase in which datum x will be frequently used it may move x from the slow memory to the fast memory.

It's inconvenient for the programmer to manage multiple memories, so the hardware does it automatically. Whenever the processor wants the datum at address x, it looks first in the cache, and – we hope – usually finds it there.

To translate a program from one language into another, a compiler must first pull it apart and understand its structure and meaning, then put it together in a different way. The front end of the compiler performs analysis; the back end does synthesis.

The analysis is usually broken up into

Lexical analysis: breaking the input into individual words or “tokens”;

Syntax analysis: parsing the phrase structure of the program; and

Semantic analysis: calculating the program's meaning.

The lexical analyzer takes a stream of characters and produces a stream of names, keywords, and punctuation marks; it discards white space and comments between the tokens. It would unduly complicate the parser to have to account for possible white space and comments at every possible point; this is the main reason for separating lexical analysis from parsing.

Lexical analysis is not very complicated, but we will attack it with high powered formalisms and tools, because similar formalisms will be useful in the study of parsing and similar tools have many applications in areas other than compilation.

LEXICAL TOKENS

A lexical token is a sequence of characters that can be treated as a unit in the grammar of a programming language. A programming language classifies lexical tokens into a finite set of token types.