1 //===- llvm/CodeGen/GlobalISel/InstructionSelect.cpp - InstructionSelect ---==//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 /// \file
10 /// This file implements the InstructionSelect class.
11 //===----------------------------------------------------------------------===//
12 
13 #include "llvm/CodeGen/GlobalISel/InstructionSelect.h"
14 #include "llvm/ADT/PostOrderIterator.h"
15 #include "llvm/ADT/Twine.h"
16 #include "llvm/CodeGen/GlobalISel/InstructionSelector.h"
17 #include "llvm/CodeGen/GlobalISel/LegalizerInfo.h"
18 #include "llvm/CodeGen/MachineRegisterInfo.h"
19 #include "llvm/CodeGen/TargetPassConfig.h"
20 #include "llvm/IR/Function.h"
21 #include "llvm/Support/CommandLine.h"
22 #include "llvm/Support/Debug.h"
23 #include "llvm/Target/TargetSubtargetInfo.h"
24 
25 #define DEBUG_TYPE "instruction-select"
26 
27 using namespace llvm;
28 
29 char InstructionSelect::ID = 0;
30 INITIALIZE_PASS_BEGIN(InstructionSelect, DEBUG_TYPE,
31                       "Select target instructions out of generic instructions",
32                       false, false)
33 INITIALIZE_PASS_DEPENDENCY(TargetPassConfig)
34 INITIALIZE_PASS_END(InstructionSelect, DEBUG_TYPE,
35                     "Select target instructions out of generic instructions",
36                     false, false)
37 
38 InstructionSelect::InstructionSelect() : MachineFunctionPass(ID) {
39   initializeInstructionSelectPass(*PassRegistry::getPassRegistry());
40 }
41 
42 void InstructionSelect::getAnalysisUsage(AnalysisUsage &AU) const {
43   AU.addRequired<TargetPassConfig>();
44   MachineFunctionPass::getAnalysisUsage(AU);
45 }
46 
47 static void reportSelectionError(const MachineFunction &MF,
48                                  const MachineInstr *MI, const Twine &Message) {
49   std::string ErrStorage;
50   raw_string_ostream Err(ErrStorage);
51   Err << Message << ":\nIn function: " << MF.getName() << '\n';
52   if (MI)
53     Err << *MI << '\n';
54   report_fatal_error(Err.str());
55 }
56 
57 bool InstructionSelect::runOnMachineFunction(MachineFunction &MF) {
58   // If the ISel pipeline failed, do not bother running that pass.
59   if (MF.getProperties().hasProperty(
60           MachineFunctionProperties::Property::FailedISel))
61     return false;
62 
63   DEBUG(dbgs() << "Selecting function: " << MF.getName() << '\n');
64 
65   const TargetPassConfig &TPC = getAnalysis<TargetPassConfig>();
66   const InstructionSelector *ISel = MF.getSubtarget().getInstructionSelector();
67   assert(ISel && "Cannot work without InstructionSelector");
68 
69   // FIXME: freezeReservedRegs is now done in IRTranslator, but there are many
70   // other MF/MFI fields we need to initialize.
71 
72   const MachineRegisterInfo &MRI = MF.getRegInfo();
73 
74 #ifndef NDEBUG
75   // Check that our input is fully legal: we require the function to have the
76   // Legalized property, so it should be.
77   // FIXME: This should be in the MachineVerifier, but it can't use the
78   // LegalizerInfo as it's currently in the separate GlobalISel library.
79   // The RegBankSelected property is already checked in the verifier. Note
80   // that it has the same layering problem, but we only use inline methods so
81   // end up not needing to link against the GlobalISel library.
82   if (const LegalizerInfo *MLI = MF.getSubtarget().getLegalizerInfo())
83     for (const MachineBasicBlock &MBB : MF)
84       for (const MachineInstr &MI : MBB)
85         if (isPreISelGenericOpcode(MI.getOpcode()) && !MLI->isLegal(MI, MRI))
86           reportSelectionError(MF, &MI, "Instruction is not legal");
87 
88 #endif
89   // FIXME: We could introduce new blocks and will need to fix the outer loop.
90   // Until then, keep track of the number of blocks to assert that we don't.
91   const size_t NumBlocks = MF.size();
92 
93   bool Failed = false;
94   for (MachineBasicBlock *MBB : post_order(&MF)) {
95     if (MBB->empty())
96       continue;
97 
98     // Select instructions in reverse block order. We permit erasing so have
99     // to resort to manually iterating and recognizing the begin (rend) case.
100     bool ReachedBegin = false;
101     for (auto MII = std::prev(MBB->end()), Begin = MBB->begin();
102          !ReachedBegin;) {
103 #ifndef NDEBUG
104       // Keep track of the insertion range for debug printing.
105       const auto AfterIt = std::next(MII);
106 #endif
107       // Select this instruction.
108       MachineInstr &MI = *MII;
109 
110       // And have our iterator point to the next instruction, if there is one.
111       if (MII == Begin)
112         ReachedBegin = true;
113       else
114         --MII;
115 
116       DEBUG(dbgs() << "Selecting: \n  " << MI);
117 
118       if (!ISel->select(MI)) {
119         if (TPC.isGlobalISelAbortEnabled())
120           // FIXME: It would be nice to dump all inserted instructions.  It's
121           // not obvious how, esp. considering select() can insert after MI.
122           reportSelectionError(MF, &MI, "Cannot select");
123         Failed = true;
124         break;
125       }
126 
127       // Dump the range of instructions that MI expanded into.
128       DEBUG({
129         auto InsertedBegin = ReachedBegin ? MBB->begin() : std::next(MII);
130         dbgs() << "Into:\n";
131         for (auto &InsertedMI : make_range(InsertedBegin, AfterIt))
132           dbgs() << "  " << InsertedMI;
133         dbgs() << '\n';
134       });
135     }
136   }
137 
138   // Now that selection is complete, there are no more generic vregs.  Verify
139   // that the size of the now-constrained vreg is unchanged and that it has a
140   // register class.
141   for (auto &VRegToType : MRI.getVRegToType()) {
142     unsigned VReg = VRegToType.first;
143     auto *RC = MRI.getRegClassOrNull(VReg);
144     auto *MI = MRI.def_instr_begin(VReg) == MRI.def_instr_end()
145                    ? nullptr
146                    : &*MRI.def_instr_begin(VReg);
147     if (!RC) {
148       if (TPC.isGlobalISelAbortEnabled())
149         reportSelectionError(MF, MI, "VReg has no regclass after selection");
150       Failed = true;
151       break;
152     }
153 
154     if (VRegToType.second.isValid() &&
155         VRegToType.second.getSizeInBits() > (RC->getSize() * 8)) {
156       if (TPC.isGlobalISelAbortEnabled())
157         reportSelectionError(
158             MF, MI, "VReg has explicit size different from class size");
159       Failed = true;
160       break;
161     }
162   }
163 
164   MRI.getVRegToType().clear();
165 
166   if (!TPC.isGlobalISelAbortEnabled() && (Failed || MF.size() != NumBlocks)) {
167     MF.getProperties().set(MachineFunctionProperties::Property::FailedISel);
168     return false;
169   }
170   assert(MF.size() == NumBlocks && "Inserting blocks is not supported yet");
171 
172   // FIXME: Should we accurately track changes?
173   return true;
174 }
175