自从年初手断了以后好久不写文字了, 说好的笔耕不辍也忘了(=.=), 今天正好有同学问AntiDepBreaker, 就花点时间看了下代码(顺便水一篇).
背景概述
1. 什么是Anti Dependency
在数据流分析中一般将数据依赖分为三种:
- 写后读(RAW, read after write), 通常情况下一个值必须先定义后使用, 因此又称数据依赖(data dependency)或真依赖(true dependency).
- 读后写(WAR, write after read), 这种情况通常发生在对同一变量/寄存器连续读写之间, 由于读的是前一次写的值, 而写的是后一次的值, 因此被称为反依赖(anti dependency).
- 写后写(WAW, write after write), 对同一变量/寄存器连续写, 被称为输出依赖(output dependency).
在LLVM调度器中使用SDep(schedule dependency)描述两个SUnit(schedule unit)之间的依赖(见include/llvm/CodeGen/ScheduleDAG.h).
2. 什么情况下出现反依赖
对于反依赖与输出依赖, 由于它们分别要求先使用后定义/多次定义, 因此只有在经过Phi Elimination后程序流不再维护SSA状态才能出现. 而一般架构在postRA阶段会再做一次指令调度, 此时分析依赖图即会产生反依赖与输出依赖.
另外需要注意的是有些架构存在隐式定义/使用特殊寄存器的情况, 由于这类指令固定使用某些物理寄存器, 因此preRA阶段也可能产生针对特定物理寄存器的反依赖/数据依赖(这也是为什么建议大家不要给指令定义隐式急寄存器, 而是通过增加寄存器类型的方式限定寄存器使用的原因).
3. AntiDepBreaker的作用
依赖的存在加强了节点间的约束, 使指令调度时可选的调度窗口变窄, 导致调度结果变差. 减少依赖可以扩大指令调度窗口, 缩短critical path的长度, 获得更好的性能.
需要注意的是真依赖与(对固定寄存器的)写依赖/反依赖都是不可消除的, 只有(对非固定寄存器的)写依赖/反依赖其读写的内容实质指向两个值, 因此可以通过变量/寄存器重命名来解决, AntiDepBreaker就是用postRA阶段调度前的消除依赖的优化.
另外还要注意的是这类优化主要针对没有硬件调度单元的架构做的, 对于支持乱序执行与重命名的架构作用相对而言较小.
4. AntiDepBreaker的实现思路
自底向上扫描指令, 跟踪寄存器分配状态的同时检查指令是否存在反依赖. 若存在反依赖则从空闲的寄存器列表中选择合适(生命周期不冲突)的寄存器做替换.
在postRA做这类数据流分析的难度主要在于无法维持SSA状态, 在分析过程中需要注意以下几点:
- 分析别名寄存器. 在LLVM中物理寄存器不同与虚拟寄存器, 不同类型的虚拟寄存器在preRA阶段存在COPY/PHI/REG_SEQUENCE等方式转换寄存器类型, 但postRA阶段对应的伪指令被消除, 判断寄存器分类时需要考虑子集/超集.
- 各式各样的寄存器标记. 类似1的原因, 在postRA阶段寄存器标记远远多于preRA阶段, 不同的寄存器标签影响寄存器生命周期的计算.
- 候选寄存器的判断. 原则上只要生命周期不冲突的寄存器都可以做候选的替换寄存器, 但是考虑函数调用, live in/out等情况, 实际可替换的候选少于理想情况.
实现分析
AntiDepBreaker不是一个单独的PASS, 而是依附于postRA阶段的调度PASS, 其原因是postRA调度按region划分并构建依赖图, 因此每个region调度前都需要调用AntiDepBreaker. 可以通过选项-mllvm -break-anti-dependencies=none关闭该优化(见lib/CodeGen/PostRASchedulerList.cpp:61).
在开启该优化时也可以选择两种模式: critical与aggressive, 其中前者只会针对关键路径上的反依赖做消除, 后者则会力求消除所有的反依赖, 可以通过上面的选项控制使用哪种模式.
我们以aggressive模式为例来看看如何实现AntiDepBreaker(源码见lib/CodeGen/AggressiveAntiDepBreaker.cpp).
先来看下数据结构的定义: AggressiveAntiDepBreaker定义了两个类(见lib/CodeGen/AggressiveAntiDepBreaker.h), AggressiveAntiDepState与AggressiveAntiDepBreaker.
AggressiveAntiDepState
AggressiveAntiDepState用于在遍历指令的过程中维护寄存器的状态, 其成员如下.
class LLVM_LIBRARY_VISIBILITY AggressiveAntiDepState {
const unsigned NumTargetRegs;
std::vector<unsigned> GroupNodes;
std::vector<unsigned> GroupNodeIndices;
std::multimap<unsigned, RegisterReference> RegRefs;
std::vector<unsigned> KillIndices;
std::vector<unsigned> DefIndices;
};
AggressiveAntiDepState::AggressiveAntiDepState(const unsigned TargetRegs,
MachineBasicBlock *BB)
: NumTargetRegs(TargetRegs), GroupNodes(TargetRegs, 0),
GroupNodeIndices(TargetRegs, 0), KillIndices(TargetRegs, 0),
DefIndices(TargetRegs, 0) {
const unsigned BBSize = BB->size();
for (unsigned i = 0; i < NumTargetRegs; ++i) {
GroupNodeIndices[i] = i;
KillIndices[i] = ~0u;
DefIndices[i] = BBSize;
}
}
- NumTargetRegs是一个常量值, 该值为架构的寄存器总数(
TRI->getNumRegs()), 为其它几个容器成员的初始元素个数. - 容器KillIndices与DefIndices分别用来记录寄存器的kill/define状态, 其下标为寄存器序号, 其值为kill/define该寄存器的指令(在本BB内的)序号. 需要注意的是值~0为特殊值, 分别表示该寄存器未存活/寄存器存活.
- GroupNodes与GroupNodeIndices实现了一个并查集, 用来为具有别名的寄存器分类. 其中后者记录了每个寄存器在分组(前者)中的序号, 前者则保存了同属一个分组的前一元素的序号(当指向自己时为根节点). 在分析的过程中发现某一寄存器存活则将所有别名寄存器都标记为该分组.
- RegRefs记录了寄存器(在一段生命周期内)的所有使用者.
补充: 寄存器的几种状态(关于寄存器状态定义的细节见include/llvm/CodeGen/MachineOperand.h中定义).
- define: 若一条指令写一个寄存器则称指令定义(define)了该寄存器.
- kill: 一个寄存器存在零到若干个使用者, 其中最后一个使用者使用后该寄存器作用消失, 因此称最后一个使用者杀死(kill)了该寄存器.
- dead: 若一个寄存器没有使用者, 则该寄存器为冗余的, 称该定义的寄存器(在被定义的同时)是死亡(dead)的.
- partial define: 若一个寄存器由若干寄存器组成(通常包含两种情况, 一是像X86架构eax/rax这种A寄存器在物理上是B寄存器的一部分, 二是软件上有时将连续的寄存器组合为一个超集), 且其中一部分被定义则称该寄存器为partial define. 其中前者情况在preRA前通常有寄存器A到寄存器B的伪拷贝指令, 后者通常会由一个REQ_SUQUENCE伪指令组合而成, 但是两者在寄存器分配后均被消除, 需要遍历别名寄存器来判断是否是partial define.
- tied: 若一条指令在读一个寄存器的同时又写了它则称这个使用者与定义者是绑定(tied)的.
再看下AggressiveAntiDepState对外暴露的几个接口.
unsigned AggressiveAntiDepState::GetGroup(unsigned Reg) {
unsigned Node = GroupNodeIndices[Reg];
while (GroupNodes[Node] != Node)
Node = GroupNodes[Node];
return Node;
}
void AggressiveAntiDepState::GetGroupRegs(
unsigned Group,
std::vector<unsigned> &Regs,
std::multimap<unsigned, AggressiveAntiDepState::RegisterReference> *RegRefs)
{
for (unsigned Reg = 0; Reg != NumTargetRegs; ++Reg) {
if ((GetGroup(Reg) == Group) && (RegRefs->count(Reg) > 0))
Regs.push_back(Reg);
}
}
unsigned AggressiveAntiDepState::UnionGroups(unsigned Reg1, unsigned Reg2) {
unsigned Group1 = GetGroup(Reg1);
unsigned Group2 = GetGroup(Reg2);
unsigned Parent = (Group1 == 0) ? Group1 : Group2;
unsigned Other = (Parent == Group1) ? Group2 : Group1;
GroupNodes.at(Other) = Parent;
return Parent;
}
unsigned AggressiveAntiDepState::LeaveGroup(unsigned Reg) {
unsigned idx = GroupNodes.size();
GroupNodes.push_back(idx);
GroupNodeIndices[Reg] = idx;
return idx;
}
bool AggressiveAntiDepState::IsLive(unsigned Reg) {
return((KillIndices[Reg] != ~0u) && (DefIndices[Reg] == ~0u));
}
AggressiveAntiDepState主要提供了操作并查集的接口, 其中GetGroup()返回给定寄存器所在的分组, UnionGroups()将两个分组合并, LeaveGroup()将给定寄存器提出分组. 需要注意的是LeaveGroup()在将寄存器踢出分组时并不会修改原有的分组, 而是新建一个分组, 这是因为当前节点可能被别的节点所引用(即在一条链路的中间).
AggressiveAntiDepBreaker
再来看下另一个类AggressiveAntiDepBreaker, 其主要成员是一个指向AggressiveAntiDepState的指针(State)以及一个BitVector(CriticalPathSet), 其基类AntiDepBreaker封装了对外的接口.
class LLVM_LIBRARY_VISIBILITY AggressiveAntiDepBreaker
: public AntiDepBreaker {
MachineFunction &MF;
MachineRegisterInfo &MRI;
const TargetInstrInfo *TII;
const TargetRegisterInfo *TRI;
const RegisterClassInfo &RegClassInfo;
BitVector CriticalPathSet;
AggressiveAntiDepState *State = nullptr;
public:
void StartBlock(MachineBasicBlock *BB) override;
unsigned BreakAntiDependencies(const std::vector<SUnit> &SUnits,
MachineBasicBlock::iterator Begin,
MachineBasicBlock::iterator End,
unsigned InsertPosIndex,
DbgValueVector &DbgValues) override;
void Observe(MachineInstr &MI, unsigned Count,
unsigned InsertPosIndex) override;
void FinishBlock() override;
};
class LLVM_LIBRARY_VISIBILITY AntiDepBreaker {
public:
virtual void StartBlock(MachineBasicBlock *BB) = 0;
virtual unsigned BreakAntiDependencies(const std::vector<SUnit> &SUnits,
MachineBasicBlock::iterator Begin,
MachineBasicBlock::iterator End,
unsigned InsertPosIndex,
DbgValueVector &DbgValues) = 0;
virtual void Observe(MachineInstr &MI, unsigned Count,
unsigned InsertPosIndex) = 0;
virtual void FinishBlock() = 0;
};
AntiDepBreaker包含四个接口, 分别作为调度器代码的四个流程(starBlock/schedule/Observe/finishBlock)的hook, 下面逐一分析.
StartBlock()
在每个Block被调度前首先需要执行StartBlock()做准备工作, 其主要内容为初始化寄存器信息的初始状态.
void AggressiveAntiDepBreaker::StartBlock(MachineBasicBlock *BB) {
State = new AggressiveAntiDepState(TRI->getNumRegs(), BB);
bool IsReturnBlock = BB->isReturnBlock();
std::vector<unsigned> &KillIndices = State->GetKillIndices();
std::vector<unsigned> &DefIndices = State->GetDefIndices();
for (MachineBasicBlock::succ_iterator SI = BB->succ_begin(),
SE = BB->succ_end(); SI != SE; ++SI)
for (const auto &LI : (*SI)->liveins()) {
for (MCRegAliasIterator AI(LI.PhysReg, TRI, true); AI.isValid(); ++AI) {
unsigned Reg = *AI;
State->UnionGroups(Reg, 0);
KillIndices[Reg] = BB->size();
DefIndices[Reg] = ~0u;
}
}
const MachineFrameInfo &MFI = MF.getFrameInfo();
BitVector Pristine = MFI.getPristineRegs(MF);
for (const MCPhysReg *I = MF.getRegInfo().getCalleeSavedRegs(); *I;
++I) {
unsigned Reg = *I;
if (!IsReturnBlock && !Pristine.test(Reg))
continue;
for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) {
unsigned AliasReg = *AI;
State->UnionGroups(AliasReg, 0);
KillIndices[AliasReg] = BB->size();
DefIndices[AliasReg] = ~0u;
}
}
}
函数首先构造并初始化一个AggressiveAntiDepState, 由于调度过程是自底向上(bottom-up)的, 因此初始化时需要考虑本Block的live out. 通常情况下本Block的live out即本Block的后继的live in的集合, 但是在这里还需加上live out的callee saved寄存器. 这是因为记录KillIndices与DefIndices的目的是判断寄存器是否可用, 而live out的callee saved寄存器虽然没有生命周期(没有定义与使用), 但同时也不是可用的寄存器. 这类寄存器包含两块: 对return block而言即所有callee saved寄存器, 对于非return block而言则是未在prolog里保存的callee save的寄存器.
BreakAntiDependencies()
BreakAntiDependencies()是处理反依赖消除的核心代码, 源代码较多这里仅列出几个重要步骤.
unsigned AggressiveAntiDepBreaker::BreakAntiDependencies(
const std::vector<SUnit> &SUnits,
MachineBasicBlock::iterator Begin,
MachineBasicBlock::iterator End,
unsigned InsertPosIndex,
DbgValueVector &DbgValues) {
......
for (MachineBasicBlock::iterator I = End, E = Begin;
I != E; --Count) {
MachineInstr &MI = *--I;
std::set<unsigned> PassthruRegs;
GetPassthruRegs(MI, PassthruRegs);
PrescanInstruction(MI, Count, PassthruRegs);
std::vector<const SDep *> Edges;
const SUnit *PathSU = MISUnitMap[&MI];
AntiDepEdges(PathSU, Edges);
for (unsigned i = 0, e = Edges.size(); i != e; ++i) {
const SDep *Edge = Edges[i];
SUnit *NextSU = Edge->getSUnit();
if ((Edge->getKind() != SDep::Anti) &&
(Edge->getKind() != SDep::Output)) continue;
......
std::map<unsigned, unsigned> RenameMap;
if (FindSuitableFreeRegisters(GroupIndex, RenameOrder, RenameMap)) {
for (std::map<unsigned, unsigned>::iterator
S = RenameMap.begin(), E = RenameMap.end(); S != E; ++S) {
State->UnionGroups(NewReg, 0);
RegRefs.erase(NewReg);
DefIndices[NewReg] = DefIndices[CurrReg];
KillIndices[NewReg] = KillIndices[CurrReg];
State->UnionGroups(CurrReg, 0);
RegRefs.erase(CurrReg);
DefIndices[CurrReg] = KillIndices[CurrReg];
KillIndices[CurrReg] = ~0u;
}
}
}
ScanInstruction(MI, Count);
}
}
bool AggressiveAntiDepBreaker::FindSuitableFreeRegisters(
unsigned AntiDepGroupIndex,
RenameOrderType& RenameOrder,
std::map<unsigned, unsigned> &RenameMap) {
std::vector<unsigned> Regs;
State->GetGroupRegs(AntiDepGroupIndex, Regs, &RegRefs);
for (unsigned i = 0, e = Regs.size(); i != e; ++i) {
unsigned Reg = Regs[i];
if ((SuperReg == 0) || TRI->isSuperRegister(SuperReg, Reg))
SuperReg = Reg;
if (RegRefs.count(Reg) > 0) {
BitVector &BV = RenameRegisterMap[Reg];
BV = GetRenameRegisters(Reg);
}
}
const TargetRegisterClass *SuperRC =
TRI->getMinimalPhysRegClass(SuperReg, MVT::Other);
RenameOrder.insert(RenameOrderType::value_type(SuperRC, Order.size()));
unsigned OrigR = RenameOrder[SuperRC];
unsigned EndR = ((OrigR == Order.size()) ? 0 : OrigR);
unsigned R = OrigR;
do {
for (unsigned i = 0, e = Regs.size(); i != e; ++i) {
if (State->IsLive(NewReg) || (KillIndices[Reg] > DefIndices[NewReg])) {
goto next_super_reg;
} else {
bool found = false;
for (MCRegAliasIterator AI(NewReg, TRI, false); AI.isValid(); ++AI) {
unsigned AliasReg = *AI;
if (State->IsLive(AliasReg) ||
(KillIndices[Reg] > DefIndices[AliasReg])) {
LLVM_DEBUG(dbgs()
<< "(alias " << printReg(AliasReg, TRI) << " live)");
found = true;
break;
}
}
if (found)
goto next_super_reg;
}
......
}
}
}
处理逻辑是从给定的迭代器开始逆序遍历指令, 对于每条指令定义的寄存器分析其定义的寄存器并更新寄存器状态(AggressiveAntiDepState). 然后在判断指令是否存在依赖, 判断打破依赖可能性. 如果确认需要打破依赖则调用FindSuitableFreeRegisters()获取可替换的寄存器列表, 尝试替换寄存器. 最后(对于重命名的情况)调用ScanInstruction()更新寄存器状态. 其中:
- GetPassthruRegs()用来处理单条指令同时包含(对同一寄存器的)定义与使用的特殊情况(即寄存器生命周期pass through这条指令), 对于这类情况寄存器生命周期默认延长(至前一个定义). 什么情况下会产生pass through? 注释已经解释了: 指令包含tied寄存器或隐式使用特殊寄存器的情况.
- PrescanInstruction()用来处理指令定义的寄存器, 并负责更新其状态. 对于每个寄存器定义如果该寄存器当前存活则将所有别名寄存器加入相同分组并更新DefIndices. 这里需要注意的几种特殊情况的处理, 一是dead定义寄存器会先为它生成一个伪的使用者(这步在HandleLastUse()中处理). 原因是dead定义没有使用者, 因此不会更新分组, 而是被延迟到前一定义处理, 导致生命周期变相延长. 二是针对函数调用(或内联汇编或其它特殊寄存器分配需求)的情况, 为维护ABI, 简化处理, 会将定义的寄存器设置为不可替换的寄存器(分组0).
- AntiDepEdges()查询SUnit并返回指令上的反依赖与写依赖. 不是所有的依赖都会做消除, 以下若干种情况不会处理: 如果寄存器是预留寄存器或所属的寄存器类不可分配(MRI.isAllocatable()), 寄存器属于关键路径寄存器但指令又不在关键路径上, 寄存器是隐式寄存器或pass through寄存器或寄存器存在多个反依赖.
- 查找可选寄存器的实现见FindSuitableFreeRegisters(), 其思路是首先通过先前保存的并查集找到被替换寄存器所在的分组, 该分组中可能包含被替换寄存器的超集, 为满足所有寄存器的分配需求需要找到最大的超集寄存器类. 在找到该类后遍历所属该类的寄存器, 查看它们在当前节点是否存活即define与kill状态. 若存活或其定义(DefIndices)小于被替换寄存器的最后的使用(KillIndices)则说明两者生命周期冲突, 不可替换. 否则进行下一步检测: 遍历该寄存器的别名寄存器分析其生命周期是否与被替换寄存器冲突.
- 若成功找到一个候选则执行替换, 替换过程会将所有被替换寄存器的别名寄存器都执行替换: 更新寄存器分组, KillIndices与DefIndices.
- 最后执行ScanInstruction()更新寄存器的live range. 其实现与PrescanInstruction()类似, 但是处理的是use(define在前一步已完成处理).
Observe()与FinishBlock()
比较简单不再赘述.
小结
相比于preRA, (LLVM中)postRA的数据流分析优化较少, 一方面原因是postRA不再维护SSA状态另一方面考虑到复杂的寄存器别名分析. AntiDepBreaker给我们很好的展示了在postRA做变换时需要考虑的若干关键点. 另一方面从代码中也可以看到其分析较为保守(候选寄存器的限定条件), 而其分析处理的情况较多, 因此有时优化结果不理想也是可以预见的.