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