Principles of Computers

Size: px

Start display at page:

Download "Principles of Computers"

某衡马佳
5 years ago
Views:

1 MIPS 汇编语言程序设计 LD(R31,x,R0) BNE(R0,skip,R31) LD(R31,y,R1) ADDC(R1,1,R1) ST(R1,y,R31) skip:...$%$^$&&$&$ if(x==0) y=y+1;

2 1 机器语言汇编程序设计思路汇编 3 编译器 4 典型程序结构及汇编语言设计

3 读写头回忆一下 : 我们已经有了 UTM 的思想图灵机只要根据每一时刻读写头读到的一个方格的信息和当前的内部状态对程序进行查表, 就可以确定下一时刻的内部状态和输出动作了具体的程序是一个列表, 也叫做规则表无限长纸带图灵机模型

4 回忆一下 : 我们已经有了 UTM 的思想 1:T u 查看 Tape2 和 Tape3 来决定图灵机的配置 T k ( 采用第 k 个图灵机 ) 及它的输入 j; 2:T u 查看第一个磁带 Tape1 决定 T k 会怎么做 ; 3: 修改磁带 2 和 3 以反映 T k (j) 在计算过程中的动作和内部状态变化 ; 我们的任务是计算所有的可计算的整数函数

(Virtual)M2; 在计算机中通常我们会使用多个不同层次的解释器来实现我们想要的行为, 例如 :

5 解释 :Interpretation Turing 的解释器模型 : 首先是有一个与问题无关的通用机器 UTM; M1 为 M1 编写一个简单的程序使得 M1 完成一个简单的功能 M2; 解释的层次 : M1 和程序 Pgm 一起变成了一个虚拟的 (Virtual)M2; 在计算机中通常我们会使用多个不同层次的解释器来实现我们想要的行为, 例如 : X86(pentium) 上面运行着 Java VM 上面又运行着应用程序比如 ant 数据结构比如走迷宫的蚂蚁

6 编译器编译器的模型 : 给定一个 UTM M1; 寻找一个比较容易写的语言 L2( 比如是为了机器 M2 设计的 ) 并写一段程序 ; 编写一个 Translator 使得这个 Translator 可以将 M 2 的语言转换为 M 1 的语言 Interpretation & Compilation: 两个不同的提高可编程性的方法. 都容许改变我们的编程的模型都可以提供一种与平台 ( 如处理器 ) 无关的编程语言 ; 都是在现代的计算机系统中被广泛采用

7 Interpretation 与 Compilation 这两种强有力的工具也有区别 : Interpretation Compilation 如何对待 x+2 计算 x+2 产生一个可以计算 x+2 的程序什么时候计算在执行过程中在执行之前什么代价 ( 使什么变慢 ) 程序执行时间程序的开发时间结果在什么时候确定运行时编译时我们以后会经常遇到的一个关键问题 : 是在运行时实现还是在编译时实现?

8 MIPS 汇编器 : 语法注释行以 # 开始 ; 标识符由字母下划线 (_) 点 (.) 构成, 但不能以数字开头, 指令操作码是一些保留字, 不能用作标识符 ; 标号放在行首, 后跟冒号 (:), 例如.data # 将子数据项, 存放到数据段中 Item:.word 1,2 # 将 2 个 32 位数值送入地址连续的内存字中.text # 将子串即指令或字送入用户文件段.global main # 必须为全局变量 Main: lw $t0, item MIPS 汇编中的命令见 Page

9 MIPS 汇编器 : 存储器中位置汇编语言源文件 :.s 特殊符号. ( 点 ): 表示当前位置. MIPS 汇编命令标识符 label: label 被赋值为当前位置的地址 Fact = 0x 编译时就确定了汇编程序在地址 0x 开始在 LW,SW, BEQ, BNE 等指令中都有应用 0x x x move $s5, $31 beq $0,$0,fact x x x x C 0x x x x x sw $s0,f($0).text 0x fact: addiu $s0,$0,1 lw loop: mul subu bnez addi jr $31 $s1, n($0) $s0,$s1,$s0 $s1,$s1,1 $s1,loop $31,$s5,4.data 0x n:.word 4 f:.word 0

