Machine-Level Programming IV: Data Feb. 5, 2008Basic Data TypesArray AllocationArray AccessArray ExampleArray Accessing ExampleReferencing ExamplesArray Loop ExampleArray Loop Implementation (IA32)Nested Array ExampleViewing as Multidimensional ArrayNested Array Row AccessNested Array Row Access CodeNested Array Element AccessNested Array Element Access CodeStrange Referencing ExamplesMulti-Level Array ExampleElement Access in Multi-Level ArrayArray Element AccessesSlide 20Using Nested ArraysDynamic Nested ArraysDynamic Array MultiplicationOptimizing Dynamic Array Mult.StructuresGenerating Pointer to Struct. MemberStructure Referencing (Cont.)AlignmentSpecific Cases of Alignment (IA32)Specific Cases of Alignment (x86-64)Satisfying Alignment with StructuresDifferent Alignment ConventionsOverall Alignment RequirementOrdering Elements Within StructureArrays of StructuresAccessing Element within ArraySatisfying Alignment within StructureUnion AllocationUsing Union to Access Bit PatternsByte Ordering RevisitedByte Ordering ExampleByte Ordering Example (Cont).Byte Ordering on IA32Byte Ordering on SunByte Ordering on x86-64SummaryMachine-Level Programming IV:DataFeb. 5, 2008Machine-Level Programming IV:DataFeb. 5, 2008Structured DataStructured DataArraysStructsUnionsclass07.ppt15-213“The course that gives CMU its Zip!”– 2 –15-213, S’08Basic Data TypesBasic Data TypesIntegralIntegralStored & operated on in general registersSigned vs. unsigned depends on instructions usedIntel GAS Bytes Cbyte b 1 [unsigned] charword w 2 [unsigned] shortdouble word l 4 [unsigned] intquad word q 8 [unsigned] long int (x86-64)Floating PointFloating PointStored & operated on in floating point registersIntel GAS Bytes CSingle s 4 floatDouble l 8 doubleExtended t 10/12/16 long double– 3 –15-213, S’08Array AllocationArray AllocationBasic PrincipleBasic PrincipleT A[L];Array of data type T and length LContiguously 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 + 8 x + 16x + 24xx + 4 x + 8 x + 12IA32x86-64– 4 –15-213, S’08Array AccessArray AccessBasic PrincipleBasic PrincipleT A[L];Array of data type T and length LIdentifier A can be used as a pointer to array element 0Type T*ReferenceReferenceTypeTypeValueValueval[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 + 4 x + 8 x + 12 x + 16 x + 20– 5 –15-213, S’08Array ExampleArray ExampleNotesNotesDeclaration “zip_dig cmu” equivalent to “int cmu[5]”Example arrays were allocated in successive 20 byte blocksNot 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, S’08Array Accessing ExampleArray Accessing ExampleIA32 Memory Reference CodeIA32 Memory Reference Codeint get_digit (zip_dig z, int dig){ return z[dig];} # %edx = z # %eax = digmovl (%edx,%eax,4),%eax # z[dig]ComputationComputationRegister %edx contains starting address of arrayRegister %eax contains array indexDesired digit at 4*%eax + %edxUse memory reference (%edx,%eax,4)– 7 –15-213, S’08Referencing 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 ?? Out of range behavior implementation-dependentNo guaranteed relative allocation of different arrays 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 76YesYesNoNoNoNoNoNo– 8 –15-213, S’08int 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 VersionAs generated by GCCEliminate loop variable iConvert array code to pointer codeExpress in do-while formNo need to test at entrance– 9 –15-213, S’08# %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 Implementation (IA32)Array Loop Implementation (IA32)RegistersRegisters%ecx z%eax zi%ebx zendComputationsComputations 10*zi + *z implemented as *z + 2*(zi+4*zi) 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, S’08Nested
View Full Document