Pengju 嵌入式系统设计与应用第五章程序设计与分析 (2) 西安交通大学电信学院任鹏举

Size: px

Start display at page:

Download "Pengju 嵌入式系统设计与应用第五章程序设计与分析 (2) 西安交通大学电信学院任鹏举"

胡窕蒲
5 years ago
Views:

1 嵌入式系统设计与应用第五章程序设计与分析 (2) 西安交通大学电信学院任鹏举

2 4 基本编译技术编译 = 翻译 + 优化翻译 : 将高级语言程序翻译成低级形式的指令正确的理解程序 ( 功能 ) 优化 : 与翻译过程中所使用的语句间相互独立的简单方法相比, 优化可以生成更高效指令的代码高效的执行程序 ( 性能 ) 编译决定着代码质量 : 占用 CPU 资源存储器访问调度代码大小 2

3 基本编译过程高级语言代码语法分析符号表生成和语义分析独立于机器的优化指令级优化和代码生成汇编代码 3

4 语句翻译与优化源代码被翻译成类似于 CDFG 的中间形式 CDFG 经过变换与优化通过优化决策,CDFG 被翻译成指令指令被进一步优化 4

5 语句的翻译与优化算术表达式 ; 控制结构 - 条件语句 ; 过程链接 ; 数据结构 ; 5

6 算术表达式 (1) a*b + 5*(c-d) expression a b c d * - 5 x w * + z y DFG 6

7 算术表达式 (2) 1 a b c d * 2-5 x w 3 * 4 + z y DFG ADR r9,a MOV r1,[r9] ADR r9,b MOV r2,[r9] MUL r3,r1,r2 ADR r9,c MOV r4,[r9] ADR r9,d MOV r5,[r9] SUB r6,r4,r5 MUL r7,r6,#5 ADD r8,r7,r3 code a/b+c*(d+e)-f^g+log2(h+7i)+sin(10g+k/3) 一个明显的优化方法是重用哪些其值不用再保存的寄存器寄存器分配问题! 7

8 控制结构 - 条件语句 (1) if (a+b > 0) else x = 5; x = 7; F T a+b>0 x=5 x=7 8

9 1 3 控制结构 - 条件语句 (2) a+b>0 x=5 F x=7 4 T 2 ADR r5,a LDR r1,[r5] ADR r5,b LDR r2,[r5] ADD r3,r1,r2 BLE label3 LDR r3,#5 ADR r5,x STR r3,[r5] B stmtend Ture block label3 LDR r3,#7 ADR r5,x STR r3,[r5] stmtend... False block 9

10 控制结构 -While 语句 for (i=0, f=0; i<n; i++) f = f + c[i] * x[i]; i=0 f=0 N i=n Y f = f + c[i] * x[i] i = i

11 过程链接过程定义包括 : 生成处理过程调用与返回的代码传递参数和返回值过程链接机制允许参数和返回值传递, 并保护和恢复修改过的寄存器帧栈的具体构造和数据结构取决于不同的 CPU (Machine dependent) 参数和返回值主要通过栈 (stack) 来传递少量参数也可以通过寄存器来传递 11

12 堆栈回顾对于高级语言程序而言, 堆栈的操作往往对程序员是不可见的, 对于大多数的汇编而言, 需要程序员指定相应堆栈的操作堆栈的具体细节取决于 : 编译器,OS 以及指令集 12

13 过程栈 growth proc1 FP frame pointer 帧指针定义最后一帧的末尾 proc2 5 SP stack pointer 栈指针定义当前帧的末尾 proc1(int a) { proc2(5); } accessed relative to SP 13

14 栈帧对于程序调用的支持 (1) 栈帧 (Stack Frames) 有时也叫做活动记录 (Activation records); 对于每个函数调用, 为函数保留一部分堆栈, 通常称为堆栈帧 (stack frame). A stack frame exists whenever a function has started, but yet to complete. 每当一个函数启动但尚未完成时, 就存在一个栈帧 14

15 栈帧对于程序调用的支持 (2) 栈帧负责子程序调用未返回的信息记录 : 局部变量 (Local variables) 调用函数的返回地址 (Caller s address) 传递参数 (Parameter values) Suppose, inside of body of main(), there is a call to foo(a,b), which needs two arguments. Then, it the main() to take the response to push arguments for foo() onto the stack. We also reserved some space for the return value. The return value is computed by foo(), so it will be filled out once foo() is done. 假设在 main() 体内部有一个对 foo(a,b) 的调用, 它需要两个参数然后,main() 将 foo() 的参数推到堆栈上我们还保留了一些空间作为返回值返回值由 foo() 计算, 所以一旦 foo() 完成, 它就会被填充 15

