Open64课程-循环嵌套优化(LNO)

循环嵌套优化(LNO)
此文是Fred Chow在德拉华大学所讲open64课程讲义的翻译，转载请注明出处 http://www.lingcc.com
Fred Chow 原版讲义见最后一页

• 循环嵌套优化

循环嵌套优化(LNO)概述
该优化主要在嵌套循环上做转换。该部分工作的范围时每个顶层循环内的嵌套，优化分析过程中并不构建控制流图，而是通过数据依赖分析驱动。使用标量优化阶段(WOPT)提供的别名和使用-定义信息，并通过代码生成器将数据依赖信息附注在每个use上(仅在最内层循环),这部分优化需要对硬件资源建模。

• 依赖测试

依赖的定义：给定两个引用R1和R2，若它们都访问同一块内存且从R1到R2有路径存在，则称R2依赖于R1，依赖分为：真依赖，反向依赖(anti dependence)和输出依赖三种。另外还要说明访问数组和向量(vector)的区别，访问数组当每个数组的下表时循环归纳变量时,访问向量时所有的向量下标都访问数组。依赖测试(输入是访问数组时),参考论文<高效精准的数据依赖分析>(Efficient and Exact Data Dependence Analysis),Dror Maydan,et al.., PLDI’91. 依赖测试的输出是依赖向量，每一维表示一个循环嵌套的层。

• LNO实施的三类优化

数据缓存转换(?),协助其他优化的转换，向量化和并行化

• 用于数据缓存的LNO转换

