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