循环优化

向量化和自动并行化是现代编译器用来提高程序性能的两种重要技术，特别是在处理循环密集型的代码时。它们都旨在利用现代处理器的并行执行能力，但对循环结构的要求各有侧重

向量化的条件

向量化是将循环中的操作转换为一种可以利用处理器的向量指令集执行多个操作的形式，通常涉及SIMD（单指令多数据）指令

数据独立性：循环的迭代之间不能有数据依赖，即循环的每次迭代必须能够独立执行。如果一个迭代的结果依赖于另一个迭代的结果，那么这个循环通常不能向量化
固定迭代次数：循环的迭代次数最好是在循环开始前就确定的。虽然这不是绝对必要的，但对于某些类型的向量化是有帮助的
简单循环体：循环体应该是简单的，最好只包含简单的算术运算、逻辑运算和数组访问。复杂的控制流（如条件分支）可能会阻碍向量化
对齐的数据访问：为了最有效地使用SIMD指令，被处理的数据最好在内存中对齐，并且以向量长度为单位连续存储

自动并行化的条件

自动并行化是编译器的一个特性，它可以将代码转换成可以利用多核CPU并行执行的形式

数据独立性：与向量化类似，循环的迭代之间不能有数据依赖，特别是写入依赖（WAW）和读写依赖（WAR）
足够的工作量：循环应该有足够的工作量来抵消并行化引入的开销，如线程创建和同步的成本。循环迭代次数较多且循环体计算密集的循环是并行化的好候选
可预测的性能收益：并行化应该能够预测性地带来性能提升。这通常意味着循环的执行时间远大于并行执行的开销
可管理的同步和通信开销：并行化循环时，需要同步和通信以确保正确性和一致性。循环结构应该使这些开销保持在可接受的范围内

循环展开、循环压紧

循环展开

循环展开（loop unrolling）是一种减少循环迭代次数以减少循环控制开销的技术。通过在每次迭代中执行多个循环体的副本，可以减少循环条件的评估次数和循环变量更新的次数。
这样做的好处是可以减少执行循环控制逻辑的开销，并有可能增加并行度或使编译器更容易进行其他优化，如指令调度。

一个简单的循环执行10次内部操作，通过将其展开两倍，可以使循环仅执行5次迭代，但每次执行两倍的操作。

循环展开的挑战在于找到最佳的展开因子（即每次迭代中包含的循环体副本数量）。过多的展开可能会增加代码大小（代码膨胀），影响缓存利用率，并且对于
已经很小的循环，可能不会带来性能提升。

优点

减少循环分支指令执行的次数
获得了更多的指令级并行
增加了寄存器的重用

例子

对内层循环进行循环展开

for (i = 0; i < N; ++i) {
    for (j = 0; j < N; ++j) {
        A[i][j] = A[i][j] + B[i][j] * C[i][j];
    }
}

for (i = 0; i < N; ++i) {
    for (j = 0; j < N; j += 4) {
        A[i][j] = A[i][j] + B[i][j] * C[i][j];
        A[i][j + 1] = A[i][j + 1] + B[i][j + 1] * C[i][j + 1];
        A[i][j + 2] = A[i][j + 2] + B[i][j + 2] * C[i][j + 2];
        A[i][j + 2] = A[i][j + 3] + B[i][j + 3] * C[i][j + 3];
    }
}

对外层循环进行循环展开

for (i = 1; i < N; ++i) {
    for (j = 1; j < N; ++j) {
        A[i + 1][j - 1] = A[i][j] + 3;
    }
}

for (i = 1; i < N; i += 2) {
    for (j = 1; j < N; ++j) {
        A[i + 1][j - 1] = A[i][j] + 3;
        A[i + 2][j - 1] = A[i][j] + 3;
    }
}

当迭代次数不能被循环展开次数整除的情况下，需要在进行循环展开的同时考虑尾循环的处理

编译器中的循环展开

