概述

什么是 VPlan

VPlan (Vectorization Plan) 是 LLVM 循环向量化器中的核心数据结构，用于表示向量化候选方案。它允许在生成实际 LLVM IR 之前，对向量化策略进行规划、优化和成本评估。

VPlan 的设计目标

1. 分离关注点：将向量化策略规划与 IR 生成分离
2. 可优化性：在 VPlan 层面进行优化，避免直接修改 IR
3. 成本评估：在生成 IR 前评估不同向量化策略的成本
4. 可扩展性：支持多种向量化场景（内层循环、外层循环、SLP 等）

整体架构

原始 IR Loop
    ↓
构建 VPlan0 (基础 VPlan)
    ↓
应用 VPlan 变换 (优化、调整)
    ↓
成本评估与选择最佳 VPlan
    ↓
执行 VPlan → 生成向量化 IR

核心概念

1. VPBlockBase - 控制流图节点

VPlan 使用层次化控制流图 (Hierarchical CFG) 来表示程序结构：

// VPBlockBase 是所有块的基类
class VPBlockBase {
  SmallVector<VPBlockBase *, 1> Predecessors;  // 前驱块
  SmallVector<VPBlockBase *, 1> Successors;   // 后继块
  VPRegionBlock *Parent = nullptr;             // 父区域
  VPlan *Plan = nullptr;                        // 所属 VPlan
};

三种块类型：

1. VPBasicBlock: 基本块，包含 Recipe 列表
2. VPRegionBlock: 区域块，包含嵌套的 CFG（用于表示循环或复制区域）
3. VPIRBasicBlock: IR 基本块包装，直接对应原始 IR 中的基本块

2. VPRecipeBase - 指令表示

Recipe 表示 VPlan 中要生成的指令或操作：

class VPRecipeBase {
  VPBasicBlock *Parent;           // 所属基本块
  SmallVector<VPValue *, 2> Operands;  // 操作数
};

主要 Recipe 类型：

• VPInstruction: 通用指令（add, sub, mul 等）
• VPWidenRecipe: 向量化扩展指令
• VPWidenLoadRecipe / VPWidenStoreRecipe: 向量化内存操作
• VPReplicateRecipe: 复制指令（在多个通道执行）
• VPReductionRecipe: 归约操作
• VPHeaderPHIRecipe: 循环头部的 PHI 节点

3. VPValue - 值表示

VPValue 表示 VPlan 中的值，类似于 LLVM IR 中的 Value：

class VPValue {
  SmallVector<VPUser *, 2> Users;  // 使用该值的用户
};

三种 VPValue 类型：

1. VPIRValue: 包装原始 IR 中的 Value
2. VPRecipeValue: 由 Recipe 定义的值
3. VPSymbolicValue: 符号值（如 VF, UF, TripCount）

4. VPTransformState - 执行状态

执行 VPlan 时维护的状态：

struct VPTransformState {
  ElementCount VF;                    // 向量化因子
  IRBuilderBase &Builder;             // IR 构建器
  VPlan *Plan;                        // 当前执行的 VPlan
  DenseMap<VPValue *, Value *> VPV2Vector;  // VPValue → 向量值映射
  DenseMap<VPValue *, SmallVector<Value *, 2>> VPV2Scalars;  // VPValue → 标量值映射
  VPlanCFG CFG;                       // CFG 状态
};

VPlan 数据结构

VPlan 类结构

class VPlan {
  VPBlockBase *Entry;                 // 入口块
  VPIRBasicBlock *ScalarHeader;       // 标量循环头
  SmallVector<VPIRBasicBlock *> ExitBlocks;  // 退出块
  
  // Live-in 值
  SmallVector<VPIRValue *> LiveIns;
  
  // 符号值
  VPSymbolicValue VF;                  // 向量化因子
  VPSymbolicValue VFxUF;              // VF * UF
  VPSymbolicValue VectorTripCount;     // 向量化行程计数
  VPValue *TripCount = nullptr;       // 原始行程计数
  VPSymbolicValue *BackedgeTakenCount = nullptr;  // 回边计数
  
  // 向量化参数
  SmallVector<ElementCount> VFs;     // 支持的 VF 范围
  SmallVector<unsigned> UFs;          // 支持的 UF 范围
};

层次化 CFG 示例

