llvm/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/Analysis/OptimizationRemarkEmitter.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/GISelKnownBits.h"
  22 #include "llvm/CodeGen/GlobalISel/GISelWorkList.h"
  23 #include "llvm/CodeGen/GlobalISel/LegalizationArtifactCombiner.h"
  24 #include "llvm/CodeGen/GlobalISel/LegalizerHelper.h"
  25 #include "llvm/CodeGen/GlobalISel/LostDebugLocObserver.h"
  26 #include "llvm/CodeGen/GlobalISel/Utils.h"
  27 #include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h"
  28 #include "llvm/CodeGen/TargetPassConfig.h"
  29 #include "llvm/CodeGen/TargetSubtargetInfo.h"
  30 #include "llvm/InitializePasses.h"
  31 #include "llvm/Support/Debug.h"
  32 #include "llvm/Support/Error.h"
  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 // This is a temporary hack, should be removed soon.
  44 static cl::opt<bool> AllowGInsertAsArtifact(
  45     "allow-ginsert-as-artifact",
  46     cl::desc("Allow G_INSERT to be considered an artifact. Hack around AMDGPU "
  47              "test infinite loops."),
  48     cl::Optional, cl::init(true));
  49
  50 enum class DebugLocVerifyLevel {
  51   None,
  52   Legalizations,
  53   LegalizationsAndArtifactCombiners,
  54 };
  55 #ifndef NDEBUG
  56 static cl::opt<DebugLocVerifyLevel> VerifyDebugLocs(
  57     "verify-legalizer-debug-locs",
  58     cl::desc("Verify that debug locations are handled"),
  59     cl::values(
  60         clEnumValN(DebugLocVerifyLevel::None, "none", "No verification"),
  61         clEnumValN(DebugLocVerifyLevel::Legalizations, "legalizations",
  62                    "Verify legalizations"),
  63         clEnumValN(DebugLocVerifyLevel::LegalizationsAndArtifactCombiners,
  64                    "legalizations+artifactcombiners",
  65                    "Verify legalizations and artifact combines")),
  66     cl::init(DebugLocVerifyLevel::Legalizations));
  67 #else
  68 // Always disable it for release builds by preventing the observer from being
  69 // installed.
  70 static const DebugLocVerifyLevel VerifyDebugLocs = DebugLocVerifyLevel::None;
  71 #endif
  72
  73 char Legalizer::ID = 0;
  74 INITIALIZE_PASS_BEGIN(Legalizer, DEBUG_TYPE,
  75                       "Legalize the Machine IR a function's Machine IR", false,
  76                       false)
  77 INITIALIZE_PASS_DEPENDENCY(TargetPassConfig)
  78 INITIALIZE_PASS_DEPENDENCY(GISelCSEAnalysisWrapperPass)
  79 INITIALIZE_PASS_DEPENDENCY(GISelKnownBitsAnalysis)
  80 INITIALIZE_PASS_END(Legalizer, DEBUG_TYPE,
  81                     "Legalize the Machine IR a function's Machine IR", false,
  82                     false)
  83
  84 Legalizer::Legalizer() : MachineFunctionPass(ID) { }
  85
  86 void Legalizer::getAnalysisUsage(AnalysisUsage &AU) const {
  87   AU.addRequired<TargetPassConfig>();
  88   AU.addRequired<GISelCSEAnalysisWrapperPass>();
  89   AU.addPreserved<GISelCSEAnalysisWrapperPass>();
  90   AU.addRequired<GISelKnownBitsAnalysis>();
  91   AU.addPreserved<GISelKnownBitsAnalysis>();
  92   getSelectionDAGFallbackAnalysisUsage(AU);
  93   MachineFunctionPass::getAnalysisUsage(AU);
  94 }
  95
  96 void Legalizer::init(MachineFunction &MF) {
  97 }
  98
  99 static bool isArtifact(const MachineInstr &MI) {
 100   switch (MI.getOpcode()) {
 101   default:
 102     return false;
 103   case TargetOpcode::G_TRUNC:
 104   case TargetOpcode::G_ZEXT:
 105   case TargetOpcode::G_ANYEXT:
 106   case TargetOpcode::G_SEXT:
 107   case TargetOpcode::G_MERGE_VALUES:
 108   case TargetOpcode::G_UNMERGE_VALUES:
 109   case TargetOpcode::G_CONCAT_VECTORS:
 110   case TargetOpcode::G_BUILD_VECTOR:
 111   case TargetOpcode::G_EXTRACT:
 112     return true;
 113   case TargetOpcode::G_INSERT:
 114     return AllowGInsertAsArtifact;
 115   }
 116 }
 117 using InstListTy = GISelWorkList<256>;
 118 using ArtifactListTy = GISelWorkList<128>;
 119
 120 namespace {
 121 class LegalizerWorkListManager : public GISelChangeObserver {
 122   InstListTy &InstList;
 123   ArtifactListTy &ArtifactList;
 124 #ifndef NDEBUG
 125   SmallVector<MachineInstr *, 4> NewMIs;
 126 #endif
 127
 128 public:
 129   LegalizerWorkListManager(InstListTy &Insts, ArtifactListTy &Arts)
 130       : InstList(Insts), ArtifactList(Arts) {}
 131
 132   void createdOrChangedInstr(MachineInstr &MI) {
 133     // Only legalize pre-isel generic instructions.
 134     // Legalization process could generate Target specific pseudo
 135     // instructions with generic types. Don't record them
 136     if (isPreISelGenericOpcode(MI.getOpcode())) {
 137       if (isArtifact(MI))
 138         ArtifactList.insert(&MI);
 139       else
 140         InstList.insert(&MI);
 141     }
 142   }
 143
 144   void createdInstr(MachineInstr &MI) override {
 145     LLVM_DEBUG(NewMIs.push_back(&MI));
 146     createdOrChangedInstr(MI);
 147   }
 148
 149   void printNewInstrs() {
 150     LLVM_DEBUG({
 151       for (const auto *MI : NewMIs)
 152         dbgs() << ".. .. New MI: " << *MI;
 153       NewMIs.clear();
 154     });
 155   }
 156
 157   void erasingInstr(MachineInstr &MI) override {
 158     LLVM_DEBUG(dbgs() << ".. .. Erasing: " << MI);
 159     InstList.remove(&MI);
 160     ArtifactList.remove(&MI);
 161   }
 162
 163   void changingInstr(MachineInstr &MI) override {
 164     LLVM_DEBUG(dbgs() << ".. .. Changing MI: " << MI);
 165   }
 166
 167   void changedInstr(MachineInstr &MI) override {
 168     // When insts change, we want to revisit them to legalize them again.
 169     // We'll consider them the same as created.
 170     LLVM_DEBUG(dbgs() << ".. .. Changed MI: " << MI);
 171     createdOrChangedInstr(MI);
 172   }
 173 };
 174 } // namespace
 175
 176 Legalizer::MFResult
 177 Legalizer::legalizeMachineFunction(MachineFunction &MF, const LegalizerInfo &LI,
 178                                    ArrayRef<GISelChangeObserver *> AuxObservers,
 179                                    LostDebugLocObserver &LocObserver,
 180                                    MachineIRBuilder &MIRBuilder,
 181                                    GISelKnownBits *KB) {
 182   MIRBuilder.setMF(MF);
 183   MachineRegisterInfo &MRI = MF.getRegInfo();
 184
 185   // Populate worklists.
 186   InstListTy InstList;
 187   ArtifactListTy ArtifactList;
 188   ReversePostOrderTraversal<MachineFunction *> RPOT(&MF);
 189   // Perform legalization bottom up so we can DCE as we legalize.
 190   // Traverse BB in RPOT and within each basic block, add insts top down,
 191   // so when we pop_back_val in the legalization process, we traverse bottom-up.
 192   for (auto *MBB : RPOT) {
 193     if (MBB->empty())
 194       continue;
 195     for (MachineInstr &MI : *MBB) {
 196       // Only legalize pre-isel generic instructions: others don't have types
 197       // and are assumed to be legal.
 198       if (!isPreISelGenericOpcode(MI.getOpcode()))
 199         continue;
 200       if (isArtifact(MI))
 201         ArtifactList.deferred_insert(&MI);
 202       else
 203         InstList.deferred_insert(&MI);
 204     }
 205   }
 206   ArtifactList.finalize();
 207   InstList.finalize();
 208
 209   // This observer keeps the worklists updated.
 210   LegalizerWorkListManager WorkListObserver(InstList, ArtifactList);
 211   // We want both WorkListObserver as well as all the auxiliary observers (e.g.
 212   // CSEInfo) to observe all changes. Use the wrapper observer.
 213   GISelObserverWrapper WrapperObserver(&WorkListObserver);
 214   for (GISelChangeObserver *Observer : AuxObservers)
 215     WrapperObserver.addObserver(Observer);
 216
 217   // Now install the observer as the delegate to MF.
 218   // This will keep all the observers notified about new insertions/deletions.
 219   RAIIMFObsDelInstaller Installer(MF, WrapperObserver);
 220   LegalizerHelper Helper(MF, LI, WrapperObserver, MIRBuilder, KB);
 221   LegalizationArtifactCombiner ArtCombiner(MIRBuilder, MRI, LI, KB);
 222   bool Changed = false;
 223   SmallVector<MachineInstr *, 128> RetryList;
 224   do {
 225     LLVM_DEBUG(dbgs() << "=== New Iteration ===\n");
 226     assert(RetryList.empty() && "Expected no instructions in RetryList");
 227     unsigned NumArtifacts = ArtifactList.size();
 228     while (!InstList.empty()) {
 229       MachineInstr &MI = *InstList.pop_back_val();
 230       assert(isPreISelGenericOpcode(MI.getOpcode()) &&
 231              "Expecting generic opcode");
 232       if (isTriviallyDead(MI, MRI)) {
 233         salvageDebugInfo(MRI, MI);
 234         eraseInstr(MI, MRI, &LocObserver);
 235         continue;
 236       }
 237
 238       // Do the legalization for this instruction.
 239       auto Res = Helper.legalizeInstrStep(MI, LocObserver);
 240       // Error out if we couldn't legalize this instruction. We may want to
 241       // fall back to DAG ISel instead in the future.
 242       if (Res == LegalizerHelper::UnableToLegalize) {
 243         // Move illegal artifacts to RetryList instead of aborting because
 244         // legalizing InstList may generate artifacts that allow
 245         // ArtifactCombiner to combine away them.
 246         if (isArtifact(MI)) {
 247           LLVM_DEBUG(dbgs() << ".. Not legalized, moving to artifacts retry\n");
 248           assert(NumArtifacts == 0 &&
 249                  "Artifacts are only expected in instruction list starting the "
 250                  "second iteration, but each iteration starting second must "
 251                  "start with an empty artifacts list");
 252           (void)NumArtifacts;
 253           RetryList.push_back(&MI);
 254           continue;
 255         }
 256         Helper.MIRBuilder.stopObservingChanges();
 257         return {Changed, &MI};
 258       }
 259       WorkListObserver.printNewInstrs();
 260       LocObserver.checkpoint();
 261       Changed |= Res == LegalizerHelper::Legalized;
 262     }
 263     // Try to combine the instructions in RetryList again if there
 264     // are new artifacts. If not, stop legalizing.
 265     if (!RetryList.empty()) {
 266       if (!ArtifactList.empty()) {
 267         while (!RetryList.empty())
 268           ArtifactList.insert(RetryList.pop_back_val());
 269       } else {
 270         LLVM_DEBUG(dbgs() << "No new artifacts created, not retrying!\n");
 271         Helper.MIRBuilder.stopObservingChanges();
 272         return {Changed, RetryList.front()};
 273       }
 274     }
 275     LocObserver.checkpoint();
 276     while (!ArtifactList.empty()) {
 277       MachineInstr &MI = *ArtifactList.pop_back_val();
 278       assert(isPreISelGenericOpcode(MI.getOpcode()) &&
 279              "Expecting generic opcode");
 280       if (isTriviallyDead(MI, MRI)) {
 281         salvageDebugInfo(MRI, MI);
 282         eraseInstr(MI, MRI, &LocObserver);
 283         continue;
 284       }
 285       SmallVector<MachineInstr *, 4> DeadInstructions;
 286       LLVM_DEBUG(dbgs() << "Trying to combine: " << MI);
 287       if (ArtCombiner.tryCombineInstruction(MI, DeadInstructions,
 288                                             WrapperObserver)) {
 289         WorkListObserver.printNewInstrs();
 290         eraseInstrs(DeadInstructions, MRI, &LocObserver);
 291         LocObserver.checkpoint(
 292             VerifyDebugLocs ==
 293             DebugLocVerifyLevel::LegalizationsAndArtifactCombiners);
 294         Changed = true;
 295         continue;
 296       }
 297       // If this was not an artifact (that could be combined away), this might
 298       // need special handling. Add it to InstList, so when it's processed
 299       // there, it has to be legal or specially handled.
 300       else {
 301         LLVM_DEBUG(dbgs() << ".. Not combined, moving to instructions list\n");
 302         InstList.insert(&MI);
 303       }
 304     }
 305   } while (!InstList.empty());
 306
 307   return {Changed, /*FailedOn*/ nullptr};
 308 }
 309
 310 bool Legalizer::runOnMachineFunction(MachineFunction &MF) {
 311   // If the ISel pipeline failed, do not bother running that pass.
 312   if (MF.getProperties().hasProperty(
 313           MachineFunctionProperties::Property::FailedISel))
 314     return false;
 315   LLVM_DEBUG(dbgs() << "Legalize Machine IR for: " << MF.getName() << '\n');
 316   init(MF);
 317   const TargetPassConfig &TPC = getAnalysis<TargetPassConfig>();
 318   GISelCSEAnalysisWrapper &Wrapper =
 319       getAnalysis<GISelCSEAnalysisWrapperPass>().getCSEWrapper();
 320   MachineOptimizationRemarkEmitter MORE(MF, /*MBFI=*/nullptr);
 321
 322   std::unique_ptr<MachineIRBuilder> MIRBuilder;
 323   GISelCSEInfo *CSEInfo = nullptr;
 324   bool EnableCSE = EnableCSEInLegalizer.getNumOccurrences()
 325                        ? EnableCSEInLegalizer
 326                        : TPC.isGISelCSEEnabled();
 327   if (EnableCSE) {
 328     MIRBuilder = std::make_unique<CSEMIRBuilder>();
 329     CSEInfo = &Wrapper.get(TPC.getCSEConfig());
 330     MIRBuilder->setCSEInfo(CSEInfo);
 331   } else
 332     MIRBuilder = std::make_unique<MachineIRBuilder>();
 333
 334   SmallVector<GISelChangeObserver *, 1> AuxObservers;
 335   if (EnableCSE && CSEInfo) {
 336     // We want CSEInfo in addition to WorkListObserver to observe all changes.
 337     AuxObservers.push_back(CSEInfo);
 338   }
 339   assert(!CSEInfo || !errorToBool(CSEInfo->verify()));
 340   LostDebugLocObserver LocObserver(DEBUG_TYPE);
 341   if (VerifyDebugLocs > DebugLocVerifyLevel::None)
 342     AuxObservers.push_back(&LocObserver);
 343
 344   // This allows Known Bits Analysis in the legalizer.
 345   GISelKnownBits *KB = &getAnalysis<GISelKnownBitsAnalysis>().get(MF);
 346
 347   const LegalizerInfo &LI = *MF.getSubtarget().getLegalizerInfo();
 348   MFResult Result = legalizeMachineFunction(MF, LI, AuxObservers, LocObserver,
 349                                             *MIRBuilder, KB);
 350
 351   if (Result.FailedOn) {
 352     reportGISelFailure(MF, TPC, MORE, "gisel-legalize",
 353                        "unable to legalize instruction", *Result.FailedOn);
 354     return false;
 355   }
 356
 357   if (LocObserver.getNumLostDebugLocs()) {
 358     MachineOptimizationRemarkMissed R("gisel-legalize", "LostDebugLoc",
 359                                       MF.getFunction().getSubprogram(),
 360                                       /*MBB=*/&*MF.begin());
 361     R << "lost "
 362       << ore::NV("NumLostDebugLocs", LocObserver.getNumLostDebugLocs())
 363       << " debug locations during pass";
 364     reportGISelWarning(MF, TPC, MORE, R);
 365     // Example remark:
 366     // --- !Missed
 367     // Pass:            gisel-legalize
 368     // Name:            GISelFailure
 369     // DebugLoc:        { File: '.../legalize-urem.mir', Line: 1, Column: 0 }
 370     // Function:        test_urem_s32
 371     // Args:
 372     //   - String:          'lost '
 373     //   - NumLostDebugLocs: '1'
 374     //   - String:          ' debug locations during pass'
 375     // ...
 376   }
 377
 378   // If for some reason CSE was not enabled, make sure that we invalidate the
 379   // CSEInfo object (as we currently declare that the analysis is preserved).
 380   // The next time get on the wrapper is called, it will force it to recompute
 381   // the analysis.
 382   if (!EnableCSE)
 383     Wrapper.setComputed(false);
 384   return Result.Changed;
 385 }