最小的 C 程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <sys/syscall.h>

.globl _start
_start:
  movq $SYS_write, %rax   // write(
  movq $1,         %rdi   //   fd=1,
  movq $st,        %rsi   //   buf=st,
  movq $(ed - st), %rdx   //   count=ed-st
  syscall                 // );

  movq $SYS_exit,  %rax   // exit(
  movq $1,         %rdi   //   status=1
  syscall                 // );

st:
  .ascii "\033[01;31mHello, OS World\033[0m\n"
ed:

问：这段代码是什么意思？

The Smallest C Program

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <sys/syscall.h>

.globl _start
_start:
  movq $SYS_write, %rax   // write(
  movq $1,         %rdi   //   fd=1,
  movq $st,        %rsi   //   buf=st,
  movq $(ed - st), %rdx   //   count=ed-st
  syscall                 // );

  movq $SYS_exit,  %rax   // exit(
  movq $1,         %rdi   //   status=1
  syscall                 // );

st:
  .ascii "\033[01;31mHello, OS World\033[0m\n"
ed:

Q: What does this piece of code mean?

ChatGPT：

这段代码是一个使用x86-64汇编语言编写的程序，它通过Linux系统调用实现了向标准输出打印红色文本并退出的功能。让我们一行一行地解释代码的含义：

  1. #include <sys/syscall.h>：这是一个系统调用头文件，其中包含了系统调用的常量定义。

  2. .globl _start：这个指令表示标记_start是一个全局标号，它是程序的入口点。

  3. _start:：这是程序的入口标号，也就是程序开始执行的地方。

  4. movq $SYS_write, %rax：将系统调用号SYS_write（代表write系统调用）加载到寄存器%rax中。在x86-64架构中，系统调用号是通过%rax寄存器传递的。

  5. movq $1, %rdi：将文件描述符1（标准输出）加载到寄存器%rdi中。在Linux中，标准输出的文件描述符是1。

  6. movq $st, %rsi：将字符串的起始地址st加载到寄存器%rsi中，作为write系统调用的第二个参数（即要打印的文本）。

  7. movq $(ed - st), %rdx：将字符串的长度(ed标号的地址 - st标号的地址)加载到寄存器%rdx中，作为write系统调用的第三个参数（即要打印的文本长度）。

  8. syscall：执行write系统调用，将指定的文本打印到标准输出。

  9. movq $SYS_exit, %rax：将系统调用号SYS_exit（代表exit系统调用）加载到寄存器%rax中。

  10. movq $1, %rdi：将返回状态码1加载到寄存器%rdi中，作为exit系统调用的参数。

  11. syscall：执行exit系统调用，程序终止执行。

  12. st:：这是一个标号，标识字符串的起始地址。

  13. .ascii "\033[01;31mHello, OS World\033[0m\n"：这是要打印的红色文本。在ASCII码中，\033表示转义字符，后面的[01;31m表示设置文本颜色为红色，Hello, OS World是要打印的文本，\033[0m表示恢复默认文本颜色，\n表示换行。

  14. ed:：这是一个标号，标识字符串的结束地址。

当程序执行时，它会将红色的"Hello, OS World"文本打印到终端，并退出执行。需要注意的是，这段代码只能在Linux系统上运行，因为它使用了Linux特定的系统调用方式。在其他操作系统上，这段代码可能会产生未定义的行为或错误。

编译指令：

image-20230724214148762

值得注意的是，上述代码执行后，终端显示的是小红叉。

通过阅读 ChatGPT 的回答，将 movq $1, %rdi 修改为 movq $0, %rdi后，程序执行后，终端将会显示小圆点。也即返回 0 。

image-20230724214805507

问：gcc -S 中的 S 选项是哪个单词的缩写，表示什么意思？

ChatGPT:

在GCC编译器中，选项-S表示"Assembly Output"的缩写，意思是生成汇编语言输出。当你使用gcc -S命令时，GCC将会把源代码编译成对应的汇编代码（以汇编语言的形式），而不进行进一步的汇编和链接，即不生成可执行文件。这个选项通常用于查看代码在汇编级别上的实现，方便进行代码优化、调试或者了解编译器的生成过程。

举例来说，如果你有一个C语言源文件example.c，你可以通过以下命令将其转换成汇编代码文件example.s：

1
gcc -S example.c

然后你可以打开example.s文件，查看对应的汇编代码。

使用 objdump -d a.out 查看 ELF 文件。

image-20230724215343836

只有一个 .text 区，401000 地址 <_start> 标记是程序的入口， 40102e <st> 开始应该是存放的字符串吧。

🌶️ Demo: 非递归实现汉诺塔问题

1
2
3
4
5
6
7
8
#include <stdio.h>
#include <assert.h>

#include "hanoi-nr.c"

int main() {
  hanoi(3, 'A', 'B', 'C');
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
typedef struct {
  int pc, n;
  char from, to, via;
} Frame;

#define call(...) ({ *(++top) = (Frame) { .pc = 0, __VA_ARGS__ }; })
#define ret()     ({ top--; })
#define goto(loc) ({ f->pc = (loc) - 1; })

void hanoi(int n, char from, char to, char via) {
  Frame stk[64], *top = stk - 1;
  call(n, from, to, via);
  for (Frame *f; (f = top) >= stk; f->pc++) {
    n = f->n; from = f->from; to = f->to; via = f->via;
    switch (f->pc) {
      case 0: if (n == 1) { printf("%c -> %c\n", from, to); goto(4); } break;
      case 1: call(n - 1, from, via, to);   break;
      case 2: call(    1, from, to,  via);  break;
      case 3: call(n - 1, via,  to,  from); break;
      case 4: ret();                        break;
      default: assert(0);
    }
  }
}
1
2
3
4
5
6
7
8
9
void hanoi(int n, char from, char to, char via) {
  if (n == 1) {
    printf("%c -> %c\n", from, to);
  } else {
    hanoi(n - 1, from, via, to);
    hanoi(1,     from, to,  via);
    hanoi(n - 1, via,  to,  from);
  }
}
1
2
a.out: hanoi-main.c hanoi-nr.c
	gcc -ggdb -Wall $<

问：详细解释这段代码（hanoi-nr.c）

ChatGPT:

这段代码实现了一个递归解法的汉诺塔问题。汉诺塔问题是经典的递归问题，目标是将一堆从小到大依次放置的圆盘从一个柱子移动到另一个柱子，移动过程中始终保持大圆盘在小圆盘之上。

让我们逐行解释代码的含义：

  1. typedef struct { ... } Frame;：定义了一个名为Frame的结构体类型，包含了整数pc、n，以及字符from、to、via。

  2. #define call(...) ({ *(++top) = (Frame) { .pc = 0, __VA_ARGS__ }; })：这是一个宏定义，用于模拟函数调用。call(...)会将参数打包成一个Frame结构体，并将其压入堆栈（用top指针指向堆栈顶部），然后将pc（程序计数器）设置为0，模拟函数的入口处。

  3. #define ret() ({ top--; })：这是另一个宏定义，用于模拟函数返回。ret()会将堆栈顶部的Frame结构体弹出，模拟函数返回。

  4. #define goto(loc) ({ f->pc = (loc) - 1; })：这是第三个宏定义，用于模拟函数内部的跳转。goto(loc)会将当前函数的pc设置为loc - 1，相当于将程序计数器设置到目标位置，模拟函数内部的跳转。

  5. void hanoi(int n, char from, char to, char via) { ... }：这是汉诺塔问题的函数实现，采用了非递归的方式。

  6. Frame stk[64], *top = stk - 1;：定义了一个名为stk的Frame数组，用于模拟函数调用堆栈。top是一个指针，初始时指向堆栈的顶部，但是由于数组从0开始索引，所以初始时指向堆栈的下一个位置（stk-1）。

  7. call(n, from, to, via);：模拟了对hanoi函数的第一次调用。将初始的汉诺塔问题参数压入堆栈，然后进入非递归的汉诺塔求解过程。

  8. for (Frame *f; (f = top) >= stk; f->pc++) { ... }：进入一个循环，条件是堆栈不为空。每次循环都取出堆栈顶部的Frame结构体，然后根据pc的值执行不同的操作。

  9. n = f->n; from = f->from; to = f->to; via = f->via;：从当前帧结构体中取出参数值，准备执行对应的操作。

  10. switch (f->pc) { ... }：根据当前帧的pc值，进行不同的操作。在这个非递归实现中，相当于模拟递归函数中的不同递归调用。

  11. case 0: if (n == 1) { printf("%c -> %c\n", from, to); goto(4); } break;：当pc为0时，执行移动一个圆盘的操作，即将from柱子上的圆盘移动到to柱子上，并输出移动的路径。然后通过goto(4)跳转到case 4，模拟递归函数返回的操作。

  12. case 1: call(n - 1, from, via, to); break;：当pc为1时，执行递归调用，将规模减一的子问题从from柱子经过to柱子移动到via柱子。

  13. case 2: call(1, from, to, via); break;：当pc为2时，执行移动最后一个圆盘的操作，将from柱子上的最后一个圆盘移动到to柱子上。

  14. case 3: call(n - 1, via, to, from); break;：当pc为3时，执行递归调用，将规模减一的子问题从via柱子经过from柱子移动到to柱子。

  15. case 4: ret(); break;：当pc为4时，执行函数返回操作，相当于递归函数的返回。

  16. default: assert(0);：如果pc的值超出了预期的范围，这里使用了assert(0)语句来触发断言，表示出现了意料之外的错误。

总体上，这段代码通过使用一个自定义的堆栈（stk数组）和宏定义（call()、ret()、goto()）的方式，实现了非递归解法的汉诺塔问题。这种方法模拟了函数调用和返回的过程，避免了递归调用时的函数调用栈溢出问题，是一种较为巧妙的非递归解法。

Demo: 在代码中控制编译优化

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
void spin_1() {
  int i;
  for (i = 0; i < 100; i++) {
    // Empty loop body
  }
}

void spin_2() {
  volatile int i;
  for (i = 0; i < 100; i++) {
    // Empty loop body
  }
}

int return_1() {
  int x;
  for (int i = 0; i < 100; i++) {
    // Compiler will assign [%0] an assembly operand
    asm("movl $1, %0" : "=g"(x));  // "x = 1;"
  }
  return x;
}

int return_1_volatile() {
  int x;
  for (int i = 0; i < 100; i++) {
    asm volatile ("movl $1, %0" : "=g"(x));
  }
  return x;
}

int foo(int *x) {
    *x = 1; // Must write at least once
    *x = 1; // because *x may be used later in external function
    return *x; // Must be 1
}

void external();
int foo_func_call(int *x) {
  *x = 1;
  external(); // May read or write x
  *x = 1;
  return *x; // Must be 1
}

int foo_volatile(int volatile *x) {
    *x = 1; // *x is volatile
    *x = 1;
    return *x;
}

int foo_volatile2(int * volatile x) {
    *x = 1; // x is volatile
    *x = 1;
    return *x;
}

int foo_barrier(int *x) {
    *x = 1;
    asm volatile("" : : : "memory"); // "Clobbers" memory
    *x = 1;
    return *x;
}

问：针对以上这些函数，编译器有权作出哪些优化？

ChatGPT:

针对以上这些函数，编译器可能会进行多种优化，取决于编译器的实现和优化级别。以下是编译器可能进行的一些优化：

  1. spin_1() 和 spin_2() 函数：
    由于这两个函数的循环体是空的，编译器可能会进行循环展开优化，将循环展开为直接执行100次空循环体的代码，以减少循环控制的开销。

  2. return_1() 和 return_1_volatile() 函数：
    由于这两个函数的循环体中对 x 的赋值语句没有实际的数据依赖关系，编译器可能会进行循环优化，将循环展开或消除循环，以减少循环控制的开销。此外，编译器可能会将循环内的赋值语句优化成直接的常数赋值。

  3. foo() 函数：
    这个函数中的循环体对 x 的赋值语句在循环内执行了两次，但是由于循环没有实际的数据依赖关系，编译器可能会进行循环优化，将循环展开或消除循环，并将两次赋值合并成一次赋值。

  4. foo_func_call() 函数：
    由于函数 external() 可能读写 x，而在调用 external() 前后都对 x 进行了赋值操作，编译器可能会进行函数内联优化，将 external() 函数的内容直接嵌入到 foo_func_call() 中，以避免在函数调用时产生额外的函数调用开销。

  5. foo_volatile() 和 foo_volatile2() 函数：
    这两个函数中的 x 声明为 volatile，意味着编译器不能对它们进行某些优化，以确保对 x 的读写操作不会被优化掉，因为 x 被标记为 volatile 表示它可能会在未知的时间被外部因素更改。编译器可能会确保对 x 的赋值和读取在最终生成的汇编代码中按照源代码的顺序执行。

  6. foo_barrier() 函数：
    在循环内部的 asm volatile("" : : : "memory") 语句使用了 "memory" clobber，这告诉编译器这个内联汇编代码可能会访问任何内存地址，从而避免编译器在该语句之前或之后的代码重排。因此，这个语句会产生一个内存屏障，确保编译器不会在这个语句附近进行优化，以保证内存访问的顺序性和可见性。

需要注意的是，编译器的优化行为可能受到编译器版本、编译器选项和目标平台的影响。不同的编译器可能会有不同的优化策略和行为。要了解具体的优化效果，可以使用特定编译器版本和选项进行实际测试和分析。

这个回答中关于 return_1() 和 return_1_volatile() 的说法正确吗…

操作系统上的应用程序

1
2
3
4
5
#include <stdio.h>

int main() {
  printf("Hello World\n");
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <sys/syscall.h>

.globl _start
_start:
  movq $SYS_write, %rax   // write(
  movq $1,         %rdi   //   fd=1,
  movq $st,        %rsi   //   buf=st,
  movq $(ed - st), %rdx   //   count=ed-st
  syscall                 // );

  movq $SYS_exit,  %rax   // exit(
  movq $1,         %rdi   //   status=1
  syscall                 // );

st:
  .ascii "\033[01;31mHello, OS World\033[0m\n"
ed:
1
2
3
4
5
6
7
8
9
10
a.out: minimal.S
	gcc -S minimal.S > minimal.s
	as minimal.s -o minimal.o
	ld minimal.o

gcc-demo:
	strace -f gcc hello.c

xedit-demo:
	strace xedit

在我的电脑上使用 strace 命令查看 gcc 编译过程执行了哪些其他工具。

1
strace -f gcc hello.c |& grep -e execve

image-20230725214010695

可以看到：

  1. 首先使用了执行了gcc 程序。
  2. 然后执行了 cc1 程序，pid 是 29651, 过一会它正确退出了，返回了 0 。
  3. 然后尝试寻找 as ，失败了好多次。最后执行的是 /usr/bin/as ，并且也是过一会正确退出。
  4. 教科书上告诉我下一个环节就是 链接 了，但很明显，ld 之前还执行了个 collect2 程序。
  5. 最后执行 ld 程序进行链接。

那么，

问: gcc 编译过程中 collect2 作了哪些工作？

ChatGPT:

在GCC（GNU Compiler Collection）编译过程中，collect2是一个重要的工具程序，它实际上是GNU链接器ld的一个驱动程序。collect2起着将目标文件（Object Files）转换为可执行文件的作用。以下是collect2在GCC编译过程中所做的主要工作：

  1. 链接目标文件（Object Files）：GCC编译过程通常分为四个阶段：预处理、编译、汇编和链接。在前三个阶段之后，会生成一组目标文件（通常以.o结尾）。collect2的首要任务是将这些目标文件进行链接，即将它们组合成一个单一的可执行文件。

  2. 解析启动文件（Startup Files）：可执行文件在执行时需要一些初始化工作，这些初始化工作包括设置堆栈、全局数据初始化等。这些初始化工作通常由启动文件完成。collect2会选择合适的启动文件，并将其链接到生成的可执行文件中。

  3. 解析共享库（Shared Libraries）：如果程序依赖于共享库（动态链接库），collect2会查找并解析这些共享库，将它们的代码和数据链接到可执行文件中，以便在运行时动态加载这些共享库。

  4. 符号解析与重定位：在链接过程中，目标文件之间可能会存在相互引用的符号（比如函数、变量等）。collect2会负责解析这些符号引用，确保它们能正确地连接到对应的定义处。同时，collect2还会进行重定位操作，将各个目标文件中的地址信息调整到正确的位置，以便在内存中正确加载和执行。

  5. 生成可执行文件：经过上述步骤，collect2会将所有链接好的代码和数据组合成一个可执行文件，它可以直接在操作系统上运行。

总的来说，collect2是GCC编译过程中一个非常重要的环节，它将分散的目标文件与所需的其他资源进行组合和链接，最终产生可在操作系统上运行的可执行文件。

这… 真的不是在骗我吗？

关于 collect2, 详见 http://gcc.gnu.org/onlinedocs/gccint/Collect2.html

ChatGPT:

This code is a program written in x86-64 assembly language. It prints red text to standard output and exits through Linux system calls. Let me explain the meaning of the code line by line:

  1. #include <sys/syscall.h>: this is a system call header file, which contains the constant definitions of system calls.

  2. .globl _start: this directive marks _start as a global label, and it is the entry point of the program.

  3. _start:: this is the entry label of the program, that is, where the program starts executing.

  4. movq $SYS_write, %rax: loads the system call number SYS_write (representing the write system call) into the %rax register. In the x86-64 architecture, system call numbers are passed through the %rax register.

  5. movq $1, %rdi: loads file descriptor 1 (standard output) into the %rdi register. In Linux, the file descriptor of standard output is 1.

  6. movq $st, %rsi: loads the starting address st of the string into the %rsi register, as the second argument of the write system call (that is, the text to be printed).

  7. movq $(ed - st), %rdx: loads the length of the string (the address of the ed label minus the address of the st label) into the %rdx register, as the third argument of the write system call (that is, the length of the text to be printed).

  8. syscall: executes the write system call, printing the specified text to standard output.

  9. movq $SYS_exit, %rax: loads the system call number SYS_exit (representing the exit system call) into the %rax register.

  10. movq $1, %rdi: loads return status code 1 into the %rdi register, as the argument of the exit system call.

  11. syscall: executes the exit system call, and the program terminates.

  12. st:: this is a label identifying the starting address of the string.

  13. .ascii "\033[01;31mHello, OS World\033[0m\n": this is the red text to be printed. In ASCII, \033 represents the escape character, the following [01;31m sets the text color to red, Hello, OS World is the text to be printed, \033[0m restores the default text color, and \n means a newline.

  14. ed:: this is a label identifying the ending address of the string.

When the program runs, it prints the red “Hello, OS World” text to the terminal and exits. Note that this code can only run on Linux, because it uses Linux-specific system call conventions. On other operating systems, this code may cause undefined behavior or errors.

Compilation command:

image-20230724214148762

It is worth noting that after the above code runs, the terminal displays a small red cross.

After reading ChatGPT’s answer and changing movq $1, %rdi to movq $0, %rdi, the program will display a small dot in the terminal after execution — that is, it returns 0.

image-20230724214805507

Q: In gcc -S, what word is the S option an abbreviation of, and what does it mean?

ChatGPT:

In the GCC compiler, the option -S stands for “Assembly Output”, meaning to generate assembly language output. When you use the gcc -S command, GCC compiles the source code into the corresponding assembly code (in assembly language form) without further assembling and linking, that is, without generating an executable file. This option is usually used to view the implementation of the code at the assembly level, making it convenient for code optimization, debugging, or understanding the compiler’s generation process.

For example, if you have a C source file example.c, you can convert it into the assembly code file example.s with the following command:

1
gcc -S example.c

Then you can open the example.s file and view the corresponding assembly code.

Use objdump -d a.out to view the ELF file.

image-20230724215343836

There is only one .text section; the <_start> label at address 401000 is the entry point of the program, and starting at 40102e, <st> should be where the string is stored.

🌶️ Demo: Non-recursive Implementation of the Tower of Hanoi

1
2
3
4
5
6
7
8
#include <stdio.h>
#include <assert.h>

#include "hanoi-nr.c"

int main() {
  hanoi(3, 'A', 'B', 'C');
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
typedef struct {
  int pc, n;
  char from, to, via;
} Frame;

#define call(...) ({ *(++top) = (Frame) { .pc = 0, __VA_ARGS__ }; })
#define ret()     ({ top--; })
#define goto(loc) ({ f->pc = (loc) - 1; })

void hanoi(int n, char from, char to, char via) {
  Frame stk[64], *top = stk - 1;
  call(n, from, to, via);
  for (Frame *f; (f = top) >= stk; f->pc++) {
    n = f->n; from = f->from; to = f->to; via = f->via;
    switch (f->pc) {
      case 0: if (n == 1) { printf("%c -> %c\n", from, to); goto(4); } break;
      case 1: call(n - 1, from, via, to);   break;
      case 2: call(    1, from, to,  via);  break;
      case 3: call(n - 1, via,  to,  from); break;
      case 4: ret();                        break;
      default: assert(0);
    }
  }
}
1
2
3
4
5
6
7
8
9
void hanoi(int n, char from, char to, char via) {
  if (n == 1) {
    printf("%c -> %c\n", from, to);
  } else {
    hanoi(n - 1, from, via, to);
    hanoi(1,     from, to,  via);
    hanoi(n - 1, via,  to,  from);
  }
}
1
2
a.out: hanoi-main.c hanoi-nr.c
	gcc -ggdb -Wall $<

Q: Explain this code in detail (hanoi-nr.c)

ChatGPT:

This code implements the Tower of Hanoi problem with a non-recursive solution. The Tower of Hanoi is a classic recursive problem: the goal is to move a stack of disks, arranged from small to large, from one peg to another, always keeping larger disks below smaller ones during the moves.

Let me explain the meaning of the code line by line:

  1. typedef struct { ... } Frame;: defines a struct type named Frame, containing integers pc, n, and characters from, to, via.

  2. #define call(...) ({ *(++top) = (Frame) { .pc = 0, __VA_ARGS__ }; }): this is a macro definition used to simulate function calls. call(...) packs the arguments into a Frame struct and pushes it onto the stack (with the top pointer pointing to the top of the stack), then sets pc (the program counter) to 0, simulating the function entry.

  3. #define ret() ({ top--; }): this is another macro definition used to simulate function returns. ret() pops the Frame struct at the top of the stack, simulating a function return.

  4. #define goto(loc) ({ f->pc = (loc) - 1; }): this is the third macro definition, used to simulate jumps inside a function. goto(loc) sets the pc of the current function to loc - 1, equivalent to setting the program counter to the target position, simulating a jump inside the function.

  5. void hanoi(int n, char from, char to, char via) { ... }: this is the function implementation of the Tower of Hanoi problem, using a non-recursive approach.

  6. Frame stk[64], *top = stk - 1;: defines an array of Frame named stk, used to simulate the function call stack. top is a pointer that initially points to the top of the stack, but since the array is indexed from 0, it initially points to the position before the stack (stk-1).

  7. call(n, from, to, via);: simulates the first call to the hanoi function, pushing the initial Tower of Hanoi parameters onto the stack, and then entering the non-recursive solving process.

  8. for (Frame *f; (f = top) >= stk; f->pc++) { ... }: enters a loop whose condition is that the stack is not empty. Each iteration takes the Frame struct at the top of the stack and performs different operations according to the value of pc.

  9. n = f->n; from = f->from; to = f->to; via = f->via;: retrieves the parameter values from the current frame struct, ready to perform the corresponding operations.

  10. switch (f->pc) { ... }: performs different operations according to the pc value of the current frame. In this non-recursive implementation, this is equivalent to simulating the different recursive calls in the recursive function.

  11. case 0: if (n == 1) { printf("%c -> %c\n", from, to); goto(4); } break;: when pc is 0, performs the operation of moving one disk, that is, moving the disk on the from peg to the to peg and printing the move path. Then it jumps to case 4 via goto(4), simulating the return operation of the recursive function.

  12. case 1: call(n - 1, from, via, to); break;: when pc is 1, performs a recursive call, moving the subproblem of size one less from the from peg via the to peg to the via peg.

  13. case 2: call(1, from, to, via); break;: when pc is 2, performs the operation of moving the last disk, moving the last disk on the from peg to the to peg.

  14. case 3: call(n - 1, via, to, from); break;: when pc is 3, performs a recursive call, moving the subproblem of size one less from the via peg via the from peg to the to peg.

  15. case 4: ret(); break;: when pc is 4, performs the function return operation, equivalent to the return of the recursive function.

  16. default: assert(0);: if the value of pc exceeds the expected range, the assert(0) statement is used to trigger an assertion, indicating that an unexpected error has occurred.

Overall, this code implements a non-recursive solution to the Tower of Hanoi problem by using a custom stack (the stk array) and macro definitions (call(), ret(), goto()). This approach simulates the process of function calls and returns, avoiding the function call stack overflow that recursive calls may cause, and is a rather clever non-recursive solution.

Demo: Controlling Compiler Optimizations in Code

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
void spin_1() {
  int i;
  for (i = 0; i < 100; i++) {
    // Empty loop body
  }
}

void spin_2() {
  volatile int i;
  for (i = 0; i < 100; i++) {
    // Empty loop body
  }
}

int return_1() {
  int x;
  for (int i = 0; i < 100; i++) {
    // Compiler will assign [%0] an assembly operand
    asm("movl $1, %0" : "=g"(x));  // "x = 1;"
  }
  return x;
}

int return_1_volatile() {
  int x;
  for (int i = 0; i < 100; i++) {
    asm volatile ("movl $1, %0" : "=g"(x));
  }
  return x;
}

int foo(int *x) {
    *x = 1; // Must write at least once
    *x = 1; // because *x may be used later in external function
    return *x; // Must be 1
}

void external();
int foo_func_call(int *x) {
  *x = 1;
  external(); // May read or write x
  *x = 1;
  return *x; // Must be 1
}

int foo_volatile(int volatile *x) {
    *x = 1; // *x is volatile
    *x = 1;
    return *x;
}

int foo_volatile2(int * volatile x) {
    *x = 1; // x is volatile
    *x = 1;
    return *x;
}

int foo_barrier(int *x) {
    *x = 1;
    asm volatile("" : : : "memory"); // "Clobbers" memory
    *x = 1;
    return *x;
}

Q: For the functions above, what optimizations is the compiler entitled to make?

ChatGPT:

For the functions above, the compiler may perform a variety of optimizations, depending on the compiler implementation and the optimization level. The following are some optimizations the compiler may perform:

  1. The spin_1() and spin_2() functions:
    Since the loop bodies of these two functions are empty, the compiler may perform loop unrolling, expanding the loop into code that directly executes the empty loop body 100 times, to reduce the overhead of loop control.

  2. The return_1() and return_1_volatile() functions:
    Since the assignment statements to x in the loop bodies of these two functions have no actual data dependencies, the compiler may perform loop optimization, unrolling or eliminating the loop, to reduce the overhead of loop control. In addition, the compiler may optimize the assignment statements in the loop into direct constant assignments.

  3. The foo() function:
    The assignment statements to x in the loop body of this function are executed twice within the loop, but since the loop has no actual data dependencies, the compiler may perform loop optimization, unrolling or eliminating the loop, and merge the two assignments into one.

  4. The foo_func_call() function:
    Since the function external() may read or write x, and x is assigned both before and after the call to external(), the compiler may perform function inlining, embedding the content of external() directly into foo_func_call(), to avoid the extra function call overhead.

  5. The foo_volatile() and foo_volatile2() functions:
    x in these two functions is declared as volatile, which means the compiler cannot perform certain optimizations on them, to ensure that reads and writes of x are not optimized away, because x being marked volatile indicates that it may be changed by external factors at unknown times. The compiler may ensure that assignments to and reads of x are executed in the order of the source code in the final generated assembly.

  6. The foo_barrier() function:
    The asm volatile("" : : : "memory") statement in the loop uses a "memory" clobber, which tells the compiler that this inline assembly may access any memory address, preventing the compiler from reordering code before or after this statement. Therefore, this statement acts as a memory barrier, ensuring that the compiler does not perform optimizations near it, guaranteeing the ordering and visibility of memory accesses.

Note that the compiler’s optimization behavior may be affected by the compiler version, compiler options, and target platform. Different compilers may have different optimization strategies and behaviors. To understand the specific optimization effects, you can perform actual testing and analysis with a specific compiler version and options.

Is the answer correct about return_1() and return_1_volatile()…

Applications on the Operating System

1
2
3
4
5
#include <stdio.h>

int main() {
  printf("Hello World\n");
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <sys/syscall.h>

.globl _start
_start:
  movq $SYS_write, %rax   // write(
  movq $1,         %rdi   //   fd=1,
  movq $st,        %rsi   //   buf=st,
  movq $(ed - st), %rdx   //   count=ed-st
  syscall                 // );

  movq $SYS_exit,  %rax   // exit(
  movq $1,         %rdi   //   status=1
  syscall                 // );

st:
  .ascii "\033[01;31mHello, OS World\033[0m\n"
ed:
1
2
3
4
5
6
7
8
9
10
a.out: minimal.S
	gcc -S minimal.S > minimal.s
	as minimal.s -o minimal.o
	ld minimal.o

gcc-demo:
	strace -f gcc hello.c

xedit-demo:
	strace xedit

On my computer, I used the strace command to see which other tools are executed during the gcc compilation process.

1
strace -f gcc hello.c |& grep -e execve

image-20230725214010695

As you can see:

  1. First, the gcc program is executed.
  2. Then the cc1 program is executed with pid 29651; after a while it exits correctly, returning 0.
  3. Then it tries to find as, failing many times. What is finally executed is /usr/bin/as, which also exits correctly after a while.
  4. The textbook tells me the next stage is linking, but obviously, before ld, a collect2 program is also executed.
  5. Finally, the ld program is executed for linking.

So,

Q: What work does collect2 do during the gcc compilation process?

ChatGPT:

During the GCC (GNU Compiler Collection) compilation process, collect2 is an important tool program; it is actually a driver for the GNU linker ld. collect2 plays the role of converting object files into an executable file. The following are the main jobs collect2 does during the GCC compilation process:

  1. Linking object files: The GCC compilation process usually consists of four stages: preprocessing, compilation, assembly, and linking. After the first three stages, a set of object files (usually ending in .o) is generated. collect2's primary task is to link these object files, combining them into a single executable file.

  2. Resolving startup files: An executable file needs some initialization work when it runs, including setting up the stack, global data initialization, and so on. This initialization work is usually done by startup files. collect2 selects the appropriate startup files and links them into the generated executable file.

  3. Resolving shared libraries: If the program depends on shared libraries (dynamic link libraries), collect2 finds and resolves these shared libraries, linking their code and data into the executable file, so that these shared libraries can be loaded dynamically at runtime.

  4. Symbol resolution and relocation: During linking, object files may reference symbols from each other (such as functions, variables, etc.). collect2 is responsible for resolving these symbol references, ensuring that they are correctly connected to their corresponding definitions. At the same time, collect2 also performs relocation, adjusting the address information in each object file to the correct positions, so that the program can be loaded and executed correctly in memory.

  5. Generating the executable file: After the above steps, collect2 combines all the linked code and data into an executable file that can run directly on the operating system.

In general, collect2 is a very important stage in the GCC compilation process; it combines and links the scattered object files with other required resources, finally producing an executable file that can run on the operating system.

This… is it really not tricking me?

For more about collect2, see http://gcc.gnu.org/onlinedocs/gccint/Collect2.html