VPlan Entry (VPIRBasicBlock)
  │
  ├─→ Vector Preheader (VPBasicBlock)
  │     │
  │     └─→ Vector Loop Region (VPRegionBlock)
  │           │
  │           ├─→ Vector Header (VPBasicBlock)
  │           │     ├─ Recipe: VPCanonicalIVPHIRecipe
  │           │     ├─ Recipe: VPWidenLoadRecipe
  │           │     ├─ Recipe: VPWidenRecipe (add)
  │           │     └─ Recipe: VPWidenStoreRecipe
  │           │
  │           └─→ Vector Latch (VPBasicBlock)
  │                 └─ Recipe: BranchOnCount
  │
  └─→ Middle Block (VPBasicBlock)
        │
        └─→ Scalar Preheader (VPIRBasicBlock)
              │
              └─→ Scalar Loop (VPIRBasicBlock)
                    │
                    └─→ Exit Blocks (VPIRBasicBlock)

VPlan 构建流程

阶段 1: 构建 VPlan0

VPlanTransforms::buildVPlan0() 创建初始 VPlan：

// 伪代码示例
VPlan* buildVPlan0(Loop *TheLoop, ...) {
  VPlan *Plan = new VPlan(TheLoop);
  
  // 1. 创建入口块（包装原始循环的 preheader）
  Plan->setEntry(createVPIRBasicBlock(TheLoop->getLoopPreheader()));
  
  // 2. 创建标量循环头
  Plan->ScalarHeader = createVPIRBasicBlock(TheLoop->getHeader());
  
  // 3. 创建退出块
  for (BasicBlock *ExitBB : TheLoop->getUniqueExitBlocks())
    Plan->ExitBlocks.push_back(createVPIRBasicBlock(ExitBB));
  
  // 4. 创建向量循环区域
  VPRegionBlock *VectorLoopRegion = Plan->createLoopRegion(...);
  
  // 5. 将原始 IR 指令转换为 VPInstruction
  for (BasicBlock *BB : TheLoop->blocks()) {
    VPBasicBlock *VPBB = ...;
    for (Instruction &I : *BB) {
      VPInstruction *VPI = VPIRInstruction::create(I);
      VPBB->appendRecipe(VPI);
    }
  }
  
  return Plan;
}

VPlan0 的特点：

• 直接映射原始 IR 结构
• 使用 VPInstruction 包装原始指令
• 包含基本的 CFG 骨架（preheader, loop, exit）

阶段 2: 识别和转换 Recipe

VPlanTransforms::tryToConvertVPInstructionsToVPRecipes() 将通用 VPInstruction 转换为专门的 Recipe：

// 示例：转换 Load 指令
if (LoadInst *Load = dyn_cast<LoadInst>(Inst)) {
  // 创建 VPWidenLoadRecipe 替代 VPInstruction
  NewRecipe = new VPWidenLoadRecipe(
    *Load, 
    Ingredient->getOperand(0),  // 地址
    nullptr,                     // Mask（如果有）
    false,                       // Consecutive
    false,                       // Reverse
    *VPI,
    Ingredient->getDebugLoc()
  );
  
  // 替换原指令
  NewRecipe->insertBefore(&Ingredient);
  VPV->replaceAllUsesWith(NewRecipe->getVPSingleValue());
  Ingredient.eraseFromParent();
}

转换规则：

• Load/Store → VPWidenLoadRecipe / VPWidenStoreRecipe
• PHI (Induction) → VPWidenIntOrFpInductionRecipe
• PHI (Reduction) → VPReductionPHIRecipe
• PHI (First-Order Recurrence) → VPFirstOrderRecurrencePHIRecipe
• GEP → VPWidenGEPRecipe
• Cast → VPWidenCastRecipe
• Call (Intrinsic) → VPWidenIntrinsicRecipe
• 其他 → VPWidenRecipe

阶段 3: 创建 Header PHI Recipes

VPlanTransforms::createHeaderPhiRecipes() 处理循环头部的 PHI 节点：

void createHeaderPhiRecipes(VPlan &Plan, ...) {
  VPBasicBlock *Header = Plan->getVectorLoopRegion()->getEntry();
  
  for (PHINode *Phi : Header->phis()) {
    // 检查是否为归纳变量
    if (InductionDescriptor *ID = GetInductionDescriptor(Phi)) {
      VPWidenIntOrFpInductionRecipe *InductionR = 
        new VPWidenIntOrFpInductionRecipe(...);
      Header->replaceRecipe(Phi, InductionR);
    }
    // 检查是否为归约
    else if (RecurrenceDescriptor *RD = GetReductionDescriptor(Phi)) {
      VPReductionPHIRecipe *ReductionR = 
        new VPReductionPHIRecipe(...);
      Header->replaceRecipe(Phi, ReductionR);
    }
    // 其他情况
    else {
      VPWidenPHIRecipe *WidenR = new VPWidenPHIRecipe(...);
      Header->replaceRecipe(Phi, WidenR);
    }
  }
}