16 栈帧对于程序调用的支持 (3) 帧栈指针 (Frame points): 方便函数的调用 (args) We've added a new pointer called FP which stands for frame pointer. The FP points to the location where the stack pointer was, just before foo() moved the stack pointer for foo()'s own local variables. 我们添加了一个名为 FP 的新指针, 代表帧指针帧指针指向堆栈指针所在的位置, 就在 foo() 移动 foo() 自己局部变量的堆栈指针之前 we can use the FP to compute the locations in memory for both arguments as well as local variables. Since it doesn't move, the computations for those locations should be some fixed offset from the frame pointer. 我们可以使用帧指针来计算内存中两个参数以及局部变量的位置由于它不移动, 这些位置的计 16 算应该是从帧指针的某个固定的偏移量

17 栈帧对于程序调用的支持 (4) 帧栈指针 (Frame points): 方便函数的返回 (ret val) Once it's time to exit foo(), you just have to set the stack pointer to where the frame pointer is, which effectively pops off foo()'s stack frame. It's quite handy to have a frame pointer. 一旦退出 foo(), 您只需将堆栈指针设置为帧指针所在的位置, 就可以有效地将 foo() 的堆栈框架弹出 Once main() has the return value, it can pop that and the arguments to foo() off the stack. 一旦 main() 获得了返回值, 它可以将返回值和 foo() 的传递参数 17 从堆栈中弹出

18 栈帧的嵌套示例 18

19 ARM 过程链接 ARM 过程调用标准 (ARM Procedure Call Standard,APCS): r0-r3 用于将参数传入过程如果需要的参数超过 4 个, 则将被置于栈中 r0 也用于保存返回值 r4-r7 保存寄存器变量 r11 是帧指针 fp,r13 是栈指针 sp r10 按栈的大小保存地址上限, 用于检测栈的溢出 19

20 ARM 过程链接 ARM 过程调用标准 (ARM Procedure Call Standard,APCS) 专用寄存器 Dedicated registers 寄存器变量 callee-saved register variables 参数传递 caller-saved argument variables 20

21 Stack Backtrace (FP based) MOV ip, sp ; save current sp, ready to save as old sp; STMFD sp!, {a1-a4, v1-v5, sb, fp, ip, lr, pc}; SUB fp, ip, #4 SUB sp,sp,#16 use the frame pointer to compute the locations in memory for both arguments as well as local variables. Since it doesn't move, the computations for those locations should be some fixed offset from the frame pointer. 使用帧指针来计算内存中的位置以及局部变量由于它不移动, 这些位置的计算应该是从帧指针的某个固定的偏移量 21

22 C 的过程链接 int p1 (int a, int b, int c, int d, int e) {return a+e;} mov ip, sp stmfd sp!, {fp, ip, lr, pc} sub fp, ip, #4 sub sp, sp, #16 str r0, [fp, #-16] str r1, [fp, #-20] str r2, [fp, #-24] str r3, [fp, #-28] ldr r2, [fp, #-16] ldr r3, [fp, #4] add r3, r2, r3 mov r0, r3 ldmea fp, {fp, sp, pc} y = p1 (a,b,c,d,x); ldr r3, [fp, #-32] ; get e 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 22

23 C 的过程链接 Caller 调用者 Callee 被调用者传递 N 个参数 r0,r1,r2,r3 做参数传递 If N>4: 多余传递参数压入堆栈获取 Y 个返回值返回值出栈保护相关指针将 fp, ip, lr, pc 入栈 ; 更新 sp->ip->fp 使用 M 个寄存器 1: 分配栈帧空间 (sp-4*m) 2: 将 M 个寄存器数值入栈 ( 保护现场 ) 实际使用 X 个传递参数使用 r0~r3; 如果有必要从堆栈中取值产生 Y 个返回值返回值压栈或使用 r0 传递恢复相关指针将 fp, ip, lr, pc 出栈 23

24 Review: 算术表达式 a b c d 1 * 2-5 x w 3 * 4 + z DFG y ADR r9,a MOV r1,[r9] ADR r9,b MOV r2,[r9] MUL r3,r1,r2 ADR r9,c MOV r4,[r9] ADR r9,d MOV r5,[r9] SUB r6,r4,r5 MUL r7,r6,#5 ADD r8,r7,r3 code X = a*b + 5*(c-d) Function X(a,b,c,d) 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 24

25 Review: 条件语句 a+b>0 x=5 x=7 label3 stmtend... ADR r5,a LDR r1,[r5] ADR r5,b LDR r2,[r5] ADD r3,r1,r2 BLE label3 LDR r3,#5 ADR r5,x STR r3,[r5] B stmtend LDR r3,#7 ADR r5,x STR r3,[r5] Function fun1(a,b); 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: 25