通过缓存分块实现，即将循环转换为工作在能装在cache中的子矩阵上。此外还有循环交换，数组填充(减少缓存冲突)，预取生成（隐藏cache失效访问的长延时）和循环合并及分裂等转换。缓存分块如下
for (i=0; i
for (j=0; j
for (k=0; k
c[i][j] = c[i][j] + a[i][k]*b[k][j];

矩阵B会一直出现缓存失效，总共失效n^3+2*n^2次(不考虑矩阵行大小).若使用能整个装入cache的子矩阵，如下图所示

则C11 = A11 * B11 + A12 * B21。对于b大小的子矩阵，失效次数为(n/b)*n^2+2*n^2

• 循环交换(置换)

增加数据的局部性
如
DO I = 1, N
DO J = 1, M
A(I, J) = B(I, J) + C
此时，没有空间重用，对于每个A和B的引用都将cache失效
DO J = 1, M
DO I = 1, N
A(I, J) = B(I, J) + C
每进行16次循环才会失效一次(假设数组元素为4字节，缓存行大小为64字节)
(译者注：此处的例子是Fortran语言，该语言二维数组在内存内按列存储)
这里面的转换为单模转换，并将其和缓存分块，循环翻转和循环偏移等结合起来增强循环嵌套的总体数据局部性。并实现自动向量化和并行化。

• 软预取

软预取主要考虑一下三个方面：取什么，何时取，避免无用的预取。对于第一点，仅对最可能引起cache失效的引用取；对于第二点，确保不早也不晚；对于第三点，综合考虑寄存器压力，缓存污染和存储带宽进行。我们的预取引擎的主要阶段:先Process_Loop–构造内建结构等；之后Build_Base_LGs–建本地化组(即可能引用相同缓存行(cache line)的),然后Volume–从最内层到最外层计算每个循环的数据量；Find_Loc_Loops–决定那个本地化的组需要预取；Gen_Prefetch–生成预取指令。
提前预取N个缓存行：对于a(i)，预取a(i+N*line_size),使用选项-LNO:prefetch_ahead=N（默认为2)来控制。每个缓存行一个预取指令，这里牵涉到两个问题，循环中的版本化以及和循环展开的结合。对于前者，可以转换如下
DO I = 1, N
if I % 16 == 0 then
含预取指令的循环体
else 不含预取指令的循环体
对于后者，转换为：
DO I = 1, N, 16
prefetch b(I + 2*16)
a = a + b(I)
a = a + b(I+1)
...
a = a + b(I+15)


• 循环分解和合并

循环分解：使得循环交换，向量化和并行化成为可能，减少冲突失效。对于循环合并：减少循环开销，增加数据重用，增大循环规模。

• 协助其他优化的LNO转换

标量展开和数组展开：减少循环内依赖，使并行化成为可能；标量重命名：循环嵌套就能分别优化，减少寄存器分配时的约束；数组标量化：改进寄存器分配；此外还有提升混乱的循环边界、最外层循环展开(该过程可以形成更大的循环体，减少循环开销）、数组替换(前向和后向)、IF语句提升(通过重复匹配的迭代来代替循环)、循环反转换(即将循环内无关的条件判断移出)、聚合-分散(?)、提升不变数组引用到循环外、迭代内CSE
(译者注：本段提到的几个优化，Fred Chow都有例子在ppt中，本人偷懒没有附上，请到本文最后一页的原版ppt中参阅第13-18页)

• LNO并行化

并行化包括三部分：SIMD代码生成(高度依赖目标机的SIMD指令)，生成向量intrinsic(基于可用的库函数)以及自动并行化(受其余后端部分OpenMP支持的影响)。

• 向量化

应用在最内层循环，没有牵涉在一个依赖环中的任何语句都可能会有向量化机会

通用向量化的实现首先需要约束检测，之后要对最内层循环做依赖分析，包括构建语句依赖图，检测依赖环(强联通分量，SCCs);然后使用实现向量化的技术，在有依赖环的地方使用(参见下面),最后将循环重写为向量化的循环。

• 实现向量化的技术

标量展开
DO I = 1, N
T = a(I)
a(I) = b(I)
b(I) = T
ENDDO
将标量T展开为数组t后
DO I = 1, N
t(I) = a(I)
a(I) = b(I)
b(I) = t(I)
ENDDO


• 循环分裂

DO I = 1, N
a(I+1) = a(I) + C //依赖环
b(I) = b(I) + D //无环
ENDDO
转换为
DO I = 1, N
a(I+1) = a(I) + C //有环，不可向量化
ENDDO
DO I = 1, N
b(I) = B(I) + D //无环，可向量化
ENDDO
其他的机制L循环交换，数组重命名等

• 关于SIMD的额外考虑

SIMD是向量化的特殊形式，对数组的访问要求连续,如A[2*i]和A[2*(i+1)]就不连续，对于F90，可能需要循环变体来确保连续性。此外还有对齐问题，有时因为没有对齐到128位边界可能没有任何优化效果，可能还需要去掉一些层。另外，可能需要剩余循环
DO I=1,N
a(I)=a(I)+C
ENDDO
转换为
DO I=1,N-N%4,4
a(I:I+3) =a(I:I+3)+C
ENDDO
!remainder
DO I =N-N%4,N
a(I)=a(I)+C
ENDDO

• 有削弱的SIMD

可能需要对每个计算单元复制累加器

• 生成向量Intrinsic

为了分离出intrinsic,通常需要循环分解，如
for(i=0;i
a[i] = a[i]+3.0;
u[i] = cos(ct[i]);
}
转换为
vcos(&ct[0],&u[0],N,1,1);
for(i=0;i
a[i]=a[i]+3.0;


• LNO阶段结构

预优化 Pre-optimization
完全短循环展开 Fully Unroll Short Loops (lnopt_main.cxx)
构建数组依赖组Build Array Dependence Graph (be/com/dep_graph.cxx)
多种优化 Miscellaneous Optimization:提升易变的循环下界 hoist varying lower bounds(access_main.cxx)、形式化最小/最大值 form min/max(ifminmax.cxx)、死存储删除数组 dead store eliminate arrays(dead.cxx)、数组替换(前向和后向) array substitutions（forward and backward)（forward.cxx)、循环翻转 loop reversal (reverse.cxx)
循环反转换 Loop unswitching（cond.cxx)
缓存分块 Cache Blocking (tile.cxx)
循环交换 loop interchange (permute.cxx)
循环合并 loop fusion (fusion.cxx)
提升混乱的循环便捷 Hoist Messy Loop Bounds(array_bounds.cxx)
数组填充 Array Padding （pad.cxx）
并行化 parallellization (parallel.cxx)
束缚 Shackling (shackle.cxx)
聚合发散 Gather Scatter (fis_gthr.cxx)
循环拆分 Loop Fission (fission.cxx)
SIMD （simd.cxx)
提升IF语句 Hoist IF （inopt_hoistif.cxx)
生成向量intrinsics （vintr_fis.cxx)
生成预取指令 Generate Prefetches (prefetch.cxx)
数组标量化 Array Scalarization(sclrze.cxx)
循环无关量外提 Move Invariant Outside the Loop (minvariant.cxx)
循环迭代内通用子表达式删除 Inter-Iteration Common Sub-Expression Elimination (cse.cxx)

此文是Fred Chow在德拉华大学所讲open64课程讲义的翻译，转载请注明出处 http://www.lingcc.com
Fred Chow 原版讲义见最后一页

整个Open64课程系列的文章包括以下，请阅读中指正

Open64课程-简介，概述和中间表示

Open64课程- 编译过程

Open64课程-内联

Open64 课程–全局标量优化(WOPT I) part 1

Open64 课程–全局标量优化(WOPT I) part II

Open64 课程–全局标量优化(WOPT II)

open64课程–过程间分析优化(IPA)

Open64课程—代码生成(CG)

相关文章:

• Open64课程-结语
• Open64课程–OpenMp和自动并行化
• Open64课程-简介，概述和中间表示
• Open64课程-内联
• Open64课程-编译过程
• Open64课程–反馈指导优化(FDO)
• open64课程–过程间分析优化(IPA)
• Open64课程—代码生成(CG)
• Open64 课程–全局标量优化(WOPT II)
• Open64 课程–全局标量优化(WOPT I) part II