diff options
Diffstat (limited to 'backend/lib/CodeGen')
22 files changed, 573 insertions, 124 deletions
diff --git a/backend/lib/CodeGen/InlineSpiller.cpp b/backend/lib/CodeGen/InlineSpiller.cpp index 589b7b8..14de321 100644 --- a/backend/lib/CodeGen/InlineSpiller.cpp +++ b/backend/lib/CodeGen/InlineSpiller.cpp @@ -7,6 +7,7 @@ #include "rcc/CodeGen/MachineIRBuilder.h" #include "rcc/CodeGen/MachineInstr.h" #include "rcc/CodeGen/MachineOperand.h" +#include "rcc/CodeGen/MachinePass.h" #include "rcc/CodeGen/MachineRegisterInfo.h" #include "rcc/CodeGen/Spiller.h" #include "rcc/CodeGen/TargetDescription.h" @@ -42,11 +43,11 @@ Expected<std::optional<std::vector<Register>>> Spiller::tryRematerialize(Registe const MachineInstr *DefiningInstruction = Definition == nullptr ? nullptr : Definition->parent(); if (DefiningInstruction == nullptr || DefiningInstruction->parent() == nullptr) return std::optional<std::vector<Register>>{}; - auto Accepted = + auto Rematerializable = TargetInfo->isRematerializable(*DefiningInstruction, VirtualReg, *Function, *Target); - if (!Accepted) - return std::unexpected(Accepted.error()); - if (!*Accepted) + if (!Rematerializable) + return std::unexpected(Rematerializable.error()); + if (!*Rematerializable) return std::optional<std::vector<Register>>{}; struct UseSite final { @@ -77,6 +78,16 @@ Expected<std::optional<std::vector<Register>>> Spiller::tryRematerialize(Registe if (Sites.empty()) return std::optional<std::vector<Register>>{}; + if (Actions != nullptr) { + for (const UseSite &Site : Sites) { + auto Accepted = Actions->request("rematerialize", *Function, Site.Instruction->stableID()); + if (!Accepted) + return std::unexpected(Accepted.error()); + if (!*Accepted) + return std::optional<std::vector<Register>>{}; + } + } + std::vector<Register> NewRegisters; NewRegisters.reserve(Sites.size()); for (UseSite &Site : Sites) { @@ -169,6 +180,19 @@ Expected<std::vector<Register>> Spiller::spillAtInstructions(Register VirtualReg } std::vector<Register> NewRegisters; + if (Actions != nullptr) { + for (const SpillSite &Site : Sites) { + if (Site.OperandIndices.empty()) + continue; + auto Accepted = Actions->request("split-live-range", *Function, Site.Instruction->stableID()); + if (!Accepted) + return std::unexpected(Accepted.error()); + if (!*Accepted) { + return makeUnexpected(ErrorCode::RegisterAllocationFailed, + "required live-range split action was rejected"); + } + } + } for (SpillSite &Site : Sites) { for (const std::size_t Index : Site.DebugIndices) { MachineOperand *Operand = Site.Instruction->operandAt(Index); @@ -259,6 +283,19 @@ Expected<std::vector<Register>> Spiller::spill(Register VirtualReg) { return makeUnexpected(ErrorCode::RegisterAllocationFailed, "register pressure requires spilling a non-spillable value"); } + if (Actions != nullptr) { + const MachineOperand *Definition = Function->registerInfo().getUniqueVRegDef(VirtualReg); + const MachineInstr *Instruction = Definition == nullptr ? nullptr : Definition->parent(); + auto Accepted = + Actions->request("spill", *Function, + Instruction == nullptr ? MachineInstrStableID{} : Instruction->stableID()); + if (!Accepted) + return std::unexpected(Accepted.error()); + if (!*Accepted) { + return makeUnexpected(ErrorCode::RegisterAllocationFailed, + "required spill action was rejected"); + } + } auto Rematerialized = tryRematerialize(VirtualReg); if (!Rematerialized) return std::unexpected(Rematerialized.error()); diff --git a/backend/lib/CodeGen/MachineBlockPlacement.cpp b/backend/lib/CodeGen/MachineBlockPlacement.cpp index fea1283..daccba0 100644 --- a/backend/lib/CodeGen/MachineBlockPlacement.cpp +++ b/backend/lib/CodeGen/MachineBlockPlacement.cpp @@ -114,21 +114,25 @@ Expected<MachinePassResult> MachineBlockPlacementPass::run(MachineFunction &Func if (!Trial) return std::unexpected(prefixedError(Trial.error(), "block placement setup failed: ")); MachineAnalysisManager TrialAnalyses; - auto TrialResult = runImplementation(*Trial->ClonedFunction, Target, TrialAnalyses); + MachineActionReplay Actions(Analyses, Trial->InstructionStableIDs); + auto TrialResult = runImplementation(*Trial->ClonedFunction, Target, TrialAnalyses, Actions); if (!TrialResult) return std::unexpected(TrialResult.error()); - auto Result = runImplementation(Function, Target, Analyses); + Actions.beginReplay(); + auto Result = runImplementation(Function, Target, Analyses, Actions); if (!Result) { return std::unexpected(prefixedError( Result.error(), "block placement diverged after a successful transaction preflight: ")); } + auto Replayed = Actions.finishReplay(); + if (!Replayed) + return std::unexpected(Replayed.error()); return Result; } -Expected<MachinePassResult> -MachineBlockPlacementPass::runImplementation(MachineFunction &Function, - const TargetDescription &Target, - MachineAnalysisManager &Analyses) const { +Expected<MachinePassResult> MachineBlockPlacementPass::runImplementation( + MachineFunction &Function, const TargetDescription &Target, MachineAnalysisManager &Analyses, + MachineActionReplay &Actions) const { auto Probabilities = Analyses.getResult<MachineBranchProbabilityAnalysis>(Function, Target); if (!Probabilities) return std::unexpected(Probabilities.error()); @@ -154,7 +158,7 @@ MachineBlockPlacementPass::runImplementation(MachineFunction &Function, return Result; } - auto factsFor = [&Facts](const MachineBasicBlock &Block) -> const PlacementFacts & { + auto FactsFor = [&Facts](const MachineBasicBlock &Block) -> const PlacementFacts & { return *std::ranges::find_if( Facts, [&Block](const PlacementFacts &Value) { return Value.Block == &Block; }); }; @@ -186,7 +190,7 @@ MachineBlockPlacementPass::runImplementation(MachineFunction &Function, continue; if (BestSuccessor == nullptr || BestProbability < Successor.Probability || (BestProbability == Successor.Probability && - betterRoot(factsFor(*Successor.Block), factsFor(*BestSuccessor)))) { + betterRoot(FactsFor(*Successor.Block), FactsFor(*BestSuccessor)))) { BestSuccessor = Successor.Block; BestProbability = Successor.Probability; } @@ -223,7 +227,22 @@ MachineBlockPlacementPass::runImplementation(MachineFunction &Function, bool Changed = false; for (std::size_t Index = 1; Index < Order.size(); ++Index) { - Changed |= Order[Index - 1U]->next() != Order[Index]; + if (Order[Index - 1U]->next() != Order[Index]) { + Changed = true; + break; + } + } + if (Changed) { + auto Accepted = Actions.request("apply-block-layout", Function); + if (!Accepted) + return std::unexpected(Accepted.error()); + if (!*Accepted) { + MachinePassResult Result; + Result.Preserved = PreservedAnalyses::all(); + return Result; + } + } + for (std::size_t Index = 1; Index < Order.size(); ++Index) { auto Moved = Function.moveBlockAfter(*Order[Index - 1U], *Order[Index]); if (!Moved) return std::unexpected(Moved.error()); diff --git a/backend/lib/CodeGen/MachineBranchRelaxation.cpp b/backend/lib/CodeGen/MachineBranchRelaxation.cpp index d56f3a0..b2a330a 100644 --- a/backend/lib/CodeGen/MachineBranchRelaxation.cpp +++ b/backend/lib/CodeGen/MachineBranchRelaxation.cpp @@ -109,7 +109,7 @@ const MachinePassContract &MachineBranchRelaxationPass::contract() const noexcep Expected<MachinePassResult> MachineBranchRelaxationPass::run(MachineFunction &Function, const TargetDescription &Target, - MachineAnalysisManager &) { + MachineAnalysisManager &Analyses) { if (!Function.properties().containsAll(contract().Requires)) { return makeUnexpected(ErrorCode::VerificationError, "branch relaxation requires finalized frame and tracked liveness"); @@ -119,20 +119,26 @@ Expected<MachinePassResult> MachineBranchRelaxationPass::run(MachineFunction &Fu MachineFunctionCloneOptions{.NewStableID = Function.stableID(), .NewName = std::nullopt}); if (!Trial) return std::unexpected(prefixedError(Trial.error(), "branch relaxation setup failed: ")); - auto TrialResult = runImplementation(*Trial->ClonedFunction, Target); + MachineActionReplay Actions(Analyses, Trial->InstructionStableIDs); + auto TrialResult = runImplementation(*Trial->ClonedFunction, Target, Actions); if (!TrialResult) return std::unexpected(TrialResult.error()); - auto Result = runImplementation(Function, Target); + Actions.beginReplay(); + auto Result = runImplementation(Function, Target, Actions); if (!Result) { return std::unexpected(prefixedError( Result.error(), "branch relaxation diverged after a successful transaction preflight: ")); } + auto Replayed = Actions.finishReplay(); + if (!Replayed) + return std::unexpected(Replayed.error()); return Result; } Expected<MachinePassResult> MachineBranchRelaxationPass::runImplementation(MachineFunction &Function, - const TargetDescription &Target) const { + const TargetDescription &Target, + MachineActionReplay &Actions) const { if (Options.ConvergenceWatchdog == 0) return makeUnexpected(ErrorCode::InvalidArgument, "branch relaxation watchdog must be nonzero"); MachinePassResult Result; @@ -162,6 +168,13 @@ MachineBranchRelaxationPass::runImplementation(MachineFunction &Function, return std::unexpected(Offset.error()); if (Info->isBranchOffsetInRange(*Instruction, *Offset)) continue; + auto Accepted = Actions.request("relax-branch", Function, Instruction->stableID()); + if (!Accepted) + return std::unexpected(Accepted.error()); + if (!*Accepted) { + return makeUnexpected(ErrorCode::BranchRelaxationFailed, + "required branch relaxation action was rejected"); + } auto Relaxed = Info->relaxBranch(*Instruction, *Offset, Function, Target); if (!Relaxed) return std::unexpected(Relaxed.error()); diff --git a/backend/lib/CodeGen/MachineCSE.cpp b/backend/lib/CodeGen/MachineCSE.cpp index a144403..47bba04 100644 --- a/backend/lib/CodeGen/MachineCSE.cpp +++ b/backend/lib/CodeGen/MachineCSE.cpp @@ -161,8 +161,11 @@ template <typename ValueT> if (Reg == nullptr || !Reg->isVirtual()) continue; auto Info = Registers.virtualRegisterInfo(*Reg); - if (Info && Info->get().Type && Info->get().Type->isFloat()) - return true; + if (Info) { + const auto &Type = Info->get().Type; + if (Type && Type->isFloat()) + return true; + } } return false; } diff --git a/backend/lib/CodeGen/MachineCombiner.cpp b/backend/lib/CodeGen/MachineCombiner.cpp index 513d282..54915ab 100644 --- a/backend/lib/CodeGen/MachineCombiner.cpp +++ b/backend/lib/CodeGen/MachineCombiner.cpp @@ -279,7 +279,7 @@ const MachinePassContract &MachineCombinerPass::contract() const noexcept { Expected<MachinePassResult> MachineCombinerPass::run(MachineFunction &Function, const TargetDescription &Target, - MachineAnalysisManager &) { + MachineAnalysisManager &Analyses) { if (!Function.properties().containsAll(contract().Requires)) { return makeUnexpected(ErrorCode::VerificationError, "machine combiner input does not satisfy its stage contract"); @@ -291,20 +291,25 @@ Expected<MachinePassResult> MachineCombinerPass::run(MachineFunction &Function, return std::unexpected( prefixedError(Trial.error(), "machine combiner transaction setup failed: ")); } - auto TrialResult = runImplementation(*Trial->ClonedFunction, Target); + MachineActionReplay Actions(Analyses, Trial->InstructionStableIDs); + auto TrialResult = runImplementation(*Trial->ClonedFunction, Target, Actions); if (!TrialResult) return std::unexpected(TrialResult.error()); - auto Result = runImplementation(Function, Target); + Actions.beginReplay(); + auto Result = runImplementation(Function, Target, Actions); if (!Result) { return std::unexpected(prefixedError( Result.error(), "machine combiner diverged after a successful transaction preflight: ")); } + auto Replayed = Actions.finishReplay(); + if (!Replayed) + return std::unexpected(Replayed.error()); return Result; } Expected<MachinePassResult> -MachineCombinerPass::runImplementation(MachineFunction &Function, - const TargetDescription &Target) const { +MachineCombinerPass::runImplementation(MachineFunction &Function, const TargetDescription &Target, + MachineActionReplay &Actions) const { if (Options.MaximumIterations == 0) return makeUnexpected(ErrorCode::InvalidArgument, "machine combiner iteration budget must be nonzero"); @@ -321,6 +326,13 @@ MachineCombinerPass::runImplementation(MachineFunction &Function, continue; if (Rewrites == Options.MaximumRewrites) break; + std::string Rule = "combine."; + Rule.append(Pattern.Name); + auto Accepted = Actions.request(Rule, Function, Instruction->stableID()); + if (!Accepted) + return std::unexpected(Accepted.error()); + if (!*Accepted) + continue; auto Executed = executePattern(*Instruction, Pattern, Function, Target); if (!Executed) return std::unexpected(Executed.error()); diff --git a/backend/lib/CodeGen/MachineCompilationStatus.cpp b/backend/lib/CodeGen/MachineCompilationStatus.cpp index 3ebfa0f..df009a4 100644 --- a/backend/lib/CodeGen/MachineCompilationStatus.cpp +++ b/backend/lib/CodeGen/MachineCompilationStatus.cpp @@ -55,6 +55,12 @@ isKnownDiagnosticSeverity(MachineCompilationDiagnosticSeverity Severity) noexcep case ErrorCode::FixupApplicationFailed: case ErrorCode::RelocationFailed: case ErrorCode::ObjectWritingFailed: + case ErrorCode::InvalidInvocation: + case ErrorCode::ManifestError: + case ErrorCode::CacheMiss: + case ErrorCode::ReproducerError: + case ErrorCode::ReductionFailed: + case ErrorCode::FuzzingFailure: case ErrorCode::IoError: case ErrorCode::InternalError: return true; diff --git a/backend/lib/CodeGen/MachineCopyPropagation.cpp b/backend/lib/CodeGen/MachineCopyPropagation.cpp index e537a06..f9211f9 100644 --- a/backend/lib/CodeGen/MachineCopyPropagation.cpp +++ b/backend/lib/CodeGen/MachineCopyPropagation.cpp @@ -292,7 +292,7 @@ const MachinePassContract &MachineCopyPropagationPass::contract() const noexcept Expected<MachinePassResult> MachineCopyPropagationPass::run(MachineFunction &Function, const TargetDescription &Target, - MachineAnalysisManager &) { + MachineAnalysisManager &Analyses) { if (!Function.properties().containsAll(contract().Requires)) { return makeUnexpected(ErrorCode::VerificationError, "machine COPY propagation has unmet stage properties"); @@ -304,20 +304,26 @@ Expected<MachinePassResult> MachineCopyPropagationPass::run(MachineFunction &Fun return std::unexpected( prefixedError(Trial.error(), "COPY propagation transaction setup failed: ")); } - auto TrialResult = runImplementation(*Trial->ClonedFunction, Target); + MachineActionReplay Actions(Analyses, Trial->InstructionStableIDs); + auto TrialResult = runImplementation(*Trial->ClonedFunction, Target, Actions); if (!TrialResult) return std::unexpected(TrialResult.error()); - auto Result = runImplementation(Function, Target); + Actions.beginReplay(); + auto Result = runImplementation(Function, Target, Actions); if (!Result) { return std::unexpected(prefixedError( Result.error(), "COPY propagation diverged after a successful transaction preflight: ")); } + auto Replayed = Actions.finishReplay(); + if (!Replayed) + return std::unexpected(Replayed.error()); return Result; } Expected<MachinePassResult> MachineCopyPropagationPass::runImplementation(MachineFunction &Function, - const TargetDescription &Target) const { + const TargetDescription &Target, + MachineActionReplay &Actions) const { MachinePassResult Result; std::size_t PropagatedCopies = 0; for (MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr; Block = Block->next()) { @@ -329,6 +335,13 @@ MachineCopyPropagationPass::runImplementation(MachineFunction &Function, Instruction = Next; continue; } + auto Accepted = Actions.request("propagate-copy", Function, Instruction->stableID()); + if (!Accepted) + return std::unexpected(Accepted.error()); + if (!*Accepted) { + Instruction = Next; + continue; + } Expected<bool> Changed = Stage == MachineCopyPropagationStage::PreRegisterAllocation ? propagateVirtualCopy(*Instruction, *Operands, Function, Target, *Info) diff --git a/backend/lib/CodeGen/MachineLICM.cpp b/backend/lib/CodeGen/MachineLICM.cpp index 8c8d732..52fffe7 100644 --- a/backend/lib/CodeGen/MachineLICM.cpp +++ b/backend/lib/CodeGen/MachineLICM.cpp @@ -146,8 +146,8 @@ namespace { auto Info = Function.registerInfo().virtualRegisterInfo(*Reg); if (!Info) return std::unexpected(Info.error()); - if (Info->get().Type && Info->get().Type->isFloat() && - !Instruction.flags().has(MachineInstrFlag::NoFPExcept)) { + const auto &Type = Info->get().Type; + if (Type && Type->isFloat() && !Instruction.flags().has(MachineInstrFlag::NoFPExcept)) { return false; } } diff --git a/backend/lib/CodeGen/MachinePass.cpp b/backend/lib/CodeGen/MachinePass.cpp index ae69b1c..0ce6f70 100644 --- a/backend/lib/CodeGen/MachinePass.cpp +++ b/backend/lib/CodeGen/MachinePass.cpp @@ -141,6 +141,79 @@ void combineFingerprint(std::uint64_t &State, std::uint64_t Value) noexcept { } // namespace +std::string MachineActionID::toString() const { + std::string Result; + Result.reserve(Pass.size() + Rule.size() + 48U); + Result.append(Pass); + Result.push_back(':'); + Result.append(Rule); + Result.append(":f"); + Result.append(std::to_string(Function.value())); + Result.append(":i"); + Result.append(std::to_string(Instruction.value())); + return Result; +} + +Expected<bool> MachineActionReplay::request(std::string_view Rule, const MachineFunction &Function, + MachineInstrStableID Instruction, std::uint64_t Cost) { + if (!IsReplaying) { + const auto Position = RecordingInstructionIDs.find(Instruction); + const MachineInstrStableID CanonicalInstruction = + Position == RecordingInstructionIDs.end() ? Instruction : Position->second; + auto Accepted = Analyses->requestAction(Rule, Function, CanonicalInstruction, Cost); + if (!Accepted) + return std::unexpected(Accepted.error()); + Decisions.push_back({ + .Rule = std::string(Rule), + .Function = Function.stableID(), + .Instruction = CanonicalInstruction, + .Cost = Cost, + .Accepted = *Accepted, + }); + return *Accepted; + } + + if (NextDecision >= Decisions.size()) { + return makeUnexpected(ErrorCode::InternalError, + "machine action replay requested an unrecorded decision"); + } + const Decision &Recorded = Decisions[NextDecision++]; + if (Recorded.Rule != Rule || Recorded.Function != Function.stableID() || + Recorded.Instruction != Instruction || Recorded.Cost != Cost) { + std::string Message = "machine action replay diverged from transaction preflight: recorded "; + Message.append(Recorded.Rule); + Message.append(":f"); + Message.append(std::to_string(Recorded.Function.value())); + Message.append(":i"); + Message.append(std::to_string(Recorded.Instruction.value())); + Message.append(" cost="); + Message.append(std::to_string(Recorded.Cost)); + Message.append(", requested "); + Message.append(Rule); + Message.append(":f"); + Message.append(std::to_string(Function.stableID().value())); + Message.append(":i"); + Message.append(std::to_string(Instruction.value())); + Message.append(" cost="); + Message.append(std::to_string(Cost)); + return makeUnexpected(ErrorCode::InternalError, std::move(Message)); + } + return Recorded.Accepted; +} + +void MachineActionReplay::beginReplay() noexcept { + IsReplaying = true; + NextDecision = 0; +} + +Expected<void> MachineActionReplay::finishReplay() const { + if (!IsReplaying || NextDecision != Decisions.size()) { + return makeUnexpected(ErrorCode::InternalError, + "machine action replay did not consume every recorded decision"); + } + return {}; +} + Expected<void> MachineAnalysisManager::registerAnalysisImpl(MachineAnalysisRegistration Registration, ErasedRunner Runner, ErasedInvalidator Invalidator) { @@ -374,12 +447,25 @@ Expected<void> MachineAnalysisManager::validateParallelRequirements( Expected<bool> MachineAnalysisManager::requestAction(std::string_view Action, const MachineFunction &Function, std::uint64_t Cost) { - if (Action.empty() || Cost == 0) + return requestAction(Action, Function, MachineInstrStableID{}, Cost); +} + +Expected<bool> MachineAnalysisManager::requestAction(std::string_view Rule, + const MachineFunction &Function, + MachineInstrStableID Instruction, + std::uint64_t Cost) { + if (Rule.empty() || Cost == 0) return makeUnexpected(ErrorCode::InvalidArgument, "machine action requires a name and nonzero cost"); if (Instrumentation == nullptr) return true; - return Instrumentation->requestAction(Action, Function, Cost); + MachineActionID ID{ + .Pass = ActivePass.empty() ? "unscoped" : ActivePass, + .Rule = std::string(Rule), + .Function = Function.stableID(), + .Instruction = Instruction, + }; + return Instrumentation->requestAction(ID, Function, Cost); } Expected<void> CompilationUnitAnalysisManager::registerAnalysisImpl( @@ -639,6 +725,7 @@ void MachinePassInstrumentation::setPerFunctionFuel(std::optional<std::uint64_t> std::scoped_lock Lock(Mutex); PerFunctionFuel = Fuel; ConsumedFuel.clear(); + ActionEvents.clear(); } void MachinePassInstrumentation::addBeforeUnitCallback(BeforeUnitCallback Callback) { @@ -879,25 +966,37 @@ void MachinePassInstrumentation::change(std::string_view Name, const MachineFunc Callback(Name, Function, Changes, FingerprintChanged); } -Expected<bool> MachinePassInstrumentation::requestAction(std::string_view Action, +Expected<bool> MachinePassInstrumentation::requestAction(const MachineActionID &Action, const MachineFunction &Function, std::uint64_t Cost) { + if (Action.Pass.empty() || Action.Rule.empty() || Action.Function != Function.stableID() || + Cost == 0) { + return makeUnexpected(ErrorCode::InvalidArgument, "machine action identity is invalid"); + } std::scoped_lock ActionLock(ActionMutex); ActionFilter CurrentFilter; { std::scoped_lock Lock(Mutex); CurrentFilter = Filter; } - if (CurrentFilter && !CurrentFilter(Action, Function, Cost)) + if (CurrentFilter && !CurrentFilter(Action, Cost)) { + std::scoped_lock Lock(Mutex); + ActionEvents.push_back({Action, Cost, false}); return false; + } std::scoped_lock Lock(Mutex); - if (!PerFunctionFuel) + if (!PerFunctionFuel) { + ActionEvents.push_back({Action, Cost, true}); return true; + } std::uint64_t &Consumed = ConsumedFuel[Function.stableID().value()]; - if (Consumed > *PerFunctionFuel || Cost > *PerFunctionFuel - Consumed) + if (Consumed > *PerFunctionFuel || Cost > *PerFunctionFuel - Consumed) { + ActionEvents.push_back({Action, Cost, false}); return false; + } Consumed += Cost; + ActionEvents.push_back({Action, Cost, true}); return true; } @@ -1007,10 +1106,33 @@ std::vector<InstrumentationStatistic> MachinePassInstrumentation::statistics() c return Result; } +std::vector<MachineActionEvent> MachinePassInstrumentation::actionEvents() const { + std::vector<MachineActionEvent> Result; + { + std::scoped_lock Lock(Mutex); + Result = ActionEvents; + } + std::ranges::sort(Result, [](const MachineActionEvent &Left, const MachineActionEvent &Right) { + if (Left.ID.Function.value() != Right.ID.Function.value()) + return Left.ID.Function.value() < Right.ID.Function.value(); + if (Left.ID.Instruction.value() != Right.ID.Instruction.value()) + return Left.ID.Instruction.value() < Right.ID.Instruction.value(); + if (Left.ID.Pass != Right.ID.Pass) + return Left.ID.Pass < Right.ID.Pass; + if (Left.ID.Rule != Right.ID.Rule) + return Left.ID.Rule < Right.ID.Rule; + if (Left.Cost != Right.Cost) + return Left.Cost < Right.Cost; + return Left.Accepted < Right.Accepted; + }); + return Result; +} + void MachinePassInstrumentation::clearStatistics() { std::scoped_lock Lock(Mutex); Statistics.clear(); ConsumedFuel.clear(); + ActionEvents.clear(); } Expected<void> MachinePassManager::validateContract(const MachinePassContract &Contract) const { @@ -1087,7 +1209,9 @@ Expected<void> MachinePassManager::run(MachineFunction &Function, const TargetDe if (Instrumentation != nullptr) Instrumentation->before(Name, Function); const Clock::time_point Start = Clock::now(); + Analyses.ActivePass = std::string(Name); auto PassResult = Pass->run(Function, Target, Analyses); + Analyses.ActivePass.clear(); const std::uint64_t Duration = elapsedNanoseconds(Start); if (!PassResult) { Error Failure = diff --git a/backend/lib/CodeGen/MachinePipelinePasses.cpp b/backend/lib/CodeGen/MachinePipelinePasses.cpp index 209439c..c7c5dc3 100644 --- a/backend/lib/CodeGen/MachinePipelinePasses.cpp +++ b/backend/lib/CodeGen/MachinePipelinePasses.cpp @@ -233,6 +233,36 @@ registerConfigurationFingerprint(const MachineRegisterInfo &RegInfo) noexcept { return Error(Source.code(), std::move(Prefix)); } +[[nodiscard]] std::string_view legalizationActionName(LegalizationAction Action) noexcept { + switch (Action) { + case LegalizationAction::Legal: + return "legal"; + case LegalizationAction::Unsupported: + return "unsupported"; + case LegalizationAction::Custom: + return "custom"; + case LegalizationAction::Lower: + return "lower"; + case LegalizationAction::Libcall: + return "libcall"; + case LegalizationAction::WidenScalar: + return "widen-scalar"; + case LegalizationAction::NarrowScalar: + return "narrow-scalar"; + case LegalizationAction::MoreElements: + return "more-elements"; + case LegalizationAction::FewerElements: + return "fewer-elements"; + case LegalizationAction::Bitcast: + return "bitcast"; + case LegalizationAction::ChangeElementType: + return "change-element-type"; + case LegalizationAction::ChangeAddressSpace: + return "change-address-space"; + } + return "unknown"; +} + [[nodiscard]] Expected<void> repairTrackedLiveness(MachineFunction &Function, const TargetDescription &Target, MachinePassResult &Result) { @@ -268,21 +298,25 @@ Expected<MachinePassResult> LegalizerPass::run(MachineFunction &Function, MachineFunctionCloneOptions{.NewStableID = Function.stableID(), .NewName = std::nullopt}); if (!Trial) return std::unexpected(prefixedError(Trial.error(), "legalizer transaction setup failed: ")); - MachineAnalysisManager TrialAnalyses; - auto TrialResult = runImplementation(*Trial->ClonedFunction, Target, TrialAnalyses); + MachineActionReplay Actions(Analyses, Trial->InstructionStableIDs); + auto TrialResult = runImplementation(*Trial->ClonedFunction, Target, Actions); if (!TrialResult) return std::unexpected(TrialResult.error()); - auto Result = runImplementation(Function, Target, Analyses); + Actions.beginReplay(); + auto Result = runImplementation(Function, Target, Actions); if (!Result) { return std::unexpected(prefixedError( Result.error(), "legalizer diverged after a successful transaction preflight: ")); } + auto Replayed = Actions.finishReplay(); + if (!Replayed) + return std::unexpected(Replayed.error()); return Result; } Expected<MachinePassResult> LegalizerPass::runImplementation(MachineFunction &Function, const TargetDescription &Target, - MachineAnalysisManager &) { + MachineActionReplay &Actions) { MachinePassResult Result; std::unordered_set<OpcodeState, OpcodeStateHash> SeenStates; @@ -328,6 +362,18 @@ Expected<MachinePassResult> LegalizerPass::runImplementation(MachineFunction &Fu if (!LoweringValidation) return std::unexpected( prefixedError(LoweringValidation.error(), "legalizer lowering precondition failed: ")); + std::string Rule = "legalize."; + Rule.append(legalizationActionName(*Action)); + Rule.push_back('.'); + Rule.append(Descriptor->Name); + auto Accepted = Actions.request(Rule, Function, Instruction->stableID()); + if (!Accepted) + return std::unexpected(Accepted.error()); + if (!*Accepted) { + return std::unexpected( + passFailure("required legalizer action was rejected for '" + Descriptor->Name + "'", + ErrorCode::VerificationError)); + } auto Lowered = Info->lower(*Instruction, Function, Target, *Action); if (!Lowered) return std::unexpected(Lowered.error()); @@ -521,22 +567,26 @@ Expected<MachinePassResult> InstructionSelectPass::run(MachineFunction &Function return std::unexpected( prefixedError(Trial.error(), "instruction-selection transaction setup failed: ")); } - MachineAnalysisManager TrialAnalyses; - auto TrialResult = runImplementation(*Trial->ClonedFunction, Target, TrialAnalyses); + MachineActionReplay Actions(Analyses, Trial->InstructionStableIDs); + auto TrialResult = runImplementation(*Trial->ClonedFunction, Target, Actions); if (!TrialResult) return std::unexpected(TrialResult.error()); - auto Result = runImplementation(Function, Target, Analyses); + Actions.beginReplay(); + auto Result = runImplementation(Function, Target, Actions); if (!Result) { return std::unexpected( prefixedError(Result.error(), "instruction selection diverged after a successful transaction preflight: ")); } + auto Replayed = Actions.finishReplay(); + if (!Replayed) + return std::unexpected(Replayed.error()); return Result; } Expected<MachinePassResult> InstructionSelectPass::runImplementation(MachineFunction &Function, const TargetDescription &Target, - MachineAnalysisManager &) { + MachineActionReplay &Actions) { MachinePassResult Result; std::vector<MachineInstr *> Worklist; @@ -580,6 +630,16 @@ InstructionSelectPass::runImplementation(MachineFunction &Function, const Target auto Match = Info->canSelect(*Instruction, Function, Target); if (!Match) return std::unexpected(Match.error()); + std::string Rule = "select."; + Rule.append(CurrentDescriptor->Name); + auto Accepted = Actions.request(Rule, Function, Instruction->stableID()); + if (!Accepted) + return std::unexpected(Accepted.error()); + if (!*Accepted) { + return std::unexpected(passFailure("required selection action was rejected for '" + + CurrentDescriptor->Name + "'", + ErrorCode::VerificationError)); + } auto Selection = Info->select(*Instruction, Function, Target); if (!Selection) return std::unexpected(Selection.error()); diff --git a/backend/lib/CodeGen/MachinePseudoExpansion.cpp b/backend/lib/CodeGen/MachinePseudoExpansion.cpp index e654d97..676804a 100644 --- a/backend/lib/CodeGen/MachinePseudoExpansion.cpp +++ b/backend/lib/CodeGen/MachinePseudoExpansion.cpp @@ -202,7 +202,7 @@ using BlockSizeSnapshot = std::vector<std::pair<MachineBlockStableID, std::uint6 [[nodiscard]] Expected<MachinePassResult> prepareImplementation(MachineFunction &Function, const TargetDescription &Target, - const TargetPseudoExpansionInfo &Info) { + const TargetPseudoExpansionInfo &Info, MachineActionReplay &Actions) { bool Changed = false; for (MachineInstr *Instruction : Function.allInstructions()) { if (Instruction == nullptr || Instruction->parent() == nullptr) @@ -213,6 +213,15 @@ prepareImplementation(MachineFunction &Function, const TargetDescription &Target "pseudo preparation encountered an unknown opcode"); if (Descriptor->Owner != PseudoOwner::PostRAExpansion) continue; + std::string Rule = "prepare-pseudo."; + Rule.append(Descriptor->Name); + auto Accepted = Actions.request(Rule, Function, Instruction->stableID()); + if (!Accepted) + return std::unexpected(Accepted.error()); + if (!*Accepted) { + return makeUnexpected(ErrorCode::PseudoExpansionFailed, + "required pseudo preparation action was rejected"); + } auto Prepared = Info.preparePostRAPseudo(*Instruction, Function, Target); if (!Prepared) return std::unexpected(Prepared.error()); @@ -232,7 +241,7 @@ prepareImplementation(MachineFunction &Function, const TargetDescription &Target [[nodiscard]] Expected<MachinePassResult> expandImplementation(MachineFunction &Function, const TargetDescription &Target, const TargetPseudoExpansionInfo &Info, MachinePseudoExpansionPhase Phase, - const TargetBranchInfo *BranchInfo) { + const TargetBranchInfo *BranchInfo, MachineActionReplay &Actions) { const ResourceSnapshot Before = snapshotResources(Function); std::optional<BlockSizeSnapshot> SizesBefore; if (Phase == MachinePseudoExpansionPhase::TargetLate) { @@ -261,6 +270,15 @@ expandImplementation(MachineFunction &Function, const TargetDescription &Target, if (!Descriptor->Flags.has(InstructionFlag::Pseudo) || Descriptor->Owner != ownerFor(Phase)) { continue; } + std::string Rule = "expand-pseudo."; + Rule.append(Descriptor->Name); + auto Accepted = Actions.request(Rule, Function, Instruction->stableID()); + if (!Accepted) + return std::unexpected(Accepted.error()); + if (!*Accepted) { + return makeUnexpected(ErrorCode::PseudoExpansionFailed, + "required pseudo expansion action was rejected"); + } MachineBasicBlock *ExpansionBlock = Instruction->parent(); std::optional<std::uint64_t> ExpansionSizeBefore; if (Phase == MachinePseudoExpansionPhase::TargetLate) { @@ -335,40 +353,51 @@ expandImplementation(MachineFunction &Function, const TargetDescription &Target, [[nodiscard]] Expected<MachinePassResult> runPreparationTransaction(MachineFunction &Function, const TargetDescription &Target, - const TargetPseudoExpansionInfo &Info) { + const TargetPseudoExpansionInfo &Info, MachineAnalysisManager &Analyses) { auto Trial = cloneMachineFunction( Function, Target, MachineFunctionCloneOptions{.NewStableID = Function.stableID(), .NewName = std::nullopt}); if (!Trial) return std::unexpected(prefixedError(Trial.error(), "pseudo preparation setup failed: ")); - auto TrialResult = prepareImplementation(*Trial->ClonedFunction, Target, Info); + MachineActionReplay Actions(Analyses, Trial->InstructionStableIDs); + auto TrialResult = prepareImplementation(*Trial->ClonedFunction, Target, Info, Actions); if (!TrialResult) return std::unexpected(TrialResult.error()); - auto Result = prepareImplementation(Function, Target, Info); + Actions.beginReplay(); + auto Result = prepareImplementation(Function, Target, Info, Actions); if (!Result) { return std::unexpected( prefixedError(Result.error(), "pseudo preparation diverged after successful preflight: ")); } + auto Replayed = Actions.finishReplay(); + if (!Replayed) + return std::unexpected(Replayed.error()); return Result; } [[nodiscard]] Expected<MachinePassResult> runExpansionTransaction(MachineFunction &Function, const TargetDescription &Target, const TargetPseudoExpansionInfo &Info, MachinePseudoExpansionPhase Phase, - const TargetBranchInfo *BranchInfo) { + const TargetBranchInfo *BranchInfo, MachineAnalysisManager &Analyses) { auto Trial = cloneMachineFunction( Function, Target, MachineFunctionCloneOptions{.NewStableID = Function.stableID(), .NewName = std::nullopt}); if (!Trial) return std::unexpected(prefixedError(Trial.error(), "pseudo expansion setup failed: ")); - auto TrialResult = expandImplementation(*Trial->ClonedFunction, Target, Info, Phase, BranchInfo); + MachineActionReplay Actions(Analyses, Trial->InstructionStableIDs); + auto TrialResult = + expandImplementation(*Trial->ClonedFunction, Target, Info, Phase, BranchInfo, Actions); if (!TrialResult) return std::unexpected(TrialResult.error()); - auto Result = expandImplementation(Function, Target, Info, Phase, BranchInfo); + Actions.beginReplay(); + auto Result = expandImplementation(Function, Target, Info, Phase, BranchInfo, Actions); if (!Result) { return std::unexpected( prefixedError(Result.error(), "pseudo expansion diverged after successful preflight: ")); } + auto Replayed = Actions.finishReplay(); + if (!Replayed) + return std::unexpected(Replayed.error()); return Result; } @@ -380,11 +409,11 @@ const MachinePassContract &PreparePostRAPseudosPass::contract() const noexcept { Expected<MachinePassResult> PreparePostRAPseudosPass::run(MachineFunction &Function, const TargetDescription &Target, - MachineAnalysisManager &) { + MachineAnalysisManager &Analyses) { if (!Function.properties().containsAll(contract().Requires)) return makeUnexpected(ErrorCode::VerificationError, "post-RA pseudo preparation requires selected MachineIR"); - return runPreparationTransaction(Function, Target, *Info); + return runPreparationTransaction(Function, Target, *Info, Analyses); } const MachinePassContract &PrePEITargetPseudoExpansionPass::contract() const noexcept { @@ -393,12 +422,12 @@ const MachinePassContract &PrePEITargetPseudoExpansionPass::contract() const noe Expected<MachinePassResult> PrePEITargetPseudoExpansionPass::run(MachineFunction &Function, const TargetDescription &Target, - MachineAnalysisManager &) { + MachineAnalysisManager &Analyses) { if (!Function.properties().containsAll(contract().Requires)) return makeUnexpected(ErrorCode::VerificationError, "pre-PEI pseudo expansion requires allocated tracked-liveness MIR"); return runExpansionTransaction(Function, Target, *Info, MachinePseudoExpansionPhase::PrePEI, - nullptr); + nullptr, Analyses); } const MachinePassContract &ExpandPostRAPseudosPass::contract() const noexcept { @@ -407,12 +436,12 @@ const MachinePassContract &ExpandPostRAPseudosPass::contract() const noexcept { Expected<MachinePassResult> ExpandPostRAPseudosPass::run(MachineFunction &Function, const TargetDescription &Target, - MachineAnalysisManager &) { + MachineAnalysisManager &Analyses) { if (!Function.properties().containsAll(contract().Requires)) return makeUnexpected(ErrorCode::VerificationError, "post-RA pseudo expansion requires finalized frame and liveness"); return runExpansionTransaction(Function, Target, *Info, MachinePseudoExpansionPhase::PostRA, - nullptr); + nullptr, Analyses); } const MachinePassContract &TargetLatePseudoExpansionPass::contract() const noexcept { @@ -421,12 +450,12 @@ const MachinePassContract &TargetLatePseudoExpansionPass::contract() const noexc Expected<MachinePassResult> TargetLatePseudoExpansionPass::run(MachineFunction &Function, const TargetDescription &Target, - MachineAnalysisManager &) { + MachineAnalysisManager &Analyses) { if (!Function.properties().containsAll(contract().Requires)) return makeUnexpected(ErrorCode::VerificationError, "target-late pseudo expansion requires finalized allocated MIR"); return runExpansionTransaction(Function, Target, *Info, MachinePseudoExpansionPhase::TargetLate, - BranchInfo); + BranchInfo, Analyses); } } // namespace rcc diff --git a/backend/lib/CodeGen/MachineSSAExit.cpp b/backend/lib/CodeGen/MachineSSAExit.cpp index e413b45..f2b0102 100644 --- a/backend/lib/CodeGen/MachineSSAExit.cpp +++ b/backend/lib/CodeGen/MachineSSAExit.cpp @@ -805,22 +805,26 @@ Expected<MachinePassResult> PHIEliminationPass::run(MachineFunction &Function, return std::unexpected( prefixedError(Trial.error(), "PHI-elimination transaction setup failed: ")); } - MachineAnalysisManager TrialAnalyses; - auto TrialResult = runImplementation(*Trial->ClonedFunction, Target, TrialAnalyses); + MachineActionReplay Actions(Analyses, Trial->InstructionStableIDs); + auto TrialResult = runImplementation(*Trial->ClonedFunction, Target, Actions); if (!TrialResult) return std::unexpected(TrialResult.error()); - auto Result = runImplementation(Function, Target, Analyses); + Actions.beginReplay(); + auto Result = runImplementation(Function, Target, Actions); if (!Result) { return std::unexpected(prefixedError( Result.error(), "PHI elimination diverged after a successful transaction preflight: ")); } + auto Replayed = Actions.finishReplay(); + if (!Replayed) + return std::unexpected(Replayed.error()); return Result; } Expected<MachinePassResult> PHIEliminationPass::runImplementation(MachineFunction &Function, const TargetDescription &Target, - MachineAnalysisManager &) { + MachineActionReplay &Actions) { MachinePassResult Result; std::unordered_map<EdgeKey, MachineBasicBlock *, EdgeKeyHash> SplitEdges; const std::vector<MachineBasicBlock *> Blocks(Function.allBlocks().begin(), @@ -834,6 +838,13 @@ Expected<MachinePassResult> PHIEliminationPass::runImplementation(MachineFunctio continue; for (PhiPlan &Plan : *Plans) { + auto Accepted = Actions.request("eliminate-phi", Function, Plan.Instruction->stableID()); + if (!Accepted) + return std::unexpected(Accepted.error()); + if (!*Accepted) { + return makeUnexpected(ErrorCode::VerificationError, + "required PHI elimination action was rejected"); + } auto Fresh = cloneRegisterConstraints(Function, Plan.Destination.Reg); if (!Fresh) return std::unexpected(Fresh.error()); @@ -928,22 +939,26 @@ Expected<MachinePassResult> TwoAddressRewritePass::run(MachineFunction &Function if (!Trial) { return std::unexpected(prefixedError(Trial.error(), "two-address transaction setup failed: ")); } - MachineAnalysisManager TrialAnalyses; - auto TrialResult = runImplementation(*Trial->ClonedFunction, Target, TrialAnalyses); + MachineActionReplay Actions(Analyses, Trial->InstructionStableIDs); + auto TrialResult = runImplementation(*Trial->ClonedFunction, Target, Actions); if (!TrialResult) return std::unexpected(TrialResult.error()); - auto Result = runImplementation(Function, Target, Analyses); + Actions.beginReplay(); + auto Result = runImplementation(Function, Target, Actions); if (!Result) { return std::unexpected(prefixedError( Result.error(), "two-address rewrite diverged after a successful transaction preflight: ")); } + auto Replayed = Actions.finishReplay(); + if (!Replayed) + return std::unexpected(Replayed.error()); return Result; } Expected<MachinePassResult> TwoAddressRewritePass::runImplementation(MachineFunction &Function, const TargetDescription &Target, - MachineAnalysisManager &) { + MachineActionReplay &Actions) { MachinePassResult Result; const std::vector<MachineInstr *> Instructions(Function.allInstructions().begin(), Function.allInstructions().end()); @@ -951,6 +966,12 @@ TwoAddressRewritePass::runImplementation(MachineFunction &Function, const Target if (Instruction->parent() == nullptr) continue; if (Instruction->opcode() == opcode(GenericOpcode::REG_SEQUENCE)) { + auto Accepted = Actions.request("expand-reg-sequence", Function, Instruction->stableID()); + if (!Accepted) + return std::unexpected(Accepted.error()); + if (!*Accepted) + return makeUnexpected(ErrorCode::VerificationError, + "required REG_SEQUENCE expansion action was rejected"); auto Expanded = expandRegSequence(*Instruction, Function, Target, *Info); if (!Expanded) return std::unexpected(Expanded.error()); @@ -959,6 +980,12 @@ TwoAddressRewritePass::runImplementation(MachineFunction &Function, const Target continue; } if (Instruction->opcode() == opcode(GenericOpcode::INSERT_SUBREG)) { + auto Accepted = Actions.request("expand-insert-subreg", Function, Instruction->stableID()); + if (!Accepted) + return std::unexpected(Accepted.error()); + if (!*Accepted) + return makeUnexpected(ErrorCode::VerificationError, + "required INSERT_SUBREG expansion action was rejected"); auto Expanded = expandInsertSubreg(*Instruction, Function, Target, *Info); if (!Expanded) return std::unexpected(Expanded.error()); @@ -1004,6 +1031,12 @@ TwoAddressRewritePass::runImplementation(MachineFunction &Function, const Target continue; if (isImplicitlyUndef(Function, *Use)) { + auto Accepted = Actions.request("rewrite-undef-tie", Function, Instruction->stableID()); + if (!Accepted) + return std::unexpected(Accepted.error()); + if (!*Accepted) + return makeUnexpected(ErrorCode::VerificationError, + "required undef tie rewrite action was rejected"); auto Rewritten = rewriteUndefTie(*Use, *Def); if (!Rewritten) return std::unexpected(Rewritten.error()); @@ -1012,28 +1045,46 @@ TwoAddressRewritePass::runImplementation(MachineFunction &Function, const Target continue; } - auto Commuted = tryCommute(*Instruction, UseIndex, *DefReg, Target, Function); - if (!Commuted) - return std::unexpected(Commuted.error()); - if (*Commuted) { - Result.Changed = true; - Result.Changes.add(MachinePassChange::Operands); - continue; + auto AllowCommute = + Actions.request("commute-tied-operands", Function, Instruction->stableID()); + if (!AllowCommute) + return std::unexpected(AllowCommute.error()); + if (*AllowCommute) { + auto Commuted = tryCommute(*Instruction, UseIndex, *DefReg, Target, Function); + if (!Commuted) + return std::unexpected(Commuted.error()); + if (*Commuted) { + Result.Changed = true; + Result.Changes.add(MachinePassChange::Operands); + continue; + } } - auto Converted = - Info->tryConvertToThreeAddress(*Instruction, DefIndex, UseIndex, Function, Target); - if (!Converted) - return std::unexpected(Converted.error()); - if (*Converted) { - Result.Changed = true; - Result.Changes.add(MachinePassChange::Instructions); - Result.Changes.add(MachinePassChange::Operands); - Result.Changes.add(MachinePassChange::Registers); - Restart = true; - break; + auto AllowConversion = + Actions.request("convert-three-address", Function, Instruction->stableID()); + if (!AllowConversion) + return std::unexpected(AllowConversion.error()); + if (*AllowConversion) { + auto Converted = + Info->tryConvertToThreeAddress(*Instruction, DefIndex, UseIndex, Function, Target); + if (!Converted) + return std::unexpected(Converted.error()); + if (*Converted) { + Result.Changed = true; + Result.Changes.add(MachinePassChange::Instructions); + Result.Changes.add(MachinePassChange::Operands); + Result.Changes.add(MachinePassChange::Registers); + Restart = true; + break; + } } + auto AllowCopy = Actions.request("insert-tied-copy", Function, Instruction->stableID()); + if (!AllowCopy) + return std::unexpected(AllowCopy.error()); + if (!*AllowCopy) + return makeUnexpected(ErrorCode::VerificationError, + "required tied COPY insertion action was rejected"); MachineBasicBlock *Block = Instruction->parent(); if (Block == nullptr) return makeUnexpected(ErrorCode::InternalError, diff --git a/backend/lib/CodeGen/MachineScheduler.cpp b/backend/lib/CodeGen/MachineScheduler.cpp index f861be2..c85489b 100644 --- a/backend/lib/CodeGen/MachineScheduler.cpp +++ b/backend/lib/CodeGen/MachineScheduler.cpp @@ -129,7 +129,8 @@ struct ScheduleCandidate final { scheduleDAG(const ScheduleDAG &DAG, const MachineFunction &Function, const TargetDescription &Target, const TargetSchedulingModel &Model, ScheduleDAGMode Mode, const MachineBlockLiveness &Liveness, - std::uint64_t BlockFrequency, bool EnableBidirectionalScheduling) { + std::uint64_t BlockFrequency, bool EnableBidirectionalScheduling, + MachineActionReplay *Actions) { auto TopPressure = RegisterPressureTracker::create(DAG, Function, Target, Model, Mode, Liveness, RegisterPressureDirection::TopDown); if (!TopPressure) @@ -214,6 +215,14 @@ scheduleDAG(const ScheduleDAG &DAG, const MachineFunction &Function, } const ScheduleUnit &Selected = DAG.units()[Best->Unit]; + if (Actions != nullptr) { + auto Accepted = Actions->request(Best->Bottom ? "schedule-bottom" : "schedule-top", Function, + Selected.StableID); + if (!Accepted) + return std::unexpected(Accepted.error()); + if (!*Accepted) + return std::vector<std::size_t>{}; + } Scheduled[Best->Unit] = true; if (Best->Bottom) { auto Issued = BottomHazards->issue(Selected, Best->Cycle); @@ -263,7 +272,7 @@ scheduleRegion(MachineBasicBlock &Block, std::span<MachineInstr *const> Instruct MachineFunction &Function, const TargetDescription &Target, const TargetSchedulingModel &Model, ScheduleDAGMode Mode, const MachineBlockLiveness &Liveness, std::uint64_t BlockFrequency, - MachineSchedulerOptions Options) { + MachineSchedulerOptions Options, MachineActionReplay *Actions) { if (Instructions.size() < 2 || Instructions.size() > Options.MaximumRegionSize) return false; auto DAG = ScheduleDAG::build(Block, Instructions, Function, Target, Model, Mode); @@ -272,9 +281,11 @@ scheduleRegion(MachineBasicBlock &Block, std::span<MachineInstr *const> Instruct if (DAG->units().size() < 2) return false; auto UnitOrder = scheduleDAG(*DAG, Function, Target, Model, Mode, Liveness, BlockFrequency, - Options.EnableBidirectionalScheduling); + Options.EnableBidirectionalScheduling, Actions); if (!UnitOrder) return std::unexpected(UnitOrder.error()); + if (UnitOrder->empty()) + return false; std::vector<MachineInstr *> NewOrder; NewOrder.reserve(Instructions.size()); @@ -305,10 +316,12 @@ scheduleRegion(MachineBasicBlock &Block, std::span<MachineInstr *const> Instruct } // namespace -Expected<MachineSchedulingRunResult> runMachineScheduler( - MachineFunction &Function, const TargetDescription &Target, const TargetSchedulingModel &Model, - ScheduleDAGMode Mode, const LiveVariablesAnalysis::Result &Liveness, - const MachineBlockFrequencyAnalysis::Result &Frequencies, MachineSchedulerOptions Options) { +Expected<MachineSchedulingRunResult> +runMachineScheduler(MachineFunction &Function, const TargetDescription &Target, + const TargetSchedulingModel &Model, ScheduleDAGMode Mode, + const LiveVariablesAnalysis::Result &Liveness, + const MachineBlockFrequencyAnalysis::Result &Frequencies, + MachineSchedulerOptions Options, MachineActionReplay *Actions) { if (Options.MaximumRegionSize == 0) { return makeUnexpected(ErrorCode::InvalidArgument, "machine scheduler region budget must be nonzero"); @@ -324,7 +337,7 @@ Expected<MachineSchedulingRunResult> runMachineScheduler( std::vector<MachineInstr *> Region; auto FlushRegion = [&]() -> Expected<void> { auto Changed = scheduleRegion(*Block, Region, Function, Target, Model, Mode, *BlockLiveness, - Frequencies.frequency(*Block), Options); + Frequencies.frequency(*Block), Options, Actions); if (!Changed) return std::unexpected(Changed.error()); BlockChanged |= *Changed; @@ -403,9 +416,10 @@ Expected<MachinePassResult> MachineSchedulerPass::run(MachineFunction &Function, TrialAnalyses.getResult<MachineBlockFrequencyAnalysis>(*Trial->ClonedFunction, Target); if (!TrialFrequencies) return std::unexpected(TrialFrequencies.error()); + MachineActionReplay Actions(Analyses, Trial->InstructionStableIDs); auto TrialResult = runMachineScheduler(*Trial->ClonedFunction, Target, *Model, ScheduleDAGMode::PreRegisterAllocation, **TrialLiveness, - **TrialFrequencies, Options); + **TrialFrequencies, Options, &Actions); if (!TrialResult) return std::unexpected(TrialResult.error()); @@ -415,12 +429,16 @@ Expected<MachinePassResult> MachineSchedulerPass::run(MachineFunction &Function, auto Frequencies = Analyses.getResult<MachineBlockFrequencyAnalysis>(Function, Target); if (!Frequencies) return std::unexpected(Frequencies.error()); + Actions.beginReplay(); auto Run = runMachineScheduler(Function, Target, *Model, ScheduleDAGMode::PreRegisterAllocation, - **Liveness, **Frequencies, Options); + **Liveness, **Frequencies, Options, &Actions); if (!Run) { return std::unexpected(prefixedError( Run.error(), "machine scheduler diverged after a successful transaction preflight: ")); } + auto Replayed = Actions.finishReplay(); + if (!Replayed) + return std::unexpected(Replayed.error()); MachinePassResult Result; Result.Changed = Run->Changed; diff --git a/backend/lib/CodeGen/MachineSchedulerInternal.h b/backend/lib/CodeGen/MachineSchedulerInternal.h index a612548..92f8eea 100644 --- a/backend/lib/CodeGen/MachineSchedulerInternal.h +++ b/backend/lib/CodeGen/MachineSchedulerInternal.h @@ -1,5 +1,7 @@ // SPDX-License-Identifier: GPL-3.0-or-later +// The private header has no stable include-root-relative guard name. +// NOLINTNEXTLINE(llvm-header-guard) #ifndef RCC_LIB_CODEGEN_MACHINESCHEDULERINTERNAL_H #define RCC_LIB_CODEGEN_MACHINESCHEDULERINTERNAL_H @@ -14,6 +16,7 @@ namespace rcc { class MachineBasicBlock; +class MachineActionReplay; class MachineFunction; class TargetDescription; class TargetSchedulingModel; @@ -22,10 +25,12 @@ struct MachineSchedulingRunResult final { std::vector<MachineBasicBlock *> ChangedBlocks; }; -[[nodiscard]] Expected<MachineSchedulingRunResult> runMachineScheduler( - MachineFunction &Function, const TargetDescription &Target, const TargetSchedulingModel &Model, - ScheduleDAGMode Mode, const LiveVariablesAnalysis::Result &Liveness, - const MachineBlockFrequencyAnalysis::Result &Frequencies, MachineSchedulerOptions Options); +[[nodiscard]] Expected<MachineSchedulingRunResult> +runMachineScheduler(MachineFunction &Function, const TargetDescription &Target, + const TargetSchedulingModel &Model, ScheduleDAGMode Mode, + const LiveVariablesAnalysis::Result &Liveness, + const MachineBlockFrequencyAnalysis::Result &Frequencies, + MachineSchedulerOptions Options, MachineActionReplay *Actions = nullptr); } // namespace rcc diff --git a/backend/lib/CodeGen/MachineSink.cpp b/backend/lib/CodeGen/MachineSink.cpp index 9e73cea..873de67 100644 --- a/backend/lib/CodeGen/MachineSink.cpp +++ b/backend/lib/CodeGen/MachineSink.cpp @@ -123,8 +123,8 @@ namespace { auto Info = Function.registerInfo().virtualRegisterInfo(*Reg); if (!Info) return std::unexpected(Info.error()); - if (Info->get().Type && Info->get().Type->isFloat() && - !Instruction.flags().has(MachineInstrFlag::NoFPExcept)) { + const auto &Type = Info->get().Type; + if (Type && Type->isFloat() && !Instruction.flags().has(MachineInstrFlag::NoFPExcept)) { return false; } } diff --git a/backend/lib/CodeGen/MachineStackSlotColoring.cpp b/backend/lib/CodeGen/MachineStackSlotColoring.cpp index b3b9af5..e60a7a2 100644 --- a/backend/lib/CodeGen/MachineStackSlotColoring.cpp +++ b/backend/lib/CodeGen/MachineStackSlotColoring.cpp @@ -178,7 +178,7 @@ collectSlotUses(MachineFunction &Function) { [[nodiscard]] bool intervalsOverlap(const SlotInterval &Left, const SlotInterval &Right) noexcept { if (Left.Block != Right.Block) return true; - return !(Left.Last < Right.First || Right.Last < Left.First); + return Left.Last >= Right.First && Right.Last >= Left.First; } struct StackColor final { diff --git a/backend/lib/CodeGen/MachineTailDuplication.cpp b/backend/lib/CodeGen/MachineTailDuplication.cpp index a130680..40d448f 100644 --- a/backend/lib/CodeGen/MachineTailDuplication.cpp +++ b/backend/lib/CodeGen/MachineTailDuplication.cpp @@ -286,7 +286,8 @@ MachineTailDuplicationPass::runImplementation(MachineFunction &Function, Tail = Next; continue; } - const std::size_t Cost = (*Candidate)->Body.size() + 1U; + const auto &TailCandidate = Candidate->value(); + const std::size_t Cost = TailCandidate.Body.size() + 1U; const std::vector<MachineBasicBlock *> Predecessors(Tail->predecessors().begin(), Tail->predecessors().end()); for (MachineBasicBlock *Predecessor : Predecessors) { @@ -296,7 +297,7 @@ MachineTailDuplicationPass::runImplementation(MachineFunction &Function, break; } auto Duplicated = - duplicateTailIntoPredecessor(**Candidate, *Tail, *Predecessor, Function, Target, *Info); + duplicateTailIntoPredecessor(TailCandidate, *Tail, *Predecessor, Function, Target, *Info); if (!Duplicated) return std::unexpected(Duplicated.error()); if (!*Duplicated) diff --git a/backend/lib/CodeGen/PostRAScheduler.cpp b/backend/lib/CodeGen/PostRAScheduler.cpp index 9aff5ac..026f763 100644 --- a/backend/lib/CodeGen/PostRAScheduler.cpp +++ b/backend/lib/CodeGen/PostRAScheduler.cpp @@ -287,9 +287,10 @@ Expected<MachinePassResult> PostRASchedulerPass::run(MachineFunction &Function, TrialAnalyses.getResult<MachineBlockFrequencyAnalysis>(*Trial->ClonedFunction, Target); if (!TrialFrequencies) return std::unexpected(TrialFrequencies.error()); + MachineActionReplay Actions(Analyses, Trial->InstructionStableIDs); auto TrialRun = runMachineScheduler(*Trial->ClonedFunction, Target, *Model, ScheduleDAGMode::PostRegisterAllocation, **TrialLiveness, - **TrialFrequencies, Options); + **TrialFrequencies, Options, &Actions); if (!TrialRun) return std::unexpected(TrialRun.error()); auto TrialRepair = @@ -303,12 +304,16 @@ Expected<MachinePassResult> PostRASchedulerPass::run(MachineFunction &Function, auto Frequencies = Analyses.getResult<MachineBlockFrequencyAnalysis>(Function, Target); if (!Frequencies) return std::unexpected(Frequencies.error()); + Actions.beginReplay(); auto Run = runMachineScheduler(Function, Target, *Model, ScheduleDAGMode::PostRegisterAllocation, - **Liveness, **Frequencies, Options); + **Liveness, **Frequencies, Options, &Actions); if (!Run) { return std::unexpected(prefixedError( Run.error(), "post-RA scheduler diverged after a successful transaction preflight: ")); } + auto Replayed = Actions.finishReplay(); + if (!Replayed) + return std::unexpected(Replayed.error()); auto Repaired = repairPostRAMachineBlockLiveness(Run->ChangedBlocks, Target, **Liveness); if (!Repaired) return std::unexpected(Repaired.error()); diff --git a/backend/lib/CodeGen/RegAllocBase.cpp b/backend/lib/CodeGen/RegAllocBase.cpp index 1aae22d..5d065dd 100644 --- a/backend/lib/CodeGen/RegAllocBase.cpp +++ b/backend/lib/CodeGen/RegAllocBase.cpp @@ -63,7 +63,8 @@ Expected<regalloc_detail::AllocationRunResult> RegAllocBase::run() { std::ranges::sort(Round->Spilled, [](Register Left, Register Right) { return Left.opaqueValue() < Right.opaqueValue(); }); - Spiller ValueSpiller(Function, Target, TargetInfo, Mapping, Options.EnableRematerialization); + Spiller ValueSpiller(Function, Target, TargetInfo, Mapping, Options.EnableRematerialization, + Actions); for (const Register VirtualReg : Round->Spilled) { VirtRegMapEntry *Entry = Mapping.entry(VirtualReg); if (Entry != nullptr) { diff --git a/backend/lib/CodeGen/RegAllocBase.h b/backend/lib/CodeGen/RegAllocBase.h index 5af5ed0..a1682b2 100644 --- a/backend/lib/CodeGen/RegAllocBase.h +++ b/backend/lib/CodeGen/RegAllocBase.h @@ -28,9 +28,9 @@ public: protected: RegAllocBase(MachineFunction &Function, const TargetDescription &Target, const TargetRegisterAllocationInfo &TargetInfo, MachineAnalysisManager &Analyses, - RegisterAllocationOptions Options) noexcept + RegisterAllocationOptions Options, MachineActionReplay *Actions = nullptr) noexcept : Function(Function), Target(Target), TargetInfo(TargetInfo), Analyses(Analyses), - Options(Options) {} + Options(Options), Actions(Actions) {} [[nodiscard]] virtual Expected<AllocationRoundResult> allocateRound(const LiveIntervalsAnalysis::Result &Intervals, VirtRegMap &Mapping) = 0; @@ -40,6 +40,7 @@ protected: const TargetRegisterAllocationInfo &TargetInfo; MachineAnalysisManager &Analyses; RegisterAllocationOptions Options; + MachineActionReplay *Actions = nullptr; }; [[nodiscard]] std::vector<const LiveInterval *> diff --git a/backend/lib/CodeGen/RegAllocPBQP.cpp b/backend/lib/CodeGen/RegAllocPBQP.cpp index a5a12f7..f1da2c1 100644 --- a/backend/lib/CodeGen/RegAllocPBQP.cpp +++ b/backend/lib/CodeGen/RegAllocPBQP.cpp @@ -15,9 +15,10 @@ #include <algorithm> #include <cstdint> #include <limits> +#include <map> #include <optional> #include <ranges> -#include <set> +#include <string> #include <utility> #include <vector> @@ -30,9 +31,9 @@ struct PBQPAllocationNode final { std::vector<std::optional<PhysicalRegister>> Options; }; -[[nodiscard]] std::set<std::pair<std::uint32_t, std::uint32_t>> +[[nodiscard]] std::map<std::pair<std::uint32_t, std::uint32_t>, MachineInstrStableID> copyRelatedRegisters(const MachineFunction &Function) { - std::set<std::pair<std::uint32_t, std::uint32_t>> Result; + std::map<std::pair<std::uint32_t, std::uint32_t>, MachineInstrStableID> Result; for (const MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr; Block = Block->next()) { for (const MachineInstr *Instruction = Block->firstInstruction(); Instruction != nullptr; @@ -48,12 +49,33 @@ copyRelatedRegisters(const MachineFunction &Function) { std::uint32_t Right = Source->opaqueValue(); if (Right < Left) std::swap(Left, Right); - Result.emplace(Left, Right); + Result.try_emplace({Left, Right}, Instruction->stableID()); } } return Result; } +[[nodiscard]] std::string_view reductionName(pbqp::ReductionKind Kind) noexcept { + switch (Kind) { + case pbqp::ReductionKind::DegreeZero: + return "degree-zero"; + case pbqp::ReductionKind::DegreeOne: + return "degree-one"; + case pbqp::ReductionKind::DegreeTwo: + return "degree-two"; + case pbqp::ReductionKind::Heuristic: + return "heuristic"; + } + return "unknown"; +} + +[[nodiscard]] MachineInstrStableID actionInstructionForRegister(const MachineFunction &Function, + Register Reg) noexcept { + const MachineOperand *Definition = Function.registerInfo().getUniqueVRegDef(Reg); + const MachineInstr *Instruction = Definition == nullptr ? nullptr : Definition->parent(); + return Instruction == nullptr ? MachineInstrStableID{} : Instruction->stableID(); +} + [[nodiscard]] pbqp::Cost boundedCost(std::uint64_t Value) noexcept { const std::uint64_t Limit = static_cast<std::uint64_t>(pbqp::InfiniteCost - 1); return static_cast<pbqp::Cost>(std::min(Value, Limit)); @@ -63,8 +85,9 @@ class PBQPAllocatorEngine final : public RegAllocBase { public: PBQPAllocatorEngine(MachineFunction &Function, const TargetDescription &Target, const TargetRegisterAllocationInfo &TargetInfo, - MachineAnalysisManager &Analyses, RegisterAllocationOptions Options) - : RegAllocBase(Function, Target, TargetInfo, Analyses, Options) {} + MachineAnalysisManager &Analyses, RegisterAllocationOptions Options, + MachineActionReplay *Actions) + : RegAllocBase(Function, Target, TargetInfo, Analyses, Options, Actions) {} private: [[nodiscard]] Expected<AllocationRoundResult> @@ -152,8 +175,14 @@ private: std::uint32_t RightKey = Right.VirtualReg.opaqueValue(); if (RightKey < LeftKey) std::swap(LeftKey, RightKey); - const bool CopyRelated = - Options.EnableCopyCoalescing && CopyPairs.contains({LeftKey, RightKey}); + const auto CopyPosition = CopyPairs.find({LeftKey, RightKey}); + bool CopyRelated = Options.EnableCopyCoalescing && CopyPosition != CopyPairs.end(); + if (CopyRelated && Actions != nullptr) { + auto Accepted = Actions->request("coalesce-copy", Function, CopyPosition->second); + if (!Accepted) + return std::unexpected(Accepted.error()); + CopyRelated = *Accepted; + } pbqp::CostMatrix Costs(Left.Options.size(), Right.Options.size(), 0); bool HasCost = false; for (std::size_t LeftOption = 1; LeftOption < Left.Options.size(); ++LeftOption) { @@ -188,7 +217,23 @@ private: } pbqp::DeterministicSolver Solver; - auto Solution = Solver.solve(Problem); + auto Solution = Solver.solve(Problem, [&](const pbqp::SolverAction &Action) -> Expected<bool> { + if (Actions == nullptr) + return true; + if (Action.Node.value() >= Nodes.size()) { + return makeUnexpected(ErrorCode::InternalError, + "PBQP action names an unknown allocation node"); + } + const Register VirtualReg = Nodes[Action.Node.value()].VirtualReg; + std::string Rule = + Action.Kind == pbqp::SolverActionKind::Reduction ? "pbqp-reduce." : "pbqp-choice."; + Rule.append(reductionName(Action.Reduction)); + if (Action.Kind == pbqp::SolverActionKind::Choice) { + Rule.append(".option-"); + Rule.append(std::to_string(Action.Value)); + } + return Actions->request(Rule, Function, actionInstructionForRegister(Function, VirtualReg)); + }); if (!Solution) return std::unexpected(Solution.error()); @@ -267,7 +312,9 @@ Expected<MachinePassResult> PBQPAllocatorPass::run(MachineFunction &Function, auto Registered = registerStage11MachineAnalyses(TrialAnalyses); if (!Registered) return std::unexpected(Registered.error()); - PBQPAllocatorEngine TrialAllocator(*Trial->ClonedFunction, Target, *Info, TrialAnalyses, Options); + MachineActionReplay Actions(Analyses, Trial->InstructionStableIDs); + PBQPAllocatorEngine TrialAllocator(*Trial->ClonedFunction, Target, *Info, TrialAnalyses, Options, + &Actions); auto TrialRun = TrialAllocator.run(); if (!TrialRun) return std::unexpected(TrialRun.error()); @@ -275,12 +322,16 @@ Expected<MachinePassResult> PBQPAllocatorPass::run(MachineFunction &Function, regalloc_detail::verifyAllocationTrial(*Trial->ClonedFunction, Target, contract()); if (!TrialVerification) return std::unexpected(TrialVerification.error()); - PBQPAllocatorEngine Allocator(Function, Target, *Info, Analyses, Options); + Actions.beginReplay(); + PBQPAllocatorEngine Allocator(Function, Target, *Info, Analyses, Options, &Actions); auto Allocated = Allocator.run(); if (!Allocated) { return std::unexpected(regalloc_detail::withPrefix( Allocated.error(), "PBQPAllocator diverged after a successful transaction preflight: ")); } + auto Replayed = Actions.finishReplay(); + if (!Replayed) + return std::unexpected(Replayed.error()); auto Reserved = regalloc_detail::reserveFunctionRegisters(Function, FunctionReserved); if (!Reserved) return std::unexpected(Reserved.error()); diff --git a/backend/lib/CodeGen/RegisterPressure.cpp b/backend/lib/CodeGen/RegisterPressure.cpp index 523a443..cbd8d8e 100644 --- a/backend/lib/CodeGen/RegisterPressure.cpp +++ b/backend/lib/CodeGen/RegisterPressure.cpp @@ -102,12 +102,12 @@ struct RegisterPressureBuilder final { auto Info = Function->registerInfo().virtualRegisterInfo(Reg); if (!Info) return std::unexpected(Info.error()); - if (!Info->get().RegClass) { + const auto &RegClass = Info->get().RegClass; + if (!RegClass) { return makeUnexpected(ErrorCode::VerificationError, "pre-RA pressure tracking requires constrained virtual registers"); } - const std::span<const RegisterPressureSetID> Sets = - Model->pressureSetsForClass(*Info->get().RegClass); + const std::span<const RegisterPressureSetID> Sets = Model->pressureSetsForClass(*RegClass); return std::vector<RegisterPressureSetID>{Sets.begin(), Sets.end()}; } |