LLVM 中的指令調度器及其工作過程

概述

LLVM 中實現了多種指令調度器，分別作用于后端流程的不同階段，包括指令選擇階段的指令調度器、寄存器分配前的指令調度器和寄存器分配后的指令調度器

這三類調度器都有llc命令行選項可以控制其使能或禁用

在寄存器分配前，基本塊中的操作數仍以虛擬寄存器表示，約束較少，指令調度的自由度較高，但要考慮調度結果對寄存器分配的影響。例如，如果虛擬寄存器的定值和使用相距較遠，虛擬寄存器的生存期可能較長，這會增加寄存器分配的難度

如果能通過指令重排序，拉近虛擬寄存器的定值和使用之間的距離，可以使寄存器分配難度降低

調度方向一般分為三種，即自頂向下(top down)、自底向上(bottom up) 或雙向(bidirectioin) 調度

自底向上策略較為簡單，并且這種策略已有很多成熟編譯時優化。雙向調度策略，即自頂向下、自底向上同時進行，再從中選出最好的候選指令

如果使用自頂向下調度策略，則以數據依賴圖中的入口節點(entry node)為調度起始節點；如果使用自底向上調度策略，則以數據依賴圖中的出口節點(exit node) 為調度起始節點

1. 指令選擇階段的調度器

所有調度器的實現類抖繼承自ScheduleDAG類。ScheduleDAG類的兩個子類分別是ScheduleDAGSDNodes類和ScheduleDAGInsts類中

其中, ScheduleDAGSDNodes 類是指令選擇調度器實現類的基類，其調度對象是SDNode實例;ScheduleDAGInstrs 類是寄存器分配前和寄存器分配后的調度器實現類的基類，其調度對象是MachineInstr實例

指令選擇通過拓撲排序將DAG轉為MachineInstr列表，并結合其他啟發式策略，決定MachineInstr列表的指令順序。作為指令選擇過程的一部分，指令選擇階段的指令調度器由ScheduleDAGRRList(其中的RR為Register Reduction 的縮寫)類實現

ScheduleDAGRRList 類繼承自 ScheduleDAGSDodes類，是LLVM中一種較傳統的指令調度器，其目的是將SelectionDAG 中的 SDNode實例轉換為MachineInstr 實例。因此，ScheduleDAGRRList 類實現的是一種DAG 調度器

ScheduleDAGRRList 類實現自底向上策略。ScheduleDAGRRList類采用啟發式調度策略決定MachineInstr列表中的順序。啟發式調度策略的基本概念是通過結構上層的代價函數對調度候選指令排序，排序的策略包括源順序(source order)、寄存器壓力敏感、物理寄存器復制優先、延遲敏感

ScheduleDAGRRList 類進行調度的基本方法是使用優先級隊列為就緒列表，并保存可用節點。然后按優先級順序每次從次優先級隊列中取出一個節點，并檢查其調度合法性

如果節點合法則將該節點發出，針對不同策略，在ScheduleDAGRRList類的C++實現文件中注冊了四種DAG調度(代碼見<llvm_root>/livm/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp):

burrListDAGScheduler
sourceListDAGScheduler
hybridListDAGScheduler
ILPListDAGScheduler

其中，burrListDAGScheduler(其中的burr為bottom-up register reduction的縮寫) 是一種減少寄存器用量的列表調度器

sourceListDAGScheduler 與 burrListDAGScheduler 類似，但是按源代碼順序調度的列表調度器

hybridListDAGScheduler 是寄存器壓力敏感的列表調度器，且其力圖在延遲和寄存器壓力間保持平衡

ILPListDAGScheduler 也是寄存器壓力敏感的列表調度器，但其力圖在指令級并行度和寄存器壓力間保持平衡

前己述及，LLVM中的指令選擇功能在SelectionDAGISel 類中實現。該類繼承自MachineFunctionPass類，是基于SelectionDAG的指令選擇pass的公共基類

