ComplexDeinterleavingPass

这个文件 ComplexDeinterleavingPass.cpp 是 LLVM 编译器中的一个优化 pass，专门处理 复杂的向量解交错（complex deinterleaving）。该优化的目的是识别并转换可以通过复杂指令表示的向量操作，特别是处理复数的情况。
这个 Pass 乍看上去根本不知道是干什么的, 所以我们必须搞懂这几个概念：

解交错
复数
shuffle 操作

Deinterleave（解交错）：与 shuffle 相反，解交错是将多个交错的向量分离成独立的分量。例如，如果一个向量是 [a1, b1, a2, b2]，那么解交错操作可能会将它分离成两个向量 [a1, a2] 和 [b1, b2]。
复合节点：复合节点 是指在图结构中代表一个可以通过一条单独的复杂指令来替代的操作。比如，复合节点表示的是一个操作，可能涉及多个向量的交错和解交错过程，目标是将这些操作合并成一条复合指令，从而避免生成多个低效的指令。
Shuffle（交错）：在 SIMD 或向量化的计算中，shuffle 是一种操作，旨在重新排列多个元素在向量中的顺序。例如，将一个向量的元素打散并重新排序。
复杂解交错图（ComplexDeinterleavingGraph）：这个图的数据结构用于表示与复合节点相关的所有操作。每个节点表示一个复合指令，在图中还包含所有相关的操作数和操作步骤。通过这个图，LLVM 可以有效地将多个 shuffle 和 deinterleave 操作合并为目标架构支持的单条复杂指令，从而提高性能。

然后来看一个例子：
假设有如下复数解包代码（伪IR）：

%real = shufflevector <4 x float> %vec, undef, <0, 2>
%imag = shufflevector <4 x float> %vec, undef, <1, 3>

Pass会识别该模式，将其替换为：

%deinterleaved = intrinsic.vector.deinterleave2 <2 x float>, %vec

从而减少指令数量，提高执行效率。

从源码上看，代码量居中（2000 行+）。
其依赖分析 Pass：auto &TLI = AM.getResult<llvm::TargetLibraryAnalysis>(F);：主要用来为 特定目标架构 提供有关 目标库（如数学库函数、标准库函数等）调用的信息。LLVM 的不同后端（目标架构）可以通过它来检查代码中哪些库函数（如 sqrt、sin、log 等）是可用的，并且可以进行相应的优化（比如使用内建指令替换库函数调用）。

PreservedAnalyses ComplexDeinterleavingPass::run(Function &F,  
                                                 FunctionAnalysisManager &AM) {  
  const TargetLowering *TL = TM->getSubtargetImpl(F)->getTargetLowering();  
  auto &TLI = AM.getResult<llvm::TargetLibraryAnalysis>(F);  
  if (!ComplexDeinterleaving(TL, &TLI).runOnFunction(F))  
    return PreservedAnalyses::all();  
  
  PreservedAnalyses PA;  
  PA.preserve<FunctionAnalysisManagerModuleProxy>();  
  return PA;  
}

bool ComplexDeinterleaving::runOnFunction(Function &F) {  
  // ... 
  
  if (!TL->isComplexDeinterleavingSupported()) {  
    LLVM_DEBUG(  
        dbgs() << "Complex deinterleaving has been disabled, target does "  
                  "not support lowering of complex number operations.\n");  
    return false;  
  }  
  
  bool Changed = false;  
  for (auto &B : F)  
    Changed |= evaluateBasicBlock(&B);  
  
  return Changed;  
}

所以可以知道核心流程如下：

bool ComplexDeinterleaving::evaluateBasicBlock(BasicBlock *B) {  
  ComplexDeinterleavingGraph Graph(TL, TLI);  
  if (Graph.collectPotentialReductions(B))  
    Graph.identifyReductionNodes();  
  
  for (auto &I : *B)  
    Graph.identifyNodes(&I);  
  
  if (Graph.checkNodes()) {  
    Graph.replaceNodes();  
    return true;  
  }  
  
  return false;  
}