VPlan 变换与优化

主要变换函数

VPlanTransforms 提供了丰富的变换函数：

1. 优化变换

void VPlanTransforms::optimize(VPlan &Plan) {
  // 1. 优化归纳变量
  optimizeInductionRecipes(Plan);
  
  // 2. 移除死代码
  removeDeadRecipes(Plan);
  
  // 3. 优化复制区域
  optimizeReplicateRegions(Plan);
  
  // 4. 合并基本块
  mergeBlocks(Plan);
}

2. 针对 VF/UF 的优化

void optimizeForVFAndUF(VPlan &Plan, ElementCount BestVF, unsigned BestUF) {
  // 限制 VPlan 只支持 BestVF 和 BestUF
  Plan->VFs = {BestVF};
  Plan->UFs = {BestUF};
  
  // 应用 VF/UF 特定的优化
  // ...
}

3. 展开变换

void unrollByUF(VPlan &Plan, unsigned UF) {
  // 显式展开 VPlan 的 UF 次
  // 创建 UF 个循环体副本
  // ...
}

4. 复制变换

void replicateByVF(VPlan &Plan, ElementCount VF) {
  // 将复制区域中的 Recipe 复制 VF 次
  // 每个通道执行一次
  // ...
}

5. 掩码和线性化

DenseMap<VPBasicBlock *, VPValue *> introduceMasksAndLinearize(
    VPlan &Plan, bool FoldTail) {
  // 为需要预测的块创建掩码
  // 线性化控制流（使用掩码控制执行）
  // ...
}

变换示例：创建复制区域

void createAndOptimizeReplicateRegions(VPlan &Plan) {
  // 1. 找到所有带掩码的 VPReplicateRecipe
  SmallVector<VPReplicateRecipe *> MaskedRecipes;
  for (VPBasicBlock *VPBB : Plan->blocks()) {
    for (VPRecipeBase &R : *VPBB) {
      if (auto *RepR = dyn_cast<VPReplicateRecipe>(&R)) {
        if (RepR->hasMask())
          MaskedRecipes.push_back(RepR);
      }
    }
  }
  
  // 2. 为每个掩码 Recipe 创建 if-then 区域
  for (VPReplicateRecipe *RepR : MaskedRecipes) {
    VPRegionBlock *Region = createReplicateRegion(RepR);
    
    // 3. 优化：下沉标量操作数到区域内部
    sinkScalarOperands(Region);
    
    // 4. 合并区域（如果可能）
    mergeRegions(Region);
  }
}

VPlan 执行与 IR 生成

执行流程

VPlan::execute() 是生成 IR 的核心函数：

void VPlan::execute(VPTransformState *State) {
  // 1. 初始化 CFG 状态
  State->CFG.PrevVPBB = nullptr;
  State->CFG.ExitBB = State->CFG.PrevBB->getSingleSuccessor();
  
  // 2. 更新支配树
  State->VPDT.recalculate(*this);
  
  // 3. 断开向量 preheader 与 exit block 的连接
  BasicBlock *VectorPreHeader = State->CFG.PrevBB;
  // ... 更新 CFG ...
  
  // 4. 按逆后序遍历执行所有块
  ReversePostOrderTraversal<...> RPOT(Entry);
  for (VPBlockBase *Block : RPOT)
    Block->execute(State);
  
  // 5. 修复循环头部的 PHI 节点（设置回边值）
  fixLatchPhis(State);
}

VPBasicBlock::execute() - 基本块执行

void VPBasicBlock::execute(VPTransformState *State) {
  // 1. 创建或重用 IR 基本块
  BasicBlock *NewBB = createEmptyBasicBlock(*State);
  State->CFG.VPBB2IRBB[this] = NewBB;
  
  // 2. 设置 IRBuilder 插入点
  State->Builder.SetInsertPoint(NewBB);
  
  // 3. 连接前驱块
  connectToPredecessors(*State);
  
  // 4. 执行所有 Recipe
  executeRecipes(State, NewBB);
}

Recipe 执行示例

VPWidenRecipe::execute()

void VPWidenRecipe::execute(VPTransformState &State) {
  // 1. 获取操作数的向量值
  Value *Op0 = State.get(getOperand(0));  // 获取向量值
  Value *Op1 = State.get(getOperand(1));
  
  // 2. 创建向量化指令
  Value *VecOp = State.Builder.CreateBinOp(
    getOpcode(),  // 例如 Instruction::Add
    Op0,
    Op1,
    getName()
  );
  
  // 3. 记录结果
  State.set(this, VecOp);
}

