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