深入理解计算机系统CSAPP笔记(未完)

点击查看参考教程

参考文章	参考链接
文章	深入理解计算机系统 (wolai.com)
书籍	《深入理解计算机系统（CSAPP）》
书籍勘误	深入理解计算机系统，第三版(CSAPPe3)

第一章 计算机系统漫游

以一个C语言的HelloWorld程序为例，看看程序运行的生命周期是怎样的

#include <stdio.h>
int main(){
    printf("Hello World\n");
    return 0;
}

程序的表示：信息就是位+上下文

• hello **程序的生命周期是从一个源程序（源文件）**开始的。

  • 即程序员通过编辑器创建并保存的文本文件，文件名是hello.c 。
  • 源程序实际上就是一个由值 0 和 1 组成的位（又称为比特）序列，8 个位被组织成一组，称为字节。每个字节表示程序中的某些文本字符。

• 像 hello.c 这样只由 ASCII 字符构成的文件称为文本文件，所有其他文件都称为二进制文件。

• hello.c 的表示方法说明了一个 基本思想：系统中所有的信息包括磁盘文件、内存中的程序、内存中存放的用户数据以及网络上传送的数据，都是由一串比特表示的。区分不同数据对象的唯一方法是我们读到这些数据对象时的上下文。

  所谓信息就是位+上下文，位是对于信息的存储载体，上下文是对位中存储内容的定义，是一种约定。

• 比如，在不同的上下文中，一个同样的字节序列可能表示一个整数、浮点数、字符串或者机器指令。

  C 语言的特点

  1. C 语言小而简单
  2. C 语言是为了实现 unix 而设计的
  3. C 语言与 unix 关系密切

  C 语言是系统级编程的首选，也非常适用于应用级程序。

程序的翻译：从高级语言到机器语言

程序被其他程序翻译成不同的格式

• hello 程序的生命周期是从一个高级 C 语言程序开始的，然而，为了在系统上运行 hello.c 程序，每条 C 语句都必须被其他程序转化为一系列的低级机器语言指令。然后这些指令按照一种称为可执行目标程序的格式打好包，并以二进制磁盘文件的形式存放起来。目标程序也称为可执行目标文件。

• 在Unix 系统上，从源文件到目标文件的转化是由编译器驱动程序完成的：

  gcc -o hello hello.c

• 在这里，GCC 编译器驱动程序读取源程序文件 hello.c，并把它翻译成一个可执行目标文件 hello 。这个翻译过程可分为四个阶段完成，执行这四个阶段的程序（预处理器、编译器、汇编器和链接器）一起构成了编译系统(compilation system) 。

  
  • 预处理阶段。预处理器(cpp)根据以字符＃开头的命令，修改原始的 C 程序.
  • 编译阶段。编译器(eel)将文本文件 hello.i 翻译成文本文件 hello.s，它包含一个汇编语言程序。
  • 汇编阶段。接下来，汇编器(as)将 hello.s 翻译成机器语言指令，把这些指令打包成一种叫做可重定位目标程序(relocatable object program) 的格式，并将结果保存在目标文件 hello.o 中。
  • 链接阶段。链接器(ld) 就负责处理不同目标文件之间的合并。结果就得到 hello 文件，它是一个可执行目标文件（或者简称为可执行文件），可以被加载到内存中，由系统执行。

了解编译系统如何工作是大有益处的

• 有一些重要的原因促使程序员必须知道编译系统是如何工作的
  • 优化程序性能。为了在 C 程序中做出好的编码选择，我们确实需要了解一些机器代码以及编译器将不同的 C 语句转化为机器代码的方式。
  • 理解链接时出现的错误
  • 避免安全漏洞

程序的运行：处理器载入并解释指令

• 要想在 Unix 系统上运行可执行目标文件 hello，我们将它的文件名输入到称为 shell 的应用程序中：

  ./hello

  • shell 是一个命令行解释器，它输出一个提示符，等待输入一个命令行，然后执行这个命令。
  • 如果该命令行的第一个单词不是一个内置的 shell 命令，那么 shell 就会假设这是一个可执行文件的名字，它将加载并运行这个文件。

系统的硬件组成

• 总线

  • 贯穿整个系统的是一组电子管道，称作总线，它携带信息字节并负责在各个部件间传递。通常总线被设计成传送定长的字节块，也就是字(word)。字中的字节数（即字长）是一个基本的系统参数，各个系统中都不尽相同。现在的大多数机器字长要么是4个字节(32位)，要么是8个字节(64位)。

• I/O设备

  • I/O(输入／输出）设备是系统与外部世界的联系通道。每个 I/O 设备都通过一个控制器或适配器与 I/O 总线相连。
  • 控制器是 I/O 设备本身或主板上的芯片组，适配器则是一块插在主板上的卡。

• 主存

  • 主存是一个临时存储设备，在处理器执行程序时，用来存放程序和程序处理的数据。从物理上来说，主存是由一组动态随机存取存储器(DRAM)芯片组成的。从逻辑上来说，存储器是一个线性的字节数组，每个字节都有其唯一的地址（数组索引）

• 处理器

  • 中央处理单元(CPU)，简称处理器，是解释（或执行）存储在主存中指令的引擎。包括程序计数器（PC）、寄存器文件(register file)和算术／逻辑单元(ALU)
  • 处理器的核心是一个大小为一个字的存储设备（或寄存器），称为程序计数器(PC)。在任何时刻，PC 都指向主存中的某条机器语言指令（即含有该条指令的地址）
  • 处理器就是在不断执行程序计数器指向的指令。每执行一条，程序计数器更新一次，指向下一条指令。
  • 寄存器文件是一个小的存储设备，由一些单个字长的寄存器组成，每个寄存器都有唯一的名字。
  • ALU 是处理器进行运算的组件，计算新的数据和地址值。
  • CPU的基础操作

    • 加载：从主存复制一个字节或者一个字到寄存器，以覆盖寄存器原来的内容。

    • 存储：从寄存器复制一个字节或者一个字到主存的某个位置，以覆盖这个位置上原来的内容。

    • 操作：把两个寄存器的内容复制到 ALU，ALU 对这两个字做算术运算，并将结果存放到一个寄存器中，以覆盖该寄存器中原来的内容

    • 跳转：从指令本身中抽取一个字，并将这个字复制到程序计数器(PC)中，以覆盖 PC 中原来的值。

• 区分处理器指令集架构和微体系架构：

  • **指令集架构：**每条机器指令的效果
  • **微体系架构：**处理器实际上是如何实现的

运行hello程序

• 读取命令
  • 初始时，shell 程序执行它的指令，等待我们输入一个命令。当我们在键盘上输入字符串 “./hello” 后，shell 程序将字符逐一读入寄存器，再把它存放到内存中
  • 利用**直接存储器存取（DMA）**可以不通过寄存器，直接将数据从磁盘到达内存。
• 加载程序
  • 当我们在键盘上敲回车键时，shell 程序就知道我们已经结束了命令的输入。然后 shell 执行一系列指令来加载可执行的 hello 文件，这些指令将 hello 目标文件中的代码和数据从磁盘复制到主存。
• 执行程序
  • 目标文件 hello 中的代码和数据被加载到主存，处理器就开始执行 hello 程序的 main 程序中的机器语言指令。
  • 这些指令将 “hello,world\n” 字符串中的字节从主存复制到寄存器文件，再从寄存器文件中复制到显示设备，最终显示在屏幕上。

整个流程：读取文件字符到寄存器 → 存储到主存 → 执行指令 → 加载 helloworld 到寄存器 → 复制到显示器 → 显示

程序的效率：存储设备层次结构

为什么需要高速缓存

• 复制的成本
  • 在 HelloWorld 示例中可以看出，系统花费了大量的时间把信息从一个地方挪到另一个地方。
  • 这些复制就是开销，减慢了程序“真正”的工作。因此，系统设计者的一个主要目标就是使这些复制操作尽可能快地完成。
  • 从主存读取一个字比磁盘快 1000 万倍。从寄存器文件读取比主存块 100 倍，并且差距还在加大。
• 高速缓存
  • 较大的存储设备要比较小的存储设备运行得慢，而快速设备的造价远高于同类的低速设备
  • 针对处理器的运行速度远高于内存的问题，系统设计者采用了更小更快的存储设备，称为高速缓存存储器（cache memory，简称为 cache 或高速缓存），作为暂时的集结区域，存放处理器近期可能会需要的信息。
  • 位于处理器芯片上的 L1 高速缓存位于 CPU 上，容量可以达到数万字节（几十 kB），访问速度几乎和访问寄存器文件一样快。一个容量为数十万到数百万字节（几百 kB 到 几 MB）的更大的 L2 高速缓存通过一条特殊的总线连接到处理器
  • 比较新的、处理能力更强大的系统甚至有三级高速缓存
  • L1 和 L2 高速缓存是用一种叫做静态随机访问存储器(SRAM)的硬件技术实现的。利用了高速缓存的局部性原理，即程序具有访问局部区域里的数据和代码的趋势。通过让高速缓存里存放可能经常访问的数据，大部分的内存操作都能在快速的高速缓存中完成。

利用高速缓存可以将程序的性能提高一个数量级

存储设备层次结构

• 在处理器和一个较大较慢的设备（例如主存）之间插入一个更小更快的存储设备（例如高速缓存）的想法已经成为一个普遍的观念。不同运行速度的存储设备被组织成了一个存储器层次结构。
• 在这个层次结构中，从上至下，设备的访问速度越来越慢、容最越来越大，并且每字节的造价也越来越便宜。
• 存储器层次结构的主要思想是上一层的存储器作为低一层存储器的高速缓存。因此，寄存器文件就是 L1 的高速缓存，L1 是 L2 的高速缓存，L2 是 L3 的高速缓存，L3 是主存的高速缓存，而主存又是磁盘的高速缓存。

系统的管理：硬件管理和基本操作的封装

操作系统

• 应用程序并没有直接访问底层硬件，它们依靠操作系统提供的服务。我们可以把操作系统看成是应用程序和硬件之间插入的一层软件。所有应用程序对硬件的操作尝试都必须通过操作系统。

  

• 操作系统有两个基本功能：

  1. 防止硬件被失控的应用程序滥用
  2. 向应用程序提供简单一致的机制来控制复杂而又通常大不相同的低级硬件设备。

• 操作系统通过几个基本的抽象概念（进程、虚拟内存和文件）来实现这两个功能。

  • 文件是对 I/O 设备的抽象表示
  • 虚拟内存是对主存和磁盘I/O 设备的抽象表示
  • 进程则是对处理器、主存和I/O 设备的抽象表示
  

进程

• 进程是操作系统对一个正在运行的程序的一种抽象。

  • 在一个系统上可以同时运行多个进程，而每个进程都好像在独占地使用硬件。
  • 并发运行，则是说一个进程的指令和另一个进程的指令是交错执行的（这两个指令属于所谓的不同线程）。
  • 一个 CPU 看上去都像是在并发地执行多个进程，这是通过处理器在进程间切换来实现的。操作系统实现这种交错执行的机制称为上下文切换。
  • 传统系统在一个时刻只能执行一个程序，而先进的多核处理器同时能够执行多个程序。

• 什么是进程上下文

  • 操作系统保持跟踪进程运行所需的所有状态信息。这种状态，也就是上下文。
  • 包括 PC 和寄存器文件的当前值，以及主存中与当前进程相关的内容。

• 什么是进程上下文切换

  • 在任何一个时刻，单处理器系统都只能执行一个进程的代码。当操作系统决定要把控制权从当前进程转移到某个新进程时，就会进行上下文切换
  • 切换时保存当前进程的上下文、恢复新进程的上下文，然后将控制权传递到新进程。新进程就会从它上次停止的地方开始。
  • 从一个进程到另一个进程的转换是由操作系统内核(kernel) 管理的。
  • 当应用程序需要操作系统的某些操作时，比如读写文件，它就执行一条特殊的系统调用(system call) 指令，将控制权传递给内核。然后内核执行被请求的操作并返回应用程序
  

• 什么是操作系统内核？

  • 内核是操作系统代码常驻主存的部分。
  • 内核不是一个独立的进程。相反，它是系统管理全部进程所用代码和数据结构的集合。

• 线程

  • 在现代系统中，一个进程实际上可以由多个称为线程的执行单元组成
  • 每个线程都运行在进程的上下文中，并共享同样的代码和全局数据。
  • 因为多线程之间比多进程之间更容易共享数据，也因为线程一般来说都比进程更高效。

虚拟内存

• 虚拟内存是一个抽象概念，它为每个进程提供了一个假象，即每个进程都在独占地使用主存。每个进程看到的内存都是一致的，称为虚拟地址空间。

• Linux 进程的虚拟地址空间

  • 在Linux 中，地址空间最上面的区域是保留给操作系统中的代码和数据的，这对所有进程来说都是一样。
  • 地址空间的底部区域存放用户进程定义的代码和数据，地址是从下往上增大的。
  

• 每个进程看到的虚拟地址空间由大量准确定义的区构成，每个区都有专门的功能。

  • **程序代码和数据。对所有的进程来说，代码是从同一固定地址开始，紧接着的是和 C 全局变量相对应的数据位置（上图从下往上看）。**代码和数据区是直接按照可执行目标文件的内容初始化的
  • 堆。**代码和数据区后紧随着的是运行时堆。**当调用像 malloc 和 free 这样的 C 标准库函数时，堆可以在运行时动态地扩展和收缩。
  • 共享库。大约在地址空间的中间部分是一块用来存放像 C 标准库和数学库这样的共享库的代码和数据的区域
  • 栈。**位于用户虚拟地址空间顶部的是用户栈，编译器用它来实现函数调用。**每次我们调用一个函数时，栈就会增长；从一个函数返回时，栈就会收缩。
  • 内核虚拟内存。**地址空间顶部的区域是为内核保留的。**不允许应用程序读写这个区域的内容或者直接调用内核代码定义的函数。相反，它们必须调用内核来执行这些操作。

• 虚拟内存的运作需要硬件和操作系统软件之间精密复杂的交互

  • 包括对处理器生成的每个地址的硬件翻译。基本思想是把一个进程虚拟内存的内容存储在磁盘上，然后用主存作为磁盘的高速缓存

文件

• 文件就是字节序列。
  • 每个 I/O 设备，包括磁盘、键盘、显示器，甚至网络，都可以看成是文件。系统中的所有输入输出都是通过使用一小组称为 Unix I/O 的系统函数调用读写文件来实现的。
  • 文件向应用程序提供了一个统一的视图，来看待系统中可能含有的所有各式各样的 I/O 设备。

系统的通信：网络

• 现代系统经常通过网络和其他系统连接到一起。从一个单独的系统来看，网络可视为一个 I/O 设备。
• 利用网络，从一台主机复制信息到另外一台主机已经成为计算机系统最重要的用途之一。

计算机系统的重要概念

Amdahl 定律

• 对提升系统某一部分性能所带来的效果被称为 Amdahl 定律。

  • 该定律的主要思想是，当我们对系统的某个部分加速时，其对系统整体性能的影响取决于该部分的重要性和加速程度。

  • 若系统执行某应用程序需要时间为 $T_{old}$。假设系统某部分所需执行时间与该时间的比例为 $\alpha$，而该部分性能提升比例为 $k$。即该部分初始所需时间为 $\alpha{}T_{old}$，现在所需时间为 $\alpha{}T_{old}/k$。因此，总的执行时间应为

    $$T_{new}=(1-\alpha)T_{old}+(\alpha T_{old})/k=T_{old}[(1-\alpha)+(\alpha/k)]$$

  • 加速比 $S$ 为

    $$S=\frac{1}{(1-\alpha)+\alpha/k}$$

• Amdahl 定律描述了改善任何过程的一般原则。

  • 虽然我们对系统的一个主要部分做出了重大改进，但是获得的系统加速比却明显小于这部分的加速比。
  • 这就是 Amdahl 定律的主要观点——要想显著加速整个系统，必须提升全系统中相当大的部分的速度。

井发和并行

• 数字计算机的整个历史中，有两个需求是驱动进步的持续动力：一个是我们想要计算机做得更多，另一个是我们想要计算机运行得更快。当处理器能够同时做更多的事情时，这两个因素都会改进。

  • 并发(concurrency)是一个通用的概念，指一个同时具有多个活动的系统；
  • 并行(parallelism)指的是用并发来使一个系统运行得更快。
  • 并行可以在计算机系统的多个抽象层次上运用。按照系统层次结构中由高到低的顺序包括：线程级并发、指令级并行和单指令、多数据并行。

• 线程级并发

  • 通过时间共享，我们能够在一个进程中执行多个控制流，这种并发执行只是模拟出来的，是通过使一台计算机在它正在执行的进程间快速切换来实现的。

  • 多核处理器的出现，真正的实现了并行。每个核都有自己的 L1 和 L2 高速缓存。

    

  • 超线程，有时称为同时多线程(simultaneous multi-threading), 是一项允许一个CPU执行多个控制流的技术。

    • 它涉及 CPU 某些硬件有多个备份，比如程序计数器和寄存器文件，而其他的硬件部分只有一份，比如执行浮点算术运算的单元。
    • 常规的处理器需要大约 20000 个时钟周期做不同线程间的转换，而超线程的处理器可以在单个周期的基础上决定要执行哪一个线程。这使得一个 4 核的系统实际上可以并行地执行8个线程。
    • 比如一个线程在等待数据装在到高速缓存，CPU 就可以去执行另一个线程。i7 处理器每个核执行两个线程，所以是 4 核 8 线程，8 个线程都并行执行。

• 指令级并行

  • 在较低的抽象层次上，现代处理器可以同时执行多条指令的属性称为指令级并行。
  • 在**流水线(pipelining)**中，将执行一条指令所需要的活动划分成不同的步骤，将处理器的硬件组织成一系列的阶段，每个阶段执行一个步骤。这些阶段可以并行地操作，用来处理不同指令的不同部分。
  • 如果处理器可以达到比一个周期一条指令更快的执行速率，就称之为超标量(superscalar)处理器。大多数现代处理器都支持超标量操作。

• 单指令、多数据并行

  • 在最低层次上，许多现代处理器拥有特殊的硬件，允许一条指令产生多个可以并行执行的操作，这种方式称为单指令、多数据，即 SIMD 并行。

抽象

抽象的使用是计算机科学中最为重要的概念之一。计算机系统中的一个重大主题就是提供不同层次的抽象表示，来隐藏实际实现的复杂性

指令集架构是对 CPU 硬件的抽象，使用这个抽象，CPU 看起来好像一次只执行机器代码程序的一条指令，实际上底层硬件并行地执行多条指令。

虚拟机是对整个计算机系统的抽象，包括操作系统、处理器和程序。

第二章 信息的表示和处理

• 现代计算机存储和处理的信息以二值信号表示。二值信号能够很容易地被表示、存储和传输。
• 单个的位不是非常有用。然而，当把位组合在一起，再加上某种解释(interpretation，也可以说是所谓的上下文)，即赋予不同的可能位模式以含意，我们就能够表示任何有限集合的元素。
• 三种最重要的数字表示
  • **无符号(unsigned)**编码基于传统的二进制表示法，表示大于或者等于零的数字。
  • **补码(two’s-complement)**编码是表示有符号整数的最常见的方式，有符号整数就是可以为正或者为负的数字。
  • **浮点数(floating-point)**编码是表示实数的科学记数法的以 2 为基数的版本
• 计算机数字表示中可能存在的问题
  • 当结果太大以至不能表示时，某些运算就会溢出(overflow)。
  • 整数的表示虽然只能编码一个相对较小的数值范围，但是这种表示是精确的；而浮点数虽然可以编码一个较大的数值范围，但是这种表示只是近似的。

信息存储

• 大多数计算机使用 8 位的块，或者字节(byte)，作为最小的可寻址的内存单位，而不是访问内存中单独的位。
• 机器级程序将内存视为一个非常大的字节数组，称为虚拟内存(virtual memory)。
• 内存的每个字节都由一个唯一的数字来标识，称为它的地址(address)，所有可能地址的集合就称为虚拟地址空间(virtual address space)。
  • 这个虚拟地址空间只是一个展现给机器级程序的概念性映像，是将动态随机访问存储器(DRAM )、闪存、磁盘存储器、特殊硬件和操作系统软件结合起来，为程序提供一个看上去统一的字节数组。
• 编译器和运行时系统将存储器空间划分为更可管理的单元，来存放不同的程序对象(program object)，即程序数据、指令和控制信息。

十六进制数表示

• 一个字节由 8 位组成。在二进制表示法中，它的值域是00000000 ~ 11111111。如果看成十进制整数，它的值域就是0 ~ 255。两种符号表示法对于描述位模式来说都不是非常方便。二进制表示法太冗长，而十进制表示法与位模式的互相转化很麻烦。替代的方法是，以 16 为基数，或者叫做十六进制(hexadecimal)数，来表示位模式。

• 十六进制（简写为"hex")使用数字 ‘0’ ~ ‘9’ 以及字符 ‘A’ ~ ‘F’ 来表示 16 个可能的值。一个字节的值域为 00 ~ FF。在 C 语言中，以 0x 或 0X 开头的数字常量被认为是十六进制的值。

  

• 比如，假设给你一个数字0x173A4C 。可以通过展开每个十六进制数字，将它转换为二进制格式。

  

• 反过来，如果给定一个二进制数字1111001010110110110011，可以通过首先把它分为每 4 位一组来转换为十六进制。不过要注意，如果位总数不是 4 的倍数，最左边的一组可以少于 4 位，前面用 0 补足。然后将每个 4 位组转换为相应的十六进制数字：

  

字数据大小

• 每台计算机都有一个字长(word size)，指明指针数据的标称大小(nominal size)。

• 因为虚拟地址是以这样的一个字来编码的，所以字长决定的最重要的系统参数就是虚拟地址空间的最大大小

  • 32位机器的虚拟地址空间为 4GB，64 位字长的虚拟地址空间位 16EB。

• 大多数 64 位机器也可以运行为 32 位机器编译的程序，这是一种向后兼容。

  • 我们将程序称为"32位程序”或"64位程序”时，区别在于该程序是如何编译的，而不是其运行的机器类型。
  • int32_t 和 int64_t 类型分别为 4 字节和 8 字节，不受机器影响。使用确定大小的整数类型很有用。

• C 语言支持整数和浮点数的多种数据格式。这部分可以看C中的数据类型。

  

• 程序员应该力图使他们的程序在不同的机器和编译器上可移植。可移植性的一个方面就是使程序对不同数据类型的确切大小不敏感。

字节顺序

• 对于跨越多字节的程序对象，我们必须建立两个规则：这个对象的地址是什么，以及在内存中如何排列这些字节。

• 在几乎所有的机器上，多字节对象被存储为连续的字节序列，对象的地址为所使用字节中最小的地址。

  • 例如，假设一个类型为 int 的变量 x 的地址为 0x100，也就是说，地址表达式 &x 的值为 0x100。那么，(假设数据类型int为32 位表示) x 的 4 个字节将被存储在内存的 0x100、0x101 、0x102 和 0x103 位置。