在SelectionDAGISel類的SelectBasicBlock()函數中，其最后一步是調用 CodeGenAndEmitDAG() 函數。該函數在調用 DoInstrucntionSelection()函數完成指令選擇后, 首先調用 CreateScheduler()函數生成指令調度器，然后調用調度器的Run()函數，將降級后的DAG轉換為機器指令。代碼實現如下:

void SelectionDAGISel::CodeGenAndEmitDAG() {...DoInstructionSelection();...// Schedule machine code.ScheduleDAGSDNodes *Scheduler = CreateScheduler();{NamedRegionTimer T("sched", "Instruction Scheduling", GroupName,GroupDescription, TimePassesIsEnabled);Scheduler->Run(CurDAG, FuncInfo->MBB);}
}

其中，CreateScheduler() 函數通過ISHeuristic 命令行選項決定使用何種指令調度器

ScheduleDAGSDNodes *SelectionDAGISel::CreateScheduler() {return ISHeuristic(this, OptLevel);
}static cl::opt<RegisterScheduler::FunctionPassCtor, false,RegisterPassParser<RegisterScheduler>>
ISHeuristic("pre-RA-sched",cl::init(&createDefaultScheduler), cl::Hidden,cl::desc("Instruction schedulers available (before register"" allocation):"));

如果llc的命令行選項pre-RA-sched 指定了調度器，則使用指定調度器；否則，調用createDefaultScheduler()函數，生成適合目標后端的指令調度器

createDefaultScheduler() 函數根據后端設置的調度偏好生成對應的調度器，這些調度偏好對應了調度時采用的不同啟發式策略

