Ch1 编译原理 ARM架构

Architecture Taster

Posted by R1NG on October 27, 2020 Viewed Times

Ch1 ARM架构

Motivation:

  1. 了解不同的指令形式
  2. 了解 ARM 处理器
  3. 介绍一些简单的指令, 并使用简单的指令编写程序
  4. 了解程序在计算机中的存储方式
  5. 了解计算机是如何知晓下一步应执行什么指令的
  6. 了解计算机 “作出分支选择” 的原理

1. 计算模型: Von Neumann 模型

Von Neumann 计算机模型清晰地将计算机定义为一台 数据处理机: 它将能够接受输入数据, 处理并输出相应的结果.

基于 Von Neumann 计算机模型涉及的计算机分为四个子系统: 存储器, 算术逻辑单元, 控制单元和输入/输出单元:

  • 存储器被计算机用于存储数据和程序.
  • 算术逻辑单元是用于执行数值运算和逻辑运算的模块.
  • 控制单元是对存储器, 算术逻辑单元, 输入/输出等子系统执行控制操作的单元.
  • 输入子系统负责从计算机外部接受输入的数据和程序, 输出子系统负责将计算机的处理结果输出到计算机外部.


2. 指令集

不同的处理器一般具有不同的指令集, 如常用于桌面计算机的 X86, 用于移动端处理器的 ARMRISC, 以及 IBM 开发的处理器所采用的 PowerPC.

在本课程中, 我们所学习的指令集为 ARM ISA(32bit) .它为 32 位架构, 相对简单, 并广泛应用在移动设备中.


3. 三地址结构

为了便于理解计算机执行指令的过程, 我们从对一种架构: “三地址结构” 的介绍开始.
在这种架构下, 每一个指令可以从最多两个内存地址中取值 (source operand) 并将其发送至处理器, 根据指令内容对这两个输入执行某种运算, 并将运算结果存入第三个目标内存地址中 (destination operand) .

注: 任何一条指令都包含 操作 (operation) 和运算数 (operands).

例: 执行两数之间的加法

20201105185759

例: 执行三个数之间的加法 (未优化寄存器使用)

20201105185833

3.1 内存瓶颈的成因

处理器的运行速度远快于内存的存取速度, 若要提升内存的存取速度, 则需要付出较高的成本. 并且, 绝大多数的内存技术不允许内存在同一时间内进行多个读写操作. 因此, 在这一情形下, 内存的读取速度就成为了制约计算机运行速度的瓶颈.

还是以 “三地址结构” 为例. 每一个三地址结构指令都需要三个内存周期, 它们分别是对两个输入运算数的分别读取, 和对输出运算数的写入. 在实际情况中, 由于指令内容本身也需要被读取, 因此执行一条三地址结构指令至少需要四个内存周期.

由上文可知, 三地址结构进行三数字的加法运算, 单单考虑对于操作数的内存读写就需要六个内存周期. 那么, 又有什么样的办法可以解决这一问题, 缩短程序的执行时间呢?

3.2 内存瓶颈的解决: 寄存器

寄存器是位于处理器中, 用于存放临时数据的, 高速独立的存储单元. 通过使用寄存器, 辅以足够简单的指令集, 我们可以利用寄存器高效的存取性能和超高的存取速度尽可能地减少内存使用, 从而避免冗长的内存周期拖慢程序的运行时间. ARM 架构的处理器内建了 16 个寄存器.

注: 有一些架构和指令 (如 X86) 允许使用指令直接访问内存; 而本课程中所学习的 ARM 指令集只能通过寄存器间接访问内存. 也就是说, 指令的输入运算数只能从寄存器中取得, 输出运算数也只能存入寄存器中. 要将内容从寄存器中存储入内存, 或要从内存中读取内容到寄存器中, 就需要额外的指令.

例: ARM 指令集执行三个数的加法

20201105185910


4. ARM 指令集

ARM 架构中有大量指令集. 而根据 Von Neumann Model, 我们只需要三类指令集:

  1. 内存操作指令: 一类负责在内存和寄存器间转移数据的指令.
  2. 运算操作指令: 一类对寄存器中存储的数据执行运算的指令.
  3. 控制操作指令: 一类进行条件判断和决策或进行循环的指令.

例: 一条简单的 ARM 汇编指令

1
ADD R3, R1, R2  ;store the value of operation (R_1 + R_2) to R_3

ARM 汇编指令包含:

  1. 助记符: 明确所执行的操作指令
  2. 目标地址: 在上述指令中为 r3.
  3. 源地址: 在上述指令中为 r1r2.

4.1 ARM 内存操作指令

内存操作指令负责在内存和寄存器间执行数据转移.

例:

1
2
3
LDR  R1, a      ;load a to R1
STR  R5, sum    ;store R5 into sum
;a, sum are ALIASES for the ADDRESS of MEMORY locations. 

我们将在后续的学习中了解更多的内存操作指令.

4.2 ARM 运算操作指令

运算操作指令负责对寄存器中存储的数据执行运算.

例:

1
2
3
4
ADD R3, R1, R2      ; R3 = R1 + R2
SUB R3, R3, R2      ; R3 = R3 - R2
MUL R3, R3, R2      ; R3 = R3 * R2
MOV R3, R4          ; R3 = R4

我们将在后续的学习中了解更多的运算操作指令.

4.3 存储指令

根据上文的讨论可知, 一条计算机程序就是一个可以执行下列操作的指令列:

  1. 从不同的位置上转移数据
  2. 对数据进行某些运算
  3. 进行决策, 如分支, 循环等.

ARM 架构中, 程序和数据一样, 存储为 32位, 被一个 32 位的二进制整数所表示. (实际上常常也表为一个 8位 的十六进制整数), 被称为 编译目标代码. 编译目标代码经过汇编器的转换后即可化为可读的 “助记符指令”.

