1
class LoopInfo:
2
    """循环信息"""
3

4
    def __init__(self, header, body, exits, parent=None):
5
        self.header = header     # 循环头基本块
6
        self.body = body         # 循环体基本块集合
7
        self.exits = exits       # 退出基本块集合
8
        self.parent = parent     # 外层循环
9
        self.depth = 1           # 嵌套深度
10
        if parent:
11
            self.depth = parent.depth + 1
12

13
    def is_innermost(self):
14
        """是否是最内层循环"""
15
        return len(self.sub_loops) == 0
16

17
def identify_loops(cfg):
18
    """识别 CFG 中的自然循环"""
19
    loops = []
20

21
    # 查找回边（header 支配 latch 的边）
22
    for block in cfg.blocks:
23
        for succ in block.successors:
24
            if dominates(succ, block, cfg):
25
                # 找到回边 block → succ
26
                loop_body = find_loop_body(succ, block, cfg)
27
                loop = LoopInfo(header=succ, body=loop_body, exits=[])
28
                loops.append(loop)
29

30
    return loops

1
// 优化前：每次迭代都有分支和计数器更新
2
for (int i = 0; i < 100; i++) {
3
    a[i] = b[i] + c[i];
4
}
5

6
// 完全展开（100 次迭代全部展开）
7
a[0] = b[0] + c[0];
8
a[1] = b[1] + c[1];
9
// ... 98 行省略 ...
10
a[99] = b[99] + c[99];
11

12
// 部分展开（4 倍展开）
13
for (int i = 0; i < 100; i += 4) {
14
    a[i]   = b[i]   + c[i];
15
    a[i+1] = b[i+1] + c[i+1];
16
    a[i+2] = b[i+2] + c[i+2];
17
    a[i+3] = b[i+3] + c[i+3];
18
}

1
class LoopUnroller:
2
    """循环展开器"""
3

4
    def unroll(self, loop, factor):
5
        """将循环展开 factor 倍"""
6
        if factor <= 1:
7
            return loop
8

9
        # 检查迭代次数是否已知
10
        trip_count = self._get_trip_count(loop)
11
        if trip_count is None:
12
            # 迭代次数未知，需要生成余数循环
13
            return self._unroll_unknown_count(loop, factor)
14

15
        if trip_count % factor != 0:
16
            # 迭代次数不是 factor 的倍数，需要处理余数
17
            return self._unroll_with_remainder(loop, factor, trip_count)
18

19
        # 完美展开
20
        return self._unroll_perfect(loop, factor)
21

22
    def _unroll_perfect(self, loop, factor):
23
        """完美展开（迭代次数是 factor 的倍数）"""
24
        new_body = []
25
        for i in range(factor):
26
            # 复制循环体，替换归纳变量
27
            for inst in loop.body_instructions:
28
                new_inst = self._rename_inst(inst, i)
29
                new_body.append(new_inst)
30

31
        # 更新循环步长
32
        loop.step *= factor
33
        loop.body_instructions = new_body
34
        return loop

1
// 标量循环
2
for (int i = 0; i < 1024; i++) {
3
    c[i] = a[i] + b[i];
4
}
5

6
// 向量化后（AVX2，8 个 float 同时处理）
7
for (int i = 0; i < 1024; i += 8) {
8
    __m256 va = _mm256_loadu_ps(&a[i]);    // 加载 8 个 float
9
    __m256 vb = _mm256_loadu_ps(&b[i]);    // 加载 8 个 float
10
    __m256 vc = _mm256_add_ps(va, vb);     // 一次加 8 个
11
    _mm256_storeu_ps(&c[i], vc);           // 存储 8 个 float
12
}

1
class DependencyAnalyzer:
2
    """循环依赖分析器"""
3

4
    def analyze(self, loop):
5
        """分析循环中的依赖关系"""
6
        deps = []
7

8
        for i, inst1 in enumerate(loop.body):
9
            for j, inst2 in enumerate(loop.body):
10
                if i >= j:
11
                    continue
12

13
                # 检查是否有依赖
14
                dep = self._check_dependency(inst1, inst2)
15
                if dep:
16
                    deps.append(dep)
17

18
        return deps
19

20
    def _check_dependency(self, inst1, inst2):
21
        """检查两条指令之间的依赖"""