26 数据结构编译器需要将数据结构的索引翻译成对原始内存的索引地址计算 : 有些计算在编译过程中完成, 有些在运行时完成一维数组二维数组结构体 26

27 一维数组一维数组 a[i] ( 每个元素为 32bit) 第 0 个元素存储数组的第一个元素 aptr a[0] a[1] a[2] = *(aptr + 1) If 数组中每个元素为 64bits ( 双精度的浮点型 ), 如何索引? 27

28 二维数组二维数组 a[i,j]:i 代表行,j 代表列行优先 vs. 列优先数组大小 N M N... a[0,0] a[0,1]... a[1,0] a[1,1] M = a[i*m+j] 28

29 结构体结构体由一个连续的存储块来实现对结构体内的字段的访问可以通过结构体基地址 + 偏移量 ( 静态 ) 来访 struct { int field1; char field2; } mystruct; aptr 1 bytes field1 field2 4 bytes *(aptr+4) struct mystruct a, *aptr = &a; 29

30 5 程序优化表达式简化无效代码的清除过程内嵌循环变换寄存器分配调度指令选择 30

31 表达式简化 (Expression simplificaction) 表达式简化是对独立于机器的变换很有效利用代数法则 : a*b + a*c = a*(b+c) 分配律使 3 操作简化成 2 操作常量叠算 (constants folding): 8+1 = 9 for (i=0; i<8+1; i++) 强度化简 : a*2 = a<<1 for (i=0; i<nops+1; i++) 31

32 无效代码清除 (Dead code elimination) 无效代码 : #define DEBUG 0 if (DEBUG) dbg(p1); 0 0 可以通过控制流分析常量叠算来消除 1 dbg(p1); 有些无效代码是编译器引入的 32

33 过程内嵌 (procedure inlining) 过程内嵌属于独立于机器的变换, 可以去除过程链接造成的耗费 int foo(a,b,c) { return a + b - c;} z = foo(w,x,y); z = w + x + y; 是否使用过程内嵌需要评估, 不一定有益 : 函数多份拷贝可能造成 cache 冲突, 减慢指令的存取速度增加代码量, 增加存储器开销 33

34 循环变换 (Loop transformations) 循环虽然在源代码中描述的很紧凑, 但通常占用大量的计算时间有很多优化循环技术, 其目标 : 减少循环的耗费 ; 增加流水线执行的机会 ; 改善存储系统的性能 34

35 循环展开 (Loop unrolling) 减少循环的开销, 使能后续的优化, 比如指令并行 for (i=0; i<4; i++) a[i] = b[i] * c[i]; 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]; a[0] = b[0] * c[0]; a[1] = b[1] * c[1]; a[2] = b[2] * c[2]; a[3] = b[3] * c[3]; 35

36 循环合并与分解 (Loop fusion and distribution) 循环合并将两个或多个循环合并成一个 : for (i=0; i<n; i++) a[i] = b[i] * 5; for (j=0; j<n; j++) w[j] = c[j] * d[j]; for (i=0; i<n; i++) { } a[i] = b[i] * 5; w[i] = c[i] * d[i]; 循环分解将一个循环分解成多个 36

37 循环分块 (Loop tiling) 将一个循环拆分成一系列嵌套循环, 通过改变数组中的访问顺序, 改善 cache 性能 37

38 数组填充 (Array padding) 向循环中添加哑数据元素, 改变数组在高速缓存中的布局, 降低高速缓存冲突 a[0,0] a[0,1] a[0,2] a[0,0] a[0,1] a[0,2] a[0,2] a[1,0] a[1,1] a[1,2] a[1,0] a[1,1] a[1,2] a[1,2] before after 38

39 寄存器分配 (Register allocation) 目标 : 选择寄存器来保存每个变量决定变量在寄存器中的生命周期控制变量 ( 包括声明的和临时的 ) 在寄存器上的分配以最小化所需的寄存器总数用一个基本语句块的例子来说明 39

40 寄存器生命周期图 lifetime graph w = a + b; x = c + w; y = c + d; t=1 t=2 t=3 a b c d w x y 如果按照变量的个数进行寄存器分配, 将每个变量分配给独立的寄存器, 需要 7 个寄存器 time 40

41 优化的寄存器分配通过重用寄存器, 我们可以编写需要不到 4 个寄存器的代码 LDR r0, [p_a] LDR r1, [p_b] ADD r3, r0, r1 STR r3, [p_w] LDR r2, [p_c] ADD r0, r2, r3 STR r0, [p_x] LDR r0, [p_d] ADD r3, r2, r0 STR r3, [p_y] 41

