106f32e7eSjoerg //===- llvm/CodeGen/GlobalISel/InstructionSelect.cpp - InstructionSelect ---==//
206f32e7eSjoerg //
306f32e7eSjoerg // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
406f32e7eSjoerg // See https://llvm.org/LICENSE.txt for license information.
506f32e7eSjoerg // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
606f32e7eSjoerg //
706f32e7eSjoerg //===----------------------------------------------------------------------===//
806f32e7eSjoerg /// \file
906f32e7eSjoerg /// This file implements the InstructionSelect class.
1006f32e7eSjoerg //===----------------------------------------------------------------------===//
1106f32e7eSjoerg
1206f32e7eSjoerg #include "llvm/CodeGen/GlobalISel/InstructionSelect.h"
1306f32e7eSjoerg #include "llvm/ADT/PostOrderIterator.h"
14*da58b97aSjoerg #include "llvm/ADT/ScopeExit.h"
1506f32e7eSjoerg #include "llvm/ADT/Twine.h"
16*da58b97aSjoerg #include "llvm/Analysis/BlockFrequencyInfo.h"
17*da58b97aSjoerg #include "llvm/Analysis/LazyBlockFrequencyInfo.h"
18*da58b97aSjoerg #include "llvm/Analysis/ProfileSummaryInfo.h"
1906f32e7eSjoerg #include "llvm/CodeGen/GlobalISel/GISelKnownBits.h"
2006f32e7eSjoerg #include "llvm/CodeGen/GlobalISel/InstructionSelector.h"
2106f32e7eSjoerg #include "llvm/CodeGen/GlobalISel/LegalizerInfo.h"
2206f32e7eSjoerg #include "llvm/CodeGen/GlobalISel/Utils.h"
2306f32e7eSjoerg #include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h"
2406f32e7eSjoerg #include "llvm/CodeGen/MachineFrameInfo.h"
2506f32e7eSjoerg #include "llvm/CodeGen/MachineRegisterInfo.h"
2606f32e7eSjoerg #include "llvm/CodeGen/TargetInstrInfo.h"
2706f32e7eSjoerg #include "llvm/CodeGen/TargetLowering.h"
2806f32e7eSjoerg #include "llvm/CodeGen/TargetPassConfig.h"
2906f32e7eSjoerg #include "llvm/CodeGen/TargetSubtargetInfo.h"
3006f32e7eSjoerg #include "llvm/Config/config.h"
3106f32e7eSjoerg #include "llvm/IR/Constants.h"
3206f32e7eSjoerg #include "llvm/IR/Function.h"
3306f32e7eSjoerg #include "llvm/Support/CommandLine.h"
3406f32e7eSjoerg #include "llvm/Support/Debug.h"
3506f32e7eSjoerg #include "llvm/Support/TargetRegistry.h"
36*da58b97aSjoerg #include "llvm/Target/TargetMachine.h"
3706f32e7eSjoerg
3806f32e7eSjoerg #define DEBUG_TYPE "instruction-select"
3906f32e7eSjoerg
4006f32e7eSjoerg using namespace llvm;
4106f32e7eSjoerg
4206f32e7eSjoerg #ifdef LLVM_GISEL_COV_PREFIX
4306f32e7eSjoerg static cl::opt<std::string>
4406f32e7eSjoerg CoveragePrefix("gisel-coverage-prefix", cl::init(LLVM_GISEL_COV_PREFIX),
4506f32e7eSjoerg cl::desc("Record GlobalISel rule coverage files of this "
4606f32e7eSjoerg "prefix if instrumentation was generated"));
4706f32e7eSjoerg #else
48*da58b97aSjoerg static const std::string CoveragePrefix;
4906f32e7eSjoerg #endif
5006f32e7eSjoerg
5106f32e7eSjoerg char InstructionSelect::ID = 0;
5206f32e7eSjoerg INITIALIZE_PASS_BEGIN(InstructionSelect, DEBUG_TYPE,
5306f32e7eSjoerg "Select target instructions out of generic instructions",
5406f32e7eSjoerg false, false)
INITIALIZE_PASS_DEPENDENCY(TargetPassConfig)5506f32e7eSjoerg INITIALIZE_PASS_DEPENDENCY(TargetPassConfig)
5606f32e7eSjoerg INITIALIZE_PASS_DEPENDENCY(GISelKnownBitsAnalysis)
57*da58b97aSjoerg INITIALIZE_PASS_DEPENDENCY(ProfileSummaryInfoWrapperPass)
58*da58b97aSjoerg INITIALIZE_PASS_DEPENDENCY(LazyBlockFrequencyInfoPass)
5906f32e7eSjoerg INITIALIZE_PASS_END(InstructionSelect, DEBUG_TYPE,
6006f32e7eSjoerg "Select target instructions out of generic instructions",
6106f32e7eSjoerg false, false)
6206f32e7eSjoerg
63*da58b97aSjoerg InstructionSelect::InstructionSelect(CodeGenOpt::Level OL)
64*da58b97aSjoerg : MachineFunctionPass(ID), OptLevel(OL) {}
65*da58b97aSjoerg
66*da58b97aSjoerg // In order not to crash when calling getAnalysis during testing with -run-pass
67*da58b97aSjoerg // we use the default opt level here instead of None, so that the addRequired()
68*da58b97aSjoerg // calls are made in getAnalysisUsage().
InstructionSelect()69*da58b97aSjoerg InstructionSelect::InstructionSelect()
70*da58b97aSjoerg : MachineFunctionPass(ID), OptLevel(CodeGenOpt::Default) {}
7106f32e7eSjoerg
getAnalysisUsage(AnalysisUsage & AU) const7206f32e7eSjoerg void InstructionSelect::getAnalysisUsage(AnalysisUsage &AU) const {
7306f32e7eSjoerg AU.addRequired<TargetPassConfig>();
74*da58b97aSjoerg if (OptLevel != CodeGenOpt::None) {
7506f32e7eSjoerg AU.addRequired<GISelKnownBitsAnalysis>();
7606f32e7eSjoerg AU.addPreserved<GISelKnownBitsAnalysis>();
77*da58b97aSjoerg AU.addRequired<ProfileSummaryInfoWrapperPass>();
78*da58b97aSjoerg LazyBlockFrequencyInfoPass::getLazyBFIAnalysisUsage(AU);
79*da58b97aSjoerg }
8006f32e7eSjoerg getSelectionDAGFallbackAnalysisUsage(AU);
8106f32e7eSjoerg MachineFunctionPass::getAnalysisUsage(AU);
8206f32e7eSjoerg }
8306f32e7eSjoerg
runOnMachineFunction(MachineFunction & MF)8406f32e7eSjoerg bool InstructionSelect::runOnMachineFunction(MachineFunction &MF) {
8506f32e7eSjoerg // If the ISel pipeline failed, do not bother running that pass.
8606f32e7eSjoerg if (MF.getProperties().hasProperty(
8706f32e7eSjoerg MachineFunctionProperties::Property::FailedISel))
8806f32e7eSjoerg return false;
8906f32e7eSjoerg
9006f32e7eSjoerg LLVM_DEBUG(dbgs() << "Selecting function: " << MF.getName() << '\n');
9106f32e7eSjoerg
9206f32e7eSjoerg const TargetPassConfig &TPC = getAnalysis<TargetPassConfig>();
9306f32e7eSjoerg InstructionSelector *ISel = MF.getSubtarget().getInstructionSelector();
94*da58b97aSjoerg
95*da58b97aSjoerg CodeGenOpt::Level OldOptLevel = OptLevel;
96*da58b97aSjoerg auto RestoreOptLevel = make_scope_exit([=]() { OptLevel = OldOptLevel; });
97*da58b97aSjoerg OptLevel = MF.getFunction().hasOptNone() ? CodeGenOpt::None
98*da58b97aSjoerg : MF.getTarget().getOptLevel();
99*da58b97aSjoerg
100*da58b97aSjoerg GISelKnownBits *KB = nullptr;
101*da58b97aSjoerg if (OptLevel != CodeGenOpt::None) {
102*da58b97aSjoerg KB = &getAnalysis<GISelKnownBitsAnalysis>().get(MF);
103*da58b97aSjoerg PSI = &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI();
104*da58b97aSjoerg if (PSI && PSI->hasProfileSummary())
105*da58b97aSjoerg BFI = &getAnalysis<LazyBlockFrequencyInfoPass>().getBFI();
106*da58b97aSjoerg }
107*da58b97aSjoerg
10806f32e7eSjoerg CodeGenCoverage CoverageInfo;
10906f32e7eSjoerg assert(ISel && "Cannot work without InstructionSelector");
110*da58b97aSjoerg ISel->setupMF(MF, KB, CoverageInfo, PSI, BFI);
11106f32e7eSjoerg
11206f32e7eSjoerg // An optimization remark emitter. Used to report failures.
11306f32e7eSjoerg MachineOptimizationRemarkEmitter MORE(MF, /*MBFI=*/nullptr);
11406f32e7eSjoerg
11506f32e7eSjoerg // FIXME: There are many other MF/MFI fields we need to initialize.
11606f32e7eSjoerg
11706f32e7eSjoerg MachineRegisterInfo &MRI = MF.getRegInfo();
11806f32e7eSjoerg #ifndef NDEBUG
11906f32e7eSjoerg // Check that our input is fully legal: we require the function to have the
12006f32e7eSjoerg // Legalized property, so it should be.
12106f32e7eSjoerg // FIXME: This should be in the MachineVerifier, as the RegBankSelected
12206f32e7eSjoerg // property check already is.
12306f32e7eSjoerg if (!DisableGISelLegalityCheck)
12406f32e7eSjoerg if (const MachineInstr *MI = machineFunctionIsIllegal(MF)) {
12506f32e7eSjoerg reportGISelFailure(MF, TPC, MORE, "gisel-select",
12606f32e7eSjoerg "instruction is not legal", *MI);
12706f32e7eSjoerg return false;
12806f32e7eSjoerg }
12906f32e7eSjoerg // FIXME: We could introduce new blocks and will need to fix the outer loop.
13006f32e7eSjoerg // Until then, keep track of the number of blocks to assert that we don't.
13106f32e7eSjoerg const size_t NumBlocks = MF.size();
13206f32e7eSjoerg #endif
13306f32e7eSjoerg
13406f32e7eSjoerg for (MachineBasicBlock *MBB : post_order(&MF)) {
135*da58b97aSjoerg ISel->CurMBB = MBB;
13606f32e7eSjoerg if (MBB->empty())
13706f32e7eSjoerg continue;
13806f32e7eSjoerg
13906f32e7eSjoerg // Select instructions in reverse block order. We permit erasing so have
14006f32e7eSjoerg // to resort to manually iterating and recognizing the begin (rend) case.
14106f32e7eSjoerg bool ReachedBegin = false;
14206f32e7eSjoerg for (auto MII = std::prev(MBB->end()), Begin = MBB->begin();
14306f32e7eSjoerg !ReachedBegin;) {
14406f32e7eSjoerg #ifndef NDEBUG
14506f32e7eSjoerg // Keep track of the insertion range for debug printing.
14606f32e7eSjoerg const auto AfterIt = std::next(MII);
14706f32e7eSjoerg #endif
14806f32e7eSjoerg // Select this instruction.
14906f32e7eSjoerg MachineInstr &MI = *MII;
15006f32e7eSjoerg
15106f32e7eSjoerg // And have our iterator point to the next instruction, if there is one.
15206f32e7eSjoerg if (MII == Begin)
15306f32e7eSjoerg ReachedBegin = true;
15406f32e7eSjoerg else
15506f32e7eSjoerg --MII;
15606f32e7eSjoerg
15706f32e7eSjoerg LLVM_DEBUG(dbgs() << "Selecting: \n " << MI);
15806f32e7eSjoerg
15906f32e7eSjoerg // We could have folded this instruction away already, making it dead.
16006f32e7eSjoerg // If so, erase it.
16106f32e7eSjoerg if (isTriviallyDead(MI, MRI)) {
16206f32e7eSjoerg LLVM_DEBUG(dbgs() << "Is dead; erasing.\n");
16306f32e7eSjoerg MI.eraseFromParentAndMarkDBGValuesForRemoval();
16406f32e7eSjoerg continue;
16506f32e7eSjoerg }
16606f32e7eSjoerg
167*da58b97aSjoerg // Eliminate hints.
168*da58b97aSjoerg if (isPreISelGenericOptimizationHint(MI.getOpcode())) {
169*da58b97aSjoerg Register DstReg = MI.getOperand(0).getReg();
170*da58b97aSjoerg Register SrcReg = MI.getOperand(1).getReg();
171*da58b97aSjoerg
172*da58b97aSjoerg // At this point, the destination register class of the hint may have
173*da58b97aSjoerg // been decided.
174*da58b97aSjoerg //
175*da58b97aSjoerg // Propagate that through to the source register.
176*da58b97aSjoerg const TargetRegisterClass *DstRC = MRI.getRegClassOrNull(DstReg);
177*da58b97aSjoerg if (DstRC)
178*da58b97aSjoerg MRI.setRegClass(SrcReg, DstRC);
179*da58b97aSjoerg assert(canReplaceReg(DstReg, SrcReg, MRI) &&
180*da58b97aSjoerg "Must be able to replace dst with src!");
181*da58b97aSjoerg MI.eraseFromParent();
182*da58b97aSjoerg MRI.replaceRegWith(DstReg, SrcReg);
183*da58b97aSjoerg continue;
184*da58b97aSjoerg }
185*da58b97aSjoerg
18606f32e7eSjoerg if (!ISel->select(MI)) {
18706f32e7eSjoerg // FIXME: It would be nice to dump all inserted instructions. It's
18806f32e7eSjoerg // not obvious how, esp. considering select() can insert after MI.
18906f32e7eSjoerg reportGISelFailure(MF, TPC, MORE, "gisel-select", "cannot select", MI);
19006f32e7eSjoerg return false;
19106f32e7eSjoerg }
19206f32e7eSjoerg
19306f32e7eSjoerg // Dump the range of instructions that MI expanded into.
19406f32e7eSjoerg LLVM_DEBUG({
19506f32e7eSjoerg auto InsertedBegin = ReachedBegin ? MBB->begin() : std::next(MII);
19606f32e7eSjoerg dbgs() << "Into:\n";
19706f32e7eSjoerg for (auto &InsertedMI : make_range(InsertedBegin, AfterIt))
19806f32e7eSjoerg dbgs() << " " << InsertedMI;
19906f32e7eSjoerg dbgs() << '\n';
20006f32e7eSjoerg });
20106f32e7eSjoerg }
20206f32e7eSjoerg }
20306f32e7eSjoerg
20406f32e7eSjoerg for (MachineBasicBlock &MBB : MF) {
20506f32e7eSjoerg if (MBB.empty())
20606f32e7eSjoerg continue;
20706f32e7eSjoerg
20806f32e7eSjoerg // Try to find redundant copies b/w vregs of the same register class.
20906f32e7eSjoerg bool ReachedBegin = false;
21006f32e7eSjoerg for (auto MII = std::prev(MBB.end()), Begin = MBB.begin(); !ReachedBegin;) {
21106f32e7eSjoerg // Select this instruction.
21206f32e7eSjoerg MachineInstr &MI = *MII;
21306f32e7eSjoerg
21406f32e7eSjoerg // And have our iterator point to the next instruction, if there is one.
21506f32e7eSjoerg if (MII == Begin)
21606f32e7eSjoerg ReachedBegin = true;
21706f32e7eSjoerg else
21806f32e7eSjoerg --MII;
21906f32e7eSjoerg if (MI.getOpcode() != TargetOpcode::COPY)
22006f32e7eSjoerg continue;
22106f32e7eSjoerg Register SrcReg = MI.getOperand(1).getReg();
22206f32e7eSjoerg Register DstReg = MI.getOperand(0).getReg();
22306f32e7eSjoerg if (Register::isVirtualRegister(SrcReg) &&
22406f32e7eSjoerg Register::isVirtualRegister(DstReg)) {
22506f32e7eSjoerg auto SrcRC = MRI.getRegClass(SrcReg);
22606f32e7eSjoerg auto DstRC = MRI.getRegClass(DstReg);
22706f32e7eSjoerg if (SrcRC == DstRC) {
22806f32e7eSjoerg MRI.replaceRegWith(DstReg, SrcReg);
229*da58b97aSjoerg MI.eraseFromParent();
23006f32e7eSjoerg }
23106f32e7eSjoerg }
23206f32e7eSjoerg }
23306f32e7eSjoerg }
23406f32e7eSjoerg
23506f32e7eSjoerg #ifndef NDEBUG
23606f32e7eSjoerg const TargetRegisterInfo &TRI = *MF.getSubtarget().getRegisterInfo();
23706f32e7eSjoerg // Now that selection is complete, there are no more generic vregs. Verify
23806f32e7eSjoerg // that the size of the now-constrained vreg is unchanged and that it has a
23906f32e7eSjoerg // register class.
24006f32e7eSjoerg for (unsigned I = 0, E = MRI.getNumVirtRegs(); I != E; ++I) {
24106f32e7eSjoerg unsigned VReg = Register::index2VirtReg(I);
24206f32e7eSjoerg
24306f32e7eSjoerg MachineInstr *MI = nullptr;
24406f32e7eSjoerg if (!MRI.def_empty(VReg))
24506f32e7eSjoerg MI = &*MRI.def_instr_begin(VReg);
24606f32e7eSjoerg else if (!MRI.use_empty(VReg))
24706f32e7eSjoerg MI = &*MRI.use_instr_begin(VReg);
24806f32e7eSjoerg if (!MI)
24906f32e7eSjoerg continue;
25006f32e7eSjoerg
25106f32e7eSjoerg const TargetRegisterClass *RC = MRI.getRegClassOrNull(VReg);
25206f32e7eSjoerg if (!RC) {
25306f32e7eSjoerg reportGISelFailure(MF, TPC, MORE, "gisel-select",
25406f32e7eSjoerg "VReg has no regclass after selection", *MI);
25506f32e7eSjoerg return false;
25606f32e7eSjoerg }
25706f32e7eSjoerg
25806f32e7eSjoerg const LLT Ty = MRI.getType(VReg);
25906f32e7eSjoerg if (Ty.isValid() && Ty.getSizeInBits() > TRI.getRegSizeInBits(*RC)) {
26006f32e7eSjoerg reportGISelFailure(
26106f32e7eSjoerg MF, TPC, MORE, "gisel-select",
26206f32e7eSjoerg "VReg's low-level type and register class have different sizes", *MI);
26306f32e7eSjoerg return false;
26406f32e7eSjoerg }
26506f32e7eSjoerg }
26606f32e7eSjoerg
26706f32e7eSjoerg if (MF.size() != NumBlocks) {
26806f32e7eSjoerg MachineOptimizationRemarkMissed R("gisel-select", "GISelFailure",
26906f32e7eSjoerg MF.getFunction().getSubprogram(),
27006f32e7eSjoerg /*MBB=*/nullptr);
27106f32e7eSjoerg R << "inserting blocks is not supported yet";
27206f32e7eSjoerg reportGISelFailure(MF, TPC, MORE, R);
27306f32e7eSjoerg return false;
27406f32e7eSjoerg }
27506f32e7eSjoerg #endif
27606f32e7eSjoerg // Determine if there are any calls in this machine function. Ported from
27706f32e7eSjoerg // SelectionDAG.
27806f32e7eSjoerg MachineFrameInfo &MFI = MF.getFrameInfo();
27906f32e7eSjoerg for (const auto &MBB : MF) {
28006f32e7eSjoerg if (MFI.hasCalls() && MF.hasInlineAsm())
28106f32e7eSjoerg break;
28206f32e7eSjoerg
28306f32e7eSjoerg for (const auto &MI : MBB) {
28406f32e7eSjoerg if ((MI.isCall() && !MI.isReturn()) || MI.isStackAligningInlineAsm())
28506f32e7eSjoerg MFI.setHasCalls(true);
28606f32e7eSjoerg if (MI.isInlineAsm())
28706f32e7eSjoerg MF.setHasInlineAsm(true);
28806f32e7eSjoerg }
28906f32e7eSjoerg }
29006f32e7eSjoerg
291*da58b97aSjoerg // FIXME: FinalizeISel pass calls finalizeLowering, so it's called twice.
292*da58b97aSjoerg auto &TLI = *MF.getSubtarget().getTargetLowering();
293*da58b97aSjoerg TLI.finalizeLowering(MF);
29406f32e7eSjoerg
29506f32e7eSjoerg LLVM_DEBUG({
29606f32e7eSjoerg dbgs() << "Rules covered by selecting function: " << MF.getName() << ":";
29706f32e7eSjoerg for (auto RuleID : CoverageInfo.covered())
29806f32e7eSjoerg dbgs() << " id" << RuleID;
29906f32e7eSjoerg dbgs() << "\n\n";
30006f32e7eSjoerg });
30106f32e7eSjoerg CoverageInfo.emit(CoveragePrefix,
302*da58b97aSjoerg TLI.getTargetMachine().getTarget().getBackendName());
30306f32e7eSjoerg
30406f32e7eSjoerg // If we successfully selected the function nothing is going to use the vreg
30506f32e7eSjoerg // types after us (otherwise MIRPrinter would need them). Make sure the types
30606f32e7eSjoerg // disappear.
30706f32e7eSjoerg MRI.clearVirtRegTypes();
30806f32e7eSjoerg
30906f32e7eSjoerg // FIXME: Should we accurately track changes?
31006f32e7eSjoerg return true;
31106f32e7eSjoerg }
312