VPWidenLoadRecipe::execute()

void VPWidenLoadRecipe::execute(VPTransformState &State) {
  // 1. 获取地址的向量值
  Value *Addr = State.get(getOperand(0));
  
  // 2. 获取掩码（如果有）
  Value *Mask = getMask() ? State.get(getMask()) : nullptr;
  
  // 3. 创建向量化加载
  Value *VecLoad = nullptr;
  if (isConsecutive()) {
    // 连续访问：使用向量指针
    VecLoad = State.Builder.CreateAlignedLoad(
      getVectorType(),
      Addr,
      getAlignment()
    );
  } else {
    // 非连续访问：使用 gather
    VecLoad = createGatherLoad(State, Addr, Mask);
  }
  
  // 4. 记录结果
  State.set(this, VecLoad);
}

VPReplicateRecipe::execute()

void VPReplicateRecipe::execute(VPTransformState &State) {
  // 复制 Recipe 在多个通道执行
  // 如果 State->Lane 已设置，只执行当前通道
  
  if (State->Lane) {
    // 单通道执行
    Value *ScalarVal = executeScalar(State);
    State.set(this, ScalarVal, *State->Lane);
  } else {
    // 多通道执行（在复制区域中）
    // 这通常由 VPRegionBlock::execute() 处理
  }
}

VPTransformState::get() - 值获取机制

这是执行过程中的关键函数，负责获取 VPValue 对应的 IR 值：

Value *VPTransformState::get(const VPValue *Def, bool NeedsScalar) {
  if (NeedsScalar) {
    // 需要标量值
    return get(Def, VPLane(0));  // 获取第一个通道的值
  }
  
  // 需要向量值
  if (hasVectorValue(Def))
    return Data.VPV2Vector[Def];  // 直接返回缓存的向量值
  
  // 如果是 live-in 值，进行广播
  if (!hasScalarValue(Def, {0})) {
    Value *IRV = Def->getLiveInIRValue();
    Value *Broadcast = Builder.CreateVectorSplat(VF, IRV);
    set(Def, Broadcast);
    return Broadcast;
  }
  
  // 从标量值构建向量值
  Value *ScalarValue = get(Def, VPLane(0));
  if (VF.isScalar()) {
    set(Def, ScalarValue);
    return ScalarValue;
  }
  
  // 广播标量值到向量
  Value *VectorValue = Builder.CreateVectorSplat(VF, ScalarValue);
  set(Def, VectorValue);
  return VectorValue;
}

实例分析

示例 1: 简单循环向量化

原始 IR:

define void @vectorize_loop(i32* %A, i32* %B, i32* %C, i32 %N) {
entry:
  br label %loop

loop:
  %iv = phi i32 [ 0, %entry ], [ %iv.next, %loop ]
  %gep.A = getelementptr i32, i32* %A, i32 %iv
  %load.A = load i32, i32* %gep.A
  %gep.B = getelementptr i32, i32* %B, i32 %iv
  %load.B = load i32, i32* %gep.B
  %add = add i32 %load.A, %load.B
  %gep.C = getelementptr i32, i32* %C, i32 %iv
  store i32 %add, i32* %gep.C
  %iv.next = add i32 %iv, 1
  %cmp = icmp ult i32 %iv.next, %N
  br i1 %cmp, label %loop, label %exit

exit:
  ret void
}

VPlan0 结构:

Entry (VPIRBasicBlock)
  │
  └─→ Vector Loop Region (VPRegionBlock)
        │
        ├─→ Header (VPBasicBlock)
        │     ├─ VPCanonicalIVPHIRecipe (iv)
        │     ├─ VPWidenGEPRecipe (gep.A)
        │     ├─ VPWidenLoadRecipe (load.A)
        │     ├─ VPWidenGEPRecipe (gep.B)
        │     ├─ VPWidenLoadRecipe (load.B)
        │     ├─ VPWidenRecipe (add)
        │     ├─ VPWidenGEPRecipe (gep.C)
        │     └─ VPWidenStoreRecipe (store)
        │
        └─→ Latch (VPBasicBlock)
              └─ VPInstruction (BranchOnCount)

执行后的向量化 IR (VF=4):

vector.ph:
  %broadcast.splatinsert = insertelement <4 x i32> undef, i32 %N, i32 0
  %broadcast.splat = shufflevector <4 x i32> %broadcast.splatinsert, 
                                    <4 x i32> undef, 
                                    <4 x i32> zeroinitializer
  br label %vector.body

