79 /// Hidden option to enable randomly shuffling the slices to help uncover
81 static cl::opt<bool> SROARandomShuffleSlices("sroa-random-shuffle-slices",
189 /// \brief Representation of the alloca slices.
191 /// This class represents the slices of an alloca which are formed by its
193 /// for the slices used and we reflect that in this structure. The uses are
194 /// stored, sorted by increasing beginning offset and with unsplittable slices
195 /// starting at a particular offset before splittable slices.
198   /// \brief Construct the slices of a particular alloca.
203   /// If this is true, the slices are never fully built and should be
207   /// \brief Support for iterating over the slices.
211   iterator begin() { return Slices.begin(); }  in begin()
212   iterator end() { return Slices.end(); }  in end()
216   const_iterator begin() const { return Slices.begin(); }  in begin()
217   const_iterator end() const { return Slices.end(); }  in end()
220   /// \brief Erase a range of slices.
221   void erase(iterator Start, iterator Stop) { Slices.erase(Start, Stop); }  in erase()
223   /// \brief Insert new slices for this alloca.
225   /// This moves the slices into the alloca's slices collection, and re-sorts
226   /// everything so that the usual ordering properties of the alloca's slices
229     int OldSize = Slices.size();  in insert()
230     Slices.append(NewSlices.begin(), NewSlices.end());  in insert()
231     auto SliceI = Slices.begin() + OldSize;  in insert()
232     std::sort(SliceI, Slices.end());  in insert()
233     std::inplace_merge(Slices.begin(), SliceI, Slices.end());  in insert()
274   /// of slices.
277   /// store a pointer to that here and abort trying to form slices of the
278   /// alloca. This will be null if the alloca slices are analyzed successfully.
281   /// \brief The slices of the alloca.
283   /// We store a vector of the slices formed by uses of the alloca here. This
285   /// slices before the splittable ones. See the Slice inner class for more
287   SmallVector<Slice, 8> Slices;  member in llvm::sroa::AllocaSlices
308 /// \brief A partition of the slices.
310 /// An ephemeral representation for a range of slices which can be viewed as
312 /// memory which cannot be split, and provides access to all of the slices
315 /// Objects of this type are produced by traversing the alloca's slices, but
341   /// All of the contained slices start at or after this offset.
346   /// All of the contained slices end at or before this offset.
357   /// \brief Test whether this partition contains no slices, and merely spans
358   /// a region occupied by split slices.
361   /// \name Iterate slices that start within the partition.
376   /// These tails are of slices which start before this partition but are
382 /// \brief An iterator over partitions of the alloca's slices.
385 /// slices. It is a forward iterator as we don't support backtracking for
387 /// current set of split slices.
400   /// \brief We need to keep the end of the slices to know when to stop.
419   /// Requires that the iterator not be at the end of the slices.
422            "Cannot advance past the end of the slices!");  in advance()
455       assert(P.SplitTails.empty() && "Failed to clear the split slices!");  in advance()
462       // Accumulate all the splittable slices which started in the old  in advance()
474       // If P.SI is now at the end, we at most have a tail of split slices.  in advance()
481       // If the we have split slices and the next slice is after a gap and is  in advance()
483       // slices up until the next slice begins.  in advance()
492     // OK, we need to consume new slices. Set the end offset based on the  in advance()
495     // pre-existing split slices that are continuing, in which case we begin  in advance()
508       // Form a partition including all of the overlapping slices with this  in advance()
526     // Collect all of the overlapping splittable slices.  in advance()
535     // a partition spanning only splittable slices.  in advance()
548     // the emptiness of the split slices. The latter is only relevant when  in operator ==()
550     // slices list, but the prior may have the same P.SI and a tail of split  in operator ==()
551     // slices.  in operator ==()
554              "Same set of slices formed two different sized partitions!");  in operator ==()
571 /// \brief A forward range over the partitions of the alloca's slices.
574 /// slices. It computes these partitions on the fly based on the overlapping
575 /// offsets of the slices and the ability to split them. It will visit "empty"
577 /// slices.
604 /// \brief Builder for the alloca slices.
606 /// This class builds a set of alloca slices by recursively visiting the uses
664     AS.Slices.push_back(Slice(BeginOffset, EndOffset, U, IsSplittable));  in insertUse()
812         AS.Slices[MTPI->second].kill();  in visitMemTransferInst()
834         MemTransferSliceMap.insert(std::make_pair(&II, AS.Slices.size()));  in visitMemTransferInst()
837       Slice &PrevP = AS.Slices[PrevIdx];  in visitMemTransferInst()
855     assert(AS.Slices[PrevIdx].getUse()->getUser() == &II &&  in visitMemTransferInst()
999   Slices.erase(std::remove_if(Slices.begin(), Slices.end(),  in AllocaSlices()
1003                Slices.end());  in AllocaSlices()
1008     std::shuffle(Slices.begin(), Slices.end(), MT);  in AllocaSlices()
1014   std::sort(Slices.begin(), Slices.end());  in AllocaSlices()
1040     OS << "Can't analyze slices for alloca: " << AI << "\n"  in print()
1046   OS << "Slices of alloca: " << AI << "\n";  in print()
1059 /// sequence of slices.
1068   // always get consistent results regardless of the order of slices.  in findCommonType()
1098     // To avoid depending on the order of slices, Ty and TyIsCommon must not  in findCommonType()
1775 /// \brief Test whether the given alloca partitioning and range of slices can be
1994   // FIXME: We shouldn't consider split slices that happen to start in the  in isIntegerWideningViable()
2274     // interchangeably for unsplit slices.  in getNewAllocaSlicePtr()
3348   // all the slices that end up split.  in presplitLoadsAndStores()
3431     // Now scan the already split slices, and add a split for any of them which  in presplitLoadsAndStores()
3525   // Collect the new slices which we will merge into the alloca slices.  in presplitLoadsAndStores()
3538   // load in a parallel structure. We also build the slices for them and append  in presplitLoadsAndStores()
3539   // them to the alloca slices.  in presplitLoadsAndStores()
3772   // Remove the killed slices that have ben pre-split.  in presplitLoadsAndStores()
3777   // Insert our new slices. This will sort and merge them into the sorted  in presplitLoadsAndStores()
3781   DEBUG(dbgs() << "  Pre-split slices:\n");  in presplitLoadsAndStores()
3897   // Now that we've processed all the slices in the new partition, check if any  in rewritePartition()
3951 /// \brief Walks the slices of an alloca and form partitions based on them,
4077 /// the slices of the alloca, and then hands it off to be split and
4102   // Build the slices using a recursive instruction-visiting builder.  in runOnAlloca()
4126   // No slices to split. Leave the dead alloca for a later pass to clean up.  in runOnAlloca()