include/llvm/CodeGen/GlobalISel/LegalizationArtifactCombiner.h

   1 //===-- llvm/CodeGen/GlobalISel/LegalizationArtifactCombiner.h -----*- C++ -*-//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 // This file contains some helper functions which try to cleanup artifacts
   9 // such as G_TRUNCs/G_[ZSA]EXTENDS that were created during legalization to make
  10 // the types match. This file also contains some combines of merges that happens
  11 // at the end of the legalization.
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "llvm/CodeGen/GlobalISel/Legalizer.h"
  15 #include "llvm/CodeGen/GlobalISel/LegalizerInfo.h"
  16 #include "llvm/CodeGen/GlobalISel/MIPatternMatch.h"
  17 #include "llvm/CodeGen/GlobalISel/MachineIRBuilder.h"
  18 #include "llvm/CodeGen/GlobalISel/Utils.h"
  19 #include "llvm/CodeGen/MachineRegisterInfo.h"
  20 #include "llvm/Support/Debug.h"
  21
  22 #define DEBUG_TYPE "legalizer"
  23 using namespace llvm::MIPatternMatch;
  24
  25 namespace llvm {
  26 class LegalizationArtifactCombiner {
  27   MachineIRBuilder &Builder;
  28   MachineRegisterInfo &MRI;
  29   const LegalizerInfo &LI;
  30
  31 public:
  32   LegalizationArtifactCombiner(MachineIRBuilder &B, MachineRegisterInfo &MRI,
  33                     const LegalizerInfo &LI)
  34       : Builder(B), MRI(MRI), LI(LI) {}
  35
  36   bool tryCombineAnyExt(MachineInstr &MI,
  37                         SmallVectorImpl<MachineInstr *> &DeadInsts) {
  38     if (MI.getOpcode() != TargetOpcode::G_ANYEXT)
  39       return false;
  40
  41     Builder.setInstr(MI);
  42     unsigned DstReg = MI.getOperand(0).getReg();
  43     unsigned SrcReg = lookThroughCopyInstrs(MI.getOperand(1).getReg());
  44
  45     // aext(trunc x) - > aext/copy/trunc x
  46     unsigned TruncSrc;
  47     if (mi_match(SrcReg, MRI, m_GTrunc(m_Reg(TruncSrc)))) {
  48       LLVM_DEBUG(dbgs() << ".. Combine MI: " << MI;);
  49       Builder.buildAnyExtOrTrunc(DstReg, TruncSrc);
  50       markInstAndDefDead(MI, *MRI.getVRegDef(SrcReg), DeadInsts);
  51       return true;
  52     }
  53
  54     // aext([asz]ext x) -> [asz]ext x
  55     unsigned ExtSrc;
  56     MachineInstr *ExtMI;
  57     if (mi_match(SrcReg, MRI,
  58                  m_all_of(m_MInstr(ExtMI), m_any_of(m_GAnyExt(m_Reg(ExtSrc)),
  59                                                     m_GSExt(m_Reg(ExtSrc)),
  60                                                     m_GZExt(m_Reg(ExtSrc)))))) {
  61       Builder.buildInstr(ExtMI->getOpcode(), {DstReg}, {ExtSrc});
  62       markInstAndDefDead(MI, *ExtMI, DeadInsts);
  63       return true;
  64     }
  65     return tryFoldImplicitDef(MI, DeadInsts);
  66   }
  67
  68   bool tryCombineZExt(MachineInstr &MI,
  69                       SmallVectorImpl<MachineInstr *> &DeadInsts) {
  70
  71     if (MI.getOpcode() != TargetOpcode::G_ZEXT)
  72       return false;
  73
  74     Builder.setInstr(MI);
  75     unsigned DstReg = MI.getOperand(0).getReg();
  76     unsigned SrcReg = lookThroughCopyInstrs(MI.getOperand(1).getReg());
  77
  78     // zext(trunc x) - > and (aext/copy/trunc x), mask
  79     unsigned TruncSrc;
  80     if (mi_match(SrcReg, MRI, m_GTrunc(m_Reg(TruncSrc)))) {
  81       LLT DstTy = MRI.getType(DstReg);
  82       if (isInstUnsupported({TargetOpcode::G_AND, {DstTy}}) ||
  83           isConstantUnsupported(DstTy))
  84         return false;
  85       LLVM_DEBUG(dbgs() << ".. Combine MI: " << MI;);
  86       LLT SrcTy = MRI.getType(SrcReg);
  87       APInt Mask = APInt::getAllOnesValue(SrcTy.getScalarSizeInBits());
  88       auto MIBMask = Builder.buildConstant(DstTy, Mask.getZExtValue());
  89       Builder.buildAnd(DstReg, Builder.buildAnyExtOrTrunc(DstTy, TruncSrc),
  90                        MIBMask);
  91       markInstAndDefDead(MI, *MRI.getVRegDef(SrcReg), DeadInsts);
  92       return true;
  93     }
  94     return tryFoldImplicitDef(MI, DeadInsts);
  95   }
  96
  97   bool tryCombineSExt(MachineInstr &MI,
  98                       SmallVectorImpl<MachineInstr *> &DeadInsts) {
  99
 100     if (MI.getOpcode() != TargetOpcode::G_SEXT)
 101       return false;
 102
 103     Builder.setInstr(MI);
 104     unsigned DstReg = MI.getOperand(0).getReg();
 105     unsigned SrcReg = lookThroughCopyInstrs(MI.getOperand(1).getReg());
 106
 107     // sext(trunc x) - > ashr (shl (aext/copy/trunc x), c), c
 108     unsigned TruncSrc;
 109     if (mi_match(SrcReg, MRI, m_GTrunc(m_Reg(TruncSrc)))) {
 110       LLT DstTy = MRI.getType(DstReg);
 111       // Guess on the RHS shift amount type, which should be re-legalized if
 112       // applicable.
 113       if (isInstUnsupported({TargetOpcode::G_SHL, {DstTy, DstTy}}) ||
 114           isInstUnsupported({TargetOpcode::G_ASHR, {DstTy, DstTy}}) ||
 115           isConstantUnsupported(DstTy))
 116         return false;
 117       LLVM_DEBUG(dbgs() << ".. Combine MI: " << MI;);
 118       LLT SrcTy = MRI.getType(SrcReg);
 119       unsigned ShAmt = DstTy.getScalarSizeInBits() - SrcTy.getScalarSizeInBits();
 120       auto MIBShAmt = Builder.buildConstant(DstTy, ShAmt);
 121       auto MIBShl = Builder.buildInstr(
 122           TargetOpcode::G_SHL, {DstTy},
 123           {Builder.buildAnyExtOrTrunc(DstTy, TruncSrc), MIBShAmt});
 124       Builder.buildInstr(TargetOpcode::G_ASHR, {DstReg}, {MIBShl, MIBShAmt});
 125       markInstAndDefDead(MI, *MRI.getVRegDef(SrcReg), DeadInsts);
 126       return true;
 127     }
 128     return tryFoldImplicitDef(MI, DeadInsts);
 129   }
 130
 131   /// Try to fold G_[ASZ]EXT (G_IMPLICIT_DEF).
 132   bool tryFoldImplicitDef(MachineInstr &MI,
 133                           SmallVectorImpl<MachineInstr *> &DeadInsts) {
 134     unsigned Opcode = MI.getOpcode();
 135     if (Opcode != TargetOpcode::G_ANYEXT && Opcode != TargetOpcode::G_ZEXT &&
 136         Opcode != TargetOpcode::G_SEXT)
 137       return false;
 138
 139     if (MachineInstr *DefMI = getOpcodeDef(TargetOpcode::G_IMPLICIT_DEF,
 140                                            MI.getOperand(1).getReg(), MRI)) {
 141       Builder.setInstr(MI);
 142       unsigned DstReg = MI.getOperand(0).getReg();
 143       LLT DstTy = MRI.getType(DstReg);
 144
 145       if (Opcode == TargetOpcode::G_ANYEXT) {
 146         // G_ANYEXT (G_IMPLICIT_DEF) -> G_IMPLICIT_DEF
 147         if (isInstUnsupported({TargetOpcode::G_IMPLICIT_DEF, {DstTy}}))
 148           return false;
 149         LLVM_DEBUG(dbgs() << ".. Combine G_ANYEXT(G_IMPLICIT_DEF): " << MI;);
 150         Builder.buildInstr(TargetOpcode::G_IMPLICIT_DEF, {DstReg}, {});
 151       } else {
 152         // G_[SZ]EXT (G_IMPLICIT_DEF) -> G_CONSTANT 0 because the top
 153         // bits will be 0 for G_ZEXT and 0/1 for the G_SEXT.
 154         if (isConstantUnsupported(DstTy))
 155           return false;
 156         LLVM_DEBUG(dbgs() << ".. Combine G_[SZ]EXT(G_IMPLICIT_DEF): " << MI;);
 157         Builder.buildConstant(DstReg, 0);
 158       }
 159
 160       markInstAndDefDead(MI, *DefMI, DeadInsts);
 161       return true;
 162     }
 163     return false;
 164   }
 165
 166   static unsigned getMergeOpcode(LLT OpTy, LLT DestTy) {
 167     if (OpTy.isVector() && DestTy.isVector())
 168       return TargetOpcode::G_CONCAT_VECTORS;
 169
 170     if (OpTy.isVector() && !DestTy.isVector())
 171       return TargetOpcode::G_BUILD_VECTOR;
 172
 173     return TargetOpcode::G_MERGE_VALUES;
 174   }
 175
 176   bool tryCombineMerges(MachineInstr &MI,
 177                         SmallVectorImpl<MachineInstr *> &DeadInsts) {
 178
 179     if (MI.getOpcode() != TargetOpcode::G_UNMERGE_VALUES)
 180       return false;
 181
 182     unsigned NumDefs = MI.getNumOperands() - 1;
 183
 184     LLT OpTy = MRI.getType(MI.getOperand(NumDefs).getReg());
 185     LLT DestTy = MRI.getType(MI.getOperand(0).getReg());
 186
 187     unsigned MergingOpcode = getMergeOpcode(OpTy, DestTy);
 188     MachineInstr *MergeI =
 189         getOpcodeDef(MergingOpcode, MI.getOperand(NumDefs).getReg(), MRI);
 190
 191     if (!MergeI)
 192       return false;
 193
 194     const unsigned NumMergeRegs = MergeI->getNumOperands() - 1;
 195
 196     if (NumMergeRegs < NumDefs) {
 197       if (NumDefs % NumMergeRegs != 0)
 198         return false;
 199
 200       Builder.setInstr(MI);
 201       // Transform to UNMERGEs, for example
 202       //   %1 = G_MERGE_VALUES %4, %5
 203       //   %9, %10, %11, %12 = G_UNMERGE_VALUES %1
 204       // to
 205       //   %9, %10 = G_UNMERGE_VALUES %4
 206       //   %11, %12 = G_UNMERGE_VALUES %5
 207
 208       const unsigned NewNumDefs = NumDefs / NumMergeRegs;
 209       for (unsigned Idx = 0; Idx < NumMergeRegs; ++Idx) {
 210         SmallVector<unsigned, 2> DstRegs;
 211         for (unsigned j = 0, DefIdx = Idx * NewNumDefs; j < NewNumDefs;
 212              ++j, ++DefIdx)
 213           DstRegs.push_back(MI.getOperand(DefIdx).getReg());
 214
 215         Builder.buildUnmerge(DstRegs, MergeI->getOperand(Idx + 1).getReg());
 216       }
 217
 218     } else if (NumMergeRegs > NumDefs) {
 219       if (NumMergeRegs % NumDefs != 0)
 220         return false;
 221
 222       Builder.setInstr(MI);
 223       // Transform to MERGEs
 224       //   %6 = G_MERGE_VALUES %17, %18, %19, %20
 225       //   %7, %8 = G_UNMERGE_VALUES %6
 226       // to
 227       //   %7 = G_MERGE_VALUES %17, %18
 228       //   %8 = G_MERGE_VALUES %19, %20
 229
 230       const unsigned NumRegs = NumMergeRegs / NumDefs;
 231       for (unsigned DefIdx = 0; DefIdx < NumDefs; ++DefIdx) {
 232         SmallVector<unsigned, 2> Regs;
 233         for (unsigned j = 0, Idx = NumRegs * DefIdx + 1; j < NumRegs;
 234              ++j, ++Idx)
 235           Regs.push_back(MergeI->getOperand(Idx).getReg());
 236
 237         Builder.buildMerge(MI.getOperand(DefIdx).getReg(), Regs);
 238       }
 239
 240     } else {
 241       // FIXME: is a COPY appropriate if the types mismatch? We know both
 242       // registers are allocatable by now.
 243       if (MRI.getType(MI.getOperand(0).getReg()) !=
 244           MRI.getType(MergeI->getOperand(1).getReg()))
 245         return false;
 246
 247       for (unsigned Idx = 0; Idx < NumDefs; ++Idx)
 248         MRI.replaceRegWith(MI.getOperand(Idx).getReg(),
 249                            MergeI->getOperand(Idx + 1).getReg());
 250     }
 251
 252     markInstAndDefDead(MI, *MergeI, DeadInsts);
 253     return true;
 254   }
 255
 256   static bool isMergeLikeOpcode(unsigned Opc) {
 257     switch (Opc) {
 258     case TargetOpcode::G_MERGE_VALUES:
 259     case TargetOpcode::G_BUILD_VECTOR:
 260     case TargetOpcode::G_CONCAT_VECTORS:
 261       return true;
 262     default:
 263       return false;
 264     }
 265   }
 266
 267   bool tryCombineExtract(MachineInstr &MI,
 268                          SmallVectorImpl<MachineInstr *> &DeadInsts) {
 269     assert(MI.getOpcode() == TargetOpcode::G_EXTRACT);
 270
 271     // Try to use the source registers from a G_MERGE_VALUES
 272     //
 273     // %2 = G_MERGE_VALUES %0, %1
 274     // %3 = G_EXTRACT %2, N
 275     // =>
 276     //
 277     // for N < %2.getSizeInBits() / 2
 278     //     %3 = G_EXTRACT %0, N
 279     //
 280     // for N >= %2.getSizeInBits() / 2
 281     //    %3 = G_EXTRACT %1, (N - %0.getSizeInBits()
 282
 283     unsigned Src = lookThroughCopyInstrs(MI.getOperand(1).getReg());
 284     MachineInstr *MergeI = MRI.getVRegDef(Src);
 285     if (!MergeI || !isMergeLikeOpcode(MergeI->getOpcode()))
 286       return false;
 287
 288     LLT DstTy = MRI.getType(MI.getOperand(0).getReg());
 289     LLT SrcTy = MRI.getType(Src);
 290
 291     // TODO: Do we need to check if the resulting extract is supported?
 292     unsigned ExtractDstSize = DstTy.getSizeInBits();
 293     unsigned Offset = MI.getOperand(2).getImm();
 294     unsigned NumMergeSrcs = MergeI->getNumOperands() - 1;
 295     unsigned MergeSrcSize = SrcTy.getSizeInBits() / NumMergeSrcs;
 296     unsigned MergeSrcIdx = Offset / MergeSrcSize;
 297
 298     // Compute the offset of the last bit the extract needs.
 299     unsigned EndMergeSrcIdx = (Offset + ExtractDstSize - 1) / MergeSrcSize;
 300
 301     // Can't handle the case where the extract spans multiple inputs.
 302     if (MergeSrcIdx != EndMergeSrcIdx)
 303       return false;
 304
 305     // TODO: We could modify MI in place in most cases.
 306     Builder.setInstr(MI);
 307     Builder.buildExtract(
 308       MI.getOperand(0).getReg(),
 309       MergeI->getOperand(MergeSrcIdx + 1).getReg(),
 310       Offset - MergeSrcIdx * MergeSrcSize);
 311     markInstAndDefDead(MI, *MergeI, DeadInsts);
 312     return true;
 313   }
 314
 315   /// Try to combine away MI.
 316   /// Returns true if it combined away the MI.
 317   /// Adds instructions that are dead as a result of the combine
 318   /// into DeadInsts, which can include MI.
 319   bool tryCombineInstruction(MachineInstr &MI,
 320                              SmallVectorImpl<MachineInstr *> &DeadInsts) {
 321     switch (MI.getOpcode()) {
 322     default:
 323       return false;
 324     case TargetOpcode::G_ANYEXT:
 325       return tryCombineAnyExt(MI, DeadInsts);
 326     case TargetOpcode::G_ZEXT:
 327       return tryCombineZExt(MI, DeadInsts);
 328     case TargetOpcode::G_SEXT:
 329       return tryCombineSExt(MI, DeadInsts);
 330     case TargetOpcode::G_UNMERGE_VALUES:
 331       return tryCombineMerges(MI, DeadInsts);
 332     case TargetOpcode::G_EXTRACT:
 333       return tryCombineExtract(MI, DeadInsts);
 334     case TargetOpcode::G_TRUNC: {
 335       bool Changed = false;
 336       for (auto &Use : MRI.use_instructions(MI.getOperand(0).getReg()))
 337         Changed |= tryCombineInstruction(Use, DeadInsts);
 338       return Changed;
 339     }
 340     }
 341   }
 342
 343 private:
 344
 345   static unsigned getArtifactSrcReg(const MachineInstr &MI) {
 346     switch (MI.getOpcode()) {
 347     case TargetOpcode::COPY:
 348     case TargetOpcode::G_TRUNC:
 349     case TargetOpcode::G_ZEXT:
 350     case TargetOpcode::G_ANYEXT:
 351     case TargetOpcode::G_SEXT:
 352     case TargetOpcode::G_UNMERGE_VALUES:
 353       return MI.getOperand(MI.getNumOperands() - 1).getReg();
 354     case TargetOpcode::G_EXTRACT:
 355       return MI.getOperand(1).getReg();
 356     default:
 357       llvm_unreachable("Not a legalization artifact happen");
 358     }
 359   }
 360
 361   /// Mark MI as dead. If a def of one of MI's operands, DefMI, would also be
 362   /// dead due to MI being killed, then mark DefMI as dead too.
 363   /// Some of the combines (extends(trunc)), try to walk through redundant
 364   /// copies in between the extends and the truncs, and this attempts to collect
 365   /// the in between copies if they're dead.
 366   void markInstAndDefDead(MachineInstr &MI, MachineInstr &DefMI,
 367                           SmallVectorImpl<MachineInstr *> &DeadInsts) {
 368     DeadInsts.push_back(&MI);
 369
 370     // Collect all the copy instructions that are made dead, due to deleting
 371     // this instruction. Collect all of them until the Trunc(DefMI).
 372     // Eg,
 373     // %1(s1) = G_TRUNC %0(s32)
 374     // %2(s1) = COPY %1(s1)
 375     // %3(s1) = COPY %2(s1)
 376     // %4(s32) = G_ANYEXT %3(s1)
 377     // In this case, we would have replaced %4 with a copy of %0,
 378     // and as a result, %3, %2, %1 are dead.
 379     MachineInstr *PrevMI = &MI;
 380     while (PrevMI != &DefMI) {
 381       unsigned PrevRegSrc = getArtifactSrcReg(*PrevMI);
 382
 383       MachineInstr *TmpDef = MRI.getVRegDef(PrevRegSrc);
 384       if (MRI.hasOneUse(PrevRegSrc)) {
 385         if (TmpDef != &DefMI) {
 386           assert(TmpDef->getOpcode() == TargetOpcode::COPY &&
 387                  "Expecting copy here");
 388           DeadInsts.push_back(TmpDef);
 389         }
 390       } else
 391         break;
 392       PrevMI = TmpDef;
 393     }
 394     if (PrevMI == &DefMI && MRI.hasOneUse(DefMI.getOperand(0).getReg()))
 395       DeadInsts.push_back(&DefMI);
 396   }
 397
 398   /// Checks if the target legalizer info has specified anything about the
 399   /// instruction, or if unsupported.
 400   bool isInstUnsupported(const LegalityQuery &Query) const {
 401     using namespace LegalizeActions;
 402     auto Step = LI.getAction(Query);
 403     return Step.Action == Unsupported || Step.Action == NotFound;
 404   }
 405
 406   bool isConstantUnsupported(LLT Ty) const {
 407     if (!Ty.isVector())
 408       return isInstUnsupported({TargetOpcode::G_CONSTANT, {Ty}});
 409
 410     LLT EltTy = Ty.getElementType();
 411     return isInstUnsupported({TargetOpcode::G_CONSTANT, {EltTy}}) ||
 412            isInstUnsupported({TargetOpcode::G_BUILD_VECTOR, {Ty, EltTy}});
 413   }
 414
 415   /// Looks through copy instructions and returns the actual
 416   /// source register.
 417   unsigned lookThroughCopyInstrs(unsigned Reg) {
 418     unsigned TmpReg;
 419     while (mi_match(Reg, MRI, m_Copy(m_Reg(TmpReg)))) {
 420       if (MRI.getType(TmpReg).isValid())
 421         Reg = TmpReg;
 422       else
 423         break;
 424     }
 425     return Reg;
 426   }
 427 };
 428
 429 } // namespace llvm