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