:brain: :brain: :brain: :brain: :brain:

AI 编译器原理汇总

很大程度上讲 AI compiler 其实就是把手动优化的经验和成果拿过来变成自动化的过程。

block_ptr 的提出是想 lowering 的时候，丢掉了这个计算的类型，即它是 FlexAttention 还是 GEMM，需要这个信息来决定如何优化。言外之意，不同的程序有各自最优的优化方式。所以单单问我的一个 dot 如何优化，这是不合理的。dot 如何优化取决于 dot 所在的程序时什么样的。什么样的程序有什么样的优化方式。

再扩展一下就是说，要做优化，你需要了解你的优化对象, 以及对象所执行的平台。

Pass 的执行顺序如何决定先做什么后做什么？

某些 Pass 可能依赖于其他 Pass 的结果；某些 Pass 可能会为后续的 Pass 创建更多的优化机会；编译器开发者通常会根据经验和启发式规则来安排 Pass 的顺序。这可能涉及到大量的实验和性能测试，以找到最佳的顺序。

函数内联

函数内联（Inlining）是一种编译器优化技术，它将函数调用替换为函数体本身的内容。这样做的好处是可以消除函数调用的开销，并且在某些情况下，允许编译器进行更进一步的优化，因为它可以看到函数调用的上下文。

Intra-procedural

（函数内部的）指的是在单个函数或过程的范围内进行的分析或优化，而不跨越函数边界。属于编译器设计和程序分析。

Inter-procedural

（函数间的）分析或优化会考虑多个函数之间的相互作用。属于编译器设计和程序分析。

transitive lowering

是指将操作从一个高级别方言逐步降低到一个低级别方言的过程，而不是直接从高级别方言生成目标方言（如LLVM方言）的操作。这种逐步降低的方法允许开发者将复杂的降低过程分解成一系列更简单、更可管理的步骤。“transitive lowering” 的关键思想是，你可以将一个操作先降低到一个中间方言，然后再从这个中间方言降低到最终的目标方言。这样做的好处是每个降低步骤可以专注于处理一小部分转换逻辑，这使得整个降低过程更加模块化和可维护。它是 mlir 中的编程模型。

为什么 MLIR 的 SSA 对于生成正确和高效的代码至关重要

在编译器设计中，SSA（Static Single Assignment）形式是一种中间表示（IR），其中每个变量只被赋值一次，并且每个变量都是局部定义的。这种形式有几个关键优势，使其在 MLIR 中特别重要：

简化数据流分析：在 SSA 形式中，每个变量的定义点只有一个，这使得编译器能够更容易地进行数据流分析，例如确定变量的生命周期、寻找变量的使用点、进行死代码消除等。
便于优化： SSA 形式简化了许多优化技术的实现，如常量传播、公共子表达式消除、循环不变代码外提等。由于每个变量只有一个定义点，优化算法可以更直接地推断出变量的值和它们之间的关系。
消除别名问题：在非 SSA 形式中，由于变量可以在多个地方被赋值，编译器必须处理复杂的别名分析问题，以确定不同的变量名是否引用相同的内存位置。SSA 通过确保每个变量只被赋值一次，减少了这种复杂性。
提高代码生成质量： SSA 形式有助于生成更高效的机器代码，因为它提供了更清晰的信息来指导寄存器分配【见：编译器是如何根据代码-进行-寄存器分配的】和指令调度等底层代码生成阶段。【编译器通过分析代码的控制流和数据流，构建依赖图，然后使用各种算法在满足依赖关系和资源约束的条件下，重新排序指令，以最大化指令级并行性，最终生成更高效的目标代码。】
便于并行化： SSA 形式明确了变量的定义和使用，这有助于识别可以并行执行的操作，从而为自动并行化提供了基础。

编译器是如何根据代码进行寄存器分配的？

编译器进行寄存器分配是一个复杂的过程，目标是将程序中的变量尽可能地存储在CPU寄存器中，以提高程序执行速度。因为寄存器的访问速度远快于内存。这通常涉及多个步骤和不同的算法，具体方法取决于编译器的设计和优化级别。以下是一些关键步骤和常用的算法：

活性分析 (Liveness Analysis):

