CMSC 611: AdvancedCMSC 611: AdvancedComputer ArchitectureComputer ArchitectureCompilersCompilersSome material adapted from Mohamed Younis, UMBC CMSC 611 Spr 2003 course slidesSome material adapted from Hennessy & Patterson / © 2003 Elsevier ScienceTypical CompilationTypical CompilationLet's assume that A is an array of word-length integers and that the compiler hasassociated the variables g, h and i with the registers $s1, $s2 and $s4. Let's assumethat the starting address, or base address, of the array is in $s3. The following is apossible compilation of a segment of a C program to MIPS assembly instructions:g = h + A[i];First convert word-index to byte-index:add $t1, $s4, $s4 # Temp reg $t1 = 2 * iadd $t1, $t1, $t1 # Temp reg $t1 = 4 * iTo get the address of A[i], we need to add $t1 to the base of A in $s3:add $t1, $t1, $s3 # $t1 = address of A[i] (4 * i + $s3)Now we can use that address to load A[i] into a temporary register:lw $t0, 0($t1) # Temporary register $t0 gets A[i]Finally add A[i] to h and place the sum in g:add $s1, $s2, $t0 # g = h + A[i]Compiling Array IndexingCompiling Array IndexingAssuming the five variables f, g, h, i,and j correspond to the five registers$s0 through $s4, what is thecompiled MIPS code for thefollowing C if statement:if (i == j) f = g + h; else f = g - h;i == j?f = g– hf = g + hElse:Exit:i=j i! jbne $s3, $s4, Else # go to Else if i ! jadd $s0, $s1, $s2 # f = g + h (skipped if i ! j)j ExitElse: sub $s0, $s1, $s2 # f = g - h (skipped if i = j)Exit:MIPS:Compiling if-then-elseCompiling if-then-elseAssume that i, j and k correspond to $s3 through $s5, and the base of thearray “save” is in $s6. what is the compiled MIPS code for the following Csegment:while (save[i] == k) i = i + j;The first step is to load save[i] into a temporary registerLoop: add $t1, $s3, $s3 # Temp reg $t1 = 2 * iadd $t1, $t1, $t1 # Temp reg $t1 = 4 * iadd $t1, $t1, $s6 # $t1 = address of save[i]lw $t0, 0($t1) # Temp reg $t0 = save[i]The next instruction performs the loop test, exiting if save[i] ! kbne $t0, $s5, Exit # go to Exit if save[i] ! kFinally reaching the loop endj Loop # go back to the beginning of loopExit:MIPS:The next instruction add j to i: add $s3, $s3, $s4 # i = i + jCompiling a while LoopCompiling a while LoopMajor Types of OptimizationMajor Types of OptimizationOptimization NameExplanationFrequencyHigh –levelAt or near source level; machine indep.Procedure integrationReplace procedure call by procedure bodyN.MLocalWithin straight line codeCommon sub- expressioneliminationReplace two instances of the same computation bysingle copy18%Constant propagationReplace all instances of a variable that is assigned aconstant with the constant22%Stack height reductionRearrange expression tree to minimize resourcesneeded for expression evaluationN.MGlobalAcross a branchGlobal common subexpression eliminationSame as local, but this version crosses branches13%Copy propagationReplace all instances of a variable A that hasbeen assigned X (i.e., A = X) with X11%Code motionRemove code from a loop that computes same valueeach iteration of the loop16%Induction variableeliminationSimplify/eliminate array –addressing calculationswithin loops2%Machine-dependantDepends on machine knowledgeStrength reductionMany examples, such as replace multiply by aconstant with adds and shiftsN.MPipeline SchedulingReorder instructions to improve pipeline performanceN.M.Measurements taken on MIPSProgram and Compiler Optimization LevelLevel 0: non-optimized codeLevel 1: local optimizationLevel 2: global optimization, s/w pipeliningLevel 3: adds procedure integrationEffect of OptimizationEffect of OptimizationMultimedia InstructionsMultimedia Instructions• Small vector processing targeting multimedia– Intel’s MMX, PowerPC AltiVec, Sparc VIS, MIPS MDMX– N 1/Nth-word vectors packed into one register– Same operations performed on all N vectors• Plus– Little additional ALU hardware– Utilize under-used hardware resources• Minus– Extra pack & unpack if data isn’t already arranged perfectly– Limited vector sizes, difficult to compile for general code• Result– Mostly used in hand-coded libraries• Compare to general vector processing– Hide memory latency in vector access– Strided processing, gather/scatter addressingEffect of Compilers on ISAEffect of Compilers on ISA• Promote regularity– Limit # register formats and variability of operands– Orthogonality in operations, registers & addressing• Provide primitives, not solutions– Common features over specific language features– Special-purpose instructions often unusable (except throughhand-assembly-coded libraries)• Simplify trade-offs among alternatives– Simplify the analysis of special features such as cache andpipeline– Allow simultaneous activities to promote optimizationAssemblerAssembly language programCompilerC programLinkerExecutable: Machine lang uage programLoaderMemoryObject: Machine language module Object: Library routine (machine language )- Place code & data modules symbolically in memory-Determine the address of data & instruction labels-Patch both internal & external ref.Object files for Unix typically contains:Header: size & position of componentsText segment: machine codeData segment: static and dynamic variablesRelocation info: identify absolute memory ref.Symbol table: name & location of labels, procedures and variablesDebugging info: mapping source to object code, break points, etc.LinkerStarting a ProgramStarting a ProgramAssuming the value in $gp is 10008000hexExecutable file headerText size300hexData size50hexText segmentAddressInstruction0040 0000hexlw $a0, 8000hex($gp)0040 0004hexjal 40 0100hex……0040 0100hexlw $a1, 8020hex($gp)0040 0104hexjal 40 0000hex……Data segmentAddress1000 0000hex(X)……1000 0020hex(Y)……Object file headerNameProcedure AText size100hexData size20hexText segmentAddressInstruction0lw $a0, 0($gp)4jal 0……Data segment0(X)….…Relocation InfoAddressInstruction typeDependency0lwX4jalBSymbol tableLabelAddressX-B-Linking Object FilesLinking Object FilesObject file headerNameProcedure BText size200hexData size30hexText segmentAddressInstruction0lw $a0, 0($gp)4jal 0……Data segment0(Y)….…Relocation InfoAddressInstruction typeDependency0lwY4jalASymbol tableLabelAddressY-A-Loading Executable ProgramLoading Executable Program$sp$gp0040 0000hex01000 0000hexTextStatic dataDynamic dataStack7fff