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