clang unroll.c -O1 -funroll-loops -emit-llvm -S -Rpass=loop-unroll

一些与循环展开的编译选项

-funroll-loops：打开循环展开
-fno-unroll-loops：关闭循环展开
-mllvm -unroll-max-count=n：指定最大展开次数
-mllvm -unroll-count=n：指定循环展开次数
-mllvm -unroll-runtime：使用运行时循环展开优化
-mllvm -unroll-threshold=n：设置代码量展开限制
-mllvm -unroll-remainder：对循环展开后的剩余循环进行优化
-Rpass=loop-unroll：显示循环展开的优化信息
-Rpass-missed=loop-unroll：显示循环展开失败的信息

progma

// 打开循环展开
#progma clang loop unroll(enable)
// 进行完全循环展开
#progma clang loop unroll(full)
// 指定循环展开次数
#progma clang loop unroll_count(n)

针对向量程序的循环展开

类似

循环压紧

循环压紧指调整复制后的语句执行，将原来一条语句复制得到的多条语句合并到一起

循环合并

循环合并（Loop Fusion）是指将具有相同迭代空间的两个循环合成一个循环的过程，属于语句层次的循环变换

优点

减小循环的迭代开销
增强数据重用，寄存器重用
减小并行化的启动开销，消除合并前多个循环间的线程同步开销
增加循环优化的范围

例子

for (i = 0; i < N; ++i) {
    x[i] = a[i] + b[i];
}
for (i = 0; i < N; ++i) {
    y[i] = a[i] - b[i];
}

for (i = 0; i < N; ++i) {
    x[i] = a[i] + b[i];
    y[i] = a[i] - b[i];
}

循环合并的合法性

不能违反原来的依赖关系图；如果两个循环之间存在一条循环无关的依赖途径，这条路径包含一个未与它们合并的循环语句，则它们不能被合并
不能产生新的依赖；如果两个循环之间存在一个阻止合并的依赖，则它们不能被合并

for (i = 1; i < N; ++i) {
    A[i] = B[i] + C;
}
for (i = 1; i < N; ++i) {
    D[i] = A[i + 1] + E;
}

不能合并为下面这样

for (i = 1; i < N; ++i) {
    A[i] = B[i] + C;
    D[i] = A[i + 1] + E;
}

循环合并的有利性

循环合并的一个重要应用场景为并行化，但不是所有循环合并都可以给并行化带来收益

分离限制：当一个并行循环和一个串行循环合并时，结果必然是串行执行的

for (i = 1; i < N; ++i) {
    A[i] = B[i] + 1;
}
for (i = 1; i < N; ++i) {
    C[i] = A[i] + C[i - 1];
}

for (i = 1; i < N; ++i) {
    A[i] = B[i] + 1;
    C[i] = A[i] + C[i - 1];
}

阻止并行性的依赖限制，当两个都可并行的循环在一个阻止并行的依赖，进行循环合并后该依赖被合并后的循环携带

for (i = 1; i < N; ++i) {
    A[i + 1] = B[i] + C;
}
for (i = 1; i < N; ++i) {
    D[i] = A[i] + E;
}

for (i = 1; i < N; ++i) {
    A[i + 1] = B[i] + C;
    D[i] = A[i] + E;
}

编译器中的循环合并

在LLVM中进行循环合并需要满足以下条件

两个循环必须相邻，即两个循环之间不能有语句
两个循环必须有相同的迭代次数
循环必须是等价的控制流，如果一个循环执行，另一个循环也保证执行
循环之间不能有负距离依赖关系，比如两个循环，当第二个循环的迭代次数为m时，使用第一个循环在未来的m+n次迭代时计算的值

LLVM提供以下选项

-fproactive-loop-fusion-analysis：打开循环合并分析遍
-fproactive-loop-fusion：打开循环合并优化遍
-loop-fusion：通过opt工具对中间码进行循环合并优化

循环分布

