优化手段 (lec3)

循环向量化

充要条件:

最内层循环

1. S < T: 不存在方向为 (0, 0, ..., 1) 的 T $\delta$ S 依赖

2. S = T: 不存在方向为 (0, 0, ..., 1) 的 T $\delta^f$ S 数据流依赖

   // 以下不行，因为有 S f S, 方向为 (1) 的依赖:
   for i in 1..N {
   	A[i] = A[i - 1];
   }
   
   // 以下可以:
   for i in 0..(N - 1) {
   	A[i] = A[i + 1];
   }
   

循环并行化

充要条件:

第 k 层循环可以并行化 ↔ 不存在方向为 (0, 0, ..., 1, *, *, ..., *) 的依赖（1 在第 k 层）

循环分布

画凝聚图（强连通分量）

在有向图的数学理论中，如果一个图的每一个顶点都可从该图其他任意一点到达，则称该图是强连通的。

语句重排

帮助向量化，看起来是得凭感觉来

循环置换（交换）

充要条件:

方向向量 * 置换矩阵得到的向量为正

置换矩阵：i → $\pi(i)$ 为第 i 层循环被置换到第 $\pi(i)$ 层循环，则 P[i][$\pi(i)$] = 1，其他值为 0

循环逆转

逆转后方向向量需要为正