程序的机器级表示

• x86-64 汇编基础部分
  • 数据类型
    • 整数按照长度分类：
      • 1 字节：b
      • 2 字节：字，w
      • 4 字节：双字，l
      • 8 字节：四字，q
    • 浮点数按照长度分类：
      • 4 字节：单精度
      • 8 字节：双精度
      • 10 字节
  • 通用寄存器
    • 命名规则：
      • 用前缀来区分寄存器的不同长度：
        • 无前缀：16 位
        • e：32 位
        • r：64 位
      • 用后缀来区分寄存器中的不同部分：
        • l：低 8 位（仅 a、b、c、d 16 位寄存器）
        • h：高 8 位（仅 a、b、c、d 16 位寄存器）
        • d：低 32 位（仅 %r8~%r15）
        • 其他: 所有部分
    • 通用寄存器名称及作用：
      • %rax：累加结果
      • %rbx：基址
      • %rcx：计数器
      • %rdx：数据
      • %rsi：源索引
      • %rdi：目标索引
      • %rsp：栈指针
      • %rbp：基址指针
      • %r8~%r15：64 位通用寄存器，没有特殊意义
  • 指令
    • 操作数与寻址
      • 多种形式（适用于所有指令）：
        • 立即数：相当于常量，硬编码在指令中，以 $ 开头。
        • 寄存器
        • 内存：用 () 表示一个内存单元，括号中间是内存地址。
      • 内存寻址方式：
        • 通用地址计算形式：<C>(<Rb>, <Ri>, <S>)，表示地址 <C> + <Rb> + <S> * <Ri>
        • 简单寻址：(<Rb>)
        • 变址：<C>(<Rb>)
    • 移动
      • mov?
        • 语法 mov? <S>, <D>，其中 ? 可以是 b、w、l、q，表示把 <S> 的值赋值给 <D>。
        • 操作数规则：
          • <S>、<D> 是操作数，可以是立即数、寄存器、内存。
          • 立即数只表示 32 位有符号整数。
          • <S>、<D> 不可以同时是内存位置。
        • <D> 为寄存器时的赋值规则：
          • 如果 ? 是 b 或 w，则只修改 <D> 的指定的位置和长度。
          • 如果 ? 是 l，则用 <S> 修改 D 的低 32 位，同时用 0 清空高 32 位。
          • 如果 ? 是 q，则使用全部寄存器空间，没有特殊情况。
      • movabsq
        • 语法 movabsq <S>, <D>，表示移动立即数。
        • <S> 是一个 64 位立即数，其他功能与 mov? 类似。
      • movz??
        • 语法 movz?? <S>, <D>，其中 ? 都可以是 b、w、l、q，表示赋值的时候清零高位（零扩展）。
        • 两个 ? 需要满足 <D> 的比 <S> 更长。?? 不能是 lq，因为这个是 movl 的默认行为。
      • movs??
        • 语法 movz?? <S>, <D>，表示赋值的时候使用符号扩展。
        • 其他与 movz?? 类似，但是存在 movslq。
      • c?t?
        • 语法 c?t?，表示对 %ax 类寄存器符号扩展再赋值给自身。
        • cltq 表示符号扩展 %eax，赋值给 %rax。
        • cqto 表示符号扩展 %rax，赋值给 %rdx:%rax，即结果的高位在 %rdx。
    • 算术/逻辑运算
      • leaq
        • 语法 leaq <C>(<Rb>, <Ri>, <S>), <D>，表示计算地址并赋值给 <D>。
        • 寻址计算可以用于表示乘和加，比分开的乘和加更高效。
      • 双目算术/逻辑指令
        • add? <S>, <D>，表示 <D> += <S>。
        • sub? <S>, <D>，表示 <D> -= <S>。
        • 乘法系列：
          • imul? <S>, <D>，表示补码 <D> *= <S>。
          • imulq <S>，表示补码 %rdx:%rax = <S> * %rax。
          • mul? <S>, <D>，表示无符号 <D> *= <S>。
          • mulq <S>，表示无符号 %rdx:%rax = <S> * %rax。
        • 除法系列：
          • idivq <S>，表示补码 %rax = %rdx:%rax / <S>，%rdx = %rdx:%rax % <S>。
          • divq <S>，表示无符号 %rax = %rdx:%rax / <S>，%rdx = %rdx:%rax % <S>。
        • and? <S>, <D>，表示 <D> &= <S>。
        • or? <S>, <D>，表示 <D> |= <S>。
        • xor? <S>, <D>，表示 <D> ^= <S>。
        • sal? <S>, <D>，表示 <D> <<= <S>。
        • sar? <S>, <D>，表示 <D> >>= <S>，即算术右移。
        • shr? <S>, <D>，表示 <D> >>>= <S>，即逻辑右移。
      • 单目算术/逻辑指令
        • neg? <D>，表示 <D> = -<D>。
        • not? <D>，表示 <D> = ~<D>。
        • inc? <D>，表示 <D> += 1。
        • dec? <D>，表示 <D> -= 1。
