summaryrefslogtreecommitdiff
path: root/lib/CodeGen/GlobalISel/Legalizer.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'lib/CodeGen/GlobalISel/Legalizer.cpp')
-rw-r--r--lib/CodeGen/GlobalISel/Legalizer.cpp249
1 files changed, 110 insertions, 139 deletions
diff --git a/lib/CodeGen/GlobalISel/Legalizer.cpp b/lib/CodeGen/GlobalISel/Legalizer.cpp
index b699156c568b..f09b0d9f11e7 100644
--- a/lib/CodeGen/GlobalISel/Legalizer.cpp
+++ b/lib/CodeGen/GlobalISel/Legalizer.cpp
@@ -14,14 +14,17 @@
//===----------------------------------------------------------------------===//
#include "llvm/CodeGen/GlobalISel/Legalizer.h"
+#include "llvm/ADT/PostOrderIterator.h"
+#include "llvm/ADT/SetVector.h"
+#include "llvm/CodeGen/GlobalISel/GISelWorkList.h"
+#include "llvm/CodeGen/GlobalISel/LegalizationArtifactCombiner.h"
#include "llvm/CodeGen/GlobalISel/LegalizerHelper.h"
#include "llvm/CodeGen/GlobalISel/Utils.h"
#include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/TargetPassConfig.h"
+#include "llvm/CodeGen/TargetSubtargetInfo.h"
#include "llvm/Support/Debug.h"
-#include "llvm/Target/TargetInstrInfo.h"
-#include "llvm/Target/TargetSubtargetInfo.h"
#include <iterator>
@@ -50,79 +53,18 @@ void Legalizer::getAnalysisUsage(AnalysisUsage &AU) const {
void Legalizer::init(MachineFunction &MF) {
}
-bool Legalizer::combineMerges(MachineInstr &MI, MachineRegisterInfo &MRI,
- const TargetInstrInfo &TII,
- MachineIRBuilder &MIRBuilder) {
- if (MI.getOpcode() != TargetOpcode::G_UNMERGE_VALUES)
+static bool isArtifact(const MachineInstr &MI) {
+ switch (MI.getOpcode()) {
+ default:
return false;
-
- unsigned NumDefs = MI.getNumOperands() - 1;
- unsigned SrcReg = MI.getOperand(NumDefs).getReg();
- MachineInstr &MergeI = *MRI.def_instr_begin(SrcReg);
- if (MergeI.getOpcode() != TargetOpcode::G_MERGE_VALUES)
- return false;
-
- const unsigned NumMergeRegs = MergeI.getNumOperands() - 1;
-
- if (NumMergeRegs < NumDefs) {
- if (NumDefs % NumMergeRegs != 0)
- return false;
-
- MIRBuilder.setInstr(MI);
- // Transform to UNMERGEs, for example
- // %1 = G_MERGE_VALUES %4, %5
- // %9, %10, %11, %12 = G_UNMERGE_VALUES %1
- // to
- // %9, %10 = G_UNMERGE_VALUES %4
- // %11, %12 = G_UNMERGE_VALUES %5
-
- const unsigned NewNumDefs = NumDefs / NumMergeRegs;
- for (unsigned Idx = 0; Idx < NumMergeRegs; ++Idx) {
- SmallVector<unsigned, 2> DstRegs;
- for (unsigned j = 0, DefIdx = Idx * NewNumDefs; j < NewNumDefs;
- ++j, ++DefIdx)
- DstRegs.push_back(MI.getOperand(DefIdx).getReg());
-
- MIRBuilder.buildUnmerge(DstRegs, MergeI.getOperand(Idx + 1).getReg());
- }
-
- } else if (NumMergeRegs > NumDefs) {
- if (NumMergeRegs % NumDefs != 0)
- return false;
-
- MIRBuilder.setInstr(MI);
- // Transform to MERGEs
- // %6 = G_MERGE_VALUES %17, %18, %19, %20
- // %7, %8 = G_UNMERGE_VALUES %6
- // to
- // %7 = G_MERGE_VALUES %17, %18
- // %8 = G_MERGE_VALUES %19, %20
-
- const unsigned NumRegs = NumMergeRegs / NumDefs;
- for (unsigned DefIdx = 0; DefIdx < NumDefs; ++DefIdx) {
- SmallVector<unsigned, 2> Regs;
- for (unsigned j = 0, Idx = NumRegs * DefIdx + 1; j < NumRegs; ++j, ++Idx)
- Regs.push_back(MergeI.getOperand(Idx).getReg());
-
- MIRBuilder.buildMerge(MI.getOperand(DefIdx).getReg(), Regs);
- }
-
- } else {
- // FIXME: is a COPY appropriate if the types mismatch? We know both
- // registers are allocatable by now.
- if (MRI.getType(MI.getOperand(0).getReg()) !=
- MRI.getType(MergeI.getOperand(1).getReg()))
- return false;
-
- for (unsigned Idx = 0; Idx < NumDefs; ++Idx)
- MRI.replaceRegWith(MI.getOperand(Idx).getReg(),
- MergeI.getOperand(Idx + 1).getReg());
+ case TargetOpcode::G_TRUNC:
+ case TargetOpcode::G_ZEXT:
+ case TargetOpcode::G_ANYEXT:
+ case TargetOpcode::G_SEXT:
+ case TargetOpcode::G_MERGE_VALUES:
+ case TargetOpcode::G_UNMERGE_VALUES:
+ return true;
}
-
- MI.eraseFromParent();
- if (MRI.use_empty(MergeI.getOperand(0).getReg()))
- MergeI.eraseFromParent();
- return true;
}
bool Legalizer::runOnMachineFunction(MachineFunction &MF) {
@@ -136,79 +78,108 @@ bool Legalizer::runOnMachineFunction(MachineFunction &MF) {
MachineOptimizationRemarkEmitter MORE(MF, /*MBFI=*/nullptr);
LegalizerHelper Helper(MF);
- // FIXME: an instruction may need more than one pass before it is legal. For
- // example on most architectures <3 x i3> is doubly-illegal. It would
- // typically proceed along a path like: <3 x i3> -> <3 x i8> -> <8 x i8>. We
- // probably want a worklist of instructions rather than naive iterate until
- // convergence for performance reasons.
- bool Changed = false;
- MachineBasicBlock::iterator NextMI;
- for (auto &MBB : MF) {
- for (auto MI = MBB.begin(); MI != MBB.end(); MI = NextMI) {
- // Get the next Instruction before we try to legalize, because there's a
- // good chance MI will be deleted.
- NextMI = std::next(MI);
+ const size_t NumBlocks = MF.size();
+ MachineRegisterInfo &MRI = MF.getRegInfo();
+ // Populate Insts
+ GISelWorkList<256> InstList;
+ GISelWorkList<128> ArtifactList;
+ ReversePostOrderTraversal<MachineFunction *> RPOT(&MF);
+ // Perform legalization bottom up so we can DCE as we legalize.
+ // Traverse BB in RPOT and within each basic block, add insts top down,
+ // so when we pop_back_val in the legalization process, we traverse bottom-up.
+ for (auto *MBB : RPOT) {
+ if (MBB->empty())
+ continue;
+ for (MachineInstr &MI : *MBB) {
// Only legalize pre-isel generic instructions: others don't have types
// and are assumed to be legal.
- if (!isPreISelGenericOpcode(MI->getOpcode()))
+ if (!isPreISelGenericOpcode(MI.getOpcode()))
continue;
- unsigned NumNewInsns = 0;
- SmallVector<MachineInstr *, 4> WorkList;
- Helper.MIRBuilder.recordInsertions([&](MachineInstr *MI) {
- // Only legalize pre-isel generic instructions.
- // Legalization process could generate Target specific pseudo
- // instructions with generic types. Don't record them
- if (isPreISelGenericOpcode(MI->getOpcode())) {
- ++NumNewInsns;
- WorkList.push_back(MI);
- }
- });
- WorkList.push_back(&*MI);
-
- bool Changed = false;
- LegalizerHelper::LegalizeResult Res;
- unsigned Idx = 0;
- do {
- Res = Helper.legalizeInstrStep(*WorkList[Idx]);
- // Error out if we couldn't legalize this instruction. We may want to
- // fall back to DAG ISel instead in the future.
- if (Res == LegalizerHelper::UnableToLegalize) {
- Helper.MIRBuilder.stopRecordingInsertions();
- if (Res == LegalizerHelper::UnableToLegalize) {
- reportGISelFailure(MF, TPC, MORE, "gisel-legalize",
- "unable to legalize instruction",
- *WorkList[Idx]);
- return false;
- }
- }
- Changed |= Res == LegalizerHelper::Legalized;
- ++Idx;
-
-#ifndef NDEBUG
- if (NumNewInsns) {
- DEBUG(dbgs() << ".. .. Emitted " << NumNewInsns << " insns\n");
- for (auto I = WorkList.end() - NumNewInsns, E = WorkList.end();
- I != E; ++I)
- DEBUG(dbgs() << ".. .. New MI: "; (*I)->print(dbgs()));
- NumNewInsns = 0;
- }
-#endif
- } while (Idx < WorkList.size());
-
- Helper.MIRBuilder.stopRecordingInsertions();
+ if (isArtifact(MI))
+ ArtifactList.insert(&MI);
+ else
+ InstList.insert(&MI);
}
}
-
- MachineRegisterInfo &MRI = MF.getRegInfo();
- const TargetInstrInfo &TII = *MF.getSubtarget().getInstrInfo();
- for (auto &MBB : MF) {
- for (auto MI = MBB.begin(); MI != MBB.end(); MI = NextMI) {
- // Get the next Instruction before we try to legalize, because there's a
- // good chance MI will be deleted.
- NextMI = std::next(MI);
- Changed |= combineMerges(*MI, MRI, TII, Helper.MIRBuilder);
+ Helper.MIRBuilder.recordInsertions([&](MachineInstr *MI) {
+ // Only legalize pre-isel generic instructions.
+ // Legalization process could generate Target specific pseudo
+ // instructions with generic types. Don't record them
+ if (isPreISelGenericOpcode(MI->getOpcode())) {
+ if (isArtifact(*MI))
+ ArtifactList.insert(MI);
+ else
+ InstList.insert(MI);
}
+ DEBUG(dbgs() << ".. .. New MI: " << *MI;);
+ });
+ const LegalizerInfo &LInfo(Helper.getLegalizerInfo());
+ LegalizationArtifactCombiner ArtCombiner(Helper.MIRBuilder, MF.getRegInfo(), LInfo);
+ auto RemoveDeadInstFromLists = [&InstList,
+ &ArtifactList](MachineInstr *DeadMI) {
+ InstList.remove(DeadMI);
+ ArtifactList.remove(DeadMI);
+ };
+ bool Changed = false;
+ do {
+ while (!InstList.empty()) {
+ MachineInstr &MI = *InstList.pop_back_val();
+ assert(isPreISelGenericOpcode(MI.getOpcode()) && "Expecting generic opcode");
+ if (isTriviallyDead(MI, MRI)) {
+ DEBUG(dbgs() << MI << "Is dead; erasing.\n");
+ MI.eraseFromParentAndMarkDBGValuesForRemoval();
+ continue;
+ }
+
+ // Do the legalization for this instruction.
+ auto Res = Helper.legalizeInstrStep(MI);
+ // Error out if we couldn't legalize this instruction. We may want to
+ // fall back to DAG ISel instead in the future.
+ if (Res == LegalizerHelper::UnableToLegalize) {
+ Helper.MIRBuilder.stopRecordingInsertions();
+ reportGISelFailure(MF, TPC, MORE, "gisel-legalize",
+ "unable to legalize instruction", MI);
+ return false;
+ }
+ Changed |= Res == LegalizerHelper::Legalized;
+ }
+ while (!ArtifactList.empty()) {
+ MachineInstr &MI = *ArtifactList.pop_back_val();
+ assert(isPreISelGenericOpcode(MI.getOpcode()) && "Expecting generic opcode");
+ if (isTriviallyDead(MI, MRI)) {
+ DEBUG(dbgs() << MI << "Is dead; erasing.\n");
+ RemoveDeadInstFromLists(&MI);
+ MI.eraseFromParentAndMarkDBGValuesForRemoval();
+ continue;
+ }
+ SmallVector<MachineInstr *, 4> DeadInstructions;
+ if (ArtCombiner.tryCombineInstruction(MI, DeadInstructions)) {
+ for (auto *DeadMI : DeadInstructions) {
+ DEBUG(dbgs() << ".. Erasing Dead Instruction " << *DeadMI);
+ RemoveDeadInstFromLists(DeadMI);
+ DeadMI->eraseFromParentAndMarkDBGValuesForRemoval();
+ }
+ Changed = true;
+ continue;
+ }
+ // If this was not an artifact (that could be combined away), this might
+ // need special handling. Add it to InstList, so when it's processed
+ // there, it has to be legal or specially handled.
+ else
+ InstList.insert(&MI);
+ }
+ } while (!InstList.empty());
+
+ // For now don't support if new blocks are inserted - we would need to fix the
+ // outerloop for that.
+ if (MF.size() != NumBlocks) {
+ MachineOptimizationRemarkMissed R("gisel-legalize", "GISelFailure",
+ MF.getFunction().getSubprogram(),
+ /*MBB=*/nullptr);
+ R << "inserting blocks is not supported yet";
+ reportGISelFailure(MF, TPC, MORE, R);
+ return false;
}
return Changed;
generated by cgit v1.2.3 (git 2.25.1) at 2025-11-03 19:40:27 +0000