9/16/09 1 From C to MIPS David E. Culler CS61CL Sept 16, 2009 Lecture 4 UCB CS61CL F09 Lec 4!Review • Arrays, Structs, and Pointers allow you define sophisticated data structures – Compiler protects you by enforcing type system – Avoid dropping beneath the abstraction and munging the bits • All map into untyped storage, ints, and addresses • Executing program has a specific structure – Code, Static Data, Stack, and Heap – Mapped into address space – “Holes” allow stack and heap to grow – Compiler defines what the bits mean by enforcing type » Chooses which operations to perform • Poor coding practices, bugs, and architecture limitations lead to vulnerabilities 9/16/09 UCB CS61CL F09 Lec 4!2Today 9/16/09 UCB CS61CL F09 Lec 4!3 int main() {! …!}!.data!A:.word 5!…!.text!main: lw $a0, x!jal decr!move $a0,$v0!Elements of the Language • Basic Data Types: char, int, float double • Type Constructors: array, struct, pointer • Variables • Expressions • Sequence of statements • Conditionals • Iteration • Functions 9/16/09 UCB CS61CL F09 Lec 4!4What does the machine do? • Instruction Fetch • Decode • Operand Fetch • Execute • Result Store • Next Instruction 9/16/09 UCB CS61CL F09 Lec 4!5 Instruction Execution CycleInstruction Cycle 9/16/09 UCB CS61CL F09 Lec 4!6 °°° 000..0: FFF..F: n: 0B20 0B20: Instruction Fetch Execute PC 32 2 3 1 “add $1,$2,$3” 40 61 101 Operand Result Next Decode + 0B24 main:Instruction Cycle - again 9/16/09 UCB CS61CL F09 Lec 4!7 °°° 000..0: FFF..F: n: 0B24 0B20: Instruction Fetch Execute PC 35 2 1 00 “lw $2,$1,00” 40 61 93 Operand Result Next Decode + 0B28 main: 93 101What does the machine do? • Instruction Fetch • Decode • Operand Fetch • Execute • Result Store • Next Instruction 9/16/09 UCB CS61CL F09 Lec 4!8 Instruction Execution Cycle Register Transfers inst <= mem[ PC ] op, rd, rs, rt <= inst A <= reg[ rs ] B <= reg[ rt ] R <= A + B reg[ rd ] := A + B PC := PC + 4MIPS Assembly Language (MAL) 9/16/09 UCB CS61CL F09 Lec 4!9 !.data!A: !.word 5!!.word 6!!…!!.text!main: !la $t0, A!!lw $a0, 4($t0)!!jal decr!!move $a0,$v0!!…!decr: !addi $v0, $a0, -1!!jr $ra!segments label opcode operands registers literals valuesMIPS Instruction Format 9/16/09 UCB CS61CL F09 Lec 4!10 op 6 rs 5 rt 5 rd 5 shamt 5 funct 6 immediate 16 add $1, $2, $3 # r1 := r2 + r3 lw $3, 24($2) # r3 := mem[ r2 + 24 ]MIPS register conventions 9/16/09 UCB CS61CL F09 Lec 4!11 Name !Number !Use !Callee must preserve? !!$zero !$0 !constant 0 !N/A !!$at !$1 !assembler temporary !No !!$v0–$v1 !$2–$3 !returns values !No !!$a0–$a3 !$4–$7 !function arguments !No !!$t0–$t7 !$8–$15 !temporaries !No !!$s0–$s7 !$16–$23 !saved temporaries !Yes !!$t8–$t9 !$24–$25 !temporaries !No !!$k0–$k1 !$26–$27 !reserved for OS kernel !No !!$gp !$28 !global pointer !Yes !!$sp !$29 !stack pointer !Yes !!$fp !$30 !frame pointer !Yes !!$ra !$31 !return address !N/A !!Administration • Calendar with links on the home page • Readers will be in lab 1 hour per week • HW3R – Resubmit as hw3r permitted till 11:59 pm Saturday – as you learn, don’t be afraid to make a fresh start • HW4 out – all future HW will be W-W – less work than hw3, little reliance on Th/F Lab, start right away – Continues C concepts plus basic MAL • Project 1 posted • Mid Term 1 shifted to Wed 10/7 in class time – alternative Monday 10/5 @ 4 pm 9/16/09 UCB CS61CL F09 Lec 4!12Elements of the Language • Basic Data Types: char, int, float double • Type Constructors: array, struct, pointer • Variables • Expressions • Sequence of statements • Conditionals • Iteration • Functions 9/16/09 UCB CS61CL F09 Lec 4!13Expressions 9/16/09 UCB CS61CL F09 Lec 4!14 y1 = (-b + sqrt(b*b - 4*a*c) / (2*a);!y2 = (-b - sqrt(b*b - 4*a*c) / (2*a);!t1 = -b;!t2 = b*b;!t3 = 4*a;!t4 = t3*c;!t5 = t2 – t4;!t6 = sqrt(t5);!t7 = t1 + t6;!t8 = 2*a;!y1 = t7 / t8;!t9 = t1 – t6;!y2 = t9 / t8;!t1 = -b;!t2 = b*b;!t3 = 4*a;!t3 = t3*c;!a0 = t2 – t3;!v0 = sqrt(a0);!t7 = t1 + v0;!t8 = 2*a;!y1 = t7 / t8;!t9 = t1 – v0;!y2 = t9 / t8;!lw !t0, b!sub !t1, 0, t0!mult !t2, t0, t0!lw !t0, a!mult !t3, t0, 4!lw !t4, c!mult !t3, t3, t4!sub !a0, t2, t3!jal !sqrt!add !t7, t1, v0!mult !t8, t0, 2!div !t0, t7, t8;!sw !t0, y1!sub !t9, t1, v0!div !t0, t9, t8!sw !t0, y2!t1 = -b; !=> lw !t0, b! !=> sub !t1, 0, t0!t2 = b*b; !=> mult !t2, t0, t0!t3 = 4*a; !=> lw !t0, a! !=> mult !t3, t0, 4!t3 = t3*c; !=> lw !t4, c! !=> mult !t3, t3, t4!a0 = t2 – t3; !=> sub !a0, t2, t3!v0 = sqrt(a0); !=> jal !sqrt!t7 = t1 + v0; !=> add !t7, t1, v0!t8 = 2*a; !=> mult !t8, t0, 2!y1 = t7 / t8; !=> div !t0, t7, t8;! !=> sw !t0, y1!t9 = t1 – v0; !=> sub !t9, t1, v0!y2 = t9 / t8; !=> div !t0, t9, t8! !=> sw !t0, y2!9/16/09 UCB CS61CL F09 Lec 4!15 y1 = (-b + sqrt(b*b - 4*a*c) / (2*a);!y2 = (-b - sqrt(b*b - 4*a*c) / (2*a);!Variables • Can be held in Registers – Temporary variables – Internal to expression evaluation – Local to a function and no references to them – Arguments and return values • Or in memory – Global or static variables (externals) – Local variables on the stack – Values in the heap • Memory is usually accessed indirectly through a (special) register – stack pointer – global pointer – heap pointer 9/16/09 UCB CS61CL F09 Lec 4!16Variable examples 9/16/09 UCB CS61CL F09 Lec 4!17 int ext;!int foo (int n) {!!int loc;!!int A [8];!!struct {int x;! int y;} point;!!int dyn[] = malloc(10*sizeof(int));!!…!!return (loc+n);!}!Conditionals 9/16/09 UCB CS61CL F09 Lec 4!18 if (condition) {true-clause }!else {false_clause }!if (condition) goto Ltrue;!false_clause!goto Ldone;!Ltrue:!true_clause!Ldone:!BR_condition Ltrue!code for false_clause!jmp Ldone!Ltrue:!code for true_clause!Ldone:!Human C code Machine-level C code Machine-level Assembly codeJumps and Branches • Jumps – unconditional control transfers – direct or indirect – “calls” are a special Jump-and-link » saves the return address – computes target address and loads PC • Branches – conditional control transfers – tests a condition and branches if true – otherwise falls through sequentially – MIPS provides simple conditions on
View Full Document
Unlocking...