1 //===-- lib/CodeGen/GlobalISel/GICombinerHelper.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 #include "llvm/CodeGen/GlobalISel/CombinerHelper.h" 9 #include "llvm/ADT/SetVector.h" 10 #include "llvm/ADT/SmallBitVector.h" 11 #include "llvm/CodeGen/GlobalISel/Combiner.h" 12 #include "llvm/CodeGen/GlobalISel/GISelChangeObserver.h" 13 #include "llvm/CodeGen/GlobalISel/GISelKnownBits.h" 14 #include "llvm/CodeGen/GlobalISel/GenericMachineInstrs.h" 15 #include "llvm/CodeGen/GlobalISel/LegalizerHelper.h" 16 #include "llvm/CodeGen/GlobalISel/LegalizerInfo.h" 17 #include "llvm/CodeGen/GlobalISel/MIPatternMatch.h" 18 #include "llvm/CodeGen/GlobalISel/MachineIRBuilder.h" 19 #include "llvm/CodeGen/GlobalISel/RegisterBankInfo.h" 20 #include "llvm/CodeGen/GlobalISel/Utils.h" 21 #include "llvm/CodeGen/LowLevelType.h" 22 #include "llvm/CodeGen/MachineBasicBlock.h" 23 #include "llvm/CodeGen/MachineDominators.h" 24 #include "llvm/CodeGen/MachineFrameInfo.h" 25 #include "llvm/CodeGen/MachineInstr.h" 26 #include "llvm/CodeGen/MachineMemOperand.h" 27 #include "llvm/CodeGen/MachineRegisterInfo.h" 28 #include "llvm/CodeGen/TargetInstrInfo.h" 29 #include "llvm/CodeGen/TargetLowering.h" 30 #include "llvm/CodeGen/TargetOpcodes.h" 31 #include "llvm/IR/DataLayout.h" 32 #include "llvm/Support/Casting.h" 33 #include "llvm/Support/DivisionByConstantInfo.h" 34 #include "llvm/Support/MathExtras.h" 35 #include <tuple> 36 37 #define DEBUG_TYPE "gi-combiner" 38 39 using namespace llvm; 40 using namespace MIPatternMatch; 41 42 // Option to allow testing of the combiner while no targets know about indexed 43 // addressing. 44 static cl::opt<bool> 45 ForceLegalIndexing("force-legal-indexing", cl::Hidden, cl::init(false), 46 cl::desc("Force all indexed operations to be " 47 "legal for the GlobalISel combiner")); 48 49 CombinerHelper::CombinerHelper(GISelChangeObserver &Observer, 50 MachineIRBuilder &B, GISelKnownBits *KB, 51 MachineDominatorTree *MDT, 52 const LegalizerInfo *LI) 53 : Builder(B), MRI(Builder.getMF().getRegInfo()), Observer(Observer), KB(KB), 54 MDT(MDT), LI(LI), RBI(Builder.getMF().getSubtarget().getRegBankInfo()), 55 TRI(Builder.getMF().getSubtarget().getRegisterInfo()) { 56 (void)this->KB; 57 } 58 59 const TargetLowering &CombinerHelper::getTargetLowering() const { 60 return *Builder.getMF().getSubtarget().getTargetLowering(); 61 } 62 63 /// \returns The little endian in-memory byte position of byte \p I in a 64 /// \p ByteWidth bytes wide type. 65 /// 66 /// E.g. Given a 4-byte type x, x[0] -> byte 0 67 static unsigned littleEndianByteAt(const unsigned ByteWidth, const unsigned I) { 68 assert(I < ByteWidth && "I must be in [0, ByteWidth)"); 69 return I; 70 } 71 72 /// Determines the LogBase2 value for a non-null input value using the 73 /// transform: LogBase2(V) = (EltBits - 1) - ctlz(V). 74 static Register buildLogBase2(Register V, MachineIRBuilder &MIB) { 75 auto &MRI = *MIB.getMRI(); 76 LLT Ty = MRI.getType(V); 77 auto Ctlz = MIB.buildCTLZ(Ty, V); 78 auto Base = MIB.buildConstant(Ty, Ty.getScalarSizeInBits() - 1); 79 return MIB.buildSub(Ty, Base, Ctlz).getReg(0); 80 } 81 82 /// \returns The big endian in-memory byte position of byte \p I in a 83 /// \p ByteWidth bytes wide type. 84 /// 85 /// E.g. Given a 4-byte type x, x[0] -> byte 3 86 static unsigned bigEndianByteAt(const unsigned ByteWidth, const unsigned I) { 87 assert(I < ByteWidth && "I must be in [0, ByteWidth)"); 88 return ByteWidth - I - 1; 89 } 90 91 /// Given a map from byte offsets in memory to indices in a load/store, 92 /// determine if that map corresponds to a little or big endian byte pattern. 93 /// 94 /// \param MemOffset2Idx maps memory offsets to address offsets. 95 /// \param LowestIdx is the lowest index in \p MemOffset2Idx. 96 /// 97 /// \returns true if the map corresponds to a big endian byte pattern, false 98 /// if it corresponds to a little endian byte pattern, and None otherwise. 99 /// 100 /// E.g. given a 32-bit type x, and x[AddrOffset], the in-memory byte patterns 101 /// are as follows: 102 /// 103 /// AddrOffset Little endian Big endian 104 /// 0 0 3 105 /// 1 1 2 106 /// 2 2 1 107 /// 3 3 0 108 static Optional<bool> 109 isBigEndian(const SmallDenseMap<int64_t, int64_t, 8> &MemOffset2Idx, 110 int64_t LowestIdx) { 111 // Need at least two byte positions to decide on endianness. 112 unsigned Width = MemOffset2Idx.size(); 113 if (Width < 2) 114 return None; 115 bool BigEndian = true, LittleEndian = true; 116 for (unsigned MemOffset = 0; MemOffset < Width; ++ MemOffset) { 117 auto MemOffsetAndIdx = MemOffset2Idx.find(MemOffset); 118 if (MemOffsetAndIdx == MemOffset2Idx.end()) 119 return None; 120 const int64_t Idx = MemOffsetAndIdx->second - LowestIdx; 121 assert(Idx >= 0 && "Expected non-negative byte offset?"); 122 LittleEndian &= Idx == littleEndianByteAt(Width, MemOffset); 123 BigEndian &= Idx == bigEndianByteAt(Width, MemOffset); 124 if (!BigEndian && !LittleEndian) 125 return None; 126 } 127 128 assert((BigEndian != LittleEndian) && 129 "Pattern cannot be both big and little endian!"); 130 return BigEndian; 131 } 132 133 bool CombinerHelper::isLegalOrBeforeLegalizer( 134 const LegalityQuery &Query) const { 135 return !LI || LI->getAction(Query).Action == LegalizeActions::Legal; 136 } 137 138 void CombinerHelper::replaceRegWith(MachineRegisterInfo &MRI, Register FromReg, 139 Register ToReg) const { 140 Observer.changingAllUsesOfReg(MRI, FromReg); 141 142 if (MRI.constrainRegAttrs(ToReg, FromReg)) 143 MRI.replaceRegWith(FromReg, ToReg); 144 else 145 Builder.buildCopy(ToReg, FromReg); 146 147 Observer.finishedChangingAllUsesOfReg(); 148 } 149 150 void CombinerHelper::replaceRegOpWith(MachineRegisterInfo &MRI, 151 MachineOperand &FromRegOp, 152 Register ToReg) const { 153 assert(FromRegOp.getParent() && "Expected an operand in an MI"); 154 Observer.changingInstr(*FromRegOp.getParent()); 155 156 FromRegOp.setReg(ToReg); 157 158 Observer.changedInstr(*FromRegOp.getParent()); 159 } 160 161 void CombinerHelper::replaceOpcodeWith(MachineInstr &FromMI, 162 unsigned ToOpcode) const { 163 Observer.changingInstr(FromMI); 164 165 FromMI.setDesc(Builder.getTII().get(ToOpcode)); 166 167 Observer.changedInstr(FromMI); 168 } 169 170 const RegisterBank *CombinerHelper::getRegBank(Register Reg) const { 171 return RBI->getRegBank(Reg, MRI, *TRI); 172 } 173 174 void CombinerHelper::setRegBank(Register Reg, const RegisterBank *RegBank) { 175 if (RegBank) 176 MRI.setRegBank(Reg, *RegBank); 177 } 178 179 bool CombinerHelper::tryCombineCopy(MachineInstr &MI) { 180 if (matchCombineCopy(MI)) { 181 applyCombineCopy(MI); 182 return true; 183 } 184 return false; 185 } 186 bool CombinerHelper::matchCombineCopy(MachineInstr &MI) { 187 if (MI.getOpcode() != TargetOpcode::COPY) 188 return false; 189 Register DstReg = MI.getOperand(0).getReg(); 190 Register SrcReg = MI.getOperand(1).getReg(); 191 return canReplaceReg(DstReg, SrcReg, MRI); 192 } 193 void CombinerHelper::applyCombineCopy(MachineInstr &MI) { 194 Register DstReg = MI.getOperand(0).getReg(); 195 Register SrcReg = MI.getOperand(1).getReg(); 196 MI.eraseFromParent(); 197 replaceRegWith(MRI, DstReg, SrcReg); 198 } 199 200 bool CombinerHelper::tryCombineConcatVectors(MachineInstr &MI) { 201 bool IsUndef = false; 202 SmallVector<Register, 4> Ops; 203 if (matchCombineConcatVectors(MI, IsUndef, Ops)) { 204 applyCombineConcatVectors(MI, IsUndef, Ops); 205 return true; 206 } 207 return false; 208 } 209 210 bool CombinerHelper::matchCombineConcatVectors(MachineInstr &MI, bool &IsUndef, 211 SmallVectorImpl<Register> &Ops) { 212 assert(MI.getOpcode() == TargetOpcode::G_CONCAT_VECTORS && 213 "Invalid instruction"); 214 IsUndef = true; 215 MachineInstr *Undef = nullptr; 216 217 // Walk over all the operands of concat vectors and check if they are 218 // build_vector themselves or undef. 219 // Then collect their operands in Ops. 220 for (const MachineOperand &MO : MI.uses()) { 221 Register Reg = MO.getReg(); 222 MachineInstr *Def = MRI.getVRegDef(Reg); 223 assert(Def && "Operand not defined"); 224 switch (Def->getOpcode()) { 225 case TargetOpcode::G_BUILD_VECTOR: 226 IsUndef = false; 227 // Remember the operands of the build_vector to fold 228 // them into the yet-to-build flattened concat vectors. 229 for (const MachineOperand &BuildVecMO : Def->uses()) 230 Ops.push_back(BuildVecMO.getReg()); 231 break; 232 case TargetOpcode::G_IMPLICIT_DEF: { 233 LLT OpType = MRI.getType(Reg); 234 // Keep one undef value for all the undef operands. 235 if (!Undef) { 236 Builder.setInsertPt(*MI.getParent(), MI); 237 Undef = Builder.buildUndef(OpType.getScalarType()); 238 } 239 assert(MRI.getType(Undef->getOperand(0).getReg()) == 240 OpType.getScalarType() && 241 "All undefs should have the same type"); 242 // Break the undef vector in as many scalar elements as needed 243 // for the flattening. 244 for (unsigned EltIdx = 0, EltEnd = OpType.getNumElements(); 245 EltIdx != EltEnd; ++EltIdx) 246 Ops.push_back(Undef->getOperand(0).getReg()); 247 break; 248 } 249 default: 250 return false; 251 } 252 } 253 return true; 254 } 255 void CombinerHelper::applyCombineConcatVectors( 256 MachineInstr &MI, bool IsUndef, const ArrayRef<Register> Ops) { 257 // We determined that the concat_vectors can be flatten. 258 // Generate the flattened build_vector. 259 Register DstReg = MI.getOperand(0).getReg(); 260 Builder.setInsertPt(*MI.getParent(), MI); 261 Register NewDstReg = MRI.cloneVirtualRegister(DstReg); 262 263 // Note: IsUndef is sort of redundant. We could have determine it by 264 // checking that at all Ops are undef. Alternatively, we could have 265 // generate a build_vector of undefs and rely on another combine to 266 // clean that up. For now, given we already gather this information 267 // in tryCombineConcatVectors, just save compile time and issue the 268 // right thing. 269 if (IsUndef) 270 Builder.buildUndef(NewDstReg); 271 else 272 Builder.buildBuildVector(NewDstReg, Ops); 273 MI.eraseFromParent(); 274 replaceRegWith(MRI, DstReg, NewDstReg); 275 } 276 277 bool CombinerHelper::tryCombineShuffleVector(MachineInstr &MI) { 278 SmallVector<Register, 4> Ops; 279 if (matchCombineShuffleVector(MI, Ops)) { 280 applyCombineShuffleVector(MI, Ops); 281 return true; 282 } 283 return false; 284 } 285 286 bool CombinerHelper::matchCombineShuffleVector(MachineInstr &MI, 287 SmallVectorImpl<Register> &Ops) { 288 assert(MI.getOpcode() == TargetOpcode::G_SHUFFLE_VECTOR && 289 "Invalid instruction kind"); 290 LLT DstType = MRI.getType(MI.getOperand(0).getReg()); 291 Register Src1 = MI.getOperand(1).getReg(); 292 LLT SrcType = MRI.getType(Src1); 293 // As bizarre as it may look, shuffle vector can actually produce 294 // scalar! This is because at the IR level a <1 x ty> shuffle 295 // vector is perfectly valid. 296 unsigned DstNumElts = DstType.isVector() ? DstType.getNumElements() : 1; 297 unsigned SrcNumElts = SrcType.isVector() ? SrcType.getNumElements() : 1; 298 299 // If the resulting vector is smaller than the size of the source 300 // vectors being concatenated, we won't be able to replace the 301 // shuffle vector into a concat_vectors. 302 // 303 // Note: We may still be able to produce a concat_vectors fed by 304 // extract_vector_elt and so on. It is less clear that would 305 // be better though, so don't bother for now. 306 // 307 // If the destination is a scalar, the size of the sources doesn't 308 // matter. we will lower the shuffle to a plain copy. This will 309 // work only if the source and destination have the same size. But 310 // that's covered by the next condition. 311 // 312 // TODO: If the size between the source and destination don't match 313 // we could still emit an extract vector element in that case. 314 if (DstNumElts < 2 * SrcNumElts && DstNumElts != 1) 315 return false; 316 317 // Check that the shuffle mask can be broken evenly between the 318 // different sources. 319 if (DstNumElts % SrcNumElts != 0) 320 return false; 321 322 // Mask length is a multiple of the source vector length. 323 // Check if the shuffle is some kind of concatenation of the input 324 // vectors. 325 unsigned NumConcat = DstNumElts / SrcNumElts; 326 SmallVector<int, 8> ConcatSrcs(NumConcat, -1); 327 ArrayRef<int> Mask = MI.getOperand(3).getShuffleMask(); 328 for (unsigned i = 0; i != DstNumElts; ++i) { 329 int Idx = Mask[i]; 330 // Undef value. 331 if (Idx < 0) 332 continue; 333 // Ensure the indices in each SrcType sized piece are sequential and that 334 // the same source is used for the whole piece. 335 if ((Idx % SrcNumElts != (i % SrcNumElts)) || 336 (ConcatSrcs[i / SrcNumElts] >= 0 && 337 ConcatSrcs[i / SrcNumElts] != (int)(Idx / SrcNumElts))) 338 return false; 339 // Remember which source this index came from. 340 ConcatSrcs[i / SrcNumElts] = Idx / SrcNumElts; 341 } 342 343 // The shuffle is concatenating multiple vectors together. 344 // Collect the different operands for that. 345 Register UndefReg; 346 Register Src2 = MI.getOperand(2).getReg(); 347 for (auto Src : ConcatSrcs) { 348 if (Src < 0) { 349 if (!UndefReg) { 350 Builder.setInsertPt(*MI.getParent(), MI); 351 UndefReg = Builder.buildUndef(SrcType).getReg(0); 352 } 353 Ops.push_back(UndefReg); 354 } else if (Src == 0) 355 Ops.push_back(Src1); 356 else 357 Ops.push_back(Src2); 358 } 359 return true; 360 } 361 362 void CombinerHelper::applyCombineShuffleVector(MachineInstr &MI, 363 const ArrayRef<Register> Ops) { 364 Register DstReg = MI.getOperand(0).getReg(); 365 Builder.setInsertPt(*MI.getParent(), MI); 366 Register NewDstReg = MRI.cloneVirtualRegister(DstReg); 367 368 if (Ops.size() == 1) 369 Builder.buildCopy(NewDstReg, Ops[0]); 370 else 371 Builder.buildMerge(NewDstReg, Ops); 372 373 MI.eraseFromParent(); 374 replaceRegWith(MRI, DstReg, NewDstReg); 375 } 376 377 namespace { 378 379 /// Select a preference between two uses. CurrentUse is the current preference 380 /// while *ForCandidate is attributes of the candidate under consideration. 381 PreferredTuple ChoosePreferredUse(PreferredTuple &CurrentUse, 382 const LLT TyForCandidate, 383 unsigned OpcodeForCandidate, 384 MachineInstr *MIForCandidate) { 385 if (!CurrentUse.Ty.isValid()) { 386 if (CurrentUse.ExtendOpcode == OpcodeForCandidate || 387 CurrentUse.ExtendOpcode == TargetOpcode::G_ANYEXT) 388 return {TyForCandidate, OpcodeForCandidate, MIForCandidate}; 389 return CurrentUse; 390 } 391 392 // We permit the extend to hoist through basic blocks but this is only 393 // sensible if the target has extending loads. If you end up lowering back 394 // into a load and extend during the legalizer then the end result is 395 // hoisting the extend up to the load. 396 397 // Prefer defined extensions to undefined extensions as these are more 398 // likely to reduce the number of instructions. 399 if (OpcodeForCandidate == TargetOpcode::G_ANYEXT && 400 CurrentUse.ExtendOpcode != TargetOpcode::G_ANYEXT) 401 return CurrentUse; 402 else if (CurrentUse.ExtendOpcode == TargetOpcode::G_ANYEXT && 403 OpcodeForCandidate != TargetOpcode::G_ANYEXT) 404 return {TyForCandidate, OpcodeForCandidate, MIForCandidate}; 405 406 // Prefer sign extensions to zero extensions as sign-extensions tend to be 407 // more expensive. 408 if (CurrentUse.Ty == TyForCandidate) { 409 if (CurrentUse.ExtendOpcode == TargetOpcode::G_SEXT && 410 OpcodeForCandidate == TargetOpcode::G_ZEXT) 411 return CurrentUse; 412 else if (CurrentUse.ExtendOpcode == TargetOpcode::G_ZEXT && 413 OpcodeForCandidate == TargetOpcode::G_SEXT) 414 return {TyForCandidate, OpcodeForCandidate, MIForCandidate}; 415 } 416 417 // This is potentially target specific. We've chosen the largest type 418 // because G_TRUNC is usually free. One potential catch with this is that 419 // some targets have a reduced number of larger registers than smaller 420 // registers and this choice potentially increases the live-range for the 421 // larger value. 422 if (TyForCandidate.getSizeInBits() > CurrentUse.Ty.getSizeInBits()) { 423 return {TyForCandidate, OpcodeForCandidate, MIForCandidate}; 424 } 425 return CurrentUse; 426 } 427 428 /// Find a suitable place to insert some instructions and insert them. This 429 /// function accounts for special cases like inserting before a PHI node. 430 /// The current strategy for inserting before PHI's is to duplicate the 431 /// instructions for each predecessor. However, while that's ok for G_TRUNC 432 /// on most targets since it generally requires no code, other targets/cases may 433 /// want to try harder to find a dominating block. 434 static void InsertInsnsWithoutSideEffectsBeforeUse( 435 MachineIRBuilder &Builder, MachineInstr &DefMI, MachineOperand &UseMO, 436 std::function<void(MachineBasicBlock *, MachineBasicBlock::iterator, 437 MachineOperand &UseMO)> 438 Inserter) { 439 MachineInstr &UseMI = *UseMO.getParent(); 440 441 MachineBasicBlock *InsertBB = UseMI.getParent(); 442 443 // If the use is a PHI then we want the predecessor block instead. 444 if (UseMI.isPHI()) { 445 MachineOperand *PredBB = std::next(&UseMO); 446 InsertBB = PredBB->getMBB(); 447 } 448 449 // If the block is the same block as the def then we want to insert just after 450 // the def instead of at the start of the block. 451 if (InsertBB == DefMI.getParent()) { 452 MachineBasicBlock::iterator InsertPt = &DefMI; 453 Inserter(InsertBB, std::next(InsertPt), UseMO); 454 return; 455 } 456 457 // Otherwise we want the start of the BB 458 Inserter(InsertBB, InsertBB->getFirstNonPHI(), UseMO); 459 } 460 } // end anonymous namespace 461 462 bool CombinerHelper::tryCombineExtendingLoads(MachineInstr &MI) { 463 PreferredTuple Preferred; 464 if (matchCombineExtendingLoads(MI, Preferred)) { 465 applyCombineExtendingLoads(MI, Preferred); 466 return true; 467 } 468 return false; 469 } 470 471 bool CombinerHelper::matchCombineExtendingLoads(MachineInstr &MI, 472 PreferredTuple &Preferred) { 473 // We match the loads and follow the uses to the extend instead of matching 474 // the extends and following the def to the load. This is because the load 475 // must remain in the same position for correctness (unless we also add code 476 // to find a safe place to sink it) whereas the extend is freely movable. 477 // It also prevents us from duplicating the load for the volatile case or just 478 // for performance. 479 GAnyLoad *LoadMI = dyn_cast<GAnyLoad>(&MI); 480 if (!LoadMI) 481 return false; 482 483 Register LoadReg = LoadMI->getDstReg(); 484 485 LLT LoadValueTy = MRI.getType(LoadReg); 486 if (!LoadValueTy.isScalar()) 487 return false; 488 489 // Most architectures are going to legalize <s8 loads into at least a 1 byte 490 // load, and the MMOs can only describe memory accesses in multiples of bytes. 491 // If we try to perform extload combining on those, we can end up with 492 // %a(s8) = extload %ptr (load 1 byte from %ptr) 493 // ... which is an illegal extload instruction. 494 if (LoadValueTy.getSizeInBits() < 8) 495 return false; 496 497 // For non power-of-2 types, they will very likely be legalized into multiple 498 // loads. Don't bother trying to match them into extending loads. 499 if (!isPowerOf2_32(LoadValueTy.getSizeInBits())) 500 return false; 501 502 // Find the preferred type aside from the any-extends (unless it's the only 503 // one) and non-extending ops. We'll emit an extending load to that type and 504 // and emit a variant of (extend (trunc X)) for the others according to the 505 // relative type sizes. At the same time, pick an extend to use based on the 506 // extend involved in the chosen type. 507 unsigned PreferredOpcode = 508 isa<GLoad>(&MI) 509 ? TargetOpcode::G_ANYEXT 510 : isa<GSExtLoad>(&MI) ? TargetOpcode::G_SEXT : TargetOpcode::G_ZEXT; 511 Preferred = {LLT(), PreferredOpcode, nullptr}; 512 for (auto &UseMI : MRI.use_nodbg_instructions(LoadReg)) { 513 if (UseMI.getOpcode() == TargetOpcode::G_SEXT || 514 UseMI.getOpcode() == TargetOpcode::G_ZEXT || 515 (UseMI.getOpcode() == TargetOpcode::G_ANYEXT)) { 516 const auto &MMO = LoadMI->getMMO(); 517 // For atomics, only form anyextending loads. 518 if (MMO.isAtomic() && UseMI.getOpcode() != TargetOpcode::G_ANYEXT) 519 continue; 520 // Check for legality. 521 if (LI) { 522 LegalityQuery::MemDesc MMDesc(MMO); 523 LLT UseTy = MRI.getType(UseMI.getOperand(0).getReg()); 524 LLT SrcTy = MRI.getType(LoadMI->getPointerReg()); 525 if (LI->getAction({LoadMI->getOpcode(), {UseTy, SrcTy}, {MMDesc}}) 526 .Action != LegalizeActions::Legal) 527 continue; 528 } 529 Preferred = ChoosePreferredUse(Preferred, 530 MRI.getType(UseMI.getOperand(0).getReg()), 531 UseMI.getOpcode(), &UseMI); 532 } 533 } 534 535 // There were no extends 536 if (!Preferred.MI) 537 return false; 538 // It should be impossible to chose an extend without selecting a different 539 // type since by definition the result of an extend is larger. 540 assert(Preferred.Ty != LoadValueTy && "Extending to same type?"); 541 542 LLVM_DEBUG(dbgs() << "Preferred use is: " << *Preferred.MI); 543 return true; 544 } 545 546 void CombinerHelper::applyCombineExtendingLoads(MachineInstr &MI, 547 PreferredTuple &Preferred) { 548 // Rewrite the load to the chosen extending load. 549 Register ChosenDstReg = Preferred.MI->getOperand(0).getReg(); 550 551 // Inserter to insert a truncate back to the original type at a given point 552 // with some basic CSE to limit truncate duplication to one per BB. 553 DenseMap<MachineBasicBlock *, MachineInstr *> EmittedInsns; 554 auto InsertTruncAt = [&](MachineBasicBlock *InsertIntoBB, 555 MachineBasicBlock::iterator InsertBefore, 556 MachineOperand &UseMO) { 557 MachineInstr *PreviouslyEmitted = EmittedInsns.lookup(InsertIntoBB); 558 if (PreviouslyEmitted) { 559 Observer.changingInstr(*UseMO.getParent()); 560 UseMO.setReg(PreviouslyEmitted->getOperand(0).getReg()); 561 Observer.changedInstr(*UseMO.getParent()); 562 return; 563 } 564 565 Builder.setInsertPt(*InsertIntoBB, InsertBefore); 566 Register NewDstReg = MRI.cloneVirtualRegister(MI.getOperand(0).getReg()); 567 MachineInstr *NewMI = Builder.buildTrunc(NewDstReg, ChosenDstReg); 568 EmittedInsns[InsertIntoBB] = NewMI; 569 replaceRegOpWith(MRI, UseMO, NewDstReg); 570 }; 571 572 Observer.changingInstr(MI); 573 MI.setDesc( 574 Builder.getTII().get(Preferred.ExtendOpcode == TargetOpcode::G_SEXT 575 ? TargetOpcode::G_SEXTLOAD 576 : Preferred.ExtendOpcode == TargetOpcode::G_ZEXT 577 ? TargetOpcode::G_ZEXTLOAD 578 : TargetOpcode::G_LOAD)); 579 580 // Rewrite all the uses to fix up the types. 581 auto &LoadValue = MI.getOperand(0); 582 SmallVector<MachineOperand *, 4> Uses; 583 for (auto &UseMO : MRI.use_operands(LoadValue.getReg())) 584 Uses.push_back(&UseMO); 585 586 for (auto *UseMO : Uses) { 587 MachineInstr *UseMI = UseMO->getParent(); 588 589 // If the extend is compatible with the preferred extend then we should fix 590 // up the type and extend so that it uses the preferred use. 591 if (UseMI->getOpcode() == Preferred.ExtendOpcode || 592 UseMI->getOpcode() == TargetOpcode::G_ANYEXT) { 593 Register UseDstReg = UseMI->getOperand(0).getReg(); 594 MachineOperand &UseSrcMO = UseMI->getOperand(1); 595 const LLT UseDstTy = MRI.getType(UseDstReg); 596 if (UseDstReg != ChosenDstReg) { 597 if (Preferred.Ty == UseDstTy) { 598 // If the use has the same type as the preferred use, then merge 599 // the vregs and erase the extend. For example: 600 // %1:_(s8) = G_LOAD ... 601 // %2:_(s32) = G_SEXT %1(s8) 602 // %3:_(s32) = G_ANYEXT %1(s8) 603 // ... = ... %3(s32) 604 // rewrites to: 605 // %2:_(s32) = G_SEXTLOAD ... 606 // ... = ... %2(s32) 607 replaceRegWith(MRI, UseDstReg, ChosenDstReg); 608 Observer.erasingInstr(*UseMO->getParent()); 609 UseMO->getParent()->eraseFromParent(); 610 } else if (Preferred.Ty.getSizeInBits() < UseDstTy.getSizeInBits()) { 611 // If the preferred size is smaller, then keep the extend but extend 612 // from the result of the extending load. For example: 613 // %1:_(s8) = G_LOAD ... 614 // %2:_(s32) = G_SEXT %1(s8) 615 // %3:_(s64) = G_ANYEXT %1(s8) 616 // ... = ... %3(s64) 617 /// rewrites to: 618 // %2:_(s32) = G_SEXTLOAD ... 619 // %3:_(s64) = G_ANYEXT %2:_(s32) 620 // ... = ... %3(s64) 621 replaceRegOpWith(MRI, UseSrcMO, ChosenDstReg); 622 } else { 623 // If the preferred size is large, then insert a truncate. For 624 // example: 625 // %1:_(s8) = G_LOAD ... 626 // %2:_(s64) = G_SEXT %1(s8) 627 // %3:_(s32) = G_ZEXT %1(s8) 628 // ... = ... %3(s32) 629 /// rewrites to: 630 // %2:_(s64) = G_SEXTLOAD ... 631 // %4:_(s8) = G_TRUNC %2:_(s32) 632 // %3:_(s64) = G_ZEXT %2:_(s8) 633 // ... = ... %3(s64) 634 InsertInsnsWithoutSideEffectsBeforeUse(Builder, MI, *UseMO, 635 InsertTruncAt); 636 } 637 continue; 638 } 639 // The use is (one of) the uses of the preferred use we chose earlier. 640 // We're going to update the load to def this value later so just erase 641 // the old extend. 642 Observer.erasingInstr(*UseMO->getParent()); 643 UseMO->getParent()->eraseFromParent(); 644 continue; 645 } 646 647 // The use isn't an extend. Truncate back to the type we originally loaded. 648 // This is free on many targets. 649 InsertInsnsWithoutSideEffectsBeforeUse(Builder, MI, *UseMO, InsertTruncAt); 650 } 651 652 MI.getOperand(0).setReg(ChosenDstReg); 653 Observer.changedInstr(MI); 654 } 655 656 bool CombinerHelper::matchCombineLoadWithAndMask(MachineInstr &MI, 657 BuildFnTy &MatchInfo) { 658 assert(MI.getOpcode() == TargetOpcode::G_AND); 659 660 // If we have the following code: 661 // %mask = G_CONSTANT 255 662 // %ld = G_LOAD %ptr, (load s16) 663 // %and = G_AND %ld, %mask 664 // 665 // Try to fold it into 666 // %ld = G_ZEXTLOAD %ptr, (load s8) 667 668 Register Dst = MI.getOperand(0).getReg(); 669 if (MRI.getType(Dst).isVector()) 670 return false; 671 672 auto MaybeMask = 673 getIConstantVRegValWithLookThrough(MI.getOperand(2).getReg(), MRI); 674 if (!MaybeMask) 675 return false; 676 677 APInt MaskVal = MaybeMask->Value; 678 679 if (!MaskVal.isMask()) 680 return false; 681 682 Register SrcReg = MI.getOperand(1).getReg(); 683 GAnyLoad *LoadMI = getOpcodeDef<GAnyLoad>(SrcReg, MRI); 684 if (!LoadMI || !MRI.hasOneNonDBGUse(LoadMI->getDstReg()) || 685 !LoadMI->isSimple()) 686 return false; 687 688 Register LoadReg = LoadMI->getDstReg(); 689 LLT LoadTy = MRI.getType(LoadReg); 690 Register PtrReg = LoadMI->getPointerReg(); 691 uint64_t LoadSizeBits = LoadMI->getMemSizeInBits(); 692 unsigned MaskSizeBits = MaskVal.countTrailingOnes(); 693 694 // The mask may not be larger than the in-memory type, as it might cover sign 695 // extended bits 696 if (MaskSizeBits > LoadSizeBits) 697 return false; 698 699 // If the mask covers the whole destination register, there's nothing to 700 // extend 701 if (MaskSizeBits >= LoadTy.getSizeInBits()) 702 return false; 703 704 // Most targets cannot deal with loads of size < 8 and need to re-legalize to 705 // at least byte loads. Avoid creating such loads here 706 if (MaskSizeBits < 8 || !isPowerOf2_32(MaskSizeBits)) 707 return false; 708 709 const MachineMemOperand &MMO = LoadMI->getMMO(); 710 LegalityQuery::MemDesc MemDesc(MMO); 711 MemDesc.MemoryTy = LLT::scalar(MaskSizeBits); 712 if (!isLegalOrBeforeLegalizer( 713 {TargetOpcode::G_ZEXTLOAD, {LoadTy, MRI.getType(PtrReg)}, {MemDesc}})) 714 return false; 715 716 MatchInfo = [=](MachineIRBuilder &B) { 717 B.setInstrAndDebugLoc(*LoadMI); 718 auto &MF = B.getMF(); 719 auto PtrInfo = MMO.getPointerInfo(); 720 auto *NewMMO = MF.getMachineMemOperand(&MMO, PtrInfo, MaskSizeBits / 8); 721 B.buildLoadInstr(TargetOpcode::G_ZEXTLOAD, Dst, PtrReg, *NewMMO); 722 }; 723 return true; 724 } 725 726 bool CombinerHelper::isPredecessor(const MachineInstr &DefMI, 727 const MachineInstr &UseMI) { 728 assert(!DefMI.isDebugInstr() && !UseMI.isDebugInstr() && 729 "shouldn't consider debug uses"); 730 assert(DefMI.getParent() == UseMI.getParent()); 731 if (&DefMI == &UseMI) 732 return true; 733 const MachineBasicBlock &MBB = *DefMI.getParent(); 734 auto DefOrUse = find_if(MBB, [&DefMI, &UseMI](const MachineInstr &MI) { 735 return &MI == &DefMI || &MI == &UseMI; 736 }); 737 if (DefOrUse == MBB.end()) 738 llvm_unreachable("Block must contain both DefMI and UseMI!"); 739 return &*DefOrUse == &DefMI; 740 } 741 742 bool CombinerHelper::dominates(const MachineInstr &DefMI, 743 const MachineInstr &UseMI) { 744 assert(!DefMI.isDebugInstr() && !UseMI.isDebugInstr() && 745 "shouldn't consider debug uses"); 746 if (MDT) 747 return MDT->dominates(&DefMI, &UseMI); 748 else if (DefMI.getParent() != UseMI.getParent()) 749 return false; 750 751 return isPredecessor(DefMI, UseMI); 752 } 753 754 bool CombinerHelper::matchSextTruncSextLoad(MachineInstr &MI) { 755 assert(MI.getOpcode() == TargetOpcode::G_SEXT_INREG); 756 Register SrcReg = MI.getOperand(1).getReg(); 757 Register LoadUser = SrcReg; 758 759 if (MRI.getType(SrcReg).isVector()) 760 return false; 761 762 Register TruncSrc; 763 if (mi_match(SrcReg, MRI, m_GTrunc(m_Reg(TruncSrc)))) 764 LoadUser = TruncSrc; 765 766 uint64_t SizeInBits = MI.getOperand(2).getImm(); 767 // If the source is a G_SEXTLOAD from the same bit width, then we don't 768 // need any extend at all, just a truncate. 769 if (auto *LoadMI = getOpcodeDef<GSExtLoad>(LoadUser, MRI)) { 770 // If truncating more than the original extended value, abort. 771 auto LoadSizeBits = LoadMI->getMemSizeInBits(); 772 if (TruncSrc && MRI.getType(TruncSrc).getSizeInBits() < LoadSizeBits) 773 return false; 774 if (LoadSizeBits == SizeInBits) 775 return true; 776 } 777 return false; 778 } 779 780 void CombinerHelper::applySextTruncSextLoad(MachineInstr &MI) { 781 assert(MI.getOpcode() == TargetOpcode::G_SEXT_INREG); 782 Builder.setInstrAndDebugLoc(MI); 783 Builder.buildCopy(MI.getOperand(0).getReg(), MI.getOperand(1).getReg()); 784 MI.eraseFromParent(); 785 } 786 787 bool CombinerHelper::matchSextInRegOfLoad( 788 MachineInstr &MI, std::tuple<Register, unsigned> &MatchInfo) { 789 assert(MI.getOpcode() == TargetOpcode::G_SEXT_INREG); 790 791 // Only supports scalars for now. 792 if (MRI.getType(MI.getOperand(0).getReg()).isVector()) 793 return false; 794 795 Register SrcReg = MI.getOperand(1).getReg(); 796 auto *LoadDef = getOpcodeDef<GLoad>(SrcReg, MRI); 797 if (!LoadDef || !MRI.hasOneNonDBGUse(LoadDef->getOperand(0).getReg()) || 798 !LoadDef->isSimple()) 799 return false; 800 801 // If the sign extend extends from a narrower width than the load's width, 802 // then we can narrow the load width when we combine to a G_SEXTLOAD. 803 // Avoid widening the load at all. 804 unsigned NewSizeBits = std::min((uint64_t)MI.getOperand(2).getImm(), 805 LoadDef->getMemSizeInBits()); 806 807 // Don't generate G_SEXTLOADs with a < 1 byte width. 808 if (NewSizeBits < 8) 809 return false; 810 // Don't bother creating a non-power-2 sextload, it will likely be broken up 811 // anyway for most targets. 812 if (!isPowerOf2_32(NewSizeBits)) 813 return false; 814 815 const MachineMemOperand &MMO = LoadDef->getMMO(); 816 LegalityQuery::MemDesc MMDesc(MMO); 817 MMDesc.MemoryTy = LLT::scalar(NewSizeBits); 818 if (!isLegalOrBeforeLegalizer({TargetOpcode::G_SEXTLOAD, 819 {MRI.getType(LoadDef->getDstReg()), 820 MRI.getType(LoadDef->getPointerReg())}, 821 {MMDesc}})) 822 return false; 823 824 MatchInfo = std::make_tuple(LoadDef->getDstReg(), NewSizeBits); 825 return true; 826 } 827 828 void CombinerHelper::applySextInRegOfLoad( 829 MachineInstr &MI, std::tuple<Register, unsigned> &MatchInfo) { 830 assert(MI.getOpcode() == TargetOpcode::G_SEXT_INREG); 831 Register LoadReg; 832 unsigned ScalarSizeBits; 833 std::tie(LoadReg, ScalarSizeBits) = MatchInfo; 834 GLoad *LoadDef = cast<GLoad>(MRI.getVRegDef(LoadReg)); 835 836 // If we have the following: 837 // %ld = G_LOAD %ptr, (load 2) 838 // %ext = G_SEXT_INREG %ld, 8 839 // ==> 840 // %ld = G_SEXTLOAD %ptr (load 1) 841 842 auto &MMO = LoadDef->getMMO(); 843 Builder.setInstrAndDebugLoc(*LoadDef); 844 auto &MF = Builder.getMF(); 845 auto PtrInfo = MMO.getPointerInfo(); 846 auto *NewMMO = MF.getMachineMemOperand(&MMO, PtrInfo, ScalarSizeBits / 8); 847 Builder.buildLoadInstr(TargetOpcode::G_SEXTLOAD, MI.getOperand(0).getReg(), 848 LoadDef->getPointerReg(), *NewMMO); 849 MI.eraseFromParent(); 850 } 851 852 bool CombinerHelper::findPostIndexCandidate(MachineInstr &MI, Register &Addr, 853 Register &Base, Register &Offset) { 854 auto &MF = *MI.getParent()->getParent(); 855 const auto &TLI = *MF.getSubtarget().getTargetLowering(); 856 857 #ifndef NDEBUG 858 unsigned Opcode = MI.getOpcode(); 859 assert(Opcode == TargetOpcode::G_LOAD || Opcode == TargetOpcode::G_SEXTLOAD || 860 Opcode == TargetOpcode::G_ZEXTLOAD || Opcode == TargetOpcode::G_STORE); 861 #endif 862 863 Base = MI.getOperand(1).getReg(); 864 MachineInstr *BaseDef = MRI.getUniqueVRegDef(Base); 865 if (BaseDef && BaseDef->getOpcode() == TargetOpcode::G_FRAME_INDEX) 866 return false; 867 868 LLVM_DEBUG(dbgs() << "Searching for post-indexing opportunity for: " << MI); 869 // FIXME: The following use traversal needs a bail out for patholigical cases. 870 for (auto &Use : MRI.use_nodbg_instructions(Base)) { 871 if (Use.getOpcode() != TargetOpcode::G_PTR_ADD) 872 continue; 873 874 Offset = Use.getOperand(2).getReg(); 875 if (!ForceLegalIndexing && 876 !TLI.isIndexingLegal(MI, Base, Offset, /*IsPre*/ false, MRI)) { 877 LLVM_DEBUG(dbgs() << " Ignoring candidate with illegal addrmode: " 878 << Use); 879 continue; 880 } 881 882 // Make sure the offset calculation is before the potentially indexed op. 883 // FIXME: we really care about dependency here. The offset calculation might 884 // be movable. 885 MachineInstr *OffsetDef = MRI.getUniqueVRegDef(Offset); 886 if (!OffsetDef || !dominates(*OffsetDef, MI)) { 887 LLVM_DEBUG(dbgs() << " Ignoring candidate with offset after mem-op: " 888 << Use); 889 continue; 890 } 891 892 // FIXME: check whether all uses of Base are load/store with foldable 893 // addressing modes. If so, using the normal addr-modes is better than 894 // forming an indexed one. 895 896 bool MemOpDominatesAddrUses = true; 897 for (auto &PtrAddUse : 898 MRI.use_nodbg_instructions(Use.getOperand(0).getReg())) { 899 if (!dominates(MI, PtrAddUse)) { 900 MemOpDominatesAddrUses = false; 901 break; 902 } 903 } 904 905 if (!MemOpDominatesAddrUses) { 906 LLVM_DEBUG( 907 dbgs() << " Ignoring candidate as memop does not dominate uses: " 908 << Use); 909 continue; 910 } 911 912 LLVM_DEBUG(dbgs() << " Found match: " << Use); 913 Addr = Use.getOperand(0).getReg(); 914 return true; 915 } 916 917 return false; 918 } 919 920 bool CombinerHelper::findPreIndexCandidate(MachineInstr &MI, Register &Addr, 921 Register &Base, Register &Offset) { 922 auto &MF = *MI.getParent()->getParent(); 923 const auto &TLI = *MF.getSubtarget().getTargetLowering(); 924 925 #ifndef NDEBUG 926 unsigned Opcode = MI.getOpcode(); 927 assert(Opcode == TargetOpcode::G_LOAD || Opcode == TargetOpcode::G_SEXTLOAD || 928 Opcode == TargetOpcode::G_ZEXTLOAD || Opcode == TargetOpcode::G_STORE); 929 #endif 930 931 Addr = MI.getOperand(1).getReg(); 932 MachineInstr *AddrDef = getOpcodeDef(TargetOpcode::G_PTR_ADD, Addr, MRI); 933 if (!AddrDef || MRI.hasOneNonDBGUse(Addr)) 934 return false; 935 936 Base = AddrDef->getOperand(1).getReg(); 937 Offset = AddrDef->getOperand(2).getReg(); 938 939 LLVM_DEBUG(dbgs() << "Found potential pre-indexed load_store: " << MI); 940 941 if (!ForceLegalIndexing && 942 !TLI.isIndexingLegal(MI, Base, Offset, /*IsPre*/ true, MRI)) { 943 LLVM_DEBUG(dbgs() << " Skipping, not legal for target"); 944 return false; 945 } 946 947 MachineInstr *BaseDef = getDefIgnoringCopies(Base, MRI); 948 if (BaseDef->getOpcode() == TargetOpcode::G_FRAME_INDEX) { 949 LLVM_DEBUG(dbgs() << " Skipping, frame index would need copy anyway."); 950 return false; 951 } 952 953 if (MI.getOpcode() == TargetOpcode::G_STORE) { 954 // Would require a copy. 955 if (Base == MI.getOperand(0).getReg()) { 956 LLVM_DEBUG(dbgs() << " Skipping, storing base so need copy anyway."); 957 return false; 958 } 959 960 // We're expecting one use of Addr in MI, but it could also be the 961 // value stored, which isn't actually dominated by the instruction. 962 if (MI.getOperand(0).getReg() == Addr) { 963 LLVM_DEBUG(dbgs() << " Skipping, does not dominate all addr uses"); 964 return false; 965 } 966 } 967 968 // FIXME: check whether all uses of the base pointer are constant PtrAdds. 969 // That might allow us to end base's liveness here by adjusting the constant. 970 971 for (auto &UseMI : MRI.use_nodbg_instructions(Addr)) { 972 if (!dominates(MI, UseMI)) { 973 LLVM_DEBUG(dbgs() << " Skipping, does not dominate all addr uses."); 974 return false; 975 } 976 } 977 978 return true; 979 } 980 981 bool CombinerHelper::tryCombineIndexedLoadStore(MachineInstr &MI) { 982 IndexedLoadStoreMatchInfo MatchInfo; 983 if (matchCombineIndexedLoadStore(MI, MatchInfo)) { 984 applyCombineIndexedLoadStore(MI, MatchInfo); 985 return true; 986 } 987 return false; 988 } 989 990 bool CombinerHelper::matchCombineIndexedLoadStore(MachineInstr &MI, IndexedLoadStoreMatchInfo &MatchInfo) { 991 unsigned Opcode = MI.getOpcode(); 992 if (Opcode != TargetOpcode::G_LOAD && Opcode != TargetOpcode::G_SEXTLOAD && 993 Opcode != TargetOpcode::G_ZEXTLOAD && Opcode != TargetOpcode::G_STORE) 994 return false; 995 996 // For now, no targets actually support these opcodes so don't waste time 997 // running these unless we're forced to for testing. 998 if (!ForceLegalIndexing) 999 return false; 1000 1001 MatchInfo.IsPre = findPreIndexCandidate(MI, MatchInfo.Addr, MatchInfo.Base, 1002 MatchInfo.Offset); 1003 if (!MatchInfo.IsPre && 1004 !findPostIndexCandidate(MI, MatchInfo.Addr, MatchInfo.Base, 1005 MatchInfo.Offset)) 1006 return false; 1007 1008 return true; 1009 } 1010 1011 void CombinerHelper::applyCombineIndexedLoadStore( 1012 MachineInstr &MI, IndexedLoadStoreMatchInfo &MatchInfo) { 1013 MachineInstr &AddrDef = *MRI.getUniqueVRegDef(MatchInfo.Addr); 1014 MachineIRBuilder MIRBuilder(MI); 1015 unsigned Opcode = MI.getOpcode(); 1016 bool IsStore = Opcode == TargetOpcode::G_STORE; 1017 unsigned NewOpcode; 1018 switch (Opcode) { 1019 case TargetOpcode::G_LOAD: 1020 NewOpcode = TargetOpcode::G_INDEXED_LOAD; 1021 break; 1022 case TargetOpcode::G_SEXTLOAD: 1023 NewOpcode = TargetOpcode::G_INDEXED_SEXTLOAD; 1024 break; 1025 case TargetOpcode::G_ZEXTLOAD: 1026 NewOpcode = TargetOpcode::G_INDEXED_ZEXTLOAD; 1027 break; 1028 case TargetOpcode::G_STORE: 1029 NewOpcode = TargetOpcode::G_INDEXED_STORE; 1030 break; 1031 default: 1032 llvm_unreachable("Unknown load/store opcode"); 1033 } 1034 1035 auto MIB = MIRBuilder.buildInstr(NewOpcode); 1036 if (IsStore) { 1037 MIB.addDef(MatchInfo.Addr); 1038 MIB.addUse(MI.getOperand(0).getReg()); 1039 } else { 1040 MIB.addDef(MI.getOperand(0).getReg()); 1041 MIB.addDef(MatchInfo.Addr); 1042 } 1043 1044 MIB.addUse(MatchInfo.Base); 1045 MIB.addUse(MatchInfo.Offset); 1046 MIB.addImm(MatchInfo.IsPre); 1047 MI.eraseFromParent(); 1048 AddrDef.eraseFromParent(); 1049 1050 LLVM_DEBUG(dbgs() << " Combinined to indexed operation"); 1051 } 1052 1053 bool CombinerHelper::matchCombineDivRem(MachineInstr &MI, 1054 MachineInstr *&OtherMI) { 1055 unsigned Opcode = MI.getOpcode(); 1056 bool IsDiv, IsSigned; 1057 1058 switch (Opcode) { 1059 default: 1060 llvm_unreachable("Unexpected opcode!"); 1061 case TargetOpcode::G_SDIV: 1062 case TargetOpcode::G_UDIV: { 1063 IsDiv = true; 1064 IsSigned = Opcode == TargetOpcode::G_SDIV; 1065 break; 1066 } 1067 case TargetOpcode::G_SREM: 1068 case TargetOpcode::G_UREM: { 1069 IsDiv = false; 1070 IsSigned = Opcode == TargetOpcode::G_SREM; 1071 break; 1072 } 1073 } 1074 1075 Register Src1 = MI.getOperand(1).getReg(); 1076 unsigned DivOpcode, RemOpcode, DivremOpcode; 1077 if (IsSigned) { 1078 DivOpcode = TargetOpcode::G_SDIV; 1079 RemOpcode = TargetOpcode::G_SREM; 1080 DivremOpcode = TargetOpcode::G_SDIVREM; 1081 } else { 1082 DivOpcode = TargetOpcode::G_UDIV; 1083 RemOpcode = TargetOpcode::G_UREM; 1084 DivremOpcode = TargetOpcode::G_UDIVREM; 1085 } 1086 1087 if (!isLegalOrBeforeLegalizer({DivremOpcode, {MRI.getType(Src1)}})) 1088 return false; 1089 1090 // Combine: 1091 // %div:_ = G_[SU]DIV %src1:_, %src2:_ 1092 // %rem:_ = G_[SU]REM %src1:_, %src2:_ 1093 // into: 1094 // %div:_, %rem:_ = G_[SU]DIVREM %src1:_, %src2:_ 1095 1096 // Combine: 1097 // %rem:_ = G_[SU]REM %src1:_, %src2:_ 1098 // %div:_ = G_[SU]DIV %src1:_, %src2:_ 1099 // into: 1100 // %div:_, %rem:_ = G_[SU]DIVREM %src1:_, %src2:_ 1101 1102 for (auto &UseMI : MRI.use_nodbg_instructions(Src1)) { 1103 if (MI.getParent() == UseMI.getParent() && 1104 ((IsDiv && UseMI.getOpcode() == RemOpcode) || 1105 (!IsDiv && UseMI.getOpcode() == DivOpcode)) && 1106 matchEqualDefs(MI.getOperand(2), UseMI.getOperand(2))) { 1107 OtherMI = &UseMI; 1108 return true; 1109 } 1110 } 1111 1112 return false; 1113 } 1114 1115 void CombinerHelper::applyCombineDivRem(MachineInstr &MI, 1116 MachineInstr *&OtherMI) { 1117 unsigned Opcode = MI.getOpcode(); 1118 assert(OtherMI && "OtherMI shouldn't be empty."); 1119 1120 Register DestDivReg, DestRemReg; 1121 if (Opcode == TargetOpcode::G_SDIV || Opcode == TargetOpcode::G_UDIV) { 1122 DestDivReg = MI.getOperand(0).getReg(); 1123 DestRemReg = OtherMI->getOperand(0).getReg(); 1124 } else { 1125 DestDivReg = OtherMI->getOperand(0).getReg(); 1126 DestRemReg = MI.getOperand(0).getReg(); 1127 } 1128 1129 bool IsSigned = 1130 Opcode == TargetOpcode::G_SDIV || Opcode == TargetOpcode::G_SREM; 1131 1132 // Check which instruction is first in the block so we don't break def-use 1133 // deps by "moving" the instruction incorrectly. 1134 if (dominates(MI, *OtherMI)) 1135 Builder.setInstrAndDebugLoc(MI); 1136 else 1137 Builder.setInstrAndDebugLoc(*OtherMI); 1138 1139 Builder.buildInstr(IsSigned ? TargetOpcode::G_SDIVREM 1140 : TargetOpcode::G_UDIVREM, 1141 {DestDivReg, DestRemReg}, 1142 {MI.getOperand(1).getReg(), MI.getOperand(2).getReg()}); 1143 MI.eraseFromParent(); 1144 OtherMI->eraseFromParent(); 1145 } 1146 1147 bool CombinerHelper::matchOptBrCondByInvertingCond(MachineInstr &MI, 1148 MachineInstr *&BrCond) { 1149 assert(MI.getOpcode() == TargetOpcode::G_BR); 1150 1151 // Try to match the following: 1152 // bb1: 1153 // G_BRCOND %c1, %bb2 1154 // G_BR %bb3 1155 // bb2: 1156 // ... 1157 // bb3: 1158 1159 // The above pattern does not have a fall through to the successor bb2, always 1160 // resulting in a branch no matter which path is taken. Here we try to find 1161 // and replace that pattern with conditional branch to bb3 and otherwise 1162 // fallthrough to bb2. This is generally better for branch predictors. 1163 1164 MachineBasicBlock *MBB = MI.getParent(); 1165 MachineBasicBlock::iterator BrIt(MI); 1166 if (BrIt == MBB->begin()) 1167 return false; 1168 assert(std::next(BrIt) == MBB->end() && "expected G_BR to be a terminator"); 1169 1170 BrCond = &*std::prev(BrIt); 1171 if (BrCond->getOpcode() != TargetOpcode::G_BRCOND) 1172 return false; 1173 1174 // Check that the next block is the conditional branch target. Also make sure 1175 // that it isn't the same as the G_BR's target (otherwise, this will loop.) 1176 MachineBasicBlock *BrCondTarget = BrCond->getOperand(1).getMBB(); 1177 return BrCondTarget != MI.getOperand(0).getMBB() && 1178 MBB->isLayoutSuccessor(BrCondTarget); 1179 } 1180 1181 void CombinerHelper::applyOptBrCondByInvertingCond(MachineInstr &MI, 1182 MachineInstr *&BrCond) { 1183 MachineBasicBlock *BrTarget = MI.getOperand(0).getMBB(); 1184 Builder.setInstrAndDebugLoc(*BrCond); 1185 LLT Ty = MRI.getType(BrCond->getOperand(0).getReg()); 1186 // FIXME: Does int/fp matter for this? If so, we might need to restrict 1187 // this to i1 only since we might not know for sure what kind of 1188 // compare generated the condition value. 1189 auto True = Builder.buildConstant( 1190 Ty, getICmpTrueVal(getTargetLowering(), false, false)); 1191 auto Xor = Builder.buildXor(Ty, BrCond->getOperand(0), True); 1192 1193 auto *FallthroughBB = BrCond->getOperand(1).getMBB(); 1194 Observer.changingInstr(MI); 1195 MI.getOperand(0).setMBB(FallthroughBB); 1196 Observer.changedInstr(MI); 1197 1198 // Change the conditional branch to use the inverted condition and 1199 // new target block. 1200 Observer.changingInstr(*BrCond); 1201 BrCond->getOperand(0).setReg(Xor.getReg(0)); 1202 BrCond->getOperand(1).setMBB(BrTarget); 1203 Observer.changedInstr(*BrCond); 1204 } 1205 1206 static Type *getTypeForLLT(LLT Ty, LLVMContext &C) { 1207 if (Ty.isVector()) 1208 return FixedVectorType::get(IntegerType::get(C, Ty.getScalarSizeInBits()), 1209 Ty.getNumElements()); 1210 return IntegerType::get(C, Ty.getSizeInBits()); 1211 } 1212 1213 bool CombinerHelper::tryEmitMemcpyInline(MachineInstr &MI) { 1214 MachineIRBuilder HelperBuilder(MI); 1215 GISelObserverWrapper DummyObserver; 1216 LegalizerHelper Helper(HelperBuilder.getMF(), DummyObserver, HelperBuilder); 1217 return Helper.lowerMemcpyInline(MI) == 1218 LegalizerHelper::LegalizeResult::Legalized; 1219 } 1220 1221 bool CombinerHelper::tryCombineMemCpyFamily(MachineInstr &MI, unsigned MaxLen) { 1222 MachineIRBuilder HelperBuilder(MI); 1223 GISelObserverWrapper DummyObserver; 1224 LegalizerHelper Helper(HelperBuilder.getMF(), DummyObserver, HelperBuilder); 1225 return Helper.lowerMemCpyFamily(MI, MaxLen) == 1226 LegalizerHelper::LegalizeResult::Legalized; 1227 } 1228 1229 static Optional<APFloat> constantFoldFpUnary(unsigned Opcode, LLT DstTy, 1230 const Register Op, 1231 const MachineRegisterInfo &MRI) { 1232 const ConstantFP *MaybeCst = getConstantFPVRegVal(Op, MRI); 1233 if (!MaybeCst) 1234 return None; 1235 1236 APFloat V = MaybeCst->getValueAPF(); 1237 switch (Opcode) { 1238 default: 1239 llvm_unreachable("Unexpected opcode!"); 1240 case TargetOpcode::G_FNEG: { 1241 V.changeSign(); 1242 return V; 1243 } 1244 case TargetOpcode::G_FABS: { 1245 V.clearSign(); 1246 return V; 1247 } 1248 case TargetOpcode::G_FPTRUNC: 1249 break; 1250 case TargetOpcode::G_FSQRT: { 1251 bool Unused; 1252 V.convert(APFloat::IEEEdouble(), APFloat::rmNearestTiesToEven, &Unused); 1253 V = APFloat(sqrt(V.convertToDouble())); 1254 break; 1255 } 1256 case TargetOpcode::G_FLOG2: { 1257 bool Unused; 1258 V.convert(APFloat::IEEEdouble(), APFloat::rmNearestTiesToEven, &Unused); 1259 V = APFloat(log2(V.convertToDouble())); 1260 break; 1261 } 1262 } 1263 // Convert `APFloat` to appropriate IEEE type depending on `DstTy`. Otherwise, 1264 // `buildFConstant` will assert on size mismatch. Only `G_FPTRUNC`, `G_FSQRT`, 1265 // and `G_FLOG2` reach here. 1266 bool Unused; 1267 V.convert(getFltSemanticForLLT(DstTy), APFloat::rmNearestTiesToEven, &Unused); 1268 return V; 1269 } 1270 1271 bool CombinerHelper::matchCombineConstantFoldFpUnary(MachineInstr &MI, 1272 Optional<APFloat> &Cst) { 1273 Register DstReg = MI.getOperand(0).getReg(); 1274 Register SrcReg = MI.getOperand(1).getReg(); 1275 LLT DstTy = MRI.getType(DstReg); 1276 Cst = constantFoldFpUnary(MI.getOpcode(), DstTy, SrcReg, MRI); 1277 return Cst.hasValue(); 1278 } 1279 1280 void CombinerHelper::applyCombineConstantFoldFpUnary(MachineInstr &MI, 1281 Optional<APFloat> &Cst) { 1282 assert(Cst.hasValue() && "Optional is unexpectedly empty!"); 1283 Builder.setInstrAndDebugLoc(MI); 1284 MachineFunction &MF = Builder.getMF(); 1285 auto *FPVal = ConstantFP::get(MF.getFunction().getContext(), *Cst); 1286 Register DstReg = MI.getOperand(0).getReg(); 1287 Builder.buildFConstant(DstReg, *FPVal); 1288 MI.eraseFromParent(); 1289 } 1290 1291 bool CombinerHelper::matchPtrAddImmedChain(MachineInstr &MI, 1292 PtrAddChain &MatchInfo) { 1293 // We're trying to match the following pattern: 1294 // %t1 = G_PTR_ADD %base, G_CONSTANT imm1 1295 // %root = G_PTR_ADD %t1, G_CONSTANT imm2 1296 // --> 1297 // %root = G_PTR_ADD %base, G_CONSTANT (imm1 + imm2) 1298 1299 if (MI.getOpcode() != TargetOpcode::G_PTR_ADD) 1300 return false; 1301 1302 Register Add2 = MI.getOperand(1).getReg(); 1303 Register Imm1 = MI.getOperand(2).getReg(); 1304 auto MaybeImmVal = getIConstantVRegValWithLookThrough(Imm1, MRI); 1305 if (!MaybeImmVal) 1306 return false; 1307 1308 MachineInstr *Add2Def = MRI.getVRegDef(Add2); 1309 if (!Add2Def || Add2Def->getOpcode() != TargetOpcode::G_PTR_ADD) 1310 return false; 1311 1312 Register Base = Add2Def->getOperand(1).getReg(); 1313 Register Imm2 = Add2Def->getOperand(2).getReg(); 1314 auto MaybeImm2Val = getIConstantVRegValWithLookThrough(Imm2, MRI); 1315 if (!MaybeImm2Val) 1316 return false; 1317 1318 // Check if the new combined immediate forms an illegal addressing mode. 1319 // Do not combine if it was legal before but would get illegal. 1320 // To do so, we need to find a load/store user of the pointer to get 1321 // the access type. 1322 Type *AccessTy = nullptr; 1323 auto &MF = *MI.getMF(); 1324 for (auto &UseMI : MRI.use_nodbg_instructions(MI.getOperand(0).getReg())) { 1325 if (auto *LdSt = dyn_cast<GLoadStore>(&UseMI)) { 1326 AccessTy = getTypeForLLT(MRI.getType(LdSt->getReg(0)), 1327 MF.getFunction().getContext()); 1328 break; 1329 } 1330 } 1331 TargetLoweringBase::AddrMode AMNew; 1332 APInt CombinedImm = MaybeImmVal->Value + MaybeImm2Val->Value; 1333 AMNew.BaseOffs = CombinedImm.getSExtValue(); 1334 if (AccessTy) { 1335 AMNew.HasBaseReg = true; 1336 TargetLoweringBase::AddrMode AMOld; 1337 AMOld.BaseOffs = MaybeImm2Val->Value.getSExtValue(); 1338 AMOld.HasBaseReg = true; 1339 unsigned AS = MRI.getType(Add2).getAddressSpace(); 1340 const auto &TLI = *MF.getSubtarget().getTargetLowering(); 1341 if (TLI.isLegalAddressingMode(MF.getDataLayout(), AMOld, AccessTy, AS) && 1342 !TLI.isLegalAddressingMode(MF.getDataLayout(), AMNew, AccessTy, AS)) 1343 return false; 1344 } 1345 1346 // Pass the combined immediate to the apply function. 1347 MatchInfo.Imm = AMNew.BaseOffs; 1348 MatchInfo.Base = Base; 1349 MatchInfo.Bank = getRegBank(Imm2); 1350 return true; 1351 } 1352 1353 void CombinerHelper::applyPtrAddImmedChain(MachineInstr &MI, 1354 PtrAddChain &MatchInfo) { 1355 assert(MI.getOpcode() == TargetOpcode::G_PTR_ADD && "Expected G_PTR_ADD"); 1356 MachineIRBuilder MIB(MI); 1357 LLT OffsetTy = MRI.getType(MI.getOperand(2).getReg()); 1358 auto NewOffset = MIB.buildConstant(OffsetTy, MatchInfo.Imm); 1359 setRegBank(NewOffset.getReg(0), MatchInfo.Bank); 1360 Observer.changingInstr(MI); 1361 MI.getOperand(1).setReg(MatchInfo.Base); 1362 MI.getOperand(2).setReg(NewOffset.getReg(0)); 1363 Observer.changedInstr(MI); 1364 } 1365 1366 bool CombinerHelper::matchShiftImmedChain(MachineInstr &MI, 1367 RegisterImmPair &MatchInfo) { 1368 // We're trying to match the following pattern with any of 1369 // G_SHL/G_ASHR/G_LSHR/G_SSHLSAT/G_USHLSAT shift instructions: 1370 // %t1 = SHIFT %base, G_CONSTANT imm1 1371 // %root = SHIFT %t1, G_CONSTANT imm2 1372 // --> 1373 // %root = SHIFT %base, G_CONSTANT (imm1 + imm2) 1374 1375 unsigned Opcode = MI.getOpcode(); 1376 assert((Opcode == TargetOpcode::G_SHL || Opcode == TargetOpcode::G_ASHR || 1377 Opcode == TargetOpcode::G_LSHR || Opcode == TargetOpcode::G_SSHLSAT || 1378 Opcode == TargetOpcode::G_USHLSAT) && 1379 "Expected G_SHL, G_ASHR, G_LSHR, G_SSHLSAT or G_USHLSAT"); 1380 1381 Register Shl2 = MI.getOperand(1).getReg(); 1382 Register Imm1 = MI.getOperand(2).getReg(); 1383 auto MaybeImmVal = getIConstantVRegValWithLookThrough(Imm1, MRI); 1384 if (!MaybeImmVal) 1385 return false; 1386 1387 MachineInstr *Shl2Def = MRI.getUniqueVRegDef(Shl2); 1388 if (Shl2Def->getOpcode() != Opcode) 1389 return false; 1390 1391 Register Base = Shl2Def->getOperand(1).getReg(); 1392 Register Imm2 = Shl2Def->getOperand(2).getReg(); 1393 auto MaybeImm2Val = getIConstantVRegValWithLookThrough(Imm2, MRI); 1394 if (!MaybeImm2Val) 1395 return false; 1396 1397 // Pass the combined immediate to the apply function. 1398 MatchInfo.Imm = 1399 (MaybeImmVal->Value.getSExtValue() + MaybeImm2Val->Value).getSExtValue(); 1400 MatchInfo.Reg = Base; 1401 1402 // There is no simple replacement for a saturating unsigned left shift that 1403 // exceeds the scalar size. 1404 if (Opcode == TargetOpcode::G_USHLSAT && 1405 MatchInfo.Imm >= MRI.getType(Shl2).getScalarSizeInBits()) 1406 return false; 1407 1408 return true; 1409 } 1410 1411 void CombinerHelper::applyShiftImmedChain(MachineInstr &MI, 1412 RegisterImmPair &MatchInfo) { 1413 unsigned Opcode = MI.getOpcode(); 1414 assert((Opcode == TargetOpcode::G_SHL || Opcode == TargetOpcode::G_ASHR || 1415 Opcode == TargetOpcode::G_LSHR || Opcode == TargetOpcode::G_SSHLSAT || 1416 Opcode == TargetOpcode::G_USHLSAT) && 1417 "Expected G_SHL, G_ASHR, G_LSHR, G_SSHLSAT or G_USHLSAT"); 1418 1419 Builder.setInstrAndDebugLoc(MI); 1420 LLT Ty = MRI.getType(MI.getOperand(1).getReg()); 1421 unsigned const ScalarSizeInBits = Ty.getScalarSizeInBits(); 1422 auto Imm = MatchInfo.Imm; 1423 1424 if (Imm >= ScalarSizeInBits) { 1425 // Any logical shift that exceeds scalar size will produce zero. 1426 if (Opcode == TargetOpcode::G_SHL || Opcode == TargetOpcode::G_LSHR) { 1427 Builder.buildConstant(MI.getOperand(0), 0); 1428 MI.eraseFromParent(); 1429 return; 1430 } 1431 // Arithmetic shift and saturating signed left shift have no effect beyond 1432 // scalar size. 1433 Imm = ScalarSizeInBits - 1; 1434 } 1435 1436 LLT ImmTy = MRI.getType(MI.getOperand(2).getReg()); 1437 Register NewImm = Builder.buildConstant(ImmTy, Imm).getReg(0); 1438 Observer.changingInstr(MI); 1439 MI.getOperand(1).setReg(MatchInfo.Reg); 1440 MI.getOperand(2).setReg(NewImm); 1441 Observer.changedInstr(MI); 1442 } 1443 1444 bool CombinerHelper::matchShiftOfShiftedLogic(MachineInstr &MI, 1445 ShiftOfShiftedLogic &MatchInfo) { 1446 // We're trying to match the following pattern with any of 1447 // G_SHL/G_ASHR/G_LSHR/G_USHLSAT/G_SSHLSAT shift instructions in combination 1448 // with any of G_AND/G_OR/G_XOR logic instructions. 1449 // %t1 = SHIFT %X, G_CONSTANT C0 1450 // %t2 = LOGIC %t1, %Y 1451 // %root = SHIFT %t2, G_CONSTANT C1 1452 // --> 1453 // %t3 = SHIFT %X, G_CONSTANT (C0+C1) 1454 // %t4 = SHIFT %Y, G_CONSTANT C1 1455 // %root = LOGIC %t3, %t4 1456 unsigned ShiftOpcode = MI.getOpcode(); 1457 assert((ShiftOpcode == TargetOpcode::G_SHL || 1458 ShiftOpcode == TargetOpcode::G_ASHR || 1459 ShiftOpcode == TargetOpcode::G_LSHR || 1460 ShiftOpcode == TargetOpcode::G_USHLSAT || 1461 ShiftOpcode == TargetOpcode::G_SSHLSAT) && 1462 "Expected G_SHL, G_ASHR, G_LSHR, G_USHLSAT and G_SSHLSAT"); 1463 1464 // Match a one-use bitwise logic op. 1465 Register LogicDest = MI.getOperand(1).getReg(); 1466 if (!MRI.hasOneNonDBGUse(LogicDest)) 1467 return false; 1468 1469 MachineInstr *LogicMI = MRI.getUniqueVRegDef(LogicDest); 1470 unsigned LogicOpcode = LogicMI->getOpcode(); 1471 if (LogicOpcode != TargetOpcode::G_AND && LogicOpcode != TargetOpcode::G_OR && 1472 LogicOpcode != TargetOpcode::G_XOR) 1473 return false; 1474 1475 // Find a matching one-use shift by constant. 1476 const Register C1 = MI.getOperand(2).getReg(); 1477 auto MaybeImmVal = getIConstantVRegValWithLookThrough(C1, MRI); 1478 if (!MaybeImmVal) 1479 return false; 1480 1481 const uint64_t C1Val = MaybeImmVal->Value.getZExtValue(); 1482 1483 auto matchFirstShift = [&](const MachineInstr *MI, uint64_t &ShiftVal) { 1484 // Shift should match previous one and should be a one-use. 1485 if (MI->getOpcode() != ShiftOpcode || 1486 !MRI.hasOneNonDBGUse(MI->getOperand(0).getReg())) 1487 return false; 1488 1489 // Must be a constant. 1490 auto MaybeImmVal = 1491 getIConstantVRegValWithLookThrough(MI->getOperand(2).getReg(), MRI); 1492 if (!MaybeImmVal) 1493 return false; 1494 1495 ShiftVal = MaybeImmVal->Value.getSExtValue(); 1496 return true; 1497 }; 1498 1499 // Logic ops are commutative, so check each operand for a match. 1500 Register LogicMIReg1 = LogicMI->getOperand(1).getReg(); 1501 MachineInstr *LogicMIOp1 = MRI.getUniqueVRegDef(LogicMIReg1); 1502 Register LogicMIReg2 = LogicMI->getOperand(2).getReg(); 1503 MachineInstr *LogicMIOp2 = MRI.getUniqueVRegDef(LogicMIReg2); 1504 uint64_t C0Val; 1505 1506 if (matchFirstShift(LogicMIOp1, C0Val)) { 1507 MatchInfo.LogicNonShiftReg = LogicMIReg2; 1508 MatchInfo.Shift2 = LogicMIOp1; 1509 } else if (matchFirstShift(LogicMIOp2, C0Val)) { 1510 MatchInfo.LogicNonShiftReg = LogicMIReg1; 1511 MatchInfo.Shift2 = LogicMIOp2; 1512 } else 1513 return false; 1514 1515 MatchInfo.ValSum = C0Val + C1Val; 1516 1517 // The fold is not valid if the sum of the shift values exceeds bitwidth. 1518 if (MatchInfo.ValSum >= MRI.getType(LogicDest).getScalarSizeInBits()) 1519 return false; 1520 1521 MatchInfo.Logic = LogicMI; 1522 return true; 1523 } 1524 1525 void CombinerHelper::applyShiftOfShiftedLogic(MachineInstr &MI, 1526 ShiftOfShiftedLogic &MatchInfo) { 1527 unsigned Opcode = MI.getOpcode(); 1528 assert((Opcode == TargetOpcode::G_SHL || Opcode == TargetOpcode::G_ASHR || 1529 Opcode == TargetOpcode::G_LSHR || Opcode == TargetOpcode::G_USHLSAT || 1530 Opcode == TargetOpcode::G_SSHLSAT) && 1531 "Expected G_SHL, G_ASHR, G_LSHR, G_USHLSAT and G_SSHLSAT"); 1532 1533 LLT ShlType = MRI.getType(MI.getOperand(2).getReg()); 1534 LLT DestType = MRI.getType(MI.getOperand(0).getReg()); 1535 Builder.setInstrAndDebugLoc(MI); 1536 1537 Register Const = Builder.buildConstant(ShlType, MatchInfo.ValSum).getReg(0); 1538 1539 Register Shift1Base = MatchInfo.Shift2->getOperand(1).getReg(); 1540 Register Shift1 = 1541 Builder.buildInstr(Opcode, {DestType}, {Shift1Base, Const}).getReg(0); 1542 1543 Register Shift2Const = MI.getOperand(2).getReg(); 1544 Register Shift2 = Builder 1545 .buildInstr(Opcode, {DestType}, 1546 {MatchInfo.LogicNonShiftReg, Shift2Const}) 1547 .getReg(0); 1548 1549 Register Dest = MI.getOperand(0).getReg(); 1550 Builder.buildInstr(MatchInfo.Logic->getOpcode(), {Dest}, {Shift1, Shift2}); 1551 1552 // These were one use so it's safe to remove them. 1553 MatchInfo.Shift2->eraseFromParentAndMarkDBGValuesForRemoval(); 1554 MatchInfo.Logic->eraseFromParentAndMarkDBGValuesForRemoval(); 1555 1556 MI.eraseFromParent(); 1557 } 1558 1559 bool CombinerHelper::matchCombineMulToShl(MachineInstr &MI, 1560 unsigned &ShiftVal) { 1561 assert(MI.getOpcode() == TargetOpcode::G_MUL && "Expected a G_MUL"); 1562 auto MaybeImmVal = 1563 getIConstantVRegValWithLookThrough(MI.getOperand(2).getReg(), MRI); 1564 if (!MaybeImmVal) 1565 return false; 1566 1567 ShiftVal = MaybeImmVal->Value.exactLogBase2(); 1568 return (static_cast<int32_t>(ShiftVal) != -1); 1569 } 1570 1571 void CombinerHelper::applyCombineMulToShl(MachineInstr &MI, 1572 unsigned &ShiftVal) { 1573 assert(MI.getOpcode() == TargetOpcode::G_MUL && "Expected a G_MUL"); 1574 MachineIRBuilder MIB(MI); 1575 LLT ShiftTy = MRI.getType(MI.getOperand(0).getReg()); 1576 auto ShiftCst = MIB.buildConstant(ShiftTy, ShiftVal); 1577 Observer.changingInstr(MI); 1578 MI.setDesc(MIB.getTII().get(TargetOpcode::G_SHL)); 1579 MI.getOperand(2).setReg(ShiftCst.getReg(0)); 1580 Observer.changedInstr(MI); 1581 } 1582 1583 // shl ([sza]ext x), y => zext (shl x, y), if shift does not overflow source 1584 bool CombinerHelper::matchCombineShlOfExtend(MachineInstr &MI, 1585 RegisterImmPair &MatchData) { 1586 assert(MI.getOpcode() == TargetOpcode::G_SHL && KB); 1587 1588 Register LHS = MI.getOperand(1).getReg(); 1589 1590 Register ExtSrc; 1591 if (!mi_match(LHS, MRI, m_GAnyExt(m_Reg(ExtSrc))) && 1592 !mi_match(LHS, MRI, m_GZExt(m_Reg(ExtSrc))) && 1593 !mi_match(LHS, MRI, m_GSExt(m_Reg(ExtSrc)))) 1594 return false; 1595 1596 // TODO: Should handle vector splat. 1597 Register RHS = MI.getOperand(2).getReg(); 1598 auto MaybeShiftAmtVal = getIConstantVRegValWithLookThrough(RHS, MRI); 1599 if (!MaybeShiftAmtVal) 1600 return false; 1601 1602 if (LI) { 1603 LLT SrcTy = MRI.getType(ExtSrc); 1604 1605 // We only really care about the legality with the shifted value. We can 1606 // pick any type the constant shift amount, so ask the target what to 1607 // use. Otherwise we would have to guess and hope it is reported as legal. 1608 LLT ShiftAmtTy = getTargetLowering().getPreferredShiftAmountTy(SrcTy); 1609 if (!isLegalOrBeforeLegalizer({TargetOpcode::G_SHL, {SrcTy, ShiftAmtTy}})) 1610 return false; 1611 } 1612 1613 int64_t ShiftAmt = MaybeShiftAmtVal->Value.getSExtValue(); 1614 MatchData.Reg = ExtSrc; 1615 MatchData.Imm = ShiftAmt; 1616 1617 unsigned MinLeadingZeros = KB->getKnownZeroes(ExtSrc).countLeadingOnes(); 1618 return MinLeadingZeros >= ShiftAmt; 1619 } 1620 1621 void CombinerHelper::applyCombineShlOfExtend(MachineInstr &MI, 1622 const RegisterImmPair &MatchData) { 1623 Register ExtSrcReg = MatchData.Reg; 1624 int64_t ShiftAmtVal = MatchData.Imm; 1625 1626 LLT ExtSrcTy = MRI.getType(ExtSrcReg); 1627 Builder.setInstrAndDebugLoc(MI); 1628 auto ShiftAmt = Builder.buildConstant(ExtSrcTy, ShiftAmtVal); 1629 auto NarrowShift = 1630 Builder.buildShl(ExtSrcTy, ExtSrcReg, ShiftAmt, MI.getFlags()); 1631 Builder.buildZExt(MI.getOperand(0), NarrowShift); 1632 MI.eraseFromParent(); 1633 } 1634 1635 bool CombinerHelper::matchCombineMergeUnmerge(MachineInstr &MI, 1636 Register &MatchInfo) { 1637 GMerge &Merge = cast<GMerge>(MI); 1638 SmallVector<Register, 16> MergedValues; 1639 for (unsigned I = 0; I < Merge.getNumSources(); ++I) 1640 MergedValues.emplace_back(Merge.getSourceReg(I)); 1641 1642 auto *Unmerge = getOpcodeDef<GUnmerge>(MergedValues[0], MRI); 1643 if (!Unmerge || Unmerge->getNumDefs() != Merge.getNumSources()) 1644 return false; 1645 1646 for (unsigned I = 0; I < MergedValues.size(); ++I) 1647 if (MergedValues[I] != Unmerge->getReg(I)) 1648 return false; 1649 1650 MatchInfo = Unmerge->getSourceReg(); 1651 return true; 1652 } 1653 1654 static Register peekThroughBitcast(Register Reg, 1655 const MachineRegisterInfo &MRI) { 1656 while (mi_match(Reg, MRI, m_GBitcast(m_Reg(Reg)))) 1657 ; 1658 1659 return Reg; 1660 } 1661 1662 bool CombinerHelper::matchCombineUnmergeMergeToPlainValues( 1663 MachineInstr &MI, SmallVectorImpl<Register> &Operands) { 1664 assert(MI.getOpcode() == TargetOpcode::G_UNMERGE_VALUES && 1665 "Expected an unmerge"); 1666 auto &Unmerge = cast<GUnmerge>(MI); 1667 Register SrcReg = peekThroughBitcast(Unmerge.getSourceReg(), MRI); 1668 1669 auto *SrcInstr = getOpcodeDef<GMergeLikeOp>(SrcReg, MRI); 1670 if (!SrcInstr) 1671 return false; 1672 1673 // Check the source type of the merge. 1674 LLT SrcMergeTy = MRI.getType(SrcInstr->getSourceReg(0)); 1675 LLT Dst0Ty = MRI.getType(Unmerge.getReg(0)); 1676 bool SameSize = Dst0Ty.getSizeInBits() == SrcMergeTy.getSizeInBits(); 1677 if (SrcMergeTy != Dst0Ty && !SameSize) 1678 return false; 1679 // They are the same now (modulo a bitcast). 1680 // We can collect all the src registers. 1681 for (unsigned Idx = 0; Idx < SrcInstr->getNumSources(); ++Idx) 1682 Operands.push_back(SrcInstr->getSourceReg(Idx)); 1683 return true; 1684 } 1685 1686 void CombinerHelper::applyCombineUnmergeMergeToPlainValues( 1687 MachineInstr &MI, SmallVectorImpl<Register> &Operands) { 1688 assert(MI.getOpcode() == TargetOpcode::G_UNMERGE_VALUES && 1689 "Expected an unmerge"); 1690 assert((MI.getNumOperands() - 1 == Operands.size()) && 1691 "Not enough operands to replace all defs"); 1692 unsigned NumElems = MI.getNumOperands() - 1; 1693 1694 LLT SrcTy = MRI.getType(Operands[0]); 1695 LLT DstTy = MRI.getType(MI.getOperand(0).getReg()); 1696 bool CanReuseInputDirectly = DstTy == SrcTy; 1697 Builder.setInstrAndDebugLoc(MI); 1698 for (unsigned Idx = 0; Idx < NumElems; ++Idx) { 1699 Register DstReg = MI.getOperand(Idx).getReg(); 1700 Register SrcReg = Operands[Idx]; 1701 if (CanReuseInputDirectly) 1702 replaceRegWith(MRI, DstReg, SrcReg); 1703 else 1704 Builder.buildCast(DstReg, SrcReg); 1705 } 1706 MI.eraseFromParent(); 1707 } 1708 1709 bool CombinerHelper::matchCombineUnmergeConstant(MachineInstr &MI, 1710 SmallVectorImpl<APInt> &Csts) { 1711 unsigned SrcIdx = MI.getNumOperands() - 1; 1712 Register SrcReg = MI.getOperand(SrcIdx).getReg(); 1713 MachineInstr *SrcInstr = MRI.getVRegDef(SrcReg); 1714 if (SrcInstr->getOpcode() != TargetOpcode::G_CONSTANT && 1715 SrcInstr->getOpcode() != TargetOpcode::G_FCONSTANT) 1716 return false; 1717 // Break down the big constant in smaller ones. 1718 const MachineOperand &CstVal = SrcInstr->getOperand(1); 1719 APInt Val = SrcInstr->getOpcode() == TargetOpcode::G_CONSTANT 1720 ? CstVal.getCImm()->getValue() 1721 : CstVal.getFPImm()->getValueAPF().bitcastToAPInt(); 1722 1723 LLT Dst0Ty = MRI.getType(MI.getOperand(0).getReg()); 1724 unsigned ShiftAmt = Dst0Ty.getSizeInBits(); 1725 // Unmerge a constant. 1726 for (unsigned Idx = 0; Idx != SrcIdx; ++Idx) { 1727 Csts.emplace_back(Val.trunc(ShiftAmt)); 1728 Val = Val.lshr(ShiftAmt); 1729 } 1730 1731 return true; 1732 } 1733 1734 void CombinerHelper::applyCombineUnmergeConstant(MachineInstr &MI, 1735 SmallVectorImpl<APInt> &Csts) { 1736 assert(MI.getOpcode() == TargetOpcode::G_UNMERGE_VALUES && 1737 "Expected an unmerge"); 1738 assert((MI.getNumOperands() - 1 == Csts.size()) && 1739 "Not enough operands to replace all defs"); 1740 unsigned NumElems = MI.getNumOperands() - 1; 1741 Builder.setInstrAndDebugLoc(MI); 1742 for (unsigned Idx = 0; Idx < NumElems; ++Idx) { 1743 Register DstReg = MI.getOperand(Idx).getReg(); 1744 Builder.buildConstant(DstReg, Csts[Idx]); 1745 } 1746 1747 MI.eraseFromParent(); 1748 } 1749 1750 bool CombinerHelper::matchCombineUnmergeWithDeadLanesToTrunc(MachineInstr &MI) { 1751 assert(MI.getOpcode() == TargetOpcode::G_UNMERGE_VALUES && 1752 "Expected an unmerge"); 1753 // Check that all the lanes are dead except the first one. 1754 for (unsigned Idx = 1, EndIdx = MI.getNumDefs(); Idx != EndIdx; ++Idx) { 1755 if (!MRI.use_nodbg_empty(MI.getOperand(Idx).getReg())) 1756 return false; 1757 } 1758 return true; 1759 } 1760 1761 void CombinerHelper::applyCombineUnmergeWithDeadLanesToTrunc(MachineInstr &MI) { 1762 Builder.setInstrAndDebugLoc(MI); 1763 Register SrcReg = MI.getOperand(MI.getNumDefs()).getReg(); 1764 // Truncating a vector is going to truncate every single lane, 1765 // whereas we want the full lowbits. 1766 // Do the operation on a scalar instead. 1767 LLT SrcTy = MRI.getType(SrcReg); 1768 if (SrcTy.isVector()) 1769 SrcReg = 1770 Builder.buildCast(LLT::scalar(SrcTy.getSizeInBits()), SrcReg).getReg(0); 1771 1772 Register Dst0Reg = MI.getOperand(0).getReg(); 1773 LLT Dst0Ty = MRI.getType(Dst0Reg); 1774 if (Dst0Ty.isVector()) { 1775 auto MIB = Builder.buildTrunc(LLT::scalar(Dst0Ty.getSizeInBits()), SrcReg); 1776 Builder.buildCast(Dst0Reg, MIB); 1777 } else 1778 Builder.buildTrunc(Dst0Reg, SrcReg); 1779 MI.eraseFromParent(); 1780 } 1781 1782 bool CombinerHelper::matchCombineUnmergeZExtToZExt(MachineInstr &MI) { 1783 assert(MI.getOpcode() == TargetOpcode::G_UNMERGE_VALUES && 1784 "Expected an unmerge"); 1785 Register Dst0Reg = MI.getOperand(0).getReg(); 1786 LLT Dst0Ty = MRI.getType(Dst0Reg); 1787 // G_ZEXT on vector applies to each lane, so it will 1788 // affect all destinations. Therefore we won't be able 1789 // to simplify the unmerge to just the first definition. 1790 if (Dst0Ty.isVector()) 1791 return false; 1792 Register SrcReg = MI.getOperand(MI.getNumDefs()).getReg(); 1793 LLT SrcTy = MRI.getType(SrcReg); 1794 if (SrcTy.isVector()) 1795 return false; 1796 1797 Register ZExtSrcReg; 1798 if (!mi_match(SrcReg, MRI, m_GZExt(m_Reg(ZExtSrcReg)))) 1799 return false; 1800 1801 // Finally we can replace the first definition with 1802 // a zext of the source if the definition is big enough to hold 1803 // all of ZExtSrc bits. 1804 LLT ZExtSrcTy = MRI.getType(ZExtSrcReg); 1805 return ZExtSrcTy.getSizeInBits() <= Dst0Ty.getSizeInBits(); 1806 } 1807 1808 void CombinerHelper::applyCombineUnmergeZExtToZExt(MachineInstr &MI) { 1809 assert(MI.getOpcode() == TargetOpcode::G_UNMERGE_VALUES && 1810 "Expected an unmerge"); 1811 1812 Register Dst0Reg = MI.getOperand(0).getReg(); 1813 1814 MachineInstr *ZExtInstr = 1815 MRI.getVRegDef(MI.getOperand(MI.getNumDefs()).getReg()); 1816 assert(ZExtInstr && ZExtInstr->getOpcode() == TargetOpcode::G_ZEXT && 1817 "Expecting a G_ZEXT"); 1818 1819 Register ZExtSrcReg = ZExtInstr->getOperand(1).getReg(); 1820 LLT Dst0Ty = MRI.getType(Dst0Reg); 1821 LLT ZExtSrcTy = MRI.getType(ZExtSrcReg); 1822 1823 Builder.setInstrAndDebugLoc(MI); 1824 1825 if (Dst0Ty.getSizeInBits() > ZExtSrcTy.getSizeInBits()) { 1826 Builder.buildZExt(Dst0Reg, ZExtSrcReg); 1827 } else { 1828 assert(Dst0Ty.getSizeInBits() == ZExtSrcTy.getSizeInBits() && 1829 "ZExt src doesn't fit in destination"); 1830 replaceRegWith(MRI, Dst0Reg, ZExtSrcReg); 1831 } 1832 1833 Register ZeroReg; 1834 for (unsigned Idx = 1, EndIdx = MI.getNumDefs(); Idx != EndIdx; ++Idx) { 1835 if (!ZeroReg) 1836 ZeroReg = Builder.buildConstant(Dst0Ty, 0).getReg(0); 1837 replaceRegWith(MRI, MI.getOperand(Idx).getReg(), ZeroReg); 1838 } 1839 MI.eraseFromParent(); 1840 } 1841 1842 bool CombinerHelper::matchCombineShiftToUnmerge(MachineInstr &MI, 1843 unsigned TargetShiftSize, 1844 unsigned &ShiftVal) { 1845 assert((MI.getOpcode() == TargetOpcode::G_SHL || 1846 MI.getOpcode() == TargetOpcode::G_LSHR || 1847 MI.getOpcode() == TargetOpcode::G_ASHR) && "Expected a shift"); 1848 1849 LLT Ty = MRI.getType(MI.getOperand(0).getReg()); 1850 if (Ty.isVector()) // TODO: 1851 return false; 1852 1853 // Don't narrow further than the requested size. 1854 unsigned Size = Ty.getSizeInBits(); 1855 if (Size <= TargetShiftSize) 1856 return false; 1857 1858 auto MaybeImmVal = 1859 getIConstantVRegValWithLookThrough(MI.getOperand(2).getReg(), MRI); 1860 if (!MaybeImmVal) 1861 return false; 1862 1863 ShiftVal = MaybeImmVal->Value.getSExtValue(); 1864 return ShiftVal >= Size / 2 && ShiftVal < Size; 1865 } 1866 1867 void CombinerHelper::applyCombineShiftToUnmerge(MachineInstr &MI, 1868 const unsigned &ShiftVal) { 1869 Register DstReg = MI.getOperand(0).getReg(); 1870 Register SrcReg = MI.getOperand(1).getReg(); 1871 LLT Ty = MRI.getType(SrcReg); 1872 unsigned Size = Ty.getSizeInBits(); 1873 unsigned HalfSize = Size / 2; 1874 assert(ShiftVal >= HalfSize); 1875 1876 LLT HalfTy = LLT::scalar(HalfSize); 1877 1878 Builder.setInstr(MI); 1879 auto Unmerge = Builder.buildUnmerge(HalfTy, SrcReg); 1880 unsigned NarrowShiftAmt = ShiftVal - HalfSize; 1881 1882 if (MI.getOpcode() == TargetOpcode::G_LSHR) { 1883 Register Narrowed = Unmerge.getReg(1); 1884 1885 // dst = G_LSHR s64:x, C for C >= 32 1886 // => 1887 // lo, hi = G_UNMERGE_VALUES x 1888 // dst = G_MERGE_VALUES (G_LSHR hi, C - 32), 0 1889 1890 if (NarrowShiftAmt != 0) { 1891 Narrowed = Builder.buildLShr(HalfTy, Narrowed, 1892 Builder.buildConstant(HalfTy, NarrowShiftAmt)).getReg(0); 1893 } 1894 1895 auto Zero = Builder.buildConstant(HalfTy, 0); 1896 Builder.buildMerge(DstReg, { Narrowed, Zero }); 1897 } else if (MI.getOpcode() == TargetOpcode::G_SHL) { 1898 Register Narrowed = Unmerge.getReg(0); 1899 // dst = G_SHL s64:x, C for C >= 32 1900 // => 1901 // lo, hi = G_UNMERGE_VALUES x 1902 // dst = G_MERGE_VALUES 0, (G_SHL hi, C - 32) 1903 if (NarrowShiftAmt != 0) { 1904 Narrowed = Builder.buildShl(HalfTy, Narrowed, 1905 Builder.buildConstant(HalfTy, NarrowShiftAmt)).getReg(0); 1906 } 1907 1908 auto Zero = Builder.buildConstant(HalfTy, 0); 1909 Builder.buildMerge(DstReg, { Zero, Narrowed }); 1910 } else { 1911 assert(MI.getOpcode() == TargetOpcode::G_ASHR); 1912 auto Hi = Builder.buildAShr( 1913 HalfTy, Unmerge.getReg(1), 1914 Builder.buildConstant(HalfTy, HalfSize - 1)); 1915 1916 if (ShiftVal == HalfSize) { 1917 // (G_ASHR i64:x, 32) -> 1918 // G_MERGE_VALUES hi_32(x), (G_ASHR hi_32(x), 31) 1919 Builder.buildMerge(DstReg, { Unmerge.getReg(1), Hi }); 1920 } else if (ShiftVal == Size - 1) { 1921 // Don't need a second shift. 1922 // (G_ASHR i64:x, 63) -> 1923 // %narrowed = (G_ASHR hi_32(x), 31) 1924 // G_MERGE_VALUES %narrowed, %narrowed 1925 Builder.buildMerge(DstReg, { Hi, Hi }); 1926 } else { 1927 auto Lo = Builder.buildAShr( 1928 HalfTy, Unmerge.getReg(1), 1929 Builder.buildConstant(HalfTy, ShiftVal - HalfSize)); 1930 1931 // (G_ASHR i64:x, C) ->, for C >= 32 1932 // G_MERGE_VALUES (G_ASHR hi_32(x), C - 32), (G_ASHR hi_32(x), 31) 1933 Builder.buildMerge(DstReg, { Lo, Hi }); 1934 } 1935 } 1936 1937 MI.eraseFromParent(); 1938 } 1939 1940 bool CombinerHelper::tryCombineShiftToUnmerge(MachineInstr &MI, 1941 unsigned TargetShiftAmount) { 1942 unsigned ShiftAmt; 1943 if (matchCombineShiftToUnmerge(MI, TargetShiftAmount, ShiftAmt)) { 1944 applyCombineShiftToUnmerge(MI, ShiftAmt); 1945 return true; 1946 } 1947 1948 return false; 1949 } 1950 1951 bool CombinerHelper::matchCombineI2PToP2I(MachineInstr &MI, Register &Reg) { 1952 assert(MI.getOpcode() == TargetOpcode::G_INTTOPTR && "Expected a G_INTTOPTR"); 1953 Register DstReg = MI.getOperand(0).getReg(); 1954 LLT DstTy = MRI.getType(DstReg); 1955 Register SrcReg = MI.getOperand(1).getReg(); 1956 return mi_match(SrcReg, MRI, 1957 m_GPtrToInt(m_all_of(m_SpecificType(DstTy), m_Reg(Reg)))); 1958 } 1959 1960 void CombinerHelper::applyCombineI2PToP2I(MachineInstr &MI, Register &Reg) { 1961 assert(MI.getOpcode() == TargetOpcode::G_INTTOPTR && "Expected a G_INTTOPTR"); 1962 Register DstReg = MI.getOperand(0).getReg(); 1963 Builder.setInstr(MI); 1964 Builder.buildCopy(DstReg, Reg); 1965 MI.eraseFromParent(); 1966 } 1967 1968 bool CombinerHelper::matchCombineP2IToI2P(MachineInstr &MI, Register &Reg) { 1969 assert(MI.getOpcode() == TargetOpcode::G_PTRTOINT && "Expected a G_PTRTOINT"); 1970 Register SrcReg = MI.getOperand(1).getReg(); 1971 return mi_match(SrcReg, MRI, m_GIntToPtr(m_Reg(Reg))); 1972 } 1973 1974 void CombinerHelper::applyCombineP2IToI2P(MachineInstr &MI, Register &Reg) { 1975 assert(MI.getOpcode() == TargetOpcode::G_PTRTOINT && "Expected a G_PTRTOINT"); 1976 Register DstReg = MI.getOperand(0).getReg(); 1977 Builder.setInstr(MI); 1978 Builder.buildZExtOrTrunc(DstReg, Reg); 1979 MI.eraseFromParent(); 1980 } 1981 1982 bool CombinerHelper::matchCombineAddP2IToPtrAdd( 1983 MachineInstr &MI, std::pair<Register, bool> &PtrReg) { 1984 assert(MI.getOpcode() == TargetOpcode::G_ADD); 1985 Register LHS = MI.getOperand(1).getReg(); 1986 Register RHS = MI.getOperand(2).getReg(); 1987 LLT IntTy = MRI.getType(LHS); 1988 1989 // G_PTR_ADD always has the pointer in the LHS, so we may need to commute the 1990 // instruction. 1991 PtrReg.second = false; 1992 for (Register SrcReg : {LHS, RHS}) { 1993 if (mi_match(SrcReg, MRI, m_GPtrToInt(m_Reg(PtrReg.first)))) { 1994 // Don't handle cases where the integer is implicitly converted to the 1995 // pointer width. 1996 LLT PtrTy = MRI.getType(PtrReg.first); 1997 if (PtrTy.getScalarSizeInBits() == IntTy.getScalarSizeInBits()) 1998 return true; 1999 } 2000 2001 PtrReg.second = true; 2002 } 2003 2004 return false; 2005 } 2006 2007 void CombinerHelper::applyCombineAddP2IToPtrAdd( 2008 MachineInstr &MI, std::pair<Register, bool> &PtrReg) { 2009 Register Dst = MI.getOperand(0).getReg(); 2010 Register LHS = MI.getOperand(1).getReg(); 2011 Register RHS = MI.getOperand(2).getReg(); 2012 2013 const bool DoCommute = PtrReg.second; 2014 if (DoCommute) 2015 std::swap(LHS, RHS); 2016 LHS = PtrReg.first; 2017 2018 LLT PtrTy = MRI.getType(LHS); 2019 2020 Builder.setInstrAndDebugLoc(MI); 2021 auto PtrAdd = Builder.buildPtrAdd(PtrTy, LHS, RHS); 2022 Builder.buildPtrToInt(Dst, PtrAdd); 2023 MI.eraseFromParent(); 2024 } 2025 2026 bool CombinerHelper::matchCombineConstPtrAddToI2P(MachineInstr &MI, 2027 int64_t &NewCst) { 2028 auto &PtrAdd = cast<GPtrAdd>(MI); 2029 Register LHS = PtrAdd.getBaseReg(); 2030 Register RHS = PtrAdd.getOffsetReg(); 2031 MachineRegisterInfo &MRI = Builder.getMF().getRegInfo(); 2032 2033 if (auto RHSCst = getIConstantVRegSExtVal(RHS, MRI)) { 2034 int64_t Cst; 2035 if (mi_match(LHS, MRI, m_GIntToPtr(m_ICst(Cst)))) { 2036 NewCst = Cst + *RHSCst; 2037 return true; 2038 } 2039 } 2040 2041 return false; 2042 } 2043 2044 void CombinerHelper::applyCombineConstPtrAddToI2P(MachineInstr &MI, 2045 int64_t &NewCst) { 2046 auto &PtrAdd = cast<GPtrAdd>(MI); 2047 Register Dst = PtrAdd.getReg(0); 2048 2049 Builder.setInstrAndDebugLoc(MI); 2050 Builder.buildConstant(Dst, NewCst); 2051 PtrAdd.eraseFromParent(); 2052 } 2053 2054 bool CombinerHelper::matchCombineAnyExtTrunc(MachineInstr &MI, Register &Reg) { 2055 assert(MI.getOpcode() == TargetOpcode::G_ANYEXT && "Expected a G_ANYEXT"); 2056 Register DstReg = MI.getOperand(0).getReg(); 2057 Register SrcReg = MI.getOperand(1).getReg(); 2058 LLT DstTy = MRI.getType(DstReg); 2059 return mi_match(SrcReg, MRI, 2060 m_GTrunc(m_all_of(m_Reg(Reg), m_SpecificType(DstTy)))); 2061 } 2062 2063 bool CombinerHelper::matchCombineZextTrunc(MachineInstr &MI, Register &Reg) { 2064 assert(MI.getOpcode() == TargetOpcode::G_ZEXT && "Expected a G_ZEXT"); 2065 Register DstReg = MI.getOperand(0).getReg(); 2066 Register SrcReg = MI.getOperand(1).getReg(); 2067 LLT DstTy = MRI.getType(DstReg); 2068 if (mi_match(SrcReg, MRI, 2069 m_GTrunc(m_all_of(m_Reg(Reg), m_SpecificType(DstTy))))) { 2070 unsigned DstSize = DstTy.getScalarSizeInBits(); 2071 unsigned SrcSize = MRI.getType(SrcReg).getScalarSizeInBits(); 2072 return KB->getKnownBits(Reg).countMinLeadingZeros() >= DstSize - SrcSize; 2073 } 2074 return false; 2075 } 2076 2077 bool CombinerHelper::matchCombineExtOfExt( 2078 MachineInstr &MI, std::tuple<Register, unsigned> &MatchInfo) { 2079 assert((MI.getOpcode() == TargetOpcode::G_ANYEXT || 2080 MI.getOpcode() == TargetOpcode::G_SEXT || 2081 MI.getOpcode() == TargetOpcode::G_ZEXT) && 2082 "Expected a G_[ASZ]EXT"); 2083 Register SrcReg = MI.getOperand(1).getReg(); 2084 MachineInstr *SrcMI = MRI.getVRegDef(SrcReg); 2085 // Match exts with the same opcode, anyext([sz]ext) and sext(zext). 2086 unsigned Opc = MI.getOpcode(); 2087 unsigned SrcOpc = SrcMI->getOpcode(); 2088 if (Opc == SrcOpc || 2089 (Opc == TargetOpcode::G_ANYEXT && 2090 (SrcOpc == TargetOpcode::G_SEXT || SrcOpc == TargetOpcode::G_ZEXT)) || 2091 (Opc == TargetOpcode::G_SEXT && SrcOpc == TargetOpcode::G_ZEXT)) { 2092 MatchInfo = std::make_tuple(SrcMI->getOperand(1).getReg(), SrcOpc); 2093 return true; 2094 } 2095 return false; 2096 } 2097 2098 void CombinerHelper::applyCombineExtOfExt( 2099 MachineInstr &MI, std::tuple<Register, unsigned> &MatchInfo) { 2100 assert((MI.getOpcode() == TargetOpcode::G_ANYEXT || 2101 MI.getOpcode() == TargetOpcode::G_SEXT || 2102 MI.getOpcode() == TargetOpcode::G_ZEXT) && 2103 "Expected a G_[ASZ]EXT"); 2104 2105 Register Reg = std::get<0>(MatchInfo); 2106 unsigned SrcExtOp = std::get<1>(MatchInfo); 2107 2108 // Combine exts with the same opcode. 2109 if (MI.getOpcode() == SrcExtOp) { 2110 Observer.changingInstr(MI); 2111 MI.getOperand(1).setReg(Reg); 2112 Observer.changedInstr(MI); 2113 return; 2114 } 2115 2116 // Combine: 2117 // - anyext([sz]ext x) to [sz]ext x 2118 // - sext(zext x) to zext x 2119 if (MI.getOpcode() == TargetOpcode::G_ANYEXT || 2120 (MI.getOpcode() == TargetOpcode::G_SEXT && 2121 SrcExtOp == TargetOpcode::G_ZEXT)) { 2122 Register DstReg = MI.getOperand(0).getReg(); 2123 Builder.setInstrAndDebugLoc(MI); 2124 Builder.buildInstr(SrcExtOp, {DstReg}, {Reg}); 2125 MI.eraseFromParent(); 2126 } 2127 } 2128 2129 void CombinerHelper::applyCombineMulByNegativeOne(MachineInstr &MI) { 2130 assert(MI.getOpcode() == TargetOpcode::G_MUL && "Expected a G_MUL"); 2131 Register DstReg = MI.getOperand(0).getReg(); 2132 Register SrcReg = MI.getOperand(1).getReg(); 2133 LLT DstTy = MRI.getType(DstReg); 2134 2135 Builder.setInstrAndDebugLoc(MI); 2136 Builder.buildSub(DstReg, Builder.buildConstant(DstTy, 0), SrcReg, 2137 MI.getFlags()); 2138 MI.eraseFromParent(); 2139 } 2140 2141 bool CombinerHelper::matchCombineFNegOfFNeg(MachineInstr &MI, Register &Reg) { 2142 assert(MI.getOpcode() == TargetOpcode::G_FNEG && "Expected a G_FNEG"); 2143 Register SrcReg = MI.getOperand(1).getReg(); 2144 return mi_match(SrcReg, MRI, m_GFNeg(m_Reg(Reg))); 2145 } 2146 2147 bool CombinerHelper::matchCombineFAbsOfFAbs(MachineInstr &MI, Register &Src) { 2148 assert(MI.getOpcode() == TargetOpcode::G_FABS && "Expected a G_FABS"); 2149 Src = MI.getOperand(1).getReg(); 2150 Register AbsSrc; 2151 return mi_match(Src, MRI, m_GFabs(m_Reg(AbsSrc))); 2152 } 2153 2154 bool CombinerHelper::matchCombineFAbsOfFNeg(MachineInstr &MI, 2155 BuildFnTy &MatchInfo) { 2156 assert(MI.getOpcode() == TargetOpcode::G_FABS && "Expected a G_FABS"); 2157 Register Src = MI.getOperand(1).getReg(); 2158 Register NegSrc; 2159 2160 if (!mi_match(Src, MRI, m_GFNeg(m_Reg(NegSrc)))) 2161 return false; 2162 2163 MatchInfo = [=, &MI](MachineIRBuilder &B) { 2164 Observer.changingInstr(MI); 2165 MI.getOperand(1).setReg(NegSrc); 2166 Observer.changedInstr(MI); 2167 }; 2168 return true; 2169 } 2170 2171 bool CombinerHelper::matchCombineTruncOfExt( 2172 MachineInstr &MI, std::pair<Register, unsigned> &MatchInfo) { 2173 assert(MI.getOpcode() == TargetOpcode::G_TRUNC && "Expected a G_TRUNC"); 2174 Register SrcReg = MI.getOperand(1).getReg(); 2175 MachineInstr *SrcMI = MRI.getVRegDef(SrcReg); 2176 unsigned SrcOpc = SrcMI->getOpcode(); 2177 if (SrcOpc == TargetOpcode::G_ANYEXT || SrcOpc == TargetOpcode::G_SEXT || 2178 SrcOpc == TargetOpcode::G_ZEXT) { 2179 MatchInfo = std::make_pair(SrcMI->getOperand(1).getReg(), SrcOpc); 2180 return true; 2181 } 2182 return false; 2183 } 2184 2185 void CombinerHelper::applyCombineTruncOfExt( 2186 MachineInstr &MI, std::pair<Register, unsigned> &MatchInfo) { 2187 assert(MI.getOpcode() == TargetOpcode::G_TRUNC && "Expected a G_TRUNC"); 2188 Register SrcReg = MatchInfo.first; 2189 unsigned SrcExtOp = MatchInfo.second; 2190 Register DstReg = MI.getOperand(0).getReg(); 2191 LLT SrcTy = MRI.getType(SrcReg); 2192 LLT DstTy = MRI.getType(DstReg); 2193 if (SrcTy == DstTy) { 2194 MI.eraseFromParent(); 2195 replaceRegWith(MRI, DstReg, SrcReg); 2196 return; 2197 } 2198 Builder.setInstrAndDebugLoc(MI); 2199 if (SrcTy.getSizeInBits() < DstTy.getSizeInBits()) 2200 Builder.buildInstr(SrcExtOp, {DstReg}, {SrcReg}); 2201 else 2202 Builder.buildTrunc(DstReg, SrcReg); 2203 MI.eraseFromParent(); 2204 } 2205 2206 bool CombinerHelper::matchCombineTruncOfShl( 2207 MachineInstr &MI, std::pair<Register, Register> &MatchInfo) { 2208 assert(MI.getOpcode() == TargetOpcode::G_TRUNC && "Expected a G_TRUNC"); 2209 Register DstReg = MI.getOperand(0).getReg(); 2210 Register SrcReg = MI.getOperand(1).getReg(); 2211 LLT DstTy = MRI.getType(DstReg); 2212 Register ShiftSrc; 2213 Register ShiftAmt; 2214 2215 if (MRI.hasOneNonDBGUse(SrcReg) && 2216 mi_match(SrcReg, MRI, m_GShl(m_Reg(ShiftSrc), m_Reg(ShiftAmt))) && 2217 isLegalOrBeforeLegalizer( 2218 {TargetOpcode::G_SHL, 2219 {DstTy, getTargetLowering().getPreferredShiftAmountTy(DstTy)}})) { 2220 KnownBits Known = KB->getKnownBits(ShiftAmt); 2221 unsigned Size = DstTy.getSizeInBits(); 2222 if (Known.countMaxActiveBits() <= Log2_32(Size)) { 2223 MatchInfo = std::make_pair(ShiftSrc, ShiftAmt); 2224 return true; 2225 } 2226 } 2227 return false; 2228 } 2229 2230 void CombinerHelper::applyCombineTruncOfShl( 2231 MachineInstr &MI, std::pair<Register, Register> &MatchInfo) { 2232 assert(MI.getOpcode() == TargetOpcode::G_TRUNC && "Expected a G_TRUNC"); 2233 Register DstReg = MI.getOperand(0).getReg(); 2234 Register SrcReg = MI.getOperand(1).getReg(); 2235 LLT DstTy = MRI.getType(DstReg); 2236 MachineInstr *SrcMI = MRI.getVRegDef(SrcReg); 2237 2238 Register ShiftSrc = MatchInfo.first; 2239 Register ShiftAmt = MatchInfo.second; 2240 Builder.setInstrAndDebugLoc(MI); 2241 auto TruncShiftSrc = Builder.buildTrunc(DstTy, ShiftSrc); 2242 Builder.buildShl(DstReg, TruncShiftSrc, ShiftAmt, SrcMI->getFlags()); 2243 MI.eraseFromParent(); 2244 } 2245 2246 bool CombinerHelper::matchAnyExplicitUseIsUndef(MachineInstr &MI) { 2247 return any_of(MI.explicit_uses(), [this](const MachineOperand &MO) { 2248 return MO.isReg() && 2249 getOpcodeDef(TargetOpcode::G_IMPLICIT_DEF, MO.getReg(), MRI); 2250 }); 2251 } 2252 2253 bool CombinerHelper::matchAllExplicitUsesAreUndef(MachineInstr &MI) { 2254 return all_of(MI.explicit_uses(), [this](const MachineOperand &MO) { 2255 return !MO.isReg() || 2256 getOpcodeDef(TargetOpcode::G_IMPLICIT_DEF, MO.getReg(), MRI); 2257 }); 2258 } 2259 2260 bool CombinerHelper::matchUndefShuffleVectorMask(MachineInstr &MI) { 2261 assert(MI.getOpcode() == TargetOpcode::G_SHUFFLE_VECTOR); 2262 ArrayRef<int> Mask = MI.getOperand(3).getShuffleMask(); 2263 return all_of(Mask, [](int Elt) { return Elt < 0; }); 2264 } 2265 2266 bool CombinerHelper::matchUndefStore(MachineInstr &MI) { 2267 assert(MI.getOpcode() == TargetOpcode::G_STORE); 2268 return getOpcodeDef(TargetOpcode::G_IMPLICIT_DEF, MI.getOperand(0).getReg(), 2269 MRI); 2270 } 2271 2272 bool CombinerHelper::matchUndefSelectCmp(MachineInstr &MI) { 2273 assert(MI.getOpcode() == TargetOpcode::G_SELECT); 2274 return getOpcodeDef(TargetOpcode::G_IMPLICIT_DEF, MI.getOperand(1).getReg(), 2275 MRI); 2276 } 2277 2278 bool CombinerHelper::matchConstantSelectCmp(MachineInstr &MI, unsigned &OpIdx) { 2279 GSelect &SelMI = cast<GSelect>(MI); 2280 auto Cst = 2281 isConstantOrConstantSplatVector(*MRI.getVRegDef(SelMI.getCondReg()), MRI); 2282 if (!Cst) 2283 return false; 2284 OpIdx = Cst->isZero() ? 3 : 2; 2285 return true; 2286 } 2287 2288 bool CombinerHelper::eraseInst(MachineInstr &MI) { 2289 MI.eraseFromParent(); 2290 return true; 2291 } 2292 2293 bool CombinerHelper::matchEqualDefs(const MachineOperand &MOP1, 2294 const MachineOperand &MOP2) { 2295 if (!MOP1.isReg() || !MOP2.isReg()) 2296 return false; 2297 auto InstAndDef1 = getDefSrcRegIgnoringCopies(MOP1.getReg(), MRI); 2298 if (!InstAndDef1) 2299 return false; 2300 auto InstAndDef2 = getDefSrcRegIgnoringCopies(MOP2.getReg(), MRI); 2301 if (!InstAndDef2) 2302 return false; 2303 MachineInstr *I1 = InstAndDef1->MI; 2304 MachineInstr *I2 = InstAndDef2->MI; 2305 2306 // Handle a case like this: 2307 // 2308 // %0:_(s64), %1:_(s64) = G_UNMERGE_VALUES %2:_(<2 x s64>) 2309 // 2310 // Even though %0 and %1 are produced by the same instruction they are not 2311 // the same values. 2312 if (I1 == I2) 2313 return MOP1.getReg() == MOP2.getReg(); 2314 2315 // If we have an instruction which loads or stores, we can't guarantee that 2316 // it is identical. 2317 // 2318 // For example, we may have 2319 // 2320 // %x1 = G_LOAD %addr (load N from @somewhere) 2321 // ... 2322 // call @foo 2323 // ... 2324 // %x2 = G_LOAD %addr (load N from @somewhere) 2325 // ... 2326 // %or = G_OR %x1, %x2 2327 // 2328 // It's possible that @foo will modify whatever lives at the address we're 2329 // loading from. To be safe, let's just assume that all loads and stores 2330 // are different (unless we have something which is guaranteed to not 2331 // change.) 2332 if (I1->mayLoadOrStore() && !I1->isDereferenceableInvariantLoad(nullptr)) 2333 return false; 2334 2335 // Check for physical registers on the instructions first to avoid cases 2336 // like this: 2337 // 2338 // %a = COPY $physreg 2339 // ... 2340 // SOMETHING implicit-def $physreg 2341 // ... 2342 // %b = COPY $physreg 2343 // 2344 // These copies are not equivalent. 2345 if (any_of(I1->uses(), [](const MachineOperand &MO) { 2346 return MO.isReg() && MO.getReg().isPhysical(); 2347 })) { 2348 // Check if we have a case like this: 2349 // 2350 // %a = COPY $physreg 2351 // %b = COPY %a 2352 // 2353 // In this case, I1 and I2 will both be equal to %a = COPY $physreg. 2354 // From that, we know that they must have the same value, since they must 2355 // have come from the same COPY. 2356 return I1->isIdenticalTo(*I2); 2357 } 2358 2359 // We don't have any physical registers, so we don't necessarily need the 2360 // same vreg defs. 2361 // 2362 // On the off-chance that there's some target instruction feeding into the 2363 // instruction, let's use produceSameValue instead of isIdenticalTo. 2364 if (Builder.getTII().produceSameValue(*I1, *I2, &MRI)) { 2365 // Handle instructions with multiple defs that produce same values. Values 2366 // are same for operands with same index. 2367 // %0:_(s8), %1:_(s8), %2:_(s8), %3:_(s8) = G_UNMERGE_VALUES %4:_(<4 x s8>) 2368 // %5:_(s8), %6:_(s8), %7:_(s8), %8:_(s8) = G_UNMERGE_VALUES %4:_(<4 x s8>) 2369 // I1 and I2 are different instructions but produce same values, 2370 // %1 and %6 are same, %1 and %7 are not the same value. 2371 return I1->findRegisterDefOperandIdx(InstAndDef1->Reg) == 2372 I2->findRegisterDefOperandIdx(InstAndDef2->Reg); 2373 } 2374 return false; 2375 } 2376 2377 bool CombinerHelper::matchConstantOp(const MachineOperand &MOP, int64_t C) { 2378 if (!MOP.isReg()) 2379 return false; 2380 auto *MI = MRI.getVRegDef(MOP.getReg()); 2381 auto MaybeCst = isConstantOrConstantSplatVector(*MI, MRI); 2382 return MaybeCst.hasValue() && MaybeCst->getBitWidth() <= 64 && 2383 MaybeCst->getSExtValue() == C; 2384 } 2385 2386 bool CombinerHelper::replaceSingleDefInstWithOperand(MachineInstr &MI, 2387 unsigned OpIdx) { 2388 assert(MI.getNumExplicitDefs() == 1 && "Expected one explicit def?"); 2389 Register OldReg = MI.getOperand(0).getReg(); 2390 Register Replacement = MI.getOperand(OpIdx).getReg(); 2391 assert(canReplaceReg(OldReg, Replacement, MRI) && "Cannot replace register?"); 2392 MI.eraseFromParent(); 2393 replaceRegWith(MRI, OldReg, Replacement); 2394 return true; 2395 } 2396 2397 bool CombinerHelper::replaceSingleDefInstWithReg(MachineInstr &MI, 2398 Register Replacement) { 2399 assert(MI.getNumExplicitDefs() == 1 && "Expected one explicit def?"); 2400 Register OldReg = MI.getOperand(0).getReg(); 2401 assert(canReplaceReg(OldReg, Replacement, MRI) && "Cannot replace register?"); 2402 MI.eraseFromParent(); 2403 replaceRegWith(MRI, OldReg, Replacement); 2404 return true; 2405 } 2406 2407 bool CombinerHelper::matchSelectSameVal(MachineInstr &MI) { 2408 assert(MI.getOpcode() == TargetOpcode::G_SELECT); 2409 // Match (cond ? x : x) 2410 return matchEqualDefs(MI.getOperand(2), MI.getOperand(3)) && 2411 canReplaceReg(MI.getOperand(0).getReg(), MI.getOperand(2).getReg(), 2412 MRI); 2413 } 2414 2415 bool CombinerHelper::matchBinOpSameVal(MachineInstr &MI) { 2416 return matchEqualDefs(MI.getOperand(1), MI.getOperand(2)) && 2417 canReplaceReg(MI.getOperand(0).getReg(), MI.getOperand(1).getReg(), 2418 MRI); 2419 } 2420 2421 bool CombinerHelper::matchOperandIsZero(MachineInstr &MI, unsigned OpIdx) { 2422 return matchConstantOp(MI.getOperand(OpIdx), 0) && 2423 canReplaceReg(MI.getOperand(0).getReg(), MI.getOperand(OpIdx).getReg(), 2424 MRI); 2425 } 2426 2427 bool CombinerHelper::matchOperandIsUndef(MachineInstr &MI, unsigned OpIdx) { 2428 MachineOperand &MO = MI.getOperand(OpIdx); 2429 return MO.isReg() && 2430 getOpcodeDef(TargetOpcode::G_IMPLICIT_DEF, MO.getReg(), MRI); 2431 } 2432 2433 bool CombinerHelper::matchOperandIsKnownToBeAPowerOfTwo(MachineInstr &MI, 2434 unsigned OpIdx) { 2435 MachineOperand &MO = MI.getOperand(OpIdx); 2436 return isKnownToBeAPowerOfTwo(MO.getReg(), MRI, KB); 2437 } 2438 2439 bool CombinerHelper::replaceInstWithFConstant(MachineInstr &MI, double C) { 2440 assert(MI.getNumDefs() == 1 && "Expected only one def?"); 2441 Builder.setInstr(MI); 2442 Builder.buildFConstant(MI.getOperand(0), C); 2443 MI.eraseFromParent(); 2444 return true; 2445 } 2446 2447 bool CombinerHelper::replaceInstWithConstant(MachineInstr &MI, int64_t C) { 2448 assert(MI.getNumDefs() == 1 && "Expected only one def?"); 2449 Builder.setInstr(MI); 2450 Builder.buildConstant(MI.getOperand(0), C); 2451 MI.eraseFromParent(); 2452 return true; 2453 } 2454 2455 bool CombinerHelper::replaceInstWithConstant(MachineInstr &MI, APInt C) { 2456 assert(MI.getNumDefs() == 1 && "Expected only one def?"); 2457 Builder.setInstr(MI); 2458 Builder.buildConstant(MI.getOperand(0), C); 2459 MI.eraseFromParent(); 2460 return true; 2461 } 2462 2463 bool CombinerHelper::replaceInstWithUndef(MachineInstr &MI) { 2464 assert(MI.getNumDefs() == 1 && "Expected only one def?"); 2465 Builder.setInstr(MI); 2466 Builder.buildUndef(MI.getOperand(0)); 2467 MI.eraseFromParent(); 2468 return true; 2469 } 2470 2471 bool CombinerHelper::matchSimplifyAddToSub( 2472 MachineInstr &MI, std::tuple<Register, Register> &MatchInfo) { 2473 Register LHS = MI.getOperand(1).getReg(); 2474 Register RHS = MI.getOperand(2).getReg(); 2475 Register &NewLHS = std::get<0>(MatchInfo); 2476 Register &NewRHS = std::get<1>(MatchInfo); 2477 2478 // Helper lambda to check for opportunities for 2479 // ((0-A) + B) -> B - A 2480 // (A + (0-B)) -> A - B 2481 auto CheckFold = [&](Register &MaybeSub, Register &MaybeNewLHS) { 2482 if (!mi_match(MaybeSub, MRI, m_Neg(m_Reg(NewRHS)))) 2483 return false; 2484 NewLHS = MaybeNewLHS; 2485 return true; 2486 }; 2487 2488 return CheckFold(LHS, RHS) || CheckFold(RHS, LHS); 2489 } 2490 2491 bool CombinerHelper::matchCombineInsertVecElts( 2492 MachineInstr &MI, SmallVectorImpl<Register> &MatchInfo) { 2493 assert(MI.getOpcode() == TargetOpcode::G_INSERT_VECTOR_ELT && 2494 "Invalid opcode"); 2495 Register DstReg = MI.getOperand(0).getReg(); 2496 LLT DstTy = MRI.getType(DstReg); 2497 assert(DstTy.isVector() && "Invalid G_INSERT_VECTOR_ELT?"); 2498 unsigned NumElts = DstTy.getNumElements(); 2499 // If this MI is part of a sequence of insert_vec_elts, then 2500 // don't do the combine in the middle of the sequence. 2501 if (MRI.hasOneUse(DstReg) && MRI.use_instr_begin(DstReg)->getOpcode() == 2502 TargetOpcode::G_INSERT_VECTOR_ELT) 2503 return false; 2504 MachineInstr *CurrInst = &MI; 2505 MachineInstr *TmpInst; 2506 int64_t IntImm; 2507 Register TmpReg; 2508 MatchInfo.resize(NumElts); 2509 while (mi_match( 2510 CurrInst->getOperand(0).getReg(), MRI, 2511 m_GInsertVecElt(m_MInstr(TmpInst), m_Reg(TmpReg), m_ICst(IntImm)))) { 2512 if (IntImm >= NumElts) 2513 return false; 2514 if (!MatchInfo[IntImm]) 2515 MatchInfo[IntImm] = TmpReg; 2516 CurrInst = TmpInst; 2517 } 2518 // Variable index. 2519 if (CurrInst->getOpcode() == TargetOpcode::G_INSERT_VECTOR_ELT) 2520 return false; 2521 if (TmpInst->getOpcode() == TargetOpcode::G_BUILD_VECTOR) { 2522 for (unsigned I = 1; I < TmpInst->getNumOperands(); ++I) { 2523 if (!MatchInfo[I - 1].isValid()) 2524 MatchInfo[I - 1] = TmpInst->getOperand(I).getReg(); 2525 } 2526 return true; 2527 } 2528 // If we didn't end in a G_IMPLICIT_DEF, bail out. 2529 return TmpInst->getOpcode() == TargetOpcode::G_IMPLICIT_DEF; 2530 } 2531 2532 void CombinerHelper::applyCombineInsertVecElts( 2533 MachineInstr &MI, SmallVectorImpl<Register> &MatchInfo) { 2534 Builder.setInstr(MI); 2535 Register UndefReg; 2536 auto GetUndef = [&]() { 2537 if (UndefReg) 2538 return UndefReg; 2539 LLT DstTy = MRI.getType(MI.getOperand(0).getReg()); 2540 UndefReg = Builder.buildUndef(DstTy.getScalarType()).getReg(0); 2541 return UndefReg; 2542 }; 2543 for (unsigned I = 0; I < MatchInfo.size(); ++I) { 2544 if (!MatchInfo[I]) 2545 MatchInfo[I] = GetUndef(); 2546 } 2547 Builder.buildBuildVector(MI.getOperand(0).getReg(), MatchInfo); 2548 MI.eraseFromParent(); 2549 } 2550 2551 void CombinerHelper::applySimplifyAddToSub( 2552 MachineInstr &MI, std::tuple<Register, Register> &MatchInfo) { 2553 Builder.setInstr(MI); 2554 Register SubLHS, SubRHS; 2555 std::tie(SubLHS, SubRHS) = MatchInfo; 2556 Builder.buildSub(MI.getOperand(0).getReg(), SubLHS, SubRHS); 2557 MI.eraseFromParent(); 2558 } 2559 2560 bool CombinerHelper::matchHoistLogicOpWithSameOpcodeHands( 2561 MachineInstr &MI, InstructionStepsMatchInfo &MatchInfo) { 2562 // Matches: logic (hand x, ...), (hand y, ...) -> hand (logic x, y), ... 2563 // 2564 // Creates the new hand + logic instruction (but does not insert them.) 2565 // 2566 // On success, MatchInfo is populated with the new instructions. These are 2567 // inserted in applyHoistLogicOpWithSameOpcodeHands. 2568 unsigned LogicOpcode = MI.getOpcode(); 2569 assert(LogicOpcode == TargetOpcode::G_AND || 2570 LogicOpcode == TargetOpcode::G_OR || 2571 LogicOpcode == TargetOpcode::G_XOR); 2572 MachineIRBuilder MIB(MI); 2573 Register Dst = MI.getOperand(0).getReg(); 2574 Register LHSReg = MI.getOperand(1).getReg(); 2575 Register RHSReg = MI.getOperand(2).getReg(); 2576 2577 // Don't recompute anything. 2578 if (!MRI.hasOneNonDBGUse(LHSReg) || !MRI.hasOneNonDBGUse(RHSReg)) 2579 return false; 2580 2581 // Make sure we have (hand x, ...), (hand y, ...) 2582 MachineInstr *LeftHandInst = getDefIgnoringCopies(LHSReg, MRI); 2583 MachineInstr *RightHandInst = getDefIgnoringCopies(RHSReg, MRI); 2584 if (!LeftHandInst || !RightHandInst) 2585 return false; 2586 unsigned HandOpcode = LeftHandInst->getOpcode(); 2587 if (HandOpcode != RightHandInst->getOpcode()) 2588 return false; 2589 if (!LeftHandInst->getOperand(1).isReg() || 2590 !RightHandInst->getOperand(1).isReg()) 2591 return false; 2592 2593 // Make sure the types match up, and if we're doing this post-legalization, 2594 // we end up with legal types. 2595 Register X = LeftHandInst->getOperand(1).getReg(); 2596 Register Y = RightHandInst->getOperand(1).getReg(); 2597 LLT XTy = MRI.getType(X); 2598 LLT YTy = MRI.getType(Y); 2599 if (XTy != YTy) 2600 return false; 2601 if (!isLegalOrBeforeLegalizer({LogicOpcode, {XTy, YTy}})) 2602 return false; 2603 2604 // Optional extra source register. 2605 Register ExtraHandOpSrcReg; 2606 switch (HandOpcode) { 2607 default: 2608 return false; 2609 case TargetOpcode::G_ANYEXT: 2610 case TargetOpcode::G_SEXT: 2611 case TargetOpcode::G_ZEXT: { 2612 // Match: logic (ext X), (ext Y) --> ext (logic X, Y) 2613 break; 2614 } 2615 case TargetOpcode::G_AND: 2616 case TargetOpcode::G_ASHR: 2617 case TargetOpcode::G_LSHR: 2618 case TargetOpcode::G_SHL: { 2619 // Match: logic (binop x, z), (binop y, z) -> binop (logic x, y), z 2620 MachineOperand &ZOp = LeftHandInst->getOperand(2); 2621 if (!matchEqualDefs(ZOp, RightHandInst->getOperand(2))) 2622 return false; 2623 ExtraHandOpSrcReg = ZOp.getReg(); 2624 break; 2625 } 2626 } 2627 2628 // Record the steps to build the new instructions. 2629 // 2630 // Steps to build (logic x, y) 2631 auto NewLogicDst = MRI.createGenericVirtualRegister(XTy); 2632 OperandBuildSteps LogicBuildSteps = { 2633 [=](MachineInstrBuilder &MIB) { MIB.addDef(NewLogicDst); }, 2634 [=](MachineInstrBuilder &MIB) { MIB.addReg(X); }, 2635 [=](MachineInstrBuilder &MIB) { MIB.addReg(Y); }}; 2636 InstructionBuildSteps LogicSteps(LogicOpcode, LogicBuildSteps); 2637 2638 // Steps to build hand (logic x, y), ...z 2639 OperandBuildSteps HandBuildSteps = { 2640 [=](MachineInstrBuilder &MIB) { MIB.addDef(Dst); }, 2641 [=](MachineInstrBuilder &MIB) { MIB.addReg(NewLogicDst); }}; 2642 if (ExtraHandOpSrcReg.isValid()) 2643 HandBuildSteps.push_back( 2644 [=](MachineInstrBuilder &MIB) { MIB.addReg(ExtraHandOpSrcReg); }); 2645 InstructionBuildSteps HandSteps(HandOpcode, HandBuildSteps); 2646 2647 MatchInfo = InstructionStepsMatchInfo({LogicSteps, HandSteps}); 2648 return true; 2649 } 2650 2651 void CombinerHelper::applyBuildInstructionSteps( 2652 MachineInstr &MI, InstructionStepsMatchInfo &MatchInfo) { 2653 assert(MatchInfo.InstrsToBuild.size() && 2654 "Expected at least one instr to build?"); 2655 Builder.setInstr(MI); 2656 for (auto &InstrToBuild : MatchInfo.InstrsToBuild) { 2657 assert(InstrToBuild.Opcode && "Expected a valid opcode?"); 2658 assert(InstrToBuild.OperandFns.size() && "Expected at least one operand?"); 2659 MachineInstrBuilder Instr = Builder.buildInstr(InstrToBuild.Opcode); 2660 for (auto &OperandFn : InstrToBuild.OperandFns) 2661 OperandFn(Instr); 2662 } 2663 MI.eraseFromParent(); 2664 } 2665 2666 bool CombinerHelper::matchAshrShlToSextInreg( 2667 MachineInstr &MI, std::tuple<Register, int64_t> &MatchInfo) { 2668 assert(MI.getOpcode() == TargetOpcode::G_ASHR); 2669 int64_t ShlCst, AshrCst; 2670 Register Src; 2671 // FIXME: detect splat constant vectors. 2672 if (!mi_match(MI.getOperand(0).getReg(), MRI, 2673 m_GAShr(m_GShl(m_Reg(Src), m_ICst(ShlCst)), m_ICst(AshrCst)))) 2674 return false; 2675 if (ShlCst != AshrCst) 2676 return false; 2677 if (!isLegalOrBeforeLegalizer( 2678 {TargetOpcode::G_SEXT_INREG, {MRI.getType(Src)}})) 2679 return false; 2680 MatchInfo = std::make_tuple(Src, ShlCst); 2681 return true; 2682 } 2683 2684 void CombinerHelper::applyAshShlToSextInreg( 2685 MachineInstr &MI, std::tuple<Register, int64_t> &MatchInfo) { 2686 assert(MI.getOpcode() == TargetOpcode::G_ASHR); 2687 Register Src; 2688 int64_t ShiftAmt; 2689 std::tie(Src, ShiftAmt) = MatchInfo; 2690 unsigned Size = MRI.getType(Src).getScalarSizeInBits(); 2691 Builder.setInstrAndDebugLoc(MI); 2692 Builder.buildSExtInReg(MI.getOperand(0).getReg(), Src, Size - ShiftAmt); 2693 MI.eraseFromParent(); 2694 } 2695 2696 /// and(and(x, C1), C2) -> C1&C2 ? and(x, C1&C2) : 0 2697 bool CombinerHelper::matchOverlappingAnd( 2698 MachineInstr &MI, std::function<void(MachineIRBuilder &)> &MatchInfo) { 2699 assert(MI.getOpcode() == TargetOpcode::G_AND); 2700 2701 Register Dst = MI.getOperand(0).getReg(); 2702 LLT Ty = MRI.getType(Dst); 2703 2704 Register R; 2705 int64_t C1; 2706 int64_t C2; 2707 if (!mi_match( 2708 Dst, MRI, 2709 m_GAnd(m_GAnd(m_Reg(R), m_ICst(C1)), m_ICst(C2)))) 2710 return false; 2711 2712 MatchInfo = [=](MachineIRBuilder &B) { 2713 if (C1 & C2) { 2714 B.buildAnd(Dst, R, B.buildConstant(Ty, C1 & C2)); 2715 return; 2716 } 2717 auto Zero = B.buildConstant(Ty, 0); 2718 replaceRegWith(MRI, Dst, Zero->getOperand(0).getReg()); 2719 }; 2720 return true; 2721 } 2722 2723 bool CombinerHelper::matchRedundantAnd(MachineInstr &MI, 2724 Register &Replacement) { 2725 // Given 2726 // 2727 // %y:_(sN) = G_SOMETHING 2728 // %x:_(sN) = G_SOMETHING 2729 // %res:_(sN) = G_AND %x, %y 2730 // 2731 // Eliminate the G_AND when it is known that x & y == x or x & y == y. 2732 // 2733 // Patterns like this can appear as a result of legalization. E.g. 2734 // 2735 // %cmp:_(s32) = G_ICMP intpred(pred), %x(s32), %y 2736 // %one:_(s32) = G_CONSTANT i32 1 2737 // %and:_(s32) = G_AND %cmp, %one 2738 // 2739 // In this case, G_ICMP only produces a single bit, so x & 1 == x. 2740 assert(MI.getOpcode() == TargetOpcode::G_AND); 2741 if (!KB) 2742 return false; 2743 2744 Register AndDst = MI.getOperand(0).getReg(); 2745 LLT DstTy = MRI.getType(AndDst); 2746 2747 // FIXME: This should be removed once GISelKnownBits supports vectors. 2748 if (DstTy.isVector()) 2749 return false; 2750 2751 Register LHS = MI.getOperand(1).getReg(); 2752 Register RHS = MI.getOperand(2).getReg(); 2753 KnownBits LHSBits = KB->getKnownBits(LHS); 2754 KnownBits RHSBits = KB->getKnownBits(RHS); 2755 2756 // Check that x & Mask == x. 2757 // x & 1 == x, always 2758 // x & 0 == x, only if x is also 0 2759 // Meaning Mask has no effect if every bit is either one in Mask or zero in x. 2760 // 2761 // Check if we can replace AndDst with the LHS of the G_AND 2762 if (canReplaceReg(AndDst, LHS, MRI) && 2763 (LHSBits.Zero | RHSBits.One).isAllOnes()) { 2764 Replacement = LHS; 2765 return true; 2766 } 2767 2768 // Check if we can replace AndDst with the RHS of the G_AND 2769 if (canReplaceReg(AndDst, RHS, MRI) && 2770 (LHSBits.One | RHSBits.Zero).isAllOnes()) { 2771 Replacement = RHS; 2772 return true; 2773 } 2774 2775 return false; 2776 } 2777 2778 bool CombinerHelper::matchRedundantOr(MachineInstr &MI, Register &Replacement) { 2779 // Given 2780 // 2781 // %y:_(sN) = G_SOMETHING 2782 // %x:_(sN) = G_SOMETHING 2783 // %res:_(sN) = G_OR %x, %y 2784 // 2785 // Eliminate the G_OR when it is known that x | y == x or x | y == y. 2786 assert(MI.getOpcode() == TargetOpcode::G_OR); 2787 if (!KB) 2788 return false; 2789 2790 Register OrDst = MI.getOperand(0).getReg(); 2791 LLT DstTy = MRI.getType(OrDst); 2792 2793 // FIXME: This should be removed once GISelKnownBits supports vectors. 2794 if (DstTy.isVector()) 2795 return false; 2796 2797 Register LHS = MI.getOperand(1).getReg(); 2798 Register RHS = MI.getOperand(2).getReg(); 2799 KnownBits LHSBits = KB->getKnownBits(LHS); 2800 KnownBits RHSBits = KB->getKnownBits(RHS); 2801 2802 // Check that x | Mask == x. 2803 // x | 0 == x, always 2804 // x | 1 == x, only if x is also 1 2805 // Meaning Mask has no effect if every bit is either zero in Mask or one in x. 2806 // 2807 // Check if we can replace OrDst with the LHS of the G_OR 2808 if (canReplaceReg(OrDst, LHS, MRI) && 2809 (LHSBits.One | RHSBits.Zero).isAllOnes()) { 2810 Replacement = LHS; 2811 return true; 2812 } 2813 2814 // Check if we can replace OrDst with the RHS of the G_OR 2815 if (canReplaceReg(OrDst, RHS, MRI) && 2816 (LHSBits.Zero | RHSBits.One).isAllOnes()) { 2817 Replacement = RHS; 2818 return true; 2819 } 2820 2821 return false; 2822 } 2823 2824 bool CombinerHelper::matchRedundantSExtInReg(MachineInstr &MI) { 2825 // If the input is already sign extended, just drop the extension. 2826 Register Src = MI.getOperand(1).getReg(); 2827 unsigned ExtBits = MI.getOperand(2).getImm(); 2828 unsigned TypeSize = MRI.getType(Src).getScalarSizeInBits(); 2829 return KB->computeNumSignBits(Src) >= (TypeSize - ExtBits + 1); 2830 } 2831 2832 static bool isConstValidTrue(const TargetLowering &TLI, unsigned ScalarSizeBits, 2833 int64_t Cst, bool IsVector, bool IsFP) { 2834 // For i1, Cst will always be -1 regardless of boolean contents. 2835 return (ScalarSizeBits == 1 && Cst == -1) || 2836 isConstTrueVal(TLI, Cst, IsVector, IsFP); 2837 } 2838 2839 bool CombinerHelper::matchNotCmp(MachineInstr &MI, 2840 SmallVectorImpl<Register> &RegsToNegate) { 2841 assert(MI.getOpcode() == TargetOpcode::G_XOR); 2842 LLT Ty = MRI.getType(MI.getOperand(0).getReg()); 2843 const auto &TLI = *Builder.getMF().getSubtarget().getTargetLowering(); 2844 Register XorSrc; 2845 Register CstReg; 2846 // We match xor(src, true) here. 2847 if (!mi_match(MI.getOperand(0).getReg(), MRI, 2848 m_GXor(m_Reg(XorSrc), m_Reg(CstReg)))) 2849 return false; 2850 2851 if (!MRI.hasOneNonDBGUse(XorSrc)) 2852 return false; 2853 2854 // Check that XorSrc is the root of a tree of comparisons combined with ANDs 2855 // and ORs. The suffix of RegsToNegate starting from index I is used a work 2856 // list of tree nodes to visit. 2857 RegsToNegate.push_back(XorSrc); 2858 // Remember whether the comparisons are all integer or all floating point. 2859 bool IsInt = false; 2860 bool IsFP = false; 2861 for (unsigned I = 0; I < RegsToNegate.size(); ++I) { 2862 Register Reg = RegsToNegate[I]; 2863 if (!MRI.hasOneNonDBGUse(Reg)) 2864 return false; 2865 MachineInstr *Def = MRI.getVRegDef(Reg); 2866 switch (Def->getOpcode()) { 2867 default: 2868 // Don't match if the tree contains anything other than ANDs, ORs and 2869 // comparisons. 2870 return false; 2871 case TargetOpcode::G_ICMP: 2872 if (IsFP) 2873 return false; 2874 IsInt = true; 2875 // When we apply the combine we will invert the predicate. 2876 break; 2877 case TargetOpcode::G_FCMP: 2878 if (IsInt) 2879 return false; 2880 IsFP = true; 2881 // When we apply the combine we will invert the predicate. 2882 break; 2883 case TargetOpcode::G_AND: 2884 case TargetOpcode::G_OR: 2885 // Implement De Morgan's laws: 2886 // ~(x & y) -> ~x | ~y 2887 // ~(x | y) -> ~x & ~y 2888 // When we apply the combine we will change the opcode and recursively 2889 // negate the operands. 2890 RegsToNegate.push_back(Def->getOperand(1).getReg()); 2891 RegsToNegate.push_back(Def->getOperand(2).getReg()); 2892 break; 2893 } 2894 } 2895 2896 // Now we know whether the comparisons are integer or floating point, check 2897 // the constant in the xor. 2898 int64_t Cst; 2899 if (Ty.isVector()) { 2900 MachineInstr *CstDef = MRI.getVRegDef(CstReg); 2901 auto MaybeCst = getBuildVectorConstantSplat(*CstDef, MRI); 2902 if (!MaybeCst) 2903 return false; 2904 if (!isConstValidTrue(TLI, Ty.getScalarSizeInBits(), *MaybeCst, true, IsFP)) 2905 return false; 2906 } else { 2907 if (!mi_match(CstReg, MRI, m_ICst(Cst))) 2908 return false; 2909 if (!isConstValidTrue(TLI, Ty.getSizeInBits(), Cst, false, IsFP)) 2910 return false; 2911 } 2912 2913 return true; 2914 } 2915 2916 void CombinerHelper::applyNotCmp(MachineInstr &MI, 2917 SmallVectorImpl<Register> &RegsToNegate) { 2918 for (Register Reg : RegsToNegate) { 2919 MachineInstr *Def = MRI.getVRegDef(Reg); 2920 Observer.changingInstr(*Def); 2921 // For each comparison, invert the opcode. For each AND and OR, change the 2922 // opcode. 2923 switch (Def->getOpcode()) { 2924 default: 2925 llvm_unreachable("Unexpected opcode"); 2926 case TargetOpcode::G_ICMP: 2927 case TargetOpcode::G_FCMP: { 2928 MachineOperand &PredOp = Def->getOperand(1); 2929 CmpInst::Predicate NewP = CmpInst::getInversePredicate( 2930 (CmpInst::Predicate)PredOp.getPredicate()); 2931 PredOp.setPredicate(NewP); 2932 break; 2933 } 2934 case TargetOpcode::G_AND: 2935 Def->setDesc(Builder.getTII().get(TargetOpcode::G_OR)); 2936 break; 2937 case TargetOpcode::G_OR: 2938 Def->setDesc(Builder.getTII().get(TargetOpcode::G_AND)); 2939 break; 2940 } 2941 Observer.changedInstr(*Def); 2942 } 2943 2944 replaceRegWith(MRI, MI.getOperand(0).getReg(), MI.getOperand(1).getReg()); 2945 MI.eraseFromParent(); 2946 } 2947 2948 bool CombinerHelper::matchXorOfAndWithSameReg( 2949 MachineInstr &MI, std::pair<Register, Register> &MatchInfo) { 2950 // Match (xor (and x, y), y) (or any of its commuted cases) 2951 assert(MI.getOpcode() == TargetOpcode::G_XOR); 2952 Register &X = MatchInfo.first; 2953 Register &Y = MatchInfo.second; 2954 Register AndReg = MI.getOperand(1).getReg(); 2955 Register SharedReg = MI.getOperand(2).getReg(); 2956 2957 // Find a G_AND on either side of the G_XOR. 2958 // Look for one of 2959 // 2960 // (xor (and x, y), SharedReg) 2961 // (xor SharedReg, (and x, y)) 2962 if (!mi_match(AndReg, MRI, m_GAnd(m_Reg(X), m_Reg(Y)))) { 2963 std::swap(AndReg, SharedReg); 2964 if (!mi_match(AndReg, MRI, m_GAnd(m_Reg(X), m_Reg(Y)))) 2965 return false; 2966 } 2967 2968 // Only do this if we'll eliminate the G_AND. 2969 if (!MRI.hasOneNonDBGUse(AndReg)) 2970 return false; 2971 2972 // We can combine if SharedReg is the same as either the LHS or RHS of the 2973 // G_AND. 2974 if (Y != SharedReg) 2975 std::swap(X, Y); 2976 return Y == SharedReg; 2977 } 2978 2979 void CombinerHelper::applyXorOfAndWithSameReg( 2980 MachineInstr &MI, std::pair<Register, Register> &MatchInfo) { 2981 // Fold (xor (and x, y), y) -> (and (not x), y) 2982 Builder.setInstrAndDebugLoc(MI); 2983 Register X, Y; 2984 std::tie(X, Y) = MatchInfo; 2985 auto Not = Builder.buildNot(MRI.getType(X), X); 2986 Observer.changingInstr(MI); 2987 MI.setDesc(Builder.getTII().get(TargetOpcode::G_AND)); 2988 MI.getOperand(1).setReg(Not->getOperand(0).getReg()); 2989 MI.getOperand(2).setReg(Y); 2990 Observer.changedInstr(MI); 2991 } 2992 2993 bool CombinerHelper::matchPtrAddZero(MachineInstr &MI) { 2994 auto &PtrAdd = cast<GPtrAdd>(MI); 2995 Register DstReg = PtrAdd.getReg(0); 2996 LLT Ty = MRI.getType(DstReg); 2997 const DataLayout &DL = Builder.getMF().getDataLayout(); 2998 2999 if (DL.isNonIntegralAddressSpace(Ty.getScalarType().getAddressSpace())) 3000 return false; 3001 3002 if (Ty.isPointer()) { 3003 auto ConstVal = getIConstantVRegVal(PtrAdd.getBaseReg(), MRI); 3004 return ConstVal && *ConstVal == 0; 3005 } 3006 3007 assert(Ty.isVector() && "Expecting a vector type"); 3008 const MachineInstr *VecMI = MRI.getVRegDef(PtrAdd.getBaseReg()); 3009 return isBuildVectorAllZeros(*VecMI, MRI); 3010 } 3011 3012 void CombinerHelper::applyPtrAddZero(MachineInstr &MI) { 3013 auto &PtrAdd = cast<GPtrAdd>(MI); 3014 Builder.setInstrAndDebugLoc(PtrAdd); 3015 Builder.buildIntToPtr(PtrAdd.getReg(0), PtrAdd.getOffsetReg()); 3016 PtrAdd.eraseFromParent(); 3017 } 3018 3019 /// The second source operand is known to be a power of 2. 3020 void CombinerHelper::applySimplifyURemByPow2(MachineInstr &MI) { 3021 Register DstReg = MI.getOperand(0).getReg(); 3022 Register Src0 = MI.getOperand(1).getReg(); 3023 Register Pow2Src1 = MI.getOperand(2).getReg(); 3024 LLT Ty = MRI.getType(DstReg); 3025 Builder.setInstrAndDebugLoc(MI); 3026 3027 // Fold (urem x, pow2) -> (and x, pow2-1) 3028 auto NegOne = Builder.buildConstant(Ty, -1); 3029 auto Add = Builder.buildAdd(Ty, Pow2Src1, NegOne); 3030 Builder.buildAnd(DstReg, Src0, Add); 3031 MI.eraseFromParent(); 3032 } 3033 3034 Optional<SmallVector<Register, 8>> 3035 CombinerHelper::findCandidatesForLoadOrCombine(const MachineInstr *Root) const { 3036 assert(Root->getOpcode() == TargetOpcode::G_OR && "Expected G_OR only!"); 3037 // We want to detect if Root is part of a tree which represents a bunch 3038 // of loads being merged into a larger load. We'll try to recognize patterns 3039 // like, for example: 3040 // 3041 // Reg Reg 3042 // \ / 3043 // OR_1 Reg 3044 // \ / 3045 // OR_2 3046 // \ Reg 3047 // .. / 3048 // Root 3049 // 3050 // Reg Reg Reg Reg 3051 // \ / \ / 3052 // OR_1 OR_2 3053 // \ / 3054 // \ / 3055 // ... 3056 // Root 3057 // 3058 // Each "Reg" may have been produced by a load + some arithmetic. This 3059 // function will save each of them. 3060 SmallVector<Register, 8> RegsToVisit; 3061 SmallVector<const MachineInstr *, 7> Ors = {Root}; 3062 3063 // In the "worst" case, we're dealing with a load for each byte. So, there 3064 // are at most #bytes - 1 ORs. 3065 const unsigned MaxIter = 3066 MRI.getType(Root->getOperand(0).getReg()).getSizeInBytes() - 1; 3067 for (unsigned Iter = 0; Iter < MaxIter; ++Iter) { 3068 if (Ors.empty()) 3069 break; 3070 const MachineInstr *Curr = Ors.pop_back_val(); 3071 Register OrLHS = Curr->getOperand(1).getReg(); 3072 Register OrRHS = Curr->getOperand(2).getReg(); 3073 3074 // In the combine, we want to elimate the entire tree. 3075 if (!MRI.hasOneNonDBGUse(OrLHS) || !MRI.hasOneNonDBGUse(OrRHS)) 3076 return None; 3077 3078 // If it's a G_OR, save it and continue to walk. If it's not, then it's 3079 // something that may be a load + arithmetic. 3080 if (const MachineInstr *Or = getOpcodeDef(TargetOpcode::G_OR, OrLHS, MRI)) 3081 Ors.push_back(Or); 3082 else 3083 RegsToVisit.push_back(OrLHS); 3084 if (const MachineInstr *Or = getOpcodeDef(TargetOpcode::G_OR, OrRHS, MRI)) 3085 Ors.push_back(Or); 3086 else 3087 RegsToVisit.push_back(OrRHS); 3088 } 3089 3090 // We're going to try and merge each register into a wider power-of-2 type, 3091 // so we ought to have an even number of registers. 3092 if (RegsToVisit.empty() || RegsToVisit.size() % 2 != 0) 3093 return None; 3094 return RegsToVisit; 3095 } 3096 3097 /// Helper function for findLoadOffsetsForLoadOrCombine. 3098 /// 3099 /// Check if \p Reg is the result of loading a \p MemSizeInBits wide value, 3100 /// and then moving that value into a specific byte offset. 3101 /// 3102 /// e.g. x[i] << 24 3103 /// 3104 /// \returns The load instruction and the byte offset it is moved into. 3105 static Optional<std::pair<GZExtLoad *, int64_t>> 3106 matchLoadAndBytePosition(Register Reg, unsigned MemSizeInBits, 3107 const MachineRegisterInfo &MRI) { 3108 assert(MRI.hasOneNonDBGUse(Reg) && 3109 "Expected Reg to only have one non-debug use?"); 3110 Register MaybeLoad; 3111 int64_t Shift; 3112 if (!mi_match(Reg, MRI, 3113 m_OneNonDBGUse(m_GShl(m_Reg(MaybeLoad), m_ICst(Shift))))) { 3114 Shift = 0; 3115 MaybeLoad = Reg; 3116 } 3117 3118 if (Shift % MemSizeInBits != 0) 3119 return None; 3120 3121 // TODO: Handle other types of loads. 3122 auto *Load = getOpcodeDef<GZExtLoad>(MaybeLoad, MRI); 3123 if (!Load) 3124 return None; 3125 3126 if (!Load->isUnordered() || Load->getMemSizeInBits() != MemSizeInBits) 3127 return None; 3128 3129 return std::make_pair(Load, Shift / MemSizeInBits); 3130 } 3131 3132 Optional<std::tuple<GZExtLoad *, int64_t, GZExtLoad *>> 3133 CombinerHelper::findLoadOffsetsForLoadOrCombine( 3134 SmallDenseMap<int64_t, int64_t, 8> &MemOffset2Idx, 3135 const SmallVector<Register, 8> &RegsToVisit, const unsigned MemSizeInBits) { 3136 3137 // Each load found for the pattern. There should be one for each RegsToVisit. 3138 SmallSetVector<const MachineInstr *, 8> Loads; 3139 3140 // The lowest index used in any load. (The lowest "i" for each x[i].) 3141 int64_t LowestIdx = INT64_MAX; 3142 3143 // The load which uses the lowest index. 3144 GZExtLoad *LowestIdxLoad = nullptr; 3145 3146 // Keeps track of the load indices we see. We shouldn't see any indices twice. 3147 SmallSet<int64_t, 8> SeenIdx; 3148 3149 // Ensure each load is in the same MBB. 3150 // TODO: Support multiple MachineBasicBlocks. 3151 MachineBasicBlock *MBB = nullptr; 3152 const MachineMemOperand *MMO = nullptr; 3153 3154 // Earliest instruction-order load in the pattern. 3155 GZExtLoad *EarliestLoad = nullptr; 3156 3157 // Latest instruction-order load in the pattern. 3158 GZExtLoad *LatestLoad = nullptr; 3159 3160 // Base pointer which every load should share. 3161 Register BasePtr; 3162 3163 // We want to find a load for each register. Each load should have some 3164 // appropriate bit twiddling arithmetic. During this loop, we will also keep 3165 // track of the load which uses the lowest index. Later, we will check if we 3166 // can use its pointer in the final, combined load. 3167 for (auto Reg : RegsToVisit) { 3168 // Find the load, and find the position that it will end up in (e.g. a 3169 // shifted) value. 3170 auto LoadAndPos = matchLoadAndBytePosition(Reg, MemSizeInBits, MRI); 3171 if (!LoadAndPos) 3172 return None; 3173 GZExtLoad *Load; 3174 int64_t DstPos; 3175 std::tie(Load, DstPos) = *LoadAndPos; 3176 3177 // TODO: Handle multiple MachineBasicBlocks. Currently not handled because 3178 // it is difficult to check for stores/calls/etc between loads. 3179 MachineBasicBlock *LoadMBB = Load->getParent(); 3180 if (!MBB) 3181 MBB = LoadMBB; 3182 if (LoadMBB != MBB) 3183 return None; 3184 3185 // Make sure that the MachineMemOperands of every seen load are compatible. 3186 auto &LoadMMO = Load->getMMO(); 3187 if (!MMO) 3188 MMO = &LoadMMO; 3189 if (MMO->getAddrSpace() != LoadMMO.getAddrSpace()) 3190 return None; 3191 3192 // Find out what the base pointer and index for the load is. 3193 Register LoadPtr; 3194 int64_t Idx; 3195 if (!mi_match(Load->getOperand(1).getReg(), MRI, 3196 m_GPtrAdd(m_Reg(LoadPtr), m_ICst(Idx)))) { 3197 LoadPtr = Load->getOperand(1).getReg(); 3198 Idx = 0; 3199 } 3200 3201 // Don't combine things like a[i], a[i] -> a bigger load. 3202 if (!SeenIdx.insert(Idx).second) 3203 return None; 3204 3205 // Every load must share the same base pointer; don't combine things like: 3206 // 3207 // a[i], b[i + 1] -> a bigger load. 3208 if (!BasePtr.isValid()) 3209 BasePtr = LoadPtr; 3210 if (BasePtr != LoadPtr) 3211 return None; 3212 3213 if (Idx < LowestIdx) { 3214 LowestIdx = Idx; 3215 LowestIdxLoad = Load; 3216 } 3217 3218 // Keep track of the byte offset that this load ends up at. If we have seen 3219 // the byte offset, then stop here. We do not want to combine: 3220 // 3221 // a[i] << 16, a[i + k] << 16 -> a bigger load. 3222 if (!MemOffset2Idx.try_emplace(DstPos, Idx).second) 3223 return None; 3224 Loads.insert(Load); 3225 3226 // Keep track of the position of the earliest/latest loads in the pattern. 3227 // We will check that there are no load fold barriers between them later 3228 // on. 3229 // 3230 // FIXME: Is there a better way to check for load fold barriers? 3231 if (!EarliestLoad || dominates(*Load, *EarliestLoad)) 3232 EarliestLoad = Load; 3233 if (!LatestLoad || dominates(*LatestLoad, *Load)) 3234 LatestLoad = Load; 3235 } 3236 3237 // We found a load for each register. Let's check if each load satisfies the 3238 // pattern. 3239 assert(Loads.size() == RegsToVisit.size() && 3240 "Expected to find a load for each register?"); 3241 assert(EarliestLoad != LatestLoad && EarliestLoad && 3242 LatestLoad && "Expected at least two loads?"); 3243 3244 // Check if there are any stores, calls, etc. between any of the loads. If 3245 // there are, then we can't safely perform the combine. 3246 // 3247 // MaxIter is chosen based off the (worst case) number of iterations it 3248 // typically takes to succeed in the LLVM test suite plus some padding. 3249 // 3250 // FIXME: Is there a better way to check for load fold barriers? 3251 const unsigned MaxIter = 20; 3252 unsigned Iter = 0; 3253 for (const auto &MI : instructionsWithoutDebug(EarliestLoad->getIterator(), 3254 LatestLoad->getIterator())) { 3255 if (Loads.count(&MI)) 3256 continue; 3257 if (MI.isLoadFoldBarrier()) 3258 return None; 3259 if (Iter++ == MaxIter) 3260 return None; 3261 } 3262 3263 return std::make_tuple(LowestIdxLoad, LowestIdx, LatestLoad); 3264 } 3265 3266 bool CombinerHelper::matchLoadOrCombine( 3267 MachineInstr &MI, std::function<void(MachineIRBuilder &)> &MatchInfo) { 3268 assert(MI.getOpcode() == TargetOpcode::G_OR); 3269 MachineFunction &MF = *MI.getMF(); 3270 // Assuming a little-endian target, transform: 3271 // s8 *a = ... 3272 // s32 val = a[0] | (a[1] << 8) | (a[2] << 16) | (a[3] << 24) 3273 // => 3274 // s32 val = *((i32)a) 3275 // 3276 // s8 *a = ... 3277 // s32 val = (a[0] << 24) | (a[1] << 16) | (a[2] << 8) | a[3] 3278 // => 3279 // s32 val = BSWAP(*((s32)a)) 3280 Register Dst = MI.getOperand(0).getReg(); 3281 LLT Ty = MRI.getType(Dst); 3282 if (Ty.isVector()) 3283 return false; 3284 3285 // We need to combine at least two loads into this type. Since the smallest 3286 // possible load is into a byte, we need at least a 16-bit wide type. 3287 const unsigned WideMemSizeInBits = Ty.getSizeInBits(); 3288 if (WideMemSizeInBits < 16 || WideMemSizeInBits % 8 != 0) 3289 return false; 3290 3291 // Match a collection of non-OR instructions in the pattern. 3292 auto RegsToVisit = findCandidatesForLoadOrCombine(&MI); 3293 if (!RegsToVisit) 3294 return false; 3295 3296 // We have a collection of non-OR instructions. Figure out how wide each of 3297 // the small loads should be based off of the number of potential loads we 3298 // found. 3299 const unsigned NarrowMemSizeInBits = WideMemSizeInBits / RegsToVisit->size(); 3300 if (NarrowMemSizeInBits % 8 != 0) 3301 return false; 3302 3303 // Check if each register feeding into each OR is a load from the same 3304 // base pointer + some arithmetic. 3305 // 3306 // e.g. a[0], a[1] << 8, a[2] << 16, etc. 3307 // 3308 // Also verify that each of these ends up putting a[i] into the same memory 3309 // offset as a load into a wide type would. 3310 SmallDenseMap<int64_t, int64_t, 8> MemOffset2Idx; 3311 GZExtLoad *LowestIdxLoad, *LatestLoad; 3312 int64_t LowestIdx; 3313 auto MaybeLoadInfo = findLoadOffsetsForLoadOrCombine( 3314 MemOffset2Idx, *RegsToVisit, NarrowMemSizeInBits); 3315 if (!MaybeLoadInfo) 3316 return false; 3317 std::tie(LowestIdxLoad, LowestIdx, LatestLoad) = *MaybeLoadInfo; 3318 3319 // We have a bunch of loads being OR'd together. Using the addresses + offsets 3320 // we found before, check if this corresponds to a big or little endian byte 3321 // pattern. If it does, then we can represent it using a load + possibly a 3322 // BSWAP. 3323 bool IsBigEndianTarget = MF.getDataLayout().isBigEndian(); 3324 Optional<bool> IsBigEndian = isBigEndian(MemOffset2Idx, LowestIdx); 3325 if (!IsBigEndian.hasValue()) 3326 return false; 3327 bool NeedsBSwap = IsBigEndianTarget != *IsBigEndian; 3328 if (NeedsBSwap && !isLegalOrBeforeLegalizer({TargetOpcode::G_BSWAP, {Ty}})) 3329 return false; 3330 3331 // Make sure that the load from the lowest index produces offset 0 in the 3332 // final value. 3333 // 3334 // This ensures that we won't combine something like this: 3335 // 3336 // load x[i] -> byte 2 3337 // load x[i+1] -> byte 0 ---> wide_load x[i] 3338 // load x[i+2] -> byte 1 3339 const unsigned NumLoadsInTy = WideMemSizeInBits / NarrowMemSizeInBits; 3340 const unsigned ZeroByteOffset = 3341 *IsBigEndian 3342 ? bigEndianByteAt(NumLoadsInTy, 0) 3343 : littleEndianByteAt(NumLoadsInTy, 0); 3344 auto ZeroOffsetIdx = MemOffset2Idx.find(ZeroByteOffset); 3345 if (ZeroOffsetIdx == MemOffset2Idx.end() || 3346 ZeroOffsetIdx->second != LowestIdx) 3347 return false; 3348 3349 // We wil reuse the pointer from the load which ends up at byte offset 0. It 3350 // may not use index 0. 3351 Register Ptr = LowestIdxLoad->getPointerReg(); 3352 const MachineMemOperand &MMO = LowestIdxLoad->getMMO(); 3353 LegalityQuery::MemDesc MMDesc(MMO); 3354 MMDesc.MemoryTy = Ty; 3355 if (!isLegalOrBeforeLegalizer( 3356 {TargetOpcode::G_LOAD, {Ty, MRI.getType(Ptr)}, {MMDesc}})) 3357 return false; 3358 auto PtrInfo = MMO.getPointerInfo(); 3359 auto *NewMMO = MF.getMachineMemOperand(&MMO, PtrInfo, WideMemSizeInBits / 8); 3360 3361 // Load must be allowed and fast on the target. 3362 LLVMContext &C = MF.getFunction().getContext(); 3363 auto &DL = MF.getDataLayout(); 3364 bool Fast = false; 3365 if (!getTargetLowering().allowsMemoryAccess(C, DL, Ty, *NewMMO, &Fast) || 3366 !Fast) 3367 return false; 3368 3369 MatchInfo = [=](MachineIRBuilder &MIB) { 3370 MIB.setInstrAndDebugLoc(*LatestLoad); 3371 Register LoadDst = NeedsBSwap ? MRI.cloneVirtualRegister(Dst) : Dst; 3372 MIB.buildLoad(LoadDst, Ptr, *NewMMO); 3373 if (NeedsBSwap) 3374 MIB.buildBSwap(Dst, LoadDst); 3375 }; 3376 return true; 3377 } 3378 3379 /// Check if the store \p Store is a truncstore that can be merged. That is, 3380 /// it's a store of a shifted value of \p SrcVal. If \p SrcVal is an empty 3381 /// Register then it does not need to match and SrcVal is set to the source 3382 /// value found. 3383 /// On match, returns the start byte offset of the \p SrcVal that is being 3384 /// stored. 3385 static Optional<int64_t> getTruncStoreByteOffset(GStore &Store, Register &SrcVal, 3386 MachineRegisterInfo &MRI) { 3387 Register TruncVal; 3388 if (!mi_match(Store.getValueReg(), MRI, m_GTrunc(m_Reg(TruncVal)))) 3389 return None; 3390 3391 // The shift amount must be a constant multiple of the narrow type. 3392 // It is translated to the offset address in the wide source value "y". 3393 // 3394 // x = G_LSHR y, ShiftAmtC 3395 // s8 z = G_TRUNC x 3396 // store z, ... 3397 Register FoundSrcVal; 3398 int64_t ShiftAmt; 3399 if (!mi_match(TruncVal, MRI, 3400 m_any_of(m_GLShr(m_Reg(FoundSrcVal), m_ICst(ShiftAmt)), 3401 m_GAShr(m_Reg(FoundSrcVal), m_ICst(ShiftAmt))))) { 3402 if (!SrcVal.isValid() || TruncVal == SrcVal) { 3403 if (!SrcVal.isValid()) 3404 SrcVal = TruncVal; 3405 return 0; // If it's the lowest index store. 3406 } 3407 return None; 3408 } 3409 3410 unsigned NarrowBits = Store.getMMO().getMemoryType().getScalarSizeInBits(); 3411 if (ShiftAmt % NarrowBits!= 0) 3412 return None; 3413 const unsigned Offset = ShiftAmt / NarrowBits; 3414 3415 if (SrcVal.isValid() && FoundSrcVal != SrcVal) 3416 return None; 3417 3418 if (!SrcVal.isValid()) 3419 SrcVal = FoundSrcVal; 3420 else if (MRI.getType(SrcVal) != MRI.getType(FoundSrcVal)) 3421 return None; 3422 return Offset; 3423 } 3424 3425 /// Match a pattern where a wide type scalar value is stored by several narrow 3426 /// stores. Fold it into a single store or a BSWAP and a store if the targets 3427 /// supports it. 3428 /// 3429 /// Assuming little endian target: 3430 /// i8 *p = ... 3431 /// i32 val = ... 3432 /// p[0] = (val >> 0) & 0xFF; 3433 /// p[1] = (val >> 8) & 0xFF; 3434 /// p[2] = (val >> 16) & 0xFF; 3435 /// p[3] = (val >> 24) & 0xFF; 3436 /// => 3437 /// *((i32)p) = val; 3438 /// 3439 /// i8 *p = ... 3440 /// i32 val = ... 3441 /// p[0] = (val >> 24) & 0xFF; 3442 /// p[1] = (val >> 16) & 0xFF; 3443 /// p[2] = (val >> 8) & 0xFF; 3444 /// p[3] = (val >> 0) & 0xFF; 3445 /// => 3446 /// *((i32)p) = BSWAP(val); 3447 bool CombinerHelper::matchTruncStoreMerge(MachineInstr &MI, 3448 MergeTruncStoresInfo &MatchInfo) { 3449 auto &StoreMI = cast<GStore>(MI); 3450 LLT MemTy = StoreMI.getMMO().getMemoryType(); 3451 3452 // We only handle merging simple stores of 1-4 bytes. 3453 if (!MemTy.isScalar()) 3454 return false; 3455 switch (MemTy.getSizeInBits()) { 3456 case 8: 3457 case 16: 3458 case 32: 3459 break; 3460 default: 3461 return false; 3462 } 3463 if (!StoreMI.isSimple()) 3464 return false; 3465 3466 // We do a simple search for mergeable stores prior to this one. 3467 // Any potential alias hazard along the way terminates the search. 3468 SmallVector<GStore *> FoundStores; 3469 3470 // We're looking for: 3471 // 1) a (store(trunc(...))) 3472 // 2) of an LSHR/ASHR of a single wide value, by the appropriate shift to get 3473 // the partial value stored. 3474 // 3) where the offsets form either a little or big-endian sequence. 3475 3476 auto &LastStore = StoreMI; 3477 3478 // The single base pointer that all stores must use. 3479 Register BaseReg; 3480 int64_t LastOffset; 3481 if (!mi_match(LastStore.getPointerReg(), MRI, 3482 m_GPtrAdd(m_Reg(BaseReg), m_ICst(LastOffset)))) { 3483 BaseReg = LastStore.getPointerReg(); 3484 LastOffset = 0; 3485 } 3486 3487 GStore *LowestIdxStore = &LastStore; 3488 int64_t LowestIdxOffset = LastOffset; 3489 3490 Register WideSrcVal; 3491 auto LowestShiftAmt = getTruncStoreByteOffset(LastStore, WideSrcVal, MRI); 3492 if (!LowestShiftAmt) 3493 return false; // Didn't match a trunc. 3494 assert(WideSrcVal.isValid()); 3495 3496 LLT WideStoreTy = MRI.getType(WideSrcVal); 3497 // The wide type might not be a multiple of the memory type, e.g. s48 and s32. 3498 if (WideStoreTy.getSizeInBits() % MemTy.getSizeInBits() != 0) 3499 return false; 3500 const unsigned NumStoresRequired = 3501 WideStoreTy.getSizeInBits() / MemTy.getSizeInBits(); 3502 3503 SmallVector<int64_t, 8> OffsetMap(NumStoresRequired, INT64_MAX); 3504 OffsetMap[*LowestShiftAmt] = LastOffset; 3505 FoundStores.emplace_back(&LastStore); 3506 3507 // Search the block up for more stores. 3508 // We use a search threshold of 10 instructions here because the combiner 3509 // works top-down within a block, and we don't want to search an unbounded 3510 // number of predecessor instructions trying to find matching stores. 3511 // If we moved this optimization into a separate pass then we could probably 3512 // use a more efficient search without having a hard-coded threshold. 3513 const int MaxInstsToCheck = 10; 3514 int NumInstsChecked = 0; 3515 for (auto II = ++LastStore.getReverseIterator(); 3516 II != LastStore.getParent()->rend() && NumInstsChecked < MaxInstsToCheck; 3517 ++II) { 3518 NumInstsChecked++; 3519 GStore *NewStore; 3520 if ((NewStore = dyn_cast<GStore>(&*II))) { 3521 if (NewStore->getMMO().getMemoryType() != MemTy || !NewStore->isSimple()) 3522 break; 3523 } else if (II->isLoadFoldBarrier() || II->mayLoad()) { 3524 break; 3525 } else { 3526 continue; // This is a safe instruction we can look past. 3527 } 3528 3529 Register NewBaseReg; 3530 int64_t MemOffset; 3531 // Check we're storing to the same base + some offset. 3532 if (!mi_match(NewStore->getPointerReg(), MRI, 3533 m_GPtrAdd(m_Reg(NewBaseReg), m_ICst(MemOffset)))) { 3534 NewBaseReg = NewStore->getPointerReg(); 3535 MemOffset = 0; 3536 } 3537 if (BaseReg != NewBaseReg) 3538 break; 3539 3540 auto ShiftByteOffset = getTruncStoreByteOffset(*NewStore, WideSrcVal, MRI); 3541 if (!ShiftByteOffset) 3542 break; 3543 if (MemOffset < LowestIdxOffset) { 3544 LowestIdxOffset = MemOffset; 3545 LowestIdxStore = NewStore; 3546 } 3547 3548 // Map the offset in the store and the offset in the combined value, and 3549 // early return if it has been set before. 3550 if (*ShiftByteOffset < 0 || *ShiftByteOffset >= NumStoresRequired || 3551 OffsetMap[*ShiftByteOffset] != INT64_MAX) 3552 break; 3553 OffsetMap[*ShiftByteOffset] = MemOffset; 3554 3555 FoundStores.emplace_back(NewStore); 3556 // Reset counter since we've found a matching inst. 3557 NumInstsChecked = 0; 3558 if (FoundStores.size() == NumStoresRequired) 3559 break; 3560 } 3561 3562 if (FoundStores.size() != NumStoresRequired) { 3563 return false; 3564 } 3565 3566 const auto &DL = LastStore.getMF()->getDataLayout(); 3567 auto &C = LastStore.getMF()->getFunction().getContext(); 3568 // Check that a store of the wide type is both allowed and fast on the target 3569 bool Fast = false; 3570 bool Allowed = getTargetLowering().allowsMemoryAccess( 3571 C, DL, WideStoreTy, LowestIdxStore->getMMO(), &Fast); 3572 if (!Allowed || !Fast) 3573 return false; 3574 3575 // Check if the pieces of the value are going to the expected places in memory 3576 // to merge the stores. 3577 unsigned NarrowBits = MemTy.getScalarSizeInBits(); 3578 auto checkOffsets = [&](bool MatchLittleEndian) { 3579 if (MatchLittleEndian) { 3580 for (unsigned i = 0; i != NumStoresRequired; ++i) 3581 if (OffsetMap[i] != i * (NarrowBits / 8) + LowestIdxOffset) 3582 return false; 3583 } else { // MatchBigEndian by reversing loop counter. 3584 for (unsigned i = 0, j = NumStoresRequired - 1; i != NumStoresRequired; 3585 ++i, --j) 3586 if (OffsetMap[j] != i * (NarrowBits / 8) + LowestIdxOffset) 3587 return false; 3588 } 3589 return true; 3590 }; 3591 3592 // Check if the offsets line up for the native data layout of this target. 3593 bool NeedBswap = false; 3594 bool NeedRotate = false; 3595 if (!checkOffsets(DL.isLittleEndian())) { 3596 // Special-case: check if byte offsets line up for the opposite endian. 3597 if (NarrowBits == 8 && checkOffsets(DL.isBigEndian())) 3598 NeedBswap = true; 3599 else if (NumStoresRequired == 2 && checkOffsets(DL.isBigEndian())) 3600 NeedRotate = true; 3601 else 3602 return false; 3603 } 3604 3605 if (NeedBswap && 3606 !isLegalOrBeforeLegalizer({TargetOpcode::G_BSWAP, {WideStoreTy}})) 3607 return false; 3608 if (NeedRotate && 3609 !isLegalOrBeforeLegalizer({TargetOpcode::G_ROTR, {WideStoreTy}})) 3610 return false; 3611 3612 MatchInfo.NeedBSwap = NeedBswap; 3613 MatchInfo.NeedRotate = NeedRotate; 3614 MatchInfo.LowestIdxStore = LowestIdxStore; 3615 MatchInfo.WideSrcVal = WideSrcVal; 3616 MatchInfo.FoundStores = std::move(FoundStores); 3617 return true; 3618 } 3619 3620 void CombinerHelper::applyTruncStoreMerge(MachineInstr &MI, 3621 MergeTruncStoresInfo &MatchInfo) { 3622 3623 Builder.setInstrAndDebugLoc(MI); 3624 Register WideSrcVal = MatchInfo.WideSrcVal; 3625 LLT WideStoreTy = MRI.getType(WideSrcVal); 3626 3627 if (MatchInfo.NeedBSwap) { 3628 WideSrcVal = Builder.buildBSwap(WideStoreTy, WideSrcVal).getReg(0); 3629 } else if (MatchInfo.NeedRotate) { 3630 assert(WideStoreTy.getSizeInBits() % 2 == 0 && 3631 "Unexpected type for rotate"); 3632 auto RotAmt = 3633 Builder.buildConstant(WideStoreTy, WideStoreTy.getSizeInBits() / 2); 3634 WideSrcVal = 3635 Builder.buildRotateRight(WideStoreTy, WideSrcVal, RotAmt).getReg(0); 3636 } 3637 3638 Builder.buildStore(WideSrcVal, MatchInfo.LowestIdxStore->getPointerReg(), 3639 MatchInfo.LowestIdxStore->getMMO().getPointerInfo(), 3640 MatchInfo.LowestIdxStore->getMMO().getAlign()); 3641 3642 // Erase the old stores. 3643 for (auto *ST : MatchInfo.FoundStores) 3644 ST->eraseFromParent(); 3645 } 3646 3647 bool CombinerHelper::matchExtendThroughPhis(MachineInstr &MI, 3648 MachineInstr *&ExtMI) { 3649 assert(MI.getOpcode() == TargetOpcode::G_PHI); 3650 3651 Register DstReg = MI.getOperand(0).getReg(); 3652 3653 // TODO: Extending a vector may be expensive, don't do this until heuristics 3654 // are better. 3655 if (MRI.getType(DstReg).isVector()) 3656 return false; 3657 3658 // Try to match a phi, whose only use is an extend. 3659 if (!MRI.hasOneNonDBGUse(DstReg)) 3660 return false; 3661 ExtMI = &*MRI.use_instr_nodbg_begin(DstReg); 3662 switch (ExtMI->getOpcode()) { 3663 case TargetOpcode::G_ANYEXT: 3664 return true; // G_ANYEXT is usually free. 3665 case TargetOpcode::G_ZEXT: 3666 case TargetOpcode::G_SEXT: 3667 break; 3668 default: 3669 return false; 3670 } 3671 3672 // If the target is likely to fold this extend away, don't propagate. 3673 if (Builder.getTII().isExtendLikelyToBeFolded(*ExtMI, MRI)) 3674 return false; 3675 3676 // We don't want to propagate the extends unless there's a good chance that 3677 // they'll be optimized in some way. 3678 // Collect the unique incoming values. 3679 SmallPtrSet<MachineInstr *, 4> InSrcs; 3680 for (unsigned Idx = 1; Idx < MI.getNumOperands(); Idx += 2) { 3681 auto *DefMI = getDefIgnoringCopies(MI.getOperand(Idx).getReg(), MRI); 3682 switch (DefMI->getOpcode()) { 3683 case TargetOpcode::G_LOAD: 3684 case TargetOpcode::G_TRUNC: 3685 case TargetOpcode::G_SEXT: 3686 case TargetOpcode::G_ZEXT: 3687 case TargetOpcode::G_ANYEXT: 3688 case TargetOpcode::G_CONSTANT: 3689 InSrcs.insert(getDefIgnoringCopies(MI.getOperand(Idx).getReg(), MRI)); 3690 // Don't try to propagate if there are too many places to create new 3691 // extends, chances are it'll increase code size. 3692 if (InSrcs.size() > 2) 3693 return false; 3694 break; 3695 default: 3696 return false; 3697 } 3698 } 3699 return true; 3700 } 3701 3702 void CombinerHelper::applyExtendThroughPhis(MachineInstr &MI, 3703 MachineInstr *&ExtMI) { 3704 assert(MI.getOpcode() == TargetOpcode::G_PHI); 3705 Register DstReg = ExtMI->getOperand(0).getReg(); 3706 LLT ExtTy = MRI.getType(DstReg); 3707 3708 // Propagate the extension into the block of each incoming reg's block. 3709 // Use a SetVector here because PHIs can have duplicate edges, and we want 3710 // deterministic iteration order. 3711 SmallSetVector<MachineInstr *, 8> SrcMIs; 3712 SmallDenseMap<MachineInstr *, MachineInstr *, 8> OldToNewSrcMap; 3713 for (unsigned SrcIdx = 1; SrcIdx < MI.getNumOperands(); SrcIdx += 2) { 3714 auto *SrcMI = MRI.getVRegDef(MI.getOperand(SrcIdx).getReg()); 3715 if (!SrcMIs.insert(SrcMI)) 3716 continue; 3717 3718 // Build an extend after each src inst. 3719 auto *MBB = SrcMI->getParent(); 3720 MachineBasicBlock::iterator InsertPt = ++SrcMI->getIterator(); 3721 if (InsertPt != MBB->end() && InsertPt->isPHI()) 3722 InsertPt = MBB->getFirstNonPHI(); 3723 3724 Builder.setInsertPt(*SrcMI->getParent(), InsertPt); 3725 Builder.setDebugLoc(MI.getDebugLoc()); 3726 auto NewExt = Builder.buildExtOrTrunc(ExtMI->getOpcode(), ExtTy, 3727 SrcMI->getOperand(0).getReg()); 3728 OldToNewSrcMap[SrcMI] = NewExt; 3729 } 3730 3731 // Create a new phi with the extended inputs. 3732 Builder.setInstrAndDebugLoc(MI); 3733 auto NewPhi = Builder.buildInstrNoInsert(TargetOpcode::G_PHI); 3734 NewPhi.addDef(DstReg); 3735 for (unsigned SrcIdx = 1; SrcIdx < MI.getNumOperands(); ++SrcIdx) { 3736 auto &MO = MI.getOperand(SrcIdx); 3737 if (!MO.isReg()) { 3738 NewPhi.addMBB(MO.getMBB()); 3739 continue; 3740 } 3741 auto *NewSrc = OldToNewSrcMap[MRI.getVRegDef(MO.getReg())]; 3742 NewPhi.addUse(NewSrc->getOperand(0).getReg()); 3743 } 3744 Builder.insertInstr(NewPhi); 3745 ExtMI->eraseFromParent(); 3746 } 3747 3748 bool CombinerHelper::matchExtractVecEltBuildVec(MachineInstr &MI, 3749 Register &Reg) { 3750 assert(MI.getOpcode() == TargetOpcode::G_EXTRACT_VECTOR_ELT); 3751 // If we have a constant index, look for a G_BUILD_VECTOR source 3752 // and find the source register that the index maps to. 3753 Register SrcVec = MI.getOperand(1).getReg(); 3754 LLT SrcTy = MRI.getType(SrcVec); 3755 if (!isLegalOrBeforeLegalizer( 3756 {TargetOpcode::G_BUILD_VECTOR, {SrcTy, SrcTy.getElementType()}})) 3757 return false; 3758 3759 auto Cst = getIConstantVRegValWithLookThrough(MI.getOperand(2).getReg(), MRI); 3760 if (!Cst || Cst->Value.getZExtValue() >= SrcTy.getNumElements()) 3761 return false; 3762 3763 unsigned VecIdx = Cst->Value.getZExtValue(); 3764 MachineInstr *BuildVecMI = 3765 getOpcodeDef(TargetOpcode::G_BUILD_VECTOR, SrcVec, MRI); 3766 if (!BuildVecMI) { 3767 BuildVecMI = getOpcodeDef(TargetOpcode::G_BUILD_VECTOR_TRUNC, SrcVec, MRI); 3768 if (!BuildVecMI) 3769 return false; 3770 LLT ScalarTy = MRI.getType(BuildVecMI->getOperand(1).getReg()); 3771 if (!isLegalOrBeforeLegalizer( 3772 {TargetOpcode::G_BUILD_VECTOR_TRUNC, {SrcTy, ScalarTy}})) 3773 return false; 3774 } 3775 3776 EVT Ty(getMVTForLLT(SrcTy)); 3777 if (!MRI.hasOneNonDBGUse(SrcVec) && 3778 !getTargetLowering().aggressivelyPreferBuildVectorSources(Ty)) 3779 return false; 3780 3781 Reg = BuildVecMI->getOperand(VecIdx + 1).getReg(); 3782 return true; 3783 } 3784 3785 void CombinerHelper::applyExtractVecEltBuildVec(MachineInstr &MI, 3786 Register &Reg) { 3787 // Check the type of the register, since it may have come from a 3788 // G_BUILD_VECTOR_TRUNC. 3789 LLT ScalarTy = MRI.getType(Reg); 3790 Register DstReg = MI.getOperand(0).getReg(); 3791 LLT DstTy = MRI.getType(DstReg); 3792 3793 Builder.setInstrAndDebugLoc(MI); 3794 if (ScalarTy != DstTy) { 3795 assert(ScalarTy.getSizeInBits() > DstTy.getSizeInBits()); 3796 Builder.buildTrunc(DstReg, Reg); 3797 MI.eraseFromParent(); 3798 return; 3799 } 3800 replaceSingleDefInstWithReg(MI, Reg); 3801 } 3802 3803 bool CombinerHelper::matchExtractAllEltsFromBuildVector( 3804 MachineInstr &MI, 3805 SmallVectorImpl<std::pair<Register, MachineInstr *>> &SrcDstPairs) { 3806 assert(MI.getOpcode() == TargetOpcode::G_BUILD_VECTOR); 3807 // This combine tries to find build_vector's which have every source element 3808 // extracted using G_EXTRACT_VECTOR_ELT. This can happen when transforms like 3809 // the masked load scalarization is run late in the pipeline. There's already 3810 // a combine for a similar pattern starting from the extract, but that 3811 // doesn't attempt to do it if there are multiple uses of the build_vector, 3812 // which in this case is true. Starting the combine from the build_vector 3813 // feels more natural than trying to find sibling nodes of extracts. 3814 // E.g. 3815 // %vec(<4 x s32>) = G_BUILD_VECTOR %s1(s32), %s2, %s3, %s4 3816 // %ext1 = G_EXTRACT_VECTOR_ELT %vec, 0 3817 // %ext2 = G_EXTRACT_VECTOR_ELT %vec, 1 3818 // %ext3 = G_EXTRACT_VECTOR_ELT %vec, 2 3819 // %ext4 = G_EXTRACT_VECTOR_ELT %vec, 3 3820 // ==> 3821 // replace ext{1,2,3,4} with %s{1,2,3,4} 3822 3823 Register DstReg = MI.getOperand(0).getReg(); 3824 LLT DstTy = MRI.getType(DstReg); 3825 unsigned NumElts = DstTy.getNumElements(); 3826 3827 SmallBitVector ExtractedElts(NumElts); 3828 for (auto &II : make_range(MRI.use_instr_nodbg_begin(DstReg), 3829 MRI.use_instr_nodbg_end())) { 3830 if (II.getOpcode() != TargetOpcode::G_EXTRACT_VECTOR_ELT) 3831 return false; 3832 auto Cst = getIConstantVRegVal(II.getOperand(2).getReg(), MRI); 3833 if (!Cst) 3834 return false; 3835 unsigned Idx = Cst.getValue().getZExtValue(); 3836 if (Idx >= NumElts) 3837 return false; // Out of range. 3838 ExtractedElts.set(Idx); 3839 SrcDstPairs.emplace_back( 3840 std::make_pair(MI.getOperand(Idx + 1).getReg(), &II)); 3841 } 3842 // Match if every element was extracted. 3843 return ExtractedElts.all(); 3844 } 3845 3846 void CombinerHelper::applyExtractAllEltsFromBuildVector( 3847 MachineInstr &MI, 3848 SmallVectorImpl<std::pair<Register, MachineInstr *>> &SrcDstPairs) { 3849 assert(MI.getOpcode() == TargetOpcode::G_BUILD_VECTOR); 3850 for (auto &Pair : SrcDstPairs) { 3851 auto *ExtMI = Pair.second; 3852 replaceRegWith(MRI, ExtMI->getOperand(0).getReg(), Pair.first); 3853 ExtMI->eraseFromParent(); 3854 } 3855 MI.eraseFromParent(); 3856 } 3857 3858 void CombinerHelper::applyBuildFn( 3859 MachineInstr &MI, std::function<void(MachineIRBuilder &)> &MatchInfo) { 3860 Builder.setInstrAndDebugLoc(MI); 3861 MatchInfo(Builder); 3862 MI.eraseFromParent(); 3863 } 3864 3865 void CombinerHelper::applyBuildFnNoErase( 3866 MachineInstr &MI, std::function<void(MachineIRBuilder &)> &MatchInfo) { 3867 Builder.setInstrAndDebugLoc(MI); 3868 MatchInfo(Builder); 3869 } 3870 3871 /// Match an FSHL or FSHR that can be combined to a ROTR or ROTL rotate. 3872 bool CombinerHelper::matchFunnelShiftToRotate(MachineInstr &MI) { 3873 unsigned Opc = MI.getOpcode(); 3874 assert(Opc == TargetOpcode::G_FSHL || Opc == TargetOpcode::G_FSHR); 3875 Register X = MI.getOperand(1).getReg(); 3876 Register Y = MI.getOperand(2).getReg(); 3877 if (X != Y) 3878 return false; 3879 unsigned RotateOpc = 3880 Opc == TargetOpcode::G_FSHL ? TargetOpcode::G_ROTL : TargetOpcode::G_ROTR; 3881 return isLegalOrBeforeLegalizer({RotateOpc, {MRI.getType(X), MRI.getType(Y)}}); 3882 } 3883 3884 void CombinerHelper::applyFunnelShiftToRotate(MachineInstr &MI) { 3885 unsigned Opc = MI.getOpcode(); 3886 assert(Opc == TargetOpcode::G_FSHL || Opc == TargetOpcode::G_FSHR); 3887 bool IsFSHL = Opc == TargetOpcode::G_FSHL; 3888 Observer.changingInstr(MI); 3889 MI.setDesc(Builder.getTII().get(IsFSHL ? TargetOpcode::G_ROTL 3890 : TargetOpcode::G_ROTR)); 3891 MI.RemoveOperand(2); 3892 Observer.changedInstr(MI); 3893 } 3894 3895 // Fold (rot x, c) -> (rot x, c % BitSize) 3896 bool CombinerHelper::matchRotateOutOfRange(MachineInstr &MI) { 3897 assert(MI.getOpcode() == TargetOpcode::G_ROTL || 3898 MI.getOpcode() == TargetOpcode::G_ROTR); 3899 unsigned Bitsize = 3900 MRI.getType(MI.getOperand(0).getReg()).getScalarSizeInBits(); 3901 Register AmtReg = MI.getOperand(2).getReg(); 3902 bool OutOfRange = false; 3903 auto MatchOutOfRange = [Bitsize, &OutOfRange](const Constant *C) { 3904 if (auto *CI = dyn_cast<ConstantInt>(C)) 3905 OutOfRange |= CI->getValue().uge(Bitsize); 3906 return true; 3907 }; 3908 return matchUnaryPredicate(MRI, AmtReg, MatchOutOfRange) && OutOfRange; 3909 } 3910 3911 void CombinerHelper::applyRotateOutOfRange(MachineInstr &MI) { 3912 assert(MI.getOpcode() == TargetOpcode::G_ROTL || 3913 MI.getOpcode() == TargetOpcode::G_ROTR); 3914 unsigned Bitsize = 3915 MRI.getType(MI.getOperand(0).getReg()).getScalarSizeInBits(); 3916 Builder.setInstrAndDebugLoc(MI); 3917 Register Amt = MI.getOperand(2).getReg(); 3918 LLT AmtTy = MRI.getType(Amt); 3919 auto Bits = Builder.buildConstant(AmtTy, Bitsize); 3920 Amt = Builder.buildURem(AmtTy, MI.getOperand(2).getReg(), Bits).getReg(0); 3921 Observer.changingInstr(MI); 3922 MI.getOperand(2).setReg(Amt); 3923 Observer.changedInstr(MI); 3924 } 3925 3926 bool CombinerHelper::matchICmpToTrueFalseKnownBits(MachineInstr &MI, 3927 int64_t &MatchInfo) { 3928 assert(MI.getOpcode() == TargetOpcode::G_ICMP); 3929 auto Pred = static_cast<CmpInst::Predicate>(MI.getOperand(1).getPredicate()); 3930 auto KnownLHS = KB->getKnownBits(MI.getOperand(2).getReg()); 3931 auto KnownRHS = KB->getKnownBits(MI.getOperand(3).getReg()); 3932 Optional<bool> KnownVal; 3933 switch (Pred) { 3934 default: 3935 llvm_unreachable("Unexpected G_ICMP predicate?"); 3936 case CmpInst::ICMP_EQ: 3937 KnownVal = KnownBits::eq(KnownLHS, KnownRHS); 3938 break; 3939 case CmpInst::ICMP_NE: 3940 KnownVal = KnownBits::ne(KnownLHS, KnownRHS); 3941 break; 3942 case CmpInst::ICMP_SGE: 3943 KnownVal = KnownBits::sge(KnownLHS, KnownRHS); 3944 break; 3945 case CmpInst::ICMP_SGT: 3946 KnownVal = KnownBits::sgt(KnownLHS, KnownRHS); 3947 break; 3948 case CmpInst::ICMP_SLE: 3949 KnownVal = KnownBits::sle(KnownLHS, KnownRHS); 3950 break; 3951 case CmpInst::ICMP_SLT: 3952 KnownVal = KnownBits::slt(KnownLHS, KnownRHS); 3953 break; 3954 case CmpInst::ICMP_UGE: 3955 KnownVal = KnownBits::uge(KnownLHS, KnownRHS); 3956 break; 3957 case CmpInst::ICMP_UGT: 3958 KnownVal = KnownBits::ugt(KnownLHS, KnownRHS); 3959 break; 3960 case CmpInst::ICMP_ULE: 3961 KnownVal = KnownBits::ule(KnownLHS, KnownRHS); 3962 break; 3963 case CmpInst::ICMP_ULT: 3964 KnownVal = KnownBits::ult(KnownLHS, KnownRHS); 3965 break; 3966 } 3967 if (!KnownVal) 3968 return false; 3969 MatchInfo = 3970 *KnownVal 3971 ? getICmpTrueVal(getTargetLowering(), 3972 /*IsVector = */ 3973 MRI.getType(MI.getOperand(0).getReg()).isVector(), 3974 /* IsFP = */ false) 3975 : 0; 3976 return true; 3977 } 3978 3979 bool CombinerHelper::matchICmpToLHSKnownBits( 3980 MachineInstr &MI, std::function<void(MachineIRBuilder &)> &MatchInfo) { 3981 assert(MI.getOpcode() == TargetOpcode::G_ICMP); 3982 // Given: 3983 // 3984 // %x = G_WHATEVER (... x is known to be 0 or 1 ...) 3985 // %cmp = G_ICMP ne %x, 0 3986 // 3987 // Or: 3988 // 3989 // %x = G_WHATEVER (... x is known to be 0 or 1 ...) 3990 // %cmp = G_ICMP eq %x, 1 3991 // 3992 // We can replace %cmp with %x assuming true is 1 on the target. 3993 auto Pred = static_cast<CmpInst::Predicate>(MI.getOperand(1).getPredicate()); 3994 if (!CmpInst::isEquality(Pred)) 3995 return false; 3996 Register Dst = MI.getOperand(0).getReg(); 3997 LLT DstTy = MRI.getType(Dst); 3998 if (getICmpTrueVal(getTargetLowering(), DstTy.isVector(), 3999 /* IsFP = */ false) != 1) 4000 return false; 4001 int64_t OneOrZero = Pred == CmpInst::ICMP_EQ; 4002 if (!mi_match(MI.getOperand(3).getReg(), MRI, m_SpecificICst(OneOrZero))) 4003 return false; 4004 Register LHS = MI.getOperand(2).getReg(); 4005 auto KnownLHS = KB->getKnownBits(LHS); 4006 if (KnownLHS.getMinValue() != 0 || KnownLHS.getMaxValue() != 1) 4007 return false; 4008 // Make sure replacing Dst with the LHS is a legal operation. 4009 LLT LHSTy = MRI.getType(LHS); 4010 unsigned LHSSize = LHSTy.getSizeInBits(); 4011 unsigned DstSize = DstTy.getSizeInBits(); 4012 unsigned Op = TargetOpcode::COPY; 4013 if (DstSize != LHSSize) 4014 Op = DstSize < LHSSize ? TargetOpcode::G_TRUNC : TargetOpcode::G_ZEXT; 4015 if (!isLegalOrBeforeLegalizer({Op, {DstTy, LHSTy}})) 4016 return false; 4017 MatchInfo = [=](MachineIRBuilder &B) { B.buildInstr(Op, {Dst}, {LHS}); }; 4018 return true; 4019 } 4020 4021 // Replace (and (or x, c1), c2) with (and x, c2) iff c1 & c2 == 0 4022 bool CombinerHelper::matchAndOrDisjointMask( 4023 MachineInstr &MI, std::function<void(MachineIRBuilder &)> &MatchInfo) { 4024 assert(MI.getOpcode() == TargetOpcode::G_AND); 4025 4026 // Ignore vector types to simplify matching the two constants. 4027 // TODO: do this for vectors and scalars via a demanded bits analysis. 4028 LLT Ty = MRI.getType(MI.getOperand(0).getReg()); 4029 if (Ty.isVector()) 4030 return false; 4031 4032 Register Src; 4033 int64_t MaskAnd; 4034 int64_t MaskOr; 4035 if (!mi_match(MI, MRI, 4036 m_GAnd(m_GOr(m_Reg(Src), m_ICst(MaskOr)), m_ICst(MaskAnd)))) 4037 return false; 4038 4039 // Check if MaskOr could turn on any bits in Src. 4040 if (MaskAnd & MaskOr) 4041 return false; 4042 4043 MatchInfo = [=, &MI](MachineIRBuilder &B) { 4044 Observer.changingInstr(MI); 4045 MI.getOperand(1).setReg(Src); 4046 Observer.changedInstr(MI); 4047 }; 4048 return true; 4049 } 4050 4051 /// Form a G_SBFX from a G_SEXT_INREG fed by a right shift. 4052 bool CombinerHelper::matchBitfieldExtractFromSExtInReg( 4053 MachineInstr &MI, std::function<void(MachineIRBuilder &)> &MatchInfo) { 4054 assert(MI.getOpcode() == TargetOpcode::G_SEXT_INREG); 4055 Register Dst = MI.getOperand(0).getReg(); 4056 Register Src = MI.getOperand(1).getReg(); 4057 LLT Ty = MRI.getType(Src); 4058 LLT ExtractTy = getTargetLowering().getPreferredShiftAmountTy(Ty); 4059 if (!LI || !LI->isLegalOrCustom({TargetOpcode::G_SBFX, {Ty, ExtractTy}})) 4060 return false; 4061 int64_t Width = MI.getOperand(2).getImm(); 4062 Register ShiftSrc; 4063 int64_t ShiftImm; 4064 if (!mi_match( 4065 Src, MRI, 4066 m_OneNonDBGUse(m_any_of(m_GAShr(m_Reg(ShiftSrc), m_ICst(ShiftImm)), 4067 m_GLShr(m_Reg(ShiftSrc), m_ICst(ShiftImm)))))) 4068 return false; 4069 if (ShiftImm < 0 || ShiftImm + Width > Ty.getScalarSizeInBits()) 4070 return false; 4071 4072 MatchInfo = [=](MachineIRBuilder &B) { 4073 auto Cst1 = B.buildConstant(ExtractTy, ShiftImm); 4074 auto Cst2 = B.buildConstant(ExtractTy, Width); 4075 B.buildSbfx(Dst, ShiftSrc, Cst1, Cst2); 4076 }; 4077 return true; 4078 } 4079 4080 /// Form a G_UBFX from "(a srl b) & mask", where b and mask are constants. 4081 bool CombinerHelper::matchBitfieldExtractFromAnd( 4082 MachineInstr &MI, std::function<void(MachineIRBuilder &)> &MatchInfo) { 4083 assert(MI.getOpcode() == TargetOpcode::G_AND); 4084 Register Dst = MI.getOperand(0).getReg(); 4085 LLT Ty = MRI.getType(Dst); 4086 if (!getTargetLowering().isConstantUnsignedBitfieldExtactLegal( 4087 TargetOpcode::G_UBFX, Ty, Ty)) 4088 return false; 4089 4090 int64_t AndImm, LSBImm; 4091 Register ShiftSrc; 4092 const unsigned Size = Ty.getScalarSizeInBits(); 4093 if (!mi_match(MI.getOperand(0).getReg(), MRI, 4094 m_GAnd(m_OneNonDBGUse(m_GLShr(m_Reg(ShiftSrc), m_ICst(LSBImm))), 4095 m_ICst(AndImm)))) 4096 return false; 4097 4098 // The mask is a mask of the low bits iff imm & (imm+1) == 0. 4099 auto MaybeMask = static_cast<uint64_t>(AndImm); 4100 if (MaybeMask & (MaybeMask + 1)) 4101 return false; 4102 4103 // LSB must fit within the register. 4104 if (static_cast<uint64_t>(LSBImm) >= Size) 4105 return false; 4106 4107 LLT ExtractTy = getTargetLowering().getPreferredShiftAmountTy(Ty); 4108 uint64_t Width = APInt(Size, AndImm).countTrailingOnes(); 4109 MatchInfo = [=](MachineIRBuilder &B) { 4110 auto WidthCst = B.buildConstant(ExtractTy, Width); 4111 auto LSBCst = B.buildConstant(ExtractTy, LSBImm); 4112 B.buildInstr(TargetOpcode::G_UBFX, {Dst}, {ShiftSrc, LSBCst, WidthCst}); 4113 }; 4114 return true; 4115 } 4116 4117 bool CombinerHelper::matchBitfieldExtractFromShr( 4118 MachineInstr &MI, std::function<void(MachineIRBuilder &)> &MatchInfo) { 4119 const unsigned Opcode = MI.getOpcode(); 4120 assert(Opcode == TargetOpcode::G_ASHR || Opcode == TargetOpcode::G_LSHR); 4121 4122 const Register Dst = MI.getOperand(0).getReg(); 4123 4124 const unsigned ExtrOpcode = Opcode == TargetOpcode::G_ASHR 4125 ? TargetOpcode::G_SBFX 4126 : TargetOpcode::G_UBFX; 4127 4128 // Check if the type we would use for the extract is legal 4129 LLT Ty = MRI.getType(Dst); 4130 LLT ExtractTy = getTargetLowering().getPreferredShiftAmountTy(Ty); 4131 if (!LI || !LI->isLegalOrCustom({ExtrOpcode, {Ty, ExtractTy}})) 4132 return false; 4133 4134 Register ShlSrc; 4135 int64_t ShrAmt; 4136 int64_t ShlAmt; 4137 const unsigned Size = Ty.getScalarSizeInBits(); 4138 4139 // Try to match shr (shl x, c1), c2 4140 if (!mi_match(Dst, MRI, 4141 m_BinOp(Opcode, 4142 m_OneNonDBGUse(m_GShl(m_Reg(ShlSrc), m_ICst(ShlAmt))), 4143 m_ICst(ShrAmt)))) 4144 return false; 4145 4146 // Make sure that the shift sizes can fit a bitfield extract 4147 if (ShlAmt < 0 || ShlAmt > ShrAmt || ShrAmt >= Size) 4148 return false; 4149 4150 // Skip this combine if the G_SEXT_INREG combine could handle it 4151 if (Opcode == TargetOpcode::G_ASHR && ShlAmt == ShrAmt) 4152 return false; 4153 4154 // Calculate start position and width of the extract 4155 const int64_t Pos = ShrAmt - ShlAmt; 4156 const int64_t Width = Size - ShrAmt; 4157 4158 MatchInfo = [=](MachineIRBuilder &B) { 4159 auto WidthCst = B.buildConstant(ExtractTy, Width); 4160 auto PosCst = B.buildConstant(ExtractTy, Pos); 4161 B.buildInstr(ExtrOpcode, {Dst}, {ShlSrc, PosCst, WidthCst}); 4162 }; 4163 return true; 4164 } 4165 4166 bool CombinerHelper::matchBitfieldExtractFromShrAnd( 4167 MachineInstr &MI, std::function<void(MachineIRBuilder &)> &MatchInfo) { 4168 const unsigned Opcode = MI.getOpcode(); 4169 assert(Opcode == TargetOpcode::G_LSHR || Opcode == TargetOpcode::G_ASHR); 4170 4171 const Register Dst = MI.getOperand(0).getReg(); 4172 LLT Ty = MRI.getType(Dst); 4173 if (!getTargetLowering().isConstantUnsignedBitfieldExtactLegal( 4174 TargetOpcode::G_UBFX, Ty, Ty)) 4175 return false; 4176 4177 // Try to match shr (and x, c1), c2 4178 Register AndSrc; 4179 int64_t ShrAmt; 4180 int64_t SMask; 4181 if (!mi_match(Dst, MRI, 4182 m_BinOp(Opcode, 4183 m_OneNonDBGUse(m_GAnd(m_Reg(AndSrc), m_ICst(SMask))), 4184 m_ICst(ShrAmt)))) 4185 return false; 4186 4187 const unsigned Size = Ty.getScalarSizeInBits(); 4188 if (ShrAmt < 0 || ShrAmt >= Size) 4189 return false; 4190 4191 // Check that ubfx can do the extraction, with no holes in the mask. 4192 uint64_t UMask = SMask; 4193 UMask |= maskTrailingOnes<uint64_t>(ShrAmt); 4194 UMask &= maskTrailingOnes<uint64_t>(Size); 4195 if (!isMask_64(UMask)) 4196 return false; 4197 4198 // Calculate start position and width of the extract. 4199 const int64_t Pos = ShrAmt; 4200 const int64_t Width = countTrailingOnes(UMask) - ShrAmt; 4201 4202 // It's preferable to keep the shift, rather than form G_SBFX. 4203 // TODO: remove the G_AND via demanded bits analysis. 4204 if (Opcode == TargetOpcode::G_ASHR && Width + ShrAmt == Size) 4205 return false; 4206 4207 MatchInfo = [=](MachineIRBuilder &B) { 4208 auto WidthCst = B.buildConstant(Ty, Width); 4209 auto PosCst = B.buildConstant(Ty, Pos); 4210 B.buildInstr(TargetOpcode::G_UBFX, {Dst}, {AndSrc, PosCst, WidthCst}); 4211 }; 4212 return true; 4213 } 4214 4215 bool CombinerHelper::reassociationCanBreakAddressingModePattern( 4216 MachineInstr &PtrAdd) { 4217 assert(PtrAdd.getOpcode() == TargetOpcode::G_PTR_ADD); 4218 4219 Register Src1Reg = PtrAdd.getOperand(1).getReg(); 4220 MachineInstr *Src1Def = getOpcodeDef(TargetOpcode::G_PTR_ADD, Src1Reg, MRI); 4221 if (!Src1Def) 4222 return false; 4223 4224 Register Src2Reg = PtrAdd.getOperand(2).getReg(); 4225 4226 if (MRI.hasOneNonDBGUse(Src1Reg)) 4227 return false; 4228 4229 auto C1 = getIConstantVRegVal(Src1Def->getOperand(2).getReg(), MRI); 4230 if (!C1) 4231 return false; 4232 auto C2 = getIConstantVRegVal(Src2Reg, MRI); 4233 if (!C2) 4234 return false; 4235 4236 const APInt &C1APIntVal = *C1; 4237 const APInt &C2APIntVal = *C2; 4238 const int64_t CombinedValue = (C1APIntVal + C2APIntVal).getSExtValue(); 4239 4240 for (auto &UseMI : MRI.use_nodbg_instructions(Src1Reg)) { 4241 // This combine may end up running before ptrtoint/inttoptr combines 4242 // manage to eliminate redundant conversions, so try to look through them. 4243 MachineInstr *ConvUseMI = &UseMI; 4244 unsigned ConvUseOpc = ConvUseMI->getOpcode(); 4245 while (ConvUseOpc == TargetOpcode::G_INTTOPTR || 4246 ConvUseOpc == TargetOpcode::G_PTRTOINT) { 4247 Register DefReg = ConvUseMI->getOperand(0).getReg(); 4248 if (!MRI.hasOneNonDBGUse(DefReg)) 4249 break; 4250 ConvUseMI = &*MRI.use_instr_nodbg_begin(DefReg); 4251 ConvUseOpc = ConvUseMI->getOpcode(); 4252 } 4253 auto LoadStore = ConvUseOpc == TargetOpcode::G_LOAD || 4254 ConvUseOpc == TargetOpcode::G_STORE; 4255 if (!LoadStore) 4256 continue; 4257 // Is x[offset2] already not a legal addressing mode? If so then 4258 // reassociating the constants breaks nothing (we test offset2 because 4259 // that's the one we hope to fold into the load or store). 4260 TargetLoweringBase::AddrMode AM; 4261 AM.HasBaseReg = true; 4262 AM.BaseOffs = C2APIntVal.getSExtValue(); 4263 unsigned AS = 4264 MRI.getType(ConvUseMI->getOperand(1).getReg()).getAddressSpace(); 4265 Type *AccessTy = 4266 getTypeForLLT(MRI.getType(ConvUseMI->getOperand(0).getReg()), 4267 PtrAdd.getMF()->getFunction().getContext()); 4268 const auto &TLI = *PtrAdd.getMF()->getSubtarget().getTargetLowering(); 4269 if (!TLI.isLegalAddressingMode(PtrAdd.getMF()->getDataLayout(), AM, 4270 AccessTy, AS)) 4271 continue; 4272 4273 // Would x[offset1+offset2] still be a legal addressing mode? 4274 AM.BaseOffs = CombinedValue; 4275 if (!TLI.isLegalAddressingMode(PtrAdd.getMF()->getDataLayout(), AM, 4276 AccessTy, AS)) 4277 return true; 4278 } 4279 4280 return false; 4281 } 4282 4283 bool CombinerHelper::matchReassocConstantInnerRHS(GPtrAdd &MI, 4284 MachineInstr *RHS, 4285 BuildFnTy &MatchInfo) { 4286 // G_PTR_ADD(BASE, G_ADD(X, C)) -> G_PTR_ADD(G_PTR_ADD(BASE, X), C) 4287 Register Src1Reg = MI.getOperand(1).getReg(); 4288 if (RHS->getOpcode() != TargetOpcode::G_ADD) 4289 return false; 4290 auto C2 = getIConstantVRegVal(RHS->getOperand(2).getReg(), MRI); 4291 if (!C2) 4292 return false; 4293 4294 MatchInfo = [=, &MI](MachineIRBuilder &B) { 4295 LLT PtrTy = MRI.getType(MI.getOperand(0).getReg()); 4296 4297 auto NewBase = 4298 Builder.buildPtrAdd(PtrTy, Src1Reg, RHS->getOperand(1).getReg()); 4299 Observer.changingInstr(MI); 4300 MI.getOperand(1).setReg(NewBase.getReg(0)); 4301 MI.getOperand(2).setReg(RHS->getOperand(2).getReg()); 4302 Observer.changedInstr(MI); 4303 }; 4304 return !reassociationCanBreakAddressingModePattern(MI); 4305 } 4306 4307 bool CombinerHelper::matchReassocConstantInnerLHS(GPtrAdd &MI, 4308 MachineInstr *LHS, 4309 MachineInstr *RHS, 4310 BuildFnTy &MatchInfo) { 4311 // G_PTR_ADD (G_PTR_ADD X, C), Y) -> (G_PTR_ADD (G_PTR_ADD(X, Y), C) 4312 // if and only if (G_PTR_ADD X, C) has one use. 4313 Register LHSBase; 4314 Optional<ValueAndVReg> LHSCstOff; 4315 if (!mi_match(MI.getBaseReg(), MRI, 4316 m_OneNonDBGUse(m_GPtrAdd(m_Reg(LHSBase), m_GCst(LHSCstOff))))) 4317 return false; 4318 4319 auto *LHSPtrAdd = cast<GPtrAdd>(LHS); 4320 MatchInfo = [=, &MI](MachineIRBuilder &B) { 4321 // When we change LHSPtrAdd's offset register we might cause it to use a reg 4322 // before its def. Sink the instruction so the outer PTR_ADD to ensure this 4323 // doesn't happen. 4324 LHSPtrAdd->moveBefore(&MI); 4325 Register RHSReg = MI.getOffsetReg(); 4326 Observer.changingInstr(MI); 4327 MI.getOperand(2).setReg(LHSCstOff->VReg); 4328 Observer.changedInstr(MI); 4329 Observer.changingInstr(*LHSPtrAdd); 4330 LHSPtrAdd->getOperand(2).setReg(RHSReg); 4331 Observer.changedInstr(*LHSPtrAdd); 4332 }; 4333 return !reassociationCanBreakAddressingModePattern(MI); 4334 } 4335 4336 bool CombinerHelper::matchReassocFoldConstantsInSubTree(GPtrAdd &MI, 4337 MachineInstr *LHS, 4338 MachineInstr *RHS, 4339 BuildFnTy &MatchInfo) { 4340 // G_PTR_ADD(G_PTR_ADD(BASE, C1), C2) -> G_PTR_ADD(BASE, C1+C2) 4341 auto *LHSPtrAdd = dyn_cast<GPtrAdd>(LHS); 4342 if (!LHSPtrAdd) 4343 return false; 4344 4345 Register Src2Reg = MI.getOperand(2).getReg(); 4346 Register LHSSrc1 = LHSPtrAdd->getBaseReg(); 4347 Register LHSSrc2 = LHSPtrAdd->getOffsetReg(); 4348 auto C1 = getIConstantVRegVal(LHSSrc2, MRI); 4349 if (!C1) 4350 return false; 4351 auto C2 = getIConstantVRegVal(Src2Reg, MRI); 4352 if (!C2) 4353 return false; 4354 4355 MatchInfo = [=, &MI](MachineIRBuilder &B) { 4356 auto NewCst = B.buildConstant(MRI.getType(Src2Reg), *C1 + *C2); 4357 Observer.changingInstr(MI); 4358 MI.getOperand(1).setReg(LHSSrc1); 4359 MI.getOperand(2).setReg(NewCst.getReg(0)); 4360 Observer.changedInstr(MI); 4361 }; 4362 return !reassociationCanBreakAddressingModePattern(MI); 4363 } 4364 4365 bool CombinerHelper::matchReassocPtrAdd(MachineInstr &MI, 4366 BuildFnTy &MatchInfo) { 4367 auto &PtrAdd = cast<GPtrAdd>(MI); 4368 // We're trying to match a few pointer computation patterns here for 4369 // re-association opportunities. 4370 // 1) Isolating a constant operand to be on the RHS, e.g.: 4371 // G_PTR_ADD(BASE, G_ADD(X, C)) -> G_PTR_ADD(G_PTR_ADD(BASE, X), C) 4372 // 4373 // 2) Folding two constants in each sub-tree as long as such folding 4374 // doesn't break a legal addressing mode. 4375 // G_PTR_ADD(G_PTR_ADD(BASE, C1), C2) -> G_PTR_ADD(BASE, C1+C2) 4376 // 4377 // 3) Move a constant from the LHS of an inner op to the RHS of the outer. 4378 // G_PTR_ADD (G_PTR_ADD X, C), Y) -> G_PTR_ADD (G_PTR_ADD(X, Y), C) 4379 // iif (G_PTR_ADD X, C) has one use. 4380 MachineInstr *LHS = MRI.getVRegDef(PtrAdd.getBaseReg()); 4381 MachineInstr *RHS = MRI.getVRegDef(PtrAdd.getOffsetReg()); 4382 4383 // Try to match example 2. 4384 if (matchReassocFoldConstantsInSubTree(PtrAdd, LHS, RHS, MatchInfo)) 4385 return true; 4386 4387 // Try to match example 3. 4388 if (matchReassocConstantInnerLHS(PtrAdd, LHS, RHS, MatchInfo)) 4389 return true; 4390 4391 // Try to match example 1. 4392 if (matchReassocConstantInnerRHS(PtrAdd, RHS, MatchInfo)) 4393 return true; 4394 4395 return false; 4396 } 4397 4398 bool CombinerHelper::matchConstantFold(MachineInstr &MI, APInt &MatchInfo) { 4399 Register Op1 = MI.getOperand(1).getReg(); 4400 Register Op2 = MI.getOperand(2).getReg(); 4401 auto MaybeCst = ConstantFoldBinOp(MI.getOpcode(), Op1, Op2, MRI); 4402 if (!MaybeCst) 4403 return false; 4404 MatchInfo = *MaybeCst; 4405 return true; 4406 } 4407 4408 bool CombinerHelper::matchNarrowBinopFeedingAnd( 4409 MachineInstr &MI, std::function<void(MachineIRBuilder &)> &MatchInfo) { 4410 // Look for a binop feeding into an AND with a mask: 4411 // 4412 // %add = G_ADD %lhs, %rhs 4413 // %and = G_AND %add, 000...11111111 4414 // 4415 // Check if it's possible to perform the binop at a narrower width and zext 4416 // back to the original width like so: 4417 // 4418 // %narrow_lhs = G_TRUNC %lhs 4419 // %narrow_rhs = G_TRUNC %rhs 4420 // %narrow_add = G_ADD %narrow_lhs, %narrow_rhs 4421 // %new_add = G_ZEXT %narrow_add 4422 // %and = G_AND %new_add, 000...11111111 4423 // 4424 // This can allow later combines to eliminate the G_AND if it turns out 4425 // that the mask is irrelevant. 4426 assert(MI.getOpcode() == TargetOpcode::G_AND); 4427 Register Dst = MI.getOperand(0).getReg(); 4428 Register AndLHS = MI.getOperand(1).getReg(); 4429 Register AndRHS = MI.getOperand(2).getReg(); 4430 LLT WideTy = MRI.getType(Dst); 4431 4432 // If the potential binop has more than one use, then it's possible that one 4433 // of those uses will need its full width. 4434 if (!WideTy.isScalar() || !MRI.hasOneNonDBGUse(AndLHS)) 4435 return false; 4436 4437 // Check if the LHS feeding the AND is impacted by the high bits that we're 4438 // masking out. 4439 // 4440 // e.g. for 64-bit x, y: 4441 // 4442 // add_64(x, y) & 65535 == zext(add_16(trunc(x), trunc(y))) & 65535 4443 MachineInstr *LHSInst = getDefIgnoringCopies(AndLHS, MRI); 4444 if (!LHSInst) 4445 return false; 4446 unsigned LHSOpc = LHSInst->getOpcode(); 4447 switch (LHSOpc) { 4448 default: 4449 return false; 4450 case TargetOpcode::G_ADD: 4451 case TargetOpcode::G_SUB: 4452 case TargetOpcode::G_MUL: 4453 case TargetOpcode::G_AND: 4454 case TargetOpcode::G_OR: 4455 case TargetOpcode::G_XOR: 4456 break; 4457 } 4458 4459 // Find the mask on the RHS. 4460 auto Cst = getIConstantVRegValWithLookThrough(AndRHS, MRI); 4461 if (!Cst) 4462 return false; 4463 auto Mask = Cst->Value; 4464 if (!Mask.isMask()) 4465 return false; 4466 4467 // No point in combining if there's nothing to truncate. 4468 unsigned NarrowWidth = Mask.countTrailingOnes(); 4469 if (NarrowWidth == WideTy.getSizeInBits()) 4470 return false; 4471 LLT NarrowTy = LLT::scalar(NarrowWidth); 4472 4473 // Check if adding the zext + truncates could be harmful. 4474 auto &MF = *MI.getMF(); 4475 const auto &TLI = getTargetLowering(); 4476 LLVMContext &Ctx = MF.getFunction().getContext(); 4477 auto &DL = MF.getDataLayout(); 4478 if (!TLI.isTruncateFree(WideTy, NarrowTy, DL, Ctx) || 4479 !TLI.isZExtFree(NarrowTy, WideTy, DL, Ctx)) 4480 return false; 4481 if (!isLegalOrBeforeLegalizer({TargetOpcode::G_TRUNC, {NarrowTy, WideTy}}) || 4482 !isLegalOrBeforeLegalizer({TargetOpcode::G_ZEXT, {WideTy, NarrowTy}})) 4483 return false; 4484 Register BinOpLHS = LHSInst->getOperand(1).getReg(); 4485 Register BinOpRHS = LHSInst->getOperand(2).getReg(); 4486 MatchInfo = [=, &MI](MachineIRBuilder &B) { 4487 auto NarrowLHS = Builder.buildTrunc(NarrowTy, BinOpLHS); 4488 auto NarrowRHS = Builder.buildTrunc(NarrowTy, BinOpRHS); 4489 auto NarrowBinOp = 4490 Builder.buildInstr(LHSOpc, {NarrowTy}, {NarrowLHS, NarrowRHS}); 4491 auto Ext = Builder.buildZExt(WideTy, NarrowBinOp); 4492 Observer.changingInstr(MI); 4493 MI.getOperand(1).setReg(Ext.getReg(0)); 4494 Observer.changedInstr(MI); 4495 }; 4496 return true; 4497 } 4498 4499 bool CombinerHelper::matchMulOBy2(MachineInstr &MI, BuildFnTy &MatchInfo) { 4500 unsigned Opc = MI.getOpcode(); 4501 assert(Opc == TargetOpcode::G_UMULO || Opc == TargetOpcode::G_SMULO); 4502 // Check for a constant 2 or a splat of 2 on the RHS. 4503 auto RHS = MI.getOperand(3).getReg(); 4504 bool IsVector = MRI.getType(RHS).isVector(); 4505 if (!IsVector && !mi_match(MI.getOperand(3).getReg(), MRI, m_SpecificICst(2))) 4506 return false; 4507 if (IsVector) { 4508 // FIXME: There's no mi_match pattern for this yet. 4509 auto *RHSDef = getDefIgnoringCopies(RHS, MRI); 4510 if (!RHSDef) 4511 return false; 4512 auto Splat = getBuildVectorConstantSplat(*RHSDef, MRI); 4513 if (!Splat || *Splat != 2) 4514 return false; 4515 } 4516 4517 MatchInfo = [=, &MI](MachineIRBuilder &B) { 4518 Observer.changingInstr(MI); 4519 unsigned NewOpc = Opc == TargetOpcode::G_UMULO ? TargetOpcode::G_UADDO 4520 : TargetOpcode::G_SADDO; 4521 MI.setDesc(Builder.getTII().get(NewOpc)); 4522 MI.getOperand(3).setReg(MI.getOperand(2).getReg()); 4523 Observer.changedInstr(MI); 4524 }; 4525 return true; 4526 } 4527 4528 MachineInstr *CombinerHelper::buildUDivUsingMul(MachineInstr &MI) { 4529 assert(MI.getOpcode() == TargetOpcode::G_UDIV); 4530 auto &UDiv = cast<GenericMachineInstr>(MI); 4531 Register Dst = UDiv.getReg(0); 4532 Register LHS = UDiv.getReg(1); 4533 Register RHS = UDiv.getReg(2); 4534 LLT Ty = MRI.getType(Dst); 4535 LLT ScalarTy = Ty.getScalarType(); 4536 const unsigned EltBits = ScalarTy.getScalarSizeInBits(); 4537 LLT ShiftAmtTy = getTargetLowering().getPreferredShiftAmountTy(Ty); 4538 LLT ScalarShiftAmtTy = ShiftAmtTy.getScalarType(); 4539 auto &MIB = Builder; 4540 MIB.setInstrAndDebugLoc(MI); 4541 4542 bool UseNPQ = false; 4543 SmallVector<Register, 16> PreShifts, PostShifts, MagicFactors, NPQFactors; 4544 4545 auto BuildUDIVPattern = [&](const Constant *C) { 4546 auto *CI = cast<ConstantInt>(C); 4547 const APInt &Divisor = CI->getValue(); 4548 UnsignedDivisonByConstantInfo magics = 4549 UnsignedDivisonByConstantInfo::get(Divisor); 4550 unsigned PreShift = 0, PostShift = 0; 4551 4552 // If the divisor is even, we can avoid using the expensive fixup by 4553 // shifting the divided value upfront. 4554 if (magics.IsAdd != 0 && !Divisor[0]) { 4555 PreShift = Divisor.countTrailingZeros(); 4556 // Get magic number for the shifted divisor. 4557 magics = 4558 UnsignedDivisonByConstantInfo::get(Divisor.lshr(PreShift), PreShift); 4559 assert(magics.IsAdd == 0 && "Should use cheap fixup now"); 4560 } 4561 4562 APInt Magic = magics.Magic; 4563 4564 unsigned SelNPQ; 4565 if (magics.IsAdd == 0 || Divisor.isOneValue()) { 4566 assert(magics.ShiftAmount < Divisor.getBitWidth() && 4567 "We shouldn't generate an undefined shift!"); 4568 PostShift = magics.ShiftAmount; 4569 SelNPQ = false; 4570 } else { 4571 PostShift = magics.ShiftAmount - 1; 4572 SelNPQ = true; 4573 } 4574 4575 PreShifts.push_back( 4576 MIB.buildConstant(ScalarShiftAmtTy, PreShift).getReg(0)); 4577 MagicFactors.push_back(MIB.buildConstant(ScalarTy, Magic).getReg(0)); 4578 NPQFactors.push_back( 4579 MIB.buildConstant(ScalarTy, 4580 SelNPQ ? APInt::getOneBitSet(EltBits, EltBits - 1) 4581 : APInt::getZero(EltBits)) 4582 .getReg(0)); 4583 PostShifts.push_back( 4584 MIB.buildConstant(ScalarShiftAmtTy, PostShift).getReg(0)); 4585 UseNPQ |= SelNPQ; 4586 return true; 4587 }; 4588 4589 // Collect the shifts/magic values from each element. 4590 bool Matched = matchUnaryPredicate(MRI, RHS, BuildUDIVPattern); 4591 (void)Matched; 4592 assert(Matched && "Expected unary predicate match to succeed"); 4593 4594 Register PreShift, PostShift, MagicFactor, NPQFactor; 4595 auto *RHSDef = getOpcodeDef<GBuildVector>(RHS, MRI); 4596 if (RHSDef) { 4597 PreShift = MIB.buildBuildVector(ShiftAmtTy, PreShifts).getReg(0); 4598 MagicFactor = MIB.buildBuildVector(Ty, MagicFactors).getReg(0); 4599 NPQFactor = MIB.buildBuildVector(Ty, NPQFactors).getReg(0); 4600 PostShift = MIB.buildBuildVector(ShiftAmtTy, PostShifts).getReg(0); 4601 } else { 4602 assert(MRI.getType(RHS).isScalar() && 4603 "Non-build_vector operation should have been a scalar"); 4604 PreShift = PreShifts[0]; 4605 MagicFactor = MagicFactors[0]; 4606 PostShift = PostShifts[0]; 4607 } 4608 4609 Register Q = LHS; 4610 Q = MIB.buildLShr(Ty, Q, PreShift).getReg(0); 4611 4612 // Multiply the numerator (operand 0) by the magic value. 4613 Q = MIB.buildUMulH(Ty, Q, MagicFactor).getReg(0); 4614 4615 if (UseNPQ) { 4616 Register NPQ = MIB.buildSub(Ty, LHS, Q).getReg(0); 4617 4618 // For vectors we might have a mix of non-NPQ/NPQ paths, so use 4619 // G_UMULH to act as a SRL-by-1 for NPQ, else multiply by zero. 4620 if (Ty.isVector()) 4621 NPQ = MIB.buildUMulH(Ty, NPQ, NPQFactor).getReg(0); 4622 else 4623 NPQ = MIB.buildLShr(Ty, NPQ, MIB.buildConstant(ShiftAmtTy, 1)).getReg(0); 4624 4625 Q = MIB.buildAdd(Ty, NPQ, Q).getReg(0); 4626 } 4627 4628 Q = MIB.buildLShr(Ty, Q, PostShift).getReg(0); 4629 auto One = MIB.buildConstant(Ty, 1); 4630 auto IsOne = MIB.buildICmp( 4631 CmpInst::Predicate::ICMP_EQ, 4632 Ty.isScalar() ? LLT::scalar(1) : Ty.changeElementSize(1), RHS, One); 4633 return MIB.buildSelect(Ty, IsOne, LHS, Q); 4634 } 4635 4636 bool CombinerHelper::matchUDivByConst(MachineInstr &MI) { 4637 assert(MI.getOpcode() == TargetOpcode::G_UDIV); 4638 Register Dst = MI.getOperand(0).getReg(); 4639 Register RHS = MI.getOperand(2).getReg(); 4640 LLT DstTy = MRI.getType(Dst); 4641 auto *RHSDef = MRI.getVRegDef(RHS); 4642 if (!isConstantOrConstantVector(*RHSDef, MRI)) 4643 return false; 4644 4645 auto &MF = *MI.getMF(); 4646 AttributeList Attr = MF.getFunction().getAttributes(); 4647 const auto &TLI = getTargetLowering(); 4648 LLVMContext &Ctx = MF.getFunction().getContext(); 4649 auto &DL = MF.getDataLayout(); 4650 if (TLI.isIntDivCheap(getApproximateEVTForLLT(DstTy, DL, Ctx), Attr)) 4651 return false; 4652 4653 // Don't do this for minsize because the instruction sequence is usually 4654 // larger. 4655 if (MF.getFunction().hasMinSize()) 4656 return false; 4657 4658 // Don't do this if the types are not going to be legal. 4659 if (LI) { 4660 if (!isLegalOrBeforeLegalizer({TargetOpcode::G_MUL, {DstTy, DstTy}})) 4661 return false; 4662 if (!isLegalOrBeforeLegalizer({TargetOpcode::G_UMULH, {DstTy}})) 4663 return false; 4664 if (!isLegalOrBeforeLegalizer( 4665 {TargetOpcode::G_ICMP, 4666 {DstTy.isVector() ? DstTy.changeElementSize(1) : LLT::scalar(1), 4667 DstTy}})) 4668 return false; 4669 } 4670 4671 auto CheckEltValue = [&](const Constant *C) { 4672 if (auto *CI = dyn_cast_or_null<ConstantInt>(C)) 4673 return !CI->isZero(); 4674 return false; 4675 }; 4676 return matchUnaryPredicate(MRI, RHS, CheckEltValue); 4677 } 4678 4679 void CombinerHelper::applyUDivByConst(MachineInstr &MI) { 4680 auto *NewMI = buildUDivUsingMul(MI); 4681 replaceSingleDefInstWithReg(MI, NewMI->getOperand(0).getReg()); 4682 } 4683 4684 bool CombinerHelper::matchUMulHToLShr(MachineInstr &MI) { 4685 assert(MI.getOpcode() == TargetOpcode::G_UMULH); 4686 Register RHS = MI.getOperand(2).getReg(); 4687 Register Dst = MI.getOperand(0).getReg(); 4688 LLT Ty = MRI.getType(Dst); 4689 LLT ShiftAmtTy = getTargetLowering().getPreferredShiftAmountTy(Ty); 4690 auto MatchPow2ExceptOne = [&](const Constant *C) { 4691 if (auto *CI = dyn_cast<ConstantInt>(C)) 4692 return CI->getValue().isPowerOf2() && !CI->getValue().isOne(); 4693 return false; 4694 }; 4695 if (!matchUnaryPredicate(MRI, RHS, MatchPow2ExceptOne, false)) 4696 return false; 4697 return isLegalOrBeforeLegalizer({TargetOpcode::G_LSHR, {Ty, ShiftAmtTy}}); 4698 } 4699 4700 void CombinerHelper::applyUMulHToLShr(MachineInstr &MI) { 4701 Register LHS = MI.getOperand(1).getReg(); 4702 Register RHS = MI.getOperand(2).getReg(); 4703 Register Dst = MI.getOperand(0).getReg(); 4704 LLT Ty = MRI.getType(Dst); 4705 LLT ShiftAmtTy = getTargetLowering().getPreferredShiftAmountTy(Ty); 4706 unsigned NumEltBits = Ty.getScalarSizeInBits(); 4707 4708 Builder.setInstrAndDebugLoc(MI); 4709 auto LogBase2 = buildLogBase2(RHS, Builder); 4710 auto ShiftAmt = 4711 Builder.buildSub(Ty, Builder.buildConstant(Ty, NumEltBits), LogBase2); 4712 auto Trunc = Builder.buildZExtOrTrunc(ShiftAmtTy, ShiftAmt); 4713 Builder.buildLShr(Dst, LHS, Trunc); 4714 MI.eraseFromParent(); 4715 } 4716 4717 bool CombinerHelper::matchRedundantNegOperands(MachineInstr &MI, 4718 BuildFnTy &MatchInfo) { 4719 unsigned Opc = MI.getOpcode(); 4720 assert(Opc == TargetOpcode::G_FADD || Opc == TargetOpcode::G_FSUB || 4721 Opc == TargetOpcode::G_FMUL || Opc == TargetOpcode::G_FDIV || 4722 Opc == TargetOpcode::G_FMAD || Opc == TargetOpcode::G_FMA); 4723 4724 Register Dst = MI.getOperand(0).getReg(); 4725 Register X = MI.getOperand(1).getReg(); 4726 Register Y = MI.getOperand(2).getReg(); 4727 LLT Type = MRI.getType(Dst); 4728 4729 // fold (fadd x, fneg(y)) -> (fsub x, y) 4730 // fold (fadd fneg(y), x) -> (fsub x, y) 4731 // G_ADD is commutative so both cases are checked by m_GFAdd 4732 if (mi_match(Dst, MRI, m_GFAdd(m_Reg(X), m_GFNeg(m_Reg(Y)))) && 4733 isLegalOrBeforeLegalizer({TargetOpcode::G_FSUB, {Type}})) { 4734 Opc = TargetOpcode::G_FSUB; 4735 } 4736 /// fold (fsub x, fneg(y)) -> (fadd x, y) 4737 else if (mi_match(Dst, MRI, m_GFSub(m_Reg(X), m_GFNeg(m_Reg(Y)))) && 4738 isLegalOrBeforeLegalizer({TargetOpcode::G_FADD, {Type}})) { 4739 Opc = TargetOpcode::G_FADD; 4740 } 4741 // fold (fmul fneg(x), fneg(y)) -> (fmul x, y) 4742 // fold (fdiv fneg(x), fneg(y)) -> (fdiv x, y) 4743 // fold (fmad fneg(x), fneg(y), z) -> (fmad x, y, z) 4744 // fold (fma fneg(x), fneg(y), z) -> (fma x, y, z) 4745 else if ((Opc == TargetOpcode::G_FMUL || Opc == TargetOpcode::G_FDIV || 4746 Opc == TargetOpcode::G_FMAD || Opc == TargetOpcode::G_FMA) && 4747 mi_match(X, MRI, m_GFNeg(m_Reg(X))) && 4748 mi_match(Y, MRI, m_GFNeg(m_Reg(Y)))) { 4749 // no opcode change 4750 } else 4751 return false; 4752 4753 MatchInfo = [=, &MI](MachineIRBuilder &B) { 4754 Observer.changingInstr(MI); 4755 MI.setDesc(B.getTII().get(Opc)); 4756 MI.getOperand(1).setReg(X); 4757 MI.getOperand(2).setReg(Y); 4758 Observer.changedInstr(MI); 4759 }; 4760 return true; 4761 } 4762 4763 bool CombinerHelper::tryCombine(MachineInstr &MI) { 4764 if (tryCombineCopy(MI)) 4765 return true; 4766 if (tryCombineExtendingLoads(MI)) 4767 return true; 4768 if (tryCombineIndexedLoadStore(MI)) 4769 return true; 4770 return false; 4771 } 4772