这是寄存器分配的第一步，它确定每个变量在程序的哪些部分是“活跃的”（即正在使用或可能被使用）。活跃的变量必须存储在寄存器或内存中。编译器使用数据流分析技术来计算每个变量的活跃区间（live range），即变量从被定义到最后一次使用之间的代码段。

干扰图构建 (Interference Graph Construction):

基于活性分析的结果，编译器构建一个干扰图 (interference graph)。图中的每个节点代表一个变量的活跃区间，如果两个变量的活跃区间重叠，且它们不能同时存储在同一个寄存器中（例如，它们同时被使用），则在它们之间添加一条边。这表示这两个变量之间存在干扰。

图着色 (Graph Coloring):

这是寄存器分配的核心步骤。编译器尝试将干扰图中的每个节点着色，使得相邻节点（即存在干扰的变量）具有不同的颜色。 每种颜色代表一个寄存器。如果图可以被 k 种颜色着色，则意味着所有变量都可以分配到 k 个寄存器中。如果图无法被 k 种颜色着色（其中 k 是可用寄存器的数量），则需要进行溢出 (spilling)。

溢出 (Spilling):

如果图无法用可用寄存器的数量进行着色，编译器必须将一些变量溢出到内存中。这会降低性能，因为内存访问速度较慢。编译器会选择溢出对性能影响最小的变量，通常是那些活跃区间较短或使用频率较低的变量。溢出策略的选择对性能有很大影响。

代码生成 (Code Generation):

最后，编译器根据寄存器分配的结果生成目标代码。它将变量分配到相应的寄存器中，并生成相应的指令。

静态单赋值 (SSA) 形式的代码对编译器寄存器分配有益，主要是因为它简化了活跃性分析和干扰图的构建，从而使寄存器分配算法更容易找到最优解或接近最优解。虽然 SSA 本身并不直接进行寄存器分配，但它为寄存器分配算法创造了一个更易于处理的环境，从而间接地提高了寄存器分配的质量。

编译器是如何根据代码进行指令调度的？

编译器进行指令调度是一个复杂的过程，目标是最大化指令级并行性，从而提高程序执行效率。它并非简单的重新排序指令，而是要遵守数据依赖性和控制依赖性等约束条件。以下步骤概述了编译器如何进行指令调度：

代码分析:

语法分析和语义分析: 编译器首先解析源代码，构建抽象语法树 (AST)，并进行语义检查，确保代码的正确性。
控制流分析: 确定程序的控制流，识别基本块、循环、分支等结构。这对于全局调度至关重要，因为跨基本块的指令调度需要理解控制流。
数据流分析: 分析变量的定义、使用和生命周期，识别数据依赖关系。这包括读后写 (RAW)、写后读 (WAR) 和写后写 (WAW) 三种依赖关系。数据依赖关系决定了指令的执行顺序，不能随意打乱。

依赖图构建:

基于数据流分析的结果，编译器构建一个依赖图 (DAG)。图中的节点代表指令，边代表指令之间的依赖关系。边上通常标注依赖的延迟 (latency)，表示指令之间必须保持的最小时间间隔。【计算指令间的延迟时间依赖于目标处理器的微架构细节，并且通常需要结合实验测量和处理器手册中的信息，并结合多种工具的使用】。

指令调度算法:

编译器使用各种算法来进行指令调度，目标是在满足依赖关系的约束下，尽可能地并行执行指令。常用的算法包括：

列表调度 (List Scheduling): 一种贪婪算法，每次选择一个没有前驱节点（或所有前驱节点都已完成）的节点进行调度。选择策略可能考虑资源冲突、关键路径等因素。
优先级调度: 为每个指令分配一个优先级，然后按照优先级顺序进行调度。优先级可以基于多种因素，例如指令的执行时间、关键路径上的位置等。
全局调度: 可以跨越基本块边界进行指令调度，这需要更复杂的控制流分析和更高级的算法。全局调度可以获得更高的并行性，但实现难度也更大。
局部调度: 只在基本块内进行指令调度，相对简单，但并行性可能不如全局调度高。
Modulo Scheduling: 一种用于软件流水线的算法，通过重叠不同迭代的指令来提高循环的性能。
Trace Scheduling: 一种全局调度算法，它选择程序中最常执行的路径（trace）进行优化。

资源约束:

编译器必须考虑目标机器的资源约束，例如寄存器数量、功能单元数量等。如果调度后的指令超过了可用资源，编译器可能需要进行寄存器分配或代码重排来解决冲突。这可能导致一些指令被延迟执行，从而降低并行性。

代码生成:

最后，编译器根据调度后的指令序列生成目标机器代码。

简而言之: 编译器通过分析代码的控制流和数据流，构建依赖图，然后使用各种算法在满足依赖关系和资源约束的条件下，重新排序指令(包括了根据指令之间的依赖关系，进行乱序执行)，以最大化指令级并行性，最终生成更高效的目标代码。不同的编译器和不同的优化级别会采用不同的调度算法和策略。

SSA 形式的代码对于编译器进行指令调度有显著的益处，主要是因为它消除了许多数据依赖关系的歧义，使得编译器更容易识别哪些指令可以并行执行。具体讲：

在 SSA 形式中，每个变量只被赋值一次。这使得编译器更容易追踪变量的值，从而准确地识别数据依赖关系。传统的代码中，同一个变量可能在多个地方被赋值，这使得数据依赖关系变得模糊，增加了编译器分析的复杂性。 SSA 消除了这种歧义，简化了依赖分析。
SSA 形式通过消除变量的重复赋值，简化了别名分析，从而减少了编译器需要考虑的依赖关系。
SSA 形式使得活跃变量分析更加精确，因为每个变量的定义和使用都清晰可见。这有助于编译器进行更好的寄存器分配和指令调度，因为编译器可以更准确地知道哪些变量需要保存在寄存器中。
SSA 使得变量的定义和使用更加清晰，编译器更容易识别出可以优化的机会。
SSA 形式简化了数据依赖关系的分析，编译器可以更容易地应用更复杂的指令调度算法，例如全局调度算法。这些算法可以识别出更多可以并行执行的指令，从而提高程序的性能。

为更有效的指令调度和全局优化创造了条件。

规约计算确保轴是非负的并且按升序排列，这是有利于编译优化的

规范化 canonical-ize (简洁化)

是一个优化过程，它应用一系列的重写规则来简化操作和改进 IR 的表示。规范化可以帮助消除冗余操作、简化复杂表达式、提高代码的可读性和性能。每个方言（Dialect）可以定义自己的规范化模式（patterns），但有一些常见的规范化方法在多个方言中都可能使用：

算术简化：简化算术表达式，例如将 x + 0 替换为 x，或者将 x * 1 替换为 x。
常量折叠（Constant Folding）：计算编译时已知的常量表达式，例如将 2 + 3 替换为 5。
死代码消除（Dead Code Elimination, DCE）：移除不会影响程序结果的操作，例如未使用的变量或操作。
操作合并（Operation Merging）：合并连续的操作，例如两个连续的转置操作可以被消除。
强度削减（Strength Reduction）：用成本更低的操作替换更昂贵的操作，例如将乘法替换为加法。
循环不变代码外提（Loop Invariant Code Motion）：将循环中不变的计算移动到循环外部。
条件简化：简化条件表达式，例如将 if (true) 替换为执行分支的内容。
公共子表达式消除（Common Subexpression Elimination, CSE）：识别并消除在多个地方重复计算的表达式。
形状和类型推导（Shape and Type Inference）：推导操作的形状和类型，以便可以应用更多的优化。
内存访问优化：优化内存访问模式，例如合并多个小的内存访问为一个大的访问。

对于的定 Dialect 的 op，实现其 getCanonicalizationPatterns 方法，MLIR 提供了 PatternRewriter 类和一套重写模式 infra。开发者可以定义自己的 RewritePattern 子类，并在其中实现特定的规范化逻辑。然后，这些模式可以注册到方言的规范化通道中，MLIR 的优化引擎会自动应用这些模式来转换和优化 IR。

对一个 Dialect 的 Analysis

Analysis 不改变 IR 的表达，它是编译优化和转换的基础，它提供了关于程序行为的信息，这些信息可以用来指导后续的优化决策。对一个 Dialect 的常用分析包括：

Dependency Analysis
Alias Analysis
Shape and Size Inference
Cost Model Analysis
Reachability Analysis
Bounds Checking Analysis …