10 能运行的版本 (1):.text main: addu $s3,$ra,$0 ori $s6,$0,0x1000 sll $s6,$s6,16 addiu $s4,$s6,0x0200 addiu $s5,$s6,0x0204 addiu $s7,$s6,0x0208 #$s4=n, $s5=f #$s7 为 $ra 开辟一个地址空间 beq $0,$0, fact result: sw $s0,0($s5) addu $ra,$s3,$0 jr $ra.text 0x fact: sw $ra,0($s7) addiu $s0,$0,1 lw $s1,0($s4) #$s0=n! loop: mul $s0,$s1,$s0 subu $s1,$s1,1 bnez $s1,loop #f=n! j result.data 0x n:.word 4 f:.word

11 test1.data 0x word 4,0.text main:addu $s7,$ra,$0 ori $s6,$0,0x1000 sll $s6,$s6,16 addiu $s5,$s6,0x04 fact: addiu $s0,$0,1 lw $s1,0($s6) loop: mul $s0,$s1,$s0 subu $s1,$s1,1 bnez $s1,loop sw $s0,0($s5) addu $ra,$0,$s7 jr $ra # 下列语句行是数据代码行 # 定义了两个字型立即数 4 和 0 # 下列语句行是指令代码行 # # #$s6=0x #$s5=0x # # #$s0=n!, n=4 # 能运行的版本 # (2) #f=n!=24 # 退出子程序 # 根据 ra 寄存器中的返回地址返回

12 编程指南 (1) 变量 (2) 分支 (3) 数组 (4) 过程调用单指令计算机 (5) 阅读改进程序

13 编程指南 :(1) 变量变量存储在主存储器内 ( 而不是寄存器内 ) 因为我们通常有很多的变量要存, 不止 32 个为了实现功能, 用 LW 语句将变量加载到寄存器中, 对寄存器进行操作, 然后再把结果 SW 回去对于比较长的操作 (e.g., loops): 让变量在寄存器中保留时间越长越好 LW and SW 只在一块代码开始和结束时使用 saves on instructions also, 事实上 LW and SW 比寄存器操作要慢得多得多! 由于一条指令只能采用两个输入, 所以必须采用临时寄存器计算复杂的问题 e.g., (x+y)+(x-y)

14 jr $ra 编程指南 :(1) 变量.data 0x word 4,0.text main: addu $s7,$ra,$0 ori $s6,$0,0x1000 sll $s6,$s6,16 addiu $s5,$s6,4 fact: addiu $s0,$0,1 lw $s1,0($s6) #s1 get 4 loop: mul $s0,$s1,$s0 subu $s1,$s1,1 bnez $s1,loop sw $s0,0($s5) #s0 hold result addu $ra,$0,$s7 #return result in s

15 编程指南 :(2) 分支在符号汇编语句中, 分支语句的目标位置是用绝对地址方式写的 e.g., beq $0,$0,fact means PC 0x 不过在实现中, 要用相对于 PC 的地址来定义 e.g., beq $0,$0,0x3f means PC 0x text main: addu $s3,$ra,$0 ori $s6,$0,0x1000 sll $s6,$s6,16 addiu $s4,$s6,0x0200 addiu $s5,$s6,0x0204 addiu $s7,$s6,0x0208 beq $0,$0, fact result: sw $s0,0($s5) addu $ra,$s3,$0 jr $ra.text 0x fact: sw $ra,0($s7) addiu $s0,$0,1 lw $s1,0($s4) #$s0=n! loop: mul $s0,$s1,$s0 subu $s1,$s1,1 bnez $s1,loop #f=n! j result.data 0x n:.word 4 f:.word

16 分支语句中的偏移量的使用偏移量 = 从下一条指令对应的 PC 开始到标号位置还有多少条指令 e.g., beq $0,$0,fact 如果位于地址 0x 的话, word displacement=(target - (<PC>+4)) / 4 =(0x x )/4 =0xfc/4=0x3f 偏移量为 0 则表示执行下一条指令不产生任何跳转为什么在代码中用相对的偏移量? relocatable 代码 ( 可重新定位的 ) 分支语句可以在每次被加载到内存不同位置的情况下正常工作

