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