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/CodeGen/GlobalISel/LegalizerHelper.h"
  18 #include "llvm/CodeGen/GlobalISel/Legalizer.h"
  19 #include "llvm/CodeGen/GlobalISel/Utils.h"
  20 #include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h"
  21 #include "llvm/CodeGen/MachineRegisterInfo.h"
  22 #include "llvm/CodeGen/TargetPassConfig.h"
  23 #include "llvm/Support/Debug.h"
  24 #include "llvm/Target/TargetInstrInfo.h"
  25 #include "llvm/Target/TargetSubtargetInfo.h"
  26
  27 #include <iterator>
  28
  29 #define DEBUG_TYPE "legalizer"
  30
  31 using namespace llvm;
  32
  33 char Legalizer::ID = 0;
  34 INITIALIZE_PASS_BEGIN(Legalizer, DEBUG_TYPE,
  35                       "Legalize the Machine IR a function's Machine IR", false,
  36                       false)
  37 INITIALIZE_PASS_DEPENDENCY(TargetPassConfig)
  38 INITIALIZE_PASS_END(Legalizer, DEBUG_TYPE,
  39                     "Legalize the Machine IR a function's Machine IR", false,
  40                     false)
  41
  42 Legalizer::Legalizer() : MachineFunctionPass(ID) {
  43   initializeLegalizerPass(*PassRegistry::getPassRegistry());
  44 }
  45
  46 void Legalizer::getAnalysisUsage(AnalysisUsage &AU) const {
  47   AU.addRequired<TargetPassConfig>();
  48   MachineFunctionPass::getAnalysisUsage(AU);
  49 }
  50
  51 void Legalizer::init(MachineFunction &MF) {
  52 }
  53
  54 bool Legalizer::combineExtracts(MachineInstr &MI, MachineRegisterInfo &MRI,
  55                                 const TargetInstrInfo &TII) {
  56   bool Changed = false;
  57   if (MI.getOpcode() != TargetOpcode::G_EXTRACT)
  58     return Changed;
  59
  60   unsigned NumDefs = (MI.getNumOperands() - 1) / 2;
  61   unsigned SrcReg = MI.getOperand(NumDefs).getReg();
  62   MachineInstr &SeqI = *MRI.def_instr_begin(SrcReg);
  63   if (SeqI.getOpcode() != TargetOpcode::G_SEQUENCE)
  64       return Changed;
  65
  66   unsigned NumSeqSrcs = (SeqI.getNumOperands() - 1) / 2;
  67   bool AllDefsReplaced = true;
  68
  69   // Try to match each register extracted with a corresponding insertion formed
  70   // by the G_SEQUENCE.
  71   for (unsigned Idx = 0, SeqIdx = 0; Idx < NumDefs; ++Idx) {
  72     MachineOperand &ExtractMO = MI.getOperand(Idx);
  73     assert(ExtractMO.isReg() && ExtractMO.isDef() &&
  74            "unexpected extract operand");
  75
  76     unsigned ExtractReg = ExtractMO.getReg();
  77     unsigned ExtractPos = MI.getOperand(NumDefs + Idx + 1).getImm();
  78
  79     while (SeqIdx < NumSeqSrcs &&
  80            SeqI.getOperand(2 * SeqIdx + 2).getImm() < ExtractPos)
  81       ++SeqIdx;
  82
  83     if (SeqIdx == NumSeqSrcs) {
  84       AllDefsReplaced = false;
  85       continue;
  86     }
  87
  88     unsigned OrigReg = SeqI.getOperand(2 * SeqIdx + 1).getReg();
  89     if (SeqI.getOperand(2 * SeqIdx + 2).getImm() != ExtractPos ||
  90         MRI.getType(OrigReg) != MRI.getType(ExtractReg)) {
  91       AllDefsReplaced = false;
  92       continue;
  93     }
  94
  95     assert(!TargetRegisterInfo::isPhysicalRegister(OrigReg) &&
  96            "unexpected physical register in G_SEQUENCE");
  97
  98     // Finally we can replace the uses.
  99     MRI.replaceRegWith(ExtractReg, OrigReg);
 100   }
 101
 102   if (AllDefsReplaced) {
 103     // If SeqI was the next instruction in the BB and we removed it, we'd break
 104     // the outer iteration.
 105     assert(std::next(MachineBasicBlock::iterator(MI)) != SeqI &&
 106            "G_SEQUENCE does not dominate G_EXTRACT");
 107
 108     MI.eraseFromParent();
 109
 110     if (MRI.use_empty(SrcReg))
 111       SeqI.eraseFromParent();
 112     Changed = true;
 113   }
 114
 115   return Changed;
 116 }
 117
 118 bool Legalizer::combineMerges(MachineInstr &MI, MachineRegisterInfo &MRI,
 119                               const TargetInstrInfo &TII) {
 120   if (MI.getOpcode() != TargetOpcode::G_UNMERGE_VALUES)
 121     return false;
 122
 123   unsigned NumDefs = MI.getNumOperands() - 1;
 124   unsigned SrcReg = MI.getOperand(NumDefs).getReg();
 125   MachineInstr &MergeI = *MRI.def_instr_begin(SrcReg);
 126   if (MergeI.getOpcode() != TargetOpcode::G_MERGE_VALUES)
 127     return false;
 128
 129   if (MergeI.getNumOperands() - 1 != NumDefs)
 130     return false;
 131
 132   // FIXME: is a COPY appropriate if the types mismatch? We know both registers
 133   // are allocatable by now.
 134   if (MRI.getType(MI.getOperand(0).getReg()) !=
 135       MRI.getType(MergeI.getOperand(1).getReg()))
 136     return false;
 137
 138   for (unsigned Idx = 0; Idx < NumDefs; ++Idx)
 139     MRI.replaceRegWith(MI.getOperand(Idx).getReg(),
 140                        MergeI.getOperand(Idx + 1).getReg());
 141
 142   MI.eraseFromParent();
 143   if (MRI.use_empty(MergeI.getOperand(0).getReg()))
 144     MergeI.eraseFromParent();
 145   return true;
 146 }
 147
 148 bool Legalizer::runOnMachineFunction(MachineFunction &MF) {
 149   // If the ISel pipeline failed, do not bother running that pass.
 150   if (MF.getProperties().hasProperty(
 151           MachineFunctionProperties::Property::FailedISel))
 152     return false;
 153   DEBUG(dbgs() << "Legalize Machine IR for: " << MF.getName() << '\n');
 154   init(MF);
 155   const TargetPassConfig &TPC = getAnalysis<TargetPassConfig>();
 156   MachineOptimizationRemarkEmitter MORE(MF, /*MBFI=*/nullptr);
 157   LegalizerHelper Helper(MF);
 158
 159   // FIXME: an instruction may need more than one pass before it is legal. For
 160   // example on most architectures <3 x i3> is doubly-illegal. It would
 161   // typically proceed along a path like: <3 x i3> -> <3 x i8> -> <8 x i8>. We
 162   // probably want a worklist of instructions rather than naive iterate until
 163   // convergence for performance reasons.
 164   bool Changed = false;
 165   MachineBasicBlock::iterator NextMI;
 166   for (auto &MBB : MF) {
 167     for (auto MI = MBB.begin(); MI != MBB.end(); MI = NextMI) {
 168       // Get the next Instruction before we try to legalize, because there's a
 169       // good chance MI will be deleted.
 170       NextMI = std::next(MI);
 171
 172       // Only legalize pre-isel generic instructions: others don't have types
 173       // and are assumed to be legal.
 174       if (!isPreISelGenericOpcode(MI->getOpcode()))
 175         continue;
 176       unsigned NumNewInsns = 0;
 177       SmallVector<MachineInstr *, 4> WorkList;
 178       Helper.MIRBuilder.recordInsertions([&](MachineInstr *MI) {
 179         ++NumNewInsns;
 180         WorkList.push_back(MI);
 181       });
 182       WorkList.push_back(&*MI);
 183
 184       bool Changed = false;
 185       LegalizerHelper::LegalizeResult Res;
 186       unsigned Idx = 0;
 187       do {
 188         Res = Helper.legalizeInstrStep(*WorkList[Idx]);
 189         // Error out if we couldn't legalize this instruction. We may want to
 190         // fall back to DAG ISel instead in the future.
 191         if (Res == LegalizerHelper::UnableToLegalize) {
 192           Helper.MIRBuilder.stopRecordingInsertions();
 193           if (Res == LegalizerHelper::UnableToLegalize) {
 194             reportGISelFailure(MF, TPC, MORE, "gisel-legalize",
 195                                "unable to legalize instruction",
 196                                *WorkList[Idx]);
 197             return false;
 198           }
 199         }
 200         Changed |= Res == LegalizerHelper::Legalized;
 201         ++Idx;
 202
 203 #ifndef NDEBUG
 204         if (NumNewInsns) {
 205           DEBUG(dbgs() << ".. .. Emitted " << NumNewInsns << " insns\n");
 206           for (auto I = WorkList.end() - NumNewInsns, E = WorkList.end();
 207                I != E; ++I)
 208             DEBUG(dbgs() << ".. .. New MI: "; (*I)->print(dbgs()));
 209           NumNewInsns = 0;
 210         }
 211 #endif
 212       } while (Idx < WorkList.size());
 213
 214       Helper.MIRBuilder.stopRecordingInsertions();
 215     }
 216   }
 217
 218   MachineRegisterInfo &MRI = MF.getRegInfo();
 219   const TargetInstrInfo &TII = *MF.getSubtarget().getInstrInfo();
 220   for (auto &MBB : MF) {
 221     for (auto MI = MBB.begin(); MI != MBB.end(); MI = NextMI) {
 222       // Get the next Instruction before we try to legalize, because there's a
 223       // good chance MI will be deleted.
 224       NextMI = std::next(MI);
 225
 226       // combineExtracts erases MI.
 227       if (combineExtracts(*MI, MRI, TII)) {
 228         Changed = true;
 229         continue;
 230       }
 231       Changed |= combineMerges(*MI, MRI, TII);
 232     }
 233   }
 234
 235   return Changed;
 236 }