文章目录

• 嵌入式程序组件
• • 状态机
  • 循环缓冲区和面向流的程序设计
  • • FIR滤波器
    • • C编写的数字滤波器
    • II型IIR 滤波器
  • 队列和生产者 / 消费者系统
• 程序的模型
• • 数据流图（DFG，Data flow graph）
  • 控制/数据流图(CDFG)
• 汇编、连接和装载
• • 汇编程序
  • 连接
  • 装载
  • 目标代码设计
• 编译技术
• • 编译一个算术表达式
  • 为一个条件结构创建代码
  • 数据结构
  • 编译器优化
  • • 表达式简化
    • 过程内联
    • 循环的转换
    • • 循环展开
    • 循环合并（loop fusion）
    • 循环分块（loop tiling）
  • 死代码删除
  • 寄存器的分配
  • 操作调度（operator scheduling）
  • 预约表（reservation table）
  • 软件流水（software pipelining）
  • 模板匹配（template matching）

嵌入式程序组件

考虑三种广泛应用于嵌入式软件的结构或组件的代码，这三种结构或组件分别是：状态机，循环缓冲器，队列。

状态机

• 状态机通过状态来表示系统的内部特性，状态的变化是基于输入的变化。
• 应用:
  • 面向控制的代码;
  • 响应式系统;
  • 非周期性采样作为输入

C语言实现的一个软件状态机——座位安全带控制器

• 需求：有人坐到座椅上，在规定时间内若没有系好安全带，就启动蜂鸣器。
• 输入：
  • seat: 是否有人坐；
  • belt: 是否系安全带；
  • timer: 定长计时器；
• 输出：蜂鸣器。
• 状态：state: 机器当前状态

