后端Pass简介——BreakFalseDeps

BreakFalseDeps

这个 LLVM pass 主要是用于识别和解决机器代码中的虚假依赖（false dependencies）问题。虚假依赖是指由于寄存器的使用，某些指令看起来像是彼此有依赖关系，实际上它们之间并没有数据依赖关系。这些虚假依赖会导致不必要的执行暂停，特别是在现代的支持乱序执行的 CPU 上。
所以这个 pass 会检测并消除这些虚假依赖，使得指令可以并行执行，从而提高程序性能。
举个例子说明什么是虚假依赖，假设有以下指令：

1. R1 = R2 + R3   // 指令1：R1 = R2 + R3
2. R4 = R1 + R5   // 指令2：R4 = R1 + R5
3. R6 = R2 + R3   // 指令3：R6 = R2 + R3

在上面的例子中，指令1 写入 R1，然后指令2 读取 R1，==即便 R6 计算与 R1 没有任何关系，也会因为 R1 发生写入和读取的冲突，导致指令3 需要等待 R1 写入完成。==实际上，指令3 并不依赖于 R1，它只是简单地读取 R2 和 R3，但由于硬件或编译器认为 R1 是共享资源，指令3 可能被延迟执行，造成了虚假依赖。
例子二（部分寄存器更新）：

1. R1[31:0] = R2 + R3   // 指令1：更新 R1 的低 32 位
2. R4 = R1[63:32] + R5  // 指令2：依赖 R1 的高 32 位

虽然指令2 只依赖于 R1 的高 32 位，但指令1 却更新了 R1 的低 32 位，可能导致指令2 被错误地认为依赖于指令1 的写操作，从而造成指令2 不必要的执行等待，这是一个典型的虚假依赖。

---

从源码来看：

bool BreakFalseDeps::runOnMachineFunction(MachineFunction &mf) {  
  if (skipFunction(mf.getFunction()))  
    return false;  
  MF = &mf;  
  TII = MF->getSubtarget().getInstrInfo();  
  TRI = MF->getSubtarget().getRegisterInfo();  
  RDA = &getAnalysis<ReachingDefAnalysis>();  
  
  RegClassInfo.runOnMachineFunction(mf);  
  
  LLVM_DEBUG(dbgs() << "********** BREAK FALSE DEPENDENCIES **********\n");  
  
  // Skip Dead blocks due to ReachingDefAnalysis has no idea about instructions  
  // in them.  df_iterator_default_set<MachineBasicBlock *> Reachable;  
  for (MachineBasicBlock *MBB : depth_first_ext(&mf, Reachable))  
    (void)MBB /* Mark all reachable blocks */;  
  
  // Traverse the basic blocks.  
  for (MachineBasicBlock &MBB : mf)  
    if (Reachable.count(&MBB))  
      processBasicBlock(&MBB);  
  
  return false;  
}

该 pass 依赖于到达定义分析（ReachingDefAnalysis）。
for (MachineBasicBlock *MBB : depth_first_ext(&mf, Reachable)) 深度优先来访问所有基本块，然后标记是否可到达，然后再依次进行处理。

• pickBestRegisterForUndef: 该函数的目标是处理虚假依赖，特别是针对“未定义寄存器读取”问题。它会检查指令中是否存在“undef”寄存器，并尝试用一个真正依赖的寄存器替换它。如果无法找到一个有效的依赖寄存器，它会选择一个具有更高清除优先级的寄存器。
• shouldBreakDependence: 该函数通过检查寄存器的清除时间（即寄存器何时变得有效）来判断是否应该打破虚假依赖。它根据清除时间和偏好值来决定是否需要“打破”依赖。
• processDefs: 处理指令的定义操作，并检查其中是否存在虚假的依赖关系，特别是针对“undef”寄存器的依赖。如果发现虚假依赖，它会尝试消除。
• processUndefReads: 该函数通过回溯遍历基本块来精确计算寄存器的活跃性，并打破虚假的依赖关系，特别是在遇到“未定义寄存器读取”的时候。

清除优先级（Clearance）指的是一个寄存器的值变得可用或有效的时间点。在指令执行时，寄存器的值可能需要等待某些操作完成才能被认为是“有效的”。这种等待时间被称为“清除优先级”或“清除时间”。具体来说，清除优先级表示的是在一个指令使用寄存器值之前，该寄存器值已经经过了多少个操作，直到它被认为是有效和可用的。

举个例子说明清除优先级：
假设有以下几条指令：

1. R1 = R2 + R3   // 指令1：计算 R2 和 R3 的和并存入 R1 
2. R4 = R1 + R5   // 指令2：依赖于 R1`

• 在 指令1 执行时，R1 被写入，但它的值仅在 指令2 执行时才变得有效。换句话说，R1 的值直到 R1 = R2 + R3 计算完成后才能被 R4 = R1 + R5 正确使用。因此，R1 的清除优先级为“指令1”完成后。
  **清除优先级与依赖性：
• 在执行指令时，如果后续指令依赖于寄存器的值，而寄存器的值尚未完成更新或清除，程序会出现“依赖冲突”。
  • 清除优先级可以帮助编译器或处理器确定什么时候寄存器的值是有效的。清除优先级较低的寄存器值会影响后续指令的执行时机。