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