contrib/llvm/lib/CodeGen/GlobalISel/Legalizer.cpp

   1 //===-- llvm/CodeGen/GlobalISel/Legalizer.cpp -----------------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 /// \file This file implements the LegalizerHelper class to legalize individual
  11 /// instructions and the LegalizePass wrapper pass for the primary
  12 /// legalization.
  13 //
  14 //===----------------------------------------------------------------------===//
  15
  16 #include "llvm/CodeGen/GlobalISel/Legalizer.h"
  17 #include "llvm/ADT/PostOrderIterator.h"
  18 #include "llvm/ADT/SetVector.h"
  19 #include "llvm/CodeGen/GlobalISel/CSEInfo.h"
  20 #include "llvm/CodeGen/GlobalISel/CSEMIRBuilder.h"
  21 #include "llvm/CodeGen/GlobalISel/GISelChangeObserver.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/Utils.h"
  26 #include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h"
  27 #include "llvm/CodeGen/MachineRegisterInfo.h"
  28 #include "llvm/CodeGen/TargetPassConfig.h"
  29 #include "llvm/CodeGen/TargetSubtargetInfo.h"
  30 #include "llvm/Support/Debug.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     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.insert(&MI);
 159       else
 160         InstList.insert(&MI);
 161     }
 162   }
 163   std::unique_ptr<MachineIRBuilder> MIRBuilder;
 164   GISelCSEInfo *CSEInfo = nullptr;
 165   bool IsO0 = TPC.getOptLevel() == CodeGenOpt::Level::None;
 166   // Disable CSE for O0.
 167   bool EnableCSE = !IsO0 && EnableCSEInLegalizer;
 168   if (EnableCSE) {
 169     MIRBuilder = make_unique<CSEMIRBuilder>();
 170     std::unique_ptr<CSEConfig> Config = make_unique<CSEConfig>();
 171     CSEInfo = &Wrapper.get(std::move(Config));
 172     MIRBuilder->setCSEInfo(CSEInfo);
 173   } else
 174     MIRBuilder = make_unique<MachineIRBuilder>();
 175   // This observer keeps the worklist updated.
 176   LegalizerWorkListManager WorkListObserver(InstList, ArtifactList);
 177   // We want both WorkListObserver as well as CSEInfo to observe all changes.
 178   // Use the wrapper observer.
 179   GISelObserverWrapper WrapperObserver(&WorkListObserver);
 180   if (EnableCSE && CSEInfo)
 181     WrapperObserver.addObserver(CSEInfo);
 182   // Now install the observer as the delegate to MF.
 183   // This will keep all the observers notified about new insertions/deletions.
 184   RAIIDelegateInstaller DelInstall(MF, &WrapperObserver);
 185   LegalizerHelper Helper(MF, WrapperObserver, *MIRBuilder.get());
 186   const LegalizerInfo &LInfo(Helper.getLegalizerInfo());
 187   LegalizationArtifactCombiner ArtCombiner(*MIRBuilder.get(), MF.getRegInfo(),
 188                                            LInfo);
 189   auto RemoveDeadInstFromLists = [&WrapperObserver](MachineInstr *DeadMI) {
 190     WrapperObserver.erasingInstr(*DeadMI);
 191   };
 192   bool Changed = false;
 193   do {
 194     while (!InstList.empty()) {
 195       MachineInstr &MI = *InstList.pop_back_val();
 196       assert(isPreISelGenericOpcode(MI.getOpcode()) && "Expecting generic opcode");
 197       if (isTriviallyDead(MI, MRI)) {
 198         LLVM_DEBUG(dbgs() << MI << "Is dead; erasing.\n");
 199         MI.eraseFromParentAndMarkDBGValuesForRemoval();
 200         continue;
 201       }
 202
 203       // Do the legalization for this instruction.
 204       auto Res = Helper.legalizeInstrStep(MI);
 205       // Error out if we couldn't legalize this instruction. We may want to
 206       // fall back to DAG ISel instead in the future.
 207       if (Res == LegalizerHelper::UnableToLegalize) {
 208         Helper.MIRBuilder.stopObservingChanges();
 209         reportGISelFailure(MF, TPC, MORE, "gisel-legalize",
 210                            "unable to legalize instruction", MI);
 211         return false;
 212       }
 213       Changed |= Res == LegalizerHelper::Legalized;
 214     }
 215     while (!ArtifactList.empty()) {
 216       MachineInstr &MI = *ArtifactList.pop_back_val();
 217       assert(isPreISelGenericOpcode(MI.getOpcode()) && "Expecting generic opcode");
 218       if (isTriviallyDead(MI, MRI)) {
 219         LLVM_DEBUG(dbgs() << MI << "Is dead\n");
 220         RemoveDeadInstFromLists(&MI);
 221         MI.eraseFromParentAndMarkDBGValuesForRemoval();
 222         continue;
 223       }
 224       SmallVector<MachineInstr *, 4> DeadInstructions;
 225       if (ArtCombiner.tryCombineInstruction(MI, DeadInstructions)) {
 226         for (auto *DeadMI : DeadInstructions) {
 227           LLVM_DEBUG(dbgs() << *DeadMI << "Is dead\n");
 228           RemoveDeadInstFromLists(DeadMI);
 229           DeadMI->eraseFromParentAndMarkDBGValuesForRemoval();
 230         }
 231         Changed = true;
 232         continue;
 233       }
 234       // If this was not an artifact (that could be combined away), this might
 235       // need special handling. Add it to InstList, so when it's processed
 236       // there, it has to be legal or specially handled.
 237       else
 238         InstList.insert(&MI);
 239     }
 240   } while (!InstList.empty());
 241
 242   // For now don't support if new blocks are inserted - we would need to fix the
 243   // outerloop for that.
 244   if (MF.size() != NumBlocks) {
 245     MachineOptimizationRemarkMissed R("gisel-legalize", "GISelFailure",
 246                                       MF.getFunction().getSubprogram(),
 247                                       /*MBB=*/nullptr);
 248     R << "inserting blocks is not supported yet";
 249     reportGISelFailure(MF, TPC, MORE, R);
 250     return false;
 251   }
 252
 253   return Changed;
 254 }