17 分支 : 返回地址与 Jr 记得 : BEQ 和 BNE 默认 $31 寄存器获得的是下一个 next-pc e.g., in beq $0,$0,fact R31 gets 0x c 此即返回地址 returnaddress 这样我们有一天还可以跳回来 ~ 这很重要! e.g., jr $31 我们就回到了 0x c 0x x x x c 0x x x x c 0x x x x x text main: addu $s3,$ra,$0 ori $s6,$0,0x1000 sll $s6,$s6,16 addiu $s4,$s6,0x0200 addiu $s5,$s6,0x0204 addiu $s7,$s6,0x0208 beq $0,$0, fact result: sw $s0,0($s5) addu $ra,$s3,$0 jr $ra.text 0x fact: sw $ra,0($s7) addiu $s0,$0,1 lw $s1,0($s4)#$s0=n! loop: mul $s0,$s1,$s0 subu $s1,$s1,1 bnez $s1,loop #f=n! j result.data 0x n:.word 4 f:.word

18 编程指南 :(2) 分支分支如果和 0 比较, 则直接使用 blez,bgez,bltz,bgtz, bnez e.g., loop example before 更复杂的比较, 采用比较指令 ( 如 slt), 然后再用与 0 比较 Example: else if ( x >= 0 ) y = x; y = -x;

19 编程指南 : 分支 test2.data 0x word -6,0.text main: addu $s7,$ra,$0 ori $s6,$0,0x1000 sll $s6,$s6,16 addiu $s5,$s6,4 lw $s0,0($s6) slt $s2,$0,$s0 beqz $s2,else move $s1,$s0 j done else: sub $s1,$0,$s0 done: sw $s1,0($s5) addu $ra,$0,$s7 jr $ra #x:-6, y:0 # 计算内存中数据存放地址 #$s6=x, $s5=y #0<x, $s2=1 #$s2=0, 跳到 else #$s2=1, 跳到 done 功能 : 求绝对值

20 编程指南 :(3) 数组 array 用.word 来给数组开辟空间在编译时静态地开辟 n*4 bytes, (n 个 32-bit 字 ) n=17? 使用 LW 和 SW 的 $2 和 $4 LW $1, const($2) SW $3, const($4) 将 const 作为数组偏移量将寄存器 $2 和 $4 作为数组中的开始地址 (A[0])

21 # 编程指南 :(3) 数组 array test3.data 0x word 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17.text main: addu $s7,$ra,$0 ori $s5,$0,0x1000 sll $s5,$s5,16 #$s5=a[]=0x , addiu $s6,$s5,0x400 #$s6=b[]=0x addiu $s0,$0,0x11 #Size(A)=Size(B)=0x11 loop: subu $s0,$s0,1 addiu $s1,$0,4 mul $s2,$s1,$s0 addu $s3,$s2,$s5 # 计算 A[] 偏移量, 送到 $s3 lw $s4,0($s3) # 读出 A[] 中的值 addu $s3,$s2,$s6 # 计算 B[] 偏移量, 送到 $s3 sw $s4,0($s3) # 写到 B[] 中去 bnez $s0,loop addu $ra,$0,$s7 # 返回调用程序 jr $ra

22 编程指南 :(3) 数组 array 数组访问 SLLV by k 等价于 MUL by 2 k SRLV by k 等价于 DIV by 2 k 很有用, 因为 MUL 和 DIV 一般都比 SLLV 和 SRLV 慢得多想想怎么实现 MUL 和 DIV~ 对于有符号数用 SRA 高位用符号位填充 ( 在 2 的补码表示情况下 ) 只对无符号数成立 e.g., R1 = -6 = 0b SRLV $R1,$R1,1 0b SRAV $R1,$R1,1 0b =-3 想想为什么这样是对的

23 编程指南 :(3) 数组 array 数组访问 add $s0,$0,$a2 # i = N loop: subu $s0 $s0,1 # i-- done: addiu $s1,$0,4 # $s1=4 mul $s2,$s1,$s0 # dest = i*4 addiu $t0,$0,2 # $t0=2 div $s0,$t0 # $lo=floor(i/2) mflo $t1 # $t1=floor(i/2) mul $t1,$s1,$t1 # $t1=$t1*4 add $t2,$t1,$a0 lw $s4,0($t2) # $s4=a[i/2] add $t3,$s2,$a1 sw $s4,0($t3) # B[i] =$s4 bnez $s0,loop # while(i!=0) loop # 数组长度 N = 0x100 # 存放在 $a2 = 0x100 A 的地址存放在 $a0 中 B 的地址存放在 $a1 中

