祭祖03

课时03

复习和补遗

$$三大类指令 \begin{cases} 运算指令\\ 控制分支指令\\ 数据传送（访存） 指令 \end{cases}$$
指令的格式，操作码（高6位） 和 操作数

$$操作数的种类 \begin{cases} reg\\ 存储器addr\\ 常数（最快） \end{cases}$$
0需要用0号寄存器表示这个立即数，所以常数不可能为0
留给常数的位数有限，一般很小，可正负有符号数，二进制补码

无符号数每一位都是有效数字

符号拓展 Sign Extension

有符号数，根据最高的符号位
e.g 4bit to 8bit

1111 -> 1111 1111
0111 -> 0000 0111

无符号数无论高位如何全部补0到需求的位数。

addi, extend immediate value
lb, lh: extend loaded byte/halfword
beq, bne: extend the displacement

instructions format

r-format instructions

op	rs	rt	rd	shamt	funct
6bits	5bits	5bits	5bits	5bits	6bits

在r-format中，三个oprand都是寄存器
rs:first source reg number
rt:second source reg number
rd destination reg number
shamt shiift aount 00000 移位，因为mips机器字长只有32位。
funct function code: 拓展码，也叫功能码。因此一共可以表示$2^{12}$个指令了。

I-format

Only one oprand is immediate number and other two oprands are register
I-format也是一个有着3个操作数的指令。

op	rs	rt	constand or adddress
6bits	5bits	5bits	16bits

rt: dest or src register number
constant: $-2^{15} \sim 2^{15} - 1$
address: offset addded to base address in rs

和r-format相比，
higher 16 bits are same
lower 16bit is different
组成相似，这使得指令解析简单。
Design priinciple: good design demands good compromises

• Different formats complicate decoding, but allow 32-bit
  instructions uniformly
• Keep formats as similar as possible

logical operations

e.g.
op rs rt rd shamt funct
shamt : how many positions to shift
shift operations:

1. shift left logical:
   • shift left and fill with 0bits
   • sll by i bits multiplies by 2^i
2. shift right logical…

1001 1101
srl l:01001110
srav a:11001110

nor 3reg $t0 $t1 $zero
weile 和r型操作数做统一

条件分支指令 Conditional Operations

beq rs,rt,L1

if (rs == rt) branch to inst labeld L1
It is a I-fmt instruction, L1 here is an immediate number
bne
these two above is compiling if statements.

if (i == j)    f = g + h;
else:     f = g - h;

这里都是局部变量，所以用寄存器。

bne $s3,$s4,Else
add $s0,$s1,$s2
j Exit
Else: sub $s0,$s1,$s2

---

j L1 : unconitonal jump to instruction label L1
It belongs to J-fmt command
One opcode plus one oprand
Here is a compiling loop statement example.

while( save[i] == k ) i+= 1;

Loop: sll $t1, $t1 ,2 # 移位，x4，因为一个int占内存4个字节
add $t1, $t1, $s6        # 得到地址
lw  $t0,  0($t1)  
bne  $t0,  $s5,  Exit  
addi  $s3,  $s3,  1  
j  Loop  
Exit:  ...

lw 抽象一下那张矩形图，从下往上。

关于高级语言代码过编译器的优化tips
A basic block is a sequence of instructions
with

• No embedded branches (except at end)
• No branch targets (except at beginning)
• A compiler identifies basic blocks for optimization
• An advanced processor can accelerate execution of basic blocks

更多的条件分支操作

$<$: r-fmt的 slt和i-fmt 的slti

slt rd,  rs, rt  
if (rs < rt) rd = 1; else rd = 0;

slti rt,  rs, constant  
if (rs < constant) rt = 1; else rt = 0;

$\le$？ 先判断小于再判断等于
$>$，调换$\le$的rs和rt

slt  $t0,  $s1,  $s2  #  if  ($s1  <  $s2)  
bne  $t0,  $zero,  L  #  branch  to  L

拓展阅读 Why not blt, bge, etc?

Hardware for <, ≥, … slower than =, ≠
Combining with branch involves more work per instruction, requiring a slower clock
All instructions penalized!
beq and bne are the common case
This is a good design compromise

case/switch statement

beq bne j jr
switch：

1. 嵌套beq，a chain of if-elif
2. 跳转表，jump address table/jump table类似你在oi中开大数组下标模拟哈希表一样。
   switch(x):
   case 0:
   break;
   …
   case 200:
   break;
   假如只有9个标签，但是取case的最大数，需要200，用int类型就要开200*4bits空间。
   非常耗费空间，适用于case多情况。

