1 //===- InstCombineLoadStoreAlloca.cpp -------------------------------------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This file implements the visit functions for load, store and alloca. 10 // 11 //===----------------------------------------------------------------------===// 12 13 #include "InstCombineInternal.h" 14 #include "llvm/ADT/MapVector.h" 15 #include "llvm/ADT/SmallString.h" 16 #include "llvm/ADT/Statistic.h" 17 #include "llvm/Analysis/AliasAnalysis.h" 18 #include "llvm/Analysis/Loads.h" 19 #include "llvm/IR/DataLayout.h" 20 #include "llvm/IR/DebugInfoMetadata.h" 21 #include "llvm/IR/IntrinsicInst.h" 22 #include "llvm/IR/LLVMContext.h" 23 #include "llvm/IR/PatternMatch.h" 24 #include "llvm/Transforms/InstCombine/InstCombiner.h" 25 #include "llvm/Transforms/Utils/Local.h" 26 using namespace llvm; 27 using namespace PatternMatch; 28 29 #define DEBUG_TYPE "instcombine" 30 31 STATISTIC(NumDeadStore, "Number of dead stores eliminated"); 32 STATISTIC(NumGlobalCopies, "Number of allocas copied from constant global"); 33 34 static cl::opt<unsigned> MaxCopiedFromConstantUsers( 35 "instcombine-max-copied-from-constant-users", cl::init(300), 36 cl::desc("Maximum users to visit in copy from constant transform"), 37 cl::Hidden); 38 39 namespace llvm { 40 cl::opt<bool> EnableInferAlignmentPass( 41 "enable-infer-alignment-pass", cl::init(true), cl::Hidden, cl::ZeroOrMore, 42 cl::desc("Enable the InferAlignment pass, disabling alignment inference in " 43 "InstCombine")); 44 } 45 46 /// isOnlyCopiedFromConstantMemory - Recursively walk the uses of a (derived) 47 /// pointer to an alloca. Ignore any reads of the pointer, return false if we 48 /// see any stores or other unknown uses. If we see pointer arithmetic, keep 49 /// track of whether it moves the pointer (with IsOffset) but otherwise traverse 50 /// the uses. If we see a memcpy/memmove that targets an unoffseted pointer to 51 /// the alloca, and if the source pointer is a pointer to a constant memory 52 /// location, we can optimize this. 53 static bool 54 isOnlyCopiedFromConstantMemory(AAResults *AA, AllocaInst *V, 55 MemTransferInst *&TheCopy, 56 SmallVectorImpl<Instruction *> &ToDelete) { 57 // We track lifetime intrinsics as we encounter them. If we decide to go 58 // ahead and replace the value with the memory location, this lets the caller 59 // quickly eliminate the markers. 60 61 using ValueAndIsOffset = PointerIntPair<Value *, 1, bool>; 62 SmallVector<ValueAndIsOffset, 32> Worklist; 63 SmallPtrSet<ValueAndIsOffset, 32> Visited; 64 Worklist.emplace_back(V, false); 65 while (!Worklist.empty()) { 66 ValueAndIsOffset Elem = Worklist.pop_back_val(); 67 if (!Visited.insert(Elem).second) 68 continue; 69 if (Visited.size() > MaxCopiedFromConstantUsers) 70 return false; 71 72 const auto [Value, IsOffset] = Elem; 73 for (auto &U : Value->uses()) { 74 auto *I = cast<Instruction>(U.getUser()); 75 76 if (auto *LI = dyn_cast<LoadInst>(I)) { 77 // Ignore non-volatile loads, they are always ok. 78 if (!LI->isSimple()) return false; 79 continue; 80 } 81 82 if (isa<PHINode, SelectInst>(I)) { 83 // We set IsOffset=true, to forbid the memcpy from occurring after the 84 // phi: If one of the phi operands is not based on the alloca, we 85 // would incorrectly omit a write. 86 Worklist.emplace_back(I, true); 87 continue; 88 } 89 if (isa<BitCastInst, AddrSpaceCastInst>(I)) { 90 // If uses of the bitcast are ok, we are ok. 91 Worklist.emplace_back(I, IsOffset); 92 continue; 93 } 94 if (auto *GEP = dyn_cast<GetElementPtrInst>(I)) { 95 // If the GEP has all zero indices, it doesn't offset the pointer. If it 96 // doesn't, it does. 97 Worklist.emplace_back(I, IsOffset || !GEP->hasAllZeroIndices()); 98 continue; 99 } 100 101 if (auto *Call = dyn_cast<CallBase>(I)) { 102 // If this is the function being called then we treat it like a load and 103 // ignore it. 104 if (Call->isCallee(&U)) 105 continue; 106 107 unsigned DataOpNo = Call->getDataOperandNo(&U); 108 bool IsArgOperand = Call->isArgOperand(&U); 109 110 // Inalloca arguments are clobbered by the call. 111 if (IsArgOperand && Call->isInAllocaArgument(DataOpNo)) 112 return false; 113 114 // If this call site doesn't modify the memory, then we know it is just 115 // a load (but one that potentially returns the value itself), so we can 116 // ignore it if we know that the value isn't captured. 117 bool NoCapture = Call->doesNotCapture(DataOpNo); 118 if ((Call->onlyReadsMemory() && (Call->use_empty() || NoCapture)) || 119 (Call->onlyReadsMemory(DataOpNo) && NoCapture)) 120 continue; 121 122 // If this is being passed as a byval argument, the caller is making a 123 // copy, so it is only a read of the alloca. 124 if (IsArgOperand && Call->isByValArgument(DataOpNo)) 125 continue; 126 } 127 128 // Lifetime intrinsics can be handled by the caller. 129 if (I->isLifetimeStartOrEnd()) { 130 assert(I->use_empty() && "Lifetime markers have no result to use!"); 131 ToDelete.push_back(I); 132 continue; 133 } 134 135 // If this is isn't our memcpy/memmove, reject it as something we can't 136 // handle. 137 MemTransferInst *MI = dyn_cast<MemTransferInst>(I); 138 if (!MI) 139 return false; 140 141 // If the transfer is volatile, reject it. 142 if (MI->isVolatile()) 143 return false; 144 145 // If the transfer is using the alloca as a source of the transfer, then 146 // ignore it since it is a load (unless the transfer is volatile). 147 if (U.getOperandNo() == 1) 148 continue; 149 150 // If we already have seen a copy, reject the second one. 151 if (TheCopy) return false; 152 153 // If the pointer has been offset from the start of the alloca, we can't 154 // safely handle this. 155 if (IsOffset) return false; 156 157 // If the memintrinsic isn't using the alloca as the dest, reject it. 158 if (U.getOperandNo() != 0) return false; 159 160 // If the source of the memcpy/move is not constant, reject it. 161 if (isModSet(AA->getModRefInfoMask(MI->getSource()))) 162 return false; 163 164 // Otherwise, the transform is safe. Remember the copy instruction. 165 TheCopy = MI; 166 } 167 } 168 return true; 169 } 170 171 /// isOnlyCopiedFromConstantMemory - Return true if the specified alloca is only 172 /// modified by a copy from a constant memory location. If we can prove this, we 173 /// can replace any uses of the alloca with uses of the memory location 174 /// directly. 175 static MemTransferInst * 176 isOnlyCopiedFromConstantMemory(AAResults *AA, 177 AllocaInst *AI, 178 SmallVectorImpl<Instruction *> &ToDelete) { 179 MemTransferInst *TheCopy = nullptr; 180 if (isOnlyCopiedFromConstantMemory(AA, AI, TheCopy, ToDelete)) 181 return TheCopy; 182 return nullptr; 183 } 184 185 /// Returns true if V is dereferenceable for size of alloca. 186 static bool isDereferenceableForAllocaSize(const Value *V, const AllocaInst *AI, 187 const DataLayout &DL) { 188 if (AI->isArrayAllocation()) 189 return false; 190 uint64_t AllocaSize = DL.getTypeStoreSize(AI->getAllocatedType()); 191 if (!AllocaSize) 192 return false; 193 return isDereferenceableAndAlignedPointer(V, AI->getAlign(), 194 APInt(64, AllocaSize), DL); 195 } 196 197 static Instruction *simplifyAllocaArraySize(InstCombinerImpl &IC, 198 AllocaInst &AI, DominatorTree &DT) { 199 // Check for array size of 1 (scalar allocation). 200 if (!AI.isArrayAllocation()) { 201 // i32 1 is the canonical array size for scalar allocations. 202 if (AI.getArraySize()->getType()->isIntegerTy(32)) 203 return nullptr; 204 205 // Canonicalize it. 206 return IC.replaceOperand(AI, 0, IC.Builder.getInt32(1)); 207 } 208 209 // Convert: alloca Ty, C - where C is a constant != 1 into: alloca [C x Ty], 1 210 if (const ConstantInt *C = dyn_cast<ConstantInt>(AI.getArraySize())) { 211 if (C->getValue().getActiveBits() <= 64) { 212 Type *NewTy = ArrayType::get(AI.getAllocatedType(), C->getZExtValue()); 213 AllocaInst *New = IC.Builder.CreateAlloca(NewTy, AI.getAddressSpace(), 214 nullptr, AI.getName()); 215 New->setAlignment(AI.getAlign()); 216 New->setUsedWithInAlloca(AI.isUsedWithInAlloca()); 217 218 replaceAllDbgUsesWith(AI, *New, *New, DT); 219 return IC.replaceInstUsesWith(AI, New); 220 } 221 } 222 223 if (isa<UndefValue>(AI.getArraySize())) 224 return IC.replaceInstUsesWith(AI, Constant::getNullValue(AI.getType())); 225 226 // Ensure that the alloca array size argument has type equal to the offset 227 // size of the alloca() pointer, which, in the tyical case, is intptr_t, 228 // so that any casting is exposed early. 229 Type *PtrIdxTy = IC.getDataLayout().getIndexType(AI.getType()); 230 if (AI.getArraySize()->getType() != PtrIdxTy) { 231 Value *V = IC.Builder.CreateIntCast(AI.getArraySize(), PtrIdxTy, false); 232 return IC.replaceOperand(AI, 0, V); 233 } 234 235 return nullptr; 236 } 237 238 namespace { 239 // If I and V are pointers in different address space, it is not allowed to 240 // use replaceAllUsesWith since I and V have different types. A 241 // non-target-specific transformation should not use addrspacecast on V since 242 // the two address space may be disjoint depending on target. 243 // 244 // This class chases down uses of the old pointer until reaching the load 245 // instructions, then replaces the old pointer in the load instructions with 246 // the new pointer. If during the chasing it sees bitcast or GEP, it will 247 // create new bitcast or GEP with the new pointer and use them in the load 248 // instruction. 249 class PointerReplacer { 250 public: 251 PointerReplacer(InstCombinerImpl &IC, Instruction &Root, unsigned SrcAS) 252 : IC(IC), Root(Root), FromAS(SrcAS) {} 253 254 bool collectUsers(); 255 void replacePointer(Value *V); 256 257 private: 258 bool collectUsersRecursive(Instruction &I); 259 void replace(Instruction *I); 260 Value *getReplacement(Value *I); 261 bool isAvailable(Instruction *I) const { 262 return I == &Root || Worklist.contains(I); 263 } 264 265 bool isEqualOrValidAddrSpaceCast(const Instruction *I, 266 unsigned FromAS) const { 267 const auto *ASC = dyn_cast<AddrSpaceCastInst>(I); 268 if (!ASC) 269 return false; 270 unsigned ToAS = ASC->getDestAddressSpace(); 271 return (FromAS == ToAS) || IC.isValidAddrSpaceCast(FromAS, ToAS); 272 } 273 274 SmallPtrSet<Instruction *, 32> ValuesToRevisit; 275 SmallSetVector<Instruction *, 4> Worklist; 276 MapVector<Value *, Value *> WorkMap; 277 InstCombinerImpl &IC; 278 Instruction &Root; 279 unsigned FromAS; 280 }; 281 } // end anonymous namespace 282 283 bool PointerReplacer::collectUsers() { 284 if (!collectUsersRecursive(Root)) 285 return false; 286 287 // Ensure that all outstanding (indirect) users of I 288 // are inserted into the Worklist. Return false 289 // otherwise. 290 for (auto *Inst : ValuesToRevisit) 291 if (!Worklist.contains(Inst)) 292 return false; 293 return true; 294 } 295 296 bool PointerReplacer::collectUsersRecursive(Instruction &I) { 297 for (auto *U : I.users()) { 298 auto *Inst = cast<Instruction>(&*U); 299 if (auto *Load = dyn_cast<LoadInst>(Inst)) { 300 if (Load->isVolatile()) 301 return false; 302 Worklist.insert(Load); 303 } else if (auto *PHI = dyn_cast<PHINode>(Inst)) { 304 // All incoming values must be instructions for replacability 305 if (any_of(PHI->incoming_values(), 306 [](Value *V) { return !isa<Instruction>(V); })) 307 return false; 308 309 // If at least one incoming value of the PHI is not in Worklist, 310 // store the PHI for revisiting and skip this iteration of the 311 // loop. 312 if (any_of(PHI->incoming_values(), [this](Value *V) { 313 return !isAvailable(cast<Instruction>(V)); 314 })) { 315 ValuesToRevisit.insert(Inst); 316 continue; 317 } 318 319 Worklist.insert(PHI); 320 if (!collectUsersRecursive(*PHI)) 321 return false; 322 } else if (auto *SI = dyn_cast<SelectInst>(Inst)) { 323 if (!isa<Instruction>(SI->getTrueValue()) || 324 !isa<Instruction>(SI->getFalseValue())) 325 return false; 326 327 if (!isAvailable(cast<Instruction>(SI->getTrueValue())) || 328 !isAvailable(cast<Instruction>(SI->getFalseValue()))) { 329 ValuesToRevisit.insert(Inst); 330 continue; 331 } 332 Worklist.insert(SI); 333 if (!collectUsersRecursive(*SI)) 334 return false; 335 } else if (isa<GetElementPtrInst, BitCastInst>(Inst)) { 336 Worklist.insert(Inst); 337 if (!collectUsersRecursive(*Inst)) 338 return false; 339 } else if (auto *MI = dyn_cast<MemTransferInst>(Inst)) { 340 if (MI->isVolatile()) 341 return false; 342 Worklist.insert(Inst); 343 } else if (isEqualOrValidAddrSpaceCast(Inst, FromAS)) { 344 Worklist.insert(Inst); 345 } else if (Inst->isLifetimeStartOrEnd()) { 346 continue; 347 } else { 348 LLVM_DEBUG(dbgs() << "Cannot handle pointer user: " << *U << '\n'); 349 return false; 350 } 351 } 352 353 return true; 354 } 355 356 Value *PointerReplacer::getReplacement(Value *V) { return WorkMap.lookup(V); } 357 358 void PointerReplacer::replace(Instruction *I) { 359 if (getReplacement(I)) 360 return; 361 362 if (auto *LT = dyn_cast<LoadInst>(I)) { 363 auto *V = getReplacement(LT->getPointerOperand()); 364 assert(V && "Operand not replaced"); 365 auto *NewI = new LoadInst(LT->getType(), V, "", LT->isVolatile(), 366 LT->getAlign(), LT->getOrdering(), 367 LT->getSyncScopeID()); 368 NewI->takeName(LT); 369 copyMetadataForLoad(*NewI, *LT); 370 371 IC.InsertNewInstWith(NewI, LT->getIterator()); 372 IC.replaceInstUsesWith(*LT, NewI); 373 WorkMap[LT] = NewI; 374 } else if (auto *PHI = dyn_cast<PHINode>(I)) { 375 Type *NewTy = getReplacement(PHI->getIncomingValue(0))->getType(); 376 auto *NewPHI = PHINode::Create(NewTy, PHI->getNumIncomingValues(), 377 PHI->getName(), PHI); 378 for (unsigned int I = 0; I < PHI->getNumIncomingValues(); ++I) 379 NewPHI->addIncoming(getReplacement(PHI->getIncomingValue(I)), 380 PHI->getIncomingBlock(I)); 381 WorkMap[PHI] = NewPHI; 382 } else if (auto *GEP = dyn_cast<GetElementPtrInst>(I)) { 383 auto *V = getReplacement(GEP->getPointerOperand()); 384 assert(V && "Operand not replaced"); 385 SmallVector<Value *, 8> Indices; 386 Indices.append(GEP->idx_begin(), GEP->idx_end()); 387 auto *NewI = 388 GetElementPtrInst::Create(GEP->getSourceElementType(), V, Indices); 389 IC.InsertNewInstWith(NewI, GEP->getIterator()); 390 NewI->takeName(GEP); 391 WorkMap[GEP] = NewI; 392 } else if (auto *BC = dyn_cast<BitCastInst>(I)) { 393 auto *V = getReplacement(BC->getOperand(0)); 394 assert(V && "Operand not replaced"); 395 auto *NewT = PointerType::get(BC->getType()->getContext(), 396 V->getType()->getPointerAddressSpace()); 397 auto *NewI = new BitCastInst(V, NewT); 398 IC.InsertNewInstWith(NewI, BC->getIterator()); 399 NewI->takeName(BC); 400 WorkMap[BC] = NewI; 401 } else if (auto *SI = dyn_cast<SelectInst>(I)) { 402 auto *NewSI = SelectInst::Create( 403 SI->getCondition(), getReplacement(SI->getTrueValue()), 404 getReplacement(SI->getFalseValue()), SI->getName(), nullptr, SI); 405 IC.InsertNewInstWith(NewSI, SI->getIterator()); 406 NewSI->takeName(SI); 407 WorkMap[SI] = NewSI; 408 } else if (auto *MemCpy = dyn_cast<MemTransferInst>(I)) { 409 auto *SrcV = getReplacement(MemCpy->getRawSource()); 410 // The pointer may appear in the destination of a copy, but we don't want to 411 // replace it. 412 if (!SrcV) { 413 assert(getReplacement(MemCpy->getRawDest()) && 414 "destination not in replace list"); 415 return; 416 } 417 418 IC.Builder.SetInsertPoint(MemCpy); 419 auto *NewI = IC.Builder.CreateMemTransferInst( 420 MemCpy->getIntrinsicID(), MemCpy->getRawDest(), MemCpy->getDestAlign(), 421 SrcV, MemCpy->getSourceAlign(), MemCpy->getLength(), 422 MemCpy->isVolatile()); 423 AAMDNodes AAMD = MemCpy->getAAMetadata(); 424 if (AAMD) 425 NewI->setAAMetadata(AAMD); 426 427 IC.eraseInstFromFunction(*MemCpy); 428 WorkMap[MemCpy] = NewI; 429 } else if (auto *ASC = dyn_cast<AddrSpaceCastInst>(I)) { 430 auto *V = getReplacement(ASC->getPointerOperand()); 431 assert(V && "Operand not replaced"); 432 assert(isEqualOrValidAddrSpaceCast( 433 ASC, V->getType()->getPointerAddressSpace()) && 434 "Invalid address space cast!"); 435 auto *NewV = V; 436 if (V->getType()->getPointerAddressSpace() != 437 ASC->getType()->getPointerAddressSpace()) { 438 auto *NewI = new AddrSpaceCastInst(V, ASC->getType(), ""); 439 NewI->takeName(ASC); 440 IC.InsertNewInstWith(NewI, ASC->getIterator()); 441 NewV = NewI; 442 } 443 IC.replaceInstUsesWith(*ASC, NewV); 444 IC.eraseInstFromFunction(*ASC); 445 } else { 446 llvm_unreachable("should never reach here"); 447 } 448 } 449 450 void PointerReplacer::replacePointer(Value *V) { 451 #ifndef NDEBUG 452 auto *PT = cast<PointerType>(Root.getType()); 453 auto *NT = cast<PointerType>(V->getType()); 454 assert(PT != NT && "Invalid usage"); 455 #endif 456 WorkMap[&Root] = V; 457 458 for (Instruction *Workitem : Worklist) 459 replace(Workitem); 460 } 461 462 Instruction *InstCombinerImpl::visitAllocaInst(AllocaInst &AI) { 463 if (auto *I = simplifyAllocaArraySize(*this, AI, DT)) 464 return I; 465 466 if (AI.getAllocatedType()->isSized()) { 467 // Move all alloca's of zero byte objects to the entry block and merge them 468 // together. Note that we only do this for alloca's, because malloc should 469 // allocate and return a unique pointer, even for a zero byte allocation. 470 if (DL.getTypeAllocSize(AI.getAllocatedType()).getKnownMinValue() == 0) { 471 // For a zero sized alloca there is no point in doing an array allocation. 472 // This is helpful if the array size is a complicated expression not used 473 // elsewhere. 474 if (AI.isArrayAllocation()) 475 return replaceOperand(AI, 0, 476 ConstantInt::get(AI.getArraySize()->getType(), 1)); 477 478 // Get the first instruction in the entry block. 479 BasicBlock &EntryBlock = AI.getParent()->getParent()->getEntryBlock(); 480 Instruction *FirstInst = EntryBlock.getFirstNonPHIOrDbg(); 481 if (FirstInst != &AI) { 482 // If the entry block doesn't start with a zero-size alloca then move 483 // this one to the start of the entry block. There is no problem with 484 // dominance as the array size was forced to a constant earlier already. 485 AllocaInst *EntryAI = dyn_cast<AllocaInst>(FirstInst); 486 if (!EntryAI || !EntryAI->getAllocatedType()->isSized() || 487 DL.getTypeAllocSize(EntryAI->getAllocatedType()) 488 .getKnownMinValue() != 0) { 489 AI.moveBefore(FirstInst); 490 return &AI; 491 } 492 493 // Replace this zero-sized alloca with the one at the start of the entry 494 // block after ensuring that the address will be aligned enough for both 495 // types. 496 const Align MaxAlign = std::max(EntryAI->getAlign(), AI.getAlign()); 497 EntryAI->setAlignment(MaxAlign); 498 return replaceInstUsesWith(AI, EntryAI); 499 } 500 } 501 } 502 503 // Check to see if this allocation is only modified by a memcpy/memmove from 504 // a memory location whose alignment is equal to or exceeds that of the 505 // allocation. If this is the case, we can change all users to use the 506 // constant memory location instead. This is commonly produced by the CFE by 507 // constructs like "void foo() { int A[] = {1,2,3,4,5,6,7,8,9...}; }" if 'A' 508 // is only subsequently read. 509 SmallVector<Instruction *, 4> ToDelete; 510 if (MemTransferInst *Copy = isOnlyCopiedFromConstantMemory(AA, &AI, ToDelete)) { 511 Value *TheSrc = Copy->getSource(); 512 Align AllocaAlign = AI.getAlign(); 513 Align SourceAlign = getOrEnforceKnownAlignment( 514 TheSrc, AllocaAlign, DL, &AI, &AC, &DT); 515 if (AllocaAlign <= SourceAlign && 516 isDereferenceableForAllocaSize(TheSrc, &AI, DL) && 517 !isa<Instruction>(TheSrc)) { 518 // FIXME: Can we sink instructions without violating dominance when TheSrc 519 // is an instruction instead of a constant or argument? 520 LLVM_DEBUG(dbgs() << "Found alloca equal to global: " << AI << '\n'); 521 LLVM_DEBUG(dbgs() << " memcpy = " << *Copy << '\n'); 522 unsigned SrcAddrSpace = TheSrc->getType()->getPointerAddressSpace(); 523 if (AI.getAddressSpace() == SrcAddrSpace) { 524 for (Instruction *Delete : ToDelete) 525 eraseInstFromFunction(*Delete); 526 527 Instruction *NewI = replaceInstUsesWith(AI, TheSrc); 528 eraseInstFromFunction(*Copy); 529 ++NumGlobalCopies; 530 return NewI; 531 } 532 533 PointerReplacer PtrReplacer(*this, AI, SrcAddrSpace); 534 if (PtrReplacer.collectUsers()) { 535 for (Instruction *Delete : ToDelete) 536 eraseInstFromFunction(*Delete); 537 538 PtrReplacer.replacePointer(TheSrc); 539 ++NumGlobalCopies; 540 } 541 } 542 } 543 544 // At last, use the generic allocation site handler to aggressively remove 545 // unused allocas. 546 return visitAllocSite(AI); 547 } 548 549 // Are we allowed to form a atomic load or store of this type? 550 static bool isSupportedAtomicType(Type *Ty) { 551 return Ty->isIntOrPtrTy() || Ty->isFloatingPointTy(); 552 } 553 554 /// Helper to combine a load to a new type. 555 /// 556 /// This just does the work of combining a load to a new type. It handles 557 /// metadata, etc., and returns the new instruction. The \c NewTy should be the 558 /// loaded *value* type. This will convert it to a pointer, cast the operand to 559 /// that pointer type, load it, etc. 560 /// 561 /// Note that this will create all of the instructions with whatever insert 562 /// point the \c InstCombinerImpl currently is using. 563 LoadInst *InstCombinerImpl::combineLoadToNewType(LoadInst &LI, Type *NewTy, 564 const Twine &Suffix) { 565 assert((!LI.isAtomic() || isSupportedAtomicType(NewTy)) && 566 "can't fold an atomic load to requested type"); 567 568 LoadInst *NewLoad = 569 Builder.CreateAlignedLoad(NewTy, LI.getPointerOperand(), LI.getAlign(), 570 LI.isVolatile(), LI.getName() + Suffix); 571 NewLoad->setAtomic(LI.getOrdering(), LI.getSyncScopeID()); 572 copyMetadataForLoad(*NewLoad, LI); 573 return NewLoad; 574 } 575 576 /// Combine a store to a new type. 577 /// 578 /// Returns the newly created store instruction. 579 static StoreInst *combineStoreToNewValue(InstCombinerImpl &IC, StoreInst &SI, 580 Value *V) { 581 assert((!SI.isAtomic() || isSupportedAtomicType(V->getType())) && 582 "can't fold an atomic store of requested type"); 583 584 Value *Ptr = SI.getPointerOperand(); 585 SmallVector<std::pair<unsigned, MDNode *>, 8> MD; 586 SI.getAllMetadata(MD); 587 588 StoreInst *NewStore = 589 IC.Builder.CreateAlignedStore(V, Ptr, SI.getAlign(), SI.isVolatile()); 590 NewStore->setAtomic(SI.getOrdering(), SI.getSyncScopeID()); 591 for (const auto &MDPair : MD) { 592 unsigned ID = MDPair.first; 593 MDNode *N = MDPair.second; 594 // Note, essentially every kind of metadata should be preserved here! This 595 // routine is supposed to clone a store instruction changing *only its 596 // type*. The only metadata it makes sense to drop is metadata which is 597 // invalidated when the pointer type changes. This should essentially 598 // never be the case in LLVM, but we explicitly switch over only known 599 // metadata to be conservatively correct. If you are adding metadata to 600 // LLVM which pertains to stores, you almost certainly want to add it 601 // here. 602 switch (ID) { 603 case LLVMContext::MD_dbg: 604 case LLVMContext::MD_DIAssignID: 605 case LLVMContext::MD_tbaa: 606 case LLVMContext::MD_prof: 607 case LLVMContext::MD_fpmath: 608 case LLVMContext::MD_tbaa_struct: 609 case LLVMContext::MD_alias_scope: 610 case LLVMContext::MD_noalias: 611 case LLVMContext::MD_nontemporal: 612 case LLVMContext::MD_mem_parallel_loop_access: 613 case LLVMContext::MD_access_group: 614 // All of these directly apply. 615 NewStore->setMetadata(ID, N); 616 break; 617 case LLVMContext::MD_invariant_load: 618 case LLVMContext::MD_nonnull: 619 case LLVMContext::MD_noundef: 620 case LLVMContext::MD_range: 621 case LLVMContext::MD_align: 622 case LLVMContext::MD_dereferenceable: 623 case LLVMContext::MD_dereferenceable_or_null: 624 // These don't apply for stores. 625 break; 626 } 627 } 628 629 return NewStore; 630 } 631 632 /// Combine loads to match the type of their uses' value after looking 633 /// through intervening bitcasts. 634 /// 635 /// The core idea here is that if the result of a load is used in an operation, 636 /// we should load the type most conducive to that operation. For example, when 637 /// loading an integer and converting that immediately to a pointer, we should 638 /// instead directly load a pointer. 639 /// 640 /// However, this routine must never change the width of a load or the number of 641 /// loads as that would introduce a semantic change. This combine is expected to 642 /// be a semantic no-op which just allows loads to more closely model the types 643 /// of their consuming operations. 644 /// 645 /// Currently, we also refuse to change the precise type used for an atomic load 646 /// or a volatile load. This is debatable, and might be reasonable to change 647 /// later. However, it is risky in case some backend or other part of LLVM is 648 /// relying on the exact type loaded to select appropriate atomic operations. 649 static Instruction *combineLoadToOperationType(InstCombinerImpl &IC, 650 LoadInst &Load) { 651 // FIXME: We could probably with some care handle both volatile and ordered 652 // atomic loads here but it isn't clear that this is important. 653 if (!Load.isUnordered()) 654 return nullptr; 655 656 if (Load.use_empty()) 657 return nullptr; 658 659 // swifterror values can't be bitcasted. 660 if (Load.getPointerOperand()->isSwiftError()) 661 return nullptr; 662 663 // Fold away bit casts of the loaded value by loading the desired type. 664 // Note that we should not do this for pointer<->integer casts, 665 // because that would result in type punning. 666 if (Load.hasOneUse()) { 667 // Don't transform when the type is x86_amx, it makes the pass that lower 668 // x86_amx type happy. 669 Type *LoadTy = Load.getType(); 670 if (auto *BC = dyn_cast<BitCastInst>(Load.user_back())) { 671 assert(!LoadTy->isX86_AMXTy() && "Load from x86_amx* should not happen!"); 672 if (BC->getType()->isX86_AMXTy()) 673 return nullptr; 674 } 675 676 if (auto *CastUser = dyn_cast<CastInst>(Load.user_back())) { 677 Type *DestTy = CastUser->getDestTy(); 678 if (CastUser->isNoopCast(IC.getDataLayout()) && 679 LoadTy->isPtrOrPtrVectorTy() == DestTy->isPtrOrPtrVectorTy() && 680 (!Load.isAtomic() || isSupportedAtomicType(DestTy))) { 681 LoadInst *NewLoad = IC.combineLoadToNewType(Load, DestTy); 682 CastUser->replaceAllUsesWith(NewLoad); 683 IC.eraseInstFromFunction(*CastUser); 684 return &Load; 685 } 686 } 687 } 688 689 // FIXME: We should also canonicalize loads of vectors when their elements are 690 // cast to other types. 691 return nullptr; 692 } 693 694 static Instruction *unpackLoadToAggregate(InstCombinerImpl &IC, LoadInst &LI) { 695 // FIXME: We could probably with some care handle both volatile and atomic 696 // stores here but it isn't clear that this is important. 697 if (!LI.isSimple()) 698 return nullptr; 699 700 Type *T = LI.getType(); 701 if (!T->isAggregateType()) 702 return nullptr; 703 704 StringRef Name = LI.getName(); 705 706 if (auto *ST = dyn_cast<StructType>(T)) { 707 // If the struct only have one element, we unpack. 708 auto NumElements = ST->getNumElements(); 709 if (NumElements == 1) { 710 LoadInst *NewLoad = IC.combineLoadToNewType(LI, ST->getTypeAtIndex(0U), 711 ".unpack"); 712 NewLoad->setAAMetadata(LI.getAAMetadata()); 713 return IC.replaceInstUsesWith(LI, IC.Builder.CreateInsertValue( 714 PoisonValue::get(T), NewLoad, 0, Name)); 715 } 716 717 // We don't want to break loads with padding here as we'd loose 718 // the knowledge that padding exists for the rest of the pipeline. 719 const DataLayout &DL = IC.getDataLayout(); 720 auto *SL = DL.getStructLayout(ST); 721 722 // Don't unpack for structure with scalable vector. 723 if (SL->getSizeInBits().isScalable()) 724 return nullptr; 725 726 if (SL->hasPadding()) 727 return nullptr; 728 729 const auto Align = LI.getAlign(); 730 auto *Addr = LI.getPointerOperand(); 731 auto *IdxType = Type::getInt32Ty(T->getContext()); 732 auto *Zero = ConstantInt::get(IdxType, 0); 733 734 Value *V = PoisonValue::get(T); 735 for (unsigned i = 0; i < NumElements; i++) { 736 Value *Indices[2] = { 737 Zero, 738 ConstantInt::get(IdxType, i), 739 }; 740 auto *Ptr = IC.Builder.CreateInBoundsGEP(ST, Addr, ArrayRef(Indices), 741 Name + ".elt"); 742 auto *L = IC.Builder.CreateAlignedLoad( 743 ST->getElementType(i), Ptr, 744 commonAlignment(Align, SL->getElementOffset(i)), Name + ".unpack"); 745 // Propagate AA metadata. It'll still be valid on the narrowed load. 746 L->setAAMetadata(LI.getAAMetadata()); 747 V = IC.Builder.CreateInsertValue(V, L, i); 748 } 749 750 V->setName(Name); 751 return IC.replaceInstUsesWith(LI, V); 752 } 753 754 if (auto *AT = dyn_cast<ArrayType>(T)) { 755 auto *ET = AT->getElementType(); 756 auto NumElements = AT->getNumElements(); 757 if (NumElements == 1) { 758 LoadInst *NewLoad = IC.combineLoadToNewType(LI, ET, ".unpack"); 759 NewLoad->setAAMetadata(LI.getAAMetadata()); 760 return IC.replaceInstUsesWith(LI, IC.Builder.CreateInsertValue( 761 PoisonValue::get(T), NewLoad, 0, Name)); 762 } 763 764 // Bail out if the array is too large. Ideally we would like to optimize 765 // arrays of arbitrary size but this has a terrible impact on compile time. 766 // The threshold here is chosen arbitrarily, maybe needs a little bit of 767 // tuning. 768 if (NumElements > IC.MaxArraySizeForCombine) 769 return nullptr; 770 771 const DataLayout &DL = IC.getDataLayout(); 772 TypeSize EltSize = DL.getTypeAllocSize(ET); 773 const auto Align = LI.getAlign(); 774 775 auto *Addr = LI.getPointerOperand(); 776 auto *IdxType = Type::getInt64Ty(T->getContext()); 777 auto *Zero = ConstantInt::get(IdxType, 0); 778 779 Value *V = PoisonValue::get(T); 780 TypeSize Offset = TypeSize::get(0, ET->isScalableTy()); 781 for (uint64_t i = 0; i < NumElements; i++) { 782 Value *Indices[2] = { 783 Zero, 784 ConstantInt::get(IdxType, i), 785 }; 786 auto *Ptr = IC.Builder.CreateInBoundsGEP(AT, Addr, ArrayRef(Indices), 787 Name + ".elt"); 788 auto EltAlign = commonAlignment(Align, Offset.getKnownMinValue()); 789 auto *L = IC.Builder.CreateAlignedLoad(AT->getElementType(), Ptr, 790 EltAlign, Name + ".unpack"); 791 L->setAAMetadata(LI.getAAMetadata()); 792 V = IC.Builder.CreateInsertValue(V, L, i); 793 Offset += EltSize; 794 } 795 796 V->setName(Name); 797 return IC.replaceInstUsesWith(LI, V); 798 } 799 800 return nullptr; 801 } 802 803 // If we can determine that all possible objects pointed to by the provided 804 // pointer value are, not only dereferenceable, but also definitively less than 805 // or equal to the provided maximum size, then return true. Otherwise, return 806 // false (constant global values and allocas fall into this category). 807 // 808 // FIXME: This should probably live in ValueTracking (or similar). 809 static bool isObjectSizeLessThanOrEq(Value *V, uint64_t MaxSize, 810 const DataLayout &DL) { 811 SmallPtrSet<Value *, 4> Visited; 812 SmallVector<Value *, 4> Worklist(1, V); 813 814 do { 815 Value *P = Worklist.pop_back_val(); 816 P = P->stripPointerCasts(); 817 818 if (!Visited.insert(P).second) 819 continue; 820 821 if (SelectInst *SI = dyn_cast<SelectInst>(P)) { 822 Worklist.push_back(SI->getTrueValue()); 823 Worklist.push_back(SI->getFalseValue()); 824 continue; 825 } 826 827 if (PHINode *PN = dyn_cast<PHINode>(P)) { 828 append_range(Worklist, PN->incoming_values()); 829 continue; 830 } 831 832 if (GlobalAlias *GA = dyn_cast<GlobalAlias>(P)) { 833 if (GA->isInterposable()) 834 return false; 835 Worklist.push_back(GA->getAliasee()); 836 continue; 837 } 838 839 // If we know how big this object is, and it is less than MaxSize, continue 840 // searching. Otherwise, return false. 841 if (AllocaInst *AI = dyn_cast<AllocaInst>(P)) { 842 if (!AI->getAllocatedType()->isSized()) 843 return false; 844 845 ConstantInt *CS = dyn_cast<ConstantInt>(AI->getArraySize()); 846 if (!CS) 847 return false; 848 849 TypeSize TS = DL.getTypeAllocSize(AI->getAllocatedType()); 850 if (TS.isScalable()) 851 return false; 852 // Make sure that, even if the multiplication below would wrap as an 853 // uint64_t, we still do the right thing. 854 if ((CS->getValue().zext(128) * APInt(128, TS.getFixedValue())) 855 .ugt(MaxSize)) 856 return false; 857 continue; 858 } 859 860 if (GlobalVariable *GV = dyn_cast<GlobalVariable>(P)) { 861 if (!GV->hasDefinitiveInitializer() || !GV->isConstant()) 862 return false; 863 864 uint64_t InitSize = DL.getTypeAllocSize(GV->getValueType()); 865 if (InitSize > MaxSize) 866 return false; 867 continue; 868 } 869 870 return false; 871 } while (!Worklist.empty()); 872 873 return true; 874 } 875 876 // If we're indexing into an object of a known size, and the outer index is 877 // not a constant, but having any value but zero would lead to undefined 878 // behavior, replace it with zero. 879 // 880 // For example, if we have: 881 // @f.a = private unnamed_addr constant [1 x i32] [i32 12], align 4 882 // ... 883 // %arrayidx = getelementptr inbounds [1 x i32]* @f.a, i64 0, i64 %x 884 // ... = load i32* %arrayidx, align 4 885 // Then we know that we can replace %x in the GEP with i64 0. 886 // 887 // FIXME: We could fold any GEP index to zero that would cause UB if it were 888 // not zero. Currently, we only handle the first such index. Also, we could 889 // also search through non-zero constant indices if we kept track of the 890 // offsets those indices implied. 891 static bool canReplaceGEPIdxWithZero(InstCombinerImpl &IC, 892 GetElementPtrInst *GEPI, Instruction *MemI, 893 unsigned &Idx) { 894 if (GEPI->getNumOperands() < 2) 895 return false; 896 897 // Find the first non-zero index of a GEP. If all indices are zero, return 898 // one past the last index. 899 auto FirstNZIdx = [](const GetElementPtrInst *GEPI) { 900 unsigned I = 1; 901 for (unsigned IE = GEPI->getNumOperands(); I != IE; ++I) { 902 Value *V = GEPI->getOperand(I); 903 if (const ConstantInt *CI = dyn_cast<ConstantInt>(V)) 904 if (CI->isZero()) 905 continue; 906 907 break; 908 } 909 910 return I; 911 }; 912 913 // Skip through initial 'zero' indices, and find the corresponding pointer 914 // type. See if the next index is not a constant. 915 Idx = FirstNZIdx(GEPI); 916 if (Idx == GEPI->getNumOperands()) 917 return false; 918 if (isa<Constant>(GEPI->getOperand(Idx))) 919 return false; 920 921 SmallVector<Value *, 4> Ops(GEPI->idx_begin(), GEPI->idx_begin() + Idx); 922 Type *SourceElementType = GEPI->getSourceElementType(); 923 // Size information about scalable vectors is not available, so we cannot 924 // deduce whether indexing at n is undefined behaviour or not. Bail out. 925 if (SourceElementType->isScalableTy()) 926 return false; 927 928 Type *AllocTy = GetElementPtrInst::getIndexedType(SourceElementType, Ops); 929 if (!AllocTy || !AllocTy->isSized()) 930 return false; 931 const DataLayout &DL = IC.getDataLayout(); 932 uint64_t TyAllocSize = DL.getTypeAllocSize(AllocTy).getFixedValue(); 933 934 // If there are more indices after the one we might replace with a zero, make 935 // sure they're all non-negative. If any of them are negative, the overall 936 // address being computed might be before the base address determined by the 937 // first non-zero index. 938 auto IsAllNonNegative = [&]() { 939 for (unsigned i = Idx+1, e = GEPI->getNumOperands(); i != e; ++i) { 940 KnownBits Known = IC.computeKnownBits(GEPI->getOperand(i), 0, MemI); 941 if (Known.isNonNegative()) 942 continue; 943 return false; 944 } 945 946 return true; 947 }; 948 949 // FIXME: If the GEP is not inbounds, and there are extra indices after the 950 // one we'll replace, those could cause the address computation to wrap 951 // (rendering the IsAllNonNegative() check below insufficient). We can do 952 // better, ignoring zero indices (and other indices we can prove small 953 // enough not to wrap). 954 if (Idx+1 != GEPI->getNumOperands() && !GEPI->isInBounds()) 955 return false; 956 957 // Note that isObjectSizeLessThanOrEq will return true only if the pointer is 958 // also known to be dereferenceable. 959 return isObjectSizeLessThanOrEq(GEPI->getOperand(0), TyAllocSize, DL) && 960 IsAllNonNegative(); 961 } 962 963 // If we're indexing into an object with a variable index for the memory 964 // access, but the object has only one element, we can assume that the index 965 // will always be zero. If we replace the GEP, return it. 966 static Instruction *replaceGEPIdxWithZero(InstCombinerImpl &IC, Value *Ptr, 967 Instruction &MemI) { 968 if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(Ptr)) { 969 unsigned Idx; 970 if (canReplaceGEPIdxWithZero(IC, GEPI, &MemI, Idx)) { 971 Instruction *NewGEPI = GEPI->clone(); 972 NewGEPI->setOperand(Idx, 973 ConstantInt::get(GEPI->getOperand(Idx)->getType(), 0)); 974 IC.InsertNewInstBefore(NewGEPI, GEPI->getIterator()); 975 return NewGEPI; 976 } 977 } 978 979 return nullptr; 980 } 981 982 static bool canSimplifyNullStoreOrGEP(StoreInst &SI) { 983 if (NullPointerIsDefined(SI.getFunction(), SI.getPointerAddressSpace())) 984 return false; 985 986 auto *Ptr = SI.getPointerOperand(); 987 if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(Ptr)) 988 Ptr = GEPI->getOperand(0); 989 return (isa<ConstantPointerNull>(Ptr) && 990 !NullPointerIsDefined(SI.getFunction(), SI.getPointerAddressSpace())); 991 } 992 993 static bool canSimplifyNullLoadOrGEP(LoadInst &LI, Value *Op) { 994 if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(Op)) { 995 const Value *GEPI0 = GEPI->getOperand(0); 996 if (isa<ConstantPointerNull>(GEPI0) && 997 !NullPointerIsDefined(LI.getFunction(), GEPI->getPointerAddressSpace())) 998 return true; 999 } 1000 if (isa<UndefValue>(Op) || 1001 (isa<ConstantPointerNull>(Op) && 1002 !NullPointerIsDefined(LI.getFunction(), LI.getPointerAddressSpace()))) 1003 return true; 1004 return false; 1005 } 1006 1007 Instruction *InstCombinerImpl::visitLoadInst(LoadInst &LI) { 1008 Value *Op = LI.getOperand(0); 1009 if (Value *Res = simplifyLoadInst(&LI, Op, SQ.getWithInstruction(&LI))) 1010 return replaceInstUsesWith(LI, Res); 1011 1012 // Try to canonicalize the loaded type. 1013 if (Instruction *Res = combineLoadToOperationType(*this, LI)) 1014 return Res; 1015 1016 if (!EnableInferAlignmentPass) { 1017 // Attempt to improve the alignment. 1018 Align KnownAlign = getOrEnforceKnownAlignment( 1019 Op, DL.getPrefTypeAlign(LI.getType()), DL, &LI, &AC, &DT); 1020 if (KnownAlign > LI.getAlign()) 1021 LI.setAlignment(KnownAlign); 1022 } 1023 1024 // Replace GEP indices if possible. 1025 if (Instruction *NewGEPI = replaceGEPIdxWithZero(*this, Op, LI)) 1026 return replaceOperand(LI, 0, NewGEPI); 1027 1028 if (Instruction *Res = unpackLoadToAggregate(*this, LI)) 1029 return Res; 1030 1031 // Do really simple store-to-load forwarding and load CSE, to catch cases 1032 // where there are several consecutive memory accesses to the same location, 1033 // separated by a few arithmetic operations. 1034 bool IsLoadCSE = false; 1035 if (Value *AvailableVal = FindAvailableLoadedValue(&LI, *AA, &IsLoadCSE)) { 1036 if (IsLoadCSE) 1037 combineMetadataForCSE(cast<LoadInst>(AvailableVal), &LI, false); 1038 1039 return replaceInstUsesWith( 1040 LI, Builder.CreateBitOrPointerCast(AvailableVal, LI.getType(), 1041 LI.getName() + ".cast")); 1042 } 1043 1044 // None of the following transforms are legal for volatile/ordered atomic 1045 // loads. Most of them do apply for unordered atomics. 1046 if (!LI.isUnordered()) return nullptr; 1047 1048 // load(gep null, ...) -> unreachable 1049 // load null/undef -> unreachable 1050 // TODO: Consider a target hook for valid address spaces for this xforms. 1051 if (canSimplifyNullLoadOrGEP(LI, Op)) { 1052 CreateNonTerminatorUnreachable(&LI); 1053 return replaceInstUsesWith(LI, PoisonValue::get(LI.getType())); 1054 } 1055 1056 if (Op->hasOneUse()) { 1057 // Change select and PHI nodes to select values instead of addresses: this 1058 // helps alias analysis out a lot, allows many others simplifications, and 1059 // exposes redundancy in the code. 1060 // 1061 // Note that we cannot do the transformation unless we know that the 1062 // introduced loads cannot trap! Something like this is valid as long as 1063 // the condition is always false: load (select bool %C, int* null, int* %G), 1064 // but it would not be valid if we transformed it to load from null 1065 // unconditionally. 1066 // 1067 if (SelectInst *SI = dyn_cast<SelectInst>(Op)) { 1068 // load (select (Cond, &V1, &V2)) --> select(Cond, load &V1, load &V2). 1069 Align Alignment = LI.getAlign(); 1070 if (isSafeToLoadUnconditionally(SI->getOperand(1), LI.getType(), 1071 Alignment, DL, SI) && 1072 isSafeToLoadUnconditionally(SI->getOperand(2), LI.getType(), 1073 Alignment, DL, SI)) { 1074 LoadInst *V1 = 1075 Builder.CreateLoad(LI.getType(), SI->getOperand(1), 1076 SI->getOperand(1)->getName() + ".val"); 1077 LoadInst *V2 = 1078 Builder.CreateLoad(LI.getType(), SI->getOperand(2), 1079 SI->getOperand(2)->getName() + ".val"); 1080 assert(LI.isUnordered() && "implied by above"); 1081 V1->setAlignment(Alignment); 1082 V1->setAtomic(LI.getOrdering(), LI.getSyncScopeID()); 1083 V2->setAlignment(Alignment); 1084 V2->setAtomic(LI.getOrdering(), LI.getSyncScopeID()); 1085 return SelectInst::Create(SI->getCondition(), V1, V2); 1086 } 1087 1088 // load (select (cond, null, P)) -> load P 1089 if (isa<ConstantPointerNull>(SI->getOperand(1)) && 1090 !NullPointerIsDefined(SI->getFunction(), 1091 LI.getPointerAddressSpace())) 1092 return replaceOperand(LI, 0, SI->getOperand(2)); 1093 1094 // load (select (cond, P, null)) -> load P 1095 if (isa<ConstantPointerNull>(SI->getOperand(2)) && 1096 !NullPointerIsDefined(SI->getFunction(), 1097 LI.getPointerAddressSpace())) 1098 return replaceOperand(LI, 0, SI->getOperand(1)); 1099 } 1100 } 1101 return nullptr; 1102 } 1103 1104 /// Look for extractelement/insertvalue sequence that acts like a bitcast. 1105 /// 1106 /// \returns underlying value that was "cast", or nullptr otherwise. 1107 /// 1108 /// For example, if we have: 1109 /// 1110 /// %E0 = extractelement <2 x double> %U, i32 0 1111 /// %V0 = insertvalue [2 x double] undef, double %E0, 0 1112 /// %E1 = extractelement <2 x double> %U, i32 1 1113 /// %V1 = insertvalue [2 x double] %V0, double %E1, 1 1114 /// 1115 /// and the layout of a <2 x double> is isomorphic to a [2 x double], 1116 /// then %V1 can be safely approximated by a conceptual "bitcast" of %U. 1117 /// Note that %U may contain non-undef values where %V1 has undef. 1118 static Value *likeBitCastFromVector(InstCombinerImpl &IC, Value *V) { 1119 Value *U = nullptr; 1120 while (auto *IV = dyn_cast<InsertValueInst>(V)) { 1121 auto *E = dyn_cast<ExtractElementInst>(IV->getInsertedValueOperand()); 1122 if (!E) 1123 return nullptr; 1124 auto *W = E->getVectorOperand(); 1125 if (!U) 1126 U = W; 1127 else if (U != W) 1128 return nullptr; 1129 auto *CI = dyn_cast<ConstantInt>(E->getIndexOperand()); 1130 if (!CI || IV->getNumIndices() != 1 || CI->getZExtValue() != *IV->idx_begin()) 1131 return nullptr; 1132 V = IV->getAggregateOperand(); 1133 } 1134 if (!match(V, m_Undef()) || !U) 1135 return nullptr; 1136 1137 auto *UT = cast<VectorType>(U->getType()); 1138 auto *VT = V->getType(); 1139 // Check that types UT and VT are bitwise isomorphic. 1140 const auto &DL = IC.getDataLayout(); 1141 if (DL.getTypeStoreSizeInBits(UT) != DL.getTypeStoreSizeInBits(VT)) { 1142 return nullptr; 1143 } 1144 if (auto *AT = dyn_cast<ArrayType>(VT)) { 1145 if (AT->getNumElements() != cast<FixedVectorType>(UT)->getNumElements()) 1146 return nullptr; 1147 } else { 1148 auto *ST = cast<StructType>(VT); 1149 if (ST->getNumElements() != cast<FixedVectorType>(UT)->getNumElements()) 1150 return nullptr; 1151 for (const auto *EltT : ST->elements()) { 1152 if (EltT != UT->getElementType()) 1153 return nullptr; 1154 } 1155 } 1156 return U; 1157 } 1158 1159 /// Combine stores to match the type of value being stored. 1160 /// 1161 /// The core idea here is that the memory does not have any intrinsic type and 1162 /// where we can we should match the type of a store to the type of value being 1163 /// stored. 1164 /// 1165 /// However, this routine must never change the width of a store or the number of 1166 /// stores as that would introduce a semantic change. This combine is expected to 1167 /// be a semantic no-op which just allows stores to more closely model the types 1168 /// of their incoming values. 1169 /// 1170 /// Currently, we also refuse to change the precise type used for an atomic or 1171 /// volatile store. This is debatable, and might be reasonable to change later. 1172 /// However, it is risky in case some backend or other part of LLVM is relying 1173 /// on the exact type stored to select appropriate atomic operations. 1174 /// 1175 /// \returns true if the store was successfully combined away. This indicates 1176 /// the caller must erase the store instruction. We have to let the caller erase 1177 /// the store instruction as otherwise there is no way to signal whether it was 1178 /// combined or not: IC.EraseInstFromFunction returns a null pointer. 1179 static bool combineStoreToValueType(InstCombinerImpl &IC, StoreInst &SI) { 1180 // FIXME: We could probably with some care handle both volatile and ordered 1181 // atomic stores here but it isn't clear that this is important. 1182 if (!SI.isUnordered()) 1183 return false; 1184 1185 // swifterror values can't be bitcasted. 1186 if (SI.getPointerOperand()->isSwiftError()) 1187 return false; 1188 1189 Value *V = SI.getValueOperand(); 1190 1191 // Fold away bit casts of the stored value by storing the original type. 1192 if (auto *BC = dyn_cast<BitCastInst>(V)) { 1193 assert(!BC->getType()->isX86_AMXTy() && 1194 "store to x86_amx* should not happen!"); 1195 V = BC->getOperand(0); 1196 // Don't transform when the type is x86_amx, it makes the pass that lower 1197 // x86_amx type happy. 1198 if (V->getType()->isX86_AMXTy()) 1199 return false; 1200 if (!SI.isAtomic() || isSupportedAtomicType(V->getType())) { 1201 combineStoreToNewValue(IC, SI, V); 1202 return true; 1203 } 1204 } 1205 1206 if (Value *U = likeBitCastFromVector(IC, V)) 1207 if (!SI.isAtomic() || isSupportedAtomicType(U->getType())) { 1208 combineStoreToNewValue(IC, SI, U); 1209 return true; 1210 } 1211 1212 // FIXME: We should also canonicalize stores of vectors when their elements 1213 // are cast to other types. 1214 return false; 1215 } 1216 1217 static bool unpackStoreToAggregate(InstCombinerImpl &IC, StoreInst &SI) { 1218 // FIXME: We could probably with some care handle both volatile and atomic 1219 // stores here but it isn't clear that this is important. 1220 if (!SI.isSimple()) 1221 return false; 1222 1223 Value *V = SI.getValueOperand(); 1224 Type *T = V->getType(); 1225 1226 if (!T->isAggregateType()) 1227 return false; 1228 1229 if (auto *ST = dyn_cast<StructType>(T)) { 1230 // If the struct only have one element, we unpack. 1231 unsigned Count = ST->getNumElements(); 1232 if (Count == 1) { 1233 V = IC.Builder.CreateExtractValue(V, 0); 1234 combineStoreToNewValue(IC, SI, V); 1235 return true; 1236 } 1237 1238 // We don't want to break loads with padding here as we'd loose 1239 // the knowledge that padding exists for the rest of the pipeline. 1240 const DataLayout &DL = IC.getDataLayout(); 1241 auto *SL = DL.getStructLayout(ST); 1242 1243 // Don't unpack for structure with scalable vector. 1244 if (SL->getSizeInBits().isScalable()) 1245 return false; 1246 1247 if (SL->hasPadding()) 1248 return false; 1249 1250 const auto Align = SI.getAlign(); 1251 1252 SmallString<16> EltName = V->getName(); 1253 EltName += ".elt"; 1254 auto *Addr = SI.getPointerOperand(); 1255 SmallString<16> AddrName = Addr->getName(); 1256 AddrName += ".repack"; 1257 1258 auto *IdxType = Type::getInt32Ty(ST->getContext()); 1259 auto *Zero = ConstantInt::get(IdxType, 0); 1260 for (unsigned i = 0; i < Count; i++) { 1261 Value *Indices[2] = { 1262 Zero, 1263 ConstantInt::get(IdxType, i), 1264 }; 1265 auto *Ptr = 1266 IC.Builder.CreateInBoundsGEP(ST, Addr, ArrayRef(Indices), AddrName); 1267 auto *Val = IC.Builder.CreateExtractValue(V, i, EltName); 1268 auto EltAlign = commonAlignment(Align, SL->getElementOffset(i)); 1269 llvm::Instruction *NS = IC.Builder.CreateAlignedStore(Val, Ptr, EltAlign); 1270 NS->setAAMetadata(SI.getAAMetadata()); 1271 } 1272 1273 return true; 1274 } 1275 1276 if (auto *AT = dyn_cast<ArrayType>(T)) { 1277 // If the array only have one element, we unpack. 1278 auto NumElements = AT->getNumElements(); 1279 if (NumElements == 1) { 1280 V = IC.Builder.CreateExtractValue(V, 0); 1281 combineStoreToNewValue(IC, SI, V); 1282 return true; 1283 } 1284 1285 // Bail out if the array is too large. Ideally we would like to optimize 1286 // arrays of arbitrary size but this has a terrible impact on compile time. 1287 // The threshold here is chosen arbitrarily, maybe needs a little bit of 1288 // tuning. 1289 if (NumElements > IC.MaxArraySizeForCombine) 1290 return false; 1291 1292 const DataLayout &DL = IC.getDataLayout(); 1293 TypeSize EltSize = DL.getTypeAllocSize(AT->getElementType()); 1294 const auto Align = SI.getAlign(); 1295 1296 SmallString<16> EltName = V->getName(); 1297 EltName += ".elt"; 1298 auto *Addr = SI.getPointerOperand(); 1299 SmallString<16> AddrName = Addr->getName(); 1300 AddrName += ".repack"; 1301 1302 auto *IdxType = Type::getInt64Ty(T->getContext()); 1303 auto *Zero = ConstantInt::get(IdxType, 0); 1304 1305 TypeSize Offset = TypeSize::get(0, AT->getElementType()->isScalableTy()); 1306 for (uint64_t i = 0; i < NumElements; i++) { 1307 Value *Indices[2] = { 1308 Zero, 1309 ConstantInt::get(IdxType, i), 1310 }; 1311 auto *Ptr = 1312 IC.Builder.CreateInBoundsGEP(AT, Addr, ArrayRef(Indices), AddrName); 1313 auto *Val = IC.Builder.CreateExtractValue(V, i, EltName); 1314 auto EltAlign = commonAlignment(Align, Offset.getKnownMinValue()); 1315 Instruction *NS = IC.Builder.CreateAlignedStore(Val, Ptr, EltAlign); 1316 NS->setAAMetadata(SI.getAAMetadata()); 1317 Offset += EltSize; 1318 } 1319 1320 return true; 1321 } 1322 1323 return false; 1324 } 1325 1326 /// equivalentAddressValues - Test if A and B will obviously have the same 1327 /// value. This includes recognizing that %t0 and %t1 will have the same 1328 /// value in code like this: 1329 /// %t0 = getelementptr \@a, 0, 3 1330 /// store i32 0, i32* %t0 1331 /// %t1 = getelementptr \@a, 0, 3 1332 /// %t2 = load i32* %t1 1333 /// 1334 static bool equivalentAddressValues(Value *A, Value *B) { 1335 // Test if the values are trivially equivalent. 1336 if (A == B) return true; 1337 1338 // Test if the values come form identical arithmetic instructions. 1339 // This uses isIdenticalToWhenDefined instead of isIdenticalTo because 1340 // its only used to compare two uses within the same basic block, which 1341 // means that they'll always either have the same value or one of them 1342 // will have an undefined value. 1343 if (isa<BinaryOperator>(A) || 1344 isa<CastInst>(A) || 1345 isa<PHINode>(A) || 1346 isa<GetElementPtrInst>(A)) 1347 if (Instruction *BI = dyn_cast<Instruction>(B)) 1348 if (cast<Instruction>(A)->isIdenticalToWhenDefined(BI)) 1349 return true; 1350 1351 // Otherwise they may not be equivalent. 1352 return false; 1353 } 1354 1355 Instruction *InstCombinerImpl::visitStoreInst(StoreInst &SI) { 1356 Value *Val = SI.getOperand(0); 1357 Value *Ptr = SI.getOperand(1); 1358 1359 // Try to canonicalize the stored type. 1360 if (combineStoreToValueType(*this, SI)) 1361 return eraseInstFromFunction(SI); 1362 1363 if (!EnableInferAlignmentPass) { 1364 // Attempt to improve the alignment. 1365 const Align KnownAlign = getOrEnforceKnownAlignment( 1366 Ptr, DL.getPrefTypeAlign(Val->getType()), DL, &SI, &AC, &DT); 1367 if (KnownAlign > SI.getAlign()) 1368 SI.setAlignment(KnownAlign); 1369 } 1370 1371 // Try to canonicalize the stored type. 1372 if (unpackStoreToAggregate(*this, SI)) 1373 return eraseInstFromFunction(SI); 1374 1375 // Replace GEP indices if possible. 1376 if (Instruction *NewGEPI = replaceGEPIdxWithZero(*this, Ptr, SI)) 1377 return replaceOperand(SI, 1, NewGEPI); 1378 1379 // Don't hack volatile/ordered stores. 1380 // FIXME: Some bits are legal for ordered atomic stores; needs refactoring. 1381 if (!SI.isUnordered()) return nullptr; 1382 1383 // If the RHS is an alloca with a single use, zapify the store, making the 1384 // alloca dead. 1385 if (Ptr->hasOneUse()) { 1386 if (isa<AllocaInst>(Ptr)) 1387 return eraseInstFromFunction(SI); 1388 if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Ptr)) { 1389 if (isa<AllocaInst>(GEP->getOperand(0))) { 1390 if (GEP->getOperand(0)->hasOneUse()) 1391 return eraseInstFromFunction(SI); 1392 } 1393 } 1394 } 1395 1396 // If we have a store to a location which is known constant, we can conclude 1397 // that the store must be storing the constant value (else the memory 1398 // wouldn't be constant), and this must be a noop. 1399 if (!isModSet(AA->getModRefInfoMask(Ptr))) 1400 return eraseInstFromFunction(SI); 1401 1402 // Do really simple DSE, to catch cases where there are several consecutive 1403 // stores to the same location, separated by a few arithmetic operations. This 1404 // situation often occurs with bitfield accesses. 1405 BasicBlock::iterator BBI(SI); 1406 for (unsigned ScanInsts = 6; BBI != SI.getParent()->begin() && ScanInsts; 1407 --ScanInsts) { 1408 --BBI; 1409 // Don't count debug info directives, lest they affect codegen, 1410 // and we skip pointer-to-pointer bitcasts, which are NOPs. 1411 if (BBI->isDebugOrPseudoInst()) { 1412 ScanInsts++; 1413 continue; 1414 } 1415 1416 if (StoreInst *PrevSI = dyn_cast<StoreInst>(BBI)) { 1417 // Prev store isn't volatile, and stores to the same location? 1418 if (PrevSI->isUnordered() && 1419 equivalentAddressValues(PrevSI->getOperand(1), SI.getOperand(1)) && 1420 PrevSI->getValueOperand()->getType() == 1421 SI.getValueOperand()->getType()) { 1422 ++NumDeadStore; 1423 // Manually add back the original store to the worklist now, so it will 1424 // be processed after the operands of the removed store, as this may 1425 // expose additional DSE opportunities. 1426 Worklist.push(&SI); 1427 eraseInstFromFunction(*PrevSI); 1428 return nullptr; 1429 } 1430 break; 1431 } 1432 1433 // If this is a load, we have to stop. However, if the loaded value is from 1434 // the pointer we're loading and is producing the pointer we're storing, 1435 // then *this* store is dead (X = load P; store X -> P). 1436 if (LoadInst *LI = dyn_cast<LoadInst>(BBI)) { 1437 if (LI == Val && equivalentAddressValues(LI->getOperand(0), Ptr)) { 1438 assert(SI.isUnordered() && "can't eliminate ordering operation"); 1439 return eraseInstFromFunction(SI); 1440 } 1441 1442 // Otherwise, this is a load from some other location. Stores before it 1443 // may not be dead. 1444 break; 1445 } 1446 1447 // Don't skip over loads, throws or things that can modify memory. 1448 if (BBI->mayWriteToMemory() || BBI->mayReadFromMemory() || BBI->mayThrow()) 1449 break; 1450 } 1451 1452 // store X, null -> turns into 'unreachable' in SimplifyCFG 1453 // store X, GEP(null, Y) -> turns into 'unreachable' in SimplifyCFG 1454 if (canSimplifyNullStoreOrGEP(SI)) { 1455 if (!isa<PoisonValue>(Val)) 1456 return replaceOperand(SI, 0, PoisonValue::get(Val->getType())); 1457 return nullptr; // Do not modify these! 1458 } 1459 1460 // This is a non-terminator unreachable marker. Don't remove it. 1461 if (isa<UndefValue>(Ptr)) { 1462 // Remove guaranteed-to-transfer instructions before the marker. 1463 if (removeInstructionsBeforeUnreachable(SI)) 1464 return &SI; 1465 1466 // Remove all instructions after the marker and handle dead blocks this 1467 // implies. 1468 SmallVector<BasicBlock *> Worklist; 1469 handleUnreachableFrom(SI.getNextNode(), Worklist); 1470 handlePotentiallyDeadBlocks(Worklist); 1471 return nullptr; 1472 } 1473 1474 // store undef, Ptr -> noop 1475 // FIXME: This is technically incorrect because it might overwrite a poison 1476 // value. Change to PoisonValue once #52930 is resolved. 1477 if (isa<UndefValue>(Val)) 1478 return eraseInstFromFunction(SI); 1479 1480 return nullptr; 1481 } 1482 1483 /// Try to transform: 1484 /// if () { *P = v1; } else { *P = v2 } 1485 /// or: 1486 /// *P = v1; if () { *P = v2; } 1487 /// into a phi node with a store in the successor. 1488 bool InstCombinerImpl::mergeStoreIntoSuccessor(StoreInst &SI) { 1489 if (!SI.isUnordered()) 1490 return false; // This code has not been audited for volatile/ordered case. 1491 1492 // Check if the successor block has exactly 2 incoming edges. 1493 BasicBlock *StoreBB = SI.getParent(); 1494 BasicBlock *DestBB = StoreBB->getTerminator()->getSuccessor(0); 1495 if (!DestBB->hasNPredecessors(2)) 1496 return false; 1497 1498 // Capture the other block (the block that doesn't contain our store). 1499 pred_iterator PredIter = pred_begin(DestBB); 1500 if (*PredIter == StoreBB) 1501 ++PredIter; 1502 BasicBlock *OtherBB = *PredIter; 1503 1504 // Bail out if all of the relevant blocks aren't distinct. This can happen, 1505 // for example, if SI is in an infinite loop. 1506 if (StoreBB == DestBB || OtherBB == DestBB) 1507 return false; 1508 1509 // Verify that the other block ends in a branch and is not otherwise empty. 1510 BasicBlock::iterator BBI(OtherBB->getTerminator()); 1511 BranchInst *OtherBr = dyn_cast<BranchInst>(BBI); 1512 if (!OtherBr || BBI == OtherBB->begin()) 1513 return false; 1514 1515 auto OtherStoreIsMergeable = [&](StoreInst *OtherStore) -> bool { 1516 if (!OtherStore || 1517 OtherStore->getPointerOperand() != SI.getPointerOperand()) 1518 return false; 1519 1520 auto *SIVTy = SI.getValueOperand()->getType(); 1521 auto *OSVTy = OtherStore->getValueOperand()->getType(); 1522 return CastInst::isBitOrNoopPointerCastable(OSVTy, SIVTy, DL) && 1523 SI.hasSameSpecialState(OtherStore); 1524 }; 1525 1526 // If the other block ends in an unconditional branch, check for the 'if then 1527 // else' case. There is an instruction before the branch. 1528 StoreInst *OtherStore = nullptr; 1529 if (OtherBr->isUnconditional()) { 1530 --BBI; 1531 // Skip over debugging info and pseudo probes. 1532 while (BBI->isDebugOrPseudoInst()) { 1533 if (BBI==OtherBB->begin()) 1534 return false; 1535 --BBI; 1536 } 1537 // If this isn't a store, isn't a store to the same location, or is not the 1538 // right kind of store, bail out. 1539 OtherStore = dyn_cast<StoreInst>(BBI); 1540 if (!OtherStoreIsMergeable(OtherStore)) 1541 return false; 1542 } else { 1543 // Otherwise, the other block ended with a conditional branch. If one of the 1544 // destinations is StoreBB, then we have the if/then case. 1545 if (OtherBr->getSuccessor(0) != StoreBB && 1546 OtherBr->getSuccessor(1) != StoreBB) 1547 return false; 1548 1549 // Okay, we know that OtherBr now goes to Dest and StoreBB, so this is an 1550 // if/then triangle. See if there is a store to the same ptr as SI that 1551 // lives in OtherBB. 1552 for (;; --BBI) { 1553 // Check to see if we find the matching store. 1554 OtherStore = dyn_cast<StoreInst>(BBI); 1555 if (OtherStoreIsMergeable(OtherStore)) 1556 break; 1557 1558 // If we find something that may be using or overwriting the stored 1559 // value, or if we run out of instructions, we can't do the transform. 1560 if (BBI->mayReadFromMemory() || BBI->mayThrow() || 1561 BBI->mayWriteToMemory() || BBI == OtherBB->begin()) 1562 return false; 1563 } 1564 1565 // In order to eliminate the store in OtherBr, we have to make sure nothing 1566 // reads or overwrites the stored value in StoreBB. 1567 for (BasicBlock::iterator I = StoreBB->begin(); &*I != &SI; ++I) { 1568 // FIXME: This should really be AA driven. 1569 if (I->mayReadFromMemory() || I->mayThrow() || I->mayWriteToMemory()) 1570 return false; 1571 } 1572 } 1573 1574 // Insert a PHI node now if we need it. 1575 Value *MergedVal = OtherStore->getValueOperand(); 1576 // The debug locations of the original instructions might differ. Merge them. 1577 DebugLoc MergedLoc = DILocation::getMergedLocation(SI.getDebugLoc(), 1578 OtherStore->getDebugLoc()); 1579 if (MergedVal != SI.getValueOperand()) { 1580 PHINode *PN = 1581 PHINode::Create(SI.getValueOperand()->getType(), 2, "storemerge"); 1582 PN->addIncoming(SI.getValueOperand(), SI.getParent()); 1583 Builder.SetInsertPoint(OtherStore); 1584 PN->addIncoming(Builder.CreateBitOrPointerCast(MergedVal, PN->getType()), 1585 OtherBB); 1586 MergedVal = InsertNewInstBefore(PN, DestBB->begin()); 1587 PN->setDebugLoc(MergedLoc); 1588 } 1589 1590 // Advance to a place where it is safe to insert the new store and insert it. 1591 BBI = DestBB->getFirstInsertionPt(); 1592 StoreInst *NewSI = 1593 new StoreInst(MergedVal, SI.getOperand(1), SI.isVolatile(), SI.getAlign(), 1594 SI.getOrdering(), SI.getSyncScopeID()); 1595 InsertNewInstBefore(NewSI, BBI); 1596 NewSI->setDebugLoc(MergedLoc); 1597 NewSI->mergeDIAssignID({&SI, OtherStore}); 1598 1599 // If the two stores had AA tags, merge them. 1600 AAMDNodes AATags = SI.getAAMetadata(); 1601 if (AATags) 1602 NewSI->setAAMetadata(AATags.merge(OtherStore->getAAMetadata())); 1603 1604 // Nuke the old stores. 1605 eraseInstFromFunction(SI); 1606 eraseInstFromFunction(*OtherStore); 1607 return true; 1608 } 1609