• 控制
  • 条件码
    • 条件码寄存器
      • 条件码寄存器保存上一条运算指令的结果的相关属性。
      • 常用条件码寄存器
        • CF：结果最高位发生进位时为 1。
        • ZF：结果为 0 时为 1。
        • SF：把结果看作补码，结果为负数时为 1。
        • OF：把运算看作补码上的运算，发生溢出时为 1。
    • 使用条件码判断
      • 判断无符号整数 a 和 b 大小：
        • 得到 a - b 结果的条件码，用 CF 和 ZF 判断。
        • CF == 1 则 a < b，CF == 0 && ZF == 0 则 a > b。
      • 判断补码整数 a 和 b 大小：
        • 得到 a - b 结果的条件码，用 SF、OF 和 ZF 判断。
        • SF ^ OF == 1 则 a < b，SF ^ OF == 0 && ZF == 0 则 a > b。
      • 判断整数 a 和 b 是否相等：
        • 得到 a - b 结果的条件码，ZF == 1 时 a == b。
      • 判断整数 a 是否等于 0：
        • 得到 a & a 结果的条件码，ZF == 1 时 a == 0。
    • 修改条件码指令
      • cmp? <Sb>, <Sa>：? 是数据长度，根据<Sa> - <Sb> 设置条件码。
        • 比较 a <cmp> b，使用 cmp? b, a，需要注意顺序。
      • cmp? <Sa>, <Sb>：? 是数据长度，根据<Sa> & <Sb> 设置条件码。
    • 提取条件码指令
      • 所有提取条件码的指令接受一个操作数，操作数为单字节，设置为 0 或 1。
      • ZF 系列：
        • sete <D> 或 setz <D>：结果等于 0，<D> = ZF。
        • setne <D> 或 setnz <D>：结果不等于 0，<D> = ~ZF。
      • SF 系列：
        • sets <D>：结果为负数，<D> = SF。
        • setns <D>：结果为 0 或正数，<D> = ~SF。
      • 无符号整数系列：
        • set{a,ae,b,be} <D> 或 setn{be,b,ae,a} <D>
        • 使用 CF、ZF。
      • 补码整数系列：
        • set{g,ge,l,le} <D> 或 setn{le,l,ge,g} <D>
        • 使用 OF、SF、ZF。
  • 跳转
    • 跳转指令
      • 无条件跳转：
        • jmp <L>：跳转到 <L> 这个指令，<L> 是标签或者地址。
        • jmp *<D>：* 是固定格式，目标地址从 <D> 中读取。
      • 条件跳转：与 set* 相对应，值为 1 时跳转。
        • j{e,ne} <L> 或 jz/jnz <L>
        • j{s,ns} <L>
        • j{a,ae,b,be} <L> 或 jn{be,b,ae,a} <L>
        • j{g,ge,l,le} <L> 或 jn{le,l,ge,g} <L>
  • 控制结构
    • if-else
      • 给定 C 语言结构：

        // <start>
        if (/* <cond> */) {
            // <block1>
        } else {
            // <block2>
        }
        // <end>
        
      • 转换为：

            # <start>
            # jump to `END` if the condition is false.
            # <block1>
            jmp END
        ELSE:
            # <block2>
        END:
            # <end>
    • ?: 表达式
      • ?: 表达式除了使用 if-else 实现，也可以使用条件移动指令：
        • cmov{e,ne} <S>, <D> 或 cmov{z,nz} <S>, <D>
        • cmov{s,ns} <S>, <D>
        • cmov{a,ae,b,be} <S> <D> 或 cmovn{be,b,ae,a} <S> <D>
        • cmov{g,ge,l,le} <S> <D> 或 cmovn{le,l,ge,g} <S> <D>
      • 给定 C 语言结构：

        // <start>
        var = /* <cond> */ ? val1 : val2;
        // <end>
        
      • 转换为：

            # <start>
            # calculate `val1` and assign it to `var`
            # calculate `val2` and assign it to `val2`
            # move `val2` to `var` if the `<cond>` is true
            # <end>
    • do-while
      • 给定 C 语言结构：

        // <start>
        do {
            // <body>
        } while (/* cond */);
        // <end>
        
      • 转换为：

            # <start>
        LOOP:
            # <body>
            # jump to `LOOP` if the `<cond>` is true
    • while
      • 给定 C 语言结构：

        // <start>
        while (/* <cond> */) {
            // <body>
        }
        // <end>
        
      • 转换为：

            # <start>
            jmp COND
        LOOP:
            # <body>
        COND:
            # jump to `LOOP` if the `<cond>` is true
            # <end>
      • 或者转换为（提前判断条件+do-while）：

            # <start>
            # jump to `END` if the `<cond>` is false
        LOOP:
            # <body>
            # jump to `LOOP` if the `<cond>` is true
        END:
            # <end>
    • for
      • 给定 C 语言结构：

        // <start>
        for (/* <init> */; /* <cond> */; /* <next> */) {
            // <body>
        }
        // <end>
        
      • 转换为：

            # <start>
            # <init>
            jmp COND
        LOOP:
            # <body>
            # <next>
        COND:
            # jump to `LOOP` if the `<cond>` is true
            # <end>
    • switch
      • switch 使用跳转表实现。
      • 每个 case 的起始地址放到一个跳转表数组 中。
      • 对于被比较数，计算 case 的下标 i，通过 jmp *(<jump-table>, i, <ptr-size>) 动态选择。
