Cooper_Engineering_a_Compiler(Second Edition) (1157546), страница 92
Текст из файла (страница 92)
The compiler can use the allocated length for runtime boundschecking on assignment and concatenation.7.6.2 String AssignmentloadIcloadAIloadIcstoreAI@br@b , 2@ar2⇒⇒⇒⇒r@br2r@ar@a ,1String assignment is conceptually simple. In c, an assignment from the thirdcharacter of b to the second character of a can be written as a[1] = b[2];.On a machine with character-sized memory operations (cload and cstore),this translates into the simple code shown in the margin. (Recall that the firstcharacter in a is a[0] because c uses zero as the lower bound of all arrays.)If, however, the underlying hardware does not support character-orientedmemory operations, the compiler must generate more complex code.Assuming that both a and b begin on word boundaries, that a characteroccupies 1 byte, and that a word is 4 bytes, the compiler might emit thefollowing code:loadI 0x0000FF00loadI 0xFF00FFFF⇒ rC2// mask for 2nd char⇒ rC124 // mask for chars 1, 2, & 47.6 Character Strings 371loadIload@br@b⇒ r@b // address of b⇒ r1 // get 1st word of bandlshiftIr1 , rC2r2 , 8⇒ r2⇒ r3loadIload@ar@a⇒ r@a // address of a⇒ r4 // get 1st word of aandorstorer4 , rC124r3 , r5r6⇒ r5 // mask away 2nd char⇒ r6 // put in new 2nd char⇒ r@a // put it back in a// mask away others// move it over 1 byteThis code loads the word that contains b[2], extracts the character, shiftsit into position, masks it into the proper position in the word that containsa[1], and stores the result back into place.
In practice, the masks that thecode loads into rC2 and rC124 would likely be stored in statically initialized storage or computed. The added complexity of this code sequence mayexplain why character-oriented load and store operations are common.The code is similar for longer strings. pl/i has a string assignment operator.The programmer can write a statement such as a = b; where a and b havebeen declared as character strings. Assume that the compiler uses the explicitlength representation. The following simple loop will move the characters ona machine with byte-oriented cload and cstore operations:loadIloadAIloadIloadAIcmp LTcbra = b;@br@b , -4@ar@a , -4r2 , r1r3⇒⇒⇒⇒⇒→r@br1r@ar2r3Lsov , L1L1 : loadIcmp LTcbr0r4 , r1r5⇒ r4⇒ r5→ L2 , L3L2 : cloadAOcstoreAOaddIcmp LTcbrr@b , r4r6r4 , 1r4 , r1r7⇒⇒⇒⇒→L3 : storeAIr1⇒ r@a , -4r6r@a , r4r4r7L2 , L3// get b’s length// get a’s length// will b fit in a?// raise overflow// counter// more to copy?////////get char from bput it in aincrement offsetmore to copy?// set lengthNotice that this code tests the lengths of a and b to avoid overrunning a.(With an explicit length representation, the overhead is small.) The labelLsov represents a runtime error handler for string-overflow conditions.In c, which uses null termination for strings, the same assignment would bewritten as a character-copying loop.372 CHAPTER 7 Code ShapeloadIloadIloadIcloadt1 = a;t2 = b;do {*t1 ++ = *t2 ++;} while (*t2 != ‘\0’)L1 : cstoreaddIaddIcloadcmp NEcbr@b@aNULLr@b⇒⇒⇒⇒r@br@ar1r2r2r@b , 1r@a , 1r@br1 , r2r4⇒⇒⇒⇒⇒→r@a// store itr@b// bump pointersr@ar2// get next charr4L1 , L2L2 : nop// get pointers// terminator// get next char// next statementIf the target machine supports autoincrement on load and store operations,the two adds in the loop can be performed in the cload and cstore operations, which reduces the loop to four operations.
(Recall that c was originallyimplemented on the dec pdp/11, which supported auto-postincrement.)Without autoincrement, the compiler would generate better code by usingcloadAO and cstoreAO with a common offset. That strategy would only useone add operation inside the loop.To achieve efficient execution for long word-aligned strings, the compilercan generate code that uses whole-word loads and stores, followed by acharacter-oriented loop to handle any leftover characters at the end of thestring.If the processor lacks character-oriented memory operations, the code ismore complex. The compiler could replace the load and store in the loopbody with a generalization of the scheme for masking and shifting singlecharacters shown in the single character assignment. The result is a functional, but ugly, loop that requires many more instructions to copy b into a.The advantages of the character-oriented loops are simplicity and generality.
The character-oriented loop handles the unusual but complex cases, suchas overlapping substrings and strings with different alignments. The disadvantage of the character-oriented loop is its inefficiency relative to a loopthat moves larger blocks of memory on each iteration. In practice, the compiler might well call a carefully optimized library routine to implement thenontrivial cases.7.6.3 String ConcatenationConcatenation is simply a shorthand for a sequence of one or more assignments. It comes in two basic forms: appending string b to string a, andcreating a new string that contains a followed immediately by b.7.6 Character Strings 373The former case is a length computation followed by an assignment.
Thecompiler emits code to determine the length of a. Space permitting, it thenperforms an assignment of b to the space that immediately follows the contents of a. (If sufficient space is not available, the code raises an error atruntime.) The latter case requires copying each character in a and each character in b. The compiler treats the concatenation as a pair of assignments andgenerates code for the assignments.In either case, the compiler should ensure that enough space is allocatedto hold the result. In practice, either the compiler or the runtime systemmust know the allocated length of each string. If the compiler knows thoselengths, it can perform the check during code generation and avoid the runtime check.
In cases where the compiler cannot know the lengths of a and b,it must generate code to compute the lengths at runtime and to perform theappropriate test and branch.7.6.4 String LengthPrograms that manipulate strings often need to compute a character string’slength. In c programs, the function strlen in the standard library takes astring as its argument and returns the string’s length, expressed as an integer.In pl/i, the built-in function length performs the same function. The twostring representations described previously lead to radically different costsfor the length computation.1.
Null Terminated String The length computation must start at thebeginning of the string and examine each character, in order, until itreaches the null character. The code is similar to the c character-copyingloop. It requires time proportional to the length of the string.2. Explicit Length Field The length computation is a memory reference.In iloc, this becomes a loadI of the string’s starting address into aregister, followed by a loadAI to obtain the length. The cost is constantand small.The tradeoff between these representations is simple. Null termination savesa small amount of space, but requires more code and more time for the lengthcomputation.
An explicit length field costs one more word per string, butmakes the length computation take constant time.A classic example of a string optimization problem is finding the length thatwould result from the concatenation of two strings, a and b. In a language withstring operators, this might be written as length(a + b), where + signifiesconcatenation. This expression has two obvious implementations: constructthe concatenated string and compute its length (strlen(strcat(a,b)) in c),374 CHAPTER 7 Code Shapeand sum the lengths of a and b (strlen(a) + strlen(b) in c).
The lattersolution, of course, is desired. With an explicit length field, the operationcan be optimized to use two loads and an add.SECTION REVIEWIn principle, string operations are similar to operations on vectors. Thedetails of string representation and the complications introduced byissues of alignment and a desire for efficiency can complicate the codethat the compiler must generate. Simple loops that copy one characterat a time are easy to generate, to understand, and to prove correct. Morecomplex loops that move multiple characters per iteration can be moreefficient; the cost of that efficiency is additional code to handle the endcases. Many compilers simply fall back on a system supplied string-copyroutine, such as the Linux strcpy or memmove routines, for the complexcases.Review Questions1.
Write the ILOC code for the string assignment a ← b using wordlength loads and stores. (Use character-length loads and stores in apost loop to clean up the end cases.) Assume that a and b are wordaligned and nonoverlapping.2. How does your code change if a and b are character aligned ratherthan word aligned? What complications would overlapping stringsintroduce?7.7 STRUCTURE REFERENCESMost programming languages provide a mechanism to aggregate datatogether into a structure.
The c structure is typical; it aggregates individually named elements, often of different types. A list implementation, in c,might, for example, use the following structure to create lists of integers:struct node {int value;struct node *next;};struct node NILNode = {0, (struct node*) 0};struct node *NIL = & NILNode;7.7 Structure References 375Each node contains a single integer and a pointer to another node. The finaldeclarations creates a node, NILNode, and a pointer, NIL. They initializeNILNode with value zero and an illegal next pointer, and set NIL to pointat NILNode.
(Programs often use a designated NIL pointer to denote the endof a list.) The introduction of structures and pointers creates two distinctproblems for the compiler: anonymous values and structure layout.7.7.1 Understanding Structure LayoutsWhen the compiler emits code for structure references, it needs to knowboth the starting address of the structure instance and the offset and lengthof each structure element. To maintain these facts, the compiler can build aseparate table of structure layouts.
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.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
