目录出版者的话专家指导委员会序致中国读者译者序前言作者简介第1章 高性能体系结构对编译器的挑战 1
1.1 概述和目标 1
1.2 流水线 3
1.2.1 流水线指令部件 3
1.2.2 流水线执行部件 4
1.2.3 并行功能部件 5
1.2.4 标量流水线编译 5
1.3 向量指令 7
1.3.1 向量硬件概述 7
1.3.2 向量流水线编译 8
1.4 超标量处理器和VLIW处理器 9
1.4.1 多发射指令部件 9
1.4.2 多发射处理器的编译 10
1.5 处理器并行性 11
1.5.1 处理器并行性概述 11
1.5.2 异步并行性的编译 12
1.6.1 存储系统概述 14
1.6 存储层次结构 14
1.6.2 存储层次结构的编译 15
1.7 实例研究：矩阵乘法 15
1.8 先进编译技术 19
1.8.1 依赖 19
1.8.2 变换 20
1.9 小结 21
1.10 实例研究 21
1.11 历史评述与参考文献 21
习题 22
第2章 依赖：理论与实践 23
2.1 引言 23
2.2 依赖及其性质 23
2.2.1 存-取分类 24
2.2.2 循环内的依赖 25
2.2.3 依赖和变换 26
2.2.4 距离向量和方向向量 29
2.2.5 循环携带依赖和循环无关依赖 31
2.3 简单的依赖测试 36
2.4.1 并行化 38
2.4 并行化和向量化 38
2.4.2 向量化 39
2.4.3 一个先进的向量化算法 41
2.5 小结 44
2.6 实例研究 44
2.7 历史评述与参考文献 44
习题 45
3.1 引言 47
第3章 依赖测试 47
3.2 依赖测试概述 51
3.2.1 下标划分 51
3.2.2 合并方向向量 52
3.3 单下标依赖测试 52
3.3.1 ZIV测试 53
3.3.2 SIV测试 53
3.3.3 多归纳变量测试 61
3.4 耦合组中的测试 73
3.4.1 Delta测试 73
3.4.2 更强有力的多下标测试 79
3.5 实验研究 80
3.6 各种测试的集成 81
3.7 小结 86
3.8 实例研究 86
3.9 历史评述与参考文献 87
习题 87
第4章 初等变换 91
4.1 引言 91
4.2 信息需求 92
4.3 循环正规化 93
4.4 数据流分析 95
4.4.1 定义-使用链 95
4.4.2 死代码消除 97
4.4.3 常数传播 98
4.4.4 静态单赋值形式 100
4.5 归纳变量暴露 105
4.5.1 前向表达式替换 105
4.5.2 归纳变量替换 107
4.5.3 驱动替换过程 111
4.7 实例研究 113
4.6 小结 113
4.8 历史评述与参考文献 114
习题 114
第5章 提高细粒度并行性 117
5.1 引言 117
5.2 循环交换 118
5.2.1 循环交换的安全性 119
5.2.2 循环交换的有利性 121
5.2.3 循环交换和向量化 122
5.3 标量扩展 126
5.4 标量和数组重命名 133
5.5 节点分裂 138
5.6 归约识别 140
5.7 索引集分裂 143
5.7.1 阈值分析 143
5.7.2 循环剥离 144
5.7.3 基于区域的分裂 145
5.8 运行时符号解析 146
5.9 循环倾斜 147
5.10 各种变换的集成 150
5.11 实际机器的复杂性 155
5.12 小结 157
5.13 实例研究 157
5.13.1 PFC 158
5.13.2 ArdentTitan编译器 158
5.13.3 向量化的性能 159
5.14 历史评述与参考文献 161
习题 161
6.2 单循环的处理方法 163
第6章 开发粗粒度并行性 163
6.1 引言 163
6.2.1 私有化 164
6.2.2 循环分布 167
6.2.3 对齐 167
6.2.4 代码复制 170
6.2.5 循环合并 173
6.3 紧嵌循环套 184
6.3.1 为并行化的循环交换 184
6.3.2 循环选择 186
6.3.3 循环反转 189
6.3.4 为并行化的循环倾斜 190
6.3.5 幺模变换 193
6.3.6 基于有利性的并行化方法 194
6.4 非紧嵌循环套 196
6.4.1 多层循环合并 196
6.4.2 一个并行代码生成算法 199
6.5 一个扩充的例子 202
6.6.1 循环分段 204
6.6 并行性的封装 204
6.6.2 流水线并行性 205
6.6.3 调度并行任务 207
6.6.4 制导的自调度 209
6.7 小结 210
6.8 实例研究 211
6.8.1 PFC和ParaScope 211
6.8.2 ArdentTitan编译器 212
6.9 历史评述与参考文献 214
习题 215
第7章 处理控制流 217
7.1 引言 217
7.2 if转换 218
7.2.1 定义 218
7.2.2 分支的分类 219
7.2.3 前向分支 219
7.2.4 出口分支 222
7.2.5 后向分支 227
7.2.6 完全前向分支消除 229
7.2.7 化简 230
7.2.8 迭代依赖 234
7.2.9 if重构 237
7.3 控制依赖 238
7.3.1 构造控制依赖 240
7.3.2 循环中的控制依赖 241
7.3.3 控制依赖的一个执行模型 242
7.3.4 控制依赖在并行化中的应用 244
7.4 小结 254
7.5 实例研究 254
习题 255
7.6 历史评述与参考文献 255
第8章 改进寄存器的使用 257
8.1 引言 257
8.2 标量寄存器分配 257
8.2.1 面向寄存器重用的数据依赖 258
8.2.2 循环携带和循环无关的重用 259
8.2.3 寄存器分配的例子 260
8.3 标量替换 260
8.3.1 依赖图剪枝 261
8.3.2 简单替换 264
8.3.3 处理循环携带依赖 264
8.3.4 跨越多个迭代的依赖 265
8.3.5 删除标量拷贝 265
8.3.6 缓解寄存器压力 266
8.3.7 标量替换算法 267
8.3.8 实验数据 270
8.4 展开和压紧 272
8.4.1 展开和压紧的合法性 274
8.4.2 展开和压紧算法 276
8.4.3 展开和压紧的效果 279
8.5 面向寄存器重用的循环交换 281
8.5.1 对循环交换的考虑 283
8.5.2 循环交换算法 284
8.6 面向寄存器重用的循环合并 285
8.6.1 面向重用的有利的循环合并 285
8.6.2 面向合并的循环对齐 287
8.6.3 合并机制 291
8.6.4 加权循环合并算法 295
8.6.5 面向寄存器重用的多层循环合并 306
8.7 改进寄存器使用的变换综合 308
8.7.1 决定变换的顺序 308
8.7.2 例子：矩阵乘法 309
8.8 复杂的循环嵌套 310
8.8.1 包含if语句的循环 310
8.8.2 梯形循环 312
8.9 小结 316
8.10 实例研究 317
8.11 历史评述与参考文献 317
习题 318
第9章 管理高速缓存 319
9.1 引言 319
9.2 适合于空间局部性的循环交换 320
9.3 分块 325
9.3.1 非对齐的数据 326
9.3.2 分块的合法性 327
9.3.3 分块的有利性 327
9.3.4 一个简单的分块算法 329
9.3.5 带倾斜的分块 330
9.3.6 循环合并和对齐 332
9.3.7 结合其他变换的分块 333
9.3.8 有效性 335
9.4 复杂循环嵌套中的高速缓存管理 335
9.4.1 三角形的高速缓存分块 335
9.4.2 特殊用途的变换 336
9.5 软件预取 338
9.5.1 一个软件预取算法 339
9.5.2 软件预取的有效性 346
9.7 实例研究 347
9.6 小结 347
9.8 历史评述与参考文献 348
习题 349
第10章 调度 351
10.1 引言 351
10.2 指令调度 351
10.2.1 机器模型 353
10.2.2 直线型代码的图调度 353
10.2.3 表调度 354
10.2.4 踪迹调度 356
10.2.5 循环内的调度 359
10.3 向量部件调度 367
10.3.1 链接 368
10.3.2 协处理器 370
10.4 小结 372
10.5 实例研究 372
10.6 历史评述与参考文献 374
习题 375
11.2.1 过程间问题 377
11.2 过程间分析 377
11.1 引言 377
第11章 过程间分析和优化 377
11.2.2 过程间问题分类 382
11.2.3 流不敏感副作用分析 384
11.2.4 流不敏感别名分析 390
11.2.5 常数传播 394
11.2.6 注销分析 397
11.2.7 符号化分析 400
11.2.8 数组区域分析 402
11.2.9 调用图的构造 404
11.3 过程间优化 406
11.3.1 内联替换 407
11.3.2 过程克隆 408
11.3.3 混合优化 409
11.4 管理整个程序的编译 409
11.5 小结 411
11.6 实例研究 411
11.7 历史评述与参考文献 413
习题 414
12.2 优化C语言 417
12.1 引言 417
第12章 C语言和硬件设计中的依赖 417
12.2.1 指针 418
12.2.2 命名和结构 420
12.2.3 循环 421
12.2.4 作用域和静态变量 422
12.2.5 方言 422
12.2.6 其他问题 423
12.3 硬件设计 424
12.3.1 硬件描述语言 426
12.3.2 优化模拟 428
12.3.3 综合优化 439
12.4 小结 448
12.5 实例研究 448
12.6 历史评述与参考文献 449
习题 449
第13章 编译数组赋值 451
13.1 引言 451
13.2 简单的标量化 451
13.3.1 循环反转 454
13.3 标量化变换 454
13.3.2 输入预取 455
13.3.3 循环分裂 458
13.4 多维标量化 461
13.4.1 多维中的简单标量化 461
13.4.2 外层循环预取 462
13.4.3 用于标量化的循环交换 464
13.4.4 通用的多维标量化 467
13.4.5 一个标量化的例子 469
13.6 标量化后的循环交换和合并 471
13.5 对向量机器的考虑 471
13.7 小结 473
13.8 实例研究 474
13.9 历史评述与参考文献 474
习题 474
第14章 编译高性能Fortran 475
14.1 引言 475
14.2 HPF编译器概览 478
14.3.1 分布信息的传播和分析 481
14.3 基本循环的编译技术 481
14.3.2 迭代的划分 482
14.3.3 通信生成 485
14.4 优化 489
14.4.1 通信向量化 489
14.4.2 重叠通信和计算 494
14.4.3 对齐和复制 495
14.4.4 流水 496
14.4.5 一般依赖环的识别 498
14.4.6 存储管理 499
14.4.7 处理多个维 501
14.5 HPF的过程间优化 503
14.6 小结 504
14.7 实例研究 504
14.8 历史评述与参考文献 506
习题 506
附录 Fortran 90基础 509
参考文献 515
索引 535