SIMD backend implementation in LLVM

在 LLVM 中支持新向量指令集

Yingchi Long

longyingchi24s@ict.ac.cn

Institute of Computing Technology, CAS

感谢 TUNA!

Agenda

什么程序向量化有收益？
向量化需要做什么工作？
基本概念: Module, Function, BasicBlock
标量 IR $\to$ 向量 IR：指导已有 Pass
向量 IR $\to$ 机器指令：指令选择算法
- 对齐了吗？
- 会溢出吗？
- 把标量当向量的骚操作？
Future Work: RVV/SVE
小结

什么样的程序做向量化有收益？

bisheng 编译器 -O3 下 SPEC2017 整点课题提升情况
类别	测试项	关 SIMD	开 SIMD	提升
整数	600.perlbench_s	3.4	3.39	-0.29%
	602.gcc_s	5.79	5.79	0.00%
	605.mcf_s	4.32	4.1	-5.09%
	620.omnetpp_s	3.01	2.99	-0.66%
	623.xalancbmk_s	3.45	3.72	7.83%
	625.x264_s	4.1	7.18	75.12%
	631.deepsjeng_s	3.71	3.65	-1.62%
	641.leela_s	3.13	3.16	0.96%
	648.exchange2_s	5.82	5.91	1.55%
	657.xz_s	2.17	2.23	2.76%
几何平均		3.74	3.97	6.29%

什么样的程序做向量化有收益？

bisheng 编译器 -O3 下 SPEC2017 浮点课题提升情况
类别	测试项	关 SIMD	开 SIMD	提升
浮点	603.bwaves_s	10.8	10.8	0.00%
	607.cactuBSSN_s	2.01	2.02	0.50%
	619.lbm_s	3.3	3.38	2.42%
	621.wrf_s	2.09	3.29	57.42%
	627.cam4_s	1.03	1.03	0.00%
	628.pop2_s	1.71	1.97	15.20%
	638.imagick_s	1.6	1.6	0.00%
	644.nab_s	3.91	3.92	0.26%
	649.fotonik3d_s	3.59	5.14	43.18%
	654.roms_s	1.85	2.79	50.81%
几何平均		2.53	2.91	14.99%

Overview

Things to do:

编译器：codegen, calling conv
JIT: v8, JVM
glibc dl-trampoline.S
kernel: alignment, fp denormal

Overview

Things to do:

scalar IR $\to$ vector IR
vector IR $\to$ machine code

Overview

Things to do:

Pass, but guided by the backend
vector IR $\to$ machine code

Overview

Things to do:

Pass, but guided by the backend
SelectionDAG algorithm
- BasicBlock-wide
- Pattern-based Rewrites

Overview

基本概念：Module, Function, BasicBlock

IR: Intermediate Representation, 中间表示
Module: 从一个{.c, .cpp~~,crate~~}生成
Function: 对应每一个程序中的函数
BasicBlock: 不带控制流的指令序列
Module := Function*
Function := BasicBlock*

向量的数据表示

基本数据类型： int、float, ...
我们如何表示向量数据类型？

给他们前面加上数量
8 x float, 4 x int
问题：8 x, 4 x 可以支持，$n$ x ？
- 部分支持：vscale x 8 x i32
- vscale 为运行时常量
对 X86, Neon(ARM) 等指令集有效
对 RVV, SVE ~~这些比较原神的扩展~~表现力有限

scalar IR $\to$ vector IR

→ godbolt
已有 Pass 来完成，可以所有 Target 共用
问题：simd 指令集差别很大，如何共用？
方案：提供信息，指导公共Pass
具体来说呢？--重写虚函数
TargetTransformInfo

scalar IR $\to$ vector IR

中端可能感兴趣什么问题？

向量有多长
运算的 Cost

后端如何实现？

硬件支持：输出 Cost
不支持：根据自己做了什么转换，递归

什么是 Cost?

后端提供的代价类型	语义
`TCK_RecipThroughput`	吞吐量倒数
`TCK_Latency`	指令延迟
`TCK_CodeSize`	指令产生的二进制大小
`TCK_SizeAndLatency`	二进制大小与延迟的加权和

Funny thing:
后端：所有代价类型都输出同一个数

scalar IR $\to$ vec IR 小结

override 虚函数，提供信息
信息包括代价、向量寄存器长度、数量
~~这个代价做的粗糙点也没问题~~
有了 vec IR ，现在怎么生成 asm/obj?

IR 与新指令的对应关系：指令选择算法

数据结构：SelectionDAG
- 有向无环图结构，bb 内，不包含控制流
- 用节点代表一次运算，前驱表示操作数
算法：Rewrites - based on pattern-matching

SelectionDAG 的结构

可以用 DAG 表意数据的流动关系

SelectionDAG 的结构

可以用 DAG 表意数据的流动关系

~~它没这么简单~~

Load/Store ?
vadd, add, fadd
控制流

SelectionDAG 的结构

Load/Store ?
vadd, add, fadd
控制流

