xref: /freebsd/contrib/llvm-project/llvm/lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp (revision a90b9d0159070121c221b966469c3e36d912bf82)
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   BatchAAResults BatchAA(*AA);
1036   if (Value *AvailableVal = FindAvailableLoadedValue(&LI, BatchAA, &IsLoadCSE)) {
1037     if (IsLoadCSE)
1038       combineMetadataForCSE(cast<LoadInst>(AvailableVal), &LI, false);
1039 
1040     return replaceInstUsesWith(
1041         LI, Builder.CreateBitOrPointerCast(AvailableVal, LI.getType(),
1042                                            LI.getName() + ".cast"));
1043   }
1044 
1045   // None of the following transforms are legal for volatile/ordered atomic
1046   // loads.  Most of them do apply for unordered atomics.
1047   if (!LI.isUnordered()) return nullptr;
1048 
1049   // load(gep null, ...) -> unreachable
1050   // load null/undef -> unreachable
1051   // TODO: Consider a target hook for valid address spaces for this xforms.
1052   if (canSimplifyNullLoadOrGEP(LI, Op)) {
1053     CreateNonTerminatorUnreachable(&LI);
1054     return replaceInstUsesWith(LI, PoisonValue::get(LI.getType()));
1055   }
1056 
1057   if (Op->hasOneUse()) {
1058     // Change select and PHI nodes to select values instead of addresses: this
1059     // helps alias analysis out a lot, allows many others simplifications, and
1060     // exposes redundancy in the code.
1061     //
1062     // Note that we cannot do the transformation unless we know that the
1063     // introduced loads cannot trap!  Something like this is valid as long as
1064     // the condition is always false: load (select bool %C, int* null, int* %G),
1065     // but it would not be valid if we transformed it to load from null
1066     // unconditionally.
1067     //
1068     if (SelectInst *SI = dyn_cast<SelectInst>(Op)) {
1069       // load (select (Cond, &V1, &V2))  --> select(Cond, load &V1, load &V2).
1070       Align Alignment = LI.getAlign();
1071       if (isSafeToLoadUnconditionally(SI->getOperand(1), LI.getType(),
1072                                       Alignment, DL, SI) &&
1073           isSafeToLoadUnconditionally(SI->getOperand(2), LI.getType(),
1074                                       Alignment, DL, SI)) {
1075         LoadInst *V1 =
1076             Builder.CreateLoad(LI.getType(), SI->getOperand(1),
1077                                SI->getOperand(1)->getName() + ".val");
1078         LoadInst *V2 =
1079             Builder.CreateLoad(LI.getType(), SI->getOperand(2),
1080                                SI->getOperand(2)->getName() + ".val");
1081         assert(LI.isUnordered() && "implied by above");
1082         V1->setAlignment(Alignment);
1083         V1->setAtomic(LI.getOrdering(), LI.getSyncScopeID());
1084         V2->setAlignment(Alignment);
1085         V2->setAtomic(LI.getOrdering(), LI.getSyncScopeID());
1086         return SelectInst::Create(SI->getCondition(), V1, V2);
1087       }
1088 
1089       // load (select (cond, null, P)) -> load P
1090       if (isa<ConstantPointerNull>(SI->getOperand(1)) &&
1091           !NullPointerIsDefined(SI->getFunction(),
1092                                 LI.getPointerAddressSpace()))
1093         return replaceOperand(LI, 0, SI->getOperand(2));
1094 
1095       // load (select (cond, P, null)) -> load P
1096       if (isa<ConstantPointerNull>(SI->getOperand(2)) &&
1097           !NullPointerIsDefined(SI->getFunction(),
1098                                 LI.getPointerAddressSpace()))
1099         return replaceOperand(LI, 0, SI->getOperand(1));
1100     }
1101   }
1102   return nullptr;
1103 }
1104 
1105 /// Look for extractelement/insertvalue sequence that acts like a bitcast.
1106 ///
1107 /// \returns underlying value that was "cast", or nullptr otherwise.
1108 ///
1109 /// For example, if we have:
1110 ///
1111 ///     %E0 = extractelement <2 x double> %U, i32 0
1112 ///     %V0 = insertvalue [2 x double] undef, double %E0, 0
1113 ///     %E1 = extractelement <2 x double> %U, i32 1
1114 ///     %V1 = insertvalue [2 x double] %V0, double %E1, 1
1115 ///
1116 /// and the layout of a <2 x double> is isomorphic to a [2 x double],
1117 /// then %V1 can be safely approximated by a conceptual "bitcast" of %U.
1118 /// Note that %U may contain non-undef values where %V1 has undef.
1119 static Value *likeBitCastFromVector(InstCombinerImpl &IC, Value *V) {
1120   Value *U = nullptr;
1121   while (auto *IV = dyn_cast<InsertValueInst>(V)) {
1122     auto *E = dyn_cast<ExtractElementInst>(IV->getInsertedValueOperand());
1123     if (!E)
1124       return nullptr;
1125     auto *W = E->getVectorOperand();
1126     if (!U)
1127       U = W;
1128     else if (U != W)
1129       return nullptr;
1130     auto *CI = dyn_cast<ConstantInt>(E->getIndexOperand());
1131     if (!CI || IV->getNumIndices() != 1 || CI->getZExtValue() != *IV->idx_begin())
1132       return nullptr;
1133     V = IV->getAggregateOperand();
1134   }
1135   if (!match(V, m_Undef()) || !U)
1136     return nullptr;
1137 
1138   auto *UT = cast<VectorType>(U->getType());
1139   auto *VT = V->getType();
1140   // Check that types UT and VT are bitwise isomorphic.
1141   const auto &DL = IC.getDataLayout();
1142   if (DL.getTypeStoreSizeInBits(UT) != DL.getTypeStoreSizeInBits(VT)) {
1143     return nullptr;
1144   }
1145   if (auto *AT = dyn_cast<ArrayType>(VT)) {
1146     if (AT->getNumElements() != cast<FixedVectorType>(UT)->getNumElements())
1147       return nullptr;
1148   } else {
1149     auto *ST = cast<StructType>(VT);
1150     if (ST->getNumElements() != cast<FixedVectorType>(UT)->getNumElements())
1151       return nullptr;
1152     for (const auto *EltT : ST->elements()) {
1153       if (EltT != UT->getElementType())
1154         return nullptr;
1155     }
1156   }
1157   return U;
1158 }
1159 
1160 /// Combine stores to match the type of value being stored.
1161 ///
1162 /// The core idea here is that the memory does not have any intrinsic type and
1163 /// where we can we should match the type of a store to the type of value being
1164 /// stored.
1165 ///
1166 /// However, this routine must never change the width of a store or the number of
1167 /// stores as that would introduce a semantic change. This combine is expected to
1168 /// be a semantic no-op which just allows stores to more closely model the types
1169 /// of their incoming values.
1170 ///
1171 /// Currently, we also refuse to change the precise type used for an atomic or
1172 /// volatile store. This is debatable, and might be reasonable to change later.
1173 /// However, it is risky in case some backend or other part of LLVM is relying
1174 /// on the exact type stored to select appropriate atomic operations.
1175 ///
1176 /// \returns true if the store was successfully combined away. This indicates
1177 /// the caller must erase the store instruction. We have to let the caller erase
1178 /// the store instruction as otherwise there is no way to signal whether it was
1179 /// combined or not: IC.EraseInstFromFunction returns a null pointer.
1180 static bool combineStoreToValueType(InstCombinerImpl &IC, StoreInst &SI) {
1181   // FIXME: We could probably with some care handle both volatile and ordered
1182   // atomic stores here but it isn't clear that this is important.
1183   if (!SI.isUnordered())
1184     return false;
1185 
1186   // swifterror values can't be bitcasted.
1187   if (SI.getPointerOperand()->isSwiftError())
1188     return false;
1189 
1190   Value *V = SI.getValueOperand();
1191 
1192   // Fold away bit casts of the stored value by storing the original type.
1193   if (auto *BC = dyn_cast<BitCastInst>(V)) {
1194     assert(!BC->getType()->isX86_AMXTy() &&
1195            "store to x86_amx* should not happen!");
1196     V = BC->getOperand(0);
1197     // Don't transform when the type is x86_amx, it makes the pass that lower
1198     // x86_amx type happy.
1199     if (V->getType()->isX86_AMXTy())
1200       return false;
1201     if (!SI.isAtomic() || isSupportedAtomicType(V->getType())) {
1202       combineStoreToNewValue(IC, SI, V);
1203       return true;
1204     }
1205   }
1206 
1207   if (Value *U = likeBitCastFromVector(IC, V))
1208     if (!SI.isAtomic() || isSupportedAtomicType(U->getType())) {
1209       combineStoreToNewValue(IC, SI, U);
1210       return true;
1211     }
1212 
1213   // FIXME: We should also canonicalize stores of vectors when their elements
1214   // are cast to other types.
1215   return false;
1216 }
1217 
1218 static bool unpackStoreToAggregate(InstCombinerImpl &IC, StoreInst &SI) {
1219   // FIXME: We could probably with some care handle both volatile and atomic
1220   // stores here but it isn't clear that this is important.
1221   if (!SI.isSimple())
1222     return false;
1223 
1224   Value *V = SI.getValueOperand();
1225   Type *T = V->getType();
1226 
1227   if (!T->isAggregateType())
1228     return false;
1229 
1230   if (auto *ST = dyn_cast<StructType>(T)) {
1231     // If the struct only have one element, we unpack.
1232     unsigned Count = ST->getNumElements();
1233     if (Count == 1) {
1234       V = IC.Builder.CreateExtractValue(V, 0);
1235       combineStoreToNewValue(IC, SI, V);
1236       return true;
1237     }
1238 
1239     // We don't want to break loads with padding here as we'd loose
1240     // the knowledge that padding exists for the rest of the pipeline.
1241     const DataLayout &DL = IC.getDataLayout();
1242     auto *SL = DL.getStructLayout(ST);
1243 
1244     // Don't unpack for structure with scalable vector.
1245     if (SL->getSizeInBits().isScalable())
1246       return false;
1247 
1248     if (SL->hasPadding())
1249       return false;
1250 
1251     const auto Align = SI.getAlign();
1252 
1253     SmallString<16> EltName = V->getName();
1254     EltName += ".elt";
1255     auto *Addr = SI.getPointerOperand();
1256     SmallString<16> AddrName = Addr->getName();
1257     AddrName += ".repack";
1258 
1259     auto *IdxType = Type::getInt32Ty(ST->getContext());
1260     auto *Zero = ConstantInt::get(IdxType, 0);
1261     for (unsigned i = 0; i < Count; i++) {
1262       Value *Indices[2] = {
1263         Zero,
1264         ConstantInt::get(IdxType, i),
1265       };
1266       auto *Ptr =
1267           IC.Builder.CreateInBoundsGEP(ST, Addr, ArrayRef(Indices), AddrName);
1268       auto *Val = IC.Builder.CreateExtractValue(V, i, EltName);
1269       auto EltAlign = commonAlignment(Align, SL->getElementOffset(i));
1270       llvm::Instruction *NS = IC.Builder.CreateAlignedStore(Val, Ptr, EltAlign);
1271       NS->setAAMetadata(SI.getAAMetadata());
1272     }
1273 
1274     return true;
1275   }
1276 
1277   if (auto *AT = dyn_cast<ArrayType>(T)) {
1278     // If the array only have one element, we unpack.
1279     auto NumElements = AT->getNumElements();
1280     if (NumElements == 1) {
1281       V = IC.Builder.CreateExtractValue(V, 0);
1282       combineStoreToNewValue(IC, SI, V);
1283       return true;
1284     }
1285 
1286     // Bail out if the array is too large. Ideally we would like to optimize
1287     // arrays of arbitrary size but this has a terrible impact on compile time.
1288     // The threshold here is chosen arbitrarily, maybe needs a little bit of
1289     // tuning.
1290     if (NumElements > IC.MaxArraySizeForCombine)
1291       return false;
1292 
1293     const DataLayout &DL = IC.getDataLayout();
1294     TypeSize EltSize = DL.getTypeAllocSize(AT->getElementType());
1295     const auto Align = SI.getAlign();
1296 
1297     SmallString<16> EltName = V->getName();
1298     EltName += ".elt";
1299     auto *Addr = SI.getPointerOperand();
1300     SmallString<16> AddrName = Addr->getName();
1301     AddrName += ".repack";
1302 
1303     auto *IdxType = Type::getInt64Ty(T->getContext());
1304     auto *Zero = ConstantInt::get(IdxType, 0);
1305 
1306     TypeSize Offset = TypeSize::get(0, AT->getElementType()->isScalableTy());
1307     for (uint64_t i = 0; i < NumElements; i++) {
1308       Value *Indices[2] = {
1309         Zero,
1310         ConstantInt::get(IdxType, i),
1311       };
1312       auto *Ptr =
1313           IC.Builder.CreateInBoundsGEP(AT, Addr, ArrayRef(Indices), AddrName);
1314       auto *Val = IC.Builder.CreateExtractValue(V, i, EltName);
1315       auto EltAlign = commonAlignment(Align, Offset.getKnownMinValue());
1316       Instruction *NS = IC.Builder.CreateAlignedStore(Val, Ptr, EltAlign);
1317       NS->setAAMetadata(SI.getAAMetadata());
1318       Offset += EltSize;
1319     }
1320 
1321     return true;
1322   }
1323 
1324   return false;
1325 }
1326 
1327 /// equivalentAddressValues - Test if A and B will obviously have the same
1328 /// value. This includes recognizing that %t0 and %t1 will have the same
1329 /// value in code like this:
1330 ///   %t0 = getelementptr \@a, 0, 3
1331 ///   store i32 0, i32* %t0
1332 ///   %t1 = getelementptr \@a, 0, 3
1333 ///   %t2 = load i32* %t1
1334 ///
1335 static bool equivalentAddressValues(Value *A, Value *B) {
1336   // Test if the values are trivially equivalent.
1337   if (A == B) return true;
1338 
1339   // Test if the values come form identical arithmetic instructions.
1340   // This uses isIdenticalToWhenDefined instead of isIdenticalTo because
1341   // its only used to compare two uses within the same basic block, which
1342   // means that they'll always either have the same value or one of them
1343   // will have an undefined value.
1344   if (isa<BinaryOperator>(A) ||
1345       isa<CastInst>(A) ||
1346       isa<PHINode>(A) ||
1347       isa<GetElementPtrInst>(A))
1348     if (Instruction *BI = dyn_cast<Instruction>(B))
1349       if (cast<Instruction>(A)->isIdenticalToWhenDefined(BI))
1350         return true;
1351 
1352   // Otherwise they may not be equivalent.
1353   return false;
1354 }
1355 
1356 Instruction *InstCombinerImpl::visitStoreInst(StoreInst &SI) {
1357   Value *Val = SI.getOperand(0);
1358   Value *Ptr = SI.getOperand(1);
1359 
1360   // Try to canonicalize the stored type.
1361   if (combineStoreToValueType(*this, SI))
1362     return eraseInstFromFunction(SI);
1363 
1364   if (!EnableInferAlignmentPass) {
1365     // Attempt to improve the alignment.
1366     const Align KnownAlign = getOrEnforceKnownAlignment(
1367         Ptr, DL.getPrefTypeAlign(Val->getType()), DL, &SI, &AC, &DT);
1368     if (KnownAlign > SI.getAlign())
1369       SI.setAlignment(KnownAlign);
1370   }
1371 
1372   // Try to canonicalize the stored type.
1373   if (unpackStoreToAggregate(*this, SI))
1374     return eraseInstFromFunction(SI);
1375 
1376   // Replace GEP indices if possible.
1377   if (Instruction *NewGEPI = replaceGEPIdxWithZero(*this, Ptr, SI))
1378     return replaceOperand(SI, 1, NewGEPI);
1379 
1380   // Don't hack volatile/ordered stores.
1381   // FIXME: Some bits are legal for ordered atomic stores; needs refactoring.
1382   if (!SI.isUnordered()) return nullptr;
1383 
1384   // If the RHS is an alloca with a single use, zapify the store, making the
1385   // alloca dead.
1386   if (Ptr->hasOneUse()) {
1387     if (isa<AllocaInst>(Ptr))
1388       return eraseInstFromFunction(SI);
1389     if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Ptr)) {
1390       if (isa<AllocaInst>(GEP->getOperand(0))) {
1391         if (GEP->getOperand(0)->hasOneUse())
1392           return eraseInstFromFunction(SI);
1393       }
1394     }
1395   }
1396 
1397   // If we have a store to a location which is known constant, we can conclude
1398   // that the store must be storing the constant value (else the memory
1399   // wouldn't be constant), and this must be a noop.
1400   if (!isModSet(AA->getModRefInfoMask(Ptr)))
1401     return eraseInstFromFunction(SI);
1402 
1403   // Do really simple DSE, to catch cases where there are several consecutive
1404   // stores to the same location, separated by a few arithmetic operations. This
1405   // situation often occurs with bitfield accesses.
1406   BasicBlock::iterator BBI(SI);
1407   for (unsigned ScanInsts = 6; BBI != SI.getParent()->begin() && ScanInsts;
1408        --ScanInsts) {
1409     --BBI;
1410     // Don't count debug info directives, lest they affect codegen,
1411     // and we skip pointer-to-pointer bitcasts, which are NOPs.
1412     if (BBI->isDebugOrPseudoInst()) {
1413       ScanInsts++;
1414       continue;
1415     }
1416 
1417     if (StoreInst *PrevSI = dyn_cast<StoreInst>(BBI)) {
1418       // Prev store isn't volatile, and stores to the same location?
1419       if (PrevSI->isUnordered() &&
1420           equivalentAddressValues(PrevSI->getOperand(1), SI.getOperand(1)) &&
1421           PrevSI->getValueOperand()->getType() ==
1422               SI.getValueOperand()->getType()) {
1423         ++NumDeadStore;
1424         // Manually add back the original store to the worklist now, so it will
1425         // be processed after the operands of the removed store, as this may
1426         // expose additional DSE opportunities.
1427         Worklist.push(&SI);
1428         eraseInstFromFunction(*PrevSI);
1429         return nullptr;
1430       }
1431       break;
1432     }
1433 
1434     // If this is a load, we have to stop.  However, if the loaded value is from
1435     // the pointer we're loading and is producing the pointer we're storing,
1436     // then *this* store is dead (X = load P; store X -> P).
1437     if (LoadInst *LI = dyn_cast<LoadInst>(BBI)) {
1438       if (LI == Val && equivalentAddressValues(LI->getOperand(0), Ptr)) {
1439         assert(SI.isUnordered() && "can't eliminate ordering operation");
1440         return eraseInstFromFunction(SI);
1441       }
1442 
1443       // Otherwise, this is a load from some other location.  Stores before it
1444       // may not be dead.
1445       break;
1446     }
1447 
1448     // Don't skip over loads, throws or things that can modify memory.
1449     if (BBI->mayWriteToMemory() || BBI->mayReadFromMemory() || BBI->mayThrow())
1450       break;
1451   }
1452 
1453   // store X, null    -> turns into 'unreachable' in SimplifyCFG
1454   // store X, GEP(null, Y) -> turns into 'unreachable' in SimplifyCFG
1455   if (canSimplifyNullStoreOrGEP(SI)) {
1456     if (!isa<PoisonValue>(Val))
1457       return replaceOperand(SI, 0, PoisonValue::get(Val->getType()));
1458     return nullptr;  // Do not modify these!
1459   }
1460 
1461   // This is a non-terminator unreachable marker. Don't remove it.
1462   if (isa<UndefValue>(Ptr)) {
1463     // Remove guaranteed-to-transfer instructions before the marker.
1464     if (removeInstructionsBeforeUnreachable(SI))
1465       return &SI;
1466 
1467     // Remove all instructions after the marker and handle dead blocks this
1468     // implies.
1469     SmallVector<BasicBlock *> Worklist;
1470     handleUnreachableFrom(SI.getNextNode(), Worklist);
1471     handlePotentiallyDeadBlocks(Worklist);
1472     return nullptr;
1473   }
1474 
1475   // store undef, Ptr -> noop
1476   // FIXME: This is technically incorrect because it might overwrite a poison
1477   // value. Change to PoisonValue once #52930 is resolved.
1478   if (isa<UndefValue>(Val))
1479     return eraseInstFromFunction(SI);
1480 
1481   return nullptr;
1482 }
1483 
1484 /// Try to transform:
1485 ///   if () { *P = v1; } else { *P = v2 }
1486 /// or:
1487 ///   *P = v1; if () { *P = v2; }
1488 /// into a phi node with a store in the successor.
1489 bool InstCombinerImpl::mergeStoreIntoSuccessor(StoreInst &SI) {
1490   if (!SI.isUnordered())
1491     return false; // This code has not been audited for volatile/ordered case.
1492 
1493   // Check if the successor block has exactly 2 incoming edges.
1494   BasicBlock *StoreBB = SI.getParent();
1495   BasicBlock *DestBB = StoreBB->getTerminator()->getSuccessor(0);
1496   if (!DestBB->hasNPredecessors(2))
1497     return false;
1498 
1499   // Capture the other block (the block that doesn't contain our store).
1500   pred_iterator PredIter = pred_begin(DestBB);
1501   if (*PredIter == StoreBB)
1502     ++PredIter;
1503   BasicBlock *OtherBB = *PredIter;
1504 
1505   // Bail out if all of the relevant blocks aren't distinct. This can happen,
1506   // for example, if SI is in an infinite loop.
1507   if (StoreBB == DestBB || OtherBB == DestBB)
1508     return false;
1509 
1510   // Verify that the other block ends in a branch and is not otherwise empty.
1511   BasicBlock::iterator BBI(OtherBB->getTerminator());
1512   BranchInst *OtherBr = dyn_cast<BranchInst>(BBI);
1513   if (!OtherBr || BBI == OtherBB->begin())
1514     return false;
1515 
1516   auto OtherStoreIsMergeable = [&](StoreInst *OtherStore) -> bool {
1517     if (!OtherStore ||
1518         OtherStore->getPointerOperand() != SI.getPointerOperand())
1519       return false;
1520 
1521     auto *SIVTy = SI.getValueOperand()->getType();
1522     auto *OSVTy = OtherStore->getValueOperand()->getType();
1523     return CastInst::isBitOrNoopPointerCastable(OSVTy, SIVTy, DL) &&
1524            SI.hasSameSpecialState(OtherStore);
1525   };
1526 
1527   // If the other block ends in an unconditional branch, check for the 'if then
1528   // else' case. There is an instruction before the branch.
1529   StoreInst *OtherStore = nullptr;
1530   if (OtherBr->isUnconditional()) {
1531     --BBI;
1532     // Skip over debugging info and pseudo probes.
1533     while (BBI->isDebugOrPseudoInst()) {
1534       if (BBI==OtherBB->begin())
1535         return false;
1536       --BBI;
1537     }
1538     // If this isn't a store, isn't a store to the same location, or is not the
1539     // right kind of store, bail out.
1540     OtherStore = dyn_cast<StoreInst>(BBI);
1541     if (!OtherStoreIsMergeable(OtherStore))
1542       return false;
1543   } else {
1544     // Otherwise, the other block ended with a conditional branch. If one of the
1545     // destinations is StoreBB, then we have the if/then case.
1546     if (OtherBr->getSuccessor(0) != StoreBB &&
1547         OtherBr->getSuccessor(1) != StoreBB)
1548       return false;
1549 
1550     // Okay, we know that OtherBr now goes to Dest and StoreBB, so this is an
1551     // if/then triangle. See if there is a store to the same ptr as SI that
1552     // lives in OtherBB.
1553     for (;; --BBI) {
1554       // Check to see if we find the matching store.
1555       OtherStore = dyn_cast<StoreInst>(BBI);
1556       if (OtherStoreIsMergeable(OtherStore))
1557         break;
1558 
1559       // If we find something that may be using or overwriting the stored
1560       // value, or if we run out of instructions, we can't do the transform.
1561       if (BBI->mayReadFromMemory() || BBI->mayThrow() ||
1562           BBI->mayWriteToMemory() || BBI == OtherBB->begin())
1563         return false;
1564     }
1565 
1566     // In order to eliminate the store in OtherBr, we have to make sure nothing
1567     // reads or overwrites the stored value in StoreBB.
1568     for (BasicBlock::iterator I = StoreBB->begin(); &*I != &SI; ++I) {
1569       // FIXME: This should really be AA driven.
1570       if (I->mayReadFromMemory() || I->mayThrow() || I->mayWriteToMemory())
1571         return false;
1572     }
1573   }
1574 
1575   // Insert a PHI node now if we need it.
1576   Value *MergedVal = OtherStore->getValueOperand();
1577   // The debug locations of the original instructions might differ. Merge them.
1578   DebugLoc MergedLoc = DILocation::getMergedLocation(SI.getDebugLoc(),
1579                                                      OtherStore->getDebugLoc());
1580   if (MergedVal != SI.getValueOperand()) {
1581     PHINode *PN =
1582         PHINode::Create(SI.getValueOperand()->getType(), 2, "storemerge");
1583     PN->addIncoming(SI.getValueOperand(), SI.getParent());
1584     Builder.SetInsertPoint(OtherStore);
1585     PN->addIncoming(Builder.CreateBitOrPointerCast(MergedVal, PN->getType()),
1586                     OtherBB);
1587     MergedVal = InsertNewInstBefore(PN, DestBB->begin());
1588     PN->setDebugLoc(MergedLoc);
1589   }
1590 
1591   // Advance to a place where it is safe to insert the new store and insert it.
1592   BBI = DestBB->getFirstInsertionPt();
1593   StoreInst *NewSI =
1594       new StoreInst(MergedVal, SI.getOperand(1), SI.isVolatile(), SI.getAlign(),
1595                     SI.getOrdering(), SI.getSyncScopeID());
1596   InsertNewInstBefore(NewSI, BBI);
1597   NewSI->setDebugLoc(MergedLoc);
1598   NewSI->mergeDIAssignID({&SI, OtherStore});
1599 
1600   // If the two stores had AA tags, merge them.
1601   AAMDNodes AATags = SI.getAAMetadata();
1602   if (AATags)
1603     NewSI->setAAMetadata(AATags.merge(OtherStore->getAAMetadata()));
1604 
1605   // Nuke the old stores.
1606   eraseInstFromFunction(SI);
1607   eraseInstFromFunction(*OtherStore);
1608   return true;
1609 }
1610