open-courses
  • 公开课笔记
  • CMU 15-445/645 Database Systems
    • Relational Data Model
    • Advanced SQL
    • Database Storage
    • Buffer Pools
    • Hash Tables
    • Tree Indexes
    • Index Concurrency Control
    • Query Processing
    • Sorting&Aggregations
    • Join Algorithms
    • Query Optimization
    • Parallel Execution
    • Embedded Database Logic
    • Concurrency Control Theory
    • Two Phase Locking
    • Timestamp Ordering Concurrency Control
    • Multi-Version Concurrency Control
    • Logging Schemes
    • Database Recovery
    • Introduction to Distributed Databases
    • Distributed OLTP Databases
    • Distributed OLAP Databases
  • UCB - CS162
    • OS intro
    • Introduction to the Process
    • Processes, Fork, I/O, Files
    • I/O Continued, Sockets, Networking
    • Concurrency: Processes & Threads
    • Cooperating Threads, Synchronization
    • Semaphores, Condition Variables, Readers/Writers
    • Scheduling
    • Resource Contention & Deadlock
    • Address Translation, Caching
    • File System (18,19,20)
    • Distributed Systems, Networking, TCP/IP, RPC (21,22)
    • Distributed Storage, Key-Value Stores, Security (23)
    • Security & Cloud Computing (24)
    • Topic: Ensuring Data Reaches Disk
  • MIT - 6.006
    • Sequence and Set Interface
    • Data Structure for Dynamic Sequence Interface
    • Computation Complexity
    • Algorithms and Computation
    • Structure Of Computation
    • Graph & Search
    • Tree & Search
    • Weighted Shortest Paths
    • String Matching, Karp-Rabin
    • Priority Queue Interface & Implementation
    • Dictionary Problem & Implementation
    • Sorting
    • Dynamic Programming
    • Backtracking
    • Self-Balancing Tree
  • MIT - 6.824
    • 2PC & 3PC
    • Introduction and MapReduce
    • RPC and Threads
    • Primary/Backup Replication
    • Lab: Primary/Backup Key/Value Service
    • Google File System (GFS)
    • Raft
    • Lab: Raft - Leader Election
    • Lab: Raft - Log Replication
  • Stanford-CS107
    • 原始数据类型及相互转化
    • 指鹿为马
    • 泛型函数
    • 泛型栈
    • 运行时内存结构
    • 从 C 到汇编
    • 函数的活动记录
    • C 与 C++ 代码生成
    • 编译的预处理过程
    • 编译的链接过程
    • 函数的活动记录续、并发
    • 从顺序到并发和并行
    • 信号量与多线程 1
    • 信号量与多线程 2
    • 复杂多线程问题
    • 函数式编程 - Scheme 1
    • 函数式编程 - Scheme 2
    • 函数式编程 - Scheme 3
    • 函数式编程 - Scheme 4
    • 函数式编程 - Scheme 5
    • Python 基础
  • MIT - 6.001 - SICP
    • 什么是程序
    • 程序抽象
    • 替代模型
    • 时间/空间复杂度
    • 数据抽象
    • 高阶函数
    • Symbol
    • 数据驱动编程与防御式编程
    • 数据抽象中的效率与可读性
    • 数据修改
    • 环境模型
    • 面向对象-消息传递
    • 面向对象 - Scheme 实现
    • 构建 Scheme 解释器
    • Eval-Apply Loop
    • Normal Order (Lazy) Evaluation
    • 通用机
    • 寄存器机器
    • 子程序、栈与递归
    • 在寄存器机器中执行
    • 内存管理
  • MIT - 6.046
    • Randomized Algorithms
    • Skip Lists
  • System Design
    • Twitter
    • Cache Consistency & Coherence
  • DDIA 笔记
    • Replication
    • Transactions
    • The Trouble with Distributed Systems
    • Consistency & Consensus
  • Papers We Love
    • Consistent Hashing and Random Trees (1997)
    • Dynamic Hash Tables (1988)
    • LFU Implementation With O(1) Complexity (2010)
    • Time, Clocks, and the Ordering of Events in a Distributed System (1978)
    • Dapper, a Large-Scale Distributed Systems Tracing Infrastructure (2010)
    • Gorilla: A Fast, Scalable, In-Memory Time Series Database (2015)
  • Release It 笔记
    • Anti-patterns & Patterns in Microservice Architecture
  • Database Design
    • Log Structured Merge (LSM) Tree & Usages in KV Stores
    • Prometheus
Powered by GitBook
On this page
  1. Stanford-CS107

从 C 到汇编

第九课

本课 Jerry Chain 老师探讨了 C 代码编译以后的汇编语言的形式。C 代码编译后:

  1. 所有 C 语言类型消失

  2. 所有指针操作消失,如指针计算、&、* 以及 cast 等等

  3. ...

简而言之,C 语言向编程者提供的各种抽象都不复存在,仅剩赤裸裸的内存操作。

符号说明

