Microsoft PowerPoint sun-program2.ppt [Compatibility Mode]

Size: px

Start display at page:

Download "Microsoft PowerPoint sun-program2.ppt [Compatibility Mode]"

懿厄林
5 years ago
Views:

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

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

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

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

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

6 算术表达式 (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 一个明显的优化方法是重用哪些其值不用再保存的寄存器寄存器分配问题! 6

7 条件语句 (1) if (a+b > 0) else x = 5; x = 7; a+b>0 x=7 x=5 F T 7

8 1 3 条件语句 (2) a+b>0 x=5 x=7 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 label3 stmtend... LDR r3,#7 ADR r5,x STR r3,[r5] 8

9 过程链接过程定义包括 : 生成处理过程调用与返回的代码传递参数和返回值过程链接机制允许参数和返回值传递, 并保护和恢复修改过的寄存器参数和返回值主要通过栈 (stack) 来传递少量参数也可以通过寄存器来传递 9

10 过程调用与传递参数 void f1 (int a) { } f2 (a); f1 LDR r0, [r13] STR r14, [r13]! ; call f2() STR r0, [r13]! BL f2 SUB r13, #4 ; return LDR r15, [r13]! 10

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

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

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

14 一维数组一维数组 a[i] 第 0 个元素存储数组的第一个元素 aptr a[0] a[1] a[2] = *(aptr + 1) 14

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

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

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

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

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

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

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

22 循环展开减少循环的开销, 使能后续的优化, 比如指令并行 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]; 22

23 循环融合与分布循环融合将两个或多个循环合并成一个 : 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]; } 循环分布将一个循环分解成多个 23

24 循环交叠 loop tiling 将一个循环拆分成一系列嵌套循环, 改善 cache for (i=0; i<n; i++) for (j=0; j<n; j++) c[i] = a[i,j]*b[i]; for (i=0; i<n; i+=2) for (j=0; j<n; j+=2) for (ii=0; ii<min(i+2,n); ii++) for (jj=0; jj<min(j+2,n); jj++) c[ii] = a[ii,jj]*b[ii]; 24

25 循环交叠 25

26 数组填充 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 26

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

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

29 优化的寄存器分配通过重用寄存器, 我们可以编写需要不到 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] 29

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

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

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

33 寄存器生命周期图 33

34 汇编代码 (4 个寄存器 ) LDR r0,a LDR r1,b ADD r2,r0,r1 STR r2,w ; w = a + b LDRr r0,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 34

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

36 调度后的生命周期图 36

37 调度后的汇编代码 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 37

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

39 指令调度 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. 39

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

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

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

43 解释器与 JIT 编译器解释器 (Interpreter): 实时的翻译和执行代码. JIT 编译器 :Java 与 JIT 43

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

嵌入式系统设计与应用 Pengju XJTU 2017 第五章程序设计与分析 (2) 西安交通大学电信学院任鹏举嵌入式系统设计与应用第五章程序设计与分析 (2) 西安交通大学电信学院任鹏举目标代码设计可重入 : 如果程序执行一个函数时被另一个执行该函数的调用中断而不改变函数结果, 则该函数是可重入的 int foo = 1; int task1() { foo = foo + 1; return foo;} } int task1(int foo){ return foo+1; 可重定位 : 若一个程序置于内存不同位置均可执行,