• 排列表示一个对象的字节有两个通用的规则

  • 某些机器选择在内存中按照从最低有效字节到最高有效字节的顺序存储对象，称为小端法(little endian)。
  • 另一些机器则按照从最高有效字节到最低有效字节的顺序存储，称为大端法(big endian)。
  • 大多数 Intel 兼容机都只用小端模式。另一方面，IBM 和 Oracle(从其 2010 年收购 Sun Microsystems 开始）的大多数机器则是按大端模式操作。
  
  • 许多比较新的微处理器是双端法(bi-endian)，也就是说可以把它们配置成作为大端或者小端的机器运行。然而，实际情况是：一旦选择了特定操作系统，那么字节顺序也就固定下来。
  • 对于大多数应用程序员来说，其机器所使用的字节顺序是完全不可见的。无论为哪种类型的机器所编译的程序都会得到同样的结果。

• 字节顺序什么时候会产生影响

  • 当小端法机器产生的数据被发送到大端法机器或者反过来时，接收程序会发现，字里的字节成了反序的。网络应用程序的代码编写必须遵守已建立的关于字节顺序的规则，以确保发送方机器将它的内部表示转换成网络标准，而接收方机器则将网络标准转换为它的内部表示。
  • 阅读表示整数数据的字节序列时字节顺序也很重要。这通常发生在检查机器级程序时。
  • 当编写规避正常的类型系统的程序时。比如在 C 语言中，可以通过使用强制类型转换(cast) 或联合(union)来允许以一种数据类型引用一个对象

表示字符串

• C 语言中字符串被编码为一个以null(其值为0)字符结尾的字符数组。为了防止转义，一般写为'\0'。
• 在使用 ASCII 码作为字符码的任何系统上都将得到相同的结果，与字节顺序和字大小规则无关。因而，文本数据比二进制数据具有更强的平台独立性。

表示代码

• 不同的机器类型使用不同的且不兼容的指令和编码方式。即使是完全一样的进程，运行在不同的操作系统上也会有不同的编码规则，因此二进制代码是不兼容的。二进制代码很少能在不同机器和操作系统组合之间移植。
• 计算机系统的一个基本概念就是，从机器的角度来看，程序仅仅只是字节序列。机器没有关于原始源程序的任何信息，除了可能有些用来帮助调试的辅助表以外。

布尔代数

• 将逻辑值TRUE(真)和FALSE(假)编码为二进制值 1 和 0，能够设计出一种代数，以研究逻辑推理的基本原则，这就是布尔代数。
• 布尔代数可以用来设计和分析机电继电器网络，进而可以使用计算机进行布尔运算。
• 在大量实际应用中，我们都能看到用位向量来对集合编码。Linux有很多不同的信号会中断程序执行。我们能够通过指定一个位向量掩码，有选择地使能或是屏蔽一些信号，其中某一位位置上为1 时，表明信号 1 是有效的（使能），而 0 表明该信号是被屏蔽的。因而，这个掩码表示的就是设置为有效信号的集合。

C语言中的位运算

• 位级运算的一个常见用法就是实现掩码运算，这里掩码是一个位模式，表示从一个字中选出的位的集合

C语言中的逻辑运算

• C 语言还提供了一组逻辑运算符 ||、&&和！，分别对应于命题逻辑中的 OR、AND 和 NOT 运算。逻辑运算很容易和位级运算相混淆，但是它们的功能是完全不同的。
• 逻辑运算认为所有非零的参数都表示TRUE，而参数 0 表示 FALSE。它们返回 1 或者 0，分别表示结果为 TRUE 或者为 FALSE
• 逻辑运算符 && 和 || 与它们对应的位级运算 & 和 | 之间第二个重要的区别是，如果对第一个参数求值就能确定表达式的结果，那么逻辑运算符就不会对第二个参数求值。

C语言中的移位运算

• C 语言还提供了一组移位运算，向左或者向右移动位模式

• x<<k：x 向左移动 k 位，丢弃最高的 k 位，并在右端补 k 个 0。

• x>>k

  • 一般而言，机器支持两种形式的右移：逻辑右移和算术右移。

  • 逻辑右移在左端补 k 个 0，算术右移是在左端补 k 个最高有效位的值

    

  • C 语言标准并没有明确定义对于有符号数应该使用哪种类型的右移————算术右移或者逻辑右移都可以。然而，实际上几乎所有的编译器／机器组合都对有符号数使用算术右移。另一方面，对于无符号数，右移必须是逻辑的。

• 移位的k很大时会发生什么

  • 对于一个由 w 位组成的数据类型，如果要移动 k ≥ w 位会得到什么结果呢。
  • C 语言标准很小心地规避了说明在这种情况下该如何做。在许多机器上，当移动一个 w 位的值时， 移位指令只考虑位移量的低 $log_2w$ 位， 因此实际上位移量就是通过计算 k mod w 得到的。
  • 不过这种行为对于 C 程序来说是没有保证的，所以应该保持位移量小于待移位值的位数。另一方面，Java 特别要求位移数量应该按照我们前面所讲的求模的方法来计算。

在许多机器上当对 k 移动一个 w 位的值时，实际上位移量就是通过计算k mod w得到的。当 int 为 w=32 时，移动 w=36 是，实际上移动4位，这种方法对java有效，对c无效

整数表示

整数数据类型

• 用位来编码整数的两种不同的方式：**一种只能表示非负数，而另一种能够表示负数、零和正数。**它们在数学属性和机器级实现方面密切相关。
• 扩展或者收缩一个已编码整数以适应不同长度表示的效果。

操作术语

• 整数的算数操作术语

  

整型数据类型

• C 语言支持多种整型数据类型表示有限范围的整数。

• 每种类型都能用关键字来指定大小，这些关键字包括 char、short、long，同时还可以指示被表示的数字是非负数(声明为unsigned)，或者可能是负数（默认）。

• 下面展示了32位或64位程序上的取值范围，这里给出来的唯一一个与机器相关的取值范围是大小指示符long，大多数 64 位机器使用 8 个字节的表示，比 32 位机器上使用的 4 个字节的表示的取值范围大很多。

  

• C 语言标准定义了每种数据类型必须能够表示的最小的取值范围

  • 它们的取值范围与典型实现一样或者小一些。

  • 特别地，除了固定大小的数据类型是例外，我们看到它们只要求正数和负数的取值范围是对称的。

    

C 和 C++ 都支持有符号（默认）和无符号数。Java 只支持有符号数。

无符号数和有符号数的编码

无符号数的编码

• 假设有一个整数数据类型有 w 位。我们可以将位向量写成 $\overrightarrow{x}$ 表示整个向量，或者写成 $[x_{w-1},x_{w-2},\cdots,x_0]$ 表示向量中的每一位。把 $\overrightarrow{x}$ 看做一个二进制表示的数，就获得了 $\overrightarrow{x}$ 的无符号表示。

• 在这个编码中，每个位 x，都取值为 0 或 1，后一种取值意味着数值 $2^i$ 应为数字值的一部分。我们用一个函数 $B2U_w$(Binary to Unsigned 的缩写，长度为w)来表示：

  原理：无符号数编码的定义

  对向量 $\overset{\rightarrow}{x}=[x_{w-1},x_{w-2},\cdots,x_0]$ ：

  $$\begin{aligned} B2U_w(\overset{\rightarrow}{x})\doteq\sum_{i=0}^{w-1}x_i2^i\\ \end{aligned} \tag{2.1}$$

  在这个等式中，符号 $\doteq$ 表示左边被定义为等于右边。函数 $B2U_w$ 将一个长度为 w 的 0、1 串映射到非负整数。举例，下图展示的是下面几种情况下 $B2U_w$ 给出的从位向量到整数的映射：

  $$B2U_4([0001])=0\cdot2^3+0\cdot2^2+0\cdot2^1+1\cdot2^0=0+0+0+1=1\\ B2U_4([0101])=0\cdot2^3+1\cdot2^2+0\cdot2^1+1\cdot2^0=0+4+0+1=5\\ B2U_4([1011])=1\cdot2^3+0\cdot2^2+1\cdot2^1+1\cdot2^0=8+0+2+1=11\\ B2U_4([1111])=1\cdot2^3+1\cdot2^2+1\cdot2^1+1\cdot2^0=8+1+2+1=15 \tag{2.2}$$

  

• w 位所能表示的值的范围。最小值是用位向量 [00…0] 表示，即整数值 0，而最大值是用位向量 [11…1] 表示，即整数值 $2^w-1$。因此，函数 $B2U_w$ 能够被定义一个映射 $B2U_w$：$\{0, 1\}^w\rightarrow{0,\cdots, 2^w-1}$

• 无符号数的二进制表示有一个很重要的属性，也就是每个介于 $0\sim2^w-1$ 之间的数都有唯一一个 w 位的值编码。

• 无符号数编码有唯一性，函数 $B2U_w$ 是一个双射。

补码编码

• 对于负数值，最常见的有符号数的计算机表示方式就是补码(two’s-complement)形式。在这个定义中，将字的最高有效位解释为负权(negative weight)。我们用函数 $B2T_w$(Binary to Two’s-complement 的缩写，长度为w)来表示：

  原理：补码编码的定义

  对向量 $\overset{\rightarrow}{x}=[x_{w-1},x_{w-2},\cdots,x_0]$ :

  $$B2T_w(\overset{\rightarrow}{x})\doteq-x_{w-1}2^{w-1}+\sum_{i=0}^{w-2}x_i2^i \tag{2.3}$$

  最高有效位 $x_{w-1}$ 也称为符号位，它的 权重 为 $-2^{w-1}$ ，是无符号表示中权重的负数。符号位被设置为1时，表示值为负，而当设置为0时，值为非负。这里来看一个示例展示的是下面几种情况下 $B2T_w$ 给出的从位向量到整数的映射。

  $$B2T_4([0001])=-0\cdot2^3+0\cdot2^2+0\cdot2^1+1\cdot2^0=0+0+0+1=1\\ B2T_4([0101])=-0\cdot2^3+1\cdot2^2+0\cdot2^1+1\cdot2^0=0+4+0+1=5\\ B2T_4([1011])=-1\cdot2^3+0\cdot2^2+1\cdot2^1+1\cdot2^0=-8+0+2+1=-5\\ B2T_4([1111])=-1\cdot2^3+1\cdot2^2+1\cdot2^1+1\cdot2^0=-8+1+2+1=-1 \tag{2.4}$$

  

  无符号数编码和补码编码的不同之处在于最高位的权重不同。无符号数编码的最高位权重为 $2^{w-1}$ ，补码编码最高位权重为 $-2^{w-1}$ 。

• w 位补码所能表示的值的范围。它能表示的最小值是位向量[10…0]（也就是设置这个位为负权，但是清除其他所有的位），其整数值为 $-2^{w-1}$。而最大值是位向量[01…1]（清除具有负权的位，而设置其他所有的位），其整数值为 $2^{w-1}-1$

• $B2T_w$ 范围是 $(-2^{w-1}, 2^{w-1}-1)$ ，即 $TMin_w$ 到 $TMax_w$ ，从位向量到整数的映射写作： $\{0, 1\}^w \rightarrow \{-2^{w-1},\cdots,2^{w-1}-1\}$。

• 补码编码有唯一性，函数 $B2T_w$ 是一个双射。

整数编码中的要点

• 针对不同字长，几个重要数字的位模式和数值。

  

• 补码的范围是不对称的： $|TMin| = |TMax| + 1$，也就是说，$TMin$ 没有与之对应的正数。

  • 这导致了补码运算的某些特殊的属性，并且容易造成程序中细微的错误。
  • 之所以会有这样的不对称性，是因为一半的位模式（符号位设置为 1 的数）表示负数，而另一半（符号位设置为 0 的数）表示非负数。因为 0 是非负数，也就意味着能表示的正数比负数少一个。

• 最大的无符号数值刚好比补码的最大值的两倍大1：$UMax_w=2TMax_w+1$。

• C 语言标准并没有要求要用补码形式来表示有符号整数，但是几乎所有的机器都是这么做的。

  • 如果希望代码具有最大可移植性，能够在所有可能的机器上运行，那么除了规定位数的补码的表示范围，我们不应该假设任何可表示的数值范围，也不应该假设有符号数会使用何种特殊的表示方式
  • C 库中的文件 ＜limits.h> 定义了一组常量，来限定编译器运行的这台机器的不同整型数据类型的取值范围。
  • C 库头文件 <stdint.h> 中定义了 uint16_t，int32_t 等类型，用于声明确定宽度类型的整数。

• 关于整数数据类型的取值范围和表示，Java 标准是非常明确的。它要求采用补码表示，保证无论在什么机器上运行，Java 程序都能表现地完全一样。

  

整数的类型转换

有符号数和无符号数之间的转换

• C 语言允许在各种不同的数字数据类型之间做强制类型转换。

• 对于在两种形式中都能表示的值，我们是想要保持不变的

• 如果是将负数转换成无符号数，或者转换的无符号数太大以至于超出了补码能够表示的范围会发生什么？

  • 对于大多数 C 语言的实现，处理同样字长的有符号数和无符号数之间相互转换的一般规则是：数值可能会改变，但是位模式不变
  • 也就是说，在进行等长的有符号数和无符号数之间的类型转换时，底层的二进制码是不变的，即二进制不变，解释方式不同。

• 定位模式的补码与无符号数之间的关系

  • 原理：补码转换为无符号数

    对满足 $TMin_w\le x\le TMax_w$ 的 x 有：

    $$T2U_w(x)= \begin{cases}x+2^w&,x\lt0\\x&,x\ge0\end{cases} \tag{2.5}$$

    比如，我们看到 $T2U_{16}(-12345)=-12345+2^{16}=53191$，同时$T2U_{w}(-1)=-1+2^w$ $=UMax_w$ 。

  • 推导：补码转换为无符号数

    比较等式(2.1)和等式(2.3)，我们可以发现对于位模式，如果我们计算 $B2U_w(\overset{\rightarrow}{x})-B2T_w(\overset{\rightarrow}{x})$ 之差，从 0 到 w-2 的位的加权和将互相抵消掉，剩下一个值$B2U_w(\overset{\rightarrow}{x})-B2T_w(\overset{\rightarrow}{x})=$ $x_{w-1}(2^{w-1}-(-2^{w-1}))=x_{w-1}2^w$ 。这就得到一个关系： $B2U_w(\overset{\rightarrow}{x})=x_{w-1}2^w+B2T_w(\overset{\rightarrow}{x})$ 。我们因此就有

    $$B2U_w(T2B_w(x))=T2U_w(x)=x+x_{w-1}2^w \tag{2.6}$$

    在x的补码表示中，位 $x_{w-1}$ 决定了 x 是否为负。

  • 实际上，如果有符号数的负数转换为无符号数时，其最高位的权重 $2^{w-1}$ 由负变正，相当于增加了 $2^{w}$。

    

• 原理：无符号数转换为补码

  对满足 $0\le u\le UMax_w$ 的 u 有：

  $$U2T_w(u)= \begin{cases}u&,u\le TMax_w\\u-2^w&,u\gt TMax_w\end{cases} \tag{2.7}$$

  推导：无符号数转换为补码
  设 $\overset{\rightarrow}{u}=U2B_w(u)$，这个位向量也是 $U2T_w(u)$ 的补码表示。公式(2.1)和公式(2.3)结合起来有

  $$U2T_w(u)=B2T_w(U2B_w(u))=-u_{w-1}2^w+u \tag{2.8}$$

• 总之，补码转为无符号数，负数跳变；无符号数转为补码，$(2^{w-1}, 2^{w})$ 跳变。

  

• 在运算时如果有任何一个运算数是无符号的，那么在比运算前，另一个运算数会被强制类型转换为无符号数。

• $TMin_{32}$ 写成 -2147483647-1。为什么不简单地写成 -2147483648 或者 0x80000000?

  回答

扩展一个数字的位表示

• 一个常见的运算是在不同字长的整数之间转换，同时又保持数值不变。当然，当目标数据类型太小以至于不能表示想要的值时，这根本就是不可能的。然而，从一个较小的数据类型转换到一个较大的类型，应该总是可能的。

• 要将一个无符号数转换为一个更大的数据类型，我们只要简单地在表示的开头添加0 。这种运算被称为零扩展(zero extension)

• 原理：无符号数的零扩展

  定义宽度为 w 的位向量 $\overset{\rightarrow}{u}=[u_{w-1},u_{w-2},\cdots,u_0]$ 和宽度为 w’ 的位向量 $\overset{\rightarrow}{u}'=[0,\cdots,0,$ $u_{w-1},u_{w-2},\cdots,u_0]$ ，其中 w’>w 。则 $B2U_w(\overset{\rightarrow}{u})=B2U_{w'}(\overset{\rightarrow}{u}')$ 。

• 要将一个补码数字转换为一个更大的数据类型，可以执行一个符号扩展(sign extension), 在表示中添加最高有效位的值。

• 原理：补码数的符号扩展

  定义宽度为 w 的位向量 $\overset{\rightarrow}{x}=[x_{w-1},x_{w-2},\cdots,x_0]$ 和宽度为 w’ 的位向量 $\overset{\rightarrow}{x}'=[{\color{Red}x_{w-1} },\cdots,{\color{Red}x_{w-1} },$ ${\color{Red}x_{w-1} },x_{w-2},\cdots,x_0]$ ，其中 w’>w。则 $B2T_w(\overset{\rightarrow}{x})=B2T_{w'}(\overset{\rightarrow}{x}')$ 。

• 相同的二进制表示 $\overrightarrow{x}$ 在 16 位字长时是相同的，但是在 32 位字长时却可能是不同的。这种情况出现在其对应的有符号数为负数的情况。

  • -12345 的补码表示和 53191 的无符号表示在 16 位字长时是相同的，但是进行扩展到32位时，有符号数扩展的是1，无符号数扩展的是0

    

• 为什么符号扩展要补符号位？

  • 以从w=3到4为例，最高两位的组合权重从 $-2^3$ 变成了 $-2^4+2^3$ ，没有发生变化
  • 因此符号扩展一位保持了数值不变，那么符号扩展任意位都能保持这种属性
  

• 从一个数据大小到另一个数据大小的转换，以及无符号和有符号数字之间的转换的相对顺序能够影响一个程序的行为。

  
  • 在大端机器上的输出为ff ff cf c7
  • 当把 short 转换成 unsigned 时，我们先要改变大小，之后再完成从有符号到无符号的转换。这个规则是 C 语言标准要求的。
  • 也就是说 (unsigned)sx 等价于 (unsigned)(int)sx，而不等价于 (unsigned)(unsigned short) sx

截断数字

• 当从较大范围的整数转换为较小范围的整数时，不用额外的位来扩展一个数值，而是减少表示一个数字的位数。

• 当将一个 w 位的数 $\overrightarrow{x}= [x_{w- 1}, x_{w-2},...， x_0]$ 截断为一个 k 位数字时，我们会丢弃高 w-k 位，得到一个位向量$\overrightarrow{x}'= [x_{k- 1}, x_{k-2},...， x_0]$。截断一个数字可能会改变它的值————溢出的一种形式。对于一个无符号数，我们可以很容易得出其数值结果。

• 原理：截断无符号数

  令 $\overrightarrow{x}$ 等于位向量 $[x_{w- 1}, x_{w-2},...， x_0]$，而 $\overrightarrow{x}'$ 是将其截断为 k 位的结果：$\overrightarrow{x}=[x_{k-1},x_{k-2},\cdots,x_0]$ 。令 $x=B2U_w(\overrightarrow{x}),x'=B2U_k(\overrightarrow{x}')$ 。则 $x'=x\ {\rm mod}\ 2^k$。

• 补码截断也具有相似的属性，只不过要将最高位解释为符号位

• 原理：截断补码数值

  令 $\overrightarrow{x}$ 等于位向量 $[x_{w- 1}, x_{w-2},...， x_0]$，而 $\overrightarrow{x}'$ 是将其截断为 k 位的结果：$\overrightarrow{x}=[x_{k-1},x_{k-2},\cdots,x_0]$ 。令 $x=B2U_w(\overrightarrow{x}),x'=B2U_k(\overrightarrow{x}')$ 。则 $x'=U2T_k(x\ {\rm mod}\ 2^k)$。

有关无符号数和有符号数类型转换的建议

• **有符号数到无符号数的隐式强制类型转换导致了某些非直观的行为。**而这些非直观的特性经常导致程序错误，并且这种包含隐式强制类型转换的细微差别的错误很难被发现。因为这种强制类型转换是在代码中没有明确指示的情况下发生的
• 有符号数到无符号数的隐式转换，会导致错误或者漏洞的方式。避免这类错误的一种方法就是绝不使用无符号数。实际上，除了 C 以外很少有语言支持无符号整数。
• 当我们想要把字仅仅看做是位的集合而没有任何数字意义时，无符号数值是非常有用的。

整数运算

• 在整数运算时会出现两个正数相加会得出一个负数，而比较表达式x<y和比较表达式x-y<0会产生不同的结果。这些属性是由于计算机运算的有限性造成的。

• 计算机执行的“整数”运算实际上是一种模运算形式。表示数字的有限字长限制了可能的值的取值范围，结果运算可能溢出。

• 补码使用了与执行无符号算术相同的位级实现，这些运算包括像加法、减法、乘法，甚至除法，无论运算数是以无符号形式还是以补码形式表示的，都有完全一样或者非常类似的位级行为。

加法

无符号加法

• 考虑两个非负整数 x 和 y，满足 $0\le x, y<2^w$ 。每个数都能表示为 w 位无符号数字。然而，如果计算它们的和，我们就有一个可能的范围 $0\le x+y\le2^{w+1}-2$ 。表示这个和可能需要 w+1 位。

• 以此类推。这种持续的 字长膨胀 意味着，要想完整地表示算术运算的结果，我们不能对字长做任何限制。一些编程语言，例如Lisp, 实际上就支持无限精度的运算。

• 更常见的是，编程语言支持固定精度的运算，因此像 加法 和 乘法 这样的运算不同千它们在整数上的相应运算。

• 我们定义参数x和y的无符号加法为 $+^u_w$ ，x 和 y，满足 $0<=x, y<2^w$ ，该操作是把整数和 x+y 截断为 w 位得到的结果，再把这个结果看做是一个无符号数。

  • 可以被视为一种形式的模运算，对 x+y 的位级表示，简单丢弃任何权重大于 $2^{w-1}$ 的位就可以计算出和模 $2^w$

• 我们可以将操作 $+^u_w$ 出描述为：

  对满足 $0\le x,y\lt2^w$ 的x和y有：

  $$x+^u_wy=\begin{cases}x+y,&x+y\lt2^w&正常\\x+y-2^w,&2^w\le x+y\lt2^{w+1}&溢出\end{cases} \tag{2.11}$$

• 正常情况下 x+y 的值保持不变，而溢出情况则是该和数减去 $2^w$ 的结果。说一个算术运算溢出，是指完整的整数结果不能放到数据类型的字长限制中去。

  

• 当执行 C 程序时，不会将溢出作为错误而发信号。不过有的时候，我们可能希望判定是否发生了溢出。

• 原理：检测无符号数加法中的溢出

  对在范围 $0\le x,y\le UMax_w$ 中的 x 和 y，令 $s\doteq x+_w^uy$ 。则对计算s，当且仅当 $s\lt x$ (或者等价地 $s\lt y$ )时，发生了溢出。

  推导：当s没有溢出容易判断 $s\ge x,y$ ，否则 $s=x+y-2^w$ ，假设 $y\lt2^w$ ，于是有 $s=x+(y-2^w)\lt x$

• 模数加法形成了一种数学结构，称为阿贝尔群(Abelian group)，也就说，它是可交换的。它有一个单位元0, 并且每个元素有一个加法逆元。让我们考虑 w 位的无符号数的集合，执行加法运算 $+^u_w$ 。对于每个值x，必然有某个值 $-^u_wx$ 满足 $-x^u_w+x^u_w=0$ 。该加法的逆操作可以表述如下：

  原理：无符号数求反

  对满足 $0\le x\lt2^w$ 的任意x，其w位的无符号逆元 $-^u_wx$ 由下式给出：

  $$-^u_wx=\begin{cases}x,&x=0\\2^w-x,&x\gt 0\end{cases} \tag{2.12}$$

补码加法

• 对于补码加法，我们必须确定当结果太大（为正）或者太小（为负）时，应该做些什么。

• 给定在范围 $-2^{w-1}0\le x, y\le2^{w-1}-1$ 之内的整数值 x 和 y，它们的和就在范围 $-2^{w}\le x+y$ $\le2^{w}-2$ 之内，要想准确表示，可能需要 w+1 位。就像以前一样，我们通过将表示截断到 w 位，来避免数据大小的不断扩张。

• 原理：补码加法

  对满足 $-2^{w-1}\le x,y\le2^{w-1}-1$ 的整数x和y，有：

  $$x+^t_wy= \begin{cases} x+y-2^w,&2^{w-1}\le x+y&正溢出\\ x+y,&-2^{w-1}\le x+y\lt2^{w-1}&正常\\ x+y+2^w,&x+y<-2^{w-1}&负溢出 \end{cases} \tag{2.13}$$

• 当和 x+y 超过 $TMax_w$ 时（情况4)，我们说发生了正溢出。在这种情况下，截断的结果是从和数中减去 $2^w$ 。

• 当和 x+y 小于 $TMin_w$ 时（情况1)，我们说发生了负溢出。在这种情况下，截断的结果是从和数中加上 $2^w$ 。

  

两个数的 w 位补码之和与无符号之和有完全相同的位级表示。实际上，大多数计算机使用同样的机器指令来执行无符号或者有符号加法。

• 如何检测是否产生溢出，产生了何种溢出呢？

• 正溢出的结果是负数，负溢出的结果是正数。

• 原理：检测补码加法中的溢出

  对满足 $TMin_w\le x,y\le TMax_w$ 的x和y，令 $s\doteq x+^t_wy$ 。当且仅当 $x\gt0,y\gt0$ ，但 $s\le0$ 时，计算s发生了正溢出。当且仅当 $x<0,y<0$ ，但 $s\ge0$ 时，计算s发生了负溢出。

补码的非

• 可以看到范围在 $TMin_w<=x<=TMax_w$ 中的每个数字 x 都有 $+^t_w$ 下的加法逆元，我们将 $-^t_wx$ 表示如下。

• 原理：补码的非

  对满足 $TMin_w<=x<=TMax_w$ 的x，其补码的非 $-^t_wx$ 由下式给出

  $$-^t_wx= \begin{cases} TMin_w,&x=TMin_w\\ -x,&x>TMin_w \end{cases} \tag{2.15}$$

  也就是说，对 w 位的补码加法来说， $TMin_w$ 是自己的加法的逆，而对其他任何数值 x 都有 -x 作为其加法的逆。

  推导：补码的非

  观察发现 $TMin_w+TMin_w=-2^{w-1}+(-2^{w-1})=-2^w$ 。这将导致负溢出，因此（负溢+$2^w$） $TMin_w+^t_wTMin_w=-2^w+2^w=0$ 。对满足 $x>TMin_w$ 的 x，数值 -x 可以表示为一个w位的补码，它们的和 $-x+x=0$ 。

• 补码的非求法

  执行位级补码非的笫一种方法是对每一位求补，再对结果加1 。在 C 语言中，我们可以说，对于任意整数值x，计算表达式 -x 和 ~x+1 得到的结果完全一样。

  计算一个数 x 的补码非的第二种方法是建立在将位向量分为两部分的基础之上的。假设 k 是最右边的 1 的位置，因而 x 的位级表示形如 $[x_{w-1},x_{w-2},\cdots,x_{k+1},1,0,\cdots,0]$ 。(只要 $x\neq0$ 就能够找到这样的k。)这个值的非写成二进制格式就是 $[\sim x_{w-1},\sim x_{w-2},\cdots,\sim x_{k+1},1,0,\cdots,0]$ 。也就是对位 k 左边的所有位取反。

乘法

无符号乘法

• 范围在 $0\le x,y\le 2^w-1$ 内的整数 x 和 y 可以被表示为 w 位的无符号数，但是它们的乘积 $x\cdot y$ 的取值范围为 0 到 $(2^w -1)^2 = 2^{2w}-2^{w+1}+1$ 之间。这可能需要 2w 位来表示。

• 不过，C 语言中的无符号乘法被定义为产生 w 位的值，就是 2w 位的整数乘积的低 w 位表示的值。我们将这个值表示为 $x*^t_wy$ 。

• 将一个无符号数截断为 w 位等价于计算该值模 $2^w$，得到：

  原理：无符号数乘法

  对满足 $0\le x,y\le UMax_w$ 的x和y有：

  $$x*^u_wy=(x\cdot y){\rm mod}\ 2^w \tag{2.16}$$

• 具体的，使用无符号数的乘法，就是像十进制的乘法一样，按位相乘，移位相加。

补码乘法

• 范围在 $-2^{w-1}\le x,y\le 2^{w-1}-1$ 内的整数 x 和 y 可以被表示为 w 位的补码，但是它们的乘积 $x\cdot y$ 的取值范围为 $-2^{w-1}\cdot(2^{w-1}-1)=-2^{2w-2}+2^{w-1}$ 到 $-2^{w-1}\cdot-2^{w-1}=2^{2w-2}$ 之间。要想用补码来表示这个乘积，可能需要 2w 位。

• 然而，C 语言中的有符号乘法是通过将 2w 位的乘积截断为 w 位来实现的。我们将这个数值表示为 $x*^t_wy$。

• 将一个补码数截断为 w 位相当于先计算该值模 $2^w$，再把无符号数转换为补码

  原理：补码乘法

  对满足 $TMin_w\le x,y\le TMax_w$ 的x和y有：

  $$x*_w^ty=U2T((x\cdot y){\rm mod}\ 2^w) \tag{2.17}$$

• 对于无符号和补码乘法来说，虽然完整的乘积的位级表示可能会不同，但是截断后乘积的位级表示是相同的。例：

  

  原理：无符号和补码乘法的位级等价性

  给定长度为 w 的位向量 $\overrightarrow{x}$ 和 $\overrightarrow{y}$ ，用补码形式的位向量表示来定义整数 x 和 y： $x=B2T_w(\overrightarrow{x}),y=B2T_w(\overrightarrow{y})$ 。用无符号形式的位向量表示来定义非负整数 x’ 和 y’： $x'=B2U(\overrightarrow{x}),y'=B2U_w(\overrightarrow{y})$ 。则

  $$T2B_w(x*^t_wy)=U2B_w(x'*^u_wy')$$

  推导：无符号和补码乘法的位级等价性

  根据等式(2.6)，我们有 $x'=x+x_{w-1}2^w$ 和 $y'=y+y_{w-1}2^w$ 。计算这些值的乘积模 $2^w$ 得到以下结果：

  $$\begin{aligned} (x'\cdot y'){\rm mod}\ 2^w&=[(x+x_{w-1}2^w)\cdot(y+y_{w-1}2^w)]{\rm mod}\ 2^w\\ &=[x\cdot y+(x_{w-1}y+y_{w-1}x)2^w+x_{w-1}y_{w-1}2^{2w}]{\rm mod}\ 2^w\\ &=(x\cdot y){\rm mod}\ 2^w \end{aligned} \tag{2.18}$$

  根据等式(2.17)，有 $x*^t_wy=U2T((x\cdot y){\rm mod}\ 2^w)$ ，对等式两边应用操作 $T2U_w$，有：

  $$T2U_w(x*^t_wy)=T2U_w(U2T((x\cdot y){\rm mod}\ 2^w))=(x\cdot y){\rm mod}\ 2^w$$

  将上述结果与式(2.16)和式(2.18)结合起来得到

  $$U2B_w(T2U_w(x*^t_wy))=T2B_w(x*^t_wy)=U2B_w(x'*^u_wy')$$

乘以常数

• 以往，在大多数机器上，整数乘法指令相当慢，需要 10 个或者更多的时钟周期，然而其他整数运算（例如加法、减法、位级运算和移位）只需要 1 个时钟周期。即使在我们的参考机器Intel Core i7 Haswell 上，其整数乘法也需要 3 个时钟周期。

• 因此，编译器使用了一项重要的优化，试着用移位和加法运算的组合来代替乘以常数因子的乘法。首先，我们会考虑乘以 2 的幂的情况，然后再概括成乘以任意常数。

• 原理：乘以2的幂

  设 x 为位模式 $[x_{w-1},x_{w-2},\cdots,x_0]$ 表示的无符号整数。那么给出 $x\cdot2^k$ ，对于任何 $k\ge0$ ，我们可以得到其w+k位的无符号表示 $[x_{w-1},x_{w-2},\cdots,x_0,0,\cdots,0]$ ，这里右边增加了k个0。

• 左移一个数值等价于执行一个与 2 的幂相乘的无符号乘法。

• 原理：与2的幂相乘的无符号乘法

  C变量x和k赋予无符号数值 x 和 k，且 $0\le k\lt w$，则C表达式 $x<<k$ 产生数值 $x*^u_w2^k$ 。

• 由于固定大小的补码算术运算的位级操作与其无符号运算等价，我们就可以对补码运算的 2 的幂的乘法与左移之间的关系进行类似的表述：

• 原理：与2的幂相乘的补码乘法
  C变量x和k有 补码值x 和 无符号数值k，且 $0\le k\lt w$，则C表达式 $x<<k$ 产生数值 $x*^u_w2^k$。

• 无论是无符号运算还是补码运算，乘以 2 的幂都可能会导致溢出。结果表明，即使溢出的时候，我们通过移位得到的结果也是一样的。

• 由于整数乘法比移位和加法的代价要大得多，许多 C 语言编译器试图以移位、加法和减法的组合来消除很多整数乘以常数的情况。

  • 例如，假设一个程序包含表达式 x*14 。利用 $14=2^3+2^2+2^1$，编译器会将乘法重写为 $(x<<3) + (x<<2) + (x<<1)$，将一个乘法替换为三个移位和两个加法。
  • 无论 x 是无符号的还是补码，甚至当乘法会导致溢出时，两个计算都会得到一样的结果。（根据整数运算的属性可以证明这一点。）
  • 更好的是，编译器还可以利用属性 $14=2^4 -2^1$ 将乘法重写为 $(2<<4) -(x<<1)$，这时只需要两个移位和一个减法

• 考虑一个任务，对于某个常数 K 的表达式 x*K 生成代码。编译器会将 K 的二进制表示表达为一组 0 和 1 交替的序列：

  [(0···0) (1···1) (0···0)···(1···1)]

  • 如 14 可以写成[(0···0)(111)(0)]。考虑一组从位位置 n 到位位置 m 的连续的1($n\ge m$)。（对于 14 来说，我们有 n=3 和 m=1 )
  • 我们可以用下面两种不同形式中的一种来计算这些位对乘积的影响：
    • 形式A：$(x<<n)+(x<<(n-1))+...+(x<<m)$
    • 形式B：$(x<<(n+1))-(x<<m)$
    • 把每个这样连续的 1 的结果加起来，不用做任何乘法，我们就能计算出 x*K
  • 选择使用移位、加法和减法的组合，还是使用一条乘法指令，取决于这些指令的相对速度，而这些是与机器高度相关的。大多数编译器只在需要少量移位、加法和减法就足够的时候才使用这种优化。

