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