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/GISelWorkList.h"
  20 #include "llvm/CodeGen/GlobalISel/LegalizationArtifactCombiner.h"
  21 #include "llvm/CodeGen/GlobalISel/LegalizerHelper.h"
  22 #include "llvm/CodeGen/GlobalISel/Utils.h"
  23 #include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h"
  24 #include "llvm/CodeGen/MachineRegisterInfo.h"
  25 #include "llvm/CodeGen/TargetPassConfig.h"
  26 #include "llvm/CodeGen/TargetSubtargetInfo.h"
  27 #include "llvm/Support/Debug.h"
  28
  29 #include <iterator>
  30
  31 #define DEBUG_TYPE "legalizer"
  32
  33 using namespace llvm;
  34
  35 char Legalizer::ID = 0;
  36 INITIALIZE_PASS_BEGIN(Legalizer, DEBUG_TYPE,
  37                       "Legalize the Machine IR a function's Machine IR", false,
  38                       false)
  39 INITIALIZE_PASS_DEPENDENCY(TargetPassConfig)
  40 INITIALIZE_PASS_END(Legalizer, DEBUG_TYPE,
  41                     "Legalize the Machine IR a function's Machine IR", false,
  42                     false)
  43
  44 Legalizer::Legalizer() : MachineFunctionPass(ID) {
  45   initializeLegalizerPass(*PassRegistry::getPassRegistry());
  46 }
  47
  48 void Legalizer::getAnalysisUsage(AnalysisUsage &AU) const {
  49   AU.addRequired<TargetPassConfig>();
  50   getSelectionDAGFallbackAnalysisUsage(AU);
  51   MachineFunctionPass::getAnalysisUsage(AU);
  52 }
  53
  54 void Legalizer::init(MachineFunction &MF) {
  55 }
  56
  57 static bool isArtifact(const MachineInstr &MI) {
  58   switch (MI.getOpcode()) {
  59   default:
  60     return false;
  61   case TargetOpcode::G_TRUNC:
  62   case TargetOpcode::G_ZEXT:
  63   case TargetOpcode::G_ANYEXT:
  64   case TargetOpcode::G_SEXT:
  65   case TargetOpcode::G_MERGE_VALUES:
  66   case TargetOpcode::G_UNMERGE_VALUES:
  67     return true;
  68   }
  69 }
  70
  71 bool Legalizer::runOnMachineFunction(MachineFunction &MF) {
  72   // If the ISel pipeline failed, do not bother running that pass.
  73   if (MF.getProperties().hasProperty(
  74           MachineFunctionProperties::Property::FailedISel))
  75     return false;
  76   LLVM_DEBUG(dbgs() << "Legalize Machine IR for: " << MF.getName() << '\n');
  77   init(MF);
  78   const TargetPassConfig &TPC = getAnalysis<TargetPassConfig>();
  79   MachineOptimizationRemarkEmitter MORE(MF, /*MBFI=*/nullptr);
  80   LegalizerHelper Helper(MF);
  81
  82   const size_t NumBlocks = MF.size();
  83   MachineRegisterInfo &MRI = MF.getRegInfo();
  84
  85   // Populate Insts
  86   GISelWorkList<256> InstList;
  87   GISelWorkList<128> ArtifactList;
  88   ReversePostOrderTraversal<MachineFunction *> RPOT(&MF);
  89   // Perform legalization bottom up so we can DCE as we legalize.
  90   // Traverse BB in RPOT and within each basic block, add insts top down,
  91   // so when we pop_back_val in the legalization process, we traverse bottom-up.
  92   for (auto *MBB : RPOT) {
  93     if (MBB->empty())
  94       continue;
  95     for (MachineInstr &MI : *MBB) {
  96       // Only legalize pre-isel generic instructions: others don't have types
  97       // and are assumed to be legal.
  98       if (!isPreISelGenericOpcode(MI.getOpcode()))
  99         continue;
 100       if (isArtifact(MI))
 101         ArtifactList.insert(&MI);
 102       else
 103         InstList.insert(&MI);
 104     }
 105   }
 106   Helper.MIRBuilder.recordInsertions([&](MachineInstr *MI) {
 107     // Only legalize pre-isel generic instructions.
 108     // Legalization process could generate Target specific pseudo
 109     // instructions with generic types. Don't record them
 110     if (isPreISelGenericOpcode(MI->getOpcode())) {
 111       if (isArtifact(*MI))
 112         ArtifactList.insert(MI);
 113       else
 114         InstList.insert(MI);
 115     }
 116     LLVM_DEBUG(dbgs() << ".. .. New MI: " << *MI;);
 117   });
 118   const LegalizerInfo &LInfo(Helper.getLegalizerInfo());
 119   LegalizationArtifactCombiner ArtCombiner(Helper.MIRBuilder, MF.getRegInfo(), LInfo);
 120   auto RemoveDeadInstFromLists = [&InstList,
 121                                   &ArtifactList](MachineInstr *DeadMI) {
 122     InstList.remove(DeadMI);
 123     ArtifactList.remove(DeadMI);
 124   };
 125   bool Changed = false;
 126   do {
 127     while (!InstList.empty()) {
 128       MachineInstr &MI = *InstList.pop_back_val();
 129       assert(isPreISelGenericOpcode(MI.getOpcode()) && "Expecting generic opcode");
 130       if (isTriviallyDead(MI, MRI)) {
 131         LLVM_DEBUG(dbgs() << MI << "Is dead; erasing.\n");
 132         MI.eraseFromParentAndMarkDBGValuesForRemoval();
 133         continue;
 134       }
 135
 136       // Do the legalization for this instruction.
 137       auto Res = Helper.legalizeInstrStep(MI);
 138       // Error out if we couldn't legalize this instruction. We may want to
 139       // fall back to DAG ISel instead in the future.
 140       if (Res == LegalizerHelper::UnableToLegalize) {
 141         Helper.MIRBuilder.stopRecordingInsertions();
 142         reportGISelFailure(MF, TPC, MORE, "gisel-legalize",
 143                            "unable to legalize instruction", MI);
 144         return false;
 145       }
 146       Changed |= Res == LegalizerHelper::Legalized;
 147     }
 148     while (!ArtifactList.empty()) {
 149       MachineInstr &MI = *ArtifactList.pop_back_val();
 150       assert(isPreISelGenericOpcode(MI.getOpcode()) && "Expecting generic opcode");
 151       if (isTriviallyDead(MI, MRI)) {
 152         LLVM_DEBUG(dbgs() << MI << "Is dead; erasing.\n");
 153         RemoveDeadInstFromLists(&MI);
 154         MI.eraseFromParentAndMarkDBGValuesForRemoval();
 155         continue;
 156       }
 157       SmallVector<MachineInstr *, 4> DeadInstructions;
 158       if (ArtCombiner.tryCombineInstruction(MI, DeadInstructions)) {
 159         for (auto *DeadMI : DeadInstructions) {
 160           LLVM_DEBUG(dbgs() << ".. Erasing Dead Instruction " << *DeadMI);
 161           RemoveDeadInstFromLists(DeadMI);
 162           DeadMI->eraseFromParentAndMarkDBGValuesForRemoval();
 163         }
 164         Changed = true;
 165         continue;
 166       }
 167       // If this was not an artifact (that could be combined away), this might
 168       // need special handling. Add it to InstList, so when it's processed
 169       // there, it has to be legal or specially handled.
 170       else
 171         InstList.insert(&MI);
 172     }
 173   } while (!InstList.empty());
 174
 175   // For now don't support if new blocks are inserted - we would need to fix the
 176   // outerloop for that.
 177   if (MF.size() != NumBlocks) {
 178     MachineOptimizationRemarkMissed R("gisel-legalize", "GISelFailure",
 179                                       MF.getFunction().getSubprogram(),
 180                                       /*MBB=*/nullptr);
 181     R << "inserting blocks is not supported yet";
 182     reportGISelFailure(MF, TPC, MORE, R);
 183     return false;
 184   }
 185
 186   return Changed;
 187 }