每个 Dialect 都可能有其特定的分析需求，这取决于它的操作和语义。开发者可以为自定义的 Dialect 实现特定的分析逻辑。这些分析通常以 Pass 的形式实现，可以在 MLIR 的 Pass 管理器中注册和运行。

属于编译器优化阶段的一部分，或者更准确地说，是优化决策过程中的一个重要组成部分。

Analysis Pass

它主要负责对中间表示（IR）进行分析，以便后续的优化和转换 Pass 能够更有效地工作。Analysis Pass 并不直接修改 IR，而是收集有关 IR 的信息，如数据流、控制流、依赖关系等，这些信息对于后续的编译优化至关重要。

基于内存的操作 VS 基于 SSA 值的操作

内存访问:

基于内存: 频繁访问内存基于SSA: 减少内存访问, 主要在寄存器中操作

变量赋值:

基于内存: 变量可多次赋值基于SSA: 每个变量只赋值一次

优化潜力:

基于内存: 优化受限于内存别名分析基于SSA: 便于进行多种编译优化

数据流分析:

基于内存: 分析复杂,需考虑内存状态基于SSA: 简化了数据流分析

代码表示:

基于内存: 更接近机器级表示基于SSA: 更适合高级优化

这个转换为 SSA 的优化 Pass 需要在编译优化的前期执行，为后续提供更多的优化可能。

arith::extf & arith::truncf

arith::extf（Extend Float）: 这个操作用于将浮点数从一种精度扩展到更高的精度。 arith::truncf（Truncate Float）: 这个操作用于将浮点数从一种精度缩减到更低的精度。

Decompose aggregated operations 在 AI 编译器中是什么意思

分解聚合操作通常指的是将复杂的操作分解为更简单、更基本的操作的过程。这种分解有助于优化编译过程，提高最终生成代码的性能，以及增强跨不同硬件和执行环境的可移植性。聚合操作是指那些执行多个功能或在单个操作中封装了多个步骤的操作。例如，在深度学习模型中，一个聚合操作可能是执行卷积、批量归一化和激活函数的复合层。在编译器中，这样的聚合操作可能不容易直接映射到硬件指令，或者可能不是所有目标硬件都能高效执行。

分解聚合操作的目的是将这些复杂的操作拆分成更小的、更标准化的操作，这些操作可以直接映射到硬件指令或者更容易进行进一步的优化。例如，一个执行多个数学运算的聚合操作可以被分解为单独的加法、乘法和除法操作。

在 MLIR 中，分解聚合操作通常是通过编写特定的 Pass 来实现的，这些 Pass 会识别聚合操作并将它们替换为一系列基本操作。这个过程可能涉及到模式匹配、重写规则和类型转换。

Fold tensor operation 作用

%0 = "constant"() {value = dense<1.0> : tensor<2x2xf32>} : () -> tensor<2x2xf32>
%1 = "constant"() {value = dense<2.0> : tensor<2x2xf32>} : () -> tensor<2x2xf32>
%2 = "arith.add"(%0, %1) : (tensor<2x2xf32>, tensor<2x2xf32>) -> tensor<2x2xf32>

在这个例子中，我们有两个常量操作，分别生成了两个值为 1.0 和 2.0 的 2x2 浮点张量。接着，我们有一个 arith.add 操作，它将这两个张量相加。由于 %0 和 %1 都是常量，我们可以在编译时计算 %2 的值。这个折叠过程可以由 MLIR 的优化 Pass 自动完成，或者你可以手动将上述代码折叠为：

%2 = "constant"() {value = dense<3.0> : tensor<2x2xf32>} : () -> tensor<2x2xf32>

现在，%2 直接是一个值为 3.0 的常量张量，这样我们就消除了运行时的加法计算。

这个Pass涉及到模式匹配和重写规则，

:brain: Pass 的实现，就是灵活使用 IR 的遍历与修改，这个 Pass 会做遍历操作，寻找可以折叠的常量操作，并用预计算的结果替换原始操作 :brain:

-loop-invariant-code-motion

Loop Invariant Code Motion (LICM) 是一种优化技术。LICM 的核心思想是将循环不变代码（loop-invariant code）移动到循环外部。循环不变代码是指在循环的每次迭代中都不会改变的代码，因此没有必要在每次迭代时都重新计算。它减少了循环内部的工作量，减少计算次数，减少循环开销，从而减少了程序执行的总时间。并且使进一步优化成为可能。

