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/Analysis/LazyBlockFrequencyInfo.h"
  16 #include "llvm/Analysis/ProfileSummaryInfo.h"
  17 #include "llvm/CodeGen/GlobalISel/GISelKnownBits.h"
  18 #include "llvm/CodeGen/GlobalISel/InstructionSelector.h"
  19 #include "llvm/CodeGen/GlobalISel/LegalizerInfo.h"
  20 #include "llvm/CodeGen/GlobalISel/Utils.h"
  21 #include "llvm/CodeGen/MachineFrameInfo.h"
  22 #include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h"
  23 #include "llvm/CodeGen/MachineRegisterInfo.h"
  24 #include "llvm/CodeGen/TargetLowering.h"
  25 #include "llvm/CodeGen/TargetPassConfig.h"
  26 #include "llvm/CodeGen/TargetSubtargetInfo.h"
  27 #include "llvm/Config/config.h"
  28 #include "llvm/IR/Function.h"
  29 #include "llvm/MC/TargetRegistry.h"
  30 #include "llvm/Support/CodeGenCoverage.h"
  31 #include "llvm/Support/CommandLine.h"
  32 #include "llvm/Support/Debug.h"
  33 #include "llvm/Target/TargetMachine.h"
  34
  35 #define DEBUG_TYPE "instruction-select"
  36
  37 using namespace llvm;
  38
  39 #ifdef LLVM_GISEL_COV_PREFIX
  40 static cl::opt<std::string>
  41     CoveragePrefix("gisel-coverage-prefix", cl::init(LLVM_GISEL_COV_PREFIX),
  42                    cl::desc("Record GlobalISel rule coverage files of this "
  43                             "prefix if instrumentation was generated"));
  44 #else
  45 static const std::string CoveragePrefix;
  46 #endif
  47
  48 char InstructionSelect::ID = 0;
  49 INITIALIZE_PASS_BEGIN(InstructionSelect, DEBUG_TYPE,
  50                       "Select target instructions out of generic instructions",
  51                       false, false)
  52 INITIALIZE_PASS_DEPENDENCY(TargetPassConfig)
  53 INITIALIZE_PASS_DEPENDENCY(GISelKnownBitsAnalysis)
  54 INITIALIZE_PASS_DEPENDENCY(ProfileSummaryInfoWrapperPass)
  55 INITIALIZE_PASS_DEPENDENCY(LazyBlockFrequencyInfoPass)
  56 INITIALIZE_PASS_END(InstructionSelect, DEBUG_TYPE,
  57                     "Select target instructions out of generic instructions",
  58                     false, false)
  59
  60 InstructionSelect::InstructionSelect(CodeGenOpt::Level OL)
  61     : MachineFunctionPass(ID), OptLevel(OL) {}
  62
  63 // In order not to crash when calling getAnalysis during testing with -run-pass
  64 // we use the default opt level here instead of None, so that the addRequired()
  65 // calls are made in getAnalysisUsage().
  66 InstructionSelect::InstructionSelect()
  67     : MachineFunctionPass(ID), OptLevel(CodeGenOpt::Default) {}
  68
  69 void InstructionSelect::getAnalysisUsage(AnalysisUsage &AU) const {
  70   AU.addRequired<TargetPassConfig>();
  71   AU.addRequired<GISelKnownBitsAnalysis>();
  72   AU.addPreserved<GISelKnownBitsAnalysis>();
  73
  74   if (OptLevel != CodeGenOpt::None) {
  75     AU.addRequired<ProfileSummaryInfoWrapperPass>();
  76     LazyBlockFrequencyInfoPass::getLazyBFIAnalysisUsage(AU);
  77   }
  78   getSelectionDAGFallbackAnalysisUsage(AU);
  79   MachineFunctionPass::getAnalysisUsage(AU);
  80 }
  81
  82 bool InstructionSelect::runOnMachineFunction(MachineFunction &MF) {
  83   // If the ISel pipeline failed, do not bother running that pass.
  84   if (MF.getProperties().hasProperty(
  85           MachineFunctionProperties::Property::FailedISel))
  86     return false;
  87
  88   LLVM_DEBUG(dbgs() << "Selecting function: " << MF.getName() << '\n');
  89
  90   const TargetPassConfig &TPC = getAnalysis<TargetPassConfig>();
  91   InstructionSelector *ISel = MF.getSubtarget().getInstructionSelector();
  92
  93   CodeGenOpt::Level OldOptLevel = OptLevel;
  94   auto RestoreOptLevel = make_scope_exit([=]() { OptLevel = OldOptLevel; });
  95   OptLevel = MF.getFunction().hasOptNone() ? CodeGenOpt::None
  96                                            : MF.getTarget().getOptLevel();
  97
  98   GISelKnownBits *KB = &getAnalysis<GISelKnownBitsAnalysis>().get(MF);
  99   if (OptLevel != CodeGenOpt::None) {
 100     PSI = &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI();
 101     if (PSI && PSI->hasProfileSummary())
 102       BFI = &getAnalysis<LazyBlockFrequencyInfoPass>().getBFI();
 103   }
 104
 105   CodeGenCoverage CoverageInfo;
 106   assert(ISel && "Cannot work without InstructionSelector");
 107   ISel->setupMF(MF, KB, CoverageInfo, PSI, BFI);
 108
 109   // An optimization remark emitter. Used to report failures.
 110   MachineOptimizationRemarkEmitter MORE(MF, /*MBFI=*/nullptr);
 111
 112   // FIXME: There are many other MF/MFI fields we need to initialize.
 113
 114   MachineRegisterInfo &MRI = MF.getRegInfo();
 115 #ifndef NDEBUG
 116   // Check that our input is fully legal: we require the function to have the
 117   // Legalized property, so it should be.
 118   // FIXME: This should be in the MachineVerifier, as the RegBankSelected
 119   // property check already is.
 120   if (!DisableGISelLegalityCheck)
 121     if (const MachineInstr *MI = machineFunctionIsIllegal(MF)) {
 122       reportGISelFailure(MF, TPC, MORE, "gisel-select",
 123                          "instruction is not legal", *MI);
 124       return false;
 125     }
 126   // FIXME: We could introduce new blocks and will need to fix the outer loop.
 127   // Until then, keep track of the number of blocks to assert that we don't.
 128   const size_t NumBlocks = MF.size();
 129 #endif
 130   // Keep track of selected blocks, so we can delete unreachable ones later.
 131   DenseSet<MachineBasicBlock *> SelectedBlocks;
 132
 133   for (MachineBasicBlock *MBB : post_order(&MF)) {
 134     ISel->CurMBB = MBB;
 135     SelectedBlocks.insert(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.eraseFromParent();
 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     if (!SelectedBlocks.contains(&MBB)) {
 209       // This is an unreachable block and therefore hasn't been selected, since
 210       // the main selection loop above uses a postorder block traversal.
 211       // We delete all the instructions in this block since it's unreachable.
 212       MBB.clear();
 213       // Don't delete the block in case the block has it's address taken or is
 214       // still being referenced by a phi somewhere.
 215       continue;
 216     }
 217     // Try to find redundant copies b/w vregs of the same register class.
 218     bool ReachedBegin = false;
 219     for (auto MII = std::prev(MBB.end()), Begin = MBB.begin(); !ReachedBegin;) {
 220       // Select this instruction.
 221       MachineInstr &MI = *MII;
 222
 223       // And have our iterator point to the next instruction, if there is one.
 224       if (MII == Begin)
 225         ReachedBegin = true;
 226       else
 227         --MII;
 228       if (MI.getOpcode() != TargetOpcode::COPY)
 229         continue;
 230       Register SrcReg = MI.getOperand(1).getReg();
 231       Register DstReg = MI.getOperand(0).getReg();
 232       if (Register::isVirtualRegister(SrcReg) &&
 233           Register::isVirtualRegister(DstReg)) {
 234         auto SrcRC = MRI.getRegClass(SrcReg);
 235         auto DstRC = MRI.getRegClass(DstReg);
 236         if (SrcRC == DstRC) {
 237           MRI.replaceRegWith(DstReg, SrcReg);
 238           MI.eraseFromParent();
 239         }
 240       }
 241     }
 242   }
 243
 244 #ifndef NDEBUG
 245   const TargetRegisterInfo &TRI = *MF.getSubtarget().getRegisterInfo();
 246   // Now that selection is complete, there are no more generic vregs.  Verify
 247   // that the size of the now-constrained vreg is unchanged and that it has a
 248   // register class.
 249   for (unsigned I = 0, E = MRI.getNumVirtRegs(); I != E; ++I) {
 250     unsigned VReg = Register::index2VirtReg(I);
 251
 252     MachineInstr *MI = nullptr;
 253     if (!MRI.def_empty(VReg))
 254       MI = &*MRI.def_instr_begin(VReg);
 255     else if (!MRI.use_empty(VReg)) {
 256       MI = &*MRI.use_instr_begin(VReg);
 257       // Debug value instruction is permitted to use undefined vregs.
 258       if (MI->isDebugValue())
 259         continue;
 260     }
 261     if (!MI)
 262       continue;
 263
 264     const TargetRegisterClass *RC = MRI.getRegClassOrNull(VReg);
 265     if (!RC) {
 266       reportGISelFailure(MF, TPC, MORE, "gisel-select",
 267                          "VReg has no regclass after selection", *MI);
 268       return false;
 269     }
 270
 271     const LLT Ty = MRI.getType(VReg);
 272     if (Ty.isValid() && Ty.getSizeInBits() > TRI.getRegSizeInBits(*RC)) {
 273       reportGISelFailure(
 274           MF, TPC, MORE, "gisel-select",
 275           "VReg's low-level type and register class have different sizes", *MI);
 276       return false;
 277     }
 278   }
 279
 280   if (MF.size() != NumBlocks) {
 281     MachineOptimizationRemarkMissed R("gisel-select", "GISelFailure",
 282                                       MF.getFunction().getSubprogram(),
 283                                       /*MBB=*/nullptr);
 284     R << "inserting blocks is not supported yet";
 285     reportGISelFailure(MF, TPC, MORE, R);
 286     return false;
 287   }
 288 #endif
 289   // Determine if there are any calls in this machine function. Ported from
 290   // SelectionDAG.
 291   MachineFrameInfo &MFI = MF.getFrameInfo();
 292   for (const auto &MBB : MF) {
 293     if (MFI.hasCalls() && MF.hasInlineAsm())
 294       break;
 295
 296     for (const auto &MI : MBB) {
 297       if ((MI.isCall() && !MI.isReturn()) || MI.isStackAligningInlineAsm())
 298         MFI.setHasCalls(true);
 299       if (MI.isInlineAsm())
 300         MF.setHasInlineAsm(true);
 301     }
 302   }
 303
 304   // FIXME: FinalizeISel pass calls finalizeLowering, so it's called twice.
 305   auto &TLI = *MF.getSubtarget().getTargetLowering();
 306   TLI.finalizeLowering(MF);
 307
 308   LLVM_DEBUG({
 309     dbgs() << "Rules covered by selecting function: " << MF.getName() << ":";
 310     for (auto RuleID : CoverageInfo.covered())
 311       dbgs() << " id" << RuleID;
 312     dbgs() << "\n\n";
 313   });
 314   CoverageInfo.emit(CoveragePrefix,
 315                     TLI.getTargetMachine().getTarget().getBackendName());
 316
 317   // If we successfully selected the function nothing is going to use the vreg
 318   // types after us (otherwise MIRPrinter would need them). Make sure the types
 319   // disappear.
 320   MRI.clearVirtRegTypes();
 321
 322   // FIXME: Should we accurately track changes?
 323   return true;
 324 }