vector.body:
  %index = phi i32 [ 0, %vector.ph ], [ %index.next, %vector.body ]
  %wide.load = load <4 x i32>, <4 x i32>* %gep.A.vec
  %wide.load1 = load <4 x i32>, <4 x i32>* %gep.B.vec
  %add.vec = add <4 x i32> %wide.load, %wide.load1
  store <4 x i32> %add.vec, <4 x i32>* %gep.C.vec
  %index.next = add i32 %index, 4
  %cmp = icmp ult i32 %index.next, %N
  br i1 %cmp, label %vector.body, label %middle.block

示例 2: 带归约的循环

原始 IR:

define i32 @reduction_loop(i32* %A, i32 %N) {
  %sum = phi i32 [ 0, %entry ], [ %add, %loop ]
  %iv = phi i32 [ 0, %entry ], [ %iv.next, %loop ]
  %gep = getelementptr i32, i32* %A, i32 %iv
  %load = load i32, i32* %gep
  %add = add i32 %sum, %load
  %iv.next = add i32 %iv, 1
  %cmp = icmp ult i32 %iv.next, %N
  br i1 %cmp, label %loop, label %exit
}

VPlan 中的归约处理:

Header (VPBasicBlock)
  ├─ VPCanonicalIVPHIRecipe (iv)
  ├─ VPReductionPHIRecipe (sum)
  ├─ VPWidenGEPRecipe (gep)
  ├─ VPWidenLoadRecipe (load)
  └─ VPReductionRecipe (add)  // 归约操作

执行后的向量化 IR:

vector.body:
  %vec.phi = phi <4 x i32> [ zeroinitializer, %vector.ph ], 
                            [ %red.add, %vector.body ]
  %wide.load = load <4 x i32>, <4 x i32>* %gep.vec
  %red.add = add <4 x i32> %vec.phi, %wide.load
  %index.next = add i32 %index, 4
  br label %vector.body

middle.block:
  %rdx.shuf = shufflevector <4 x i32> %red.add, 
                            <4 x i32> undef,
                            <4 x i32> <i32 2, i32 3, i32 undef, i32 undef>
  %bin.rdx = add <4 x i32> %red.add, %rdx.shuf
  %rdx.shuf1 = shufflevector <4 x i32> %bin.rdx, 
                             <4 x i32> undef,
                             <4 x i32> <i32 1, i32 undef, i32 undef, i32 undef>
  %bin.rdx2 = add <4 x i32> %bin.rdx, %rdx.shuf1
  %extract = extractelement <4 x i32> %bin.rdx2, i32 0

示例 3: 带条件分支的循环

原始 IR:

loop:
  %iv = phi i32 [ 0, %entry ], [ %iv.next, %loop ]
  %cmp = icmp sgt i32 %iv, 10
  br i1 %cmp, label %then, label %else

then:
  %load = load i32, i32* %A
  %add = add i32 %load, 1
  store i32 %add, i32* %A
  br label %merge

else:
  %load2 = load i32, i32* %B
  %add2 = add i32 %load2, 2
  store i32 %add2, i32* %B
  br label %merge

merge:
  %iv.next = add i32 %iv, 1
  %exit.cmp = icmp ult i32 %iv.next, %N
  br i1 %exit.cmp, label %loop, label %exit

VPlan 中的预测处理:

Header (VPBasicBlock)
  ├─ VPCanonicalIVPHIRecipe (iv)
  └─ VPInstruction (ICMP) -> 生成向量掩码

Then Region (VPRegionBlock - Replicator)
  └─ Then Block (VPBasicBlock)
        ├─ VPReplicateRecipe (load) [带掩码]
        ├─ VPReplicateRecipe (add) [带掩码]
        └─ VPReplicateRecipe (store) [带掩码]

Else Region (VPRegionBlock - Replicator)
  └─ Else Block (VPBasicBlock)
        ├─ VPReplicateRecipe (load) [带掩码]
        ├─ VPReplicateRecipe (add) [带掩码]
        └─ VPReplicateRecipe (store) [带掩码]

Latch (VPBasicBlock)
  └─ VPInstruction (BranchOnCount)

执行后的向量化 IR (使用掩码):

vector.body:
  %wide.mask = icmp sgt <4 x i32> %vec.iv, <i32 10, i32 10, i32 10, i32 10>
  
  ; Then 路径（掩码为 true 的通道）
  %masked.load = call <4 x i32> @llvm.masked.load.v4i32(
    <4 x i32>* %A.vec, 
    i32 4, 
    <4 x i1> %wide.mask, 
    <4 x i32> undef
  )
  %add.vec = add <4 x i32> %masked.load, <i32 1, i32 1, i32 1, i32 1>
  call void @llvm.masked.store.v4i32(
    <4 x i32> %add.vec, 
    <4 x i32>* %A.vec, 
    i32 4, 
    <4 x i1> %wide.mask
  )
  
  ; Else 路径（掩码为 false 的通道）
  %not.mask = xor <4 x i1> %wide.mask, <i1 true, i1 true, i1 true, i1 true>
  %masked.load2 = call <4 x i32> @llvm.masked.load.v4i32(...)
  ; ...