在 MLIR 中，LICM 可以作为一个 Pass 实现，它会分析循环结构，识别循环不变的操作，并将它们移动到适当的位置。

实例：

for i in range(0, n):
    x = a * b
    y[i] = x + i

应用LICM后

x = a * b
for i in range(0, n):
    y[i] = x + i

-loop-invariant-subset-hoisting mlir

与 LICM 类似，将循环中的不变子集操作（subset ops）移动到循环外部。

Bufferization

从高级别的抽象数据结构转换为低级别的**内存缓冲区（buffer）**表示的过程. 实例：

我有一个 tensor 加法计算：

%result = "toy.add"(%tensor1, %tensor2) : (tensor<2x2xf32>, tensor<2x2xf32>) -> tensor<2x2xf32>

在 bufferization 之后，变为如下计算:

// 分配内存缓冲区
%buffer1 = memref.alloc() : memref<2x2xf32>
%buffer2 = memref.alloc() : memref<2x2xf32>
%result_buffer = memref.alloc() : memref<2x2xf32>

// 将张量数据复制到缓冲区
"toy.tensor_to_memref"(%tensor1, %buffer1) : (tensor<2x2xf32>, memref<2x2xf32>) -> ()
"toy.tensor_to_memref"(%tensor2, %buffer2) : (tensor<2x2xf32>, memref<2x2xf32>) -> ()

// 执行缓冲区加法
"toy.buffer_add"(%buffer1, %buffer2, %result_buffer) : (memref<2x2xf32>, memref<2x2xf32>, memref<2x2xf32>) -> ()

// 将结果缓冲区转换回张量
%result = "toy.memref_to_tensor"(%result_buffer) : (memref<2x2xf32>) -> tensor<2x2xf32>

上述转换（从高级抽象到低级内存操作）过程发生在编译时，在运行时，直接操作内存缓冲区，而不是通过高级抽象层。

补：内存缓冲区

是分配在主内存中的一块连续内存区域，它充当缓存的角色，用于缓冲数据传输，以应对不同设备或进程之间速度差异。与CPU缓存不同，内存缓冲区由程序直接控制，可以被编程，程序员可以对其进行读写操作，管理其生命周期。它本质上是内存，但其用途和管理方式使其也具有缓存的特性。

内存缓冲区是一个更通用的概念，指的是一块连续的内存区域，用于临时存储数据。并不是一个物理概念。

-eliminate-empty-tensors

这个 Pass 的作用是识别和移除那些不包含任何元素的张量。这些张量通常被称为“空张量”（empty tensors），它们的尺寸（dimensions）中至少有一个是零。由于空张量不包含任何实际的数据，因此在内存中为它们分配缓冲区是不必要的，也是一种资源浪费。

-one-shot-bufferize

是将整个 module 做一次 bufferize，通过一次性转换，减少中间状态和临时数据结构的创建。

-mem2reg

主要用于将内存操作转换为基于 SSA 值的操作。给出实例，应用这个 Pass 前后 mlir：

// 返回两个参数中数值较大的一个
func @example(%arg0: i32, %arg1: i32) -> i32 {
  %c0 = arith.constant 0 : i32
  // 在栈上分配一个32位整数的内存,并将指向该内存的引用存储在%alloca中
  %alloca = memref.alloca() : memref<i32>
  // 将常量0(%c0)存储到%alloca指向的内存中
  memref.store %c0, %alloca[] : memref<i32>

  // 比较%arg0和%arg1,检查是否%arg0 > %arg1, sgt 是谓词 "signed greater than" 的缩写，表示有符号整数的大于比较
  // 结果(布尔值)存储在%cond中
  %cond = arith.cmpi sgt, %arg0, %arg1 : i32
  // 条件分支:如果%cond为真,跳转到^bb1,否则跳转到^bb2
  cond_br %cond, ^bb1, ^bb2

// 定义一个基本块 ^bb1
^bb1:
  // 将arg0 中存储的值 放进 alloca 指向的内存中
  memref.store %arg0, %alloca[] : memref<i32>
  br ^bb3 // 跳转到 基本块

// 定义第二个个基本块 ^bb2
^bb2:
  memref.store %arg1, %alloca[] : memref<i32>
  br ^bb3

// 定义第三个基本块 ^bb3
^bb3:
  // 将alloca 中的值加载到 result中
  %result = memref.load %alloca[] : memref<i32>
  return %result : i32
}

