LLVM 之后端篇（4）：理解指令选择的 dump 输出

Author: stormQ

Created: Thursday, 13. January 2022 10:23PM

Last Modified: Wednesday, 13. July 2022 07:21AM

摘要

本文基于release/13.x版本的 LLVM 源码，介绍了指令选择的整体阶段以及llc中常用 SelectionDAG 命令选项与各阶段之间的对应关系。除此之外，通过一个简单的示例展示了指令选择的 dump 输出及其含义。从而，掌握指令选择的常见调试分析方法，并有助于进一步研究指令选择的内部原理。

指令选择的整体阶段

指令选择是将LLVM IR转换为代表目标指令的 SelectionDAG 节点——SDNode。它是由一些较小的阶段组成的，这些阶段如下图所示。

为了直观地展示llc中常用 SelectionDAG 命令选项与各阶段之间的对应关系，图中除了指令选择阶段(1)~(10)以外，还包括了指令调度阶段(11)。

查看各阶段输出结果的常见方式有以下两种：

通过-debug-only=isel命令选项查看所有阶段的文本输出（对应图中绿色字体）。比如：Initial selection DAG:后面的 SelectionDAG 对应阶段(1)的文本输出结果。
通过-view-dag-combine1-dags、-view-legalize-dags等命令选项（对应图中紫色字体）查看指定阶段的可视化输出。比如：-view-dag-combine1-dags用于查看阶段(1)的可视化输出结果。另外，可以通过-filter-view-dags命令选项指定允许可视化的基本块。比如：-filter-view-dags=if_else -view-sched-dags表示只可视化基本块if_else在阶段(10)的输出结果。

需要注意的是：

如果阶段(3)——Type Legalization未修改 SelectionDAG，那么-view-dag-combine-lt-dags命令选项不会输出其可视化结果。并且，阶段(4)——DAG Combining也不会执行。相应地，Optimized type-legalized selection DAG:不会出现在文本输出结果中。
如果阶段(5)——Vector Legalization未修改 SelectionDAG，那么阶段(6)——Type Legalization 2和阶段(7)——DAG Combining都不会执行。并且，Vector-legalized selection DAG:、Vector/type-legalized selection DAG:、Optimized vector-legalized selection DAG:都不会出现在文本输出结果中。除此之外，-view-dag-combine-lt-dags命令选项也不会输出阶段(6)的可视化结果。然而，-view-legalize-dags命令选项总是可用的。

注：

指令选择的整体流程见SelectionDAGISel::CodeGenAndEmitDAG()函数的实现（定义在 llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp 文件中）。
llc中所有的 SelectionDAG 命令选项可以通过llc --help-list-hidden | grep dags命令进行查看。其输出结果如下：

  --filter-view-dags=<string>                                          - Only display the basic block whose name matches this for all view-*-dags options
  --view-block-freq-propagation-dags=<value>                           - Pop up a window to show a dag displaying how block frequencies propagation through the CFG.
  --view-dag-combine-lt-dags                                           - Pop up a window to show dags before the post legalize types dag combine pass
  --view-dag-combine1-dags                                             - Pop up a window to show dags before the first dag combine pass
  --view-dag-combine2-dags                                             - Pop up a window to show dags before the second dag combine pass
  --view-isel-dags                                                     - Pop up a window to show isel dags as they are selected
  --view-legalize-dags                                                 - Pop up a window to show dags before legalize
  --view-legalize-types-dags                                           - Pop up a window to show dags before legalize types
  --view-machine-block-freq-propagation-dags=<value>                   - Pop up a window to show a dag displaying how machine block frequencies propagate through the CFG.
  --view-misched-dags                                                  - Pop up a window to show MISched dags after they are processed
  --view-sched-dags                                                    - Pop up a window to show sched dags as they are processed
  --view-sunit-dags                                                    - Pop up a window to show SUnit dags after they are processed

查看指令选择的输出结果

step 1： 示例程序

test.ll：

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

step 2： 查看指令选择的文本输出

执行如下命令，打印指令选择各阶段的文本输出结果到 Shell 窗口中：

$ llc -march=riscv32 -filetype=asm test.ll -debug-only=isel -o test.s