除以2的幂

• 在大多数机器上，整数除法要比整数乘法更慢需要 30 个或者更多的时钟周期。

• 除以 2 的幂也可以用移位运算来实现，只不过用的是右移，而不是左移。无符号和补码数分别使用逻辑移位和算术移位来达到目的。

• 整数除法总是舍入到零。为了准确进行定义，我们要引人一些符号。对于任何实数a，定义 $ \left \lfloor a\right \rfloor$ 为唯一的整数 a’，使得 $a'\le a\lt a'+1$。例如，$ \left \lfloor 3.14\right \rfloor=3$，$ \left \lfloor-3.14\right \rfloor=-4$ 而 $ \left \lfloor 3\right \rfloor=3$。同样，定义 $ \left \lceil a\right \rceil$ 为唯一的整数a’，使得 $a'-1\lt a\le a'$。例如，$ \left \lceil 3.14\right \rceil=4$，$ \left \lceil -3.14\right \rceil=-3$，而 $ \left \lceil 3\right \rceil=3$。对于x≥0和y>0，结果会是 $ \left \lfloor x/y\right \rfloor$，而对于x<0和y>0，结果会是 $ \left \lceil x/y\right \rceil$。也就是说，它将向下舍入一个正值，而向上舍入一个负值。

• 对无符号运算使用移位是非常简单的，部分原因是由于无符号数的右移一定是逻辑右移。

• 原理：除以2的幂的无符号除法

  C变量×和k有无符号数值x和k，且 $0\le k\lt w$，则C表达式 $x>>k$ 产生数值 $ \left \lfloor x/2^k\right \rfloor$。

• 对于除以 2 的幂的补码运算来说，情况要稍微复杂一些。

  • 首先，为了保证负数仍然为负，移位要执行的是 算术右移。

  • 原理：除以2的幂的补码除法，向下舍入

    C变量x和k分别有补码值x和无符号数值k，且 $0\le k\lt w$，则当执行算术移位时，C表达式 $x>>k$ 产生数值 $ \left \lfloor x/2^k\right \rfloor$。

  • 这种操作，在x是负数且需要舍入时会进行向下舍入，而我们希望的是向上舍入。

  • 在计算x/y时，通过给原来的值加一个y-1，变成(x+y-1)/y来从向下舍入变为向上舍入

  • 原理：除以2的幂的补码除法，向上舍入

    C变量x和k分别有补码值x和无符号数值k，且 $0\le k\lt w$，则当执行算术移位时，C表达式 $ (x+(1<<k)-1)>>k$ 产生数值 $ \left \lceil x/2^k\right \rceil$。

  • 偏置技术利用如下属性：对于整数x和y(y>0)， $\left\lceil x/y\right\rceil=\left\lfloor (x+y-1)/y\right\rfloor$ 。例如，当 $x=-30$ 和 $y=4$ ，我们有 $x+y-1=-27$ ，而 $\left\lceil -30/4\right\rceil=-7=\left\lfloor -27/4\right\rfloor$ 。当 $x=-32$ 和 $y=4$ 时，我们有 $x+y-1=-29$ ，而 $\left\lceil -32/4\right\rceil=-8=\left\lfloor -29/4\right\rfloor$ 。

  • 最终，对于使用算术右移的补码机器， C 表达式计算x除以2的k次幂的表达式为：$(x<0 ? x+(1<<k)-1 : x)>>k$

• 除以2的幂可以通过逻辑或者算术右移来实现。这也正是为什么大多数机器上提供这两种类型的右移。不幸的是，这种方法不能推广到除以任意常数。同乘法不同，我们不能用除以2的幂的除法来表示除以任意常数K的除法。

浮点数

二进制小数

• 考虑一个形如 $b_mb_{m-1} ...b_1b_0b_{-1}b_{-2}b_{-n-1}b_{-n}$ 的表示法，其中每个二进制数字，或者称为位，$b_i$ 的取值范围是 0 和 1。这种表示方法表示的数b定义如下：

  $$b=\sum_{i=-n}^m2^i\times b_i \tag{2.19}$$

• 符号“.”点，点左边的位的权是 2 的正幂，点右边的位的权是 2 的负幂。

  

• 二进制小数点向左移动一位相当于这个数被 2 除。二进制小数点向右移动一位相当于将该数乘 2。

• 假定我们仅考虑有限长度的编码，那么十进制表示法不能准确地表达像 1/3 和 5/7 这样的数。

  • 类似，小数的二进制表示法只能表示那些能够被写成 $x×2^y$ 的数。其他的值只能够被近似地表示。

  • 数字 1/5 可以用十进制小数 0.20 精确表示。不过，我们并不能把它准确地表示为一个二进制小数，我们只能近似地表示它，增加二进制表示的长度可以提高表示的精度：

    

IEEE浮点表示

• 浮点表示对形如$V=x×2^y$ 的有理数进行编码。它对执行涉及非常大的数字(|V|>>0)、非常接近于0(|V|<<1) 的数字，以及更普遍地作为实数运算的近似值的计算，是很有用的。
  • IEEE 浮点格式中数字是如何表示的。以及舍入(rounding) 的问题，即当一个数字不能被准确地表示为这种格式时，就必须向上调整或者向下调整
  • 讨论加法、乘法和关系运算符的数学属性
• 所有的计算机都支持后来被称为 IEEE 浮点的标准。这大大提高了科学应用程序在不同机器上的可移植性。

IEEE标准

• 定点表示法不能很有效地表示非常大的数字。例如，表达式$5 × 2^{100}$ 是用 101 后面跟随 100 个零的位模式来表示。相反，我们希望通过给定 x 和 y 的值，来表示形如 $V=x×2^y$ 的数。

• IEEE 浮点标准用 $V=(-1)^s× M ×2^E$ 的形式来表示一个数：

  • 符号(sign) s 决定这数是负数(s=1) 还是正数(s=0)，而对于数值0 的符号位解释作为特殊情况处理。
  • 尾数(significand) M 是一个二进制小数，它的范围是1~2-ε， 或者是0~1-ε。
  • 阶码(exponent) E 的作用是对浮点数加权，这个权重是 2 的 E 次幂（可能是负数）。

• 将浮点数的位表示划分为三个字段，分别对这些值进行编码：

  • 一个单独的符号位 s 直接编码符号s 。
  • k 位的阶码字段 $exp=e_{k - 1} ... e_1e_0$。编码阶码E 。
  • n 位小数字段 $frac= f_{n-1}f_1f_0$ 编码尾数M，但是编码出来的值也依赖于阶码字段的值是否等于0 。

• 将这三个字段装进字中两种最常见的格式。

  • 在单精度浮点格式（C 语言中的float）中， s 、exp 和 frac 字段分别为 1 位、k=8 位和 n=23 位，得到一个 32 位的表示。
  • 在双精度浮点格式（C 语言中的double) 中， s 、exp 和 frac 字段分别为 1 位、k=11 位和 n=52 位，得到一个 64 位的表示。
  

编码值的三种情况

• 给定位表示，根据 exp 的值，被编码的值可以分成三种不同的情况（最后一种情况有两个变种）

  

• 情况1：规格化的值

  • 这是最普遍的情况。当 exp 的位模式既不全为0(数值0)，也不全为1(单精度数值为255, 双精度数值为2047)时，都属与这类情况。在这种情况中，阶码字段被解释为以偏置（Based）形式表示的有符号整数。
  • 阶码的值是E=e-Bias，其中 e 是无符号数，其位表示为 $e_{k - 1} ... e_1e_0$，而Bias 是一个等于 $2^{k-1} -1$(单精度是127, 双精度是1023)的偏置值
    • 由此产生指数的取值范围，对于单精度是 -126 ~ +127，而对于双精度是 -1022 ~ +1023 。
  • 小数字段 frac 被解释为描述小数值 f，其中 $0\le f<1$，其二进制表示为 $0.f_{n-1}f_1f_0$，也就是二进制小数点在最高有效位的左边。
    • 尾数定义为 M=1+f。这种方式也叫做隐含的以 1 开头的(implied leading 1)表示，因为我们可以把 M 看成一个二进制表达式为 $1.f_{n-1}f_1f_0$ 的数字。
    • 既然我们总是能够调整阶码 E，使得尾数 M 在范围 $1\le M<2$ 之中（假设没有溢出），那么这种表示方法是一种轻松获得一个额外精度位的技巧。——既然第一位总是等于1，那么我们就不需要显式地表示它。

• 情况2：非规格化的值

  • 当阶码域为全 0 时，所表示的数是非规格化形式。在这种情况下，阶码值是 E=1-Bias，而尾数的值是 M=f，也就是小数字段的值，不包含隐含的开头的1。

  对于非规格化值为什么要这样设置偏置值
  使阶码值为 1-Bias 而不是简单的 -Bias 似乎是违反直觉的。这种方式提供了一种从非规格化值平滑转换到规格化值的方法。

  • 非规格化数有两个用途。首先，它们提供了一种表示数值 0 的方法
    • 因为使用规格化数，我们必须总是使 $M\ge1$，因此我们就不能表示 0
    • 实际上，+0.0 的浮点表示的位模式为全0：符号位是0，阶码字段全为0(表明是一个非规格化值），而小数域也全为0，这就得到 M=f=0 。
    • 当符号位为1，而其他域全为0时，我们得到值-0.0。根据 IEEE 的浮点格式，值+0.0 和-0.0在某些方面被认为是不同的，而在其他方面是相同的。
  • 非规格化数的另外一个功能是表示那些非常接近于0.0的数。它们提供了一种属性，称为逐渐下溢(gradual underflow)，其中，可能的数值分布均匀地接近于0.0

• 情况3: 特殊值

  • 最后一类数值是当指阶码全为 1 的时候出现的。当小数域全为 0 时，得到的值表示无穷，当 s=0 时是正无穷, 或者当 s=1 时是负无穷 。当我们把两个非常大的数相乘，或者除以零时，无穷能够表示溢出的结果
  • 当小数域为非零时，结果值被称为"NaN", 即“不是一个数(Not a Number)”的缩写。一些运算的结果不能是实数或无穷，就会返回这样的NaN值，比如当计算 $\sqrt{-1}$ 或 $\infty-\infty$ 时。在某些应用中，表示未初始化的数据时，它们也很有用处。

数字示例

• 下图图展示了一组数值，它们可以用假定的6位格式来表示，有k=3的阶码位和n=2的尾数位。偏置量是 $2^{3-1}-1=3$ 。图中的a部分显示了所有可表示的值(除了NaN)。两个无穷值在两个末端。最大数量值的规格化数是 $\pm14$。非规格化数聚集在0的附近。图的b部分中，我们只展示了介于-1.0和+1.0之间的数值，这样就能够看得更加清楚了。两个零是特殊的非规格化数。可以观察到，那些可表示的数并不是均匀分布的————越靠近原点处它们越稠密。

• 可以观察到最大非规格化数7/512和最小规格化8/512之间的平滑转变。这种平滑性归功于我们对非规格化数的 E 的定义。通过将E 定义为1-Bias, 而不是-Bias, 我们可以补偿非规格化数的尾数没有隐含的开头的1 。
  • 将 E 定义为 -Bias 的话，非规格化数最大表示就是 $2^{-Bias}*0.1$，与规格化数的最小表示$2^{1-Bias}*1$发生跳变了
• 如果将IEEE浮点数的位表达式解释为无符号整数，它们就是按升序排列的，就像它们表示的浮点数一样。
  • 这不是偶然的，IEEE 格式如此设计就是为了浮点数能够使用整数排序函数来进行排序。
  • 当处理负数时，有一个小的难点，因为它们有开头的1, 并且它们是按照降序出现的，但是不需要浮点运算来进行比较也能解决这个问题

浮点数属性

• 一些重要的单精度和双精度浮点数的表示和数字值。

  

• 有 k 位阶码和 n 位小数的浮点表示的一般属性。

• 值＋0.0总有一个全为0的位表示。

• 最小的正非规格化值的位表示，是由最低有效位为1而其他所有位为О构成的。它具有小数(和尾数)值 $M=f=2^{-n}$ 和阶码值 $E=-2^{k-1}+2$。因此它的数字值是 $V=2^{-n-2^{k-1}+2}$。

• 最大的非规格化值的位模式是由全为0的阶码字段和全为1的小数字段组成的。它有小数(和尾数)值 $M=f=1-2^{-n}$(我们写成1-ε)和阶码值 $E=-2^{k-1}+2$。因此，数值 $V=(1-2^{-n})\times2^{-2^{k-1}+2}$，这仅比最小的规格化值小一点。

• 最小的正规格化值的位模式的阶码字段的最低有效位为1，其他位全为0。它的尾数值M=1，而阶码值 $E=-2^{k-1}+2$。因此，数值 $V=2^{-2^{k-1}+2}$。

• 值1.0的位表示的阶码字段除了最高有效位等于0以外，其他位都等于1。它的尾数值是M=1，而它的阶码值是E=0。

• 最大的规格化值的位表示的符号位为0，阶码的最低有效位等于0，其他位等于1。它的小数值 $f=1—2^{-n}$ ，尾数 $M=2-2^{-n}$ (我们写作1-ε)。它的阶码值 $E=2^{k-1}-1$ ，得到数值 $V=(2-2^{-n})\times 2^{2^{k-1}-1}=(1-2^{-n-1})\times2^{2^{k-1} }$

舍入

• 因为表示方法限制了浮点数的范围和精度，所以浮点运算只能近似地表示实数运算。因此对于值x， 我们一般想用一种系统的方法，能够找到“最接近的”匹配值x’，它可以用期望的浮点形式表示出来。这就是舍入(rounding)运算的任务

• 一个关键问题是在两个可能值的中间确定舍入方向。

• 一种可选择的方法是维持实际数字的下界和上界。例如，我们可以确定可表示的值 $x^+$ 和 $x ^-$，使得x的值位于它们之间：$x ^-\le x\le x^+$。IEEE浮点格式定义了四种不同的舍入方式。默认的方法是找到最接近的匹配，而其他三种可用于计算上界和下界。

  • 向偶数舍入(round-to-even)，也被称为向最接近的值舍入(round- to-nearest)，是默认的方式，试图找到一个最接近的匹配值。
    • 唯一的设计决策是确定两个可能结果中间数值的舍入效果。向偶数舍入方式采用的方法是：它将数字向上或者向下舍入，使得结果的最低有效数字是偶数。
    • 为什么偏向于取偶数？为了防止舍入引入平均值的统计偏差。在 50% 的时间里，它将向上舍入，而在 50% 的时间里，它将向下舍入。
    • **向偶数舍入有两个原则，一是向最接近的值舍入，再一个是当处在"中间值"时看有效数值是否是偶数，如果是偶数则直接舍去不进位，如果是奇数则进位。**例如：逗号前一位为舍入位，例1,10，舍入后为10,00，0,10，舍入后为0,00。
  • 其他三种方式产生实际值的确界(guaranteed bound)。这些方法在一些数字应用中是很有用的。
    • 向零舍入方式把正数向下舍入，把负数向上舍入，得到值 $\hat{x}$，使得 $|\hat{x}\le |x|$。
    • 向下舍入方式把正数和负数都向下舍入，得到值 $x^-$，使得 $x^-\le x$。
    • 向上舍人方式把正数和负数都向上舍入，得到值 $x^+$，满足 $x\le x^+$。

• 向偶数舍入法能够运用在二进制小数上。我们将最低有效位的值0认为是偶数，值1认为是奇数。

  • 一般来说，只有对形如 XX…X.YY…Y100… 的二进制位模式的数，这种舍入方式才有效，其中X和Y表示任意位值，最右边的Y是要被舍入的位置。只有这种位模式表示在两个可能的结果正中间的值。

浮点计算

• IEEE 标准指定了一个简单的规则，来确定诸如加法和乘法这样的算术运算的结果。把浮点值x和y看成实数，而某个运算 $\odot$ 定义在实数上，计算将产生Round($x\odot y$), 这是对实际运算的精确结果进行舍入后的结果
• 在实际中，浮点单元的设计者使用一些小技巧来避免执行这种精确的计算，因为计算只要精确到能够保证得到一个正确的舍入结果就可以了。同时，对特殊值定义了相应的规则。
• IEEE 标准中指定浮点运算行为方法的一个优势在于，它可以独立于任何具体的硬件或者软件实现。因此，我们可以检查它的抽象数学属性，而不必考虑它实际上是如何实现的。
• 实数上的加法也形成了阿贝尔群，但是对于浮点数，我们必须考虑舍入对这些属性的影响。

浮点加法

• 将 $x+^fy$ 定义为Round(x+y)。这个运算的定义针对x和y的所有取值，但是虽然x和y都是实数，由于溢出，该运算可能得到无穷值。
  • 对于所有x和y的值，这个运算是可交换的
  • 作为阿贝尔群，大多数值在浮点加法下都有逆元，无穷和NaN是例外情况
  • 浮点加法不具有结合性，这是缺少的最重要的群属性。这使得避免任何对功能产生影响的优化
  • 浮点加法满足了单调性属性：如果 $a\ge b$ , 那么对于任何a、b以及x的值，除了NaN，都有 $x+a\ge x+b$ 。无符号或补码加法不具有这个实数（和整数）加法的属性。

浮点乘法

• 定义 $x* ^fy$ 为Round($x\times y$) 。这个运算在乘法中是封闭的（虽然可能产生无穷大或NaN)

  • 它是可交换的，而且它的乘法单位元为1.0 。
  • 由于可能发生溢出，或者由于舍入而失去精度，它不具有可结合性。
  • 浮点乘法在加法上不具备分配性

• 另一方面，对于任何a、b和c，并且a、b和c都不等于NaN，浮点乘法满足下列单调性:

  $$a\ge b且c\ge0\Rightarrow a*^fc\ge b*^fc\\ a\ge b且c\le0\Rightarrow a*^fc\le b*^fc$$

  此外，我们还可以保证，只要 $a\neq NaN$，就有 $a*^fa\ge0$。像我们先前所看到的，无符号或补码的乘法没有这些单调性属性。

C语言中的浮点数

• 所有的C 语言版本提供了两种不同的浮点数据类型：float和double。
  • 在支持IEEE浮点格式的机器上。这些数据类型就对应于单精度和双精度浮点。另外，这类机器使用向偶数舍入的舍入方式。
  • 不幸的是，因为C语言标准不要求机器使用IEEE浮点，所以没有标准的方法来改变舍入方式或者得到诸如正无穷、负无穷、-0或者NaN之类的特殊值。
• 当在int、float 和double格式之间进行强制类型转换时，程序改变数值和位模式的原则如下（假设int 是32 位的）：
  • 从int转换成float，数字不会溢出，但是可能被舍入。
  • 从int或float转换成double，因为double有更大的范围（也就是可表示值的范围），也有更高的精度（也就是有效位数），所以能够保留精确的数值。
  • 从double转换成float，因为范围要小一些，所以值可能溢出成正无穷或负无穷。另外，由于精确度较小，它还可能被舍入。
  • 从float或者double转换成int，值将会向零舍入。进一步来说，值可能会溢出。C语言标准没有对这种情况指定固定的结果。
    • 与Intel兼容的微处理器指定位模式 [10…00] (字长为w时的 $TMin_w$) 为整数不确定(integer indefinite)值。一个从浮点数到整数的转换，如果不能为该浮点数找到一个合理的整数近似值，就会产生这样一个值。

第三章 程序的机器级表示

• 计算机执行机器代码，用字节序列编码低级的操作，包括处理数据、管理内存、读写存储设备上的数据，以及利用网络通信。
• 编译器基于编程语言的规则、目标机器的指令集和操作系统遵循的惯例，经过一系列的阶段生成机器代码。GCC C 语言编译器以汇编代码的形式产生输出，汇编代码是机器代码的文本表示，给出程序中的每一条指令。然后 GCC 调用汇编器和链接器，根据汇编代码生成可执行的机器代码。
• 当我们用高级语言编程的时候，机器屏蔽了程序的细节，即机器级的实现。与此相反，当用汇编代码编程的时候，程序员必须指定程序用来执行计算的低级指令。用高级语言编写的程序可以在很多不同的机器上编译和执行，而汇编代码则是与特定机器密切相关的。

x86处理器历史

• Intel 处理器系列俗称x86，经历了一个长期的、不断进化的发展过程。
• 开始时，它是第一代单芯片、16 位微处理器之一，由千当时集成电路技术水平十分有限，其中做了很多妥协。以后，它不断地成长，利用进步的技术满足更高性能和支持更高级操作系统的需求。
• 每个后继处理器的设计都是后向兼容的，较早版本上编译的代码可以在较新的处理器上运行。
• IA32 指的是 Intel 32 位体系结构，x86-64指 IA32 的64位扩展。

下面是一些Intel 处理器的模型，以及它们的一些关键特性，特别是影响机器级编程的特性