循环分布（Loop Distribute）是指将一个循环分解为多个循环，且每个循环都有与原循环相同的迭代空间，但只包含原循环的语句子集，常用于分解出可向量化或者
可并行化的循环，进而将可向量化部分的代码转为向量执行。

优缺点

优点

将一个串行循环转变为多个并行循环
实现循环的部分并行化
增加循环优化的范围

缺点

减小并行性粒度
增加额外的通信和同步开销

应用场景

改善缓存利用：通过分解循环，可以减少单个循环迭代中的工作量，使得循环体中访问的数据更可能在缓存中保持，从而减少缓存未命中的次数
减少资源冲突：在并行计算中，不同的循环可能更容易在不同的处理单元上并行执行，减少了资源（如寄存器或内存带宽）的冲突
便于进一步优化：分解后的循环可能更容易被编译器进一步优化，比如循环展开、向量化或自动并行化

例子

for (i = 0; i < n; ++i) {
    A[i] = i;
    B[i] = 2 + B[i];
    C[i] = 3 + C[i - 1];
} // 不可并行化

for (i = 0; i < n; ++i) {
    A[i] = i;
    B[i] = 2 + B[i];
} // 可并行化
for (i = 0; i < n; ++i) {
    C[i] = 3 + C[i - 1];
} // 将不可并行化的部分分离

效果

将循环携带依赖变为循环无关依赖

for (i = 1; i < N; ++i) {
    for (j = 1; j < N; ++j) {
        A[i][j] = B[i][j] + C[i][j];
        D[i][j] = A[i][j - 1] * 2; 
    }
}

for (i = 1; i < N; ++i) {
    for (j = 1; j < N; ++j) {
        A[i][j] = B[i][j] + C[i][j];
    }
}
for (i = 1; i < N; ++i) {
    for (j = 1; j < N; ++j) {
        D[i][j] = A[i][j - 1] * 2; 
    }
}

与循环交换优化的配合

若循环不是紧嵌套循环导致无法进行后续优化操作时，可以使用循环分布将循环体变换为紧嵌套循环

优化人员会通过循环交换的方法对j层和k层交换，以提高访存速度和向量化能力，但是由于A[i][j] = D的存在，该循环不是紧嵌套循环，不能直接将j层和k层进行交换

for (i = 1; i < N; i++) {
	for (j = 1; j < N; j++) {
  		A[i][j] = D;
   		for (k = 1; k < N; k++) {
    		A[i][j] = A[i][j] + B[i][k] * C[k][j];
        }
    }
}

经过循环分布后变为紧嵌套循环，再使用循环交换以达到最好的性能

for (i = 1; i < N; i++)
 	for (j = 1; j < N; j++)
  		A[i][j] = D;

for (i = 1; i < N; i++)
 	for (j = 1; j < N; j++)
  		for (k = 1; k < N; k++)
   			A[i][j] = A[i][j] + B[i][k] * C[k][j];

与循环合并优化的配合

由于S2语句存在一个自身的循环携带依赖导致该循环无法进行并行化，但S1和S3语句不携带依赖是可以并行化的，因此可先通过循环分布优化将S2和S3语句分离出去

for(i=1;i<N;i++){
  	A[i] =  B[i] + 1;                              //S1语句
  	C[i] = A[i] + C[i-1];                          //S2语句
  	D[i] = A[i] + x;                               //S3语句
}

分离

for(i=1;i<N;i++)
  	A[i] =  B[i] + 1;                              //S1语句
for(i=1;i<N;i++)
  	C[i] = A[i] + C[i-1];                          //S2语句
for(i=1;i<N;i++)
  	D[i] = A[i] + x;                               //S3语句

合并：S1和S3语句组成的循环可以进行并行化

for(i=1;i<N;i++){
  	A[i] =  B[i] + 1;                               //S1语句
  	D[i] = A[i] + x;                                //S3语句
} 
for(i=1;i<N;i++)
  	C[i] = A[i] + C[i-1];                           //S2语句

