Choreo 值编号简介¶

在 Choreo 中，值编号过程用于辅助 Shape Inference：要么直接推断编译期已知的形状，要么生成形状计算表达式。

许多值编号方法侧重于消除冗余计算（始终产生相同值的表达式），而 Choreo 的值编号旨在为简化 Choreo 领域专用构造 mdspan 建立一种渐进式方法。在此语境下，常量传播、代数化简等技术的应用更为关键。

在实现方式上，Choreo 采用简单的基于作用域的值编号方法——这是对局部值编号方法的扩展，并辅以词法作用域的值编号表[1]。与其他值编号方法不同，Choreo 不必构建基本块、pruned-SSA 或编译器后端，因为它将值编号直接施加于抽象语法树（AST）。然而，为支持该做法，必须对 Choreo 的语法规则施加一定限制，尤其需防止值的变更。

简明示例¶

值编号过程为所有包含值列表的实体（包括 mdspan 与 ituple）分配值编号。例如，

mdspan a : {1, b, c + 3}

值编号过程会产生如下值：

   VN #0:  const_1
   VN #1:  b
   VN #2:  c
   VN #3:  const_3
   VN #4:  +:#2:#3
   VN #5:  #0,#1,#4

在本例中，VN # 后的数字为表达式的值编号。它要么表示常量整数值（编译期已知），要么表示符号值（如变量 a、b），要么表示对其他值编号的组合。此处，值编号 #0 与 #3 表示对常量值的引用，#1 与 #2 表示对整型变量 b 与 c 的引用。#4 表示加法表达式的值，即 #2 与 #3 之和；若将所有值编号还原，即对应表达式 c + 3。最后，值编号 #5 以符号化方式表示由 mdspan a 所定义的值列表。依此定义，可将索引操作（例如 a(0)）翻译为值编号 #0，从而得到常量 1。

实现¶

从表达式到值编号¶

在当前实现中，值编号以语法制导方式进行：遍历 AST 节点，当节点包含表达式时生成值编号。

生成值编号的方法较为直接：对每个表达式，以其为输入，返回对应的值编号。

更具体地，流程为： * 由表达式生成签名（signature）。 * 若该签名已存在，则通过查找值编号表返回关联的值编号。 * 否则，在值编号表中将该签名关联到新的值编号并返回。

为简化起见，当前签名采用表达式的字符串形式；后续可像多数值编号流程那样改为哈希。

此外，为处理符号定义与符号引用，遵循如下规则：

当某表达式用于初始化符号（变量或 partial type）时，该符号与表达式的值编号相同。更具体地，将带作用域的符号名之签名关联到值编号表中的对应值编号。
当表达式引用符号时，在值编号表中查找其对应签名并返回。

注意：符号在生成签名时必须使用带作用域的名称，因为不同作用域中允许出现同名定义。

化简¶

每次值编号过程生成签名时，会尝试对表达式进行化简。例如，

   int a = 0 + 1;

对简单整型表达式，值编号过程可生成如下签名及关联值编号：

   VN #0:  const_3
   VN #1:  const_8
   VN #2:  +:#0:#1
   Alias a -> #2

若无优化，会生成两个常量值 #0、#1，以及新的值编号 #2，表示 #0 与 #1 的加法。#2 的签名为 +:#0:#1。考虑到常量加法可在编译期求值，可执行化简。下述输出展示了优化后的值编号过程：

   VN #0:  const_3
   VN #1:  const_8
   VN #2:  const_11
   Alias a -> #2

此时 #2 的签名表示常量，表明代数化简已成功应用。

从值编号到表达式¶

经过值编号与化简后，每个表达式与其化简后的值编号相关联。在 Choreo 中，这是 mdspan 类型形状推断的重要步骤。

mdspan 类型是一种 partial type，用于定义基本类型元素的个数；在编程中，与某一 fundamental type 结合时，可决定被span 的对象所占内存大小。

mdspan 的形状细节可在运行时确定。然而在许多情形下，形状可在编译期完全求值为固定数值。此时亦可于编译期触发静态内存分配，以更好利用系统内存；否则需生成计算形状的代码。

因此，除常量值外，还需要从值编号反向生成表达式。

设计考量¶

词法作用域与限制¶

在 Choreo 中，值编号在 AST 之上全局应用。由于其为不构建基本块的语法制导方法、因而缺乏数据流分析，无法推断维度会变化的形状。

局限性¶

更具体地，需设定两条限制： 1. 任何 mdspan 不得含有 bounded integer 类型的元素，或由 bounded ituple 产生。 2. 简单整型与 ituple 类型不得被重复定义。

参考文献¶

[1] Briggs P, Cooper K D, Simpson L T. Value numbering[J]. Software: Practice and Experience, 1997, 27(6): 701-724.