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. If there is a cache miss – x is not in the cache – then the processor fetches x from main memory and places a copy of x in the cache so that the next reference to x will be a cache hit.

The trees generated by the semantic analysis phase must be translated into assembly or machine language. The operators of the Tree language are chosen carefully to match the capabilities of most machines. However, there are certain aspects of the tree language that do not correspond exactly with machine languages, and some aspects of the Tree language interfere with compile-time optimization analyses.

For example, it's useful to be able to evaluate the subexpressions of an expression in any order. But the subexpressions of Tree.exp can contain side effects – ESEQ and CALL nodes that contain assignment statements and perform input/output. If tree expressions did not contain ESEQ and CALL nodes, then the order of evaluation would not matter.

Some of the mismatches between Trees and machine-language programs are

• The cjump instruction can jump to either of two labels, but real machines' conditional jump instructions fall through to the next instruction if the condition is false.

• eseq nodes within expressions are inconvenient, because they make different orders of evaluating subtrees yield different results.

• call nodes within expressions cause the same problem.

• call nodes within the argument-expressions of other call nodes will cause problems when trying to put arguments into a fixed set of formal-parameter registers.

Why does the Tree language allow eseq and two-way cjump, if they are so troublesome? Because they make it much more convenient for the Translate (translation to intermediate code) phase of the compiler.

Loops are pervasive in computer programs, and a great proportion of the execution time of a typical program is spent in one loop or another. Hence it is worthwhile devising optimizations to make loops go faster. Intuitively, a loop is a sequence of instructions that ends by jumping back to the beginning. But to be able to optimize loops effectively we will use a more precise definition.

A loop in a control-flow graph is a set of nodes S including a header node h with the following properties:

• From any node in S there is a path of directed edges leading to h.

• There is a path of directed edges from h to any node in S.

• There is no edge from any node outside S to any node in S other than h.

Thus, the dictionary definition (from Webster's) is not the same as the technical definition.

Figure 18.1 shows some loops. A loop entry node is one with some predecessor outside the loop; a loop exit node is one with a successor outside the loop. Figures 18.1c, 18.1d, and 18.1f illustrate that a loop may have multiple exits, but may have only one entry. Figures 18.1e and 18.1f contain nested loops.

REDUCIBLE FLOW GRAPHS

A reducible flow graph is one in which the dictionary definition of loop corresponds more closely to the technical definition; but let us develop a more precise definition.

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

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.

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, we show how to compile MiniJava, a simple but nontrivial subset of Java. 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. MiniJava is easily extended to support class extension or higher-order functions, 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 MiniJava 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 Java – a simple object-oriented language. Java is safe, in that programs cannot circumvent the type system to violate abstractions; and it has garbage collection, which greatly simplifies the management of dynamic storage allocation.

Many dataflow analyses need to find the use sites of each defined variable or the definition sites of each variable used in an expression. The def-use chain is a data structure that makes this efficient: For each statement in the flow graph, the compiler can keep a list of pointers to all the use sites of variables defined there, and a list of pointers to all definition sites of the variables used there. In this way the compiler can hop quickly from use to definition to use to definition.

An improvement on the idea of def-use chains is static single-assignment form, or SSA form, an intermediate representation in which each variable has only one definition in the program text. The one (static) definition site may be in a loop that is executed many (dynamic) times, thus the name static single-assignment form instead of single-assignment form (in which variables are never redefined at all).

The SSA form is useful for several reasons:

1. Dataflow analysis and optimization algorithms can be made simpler when each variable has only one definition.

2. If a variable has N uses and M definitions (which occupy about N + M instructions in a program), it takes space (and time) proportional to N · M to represent def-use chains – a quadratic blowup (see Exercise 19.8). For almost all realistic programs, the size of the SSA form is linear in the size of the original program (but see Exercise 19.9).

3. […]

The front end of the compiler translates programs into an intermediate language with an unbounded number of temporaries. This program must run on a machine with a bounded number of registers. Two temporaries a and b can fit into the same register, if a and b are never “in use” at the same time. Thus, many temporaries can fit in few registers; if they don't all fit, the excess temporaries can be kept in memory.

Therefore, the compiler needs to analyze the intermediate-representation program to determine which temporaries are in use at the same time. We say a variable is live if it holds a value that may be needed in the future, so this analysis is called liveness analysis.

To perform analyses on a program, it is often useful to make a control-flow graph. Each statement in the program is a node in the flow graph; if statement x can be followed by statement y, there is an edge from x to y. Graph 10.1 shows the flow graph for a simple loop.

Let us consider the liveness of each variable (Figure 10.2). A variable is live if its current value will be used in the future, so we analyze liveness by working from the future to the past. Variable b is used in statement 4, so b is live on the 3 → 4 edge.

An optimizing compiler transforms programs to improve their efficiency without changing their output. There are many transformations that improve efficiency:

1. Register allocation: Keep two nonoverlapping temporaries in the same register.

2. Common-subexpression elimination: If an expression is computed more than once, eliminate one of the computations.

3. Dead-code elimination: Delete a computation whose result will never be used.

4. Constant folding: If the operands of an expression are constants, do the computation at compile time.

This is not a complete list of optimizations. In fact, there can never be a complete list.

NO MAGIC BULLET

Computability theory shows that it will always be possible to invent new optimizing transformations.

Let us say that a fully optimizing compiler is one that transforms each program P to a program Opt(P) that is the smallest program with the same input/output behavior as P. We could also imagine optimizing for speed instead of program size, but let us choose size to simplify the discussion.

For any program Q that produces no output and never halts, Opt(Q) is short and easily recognizable:

INTERMEDIATE REPRESENTATION FOR FLOW ANALYSIS

Therefore, if we had a fully optimizing compiler, we could use it to solve the halting problem; to see if there exists an input on which P halts, just see if Opt(P) is the one-line infinite loop. But we know that no computable algorithm can always tell whether programs halt, so a fully optimizing compiler cannot be written either.

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

We have seen in Chapter 6 that not all tasks can be implemented by a single CNN template; the XOR function is a typical example.

There are many tasks which are solved by applying several templates, or by applying one template several times. If we consider a template as an instruction with well-defined input and output, we can define a CNN subroutine or function (as in C-like languages) when applying several templates. We can build up processes and complete programs from functions and other instructions.

We define a subroutine by specifying the following items:

• the input/output parameters,

• the global task,

• the informal description of the algorithm,

• the CNN implementation.

In this chapter the CNN implementation is given by three equivalent ways:

the hardware schematics, supposing each CNN template (placed in the CNN Software Library) is implemented by a separate device containing discrete hard-wired cells and additional local (cell by cell) and global devices.

a flow diagram of the CNN algorithm, and

a list of consecutive instructions, henceforth called a program, written in a simple vocabulary involving the CNN analog and logic operations, henceforth called an analogic CNN language, or simply “α” language.

An Alpha Compiler is supposed to exist to translate the code into executable programs on CNN chips. We will describe this process later in Chapter 9.

Indeed, we follow the theory and practice of digital computers.