K. Cooper, L. Torczon - Engineering a Compiler (2011 - 2nd edition) (798440), страница 94
Текст из файла (страница 94)
This compile-time table must include thetextual name for each structure element, its offset within the structure, andits source-language data type. For the list example on page 374, the compilermight build the tables shown in Figure 7.12. Entries in the element table usefully qualified names to avoid conflicts due to reuse of a name in severaldistinct structures.With this information, the compiler can easily generate code for structurereferences.
Returning to the list example, the compiler might translate thereference p1 -> next, for a pointer to node p1, into the following iloccode:loadI 4⇒ r1loadAO rp1 , r1 ⇒ r2// offset of next// value of p1->nextStructure Layout TableName1st ElementLengthnode8......Structure Element TableNameLengthOffsetTypenode.value40intnode.next44struct node *.........n FIGURE 7.12 Structure Tables for the List Example....Next...376 CHAPTER 7 Code ShapeHere, the compiler finds the offset of next by following the table from thenode entry in the structure table to the chain of entries for node in the ele-ment table. Walking that chain, it finds the entry for node.next and itsoffset, 4.In laying out a structure and assigning offsets to its elements, the compilermust obey the alignment rules of the target architecture. This may force itto leave unused space in the structure.
The compiler confronts this problemwhen it lays out the structure declared on the left:struct example {int fee;04feedouble fum;};1216fie20foe2428fum···Elements in Declaration Orderdouble fie;int foe;8···04fie812fum1616feefoeElements Ordered by AlignmentThe top-right drawing shows the structure layout if the compiler is constrained to place the elements in declaration order.
Because fie and fummust be doubleword aligned, the compiler must insert padding after fee andfoe. If the compiler could order the elements in memory arbitrarily, it coulduse the layout shown on the bottom left, which needs no padding. This is alanguage-design issue: the language definition specifies whether or not thelayout of a structure is exposed to the user.7.7.2 Arrays of StructuresMany programming languages allow the user to declare an array of structures. If the user is allowed to take the address of a structure-valued elementof an array, then the compiler must lay out the data in memory as multiplecopies of the structure layout.
If the programmer cannot take the addressof a structure-valued element of an array, the compiler might lay out thestructure as if it were a structure composed of elements that are, themselves,arrays. Depending on how the surrounding code accesses the data, these twostrategies may have strikingly different performance on a system with cachememory.To address an array of structures laid out as multiple copies of thestructure, the compiler uses the array-address polynomials described inSection 7.5.
The overall length of the structure, including any neededpadding, becomes the element size w in the address polynomial. The polynomial generates the address of the start of the structure instance. To obtainthe value of a specific element, the element’s offset is added to the instance’saddress.7.7 Structure References 377If the compiler has laid out the structure with elements that are arrays, itmust compute the starting location of the element array using the offset-tableinformation and the array dimension. This address can then be used as thestarting point for an address calculation using the appropriate array-addresspolynomial.7.7.3 Unions and Runtime TagsMany languages allow the programmer to create a structure with multiple, data-dependent interpretations. In c, the union construct has this effect.Pascal achieved the same effect with its variant records.Unions and variants present one additional complication.
To emit code for areference to an element of a union, the compiler must resolve the reference toa specific offset. Because a union is built from multiple structure definitions,the possibility exists that element names are not unique. The compiler mustresolve each reference to a unique offset and type in the runtime object.This problem has a linguistic solution.
The programming language can forcethe programmer to make the reference unambiguous. Consider the c declarations shown in Figure 7.13. Panel a shows declarations for two kinds ofnode, one that holds an integer value and another that holds a floating-pointvalue.The code in panel b declares a union named one that is either an n1 or an n2. Toreference an integer value, the programmer specifies u1.inode.value. Toreference a floating-point value, the programmer specifies u1.fnode.value.The fully qualified name resolves any ambiguity.struct n1 {union one {int kind;struct n1 inode;int value;struct n2 fnode;};} u1;union two {struct {int kind;int value;} inode;struct n2 {struct {int kind;int kind;float value;float value;};} fnode;} u2;(a) Basic Structures(b) Union of Structuresn FIGURE 7.13 Union Declarations in C.(c) Union of Implicit Structures378 CHAPTER 7 Code ShapeThe code in panel c declares a union named two that has the same propertiesas one.
The declaration of two explicitly declares its internal structure. Thelinguistic mechanism for disambiguating a reference to value, however, isthe same—the programmer specifies a fully qualified name.As an alternative, some systems have relied on runtime discrimination. Here,each variant in the union has a field that distinguishes it from all othervariants—a “tag.” (For example, the declaration of two, might initializekind to one for inode and to two for fnode.) The compiler can then emitcode to check the value of the tag field and ensure that each object is handled correctly. In essence, it emits a case statement based on the tag’s value.The language may require that the programmer define the tag field and itsvalues; alternatively, the compiler could generate and insert tags automatically. In this latter case, the compiler has a strong motivation to perform typechecking and remove as many checks as possible.7.7.4 Pointers and Anonymous ValuesA c program creates an instance of a structure in one of two ways.
It candeclare a structure instance, as with NilNode in the earlier example. Alternatively, the code can explicitly allocate a structure instance. For a variablefee declared as a pointer to node, the allocation would look like:fee = (struct node *) malloc(sizeof(node));The only access to this new node is through the pointer fee.
Thus, we thinkof it as an anonymous value, since it has no permanent name.Because the only name for an anonymous value is a pointer, the compilercannot easily determine if two pointer references specify the same memorylocation. Consider the code fragment12345678p1 = (node *) malloc(sizeof(node));p2 = (node *) malloc(sizeof(node));if (...)then p3 = p1;else p3 = p2;p1->value = ...;p3->value = ...;...= p1->value;7.7 Structure References 379The first two lines create anonymous nodes. Line 6 writes through p1 whileline 7 writes through p3. Because of the if-then-else, p3 can refer toeither the node allocated in line 1 or in line 2.
Finally, line 8 referencesp1->value.The use of pointers limits the compiler’s ability to keep values in registers.Consider the sequence of assignments in lines 6 through 8. Line 8 reuseseither the value assigned in line 6 or the value assigned in line 7. As amatter of efficiency, the compiler should avoid storing that value to memory and reloading it. However, the compiler cannot easily determine whichvalue line 8 uses. The answer to that question depends on the value of theconditional expression in line 3.While it may be possible to know the value of the conditional expression incertain specific instances (for example, 1 > 2), it is undecidable in the generalcase. Unless the compiler knows the value of the conditional expression,it must emit conservative code for the three assignments. It must load thevalue used in line 8 from memory, even though it recently had the value in aregister.The uncertainty introduced by pointers prevents the compiler from keeping values used in pointer-based references in registers.
Anonymous objectsfurther complicate the problem because they introduce an unbounded set ofobjects to track. As a result, statements that involve pointer-based referencesare often less efficient than the corresponding computations on unambiguouslocal values.A similar effect occurs for code that makes intensive use of arrays.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
