lib/CodeGen/GlobalISel/Legalizer.cpp

   1 //===-- llvm/CodeGen/GlobalISel/Legalizer.cpp -----------------------------===//
   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 //
   9 /// \file This file implements the LegalizerHelper class to legalize individual
  10 /// instructions and the LegalizePass wrapper pass for the primary
  11 /// legalization.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "llvm/CodeGen/GlobalISel/Legalizer.h"
  16 #include "llvm/ADT/PostOrderIterator.h"
  17 #include "llvm/ADT/SetVector.h"
  18 #include "llvm/CodeGen/GlobalISel/CSEInfo.h"
  19 #include "llvm/CodeGen/GlobalISel/CSEMIRBuilder.h"
  20 #include "llvm/CodeGen/GlobalISel/GISelChangeObserver.h"
  21 #include "llvm/CodeGen/GlobalISel/GISelWorkList.h"
  22 #include "llvm/CodeGen/GlobalISel/LegalizationArtifactCombiner.h"
  23 #include "llvm/CodeGen/GlobalISel/LegalizerHelper.h"
  24 #include "llvm/CodeGen/GlobalISel/Utils.h"
  25 #include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h"
  26 #include "llvm/CodeGen/MachineRegisterInfo.h"
  27 #include "llvm/CodeGen/TargetPassConfig.h"
  28 #include "llvm/CodeGen/TargetSubtargetInfo.h"
  29 #include "llvm/Support/Debug.h"
  30 #include "llvm/Target/TargetMachine.h"
  31
  32 #include <iterator>
  33
  34 #define DEBUG_TYPE "legalizer"
  35
  36 using namespace llvm;
  37
  38 static cl::opt<bool>
  39     EnableCSEInLegalizer("enable-cse-in-legalizer",
  40                          cl::desc("Should enable CSE in Legalizer"),
  41                          cl::Optional, cl::init(false));
  42
  43 char Legalizer::ID = 0;
  44 INITIALIZE_PASS_BEGIN(Legalizer, DEBUG_TYPE,
  45                       "Legalize the Machine IR a function's Machine IR", false,
  46                       false)
  47 INITIALIZE_PASS_DEPENDENCY(TargetPassConfig)
  48 INITIALIZE_PASS_DEPENDENCY(GISelCSEAnalysisWrapperPass)
  49 INITIALIZE_PASS_END(Legalizer, DEBUG_TYPE,
  50                     "Legalize the Machine IR a function's Machine IR", false,
  51                     false)
  52
  53 Legalizer::Legalizer() : MachineFunctionPass(ID) {
  54   initializeLegalizerPass(*PassRegistry::getPassRegistry());
  55 }
  56
  57 void Legalizer::getAnalysisUsage(AnalysisUsage &AU) const {
  58   AU.addRequired<TargetPassConfig>();
  59   AU.addRequired<GISelCSEAnalysisWrapperPass>();
  60   AU.addPreserved<GISelCSEAnalysisWrapperPass>();
  61   getSelectionDAGFallbackAnalysisUsage(AU);
  62   MachineFunctionPass::getAnalysisUsage(AU);
  63 }
  64
  65 void Legalizer::init(MachineFunction &MF) {
  66 }
  67
  68 static bool isArtifact(const MachineInstr &MI) {
  69   switch (MI.getOpcode()) {
  70   default:
  71     return false;
  72   case TargetOpcode::G_TRUNC:
  73   case TargetOpcode::G_ZEXT:
  74   case TargetOpcode::G_ANYEXT:
  75   case TargetOpcode::G_SEXT:
  76   case TargetOpcode::G_MERGE_VALUES:
  77   case TargetOpcode::G_UNMERGE_VALUES:
  78   case TargetOpcode::G_CONCAT_VECTORS:
  79   case TargetOpcode::G_BUILD_VECTOR:
  80   case TargetOpcode::G_EXTRACT:
  81     return true;
  82   }
  83 }
  84 using InstListTy = GISelWorkList<256>;
  85 using ArtifactListTy = GISelWorkList<128>;
  86
  87 namespace {
  88 class LegalizerWorkListManager : public GISelChangeObserver {
  89   InstListTy &InstList;
  90   ArtifactListTy &ArtifactList;
  91 #ifndef NDEBUG
  92   SmallVector<MachineInstr *, 4> NewMIs;
  93 #endif
  94
  95 public:
  96   LegalizerWorkListManager(InstListTy &Insts, ArtifactListTy &Arts)
  97       : InstList(Insts), ArtifactList(Arts) {}
  98
  99   void createdOrChangedInstr(MachineInstr &MI) {
 100     // Only legalize pre-isel generic instructions.
 101     // Legalization process could generate Target specific pseudo
 102     // instructions with generic types. Don't record them
 103     if (isPreISelGenericOpcode(MI.getOpcode())) {
 104       if (isArtifact(MI))
 105         ArtifactList.insert(&MI);
 106       else
 107         InstList.insert(&MI);
 108     }
 109   }
 110
 111   void createdInstr(MachineInstr &MI) override {
 112     LLVM_DEBUG(dbgs() << ".. .. New MI: " << MI);
 113     LLVM_DEBUG(NewMIs.push_back(&MI));
 114     createdOrChangedInstr(MI);
 115   }
 116
 117   void printNewInstrs() {
 118     LLVM_DEBUG({
 119       for (const auto *MI : NewMIs)
 120         dbgs() << ".. .. New MI: " << *MI;
 121       NewMIs.clear();
 122     });
 123   }
 124
 125   void erasingInstr(MachineInstr &MI) override {
 126     LLVM_DEBUG(dbgs() << ".. .. Erasing: " << MI);
 127     InstList.remove(&MI);
 128     ArtifactList.remove(&MI);
 129   }
 130
 131   void changingInstr(MachineInstr &MI) override {
 132     LLVM_DEBUG(dbgs() << ".. .. Changing MI: " << MI);
 133   }
 134
 135   void changedInstr(MachineInstr &MI) override {
 136     // When insts change, we want to revisit them to legalize them again.
 137     // We'll consider them the same as created.
 138     LLVM_DEBUG(dbgs() << ".. .. Changed MI: " << MI);
 139     createdOrChangedInstr(MI);
 140   }
 141 };
 142 } // namespace
 143
 144 bool Legalizer::runOnMachineFunction(MachineFunction &MF) {
 145   // If the ISel pipeline failed, do not bother running that pass.
 146   if (MF.getProperties().hasProperty(
 147           MachineFunctionProperties::Property::FailedISel))
 148     return false;
 149   LLVM_DEBUG(dbgs() << "Legalize Machine IR for: " << MF.getName() << '\n');
 150   init(MF);
 151   const TargetPassConfig &TPC = getAnalysis<TargetPassConfig>();
 152   GISelCSEAnalysisWrapper &Wrapper =
 153       getAnalysis<GISelCSEAnalysisWrapperPass>().getCSEWrapper();
 154   MachineOptimizationRemarkEmitter MORE(MF, /*MBFI=*/nullptr);
 155
 156   const size_t NumBlocks = MF.size();
 157   MachineRegisterInfo &MRI = MF.getRegInfo();
 158
 159   // Populate Insts
 160   InstListTy InstList;
 161   ArtifactListTy ArtifactList;
 162   ReversePostOrderTraversal<MachineFunction *> RPOT(&MF);
 163   // Perform legalization bottom up so we can DCE as we legalize.
 164   // Traverse BB in RPOT and within each basic block, add insts top down,
 165   // so when we pop_back_val in the legalization process, we traverse bottom-up.
 166   for (auto *MBB : RPOT) {
 167     if (MBB->empty())
 168       continue;
 169     for (MachineInstr &MI : *MBB) {
 170       // Only legalize pre-isel generic instructions: others don't have types
 171       // and are assumed to be legal.
 172       if (!isPreISelGenericOpcode(MI.getOpcode()))
 173         continue;
 174       if (isArtifact(MI))
 175         ArtifactList.deferred_insert(&MI);
 176       else
 177         InstList.deferred_insert(&MI);
 178     }
 179   }
 180   ArtifactList.finalize();
 181   InstList.finalize();
 182   std::unique_ptr<MachineIRBuilder> MIRBuilder;
 183   GISelCSEInfo *CSEInfo = nullptr;
 184   bool EnableCSE = EnableCSEInLegalizer.getNumOccurrences()
 185                        ? EnableCSEInLegalizer
 186                        : TPC.isGISelCSEEnabled();
 187
 188   if (EnableCSE) {
 189     MIRBuilder = make_unique<CSEMIRBuilder>();
 190     CSEInfo = &Wrapper.get(TPC.getCSEConfig());
 191     MIRBuilder->setCSEInfo(CSEInfo);
 192   } else
 193     MIRBuilder = make_unique<MachineIRBuilder>();
 194   // This observer keeps the worklist updated.
 195   LegalizerWorkListManager WorkListObserver(InstList, ArtifactList);
 196   // We want both WorkListObserver as well as CSEInfo to observe all changes.
 197   // Use the wrapper observer.
 198   GISelObserverWrapper WrapperObserver(&WorkListObserver);
 199   if (EnableCSE && CSEInfo)
 200     WrapperObserver.addObserver(CSEInfo);
 201   // Now install the observer as the delegate to MF.
 202   // This will keep all the observers notified about new insertions/deletions.
 203   RAIIDelegateInstaller DelInstall(MF, &WrapperObserver);
 204   LegalizerHelper Helper(MF, WrapperObserver, *MIRBuilder.get());
 205   const LegalizerInfo &LInfo(Helper.getLegalizerInfo());
 206   LegalizationArtifactCombiner ArtCombiner(*MIRBuilder.get(), MF.getRegInfo(),
 207                                            LInfo);
 208   auto RemoveDeadInstFromLists = [&WrapperObserver](MachineInstr *DeadMI) {
 209     WrapperObserver.erasingInstr(*DeadMI);
 210   };
 211   bool Changed = false;
 212   do {
 213     while (!InstList.empty()) {
 214       MachineInstr &MI = *InstList.pop_back_val();
 215       assert(isPreISelGenericOpcode(MI.getOpcode()) && "Expecting generic opcode");
 216       if (isTriviallyDead(MI, MRI)) {
 217         LLVM_DEBUG(dbgs() << MI << "Is dead; erasing.\n");
 218         MI.eraseFromParentAndMarkDBGValuesForRemoval();
 219         continue;
 220       }
 221
 222       // Do the legalization for this instruction.
 223       auto Res = Helper.legalizeInstrStep(MI);
 224       // Error out if we couldn't legalize this instruction. We may want to
 225       // fall back to DAG ISel instead in the future.
 226       if (Res == LegalizerHelper::UnableToLegalize) {
 227         Helper.MIRBuilder.stopObservingChanges();
 228         reportGISelFailure(MF, TPC, MORE, "gisel-legalize",
 229                            "unable to legalize instruction", MI);
 230         return false;
 231       }
 232       WorkListObserver.printNewInstrs();
 233       Changed |= Res == LegalizerHelper::Legalized;
 234     }
 235     while (!ArtifactList.empty()) {
 236       MachineInstr &MI = *ArtifactList.pop_back_val();
 237       assert(isPreISelGenericOpcode(MI.getOpcode()) && "Expecting generic opcode");
 238       if (isTriviallyDead(MI, MRI)) {
 239         LLVM_DEBUG(dbgs() << MI << "Is dead\n");
 240         RemoveDeadInstFromLists(&MI);
 241         MI.eraseFromParentAndMarkDBGValuesForRemoval();
 242         continue;
 243       }
 244       SmallVector<MachineInstr *, 4> DeadInstructions;
 245       if (ArtCombiner.tryCombineInstruction(MI, DeadInstructions,
 246                                             WrapperObserver)) {
 247         WorkListObserver.printNewInstrs();
 248         for (auto *DeadMI : DeadInstructions) {
 249           LLVM_DEBUG(dbgs() << *DeadMI << "Is dead\n");
 250           RemoveDeadInstFromLists(DeadMI);
 251           DeadMI->eraseFromParentAndMarkDBGValuesForRemoval();
 252         }
 253         Changed = true;
 254         continue;
 255       }
 256       // If this was not an artifact (that could be combined away), this might
 257       // need special handling. Add it to InstList, so when it's processed
 258       // there, it has to be legal or specially handled.
 259       else
 260         InstList.insert(&MI);
 261     }
 262   } while (!InstList.empty());
 263
 264   // For now don't support if new blocks are inserted - we would need to fix the
 265   // outerloop for that.
 266   if (MF.size() != NumBlocks) {
 267     MachineOptimizationRemarkMissed R("gisel-legalize", "GISelFailure",
 268                                       MF.getFunction().getSubprogram(),
 269                                       /*MBB=*/nullptr);
 270     R << "inserting blocks is not supported yet";
 271     reportGISelFailure(MF, TPC, MORE, R);
 272     return false;
 273   }
 274
 275   return Changed;
 276 }