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