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