ScheduleDAGSDNodes* createDefaultScheduler(SelectionDAGISel *IS,CodeGenOpt::Level OptLevel) {const TargetLowering *TLI = IS->TLI;const TargetSubtargetInfo &ST = IS->MF->getSubtarget();// Try first to see if the Target has its own way of selecting a schedulerif (auto *SchedulerCtor = ST.getDAGScheduler(OptLevel)) {return SchedulerCtor(IS, OptLevel);}if (OptLevel == CodeGenOpt::None ||(ST.enableMachineScheduler() && ST.enableMachineSchedDefaultSched()) ||TLI->getSchedulingPreference() == Sched::Source)return createSourceListDAGScheduler(IS, OptLevel);if (TLI->getSchedulingPreference() == Sched::RegPressure)return createBURRListDAGScheduler(IS, OptLevel);if (TLI->getSchedulingPreference() == Sched::Hybrid)return createHybridListDAGScheduler(IS, OptLevel);if (TLI->getSchedulingPreference() == Sched::VLIW)return createVLIWDAGScheduler(IS, OptLevel);if (TLI->getSchedulingPreference() == Sched::Fast)return createFastDAGScheduler(IS, OptLevel);if (TLI->getSchedulingPreference() == Sched::Linearize)return createDAGLinearizer(IS, OptLevel);assert(TLI->getSchedulingPreference() == Sched::ILP &&"Unknown sched type!");return createILPListDAGScheduler(IS, OptLevel);}

目標后端可以為不同的子目標設置不同的調度偏好。例如，AMDGPU后端為其R600和SI 子目標分別設置調度偏好為Source和RegPressure:

R600ISelLowering.cpp

R600TargetLowering::R600TargetLowering(const TargetMachine &TM,const R600Subtarget &STI): AMDGPUTargetLowering(TM, STI), Subtarget(&STI), Gen(STI.getGeneration()) {setSchedulingPreference(Sched::Source);
}SITargetLowering::SITargetLowering(const TargetMachine &TM,const GCNSubtarget &STI): AMDGPUTargetLowering(TM, STI),Subtarget(&STI) {setSchedulingPreference(Sched::RegPressure);      
}

在ScheduleDAGRRList.cpp 文件中，為不同啟發式策略實現了不同調度器的生成函數，并在生成函數中生成了對應的優先級隊列，而且將優先級隊列作為 ScheduleDAGRRList 實例的初始化參數

例如，在上述createDefaultScheduler()函數中，針對RegPressure調度偏好，調用burrListDAGScheduler調度器生成函數 createBURRListDAGScheduler()

該函數實現代碼如下:

ScheduleDAGSDNodes *
llvm::createBURRListDAGScheduler(SelectionDAGISel *IS,CodeGenOpt::Level OptLevel) {...BURegReductionPriorityQueue *PQ =new BURegReductionPriorityQueue(*IS->MF, false, false, TII, TRI, nullptr);ScheduleDAGRRList *SD = new ScheduleDAGRRList(*IS->MF, false, PQ, OptLevel);PQ->setScheduleDAG(SD);return SD;
}

其中，BURegReductionPriorityQueue 為 RegReductionPriorityQueue 類模板別名。 RegReductionPriorityQueue 類通過模板參數自定義優先調度的排序標準，實現了調度器 burrListDAGScheduler 中使用的優先級隊列

相應地，sourceListDAGScheduler、hybridListDAGScheduler 和 ILPListDAGScheduler 都有各自對應的優先級隊列實現類

生成指令調度后，CodeGenAndEmitDAG() 函數中調用的調度器Run()函數將進一步調用目標后端調度器的 Schedule()函數，也就是ScheduleDAGRRList 類重寫的 Schedule() 函數

SelectionDAGISel.cpp

void SelectionDAGISel::CodeGenAndEmitDAG() {...// Schedule machine code.ScheduleDAGSDNodes *Scheduler = CreateScheduler();{NamedRegionTimer T("sched", "Instruction Scheduling", GroupName,GroupDescription, TimePassesIsEnabled);Scheduler->Run(CurDAG, FuncInfo->MBB);}...
}

ScheduleDAGSDNodes.cpp

/// Run - perform scheduling.
///
void ScheduleDAGSDNodes::Run(SelectionDAG *dag, MachineBasicBlock *bb) {BB = bb;DAG = dag;// Clear the scheduler's SUnit DAG.ScheduleDAG::clearDAG();Sequence.clear();// Invoke the target's selection of scheduler.Schedule();
}

ScheduleDAGRRList 類的主要功能可通過重寫Schedule() 函數實現，包括建立指令調度所需的依賴圖和執行列表調度兩個部分。

建立依賴圖由ScheduleDAGSDNodes 類的 BuildSchedGraph() 函數完成

這里依賴圖是根據輸入的SelectionDAG對象構建的SUnit(Scheduling Unit)圖。SUnit 圖與SelectionDAG相似，但不包括與調度無關的節點，而且，SUnit 圖中的每個SUnit對象表示粘合在一起的SDNode 節點

ScheduleDAGRRList 類定義及其成員變量AvailableQueue(表示就緒隊列)定義、成員函數Schedule() 聲明如下:

/// Schedule - Schedule the DAG using list scheduling.
void ScheduleDAGRRList::Schedule() {...// Build the scheduling graph.BuildSchedGraph(nullptr);...AvailableQueue->initNodes(SUnits);HazardRec->Reset();// Execute the actual scheduling loop.ListScheduleBottomUp();AvailableQueue->releaseState();....
}

BuildSchedGraph() 函數通過聚類、生成SUnit節點、添加調度邊三個步驟建立SUnit圖

/// BuildSchedGraph - Build the SUnit graph from the selection dag that we
/// are input.  This SUnit graph is similar to the SelectionDAG, but
/// excludes nodes that aren't interesting to scheduling, and represents
/// glued together nodes with a single SUnit.
void ScheduleDAGSDNodes::BuildSchedGraph(AAResults *AA) {// Cluster certain nodes which should be scheduled together.ClusterNodes();// Populate the SUnits array.BuildSchedUnits();// Compute all the scheduling dependencies between nodes.AddSchedEdges();
}

首先，ClusterNodes() 函數將某些需要放在一起調度的節點聚類在一起

例如，對于多個基址相同但偏移量不同，且偏移量相距不遠的加載(load) 操作節點
可以通過在加載操作節點間增加粘合依賴，將這些加載操作節點聚類在一起，保證這些加載操作節點以地址升序調度，以此提高緩存局部性
聚類中的加載節點基址是否相同，聚類中加載節點數量和聚類中不同加載節點間的偏移量距離由各后端通過areLoadsFromSameBasePtr() 和 shouldScheduleLoadsNear() 函數實現自行決定
例如, AMDGPU 后端要求聚類的加載節點不超過16個，聚類在一起的加載節點間的偏移量距離不超過64字節

其次，BuildSchedUnits() 函數為SDNode 節點(包括粘合在一起的多個SDNode節點)，建立對應的SUnit節點

但是對于某些節點，如ConstantSDNode、RegisterSDNode、GlobalAddressSDNode等，因與調度無關，被稱為被動節點(passive node), 被動節點不需要建立對應的SUnit節點
此處還會為每個SUnit節點計算延遲值(Latency)，該延遲值可用于設置后續的調度依賴延遲。如果當前SUnit 節點中包含了多個聚類的SDNode節點，則將聚類中所有SDNode 節點的延遲之和作為當前SUnit節點的延遲值
各后端可通過實現各自的getInstrLatency()接口自行決定計算延遲值的方法
例如, AMDGPU 后端的 R600子目標將延遲值固定設置為2，SI子目標則通過指令調度機器模型計算延遲值

最后，AddSchedEdges() 根據SUnit 節點間的調度依賴，在SUnit 節點間增加邊

這里涉及的調度依賴分為Barrier和Data兩種
Barrier 依賴對應操作數的值類型為MVT::Other(表示兩個SDNode 節點間通過非數據流鏈相連)
除MVT::Other 以外的其他值類型對應的是Data 依賴
對于Barrier 依賴，其延遲固定設置為1。對于Data依賴，其延遲為BuildSchedUnits()函數中計算得到的SUnit節點延遲值

建立依賴圖， Schedule() 函數繼續調用AvailableQueue的initNodes() 函數完成隊列初始化

AvailableQueue 是由其父類SchedulingPriorityQueue 指針指向的子類對象。 SchedulingPriorityQueue 類可將不同的優先級計算算法插入列表調度程序，并實現標準優先級隊列接口，確保Sunit 節點能以任意順序插入，并按定義的優先級順序返回

優先級的計算和隊列的表示完全取決于子類實現

AvailableQueue 具體指向哪個子類對象，由ScheduleDAGRRList類提供的調度器生成函數決定。例如，對于burrListDAGScheduler 調度器，AvailableQueue指向的是 BURegReductionPriorityQueue(RegReductionPriorityQueue的別名)類對象

RegReductionPriorityQueue類可根據SUnit節點的Sethi-Ullman值作為優先級(Sethi-Ullman值越小，優先級越高)進行調度，以減少寄存器壓力

RegReductionPriorityQueue 類的基類RegReductionPQBase中重寫了initNodes()函數，其中調用CalcNodeSethiUllmanNumber()函數實現了SUnit節點的Sethi-Ullman值計算

Sethi-Ullman算法是一種最小化寄存器占用量的調度算法，并可減少中間值溢出及內存恢復的代價

Sethi-Ullman 值的計算方法是遍歷當前SUnit節點的所有前驅節點(PreSU)，如果發現某個前驅節點的Sethi-Ullman值大于當前SUnit節點的Sethi-Ullman值，則將當前SUnit節點的Sethi-Ullman值設置為該前驅節點的Sethi-Ullman值

否則，當前SUnit節點的Sethi-Ullman值增加1。隨后，列表調度的執行由ScheduleDAGRRList 類實現的 ListScheduleBottomUp() 函數完成，代碼實現如下:

void ScheduleDAGRRList::ListScheduleBottomUp() {// Release any predecessors of the special Exit node.ReleasePredecessors(&ExitSU);...while (!AvailableQueue->empty() || !Interferences.empty()) {SUnit *SU = PickNodeToScheduleBottomUp();AdvancePastStalls(SU);ScheduleNodeBottomUp(SU);while (AvailableQueue->empty() && !PendingQueue.empty()) {// Advance the cycle to free resources. Skip ahead to the next ready SU.assert(MinAvailableCycle < std::numeric_limits<unsigned>::max() &&"MinAvailableCycle uninitialized");AdvanceToCycle(std::max(CurCycle + 1, MinAvailableCycle));}}// Reverse the order if it is bottom up.std::reverse(Sequence.begin(), Sequence.end());
}

ListScheduleBottomUp() 函數是自底向上列表調度的主循環。其中，ReleasePredecessors()函數遍歷出口節點ExitSU(因為調度方向自底向上，所以從出口節點開始遍歷)的每一前驅節點，并遞減這些前驅節點的NumSucessLeft值，NumSuccsLeft值表示未調度的后繼節點數量

如果某前驅節點的NumSuccsLeft 值到達零，表示該前驅節點的所有后繼節點都被調用，則該前驅節點可以被添加到就緒隊列AvailableQueue等待調度，并將ExitSU 節點的時鐘周期界限(代碼中稱為 Height) 與前驅節點的ExitSU 節點間的連接邊延遲相加，以二者相加的和更新前驅節點的Height

Height 是在不導致流水線停頓的前提下，可以調度前驅節點的時鐘周期。然后，ReleasePredecessors() 函數還會更新兩個指針數組LiveRegDefs 和 LiveRegGens

LiveRegDefs 是物理寄存器定值集合，其中的每個元素記錄了物理寄存器的定值。相應地，LiveRegGens是物理寄存器使用集合，其中的每個元素記錄了物理寄存器的使用，例如，對下面節點序列

flags = (3) add
flags = (2) addc flags
flags = (1) addc flags

LiveRegDefs 中與物理寄存器flags對應的元素(即LiveRegDefs[flags])值為3，LiveRegGens中與物理寄存器flags對應的元素(即LiveRegGens[flags]) 值為1

在調度時，必須先調度LiveRegDefs中的節點，然后才能調度其他修改寄存器的節點。LiveRegDefs 和 LiveRegGens這兩個數組可用于寄存器的干擾檢查

/// Return a node that can be scheduled in this cycle. Requirements:
/// (1) Ready: latency has been satisfied
/// (2) No Hazards: resources are available
/// (3) No Interferences: may unschedule to break register interferences.
SUnit *ScheduleDAGRRList::PickNodeToScheduleBottomUp() {SUnit *CurSU = AvailableQueue->empty() ? nullptr : AvailableQueue->pop();auto FindAvailableNode = [&]() {while (CurSU) {SmallVector<unsigned, 4> LRegs;if (!DelayForLiveRegsBottomUp(CurSU, LRegs))break;LLVM_DEBUG(dbgs() << "    Interfering reg ";if (LRegs[0] == TRI->getNumRegs()) dbgs() << "CallResource";else dbgs() << printReg(LRegs[0], TRI);dbgs() << " SU #" << CurSU->NodeNum << '\n');auto [LRegsIter, LRegsInserted] = LRegsMap.try_emplace(CurSU, LRegs);if (LRegsInserted) {CurSU->isPending = true;  // This SU is not in AvailableQueue right now.Interferences.push_back(CurSU);}else {assert(CurSU->isPending && "Interferences are pending");// Update the interference with current live regs.LRegsIter->second = LRegs;}CurSU = AvailableQueue->pop();}};...
}

PickNodeToScheduleBottomUp() 函數可以從就緒隊列 AvailableQueue 中取出當前 SUnit 節點，并檢查其延遲、干擾是否滿足調度要求

當前SUnit 節點可以調用需要滿足的要求有三項：第一，當前時鐘周期滿足當前SUnit 節點延遲要求；第二，有滿足調度的可用資源；第三，不存在寄存器干擾

如果上述三項要求都滿足，且其前驅節點的計數減少到零，則調用 ScheduleNodeBottomUp() 函數將當前SUnit 節點加入 AvailableQueue 中調度，并更新流水線、計分板、寄存器壓力、LiveRegDefs、LiveRegGens等狀態

ScheduleNodeBottomUp()函數通過 ScheduleHazardRecognizer 對象HazardRec 調用指令發射函數 EmitInstrunction(), ScheduleHazardRecognizer 對象決定是否應在當前時鐘周期發射指令，并且在當前時鐘周期發射指令一旦導致流水線停頓，是否發射其他就緒指令，或者插入空操作(nop)