lib/Target/PowerPC/PPCVSXSwapRemoval.cpp

   1 //===----------- PPCVSXSwapRemoval.cpp - Remove VSX LE Swaps -------------===//
   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 // This pass analyzes vector computations and removes unnecessary
  11 // doubleword swaps (xxswapd instructions).  This pass is performed
  12 // only for little-endian VSX code generation.
  13 //
  14 // For this specific case, loads and stores of v4i32, v4f32, v2i64,
  15 // and v2f64 vectors are inefficient.  These are implemented using
  16 // the lxvd2x and stxvd2x instructions, which invert the order of
  17 // doublewords in a vector register.  Thus code generation inserts
  18 // an xxswapd after each such load, and prior to each such store.
  19 //
  20 // The extra xxswapd instructions reduce performance.  The purpose
  21 // of this pass is to reduce the number of xxswapd instructions
  22 // required for correctness.
  23 //
  24 // The primary insight is that much code that operates on vectors
  25 // does not care about the relative order of elements in a register,
  26 // so long as the correct memory order is preserved.  If we have a
  27 // computation where all input values are provided by lxvd2x/xxswapd,
  28 // all outputs are stored using xxswapd/lxvd2x, and all intermediate
  29 // computations are lane-insensitive (independent of element order),
  30 // then all the xxswapd instructions associated with the loads and
  31 // stores may be removed without changing observable semantics.
  32 //
  33 // This pass uses standard equivalence class infrastructure to create
  34 // maximal webs of computations fitting the above description.  Each
  35 // such web is then optimized by removing its unnecessary xxswapd
  36 // instructions.
  37 //
  38 // There are some lane-sensitive operations for which we can still
  39 // permit the optimization, provided we modify those operations
  40 // accordingly.  Such operations are identified as using "special
  41 // handling" within this module.
  42 //
  43 //===---------------------------------------------------------------------===//
  44
  45 #include "PPCInstrInfo.h"
  46 #include "PPC.h"
  47 #include "PPCInstrBuilder.h"
  48 #include "PPCTargetMachine.h"
  49 #include "llvm/ADT/DenseMap.h"
  50 #include "llvm/ADT/EquivalenceClasses.h"
  51 #include "llvm/CodeGen/MachineFunctionPass.h"
  52 #include "llvm/CodeGen/MachineInstrBuilder.h"
  53 #include "llvm/CodeGen/MachineRegisterInfo.h"
  54 #include "llvm/Support/Debug.h"
  55 #include "llvm/Support/Format.h"
  56 #include "llvm/Support/raw_ostream.h"
  57
  58 using namespace llvm;
  59
  60 #define DEBUG_TYPE "ppc-vsx-swaps"
  61
  62 namespace llvm {
  63   void initializePPCVSXSwapRemovalPass(PassRegistry&);
  64 }
  65
  66 namespace {
  67
  68 // A PPCVSXSwapEntry is created for each machine instruction that
  69 // is relevant to a vector computation.
  70 struct PPCVSXSwapEntry {
  71   // Pointer to the instruction.
  72   MachineInstr *VSEMI;
  73
  74   // Unique ID (position in the swap vector).
  75   int VSEId;
  76
  77   // Attributes of this node.
  78   unsigned int IsLoad : 1;
  79   unsigned int IsStore : 1;
  80   unsigned int IsSwap : 1;
  81   unsigned int MentionsPhysVR : 1;
  82   unsigned int HasImplicitSubreg : 1;
  83   unsigned int IsSwappable : 1;
  84   unsigned int SpecialHandling : 3;
  85   unsigned int WebRejected : 1;
  86   unsigned int WillRemove : 1;
  87 };
  88
  89 enum SHValues {
  90   SH_NONE = 0,
  91   SH_EXTRACT,
  92   SH_INSERT,
  93   SH_NOSWAP_LD,
  94   SH_NOSWAP_ST,
  95   SH_SPLAT
  96 };
  97
  98 struct PPCVSXSwapRemoval : public MachineFunctionPass {
  99
 100   static char ID;
 101   const PPCInstrInfo *TII;
 102   MachineFunction *MF;
 103   MachineRegisterInfo *MRI;
 104
 105   // Swap entries are allocated in a vector for better performance.
 106   std::vector<PPCVSXSwapEntry> SwapVector;
 107
 108   // A mapping is maintained between machine instructions and
 109   // their swap entries.  The key is the address of the MI.
 110   DenseMap<MachineInstr*, int> SwapMap;
 111
 112   // Equivalence classes are used to gather webs of related computation.
 113   // Swap entries are represented by their VSEId fields.
 114   EquivalenceClasses<int> *EC;
 115
 116   PPCVSXSwapRemoval() : MachineFunctionPass(ID) {
 117     initializePPCVSXSwapRemovalPass(*PassRegistry::getPassRegistry());
 118   }
 119
 120 private:
 121   // Initialize data structures.
 122   void initialize(MachineFunction &MFParm);
 123
 124   // Walk the machine instructions to gather vector usage information.
 125   // Return true iff vector mentions are present.
 126   bool gatherVectorInstructions();
 127
 128   // Add an entry to the swap vector and swap map.
 129   int addSwapEntry(MachineInstr *MI, PPCVSXSwapEntry &SwapEntry);
 130
 131   // Hunt backwards through COPY and SUBREG_TO_REG chains for a
 132   // source register.  VecIdx indicates the swap vector entry to
 133   // mark as mentioning a physical register if the search leads
 134   // to one.
 135   unsigned lookThruCopyLike(unsigned SrcReg, unsigned VecIdx);
 136
 137   // Generate equivalence classes for related computations (webs).
 138   void formWebs();
 139
 140   // Analyze webs and determine those that cannot be optimized.
 141   void recordUnoptimizableWebs();
 142
 143   // Record which swap instructions can be safely removed.
 144   void markSwapsForRemoval();
 145
 146   // Remove swaps and update other instructions requiring special
 147   // handling.  Return true iff any changes are made.
 148   bool removeSwaps();
 149
 150   // Update instructions requiring special handling.
 151   void handleSpecialSwappables(int EntryIdx);
 152
 153   // Dump a description of the entries in the swap vector.
 154   void dumpSwapVector();
 155
 156   // Return true iff the given register is in the given class.
 157   bool isRegInClass(unsigned Reg, const TargetRegisterClass *RC) {
 158     if (TargetRegisterInfo::isVirtualRegister(Reg))
 159       return RC->hasSubClassEq(MRI->getRegClass(Reg));
 160     if (RC->contains(Reg))
 161       return true;
 162     return false;
 163   }
 164
 165   // Return true iff the given register is a full vector register.
 166   bool isVecReg(unsigned Reg) {
 167     return (isRegInClass(Reg, &PPC::VSRCRegClass) ||
 168             isRegInClass(Reg, &PPC::VRRCRegClass));
 169   }
 170
 171 public:
 172   // Main entry point for this pass.
 173   bool runOnMachineFunction(MachineFunction &MF) override {
 174     // If we don't have VSX on the subtarget, don't do anything.
 175     const PPCSubtarget &STI = MF.getSubtarget<PPCSubtarget>();
 176     if (!STI.hasVSX())
 177       return false;
 178
 179     bool Changed = false;
 180     initialize(MF);
 181
 182     if (gatherVectorInstructions()) {
 183       formWebs();
 184       recordUnoptimizableWebs();
 185       markSwapsForRemoval();
 186       Changed = removeSwaps();
 187     }
 188
 189     // FIXME: See the allocation of EC in initialize().
 190     delete EC;
 191     return Changed;
 192   }
 193 };
 194
 195 // Initialize data structures for this pass.  In particular, clear the
 196 // swap vector and allocate the equivalence class mapping before
 197 // processing each function.
 198 void PPCVSXSwapRemoval::initialize(MachineFunction &MFParm) {
 199   MF = &MFParm;
 200   MRI = &MF->getRegInfo();
 201   TII = static_cast<const PPCInstrInfo*>(MF->getSubtarget().getInstrInfo());
 202
 203   // An initial vector size of 256 appears to work well in practice.
 204   // Small/medium functions with vector content tend not to incur a
 205   // reallocation at this size.  Three of the vector tests in
 206   // projects/test-suite reallocate, which seems like a reasonable rate.
 207   const int InitialVectorSize(256);
 208   SwapVector.clear();
 209   SwapVector.reserve(InitialVectorSize);
 210
 211   // FIXME: Currently we allocate EC each time because we don't have
 212   // access to the set representation on which to call clear().  Should
 213   // consider adding a clear() method to the EquivalenceClasses class.
 214   EC = new EquivalenceClasses<int>;
 215 }
 216
 217 // Create an entry in the swap vector for each instruction that mentions
 218 // a full vector register, recording various characteristics of the
 219 // instructions there.
 220 bool PPCVSXSwapRemoval::gatherVectorInstructions() {
 221   bool RelevantFunction = false;
 222
 223   for (MachineBasicBlock &MBB : *MF) {
 224     for (MachineInstr &MI : MBB) {
 225
 226       bool RelevantInstr = false;
 227       bool ImplicitSubreg = false;
 228
 229       for (const MachineOperand &MO : MI.operands()) {
 230         if (!MO.isReg())
 231           continue;
 232         unsigned Reg = MO.getReg();
 233         if (isVecReg(Reg)) {
 234           RelevantInstr = true;
 235           if (MO.getSubReg() != 0)
 236             ImplicitSubreg = true;
 237           break;
 238         }
 239       }
 240
 241       if (!RelevantInstr)
 242         continue;
 243
 244       RelevantFunction = true;
 245
 246       // Create a SwapEntry initialized to zeros, then fill in the
 247       // instruction and ID fields before pushing it to the back
 248       // of the swap vector.
 249       PPCVSXSwapEntry SwapEntry{};
 250       int VecIdx = addSwapEntry(&MI, SwapEntry);
 251
 252       if (ImplicitSubreg)
 253         SwapVector[VecIdx].HasImplicitSubreg = 1;
 254
 255       switch(MI.getOpcode()) {
 256       default:
 257         // Unless noted otherwise, an instruction is considered
 258         // safe for the optimization.  There are a large number of
 259         // such true-SIMD instructions (all vector math, logical,
 260         // select, compare, etc.).
 261         SwapVector[VecIdx].IsSwappable = 1;
 262         break;
 263       case PPC::XXPERMDI:
 264         // This is a swap if it is of the form XXPERMDI t, s, s, 2.
 265         // Unfortunately, MachineCSE ignores COPY and SUBREG_TO_REG, so we
 266         // can also see XXPERMDI t, SUBREG_TO_REG(s), SUBREG_TO_REG(s), 2,
 267         // for example.  We have to look through chains of COPY and
 268         // SUBREG_TO_REG to find the real source value for comparison.
 269         // If the real source value is a physical register, then mark the
 270         // XXPERMDI as mentioning a physical register.
 271         // Any other form of XXPERMDI is lane-sensitive and unsafe
 272         // for the optimization.
 273         if (MI.getOperand(3).getImm() == 2) {
 274           unsigned trueReg1 = lookThruCopyLike(MI.getOperand(1).getReg(),
 275                                                VecIdx);
 276           unsigned trueReg2 = lookThruCopyLike(MI.getOperand(2).getReg(),
 277                                                VecIdx);
 278           if (trueReg1 == trueReg2)
 279             SwapVector[VecIdx].IsSwap = 1;
 280         }
 281         break;
 282       case PPC::LVX:
 283         // Non-permuting loads are currently unsafe.  We can use special
 284         // handling for this in the future.  By not marking these as
 285         // IsSwap, we ensure computations containing them will be rejected
 286         // for now.
 287         SwapVector[VecIdx].IsLoad = 1;
 288         break;
 289       case PPC::LXVD2X:
 290       case PPC::LXVW4X:
 291         // Permuting loads are marked as both load and swap, and are
 292         // safe for optimization.
 293         SwapVector[VecIdx].IsLoad = 1;
 294         SwapVector[VecIdx].IsSwap = 1;
 295         break;
 296       case PPC::STVX:
 297         // Non-permuting stores are currently unsafe.  We can use special
 298         // handling for this in the future.  By not marking these as
 299         // IsSwap, we ensure computations containing them will be rejected
 300         // for now.
 301         SwapVector[VecIdx].IsStore = 1;
 302         break;
 303       case PPC::STXVD2X:
 304       case PPC::STXVW4X:
 305         // Permuting stores are marked as both store and swap, and are
 306         // safe for optimization.
 307         SwapVector[VecIdx].IsStore = 1;
 308         SwapVector[VecIdx].IsSwap = 1;
 309         break;
 310       case PPC::SUBREG_TO_REG:
 311         // These are fine provided they are moving between full vector
 312         // register classes.  For example, the VRs are a subset of the
 313         // VSRs, but each VR and each VSR is a full 128-bit register.
 314         if (isVecReg(MI.getOperand(0).getReg()) &&
 315             isVecReg(MI.getOperand(2).getReg()))
 316           SwapVector[VecIdx].IsSwappable = 1;
 317         break;
 318       case PPC::COPY:
 319         // These are fine provided they are moving between full vector
 320         // register classes.
 321         if (isVecReg(MI.getOperand(0).getReg()) &&
 322             isVecReg(MI.getOperand(1).getReg()))
 323           SwapVector[VecIdx].IsSwappable = 1;
 324         break;
 325       case PPC::VSPLTB:
 326       case PPC::VSPLTH:
 327       case PPC::VSPLTW:
 328         // Splats are lane-sensitive, but we can use special handling
 329         // to adjust the source lane for the splat.  This is not yet
 330         // implemented.  When it is, we need to uncomment the following:
 331         SwapVector[VecIdx].IsSwappable = 1;
 332         SwapVector[VecIdx].SpecialHandling = SHValues::SH_SPLAT;
 333         break;
 334       // The presence of the following lane-sensitive operations in a
 335       // web will kill the optimization, at least for now.  For these
 336       // we do nothing, causing the optimization to fail.
 337       // FIXME: Some of these could be permitted with special handling,
 338       // and will be phased in as time permits.
 339       // FIXME: There is no simple and maintainable way to express a set
 340       // of opcodes having a common attribute in TableGen.  Should this
 341       // change, this is a prime candidate to use such a mechanism.
 342       case PPC::INLINEASM:
 343       case PPC::EXTRACT_SUBREG:
 344       case PPC::INSERT_SUBREG:
 345       case PPC::COPY_TO_REGCLASS:
 346       case PPC::LVEBX:
 347       case PPC::LVEHX:
 348       case PPC::LVEWX:
 349       case PPC::LVSL:
 350       case PPC::LVSR:
 351       case PPC::LVXL:
 352       case PPC::LXVDSX:
 353       case PPC::STVEBX:
 354       case PPC::STVEHX:
 355       case PPC::STVEWX:
 356       case PPC::STVXL:
 357       case PPC::STXSDX:
 358       case PPC::VCIPHER:
 359       case PPC::VCIPHERLAST:
 360       case PPC::VMRGHB:
 361       case PPC::VMRGHH:
 362       case PPC::VMRGHW:
 363       case PPC::VMRGLB:
 364       case PPC::VMRGLH:
 365       case PPC::VMRGLW:
 366       case PPC::VMULESB:
 367       case PPC::VMULESH:
 368       case PPC::VMULESW:
 369       case PPC::VMULEUB:
 370       case PPC::VMULEUH:
 371       case PPC::VMULEUW:
 372       case PPC::VMULOSB:
 373       case PPC::VMULOSH:
 374       case PPC::VMULOSW:
 375       case PPC::VMULOUB:
 376       case PPC::VMULOUH:
 377       case PPC::VMULOUW:
 378       case PPC::VNCIPHER:
 379       case PPC::VNCIPHERLAST:
 380       case PPC::VPERM:
 381       case PPC::VPERMXOR:
 382       case PPC::VPKPX:
 383       case PPC::VPKSHSS:
 384       case PPC::VPKSHUS:
 385       case PPC::VPKSDSS:
 386       case PPC::VPKSDUS:
 387       case PPC::VPKSWSS:
 388       case PPC::VPKSWUS:
 389       case PPC::VPKUDUM:
 390       case PPC::VPKUDUS:
 391       case PPC::VPKUHUM:
 392       case PPC::VPKUHUS:
 393       case PPC::VPKUWUM:
 394       case PPC::VPKUWUS:
 395       case PPC::VPMSUMB:
 396       case PPC::VPMSUMD:
 397       case PPC::VPMSUMH:
 398       case PPC::VPMSUMW:
 399       case PPC::VRLB:
 400       case PPC::VRLD:
 401       case PPC::VRLH:
 402       case PPC::VRLW:
 403       case PPC::VSBOX:
 404       case PPC::VSHASIGMAD:
 405       case PPC::VSHASIGMAW:
 406       case PPC::VSL:
 407       case PPC::VSLDOI:
 408       case PPC::VSLO:
 409       case PPC::VSR:
 410       case PPC::VSRO:
 411       case PPC::VSUM2SWS:
 412       case PPC::VSUM4SBS:
 413       case PPC::VSUM4SHS:
 414       case PPC::VSUM4UBS:
 415       case PPC::VSUMSWS:
 416       case PPC::VUPKHPX:
 417       case PPC::VUPKHSB:
 418       case PPC::VUPKHSH:
 419       case PPC::VUPKHSW:
 420       case PPC::VUPKLPX:
 421       case PPC::VUPKLSB:
 422       case PPC::VUPKLSH:
 423       case PPC::VUPKLSW:
 424       case PPC::XXMRGHW:
 425       case PPC::XXMRGLW:
 426       case PPC::XXSPLTW:
 427         break;
 428       }
 429     }
 430   }
 431
 432   if (RelevantFunction) {
 433     DEBUG(dbgs() << "Swap vector when first built\n\n");
 434     dumpSwapVector();
 435   }
 436
 437   return RelevantFunction;
 438 }
 439
 440 // Add an entry to the swap vector and swap map, and make a
 441 // singleton equivalence class for the entry.
 442 int PPCVSXSwapRemoval::addSwapEntry(MachineInstr *MI,
 443                                   PPCVSXSwapEntry& SwapEntry) {
 444   SwapEntry.VSEMI = MI;
 445   SwapEntry.VSEId = SwapVector.size();
 446   SwapVector.push_back(SwapEntry);
 447   EC->insert(SwapEntry.VSEId);
 448   SwapMap[MI] = SwapEntry.VSEId;
 449   return SwapEntry.VSEId;
 450 }
 451
 452 // This is used to find the "true" source register for an
 453 // XXPERMDI instruction, since MachineCSE does not handle the
 454 // "copy-like" operations (Copy and SubregToReg).  Returns
 455 // the original SrcReg unless it is the target of a copy-like
 456 // operation, in which case we chain backwards through all
 457 // such operations to the ultimate source register.  If a
 458 // physical register is encountered, we stop the search and
 459 // flag the swap entry indicated by VecIdx (the original
 460 // XXPERMDI) as mentioning a physical register.  Similarly
 461 // for implicit subregister mentions (which should never
 462 // happen).
 463 unsigned PPCVSXSwapRemoval::lookThruCopyLike(unsigned SrcReg,
 464                                              unsigned VecIdx) {
 465   MachineInstr *MI = MRI->getVRegDef(SrcReg);
 466   if (!MI->isCopyLike())
 467     return SrcReg;
 468
 469   unsigned CopySrcReg, CopySrcSubreg;
 470   if (MI->isCopy()) {
 471     CopySrcReg = MI->getOperand(1).getReg();
 472     CopySrcSubreg = MI->getOperand(1).getSubReg();
 473   } else {
 474     assert(MI->isSubregToReg() && "bad opcode for lookThruCopyLike");
 475     CopySrcReg = MI->getOperand(2).getReg();
 476     CopySrcSubreg = MI->getOperand(2).getSubReg();
 477   }
 478
 479   if (!TargetRegisterInfo::isVirtualRegister(CopySrcReg)) {
 480     SwapVector[VecIdx].MentionsPhysVR = 1;
 481     return CopySrcReg;
 482   }
 483
 484   if (CopySrcSubreg != 0) {
 485     SwapVector[VecIdx].HasImplicitSubreg = 1;
 486     return CopySrcReg;
 487   }
 488
 489   return lookThruCopyLike(CopySrcReg, VecIdx);
 490 }
 491
 492 // Generate equivalence classes for related computations (webs) by
 493 // def-use relationships of virtual registers.  Mention of a physical
 494 // register terminates the generation of equivalence classes as this
 495 // indicates a use of a parameter, definition of a return value, use
 496 // of a value returned from a call, or definition of a parameter to a
 497 // call.  Computations with physical register mentions are flagged
 498 // as such so their containing webs will not be optimized.
 499 void PPCVSXSwapRemoval::formWebs() {
 500
 501   DEBUG(dbgs() << "\n*** Forming webs for swap removal ***\n\n");
 502
 503   for (unsigned EntryIdx = 0; EntryIdx < SwapVector.size(); ++EntryIdx) {
 504
 505     MachineInstr *MI = SwapVector[EntryIdx].VSEMI;
 506
 507     DEBUG(dbgs() << "\n" << SwapVector[EntryIdx].VSEId << " ");
 508     DEBUG(MI->dump());
 509
 510     // It's sufficient to walk vector uses and join them to their unique
 511     // definitions.  In addition, check *all* vector register operands
 512     // for physical regs.
 513     for (const MachineOperand &MO : MI->operands()) {
 514       if (!MO.isReg())
 515         continue;
 516
 517       unsigned Reg = MO.getReg();
 518       if (!isVecReg(Reg))
 519         continue;
 520
 521       if (!TargetRegisterInfo::isVirtualRegister(Reg)) {
 522         SwapVector[EntryIdx].MentionsPhysVR = 1;
 523         continue;
 524       }
 525
 526       if (!MO.isUse())
 527         continue;
 528
 529       MachineInstr* DefMI = MRI->getVRegDef(Reg);
 530       assert(SwapMap.find(DefMI) != SwapMap.end() &&
 531              "Inconsistency: def of vector reg not found in swap map!");
 532       int DefIdx = SwapMap[DefMI];
 533       (void)EC->unionSets(SwapVector[DefIdx].VSEId,
 534                           SwapVector[EntryIdx].VSEId);
 535
 536       DEBUG(dbgs() << format("Unioning %d with %d\n", SwapVector[DefIdx].VSEId,
 537                              SwapVector[EntryIdx].VSEId));
 538       DEBUG(dbgs() << "  Def: ");
 539       DEBUG(DefMI->dump());
 540     }
 541   }
 542 }
 543
 544 // Walk the swap vector entries looking for conditions that prevent their
 545 // containing computations from being optimized.  When such conditions are
 546 // found, mark the representative of the computation's equivalence class
 547 // as rejected.
 548 void PPCVSXSwapRemoval::recordUnoptimizableWebs() {
 549
 550   DEBUG(dbgs() << "\n*** Rejecting webs for swap removal ***\n\n");
 551
 552   for (unsigned EntryIdx = 0; EntryIdx < SwapVector.size(); ++EntryIdx) {
 553     int Repr = EC->getLeaderValue(SwapVector[EntryIdx].VSEId);
 554
 555     // Reject webs containing mentions of physical registers or implicit
 556     // subregs, or containing operations that we don't know how to handle
 557     // in a lane-permuted region.
 558     if (SwapVector[EntryIdx].MentionsPhysVR ||
 559         SwapVector[EntryIdx].HasImplicitSubreg ||
 560         !(SwapVector[EntryIdx].IsSwappable || SwapVector[EntryIdx].IsSwap)) {
 561
 562       SwapVector[Repr].WebRejected = 1;
 563
 564       DEBUG(dbgs() <<
 565             format("Web %d rejected for physreg, subreg, or not swap[pable]\n",
 566                    Repr));
 567       DEBUG(dbgs() << "  in " << EntryIdx << ": ");
 568       DEBUG(SwapVector[EntryIdx].VSEMI->dump());
 569       DEBUG(dbgs() << "\n");
 570     }
 571
 572     // Reject webs than contain swapping loads that feed something other
 573     // than a swap instruction.
 574     else if (SwapVector[EntryIdx].IsLoad && SwapVector[EntryIdx].IsSwap) {
 575       MachineInstr *MI = SwapVector[EntryIdx].VSEMI;
 576       unsigned DefReg = MI->getOperand(0).getReg();
 577
 578       // We skip debug instructions in the analysis.  (Note that debug
 579       // location information is still maintained by this optimization
 580       // because it remains on the LXVD2X and STXVD2X instructions after
 581       // the XXPERMDIs are removed.)
 582       for (MachineInstr &UseMI : MRI->use_nodbg_instructions(DefReg)) {
 583         int UseIdx = SwapMap[&UseMI];
 584
 585         if (!SwapVector[UseIdx].IsSwap || SwapVector[UseIdx].IsLoad ||
 586             SwapVector[UseIdx].IsStore) {
 587
 588           SwapVector[Repr].WebRejected = 1;
 589
 590           DEBUG(dbgs() <<
 591                 format("Web %d rejected for load not feeding swap\n", Repr));
 592           DEBUG(dbgs() << "  def " << EntryIdx << ": ");
 593           DEBUG(MI->dump());
 594           DEBUG(dbgs() << "  use " << UseIdx << ": ");
 595           DEBUG(UseMI.dump());
 596           DEBUG(dbgs() << "\n");
 597         }
 598       }
 599
 600     // Reject webs than contain swapping stores that are fed by something
 601     // other than a swap instruction.
 602     } else if (SwapVector[EntryIdx].IsStore && SwapVector[EntryIdx].IsSwap) {
 603       MachineInstr *MI = SwapVector[EntryIdx].VSEMI;
 604       unsigned UseReg = MI->getOperand(0).getReg();
 605       MachineInstr *DefMI = MRI->getVRegDef(UseReg);
 606       int DefIdx = SwapMap[DefMI];
 607
 608       if (!SwapVector[DefIdx].IsSwap || SwapVector[DefIdx].IsLoad ||
 609           SwapVector[DefIdx].IsStore) {
 610
 611         SwapVector[Repr].WebRejected = 1;
 612
 613         DEBUG(dbgs() <<
 614               format("Web %d rejected for store not fed by swap\n", Repr));
 615         DEBUG(dbgs() << "  def " << DefIdx << ": ");
 616         DEBUG(DefMI->dump());
 617         DEBUG(dbgs() << "  use " << EntryIdx << ": ");
 618         DEBUG(MI->dump());
 619         DEBUG(dbgs() << "\n");
 620       }
 621     }
 622   }
 623
 624   DEBUG(dbgs() << "Swap vector after web analysis:\n\n");
 625   dumpSwapVector();
 626 }
 627
 628 // Walk the swap vector entries looking for swaps fed by permuting loads
 629 // and swaps that feed permuting stores.  If the containing computation
 630 // has not been marked rejected, mark each such swap for removal.
 631 // (Removal is delayed in case optimization has disturbed the pattern,
 632 // such that multiple loads feed the same swap, etc.)
 633 void PPCVSXSwapRemoval::markSwapsForRemoval() {
 634
 635   DEBUG(dbgs() << "\n*** Marking swaps for removal ***\n\n");
 636
 637   for (unsigned EntryIdx = 0; EntryIdx < SwapVector.size(); ++EntryIdx) {
 638
 639     if (SwapVector[EntryIdx].IsLoad && SwapVector[EntryIdx].IsSwap) {
 640       int Repr = EC->getLeaderValue(SwapVector[EntryIdx].VSEId);
 641
 642       if (!SwapVector[Repr].WebRejected) {
 643         MachineInstr *MI = SwapVector[EntryIdx].VSEMI;
 644         unsigned DefReg = MI->getOperand(0).getReg();
 645
 646         for (MachineInstr &UseMI : MRI->use_nodbg_instructions(DefReg)) {
 647           int UseIdx = SwapMap[&UseMI];
 648           SwapVector[UseIdx].WillRemove = 1;
 649
 650           DEBUG(dbgs() << "Marking swap fed by load for removal: ");
 651           DEBUG(UseMI.dump());
 652         }
 653       }
 654
 655     } else if (SwapVector[EntryIdx].IsStore && SwapVector[EntryIdx].IsSwap) {
 656       int Repr = EC->getLeaderValue(SwapVector[EntryIdx].VSEId);
 657
 658       if (!SwapVector[Repr].WebRejected) {
 659         MachineInstr *MI = SwapVector[EntryIdx].VSEMI;
 660         unsigned UseReg = MI->getOperand(0).getReg();
 661         MachineInstr *DefMI = MRI->getVRegDef(UseReg);
 662         int DefIdx = SwapMap[DefMI];
 663         SwapVector[DefIdx].WillRemove = 1;
 664
 665         DEBUG(dbgs() << "Marking swap feeding store for removal: ");
 666         DEBUG(DefMI->dump());
 667       }
 668
 669     } else if (SwapVector[EntryIdx].IsSwappable &&
 670                SwapVector[EntryIdx].SpecialHandling != 0) {
 671       int Repr = EC->getLeaderValue(SwapVector[EntryIdx].VSEId);
 672
 673       if (!SwapVector[Repr].WebRejected)
 674         handleSpecialSwappables(EntryIdx);
 675     }
 676   }
 677 }
 678
 679 // The identified swap entry requires special handling to allow its
 680 // containing computation to be optimized.  Perform that handling
 681 // here.
 682 // FIXME: This code is to be phased in with subsequent patches.
 683 void PPCVSXSwapRemoval::handleSpecialSwappables(int EntryIdx) {
 684   switch (SwapVector[EntryIdx].SpecialHandling) {
 685
 686   default:
 687     assert(false && "Unexpected special handling type");
 688     break;
 689
 690   // For splats based on an index into a vector, add N/2 modulo N
 691   // to the index, where N is the number of vector elements.
 692   case SHValues::SH_SPLAT: {
 693     MachineInstr *MI = SwapVector[EntryIdx].VSEMI;
 694     unsigned NElts;
 695
 696     DEBUG(dbgs() << "Changing splat: ");
 697     DEBUG(MI->dump());
 698
 699     switch (MI->getOpcode()) {
 700     default:
 701       assert(false && "Unexpected splat opcode");
 702     case PPC::VSPLTB: NElts = 16; break;
 703     case PPC::VSPLTH: NElts = 8;  break;
 704     case PPC::VSPLTW: NElts = 4;  break;
 705     }
 706
 707     unsigned EltNo = MI->getOperand(1).getImm();
 708     EltNo = (EltNo + NElts / 2) % NElts;
 709     MI->getOperand(1).setImm(EltNo);
 710
 711     DEBUG(dbgs() << "  Into: ");
 712     DEBUG(MI->dump());
 713     break;
 714   }
 715
 716   }
 717 }
 718
 719 // Walk the swap vector and replace each entry marked for removal with
 720 // a copy operation.
 721 bool PPCVSXSwapRemoval::removeSwaps() {
 722
 723   DEBUG(dbgs() << "\n*** Removing swaps ***\n\n");
 724
 725   bool Changed = false;
 726
 727   for (unsigned EntryIdx = 0; EntryIdx < SwapVector.size(); ++EntryIdx) {
 728     if (SwapVector[EntryIdx].WillRemove) {
 729       Changed = true;
 730       MachineInstr *MI = SwapVector[EntryIdx].VSEMI;
 731       MachineBasicBlock *MBB = MI->getParent();
 732       BuildMI(*MBB, MI, MI->getDebugLoc(),
 733               TII->get(TargetOpcode::COPY), MI->getOperand(0).getReg())
 734         .addOperand(MI->getOperand(1));
 735
 736       DEBUG(dbgs() << format("Replaced %d with copy: ",
 737                              SwapVector[EntryIdx].VSEId));
 738       DEBUG(MI->dump());
 739
 740       MI->eraseFromParent();
 741     }
 742   }
 743
 744   return Changed;
 745 }
 746
 747 // For debug purposes, dump the contents of the swap vector.
 748 void PPCVSXSwapRemoval::dumpSwapVector() {
 749
 750   for (unsigned EntryIdx = 0; EntryIdx < SwapVector.size(); ++EntryIdx) {
 751
 752     MachineInstr *MI = SwapVector[EntryIdx].VSEMI;
 753     int ID = SwapVector[EntryIdx].VSEId;
 754
 755     DEBUG(dbgs() << format("%6d", ID));
 756     DEBUG(dbgs() << format("%6d", EC->getLeaderValue(ID)));
 757     DEBUG(dbgs() << format(" BB#%3d", MI->getParent()->getNumber()));
 758     DEBUG(dbgs() << format("  %14s  ", TII->getName(MI->getOpcode())));
 759
 760     if (SwapVector[EntryIdx].IsLoad)
 761       DEBUG(dbgs() << "load ");
 762     if (SwapVector[EntryIdx].IsStore)
 763       DEBUG(dbgs() << "store ");
 764     if (SwapVector[EntryIdx].IsSwap)
 765       DEBUG(dbgs() << "swap ");
 766     if (SwapVector[EntryIdx].MentionsPhysVR)
 767       DEBUG(dbgs() << "physreg ");
 768     if (SwapVector[EntryIdx].HasImplicitSubreg)
 769       DEBUG(dbgs() << "implsubreg ");
 770
 771     if (SwapVector[EntryIdx].IsSwappable) {
 772       DEBUG(dbgs() << "swappable ");
 773       switch(SwapVector[EntryIdx].SpecialHandling) {
 774       default:
 775         DEBUG(dbgs() << "special:**unknown**");
 776         break;
 777       case SH_NONE:
 778         break;
 779       case SH_EXTRACT:
 780         DEBUG(dbgs() << "special:extract ");
 781         break;
 782       case SH_INSERT:
 783         DEBUG(dbgs() << "special:insert ");
 784         break;
 785       case SH_NOSWAP_LD:
 786         DEBUG(dbgs() << "special:load ");
 787         break;
 788       case SH_NOSWAP_ST:
 789         DEBUG(dbgs() << "special:store ");
 790         break;
 791       case SH_SPLAT:
 792         DEBUG(dbgs() << "special:splat ");
 793         break;
 794       }
 795     }
 796
 797     if (SwapVector[EntryIdx].WebRejected)
 798       DEBUG(dbgs() << "rejected ");
 799     if (SwapVector[EntryIdx].WillRemove)
 800       DEBUG(dbgs() << "remove ");
 801
 802     DEBUG(dbgs() << "\n");
 803
 804     // For no-asserts builds.
 805     (void)MI;
 806     (void)ID;
 807   }
 808
 809   DEBUG(dbgs() << "\n");
 810 }
 811
 812 } // end default namespace
 813
 814 INITIALIZE_PASS_BEGIN(PPCVSXSwapRemoval, DEBUG_TYPE,
 815                       "PowerPC VSX Swap Removal", false, false)
 816 INITIALIZE_PASS_END(PPCVSXSwapRemoval, DEBUG_TYPE,
 817                     "PowerPC VSX Swap Removal", false, false)
 818
 819 char PPCVSXSwapRemoval::ID = 0;
 820 FunctionPass*
 821 llvm::createPPCVSXSwapRemovalPass() { return new PPCVSXSwapRemoval(); }