Arrays Elements of arrays can be accessed quickly if the elements are stored in a block of consecutive locations. A one-dimensional array A: basea low width base is the address of the first location of the array A, width is the width of each array element. low is the index of the first array element location of A[i]>base+(i-low)*width CS308 Compiler Theory 11
Arrays • Elements of arrays can be accessed quickly if the elements are stored in a block of consecutive locations consecutive locations. A one-dimensional array A: … … baseA low i width baseA is the address of the first location of the array A, width is the width of each array element. low is the index of the first array element CS308 Compiler Theory 11 location of A[i] Î baseA+(i-low)*width
Arrays (cont.) base+(i-low)*width can be re-written as i*width (basea-low*width) should be computed at run-time can be computed at compile-time o So,the location of A[i]can be computed at the run-time by evaluating the formula i*width+c where c is(base-low*width)which is evaluated at compile-time. Intermediate code generator should produce the code to evaluate this formula i*width+c (one multiplication and one addition operation). CS308 Compiler Theory 2
Arrays (cont.) baseA+(i-low)*width can be re-written as i*width + (baseA-low*width) should be computed at run-time can be computed at compile-time • So, the location of A[i] can be computed at the run-time by evaluating the formula i*width+c where c is (baseA-low*width) which is evaluated at compile-time. • Intermediate code generator should produce the code to evaluate this formula i*width+c (one multiplication and one addition operation). CS308 Compiler Theory 12
Two-Dimensional Arrays (cont.) .The location of A[iji]is base+((i-low)*n2+i2-low2)*width base is the location of the array A. low is the index of the first row lowz is the index of the first column nz is the number of elements in each row width is the width of each array element Again,this formula can be re-written as ((i1*n2)+i)*width +(baseA-((low1*n)+low2)*width) should be computed at run-time can be computed at compile-time CS308 Compiler Theory 13
Two-Dimensional Arrays (cont.) • The location of A[i1,i 2] is base A+ ((i1-low1)*n 2+i 2-low 2)*width base A is the location of the array A is the location of the array A. low 1 is the index of the first row low 2 is the index of the first column n 2 is the number of elements in each row width is the width of each arra y element • Again, this formula can be re-written as ((i * )+i )* idth + (b ((l * )+l )* idth) 1* n 2)+i 2)* width + (base A -((low1* n1)+low 2)* width) should be computed at run time can be computed at compile time CS308 Compiler Theory 13 should be computed at run -time can be computed at compile -time
Multi-Dimensional Arrays .In general,the location of A[ii2,...i]is ((..((in2)+i)...)*nk+ik)*width (baseA- ((...((low *n)+low)...)*nk+low)*width) So,the intermediate code generator should produce the codes to evaluate the following formula (to find the location of A[i,i): (.(i*n2十i2).…)*nk+ik)*width+c To evaluate the ((...((in2)+i2)...)*nk+ik portion of this formula,we can use the recurrence equation: e1=l1 em=em-1 nm+im CS308 Compiler Theory
Multi-Dimensional Arrays • In general, the location of A[i1,i 2,...,i k] is (( ... ((i1*n 2)+i 2) ...)*n k+i k)*width + (base A - ((...((low1*n1)+low 2)...)*n k+low k)*width) • So, the intermediate code generator should produce the codes to evaluate the following formula (to find the location of A[i evaluate the following formula (to find the location of A[i i i ]) : 1,i 2,..., i k]) : (( ... ((i1*n 2)+i 2) ...)*n k+i k)*width + c • To evaluate the (( ... ((i1*n 2)+i 2) ...)*n k+i k portion of this formula, we can use the recurrence equation: e1 = i1 CS308 Compiler Theory 14 e m = em-1 * n m + i m
Translation Scheme for Arrays S→L=E{ if (L.offset is null)emit('mov'E.place ,'L.place) else emit(mov'E.place,'L.place L.offset ]) E->E+E2 {E.place=newtemp(); emit(‘add'E1place‘,'E2:place‘,'E.place)} E→(E) E.place =E1place; E→L if (L.offset is null)E.place =L.place) else E.place newtempO; emit(mov'L.place [L.offset]E.place)} CS308 Compiler Theory
Translation Scheme for Arrays S → L := E { if (L.offset is null) emit(‘mov’ E.place ‘,,’ L.place) else emit(‘mov’ E.place ‘,,’ L.place ‘[‘ L.offset ‘]’) } E → E1 + E 2 E → E { E.place = newtemp(); 1 E 2 { E.place newtemp(); emit(‘add’ E1.place ‘,’ E 2.place ‘,’ E.place) } E → ( E ) {E l E l } 1 ) { E.p lace = E1.p lace; } E → L { if (L.offset is null) E.place = L.place) else { E.place = newtemp(); emit(‘mov’ L.place ‘[‘ L.offset ‘]’ ‘,,’ E.place) } } CS308 Compiler Theory 15