contrib/llvm/include/llvm/CodeGen/GlobalISel/LegalizationArtifactCombiner.h

   1 //===-- llvm/CodeGen/GlobalISel/LegalizationArtifactCombiner.h -----*- C++ -*-//
   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 // This file contains some helper functions which try to cleanup artifacts
  10 // such as G_TRUNCs/G_[ZSA]EXTENDS that were created during legalization to make
  11 // the types match. This file also contains some combines of merges that happens
  12 // at the end of the legalization.
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "llvm/CodeGen/GlobalISel/Legalizer.h"
  16 #include "llvm/CodeGen/GlobalISel/LegalizerInfo.h"
  17 #include "llvm/CodeGen/GlobalISel/MIPatternMatch.h"
  18 #include "llvm/CodeGen/GlobalISel/MachineIRBuilder.h"
  19 #include "llvm/CodeGen/GlobalISel/Utils.h"
  20 #include "llvm/CodeGen/MachineRegisterInfo.h"
  21 #include "llvm/Support/Debug.h"
  22
  23 #define DEBUG_TYPE "legalizer"
  24 using namespace llvm::MIPatternMatch;
  25
  26 namespace llvm {
  27 class LegalizationArtifactCombiner {
  28   MachineIRBuilder &Builder;
  29   MachineRegisterInfo &MRI;
  30   const LegalizerInfo &LI;
  31
  32 public:
  33   LegalizationArtifactCombiner(MachineIRBuilder &B, MachineRegisterInfo &MRI,
  34                     const LegalizerInfo &LI)
  35       : Builder(B), MRI(MRI), LI(LI) {}
  36
  37   bool tryCombineAnyExt(MachineInstr &MI,
  38                         SmallVectorImpl<MachineInstr *> &DeadInsts) {
  39     if (MI.getOpcode() != TargetOpcode::G_ANYEXT)
  40       return false;
  41
  42     Builder.setInstr(MI);
  43     unsigned DstReg = MI.getOperand(0).getReg();
  44     unsigned SrcReg = lookThroughCopyInstrs(MI.getOperand(1).getReg());
  45
  46     // aext(trunc x) - > aext/copy/trunc x
  47     unsigned TruncSrc;
  48     if (mi_match(SrcReg, MRI, m_GTrunc(m_Reg(TruncSrc)))) {
  49       LLVM_DEBUG(dbgs() << ".. Combine MI: " << MI;);
  50       Builder.buildAnyExtOrTrunc(DstReg, TruncSrc);
  51       markInstAndDefDead(MI, *MRI.getVRegDef(SrcReg), DeadInsts);
  52       return true;
  53     }
  54
  55     // aext([asz]ext x) -> [asz]ext x
  56     unsigned ExtSrc;
  57     MachineInstr *ExtMI;
  58     if (mi_match(SrcReg, MRI,
  59                  m_all_of(m_MInstr(ExtMI), m_any_of(m_GAnyExt(m_Reg(ExtSrc)),
  60                                                     m_GSExt(m_Reg(ExtSrc)),
  61                                                     m_GZExt(m_Reg(ExtSrc)))))) {
  62       Builder.buildInstr(ExtMI->getOpcode(), {DstReg}, {ExtSrc});
  63       markInstAndDefDead(MI, *ExtMI, DeadInsts);
  64       return true;
  65     }
  66     return tryFoldImplicitDef(MI, DeadInsts);
  67   }
  68
  69   bool tryCombineZExt(MachineInstr &MI,
  70                       SmallVectorImpl<MachineInstr *> &DeadInsts) {
  71
  72     if (MI.getOpcode() != TargetOpcode::G_ZEXT)
  73       return false;
  74
  75     Builder.setInstr(MI);
  76     unsigned DstReg = MI.getOperand(0).getReg();
  77     unsigned SrcReg = lookThroughCopyInstrs(MI.getOperand(1).getReg());
  78
  79     // zext(trunc x) - > and (aext/copy/trunc x), mask
  80     unsigned TruncSrc;
  81     if (mi_match(SrcReg, MRI, m_GTrunc(m_Reg(TruncSrc)))) {
  82       LLT DstTy = MRI.getType(DstReg);
  83       if (isInstUnsupported({TargetOpcode::G_AND, {DstTy}}) ||
  84           isInstUnsupported({TargetOpcode::G_CONSTANT, {DstTy}}))
  85         return false;
  86       LLVM_DEBUG(dbgs() << ".. Combine MI: " << MI;);
  87       LLT SrcTy = MRI.getType(SrcReg);
  88       APInt Mask = APInt::getAllOnesValue(SrcTy.getSizeInBits());
  89       auto MIBMask = Builder.buildConstant(DstTy, Mask.getZExtValue());
  90       Builder.buildAnd(DstReg, Builder.buildAnyExtOrTrunc(DstTy, TruncSrc),
  91                        MIBMask);
  92       markInstAndDefDead(MI, *MRI.getVRegDef(SrcReg), DeadInsts);
  93       return true;
  94     }
  95     return tryFoldImplicitDef(MI, DeadInsts);
  96   }
  97
  98   bool tryCombineSExt(MachineInstr &MI,
  99                       SmallVectorImpl<MachineInstr *> &DeadInsts) {
 100
 101     if (MI.getOpcode() != TargetOpcode::G_SEXT)
 102       return false;
 103
 104     Builder.setInstr(MI);
 105     unsigned DstReg = MI.getOperand(0).getReg();
 106     unsigned SrcReg = lookThroughCopyInstrs(MI.getOperand(1).getReg());
 107
 108     // sext(trunc x) - > ashr (shl (aext/copy/trunc x), c), c
 109     unsigned TruncSrc;
 110     if (mi_match(SrcReg, MRI, m_GTrunc(m_Reg(TruncSrc)))) {
 111       LLT DstTy = MRI.getType(DstReg);
 112       if (isInstUnsupported({TargetOpcode::G_SHL, {DstTy}}) ||
 113           isInstUnsupported({TargetOpcode::G_ASHR, {DstTy}}) ||
 114           isInstUnsupported({TargetOpcode::G_CONSTANT, {DstTy}}))
 115         return false;
 116       LLVM_DEBUG(dbgs() << ".. Combine MI: " << MI;);
 117       LLT SrcTy = MRI.getType(SrcReg);
 118       unsigned ShAmt = DstTy.getSizeInBits() - SrcTy.getSizeInBits();
 119       auto MIBShAmt = Builder.buildConstant(DstTy, ShAmt);
 120       auto MIBShl = Builder.buildInstr(
 121           TargetOpcode::G_SHL, {DstTy},
 122           {Builder.buildAnyExtOrTrunc(DstTy, TruncSrc), MIBShAmt});
 123       Builder.buildInstr(TargetOpcode::G_ASHR, {DstReg}, {MIBShl, MIBShAmt});
 124       markInstAndDefDead(MI, *MRI.getVRegDef(SrcReg), DeadInsts);
 125       return true;
 126     }
 127     return tryFoldImplicitDef(MI, DeadInsts);
 128   }
 129
 130   /// Try to fold G_[ASZ]EXT (G_IMPLICIT_DEF).
 131   bool tryFoldImplicitDef(MachineInstr &MI,
 132                           SmallVectorImpl<MachineInstr *> &DeadInsts) {
 133     unsigned Opcode = MI.getOpcode();
 134     if (Opcode != TargetOpcode::G_ANYEXT && Opcode != TargetOpcode::G_ZEXT &&
 135         Opcode != TargetOpcode::G_SEXT)
 136       return false;
 137
 138     if (MachineInstr *DefMI = getOpcodeDef(TargetOpcode::G_IMPLICIT_DEF,
 139                                            MI.getOperand(1).getReg(), MRI)) {
 140       Builder.setInstr(MI);
 141       unsigned DstReg = MI.getOperand(0).getReg();
 142       LLT DstTy = MRI.getType(DstReg);
 143
 144       if (Opcode == TargetOpcode::G_ANYEXT) {
 145         // G_ANYEXT (G_IMPLICIT_DEF) -> G_IMPLICIT_DEF
 146         if (isInstUnsupported({TargetOpcode::G_IMPLICIT_DEF, {DstTy}}))
 147           return false;
 148         LLVM_DEBUG(dbgs() << ".. Combine G_ANYEXT(G_IMPLICIT_DEF): " << MI;);
 149         Builder.buildInstr(TargetOpcode::G_IMPLICIT_DEF, {DstReg}, {});
 150       } else {
 151         // G_[SZ]EXT (G_IMPLICIT_DEF) -> G_CONSTANT 0 because the top
 152         // bits will be 0 for G_ZEXT and 0/1 for the G_SEXT.
 153         if (isInstUnsupported({TargetOpcode::G_CONSTANT, {DstTy}}))
 154           return false;
 155         LLVM_DEBUG(dbgs() << ".. Combine G_[SZ]EXT(G_IMPLICIT_DEF): " << MI;);
 156         Builder.buildConstant(DstReg, 0);
 157       }
 158
 159       markInstAndDefDead(MI, *DefMI, DeadInsts);
 160       return true;
 161     }
 162     return false;
 163   }
 164
 165   bool tryCombineMerges(MachineInstr &MI,
 166                         SmallVectorImpl<MachineInstr *> &DeadInsts) {
 167
 168     if (MI.getOpcode() != TargetOpcode::G_UNMERGE_VALUES)
 169       return false;
 170
 171     unsigned NumDefs = MI.getNumOperands() - 1;
 172
 173     unsigned MergingOpcode;
 174     LLT OpTy = MRI.getType(MI.getOperand(NumDefs).getReg());
 175     LLT DestTy = MRI.getType(MI.getOperand(0).getReg());
 176     if (OpTy.isVector() && DestTy.isVector())
 177       MergingOpcode = TargetOpcode::G_CONCAT_VECTORS;
 178     else if (OpTy.isVector() && !DestTy.isVector())
 179       MergingOpcode = TargetOpcode::G_BUILD_VECTOR;
 180     else
 181       MergingOpcode = TargetOpcode::G_MERGE_VALUES;
 182
 183     MachineInstr *MergeI =
 184         getOpcodeDef(MergingOpcode, MI.getOperand(NumDefs).getReg(), MRI);
 185
 186     if (!MergeI)
 187       return false;
 188
 189     const unsigned NumMergeRegs = MergeI->getNumOperands() - 1;
 190
 191     if (NumMergeRegs < NumDefs) {
 192       if (NumDefs % NumMergeRegs != 0)
 193         return false;
 194
 195       Builder.setInstr(MI);
 196       // Transform to UNMERGEs, for example
 197       //   %1 = G_MERGE_VALUES %4, %5
 198       //   %9, %10, %11, %12 = G_UNMERGE_VALUES %1
 199       // to
 200       //   %9, %10 = G_UNMERGE_VALUES %4
 201       //   %11, %12 = G_UNMERGE_VALUES %5
 202
 203       const unsigned NewNumDefs = NumDefs / NumMergeRegs;
 204       for (unsigned Idx = 0; Idx < NumMergeRegs; ++Idx) {
 205         SmallVector<unsigned, 2> DstRegs;
 206         for (unsigned j = 0, DefIdx = Idx * NewNumDefs; j < NewNumDefs;
 207              ++j, ++DefIdx)
 208           DstRegs.push_back(MI.getOperand(DefIdx).getReg());
 209
 210         Builder.buildUnmerge(DstRegs, MergeI->getOperand(Idx + 1).getReg());
 211       }
 212
 213     } else if (NumMergeRegs > NumDefs) {
 214       if (NumMergeRegs % NumDefs != 0)
 215         return false;
 216
 217       Builder.setInstr(MI);
 218       // Transform to MERGEs
 219       //   %6 = G_MERGE_VALUES %17, %18, %19, %20
 220       //   %7, %8 = G_UNMERGE_VALUES %6
 221       // to
 222       //   %7 = G_MERGE_VALUES %17, %18
 223       //   %8 = G_MERGE_VALUES %19, %20
 224
 225       const unsigned NumRegs = NumMergeRegs / NumDefs;
 226       for (unsigned DefIdx = 0; DefIdx < NumDefs; ++DefIdx) {
 227         SmallVector<unsigned, 2> Regs;
 228         for (unsigned j = 0, Idx = NumRegs * DefIdx + 1; j < NumRegs;
 229              ++j, ++Idx)
 230           Regs.push_back(MergeI->getOperand(Idx).getReg());
 231
 232         Builder.buildMerge(MI.getOperand(DefIdx).getReg(), Regs);
 233       }
 234
 235     } else {
 236       // FIXME: is a COPY appropriate if the types mismatch? We know both
 237       // registers are allocatable by now.
 238       if (MRI.getType(MI.getOperand(0).getReg()) !=
 239           MRI.getType(MergeI->getOperand(1).getReg()))
 240         return false;
 241
 242       for (unsigned Idx = 0; Idx < NumDefs; ++Idx)
 243         MRI.replaceRegWith(MI.getOperand(Idx).getReg(),
 244                            MergeI->getOperand(Idx + 1).getReg());
 245     }
 246
 247     markInstAndDefDead(MI, *MergeI, DeadInsts);
 248     return true;
 249   }
 250
 251   /// Try to combine away MI.
 252   /// Returns true if it combined away the MI.
 253   /// Adds instructions that are dead as a result of the combine
 254   /// into DeadInsts, which can include MI.
 255   bool tryCombineInstruction(MachineInstr &MI,
 256                              SmallVectorImpl<MachineInstr *> &DeadInsts) {
 257     switch (MI.getOpcode()) {
 258     default:
 259       return false;
 260     case TargetOpcode::G_ANYEXT:
 261       return tryCombineAnyExt(MI, DeadInsts);
 262     case TargetOpcode::G_ZEXT:
 263       return tryCombineZExt(MI, DeadInsts);
 264     case TargetOpcode::G_SEXT:
 265       return tryCombineSExt(MI, DeadInsts);
 266     case TargetOpcode::G_UNMERGE_VALUES:
 267       return tryCombineMerges(MI, DeadInsts);
 268     case TargetOpcode::G_TRUNC: {
 269       bool Changed = false;
 270       for (auto &Use : MRI.use_instructions(MI.getOperand(0).getReg()))
 271         Changed |= tryCombineInstruction(Use, DeadInsts);
 272       return Changed;
 273     }
 274     }
 275   }
 276
 277 private:
 278   /// Mark MI as dead. If a def of one of MI's operands, DefMI, would also be
 279   /// dead due to MI being killed, then mark DefMI as dead too.
 280   /// Some of the combines (extends(trunc)), try to walk through redundant
 281   /// copies in between the extends and the truncs, and this attempts to collect
 282   /// the in between copies if they're dead.
 283   void markInstAndDefDead(MachineInstr &MI, MachineInstr &DefMI,
 284                           SmallVectorImpl<MachineInstr *> &DeadInsts) {
 285     DeadInsts.push_back(&MI);
 286
 287     // Collect all the copy instructions that are made dead, due to deleting
 288     // this instruction. Collect all of them until the Trunc(DefMI).
 289     // Eg,
 290     // %1(s1) = G_TRUNC %0(s32)
 291     // %2(s1) = COPY %1(s1)
 292     // %3(s1) = COPY %2(s1)
 293     // %4(s32) = G_ANYEXT %3(s1)
 294     // In this case, we would have replaced %4 with a copy of %0,
 295     // and as a result, %3, %2, %1 are dead.
 296     MachineInstr *PrevMI = &MI;
 297     while (PrevMI != &DefMI) {
 298       unsigned PrevRegSrc =
 299           PrevMI->getOperand(PrevMI->getNumOperands() - 1).getReg();
 300       MachineInstr *TmpDef = MRI.getVRegDef(PrevRegSrc);
 301       if (MRI.hasOneUse(PrevRegSrc)) {
 302         if (TmpDef != &DefMI) {
 303           assert(TmpDef->getOpcode() == TargetOpcode::COPY &&
 304                  "Expecting copy here");
 305           DeadInsts.push_back(TmpDef);
 306         }
 307       } else
 308         break;
 309       PrevMI = TmpDef;
 310     }
 311     if (PrevMI == &DefMI && MRI.hasOneUse(DefMI.getOperand(0).getReg()))
 312       DeadInsts.push_back(&DefMI);
 313   }
 314
 315   /// Checks if the target legalizer info has specified anything about the
 316   /// instruction, or if unsupported.
 317   bool isInstUnsupported(const LegalityQuery &Query) const {
 318     using namespace LegalizeActions;
 319     auto Step = LI.getAction(Query);
 320     return Step.Action == Unsupported || Step.Action == NotFound;
 321   }
 322
 323   /// Looks through copy instructions and returns the actual
 324   /// source register.
 325   unsigned lookThroughCopyInstrs(unsigned Reg) {
 326     unsigned TmpReg;
 327     while (mi_match(Reg, MRI, m_Copy(m_Reg(TmpReg)))) {
 328       if (MRI.getType(TmpReg).isValid())
 329         Reg = TmpReg;
 330       else
 331         break;
 332     }
 333     return Reg;
 334   }
 335 };
 336
 337 } // namespace llvm