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