22
        # 写后读（WAR）— 反依赖
23
        if inst1.is_read and inst2.is_write:
24
            if self._same_array(inst1, inst2):
25
                return Dependency('WAR', inst1, inst2)
26

27
        # 读后写（RAW）— 真依赖
28
        if inst1.is_write and inst2.is_read:
29
            if self._same_array(inst1, inst2):
30
                return Dependency('RAW', inst1, inst2)
31

32
        # 写后写（WAW）— 输出依赖
33
        if inst1.is_write and inst2.is_write:
34
            if self._same_array(inst1, inst2):
35
                return Dependency('WAW', inst1, inst2)
36

37
        return None

1
// SLP 向量化示例
2
struct Point { float x, y, z, w; };
3

4
void transform(Point* p, float s) {
5
    p->x = p->x * s;    // 这四个乘法
6
    p->y = p->y * s;    // 可以打包为
7
    p->z = p->z * s;    // 一条 SIMD 乘法
8
    p->w = p->w * s;    // 指令
9
}

1
// 优化前
2
for (int i = 0; i < n; i++) {
3
    a[i] = b[i] * (x + y);  // x + y 是循环不变量
4
}
5

6
// 优化后
7
int temp = x + y;            // 外提到循环前
8
for (int i = 0; i < n; i++) {
9
    a[i] = b[i] * temp;
10
}

1
class LICM:
2
    """循环不变量外提"""
3

4
    def hoist(self, loop):
5
        """将循环不变量外提到循环前置节点"""
6
        preheader = self._ensure_preheader(loop)
7

8
        changed = True
9
        while changed:
10
            changed = False
11
            for block in loop.body:
12
                new_insts = []
13
                for inst in block.instructions:
14
                    if self._is_loop_invariant(inst, loop):
15
                        # 外提到 preheader
16
                        preheader.instructions.append(inst)
17
                        changed = True
18
                    else:
19
                        new_insts.append(inst)
20
                block.instructions = new_insts
21

22
        return loop
23

24
    def _is_loop_invariant(self, inst, loop):
25
        """判断指令是否是循环不变量"""
26
        # 有副作用不是不变量
27
        if inst.op in ('store', 'call', 'load'):
28
            return False
29

30
        # 终止指令不是不变量
31
        if inst.op in ('br', 'ret', 'phi'):
32
            return False
33

34
        # 所有操作数都是循环不变量
35
        for operand in inst.operands:
36
            if isinstance(operand, str):
37
                # 检查操作数是否在循环外定义
38
                def_block = self._get_definition_block(operand)
39
                if def_block in loop.body:
40
                    return False
41

42
        return True
43

44
    def _ensure_preheader(self, loop):
45
        """确保循环有前置节点"""
46
        if loop.preheader:
47
            return loop.preheader
48

49
        # 创建前置节点
50
        preheader = BasicBlock(f"{loop.header.label}.preheader")
51
        # 调整 CFG 边
52
        # ...
53
        return preheader

1
// 优化前：数组索引使用乘法
2
for (int i = 0; i < n; i++) {
3
    a[i * 4] = 0;     // 每次迭代计算 i * 4
4
}
5

6
// 强度消减后：用加法替代乘法
7
for (int i = 0, j = 0; i < n; i++, j += 4) {
8
    a[j] = 0;          // j 每次加 4，无需乘法
9
}

1
class StrengthReducer:
2
    """强度消减器"""
3

4
    def reduce(self, loop):
5
        """对循环中的归纳变量进行强度消减"""
6
        # 识别归纳变量
7
        ivs = self._find_induction_vars(loop)
8

9
        for iv in ivs:
10
            # 查找 iv * constant 模式
11
            for user in iv.users:
12
                if user.op == 'mul' and user.operands[1].is_constant:
13
                    # 替换为新的归纳变量
14
                    new_iv = self._create_derived_iv(
15
                        iv, user.operands[1].value, loop
16
                    )
17
                    user.replace_with(new_iv)
18

19
        return loop
20

21
    def _find_induction_vars(self, loop):
22
        """识别归纳变量"""
23
        ivs = []
24
        for block in loop.body:
25
            for inst in block.instructions:
26
                if inst.op == 'phi':
27
                    # phi 节点可能是归纳变量
