概述linearize 函数将控制流图CFG转换为线性指令序列这是代码生成的最后一步。它通过深度优先遍历基本块正确处理分支和跳转确保每个基本块只出现一次并生成可直接汇编的顺序指令列表。代码/// linearize 函数将控制流图线性化为指令序列////// 返回值VecRV64Operation - 线性化的RISC-V指令序列////// 功能执行深度优先的图遍历将控制流图转换为线性指令序列/// 这是代码生成的最后一步生成可以直接汇编的指令序列pubfnlinearize(self)-VecRV64Operation{// 步骤1初始化数据结构// placed: 记录已经放置到线性序列中的基本块标签letmutplacedHashSet::new();// worklist: 工作队列用于深度优先遍历控制流图// 使用VecDeque作为双端队列支持前端和后端操作letmutworklistVecDeque::new();// 将入口块添加到工作队列worklist.push_back(self.get_block(self.get_entry()));// result: 存储最终的线性指令序列letmutresultVec::new();// 步骤2主循环 - 深度优先遍历控制流图// 使用while let模式匹配从工作队列中取出下一个要处理的基本块whileletSome(to_place)worklist.pop_front(){// 步骤2.1检查基本块是否已经处理过// 避免重复处理同一个基本块循环控制流ifplaced.contains(to_place.label){continue;// 已处理跳过}// 步骤2.2为当前基本块插入标签指令// PSEUD_LABEL是伪指令表示基本块的标签result.push(RV64Operation::PSEUD_LABEL(Rc::clone(to_place.label)));// 步骤2.3遍历当前基本块中的所有指令foropinto_place.body.iter(){// 根据指令类型进行不同的处理matchop{// 情况1处理无条件跳转指令 PSEUD_J// 格式PSEUD_J(target_label)RV64Operation::PSEUD_J(t){// 检查目标标签是否已经放置ifplaced.contains(t){// 目标已放置直接添加跳转指令result.push(op.clone());}else{// 目标未放置将目标块添加到工作队列前端// 使用前端添加实现深度优先遍历worklist.push_front(self.blocks.iter().find(|b|b.labelt).unwrap(),);}}// 情况2处理条件分支指令// 包括BEQ相等分支、BGE大于等于分支、BL小于分支// 格式BEQ/BGE/BL(reg1, reg2, target_label)RV64Operation::BEQ(_,_,l)|RV64Operation::BGE(_,_,l)|RV64Operation::BL(_,_,l){// 断言条件分支指令必须有两个后继debug_assert_eq!(to_place.children.len(),2);// 获取false分支第二个后继letrself.get_block(to_place.children[1]);// 添加条件分支指令到结果序列result.push(op.clone());// 检查false分支是否已经放置ifplaced.contains(r.label){// false分支已放置添加无条件跳转到false分支result.push(RV64Operation::PSEUD_J(Rc::clone(r.label)));}else{// false分支未放置将false分支添加到工作队列前端worklist.push_front(r);}// 将true分支目标标签添加到工作队列后端// 使用后端添加确保true分支在false分支之后处理worklist.push_back(self.blocks.iter().find(|b|b.labell).unwrap());}// 情况3处理其他所有指令// 包括算术指令、内存访问指令、伪指令等op{// 直接添加到结果序列result.push(op.clone());}}}// 步骤2.4标记当前基本块为已处理placed.insert(Rc::clone(to_place.label));}// 步骤3返回线性化的指令序列result}主要作用将图状结构线性化CFG 中的基本块通过边分支/跳转连接无法直接输出为指令流。linearize通过遍历将这些块按深度优先顺序排列使生成的指令序列在逻辑上等价于原控制流。插入标签为每个基本块生成一个标签PSEUD_LABEL作为跳转目标处理跳转对于无条件跳转PSEUD_J如果目标块尚未放置则将其加入工作队列前端深度优先如果已放置则直接生成跳转指令。对于条件分支BEQ/BGE/BL先输出分支指令然后将 false 分支fall-through 路径加入队列前端优先处理将 true 分支显式跳转目标加入队列后端稍后处理并在 false 分支已放置时插入一个显式的无条件跳转以维持控制流。保证单次访问使用placed集合记录已处理的基本块避免重复处理例如循环。举例说明假设有以下简单控制流图用伪代码表示BB0: inst0 beq r1, r2, BB2 ; 如果 r1 r2跳转到 BB2否则执行 BB1 BB1: inst1 j BB3 BB2: inst2 j BB3 BB3: inst3 ret执行过程初始化工作队列 worklist 包含入口块 BB0placed 为空。处理 BB0输出 PSEUD_LABEL BB0。处理 inst0直接输出。遇到条件分支 beq r1, r2, BB2输出该分支指令。false 分支为 BB1children[1]未放置 → 将 BB1 加入队列前端。true 分支 BB2 未放置 → 将 BB2 加入队列后端。标记 BB0 为已放置。此时工作队列[BB1, BB2]。标记 BB0 为已放置。此时工作队列[BB1, BB2]。处理 BB1从队列前端取出输出 PSEUD_LABEL BB1。处理 inst1直接输出。遇到无条件跳转 j BB3检查 BB3 是否已放置尚未→ 将 BB3 加入队列前端。标记 BB1 已放置。工作队列[BB3, BB2]。处理 BB3输出 PSEUD_LABEL BB3。处理 inst3 和 ret直接输出。标记 BB3 已放置。工作队列[BB2]。处理 BB2输出 PSEUD_LABEL BB2。处理 inst2直接输出。遇到无条件跳转 j BB3BB3 已放置 → 直接输出该跳转指令。标记 BB2 已放置。工作队列为空结束。最终线性指令序列PSEUD_LABEL BB0 inst0 beq r1, r2, BB2 PSEUD_LABEL BB1 inst1 j BB3 PSEUD_LABEL BB3 inst3 ret PSEUD_LABEL BB2 inst2 j BB3该序列保持了与原控制流图相同的语义从BB0开始根据条件分支进入BB1或BB2BB1和BB2最终都跳转到BB3执行ret为什么使用深度优先策略局部性深度优先遍历倾向于将基本块按执行路径紧密排列有利于指令缓存。简单性利用双端队列可以自然地实现分支路径的优先处理将 fall-through 路径优先输出减少跳转。该函数是编译器后端从中间表示到最终汇编输出的关键桥梁确保生成的机器码可以正确执行。