循环级优化

循环不变量外提

循环不变量是指在循环迭代空间内值不发生变化的变量。由于循环不变量的值在循环的迭代空间内不发生变化，因此可将其外提到循环外仅计算一次，避免其在循环体内重复计算。示例如下，经过循环不变量外提后，上述循环的计算强度得到了削弱，提高了代码的性能。

优化前代码：

优化后代码：

循环展开

循环展开是一种常用的提高程序性能方法，它通过将循环体内的代码复制多次的操作，进而减少循环分支指令执行的次数，增大处理器指令调度的空间，获得更多的指令级并行。

优化前代码：

优化后代码：

循环合并

循环合并是指将具有相同迭代空间的两个循环合成一个循环的过程，其属于语句层次的循环变换。但并不是所有循环都可以进行合并，循环合并需要满足合法性要求，有些情况下循环合并会导致结果错误。

优化前代码：

优化后代码：

满足合法性要求的循环合并可以减小循环的迭代开销以及并行化的启动和通信开销，还可能增强寄存器的重用。

优化前代码：

优化后代码：

循环分段

循环分段可将单层循环变换为多层嵌套循环，循环分段的段长可根据需要选取。如果原循环是可并行化的循环，则分段后依然可以实施并行化变换。通常采用循环分段技术实现外层的并行化以及内层的向量化，以达到利用系统多层次并行资源的目的。

优化前代码：

优化后代码：

循环交换

循环交换是一个重排序变换，在程序的向量化和并行化识别以及增强数据局部性方面都起着重要的作用。

 优化前代码：

优化后代码：

循环交换在某些情况下也能提高寄存器的重用能力。为了提高寄存器重用能力的循环交换的目的在于把携带依赖的循环放在最内层的位置，使可以被重用的值保留在寄存器中。

优化前代码：

优化后代码：

循环分块

循环分块是指通过增加循环嵌套的维度来提升数据局部性的循环变换技术，是对多重循环的迭代空间进行重新划分的过程，循环分块前后要保证迭代空间相同。循环分块是循环交换和循环分段的结合。可以提高程序的局部性，增加数据重用来提升程序的性能

C语言访存数据是行优先的原则，设置S长度与硬件平台高速缓存行相匹配，将控制这些分段上进行迭代的循环移动最外层的位置，这样单次迭代数据量得到了大幅度的减少，减少了从主存取数的时间，进而提升了性能。

对循环分块前后优化效果进行测试，编译器版本为llvm-13，示例优化前执行时间为3600us，优化后执行时间为397us，可以看出有将近十倍的加速效果。

循环分布

循环分布将一个循环分解为多个循环，每个循环都有与原循环相同的迭代空间，但只包含原循环的语句子集。通过循环分布可以a减少指令缓存的压力，还能增加寄存器的重用，常用于分解出可向量化或可并行化的循环，进而将可向量化部分的代码转为向量执行。

优化前代码：

优化后代码：

循环分裂

循环分裂是对循环的迭代次数进行拆分，将循环的迭代次数拆成两段或者多段，但是拆分后的循环不存在主体循环之说，也就是拆分成迭代次数都比较多的两个或者多个循环。

 优化前代码：

优化后代码：