• 8086（1978 年，29K 个晶体管）。它是第一代单芯片、16位微处理器之一。8088是 8086 的一个变种，在 8086 上增加了一个 8 位外部总线，构成最初的 IBM 个人计算机的心脏。IBM 与当时还不强大的微软签订合同，开发 MS-DOS 操作系统。最初的机器型号有 32768 字节的内存和两个软驱（没有硬盘驱动器）。从体系结构上来说，这些机器只有 655360 字节的地址空间———地址只有 20 位长（可寻址范围为 1048576 字节），而操作系统保留了 393216 字节自用。1980 年，Intel 提出了 8087 浮点协处理器(45K 个晶体管），它与一个 8086 或 8088 处理器一同运行，执行浮点指令。8087 建立了 x86 系列的浮点模型，通常被称为"x87"

• 80286（1982 年，134K 个品体管）。增加了更多的寻址模式（现在已经废弃了），构成了 IBM PC-AT 个人计算机的基础，这种计算机是 MS Windows 最初的使用平台。

• i386（1985 年，275K 个晶体管）。将体系结构扩展到 32 位。增加了平坦寻址模式(flat addressing model)，Linux 和最近版本的 Windows 操作系统都是使用的这种模式。这是 Intel 系列中第一台全面支持 Unix 操作系统的机器。

• i486（1989 年，1.2M 个晶体管）。改善了性能，同时将浮点单元集成到了处理器芯片上，但是指令集没有明显的改变。

• Pentium（1993 年，3.1M 个晶体管）。改善了性能，不过只对指令集进行了小的扩展。

• PentiumPro（l995 年，5.5M 个晶体管）。引入全新的处理器设计，在内部被称为P6微体系结构。指令集中增加了一类“条件传送(conditional move)”指令。

• Pentium/MMX（1997 年，4.5M 个晶体管）。在 Pentium 处理器中增加了一类新的处理整数向量的指令。每个数据大小可以是1、2或4字节。每个向量总长 64 位。

• Pentium Ⅱ（1997 年，7M 个晶体管）。P6 微体系结构的延伸。

• Pentium Ⅲ（1999 年，8.2M 个晶体管）。引入了SSE，这是一类处理整数或浮点数向量的指令。每个数据可以是1 、2 或4 个字节，打包成 128 位的向量。由于芯片上包括了二级高速缓存，这种芯片后来的版本最多使用了 24M 个晶体管。

• Pentium 4（2000 年，42M 个晶体管）。SSE 扩展到了 SSE2，增加了新的数据类型（包括双精度浮点数），以及针对这些格式的 144 条新指令。有了这些扩展，编译器可以使用 SSE 指令（而不是x87 指令），来编译浮点代码。

• Pentium 4E（2004 年，125M 个品体管）。增加了超线程(hyperthreading)，这种技术可以在一个处理器上同时运行两个程序；还增加了 EM64T，它是 Intel 对 AMD 提出的对 IA32 的 64 位扩展的实现，我们称之为 x86-64 。

• Core 2（2006 年，291M 个晶体管）。回归到类似于 P6 的微体系结构。Intel 的第一个多核微处理器，即多处理器实现在一个芯片上。但不支持超线程。

• Core i7，Nehalem（2008 年，781M 个晶体管）。既支持超线程，也有多核，最初的版本支持每个核上执行两个程序，每个芯片上最多四个核。

• Core i7，Sandy Bridge（2011 年，1.17G 个晶体管）。引入了AVX，这是对 SSE 的扩展，支持把数据封装进 256 位的向量。

• Core i7，Haswell（2013 年，1.4G 个晶体管）。将 AVX 扩展至 AVX2，增加了更多的指令和指令格式。

程序编码

从C语言视角到机器语言视角

• 假设一个C 程序，有两个文件 p1.c 和 p2.c 。我们用 Unix 命令行编译这些代码：

  gcc -Og -o p p1.c p2.c

• 命令 gcc 指的就是 GCC C 编译器，这是 Linux 上默认的编译器，我们也可以简单地用 cc 来启动它。

• 编译选项 -Og 告诉编译器使用会生成符合原始 C 代码整体结构的机器代码的优化等级。使用较高级别优化产生的代码会严重变形，以至于产生的机器代码和初始源代码之间的关系非常难以理解。

• gcc 命令调用了一整套的程序，将源代码转化成可执行代码。

  • 首先，C 预处理器扩展源代码，插入所有用#include命令指定的文件，并扩展所有用#define声明指定的宏
  • 其次，编译器产生两个源文件的汇编代码，名字分别为 p1.s 和 p2.s 。
    • 编译器把用 C 语言提供的相对比较抽象的执行模型表示的程序转化成处理器执行的非常基本的指令。
    • 汇编代码表示非常接近于机器代码。与机器代码的二进制格式相比，汇编代码的主要特点是它用可读性更好的文本格式表示。
  • 接下来，汇编器会将汇编代码转化成二进制目标代码文件 p1.o 和 p2.o 。
    • 目标代码是机器代码的一种形式，它包含所有指令的二进制表示，但是还没有填入全局值的地址。
  • 最后，链接器将两个目标代码文件与实现库函数(例如printf)的代码合并，并产生最终的可执行代码文件 p（由命令行指示符-o p 指定的）
    • 可执行代码是我们要考虑的机器代码的第二种形式，也就是处理器执行的代码格式。

机器级代码

• 对于机器级编程来说，其中两种抽象尤为重要。
  • 第一种是由指令集体系结构或指令集架构(Instruetion Set Arehiteeture，ISA) 来定义机器级程序的格式和行为，它定义了处理器状态、指令的格式，以及每条指令对状态的影响。
    • 大多数ISA，包括x86-64，将程序的行为描述成好像每条指令都是按顺序执行的，一条指令结束后，下一条再开始。
    • 处理器的硬件远比描述的精细复杂，它们并发地执行许多指令，但是可以采取措施保证整体行为与ISA指定的顺序执行的行为完全一致。
  • 第二种抽象是，机器级程序使用的内存地址是虚拟地址，提供的内存模型看上去是一个非常大的字节数组。
• x86-64 的机器代码和原始的 C 代码差别非常大。一些通常对 C 语言程序员隐藏的处理器状态都是可见的（也就是说，机器代码在操作什么）：
  • 程序计数器（通常称为"PC", 在 x86-64 中用 ％rip 表示）。给出将要执行的下一条指令在内存中的地址。
  • 整数寄存器文件。包含 16 个命名的位置，分别存储 64 位的值。
    • 这些寄存器可以存储地址（对应于 C 语言的指针）或整数数据。
    • 有的寄存器被用来记录某些重要的程序状态，而其他的寄存器用来保存临时数据，例如过程的参数和局部变量，以及函数的返回值。
  • **条件码寄存器。**保存着最近执行的算术或逻辑指令的状态信息。它们用来实现控制或数据流中的条件变化，比如说用来实现if和while语句。
  • 一组向量寄存器可以存放一个或多个整数或浮点数值。
• 虽然C语言提供了一种模型，可以在内存中声明和分配各种数据类型的对象，但是机器代码只是简单地将内存看成一个很大的、按字节寻址的数组，并不对数据类型进行区分。
• 程序内存包含：程序的可执行机器代码，操作系统需要的一些信息，用来管理过程调用和返回的运行时栈，以及用户分配的内存块。例如，x86-64 的虚拟地址是由64位的字来表示的。在目前的实现中，这些地址的高16位必须设置为0，所以一个地址实际上能够指定的是 $2^{48}$ 或256TB范围内的一个字节。
• 一条机器指令只执行一个非常基本的操作。例如，将存放在寄存器中的两个数字相加，在存储器和寄存器之间传送数据，或是条件分支转移到新的指令地址。编译器必须产生这些指令的序列，从而实现（像算术表达式求值、循环或过程调用和返回这样的）程序结构。

C语言的机器语言表示示例

代码示例

• 写了一个 C 语言代码文件mstore.c, 包含如下的函数定义：

  long mult2(long, long);
  void multstore(long x, long y, long *dest) {
    long t = mult2(x, y);
    *dest = t;
  }

编译

• 在命令行上使用 -S 选项，就能看到 C 语言编译器产生的汇编代码：

  gcc -Og -S mstore.c

• 这会使 GCC 运行编译器，产生一个汇编文件mstore.s，但是不做其他进一步的工作。（通常情况下，它还会继续调用汇编器产生目标代码文件）。

• 汇编代码文件包含各种声明，包括下面几行：

  multstore:
      pushq     %rbx
      movq      %rdx,    %rbx
      call      mult2
      movq      %rax,   (%rbx)
      popq      %rbx
      ret

• 上面代码中每个缩进去的行都对应于一条机器指令。比如，pushq指令表示应该将寄存器%rbx的内容压入程序栈中。这段代码中已经除去了所有关于局部变量名或数据类型的信息。

• 在实际中以 . 开头的行都是指导汇编器和链接器工作的伪指令。我们通常可以忽略这些行。

  

汇编

• 如果我们使用 -c 命令行选项，GCC 会编译并汇编该代码：

  gcc -Og -c mstore.c

  这就会产生目标代码文件mstore.o，它是二进制格式的，所以无法直接查看。

• mstore.o 中有一段 14 字节的序列，它的十六进制表示为：

  53 48 89 d3 e8 00 00 00 00 48 89 03 5b c3

  • 这就是上面列出的汇编指令对应的目标代码，从中得到一个重要信息，即机器执行的程序只是一个字节序列，它对产生这些指令的源代码几乎一无所知。

  • 要展示程序(比如说mstore)的二进制目标代码，我们用反汇编器(后面会讲到)确定该过程的代码长度是14字节。

  • 然后，在文件mstore.o上运行GNU调试工具GDB，使用gdb需要在生成目标代码文件时需要加上 -g 命令行选项，然后再使用GDB调试

    gcc -g -Og -c mstore.c
    gdb mstore.o

  • 在gdb中使用以下命令，这条命令告诉GDB显示(简写为 x)从函数multstore所处地址开始的14个十六进制格式表示(也简写为 x)的字节(简写为 b)。

    (gdb) x/14xb multstore

  • 在gcc版本11.4.0下显示结果如下，请忽略前4个字节，因为它是一个额外的指令占用了，在上面的.s文件中也有展示

    

反汇编

• 查看机器代码文件的内容，有一类称为**反汇编器(disassem bier)**的程序。这些程序根据机器代码产生一种类似于汇编代码的格式。在Linux中，带 -d 命令行标志的程序OBJDUMP(表示"object dump")可以充当这个角色：

  objdump -d mstore.o

  

• 左边的十六进制字节值，每行都对应右边的汇编指令。

  • **x86-64的指令长度从1到15个字节不等。**常用的指令以及操作数较少的指令所需的字节数少，而那些不太常用或操作数较多的指令所需字节数较多。
  • 设计指令格式的方式是，从某个给定位置开始，可以将字节唯一地解码成机器指令。
  • 反汇编器只是基于机器代码文件中的字节序列来确定汇编代码。它不需要访问该程序的源代码或汇编代码。
  • 反汇编器使用的指令命名规则与 GCC 生成的汇编代码使用的有些细微的差别。在我们的示例中，它省略了很多指令结尾的‘q’。这些后缀是大小指示符，在大多数情况中可以省略。

链接

• 生成实际可执行的代码需要对一组目标代码文件运行链接器，而这一组目标代码文件中必须含有一个main函数。

  #include <stdio.h>
  void multstore(long, long, long *);
  int main(){
      long d;
      multstore(2, 3, &d);
      printf("2 * 3 --> %ld\n", d);
      return 0;
  }
  long mult2(long a, long b){
      long s = a * b;
      return s;
  }

• 用如下方法生成可执行文件prog：

  gcc -Og -o prog main.c mstore.c

  • prog不仅包含了两个过程的代码，还包含了用来启动和终止程序的代码，以及用来与操作系统交互的代码。

• 反汇编prog 文件：

  objdump -d prog

  其中会包含下面这段

  

• 这段代码与 mstore.o 反汇编产生的代码几乎完全一样。其中一个主要的区别是左边列出的地址不同———链接器将这段代码的地址移到了一段不同的地址范围中

• 第二个不同之处在于链接器填上了callq指令调用函数mult2需要使用的地址。链接器的任务之一就是为函数调用找到匹配的函数的可执行代码的位置。

• 最后一个区别是多了两行代码(第8和9行)。这两条指令对程序没有影响，插入这些指令是为了使函数代码变为16字节，使得就存储器系统性能而言，能更好地放置下一个代码块。

ATT与Intel汇编代码格式有所不同

例如，使用下述命令行，GCC可以产生multstore函数的Intel格式的代码：

gcc -Og -S -masm=intel mstore.c

这个命令得到下列汇编代码：

multstore:
	push	rbx
	mov		rbx, rdx
	call	mult2
	mov		QWORD PTR [rbx], rax
	pop		rbx
	ret

• Intel代码省略了指示大小的后缀。我们看到指令push和mov，而不是pushq和movq

• Intel代码省略了寄存器名字前面的 % 符号，用的是rbx，而不是%rbx

• Intel代码用不同的方式来描述内存中的位置，例如是 QWORD PTR [rbx] 而不是(%rbx)。

• 32或64位体系结构都是由16位扩展而来的，因此用word(字)表示16位。所以qword ptr表示指针指向一个四字(quad words)（64位）的内存单元。

• 在带有多个操作数的指令情况下，列出操作数的顺序相反。

数据格式

• 由于是从16位体系结构扩展成32位的，Intel用术语"字(word)“表示16 位数据类型。因此，称32位数为"双字(double words)”，称64位数为“四字(quad words)"。

• 标准int值存储为双字(32位)，指针(在此用char*表示)存储为8字节的四字，如下图示

  

• 对于相同大小的整数和浮点数，汇编代码的后缀是区分开的。

• 大多数GCC 生成的汇编代码指令都有一个字符的后缀，表明操作数的大小。

  • 例如，数据传送指令有四个变种：movb(传送字节)、movw(传送字)、movl(传送双字)和movq(传送四字)。后缀’l’用来表示双字，因为32 位数被看成是长字"(long word)"。
  • 注意，汇编代码也使用后缀’l’来表示4字节整数和8字节双精度浮点数。这不会产生歧义，因为浮点数使用的是一组完全不同的指令和寄存器。

访问信息

寄存器和操作数指示符

寄存器

• 一个x86-64 的中央处理单元(CPU)包含一组16个存储64位值的通用目的寄存器。这些寄存器用来存储整数数据和指针。

• 它们的名字都以%r开头，不过后面还跟着一些不同的命名规则的名字，这是由于指令集历史演化造成的。

  • 最初的8086中有8个16位的寄存器，即%ax到%bp
  • 扩展到IA32架构时，这些寄存器也扩展成32位寄存器，标号从%eax到%ebp。
  • 扩展到x86-64后，原来的8个寄存器扩展成64位，标号从%rax到%rbp。
  • 除此之外，还增加了8个新的寄存器，它们的标号是按照新的命名规则制定的：从%r8到%r15
  

• 指令可以对这16个寄存器的低位字节中存放的不同大小的数据进行操作。字节级操作可以访问最低的字节，16位操作可以访问最低的2个字节，32位操作可以访问最低的4个字节，而64位操作可以访问整个寄存器。

• 对于生成小于8字节结果的指令，寄存器中剩下的字节会怎么样，对此有两条规则：

  • 生成1字节和2字节数字的指令会保持剩下的字节不变；
  • 生成4字节数字的指令会把高位4个字节置为0。
    • 后面这条规则是作为从IA32到x86-64的扩展的一部分而采用的。

• 在常见的程序里不同的寄存器扮演不同的角色。

操作数指示符

• 大多数指令有一个或多个操作数(operand)，指示出执行一个操作中要使用的源数据值，以及放置结果的目的位置。

• x86-64支持多种操作数格式。源数据值可以以常数形式给出，或是从寄存器或内存中读出。结果可以存放在寄存器或内存中。各种不同的操作数的可能性被分为三种类型。

  • 立即数(immediate)，用来表示常数值。
    • 在ATT格式的汇编代码中，立即数的书写方式是"$"后面跟一个用标准C表示法表示的整数。
    • 不同的指令允许的立即数值范围不同，汇编器会自动选择最紧凑的方式进行数值编码。
  • 寄存器(register)，它表示某个寄存器的内容
    • 16个寄存器的低位1字节、2字节、4字节或8字节中的一个作为操作数，这些字节数分别对应于8位、16位、32位或64位。
    • 用符号 $r_a$ 来表示任意寄存器a, 用引用 $R[r_a ]$ 来表示它的值，这是将寄存器集合看成一个数组R，用寄存器标识符作为索引。
  • 内存引用，它会根据计算出来的地址（通常称为有效地址）访问某个内存位置
    • 因为将内存看成一个很大的字节数组，我们用符号 $M_b[Addr]$ 表示对存储在内存中从地址Addr开始的b个字节值的引用。为了简便，我们通常省去下标b。
    • 有多种不同的寻址模式，允许不同形式的内存引用。$Imm(r_b, r_i, s)$ 表示的是最常用的形式。这样的引用有四个组成部分：一个立即数偏移Imm, 一个基址寄存器 $r_b$ 一个变址寄存器 $r_i$，和一个比例因子s，这里s必须是1、2、4或者8。基址和变址寄存器都必须是64 位寄存器。有效地址被计算为 $Imm+R[r_b]+R[r_i]\cdot s$。
    • 其他形式都是这种通用形式的特殊情况，只是省略了某些部分。当引用数组和结构元素时，比较复杂的寻址模式是很有用的。
  

数据传送指令和栈操作指令

数据传送指令

• 最频繁使用的是将数据从一个位置复制到另一个位置的指令。
• 操作数的通用性使得一条指令能够完成多种功能。它们或者源和目的类型不同，或者执行的转换不同，或者具有的一些副作用不同。

MOV类

• 最简单形式的数据传送(MOVE)指令———MOV类。这些指令把数据从源位置复制到目的位置，不做任何变化。

• MOV类由四条指令组成：movb、movw、movl和movq。这些指令都执行同样的操作；主要区别在于它们操作的数据大小不同：分别是1、2、4和8字节。

  

• 源操作数指定的值要么是一个立即数，要么存储在寄存器中或者内存中。

• 目的操作数指定一个位置，要么是一个寄存器，要么是一个内存地址。

• x86-64加了一条限制，传送指令的两个操作数不能都指向内存位置。将一个值从一个内存位置复制到另一个内存位置需要两条指令———第一条指令将源值加载到寄存器中，第二条将该寄存器值写入目的位置。

• 这些指令的寄存器操作数可以是16个寄存器有标号部分中的任意一个，寄存器部分的大小必须与指令最后一个字符(‘b’,‘w’,‘l’或’q’)指定的大小匹配。

• 大多数情况中，MOV指令只会更新目的操作数指定的那些寄存器字节或内存位置。唯一的例外是movl 指令以寄存器作为目的时，它会把该寄存器的高位4字节设置为0。

  

• 源和目的类型的五种可能的组合。第一个是源操作数，第二个是目的操作数：

  
  • 最后一条指令是处理64位立即数数据的。常规的movq指令只能以表示为32位补码数字的立即数作为源操作数，然后把这个值符号扩展得到64位的值，放到目的位置。
  • movabsq指令能够以任意64位立即数值作为源操作数，并且只能以寄存器作为目的。

MOVZ/MOVS类

• MOVZ(extended move with zero data)和MOVS(extended move with sign data)类两类数据移动指令，在将较小的源值复制到较大的目的时使用。

• 所有这些指令都把数据从源（在寄存器或内存中）复制到目的寄存器。

• MOVZ类中的指令把目的中剩余的字节填充为0，而MOVS类中的指令通过符号扩展来填充，把源操作的最高位进行复制。

  

• 每条指令名字的最后两个字符都是大小指示符：第一个字符指定源的大小，而第二个指明目的的大小。

• **没有一条明确的指令把4字节源值零扩展到8字节目的。**这样的指令逻辑上应该被命名为movzlq，但是并没有这样的指令。

  • 不过，这样的数据传送可以用以寄存器为目的的movl指令来实现。
  • 这一技术利用的属性是，生成4字节值并以寄存器作为目的的指令会把高4字节置为0

• 对于64位的目标寄存器，所有三种源类型（8位、16位和32位）都有对应的符号扩展传送指令，而只有两种较小的源类型（8位和16位）有零扩展传送指令。

• cltq指令。**这条指令没有操作数：它总是以寄存器%eax作为源，%rax作为符号扩展结果的目的。**它的效果与指令 movslq %eax,%rax 完全一致，不过编码更紧凑。

字节传送指令示例：零扩展/符号扩展对高位的影响

数据传送示例

• c语言的数据交换函数

  long exchange(long *xp, long y){
      long x = *xp;
      *xp = y;
      return x;
  }

  汇编代码为，寄存器%rdi和%rsi分别存放参数xp和y

  ;long exchange(long *xp，long y)
  ;xp in %rdi , y in %rsi
  exchange:
  	movq	(%rdi), %rax	;Get x at xp. Set as return value
  	movq	%rsi, (%rdi)	;store y at xp
  	ret						;Return

• 函数exchange由三条指令实现：两个数据传送(movq)，加上一条返回函数被调用点的指令(ret)

  • 当开始执行时，过程参数xp和y分别存储在寄存器%rdi和%rsi中。
  • 然后，第1条指令从内存中读出x，把它存放到寄存器%rax中，实现了C程序中的x=*xp。
  • 稍后，用寄存器%rax从这个函数返回一个值，因而返回值就是x 。
  • 第二条指令将y写入到寄存器%rdi中的xp指向的内存位置，实现了操作*xp=y。

• 关于这段汇编代码有两点值得注意。

  • C语言中所谓的”指针”其实就是地址。间接引用指针就是将该指针（地址）放在一个寄存器中，然后在内存引用中使用这个寄存器中存放的指针（地址）。
  • 像x这样的局部变量通常是保存在寄存器中，而不是内存中。访问寄存器比访问内存要快得多。

数据传送指令如何实现类型转换

• 练习题3.4中讨论了数据传送指令是如何实现类型转换的
  • 对于相同长度的并且同为有符号或者无符号类型的，直接用MOV类即可
  • 如果是从短类型向长类型转
    • 首先，使用MOVZ/MOVS类，将位扩展到长类型，存入长类型寄存器（%eax）
    • 然后，获取整个长类型寄存器（%eax）中的值。
  • 如果是从长类型向短类型转
    • 首先，使用MOV类，把长类型存储长类型寄存器（%eax）
    • 然后，使用MOV类，把长类型寄存器中的一部分，也就是其中的短类型寄存器(%al)中值进行获取
  • 如果是有符号转无符号
    • 首先，使用MOVS类进行符号扩展
    • 然后，使用MOV类获取
  • 如果是无符号转有符号
    • 首先，使用MOVZ类进行零扩展
    • 然后，使用MOV类获取
  • 实际上，由于C语言中的位数相同的有符号数和无符号数之间的转换位级表示不变，所以转换时有符号数做符号扩展，无符号数做零扩展。

栈操作指令

• 最后两个数据传送操作可以将数据压入程序栈中，以及从程序栈中弹出数据。

  • pushq指令的功能是把数据压入到栈上，而popq指令是弹出数据。这些指令都只有一个操作数———压入的数据源和弹出的数据目的。

    

  • **将一个四字值压人栈中，首先要将栈指针减8，然后将值写到新的栈顶地址。**因此，指令 pushq %rbp 的行为等价于下面两条指令：

    subq	$8, %rsp		;Decrement stack pointer
    movq	%rbp, (%rsp)	;Store %rbp on stack

    • 它们之间的区别是在机器代码中 pushq指令 编码为1个字节，而上面那两条指令一共需要8个字节。
    • 先更新栈顶，然后存入数据。因此，栈顶指向的是现在栈中最新的数据。

  • **弹出一个四字的操作包括从栈顶位置读出数据，然后将栈指针加8。**因此，指令 popq %rax 等价于下面两条指令：

    movq	(%rsp), %rax	;Read %rax from stack
    addq	$8, %rsp		;Increment stack pointer

• **栈是向下增长的，这样一来，栈顶元素的地址是所有栈中元素地址中最低的。**栈指针%rsp保存着栈顶元素的地址。

  

• 关于栈，需要注意的两点

  • 出栈的值仍然会保持在原本的内存位置中，直到被覆盖（例如被另一条入栈操作覆盖）。
  • 因为栈和程序代码以及其他形式的程序数据都是放在同一内存中，所以程序可以用标准的内存寻址方法访问栈内的任意位置。

算数和逻辑操作

• x86-64的一些整数和逻辑操作。

  • 大多数操作都分成了指令类，这些指令类有各种带不同大小操作数的变种（后边加b、w、l、q）（只有leaq没有其他大小的变种）。
  • 操作被分为四组：加载有效地址、一元操作、二元操作和移位。二元操作有两个操作数，而一元操作有一个操作数
  

加载有效地址(leaq)

• 加载有效地址(load effective address)指令leaq实际上是movq指令的变形。它的指令形式是从内存读数据到寄存器。

• 但实际上它根本就没有引用内存。它的第一个操作数看上去是一个内存引用，但该指令并不是从指定的位置读入数据，而是将有效地址写入到目的操作数。

  • 也就是说，本来leaq应该读取源操作数这个地址上存储的内容，但是现在他读到的是这个地址的值。
  • 这条指令可以为后面的内存引用产生指针。另外，它还可以简洁地描述普通的算术操作。
  • 目的操作数必须是一个寄存器。

• 为了说明leaq在编译出的代码中的使用，看看下面这个C程序

  long scale(long x,long y,long z) {
  	long t = x + 4 * y + 12 * Z;
  	return t;
  }

  编译时，该函数的算术运算以三条leaq指令实现

  ;long scale(long x， long y， long z)
  ;x in %rdi, y in %rsi, z in %rdx
  scale:
  	leaq	(%rdi, %rsi, 4), %rax	;x+4*y
  	leaq	(%rdx, %rdx, 2), %rdx	;z+2*z=3*z
  	leaq	(%rax, %rdx, 4), %rax	;(x+4*y)+4*(3*z)=x+4*y+12*Z
  ret

一元和二元操作

• 第二组中的操作是一元操作，只有一个操作数，既是源又是目的。这个操作数可以是一个寄存器，也可以是一个内存位置。对应的是C语言中的++、–、~等运算符

  

• 第三组是二元操作，其中，第一个操作数是源，第二个操作数既是源又是目的。例如，指令 subq %rax,%rdx 使寄存器%rdx的值减去%rax中的值。第一个操作数可以是立即数、寄存器或是内存位置。第二个操作数可以是寄存器或是内存位置。

  

• 注意这些操作后边都是要加后边加b、w、l、q的。

移位操作

• 最后一组是移位操作，先给出移位量，然后第二项给出的是要移位的数。可以进行算术和逻辑右移。

  

• 移位量可以是一个立即数，或者放在单字节寄存器%cl中。（这些指令很特别，因为只允许以这个特定的寄存器作为操作数）。如果只有一个操作数，也就是比如 SAL %eax ，是移位一位的意思。

• 原则上来说，1个字节的移位量使得移位量的编码范围可以达到 $2^8-1=255$ 。x86-64中，移位操作对w位长的数据值进行操作，移位最是由%cl寄存器的低m位决定的，这里 $2^m=w$。高位会被忽略。

  • 所以，例如当寄存器%cl的十六进制值为0xFF时，指令salb会移7位，salw会移15位，sall 会移31位，而salq会移63位。

• 左移指令有两个名字：SAL和SHL。两者的效果是一样的，都是将右边填上0。右移指令不同，SAR 执行算术移位（填上符号位），而SHR执行逻辑移位（填上0）。

• 移位操作的目的操作数可以是一个寄存器或是一个内存位置。

• 大多数指令，既可以用于无符号运算，也可以用于补码运算。只有右移操作要求区分有符号和无符号数。这个特性使得补码运算成为实现有符号整数运算的一种比较好的方法的原因之一。

八字乘法

• 两个64位有符号或无符号整数相乘得到的乘积需要128位来表示。x86-64指令集对128位(16字节）数的操作提供有限的支持。延续 字(2字节)、双字(4字节)和四字(8字节)的命名惯例，Intel把16 字节的数称为八字(oct word)。

  

• 图3-10中双操作数的imulq，它从两个64位操作数产生一个64位乘积种。(回想一下，当将乘积截取到64位时，无符号乘和补码乘的位级行为是一样的。)

• x86-64指令集还提供了两条不同的“单操作数”乘法指令，以计算两个64位值的全128位乘积，一个是无符号数乘法(mulq)，而另一个是补码乘法(imulq)。

• 这两条指令都要求一个参数必须在寄存器%rax中，而另一个作为指令的源操作数给出。然后乘积存放在寄存器%rdx(高64位)和%rax(低64位)中。

• 虽然imulq这个名字可以用于两个不同的乘法操作，但是汇编器能够通过计算操作数的数目，分辨出想用哪条指令。

• 下面这段C代码是一个示例

  #include <inttypes.h>
  typedef unsigned __int128 uint128_t;
  
  void store_uprod(uint128_t *dest, uint64_t x, uint64_t y)
  {
      *dest = x * (uint128_t)y;
  }

  inttypes.h和stdin.h差不多，依赖GCC提供的128位整数支持，用名字__int128来声明。这段代码指明得到的乘积应该存放在指针dest指向的16字节处。GCC生成的汇编代码如下

  ;void store_uprod(uint128_t *dest， uint64_t x, uint64_t y)
  ;dest in %rdi,x in %rsi,y in %rdx
  store_uprod:
  	movq	%rsi, %rax		;Copy x to multiplicand
  	mulq	%rdx			;Multiply by y
  	movq	%rax, (%rdi)	;store lower 8 bytes at dest
  	movq	%rdx, 8(%rdi)	;Store upper 8 bytes at dest+8
  	ret

• 可以观察到，存储乘积需要两个movq指令：一个存储低8个字节，一个存储高8个字节。由于生成这段代码针对的是小端法机器，所以高位字节存储在大地址，正如地址8(%rdi)表明的那样。

除法运算

• 除法或取模操作由单操作数除法指令来提供，类似于单操作数乘法指令。有符号除法指令idivq将寄存器 %rdx(高64位)和%rax(低64位) 中的128位数作为被除数，而除数作为指令的操作数给出。指令将商存储在寄存器%rax中，将余数存储在寄存器%rdx中。

• 对于大多数64位除法应用来说，被除数也常常是一个64位的值。这个值应该存放在％rax中，%rdx的位应该设置为全0(无符号运算)或者%rax的符号位(有符号运算)。

  • 后面这个操作可以用**指令cqto(Convert to oct word)**来完成（在Intel的文档中这条指令叫做cqo）。这条指令不需要操作数，它隐含读出%rax的符号位，并将它复制到%rdx的所有位

• x86-64如何实现除法，计算了两个64位有符号数的商和余数

  void remdiv(long x, long y, long *qp, long *rp){
      long q = x / y;
      long r = x % y;
      *qp = q;
      *rp = r;
  }

  该函数编译得到如下汇编代码：

  ;void remdiv(long x, long y，long *qp， long *rp)
  ;x in %rdi , y in %rsi, qp in %rdx，rp in %rcx
  remdiv:
  	movq	%rdx, %r8	;copy qp
  	movq	%rdi, %rax	;Move x to lower 8 bytes of dividend
  	cqto				;Sign-extend to upper 8 bytes of dividend
  	idivq	%rsi		;Divide by y
  	movq	%rax, (%r8)	;store quotient at qp
  	movq	%rdx, (%rcx)	;store remainder at rp
  	ret

• 无符号除法使用divq指令。通常，寄存器%rdx会事先设置为0。

控制

到目前为止，我们只考虑了直线代码的行为，也就是指令一条接着一条顺序地执行。C语言中的某些结构，比如条件语句、循环语句和分支语句，要求有条件的执行，根据数据测试的结果来决定操作执行的顺序。

条件码

• 除了整数寄存器，CPU还维护着一组单个位的**条件码(condition code)**寄存器，它们描述了最近的算术或逻辑操作的属性。可以检测这些寄存器来执行条件分支指令。

• 最常用的条件码有：

  • **CF: 进位标志。**最近的操作使最高位产生了进位。可用来检查无符号操作的溢出。

  • **ZF: 零标志。**最近的操作得出的结果为0 。

  • **SF: 符号标志。**最近的操作得到的结果为负数。

  • **OF: 溢出标志。**最近的操作导致一个补码溢出正溢出或负溢出。

  • **PF：奇偶标志。**对于整数操作，当最近的一次算术或逻辑运算产生的值的最低位字节是偶校验的（即这个字节中有偶数个1)，那么就会设置这个标志位。

• 假设我们用一条ADD指令完成等价于C表达式 t=a+b 的功能，这里变量 a、b和t 都是整型的。然后，根据下面的C表达式来设置条件码(可以学习下带标志加法器对标志信息)：

  CF		(unsigned)t < (unsigned)a		Unsigned overflow
  ZF		(t==0)							Zero
  SF		(t<0)							Negative
  OF		(a<0==b<0) && (t<0 != a<0)		Signed overflow

• 哪些操作会影响条件码？

  • leaq指令不改变任何条件码，因为它是用来进行地址计算的。除此之外，所有的算术和逻辑指令都会设置条件码

  • 对于逻辑操作，例如XOR，进位标志和溢出标志会设置成0。

  • 对于移位操作，进位标志将设置为最后一个被移出的位，而溢出标志设置为0 。

  • INC和DEC指令会设置溢出和零标志，但是不会改变进位标志

• 此外，还有两类指令，它们只设置条件码而不改变任何其他寄存器

  • CMP 指令根据两个操作数之差来设置条件码。除了只设置条件码而不更新目的寄存器之外，CMP 指令与 SUB 指令的行为是一样的。
    • 如果两个操作数相等，这些指令会将零标志设置为1, 而其他的标志可以用来确定两个操作数之间的大小关系。
  • TEST 指令的行为与 AND 指令一样，除了它们只设置条件码而不改变目的寄存器的值。
    • 典型的用法是，两个操作数是一样的（例如，testq %rax, %rax 用来检查 %rax 是负数、零，还是正数），或其中的一个操作数是一个掩码，用来指示哪些位应该被测试。
  

访问条件码

• 条件码通常不会直接读取，常用的使用方法有三种：

  1. 可以根据条件码的某种组合，将一个字节设置为 0 或者 1
  2. 可以条件跳转到程序的某个其他的部分
  3. 可以有条件地传送数据。

• 根据条件码的组合，设置一个字节的值

  • 将这一整类指令称为 SET指令；它们之间的区别就在于它们考虑的条件码的组合是什么，这些指令名字的不同后缀指明了它们所考虑的条件码的组合。

  • 一条 SET指令 的目的操作数是低位单字节寄存器元素之一，或是一个字节的内存位置，指令会将这个字节设置成0或者1。为了得到一个32位或64位结果，我们必须对高位清零。

    
    • 这里解释一下setg、setge、setl和setle，当进行比较a和b，会等价a-b
      • 若a<b，则a-b<0，正常情况下会有SF=1，OF=0
        • 特殊情况：当a远远小于0，b远远大于0，可能会发生溢出，这时OF=1，SF=0
        • 因此要满足a<b，需要SF和OF异号，即SF^OF=1
        • 若同时要满足a=b的情况，则a-b=0，有SF=0，OF=0，ZF=1
          • 这时SF^OF=0，或上ZF可以满足等于号，得到(SF^OF)|ZF
      • 若a>b，则a-b>0，正常情况下会有SF=0，OF=0
        • 特殊情况：当a远远大于0，b远远小于0，可能会发生溢出，这时OF=1，SF=1
        • 因此要满足a>b，需要SF和OF同号，即~(SF^OF)=1
        • 若同时要满足a=b的情况，则a-b=0，有SF=0，OF=0，ZF=1
          • 这时~(SF^OF)=1，满足a=b的情况，所以表达式~(SF^OF)是对应不等式 $a\ge b$ 的
          • 若要只满足a>b，需要排除ZF=1的情况，即~(SF^OF)&~ZF
    • 这里可以看到 a<b 和 $a\ge b$ 以及 $a\le b$ 和 a>b 的表达式是都可以相互取反得到，和后面的 同义名 也相对应
    • 最后4个无符号指令和上面类似

  • 比如两个long类型的数据进行比较a<b，其汇编代码为

    ;int comp(data_t a,data_t b)
    ;a in %rdi , b in %rsi
    comp:
    	cmpq	%rsi, %rdi	;Compare a:b
    	setl	%al			;set low-order byte of %eax to 0 or 1
    	movzbl	%a1, %eax	;Clear rest of %eax (and rest of %rax)
    	ret

• 为什么条件码会有这些组合呢？以运算t=a-b为例

  • sete的情况，即当相等时设置(set when equal)指令。当a=b时，会得到t=0，因此零标志置位ZF就表示相等。
  • 用setl，即 当小于时设置(set when less) 指令，测试一个有符号比较。当没有发生溢出时(OF设置为0就表明无溢出)，我们有当 $a-^y_wb<0$ 时a<b，将SF设置为1即指明这一点，而当 $a-^y_wb>0$ 时a>b，由SF设置为0指明。
  • 另一方面，当发生溢出时，有当 $a-^y_wb>0$ (负溢出）时a<b，而当 $a-^y_wb<0$ (正溢出)时a>b。当a=b时，不会有溢出。因此，当OF被设置为1时，当且仅当SF被设置为0，有a<b 。
  • 将这些情况组合起来，溢出和符号位的EXCLUSIVE-OR(异或)提供了a<b是否为真的测试。其他的有符号比较测试基于SF^OF和ZF的其他组合。
  • 对于无符号比较的测试，现设a和b是变量a和b的无符号形式表示的整数。当a-b<0时，CMP指令会设置进位标志，因而无符号比较使用的是进位标志和零标志的组合。

• 机器代码并不能区分有符号和无符号值，不会将每个程序值都和一个数据类型联系起来。大多数情况下，机器代码对于有符号和无符号两种情况都使用一样的指令，这是因为许多算术运算对无符号和补码算术都有一样的位级行为。

• 有些情况需要用不同的指令来处理有符号和无符号操作，例如，使用不同版本的右移、除法和乘法指令，以及不同的条件码组合。这个过程中对符号数和无符号数的区分应该是编译中实现的。

跳转指令

jump

• 跳转(jump)指令会导致执行切换到程序中一个全新的位置。在汇编代码中，这些跳转的目的地通常用一个标号(label)指明。

• 在产生目标代码文件时，汇编器会确定所有带标号指令的地址，并将跳转目标（目的指令的地址）编码为跳转指令的一部分。

• 例如，指令 jmp .L1 会导致程序跳过 movq指令，而从 popq指令 开始继续执行。

  	movq	$0, %rax		;Set %rax to 0
  	jmp		.L1				;Goto .L1
  	movq	(%rax), %rdx	;Null pointer dereference (skipped)
  .L1:
  	popq	%rdx			;jump target

• jmp指令 是无条件跳转。它可以是直接跳转，即跳转目标是作为指令的一部分编码的；也可以是间接跳转，即跳转目标是从寄存器或内存位置中读出的

  • 汇编语言中，直接跳转是给出一个标号作为跳转目标的，例如上面所示代码中的标号". L1"

  • 间接跳转的写法是"*"后面跟一个操作数指示符，使用内存操作数格式中的一种，如

    jmp	*%rax		;用寄存器%rax中的值作为跳转目标
    jmp *(%rax)		;以%rax中的值作为读地址,从内存中读出跳转目标。

• 其他跳转指令都是有条件的，它们根据条件码的某种组合，跳转或者继续执行代码序列中下一条指令。这些指令的名字和跳转条件与SET指令的名字和设置条件是相匹配的。

  • 条件跳转只能是直接跳转
  

跳转指令的编码

• 在汇编代码中，跳转目标用符号标号书写。汇编器，以及后来的链接器，会产生跳转目标的适当编码

• 跳转指令有几种不同的编码，但是最常用都是 PC相对的(PC-relative)。

  • 它们会将目标指令的地址与紧跟在跳转指令后面那条指令的地址之间的差作为编码。这些地址偏移量可以编码为1、2或4个字节

  • 第二种编码方法是给出 绝对地址，用4个字节直接指定目标。

  • 汇编器和链接器会选择适当的跳转目的编码。

• 一个PC相对寻址的例子，它包含两个跳转：第2行的jmp指令前向跳转到更高的地址，而第7行的jg 指令后向跳转到较低的地址。

  1		movq	%rdi, %rax
  2		jnp		.L2
  3	.L3:
  4		sarq	%.rax
  5	.L2:
  6		testq	rax, %rax
  7		jg		.L3
  8	rep; ret

• 汇编器产生的 .o 格式的反汇编版本如下:

  1	0:	48 89 f8		mov		%rdi, %rax
  2	3:	eb 03			jmp		8 <loop+0x8>
  3	5:	48 d1 f8		sar		%rax
  4	8:	48 85 c0		test	%rax, %rax
  5	b:	7f f8			jg		5<loop+0x5>
  6	d:	f3 c3			repz retq

• 第2行中跳转指令的跳转目标指明为0x8，第5行中跳转指令的跳转目标是0x5。观察指令的字节编码，看到第一条跳转指令的目标编码（在第二个字节中）为0x03。把它加上0x5，也就是下一条指令的地址，就得到跳转目标地址0x8，也就是第4行指令的地址。

• 类似，第二个跳转指令的目标用单字节、补码表示编码为0xf8(十进制-8)。将这个数加上0xd(十进制13)，即第6行指令的地址，我们得到0x5，即第3行指令的地址。

• 这些例子说明，当执行PC相对寻址时，程序计数器的值是跳转指令后面的那条指令的地址，而不是跳转指令本身的地址。这种惯例可以追溯到早期的实现，当时的处理器会将更新程序计数器作为执行一条指令的第一步。

• 下面是链接后的程序反汇编版本

  1	4004d0:	48 89 f8	mov		%rdi, %rax
  2	4004d3:	eb 03		jmp		4004d8 <loop+0x8>
  3	4004d5:	48 d1 f8	sar		%rax
  4	4004d8:	48 85 c0	test	%rax, %rax
  5	4004db:	7f f8		jg		4004d5 <loop+0x5>
  6	4004dd:	f3 c3		repz retq

条件分支

用条件控制来实现条件分支

• 将条件表达式和语句从C语言翻译成机器代码，最常用的方式是结合有条件和无条件跳转。

• 下面用一个例子，给出了一个计算两数之差绝对值的函数的C代码。实际上，如果这个减法溢出，这个函数就会返回一个负数值，这里我们主要是为了展示机器代码。这个函数有一个副作用，会增加两个计数器，编码为全局变量lt_cnt和ge_cnt

  long lt_cnt = 0;
  long ge_cnt = 0;
  
  long absdiff_se(long x, long y){
      long result;
      if (x < y){
          lt_cnt++;
          result = y - x;
      }
      else{
          ge_cnt++;
          result = x - y;
      }
      return result;
  }

  使用goto语句的C程序。在goto代码中，第5行中的goto x_ge_y语句会导致跳转到第9行中的标号x_ge_y处，从这一点继续执行，完成函数absdiff_se的else部分并返回。另一方面，如果测试x>=y失败，程序会计算absdiff_se的if部分指定的步骤并返回。

  long gotodiff_se(long x, long y){
      long result;
      if (x >= y)
          goto x_ge_y;
      lt_cnt++;
      result = y - x;
      return result;
  x_ge_y:
      ge_cnt++;
      result = x - y;
      return result;
  }

  GCC产生的汇编代码。汇编代码的实现首先比较了两个操作数，设置条件码。如果比较的结果表明x大于或者等于y，那么它就会跳转到.L2，增加全局变量ge_cnt，计算x-y作为返回值并返回。由此我们可以看到absdiff_se对应汇编代码的控制流非常类似于gotodiff_se的goto代码。

  ;long absdiff _se(long x， long y)
  ;x in %rdi, y in %rsi
  absdiff_se:
  	cmpa	%rsi, %rdi			;Compare x:y
  	jge		.L2					;If >=goto x_gey
  	addq	$1, lt_cnt(%rip)	;lt_cnt++
  	movq	%rsi, %rax
  	subq	%rdi, %rax			;result = y - x
  	ret							;Return
  .L2:							;x_ge_y:
  	addq	$1, ge_cnt(%rip)	;ge_cnt++
  	movq	%rdi, %rax
  	subq	%rsi, %rax			;result = x - y
  	ret							;Return

• C语言中的if-else语句的通用形式模板如下：

  if (test-expr)
      then-statement
  else
      else-statement

• 这里test-expr是一个整数表达式，它的取值为0(解释为 假)或者为非0(解释为 真)。两个分支语句中(then-statement或else-statement)只会执行一个。

• 对于这种通用形式，汇编实现通常会使用下面这种形式，这里，我们用C语法来描述控制流：

      t = test-expr;
      if (!t)
          goto false;
      then-statement
      goto done;
  false:
      else-statement
  done:

• 也就是，汇编器为then-statement和else-statement产生各自的代码块。它会插入条件和无条件分支，以保证能执行正确的代码块。

用条件传送来实现条件分支

• **实现条件操作的传统方法是通过使用控制的条件转移。当条件满足时，程序沿着一条执行路径执行，而当条件不满足时，就走另一条路径。**这种机制简单而通用，但是在现代处理器上，它可能会非常低效。

• 一种替代的策略是使用数据的条件转移。这种方法计算一个条件操作的两种结果，然后再根据条件是否满足从中选取一个。

  • 条件传送是什么？就是mov指令的变种，满足某些标志位才执行mov，否则不操作；例如下面的cmovge指令，当大于等于的时候才会执行这条指令

• 只有在一些受限制的情况中，这种策略才可行，但是如果可行，就可以用一条简单的条件传送指令来实现它，条件传送指令更符合现代处理器的性能特性。

• 给出一个使用条件传送的例子，C函数absdiff包含一个条件表达式

  long absdiff(long x, long y){
      long result;
      if (x < y)
          result = y - x;
      else
          result = x - y;
      return result;
  }

  C函数cmovdiff模拟汇编代码操作

  long cmovdiff(long x, long y){
      long rval = y - x;
      long eval = x - y;
      long ntest = x >= y;
      /*Line below requires
  	single instruction: */
  	if (ntest) rval = eval;
      return rval;
  }

  给出产生的汇编代码

  ;long absdiff(long x， long y)
  ;x in %rdi , y in %rsi
  absdiff :
  	movq	%rsi, %rax
  	subq	%rdi, %rax		;rval = y-x
  	movq	%rdi, %rdx
  	subq	%rsi, %rdx		;eval = x-y
  	cmpq	%rsi, %rdi		;Compare x:y
  	cmovge	%rdx, %rax		;If >=， rval = eval
  	ret						;Return rval

• 为什么基于条件数据传送的代码会比基于条件控制转移的代码性能要好

  • 处理器通过使用流水线(pipelining) 来获得高性能，在流水线中，一条指令的处理要经过一系列的阶段，每个阶段执行所需操作的一小部分（例如，从内存取指令、确定指令类型、从内存读数据、执行算术运算、向内存写数据，以及更新程序计数器）。
  • 这种方法通过重叠连续指令的步骤来获得高性能，例如，在取一条指令的同时，执行它前面一条指令的算术运算。要做到这一点，要求能够事先确定要执行的指令序列，这样才能保持流水线中充满了待执行的指令。
  • 当机器遇到条件跳转(也称为 分支)时，只有当分支条件求值完成之后，才能决定分支往哪边走。处理器采用非常精密的分支预测逻辑来猜测每条跳转指令是否会执行。
  • 如果它的猜测还比较可靠(现代微处理器设计试图达到90%以上的成功率)，指令流水线中就会充满着指令。另一方面，错误预测一个跳转，要求处理器丢掉它为该跳转指令后所有指令己做的工作，然后再开始用从正确位置处起始的指令去填充流水线。这样一个错误预测会招致很严重的惩罚，浪费大约15~30个时钟周期，导致程序性能严重下降。
    • 在Intel Haswell处理器上运行absdiff函数，用两种方法来实现条件操作。在一个典型的应用中，x<y的结果非常地不可预测，因此即使是最精密的分支预测硬件也只能有大约50%的概率猜对。此外，两个代码序列中的计算执行都只需要一个时钟周期。因此，分支预测错误处罚主导着这个函数的性能。对于包含条件跳转的x86-64代码，我们发现当分支行为模式很容易预测时，每次调用函数需要大约8个时钟周期；而分支行为模式是随机的时候，每次调用需要大约17.50个时钟周期。由此我们可以推断出分支预测错误的处罚是大约19个时钟周期。这就意味着函数需要的时间范围大约在8到27个周期之间，这依赖于分支预测是否正确。
      • 如何确定分支预测错误的处罚。假设预测错误的概率是p，如果没有预测错误，执行代码的时间是 $T_{OK}$，而预测错误的处罚是 $T_{MP}$。那么，作为p的一个函数，执行代码的平均时间是 $T_{avg}(p)=(1-p)T_{OK}+p(T_{OK}+T_{MP})=T_{OK}+pT_{MP}$。如果已知 $T_{OK}$和 $T_{ran}$(当p=0.5时的平均时间)，要确定 $T_{MP}$。将参数代入等式，我们有 $T_{ran}= T_{avg}(0.5)=T_{OK}+0.5T_{MP}$，所以有 $T_{MP}=2(T_{ran}-T_{OK})$。因此，对于 $T_{OK}=8$ 和 $T_{ran}=17.5$，我们有 $T_{MP}=19$。
    • 另一方面，无论测试的数据是什么，编译出来使用条件传送的代码所需的时间都是大约8个时钟周期。控制流不依赖于数据，这使得处理器更容易保持流水线是满的。
  • 基于条件数据传送的代码，更符合线性的执行顺序，避免了错误的惩罚。在分支内的操作较少时可以提高效率。最典型的就是三元表达式。

• x86-64中的条件传送指令。每条指令都有两个操作数：源寄存器或者内存地址S，和目的寄存器R。这些指令的结果取决于条件码的值。源值可以从内存或者源寄存器中读取，但是只有在指定的条件满足时，才会被复制到目的寄存器中。

  

• 源和目的的值可以是16位、32位或64位长。不支持单字节的条件传送。

• 因为目标只能是寄存器，所以汇编器可以从目标寄存器的名字推断出条件传送指令的操作数长度，所以对所有的操作数长度，都可以使用同一个的指令名字。

• 同条件跳转不同，处理器无需预测测试的结果就可以执行条件传送。处理器只是读源值(可能是从内存中)，检查条件码，然后要么更新目的寄存器，要么保持不变。

• 为了理解如何通过条件数据传输来实现条件操作，考虑下面的条件表达式和赋值的通用形式：

  v = test-expr ? then-expr : else-expr;

  用条件控制转移的标准方法来编译这个表达式会得到如下形式

  	if (!test-expr)
          goto false;
      v = then-expr;
      goto done;
  false:
  	v = else-expr;
  done:

  但是对于then-expr和else-expr，最终值的选择基于test-expr的值。于是有以下代码

  v = then-expr;
  ve = else-expr;
  t = test-expr;
  if(!t) v = ve;

  这个序列中最后一条语句是用条件传送实现的，当测试条件t不满足时，ve的值会被复制到v中。

• 条件传送在那些情况下不适用

  • 无论测试结果如何，用条件传送来实现条件分支会对then-expr和else-expr都求值。如果这两个表达式中的任意一个可能产生错误条件或者副作用，就会导致非法的行为。

  • 作为说明，考虑下面这个C函数：

    long cread(long *xp){
        return (xp ? *xp : 0);
    }

    这段代码看起来似乎很适合被编译成使用条件传送，当指针为空时将结果设置为0，汇编代码如下所示：

    ;long cread(long *xp)
    ;Invalid implementation of function cread
    ;xp in register %rdi
    cread:
    	movq	(%rdi), %rax	;v=*xp
    	testq	%rdi, %rdi		;Test x
    	movl	$0, %edx		;Set ve = o
    	cmove	%rdx, %rax		;If x==0,v = ve
    	ret						;Return v

    不过，这个实现是非法的，因为即使当测试为假时，movq指令(第2行)对xp的间接引用还是发生了，导致一个间接引用空指针的错误。所以，必须用分支代码来编译这段代码。

  • 使用条件传送也不总是会提高代码的效率。例如，如果then-expr或者else-expr的求值需要大量的计算，那么当相对应的条件不满足时，这些工作就白费了。编译器必须考虑浪费的计算和由于分支预测错误所造成的性能处罚之间的相对性能。

    • 根据我们的经验，即使许多分支预测错误的开销会超过更复杂的计算，GCC 还是会使用条件控制转移。

  • 所以，总的来说，条件数据传送提供了一种用条件控制转移来实现条件操作的替代策略。它们只能用于非常受限制的情况，但是这些情况还是相当常见的，而且与现代处理器的运行方式更契合。

循环

• C语言提供了多种循环结构，即do-while、while和for。汇编中没有相应的指令，可以用条件测试和跳转组合起来实现循环效果。GCC和其他汇编器产生的循环代码主要基于两种基本的循环模式

do-while循环

• do-while语句的通用形式如下：

  do
      body-statement;
  while (test-expr);

  这个循环的效果就是重复执行body-statement，对test-expr求值，如果求值的结果为非零，就继续循环。可以看到，body-statement至少会执行一次。

• 这种通用形式可以被翻译成如下所示的条件和goto语句：

  loop:
      body-statement;
      t = test-expr;
      if (t)
          goto loop;

  • 每次循环，程序会执行循环体里的语句，然后执行测试表达式。如果测试为真，就回去再执行一次循环。
  • do-while模式是最基本的循环模式。

• 示例，用do-while循环来计算函数参数的阶乘

  long fact_do(long n){
  	long result = 1;
      do {
  		result *= n;
          n = n-1;
      } while (n > 1);
      return result;
  }

  等价的goto版本

  long fact_do_goto(long n){
  	1ong result = 1;
  loop:
      result *= n;
      n = n-1;
      if (n > 1)
      	goto loop;
      return result;
  }

  对应的汇编代码：

  ;long fact_do(long n)
  ;n in %rdi
  fact_do:
  	movl	$1, %eax	;Set result =.1
  .L2:					;loop:
  	imulq	%rdi, %rax	;Compute result*=n
  	subq	$1, %rdi	;Decrement n
  	cmpq	$1, %rdi	;Compare n:1
  	jg		.L2			;If >, goto loop
  	rep; ret			;Return

while 循环

• while 语句的通用形式如下：

  while (test-expr)
      body-statement

  • 与do-while的不同之处在于，在第一次执行body-statement之前，它会对test-expr求值，循环有可能就中止了

• 有很多种方法将while循环翻译成机器代码，GCC在代码生成中使用其中的两种方法。这两种方法使用同样的循环结构，与do-while一样，不过它们实现初始测试的方法不同。

• 第一种翻译方法，我们称之为跳转到中间(jump to middle), 它执行一个无条件跳转跳到循环结尾处的测试，以此来执行初始的测试。

  • 这种模式实际上是在第一次直接跳转到了do-while模式中的测试条件。
  • 可以用以下模板来表达这种方法

      goto test;
  loop:
      body-statement
  test:
      t = test-expr;
      if (t)
          goto loop;

• 示例，使用while循环的阶乘函数

  long fact_while(long n){
      long result = 1;
      while (n > 1) {
      	result *= n;
          n = n-1;
      }
      return result;
  }

  等价的goto版本

  long fact_while_jm_goto(long n){
      long result = 1;
      goto test;
  loop:
      result *= n;
      n = n-1;
  test:
      if (n > 1)
      	goto loop;
      return result;
  }

  对应的汇编代码

  ;long fact_while(long n)
  ;n in %rdi
  fact_while:
  	movl	$1, %eax	;Set result = 1
  	jmp		.L5			;Goto test
  .L6:					;loop:
  	imulq	%rdi, %rax	;Compute result*=n
  	subq	$1, %rdi	;Decrement n
  .L5:					;test:
  	cmpq	$1, %rdi	;Compare n:1
  	jg		.L6			;If > , goto loop
  	rep; ret			;Return

• 第二种翻译方法，我们称之为guarded-do，首先用条件分支，如果初始条件不成立就跳过循环，把代码变换为do-while循环。

  • 这种方法，就是在do-while前置一个额外的判断。

  • 当使用较高优化等级编译时，例如使用命令行选项-O1，GCC会采用这种策略。

  • 利用这种实现策略，编译器常常可以优化初始的测试，例如认为测试条件总是满足。

  • 可以用如下模板来表达这种方法，把通用的while循环格式翻译成do-while的goto循环

    t = test-expr;
    if (!t)
        goto done;
    loop:
        body-statement
        t = test-expr;
        if (t)
            goto loop;
    done:

• 示例，同样阶乘函数等价的goto版本

  long fact_while_gd_goto(long n){
  	long result = 1;
      if (n <= 1)
  		goto done;
  loop:
      result *= n;
      n = n-1;
      if (n != 1)
      	goto loop;
  done:
      return result;
  }

  对应的汇编代码

  ;long fact_while(long n)
  ;n in %rdi
  fact_while:
  	cmpq	$1, %rdi		;Compare n: 1
  	jle		.L7				;If<=, goto done
  	movl	$1, %eax		;Set result = 1
  .L6:					;loop:
  	imulq	%rdi, %rax		;Compute result*=n
  	subq	$1, %rdi		;Decrement n
  	cmpq	$1, %rdi		;Compare n: 1
  	jne		.L6				;If !=，goto loop
  	rep; ret				;Return
  .L7:					;done:
  	movl	$1, %eax		;Compute result = 1
  	ret						;Return

for 循环

• for循环的通用形式如下：

  for (init-expr; test-expr; update-expr)
      body-statement

• C语言标准说明(有一个例外)，这样一个循环的行为与下面这段使用while循环的代码的行为一样：

  init-expr;
  while (test-expr) {
      body-statement
      update-exp;
  }

  • 程序首先对初始表达式init-expr求值，然后进入循环；

  • 在循环中它先对测试条件test-expr求值，如果测试结果为“假”就会退出，否则执行循环体body-statement;

  • 最后对更新表达式update-expr求值。

• GCC为for循环产生的代码是while循环的两种翻译之一，这取决于优化的等级。

  • 跳转到中间策略会得到如下goto代码：

  init-expr;
  goto test;
  loop:
      body-statement
      update-expr;
  test:
      t = test-expr;
      if (t)
          goto loop;

• guarded-do策略得到：

      init-expr;
      t = test-expr;
      if (! t)
          goto done;
  loop :
      body-statement
      update-expr;
      t = test-expr;
      if (t)
          goto loop;
  done:

continue和break

• break的行为无疑是跳转到循环的判断指令之后。
• continue语句会导致程序跳到当前循环迭代的结尾。

switch语句

switch实现逻辑

• switch(开关)语句可以根据一个整数索引值进行多重分支(multiway branching)。**在处理具有多种可能结果的测试时，这种语句特别有用。**它们不仅提高了C代码的可读性，而且通过使用跳转表(jump table)这种数据结构使得实现更加高效
• 跳转表是一个数组，表项i是一个代码段的地址，这个代码段实现当开关索引值等于i时程序应该采取的动作。程序代码用开关索引值来执行一个跳转表内的数组引用，确定跳转指令的目标。
• 和使用一组很长的if-else语句相比，使用跳转表的优点是执行开关语句的时间与开关情况的数量无关。
• GCC根据开关情况的数量和开关情况值的稀疏程度来翻译开关语句。当开关情况数量比较多（例如4 个以上），并且值的范围跨度比较小时，就会使用跳转表。

示例

• 一个C语言switch语句的示例。

  • 这个例子有些非常有意思的特征，包括情况标号(case label)跨过一个不连续的区域(对于情况101和105没有标号)，有些情况有多个标号(情况104和106)，而有些情况则会落入其他情况之中(情况102)，因为对应该情况的代码段没有以break语句结尾。

  void switch_eg(long x, long n, long *dest){
      long val = x;
      switch (n)
      {
      case 100:
          val *= 13;
          break;
      case 102:
          val += 10;
          /*Fall through */
      case 103:
          val += 11;
          break;
      case 104:
      case 106:
          val *= val;
          break;
      default:
          val = 0;
      }
      *dest = val;
  }

  • GCC提供的对跳转表的支持，这是对C语言的扩展。数组jt包含7个表项，每个都是一个代码块的地址。
  • 这些位置由代码中的标号定义，在jt的表项中由代码指针指明，由标号加上“&&”前缀组成(创建一个指向代码位置的指针)。（比如原来是goto loc，现在也可以写goto &&loc）

  void switcheg_impl(long x, long n, long *dest)
  {
      /*Table of code pointers */
      static void *jt[7] = {
          &&loc_A, &&loc_def, &&loc_B, &&loc_C, &&loc_D, &&loc_def, &&loc_D};
      unsigned long index = n - 100;
      long val;
      if (index > 6)
          goto loc_def;
      goto *jt[index]; /* Multiway branch */
  loc_A: /* Case 100 */
      val = x * 13;
      goto done;
  loc_B: /* Case 102 */
      val = x + 10;
      /*Fall through*/
  loc_C: /*Case 103 */
      val = x + 11;
      goto done;
  loc_D: /* Cases 104,106*/
      val = x * x;
      goto done;
  loc_def: /* Default case */
      val = 0;
  done:
      *dest = val;
  }

• 原始的C代码有针对值100、102-104和106的清况，但是开关变量n可以是任意整数。编译器首先将n减去100，把取值范围移到0和6之间，创建一个新的程序变量，在我们的C版本中称为index。

• 补码表示的负数会映射成无符号表示的大正数，利用这一事实，将index看作无符号值，从而进一步简化了分支的可能性。因此可以通过测试index是否大于6来判定index是否在0~6的范围之外。

• 根据index的值，有五个不同的跳转位置，最后一个是默认的目的地址。每个标号都标识一个实现某个情况分支的代码块。

;void switch_eg(long x, long n, long *dest)
;x in %rdi, n in %rsi, dest in %rdx
switch_eg:
    subq    $100, %rsi                  ;Compute index = n-100
    cmpq    $6, %rsi                    ;Compare index:6
    ja      .L8                         ;If >, goto loc_def
    jmp     *.L4(, %rsi, 8)             ;Goto *jt[index]
.L3:                                    ;loc_A:
    leaq    (%rdi, %rdi, 2), %rax       ;3*x
    leaq    (%rdi, %rax, 4), %rdi       ;val = 13*x
    jmp     .L2                         ;Goto done
.L5:									;loc_B:
	addq	$10, %rdi                   ;x= x +10
.L6:                                    ;loc_C:
    addq    $11, %rdi                   ;val = x + 11
    jmp     .L2                         ;Goto done
.L7:                                    ;loc_D:
    imulq   %rdi, %rdi                  ;val = *x
    jmp     .L2                         ;goto done
.L8:                                    ;loc_def :
    movl    $0, %edi                    ;val = 0
.L2:                                    ;done:
    movq    %rdi, (%rdx)                ;*dest = val
    ret                                 ;Return

• 执行switch语句的关键步骤是通过跳转表来访问代码位置。jmp指令的操作数有前缀“*”，表明是一个间接跳转，操作数指定一个内存位置，索引由寄存器%rsi给出，这个寄存器保存着index的值。

• C代码将跳转表声明为一个有7个元素的数组，每个元素都是一个指向代码位置的指针。可以观察到，跳转表对重复情况的处理就是简单地对表项4和6用同样的代码标号(loc_D)，而对于缺失的情况的处理就是对表项1和5使用默认情况的标号(loc_def)。

• 在汇编代码中，跳转表用以下声明表示

      .section            ;.rodata
      .align 8            ;Align address to multiple of 8
  .L4:
  .quad   .L3				;Case 100: loc_A
  .quad   .L8             ;Case 101: loc_def
  .quad   .L5             ;case 102: loc_B
  .quad   .L6             ;Case 103: loc_c
  .quad   .L7             ;case 104: loc_D
  .quad   .L8             ;Case 105: loc_def
  .quad   .L7             ;Case 106: loc_D

  • 这些声明表明，在叫做".rodata" (只读数据，Read-Only Data)的目标代码文件的段中，应该有一组7个“四”字(8个字节)，每个字的值都是与指定的汇编代码标号(例如.L3)相关联的指令地址。
  • 标号.L4标记出这个分配地址的起始。与这个标号相对应的地址会作为间接跳转（第5行）的基地址。

• 关键是领会使用跳转表是一种非常有效的实现多重分支的方法，当switch语句有上百种情况的时候，也可以只用一次跳转表访问去处理。

过程

过程调用机制

过程是软件中一种很重要的抽象。它提供了一种封装代码的方式，用一组指定的参数和一个可选的返回值实现了某种功能。

• 然后可以在程序中不同的地方调用这个函数。设计良好的软件用过程作为抽象机制，隐藏某个行为的具体实现，同时又提供清晰简洁的接口定义，说明要计算的是哪些值，过程会对程序状态产生什么样的影响。

• 不同编程语言中，过程的形式多样：函数(function)、方法(method)、子例程(subroutine)、处理函数(handler)等等，但是它们有一些共有的特性。

• 要提供对过程的机器级支持，必须要处理许多不同的属性。为了讨论方便，假设过程P调用过程Q，Q执行后返回到P。这些动作包括下面一个或多个机制：

  • 传递控制。在进入过程Q的时候，程序计数器必须被设置为Q的代码的起始地址，然后在返时，要把程序计数器设置为P中调用Q后面那条指令的地址。
  • 传递数据。P必须能够向Q提供一个或多个参数，Q必须能够向P返回一个值。
  • 分配和释放内存。在开始时，Q可能需要为局部变量分配空间，而在返回前，又必须释放这些存储空间。

• x86-64的过程实现包括一组特殊的指令和一些对机器资源（例如寄存器和程序内存）使用的约定规则。它遵循了被认为是最低要求策略的方法，只实现上述机制中每个过程所必需的那些。

运行时栈

• C语言过程调用机制的一个关键特性（大多数其他语言也是如此）在于使用了栈数据结构提供的后进先出的内存管理原则。

• 在过程P调用过程Q的例子中

  • 当Q在执行时，P以及所有在向上追溯到P的调用链中的过程，都是暂时被挂起的。当Q运行时，它只需要为局部变量分配新的存储空间，或者设置到另一个过程的调用。
  • **当Q返回时，任何它所分配的局部存储地址空间都可以被释放。**因此，程序可以用栈来管理它的过程所需要的存储空间，栈和程序寄存器存放着传递控制和数据、分配内存所需要的信息。当P调用Q时，控制和数据信息添加到栈尾。当P返回时，这些信息会释放掉。
  

• x86-64的栈

  • x86-64的栈向低地址方向增长，而栈指针%rsp指向栈顶元素。可以用pushq和popq指令将数据存入栈中或是从栈中取出。将栈指针减小一个适当的量可以为没有指定初始值的数据在栈上分配空间。类似地，可以通过增加栈指针来释放空间。

  • 当x86-64过程需要的存储空间超出寄存器能够存放的大小时，就会在栈上分配空间。这个部分称为过程的栈帧(stack frame)，这个空间一般是16字节的整数倍

  • 当前正在执行的过程的帧总是在栈顶。当过程P调用过程Q时，会把返回地址压入栈中，指明当Q返回时，要从P程序的哪个位置继续执行。

  • 在x86-64架构中，寄存器的值通常会被保存到栈帧的特定位置。这个位置取决于寄存器的用途和函数调用的约定

    • 调用者保存约定：当一个函数（调用者）准备调用另一个函数（被调用者）时，它需要保存那些可能会在被调用者中被改变的寄存器的值，寄存器的值会被保存到调用者的栈帧中
    • 被调用者保存约定：当一个函数（被调用者）开始执行时，它需要保存那些在函数执行过程中可能会被改变，且在函数返回后需要恢复的寄存器的值，寄存器的值会被保存到被调用者的栈帧中

  • 在栈帧中，可以保存寄存器的值，分配局部变量空间，为它调用的过程设置参数。大多数过程的栈帧都是定长的，在过程的开始就分配好了。

  • 通过寄存器，过程P可以传递最多6个整数值(也就是指针和整数)，但是如果Q需要更多的参数，P可以在调用Q之前在自己的栈帧里存储好这些参数。

    • 为了提高空间和时间效率，x86-64过程只分配自己所需要的栈帧部分。例如，许多过程有6个或者更少的参数，那么所有的参数都可以通过寄存器传递。
    • 实际上，许多函数甚至根本不需要栈帧。当所有的局部变量都可以保存在寄存器中，而且该函数不会调用任何其他函数(有时称之为叶子过程，此时把过程调用看做树结构)时，就可以这样处理。例如，到目前为止我们仔细审视过的所有函数都不需要栈帧。

转移控制

转移控制指令

• 将控制从函数P转移到函数Q只需要简单地把程序计数器(PC)设置为Q的代码的起始位置。

• 不过，当稍后从Q返回的时候，处理器必须记录好它需要继续P的执行的代码位置。在x86-64机器中，这个信息是用指令call Q调用过程Q来记录的。

  • 该指令会把地址A压入栈中，并将PC设置为Q的起始地址。压入的地址A被称为返回地址，是紧跟在call指令后面的那条指令的地址。
  • 对应的指令ret会从栈中弹出地址A，并把PC设置为A。

• call和ret指令的一般形式(OBJDUMP产生的反汇编输出中为callq和retq，添加的后缀q是为了强调是x86-64版本的调用和返回，而不是IA32的)：

  指令	描述
  call Lable	过程调用
  call *Operand	过程调用
  ret	从过程调用中返回

• call指令有一个目标，即指明被调用过程起始的指令地址。同跳转一样，调用可以是直接的，也可以是间接的。

  • 在汇编代码中，直接调用的目标是一个标号，而间接调用的目标是“*”后面跟一个操作数指示符，使用寄存器或者内存索引。

转移控制指令示例

• 示例1，比如main函数调用mulstore函数

  ;Beginning of function multstore
  0000000000400540 <multstore>:
  400540: 53							push	%rbx
  400541: 48 89 d3					mov		%rdx,%rbx
  . . .
  ;Return from function multstore
  40054d: c3							retq
  . . .
  ;Call to multstore from main
  400563: e8 d8 ff ff ff				callq	400540 <multstore>
  400568: 48 8b 54 24 08				mov		0x8(%rsp), %rdx

  
  • 在main函数中，地址为0x400563的call指令调用函数multstore。
  • call指令把PC的值修改为mulstore函数的开始位置400540，并且把下一条的mov指令的地址400568压入栈中
  • mulstore函数中retq指令弹出栈中的400568，返回main函数

• 示例2，从函数调用中看返回值是怎么实现的

  ;Disassembly of leaf(long y)
  ;y in %rdi
  0000000000400540 <leaf>:
  	400540: 48 8d 47 02				lea	0x2(%rdi), %rax 	;L1: y+2
  	400544: c3						retq					;L2: Return
  0000000000400545 <top>:
  ;Disassembly of top(long x)
  ;x in %rdi
  	400545: 48 83 ef 05				sub $0x5, %rdi			;T1: x-5
  	400549: e8 f2 ff ff ff			callq 400540 <leaf>		;T2: Call leaf(x-5)
  	40054e: 48 01 c0				add	%rax, %rax			;T3: Double result
  	400551: c3						retq					;T4: Return
  	
  . . .
  ;Call to top from function main
  	40055b: e8 e5 ff ff ff			callq 400545 <top>		;M1: Call top(100)
  	400560: 48 89 c2				mov	%rax, %rdx			;M2: Resume

  • 函数的调用过程为main调用top(100)，然后top调用leaf(95)。函数leaf向top返回97，然后top向main返回194 。
  
  • 注意寄存器%rdi和%rax的变化，实际上%rdi是用来存储入参，而%rax是用来存储返回值的。
  • 栈顶指针存入调用者PC下一个指令的地址，地址大小为8字节即%rsp减8

数据传送

数据传输方式

• 当调用一个过程时，除了要把控制传递给它并在过程返回时再传递回来之外，过程调用还可能包括把数据作为参数传递，而从过程返回还有可能包括返回一个值。x86-64中，大部分过程间的数据传送是通过寄存器实现的。

• 当过程P调用过程Q时，P的代码必须首先把参数复制到适当的寄存器中。类似地，当Q返回到P时，P的代码可以访问寄存器%rax中的返回值。

• x86-64中，可以通过寄存器最多传递6个整型（即整数和指针）参数。寄存器的使用是有特殊顺序的，寄存器使用的名字取决于要传递的数据类型的大小。

• 如下图，会根据参数在参数列表中的顺序为它们分配寄存器。可以通过64位寄存器适当的部分访问小于64位的参数。

  

• 如果一个函数有大于6个整型参数，超出6个的部分就要通过栈来传递。假设过程P调用过程Q，有n个整型参数，且n>6。那么P的代码分配的栈帧必须要能容纳7到n号参数的存储空间，参数7位于栈顶

• 通过栈传递参数时，所有的数据大小都向8的倍数对齐。参数到位以后，程序就可以执行call指令将控制转移到过程Q了。过程Q可以通过寄存器访问参数，有必要的话也可以通过栈访问。

• 特殊的，如果过程的参数是结构或者返回值是结构，有特殊的约定，可见习题3.67。简单来说

  • 结构作为函数的参数，传参时结构参数不作为显式的参数传递，而是约定存储在调用者的栈帧的栈顶。
  • 结构作为函数的返回值，调用函数之前在调用者的栈帧上分配内存空间，并将内存空间的地址作为参数存入寄存器。

数据传输方式示例

• C函数proc。这个函数有8个参数，包括字节数不同的整数(8、4、2和1)和不同类型的指针

  void proc(long a1, long *a1p, int a2, int *a2p, 
            short a3, short *a3p, char a4, char *a4p){
      *a1p += a1;
      *a2p += a2;
      *a3p += a3;
      *a4p += a4;
  }

  生成的汇编代码

  ;void proc(a1 , a1p, a2 , a2p, a3, a3p, a4 ,a4p)
  ;Arguments passed as follows:
  ;ai in %rdi          (64 bits)
  ;a1p in %rsi         (64 bits)
  ;a2 in %edx          (32 bits)
  ;a2p in %rcx         (64 bits)
  ;a3 in %r8w          (16 bits)
  ;a3p in %r9          (64 bits)
  ;a4 at %rsp+8        (8 bits)
  ;a4p at %rsp+16      (64 bits)
  proc:
      movq    16(%rsp), %rax      ;Fetch a4p(64 bits)
      addq    %rdi, (%rsi)        ;*a1p += a1 (64 bits)
      addl    %edx, (%rcx)        ;*a2p += a2(32 bits)
      addw    %r8w, (%r9)         ;*a3p += a3(16 bits)
      movl    8(%rsp), %edx       ;Fetch a4(8 bits)
      addb    %dl, (%rax)         ;*a4p += a4(8 bits)
      ret                         ;Return

• 前面6个参数通过寄存器传递，后面2个通过栈传递。作为过程调用的一部分，返回地址被压入栈中。因而这两个参数位于相对于栈指针距离为8和16的位置。

  

局部存储

栈上的局部存储

• 到目前为止都不需要超出寄存器大小的本地存储区域。不过有些时候，局部数据必须存放在内存中，常见的情况包括：

  • 寄存器不足够存放所有的本地数据。

  • 对一个局部变量使用地址运算符＆，因此必须能够为它产生一个地址。

  • 某些局部变量是数组或结构，因此必须能够通过数组或结构引用被访问到

• 过程通过减小栈指针在栈上分配空间。分配的结果作为栈帧的一部分，标号为 局部变量

栈上的局部存储示例

• 示例1是一个处理地址运算符的例子。函数swap_add交换指针xp和yp指向的两个值，并返回这两个值的和。函数caller创建到局部变量arg1和arg2的指针，把它们传递给swap_add。

  long swap_add(long *xp, long *yp){
      long x = *xp;
      long y = *yp;
      *xp = y;
      *yp = x;
      return x + y;
  }
  long caller(){
      long arg1 = 534;
      long arg2 = 1057;
      long sum = swap_add(&arg1, &arg2);
      long diff = arg1 - arg2;
      return sum * diff;
  }

  其汇编代码为：

  ;long caller()
  caller:
      subq    $16, %rsp       ;Allocate 16 bytes for stack frame
      movq    $534, (%rsp)    ;store 534 in arg1
      movq    $1057, 8(%rsp)  ;store 1057 in arg2
      leaq    8(%rsp), %rsi   ;Compute &arg2 as second argument
      movq    %rsp, %rdi      ;Compute &arg1 as first argument
      call    swap_add        ;Call swap_add(&arg1 , &arg2)
      movq    (%rsp), %rdx    ;Get arg1
      subq    8(%rsp), %rdx   ;Compute diff = arg1 - arg2
      imulq   %rdx, %rax      ;compute sum * diff
      addq    $16, %rsp       ;Deallocate stack frame
      ret                     ;Return

  • caller的代码开始的时候把栈指针减掉了16；实际上这就是在栈上分配了16个字节。
  • S表示栈指针的值，可以看到这段代码计算&arg2为S+8，而&arg1为S。因此可以推断局部变量arg1和arg2存放在栈帧中相对于栈指针偏移量为0和8的地方。
  • 当对swap_add的调用完成后，caller的代码会从栈上取出这两个值，计算它们的差，再乘以swap_add在寄存器%rax中返回的值。
  • 最后，该函数把栈指针加16，释放栈帧

• 示例2：一个必须在栈上分配局部变量存储空间的函数，同时还要向有8个参数的函数proc传递值

  long cal1_proc(){
      long x1 = 1; int x2 = 2;
      short x3 = 3;char x4 = 4;
      proc(x1, &x1, x2, &x2, x3, &x3, x4, &x4);
      return (x1 + x2) * (x3 - x4);
  }

  调用函数生成的汇编代码:

        ;long call_proc()
   1    call_proc:
            ;set up arguments to proc
   2        subq    $32, %rsp               ;Allocate 32-byte stack frame
   3        movq    $1, 24(%rsp)            ;Store 1 in &x1
   4        movl    $2, 20(%rsp)            ;store 2 in &x2
   5        movw    $3, 18(%rsp)            ;store 3 in &x3
   6        movb    $4, 17(%rsp)            ;store 4 in &x4
   7        leaq    17(%rsp), %rax          ;Create &x4
   8        movq    %rax, 8(%rsp)           ;store &x4 as argument 8
   9        movl    $4, (%rsp)              ;Store 4 as argument 7
  10        leaq    18(%rsp), %r9           ;Pass &x3 as argument 6
  11        movl    $3, %r8d                ;Pass 3 as argument 5
  12        leaq    20(%rsp), %rcx          ;Pass &x2 as argument 4
  13        movl    $2, %edx                ;Pass 2 as argument 3
  14        leaq    24(%rsp), %rsi          ;Pass &x1 as argument 2
  15        movl 	$1, %edi                ;Pass 1 as argument 1
            ;Call proc
  16        call proc
            ;Retrieve changes to memory
  17        movslq  20(%rsp), %rdx          ;Get x2 and convert to long
  18        addq    24(%rsp), %rdx          ;Compute x1+x2
  19        movswl  18(%rsp), %eax          ;Get x3 and convert to int
  20        movsbl  17(%rsp), %ecx          ;Get x4 and convert to int
  21        subl    %ecx, %eax              ;Compute x3-x4
  22        cltq                            ;Convert to long
  23        imulq   %rdx, %rax              ;Compute (x1+x2)*(x3-x4)
  24        addq    $32, %rsp               ;Deallocate stack frame
  25        ret                             ;Return

  • 代码中一大部分(第2～15行)是为调用proc做准备。其中包括为局部变最和函数参数建立栈帧，将函数参数加载至寄存器
  
  • 在栈上分配局部变量x1～x4，它们大小不同：24～31(x1)，20~23(x2)，18～19(x3)和17(x4)。用leaq指令生成到这些位置的指针(第7、10、12和14行)。参数7(值为4)和8(指向x4的位置的指针)存放在栈中相对于栈指针偏移量为0和8的地方。
  • 当调用过程proc时，参数7和8现在位于相对于栈指针偏移量为8和16的地方，因为返回地址这时已经被压人栈中了。
  • 当程序返回call_proc时，代码会取出4个局部变量(第17～20行)，并执行最终的计算。在程序结束前，把栈指针加32，释放这个栈帧。

寄存器中的局部存储空间

• 寄存器组是唯一被所有过程共享的资源。虽然在给定时刻只有一个过程是活动的，我们仍然必须确保当一个过程（调用者）调用另一个过程（被调用者）时，被调用者不会覆盖调用者稍后会使用的寄存器值。
• 为此，x86-64采用了一组统一的寄存器使用惯例，所有的过程（包括程序库）都必须遵循。
  • 根据惯例，寄存器%rbx、%rbp和%r12~%r15被划分为 被调用者保存寄存器 。当过程P调用过程Q时，Q必须保存这些寄存器的值，保证它们的值在Q返回到P时与Q被调用时是一样的。
    • 过程Q保存一个寄存器的值不变，要么就是不去改变它；要么就是把原始值压入栈中，改变寄存器的值，然后在返回前从栈中弹出旧值。压入寄存器的值会在栈帧中创建标号为 被保存的寄存器 的一部分。
    • 有了这条惯例，P的代码就能安全地把值存在被调用者保存寄存器中（当然，要先把之前的值保存到栈上），调用Q，然后继续使用寄存器中的值，不用担心值被破坏。
  • 所有其他的寄存器，除了栈指针%rsp，都分类为调用者保存寄存器。这就意味着任何函数都能修改它们。
    • 可以这样来理解 调用者保存 这个名字：过程P在某个此类寄存器中有局部数据，然后调用过程Q。因为Q可以随意修改这个寄存器，所以在调用之前首先保存好这个数据是P(调用者)的责任。

寄存器中的局部存储空间示例

• 函数P两次调用Q。在第一次调用中，必须保存x的值以备后面使用。类似地，在第二次调用中，也必须保存Q(y)的值。

  long P(long x, long y){
      long u = Q(y);
      long v = Q(x);
      return u + v;
  }

  调用函数生成的汇编代码：

  	;long P(long x, long y)
  	;x in %rdi, y in %rsi
  1	P:
  2	    pushq   %rbp        	;save %rbp
  3	    pushq   %rbx        	;Save %rbx
  4	    subq    $8, %rsp    	;Align stack frame
  5	    movq    %rdi, %rbp  	;Save x
  6	    movq    %rsi, %rdi  	;Move y to first argument
  7	    call    Q           	;Call Q(y)
  8	    movq    %rax, %rbx  	;save result
  9	    movq    %rbp, %rdi  	;Move x to first argument
  10	    call    Q           	;call Q(x)
  11	    addq    %rbx, %rax  	;Add saved Q(y) to Q(x)
  12	    addq    $8, %rsp    	;Deallocate last part of stack
  13	    popq    %rbx        	;Restore %rbx
  14	    popq    %rbp        	;Restore %rbp
  15	    ret

  • GCC生成的代码使用了两个被调用者保存寄存器：%rbp保存x和%rbx保存Q(y)。在函数的开头，把这两个寄存器的值保存到栈中(第2~3行)。
  • 在第一次调用Q之前，把参数x复制到%rbp(第5行)。在第二次调用Q之前，把这次调用的结果复制到%rbx(第8行)。
  • 在函数的结尾，(第13~14行)，把它们从栈中弹出，恢复这两个被调用者保存寄存器的值。注意它们的弹出顺序与压入顺序相反，说明了栈的后进先出规则。
  • 第4行和第12行对%rsp的操作是为了对齐栈帧。
    • 对于x86_64架构，大多数函数的栈帧边界都必须是16字节的倍数
    • pushq %rbp：这条指令将%rbp寄存器的值压入栈中，占用8字节的空间。
    • pushq %rbx：这条指令将%rbx寄存器的值压入栈中，再占用8字节的空间。到目前为止，栈帧大小增加了16字节，满足16字节对齐的要求。
    • subq $8, %rsp：这条指令在栈上分配了8字节的空间。此时，栈帧大小增加了8字节，总共24字节，不再满足16字节对齐的要求。
    • call Q：调用函数Q时，返回地址被压入栈中，占用8字节的空间。此时，栈帧大小增加了8字节，总共32字节，恢复到了16字节对齐的状态。
    • 所以，在整个函数P中，尽管有一段时间栈帧大小不是16字节的倍数，但在调用其他函数之前和函数结束时，都保证了栈帧大小满足16字节对齐的要求。

递归过程

• 寄存器和栈的惯例使得x86-64过程能够递归地调用它们自身。每个过程调用在栈中都有它自己的私有空间，因此多个未完成调用的局部变量不会相互影响。

• 此外，栈的原则很自然地就提供了适当的策略，当过程被调用时分配局部存储，当返回时释放存储。

• **递归调用一个函数本身与调用其他函数是一样的。**栈规则提供了一种机制，每次函数调用都有它自己私有的状态信息（保存的返回位置和被调用者保存寄存器的值）存储空间。如果需要，它还可以提供局部变量的存储。

• 示例，递归计算阶乘

  long rfact(long n){
      long result;
      if (n <= 1)
          result = 1;
      else
          result = n * rfact(n - 1);
      return result;
  }

  生成的汇编代码

  ;long rfact(long n)
  ;n in %rdi
  rfact:
  	pushq	%rbx			;Save %rbx
  	movq	%rdi, %rbx		;Store n in callee-saved register
  	movl	$1, %eax		;set return value = 1
  	cmpq	$1, %rdi		;Compare n:1
  	jle		.L35			;If <=，goto done
  	leaq	-1(%rdi), %rdi	;Compute n-1
  	call	rfact			;Call rfact(n-1)
  	imulq	%rbx, %rax		;Multiply result by n
  .L35:						;done:
  	popq	%rbx			;Restore %rbx
  	ret						;Return

数组分配和访问

数组表示原则

• C语言中的数组是一种将标量数据聚集成更大数据类型的方式。

• C语言实现数组的方式非常简单，因此很容易翻译成机器代码。C语言的一个不同寻常的特点是可以产生指向数组中元素的指针，并对这些指针进行运算。在机器代码中，这些指针会被翻译成地址计算。

• 优化编译器非常善于简化数组索引所使用的地址计算。不过这使得C代码和它到机器代码的翻译之间的对应关系有些难以理解。

基本原则

• 对于数据类型T和整型常数N，声明为： T A[N];

• 起始位置表示为 $x_A$。这个声明有两个效果。

  • 首先，它在内存中分配一个L×N字节的连续区域，这里L是数据类型T的大小(单位为字节)。

  • 其次，它引入了标识符A，可以用A来作为指向数组开头的指针，这个指针的值就是 $x_A$。

• 可以用 0~N-1 的整数索引来访问该数组元素。数组元素i会被存放在地址为 $x_A+L\times i$ 的地方。

• x86-64的内存引用指令可以用来简化数组访问。

  • 例如，假设E是一个1个int型的数组，而我们想计算E[i]，在此E的地址存放在寄器%rdx中，而i存放在寄存器%rcx中。

  • 然后，指令 movl (%rdx, %rcx, 4), %eax 会执行地址计算 $x_E+4i$，读这个内存位置的值，并将结果存放到寄存器%eax中。允许的伸缩因子1、2、4和8覆盖了所有基本简单数据类型的大小。

指针运算

• C语言允许对指针进行运算，而计算出来的值会根据该指针引用的数据类型的大小进行伸缩。也就是说，如果p是一个指向类型为T的数据的指针，p的值为 $x_p$，那么表达式 p+i 的值为 $x_p+L\times i$, 这里L是数据类型T的大小。

• 单操作数操作符 & 和 * 可以产生指针和间接引用指针。

  • 也就是，对于一个表示某个对象的表达式 Expr，&Expr 是给出该对象地址的一个指针。
  • 对于一个表示地址的表达式 AExpr，*AExpr 给出该地址处的值。
  • 因此，表达式 Expr 与 *&Expr 是等价的。
  • 可以对数组和指针应用数组下标操作。数组引用A[i]等同于表达式*(A+1)。它计算第i个数组元素的地址，然后访问这个内存位置。

• 假设整型数组E的起始地址和整数索引i分别存放在寄存器%rdx和%rcx中。有以下表达式

  

不同类型的数组

嵌套的数组

• 当我们创建数组的数组时，数组分配和引用的一般原则也是成立的。例如，声明 int A[5][3];

• 等价于下面的声明

  typedef int row3_t[3];
  row3_t A[5];

  • 数据类型row3_t被定义为一个3个整数的数组。数组A包含5个这样的元素，每个元素需要12个字节来存储3个整数。整个数组的大小就是4×5×3=60字节。

  • 数组A还可以被看成一个5行3列的二维数组，用 A[0][0] 到 A[4][2] 来引用。

  • 数组元素在内存中按照 行优先 的顺序排列，意味着第0行的所有元素，可以写作A[0]，后面跟着第1行的所有元素。

    • 这种排列顺序是嵌套声明的结果。将A看作一个有5个元素的数组，每个元素都是3个int的数组，首先是A[0]，然后是A[1]
    

• 要访问多维数组的元素，编译器会以数组起始为基地址，(可能需要经过伸缩的)偏移量为索引，产生计算期望的元素的偏移量，然后使用某种MOV指令。

• 通常来说，对于一个声明如下的数组： T D[R][C];

  • 它的数组元素 D[i][j] 的内存地址为：

    $$\&D[i][j] = x_D+L(C\cdot i+j)\tag{3.1}$$

    • 这里，L是数据类型T以字节为单位的大小。

• 示例，考虑前面定义的 5×3 的整型数组A。假设 $x_A$、i和j分别在寄存器%rdi、%rsi和%rdx中。然后，可以用下面的代码将数组元素 A[i][j] 复制到寄存器%eax中：

  ;A in %rdi, i in %rsi, and j in %rdx
  	leaq	(%rsi, %rsi, 2), %rax	;Compute 3i
  	leaq	(%rdi, %rax ,4), %rax	;Compute xA＋ 12i
  	movl	(%rax, %rdx, 4), %eax	;Read from M[xA + 12i + 4j]

定长数组

• C语言编译器能够优化定长多维数组上的操作代码。这里我们展示优化等级设置为-O1时GCC采用的一些优化。假设我们用如下方式将数据类型fix_matrix声明为16×16的整型数组：

  #define N 16
  typedef int fix_matrix [N][N] ;

• 示例，现在有两个fix_matrix数组A和B，要计算A的行i和B的列k的内积。

  /*Compute i,k of fixed matrix product*/
  int fix_prod_ele(fix_matrix A, fix_matrix B, long i, long k){
      long j;
      int result = 0;
      for (j = 0; j < N; j++)
          result += A[i][j] * B[j][k];
      return result;
  }

• 将代码反编译后，会发现编译器针对定长数组做了一些优化，它去掉了整数索引j，并把所有的数组引用都转换成了指针间接引用

  • 生成一个指针，命名为Aptr，指向A的行1中连续的元素；
  • 生成一个指针，命名为Bptr，指向B的列k中连续的元素；
  • 生成一个指针，命名为Bend，当需要终止该循环时，它会等于Bptr的值。

  int fix_prod_ele_opt(fix_matrix A, fix_matrix B, long i, long k) {
      int *Aptr = &A[i][0]; /* Points to elements in row i of A */
      int *Bptr = &B[0][k]; /* Points to elements in column k of B */
      int *Bend = &B[N][k]; /* Marks stopping point for Bptr */
      int result = 0;
      do {                         /* No need for initial test*/
          result += *Aptr * *Bptr; /* Add next product to sum */
          Aptr++;                  /* Move Aptr to next column */
          Bptr += N;               /* Move Bptr to next row */
      } while (Bptr != Bend);      /* Test for stopping point*/
      return result;
  }

• GCC为函数fix_prod_ele生成的实际汇编代码。4个寄存器的使用如下：%eax保存result，%rdi保存Aptr，%rcx保存Bptr，而%rsi保存Bend。

  ;int fix_prod_ele_opt(fix_matrix A, fix_matrix B, long i, long k)
  ;A in %rdi, B in %rsi, i in %rdx, k in %rcx
  fix_prod_ele:
      salq    $6, %rdx                ;Compute 64 * i
      addq    %rdx, %rdi              ;Compute Aptr = xA + 64i = &A[i][0]
      leaq    (%rsi, %rcx, 4), %rcx   ;Compute Bptr = XB + 4k = &B[0][k]
      leaq    1024(%rcx), %rsi        ;Compute Bend = XB + 4k + 1024 = &B[N][k]
      movl    $0, %eax                ;set result = 0
  .L7:                                ;loop:
      movl    (%rdi), %edx            ;Read *Aptr
      imull   (%rcx), %edx            ;Multiply by *Bptr
      addl    %edx, %eax              ;Add to result
      addq    $4, %rdi                ;Increment Aptr ++
      addq    $64, %rcx               ;Increment Bptr +=N
      cmpq    %rsi, %rcx              ;Compare Bptr:Bend
      jne     .L7                     ;If !=, goto loop
      rep; ret                        ;Return

变长数组

• 历史上，C语言只支持大小在编译时就能确定的多维数组（对第一维可能有些例外）。程序员需要变长数组时不得不用malloc或calloc这样的函数为这些数组分配存储空间，而且不得不显式地编码，用行优先索引将多维数组映射到一维数组

• C99引入了一种功能，允许数组的维度是表达式，在数组被分配的时候才计算出来。在变长数组的C版本中，我们可以将一个数组声明如下： int A[expr1][expr2]

  • 它可以作为一个局部变量，也可以作为一个函数的参数，然后在遇到这个声明的时候，通过对表达式expr1和expr2求值来确定数组的维度。

• 例如要访问n×n数组的元素i、j，我们可以写一个如下的函数：

  int var_ele(long n, int A[n][n], long i, long j) {
        return A[i][j] ;
  }

• 参数n必须在参数 A[n][n] 之前，这样函数就可以在遇到这个数组的时候计算出数组的维度。

• GCC为这个引用函数产生的代码如下所示：

  ;int var_ele(long n, int A[n][n], long i , long j)
  ;n in %rdi, A in %rsi, i in %rdx, j in %rcx
  var_ele:
      imulq   %rdx, %rdi              ;Compute n · i
      leaq    (%rsi, %rdi, 4), %rax   ;Compute xA + 4(n · i)
      movl    (%rax, %rcx, 4), %eax   ;Read from M[xA + 4(n · i) + 4j]
      ret

• 这段代码计算元素i、j的地址为 $x_A+4(n\cdot i)+4j=x_A+4(n\cdot i+ j)$。这个地址的计算类似于定长数组的地址计算

• 不同点在于

  • 由于增加了参数n，寄存器的使用变化了
  • 用了乘法指令来计算n·i(第2行)，而不是用leaq指令来计算3i

• 因此引用变长数组只需要对定长数组做一点儿概括。动态的版本必须用乘法指令对i伸缩n倍，而不能用一系列的移位和加法。在一些处理器中，乘法会招致严重的性能处罚，但是在这种情况中无可避免。

变长数组优化示例

• 在一个循环中引用变长数组时，编译器常常可以利用访问模式的规律性来优化索引的计算。以计算两个n×n矩阵A和B乘积的元素i、k为例子。

  /*Compute i,k of variable matrix product*/
  int var_prod_ele(long n, int A[n][n], int B[n][n], long i, long k){
      long j;
      int result = 0;
      for (j = 0; j < n; j++)
          result += A[i][j] * B[j][k];
      return result;
  }

  优化后的C代码

  /* Compute i,k of variable matrix product */
  int var_prod_ele_opt(long n, int A[n][n], int B[n][n], long i, long k) {
      int *Arow = A[i];
      int *Bptr = &B[0][k];
      int result = 0;
      long j;
      for (j = 0; j < n; j++) {
          result += Arow[j] * *Bptr;
          Bptr += n;
      }
      return result;
  }

  • 反编译和主要的优化是，之前直接索引 A[i][j] 需要用到乘法，而我们尽量使用指针来进行加法。

• var_prod_ele的循环的汇编代码：

  ;Registers: n in %rdi, Arow in %rsi, Bptr in %rcx
  ;4n in %r9, result in %eax, j in %rdx
  .L24:                                   ;loop:
      movl    (%rsi, %rdx, 4), %r8d       ;Read Arow[j]
      imull   (%rcx), %r8d                ;Multiply by *Bptr
      addl    %r8d, %eax                  ;Add to result
      addq    $1, %rdx                    ;j++
      addq    %r9, %rcx                   ;Bptr += n
      cmpq    %rdi, %rdx                  ;Compare j :n
      jne     .L24                        ;If !=,goto loop

  • 我们看到程序既使用了伸缩过的值4n(寄存器%r9)来增加Bptr，也使用了n的值(寄存器%rdi)来检查循环的边界。C代码中并没有体现出需要这两个值，但是由于指针运算的伸缩，才使用了这两个值。
  • 如果允许使用优化，GCC能够识别出程序访问多维数组的元素的步长。然后生成的代码会避免直接使用乘法计算内存位置。这些优化能显著提高程序的性能。

异质的数据结构

C语言提供了两种将不同类型的对象组合到一起创建数据类型的机制：结构(structure)，用关键字struct来声明，将多个对象集合到一个单位中；联合(union)，用关键字union来声明，允许用几种不同的类型来引用一个对象。

结构

• C语言的struct声明创建一个数据类型，将可能不同类型的对象聚合到一个对象中。用名字来引用结构的各个组成部分。

• 类似于数组的实现，结构的所有组成部分都存放在内存中一段连续的区域内，而指向结构的指针就是结构第一个字节的地址。

• 编译器维护关于每个结构类型的信息，指示每个字段(field)的字节偏移。它以这些偏移作为内存引用指令中的位移，从而产生对结构元素的引用。

• 考虑下面这样的结构声明：

  struct rec {
      int i;
      int j;
      int a[2];
      int *p;
  };

  • 这个结构包括4个字段：两个4字节int、一个由两个类型为int的元素组成的数组和一个8字节整型指针，总共是24个字节：

    

  • 可以观察到，数组a是嵌入到这个结构中的。上图中顶部的数字给出的是各个字段相对于结构开始处的字节偏移。

    • 如只用加上偏移量8+4×1=12，就可以得到指针&(r->a[1])。

    • struct rec*类型的变量r放在寄存器%rdi中，在寄存器%rsi中的长整数变量i，我们可以用一条指令产生指针&(r->a[i])的值:

    ;Registers: r in %rdi, i in %rsi
    leaq	8(%rdi, %rsi, 4), %rax		;Set %rax to &r->a[i]

  • 示例，实现 r->p = &r->a[r->i + r->j];

    • 为了访问结构的字段，编译器产生的代码要将结构的地址加上适当的偏移。
    • 要产生一个指向结构内部对象的指针，我们只需将结构的地址加上该字段的偏移量。

    ;Registers: r in %rdi
    movl    4(%rdi), %eax           ;Get r->j
    addl    (%rdi), %eax            ;Add r->i
    cltq                            ;Extend to 8 bytes
    leaq    8(%rdi, %rax, 4), %rax  ;Compute &r->a[r->i +r->j]
    movq    %rax, 16(%rdi)          ;Store in r->p

• 结构的各个字段的选取完全是在编译时处理的。机器代码不包含关于字段声明或字段名字的信息。

联合

• 联合提供了一种方式，能够规避C语言的类型系统，允许以多种类型来引用一个对象。联合声明的语法与结构的语法一样，只不过语义相差比较大。它们是用不同的字段来引用相同的内存块。

• 考虑下面的声明：

  struct S3 {
      char c;
      int i[2];
      double v;
  };
  union U3 {
      char c;
      int i [2];
      double v;
  };

  • 在一台x86-64 Linux机器上编译时，字段的偏移最、数据类型S3和U3的完整大小如下：

    类型	c	i	v	大小
    S3	0	4	16	24
    U3	0	0	0	8

  • 对于类型union U3*的指针p，p->c、p->i[0]和p->v引用的都是数据结构的起始位置。一个联合的总的大小等于它最大字段的大小。

• 在一些下上文中，联合十分有用。但是，它也能引起一些讨厌的错误，因为它们绕过了C语言类型系统提供的安全措施。一种应用情况是，我们事先知道对一个数据结构中的两个不同字段的使用是互斥的，那么将这两个字段声明为联合的一部分，而不是结构的一部分，会减小分配空间的总量。

• 示例：假设我们想实现一个二叉树的数据结构，每个叶子节点都有两个double类型的数据值，而每个内部节点都有指向两个孩子节点的指针，但是没有数据。

  • 如果声明为结构，那么每个节点需要32个字节，每种类型的节点都要浪费一半的字节。

    struct node_s {
        struct node_s *left;
        struct node_s *right;
        double data[2];
    };

  • 如果声明为联合，那么，每个节点就只需要16个字节。

    union node_u {
        struct {
            union node_u *left;
            union node_u *right;
        } internal;
        double data[2];
    };

  • 不过，如果这样编码，就没有办法来确定一个给定的节点到底是叶子节点，还是内部节点。

  • 通常的方法是引入一个枚举类型，定义这个联合中可能的不同选择，然后再创建一个结构，包含一个标签字段和这个联合：

    typedef enum { N_LEAF, N_INTERNAL} nodetype_t;
    struct node_t {
        nodetype_t type;
        union {
            struct {
                struct node_t *left;
                struct node_t *right;
            } internal;
            double data[2];
        } info;
    };

  • 这个结构总共需要24个字节：type是4个字节，info要16个字节，我们后面很快会谈到，在字段type和联合的元素之间需要4个字节的填充，所以整个结构大小为4+4＋16=24。

• 联合还可以用来访问不同数据类型的位模式。

  • 例如，假设我们使用简单的强制类型转换将一个double类型的值d转换为unsigned long类型的值u： unsigned long u = (unsigned long)d

  • 值u会是d的整数表示。除了d的值为0.0的情况以外，u的位表示会与d的很不一样。

  • 如果我们以一种数据类型来存储联合中的参数，又以另一种数据类型来访问它。结果会是u具有和d一样的位表示，包括符号位字段、指数和尾数。

    unsigned long double2bits(double d) {
        union {
            doubled;
            unsigned long u;
        } temp;
        temp.d = d;
        return temp.u;
    }

• 当用联合来将各种不同大小的数据类型结合到一起时，字节顺序问题就变得很重要了。

  • 例如，以两个4字节的unsigned的位模式，创建一个8字节的double

  double uu2double(unsigned wordO, unsigned word1)
      union {
          double d;
          unsigned u[2];
      } temp;
      temp.u[O] = wordO;
      temp.u[1] = word1;
      return temp.d;
  }

  • 在x86-64这样的小端法机器上，参数word0是d的低位4个字节，而word1是高位4个字节。在大端法机器上，这两个参数的角色刚好相反。

数据对齐

• 许多计算机系统对基本数据类型的合法地址做出了一些限制，要求某种类型对象的地址必须是某个值K(通常是2、4或8)的倍数。这种对齐限制简化了形成处理器和内存系统之间接口的硬件设计。

  • 例如，假设一个处理器总是从内存中取8个字节，则地址必须为8的倍数。
  • 如果我们能保证将所有的double类型数据的地址对齐成8的倍数，那么就可以用一个内存操作来读或者写值了。
  • 否则，我们可能需要执行两次内存访问，因为对象可能被分放在两个8字节内存块中。

• 无论数据是否对齐，x86-64硬件都能正确工作。Intel还是建议要对齐数据以提高内存系统的性能。对齐原则是任何K字节的基本对象的地址必须是K的倍数。可以看到这条原则会得到如下对齐：

  K	类型
  1	char
  2	short
  4	int,float
  8	long,double,char*

  • 确保每种数据类型都是按照指定方式来组织和分配，即每种类型的对象都满足它的对齐限制，就可保证实施对齐。
  • 编译器在汇编代码中放入命令，指明全局数据所需的对齐。例如：.align 8，保证了它后面的数据的起始地址是8的倍数。

• 对于包含结构的代码，编译器可能需要在字段的分配中插入间隙，以保证每个结构元素都满足它的对齐要求。而结构本身对它的起始地址也有一些对齐要求。

  • 例如，对于结构声明：

  struct S1 {
      int i;
      char c;
      int j;
  };

• 假设编译器用最小的9字节分配，是不可能满足字段i(偏移为0)和j(偏移为5)的4字节对齐要求的。

  

• 编译器在字段c和j之间插入一个3字节的间隙。结果j的偏移量为8，而整个结构的大小为12字节

  

• 编译器结构的末尾可能需要一些填充，这样结构数组中的每个元素都会满足它的对齐要求。

  • 例如，对于结构声明：

    struct S2 {
        int i;
        int j;
        char c;
    };

  • 如果将这个结构打包成9个字节，结构的每个字段的起始地址满足对齐要求。但考虑到结构数组 struct S2 d[4] 的对齐要求，编译器会为S2分配12个字节，最后3个字节是浪费的空间

    

• 观察下面五个例子进行理解

  

• 因此，结构体的填充模式可以总结为

  • 首先，结构体内的各个字段，都要满足其数据类型的对齐要求，即任何K字节的基本对象的地址必须是K的倍数，如int类型的数据应该存储在内存地址是4的倍数的位置。对于数组元素直接拆开看。
  • 其次，结构体中的字段是一个接着一个放置的，但是为了满足其数据类型的对齐要求，有时候需要有空隙。
  • 最后，结构体总的大小也需要对齐，其对齐的长度为有效对齐长度。
    • 有效对齐长度为结构体中最长的数据类型的长度和系统内置最长数据类型的长度的较小值。
    • 系统内置最长数据类型的长度用 #pram pack 定义，一般可以认为32位是4，64位是8。

• 强制对齐

  • 对于大多数x86-64指令来说，保持数据对齐能够提高效率，但是它不会影响程序的行为。

  • 另一方面，如果数据没有对齐，某些型号的Intel和AMD处理器对于有些实现多媒体操作的SSE指令，就无法正确执行。

  • 这些指令对16字节数据块进行操作，**在SSE单元和内存之间传送数据的指令要求内存地址必须是16的倍数。**任何试图以不满足对齐要求的地址未访问内存都会导致异常，默认的行为是程序终止。

  • 任何针对x86-64处理器的编译器和运行时系统都必须保证分配用来保存可能会被SSE寄存器读或写的数据结构的内存，都必须满足16字节对齐。这个要求有两个后果：

    • 任何内存分配函数(alloca、malloc、calloc或realloc)生成的块的起始地址都必须是16的倍数。
    • 大多数函数的栈帧的边界都必须是16宇节的倍数。(这个要求有一些例外)

  • 较近版本的x86-64处理器实现了AVX多媒体指令。除了提供SSE指令的超集，支持AVX的指令并没有强制性的对齐要求。

在机器级程序中将控制与数据结合起来

理解指针

• 指针是C语言的一个核心特色。它们以一种统一方式，对不同数据结构中的元素产生引用。

• **每个指针都对应一个类型。**这个类型表明该指针指向的是哪一类对象。

  以下面的指针声明为例：

  int *ip;
  char **cpp;

  • 变量ip是一个指向int类型对象的指针，而cpp指针指向的对象自身就是一个指向char类型对象的指针。
  • 如果对象类型为T，那么指针的类型为 T*。特殊的 void* 类型代表通用指针。
    • 比如说，malloc函数返回一个通用指针，然后通过显式强制类型转换或者赋值操作那样的隐式强制类型转换，将它转换成一个有类型的指针。
    • 指针类型不是机器代码中的一部分；它们是C语言提供的一种抽象，帮助程序员避免寻址错误。

• 每个指针都有一个值，这个值是某个指定类型的对象的地址。

  • 特殊的NULL(0)值表示该指针没有指向任何地方。

• **指针用 & 运算符创建。**这个运算符可以应用到任何lvalue类的C表达式上

  • lvalue意指可以出现在赋值语句左边的表达式。这样的例子包括变量以及结构、联合和数组的元素。
  • 因为leaq指令是设计用来计算内存引用的地址的，&运算符的机器代码实现常常用这条指令来计算表达式的值。

• * 操作符用于间接引用指针。

  • 其结果是一个值，它的类型与该指针的类型一致。
  • 间接引用是用内存引用来实现的，要么是存储到一个指定的地址，要么是从指定的地址读取。

• **数组与指针紧密联系。**一个数组的名字可以像一个指针变量一样引用（但是不能修改）

  • 数组引用(例如a[3])与指针运算和间接引用(例如*(a+3))有一样的效果。

  • 数组引用和指针运算都需要用对象大小对偏移量进行伸缩。

• 将指针从一种类型强制转换成另一种类型，只改变它的类型，而不改变它的值。

  • 强制类型转换的一个效果是改变指针运算的伸缩。
  • 例如，如果p是一个 char* 类型的指针，它的值为p，那么表达式 (int*)p+7 计算为p+28，而(int*)(p+7)计算为p+7。

• 指针也可以指向函数。

  • 函数指针的值是该函数机器代码表示中第一条指令的地址。这提供了一个很强大的存储和向代码传递引用的功能，这些引用可以被程序的某个其他部分调用。

  • 例如，如果我们有一个函数，用下面这个原型定义： int fun(int x, int *p)

    • 然后，我们可以声明一个指针fp, 将它赋值为这个函数

    int (*fp)(int, int*);
    fp = fun;

    • 然后用这个指针来调用这个函数

    int y = 1;
    int result= fp(3, &y);

• 如何理解函数指针的声明？

  对于以下声明： int (*f)(int*) 中

  • (*f) 指的是，f是一个指向函数的指针，这个函数以一个 int* 作为参数。
  • *f 两边的括号是必需的，否则声明 int *fp(int*) 变成 (int*) fp(int*)

使用GDB调试器

• GNU的调试器GDB提供了许多有用的特性，支持机器级程序的运行时评估和分析。

• DDD是GDB的一个扩展，提供了图形用户界面。

• 用下面的命令行来启动GDB：

  gdb prog

• 通常的方法是在程序中感兴趣的地方附近设置断点。

  • 断点可以设置在函数入口后面，或是一个程序的地址处。
  • 程序在执行过程中遇到一个断点时，程序会停下来，并将控制返回给用户。
  • 在断点处，我们能够以各种方式查看各个寄存器和内存位置。
  • 我们也可以单步跟踪程序，一次只执行几条指令，或是前进到下一个断点。

内存越界引用和缓冲区溢出

内存越界引用

• C对于数组引用不进行任何边界检查，而且局部变量和状态信息(例如保存的寄存器值和返回地址)都存放在栈中。

• 如果这两种情况结合到一起，发生了对于合法范围外的内存的操作，就能导致严重的程序错误，对越界的数组元素的写操作会破坏存储在栈中的状态信息。当程序使用这个被破坏的状态，试图重新加载寄存器或执行ret指令时，就会出现很严重的错误。

• 一种特别常见的状态破坏称为缓冲区溢出(buffer overflow)。通常，在栈中分配某个字符数组来保存一个字符串，但是字符串的长度超出了为数组分配的空间。

• 示例，缓冲区溢出

  /*Implementation of library function gets()*/
  char *gets(char *s){
      int c;
      char *dest = s;
      while ((c = getchar()) != '\n' && c != EOF)
          *dest++ = c;
      if (c == EOF && dest == s)
          /* No characters read */
          return NULL;
      *dest++ = '\0'; /* Terminate string */
      return s;
  }
  /* Read input line and write it back */
  void echo(){
      char buf[8]; /* way too small ! */
      gets(buf);
      puts(buf);
  }

  • gets从标准输入读入一行，在遇到一个回车换行字符或某个错误情况时停止。它将这个字符串复制到参数s指明的位置，并在字符串结尾加上null字符。

  • 问题在于，没有办法确定是否为保存整个字符串分配了足够的空间。在echo示例中，我们故意将缓冲区设得非常小，只有8 个字节长。任何长度超过7个字符的字符串都会导致写越界。

  • GCC为echo产生的汇编代码，看看栈是如何组织的：

    ;void echo()
    echo:
        subq    $24, %rsp       ;Allocate 24 bytes on stack
        movq    %rsp, %rdi      ;Compute buf as %rsp
        call    gets            ;Call gets
        movq    %rsp, %rdi      ;Compute buf as %rsp
        call    puts            ;Call puts
        addq    $24, %rsp       ;Deallocate stack space
        ret                     ;Return

  • 该程序把栈指针减去了24(第2行)，在栈上分配了24个字节。字符数组buf位于栈顶，可以看到，%rsp被复制到%rdi作为调用gets和puts的参数。这个调用的参数和存储的返回指针之间的16字节是未被使用的。

    

  • 只要用户输入不超过7个字符，gets返回的字符串(包括结尾的null)就能够放进为buf分配的空间里。不过，长一些的字符串就会导致gets覆盖栈上存储的某些信息。随着字符串变长，下面的信息会被破坏：

  - 字符串到23个字符之前都没有严重的后果，但是超过以后，返回指针的值以及更多可能的保存状态会被破坏。如果存储的返回地址的值被破坏了，那么ret指令(第8行)会导致程序跳转到一个完全意想不到的位置。

• 缓冲区溢出的一个更加致命的使用就是让程序执行它本来不应该执行的函数。这是一种最常见的通过计算机网络攻击系统安全的方法。

  • 输入给程序一个字符串，这个字符串包含一些可执行代码的字节编码，称为攻击代码(exploit code)
  • 另外，还有一些字节会用一个指向攻击代码的指针覆盖返回地址。那么，执行ret指令的效果就是跳转到攻击代码。

对抗缓冲区溢出攻击

• 缓冲区溢出攻击的普遍发生给计算机系统造成了许多的麻烦。现代的编译器和操作系统实现了很多机制，以避免遭受这样的攻击，限制入侵者通过缓冲区溢出攻击获得系统控制的方式

栈随机化

• 安全单一化(security monoculture)
  • 为了在系统中插入攻击代码，攻击者既要插入代码，也要插入指向这段代码的指针，这个指针也是攻击字符串的一部分。产生这个指针需要知道这个字符串放置的栈地址。
  • 在过去，程序的栈地址非常容易预测。对于所有运行同样程序和操作系统版本的系统来说，在不同的机器之间，栈的位置是相当固定的。因此，如果攻击者可以确定一个常见的Web服务器所使用的栈空间，就可以设计一个在许多机器上都能实施的攻击。这种现象常被称作安全单一化。
• 栈随机化的思想使得栈的位置在程序每次运行时都有变化。因此，即使许多机器都运行同样的代码，它们的栈地址都是不同的。
  • 实现的方式是：程序开始时，在栈上分配一段0~n字节之间的随机大小的空间。
  • 程序不使用这段空间，但是它会导致程序每次执行时后续的栈位置发生了变化。分配的范围n 必须足够大，才能获得足够多的栈地址变化，但是又要足够小，不至于浪费程序太多的空间。
• 在Linux系统中，栈随机化已经变成了标准行为。它是更大的一类技术中的一种，这类技术称为地址空间布局随机化(Address-Space Layout Randomization), 或者简称ASLR
  • 采用ASLR，每次运行时程序的不同部分，包括程序代码、库代码、栈、全局变最和堆数据，都会被加载到内存的不同区域。
  • 这就意味着在一台机器上运行一个程序，与在其他机器上运行同样的程序，它们的地址映射大相径庭。这样才能够对抗一些形式的攻击。
• 通过一些方式，能够用蛮力克服随机化，他可以反复地用不同的地址进行攻击。
  • 一种常见的把戏是在实际的攻击代码前插入很长一段的nop(no operatioin的缩写)指令。执行这种指令除了对程序计数器加一，使之指向下一条指令之外，没有任何的效果。
  • 只要攻击者能够猜中这段序列中的某个地址，程序就会经过这个序列，到达攻击代码。这个序列常用的术语是 空操作雪橇(nop sled)，意思是程序会滑过这个序列。
  • 栈随机化和其他一些ASLR技术能够增加成功攻击一个系统的难度，但是也不能提供完全的安全保障。

栈破坏检测

• 计算机的第二道防线是能够检测到何时栈已经被破坏。

  • 破坏通常发生在当超越局部缓冲区的边界时。在C语言中，没有可靠的方法来防止对数组的越界写。
  • 但是，我们能够在发生了越界写的时候，在造成任何有害结果之前，尝试检测到它。

• GCC版本在产生的代码中加入了一种栈保护者(stack protector)机制，来检测缓冲区越界。

  • 其思想是在栈帧中任何局部缓冲区与栈状态之间存储一个特殊调用者的栈帧的金丝雀(canary) 值

    

  • 这个金丝雀值，也称为哨兵(guard value)，是在程序每次运行时随机产生的，因此，攻击者没有简单的办法能够知道它是什么。

  • 在恢复寄存器状态和从函数返回之前，程序检查这个金丝雀值是否被该函数的某个操作或者该函数调用的某个函数的某个操作改变了。如果是的，那么程序异常中止。

  • 栈保护很好地防止了缓冲区溢出攻击破坏存储在程序栈上的状态。它只会带来很小的性能损失，特别是因为GCC只在函数中有局部char类型缓冲区的时候才插入这样的代码。

• 示例，在允许使用栈保护者时来编译echo函数

  	;void echo()
  1	echo :
  2		subq	$24, %rsp			;Allocate 24 bytes on stack
  3		movq	%fs:40, %rax		;Retrieve canary
  4		movq	%rax, 8(%rsp)		;Store on stack
  5		xorl	%eax, %eax			;Zero out register
  6		movq	%rsp, %rdi			;Compute buf as %rsp
  7		call	gets				;Call gets
  8	    movq	%rsp, %rdi			;Compute buf as %rsp
  9		call	puts				;call puts
  10		movq	8(%rsp), %rax		;Retrieve canary
  11		xorq	%fs:40, %rax		;Compare to stored value
  12		je		.L9					;If =, goto ok
  13		call	__stack_chk_fail	;Stack corruptcd!
  14	.L9:							;ok ;
  15		addq	$24, %rsp			;Deallocate stack space
  16		ret

  • 这个版本的函数从内存中读出一个值(第3行)，再把它存放在栈中相对于%rsp偏移量为8的地方。指令参数%fs:40指明金丝雀值是用段寻址(segmented addressing)从内存中读入的
  • 将金丝雀值存放在一个特殊的段中，标志为 只读，这样攻击者就不能覆盖存储的金丝雀值。
  • 在恢复寄存器状态和返回前，函数将存储在栈位置处的值与金丝雀值做比较（通过第11行的xorq指令)。如果两个数相同，xorq指令就会得到0，函数会按照正常的方式完成。非零的值表明栈上的金丝雀值被修改过，那么代码就会调用一个错误处理例程。