注：如果要将结果输出到指定文件test.isel，则执行命令llc -march=riscv32 -filetype=asm test.ll -debug-only=isel -o test.s 2>test.isel。

输出结果如下：

=== test
Initial selection DAG: %bb.0 'test:'
SelectionDAG has 9 nodes:
  t0: ch = EntryToken
      t2: i32,ch = CopyFromReg t0, Register:i32 %0
      t4: i32,ch = CopyFromReg t0, Register:i32 %1
    t5: i32 = add t2, t4
  t7: ch,glue = CopyToReg t0, Register:i32 $x10, t5
  t8: ch = RISCVISD::RET_FLAG t7, Register:i32 $x10, t7:1


Optimized lowered selection DAG: %bb.0 'test:'
SelectionDAG has 9 nodes:
  t0: ch = EntryToken
      t2: i32,ch = CopyFromReg t0, Register:i32 %0
      t4: i32,ch = CopyFromReg t0, Register:i32 %1
    t5: i32 = add t2, t4
  t7: ch,glue = CopyToReg t0, Register:i32 $x10, t5
  t8: ch = RISCVISD::RET_FLAG t7, Register:i32 $x10, t7:1


Type-legalized selection DAG: %bb.0 'test:'
SelectionDAG has 9 nodes:
  t0: ch = EntryToken
      t2: i32,ch = CopyFromReg t0, Register:i32 %0
      t4: i32,ch = CopyFromReg t0, Register:i32 %1
    t5: i32 = add t2, t4
  t7: ch,glue = CopyToReg t0, Register:i32 $x10, t5
  t8: ch = RISCVISD::RET_FLAG t7, Register:i32 $x10, t7:1


Legalized selection DAG: %bb.0 'test:'
SelectionDAG has 9 nodes:
  t0: ch = EntryToken
      t2: i32,ch = CopyFromReg t0, Register:i32 %0
      t4: i32,ch = CopyFromReg t0, Register:i32 %1
    t5: i32 = add t2, t4
  t7: ch,glue = CopyToReg t0, Register:i32 $x10, t5
  t8: ch = RISCVISD::RET_FLAG t7, Register:i32 $x10, t7:1


Optimized legalized selection DAG: %bb.0 'test:'
SelectionDAG has 9 nodes:
  t0: ch = EntryToken
      t2: i32,ch = CopyFromReg t0, Register:i32 %0
      t4: i32,ch = CopyFromReg t0, Register:i32 %1
    t5: i32 = add t2, t4
  t7: ch,glue = CopyToReg t0, Register:i32 $x10, t5
  t8: ch = RISCVISD::RET_FLAG t7, Register:i32 $x10, t7:1


===== Instruction selection begins: %bb.0 ''

ISEL: Starting selection on root node: t8: ch = RISCVISD::RET_FLAG t7, Register:i32 $x10, t7:1
ISEL: Starting pattern match
  Morphed node: t8: ch = PseudoRET Register:i32 $x10, t7, t7:1
ISEL: Match complete!

ISEL: Starting selection on root node: t7: ch,glue = CopyToReg t0, Register:i32 $x10, t5

ISEL: Starting selection on root node: t5: i32 = add t2, t4
ISEL: Starting pattern match
  Initial Opcode index to 16032
  Skipped scope entry (due to false predicate) at index 16038, continuing at 16121
  Skipped scope entry (due to false predicate) at index 16122, continuing at 16156
  Skipped scope entry (due to false predicate) at index 16157, continuing at 16191
  Skipped scope entry (due to false predicate) at index 16192, continuing at 16226
  Match failed at index 16036
  Continuing at 16227
  Skipped scope entry (due to false predicate) at index 16240, continuing at 16308
  Skipped scope entry (due to false predicate) at index 16309, continuing at 16338
  Skipped scope entry (due to false predicate) at index 16339, continuing at 16368
  Skipped scope entry (due to false predicate) at index 16369, continuing at 16398
  Match failed at index 16238
  Continuing at 16399
  Match failed at index 16402
  Continuing at 16444
  Continuing at 16445
  Skipped scope entry (due to false predicate) at index 16451, continuing at 16598
  Skipped scope entry (due to false predicate) at index 16599, continuing at 16624
  Match failed at index 16448
  Continuing at 16625
  Skipped scope entry (due to false predicate) at index 16635, continuing at 16752
  Skipped scope entry (due to false predicate) at index 16753, continuing at 16773
  Match failed at index 16633
  Continuing at 16774
  Match failed at index 16777
  Continuing at 17225
  Match failed at index 17232
  Continuing at 17671
  Match failed at index 17677
  Continuing at 17778
  Match failed at index 17779
  Continuing at 17791
  Morphed node: t5: i32 = ADD t2, t4