编译器中的循环分布

LLVM：-mllvm -enable-loop-distribute
GCC：-ftree-loop-distribute

加入优化选项-mllvm -enable-loop-distribute打开循环分布优化，并通过选项-Rpass=loop-distribute提供循环分布优化成功的信息，
通过-Rpass-missed=loop-distribute -Rpass-analysis=loop-distribute 两个选项可以分别提供分布优化失败、以及失败的分析

progma

#progma clang loop distribute(enable)

循环交换

当一个循环体中包含一个以上的循环，且循环语句之间不包含其它语句，则称这个循环为紧嵌套循环，交换紧嵌套中两个循环的嵌套顺序是提高程序性能最有效的变换之一。
实际上，循环交换是一个重排序变换，仅改变了参数化迭代的执行顺序，但是并没有删除任何语句或产生任何新的语句，所以循环交换的合法性需要通过循环的依赖关系进行判定

优点

增强数据局部性
增强向量化和并行化的识别

例子

效果

//循环交换前
for (j = 0; j < N; j++)
    for (k = 0; k < N; k++)
        for (i = 0; i < N; i++)
            A[i][j] = A[i][j] + B[i][k] * C[k][j];	
//循环交换后
for (j = 0; j < N; j++)
    for (i = 0; i < N; i++)
        for (k = 0; k < N; k++)
            A[i][j] = A[i][j] + B[i][k] * C[k][j];

循环交换的有利性

//循环交换前
for(i=1;i<N;i++)
    for(j=1;j<N;j++)
        A[i][j+1] = A[i][j] + 2;	
//循环交换后
for(j=1;j<N;j++)
    for(i=1;i<N;i++)
        A[i][j+1] = A[i][j] + 2;

最内层的循环存在循环携带依赖，而导致循环无法进行并行化，向量化的效果变差。如果交换这两个循环，依赖关系就变为由外层循环携带，而内层循环不携带依赖，
就可以进行并行化，或者把可向量化的循环移动到最内层而提高向量化效果

//循环交换前
for (j = 1; j < N; j++)
   for (i = 1; i < M; i++)
        A[i][j] = A[i - 1][j];	
//循环交换后
for (i = 1; j < M; j++)
    for (j = 1; i < N; i++)
        A[i][j] = A[i - 1][j];

内层循环每一次迭代都需要进行存储和读取操作，共需MN次，寄存器重用较少。进行循环交换后，仍然需要MN次的存储操作，但读取操作的次数减少到了N次，
即第一行的每个值都放在寄存器里被重用了M次。循环交换还可以提高寄存器的重用能力，把携带依赖的循环放在最内层的位置，使可以被重用的值保留在寄存器中

循环依赖的合法性

重排序某个依赖端点的循环交换是不合法的，即不要引起依赖关系的反转

编译器中的循环交换

clang test.c -O1  -mllvm -enable-loopinterchange -Rpass=loop-interchange -Rpass-missed=loop-interchange -Rpass-analysis=loop-interchange

LLVM：-mllvm -enable-loopinterchange
GCC：-floop-interchange

循环不变量外提

循环不变量是指在循环迭代空间内值不发生变化的变量；由于循环不变量的值在循环的迭代空间内不发生变化，因此可将其外提到循环外仅计算一次，避免其在循环体内重复计算

for (i = 1; i < N; ++i) {
    for (j = 1; j < M; ++j) {
        U[i] = U[i] + W[i] * W[i] * D[j] / (dt * dt);
    }
}

T1 = 1 / (dt * dt);
for (i = 1; i < N; ++i) {
    T2 = W[i] * W[i];
    for (j = 1; j < M; ++j) {
        U[i] = U[i] + T2 * D[j] * T1;
    }
}

编译器中的循环不变量外提

clang test.c -O1 -Rpass=licm