4.4 控制流

  • 程序计数器 (Program Counter)
    计算机需要知道在执行完本次执行的程序后, 下一条该执行的指令是什么. 为了达成这一目的, 引入了 程序计数器 的概念.

    程序计数器是一个保存着下一条待执行指令的内存地址的通用寄存器. 在 ARM 架构中, 第 16 个寄存器 R15 被当作程序计数器.

  • 读取-执行周期 (Fetch-Execute Cycle)
    程序计数器存储着程序运行时第一条待执行的指令. 在读取-执行周期中, 以下步骤周而复始地进行:

    1. 读取: 从程序计数器指向的内存地址中存取指令, 并令程序计数器指向存取的指令后面的, 下一条待执行的指令
    2. 执行: 执行所存取的指令.

    对于 ARM 架构:

    1. 执行程序前, 程序计数器被初始化为指向内存地址 00000000.
    2. 每条指令长为 32 位, 4 字节.
    3. 每个内存地址只存取一个字节, 每条指令占用四个存储单元 (Memory Location).
    4. 在每次读取-执行周期内, 结束 “读取” 操作后, 程序计数器的值都增加 4.

4.5 分支

到目前为止, 我们已经介绍了 Von Neumann结构, 寄存器和 ARM 架构, 并了解了 ARM 架构是如何利用程序计数器依次序执行指令的. 下面, 我们将通过学习 分支指令 (Branch Instruction), 了解 ARM 架构是如何实现程序分支执行的.

  • 分支

    ARM 架构提供了多种分支指令. 其中最简单的指令自然是 always 分支 (实际上等同于没有分支): 每一条指令被读取后, 程序计数器都增加四个位. 一般地, 分支指令形如:

    1
    
      B somewhere     ;means: branch to alias "somewhere"
    

    注:

    1. "somewhere" 是一个标签, 实际上指代某个存储单元的地址的别名.
    2. “somewhere” 应该指向某一列指令的起始, 否则执行结果将会导致崩溃.
  • 如何分支

    以下列代码为例:

    1
    2
    3
    
      [1]B somewhere        ;Jump from here
    
      [2]somewhere ADD R0, R1, R2    ;Jump to here 
    

    [1] 处的指令被执行时, 程序计数器内所存储的 内存地址 被更新为 somewhere 的内存地址. (记住: 程序计数器能且只能存储内存地址!)

  • 条件分支 分支的类型分为 条件分支 (Conditional Branching)非条件分支 (Unconditional Branching). 相比非条件分支, 条件分支的差异在于, 他的执行与否取决于是否满足某些条件.

    一个标准的条件分支决策包含两个部分:

    1. 对条件进行评估和判断
    2. 基于判断条件所得出的值, 决定是否执行分支

    我们可以使用如下的命令定义条件分支的条件:

    1
    2
    3
    4
    5
    6
    
      CMP: operand1 - operand2, result not written to a register
      CMN: operand1 + operand2, result not written to a register
      TST: operand1 AND operand2, result not written to a register
      TEQ: operand1 EOR operand2, result not written to a register
    
      ;SYNTAX: <Operation>{<cond>} Rn, operand2
    

    举例而言, 指令 CMP 即可用于条件的评估和判断:

    1
    
      CMP Op1, Op2    ;Compares its two operands
    

    处理器将记录 (Op1 - Op2) 的值孰正孰负, 或为零.

    BLT 指令则使用 CMP 指令的返回值决定是否执行分支. 对于该指令, 若 Op1 - Op2 is negative, 则分支将会被执行. BLT 指令和 B 指令类似, 都会在相应条件被满足时更新程序计数器的值.

    B 指令一样, 分支的操作值也是一列新指令的起始端的内存地址, 一般都被一个标签所指代.

    下面是一些常用于条件分支的判断条件:

    20201105185947

    除了内建的 $16$ 个寄存器, ARM 架构还额外定义了一个大小为 1bit状态位 (Status Flags). 当前处理器状态寄存器 (Current Processor Status Register) 是一个记录当前处理器状态的寄存器. 它包含了一些状态位:

    20201105190018

    我们目前只关注状态位的以下四种状态:

    1. Negative: 指示条件判断结果是否为负
    2. Zero: 指示条件判断结果是否为零
    3. Carry: 之前执行的加减法是否产生了一个进位
    4. oVerflow: 之前执行的加减法是否发生溢出

    状态位可随着条件分支判断命令的执行所更改. 当我们在任何数据操作指令后加上助记符 “S” 后, 状态位也会被改变:

    1
    2
    3
    
      ;Ex:
      SUBS R0, R1, R2;
      ;Behave like CMP, but keep the result in R0 as well as will set flags
    

    状态位有以下几种使用方法:

    1. 用于储存条件判断的结果, 并将结果作为后续指令的输入; 这样可以使分支以及其他指令条件化.
    2. 可以无需分支地写出简练的代码:
      1
      2
      
       SUBS R0, R1, R2;   ;subtract R0 = R1 - R2, set flags
       ADDEQ R3, R3, #1;  ;add 1 to a counter R3
      
    3. 在下一条以助记符 “S” 结尾的指令执行之前, 条件位保持不变.
    4. 在设置条件位后, 我们可以经过很长的一段代码后才执行基于条件位指示的条件语句.
    5. 可利用条件位作为进位, 从而使用 32 位处理器执行 64 位运算:
      1
      2
      3
      
       ;64-bit add using register pairs: R1:R0 := R1:R0 + R3:R2
       ADDS R0, R0, R2    ;Add LS words & set flags
       ADC R1, R1, R3     ;Add MS words with CARRY