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