限制可执行代码区域

• 最后一招是消除攻击者向系统中插入可执行代码的能力。一种方法是限制哪些内存区域能够存放可执行代码。在典型的程序中，只有保存编译器产生的代码的那部分内存才需要是可执行的。其他部分可以被限制为只允许读和写。
• 许多系统允许控制三种访问形式：读（从内存读数据）、写（存储数据到内存）和执行（将内存的内容看作机器级代码）。
• 以前，x86体系结构将读和执行访问控制合并成一个1位的标志，这样任何被标记为可读的页也都是可执行的。已经实现的很多机制，能够限制一些页是可读但是不可执行的，然而这些机制通常会带来严重的性能损失。
• 内存保护引入 NX(No-Execute，不执行)位，将读和执行访问模式分开，有了这个特性，栈可以被标记为可读和可写，但是不可执行，而检查页是否可执行由硬件来完成，效率上没有损失。

支持变长栈帧

• 到目前为止，我们已经检查了各种函数的机器级代码，但它们有一个共同点，即编译器能够预先确定需要为栈帧分配多少空间。

• 但是有些函数，需要的局部存储是变长的。例如，当函数调用alloca时就会发生这种情况。

  • alloca是一个标准库函数，可以在栈上分配任意字节数量的存储。当代码声明一个局部变长数组时，也会发生这种情况。

