Ylin's Blog
0%

发表于 更新于
本文字数： 24 阅读时长 ≈ 1 分钟

你好呀！

这里记录我的学习经历和内容

希望能够帮到你们

: )

发表于 更新于 分类于 ，
本文字数： 6.9k 阅读时长 ≈ 6 分钟

接下来我们要探讨学习一下符号解析和重定位实现的原理。

符号解析

连接器解析符号引用，实际上就是将每个引用，和它输入的可重定位目标文件的符号表中的一个确定的符号定义关联起来。当局部符号的引用和引用定义在相同模块的时候，符号解析简单明了。编译器只允许每个模块中每个局部符号只有一个定义，因此编译器要确保它们又唯一的名字。

不过，对于全局符号的引用解析就十分难以处理。当编译器遇到一个不是在当前模块定义的符号时，会假设这个符号已经被其他模块定义了，生成一个链接器符号表条目，将它交给链接器处理。如果链接器在它的任何输入模块中都找不到这个被引用的符号的定义，就会报错。比如我们尝试编译这个程序:

1
2
3
4
5
void foo();
int main(){
	foo();
	return 0;
}

编译器会毫无障碍的编译，但是链接器却无法解析对foo的引用：

1
2
3
ylin@Ylin:~/Program/test$ gcc test.c -o test -Wall -Og
/usr/bin/ld: /tmp/ccKOmx5V.o: in function `main':
test.c:(.text+0xe): undefined reference to `foo'

因此对于全局符号的处理比较困难，而且可能会出现多个目标文件定义相同名字的全局符号。此时，链接器要么选出一个定义抛弃其他定义，要么就给出一个错误。

链接器如何解析多重定义的全局符号

链接器的输入是一组可重定位目标模块。每个模块定义一组符号，有的是局部的（只对本地模块可见），有的是全局的（对其他模块也可见）。但是如果多个模块的定义了同名的全局符号，Linux编译系统会怎么做？

在编译时，编译器向汇编器输出每个全局符号，或是强或是弱，而汇编器把这个信息隐含地编码在可重定位的目标文件的符号表里。函数和已初始化的全局变量是强符号，未初始化的全局变量是弱符号。

Linux链接器会根据以下规则来处理多重定义的符号名：

  • 不允许有多个同名的强符号
  • 如果有一个强符号和多个弱符号同名，那么选择强符号。
  • 如果有多个弱符号同名，那么从这些弱符号中任意选择一个

我们可以看下各个规则的具体表现：

  • 规则一
1
2
3
4
5
6
7
8
//1.c
int main(){
	return 0;
}
//2.c
int main(){
	return 0;
}
1
2
3
4
ylin@Ylin:~/Program/test$ gcc -o prog 1.c 2.c
/usr/bin/ld: /tmp/ccYSd6rb.o: in function `main':
2.c:(.text+0x0): multiple definition of `main'; /tmp/ccogxBxO.o:1.c:(.text+0x0): first defined here
collect2: error: ld returned 1 exit status

这是因为强符号main被定义了多次，造成了冲突。下面也是

