Cooper_Engineering_a_Compiler(Second Edition) (Rice), страница 91

If that is not the case,then the values in rj and rk must be decremented by the correspondinglower bounds. The multiplies can be replaced by shifts in this example.Using indirection vectors, the reference requires just two operations perdimension. This property made the indirection-vector scheme efficient onsystems in which memory access is fast relative to arithmetic—for example,on most computer systems prior to 1985.

As the cost of memory accesses hasincreased relative to arithmetic, this scheme has lost its advantage in speed.On cache-based machines, locality is critical to performance. When arraysgrow to be much larger than the cache, storage order affects locality. Rowmajor and column-major storage schemes produce good locality for somearray-based operations. The locality properties of an array implemented withindirection vectors are harder for the compiler to predict and, perhaps, tooptimize.Accessing Array-Valued ParametersWhen an array is passed as a parameter, most implementations pass it byreference. Even in languages that use call by value for all other parameters,arrays are usually passed by reference.

Consider the mechanism required topass an array by value. The caller would need to copy each array element’svalue into the activation record of the callee. Passing the array as a referenceparameter can greatly reduce the cost of each call.If the compiler is to generate array references in the callee, it needs information about the dimensions of the array that is bound to the parameter. Infortran, for example, the programmer is required to declare the array usingeither constants or other formal parameters to specify its dimensions. Thus,fortran gives the programmer responsibility for passing to the callee theinformation that it needs to address correctly a parameter array.7.5 Storing and Accessing Arrays 367Other languages leave the task of collecting, organizing, and passing thenecessary information to the compiler.

The compiler builds a descriptor thatcontains both a pointer to the start of the array and the necessary informationfor each dimension. The descriptor has a known size, even when the array’ssize cannot be known at compile time. Thus, the compiler can allocate spacefor the descriptor in the ar of the callee procedure. The value passed in thearray’s parameter slot is a pointer to this descriptor, which is called a dopevector.When the compiler generates a reference to a formal-parameter array, it mustextract the information from the dope vector.

It generates the same addresspolynomial that it would use for a reference to a local array, loading valuesout of the dope vector as needed. The compiler must decide, as a matterof policy, which form of the address polynomial it will use. With the naiveaddress polynomial, the dope vector contains a pointer to the start of thearray, the lower bound of each dimension, and the sizes of all but one of thedimensions. With the address polynomial based on the false zero, the lowerbound information is unneeded.

Because it may compile caller and calleeseparately, the compiler must be consistent in its usage. In most cases, thecode to build the actual dope vector can be moved away from the call siteand placed in the caller’s prologue code. For a call inside a loop, this movereduces the call overhead.One procedure might be invoked from multiple call sites, each passing adifferent array. The pl/i procedure main in Figure 7.11a contains two callsto procedure fee. The first passes the array x, while the second passes y.Inside fee, the actual parameter (x or y) is bound to the formal parameter A.The code in fee for a reference to A needs a dope vector to describe the actualparameter.

Figure 7.11b shows the respective dope vectors for the two callsites, based on the false-zero version of the address polynomial.Notice that the cost of accessing an array-valued parameter or a dynamically sized array is higher than the cost of accessing a local array withfixed bounds. At best, the dope vector introduces additional memory references to access the relevant entries. At worst, it prevents the compiler fromperforming optimizations that rely on complete knowledge of an array’sdeclaration.7.5.4 Range CheckingMost programming-language definitions assume, either explicitly or implicitly, that a program refers only to array elements within the defined boundsof an array.

A program that references an out-of-bounds element is, bydefinition, not well formed. Some languages (for example, Java and Ada)require that out-of-bounds accesses be detected and reported. In otherDope vectora descriptor for an actual parameter arrayDope vectors may also be used for arrays whosebounds are determined at runtime.368 CHAPTER 7 Code Shapeprogram main;Abegin;100declare x(1:100,1:10,2:50),y(1:10,1:10,15:35) float;10...49call fee(x)call fee(y);end main;procedure fee(A)declare A(∗ ,∗ ,∗ ) float;begin;declare x float;declare i, j, k fixed binary;...x = A(i,j,k);...end fee;(a) Code that Passes Whole Arrays@x0At the First CallA@y0101021At the Second Call(b) Dope Vectors for the Call Sitesn FIGURE 7.11 Dope Vectors.languages, compilers have included optional mechanisms to detect andreport out-of-bounds array accesses.The simplest implementation of range checking, as this is called, insertsa test before each array reference.

