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