使用-O1选项即可打开循环不变量优化

确定循环

计算该循环的标头（header）结点和支配（dominate）结点和定义（define）结点
寻找循环不变语句
找到循环的出口（exit）块：在循环外有后继结点（successor）的块

找出符合以下条件的代码并进行外提

是循环不变量
位于支配出口的块中
位于支配循环中所有使用其计算值块的基本块中
这个变量在循环内只有一次赋值

对循环采用深度优先算法，进行搜索，从候选项中选出不变量

如果不变量所依赖的所有不变操作都已移动，则把它移动到preheader块里面，完成优化算法

循环分段

循环分段是将单层循环变换为两层嵌套循环，内层循环遍历的是迭代次数为strip的连续区域(或叫条带循环)，外层循环的步进单位为strip，这个strip就是分段因子，分段因子需要根据硬件情况选取

for(i = 0; i < N; i++) {
    A[i] = B[i] + C[i];
  }
//循环分段后
for(i = 0; i < N; i += k) {    //并行执行
    for(j = i; j <= i + k - 1; j++) {
        A[j] = B[j] + C[j];    //向量执行
      }
}

充分利用多个处理器资源
将可用的并行性转换成更适合硬件的形式

不适用的情况

for(i = 1; i < SIZE; i++){
    for(j = 1; j < i; j++) {
        A[i][j] = A[i][j - 1] + B[i];
    }
}

内层循环中每次迭代调用的数组A[i][j]的数量都不同，找到一个有效的平衡点很难，通常宁愿选择一个较小的分段大小，而不是把并行循环平均分到处理其中，
这样当负担较重的处理器还在执行时，执行结束较早的处理器可以承担一些过剩的工作

循环分块

循环分块是指通过增加循环嵌套的维度来提升数据局部性的循环变换技术，是对多重循环的迭代空间进行重新划分的过程。在计算机存取数据，
需要从主存将数据取到寄存器中，这一过程为了是数据存取更有效率，在主存和寄存器中会存在一个高速缓存Cache，缓存常用的数据，但存储
量很少，通常当某个数据现在被用过以后，后面还会被用，但是按循环默认的执行方式，可能到下次再被用到的时候就已经从高速缓存行Cache
中被消除了，于是重排循环，减少内层循环的迭代量，使得一个cache line在被消除之前会被再次使用

过程

首先将一个循环经过循环分段得到两个循环，其中一个循环在循环内进行连续地迭代，而另一个循环进行逐段地迭代且迭代跨度为S，之后经过循环
交换将内外层循环交换，这一过程需要保证与分块前的迭代空间相同

for (i = 0; i < N; ++i) {
    for (j = 0; j < N; ++j) {
        B[i] = B[i] + A[i][j];
    }
}

循环分段

S = 4;
for (i = 0; i < N; ++i) {
    for (j = 0; j < N; j += S) {
        for (k = j; k <= MIN(j + S - 1, N); ++k) {
            B[i] = B[i] + A[i][k];
        } 
    }
}

循环交换

S = 4;
for (j = 0; j < N; j += S) {
    for (i = 0; i < N; ++i) {
        for (k = j; k <= MIN(j + S - 1, N); ++k) {
            B[i] = B[i] + A[i][k];
        }
    }
}

循环分块是循环分段和循环交换的结合，其合法性也同这两个优化方法一致，不能破坏原程序语义

e.g.

//示例1：循环分块前
#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
int main() {
  const int N = 512;
  const int M = 1024;
  double A[N][M], B[N];
  int i, j, k;
  struct timeval  time_start, time_end;
  for (i = 0; i < N; i++) {
    B[i] = rand()%10;
    for (j = 0; j < N; j++) {
      A[i][j] = rand()%10;
    }
  }
  gettimeofday(&time_start, NULL);
  for (j = 0; j < M; j++){
    for (i = 0; i < N; i++){
      B[i] = B[i] + A[i][j];//语句S
    }
  }
  gettimeofday(&time_end, NULL);
  printf("used time %ld us\n", time_end.tv_usec - time_start.tv_usec);
}

