andreww's blog

在高性能计算中，矩阵乘法是一个非常基础且重要的操作。一个看似简单的实现，背后却可能蕴含着编译器大量的分析和优化工作。本文将以一个基础的矩阵乘法C语言代码为例，探讨编译器是如何通过SCEV (Scalar Evolution) 表达式来分析循环中的内存访问模式，并在此基础上执行循环展开 (Loop Unrolling) 等优化，从而大幅提升程序性能。

1. 矩阵乘法C代码·

首先，我们来看一个标准的 N × N 矩阵乘法实现 C = A * B。为了简化，我们使用一维数组来模拟二维矩阵，其中元素 M[i][j] 通过 M[i * N + j] 来访问。

1
2
3
4
5
6
7
8
9
10
11
12

void MatrixMul(unsigned int N, int *C, int *A, int *B) {
  unsigned int i, j, k;

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

这段代码通过三层嵌套循环，精确地实现了矩阵乘法的数学定义。虽然功能正确，但其性能在不经过优化的情况下通常不理想。接下来，我们将探讨编译器如何“读懂”并优化这段代码。

Posts in This Series·

1. Understanding In-Order Pipelines and Pipeline Stalls
2. What We Need in a Scheduling Model
3. Scheduling Model: GCC and LLVM Perspectives
4. Tuning Your Scheduling Model for Better Performance(TODO)

A Simple Scheduling Model·

在上一篇中我们提到，如果调度器想要通过指令重排布来解决流水线中的三大问题——发射阻塞、资源冲突以及数据冲突，那么它就需要知道一些流水线的硬件信息。

为了避免发射阻塞，调度器需要知道流水线一次能发射多少条指令，也就是它有多少条发射通路。另外，每条指令可能会被解码成多个微操作，也需要考虑进去。

对应我们结构体中的字段是：

• Pipeline.issue_width
• Ins.num_micro_ops

而要避免资源冲突，调度器需要知道：

• 流水线有哪些功能单元
• 每种功能单元有多少个
• 每条指令会用到哪些功能单元，以及需要使用多久

Posts in This Series·

1. Understanding In-Order Pipelines and Pipeline Stalls
2. What We Need in a Scheduling Model
3. Scheduling Model: GCC and LLVM Perspectives
4. Tuning Your Scheduling Model for Better Performance(TODO)

Recap·

第一篇文章中，我们已经说过，调度器主要是用来解决三类冲突，

• 汇编解码出的微操作数过多，无法在一个周期内发射出去所导致的发射阻塞
• 指令争夺相同运算单元导致流水线暂停的结构冲突
• 指令间存在寄存器读写依赖导致流水线暂停的数据冲突

这一节我们将详细展开，并且说明如果我们想要解决这些导致流水线暂停的冲突，我们需要哪些具体的流水线信息。

Model it·

假设我们现在不知道调度模型需要包含什么信息，目前先构建一个空的结构体定义struct Pipeline，后面我们将逐渐完善这个结构体内的变量定义。

这个调度模型定义，即不是 LLVM 中的用法，也不是 gcc 中的用法，在这里是用更简单的方式表述，后面我们才会延伸到 LLVM 和 gcc 中的用法。

1
2
3
4

struct Pipeline {
  // Contains nothing.
  // We don't yet know what we need to model a pipeline.
};

Posts in This Series·

1. Understanding In-Order Pipelines and Pipeline Stalls
2. What We Need in a Scheduling Model
3. Scheduling Model: GCC and LLVM Perspectives
4. Tuning Your Scheduling Model for Better Performance(TODO)

Extended in-order pipeline·

Extended EX stage pipeline·

我不想在这里讨论基本的五级顺序流水线概念，你可以在任何一本介绍计算机体系结构的书上找到相关的内容，所以我会假设你已经了解基本的顺序流水线知识、流水线冒险（结构冒险、数据冒险、控制冒险）、数据前推，如果你对提到的任何关键词有疑问，请先补充相关的知识 😉

flowchart LR
    IF[IF]
    ID[ID]
    EX[EX]
    MEM[MEM]
    WB[WB]

    IF --> ID
    ID --> EX
    EX --> MEM
    MEM --> WB

如上图，基本的五级流水线（取指，译码，执行，访存，写回）由于做了简化，并没有暴露其中的细节。从图中看起来所有的执行单元被抽象成一个 EX stage，而真实的 CPU 流水线不仅要处理基本的整数运算，还需要处理浮点运算以及它们各自的加减乘除，所以一个完整的 EX stage 至少会包括 ALU 单元运算，乘法除法器运算单元，浮点加减运算单元，浮点乘除运算单元。

假设我们有一个可以处理各种整数运算，浮点加减乘除运算的流水线，从黑盒子的角度来看，它可能长成下图这个样子。

这是我的第一篇博客，作为“程序员”的我，理应叫他"Hello,World!" (其实我不太喜欢“程序员”这个称呼，因为总感觉它带着一些刻板印象在里面。)

Introduce myself·

第一篇也也不知道说些什么，就随便唠叨唠叨了。

那就先介绍一下自己。个人目前是在武汉做LLVM编译器开发，目前主要的工作是做编译优化。当初因为很喜欢计算机底层知识，所以选择了这个方向。可能由于国内做编译器的很少，所以同行竞争压力比较小，加上我们的老板和总监之前都是常年在国外创业和工作，所以工作氛围很轻松，而且工作时间是真的弹性965。

但是工作压力还是有的，主要是因为编译器软件过于庞大，计算机底层知识牵涉过多，所以有时候举步维艰。所以这也是我花费周末时间搭这个博客的一点原因，想借助这个博客来记录自己的学习。当然其实更多的是兴趣使然，不然我是不可能凌晨熬夜还在看这个前端代码的。

工作五个月，从最开始接触linux指令，跑测试，整理数据，到开始做code size相关的优化（主要是outline相关），现在由于公司要用picolibc库开发，所以最近都在和picolibc打交道，所以也接触到了很多链接器相关的东西。我的工作其实说起来很无聊，就是测试，对比，阅读LLVM源码，在源码基础上做优化，但我很喜欢我的工作，可能本身对计算机底层的兴趣使我不会那么厌烦。工作中有很多很难的东西，比如要去阅读上千上万行的源码，虽然LLVM已经有十多年的时间了，但是能参考的资料真的不是很多，而且几乎没有中文，只能硬着头皮去看英文文档。遇到特别难的东西，其实真的也会很暴躁。😦

结果就是，在技术方面，我真的成长了许多，但现在仍然还是个菜鸡。

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.

Quick Start·

Create a new post·

1

$ hexo new "My New Post"

More info: Writing

Run server·

1

$ hexo server

More info: Server

Generate static files·

1

$ hexo generate

More info: Generating

Deploy to remote sites·

1

$ hexo deploy

More info: Deployment