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 "PPC.h" 46 #include "PPCInstrBuilder.h" 47 #include "PPCInstrInfo.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/Config/llvm-config.h" 55 #include "llvm/Support/Debug.h" 56 #include "llvm/Support/Format.h" 57 #include "llvm/Support/raw_ostream.h" 58 59 using namespace llvm; 60 61 #define DEBUG_TYPE "ppc-vsx-swaps" 62 63 namespace llvm { 64 void initializePPCVSXSwapRemovalPass(PassRegistry&); 65 } 66 67 namespace { 68 69 // A PPCVSXSwapEntry is created for each machine instruction that 70 // is relevant to a vector computation. 71 struct PPCVSXSwapEntry { 72 // Pointer to the instruction. 73 MachineInstr *VSEMI; 74 75 // Unique ID (position in the swap vector). 76 int VSEId; 77 78 // Attributes of this node. 79 unsigned int IsLoad : 1; 80 unsigned int IsStore : 1; 81 unsigned int IsSwap : 1; 82 unsigned int MentionsPhysVR : 1; 83 unsigned int IsSwappable : 1; 84 unsigned int MentionsPartialVR : 1; 85 unsigned int SpecialHandling : 3; 86 unsigned int WebRejected : 1; 87 unsigned int WillRemove : 1; 88 }; 89 90 enum SHValues { 91 SH_NONE = 0, 92 SH_EXTRACT, 93 SH_INSERT, 94 SH_NOSWAP_LD, 95 SH_NOSWAP_ST, 96 SH_SPLAT, 97 SH_XXPERMDI, 98 SH_COPYWIDEN 99 }; 100 101 struct PPCVSXSwapRemoval : public MachineFunctionPass { 102 103 static char ID; 104 const PPCInstrInfo *TII; 105 MachineFunction *MF; 106 MachineRegisterInfo *MRI; 107 108 // Swap entries are allocated in a vector for better performance. 109 std::vector<PPCVSXSwapEntry> SwapVector; 110 111 // A mapping is maintained between machine instructions and 112 // their swap entries. The key is the address of the MI. 113 DenseMap<MachineInstr*, int> SwapMap; 114 115 // Equivalence classes are used to gather webs of related computation. 116 // Swap entries are represented by their VSEId fields. 117 EquivalenceClasses<int> *EC; 118 119 PPCVSXSwapRemoval() : MachineFunctionPass(ID) { 120 initializePPCVSXSwapRemovalPass(*PassRegistry::getPassRegistry()); 121 } 122 123 private: 124 // Initialize data structures. 125 void initialize(MachineFunction &MFParm); 126 127 // Walk the machine instructions to gather vector usage information. 128 // Return true iff vector mentions are present. 129 bool gatherVectorInstructions(); 130 131 // Add an entry to the swap vector and swap map. 132 int addSwapEntry(MachineInstr *MI, PPCVSXSwapEntry &SwapEntry); 133 134 // Hunt backwards through COPY and SUBREG_TO_REG chains for a 135 // source register. VecIdx indicates the swap vector entry to 136 // mark as mentioning a physical register if the search leads 137 // to one. 138 unsigned lookThruCopyLike(unsigned SrcReg, unsigned VecIdx); 139 140 // Generate equivalence classes for related computations (webs). 141 void formWebs(); 142 143 // Analyze webs and determine those that cannot be optimized. 144 void recordUnoptimizableWebs(); 145 146 // Record which swap instructions can be safely removed. 147 void markSwapsForRemoval(); 148 149 // Remove swaps and update other instructions requiring special 150 // handling. Return true iff any changes are made. 151 bool removeSwaps(); 152 153 // Insert a swap instruction from SrcReg to DstReg at the given 154 // InsertPoint. 155 void insertSwap(MachineInstr *MI, MachineBasicBlock::iterator InsertPoint, 156 unsigned DstReg, unsigned SrcReg); 157 158 // Update instructions requiring special handling. 159 void handleSpecialSwappables(int EntryIdx); 160 161 // Dump a description of the entries in the swap vector. 162 void dumpSwapVector(); 163 164 // Return true iff the given register is in the given class. 165 bool isRegInClass(unsigned Reg, const TargetRegisterClass *RC) { 166 if (TargetRegisterInfo::isVirtualRegister(Reg)) 167 return RC->hasSubClassEq(MRI->getRegClass(Reg)); 168 return RC->contains(Reg); 169 } 170 171 // Return true iff the given register is a full vector register. 172 bool isVecReg(unsigned Reg) { 173 return (isRegInClass(Reg, &PPC::VSRCRegClass) || 174 isRegInClass(Reg, &PPC::VRRCRegClass)); 175 } 176 177 // Return true iff the given register is a partial vector register. 178 bool isScalarVecReg(unsigned Reg) { 179 return (isRegInClass(Reg, &PPC::VSFRCRegClass) || 180 isRegInClass(Reg, &PPC::VSSRCRegClass)); 181 } 182 183 // Return true iff the given register mentions all or part of a 184 // vector register. Also sets Partial to true if the mention 185 // is for just the floating-point register overlap of the register. 186 bool isAnyVecReg(unsigned Reg, bool &Partial) { 187 if (isScalarVecReg(Reg)) 188 Partial = true; 189 return isScalarVecReg(Reg) || isVecReg(Reg); 190 } 191 192 public: 193 // Main entry point for this pass. 194 bool runOnMachineFunction(MachineFunction &MF) override { 195 if (skipFunction(MF.getFunction())) 196 return false; 197 198 // If we don't have VSX on the subtarget, don't do anything. 199 // Also, on Power 9 the load and store ops preserve element order and so 200 // the swaps are not required. 201 const PPCSubtarget &STI = MF.getSubtarget<PPCSubtarget>(); 202 if (!STI.hasVSX() || !STI.needsSwapsForVSXMemOps()) 203 return false; 204 205 bool Changed = false; 206 initialize(MF); 207 208 if (gatherVectorInstructions()) { 209 formWebs(); 210 recordUnoptimizableWebs(); 211 markSwapsForRemoval(); 212 Changed = removeSwaps(); 213 } 214 215 // FIXME: See the allocation of EC in initialize(). 216 delete EC; 217 return Changed; 218 } 219 }; 220 221 // Initialize data structures for this pass. In particular, clear the 222 // swap vector and allocate the equivalence class mapping before 223 // processing each function. 224 void PPCVSXSwapRemoval::initialize(MachineFunction &MFParm) { 225 MF = &MFParm; 226 MRI = &MF->getRegInfo(); 227 TII = MF->getSubtarget<PPCSubtarget>().getInstrInfo(); 228 229 // An initial vector size of 256 appears to work well in practice. 230 // Small/medium functions with vector content tend not to incur a 231 // reallocation at this size. Three of the vector tests in 232 // projects/test-suite reallocate, which seems like a reasonable rate. 233 const int InitialVectorSize(256); 234 SwapVector.clear(); 235 SwapVector.reserve(InitialVectorSize); 236 237 // FIXME: Currently we allocate EC each time because we don't have 238 // access to the set representation on which to call clear(). Should 239 // consider adding a clear() method to the EquivalenceClasses class. 240 EC = new EquivalenceClasses<int>; 241 } 242 243 // Create an entry in the swap vector for each instruction that mentions 244 // a full vector register, recording various characteristics of the 245 // instructions there. 246 bool PPCVSXSwapRemoval::gatherVectorInstructions() { 247 bool RelevantFunction = false; 248 249 for (MachineBasicBlock &MBB : *MF) { 250 for (MachineInstr &MI : MBB) { 251 252 if (MI.isDebugInstr()) 253 continue; 254 255 bool RelevantInstr = false; 256 bool Partial = false; 257 258 for (const MachineOperand &MO : MI.operands()) { 259 if (!MO.isReg()) 260 continue; 261 unsigned Reg = MO.getReg(); 262 if (isAnyVecReg(Reg, Partial)) { 263 RelevantInstr = true; 264 break; 265 } 266 } 267 268 if (!RelevantInstr) 269 continue; 270 271 RelevantFunction = true; 272 273 // Create a SwapEntry initialized to zeros, then fill in the 274 // instruction and ID fields before pushing it to the back 275 // of the swap vector. 276 PPCVSXSwapEntry SwapEntry{}; 277 int VecIdx = addSwapEntry(&MI, SwapEntry); 278 279 switch(MI.getOpcode()) { 280 default: 281 // Unless noted otherwise, an instruction is considered 282 // safe for the optimization. There are a large number of 283 // such true-SIMD instructions (all vector math, logical, 284 // select, compare, etc.). However, if the instruction 285 // mentions a partial vector register and does not have 286 // special handling defined, it is not swappable. 287 if (Partial) 288 SwapVector[VecIdx].MentionsPartialVR = 1; 289 else 290 SwapVector[VecIdx].IsSwappable = 1; 291 break; 292 case PPC::XXPERMDI: { 293 // This is a swap if it is of the form XXPERMDI t, s, s, 2. 294 // Unfortunately, MachineCSE ignores COPY and SUBREG_TO_REG, so we 295 // can also see XXPERMDI t, SUBREG_TO_REG(s), SUBREG_TO_REG(s), 2, 296 // for example. We have to look through chains of COPY and 297 // SUBREG_TO_REG to find the real source value for comparison. 298 // If the real source value is a physical register, then mark the 299 // XXPERMDI as mentioning a physical register. 300 int immed = MI.getOperand(3).getImm(); 301 if (immed == 2) { 302 unsigned trueReg1 = lookThruCopyLike(MI.getOperand(1).getReg(), 303 VecIdx); 304 unsigned trueReg2 = lookThruCopyLike(MI.getOperand(2).getReg(), 305 VecIdx); 306 if (trueReg1 == trueReg2) 307 SwapVector[VecIdx].IsSwap = 1; 308 else { 309 // We can still handle these if the two registers are not 310 // identical, by adjusting the form of the XXPERMDI. 311 SwapVector[VecIdx].IsSwappable = 1; 312 SwapVector[VecIdx].SpecialHandling = SHValues::SH_XXPERMDI; 313 } 314 // This is a doubleword splat if it is of the form 315 // XXPERMDI t, s, s, 0 or XXPERMDI t, s, s, 3. As above we 316 // must look through chains of copy-likes to find the source 317 // register. We turn off the marking for mention of a physical 318 // register, because splatting it is safe; the optimization 319 // will not swap the value in the physical register. Whether 320 // or not the two input registers are identical, we can handle 321 // these by adjusting the form of the XXPERMDI. 322 } else if (immed == 0 || immed == 3) { 323 324 SwapVector[VecIdx].IsSwappable = 1; 325 SwapVector[VecIdx].SpecialHandling = SHValues::SH_XXPERMDI; 326 327 unsigned trueReg1 = lookThruCopyLike(MI.getOperand(1).getReg(), 328 VecIdx); 329 unsigned trueReg2 = lookThruCopyLike(MI.getOperand(2).getReg(), 330 VecIdx); 331 if (trueReg1 == trueReg2) 332 SwapVector[VecIdx].MentionsPhysVR = 0; 333 334 } else { 335 // We can still handle these by adjusting the form of the XXPERMDI. 336 SwapVector[VecIdx].IsSwappable = 1; 337 SwapVector[VecIdx].SpecialHandling = SHValues::SH_XXPERMDI; 338 } 339 break; 340 } 341 case PPC::LVX: 342 // Non-permuting loads are currently unsafe. We can use special 343 // handling for this in the future. By not marking these as 344 // IsSwap, we ensure computations containing them will be rejected 345 // for now. 346 SwapVector[VecIdx].IsLoad = 1; 347 break; 348 case PPC::LXVD2X: 349 case PPC::LXVW4X: 350 // Permuting loads are marked as both load and swap, and are 351 // safe for optimization. 352 SwapVector[VecIdx].IsLoad = 1; 353 SwapVector[VecIdx].IsSwap = 1; 354 break; 355 case PPC::LXSDX: 356 case PPC::LXSSPX: 357 case PPC::XFLOADf64: 358 case PPC::XFLOADf32: 359 // A load of a floating-point value into the high-order half of 360 // a vector register is safe, provided that we introduce a swap 361 // following the load, which will be done by the SUBREG_TO_REG 362 // support. So just mark these as safe. 363 SwapVector[VecIdx].IsLoad = 1; 364 SwapVector[VecIdx].IsSwappable = 1; 365 break; 366 case PPC::STVX: 367 // Non-permuting stores are currently unsafe. We can use special 368 // handling for this in the future. By not marking these as 369 // IsSwap, we ensure computations containing them will be rejected 370 // for now. 371 SwapVector[VecIdx].IsStore = 1; 372 break; 373 case PPC::STXVD2X: 374 case PPC::STXVW4X: 375 // Permuting stores are marked as both store and swap, and are 376 // safe for optimization. 377 SwapVector[VecIdx].IsStore = 1; 378 SwapVector[VecIdx].IsSwap = 1; 379 break; 380 case PPC::COPY: 381 // These are fine provided they are moving between full vector 382 // register classes. 383 if (isVecReg(MI.getOperand(0).getReg()) && 384 isVecReg(MI.getOperand(1).getReg())) 385 SwapVector[VecIdx].IsSwappable = 1; 386 // If we have a copy from one scalar floating-point register 387 // to another, we can accept this even if it is a physical 388 // register. The only way this gets involved is if it feeds 389 // a SUBREG_TO_REG, which is handled by introducing a swap. 390 else if (isScalarVecReg(MI.getOperand(0).getReg()) && 391 isScalarVecReg(MI.getOperand(1).getReg())) 392 SwapVector[VecIdx].IsSwappable = 1; 393 break; 394 case PPC::SUBREG_TO_REG: { 395 // These are fine provided they are moving between full vector 396 // register classes. If they are moving from a scalar 397 // floating-point class to a vector class, we can handle those 398 // as well, provided we introduce a swap. It is generally the 399 // case that we will introduce fewer swaps than we remove, but 400 // (FIXME) a cost model could be used. However, introduced 401 // swaps could potentially be CSEd, so this is not trivial. 402 if (isVecReg(MI.getOperand(0).getReg()) && 403 isVecReg(MI.getOperand(2).getReg())) 404 SwapVector[VecIdx].IsSwappable = 1; 405 else if (isVecReg(MI.getOperand(0).getReg()) && 406 isScalarVecReg(MI.getOperand(2).getReg())) { 407 SwapVector[VecIdx].IsSwappable = 1; 408 SwapVector[VecIdx].SpecialHandling = SHValues::SH_COPYWIDEN; 409 } 410 break; 411 } 412 case PPC::VSPLTB: 413 case PPC::VSPLTH: 414 case PPC::VSPLTW: 415 case PPC::XXSPLTW: 416 // Splats are lane-sensitive, but we can use special handling 417 // to adjust the source lane for the splat. 418 SwapVector[VecIdx].IsSwappable = 1; 419 SwapVector[VecIdx].SpecialHandling = SHValues::SH_SPLAT; 420 break; 421 // The presence of the following lane-sensitive operations in a 422 // web will kill the optimization, at least for now. For these 423 // we do nothing, causing the optimization to fail. 424 // FIXME: Some of these could be permitted with special handling, 425 // and will be phased in as time permits. 426 // FIXME: There is no simple and maintainable way to express a set 427 // of opcodes having a common attribute in TableGen. Should this 428 // change, this is a prime candidate to use such a mechanism. 429 case PPC::INLINEASM: 430 case PPC::EXTRACT_SUBREG: 431 case PPC::INSERT_SUBREG: 432 case PPC::COPY_TO_REGCLASS: 433 case PPC::LVEBX: 434 case PPC::LVEHX: 435 case PPC::LVEWX: 436 case PPC::LVSL: 437 case PPC::LVSR: 438 case PPC::LVXL: 439 case PPC::STVEBX: 440 case PPC::STVEHX: 441 case PPC::STVEWX: 442 case PPC::STVXL: 443 // We can handle STXSDX and STXSSPX similarly to LXSDX and LXSSPX, 444 // by adding special handling for narrowing copies as well as 445 // widening ones. However, I've experimented with this, and in 446 // practice we currently do not appear to use STXSDX fed by 447 // a narrowing copy from a full vector register. Since I can't 448 // generate any useful test cases, I've left this alone for now. 449 case PPC::STXSDX: 450 case PPC::STXSSPX: 451 case PPC::VCIPHER: 452 case PPC::VCIPHERLAST: 453 case PPC::VMRGHB: 454 case PPC::VMRGHH: 455 case PPC::VMRGHW: 456 case PPC::VMRGLB: 457 case PPC::VMRGLH: 458 case PPC::VMRGLW: 459 case PPC::VMULESB: 460 case PPC::VMULESH: 461 case PPC::VMULESW: 462 case PPC::VMULEUB: 463 case PPC::VMULEUH: 464 case PPC::VMULEUW: 465 case PPC::VMULOSB: 466 case PPC::VMULOSH: 467 case PPC::VMULOSW: 468 case PPC::VMULOUB: 469 case PPC::VMULOUH: 470 case PPC::VMULOUW: 471 case PPC::VNCIPHER: 472 case PPC::VNCIPHERLAST: 473 case PPC::VPERM: 474 case PPC::VPERMXOR: 475 case PPC::VPKPX: 476 case PPC::VPKSHSS: 477 case PPC::VPKSHUS: 478 case PPC::VPKSDSS: 479 case PPC::VPKSDUS: 480 case PPC::VPKSWSS: 481 case PPC::VPKSWUS: 482 case PPC::VPKUDUM: 483 case PPC::VPKUDUS: 484 case PPC::VPKUHUM: 485 case PPC::VPKUHUS: 486 case PPC::VPKUWUM: 487 case PPC::VPKUWUS: 488 case PPC::VPMSUMB: 489 case PPC::VPMSUMD: 490 case PPC::VPMSUMH: 491 case PPC::VPMSUMW: 492 case PPC::VRLB: 493 case PPC::VRLD: 494 case PPC::VRLH: 495 case PPC::VRLW: 496 case PPC::VSBOX: 497 case PPC::VSHASIGMAD: 498 case PPC::VSHASIGMAW: 499 case PPC::VSL: 500 case PPC::VSLDOI: 501 case PPC::VSLO: 502 case PPC::VSR: 503 case PPC::VSRO: 504 case PPC::VSUM2SWS: 505 case PPC::VSUM4SBS: 506 case PPC::VSUM4SHS: 507 case PPC::VSUM4UBS: 508 case PPC::VSUMSWS: 509 case PPC::VUPKHPX: 510 case PPC::VUPKHSB: 511 case PPC::VUPKHSH: 512 case PPC::VUPKHSW: 513 case PPC::VUPKLPX: 514 case PPC::VUPKLSB: 515 case PPC::VUPKLSH: 516 case PPC::VUPKLSW: 517 case PPC::XXMRGHW: 518 case PPC::XXMRGLW: 519 // XXSLDWI could be replaced by a general permute with one of three 520 // permute control vectors (for shift values 1, 2, 3). However, 521 // VPERM has a more restrictive register class. 522 case PPC::XXSLDWI: 523 case PPC::XSCVDPSPN: 524 case PPC::XSCVSPDPN: 525 break; 526 } 527 } 528 } 529 530 if (RelevantFunction) { 531 LLVM_DEBUG(dbgs() << "Swap vector when first built\n\n"); 532 LLVM_DEBUG(dumpSwapVector()); 533 } 534 535 return RelevantFunction; 536 } 537 538 // Add an entry to the swap vector and swap map, and make a 539 // singleton equivalence class for the entry. 540 int PPCVSXSwapRemoval::addSwapEntry(MachineInstr *MI, 541 PPCVSXSwapEntry& SwapEntry) { 542 SwapEntry.VSEMI = MI; 543 SwapEntry.VSEId = SwapVector.size(); 544 SwapVector.push_back(SwapEntry); 545 EC->insert(SwapEntry.VSEId); 546 SwapMap[MI] = SwapEntry.VSEId; 547 return SwapEntry.VSEId; 548 } 549 550 // This is used to find the "true" source register for an 551 // XXPERMDI instruction, since MachineCSE does not handle the 552 // "copy-like" operations (Copy and SubregToReg). Returns 553 // the original SrcReg unless it is the target of a copy-like 554 // operation, in which case we chain backwards through all 555 // such operations to the ultimate source register. If a 556 // physical register is encountered, we stop the search and 557 // flag the swap entry indicated by VecIdx (the original 558 // XXPERMDI) as mentioning a physical register. 559 unsigned PPCVSXSwapRemoval::lookThruCopyLike(unsigned SrcReg, 560 unsigned VecIdx) { 561 MachineInstr *MI = MRI->getVRegDef(SrcReg); 562 if (!MI->isCopyLike()) 563 return SrcReg; 564 565 unsigned CopySrcReg; 566 if (MI->isCopy()) 567 CopySrcReg = MI->getOperand(1).getReg(); 568 else { 569 assert(MI->isSubregToReg() && "bad opcode for lookThruCopyLike"); 570 CopySrcReg = MI->getOperand(2).getReg(); 571 } 572 573 if (!TargetRegisterInfo::isVirtualRegister(CopySrcReg)) { 574 if (!isScalarVecReg(CopySrcReg)) 575 SwapVector[VecIdx].MentionsPhysVR = 1; 576 return CopySrcReg; 577 } 578 579 return lookThruCopyLike(CopySrcReg, VecIdx); 580 } 581 582 // Generate equivalence classes for related computations (webs) by 583 // def-use relationships of virtual registers. Mention of a physical 584 // register terminates the generation of equivalence classes as this 585 // indicates a use of a parameter, definition of a return value, use 586 // of a value returned from a call, or definition of a parameter to a 587 // call. Computations with physical register mentions are flagged 588 // as such so their containing webs will not be optimized. 589 void PPCVSXSwapRemoval::formWebs() { 590 591 LLVM_DEBUG(dbgs() << "\n*** Forming webs for swap removal ***\n\n"); 592 593 for (unsigned EntryIdx = 0; EntryIdx < SwapVector.size(); ++EntryIdx) { 594 595 MachineInstr *MI = SwapVector[EntryIdx].VSEMI; 596 597 LLVM_DEBUG(dbgs() << "\n" << SwapVector[EntryIdx].VSEId << " "); 598 LLVM_DEBUG(MI->dump()); 599 600 // It's sufficient to walk vector uses and join them to their unique 601 // definitions. In addition, check full vector register operands 602 // for physical regs. We exclude partial-vector register operands 603 // because we can handle them if copied to a full vector. 604 for (const MachineOperand &MO : MI->operands()) { 605 if (!MO.isReg()) 606 continue; 607 608 unsigned Reg = MO.getReg(); 609 if (!isVecReg(Reg) && !isScalarVecReg(Reg)) 610 continue; 611 612 if (!TargetRegisterInfo::isVirtualRegister(Reg)) { 613 if (!(MI->isCopy() && isScalarVecReg(Reg))) 614 SwapVector[EntryIdx].MentionsPhysVR = 1; 615 continue; 616 } 617 618 if (!MO.isUse()) 619 continue; 620 621 MachineInstr* DefMI = MRI->getVRegDef(Reg); 622 assert(SwapMap.find(DefMI) != SwapMap.end() && 623 "Inconsistency: def of vector reg not found in swap map!"); 624 int DefIdx = SwapMap[DefMI]; 625 (void)EC->unionSets(SwapVector[DefIdx].VSEId, 626 SwapVector[EntryIdx].VSEId); 627 628 LLVM_DEBUG(dbgs() << format("Unioning %d with %d\n", 629 SwapVector[DefIdx].VSEId, 630 SwapVector[EntryIdx].VSEId)); 631 LLVM_DEBUG(dbgs() << " Def: "); 632 LLVM_DEBUG(DefMI->dump()); 633 } 634 } 635 } 636 637 // Walk the swap vector entries looking for conditions that prevent their 638 // containing computations from being optimized. When such conditions are 639 // found, mark the representative of the computation's equivalence class 640 // as rejected. 641 void PPCVSXSwapRemoval::recordUnoptimizableWebs() { 642 643 LLVM_DEBUG(dbgs() << "\n*** Rejecting webs for swap removal ***\n\n"); 644 645 for (unsigned EntryIdx = 0; EntryIdx < SwapVector.size(); ++EntryIdx) { 646 int Repr = EC->getLeaderValue(SwapVector[EntryIdx].VSEId); 647 648 // If representative is already rejected, don't waste further time. 649 if (SwapVector[Repr].WebRejected) 650 continue; 651 652 // Reject webs containing mentions of physical or partial registers, or 653 // containing operations that we don't know how to handle in a lane- 654 // permuted region. 655 if (SwapVector[EntryIdx].MentionsPhysVR || 656 SwapVector[EntryIdx].MentionsPartialVR || 657 !(SwapVector[EntryIdx].IsSwappable || SwapVector[EntryIdx].IsSwap)) { 658 659 SwapVector[Repr].WebRejected = 1; 660 661 LLVM_DEBUG( 662 dbgs() << format("Web %d rejected for physreg, partial reg, or not " 663 "swap[pable]\n", 664 Repr)); 665 LLVM_DEBUG(dbgs() << " in " << EntryIdx << ": "); 666 LLVM_DEBUG(SwapVector[EntryIdx].VSEMI->dump()); 667 LLVM_DEBUG(dbgs() << "\n"); 668 } 669 670 // Reject webs than contain swapping loads that feed something other 671 // than a swap instruction. 672 else if (SwapVector[EntryIdx].IsLoad && SwapVector[EntryIdx].IsSwap) { 673 MachineInstr *MI = SwapVector[EntryIdx].VSEMI; 674 unsigned DefReg = MI->getOperand(0).getReg(); 675 676 // We skip debug instructions in the analysis. (Note that debug 677 // location information is still maintained by this optimization 678 // because it remains on the LXVD2X and STXVD2X instructions after 679 // the XXPERMDIs are removed.) 680 for (MachineInstr &UseMI : MRI->use_nodbg_instructions(DefReg)) { 681 int UseIdx = SwapMap[&UseMI]; 682 683 if (!SwapVector[UseIdx].IsSwap || SwapVector[UseIdx].IsLoad || 684 SwapVector[UseIdx].IsStore) { 685 686 SwapVector[Repr].WebRejected = 1; 687 688 LLVM_DEBUG(dbgs() << format( 689 "Web %d rejected for load not feeding swap\n", Repr)); 690 LLVM_DEBUG(dbgs() << " def " << EntryIdx << ": "); 691 LLVM_DEBUG(MI->dump()); 692 LLVM_DEBUG(dbgs() << " use " << UseIdx << ": "); 693 LLVM_DEBUG(UseMI.dump()); 694 LLVM_DEBUG(dbgs() << "\n"); 695 } 696 } 697 698 // Reject webs that contain swapping stores that are fed by something 699 // other than a swap instruction. 700 } else if (SwapVector[EntryIdx].IsStore && SwapVector[EntryIdx].IsSwap) { 701 MachineInstr *MI = SwapVector[EntryIdx].VSEMI; 702 unsigned UseReg = MI->getOperand(0).getReg(); 703 MachineInstr *DefMI = MRI->getVRegDef(UseReg); 704 unsigned DefReg = DefMI->getOperand(0).getReg(); 705 int DefIdx = SwapMap[DefMI]; 706 707 if (!SwapVector[DefIdx].IsSwap || SwapVector[DefIdx].IsLoad || 708 SwapVector[DefIdx].IsStore) { 709 710 SwapVector[Repr].WebRejected = 1; 711 712 LLVM_DEBUG(dbgs() << format( 713 "Web %d rejected for store not fed by swap\n", Repr)); 714 LLVM_DEBUG(dbgs() << " def " << DefIdx << ": "); 715 LLVM_DEBUG(DefMI->dump()); 716 LLVM_DEBUG(dbgs() << " use " << EntryIdx << ": "); 717 LLVM_DEBUG(MI->dump()); 718 LLVM_DEBUG(dbgs() << "\n"); 719 } 720 721 // Ensure all uses of the register defined by DefMI feed store 722 // instructions 723 for (MachineInstr &UseMI : MRI->use_nodbg_instructions(DefReg)) { 724 int UseIdx = SwapMap[&UseMI]; 725 726 if (SwapVector[UseIdx].VSEMI->getOpcode() != MI->getOpcode()) { 727 SwapVector[Repr].WebRejected = 1; 728 729 LLVM_DEBUG( 730 dbgs() << format( 731 "Web %d rejected for swap not feeding only stores\n", Repr)); 732 LLVM_DEBUG(dbgs() << " def " 733 << " : "); 734 LLVM_DEBUG(DefMI->dump()); 735 LLVM_DEBUG(dbgs() << " use " << UseIdx << ": "); 736 LLVM_DEBUG(SwapVector[UseIdx].VSEMI->dump()); 737 LLVM_DEBUG(dbgs() << "\n"); 738 } 739 } 740 } 741 } 742 743 LLVM_DEBUG(dbgs() << "Swap vector after web analysis:\n\n"); 744 LLVM_DEBUG(dumpSwapVector()); 745 } 746 747 // Walk the swap vector entries looking for swaps fed by permuting loads 748 // and swaps that feed permuting stores. If the containing computation 749 // has not been marked rejected, mark each such swap for removal. 750 // (Removal is delayed in case optimization has disturbed the pattern, 751 // such that multiple loads feed the same swap, etc.) 752 void PPCVSXSwapRemoval::markSwapsForRemoval() { 753 754 LLVM_DEBUG(dbgs() << "\n*** Marking swaps for removal ***\n\n"); 755 756 for (unsigned EntryIdx = 0; EntryIdx < SwapVector.size(); ++EntryIdx) { 757 758 if (SwapVector[EntryIdx].IsLoad && SwapVector[EntryIdx].IsSwap) { 759 int Repr = EC->getLeaderValue(SwapVector[EntryIdx].VSEId); 760 761 if (!SwapVector[Repr].WebRejected) { 762 MachineInstr *MI = SwapVector[EntryIdx].VSEMI; 763 unsigned DefReg = MI->getOperand(0).getReg(); 764 765 for (MachineInstr &UseMI : MRI->use_nodbg_instructions(DefReg)) { 766 int UseIdx = SwapMap[&UseMI]; 767 SwapVector[UseIdx].WillRemove = 1; 768 769 LLVM_DEBUG(dbgs() << "Marking swap fed by load for removal: "); 770 LLVM_DEBUG(UseMI.dump()); 771 } 772 } 773 774 } else if (SwapVector[EntryIdx].IsStore && SwapVector[EntryIdx].IsSwap) { 775 int Repr = EC->getLeaderValue(SwapVector[EntryIdx].VSEId); 776 777 if (!SwapVector[Repr].WebRejected) { 778 MachineInstr *MI = SwapVector[EntryIdx].VSEMI; 779 unsigned UseReg = MI->getOperand(0).getReg(); 780 MachineInstr *DefMI = MRI->getVRegDef(UseReg); 781 int DefIdx = SwapMap[DefMI]; 782 SwapVector[DefIdx].WillRemove = 1; 783 784 LLVM_DEBUG(dbgs() << "Marking swap feeding store for removal: "); 785 LLVM_DEBUG(DefMI->dump()); 786 } 787 788 } else if (SwapVector[EntryIdx].IsSwappable && 789 SwapVector[EntryIdx].SpecialHandling != 0) { 790 int Repr = EC->getLeaderValue(SwapVector[EntryIdx].VSEId); 791 792 if (!SwapVector[Repr].WebRejected) 793 handleSpecialSwappables(EntryIdx); 794 } 795 } 796 } 797 798 // Create an xxswapd instruction and insert it prior to the given point. 799 // MI is used to determine basic block and debug loc information. 800 // FIXME: When inserting a swap, we should check whether SrcReg is 801 // defined by another swap: SrcReg = XXPERMDI Reg, Reg, 2; If so, 802 // then instead we should generate a copy from Reg to DstReg. 803 void PPCVSXSwapRemoval::insertSwap(MachineInstr *MI, 804 MachineBasicBlock::iterator InsertPoint, 805 unsigned DstReg, unsigned SrcReg) { 806 BuildMI(*MI->getParent(), InsertPoint, MI->getDebugLoc(), 807 TII->get(PPC::XXPERMDI), DstReg) 808 .addReg(SrcReg) 809 .addReg(SrcReg) 810 .addImm(2); 811 } 812 813 // The identified swap entry requires special handling to allow its 814 // containing computation to be optimized. Perform that handling 815 // here. 816 // FIXME: Additional opportunities will be phased in with subsequent 817 // patches. 818 void PPCVSXSwapRemoval::handleSpecialSwappables(int EntryIdx) { 819 switch (SwapVector[EntryIdx].SpecialHandling) { 820 821 default: 822 llvm_unreachable("Unexpected special handling type"); 823 824 // For splats based on an index into a vector, add N/2 modulo N 825 // to the index, where N is the number of vector elements. 826 case SHValues::SH_SPLAT: { 827 MachineInstr *MI = SwapVector[EntryIdx].VSEMI; 828 unsigned NElts; 829 830 LLVM_DEBUG(dbgs() << "Changing splat: "); 831 LLVM_DEBUG(MI->dump()); 832 833 switch (MI->getOpcode()) { 834 default: 835 llvm_unreachable("Unexpected splat opcode"); 836 case PPC::VSPLTB: NElts = 16; break; 837 case PPC::VSPLTH: NElts = 8; break; 838 case PPC::VSPLTW: 839 case PPC::XXSPLTW: NElts = 4; break; 840 } 841 842 unsigned EltNo; 843 if (MI->getOpcode() == PPC::XXSPLTW) 844 EltNo = MI->getOperand(2).getImm(); 845 else 846 EltNo = MI->getOperand(1).getImm(); 847 848 EltNo = (EltNo + NElts / 2) % NElts; 849 if (MI->getOpcode() == PPC::XXSPLTW) 850 MI->getOperand(2).setImm(EltNo); 851 else 852 MI->getOperand(1).setImm(EltNo); 853 854 LLVM_DEBUG(dbgs() << " Into: "); 855 LLVM_DEBUG(MI->dump()); 856 break; 857 } 858 859 // For an XXPERMDI that isn't handled otherwise, we need to 860 // reverse the order of the operands. If the selector operand 861 // has a value of 0 or 3, we need to change it to 3 or 0, 862 // respectively. Otherwise we should leave it alone. (This 863 // is equivalent to reversing the two bits of the selector 864 // operand and complementing the result.) 865 case SHValues::SH_XXPERMDI: { 866 MachineInstr *MI = SwapVector[EntryIdx].VSEMI; 867 868 LLVM_DEBUG(dbgs() << "Changing XXPERMDI: "); 869 LLVM_DEBUG(MI->dump()); 870 871 unsigned Selector = MI->getOperand(3).getImm(); 872 if (Selector == 0 || Selector == 3) 873 Selector = 3 - Selector; 874 MI->getOperand(3).setImm(Selector); 875 876 unsigned Reg1 = MI->getOperand(1).getReg(); 877 unsigned Reg2 = MI->getOperand(2).getReg(); 878 MI->getOperand(1).setReg(Reg2); 879 MI->getOperand(2).setReg(Reg1); 880 881 // We also need to swap kill flag associated with the register. 882 bool IsKill1 = MI->getOperand(1).isKill(); 883 bool IsKill2 = MI->getOperand(2).isKill(); 884 MI->getOperand(1).setIsKill(IsKill2); 885 MI->getOperand(2).setIsKill(IsKill1); 886 887 LLVM_DEBUG(dbgs() << " Into: "); 888 LLVM_DEBUG(MI->dump()); 889 break; 890 } 891 892 // For a copy from a scalar floating-point register to a vector 893 // register, removing swaps will leave the copied value in the 894 // wrong lane. Insert a swap following the copy to fix this. 895 case SHValues::SH_COPYWIDEN: { 896 MachineInstr *MI = SwapVector[EntryIdx].VSEMI; 897 898 LLVM_DEBUG(dbgs() << "Changing SUBREG_TO_REG: "); 899 LLVM_DEBUG(MI->dump()); 900 901 unsigned DstReg = MI->getOperand(0).getReg(); 902 const TargetRegisterClass *DstRC = MRI->getRegClass(DstReg); 903 unsigned NewVReg = MRI->createVirtualRegister(DstRC); 904 905 MI->getOperand(0).setReg(NewVReg); 906 LLVM_DEBUG(dbgs() << " Into: "); 907 LLVM_DEBUG(MI->dump()); 908 909 auto InsertPoint = ++MachineBasicBlock::iterator(MI); 910 911 // Note that an XXPERMDI requires a VSRC, so if the SUBREG_TO_REG 912 // is copying to a VRRC, we need to be careful to avoid a register 913 // assignment problem. In this case we must copy from VRRC to VSRC 914 // prior to the swap, and from VSRC to VRRC following the swap. 915 // Coalescing will usually remove all this mess. 916 if (DstRC == &PPC::VRRCRegClass) { 917 unsigned VSRCTmp1 = MRI->createVirtualRegister(&PPC::VSRCRegClass); 918 unsigned VSRCTmp2 = MRI->createVirtualRegister(&PPC::VSRCRegClass); 919 920 BuildMI(*MI->getParent(), InsertPoint, MI->getDebugLoc(), 921 TII->get(PPC::COPY), VSRCTmp1) 922 .addReg(NewVReg); 923 LLVM_DEBUG(std::prev(InsertPoint)->dump()); 924 925 insertSwap(MI, InsertPoint, VSRCTmp2, VSRCTmp1); 926 LLVM_DEBUG(std::prev(InsertPoint)->dump()); 927 928 BuildMI(*MI->getParent(), InsertPoint, MI->getDebugLoc(), 929 TII->get(PPC::COPY), DstReg) 930 .addReg(VSRCTmp2); 931 LLVM_DEBUG(std::prev(InsertPoint)->dump()); 932 933 } else { 934 insertSwap(MI, InsertPoint, DstReg, NewVReg); 935 LLVM_DEBUG(std::prev(InsertPoint)->dump()); 936 } 937 break; 938 } 939 } 940 } 941 942 // Walk the swap vector and replace each entry marked for removal with 943 // a copy operation. 944 bool PPCVSXSwapRemoval::removeSwaps() { 945 946 LLVM_DEBUG(dbgs() << "\n*** Removing swaps ***\n\n"); 947 948 bool Changed = false; 949 950 for (unsigned EntryIdx = 0; EntryIdx < SwapVector.size(); ++EntryIdx) { 951 if (SwapVector[EntryIdx].WillRemove) { 952 Changed = true; 953 MachineInstr *MI = SwapVector[EntryIdx].VSEMI; 954 MachineBasicBlock *MBB = MI->getParent(); 955 BuildMI(*MBB, MI, MI->getDebugLoc(), TII->get(TargetOpcode::COPY), 956 MI->getOperand(0).getReg()) 957 .add(MI->getOperand(1)); 958 959 LLVM_DEBUG(dbgs() << format("Replaced %d with copy: ", 960 SwapVector[EntryIdx].VSEId)); 961 LLVM_DEBUG(MI->dump()); 962 963 MI->eraseFromParent(); 964 } 965 } 966 967 return Changed; 968 } 969 970 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 971 // For debug purposes, dump the contents of the swap vector. 972 LLVM_DUMP_METHOD void PPCVSXSwapRemoval::dumpSwapVector() { 973 974 for (unsigned EntryIdx = 0; EntryIdx < SwapVector.size(); ++EntryIdx) { 975 976 MachineInstr *MI = SwapVector[EntryIdx].VSEMI; 977 int ID = SwapVector[EntryIdx].VSEId; 978 979 dbgs() << format("%6d", ID); 980 dbgs() << format("%6d", EC->getLeaderValue(ID)); 981 dbgs() << format(" %bb.%3d", MI->getParent()->getNumber()); 982 dbgs() << format(" %14s ", TII->getName(MI->getOpcode()).str().c_str()); 983 984 if (SwapVector[EntryIdx].IsLoad) 985 dbgs() << "load "; 986 if (SwapVector[EntryIdx].IsStore) 987 dbgs() << "store "; 988 if (SwapVector[EntryIdx].IsSwap) 989 dbgs() << "swap "; 990 if (SwapVector[EntryIdx].MentionsPhysVR) 991 dbgs() << "physreg "; 992 if (SwapVector[EntryIdx].MentionsPartialVR) 993 dbgs() << "partialreg "; 994 995 if (SwapVector[EntryIdx].IsSwappable) { 996 dbgs() << "swappable "; 997 switch(SwapVector[EntryIdx].SpecialHandling) { 998 default: 999 dbgs() << "special:**unknown**"; 1000 break; 1001 case SH_NONE: 1002 break; 1003 case SH_EXTRACT: 1004 dbgs() << "special:extract "; 1005 break; 1006 case SH_INSERT: 1007 dbgs() << "special:insert "; 1008 break; 1009 case SH_NOSWAP_LD: 1010 dbgs() << "special:load "; 1011 break; 1012 case SH_NOSWAP_ST: 1013 dbgs() << "special:store "; 1014 break; 1015 case SH_SPLAT: 1016 dbgs() << "special:splat "; 1017 break; 1018 case SH_XXPERMDI: 1019 dbgs() << "special:xxpermdi "; 1020 break; 1021 case SH_COPYWIDEN: 1022 dbgs() << "special:copywiden "; 1023 break; 1024 } 1025 } 1026 1027 if (SwapVector[EntryIdx].WebRejected) 1028 dbgs() << "rejected "; 1029 if (SwapVector[EntryIdx].WillRemove) 1030 dbgs() << "remove "; 1031 1032 dbgs() << "\n"; 1033 1034 // For no-asserts builds. 1035 (void)MI; 1036 (void)ID; 1037 } 1038 1039 dbgs() << "\n"; 1040 } 1041 #endif 1042 1043 } // end default namespace 1044 1045 INITIALIZE_PASS_BEGIN(PPCVSXSwapRemoval, DEBUG_TYPE, 1046 "PowerPC VSX Swap Removal", false, false) 1047 INITIALIZE_PASS_END(PPCVSXSwapRemoval, DEBUG_TYPE, 1048 "PowerPC VSX Swap Removal", false, false) 1049 1050 char PPCVSXSwapRemoval::ID = 0; 1051 FunctionPass* 1052 llvm::createPPCVSXSwapRemovalPass() { return new PPCVSXSwapRemoval(); } 1053