LLVM 中的指令调度器及其工作过程

标签：LLVM 函数调度指令 SUnit 寄存器节点

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 scheduler
    if (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)

2. 寄存器分配前的调度器

寄存器分配前指令调度器将DAG 中的节点拓扑结构排序。寄存器分配高度依赖于寄存器分配前指令调度器产生的指令顺序，该指令顺序决定了寄存器压力，即同时处于活动状态且必须分配给不同物理寄存器的虚拟寄存器的数量

因此，寄存器分配前指令调度必须最小化寄存器压力以优化性能

寄存器分配前调度器的实现类是 ScheduleDAGMILive 类(实现代码见<llvm_root>/llvm/lib/GodeGen/MachineScheduler.cpp)

ScheduleDAGMILive 类是ScheduleDAGMI 类的子类，而ScheduleDAGMI 类又是 ScheduleDAGInstrs 的子类

ScheduleDAGMILive 类中实现了寄存器分配前调度器和寄存器分配后调度器的共用功能，并可以根据给定的MachineSchedStrategy 策略接口调度机器指令，为配置调度器提供更多灵活性

和ScheduleDAGMI 相比，

标签：LLVM,函数,调度,指令,SUnit,寄存器,节点
From： https://blog.csdn.net/weixin_40398522/article/details/140082212

LLVM 中的指令调度器及其工作过程