1
2
3
4
5
6
7
8
9
10
//1.c
int x=114;
int main(){
	return 0;
}
//2.c
int x=514;
int f(){
	return 0;
}
1
2
3
ylin@Ylin:~/Program/test$ gcc -o prog 1.c 2.c
/usr/bin/ld: /tmp/cc9GFQfr.o:(.data+0x0): multiple definition of `x'; /tmp/ccljmBRr.o:(.data+0x0): first defined here
collect2: error: ld returned 1 exit status

这里是因为被初始化的全局变量（强符号）x出现了多次，造成冲突。

  • 规则二
1
2
3
4
5
6
7
8
9
10
11
12
13
14
//1.c
#include <stdio.h>
int x=114;
int main(){
    f();
    printf("%d\n",x);
	return 0;
}
//2.c
int x;
int f(){
    x = 514;
	return 0;
}
1
2
3
ylin@Ylin:~/Program/test$ gcc -o prog 1.c 2.c
ylin@Ylin:~/Program/test$ ./prog
514

这里虽然没有造成冲突，但是可以看到另一个模块对x的使用，修改了它的值。

  • 规则三
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//1.c
#include <stdio.h>
int x;
int main(){
    x = 114;
    f();
    printf("%d\n",x);
	return 0;
}
//2.c
int x;
int f(){
    x = 514;
	return 0;
}
1
2
3
ylin@Ylin:~/Program/test$ gcc -o prog 1.c 2.c
ylin@Ylin:~/Program/test$ ./prog
514

结果和上面基本一致，但是我们并不知道最终使用了哪个符号，因为它们都是弱符号，是随机的。

当然现代的编译器为了避免多重定义的全局符号给我们带来的错误，往往在编译时，会开启GCC-fno-common选项，以保证遇到多重定义的全局符号时，会发生错误，无法通过链接。

在上一篇中我们提到了编译器会按规则将符号分配到COMMON或.bss，但是我们并不清楚为什么要这样做。现在我们知道了，在编译器翻译一个模块时，对于一个弱全局符号，它并不知道其他模块是否也定义了相同的符号。如果是的话，它无法预测链接器会使用多重定义中的哪一个，所以编译器将它这个弱全局符号放入COMMON中，交给链接器来决定。如果这个符号被初始化为0的话，那么它就是一个强符号，编译器就可以直接将它分配为.bss。相似的，对于静态变量(不用考虑多重定义)，也是如此放入.bss或.data。

与静态库链接

到目前为止，我们都是假设链接器会读取一组可重定位目标文件，并将其链接起来，形成一个输出的可执行文件。实际上，所有的编译系统都支持一种机制——把所有相关的目标模块打包成为一个单独的文件，被称为静态库。当链接器要构造一个输出的可执行文件时，它只会复制静态库中被程序引用的目标模块。这么做有以下好处：

  • 如果将模块合并到一个可重定位目标文件中，会导致程序每次链接都会包含一份完整的标准库。其中大部分的模块并不会被使用，这导致程序占用的磁盘空间会更大。
  • 如果将标准函数内联至编译器，这虽然很便捷。但是会导致编译器开发的难度更大。且每次标准库的更新都需要修改编译器
  • 如果为每个标准函数都创建一个独立的可重定位文件，将他们放在一个目录下。这会导致链接时需要大量的显式链接合适模块到可执行文件中。

所以链接库的概念被提出来。相关的函数可以被编译为独立的目标模块然后封装在一个单独的静态库文件。然后应用程序可以在命令行中指定单独的文件名字来使用这些在库中定义的函数。

在链接时，链接器将只复制被程序引用的模块，这就减少了可执行文件在磁盘和内存中的大小。且减少了程序员对库文件引用次数。

在Linux中，静态库以一种称为存档的特殊文件格式存放在磁盘中。存档文件时一组连接起来的可重定位目标文件集合，它的头部来描述每个成员目标文件的大小和为止。存档文件的后缀为.a

我们可以简单的实现一下这个过程：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//addvec.c
int addcnt=0;
void addvec(int*x,int*y,int*z,int n){
    int i;
    addcnt++;
    for(i=0;i<n;i++)
        z[i] = x[i] + y[i];
}
//multvec.c
int multcnt = 0;
void multvec(int*x,int*y,int*z,int n){
    int i;
    multvec++;
    for(i=0;i<n;i++)
        z[i] = x[i]*y[i];
}

然后我们用这两个函数创建一个静态库：

1
2
3
4
ylin@Ylin:~/Program/test$ gcc -c addvec.c multvec.c
ylin@Ylin:~/Program/test$ ls
addvec.c  addvec.o  multvec.c  multvec.o
ylin@Ylin:~/Program/test$ ar rcs libtest.a addvec.o multvec.o

然后我们可以利用这个静态库来编写我们的程序，来验证是否只调用了我们需要的目标模块：

1
2
3
4
5
6
7
8
9
10
11
12
#include <stdio.h>
#include "test.h"	//包含两个函数的原型

int main(){
        int x[4] = {1,2,3,4};
        int y[4] = {1,2,3,4};
        int z[4];

        multvec(x,y,z,4);
        printf("z = [%d %d %d %d]",z[0],z[1],z[2],z[3]);
        return 0;
}

使用gcc -static -o prog main.o -L . -ltest编译（其中-static是静态链接，-L指定静态库的查询目录，-ltest是./libtest.a的缩写），我们使用：

1
ylin@Ylin:~/Program/test$ objdump -d prog | grep "addvec"

发现程序中并没有addvec目标模块，静态库的链接很好的完成了工作。整个过程我们可以用这个图来大致的表现。

image.png

链接器如何使用静态库来解析引用

解释一下静态库使用的原理和可能遇到的一些问题。

Linux链接器在解析外部引用的时候，是从左往右按照编译器驱动程序命令行上的顺序来扫描，可重定位目标文件和存档文件（驱动程序会自动将源程序文件翻译成可重定位目标文件）。在扫描中，链接器会维护一个可重定位目标文件中的集合E(该集合文件中的目标文件会被链接成可执行文件)，一个未解析的符号集合U（引用了但是尚未定义的符号），一个在前面的输入文件中已定义的符号集合D。初始时，E、U、D均为空：

  • 对于命令行上的每个输入文件f，链接器会判断它的类型，是目标文件还是存档文件。如果是目标文件，则将其放入E中，然后修改U和D来反映f中符号定义和引用，并继续下一个输入文件。
  • 如果f是一个存档文件，那么链接器就尝试匹配U中未解析的符号和由存档文件成员定义的符号。如果某个存档文件成员定义了一个符号来解析U中的一个引用，那么就将m加到E中，并且修改U和D来反映m的符号定义和引用。对存档文件中的每一个程序进行这个尝试，知道U和D都不再变化。此时不包含在E中的目标文件被丢弃。开始处理下一个输入文件。
  • 如果链接器处理完所有的输入文件之后，U是非空的，链接器就会输出一个错误并停止。反之，则合并重定位E中的目标文件，构建输出的可执行文件。

不过因此，命令行上的库和目标文件的顺序也很重要。在命令行中，如果定义一个符号的库出现在引用这个符号的目标文件之前，那么引用就不会被解析，链接会失败。对于存档文件之间的顺序也是如此。如果一个库a中的引用在另一个库b中被定义，那么要先a后b。反之，如果库直接都是相互独立的，就可以不在乎输入顺序。

重定位

当链接器完成了符号解析，代码中的每个符号引用和它的符号定义（即目标模块中的符号表条目）就会被关联起来。此时，链接器就知道它的输入目标模块中的代码节和数据节的确切大小。现在就可以重定位操作了，在这个步骤中，将合并输入模块，并为每个符号分配运行时的地址。

  • 重定位节和符号定义:

    在这一步中，链接器将所有相同类型的节合并为同一类型的新的聚合节。然后链接器将运行时内存地址赋给新的聚合节，赋给输入模块定义的每个节，以及赋给每个节的每个符号。当这一步完成时。程序中的每条指令和全局变量都有唯一的运行时内存地址。

  • 重定位节中的符号引用：

    在这一步中，链接器修改代码节和数据节中对每个符号的引用，使得他们指向正确的运行时的地址。要执行这一步，链接器依赖于可重定位目标模块中称为重定位条目的数据结构，我们接下来将会描述这种数据结构。

重定位条目

当汇编器生成一个目标模块时，它并不知道数据和代码在运行时会被存放在内存中的哪个位置。也不知道模块引用的外部定义的函数或全局变量的位置在哪里。所以，当汇编器遇到最终位置未知的目标引用，他就会生成一个重定位条目（用来为链接器修正未知提供“导航”），用来告诉链接器，在合并目标模块时如何修改这个引用。代码的重定位条目存放在.rel.text，数据的重定位条目存放在.rel.data

下面是一个典型的重定位条目格式：

1
2
3
4
5
6
typedef struct{
    long offset;
    long type:32,
    	symbol:32;
    long addend;
}Elf64_Rela;
  • offset：需要被修改的引用的节偏移
  • type：如何修改新的引用
  • symbol：被修改的引用应该指向的符号
  • addend：一个有符号常数，个别类型的重定位需要使用它对被修改引用的值做偏移调整

ELF定义了32中不同的重定位类型，但是我们需要考虑两种最常见的类型：

  • R_X86_64_PC32：

    重定位一个使用32位PC相对地址的引用。一个PC相对地址就是据PC当前运行时值的偏移量。当CPU执行一条使用PC相对寻址的指令时，他就将在指令中编码的32位值加上当前的PC值，得到有效地址，PC值通常是下一条指令在内存中的地址

  • R_X86_64_32:

    重定位一个使用32位绝对地址的引用。通过绝对寻址，CPU直接使用在指令中编码的32位值作为有效地址

重定位符号引用

根据重定位算法，来分析一下重定位的过程。下面展示重定位算法的伪代码，为了方便表示，假设每个节s是一个字节数组，每个重定位条目r都是一个类型为Elf64_Rela的结构。用ADDR()来获取对应的运行时的地址：

1
2
3
4
5
6
7
8
9
10
11
12
13
for (section:s){
    for (relocation_entry:r){
        refptr = s + r.offset;	//重定位编码的地址
        //相对PC地址引用
        if(r.type == R_X86_64_PC32){
            refaddr = ADDR(s) + r.offset;	//运行时的待重定位地址
            *refptr = (unsigned)(ADDR(r.symbol) + r.addend - refaddr);
        }
		//绝对PC地址引用        
        if(r.type == R_X86_64_32)
            *refptr = (unsigned)(ADDR(r.symbol) + r.addend);
    }
}

以下面这个反汇编代码为例，我们来分析一下链接器是怎么重定位这些引用的：

image.png

重定位PC相对引用

第6行，call开始于节偏移值为0xe的地方，包括1字节的操作码0xe8，还有四个字节的占位符。其中sum的重定位条目r为：

1
2
3
4
r.offset = 0xf
r.symbol = sum
r.type = R_X86_64_PC32
r.addend = -4

这些字段告诉链接器修改开始于偏移量0xf的32位PC相对引用，在运行时它会指向sum例程。此时链接器已知：

1
2
ADDR(s) = ADDR(.text) = 0x4004d0
ADDR(r.symbol) = ADDR(sum) = 0x4004e8

我们重定位的过程应该是这样的：

1
2
3
4
5
6
refaddr = ADDR(s) + r.offset
    	= 0x4004d0 + 0xf
    	= 0x4004df
*refptr = (unsigned) (ADDR(r.symbol) + r.addend - refaddr)
    	= (unsigned) (0x4004e8 + (-4) - 0x4004df)
    	= (unsigned) (0x5)

最终得到4004de: e8 05 00 00 00 callq 4004e8 <sum>

重定位绝对引用

第4行，mov开始于节偏移值位0x4的地方，包括1字节的操作码0xbf，还有四个字节的arrary地址的占位符。其中array的重定位条目r为：

1
2
3
4
r.offset = 0xa
r.symbol = array
r.type = R_X86_64_32
r.addend = 0

这些字段告诉链接器要修改从偏移量0xa开始的绝对引用，这样在运行时它会指向arrary的第一个字节。此时链接器已知：

1
ADDR(r.symbol) = ADDR(array) = 0x601018

我们重定位的过程为是这样的：

1
2
3
*refptr = (unsigned) (ADDR(r.symbol) + r.addend)
     	= (unsigned) (0x601018 + 0)
    	= (unsigned) (0x601018)

最终得到4004d9: bf 18 10 60 00 mov $0x601018,%edi。最终的效果如下：

image.png

发表于 分类于 ，
本文字数： 3.2k 阅读时长 ≈ 3 分钟

开始学习新的章节——链接。我们现在要研究在gcc调用的过程中，到底有哪些过程是被我们所忽略的，在编译的过程中它们又有着什么作用呢？

编译器驱动程序

我们以下面的这段代码为例，将以此来分析整个编译的过程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//file 1
int sum(int *a,int n);

int array[2] = {1,2};

int main(){
    int val = sum(array,2);
    return val;
}
//file 2
int sum(int *a,int n){
    int i,s = 0;
    
    for(int i=0;i<n;i++){
        s += a[i];
    }
    return s;
}

大多数编译系统都会提供一个编译驱动程序，在用户需要时调用语言处理器，编译器，汇编器，链接器。比如我们要用GNU编译系统进行编译时，我们就需要使用gcc编译驱动：

1
ylin@Ylin:~/Program/test$ gcc -Og -o test main.c sum.c

但是实际上省略了很多中间过程并没有让我们看到，我们可以通过加入-v参数来观察这个过程：

image.png

红色框出来的分别时ccl as ld的调用，我们之后会分析这几个程序的作用。现在我们可以将从ASCIII源码到执行文件的编译驱动的过程总结一下：

image.png

首先预处理器cpp(预处理器实际上和编译器是集成在一起的)将ASCII源文件翻译成一个ASCII码的中间文件

1
ylin@Ylin:~/Program/test$ cpp main.c -o main.i

然后驱动程序运行C编译器ccl（这里我们使用gcc实现），将中间文件翻译成汇编语言：

1
ylin@Ylin:~/Program/test$ gcc -S main.i

接着驱动程序运行汇编器as，将main.s翻译成一个可重定位目标文件main.o:

1
ylin@Ylin:~/Program/test$ as main.s -o main.o

然后对sum.c进行同样的操作，得到sum.o。然后驱动程序运行链接器程序ld（在gcc -v的过程中可以看到链接过程使用的是collect2，实际上是ld的封装用法），将main.o和sum.o以及一些必要的系统目标文件编译起来，创建一个可执行的目标文件：

1
ylin@Ylin:~/Program/test$ ld -o test sum.o main.o

最后当我们执行编译出来的test程序时，shell会调用一个名为加载器loader的函数，将可执行文件中的代码和数据复制到内存，然后将控制转移到这个程序的开头：

1
ylin@Ylin:~/Program/test$ ./test

不过实际上，这些中间过程是被什么略的，其中生成的中间文件会被存放在\tmp下，待编译结束后被清理。

静态链接

像ld这样的静态连接器以一组可重定位目标文件个命令行参数作为输入，生成一个完全链接的、可以加载和运行的可执行目标文件作为输出。输出的可重定位目标文件由各种不同的代码和数据节section组成，每一节都是一个连续的字节序列。指令在一个节中，初始化了的全局变量在另一个节中，而未初始化的变量又在另一个节中…

为了构建一个可重定位文件，链接器要实现一下的功能：

  • 符号解析：

    目标文件会定义和引用符号。每个符号可能对应一个全局变量、一个函数或一个静态变量（static声明的变量），符号解析则是将每个符号的引用和它的定义联系起来。

  • 重定位：

    编译器和汇编器会生成从地址0开始的代码和数据节。链接器通过把每个符号的定义和一个内存位置关联起来，从而重定位这些节，然后修改这些符号的引用，使得它们指向这个内存位置。链接器使用汇编器产生的重定位信息条目的详细指令给，进行这些重定位操作

之后我们会详细的分析这几个过程。实际上我们只需要清除，目标文件实际上就是字节块的集合。这些块中，有的包含程序代码，有的包含程序数据，其他的则包含引到链接器和加载器的数据结构。链接器负责将这些块连接起来，确定被连接块的运行时的位置，并且修改代码和数据块中的各种位置。

目标文件

目标文件有三种形式：

  • 可重定位目标文件：

    主要包含二进制代码和数据，其形式可以在链接时与其他的可重定位目标文件合并起来，创建一个可执行目标文件。

  • 可执行目标文件：

    包含二进制代码和数据，其形式可以直接被复制到内存中并执行。

  • 共享目标文件：

    一种特殊类型的可重定位目标文件，可以在加载或者运行时，被动态地加载进内存并链接。

编译器和汇编器生成可重定位目标文件（包括共享目标文件）。链接器生成可执行目标文件。

从技术上来说，一个目标模块就是一个字节序列，而一个目标文件就是一个以文件形式存储在磁盘中的目标模块。本质上它们是一样的。

不同的系统有不同的目标文件格式，如：

  • Unix ：a.out格式
  • Windows ：可移植可执行格式（PE）
  • Mac ：Mach-O格式
  • 现代Linux/Unix ：可执行可链接格式（ELF）

可重定位目标文件

image.png

这是一个典型的ELF可重定位目标文件的格式。我们从ELF头开始说起，我们可以使用readelf -h来获取一个程序的ELF头信息：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
ylin@Ylin:~/Program/test$ readelf -h test
ELF Header:
  Magic:   7f 45 4c 46 02 01 01 00 00 00 00 00 00 00 00 00
  Class:                             ELF64
  Data:                              2's complement, little endian
  Version:                           1 (current)
  OS/ABI:                            UNIX - System V
  ABI Version:                       0
  Type:                              DYN (Position-Independent Executable file)
  Machine:                           Advanced Micro Devices X86-64
  Version:                           0x1
  Entry point address:               0x1040
  Start of program headers:          64 (bytes into file)
  Start of section headers:          14016 (bytes into file)
  Flags:                             0x0
  Size of this header:               64 (bytes)
  Size of program headers:           56 (bytes)
  Number of program headers:         13
  Size of section headers:           64 (bytes)
  Number of section headers:         29
  Section header string table index: 28

以一个16字节长的字节序列Magic开始，这个序列用于系统判断是否为ELF文件格式（字节序和位宽），ELF头的其他部分则包含了帮链接器语法分析和解释目标文件的信息。其中包括

  • ELF头的大小 –> Size of this header
  • 目标文件的类型 –> Type
  • 机器类型 –> Machine
  • 节头部表的文件偏移 –> Start of section headers
  • 节头部表条目的大小和数量 –> Number of section headers + Size of section headers

不同节的位置和大小是由节头部表描述的，其中目标文件中的每个节都有一个固定的条目（entry）。夹在ELF头和节头部表中间的都是节。一个典型的ELF可重定位目标文件包含以下的节：

  • .text

    已编译程序的机器代码

  • .rodata

    只读数据(常量数据，运行期间不可更改)

  • .data

    已初始化的全局和静态C变量。局部C变量在运行时被保存在栈中，不被保存在节

  • .bss

    未初始化的全局和静态C变量，以及所有被初始化为0的全局或静态变量。在目标文件中这个节不占据任何实际的空间，仅仅是一个占位符。区分已初始化和未初始化是为了空间效率，未初始化变量不需要占据任何实际的磁盘空间。运行时，在内存中分配这些变量，初始化为0

  • .symtab

    一个符号表，它存放在程序中定义和引用的函数和全局变量的信息。和使用-g编译出的程序得到的符号表信息不同，.symtab中不包含局部变量的条目

  • .rel.text

    重定位节。一个.text节中位置的列表，当链接器把这个目标文件和其他文件组合时，需要修改这些位置。这个时候.text中有哪些地址/符号需要在链接或加载时被修正的内容，就记录在.rel.text中。

  • .rel.data

    数据的重定位节。记录.data中哪些变量/指针需要链接器修改地址

  • .debug

    调试符号表，其条目是程序中定义的局部变量和类型定义，程序中定义和引用的全局变量，以及原始的C源文件。只有在使用gcc时加上-g选项，才可以得到这张表

  • .line

    原始C源程序中的行号和.text节中机器指令之间的映射。只有使用-g时得到。

  • .strtab

    一个字符串表，内容包括其他节中的字符串信息。它自己不包含逻辑结构，只是被其他节按索引引用，用来存放符号名，段名，动态库名等文本。因此其他节只需要存放对应字符串的偏移索引就行了，真正的字符内容放在.strtab.

符号和符号表

符号

每个可重定位模块m都有一个符号表，它包含m定义和引用的符号的信息。在连接器的上下文中，有三种不同的符号：

  • 由模块m定义并能被其他模块引用的全局符号。全局符号对应于非静态的C函数和全局变量。
  • 由其他模块定义并被模块m引用的全局符号，称之为外部符号，对应于在其他模块中定义的非静态C函数和全局变量
  • 只被模块m定义和引用的局部符号。它们对应于带static属性的C函数和全局变量。这些符号在模块m中任何位置可见但是，不能被其他模块引用。

链接器不关心本地局部变量。同样的.symtab中的符号表也不包含对应于本地非静态程序变量的任何符号。这些符号在运行时由栈管理。不被链接器考虑。

不过定义为带有Cstatic属性的本地过程变量时不在栈中管理的（使用static属性可以隐藏模块内部的变量和函数声明，就像class中使用private，来保护变量和函数只能被本地模块使用）。相反，编译器在.data或.bss中会为每个定义分配空间，并在符号表中创建一个有唯一名字的本地连接符号。比如：

1
2
3
4
5
6
7
8
int f(){
    static int x=0;
    return x;
}
int g(){
    static int x=0;
    return x;
}

此时编译器会向汇编器输出两个不同名字的局部链接符号。比如，可以用x.1表示函数f中的定义，用x.2表示函数g中的定义。

符号表

符号表是由汇编器构造的，使用的是编译器给出的符号。ELF符号表被存放在.symtab中。这个符号表包含着一个条目的数组，其条目结构如下：

1
2
3
4
5
6
7
8
9
typedef struct{
    int name;			
    char type:4;		
    	 binding:4;		
    char reversed;		
    short section;		
    long value;			
    long size;			
}ELF64_symbol;

它们的作用分别是：

  • name：字符串表中的字节偏移，指向符号的字符串名字
  • type：表示符号的种类（数据/函数）
  • binding：表示符号的可见性（本地/全局）
  • reverse：暂时无用，留作数据对齐。
  • section：节头部表的索引，用于定位节
  • value：指定节中的偏移，相当于一个绝对运行时的地址
  • size：目标的大小（字节大小）

每个符号都会被分配到目标文件的某个节中。由section字段表示，该字段也是一个到节头部表的索引。有三个特殊的伪节，它们在节头部表中并没有条目：

  • ABS，表示符号值是绝对的，不应该被重定位
  • UNDEF，表示符号未定义，就是在本模块中使用，但是在其他地方定义的符号。
  • COMMON，表示未被分配位置的未初始化的数据目标 > 只有在可重定位目标文件中才有伪节，可执行目标文件中没有

对于COMMON符号，value给出的是对齐要求，size给出的是最小的大小。

这么一看COMMON和.bss似乎差不多。现代的汇编器根据以下规则来将符号分配到COMMON和.bss中： 

1
2
COMMON  未初始化的全局变量
.bss	未初始化的静态变量，以及初始化为0的全局变量和静态变量

之后我们会详细解释这个设置的原因。

发表于 更新于 分类于 ，
本文字数： 3.3k 阅读时长 ≈ 3 分钟

我们学习一下现代计算机中的存储器架构，以及它的一些具体实现。我们该如何利用存储器的性能来实现对局部性的高效利用？它背后的原理又是什么呢？

存储器存储结构

不同的存储器有着不同的存储技术和存储性能，可喜的是，它们的属性很好的互相补齐各自的不足，利用这个性质，出现了一种组织存储器系统的方法，称之为存储器层次结构。

image.png

从高层往底层走，存储器的容量、成本、速度都越来越慢。所以我们以下面为基础，不断的向上层提供数据。其中我们就不得不提到存储器结构中最为关键的 缓存

缓存

存储器之间的属性有着较大的差异，通常我们需要在其之间设置一个缓冲，以更好的实现数据的读取和转移。其中，高速缓存就是一种小而迅速的存储设备，它作为更大、更慢的存储器设备的数据的缓存区域。而使用高速缓存的过程我们就称之为缓存。缓存的基本原理如下：

image.png

对于缓存，我们还要理解它的各个状态：

缓存命中

当程序需要k+1层的某个数据对象d时，它首先到k层中去查找，如果找到了，则此时数据d缓存命中。

缓存不命中

相反，如果k层没有找到数据d时，我们则发生缓存不命中。此时k层的缓存从第k+1层中取出包含d的块。如果此时k层的缓冲已经满了，就会覆盖其中的一个块，这个过程叫做替换/牺牲。具体替换哪个块由替换策略所决定。

缓存不命中的状态：

  • 强制不命中（冷不命中）：此时缓存为空，无论什么数据都不会命中。
  • 容量不命中：当前的工作集的大小大于缓存的大小。
  • 冲突不命中：有些替换策略会将符合同一规则的块指定替换到上层换从中的指定块，这种策略比较简洁容易实现。此时就可能会出现同组的块互相冲突。类似于哈希表中的哈希冲突。

存储器层次结构的本质是，每一层存储设备都是较低一层的缓存。所以在每一层中，都需要有某种形式的逻辑来管理缓存（将缓存分块，在不同层之间传送块，判定是否命中，并处理它们），不论是硬件还是软件。下面有一张表，大致的说明了各个缓存的管理实现：

image.png

高速缓存存储器

为了更好的理解存储器缓存的原理，我们需要介绍一下高速缓存存储器的组织架构。

计算机的地址数量通常由存储器的位数所决定，当存储器的位数为m时，计算机的内存空间就有2m个地址。而高速缓存存储器的结构如下：

image.png

一个高速缓存存储器被分作S(2s)个高速缓存组，每个高速缓存组有E个高速缓存行，每个高速缓存行中有B(2b)个数据块。我们通过对地址字段进行划分，从而实现对高速缓存的定位。

当我们拿到一个地址，想要尝试从高速缓存存储器中取出一个数据块时，都要经历以下过程：

  • 读组索引：根据地址中的s位的数据来确定数据所在的缓存组
  • 标记比对：当数据行有效时，与其比较t位标记值，如果标记相同则确定数据存储行。
  • 读块索引：根据地址中的b位数据确定数据在缓存块中的偏移地址。
  • 缓存不命中：则重复上述的步骤向下取需要的数据。

你可能会好奇，为什么使用中间的几位作为组索引，而不是高位呢？这是为了避免高位的一致性从而导致连续的内存空间被分配到一个组，从而引发冲突不命中，下图很好的说明了这一点：

image.png

同时，根据每个组的高速缓存行的数量，也可以分成以下高速缓存存储器类型：

  • 直接映射高速缓存

    E=1，每组高速缓存行只有一行，所以不需要再组中查找对应的缓存行，且实现起来比较简单。但是对于冲突不命中的应对上效果很差，因为每个组只能取一条数据。

  • 全相联高速缓存

    S = 0，E = C/B。所有的缓存行都存储在一个组中，由于没有固定的映射关系，所以任何主存块可以存储在缓存的任何位置。灵活性很高，很好的避免了冲突的关系。但是由于结构复杂，且每次访问时，需要匹配缓存行，消耗了大量的时间，访问速度慢。

  • 组相联高速缓存

    相当于直接映射和全相联的中和版本。每个组有一定的缓存行。

高速缓存层次结构分析

我们给出一个真实的高速缓存层次结构

image.png

实际上高速缓存存储器不仅存储数据，同时存储着指令，只不过指令是只读的，数据则可读可写。芯片上的每个核有着自己的高速缓存，同时共享一个高速缓存和主存。在复杂的资源共享管理下，实现工作

高速缓存参数的性能影响

定性的分析高速缓存的影响参数：

  • 高速缓存大小

    较大的高速缓存可以提高缓存的命中率，但也意味着会造成更大的运行开销，这也是为什么越上层的存储器越小，这可以减少访问的时间。

  • 块大小

    大的块可以更好的利用程序中的空间局部性。但是在缓存空间给定的情况下，较大的块会导致较少的缓存内存行，会加剧数据冲突。从而导致时间局部性所受到的损耗大于空间局部性带来的好处。

  • 相联度

    即高速缓存行数E的选择，较高的相联度可以减少冲突不命中导致的不命中处罚，但是访问速度低，而且较大的块也会导致更严重的不命中处罚。而较低的相联度虽然访问速度快，但是也会导致更多的不命中处罚。所以需要根据不同的情况选择不同的相联度。

    在L1中，通常使用相联度低的存储方式，因为不命中的处罚较小（数据较少）。但是对于底层的主存等区域，每次不命中的处罚很严重，所以要提高相联度，尽可能的减少不命中。

  • 写策略

    直写（立即将高速缓存块写入第一层的存储器中）比较容易实现，而且可以使用写缓冲区进行内存更新，但是会导致总线的流量增大。写回（尽可能的推迟更新，只有该块被替换的时候才将数据块更新到第一层的存储器中）引起的传送会更少。此外，越往底层走，传送的时间更长。所以在下层，会尽可能的使用写回。

局部性

一个具有良好局部性的程序，通常会有着更好的效率。它们倾向于使用离它们较近的数据项，或是最近引用过的数据项，这被称为局部性原理。

局部性别分为空间局部性和时间局部性。对于一个良好的时间局部性程序，被引用过一次的内存位置会在不久后再次被引用。对于一个良好的空间局部性程序，如果一个内存位置被使用，那么它领近的内存位置也会被使用。

对程序数据引用的局部性

我们以一个简单的程序为例：

1
2
3
4
5
6
7
int sumvec(int v[N]){
    int i,sum=0;
    for(i=0;i<N;i++){
        sum += v[i];
    }
    return sum;
}

对于sum，由于它在每次迭代中都被使用，所以我们称它有良好的时间局部性，但是它是一个标量，所以不存在空间局部性。对于向量v，它是被顺序读取的，所以我们称它有良好的空间局部性，但是由于每个位置只访问一次，所以我们说v的时间局部性很差。

我们说像sumvec这样顺序访问一个向量每个元素的函数，是具有步长为1的引用模式（相对于元素的大小）。有时我们称步长为1的引用模式为顺序引用模式。一个连续向量中，每隔k个元素进行访问，就称为步长为k的引用模式，步长越长，空间局部性就越差。

取指令的局部性

程序指令存放在内存中，CPU需要取出这些指令，所以我们也可以评价一个程序关于取指令的局部性。对于循环，通常是在连续的空间中进行的，所以它有良好的空间局部性，由于它会被反复调用，所以也有着良好的时间局部性。举个例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// clang-format off
hotblock1:
    Stmts; // <-- 热！
    if (/* 边界条件不成立 */ true)
        goto hotblock2; // 经常发生！ ------+
coldblock:                           /*   |   */
    Stmt; // <- 冷                        |
    Stmt; // <- 冷                        |
    Stmt; // <- 冷                        |  跨越了大量指令，代价高昂！
    Stmt; // <- 冷                        |
    Stmt; // <- 冷                        |
    Stmt; // <- 冷                        |
    Stmt; // <- 冷                        |
hotblock2:                          /*    |   */
    Stmts; // <- 热！           <----------+
1
2
3
4
5
6
7
8
9
10
11
12
13
// clang-format off
hotblock1:
    Stmts; // <-- 热！
    if (/* 边界条件 */ false)
        goto coldblock; // 很少发生
hotblock2:                         /*   |  低代价！  */
    Stmts; // <- 热！  <-----------------+
coldblock:
    Stmt; // <- 冷
    Stmt; // <- 冷
    Stmt; // <- 冷
    Stmt; // <- 冷
    Stmt; // <- 冷

代码区别于程序数据的一点在于，在运行时它是不能被修改的，CPU只从内存中读取指令，并不修改它。

编写高速缓存友好的代码

明白了高速缓存的工作原理之后，我们可以更准确的描述局部性了，局部性较好的程序通常意味着较高的命中率，不命中率较低的程序往往运行的会更快。所以编写局部性好的程序实际上是编写对高速缓存友好的程序。

下面就是我们用来确保代码高速缓存友好的基本方法：

  • 让常见的情况运行得快，程序通常把大部分时间花在少量的核心函数上，而这些函数通常把大部分时间花在了少量的循环上，所以要把注意力击中在核心函数的循环上，忽略其他部分。
  • 尽量减少每个循环内部的缓存不命中数量，在其他条件相同的情况下（加载存储操作次数），不命中率低的程序通常循环运行的更快。

同时还有几个重要问题：

  • 对局部变量的反复引用是好的，因为编译器能够将它们缓存在寄存器中（时间局部性）
  • 步长为1的顺序引用是好的，因为存储器层次结构中所有层次上的缓存都是讲数据存储为连续的块（空间局部性）

我们这里以n*n矩阵相乘为例：

让 C = A x B，我们通常会写出以下代码：

1
2
3
4
5
6
7
for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
        for(int k=0;k<n;k++){
            C[i][j] = A[i][k]*B[k][j];
        }
    }
}

根据i,j,k不同的循环顺序，实际上我们可以写出六个版本的矩阵乘法，但是它们是否互相等价呢？

image.png

我们可以分析，对于循环的过程中，我们总是希望步长是尽可能小的。所以我们优先考虑B矩阵的数据，对于B[k][j]的迭代，我们希望是kj顺序的，此时是顺序执行，空间局部性良好。对于左边的A[i][k]，我们应该优先考虑对k的迭代，以保证步长尽可能的小，所以使用ik顺序迭代。综上所述，ikj循环才是性能最好的，其他的就不过多赘述。反向分析即可。

在对程序空间局部性的分析过程中，我们要考虑到缓存时是行缓存存储的，所以应该尽可能的让要使用的数据在空间上是连续接近的。同时将目光聚焦于内循环（程序中迭代次数最多的代码块）中，以获得最好的局部性。对于新引入的数据对象，我们也应该多使用它，利用好时间局部性。

发表于 分类于
本文字数： 1.7k 阅读时长 ≈ 2 分钟

螺旋矩阵题型总结。我刷了几道螺旋矩阵相关的题目，这里我们介绍一下一些常见的解法。

螺旋矩阵

方形矩阵

当我们遇到n*n的方形矩阵时，可以用一种特殊的解法来遍历实现，以下面这道题为例：

59. 螺旋矩阵 II

我们可以定义几个变量用来控制遍历的行为：

  • startX：每次循环的起点的行数
  • startY：每次循环的起点的列数
  • offset：每循环一圈，用偏移量表现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> ans(n,vector<int>(n,0));
        int offset = 1 , startX = 0 , startY = 0;
        int val = 1;
        int i,j;
        for(int k=0;k<n/2;k++){		//循环次数就是圈数
            for(j=startY;j<n-offset;j++)	//左上->右上（从此以下都是左闭右开）
                ans[startX][j] = val++;
            for(i=startX;i<n-offset;i++)	//右上->右下
                ans[i][j] = val++;
            for(;j>startY;j--)				//右下->左下	
                ans[i][j] = val++;
            for(;i>startX;i--)				//左下->右上
                ans[i][j] = val++;
            startX++;
            startY++;
            offset++;	//实际上更新offset就是在更新每次循环的边界（缩小）
        }
        if (n&1){	//如果矩阵的边长为奇数，最中间的值会没法遍历到
            ans[offset-1][offset-1] = val;
        }
        return ans;
    }
};

同时还可以将方形矩阵视作一种特殊的矩形矩阵，以下对矩形矩阵的所有解法对方形都适用。

矩形矩阵

有时候我们会发现矩阵是矩形的，或者只有一层，这个时候就需要用几个通用的方法，来实现。例题：

LCR 146. 螺旋遍历二维数组

54. 螺旋矩阵

2326. 螺旋矩阵 IV

模拟路径法

我们先分析我们的转向条件：（1）当前进的方向上碰到了边界（2）当前进的方向上是已经走过的路径

第一个条件比较好解决，第二条件我们需要维护一个和数组相同大小的矩阵，走过的路线我们设置为true，没走过的设置为false.

由于我们的转向动作是有序的，是顺时针，所以我们可以使用一个数组来存储我们的方向。当到达转向条件时，设置成下一个转向动作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
vector<int> spiralArray(vector<vector<int>>& array) {
        if(array.empty()||array[0].empty())	//判断数组是否为空，注意先后顺序，array[0]在array为空时是不能访问的
            return {};
        int row = array.size();
        int col = array[0].size();
        int total = row*col;
        vector<vector<bool>> use(row,vector<bool>(col,0));	//路径表
        vector<int> ans(total,0);
        vector<vector<int>> direction{{0,1},{1,0},{0,-1},{-1,0}};	//方向表（顺时针）
        int directionIdx = 0;	//方向表索引
        int i=0,j=0;
        for(int k=0;k<total;k++){
            ans[k] = array[i][j];
            use[i][j] = true;
            int ni = i + direction[directionIdx][0];	//预更新i
            int nj = j + direction[directionIdx][1];	//预更新j
            if(ni<0||ni>=row||nj<0||nj>=col||use[ni][nj]==true){	//根据预更新状态判断转向条件
                directionIdx = (directionIdx+1)%4;	//转向则把方向索引设置到下一位
            }
            //实际更新
            i = i + direction[directionIdx][0];
            j = j + direction[directionIdx][1];
        }
        return ans;
    }

层级遍历法（边界收缩）

这个和刚刚用来解决方形矩阵的方法是相同的，只不过更新方式和更新条件要更加复杂。

一开始先设定好边界，当移动到边界的时候就转向，然后收缩边界。这样的好处在于我们不用再特意维护一个数组来判断路径是否被走过 了。因为走过的路径被我们收缩了，所以就不用在考虑。只需要在边界做检测就好了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
vector<vector<int>> spiralMatrix(int m, int n, ListNode* head) {
        vector<vector<int>> ans(m,vector<int>(n,-1));
        int top = 0;	
        int bottom = m-1;	//-1是因为索引和实际位置的差值
        int left = 0;
        int right = n-1;
        while(left<=right&&top<=bottom){	//如果相等就说明，边界收缩了，遍历结束了
            for(int i=left;i<=right;i++)	
                ans[top][i] = val;
            top++;							//左上->右上 top边界收缩
            for(int i=top;i<=bottom;i++)
                ans[i][right] = val;
            right--;						//右上->右下 right边界收缩
            for(int i=right;i>=left;i--)
                ans[bottom][i] = val;
            bottom--;						//右下->左下 bottom边界收缩
            for(int i=bottom;i>=top;i--)
                ans[i][left] = val;
            left++;							//左下->右上 left边界收缩
        }
        return ans;
    }

螺旋生成矩阵

这个算是一个小特例，大多数题目是给你一个矩阵让你去螺旋遍历，但是有的题目需要你自己螺旋生成一个矩阵。我们看到下面的例题：

885. 螺旋矩阵 III

image.png

这道题需要我们形成一个螺旋的路径，然后返回矩形内的位置的坐标。难点在于这个螺旋路径的生成，因为转向的条件和每次前进的步长综合考虑起来条件会非常的复杂。下面的话给出两种方法。

边界扩展法

和我们之前所做的边界收缩相反，我们先界定好边界，然后每次转向时宽展这个方向上的边界。通过这种方式来动态的生成一个螺旋的路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
const int DIR[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};
vector<vector<int>> spiralMatrixIII(int rows, int cols, int rStart, int cStart) {
        vector<vector<int>> ans;
        int total = rows*cols;
        int num = 1;
        int i = rStart,j = cStart;	//令i,j记录路径的实时位置
        int left = cStart - 1,right = cStart + 1,top = rStart - 1,bottom = rStart + 1;	//确定边界
        int dir=0;	//记录方向
        while(num <= total){
            if(i>=0&&i<rows&&j>=0&&j<cols){	//当路径到达矩阵内部时，记录当前位置
                ans.push_back({i,j});
                num++;
            }
            if(dir==0&&j==right){	//如果向右移动触碰右边界
                dir+=1;				//则转向
                right++;			//并拓展右边界
            }else if(dir==1&&i==bottom){	//如果向下移动触碰下边界
                dir+=1;						//则转向
                bottom++;					//并拓展下边界
            }else if(dir==2&&j==left){		//...
                dir+=1;
                left--;
            }else if(dir==3&&i==top){		//...
                dir=0;
                top--;
            }
            i += DIR[dir][0];		//根据方向来更新位置
            j += DIR[dir][1];
        }
        return ans;
    }

规律法

我们可以观察螺线路径的一个显著规律：每转向两次会更新一次前进的步长

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
const int DIR[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
vector<vector<int>> spiralMatrixIII(int R, int C, int r0, int c0) {
    	int num=0;
    	int dir=0;
    	int run=2;	//步长计数器
        vector<vector<int>> ans;

        while(num < R * C){
            for(int i = 0; i < run / 2; i ++){   //遍历步长，每转两下就会增加一步
                if(r0 >= 0 && r0 < R && c0 >= 0 && c0 < C)
                    ans.push_back({r0, c0}), ++ num;
                r0 += DIR[dir][0];
                c0 += DIR[dir][1];
            }
            pos = (pos + 1) % 4;	//每遍历一次步长，就转向
            run++;		//利用取整的性质，每转向两次才会增加一次步长
        }
        return ans;
    }

总结

螺旋矩阵的关键在于边界的检测和变换，还有转向条件的判断。比较简单。

发表于 分类于 ，
本文字数： 3.2k 阅读时长 ≈ 3 分钟

我们已经尽可能的实现各种程度的优化了，但所谓知己知彼，百战不殆。我们不仅要了解程序的性能怎么去优化，同时也要了解制约程序进一步优化的因素是什么。

限制因素

关键路径指明了执行程序所需时间的基本下界。如果程序中有某条数据相关链，这条链上的所有的延迟之和等于T，那么程序至少需要T个周期才能执行完。我们还看到功能单元的吞吐量界限也是程序执行的一个下界。也就是说，假设一个程序一共需要N个某种运算的计算，而微处理器只有C个能执行这个操纵的功能单元，并且这些单元的发射时间为I，那么这个程序的执行至少需要N*I/C个周期。

不过以上是理想状态，实际过程中，我们仍然需要考虑其他的制约因素。

寄存器溢出

循环并行性的好处受汇编代码描述计算的能力限制（如果代码描述不出来，说明寄存器不够用了）。如果并行度p超过了可用的寄存器数量，那么编译器就会溢出。将某些临时值放到内存中，在堆栈上分配空间。比如下面的例子：

image.png

为啥20*20的循环展开反而不如10*10呢？现代x86-64处理器可以使用16个YMM寄存器来保存浮点数。一旦数量超过了可用的寄存器的数量，程序就必须在栈上分配变量。内存写入读取的过程会造成不必要的开销。不过大多数循环会在出现寄存器溢出之前就会达到吞吐量的极限。

分支预测和预测错误处罚

指令在进行分支预测时，往往会使用投机执行的机制，但是预测错误意味着很大的代价。虽然代价是无法避免的，但是我们是否可以减少这个代价呢？在x86-64的程序处理中有条件传送的指令。我们可以在进行分支跳转的时候，通过将条件转移编译成条件传送来，减少这个代价。我们直接结算出两个方向上的可能的值，然后根据条件传送选择期望的值。这样，我们就不用考虑条件是否满足了，因为没有代价。

抛开编译器的优化，我们又该如何编写能够减少分支预测处罚的代码呢?

不要过分关心可以预测的分支

错误的分支预测影响可能很大，但是并不意味着所有的程序分支都会减缓程序的运行。现代处理器的分支预测逻辑十分先进，对于循环语句的分支，往往会被预测为选择分支，这样只有最后一次才会导致预测错误。

所以在程序性能优化（1）中的这个现象可以解释：

image.png

我们为了减少get_vec_element中的边界检测的延迟，改进成了combine3，发现程序性能几乎没什么改变，这是因为对于i的边界检测，是高度可预测的，对于计算机而言影响微乎其微。这些检测并不会影响程序的关键路径，或是起不到决定性作用。

书写适合用条件传送实现的代码

分支预测对于循环这种有规律的模式还行，但是程序中的大多数测试时完全不可预测的，依赖于数据的任意性，分支预测逻辑会表现得很糟糕。我们无法保证编译器会在编译中使用条件数据传送而不是条件控制转移，但是我们可以引导编译器进行我们想要的编译。

以一个程序为例，给定两个整数数组a和b，对于每个位置i，我们想要将a[i]设置为a[i]和b[i]中较小的那个，将b[i]设置成较大的那个。

首先是我们常用的风格：

1
2
3
4
5
6
7
8
9
10
void minmax1(long a[],long b[],long n){
    long i;
    for(i=0;i<n;i++){
        if(a[i]>b[i]){
            long t = a[i];
            a[i] = b[i];
            b[i] = t;
        }
    }
}

在这里可以看到，我们是在分支预测之后才执行交换的过程。这会扩大分支预测的代价。可是我们尝试另一种写法：

1
2
3
4
5
6
7
8
9
void minmax2(long a[],long b[],long n){
    long i;
    for(i=0;i<n;i++){
        long min = a[i] < b[i] ? a[i] : b[i];
        long max = a[i] < b[i] ? b[i] : a[i];
        a[i] = min;
        b[i] = max;
    }
}

这里的话相当于去除了条件分支，先把每个位置的最大值和最小值计算出来，然后分别赋值给a[i]和b[i]。通过合理的安排代码，我们也可以更好的帮助编译器优化代码。

理解内存性能

内存性能实际上也是很重要的决定性因素，在之前的测试中，实际上访问的内存都十分少量。所有的现代处理器都包含一个或多个高速缓存存储器，以对少量的存储器提供快速的访问。接下来我们要进一步讨论加载和存储操作的程序的性能印象。不过我们默认所有的数据都是存放在高速缓存中的情况。

加载的性能

一个包含加载操作的程序性能既依赖于流水线的能力，也依赖于加载单元的延迟。在之前的合并函数中，无论什么数据类型和合并操作都无法让CPE下降到0.5以下。这是因为，每一个被计算的元素，所有的示例都需要熊内存中独一个值，对于两个加载单元而言，其每个时钟周期都只能启动一条加载操作，所以CPE不可能小于0.5

到目前为止我们并没有在示例中看到加载操作的延迟产生的影响。加载操作的地址只依赖于循环索引i，所以加载操作不会称为限制性能的关键路径的一部分。

但是我们可以手动构造一个由一系列加载操作构成的计算，一个加载操作的结果决定下一条操作的地址：

1
2
3
4
5
6
7
8
9
10
11
12
13
typedef struct ELE{
    struct ELE* next;
    long data;
}list_ele,*list_ptr;

long list_len(list_ptr ls){
 	long len = 0;
    while (ls){
        len ++;
        ls = ls->next;
    }
    return;
}

在这里变量ls的每个后续只依赖于指针引用ls->next读出的值。我们可以关键部分的汇编代码：

1
2
3
4
5
.L3:
	addq $1,%rax
	movq (%rdi),%rdi	;ls = ls->next
	testq %rdi,%rdi
	jne .L3

我们可以可以看到movq是整个循环中关键的瓶颈，且每次循环都会依赖加载出来的%rdi的值，此时的程序的CPE是由加载操作的延迟决定的。我们之后在存储器部分会详细讨论。

存储的性能

和其他的操作不一样，存储操作不会影响任何寄存器的值。一系列的存储操作并不会产生数据相关。只有加载操作会受存储操作结果的影响，因为只有加载操作才能从由存储操作写的那个位置读回值。

我们可以做一个实验来体现这种影响：

1
2
3
4
5
6
7
8
9
void write_read(long* src,long* dst,long n){
    long cnt = n;
    long val = 0;
    while (cnt){
        *dst = val;
        val = (*src)+1;
        cnt--;
    }
}

然后我们分别使用两种不同的调用方式：

image.png

最终的结果是示例A的CPE=1.3远快于示例B的CPE = 7.3。这背后的原因就是因为在调用write_read时，参数src和dst指向了同一个内存位置，导致产生了写/读相关——一个内存读的结果依赖于一个最近的内存写。

为了理解这背后具体的原理，我们需要更加仔细的看看加载和存储执行单元：

image.png

存储单元实际上会包含一个存储缓冲区，它包含已经被发射到存储单元而又还没完成的存储操作（这里的完成包括更新数据高速缓存）的地址和数据。提供这么一个缓冲区，使得一系列存储操作不必等待每个操作都更新高速缓存就能执行。当一个加载操作发生时，它必须检查存储缓存区中的条目，看看有没有地址匹配。如果有就取出相应的数据条目作为加载操作的结果。

其机器代码形式如下：

1
2
3
4
5
6
7
; src in %rdi , dst in %rsi , val in %rax
.L3:				; loop:
	movq %rax,(%rsi)	;write val to dst
	movq (%rdi),%rax	;t = *src
	addq $1,%rax		; val = t+1
	subq $1,%rdx		;cnt--
	jne .L3				;if != 0,goto loop

这里的movq (%rdi),%rax在实际的过程中被翻译成了两个操作：

  • s_addr指令计算存储操作的地址，在存储缓冲区创建一个条目，并设置该条目的地址字段
  • s_data操作设置该条目的数据字段。
image.png

这两个计算时独立执行的，不过它们之间有隐含的相关，实际上s_addr的操作必须在s_data之前。同时由于load操作需要检查所有未完成的存储操作的地址，所以s_addr到load之间也会存在数据相关。还有一个有条件的数据相关，存在于s_data和load之间（当%rsi和%rdi相等，即读写的地址相同），此时load操作必须等待直到s_data将它的结果存放到存储缓冲区中。反之，则继续进行。

我们依旧可以图形化抽象write_read的操作，来分析它的关键路径：

image.png

右边是最简情况，只保留了使用一次迭代中的值为下一次迭代产生的值的操作。

现在我们可以理解函数write_read的性能特征了，下面是内循环多次迭代形成的数据相关：

image.png

在示例A的情况下，有不同的源和目的地址，加载和存储操作都可以独立进行，因此唯一的关键路径是减少变量造成的，因此这个程序的CPE为1.0。对于示例B的情况下，源地址和目的地址相同，导致s_data和load指令之间的数据相关使得关键路径形成。其中包括了存储，加载，增加数据等操作，导致程序的CPE为7.0。

这个例子说明了，内存操作的细微之处。对于寄存器操作，在指令被译码成操作的时候，处理器就可以确定哪些指令会影响那些指令了。但是对于内存操作，只有到计算出加载和存储的地址被计算出来后，处理器才能确定那些指令会影响哪些。

我们可以通过设置中间变量的方式来避免写/读相关。例如：

我们有a，p两个数组，令p[0] = a[0]，p[i] = p[i-1] + a[i]，我们正常写出来的程序会是这样：

1
2
3
4
5
6
void psum1(long a[],long p[],long n){
    long i;
    p[0] = a[0];
    for (i=1;i<n;i++)
        p[i] = p[i-1] + a[i];
}

但是这里的p[i]=p[i-1] + a[i]存在着读/写相关。我们可以引入一个中间的存储变量，来避免这种数据上的依赖：

1
2
3
4
5
6
7
8
9
10
void psum1(long a[],long p[],long n){
    long i;
    long last_val,val;
    last_val = p[0] = a[0];
    for (i=1;i<n;i++){
        val = last_val + a[i];
        p[i] = val;
        last_val = val;
    }
}

总结：性能提高技术

  • 高效设计：为遇到问题选择适当的算法和数据结构，避免使用会渐进的产生糟糕性能的算法或编码技术。
  • 基本编码原则：避免限制优化的因素，这样编译器就能产生高效的代码。
    • 消除连续的函数引用：必要时，将计算移到循环外面。
    • 消除不必要的内存引用：引入临时变量来保存中间结果。只有在最后的值计算出来时，才将结果存放到数组或全局变量中
  • 低级优化：结构化代码以利用硬件功能。
    • 展开循环，降低开销，并且使得进一步的优化称为可能
    • 通过使用例如多个累计变量和重新结合等技术，提高指令的并行性
    • 用功能性的风格重写条件操作，使得编译采用条件数据传送

发表于 分类于 ，
本文字数： 1.6k 阅读时长 ≈ 1 分钟

上次我们分别从简单的过程调用的优化到了机器级层面的关键路径优化。在此基础之上，我们可以尝试更进一步的优化。

循环展开

循环展开通过增加每次迭代计算的元素的数量，减少循环的迭代次数。它从两个方面改进了程序的性能：

  • 减少了循环索引的计算和条件分支的判断
  • 提供了一些方法，进一步的变化代码，减少整个计算中关键路径上的操作数量

比如下面这个例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void combine5(vec_ptr v, data_t *dest){
    long i;
    long length = vec_length(v);
    long limit = length - 1;
    data_t *data = get_vec_start(v);
    data_t acc = IDENT;
    
    for(i=0;i<limit;i+=2)
        acc = (acc OP data[i]) OP data[i+1];
    
    for(;i<length;i++)
        acc = acc OP data[i];
    *dest = acc;
}

这里我们每次迭代都进行了两次迭代，我们可以看到一定程度上的性能优化：

image.png

实际上循环展开也有许多需要注意的地方，比如循环展开的边界条件。我们设我们的按k次进行迭代，也就是说每次会将从i到i+k-1的数据进行计算，但是可能会出现一个情况。我们的原迭代次数可能无法被k整除，这意味着我们可能会出现漏处理的情况，需要额外设置一个循环。那么第一个循环的边界应该到哪里为止呢？

1
i+k-1 < n --> i < n-k+1 --> limit = n-k+1

推断可知i只能小于我们得到的limit，以确保程序能够正常迭代。剩下的未能完全迭代的部分，我们使用另一个循环来继续计算。

但是循环展开的次数越多，性能的优化效果就越好吗？我们看到并非如此：

image.png

要理解为什么程序没法进一步的优化，我们需要分析程序的关键路径，我们将k=2 data_t=double OP=*时的关键代码转化成图形化表示：

image.jpg

我们进一步的化简，可以看到关键路径的状态：

image.png

无论怎么展开，关键路径上还是有n个mul操作，由于数据的依赖关系，这里的乘法操作在每次展开中实际上并不能并行处理。为了进一步的提高程序的性能，我们要想办法提高数据的并行性。

提高并行性

硬件通常有多个相同的硬件组成，实际上硬件有更高速率执行加法和乘法的潜力，但是我们的代码无法实现这个功能，这是因为我们将累计的值放在一个单独的变量中，在前一个操作结束前，我们都无法进行下一个整数操作，所以我们需要相办法打破这种顺序相关，来更好的利用硬件的并行性能。

多个累计变量

对于一个可交换可结合的合并运算来说，我么可以通过将一组合并运算拆分成多个部分，最后合并结果，来提高性能，比如对于：

Pn = a1 * a2 * …… * an 我们可以将其拆分成 POn = a1 * a3 * …… * a2i+1 和 PEn = a2 * a4 * …… * a2i，最后合并得到 Pn = POn * PEn

我们可以用代码实现，这种既做循环展开，又做两路并行的效果：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void combine6(vec_ptr v, data_t *dest){
    long i;
    long length = vec_length(v);
    long limit = length - 1;
    data_t *data = get_vec_start(v);
    data_t acc0 = IDENT;
    data_t acc1 = IDENT;
    
    for(i=0;i<limit;i+=2){
        acc0 = acc0 OP data[i];
        acc1 = acc1 OP data[i+1];
    }
    	
    for(;i<length;i++)
        acc0 = acc0 OP data[i];
    *dest = acc0 OP acc1;
}

性能如下：

image.png

我们的增加并行计算后的程序性能超过了延迟界限，相较于之前提升了两倍，这意味着我们很好的利用了并行计算的优势，我们可以根据对关键路径的分析中很好的看到这一点：

image.png

combine6中的两路并行优化将原来的一条关键路径拆分成了两条关键路径，现在每条关键路径上的mul操作变成了n/2次。使得程序的性能极大的提升，对于我们进行k*k的优化，我们可以在下图中看到效率的提升：

image.png

可以看到随着k的增加，甚至可以使程序的性能逼近吞吐量的界限。

但是，这样的并行计算一定很好吗？它也有着一定的副作用，受四舍五入和溢出的影响，可能会一定程度上改变程序的行为，造成一定的误差。需要酌情处理。

重新结合变换

现在我们需要探讨另一种打破顺序相关的方式以将性能提高到延迟界限之外。我们只需进行对combine5的循环逻辑进行微小的合并变换即可得到：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void combine7(vec_ptr v, data_t *dest){
    long i;
    long length = vec_length(v);
    long limit = length - 1;
    data_t *data = get_vec_start(v);
    data_t acc = IDENT;
    
    for(i=0;i<limit;i+=2)
        //原：acc = (acc OP data[i]) OP data[i+1];
        acc = acc OP (data[i] OP data[i+1]);
    
    for(;i<length;i++)
        acc = acc OP data[i];
    *dest = acc;
}

看上去并没有发生什么改变，但是实际测量的性能却得到了很好的提升：

image.png

我们还是分析关键路径：

image.png

我们可以看到，每次迭代的第一个乘法实际上不存在顺序相关的问题，它的每次计算不依赖于上一次的迭代寄存器，所以关键路径上只有一次乘法操作，另一次乘法操作始终可以并行操作。所以通过这种方式，关键路径上只有n/2次mul操作。

随着展开次数的增多，程序的性能也可以接近吞吐量界限。总的来说重新结合变换会减少计算中关键路径上操作的数量，通过更好的利用功能单元的流水线能力得到更好的性能。要注意的问题和上面一样。

优化合并小结

通过以上的例子，我们应该意识到现代处理器强大的计算能力，可是现代编译器因为种种原因始终不能完全的利用这些能力，但是我们可以按一些非程式化的方式来编写程序以激发这些能力。

发表于 更新于 分类于 ，
本文字数： 4.3k 阅读时长 ≈ 4 分钟

对于特定的程序而言，尤其是要长时间多次运行的程序而言，我们需要尽可能的优化他的效率。如计算效率，空间效率…大多数时候编译器会帮助我们完成这个工作，但是特定的场景中，我们需要自己实现程序的优化设计。

优化编译器的能力和局限性

在现代编译器中，编译器往往会通过各种复杂的算法，根据程序中的值，被计算被使用的过程，来优化程序的实现。其中以GCC为例，编译器为我们提供了一系列指定优化级别，如-Og是使用一些基本的优化。使用-O1 -O2 -O3则会使用更多的优化。但是可能会导致一些未定义的复杂的情况出现。

我们需要保证编译器对程序只进行 安全 的优化，也就是说对于程序所有可能遇到的情况，在C语言标准之下，优化后得到的程序和优化前得到程序应该有相同的行为。我们可以看下面的一个范例：

1
2
3
4
5
6
7
void twiddle1(long *xp,long *yp){
    *xp += *yp;		//两次读一次写
    *xp += *yp;		//两次读一次写
}
void twiddle2(long *xp,long *yp){
    *xp += 2* *yp	//两次读一次写
}

看上去，两个程序似乎有这相同的行为，而且看起来twiddle2有着更好的效率。但是实际上，当我们考虑xp=yp的情况时。我们发现twiddle1和 twiddle2的结果并不一样。所以编译器不应该将twddle2做为twiddle1的优化版本。

这种两个指针可能指向同一个内存位置的情况，我们称之为内存别名使用。在编译器优化中，我们必须假设不同的指针可能会指向内存中的同一个位置。这是妨碍优化的第一个因素。

第二妨碍优化的因素是函数调用，我们假设下面的这个范例：

1
2
3
4
5
6
7
long f();
long func1(){
    return f()+f()+f()+f();
}
long func2(){
    return 4*f();
}

我们乍一看可能认为func1和func2效果是相同的，实际上，当我们考虑如下情况时：

1
2
3
4
long counter = 0;
long f(){
    return counter++;
}

这个时候就会产生不一样的结果，这是因为这个函数有副作用——它修改了全局程序状态的一部分。改变调用它的次数，会的改变程序的行为。

如果编译器不会试图判断一个函数有没有副作用，那可能会被错误的优化成func2。相反，则会保持函数调用不变。不过还有现代编译器也会使用一种特殊的手段来实现这种优化——内联函数替换。如func1可能会被内联替换成：

1
2
3
4
5
6
7
long func1in(){
    long t = counter++; 	//+0
    t += counter++;			//+1
    t += counter++;			//+2
    t += counter++;			//+3
    return t;
}

这样的话就减少了函数调用的开销。同时我们可以实现进一步的优化：

1
2
3
4
5
long func1opt(){
    long t = 4*counter + 6;
    counter += 4;
    return t;
}

我们可以在gcc中使用-finline和-O1以上等级的优化实现这个优化。但是这个优化也有一定的代价，我们将函数调用的过程优化掉了，意味着我们不能在调试器中，跳转到对应的程序，这意味程序行为一定程度上的失真。

程序示例

为了说明一个抽象的程序是如何被系统地转换成更有效的代码的，我们使用一个基于下面的是向量数据结构的运行示例。

image.png

向量有两个内存块组成：头部和数据数组，其中头部的结构声明如下：

1
2
3
4
typedef struct{
    long len;
    data_t *data;
} vec_rec,*vec_ptr;

这个声明由data_t来表示基本元素的数据类型，我们可以指定类型给data_t。同时，我们还会分配一个len个data_t类型对象的数组，来存放实际的向量元素。

我们给出一个生成向量，访问向量元素，以及确定向量长度的基本过程：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
//生成指定长度的向量数组
vec_ptr new_vec(long len){
	//分配向量头部的空间
    vec_ptr result = (vec_ptr) malloc(sizeof(vec_rec));
    data_t *data = NULL;
    if(!result)
        return NULL;	//分配失败
    result->len = len;
    //分配数组的空间
    if(len>0){
        data = (data_t*)calloc(len,sizeof(data_t));
        if(!data){
            free((void *)result);
            return NULL;	//分配失败
        }
    }
    result->data = data;
    return result;
}

//访问向量中的指定元素并存储在指定空间中
int get_vec_element(vec_ptr v,long index,data_t *dest){
    if(index<0 || index>=v->len)
        return 0;
    *dest = v->data[index];
    return 1;
}

//返回向量的长度
long vec_length(vec_ptr v){
    return v->len;
}

我们在此基础上实现一个合并运算的实现，通过对基本元素IDENT和合并运算OP的不同声明，我们测量这个函数对不同运算的性能：

1
2
3
4
5
6
7
8
9
10
11
12
13
#define IDENT 0
#define OP +
//#define IDENT 1
//#define OP *
void combine1(vec_ptr v,data_t *dest){
    long i;
    *dest = IDENT;
    for (i = 0;i < vec_length(v);i++){
        data_t val;
        get_vec_element(v,i,&val);
        *dest = *dest OP val
    }
}

下面我们会给出程序的CPE效率（数值越小性能越好），以参考：

image.png

消除循环的低效率

我么可以看到过程combine1调用函数vec_length作为for循环的测试条件。这导致每次循环测试的过程中我们都会有一次函数调用开销，我们可以通过以下方式来减少这个开销：

1
2
3
4
5
6
7
8
9
10
11
void combine2(vec_ptr v,data_t *dest){
    long i;
    long length = vec_length(v);
    
    *dest = IDENT;
    for(i=0;i<length;i++){
        data_t val;
        get_vec_element(v,i,&val);
        *dest = *dest OP val;
    }
}

效果如下：

image.png

这个优化是一个常见的优化，叫做代码移动。这类优化包括识别要执行多次，但是计算结果不会改变的计算。因为可以将计算移动到不会被多次求值的部分。

很遗憾的是，现在的编译器并不能很好的实现这一点。这个看起来无足轻重的代码，实际上在循环次数高的使用环境下，极大的影响了程序的效率。

减少过程的调用

正如我们刚刚所提到的，在循环测试中的过程调用会导致程序的性能下降，同样的在循环体中的过程调用也会导致性能的开销。在我们的代码中，可以看到每次循环迭代都会调用get_vec_element，这个函数会对索引做边界检测，然后再获取指定的数据。

在这里我们可以简化这个过程，我们定义一个新的函数以获取向量的起始位置，然后通过数组索引访问，从而实现对元素的访问。避免在循环体中的过程调用：

1
2
3
4
5
6
7
8
9
10
11
12
13
data_t* get_vec_start(vec_ptr v){
    return v->data;
}
void combine3(vec_ptr v,data_t *dest){
    long i;
    long length = vec_length(v);
    data_t *data = get_vec_start(v);
    
    *dest = IDENT;
    for(i=0;i<length;i++){
        *dest = *dest OP data[i];
    }
}

效果如下：

image.png

令我们吃惊的是，性能并没有明显的提升。事实上，整数求和的性能还略有下降。显然是内存循环中的其他操作形成了瓶颈，限制性能超过调用get_vec_element我们之后还会在此回头看看这个现象。看看为什么combine2中反复的边界检查不会让性能更差。

消除不必要的内存引用

combine3的代码将合并运算的值累积在指针dest指定的位置。通过检查编译出来的内循环代码我们可以看出，每次我们对指定位置的计算都需要先从内存中取出，再重新存入。在此我们给出的数据类型为double,合并运算为乘法的汇编为：

image.png

在这里我们可以看出每次迭代都需要从内存中读出再写入内存。这样的内存读写十分浪费，我们应该先用一个临时寄存器来存储每次迭代后的值，等到迭代结束后，再将值写入内存，从而避免不必要的内存引用:

1
2
3
4
5
6
7
8
9
10
11
void combine4(vec_ptr v, data_t *dest){
    long i;
    long length = vec_length(v);
    data_t *data = get_vec_start(v);
    data_t acc = IDENT;
    
    for (i=0;i<length;i++){
        acc = acc OP data[i];
    }
    *dest = acc;
}

效果如下：

image.png

我们可以看到程序性能显著的提升。但是遗憾的是，编译器无法实现这个简单的变换，因为在大多数情况下，编译器并不能判断函数会在什么情况下被调用，以及程序员的本意是什么。所以在编译的过程中，往往只能进行保守的读写内存。

理解现代处理器

到现在为止，我们所运用的优化都是不依赖于目标机器的任何特性的。这些优化只是简单的降低了过程调用的开销，以及消除了一些妨碍优化的因素。但是随着进一步提高性能，我们必须考虑利用处理器微体系结构的优化，也就是处理器用来执行指令的底层系统设计。

实际上处理器的实际操作与通过观察机器级程序所察觉到的大相径庭。在代码级别上，我们认为程序是一条一条执行的，实际上，在实际的处理器中，使同时对多条指令求值的，我们称这个现象叫做指令并行.

我们对指令并行的认识来理解是什么限制了程序的最大性能：

  • 当一系列操作必须按照严格顺序执行时，就会遇到延迟界限，因为在下一条指令开始之前，这条指令必须结束。当代码中的数据相关限制了处理器利用指令并行的功能时，延迟界限能够限制程序性能
  • 吞吐量界限刻画了处理器功能单元的原始计算能力。这个界限时程序性能的终极限制。

整数操作

image.png

这是现代微处理器的一个简单的示意图。这和我们认知的处理器结构并不一样，我们称这种处理器是超标量的，意味着它可以在每个时钟周期执行多个操作，而且是乱序的——意味着指令执行的顺序并不一定要和它们在机器级程序中的顺序是一样的。整个设计由两个主要部分：控制单元和执行单元。前者负责从内存中读出指令序列，并根据指令序列生成一组针对程序数据的基本操作；后者负责执行这些操作。

ICU（控制单元）从指令高速缓存中读取指令，指令高速缓存是一个特殊的存储器，它包含最近访问的指令。ICU会在当前正在执行的指令很早之前取指，这样它才有足够的时间译码，并把操作发送到EU（执行单元）。同时处理器会使用分支预测预测目标地址，并使用投机执行的技术，处理器会开始取出位于它预测分支的地址的指令，在预测之前正确之前就执行这些操作。如果之后发现预测错误，则将状态重新设置到分支点的状态，并开始取出并执行另一个方向上的指令。

指令译码逻辑将接受实际的程序指令，并将它们转换成一系列的微操作。然后EU接受来自取指单元的操作。通常每个时钟周期会接受多个操作。这些操作被分配到功能单元中执行。

读写内存是由加载和存储单元实现的。加载单元处理从内存读数据到处理器的操作。存储单元处理从内存读数据到处理器的操作。这两个单元都有一个加法器来完成地址的计算。图中的数据高速缓存是一个高速存储器，存放着最近访问的数值。

使用投机执行结束对操作求值，但是最终结果不会存放在程序寄存器和数据内存中，直到处理器确定（确定预测是否正确）实际应该执行这些指令，分支操作被送到EU。如果预测错误，EU会丢弃分支点之后计算出来的结果。它还会发送信号告诉分支单元，说预测是错误的，并指出正确的目的和分支。

在ICU中，退役单元记录正在进行的处理，确保它们遵守机器级程序的顺序语义。退役单元控制这些寄存器的更新。指令译码时，关于指令的信息被防止在一个先进先出的队列中。这个信息会一直保持在队列中，直到发生：

  • 一条指令的操作完成了，而且所有引起这条指令的分支点也都被确认为预测正确，那么这条指令就退役了，所有对程序寄存器的更新都可以被实际执行了。
  • 如果引起该指令的某个分支点预测错误，这条指令会被清空，丢弃所有计算出来的结果。这样预测错误就不会改变程序的状态。

由于任何对程序寄存器的更新都是在指令退役的时候进行。为了加速从一条指令到另一条指令的结果的传送，许多信息都是在执行单元之间进行交换的，原理和之前的转发原理相同，只不过更加复杂精细。

实现操作数在执行单元间传送的常用机制是寄存器重命名。当一条更新寄存器r的指令译码时，产生一个标记t（一个执行该操作结果的唯一的标识符）。条目（r，t）被加入一张表中，这个表维护着每个程序寄存器与会更新该寄存器的操作的标识符间的关系。当某个执行单元执行完一个操作时，会产生一个结果（v，t）指明标记为t的操作产生值v。所有等待t为源的操作都能使用v作为源值，这就是一种形式的数据转发。

通过这个机制，值可以从一个操作直接转发到另一个操作，而不是写到寄存器文件中再读出来，使得第二个操作能够再第一个操作完成后尽快开始。重命名表只包含关于有未进行写操作的寄存器条目。如果一条被译码的指令需要某寄存器，但是又没有标记与这个寄存器相关联，那么可以直接从寄存器文件中获取这个操作数。

性能瓶颈

想要理解程序的性能，首先我们要能理解程序中的关键路径延迟。在迭代中，影响性能瓶颈的是迭代寄存器（在迭代中被更新，既作为操作数又作为结果的寄存器）的更新速度。因为其他的操作是可以利用现有的数据进行并行计算的，我们可以以下面的一个问题为例：

  • 多项式求值

a0 + a1X + a2X2 + ……. + anXn

这个求多项式的过程可以用下面的函数实现：

1
2
3
4
5
6
7
8
9
10
double poly(double a[],double x,long degree){
    long i;
    double result = a[0];
    double xpwr = x;
    for (i=1;i<=degree;i++){
        result += a[i]*xpwr;
        xpwr = x*xpwr;
    }
    return result;
}
  • Horner法多项式求值(减少乘法数量)

a0 + X ( a1 + X (a2 + …… + X (an-1 + Xan) … ))

这个求值过程，我们可以使用下面的函数实现：

1
2
3
4
5
6
7
double polyh(double a[],double x,long degree){
    long i;
    double result = a[degree];
    for (i=degree-1;i>=0;i--)
        result = a[i] + x*result;
    return result;
}

乍一看我们会认为下面的方法更加高效，因为相较于上面的程序，它只使用了一次乘法。但是事实真的是这样的嘛，我们测得poly的CPE比polyh更低。这是为什么呢？

image.png

我们可以判断程序的性能瓶颈主要体现在循环迭代的过程中，而迭代的性能是由迭代寄存器的更新的速度决定的。我们可以看到两个函数对迭代寄存器的更新情况：

  • poly：他有两个迭代对象，分别是result和xpwr，由于数据的关联性，两个数据的迭代是互不干扰的。而制约迭代性能的关键则是xpwr的更新——一次乘法。
  • polyh：它只有一个迭代对象result，它的每次更新需要一次乘法和一次加法，由于数据依赖的关联性，加法与乘法并不能并行处理。

所以综上所述，程序的性能实际上是由关键路径延迟所决定的，而不是由整体的运算量决定的。

发表于 更新于 分类于
本文字数： 980 阅读时长 ≈ 1 分钟

开始算法的简单学习，今天先从二分查找法开始

二分查找

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int binary_search(int start,int end,int key){
    int ret = -1;
    int mid;
    while (start <= end){
        mid = start + ((end - start) >> 1);
        if(arr[mid] < key)
            start = mid + 1;
        else if(arr[mid] > key)
            end = mid - 1;
        else{
            ret = mid;
            break;
        }
    }
    return ret;
}

这个是常用的二分法的代码实现，但是在这里我们仍然有很多要注意的地方：

while的循环条件与start end更新

有时候会疑惑循环不变量中我们什么时候使用<或<=。而在start和end的更新中不知道什么时候使用+1或-1或不变。我们需要理解什么情况下怎么去使用。

当有序数组的数据呈闭区间的时候，即[start,end]。我们令：

1
2
3
4
5
while(start <= end)		//当我们考虑start=end时，条件必须成立，所以等于关系也是其中的一种情况
...
start = mid + 1		//由于每一次的比较中，先前mid的值经过了一次比较，所以需要+1-1来避免重复比较
...
end = mid - 1

当有序数组存在开区间时，如[) (] ()，实际上它们都隐含了一个信息——start!=end，否则区间是不成立的，因此：

1
2
3
4
while(start < end)	//当start=end时，搜索区间实际上是不成立的
...
start = ？？？	//这个和左右的开闭性相关，要考虑什么时候该包括，什么时候不该包括，应该明确有效的搜索区间的范围是什么
end = ？？？

二分法解题思路

我们刚刚实现的是bsearch，即二分查找匹配的数值，实际上更多时候我们需要查找的是一个区间，即在数组内查找第一个不小于X的数值的下标：

1
2
3
4
5
6
7
8
9
10
11
12
int lower_bound(vector<int> arr, int target){
    left = 0;
    right = arr.size() - 1;
    while (left <= right){
        int mid = left + (right-left)>>1;
        if (arr[mid] < target)
            left = mid + 1;
        else:
        	right = mid -1;
    }
    return left;
}

现在，如果程序要求我们返回数组中一个=\>\>=\<\<=某个数的起始下标，实际上可以根据数组的有序性，将他们联系起来：

  • >= 这个是最基本的我们binary_search的返回值X就是它的左边界，得到答案 X
  • > 我们可以把这个问题的转换成，>= x+1 ，得到答案X+1
  • < 实际上就是>=问题的补集，得到答案(>=x) - 1
  • <= 是>问题的补集，我们可以得到答案 （>x）-1

以后遇到这种问题，都可以通过这种转换的思想来实现

练习：

704. 二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int start = 0;
        int end = nums.size()-1;

        while (start <= end){
            int mid = end + (start-end)/2;	//这里的除法我一开始使用了位运算，但是由于这里会涉及到有符号整数的运算，所以不能使用位运算
            int num = nums[mid];
            if(target > num)
                start = mid + 1;
            else if (target < num)
                end = mid - 1;
            else {
                return mid;
            }
        }
        return -1;
    }
};

34. 在排序数组中查找元素的第一个和最后一个位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int left = lower_bound(nums,target);
        if(nums.empty() || left == nums.size() || nums[left]!=target ){
            //当left==len(nums)时，说明数组中没有>=target的数
            return vector<int>{-1,-1};
        }
        int right = lower_bound(nums,target+1)-1;
        return vector<int>{left,right};

    }
    //返回>=target的第一个数
    int lower_bound(vector<int>& nums,int target){
         int start = 0;
         int end = nums.size() - 1;
         while (start <= end){
            int mid = (end - start)/2 + start;
            if(nums[mid] < target){
                start = mid + 1;
            }else{
                end = mid -1;
            }
         }
        return start;
    }
};

441. 排列硬币

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int arrangeCoins(int n) {
        if(n==1) return 1;
        int start = 1;
        int end = n;
        while (start <= end){
            long mid = start + ((end - start)>>1);
            if (mid*(mid+1)/2 <= n)	//更新比较条件
                start = mid +1;
            else
                end = mid-1;
        }
        return start-1;		//由于得到的是大于n的阶层数，所以想要得到能完整标识的阶层数要-1
    }
};

367. 有效的完全平方数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    bool isPerfectSquare(int num) {
        int start = 1;
        int end = num;
        while(start <= end){
            long mid = start + ((end -start)>>1);
            if(mid*mid==num){
                return true;
            }else if(mid*mid >num){
                end = mid-1;
            }else{
                start = mid +1;
            }
        }
        return false;
    }
};

发表于 更新于 分类于 ，
本文字数： 4.7k 阅读时长 ≈ 4 分钟

接着上一次的内容，中间有一段时间在忙着搞大作业的内容，所以就没继续搞这个了。今天我们将具体实现Y86-64的设计。

异常处理

异常控制流导致程序正常的执行流程被破坏掉。异常可以有程序内部产生，也可以由某个外部中断产生。我们的指令集主要包括三种类型：

  • halt指令
  • 非法指令和功能码组合的结果
  • 取指或数据读写访问了非法地址

我们需要考虑的问题也比较简单：

  1. 可能有多条指令引起异常。例如取指阶段遇到halt指令，然后访存阶段遇到了非法地址的访问。这个时候我们的处理器应该向操作系统返回哪个异常呢？我们的基本原则是：由流水线中最深的指令引起的异常，优先级最高，所以这里我们应该返回非法地址访问的异常

  2. 当取出一条指令时，开始执行时，导致了一个异常，而后来由于分支预测错误，取消了该指令。例如：

1
2
3
4
5
6
	xorq %rax,%rax
	jne target			;处理器默认选择分支
	irmovq $1,%rax
	halt
target:
	.byte oxFF			;非法地址

流水线默认选择分支，在译码阶段会发现一个非法指令异常。但是之后又会发现不应该预测分支，流水线控制逻辑会取消该指令。但是我们想要避免这个异常

  1. 流水线化的处理器会在不同的阶段更新系统状态的不同部分。有可能会出现这个情况，一个指令导致了一个异常，可是后面的指令在这个异常前改变了部分的状态。比如：
1
2
3
4
irmovq $1,%rax
xorq %rsp,%rsp		;CC=b100
pushq %rax			;假设此时的栈顶在0xfffffffffffffff8
addq %rax,%rax		;CC=b000

当push时，由于栈顶的移动会导致地址异常，同时addq此时位于执行阶段，它将条件码设置成了新的值。这就违反了异常指令之后所有指令不能影响系统状态的要求。

现在我们明确了我们需要解决的问题，首先需要避免由于分支预测错误取出的指令造成异常。所以我们要在每个流水线寄存器中包括一个状态码stat。如果一个指令在某个阶段中产生了一个异常，这个状态字段就被设置为异常的种类。异常和其他信息一起随着流水线传播，直到写回才发现异常，停止执行。

为了避免异常指令之后的指令更新任何程序员可见的状态，当访存或写回阶段中导致异常时，流水线控制逻辑必须禁止更新条件码寄存器或是数据内存。

所以综上所述，当流水线有一个或多个阶段产生异常时，信息只是简单的存放在流水线寄存器的状态字段中。异常事件不会对流水线中的指令流有任何影响，除了会禁止流水线后面的指令更新程序员可见的状态（条件码寄存器和内存），直到异常指令到最后的写回阶段。由于指令到达写回阶段的顺序就是异常发生的顺序，所以我们可以保证第一个发生异常的指令可以第一个到达写回阶段。如果取出了某条指令，过后又被取消了，那么所有的关于这条指令的异常信息都会被取消。所有导致异常的指令后面的指令都不能改变程序员可见的状态。携带指令的异常状态以及所有其他信息通过流水线的简单原则是处理异常的简单可靠的机制。

PIPE各个阶段实现

PIPE的具体实现和之前SEQ的实现基本差不多，只不过PIPE的每个状态都叫上了前缀。如”D_“表示源值，信息来自流水线D寄存器，而"d_"表示结果值，表明它是在译码阶段产生的。

PC选择和取指阶段

这个阶段用于选择程序计数器的当前值，用于预测下一个PC值。由于从内存中读取指令和抽取不同的字段的硬件单元一样，我就不重复了。

image.png

PC选择逻辑从三个程序计数器源中进行选择。当程序分支预测错误时，从M_valA中读出valP(不跳转的话本应执行的地址)。当ret指令进入写回阶段时，会从W_valM中读出返回地址。其他情况则会使用F阶段寄存器中的predPC的值，我们可以选择PC的值：

1
2
3
4
5
6
7
8
9
# f_pc 
# 分支预测有误则回退
if M_icode == JXX && !M_Cnd:
    f_pc = M_valA
# RET在写回阶段
else if W_icode == RET:
    f_pc = W_valM
else:
    f_pc = F_predPC

PC的预测逻辑则很简单。当函数为调用或跳转时，使用valC。否则用valP

1
2
3
4
5
# F_predPC
if f_icode in [JXX,CALL]:
    F_predPC = valC		
else:
    F_predPC = valP

关于Instr valid Need regids Need valC的逻辑块则和SEQ一样。

同时我们需要根据这些信息来确定程序的状态：

1
2
3
4
5
6
7
8
9
10
11
12
# f_stat
# 检查指令地址越界
if imem_error:
    f_stat = SADR
# 检查icode是否存在
else if !instr_valid:
    f_stat = SINS
# 检查手动中断
else if f_icode == HALT:
    f_stat = SHLT
else:
    f_stat = SAOK

译码和写回阶段

image.png

标号为"srcA" "srcB" "dstM" "dstE"的逻辑块我们在SEQ中已经实现过，基本不需要什么改动。不过我们也需要注意到，dstE和dstM写端口的寄存器ID不再是直接使用译码阶段所产生的，而是使用来自写回阶段的信号（W_dstE和W_dstM），这是因为我们希望写的目的寄存器是由写回阶段产生的。

不过这个阶段难在转发逻辑的实现上，尤其是”Sel+FwdA”块，不仅要实现valA的转发逻辑，还要实现valA和valP的合并。这两个信号之所以可以合并是因为，只有call和跳转指令才会用到valP的值，且不需要寄存器文件中读出来的值。这个选择通过icode信号可以控制实现。

接下来我们整理一下转发源和目的寄存器的关系以实现转发逻辑：

数据字 寄存器ID 源描述
e_valE e_dstE ALU输出
m_valM M_dstM 内存输出
M_valE M_dstE 访存阶段未对E进行的写
W_valM W_dstM 写回阶段未对M进行的写
W_valE W_dstE 写回阶段未对E进行的写

如果不满足任何的转发条件，就是用原来的d_rvalA作为输出：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# d_valA
# 注意这里的判断是有优先级的，阶段越浅的数据优先级越高，因为后执行的指令可能会覆盖先执行的指令的数据内容。同阶段的优先级需要特殊考虑
if D_icode in [JXX,CALL]:
    d_valA = D_valP
else if d_srcA == e_dstE:
    d_valA = e_valE
# popq %rsp会试图将两个值写入同一个寄存器中，valE是计算后的数据，有限考虑会造成冲突，与事实不符
else if d_srcA == M_dstM:
    d_valA = m_valM
else if d_srcA == M_dstE
	d_valA = M_valE
# 内存访问的值W_valM比计算出的值W_valE更"新鲜"
else if d_srcA == W_dstM:
    d_valA = W_valM
else if d_srcA == W_dstE:
    d_valA = W_valE
else:
    d_valA = d_rvalA

同理我们可以写出d_valB的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
# d_valB
if d_srcB == e_dstE:
    d_valB = e_valE
else if d_srcB == M_dstM:
    d_valB = m_valM
else if d_srcB == M_dstE:
    d_valB = M_valE
else if d_srcB == W_dstM:
    d_valB = W_valM
else if d_srcB == W_dstE:
    d_valB = W_valE
else:
    d_valB = d_rvalB

然后就是写回阶段的逻辑，写回阶段基本是不用保持不变的。其中Stat需要根据W中的状态值计算出来，因为W保存着最近完成的指令的状态，所以我们需要用这个信号来表示整个处理器的状态。不过也要考虑写回阶段有气泡时。这也是一种正常状态，我们可以写出：

1
2
3
4
5
# Stat
if W_stat == SBUB:
    Stat = AOK
else:
    Stat = W_stat

执行阶段

image.png

这一部分和SEQ种基本没有什么区别，其中e_dstE和e_valE被作为了指向译码阶段的转发源。不过有一点需要注意，SetCC不仅由icode控制，同时还以m_stat和W_stat作为输入。这样可以实现，当一条导致异常的指令通过后面的流水线时，任何对条件码的更新都会被停止。

访存阶段

image.png

访存阶段中SEQ和PIPE的逻辑基本差不多，区别在于，这里用了很多流水线的数值用来向译码阶段做转发源。同时我们在这里来验证程序地址的合理性从而计算m_stat：

1
2
3
4
5
# m_stat
if dmem_error:
    m_stat = SADR
else:
    m_stat = M_stat

流水线的控制逻辑

现在我们要创建我们的流水线控制逻辑，以完成我们处理器设计，我们需要处理以下四种情况，这是我们无法通过分支预测和数据妆发处理的：

  • 加载/使用冒险：在一条从内存中读出一个值的指令和一条使用该值的指令之间，流水线必须暂停一个周期
  • 处理ret：流水线必须暂停直到ret指令到达写回阶段
  • 预测错误的分支：再分支逻辑发现不应该选择分支之前，分支目标处的几条指令已经进入流水线了。必须取消这些命令，并从跳转指令后面的那条指令开始取指。
  • 异常：当一条指令导致异常，我们想要禁止后面的指令更新程序员可见的状态，并且再异常指令到达写回阶段时，停止执行。

我们先设计每种情况所期望的行为，然后再设计处理些情况的控制逻辑：

特殊控制情况所期望的处理

  • 加载/使用冒险：

    只有mrmovq和popq指令会从内存中读取数据。当这两条指令中的任一一条处于执行阶段时，并且需要该目的寄存器的指令正处在译码阶段时（此时我们无法完成数据转发）。我们需要将第二条指令阻塞在译码阶段，并在下一个周期，往执行阶段中插入一个气泡。此后转发逻辑会解决这个数据冒险，可以将流水线寄存器D保持为固定状态，从而将一个指令阻塞在译码阶段。这样做还可以保证流水线寄存器F保持在固定状态，由此第二条指令会被再取指一次。总而言之我们需要保持流水线寄存器F和D不变，并在执行阶段中差插入气泡。

  • 处理ret：

    对ret指令的处理，我们需要将流水线停顿三个时钟周期，直到ret经过了访存阶段，读出返回地址。我们遇到ret时会默认PC新值为valP，也就是下一条指令地址。然后会对下一条指令进行取指，在下一条指令的译码阶段会被插入气泡，空转三个周期。

  • 分支预测错误：

    当跳转指令执行到执行阶段时就可以检测到预测错误。然后在下一个周期，控制逻辑会在译码和执行阶段插入气泡，取消两条不正确的已取指令。在同一个时钟周期，流水线将正确的指令读取到取指阶段。

  • 异常：

    我们必须保证，在前面的所有的指令结束前，后面的指令不能影响程序的状态。当异常发生时，我们的stat信息作为指令状态的一部分记录下来，并且继续取指译码和执行命令。当异常指令到达访存阶段时，我们采取措施防止之后的指令会修改程序员可见的状态：（1）禁止执行阶段设置条件码（2）向内存中插入气泡，禁止数据向内存中写入（3）当写回阶段中有异常指令时，暂停写回阶段，暂停流水线。这样我们实现了异常发生之前的指令完成，异常发生之后的指令不对程序员可见的状态进行修改。

发现特殊控制条件

总结一下各个特殊控制触发的条件：

条件 触发条件
处理ret IRET∈{D_icode,E_icode,M_icode}
加载/使用冒险 E_icode∈{MRMOVL,POPL}&&E_dstM∈{d_srcA,d_srcB}
预测错误的分支 E_icode==JXX&&!e_Cnd
异常 m_stat∈{SADR,SINS,SHLT}||W_stat∈{SADR,SINS,SHLT}

流水线控制机制

我们对流水线控制需要使用两个最简单的机制：暂停和气泡。它们分别将指令阻塞在流水线寄存器中（让真个流水线暂时停滞），或是往流水线中插入一个气泡（用空操作替换错误指令）。

image.png
  • 在正常操作下，这两个输入都设为0，使得寄存器加载它的输入作为新的状态。
  • 在暂停时，将暂停信号设置为1，禁止更新状态。
  • 在气泡时，将气泡信号设置为1，寄存器状态会设置成一个固定的复位配置，得到一个等效于nop的状态
  • 当暂停信号和气泡信号都设为1时会导致错误

当我们遇到特定的条件时，我们可以将各个阶段的流水线状态设置为以下情况，以控制流水线逻辑：

条件/流水线寄存器 F D E M W
处理ret 暂停 气泡 正常 正常 正常
加载/使用冒险 暂停 暂停 气泡 正常 正常
预测错误的分支 正常 气泡 气泡 正常 正常

暂停后面跟气泡时为了取消进入该阶段的指令，避免产生影响

控制条件的组合

我们在之前的讨论中，默认一个时钟周期只能出现一个特殊情况，实际上，一个时钟周期可能会同时出现多种特殊情况的组合。我们把所有可能出现的特殊情况列出来，讨论它们组合的可能性。

image.png

从这里我们可以看出大多数的控制条件之间是互斥的。加载/使用要求执行阶段是加载指令，预测错误要求执行阶段是跳转指令，所以是冲突的。ret的另外两种情况也是同理。所以实际上只有组合A和组合B可能会出现。

组合A中执行阶段有一条不选择分支的跳转指令，而译码阶段有一条ret指令，这种组合要求ret位于不选择分支的目标处。流水线控制逻辑发现分支预测错误，因此要取消ret指令。由此我们可以得出控制逻辑的控制动作

条件/流水线寄存器 F D E M W
处理ret 暂停 气泡 正常 正常 正常
预测错误的分支 正常 气泡 气泡 正常 正常
组合A 暂停 气泡 气泡 正常 正常

因为下一个周期，PC选择逻辑会跳转到后面那条指令的地址，所以流水线寄存器F的保存的内容是无所谓的，因为正确的取指会覆盖他，错误的旧值会被取消。

组合B中包括一个加载/使用冒险，其中加载指令设置%rsp，然后ret用这个寄存器作为原操作数，因为它必须从栈中弹出返回地址。所以流水线控制逻辑应该将ret指令阻塞在译码阶段。我们看下组合B的控制逻辑的控制动作：

条件/流水线寄存器 F D E M W
处理ret 暂停 气泡 正常 正常 正常
加载/使用冒险 暂停 暂停 气泡 正常 正常
组合B 暂停 气泡+暂停 气泡 正常 正常
期望的情况 暂停 暂停 气泡 正常 正常

这里我们发现组合B需要进行特殊的处理。我们可以看到，在组合B的译码阶段，控制动作将寄存器的气泡信号和暂停信号同时设置成了1，这会导致错误。

实际上，我们在组合B中应该优先处理加载/使用冒险，我们要优先确保数据被成功加载后，再进行使用。所以这里将ret的处理推迟了一个周期。

控制逻辑的实现

下图是流水线控制逻辑的整体结构，根据流水线寄存器和流水线阶段的信号，控制逻辑产生流水线寄存器的暂停和气泡控制信号，同时决定是否更新条件码寄存器。

image.png

接下来我们将控制条件和控制动作结合起来，产生各个流水线控制信号的描述：

1
2
3
4
5
6
7
8
9
10
11
12
13
# F_stall
	# 加载/使用冒险
if (E_icode in [MRMOVQ,POPQ] and E_dstM in [d_srcA,d_srcB]):
    F_stall = 1
	# ret处理
else if RET in [D_icode,E_icode,M_icode]:
    F_stall = 1
    
    
# D_stall
	# 加载/使用冒险
if (E_icode in [MRMOVQ,POPQ] and E_dstM in [d_srcA,d_srcB]):
    D_stall = 1

遇到预测错误和ret指令时，流水线寄存器D必须设置成气泡。不过前面提到的对于加载/使用冒险和ret的组合，我们需要将流水线寄存器设置成暂停

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# D_bubble
	# 排除组合状态
if not (E_icode in [MRMOVQ,POPQ] and E_dstM in [d_srcA,d_srcB]):
	if RET in [D_icode,E_icode,M_icode]:
        D_bubble = 1
	# 分支预测错误
else if E_icode == JXX && !e_Cnd:
    D_bubble
  

# E_bubble
	# 分支预测错误
if E_icode == JXX && !e_Cnd:
    E_bubble = 1
	# 加载/冒险使用
else if (E_icode in [MRMOVQ,POPQ] and E_dstM in [d_srcA,d_srcB]):
    E_bubble = 1

同时为了避免异常后的指令更新了程序状态，我们设置条件码不被整数操作设置：

1
2
3
4
# set_cc
if E_icode == OPq:
    if (not m_stat in [SADR,SINS,SHLT] and not W_stat in [SADR,SINS,SHLT]):
        set_CC = 1

同时，在下一个周期需要向访存阶段插入气泡，因为如果访存或写回阶段有异常时，我们不希望其他的指令改变了内存状态：

1
2
3
4
5
# M_bubble
if m_stat in [SADR,SINS,SHLT]:
    M_bubble = 1
else if W_stat in [SADR,SINS,SHLT]:
    M_bubble = 1

为了在写回阶段将异常提交到异常处理程序，所以我们也需要在异常指令到达W阶段时，阻塞整个流水线。从而实现异常之前的指令都被完成，后续的指令像没执行过一样：

1
2
3
# W_stall
if W_stat in [SADR,SINS,SHLT]:
    W_stat

至此，我们处理器的流水线控制逻辑就实现了。