llvm/lib/CodeGen/GlobalISel/InstructionSelect.cpp

   1 //===- llvm/CodeGen/GlobalISel/InstructionSelect.cpp - InstructionSelect ---==//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 /// \file
   9 /// This file implements the InstructionSelect class.
  10 //===----------------------------------------------------------------------===//
  11
  12 #include "llvm/CodeGen/GlobalISel/InstructionSelect.h"
  13 #include "llvm/ADT/PostOrderIterator.h"
  14 #include "llvm/ADT/ScopeExit.h"
  15 #include "llvm/ADT/Twine.h"
  16 #include "llvm/Analysis/BlockFrequencyInfo.h"
  17 #include "llvm/Analysis/LazyBlockFrequencyInfo.h"
  18 #include "llvm/Analysis/ProfileSummaryInfo.h"
  19 #include "llvm/CodeGen/GlobalISel/GISelKnownBits.h"
  20 #include "llvm/CodeGen/GlobalISel/InstructionSelector.h"
  21 #include "llvm/CodeGen/GlobalISel/LegalizerInfo.h"
  22 #include "llvm/CodeGen/GlobalISel/Utils.h"
  23 #include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h"
  24 #include "llvm/CodeGen/MachineFrameInfo.h"
  25 #include "llvm/CodeGen/MachineRegisterInfo.h"
  26 #include "llvm/CodeGen/TargetInstrInfo.h"
  27 #include "llvm/CodeGen/TargetLowering.h"
  28 #include "llvm/CodeGen/TargetPassConfig.h"
  29 #include "llvm/CodeGen/TargetSubtargetInfo.h"
  30 #include "llvm/Config/config.h"
  31 #include "llvm/IR/Constants.h"
  32 #include "llvm/IR/Function.h"
  33 #include "llvm/Support/CommandLine.h"
  34 #include "llvm/Support/Debug.h"
  35 #include "llvm/Support/TargetRegistry.h"
  36 #include "llvm/Target/TargetMachine.h"
  37
  38 #define DEBUG_TYPE "instruction-select"
  39
  40 using namespace llvm;
  41
  42 #ifdef LLVM_GISEL_COV_PREFIX
  43 static cl::opt<std::string>
  44     CoveragePrefix("gisel-coverage-prefix", cl::init(LLVM_GISEL_COV_PREFIX),
  45                    cl::desc("Record GlobalISel rule coverage files of this "
  46                             "prefix if instrumentation was generated"));
  47 #else
  48 static const std::string CoveragePrefix;
  49 #endif
  50
  51 char InstructionSelect::ID = 0;
  52 INITIALIZE_PASS_BEGIN(InstructionSelect, DEBUG_TYPE,
  53                       "Select target instructions out of generic instructions",
  54                       false, false)
  55 INITIALIZE_PASS_DEPENDENCY(TargetPassConfig)
  56 INITIALIZE_PASS_DEPENDENCY(GISelKnownBitsAnalysis)
  57 INITIALIZE_PASS_DEPENDENCY(ProfileSummaryInfoWrapperPass)
  58 INITIALIZE_PASS_DEPENDENCY(LazyBlockFrequencyInfoPass)
  59 INITIALIZE_PASS_END(InstructionSelect, DEBUG_TYPE,
  60                     "Select target instructions out of generic instructions",
  61                     false, false)
  62
  63 InstructionSelect::InstructionSelect(CodeGenOpt::Level OL)
  64     : MachineFunctionPass(ID), OptLevel(OL) {}
  65
  66 // In order not to crash when calling getAnalysis during testing with -run-pass
  67 // we use the default opt level here instead of None, so that the addRequired()
  68 // calls are made in getAnalysisUsage().
  69 InstructionSelect::InstructionSelect()
  70     : MachineFunctionPass(ID), OptLevel(CodeGenOpt::Default) {}
  71
  72 void InstructionSelect::getAnalysisUsage(AnalysisUsage &AU) const {
  73   AU.addRequired<TargetPassConfig>();
  74   if (OptLevel != CodeGenOpt::None) {
  75     AU.addRequired<GISelKnownBitsAnalysis>();
  76     AU.addPreserved<GISelKnownBitsAnalysis>();
  77     AU.addRequired<ProfileSummaryInfoWrapperPass>();
  78     LazyBlockFrequencyInfoPass::getLazyBFIAnalysisUsage(AU);
  79   }
  80   getSelectionDAGFallbackAnalysisUsage(AU);
  81   MachineFunctionPass::getAnalysisUsage(AU);
  82 }
  83
  84 bool InstructionSelect::runOnMachineFunction(MachineFunction &MF) {
  85   // If the ISel pipeline failed, do not bother running that pass.
  86   if (MF.getProperties().hasProperty(
  87           MachineFunctionProperties::Property::FailedISel))
  88     return false;
  89
  90   LLVM_DEBUG(dbgs() << "Selecting function: " << MF.getName() << '\n');
  91
  92   const TargetPassConfig &TPC = getAnalysis<TargetPassConfig>();
  93   InstructionSelector *ISel = MF.getSubtarget().getInstructionSelector();
  94
  95   CodeGenOpt::Level OldOptLevel = OptLevel;
  96   auto RestoreOptLevel = make_scope_exit([=]() { OptLevel = OldOptLevel; });
  97   OptLevel = MF.getFunction().hasOptNone() ? CodeGenOpt::None
  98                                            : MF.getTarget().getOptLevel();
  99
 100   GISelKnownBits *KB = nullptr;
 101   if (OptLevel != CodeGenOpt::None) {
 102     KB = &getAnalysis<GISelKnownBitsAnalysis>().get(MF);
 103     PSI = &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI();
 104     if (PSI && PSI->hasProfileSummary())
 105       BFI = &getAnalysis<LazyBlockFrequencyInfoPass>().getBFI();
 106   }
 107
 108   CodeGenCoverage CoverageInfo;
 109   assert(ISel && "Cannot work without InstructionSelector");
 110   ISel->setupMF(MF, KB, CoverageInfo, PSI, BFI);
 111
 112   // An optimization remark emitter. Used to report failures.
 113   MachineOptimizationRemarkEmitter MORE(MF, /*MBFI=*/nullptr);
 114
 115   // FIXME: There are many other MF/MFI fields we need to initialize.
 116
 117   MachineRegisterInfo &MRI = MF.getRegInfo();
 118 #ifndef NDEBUG
 119   // Check that our input is fully legal: we require the function to have the
 120   // Legalized property, so it should be.
 121   // FIXME: This should be in the MachineVerifier, as the RegBankSelected
 122   // property check already is.
 123   if (!DisableGISelLegalityCheck)
 124     if (const MachineInstr *MI = machineFunctionIsIllegal(MF)) {
 125       reportGISelFailure(MF, TPC, MORE, "gisel-select",
 126                          "instruction is not legal", *MI);
 127       return false;
 128     }
 129   // FIXME: We could introduce new blocks and will need to fix the outer loop.
 130   // Until then, keep track of the number of blocks to assert that we don't.
 131   const size_t NumBlocks = MF.size();
 132 #endif
 133
 134   for (MachineBasicBlock *MBB : post_order(&MF)) {
 135     ISel->CurMBB = MBB;
 136     if (MBB->empty())
 137       continue;
 138
 139     // Select instructions in reverse block order. We permit erasing so have
 140     // to resort to manually iterating and recognizing the begin (rend) case.
 141     bool ReachedBegin = false;
 142     for (auto MII = std::prev(MBB->end()), Begin = MBB->begin();
 143          !ReachedBegin;) {
 144 #ifndef NDEBUG
 145       // Keep track of the insertion range for debug printing.
 146       const auto AfterIt = std::next(MII);
 147 #endif
 148       // Select this instruction.
 149       MachineInstr &MI = *MII;
 150
 151       // And have our iterator point to the next instruction, if there is one.
 152       if (MII == Begin)
 153         ReachedBegin = true;
 154       else
 155         --MII;
 156
 157       LLVM_DEBUG(dbgs() << "Selecting: \n  " << MI);
 158
 159       // We could have folded this instruction away already, making it dead.
 160       // If so, erase it.
 161       if (isTriviallyDead(MI, MRI)) {
 162         LLVM_DEBUG(dbgs() << "Is dead; erasing.\n");
 163         MI.eraseFromParentAndMarkDBGValuesForRemoval();
 164         continue;
 165       }
 166
 167       // Eliminate hints.
 168       if (isPreISelGenericOptimizationHint(MI.getOpcode())) {
 169         Register DstReg = MI.getOperand(0).getReg();
 170         Register SrcReg = MI.getOperand(1).getReg();
 171
 172         // At this point, the destination register class of the hint may have
 173         // been decided.
 174         //
 175         // Propagate that through to the source register.
 176         const TargetRegisterClass *DstRC = MRI.getRegClassOrNull(DstReg);
 177         if (DstRC)
 178           MRI.setRegClass(SrcReg, DstRC);
 179         assert(canReplaceReg(DstReg, SrcReg, MRI) &&
 180                "Must be able to replace dst with src!");
 181         MI.eraseFromParent();
 182         MRI.replaceRegWith(DstReg, SrcReg);
 183         continue;
 184       }
 185
 186       if (!ISel->select(MI)) {
 187         // FIXME: It would be nice to dump all inserted instructions.  It's
 188         // not obvious how, esp. considering select() can insert after MI.
 189         reportGISelFailure(MF, TPC, MORE, "gisel-select", "cannot select", MI);
 190         return false;
 191       }
 192
 193       // Dump the range of instructions that MI expanded into.
 194       LLVM_DEBUG({
 195         auto InsertedBegin = ReachedBegin ? MBB->begin() : std::next(MII);
 196         dbgs() << "Into:\n";
 197         for (auto &InsertedMI : make_range(InsertedBegin, AfterIt))
 198           dbgs() << "  " << InsertedMI;
 199         dbgs() << '\n';
 200       });
 201     }
 202   }
 203
 204   for (MachineBasicBlock &MBB : MF) {
 205     if (MBB.empty())
 206       continue;
 207
 208     // Try to find redundant copies b/w vregs of the same register class.
 209     bool ReachedBegin = false;
 210     for (auto MII = std::prev(MBB.end()), Begin = MBB.begin(); !ReachedBegin;) {
 211       // Select this instruction.
 212       MachineInstr &MI = *MII;
 213
 214       // And have our iterator point to the next instruction, if there is one.
 215       if (MII == Begin)
 216         ReachedBegin = true;
 217       else
 218         --MII;
 219       if (MI.getOpcode() != TargetOpcode::COPY)
 220         continue;
 221       Register SrcReg = MI.getOperand(1).getReg();
 222       Register DstReg = MI.getOperand(0).getReg();
 223       if (Register::isVirtualRegister(SrcReg) &&
 224           Register::isVirtualRegister(DstReg)) {
 225         auto SrcRC = MRI.getRegClass(SrcReg);
 226         auto DstRC = MRI.getRegClass(DstReg);
 227         if (SrcRC == DstRC) {
 228           MRI.replaceRegWith(DstReg, SrcReg);
 229           MI.eraseFromParent();
 230         }
 231       }
 232     }
 233   }
 234
 235 #ifndef NDEBUG
 236   const TargetRegisterInfo &TRI = *MF.getSubtarget().getRegisterInfo();
 237   // Now that selection is complete, there are no more generic vregs.  Verify
 238   // that the size of the now-constrained vreg is unchanged and that it has a
 239   // register class.
 240   for (unsigned I = 0, E = MRI.getNumVirtRegs(); I != E; ++I) {
 241     unsigned VReg = Register::index2VirtReg(I);
 242
 243     MachineInstr *MI = nullptr;
 244     if (!MRI.def_empty(VReg))
 245       MI = &*MRI.def_instr_begin(VReg);
 246     else if (!MRI.use_empty(VReg))
 247       MI = &*MRI.use_instr_begin(VReg);
 248     if (!MI)
 249       continue;
 250
 251     const TargetRegisterClass *RC = MRI.getRegClassOrNull(VReg);
 252     if (!RC) {
 253       reportGISelFailure(MF, TPC, MORE, "gisel-select",
 254                          "VReg has no regclass after selection", *MI);
 255       return false;
 256     }
 257
 258     const LLT Ty = MRI.getType(VReg);
 259     if (Ty.isValid() && Ty.getSizeInBits() > TRI.getRegSizeInBits(*RC)) {
 260       reportGISelFailure(
 261           MF, TPC, MORE, "gisel-select",
 262           "VReg's low-level type and register class have different sizes", *MI);
 263       return false;
 264     }
 265   }
 266
 267   if (MF.size() != NumBlocks) {
 268     MachineOptimizationRemarkMissed R("gisel-select", "GISelFailure",
 269                                       MF.getFunction().getSubprogram(),
 270                                       /*MBB=*/nullptr);
 271     R << "inserting blocks is not supported yet";
 272     reportGISelFailure(MF, TPC, MORE, R);
 273     return false;
 274   }
 275 #endif
 276   // Determine if there are any calls in this machine function. Ported from
 277   // SelectionDAG.
 278   MachineFrameInfo &MFI = MF.getFrameInfo();
 279   for (const auto &MBB : MF) {
 280     if (MFI.hasCalls() && MF.hasInlineAsm())
 281       break;
 282
 283     for (const auto &MI : MBB) {
 284       if ((MI.isCall() && !MI.isReturn()) || MI.isStackAligningInlineAsm())
 285         MFI.setHasCalls(true);
 286       if (MI.isInlineAsm())
 287         MF.setHasInlineAsm(true);
 288     }
 289   }
 290
 291   // FIXME: FinalizeISel pass calls finalizeLowering, so it's called twice.
 292   auto &TLI = *MF.getSubtarget().getTargetLowering();
 293   TLI.finalizeLowering(MF);
 294
 295   LLVM_DEBUG({
 296     dbgs() << "Rules covered by selecting function: " << MF.getName() << ":";
 297     for (auto RuleID : CoverageInfo.covered())
 298       dbgs() << " id" << RuleID;
 299     dbgs() << "\n\n";
 300   });
 301   CoverageInfo.emit(CoveragePrefix,
 302                     TLI.getTargetMachine().getTarget().getBackendName());
 303
 304   // If we successfully selected the function nothing is going to use the vreg
 305   // types after us (otherwise MIRPrinter would need them). Make sure the types
 306   // disappear.
 307   MRI.clearVirtRegTypes();
 308
 309   // FIXME: Should we accurately track changes?
 310   return true;
 311 }