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