1//===- ScalarReplAggregates.cpp - Scalar Replacement of Aggregates --------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This transformation implements the well known scalar replacement of 11// aggregates transformation. This xform breaks up alloca instructions of 12// aggregate type (structure or array) into individual alloca instructions for 13// each member (if possible). Then, if possible, it transforms the individual 14// alloca instructions into nice clean scalar SSA form. 15// 16// This combines a simple SRoA algorithm with the Mem2Reg algorithm because they 17// often interact, especially for C++ programs. As such, iterating between 18// SRoA, then Mem2Reg until we run out of things to promote works well. 19// 20//===----------------------------------------------------------------------===// 21 22#include "llvm/Transforms/Scalar.h" 23#include "llvm/ADT/SetVector.h" 24#include "llvm/ADT/SmallVector.h" 25#include "llvm/ADT/Statistic.h" 26#include "llvm/Analysis/AssumptionCache.h" 27#include "llvm/Analysis/Loads.h" 28#include "llvm/Analysis/ValueTracking.h" 29#include "llvm/IR/CallSite.h" 30#include "llvm/IR/Constants.h" 31#include "llvm/IR/DIBuilder.h" 32#include "llvm/IR/DataLayout.h" 33#include "llvm/IR/DebugInfo.h" 34#include "llvm/IR/DerivedTypes.h" 35#include "llvm/IR/Dominators.h" 36#include "llvm/IR/Function.h" 37#include "llvm/IR/GetElementPtrTypeIterator.h" 38#include "llvm/IR/GlobalVariable.h" 39#include "llvm/IR/IRBuilder.h" 40#include "llvm/IR/Instructions.h" 41#include "llvm/IR/IntrinsicInst.h" 42#include "llvm/IR/LLVMContext.h" 43#include "llvm/IR/Module.h" 44#include "llvm/IR/Operator.h" 45#include "llvm/Pass.h" 46#include "llvm/Support/Debug.h" 47#include "llvm/Support/ErrorHandling.h" 48#include "llvm/Support/MathExtras.h" 49#include "llvm/Support/raw_ostream.h" 50#include "llvm/Transforms/Utils/Local.h" 51#include "llvm/Transforms/Utils/PromoteMemToReg.h" 52#include "llvm/Transforms/Utils/SSAUpdater.h" 53using namespace llvm; 54 55#define DEBUG_TYPE "scalarrepl" 56 57STATISTIC(NumReplaced, "Number of allocas broken up"); 58STATISTIC(NumPromoted, "Number of allocas promoted"); 59STATISTIC(NumAdjusted, "Number of scalar allocas adjusted to allow promotion"); 60STATISTIC(NumConverted, "Number of aggregates converted to scalar"); 61 62namespace { 63#define SROA SROA_ 64 struct SROA : public FunctionPass { 65 SROA(int T, bool hasDT, char &ID, int ST, int AT, int SLT) 66 : FunctionPass(ID), HasDomTree(hasDT) { 67 if (T == -1) 68 SRThreshold = 128; 69 else 70 SRThreshold = T; 71 if (ST == -1) 72 StructMemberThreshold = 32; 73 else 74 StructMemberThreshold = ST; 75 if (AT == -1) 76 ArrayElementThreshold = 8; 77 else 78 ArrayElementThreshold = AT; 79 if (SLT == -1) 80 // Do not limit the scalar integer load size if no threshold is given. 81 ScalarLoadThreshold = -1; 82 else 83 ScalarLoadThreshold = SLT; 84 } 85 86 bool runOnFunction(Function &F) override; 87 88 bool performScalarRepl(Function &F); 89 bool performPromotion(Function &F); 90 91 private: 92 bool HasDomTree; 93 94 /// DeadInsts - Keep track of instructions we have made dead, so that 95 /// we can remove them after we are done working. 96 SmallVector<Value*, 32> DeadInsts; 97 98 /// AllocaInfo - When analyzing uses of an alloca instruction, this captures 99 /// information about the uses. All these fields are initialized to false 100 /// and set to true when something is learned. 101 struct AllocaInfo { 102 /// The alloca to promote. 103 AllocaInst *AI; 104 105 /// CheckedPHIs - This is a set of verified PHI nodes, to prevent infinite 106 /// looping and avoid redundant work. 107 SmallPtrSet<PHINode*, 8> CheckedPHIs; 108 109 /// isUnsafe - This is set to true if the alloca cannot be SROA'd. 110 bool isUnsafe : 1; 111 112 /// isMemCpySrc - This is true if this aggregate is memcpy'd from. 113 bool isMemCpySrc : 1; 114 115 /// isMemCpyDst - This is true if this aggregate is memcpy'd into. 116 bool isMemCpyDst : 1; 117 118 /// hasSubelementAccess - This is true if a subelement of the alloca is 119 /// ever accessed, or false if the alloca is only accessed with mem 120 /// intrinsics or load/store that only access the entire alloca at once. 121 bool hasSubelementAccess : 1; 122 123 /// hasALoadOrStore - This is true if there are any loads or stores to it. 124 /// The alloca may just be accessed with memcpy, for example, which would 125 /// not set this. 126 bool hasALoadOrStore : 1; 127 128 explicit AllocaInfo(AllocaInst *ai) 129 : AI(ai), isUnsafe(false), isMemCpySrc(false), isMemCpyDst(false), 130 hasSubelementAccess(false), hasALoadOrStore(false) {} 131 }; 132 133 /// SRThreshold - The maximum alloca size to considered for SROA. 134 unsigned SRThreshold; 135 136 /// StructMemberThreshold - The maximum number of members a struct can 137 /// contain to be considered for SROA. 138 unsigned StructMemberThreshold; 139 140 /// ArrayElementThreshold - The maximum number of elements an array can 141 /// have to be considered for SROA. 142 unsigned ArrayElementThreshold; 143 144 /// ScalarLoadThreshold - The maximum size in bits of scalars to load when 145 /// converting to scalar 146 unsigned ScalarLoadThreshold; 147 148 void MarkUnsafe(AllocaInfo &I, Instruction *User) { 149 I.isUnsafe = true; 150 DEBUG(dbgs() << " Transformation preventing inst: " << *User << '\n'); 151 } 152 153 bool isSafeAllocaToScalarRepl(AllocaInst *AI); 154 155 void isSafeForScalarRepl(Instruction *I, uint64_t Offset, AllocaInfo &Info); 156 void isSafePHISelectUseForScalarRepl(Instruction *User, uint64_t Offset, 157 AllocaInfo &Info); 158 void isSafeGEP(GetElementPtrInst *GEPI, uint64_t &Offset, AllocaInfo &Info); 159 void isSafeMemAccess(uint64_t Offset, uint64_t MemSize, 160 Type *MemOpType, bool isStore, AllocaInfo &Info, 161 Instruction *TheAccess, bool AllowWholeAccess); 162 bool TypeHasComponent(Type *T, uint64_t Offset, uint64_t Size, 163 const DataLayout &DL); 164 uint64_t FindElementAndOffset(Type *&T, uint64_t &Offset, Type *&IdxTy, 165 const DataLayout &DL); 166 167 void DoScalarReplacement(AllocaInst *AI, 168 std::vector<AllocaInst*> &WorkList); 169 void DeleteDeadInstructions(); 170 171 void RewriteForScalarRepl(Instruction *I, AllocaInst *AI, uint64_t Offset, 172 SmallVectorImpl<AllocaInst *> &NewElts); 173 void RewriteBitCast(BitCastInst *BC, AllocaInst *AI, uint64_t Offset, 174 SmallVectorImpl<AllocaInst *> &NewElts); 175 void RewriteGEP(GetElementPtrInst *GEPI, AllocaInst *AI, uint64_t Offset, 176 SmallVectorImpl<AllocaInst *> &NewElts); 177 void RewriteLifetimeIntrinsic(IntrinsicInst *II, AllocaInst *AI, 178 uint64_t Offset, 179 SmallVectorImpl<AllocaInst *> &NewElts); 180 void RewriteMemIntrinUserOfAlloca(MemIntrinsic *MI, Instruction *Inst, 181 AllocaInst *AI, 182 SmallVectorImpl<AllocaInst *> &NewElts); 183 void RewriteStoreUserOfWholeAlloca(StoreInst *SI, AllocaInst *AI, 184 SmallVectorImpl<AllocaInst *> &NewElts); 185 void RewriteLoadUserOfWholeAlloca(LoadInst *LI, AllocaInst *AI, 186 SmallVectorImpl<AllocaInst *> &NewElts); 187 bool ShouldAttemptScalarRepl(AllocaInst *AI); 188 }; 189 190 // SROA_DT - SROA that uses DominatorTree. 191 struct SROA_DT : public SROA { 192 static char ID; 193 public: 194 SROA_DT(int T = -1, int ST = -1, int AT = -1, int SLT = -1) : 195 SROA(T, true, ID, ST, AT, SLT) { 196 initializeSROA_DTPass(*PassRegistry::getPassRegistry()); 197 } 198 199 // getAnalysisUsage - This pass does not require any passes, but we know it 200 // will not alter the CFG, so say so. 201 void getAnalysisUsage(AnalysisUsage &AU) const override { 202 AU.addRequired<AssumptionCacheTracker>(); 203 AU.addRequired<DominatorTreeWrapperPass>(); 204 AU.setPreservesCFG(); 205 } 206 }; 207 208 // SROA_SSAUp - SROA that uses SSAUpdater. 209 struct SROA_SSAUp : public SROA { 210 static char ID; 211 public: 212 SROA_SSAUp(int T = -1, int ST = -1, int AT = -1, int SLT = -1) : 213 SROA(T, false, ID, ST, AT, SLT) { 214 initializeSROA_SSAUpPass(*PassRegistry::getPassRegistry()); 215 } 216 217 // getAnalysisUsage - This pass does not require any passes, but we know it 218 // will not alter the CFG, so say so. 219 void getAnalysisUsage(AnalysisUsage &AU) const override { 220 AU.addRequired<AssumptionCacheTracker>(); 221 AU.setPreservesCFG(); 222 } 223 }; 224 225} 226 227char SROA_DT::ID = 0; 228char SROA_SSAUp::ID = 0; 229 230INITIALIZE_PASS_BEGIN(SROA_DT, "scalarrepl", 231 "Scalar Replacement of Aggregates (DT)", false, false) 232INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker) 233INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) 234INITIALIZE_PASS_END(SROA_DT, "scalarrepl", 235 "Scalar Replacement of Aggregates (DT)", false, false) 236 237INITIALIZE_PASS_BEGIN(SROA_SSAUp, "scalarrepl-ssa", 238 "Scalar Replacement of Aggregates (SSAUp)", false, false) 239INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker) 240INITIALIZE_PASS_END(SROA_SSAUp, "scalarrepl-ssa", 241 "Scalar Replacement of Aggregates (SSAUp)", false, false) 242 243// Public interface to the ScalarReplAggregates pass 244FunctionPass *llvm::createScalarReplAggregatesPass(int Threshold, 245 bool UseDomTree, 246 int StructMemberThreshold, 247 int ArrayElementThreshold, 248 int ScalarLoadThreshold) { 249 if (UseDomTree) 250 return new SROA_DT(Threshold, StructMemberThreshold, ArrayElementThreshold, 251 ScalarLoadThreshold); 252 return new SROA_SSAUp(Threshold, StructMemberThreshold, 253 ArrayElementThreshold, ScalarLoadThreshold); 254} 255 256 257//===----------------------------------------------------------------------===// 258// Convert To Scalar Optimization. 259//===----------------------------------------------------------------------===// 260 261namespace { 262/// ConvertToScalarInfo - This class implements the "Convert To Scalar" 263/// optimization, which scans the uses of an alloca and determines if it can 264/// rewrite it in terms of a single new alloca that can be mem2reg'd. 265class ConvertToScalarInfo { 266 /// AllocaSize - The size of the alloca being considered in bytes. 267 unsigned AllocaSize; 268 const DataLayout &DL; 269 unsigned ScalarLoadThreshold; 270 271 /// IsNotTrivial - This is set to true if there is some access to the object 272 /// which means that mem2reg can't promote it. 273 bool IsNotTrivial; 274 275 /// ScalarKind - Tracks the kind of alloca being considered for promotion, 276 /// computed based on the uses of the alloca rather than the LLVM type system. 277 enum { 278 Unknown, 279 280 // Accesses via GEPs that are consistent with element access of a vector 281 // type. This will not be converted into a vector unless there is a later 282 // access using an actual vector type. 283 ImplicitVector, 284 285 // Accesses via vector operations and GEPs that are consistent with the 286 // layout of a vector type. 287 Vector, 288 289 // An integer bag-of-bits with bitwise operations for insertion and 290 // extraction. Any combination of types can be converted into this kind 291 // of scalar. 292 Integer 293 } ScalarKind; 294 295 /// VectorTy - This tracks the type that we should promote the vector to if 296 /// it is possible to turn it into a vector. This starts out null, and if it 297 /// isn't possible to turn into a vector type, it gets set to VoidTy. 298 VectorType *VectorTy; 299 300 /// HadNonMemTransferAccess - True if there is at least one access to the 301 /// alloca that is not a MemTransferInst. We don't want to turn structs into 302 /// large integers unless there is some potential for optimization. 303 bool HadNonMemTransferAccess; 304 305 /// HadDynamicAccess - True if some element of this alloca was dynamic. 306 /// We don't yet have support for turning a dynamic access into a large 307 /// integer. 308 bool HadDynamicAccess; 309 310public: 311 explicit ConvertToScalarInfo(unsigned Size, const DataLayout &DL, 312 unsigned SLT) 313 : AllocaSize(Size), DL(DL), ScalarLoadThreshold(SLT), IsNotTrivial(false), 314 ScalarKind(Unknown), VectorTy(nullptr), HadNonMemTransferAccess(false), 315 HadDynamicAccess(false) { } 316 317 AllocaInst *TryConvert(AllocaInst *AI); 318 319private: 320 bool CanConvertToScalar(Value *V, uint64_t Offset, Value* NonConstantIdx); 321 void MergeInTypeForLoadOrStore(Type *In, uint64_t Offset); 322 bool MergeInVectorType(VectorType *VInTy, uint64_t Offset); 323 void ConvertUsesToScalar(Value *Ptr, AllocaInst *NewAI, uint64_t Offset, 324 Value *NonConstantIdx); 325 326 Value *ConvertScalar_ExtractValue(Value *NV, Type *ToType, 327 uint64_t Offset, Value* NonConstantIdx, 328 IRBuilder<> &Builder); 329 Value *ConvertScalar_InsertValue(Value *StoredVal, Value *ExistingVal, 330 uint64_t Offset, Value* NonConstantIdx, 331 IRBuilder<> &Builder); 332}; 333} // end anonymous namespace. 334 335 336/// TryConvert - Analyze the specified alloca, and if it is safe to do so, 337/// rewrite it to be a new alloca which is mem2reg'able. This returns the new 338/// alloca if possible or null if not. 339AllocaInst *ConvertToScalarInfo::TryConvert(AllocaInst *AI) { 340 // If we can't convert this scalar, or if mem2reg can trivially do it, bail 341 // out. 342 if (!CanConvertToScalar(AI, 0, nullptr) || !IsNotTrivial) 343 return nullptr; 344 345 // If an alloca has only memset / memcpy uses, it may still have an Unknown 346 // ScalarKind. Treat it as an Integer below. 347 if (ScalarKind == Unknown) 348 ScalarKind = Integer; 349 350 if (ScalarKind == Vector && VectorTy->getBitWidth() != AllocaSize * 8) 351 ScalarKind = Integer; 352 353 // If we were able to find a vector type that can handle this with 354 // insert/extract elements, and if there was at least one use that had 355 // a vector type, promote this to a vector. We don't want to promote 356 // random stuff that doesn't use vectors (e.g. <9 x double>) because then 357 // we just get a lot of insert/extracts. If at least one vector is 358 // involved, then we probably really do have a union of vector/array. 359 Type *NewTy; 360 if (ScalarKind == Vector) { 361 assert(VectorTy && "Missing type for vector scalar."); 362 DEBUG(dbgs() << "CONVERT TO VECTOR: " << *AI << "\n TYPE = " 363 << *VectorTy << '\n'); 364 NewTy = VectorTy; // Use the vector type. 365 } else { 366 unsigned BitWidth = AllocaSize * 8; 367 368 // Do not convert to scalar integer if the alloca size exceeds the 369 // scalar load threshold. 370 if (BitWidth > ScalarLoadThreshold) 371 return nullptr; 372 373 if ((ScalarKind == ImplicitVector || ScalarKind == Integer) && 374 !HadNonMemTransferAccess && !DL.fitsInLegalInteger(BitWidth)) 375 return nullptr; 376 // Dynamic accesses on integers aren't yet supported. They need us to shift 377 // by a dynamic amount which could be difficult to work out as we might not 378 // know whether to use a left or right shift. 379 if (ScalarKind == Integer && HadDynamicAccess) 380 return nullptr; 381 382 DEBUG(dbgs() << "CONVERT TO SCALAR INTEGER: " << *AI << "\n"); 383 // Create and insert the integer alloca. 384 NewTy = IntegerType::get(AI->getContext(), BitWidth); 385 } 386 AllocaInst *NewAI = 387 new AllocaInst(NewTy, nullptr, "", &AI->getParent()->front()); 388 ConvertUsesToScalar(AI, NewAI, 0, nullptr); 389 return NewAI; 390} 391 392/// MergeInTypeForLoadOrStore - Add the 'In' type to the accumulated vector type 393/// (VectorTy) so far at the offset specified by Offset (which is specified in 394/// bytes). 395/// 396/// There are two cases we handle here: 397/// 1) A union of vector types of the same size and potentially its elements. 398/// Here we turn element accesses into insert/extract element operations. 399/// This promotes a <4 x float> with a store of float to the third element 400/// into a <4 x float> that uses insert element. 401/// 2) A fully general blob of memory, which we turn into some (potentially 402/// large) integer type with extract and insert operations where the loads 403/// and stores would mutate the memory. We mark this by setting VectorTy 404/// to VoidTy. 405void ConvertToScalarInfo::MergeInTypeForLoadOrStore(Type *In, 406 uint64_t Offset) { 407 // If we already decided to turn this into a blob of integer memory, there is 408 // nothing to be done. 409 if (ScalarKind == Integer) 410 return; 411 412 // If this could be contributing to a vector, analyze it. 413 414 // If the In type is a vector that is the same size as the alloca, see if it 415 // matches the existing VecTy. 416 if (VectorType *VInTy = dyn_cast<VectorType>(In)) { 417 if (MergeInVectorType(VInTy, Offset)) 418 return; 419 } else if (In->isFloatTy() || In->isDoubleTy() || 420 (In->isIntegerTy() && In->getPrimitiveSizeInBits() >= 8 && 421 isPowerOf2_32(In->getPrimitiveSizeInBits()))) { 422 // Full width accesses can be ignored, because they can always be turned 423 // into bitcasts. 424 unsigned EltSize = In->getPrimitiveSizeInBits()/8; 425 if (EltSize == AllocaSize) 426 return; 427 428 // If we're accessing something that could be an element of a vector, see 429 // if the implied vector agrees with what we already have and if Offset is 430 // compatible with it. 431 if (Offset % EltSize == 0 && AllocaSize % EltSize == 0 && 432 (!VectorTy || EltSize == VectorTy->getElementType() 433 ->getPrimitiveSizeInBits()/8)) { 434 if (!VectorTy) { 435 ScalarKind = ImplicitVector; 436 VectorTy = VectorType::get(In, AllocaSize/EltSize); 437 } 438 return; 439 } 440 } 441 442 // Otherwise, we have a case that we can't handle with an optimized vector 443 // form. We can still turn this into a large integer. 444 ScalarKind = Integer; 445} 446 447/// MergeInVectorType - Handles the vector case of MergeInTypeForLoadOrStore, 448/// returning true if the type was successfully merged and false otherwise. 449bool ConvertToScalarInfo::MergeInVectorType(VectorType *VInTy, 450 uint64_t Offset) { 451 if (VInTy->getBitWidth()/8 == AllocaSize && Offset == 0) { 452 // If we're storing/loading a vector of the right size, allow it as a 453 // vector. If this the first vector we see, remember the type so that 454 // we know the element size. If this is a subsequent access, ignore it 455 // even if it is a differing type but the same size. Worst case we can 456 // bitcast the resultant vectors. 457 if (!VectorTy) 458 VectorTy = VInTy; 459 ScalarKind = Vector; 460 return true; 461 } 462 463 return false; 464} 465 466/// CanConvertToScalar - V is a pointer. If we can convert the pointee and all 467/// its accesses to a single vector type, return true and set VecTy to 468/// the new type. If we could convert the alloca into a single promotable 469/// integer, return true but set VecTy to VoidTy. Further, if the use is not a 470/// completely trivial use that mem2reg could promote, set IsNotTrivial. Offset 471/// is the current offset from the base of the alloca being analyzed. 472/// 473/// If we see at least one access to the value that is as a vector type, set the 474/// SawVec flag. 475bool ConvertToScalarInfo::CanConvertToScalar(Value *V, uint64_t Offset, 476 Value* NonConstantIdx) { 477 for (User *U : V->users()) { 478 Instruction *UI = cast<Instruction>(U); 479 480 if (LoadInst *LI = dyn_cast<LoadInst>(UI)) { 481 // Don't break volatile loads. 482 if (!LI->isSimple()) 483 return false; 484 // Don't touch MMX operations. 485 if (LI->getType()->isX86_MMXTy()) 486 return false; 487 HadNonMemTransferAccess = true; 488 MergeInTypeForLoadOrStore(LI->getType(), Offset); 489 continue; 490 } 491 492 if (StoreInst *SI = dyn_cast<StoreInst>(UI)) { 493 // Storing the pointer, not into the value? 494 if (SI->getOperand(0) == V || !SI->isSimple()) return false; 495 // Don't touch MMX operations. 496 if (SI->getOperand(0)->getType()->isX86_MMXTy()) 497 return false; 498 HadNonMemTransferAccess = true; 499 MergeInTypeForLoadOrStore(SI->getOperand(0)->getType(), Offset); 500 continue; 501 } 502 503 if (BitCastInst *BCI = dyn_cast<BitCastInst>(UI)) { 504 if (!onlyUsedByLifetimeMarkers(BCI)) 505 IsNotTrivial = true; // Can't be mem2reg'd. 506 if (!CanConvertToScalar(BCI, Offset, NonConstantIdx)) 507 return false; 508 continue; 509 } 510 511 if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(UI)) { 512 // If this is a GEP with a variable indices, we can't handle it. 513 PointerType* PtrTy = dyn_cast<PointerType>(GEP->getPointerOperandType()); 514 if (!PtrTy) 515 return false; 516 517 // Compute the offset that this GEP adds to the pointer. 518 SmallVector<Value*, 8> Indices(GEP->op_begin()+1, GEP->op_end()); 519 Value *GEPNonConstantIdx = nullptr; 520 if (!GEP->hasAllConstantIndices()) { 521 if (!isa<VectorType>(PtrTy->getElementType())) 522 return false; 523 if (NonConstantIdx) 524 return false; 525 GEPNonConstantIdx = Indices.pop_back_val(); 526 if (!GEPNonConstantIdx->getType()->isIntegerTy(32)) 527 return false; 528 HadDynamicAccess = true; 529 } else 530 GEPNonConstantIdx = NonConstantIdx; 531 uint64_t GEPOffset = DL.getIndexedOffset(PtrTy, 532 Indices); 533 // See if all uses can be converted. 534 if (!CanConvertToScalar(GEP, Offset+GEPOffset, GEPNonConstantIdx)) 535 return false; 536 IsNotTrivial = true; // Can't be mem2reg'd. 537 HadNonMemTransferAccess = true; 538 continue; 539 } 540 541 // If this is a constant sized memset of a constant value (e.g. 0) we can 542 // handle it. 543 if (MemSetInst *MSI = dyn_cast<MemSetInst>(UI)) { 544 // Store to dynamic index. 545 if (NonConstantIdx) 546 return false; 547 // Store of constant value. 548 if (!isa<ConstantInt>(MSI->getValue())) 549 return false; 550 551 // Store of constant size. 552 ConstantInt *Len = dyn_cast<ConstantInt>(MSI->getLength()); 553 if (!Len) 554 return false; 555 556 // If the size differs from the alloca, we can only convert the alloca to 557 // an integer bag-of-bits. 558 // FIXME: This should handle all of the cases that are currently accepted 559 // as vector element insertions. 560 if (Len->getZExtValue() != AllocaSize || Offset != 0) 561 ScalarKind = Integer; 562 563 IsNotTrivial = true; // Can't be mem2reg'd. 564 HadNonMemTransferAccess = true; 565 continue; 566 } 567 568 // If this is a memcpy or memmove into or out of the whole allocation, we 569 // can handle it like a load or store of the scalar type. 570 if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(UI)) { 571 // Store to dynamic index. 572 if (NonConstantIdx) 573 return false; 574 ConstantInt *Len = dyn_cast<ConstantInt>(MTI->getLength()); 575 if (!Len || Len->getZExtValue() != AllocaSize || Offset != 0) 576 return false; 577 578 IsNotTrivial = true; // Can't be mem2reg'd. 579 continue; 580 } 581 582 // If this is a lifetime intrinsic, we can handle it. 583 if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(UI)) { 584 if (II->getIntrinsicID() == Intrinsic::lifetime_start || 585 II->getIntrinsicID() == Intrinsic::lifetime_end) { 586 continue; 587 } 588 } 589 590 // Otherwise, we cannot handle this! 591 return false; 592 } 593 594 return true; 595} 596 597/// ConvertUsesToScalar - Convert all of the users of Ptr to use the new alloca 598/// directly. This happens when we are converting an "integer union" to a 599/// single integer scalar, or when we are converting a "vector union" to a 600/// vector with insert/extractelement instructions. 601/// 602/// Offset is an offset from the original alloca, in bits that need to be 603/// shifted to the right. By the end of this, there should be no uses of Ptr. 604void ConvertToScalarInfo::ConvertUsesToScalar(Value *Ptr, AllocaInst *NewAI, 605 uint64_t Offset, 606 Value* NonConstantIdx) { 607 while (!Ptr->use_empty()) { 608 Instruction *User = cast<Instruction>(Ptr->user_back()); 609 610 if (BitCastInst *CI = dyn_cast<BitCastInst>(User)) { 611 ConvertUsesToScalar(CI, NewAI, Offset, NonConstantIdx); 612 CI->eraseFromParent(); 613 continue; 614 } 615 616 if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(User)) { 617 // Compute the offset that this GEP adds to the pointer. 618 SmallVector<Value*, 8> Indices(GEP->op_begin()+1, GEP->op_end()); 619 Value* GEPNonConstantIdx = nullptr; 620 if (!GEP->hasAllConstantIndices()) { 621 assert(!NonConstantIdx && 622 "Dynamic GEP reading from dynamic GEP unsupported"); 623 GEPNonConstantIdx = Indices.pop_back_val(); 624 } else 625 GEPNonConstantIdx = NonConstantIdx; 626 uint64_t GEPOffset = DL.getIndexedOffset(GEP->getPointerOperandType(), 627 Indices); 628 ConvertUsesToScalar(GEP, NewAI, Offset+GEPOffset*8, GEPNonConstantIdx); 629 GEP->eraseFromParent(); 630 continue; 631 } 632 633 IRBuilder<> Builder(User); 634 635 if (LoadInst *LI = dyn_cast<LoadInst>(User)) { 636 // The load is a bit extract from NewAI shifted right by Offset bits. 637 Value *LoadedVal = Builder.CreateLoad(NewAI); 638 Value *NewLoadVal 639 = ConvertScalar_ExtractValue(LoadedVal, LI->getType(), Offset, 640 NonConstantIdx, Builder); 641 LI->replaceAllUsesWith(NewLoadVal); 642 LI->eraseFromParent(); 643 continue; 644 } 645 646 if (StoreInst *SI = dyn_cast<StoreInst>(User)) { 647 assert(SI->getOperand(0) != Ptr && "Consistency error!"); 648 Instruction *Old = Builder.CreateLoad(NewAI, NewAI->getName()+".in"); 649 Value *New = ConvertScalar_InsertValue(SI->getOperand(0), Old, Offset, 650 NonConstantIdx, Builder); 651 Builder.CreateStore(New, NewAI); 652 SI->eraseFromParent(); 653 654 // If the load we just inserted is now dead, then the inserted store 655 // overwrote the entire thing. 656 if (Old->use_empty()) 657 Old->eraseFromParent(); 658 continue; 659 } 660 661 // If this is a constant sized memset of a constant value (e.g. 0) we can 662 // transform it into a store of the expanded constant value. 663 if (MemSetInst *MSI = dyn_cast<MemSetInst>(User)) { 664 assert(MSI->getRawDest() == Ptr && "Consistency error!"); 665 assert(!NonConstantIdx && "Cannot replace dynamic memset with insert"); 666 int64_t SNumBytes = cast<ConstantInt>(MSI->getLength())->getSExtValue(); 667 if (SNumBytes > 0 && (SNumBytes >> 32) == 0) { 668 unsigned NumBytes = static_cast<unsigned>(SNumBytes); 669 unsigned Val = cast<ConstantInt>(MSI->getValue())->getZExtValue(); 670 671 // Compute the value replicated the right number of times. 672 APInt APVal(NumBytes*8, Val); 673 674 // Splat the value if non-zero. 675 if (Val) 676 for (unsigned i = 1; i != NumBytes; ++i) 677 APVal |= APVal << 8; 678 679 Instruction *Old = Builder.CreateLoad(NewAI, NewAI->getName()+".in"); 680 Value *New = ConvertScalar_InsertValue( 681 ConstantInt::get(User->getContext(), APVal), 682 Old, Offset, nullptr, Builder); 683 Builder.CreateStore(New, NewAI); 684 685 // If the load we just inserted is now dead, then the memset overwrote 686 // the entire thing. 687 if (Old->use_empty()) 688 Old->eraseFromParent(); 689 } 690 MSI->eraseFromParent(); 691 continue; 692 } 693 694 // If this is a memcpy or memmove into or out of the whole allocation, we 695 // can handle it like a load or store of the scalar type. 696 if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(User)) { 697 assert(Offset == 0 && "must be store to start of alloca"); 698 assert(!NonConstantIdx && "Cannot replace dynamic transfer with insert"); 699 700 // If the source and destination are both to the same alloca, then this is 701 // a noop copy-to-self, just delete it. Otherwise, emit a load and store 702 // as appropriate. 703 AllocaInst *OrigAI = cast<AllocaInst>(GetUnderlyingObject(Ptr, DL, 0)); 704 705 if (GetUnderlyingObject(MTI->getSource(), DL, 0) != OrigAI) { 706 // Dest must be OrigAI, change this to be a load from the original 707 // pointer (bitcasted), then a store to our new alloca. 708 assert(MTI->getRawDest() == Ptr && "Neither use is of pointer?"); 709 Value *SrcPtr = MTI->getSource(); 710 PointerType* SPTy = cast<PointerType>(SrcPtr->getType()); 711 PointerType* AIPTy = cast<PointerType>(NewAI->getType()); 712 if (SPTy->getAddressSpace() != AIPTy->getAddressSpace()) { 713 AIPTy = PointerType::get(AIPTy->getElementType(), 714 SPTy->getAddressSpace()); 715 } 716 SrcPtr = Builder.CreateBitCast(SrcPtr, AIPTy); 717 718 LoadInst *SrcVal = Builder.CreateLoad(SrcPtr, "srcval"); 719 SrcVal->setAlignment(MTI->getAlignment()); 720 Builder.CreateStore(SrcVal, NewAI); 721 } else if (GetUnderlyingObject(MTI->getDest(), DL, 0) != OrigAI) { 722 // Src must be OrigAI, change this to be a load from NewAI then a store 723 // through the original dest pointer (bitcasted). 724 assert(MTI->getRawSource() == Ptr && "Neither use is of pointer?"); 725 LoadInst *SrcVal = Builder.CreateLoad(NewAI, "srcval"); 726 727 PointerType* DPTy = cast<PointerType>(MTI->getDest()->getType()); 728 PointerType* AIPTy = cast<PointerType>(NewAI->getType()); 729 if (DPTy->getAddressSpace() != AIPTy->getAddressSpace()) { 730 AIPTy = PointerType::get(AIPTy->getElementType(), 731 DPTy->getAddressSpace()); 732 } 733 Value *DstPtr = Builder.CreateBitCast(MTI->getDest(), AIPTy); 734 735 StoreInst *NewStore = Builder.CreateStore(SrcVal, DstPtr); 736 NewStore->setAlignment(MTI->getAlignment()); 737 } else { 738 // Noop transfer. Src == Dst 739 } 740 741 MTI->eraseFromParent(); 742 continue; 743 } 744 745 if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(User)) { 746 if (II->getIntrinsicID() == Intrinsic::lifetime_start || 747 II->getIntrinsicID() == Intrinsic::lifetime_end) { 748 // There's no need to preserve these, as the resulting alloca will be 749 // converted to a register anyways. 750 II->eraseFromParent(); 751 continue; 752 } 753 } 754 755 llvm_unreachable("Unsupported operation!"); 756 } 757} 758 759/// ConvertScalar_ExtractValue - Extract a value of type ToType from an integer 760/// or vector value FromVal, extracting the bits from the offset specified by 761/// Offset. This returns the value, which is of type ToType. 762/// 763/// This happens when we are converting an "integer union" to a single 764/// integer scalar, or when we are converting a "vector union" to a vector with 765/// insert/extractelement instructions. 766/// 767/// Offset is an offset from the original alloca, in bits that need to be 768/// shifted to the right. 769Value *ConvertToScalarInfo:: 770ConvertScalar_ExtractValue(Value *FromVal, Type *ToType, 771 uint64_t Offset, Value* NonConstantIdx, 772 IRBuilder<> &Builder) { 773 // If the load is of the whole new alloca, no conversion is needed. 774 Type *FromType = FromVal->getType(); 775 if (FromType == ToType && Offset == 0) 776 return FromVal; 777 778 // If the result alloca is a vector type, this is either an element 779 // access or a bitcast to another vector type of the same size. 780 if (VectorType *VTy = dyn_cast<VectorType>(FromType)) { 781 unsigned FromTypeSize = DL.getTypeAllocSize(FromType); 782 unsigned ToTypeSize = DL.getTypeAllocSize(ToType); 783 if (FromTypeSize == ToTypeSize) 784 return Builder.CreateBitCast(FromVal, ToType); 785 786 // Otherwise it must be an element access. 787 unsigned Elt = 0; 788 if (Offset) { 789 unsigned EltSize = DL.getTypeAllocSizeInBits(VTy->getElementType()); 790 Elt = Offset/EltSize; 791 assert(EltSize*Elt == Offset && "Invalid modulus in validity checking"); 792 } 793 // Return the element extracted out of it. 794 Value *Idx; 795 if (NonConstantIdx) { 796 if (Elt) 797 Idx = Builder.CreateAdd(NonConstantIdx, 798 Builder.getInt32(Elt), 799 "dyn.offset"); 800 else 801 Idx = NonConstantIdx; 802 } else 803 Idx = Builder.getInt32(Elt); 804 Value *V = Builder.CreateExtractElement(FromVal, Idx); 805 if (V->getType() != ToType) 806 V = Builder.CreateBitCast(V, ToType); 807 return V; 808 } 809 810 // If ToType is a first class aggregate, extract out each of the pieces and 811 // use insertvalue's to form the FCA. 812 if (StructType *ST = dyn_cast<StructType>(ToType)) { 813 assert(!NonConstantIdx && 814 "Dynamic indexing into struct types not supported"); 815 const StructLayout &Layout = *DL.getStructLayout(ST); 816 Value *Res = UndefValue::get(ST); 817 for (unsigned i = 0, e = ST->getNumElements(); i != e; ++i) { 818 Value *Elt = ConvertScalar_ExtractValue(FromVal, ST->getElementType(i), 819 Offset+Layout.getElementOffsetInBits(i), 820 nullptr, Builder); 821 Res = Builder.CreateInsertValue(Res, Elt, i); 822 } 823 return Res; 824 } 825 826 if (ArrayType *AT = dyn_cast<ArrayType>(ToType)) { 827 assert(!NonConstantIdx && 828 "Dynamic indexing into array types not supported"); 829 uint64_t EltSize = DL.getTypeAllocSizeInBits(AT->getElementType()); 830 Value *Res = UndefValue::get(AT); 831 for (unsigned i = 0, e = AT->getNumElements(); i != e; ++i) { 832 Value *Elt = ConvertScalar_ExtractValue(FromVal, AT->getElementType(), 833 Offset+i*EltSize, nullptr, 834 Builder); 835 Res = Builder.CreateInsertValue(Res, Elt, i); 836 } 837 return Res; 838 } 839 840 // Otherwise, this must be a union that was converted to an integer value. 841 IntegerType *NTy = cast<IntegerType>(FromVal->getType()); 842 843 // If this is a big-endian system and the load is narrower than the 844 // full alloca type, we need to do a shift to get the right bits. 845 int ShAmt = 0; 846 if (DL.isBigEndian()) { 847 // On big-endian machines, the lowest bit is stored at the bit offset 848 // from the pointer given by getTypeStoreSizeInBits. This matters for 849 // integers with a bitwidth that is not a multiple of 8. 850 ShAmt = DL.getTypeStoreSizeInBits(NTy) - 851 DL.getTypeStoreSizeInBits(ToType) - Offset; 852 } else { 853 ShAmt = Offset; 854 } 855 856 // Note: we support negative bitwidths (with shl) which are not defined. 857 // We do this to support (f.e.) loads off the end of a structure where 858 // only some bits are used. 859 if (ShAmt > 0 && (unsigned)ShAmt < NTy->getBitWidth()) 860 FromVal = Builder.CreateLShr(FromVal, 861 ConstantInt::get(FromVal->getType(), ShAmt)); 862 else if (ShAmt < 0 && (unsigned)-ShAmt < NTy->getBitWidth()) 863 FromVal = Builder.CreateShl(FromVal, 864 ConstantInt::get(FromVal->getType(), -ShAmt)); 865 866 // Finally, unconditionally truncate the integer to the right width. 867 unsigned LIBitWidth = DL.getTypeSizeInBits(ToType); 868 if (LIBitWidth < NTy->getBitWidth()) 869 FromVal = 870 Builder.CreateTrunc(FromVal, IntegerType::get(FromVal->getContext(), 871 LIBitWidth)); 872 else if (LIBitWidth > NTy->getBitWidth()) 873 FromVal = 874 Builder.CreateZExt(FromVal, IntegerType::get(FromVal->getContext(), 875 LIBitWidth)); 876 877 // If the result is an integer, this is a trunc or bitcast. 878 if (ToType->isIntegerTy()) { 879 // Should be done. 880 } else if (ToType->isFloatingPointTy() || ToType->isVectorTy()) { 881 // Just do a bitcast, we know the sizes match up. 882 FromVal = Builder.CreateBitCast(FromVal, ToType); 883 } else { 884 // Otherwise must be a pointer. 885 FromVal = Builder.CreateIntToPtr(FromVal, ToType); 886 } 887 assert(FromVal->getType() == ToType && "Didn't convert right?"); 888 return FromVal; 889} 890 891/// ConvertScalar_InsertValue - Insert the value "SV" into the existing integer 892/// or vector value "Old" at the offset specified by Offset. 893/// 894/// This happens when we are converting an "integer union" to a 895/// single integer scalar, or when we are converting a "vector union" to a 896/// vector with insert/extractelement instructions. 897/// 898/// Offset is an offset from the original alloca, in bits that need to be 899/// shifted to the right. 900/// 901/// NonConstantIdx is an index value if there was a GEP with a non-constant 902/// index value. If this is 0 then all GEPs used to find this insert address 903/// are constant. 904Value *ConvertToScalarInfo:: 905ConvertScalar_InsertValue(Value *SV, Value *Old, 906 uint64_t Offset, Value* NonConstantIdx, 907 IRBuilder<> &Builder) { 908 // Convert the stored type to the actual type, shift it left to insert 909 // then 'or' into place. 910 Type *AllocaType = Old->getType(); 911 LLVMContext &Context = Old->getContext(); 912 913 if (VectorType *VTy = dyn_cast<VectorType>(AllocaType)) { 914 uint64_t VecSize = DL.getTypeAllocSizeInBits(VTy); 915 uint64_t ValSize = DL.getTypeAllocSizeInBits(SV->getType()); 916 917 // Changing the whole vector with memset or with an access of a different 918 // vector type? 919 if (ValSize == VecSize) 920 return Builder.CreateBitCast(SV, AllocaType); 921 922 // Must be an element insertion. 923 Type *EltTy = VTy->getElementType(); 924 if (SV->getType() != EltTy) 925 SV = Builder.CreateBitCast(SV, EltTy); 926 uint64_t EltSize = DL.getTypeAllocSizeInBits(EltTy); 927 unsigned Elt = Offset/EltSize; 928 Value *Idx; 929 if (NonConstantIdx) { 930 if (Elt) 931 Idx = Builder.CreateAdd(NonConstantIdx, 932 Builder.getInt32(Elt), 933 "dyn.offset"); 934 else 935 Idx = NonConstantIdx; 936 } else 937 Idx = Builder.getInt32(Elt); 938 return Builder.CreateInsertElement(Old, SV, Idx); 939 } 940 941 // If SV is a first-class aggregate value, insert each value recursively. 942 if (StructType *ST = dyn_cast<StructType>(SV->getType())) { 943 assert(!NonConstantIdx && 944 "Dynamic indexing into struct types not supported"); 945 const StructLayout &Layout = *DL.getStructLayout(ST); 946 for (unsigned i = 0, e = ST->getNumElements(); i != e; ++i) { 947 Value *Elt = Builder.CreateExtractValue(SV, i); 948 Old = ConvertScalar_InsertValue(Elt, Old, 949 Offset+Layout.getElementOffsetInBits(i), 950 nullptr, Builder); 951 } 952 return Old; 953 } 954 955 if (ArrayType *AT = dyn_cast<ArrayType>(SV->getType())) { 956 assert(!NonConstantIdx && 957 "Dynamic indexing into array types not supported"); 958 uint64_t EltSize = DL.getTypeAllocSizeInBits(AT->getElementType()); 959 for (unsigned i = 0, e = AT->getNumElements(); i != e; ++i) { 960 Value *Elt = Builder.CreateExtractValue(SV, i); 961 Old = ConvertScalar_InsertValue(Elt, Old, Offset+i*EltSize, nullptr, 962 Builder); 963 } 964 return Old; 965 } 966 967 // If SV is a float, convert it to the appropriate integer type. 968 // If it is a pointer, do the same. 969 unsigned SrcWidth = DL.getTypeSizeInBits(SV->getType()); 970 unsigned DestWidth = DL.getTypeSizeInBits(AllocaType); 971 unsigned SrcStoreWidth = DL.getTypeStoreSizeInBits(SV->getType()); 972 unsigned DestStoreWidth = DL.getTypeStoreSizeInBits(AllocaType); 973 if (SV->getType()->isFloatingPointTy() || SV->getType()->isVectorTy()) 974 SV = Builder.CreateBitCast(SV, IntegerType::get(SV->getContext(),SrcWidth)); 975 else if (SV->getType()->isPointerTy()) 976 SV = Builder.CreatePtrToInt(SV, DL.getIntPtrType(SV->getType())); 977 978 // Zero extend or truncate the value if needed. 979 if (SV->getType() != AllocaType) { 980 if (SV->getType()->getPrimitiveSizeInBits() < 981 AllocaType->getPrimitiveSizeInBits()) 982 SV = Builder.CreateZExt(SV, AllocaType); 983 else { 984 // Truncation may be needed if storing more than the alloca can hold 985 // (undefined behavior). 986 SV = Builder.CreateTrunc(SV, AllocaType); 987 SrcWidth = DestWidth; 988 SrcStoreWidth = DestStoreWidth; 989 } 990 } 991 992 // If this is a big-endian system and the store is narrower than the 993 // full alloca type, we need to do a shift to get the right bits. 994 int ShAmt = 0; 995 if (DL.isBigEndian()) { 996 // On big-endian machines, the lowest bit is stored at the bit offset 997 // from the pointer given by getTypeStoreSizeInBits. This matters for 998 // integers with a bitwidth that is not a multiple of 8. 999 ShAmt = DestStoreWidth - SrcStoreWidth - Offset; 1000 } else { 1001 ShAmt = Offset; 1002 } 1003 1004 // Note: we support negative bitwidths (with shr) which are not defined. 1005 // We do this to support (f.e.) stores off the end of a structure where 1006 // only some bits in the structure are set. 1007 APInt Mask(APInt::getLowBitsSet(DestWidth, SrcWidth)); 1008 if (ShAmt > 0 && (unsigned)ShAmt < DestWidth) { 1009 SV = Builder.CreateShl(SV, ConstantInt::get(SV->getType(), ShAmt)); 1010 Mask <<= ShAmt; 1011 } else if (ShAmt < 0 && (unsigned)-ShAmt < DestWidth) { 1012 SV = Builder.CreateLShr(SV, ConstantInt::get(SV->getType(), -ShAmt)); 1013 Mask = Mask.lshr(-ShAmt); 1014 } 1015 1016 // Mask out the bits we are about to insert from the old value, and or 1017 // in the new bits. 1018 if (SrcWidth != DestWidth) { 1019 assert(DestWidth > SrcWidth); 1020 Old = Builder.CreateAnd(Old, ConstantInt::get(Context, ~Mask), "mask"); 1021 SV = Builder.CreateOr(Old, SV, "ins"); 1022 } 1023 return SV; 1024} 1025 1026 1027//===----------------------------------------------------------------------===// 1028// SRoA Driver 1029//===----------------------------------------------------------------------===// 1030 1031 1032bool SROA::runOnFunction(Function &F) { 1033 if (skipOptnoneFunction(F)) 1034 return false; 1035 1036 bool Changed = performPromotion(F); 1037 1038 while (1) { 1039 bool LocalChange = performScalarRepl(F); 1040 if (!LocalChange) break; // No need to repromote if no scalarrepl 1041 Changed = true; 1042 LocalChange = performPromotion(F); 1043 if (!LocalChange) break; // No need to re-scalarrepl if no promotion 1044 } 1045 1046 return Changed; 1047} 1048 1049namespace { 1050class AllocaPromoter : public LoadAndStorePromoter { 1051 AllocaInst *AI; 1052 DIBuilder *DIB; 1053 SmallVector<DbgDeclareInst *, 4> DDIs; 1054 SmallVector<DbgValueInst *, 4> DVIs; 1055public: 1056 AllocaPromoter(ArrayRef<Instruction*> Insts, SSAUpdater &S, 1057 DIBuilder *DB) 1058 : LoadAndStorePromoter(Insts, S), AI(nullptr), DIB(DB) {} 1059 1060 void run(AllocaInst *AI, const SmallVectorImpl<Instruction*> &Insts) { 1061 // Remember which alloca we're promoting (for isInstInList). 1062 this->AI = AI; 1063 if (auto *L = LocalAsMetadata::getIfExists(AI)) { 1064 if (auto *DINode = MetadataAsValue::getIfExists(AI->getContext(), L)) { 1065 for (User *U : DINode->users()) 1066 if (DbgDeclareInst *DDI = dyn_cast<DbgDeclareInst>(U)) 1067 DDIs.push_back(DDI); 1068 else if (DbgValueInst *DVI = dyn_cast<DbgValueInst>(U)) 1069 DVIs.push_back(DVI); 1070 } 1071 } 1072 1073 LoadAndStorePromoter::run(Insts); 1074 AI->eraseFromParent(); 1075 for (SmallVectorImpl<DbgDeclareInst *>::iterator I = DDIs.begin(), 1076 E = DDIs.end(); I != E; ++I) { 1077 DbgDeclareInst *DDI = *I; 1078 DDI->eraseFromParent(); 1079 } 1080 for (SmallVectorImpl<DbgValueInst *>::iterator I = DVIs.begin(), 1081 E = DVIs.end(); I != E; ++I) { 1082 DbgValueInst *DVI = *I; 1083 DVI->eraseFromParent(); 1084 } 1085 } 1086 1087 bool isInstInList(Instruction *I, 1088 const SmallVectorImpl<Instruction*> &Insts) const override { 1089 if (LoadInst *LI = dyn_cast<LoadInst>(I)) 1090 return LI->getOperand(0) == AI; 1091 return cast<StoreInst>(I)->getPointerOperand() == AI; 1092 } 1093 1094 void updateDebugInfo(Instruction *Inst) const override { 1095 for (SmallVectorImpl<DbgDeclareInst *>::const_iterator I = DDIs.begin(), 1096 E = DDIs.end(); I != E; ++I) { 1097 DbgDeclareInst *DDI = *I; 1098 if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) 1099 ConvertDebugDeclareToDebugValue(DDI, SI, *DIB); 1100 else if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) 1101 ConvertDebugDeclareToDebugValue(DDI, LI, *DIB); 1102 } 1103 for (SmallVectorImpl<DbgValueInst *>::const_iterator I = DVIs.begin(), 1104 E = DVIs.end(); I != E; ++I) { 1105 DbgValueInst *DVI = *I; 1106 Value *Arg = nullptr; 1107 if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) { 1108 // If an argument is zero extended then use argument directly. The ZExt 1109 // may be zapped by an optimization pass in future. 1110 if (ZExtInst *ZExt = dyn_cast<ZExtInst>(SI->getOperand(0))) 1111 Arg = dyn_cast<Argument>(ZExt->getOperand(0)); 1112 if (SExtInst *SExt = dyn_cast<SExtInst>(SI->getOperand(0))) 1113 Arg = dyn_cast<Argument>(SExt->getOperand(0)); 1114 if (!Arg) 1115 Arg = SI->getOperand(0); 1116 } else if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) { 1117 Arg = LI->getOperand(0); 1118 } else { 1119 continue; 1120 } 1121 DIB->insertDbgValueIntrinsic(Arg, 0, DVI->getVariable(), 1122 DVI->getExpression(), DVI->getDebugLoc(), 1123 Inst); 1124 } 1125 } 1126}; 1127} // end anon namespace 1128 1129/// isSafeSelectToSpeculate - Select instructions that use an alloca and are 1130/// subsequently loaded can be rewritten to load both input pointers and then 1131/// select between the result, allowing the load of the alloca to be promoted. 1132/// From this: 1133/// %P2 = select i1 %cond, i32* %Alloca, i32* %Other 1134/// %V = load i32* %P2 1135/// to: 1136/// %V1 = load i32* %Alloca -> will be mem2reg'd 1137/// %V2 = load i32* %Other 1138/// %V = select i1 %cond, i32 %V1, i32 %V2 1139/// 1140/// We can do this to a select if its only uses are loads and if the operand to 1141/// the select can be loaded unconditionally. 1142static bool isSafeSelectToSpeculate(SelectInst *SI) { 1143 const DataLayout &DL = SI->getModule()->getDataLayout(); 1144 bool TDerefable = isDereferenceablePointer(SI->getTrueValue(), DL); 1145 bool FDerefable = isDereferenceablePointer(SI->getFalseValue(), DL); 1146 1147 for (User *U : SI->users()) { 1148 LoadInst *LI = dyn_cast<LoadInst>(U); 1149 if (!LI || !LI->isSimple()) return false; 1150 1151 // Both operands to the select need to be dereferencable, either absolutely 1152 // (e.g. allocas) or at this point because we can see other accesses to it. 1153 if (!TDerefable && 1154 !isSafeToLoadUnconditionally(SI->getTrueValue(), LI, 1155 LI->getAlignment())) 1156 return false; 1157 if (!FDerefable && 1158 !isSafeToLoadUnconditionally(SI->getFalseValue(), LI, 1159 LI->getAlignment())) 1160 return false; 1161 } 1162 1163 return true; 1164} 1165 1166/// isSafePHIToSpeculate - PHI instructions that use an alloca and are 1167/// subsequently loaded can be rewritten to load both input pointers in the pred 1168/// blocks and then PHI the results, allowing the load of the alloca to be 1169/// promoted. 1170/// From this: 1171/// %P2 = phi [i32* %Alloca, i32* %Other] 1172/// %V = load i32* %P2 1173/// to: 1174/// %V1 = load i32* %Alloca -> will be mem2reg'd 1175/// ... 1176/// %V2 = load i32* %Other 1177/// ... 1178/// %V = phi [i32 %V1, i32 %V2] 1179/// 1180/// We can do this to a select if its only uses are loads and if the operand to 1181/// the select can be loaded unconditionally. 1182static bool isSafePHIToSpeculate(PHINode *PN) { 1183 // For now, we can only do this promotion if the load is in the same block as 1184 // the PHI, and if there are no stores between the phi and load. 1185 // TODO: Allow recursive phi users. 1186 // TODO: Allow stores. 1187 BasicBlock *BB = PN->getParent(); 1188 unsigned MaxAlign = 0; 1189 for (User *U : PN->users()) { 1190 LoadInst *LI = dyn_cast<LoadInst>(U); 1191 if (!LI || !LI->isSimple()) return false; 1192 1193 // For now we only allow loads in the same block as the PHI. This is a 1194 // common case that happens when instcombine merges two loads through a PHI. 1195 if (LI->getParent() != BB) return false; 1196 1197 // Ensure that there are no instructions between the PHI and the load that 1198 // could store. 1199 for (BasicBlock::iterator BBI(PN); &*BBI != LI; ++BBI) 1200 if (BBI->mayWriteToMemory()) 1201 return false; 1202 1203 MaxAlign = std::max(MaxAlign, LI->getAlignment()); 1204 } 1205 1206 const DataLayout &DL = PN->getModule()->getDataLayout(); 1207 1208 // Okay, we know that we have one or more loads in the same block as the PHI. 1209 // We can transform this if it is safe to push the loads into the predecessor 1210 // blocks. The only thing to watch out for is that we can't put a possibly 1211 // trapping load in the predecessor if it is a critical edge. 1212 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 1213 BasicBlock *Pred = PN->getIncomingBlock(i); 1214 Value *InVal = PN->getIncomingValue(i); 1215 1216 // If the terminator of the predecessor has side-effects (an invoke), 1217 // there is no safe place to put a load in the predecessor. 1218 if (Pred->getTerminator()->mayHaveSideEffects()) 1219 return false; 1220 1221 // If the value is produced by the terminator of the predecessor 1222 // (an invoke), there is no valid place to put a load in the predecessor. 1223 if (Pred->getTerminator() == InVal) 1224 return false; 1225 1226 // If the predecessor has a single successor, then the edge isn't critical. 1227 if (Pred->getTerminator()->getNumSuccessors() == 1) 1228 continue; 1229 1230 // If this pointer is always safe to load, or if we can prove that there is 1231 // already a load in the block, then we can move the load to the pred block. 1232 if (isDereferenceablePointer(InVal, DL) || 1233 isSafeToLoadUnconditionally(InVal, Pred->getTerminator(), MaxAlign)) 1234 continue; 1235 1236 return false; 1237 } 1238 1239 return true; 1240} 1241 1242 1243/// tryToMakeAllocaBePromotable - This returns true if the alloca only has 1244/// direct (non-volatile) loads and stores to it. If the alloca is close but 1245/// not quite there, this will transform the code to allow promotion. As such, 1246/// it is a non-pure predicate. 1247static bool tryToMakeAllocaBePromotable(AllocaInst *AI, const DataLayout &DL) { 1248 SetVector<Instruction*, SmallVector<Instruction*, 4>, 1249 SmallPtrSet<Instruction*, 4> > InstsToRewrite; 1250 for (User *U : AI->users()) { 1251 if (LoadInst *LI = dyn_cast<LoadInst>(U)) { 1252 if (!LI->isSimple()) 1253 return false; 1254 continue; 1255 } 1256 1257 if (StoreInst *SI = dyn_cast<StoreInst>(U)) { 1258 if (SI->getOperand(0) == AI || !SI->isSimple()) 1259 return false; // Don't allow a store OF the AI, only INTO the AI. 1260 continue; 1261 } 1262 1263 if (SelectInst *SI = dyn_cast<SelectInst>(U)) { 1264 // If the condition being selected on is a constant, fold the select, yes 1265 // this does (rarely) happen early on. 1266 if (ConstantInt *CI = dyn_cast<ConstantInt>(SI->getCondition())) { 1267 Value *Result = SI->getOperand(1+CI->isZero()); 1268 SI->replaceAllUsesWith(Result); 1269 SI->eraseFromParent(); 1270 1271 // This is very rare and we just scrambled the use list of AI, start 1272 // over completely. 1273 return tryToMakeAllocaBePromotable(AI, DL); 1274 } 1275 1276 // If it is safe to turn "load (select c, AI, ptr)" into a select of two 1277 // loads, then we can transform this by rewriting the select. 1278 if (!isSafeSelectToSpeculate(SI)) 1279 return false; 1280 1281 InstsToRewrite.insert(SI); 1282 continue; 1283 } 1284 1285 if (PHINode *PN = dyn_cast<PHINode>(U)) { 1286 if (PN->use_empty()) { // Dead PHIs can be stripped. 1287 InstsToRewrite.insert(PN); 1288 continue; 1289 } 1290 1291 // If it is safe to turn "load (phi [AI, ptr, ...])" into a PHI of loads 1292 // in the pred blocks, then we can transform this by rewriting the PHI. 1293 if (!isSafePHIToSpeculate(PN)) 1294 return false; 1295 1296 InstsToRewrite.insert(PN); 1297 continue; 1298 } 1299 1300 if (BitCastInst *BCI = dyn_cast<BitCastInst>(U)) { 1301 if (onlyUsedByLifetimeMarkers(BCI)) { 1302 InstsToRewrite.insert(BCI); 1303 continue; 1304 } 1305 } 1306 1307 return false; 1308 } 1309 1310 // If there are no instructions to rewrite, then all uses are load/stores and 1311 // we're done! 1312 if (InstsToRewrite.empty()) 1313 return true; 1314 1315 // If we have instructions that need to be rewritten for this to be promotable 1316 // take care of it now. 1317 for (unsigned i = 0, e = InstsToRewrite.size(); i != e; ++i) { 1318 if (BitCastInst *BCI = dyn_cast<BitCastInst>(InstsToRewrite[i])) { 1319 // This could only be a bitcast used by nothing but lifetime intrinsics. 1320 for (BitCastInst::user_iterator I = BCI->user_begin(), E = BCI->user_end(); 1321 I != E;) 1322 cast<Instruction>(*I++)->eraseFromParent(); 1323 BCI->eraseFromParent(); 1324 continue; 1325 } 1326 1327 if (SelectInst *SI = dyn_cast<SelectInst>(InstsToRewrite[i])) { 1328 // Selects in InstsToRewrite only have load uses. Rewrite each as two 1329 // loads with a new select. 1330 while (!SI->use_empty()) { 1331 LoadInst *LI = cast<LoadInst>(SI->user_back()); 1332 1333 IRBuilder<> Builder(LI); 1334 LoadInst *TrueLoad = 1335 Builder.CreateLoad(SI->getTrueValue(), LI->getName()+".t"); 1336 LoadInst *FalseLoad = 1337 Builder.CreateLoad(SI->getFalseValue(), LI->getName()+".f"); 1338 1339 // Transfer alignment and AA info if present. 1340 TrueLoad->setAlignment(LI->getAlignment()); 1341 FalseLoad->setAlignment(LI->getAlignment()); 1342 1343 AAMDNodes Tags; 1344 LI->getAAMetadata(Tags); 1345 if (Tags) { 1346 TrueLoad->setAAMetadata(Tags); 1347 FalseLoad->setAAMetadata(Tags); 1348 } 1349 1350 Value *V = Builder.CreateSelect(SI->getCondition(), TrueLoad, FalseLoad); 1351 V->takeName(LI); 1352 LI->replaceAllUsesWith(V); 1353 LI->eraseFromParent(); 1354 } 1355 1356 // Now that all the loads are gone, the select is gone too. 1357 SI->eraseFromParent(); 1358 continue; 1359 } 1360 1361 // Otherwise, we have a PHI node which allows us to push the loads into the 1362 // predecessors. 1363 PHINode *PN = cast<PHINode>(InstsToRewrite[i]); 1364 if (PN->use_empty()) { 1365 PN->eraseFromParent(); 1366 continue; 1367 } 1368 1369 Type *LoadTy = cast<PointerType>(PN->getType())->getElementType(); 1370 PHINode *NewPN = PHINode::Create(LoadTy, PN->getNumIncomingValues(), 1371 PN->getName()+".ld", PN); 1372 1373 // Get the AA tags and alignment to use from one of the loads. It doesn't 1374 // matter which one we get and if any differ, it doesn't matter. 1375 LoadInst *SomeLoad = cast<LoadInst>(PN->user_back()); 1376 1377 AAMDNodes AATags; 1378 SomeLoad->getAAMetadata(AATags); 1379 unsigned Align = SomeLoad->getAlignment(); 1380 1381 // Rewrite all loads of the PN to use the new PHI. 1382 while (!PN->use_empty()) { 1383 LoadInst *LI = cast<LoadInst>(PN->user_back()); 1384 LI->replaceAllUsesWith(NewPN); 1385 LI->eraseFromParent(); 1386 } 1387 1388 // Inject loads into all of the pred blocks. Keep track of which blocks we 1389 // insert them into in case we have multiple edges from the same block. 1390 DenseMap<BasicBlock*, LoadInst*> InsertedLoads; 1391 1392 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 1393 BasicBlock *Pred = PN->getIncomingBlock(i); 1394 LoadInst *&Load = InsertedLoads[Pred]; 1395 if (!Load) { 1396 Load = new LoadInst(PN->getIncomingValue(i), 1397 PN->getName() + "." + Pred->getName(), 1398 Pred->getTerminator()); 1399 Load->setAlignment(Align); 1400 if (AATags) Load->setAAMetadata(AATags); 1401 } 1402 1403 NewPN->addIncoming(Load, Pred); 1404 } 1405 1406 PN->eraseFromParent(); 1407 } 1408 1409 ++NumAdjusted; 1410 return true; 1411} 1412 1413bool SROA::performPromotion(Function &F) { 1414 std::vector<AllocaInst*> Allocas; 1415 const DataLayout &DL = F.getParent()->getDataLayout(); 1416 DominatorTree *DT = nullptr; 1417 if (HasDomTree) 1418 DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree(); 1419 AssumptionCache &AC = 1420 getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F); 1421 1422 BasicBlock &BB = F.getEntryBlock(); // Get the entry node for the function 1423 DIBuilder DIB(*F.getParent(), /*AllowUnresolved*/ false); 1424 bool Changed = false; 1425 SmallVector<Instruction*, 64> Insts; 1426 while (1) { 1427 Allocas.clear(); 1428 1429 // Find allocas that are safe to promote, by looking at all instructions in 1430 // the entry node 1431 for (BasicBlock::iterator I = BB.begin(), E = --BB.end(); I != E; ++I) 1432 if (AllocaInst *AI = dyn_cast<AllocaInst>(I)) // Is it an alloca? 1433 if (tryToMakeAllocaBePromotable(AI, DL)) 1434 Allocas.push_back(AI); 1435 1436 if (Allocas.empty()) break; 1437 1438 if (HasDomTree) 1439 PromoteMemToReg(Allocas, *DT, nullptr, &AC); 1440 else { 1441 SSAUpdater SSA; 1442 for (unsigned i = 0, e = Allocas.size(); i != e; ++i) { 1443 AllocaInst *AI = Allocas[i]; 1444 1445 // Build list of instructions to promote. 1446 for (User *U : AI->users()) 1447 Insts.push_back(cast<Instruction>(U)); 1448 AllocaPromoter(Insts, SSA, &DIB).run(AI, Insts); 1449 Insts.clear(); 1450 } 1451 } 1452 NumPromoted += Allocas.size(); 1453 Changed = true; 1454 } 1455 1456 return Changed; 1457} 1458 1459 1460/// ShouldAttemptScalarRepl - Decide if an alloca is a good candidate for 1461/// SROA. It must be a struct or array type with a small number of elements. 1462bool SROA::ShouldAttemptScalarRepl(AllocaInst *AI) { 1463 Type *T = AI->getAllocatedType(); 1464 // Do not promote any struct that has too many members. 1465 if (StructType *ST = dyn_cast<StructType>(T)) 1466 return ST->getNumElements() <= StructMemberThreshold; 1467 // Do not promote any array that has too many elements. 1468 if (ArrayType *AT = dyn_cast<ArrayType>(T)) 1469 return AT->getNumElements() <= ArrayElementThreshold; 1470 return false; 1471} 1472 1473// performScalarRepl - This algorithm is a simple worklist driven algorithm, 1474// which runs on all of the alloca instructions in the entry block, removing 1475// them if they are only used by getelementptr instructions. 1476// 1477bool SROA::performScalarRepl(Function &F) { 1478 std::vector<AllocaInst*> WorkList; 1479 const DataLayout &DL = F.getParent()->getDataLayout(); 1480 1481 // Scan the entry basic block, adding allocas to the worklist. 1482 BasicBlock &BB = F.getEntryBlock(); 1483 for (BasicBlock::iterator I = BB.begin(), E = BB.end(); I != E; ++I) 1484 if (AllocaInst *A = dyn_cast<AllocaInst>(I)) 1485 WorkList.push_back(A); 1486 1487 // Process the worklist 1488 bool Changed = false; 1489 while (!WorkList.empty()) { 1490 AllocaInst *AI = WorkList.back(); 1491 WorkList.pop_back(); 1492 1493 // Handle dead allocas trivially. These can be formed by SROA'ing arrays 1494 // with unused elements. 1495 if (AI->use_empty()) { 1496 AI->eraseFromParent(); 1497 Changed = true; 1498 continue; 1499 } 1500 1501 // If this alloca is impossible for us to promote, reject it early. 1502 if (AI->isArrayAllocation() || !AI->getAllocatedType()->isSized()) 1503 continue; 1504 1505 // Check to see if we can perform the core SROA transformation. We cannot 1506 // transform the allocation instruction if it is an array allocation 1507 // (allocations OF arrays are ok though), and an allocation of a scalar 1508 // value cannot be decomposed at all. 1509 uint64_t AllocaSize = DL.getTypeAllocSize(AI->getAllocatedType()); 1510 1511 // Do not promote [0 x %struct]. 1512 if (AllocaSize == 0) continue; 1513 1514 // Do not promote any struct whose size is too big. 1515 if (AllocaSize > SRThreshold) continue; 1516 1517 // If the alloca looks like a good candidate for scalar replacement, and if 1518 // all its users can be transformed, then split up the aggregate into its 1519 // separate elements. 1520 if (ShouldAttemptScalarRepl(AI) && isSafeAllocaToScalarRepl(AI)) { 1521 DoScalarReplacement(AI, WorkList); 1522 Changed = true; 1523 continue; 1524 } 1525 1526 // If we can turn this aggregate value (potentially with casts) into a 1527 // simple scalar value that can be mem2reg'd into a register value. 1528 // IsNotTrivial tracks whether this is something that mem2reg could have 1529 // promoted itself. If so, we don't want to transform it needlessly. Note 1530 // that we can't just check based on the type: the alloca may be of an i32 1531 // but that has pointer arithmetic to set byte 3 of it or something. 1532 if (AllocaInst *NewAI = 1533 ConvertToScalarInfo((unsigned)AllocaSize, DL, ScalarLoadThreshold) 1534 .TryConvert(AI)) { 1535 NewAI->takeName(AI); 1536 AI->eraseFromParent(); 1537 ++NumConverted; 1538 Changed = true; 1539 continue; 1540 } 1541 1542 // Otherwise, couldn't process this alloca. 1543 } 1544 1545 return Changed; 1546} 1547 1548/// DoScalarReplacement - This alloca satisfied the isSafeAllocaToScalarRepl 1549/// predicate, do SROA now. 1550void SROA::DoScalarReplacement(AllocaInst *AI, 1551 std::vector<AllocaInst*> &WorkList) { 1552 DEBUG(dbgs() << "Found inst to SROA: " << *AI << '\n'); 1553 SmallVector<AllocaInst*, 32> ElementAllocas; 1554 if (StructType *ST = dyn_cast<StructType>(AI->getAllocatedType())) { 1555 ElementAllocas.reserve(ST->getNumContainedTypes()); 1556 for (unsigned i = 0, e = ST->getNumContainedTypes(); i != e; ++i) { 1557 AllocaInst *NA = new AllocaInst(ST->getContainedType(i), nullptr, 1558 AI->getAlignment(), 1559 AI->getName() + "." + Twine(i), AI); 1560 ElementAllocas.push_back(NA); 1561 WorkList.push_back(NA); // Add to worklist for recursive processing 1562 } 1563 } else { 1564 ArrayType *AT = cast<ArrayType>(AI->getAllocatedType()); 1565 ElementAllocas.reserve(AT->getNumElements()); 1566 Type *ElTy = AT->getElementType(); 1567 for (unsigned i = 0, e = AT->getNumElements(); i != e; ++i) { 1568 AllocaInst *NA = new AllocaInst(ElTy, nullptr, AI->getAlignment(), 1569 AI->getName() + "." + Twine(i), AI); 1570 ElementAllocas.push_back(NA); 1571 WorkList.push_back(NA); // Add to worklist for recursive processing 1572 } 1573 } 1574 1575 // Now that we have created the new alloca instructions, rewrite all the 1576 // uses of the old alloca. 1577 RewriteForScalarRepl(AI, AI, 0, ElementAllocas); 1578 1579 // Now erase any instructions that were made dead while rewriting the alloca. 1580 DeleteDeadInstructions(); 1581 AI->eraseFromParent(); 1582 1583 ++NumReplaced; 1584} 1585 1586/// DeleteDeadInstructions - Erase instructions on the DeadInstrs list, 1587/// recursively including all their operands that become trivially dead. 1588void SROA::DeleteDeadInstructions() { 1589 while (!DeadInsts.empty()) { 1590 Instruction *I = cast<Instruction>(DeadInsts.pop_back_val()); 1591 1592 for (User::op_iterator OI = I->op_begin(), E = I->op_end(); OI != E; ++OI) 1593 if (Instruction *U = dyn_cast<Instruction>(*OI)) { 1594 // Zero out the operand and see if it becomes trivially dead. 1595 // (But, don't add allocas to the dead instruction list -- they are 1596 // already on the worklist and will be deleted separately.) 1597 *OI = nullptr; 1598 if (isInstructionTriviallyDead(U) && !isa<AllocaInst>(U)) 1599 DeadInsts.push_back(U); 1600 } 1601 1602 I->eraseFromParent(); 1603 } 1604} 1605 1606/// isSafeForScalarRepl - Check if instruction I is a safe use with regard to 1607/// performing scalar replacement of alloca AI. The results are flagged in 1608/// the Info parameter. Offset indicates the position within AI that is 1609/// referenced by this instruction. 1610void SROA::isSafeForScalarRepl(Instruction *I, uint64_t Offset, 1611 AllocaInfo &Info) { 1612 const DataLayout &DL = I->getModule()->getDataLayout(); 1613 for (Use &U : I->uses()) { 1614 Instruction *User = cast<Instruction>(U.getUser()); 1615 1616 if (BitCastInst *BC = dyn_cast<BitCastInst>(User)) { 1617 isSafeForScalarRepl(BC, Offset, Info); 1618 } else if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(User)) { 1619 uint64_t GEPOffset = Offset; 1620 isSafeGEP(GEPI, GEPOffset, Info); 1621 if (!Info.isUnsafe) 1622 isSafeForScalarRepl(GEPI, GEPOffset, Info); 1623 } else if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(User)) { 1624 ConstantInt *Length = dyn_cast<ConstantInt>(MI->getLength()); 1625 if (!Length || Length->isNegative()) 1626 return MarkUnsafe(Info, User); 1627 1628 isSafeMemAccess(Offset, Length->getZExtValue(), nullptr, 1629 U.getOperandNo() == 0, Info, MI, 1630 true /*AllowWholeAccess*/); 1631 } else if (LoadInst *LI = dyn_cast<LoadInst>(User)) { 1632 if (!LI->isSimple()) 1633 return MarkUnsafe(Info, User); 1634 Type *LIType = LI->getType(); 1635 isSafeMemAccess(Offset, DL.getTypeAllocSize(LIType), LIType, false, Info, 1636 LI, true /*AllowWholeAccess*/); 1637 Info.hasALoadOrStore = true; 1638 1639 } else if (StoreInst *SI = dyn_cast<StoreInst>(User)) { 1640 // Store is ok if storing INTO the pointer, not storing the pointer 1641 if (!SI->isSimple() || SI->getOperand(0) == I) 1642 return MarkUnsafe(Info, User); 1643 1644 Type *SIType = SI->getOperand(0)->getType(); 1645 isSafeMemAccess(Offset, DL.getTypeAllocSize(SIType), SIType, true, Info, 1646 SI, true /*AllowWholeAccess*/); 1647 Info.hasALoadOrStore = true; 1648 } else if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(User)) { 1649 if (II->getIntrinsicID() != Intrinsic::lifetime_start && 1650 II->getIntrinsicID() != Intrinsic::lifetime_end) 1651 return MarkUnsafe(Info, User); 1652 } else if (isa<PHINode>(User) || isa<SelectInst>(User)) { 1653 isSafePHISelectUseForScalarRepl(User, Offset, Info); 1654 } else { 1655 return MarkUnsafe(Info, User); 1656 } 1657 if (Info.isUnsafe) return; 1658 } 1659} 1660 1661 1662/// isSafePHIUseForScalarRepl - If we see a PHI node or select using a pointer 1663/// derived from the alloca, we can often still split the alloca into elements. 1664/// This is useful if we have a large alloca where one element is phi'd 1665/// together somewhere: we can SRoA and promote all the other elements even if 1666/// we end up not being able to promote this one. 1667/// 1668/// All we require is that the uses of the PHI do not index into other parts of 1669/// the alloca. The most important use case for this is single load and stores 1670/// that are PHI'd together, which can happen due to code sinking. 1671void SROA::isSafePHISelectUseForScalarRepl(Instruction *I, uint64_t Offset, 1672 AllocaInfo &Info) { 1673 // If we've already checked this PHI, don't do it again. 1674 if (PHINode *PN = dyn_cast<PHINode>(I)) 1675 if (!Info.CheckedPHIs.insert(PN).second) 1676 return; 1677 1678 const DataLayout &DL = I->getModule()->getDataLayout(); 1679 for (User *U : I->users()) { 1680 Instruction *UI = cast<Instruction>(U); 1681 1682 if (BitCastInst *BC = dyn_cast<BitCastInst>(UI)) { 1683 isSafePHISelectUseForScalarRepl(BC, Offset, Info); 1684 } else if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(UI)) { 1685 // Only allow "bitcast" GEPs for simplicity. We could generalize this, 1686 // but would have to prove that we're staying inside of an element being 1687 // promoted. 1688 if (!GEPI->hasAllZeroIndices()) 1689 return MarkUnsafe(Info, UI); 1690 isSafePHISelectUseForScalarRepl(GEPI, Offset, Info); 1691 } else if (LoadInst *LI = dyn_cast<LoadInst>(UI)) { 1692 if (!LI->isSimple()) 1693 return MarkUnsafe(Info, UI); 1694 Type *LIType = LI->getType(); 1695 isSafeMemAccess(Offset, DL.getTypeAllocSize(LIType), LIType, false, Info, 1696 LI, false /*AllowWholeAccess*/); 1697 Info.hasALoadOrStore = true; 1698 1699 } else if (StoreInst *SI = dyn_cast<StoreInst>(UI)) { 1700 // Store is ok if storing INTO the pointer, not storing the pointer 1701 if (!SI->isSimple() || SI->getOperand(0) == I) 1702 return MarkUnsafe(Info, UI); 1703 1704 Type *SIType = SI->getOperand(0)->getType(); 1705 isSafeMemAccess(Offset, DL.getTypeAllocSize(SIType), SIType, true, Info, 1706 SI, false /*AllowWholeAccess*/); 1707 Info.hasALoadOrStore = true; 1708 } else if (isa<PHINode>(UI) || isa<SelectInst>(UI)) { 1709 isSafePHISelectUseForScalarRepl(UI, Offset, Info); 1710 } else { 1711 return MarkUnsafe(Info, UI); 1712 } 1713 if (Info.isUnsafe) return; 1714 } 1715} 1716 1717/// isSafeGEP - Check if a GEP instruction can be handled for scalar 1718/// replacement. It is safe when all the indices are constant, in-bounds 1719/// references, and when the resulting offset corresponds to an element within 1720/// the alloca type. The results are flagged in the Info parameter. Upon 1721/// return, Offset is adjusted as specified by the GEP indices. 1722void SROA::isSafeGEP(GetElementPtrInst *GEPI, 1723 uint64_t &Offset, AllocaInfo &Info) { 1724 gep_type_iterator GEPIt = gep_type_begin(GEPI), E = gep_type_end(GEPI); 1725 if (GEPIt == E) 1726 return; 1727 bool NonConstant = false; 1728 unsigned NonConstantIdxSize = 0; 1729 1730 // Walk through the GEP type indices, checking the types that this indexes 1731 // into. 1732 for (; GEPIt != E; ++GEPIt) { 1733 // Ignore struct elements, no extra checking needed for these. 1734 if ((*GEPIt)->isStructTy()) 1735 continue; 1736 1737 ConstantInt *IdxVal = dyn_cast<ConstantInt>(GEPIt.getOperand()); 1738 if (!IdxVal) 1739 return MarkUnsafe(Info, GEPI); 1740 } 1741 1742 // Compute the offset due to this GEP and check if the alloca has a 1743 // component element at that offset. 1744 SmallVector<Value*, 8> Indices(GEPI->op_begin() + 1, GEPI->op_end()); 1745 // If this GEP is non-constant then the last operand must have been a 1746 // dynamic index into a vector. Pop this now as it has no impact on the 1747 // constant part of the offset. 1748 if (NonConstant) 1749 Indices.pop_back(); 1750 1751 const DataLayout &DL = GEPI->getModule()->getDataLayout(); 1752 Offset += DL.getIndexedOffset(GEPI->getPointerOperandType(), Indices); 1753 if (!TypeHasComponent(Info.AI->getAllocatedType(), Offset, NonConstantIdxSize, 1754 DL)) 1755 MarkUnsafe(Info, GEPI); 1756} 1757 1758/// isHomogeneousAggregate - Check if type T is a struct or array containing 1759/// elements of the same type (which is always true for arrays). If so, 1760/// return true with NumElts and EltTy set to the number of elements and the 1761/// element type, respectively. 1762static bool isHomogeneousAggregate(Type *T, unsigned &NumElts, 1763 Type *&EltTy) { 1764 if (ArrayType *AT = dyn_cast<ArrayType>(T)) { 1765 NumElts = AT->getNumElements(); 1766 EltTy = (NumElts == 0 ? nullptr : AT->getElementType()); 1767 return true; 1768 } 1769 if (StructType *ST = dyn_cast<StructType>(T)) { 1770 NumElts = ST->getNumContainedTypes(); 1771 EltTy = (NumElts == 0 ? nullptr : ST->getContainedType(0)); 1772 for (unsigned n = 1; n < NumElts; ++n) { 1773 if (ST->getContainedType(n) != EltTy) 1774 return false; 1775 } 1776 return true; 1777 } 1778 return false; 1779} 1780 1781/// isCompatibleAggregate - Check if T1 and T2 are either the same type or are 1782/// "homogeneous" aggregates with the same element type and number of elements. 1783static bool isCompatibleAggregate(Type *T1, Type *T2) { 1784 if (T1 == T2) 1785 return true; 1786 1787 unsigned NumElts1, NumElts2; 1788 Type *EltTy1, *EltTy2; 1789 if (isHomogeneousAggregate(T1, NumElts1, EltTy1) && 1790 isHomogeneousAggregate(T2, NumElts2, EltTy2) && 1791 NumElts1 == NumElts2 && 1792 EltTy1 == EltTy2) 1793 return true; 1794 1795 return false; 1796} 1797 1798/// isSafeMemAccess - Check if a load/store/memcpy operates on the entire AI 1799/// alloca or has an offset and size that corresponds to a component element 1800/// within it. The offset checked here may have been formed from a GEP with a 1801/// pointer bitcasted to a different type. 1802/// 1803/// If AllowWholeAccess is true, then this allows uses of the entire alloca as a 1804/// unit. If false, it only allows accesses known to be in a single element. 1805void SROA::isSafeMemAccess(uint64_t Offset, uint64_t MemSize, 1806 Type *MemOpType, bool isStore, 1807 AllocaInfo &Info, Instruction *TheAccess, 1808 bool AllowWholeAccess) { 1809 const DataLayout &DL = TheAccess->getModule()->getDataLayout(); 1810 // Check if this is a load/store of the entire alloca. 1811 if (Offset == 0 && AllowWholeAccess && 1812 MemSize == DL.getTypeAllocSize(Info.AI->getAllocatedType())) { 1813 // This can be safe for MemIntrinsics (where MemOpType is 0) and integer 1814 // loads/stores (which are essentially the same as the MemIntrinsics with 1815 // regard to copying padding between elements). But, if an alloca is 1816 // flagged as both a source and destination of such operations, we'll need 1817 // to check later for padding between elements. 1818 if (!MemOpType || MemOpType->isIntegerTy()) { 1819 if (isStore) 1820 Info.isMemCpyDst = true; 1821 else 1822 Info.isMemCpySrc = true; 1823 return; 1824 } 1825 // This is also safe for references using a type that is compatible with 1826 // the type of the alloca, so that loads/stores can be rewritten using 1827 // insertvalue/extractvalue. 1828 if (isCompatibleAggregate(MemOpType, Info.AI->getAllocatedType())) { 1829 Info.hasSubelementAccess = true; 1830 return; 1831 } 1832 } 1833 // Check if the offset/size correspond to a component within the alloca type. 1834 Type *T = Info.AI->getAllocatedType(); 1835 if (TypeHasComponent(T, Offset, MemSize, DL)) { 1836 Info.hasSubelementAccess = true; 1837 return; 1838 } 1839 1840 return MarkUnsafe(Info, TheAccess); 1841} 1842 1843/// TypeHasComponent - Return true if T has a component type with the 1844/// specified offset and size. If Size is zero, do not check the size. 1845bool SROA::TypeHasComponent(Type *T, uint64_t Offset, uint64_t Size, 1846 const DataLayout &DL) { 1847 Type *EltTy; 1848 uint64_t EltSize; 1849 if (StructType *ST = dyn_cast<StructType>(T)) { 1850 const StructLayout *Layout = DL.getStructLayout(ST); 1851 unsigned EltIdx = Layout->getElementContainingOffset(Offset); 1852 EltTy = ST->getContainedType(EltIdx); 1853 EltSize = DL.getTypeAllocSize(EltTy); 1854 Offset -= Layout->getElementOffset(EltIdx); 1855 } else if (ArrayType *AT = dyn_cast<ArrayType>(T)) { 1856 EltTy = AT->getElementType(); 1857 EltSize = DL.getTypeAllocSize(EltTy); 1858 if (Offset >= AT->getNumElements() * EltSize) 1859 return false; 1860 Offset %= EltSize; 1861 } else if (VectorType *VT = dyn_cast<VectorType>(T)) { 1862 EltTy = VT->getElementType(); 1863 EltSize = DL.getTypeAllocSize(EltTy); 1864 if (Offset >= VT->getNumElements() * EltSize) 1865 return false; 1866 Offset %= EltSize; 1867 } else { 1868 return false; 1869 } 1870 if (Offset == 0 && (Size == 0 || EltSize == Size)) 1871 return true; 1872 // Check if the component spans multiple elements. 1873 if (Offset + Size > EltSize) 1874 return false; 1875 return TypeHasComponent(EltTy, Offset, Size, DL); 1876} 1877 1878/// RewriteForScalarRepl - Alloca AI is being split into NewElts, so rewrite 1879/// the instruction I, which references it, to use the separate elements. 1880/// Offset indicates the position within AI that is referenced by this 1881/// instruction. 1882void SROA::RewriteForScalarRepl(Instruction *I, AllocaInst *AI, uint64_t Offset, 1883 SmallVectorImpl<AllocaInst *> &NewElts) { 1884 const DataLayout &DL = I->getModule()->getDataLayout(); 1885 for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); UI!=E;) { 1886 Use &TheUse = *UI++; 1887 Instruction *User = cast<Instruction>(TheUse.getUser()); 1888 1889 if (BitCastInst *BC = dyn_cast<BitCastInst>(User)) { 1890 RewriteBitCast(BC, AI, Offset, NewElts); 1891 continue; 1892 } 1893 1894 if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(User)) { 1895 RewriteGEP(GEPI, AI, Offset, NewElts); 1896 continue; 1897 } 1898 1899 if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(User)) { 1900 ConstantInt *Length = dyn_cast<ConstantInt>(MI->getLength()); 1901 uint64_t MemSize = Length->getZExtValue(); 1902 if (Offset == 0 && MemSize == DL.getTypeAllocSize(AI->getAllocatedType())) 1903 RewriteMemIntrinUserOfAlloca(MI, I, AI, NewElts); 1904 // Otherwise the intrinsic can only touch a single element and the 1905 // address operand will be updated, so nothing else needs to be done. 1906 continue; 1907 } 1908 1909 if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(User)) { 1910 if (II->getIntrinsicID() == Intrinsic::lifetime_start || 1911 II->getIntrinsicID() == Intrinsic::lifetime_end) { 1912 RewriteLifetimeIntrinsic(II, AI, Offset, NewElts); 1913 } 1914 continue; 1915 } 1916 1917 if (LoadInst *LI = dyn_cast<LoadInst>(User)) { 1918 Type *LIType = LI->getType(); 1919 1920 if (isCompatibleAggregate(LIType, AI->getAllocatedType())) { 1921 // Replace: 1922 // %res = load { i32, i32 }* %alloc 1923 // with: 1924 // %load.0 = load i32* %alloc.0 1925 // %insert.0 insertvalue { i32, i32 } zeroinitializer, i32 %load.0, 0 1926 // %load.1 = load i32* %alloc.1 1927 // %insert = insertvalue { i32, i32 } %insert.0, i32 %load.1, 1 1928 // (Also works for arrays instead of structs) 1929 Value *Insert = UndefValue::get(LIType); 1930 IRBuilder<> Builder(LI); 1931 for (unsigned i = 0, e = NewElts.size(); i != e; ++i) { 1932 Value *Load = Builder.CreateLoad(NewElts[i], "load"); 1933 Insert = Builder.CreateInsertValue(Insert, Load, i, "insert"); 1934 } 1935 LI->replaceAllUsesWith(Insert); 1936 DeadInsts.push_back(LI); 1937 } else if (LIType->isIntegerTy() && 1938 DL.getTypeAllocSize(LIType) == 1939 DL.getTypeAllocSize(AI->getAllocatedType())) { 1940 // If this is a load of the entire alloca to an integer, rewrite it. 1941 RewriteLoadUserOfWholeAlloca(LI, AI, NewElts); 1942 } 1943 continue; 1944 } 1945 1946 if (StoreInst *SI = dyn_cast<StoreInst>(User)) { 1947 Value *Val = SI->getOperand(0); 1948 Type *SIType = Val->getType(); 1949 if (isCompatibleAggregate(SIType, AI->getAllocatedType())) { 1950 // Replace: 1951 // store { i32, i32 } %val, { i32, i32 }* %alloc 1952 // with: 1953 // %val.0 = extractvalue { i32, i32 } %val, 0 1954 // store i32 %val.0, i32* %alloc.0 1955 // %val.1 = extractvalue { i32, i32 } %val, 1 1956 // store i32 %val.1, i32* %alloc.1 1957 // (Also works for arrays instead of structs) 1958 IRBuilder<> Builder(SI); 1959 for (unsigned i = 0, e = NewElts.size(); i != e; ++i) { 1960 Value *Extract = Builder.CreateExtractValue(Val, i, Val->getName()); 1961 Builder.CreateStore(Extract, NewElts[i]); 1962 } 1963 DeadInsts.push_back(SI); 1964 } else if (SIType->isIntegerTy() && 1965 DL.getTypeAllocSize(SIType) == 1966 DL.getTypeAllocSize(AI->getAllocatedType())) { 1967 // If this is a store of the entire alloca from an integer, rewrite it. 1968 RewriteStoreUserOfWholeAlloca(SI, AI, NewElts); 1969 } 1970 continue; 1971 } 1972 1973 if (isa<SelectInst>(User) || isa<PHINode>(User)) { 1974 // If we have a PHI user of the alloca itself (as opposed to a GEP or 1975 // bitcast) we have to rewrite it. GEP and bitcast uses will be RAUW'd to 1976 // the new pointer. 1977 if (!isa<AllocaInst>(I)) continue; 1978 1979 assert(Offset == 0 && NewElts[0] && 1980 "Direct alloca use should have a zero offset"); 1981 1982 // If we have a use of the alloca, we know the derived uses will be 1983 // utilizing just the first element of the scalarized result. Insert a 1984 // bitcast of the first alloca before the user as required. 1985 AllocaInst *NewAI = NewElts[0]; 1986 BitCastInst *BCI = new BitCastInst(NewAI, AI->getType(), "", NewAI); 1987 NewAI->moveBefore(BCI); 1988 TheUse = BCI; 1989 continue; 1990 } 1991 } 1992} 1993 1994/// RewriteBitCast - Update a bitcast reference to the alloca being replaced 1995/// and recursively continue updating all of its uses. 1996void SROA::RewriteBitCast(BitCastInst *BC, AllocaInst *AI, uint64_t Offset, 1997 SmallVectorImpl<AllocaInst *> &NewElts) { 1998 RewriteForScalarRepl(BC, AI, Offset, NewElts); 1999 if (BC->getOperand(0) != AI) 2000 return; 2001 2002 // The bitcast references the original alloca. Replace its uses with 2003 // references to the alloca containing offset zero (which is normally at 2004 // index zero, but might not be in cases involving structs with elements 2005 // of size zero). 2006 Type *T = AI->getAllocatedType(); 2007 uint64_t EltOffset = 0; 2008 Type *IdxTy; 2009 uint64_t Idx = FindElementAndOffset(T, EltOffset, IdxTy, 2010 BC->getModule()->getDataLayout()); 2011 Instruction *Val = NewElts[Idx]; 2012 if (Val->getType() != BC->getDestTy()) { 2013 Val = new BitCastInst(Val, BC->getDestTy(), "", BC); 2014 Val->takeName(BC); 2015 } 2016 BC->replaceAllUsesWith(Val); 2017 DeadInsts.push_back(BC); 2018} 2019 2020/// FindElementAndOffset - Return the index of the element containing Offset 2021/// within the specified type, which must be either a struct or an array. 2022/// Sets T to the type of the element and Offset to the offset within that 2023/// element. IdxTy is set to the type of the index result to be used in a 2024/// GEP instruction. 2025uint64_t SROA::FindElementAndOffset(Type *&T, uint64_t &Offset, Type *&IdxTy, 2026 const DataLayout &DL) { 2027 uint64_t Idx = 0; 2028 2029 if (StructType *ST = dyn_cast<StructType>(T)) { 2030 const StructLayout *Layout = DL.getStructLayout(ST); 2031 Idx = Layout->getElementContainingOffset(Offset); 2032 T = ST->getContainedType(Idx); 2033 Offset -= Layout->getElementOffset(Idx); 2034 IdxTy = Type::getInt32Ty(T->getContext()); 2035 return Idx; 2036 } else if (ArrayType *AT = dyn_cast<ArrayType>(T)) { 2037 T = AT->getElementType(); 2038 uint64_t EltSize = DL.getTypeAllocSize(T); 2039 Idx = Offset / EltSize; 2040 Offset -= Idx * EltSize; 2041 IdxTy = Type::getInt64Ty(T->getContext()); 2042 return Idx; 2043 } 2044 VectorType *VT = cast<VectorType>(T); 2045 T = VT->getElementType(); 2046 uint64_t EltSize = DL.getTypeAllocSize(T); 2047 Idx = Offset / EltSize; 2048 Offset -= Idx * EltSize; 2049 IdxTy = Type::getInt64Ty(T->getContext()); 2050 return Idx; 2051} 2052 2053/// RewriteGEP - Check if this GEP instruction moves the pointer across 2054/// elements of the alloca that are being split apart, and if so, rewrite 2055/// the GEP to be relative to the new element. 2056void SROA::RewriteGEP(GetElementPtrInst *GEPI, AllocaInst *AI, uint64_t Offset, 2057 SmallVectorImpl<AllocaInst *> &NewElts) { 2058 uint64_t OldOffset = Offset; 2059 const DataLayout &DL = GEPI->getModule()->getDataLayout(); 2060 SmallVector<Value*, 8> Indices(GEPI->op_begin() + 1, GEPI->op_end()); 2061 // If the GEP was dynamic then it must have been a dynamic vector lookup. 2062 // In this case, it must be the last GEP operand which is dynamic so keep that 2063 // aside until we've found the constant GEP offset then add it back in at the 2064 // end. 2065 Value* NonConstantIdx = nullptr; 2066 if (!GEPI->hasAllConstantIndices()) 2067 NonConstantIdx = Indices.pop_back_val(); 2068 Offset += DL.getIndexedOffset(GEPI->getPointerOperandType(), Indices); 2069 2070 RewriteForScalarRepl(GEPI, AI, Offset, NewElts); 2071 2072 Type *T = AI->getAllocatedType(); 2073 Type *IdxTy; 2074 uint64_t OldIdx = FindElementAndOffset(T, OldOffset, IdxTy, DL); 2075 if (GEPI->getOperand(0) == AI) 2076 OldIdx = ~0ULL; // Force the GEP to be rewritten. 2077 2078 T = AI->getAllocatedType(); 2079 uint64_t EltOffset = Offset; 2080 uint64_t Idx = FindElementAndOffset(T, EltOffset, IdxTy, DL); 2081 2082 // If this GEP does not move the pointer across elements of the alloca 2083 // being split, then it does not needs to be rewritten. 2084 if (Idx == OldIdx) 2085 return; 2086 2087 Type *i32Ty = Type::getInt32Ty(AI->getContext()); 2088 SmallVector<Value*, 8> NewArgs; 2089 NewArgs.push_back(Constant::getNullValue(i32Ty)); 2090 while (EltOffset != 0) { 2091 uint64_t EltIdx = FindElementAndOffset(T, EltOffset, IdxTy, DL); 2092 NewArgs.push_back(ConstantInt::get(IdxTy, EltIdx)); 2093 } 2094 if (NonConstantIdx) { 2095 Type* GepTy = T; 2096 // This GEP has a dynamic index. We need to add "i32 0" to index through 2097 // any structs or arrays in the original type until we get to the vector 2098 // to index. 2099 while (!isa<VectorType>(GepTy)) { 2100 NewArgs.push_back(Constant::getNullValue(i32Ty)); 2101 GepTy = cast<CompositeType>(GepTy)->getTypeAtIndex(0U); 2102 } 2103 NewArgs.push_back(NonConstantIdx); 2104 } 2105 Instruction *Val = NewElts[Idx]; 2106 if (NewArgs.size() > 1) { 2107 Val = GetElementPtrInst::CreateInBounds(Val, NewArgs, "", GEPI); 2108 Val->takeName(GEPI); 2109 } 2110 if (Val->getType() != GEPI->getType()) 2111 Val = new BitCastInst(Val, GEPI->getType(), Val->getName(), GEPI); 2112 GEPI->replaceAllUsesWith(Val); 2113 DeadInsts.push_back(GEPI); 2114} 2115 2116/// RewriteLifetimeIntrinsic - II is a lifetime.start/lifetime.end. Rewrite it 2117/// to mark the lifetime of the scalarized memory. 2118void SROA::RewriteLifetimeIntrinsic(IntrinsicInst *II, AllocaInst *AI, 2119 uint64_t Offset, 2120 SmallVectorImpl<AllocaInst *> &NewElts) { 2121 ConstantInt *OldSize = cast<ConstantInt>(II->getArgOperand(0)); 2122 // Put matching lifetime markers on everything from Offset up to 2123 // Offset+OldSize. 2124 Type *AIType = AI->getAllocatedType(); 2125 const DataLayout &DL = II->getModule()->getDataLayout(); 2126 uint64_t NewOffset = Offset; 2127 Type *IdxTy; 2128 uint64_t Idx = FindElementAndOffset(AIType, NewOffset, IdxTy, DL); 2129 2130 IRBuilder<> Builder(II); 2131 uint64_t Size = OldSize->getLimitedValue(); 2132 2133 if (NewOffset) { 2134 // Splice the first element and index 'NewOffset' bytes in. SROA will 2135 // split the alloca again later. 2136 unsigned AS = AI->getType()->getAddressSpace(); 2137 Value *V = Builder.CreateBitCast(NewElts[Idx], Builder.getInt8PtrTy(AS)); 2138 V = Builder.CreateGEP(Builder.getInt8Ty(), V, Builder.getInt64(NewOffset)); 2139 2140 IdxTy = NewElts[Idx]->getAllocatedType(); 2141 uint64_t EltSize = DL.getTypeAllocSize(IdxTy) - NewOffset; 2142 if (EltSize > Size) { 2143 EltSize = Size; 2144 Size = 0; 2145 } else { 2146 Size -= EltSize; 2147 } 2148 if (II->getIntrinsicID() == Intrinsic::lifetime_start) 2149 Builder.CreateLifetimeStart(V, Builder.getInt64(EltSize)); 2150 else 2151 Builder.CreateLifetimeEnd(V, Builder.getInt64(EltSize)); 2152 ++Idx; 2153 } 2154 2155 for (; Idx != NewElts.size() && Size; ++Idx) { 2156 IdxTy = NewElts[Idx]->getAllocatedType(); 2157 uint64_t EltSize = DL.getTypeAllocSize(IdxTy); 2158 if (EltSize > Size) { 2159 EltSize = Size; 2160 Size = 0; 2161 } else { 2162 Size -= EltSize; 2163 } 2164 if (II->getIntrinsicID() == Intrinsic::lifetime_start) 2165 Builder.CreateLifetimeStart(NewElts[Idx], 2166 Builder.getInt64(EltSize)); 2167 else 2168 Builder.CreateLifetimeEnd(NewElts[Idx], 2169 Builder.getInt64(EltSize)); 2170 } 2171 DeadInsts.push_back(II); 2172} 2173 2174/// RewriteMemIntrinUserOfAlloca - MI is a memcpy/memset/memmove from or to AI. 2175/// Rewrite it to copy or set the elements of the scalarized memory. 2176void 2177SROA::RewriteMemIntrinUserOfAlloca(MemIntrinsic *MI, Instruction *Inst, 2178 AllocaInst *AI, 2179 SmallVectorImpl<AllocaInst *> &NewElts) { 2180 // If this is a memcpy/memmove, construct the other pointer as the 2181 // appropriate type. The "Other" pointer is the pointer that goes to memory 2182 // that doesn't have anything to do with the alloca that we are promoting. For 2183 // memset, this Value* stays null. 2184 Value *OtherPtr = nullptr; 2185 unsigned MemAlignment = MI->getAlignment(); 2186 if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(MI)) { // memmove/memcopy 2187 if (Inst == MTI->getRawDest()) 2188 OtherPtr = MTI->getRawSource(); 2189 else { 2190 assert(Inst == MTI->getRawSource()); 2191 OtherPtr = MTI->getRawDest(); 2192 } 2193 } 2194 2195 // If there is an other pointer, we want to convert it to the same pointer 2196 // type as AI has, so we can GEP through it safely. 2197 if (OtherPtr) { 2198 unsigned AddrSpace = 2199 cast<PointerType>(OtherPtr->getType())->getAddressSpace(); 2200 2201 // Remove bitcasts and all-zero GEPs from OtherPtr. This is an 2202 // optimization, but it's also required to detect the corner case where 2203 // both pointer operands are referencing the same memory, and where 2204 // OtherPtr may be a bitcast or GEP that currently being rewritten. (This 2205 // function is only called for mem intrinsics that access the whole 2206 // aggregate, so non-zero GEPs are not an issue here.) 2207 OtherPtr = OtherPtr->stripPointerCasts(); 2208 2209 // Copying the alloca to itself is a no-op: just delete it. 2210 if (OtherPtr == AI || OtherPtr == NewElts[0]) { 2211 // This code will run twice for a no-op memcpy -- once for each operand. 2212 // Put only one reference to MI on the DeadInsts list. 2213 for (SmallVectorImpl<Value *>::const_iterator I = DeadInsts.begin(), 2214 E = DeadInsts.end(); I != E; ++I) 2215 if (*I == MI) return; 2216 DeadInsts.push_back(MI); 2217 return; 2218 } 2219 2220 // If the pointer is not the right type, insert a bitcast to the right 2221 // type. 2222 Type *NewTy = 2223 PointerType::get(AI->getType()->getElementType(), AddrSpace); 2224 2225 if (OtherPtr->getType() != NewTy) 2226 OtherPtr = new BitCastInst(OtherPtr, NewTy, OtherPtr->getName(), MI); 2227 } 2228 2229 // Process each element of the aggregate. 2230 bool SROADest = MI->getRawDest() == Inst; 2231 2232 Constant *Zero = Constant::getNullValue(Type::getInt32Ty(MI->getContext())); 2233 const DataLayout &DL = MI->getModule()->getDataLayout(); 2234 2235 for (unsigned i = 0, e = NewElts.size(); i != e; ++i) { 2236 // If this is a memcpy/memmove, emit a GEP of the other element address. 2237 Value *OtherElt = nullptr; 2238 unsigned OtherEltAlign = MemAlignment; 2239 2240 if (OtherPtr) { 2241 Value *Idx[2] = { Zero, 2242 ConstantInt::get(Type::getInt32Ty(MI->getContext()), i) }; 2243 OtherElt = GetElementPtrInst::CreateInBounds(OtherPtr, Idx, 2244 OtherPtr->getName()+"."+Twine(i), 2245 MI); 2246 uint64_t EltOffset; 2247 PointerType *OtherPtrTy = cast<PointerType>(OtherPtr->getType()); 2248 Type *OtherTy = OtherPtrTy->getElementType(); 2249 if (StructType *ST = dyn_cast<StructType>(OtherTy)) { 2250 EltOffset = DL.getStructLayout(ST)->getElementOffset(i); 2251 } else { 2252 Type *EltTy = cast<SequentialType>(OtherTy)->getElementType(); 2253 EltOffset = DL.getTypeAllocSize(EltTy) * i; 2254 } 2255 2256 // The alignment of the other pointer is the guaranteed alignment of the 2257 // element, which is affected by both the known alignment of the whole 2258 // mem intrinsic and the alignment of the element. If the alignment of 2259 // the memcpy (f.e.) is 32 but the element is at a 4-byte offset, then the 2260 // known alignment is just 4 bytes. 2261 OtherEltAlign = (unsigned)MinAlign(OtherEltAlign, EltOffset); 2262 } 2263 2264 Value *EltPtr = NewElts[i]; 2265 Type *EltTy = cast<PointerType>(EltPtr->getType())->getElementType(); 2266 2267 // If we got down to a scalar, insert a load or store as appropriate. 2268 if (EltTy->isSingleValueType()) { 2269 if (isa<MemTransferInst>(MI)) { 2270 if (SROADest) { 2271 // From Other to Alloca. 2272 Value *Elt = new LoadInst(OtherElt, "tmp", false, OtherEltAlign, MI); 2273 new StoreInst(Elt, EltPtr, MI); 2274 } else { 2275 // From Alloca to Other. 2276 Value *Elt = new LoadInst(EltPtr, "tmp", MI); 2277 new StoreInst(Elt, OtherElt, false, OtherEltAlign, MI); 2278 } 2279 continue; 2280 } 2281 assert(isa<MemSetInst>(MI)); 2282 2283 // If the stored element is zero (common case), just store a null 2284 // constant. 2285 Constant *StoreVal; 2286 if (ConstantInt *CI = dyn_cast<ConstantInt>(MI->getArgOperand(1))) { 2287 if (CI->isZero()) { 2288 StoreVal = Constant::getNullValue(EltTy); // 0.0, null, 0, <0,0> 2289 } else { 2290 // If EltTy is a vector type, get the element type. 2291 Type *ValTy = EltTy->getScalarType(); 2292 2293 // Construct an integer with the right value. 2294 unsigned EltSize = DL.getTypeSizeInBits(ValTy); 2295 APInt OneVal(EltSize, CI->getZExtValue()); 2296 APInt TotalVal(OneVal); 2297 // Set each byte. 2298 for (unsigned i = 0; 8*i < EltSize; ++i) { 2299 TotalVal = TotalVal.shl(8); 2300 TotalVal |= OneVal; 2301 } 2302 2303 // Convert the integer value to the appropriate type. 2304 StoreVal = ConstantInt::get(CI->getContext(), TotalVal); 2305 if (ValTy->isPointerTy()) 2306 StoreVal = ConstantExpr::getIntToPtr(StoreVal, ValTy); 2307 else if (ValTy->isFloatingPointTy()) 2308 StoreVal = ConstantExpr::getBitCast(StoreVal, ValTy); 2309 assert(StoreVal->getType() == ValTy && "Type mismatch!"); 2310 2311 // If the requested value was a vector constant, create it. 2312 if (EltTy->isVectorTy()) { 2313 unsigned NumElts = cast<VectorType>(EltTy)->getNumElements(); 2314 StoreVal = ConstantVector::getSplat(NumElts, StoreVal); 2315 } 2316 } 2317 new StoreInst(StoreVal, EltPtr, MI); 2318 continue; 2319 } 2320 // Otherwise, if we're storing a byte variable, use a memset call for 2321 // this element. 2322 } 2323 2324 unsigned EltSize = DL.getTypeAllocSize(EltTy); 2325 if (!EltSize) 2326 continue; 2327 2328 IRBuilder<> Builder(MI); 2329 2330 // Finally, insert the meminst for this element. 2331 if (isa<MemSetInst>(MI)) { 2332 Builder.CreateMemSet(EltPtr, MI->getArgOperand(1), EltSize, 2333 MI->isVolatile()); 2334 } else { 2335 assert(isa<MemTransferInst>(MI)); 2336 Value *Dst = SROADest ? EltPtr : OtherElt; // Dest ptr 2337 Value *Src = SROADest ? OtherElt : EltPtr; // Src ptr 2338 2339 if (isa<MemCpyInst>(MI)) 2340 Builder.CreateMemCpy(Dst, Src, EltSize, OtherEltAlign,MI->isVolatile()); 2341 else 2342 Builder.CreateMemMove(Dst, Src, EltSize,OtherEltAlign,MI->isVolatile()); 2343 } 2344 } 2345 DeadInsts.push_back(MI); 2346} 2347 2348/// RewriteStoreUserOfWholeAlloca - We found a store of an integer that 2349/// overwrites the entire allocation. Extract out the pieces of the stored 2350/// integer and store them individually. 2351void 2352SROA::RewriteStoreUserOfWholeAlloca(StoreInst *SI, AllocaInst *AI, 2353 SmallVectorImpl<AllocaInst *> &NewElts) { 2354 // Extract each element out of the integer according to its structure offset 2355 // and store the element value to the individual alloca. 2356 Value *SrcVal = SI->getOperand(0); 2357 Type *AllocaEltTy = AI->getAllocatedType(); 2358 const DataLayout &DL = SI->getModule()->getDataLayout(); 2359 uint64_t AllocaSizeBits = DL.getTypeAllocSizeInBits(AllocaEltTy); 2360 2361 IRBuilder<> Builder(SI); 2362 2363 // Handle tail padding by extending the operand 2364 if (DL.getTypeSizeInBits(SrcVal->getType()) != AllocaSizeBits) 2365 SrcVal = Builder.CreateZExt(SrcVal, 2366 IntegerType::get(SI->getContext(), AllocaSizeBits)); 2367 2368 DEBUG(dbgs() << "PROMOTING STORE TO WHOLE ALLOCA: " << *AI << '\n' << *SI 2369 << '\n'); 2370 2371 // There are two forms here: AI could be an array or struct. Both cases 2372 // have different ways to compute the element offset. 2373 if (StructType *EltSTy = dyn_cast<StructType>(AllocaEltTy)) { 2374 const StructLayout *Layout = DL.getStructLayout(EltSTy); 2375 2376 for (unsigned i = 0, e = NewElts.size(); i != e; ++i) { 2377 // Get the number of bits to shift SrcVal to get the value. 2378 Type *FieldTy = EltSTy->getElementType(i); 2379 uint64_t Shift = Layout->getElementOffsetInBits(i); 2380 2381 if (DL.isBigEndian()) 2382 Shift = AllocaSizeBits - Shift - DL.getTypeAllocSizeInBits(FieldTy); 2383 2384 Value *EltVal = SrcVal; 2385 if (Shift) { 2386 Value *ShiftVal = ConstantInt::get(EltVal->getType(), Shift); 2387 EltVal = Builder.CreateLShr(EltVal, ShiftVal, "sroa.store.elt"); 2388 } 2389 2390 // Truncate down to an integer of the right size. 2391 uint64_t FieldSizeBits = DL.getTypeSizeInBits(FieldTy); 2392 2393 // Ignore zero sized fields like {}, they obviously contain no data. 2394 if (FieldSizeBits == 0) continue; 2395 2396 if (FieldSizeBits != AllocaSizeBits) 2397 EltVal = Builder.CreateTrunc(EltVal, 2398 IntegerType::get(SI->getContext(), FieldSizeBits)); 2399 Value *DestField = NewElts[i]; 2400 if (EltVal->getType() == FieldTy) { 2401 // Storing to an integer field of this size, just do it. 2402 } else if (FieldTy->isFloatingPointTy() || FieldTy->isVectorTy()) { 2403 // Bitcast to the right element type (for fp/vector values). 2404 EltVal = Builder.CreateBitCast(EltVal, FieldTy); 2405 } else { 2406 // Otherwise, bitcast the dest pointer (for aggregates). 2407 DestField = Builder.CreateBitCast(DestField, 2408 PointerType::getUnqual(EltVal->getType())); 2409 } 2410 new StoreInst(EltVal, DestField, SI); 2411 } 2412 2413 } else { 2414 ArrayType *ATy = cast<ArrayType>(AllocaEltTy); 2415 Type *ArrayEltTy = ATy->getElementType(); 2416 uint64_t ElementOffset = DL.getTypeAllocSizeInBits(ArrayEltTy); 2417 uint64_t ElementSizeBits = DL.getTypeSizeInBits(ArrayEltTy); 2418 2419 uint64_t Shift; 2420 2421 if (DL.isBigEndian()) 2422 Shift = AllocaSizeBits-ElementOffset; 2423 else 2424 Shift = 0; 2425 2426 for (unsigned i = 0, e = NewElts.size(); i != e; ++i) { 2427 // Ignore zero sized fields like {}, they obviously contain no data. 2428 if (ElementSizeBits == 0) continue; 2429 2430 Value *EltVal = SrcVal; 2431 if (Shift) { 2432 Value *ShiftVal = ConstantInt::get(EltVal->getType(), Shift); 2433 EltVal = Builder.CreateLShr(EltVal, ShiftVal, "sroa.store.elt"); 2434 } 2435 2436 // Truncate down to an integer of the right size. 2437 if (ElementSizeBits != AllocaSizeBits) 2438 EltVal = Builder.CreateTrunc(EltVal, 2439 IntegerType::get(SI->getContext(), 2440 ElementSizeBits)); 2441 Value *DestField = NewElts[i]; 2442 if (EltVal->getType() == ArrayEltTy) { 2443 // Storing to an integer field of this size, just do it. 2444 } else if (ArrayEltTy->isFloatingPointTy() || 2445 ArrayEltTy->isVectorTy()) { 2446 // Bitcast to the right element type (for fp/vector values). 2447 EltVal = Builder.CreateBitCast(EltVal, ArrayEltTy); 2448 } else { 2449 // Otherwise, bitcast the dest pointer (for aggregates). 2450 DestField = Builder.CreateBitCast(DestField, 2451 PointerType::getUnqual(EltVal->getType())); 2452 } 2453 new StoreInst(EltVal, DestField, SI); 2454 2455 if (DL.isBigEndian()) 2456 Shift -= ElementOffset; 2457 else 2458 Shift += ElementOffset; 2459 } 2460 } 2461 2462 DeadInsts.push_back(SI); 2463} 2464 2465/// RewriteLoadUserOfWholeAlloca - We found a load of the entire allocation to 2466/// an integer. Load the individual pieces to form the aggregate value. 2467void 2468SROA::RewriteLoadUserOfWholeAlloca(LoadInst *LI, AllocaInst *AI, 2469 SmallVectorImpl<AllocaInst *> &NewElts) { 2470 // Extract each element out of the NewElts according to its structure offset 2471 // and form the result value. 2472 Type *AllocaEltTy = AI->getAllocatedType(); 2473 const DataLayout &DL = LI->getModule()->getDataLayout(); 2474 uint64_t AllocaSizeBits = DL.getTypeAllocSizeInBits(AllocaEltTy); 2475 2476 DEBUG(dbgs() << "PROMOTING LOAD OF WHOLE ALLOCA: " << *AI << '\n' << *LI 2477 << '\n'); 2478 2479 // There are two forms here: AI could be an array or struct. Both cases 2480 // have different ways to compute the element offset. 2481 const StructLayout *Layout = nullptr; 2482 uint64_t ArrayEltBitOffset = 0; 2483 if (StructType *EltSTy = dyn_cast<StructType>(AllocaEltTy)) { 2484 Layout = DL.getStructLayout(EltSTy); 2485 } else { 2486 Type *ArrayEltTy = cast<ArrayType>(AllocaEltTy)->getElementType(); 2487 ArrayEltBitOffset = DL.getTypeAllocSizeInBits(ArrayEltTy); 2488 } 2489 2490 Value *ResultVal = 2491 Constant::getNullValue(IntegerType::get(LI->getContext(), AllocaSizeBits)); 2492 2493 for (unsigned i = 0, e = NewElts.size(); i != e; ++i) { 2494 // Load the value from the alloca. If the NewElt is an aggregate, cast 2495 // the pointer to an integer of the same size before doing the load. 2496 Value *SrcField = NewElts[i]; 2497 Type *FieldTy = 2498 cast<PointerType>(SrcField->getType())->getElementType(); 2499 uint64_t FieldSizeBits = DL.getTypeSizeInBits(FieldTy); 2500 2501 // Ignore zero sized fields like {}, they obviously contain no data. 2502 if (FieldSizeBits == 0) continue; 2503 2504 IntegerType *FieldIntTy = IntegerType::get(LI->getContext(), 2505 FieldSizeBits); 2506 if (!FieldTy->isIntegerTy() && !FieldTy->isFloatingPointTy() && 2507 !FieldTy->isVectorTy()) 2508 SrcField = new BitCastInst(SrcField, 2509 PointerType::getUnqual(FieldIntTy), 2510 "", LI); 2511 SrcField = new LoadInst(SrcField, "sroa.load.elt", LI); 2512 2513 // If SrcField is a fp or vector of the right size but that isn't an 2514 // integer type, bitcast to an integer so we can shift it. 2515 if (SrcField->getType() != FieldIntTy) 2516 SrcField = new BitCastInst(SrcField, FieldIntTy, "", LI); 2517 2518 // Zero extend the field to be the same size as the final alloca so that 2519 // we can shift and insert it. 2520 if (SrcField->getType() != ResultVal->getType()) 2521 SrcField = new ZExtInst(SrcField, ResultVal->getType(), "", LI); 2522 2523 // Determine the number of bits to shift SrcField. 2524 uint64_t Shift; 2525 if (Layout) // Struct case. 2526 Shift = Layout->getElementOffsetInBits(i); 2527 else // Array case. 2528 Shift = i*ArrayEltBitOffset; 2529 2530 if (DL.isBigEndian()) 2531 Shift = AllocaSizeBits-Shift-FieldIntTy->getBitWidth(); 2532 2533 if (Shift) { 2534 Value *ShiftVal = ConstantInt::get(SrcField->getType(), Shift); 2535 SrcField = BinaryOperator::CreateShl(SrcField, ShiftVal, "", LI); 2536 } 2537 2538 // Don't create an 'or x, 0' on the first iteration. 2539 if (!isa<Constant>(ResultVal) || 2540 !cast<Constant>(ResultVal)->isNullValue()) 2541 ResultVal = BinaryOperator::CreateOr(SrcField, ResultVal, "", LI); 2542 else 2543 ResultVal = SrcField; 2544 } 2545 2546 // Handle tail padding by truncating the result 2547 if (DL.getTypeSizeInBits(LI->getType()) != AllocaSizeBits) 2548 ResultVal = new TruncInst(ResultVal, LI->getType(), "", LI); 2549 2550 LI->replaceAllUsesWith(ResultVal); 2551 DeadInsts.push_back(LI); 2552} 2553 2554/// HasPadding - Return true if the specified type has any structure or 2555/// alignment padding in between the elements that would be split apart 2556/// by SROA; return false otherwise. 2557static bool HasPadding(Type *Ty, const DataLayout &DL) { 2558 if (ArrayType *ATy = dyn_cast<ArrayType>(Ty)) { 2559 Ty = ATy->getElementType(); 2560 return DL.getTypeSizeInBits(Ty) != DL.getTypeAllocSizeInBits(Ty); 2561 } 2562 2563 // SROA currently handles only Arrays and Structs. 2564 StructType *STy = cast<StructType>(Ty); 2565 const StructLayout *SL = DL.getStructLayout(STy); 2566 unsigned PrevFieldBitOffset = 0; 2567 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) { 2568 unsigned FieldBitOffset = SL->getElementOffsetInBits(i); 2569 2570 // Check to see if there is any padding between this element and the 2571 // previous one. 2572 if (i) { 2573 unsigned PrevFieldEnd = 2574 PrevFieldBitOffset+DL.getTypeSizeInBits(STy->getElementType(i-1)); 2575 if (PrevFieldEnd < FieldBitOffset) 2576 return true; 2577 } 2578 PrevFieldBitOffset = FieldBitOffset; 2579 } 2580 // Check for tail padding. 2581 if (unsigned EltCount = STy->getNumElements()) { 2582 unsigned PrevFieldEnd = PrevFieldBitOffset + 2583 DL.getTypeSizeInBits(STy->getElementType(EltCount-1)); 2584 if (PrevFieldEnd < SL->getSizeInBits()) 2585 return true; 2586 } 2587 return false; 2588} 2589 2590/// isSafeStructAllocaToScalarRepl - Check to see if the specified allocation of 2591/// an aggregate can be broken down into elements. Return 0 if not, 3 if safe, 2592/// or 1 if safe after canonicalization has been performed. 2593bool SROA::isSafeAllocaToScalarRepl(AllocaInst *AI) { 2594 // Loop over the use list of the alloca. We can only transform it if all of 2595 // the users are safe to transform. 2596 AllocaInfo Info(AI); 2597 2598 isSafeForScalarRepl(AI, 0, Info); 2599 if (Info.isUnsafe) { 2600 DEBUG(dbgs() << "Cannot transform: " << *AI << '\n'); 2601 return false; 2602 } 2603 2604 const DataLayout &DL = AI->getModule()->getDataLayout(); 2605 2606 // Okay, we know all the users are promotable. If the aggregate is a memcpy 2607 // source and destination, we have to be careful. In particular, the memcpy 2608 // could be moving around elements that live in structure padding of the LLVM 2609 // types, but may actually be used. In these cases, we refuse to promote the 2610 // struct. 2611 if (Info.isMemCpySrc && Info.isMemCpyDst && 2612 HasPadding(AI->getAllocatedType(), DL)) 2613 return false; 2614 2615 // If the alloca never has an access to just *part* of it, but is accessed 2616 // via loads and stores, then we should use ConvertToScalarInfo to promote 2617 // the alloca instead of promoting each piece at a time and inserting fission 2618 // and fusion code. 2619 if (!Info.hasSubelementAccess && Info.hasALoadOrStore) { 2620 // If the struct/array just has one element, use basic SRoA. 2621 if (StructType *ST = dyn_cast<StructType>(AI->getAllocatedType())) { 2622 if (ST->getNumElements() > 1) return false; 2623 } else { 2624 if (cast<ArrayType>(AI->getAllocatedType())->getNumElements() > 1) 2625 return false; 2626 } 2627 } 2628 2629 return true; 2630} 2631