访存多接受一个参数
每个数据类型都有 Type
不支持复杂控制流

Example: add

define i32 @add(i32 %a, i32 %b) {
    %ret = add i32 %a, %b
    ret i32 %ret
}

实际的 SelectionDAG：Type + Chain

                        digraph "dag-combine1 input for add:" {
                            rankdir="BT";
                            Node0x431106d0 [shape=record,shape=Mrecord,label="{EntryToken|t0|{ch|glue}}"];
                            Node0x43168070 [shape=record,shape=Mrecord,label="{Register %0|t1|{i32}}"];
                            Node0x431680e0 [shape=record,shape=Mrecord,label="{{0|1}|CopyFromReg|t2|{i32|ch}}"];
                            Node0x431680e0:s0 -> Node0x431106d0:d0[color=blue,style=dashed];
                            Node0x431680e0:s1 -> Node0x43168070:d0;
                            Node0x43168150 [shape=record,shape=Mrecord,label="{Register %1|t3|{i32}}"];
                            Node0x431681c0 [shape=record,shape=Mrecord,label="{{0|1}|CopyFromReg|t4|{i32|ch}}"];
                            Node0x431681c0:s0 -> Node0x431106d0:d0[color=blue,style=dashed];
                            Node0x431681c0:s1 -> Node0x43168150:d0;
                            Node0x43168230 [shape=record,shape=Mrecord,label="{{0|1}|add|t5|{i32}}"];
                            Node0x43168230:s0 -> Node0x431680e0:d0;
                            Node0x43168230:s1 -> Node0x431681c0:d0;
                        }

add i32 %1 %2 的 SelectionDAG

Example: load / store: add chains

define void @store(ptr %f) {
    store i32 1, ptr %f
    store i32 2, ptr %f
    ret void
}

Example: load / store: add chains

                        digraph "dag-combine1 input for store:" {
                            rankdir="BT";
                            Node0x3776a290 [shape=record,shape=Mrecord,label="{EntryToken|t0|{ch|glue}}"];
                            Node0x377c1af0 [shape=record,shape=Mrecord,label="{Register %0|t1|{i64}}"];
                            Node0x377c1b60 [shape=record,shape=Mrecord,label="{{0|1}|CopyFromReg|t2|{i64|ch}}"];
                            Node0x377c1b60:s0 -> Node0x3776a290:d0[color=blue,style=dashed];
                            Node0x377c1b60:s1 -> Node0x377c1af0:d0;
                            Node0x377c1bd0 [shape=record,shape=Mrecord,label="{Constant\<1\>|t3|{i32}}"];
                            Node0x377c1cb0 [shape=record,shape=Mrecord,label="{undef|t5|{i64}}"];
                            Node0x377c1d20 [shape=record,shape=Mrecord,label="{{0|1|2|3}|store\<(store (s32) into %ir.f)\>|t6|{ch}}"];
                            Node0x377c1d20:s0 -> Node0x3776a290:d0[color=blue,style=dashed];
                            Node0x377c1d20:s1 -> Node0x377c1bd0:d0;
                            Node0x377c1d20:s2 -> Node0x377c1b60:d0;
                            Node0x377c1d20:s3 -> Node0x377c1cb0:d0;
                            Node0x377c1d90 [shape=record,shape=Mrecord,label="{Constant\<2\>|t7|{i32}}"];
                            Node0x377c1e00 [shape=record,shape=Mrecord,label="{{0|1|2|3}|store\<(store (s32) into %ir.f)\>|t8|{ch}}"];
                            Node0x377c1e00:s0 -> Node0x377c1d20:d0[color=blue,style=dashed];
                            Node0x377c1e00:s1 -> Node0x377c1d90:d0;
                            Node0x377c1e00:s2 -> Node0x377c1b60:d0;
                            Node0x377c1e00:s3 -> Node0x377c1cb0:d0;
                        }

两个 store，用蓝色的线连接他们的相对顺序

SelectionDAG: 将 IR 逐渐翻译到目标指令 (ISel)

合法化
1. Types
2. Operation
DAG $\to$ DAG ISel

先看如何合法化 Type

依据：后端给定一系列支持的 Type
自动完成 Promote/Expand 等操作
小问题：与 Op 是否相关？
- 不相关
方法：addRegisterClass()

合法化 Type: 一些例子

i31 $\to$ i32
4 x i32 $\to$ i32, i32, i32, i32
16 x i8 $\to$ 8 x i32, 8 x i32

合法化 Op: Expand/Custom/Legal

对象：(Op, Type) 元组
(Op, Type) $\to$ "Expand" | "Custom" | "Legal"
Target 支持 (Op, Type) $\to$ Legal
Target 不支持某些Op $\to$ 需要合法化
- 展开成标量：Expand
- 编写代码自力更生：Custom

合法化 Op: Expand/Custom/Legal

某Arch支持向量指令：

整数加法减法
向量移位，但移位量必须是常数
xor, or, and 位运算
不支持非对齐访存

如何合法化 Op:

ADD/SUB
SRA
MUL
LOAD/STORE
BSWAP
ABS

合法化 Op: Expand/Custom/Legal

某Arch支持向量指令：

整数加法减法
向量移位，但移位量必须是常数
xor, or, and 位运算
不支持非对齐访存

Load Store?

拆成两个 + Combine

Load p $\Rightarrow$
Load p_low + Load p_hi

如果还不对齐的话，需要 memcpy

地址对齐是前端分析出来并一路从中端传到后端的
要分析正确、传递正确

合法化 Op: Expand/Custom/Legal

某Arch支持向量指令：

整数加法减法
向量移位，但移位量必须是常数
xor, or, and 位运算
不支持非对齐访存

Byte Swap (from Chromium)?

整体移位 + or

$(A_0, A_1, A_2, A_3)$

$(A_3, O, O, O)$

$(O, A_2, O, O)$

$(O, O, A_1, O)$

合法化 Op: Expand/Custom/Legal

某Arch支持向量指令：

整数加法减法
向量移位，但移位量必须是常数
xor, or, and 位运算
不支持非对齐访存

ABS?

(SRA x, type_size - 1) = $t$
(ABS x) = (XOR (ADD x, $t$), $t$)

例子：8 位整数 -5 = $11111011_2$
$t$ = -1
$11111010_2$ xor $11111111_2$
= $11111111_2$

指令选择小结

结构：SelectionDAG
算法：DAG Rewrites: Type + Op

指令选择中的一些趣事

前端的对齐信息怎么感觉是瞎编的？？
simd不支持整数乘法？
我靠，Neon 这什么天顶星指令集
别人全 Legal, 我全得 Expand
i8 i32 都是 i ，倒腾一下也能用！

趣事：前端对齐信息瞎编？？

背景：

特殊支持: 单元素对齐的 load
为了优化：假定 double 至少对齐到 8
前端：load double align 1
后端：生成 memcpy

啥问题？

cflang 生成 IR 字符串，再由 llvm parse
cflang 对齐信息丢了，没打印
llvm verifier 自动补全了 align 1

趣事：simd 不支持整数乘法

省点面积：早期 x86 simd 是按需求加内容
SSE2 中有 PMULUDQ，但是🥵
这会导致 ISel / CostModel 写的特别复杂
省事儿：CostModel: simd MUL 的代价是 998244353
大数字 $\to$ 禁止中端向量化 $\to$ 别为难我
~~我其实说的不是 x86~~

趣事：我靠，Neon 这什么天顶星指令集

Neon 指令集只有 128 位，但是加速比吊打 x86

支持指令特别完备，~~要啥有啥~~
乘法、shuffle、特定 pattern 的 shuffle
Op 与 Type 是正交的：
支持 i32 加法，就一定支持 i8 加法
例子：x264 satd

Vector Shuffle: x264

Source code of x264_pixel_satd_8x4

Vector Shuffle: x264

See neon permutations.

Future Work: GlobalISel

ISel 是 per BB 的，丢失信息
InstCombine/DAGCombine 重复代码
$\to$ 新框架，全局地进行指令选择
未来可期，aarch64/riscv 后端支持还不错
信创后端不适配

Fuuuuture Work: RVV / SVE

框架表意比较困难，目前对 SVE 支持更好
在 MLIR 中有一些实践
~~感觉不如手写，效率不高~~

总结

向量化，收益看 Workload
标量 IR → 向量 IR，指导已有框架就行
向量 IR → 指令集，靠的是 SelectionDAG 的“花式操作”
增加向量寄存器长度，不如增加点操作
未来工作：RVV、SVE、GISel，还得加油

在 LLVM 中支持新向量指令集

感谢 TUNA!

Agenda

什么样的程序做向量化有收益？

什么样的程序做向量化有收益？

Overview

Overview

Overview

Overview

Overview

基本概念：Module, Function, BasicBlock

向量的数据表示

向量的数据表示

scalar IR $\to$ vector IR

scalar IR $\to$ vector IR

什么是 Cost?

scalar IR $\to$ vec IR 小结

IR 与新指令的对应关系：指令选择算法

SelectionDAG 的结构

SelectionDAG 的结构

SelectionDAG 的结构

Example: add

实际的 SelectionDAG：Type + Chain

Example: load / store: add chains

Example: load / store: add chains

SelectionDAG: 将 IR 逐渐翻译到目标指令 (ISel)

先看如何合法化 Type

合法化 Type: 一些例子

合法化 Op: Expand/Custom/Legal

合法化 Op: Expand/Custom/Legal

合法化 Op: Expand/Custom/Legal

合法化 Op: Expand/Custom/Legal

合法化 Op: Expand/Custom/Legal

指令选择小结

指令选择中的一些趣事

趣事：前端对齐信息瞎编？？

趣事：simd 不支持整数乘法

趣事：我靠，Neon 这什么天顶星指令集

Vector Shuffle: x264

Vector Shuffle: x264

Future Work: GlobalISel

Fuuuuture Work: RVV / SVE

总结

Question Time