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