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