LLVM  6.0.0svn
InstCombineLoadStoreAlloca.cpp
Go to the documentation of this file.
1 //===- InstCombineLoadStoreAlloca.cpp -------------------------------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file implements the visit functions for load, store and alloca.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #include "InstCombineInternal.h"
15 #include "llvm/ADT/MapVector.h"
16 #include "llvm/ADT/SmallString.h"
17 #include "llvm/ADT/Statistic.h"
18 #include "llvm/Analysis/Loads.h"
19 #include "llvm/IR/ConstantRange.h"
20 #include "llvm/IR/DataLayout.h"
21 #include "llvm/IR/IntrinsicInst.h"
22 #include "llvm/IR/LLVMContext.h"
23 #include "llvm/IR/MDBuilder.h"
24 #include "llvm/IR/PatternMatch.h"
27 using namespace llvm;
28 using namespace PatternMatch;
29 
30 #define DEBUG_TYPE "instcombine"
31 
32 STATISTIC(NumDeadStore, "Number of dead stores eliminated");
33 STATISTIC(NumGlobalCopies, "Number of allocas copied from constant global");
34 
35 /// pointsToConstantGlobal - Return true if V (possibly indirectly) points to
36 /// some part of a constant global variable. This intentionally only accepts
37 /// constant expressions because we can't rewrite arbitrary instructions.
38 static bool pointsToConstantGlobal(Value *V) {
39  if (GlobalVariable *GV = dyn_cast<GlobalVariable>(V))
40  return GV->isConstant();
41 
42  if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) {
43  if (CE->getOpcode() == Instruction::BitCast ||
44  CE->getOpcode() == Instruction::AddrSpaceCast ||
45  CE->getOpcode() == Instruction::GetElementPtr)
46  return pointsToConstantGlobal(CE->getOperand(0));
47  }
48  return false;
49 }
50 
51 /// isOnlyCopiedFromConstantGlobal - Recursively walk the uses of a (derived)
52 /// pointer to an alloca. Ignore any reads of the pointer, return false if we
53 /// see any stores or other unknown uses. If we see pointer arithmetic, keep
54 /// track of whether it moves the pointer (with IsOffset) but otherwise traverse
55 /// the uses. If we see a memcpy/memmove that targets an unoffseted pointer to
56 /// the alloca, and if the source pointer is a pointer to a constant global, we
57 /// can optimize this.
58 static bool
61  // We track lifetime intrinsics as we encounter them. If we decide to go
62  // ahead and replace the value with the global, this lets the caller quickly
63  // eliminate the markers.
64 
65  SmallVector<std::pair<Value *, bool>, 35> ValuesToInspect;
66  ValuesToInspect.emplace_back(V, false);
67  while (!ValuesToInspect.empty()) {
68  auto ValuePair = ValuesToInspect.pop_back_val();
69  const bool IsOffset = ValuePair.second;
70  for (auto &U : ValuePair.first->uses()) {
71  auto *I = cast<Instruction>(U.getUser());
72 
73  if (auto *LI = dyn_cast<LoadInst>(I)) {
74  // Ignore non-volatile loads, they are always ok.
75  if (!LI->isSimple()) return false;
76  continue;
77  }
78 
79  if (isa<BitCastInst>(I) || isa<AddrSpaceCastInst>(I)) {
80  // If uses of the bitcast are ok, we are ok.
81  ValuesToInspect.emplace_back(I, IsOffset);
82  continue;
83  }
84  if (auto *GEP = dyn_cast<GetElementPtrInst>(I)) {
85  // If the GEP has all zero indices, it doesn't offset the pointer. If it
86  // doesn't, it does.
87  ValuesToInspect.emplace_back(I, IsOffset || !GEP->hasAllZeroIndices());
88  continue;
89  }
90 
91  if (auto CS = CallSite(I)) {
92  // If this is the function being called then we treat it like a load and
93  // ignore it.
94  if (CS.isCallee(&U))
95  continue;
96 
97  unsigned DataOpNo = CS.getDataOperandNo(&U);
98  bool IsArgOperand = CS.isArgOperand(&U);
99 
100  // Inalloca arguments are clobbered by the call.
101  if (IsArgOperand && CS.isInAllocaArgument(DataOpNo))
102  return false;
103 
104  // If this is a readonly/readnone call site, then we know it is just a
105  // load (but one that potentially returns the value itself), so we can
106  // ignore it if we know that the value isn't captured.
107  if (CS.onlyReadsMemory() &&
108  (CS.getInstruction()->use_empty() || CS.doesNotCapture(DataOpNo)))
109  continue;
110 
111  // If this is being passed as a byval argument, the caller is making a
112  // copy, so it is only a read of the alloca.
113  if (IsArgOperand && CS.isByValArgument(DataOpNo))
114  continue;
115  }
116 
117  // Lifetime intrinsics can be handled by the caller.
118  if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
119  if (II->getIntrinsicID() == Intrinsic::lifetime_start ||
120  II->getIntrinsicID() == Intrinsic::lifetime_end) {
121  assert(II->use_empty() && "Lifetime markers have no result to use!");
122  ToDelete.push_back(II);
123  continue;
124  }
125  }
126 
127  // If this is isn't our memcpy/memmove, reject it as something we can't
128  // handle.
130  if (!MI)
131  return false;
132 
133  // If the transfer is using the alloca as a source of the transfer, then
134  // ignore it since it is a load (unless the transfer is volatile).
135  if (U.getOperandNo() == 1) {
136  if (MI->isVolatile()) return false;
137  continue;
138  }
139 
140  // If we already have seen a copy, reject the second one.
141  if (TheCopy) return false;
142 
143  // If the pointer has been offset from the start of the alloca, we can't
144  // safely handle this.
145  if (IsOffset) return false;
146 
147  // If the memintrinsic isn't using the alloca as the dest, reject it.
148  if (U.getOperandNo() != 0) return false;
149 
150  // If the source of the memcpy/move is not a constant global, reject it.
151  if (!pointsToConstantGlobal(MI->getSource()))
152  return false;
153 
154  // Otherwise, the transform is safe. Remember the copy instruction.
155  TheCopy = MI;
156  }
157  }
158  return true;
159 }
160 
161 /// isOnlyCopiedFromConstantGlobal - Return true if the specified alloca is only
162 /// modified by a copy from a constant global. If we can prove this, we can
163 /// replace any uses of the alloca with uses of the global directly.
164 static MemTransferInst *
166  SmallVectorImpl<Instruction *> &ToDelete) {
167  MemTransferInst *TheCopy = nullptr;
168  if (isOnlyCopiedFromConstantGlobal(AI, TheCopy, ToDelete))
169  return TheCopy;
170  return nullptr;
171 }
172 
173 /// Returns true if V is dereferenceable for size of alloca.
174 static bool isDereferenceableForAllocaSize(const Value *V, const AllocaInst *AI,
175  const DataLayout &DL) {
176  if (AI->isArrayAllocation())
177  return false;
178  uint64_t AllocaSize = DL.getTypeStoreSize(AI->getAllocatedType());
179  if (!AllocaSize)
180  return false;
182  APInt(64, AllocaSize), DL);
183 }
184 
186  // Check for array size of 1 (scalar allocation).
187  if (!AI.isArrayAllocation()) {
188  // i32 1 is the canonical array size for scalar allocations.
189  if (AI.getArraySize()->getType()->isIntegerTy(32))
190  return nullptr;
191 
192  // Canonicalize it.
193  Value *V = IC.Builder.getInt32(1);
194  AI.setOperand(0, V);
195  return &AI;
196  }
197 
198  // Convert: alloca Ty, C - where C is a constant != 1 into: alloca [C x Ty], 1
199  if (const ConstantInt *C = dyn_cast<ConstantInt>(AI.getArraySize())) {
200  Type *NewTy = ArrayType::get(AI.getAllocatedType(), C->getZExtValue());
201  AllocaInst *New = IC.Builder.CreateAlloca(NewTy, nullptr, AI.getName());
202  New->setAlignment(AI.getAlignment());
203 
204  // Scan to the end of the allocation instructions, to skip over a block of
205  // allocas if possible...also skip interleaved debug info
206  //
207  BasicBlock::iterator It(New);
208  while (isa<AllocaInst>(*It) || isa<DbgInfoIntrinsic>(*It))
209  ++It;
210 
211  // Now that I is pointing to the first non-allocation-inst in the block,
212  // insert our getelementptr instruction...
213  //
214  Type *IdxTy = IC.getDataLayout().getIntPtrType(AI.getType());
215  Value *NullIdx = Constant::getNullValue(IdxTy);
216  Value *Idx[2] = {NullIdx, NullIdx};
217  Instruction *GEP =
218  GetElementPtrInst::CreateInBounds(New, Idx, New->getName() + ".sub");
219  IC.InsertNewInstBefore(GEP, *It);
220 
221  // Now make everything use the getelementptr instead of the original
222  // allocation.
223  return IC.replaceInstUsesWith(AI, GEP);
224  }
225 
226  if (isa<UndefValue>(AI.getArraySize()))
228 
229  // Ensure that the alloca array size argument has type intptr_t, so that
230  // any casting is exposed early.
231  Type *IntPtrTy = IC.getDataLayout().getIntPtrType(AI.getType());
232  if (AI.getArraySize()->getType() != IntPtrTy) {
233  Value *V = IC.Builder.CreateIntCast(AI.getArraySize(), IntPtrTy, false);
234  AI.setOperand(0, V);
235  return &AI;
236  }
237 
238  return nullptr;
239 }
240 
241 namespace {
242 // If I and V are pointers in different address space, it is not allowed to
243 // use replaceAllUsesWith since I and V have different types. A
244 // non-target-specific transformation should not use addrspacecast on V since
245 // the two address space may be disjoint depending on target.
246 //
247 // This class chases down uses of the old pointer until reaching the load
248 // instructions, then replaces the old pointer in the load instructions with
249 // the new pointer. If during the chasing it sees bitcast or GEP, it will
250 // create new bitcast or GEP with the new pointer and use them in the load
251 // instruction.
252 class PointerReplacer {
253 public:
254  PointerReplacer(InstCombiner &IC) : IC(IC) {}
255  void replacePointer(Instruction &I, Value *V);
256 
257 private:
258  void findLoadAndReplace(Instruction &I);
259  void replace(Instruction *I);
260  Value *getReplacement(Value *I);
261 
264  InstCombiner &IC;
265 };
266 } // end anonymous namespace
267 
268 void PointerReplacer::findLoadAndReplace(Instruction &I) {
269  for (auto U : I.users()) {
270  auto *Inst = dyn_cast<Instruction>(&*U);
271  if (!Inst)
272  return;
273  DEBUG(dbgs() << "Found pointer user: " << *U << '\n');
274  if (isa<LoadInst>(Inst)) {
275  for (auto P : Path)
276  replace(P);
277  replace(Inst);
278  } else if (isa<GetElementPtrInst>(Inst) || isa<BitCastInst>(Inst)) {
279  Path.push_back(Inst);
280  findLoadAndReplace(*Inst);
281  Path.pop_back();
282  } else {
283  return;
284  }
285  }
286 }
287 
288 Value *PointerReplacer::getReplacement(Value *V) {
289  auto Loc = WorkMap.find(V);
290  if (Loc != WorkMap.end())
291  return Loc->second;
292  return nullptr;
293 }
294 
296  if (getReplacement(I))
297  return;
298 
299  if (auto *LT = dyn_cast<LoadInst>(I)) {
300  auto *V = getReplacement(LT->getPointerOperand());
301  assert(V && "Operand not replaced");
302  auto *NewI = new LoadInst(V);
303  NewI->takeName(LT);
304  IC.InsertNewInstWith(NewI, *LT);
305  IC.replaceInstUsesWith(*LT, NewI);
306  WorkMap[LT] = NewI;
307  } else if (auto *GEP = dyn_cast<GetElementPtrInst>(I)) {
308  auto *V = getReplacement(GEP->getPointerOperand());
309  assert(V && "Operand not replaced");
310  SmallVector<Value *, 8> Indices;
311  Indices.append(GEP->idx_begin(), GEP->idx_end());
312  auto *NewI = GetElementPtrInst::Create(
313  V->getType()->getPointerElementType(), V, Indices);
314  IC.InsertNewInstWith(NewI, *GEP);
315  NewI->takeName(GEP);
316  WorkMap[GEP] = NewI;
317  } else if (auto *BC = dyn_cast<BitCastInst>(I)) {
318  auto *V = getReplacement(BC->getOperand(0));
319  assert(V && "Operand not replaced");
320  auto *NewT = PointerType::get(BC->getType()->getPointerElementType(),
322  auto *NewI = new BitCastInst(V, NewT);
323  IC.InsertNewInstWith(NewI, *BC);
324  NewI->takeName(BC);
325  WorkMap[BC] = NewI;
326  } else {
327  llvm_unreachable("should never reach here");
328  }
329 }
330 
331 void PointerReplacer::replacePointer(Instruction &I, Value *V) {
332 #ifndef NDEBUG
333  auto *PT = cast<PointerType>(I.getType());
334  auto *NT = cast<PointerType>(V->getType());
335  assert(PT != NT && PT->getElementType() == NT->getElementType() &&
336  "Invalid usage");
337 #endif
338  WorkMap[&I] = V;
339  findLoadAndReplace(I);
340 }
341 
343  if (auto *I = simplifyAllocaArraySize(*this, AI))
344  return I;
345 
346  if (AI.getAllocatedType()->isSized()) {
347  // If the alignment is 0 (unspecified), assign it the preferred alignment.
348  if (AI.getAlignment() == 0)
349  AI.setAlignment(DL.getPrefTypeAlignment(AI.getAllocatedType()));
350 
351  // Move all alloca's of zero byte objects to the entry block and merge them
352  // together. Note that we only do this for alloca's, because malloc should
353  // allocate and return a unique pointer, even for a zero byte allocation.
354  if (DL.getTypeAllocSize(AI.getAllocatedType()) == 0) {
355  // For a zero sized alloca there is no point in doing an array allocation.
356  // This is helpful if the array size is a complicated expression not used
357  // elsewhere.
358  if (AI.isArrayAllocation()) {
359  AI.setOperand(0, ConstantInt::get(AI.getArraySize()->getType(), 1));
360  return &AI;
361  }
362 
363  // Get the first instruction in the entry block.
364  BasicBlock &EntryBlock = AI.getParent()->getParent()->getEntryBlock();
365  Instruction *FirstInst = EntryBlock.getFirstNonPHIOrDbg();
366  if (FirstInst != &AI) {
367  // If the entry block doesn't start with a zero-size alloca then move
368  // this one to the start of the entry block. There is no problem with
369  // dominance as the array size was forced to a constant earlier already.
370  AllocaInst *EntryAI = dyn_cast<AllocaInst>(FirstInst);
371  if (!EntryAI || !EntryAI->getAllocatedType()->isSized() ||
372  DL.getTypeAllocSize(EntryAI->getAllocatedType()) != 0) {
373  AI.moveBefore(FirstInst);
374  return &AI;
375  }
376 
377  // If the alignment of the entry block alloca is 0 (unspecified),
378  // assign it the preferred alignment.
379  if (EntryAI->getAlignment() == 0)
380  EntryAI->setAlignment(
381  DL.getPrefTypeAlignment(EntryAI->getAllocatedType()));
382  // Replace this zero-sized alloca with the one at the start of the entry
383  // block after ensuring that the address will be aligned enough for both
384  // types.
385  unsigned MaxAlign = std::max(EntryAI->getAlignment(),
386  AI.getAlignment());
387  EntryAI->setAlignment(MaxAlign);
388  if (AI.getType() != EntryAI->getType())
389  return new BitCastInst(EntryAI, AI.getType());
390  return replaceInstUsesWith(AI, EntryAI);
391  }
392  }
393  }
394 
395  if (AI.getAlignment()) {
396  // Check to see if this allocation is only modified by a memcpy/memmove from
397  // a constant global whose alignment is equal to or exceeds that of the
398  // allocation. If this is the case, we can change all users to use
399  // the constant global instead. This is commonly produced by the CFE by
400  // constructs like "void foo() { int A[] = {1,2,3,4,5,6,7,8,9...}; }" if 'A'
401  // is only subsequently read.
403  if (MemTransferInst *Copy = isOnlyCopiedFromConstantGlobal(&AI, ToDelete)) {
404  unsigned SourceAlign = getOrEnforceKnownAlignment(
405  Copy->getSource(), AI.getAlignment(), DL, &AI, &AC, &DT);
406  if (AI.getAlignment() <= SourceAlign &&
407  isDereferenceableForAllocaSize(Copy->getSource(), &AI, DL)) {
408  DEBUG(dbgs() << "Found alloca equal to global: " << AI << '\n');
409  DEBUG(dbgs() << " memcpy = " << *Copy << '\n');
410  for (unsigned i = 0, e = ToDelete.size(); i != e; ++i)
411  eraseInstFromFunction(*ToDelete[i]);
412  Constant *TheSrc = cast<Constant>(Copy->getSource());
413  auto *SrcTy = TheSrc->getType();
414  auto *DestTy = PointerType::get(AI.getType()->getPointerElementType(),
415  SrcTy->getPointerAddressSpace());
416  Constant *Cast =
418  if (AI.getType()->getPointerAddressSpace() ==
419  SrcTy->getPointerAddressSpace()) {
420  Instruction *NewI = replaceInstUsesWith(AI, Cast);
421  eraseInstFromFunction(*Copy);
422  ++NumGlobalCopies;
423  return NewI;
424  } else {
425  PointerReplacer PtrReplacer(*this);
426  PtrReplacer.replacePointer(AI, Cast);
427  ++NumGlobalCopies;
428  }
429  }
430  }
431  }
432 
433  // At last, use the generic allocation site handler to aggressively remove
434  // unused allocas.
435  return visitAllocSite(AI);
436 }
437 
438 // Are we allowed to form a atomic load or store of this type?
439 static bool isSupportedAtomicType(Type *Ty) {
440  return Ty->isIntegerTy() || Ty->isPointerTy() || Ty->isFloatingPointTy();
441 }
442 
443 /// \brief Helper to combine a load to a new type.
444 ///
445 /// This just does the work of combining a load to a new type. It handles
446 /// metadata, etc., and returns the new instruction. The \c NewTy should be the
447 /// loaded *value* type. This will convert it to a pointer, cast the operand to
448 /// that pointer type, load it, etc.
449 ///
450 /// Note that this will create all of the instructions with whatever insert
451 /// point the \c InstCombiner currently is using.
453  const Twine &Suffix = "") {
454  assert((!LI.isAtomic() || isSupportedAtomicType(NewTy)) &&
455  "can't fold an atomic load to requested type");
456 
457  Value *Ptr = LI.getPointerOperand();
458  unsigned AS = LI.getPointerAddressSpace();
460  LI.getAllMetadata(MD);
461 
462  LoadInst *NewLoad = IC.Builder.CreateAlignedLoad(
463  IC.Builder.CreateBitCast(Ptr, NewTy->getPointerTo(AS)),
464  LI.getAlignment(), LI.isVolatile(), LI.getName() + Suffix);
465  NewLoad->setAtomic(LI.getOrdering(), LI.getSyncScopeID());
466  MDBuilder MDB(NewLoad->getContext());
467  for (const auto &MDPair : MD) {
468  unsigned ID = MDPair.first;
469  MDNode *N = MDPair.second;
470  // Note, essentially every kind of metadata should be preserved here! This
471  // routine is supposed to clone a load instruction changing *only its type*.
472  // The only metadata it makes sense to drop is metadata which is invalidated
473  // when the pointer type changes. This should essentially never be the case
474  // in LLVM, but we explicitly switch over only known metadata to be
475  // conservatively correct. If you are adding metadata to LLVM which pertains
476  // to loads, you almost certainly want to add it here.
477  switch (ID) {
478  case LLVMContext::MD_dbg:
488  // All of these directly apply.
489  NewLoad->setMetadata(ID, N);
490  break;
491 
493  copyNonnullMetadata(LI, N, *NewLoad);
494  break;
498  // These only directly apply if the new type is also a pointer.
499  if (NewTy->isPointerTy())
500  NewLoad->setMetadata(ID, N);
501  break;
503  copyRangeMetadata(IC.getDataLayout(), LI, N, *NewLoad);
504  break;
505  }
506  }
507  return NewLoad;
508 }
509 
510 /// \brief Combine a store to a new type.
511 ///
512 /// Returns the newly created store instruction.
514  assert((!SI.isAtomic() || isSupportedAtomicType(V->getType())) &&
515  "can't fold an atomic store of requested type");
516 
517  Value *Ptr = SI.getPointerOperand();
518  unsigned AS = SI.getPointerAddressSpace();
520  SI.getAllMetadata(MD);
521 
522  StoreInst *NewStore = IC.Builder.CreateAlignedStore(
523  V, IC.Builder.CreateBitCast(Ptr, V->getType()->getPointerTo(AS)),
524  SI.getAlignment(), SI.isVolatile());
525  NewStore->setAtomic(SI.getOrdering(), SI.getSyncScopeID());
526  for (const auto &MDPair : MD) {
527  unsigned ID = MDPair.first;
528  MDNode *N = MDPair.second;
529  // Note, essentially every kind of metadata should be preserved here! This
530  // routine is supposed to clone a store instruction changing *only its
531  // type*. The only metadata it makes sense to drop is metadata which is
532  // invalidated when the pointer type changes. This should essentially
533  // never be the case in LLVM, but we explicitly switch over only known
534  // metadata to be conservatively correct. If you are adding metadata to
535  // LLVM which pertains to stores, you almost certainly want to add it
536  // here.
537  switch (ID) {
538  case LLVMContext::MD_dbg:
547  // All of these directly apply.
548  NewStore->setMetadata(ID, N);
549  break;
550 
557  // These don't apply for stores.
558  break;
559  }
560  }
561 
562  return NewStore;
563 }
564 
565 /// Returns true if instruction represent minmax pattern like:
566 /// select ((cmp load V1, load V2), V1, V2).
567 static bool isMinMaxWithLoads(Value *V) {
568  assert(V->getType()->isPointerTy() && "Expected pointer type.");
569  // Ignore possible ty* to ixx* bitcast.
570  V = peekThroughBitcast(V);
571  // Check that select is select ((cmp load V1, load V2), V1, V2) - minmax
572  // pattern.
573  CmpInst::Predicate Pred;
574  Instruction *L1;
575  Instruction *L2;
576  Value *LHS;
577  Value *RHS;
578  if (!match(V, m_Select(m_Cmp(Pred, m_Instruction(L1), m_Instruction(L2)),
579  m_Value(LHS), m_Value(RHS))))
580  return false;
581  return (match(L1, m_Load(m_Specific(LHS))) &&
582  match(L2, m_Load(m_Specific(RHS)))) ||
583  (match(L1, m_Load(m_Specific(RHS))) &&
584  match(L2, m_Load(m_Specific(LHS))));
585 }
586 
587 /// \brief Combine loads to match the type of their uses' value after looking
588 /// through intervening bitcasts.
589 ///
590 /// The core idea here is that if the result of a load is used in an operation,
591 /// we should load the type most conducive to that operation. For example, when
592 /// loading an integer and converting that immediately to a pointer, we should
593 /// instead directly load a pointer.
594 ///
595 /// However, this routine must never change the width of a load or the number of
596 /// loads as that would introduce a semantic change. This combine is expected to
597 /// be a semantic no-op which just allows loads to more closely model the types
598 /// of their consuming operations.
599 ///
600 /// Currently, we also refuse to change the precise type used for an atomic load
601 /// or a volatile load. This is debatable, and might be reasonable to change
602 /// later. However, it is risky in case some backend or other part of LLVM is
603 /// relying on the exact type loaded to select appropriate atomic operations.
605  // FIXME: We could probably with some care handle both volatile and ordered
606  // atomic loads here but it isn't clear that this is important.
607  if (!LI.isUnordered())
608  return nullptr;
609 
610  if (LI.use_empty())
611  return nullptr;
612 
613  // swifterror values can't be bitcasted.
614  if (LI.getPointerOperand()->isSwiftError())
615  return nullptr;
616 
617  Type *Ty = LI.getType();
618  const DataLayout &DL = IC.getDataLayout();
619 
620  // Try to canonicalize loads which are only ever stored to operate over
621  // integers instead of any other type. We only do this when the loaded type
622  // is sized and has a size exactly the same as its store size and the store
623  // size is a legal integer type.
624  // Do not perform canonicalization if minmax pattern is found (to avoid
625  // infinite loop).
626  if (!Ty->isIntegerTy() && Ty->isSized() &&
628  DL.getTypeStoreSizeInBits(Ty) == DL.getTypeSizeInBits(Ty) &&
629  !DL.isNonIntegralPointerType(Ty) &&
631  peekThroughBitcast(LI.getPointerOperand(), /*OneUseOnly=*/true))) {
632  if (all_of(LI.users(), [&LI](User *U) {
633  auto *SI = dyn_cast<StoreInst>(U);
634  return SI && SI->getPointerOperand() != &LI &&
635  !SI->getPointerOperand()->isSwiftError();
636  })) {
637  LoadInst *NewLoad = combineLoadToNewType(
638  IC, LI,
640  // Replace all the stores with stores of the newly loaded value.
641  for (auto UI = LI.user_begin(), UE = LI.user_end(); UI != UE;) {
642  auto *SI = cast<StoreInst>(*UI++);
644  combineStoreToNewValue(IC, *SI, NewLoad);
646  }
647  assert(LI.use_empty() && "Failed to remove all users of the load!");
648  // Return the old load so the combiner can delete it safely.
649  return &LI;
650  }
651  }
652 
653  // Fold away bit casts of the loaded value by loading the desired type.
654  // We can do this for BitCastInsts as well as casts from and to pointer types,
655  // as long as those are noops (i.e., the source or dest type have the same
656  // bitwidth as the target's pointers).
657  if (LI.hasOneUse())
658  if (auto* CI = dyn_cast<CastInst>(LI.user_back()))
659  if (CI->isNoopCast(DL))
660  if (!LI.isAtomic() || isSupportedAtomicType(CI->getDestTy())) {
661  LoadInst *NewLoad = combineLoadToNewType(IC, LI, CI->getDestTy());
662  CI->replaceAllUsesWith(NewLoad);
663  IC.eraseInstFromFunction(*CI);
664  return &LI;
665  }
666 
667  // FIXME: We should also canonicalize loads of vectors when their elements are
668  // cast to other types.
669  return nullptr;
670 }
671 
673  // FIXME: We could probably with some care handle both volatile and atomic
674  // stores here but it isn't clear that this is important.
675  if (!LI.isSimple())
676  return nullptr;
677 
678  Type *T = LI.getType();
679  if (!T->isAggregateType())
680  return nullptr;
681 
682  StringRef Name = LI.getName();
683  assert(LI.getAlignment() && "Alignment must be set at this point");
684 
685  if (auto *ST = dyn_cast<StructType>(T)) {
686  // If the struct only have one element, we unpack.
687  auto NumElements = ST->getNumElements();
688  if (NumElements == 1) {
689  LoadInst *NewLoad = combineLoadToNewType(IC, LI, ST->getTypeAtIndex(0U),
690  ".unpack");
691  AAMDNodes AAMD;
692  LI.getAAMetadata(AAMD);
693  NewLoad->setAAMetadata(AAMD);
695  UndefValue::get(T), NewLoad, 0, Name));
696  }
697 
698  // We don't want to break loads with padding here as we'd loose
699  // the knowledge that padding exists for the rest of the pipeline.
700  const DataLayout &DL = IC.getDataLayout();
701  auto *SL = DL.getStructLayout(ST);
702  if (SL->hasPadding())
703  return nullptr;
704 
705  auto Align = LI.getAlignment();
706  if (!Align)
708 
709  auto *Addr = LI.getPointerOperand();
710  auto *IdxType = Type::getInt32Ty(T->getContext());
711  auto *Zero = ConstantInt::get(IdxType, 0);
712 
713  Value *V = UndefValue::get(T);
714  for (unsigned i = 0; i < NumElements; i++) {
715  Value *Indices[2] = {
716  Zero,
717  ConstantInt::get(IdxType, i),
718  };
719  auto *Ptr = IC.Builder.CreateInBoundsGEP(ST, Addr, makeArrayRef(Indices),
720  Name + ".elt");
721  auto EltAlign = MinAlign(Align, SL->getElementOffset(i));
722  auto *L = IC.Builder.CreateAlignedLoad(Ptr, EltAlign, Name + ".unpack");
723  // Propagate AA metadata. It'll still be valid on the narrowed load.
724  AAMDNodes AAMD;
725  LI.getAAMetadata(AAMD);
726  L->setAAMetadata(AAMD);
727  V = IC.Builder.CreateInsertValue(V, L, i);
728  }
729 
730  V->setName(Name);
731  return IC.replaceInstUsesWith(LI, V);
732  }
733 
734  if (auto *AT = dyn_cast<ArrayType>(T)) {
735  auto *ET = AT->getElementType();
736  auto NumElements = AT->getNumElements();
737  if (NumElements == 1) {
738  LoadInst *NewLoad = combineLoadToNewType(IC, LI, ET, ".unpack");
739  AAMDNodes AAMD;
740  LI.getAAMetadata(AAMD);
741  NewLoad->setAAMetadata(AAMD);
743  UndefValue::get(T), NewLoad, 0, Name));
744  }
745 
746  // Bail out if the array is too large. Ideally we would like to optimize
747  // arrays of arbitrary size but this has a terrible impact on compile time.
748  // The threshold here is chosen arbitrarily, maybe needs a little bit of
749  // tuning.
750  if (NumElements > IC.MaxArraySizeForCombine)
751  return nullptr;
752 
753  const DataLayout &DL = IC.getDataLayout();
754  auto EltSize = DL.getTypeAllocSize(ET);
755  auto Align = LI.getAlignment();
756  if (!Align)
757  Align = DL.getABITypeAlignment(T);
758 
759  auto *Addr = LI.getPointerOperand();
760  auto *IdxType = Type::getInt64Ty(T->getContext());
761  auto *Zero = ConstantInt::get(IdxType, 0);
762 
763  Value *V = UndefValue::get(T);
764  uint64_t Offset = 0;
765  for (uint64_t i = 0; i < NumElements; i++) {
766  Value *Indices[2] = {
767  Zero,
768  ConstantInt::get(IdxType, i),
769  };
770  auto *Ptr = IC.Builder.CreateInBoundsGEP(AT, Addr, makeArrayRef(Indices),
771  Name + ".elt");
772  auto *L = IC.Builder.CreateAlignedLoad(Ptr, MinAlign(Align, Offset),
773  Name + ".unpack");
774  AAMDNodes AAMD;
775  LI.getAAMetadata(AAMD);
776  L->setAAMetadata(AAMD);
777  V = IC.Builder.CreateInsertValue(V, L, i);
778  Offset += EltSize;
779  }
780 
781  V->setName(Name);
782  return IC.replaceInstUsesWith(LI, V);
783  }
784 
785  return nullptr;
786 }
787 
788 // If we can determine that all possible objects pointed to by the provided
789 // pointer value are, not only dereferenceable, but also definitively less than
790 // or equal to the provided maximum size, then return true. Otherwise, return
791 // false (constant global values and allocas fall into this category).
792 //
793 // FIXME: This should probably live in ValueTracking (or similar).
794 static bool isObjectSizeLessThanOrEq(Value *V, uint64_t MaxSize,
795  const DataLayout &DL) {
796  SmallPtrSet<Value *, 4> Visited;
797  SmallVector<Value *, 4> Worklist(1, V);
798 
799  do {
800  Value *P = Worklist.pop_back_val();
801  P = P->stripPointerCasts();
802 
803  if (!Visited.insert(P).second)
804  continue;
805 
806  if (SelectInst *SI = dyn_cast<SelectInst>(P)) {
807  Worklist.push_back(SI->getTrueValue());
808  Worklist.push_back(SI->getFalseValue());
809  continue;
810  }
811 
812  if (PHINode *PN = dyn_cast<PHINode>(P)) {
813  for (Value *IncValue : PN->incoming_values())
814  Worklist.push_back(IncValue);
815  continue;
816  }
817 
818  if (GlobalAlias *GA = dyn_cast<GlobalAlias>(P)) {
819  if (GA->isInterposable())
820  return false;
821  Worklist.push_back(GA->getAliasee());
822  continue;
823  }
824 
825  // If we know how big this object is, and it is less than MaxSize, continue
826  // searching. Otherwise, return false.
827  if (AllocaInst *AI = dyn_cast<AllocaInst>(P)) {
828  if (!AI->getAllocatedType()->isSized())
829  return false;
830 
831  ConstantInt *CS = dyn_cast<ConstantInt>(AI->getArraySize());
832  if (!CS)
833  return false;
834 
835  uint64_t TypeSize = DL.getTypeAllocSize(AI->getAllocatedType());
836  // Make sure that, even if the multiplication below would wrap as an
837  // uint64_t, we still do the right thing.
838  if ((CS->getValue().zextOrSelf(128)*APInt(128, TypeSize)).ugt(MaxSize))
839  return false;
840  continue;
841  }
842 
843  if (GlobalVariable *GV = dyn_cast<GlobalVariable>(P)) {
844  if (!GV->hasDefinitiveInitializer() || !GV->isConstant())
845  return false;
846 
847  uint64_t InitSize = DL.getTypeAllocSize(GV->getValueType());
848  if (InitSize > MaxSize)
849  return false;
850  continue;
851  }
852 
853  return false;
854  } while (!Worklist.empty());
855 
856  return true;
857 }
858 
859 // If we're indexing into an object of a known size, and the outer index is
860 // not a constant, but having any value but zero would lead to undefined
861 // behavior, replace it with zero.
862 //
863 // For example, if we have:
864 // @f.a = private unnamed_addr constant [1 x i32] [i32 12], align 4
865 // ...
866 // %arrayidx = getelementptr inbounds [1 x i32]* @f.a, i64 0, i64 %x
867 // ... = load i32* %arrayidx, align 4
868 // Then we know that we can replace %x in the GEP with i64 0.
869 //
870 // FIXME: We could fold any GEP index to zero that would cause UB if it were
871 // not zero. Currently, we only handle the first such index. Also, we could
872 // also search through non-zero constant indices if we kept track of the
873 // offsets those indices implied.
875  Instruction *MemI, unsigned &Idx) {
876  if (GEPI->getNumOperands() < 2)
877  return false;
878 
879  // Find the first non-zero index of a GEP. If all indices are zero, return
880  // one past the last index.
881  auto FirstNZIdx = [](const GetElementPtrInst *GEPI) {
882  unsigned I = 1;
883  for (unsigned IE = GEPI->getNumOperands(); I != IE; ++I) {
884  Value *V = GEPI->getOperand(I);
885  if (const ConstantInt *CI = dyn_cast<ConstantInt>(V))
886  if (CI->isZero())
887  continue;
888 
889  break;
890  }
891 
892  return I;
893  };
894 
895  // Skip through initial 'zero' indices, and find the corresponding pointer
896  // type. See if the next index is not a constant.
897  Idx = FirstNZIdx(GEPI);
898  if (Idx == GEPI->getNumOperands())
899  return false;
900  if (isa<Constant>(GEPI->getOperand(Idx)))
901  return false;
902 
903  SmallVector<Value *, 4> Ops(GEPI->idx_begin(), GEPI->idx_begin() + Idx);
904  Type *AllocTy =
906  if (!AllocTy || !AllocTy->isSized())
907  return false;
908  const DataLayout &DL = IC.getDataLayout();
909  uint64_t TyAllocSize = DL.getTypeAllocSize(AllocTy);
910 
911  // If there are more indices after the one we might replace with a zero, make
912  // sure they're all non-negative. If any of them are negative, the overall
913  // address being computed might be before the base address determined by the
914  // first non-zero index.
915  auto IsAllNonNegative = [&]() {
916  for (unsigned i = Idx+1, e = GEPI->getNumOperands(); i != e; ++i) {
917  KnownBits Known = IC.computeKnownBits(GEPI->getOperand(i), 0, MemI);
918  if (Known.isNonNegative())
919  continue;
920  return false;
921  }
922 
923  return true;
924  };
925 
926  // FIXME: If the GEP is not inbounds, and there are extra indices after the
927  // one we'll replace, those could cause the address computation to wrap
928  // (rendering the IsAllNonNegative() check below insufficient). We can do
929  // better, ignoring zero indices (and other indices we can prove small
930  // enough not to wrap).
931  if (Idx+1 != GEPI->getNumOperands() && !GEPI->isInBounds())
932  return false;
933 
934  // Note that isObjectSizeLessThanOrEq will return true only if the pointer is
935  // also known to be dereferenceable.
936  return isObjectSizeLessThanOrEq(GEPI->getOperand(0), TyAllocSize, DL) &&
937  IsAllNonNegative();
938 }
939 
940 // If we're indexing into an object with a variable index for the memory
941 // access, but the object has only one element, we can assume that the index
942 // will always be zero. If we replace the GEP, return it.
943 template <typename T>
945  T &MemI) {
946  if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(Ptr)) {
947  unsigned Idx;
948  if (canReplaceGEPIdxWithZero(IC, GEPI, &MemI, Idx)) {
949  Instruction *NewGEPI = GEPI->clone();
950  NewGEPI->setOperand(Idx,
951  ConstantInt::get(GEPI->getOperand(Idx)->getType(), 0));
952  NewGEPI->insertBefore(GEPI);
953  MemI.setOperand(MemI.getPointerOperandIndex(), NewGEPI);
954  return NewGEPI;
955  }
956  }
957 
958  return nullptr;
959 }
960 
962  if (SI.getPointerAddressSpace() != 0)
963  return false;
964 
965  auto *Ptr = SI.getPointerOperand();
966  if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(Ptr))
967  Ptr = GEPI->getOperand(0);
968  return isa<ConstantPointerNull>(Ptr);
969 }
970 
972  if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(Op)) {
973  const Value *GEPI0 = GEPI->getOperand(0);
974  if (isa<ConstantPointerNull>(GEPI0) && GEPI->getPointerAddressSpace() == 0)
975  return true;
976  }
977  if (isa<UndefValue>(Op) ||
978  (isa<ConstantPointerNull>(Op) && LI.getPointerAddressSpace() == 0))
979  return true;
980  return false;
981 }
982 
984  Value *Op = LI.getOperand(0);
985 
986  // Try to canonicalize the loaded type.
987  if (Instruction *Res = combineLoadToOperationType(*this, LI))
988  return Res;
989 
990  // Attempt to improve the alignment.
991  unsigned KnownAlign = getOrEnforceKnownAlignment(
992  Op, DL.getPrefTypeAlignment(LI.getType()), DL, &LI, &AC, &DT);
993  unsigned LoadAlign = LI.getAlignment();
994  unsigned EffectiveLoadAlign =
995  LoadAlign != 0 ? LoadAlign : DL.getABITypeAlignment(LI.getType());
996 
997  if (KnownAlign > EffectiveLoadAlign)
998  LI.setAlignment(KnownAlign);
999  else if (LoadAlign == 0)
1000  LI.setAlignment(EffectiveLoadAlign);
1001 
1002  // Replace GEP indices if possible.
1003  if (Instruction *NewGEPI = replaceGEPIdxWithZero(*this, Op, LI)) {
1004  Worklist.Add(NewGEPI);
1005  return &LI;
1006  }
1007 
1008  if (Instruction *Res = unpackLoadToAggregate(*this, LI))
1009  return Res;
1010 
1011  // Do really simple store-to-load forwarding and load CSE, to catch cases
1012  // where there are several consecutive memory accesses to the same location,
1013  // separated by a few arithmetic operations.
1014  BasicBlock::iterator BBI(LI);
1015  bool IsLoadCSE = false;
1016  if (Value *AvailableVal = FindAvailableLoadedValue(
1017  &LI, LI.getParent(), BBI, DefMaxInstsToScan, AA, &IsLoadCSE)) {
1018  if (IsLoadCSE)
1019  combineMetadataForCSE(cast<LoadInst>(AvailableVal), &LI);
1020 
1021  return replaceInstUsesWith(
1022  LI, Builder.CreateBitOrPointerCast(AvailableVal, LI.getType(),
1023  LI.getName() + ".cast"));
1024  }
1025 
1026  // None of the following transforms are legal for volatile/ordered atomic
1027  // loads. Most of them do apply for unordered atomics.
1028  if (!LI.isUnordered()) return nullptr;
1029 
1030  // load(gep null, ...) -> unreachable
1031  // load null/undef -> unreachable
1032  // TODO: Consider a target hook for valid address spaces for this xforms.
1033  if (canSimplifyNullLoadOrGEP(LI, Op)) {
1034  // Insert a new store to null instruction before the load to indicate
1035  // that this code is not reachable. We do this instead of inserting
1036  // an unreachable instruction directly because we cannot modify the
1037  // CFG.
1039  Constant::getNullValue(Op->getType()), &LI);
1040  SI->setDebugLoc(LI.getDebugLoc());
1041  return replaceInstUsesWith(LI, UndefValue::get(LI.getType()));
1042  }
1043 
1044  if (Op->hasOneUse()) {
1045  // Change select and PHI nodes to select values instead of addresses: this
1046  // helps alias analysis out a lot, allows many others simplifications, and
1047  // exposes redundancy in the code.
1048  //
1049  // Note that we cannot do the transformation unless we know that the
1050  // introduced loads cannot trap! Something like this is valid as long as
1051  // the condition is always false: load (select bool %C, int* null, int* %G),
1052  // but it would not be valid if we transformed it to load from null
1053  // unconditionally.
1054  //
1055  if (SelectInst *SI = dyn_cast<SelectInst>(Op)) {
1056  // load (select (Cond, &V1, &V2)) --> select(Cond, load &V1, load &V2).
1057  unsigned Align = LI.getAlignment();
1058  if (isSafeToLoadUnconditionally(SI->getOperand(1), Align, DL, SI) &&
1059  isSafeToLoadUnconditionally(SI->getOperand(2), Align, DL, SI)) {
1060  LoadInst *V1 = Builder.CreateLoad(SI->getOperand(1),
1061  SI->getOperand(1)->getName()+".val");
1062  LoadInst *V2 = Builder.CreateLoad(SI->getOperand(2),
1063  SI->getOperand(2)->getName()+".val");
1064  assert(LI.isUnordered() && "implied by above");
1065  V1->setAlignment(Align);
1066  V1->setAtomic(LI.getOrdering(), LI.getSyncScopeID());
1067  V2->setAlignment(Align);
1068  V2->setAtomic(LI.getOrdering(), LI.getSyncScopeID());
1069  return SelectInst::Create(SI->getCondition(), V1, V2);
1070  }
1071 
1072  // load (select (cond, null, P)) -> load P
1073  if (isa<ConstantPointerNull>(SI->getOperand(1)) &&
1074  LI.getPointerAddressSpace() == 0) {
1075  LI.setOperand(0, SI->getOperand(2));
1076  return &LI;
1077  }
1078 
1079  // load (select (cond, P, null)) -> load P
1080  if (isa<ConstantPointerNull>(SI->getOperand(2)) &&
1081  LI.getPointerAddressSpace() == 0) {
1082  LI.setOperand(0, SI->getOperand(1));
1083  return &LI;
1084  }
1085  }
1086  }
1087  return nullptr;
1088 }
1089 
1090 /// \brief Look for extractelement/insertvalue sequence that acts like a bitcast.
1091 ///
1092 /// \returns underlying value that was "cast", or nullptr otherwise.
1093 ///
1094 /// For example, if we have:
1095 ///
1096 /// %E0 = extractelement <2 x double> %U, i32 0
1097 /// %V0 = insertvalue [2 x double] undef, double %E0, 0
1098 /// %E1 = extractelement <2 x double> %U, i32 1
1099 /// %V1 = insertvalue [2 x double] %V0, double %E1, 1
1100 ///
1101 /// and the layout of a <2 x double> is isomorphic to a [2 x double],
1102 /// then %V1 can be safely approximated by a conceptual "bitcast" of %U.
1103 /// Note that %U may contain non-undef values where %V1 has undef.
1105  Value *U = nullptr;
1106  while (auto *IV = dyn_cast<InsertValueInst>(V)) {
1107  auto *E = dyn_cast<ExtractElementInst>(IV->getInsertedValueOperand());
1108  if (!E)
1109  return nullptr;
1110  auto *W = E->getVectorOperand();
1111  if (!U)
1112  U = W;
1113  else if (U != W)
1114  return nullptr;
1115  auto *CI = dyn_cast<ConstantInt>(E->getIndexOperand());
1116  if (!CI || IV->getNumIndices() != 1 || CI->getZExtValue() != *IV->idx_begin())
1117  return nullptr;
1118  V = IV->getAggregateOperand();
1119  }
1120  if (!isa<UndefValue>(V) ||!U)
1121  return nullptr;
1122 
1123  auto *UT = cast<VectorType>(U->getType());
1124  auto *VT = V->getType();
1125  // Check that types UT and VT are bitwise isomorphic.
1126  const auto &DL = IC.getDataLayout();
1127  if (DL.getTypeStoreSizeInBits(UT) != DL.getTypeStoreSizeInBits(VT)) {
1128  return nullptr;
1129  }
1130  if (auto *AT = dyn_cast<ArrayType>(VT)) {
1131  if (AT->getNumElements() != UT->getNumElements())
1132  return nullptr;
1133  } else {
1134  auto *ST = cast<StructType>(VT);
1135  if (ST->getNumElements() != UT->getNumElements())
1136  return nullptr;
1137  for (const auto *EltT : ST->elements()) {
1138  if (EltT != UT->getElementType())
1139  return nullptr;
1140  }
1141  }
1142  return U;
1143 }
1144 
1145 /// \brief Combine stores to match the type of value being stored.
1146 ///
1147 /// The core idea here is that the memory does not have any intrinsic type and
1148 /// where we can we should match the type of a store to the type of value being
1149 /// stored.
1150 ///
1151 /// However, this routine must never change the width of a store or the number of
1152 /// stores as that would introduce a semantic change. This combine is expected to
1153 /// be a semantic no-op which just allows stores to more closely model the types
1154 /// of their incoming values.
1155 ///
1156 /// Currently, we also refuse to change the precise type used for an atomic or
1157 /// volatile store. This is debatable, and might be reasonable to change later.
1158 /// However, it is risky in case some backend or other part of LLVM is relying
1159 /// on the exact type stored to select appropriate atomic operations.
1160 ///
1161 /// \returns true if the store was successfully combined away. This indicates
1162 /// the caller must erase the store instruction. We have to let the caller erase
1163 /// the store instruction as otherwise there is no way to signal whether it was
1164 /// combined or not: IC.EraseInstFromFunction returns a null pointer.
1166  // FIXME: We could probably with some care handle both volatile and ordered
1167  // atomic stores here but it isn't clear that this is important.
1168  if (!SI.isUnordered())
1169  return false;
1170 
1171  // swifterror values can't be bitcasted.
1172  if (SI.getPointerOperand()->isSwiftError())
1173  return false;
1174 
1175  Value *V = SI.getValueOperand();
1176 
1177  // Fold away bit casts of the stored value by storing the original type.
1178  if (auto *BC = dyn_cast<BitCastInst>(V)) {
1179  V = BC->getOperand(0);
1180  if (!SI.isAtomic() || isSupportedAtomicType(V->getType())) {
1181  combineStoreToNewValue(IC, SI, V);
1182  return true;
1183  }
1184  }
1185 
1186  if (Value *U = likeBitCastFromVector(IC, V))
1187  if (!SI.isAtomic() || isSupportedAtomicType(U->getType())) {
1188  combineStoreToNewValue(IC, SI, U);
1189  return true;
1190  }
1191 
1192  // FIXME: We should also canonicalize stores of vectors when their elements
1193  // are cast to other types.
1194  return false;
1195 }
1196 
1198  // FIXME: We could probably with some care handle both volatile and atomic
1199  // stores here but it isn't clear that this is important.
1200  if (!SI.isSimple())
1201  return false;
1202 
1203  Value *V = SI.getValueOperand();
1204  Type *T = V->getType();
1205 
1206  if (!T->isAggregateType())
1207  return false;
1208 
1209  if (auto *ST = dyn_cast<StructType>(T)) {
1210  // If the struct only have one element, we unpack.
1211  unsigned Count = ST->getNumElements();
1212  if (Count == 1) {
1213  V = IC.Builder.CreateExtractValue(V, 0);
1214  combineStoreToNewValue(IC, SI, V);
1215  return true;
1216  }
1217 
1218  // We don't want to break loads with padding here as we'd loose
1219  // the knowledge that padding exists for the rest of the pipeline.
1220  const DataLayout &DL = IC.getDataLayout();
1221  auto *SL = DL.getStructLayout(ST);
1222  if (SL->hasPadding())
1223  return false;
1224 
1225  auto Align = SI.getAlignment();
1226  if (!Align)
1228 
1229  SmallString<16> EltName = V->getName();
1230  EltName += ".elt";
1231  auto *Addr = SI.getPointerOperand();
1232  SmallString<16> AddrName = Addr->getName();
1233  AddrName += ".repack";
1234 
1235  auto *IdxType = Type::getInt32Ty(ST->getContext());
1236  auto *Zero = ConstantInt::get(IdxType, 0);
1237  for (unsigned i = 0; i < Count; i++) {
1238  Value *Indices[2] = {
1239  Zero,
1240  ConstantInt::get(IdxType, i),
1241  };
1242  auto *Ptr = IC.Builder.CreateInBoundsGEP(ST, Addr, makeArrayRef(Indices),
1243  AddrName);
1244  auto *Val = IC.Builder.CreateExtractValue(V, i, EltName);
1245  auto EltAlign = MinAlign(Align, SL->getElementOffset(i));
1246  llvm::Instruction *NS = IC.Builder.CreateAlignedStore(Val, Ptr, EltAlign);
1247  AAMDNodes AAMD;
1248  SI.getAAMetadata(AAMD);
1249  NS->setAAMetadata(AAMD);
1250  }
1251 
1252  return true;
1253  }
1254 
1255  if (auto *AT = dyn_cast<ArrayType>(T)) {
1256  // If the array only have one element, we unpack.
1257  auto NumElements = AT->getNumElements();
1258  if (NumElements == 1) {
1259  V = IC.Builder.CreateExtractValue(V, 0);
1260  combineStoreToNewValue(IC, SI, V);
1261  return true;
1262  }
1263 
1264  // Bail out if the array is too large. Ideally we would like to optimize
1265  // arrays of arbitrary size but this has a terrible impact on compile time.
1266  // The threshold here is chosen arbitrarily, maybe needs a little bit of
1267  // tuning.
1268  if (NumElements > IC.MaxArraySizeForCombine)
1269  return false;
1270 
1271  const DataLayout &DL = IC.getDataLayout();
1272  auto EltSize = DL.getTypeAllocSize(AT->getElementType());
1273  auto Align = SI.getAlignment();
1274  if (!Align)
1275  Align = DL.getABITypeAlignment(T);
1276 
1277  SmallString<16> EltName = V->getName();
1278  EltName += ".elt";
1279  auto *Addr = SI.getPointerOperand();
1280  SmallString<16> AddrName = Addr->getName();
1281  AddrName += ".repack";
1282 
1283  auto *IdxType = Type::getInt64Ty(T->getContext());
1284  auto *Zero = ConstantInt::get(IdxType, 0);
1285 
1286  uint64_t Offset = 0;
1287  for (uint64_t i = 0; i < NumElements; i++) {
1288  Value *Indices[2] = {
1289  Zero,
1290  ConstantInt::get(IdxType, i),
1291  };
1292  auto *Ptr = IC.Builder.CreateInBoundsGEP(AT, Addr, makeArrayRef(Indices),
1293  AddrName);
1294  auto *Val = IC.Builder.CreateExtractValue(V, i, EltName);
1295  auto EltAlign = MinAlign(Align, Offset);
1296  Instruction *NS = IC.Builder.CreateAlignedStore(Val, Ptr, EltAlign);
1297  AAMDNodes AAMD;
1298  SI.getAAMetadata(AAMD);
1299  NS->setAAMetadata(AAMD);
1300  Offset += EltSize;
1301  }
1302 
1303  return true;
1304  }
1305 
1306  return false;
1307 }
1308 
1309 /// equivalentAddressValues - Test if A and B will obviously have the same
1310 /// value. This includes recognizing that %t0 and %t1 will have the same
1311 /// value in code like this:
1312 /// %t0 = getelementptr \@a, 0, 3
1313 /// store i32 0, i32* %t0
1314 /// %t1 = getelementptr \@a, 0, 3
1315 /// %t2 = load i32* %t1
1316 ///
1318  // Test if the values are trivially equivalent.
1319  if (A == B) return true;
1320 
1321  // Test if the values come form identical arithmetic instructions.
1322  // This uses isIdenticalToWhenDefined instead of isIdenticalTo because
1323  // its only used to compare two uses within the same basic block, which
1324  // means that they'll always either have the same value or one of them
1325  // will have an undefined value.
1326  if (isa<BinaryOperator>(A) ||
1327  isa<CastInst>(A) ||
1328  isa<PHINode>(A) ||
1329  isa<GetElementPtrInst>(A))
1330  if (Instruction *BI = dyn_cast<Instruction>(B))
1331  if (cast<Instruction>(A)->isIdenticalToWhenDefined(BI))
1332  return true;
1333 
1334  // Otherwise they may not be equivalent.
1335  return false;
1336 }
1337 
1338 /// Converts store (bitcast (load (bitcast (select ...)))) to
1339 /// store (load (select ...)), where select is minmax:
1340 /// select ((cmp load V1, load V2), V1, V2).
1342  StoreInst &SI) {
1343  // bitcast?
1344  if (!match(SI.getPointerOperand(), m_BitCast(m_Value())))
1345  return false;
1346  // load? integer?
1347  Value *LoadAddr;
1348  if (!match(SI.getValueOperand(), m_Load(m_BitCast(m_Value(LoadAddr)))))
1349  return false;
1350  auto *LI = cast<LoadInst>(SI.getValueOperand());
1351  if (!LI->getType()->isIntegerTy())
1352  return false;
1353  if (!isMinMaxWithLoads(LoadAddr))
1354  return false;
1355 
1356  if (!all_of(LI->users(), [LI, LoadAddr](User *U) {
1357  auto *SI = dyn_cast<StoreInst>(U);
1358  return SI && SI->getPointerOperand() != LI &&
1359  peekThroughBitcast(SI->getPointerOperand()) != LoadAddr &&
1360  !SI->getPointerOperand()->isSwiftError();
1361  }))
1362  return false;
1363 
1364  IC.Builder.SetInsertPoint(LI);
1365  LoadInst *NewLI = combineLoadToNewType(
1366  IC, *LI, LoadAddr->getType()->getPointerElementType());
1367  // Replace all the stores with stores of the newly loaded value.
1368  for (auto *UI : LI->users()) {
1369  auto *USI = cast<StoreInst>(UI);
1370  IC.Builder.SetInsertPoint(USI);
1371  combineStoreToNewValue(IC, *USI, NewLI);
1372  }
1373  IC.replaceInstUsesWith(*LI, UndefValue::get(LI->getType()));
1374  IC.eraseInstFromFunction(*LI);
1375  return true;
1376 }
1377 
1379  Value *Val = SI.getOperand(0);
1380  Value *Ptr = SI.getOperand(1);
1381 
1382  // Try to canonicalize the stored type.
1383  if (combineStoreToValueType(*this, SI))
1384  return eraseInstFromFunction(SI);
1385 
1386  // Attempt to improve the alignment.
1387  unsigned KnownAlign = getOrEnforceKnownAlignment(
1388  Ptr, DL.getPrefTypeAlignment(Val->getType()), DL, &SI, &AC, &DT);
1389  unsigned StoreAlign = SI.getAlignment();
1390  unsigned EffectiveStoreAlign =
1391  StoreAlign != 0 ? StoreAlign : DL.getABITypeAlignment(Val->getType());
1392 
1393  if (KnownAlign > EffectiveStoreAlign)
1394  SI.setAlignment(KnownAlign);
1395  else if (StoreAlign == 0)
1396  SI.setAlignment(EffectiveStoreAlign);
1397 
1398  // Try to canonicalize the stored type.
1399  if (unpackStoreToAggregate(*this, SI))
1400  return eraseInstFromFunction(SI);
1401 
1402  if (removeBitcastsFromLoadStoreOnMinMax(*this, SI))
1403  return eraseInstFromFunction(SI);
1404 
1405  // Replace GEP indices if possible.
1406  if (Instruction *NewGEPI = replaceGEPIdxWithZero(*this, Ptr, SI)) {
1407  Worklist.Add(NewGEPI);
1408  return &SI;
1409  }
1410 
1411  // Don't hack volatile/ordered stores.
1412  // FIXME: Some bits are legal for ordered atomic stores; needs refactoring.
1413  if (!SI.isUnordered()) return nullptr;
1414 
1415  // If the RHS is an alloca with a single use, zapify the store, making the
1416  // alloca dead.
1417  if (Ptr->hasOneUse()) {
1418  if (isa<AllocaInst>(Ptr))
1419  return eraseInstFromFunction(SI);
1420  if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Ptr)) {
1421  if (isa<AllocaInst>(GEP->getOperand(0))) {
1422  if (GEP->getOperand(0)->hasOneUse())
1423  return eraseInstFromFunction(SI);
1424  }
1425  }
1426  }
1427 
1428  // Do really simple DSE, to catch cases where there are several consecutive
1429  // stores to the same location, separated by a few arithmetic operations. This
1430  // situation often occurs with bitfield accesses.
1431  BasicBlock::iterator BBI(SI);
1432  for (unsigned ScanInsts = 6; BBI != SI.getParent()->begin() && ScanInsts;
1433  --ScanInsts) {
1434  --BBI;
1435  // Don't count debug info directives, lest they affect codegen,
1436  // and we skip pointer-to-pointer bitcasts, which are NOPs.
1437  if (isa<DbgInfoIntrinsic>(BBI) ||
1438  (isa<BitCastInst>(BBI) && BBI->getType()->isPointerTy())) {
1439  ScanInsts++;
1440  continue;
1441  }
1442 
1443  if (StoreInst *PrevSI = dyn_cast<StoreInst>(BBI)) {
1444  // Prev store isn't volatile, and stores to the same location?
1445  if (PrevSI->isUnordered() && equivalentAddressValues(PrevSI->getOperand(1),
1446  SI.getOperand(1))) {
1447  ++NumDeadStore;
1448  ++BBI;
1449  eraseInstFromFunction(*PrevSI);
1450  continue;
1451  }
1452  break;
1453  }
1454 
1455  // If this is a load, we have to stop. However, if the loaded value is from
1456  // the pointer we're loading and is producing the pointer we're storing,
1457  // then *this* store is dead (X = load P; store X -> P).
1458  if (LoadInst *LI = dyn_cast<LoadInst>(BBI)) {
1459  if (LI == Val && equivalentAddressValues(LI->getOperand(0), Ptr)) {
1460  assert(SI.isUnordered() && "can't eliminate ordering operation");
1461  return eraseInstFromFunction(SI);
1462  }
1463 
1464  // Otherwise, this is a load from some other location. Stores before it
1465  // may not be dead.
1466  break;
1467  }
1468 
1469  // Don't skip over loads, throws or things that can modify memory.
1470  if (BBI->mayWriteToMemory() || BBI->mayReadFromMemory() || BBI->mayThrow())
1471  break;
1472  }
1473 
1474  // store X, null -> turns into 'unreachable' in SimplifyCFG
1475  // store X, GEP(null, Y) -> turns into 'unreachable' in SimplifyCFG
1476  if (canSimplifyNullStoreOrGEP(SI)) {
1477  if (!isa<UndefValue>(Val)) {
1478  SI.setOperand(0, UndefValue::get(Val->getType()));
1479  if (Instruction *U = dyn_cast<Instruction>(Val))
1480  Worklist.Add(U); // Dropped a use.
1481  }
1482  return nullptr; // Do not modify these!
1483  }
1484 
1485  // store undef, Ptr -> noop
1486  if (isa<UndefValue>(Val))
1487  return eraseInstFromFunction(SI);
1488 
1489  // If this store is the last instruction in the basic block (possibly
1490  // excepting debug info instructions), and if the block ends with an
1491  // unconditional branch, try to move it to the successor block.
1492  BBI = SI.getIterator();
1493  do {
1494  ++BBI;
1495  } while (isa<DbgInfoIntrinsic>(BBI) ||
1496  (isa<BitCastInst>(BBI) && BBI->getType()->isPointerTy()));
1497  if (BranchInst *BI = dyn_cast<BranchInst>(BBI))
1498  if (BI->isUnconditional())
1499  if (SimplifyStoreAtEndOfBlock(SI))
1500  return nullptr; // xform done!
1501 
1502  return nullptr;
1503 }
1504 
1505 /// SimplifyStoreAtEndOfBlock - Turn things like:
1506 /// if () { *P = v1; } else { *P = v2 }
1507 /// into a phi node with a store in the successor.
1508 ///
1509 /// Simplify things like:
1510 /// *P = v1; if () { *P = v2; }
1511 /// into a phi node with a store in the successor.
1512 ///
1513 bool InstCombiner::SimplifyStoreAtEndOfBlock(StoreInst &SI) {
1514  assert(SI.isUnordered() &&
1515  "this code has not been auditted for volatile or ordered store case");
1516 
1517  BasicBlock *StoreBB = SI.getParent();
1518 
1519  // Check to see if the successor block has exactly two incoming edges. If
1520  // so, see if the other predecessor contains a store to the same location.
1521  // if so, insert a PHI node (if needed) and move the stores down.
1522  BasicBlock *DestBB = StoreBB->getTerminator()->getSuccessor(0);
1523 
1524  // Determine whether Dest has exactly two predecessors and, if so, compute
1525  // the other predecessor.
1526  pred_iterator PI = pred_begin(DestBB);
1527  BasicBlock *P = *PI;
1528  BasicBlock *OtherBB = nullptr;
1529 
1530  if (P != StoreBB)
1531  OtherBB = P;
1532 
1533  if (++PI == pred_end(DestBB))
1534  return false;
1535 
1536  P = *PI;
1537  if (P != StoreBB) {
1538  if (OtherBB)
1539  return false;
1540  OtherBB = P;
1541  }
1542  if (++PI != pred_end(DestBB))
1543  return false;
1544 
1545  // Bail out if all the relevant blocks aren't distinct (this can happen,
1546  // for example, if SI is in an infinite loop)
1547  if (StoreBB == DestBB || OtherBB == DestBB)
1548  return false;
1549 
1550  // Verify that the other block ends in a branch and is not otherwise empty.
1551  BasicBlock::iterator BBI(OtherBB->getTerminator());
1552  BranchInst *OtherBr = dyn_cast<BranchInst>(BBI);
1553  if (!OtherBr || BBI == OtherBB->begin())
1554  return false;
1555 
1556  // If the other block ends in an unconditional branch, check for the 'if then
1557  // else' case. there is an instruction before the branch.
1558  StoreInst *OtherStore = nullptr;
1559  if (OtherBr->isUnconditional()) {
1560  --BBI;
1561  // Skip over debugging info.
1562  while (isa<DbgInfoIntrinsic>(BBI) ||
1563  (isa<BitCastInst>(BBI) && BBI->getType()->isPointerTy())) {
1564  if (BBI==OtherBB->begin())
1565  return false;
1566  --BBI;
1567  }
1568  // If this isn't a store, isn't a store to the same location, or is not the
1569  // right kind of store, bail out.
1570  OtherStore = dyn_cast<StoreInst>(BBI);
1571  if (!OtherStore || OtherStore->getOperand(1) != SI.getOperand(1) ||
1572  !SI.isSameOperationAs(OtherStore))
1573  return false;
1574  } else {
1575  // Otherwise, the other block ended with a conditional branch. If one of the
1576  // destinations is StoreBB, then we have the if/then case.
1577  if (OtherBr->getSuccessor(0) != StoreBB &&
1578  OtherBr->getSuccessor(1) != StoreBB)
1579  return false;
1580 
1581  // Okay, we know that OtherBr now goes to Dest and StoreBB, so this is an
1582  // if/then triangle. See if there is a store to the same ptr as SI that
1583  // lives in OtherBB.
1584  for (;; --BBI) {
1585  // Check to see if we find the matching store.
1586  if ((OtherStore = dyn_cast<StoreInst>(BBI))) {
1587  if (OtherStore->getOperand(1) != SI.getOperand(1) ||
1588  !SI.isSameOperationAs(OtherStore))
1589  return false;
1590  break;
1591  }
1592  // If we find something that may be using or overwriting the stored
1593  // value, or if we run out of instructions, we can't do the xform.
1594  if (BBI->mayReadFromMemory() || BBI->mayThrow() ||
1595  BBI->mayWriteToMemory() || BBI == OtherBB->begin())
1596  return false;
1597  }
1598 
1599  // In order to eliminate the store in OtherBr, we have to
1600  // make sure nothing reads or overwrites the stored value in
1601  // StoreBB.
1602  for (BasicBlock::iterator I = StoreBB->begin(); &*I != &SI; ++I) {
1603  // FIXME: This should really be AA driven.
1604  if (I->mayReadFromMemory() || I->mayThrow() || I->mayWriteToMemory())
1605  return false;
1606  }
1607  }
1608 
1609  // Insert a PHI node now if we need it.
1610  Value *MergedVal = OtherStore->getOperand(0);
1611  if (MergedVal != SI.getOperand(0)) {
1612  PHINode *PN = PHINode::Create(MergedVal->getType(), 2, "storemerge");
1613  PN->addIncoming(SI.getOperand(0), SI.getParent());
1614  PN->addIncoming(OtherStore->getOperand(0), OtherBB);
1615  MergedVal = InsertNewInstBefore(PN, DestBB->front());
1616  }
1617 
1618  // Advance to a place where it is safe to insert the new store and
1619  // insert it.
1620  BBI = DestBB->getFirstInsertionPt();
1621  StoreInst *NewSI = new StoreInst(MergedVal, SI.getOperand(1),
1622  SI.isVolatile(),
1623  SI.getAlignment(),
1624  SI.getOrdering(),
1625  SI.getSyncScopeID());
1626  InsertNewInstBefore(NewSI, *BBI);
1627  // The debug locations of the original instructions might differ; merge them.
1628  NewSI->applyMergedLocation(SI.getDebugLoc(), OtherStore->getDebugLoc());
1629 
1630  // If the two stores had AA tags, merge them.
1631  AAMDNodes AATags;
1632  SI.getAAMetadata(AATags);
1633  if (AATags) {
1634  OtherStore->getAAMetadata(AATags, /* Merge = */ true);
1635  NewSI->setAAMetadata(AATags);
1636  }
1637 
1638  // Nuke the old stores.
1639  eraseInstFromFunction(SI);
1640  eraseInstFromFunction(*OtherStore);
1641  return true;
1642 }
Value * CreateInBoundsGEP(Value *Ptr, ArrayRef< Value *> IdxList, const Twine &Name="")
Definition: IRBuilder.h:1244
uint64_t CallInst * C
Value * getValueOperand()
Definition: Instructions.h:395
A parsed version of the target data layout string in and methods for querying it. ...
Definition: DataLayout.h:109
void computeKnownBits(const Value *V, KnownBits &Known, unsigned Depth, const Instruction *CxtI) const
constexpr char Align[]
Key for Kernel::Arg::Metadata::mAlign.
uint64_t getTypeStoreSizeInBits(Type *Ty) const
Returns the maximum number of bits that may be overwritten by storing the specified type; always a mu...
Definition: DataLayout.h:394
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
Definition: PatternMatch.h:72
bool isSimple() const
Definition: Instructions.h:262
class_match< CmpInst > m_Cmp()
Matches any compare instruction and ignore it.
Definition: PatternMatch.h:80
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
unsigned getOrEnforceKnownAlignment(Value *V, unsigned PrefAlign, const DataLayout &DL, const Instruction *CxtI=nullptr, AssumptionCache *AC=nullptr, const DominatorTree *DT=nullptr)
Try to ensure that the alignment of V is at least PrefAlign bytes.
Definition: Local.cpp:1066
GCNRegPressure max(const GCNRegPressure &P1, const GCNRegPressure &P2)
AllocaInst * CreateAlloca(Type *Ty, unsigned AddrSpace, Value *ArraySize=nullptr, const Twine &Name="")
Definition: IRBuilder.h:1156
static Constant * getPointerBitCastOrAddrSpaceCast(Constant *C, Type *Ty)
Create a BitCast or AddrSpaceCast for a pointer type depending on the address space.
Definition: Constants.cpp:1506
bool isSameOperationAs(const Instruction *I, unsigned flags=0) const
This function determines if the specified instruction executes the same operation as the current one...
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
bool isAtomic() const
Return true if this instruction has an AtomicOrdering of unordered or higher.
bool isSized(SmallPtrSetImpl< Type *> *Visited=nullptr) const
Return true if it makes sense to take the size of this type.
Definition: Type.h:262
BasicBlock * getSuccessor(unsigned idx) const
Return the specified successor.
LLVM_ATTRIBUTE_ALWAYS_INLINE size_type size() const
Definition: SmallVector.h:136
static bool canSimplifyNullStoreOrGEP(StoreInst &SI)
void setAlignment(unsigned Align)
bool isUnordered() const
Definition: Instructions.h:389
const StructLayout * getStructLayout(StructType *Ty) const
Returns a StructLayout object, indicating the alignment of the struct, its size, and the offsets of i...
Definition: DataLayout.cpp:562
static GetElementPtrInst * Create(Type *PointeeType, Value *Ptr, ArrayRef< Value *> IdxList, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Definition: Instructions.h:863
cl::opt< unsigned > DefMaxInstsToScan
The default number of maximum instructions to scan in the block, used by FindAvailableLoadedValue().
static PointerType * get(Type *ElementType, unsigned AddressSpace)
This constructs a pointer to an object of the specified type in a numbered address space...
Definition: Type.cpp:617
SyncScope::ID getSyncScopeID() const
Returns the synchronization scope ID of this store instruction.
Definition: Instructions.h:370
bool mayWriteToMemory() const
Return true if this instruction may modify memory.
static bool isDereferenceableForAllocaSize(const Value *V, const AllocaInst *AI, const DataLayout &DL)
Returns true if V is dereferenceable for size of alloca.
AtomicOrdering getOrdering() const
Returns the ordering constraint of this load instruction.
Definition: Instructions.h:233
static SelectInst * Create(Value *C, Value *S1, Value *S2, const Twine &NameStr="", Instruction *InsertBefore=nullptr, Instruction *MDFrom=nullptr)
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:728
This class implements a map that also provides access to all stored values in a deterministic order...
Definition: MapVector.h:38
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:813
STATISTIC(NumFunctions, "Total number of functions")
Metadata node.
Definition: Metadata.h:862
unsigned getPointerAddressSpace() const
Get the address space of this pointer or pointer vector type.
Definition: DerivedTypes.h:503
static LoadInst * combineLoadToNewType(InstCombiner &IC, LoadInst &LI, Type *NewTy, const Twine &Suffix="")
Helper to combine a load to a new type.
An instruction for reading from memory.
Definition: Instructions.h:164
static bool pointsToConstantGlobal(Value *V)
pointsToConstantGlobal - Return true if V (possibly indirectly) points to some part of a constant glo...
uint64_t MaxArraySizeForCombine
Maximum size of array considered when transforming.
static IntegerType * getInt64Ty(LLVMContext &C)
Definition: Type.cpp:177
Hexagon Common GEP
void setAtomic(AtomicOrdering Ordering, SyncScope::ID SSID=SyncScope::System)
Sets the ordering constraint and the synchronization scope ID of this store instruction.
Definition: Instructions.h:381
bool isSafeToLoadUnconditionally(Value *V, unsigned Align, const DataLayout &DL, Instruction *ScanFrom=nullptr, const DominatorTree *DT=nullptr)
Return true if we know that executing a load from this value cannot trap.
Definition: Loads.cpp:201
LLVMContext & getContext() const
Return the LLVMContext in which this type was uniqued.
Definition: Type.h:130
static Constant * getNullValue(Type *Ty)
Constructor to create a &#39;0&#39; constant of arbitrary type.
Definition: Constants.cpp:206
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:252
StoreInst * CreateAlignedStore(Value *Val, Value *Ptr, unsigned Align, bool isVolatile=false)
Definition: IRBuilder.h:1203
void setAtomic(AtomicOrdering Ordering, SyncScope::ID SSID=SyncScope::System)
Sets the ordering constraint and the synchronization scope ID of this load instruction.
Definition: Instructions.h:256
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
bool isVolatile() const
Return true if this is a load from a volatile memory location.
Definition: Instructions.h:217
This class represents the LLVM &#39;select&#39; instruction.
Type * getPointerElementType() const
Definition: Type.h:373
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:81
unsigned getAlignment() const
Return the alignment of the memory that is being allocated by the instruction.
Definition: Instructions.h:109
ArrayRef< T > makeArrayRef(const T &OneElt)
Construct an ArrayRef from a single element.
Definition: ArrayRef.h:451
PointerType * getType() const
Overload to return most specific pointer type.
Definition: Instructions.h:97
bool isFloatingPointTy() const
Return true if this is one of the six floating-point types.
Definition: Type.h:162
Value * FindAvailableLoadedValue(LoadInst *Load, BasicBlock *ScanBB, BasicBlock::iterator &ScanFrom, unsigned MaxInstsToScan=DefMaxInstsToScan, AliasAnalysis *AA=nullptr, bool *IsLoadCSE=nullptr, unsigned *NumScanedInst=nullptr)
Scan backwards to see if we have the value of the given load available locally within a small number ...
Definition: Loads.cpp:321
APInt zextOrSelf(unsigned width) const
Zero extend or truncate to width.
Definition: APInt.cpp:899
PointerType * getPointerTo(unsigned AddrSpace=0) const
Return a pointer to the current type.
Definition: Type.cpp:639
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:42
Instruction * eraseInstFromFunction(Instruction &I)
Combiner aware instruction erasure.
bool isIntegerTy() const
True if this is an instance of IntegerType.
Definition: Type.h:197
static Instruction * replaceGEPIdxWithZero(InstCombiner &IC, Value *Ptr, T &MemI)
The core instruction combiner logic.
void setName(const Twine &Name)
Change the name of the value.
Definition: Value.cpp:286
Type * getSourceElementType() const
Definition: Instructions.h:934
Instruction * clone() const
Create a copy of &#39;this&#39; instruction that is identical in all ways except the following: ...
unsigned getPointerAddressSpace() const
Returns the address space of the pointer operand.
Definition: Instructions.h:404
A constant value that is initialized with an expression using other constant values.
Definition: Constants.h:862
static Value * peekThroughBitcast(Value *V, bool OneUseOnly=false)
Return the source operand of a potentially bitcasted value while optionally checking if it has one us...
Value * CreateBitCast(Value *V, Type *DestTy, const Twine &Name="")
Definition: IRBuilder.h:1448
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:245
void copyNonnullMetadata(const LoadInst &OldLI, MDNode *N, LoadInst &NewLI)
Copy a nonnull metadata node to a new load instruction.
Definition: Local.cpp:1924
bool isInBounds() const
Determine whether the GEP has the inbounds flag.
static Instruction * simplifyAllocaArraySize(InstCombiner &IC, AllocaInst &AI)
bool isSwiftError() const
Return true if this value is a swifterror value.
Definition: Value.cpp:749
This class represents a no-op cast from one type to another.
op_iterator idx_begin()
Definition: Instructions.h:962
const APInt & getValue() const
Return the constant as an APInt value reference.
Definition: Constants.h:138
SmallString - A SmallString is just a SmallVector with methods and accessors that make it work better...
Definition: SmallString.h:26
An instruction for storing to memory.
Definition: Instructions.h:306
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:430
SelectClass_match< Cond, LHS, RHS > m_Select(const Cond &C, const LHS &L, const RHS &R)
Definition: PatternMatch.h:869
void takeName(Value *V)
Transfer the name from V to this value.
Definition: Value.cpp:292
void SetInsertPoint(BasicBlock *TheBB)
This specifies that created instructions should be appended to the end of the specified block...
Definition: IRBuilder.h:128
Value * getOperand(unsigned i) const
Definition: User.h:154
const DataLayout & getDataLayout() const
const BasicBlock & getEntryBlock() const
Definition: Function.h:572
constexpr uint64_t MinAlign(uint64_t A, uint64_t B)
A and B are either alignments or offsets.
Definition: MathExtras.h:602
an instruction for type-safe pointer arithmetic to access elements of arrays and structs ...
Definition: Instructions.h:837
IntegerType * getIntPtrType(LLVMContext &C, unsigned AddressSpace=0) const
Returns an integer type with size at least as big as that of a pointer in the given address space...
Definition: DataLayout.cpp:702
void getAAMetadata(AAMDNodes &N, bool Merge=false) const
Fills the AAMDNodes structure with AA metadata from this instruction.
#define P(N)
static Instruction * combineLoadToOperationType(InstCombiner &IC, LoadInst &LI)
Combine loads to match the type of their uses&#39; value after looking through intervening bitcasts...
static bool equivalentAddressValues(Value *A, Value *B)
equivalentAddressValues - Test if A and B will obviously have the same value.
static bool unpackStoreToAggregate(InstCombiner &IC, StoreInst &SI)
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
const_iterator getFirstInsertionPt() const
Returns an iterator to the first instruction in this block that is suitable for inserting a non-PHI i...
Definition: BasicBlock.cpp:200
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Definition: Instruction.h:282
void insertBefore(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately before the specified instruction...
Definition: Instruction.cpp:73
void setAAMetadata(const AAMDNodes &N)
Sets the metadata on this instruction from the AAMDNodes structure.
Definition: Metadata.cpp:1253
LLVM Basic Block Representation.
Definition: BasicBlock.h:59
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:46
Conditional or Unconditional Branch instruction.
CastClass_match< OpTy, Instruction::BitCast > m_BitCast(const OpTy &Op)
Matches BitCast.
Definition: PatternMatch.h:900
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This is an important base class in LLVM.
Definition: Constant.h:42
bool isPointerTy() const
True if this is an instance of PointerType.
Definition: Type.h:221
const Instruction & front() const
Definition: BasicBlock.h:264
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:371
static StoreInst * combineStoreToNewValue(InstCombiner &IC, StoreInst &SI, Value *V)
Combine a store to a new type.
bool mayThrow() const
Return true if this instruction may throw an exception.
Interval::pred_iterator pred_begin(Interval *I)
pred_begin/pred_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Definition: Interval.h:113
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
Definition: PatternMatch.h:382
bool isUnordered() const
Definition: Instructions.h:264
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:853
void copyRangeMetadata(const DataLayout &DL, const LoadInst &OldLI, MDNode *N, LoadInst &NewLI)
Copy a range metadata node to a new load instruction.
Definition: Local.cpp:1949
Instruction * visitAllocaInst(AllocaInst &AI)
Interval::pred_iterator pred_end(Interval *I)
Definition: Interval.h:116
Value * getPointerOperand()
Definition: Instructions.h:270
self_iterator getIterator()
Definition: ilist_node.h:82
void setAlignment(unsigned Align)
static UndefValue * get(Type *T)
Static factory methods - Return an &#39;undef&#39; object of the specified type.
Definition: Constants.cpp:1319
const AMDGPUAS & AS
const Value * stripPointerCasts() const
Strip off pointer casts, all-zero GEPs, and aliases.
Definition: Value.cpp:558
const Value * getArraySize() const
Get the number of elements allocated.
Definition: Instructions.h:93
Value * CreateExtractValue(Value *Agg, ArrayRef< unsigned > Idxs, const Twine &Name="")
Definition: IRBuilder.h:1755
bool isVolatile() const
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
void setMetadata(unsigned KindID, MDNode *Node)
Set the metadata of the specified kind to the specified node.
Definition: Metadata.cpp:1214
Type * getAllocatedType() const
Return the type that is being allocated by the instruction.
Definition: Instructions.h:102
LoadClass_match< OpTy > m_Load(const OpTy &Op)
Matches LoadInst.
Definition: PatternMatch.h:976
static bool canSimplifyNullLoadOrGEP(LoadInst &LI, Value *Op)
static bool isOnlyCopiedFromConstantGlobal(Value *V, MemTransferInst *&TheCopy, SmallVectorImpl< Instruction *> &ToDelete)
isOnlyCopiedFromConstantGlobal - Recursively walk the uses of a (derived) pointer to an alloca...
Iterator for intrusive lists based on ilist_node.
unsigned getNumOperands() const
Definition: User.h:176
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:418
This is the shared class of boolean and integer constants.
Definition: Constants.h:84
Value * CreateIntCast(Value *V, Type *DestTy, bool isSigned, const Twine &Name="")
Definition: IRBuilder.h:1511
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:864
Instruction * user_back()
Specialize the methods defined in Value, as we know that an instruction can only be used by other ins...
Definition: Instruction.h:64
static bool isSupportedAtomicType(Type *Ty)
bool isLegalInteger(uint64_t Width) const
Returns true if the specified type is known to be a native integer type supported by the CPU...
Definition: DataLayout.h:238
unsigned getABITypeAlignment(Type *Ty) const
Returns the minimum ABI-required alignment for the specified type.
Definition: DataLayout.cpp:682
bool isAggregateType() const
Return true if the type is an aggregate type.
Definition: Type.h:255
A collection of metadata nodes that might be associated with a memory access used by the alias-analys...
Definition: Metadata.h:642
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:385
ConstantInt * getInt32(uint32_t C)
Get a constant 32-bit value.
Definition: IRBuilder.h:308
static IntegerType * getIntNTy(LLVMContext &C, unsigned N)
Definition: Type.cpp:180
static Constant * get(Type *Ty, uint64_t V, bool isSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
Definition: Constants.cpp:559
void applyMergedLocation(const DILocation *LocA, const DILocation *LocB)
Merge 2 debug locations and apply it to the Instruction.
Definition: DebugInfo.cpp:676
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
static bool combineStoreToValueType(InstCombiner &IC, StoreInst &SI)
Combine stores to match the type of value being stored.
void getAllMetadata(SmallVectorImpl< std::pair< unsigned, MDNode *>> &MDs) const
Get all metadata attached to this Instruction.
Definition: Instruction.h:211
void setOperand(unsigned i, Value *Val)
Definition: User.h:159
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
Class for arbitrary precision integers.
Definition: APInt.h:69
iterator_range< user_iterator > users()
Definition: Value.h:405
static bool isObjectSizeLessThanOrEq(Value *V, uint64_t MaxSize, const DataLayout &DL)
void append(in_iter in_start, in_iter in_end)
Add the specified range to the end of the SmallVector.
Definition: SmallVector.h:398
bool isNonIntegralPointerType(PointerType *PT) const
Definition: DataLayout.h:330
uint64_t getTypeSizeInBits(Type *Ty) const
Size examples:
Definition: DataLayout.h:530
uint64_t getTypeAllocSize(Type *Ty) const
Returns the offset in bytes between successive objects of the specified type, including alignment pad...
Definition: DataLayout.h:403
This class wraps the llvm.memcpy/memmove intrinsics.
bool isVolatile() const
Return true if this is a store to a volatile memory location.
Definition: Instructions.h:339
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
Definition: Instruction.h:285
unsigned getAlignment() const
Return the alignment of the access that is being performed.
Definition: Instructions.h:226
void emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:656
static Type * getIndexedType(Type *Ty, ArrayRef< Value *> IdxList)
Returns the type of the element that would be loaded with a load instruction with the specified param...
static IntegerType * getInt32Ty(LLVMContext &C)
Definition: Type.cpp:176
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:61
AtomicOrdering getOrdering() const
Returns the ordering constraint of this store instruction.
Definition: Instructions.h:358
static bool removeBitcastsFromLoadStoreOnMinMax(InstCombiner &IC, StoreInst &SI)
Converts store (bitcast (load (bitcast (select ...)))) to store (load (select ...)), where select is minmax: select ((cmp load V1, load V2), V1, V2).
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:220
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:108
SyncScope::ID getSyncScopeID() const
Returns the synchronization scope ID of this load instruction.
Definition: Instructions.h:245
#define I(x, y, z)
Definition: MD5.cpp:58
#define N
static Value * likeBitCastFromVector(InstCombiner &IC, Value *V)
Look for extractelement/insertvalue sequence that acts like a bitcast.
bool mayReadFromMemory() const
Return true if this instruction may read memory.
Value * getSource() const
This is just like getRawSource, but it strips off any cast instructions that feed it...
static ArrayType * get(Type *ElementType, uint64_t NumElements)
This static method is the primary way to construct an ArrayType.
Definition: Type.cpp:568
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
Definition: Casting.h:323
This instruction extracts a single (scalar) element from a VectorType value.
Instruction * InsertNewInstBefore(Instruction *New, Instruction &Old)
Inserts an instruction New before instruction Old.
void combineMetadataForCSE(Instruction *K, const Instruction *J)
Combine the metadata of two instructions so that K can replace J.
Definition: Local.cpp:1831
unsigned getAlignment() const
Return the alignment of the access that is being performed.
Definition: Instructions.h:351
unsigned getPointerAddressSpace() const
Returns the address space of the pointer operand.
Definition: Instructions.h:276
static GetElementPtrInst * CreateInBounds(Value *Ptr, ArrayRef< Value *> IdxList, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Create an "inbounds" getelementptr.
Definition: Instructions.h:897
bool isArrayAllocation() const
Return true if there is an allocation size parameter to the allocation instruction that is not 1...
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
user_iterator user_begin()
Definition: Value.h:381
static bool canReplaceGEPIdxWithZero(InstCombiner &IC, GetElementPtrInst *GEPI, Instruction *MemI, unsigned &Idx)
Instruction * replaceInstUsesWith(Instruction &I, Value *V)
A combiner-aware RAUW-like routine.
LoadInst * CreateAlignedLoad(Value *Ptr, unsigned Align, const char *Name)
Definition: IRBuilder.h:1186
Instruction * visitLoadInst(LoadInst &LI)
LLVM Value Representation.
Definition: Value.h:73
void setAlignment(unsigned Align)
This file provides internal interfaces used to implement the InstCombine.
uint64_t getTypeStoreSize(Type *Ty) const
Returns the maximum number of bytes that may be overwritten by storing the specified type...
Definition: DataLayout.h:386
Instruction * visitStoreInst(StoreInst &SI)
void moveBefore(Instruction *MovePos)
Unlink this instruction from its current basic block and insert it into the basic block that MovePos ...
Definition: Instruction.cpp:86
#define DEBUG(X)
Definition: Debug.h:118
IRTranslator LLVM IR MI
bool hasOneUse() const
Return true if there is exactly one user of this value.
Definition: Value.h:418
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:49
static Expected< std::string > replace(StringRef S, StringRef From, StringRef To)
bool isNonNegative() const
Returns true if this value is known to be non-negative.
Definition: KnownBits.h:99
const Instruction * getFirstNonPHIOrDbg() const
Returns a pointer to the first instruction in this block that is not a PHINode or a debug intrinsic...
Definition: BasicBlock.cpp:178
bool isDereferenceableAndAlignedPointer(const Value *V, unsigned Align, const DataLayout &DL, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr)
Returns true if V is always a dereferenceable pointer with alignment greater or equal than requested...
Definition: Loads.cpp:129
bool isSimple() const
Definition: Instructions.h:387
const TerminatorInst * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.cpp:120
Value * CreateInsertValue(Value *Agg, Value *Val, ArrayRef< unsigned > Idxs, const Twine &Name="")
Definition: IRBuilder.h:1763
Value * getPointerOperand()
Definition: Instructions.h:398
static Instruction * unpackLoadToAggregate(InstCombiner &IC, LoadInst &LI)
bool use_empty() const
Definition: Value.h:328
bind_ty< Instruction > m_Instruction(Instruction *&I)
Match an instruction, capturing it if we match.
Definition: PatternMatch.h:359
static bool isMinMaxWithLoads(Value *V)
Returns true if instruction represent minmax pattern like: select ((cmp load V1, load V2)...
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:44
const BasicBlock * getParent() const
Definition: Instruction.h:67
an instruction to allocate memory on the stack
Definition: Instructions.h:60
user_iterator user_end()
Definition: Value.h:389