• 过程调用
  • 栈操作指令
    • push? <S>：把 <S> 的值添加到栈顶。
    • pop? <D>：弹出栈顶并把值赋值给 <D>。
  • 过程调用 ABI
    • 栈底位于高地址，栈顶位于低地址。
    • 每次函数调用产生一个栈帧，返回时栈帧销毁。
      • 栈帧中，从栈低到栈顶依次保存保护寄存器、局部变量、额外函数参数、函数返回地址（有调用时）。
      • 函数参数优先保存在寄存器 %rdi、%rsi、%rdx、%rcx、%r8、%r9，其次保存在栈上。
    • 寄存器保护规则：
      • 调用者保护寄存器：%rax、%rcx、%rdx、%rdi、%rsi、%r8~%r11，被调函数参数和返回值包括在其中。
      • 被调用者保护寄存器：%rbx、%rbp、%rsp、%r12~%r15，需要在返回时恢复这些寄存器为调用前的值。
  • 过程调用指令
    • call <L>：调用函数 <L>，<L> 是函数起始代码地址的标号，会自动填写返回地址并修改 %rsp。
    • call *<D>：* 是固定格式，目标地址从 <D> 中读取。
    • retq：读取返回地址，跳转会调用者函数，自动修改 %rsp。
• 复合数据结构
  • 数组
    • 一维数组
      • 通过 (<array>, <index>, <size>) 来获取数组元素的地址。
      • 数组的对齐按照单个元素的对齐要求对齐。
    • 多维数组
      • 连续储存的多维数组通过把多维下标转换为一维下标来访问元素：
        • C 语言中多维数组是行优先储存。
        • type array[m][n] 中访问 array[i][j]，下标换算为 i * n + j，地址还要注意乘元素大小。
        • 二维数组访问至少需要两个指令——计算地址和真正访问。
      • 链式储存的多维数组先访问子数组的地址再访问子数组的元素。
  • 结构体
    • C 语言结构体中，成员的底层顺序按照定义的顺序排列，不会被重排。
    • 结构体的对齐与最大的成员的对齐相同，各个成员按照自身对齐要求对齐，中间插入空白填充。
      • 结构体整体的大小是计入填充的。
      • 结构体成员的大小是数据类型的大小，占用空间是计入为此成员加入的填充的。
  • 联合体
    • C 语言联合体大小有最大的变体决定，对齐与最大的对齐相同。