24 编程指南 :(3) 数组 array 数组访问 Side Note #1: 用移位代替乘法 loop: add $s0,$0,$a2 # i = N subu $s0 $s0,1 # i-- sllv $s2,$s0,2 # dest = i*4 sra $t1,$s0,1 # $t1=floor(i/2) sllv $t1,$t1,2 # $t1=$t1*4 add $t2,$t1,$a0 lw $s4,0($t2) # $s4=a[i/2] add $t3,$s2,$a1 sw $s4,0($t3) # B[i] = $s4 bnez $s0,loop # while(i!=0) loop done: 对无符号数 SLLV by k 等价于 MUL by 2 k SRLV by k 等价于 DIV by 2 k 对于有符号数用 SRA 高位用符号位填充 ( 在 2 的补码表示情况下 )

25 编程指南 :(4) 过程调用用汇编写程序时需要明确说明每一次的调用和返回 Why? 为什么用 C 编写程序时不需要了解子程序被调用的具体细节? 大多数有关过程调用的记录集中在一个叫做过程调用帧的内存块中, 实现 : 以参数形式保存调用值被调用过程不希望被调用过程修改的寄存器的值为程序的变量提供足够的内存空间程序的调用和返回严格遵从后进先出 (LIFO) 原则

26 编程指南 :(4) 过程调用我们需要存储 : 返回地址 (old ra) 参数 x, y, z in f(x, y, z) 临时 / 局部的变量 ( 在 f 执行过程中 ) 被破坏的寄存器想法 : 存在栈里! 增长 (PUSH 进去 ) 栈, ( 每次调用函数时 ) 缩减栈 (POP 出来 ) ( 每次返回时 ) 每次调用都有自己的栈框架 int fact( int n ) { int x, y, z, a, b; if (n > 0) return fact( n-1 ) * n; else return 1 ; 主存储器 <SP> } 地址减小方向例如调用 fact(2)

27 使用栈 : 栈框架我们需要存储 : 返回地址 (old ra) 参数 x, y, z in f(x, y, z) 临时 / 局部的变量 ( 在 f 执行过程中 ) 被破坏的寄存器想法 : 存在栈里! 增长 (PUSH 进去 ) 栈,( 每次调用函数时 ) 缩减栈 (POP 出来 ) ( 每次返回时 ) 每次调用都有自己的栈框架地址减小方向 int fact( int n ) { if (n > 0) return fact( n-1 ) * n; else return 1 ; } 例如主存储器 2 return addr temp vars 调用 fact(2) fact(2) s 的栈框架 <SP>

28 使用栈 : 栈框架我们需要存储 : 返回地址 (old ra) 参数 x, y, z in f(x, y, z) 临时 / 局部的变量 ( 在 f 执行过程中 ) 被破坏的寄存器想法 : 存在栈里! 增长 (PUSH 进去 ) 栈,( 每次调用函数时 ) 缩减栈 (POP 出来 ) ( 每次返回时 ) 每次调用都有自己的栈框架主存储器地址减小方向 int fact( int n ) { if (n > 0) return fact( n-1 ) * n; else return 1 ; } 例如 2 return addr temp vars 1 return addr temp vars 调用 fact(2) fact(2) s 栈框架 fact(1) s 栈框架 <SP>

29 使用栈 : 栈框架我们需要存储 : 返回地址 (old ra) 参数 x, y, z in f(x, y, z) 临时 / 局部的变量 ( 在 f 执行过程中 ) 被破坏的寄存器想法 : 存在栈里! 增长 (PUSH 进去 ) 栈,( 每次调用函数时 ) 缩减栈 (POP 出来 ) ( 每次返回时 ) 每次调用都有自己的栈框架 int fact( int n ) { if (n > 0) return fact( n-1 ) * n; else return 1 ; 主存储器 } 地址减小方向 2 return addr temp vars 1 return addr temp vars 0 return addr temp vars 例如调用 fact(2) fact(2) s 框架 fact(1) s 框架 fact(0) s 框架 <SP>