• 为了管理变长栈帧，x86-64代码使用寄存器%rbp作为帧指针(frame pointer)(有时称为基指针(base pointer)，这也是%rbp中bp两个字母的由来）

  • 当使用帧指针时，栈帧的组织结构如图。可以看到代码必须把%rbp之前的值保存到栈中，因为它是一个被调用者保存寄存器。
  • 然后在函数的整个执行过程中，都使得%rbp指向那个时刻栈的位置，然后用固定长度的局部变量(例如i)相对于%rbp的偏移量来引用它们。
  

• 示例，一个包含变长数组的例子。

  long vframe(long n, long idx, long *q) {
      long i;
      long *p[n];
      p[0] = &i;
      for (i = 1; i < n; i++)
          p[i] = q;
      return *p[idx];
  }

  • 该函数声明了n个指针的局部数组p，这里n由第一个参数给出。这要求在栈上分配8n个字节，这里n的值每次调用该函数时都会不同。因此编译器无法确定要给该函数的栈帧分配多少空间。
  • 此外，该程序还产生一个对局部变量i的地址引用，因此该变量必须存储在栈中。
  • 在执行过程中，程序必须能够访问局部变量i和数组p中的元素。返回时，该函数必须释放这个栈帧，并将栈指针设置为存储返回地址的位置。

• GCC为函数vframe生成的部分代码。

  	;long vframe (long n, long idx, long *q)
  	;n in %rdi, idx in %rsi, q in %rdx
  	;Only portions of code shown
  1	vframe:
  2	    pushq   %rbp                    ;Save old %rbp
  3	    movq    %rsp, %rbp              ;set frame pointer
  4	    subq    $16, %rsp               ;Allocate space for i (%rsp = s1)
  5	    leaq    22(, %rdi, 8), %rax
  6	    andq    $-16, %rax
  7	    subq    %rax, %rsp              ;Allocate space for array p (%rsp = s2)
  8	    leaq    7(%rsp), %rax
  9	    shrq    $3, %rax
  10	    leaq    0(, %rax, 8), %r8       ;Set %r8 to &p[0]
  11	    movq    %r8, %rcx               ;Set %rcx to &p[0] (%rcx = p)
  	    . . .
  	;Code for initialization loop
  	;i in %rax and on stack, n in %rdi, p in %rcx, q in %rdx
  12	.L3:                                ;loop:
  13	    movq    %rdx, (%rcx, %rax, 8)   ;set p[i] to q
  14	    addq    $1, %rax                ;Increment i
  15	    movq    %rax, -8(%rbp)          ;store on stack
  16	.L2:
  17	    movq    -8(%rbp), %rax          ;Retrieve i from stack
  18	    cmpq    %rdi, %rax              ;Compare i:n
  19	    jl      .L3                     ;If <, goto loop
  	    . . .
  	;Code for function exit
  20	    leave                           ;Restore %rbp and %rsp
  21	    ret                             ;Return

  • 在函数的开始，代码建立栈帧，并为数组p分配空间。首先把%rbp的当前值压入栈中，将%rbp设置为指向当前的栈位置(第2~3行)

  • 然后，在栈上分配16个字节，其中前8个字节用于存储局部变最i，而后8个字节是未被使用的

  • 接着，为数组p分配空间(第5~11行)

    • 第5行的leaq指令计算值8n＋22，然后第6行的andq指令把它向下舍入到最接近的16的倍数。当n是奇数时，结果值会是8n+8，当n是偶数时，结果值会是8n＋16，这个值减去s1就得到s2。

    • 第8~10行中的三条指令将s2向上舍入到最近的8的倍数。

    • 当程序到第11行的时候，已经在栈上分配了8n字节，并在已分配的区域内放置好数组p，至少有8n字节可供其使用。

    • 对于不同n和s1的值，s2 、p、e1和e2的值示例

      

  • 在函数的结尾，leave指令将帧指针恢复到它之前的值(第20行)。这条指令不需要参数，等价于执行下面两条指令：

    movq	%rbp, %rsp	;set stack pointer to beginning of frame
    popq	%rbp		;Restore saved %rbp and set stack ptr
    					;to end of caller's frame

    • 也就是，首先把栈指针设置为保存%rbp值的位置，然后把该值从栈中弹出到%rbp。这个指令组合具有释放整个栈帧的效果。

  • 在较早版本的x86代码中，每个函数调用都使用了帧指针。而现在，只在栈帧长可变的情况下才使用。可以看到把使用帧指针的代码和不使用帧指针的代码混在一起是可以的，只要所有的函数都把%rbp当做被调用者保存寄存器来处理即可。

浮点代码

浮点传送和转换操作

浮点代码概述

• 处理器的浮点体系结构包括多个方面，会影响对浮点数据操作的程序如何被映射到机器上，包括：

  • 如何存储和访问浮点数值。通常是通过某种寄存器方式来完成。
  • 对浮点数据操作的指令。
  • 向函数传递浮点数参数和从函数返回浮点数结果的规则。
  • 函数调用过程中保存寄存器的规则例如，一些寄存器被指定为调用者保存，而其他的被指定为被调用者保存。

• x86-64的浮点体系结构的历史

  • 1997年出现了Pentium/MMX，Intel和AMD都引入了持续数代的媒体(media)指令，支持图形和图像处理。
    • 这些指令本意是多个操作以并行模式执行，称为单指令多数据或SIMD(读作sim-dee)。在这种模式中，对多个不同的数据并行执行同一个操作。
  • 近年来，这些扩展有了长足的发展。名字经过了一系列大的修改，从MMX到SSE(Streaming SIMD Extension，流式SIMD扩展)，以及最新的AVX(Advanced Vector Extension , 高级向量扩展）。

    • 每一代中，都有一些不同的版本。每个扩展都是管理寄存器组中的数据，这些寄存器组在MMX中称为"MM"寄存器，SSE中称为"XMM"寄存器，而在AVX中称为"YMM"寄存器；

    • MM寄存器是64位的，XMM是128位的，而YMM是256位的。所以，每个YMM寄存器可以存放8个32位值，或4个64位值，这些值可以是整数，也可以是浮点数。

  • 2000年Pentium 4中引入了SSE2，媒体指令开始包括那些对标量浮点数据进行操作的指令，使用XMM或YMM寄存器的低32位或64位中的单个值。
    • 这个标量模式提供了一组寄存器和指令，它们更类似于其他处理器支待浮点数的方式。
    • 所有能够执行x86-64代码的处理器都支待SSE2或更高的版本，因此x86-64浮点数是基于SSE或AVX的，包括传递过程参数和返回值的规则。

• 我们的讲述基于AVX2，即AVX的第二个版本，它是在2013年Core i7 Haswell处理器中引入的。当给定命令行参数-mavx2时，GCC会生成AVX2代码。基于不同版本的SSE以及第一个版本的AVX的代码从概念上来说是类似的，不过指令名和格式有所不同。

• AVX浮点体系结构允许数据存储在16个YMM寄存器中，它们的名字为%ymm0~%ymm15。每个YMM寄存器都是256位(32字节）。

  • 当对标量数据操作时，这些寄存器只保存浮点数，而且只使用低32位(对于float)或64位(对于double)。
  • 汇编代码用寄存器的SSE XMM寄存器名字%xmm0~%xmm15来引用它们，每个XMM寄存器都是对应的YMM寄存器的低128位(16字节）。
  

浮点传送指令

• 在内存和XMM寄存器之间以及从一个XMM寄存器到另一个不做任何转换的传送浮点数的指令。

  
  • 引用内存的指令是标量指令，意味着它们只对单个而不是一组封装好的数据值进行操作。
  • 数据要么保存在内存中(由表中的 $M_{32}$ 和 $M_{64}$ 指明)，要么保存在XMM寄存器中(在表中用X 表示)。
  • 无论数据对齐与否，这些指令都能正确执行，不过代码优化规则建议32位内存数据满足4字节对齐，64位数据满足8字节对齐。
  • 内存引用的指定方式与整数MOV指令的一样，包括偏移量、基址寄存器、变址寄存器和伸缩因子的所有可能的组合。

• GCC只用标量传送操作从内存传送数据到XMM寄存器或从XMM寄存器传送数据到内存。

• 对于在两个XMM寄存器之间传送数据，GCC会使用两种指令之一，即用vmovaps传送单精度数，用vmovapd传送双精度数。

  • 对于这些情况，程序复制整个寄存器还是只复制低位值既不会影响程序功能，也不会影响执行速度，所以使用这些指令还是针对标量数据的指令没有实质上的差别。
  • 指令名字中的字母 a 表示aligned(对齐的)。当用于读写内存时，如果地址不满足16字节对齐，它们会导致异常。在两个寄存器之间传送数据，绝不会出现错误对齐的状况。

• 示例，一个不同浮点传送操作的例子

  • 使用了vmovaps指令把数据从一个寄存器复制到另一个，使用了vmovss指令把数据从内存复制到XMM寄存器以及从XMM寄存器复制到内存。

  float float_mov(float v1, float *src, float *dst) {
      float v2 = *src;
      *dst = v1;
      return v2;
  }

  与它相关联的x86-64汇编代码为

  ;float float_mov(float v1 , float *src, float *dst)
  ;v1 in %xmm0 , src in %rdi , dst in %rsi
  float_mov:
      vmovaps     %xmm0, %xmm1        ;Copy v1
      vmovss      (%rdi), %xmm0       ;Read v2 from src
      vmovss      %xmm1, (%rsi)       ;write vi to dst
      ret                             ;Return v2 in %xmm0

浮点数与整数的转换

• 在浮点数和整数数据类型之间以及不同浮点格式之间进行转换的指令集合。这些都是对单个数据值进行操作的标量指令。

  • 浮点数转换为整数的指令把一个从XMM寄存器或内存中读出的浮点值进行转换，并将结果写入一个通用寄存器（例如%rax、%ebx等）。

    
    • 把浮点值转换成整数时，指令会执行截断(truncation)，把值向0进行舍入，这是C和大多数其他编程语言的要求。

  • 整数转换为浮点数的指令使用的是不太常见的三操作数格式，有两个源和一个目的

    
    • 第一个操作数读自于内存或一个通用目的寄存器。这里可以忽略第二个操作数，因为它的值只会影响结果的高位字节。而我们的目标必须是XMM寄存器。
    • 最常见的使用场景中，第二个源和目的操作数都是一样的，比如 vcvtsi2sdq %rax, %xmm1, %xmm1，这条指令从寄存器%rax中读出一个长整数，把它转换成数据类型double，并把结果存放进XMM寄存器%xmm1的低字节中。

浮点数之间的转换

• 在两种不同的浮点格式之间转换，比如要将单精度值转换为双精度，可以用指令

  vcvtss2sd %xmm0, %xmm0, %xmm0

  • 把它转换成一个双精度值，并将结果存储在寄存器%xmm0的低8字节

  • 不过我们发现GCC实际生成的代码如下

    ;Conversion from single to double precision
    vunpcklps	%xmm0, %xmm0, %xmm0       ;Replicate first vector element
    vcvtps2pd	%xmm0, %xmm0              ;Convert two vector elements to double

  • vunpcklps指令通常用来交叉放置来自两个XMM寄存器的值，把它们存储到第三个寄存器中。

  • 也就是说，如果一个源寄存器的内容为字[s3,s2,s1,s0]（这是一个四元素的单精度浮点数向量），另一个源寄存器为字[d3,d2,d1,d0]，那么目的寄存器的值会是[s1,d1,s0,d0]。在上面的代码中，我们看到三个操作数使用同一个寄存器，所以如果原始寄存器的值为[x3,x2,x1,x0]，那么该指令会将寄存器的值更新为值[x1,x1,x0,x0]。

  • vcvtps2pd指令把源XMM寄存器中的两个低位单精度值扩展成目的XMM寄存器中的两个双精度值。对前面vunpcklps指令的结果应用这条指令会得到值 [dx0,dx0]，这里dx0是将x0转换成双精度后的结果。

  • 这两条指令的最终效果是将原始的%xmm0低位4字节中的单精度值转换成双精度值，再将其两个副本保存到%xmm0中。我们不太清楚GCC为什么会生成这样的代码，这样做既没有好处，也没有必要在XMM寄存器中把这个值复制一遍。

• 对于把双精度转换为单精度，可以用指令

  vcvtsd2ss %xmm0, %xmm0, %xmm0

  • GCC会产生类似的代码

    ;Conversion from double to single precision
    vmovddup	%xmm0, %xmm0		;Replicate first vector element
    vcvtpd2psx	%xmm0, %xmm0		;Convert two vector elements to single

  • 假设这些指令开始执行前寄存器%xmm0保存着两个双精度值 [x1,x0]。

  • 这vmovddup指令会将源操作数的低64位复制到目标操作数的低64位和高64位。于是两个双精度值被设置为[x0,x0]。

  • vcvtpd2psx指令把这两个值转换成单精度，再存放到该寄存器的低位一半中，并将高位一半设置为0。

  • 换句话说，它会将%xmm0寄存器的两个双精度浮点数（%xmm0[0:63]和%xmm0[64:127]）转换为两个单精度浮点数，并存储在同一寄存器的低64位中（%xmm0[0:31]和%xmm0[32:63]）

  • 同样，用这种方式把一种精度转换成另一种精度，没有明显直接的意义

• 示例，不同浮点转换操作的例子

  double fcvt(int i, float *fp, double *dp, long *lp){
      float f = *fp; double d = *dp; long l = *lp;
      *lp = (long)d;
      *fp = (float)i;
      *dp = (double)l;
      return (double)f;
  }

  它对应的x86-64汇编代码

  ;double fcvt(int i, float *fp, double *dp, long *lp)
  ;i in %edi, fp in %rsi, dp in %rdx, lp in %rcx
  fcvt:
      vmovss      (%rsi), %xmm0       ;Get f = *fp
      movq        (%rcx), %rax        ;Get l = *lp
      vcvttsd2siq (%rdx), %r8         ;Get d = *dp and convert to long
      movq        %r8, (%rcx)         ;store at lp
      vcvtsi2ss   %edi, %xmm1, %xmm1  ;convert i to float
      vmovss      %xmm1, (%rsi)       ;Store at fp
      vcvtsi2sdq  %rax, %xmm1, %xmm1  ;Convert l to double
      vmovsd      %xmm1, (%rdx)       ;store at dp
      ;The following two instructions convert f to double
      vunpcklps   %xmm0, %xmm0, %xmm0
      vcvtps2pd   %xmm0, %xmm0
      ret                             ;Return f

  • fcvt的所有参数都是通过通用寄存器传递的，因为它们是整数或者指针。
  • 结果通过寄存器%xmm0返回。这是float或double值指定的返回寄存器。

浮点过程和运算

过程中的浮点代码

• 在x86-64中，XMM寄存器用来向函数传递浮点参数，以及从函数返回浮点值。
  • XMM寄存器%xmm0~%xmm7最多可以传递8个浮点参数。按照参数列出的顺序使用这些寄存器。可以通过栈传递额外的浮点参数。
  • 函数使用寄存器%xmm0来返回浮点值。
  • 所有的XMM寄存器都是调用者保存的。被调用者可以不用保存就覆盖这些寄存器中任意一个。
• 当函数包含指针、整数和浮点数混合的参数时，指针和整数通过通用寄存器传递，而浮点值通过XMM 寄存器传递。也就是说，参数到寄存器的映射取决于它们的类型和排列的顺序。

浮点运算操作

• 一组执行算术运算的标量AVX2浮点指令。

  • 每条指令有一个(S1)或两个(S1,S2)源操作数，和一个目的操作数D

  • 第一个源操作数S1可以是一个XMM寄存器或一个内存位置。第二个源操作数和目的操作数都必须是XMM寄存器。

  • 每个操作都有一条针对单精度的指令和一条针对双精度的指令。结果存放在目的寄存器中。

    

• 示例，一个包括浮点数乘法、除法和隐式类型转换的函数

  double funct(double a, float x, double b, int i)
  {
      return a*x - b/i;
  }

  x86-64 代码如下：

  ;double funct(double a, float x, double b, int i)
  ;a in %xmm0, x in %xmm1, b in %xmm2, i in %edi
  funct:
      ;The following two instructions convert x to double
      vunpcklps   %xmm1, %xmm1, %xmm1
      vcvtps2pd   %xmm1, %xmm1
      vmulsd      %xmm0, %xmm1, %xmm0     ;Multiply a by x
      vcvtsi2sd   %edi, %xmm1, %xmm1      ;Convert i to double
      vdivsd      %xmm1, %xmm2, %xmm2     ;Compute b/i
      vsubsd      %xmm2, %xmm0, %xmm0     ;Subtract from a*X
      ret                                 ;Return

  • 三个浮点参数a、x和b通过XMM寄存器%xmm0~%xmm2传递，而整数参数通过寄存器%edi传递。
  • 标准的双指令序列用以将参数x转换为双精度类型（第2~3行）。另一条转换指令用来将参数i转换为双精度类型（第5行）。该函数的值通过寄存器%xmm0返回。

定义和使用浮点常数

• 和整数运算操作不同，AVX浮点操作不能以立即数值作为操作数。相反，编译器必须为所有的常量值分配和初始化存储空间。然后代码再把这些值从内存读入。

• 示例，从摄氏度到华氏度转换的函数

  double cel2fahr(double temp) {
  	return 1.8 * temp + 32.0;
  }

  相应的x86-64汇编代码部分

  ;double cel2fahr(double temp)
  ;temp in %xmm0
  cel2fahr:
      vmulsd  .LC2(%rip), %xmm0, %xmm0        ;Multiply by 1.8
      vaddsd  .LC3(%rip), %xmm0, %xmm0        ;Add 32.0
      ret
  .LC2:
      .1ong   3435973837                      ;Low-order 4 bytes of 1.8
      .long   1073532108                      ;High-order 4 bytes of 1.8
  .LC3:
      .long   0                               ;Low-order 4 bytes of 32.0
      .long   1077936128                      ;High-order 4 bytes of 32.0

  • 函数从标号为.LC2的内存位置读出值1.8，从标号为.LC3的位置读入值32.0。每一个都是通过一对.long声明和十进制表示的值指定的。
  • 标号.LC2的声明，有两个值：3435973837(0xcccccccd)和1073532108(0x3ffccccc)。因为机器采用的是小端法字节顺序，第一个值给出的是低位4字节，第二个给出的是高位4字节。
  • 从高位字节，可以抽取指数字段为0x3ff(1023)，减去偏移1023得到指数0。将两个值的小数位连接起来，得到小数字段0xccccccccccccd，二进制小数表示为0.8，加上隐含的1得到1.8。

在浮点代码中使用位级操作

• GCC生成的代码会在XMM寄存器上执行位级操作，类似于它们在通用寄存器上对应的操作。这些操作都作用于封装好的数据，即它们更新整个目的XMM寄存器，对两个源寄存器的所有位都实施指定的位级操作。

• 我们只对标量数据感兴趣，只想了解这些指令对目的寄存器的低4或8字节的影响。

  

浮点比较操作

• AVX2提供了两条用千比较浮点数值的指令：

  
  • 这些指令类似于CMP指令，它们都比较操作数S1和S2，并且设置条件码指示它们的相对值。
  • 参数S2必须在XMM寄存器中，而S1可以在XMM寄存器中，也可以在内存中。

• 浮点比较指令会设置三个条件码：零标志位ZF、进位标志位CF和奇偶标志位PF。

  • 对于整数操作，当最近的一次算术或逻辑运算产生的值的最低位字节是偶校验的(即这个字节中有偶数个1)，那么就会设置奇偶标志位为1。对于多字节的整数，可以通过将每个字节进行异或运算来检查整个整数的奇偶性。

  • 对于浮点比较，当两个操作数中任一个是NaN时，会设置奇偶标志位为1，表示是无序的。

  • C语言中如果有个参数为NaN，就认为比较失败了，这个标志位就被用来发现这样的条件。

    条件码的设置条件如下：

    

  • 当任一操作数为NaN时，就会出现无序的情况。

    • 可以通过奇偶标志位发现这种情况。通常jp(jump on parity，根据奇偶跳转)指令是条件跳转，条件就是浮点比较得到一个无序的结果。
    • 除了操作数为NaN，其他数进行比较时，进位和零标志位的值都和对应的无符号比较一样：当两个操作数相等时，设置ZF；当S2<S1时，设置CF。
    • 像ja和jb这样的指令可以根据标志位的各种组合进行条件跳转。

• 示例，根据参数x与0.0的相对关系进行分类，返回一个枚举类型作为结果。

  typedef enum {NEG, ZERO, POS, OTHER} range_t;
  range_t find_range(float x) {
      int result;
      if (x < 0)
          result = NEG;
      else if (x == 0)
          result = ZERO;
      else if (x > 0)
          result = POS;
      else
          result = OTHER;
      return result;
  }

  • C中的枚举类型是编码为整数的，所以函数可能的值为：0(NEG)，1(ZERO)，2(Pos)和3(OTHER)。当x的值为NaN时，会出现最后一种结果

  GCC产生的汇编代码为

  	;range_t find_range(float x)
  	;x in %xmm0
  1	find_range :
  2	    vxorps      %xmm1, %xmm1, %xmm1	;Set %xmm1 = 0
  3	    vucomiss    %xmm0, %xmm1      	;Compare 0 : x
  4	    ja          .L5           		;If >, goto neg
  5	    vucomiss    %xmm1, %xmm0      	;Compare x:0
  6	    jp          .L8             	;If NaN, goto posornan
  7	    movl        $1, %eax            ;result = ZERO
  8	    je          .L3                 ;If =, goto done
  9	.L8:                                ;posornan:
  10	    vucomiss    .LC0(%rip), %xmm0   ;Compare x:0
  11	    setbe       %al                 ;Set result = NaN ? 1 : 0
  12	    movzbl      %al, %eax           ;Zero-extend
  13	    addl        $2, %eax			;result += 2(POS for > 0, OTHER for NaN)
  14	    ret                             ;Return
  15	.L5:                                ;neg:
  16	    movl        $0, %eax            ;result= NEG
  17	.L3:                                ;done:
  18	    rep; ret                        ;Return

  • 这段代码的效率不是很高：它比较了x和0.0三次，即使一次比较就能获得所需的信息。它还生成了浮点常数两次：一次使用vxorps，另一次从内存读出这个值。
  • x<0.0，第4行的ja分支指令会选择跳转，跳转到结尾，返回值为0。
  • x=0.0，ja(第4行)和jp(第6行)两个分支语句都会选择不跳转，但是je分支(第8行)会选择跳转，以%eax等于1返回。
  • x >0.0，这三个分支都不会选择跳转。setbe(第11行)会得到0，addl指令(第13行)会把它增加，得到返回值2。
  • x=NaN，jp分支(第6行)会选择跳转。第三个vucomiss指令(第10行)会设置进位和零标志位，因此 setbe指令(第11行)和后面的指令会把%eax设置为1。addl指令(第13行)会把它增加，得到返回值3。作业3.73和3.74中，需要试着手动生成find_range更高效的实现。