Comments (2)
qjivy
commented on July 30, 2024
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的循环）
加入原理的介绍是否多余？侧重点是源码（默认有编译理论基础）还是大而全？
from v8-internals.
qjivy
commented on July 30, 2024
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的循环）
加入原理的介绍是否多余？侧重点是源码（默认有编译理论基础）还是大而全？
from v8-internals.
Related Issues (8)
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from v8-internals.