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