jr跳寄存器

Procedure Calling

j and jal
how to use 16bits to express 32bits address?
这就介绍到Program Counter了。
PC: program count程序计数器，无法被用户代码访问对特殊寄存器。
其值=下一条执行指令的地址，不是跳转（如存在）之后的值，而是刚刚执行的下一条指令。
存储程序$\to$程序到存储器中$\to$cpu从存储器取出所需要的指令。
相邻指令相距4个字节，pc每次自动+4bytes。

ps:存储器单位都是1个字节1个字节操作的。

所以转移地址怎么计算呢？
op 6bits + address 26bits
规定j和jal操作码只能转移到对齐地址。这个地址只能被4字节整除，也就是地址最低两位为0.。

在 MIPS 平台上，lh 读取一个半字时，存储器的地址必须是 2 的整数倍； lw 读取一个字时，存储器的地址必须是 4的整数倍； sd 写入一个双字时，存储器的地址必须是 8 的整数倍。倘若访存时，目标地址不对齐，则会引起异常,典型的是系统提示“总线错误”后，直接杀死进程。

所以，00 就需要不存了，只存高位。
所以现在16bits可以表示18bits的值。

bne beq : target address = PC + (offset* 4)

tips: pc has already incremented by 4 by this time
offset是有符号数，所以可以为负数。
j/ jal $PC_{31…28} $+ address(后26bits) * 4

例题p62
在最后的j loop中，
题节目中的地址是十进制，convert to bin进制，80024-》 31.。。28就是全0，
所以 所求的26bits数 * 4 == 80000（要跳转）

怎么跳的更远呢。

过程调用

1. Placeparametersinregisters
2. Transfer control to procedure
3. Acquire storage for procedure
4. Performprocedure’soperations
5. Place result in register for caller
6. Return to place of call

call

jal ProcedureLabel 起下列两个作用(call)

• pc赋值给ra (作为return address),Address of following instruction put in $ra
• PC(31-28)连接I * 4 赋值给PC. 这也是j操作码所做的。Jumps to target address

jr return: ra重新赋值给pc

做过程调用的第2和6步。

温习用到的reg
$a0 – $a3: arguments (reg’s 4-7)
$v0, $v1: result values (reg’s 2 and 3)
$sp: stack pointer (reg 29)
$ra: return address (reg 31)

叶子过程（即不会再调用其他过程）示例，

int leaf_exam(intg ,h ,i ,j) // a0 a1 a2 a3必定按顺序编号{
int f;
f= (g + h) - (i +j);
return f;
}	

Arguments g, …, j in $a0, …, $a3
f in $s0 (hence, need to save $s0 on stack)
Result in $v0

leaf_example:  

# Save $s0 on stack  
addi  $sp,  $sp, -4  
sw  $s0,  0($sp)  

# Procedure body
add  $t0,  $a0,  $a1  
add  $t1,  $a2,  $a3  
sub  $s0,  $t0,  $t1  

# Result
add  $v0,  $s0,  $zero  

# Restore $s0  
lw  $s0,  0($sp)  
addi  $sp,  $sp,  4  

# Return
jr  $ra   

非叶子过程示例，
Procedures that call other procedures
For nested call, caller needs to save on the
stack:

• Its return address
• Any arguments and temporaries needed after
  the call
  Restore from the stack after the call
  这里示例递归法求阶乘。

  
C code:  
int  fact  (int  n)  
{  
if  (n  <  1)  return  1;  
else  return  n  *  fact(n - 1);  
}  

• Argument n in $a0
• Result in $v0

fact:  
addi  $sp,  $sp, -8  #  adjust stack  for  2  items  
sw  $ra,  4($sp)  #  save  return  address  
sw  $a0,  0($sp)  #  save  argument  
slti  $t0,  $a0,  1  #  test  for  n  <  1  
beq  $t0,  $zero, L1  
addi  $v0,  $zero,  1  #  if  so,  result  is  1  
addi  $sp,  $sp,  8  #  pop  2  items  from  stack  
jr  $ra  #  and  return  
L1:  addi  $a0,  $a0, -1  #  else  decrement  n  
jal  fact  #  recursive  call  
lw  $a0,  0($sp)  #  restore  original  n  
lw  $ra,  4($sp)  #  and  return  address  
addi  $sp,  $sp,  8  #  pop  2  items  from  stack  
mul  $v0,  $a0,  $v0  #  multiply  to get  result  
jr  $ra  #  and  return

其他的话

像c语言的函数内static变量，存储在内存中而不是寄存器。
另外，下周才布置作业。