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