本课中,R 指代 General Purpose Registers (GPR),R1 即第一个 GPR,R2 即第二个 GPR 等等。PC 为 Program Counter Register,它永远指向当前正在执行的汇编指令的地址。为了方便,本课中,R1 永远指向当前 Activation Record 的最低地址。此外,本课中的各种汇编指令默认操纵 4 字节数据。

另外,本文所用的汇编指令不是真正的汇编指令,仅仅是为了课程讲解需要构造的,但实际情况与此出入不大。

例1:简单计算和赋值

int i;
int j;

i = 10;
j = i + 7;
j++;

// ===== compiled to
// R -> general purpose registers
// R1 -> stores the base address of the activation record

// i = 10;
// M[R1+4] = 10;         // store operation

// j = i + 7;
// R2 = M[R1+4];         // load operation
// R3 = R2 + 7;          // ALU operation
// M[R1] = R3;           // store operation

// j++;
// R2 = M[R1];
// R2 = R2+1;
// M[R1] = R2;

本例内存的栈结构如下图所示:R1 指向当前 Activation Record 的最低地址,即为整型变量 j 的地址,而 R1 + 4 即为整型变量 i 的地址。j = i + 7 被编译成三个步骤,将内存地址 R1+4 中的连续 4 个字节复制到 R2 中,利用 ALU (Arithmetic Logic Unit) 计算 R2 + 7 的结果并存储到 R3 中,再将 R3 中的 4 个字节复制到内存地址 R1 中。接着,读入内存地址 R1 存储的 4 个字节数据到 R2,利用 ALU 自增 1 并写回 R2,再将计算结果写回原地址。这个过程抛弃了所有类型信息,只对 4 个字节进行读取、计算、写出。

问题1:为什么不直接将 j = i + 7 编译成 M[R1] = 10 + 7

问题2:为什么不直接将 j++ 编译成 M[R1] = 17 + 1

为了使编译出来的汇编语言更具扩展性,即如果把i = 10改成i = 11,j = i + 7 被编译而成的三个步骤无需改变。同理,j++; 被编译而成的三个步骤也无需改变。

例2:隐形类型转换

int i;
short s1;
short s2;

i = 200;      
s1 = i;
s2 = s1 + 1;

// i = 200;
// M[R1+4] = 200;

// s1 = i;
// M[R1+2] = M[R1+4];
// R2 = M[R1+4];
// M[R1+2] = .2R2; // only copy 2 bytes

// s2 = s1 + 1;
// R2 = .2M[R1+2]
// R3 = R2 + 1;
// M[R1] = .2R3;

本例的内存栈结构如下图所示:

本例 s1 = i 中 i 是整型,占 4 字节;s1 是短整型,占 2 字节,把整型赋数值赋给短整型,将只取其中两个字节,具体取哪两个字节取决于多字节数据类型的存储方式是大端还是小端。因此将 R2 中存储的 200 写回 R1+2 时,只写回原 4 个字节中的 2 个字节,因此 M[R1+2] = .2R2。s2 = s1 + 1,这里被编译成了 3 个汇编指令,分别是将 s1 写入 R2 中,利用 ALU 将 R2 自增的结果存到 R3 中,然后写回内存地址 R1 中。这里 R2 = .2M[R1+2] 只将内存 R1+2 处的 2 个字节复制到 R2 中,而 R2 为 4 个字节,余下的两个字节会自动填 0,而写出时也只写出 2 个字节,因此数值溢出产生的结果也就可以理解了。

例3:循环体

本例的内存栈结构如下图所示:

本例中 R1 为整数 i 的地址,R1+4 为数组 array 的地址。这里为了复用循环体,使用了

  1. 汇编指令 BGE (branch if greater than) ,当它的第一个操作数大于第二个操作数时,将往前跳转到第三个操作数所指的指令地址。其中 PC 为 Program Counter,它永远指向当前正在执行的汇编指令地址。

  2. 汇编指令 JMP,将跳到唯一的操作数所指的指令地址。

int array[4];
int i;

for (i=0; i < 4; i++) {
  array[i] = 0;
}
i--; 

// M[R1] = 0;
// R2 = M[R1];
// BGE = R2,4, PC + 40;

// array[i] = 0;
// R3 = M[R1];
// R4 = R3 * 4;
// R5 = R1 + 4;
// R6 = R4 + R5;
// M[R6] = 0;
// R2 = M[R1];
// R2 = R2 + 1;
// M[R1] = R2;
// JMP PC - 40;
// i--;

例4:指针强制转换

struct fraction {
  int num;
  int dnum;
};

struct fraction pi;
pi.num = 22;
pi.dnum = 7;
((struct fraction *)&pi.dum) -> dnum = 451;

// M[R1] = 22;
// M[R1+4] = 7;
// M[R1+8] = 451;

本例内存栈结构如下图所示:

我们发现复杂的指针强制转换语句最后竟然只被编译成一个简单的汇编指令!原因在于,指针、指针类型等都是 C 语言在编程上添加的抽象,只要通过了编译器的检查,最终这些抽象都会消失,编程赤裸裸的字节数据操作。

参考

Previous运行时内存结构Next函数的活动记录

Last updated 6 years ago

Stanford CS107: lecture 9
Github: ZhengHe-MD - lecture codes