ISEL: Match complete!

ISEL: Starting selection on root node: t4: i32,ch = CopyFromReg t0, Register:i32 %1

ISEL: Starting selection on root node: t2: i32,ch = CopyFromReg t0, Register:i32 %0

ISEL: Starting selection on root node: t6: i32 = Register $x10

ISEL: Starting selection on root node: t3: i32 = Register %1

ISEL: Starting selection on root node: t1: i32 = Register %0

ISEL: Starting selection on root node: t0: ch = EntryToken

===== Instruction selection ends:
Selected selection DAG: %bb.0 'test:'
SelectionDAG has 9 nodes:
  t0: ch = EntryToken
      t2: i32,ch = CopyFromReg t0, Register:i32 %0
      t4: i32,ch = CopyFromReg t0, Register:i32 %1
    t5: i32 = ADD t2, t4
  t7: ch,glue = CopyToReg t0, Register:i32 $x10, t5
  t8: ch = PseudoRET Register:i32 $x10, t7, t7:1


Total amount of phi nodes to update: 0
*** MachineFunction at end of ISel ***
# Machine code for function test: IsSSA, TracksLiveness
Function Live Ins: $x10 in %0, $x11 in %1

bb.0 (%ir-block.0):
  liveins: $x10, $x11
  %1:gpr = COPY $x11
  %0:gpr = COPY $x10
  %2:gpr = ADD %0:gpr, %1:gpr
  $x10 = COPY %2:gpr
  PseudoRET implicit $x10

# End machine code for function test.

step 3： 查看指令选择的可视化输出

1）准备可视化数据

执行如下命令，打印阶段(10)——Instruction Selection的可视化数据（以.dot结尾的文件）：

$ llc -march=riscv32 -filetype=asm -view-sched-dags test.ll -o test.s

输出结果如下：

Writing '/tmp/dag.test-e90982.dot'...  done. 
Trying 'xdg-open' program... Remember to erase graph file: /tmp/dag.test-e90982.dot
省略 ...

从上面的结果可以看出，可视化数据保存在/tmp/dag.test-e90982.dot文件中。

2）可视化输出结果

dot命令支持多种可视化格式，比如：.png、.svg、.pdf等，可以通过命令man dot查看可支持的格式。

$ dot -Tpng /tmp/dag.test-e90982.dot -o dag.test_e90982.png

或

$ dot -Tsvg /tmp/dag.test-e90982.dot -o dag.test_e90982.svg

注：为了使用dot命令，需要执行sudo apt-get install graphviz命令安装graphviz。

理解指令选择的文本输出

指令选择中各阶段的文本输出都是由llvm::SelectionDAG::dump()函数打印的。该函数的声明位于 llvm/include/llvm/CodeGen/SelectionDAG.h 文件，其定义位于 llvm/lib/CodeGen/SelectionDAG/SelectionDAGDumper.cpp 文件。

类llvm::SelectionDAG是一个有向无环图（Directed-Acyclic-Graph，DAG），用于表示每个基本块。DAG 的节点为llvm::SDNode类（定义在 llvm/include/llvm/CodeGen/SelectionDAGNodes.h 文件中）的实例，每个节点对应一条指令或一个操作数。DAG 的边为llvm::SDValue类的实例，作为节点的操作数（即节点的每个操作数都是一条指向其它节点的边）；每条边由一个<SDNode, unsigned>键值对构成，Key 表示所指向的节点（即定义操作数的节点，不妨称为Def-SDNode），Value 是一个索引（从 0 开始）表示使用Def-SDNode所定义的哪个值；每条边决定了两个节点在指令调度后必须满足何种（在基本块内的）先后出现顺序。