关键实现细节

1. 值映射机制

VPlan 执行时需要维护 VPValue 到 IR Value 的映射：

struct VPTransformState {
  // 向量值映射：VPValue → 向量 IR Value
  DenseMap<VPValue *, Value *> VPV2Vector;
  
  // 标量值映射：VPValue → [每个通道的标量值]
  DenseMap<VPValue *, SmallVector<Value *, 2>> VPV2Scalars;
  
  // CFG 映射：VPBasicBlock → IR BasicBlock
  DenseMap<VPBasicBlock *, BasicBlock *> VPBB2IRBB;
};

获取值的策略：

• 如果已缓存向量值，直接返回
• 如果是 live-in 值，进行广播
• 如果是单标量值，广播到向量
• 如果需要特定通道的值，从向量中提取

2. 通道 (Lane) 概念

在执行复制区域时，需要跟踪当前执行的通道：

struct VPLane {
  unsigned Lane;           // 通道索引 (0..VF-1)
  enum Kind {
    First,                 // 第一个通道
    ScalableLast          // 可扩展向量的最后一个通道
  } LaneKind;
};

使用场景：

• 复制区域执行时，每个通道执行一次
• 标量值提取时，指定通道索引
• 可扩展向量处理时，处理最后一个通道

3. 类型推断

VPlan 需要推断 Recipe 的类型：

class VPTypeAnalysis {
  // 推断 VPValue 的标量类型
  Type *inferScalarType(VPValue *V);
  
  // 推断向量化后的类型
  Type *inferVectorType(VPValue *V, ElementCount VF);
};

4. 成本评估

在生成 IR 前评估 VPlan 的成本：

InstructionCost VPlan::cost(ElementCount VF, VPCostContext &Ctx) {
  InstructionCost Cost = 0;
  
  // 遍历所有块和 Recipe，累加成本
  for (VPBlockBase *Block : blocks()) {
    Cost += Block->cost(VF, Ctx);
  }
  
  return Cost;
}

5. 调试支持

VPlan 提供丰富的调试功能：

// 打印 VPlan（文本格式）
void VPlan::print(raw_ostream &O) const;

// 打印 VPlan（DOT 图形格式）
void VPlan::printDOT(raw_ostream &O) const;

// 验证 VPlan 的有效性
void verifyVPlanIsValid(VPlan &Plan);

使用方式：

# 启用 VPlan 打印
opt -passes=loop-vectorize -debug-only=loop-vectorize input.ll

# 打印 DOT 格式
opt -passes=loop-vectorize -vplan-print-in-dot-format input.ll

总结

VPlan 的优势

1. 分离关注点：策略规划与 IR 生成分离
2. 可优化性：在 VPlan 层面进行优化
3. 成本评估：生成 IR 前评估成本
4. 可扩展性：易于添加新的向量化策略

关键学习点

1. 层次化 CFG：使用 VPRegionBlock 表示嵌套结构
2. Recipe 系统：不同类型的 Recipe 表示不同的向量化策略
3. 值映射：VPValue 到 IR Value 的映射机制
4. 执行模型：通过 execute() 函数生成 IR

进一步学习

• VPlan.h: 核心数据结构定义
• VPlanTransforms.h/cpp: 变换函数实现
• VPlanRecipes.cpp: Recipe 执行逻辑
• LoopVectorize.cpp: 整体向量化流程

附录：常用 API 速查

VPlan 创建

VPlan *Plan = new VPlan(Loop);
VPBasicBlock *VPBB = Plan->createVPBasicBlock("name");
VPRegionBlock *Region = Plan->createLoopRegion("name", Entry, Exiting);

Recipe 操作

VPRecipeBase *R = new VPWidenRecipe(...);
VPBB->appendRecipe(R);
R->insertBefore(OtherR);
R->eraseFromParent();

值操作

VPValue *VPV = Plan->getOrAddLiveIn(IRValue);
VPV->replaceAllUsesWith(NewVPV);
Value *IRVal = State.get(VPV);  // 执行时获取 IR 值

变换应用

VPlanTransforms::optimize(*Plan);
VPlanTransforms::unrollByUF(*Plan, UF);
VPlanTransforms::replicateByVF(*Plan, VF);

