llvm/lib/Target/AArch64/GISel/AArch64PostLegalizerCombiner.cpp

   1 //=== lib/CodeGen/GlobalISel/AArch64PostLegalizerCombiner.cpp -------------===//
   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 //
   9 // This performs post-legalization combines on generic MachineInstrs.
  10 //
  11 // Any combine that this pass performs must preserve instruction legality.
  12 // Combines unconcerned with legality should be handled by the
  13 // PreLegalizerCombiner instead.
  14 //
  15 //===----------------------------------------------------------------------===//
  16
  17 #include "AArch64TargetMachine.h"
  18 #include "llvm/CodeGen/GlobalISel/Combiner.h"
  19 #include "llvm/CodeGen/GlobalISel/CombinerHelper.h"
  20 #include "llvm/CodeGen/GlobalISel/CombinerInfo.h"
  21 #include "llvm/CodeGen/GlobalISel/GISelKnownBits.h"
  22 #include "llvm/CodeGen/MachineDominators.h"
  23 #include "llvm/CodeGen/MachineFunctionPass.h"
  24 #include "llvm/CodeGen/TargetPassConfig.h"
  25 #include "llvm/Support/Debug.h"
  26
  27 #define DEBUG_TYPE "aarch64-postlegalizer-combiner"
  28
  29 using namespace llvm;
  30
  31 /// Represents a pseudo instruction which replaces a G_SHUFFLE_VECTOR.
  32 ///
  33 /// Used for matching target-supported shuffles before codegen.
  34 struct ShuffleVectorPseudo {
  35   unsigned Opc; ///< Opcode for the instruction. (E.g. G_ZIP1)
  36   Register Dst; ///< Destination register.
  37   SmallVector<SrcOp, 2> SrcOps; ///< Source registers.
  38   ShuffleVectorPseudo(unsigned Opc, Register Dst,
  39                       std::initializer_list<SrcOp> SrcOps)
  40       : Opc(Opc), Dst(Dst), SrcOps(SrcOps){};
  41   ShuffleVectorPseudo() {}
  42 };
  43
  44 /// Check if a vector shuffle corresponds to a REV instruction with the
  45 /// specified blocksize.
  46 static bool isREVMask(ArrayRef<int> M, unsigned EltSize, unsigned NumElts,
  47                       unsigned BlockSize) {
  48   assert((BlockSize == 16 || BlockSize == 32 || BlockSize == 64) &&
  49          "Only possible block sizes for REV are: 16, 32, 64");
  50   assert(EltSize != 64 && "EltSize cannot be 64 for REV mask.");
  51
  52   unsigned BlockElts = M[0] + 1;
  53
  54   // If the first shuffle index is UNDEF, be optimistic.
  55   if (M[0] < 0)
  56     BlockElts = BlockSize / EltSize;
  57
  58   if (BlockSize <= EltSize || BlockSize != BlockElts * EltSize)
  59     return false;
  60
  61   for (unsigned i = 0; i < NumElts; ++i) {
  62     // Ignore undef indices.
  63     if (M[i] < 0)
  64       continue;
  65     if (static_cast<unsigned>(M[i]) !=
  66         (i - i % BlockElts) + (BlockElts - 1 - i % BlockElts))
  67       return false;
  68   }
  69
  70   return true;
  71 }
  72
  73 /// Determines if \p M is a shuffle vector mask for a UZP of \p NumElts.
  74 /// Whether or not G_UZP1 or G_UZP2 should be used is stored in \p WhichResult.
  75 static bool isUZPMask(ArrayRef<int> M, unsigned NumElts,
  76                       unsigned &WhichResult) {
  77   WhichResult = (M[0] == 0 ? 0 : 1);
  78   for (unsigned i = 0; i != NumElts; ++i) {
  79     // Skip undef indices.
  80     if (M[i] < 0)
  81       continue;
  82     if (static_cast<unsigned>(M[i]) != 2 * i + WhichResult)
  83       return false;
  84   }
  85   return true;
  86 }
  87
  88 /// \return true if \p M is a zip mask for a shuffle vector of \p NumElts.
  89 /// Whether or not G_ZIP1 or G_ZIP2 should be used is stored in \p WhichResult.
  90 static bool isZipMask(ArrayRef<int> M, unsigned NumElts,
  91                       unsigned &WhichResult) {
  92   if (NumElts % 2 != 0)
  93     return false;
  94
  95   // 0 means use ZIP1, 1 means use ZIP2.
  96   WhichResult = (M[0] == 0 ? 0 : 1);
  97   unsigned Idx = WhichResult * NumElts / 2;
  98   for (unsigned i = 0; i != NumElts; i += 2) {
  99       if ((M[i] >= 0 && static_cast<unsigned>(M[i]) != Idx) ||
 100           (M[i + 1] >= 0 && static_cast<unsigned>(M[i + 1]) != Idx + NumElts))
 101         return false;
 102     Idx += 1;
 103   }
 104   return true;
 105 }
 106
 107 /// \return true if a G_SHUFFLE_VECTOR instruction \p MI can be replaced with a
 108 /// G_REV instruction. Returns the appropriate G_REV opcode in \p Opc.
 109 static bool matchREV(MachineInstr &MI, MachineRegisterInfo &MRI,
 110                      ShuffleVectorPseudo &MatchInfo) {
 111   assert(MI.getOpcode() == TargetOpcode::G_SHUFFLE_VECTOR);
 112   ArrayRef<int> ShuffleMask = MI.getOperand(3).getShuffleMask();
 113   Register Dst = MI.getOperand(0).getReg();
 114   Register Src = MI.getOperand(1).getReg();
 115   LLT Ty = MRI.getType(Dst);
 116   unsigned EltSize = Ty.getScalarSizeInBits();
 117
 118   // Element size for a rev cannot be 64.
 119   if (EltSize == 64)
 120     return false;
 121
 122   unsigned NumElts = Ty.getNumElements();
 123
 124   // Try to produce G_REV64
 125   if (isREVMask(ShuffleMask, EltSize, NumElts, 64)) {
 126     MatchInfo = ShuffleVectorPseudo(AArch64::G_REV64, Dst, {Src});
 127     return true;
 128   }
 129
 130   // TODO: Produce G_REV32 and G_REV16 once we have proper legalization support.
 131   // This should be identical to above, but with a constant 32 and constant
 132   // 16.
 133   return false;
 134 }
 135
 136 /// \return true if a G_SHUFFLE_VECTOR instruction \p MI can be replaced with
 137 /// a G_UZP1 or G_UZP2 instruction.
 138 ///
 139 /// \param [in] MI - The shuffle vector instruction.
 140 /// \param [out] Opc - Either G_UZP1 or G_UZP2 on success.
 141 static bool matchUZP(MachineInstr &MI, MachineRegisterInfo &MRI,
 142                      ShuffleVectorPseudo &MatchInfo) {
 143   assert(MI.getOpcode() == TargetOpcode::G_SHUFFLE_VECTOR);
 144   unsigned WhichResult;
 145   ArrayRef<int> ShuffleMask = MI.getOperand(3).getShuffleMask();
 146   Register Dst = MI.getOperand(0).getReg();
 147   unsigned NumElts = MRI.getType(Dst).getNumElements();
 148   if (!isUZPMask(ShuffleMask, NumElts, WhichResult))
 149     return false;
 150   unsigned Opc = (WhichResult == 0) ? AArch64::G_UZP1 : AArch64::G_UZP2;
 151   Register V1 = MI.getOperand(1).getReg();
 152   Register V2 = MI.getOperand(2).getReg();
 153   MatchInfo = ShuffleVectorPseudo(Opc, Dst, {V1, V2});
 154   return true;
 155 }
 156
 157 static bool matchZip(MachineInstr &MI, MachineRegisterInfo &MRI,
 158                      ShuffleVectorPseudo &MatchInfo) {
 159   assert(MI.getOpcode() == TargetOpcode::G_SHUFFLE_VECTOR);
 160   unsigned WhichResult;
 161   ArrayRef<int> ShuffleMask = MI.getOperand(3).getShuffleMask();
 162   Register Dst = MI.getOperand(0).getReg();
 163   unsigned NumElts = MRI.getType(Dst).getNumElements();
 164   if (!isZipMask(ShuffleMask, NumElts, WhichResult))
 165     return false;
 166   unsigned Opc = (WhichResult == 0) ? AArch64::G_ZIP1 : AArch64::G_ZIP2;
 167   Register V1 = MI.getOperand(1).getReg();
 168   Register V2 = MI.getOperand(2).getReg();
 169   MatchInfo = ShuffleVectorPseudo(Opc, Dst, {V1, V2});
 170   return true;
 171 }
 172
 173 /// Replace a G_SHUFFLE_VECTOR instruction with a pseudo.
 174 /// \p Opc is the opcode to use. \p MI is the G_SHUFFLE_VECTOR.
 175 static bool applyShuffleVectorPseudo(MachineInstr &MI,
 176                                      ShuffleVectorPseudo &MatchInfo) {
 177   MachineIRBuilder MIRBuilder(MI);
 178   MIRBuilder.buildInstr(MatchInfo.Opc, {MatchInfo.Dst}, MatchInfo.SrcOps);
 179   MI.eraseFromParent();
 180   return true;
 181 }
 182
 183 #define AARCH64POSTLEGALIZERCOMBINERHELPER_GENCOMBINERHELPER_DEPS
 184 #include "AArch64GenPostLegalizeGICombiner.inc"
 185 #undef AARCH64POSTLEGALIZERCOMBINERHELPER_GENCOMBINERHELPER_DEPS
 186
 187 namespace {
 188 #define AARCH64POSTLEGALIZERCOMBINERHELPER_GENCOMBINERHELPER_H
 189 #include "AArch64GenPostLegalizeGICombiner.inc"
 190 #undef AARCH64POSTLEGALIZERCOMBINERHELPER_GENCOMBINERHELPER_H
 191
 192 class AArch64PostLegalizerCombinerInfo : public CombinerInfo {
 193   GISelKnownBits *KB;
 194   MachineDominatorTree *MDT;
 195
 196 public:
 197   AArch64GenPostLegalizerCombinerHelper Generated;
 198
 199   AArch64PostLegalizerCombinerInfo(bool EnableOpt, bool OptSize, bool MinSize,
 200                                    GISelKnownBits *KB,
 201                                    MachineDominatorTree *MDT)
 202       : CombinerInfo(/*AllowIllegalOps*/ true, /*ShouldLegalizeIllegal*/ false,
 203                      /*LegalizerInfo*/ nullptr, EnableOpt, OptSize, MinSize),
 204         KB(KB), MDT(MDT) {
 205     if (!Generated.parseCommandLineOption())
 206       report_fatal_error("Invalid rule identifier");
 207   }
 208
 209   virtual bool combine(GISelChangeObserver &Observer, MachineInstr &MI,
 210                        MachineIRBuilder &B) const override;
 211 };
 212
 213 bool AArch64PostLegalizerCombinerInfo::combine(GISelChangeObserver &Observer,
 214                                                MachineInstr &MI,
 215                                                MachineIRBuilder &B) const {
 216   const auto *LI =
 217       MI.getParent()->getParent()->getSubtarget().getLegalizerInfo();
 218   CombinerHelper Helper(Observer, B, KB, MDT, LI);
 219   return Generated.tryCombineAll(Observer, MI, B, Helper);
 220 }
 221
 222 #define AARCH64POSTLEGALIZERCOMBINERHELPER_GENCOMBINERHELPER_CPP
 223 #include "AArch64GenPostLegalizeGICombiner.inc"
 224 #undef AARCH64POSTLEGALIZERCOMBINERHELPER_GENCOMBINERHELPER_CPP
 225
 226 class AArch64PostLegalizerCombiner : public MachineFunctionPass {
 227 public:
 228   static char ID;
 229
 230   AArch64PostLegalizerCombiner(bool IsOptNone = false);
 231
 232   StringRef getPassName() const override {
 233     return "AArch64PostLegalizerCombiner";
 234   }
 235
 236   bool runOnMachineFunction(MachineFunction &MF) override;
 237   void getAnalysisUsage(AnalysisUsage &AU) const override;
 238
 239 private:
 240   bool IsOptNone;
 241 };
 242 } // end anonymous namespace
 243
 244 void AArch64PostLegalizerCombiner::getAnalysisUsage(AnalysisUsage &AU) const {
 245   AU.addRequired<TargetPassConfig>();
 246   AU.setPreservesCFG();
 247   getSelectionDAGFallbackAnalysisUsage(AU);
 248   AU.addRequired<GISelKnownBitsAnalysis>();
 249   AU.addPreserved<GISelKnownBitsAnalysis>();
 250   if (!IsOptNone) {
 251     AU.addRequired<MachineDominatorTree>();
 252     AU.addPreserved<MachineDominatorTree>();
 253   }
 254   MachineFunctionPass::getAnalysisUsage(AU);
 255 }
 256
 257 AArch64PostLegalizerCombiner::AArch64PostLegalizerCombiner(bool IsOptNone)
 258     : MachineFunctionPass(ID), IsOptNone(IsOptNone) {
 259   initializeAArch64PostLegalizerCombinerPass(*PassRegistry::getPassRegistry());
 260 }
 261
 262 bool AArch64PostLegalizerCombiner::runOnMachineFunction(MachineFunction &MF) {
 263   if (MF.getProperties().hasProperty(
 264           MachineFunctionProperties::Property::FailedISel))
 265     return false;
 266   assert(MF.getProperties().hasProperty(
 267              MachineFunctionProperties::Property::Legalized) &&
 268          "Expected a legalized function?");
 269   auto *TPC = &getAnalysis<TargetPassConfig>();
 270   const Function &F = MF.getFunction();
 271   bool EnableOpt =
 272       MF.getTarget().getOptLevel() != CodeGenOpt::None && !skipFunction(F);
 273   GISelKnownBits *KB = &getAnalysis<GISelKnownBitsAnalysis>().get(MF);
 274   MachineDominatorTree *MDT =
 275       IsOptNone ? nullptr : &getAnalysis<MachineDominatorTree>();
 276   AArch64PostLegalizerCombinerInfo PCInfo(EnableOpt, F.hasOptSize(),
 277                                           F.hasMinSize(), KB, MDT);
 278   Combiner C(PCInfo, TPC);
 279   return C.combineMachineInstrs(MF, /*CSEInfo*/ nullptr);
 280 }
 281
 282 char AArch64PostLegalizerCombiner::ID = 0;
 283 INITIALIZE_PASS_BEGIN(AArch64PostLegalizerCombiner, DEBUG_TYPE,
 284                       "Combine AArch64 MachineInstrs after legalization", false,
 285                       false)
 286 INITIALIZE_PASS_DEPENDENCY(TargetPassConfig)
 287 INITIALIZE_PASS_DEPENDENCY(GISelKnownBitsAnalysis)
 288 INITIALIZE_PASS_END(AArch64PostLegalizerCombiner, DEBUG_TYPE,
 289                     "Combine AArch64 MachineInstrs after legalization", false,
 290                     false)
 291
 292 namespace llvm {
 293 FunctionPass *createAArch64PostLegalizeCombiner(bool IsOptNone) {
 294   return new AArch64PostLegalizerCombiner(IsOptNone);
 295 }
 296 } // end namespace llvm