30 使用栈 : 栈框架我们需要存储 : 返回地址 (old ra) 参数 x, y, z in f(x, y, z) 临时 / 局部的变量 ( 在 f 执行过程中 ) 被破坏的寄存器想法 : 存在栈里! 增长 (PUSH 进去 ) 栈,( 每次调用函数时 ) 缩减栈 (POP 出来 ) ( 每次返回时 ) 每次调用都有自己的栈框架主存储器地址减小方向 int fact( int n ) { if (n > 0) return fact( n-1 ) * n; else return 1 ; } 例如 2 return addr temp vars 1 return addr temp vars 调用 fact(2) fact(2) s 栈框架 fact(1) s 栈框架 <SP>

31 使用栈 : 栈框架我们需要存储 : 返回地址 (old ra) 参数 x, y, z in f(x, y, z) 临时 / 局部的变量 ( 在 f 执行过程中 ) 被破坏的寄存器想法 : 存在栈里! 增长 (PUSH 进去 ) 栈,( 每次调用函数时 ) 缩减栈 (POP 出来 ) ( 每次返回时 ) 每次调用都有自己的栈框架主存储器地址减小方向 int fact( int n ) { if (n > 0) return fact( n-1 ) * n; else return 1 ; } 例如 2 return addr temp vars 调用 fact(2) fact(2) s 的栈框架 <SP>

32 使用栈 : 栈框架我们需要存储 : 返回地址 (old ra) 参数 x, y, z in f(x, y, z) 临时 / 局部的变量 ( 在 f 执行过程中 ) 被破坏的寄存器想法 : 存在栈里! 增长 (PUSH 进去 ) 栈,( 每次调用函数时 ) 缩减栈 (POP 出来 ) ( 每次返回时 ) 每次调用都有自己的栈框架主存储器 <SP> 地址减小方向 int fact( int n ) { if (n > 0) return fact( n-1 ) * n; else return 1 ; } 例如调用 fact(2)

33 调用者 : 栈的规定 ( 简介 ) 将参数按照相反的顺序放入栈中跳转到被调用函数地址, 返回地址 ra 调整栈指针将参数移除被调用者的任务 : 在栈内保存 ra 为局部变量在栈内分配存储器这样每次调用的时候都可以有不同的工作存储器计算, 并将结果放在寄存器中保存并在结束的时候恢复被自己破坏的寄存器, 也是在栈里每次返回前都要将栈恢复成与进来时指针一样 Jr $ra

34 框架细节 args ( 函数参数 ) 地址减小方向 <fp> old <ra> old <fp> locals temps ( 返回地址 ) ( 调用者的栈框架 ) ( 局部变量 ) ( 被破坏的寄存器 ) 保留的专用寄存器 <SP> r30 = fp 框架指针 : 指向第一个局部变量和临时变量 (points to 1 st local) r31 = ra 返回地址 : 保存调用者下一条指令的地址 ( 等于调用当时的 PC) r29 = SP 栈指针 : 指向第一个可用的栈内地址 r26 = XP 异常指针 : 当中断发生时保存 PC

35 访问框架存储器 fp 是访问当前框架内存储器内容的基指针在一次函数调用内 : fp 指向变量, 老的 ra, 和老的 fp 之后 <fp> 指向第一个临时变量, <fp>+12 指向第一个调用时的参数 fp 本身也是要保存的! <fp>+12 <fp> <SP> arg n... arg 1 old <ra> old <fp> local 1... local k 为了访问 j th 局部变量 : LW $rx, (fp) SW $rx, (fp) 为了访问第 j th 参数 : LW $rx, (fp) SW $rx, (fp) Note: 调用者必须按照逆序将参数入栈, 这样第一个调用参数将总是在相对于 fp 相同的位置 (fp+12)

36 递归方式实现阶乘例子 : int x,y; main() { x = fact( y ); } int fact( int n ) { if (n!= 0) return fact( n-1 ) * n; else return 1 ; } ( 书上 606 页 ) 这个程序的汇编程序说明了过程是怎么处理栈框架的

37 递归方式实现阶乘 ( 书上 606 页 ) 在过程接口处, 程序 main 构造程序的堆栈帧 : 两个 old 寄存器 :$fp, $ra 四个参数寄存器 :$a0-$a3 栈帧指针 :$fp= 栈帧大小 -4 +$sp.text.globl main main: subu $sp, $sp,32 # 堆栈帧有 32 位字节长 sw $ra, 20 ($ sp ) # 保存返回地址 sw $fp, 16 ($ sp ) # 保存旧帧指针 addu $fp, $ sp, 28 # 设置帧指针