The test verifies that each index valuefalls in the valid range for the dimension in which it is used. In an arrayintensive program, the overhead of such checks can be significant. Manyimprovements on this simple scheme are possible. The least expensive alternative is to prove, in the compiler, that a given reference cannot generate anout-of-bounds reference.If the compiler intends to insert range checks for array-valued parameters, itmay need to include additional information in the dope vectors.

For example, if the compiler uses the address polynomial based on the array’s falsezero, it has length information for each dimension, but not upper and lowerbound information. It might perform an imprecise test by checking the offsetagainst the array’s overall length.

However, to perform a precise test, thecompiler must include the upper and lower bounds for each dimension inthe dope vector and test against them.When the compiler generates runtime code for range checking, it insertsmany copies of the code to report an out-of-range subscript. Optimizingcompilers often contain techniques that improve range-checking code.7.6 Character Strings 369Checks can be combined. They can be moved out of loops. They can beproved redundant.

Taken together, such optimizations can radically reducethe overhead of range checking.SECTION REVIEWProgramming language implementations store arrays in a variety offormats. The primary ones are contiguous arrays in either row-majoror column-major order and disjoint arrays using indirection vectors.Each format has a distinct formula for computing the address of agiven element. The address polynomials for contiguous arrays can beoptimized with simple algebra to reduce their evaluation costs.Parameters passed as arrays require cooperation between the caller andthe callee. The caller must create a dope vector to hold the informationthat the callee requires.

The caller and callee must agree on the dopevector format.Review Questions1. For a two-dimensional array A stored in column-major order, writedown the address polynomial for the reference A[i,j]. Assume thatA is declared with dimensions (l1 : h1 ) and (l2 : h2 ) and that elements ofA occupy w bytes.2. Given an array of integers with dimensions A[0:99,0:89,0:109],how many words of memory are used to represent A as a compactrow-major order array? How many words are needed to representA using indirection vectors? Assume that both pointers and integersrequire one word each.7.6 CHARACTER STRINGSThe operations that programming languages provide for character data aredifferent from those provided for numerical data. The level of programminglanguage support for character strings ranges from c’s level of support,where most manipulation takes the form of calls to library routines, topl/i’s level of support, where the language provides first-class mechanisms to assign individual characters, specify arbitrary substrings, andconcatenate strings to form new strings.

To illustrate the issues that arisein string implementation, this section discusses string assignment, stringconcatenation, and the string-length computation.String operations can be costly. Older cisc architectures, such as the ibmS/370 and the dec vax, provide extensive support for string manipulation.Modern risc machines rely more heavily on the compiler to code these370 CHAPTER 7 Code Shapecomplex operations using a set of simpler operations.

The basic operation,copying bytes from one location to another, arises in many different contexts.7.6.1 String RepresentationsThe compiler writer must choose a representation for strings; the details ofthat representation have a strong impact on the cost of string operations.

Tosee this point, consider two common representations of a string b. The oneon the left is traditional in c implementations. It uses a simple vector ofcharacters, with a designated character (‘\0’) serving as a terminator. Theglyph 6 b represents a blank. The representation on the right stores the lengthof the string (8) alongside its contents. Many language implementations haveused this approach.abstring\08@babstring@bNull TerminationExplicit Length FieldIf the length field takes more space than the null terminator, then storingthe length will marginally increase the size of the string in memory. (Ourexamples assume the length is 4 bytes; in practice, it might be smaller.) However, storing the length simplifies several operations on strings. If a languageallows varying-length strings to be stored inside a string allocated with somefixed length, the implementor might also store the allocated length withthe string.