lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp

   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/SmallString.h"
  16 #include "llvm/ADT/Statistic.h"
  17 #include "llvm/Analysis/Loads.h"
  18 #include "llvm/IR/ConstantRange.h"
  19 #include "llvm/IR/DataLayout.h"
  20 #include "llvm/IR/LLVMContext.h"
  21 #include "llvm/IR/IntrinsicInst.h"
  22 #include "llvm/IR/MDBuilder.h"
  23 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
  24 #include "llvm/Transforms/Utils/Local.h"
  25 using namespace llvm;
  26
  27 #define DEBUG_TYPE "instcombine"
  28
  29 STATISTIC(NumDeadStore,    "Number of dead stores eliminated");
  30 STATISTIC(NumGlobalCopies, "Number of allocas copied from constant global");
  31
  32 /// pointsToConstantGlobal - Return true if V (possibly indirectly) points to
  33 /// some part of a constant global variable.  This intentionally only accepts
  34 /// constant expressions because we can't rewrite arbitrary instructions.
  35 static bool pointsToConstantGlobal(Value *V) {
  36   if (GlobalVariable *GV = dyn_cast<GlobalVariable>(V))
  37     return GV->isConstant();
  38
  39   if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) {
  40     if (CE->getOpcode() == Instruction::BitCast ||
  41         CE->getOpcode() == Instruction::AddrSpaceCast ||
  42         CE->getOpcode() == Instruction::GetElementPtr)
  43       return pointsToConstantGlobal(CE->getOperand(0));
  44   }
  45   return false;
  46 }
  47
  48 /// isOnlyCopiedFromConstantGlobal - Recursively walk the uses of a (derived)
  49 /// pointer to an alloca.  Ignore any reads of the pointer, return false if we
  50 /// see any stores or other unknown uses.  If we see pointer arithmetic, keep
  51 /// track of whether it moves the pointer (with IsOffset) but otherwise traverse
  52 /// the uses.  If we see a memcpy/memmove that targets an unoffseted pointer to
  53 /// the alloca, and if the source pointer is a pointer to a constant global, we
  54 /// can optimize this.
  55 static bool
  56 isOnlyCopiedFromConstantGlobal(Value *V, MemTransferInst *&TheCopy,
  57                                SmallVectorImpl<Instruction *> &ToDelete) {
  58   // We track lifetime intrinsics as we encounter them.  If we decide to go
  59   // ahead and replace the value with the global, this lets the caller quickly
  60   // eliminate the markers.
  61
  62   SmallVector<std::pair<Value *, bool>, 35> ValuesToInspect;
  63   ValuesToInspect.emplace_back(V, false);
  64   while (!ValuesToInspect.empty()) {
  65     auto ValuePair = ValuesToInspect.pop_back_val();
  66     const bool IsOffset = ValuePair.second;
  67     for (auto &U : ValuePair.first->uses()) {
  68       auto *I = cast<Instruction>(U.getUser());
  69
  70       if (auto *LI = dyn_cast<LoadInst>(I)) {
  71         // Ignore non-volatile loads, they are always ok.
  72         if (!LI->isSimple()) return false;
  73         continue;
  74       }
  75
  76       if (isa<BitCastInst>(I) || isa<AddrSpaceCastInst>(I)) {
  77         // If uses of the bitcast are ok, we are ok.
  78         ValuesToInspect.emplace_back(I, IsOffset);
  79         continue;
  80       }
  81       if (auto *GEP = dyn_cast<GetElementPtrInst>(I)) {
  82         // If the GEP has all zero indices, it doesn't offset the pointer. If it
  83         // doesn't, it does.
  84         ValuesToInspect.emplace_back(I, IsOffset || !GEP->hasAllZeroIndices());
  85         continue;
  86       }
  87
  88       if (auto CS = CallSite(I)) {
  89         // If this is the function being called then we treat it like a load and
  90         // ignore it.
  91         if (CS.isCallee(&U))
  92           continue;
  93
  94         unsigned DataOpNo = CS.getDataOperandNo(&U);
  95         bool IsArgOperand = CS.isArgOperand(&U);
  96
  97         // Inalloca arguments are clobbered by the call.
  98         if (IsArgOperand && CS.isInAllocaArgument(DataOpNo))
  99           return false;
 100
 101         // If this is a readonly/readnone call site, then we know it is just a
 102         // load (but one that potentially returns the value itself), so we can
 103         // ignore it if we know that the value isn't captured.
 104         if (CS.onlyReadsMemory() &&
 105             (CS.getInstruction()->use_empty() || CS.doesNotCapture(DataOpNo)))
 106           continue;
 107
 108         // If this is being passed as a byval argument, the caller is making a
 109         // copy, so it is only a read of the alloca.
 110         if (IsArgOperand && CS.isByValArgument(DataOpNo))
 111           continue;
 112       }
 113
 114       // Lifetime intrinsics can be handled by the caller.
 115       if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
 116         if (II->getIntrinsicID() == Intrinsic::lifetime_start ||
 117             II->getIntrinsicID() == Intrinsic::lifetime_end) {
 118           assert(II->use_empty() && "Lifetime markers have no result to use!");
 119           ToDelete.push_back(II);
 120           continue;
 121         }
 122       }
 123
 124       // If this is isn't our memcpy/memmove, reject it as something we can't
 125       // handle.
 126       MemTransferInst *MI = dyn_cast<MemTransferInst>(I);
 127       if (!MI)
 128         return false;
 129
 130       // If the transfer is using the alloca as a source of the transfer, then
 131       // ignore it since it is a load (unless the transfer is volatile).
 132       if (U.getOperandNo() == 1) {
 133         if (MI->isVolatile()) return false;
 134         continue;
 135       }
 136
 137       // If we already have seen a copy, reject the second one.
 138       if (TheCopy) return false;
 139
 140       // If the pointer has been offset from the start of the alloca, we can't
 141       // safely handle this.
 142       if (IsOffset) return false;
 143
 144       // If the memintrinsic isn't using the alloca as the dest, reject it.
 145       if (U.getOperandNo() != 0) return false;
 146
 147       // If the source of the memcpy/move is not a constant global, reject it.
 148       if (!pointsToConstantGlobal(MI->getSource()))
 149         return false;
 150
 151       // Otherwise, the transform is safe.  Remember the copy instruction.
 152       TheCopy = MI;
 153     }
 154   }
 155   return true;
 156 }
 157
 158 /// isOnlyCopiedFromConstantGlobal - Return true if the specified alloca is only
 159 /// modified by a copy from a constant global.  If we can prove this, we can
 160 /// replace any uses of the alloca with uses of the global directly.
 161 static MemTransferInst *
 162 isOnlyCopiedFromConstantGlobal(AllocaInst *AI,
 163                                SmallVectorImpl<Instruction *> &ToDelete) {
 164   MemTransferInst *TheCopy = nullptr;
 165   if (isOnlyCopiedFromConstantGlobal(AI, TheCopy, ToDelete))
 166     return TheCopy;
 167   return nullptr;
 168 }
 169
 170 static Instruction *simplifyAllocaArraySize(InstCombiner &IC, AllocaInst &AI) {
 171   // Check for array size of 1 (scalar allocation).
 172   if (!AI.isArrayAllocation()) {
 173     // i32 1 is the canonical array size for scalar allocations.
 174     if (AI.getArraySize()->getType()->isIntegerTy(32))
 175       return nullptr;
 176
 177     // Canonicalize it.
 178     Value *V = IC.Builder->getInt32(1);
 179     AI.setOperand(0, V);
 180     return &AI;
 181   }
 182
 183   // Convert: alloca Ty, C - where C is a constant != 1 into: alloca [C x Ty], 1
 184   if (const ConstantInt *C = dyn_cast<ConstantInt>(AI.getArraySize())) {
 185     Type *NewTy = ArrayType::get(AI.getAllocatedType(), C->getZExtValue());
 186     AllocaInst *New = IC.Builder->CreateAlloca(NewTy, nullptr, AI.getName());
 187     New->setAlignment(AI.getAlignment());
 188
 189     // Scan to the end of the allocation instructions, to skip over a block of
 190     // allocas if possible...also skip interleaved debug info
 191     //
 192     BasicBlock::iterator It(New);
 193     while (isa<AllocaInst>(*It) || isa<DbgInfoIntrinsic>(*It))
 194       ++It;
 195
 196     // Now that I is pointing to the first non-allocation-inst in the block,
 197     // insert our getelementptr instruction...
 198     //
 199     Type *IdxTy = IC.getDataLayout().getIntPtrType(AI.getType());
 200     Value *NullIdx = Constant::getNullValue(IdxTy);
 201     Value *Idx[2] = {NullIdx, NullIdx};
 202     Instruction *GEP =
 203         GetElementPtrInst::CreateInBounds(New, Idx, New->getName() + ".sub");
 204     IC.InsertNewInstBefore(GEP, *It);
 205
 206     // Now make everything use the getelementptr instead of the original
 207     // allocation.
 208     return IC.replaceInstUsesWith(AI, GEP);
 209   }
 210
 211   if (isa<UndefValue>(AI.getArraySize()))
 212     return IC.replaceInstUsesWith(AI, Constant::getNullValue(AI.getType()));
 213
 214   // Ensure that the alloca array size argument has type intptr_t, so that
 215   // any casting is exposed early.
 216   Type *IntPtrTy = IC.getDataLayout().getIntPtrType(AI.getType());
 217   if (AI.getArraySize()->getType() != IntPtrTy) {
 218     Value *V = IC.Builder->CreateIntCast(AI.getArraySize(), IntPtrTy, false);
 219     AI.setOperand(0, V);
 220     return &AI;
 221   }
 222
 223   return nullptr;
 224 }
 225
 226 Instruction *InstCombiner::visitAllocaInst(AllocaInst &AI) {
 227   if (auto *I = simplifyAllocaArraySize(*this, AI))
 228     return I;
 229
 230   if (AI.getAllocatedType()->isSized()) {
 231     // If the alignment is 0 (unspecified), assign it the preferred alignment.
 232     if (AI.getAlignment() == 0)
 233       AI.setAlignment(DL.getPrefTypeAlignment(AI.getAllocatedType()));
 234
 235     // Move all alloca's of zero byte objects to the entry block and merge them
 236     // together.  Note that we only do this for alloca's, because malloc should
 237     // allocate and return a unique pointer, even for a zero byte allocation.
 238     if (DL.getTypeAllocSize(AI.getAllocatedType()) == 0) {
 239       // For a zero sized alloca there is no point in doing an array allocation.
 240       // This is helpful if the array size is a complicated expression not used
 241       // elsewhere.
 242       if (AI.isArrayAllocation()) {
 243         AI.setOperand(0, ConstantInt::get(AI.getArraySize()->getType(), 1));
 244         return &AI;
 245       }
 246
 247       // Get the first instruction in the entry block.
 248       BasicBlock &EntryBlock = AI.getParent()->getParent()->getEntryBlock();
 249       Instruction *FirstInst = EntryBlock.getFirstNonPHIOrDbg();
 250       if (FirstInst != &AI) {
 251         // If the entry block doesn't start with a zero-size alloca then move
 252         // this one to the start of the entry block.  There is no problem with
 253         // dominance as the array size was forced to a constant earlier already.
 254         AllocaInst *EntryAI = dyn_cast<AllocaInst>(FirstInst);
 255         if (!EntryAI || !EntryAI->getAllocatedType()->isSized() ||
 256             DL.getTypeAllocSize(EntryAI->getAllocatedType()) != 0) {
 257           AI.moveBefore(FirstInst);
 258           return &AI;
 259         }
 260
 261         // If the alignment of the entry block alloca is 0 (unspecified),
 262         // assign it the preferred alignment.
 263         if (EntryAI->getAlignment() == 0)
 264           EntryAI->setAlignment(
 265               DL.getPrefTypeAlignment(EntryAI->getAllocatedType()));
 266         // Replace this zero-sized alloca with the one at the start of the entry
 267         // block after ensuring that the address will be aligned enough for both
 268         // types.
 269         unsigned MaxAlign = std::max(EntryAI->getAlignment(),
 270                                      AI.getAlignment());
 271         EntryAI->setAlignment(MaxAlign);
 272         if (AI.getType() != EntryAI->getType())
 273           return new BitCastInst(EntryAI, AI.getType());
 274         return replaceInstUsesWith(AI, EntryAI);
 275       }
 276     }
 277   }
 278
 279   if (AI.getAlignment()) {
 280     // Check to see if this allocation is only modified by a memcpy/memmove from
 281     // a constant global whose alignment is equal to or exceeds that of the
 282     // allocation.  If this is the case, we can change all users to use
 283     // the constant global instead.  This is commonly produced by the CFE by
 284     // constructs like "void foo() { int A[] = {1,2,3,4,5,6,7,8,9...}; }" if 'A'
 285     // is only subsequently read.
 286     SmallVector<Instruction *, 4> ToDelete;
 287     if (MemTransferInst *Copy = isOnlyCopiedFromConstantGlobal(&AI, ToDelete)) {
 288       unsigned SourceAlign = getOrEnforceKnownAlignment(
 289           Copy->getSource(), AI.getAlignment(), DL, &AI, &AC, &DT);
 290       if (AI.getAlignment() <= SourceAlign) {
 291         DEBUG(dbgs() << "Found alloca equal to global: " << AI << '\n');
 292         DEBUG(dbgs() << "  memcpy = " << *Copy << '\n');
 293         for (unsigned i = 0, e = ToDelete.size(); i != e; ++i)
 294           eraseInstFromFunction(*ToDelete[i]);
 295         Constant *TheSrc = cast<Constant>(Copy->getSource());
 296         Constant *Cast
 297           = ConstantExpr::getPointerBitCastOrAddrSpaceCast(TheSrc, AI.getType());
 298         Instruction *NewI = replaceInstUsesWith(AI, Cast);
 299         eraseInstFromFunction(*Copy);
 300         ++NumGlobalCopies;
 301         return NewI;
 302       }
 303     }
 304   }
 305
 306   // At last, use the generic allocation site handler to aggressively remove
 307   // unused allocas.
 308   return visitAllocSite(AI);
 309 }
 310
 311 // Are we allowed to form a atomic load or store of this type?
 312 static bool isSupportedAtomicType(Type *Ty) {
 313   return Ty->isIntegerTy() || Ty->isPointerTy() || Ty->isFloatingPointTy();
 314 }
 315
 316 /// \brief Helper to combine a load to a new type.
 317 ///
 318 /// This just does the work of combining a load to a new type. It handles
 319 /// metadata, etc., and returns the new instruction. The \c NewTy should be the
 320 /// loaded *value* type. This will convert it to a pointer, cast the operand to
 321 /// that pointer type, load it, etc.
 322 ///
 323 /// Note that this will create all of the instructions with whatever insert
 324 /// point the \c InstCombiner currently is using.
 325 static LoadInst *combineLoadToNewType(InstCombiner &IC, LoadInst &LI, Type *NewTy,
 326                                       const Twine &Suffix = "") {
 327   assert((!LI.isAtomic() || isSupportedAtomicType(NewTy)) &&
 328          "can't fold an atomic load to requested type");
 329
 330   Value *Ptr = LI.getPointerOperand();
 331   unsigned AS = LI.getPointerAddressSpace();
 332   SmallVector<std::pair<unsigned, MDNode *>, 8> MD;
 333   LI.getAllMetadata(MD);
 334
 335   LoadInst *NewLoad = IC.Builder->CreateAlignedLoad(
 336       IC.Builder->CreateBitCast(Ptr, NewTy->getPointerTo(AS)),
 337       LI.getAlignment(), LI.isVolatile(), LI.getName() + Suffix);
 338   NewLoad->setAtomic(LI.getOrdering(), LI.getSynchScope());
 339   MDBuilder MDB(NewLoad->getContext());
 340   for (const auto &MDPair : MD) {
 341     unsigned ID = MDPair.first;
 342     MDNode *N = MDPair.second;
 343     // Note, essentially every kind of metadata should be preserved here! This
 344     // routine is supposed to clone a load instruction changing *only its type*.
 345     // The only metadata it makes sense to drop is metadata which is invalidated
 346     // when the pointer type changes. This should essentially never be the case
 347     // in LLVM, but we explicitly switch over only known metadata to be
 348     // conservatively correct. If you are adding metadata to LLVM which pertains
 349     // to loads, you almost certainly want to add it here.
 350     switch (ID) {
 351     case LLVMContext::MD_dbg:
 352     case LLVMContext::MD_tbaa:
 353     case LLVMContext::MD_prof:
 354     case LLVMContext::MD_fpmath:
 355     case LLVMContext::MD_tbaa_struct:
 356     case LLVMContext::MD_invariant_load:
 357     case LLVMContext::MD_alias_scope:
 358     case LLVMContext::MD_noalias:
 359     case LLVMContext::MD_nontemporal:
 360     case LLVMContext::MD_mem_parallel_loop_access:
 361       // All of these directly apply.
 362       NewLoad->setMetadata(ID, N);
 363       break;
 364
 365     case LLVMContext::MD_nonnull:
 366       // This only directly applies if the new type is also a pointer.
 367       if (NewTy->isPointerTy()) {
 368         NewLoad->setMetadata(ID, N);
 369         break;
 370       }
 371       // If it's integral now, translate it to !range metadata.
 372       if (NewTy->isIntegerTy()) {
 373         auto *ITy = cast<IntegerType>(NewTy);
 374         auto *NullInt = ConstantExpr::getPtrToInt(
 375             ConstantPointerNull::get(cast<PointerType>(Ptr->getType())), ITy);
 376         auto *NonNullInt =
 377             ConstantExpr::getAdd(NullInt, ConstantInt::get(ITy, 1));
 378         NewLoad->setMetadata(LLVMContext::MD_range,
 379                              MDB.createRange(NonNullInt, NullInt));
 380       }
 381       break;
 382     case LLVMContext::MD_align:
 383     case LLVMContext::MD_dereferenceable:
 384     case LLVMContext::MD_dereferenceable_or_null:
 385       // These only directly apply if the new type is also a pointer.
 386       if (NewTy->isPointerTy())
 387         NewLoad->setMetadata(ID, N);
 388       break;
 389     case LLVMContext::MD_range:
 390       // FIXME: It would be nice to propagate this in some way, but the type
 391       // conversions make it hard.
 392
 393       // If it's a pointer now and the range does not contain 0, make it !nonnull.
 394       if (NewTy->isPointerTy()) {
 395         unsigned BitWidth = IC.getDataLayout().getTypeSizeInBits(NewTy);
 396         if (!getConstantRangeFromMetadata(*N).contains(APInt(BitWidth, 0))) {
 397           MDNode *NN = MDNode::get(LI.getContext(), None);
 398           NewLoad->setMetadata(LLVMContext::MD_nonnull, NN);
 399         }
 400       }
 401       break;
 402     }
 403   }
 404   return NewLoad;
 405 }
 406
 407 /// \brief Combine a store to a new type.
 408 ///
 409 /// Returns the newly created store instruction.
 410 static StoreInst *combineStoreToNewValue(InstCombiner &IC, StoreInst &SI, Value *V) {
 411   assert((!SI.isAtomic() || isSupportedAtomicType(V->getType())) &&
 412          "can't fold an atomic store of requested type");
 413
 414   Value *Ptr = SI.getPointerOperand();
 415   unsigned AS = SI.getPointerAddressSpace();
 416   SmallVector<std::pair<unsigned, MDNode *>, 8> MD;
 417   SI.getAllMetadata(MD);
 418
 419   StoreInst *NewStore = IC.Builder->CreateAlignedStore(
 420       V, IC.Builder->CreateBitCast(Ptr, V->getType()->getPointerTo(AS)),
 421       SI.getAlignment(), SI.isVolatile());
 422   NewStore->setAtomic(SI.getOrdering(), SI.getSynchScope());
 423   for (const auto &MDPair : MD) {
 424     unsigned ID = MDPair.first;
 425     MDNode *N = MDPair.second;
 426     // Note, essentially every kind of metadata should be preserved here! This
 427     // routine is supposed to clone a store instruction changing *only its
 428     // type*. The only metadata it makes sense to drop is metadata which is
 429     // invalidated when the pointer type changes. This should essentially
 430     // never be the case in LLVM, but we explicitly switch over only known
 431     // metadata to be conservatively correct. If you are adding metadata to
 432     // LLVM which pertains to stores, you almost certainly want to add it
 433     // here.
 434     switch (ID) {
 435     case LLVMContext::MD_dbg:
 436     case LLVMContext::MD_tbaa:
 437     case LLVMContext::MD_prof:
 438     case LLVMContext::MD_fpmath:
 439     case LLVMContext::MD_tbaa_struct:
 440     case LLVMContext::MD_alias_scope:
 441     case LLVMContext::MD_noalias:
 442     case LLVMContext::MD_nontemporal:
 443     case LLVMContext::MD_mem_parallel_loop_access:
 444       // All of these directly apply.
 445       NewStore->setMetadata(ID, N);
 446       break;
 447
 448     case LLVMContext::MD_invariant_load:
 449     case LLVMContext::MD_nonnull:
 450     case LLVMContext::MD_range:
 451     case LLVMContext::MD_align:
 452     case LLVMContext::MD_dereferenceable:
 453     case LLVMContext::MD_dereferenceable_or_null:
 454       // These don't apply for stores.
 455       break;
 456     }
 457   }
 458
 459   return NewStore;
 460 }
 461
 462 /// \brief Combine loads to match the type of their uses' value after looking
 463 /// through intervening bitcasts.
 464 ///
 465 /// The core idea here is that if the result of a load is used in an operation,
 466 /// we should load the type most conducive to that operation. For example, when
 467 /// loading an integer and converting that immediately to a pointer, we should
 468 /// instead directly load a pointer.
 469 ///
 470 /// However, this routine must never change the width of a load or the number of
 471 /// loads as that would introduce a semantic change. This combine is expected to
 472 /// be a semantic no-op which just allows loads to more closely model the types
 473 /// of their consuming operations.
 474 ///
 475 /// Currently, we also refuse to change the precise type used for an atomic load
 476 /// or a volatile load. This is debatable, and might be reasonable to change
 477 /// later. However, it is risky in case some backend or other part of LLVM is
 478 /// relying on the exact type loaded to select appropriate atomic operations.
 479 static Instruction *combineLoadToOperationType(InstCombiner &IC, LoadInst &LI) {
 480   // FIXME: We could probably with some care handle both volatile and ordered
 481   // atomic loads here but it isn't clear that this is important.
 482   if (!LI.isUnordered())
 483     return nullptr;
 484
 485   if (LI.use_empty())
 486     return nullptr;
 487
 488   // swifterror values can't be bitcasted.
 489   if (LI.getPointerOperand()->isSwiftError())
 490     return nullptr;
 491
 492   Type *Ty = LI.getType();
 493   const DataLayout &DL = IC.getDataLayout();
 494
 495   // Try to canonicalize loads which are only ever stored to operate over
 496   // integers instead of any other type. We only do this when the loaded type
 497   // is sized and has a size exactly the same as its store size and the store
 498   // size is a legal integer type.
 499   if (!Ty->isIntegerTy() && Ty->isSized() &&
 500       DL.isLegalInteger(DL.getTypeStoreSizeInBits(Ty)) &&
 501       DL.getTypeStoreSizeInBits(Ty) == DL.getTypeSizeInBits(Ty) &&
 502       !DL.isNonIntegralPointerType(Ty)) {
 503     if (all_of(LI.users(), [&LI](User *U) {
 504           auto *SI = dyn_cast<StoreInst>(U);
 505           return SI && SI->getPointerOperand() != &LI;
 506         })) {
 507       LoadInst *NewLoad = combineLoadToNewType(
 508           IC, LI,
 509           Type::getIntNTy(LI.getContext(), DL.getTypeStoreSizeInBits(Ty)));
 510       // Replace all the stores with stores of the newly loaded value.
 511       for (auto UI = LI.user_begin(), UE = LI.user_end(); UI != UE;) {
 512         auto *SI = cast<StoreInst>(*UI++);
 513         IC.Builder->SetInsertPoint(SI);
 514         combineStoreToNewValue(IC, *SI, NewLoad);
 515         IC.eraseInstFromFunction(*SI);
 516       }
 517       assert(LI.use_empty() && "Failed to remove all users of the load!");
 518       // Return the old load so the combiner can delete it safely.
 519       return &LI;
 520     }
 521   }
 522
 523   // Fold away bit casts of the loaded value by loading the desired type.
 524   // We can do this for BitCastInsts as well as casts from and to pointer types,
 525   // as long as those are noops (i.e., the source or dest type have the same
 526   // bitwidth as the target's pointers).
 527   if (LI.hasOneUse())
 528     if (auto* CI = dyn_cast<CastInst>(LI.user_back()))
 529       if (CI->isNoopCast(DL))
 530         if (!LI.isAtomic() || isSupportedAtomicType(CI->getDestTy())) {
 531           LoadInst *NewLoad = combineLoadToNewType(IC, LI, CI->getDestTy());
 532           CI->replaceAllUsesWith(NewLoad);
 533           IC.eraseInstFromFunction(*CI);
 534           return &LI;
 535         }
 536
 537   // FIXME: We should also canonicalize loads of vectors when their elements are
 538   // cast to other types.
 539   return nullptr;
 540 }
 541
 542 static Instruction *unpackLoadToAggregate(InstCombiner &IC, LoadInst &LI) {
 543   // FIXME: We could probably with some care handle both volatile and atomic
 544   // stores here but it isn't clear that this is important.
 545   if (!LI.isSimple())
 546     return nullptr;
 547
 548   Type *T = LI.getType();
 549   if (!T->isAggregateType())
 550     return nullptr;
 551
 552   StringRef Name = LI.getName();
 553   assert(LI.getAlignment() && "Alignment must be set at this point");
 554
 555   if (auto *ST = dyn_cast<StructType>(T)) {
 556     // If the struct only have one element, we unpack.
 557     auto NumElements = ST->getNumElements();
 558     if (NumElements == 1) {
 559       LoadInst *NewLoad = combineLoadToNewType(IC, LI, ST->getTypeAtIndex(0U),
 560                                                ".unpack");
 561       return IC.replaceInstUsesWith(LI, IC.Builder->CreateInsertValue(
 562         UndefValue::get(T), NewLoad, 0, Name));
 563     }
 564
 565     // We don't want to break loads with padding here as we'd loose
 566     // the knowledge that padding exists for the rest of the pipeline.
 567     const DataLayout &DL = IC.getDataLayout();
 568     auto *SL = DL.getStructLayout(ST);
 569     if (SL->hasPadding())
 570       return nullptr;
 571
 572     auto Align = LI.getAlignment();
 573     if (!Align)
 574       Align = DL.getABITypeAlignment(ST);
 575
 576     auto *Addr = LI.getPointerOperand();
 577     auto *IdxType = Type::getInt32Ty(T->getContext());
 578     auto *Zero = ConstantInt::get(IdxType, 0);
 579
 580     Value *V = UndefValue::get(T);
 581     for (unsigned i = 0; i < NumElements; i++) {
 582       Value *Indices[2] = {
 583         Zero,
 584         ConstantInt::get(IdxType, i),
 585       };
 586       auto *Ptr = IC.Builder->CreateInBoundsGEP(ST, Addr, makeArrayRef(Indices),
 587                                                 Name + ".elt");
 588       auto EltAlign = MinAlign(Align, SL->getElementOffset(i));
 589       auto *L = IC.Builder->CreateAlignedLoad(Ptr, EltAlign, Name + ".unpack");
 590       V = IC.Builder->CreateInsertValue(V, L, i);
 591     }
 592
 593     V->setName(Name);
 594     return IC.replaceInstUsesWith(LI, V);
 595   }
 596
 597   if (auto *AT = dyn_cast<ArrayType>(T)) {
 598     auto *ET = AT->getElementType();
 599     auto NumElements = AT->getNumElements();
 600     if (NumElements == 1) {
 601       LoadInst *NewLoad = combineLoadToNewType(IC, LI, ET, ".unpack");
 602       return IC.replaceInstUsesWith(LI, IC.Builder->CreateInsertValue(
 603         UndefValue::get(T), NewLoad, 0, Name));
 604     }
 605
 606     // Bail out if the array is too large. Ideally we would like to optimize
 607     // arrays of arbitrary size but this has a terrible impact on compile time.
 608     // The threshold here is chosen arbitrarily, maybe needs a little bit of
 609     // tuning.
 610     if (NumElements > 1024)
 611       return nullptr;
 612
 613     const DataLayout &DL = IC.getDataLayout();
 614     auto EltSize = DL.getTypeAllocSize(ET);
 615     auto Align = LI.getAlignment();
 616     if (!Align)
 617       Align = DL.getABITypeAlignment(T);
 618
 619     auto *Addr = LI.getPointerOperand();
 620     auto *IdxType = Type::getInt64Ty(T->getContext());
 621     auto *Zero = ConstantInt::get(IdxType, 0);
 622
 623     Value *V = UndefValue::get(T);
 624     uint64_t Offset = 0;
 625     for (uint64_t i = 0; i < NumElements; i++) {
 626       Value *Indices[2] = {
 627         Zero,
 628         ConstantInt::get(IdxType, i),
 629       };
 630       auto *Ptr = IC.Builder->CreateInBoundsGEP(AT, Addr, makeArrayRef(Indices),
 631                                                 Name + ".elt");
 632       auto *L = IC.Builder->CreateAlignedLoad(Ptr, MinAlign(Align, Offset),
 633                                               Name + ".unpack");
 634       V = IC.Builder->CreateInsertValue(V, L, i);
 635       Offset += EltSize;
 636     }
 637
 638     V->setName(Name);
 639     return IC.replaceInstUsesWith(LI, V);
 640   }
 641
 642   return nullptr;
 643 }
 644
 645 // If we can determine that all possible objects pointed to by the provided
 646 // pointer value are, not only dereferenceable, but also definitively less than
 647 // or equal to the provided maximum size, then return true. Otherwise, return
 648 // false (constant global values and allocas fall into this category).
 649 //
 650 // FIXME: This should probably live in ValueTracking (or similar).
 651 static bool isObjectSizeLessThanOrEq(Value *V, uint64_t MaxSize,
 652                                      const DataLayout &DL) {
 653   SmallPtrSet<Value *, 4> Visited;
 654   SmallVector<Value *, 4> Worklist(1, V);
 655
 656   do {
 657     Value *P = Worklist.pop_back_val();
 658     P = P->stripPointerCasts();
 659
 660     if (!Visited.insert(P).second)
 661       continue;
 662
 663     if (SelectInst *SI = dyn_cast<SelectInst>(P)) {
 664       Worklist.push_back(SI->getTrueValue());
 665       Worklist.push_back(SI->getFalseValue());
 666       continue;
 667     }
 668
 669     if (PHINode *PN = dyn_cast<PHINode>(P)) {
 670       for (Value *IncValue : PN->incoming_values())
 671         Worklist.push_back(IncValue);
 672       continue;
 673     }
 674
 675     if (GlobalAlias *GA = dyn_cast<GlobalAlias>(P)) {
 676       if (GA->isInterposable())
 677         return false;
 678       Worklist.push_back(GA->getAliasee());
 679       continue;
 680     }
 681
 682     // If we know how big this object is, and it is less than MaxSize, continue
 683     // searching. Otherwise, return false.
 684     if (AllocaInst *AI = dyn_cast<AllocaInst>(P)) {
 685       if (!AI->getAllocatedType()->isSized())
 686         return false;
 687
 688       ConstantInt *CS = dyn_cast<ConstantInt>(AI->getArraySize());
 689       if (!CS)
 690         return false;
 691
 692       uint64_t TypeSize = DL.getTypeAllocSize(AI->getAllocatedType());
 693       // Make sure that, even if the multiplication below would wrap as an
 694       // uint64_t, we still do the right thing.
 695       if ((CS->getValue().zextOrSelf(128)*APInt(128, TypeSize)).ugt(MaxSize))
 696         return false;
 697       continue;
 698     }
 699
 700     if (GlobalVariable *GV = dyn_cast<GlobalVariable>(P)) {
 701       if (!GV->hasDefinitiveInitializer() || !GV->isConstant())
 702         return false;
 703
 704       uint64_t InitSize = DL.getTypeAllocSize(GV->getValueType());
 705       if (InitSize > MaxSize)
 706         return false;
 707       continue;
 708     }
 709
 710     return false;
 711   } while (!Worklist.empty());
 712
 713   return true;
 714 }
 715
 716 // If we're indexing into an object of a known size, and the outer index is
 717 // not a constant, but having any value but zero would lead to undefined
 718 // behavior, replace it with zero.
 719 //
 720 // For example, if we have:
 721 // @f.a = private unnamed_addr constant [1 x i32] [i32 12], align 4
 722 // ...
 723 // %arrayidx = getelementptr inbounds [1 x i32]* @f.a, i64 0, i64 %x
 724 // ... = load i32* %arrayidx, align 4
 725 // Then we know that we can replace %x in the GEP with i64 0.
 726 //
 727 // FIXME: We could fold any GEP index to zero that would cause UB if it were
 728 // not zero. Currently, we only handle the first such index. Also, we could
 729 // also search through non-zero constant indices if we kept track of the
 730 // offsets those indices implied.
 731 static bool canReplaceGEPIdxWithZero(InstCombiner &IC, GetElementPtrInst *GEPI,
 732                                      Instruction *MemI, unsigned &Idx) {
 733   if (GEPI->getNumOperands() < 2)
 734     return false;
 735
 736   // Find the first non-zero index of a GEP. If all indices are zero, return
 737   // one past the last index.
 738   auto FirstNZIdx = [](const GetElementPtrInst *GEPI) {
 739     unsigned I = 1;
 740     for (unsigned IE = GEPI->getNumOperands(); I != IE; ++I) {
 741       Value *V = GEPI->getOperand(I);
 742       if (const ConstantInt *CI = dyn_cast<ConstantInt>(V))
 743         if (CI->isZero())
 744           continue;
 745
 746       break;
 747     }
 748
 749     return I;
 750   };
 751
 752   // Skip through initial 'zero' indices, and find the corresponding pointer
 753   // type. See if the next index is not a constant.
 754   Idx = FirstNZIdx(GEPI);
 755   if (Idx == GEPI->getNumOperands())
 756     return false;
 757   if (isa<Constant>(GEPI->getOperand(Idx)))
 758     return false;
 759
 760   SmallVector<Value *, 4> Ops(GEPI->idx_begin(), GEPI->idx_begin() + Idx);
 761   Type *AllocTy =
 762     GetElementPtrInst::getIndexedType(GEPI->getSourceElementType(), Ops);
 763   if (!AllocTy || !AllocTy->isSized())
 764     return false;
 765   const DataLayout &DL = IC.getDataLayout();
 766   uint64_t TyAllocSize = DL.getTypeAllocSize(AllocTy);
 767
 768   // If there are more indices after the one we might replace with a zero, make
 769   // sure they're all non-negative. If any of them are negative, the overall
 770   // address being computed might be before the base address determined by the
 771   // first non-zero index.
 772   auto IsAllNonNegative = [&]() {
 773     for (unsigned i = Idx+1, e = GEPI->getNumOperands(); i != e; ++i) {
 774       bool KnownNonNegative, KnownNegative;
 775       IC.ComputeSignBit(GEPI->getOperand(i), KnownNonNegative,
 776                         KnownNegative, 0, MemI);
 777       if (KnownNonNegative)
 778         continue;
 779       return false;
 780     }
 781
 782     return true;
 783   };
 784
 785   // FIXME: If the GEP is not inbounds, and there are extra indices after the
 786   // one we'll replace, those could cause the address computation to wrap
 787   // (rendering the IsAllNonNegative() check below insufficient). We can do
 788   // better, ignoring zero indices (and other indices we can prove small
 789   // enough not to wrap).
 790   if (Idx+1 != GEPI->getNumOperands() && !GEPI->isInBounds())
 791     return false;
 792
 793   // Note that isObjectSizeLessThanOrEq will return true only if the pointer is
 794   // also known to be dereferenceable.
 795   return isObjectSizeLessThanOrEq(GEPI->getOperand(0), TyAllocSize, DL) &&
 796          IsAllNonNegative();
 797 }
 798
 799 // If we're indexing into an object with a variable index for the memory
 800 // access, but the object has only one element, we can assume that the index
 801 // will always be zero. If we replace the GEP, return it.
 802 template <typename T>
 803 static Instruction *replaceGEPIdxWithZero(InstCombiner &IC, Value *Ptr,
 804                                           T &MemI) {
 805   if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(Ptr)) {
 806     unsigned Idx;
 807     if (canReplaceGEPIdxWithZero(IC, GEPI, &MemI, Idx)) {
 808       Instruction *NewGEPI = GEPI->clone();
 809       NewGEPI->setOperand(Idx,
 810         ConstantInt::get(GEPI->getOperand(Idx)->getType(), 0));
 811       NewGEPI->insertBefore(GEPI);
 812       MemI.setOperand(MemI.getPointerOperandIndex(), NewGEPI);
 813       return NewGEPI;
 814     }
 815   }
 816
 817   return nullptr;
 818 }
 819
 820 Instruction *InstCombiner::visitLoadInst(LoadInst &LI) {
 821   Value *Op = LI.getOperand(0);
 822
 823   // Try to canonicalize the loaded type.
 824   if (Instruction *Res = combineLoadToOperationType(*this, LI))
 825     return Res;
 826
 827   // Attempt to improve the alignment.
 828   unsigned KnownAlign = getOrEnforceKnownAlignment(
 829       Op, DL.getPrefTypeAlignment(LI.getType()), DL, &LI, &AC, &DT);
 830   unsigned LoadAlign = LI.getAlignment();
 831   unsigned EffectiveLoadAlign =
 832       LoadAlign != 0 ? LoadAlign : DL.getABITypeAlignment(LI.getType());
 833
 834   if (KnownAlign > EffectiveLoadAlign)
 835     LI.setAlignment(KnownAlign);
 836   else if (LoadAlign == 0)
 837     LI.setAlignment(EffectiveLoadAlign);
 838
 839   // Replace GEP indices if possible.
 840   if (Instruction *NewGEPI = replaceGEPIdxWithZero(*this, Op, LI)) {
 841       Worklist.Add(NewGEPI);
 842       return &LI;
 843   }
 844
 845   if (Instruction *Res = unpackLoadToAggregate(*this, LI))
 846     return Res;
 847
 848   // Do really simple store-to-load forwarding and load CSE, to catch cases
 849   // where there are several consecutive memory accesses to the same location,
 850   // separated by a few arithmetic operations.
 851   BasicBlock::iterator BBI(LI);
 852   bool IsLoadCSE = false;
 853   if (Value *AvailableVal =
 854       FindAvailableLoadedValue(&LI, LI.getParent(), BBI,
 855                                DefMaxInstsToScan, AA, &IsLoadCSE)) {
 856     if (IsLoadCSE) {
 857       LoadInst *NLI = cast<LoadInst>(AvailableVal);
 858       unsigned KnownIDs[] = {
 859           LLVMContext::MD_tbaa,            LLVMContext::MD_alias_scope,
 860           LLVMContext::MD_noalias,         LLVMContext::MD_range,
 861           LLVMContext::MD_invariant_load,  LLVMContext::MD_nonnull,
 862           LLVMContext::MD_invariant_group, LLVMContext::MD_align,
 863           LLVMContext::MD_dereferenceable,
 864           LLVMContext::MD_dereferenceable_or_null};
 865       combineMetadata(NLI, &LI, KnownIDs);
 866     };
 867
 868     return replaceInstUsesWith(
 869         LI, Builder->CreateBitOrPointerCast(AvailableVal, LI.getType(),
 870                                             LI.getName() + ".cast"));
 871   }
 872
 873   // None of the following transforms are legal for volatile/ordered atomic
 874   // loads.  Most of them do apply for unordered atomics.
 875   if (!LI.isUnordered()) return nullptr;
 876
 877   // load(gep null, ...) -> unreachable
 878   if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(Op)) {
 879     const Value *GEPI0 = GEPI->getOperand(0);
 880     // TODO: Consider a target hook for valid address spaces for this xform.
 881     if (isa<ConstantPointerNull>(GEPI0) && GEPI->getPointerAddressSpace() == 0){
 882       // Insert a new store to null instruction before the load to indicate
 883       // that this code is not reachable.  We do this instead of inserting
 884       // an unreachable instruction directly because we cannot modify the
 885       // CFG.
 886       new StoreInst(UndefValue::get(LI.getType()),
 887                     Constant::getNullValue(Op->getType()), &LI);
 888       return replaceInstUsesWith(LI, UndefValue::get(LI.getType()));
 889     }
 890   }
 891
 892   // load null/undef -> unreachable
 893   // TODO: Consider a target hook for valid address spaces for this xform.
 894   if (isa<UndefValue>(Op) ||
 895       (isa<ConstantPointerNull>(Op) && LI.getPointerAddressSpace() == 0)) {
 896     // Insert a new store to null instruction before the load to indicate that
 897     // this code is not reachable.  We do this instead of inserting an
 898     // unreachable instruction directly because we cannot modify the CFG.
 899     new StoreInst(UndefValue::get(LI.getType()),
 900                   Constant::getNullValue(Op->getType()), &LI);
 901     return replaceInstUsesWith(LI, UndefValue::get(LI.getType()));
 902   }
 903
 904   if (Op->hasOneUse()) {
 905     // Change select and PHI nodes to select values instead of addresses: this
 906     // helps alias analysis out a lot, allows many others simplifications, and
 907     // exposes redundancy in the code.
 908     //
 909     // Note that we cannot do the transformation unless we know that the
 910     // introduced loads cannot trap!  Something like this is valid as long as
 911     // the condition is always false: load (select bool %C, int* null, int* %G),
 912     // but it would not be valid if we transformed it to load from null
 913     // unconditionally.
 914     //
 915     if (SelectInst *SI = dyn_cast<SelectInst>(Op)) {
 916       // load (select (Cond, &V1, &V2))  --> select(Cond, load &V1, load &V2).
 917       unsigned Align = LI.getAlignment();
 918       if (isSafeToLoadUnconditionally(SI->getOperand(1), Align, DL, SI) &&
 919           isSafeToLoadUnconditionally(SI->getOperand(2), Align, DL, SI)) {
 920         LoadInst *V1 = Builder->CreateLoad(SI->getOperand(1),
 921                                            SI->getOperand(1)->getName()+".val");
 922         LoadInst *V2 = Builder->CreateLoad(SI->getOperand(2),
 923                                            SI->getOperand(2)->getName()+".val");
 924         assert(LI.isUnordered() && "implied by above");
 925         V1->setAlignment(Align);
 926         V1->setAtomic(LI.getOrdering(), LI.getSynchScope());
 927         V2->setAlignment(Align);
 928         V2->setAtomic(LI.getOrdering(), LI.getSynchScope());
 929         return SelectInst::Create(SI->getCondition(), V1, V2);
 930       }
 931
 932       // load (select (cond, null, P)) -> load P
 933       if (isa<ConstantPointerNull>(SI->getOperand(1)) &&
 934           LI.getPointerAddressSpace() == 0) {
 935         LI.setOperand(0, SI->getOperand(2));
 936         return &LI;
 937       }
 938
 939       // load (select (cond, P, null)) -> load P
 940       if (isa<ConstantPointerNull>(SI->getOperand(2)) &&
 941           LI.getPointerAddressSpace() == 0) {
 942         LI.setOperand(0, SI->getOperand(1));
 943         return &LI;
 944       }
 945     }
 946   }
 947   return nullptr;
 948 }
 949
 950 /// \brief Look for extractelement/insertvalue sequence that acts like a bitcast.
 951 ///
 952 /// \returns underlying value that was "cast", or nullptr otherwise.
 953 ///
 954 /// For example, if we have:
 955 ///
 956 ///     %E0 = extractelement <2 x double> %U, i32 0
 957 ///     %V0 = insertvalue [2 x double] undef, double %E0, 0
 958 ///     %E1 = extractelement <2 x double> %U, i32 1
 959 ///     %V1 = insertvalue [2 x double] %V0, double %E1, 1
 960 ///
 961 /// and the layout of a <2 x double> is isomorphic to a [2 x double],
 962 /// then %V1 can be safely approximated by a conceptual "bitcast" of %U.
 963 /// Note that %U may contain non-undef values where %V1 has undef.
 964 static Value *likeBitCastFromVector(InstCombiner &IC, Value *V) {
 965   Value *U = nullptr;
 966   while (auto *IV = dyn_cast<InsertValueInst>(V)) {
 967     auto *E = dyn_cast<ExtractElementInst>(IV->getInsertedValueOperand());
 968     if (!E)
 969       return nullptr;
 970     auto *W = E->getVectorOperand();
 971     if (!U)
 972       U = W;
 973     else if (U != W)
 974       return nullptr;
 975     auto *CI = dyn_cast<ConstantInt>(E->getIndexOperand());
 976     if (!CI || IV->getNumIndices() != 1 || CI->getZExtValue() != *IV->idx_begin())
 977       return nullptr;
 978     V = IV->getAggregateOperand();
 979   }
 980   if (!isa<UndefValue>(V) ||!U)
 981     return nullptr;
 982
 983   auto *UT = cast<VectorType>(U->getType());
 984   auto *VT = V->getType();
 985   // Check that types UT and VT are bitwise isomorphic.
 986   const auto &DL = IC.getDataLayout();
 987   if (DL.getTypeStoreSizeInBits(UT) != DL.getTypeStoreSizeInBits(VT)) {
 988     return nullptr;
 989   }
 990   if (auto *AT = dyn_cast<ArrayType>(VT)) {
 991     if (AT->getNumElements() != UT->getNumElements())
 992       return nullptr;
 993   } else {
 994     auto *ST = cast<StructType>(VT);
 995     if (ST->getNumElements() != UT->getNumElements())
 996       return nullptr;
 997     for (const auto *EltT : ST->elements()) {
 998       if (EltT != UT->getElementType())
 999         return nullptr;
1000     }
1001   }
1002   return U;
1003 }
1004
1005 /// \brief Combine stores to match the type of value being stored.
1006 ///
1007 /// The core idea here is that the memory does not have any intrinsic type and
1008 /// where we can we should match the type of a store to the type of value being
1009 /// stored.
1010 ///
1011 /// However, this routine must never change the width of a store or the number of
1012 /// stores as that would introduce a semantic change. This combine is expected to
1013 /// be a semantic no-op which just allows stores to more closely model the types
1014 /// of their incoming values.
1015 ///
1016 /// Currently, we also refuse to change the precise type used for an atomic or
1017 /// volatile store. This is debatable, and might be reasonable to change later.
1018 /// However, it is risky in case some backend or other part of LLVM is relying
1019 /// on the exact type stored to select appropriate atomic operations.
1020 ///
1021 /// \returns true if the store was successfully combined away. This indicates
1022 /// the caller must erase the store instruction. We have to let the caller erase
1023 /// the store instruction as otherwise there is no way to signal whether it was
1024 /// combined or not: IC.EraseInstFromFunction returns a null pointer.
1025 static bool combineStoreToValueType(InstCombiner &IC, StoreInst &SI) {
1026   // FIXME: We could probably with some care handle both volatile and ordered
1027   // atomic stores here but it isn't clear that this is important.
1028   if (!SI.isUnordered())
1029     return false;
1030
1031   // swifterror values can't be bitcasted.
1032   if (SI.getPointerOperand()->isSwiftError())
1033     return false;
1034
1035   Value *V = SI.getValueOperand();
1036
1037   // Fold away bit casts of the stored value by storing the original type.
1038   if (auto *BC = dyn_cast<BitCastInst>(V)) {
1039     V = BC->getOperand(0);
1040     if (!SI.isAtomic() || isSupportedAtomicType(V->getType())) {
1041       combineStoreToNewValue(IC, SI, V);
1042       return true;
1043     }
1044   }
1045
1046   if (Value *U = likeBitCastFromVector(IC, V))
1047     if (!SI.isAtomic() || isSupportedAtomicType(U->getType())) {
1048       combineStoreToNewValue(IC, SI, U);
1049       return true;
1050     }
1051
1052   // FIXME: We should also canonicalize stores of vectors when their elements
1053   // are cast to other types.
1054   return false;
1055 }
1056
1057 static bool unpackStoreToAggregate(InstCombiner &IC, StoreInst &SI) {
1058   // FIXME: We could probably with some care handle both volatile and atomic
1059   // stores here but it isn't clear that this is important.
1060   if (!SI.isSimple())
1061     return false;
1062
1063   Value *V = SI.getValueOperand();
1064   Type *T = V->getType();
1065
1066   if (!T->isAggregateType())
1067     return false;
1068
1069   if (auto *ST = dyn_cast<StructType>(T)) {
1070     // If the struct only have one element, we unpack.
1071     unsigned Count = ST->getNumElements();
1072     if (Count == 1) {
1073       V = IC.Builder->CreateExtractValue(V, 0);
1074       combineStoreToNewValue(IC, SI, V);
1075       return true;
1076     }
1077
1078     // We don't want to break loads with padding here as we'd loose
1079     // the knowledge that padding exists for the rest of the pipeline.
1080     const DataLayout &DL = IC.getDataLayout();
1081     auto *SL = DL.getStructLayout(ST);
1082     if (SL->hasPadding())
1083       return false;
1084
1085     auto Align = SI.getAlignment();
1086     if (!Align)
1087       Align = DL.getABITypeAlignment(ST);
1088
1089     SmallString<16> EltName = V->getName();
1090     EltName += ".elt";
1091     auto *Addr = SI.getPointerOperand();
1092     SmallString<16> AddrName = Addr->getName();
1093     AddrName += ".repack";
1094
1095     auto *IdxType = Type::getInt32Ty(ST->getContext());
1096     auto *Zero = ConstantInt::get(IdxType, 0);
1097     for (unsigned i = 0; i < Count; i++) {
1098       Value *Indices[2] = {
1099         Zero,
1100         ConstantInt::get(IdxType, i),
1101       };
1102       auto *Ptr = IC.Builder->CreateInBoundsGEP(ST, Addr, makeArrayRef(Indices),
1103                                                 AddrName);
1104       auto *Val = IC.Builder->CreateExtractValue(V, i, EltName);
1105       auto EltAlign = MinAlign(Align, SL->getElementOffset(i));
1106       IC.Builder->CreateAlignedStore(Val, Ptr, EltAlign);
1107     }
1108
1109     return true;
1110   }
1111
1112   if (auto *AT = dyn_cast<ArrayType>(T)) {
1113     // If the array only have one element, we unpack.
1114     auto NumElements = AT->getNumElements();
1115     if (NumElements == 1) {
1116       V = IC.Builder->CreateExtractValue(V, 0);
1117       combineStoreToNewValue(IC, SI, V);
1118       return true;
1119     }
1120
1121     // Bail out if the array is too large. Ideally we would like to optimize
1122     // arrays of arbitrary size but this has a terrible impact on compile time.
1123     // The threshold here is chosen arbitrarily, maybe needs a little bit of
1124     // tuning.
1125     if (NumElements > 1024)
1126       return false;
1127
1128     const DataLayout &DL = IC.getDataLayout();
1129     auto EltSize = DL.getTypeAllocSize(AT->getElementType());
1130     auto Align = SI.getAlignment();
1131     if (!Align)
1132       Align = DL.getABITypeAlignment(T);
1133
1134     SmallString<16> EltName = V->getName();
1135     EltName += ".elt";
1136     auto *Addr = SI.getPointerOperand();
1137     SmallString<16> AddrName = Addr->getName();
1138     AddrName += ".repack";
1139
1140     auto *IdxType = Type::getInt64Ty(T->getContext());
1141     auto *Zero = ConstantInt::get(IdxType, 0);
1142
1143     uint64_t Offset = 0;
1144     for (uint64_t i = 0; i < NumElements; i++) {
1145       Value *Indices[2] = {
1146         Zero,
1147         ConstantInt::get(IdxType, i),
1148       };
1149       auto *Ptr = IC.Builder->CreateInBoundsGEP(AT, Addr, makeArrayRef(Indices),
1150                                                 AddrName);
1151       auto *Val = IC.Builder->CreateExtractValue(V, i, EltName);
1152       auto EltAlign = MinAlign(Align, Offset);
1153       IC.Builder->CreateAlignedStore(Val, Ptr, EltAlign);
1154       Offset += EltSize;
1155     }
1156
1157     return true;
1158   }
1159
1160   return false;
1161 }
1162
1163 /// equivalentAddressValues - Test if A and B will obviously have the same
1164 /// value. This includes recognizing that %t0 and %t1 will have the same
1165 /// value in code like this:
1166 ///   %t0 = getelementptr \@a, 0, 3
1167 ///   store i32 0, i32* %t0
1168 ///   %t1 = getelementptr \@a, 0, 3
1169 ///   %t2 = load i32* %t1
1170 ///
1171 static bool equivalentAddressValues(Value *A, Value *B) {
1172   // Test if the values are trivially equivalent.
1173   if (A == B) return true;
1174
1175   // Test if the values come form identical arithmetic instructions.
1176   // This uses isIdenticalToWhenDefined instead of isIdenticalTo because
1177   // its only used to compare two uses within the same basic block, which
1178   // means that they'll always either have the same value or one of them
1179   // will have an undefined value.
1180   if (isa<BinaryOperator>(A) ||
1181       isa<CastInst>(A) ||
1182       isa<PHINode>(A) ||
1183       isa<GetElementPtrInst>(A))
1184     if (Instruction *BI = dyn_cast<Instruction>(B))
1185       if (cast<Instruction>(A)->isIdenticalToWhenDefined(BI))
1186         return true;
1187
1188   // Otherwise they may not be equivalent.
1189   return false;
1190 }
1191
1192 Instruction *InstCombiner::visitStoreInst(StoreInst &SI) {
1193   Value *Val = SI.getOperand(0);
1194   Value *Ptr = SI.getOperand(1);
1195
1196   // Try to canonicalize the stored type.
1197   if (combineStoreToValueType(*this, SI))
1198     return eraseInstFromFunction(SI);
1199
1200   // Attempt to improve the alignment.
1201   unsigned KnownAlign = getOrEnforceKnownAlignment(
1202       Ptr, DL.getPrefTypeAlignment(Val->getType()), DL, &SI, &AC, &DT);
1203   unsigned StoreAlign = SI.getAlignment();
1204   unsigned EffectiveStoreAlign =
1205       StoreAlign != 0 ? StoreAlign : DL.getABITypeAlignment(Val->getType());
1206
1207   if (KnownAlign > EffectiveStoreAlign)
1208     SI.setAlignment(KnownAlign);
1209   else if (StoreAlign == 0)
1210     SI.setAlignment(EffectiveStoreAlign);
1211
1212   // Try to canonicalize the stored type.
1213   if (unpackStoreToAggregate(*this, SI))
1214     return eraseInstFromFunction(SI);
1215
1216   // Replace GEP indices if possible.
1217   if (Instruction *NewGEPI = replaceGEPIdxWithZero(*this, Ptr, SI)) {
1218       Worklist.Add(NewGEPI);
1219       return &SI;
1220   }
1221
1222   // Don't hack volatile/ordered stores.
1223   // FIXME: Some bits are legal for ordered atomic stores; needs refactoring.
1224   if (!SI.isUnordered()) return nullptr;
1225
1226   // If the RHS is an alloca with a single use, zapify the store, making the
1227   // alloca dead.
1228   if (Ptr->hasOneUse()) {
1229     if (isa<AllocaInst>(Ptr))
1230       return eraseInstFromFunction(SI);
1231     if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Ptr)) {
1232       if (isa<AllocaInst>(GEP->getOperand(0))) {
1233         if (GEP->getOperand(0)->hasOneUse())
1234           return eraseInstFromFunction(SI);
1235       }
1236     }
1237   }
1238
1239   // Do really simple DSE, to catch cases where there are several consecutive
1240   // stores to the same location, separated by a few arithmetic operations. This
1241   // situation often occurs with bitfield accesses.
1242   BasicBlock::iterator BBI(SI);
1243   for (unsigned ScanInsts = 6; BBI != SI.getParent()->begin() && ScanInsts;
1244        --ScanInsts) {
1245     --BBI;
1246     // Don't count debug info directives, lest they affect codegen,
1247     // and we skip pointer-to-pointer bitcasts, which are NOPs.
1248     if (isa<DbgInfoIntrinsic>(BBI) ||
1249         (isa<BitCastInst>(BBI) && BBI->getType()->isPointerTy())) {
1250       ScanInsts++;
1251       continue;
1252     }
1253
1254     if (StoreInst *PrevSI = dyn_cast<StoreInst>(BBI)) {
1255       // Prev store isn't volatile, and stores to the same location?
1256       if (PrevSI->isUnordered() && equivalentAddressValues(PrevSI->getOperand(1),
1257                                                         SI.getOperand(1))) {
1258         ++NumDeadStore;
1259         ++BBI;
1260         eraseInstFromFunction(*PrevSI);
1261         continue;
1262       }
1263       break;
1264     }
1265
1266     // If this is a load, we have to stop.  However, if the loaded value is from
1267     // the pointer we're loading and is producing the pointer we're storing,
1268     // then *this* store is dead (X = load P; store X -> P).
1269     if (LoadInst *LI = dyn_cast<LoadInst>(BBI)) {
1270       if (LI == Val && equivalentAddressValues(LI->getOperand(0), Ptr)) {
1271         assert(SI.isUnordered() && "can't eliminate ordering operation");
1272         return eraseInstFromFunction(SI);
1273       }
1274
1275       // Otherwise, this is a load from some other location.  Stores before it
1276       // may not be dead.
1277       break;
1278     }
1279
1280     // Don't skip over loads or things that can modify memory.
1281     if (BBI->mayWriteToMemory() || BBI->mayReadFromMemory())
1282       break;
1283   }
1284
1285   // store X, null    -> turns into 'unreachable' in SimplifyCFG
1286   if (isa<ConstantPointerNull>(Ptr) && SI.getPointerAddressSpace() == 0) {
1287     if (!isa<UndefValue>(Val)) {
1288       SI.setOperand(0, UndefValue::get(Val->getType()));
1289       if (Instruction *U = dyn_cast<Instruction>(Val))
1290         Worklist.Add(U);  // Dropped a use.
1291     }
1292     return nullptr;  // Do not modify these!
1293   }
1294
1295   // store undef, Ptr -> noop
1296   if (isa<UndefValue>(Val))
1297     return eraseInstFromFunction(SI);
1298
1299   // If this store is the last instruction in the basic block (possibly
1300   // excepting debug info instructions), and if the block ends with an
1301   // unconditional branch, try to move it to the successor block.
1302   BBI = SI.getIterator();
1303   do {
1304     ++BBI;
1305   } while (isa<DbgInfoIntrinsic>(BBI) ||
1306            (isa<BitCastInst>(BBI) && BBI->getType()->isPointerTy()));
1307   if (BranchInst *BI = dyn_cast<BranchInst>(BBI))
1308     if (BI->isUnconditional())
1309       if (SimplifyStoreAtEndOfBlock(SI))
1310         return nullptr;  // xform done!
1311
1312   return nullptr;
1313 }
1314
1315 /// SimplifyStoreAtEndOfBlock - Turn things like:
1316 ///   if () { *P = v1; } else { *P = v2 }
1317 /// into a phi node with a store in the successor.
1318 ///
1319 /// Simplify things like:
1320 ///   *P = v1; if () { *P = v2; }
1321 /// into a phi node with a store in the successor.
1322 ///
1323 bool InstCombiner::SimplifyStoreAtEndOfBlock(StoreInst &SI) {
1324   assert(SI.isUnordered() &&
1325          "this code has not been auditted for volatile or ordered store case");
1326
1327   BasicBlock *StoreBB = SI.getParent();
1328
1329   // Check to see if the successor block has exactly two incoming edges.  If
1330   // so, see if the other predecessor contains a store to the same location.
1331   // if so, insert a PHI node (if needed) and move the stores down.
1332   BasicBlock *DestBB = StoreBB->getTerminator()->getSuccessor(0);
1333
1334   // Determine whether Dest has exactly two predecessors and, if so, compute
1335   // the other predecessor.
1336   pred_iterator PI = pred_begin(DestBB);
1337   BasicBlock *P = *PI;
1338   BasicBlock *OtherBB = nullptr;
1339
1340   if (P != StoreBB)
1341     OtherBB = P;
1342
1343   if (++PI == pred_end(DestBB))
1344     return false;
1345
1346   P = *PI;
1347   if (P != StoreBB) {
1348     if (OtherBB)
1349       return false;
1350     OtherBB = P;
1351   }
1352   if (++PI != pred_end(DestBB))
1353     return false;
1354
1355   // Bail out if all the relevant blocks aren't distinct (this can happen,
1356   // for example, if SI is in an infinite loop)
1357   if (StoreBB == DestBB || OtherBB == DestBB)
1358     return false;
1359
1360   // Verify that the other block ends in a branch and is not otherwise empty.
1361   BasicBlock::iterator BBI(OtherBB->getTerminator());
1362   BranchInst *OtherBr = dyn_cast<BranchInst>(BBI);
1363   if (!OtherBr || BBI == OtherBB->begin())
1364     return false;
1365
1366   // If the other block ends in an unconditional branch, check for the 'if then
1367   // else' case.  there is an instruction before the branch.
1368   StoreInst *OtherStore = nullptr;
1369   if (OtherBr->isUnconditional()) {
1370     --BBI;
1371     // Skip over debugging info.
1372     while (isa<DbgInfoIntrinsic>(BBI) ||
1373            (isa<BitCastInst>(BBI) && BBI->getType()->isPointerTy())) {
1374       if (BBI==OtherBB->begin())
1375         return false;
1376       --BBI;
1377     }
1378     // If this isn't a store, isn't a store to the same location, or is not the
1379     // right kind of store, bail out.
1380     OtherStore = dyn_cast<StoreInst>(BBI);
1381     if (!OtherStore || OtherStore->getOperand(1) != SI.getOperand(1) ||
1382         !SI.isSameOperationAs(OtherStore))
1383       return false;
1384   } else {
1385     // Otherwise, the other block ended with a conditional branch. If one of the
1386     // destinations is StoreBB, then we have the if/then case.
1387     if (OtherBr->getSuccessor(0) != StoreBB &&
1388         OtherBr->getSuccessor(1) != StoreBB)
1389       return false;
1390
1391     // Okay, we know that OtherBr now goes to Dest and StoreBB, so this is an
1392     // if/then triangle.  See if there is a store to the same ptr as SI that
1393     // lives in OtherBB.
1394     for (;; --BBI) {
1395       // Check to see if we find the matching store.
1396       if ((OtherStore = dyn_cast<StoreInst>(BBI))) {
1397         if (OtherStore->getOperand(1) != SI.getOperand(1) ||
1398             !SI.isSameOperationAs(OtherStore))
1399           return false;
1400         break;
1401       }
1402       // If we find something that may be using or overwriting the stored
1403       // value, or if we run out of instructions, we can't do the xform.
1404       if (BBI->mayReadFromMemory() || BBI->mayWriteToMemory() ||
1405           BBI == OtherBB->begin())
1406         return false;
1407     }
1408
1409     // In order to eliminate the store in OtherBr, we have to
1410     // make sure nothing reads or overwrites the stored value in
1411     // StoreBB.
1412     for (BasicBlock::iterator I = StoreBB->begin(); &*I != &SI; ++I) {
1413       // FIXME: This should really be AA driven.
1414       if (I->mayReadFromMemory() || I->mayWriteToMemory())
1415         return false;
1416     }
1417   }
1418
1419   // Insert a PHI node now if we need it.
1420   Value *MergedVal = OtherStore->getOperand(0);
1421   if (MergedVal != SI.getOperand(0)) {
1422     PHINode *PN = PHINode::Create(MergedVal->getType(), 2, "storemerge");
1423     PN->addIncoming(SI.getOperand(0), SI.getParent());
1424     PN->addIncoming(OtherStore->getOperand(0), OtherBB);
1425     MergedVal = InsertNewInstBefore(PN, DestBB->front());
1426   }
1427
1428   // Advance to a place where it is safe to insert the new store and
1429   // insert it.
1430   BBI = DestBB->getFirstInsertionPt();
1431   StoreInst *NewSI = new StoreInst(MergedVal, SI.getOperand(1),
1432                                    SI.isVolatile(),
1433                                    SI.getAlignment(),
1434                                    SI.getOrdering(),
1435                                    SI.getSynchScope());
1436   InsertNewInstBefore(NewSI, *BBI);
1437   NewSI->setDebugLoc(OtherStore->getDebugLoc());
1438
1439   // If the two stores had AA tags, merge them.
1440   AAMDNodes AATags;
1441   SI.getAAMetadata(AATags);
1442   if (AATags) {
1443     OtherStore->getAAMetadata(AATags, /* Merge = */ true);
1444     NewSI->setAAMetadata(AATags);
1445   }
1446
1447   // Nuke the old stores.
1448   eraseInstFromFunction(SI);
1449   eraseInstFromFunction(*OtherStore);
1450   return true;
1451 }