9c69b6c755874f49b013d528a8650795e76bbb4c
[oota-llvm.git] / lib / Transforms / Scalar / SROA.cpp
1 //===- SROA.cpp - Scalar Replacement Of Aggregates ------------------------===//
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 /// \file
10 /// This transformation implements the well known scalar replacement of
11 /// aggregates transformation. It tries to identify promotable elements of an
12 /// aggregate alloca, and promote them to registers. It will also try to
13 /// convert uses of an element (or set of elements) of an alloca into a vector
14 /// or bitfield-style integer scalar if appropriate.
15 ///
16 /// It works to do this with minimal slicing of the alloca so that regions
17 /// which are merely transferred in and out of external memory remain unchanged
18 /// and are not decomposed to scalar code.
19 ///
20 /// Because this also performs alloca promotion, it can be thought of as also
21 /// serving the purpose of SSA formation. The algorithm iterates on the
22 /// function until all opportunities for promotion have been realized.
23 ///
24 //===----------------------------------------------------------------------===//
25
26 #include "llvm/Transforms/Scalar.h"
27 #include "llvm/ADT/STLExtras.h"
28 #include "llvm/ADT/SetVector.h"
29 #include "llvm/ADT/SmallVector.h"
30 #include "llvm/ADT/Statistic.h"
31 #include "llvm/Analysis/AssumptionCache.h"
32 #include "llvm/Analysis/Loads.h"
33 #include "llvm/Analysis/PtrUseVisitor.h"
34 #include "llvm/Analysis/ValueTracking.h"
35 #include "llvm/IR/Constants.h"
36 #include "llvm/IR/DIBuilder.h"
37 #include "llvm/IR/DataLayout.h"
38 #include "llvm/IR/DebugInfo.h"
39 #include "llvm/IR/DerivedTypes.h"
40 #include "llvm/IR/Dominators.h"
41 #include "llvm/IR/Function.h"
42 #include "llvm/IR/IRBuilder.h"
43 #include "llvm/IR/InstVisitor.h"
44 #include "llvm/IR/Instructions.h"
45 #include "llvm/IR/IntrinsicInst.h"
46 #include "llvm/IR/LLVMContext.h"
47 #include "llvm/IR/Operator.h"
48 #include "llvm/Pass.h"
49 #include "llvm/Support/CommandLine.h"
50 #include "llvm/Support/Compiler.h"
51 #include "llvm/Support/Debug.h"
52 #include "llvm/Support/ErrorHandling.h"
53 #include "llvm/Support/MathExtras.h"
54 #include "llvm/Support/TimeValue.h"
55 #include "llvm/Support/raw_ostream.h"
56 #include "llvm/Transforms/Utils/Local.h"
57 #include "llvm/Transforms/Utils/PromoteMemToReg.h"
58 #include "llvm/Transforms/Utils/SSAUpdater.h"
59
60 #if __cplusplus >= 201103L && !defined(NDEBUG)
61 // We only use this for a debug check in C++11
62 #include <random>
63 #endif
64
65 using namespace llvm;
66
67 #define DEBUG_TYPE "sroa"
68
69 STATISTIC(NumAllocasAnalyzed, "Number of allocas analyzed for replacement");
70 STATISTIC(NumAllocaPartitions, "Number of alloca partitions formed");
71 STATISTIC(MaxPartitionsPerAlloca, "Maximum number of partitions per alloca");
72 STATISTIC(NumAllocaPartitionUses, "Number of alloca partition uses rewritten");
73 STATISTIC(MaxUsesPerAllocaPartition, "Maximum number of uses of a partition");
74 STATISTIC(NumNewAllocas, "Number of new, smaller allocas introduced");
75 STATISTIC(NumPromoted, "Number of allocas promoted to SSA values");
76 STATISTIC(NumLoadsSpeculated, "Number of loads speculated to allow promotion");
77 STATISTIC(NumDeleted, "Number of instructions deleted");
78 STATISTIC(NumVectorized, "Number of vectorized aggregates");
79
80 /// Hidden option to force the pass to not use DomTree and mem2reg, instead
81 /// forming SSA values through the SSAUpdater infrastructure.
82 static cl::opt<bool> ForceSSAUpdater("force-ssa-updater", cl::init(false),
83                                      cl::Hidden);
84
85 /// Hidden option to enable randomly shuffling the slices to help uncover
86 /// instability in their order.
87 static cl::opt<bool> SROARandomShuffleSlices("sroa-random-shuffle-slices",
88                                              cl::init(false), cl::Hidden);
89
90 /// Hidden option to experiment with completely strict handling of inbounds
91 /// GEPs.
92 static cl::opt<bool> SROAStrictInbounds("sroa-strict-inbounds", cl::init(false),
93                                         cl::Hidden);
94
95 namespace {
96 /// \brief A custom IRBuilder inserter which prefixes all names if they are
97 /// preserved.
98 template <bool preserveNames = true>
99 class IRBuilderPrefixedInserter
100     : public IRBuilderDefaultInserter<preserveNames> {
101   std::string Prefix;
102
103 public:
104   void SetNamePrefix(const Twine &P) { Prefix = P.str(); }
105
106 protected:
107   void InsertHelper(Instruction *I, const Twine &Name, BasicBlock *BB,
108                     BasicBlock::iterator InsertPt) const {
109     IRBuilderDefaultInserter<preserveNames>::InsertHelper(
110         I, Name.isTriviallyEmpty() ? Name : Prefix + Name, BB, InsertPt);
111   }
112 };
113
114 // Specialization for not preserving the name is trivial.
115 template <>
116 class IRBuilderPrefixedInserter<false>
117     : public IRBuilderDefaultInserter<false> {
118 public:
119   void SetNamePrefix(const Twine &P) {}
120 };
121
122 /// \brief Provide a typedef for IRBuilder that drops names in release builds.
123 #ifndef NDEBUG
124 typedef llvm::IRBuilder<true, ConstantFolder, IRBuilderPrefixedInserter<true>>
125     IRBuilderTy;
126 #else
127 typedef llvm::IRBuilder<false, ConstantFolder, IRBuilderPrefixedInserter<false>>
128     IRBuilderTy;
129 #endif
130 }
131
132 namespace {
133 /// \brief A used slice of an alloca.
134 ///
135 /// This structure represents a slice of an alloca used by some instruction. It
136 /// stores both the begin and end offsets of this use, a pointer to the use
137 /// itself, and a flag indicating whether we can classify the use as splittable
138 /// or not when forming partitions of the alloca.
139 class Slice {
140   /// \brief The beginning offset of the range.
141   uint64_t BeginOffset;
142
143   /// \brief The ending offset, not included in the range.
144   uint64_t EndOffset;
145
146   /// \brief Storage for both the use of this slice and whether it can be
147   /// split.
148   PointerIntPair<Use *, 1, bool> UseAndIsSplittable;
149
150 public:
151   Slice() : BeginOffset(), EndOffset() {}
152   Slice(uint64_t BeginOffset, uint64_t EndOffset, Use *U, bool IsSplittable)
153       : BeginOffset(BeginOffset), EndOffset(EndOffset),
154         UseAndIsSplittable(U, IsSplittable) {}
155
156   uint64_t beginOffset() const { return BeginOffset; }
157   uint64_t endOffset() const { return EndOffset; }
158
159   bool isSplittable() const { return UseAndIsSplittable.getInt(); }
160   void makeUnsplittable() { UseAndIsSplittable.setInt(false); }
161
162   Use *getUse() const { return UseAndIsSplittable.getPointer(); }
163
164   bool isDead() const { return getUse() == nullptr; }
165   void kill() { UseAndIsSplittable.setPointer(nullptr); }
166
167   /// \brief Support for ordering ranges.
168   ///
169   /// This provides an ordering over ranges such that start offsets are
170   /// always increasing, and within equal start offsets, the end offsets are
171   /// decreasing. Thus the spanning range comes first in a cluster with the
172   /// same start position.
173   bool operator<(const Slice &RHS) const {
174     if (beginOffset() < RHS.beginOffset())
175       return true;
176     if (beginOffset() > RHS.beginOffset())
177       return false;
178     if (isSplittable() != RHS.isSplittable())
179       return !isSplittable();
180     if (endOffset() > RHS.endOffset())
181       return true;
182     return false;
183   }
184
185   /// \brief Support comparison with a single offset to allow binary searches.
186   friend LLVM_ATTRIBUTE_UNUSED bool operator<(const Slice &LHS,
187                                               uint64_t RHSOffset) {
188     return LHS.beginOffset() < RHSOffset;
189   }
190   friend LLVM_ATTRIBUTE_UNUSED bool operator<(uint64_t LHSOffset,
191                                               const Slice &RHS) {
192     return LHSOffset < RHS.beginOffset();
193   }
194
195   bool operator==(const Slice &RHS) const {
196     return isSplittable() == RHS.isSplittable() &&
197            beginOffset() == RHS.beginOffset() && endOffset() == RHS.endOffset();
198   }
199   bool operator!=(const Slice &RHS) const { return !operator==(RHS); }
200 };
201 } // end anonymous namespace
202
203 namespace llvm {
204 template <typename T> struct isPodLike;
205 template <> struct isPodLike<Slice> { static const bool value = true; };
206 }
207
208 namespace {
209 /// \brief Representation of the alloca slices.
210 ///
211 /// This class represents the slices of an alloca which are formed by its
212 /// various uses. If a pointer escapes, we can't fully build a representation
213 /// for the slices used and we reflect that in this structure. The uses are
214 /// stored, sorted by increasing beginning offset and with unsplittable slices
215 /// starting at a particular offset before splittable slices.
216 class AllocaSlices {
217 public:
218   /// \brief Construct the slices of a particular alloca.
219   AllocaSlices(const DataLayout &DL, AllocaInst &AI);
220
221   /// \brief Test whether a pointer to the allocation escapes our analysis.
222   ///
223   /// If this is true, the slices are never fully built and should be
224   /// ignored.
225   bool isEscaped() const { return PointerEscapingInstr; }
226
227   /// \brief Support for iterating over the slices.
228   /// @{
229   typedef SmallVectorImpl<Slice>::iterator iterator;
230   typedef iterator_range<iterator> range;
231   iterator begin() { return Slices.begin(); }
232   iterator end() { return Slices.end(); }
233
234   typedef SmallVectorImpl<Slice>::const_iterator const_iterator;
235   typedef iterator_range<const_iterator> const_range;
236   const_iterator begin() const { return Slices.begin(); }
237   const_iterator end() const { return Slices.end(); }
238   /// @}
239
240   /// \brief Erase a range of slices.
241   void erase(iterator Start, iterator Stop) { Slices.erase(Start, Stop); }
242
243   /// \brief Insert new slices for this alloca.
244   ///
245   /// This moves the slices into the alloca's slices collection, and re-sorts
246   /// everything so that the usual ordering properties of the alloca's slices
247   /// hold.
248   void insert(ArrayRef<Slice> NewSlices) {
249     int OldSize = Slices.size();
250     Slices.append(NewSlices.begin(), NewSlices.end());
251     auto SliceI = Slices.begin() + OldSize;
252     std::sort(SliceI, Slices.end());
253     std::inplace_merge(Slices.begin(), SliceI, Slices.end());
254   }
255
256   // Forward declare an iterator to befriend it.
257   class partition_iterator;
258
259   /// \brief A partition of the slices.
260   ///
261   /// An ephemeral representation for a range of slices which can be viewed as
262   /// a partition of the alloca. This range represents a span of the alloca's
263   /// memory which cannot be split, and provides access to all of the slices
264   /// overlapping some part of the partition.
265   ///
266   /// Objects of this type are produced by traversing the alloca's slices, but
267   /// are only ephemeral and not persistent.
268   class Partition {
269   private:
270     friend class AllocaSlices;
271     friend class AllocaSlices::partition_iterator;
272
273     /// \brief The beginning and ending offsets of the alloca for this
274     /// partition.
275     uint64_t BeginOffset, EndOffset;
276
277     /// \brief The start end end iterators of this partition.
278     iterator SI, SJ;
279
280     /// \brief A collection of split slice tails overlapping the partition.
281     SmallVector<Slice *, 4> SplitTails;
282
283     /// \brief Raw constructor builds an empty partition starting and ending at
284     /// the given iterator.
285     Partition(iterator SI) : SI(SI), SJ(SI) {}
286
287   public:
288     /// \brief The start offset of this partition.
289     ///
290     /// All of the contained slices start at or after this offset.
291     uint64_t beginOffset() const { return BeginOffset; }
292
293     /// \brief The end offset of this partition.
294     ///
295     /// All of the contained slices end at or before this offset.
296     uint64_t endOffset() const { return EndOffset; }
297
298     /// \brief The size of the partition.
299     ///
300     /// Note that this can never be zero.
301     uint64_t size() const {
302       assert(BeginOffset < EndOffset && "Partitions must span some bytes!");
303       return EndOffset - BeginOffset;
304     }
305
306     /// \brief Test whether this partition contains no slices, and merely spans
307     /// a region occupied by split slices.
308     bool empty() const { return SI == SJ; }
309
310     /// \name Iterate slices that start within the partition.
311     /// These may be splittable or unsplittable. They have a begin offset >= the
312     /// partition begin offset.
313     /// @{
314     // FIXME: We should probably define a "concat_iterator" helper and use that
315     // to stitch together pointee_iterators over the split tails and the
316     // contiguous iterators of the partition. That would give a much nicer
317     // interface here. We could then additionally expose filtered iterators for
318     // split, unsplit, and unsplittable splices based on the usage patterns.
319     iterator begin() const { return SI; }
320     iterator end() const { return SJ; }
321     /// @}
322
323     /// \brief Get the sequence of split slice tails.
324     ///
325     /// These tails are of slices which start before this partition but are
326     /// split and overlap into the partition. We accumulate these while forming
327     /// partitions.
328     ArrayRef<Slice *> splitSliceTails() const { return SplitTails; }
329   };
330
331   /// \brief An iterator over partitions of the alloca's slices.
332   ///
333   /// This iterator implements the core algorithm for partitioning the alloca's
334   /// slices. It is a forward iterator as we don't support backtracking for
335   /// efficiency reasons, and re-use a single storage area to maintain the
336   /// current set of split slices.
337   ///
338   /// It is templated on the slice iterator type to use so that it can operate
339   /// with either const or non-const slice iterators.
340   class partition_iterator
341       : public iterator_facade_base<partition_iterator,
342                                     std::forward_iterator_tag, Partition> {
343     friend class AllocaSlices;
344
345     /// \brief Most of the state for walking the partitions is held in a class
346     /// with a nice interface for examining them.
347     Partition P;
348
349     /// \brief We need to keep the end of the slices to know when to stop.
350     AllocaSlices::iterator SE;
351
352     /// \brief We also need to keep track of the maximum split end offset seen.
353     /// FIXME: Do we really?
354     uint64_t MaxSplitSliceEndOffset;
355
356     /// \brief Sets the partition to be empty at given iterator, and sets the
357     /// end iterator.
358     partition_iterator(AllocaSlices::iterator SI, AllocaSlices::iterator SE)
359         : P(SI), SE(SE), MaxSplitSliceEndOffset(0) {
360       // If not already at the end, advance our state to form the initial
361       // partition.
362       if (SI != SE)
363         advance();
364     }
365
366     /// \brief Advance the iterator to the next partition.
367     ///
368     /// Requires that the iterator not be at the end of the slices.
369     void advance() {
370       assert((P.SI != SE || !P.SplitTails.empty()) &&
371              "Cannot advance past the end of the slices!");
372
373       // Clear out any split uses which have ended.
374       if (!P.SplitTails.empty()) {
375         if (P.EndOffset >= MaxSplitSliceEndOffset) {
376           // If we've finished all splits, this is easy.
377           P.SplitTails.clear();
378           MaxSplitSliceEndOffset = 0;
379         } else {
380           // Remove the uses which have ended in the prior partition. This
381           // cannot change the max split slice end because we just checked that
382           // the prior partition ended prior to that max.
383           P.SplitTails.erase(
384               std::remove_if(
385                   P.SplitTails.begin(), P.SplitTails.end(),
386                   [&](Slice *S) { return S->endOffset() <= P.EndOffset; }),
387               P.SplitTails.end());
388           assert(std::any_of(P.SplitTails.begin(), P.SplitTails.end(),
389                              [&](Slice *S) {
390                                return S->endOffset() == MaxSplitSliceEndOffset;
391                              }) &&
392                  "Could not find the current max split slice offset!");
393           assert(std::all_of(P.SplitTails.begin(), P.SplitTails.end(),
394                              [&](Slice *S) {
395                                return S->endOffset() <= MaxSplitSliceEndOffset;
396                              }) &&
397                  "Max split slice end offset is not actually the max!");
398         }
399       }
400
401       // If P.SI is already at the end, then we've cleared the split tail and
402       // now have an end iterator.
403       if (P.SI == SE) {
404         assert(P.SplitTails.empty() && "Failed to clear the split slices!");
405         return;
406       }
407
408       // If we had a non-empty partition previously, set up the state for
409       // subsequent partitions.
410       if (P.SI != P.SJ) {
411         // Accumulate all the splittable slices which started in the old
412         // partition into the split list.
413         for (Slice &S : P)
414           if (S.isSplittable() && S.endOffset() > P.EndOffset) {
415             P.SplitTails.push_back(&S);
416             MaxSplitSliceEndOffset =
417                 std::max(S.endOffset(), MaxSplitSliceEndOffset);
418           }
419
420         // Start from the end of the previous partition.
421         P.SI = P.SJ;
422
423         // If P.SI is now at the end, we at most have a tail of split slices.
424         if (P.SI == SE) {
425           P.BeginOffset = P.EndOffset;
426           P.EndOffset = MaxSplitSliceEndOffset;
427           return;
428         }
429
430         // If the we have split slices and the next slice is after a gap and is
431         // not splittable immediately form an empty partition for the split
432         // slices up until the next slice begins.
433         if (!P.SplitTails.empty() && P.SI->beginOffset() != P.EndOffset &&
434             !P.SI->isSplittable()) {
435           P.BeginOffset = P.EndOffset;
436           P.EndOffset = P.SI->beginOffset();
437           return;
438         }
439       }
440
441       // OK, we need to consume new slices. Set the end offset based on the
442       // current slice, and step SJ past it. The beginning offset of the
443       // partition is the beginning offset of the next slice unless we have
444       // pre-existing split slices that are continuing, in which case we begin
445       // at the prior end offset.
446       P.BeginOffset = P.SplitTails.empty() ? P.SI->beginOffset() : P.EndOffset;
447       P.EndOffset = P.SI->endOffset();
448       ++P.SJ;
449
450       // There are two strategies to form a partition based on whether the
451       // partition starts with an unsplittable slice or a splittable slice.
452       if (!P.SI->isSplittable()) {
453         // When we're forming an unsplittable region, it must always start at
454         // the first slice and will extend through its end.
455         assert(P.BeginOffset == P.SI->beginOffset());
456
457         // Form a partition including all of the overlapping slices with this
458         // unsplittable slice.
459         while (P.SJ != SE && P.SJ->beginOffset() < P.EndOffset) {
460           if (!P.SJ->isSplittable())
461             P.EndOffset = std::max(P.EndOffset, P.SJ->endOffset());
462           ++P.SJ;
463         }
464
465         // We have a partition across a set of overlapping unsplittable
466         // partitions.
467         return;
468       }
469
470       // If we're starting with a splittable slice, then we need to form
471       // a synthetic partition spanning it and any other overlapping splittable
472       // splices.
473       assert(P.SI->isSplittable() && "Forming a splittable partition!");
474
475       // Collect all of the overlapping splittable slices.
476       while (P.SJ != SE && P.SJ->beginOffset() < P.EndOffset &&
477              P.SJ->isSplittable()) {
478         P.EndOffset = std::max(P.EndOffset, P.SJ->endOffset());
479         ++P.SJ;
480       }
481
482       // Back upiP.EndOffset if we ended the span early when encountering an
483       // unsplittable slice. This synthesizes the early end offset of
484       // a partition spanning only splittable slices.
485       if (P.SJ != SE && P.SJ->beginOffset() < P.EndOffset) {
486         assert(!P.SJ->isSplittable());
487         P.EndOffset = P.SJ->beginOffset();
488       }
489     }
490
491   public:
492     bool operator==(const partition_iterator &RHS) const {
493       assert(SE == RHS.SE &&
494              "End iterators don't match between compared partition iterators!");
495
496       // The observed positions of partitions is marked by the P.SI iterator and
497       // the emptiness of the split slices. The latter is only relevant when
498       // P.SI == SE, as the end iterator will additionally have an empty split
499       // slices list, but the prior may have the same P.SI and a tail of split
500       // slices.
501       if (P.SI == RHS.P.SI &&
502           P.SplitTails.empty() == RHS.P.SplitTails.empty()) {
503         assert(P.SJ == RHS.P.SJ &&
504                "Same set of slices formed two different sized partitions!");
505         assert(P.SplitTails.size() == RHS.P.SplitTails.size() &&
506                "Same slice position with differently sized non-empty split "
507                "slice tails!");
508         return true;
509       }
510       return false;
511     }
512
513     partition_iterator &operator++() {
514       advance();
515       return *this;
516     }
517
518     Partition &operator*() { return P; }
519   };
520
521   /// \brief A forward range over the partitions of the alloca's slices.
522   ///
523   /// This accesses an iterator range over the partitions of the alloca's
524   /// slices. It computes these partitions on the fly based on the overlapping
525   /// offsets of the slices and the ability to split them. It will visit "empty"
526   /// partitions to cover regions of the alloca only accessed via split
527   /// slices.
528   iterator_range<partition_iterator> partitions() {
529     return make_range(partition_iterator(begin(), end()),
530                       partition_iterator(end(), end()));
531   }
532
533   /// \brief Access the dead users for this alloca.
534   ArrayRef<Instruction *> getDeadUsers() const { return DeadUsers; }
535
536   /// \brief Access the dead operands referring to this alloca.
537   ///
538   /// These are operands which have cannot actually be used to refer to the
539   /// alloca as they are outside its range and the user doesn't correct for
540   /// that. These mostly consist of PHI node inputs and the like which we just
541   /// need to replace with undef.
542   ArrayRef<Use *> getDeadOperands() const { return DeadOperands; }
543
544 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
545   void print(raw_ostream &OS, const_iterator I, StringRef Indent = "  ") const;
546   void printSlice(raw_ostream &OS, const_iterator I,
547                   StringRef Indent = "  ") const;
548   void printUse(raw_ostream &OS, const_iterator I,
549                 StringRef Indent = "  ") const;
550   void print(raw_ostream &OS) const;
551   void dump(const_iterator I) const;
552   void dump() const;
553 #endif
554
555 private:
556   template <typename DerivedT, typename RetT = void> class BuilderBase;
557   class SliceBuilder;
558   friend class AllocaSlices::SliceBuilder;
559
560 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
561   /// \brief Handle to alloca instruction to simplify method interfaces.
562   AllocaInst &AI;
563 #endif
564
565   /// \brief The instruction responsible for this alloca not having a known set
566   /// of slices.
567   ///
568   /// When an instruction (potentially) escapes the pointer to the alloca, we
569   /// store a pointer to that here and abort trying to form slices of the
570   /// alloca. This will be null if the alloca slices are analyzed successfully.
571   Instruction *PointerEscapingInstr;
572
573   /// \brief The slices of the alloca.
574   ///
575   /// We store a vector of the slices formed by uses of the alloca here. This
576   /// vector is sorted by increasing begin offset, and then the unsplittable
577   /// slices before the splittable ones. See the Slice inner class for more
578   /// details.
579   SmallVector<Slice, 8> Slices;
580
581   /// \brief Instructions which will become dead if we rewrite the alloca.
582   ///
583   /// Note that these are not separated by slice. This is because we expect an
584   /// alloca to be completely rewritten or not rewritten at all. If rewritten,
585   /// all these instructions can simply be removed and replaced with undef as
586   /// they come from outside of the allocated space.
587   SmallVector<Instruction *, 8> DeadUsers;
588
589   /// \brief Operands which will become dead if we rewrite the alloca.
590   ///
591   /// These are operands that in their particular use can be replaced with
592   /// undef when we rewrite the alloca. These show up in out-of-bounds inputs
593   /// to PHI nodes and the like. They aren't entirely dead (there might be
594   /// a GEP back into the bounds using it elsewhere) and nor is the PHI, but we
595   /// want to swap this particular input for undef to simplify the use lists of
596   /// the alloca.
597   SmallVector<Use *, 8> DeadOperands;
598 };
599 }
600
601 static Value *foldSelectInst(SelectInst &SI) {
602   // If the condition being selected on is a constant or the same value is
603   // being selected between, fold the select. Yes this does (rarely) happen
604   // early on.
605   if (ConstantInt *CI = dyn_cast<ConstantInt>(SI.getCondition()))
606     return SI.getOperand(1 + CI->isZero());
607   if (SI.getOperand(1) == SI.getOperand(2))
608     return SI.getOperand(1);
609
610   return nullptr;
611 }
612
613 /// \brief A helper that folds a PHI node or a select.
614 static Value *foldPHINodeOrSelectInst(Instruction &I) {
615   if (PHINode *PN = dyn_cast<PHINode>(&I)) {
616     // If PN merges together the same value, return that value.
617     return PN->hasConstantValue();
618   }
619   return foldSelectInst(cast<SelectInst>(I));
620 }
621
622 /// \brief Builder for the alloca slices.
623 ///
624 /// This class builds a set of alloca slices by recursively visiting the uses
625 /// of an alloca and making a slice for each load and store at each offset.
626 class AllocaSlices::SliceBuilder : public PtrUseVisitor<SliceBuilder> {
627   friend class PtrUseVisitor<SliceBuilder>;
628   friend class InstVisitor<SliceBuilder>;
629   typedef PtrUseVisitor<SliceBuilder> Base;
630
631   const uint64_t AllocSize;
632   AllocaSlices &AS;
633
634   SmallDenseMap<Instruction *, unsigned> MemTransferSliceMap;
635   SmallDenseMap<Instruction *, uint64_t> PHIOrSelectSizes;
636
637   /// \brief Set to de-duplicate dead instructions found in the use walk.
638   SmallPtrSet<Instruction *, 4> VisitedDeadInsts;
639
640 public:
641   SliceBuilder(const DataLayout &DL, AllocaInst &AI, AllocaSlices &AS)
642       : PtrUseVisitor<SliceBuilder>(DL),
643         AllocSize(DL.getTypeAllocSize(AI.getAllocatedType())), AS(AS) {}
644
645 private:
646   void markAsDead(Instruction &I) {
647     if (VisitedDeadInsts.insert(&I).second)
648       AS.DeadUsers.push_back(&I);
649   }
650
651   void insertUse(Instruction &I, const APInt &Offset, uint64_t Size,
652                  bool IsSplittable = false) {
653     // Completely skip uses which have a zero size or start either before or
654     // past the end of the allocation.
655     if (Size == 0 || Offset.uge(AllocSize)) {
656       DEBUG(dbgs() << "WARNING: Ignoring " << Size << " byte use @" << Offset
657                    << " which has zero size or starts outside of the "
658                    << AllocSize << " byte alloca:\n"
659                    << "    alloca: " << AS.AI << "\n"
660                    << "       use: " << I << "\n");
661       return markAsDead(I);
662     }
663
664     uint64_t BeginOffset = Offset.getZExtValue();
665     uint64_t EndOffset = BeginOffset + Size;
666
667     // Clamp the end offset to the end of the allocation. Note that this is
668     // formulated to handle even the case where "BeginOffset + Size" overflows.
669     // This may appear superficially to be something we could ignore entirely,
670     // but that is not so! There may be widened loads or PHI-node uses where
671     // some instructions are dead but not others. We can't completely ignore
672     // them, and so have to record at least the information here.
673     assert(AllocSize >= BeginOffset); // Established above.
674     if (Size > AllocSize - BeginOffset) {
675       DEBUG(dbgs() << "WARNING: Clamping a " << Size << " byte use @" << Offset
676                    << " to remain within the " << AllocSize << " byte alloca:\n"
677                    << "    alloca: " << AS.AI << "\n"
678                    << "       use: " << I << "\n");
679       EndOffset = AllocSize;
680     }
681
682     AS.Slices.push_back(Slice(BeginOffset, EndOffset, U, IsSplittable));
683   }
684
685   void visitBitCastInst(BitCastInst &BC) {
686     if (BC.use_empty())
687       return markAsDead(BC);
688
689     return Base::visitBitCastInst(BC);
690   }
691
692   void visitGetElementPtrInst(GetElementPtrInst &GEPI) {
693     if (GEPI.use_empty())
694       return markAsDead(GEPI);
695
696     if (SROAStrictInbounds && GEPI.isInBounds()) {
697       // FIXME: This is a manually un-factored variant of the basic code inside
698       // of GEPs with checking of the inbounds invariant specified in the
699       // langref in a very strict sense. If we ever want to enable
700       // SROAStrictInbounds, this code should be factored cleanly into
701       // PtrUseVisitor, but it is easier to experiment with SROAStrictInbounds
702       // by writing out the code here where we have tho underlying allocation
703       // size readily available.
704       APInt GEPOffset = Offset;
705       const DataLayout &DL = GEPI.getModule()->getDataLayout();
706       for (gep_type_iterator GTI = gep_type_begin(GEPI),
707                              GTE = gep_type_end(GEPI);
708            GTI != GTE; ++GTI) {
709         ConstantInt *OpC = dyn_cast<ConstantInt>(GTI.getOperand());
710         if (!OpC)
711           break;
712
713         // Handle a struct index, which adds its field offset to the pointer.
714         if (StructType *STy = dyn_cast<StructType>(*GTI)) {
715           unsigned ElementIdx = OpC->getZExtValue();
716           const StructLayout *SL = DL.getStructLayout(STy);
717           GEPOffset +=
718               APInt(Offset.getBitWidth(), SL->getElementOffset(ElementIdx));
719         } else {
720           // For array or vector indices, scale the index by the size of the
721           // type.
722           APInt Index = OpC->getValue().sextOrTrunc(Offset.getBitWidth());
723           GEPOffset += Index * APInt(Offset.getBitWidth(),
724                                      DL.getTypeAllocSize(GTI.getIndexedType()));
725         }
726
727         // If this index has computed an intermediate pointer which is not
728         // inbounds, then the result of the GEP is a poison value and we can
729         // delete it and all uses.
730         if (GEPOffset.ugt(AllocSize))
731           return markAsDead(GEPI);
732       }
733     }
734
735     return Base::visitGetElementPtrInst(GEPI);
736   }
737
738   void handleLoadOrStore(Type *Ty, Instruction &I, const APInt &Offset,
739                          uint64_t Size, bool IsVolatile) {
740     // We allow splitting of non-volatile loads and stores where the type is an
741     // integer type. These may be used to implement 'memcpy' or other "transfer
742     // of bits" patterns.
743     bool IsSplittable = Ty->isIntegerTy() && !IsVolatile;
744
745     insertUse(I, Offset, Size, IsSplittable);
746   }
747
748   void visitLoadInst(LoadInst &LI) {
749     assert((!LI.isSimple() || LI.getType()->isSingleValueType()) &&
750            "All simple FCA loads should have been pre-split");
751
752     if (!IsOffsetKnown)
753       return PI.setAborted(&LI);
754
755     const DataLayout &DL = LI.getModule()->getDataLayout();
756     uint64_t Size = DL.getTypeStoreSize(LI.getType());
757     return handleLoadOrStore(LI.getType(), LI, Offset, Size, LI.isVolatile());
758   }
759
760   void visitStoreInst(StoreInst &SI) {
761     Value *ValOp = SI.getValueOperand();
762     if (ValOp == *U)
763       return PI.setEscapedAndAborted(&SI);
764     if (!IsOffsetKnown)
765       return PI.setAborted(&SI);
766
767     const DataLayout &DL = SI.getModule()->getDataLayout();
768     uint64_t Size = DL.getTypeStoreSize(ValOp->getType());
769
770     // If this memory access can be shown to *statically* extend outside the
771     // bounds of of the allocation, it's behavior is undefined, so simply
772     // ignore it. Note that this is more strict than the generic clamping
773     // behavior of insertUse. We also try to handle cases which might run the
774     // risk of overflow.
775     // FIXME: We should instead consider the pointer to have escaped if this
776     // function is being instrumented for addressing bugs or race conditions.
777     if (Size > AllocSize || Offset.ugt(AllocSize - Size)) {
778       DEBUG(dbgs() << "WARNING: Ignoring " << Size << " byte store @" << Offset
779                    << " which extends past the end of the " << AllocSize
780                    << " byte alloca:\n"
781                    << "    alloca: " << AS.AI << "\n"
782                    << "       use: " << SI << "\n");
783       return markAsDead(SI);
784     }
785
786     assert((!SI.isSimple() || ValOp->getType()->isSingleValueType()) &&
787            "All simple FCA stores should have been pre-split");
788     handleLoadOrStore(ValOp->getType(), SI, Offset, Size, SI.isVolatile());
789   }
790
791   void visitMemSetInst(MemSetInst &II) {
792     assert(II.getRawDest() == *U && "Pointer use is not the destination?");
793     ConstantInt *Length = dyn_cast<ConstantInt>(II.getLength());
794     if ((Length && Length->getValue() == 0) ||
795         (IsOffsetKnown && Offset.uge(AllocSize)))
796       // Zero-length mem transfer intrinsics can be ignored entirely.
797       return markAsDead(II);
798
799     if (!IsOffsetKnown)
800       return PI.setAborted(&II);
801
802     insertUse(II, Offset, Length ? Length->getLimitedValue()
803                                  : AllocSize - Offset.getLimitedValue(),
804               (bool)Length);
805   }
806
807   void visitMemTransferInst(MemTransferInst &II) {
808     ConstantInt *Length = dyn_cast<ConstantInt>(II.getLength());
809     if (Length && Length->getValue() == 0)
810       // Zero-length mem transfer intrinsics can be ignored entirely.
811       return markAsDead(II);
812
813     // Because we can visit these intrinsics twice, also check to see if the
814     // first time marked this instruction as dead. If so, skip it.
815     if (VisitedDeadInsts.count(&II))
816       return;
817
818     if (!IsOffsetKnown)
819       return PI.setAborted(&II);
820
821     // This side of the transfer is completely out-of-bounds, and so we can
822     // nuke the entire transfer. However, we also need to nuke the other side
823     // if already added to our partitions.
824     // FIXME: Yet another place we really should bypass this when
825     // instrumenting for ASan.
826     if (Offset.uge(AllocSize)) {
827       SmallDenseMap<Instruction *, unsigned>::iterator MTPI =
828           MemTransferSliceMap.find(&II);
829       if (MTPI != MemTransferSliceMap.end())
830         AS.Slices[MTPI->second].kill();
831       return markAsDead(II);
832     }
833
834     uint64_t RawOffset = Offset.getLimitedValue();
835     uint64_t Size = Length ? Length->getLimitedValue() : AllocSize - RawOffset;
836
837     // Check for the special case where the same exact value is used for both
838     // source and dest.
839     if (*U == II.getRawDest() && *U == II.getRawSource()) {
840       // For non-volatile transfers this is a no-op.
841       if (!II.isVolatile())
842         return markAsDead(II);
843
844       return insertUse(II, Offset, Size, /*IsSplittable=*/false);
845     }
846
847     // If we have seen both source and destination for a mem transfer, then
848     // they both point to the same alloca.
849     bool Inserted;
850     SmallDenseMap<Instruction *, unsigned>::iterator MTPI;
851     std::tie(MTPI, Inserted) =
852         MemTransferSliceMap.insert(std::make_pair(&II, AS.Slices.size()));
853     unsigned PrevIdx = MTPI->second;
854     if (!Inserted) {
855       Slice &PrevP = AS.Slices[PrevIdx];
856
857       // Check if the begin offsets match and this is a non-volatile transfer.
858       // In that case, we can completely elide the transfer.
859       if (!II.isVolatile() && PrevP.beginOffset() == RawOffset) {
860         PrevP.kill();
861         return markAsDead(II);
862       }
863
864       // Otherwise we have an offset transfer within the same alloca. We can't
865       // split those.
866       PrevP.makeUnsplittable();
867     }
868
869     // Insert the use now that we've fixed up the splittable nature.
870     insertUse(II, Offset, Size, /*IsSplittable=*/Inserted && Length);
871
872     // Check that we ended up with a valid index in the map.
873     assert(AS.Slices[PrevIdx].getUse()->getUser() == &II &&
874            "Map index doesn't point back to a slice with this user.");
875   }
876
877   // Disable SRoA for any intrinsics except for lifetime invariants.
878   // FIXME: What about debug intrinsics? This matches old behavior, but
879   // doesn't make sense.
880   void visitIntrinsicInst(IntrinsicInst &II) {
881     if (!IsOffsetKnown)
882       return PI.setAborted(&II);
883
884     if (II.getIntrinsicID() == Intrinsic::lifetime_start ||
885         II.getIntrinsicID() == Intrinsic::lifetime_end) {
886       ConstantInt *Length = cast<ConstantInt>(II.getArgOperand(0));
887       uint64_t Size = std::min(AllocSize - Offset.getLimitedValue(),
888                                Length->getLimitedValue());
889       insertUse(II, Offset, Size, true);
890       return;
891     }
892
893     Base::visitIntrinsicInst(II);
894   }
895
896   Instruction *hasUnsafePHIOrSelectUse(Instruction *Root, uint64_t &Size) {
897     // We consider any PHI or select that results in a direct load or store of
898     // the same offset to be a viable use for slicing purposes. These uses
899     // are considered unsplittable and the size is the maximum loaded or stored
900     // size.
901     SmallPtrSet<Instruction *, 4> Visited;
902     SmallVector<std::pair<Instruction *, Instruction *>, 4> Uses;
903     Visited.insert(Root);
904     Uses.push_back(std::make_pair(cast<Instruction>(*U), Root));
905     const DataLayout &DL = Root->getModule()->getDataLayout();
906     // If there are no loads or stores, the access is dead. We mark that as
907     // a size zero access.
908     Size = 0;
909     do {
910       Instruction *I, *UsedI;
911       std::tie(UsedI, I) = Uses.pop_back_val();
912
913       if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
914         Size = std::max(Size, DL.getTypeStoreSize(LI->getType()));
915         continue;
916       }
917       if (StoreInst *SI = dyn_cast<StoreInst>(I)) {
918         Value *Op = SI->getOperand(0);
919         if (Op == UsedI)
920           return SI;
921         Size = std::max(Size, DL.getTypeStoreSize(Op->getType()));
922         continue;
923       }
924
925       if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(I)) {
926         if (!GEP->hasAllZeroIndices())
927           return GEP;
928       } else if (!isa<BitCastInst>(I) && !isa<PHINode>(I) &&
929                  !isa<SelectInst>(I)) {
930         return I;
931       }
932
933       for (User *U : I->users())
934         if (Visited.insert(cast<Instruction>(U)).second)
935           Uses.push_back(std::make_pair(I, cast<Instruction>(U)));
936     } while (!Uses.empty());
937
938     return nullptr;
939   }
940
941   void visitPHINodeOrSelectInst(Instruction &I) {
942     assert(isa<PHINode>(I) || isa<SelectInst>(I));
943     if (I.use_empty())
944       return markAsDead(I);
945
946     // TODO: We could use SimplifyInstruction here to fold PHINodes and
947     // SelectInsts. However, doing so requires to change the current
948     // dead-operand-tracking mechanism. For instance, suppose neither loading
949     // from %U nor %other traps. Then "load (select undef, %U, %other)" does not
950     // trap either.  However, if we simply replace %U with undef using the
951     // current dead-operand-tracking mechanism, "load (select undef, undef,
952     // %other)" may trap because the select may return the first operand
953     // "undef".
954     if (Value *Result = foldPHINodeOrSelectInst(I)) {
955       if (Result == *U)
956         // If the result of the constant fold will be the pointer, recurse
957         // through the PHI/select as if we had RAUW'ed it.
958         enqueueUsers(I);
959       else
960         // Otherwise the operand to the PHI/select is dead, and we can replace
961         // it with undef.
962         AS.DeadOperands.push_back(U);
963
964       return;
965     }
966
967     if (!IsOffsetKnown)
968       return PI.setAborted(&I);
969
970     // See if we already have computed info on this node.
971     uint64_t &Size = PHIOrSelectSizes[&I];
972     if (!Size) {
973       // This is a new PHI/Select, check for an unsafe use of it.
974       if (Instruction *UnsafeI = hasUnsafePHIOrSelectUse(&I, Size))
975         return PI.setAborted(UnsafeI);
976     }
977
978     // For PHI and select operands outside the alloca, we can't nuke the entire
979     // phi or select -- the other side might still be relevant, so we special
980     // case them here and use a separate structure to track the operands
981     // themselves which should be replaced with undef.
982     // FIXME: This should instead be escaped in the event we're instrumenting
983     // for address sanitization.
984     if (Offset.uge(AllocSize)) {
985       AS.DeadOperands.push_back(U);
986       return;
987     }
988
989     insertUse(I, Offset, Size);
990   }
991
992   void visitPHINode(PHINode &PN) { visitPHINodeOrSelectInst(PN); }
993
994   void visitSelectInst(SelectInst &SI) { visitPHINodeOrSelectInst(SI); }
995
996   /// \brief Disable SROA entirely if there are unhandled users of the alloca.
997   void visitInstruction(Instruction &I) { PI.setAborted(&I); }
998 };
999
1000 AllocaSlices::AllocaSlices(const DataLayout &DL, AllocaInst &AI)
1001     :
1002 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1003       AI(AI),
1004 #endif
1005       PointerEscapingInstr(nullptr) {
1006   SliceBuilder PB(DL, AI, *this);
1007   SliceBuilder::PtrInfo PtrI = PB.visitPtr(AI);
1008   if (PtrI.isEscaped() || PtrI.isAborted()) {
1009     // FIXME: We should sink the escape vs. abort info into the caller nicely,
1010     // possibly by just storing the PtrInfo in the AllocaSlices.
1011     PointerEscapingInstr = PtrI.getEscapingInst() ? PtrI.getEscapingInst()
1012                                                   : PtrI.getAbortingInst();
1013     assert(PointerEscapingInstr && "Did not track a bad instruction");
1014     return;
1015   }
1016
1017   Slices.erase(std::remove_if(Slices.begin(), Slices.end(),
1018                               [](const Slice &S) {
1019                                 return S.isDead();
1020                               }),
1021                Slices.end());
1022
1023 #if __cplusplus >= 201103L && !defined(NDEBUG)
1024   if (SROARandomShuffleSlices) {
1025     std::mt19937 MT(static_cast<unsigned>(sys::TimeValue::now().msec()));
1026     std::shuffle(Slices.begin(), Slices.end(), MT);
1027   }
1028 #endif
1029
1030   // Sort the uses. This arranges for the offsets to be in ascending order,
1031   // and the sizes to be in descending order.
1032   std::sort(Slices.begin(), Slices.end());
1033 }
1034
1035 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1036
1037 void AllocaSlices::print(raw_ostream &OS, const_iterator I,
1038                          StringRef Indent) const {
1039   printSlice(OS, I, Indent);
1040   OS << "\n";
1041   printUse(OS, I, Indent);
1042 }
1043
1044 void AllocaSlices::printSlice(raw_ostream &OS, const_iterator I,
1045                               StringRef Indent) const {
1046   OS << Indent << "[" << I->beginOffset() << "," << I->endOffset() << ")"
1047      << " slice #" << (I - begin())
1048      << (I->isSplittable() ? " (splittable)" : "");
1049 }
1050
1051 void AllocaSlices::printUse(raw_ostream &OS, const_iterator I,
1052                             StringRef Indent) const {
1053   OS << Indent << "  used by: " << *I->getUse()->getUser() << "\n";
1054 }
1055
1056 void AllocaSlices::print(raw_ostream &OS) const {
1057   if (PointerEscapingInstr) {
1058     OS << "Can't analyze slices for alloca: " << AI << "\n"
1059        << "  A pointer to this alloca escaped by:\n"
1060        << "  " << *PointerEscapingInstr << "\n";
1061     return;
1062   }
1063
1064   OS << "Slices of alloca: " << AI << "\n";
1065   for (const_iterator I = begin(), E = end(); I != E; ++I)
1066     print(OS, I);
1067 }
1068
1069 LLVM_DUMP_METHOD void AllocaSlices::dump(const_iterator I) const {
1070   print(dbgs(), I);
1071 }
1072 LLVM_DUMP_METHOD void AllocaSlices::dump() const { print(dbgs()); }
1073
1074 #endif // !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1075
1076 namespace {
1077 /// \brief Implementation of LoadAndStorePromoter for promoting allocas.
1078 ///
1079 /// This subclass of LoadAndStorePromoter adds overrides to handle promoting
1080 /// the loads and stores of an alloca instruction, as well as updating its
1081 /// debug information. This is used when a domtree is unavailable and thus
1082 /// mem2reg in its full form can't be used to handle promotion of allocas to
1083 /// scalar values.
1084 class AllocaPromoter : public LoadAndStorePromoter {
1085   AllocaInst &AI;
1086   DIBuilder &DIB;
1087
1088   SmallVector<DbgDeclareInst *, 4> DDIs;
1089   SmallVector<DbgValueInst *, 4> DVIs;
1090
1091 public:
1092   AllocaPromoter(ArrayRef<const Instruction *> Insts,
1093                  SSAUpdater &S,
1094                  AllocaInst &AI, DIBuilder &DIB)
1095       : LoadAndStorePromoter(Insts, S), AI(AI), DIB(DIB) {}
1096
1097   void run(const SmallVectorImpl<Instruction *> &Insts) {
1098     // Retain the debug information attached to the alloca for use when
1099     // rewriting loads and stores.
1100     if (auto *L = LocalAsMetadata::getIfExists(&AI)) {
1101       if (auto *DINode = MetadataAsValue::getIfExists(AI.getContext(), L)) {
1102         for (User *U : DINode->users())
1103           if (DbgDeclareInst *DDI = dyn_cast<DbgDeclareInst>(U))
1104             DDIs.push_back(DDI);
1105           else if (DbgValueInst *DVI = dyn_cast<DbgValueInst>(U))
1106             DVIs.push_back(DVI);
1107       }
1108     }
1109
1110     LoadAndStorePromoter::run(Insts);
1111
1112     // While we have the debug information, clear it off of the alloca. The
1113     // caller takes care of deleting the alloca.
1114     while (!DDIs.empty())
1115       DDIs.pop_back_val()->eraseFromParent();
1116     while (!DVIs.empty())
1117       DVIs.pop_back_val()->eraseFromParent();
1118   }
1119
1120   bool
1121   isInstInList(Instruction *I,
1122                const SmallVectorImpl<Instruction *> &Insts) const override {
1123     Value *Ptr;
1124     if (LoadInst *LI = dyn_cast<LoadInst>(I))
1125       Ptr = LI->getOperand(0);
1126     else
1127       Ptr = cast<StoreInst>(I)->getPointerOperand();
1128
1129     // Only used to detect cycles, which will be rare and quickly found as
1130     // we're walking up a chain of defs rather than down through uses.
1131     SmallPtrSet<Value *, 4> Visited;
1132
1133     do {
1134       if (Ptr == &AI)
1135         return true;
1136
1137       if (BitCastInst *BCI = dyn_cast<BitCastInst>(Ptr))
1138         Ptr = BCI->getOperand(0);
1139       else if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(Ptr))
1140         Ptr = GEPI->getPointerOperand();
1141       else
1142         return false;
1143
1144     } while (Visited.insert(Ptr).second);
1145
1146     return false;
1147   }
1148
1149   void updateDebugInfo(Instruction *Inst) const override {
1150     for (DbgDeclareInst *DDI : DDIs)
1151       if (StoreInst *SI = dyn_cast<StoreInst>(Inst))
1152         ConvertDebugDeclareToDebugValue(DDI, SI, DIB);
1153       else if (LoadInst *LI = dyn_cast<LoadInst>(Inst))
1154         ConvertDebugDeclareToDebugValue(DDI, LI, DIB);
1155     for (DbgValueInst *DVI : DVIs) {
1156       Value *Arg = nullptr;
1157       if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
1158         // If an argument is zero extended then use argument directly. The ZExt
1159         // may be zapped by an optimization pass in future.
1160         if (ZExtInst *ZExt = dyn_cast<ZExtInst>(SI->getOperand(0)))
1161           Arg = dyn_cast<Argument>(ZExt->getOperand(0));
1162         else if (SExtInst *SExt = dyn_cast<SExtInst>(SI->getOperand(0)))
1163           Arg = dyn_cast<Argument>(SExt->getOperand(0));
1164         if (!Arg)
1165           Arg = SI->getValueOperand();
1166       } else if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) {
1167         Arg = LI->getPointerOperand();
1168       } else {
1169         continue;
1170       }
1171       DIB.insertDbgValueIntrinsic(Arg, 0, DVI->getVariable(),
1172                                   DVI->getExpression(), DVI->getDebugLoc(),
1173                                   Inst);
1174     }
1175   }
1176 };
1177 } // end anon namespace
1178
1179 namespace {
1180 /// \brief An optimization pass providing Scalar Replacement of Aggregates.
1181 ///
1182 /// This pass takes allocations which can be completely analyzed (that is, they
1183 /// don't escape) and tries to turn them into scalar SSA values. There are
1184 /// a few steps to this process.
1185 ///
1186 /// 1) It takes allocations of aggregates and analyzes the ways in which they
1187 ///    are used to try to split them into smaller allocations, ideally of
1188 ///    a single scalar data type. It will split up memcpy and memset accesses
1189 ///    as necessary and try to isolate individual scalar accesses.
1190 /// 2) It will transform accesses into forms which are suitable for SSA value
1191 ///    promotion. This can be replacing a memset with a scalar store of an
1192 ///    integer value, or it can involve speculating operations on a PHI or
1193 ///    select to be a PHI or select of the results.
1194 /// 3) Finally, this will try to detect a pattern of accesses which map cleanly
1195 ///    onto insert and extract operations on a vector value, and convert them to
1196 ///    this form. By doing so, it will enable promotion of vector aggregates to
1197 ///    SSA vector values.
1198 class SROA : public FunctionPass {
1199   const bool RequiresDomTree;
1200
1201   LLVMContext *C;
1202   DominatorTree *DT;
1203   AssumptionCache *AC;
1204
1205   /// \brief Worklist of alloca instructions to simplify.
1206   ///
1207   /// Each alloca in the function is added to this. Each new alloca formed gets
1208   /// added to it as well to recursively simplify unless that alloca can be
1209   /// directly promoted. Finally, each time we rewrite a use of an alloca other
1210   /// the one being actively rewritten, we add it back onto the list if not
1211   /// already present to ensure it is re-visited.
1212   SetVector<AllocaInst *, SmallVector<AllocaInst *, 16>> Worklist;
1213
1214   /// \brief A collection of instructions to delete.
1215   /// We try to batch deletions to simplify code and make things a bit more
1216   /// efficient.
1217   SetVector<Instruction *, SmallVector<Instruction *, 8>> DeadInsts;
1218
1219   /// \brief Post-promotion worklist.
1220   ///
1221   /// Sometimes we discover an alloca which has a high probability of becoming
1222   /// viable for SROA after a round of promotion takes place. In those cases,
1223   /// the alloca is enqueued here for re-processing.
1224   ///
1225   /// Note that we have to be very careful to clear allocas out of this list in
1226   /// the event they are deleted.
1227   SetVector<AllocaInst *, SmallVector<AllocaInst *, 16>> PostPromotionWorklist;
1228
1229   /// \brief A collection of alloca instructions we can directly promote.
1230   std::vector<AllocaInst *> PromotableAllocas;
1231
1232   /// \brief A worklist of PHIs to speculate prior to promoting allocas.
1233   ///
1234   /// All of these PHIs have been checked for the safety of speculation and by
1235   /// being speculated will allow promoting allocas currently in the promotable
1236   /// queue.
1237   SetVector<PHINode *, SmallVector<PHINode *, 2>> SpeculatablePHIs;
1238
1239   /// \brief A worklist of select instructions to speculate prior to promoting
1240   /// allocas.
1241   ///
1242   /// All of these select instructions have been checked for the safety of
1243   /// speculation and by being speculated will allow promoting allocas
1244   /// currently in the promotable queue.
1245   SetVector<SelectInst *, SmallVector<SelectInst *, 2>> SpeculatableSelects;
1246
1247 public:
1248   SROA(bool RequiresDomTree = true)
1249       : FunctionPass(ID), RequiresDomTree(RequiresDomTree), C(nullptr),
1250         DT(nullptr) {
1251     initializeSROAPass(*PassRegistry::getPassRegistry());
1252   }
1253   bool runOnFunction(Function &F) override;
1254   void getAnalysisUsage(AnalysisUsage &AU) const override;
1255
1256   const char *getPassName() const override { return "SROA"; }
1257   static char ID;
1258
1259 private:
1260   friend class PHIOrSelectSpeculator;
1261   friend class AllocaSliceRewriter;
1262
1263   bool presplitLoadsAndStores(AllocaInst &AI, AllocaSlices &AS);
1264   AllocaInst *rewritePartition(AllocaInst &AI, AllocaSlices &AS,
1265                                AllocaSlices::Partition &P);
1266   bool splitAlloca(AllocaInst &AI, AllocaSlices &AS);
1267   bool runOnAlloca(AllocaInst &AI);
1268   void clobberUse(Use &U);
1269   void deleteDeadInstructions(SmallPtrSetImpl<AllocaInst *> &DeletedAllocas);
1270   bool promoteAllocas(Function &F);
1271 };
1272 }
1273
1274 char SROA::ID = 0;
1275
1276 FunctionPass *llvm::createSROAPass(bool RequiresDomTree) {
1277   return new SROA(RequiresDomTree);
1278 }
1279
1280 INITIALIZE_PASS_BEGIN(SROA, "sroa", "Scalar Replacement Of Aggregates", false,
1281                       false)
1282 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
1283 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
1284 INITIALIZE_PASS_END(SROA, "sroa", "Scalar Replacement Of Aggregates", false,
1285                     false)
1286
1287 /// Walk the range of a partitioning looking for a common type to cover this
1288 /// sequence of slices.
1289 static Type *findCommonType(AllocaSlices::const_iterator B,
1290                             AllocaSlices::const_iterator E,
1291                             uint64_t EndOffset) {
1292   Type *Ty = nullptr;
1293   bool TyIsCommon = true;
1294   IntegerType *ITy = nullptr;
1295
1296   // Note that we need to look at *every* alloca slice's Use to ensure we
1297   // always get consistent results regardless of the order of slices.
1298   for (AllocaSlices::const_iterator I = B; I != E; ++I) {
1299     Use *U = I->getUse();
1300     if (isa<IntrinsicInst>(*U->getUser()))
1301       continue;
1302     if (I->beginOffset() != B->beginOffset() || I->endOffset() != EndOffset)
1303       continue;
1304
1305     Type *UserTy = nullptr;
1306     if (LoadInst *LI = dyn_cast<LoadInst>(U->getUser())) {
1307       UserTy = LI->getType();
1308     } else if (StoreInst *SI = dyn_cast<StoreInst>(U->getUser())) {
1309       UserTy = SI->getValueOperand()->getType();
1310     }
1311
1312     if (IntegerType *UserITy = dyn_cast_or_null<IntegerType>(UserTy)) {
1313       // If the type is larger than the partition, skip it. We only encounter
1314       // this for split integer operations where we want to use the type of the
1315       // entity causing the split. Also skip if the type is not a byte width
1316       // multiple.
1317       if (UserITy->getBitWidth() % 8 != 0 ||
1318           UserITy->getBitWidth() / 8 > (EndOffset - B->beginOffset()))
1319         continue;
1320
1321       // Track the largest bitwidth integer type used in this way in case there
1322       // is no common type.
1323       if (!ITy || ITy->getBitWidth() < UserITy->getBitWidth())
1324         ITy = UserITy;
1325     }
1326
1327     // To avoid depending on the order of slices, Ty and TyIsCommon must not
1328     // depend on types skipped above.
1329     if (!UserTy || (Ty && Ty != UserTy))
1330       TyIsCommon = false; // Give up on anything but an iN type.
1331     else
1332       Ty = UserTy;
1333   }
1334
1335   return TyIsCommon ? Ty : ITy;
1336 }
1337
1338 /// PHI instructions that use an alloca and are subsequently loaded can be
1339 /// rewritten to load both input pointers in the pred blocks and then PHI the
1340 /// results, allowing the load of the alloca to be promoted.
1341 /// From this:
1342 ///   %P2 = phi [i32* %Alloca, i32* %Other]
1343 ///   %V = load i32* %P2
1344 /// to:
1345 ///   %V1 = load i32* %Alloca      -> will be mem2reg'd
1346 ///   ...
1347 ///   %V2 = load i32* %Other
1348 ///   ...
1349 ///   %V = phi [i32 %V1, i32 %V2]
1350 ///
1351 /// We can do this to a select if its only uses are loads and if the operands
1352 /// to the select can be loaded unconditionally.
1353 ///
1354 /// FIXME: This should be hoisted into a generic utility, likely in
1355 /// Transforms/Util/Local.h
1356 static bool isSafePHIToSpeculate(PHINode &PN) {
1357   // For now, we can only do this promotion if the load is in the same block
1358   // as the PHI, and if there are no stores between the phi and load.
1359   // TODO: Allow recursive phi users.
1360   // TODO: Allow stores.
1361   BasicBlock *BB = PN.getParent();
1362   unsigned MaxAlign = 0;
1363   bool HaveLoad = false;
1364   for (User *U : PN.users()) {
1365     LoadInst *LI = dyn_cast<LoadInst>(U);
1366     if (!LI || !LI->isSimple())
1367       return false;
1368
1369     // For now we only allow loads in the same block as the PHI.  This is
1370     // a common case that happens when instcombine merges two loads through
1371     // a PHI.
1372     if (LI->getParent() != BB)
1373       return false;
1374
1375     // Ensure that there are no instructions between the PHI and the load that
1376     // could store.
1377     for (BasicBlock::iterator BBI = &PN; &*BBI != LI; ++BBI)
1378       if (BBI->mayWriteToMemory())
1379         return false;
1380
1381     MaxAlign = std::max(MaxAlign, LI->getAlignment());
1382     HaveLoad = true;
1383   }
1384
1385   if (!HaveLoad)
1386     return false;
1387
1388   const DataLayout &DL = PN.getModule()->getDataLayout();
1389
1390   // We can only transform this if it is safe to push the loads into the
1391   // predecessor blocks. The only thing to watch out for is that we can't put
1392   // a possibly trapping load in the predecessor if it is a critical edge.
1393   for (unsigned Idx = 0, Num = PN.getNumIncomingValues(); Idx != Num; ++Idx) {
1394     TerminatorInst *TI = PN.getIncomingBlock(Idx)->getTerminator();
1395     Value *InVal = PN.getIncomingValue(Idx);
1396
1397     // If the value is produced by the terminator of the predecessor (an
1398     // invoke) or it has side-effects, there is no valid place to put a load
1399     // in the predecessor.
1400     if (TI == InVal || TI->mayHaveSideEffects())
1401       return false;
1402
1403     // If the predecessor has a single successor, then the edge isn't
1404     // critical.
1405     if (TI->getNumSuccessors() == 1)
1406       continue;
1407
1408     // If this pointer is always safe to load, or if we can prove that there
1409     // is already a load in the block, then we can move the load to the pred
1410     // block.
1411     if (isDereferenceablePointer(InVal, DL) ||
1412         isSafeToLoadUnconditionally(InVal, TI, MaxAlign))
1413       continue;
1414
1415     return false;
1416   }
1417
1418   return true;
1419 }
1420
1421 static void speculatePHINodeLoads(PHINode &PN) {
1422   DEBUG(dbgs() << "    original: " << PN << "\n");
1423
1424   Type *LoadTy = cast<PointerType>(PN.getType())->getElementType();
1425   IRBuilderTy PHIBuilder(&PN);
1426   PHINode *NewPN = PHIBuilder.CreatePHI(LoadTy, PN.getNumIncomingValues(),
1427                                         PN.getName() + ".sroa.speculated");
1428
1429   // Get the AA tags and alignment to use from one of the loads.  It doesn't
1430   // matter which one we get and if any differ.
1431   LoadInst *SomeLoad = cast<LoadInst>(PN.user_back());
1432
1433   AAMDNodes AATags;
1434   SomeLoad->getAAMetadata(AATags);
1435   unsigned Align = SomeLoad->getAlignment();
1436
1437   // Rewrite all loads of the PN to use the new PHI.
1438   while (!PN.use_empty()) {
1439     LoadInst *LI = cast<LoadInst>(PN.user_back());
1440     LI->replaceAllUsesWith(NewPN);
1441     LI->eraseFromParent();
1442   }
1443
1444   // Inject loads into all of the pred blocks.
1445   for (unsigned Idx = 0, Num = PN.getNumIncomingValues(); Idx != Num; ++Idx) {
1446     BasicBlock *Pred = PN.getIncomingBlock(Idx);
1447     TerminatorInst *TI = Pred->getTerminator();
1448     Value *InVal = PN.getIncomingValue(Idx);
1449     IRBuilderTy PredBuilder(TI);
1450
1451     LoadInst *Load = PredBuilder.CreateLoad(
1452         InVal, (PN.getName() + ".sroa.speculate.load." + Pred->getName()));
1453     ++NumLoadsSpeculated;
1454     Load->setAlignment(Align);
1455     if (AATags)
1456       Load->setAAMetadata(AATags);
1457     NewPN->addIncoming(Load, Pred);
1458   }
1459
1460   DEBUG(dbgs() << "          speculated to: " << *NewPN << "\n");
1461   PN.eraseFromParent();
1462 }
1463
1464 /// Select instructions that use an alloca and are subsequently loaded can be
1465 /// rewritten to load both input pointers and then select between the result,
1466 /// allowing the load of the alloca to be promoted.
1467 /// From this:
1468 ///   %P2 = select i1 %cond, i32* %Alloca, i32* %Other
1469 ///   %V = load i32* %P2
1470 /// to:
1471 ///   %V1 = load i32* %Alloca      -> will be mem2reg'd
1472 ///   %V2 = load i32* %Other
1473 ///   %V = select i1 %cond, i32 %V1, i32 %V2
1474 ///
1475 /// We can do this to a select if its only uses are loads and if the operand
1476 /// to the select can be loaded unconditionally.
1477 static bool isSafeSelectToSpeculate(SelectInst &SI) {
1478   Value *TValue = SI.getTrueValue();
1479   Value *FValue = SI.getFalseValue();
1480   const DataLayout &DL = SI.getModule()->getDataLayout();
1481   bool TDerefable = isDereferenceablePointer(TValue, DL);
1482   bool FDerefable = isDereferenceablePointer(FValue, DL);
1483
1484   for (User *U : SI.users()) {
1485     LoadInst *LI = dyn_cast<LoadInst>(U);
1486     if (!LI || !LI->isSimple())
1487       return false;
1488
1489     // Both operands to the select need to be dereferencable, either
1490     // absolutely (e.g. allocas) or at this point because we can see other
1491     // accesses to it.
1492     if (!TDerefable &&
1493         !isSafeToLoadUnconditionally(TValue, LI, LI->getAlignment()))
1494       return false;
1495     if (!FDerefable &&
1496         !isSafeToLoadUnconditionally(FValue, LI, LI->getAlignment()))
1497       return false;
1498   }
1499
1500   return true;
1501 }
1502
1503 static void speculateSelectInstLoads(SelectInst &SI) {
1504   DEBUG(dbgs() << "    original: " << SI << "\n");
1505
1506   IRBuilderTy IRB(&SI);
1507   Value *TV = SI.getTrueValue();
1508   Value *FV = SI.getFalseValue();
1509   // Replace the loads of the select with a select of two loads.
1510   while (!SI.use_empty()) {
1511     LoadInst *LI = cast<LoadInst>(SI.user_back());
1512     assert(LI->isSimple() && "We only speculate simple loads");
1513
1514     IRB.SetInsertPoint(LI);
1515     LoadInst *TL =
1516         IRB.CreateLoad(TV, LI->getName() + ".sroa.speculate.load.true");
1517     LoadInst *FL =
1518         IRB.CreateLoad(FV, LI->getName() + ".sroa.speculate.load.false");
1519     NumLoadsSpeculated += 2;
1520
1521     // Transfer alignment and AA info if present.
1522     TL->setAlignment(LI->getAlignment());
1523     FL->setAlignment(LI->getAlignment());
1524
1525     AAMDNodes Tags;
1526     LI->getAAMetadata(Tags);
1527     if (Tags) {
1528       TL->setAAMetadata(Tags);
1529       FL->setAAMetadata(Tags);
1530     }
1531
1532     Value *V = IRB.CreateSelect(SI.getCondition(), TL, FL,
1533                                 LI->getName() + ".sroa.speculated");
1534
1535     DEBUG(dbgs() << "          speculated to: " << *V << "\n");
1536     LI->replaceAllUsesWith(V);
1537     LI->eraseFromParent();
1538   }
1539   SI.eraseFromParent();
1540 }
1541
1542 /// \brief Build a GEP out of a base pointer and indices.
1543 ///
1544 /// This will return the BasePtr if that is valid, or build a new GEP
1545 /// instruction using the IRBuilder if GEP-ing is needed.
1546 static Value *buildGEP(IRBuilderTy &IRB, Value *BasePtr,
1547                        SmallVectorImpl<Value *> &Indices, Twine NamePrefix) {
1548   if (Indices.empty())
1549     return BasePtr;
1550
1551   // A single zero index is a no-op, so check for this and avoid building a GEP
1552   // in that case.
1553   if (Indices.size() == 1 && cast<ConstantInt>(Indices.back())->isZero())
1554     return BasePtr;
1555
1556   return IRB.CreateInBoundsGEP(nullptr, BasePtr, Indices,
1557                                NamePrefix + "sroa_idx");
1558 }
1559
1560 /// \brief Get a natural GEP off of the BasePtr walking through Ty toward
1561 /// TargetTy without changing the offset of the pointer.
1562 ///
1563 /// This routine assumes we've already established a properly offset GEP with
1564 /// Indices, and arrived at the Ty type. The goal is to continue to GEP with
1565 /// zero-indices down through type layers until we find one the same as
1566 /// TargetTy. If we can't find one with the same type, we at least try to use
1567 /// one with the same size. If none of that works, we just produce the GEP as
1568 /// indicated by Indices to have the correct offset.
1569 static Value *getNaturalGEPWithType(IRBuilderTy &IRB, const DataLayout &DL,
1570                                     Value *BasePtr, Type *Ty, Type *TargetTy,
1571                                     SmallVectorImpl<Value *> &Indices,
1572                                     Twine NamePrefix) {
1573   if (Ty == TargetTy)
1574     return buildGEP(IRB, BasePtr, Indices, NamePrefix);
1575
1576   // Pointer size to use for the indices.
1577   unsigned PtrSize = DL.getPointerTypeSizeInBits(BasePtr->getType());
1578
1579   // See if we can descend into a struct and locate a field with the correct
1580   // type.
1581   unsigned NumLayers = 0;
1582   Type *ElementTy = Ty;
1583   do {
1584     if (ElementTy->isPointerTy())
1585       break;
1586
1587     if (ArrayType *ArrayTy = dyn_cast<ArrayType>(ElementTy)) {
1588       ElementTy = ArrayTy->getElementType();
1589       Indices.push_back(IRB.getIntN(PtrSize, 0));
1590     } else if (VectorType *VectorTy = dyn_cast<VectorType>(ElementTy)) {
1591       ElementTy = VectorTy->getElementType();
1592       Indices.push_back(IRB.getInt32(0));
1593     } else if (StructType *STy = dyn_cast<StructType>(ElementTy)) {
1594       if (STy->element_begin() == STy->element_end())
1595         break; // Nothing left to descend into.
1596       ElementTy = *STy->element_begin();
1597       Indices.push_back(IRB.getInt32(0));
1598     } else {
1599       break;
1600     }
1601     ++NumLayers;
1602   } while (ElementTy != TargetTy);
1603   if (ElementTy != TargetTy)
1604     Indices.erase(Indices.end() - NumLayers, Indices.end());
1605
1606   return buildGEP(IRB, BasePtr, Indices, NamePrefix);
1607 }
1608
1609 /// \brief Recursively compute indices for a natural GEP.
1610 ///
1611 /// This is the recursive step for getNaturalGEPWithOffset that walks down the
1612 /// element types adding appropriate indices for the GEP.
1613 static Value *getNaturalGEPRecursively(IRBuilderTy &IRB, const DataLayout &DL,
1614                                        Value *Ptr, Type *Ty, APInt &Offset,
1615                                        Type *TargetTy,
1616                                        SmallVectorImpl<Value *> &Indices,
1617                                        Twine NamePrefix) {
1618   if (Offset == 0)
1619     return getNaturalGEPWithType(IRB, DL, Ptr, Ty, TargetTy, Indices,
1620                                  NamePrefix);
1621
1622   // We can't recurse through pointer types.
1623   if (Ty->isPointerTy())
1624     return nullptr;
1625
1626   // We try to analyze GEPs over vectors here, but note that these GEPs are
1627   // extremely poorly defined currently. The long-term goal is to remove GEPing
1628   // over a vector from the IR completely.
1629   if (VectorType *VecTy = dyn_cast<VectorType>(Ty)) {
1630     unsigned ElementSizeInBits = DL.getTypeSizeInBits(VecTy->getScalarType());
1631     if (ElementSizeInBits % 8 != 0) {
1632       // GEPs over non-multiple of 8 size vector elements are invalid.
1633       return nullptr;
1634     }
1635     APInt ElementSize(Offset.getBitWidth(), ElementSizeInBits / 8);
1636     APInt NumSkippedElements = Offset.sdiv(ElementSize);
1637     if (NumSkippedElements.ugt(VecTy->getNumElements()))
1638       return nullptr;
1639     Offset -= NumSkippedElements * ElementSize;
1640     Indices.push_back(IRB.getInt(NumSkippedElements));
1641     return getNaturalGEPRecursively(IRB, DL, Ptr, VecTy->getElementType(),
1642                                     Offset, TargetTy, Indices, NamePrefix);
1643   }
1644
1645   if (ArrayType *ArrTy = dyn_cast<ArrayType>(Ty)) {
1646     Type *ElementTy = ArrTy->getElementType();
1647     APInt ElementSize(Offset.getBitWidth(), DL.getTypeAllocSize(ElementTy));
1648     APInt NumSkippedElements = Offset.sdiv(ElementSize);
1649     if (NumSkippedElements.ugt(ArrTy->getNumElements()))
1650       return nullptr;
1651
1652     Offset -= NumSkippedElements * ElementSize;
1653     Indices.push_back(IRB.getInt(NumSkippedElements));
1654     return getNaturalGEPRecursively(IRB, DL, Ptr, ElementTy, Offset, TargetTy,
1655                                     Indices, NamePrefix);
1656   }
1657
1658   StructType *STy = dyn_cast<StructType>(Ty);
1659   if (!STy)
1660     return nullptr;
1661
1662   const StructLayout *SL = DL.getStructLayout(STy);
1663   uint64_t StructOffset = Offset.getZExtValue();
1664   if (StructOffset >= SL->getSizeInBytes())
1665     return nullptr;
1666   unsigned Index = SL->getElementContainingOffset(StructOffset);
1667   Offset -= APInt(Offset.getBitWidth(), SL->getElementOffset(Index));
1668   Type *ElementTy = STy->getElementType(Index);
1669   if (Offset.uge(DL.getTypeAllocSize(ElementTy)))
1670     return nullptr; // The offset points into alignment padding.
1671
1672   Indices.push_back(IRB.getInt32(Index));
1673   return getNaturalGEPRecursively(IRB, DL, Ptr, ElementTy, Offset, TargetTy,
1674                                   Indices, NamePrefix);
1675 }
1676
1677 /// \brief Get a natural GEP from a base pointer to a particular offset and
1678 /// resulting in a particular type.
1679 ///
1680 /// The goal is to produce a "natural" looking GEP that works with the existing
1681 /// composite types to arrive at the appropriate offset and element type for
1682 /// a pointer. TargetTy is the element type the returned GEP should point-to if
1683 /// possible. We recurse by decreasing Offset, adding the appropriate index to
1684 /// Indices, and setting Ty to the result subtype.
1685 ///
1686 /// If no natural GEP can be constructed, this function returns null.
1687 static Value *getNaturalGEPWithOffset(IRBuilderTy &IRB, const DataLayout &DL,
1688                                       Value *Ptr, APInt Offset, Type *TargetTy,
1689                                       SmallVectorImpl<Value *> &Indices,
1690                                       Twine NamePrefix) {
1691   PointerType *Ty = cast<PointerType>(Ptr->getType());
1692
1693   // Don't consider any GEPs through an i8* as natural unless the TargetTy is
1694   // an i8.
1695   if (Ty == IRB.getInt8PtrTy(Ty->getAddressSpace()) && TargetTy->isIntegerTy(8))
1696     return nullptr;
1697
1698   Type *ElementTy = Ty->getElementType();
1699   if (!ElementTy->isSized())
1700     return nullptr; // We can't GEP through an unsized element.
1701   APInt ElementSize(Offset.getBitWidth(), DL.getTypeAllocSize(ElementTy));
1702   if (ElementSize == 0)
1703     return nullptr; // Zero-length arrays can't help us build a natural GEP.
1704   APInt NumSkippedElements = Offset.sdiv(ElementSize);
1705
1706   Offset -= NumSkippedElements * ElementSize;
1707   Indices.push_back(IRB.getInt(NumSkippedElements));
1708   return getNaturalGEPRecursively(IRB, DL, Ptr, ElementTy, Offset, TargetTy,
1709                                   Indices, NamePrefix);
1710 }
1711
1712 /// \brief Compute an adjusted pointer from Ptr by Offset bytes where the
1713 /// resulting pointer has PointerTy.
1714 ///
1715 /// This tries very hard to compute a "natural" GEP which arrives at the offset
1716 /// and produces the pointer type desired. Where it cannot, it will try to use
1717 /// the natural GEP to arrive at the offset and bitcast to the type. Where that
1718 /// fails, it will try to use an existing i8* and GEP to the byte offset and
1719 /// bitcast to the type.
1720 ///
1721 /// The strategy for finding the more natural GEPs is to peel off layers of the
1722 /// pointer, walking back through bit casts and GEPs, searching for a base
1723 /// pointer from which we can compute a natural GEP with the desired
1724 /// properties. The algorithm tries to fold as many constant indices into
1725 /// a single GEP as possible, thus making each GEP more independent of the
1726 /// surrounding code.
1727 static Value *getAdjustedPtr(IRBuilderTy &IRB, const DataLayout &DL, Value *Ptr,
1728                              APInt Offset, Type *PointerTy, Twine NamePrefix) {
1729   // Even though we don't look through PHI nodes, we could be called on an
1730   // instruction in an unreachable block, which may be on a cycle.
1731   SmallPtrSet<Value *, 4> Visited;
1732   Visited.insert(Ptr);
1733   SmallVector<Value *, 4> Indices;
1734
1735   // We may end up computing an offset pointer that has the wrong type. If we
1736   // never are able to compute one directly that has the correct type, we'll
1737   // fall back to it, so keep it and the base it was computed from around here.
1738   Value *OffsetPtr = nullptr;
1739   Value *OffsetBasePtr;
1740
1741   // Remember any i8 pointer we come across to re-use if we need to do a raw
1742   // byte offset.
1743   Value *Int8Ptr = nullptr;
1744   APInt Int8PtrOffset(Offset.getBitWidth(), 0);
1745
1746   Type *TargetTy = PointerTy->getPointerElementType();
1747
1748   do {
1749     // First fold any existing GEPs into the offset.
1750     while (GEPOperator *GEP = dyn_cast<GEPOperator>(Ptr)) {
1751       APInt GEPOffset(Offset.getBitWidth(), 0);
1752       if (!GEP->accumulateConstantOffset(DL, GEPOffset))
1753         break;
1754       Offset += GEPOffset;
1755       Ptr = GEP->getPointerOperand();
1756       if (!Visited.insert(Ptr).second)
1757         break;
1758     }
1759
1760     // See if we can perform a natural GEP here.
1761     Indices.clear();
1762     if (Value *P = getNaturalGEPWithOffset(IRB, DL, Ptr, Offset, TargetTy,
1763                                            Indices, NamePrefix)) {
1764       // If we have a new natural pointer at the offset, clear out any old
1765       // offset pointer we computed. Unless it is the base pointer or
1766       // a non-instruction, we built a GEP we don't need. Zap it.
1767       if (OffsetPtr && OffsetPtr != OffsetBasePtr)
1768         if (Instruction *I = dyn_cast<Instruction>(OffsetPtr)) {
1769           assert(I->use_empty() && "Built a GEP with uses some how!");
1770           I->eraseFromParent();
1771         }
1772       OffsetPtr = P;
1773       OffsetBasePtr = Ptr;
1774       // If we also found a pointer of the right type, we're done.
1775       if (P->getType() == PointerTy)
1776         return P;
1777     }
1778
1779     // Stash this pointer if we've found an i8*.
1780     if (Ptr->getType()->isIntegerTy(8)) {
1781       Int8Ptr = Ptr;
1782       Int8PtrOffset = Offset;
1783     }
1784
1785     // Peel off a layer of the pointer and update the offset appropriately.
1786     if (Operator::getOpcode(Ptr) == Instruction::BitCast) {
1787       Ptr = cast<Operator>(Ptr)->getOperand(0);
1788     } else if (GlobalAlias *GA = dyn_cast<GlobalAlias>(Ptr)) {
1789       if (GA->mayBeOverridden())
1790         break;
1791       Ptr = GA->getAliasee();
1792     } else {
1793       break;
1794     }
1795     assert(Ptr->getType()->isPointerTy() && "Unexpected operand type!");
1796   } while (Visited.insert(Ptr).second);
1797
1798   if (!OffsetPtr) {
1799     if (!Int8Ptr) {
1800       Int8Ptr = IRB.CreateBitCast(
1801           Ptr, IRB.getInt8PtrTy(PointerTy->getPointerAddressSpace()),
1802           NamePrefix + "sroa_raw_cast");
1803       Int8PtrOffset = Offset;
1804     }
1805
1806     OffsetPtr = Int8PtrOffset == 0
1807                     ? Int8Ptr
1808                     : IRB.CreateInBoundsGEP(IRB.getInt8Ty(), Int8Ptr,
1809                                             IRB.getInt(Int8PtrOffset),
1810                                             NamePrefix + "sroa_raw_idx");
1811   }
1812   Ptr = OffsetPtr;
1813
1814   // On the off chance we were targeting i8*, guard the bitcast here.
1815   if (Ptr->getType() != PointerTy)
1816     Ptr = IRB.CreateBitCast(Ptr, PointerTy, NamePrefix + "sroa_cast");
1817
1818   return Ptr;
1819 }
1820
1821 /// \brief Compute the adjusted alignment for a load or store from an offset.
1822 static unsigned getAdjustedAlignment(Instruction *I, uint64_t Offset,
1823                                      const DataLayout &DL) {
1824   unsigned Alignment;
1825   Type *Ty;
1826   if (auto *LI = dyn_cast<LoadInst>(I)) {
1827     Alignment = LI->getAlignment();
1828     Ty = LI->getType();
1829   } else if (auto *SI = dyn_cast<StoreInst>(I)) {
1830     Alignment = SI->getAlignment();
1831     Ty = SI->getValueOperand()->getType();
1832   } else {
1833     llvm_unreachable("Only loads and stores are allowed!");
1834   }
1835
1836   if (!Alignment)
1837     Alignment = DL.getABITypeAlignment(Ty);
1838
1839   return MinAlign(Alignment, Offset);
1840 }
1841
1842 /// \brief Test whether we can convert a value from the old to the new type.
1843 ///
1844 /// This predicate should be used to guard calls to convertValue in order to
1845 /// ensure that we only try to convert viable values. The strategy is that we
1846 /// will peel off single element struct and array wrappings to get to an
1847 /// underlying value, and convert that value.
1848 static bool canConvertValue(const DataLayout &DL, Type *OldTy, Type *NewTy) {
1849   if (OldTy == NewTy)
1850     return true;
1851
1852   // For integer types, we can't handle any bit-width differences. This would
1853   // break both vector conversions with extension and introduce endianness
1854   // issues when in conjunction with loads and stores.
1855   if (isa<IntegerType>(OldTy) && isa<IntegerType>(NewTy)) {
1856     assert(cast<IntegerType>(OldTy)->getBitWidth() !=
1857                cast<IntegerType>(NewTy)->getBitWidth() &&
1858            "We can't have the same bitwidth for different int types");
1859     return false;
1860   }
1861
1862   if (DL.getTypeSizeInBits(NewTy) != DL.getTypeSizeInBits(OldTy))
1863     return false;
1864   if (!NewTy->isSingleValueType() || !OldTy->isSingleValueType())
1865     return false;
1866
1867   // We can convert pointers to integers and vice-versa. Same for vectors
1868   // of pointers and integers.
1869   OldTy = OldTy->getScalarType();
1870   NewTy = NewTy->getScalarType();
1871   if (NewTy->isPointerTy() || OldTy->isPointerTy()) {
1872     if (NewTy->isPointerTy() && OldTy->isPointerTy())
1873       return true;
1874     if (NewTy->isIntegerTy() || OldTy->isIntegerTy())
1875       return true;
1876     return false;
1877   }
1878
1879   return true;
1880 }
1881
1882 /// \brief Generic routine to convert an SSA value to a value of a different
1883 /// type.
1884 ///
1885 /// This will try various different casting techniques, such as bitcasts,
1886 /// inttoptr, and ptrtoint casts. Use the \c canConvertValue predicate to test
1887 /// two types for viability with this routine.
1888 static Value *convertValue(const DataLayout &DL, IRBuilderTy &IRB, Value *V,
1889                            Type *NewTy) {
1890   Type *OldTy = V->getType();
1891   assert(canConvertValue(DL, OldTy, NewTy) && "Value not convertable to type");
1892
1893   if (OldTy == NewTy)
1894     return V;
1895
1896   assert(!(isa<IntegerType>(OldTy) && isa<IntegerType>(NewTy)) &&
1897          "Integer types must be the exact same to convert.");
1898
1899   // See if we need inttoptr for this type pair. A cast involving both scalars
1900   // and vectors requires and additional bitcast.
1901   if (OldTy->getScalarType()->isIntegerTy() &&
1902       NewTy->getScalarType()->isPointerTy()) {
1903     // Expand <2 x i32> to i8* --> <2 x i32> to i64 to i8*
1904     if (OldTy->isVectorTy() && !NewTy->isVectorTy())
1905       return IRB.CreateIntToPtr(IRB.CreateBitCast(V, DL.getIntPtrType(NewTy)),
1906                                 NewTy);
1907
1908     // Expand i128 to <2 x i8*> --> i128 to <2 x i64> to <2 x i8*>
1909     if (!OldTy->isVectorTy() && NewTy->isVectorTy())
1910       return IRB.CreateIntToPtr(IRB.CreateBitCast(V, DL.getIntPtrType(NewTy)),
1911                                 NewTy);
1912
1913     return IRB.CreateIntToPtr(V, NewTy);
1914   }
1915
1916   // See if we need ptrtoint for this type pair. A cast involving both scalars
1917   // and vectors requires and additional bitcast.
1918   if (OldTy->getScalarType()->isPointerTy() &&
1919       NewTy->getScalarType()->isIntegerTy()) {
1920     // Expand <2 x i8*> to i128 --> <2 x i8*> to <2 x i64> to i128
1921     if (OldTy->isVectorTy() && !NewTy->isVectorTy())
1922       return IRB.CreateBitCast(IRB.CreatePtrToInt(V, DL.getIntPtrType(OldTy)),
1923                                NewTy);
1924
1925     // Expand i8* to <2 x i32> --> i8* to i64 to <2 x i32>
1926     if (!OldTy->isVectorTy() && NewTy->isVectorTy())
1927       return IRB.CreateBitCast(IRB.CreatePtrToInt(V, DL.getIntPtrType(OldTy)),
1928                                NewTy);
1929
1930     return IRB.CreatePtrToInt(V, NewTy);
1931   }
1932
1933   return IRB.CreateBitCast(V, NewTy);
1934 }
1935
1936 /// \brief Test whether the given slice use can be promoted to a vector.
1937 ///
1938 /// This function is called to test each entry in a partition which is slated
1939 /// for a single slice.
1940 static bool isVectorPromotionViableForSlice(AllocaSlices::Partition &P,
1941                                             const Slice &S, VectorType *Ty,
1942                                             uint64_t ElementSize,
1943                                             const DataLayout &DL) {
1944   // First validate the slice offsets.
1945   uint64_t BeginOffset =
1946       std::max(S.beginOffset(), P.beginOffset()) - P.beginOffset();
1947   uint64_t BeginIndex = BeginOffset / ElementSize;
1948   if (BeginIndex * ElementSize != BeginOffset ||
1949       BeginIndex >= Ty->getNumElements())
1950     return false;
1951   uint64_t EndOffset =
1952       std::min(S.endOffset(), P.endOffset()) - P.beginOffset();
1953   uint64_t EndIndex = EndOffset / ElementSize;
1954   if (EndIndex * ElementSize != EndOffset || EndIndex > Ty->getNumElements())
1955     return false;
1956
1957   assert(EndIndex > BeginIndex && "Empty vector!");
1958   uint64_t NumElements = EndIndex - BeginIndex;
1959   Type *SliceTy = (NumElements == 1)
1960                       ? Ty->getElementType()
1961                       : VectorType::get(Ty->getElementType(), NumElements);
1962
1963   Type *SplitIntTy =
1964       Type::getIntNTy(Ty->getContext(), NumElements * ElementSize * 8);
1965
1966   Use *U = S.getUse();
1967
1968   if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(U->getUser())) {
1969     if (MI->isVolatile())
1970       return false;
1971     if (!S.isSplittable())
1972       return false; // Skip any unsplittable intrinsics.
1973   } else if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(U->getUser())) {
1974     if (II->getIntrinsicID() != Intrinsic::lifetime_start &&
1975         II->getIntrinsicID() != Intrinsic::lifetime_end)
1976       return false;
1977   } else if (U->get()->getType()->getPointerElementType()->isStructTy()) {
1978     // Disable vector promotion when there are loads or stores of an FCA.
1979     return false;
1980   } else if (LoadInst *LI = dyn_cast<LoadInst>(U->getUser())) {
1981     if (LI->isVolatile())
1982       return false;
1983     Type *LTy = LI->getType();
1984     if (P.beginOffset() > S.beginOffset() || P.endOffset() < S.endOffset()) {
1985       assert(LTy->isIntegerTy());
1986       LTy = SplitIntTy;
1987     }
1988     if (!canConvertValue(DL, SliceTy, LTy))
1989       return false;
1990   } else if (StoreInst *SI = dyn_cast<StoreInst>(U->getUser())) {
1991     if (SI->isVolatile())
1992       return false;
1993     Type *STy = SI->getValueOperand()->getType();
1994     if (P.beginOffset() > S.beginOffset() || P.endOffset() < S.endOffset()) {
1995       assert(STy->isIntegerTy());
1996       STy = SplitIntTy;
1997     }
1998     if (!canConvertValue(DL, STy, SliceTy))
1999       return false;
2000   } else {
2001     return false;
2002   }
2003
2004   return true;
2005 }
2006
2007 /// \brief Test whether the given alloca partitioning and range of slices can be
2008 /// promoted to a vector.
2009 ///
2010 /// This is a quick test to check whether we can rewrite a particular alloca
2011 /// partition (and its newly formed alloca) into a vector alloca with only
2012 /// whole-vector loads and stores such that it could be promoted to a vector
2013 /// SSA value. We only can ensure this for a limited set of operations, and we
2014 /// don't want to do the rewrites unless we are confident that the result will
2015 /// be promotable, so we have an early test here.
2016 static VectorType *isVectorPromotionViable(AllocaSlices::Partition &P,
2017                                            const DataLayout &DL) {
2018   // Collect the candidate types for vector-based promotion. Also track whether
2019   // we have different element types.
2020   SmallVector<VectorType *, 4> CandidateTys;
2021   Type *CommonEltTy = nullptr;
2022   bool HaveCommonEltTy = true;
2023   auto CheckCandidateType = [&](Type *Ty) {
2024     if (auto *VTy = dyn_cast<VectorType>(Ty)) {
2025       CandidateTys.push_back(VTy);
2026       if (!CommonEltTy)
2027         CommonEltTy = VTy->getElementType();
2028       else if (CommonEltTy != VTy->getElementType())
2029         HaveCommonEltTy = false;
2030     }
2031   };
2032   // Consider any loads or stores that are the exact size of the slice.
2033   for (const Slice &S : P)
2034     if (S.beginOffset() == P.beginOffset() &&
2035         S.endOffset() == P.endOffset()) {
2036       if (auto *LI = dyn_cast<LoadInst>(S.getUse()->getUser()))
2037         CheckCandidateType(LI->getType());
2038       else if (auto *SI = dyn_cast<StoreInst>(S.getUse()->getUser()))
2039         CheckCandidateType(SI->getValueOperand()->getType());
2040     }
2041
2042   // If we didn't find a vector type, nothing to do here.
2043   if (CandidateTys.empty())
2044     return nullptr;
2045
2046   // Remove non-integer vector types if we had multiple common element types.
2047   // FIXME: It'd be nice to replace them with integer vector types, but we can't
2048   // do that until all the backends are known to produce good code for all
2049   // integer vector types.
2050   if (!HaveCommonEltTy) {
2051     CandidateTys.erase(std::remove_if(CandidateTys.begin(), CandidateTys.end(),
2052                                       [](VectorType *VTy) {
2053                          return !VTy->getElementType()->isIntegerTy();
2054                        }),
2055                        CandidateTys.end());
2056
2057     // If there were no integer vector types, give up.
2058     if (CandidateTys.empty())
2059       return nullptr;
2060
2061     // Rank the remaining candidate vector types. This is easy because we know
2062     // they're all integer vectors. We sort by ascending number of elements.
2063     auto RankVectorTypes = [&DL](VectorType *RHSTy, VectorType *LHSTy) {
2064       assert(DL.getTypeSizeInBits(RHSTy) == DL.getTypeSizeInBits(LHSTy) &&
2065              "Cannot have vector types of different sizes!");
2066       assert(RHSTy->getElementType()->isIntegerTy() &&
2067              "All non-integer types eliminated!");
2068       assert(LHSTy->getElementType()->isIntegerTy() &&
2069              "All non-integer types eliminated!");
2070       return RHSTy->getNumElements() < LHSTy->getNumElements();
2071     };
2072     std::sort(CandidateTys.begin(), CandidateTys.end(), RankVectorTypes);
2073     CandidateTys.erase(
2074         std::unique(CandidateTys.begin(), CandidateTys.end(), RankVectorTypes),
2075         CandidateTys.end());
2076   } else {
2077 // The only way to have the same element type in every vector type is to
2078 // have the same vector type. Check that and remove all but one.
2079 #ifndef NDEBUG
2080     for (VectorType *VTy : CandidateTys) {
2081       assert(VTy->getElementType() == CommonEltTy &&
2082              "Unaccounted for element type!");
2083       assert(VTy == CandidateTys[0] &&
2084              "Different vector types with the same element type!");
2085     }
2086 #endif
2087     CandidateTys.resize(1);
2088   }
2089
2090   // Try each vector type, and return the one which works.
2091   auto CheckVectorTypeForPromotion = [&](VectorType *VTy) {
2092     uint64_t ElementSize = DL.getTypeSizeInBits(VTy->getElementType());
2093
2094     // While the definition of LLVM vectors is bitpacked, we don't support sizes
2095     // that aren't byte sized.
2096     if (ElementSize % 8)
2097       return false;
2098     assert((DL.getTypeSizeInBits(VTy) % 8) == 0 &&
2099            "vector size not a multiple of element size?");
2100     ElementSize /= 8;
2101
2102     for (const Slice &S : P)
2103       if (!isVectorPromotionViableForSlice(P, S, VTy, ElementSize, DL))
2104         return false;
2105
2106     for (const Slice *S : P.splitSliceTails())
2107       if (!isVectorPromotionViableForSlice(P, *S, VTy, ElementSize, DL))
2108         return false;
2109
2110     return true;
2111   };
2112   for (VectorType *VTy : CandidateTys)
2113     if (CheckVectorTypeForPromotion(VTy))
2114       return VTy;
2115
2116   return nullptr;
2117 }
2118
2119 /// \brief Test whether a slice of an alloca is valid for integer widening.
2120 ///
2121 /// This implements the necessary checking for the \c isIntegerWideningViable
2122 /// test below on a single slice of the alloca.
2123 static bool isIntegerWideningViableForSlice(const Slice &S,
2124                                             uint64_t AllocBeginOffset,
2125                                             Type *AllocaTy,
2126                                             const DataLayout &DL,
2127                                             bool &WholeAllocaOp) {
2128   uint64_t Size = DL.getTypeStoreSize(AllocaTy);
2129
2130   uint64_t RelBegin = S.beginOffset() - AllocBeginOffset;
2131   uint64_t RelEnd = S.endOffset() - AllocBeginOffset;
2132
2133   // We can't reasonably handle cases where the load or store extends past
2134   // the end of the alloca's type and into its padding.
2135   if (RelEnd > Size)
2136     return false;
2137
2138   Use *U = S.getUse();
2139
2140   if (LoadInst *LI = dyn_cast<LoadInst>(U->getUser())) {
2141     if (LI->isVolatile())
2142       return false;
2143     // We can't handle loads that extend past the allocated memory.
2144     if (DL.getTypeStoreSize(LI->getType()) > Size)
2145       return false;
2146     // Note that we don't count vector loads or stores as whole-alloca
2147     // operations which enable integer widening because we would prefer to use
2148     // vector widening instead.
2149     if (!isa<VectorType>(LI->getType()) && RelBegin == 0 && RelEnd == Size)
2150       WholeAllocaOp = true;
2151     if (IntegerType *ITy = dyn_cast<IntegerType>(LI->getType())) {
2152       if (ITy->getBitWidth() < DL.getTypeStoreSizeInBits(ITy))
2153         return false;
2154     } else if (RelBegin != 0 || RelEnd != Size ||
2155                !canConvertValue(DL, AllocaTy, LI->getType())) {
2156       // Non-integer loads need to be convertible from the alloca type so that
2157       // they are promotable.
2158       return false;
2159     }
2160   } else if (StoreInst *SI = dyn_cast<StoreInst>(U->getUser())) {
2161     Type *ValueTy = SI->getValueOperand()->getType();
2162     if (SI->isVolatile())
2163       return false;
2164     // We can't handle stores that extend past the allocated memory.
2165     if (DL.getTypeStoreSize(ValueTy) > Size)
2166       return false;
2167     // Note that we don't count vector loads or stores as whole-alloca
2168     // operations which enable integer widening because we would prefer to use
2169     // vector widening instead.
2170     if (!isa<VectorType>(ValueTy) && RelBegin == 0 && RelEnd == Size)
2171       WholeAllocaOp = true;
2172     if (IntegerType *ITy = dyn_cast<IntegerType>(ValueTy)) {
2173       if (ITy->getBitWidth() < DL.getTypeStoreSizeInBits(ITy))
2174         return false;
2175     } else if (RelBegin != 0 || RelEnd != Size ||
2176                !canConvertValue(DL, ValueTy, AllocaTy)) {
2177       // Non-integer stores need to be convertible to the alloca type so that
2178       // they are promotable.
2179       return false;
2180     }
2181   } else if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(U->getUser())) {
2182     if (MI->isVolatile() || !isa<Constant>(MI->getLength()))
2183       return false;
2184     if (!S.isSplittable())
2185       return false; // Skip any unsplittable intrinsics.
2186   } else if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(U->getUser())) {
2187     if (II->getIntrinsicID() != Intrinsic::lifetime_start &&
2188         II->getIntrinsicID() != Intrinsic::lifetime_end)
2189       return false;
2190   } else {
2191     return false;
2192   }
2193
2194   return true;
2195 }
2196
2197 /// \brief Test whether the given alloca partition's integer operations can be
2198 /// widened to promotable ones.
2199 ///
2200 /// This is a quick test to check whether we can rewrite the integer loads and
2201 /// stores to a particular alloca into wider loads and stores and be able to
2202 /// promote the resulting alloca.
2203 static bool isIntegerWideningViable(AllocaSlices::Partition &P, Type *AllocaTy,
2204                                     const DataLayout &DL) {
2205   uint64_t SizeInBits = DL.getTypeSizeInBits(AllocaTy);
2206   // Don't create integer types larger than the maximum bitwidth.
2207   if (SizeInBits > IntegerType::MAX_INT_BITS)
2208     return false;
2209
2210   // Don't try to handle allocas with bit-padding.
2211   if (SizeInBits != DL.getTypeStoreSizeInBits(AllocaTy))
2212     return false;
2213
2214   // We need to ensure that an integer type with the appropriate bitwidth can
2215   // be converted to the alloca type, whatever that is. We don't want to force
2216   // the alloca itself to have an integer type if there is a more suitable one.
2217   Type *IntTy = Type::getIntNTy(AllocaTy->getContext(), SizeInBits);
2218   if (!canConvertValue(DL, AllocaTy, IntTy) ||
2219       !canConvertValue(DL, IntTy, AllocaTy))
2220     return false;
2221
2222   // While examining uses, we ensure that the alloca has a covering load or
2223   // store. We don't want to widen the integer operations only to fail to
2224   // promote due to some other unsplittable entry (which we may make splittable
2225   // later). However, if there are only splittable uses, go ahead and assume
2226   // that we cover the alloca.
2227   // FIXME: We shouldn't consider split slices that happen to start in the
2228   // partition here...
2229   bool WholeAllocaOp =
2230       P.begin() != P.end() ? false : DL.isLegalInteger(SizeInBits);
2231
2232   for (const Slice &S : P)
2233     if (!isIntegerWideningViableForSlice(S, P.beginOffset(), AllocaTy, DL,
2234                                          WholeAllocaOp))
2235       return false;
2236
2237   for (const Slice *S : P.splitSliceTails())
2238     if (!isIntegerWideningViableForSlice(*S, P.beginOffset(), AllocaTy, DL,
2239                                          WholeAllocaOp))
2240       return false;
2241
2242   return WholeAllocaOp;
2243 }
2244
2245 static Value *extractInteger(const DataLayout &DL, IRBuilderTy &IRB, Value *V,
2246                              IntegerType *Ty, uint64_t Offset,
2247                              const Twine &Name) {
2248   DEBUG(dbgs() << "       start: " << *V << "\n");
2249   IntegerType *IntTy = cast<IntegerType>(V->getType());
2250   assert(DL.getTypeStoreSize(Ty) + Offset <= DL.getTypeStoreSize(IntTy) &&
2251          "Element extends past full value");
2252   uint64_t ShAmt = 8 * Offset;
2253   if (DL.isBigEndian())
2254     ShAmt = 8 * (DL.getTypeStoreSize(IntTy) - DL.getTypeStoreSize(Ty) - Offset);
2255   if (ShAmt) {
2256     V = IRB.CreateLShr(V, ShAmt, Name + ".shift");
2257     DEBUG(dbgs() << "     shifted: " << *V << "\n");
2258   }
2259   assert(Ty->getBitWidth() <= IntTy->getBitWidth() &&
2260          "Cannot extract to a larger integer!");
2261   if (Ty != IntTy) {
2262     V = IRB.CreateTrunc(V, Ty, Name + ".trunc");
2263     DEBUG(dbgs() << "     trunced: " << *V << "\n");
2264   }
2265   return V;
2266 }
2267
2268 static Value *insertInteger(const DataLayout &DL, IRBuilderTy &IRB, Value *Old,
2269                             Value *V, uint64_t Offset, const Twine &Name) {
2270   IntegerType *IntTy = cast<IntegerType>(Old->getType());
2271   IntegerType *Ty = cast<IntegerType>(V->getType());
2272   assert(Ty->getBitWidth() <= IntTy->getBitWidth() &&
2273          "Cannot insert a larger integer!");
2274   DEBUG(dbgs() << "       start: " << *V << "\n");
2275   if (Ty != IntTy) {
2276     V = IRB.CreateZExt(V, IntTy, Name + ".ext");
2277     DEBUG(dbgs() << "    extended: " << *V << "\n");
2278   }
2279   assert(DL.getTypeStoreSize(Ty) + Offset <= DL.getTypeStoreSize(IntTy) &&
2280          "Element store outside of alloca store");
2281   uint64_t ShAmt = 8 * Offset;
2282   if (DL.isBigEndian())
2283     ShAmt = 8 * (DL.getTypeStoreSize(IntTy) - DL.getTypeStoreSize(Ty) - Offset);
2284   if (ShAmt) {
2285     V = IRB.CreateShl(V, ShAmt, Name + ".shift");
2286     DEBUG(dbgs() << "     shifted: " << *V << "\n");
2287   }
2288
2289   if (ShAmt || Ty->getBitWidth() < IntTy->getBitWidth()) {
2290     APInt Mask = ~Ty->getMask().zext(IntTy->getBitWidth()).shl(ShAmt);
2291     Old = IRB.CreateAnd(Old, Mask, Name + ".mask");
2292     DEBUG(dbgs() << "      masked: " << *Old << "\n");
2293     V = IRB.CreateOr(Old, V, Name + ".insert");
2294     DEBUG(dbgs() << "    inserted: " << *V << "\n");
2295   }
2296   return V;
2297 }
2298
2299 static Value *extractVector(IRBuilderTy &IRB, Value *V, unsigned BeginIndex,
2300                             unsigned EndIndex, const Twine &Name) {
2301   VectorType *VecTy = cast<VectorType>(V->getType());
2302   unsigned NumElements = EndIndex - BeginIndex;
2303   assert(NumElements <= VecTy->getNumElements() && "Too many elements!");
2304
2305   if (NumElements == VecTy->getNumElements())
2306     return V;
2307
2308   if (NumElements == 1) {
2309     V = IRB.CreateExtractElement(V, IRB.getInt32(BeginIndex),
2310                                  Name + ".extract");
2311     DEBUG(dbgs() << "     extract: " << *V << "\n");
2312     return V;
2313   }
2314
2315   SmallVector<Constant *, 8> Mask;
2316   Mask.reserve(NumElements);
2317   for (unsigned i = BeginIndex; i != EndIndex; ++i)
2318     Mask.push_back(IRB.getInt32(i));
2319   V = IRB.CreateShuffleVector(V, UndefValue::get(V->getType()),
2320                               ConstantVector::get(Mask), Name + ".extract");
2321   DEBUG(dbgs() << "     shuffle: " << *V << "\n");
2322   return V;
2323 }
2324
2325 static Value *insertVector(IRBuilderTy &IRB, Value *Old, Value *V,
2326                            unsigned BeginIndex, const Twine &Name) {
2327   VectorType *VecTy = cast<VectorType>(Old->getType());
2328   assert(VecTy && "Can only insert a vector into a vector");
2329
2330   VectorType *Ty = dyn_cast<VectorType>(V->getType());
2331   if (!Ty) {
2332     // Single element to insert.
2333     V = IRB.CreateInsertElement(Old, V, IRB.getInt32(BeginIndex),
2334                                 Name + ".insert");
2335     DEBUG(dbgs() << "     insert: " << *V << "\n");
2336     return V;
2337   }
2338
2339   assert(Ty->getNumElements() <= VecTy->getNumElements() &&
2340          "Too many elements!");
2341   if (Ty->getNumElements() == VecTy->getNumElements()) {
2342     assert(V->getType() == VecTy && "Vector type mismatch");
2343     return V;
2344   }
2345   unsigned EndIndex = BeginIndex + Ty->getNumElements();
2346
2347   // When inserting a smaller vector into the larger to store, we first
2348   // use a shuffle vector to widen it with undef elements, and then
2349   // a second shuffle vector to select between the loaded vector and the
2350   // incoming vector.
2351   SmallVector<Constant *, 8> Mask;
2352   Mask.reserve(VecTy->getNumElements());
2353   for (unsigned i = 0; i != VecTy->getNumElements(); ++i)
2354     if (i >= BeginIndex && i < EndIndex)
2355       Mask.push_back(IRB.getInt32(i - BeginIndex));
2356     else
2357       Mask.push_back(UndefValue::get(IRB.getInt32Ty()));
2358   V = IRB.CreateShuffleVector(V, UndefValue::get(V->getType()),
2359                               ConstantVector::get(Mask), Name + ".expand");
2360   DEBUG(dbgs() << "    shuffle: " << *V << "\n");
2361
2362   Mask.clear();
2363   for (unsigned i = 0; i != VecTy->getNumElements(); ++i)
2364     Mask.push_back(IRB.getInt1(i >= BeginIndex && i < EndIndex));
2365
2366   V = IRB.CreateSelect(ConstantVector::get(Mask), V, Old, Name + "blend");
2367
2368   DEBUG(dbgs() << "    blend: " << *V << "\n");
2369   return V;
2370 }
2371
2372 namespace {
2373 /// \brief Visitor to rewrite instructions using p particular slice of an alloca
2374 /// to use a new alloca.
2375 ///
2376 /// Also implements the rewriting to vector-based accesses when the partition
2377 /// passes the isVectorPromotionViable predicate. Most of the rewriting logic
2378 /// lives here.
2379 class AllocaSliceRewriter : public InstVisitor<AllocaSliceRewriter, bool> {
2380   // Befriend the base class so it can delegate to private visit methods.
2381   friend class llvm::InstVisitor<AllocaSliceRewriter, bool>;
2382   typedef llvm::InstVisitor<AllocaSliceRewriter, bool> Base;
2383
2384   const DataLayout &DL;
2385   AllocaSlices &AS;
2386   SROA &Pass;
2387   AllocaInst &OldAI, &NewAI;
2388   const uint64_t NewAllocaBeginOffset, NewAllocaEndOffset;
2389   Type *NewAllocaTy;
2390
2391   // This is a convenience and flag variable that will be null unless the new
2392   // alloca's integer operations should be widened to this integer type due to
2393   // passing isIntegerWideningViable above. If it is non-null, the desired
2394   // integer type will be stored here for easy access during rewriting.
2395   IntegerType *IntTy;
2396
2397   // If we are rewriting an alloca partition which can be written as pure
2398   // vector operations, we stash extra information here. When VecTy is
2399   // non-null, we have some strict guarantees about the rewritten alloca:
2400   //   - The new alloca is exactly the size of the vector type here.
2401   //   - The accesses all either map to the entire vector or to a single
2402   //     element.
2403   //   - The set of accessing instructions is only one of those handled above
2404   //     in isVectorPromotionViable. Generally these are the same access kinds
2405   //     which are promotable via mem2reg.
2406   VectorType *VecTy;
2407   Type *ElementTy;
2408   uint64_t ElementSize;
2409
2410   // The original offset of the slice currently being rewritten relative to
2411   // the original alloca.
2412   uint64_t BeginOffset, EndOffset;
2413   // The new offsets of the slice currently being rewritten relative to the
2414   // original alloca.
2415   uint64_t NewBeginOffset, NewEndOffset;
2416
2417   uint64_t SliceSize;
2418   bool IsSplittable;
2419   bool IsSplit;
2420   Use *OldUse;
2421   Instruction *OldPtr;
2422
2423   // Track post-rewrite users which are PHI nodes and Selects.
2424   SmallPtrSetImpl<PHINode *> &PHIUsers;
2425   SmallPtrSetImpl<SelectInst *> &SelectUsers;
2426
2427   // Utility IR builder, whose name prefix is setup for each visited use, and
2428   // the insertion point is set to point to the user.
2429   IRBuilderTy IRB;
2430
2431 public:
2432   AllocaSliceRewriter(const DataLayout &DL, AllocaSlices &AS, SROA &Pass,
2433                       AllocaInst &OldAI, AllocaInst &NewAI,
2434                       uint64_t NewAllocaBeginOffset,
2435                       uint64_t NewAllocaEndOffset, bool IsIntegerPromotable,
2436                       VectorType *PromotableVecTy,
2437                       SmallPtrSetImpl<PHINode *> &PHIUsers,
2438                       SmallPtrSetImpl<SelectInst *> &SelectUsers)
2439       : DL(DL), AS(AS), Pass(Pass), OldAI(OldAI), NewAI(NewAI),
2440         NewAllocaBeginOffset(NewAllocaBeginOffset),
2441         NewAllocaEndOffset(NewAllocaEndOffset),
2442         NewAllocaTy(NewAI.getAllocatedType()),
2443         IntTy(IsIntegerPromotable
2444                   ? Type::getIntNTy(
2445                         NewAI.getContext(),
2446                         DL.getTypeSizeInBits(NewAI.getAllocatedType()))
2447                   : nullptr),
2448         VecTy(PromotableVecTy),
2449         ElementTy(VecTy ? VecTy->getElementType() : nullptr),
2450         ElementSize(VecTy ? DL.getTypeSizeInBits(ElementTy) / 8 : 0),
2451         BeginOffset(), EndOffset(), IsSplittable(), IsSplit(), OldUse(),
2452         OldPtr(), PHIUsers(PHIUsers), SelectUsers(SelectUsers),
2453         IRB(NewAI.getContext(), ConstantFolder()) {
2454     if (VecTy) {
2455       assert((DL.getTypeSizeInBits(ElementTy) % 8) == 0 &&
2456              "Only multiple-of-8 sized vector elements are viable");
2457       ++NumVectorized;
2458     }
2459     assert((!IntTy && !VecTy) || (IntTy && !VecTy) || (!IntTy && VecTy));
2460   }
2461
2462   bool visit(AllocaSlices::const_iterator I) {
2463     bool CanSROA = true;
2464     BeginOffset = I->beginOffset();
2465     EndOffset = I->endOffset();
2466     IsSplittable = I->isSplittable();
2467     IsSplit =
2468         BeginOffset < NewAllocaBeginOffset || EndOffset > NewAllocaEndOffset;
2469     DEBUG(dbgs() << "  rewriting " << (IsSplit ? "split " : ""));
2470     DEBUG(AS.printSlice(dbgs(), I, ""));
2471     DEBUG(dbgs() << "\n");
2472
2473     // Compute the intersecting offset range.
2474     assert(BeginOffset < NewAllocaEndOffset);
2475     assert(EndOffset > NewAllocaBeginOffset);
2476     NewBeginOffset = std::max(BeginOffset, NewAllocaBeginOffset);
2477     NewEndOffset = std::min(EndOffset, NewAllocaEndOffset);
2478
2479     SliceSize = NewEndOffset - NewBeginOffset;
2480
2481     OldUse = I->getUse();
2482     OldPtr = cast<Instruction>(OldUse->get());
2483
2484     Instruction *OldUserI = cast<Instruction>(OldUse->getUser());
2485     IRB.SetInsertPoint(OldUserI);
2486     IRB.SetCurrentDebugLocation(OldUserI->getDebugLoc());
2487     IRB.SetNamePrefix(Twine(NewAI.getName()) + "." + Twine(BeginOffset) + ".");
2488
2489     CanSROA &= visit(cast<Instruction>(OldUse->getUser()));
2490     if (VecTy || IntTy)
2491       assert(CanSROA);
2492     return CanSROA;
2493   }
2494
2495 private:
2496   // Make sure the other visit overloads are visible.
2497   using Base::visit;
2498
2499   // Every instruction which can end up as a user must have a rewrite rule.
2500   bool visitInstruction(Instruction &I) {
2501     DEBUG(dbgs() << "    !!!! Cannot rewrite: " << I << "\n");
2502     llvm_unreachable("No rewrite rule for this instruction!");
2503   }
2504
2505   Value *getNewAllocaSlicePtr(IRBuilderTy &IRB, Type *PointerTy) {
2506     // Note that the offset computation can use BeginOffset or NewBeginOffset
2507     // interchangeably for unsplit slices.
2508     assert(IsSplit || BeginOffset == NewBeginOffset);
2509     uint64_t Offset = NewBeginOffset - NewAllocaBeginOffset;
2510
2511 #ifndef NDEBUG
2512     StringRef OldName = OldPtr->getName();
2513     // Skip through the last '.sroa.' component of the name.
2514     size_t LastSROAPrefix = OldName.rfind(".sroa.");
2515     if (LastSROAPrefix != StringRef::npos) {
2516       OldName = OldName.substr(LastSROAPrefix + strlen(".sroa."));
2517       // Look for an SROA slice index.
2518       size_t IndexEnd = OldName.find_first_not_of("0123456789");
2519       if (IndexEnd != StringRef::npos && OldName[IndexEnd] == '.') {
2520         // Strip the index and look for the offset.
2521         OldName = OldName.substr(IndexEnd + 1);
2522         size_t OffsetEnd = OldName.find_first_not_of("0123456789");
2523         if (OffsetEnd != StringRef::npos && OldName[OffsetEnd] == '.')
2524           // Strip the offset.
2525           OldName = OldName.substr(OffsetEnd + 1);
2526       }
2527     }
2528     // Strip any SROA suffixes as well.
2529     OldName = OldName.substr(0, OldName.find(".sroa_"));
2530 #endif
2531
2532     return getAdjustedPtr(IRB, DL, &NewAI,
2533                           APInt(DL.getPointerSizeInBits(), Offset), PointerTy,
2534 #ifndef NDEBUG
2535                           Twine(OldName) + "."
2536 #else
2537                           Twine()
2538 #endif
2539                           );
2540   }
2541
2542   /// \brief Compute suitable alignment to access this slice of the *new*
2543   /// alloca.
2544   ///
2545   /// You can optionally pass a type to this routine and if that type's ABI
2546   /// alignment is itself suitable, this will return zero.
2547   unsigned getSliceAlign(Type *Ty = nullptr) {
2548     unsigned NewAIAlign = NewAI.getAlignment();
2549     if (!NewAIAlign)
2550       NewAIAlign = DL.getABITypeAlignment(NewAI.getAllocatedType());
2551     unsigned Align =
2552         MinAlign(NewAIAlign, NewBeginOffset - NewAllocaBeginOffset);
2553     return (Ty && Align == DL.getABITypeAlignment(Ty)) ? 0 : Align;
2554   }
2555
2556   unsigned getIndex(uint64_t Offset) {
2557     assert(VecTy && "Can only call getIndex when rewriting a vector");
2558     uint64_t RelOffset = Offset - NewAllocaBeginOffset;
2559     assert(RelOffset / ElementSize < UINT32_MAX && "Index out of bounds");
2560     uint32_t Index = RelOffset / ElementSize;
2561     assert(Index * ElementSize == RelOffset);
2562     return Index;
2563   }
2564
2565   void deleteIfTriviallyDead(Value *V) {
2566     Instruction *I = cast<Instruction>(V);
2567     if (isInstructionTriviallyDead(I))
2568       Pass.DeadInsts.insert(I);
2569   }
2570
2571   Value *rewriteVectorizedLoadInst() {
2572     unsigned BeginIndex = getIndex(NewBeginOffset);
2573     unsigned EndIndex = getIndex(NewEndOffset);
2574     assert(EndIndex > BeginIndex && "Empty vector!");
2575
2576     Value *V = IRB.CreateAlignedLoad(&NewAI, NewAI.getAlignment(), "load");
2577     return extractVector(IRB, V, BeginIndex, EndIndex, "vec");
2578   }
2579
2580   Value *rewriteIntegerLoad(LoadInst &LI) {
2581     assert(IntTy && "We cannot insert an integer to the alloca");
2582     assert(!LI.isVolatile());
2583     Value *V = IRB.CreateAlignedLoad(&NewAI, NewAI.getAlignment(), "load");
2584     V = convertValue(DL, IRB, V, IntTy);
2585     assert(NewBeginOffset >= NewAllocaBeginOffset && "Out of bounds offset");
2586     uint64_t Offset = NewBeginOffset - NewAllocaBeginOffset;
2587     if (Offset > 0 || NewEndOffset < NewAllocaEndOffset)
2588       V = extractInteger(DL, IRB, V, cast<IntegerType>(LI.getType()), Offset,
2589                          "extract");
2590     return V;
2591   }
2592
2593   bool visitLoadInst(LoadInst &LI) {
2594     DEBUG(dbgs() << "    original: " << LI << "\n");
2595     Value *OldOp = LI.getOperand(0);
2596     assert(OldOp == OldPtr);
2597
2598     Type *TargetTy = IsSplit ? Type::getIntNTy(LI.getContext(), SliceSize * 8)
2599                              : LI.getType();
2600     const bool IsLoadPastEnd = DL.getTypeStoreSize(TargetTy) > SliceSize;
2601     bool IsPtrAdjusted = false;
2602     Value *V;
2603     if (VecTy) {
2604       V = rewriteVectorizedLoadInst();
2605     } else if (IntTy && LI.getType()->isIntegerTy()) {
2606       V = rewriteIntegerLoad(LI);
2607     } else if (NewBeginOffset == NewAllocaBeginOffset &&
2608                NewEndOffset == NewAllocaEndOffset &&
2609                (canConvertValue(DL, NewAllocaTy, TargetTy) ||
2610                 (IsLoadPastEnd && NewAllocaTy->isIntegerTy() &&
2611                  TargetTy->isIntegerTy()))) {
2612       LoadInst *NewLI = IRB.CreateAlignedLoad(&NewAI, NewAI.getAlignment(),
2613                                               LI.isVolatile(), LI.getName());
2614       if (LI.isVolatile())
2615         NewLI->setAtomic(LI.getOrdering(), LI.getSynchScope());
2616       V = NewLI;
2617
2618       // If this is an integer load past the end of the slice (which means the
2619       // bytes outside the slice are undef or this load is dead) just forcibly
2620       // fix the integer size with correct handling of endianness.
2621       if (auto *AITy = dyn_cast<IntegerType>(NewAllocaTy))
2622         if (auto *TITy = dyn_cast<IntegerType>(TargetTy))
2623           if (AITy->getBitWidth() < TITy->getBitWidth()) {
2624             V = IRB.CreateZExt(V, TITy, "load.ext");
2625             if (DL.isBigEndian())
2626               V = IRB.CreateShl(V, TITy->getBitWidth() - AITy->getBitWidth(),
2627                                 "endian_shift");
2628           }
2629     } else {
2630       Type *LTy = TargetTy->getPointerTo();
2631       LoadInst *NewLI = IRB.CreateAlignedLoad(getNewAllocaSlicePtr(IRB, LTy),
2632                                               getSliceAlign(TargetTy),
2633                                               LI.isVolatile(), LI.getName());
2634       if (LI.isVolatile())
2635         NewLI->setAtomic(LI.getOrdering(), LI.getSynchScope());
2636
2637       V = NewLI;
2638       IsPtrAdjusted = true;
2639     }
2640     V = convertValue(DL, IRB, V, TargetTy);
2641
2642     if (IsSplit) {
2643       assert(!LI.isVolatile());
2644       assert(LI.getType()->isIntegerTy() &&
2645              "Only integer type loads and stores are split");
2646       assert(SliceSize < DL.getTypeStoreSize(LI.getType()) &&
2647              "Split load isn't smaller than original load");
2648       assert(LI.getType()->getIntegerBitWidth() ==
2649                  DL.getTypeStoreSizeInBits(LI.getType()) &&
2650              "Non-byte-multiple bit width");
2651       // Move the insertion point just past the load so that we can refer to it.
2652       IRB.SetInsertPoint(std::next(BasicBlock::iterator(&LI)));
2653       // Create a placeholder value with the same type as LI to use as the
2654       // basis for the new value. This allows us to replace the uses of LI with
2655       // the computed value, and then replace the placeholder with LI, leaving
2656       // LI only used for this computation.
2657       Value *Placeholder =
2658           new LoadInst(UndefValue::get(LI.getType()->getPointerTo()));
2659       V = insertInteger(DL, IRB, Placeholder, V, NewBeginOffset - BeginOffset,
2660                         "insert");
2661       LI.replaceAllUsesWith(V);
2662       Placeholder->replaceAllUsesWith(&LI);
2663       delete Placeholder;
2664     } else {
2665       LI.replaceAllUsesWith(V);
2666     }
2667
2668     Pass.DeadInsts.insert(&LI);
2669     deleteIfTriviallyDead(OldOp);
2670     DEBUG(dbgs() << "          to: " << *V << "\n");
2671     return !LI.isVolatile() && !IsPtrAdjusted;
2672   }
2673
2674   bool rewriteVectorizedStoreInst(Value *V, StoreInst &SI, Value *OldOp) {
2675     if (V->getType() != VecTy) {
2676       unsigned BeginIndex = getIndex(NewBeginOffset);
2677       unsigned EndIndex = getIndex(NewEndOffset);
2678       assert(EndIndex > BeginIndex && "Empty vector!");
2679       unsigned NumElements = EndIndex - BeginIndex;
2680       assert(NumElements <= VecTy->getNumElements() && "Too many elements!");
2681       Type *SliceTy = (NumElements == 1)
2682                           ? ElementTy
2683                           : VectorType::get(ElementTy, NumElements);
2684       if (V->getType() != SliceTy)
2685         V = convertValue(DL, IRB, V, SliceTy);
2686
2687       // Mix in the existing elements.
2688       Value *Old = IRB.CreateAlignedLoad(&NewAI, NewAI.getAlignment(), "load");
2689       V = insertVector(IRB, Old, V, BeginIndex, "vec");
2690     }
2691     StoreInst *Store = IRB.CreateAlignedStore(V, &NewAI, NewAI.getAlignment());
2692     Pass.DeadInsts.insert(&SI);
2693
2694     (void)Store;
2695     DEBUG(dbgs() << "          to: " << *Store << "\n");
2696     return true;
2697   }
2698
2699   bool rewriteIntegerStore(Value *V, StoreInst &SI) {
2700     assert(IntTy && "We cannot extract an integer from the alloca");
2701     assert(!SI.isVolatile());
2702     if (DL.getTypeSizeInBits(V->getType()) != IntTy->getBitWidth()) {
2703       Value *Old =
2704           IRB.CreateAlignedLoad(&NewAI, NewAI.getAlignment(), "oldload");
2705       Old = convertValue(DL, IRB, Old, IntTy);
2706       assert(BeginOffset >= NewAllocaBeginOffset && "Out of bounds offset");
2707       uint64_t Offset = BeginOffset - NewAllocaBeginOffset;
2708       V = insertInteger(DL, IRB, Old, SI.getValueOperand(), Offset, "insert");
2709     }
2710     V = convertValue(DL, IRB, V, NewAllocaTy);
2711     StoreInst *Store = IRB.CreateAlignedStore(V, &NewAI, NewAI.getAlignment());
2712     Pass.DeadInsts.insert(&SI);
2713     (void)Store;
2714     DEBUG(dbgs() << "          to: " << *Store << "\n");
2715     return true;
2716   }
2717
2718   bool visitStoreInst(StoreInst &SI) {
2719     DEBUG(dbgs() << "    original: " << SI << "\n");
2720     Value *OldOp = SI.getOperand(1);
2721     assert(OldOp == OldPtr);
2722
2723     Value *V = SI.getValueOperand();
2724
2725     // Strip all inbounds GEPs and pointer casts to try to dig out any root
2726     // alloca that should be re-examined after promoting this alloca.
2727     if (V->getType()->isPointerTy())
2728       if (AllocaInst *AI = dyn_cast<AllocaInst>(V->stripInBoundsOffsets()))
2729         Pass.PostPromotionWorklist.insert(AI);
2730
2731     if (SliceSize < DL.getTypeStoreSize(V->getType())) {
2732       assert(!SI.isVolatile());
2733       assert(V->getType()->isIntegerTy() &&
2734              "Only integer type loads and stores are split");
2735       assert(V->getType()->getIntegerBitWidth() ==
2736                  DL.getTypeStoreSizeInBits(V->getType()) &&
2737              "Non-byte-multiple bit width");
2738       IntegerType *NarrowTy = Type::getIntNTy(SI.getContext(), SliceSize * 8);
2739       V = extractInteger(DL, IRB, V, NarrowTy, NewBeginOffset - BeginOffset,
2740                          "extract");
2741     }
2742
2743     if (VecTy)
2744       return rewriteVectorizedStoreInst(V, SI, OldOp);
2745     if (IntTy && V->getType()->isIntegerTy())
2746       return rewriteIntegerStore(V, SI);
2747
2748     const bool IsStorePastEnd = DL.getTypeStoreSize(V->getType()) > SliceSize;
2749     StoreInst *NewSI;
2750     if (NewBeginOffset == NewAllocaBeginOffset &&
2751         NewEndOffset == NewAllocaEndOffset &&
2752         (canConvertValue(DL, V->getType(), NewAllocaTy) ||
2753          (IsStorePastEnd && NewAllocaTy->isIntegerTy() &&
2754           V->getType()->isIntegerTy()))) {
2755       // If this is an integer store past the end of slice (and thus the bytes
2756       // past that point are irrelevant or this is unreachable), truncate the
2757       // value prior to storing.
2758       if (auto *VITy = dyn_cast<IntegerType>(V->getType()))
2759         if (auto *AITy = dyn_cast<IntegerType>(NewAllocaTy))
2760           if (VITy->getBitWidth() > AITy->getBitWidth()) {
2761             if (DL.isBigEndian())
2762               V = IRB.CreateLShr(V, VITy->getBitWidth() - AITy->getBitWidth(),
2763                                  "endian_shift");
2764             V = IRB.CreateTrunc(V, AITy, "load.trunc");
2765           }
2766
2767       V = convertValue(DL, IRB, V, NewAllocaTy);
2768       NewSI = IRB.CreateAlignedStore(V, &NewAI, NewAI.getAlignment(),
2769                                      SI.isVolatile());
2770     } else {
2771       Value *NewPtr = getNewAllocaSlicePtr(IRB, V->getType()->getPointerTo());
2772       NewSI = IRB.CreateAlignedStore(V, NewPtr, getSliceAlign(V->getType()),
2773                                      SI.isVolatile());
2774     }
2775     if (SI.isVolatile())
2776       NewSI->setAtomic(SI.getOrdering(), SI.getSynchScope());
2777     Pass.DeadInsts.insert(&SI);
2778     deleteIfTriviallyDead(OldOp);
2779
2780     DEBUG(dbgs() << "          to: " << *NewSI << "\n");
2781     return NewSI->getPointerOperand() == &NewAI && !SI.isVolatile();
2782   }
2783
2784   /// \brief Compute an integer value from splatting an i8 across the given
2785   /// number of bytes.
2786   ///
2787   /// Note that this routine assumes an i8 is a byte. If that isn't true, don't
2788   /// call this routine.
2789   /// FIXME: Heed the advice above.
2790   ///
2791   /// \param V The i8 value to splat.
2792   /// \param Size The number of bytes in the output (assuming i8 is one byte)
2793   Value *getIntegerSplat(Value *V, unsigned Size) {
2794     assert(Size > 0 && "Expected a positive number of bytes.");
2795     IntegerType *VTy = cast<IntegerType>(V->getType());
2796     assert(VTy->getBitWidth() == 8 && "Expected an i8 value for the byte");
2797     if (Size == 1)
2798       return V;
2799
2800     Type *SplatIntTy = Type::getIntNTy(VTy->getContext(), Size * 8);
2801     V = IRB.CreateMul(
2802         IRB.CreateZExt(V, SplatIntTy, "zext"),
2803         ConstantExpr::getUDiv(
2804             Constant::getAllOnesValue(SplatIntTy),
2805             ConstantExpr::getZExt(Constant::getAllOnesValue(V->getType()),
2806                                   SplatIntTy)),
2807         "isplat");
2808     return V;
2809   }
2810
2811   /// \brief Compute a vector splat for a given element value.
2812   Value *getVectorSplat(Value *V, unsigned NumElements) {
2813     V = IRB.CreateVectorSplat(NumElements, V, "vsplat");
2814     DEBUG(dbgs() << "       splat: " << *V << "\n");
2815     return V;
2816   }
2817
2818   bool visitMemSetInst(MemSetInst &II) {
2819     DEBUG(dbgs() << "    original: " << II << "\n");
2820     assert(II.getRawDest() == OldPtr);
2821
2822     // If the memset has a variable size, it cannot be split, just adjust the
2823     // pointer to the new alloca.
2824     if (!isa<Constant>(II.getLength())) {
2825       assert(!IsSplit);
2826       assert(NewBeginOffset == BeginOffset);
2827       II.setDest(getNewAllocaSlicePtr(IRB, OldPtr->getType()));
2828       Type *CstTy = II.getAlignmentCst()->getType();
2829       II.setAlignment(ConstantInt::get(CstTy, getSliceAlign()));
2830
2831       deleteIfTriviallyDead(OldPtr);
2832       return false;
2833     }
2834
2835     // Record this instruction for deletion.
2836     Pass.DeadInsts.insert(&II);
2837
2838     Type *AllocaTy = NewAI.getAllocatedType();
2839     Type *ScalarTy = AllocaTy->getScalarType();
2840
2841     // If this doesn't map cleanly onto the alloca type, and that type isn't
2842     // a single value type, just emit a memset.
2843     if (!VecTy && !IntTy &&
2844         (BeginOffset > NewAllocaBeginOffset || EndOffset < NewAllocaEndOffset ||
2845          SliceSize != DL.getTypeStoreSize(AllocaTy) ||
2846          !AllocaTy->isSingleValueType() ||
2847          !DL.isLegalInteger(DL.getTypeSizeInBits(ScalarTy)) ||
2848          DL.getTypeSizeInBits(ScalarTy) % 8 != 0)) {
2849       Type *SizeTy = II.getLength()->getType();
2850       Constant *Size = ConstantInt::get(SizeTy, NewEndOffset - NewBeginOffset);
2851       CallInst *New = IRB.CreateMemSet(
2852           getNewAllocaSlicePtr(IRB, OldPtr->getType()), II.getValue(), Size,
2853           getSliceAlign(), II.isVolatile());
2854       (void)New;
2855       DEBUG(dbgs() << "          to: " << *New << "\n");
2856       return false;
2857     }
2858
2859     // If we can represent this as a simple value, we have to build the actual
2860     // value to store, which requires expanding the byte present in memset to
2861     // a sensible representation for the alloca type. This is essentially
2862     // splatting the byte to a sufficiently wide integer, splatting it across
2863     // any desired vector width, and bitcasting to the final type.
2864     Value *V;
2865
2866     if (VecTy) {
2867       // If this is a memset of a vectorized alloca, insert it.
2868       assert(ElementTy == ScalarTy);
2869
2870       unsigned BeginIndex = getIndex(NewBeginOffset);
2871       unsigned EndIndex = getIndex(NewEndOffset);
2872       assert(EndIndex > BeginIndex && "Empty vector!");
2873       unsigned NumElements = EndIndex - BeginIndex;
2874       assert(NumElements <= VecTy->getNumElements() && "Too many elements!");
2875
2876       Value *Splat =
2877           getIntegerSplat(II.getValue(), DL.getTypeSizeInBits(ElementTy) / 8);
2878       Splat = convertValue(DL, IRB, Splat, ElementTy);
2879       if (NumElements > 1)
2880         Splat = getVectorSplat(Splat, NumElements);
2881
2882       Value *Old =
2883           IRB.CreateAlignedLoad(&NewAI, NewAI.getAlignment(), "oldload");
2884       V = insertVector(IRB, Old, Splat, BeginIndex, "vec");
2885     } else if (IntTy) {
2886       // If this is a memset on an alloca where we can widen stores, insert the
2887       // set integer.
2888       assert(!II.isVolatile());
2889
2890       uint64_t Size = NewEndOffset - NewBeginOffset;
2891       V = getIntegerSplat(II.getValue(), Size);
2892
2893       if (IntTy && (BeginOffset != NewAllocaBeginOffset ||
2894                     EndOffset != NewAllocaBeginOffset)) {
2895         Value *Old =
2896             IRB.CreateAlignedLoad(&NewAI, NewAI.getAlignment(), "oldload");
2897         Old = convertValue(DL, IRB, Old, IntTy);
2898         uint64_t Offset = NewBeginOffset - NewAllocaBeginOffset;
2899         V = insertInteger(DL, IRB, Old, V, Offset, "insert");
2900       } else {
2901         assert(V->getType() == IntTy &&
2902                "Wrong type for an alloca wide integer!");
2903       }
2904       V = convertValue(DL, IRB, V, AllocaTy);
2905     } else {
2906       // Established these invariants above.
2907       assert(NewBeginOffset == NewAllocaBeginOffset);
2908       assert(NewEndOffset == NewAllocaEndOffset);
2909
2910       V = getIntegerSplat(II.getValue(), DL.getTypeSizeInBits(ScalarTy) / 8);
2911       if (VectorType *AllocaVecTy = dyn_cast<VectorType>(AllocaTy))
2912         V = getVectorSplat(V, AllocaVecTy->getNumElements());
2913
2914       V = convertValue(DL, IRB, V, AllocaTy);
2915     }
2916
2917     Value *New = IRB.CreateAlignedStore(V, &NewAI, NewAI.getAlignment(),
2918                                         II.isVolatile());
2919     (void)New;
2920     DEBUG(dbgs() << "          to: " << *New << "\n");
2921     return !II.isVolatile();
2922   }
2923
2924   bool visitMemTransferInst(MemTransferInst &II) {
2925     // Rewriting of memory transfer instructions can be a bit tricky. We break
2926     // them into two categories: split intrinsics and unsplit intrinsics.
2927
2928     DEBUG(dbgs() << "    original: " << II << "\n");
2929
2930     bool IsDest = &II.getRawDestUse() == OldUse;
2931     assert((IsDest && II.getRawDest() == OldPtr) ||
2932            (!IsDest && II.getRawSource() == OldPtr));
2933
2934     unsigned SliceAlign = getSliceAlign();
2935
2936     // For unsplit intrinsics, we simply modify the source and destination
2937     // pointers in place. This isn't just an optimization, it is a matter of
2938     // correctness. With unsplit intrinsics we may be dealing with transfers
2939     // within a single alloca before SROA ran, or with transfers that have
2940     // a variable length. We may also be dealing with memmove instead of
2941     // memcpy, and so simply updating the pointers is the necessary for us to
2942     // update both source and dest of a single call.
2943     if (!IsSplittable) {
2944       Value *AdjustedPtr = getNewAllocaSlicePtr(IRB, OldPtr->getType());
2945       if (IsDest)
2946         II.setDest(AdjustedPtr);
2947       else
2948         II.setSource(AdjustedPtr);
2949
2950       if (II.getAlignment() > SliceAlign) {
2951         Type *CstTy = II.getAlignmentCst()->getType();
2952         II.setAlignment(
2953             ConstantInt::get(CstTy, MinAlign(II.getAlignment(), SliceAlign)));
2954       }
2955
2956       DEBUG(dbgs() << "          to: " << II << "\n");
2957       deleteIfTriviallyDead(OldPtr);
2958       return false;
2959     }
2960     // For split transfer intrinsics we have an incredibly useful assurance:
2961     // the source and destination do not reside within the same alloca, and at
2962     // least one of them does not escape. This means that we can replace
2963     // memmove with memcpy, and we don't need to worry about all manner of
2964     // downsides to splitting and transforming the operations.
2965
2966     // If this doesn't map cleanly onto the alloca type, and that type isn't
2967     // a single value type, just emit a memcpy.
2968     bool EmitMemCpy =
2969         !VecTy && !IntTy &&
2970         (BeginOffset > NewAllocaBeginOffset || EndOffset < NewAllocaEndOffset ||
2971          SliceSize != DL.getTypeStoreSize(NewAI.getAllocatedType()) ||
2972          !NewAI.getAllocatedType()->isSingleValueType());
2973
2974     // If we're just going to emit a memcpy, the alloca hasn't changed, and the
2975     // size hasn't been shrunk based on analysis of the viable range, this is
2976     // a no-op.
2977     if (EmitMemCpy && &OldAI == &NewAI) {
2978       // Ensure the start lines up.
2979       assert(NewBeginOffset == BeginOffset);
2980
2981       // Rewrite the size as needed.
2982       if (NewEndOffset != EndOffset)
2983         II.setLength(ConstantInt::get(II.getLength()->getType(),
2984                                       NewEndOffset - NewBeginOffset));
2985       return false;
2986     }
2987     // Record this instruction for deletion.
2988     Pass.DeadInsts.insert(&II);
2989
2990     // Strip all inbounds GEPs and pointer casts to try to dig out any root
2991     // alloca that should be re-examined after rewriting this instruction.
2992     Value *OtherPtr = IsDest ? II.getRawSource() : II.getRawDest();
2993     if (AllocaInst *AI =
2994             dyn_cast<AllocaInst>(OtherPtr->stripInBoundsOffsets())) {
2995       assert(AI != &OldAI && AI != &NewAI &&
2996              "Splittable transfers cannot reach the same alloca on both ends.");
2997       Pass.Worklist.insert(AI);
2998     }
2999
3000     Type *OtherPtrTy = OtherPtr->getType();
3001     unsigned OtherAS = OtherPtrTy->getPointerAddressSpace();
3002
3003     // Compute the relative offset for the other pointer within the transfer.
3004     unsigned IntPtrWidth = DL.getPointerSizeInBits(OtherAS);
3005     APInt OtherOffset(IntPtrWidth, NewBeginOffset - BeginOffset);
3006     unsigned OtherAlign = MinAlign(II.getAlignment() ? II.getAlignment() : 1,
3007                                    OtherOffset.zextOrTrunc(64).getZExtValue());
3008
3009     if (EmitMemCpy) {
3010       // Compute the other pointer, folding as much as possible to produce
3011       // a single, simple GEP in most cases.
3012       OtherPtr = getAdjustedPtr(IRB, DL, OtherPtr, OtherOffset, OtherPtrTy,
3013                                 OtherPtr->getName() + ".");
3014
3015       Value *OurPtr = getNewAllocaSlicePtr(IRB, OldPtr->getType());
3016       Type *SizeTy = II.getLength()->getType();
3017       Constant *Size = ConstantInt::get(SizeTy, NewEndOffset - NewBeginOffset);
3018
3019       CallInst *New = IRB.CreateMemCpy(
3020           IsDest ? OurPtr : OtherPtr, IsDest ? OtherPtr : OurPtr, Size,
3021           MinAlign(SliceAlign, OtherAlign), II.isVolatile());
3022       (void)New;
3023       DEBUG(dbgs() << "          to: " << *New << "\n");
3024       return false;
3025     }
3026
3027     bool IsWholeAlloca = NewBeginOffset == NewAllocaBeginOffset &&
3028                          NewEndOffset == NewAllocaEndOffset;
3029     uint64_t Size = NewEndOffset - NewBeginOffset;
3030     unsigned BeginIndex = VecTy ? getIndex(NewBeginOffset) : 0;
3031     unsigned EndIndex = VecTy ? getIndex(NewEndOffset) : 0;
3032     unsigned NumElements = EndIndex - BeginIndex;
3033     IntegerType *SubIntTy =
3034         IntTy ? Type::getIntNTy(IntTy->getContext(), Size * 8) : nullptr;
3035
3036     // Reset the other pointer type to match the register type we're going to
3037     // use, but using the address space of the original other pointer.
3038     if (VecTy && !IsWholeAlloca) {
3039       if (NumElements == 1)
3040         OtherPtrTy = VecTy->getElementType();
3041       else
3042         OtherPtrTy = VectorType::get(VecTy->getElementType(), NumElements);
3043
3044       OtherPtrTy = OtherPtrTy->getPointerTo(OtherAS);
3045     } else if (IntTy && !IsWholeAlloca) {
3046       OtherPtrTy = SubIntTy->getPointerTo(OtherAS);
3047     } else {
3048       OtherPtrTy = NewAllocaTy->getPointerTo(OtherAS);
3049     }
3050
3051     Value *SrcPtr = getAdjustedPtr(IRB, DL, OtherPtr, OtherOffset, OtherPtrTy,
3052                                    OtherPtr->getName() + ".");
3053     unsigned SrcAlign = OtherAlign;
3054     Value *DstPtr = &NewAI;
3055     unsigned DstAlign = SliceAlign;
3056     if (!IsDest) {
3057       std::swap(SrcPtr, DstPtr);
3058       std::swap(SrcAlign, DstAlign);
3059     }
3060
3061     Value *Src;
3062     if (VecTy && !IsWholeAlloca && !IsDest) {
3063       Src = IRB.CreateAlignedLoad(&NewAI, NewAI.getAlignment(), "load");
3064       Src = extractVector(IRB, Src, BeginIndex, EndIndex, "vec");
3065     } else if (IntTy && !IsWholeAlloca && !IsDest) {
3066       Src = IRB.CreateAlignedLoad(&NewAI, NewAI.getAlignment(), "load");
3067       Src = convertValue(DL, IRB, Src, IntTy);
3068       uint64_t Offset = NewBeginOffset - NewAllocaBeginOffset;
3069       Src = extractInteger(DL, IRB, Src, SubIntTy, Offset, "extract");
3070     } else {
3071       Src =
3072           IRB.CreateAlignedLoad(SrcPtr, SrcAlign, II.isVolatile(), "copyload");
3073     }
3074
3075     if (VecTy && !IsWholeAlloca && IsDest) {
3076       Value *Old =
3077           IRB.CreateAlignedLoad(&NewAI, NewAI.getAlignment(), "oldload");
3078       Src = insertVector(IRB, Old, Src, BeginIndex, "vec");
3079     } else if (IntTy && !IsWholeAlloca && IsDest) {
3080       Value *Old =
3081           IRB.CreateAlignedLoad(&NewAI, NewAI.getAlignment(), "oldload");
3082       Old = convertValue(DL, IRB, Old, IntTy);
3083       uint64_t Offset = NewBeginOffset - NewAllocaBeginOffset;
3084       Src = insertInteger(DL, IRB, Old, Src, Offset, "insert");
3085       Src = convertValue(DL, IRB, Src, NewAllocaTy);
3086     }
3087
3088     StoreInst *Store = cast<StoreInst>(
3089         IRB.CreateAlignedStore(Src, DstPtr, DstAlign, II.isVolatile()));
3090     (void)Store;
3091     DEBUG(dbgs() << "          to: " << *Store << "\n");
3092     return !II.isVolatile();
3093   }
3094
3095   bool visitIntrinsicInst(IntrinsicInst &II) {
3096     assert(II.getIntrinsicID() == Intrinsic::lifetime_start ||
3097            II.getIntrinsicID() == Intrinsic::lifetime_end);
3098     DEBUG(dbgs() << "    original: " << II << "\n");
3099     assert(II.getArgOperand(1) == OldPtr);
3100
3101     // Record this instruction for deletion.
3102     Pass.DeadInsts.insert(&II);
3103
3104     ConstantInt *Size =
3105         ConstantInt::get(cast<IntegerType>(II.getArgOperand(0)->getType()),
3106                          NewEndOffset - NewBeginOffset);
3107     Value *Ptr = getNewAllocaSlicePtr(IRB, OldPtr->getType());
3108     Value *New;
3109     if (II.getIntrinsicID() == Intrinsic::lifetime_start)
3110       New = IRB.CreateLifetimeStart(Ptr, Size);
3111     else
3112       New = IRB.CreateLifetimeEnd(Ptr, Size);
3113
3114     (void)New;
3115     DEBUG(dbgs() << "          to: " << *New << "\n");
3116     return true;
3117   }
3118
3119   bool visitPHINode(PHINode &PN) {
3120     DEBUG(dbgs() << "    original: " << PN << "\n");
3121     assert(BeginOffset >= NewAllocaBeginOffset && "PHIs are unsplittable");
3122     assert(EndOffset <= NewAllocaEndOffset && "PHIs are unsplittable");
3123
3124     // We would like to compute a new pointer in only one place, but have it be
3125     // as local as possible to the PHI. To do that, we re-use the location of
3126     // the old pointer, which necessarily must be in the right position to
3127     // dominate the PHI.
3128     IRBuilderTy PtrBuilder(IRB);
3129     if (isa<PHINode>(OldPtr))
3130       PtrBuilder.SetInsertPoint(OldPtr->getParent()->getFirstInsertionPt());
3131     else
3132       PtrBuilder.SetInsertPoint(OldPtr);
3133     PtrBuilder.SetCurrentDebugLocation(OldPtr->getDebugLoc());
3134
3135     Value *NewPtr = getNewAllocaSlicePtr(PtrBuilder, OldPtr->getType());
3136     // Replace the operands which were using the old pointer.
3137     std::replace(PN.op_begin(), PN.op_end(), cast<Value>(OldPtr), NewPtr);
3138
3139     DEBUG(dbgs() << "          to: " << PN << "\n");
3140     deleteIfTriviallyDead(OldPtr);
3141
3142     // PHIs can't be promoted on their own, but often can be speculated. We
3143     // check the speculation outside of the rewriter so that we see the
3144     // fully-rewritten alloca.
3145     PHIUsers.insert(&PN);
3146     return true;
3147   }
3148
3149   bool visitSelectInst(SelectInst &SI) {
3150     DEBUG(dbgs() << "    original: " << SI << "\n");
3151     assert((SI.getTrueValue() == OldPtr || SI.getFalseValue() == OldPtr) &&
3152            "Pointer isn't an operand!");
3153     assert(BeginOffset >= NewAllocaBeginOffset && "Selects are unsplittable");
3154     assert(EndOffset <= NewAllocaEndOffset && "Selects are unsplittable");
3155
3156     Value *NewPtr = getNewAllocaSlicePtr(IRB, OldPtr->getType());
3157     // Replace the operands which were using the old pointer.
3158     if (SI.getOperand(1) == OldPtr)
3159       SI.setOperand(1, NewPtr);
3160     if (SI.getOperand(2) == OldPtr)
3161       SI.setOperand(2, NewPtr);
3162
3163     DEBUG(dbgs() << "          to: " << SI << "\n");
3164     deleteIfTriviallyDead(OldPtr);
3165
3166     // Selects can't be promoted on their own, but often can be speculated. We
3167     // check the speculation outside of the rewriter so that we see the
3168     // fully-rewritten alloca.
3169     SelectUsers.insert(&SI);
3170     return true;
3171   }
3172 };
3173 }
3174
3175 namespace {
3176 /// \brief Visitor to rewrite aggregate loads and stores as scalar.
3177 ///
3178 /// This pass aggressively rewrites all aggregate loads and stores on
3179 /// a particular pointer (or any pointer derived from it which we can identify)
3180 /// with scalar loads and stores.
3181 class AggLoadStoreRewriter : public InstVisitor<AggLoadStoreRewriter, bool> {
3182   // Befriend the base class so it can delegate to private visit methods.
3183   friend class llvm::InstVisitor<AggLoadStoreRewriter, bool>;
3184
3185   const DataLayout &DL;
3186
3187   /// Queue of pointer uses to analyze and potentially rewrite.
3188   SmallVector<Use *, 8> Queue;
3189
3190   /// Set to prevent us from cycling with phi nodes and loops.
3191   SmallPtrSet<User *, 8> Visited;
3192
3193   /// The current pointer use being rewritten. This is used to dig up the used
3194   /// value (as opposed to the user).
3195   Use *U;
3196
3197 public:
3198   AggLoadStoreRewriter(const DataLayout &DL) : DL(DL) {}
3199
3200   /// Rewrite loads and stores through a pointer and all pointers derived from
3201   /// it.
3202   bool rewrite(Instruction &I) {
3203     DEBUG(dbgs() << "  Rewriting FCA loads and stores...\n");
3204     enqueueUsers(I);
3205     bool Changed = false;
3206     while (!Queue.empty()) {
3207       U = Queue.pop_back_val();
3208       Changed |= visit(cast<Instruction>(U->getUser()));
3209     }
3210     return Changed;
3211   }
3212
3213 private:
3214   /// Enqueue all the users of the given instruction for further processing.
3215   /// This uses a set to de-duplicate users.
3216   void enqueueUsers(Instruction &I) {
3217     for (Use &U : I.uses())
3218       if (Visited.insert(U.getUser()).second)
3219         Queue.push_back(&U);
3220   }
3221
3222   // Conservative default is to not rewrite anything.
3223   bool visitInstruction(Instruction &I) { return false; }
3224
3225   /// \brief Generic recursive split emission class.
3226   template <typename Derived> class OpSplitter {
3227   protected:
3228     /// The builder used to form new instructions.
3229     IRBuilderTy IRB;
3230     /// The indices which to be used with insert- or extractvalue to select the
3231     /// appropriate value within the aggregate.
3232     SmallVector<unsigned, 4> Indices;
3233     /// The indices to a GEP instruction which will move Ptr to the correct slot
3234     /// within the aggregate.
3235     SmallVector<Value *, 4> GEPIndices;
3236     /// The base pointer of the original op, used as a base for GEPing the
3237     /// split operations.
3238     Value *Ptr;
3239
3240     /// Initialize the splitter with an insertion point, Ptr and start with a
3241     /// single zero GEP index.
3242     OpSplitter(Instruction *InsertionPoint, Value *Ptr)
3243         : IRB(InsertionPoint), GEPIndices(1, IRB.getInt32(0)), Ptr(Ptr) {}
3244
3245   public:
3246     /// \brief Generic recursive split emission routine.
3247     ///
3248     /// This method recursively splits an aggregate op (load or store) into
3249     /// scalar or vector ops. It splits recursively until it hits a single value
3250     /// and emits that single value operation via the template argument.
3251     ///
3252     /// The logic of this routine relies on GEPs and insertvalue and
3253     /// extractvalue all operating with the same fundamental index list, merely
3254     /// formatted differently (GEPs need actual values).
3255     ///
3256     /// \param Ty  The type being split recursively into smaller ops.
3257     /// \param Agg The aggregate value being built up or stored, depending on
3258     /// whether this is splitting a load or a store respectively.
3259     void emitSplitOps(Type *Ty, Value *&Agg, const Twine &Name) {
3260       if (Ty->isSingleValueType())
3261         return static_cast<Derived *>(this)->emitFunc(Ty, Agg, Name);
3262
3263       if (ArrayType *ATy = dyn_cast<ArrayType>(Ty)) {
3264         unsigned OldSize = Indices.size();
3265         (void)OldSize;
3266         for (unsigned Idx = 0, Size = ATy->getNumElements(); Idx != Size;
3267              ++Idx) {
3268           assert(Indices.size() == OldSize && "Did not return to the old size");
3269           Indices.push_back(Idx);
3270           GEPIndices.push_back(IRB.getInt32(Idx));
3271           emitSplitOps(ATy->getElementType(), Agg, Name + "." + Twine(Idx));
3272           GEPIndices.pop_back();
3273           Indices.pop_back();
3274         }
3275         return;
3276       }
3277
3278       if (StructType *STy = dyn_cast<StructType>(Ty)) {
3279         unsigned OldSize = Indices.size();
3280         (void)OldSize;
3281         for (unsigned Idx = 0, Size = STy->getNumElements(); Idx != Size;
3282              ++Idx) {
3283           assert(Indices.size() == OldSize && "Did not return to the old size");
3284           Indices.push_back(Idx);
3285           GEPIndices.push_back(IRB.getInt32(Idx));
3286           emitSplitOps(STy->getElementType(Idx), Agg, Name + "." + Twine(Idx));
3287           GEPIndices.pop_back();
3288           Indices.pop_back();
3289         }
3290         return;
3291       }
3292
3293       llvm_unreachable("Only arrays and structs are aggregate loadable types");
3294     }
3295   };
3296
3297   struct LoadOpSplitter : public OpSplitter<LoadOpSplitter> {
3298     LoadOpSplitter(Instruction *InsertionPoint, Value *Ptr)
3299         : OpSplitter<LoadOpSplitter>(InsertionPoint, Ptr) {}
3300
3301     /// Emit a leaf load of a single value. This is called at the leaves of the
3302     /// recursive emission to actually load values.
3303     void emitFunc(Type *Ty, Value *&Agg, const Twine &Name) {
3304       assert(Ty->isSingleValueType());
3305       // Load the single value and insert it using the indices.
3306       Value *GEP =
3307           IRB.CreateInBoundsGEP(nullptr, Ptr, GEPIndices, Name + ".gep");
3308       Value *Load = IRB.CreateLoad(GEP, Name + ".load");
3309       Agg = IRB.CreateInsertValue(Agg, Load, Indices, Name + ".insert");
3310       DEBUG(dbgs() << "          to: " << *Load << "\n");
3311     }
3312   };
3313
3314   bool visitLoadInst(LoadInst &LI) {
3315     assert(LI.getPointerOperand() == *U);
3316     if (!LI.isSimple() || LI.getType()->isSingleValueType())
3317       return false;
3318
3319     // We have an aggregate being loaded, split it apart.
3320     DEBUG(dbgs() << "    original: " << LI << "\n");
3321     LoadOpSplitter Splitter(&LI, *U);
3322     Value *V = UndefValue::get(LI.getType());
3323     Splitter.emitSplitOps(LI.getType(), V, LI.getName() + ".fca");
3324     LI.replaceAllUsesWith(V);
3325     LI.eraseFromParent();
3326     return true;
3327   }
3328
3329   struct StoreOpSplitter : public OpSplitter<StoreOpSplitter> {
3330     StoreOpSplitter(Instruction *InsertionPoint, Value *Ptr)
3331         : OpSplitter<StoreOpSplitter>(InsertionPoint, Ptr) {}
3332
3333     /// Emit a leaf store of a single value. This is called at the leaves of the
3334     /// recursive emission to actually produce stores.
3335     void emitFunc(Type *Ty, Value *&Agg, const Twine &Name) {
3336       assert(Ty->isSingleValueType());
3337       // Extract the single value and store it using the indices.
3338       Value *Store = IRB.CreateStore(
3339           IRB.CreateExtractValue(Agg, Indices, Name + ".extract"),
3340           IRB.CreateInBoundsGEP(nullptr, Ptr, GEPIndices, Name + ".gep"));
3341       (void)Store;
3342       DEBUG(dbgs() << "          to: " << *Store << "\n");
3343     }
3344   };
3345
3346   bool visitStoreInst(StoreInst &SI) {
3347     if (!SI.isSimple() || SI.getPointerOperand() != *U)
3348       return false;
3349     Value *V = SI.getValueOperand();
3350     if (V->getType()->isSingleValueType())
3351       return false;
3352
3353     // We have an aggregate being stored, split it apart.
3354     DEBUG(dbgs() << "    original: " << SI << "\n");
3355     StoreOpSplitter Splitter(&SI, *U);
3356     Splitter.emitSplitOps(V->getType(), V, V->getName() + ".fca");
3357     SI.eraseFromParent();
3358     return true;
3359   }
3360
3361   bool visitBitCastInst(BitCastInst &BC) {
3362     enqueueUsers(BC);
3363     return false;
3364   }
3365
3366   bool visitGetElementPtrInst(GetElementPtrInst &GEPI) {
3367     enqueueUsers(GEPI);
3368     return false;
3369   }
3370
3371   bool visitPHINode(PHINode &PN) {
3372     enqueueUsers(PN);
3373     return false;
3374   }
3375
3376   bool visitSelectInst(SelectInst &SI) {
3377     enqueueUsers(SI);
3378     return false;
3379   }
3380 };
3381 }
3382
3383 /// \brief Strip aggregate type wrapping.
3384 ///
3385 /// This removes no-op aggregate types wrapping an underlying type. It will
3386 /// strip as many layers of types as it can without changing either the type
3387 /// size or the allocated size.
3388 static Type *stripAggregateTypeWrapping(const DataLayout &DL, Type *Ty) {
3389   if (Ty->isSingleValueType())
3390     return Ty;
3391
3392   uint64_t AllocSize = DL.getTypeAllocSize(Ty);
3393   uint64_t TypeSize = DL.getTypeSizeInBits(Ty);
3394
3395   Type *InnerTy;
3396   if (ArrayType *ArrTy = dyn_cast<ArrayType>(Ty)) {
3397     InnerTy = ArrTy->getElementType();
3398   } else if (StructType *STy = dyn_cast<StructType>(Ty)) {
3399     const StructLayout *SL = DL.getStructLayout(STy);
3400     unsigned Index = SL->getElementContainingOffset(0);
3401     InnerTy = STy->getElementType(Index);
3402   } else {
3403     return Ty;
3404   }
3405
3406   if (AllocSize > DL.getTypeAllocSize(InnerTy) ||
3407       TypeSize > DL.getTypeSizeInBits(InnerTy))
3408     return Ty;
3409
3410   return stripAggregateTypeWrapping(DL, InnerTy);
3411 }
3412
3413 /// \brief Try to find a partition of the aggregate type passed in for a given
3414 /// offset and size.
3415 ///
3416 /// This recurses through the aggregate type and tries to compute a subtype
3417 /// based on the offset and size. When the offset and size span a sub-section
3418 /// of an array, it will even compute a new array type for that sub-section,
3419 /// and the same for structs.
3420 ///
3421 /// Note that this routine is very strict and tries to find a partition of the
3422 /// type which produces the *exact* right offset and size. It is not forgiving
3423 /// when the size or offset cause either end of type-based partition to be off.
3424 /// Also, this is a best-effort routine. It is reasonable to give up and not
3425 /// return a type if necessary.
3426 static Type *getTypePartition(const DataLayout &DL, Type *Ty, uint64_t Offset,
3427                               uint64_t Size) {
3428   if (Offset == 0 && DL.getTypeAllocSize(Ty) == Size)
3429     return stripAggregateTypeWrapping(DL, Ty);
3430   if (Offset > DL.getTypeAllocSize(Ty) ||
3431       (DL.getTypeAllocSize(Ty) - Offset) < Size)
3432     return nullptr;
3433
3434   if (SequentialType *SeqTy = dyn_cast<SequentialType>(Ty)) {
3435     // We can't partition pointers...
3436     if (SeqTy->isPointerTy())
3437       return nullptr;
3438
3439     Type *ElementTy = SeqTy->getElementType();
3440     uint64_t ElementSize = DL.getTypeAllocSize(ElementTy);
3441     uint64_t NumSkippedElements = Offset / ElementSize;
3442     if (ArrayType *ArrTy = dyn_cast<ArrayType>(SeqTy)) {
3443       if (NumSkippedElements >= ArrTy->getNumElements())
3444         return nullptr;
3445     } else if (VectorType *VecTy = dyn_cast<VectorType>(SeqTy)) {
3446       if (NumSkippedElements >= VecTy->getNumElements())
3447         return nullptr;
3448     }
3449     Offset -= NumSkippedElements * ElementSize;
3450
3451     // First check if we need to recurse.
3452     if (Offset > 0 || Size < ElementSize) {
3453       // Bail if the partition ends in a different array element.
3454       if ((Offset + Size) > ElementSize)
3455         return nullptr;
3456       // Recurse through the element type trying to peel off offset bytes.
3457       return getTypePartition(DL, ElementTy, Offset, Size);
3458     }
3459     assert(Offset == 0);
3460
3461     if (Size == ElementSize)
3462       return stripAggregateTypeWrapping(DL, ElementTy);
3463     assert(Size > ElementSize);
3464     uint64_t NumElements = Size / ElementSize;
3465     if (NumElements * ElementSize != Size)
3466       return nullptr;
3467     return ArrayType::get(ElementTy, NumElements);
3468   }
3469
3470   StructType *STy = dyn_cast<StructType>(Ty);
3471   if (!STy)
3472     return nullptr;
3473
3474   const StructLayout *SL = DL.getStructLayout(STy);
3475   if (Offset >= SL->getSizeInBytes())
3476     return nullptr;
3477   uint64_t EndOffset = Offset + Size;
3478   if (EndOffset > SL->getSizeInBytes())
3479     return nullptr;
3480
3481   unsigned Index = SL->getElementContainingOffset(Offset);
3482   Offset -= SL->getElementOffset(Index);
3483
3484   Type *ElementTy = STy->getElementType(Index);
3485   uint64_t ElementSize = DL.getTypeAllocSize(ElementTy);
3486   if (Offset >= ElementSize)
3487     return nullptr; // The offset points into alignment padding.
3488
3489   // See if any partition must be contained by the element.
3490   if (Offset > 0 || Size < ElementSize) {
3491     if ((Offset + Size) > ElementSize)
3492       return nullptr;
3493     return getTypePartition(DL, ElementTy, Offset, Size);
3494   }
3495   assert(Offset == 0);
3496
3497   if (Size == ElementSize)
3498     return stripAggregateTypeWrapping(DL, ElementTy);
3499
3500   StructType::element_iterator EI = STy->element_begin() + Index,
3501                                EE = STy->element_end();
3502   if (EndOffset < SL->getSizeInBytes()) {
3503     unsigned EndIndex = SL->getElementContainingOffset(EndOffset);
3504     if (Index == EndIndex)
3505       return nullptr; // Within a single element and its padding.
3506
3507     // Don't try to form "natural" types if the elements don't line up with the
3508     // expected size.
3509     // FIXME: We could potentially recurse down through the last element in the
3510     // sub-struct to find a natural end point.
3511     if (SL->getElementOffset(EndIndex) != EndOffset)
3512       return nullptr;
3513
3514     assert(Index < EndIndex);
3515     EE = STy->element_begin() + EndIndex;
3516   }
3517
3518   // Try to build up a sub-structure.
3519   StructType *SubTy =
3520       StructType::get(STy->getContext(), makeArrayRef(EI, EE), STy->isPacked());
3521   const StructLayout *SubSL = DL.getStructLayout(SubTy);
3522   if (Size != SubSL->getSizeInBytes())
3523     return nullptr; // The sub-struct doesn't have quite the size needed.
3524
3525   return SubTy;
3526 }
3527
3528 /// \brief Pre-split loads and stores to simplify rewriting.
3529 ///
3530 /// We want to break up the splittable load+store pairs as much as
3531 /// possible. This is important to do as a preprocessing step, as once we
3532 /// start rewriting the accesses to partitions of the alloca we lose the
3533 /// necessary information to correctly split apart paired loads and stores
3534 /// which both point into this alloca. The case to consider is something like
3535 /// the following:
3536 ///
3537 ///   %a = alloca [12 x i8]
3538 ///   %gep1 = getelementptr [12 x i8]* %a, i32 0, i32 0
3539 ///   %gep2 = getelementptr [12 x i8]* %a, i32 0, i32 4
3540 ///   %gep3 = getelementptr [12 x i8]* %a, i32 0, i32 8
3541 ///   %iptr1 = bitcast i8* %gep1 to i64*
3542 ///   %iptr2 = bitcast i8* %gep2 to i64*
3543 ///   %fptr1 = bitcast i8* %gep1 to float*
3544 ///   %fptr2 = bitcast i8* %gep2 to float*
3545 ///   %fptr3 = bitcast i8* %gep3 to float*
3546 ///   store float 0.0, float* %fptr1
3547 ///   store float 1.0, float* %fptr2
3548 ///   %v = load i64* %iptr1
3549 ///   store i64 %v, i64* %iptr2
3550 ///   %f1 = load float* %fptr2
3551 ///   %f2 = load float* %fptr3
3552 ///
3553 /// Here we want to form 3 partitions of the alloca, each 4 bytes large, and
3554 /// promote everything so we recover the 2 SSA values that should have been
3555 /// there all along.
3556 ///
3557 /// \returns true if any changes are made.
3558 bool SROA::presplitLoadsAndStores(AllocaInst &AI, AllocaSlices &AS) {
3559   DEBUG(dbgs() << "Pre-splitting loads and stores\n");
3560
3561   // Track the loads and stores which are candidates for pre-splitting here, in
3562   // the order they first appear during the partition scan. These give stable
3563   // iteration order and a basis for tracking which loads and stores we
3564   // actually split.
3565   SmallVector<LoadInst *, 4> Loads;
3566   SmallVector<StoreInst *, 4> Stores;
3567
3568   // We need to accumulate the splits required of each load or store where we
3569   // can find them via a direct lookup. This is important to cross-check loads
3570   // and stores against each other. We also track the slice so that we can kill
3571   // all the slices that end up split.
3572   struct SplitOffsets {
3573     Slice *S;
3574     std::vector<uint64_t> Splits;
3575   };
3576   SmallDenseMap<Instruction *, SplitOffsets, 8> SplitOffsetsMap;
3577
3578   // Track loads out of this alloca which cannot, for any reason, be pre-split.
3579   // This is important as we also cannot pre-split stores of those loads!
3580   // FIXME: This is all pretty gross. It means that we can be more aggressive
3581   // in pre-splitting when the load feeding the store happens to come from
3582   // a separate alloca. Put another way, the effectiveness of SROA would be
3583   // decreased by a frontend which just concatenated all of its local allocas
3584   // into one big flat alloca. But defeating such patterns is exactly the job
3585   // SROA is tasked with! Sadly, to not have this discrepancy we would have
3586   // change store pre-splitting to actually force pre-splitting of the load
3587   // that feeds it *and all stores*. That makes pre-splitting much harder, but
3588   // maybe it would make it more principled?
3589   SmallPtrSet<LoadInst *, 8> UnsplittableLoads;
3590
3591   DEBUG(dbgs() << "  Searching for candidate loads and stores\n");
3592   for (auto &P : AS.partitions()) {
3593     for (Slice &S : P) {
3594       Instruction *I = cast<Instruction>(S.getUse()->getUser());
3595       if (!S.isSplittable() ||S.endOffset() <= P.endOffset()) {
3596         // If this was a load we have to track that it can't participate in any
3597         // pre-splitting!
3598         if (auto *LI = dyn_cast<LoadInst>(I))
3599           UnsplittableLoads.insert(LI);
3600         continue;
3601       }
3602       assert(P.endOffset() > S.beginOffset() &&
3603              "Empty or backwards partition!");
3604
3605       // Determine if this is a pre-splittable slice.
3606       if (auto *LI = dyn_cast<LoadInst>(I)) {
3607         assert(!LI->isVolatile() && "Cannot split volatile loads!");
3608
3609         // The load must be used exclusively to store into other pointers for
3610         // us to be able to arbitrarily pre-split it. The stores must also be
3611         // simple to avoid changing semantics.
3612         auto IsLoadSimplyStored = [](LoadInst *LI) {
3613           for (User *LU : LI->users()) {
3614             auto *SI = dyn_cast<StoreInst>(LU);
3615             if (!SI || !SI->isSimple())
3616               return false;
3617           }
3618           return true;
3619         };
3620         if (!IsLoadSimplyStored(LI)) {
3621           UnsplittableLoads.insert(LI);
3622           continue;
3623         }
3624
3625         Loads.push_back(LI);
3626       } else if (auto *SI = dyn_cast<StoreInst>(S.getUse()->getUser())) {
3627         if (!SI ||
3628             S.getUse() != &SI->getOperandUse(SI->getPointerOperandIndex()))
3629           continue;
3630         auto *StoredLoad = dyn_cast<LoadInst>(SI->getValueOperand());
3631         if (!StoredLoad || !StoredLoad->isSimple())
3632           continue;
3633         assert(!SI->isVolatile() && "Cannot split volatile stores!");
3634
3635         Stores.push_back(SI);
3636       } else {
3637         // Other uses cannot be pre-split.
3638         continue;
3639       }
3640
3641       // Record the initial split.
3642       DEBUG(dbgs() << "    Candidate: " << *I << "\n");
3643       auto &Offsets = SplitOffsetsMap[I];
3644       assert(Offsets.Splits.empty() &&
3645              "Should not have splits the first time we see an instruction!");
3646       Offsets.S = &S;
3647       Offsets.Splits.push_back(P.endOffset() - S.beginOffset());
3648     }
3649
3650     // Now scan the already split slices, and add a split for any of them which
3651     // we're going to pre-split.
3652     for (Slice *S : P.splitSliceTails()) {
3653       auto SplitOffsetsMapI =
3654           SplitOffsetsMap.find(cast<Instruction>(S->getUse()->getUser()));
3655       if (SplitOffsetsMapI == SplitOffsetsMap.end())
3656         continue;
3657       auto &Offsets = SplitOffsetsMapI->second;
3658
3659       assert(Offsets.S == S && "Found a mismatched slice!");
3660       assert(!Offsets.Splits.empty() &&
3661              "Cannot have an empty set of splits on the second partition!");
3662       assert(Offsets.Splits.back() ==
3663                  P.beginOffset() - Offsets.S->beginOffset() &&
3664              "Previous split does not end where this one begins!");
3665
3666       // Record each split. The last partition's end isn't needed as the size
3667       // of the slice dictates that.
3668       if (S->endOffset() > P.endOffset())
3669         Offsets.Splits.push_back(P.endOffset() - Offsets.S->beginOffset());
3670     }
3671   }
3672
3673   // We may have split loads where some of their stores are split stores. For
3674   // such loads and stores, we can only pre-split them if their splits exactly
3675   // match relative to their starting offset. We have to verify this prior to
3676   // any rewriting.
3677   Stores.erase(
3678       std::remove_if(Stores.begin(), Stores.end(),
3679                      [&UnsplittableLoads, &SplitOffsetsMap](StoreInst *SI) {
3680                        // Lookup the load we are storing in our map of split
3681                        // offsets.
3682                        auto *LI = cast<LoadInst>(SI->getValueOperand());
3683                        // If it was completely unsplittable, then we're done,
3684                        // and this store can't be pre-split.
3685                        if (UnsplittableLoads.count(LI))
3686                          return true;
3687
3688                        auto LoadOffsetsI = SplitOffsetsMap.find(LI);
3689                        if (LoadOffsetsI == SplitOffsetsMap.end())
3690                          return false; // Unrelated loads are definitely safe.
3691                        auto &LoadOffsets = LoadOffsetsI->second;
3692
3693                        // Now lookup the store's offsets.
3694                        auto &StoreOffsets = SplitOffsetsMap[SI];
3695
3696                        // If the relative offsets of each split in the load and
3697                        // store match exactly, then we can split them and we
3698                        // don't need to remove them here.
3699                        if (LoadOffsets.Splits == StoreOffsets.Splits)
3700                          return false;
3701
3702                        DEBUG(dbgs()
3703                              << "    Mismatched splits for load and store:\n"
3704                              << "      " << *LI << "\n"
3705                              << "      " << *SI << "\n");
3706
3707                        // We've found a store and load that we need to split
3708                        // with mismatched relative splits. Just give up on them
3709                        // and remove both instructions from our list of
3710                        // candidates.
3711                        UnsplittableLoads.insert(LI);
3712                        return true;
3713                      }),
3714       Stores.end());
3715   // Now we have to go *back* through all the stores, because a later store may
3716   // have caused an earlier store's load to become unsplittable and if it is
3717   // unsplittable for the later store, then we can't rely on it being split in
3718   // the earlier store either.
3719   Stores.erase(std::remove_if(Stores.begin(), Stores.end(),
3720                               [&UnsplittableLoads](StoreInst *SI) {
3721                                 auto *LI =
3722                                     cast<LoadInst>(SI->getValueOperand());
3723                                 return UnsplittableLoads.count(LI);
3724                               }),
3725                Stores.end());
3726   // Once we've established all the loads that can't be split for some reason,
3727   // filter any that made it into our list out.
3728   Loads.erase(std::remove_if(Loads.begin(), Loads.end(),
3729                              [&UnsplittableLoads](LoadInst *LI) {
3730                                return UnsplittableLoads.count(LI);
3731                              }),
3732               Loads.end());
3733
3734
3735   // If no loads or stores are left, there is no pre-splitting to be done for
3736   // this alloca.
3737   if (Loads.empty() && Stores.empty())
3738     return false;
3739
3740   // From here on, we can't fail and will be building new accesses, so rig up
3741   // an IR builder.
3742   IRBuilderTy IRB(&AI);
3743
3744   // Collect the new slices which we will merge into the alloca slices.
3745   SmallVector<Slice, 4> NewSlices;
3746
3747   // Track any allocas we end up splitting loads and stores for so we iterate
3748   // on them.
3749   SmallPtrSet<AllocaInst *, 4> ResplitPromotableAllocas;
3750
3751   // At this point, we have collected all of the loads and stores we can
3752   // pre-split, and the specific splits needed for them. We actually do the
3753   // splitting in a specific order in order to handle when one of the loads in
3754   // the value operand to one of the stores.
3755   //
3756   // First, we rewrite all of the split loads, and just accumulate each split
3757   // load in a parallel structure. We also build the slices for them and append
3758   // them to the alloca slices.
3759   SmallDenseMap<LoadInst *, std::vector<LoadInst *>, 1> SplitLoadsMap;
3760   std::vector<LoadInst *> SplitLoads;
3761   const DataLayout &DL = AI.getModule()->getDataLayout();
3762   for (LoadInst *LI : Loads) {
3763     SplitLoads.clear();
3764
3765     IntegerType *Ty = cast<IntegerType>(LI->getType());
3766     uint64_t LoadSize = Ty->getBitWidth() / 8;
3767     assert(LoadSize > 0 && "Cannot have a zero-sized integer load!");
3768
3769     auto &Offsets = SplitOffsetsMap[LI];
3770     assert(LoadSize == Offsets.S->endOffset() - Offsets.S->beginOffset() &&
3771            "Slice size should always match load size exactly!");
3772     uint64_t BaseOffset = Offsets.S->beginOffset();
3773     assert(BaseOffset + LoadSize > BaseOffset &&
3774            "Cannot represent alloca access size using 64-bit integers!");
3775
3776     Instruction *BasePtr = cast<Instruction>(LI->getPointerOperand());
3777     IRB.SetInsertPoint(BasicBlock::iterator(LI));
3778
3779     DEBUG(dbgs() << "  Splitting load: " << *LI << "\n");
3780
3781     uint64_t PartOffset = 0, PartSize = Offsets.Splits.front();
3782     int Idx = 0, Size = Offsets.Splits.size();
3783     for (;;) {
3784       auto *PartTy = Type::getIntNTy(Ty->getContext(), PartSize * 8);
3785       auto *PartPtrTy = PartTy->getPointerTo(LI->getPointerAddressSpace());
3786       LoadInst *PLoad = IRB.CreateAlignedLoad(
3787           getAdjustedPtr(IRB, DL, BasePtr,
3788                          APInt(DL.getPointerSizeInBits(), PartOffset),
3789                          PartPtrTy, BasePtr->getName() + "."),
3790           getAdjustedAlignment(LI, PartOffset, DL), /*IsVolatile*/ false,
3791           LI->getName());
3792
3793       // Append this load onto the list of split loads so we can find it later
3794       // to rewrite the stores.
3795       SplitLoads.push_back(PLoad);
3796
3797       // Now build a new slice for the alloca.
3798       NewSlices.push_back(
3799           Slice(BaseOffset + PartOffset, BaseOffset + PartOffset + PartSize,
3800                 &PLoad->getOperandUse(PLoad->getPointerOperandIndex()),
3801                 /*IsSplittable*/ false));
3802       DEBUG(dbgs() << "    new slice [" << NewSlices.back().beginOffset()
3803                    << ", " << NewSlices.back().endOffset() << "): " << *PLoad
3804                    << "\n");
3805
3806       // See if we've handled all the splits.
3807       if (Idx >= Size)
3808         break;
3809
3810       // Setup the next partition.
3811       PartOffset = Offsets.Splits[Idx];
3812       ++Idx;
3813       PartSize = (Idx < Size ? Offsets.Splits[Idx] : LoadSize) - PartOffset;
3814     }
3815
3816     // Now that we have the split loads, do the slow walk over all uses of the
3817     // load and rewrite them as split stores, or save the split loads to use
3818     // below if the store is going to be split there anyways.
3819     bool DeferredStores = false;
3820     for (User *LU : LI->users()) {
3821       StoreInst *SI = cast<StoreInst>(LU);
3822       if (!Stores.empty() && SplitOffsetsMap.count(SI)) {
3823         DeferredStores = true;
3824         DEBUG(dbgs() << "    Deferred splitting of store: " << *SI << "\n");
3825         continue;
3826       }
3827
3828       Value *StoreBasePtr = SI->getPointerOperand();
3829       IRB.SetInsertPoint(BasicBlock::iterator(SI));
3830
3831       DEBUG(dbgs() << "    Splitting store of load: " << *SI << "\n");
3832
3833       for (int Idx = 0, Size = SplitLoads.size(); Idx < Size; ++Idx) {
3834         LoadInst *PLoad = SplitLoads[Idx];
3835         uint64_t PartOffset = Idx == 0 ? 0 : Offsets.Splits[Idx - 1];
3836         auto *PartPtrTy =
3837             PLoad->getType()->getPointerTo(SI->getPointerAddressSpace());
3838
3839         StoreInst *PStore = IRB.CreateAlignedStore(
3840             PLoad, getAdjustedPtr(IRB, DL, StoreBasePtr,
3841                                   APInt(DL.getPointerSizeInBits(), PartOffset),
3842                                   PartPtrTy, StoreBasePtr->getName() + "."),
3843             getAdjustedAlignment(SI, PartOffset, DL), /*IsVolatile*/ false);
3844         (void)PStore;
3845         DEBUG(dbgs() << "      +" << PartOffset << ":" << *PStore << "\n");
3846       }
3847
3848       // We want to immediately iterate on any allocas impacted by splitting
3849       // this store, and we have to track any promotable alloca (indicated by
3850       // a direct store) as needing to be resplit because it is no longer
3851       // promotable.
3852       if (AllocaInst *OtherAI = dyn_cast<AllocaInst>(StoreBasePtr)) {
3853         ResplitPromotableAllocas.insert(OtherAI);
3854         Worklist.insert(OtherAI);
3855       } else if (AllocaInst *OtherAI = dyn_cast<AllocaInst>(
3856                      StoreBasePtr->stripInBoundsOffsets())) {
3857         Worklist.insert(OtherAI);
3858       }
3859
3860       // Mark the original store as dead.
3861       DeadInsts.insert(SI);
3862     }
3863
3864     // Save the split loads if there are deferred stores among the users.
3865     if (DeferredStores)
3866       SplitLoadsMap.insert(std::make_pair(LI, std::move(SplitLoads)));
3867
3868     // Mark the original load as dead and kill the original slice.
3869     DeadInsts.insert(LI);
3870     Offsets.S->kill();
3871   }
3872
3873   // Second, we rewrite all of the split stores. At this point, we know that
3874   // all loads from this alloca have been split already. For stores of such
3875   // loads, we can simply look up the pre-existing split loads. For stores of
3876   // other loads, we split those loads first and then write split stores of
3877   // them.
3878   for (StoreInst *SI : Stores) {
3879     auto *LI = cast<LoadInst>(SI->getValueOperand());
3880     IntegerType *Ty = cast<IntegerType>(LI->getType());
3881     uint64_t StoreSize = Ty->getBitWidth() / 8;
3882     assert(StoreSize > 0 && "Cannot have a zero-sized integer store!");
3883
3884     auto &Offsets = SplitOffsetsMap[SI];
3885     assert(StoreSize == Offsets.S->endOffset() - Offsets.S->beginOffset() &&
3886            "Slice size should always match load size exactly!");
3887     uint64_t BaseOffset = Offsets.S->beginOffset();
3888     assert(BaseOffset + StoreSize > BaseOffset &&
3889            "Cannot represent alloca access size using 64-bit integers!");
3890
3891     Value *LoadBasePtr = LI->getPointerOperand();
3892     Instruction *StoreBasePtr = cast<Instruction>(SI->getPointerOperand());
3893
3894     DEBUG(dbgs() << "  Splitting store: " << *SI << "\n");
3895
3896     // Check whether we have an already split load.
3897     auto SplitLoadsMapI = SplitLoadsMap.find(LI);
3898     std::vector<LoadInst *> *SplitLoads = nullptr;
3899     if (SplitLoadsMapI != SplitLoadsMap.end()) {
3900       SplitLoads = &SplitLoadsMapI->second;
3901       assert(SplitLoads->size() == Offsets.Splits.size() + 1 &&
3902              "Too few split loads for the number of splits in the store!");
3903     } else {
3904       DEBUG(dbgs() << "          of load: " << *LI << "\n");
3905     }
3906
3907     uint64_t PartOffset = 0, PartSize = Offsets.Splits.front();
3908     int Idx = 0, Size = Offsets.Splits.size();
3909     for (;;) {
3910       auto *PartTy = Type::getIntNTy(Ty->getContext(), PartSize * 8);
3911       auto *PartPtrTy = PartTy->getPointerTo(SI->getPointerAddressSpace());
3912
3913       // Either lookup a split load or create one.
3914       LoadInst *PLoad;
3915       if (SplitLoads) {
3916         PLoad = (*SplitLoads)[Idx];
3917       } else {
3918         IRB.SetInsertPoint(BasicBlock::iterator(LI));
3919         PLoad = IRB.CreateAlignedLoad(
3920             getAdjustedPtr(IRB, DL, LoadBasePtr,
3921                            APInt(DL.getPointerSizeInBits(), PartOffset),
3922                            PartPtrTy, LoadBasePtr->getName() + "."),
3923             getAdjustedAlignment(LI, PartOffset, DL), /*IsVolatile*/ false,
3924             LI->getName());
3925       }
3926
3927       // And store this partition.
3928       IRB.SetInsertPoint(BasicBlock::iterator(SI));
3929       StoreInst *PStore = IRB.CreateAlignedStore(
3930           PLoad, getAdjustedPtr(IRB, DL, StoreBasePtr,
3931                                 APInt(DL.getPointerSizeInBits(), PartOffset),
3932                                 PartPtrTy, StoreBasePtr->getName() + "."),
3933           getAdjustedAlignment(SI, PartOffset, DL), /*IsVolatile*/ false);
3934
3935       // Now build a new slice for the alloca.
3936       NewSlices.push_back(
3937           Slice(BaseOffset + PartOffset, BaseOffset + PartOffset + PartSize,
3938                 &PStore->getOperandUse(PStore->getPointerOperandIndex()),
3939                 /*IsSplittable*/ false));
3940       DEBUG(dbgs() << "    new slice [" << NewSlices.back().beginOffset()
3941                    << ", " << NewSlices.back().endOffset() << "): " << *PStore
3942                    << "\n");
3943       if (!SplitLoads) {
3944         DEBUG(dbgs() << "      of split load: " << *PLoad << "\n");
3945       }
3946
3947       // See if we've finished all the splits.
3948       if (Idx >= Size)
3949         break;