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/SetVector.h"
  16 #include "llvm/Analysis/LazyBlockFrequencyInfo.h"
  17 #include "llvm/Analysis/ProfileSummaryInfo.h"
  18 #include "llvm/CodeGen/GlobalISel/GISelChangeObserver.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/MachineFrameInfo.h"
  24 #include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h"
  25 #include "llvm/CodeGen/MachineRegisterInfo.h"
  26 #include "llvm/CodeGen/TargetLowering.h"
  27 #include "llvm/CodeGen/TargetOpcodes.h"
  28 #include "llvm/CodeGen/TargetPassConfig.h"
  29 #include "llvm/CodeGen/TargetSubtargetInfo.h"
  30 #include "llvm/Config/config.h"
  31 #include "llvm/IR/Function.h"
  32 #include "llvm/MC/TargetRegistry.h"
  33 #include "llvm/Support/CodeGenCoverage.h"
  34 #include "llvm/Support/Debug.h"
  35 #include "llvm/Support/DebugCounter.h"
  36 #include "llvm/Target/TargetMachine.h"
  37
  38 #define DEBUG_TYPE "instruction-select"
  39
  40 using namespace llvm;
  41
  42 DEBUG_COUNTER(GlobalISelCounter, "globalisel",
  43               "Controls whether to select function with GlobalISel");
  44
  45 #ifdef LLVM_GISEL_COV_PREFIX
  46 static cl::opt<std::string>
  47     CoveragePrefix("gisel-coverage-prefix", cl::init(LLVM_GISEL_COV_PREFIX),
  48                    cl::desc("Record GlobalISel rule coverage files of this "
  49                             "prefix if instrumentation was generated"));
  50 #else
  51 static const std::string CoveragePrefix;
  52 #endif
  53
  54 char InstructionSelect::ID = 0;
  55 INITIALIZE_PASS_BEGIN(InstructionSelect, DEBUG_TYPE,
  56                       "Select target instructions out of generic instructions",
  57                       false, false)
  58 INITIALIZE_PASS_DEPENDENCY(TargetPassConfig)
  59 INITIALIZE_PASS_DEPENDENCY(GISelKnownBitsAnalysis)
  60 INITIALIZE_PASS_DEPENDENCY(ProfileSummaryInfoWrapperPass)
  61 INITIALIZE_PASS_DEPENDENCY(LazyBlockFrequencyInfoPass)
  62 INITIALIZE_PASS_END(InstructionSelect, DEBUG_TYPE,
  63                     "Select target instructions out of generic instructions",
  64                     false, false)
  65
  66 InstructionSelect::InstructionSelect(CodeGenOptLevel OL, char &PassID)
  67     : MachineFunctionPass(PassID), OptLevel(OL) {}
  68
  69 /// This class observes instruction insertions/removals.
  70 /// InstructionSelect stores an iterator of the instruction prior to the one
  71 /// that is currently being selected to determine which instruction to select
  72 /// next. Previously this meant that selecting multiple instructions at once was
  73 /// illegal behavior due to potential invalidation of this iterator. This is
  74 /// a non-obvious limitation for selector implementers. Therefore, to allow
  75 /// deletion of arbitrary instructions, we detect this case and continue
  76 /// selection with the predecessor of the deleted instruction.
  77 class InstructionSelect::MIIteratorMaintainer : public GISelChangeObserver {
  78 #ifndef NDEBUG
  79   SmallSetVector<const MachineInstr *, 32> CreatedInstrs;
  80 #endif
  81 public:
  82   MachineBasicBlock::reverse_iterator MII;
  83
  84   void changingInstr(MachineInstr &MI) override {
  85     llvm_unreachable("InstructionSelect does not track changed instructions!");
  86   }
  87   void changedInstr(MachineInstr &MI) override {
  88     llvm_unreachable("InstructionSelect does not track changed instructions!");
  89   }
  90
  91   void createdInstr(MachineInstr &MI) override {
  92     LLVM_DEBUG(dbgs() << "Creating:  " << MI; CreatedInstrs.insert(&MI));
  93   }
  94
  95   void erasingInstr(MachineInstr &MI) override {
  96     LLVM_DEBUG(dbgs() << "Erasing:   " << MI; CreatedInstrs.remove(&MI));
  97     if (MII.getInstrIterator().getNodePtr() == &MI) {
  98       // If the iterator points to the MI that will be erased (i.e. the MI prior
  99       // to the MI that is currently being selected), the iterator would be
 100       // invalidated. Continue selection with its predecessor.
 101       ++MII;
 102       LLVM_DEBUG(dbgs() << "Instruction removal updated iterator.\n");
 103     }
 104   }
 105
 106   void reportFullyCreatedInstrs() {
 107     LLVM_DEBUG({
 108       if (CreatedInstrs.empty()) {
 109         dbgs() << "Created no instructions.\n";
 110       } else {
 111         dbgs() << "Created:\n";
 112         for (const auto *MI : CreatedInstrs) {
 113           dbgs() << "  " << *MI;
 114         }
 115         CreatedInstrs.clear();
 116       }
 117     });
 118   }
 119 };
 120
 121 void InstructionSelect::getAnalysisUsage(AnalysisUsage &AU) const {
 122   AU.addRequired<TargetPassConfig>();
 123   AU.addRequired<GISelKnownBitsAnalysis>();
 124   AU.addPreserved<GISelKnownBitsAnalysis>();
 125
 126   if (OptLevel != CodeGenOptLevel::None) {
 127     AU.addRequired<ProfileSummaryInfoWrapperPass>();
 128     LazyBlockFrequencyInfoPass::getLazyBFIAnalysisUsage(AU);
 129   }
 130   getSelectionDAGFallbackAnalysisUsage(AU);
 131   MachineFunctionPass::getAnalysisUsage(AU);
 132 }
 133
 134 bool InstructionSelect::runOnMachineFunction(MachineFunction &MF) {
 135   // If the ISel pipeline failed, do not bother running that pass.
 136   if (MF.getProperties().hasProperty(
 137           MachineFunctionProperties::Property::FailedISel))
 138     return false;
 139
 140   ISel = MF.getSubtarget().getInstructionSelector();
 141   ISel->TPC = &getAnalysis<TargetPassConfig>();
 142
 143   // FIXME: Properly override OptLevel in TargetMachine. See OptLevelChanger
 144   CodeGenOptLevel OldOptLevel = OptLevel;
 145   auto RestoreOptLevel = make_scope_exit([=]() { OptLevel = OldOptLevel; });
 146   OptLevel = MF.getFunction().hasOptNone() ? CodeGenOptLevel::None
 147                                            : MF.getTarget().getOptLevel();
 148
 149   KB = &getAnalysis<GISelKnownBitsAnalysis>().get(MF);
 150   if (OptLevel != CodeGenOptLevel::None) {
 151     PSI = &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI();
 152     if (PSI && PSI->hasProfileSummary())
 153       BFI = &getAnalysis<LazyBlockFrequencyInfoPass>().getBFI();
 154   }
 155
 156   return selectMachineFunction(MF);
 157 }
 158
 159 bool InstructionSelect::selectMachineFunction(MachineFunction &MF) {
 160   LLVM_DEBUG(dbgs() << "Selecting function: " << MF.getName() << '\n');
 161   assert(ISel && "Cannot work without InstructionSelector");
 162
 163   const TargetPassConfig &TPC = *ISel->TPC;
 164   CodeGenCoverage CoverageInfo;
 165   ISel->setupMF(MF, KB, &CoverageInfo, PSI, BFI);
 166
 167   // An optimization remark emitter. Used to report failures.
 168   MachineOptimizationRemarkEmitter MORE(MF, /*MBFI=*/nullptr);
 169   ISel->MORE = &MORE;
 170
 171   // FIXME: There are many other MF/MFI fields we need to initialize.
 172
 173   MachineRegisterInfo &MRI = MF.getRegInfo();
 174 #ifndef NDEBUG
 175   // Check that our input is fully legal: we require the function to have the
 176   // Legalized property, so it should be.
 177   // FIXME: This should be in the MachineVerifier, as the RegBankSelected
 178   // property check already is.
 179   if (!DisableGISelLegalityCheck)
 180     if (const MachineInstr *MI = machineFunctionIsIllegal(MF)) {
 181       reportGISelFailure(MF, TPC, MORE, "gisel-select",
 182                          "instruction is not legal", *MI);
 183       return false;
 184     }
 185   // FIXME: We could introduce new blocks and will need to fix the outer loop.
 186   // Until then, keep track of the number of blocks to assert that we don't.
 187   const size_t NumBlocks = MF.size();
 188 #endif
 189   // Keep track of selected blocks, so we can delete unreachable ones later.
 190   DenseSet<MachineBasicBlock *> SelectedBlocks;
 191
 192   {
 193     // Observe IR insertions and removals during selection.
 194     // We only install a MachineFunction::Delegate instead of a
 195     // GISelChangeObserver, because we do not want notifications about changed
 196     // instructions. This prevents significant compile-time regressions from
 197     // e.g. constrainOperandRegClass().
 198     GISelObserverWrapper AllObservers;
 199     MIIteratorMaintainer MIIMaintainer;
 200     AllObservers.addObserver(&MIIMaintainer);
 201     RAIIDelegateInstaller DelInstaller(MF, &AllObservers);
 202     ISel->AllObservers = &AllObservers;
 203
 204     for (MachineBasicBlock *MBB : post_order(&MF)) {
 205       ISel->CurMBB = MBB;
 206       SelectedBlocks.insert(MBB);
 207
 208       // Select instructions in reverse block order.
 209       MIIMaintainer.MII = MBB->rbegin();
 210       for (auto End = MBB->rend(); MIIMaintainer.MII != End;) {
 211         MachineInstr &MI = *MIIMaintainer.MII;
 212         // Increment early to skip instructions inserted by select().
 213         ++MIIMaintainer.MII;
 214
 215         LLVM_DEBUG(dbgs() << "\nSelect:  " << MI);
 216         if (!selectInstr(MI)) {
 217           LLVM_DEBUG(dbgs() << "Selection failed!\n";
 218                      MIIMaintainer.reportFullyCreatedInstrs());
 219           reportGISelFailure(MF, TPC, MORE, "gisel-select", "cannot select",
 220                              MI);
 221           return false;
 222         }
 223         LLVM_DEBUG(MIIMaintainer.reportFullyCreatedInstrs());
 224       }
 225     }
 226   }
 227
 228   for (MachineBasicBlock &MBB : MF) {
 229     if (MBB.empty())
 230       continue;
 231
 232     if (!SelectedBlocks.contains(&MBB)) {
 233       // This is an unreachable block and therefore hasn't been selected, since
 234       // the main selection loop above uses a postorder block traversal.
 235       // We delete all the instructions in this block since it's unreachable.
 236       MBB.clear();
 237       // Don't delete the block in case the block has it's address taken or is
 238       // still being referenced by a phi somewhere.
 239       continue;
 240     }
 241     // Try to find redundant copies b/w vregs of the same register class.
 242     for (auto MII = MBB.rbegin(), End = MBB.rend(); MII != End;) {
 243       MachineInstr &MI = *MII;
 244       ++MII;
 245
 246       if (MI.getOpcode() != TargetOpcode::COPY)
 247         continue;
 248       Register SrcReg = MI.getOperand(1).getReg();
 249       Register DstReg = MI.getOperand(0).getReg();
 250       if (SrcReg.isVirtual() && DstReg.isVirtual()) {
 251         auto SrcRC = MRI.getRegClass(SrcReg);
 252         auto DstRC = MRI.getRegClass(DstReg);
 253         if (SrcRC == DstRC) {
 254           MRI.replaceRegWith(DstReg, SrcReg);
 255           MI.eraseFromParent();
 256         }
 257       }
 258     }
 259   }
 260
 261 #ifndef NDEBUG
 262   const TargetRegisterInfo &TRI = *MF.getSubtarget().getRegisterInfo();
 263   // Now that selection is complete, there are no more generic vregs.  Verify
 264   // that the size of the now-constrained vreg is unchanged and that it has a
 265   // register class.
 266   for (unsigned I = 0, E = MRI.getNumVirtRegs(); I != E; ++I) {
 267     Register VReg = Register::index2VirtReg(I);
 268
 269     MachineInstr *MI = nullptr;
 270     if (!MRI.def_empty(VReg))
 271       MI = &*MRI.def_instr_begin(VReg);
 272     else if (!MRI.use_empty(VReg)) {
 273       MI = &*MRI.use_instr_begin(VReg);
 274       // Debug value instruction is permitted to use undefined vregs.
 275       if (MI->isDebugValue())
 276         continue;
 277     }
 278     if (!MI)
 279       continue;
 280
 281     const TargetRegisterClass *RC = MRI.getRegClassOrNull(VReg);
 282     if (!RC) {
 283       reportGISelFailure(MF, TPC, MORE, "gisel-select",
 284                          "VReg has no regclass after selection", *MI);
 285       return false;
 286     }
 287
 288     const LLT Ty = MRI.getType(VReg);
 289     if (Ty.isValid() &&
 290         TypeSize::isKnownGT(Ty.getSizeInBits(), TRI.getRegSizeInBits(*RC))) {
 291       reportGISelFailure(
 292           MF, TPC, MORE, "gisel-select",
 293           "VReg's low-level type and register class have different sizes", *MI);
 294       return false;
 295     }
 296   }
 297
 298   if (MF.size() != NumBlocks) {
 299     MachineOptimizationRemarkMissed R("gisel-select", "GISelFailure",
 300                                       MF.getFunction().getSubprogram(),
 301                                       /*MBB=*/nullptr);
 302     R << "inserting blocks is not supported yet";
 303     reportGISelFailure(MF, TPC, MORE, R);
 304     return false;
 305   }
 306 #endif
 307
 308   if (!DebugCounter::shouldExecute(GlobalISelCounter)) {
 309     dbgs() << "Falling back for function " << MF.getName() << "\n";
 310     MF.getProperties().set(MachineFunctionProperties::Property::FailedISel);
 311     return false;
 312   }
 313
 314   // Determine if there are any calls in this machine function. Ported from
 315   // SelectionDAG.
 316   MachineFrameInfo &MFI = MF.getFrameInfo();
 317   for (const auto &MBB : MF) {
 318     if (MFI.hasCalls() && MF.hasInlineAsm())
 319       break;
 320
 321     for (const auto &MI : MBB) {
 322       if ((MI.isCall() && !MI.isReturn()) || MI.isStackAligningInlineAsm())
 323         MFI.setHasCalls(true);
 324       if (MI.isInlineAsm())
 325         MF.setHasInlineAsm(true);
 326     }
 327   }
 328
 329   // FIXME: FinalizeISel pass calls finalizeLowering, so it's called twice.
 330   auto &TLI = *MF.getSubtarget().getTargetLowering();
 331   TLI.finalizeLowering(MF);
 332
 333   LLVM_DEBUG({
 334     dbgs() << "Rules covered by selecting function: " << MF.getName() << ":";
 335     for (auto RuleID : CoverageInfo.covered())
 336       dbgs() << " id" << RuleID;
 337     dbgs() << "\n\n";
 338   });
 339   CoverageInfo.emit(CoveragePrefix,
 340                     TLI.getTargetMachine().getTarget().getBackendName());
 341
 342   // If we successfully selected the function nothing is going to use the vreg
 343   // types after us (otherwise MIRPrinter would need them). Make sure the types
 344   // disappear.
 345   MRI.clearVirtRegTypes();
 346
 347   // FIXME: Should we accurately track changes?
 348   return true;
 349 }
 350
 351 bool InstructionSelect::selectInstr(MachineInstr &MI) {
 352   MachineRegisterInfo &MRI = ISel->MF->getRegInfo();
 353
 354   // We could have folded this instruction away already, making it dead.
 355   // If so, erase it.
 356   if (isTriviallyDead(MI, MRI)) {
 357     LLVM_DEBUG(dbgs() << "Is dead.\n");
 358     salvageDebugInfo(MRI, MI);
 359     MI.eraseFromParent();
 360     return true;
 361   }
 362
 363   // Eliminate hints or G_CONSTANT_FOLD_BARRIER.
 364   if (isPreISelGenericOptimizationHint(MI.getOpcode()) ||
 365       MI.getOpcode() == TargetOpcode::G_CONSTANT_FOLD_BARRIER) {
 366     auto [DstReg, SrcReg] = MI.getFirst2Regs();
 367
 368     // At this point, the destination register class of the op may have
 369     // been decided.
 370     //
 371     // Propagate that through to the source register.
 372     const TargetRegisterClass *DstRC = MRI.getRegClassOrNull(DstReg);
 373     if (DstRC)
 374       MRI.setRegClass(SrcReg, DstRC);
 375     assert(canReplaceReg(DstReg, SrcReg, MRI) &&
 376            "Must be able to replace dst with src!");
 377     MI.eraseFromParent();
 378     MRI.replaceRegWith(DstReg, SrcReg);
 379     return true;
 380   }
 381
 382   if (MI.getOpcode() == TargetOpcode::G_INVOKE_REGION_START) {
 383     MI.eraseFromParent();
 384     return true;
 385   }
 386
 387   return ISel->select(MI);
 388 }