Slide 1Slide 2Logical OperationsAND OperationsOR OperationsNOT OperationsShift OperationsUses for Shift InstructionsUses for Shift InstructionsUse for Shift InstructionsUse for Shift InstructionsMultiplication by ConstantsDivision: Sign of the remainderProceduresC functionsFunction Call BookkeepingInstruction Support for FunctionsInstruction Support for FunctionsInstruction Support for FunctionsInstruction Support for FunctionsInstruction Support for FunctionsNested ProceduresNested ProceduresC memory Allocation reviewUsing the StackUsing the StackProcedure CallsMIPS RegistersOther RegistersRegister ConventionSaved Register ConventionVolatile Register ConventionRegister ConventionsBasic Structure of a FunctionReviewECE 15B Computer OrganizationSpring 2010Dmitri StrukovLecture 7: Procedures IPartially adapted from Computer Organization and Design, 4th edition, Patterson and Hennessy, and classes taught by and classes taught by Patterson at Berkeley and Ryan Kastner at UCSBReview of the last lecture: Logic and Shift Instructionsand multiplication/divisionECE 15B Spring 2010Logical Operations•Instructions for bitwise manipulationOperation C Java MIPSShift left << <<sllShift right >> >>>srlBitwise AND & &and, andiBitwise OR | |or, oriBitwise NOT ~ ~norUseful for extracting and inserting groups of bits in a wordECE 15B Spring 2010AND Operations•Useful to mask bits in a word–Select some bits, clear others to 0and $t0, $t1, $t20000 0000 0000 0000 0000 1101 1100 00000000 0000 0000 0000 0011 1100 0000 0000$t2$t10000 0000 0000 0000 0000 1100 0000 0000$t0ECE 15B Spring 2010OR Operations•Useful to include bits in a word–Set some bits to 1, leave others unchangedor $t0, $t1, $t20000 0000 0000 0000 0000 1101 1100 00000000 0000 0000 0000 0011 1100 0000 0000$t2$t10000 0000 0000 0000 0011 1101 1100 0000$t0ECE 15B Spring 2010NOT Operations•Useful to invert bits in a word–Change 0 to 1, and 1 to 0•MIPS has NOR 3-operand instruction–a NOR b == NOT ( a OR b )nor $t0, $t1, $zero0000 0000 0000 0000 0011 1100 0000 0000$t11111 1111 1111 1111 1100 0011 1111 1111$t0Register 0: always read as zeroECE 15B Spring 2010Shift Operations•shamt: how many positions to shift •Shift left logical (SLL)–Shift left and fill with 0 bits–sll by i bits multiplies by 2i•Shift right logical (SRL)–Shift right and fill with 0 bits–srl by i bits divides by 2i (unsigned only)•Shift right arithmetic (SRA)–Shift right and fill emptied bits by sign extending•Note that shamt (immediate value) is only 5 bitsop rs rt rd shamt funct6 bits 6 bits5 bits 5 bits 5 bits 5 bitsECE 15B Spring 2010Uses for Shift Instructions•Very convenient operation to extract group of bits (e.g. one byte) within a word (e.g. think of operations on 8-bit pixels or 8-bit characters)•For example, suppose we want to get bits 8 to 15 from $t0. The code below will do the jobsll $t0, $t0, 16srl $t0, $t0, 24 ECE 15B Spring 2010Uses for Shift Instructions•Since shifting is faster than multiplication, a good compiler (or a good programmer for that matter) usually notices when C code multiplies by a power of 2 and compiles it to a shift instructionFor example:a = a*8; (in C) would compile to: sll $s0, $s0, 3 (in MIPS)ECE 15B Spring 2010Use for Shift InstructionsLet’s consider fast version for 4 bit unsigned number multiplication. Let’s have multiplicand in $a0 and multiplier in $a1 and let’s assume that we don’t have to preserve the values of $a0 and $a1. addi $t1, $0, 4 # initialize loop counter srl $a0, $a0, 4 # align multiplicand with high 4-bit portion of the product loop: andi $t0, $a1, 1 # get the current LSB of the product (i.e. that of the multiplier) beq $t0, $0, skipadd # skip addition of the multiplicand to the product if current last bit of the product is 0 add $a1, $a1, $a0 # add multiplicand to the productskipadd:addi $t1, $t1, -1 # decrement loop counter srl $a1, $a1, 1 # shift to the right product by one bit bne $t1, $0, loop; # repeat loop 4 timesThe code will have 8 bit product in register $a1 ECE 15B Spring 2010Use for Shift InstructionsThe previous code have branch instruction in the loop. It is desirable to avoid branching whenever possible so that using shift and logic (masking) instruction we can have instead: addi $t1, $0, 4 # initialize loop counter srl $a0, $a0, 4 # align multiplicand with high 4-bit portion of the product loop: sll $t0, $a1, 31 # move the current LSB of the product to the MSB srla $t0, $t0, 24 # perform sign extension which will create mask with LSB value of the product and $t0, $t0, $a0 # if LSB =1 then $t0 = $a0, if LSB = 0 then $t0 = 0 add $a1, $a1, $t0 # add $t0 to the productskipadd:addi $t1, $t1, -1 # decrement loop counter srl $a1, $a1, 1 # shift to the right product by one bit bne $t1, $0, loop; # repeat loop 4 times ECE 15B Spring 2010Multiplication by ConstantsMultiplication by the constant could be implemented more efficientlyFor example: b = a*7 is the same as b = a*8 – a which can be implemented as one shift and one sub operation which could be faster than performing mult operation or if mult is not available faster than sequential multiplication algorithm Compiler will typically do the optimization for youECE 15B Spring 2010Division: Sign of the remainder divident = quotient*divisor + reminderfor division of signed numbers the sign of the reminder is always the same as the sign of the dividentcorrect: -7 = -3 * 2 – 1incorrect: -7 = -4 * 2 + 1ECE 15B Spring 2010ProceduresECE 15B Spring 2010C functionsmain() {int a,b,c;...c = sum(a,b); ... }/* really dumb mult function */... sum(a,b);... /* a,b:$s0,$s1 */}int sum(int x, int y) {return x+y;}What information mustcompiler/programmer keep track of?What instructions can accomplish this?ECE 15B Spring 2010Function Call Bookkeeping•Registers play a major role in keeping track of information for function calls.•Register conventions:–Return address $ra–Arguments $a0, $a1, $a2, $a3–Return value $v0, $v1–Local variables $s0, $s1, … , $s7•The stack is also used; more later.ECE 15B Spring 2010Instruction Support for Functions ... sum(a,b);... /* a,b:$s0,$s1 */}int sum(int x, int y) {return x+y;} address (shown in