附录 B：实际代码执行流程详解

VPWidenRecipe::execute() 完整实现

void VPWidenRecipe::execute(VPTransformState &State) {
  // 1. 检查是否只需要第一个通道的值
  bool OnlyFirstLaneUsed = vputils::onlyFirstLaneUsed(this);
  
  // 2. 获取操作数（根据是否需要标量值）
  Value *Op0 = State.get(getOperand(0), OnlyFirstLaneUsed);
  Value *Op1 = State.get(getOperand(1), OnlyFirstLaneUsed);
  
  // 3. 创建向量化指令
  Value *VecOp = State.Builder.CreateBinOp(
    getOpcode(),  // 例如 Instruction::Add
    Op0,
    Op1,
    getName()
  );
  
  // 4. 应用标志（如 fast-math flags）
  if (auto *I = dyn_cast<Instruction>(VecOp))
    applyFlags(*I);
  
  // 5. 记录结果到 State
  State.set(this, VecOp);
}

VPWidenLoadRecipe::execute() 完整实现

void VPWidenLoadRecipe::execute(VPTransformState &State) {
  // 1. 获取地址
  Value *Addr = State.get(getOperand(0));
  
  // 2. 获取掩码（如果有）
  Value *Mask = getMask() ? State.get(getMask()) : nullptr;
  
  // 3. 处理连续访问
  if (isConsecutive()) {
    // 连续访问：直接使用向量指针
    Type *VecTy = getVectorType();
    Value *VecLoad = State.Builder.CreateAlignedLoad(
      VecTy,
      Addr,
      getAlignment()
    );
    State.set(this, VecLoad);
    return;
  }
  
  // 4. 处理非连续访问（使用 gather）
  if (Mask) {
    // 使用掩码 gather
    Value *VecLoad = State.Builder.CreateMaskedGather(
      getVectorType(),
      Addr,
      getAlignment(),
      Mask,
      nullptr  // PassThru
    );
    State.set(this, VecLoad);
  } else {
    // 无掩码 gather
    Value *VecLoad = State.Builder.CreateGather(
      getVectorType(),
      Addr,
      getAlignment()
    );
    State.set(this, VecLoad);
  }
}

VPReplicateRecipe::execute() - 复制执行

void VPReplicateRecipe::execute(VPTransformState &State) {
  // 如果 State->Lane 已设置，说明在复制区域中执行
  if (State->Lane) {
    // 单通道执行：生成标量指令
    Value *ScalarVal = executeScalar(State);
    State.set(this, ScalarVal, *State->Lane);
    return;
  }
  
  // 否则，应该在复制区域外部，这种情况不应该发生
  llvm_unreachable("VPReplicateRecipe executed outside replicate region");
}

Value *VPReplicateRecipe::executeScalar(VPTransformState &State) {
  // 获取操作数的标量值
  SmallVector<Value *, 4> ScalarOps;
  for (VPValue *Op : operands()) {
    Value *ScalarOp = State.get(Op, true);  // 需要标量值
    ScalarOps.push_back(ScalarOp);
  }
  
  // 创建标量指令
  Instruction *ScalarInst = getUnderlyingInstr()->clone();
  for (unsigned I = 0; I < ScalarOps.size(); ++I)
    ScalarInst->setOperand(I, ScalarOps[I]);
  
  State.Builder.Insert(ScalarInst);
  return ScalarInst;
}

VPRegionBlock::execute() - 复制区域执行

void VPRegionBlock::execute(VPTransformState *State) {
  assert(isReplicator() && "Only replicate regions execute here");
  assert(!State->Lane && "Replicating with non-null lane");
  
  // 逆后序遍历区域内的块
  ReversePostOrderTraversal<...> RPOT(Entry);
  
  // 对每个通道执行一次
  for (unsigned Lane = 0, VF = State->VF.getFixedValue(); Lane < VF; ++Lane) {
    State->Lane = VPLane(Lane, VPLane::Kind::First);
    
    // 执行区域内的所有块
    for (VPBlockBase *Block : RPOT) {
      Block->execute(State);
    }
  }
  
  // 退出复制模式
  State->Lane.reset();
}

VPTransformState::get() 详细机制