28
                    # 检查递增模式：iv = iv + step
29
                    if self._is_linear_induction(inst, loop):
30
                        ivs.append(inst)
31
        return ivs

1
// 优化前：三个归纳变量
2
for (int i = 0; i < n; i++) {
3
    int j = i * 4;        // 派生归纳变量
4
    int k = i * 4 + 1;    // 派生归纳变量
5
    a[j] = 0;
6
    b[k] = 1;
7
}
8

9
// 归纳变量简化后
10
for (int i = 0; i < n * 4; i += 4) {
11
    a[i] = 0;
12
    b[i + 1] = 1;
13
}

1
// 原始代码
2
void add_arrays(float* a, float* b, float* c, int n, float scale) {
3
    for (int i = 0; i < n; i++) {
4
        c[i] = (a[i] + b[i]) * scale;
5
    }
6
}

1
# 查看不同优化级别的汇编输出
2
clang -O0 -S add_arrays.c   # 无优化
3
clang -O1 -S add_arrays.c   # 基本优化
4
clang -O2 -S add_arrays.c   # 标准优化（包含向量化）
5
clang -O3 -S add_arrays.c   # 激进优化（更多展开）

1
// 1. 循环携带依赖
2
for (int i = 1; i < n; i++) {
3
    a[i] = a[i-1] + 1;    // 依赖前一次迭代
4
}
5

6
// 2. 未知指针别名
7
void add(float* a, float* b, float* c, int n) {
8
    for (int i = 0; i < n; i++) {
9
        c[i] = a[i] + b[i];  // 如果 c 和 a/b 重叠呢？
10
    }
11
}
12

13
// 3. 循环内分支
14
for (int i = 0; i < n; i++) {
15
    if (a[i] > 0) {          // 分支难以向量化
16
        b[i] = a[i];
17
    }
18
}
19

20
// 解决方案
21
void add_restrict(float* __restrict__ a,
22
                   float* __restrict__ b,
23
                   float* __restrict__ c, int n) {
24
    for (int i = 0; i < n; i++) {
25
        c[i] = a[i] + b[i];  // restrict 保证不重叠
26
    }
27
}

1
cat > vec_test.c << 'EOF'
2
void add(float* a, float* b, float* c, int n) {
3
    for (int i = 0; i < n; i++) {
4
        c[i] = a[i] + b[i];
5
    }
6
}
7
EOF
8

9
# 查看向量化报告
10
clang -O2 -Rpass=loop-vectorize vec_test.c -c 2>&1
11
# 输出：vec_test.c:3:5: remark: vectorized loop (vectorization width: 8, interleaved count: 4)
12

13
# 查看汇编中的 SIMD 指令
14
clang -O2 -S vec_test.c -o vec_test.s
15
grep -E "(vmov|vadd|vld|vst)" vec_test.s

1
cat > restrict_test.c << 'EOF'
2
// 无 restrict
3
void add1(float* a, float* b, float* c, int n) {
4
    for (int i = 0; i < n; i++) c[i] = a[i] + b[i];
5
}
6

7
// 有 restrict
8
void add2(float* __restrict__ a, float* __restrict__ b,
9
          float* __restrict__ c, int n) {
10
    for (int i = 0; i < n; i++) c[i] = a[i] + b[i];
11
}
12
EOF
13

14
clang -O2 -S restrict_test.c -o restrict_test.s
15
diff <(grep -A5 "add1:" restrict_test.s) <(grep -A5 "add2:" restrict_test.s)

1
#include <immintrin.h>
2

3
// 自动向量化
4
void auto_vec(float* a, float* b, float* c, int n) {
5
    for (int i = 0; i < n; i++) {
6
        c[i] = a[i] + b[i];
7
    }
8
}
9

10
// 手动向量化
11
void manual_vec(float* a, float* b, float* c, int n) {
12
    int i = 0;
13
    for (; i + 7 < n; i += 8) {
14
        __m256 va = _mm256_loadu_ps(&a[i]);
15
        __m256 vb = _mm256_loadu_ps(&b[i]);
16
        __m256 vc = _mm256_add_ps(va, vb);
17
        _mm256_storeu_ps(&c[i], vc);
18
    }
19
    for (; i < n; i++) {
20
        c[i] = a[i] + b[i];
21
    }
22
}