Machine-Level Programming IV:Structured DataSept. 19, 2002Machine-Level Programming IV:Structured DataSept. 19, 2002TopicsTopicsn Arraysn Structsn Unionsclass08.ppt15-213“The course that gives CMU its Zip!”– 2 –15-213, F’02Basic Data TypesBasic Data TypesIntegralIntegraln Stored & operated on in general registersn Signed vs. unsigned depends on instructions usedIntel GAS Bytes Cbyte b 1 [unsigned] charword w 2 [unsigned] shortdouble word l 4 [unsigned] intFloating PointFloating Pointn Stored & operated on in floating point registersIntel GAS Bytes CSingle s 4 floatDouble l 8 doubleExtended t 10/12 long double– 3 –15-213, F’02Array AllocationArray AllocationBasic PrincipleBasic PrincipleT A[L];n Array of data type T and length Ln Contiguously allocated region of L * sizeof(T) byteschar string[12];x x + 12int val[5];xx + 4 x + 8 x + 12 x + 16 x + 20double a[4];x + 32x + 24xx + 8 x + 16char *p[3];xx + 4 x + 8– 4 –15-213, F’02Array AccessArray AccessBasic PrincipleBasic PrincipleT A[L];n Array of data type T and length Ln Identifier A can be used as a pointer to array element 0ReferenceReferenceTypeTypeValueValueval[4] int 3val int * xval+1 int * x + 4&val[2] int * x + 8val[5] int ??*(val+1) int 5val + i int * x + 4 i1 5 2 1 3int val[5];xx + 4x + 8 x + 12 x + 16 x + 20– 5 –15-213, F’02Array ExampleArray ExampleNotesNotesn Declaration “zip_dig cmu” equivalent to “int cmu[5]”n Example arrays were allocated in successive 20 byte blocksl Not guaranteed to happen in generaltypedef int zip_dig[5];zip_dig cmu = { 1, 5, 2, 1, 3 };zip_dig mit = { 0, 2, 1, 3, 9 };zip_dig ucb = { 9, 4, 7, 2, 0 };zip_dig cmu;1 5 2 1 316 20 24 28 32 36zip_dig mit;0 2 1 3 936 40 44 48 52 56zip_dig ucb;9 4 7 2 056 60 64 68 72 76– 6 –15-213, F’02Array Accessing ExampleArray Accessing ExampleMemory Reference CodeMemory Reference Codeint get_digit (zip_dig z, int dig){ return z[dig];} # %edx = z # %eax = digmovl (%edx,%eax,4),%eax # z[dig]ComputationComputationn Register %edx contains startingaddress of arrayn Register %eax contains arrayindexn Desired digit at 4*%eax + %edxn Use memory reference(%edx,%eax,4)– 7 –15-213, F’02Referencing ExamplesReferencing ExamplesCode Does Not Do Any Bounds Checking!Code Does Not Do Any Bounds Checking!ReferenceReferenceAddressAddressValueValueGuaranteed?Guaranteed?mit[3] 36 + 4* 3 = 48 3mit[5] 36 + 4* 5 = 56 9mit[-1] 36 + 4*-1 = 32 3cmu[15] 16 + 4*15 = 76 ?? n Out of range behavior implementation-dependentlNo guaranteed relative allocation of different arrayszip_dig cmu;1 5 2 1 316 20 24 28 32 36zip_dig mit;0 2 1 3 936 40 44 48 52 56zip_dig ucb;9 4 7 2 056 60 64 68 72 76YesYesNoNoNoNoNoNo– 8 –15-213, F’02int zd2int(zip_dig z){ int i; int zi = 0; for (i = 0; i < 5; i++) { zi = 10 * zi + z[i]; } return zi;}Array Loop ExampleArray Loop ExampleOriginal SourceOriginal Sourceint zd2int(zip_dig z){ int zi = 0; int *zend = z + 4; do { zi = 10 * zi + *z; z++; } while(z <= zend); return zi;}Transformed VersionTransformed Versionn As generated by GCCn Eliminate loop variable in Convert array code topointer coden Express in do-while formlNo need to test at entrance– 9 –15-213, F’02# %ecx = zxorl %eax,%eax # zi = 0leal 16(%ecx),%ebx # zend = z+4.L59:leal (%eax,%eax,4),%edx # 5*zimovl (%ecx),%eax # *zaddl $4,%ecx # z++leal (%eax,%edx,2),%eax # zi = *z + 2*(5*zi)cmpl %ebx,%ecx # z : zendjle .L59 # if <= goto loopArray Loop ImplementationArray Loop ImplementationRegistersRegisters%ecx z%eax zi%ebx zendComputationsComputationsn 10*zi + *z implemented as*z + 2*(zi+4*zi)n z++ increments by 4int zd2int(zip_dig z){ int zi = 0; int *zend = z + 4; do { zi = 10 * zi + *z; z++; } while(z <= zend); return zi;}# %ecx = zxorl %eax,%eax # zi = 0leal 16(%ecx),%ebx # zend = z+4.L59:leal (%eax,%eax,4),%edx # 5*zimovl (%ecx),%eax # *zaddl $4,%ecx # z++leal (%eax,%edx,2),%eax # zi = *z + 2*(5*zi)cmpl %ebx,%ecx # z : zendjle .L59 # if <= goto loopint zd2int(zip_dig z){ int zi = 0; int *zend = z + 4; do { zi = 10 * zi + *z; z++; } while(z <= zend); return zi;}# %ecx = zxorl %eax,%eax # zi = 0leal 16(%ecx),%ebx # zend = z+4.L59:leal (%eax,%eax,4),%edx # 5*zimovl (%ecx),%eax # *zaddl $4,%ecx # z++leal (%eax,%edx,2),%eax # zi = *z + 2*(5*zi)cmpl %ebx,%ecx # z : zendjle .L59 # if <= goto loopint zd2int(zip_dig z){ int zi = 0; int *zend = z + 4; do { zi = 10 * zi + *z; z++; } while(z <= zend); return zi;}# %ecx = zxorl %eax,%eax # zi = 0leal 16(%ecx),%ebx # zend = z+4.L59:leal (%eax,%eax,4),%edx # 5*zimovl (%ecx),%eax # *zaddl $4,%ecx # z++leal (%eax,%edx,2),%eax # zi = *z + 2*(5*zi)cmpl %ebx,%ecx # z : zendjle .L59 # if <= goto loopint zd2int(zip_dig z){ int zi = 0; int *zend = z + 4; do { zi = 10 * zi + *z; z++; } while(z <= zend); return zi;}# %ecx = zxorl %eax,%eax # zi = 0leal 16(%ecx),%ebx # zend = z+4.L59:leal (%eax,%eax,4),%edx # 5*zimovl (%ecx),%eax # *zaddl $4,%ecx # z++leal (%eax,%edx,2),%eax # zi = *z + 2*(5*zi)cmpl %ebx,%ecx # z : zendjle .L59 # if <= goto loopint zd2int(zip_dig z){ int zi = 0; int *zend = z + 4; do { zi = 10 * zi + *z; z++; } while(z <= zend); return zi;}– 10 –15-213, F’02Nested Array ExampleNested Array Examplen Declaration “zip_dig pgh[4]” equivalent to “int pgh[4][5]”l Variable pgh denotes array of 4 elements» Allocated contiguouslyl Each element is an array of 5 int’s» Allocated contiguouslyn “Row-Major” ordering of all elements guaranteed#define PCOUNT 4zip_dig pgh[PCOUNT] = {{1, 5, 2, 0, 6}, {1, 5, 2, 1, 3 }, {1, 5, 2, 1, 7 }, {1, 5, 2, 2, 1 }};zip_digpgh[4];76 96 116 136 1561 5 2 0 6 1 5 2 1 3 1 5 2 1 7 1 5 2 2 1– 11 –15-213, F’02Nested Array AllocationNested Array AllocationDeclarationDeclarationT A[R][C];n Array of data type Tn R rows, C columnsn Type T element requires KbytesArray SizeArray Sizen R * C * K bytesArrangementArrangementn Row-Major OrderingA[0][0] A[0][C-1]A[R-1][0]¥Ê¥Ê¥¥Ê¥Ê¥ A[R-1][C-1]¥¥¥¥¥¥int A[R][C];A[0][0]A[0][C-1]¥Ê¥Ê¥A[1][0]A[1][C-1]¥Ê¥Ê¥A[R-1][0]A[R-1][C-1]¥Ê¥Ê¥¥ Ê¥Ê ¥4*R*C Bytes– 12 –15-213, F’02• • •Nested Array Row AccessNested Array Row AccessRow VectorsRow Vectorsn A[i] is array of C elementsn Each element of type Tn Starting address A + i * C * KA[i][0]A[i][C-1]• • •A[i]A[R-1][0]A[R-1][C-1]• • •A[R-1]• • •AA[0][0]A[0][C-1]• • •A[0]int A[R][C];A+i*C*4 A+(R-1)*C*4– 13 –15-213, F’02Nested Array Row Access CodeNested
View Full Document