原Y站v8-riscv/-/issues/253:指令调度代码剖析 by 陶立强
qjivy opened this issue · 2 comments
搬运issue253.
V8 TurboFan后端指令调度代码剖析
前言
下面的内容以代码解析为主,必要的知识会给出参考链接或者简单介绍
整体
指令调度的位置,相关文件
指令调度(instruction scheduling),是一种代码优化手段,常见于优化编译器,需要满足在执行结果相同的前提下,最小化程序块的执行时间,使得程序在拥有指令流水线的**处理器上能够高效运行。(一般意义上的指令调度)
这里放个链接吧?
在v8的turbofan后端中,指令调度位于指令选择之后;指令调度的后一个优化阶段为寄存器分配(Register Allocate)。
由于V8中的IR为SON node,一种图IR,所以最终会被转换成序列(线性)的形式。一种简单直白的方式是,按照遍历图IR中的basic block的顺序,将其排列成线性的形式(在后面的代码中我们也会看到),但是,这样简单粗暴的办法是无法利用处理器流水线处理指令的这一特点。
出于更好利用处理器的流水线操作的目的,经过v8 turbofan后端的指令调度输出的指令序列,在满足指令间数据依赖的前提下,时钟周期长(后续代码中用latency来表示,具体的计算方式见下文)的指令会排列在序列的前面。
主要的文件有
src/compiler/backend/instruction-scheduler.h
src/compiler/backend/instruction-scheduler.cc
src/compiler/backend/instruction-scheduler-riscv64.cc
首先来看指令调度阶段的代码调用,其位置为src/compiler/backend/instruction-selector.cc
文件中的InstructionSelector::SelectInstructions()
方法内,在包含VisitBlock
方法的for循环之后,大约为107行以后。
// Schedule the selected instructions.
if (UseInstructionScheduling()) {
scheduler_ = zone()->New<InstructionScheduler>(zone(), sequence());
}
for (auto const block : *blocks) {
InstructionBlock* instruction_block =
sequence()->InstructionBlockAt(RpoNumber::FromInt(block->rpo_number()));
for (size_t i = 0; i < instruction_block->phis().size(); i++) {
UpdateRenamesInPhi(instruction_block->PhiAt(i));
}
size_t end = instruction_block->code_end();
size_t start = instruction_block->code_start();
DCHECK_LE(end, start);
StartBlock(RpoNumber::FromInt(block->rpo_number()));
if (end != start) {
while (start-- > end + 1) {
UpdateRenames(instructions_[start]);
AddInstruction(instructions_[start]);
}
UpdateRenames(instructions_[end]);
AddTerminator(instructions_[end]);
}
EndBlock(RpoNumber::FromInt(block->rpo_number()));
}
在进一步讲解代码之前,首先来看一下该阶段的输入和输出。
从哪来到哪去(输入输出)
数据的来源,也就是前一阶段指令选择结束后的指令,在指令选择阶段,每一条指令都会被添加到InstructionSelector::instructions_
成员变量中。
Instruction* InstructionSelector::Emit(Instruction* instr) {
instructions_.push_back(instr);
return instr;
}
instructions_
线性表中的指令将在上述的代码中被做相应处理,即
if (end != start) {
while (start-- > end + 1) {
UpdateRenames(instructions_[start]);
AddInstruction(instructions_[start]);
}
UpdateRenames(instructions_[end]);
AddTerminator(instructions_[end]);
}
最后调度完毕的指令序列会加入到成员变量sequence_
中,例如上面出现过的AddInstrucion
方法
void InstructionSelector::AddInstruction(Instruction* instr) {
if (UseInstructionScheduling()) {
DCHECK_NOT_NULL(scheduler_);
scheduler_->AddInstruction(instr);
} else {
sequence()->AddInstruction(instr);
}
}
上述代码中的sequence()
和scheduler_
成员最终都会调用sequence_
成员变量。
讲完了数据的从哪来到哪去之后,回到指令调度的外部调用代码中,首先是类初始化
// Schedule the selected instructions.
if (UseInstructionScheduling()) {
scheduler_ = zone()->New<InstructionScheduler>(zone(), sequence());
}
其中的InstcutionScheduler
就是指令调度的具体实现类了,实例化的scheduler_被用来会调用指令调度的具体的方法。
紧接着的for循环便是指令调度处理的主体代码了
for (auto const block : *blocks) {
InstructionBlock* instruction_block =
sequence()->InstructionBlockAt(RpoNumber::FromInt(block->rpo_number()));
for (size_t i = 0; i < instruction_block->phis().size(); i++) {
UpdateRenamesInPhi(instruction_block->PhiAt(i));
}
size_t end = instruction_block->code_end();
size_t start = instruction_block->code_start();
DCHECK_LE(end, start);
StartBlock(RpoNumber::FromInt(block->rpo_number()));
if (end != start) {
while (start-- > end + 1) {
UpdateRenames(instructions_[start]);
AddInstruction(instructions_[start]);
}
UpdateRenames(instructions_[end]);
AddTerminator(instructions_[end]);
}
EndBlock(RpoNumber::FromInt(block->rpo_number()));
}
编译器在这个for循环中遍历basic blocks,然后对每个basic block内的指令进行处理,其中与指令调度最密切相关的四个方法如下,
void StartBlock(RpoNumber rpo);
void EndBlock(RpoNumber rpo);
void AddInstruction(Instruction* instr);
void AddTerminator(Instruction* instr);
这部分的语义比较清晰,可以通过望文生义来理解,对于每个basic block,标记block的开始StartBlock
;遍历并添加指令AddInstrucion
;该block中指令添加完调用AddTerminator
;最后标记该block的结束EndBlock
。
接下来再看一下这四个成员方法的代码,均为一个分支判断,分支判断会调用成员相应的同名方法,例如AddInstruction
,从这里也可以观察到,当不使用指令调度(即进入else分支)时,指令会直接添加到最后的sequence()
线性表中。
void InstructionSelector::AddInstruction(Instruction* instr) {
if (UseInstructionScheduling()) {
DCHECK_NOT_NULL(scheduler_);
scheduler_->AddInstruction(instr);
} else {
sequence()->AddInstruction(instr);
}
}
具体实现(内部)
TODO
从外部调用的四个方法开始一点点深入
从易到难,StartBlock, EndBlock, AddTerminator, AddInstruction, Schedule
引入依赖关系,抽象成DAG(有向无环图)
算法流程,latency相关定义和计算
后记
还没想好记点什么
疑难杂问题
在指令选择中,为什么后序(rpo)遍历basic block(调用VisitBlock的循环)
加入原理的介绍是否多余?侧重点是源码(默认有编译理论基础)还是大而全?
V8 TurboFan后端指令调度代码剖析
前言
下面的内容以代码解析为主,必要的知识会给出参考链接或者简单介绍
整体
指令调度的位置,相关文件
指令调度(instruction scheduling),是一种代码优化手段,常见于优化编译器,需要满足在执行结果相同的前提下,最小化程序块的执行时间,使得程序在拥有指令流水线的**处理器上能够高效运行。(一般意义上的指令调度)
这里放个链接吧?
在v8的turbofan后端中,指令调度位于指令选择之后;指令调度的后一个优化阶段为寄存器分配(Register Allocate)。
由于V8中的IR为SON node,一种图IR,所以最终会被转换成序列(线性)的形式。一种简单直白的方式是,按照遍历图IR中的basic block的顺序,将其排列成线性的形式(在后面的代码中我们也会看到),但是,这样简单粗暴的办法是无法利用处理器流水线处理指令的这一特点。
出于更好利用处理器的流水线操作的目的,经过v8 turbofan后端的指令调度输出的指令序列,在满足指令间数据依赖的前提下,时钟周期长(后续代码中用latency来表示,具体的计算方式见下文)的指令会排列在序列的前面。
主要的文件有
src/compiler/backend/instruction-scheduler.h
src/compiler/backend/instruction-scheduler.cc
src/compiler/backend/instruction-scheduler-riscv64.cc
首先来看指令调度阶段的代码调用,其位置为src/compiler/backend/instruction-selector.cc
文件中的InstructionSelector::SelectInstructions()
方法内,在包含VisitBlock
方法的for循环之后,大约为107行以后。
// Schedule the selected instructions.
if (UseInstructionScheduling()) {
scheduler_ = zone()->New<InstructionScheduler>(zone(), sequence());
}
for (auto const block : *blocks) {
InstructionBlock* instruction_block =
sequence()->InstructionBlockAt(RpoNumber::FromInt(block->rpo_number()));
for (size_t i = 0; i < instruction_block->phis().size(); i++) {
UpdateRenamesInPhi(instruction_block->PhiAt(i));
}
size_t end = instruction_block->code_end();
size_t start = instruction_block->code_start();
DCHECK_LE(end, start);
StartBlock(RpoNumber::FromInt(block->rpo_number()));
if (end != start) {
while (start-- > end + 1) {
UpdateRenames(instructions_[start]);
AddInstruction(instructions_[start]);
}
UpdateRenames(instructions_[end]);
AddTerminator(instructions_[end]);
}
EndBlock(RpoNumber::FromInt(block->rpo_number()));
}
在进一步讲解代码之前,首先来看一下该阶段的输入和输出。
从哪来到哪去(输入输出)
数据的来源,也就是前一阶段指令选择结束后的指令,在指令选择阶段,每一条指令都会被添加到InstructionSelector::instructions_
成员变量中。
Instruction* InstructionSelector::Emit(Instruction* instr) {
instructions_.push_back(instr);
return instr;
}
instructions_
线性表中的指令将在上述的代码中被做相应处理,即
if (end != start) {
while (start-- > end + 1) {
UpdateRenames(instructions_[start]);
AddInstruction(instructions_[start]);
}
UpdateRenames(instructions_[end]);
AddTerminator(instructions_[end]);
}
最后调度完毕的指令序列会加入到成员变量sequence_
中,例如上面出现过的AddInstrucion
方法
void InstructionSelector::AddInstruction(Instruction* instr) {
if (UseInstructionScheduling()) {
DCHECK_NOT_NULL(scheduler_);
scheduler_->AddInstruction(instr);
} else {
sequence()->AddInstruction(instr);
}
}
上述代码中的sequence()
和scheduler_
成员最终都会调用sequence_
成员变量。
讲完了数据的从哪来到哪去之后,回到指令调度的外部调用代码中,首先是类初始化
// Schedule the selected instructions.
if (UseInstructionScheduling()) {
scheduler_ = zone()->New<InstructionScheduler>(zone(), sequence());
}
其中的InstcutionScheduler
就是指令调度的具体实现类了,实例化的scheduler_被用来会调用指令调度的具体的方法。
紧接着的for循环便是指令调度处理的主体代码了
for (auto const block : *blocks) {
InstructionBlock* instruction_block =
sequence()->InstructionBlockAt(RpoNumber::FromInt(block->rpo_number()));
for (size_t i = 0; i < instruction_block->phis().size(); i++) {
UpdateRenamesInPhi(instruction_block->PhiAt(i));
}
size_t end = instruction_block->code_end();
size_t start = instruction_block->code_start();
DCHECK_LE(end, start);
StartBlock(RpoNumber::FromInt(block->rpo_number()));
if (end != start) {
while (start-- > end + 1) {
UpdateRenames(instructions_[start]);
AddInstruction(instructions_[start]);
}
UpdateRenames(instructions_[end]);
AddTerminator(instructions_[end]);
}
EndBlock(RpoNumber::FromInt(block->rpo_number()));
}
编译器在这个for循环中遍历basic blocks,然后对每个basic block内的指令进行处理,其中与指令调度最密切相关的四个方法如下,
void StartBlock(RpoNumber rpo);
void EndBlock(RpoNumber rpo);
void AddInstruction(Instruction* instr);
void AddTerminator(Instruction* instr);
这部分的语义比较清晰,可以通过望文生义来理解,对于每个basic block,标记block的开始StartBlock
;遍历并添加指令AddInstrucion
;该block中指令添加完调用AddTerminator
;最后标记该block的结束EndBlock
。
接下来再看一下这四个成员方法的代码,均为一个分支判断,分支判断会调用成员相应的同名方法,例如AddInstruction
,从这里也可以观察到,当不使用指令调度(即进入else分支)时,指令会直接添加到最后的sequence()
线性表中。
void InstructionSelector::AddInstruction(Instruction* instr) {
if (UseInstructionScheduling()) {
DCHECK_NOT_NULL(scheduler_);
scheduler_->AddInstruction(instr);
} else {
sequence()->AddInstruction(instr);
}
}
具体实现(内部)
TODO
从外部调用的四个方法开始一点点深入
从易到难,StartBlock, EndBlock, AddTerminator, AddInstruction, Schedule
引入依赖关系,抽象成DAG(有向无环图)
算法流程,latency相关定义和计算
后记
还没想好记点什么
疑难杂问题
在指令选择中,为什么后序(rpo)遍历basic block(调用VisitBlock的循环)
加入原理的介绍是否多余?侧重点是源码(默认有编译理论基础)还是大而全?