#define IDLE 0  
#define SEATED 1  
#define BELTED 2  
#define BUZZER 3   switch (state) {     case IDLE:      if (seat) { state = SEATED;  timer_on = TRUE; }     break;  
    case SEATED:      if (belt)  state = BELTED;     else if (timer)  state = BUZZER;     break;  
    case BELTED:      if (!seat)  state = IDLE;     else if (!belt)  state = SEATED;     break;  
    case BUZZER:      if (belt)  state = BELTED;     else if (!seat)  state = IDLE;     break;   }   ```

循环缓冲区和面向流的程序设计

• 数据流形式表示按规律到达并需要立即处理的数据
  • FIR滤波器是一个典型的面向流处理的例子：对每一个采样，滤波器必须有一个输出，这个输出依赖于之前到达的n个输入。
    
• 循环缓冲区(circular buffer) 是便于我们处理流数据的一种数据结构。
  
• 使用一个固定大小的缓冲区来保存当前数据，按时序移动缓冲区的头部，缓冲区的指针指向下一个采样数据被替换的位置。每添加一个采样就覆盖原先要剔除的数据，当指针移动到缓冲区的末端，则自动回到顶部。
  • use:数据替换位置的前一个位置
  • Input：输入数据指针
    

C语言实现的循环缓冲区

#define CMAX 6 /* filter order */  
int circ[CMAX]; /* circular buffer */ 
int pos; /* position of current sample */  

• 变量pos保存当前采样位置，向缓冲区添加值时，变量位置移动

 //向缓冲区中添加新值 
 void circ_update(int xnew) 
 {  
 /* compute the new head value with wrap around; the pos pointer  moves from 0 to CMAX-1 */ 
  pos = ((pos == CMAX-1) ? 0 : (pos+1));  /* insert the new value at the
  new head */  circ[pos] = xnew;  
 } 

• pos指向数组末尾时返回0。

//初始化函数 
void circ_init() {  
  int i;  
  for (i=0; i<CMAX; i++) /* set values to 0 */
  circ[i] = 0; 
  pos=CMAX-1; /* startat tail so first element will be at 0 */  
  } 

• 为了使第一个数据元素进入circ[0]，设置pos指到数组末尾，再添加第一个元素前，它的值会变为0。

int circ_get(int i) 
{  
  int ii;  /* compute the buffer position */
  ii = (pos - i) % CMAX;  return circ[ii]; /* return the value */  
} 

FIR滤波器

• 表示为 z^-1 的方框代表延迟运算符
  • z符号来源于数字信号处理中的z变换
  • 上标-1都表示操作执行一个采样周期的时间延迟。
• b₁ 意味着延迟运算符的输出要乘以b₁
• 生成FIR滤波器输出的代码为：

for(i=0,y=0.0;i<N;i++)
  y+=x[i]*b[i];

C编写的数字滤波器

• 延迟元素在垂直方向运行，在顶端保存最近采样的输入样本，在低端保持最早的输入样本。
  
• x值随时间变化
  • 用循环缓冲区保存x值
  • 缓冲区头部从高值向低值移动
• b值不变：使用标准数组来保存

//修改后的update函数，按照既定顺序将新值放入缓冲区
void circ_update(int xnew) { 
/* add the new sample and push off the oldest one */ 
/* compute the new head value with wraparound; the 
pos pointer moves from CMAX-1 down to 0 */ 
pos = ((pos == 0) ? CMAX-1 : (pos-1)); 
/* insert the new value at the new head */ 
circ[pos] = xnew; 
}

• 改变 circ_init() 函数初始化 pos = 0 。circ_get() 函数不需要改变
• FIR滤波器函数代码如下：

int fir(int xnew) { 
/* given a new sample value, update the queue and 
compute the filter output */ 
  int i; 
  int result; /* holds the filter output */ 
  circ_update(xnew); /* put the new value in */ 
  for (i=0, result=0; i<CMAX; i++)
    result += b[i] * circ_get(i); 
  return result;
}

II型IIR 滤波器

• v表示输入与右边的参数的乘积
• a、b是固定不变的，
  • 标准数组存储。
• 先计算，然后把新输入压入缓冲区

int iir2(int xnew) { 
int i, aside, bside, result; 
//ZMAX-1 ：最陈数据不适用
for (i=0, aside=0; i<ZMAX-1; i++) 
aside += -a[i+1] * circ_get(i); 
for (i=0, bside=0; i<ZMAX-1; i++) 
bside += b[i+1] * circ_get(i); 
result = b[0] * (xnew + aside) + bside; 
circ_update(xnew); 
/* put the new value in */ 
return result; 
}

队列和生产者 / 消费者系统

• 数据在无法预料的时刻到达和离开，或者在某时刻有不同数目的数据到达可以用队列来描述
• 队列常被视为弹性缓冲区
  • 构建队列的方式：链表、数组
  • 具体代码就不用我贴了叭
• 生产者 / 消费者系统
  
  • p1,p2是两个算法处理块
  • 数据从单行缓存区的队列中发送到处理块中
  • 数据q12是p1产生的数据，p2消费的数据

程序的模型

• 源代码不是一种很好的表示形式
  • 源代码多样性：C语言、汇编语言
  • 有很多隐含的信息
• 基本程序模型：控制/数据流图（CDFG）

数据流图（DFG，Data flow graph）

• 数据流图是一个无条件程序模型
• 基本语句块：
  • 无条件代码段
  • 只有一个入口和出口
• 可操作的最大顺序语句序列

• 单赋值形式：一个变量只能在赋值运算符左边出现一次
  • 它允许我们在每一个计算命名地址的代码中标识一个唯一地址
  • 单赋值意味着数据流图是非循环的
• 两类结点：
  • 圆形结点：表示操作
  • 方形结点：表示值

• 数据流图在基本语句块中定义了操作的部分顺序
  • 可以用它来确定对操作顺序重排是否可行
    
  • a+b, c-d; b+d, x*y
  • 可以用任何顺序执行

控制/数据流图(CDFG)

• CDFG：表示控制与数据的图
  • 用数据流表示组件，添加控制部分
• CDFG有两种类型的节点:

  • 判决节点：描述的全部控制类型

    • 描述控制类型
      

  • 数据流节点：一个完整的表示基本语句块的数据流图

    • 封装一个数据流图
    • 在节点中完成写操作
      
• CDFG是一种分层表述形式，可以对一个数据流CDFG进行扩展来展现完整的数据流图

• CDFG例子：选择分支

if (cond1) 
   bb1(); 
else
   bb2();
bb3(); 
switch (test1) { 
   case c1: bb4(); break; 
   case c2: bb5(); break;
   case c3: bb6(); break; 
} 

• CDFG例子：循环

//for循环 
for (i=0; i<N; i++)   
  loop_body();

//while循环 
i=0; 
while (i<N) {   
   loop_body();    
   i++; 
 } 

汇编、连接和装载

• 汇编和链接是编译处理过程的最后一步，它们将一系列指令转换成程序的片段在内存中的映像。
• 装载将程序放入程序中，使得程序能够执行。
• 多模块程序：
  • 程序由多个文件构成，决定指令和操作数地址的最后一步由连接器完成
  • 地址类型：
    • 相对地址：从一个模块的开始编址
    • 绝对地址：按照CPU地址空间编址

汇编程序

• 主要任务:

  • 为符号指令产生二进制代码
  • 把标签变为地址
  • 处理伪操作 (data, etc.)

• 标签让编译器不用担心指令和操作数的位置

  • 标签处理过程：两次扫描
    • 第一次扫描处理决定每个标记的地址，并生成符号表
      
    • 在第二次扫描过程中，用第一次计算的标记值汇编指令，产生二进制指令

• 第一次扫描过程：

  • 在扫描过程中，内存中的当前地址保存在程序位置计数器(PLC)中
    • PLC和PC的区别：PLC不用于程序的执行，只对程序进行一次扫描处理。PC在一个循环中对程序要扫描多次。
  • 如果指令一个标签开始，符号表中添加一个新元素，包括标记名称和标记值。标记值即为PLC当前值。
  • 相对地址的产生
    • 标签值在汇编时可能并不能知道
    • 标签以相对地址的形式保留
    • 对外部标签的跟踪——使用外部标签不能产生完全的二进制指令
  • 伪指令：不能产生指令
    • ORG 设置程序位置
    • EQU 将标记添加到符号表而不占用程序的内存空间
      • 例如以下代码：

               ADD r0,r1,r2
           FOO EQU 5
           BAZ SUB r3,r4,#FOO
        

      • EQU伪操作添加一个名为FOO的值为5的标记到符号表中
      • EQU没有使PLC向前移动，因此BAZ标记的值不变
      • EQU能够用于定义符号化的值
    • Data statements 定义数据块

示例：创建一个符号表
使用如下简单的ARM汇编代码

       ORG 100
label1 ADR r4, c
       LDR r0,[r4]
label2 ADR r4,d
       LDR r1,[r4]
label3 SUB r0,r0,r1

• 一开始的ORG语句告诉我们程序开始地址
  
  
• 处理下一条语句只需要移动PLC，由于上一条语句是一个位操作没有内存值，PLC的值不变
  
  
• 由于ARM指令是4个字长，所以PLC将每次增加4个单位
  
  

连接

• 将几个目标模块连接成一个可执行模块。连接器允许通过几个程序片段来组成一个程序
• 任务:
  • 形成模块顺序
  • 解决模块之间的标签
• 外部引用和入口点
  • 入口点：定义标签的位置
  • 外部引用：使用标签的位置
    
  • 装载器的主要工作是根据入口点解析外部引用。

• 动态连接：
  • 在运行程序时动态连接模块
    • 所有执行程序共享一个库拷贝;
    • 程序运行之前运行短的链接，把代码中用到的函数找到，并链接到程序中；
    • 允许程序用新版本的库.
  • 问题：引起程序启动的延迟

装载

• 代码块必须放到内存中的绝对位置
  • 首先，它要确定每个目标文件的开始地址。目标文件的装载次序由用户给定。给定了每个文件放入内存的次序和每个目标文件的长度，就可以计算出每个文件的开始地址
  • 加载映射（Load map） 文件或者是连接器标记控制了模块的顺序
  • 装载器将来自全部目标文件的符号表合并成一个大的符号表，然后编辑目标文件，把相对地址转成绝对地址。
    

目标代码设计

• 嵌入式程序设计有些问题需要开发者解决
  • I/O设备的中断向量表应放在特定位置；
  • 设置内存管理表
  • 全局变量必须放在所有用户都可访问的位置
• 为这些位置命名符号名称
• 连接器根据硬件平台给定绝对地址，修改程序的引用
• 解决可重入问题，许多程序应被设计为可重入的
  • 函数执行中被打断，打断者又调用该函数，应不改变打断的函数的返回值
• 一个函数在执行过程中被打断，并且打断者又一次调用此函数，这种打断和重复执行不改变这这些函数调用的返回结果，则这个函数就是可重入的。
• 如果程序改变了全局变量的值，发生递归时它可能会给出不同的答案

//不可重入的
int foo=1;
Int task( )
{
  foo=foo+1;
  return foo;
}

//可重入的
int task(int foo )
{
  foo=foo+1;
  return foo;
}

• 若一个程序置于内存不同位置据可执行，那么称之为可重定位的

编译技术

• 编译策略：编译=翻译+优化
• 编译决定了代码的质量
  • 对CPU资源的应用
  • 内存的调度
  • 代码的大小
• APCS（ARM过程调用标准）
  • r0-r3传递参数给过程，额外的参数放到栈中
  • r0保持返回的值
  • r4-r7保留寄存器的值
  • r11是帧指针fp，指向栈底；r13是栈指针sp
  • r10是指示栈界限的寄存器，以判断栈是否溢出。

// 编译调用过程的代码：y=p1(a,b,c,d,x)

ldr r3, [fp, #-32] ; get x, the fifth parameter 
str r3, [sp, #0] ; put into p1()’s stack frame 
ldr r0, [fp, #-16] ; put a into r0 
ldr r1, [fp, #-20] ; put b into r1 
ldr r2, [fp, #-24] ; put c into r2 
ldr r3, [fp, #-28] ; put d into r3 
bl p1 ; call p1() 
mov r3, r0 ; move return value into r3 
str r3, [fp, #-36] ; store into y in stack frame

• 语句的翻译和优化:
  • 源代码翻译成中间格式，如CDFG；
  • CDFG被转换和优化；
  • CDFG在优化的基础上被翻译成指令；
  • 指令被更进一步优化。

编译一个算术表达式

• 对于ARM：
  • 寄存器选择
  • 变量放入寄存器
  • 存放中间结果的寄存器

a × b + 5 × ( c − d ) a\times b + 5\times (c-d) a×b+5×(c−d)

• 遍历节点即可得到ARM代码：

; operator 1 (*)
ADR r4,a
LDR r1,[r4]
ADR r4,b
LDR r2,[r4]
MUL r3,r1,r2
; operator 2 (-)
ADR r4,c
LDR r1,[r4]
ADR r4,d
LDR r5,[r4]
SUB r6,r4,r5
; operator 3 (*)
MUL r7,r6,#5
; operator 4 (+)
ADD r8,r7,r3

• 可以优化用过不会再用的寄存器，对其进行重用。ARM gcc编译器生成的代码如下：

ldr r2, [fp, #-16] 
ldr r3, [fp, #-20] 
mul r1, r3, r2 ; multiply 
ldr r2, [fp, #-24] 
ldr r3, [fp, #-28] 
rsb r2, r3, r2 ; subtract 
mov r3, r2 
mov r3, r3, asl #2 
add r3, r3, r2 ; add 
add r3, r1, r3 ; add 
str r3, [fp, #-32] 
; assign 

为一个条件结构创建代码

if (a+b > 0)
  x = 5;
else
  x = 7;

• 以上代码的CDFG如下：
  
• 可以通过遍历CDFG创建控制流代码，一个有序的CDFG遍历如下：
  
• 通过1-2-3遍历可得到如下ARM代码

   ADR r5,a
   LDR r1,[r5]
   ADR r5,b
   LDR r2,[r5]
   ADDS r3,r1,r2
   BLE l3 ;<=
   LDR r3,#5
   ADR r5,x
   STR r3,[r5]
   B stmtent
l3 LDR r3,#7
   ADR r5,x
   STR r3,[r5]
stmtend ...

• 1-2和3-4边不需要分支和标记，因为他们是直线型代码。
• 编译器生成的控制代码如下：

ldr r2, [fp, #-16] 
ldr r3, [fp, #-20] 
add r3, r2, r3 
cmp r3, #0 
；test the branch condition 
ble .L3 
; branch to false block if <=
mov r3, #5 ; true block 
str r3, [fp, #-32] 
b .L4
; go to end of if statement 
.L3: 
; false block 
mov r3, #7 
str r3, [fp, #-32] 
.L4: 

数据结构

• 不同的数据结构类型有不同的数据结构布局
• 编译器要将数据结构的索引翻译成对原始内存的索引。一些数据结构的地址计算在编译时进行，其它的则在运行时进行
• 数组下标可变，因此数组元素的地址一般要在运行时计算

• 考虑一维数组 a[i] ，可以创建一个指向数组头部的指针 aptr ，那么对于 a[i] 的读取可以写为*(aptr+i)
• 二维数组一般采用行优先的排列形式，要求更复杂的寻址。如果数组 a[ ] 的大小时N * M ，那么我们可以将二维数组的访问转化为对一维数组的访问。即 a[i,j] 变成 a[i*M+j] ，其中 j 的最大值为 M-1

• 结构体中的每个数据域都是静态偏移

struct {
int field1;
char field2;
} mystruct;

struct mystruct a, *aptr = &a;

编译器优化

表达式简化

• 常数求解
  • 8+1=9
• 算术表达式
  • ab+ac=a*(a+b)
• 强度化简
  • a*2=a<<1

过程内联

• 删除内联函数

// old
int foo(a,b,c) { return a + b - c;}
z = foo(w,x,y);

//new
z = w + x - y;

循环的转换

• 目的：
  • 减少变量迭代和循环条件测试次数，减少循环的开销
  • 为流水增加机会
  • 提高内存系统的性能

循环展开

• 减少循环开销，增强优化的可能性

for (i=0; i<4; i++)
  a[i] = b[i] * c[i];

• 若N=4，则可展开为：

a[0] = b[0] * c[0];
a[1] = b[1] * c[1];
a[2] = b[2] * c[2];
a[3] = b[3] * c[3];

• 不将循环完全展开，只展开两次：

for (i=0; i<2; i++) {
  a[i*2] = b[i*2] * c[i*2];
  a[i*2+1] = b[i*2+1] * c[i*2+1];
}

• 此时循环体两行内的所有操作都是独立的，在编译的后期可以创建在CPU流水线上有效执行的代码。

循环合并（loop fusion）

• 将两个或多个循环合并成一个循环
  • 循环次数必须相同
  • 循环体之间不能有在一起执行时可能会冲突的依赖性。

// old
for (i=0; i<N; i++) a[i] = b[i] * 5;
for (j=0; j<N; j++) w[j] = c[j] * d[j];

//new
for (i=0; i<N; i++) {
  a[i] = b[i] * 5; w[i] = c[i] * d[i];
}

• 循环分解（loop distribution） 与循环合并相反，它把一个循环分解为多个循环。

循环分块（loop tiling）

• 将一个循环拆分成一系列嵌套的循环。
  
• 循环分块改变了数组元素访问次序，可以更好地控制cache的行为。
• 数据填充（array padding） 向循环中添加填充数据以改变数据在高速缓存中的布局。
  • 在循环执行过程中可以减少高速缓存冲突的次数

死代码删除

• 死代码 就是永远都不会被执行的代码

#define DEBUG 0
if (DEBUG) dbg(p1);

• 死代码可以通过可达性分析（寻找可到达的其他语句或指令）来确定。

寄存器的分配

• 目标：
  • 选择变量（包括声明的和临时变量）在寄存器上的分配以减少所需的寄存器数
  • 确定变量在寄存器中的时间
• 基本情况
  • 生命周期图
  • 寄存器数目

w = a + b;
x = c + w;
y = c + d;

• 可以通过画一个冲突图（conflict graph） 并解决一个着色问题来解决寄存器分配问题。
  
• 不同的装载、存储和算术操作次序可能在流水线上导致不同的执行时间。

操作调度（operator scheduling）

• 操作调度目的是改善寄存器分配
• 考虑如下代码：

w=a+b;
x=c+d;
y=x+e;
z=a-b;

• 它的生命周期图如下：
  
• 重新排序后所需寄存器的数目减少到三个：

w=a+b; 
z=a-b; 
x=c+d; 
y=x+e;

• 指令的调度
  • 非流水线机器不需要指令的调度：
    • 以任何满足指令依赖行的指令顺序执行
  • 在流水线机器里，一条指令的执行时间与就近指令有关（包括指令的操作数、操作码）

预约表（reservation table）

• 用于追踪CPU的资源使用
  
• 行：指令执行时间
• 列：被调度的资源
• 调度可使用多种不同的算法
  • 依赖于资源和指令的类型

软件流水（software pipelining）

• 若指令比正常的时间周期多的时间完成，出
  现延迟而降低性能。
• 软件流水是一种对指令重新排序的技术
  • 向循环体内添加下一次迭代的指令
  • 选择实现每一条操作的指令
  • 通过循环迭代减少流水线中的延迟

模板匹配（template matching）

• 是一种有用的代码创建技术

• 有几种方式来完成一个操作或一系列操作
• 可用图表示操作，图上匹配可能的指令