第 3 章 程序的机器级表示

程序编码

对于机器级变成来说，两种抽象尤为重要。第一种是由指令集体系结构或指令集架构（Instruction Set Architecture, ISA）来定义机器级程序的格式和行为，它定义了处理器状态、指令的格式，以及每条指令对状态的影响。

第二种抽象是，机器级程序使用的内存地址是虚拟地址，提供的内存模型看上去是一个非常大的字节数组。

• Programmer-Visible State
  • PC: Program counter
  • Register file
  • Condition codes
  • Memory

控制：分支循环与 switch

分支

分支，if-else-then 语句，对 text-expr，常见的汇编代码，会使用条件跳转（比如jg等等），判断text-expr相反的情况（因为真才跳转），为真则跳转至后面（即 else），为假则继续执行，这样整体生成的汇编代码会比较符合原始 C 代码的顺序。

还有一种优化的手段，使用条件传送，即同时计算分支两边，然后根据条件是否满足从中选取一个，使用cmovge指令实现条件赋值。现代处理器通常使用流水线 pipeline 来获得高性能，这种优化的控制不依赖于数据，使得处理器更容易保持流水线是满的。

理解这种优化的手段，教授举的例子很恰当，，想象程序的执行是在指令的 big ocean 中，向一个方向会比较容易（在流水线，指令预取等技术帮助下），但停下来掉头就要很困难，条件传送的优化就在于可以尽量减少这种“掉头”的情况。

循环

do-while 循环的翻译更容易理解，执行一次后对test-expr条件进行判断，满足则跳转回。

while 循环的翻译方法，一种叫做跳转到中间（jump to middle），即先五跳转到循环结尾处进行测试，来进行初始测试，满足则 goto 的循环体。另一种翻译较高等级比如-O1 优化时会采用，叫做 guarded-do，会先对不满足条件进行测试，条件跳转至结尾，否则执行循环体，然后再测试 goto loop，后面类似 do-while，只是加了前面初始情况的限制，所以叫做 guarded-do。

for 语句可以对应翻译成 while 循环来理解（注意练习题中提到的 continue 的问题，不能 goto 直接跳过更新，否则会造成死循环）。

switch

注意 bias，极差为表大小，需要找到跳转表和实际 case 的关系（顺序一般不是对应的），ja巧妙的解决了负数的问题，负数会被理解为无符号的相当大的数，ja后面紧跟的是 default 情况的地址。注意观察跳转表里与 default 地址一致的就是不显示的 case（虽然在范围内，但也是 default）。

根据 CMU 课堂上的讨论，如果有相当大的两个 case（比如 0 和 100000），是不是要填这么大一张表格？教授指出编译器来划定跳转表框架，这种情况实际采用的是二分 if-else 来 balance 空间消耗（还好是编译器来做这件事）。

过程 Procedures

栈帧！栈帧！

转移控制 Passing Control

（大部分笔记都记录在书上了）Passing Control 记住%rsp指向栈顶元素，call 指令执行后，则会向低地址移动，将 call 后面一条指令（返回的地址）填入，即压栈。然后自动地将程序指针%rip指向 call 的过程的起始地址（之前是 call 上一条指令地址）。ret 指令执行后，则弹出，返回地址写回程序指针%rip，又回到 call 后面一条指令。

数据传送 Data

几个点

传递参数：超过寄存器 6 个传递的值需要使用分配栈上的空间，

寄存器分为调用者保存的寄存器（%rdi,%rsi,%rdx,%rcx,%r8,%r9），还有被调用者保存的寄存器（%rbx,%rbp,%r12--%r15），对于调用者来说，后者这些寄存器可以确定在过程调用前后值是一定的（用来保存一些局部变量很有用），所以使用被调用者保存的寄存器时，都要在过程起始压栈（存入原始值），然后在末尾弹出，另外%rax是返回值用。

递归过程

!!注意查阅尾递归栈帧复用资料，C 和 OCaml 尾递归到底有啥差别。

机器语言角度看，递归过程和普通的函数调用并无多少差别。

数据

机器级代码中是没有数组这一高级概念的，而是将其视作字节的集合，struct 也一样。

Arrays

经常，计算地址的时候 lea，值的时候 mov，注意尾缀是 w，l 还是 q 要依据数组实际存储的数据类型。

指针运算和数组的联系已经比较熟悉了，再次强调，定义数组的时候我们已经在某个地方分配了空间，并提供允许一定指针运算的数组名称，但是我们定义一个指针的时候，就只有该指针而没有额外分配的空间。

注意 Nested array（整个数组在一起，可以一次性计算内存要取的地址），还有 Multi-level array（多层次，需要先获得指针，然后再根据指针加偏移计算要取的地址，至少两次）

• Fixed dimensions: 定长数组优化，C 语言编译器能够优化定长多维数组上的操作代码。
• Variable dimensions, explicit indexing
• Variable dimensions, implicit indexing

Structures

structures 需要注意对齐，数据强制以特定的地址（x 倍数）开始。

Advanced Topics

本节主要跟随 CMU 原始课程有关机器编程的最后一个视频

Memory Layout

x86-64 Linux 的内存结构

• Stack
  • Runtime stack (8MB limit)如果尝试使用栈指针来指向超过 8M 的地址，会产生一个段错误。
  • 0x00007f 开头的就是放在栈中的（容易推测）
• Heap
  • Dynamically allocated as neeed
  • malloc(), calloc(), new()
• Data
  • Statically allocated data
  • E.g. global vars, static vars, string constants.
• Text/Shared Libraries
  • Executable machine instructions 一些 library，当程序开始执行之处会把它们加载到程序当中，称之为“动态加载”。

分布 Stack 是在高地址向下扩展的（和之前使用栈帧的习惯相同）。Text Data 低地址，Heap 在其上，向高地址扩展。

Buffer Overflow

C 语言编写的程序，从外界获取一个很大的值，产生栈溢出，安全风险。在存储来自一条消息的字符串时，将会出现非常多有关缓冲区溢出的问题。罪魁祸首：存储字符串但是并不检查字符串边界的库函数。gets，strcpy都默认分配了足够的目标地址缓冲区，很容易溢出。以及scanf当输入字符串的时候也不会做缓冲区的检测和限制。