DAG 的节点既可以同时定义多个值，也可以同时包含多个操作数。DAG 节点所定义的每个值都关联一个MVT（Machine Value Type），用于表示该值的类型。常见的类型有如下三种（定义在 llvm/include/llvm/Support/MachineValueType.h 文件中）：

Concrete Value类型，表示具体的数据类型。比如：llvm::MVT::i8、llvm::MVT::f16、llvm::MVT::v1i1等，对应文本输出和 DAG 中的i8、f16等。
Other类型，对应的枚举值为llvm::MVT::Other，对应文本输出和 DAG 中的ch。
Glue类型，对应的枚举值为llvm::MVT::Glue，对应文本输出和 DAG 中的glue。

DAG 的边用于表示两个节点之间的依赖关系：数据依赖或控制依赖。如果节点A依赖于节点B记作A->B（意味着节点B必须位于节点A的前面）；那么边的含义可以分为如下三种：

表示数据依赖，称为regular-edge。对应 DAG 中的从节点A指向节点B的黑色实线。并且，箭头所指向的值（由节点B定义）的MVT类型一定是Concrete Value。
表示控制依赖并且节点A与B之间允许插入其它节点，称为chain-edge。对应 DAG 中的从节点A指向节点B的蓝色虚线。并且，箭头所指向的值（由节点B定义）的MVT类型一定是Other。
表示控制依赖并且节点A与B之间不允许插入其它节点（即节点B后面的第一个节点必须是A），称为glue-edge。对应 DAG 中的从节点A指向节点B的红色实线。并且，箭头所指向的值（由节点B定义）的MVT类型一定是Glue。

接下来，以阶段(10)——Instruction Selection为例，说明指令选择的文本输出所表示的含义。

114 Selected selection DAG: %bb.0 'test:'
115 SelectionDAG has 9 nodes:
116   t0: ch = EntryToken
117       t2: i32,ch = CopyFromReg t0, Register:i32 %0
118       t4: i32,ch = CopyFromReg t0, Register:i32 %1
119     t5: i32 = ADD t2, t4
120   t7: ch,glue = CopyToReg t0, Register:i32 $x10, t5
121   t8: ch = PseudoRET Register:i32 $x10, t7, t7:1

第 114 行，%bb.0是由 LLVM 内部为该基本块定义的标签名。'test:'表示该基本块对应的函数名:标签名，这里的函数名和标签名都是在 IR 代码中定义的。
第 115 行，表示该基本块所对应的 DAG 中包含t0~t8 9 个节点。这些节点的节点 ID（即llvm::SDNode::PersistentId字段）值为0~8。比如：t0表示节点 ID 为 0 的节点。
第 116 行，t0:表示该节点的节点 ID 为 0 （这里的节点 ID 对应源代码中的SDNode::PersistentId）。
- 等号左侧的ch表示该节点仅定义了一个值，其MVT类型为llvm::MVT::Other，该值的索引为 0。
- 等号右侧的EntryToken表示该节点是一个特殊的标记节点（对应的操作码为llvm::ISD::EntryToken）。
第 117 行， t2:表示该节点的节点 ID 为 2 。
- 等号左侧的i32,ch表示该节点定义了两个值，索引为 0 的值的MVT类型为llvm::MVT::i32；索引为 1 的值的MVT类型为llvm::MVT::Other。
- 等号右侧的CopyFromReg表示该节点是读寄存器操作（对应的操作码为llvm::ISD::CopyFromReg）。
- 等号右侧的t0, Register:i32 %0表示该节点包含两个操作数，索引为 0 的操作数表示一条指向t0节点所定义的索引为 0 的值的chain-edge（即省略了t0:0中的:0）；索引为 1 的操作数表示一条指向t1节点所定义的索引为 0 的值的regular-edge。
  
  实际上，Register:i32 %0是 DAG 中的t1节点，其中冒号左侧的Register表示该节点是寄存器（对应的操作码为llvm::ISD::Register）；冒号右侧的i32表示该节点仅定义了一个值，其MVT类型为llvm::MVT::i32；%0以%开头表示虚拟寄存器%0，该节点在文本输出时被折叠打印了。如果不折叠打印，那么该行的输出结果应该为t2: i32,ch = CopyFromReg t0, t1。