42 寄存器溢出如果一段代码所需寄存器数目超过可用寄存器数目, 必须临时将一些值溢出 (spill) 到内存计算出的一些值后, 我们可以将其写入临时存储单元, 在其他计算中重用这些寄存器, 然后重新从临时存储单元读入以前的数值继续进行计算寄存器溢出的问题 : 需要额外的 CPU 时间增加指令和数据存储器的使用优化寄存器分配, 避免不必要的寄存器溢出是有价值的 42

43 寄存器分配问题通过建立冲突图 (conflict graph) 并解一个图的着色问题来解决寄存器分配问题每个变量由一个节点表示, 如果两个变量有相同的生存期, 就在两个点之间添加一条边图的着色问题就是用最少的颜色给全部节点着色, 要求两个相同颜色的节点之间没有一条直接相连的边图的着色问题是 NP-complete 问题, 但是有启发式算法 43

44 图着色问题约束受限问题, 请感兴趣的同学查看人工智能 - 一种现代的方法第 6 章内容 44

45 改善寄存器分配的操作调度 (a + b)*(c - d) 示例 5.6 w = a + b x = c + d y = x + e z = a - b 45

46 寄存器生命周期图 w = a + b x = c + d y = x + e z = a - b 46

47 汇编代码 (4 个寄存器 ) LDR r0,a LDR r1,b ADD r2,r0,r1 STR r2,w ; w = a + b LDR r3,c LDR r1,d ADD r2,r0,r1 STR r2,x ; x = c + d LDR r1,e ADD r0,r1,r2 STR r0,y LDR r0,a LDR r1,b SUB r2,r1,r0 STR r2,z ; y = x + e ; reload a ; reload b ; z = a b 47

48 操作调度后的 C 代码 w = a + b z = a - b x = c + d y = x + e 48

49 调度后的生命周期图 49

50 调度后的汇编代码 LDR r0,a LDR r1,b ADD r2,r0,r1 STR r2,w LDR r3,c LDR r1,d ADD r2,r0,r1 STR r2,x LDR r1,e ADD r0,r1,r2 STR r0,y LDR r0,a LDR r1,b SUB r2,r1,r0 STR r2,z ; w = a + b ; x = c + d ; y = x + e ; reload a ; reload b ; z = a b LDR r0,a LDR r1,b ADD r2,r1,r0 STR r2,w ; w = a + b SUB r2,r0,r1 STR r2,z ; z = a b LDR r0,c LDR r1,d ADD r2,r1,r0 STR r2,x ; x = c + d LDR r1,e ADD r0,r1,r2 STR r0,y ; y = x + e 50

51 调度预约表 reservation table 在指令调度期间用预约表跟踪 CPU 资源使用情况调度指令执行前, 要检查预约表确定所有指令所需的资源都是可用的调度后, 更新预约表 Time/instr A B instr1 X instr2 X X instr3 instr4 X X 51

52 指令调度 Non-pipelined machines do not need instruction scheduling: any order of instructions that satisfies data dependencies runs equally fast. In pipelined machines, execution time of one instruction depends on the nearby instructions: opcode, operands. 52

53 软件流水 software pipeline 流水线中, 如果指令执行所花费的周期比正常情况下多, 就会出现流水线气泡导致性能降低软件流水是一种对指令重排序的技术, 跨越几个循环迭代来减少流水线气泡 Reduces instruction latency in iteration i by inserting instructions from iteration i+1. 53

54 指令选择 (Instruction selection) 执行一个操作或一系列操作可能有几种不同的指令执行时间 / 对邻近代码的影响模板匹配 (template matching): 将操作用图表示, 使用可能的指令序列进行匹配 + * expression * + MUL ADD templates * + MADD 54

55 理解并使用你的编译器研究编译器的汇编语言输出是了解编译器的好方式理解并使用编译器不同的优化级别 (-O1, -O2, etc.) 尝试使用不同方式实现同一算法, 观察编译结果的区别在编译输出结果上修改, 但是要注意 : 正确性记录手工修改 55

56 Optimize options 56

Microsoft PowerPoint sun-program2.ppt [Compatibility Mode]

Microsoft PowerPoint sun-program2.ppt [Compatibility Mode] 嵌入式系统设计与应用第五章程序设计与分析 (2) 西安交通大学电信学院孙宏滨 4 基本编译技术编译 = 翻译 + 优化翻译 : 将高级语言程序翻译成低级形式的指令优化 : 与翻译过程中所使用的语句间相互独立的简单方法相比, 优化可以生成更高指令的代码编译决定着代码质量 : 占用 CPU 资源存储器访问调度代码大小 2 基本编译过程高级语言代码语法分析符号表生成和语义分析独立于机器的优化

Pengju 嵌入式系统设计与应用 第五章程序设计与分析 (2) 西安交通大学电信学院 任鹏举

Pengju 嵌入式系统设计与应用第五章程序设计与分析 (2) 西安交通大学电信学院任鹏举