38 递归方式实现阶乘 li $a0, 10 # 将参数 10 送到寄存器 $a0 jal fact # 调用递归函数 la $ a0, $ LC # 字符串送到寄存器 $a0 move $a1, $v0 # 函数 fact 中返回的结果送到寄存器 $a1 jal printf # 调用 printf 函数 lw $ra,20($sp) # 读出返回值 lw $fp,16 ($sp) # 读出帧指针 addu $sp,$sp,32 # 弹出堆栈指针 jr $ra # 返回调用程序.rdata $LC:.ascii The factorial of 10 is % d\n\

39 递归方式实现阶乘.text fact: subu $sp, $sp,32 # 堆栈帧有 32 个字节 sw $ra, 20 ($ sp ) # 保存返回地址 sw $fp, 16 ($ sp ) # 保存旧帧指针 addu $fp, $ sp, 28 # 设置帧指针 sw $a0, 0 ($ fp) # 保存参数 (n) lw $ v0, 0 ($ fp) # 装入 a0 bgtz $ v0, $L2 # 执行判断分支 if n>0 li $ v0, 1 # 返回 1 j $L1 # 跳转到代码并返回

40 递归方式实现阶乘 $L2: lw $ v1, 0 ($ fp) # 装入 n subu $v0, $v1, 1 # 计算 n -1 move $ a0, $v0 # 将值送到寄存器 $ a0 jal $fact # 调用过程 fact lw $v1, 0( $ fp) # 装入 n mul $ v0, $ v0, $ v1 # 计算 n*fact(n-1) $L1: # 结果保存到寄存器 $ v0 lw $ ra,20 ($ sp) # 保存寄存器 $ ra lw $fp,16 ($ sp) # 保存寄存器 $ fp addu $sp, $ sp,32 # 弹出堆栈 j $ra # 返回到调用过程

41 编程指南 : (5) 阅读改进汇编代码.data #x s address stored in $a0 # f s address stored in $a1.text move $s1,$0 move $s2,$s1 addiu $s3,$0,1 lw $s4,0($a0) loop: subu $s4,$s4,1 beqz $s4,done move $s1,$s2 move $s2,$s3 addu $s3,$s2,$s1 j loop done: sw $s3,0($a1) 这段程序干了啥?

42 阅读汇编代码.data #x s address stored in $a0 # f s address stored in $a1.text move $s1,$0 move $s2,$s1 addiu $s3,$0,1 lw $s4,0($a0) loop: subu $s4,$s4,1 beqz $s4,done move $s1,$s2 move $s2,$s3 addu $s3,$s2,$s1 j loop done: sw $s3,0($a1) #$s1=0 #$s2=$s1 #$s3=1 #$s4=x #$s4=$s4-1 #if($s4=0)done #$s1=$s2 #$s2=$s3 #$s3=$s2+$s1 #goto loop #store result in f 这段程序干了啥? a = 0; // a = r1 b = a; // b = r2 res = 1; i = x; while ( --i!= 0 ) // dec i then check if 0 { a=b; b=res; res=a+b; } f = res; // note x itself isn t changed x = f = 前两项均为 1, 从第三项起, 每一项都是其前两项的和 f = fib(x) (for x > 0) (Fibonacci)

43 例题汇编下面的 C 语言语句 1. a=b+5*c; 2 if(b> a) c=127;.data 0x c:.word b:.word 2345 a:.word 0.text main: ori $s6,$0,0x1000 sll $s6,$s6,16 #C s Address addiu $s5,$s6,4 #B s Address addiu $s4,$s5,4 #A s Address lw $s1,0($s6) #$s1=c sll $s0,$s1,2 #$s0=$s1*4 addu $s0,$s0,$s1 #$s0=$s0+$s1 lw $s1,0($s5) #$s1=b addu $s0,$s0,$s1 #$S0=$S0+$S1 done: sw $s0,0($s4) #store result in a

44 例题汇编下面的 C 语言语句 1. a=b+5*c; 2 if(b> a) c=127;.data 0x b:.word 2345 a:.word 0 c:.word 0.text Main: ori $s6,$0,0x1000 sll $s6,$s6,16 #B s Address addiu $s5,$s6,4 #A s Address addiu $s4,$s5,4 #C s Address lw $s0,0($s5) #$s0=a lw $s1,0($s6) #$s1=b slt $s0,$s0,$s1 #s0=1, (s0<=s1) beqz $s0,done #if($s0=0)done addiu $s0,$0,127 #$s0=127 sw $s0,0($s4) # c=$s0 done:

45 思考题 : 当变量存储在一个绝对地址与 0x 距离超过 2 16 的地方时, 如何访问?.data 0x A:.word

46 优化代码 ( 请同时完成书上 3.9 题 ).data #x: $a0 #f: $a1.text move $s1,$0 move $s2,$s1 addiu $s3,$0,1 lw $s4,0($a0) loop: subu $s4,$s4,1 beqz $s4,done move $s1,$s2 move $s2,$s3 addu $s3,$s2,$s1 j loop done: sw $s3,0($a1) #$s1=0 #$s2=$s1 #$s3=1 #$s4=x #$s4=$s4-1 #if($s4=0)done #$s1=$s2 #$s2=$s3 #$s3=$s2+$s1 #goto loop #store result in f 如何使本部分代码运行更快? 目前运行时间 : = const + 6x 能否达到 const + 5x?

47 Optimizing Code move $s1,$0 #$s1=0 move $s2,$s1 #$s2=$s1 addiu $s3,$0,1 #$s3=1 lw $s4,0($a0) #$s4=x subu $s4,$s4,1 #$s4=$s4-1 beqz $s4,done #if($s4=0)done loop: move $s1,$s2 #$s1=$s2 move $s2,$s3 #$s2=$s3 addu $s3,$s2,$s1 #$s3=$s2+$s1 subu $s4,$s4,1 #$s4=$s4-1 bnez $s4,loop #while($s4!=0)goto loop done: sw $s3,0($a1) #store result in f 运行时间从 const+6x 到 const+5x Trick: 将 SUB 和检查移出, 减掉额外的分支指令当 x 比较大时, 减少了运行时间 (constant 有所增加 ) 目前的编译器一般都可以支持这类优化 Can you do better?

48 有趣的话题 : 单指令计算机深入理解计算机的工作例子 :SIC single instruction computer 减并且结果如果为负数就跳转 Sbn a, b, c # mem[a] = mem[a]-mem[b]; # if mem[a] < 0 goto c; # if mem[a] >=0 从紧接着本指令的下一存储器地址取出下一条指令三个操作数每个都指向存储器中一个字的地址

49 有趣的话题 : 单指令计算机 SIC 虽然只有一条指令, 通过巧妙设计 sbn 指令的次序,SIC 能模仿很多更复杂指令集的操作例 : 将存储器地址 a 的数复制到存储器 b Start: sbn temp, temp,.+1 # 将 temp 清零 sbn temp, a,.+1 # 将 temp 设为 -a sbn b, b,.+1 # 将 b 清零 sbn b, temp,.+1 # 将 b 设为 -temp, 即 a 这条指令之后的地址

50 Q: 我们现在有了什么? 可以做什么了? 1 可编程的控制如何实现一个计算机以达到 UTM 的作用 2 指令集与不同级别的抽象 3 MIPS 的 Programming Model

51 Motivation: 计算一个表达式 Given an expression: K = (C + D) * (C - D) 我们可以设计这么一个电路 ( 或者说是图灵机 ) C D C D + - 电路的规模直接与计算表达式的规模有关 * K

52 回忆一下 : 我们已经有了 UTM 的思想 1:T u 查看 Tape2 和 Tape3 来决定图灵机的配置 T k ( 采用第 k 个图灵机 ) 及它的输入 j; 2:T u 查看第一个磁带 Tape1 决定 T k 会怎么做 ; 3: 修改磁带 2 和 3 以反映 T k (j) 在计算过程中的动作和内部状态变化 ; 我们的任务是计算所有的可计算的整数函数

53 控制与数据通路的方法用一系列的命令给一个简单的单元 ( 名叫 datapath) 以实现表达式计算 Control (outputs) Universal Datapath Control FSM State ALU Condition codes (inputs) 这样数据通路的规模就不随着问题规模增大而增大了