Value *VPTransformState::get(const VPValue *Def, bool NeedsScalar) {
  // 情况1: 需要标量值
  if (NeedsScalar) {
    return get(Def, VPLane(0));  // 获取第一个通道
  }
  
  // 情况2: 已缓存向量值
  if (hasVectorValue(Def))
    return Data.VPV2Vector[Def];
  
  // 情况3: Live-in 值，需要广播
  if (!hasScalarValue(Def, {0})) {
    Value *IRV = Def->getLiveInIRValue();
    Value *Broadcast = Builder.CreateVectorSplat(VF, IRV, "broadcast");
    set(Def, Broadcast);
    return Broadcast;
  }
  
  // 情况4: 从标量值构建向量值
  Value *ScalarValue = get(Def, VPLane(0));
  
  if (VF.isScalar()) {
    set(Def, ScalarValue);
    return ScalarValue;
  }
  
  // 情况5: 单标量值，广播到向量
  assert(vputils::isSingleScalar(Def) && "must be single scalar");
  
  // 设置插入点（在最后一个标量定义之后）
  auto OldIP = Builder.saveIP();
  VPLane LastLane(VF.getFixedValue() - 1);
  auto *LastInst = cast<Instruction>(get(Def, LastLane));
  auto NewIP = isa<PHINode>(LastInst)
    ? LastInst->getParent()->getFirstNonPHIIt()
    : std::next(BasicBlock::iterator(LastInst));
  Builder.SetInsertPoint(&*NewIP);
  
  // 广播
  Value *VectorValue = Builder.CreateVectorSplat(VF, ScalarValue, "broadcast");
  set(Def, VectorValue);
  Builder.restoreIP(OldIP);
  
  return VectorValue;
}

附录 C：调试和验证

启用 VPlan 调试输出

# 1. 编译时启用调试支持
cmake -DCMAKE_BUILD_TYPE=Debug ...

# 2. 运行时启用 VPlan 打印
opt -passes=loop-vectorize -debug-only=loop-vectorize input.ll

# 3. 打印 DOT 格式（用于图形化查看）
opt -passes=loop-vectorize -vplan-print-in-dot-format input.ll > vplan.dot
dot -Tpng vplan.dot -o vplan.png

# 4. 在代码中添加调试输出
LLVM_DEBUG(dbgs() << "VPlan after optimization:\n");
LLVM_DEBUG(Plan->dump());

VPlan 验证

// 验证 VPlan 的有效性
void verifyVPlanIsValid(VPlan &Plan) {
  // 1. 检查 CFG 完整性
  verifyCFG(Plan);
  
  // 2. 检查 Recipe 操作数
  verifyRecipeOperands(Plan);
  
  // 3. 检查类型一致性
  verifyTypes(Plan);
  
  // 4. 检查值使用
  verifyValueUses(Plan);
}

常见问题排查

1. Recipe 操作数未定义检查 VPValue 是否已创建检查 Recipe 插入顺序
2. 类型不匹配使用 VPTypeAnalysis 推断类型检查向量化后的类型是否正确
3. CFG 连接错误检查前驱/后继关系验证区域块的结构

附录 D：扩展 VPlan

添加新的 Recipe 类型

// 1. 在 VPlan.h 中声明新 Recipe
class VPMyCustomRecipe : public VPSingleDefRecipe {
public:
  VPMyCustomRecipe(...) : VPSingleDefRecipe(VPMyCustomRecipeSC, ...) {}
  
  void execute(VPTransformState &State) override;
  
  static bool classof(const VPRecipeBase *R) {
    return R->getVPDefID() == VPMyCustomRecipeSC;
  }
};

// 2. 在 VPlanRecipes.cpp 中实现 execute()
void VPMyCustomRecipe::execute(VPTransformState &State) {
  // 获取操作数
  Value *Op0 = State.get(getOperand(0));
  
  // 生成 IR
  Value *Result = State.Builder.CreateMyCustomIntrinsic(Op0);
  
  // 记录结果
  State.set(this, Result);
}

// 3. 在变换中使用新 Recipe
void MyTransform(VPlan &Plan) {
  // 创建新 Recipe
  VPMyCustomRecipe *R = new VPMyCustomRecipe(...);
  VPBB->appendRecipe(R);
}

添加新的变换

// 在 VPlanTransforms.h 中声明
namespace VPlanTransforms {
  void myCustomTransform(VPlan &Plan, ...);
}

// 在 VPlanTransforms.cpp 中实现
void VPlanTransforms::myCustomTransform(VPlan &Plan, ...) {
  // 遍历 VPlan
  for (VPBasicBlock *VPBB : vp_depth_first(Plan.getEntry())) {
    // 查找目标 Recipe
    for (VPRecipeBase &R : *VPBB) {
      if (auto *TargetR = dyn_cast<VPWidenRecipe>(&R)) {
        // 应用变换
        // ...
      }
    }
  }
  
  // 验证结果
  if (VerifyEachVPlan)
    verifyVPlanIsValid(Plan);
}