From e8555cfd193c8de5a3de29275148731b29f6e176 Mon Sep 17 00:00:00 2001 From: Richard-Qin-X Date: Wed, 19 Aug 2026 17:50:30 +0800 Subject: [CodeGen] Unify LLVM branch folding pipeline --- backend/lib/CodeGen/MachineTailMerge.cpp | 402 ------------------------------- 1 file changed, 402 deletions(-) delete mode 100644 backend/lib/CodeGen/MachineTailMerge.cpp (limited to 'backend/lib/CodeGen/MachineTailMerge.cpp') diff --git a/backend/lib/CodeGen/MachineTailMerge.cpp b/backend/lib/CodeGen/MachineTailMerge.cpp deleted file mode 100644 index 7467993..0000000 --- a/backend/lib/CodeGen/MachineTailMerge.cpp +++ /dev/null @@ -1,402 +0,0 @@ -// SPDX-License-Identifier: GPL-3.0-or-later - -#include "rcc/CodeGen/MachineTailMerge.h" - -#include "rcc/CodeGen/InstructionDescriptor.h" -#include "rcc/CodeGen/LiveVariables.h" -#include "rcc/CodeGen/MachineBasicBlock.h" -#include "rcc/CodeGen/MachineBasicBlockAttributes.h" -#include "rcc/CodeGen/MachineCFGUpdater.h" -#include "rcc/CodeGen/MachineFunction.h" -#include "rcc/CodeGen/MachineFunctionCloner.h" -#include "rcc/CodeGen/MachineInstr.h" -#include "rcc/CodeGen/MachineJumpTableInfo.h" -#include "rcc/CodeGen/MachineMemOperand.h" -#include "rcc/CodeGen/MachineOperand.h" -#include "rcc/CodeGen/RegisterMask.h" -#include "rcc/CodeGen/TargetDescription.h" -#include "rcc/CodeGen/TargetInstrInfo.h" - -#include -#include -#include -#include -#include -#include -#include - -namespace rcc { -namespace { - -[[nodiscard]] const MachinePassContract &tailMergeContract() { - static const MachinePassContract Contract = [] { - MachinePassContract Value{ - .Name = "machine-tail-merge", - .Requires = {MachineFunctionProperty::Selected, MachineFunctionProperty::NoPHIs, - MachineFunctionProperty::TiedOpsRewritten, MachineFunctionProperty::NoVRegs, - MachineFunctionProperty::TracksLiveness, - MachineFunctionProperty::FrameFinalized, - MachineFunctionProperty::NoFrameIndices}, - .Sets = {}, - .Clears = {}, - .RequiredAnalyses = {}, - .VerificationStage = PipelineStage::FrameFinalized, - }; - Value.ThreadSafety = PassThreadSafety::ThreadSafe; - Value.DeclaredChanges = {MachinePassChange::Instructions, MachinePassChange::Operands, - MachinePassChange::CFG, MachinePassChange::BlockLayout}; - return Value; - }(); - return Contract; -} - -[[nodiscard]] bool hasProtectedAttachment(const MachineInstr &Instruction) noexcept { - return Instruction.debugInstrNumber() != 0 || Instruction.preInstrSymbol().has_value() || - Instruction.postInstrSymbol().has_value() || Instruction.heapAllocMarker().has_value() || - Instruction.pcSections().has_value() || Instruction.mmra().has_value() || - Instruction.cfiType().has_value() || Instruction.deactivationSymbol().has_value(); -} - -[[nodiscard]] bool isJumpTableTarget(const MachineBasicBlock &Block, - const MachineFunction &Function) noexcept { - for (const MachineJumpTableEntry &Entry : Function.jumpTableInfo().tables()) { - const MachineJumpTableDesc *Description = Entry.description(); - if (Description != nullptr && - std::ranges::find(Description->Targets, &Block) != Description->Targets.end()) { - return true; - } - } - return false; -} - -[[nodiscard]] bool hasProtectedIdentity(const MachineBasicBlock &Block, - const MachineFunction &Function) noexcept { - const MachineBasicBlockAttributes &Attributes = Block.attributes(); - return Attributes.rawFlags() != 0 || !Attributes.sectionID().isDefault() || - Attributes.profileID().has_value() || isJumpTableTarget(Block, Function); -} - -template -[[nodiscard]] bool payloadEquals(const MachineOperand &Left, const MachineOperand &Right) noexcept { - const ValueT *LeftValue = Left.getIf(); - const ValueT *RightValue = Right.getIf(); - return LeftValue != nullptr && RightValue != nullptr && *LeftValue == *RightValue; -} - -template -[[nodiscard]] bool maskEquals(const MachineOperand &Left, const MachineOperand &Right) noexcept { - const MaskOperandT *LeftValue = Left.getIf(); - const MaskOperandT *RightValue = Right.getIf(); - if (LeftValue == nullptr || RightValue == nullptr) - return false; - if (!LeftValue->Mask || !RightValue->Mask) - return LeftValue->Mask == RightValue->Mask; - return *LeftValue->Mask == *RightValue->Mask; -} - -[[nodiscard]] bool operandEquals(const MachineOperand &Left, const MachineOperand &Right) noexcept { - if (Left.kind() != Right.kind() || Left.targetFlags() != Right.targetFlags() || - Left.tiedOperandIndex() != Right.tiedOperandIndex()) { - return false; - } - if (Left.kind() == MachineOperand::Kind::Register) { - const Register *LeftReg = Left.getIf(); - const Register *RightReg = Right.getIf(); - if (LeftReg == nullptr || RightReg == nullptr || *LeftReg != *RightReg || - Left.subReg() != Right.subReg()) { - return false; - } - RegisterOperandFlags LeftFlags = Left.registerFlags(); - RegisterOperandFlags RightFlags = Right.registerFlags(); - for (const RegisterOperandFlag Flag : - {RegisterOperandFlag::Kill, RegisterOperandFlag::Dead, RegisterOperandFlag::Renamable}) { - LeftFlags.clear(Flag); - RightFlags.clear(Flag); - } - return LeftFlags == RightFlags; - } - switch (Left.kind()) { - case MachineOperand::Kind::Register: - return false; - case MachineOperand::Kind::Immediate: - return payloadEquals(Left, Right); - case MachineOperand::Kind::IntegerImmediate: - return payloadEquals(Left, Right); - case MachineOperand::Kind::FloatingImmediate: - return payloadEquals(Left, Right); - case MachineOperand::Kind::BasicBlock: - return payloadEquals(Left, Right); - case MachineOperand::Kind::FrameIndex: - return payloadEquals(Left, Right); - case MachineOperand::Kind::ConstantPoolIndex: - return payloadEquals(Left, Right); - case MachineOperand::Kind::JumpTableIndex: - return payloadEquals(Left, Right); - case MachineOperand::Kind::GlobalSymbol: - return payloadEquals(Left, Right); - case MachineOperand::Kind::ExternalSymbol: - return payloadEquals(Left, Right); - case MachineOperand::Kind::BlockAddress: - return payloadEquals(Left, Right); - case MachineOperand::Kind::RegisterMask: - return maskEquals(Left, Right); - case MachineOperand::Kind::LiveOutRegisterMask: - return maskEquals(Left, Right); - case MachineOperand::Kind::Metadata: - return payloadEquals(Left, Right); - case MachineOperand::Kind::TargetIndex: - return payloadEquals(Left, Right); - case MachineOperand::Kind::MCSymbol: - return payloadEquals(Left, Right); - case MachineOperand::Kind::CFIIndex: - return payloadEquals(Left, Right); - case MachineOperand::Kind::Intrinsic: - return payloadEquals(Left, Right); - case MachineOperand::Kind::Predicate: - return payloadEquals(Left, Right); - case MachineOperand::Kind::ShuffleMask: - return payloadEquals(Left, Right); - case MachineOperand::Kind::DebugInstrRef: - return payloadEquals(Left, Right); - case MachineOperand::Kind::LaneMask: - return payloadEquals(Left, Right); - case MachineOperand::Kind::Count: - return false; - } - return false; -} - -[[nodiscard]] Expected instructionEquals(const MachineInstr &Left, const MachineInstr &Right, - const TargetDescription &Target) { - const InstructionDescriptor *Descriptor = Target.instructionDescriptor(Left.opcode()); - if (Descriptor == nullptr || Target.instructionDescriptor(Right.opcode()) == nullptr) { - return makeUnexpected(ErrorCode::VerificationError, - "tail merge encountered an unknown instruction"); - } - if (Left.opcode() != Right.opcode() || Left.flags() != Right.flags() || - Left.operandCount() != Right.operandCount() || - Left.memOperands().size() != Right.memOperands().size() || - Left.sourceLocation() != Right.sourceLocation() || - Left.debugLocation() != Right.debugLocation() || Left.origin() != Right.origin() || - hasProtectedAttachment(Left) || hasProtectedAttachment(Right) || - Descriptor->Flags.has(InstructionFlag::Call) || - Descriptor->Flags.has(InstructionFlag::Convergent) || - Descriptor->Flags.has(InstructionFlag::NotDuplicable) || - Left.flags().has(MachineInstrFlag::NoMerge) || - Left.flags().has(MachineInstrFlag::BundledWithPred) || - Left.flags().has(MachineInstrFlag::BundledWithSucc)) { - return false; - } - for (std::size_t Index = 0; Index < Left.operandCount(); ++Index) { - const MachineOperand *LeftOperand = Left.operandAt(Index); - const MachineOperand *RightOperand = Right.operandAt(Index); - if (LeftOperand == nullptr || RightOperand == nullptr || - !operandEquals(*LeftOperand, *RightOperand)) { - return false; - } - } - for (std::size_t Index = 0; Index < Left.memOperands().size(); ++Index) { - const MachineMemOperand *LeftMemory = Left.memOperands()[Index]; - const MachineMemOperand *RightMemory = Right.memOperands()[Index]; - if (LeftMemory == nullptr || RightMemory == nullptr || - LeftMemory->description() != RightMemory->description()) { - return false; - } - } - return true; -} - -[[nodiscard]] Expected blockEquals(const MachineBasicBlock &Left, - const MachineBasicBlock &Right, - const MachineFunction &Function, - const TargetDescription &Target) { - if (&Left == &Right || &Left == Function.firstBlock() || &Right == Function.firstBlock() || - hasProtectedIdentity(Left, Function) || hasProtectedIdentity(Right, Function) || - Left.attributes().alignment() != Right.attributes().alignment() || - Left.attributes().sectionID() != Right.attributes().sectionID() || - Left.attributes().callFrameSize() != Right.attributes().callFrameSize() || - !std::ranges::equal(Left.liveIns(), Right.liveIns()) || - !std::ranges::equal(Left.successors(), Right.successors()) || - Left.instructionCount() != Right.instructionCount()) { - return false; - } - const MachineInstr *LeftInstruction = Left.firstInstruction(); - const MachineInstr *RightInstruction = Right.firstInstruction(); - while (LeftInstruction != nullptr && RightInstruction != nullptr) { - auto Equal = instructionEquals(*LeftInstruction, *RightInstruction, Target); - if (!Equal) - return std::unexpected(Equal.error()); - if (!*Equal) - return false; - LeftInstruction = LeftInstruction->next(); - RightInstruction = RightInstruction->next(); - } - return LeftInstruction == nullptr && RightInstruction == nullptr; -} - -[[nodiscard]] Expected canRedirectPredecessor(MachineBasicBlock &Predecessor, - MachineBasicBlock &Duplicate, - MachineFunction &Function, - const TargetDescription &Target, - const TargetInstrInfo &Info) { - auto Analysis = Info.analyzeBranch(Predecessor, Function, Target); - if (!Analysis) - return std::unexpected(Analysis.error()); - if (Analysis->HasUnanalyzableTerminator) - return false; - if ((Analysis->Conditional != nullptr && Analysis->TrueTarget == &Duplicate && - hasProtectedAttachment(*Analysis->Conditional)) || - (Analysis->Unconditional != nullptr && Analysis->TrueTarget == &Duplicate && - hasProtectedAttachment(*Analysis->Unconditional))) { - return false; - } - if (Analysis->TrueTarget == &Duplicate || Analysis->FalseTarget == &Duplicate) - return true; - return Analysis->Conditional == nullptr && Analysis->Unconditional == nullptr && - Predecessor.successors().size() == 1 && Predecessor.next() == &Duplicate; -} - -[[nodiscard]] Expected -redirectPredecessor(MachineBasicBlock &Predecessor, MachineBasicBlock &Duplicate, - MachineBasicBlock &Canonical, MachineFunction &Function, - const TargetDescription &Target, const TargetInstrInfo &Info) { - auto Analysis = Info.analyzeBranch(Predecessor, Function, Target); - if (!Analysis) - return std::unexpected(Analysis.error()); - auto Rewritten = Info.rewriteBranchTarget(Predecessor, Duplicate, Canonical, Function, Target); - if (!Rewritten) - return std::unexpected(Rewritten.error()); - if (!*Rewritten) { - const bool IsImplicitEdge = - (Analysis->Conditional == nullptr && Analysis->Unconditional == nullptr && - Predecessor.successors().size() == 1 && Predecessor.next() == &Duplicate) || - (Analysis->Conditional != nullptr && Analysis->Unconditional == nullptr && - Analysis->FalseTarget == &Duplicate); - if (!IsImplicitEdge) - return false; - auto Inserted = Info.insertBranch(Predecessor, Canonical, Function, Target); - if (!Inserted) - return std::unexpected(Inserted.error()); - } - MachineCFGUpdater CFG = Function.cfgUpdater(); - auto Redirected = CFG.replaceSuccessor(Predecessor, Duplicate, Canonical); - if (!Redirected) - return std::unexpected(Redirected.error()); - return true; -} - -} // namespace - -const MachinePassContract &MachineTailMergePass::contract() const noexcept { - return tailMergeContract(); -} - -Expected MachineTailMergePass::run(MachineFunction &Function, - const TargetDescription &Target, - MachineFunctionAnalysisManager &) { - if (!Function.properties().containsAll(contract().Requires)) { - return makeUnexpected(ErrorCode::VerificationError, - "tail merge requires finalized allocated tracked-liveness MIR"); - } - auto Trial = cloneMachineFunction( - Function, Target, - MachineFunctionCloneOptions{.NewStableID = Function.stableID(), .NewName = std::nullopt}); - if (!Trial) { - return std::unexpected( - withErrorContext(Trial.error(), "tail merge transaction setup failed: ")); - } - auto TrialResult = runImplementation(*Trial->ClonedFunction, Target); - if (!TrialResult) - return std::unexpected(TrialResult.error()); - auto Result = runImplementation(Function, Target); - if (!Result) { - return std::unexpected(withErrorContext( - Result.error(), "tail merge diverged after a successful transaction preflight: ")); - } - return Result; -} - -Expected -MachineTailMergePass::runImplementation(MachineFunction &Function, - const TargetDescription &Target) const { - MachinePassResult Result; - std::size_t MergedBlocks = 0; - bool LocalChange = true; - while (LocalChange && MergedBlocks < Options.MaximumMergedBlocks) { - LocalChange = false; - std::vector Blocks; - for (MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr; - Block = Block->next()) { - Blocks.push_back(Block); - } - for (std::size_t DuplicateIndex = 1; DuplicateIndex < Blocks.size(); ++DuplicateIndex) { - MachineBasicBlock *Duplicate = Blocks[DuplicateIndex]; - if (Duplicate == nullptr || !Duplicate->isLinked()) - continue; - for (std::size_t CanonicalIndex = 1; CanonicalIndex < DuplicateIndex; ++CanonicalIndex) { - MachineBasicBlock *Canonical = Blocks[CanonicalIndex]; - if (Canonical == nullptr || !Canonical->isLinked()) - continue; - auto Equal = blockEquals(*Canonical, *Duplicate, Function, Target); - if (!Equal) - return std::unexpected(Equal.error()); - if (!*Equal) - continue; - - const std::vector Predecessors(Duplicate->predecessors().begin(), - Duplicate->predecessors().end()); - bool RedirectedAll = true; - for (MachineBasicBlock *Predecessor : Predecessors) { - if (Predecessor == nullptr || Predecessor == Canonical || Predecessor == Duplicate) { - RedirectedAll = false; - break; - } - auto CanRedirect = - canRedirectPredecessor(*Predecessor, *Duplicate, Function, Target, *Info); - if (!CanRedirect) - return std::unexpected(CanRedirect.error()); - if (!*CanRedirect) { - RedirectedAll = false; - break; - } - } - if (!RedirectedAll) - continue; - for (MachineBasicBlock *Predecessor : Predecessors) { - auto Redirected = - redirectPredecessor(*Predecessor, *Duplicate, *Canonical, Function, Target, *Info); - if (!Redirected) - return std::unexpected(Redirected.error()); - if (!*Redirected) { - return makeUnexpected(ErrorCode::CFGOptimizationFailed, - "tail merge predecessor changed after redirect preflight"); - } - } - MachineCFGUpdater CFG = Function.cfgUpdater(); - auto Deleted = CFG.deleteBlock(*Duplicate); - if (!Deleted) - return std::unexpected(Deleted.error()); - ++MergedBlocks; - Result.Changed = true; - LocalChange = true; - break; - } - if (LocalChange) - break; - } - } - - if (!Result.Changed) { - Result.Preserved = PreservedAnalyses::all(); - return Result; - } - auto Rebuilt = rebuildMachineLiveness(Function, Target); - if (!Rebuilt) - return std::unexpected(Rebuilt.error()); - Result.Changes = {MachinePassChange::Instructions, MachinePassChange::Operands, - MachinePassChange::CFG, MachinePassChange::BlockLayout}; - Result.Preserved = PreservedAnalyses::none(); - return Result; -} - -} // namespace rcc -- cgit v1.2.3