54 Control FSM for K = (C + D) * D 假定输入 X 1, X 2 只在第一个时钟周期出现 X 1 =C X 2 =D Control FSM current outputs state A SEL A LE 1 A B B SEL B LE s 1 A SEL B SEL A LE B LE F ALU F s 2 s 3 Note: 这个 FSM 只是一些状态转移关系, 没有输入 Y

55 Control FSM for K = (C + D) * D Step 1: 通过给 A LE and B LE 置位, 把 C 和 D 加载到寄存器 A 和 B 中 X 1 =C X 2 =D Control FSM current outputs state A SEL A LE 0 1 C A 0 1 D B B SEL B LE s 1 A SEL B SEL A LE B LE F Load C into A, and D into B ALU F s 2 s 3 Note: 这个 FSM 只是一些状态转移关系, 没有输入 Y

56 s 1 Control FSM for K = (C + D) * D Control FSM current outputs state A SEL B SEL A LE B LE F s A+B s 3 Step 2: 把 A+B 计算完毕并把结果存在 A 里面 A SEL A LE Put C into A, and D into B Put A+B into A (A will hold C+D) Note: 这个 FSM 只是一些状态转移关系, 没有输入 X 1 =? X 2 =? ALU C+D A C Y 1 D C+D 0 B = A+B B SEL B LE F=000

57 s 1 Control FSM for K = (C + D) * D Control FSM current outputs state A SEL B SEL A LE B LE F s A+B s 3 Step 3: 将 A*B 的结果保存在 A 中 A*B A SEL A LE Put C into A, and D into B Put A+B into A (A will hold C+D) Put A*B into A (A will hold (C+D)*D) Note: 这个 FSM 只是一些状态转移关系, 没有输入 X 1 =? X 2 =? ALU (C+D)*D A C+D D 0 B (C+D)*D Y = A*B B SEL B LE F=101

58 Control FSM for K = (C + D) * D 第 3 步的时钟上升沿过后 : A 里面存放的是 (C+D)*D s 1 Control FSM current outputs state A SEL B SEL A LE B LE F s A+B s A*B A SEL A LE Put C into A, and D into B Put A+B into A (A will hold C+D) Put A*B into A (A will hold (C+D)*D) X 1 =? X 2 =? ALU (C+D)*D Note: 这个 FSM 只是一些状态转移关系, 没有输入 A 0 Y 1 D 0 B F B SEL B LE

59 写哪个会比较好一些? s 1 s 2 s 3 s 4 s 5 s 6 s 7 s 8 s 9 K = (C + D) * (C - D) RF SEL RF LE ADR A LE B LE F A+B A-B A*B 等等, 看上去下面的东西是软件? R C 0 R D 1 A <R 0 > B <R 1 > R 0 <A> + <B> R <A> 1 - <B> A <R 0 > B <R 1 > R 0 <A> * <B>

60 RTL or 机器语言需要些什么? 需要关于机器的抽象描述有哪些寄存器 : R 0, R 1, 可以进行哪些运算 : +, *, or 机器指令的编码序列 : R 1 <R 2 > + <R 3 > 需要对指令是如何改变机器状态的有深入的了解 note: 有些寄存器的转移动作是无法在一个周期内完成的! 需要定义一些指令以影响数据通路的流程 ( 条件码 ) We will see a lot of this in coming weeks

61 TTR1: 机器语言与指令集体系 ISA 两个重要的组成部分 : ( 指令不仅仅是操作而已!) (1) 可见的状态 ( 寄存器, 存储器等 ); (2) 这些状态的操作 (instructions) 存储程序的计算机 (UTM)

62 深入内部看看 Von Neumann 模型存储 T k 的内部状态存储 T k 的磁带 j T K 的描述 K 的描述 UTM! 指令被编码成为二进制的数据指令计数器 PC: 下一条指令的地址转换指令为数据通路的控制信号的控制逻辑

微机原理(计算机原理与接口技术)

微机原理(计算机原理与接口技术) 微机原理 ( 计算机原理 ) 第 10 讲 MIPS 体系结构与编程 1 第 10 讲 MIPS 体系结构与编程 MIPS 体系结构概述 MIPS 指令集简介 MIPS 汇编语言程序设计 2 MIPS 体系结构概述 MIPS 诞生于 1980 年代, 是最早的 RISC 处理器之一, 也是目前销量最好的 RISC 处理器之一, 从游戏机到路由器, 再到 SGI 的超级计算机, 都可以看到 MIPS