K. Cooper, L. Torczon - Engineering a Compiler (2011 - 2nd edition) (798440), страница 59
Текст из файла (страница 59)
All other constants were represented with a singlepairc1c2AST Designed for Editingconstant(c1,c2)AST for Compiling228 CHAPTER 5 Intermediate RepresentationsSTORAGE EFFICIENCY AND GRAPHICAL REPRESENTATIONSMany practical systems have used abstract syntax trees to represent thesource text being translated. A common problem encountered in thesesystems is the size of the AST relative to the input text. Large data structurescan limit the size of programs that the tools can handle.The AST nodes in the Rn Programming Environment were large enoughthat they posed a problem for the limited memory systems of 1980sworkstations.
The cost of disk I/O for the trees slowed down all the Rntools.No single problem leads to this explosion in AST size. Rn had only one kindof node, so that structure included all the fields needed by any node. Thissimplified allocation but increased the node size. (Roughly half the nodeswere leaves, which need no pointers to children.) In other systems, thenodes grow through the addition of myriad minor fields used by one passor another in the compiler.
Sometimes, the node size increases over time,as new features and passes are added.Careful attention to the form and content of the AST can shrink its size.In Rn , we built programs to analyze the contents of the AST and how theAST was used. We combined some fields and eliminated others. (In somecases, it was less expensive to recompute information than to write it andread it.) In a few cases, we used hash linking to record unusual facts—usingone bit in the field that stores each node’s type to indicate the presenceof additional information stored in a hash table. (This scheme reduced thespace devoted to fields that were rarely used.) To record the AST on disk,we converted it to a linear representation with a preorder treewalk; thiseliminated the need to record any internal pointers.In Rn , these changes reduced the size of ASTs in memory by roughly 75percent.
On disk, after the pointers were removed, the files were abouthalf the size of their memory representation. These changes let Rn handlelarger programs and made the tools more responsive.node that contained a pointer to the constant’s actual text.
Using a similar format for complex constants would have complicated some operations,such as editing the complex constants and loading them into registers. Itwould have simplified others, such as comparing two constants. Taken overthe entire system, the simplifications would likely have outweighed thecomplications.Abstract syntax trees have found widespread use. Many compilers and interpreters use them; the level of abstraction that those systems need varieswidely.
If the compiler generates source code as its output, the ast typically has source-level abstractions. If the compiler generates assembly code,5.2 Graphical IRs 229the final version of the ast is usually at or below the abstraction level of themachine’s instruction set.Directed Acyclic GraphsWhile the ast is more concise than a syntax tree, it faithfully retains thestructure of the original source code. For example, the ast for a × 2 + a × 2 × bcontains two distinct copies of the expression a × 2. A directed acyclic graph(dag) is a contraction of the ast that avoids this duplication. In a dag, nodescan have multiple parents, and identical subtrees are reused.
Such sharingmakes the dag more compact than the corresponding ast.For expressions without assignment, textually identical expressions mustproduce identical values. The dag for a × 2 + a × 2 × b , shown to the left,reflects this fact by sharing a single copy of a × 2. The dag encodes anexplicit hint for evaluating the expression.
If the value of a cannot changebetween the two uses of a, then the compiler should generate code toevaluate a × 2 once and use the result twice. This strategy can reduce thecost of evaluation. However, the compiler must prove that a’s value cannot change. If the expression contains neither assignment nor calls to otherprocedures, the proof is easy. Since an assignment or a procedure call canchange the value associated with a name, the dag construction algorithmmust invalidate subtrees as the values of their operands change.dags are used in real systems for two reasons. If memory constraints limitthe size of programs that the compiler can handle, using a dag can help byreducing the memory footprint. Other systems use dags to expose redundancies.
Here, the benefit lies in better compiled code. These latter systemstend to use the dag as a derivative ir—building the dag, transforming thedefinitive ir to reflect the redundancies, and discarding the dag.Level of AbstractionAll of our example trees so far have shown near-source irs. Compilersalso use low-level trees. Tree-based techniques for optimization and codegeneration, in fact, may require such detail.
As an example, consider thestatement w ← a - 2 × b. A source-level ast creates a concise form, as shownin Figure 5.2a. However, the source-level tree lacks much of the detailneeded to translate the statement into assembly code. A low-level tree,shown in Figure 5.2b, can make that detail explicit. This tree introduces fournew node types. A val node represents a value already in a register. A numnode represents a known constant. A lab node represents an assembly-levellabel, typically a relocatable symbol.
Finally, u is an operator that dereferences a value; it treats the value as a memory address and returns the contentsof the memory at that address.Directed acyclic graphA DAG is an AST with sharing. Identical subtrees areinstantiated once, with multiple parents.+××ab2230 CHAPTER 5 Intermediate Representations←+-←valrarp-wnum4×num2×a2+bvalrarp(a) Source-Level ASTnumlab@G-16(b) Low-Level AST+num12n FIGURE 5.2 Abstract Syntax Trees with Different Levels of Abstraction.Data areaThe compiler groups together storage for valuesthat have the same lifetime and visibility. We callthese blocks of storage data areas.The low-level tree reveals the address calculations for the three variables.w is stored at offset 4 from the pointer in rarp , which holds the pointer to thedata area for the current procedure.
The double dereference of a shows thatit is a call-by-reference formal parameter accessed through a pointer stored16 bytes before rarp . Finally, b is stored at offset 12 after the label @G.The level of abstraction matters because the compiler can, in general, onlyoptimize details that are exposed in the ir. Properties that are implicitin the ir are hard to change, in part because the compiler would needto translate implicit facts in different, instance-specific ways. For example,to customize the code generated for an array reference, the compiler mustrewrite the related ir expressions.
In a real program, different array references are optimized in different ways, each according to the surroundingcontext. For the compiler to tailor those references, it must be able to writedown the improvements in the ir.As a final point, notice that the representations for the variable referencesin the low-level tree reflect the different interpretations that occur on theright and left side of the assignment.
On the left-hand side, w evaluates to anaddress, while both a and b evaluate to values because of the u operator.5.2.2 GraphsWhile trees provide a natural representation for the grammatical structure ofthe source code discovered by parsing, their rigid structure makes them lessuseful for representing other properties of programs. To model these aspectsof program behavior, compilers often use more general graphs as irs. Thedag introduced in the previous section is one example of a graph.5.2 Graphical IRs 231Control-Flow GraphThe simplest unit of control flow in a program is a basic block—a maximallength sequence of straightline, or branch-free, code.
A basic block is asequence of operations that always execute together, unless an operationraises an exception. Control always enters a basic block at its first operationand exits at its last operation.Basic blocka maximal-length sequence of branch-free codeA control-flow graph (cfg) models the flow of control between the basicblocks in a program. A cfg is a directed graph, G = (N , E).
Each noden ∈ N corresponds to a basic block. Each edge e = (ni , n j ) ∈ E correspondsto a possible transfer of control from block ni to block n j .Control-flow graphA CFG has a node for every basic block and an edgefor each possible control transfer between blocks.To simplify the discussion of program analysis in Chapters 8 and 9, weassume that each cfg has a unique entry node, n0 , and a unique exit node,n f . In the cfg for a procedure, n0 corresponds to the procedure’s entry point.If a procedure has multiple entries, the compiler can insert a unique n0 andadd edges from n0 to each actual entry point.
Similarly, n f corresponds tothe procedure’s exit. Multiple exits are more common than multiple entries,but the compiler can easily add a unique n f and connect each of the actualexits to it.The cfg provides a graphical representation of the possible runtime controlflow paths. The cfg differs from the syntax-oriented irs, such as an ast, inwhich the edges show grammatical structure. Consider the following cfg fora while loop:while(i < 100)beginwhile i < 100stmt1stmt2stmt1endstmt2The edge from stmt1 back to the loop header creates a cycle; the ast for thisfragment would be acyclic. For an if-then-else construct, the cfg is acyclic:if (x = y)then stmt1else stmt2stmt3if (x = y)stmt2stmt1stmt3It shows that control always flows from stmt1 and stmt2 to stmt3 . In an ast,that connection is implicit, rather than explicit.Compilers typically use a cfg in conjunction with another ir. The cfg represents the relationships among blocks, while the operations inside a blockIt begins with a labelled operation and ends witha branch, jump, or predicated operation.We use the acronym CFG for both context-freegrammar (see page 86) and control-flow graph.The meaning should be clear from context.232 CHAPTER 5 Intermediate Representations12345678910loadAIrarp , @a ⇒ raloadI2loadAIrarp , @b ⇒ rbrarp , @c ⇒ rcloadAIloadAI⇒ r2multrarp , @d ⇒ rdra , r2⇒ ramultra , rbmultra , rcmultra , rdstoreAI ra⇒⇒⇒⇒1rarp26rararararp , @a34758910n FIGURE 5.3 An ILOC Basic Block and Its Dependence Graph.are represented with another ir, such as an expression-level ast, a dag, orone of the linear irs.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