应用这个Pass之后：

func @example(%arg0: i32, %arg1: i32) -> i32 {
  %c0 = arith.constant 0 : i32

  %cond = arith.cmpi sgt, %arg0, %arg1 : i32
  cond_br %cond, ^bb1(%arg0 : i32), ^bb2(%arg1 : i32)

^bb1(%1: i32):
  br ^bb3(%1 : i32)

^bb2(%2: i32):
  br ^bb3(%2 : i32)

^bb3(%result: i32):
  return %result : i32
}

主要变化说明:

移除了 %alloca = memref.alloca() 操作,不再需要分配内存。
删除了所有的 memref.store 和 memref.load 操作。
在条件分支时, 直接将值作为参数传递给目标基本块。
引入了新的块参数来表示不同路径上的值。例如, ^bb3 现在有一个参数 %result。
最终的 return 语句直接使用 %result, 而不是从内存中加载。

这个转换将基于内存的操作转换为了基于 SSA 值的操作,消除了不必要的内存访问,可能会提高代码的执行效率。

Reduction Sinking

它涉及到将归约操作（reduction operation）从循环中移出来，以减少对共享资源的争用，提高并行性和执行效率。在没有优化的情况下，规约操作是在循环内部进行的，这导致了对该变量的频繁读写，尤其是在多线程环境中。其中会使用到锁来保证线程安全。应用这个优化之后，每次迭代只会读写局部规约变量。避免了上述的问题。

// 优化前
int sum = 0;
for (int i = 0; i < N; ++i) {
    sum += array[i]; // 归约操作在循环内部
}

// 优化后
int sum = 0;
for (int i = 0; i < N; ++i) {
    local_sum += array[i]; // 局部归约变量
}
sum += local_sum; // 在循环外部合并结果

Loop Interchange [访问模式] ***

它涉及改变嵌套循环的顺序。这种优化的目的是为了提高内存访问的局部性，从而减少缓存未命中（cache misses）。知识点：Cache Lines，CPU缓存是以缓存行（cache lines）为单位组织的，当程序访问一个内存地址时，整个缓存行都会被加载到缓存中。因此，如果程序能够连续访问存储在相邻内存地址上的数据，就可以充分利用缓存行（按照硬件的喜好来设计程序），减少对主内存的访问，从而提高性能。[空间局部性原理]

在处理多维数组时，循环的顺序对内存访问模式有很大影响。例如，考虑一个二维数组 A[i][j]，在C语言中，数组是按行优先存储的，这意味着 A[i][j] 中的 j 索引变化得更快时，内存访问是连续的。如果外层循环是 i，内层循环是 j，那么内层循环将连续访问内存，这是最佳的访问模式。如果编译器检测到内层循环的索引不是连续访问内存，它们可能会交换循环的顺序，以确保内层循环对数组的访问是连续的。

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

// 应用优化之后
for (int j = 0; j < M; j++) {
    for (int i = 0; i < N; i++) {
        A[j][i] = A[j][i] + B[j][i];
    }
}

register spill

这个行为发生在编译器试图将程序中的变量分配到 CPU 寄存器时，但可用的寄存器数量不足以容纳所有需要的变量。当寄存器用完时，编译器必须将一些变量的值存储到内存中（通常是栈中），以便腾出寄存器给其他变量使用。这种将变量从寄存器移到内存的过程就称为 register spill。

性能下降：将变量从寄存器移到内存（栈）会增加内存访问的开销，因为内存访问速度通常比寄存器访问速度慢得多。这会导致程序性能下降。
代码复杂性增加：编译器需要生成额外的指令来处理 register spill，这会增加生成代码的复杂性和长度。

译器在处理 register spill 时，会进行以下操作：