- 相比于节点t5，节点t2缩进了两个空格，表示节点t2仅被节点t5使用了（即节点t2的使用者只有节点t5，意味着节点t2必须位于节点t5的前面）。如果节点t2的使用者有多个，那么该节点不会进行缩进打印。
第 118 行，t4:表示该节点的节点 ID 为 4 。同样地，节点t4也仅被节点t5使用了。
第 119 行，t5:表示该节点的节点 ID 为 5 。
- 等号左侧的i32表示该节点仅定义了一个值，其MVT类型为llvm::MVT::i32，该值的索引为 0。
- 等号右侧的ADD表示该节点是机器指令add（对应的操作码为llvm::RISCV::ADD）。
- 等号右侧的t2, t4表示该节点包含两个操作数，索引为 0 的操作数表示一条指向t2节点所定义的索引为 0 的值的regular-edge（省略了t2:0中的:0）；索引为 1 的操作数表示一条指向t4节点所定义的索引为 0 的值的regular-edge（省略了t4:0中的:0）。
- 同样地，节点t5仅被节点t7使用了。
第 120 行，t7:表示该节点的节点 ID 为 7 。
- 等号左侧的ch,glue表示该节点定义了两个值，索引为 0 的值的MVT类型为llvm::MVT::Other；索引为 1 的值的MVT类型为llvm::MVT::Glue。
- 等号右侧的CopyToReg表示该节点是写寄存器操作（对应的操作码为llvm::ISD::CopyToReg）。
- 等号右侧的t0, Register:i32 $x10, t5表示该节点包含三个操作数，索引为 0 的操作数表示一条指向t0节点所定义的索引为 0 的值的chain-edge（省略了t0:0中的:0）；索引为 1 的操作数表示一条指向t6节点所定义的索引为 0 的值的regular-edge；索引为 2 的操作数表示一条指向t5节点所定义的索引为 0 的值的regular-edge（省略了t5:0中的:0）。
  
  实际上，Register:i32 $x10是 DAG 中的t6节点，其中冒号左侧的Register表示该节点是寄存器（对应的操作码为llvm::ISD::Register）；冒号右侧的i32表示该节点仅定义了一个值，其MVT类型为llvm::MVT::i32；$x10以$开头表示物理寄存器x10，该节点在文本输出时被折叠打印了。如果不折叠打印，那么该行的输出结果应该为t7: ch,glue = CopyToReg t0, t6, t5。
第 121 行，t8:表示该节点的节点 ID 为 8 。
- 等号左侧的ch表示该节点仅定义了一个值，其MVT类型为llvm::MVT::Other，该值的索引为 0。
- 等号右侧的PseudoRET表示该节点是伪机器指令ret（对应的操作码为llvm::RISCV::PseudoRET）。
- 等号右侧的Register:i32 $x10, t7, t7:1表示该节点包含三个操作数，索引为 0 的操作数表示一条指向t6节点所定义的索引为 0 的值的regular-edge（被折叠打印了）；索引为 1 的操作数表示一条指向t7节点所定义的索引为 0 的值的chain-edge（省略了t7:0中的:0）；索引为 2 的操作数表示一条指向t7节点所定义的索引为 1 的值的glue-edge。

理解指令选择的可视化输出

指令选择中各阶段的可视化输出都是由llvm::SelectionDAG::viewGraph()函数打印的。该函数的声明位于 llvm/include/llvm/CodeGen/SelectionDAG.h 文件，其定义位于 llvm/lib/CodeGen/SelectionDAG/SelectionDAGPrinter.cpp 文件。

接下来，以阶段(10)——Instruction Selection为例，说明指令选择的可视化输出所表示的含义。

根节点GraphRoot，实际上 DAG 中不存在该节点（用椭圆形表示）。该节点与节点t8之间有一条chain-edge，表示节点t8必须作为基本块内的最后一条指令。
节点t8，DAG 中实际存在该节点（用圆角矩形表示）。该节点分为四部分，从上到下依次为：操作数的索引、操作码、节点 ID、节点所定义值的MVT类型。每部分的含义与文本输出中一致，这里不再赘述。

References

下一篇：LLVM 之后端篇（5）：理解 SelectionDAG 合法化

上一篇：LLVM 之后端篇（3）：如何添加 MyRISCV 目标后端的第一条指令

首页