//示例1：循环分块后
#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
#define MIN(i,j) (((i)<(j))?(i):(j))
int main() {
  const int N = 512;
  const int M = 1024;
  double A[N][M], B[N];
  int i, j, k,I,J,S;
  struct timeval  time_start, time_end;
  for (i = 0; i < N; i++) {
    B[i] = rand()%10;
    for (j = 0; j < M; j++) {
      A[i][j] = rand()%10;
    }
  }
  gettimeofday(&time_start, NULL);
  S = 8;
  for (i = 0; i < N; i+=S){
    for (j = 0; j < M; j++){
      for (I = i;I < MIN(i+S,N);I++){
        B[I] = B[I] + A[I][j];
      }
    }
  }
  gettimeofday(&time_end, NULL);
  printf("used time %ld us\n", time_end.tv_usec - time_start.tv_usec);
}

//示例2：循环分块前
#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
int main() {
  const int N = 256;
  double A[N][N], B[N][N], C[N][N];
  int i, j, k;
  struct timeval  time_start, time_end;
  for (i = 0; i < N; i++) {
    for (j = 0; j < N; j++) {
      A[i][j] = rand()%10;
      B[i][j] = rand()%10;
      C[i][j] = rand()%10;
    }
  }
  gettimeofday(&time_start, NULL);
  for (i = 0; i < N; i++)
    for (j = 0; j < N; j++)
      for (k = 0; k < N; k++)
        C[i][j] = C[i][j] + A[i][k] * B[k][j];//语句S
  gettimeofday(&time_end, NULL);
  printf("used time %ld us\n", time_end.tv_usec - time_start.tv_usec);
}
//示例2：循环分块后
#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
#define MIN(i,j) (((i)<(j))?(i):(j))
int main() {
  const int N = 256;
  double A[N][N], B[N][N], C[N][N];
  int i, j, k,I,J,K;
  struct timeval  time_start, time_end;
  for (i = 0; i < N; i++) {
    for (j = 0; j < N; j++) {
      A[i][j] = rand()%10;
      B[i][j] = rand()%10;
      C[i][j] = rand()%10;
    }
  }
  int S = 4;
  gettimeofday(&time_start, NULL);
  for (i = 0; i < N; i += S)
    for (j = 0; j < N; j+=S)
      for (k = 0; k < N; k+=S)
        for (I = i; I < MIN(i + S, N); I++)
          for (J = j; J < MIN(j + S , N); J++)
            for (K = k; K < MIN(k + S, N); K++)
              C[I][J] = C[I][J] + A[I][K] * B[K][J];

  gettimeofday(&time_end, NULL);
  printf("used time %ld us\n", time_end.tv_usec - time_start.tv_usec);
}

循环分裂

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

for (i = 1; i < N; ++i) {
    Vec[i] = Vec[i] + Vec[M];
}

循环分裂

for (i = 1; i < M; ++i) {
    Vec[i] = Vec[i] + Vec[M];
}
for (i = M; i < N; ++i) {
    vec[i] = Vec[i] + Vec[M];
}

循环分裂有利性

for (i = 0; i < N; ++i) {
    tmp = a[i] - b[i];
    coff[i] = (a[i] + b[i]) * tmp;
    diff[i + M] = (c[i + M] + d[i + M]) / phi;
}

循环分裂

for (i = 0; i < N; ++i) {
    tmp = a[i] - b[i];
    coff[i] = (a[i] + b[i]) * tmp;
}
for (i = M; i < M; ++i) {
    diff[i] = (c[i] + d[i]) / phi;
}

在循环分裂之前，我们使用 -O3 选项对原始循环进行优化并不能进行向量化，而经过手工循环分裂优化后再使用-O3选项则可以进行向量化优化

e.g.