寄存器分配：编译器首先尝试将所有变量分配到寄存器中。如果寄存器数量不足，编译器会选择一些变量进行溢出。
溢出变量选择：编译器使用寄存器分配算法（如图着色算法线性扫描算法）来选择哪些变量需要溢出到内存。通常，编译器会选择那些使用频率较低或生命周期较短的变量进行溢出。
生成溢出代码：编译器生成将变量值存储到内存（栈）和从内存加载回寄存器的指令。这些指令会在变量需要使用时插入到代码中。

scratch space

一种临时存储区域，用于存储中间结果或临时数据。Scratch Space 在不同上下文中的应用

编译器和寄存器分配：在编译器优化过程中，寄存器分配是一个关键步骤。由于寄存器数量有限，当寄存器用完时，编译器会将一些变量的值存储到 scratch space 中，这个过程称为 register spill。Scratch space 通常位于栈中或内存的其他区域。
GPU 编程：在 GPU 编程中，scratch space 通常用于存储线程的私有数据或中间计算结果。由于 GPU 的寄存器数量有限，scratch space 可以帮助缓解寄存器压力。
操作系统和内存管理：操作系统在进行内存管理时，也会使用 scratch space 来存储临时数据。例如，在分页系统中，操作系统可能会使用 scratch space 来存储页表或其他临时数据。

======================================================================================

传统编译器

给出算法将表达式树转换为DAG

表达式树

多面体优化框架

多面体模型是一种用于程序分析和优化的数学模型,主要用于优化循环结构。它的核心思想是将程序的执行过程抽象为几何空间中的点和多面体。

GCC/GRAPHITE:
GRAPHITE是GNU编译器集合(GCC)中的多面体优化框架。它允许GCC对循环和数组访问进行高级优化。
LLVM/Polly:
Polly是LLVM编译器基础设施中的多面体优化框架。它使用多面体模型来优化循环和数据局部性。
MLIR/Polygeist:
Polygeist是MLIR(Multi-Level Intermediate Representation)生态系统中的一个项目。它是一个C/C++前端,可以将C/C++代码转换为MLIR表示。Polygeist还包含了一系列优化passes,包括多面体优化。

实例：

import islpy as isl

# 定义原始循环
original_code = """
for i in range(N):
  for j in range(N):
    C[i,j] = 0
    for k in range(N):
      C[i,j] += A[i,k] * B[k,j]
"""

# 定义迭代域
iteration_domain = isl.Set("[N] -> { [i,j,k] : 0 <= i,j,k < N }")

# 定义访问关系
access_C = isl.Map("[N] -> { [i,j,k] -> C[i,j] }")
access_A = isl.Map("[N] -> { [i,j,k] -> A[i,k] }")
access_B = isl.Map("[N] -> { [i,j,k] -> B[k,j] }")

# 定义调度
schedule = isl.Map("[N] -> { [i,j,k] -> [i,j,k] }")

# 应用循环平铺优化
tile_size = 32
tiled_schedule = schedule.tile({"i": tile_size, "j": tile_size})

# 生成优化后的代码
ast_build = isl.AstBuild.from_context(iteration_domain.params())
ast = ast_build.ast_from_schedule(tiled_schedule)

print("优化后的代码:")
print(ast)

AI 编译器原理汇总#

Pass 的执行顺序 如何决定先做什么后做什么？#

函数内联#

Intra-procedural#

Inter-procedural#

transitive lowering#

为什么 MLIR 的 SSA 对于生成正确和高效的代码至关重要#

编译器是如何根据代码进行寄存器分配的 ？#

编译器是如何根据代码进行指令调度的？#

规约计算确保轴是非负的并且按升序排列，这是有利于编译优化的#

规范化 canonical-ize (简洁化)#

对一个 Dialect 的 Analysis#

Analysis Pass#

基于内存的操作 VS 基于 SSA 值的操作#

arith::extf & arith::truncf#

Decompose aggregated operations 在 AI 编译器中是什么意思#

Fold tensor operation 作用#

-loop-invariant-code-motion#

-loop-invariant-subset-hoisting mlir#

Bufferization#

补：内存缓冲区#

-eliminate-empty-tensors#

-one-shot-bufferize#

-mem2reg#

Reduction Sinking#

Loop Interchange [访问模式] ***#

register spill#

scratch space#

传统编译器#

给出算法将表达式树 转换为DAG#

表达式树#

多面体优化框架#