#include <stdio.h>
#include <sys/time.h>
#define N 8192 
int main() {
  int i, temp, phi;
  int M = 4096;
  int a[N], b[N], c[N], d[N], coff[N], diff[N];
  struct timeval  time_start, time_end;
  temp = 2;
  phi = 2;
  for (i = 0; i < N; i++) {
    a[i] = i;
    b[i] = i + 1;
    c[i] = i + 2;
    d[i] = i + 3;
  }
  gettimeofday(&time_start, NULL);
  for (i = 0; i < N; i++) {
    temp = a[i] - b[i];
    coff[i] = (a[i] + b[i]) * temp;
    diff[i+M] = (c[i+M] + d[i+M]) / phi;
  }
  gettimeofday(&time_end, NULL);
  printf("used time %ld us\n", time_end.tv_usec - time_start.tv_usec);
}

//循环分裂优化后
#include <stdio.h>
#include <sys/time.h>
#define N 8192
int main() {
int i, temp, phi;
int M = 4096;
    int a[N], b[N], c[N], d[N], coff[N], diff[N];
    struct timeval  time_start, time_end;
    temp = 2;
    phi = 2;
    for (i = 0; i < N; i++) {
        a[i] = i;
        b[i] = i + 1;
        c[i] = i + 2;
        d[i] = i + 3;
    }
    gettimeofday(&time_start, NULL);
    for (i = 0; i < N; i++) {
        temp = a[i] - b[i];
        coff[i] = (a[i] + b[i]) * temp;
    }
    for (i = M; i < N; i++) {
        diff[i] = (c[i] + d[i]) / phi;
    }
    gettimeofday(&time_end, NULL);
    printf("used time %ld us\n", time_end.tv_usec - time_start.tv_usec);
}

循环倾斜

循环倾斜是一种改变迭代空间形式的变换，用于挖掘循环中的并行潜能的优化方式，可以把存在的并行性用传统的并行循环的形式表示出来

for (i = 1; i < 4; ++i) {
    for (j = 1; j < 4; ++j) {
        A[i][j] = A[i][j - 1] + A[i - 1][j];
    }
}

循环倾斜

for (i = 1;i < 4; ++i) {
    for (j = i + 1; j < i + 4; ++j) {
        A[i][j - i] = A[i][j - i - 1] + A[i - 1][j - i];
    }
}

循环交换

for (j = 2; j < 8; ++j) {
    for (i = max(1, j - 4 + 1); i < min(j - 1, 4); ++i) {
        A[i][j - i] = A[i][j - i - 1] + A[i - 1][j - i];
    }
}

推广到 n

for (i = 1; i < N; ++i) {
    for (j = 1; j < N; ++j) {
        A[i][j] = A[i - 1][j] + A[i][j - 1];
    }
}

循环倾斜

for (j = 2; j < 2 * N; ++j) {
    for (i = max(1, j - M + 1); i < min(N, j); ++i) {
        A[i][j - i] = A[i - 1][j - i] + A[i][j - i - 1];
}

fetch150zy's blog

循环优化

循环优化

循环展开、循环压紧

循环展开

优点

例子

对内层循环进行循环展开

对外层循环进行循环展开

编译器中的循环展开

progma

针对向量程序的循环展开

循环压紧

循环合并

优点

例子

循环合并的合法性

循环合并的有利性

编译器中的循环合并

循环分布

优缺点

优点

缺点

应用场景

例子

效果

与循环交换优化的配合

与循环合并优化的配合

编译器中的循环分布

progma

循环交换

优点

例子

效果

循环交换的有利性

循环依赖的合法性

编译器中的循环交换

循环不变量外提

编译器中的循环不变量外提

确定循环

找出符合以下条件的代码并进行外提

对循环采用深度优先算法，进行搜索，从候选项中选出不变量

循环分段

不适用的情况

循环分块

过程

循环分裂

循环分裂有利性

循环倾斜