1//===- LoopAccessAnalysis.cpp - Loop Access Analysis Implementation --------==// 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// The implementation for the loop memory dependence that was originally 11// developed for the loop vectorizer. 12// 13//===----------------------------------------------------------------------===// 14 15#include "llvm/Analysis/LoopAccessAnalysis.h" 16#include "llvm/Analysis/LoopInfo.h" 17#include "llvm/Analysis/ScalarEvolutionExpander.h" 18#include "llvm/Analysis/TargetLibraryInfo.h" 19#include "llvm/Analysis/ValueTracking.h" 20#include "llvm/IR/DiagnosticInfo.h" 21#include "llvm/IR/Dominators.h" 22#include "llvm/IR/IRBuilder.h" 23#include "llvm/Support/Debug.h" 24#include "llvm/Support/raw_ostream.h" 25#include "llvm/Transforms/Utils/VectorUtils.h" 26using namespace llvm; 27 28#define DEBUG_TYPE "loop-accesses" 29 30static cl::opt<unsigned, true> 31VectorizationFactor("force-vector-width", cl::Hidden, 32 cl::desc("Sets the SIMD width. Zero is autoselect."), 33 cl::location(VectorizerParams::VectorizationFactor)); 34unsigned VectorizerParams::VectorizationFactor; 35 36static cl::opt<unsigned, true> 37VectorizationInterleave("force-vector-interleave", cl::Hidden, 38 cl::desc("Sets the vectorization interleave count. " 39 "Zero is autoselect."), 40 cl::location( 41 VectorizerParams::VectorizationInterleave)); 42unsigned VectorizerParams::VectorizationInterleave; 43 44static cl::opt<unsigned, true> RuntimeMemoryCheckThreshold( 45 "runtime-memory-check-threshold", cl::Hidden, 46 cl::desc("When performing memory disambiguation checks at runtime do not " 47 "generate more than this number of comparisons (default = 8)."), 48 cl::location(VectorizerParams::RuntimeMemoryCheckThreshold), cl::init(8)); 49unsigned VectorizerParams::RuntimeMemoryCheckThreshold; 50 51/// Maximum SIMD width. 52const unsigned VectorizerParams::MaxVectorWidth = 64; 53 54/// \brief We collect interesting dependences up to this threshold. 55static cl::opt<unsigned> MaxInterestingDependence( 56 "max-interesting-dependences", cl::Hidden, 57 cl::desc("Maximum number of interesting dependences collected by " 58 "loop-access analysis (default = 100)"), 59 cl::init(100)); 60 61bool VectorizerParams::isInterleaveForced() { 62 return ::VectorizationInterleave.getNumOccurrences() > 0; 63} 64 65void LoopAccessReport::emitAnalysis(const LoopAccessReport &Message, 66 const Function *TheFunction, 67 const Loop *TheLoop, 68 const char *PassName) { 69 DebugLoc DL = TheLoop->getStartLoc(); 70 if (const Instruction *I = Message.getInstr()) 71 DL = I->getDebugLoc(); 72 emitOptimizationRemarkAnalysis(TheFunction->getContext(), PassName, 73 *TheFunction, DL, Message.str()); 74} 75 76Value *llvm::stripIntegerCast(Value *V) { 77 if (CastInst *CI = dyn_cast<CastInst>(V)) 78 if (CI->getOperand(0)->getType()->isIntegerTy()) 79 return CI->getOperand(0); 80 return V; 81} 82 83const SCEV *llvm::replaceSymbolicStrideSCEV(ScalarEvolution *SE, 84 const ValueToValueMap &PtrToStride, 85 Value *Ptr, Value *OrigPtr) { 86 87 const SCEV *OrigSCEV = SE->getSCEV(Ptr); 88 89 // If there is an entry in the map return the SCEV of the pointer with the 90 // symbolic stride replaced by one. 91 ValueToValueMap::const_iterator SI = 92 PtrToStride.find(OrigPtr ? OrigPtr : Ptr); 93 if (SI != PtrToStride.end()) { 94 Value *StrideVal = SI->second; 95 96 // Strip casts. 97 StrideVal = stripIntegerCast(StrideVal); 98 99 // Replace symbolic stride by one. 100 Value *One = ConstantInt::get(StrideVal->getType(), 1); 101 ValueToValueMap RewriteMap; 102 RewriteMap[StrideVal] = One; 103 104 const SCEV *ByOne = 105 SCEVParameterRewriter::rewrite(OrigSCEV, *SE, RewriteMap, true); 106 DEBUG(dbgs() << "LAA: Replacing SCEV: " << *OrigSCEV << " by: " << *ByOne 107 << "\n"); 108 return ByOne; 109 } 110 111 // Otherwise, just return the SCEV of the original pointer. 112 return SE->getSCEV(Ptr); 113} 114 115void LoopAccessInfo::RuntimePointerCheck::insert( 116 ScalarEvolution *SE, Loop *Lp, Value *Ptr, bool WritePtr, unsigned DepSetId, 117 unsigned ASId, const ValueToValueMap &Strides) { 118 // Get the stride replaced scev. 119 const SCEV *Sc = replaceSymbolicStrideSCEV(SE, Strides, Ptr); 120 const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(Sc); 121 assert(AR && "Invalid addrec expression"); 122 const SCEV *Ex = SE->getBackedgeTakenCount(Lp); 123 const SCEV *ScEnd = AR->evaluateAtIteration(Ex, *SE); 124 Pointers.push_back(Ptr); 125 Starts.push_back(AR->getStart()); 126 Ends.push_back(ScEnd); 127 IsWritePtr.push_back(WritePtr); 128 DependencySetId.push_back(DepSetId); 129 AliasSetId.push_back(ASId); 130} 131 132bool LoopAccessInfo::RuntimePointerCheck::needsChecking( 133 unsigned I, unsigned J, const SmallVectorImpl<int> *PtrPartition) const { 134 // No need to check if two readonly pointers intersect. 135 if (!IsWritePtr[I] && !IsWritePtr[J]) 136 return false; 137 138 // Only need to check pointers between two different dependency sets. 139 if (DependencySetId[I] == DependencySetId[J]) 140 return false; 141 142 // Only need to check pointers in the same alias set. 143 if (AliasSetId[I] != AliasSetId[J]) 144 return false; 145 146 // If PtrPartition is set omit checks between pointers of the same partition. 147 // Partition number -1 means that the pointer is used in multiple partitions. 148 // In this case we can't omit the check. 149 if (PtrPartition && (*PtrPartition)[I] != -1 && 150 (*PtrPartition)[I] == (*PtrPartition)[J]) 151 return false; 152 153 return true; 154} 155 156void LoopAccessInfo::RuntimePointerCheck::print( 157 raw_ostream &OS, unsigned Depth, 158 const SmallVectorImpl<int> *PtrPartition) const { 159 unsigned NumPointers = Pointers.size(); 160 if (NumPointers == 0) 161 return; 162 163 OS.indent(Depth) << "Run-time memory checks:\n"; 164 unsigned N = 0; 165 for (unsigned I = 0; I < NumPointers; ++I) 166 for (unsigned J = I + 1; J < NumPointers; ++J) 167 if (needsChecking(I, J, PtrPartition)) { 168 OS.indent(Depth) << N++ << ":\n"; 169 OS.indent(Depth + 2) << *Pointers[I]; 170 if (PtrPartition) 171 OS << " (Partition: " << (*PtrPartition)[I] << ")"; 172 OS << "\n"; 173 OS.indent(Depth + 2) << *Pointers[J]; 174 if (PtrPartition) 175 OS << " (Partition: " << (*PtrPartition)[J] << ")"; 176 OS << "\n"; 177 } 178} 179 180bool LoopAccessInfo::RuntimePointerCheck::needsAnyChecking( 181 const SmallVectorImpl<int> *PtrPartition) const { 182 unsigned NumPointers = Pointers.size(); 183 184 for (unsigned I = 0; I < NumPointers; ++I) 185 for (unsigned J = I + 1; J < NumPointers; ++J) 186 if (needsChecking(I, J, PtrPartition)) 187 return true; 188 return false; 189} 190 191namespace { 192/// \brief Analyses memory accesses in a loop. 193/// 194/// Checks whether run time pointer checks are needed and builds sets for data 195/// dependence checking. 196class AccessAnalysis { 197public: 198 /// \brief Read or write access location. 199 typedef PointerIntPair<Value *, 1, bool> MemAccessInfo; 200 typedef SmallPtrSet<MemAccessInfo, 8> MemAccessInfoSet; 201 202 AccessAnalysis(const DataLayout &Dl, AliasAnalysis *AA, 203 MemoryDepChecker::DepCandidates &DA) 204 : DL(Dl), AST(*AA), DepCands(DA), IsRTCheckNeeded(false) {} 205 206 /// \brief Register a load and whether it is only read from. 207 void addLoad(AliasAnalysis::Location &Loc, bool IsReadOnly) { 208 Value *Ptr = const_cast<Value*>(Loc.Ptr); 209 AST.add(Ptr, AliasAnalysis::UnknownSize, Loc.AATags); 210 Accesses.insert(MemAccessInfo(Ptr, false)); 211 if (IsReadOnly) 212 ReadOnlyPtr.insert(Ptr); 213 } 214 215 /// \brief Register a store. 216 void addStore(AliasAnalysis::Location &Loc) { 217 Value *Ptr = const_cast<Value*>(Loc.Ptr); 218 AST.add(Ptr, AliasAnalysis::UnknownSize, Loc.AATags); 219 Accesses.insert(MemAccessInfo(Ptr, true)); 220 } 221 222 /// \brief Check whether we can check the pointers at runtime for 223 /// non-intersection. 224 bool canCheckPtrAtRT(LoopAccessInfo::RuntimePointerCheck &RtCheck, 225 unsigned &NumComparisons, ScalarEvolution *SE, 226 Loop *TheLoop, const ValueToValueMap &Strides, 227 bool ShouldCheckStride = false); 228 229 /// \brief Goes over all memory accesses, checks whether a RT check is needed 230 /// and builds sets of dependent accesses. 231 void buildDependenceSets() { 232 processMemAccesses(); 233 } 234 235 bool isRTCheckNeeded() { return IsRTCheckNeeded; } 236 237 bool isDependencyCheckNeeded() { return !CheckDeps.empty(); } 238 void resetDepChecks() { CheckDeps.clear(); } 239 240 MemAccessInfoSet &getDependenciesToCheck() { return CheckDeps; } 241 242private: 243 typedef SetVector<MemAccessInfo> PtrAccessSet; 244 245 /// \brief Go over all memory access and check whether runtime pointer checks 246 /// are needed /// and build sets of dependency check candidates. 247 void processMemAccesses(); 248 249 /// Set of all accesses. 250 PtrAccessSet Accesses; 251 252 const DataLayout &DL; 253 254 /// Set of accesses that need a further dependence check. 255 MemAccessInfoSet CheckDeps; 256 257 /// Set of pointers that are read only. 258 SmallPtrSet<Value*, 16> ReadOnlyPtr; 259 260 /// An alias set tracker to partition the access set by underlying object and 261 //intrinsic property (such as TBAA metadata). 262 AliasSetTracker AST; 263 264 /// Sets of potentially dependent accesses - members of one set share an 265 /// underlying pointer. The set "CheckDeps" identfies which sets really need a 266 /// dependence check. 267 MemoryDepChecker::DepCandidates &DepCands; 268 269 bool IsRTCheckNeeded; 270}; 271 272} // end anonymous namespace 273 274/// \brief Check whether a pointer can participate in a runtime bounds check. 275static bool hasComputableBounds(ScalarEvolution *SE, 276 const ValueToValueMap &Strides, Value *Ptr) { 277 const SCEV *PtrScev = replaceSymbolicStrideSCEV(SE, Strides, Ptr); 278 const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(PtrScev); 279 if (!AR) 280 return false; 281 282 return AR->isAffine(); 283} 284 285/// \brief Check the stride of the pointer and ensure that it does not wrap in 286/// the address space. 287static int isStridedPtr(ScalarEvolution *SE, Value *Ptr, const Loop *Lp, 288 const ValueToValueMap &StridesMap); 289 290bool AccessAnalysis::canCheckPtrAtRT( 291 LoopAccessInfo::RuntimePointerCheck &RtCheck, unsigned &NumComparisons, 292 ScalarEvolution *SE, Loop *TheLoop, const ValueToValueMap &StridesMap, 293 bool ShouldCheckStride) { 294 // Find pointers with computable bounds. We are going to use this information 295 // to place a runtime bound check. 296 bool CanDoRT = true; 297 298 bool IsDepCheckNeeded = isDependencyCheckNeeded(); 299 NumComparisons = 0; 300 301 // We assign a consecutive id to access from different alias sets. 302 // Accesses between different groups doesn't need to be checked. 303 unsigned ASId = 1; 304 for (auto &AS : AST) { 305 unsigned NumReadPtrChecks = 0; 306 unsigned NumWritePtrChecks = 0; 307 308 // We assign consecutive id to access from different dependence sets. 309 // Accesses within the same set don't need a runtime check. 310 unsigned RunningDepId = 1; 311 DenseMap<Value *, unsigned> DepSetId; 312 313 for (auto A : AS) { 314 Value *Ptr = A.getValue(); 315 bool IsWrite = Accesses.count(MemAccessInfo(Ptr, true)); 316 MemAccessInfo Access(Ptr, IsWrite); 317 318 if (IsWrite) 319 ++NumWritePtrChecks; 320 else 321 ++NumReadPtrChecks; 322 323 if (hasComputableBounds(SE, StridesMap, Ptr) && 324 // When we run after a failing dependency check we have to make sure 325 // we don't have wrapping pointers. 326 (!ShouldCheckStride || 327 isStridedPtr(SE, Ptr, TheLoop, StridesMap) == 1)) { 328 // The id of the dependence set. 329 unsigned DepId; 330 331 if (IsDepCheckNeeded) { 332 Value *Leader = DepCands.getLeaderValue(Access).getPointer(); 333 unsigned &LeaderId = DepSetId[Leader]; 334 if (!LeaderId) 335 LeaderId = RunningDepId++; 336 DepId = LeaderId; 337 } else 338 // Each access has its own dependence set. 339 DepId = RunningDepId++; 340 341 RtCheck.insert(SE, TheLoop, Ptr, IsWrite, DepId, ASId, StridesMap); 342 343 DEBUG(dbgs() << "LAA: Found a runtime check ptr:" << *Ptr << '\n'); 344 } else { 345 CanDoRT = false; 346 } 347 } 348 349 if (IsDepCheckNeeded && CanDoRT && RunningDepId == 2) 350 NumComparisons += 0; // Only one dependence set. 351 else { 352 NumComparisons += (NumWritePtrChecks * (NumReadPtrChecks + 353 NumWritePtrChecks - 1)); 354 } 355 356 ++ASId; 357 } 358 359 // If the pointers that we would use for the bounds comparison have different 360 // address spaces, assume the values aren't directly comparable, so we can't 361 // use them for the runtime check. We also have to assume they could 362 // overlap. In the future there should be metadata for whether address spaces 363 // are disjoint. 364 unsigned NumPointers = RtCheck.Pointers.size(); 365 for (unsigned i = 0; i < NumPointers; ++i) { 366 for (unsigned j = i + 1; j < NumPointers; ++j) { 367 // Only need to check pointers between two different dependency sets. 368 if (RtCheck.DependencySetId[i] == RtCheck.DependencySetId[j]) 369 continue; 370 // Only need to check pointers in the same alias set. 371 if (RtCheck.AliasSetId[i] != RtCheck.AliasSetId[j]) 372 continue; 373 374 Value *PtrI = RtCheck.Pointers[i]; 375 Value *PtrJ = RtCheck.Pointers[j]; 376 377 unsigned ASi = PtrI->getType()->getPointerAddressSpace(); 378 unsigned ASj = PtrJ->getType()->getPointerAddressSpace(); 379 if (ASi != ASj) { 380 DEBUG(dbgs() << "LAA: Runtime check would require comparison between" 381 " different address spaces\n"); 382 return false; 383 } 384 } 385 } 386 387 return CanDoRT; 388} 389 390void AccessAnalysis::processMemAccesses() { 391 // We process the set twice: first we process read-write pointers, last we 392 // process read-only pointers. This allows us to skip dependence tests for 393 // read-only pointers. 394 395 DEBUG(dbgs() << "LAA: Processing memory accesses...\n"); 396 DEBUG(dbgs() << " AST: "; AST.dump()); 397 DEBUG(dbgs() << "LAA: Accesses(" << Accesses.size() << "):\n"); 398 DEBUG({ 399 for (auto A : Accesses) 400 dbgs() << "\t" << *A.getPointer() << " (" << 401 (A.getInt() ? "write" : (ReadOnlyPtr.count(A.getPointer()) ? 402 "read-only" : "read")) << ")\n"; 403 }); 404 405 // The AliasSetTracker has nicely partitioned our pointers by metadata 406 // compatibility and potential for underlying-object overlap. As a result, we 407 // only need to check for potential pointer dependencies within each alias 408 // set. 409 for (auto &AS : AST) { 410 // Note that both the alias-set tracker and the alias sets themselves used 411 // linked lists internally and so the iteration order here is deterministic 412 // (matching the original instruction order within each set). 413 414 bool SetHasWrite = false; 415 416 // Map of pointers to last access encountered. 417 typedef DenseMap<Value*, MemAccessInfo> UnderlyingObjToAccessMap; 418 UnderlyingObjToAccessMap ObjToLastAccess; 419 420 // Set of access to check after all writes have been processed. 421 PtrAccessSet DeferredAccesses; 422 423 // Iterate over each alias set twice, once to process read/write pointers, 424 // and then to process read-only pointers. 425 for (int SetIteration = 0; SetIteration < 2; ++SetIteration) { 426 bool UseDeferred = SetIteration > 0; 427 PtrAccessSet &S = UseDeferred ? DeferredAccesses : Accesses; 428 429 for (auto AV : AS) { 430 Value *Ptr = AV.getValue(); 431 432 // For a single memory access in AliasSetTracker, Accesses may contain 433 // both read and write, and they both need to be handled for CheckDeps. 434 for (auto AC : S) { 435 if (AC.getPointer() != Ptr) 436 continue; 437 438 bool IsWrite = AC.getInt(); 439 440 // If we're using the deferred access set, then it contains only 441 // reads. 442 bool IsReadOnlyPtr = ReadOnlyPtr.count(Ptr) && !IsWrite; 443 if (UseDeferred && !IsReadOnlyPtr) 444 continue; 445 // Otherwise, the pointer must be in the PtrAccessSet, either as a 446 // read or a write. 447 assert(((IsReadOnlyPtr && UseDeferred) || IsWrite || 448 S.count(MemAccessInfo(Ptr, false))) && 449 "Alias-set pointer not in the access set?"); 450 451 MemAccessInfo Access(Ptr, IsWrite); 452 DepCands.insert(Access); 453 454 // Memorize read-only pointers for later processing and skip them in 455 // the first round (they need to be checked after we have seen all 456 // write pointers). Note: we also mark pointer that are not 457 // consecutive as "read-only" pointers (so that we check 458 // "a[b[i]] +="). Hence, we need the second check for "!IsWrite". 459 if (!UseDeferred && IsReadOnlyPtr) { 460 DeferredAccesses.insert(Access); 461 continue; 462 } 463 464 // If this is a write - check other reads and writes for conflicts. If 465 // this is a read only check other writes for conflicts (but only if 466 // there is no other write to the ptr - this is an optimization to 467 // catch "a[i] = a[i] + " without having to do a dependence check). 468 if ((IsWrite || IsReadOnlyPtr) && SetHasWrite) { 469 CheckDeps.insert(Access); 470 IsRTCheckNeeded = true; 471 } 472 473 if (IsWrite) 474 SetHasWrite = true; 475 476 // Create sets of pointers connected by a shared alias set and 477 // underlying object. 478 typedef SmallVector<Value *, 16> ValueVector; 479 ValueVector TempObjects; 480 GetUnderlyingObjects(Ptr, TempObjects, DL); 481 for (Value *UnderlyingObj : TempObjects) { 482 UnderlyingObjToAccessMap::iterator Prev = 483 ObjToLastAccess.find(UnderlyingObj); 484 if (Prev != ObjToLastAccess.end()) 485 DepCands.unionSets(Access, Prev->second); 486 487 ObjToLastAccess[UnderlyingObj] = Access; 488 } 489 } 490 } 491 } 492 } 493} 494 495static bool isInBoundsGep(Value *Ptr) { 496 if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Ptr)) 497 return GEP->isInBounds(); 498 return false; 499} 500 501/// \brief Check whether the access through \p Ptr has a constant stride. 502static int isStridedPtr(ScalarEvolution *SE, Value *Ptr, const Loop *Lp, 503 const ValueToValueMap &StridesMap) { 504 const Type *Ty = Ptr->getType(); 505 assert(Ty->isPointerTy() && "Unexpected non-ptr"); 506 507 // Make sure that the pointer does not point to aggregate types. 508 const PointerType *PtrTy = cast<PointerType>(Ty); 509 if (PtrTy->getElementType()->isAggregateType()) { 510 DEBUG(dbgs() << "LAA: Bad stride - Not a pointer to a scalar type" 511 << *Ptr << "\n"); 512 return 0; 513 } 514 515 const SCEV *PtrScev = replaceSymbolicStrideSCEV(SE, StridesMap, Ptr); 516 517 const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(PtrScev); 518 if (!AR) { 519 DEBUG(dbgs() << "LAA: Bad stride - Not an AddRecExpr pointer " 520 << *Ptr << " SCEV: " << *PtrScev << "\n"); 521 return 0; 522 } 523 524 // The accesss function must stride over the innermost loop. 525 if (Lp != AR->getLoop()) { 526 DEBUG(dbgs() << "LAA: Bad stride - Not striding over innermost loop " << 527 *Ptr << " SCEV: " << *PtrScev << "\n"); 528 } 529 530 // The address calculation must not wrap. Otherwise, a dependence could be 531 // inverted. 532 // An inbounds getelementptr that is a AddRec with a unit stride 533 // cannot wrap per definition. The unit stride requirement is checked later. 534 // An getelementptr without an inbounds attribute and unit stride would have 535 // to access the pointer value "0" which is undefined behavior in address 536 // space 0, therefore we can also vectorize this case. 537 bool IsInBoundsGEP = isInBoundsGep(Ptr); 538 bool IsNoWrapAddRec = AR->getNoWrapFlags(SCEV::NoWrapMask); 539 bool IsInAddressSpaceZero = PtrTy->getAddressSpace() == 0; 540 if (!IsNoWrapAddRec && !IsInBoundsGEP && !IsInAddressSpaceZero) { 541 DEBUG(dbgs() << "LAA: Bad stride - Pointer may wrap in the address space " 542 << *Ptr << " SCEV: " << *PtrScev << "\n"); 543 return 0; 544 } 545 546 // Check the step is constant. 547 const SCEV *Step = AR->getStepRecurrence(*SE); 548 549 // Calculate the pointer stride and check if it is consecutive. 550 const SCEVConstant *C = dyn_cast<SCEVConstant>(Step); 551 if (!C) { 552 DEBUG(dbgs() << "LAA: Bad stride - Not a constant strided " << *Ptr << 553 " SCEV: " << *PtrScev << "\n"); 554 return 0; 555 } 556 557 auto &DL = Lp->getHeader()->getModule()->getDataLayout(); 558 int64_t Size = DL.getTypeAllocSize(PtrTy->getElementType()); 559 const APInt &APStepVal = C->getValue()->getValue(); 560 561 // Huge step value - give up. 562 if (APStepVal.getBitWidth() > 64) 563 return 0; 564 565 int64_t StepVal = APStepVal.getSExtValue(); 566 567 // Strided access. 568 int64_t Stride = StepVal / Size; 569 int64_t Rem = StepVal % Size; 570 if (Rem) 571 return 0; 572 573 // If the SCEV could wrap but we have an inbounds gep with a unit stride we 574 // know we can't "wrap around the address space". In case of address space 575 // zero we know that this won't happen without triggering undefined behavior. 576 if (!IsNoWrapAddRec && (IsInBoundsGEP || IsInAddressSpaceZero) && 577 Stride != 1 && Stride != -1) 578 return 0; 579 580 return Stride; 581} 582 583bool MemoryDepChecker::Dependence::isSafeForVectorization(DepType Type) { 584 switch (Type) { 585 case NoDep: 586 case Forward: 587 case BackwardVectorizable: 588 return true; 589 590 case Unknown: 591 case ForwardButPreventsForwarding: 592 case Backward: 593 case BackwardVectorizableButPreventsForwarding: 594 return false; 595 } 596 llvm_unreachable("unexpected DepType!"); 597} 598 599bool MemoryDepChecker::Dependence::isInterestingDependence(DepType Type) { 600 switch (Type) { 601 case NoDep: 602 case Forward: 603 return false; 604 605 case BackwardVectorizable: 606 case Unknown: 607 case ForwardButPreventsForwarding: 608 case Backward: 609 case BackwardVectorizableButPreventsForwarding: 610 return true; 611 } 612 llvm_unreachable("unexpected DepType!"); 613} 614 615bool MemoryDepChecker::Dependence::isPossiblyBackward() const { 616 switch (Type) { 617 case NoDep: 618 case Forward: 619 case ForwardButPreventsForwarding: 620 return false; 621 622 case Unknown: 623 case BackwardVectorizable: 624 case Backward: 625 case BackwardVectorizableButPreventsForwarding: 626 return true; 627 } 628 llvm_unreachable("unexpected DepType!"); 629} 630 631bool MemoryDepChecker::couldPreventStoreLoadForward(unsigned Distance, 632 unsigned TypeByteSize) { 633 // If loads occur at a distance that is not a multiple of a feasible vector 634 // factor store-load forwarding does not take place. 635 // Positive dependences might cause troubles because vectorizing them might 636 // prevent store-load forwarding making vectorized code run a lot slower. 637 // a[i] = a[i-3] ^ a[i-8]; 638 // The stores to a[i:i+1] don't align with the stores to a[i-3:i-2] and 639 // hence on your typical architecture store-load forwarding does not take 640 // place. Vectorizing in such cases does not make sense. 641 // Store-load forwarding distance. 642 const unsigned NumCyclesForStoreLoadThroughMemory = 8*TypeByteSize; 643 // Maximum vector factor. 644 unsigned MaxVFWithoutSLForwardIssues = 645 VectorizerParams::MaxVectorWidth * TypeByteSize; 646 if(MaxSafeDepDistBytes < MaxVFWithoutSLForwardIssues) 647 MaxVFWithoutSLForwardIssues = MaxSafeDepDistBytes; 648 649 for (unsigned vf = 2*TypeByteSize; vf <= MaxVFWithoutSLForwardIssues; 650 vf *= 2) { 651 if (Distance % vf && Distance / vf < NumCyclesForStoreLoadThroughMemory) { 652 MaxVFWithoutSLForwardIssues = (vf >>=1); 653 break; 654 } 655 } 656 657 if (MaxVFWithoutSLForwardIssues< 2*TypeByteSize) { 658 DEBUG(dbgs() << "LAA: Distance " << Distance << 659 " that could cause a store-load forwarding conflict\n"); 660 return true; 661 } 662 663 if (MaxVFWithoutSLForwardIssues < MaxSafeDepDistBytes && 664 MaxVFWithoutSLForwardIssues != 665 VectorizerParams::MaxVectorWidth * TypeByteSize) 666 MaxSafeDepDistBytes = MaxVFWithoutSLForwardIssues; 667 return false; 668} 669 670MemoryDepChecker::Dependence::DepType 671MemoryDepChecker::isDependent(const MemAccessInfo &A, unsigned AIdx, 672 const MemAccessInfo &B, unsigned BIdx, 673 const ValueToValueMap &Strides) { 674 assert (AIdx < BIdx && "Must pass arguments in program order"); 675 676 Value *APtr = A.getPointer(); 677 Value *BPtr = B.getPointer(); 678 bool AIsWrite = A.getInt(); 679 bool BIsWrite = B.getInt(); 680 681 // Two reads are independent. 682 if (!AIsWrite && !BIsWrite) 683 return Dependence::NoDep; 684 685 // We cannot check pointers in different address spaces. 686 if (APtr->getType()->getPointerAddressSpace() != 687 BPtr->getType()->getPointerAddressSpace()) 688 return Dependence::Unknown; 689 690 const SCEV *AScev = replaceSymbolicStrideSCEV(SE, Strides, APtr); 691 const SCEV *BScev = replaceSymbolicStrideSCEV(SE, Strides, BPtr); 692 693 int StrideAPtr = isStridedPtr(SE, APtr, InnermostLoop, Strides); 694 int StrideBPtr = isStridedPtr(SE, BPtr, InnermostLoop, Strides); 695 696 const SCEV *Src = AScev; 697 const SCEV *Sink = BScev; 698 699 // If the induction step is negative we have to invert source and sink of the 700 // dependence. 701 if (StrideAPtr < 0) { 702 //Src = BScev; 703 //Sink = AScev; 704 std::swap(APtr, BPtr); 705 std::swap(Src, Sink); 706 std::swap(AIsWrite, BIsWrite); 707 std::swap(AIdx, BIdx); 708 std::swap(StrideAPtr, StrideBPtr); 709 } 710 711 const SCEV *Dist = SE->getMinusSCEV(Sink, Src); 712 713 DEBUG(dbgs() << "LAA: Src Scev: " << *Src << "Sink Scev: " << *Sink 714 << "(Induction step: " << StrideAPtr << ")\n"); 715 DEBUG(dbgs() << "LAA: Distance for " << *InstMap[AIdx] << " to " 716 << *InstMap[BIdx] << ": " << *Dist << "\n"); 717 718 // Need consecutive accesses. We don't want to vectorize 719 // "A[B[i]] += ..." and similar code or pointer arithmetic that could wrap in 720 // the address space. 721 if (!StrideAPtr || !StrideBPtr || StrideAPtr != StrideBPtr){ 722 DEBUG(dbgs() << "Non-consecutive pointer access\n"); 723 return Dependence::Unknown; 724 } 725 726 const SCEVConstant *C = dyn_cast<SCEVConstant>(Dist); 727 if (!C) { 728 DEBUG(dbgs() << "LAA: Dependence because of non-constant distance\n"); 729 ShouldRetryWithRuntimeCheck = true; 730 return Dependence::Unknown; 731 } 732 733 Type *ATy = APtr->getType()->getPointerElementType(); 734 Type *BTy = BPtr->getType()->getPointerElementType(); 735 auto &DL = InnermostLoop->getHeader()->getModule()->getDataLayout(); 736 unsigned TypeByteSize = DL.getTypeAllocSize(ATy); 737 738 // Negative distances are not plausible dependencies. 739 const APInt &Val = C->getValue()->getValue(); 740 if (Val.isNegative()) { 741 bool IsTrueDataDependence = (AIsWrite && !BIsWrite); 742 if (IsTrueDataDependence && 743 (couldPreventStoreLoadForward(Val.abs().getZExtValue(), TypeByteSize) || 744 ATy != BTy)) 745 return Dependence::ForwardButPreventsForwarding; 746 747 DEBUG(dbgs() << "LAA: Dependence is negative: NoDep\n"); 748 return Dependence::Forward; 749 } 750 751 // Write to the same location with the same size. 752 // Could be improved to assert type sizes are the same (i32 == float, etc). 753 if (Val == 0) { 754 if (ATy == BTy) 755 return Dependence::NoDep; 756 DEBUG(dbgs() << "LAA: Zero dependence difference but different types\n"); 757 return Dependence::Unknown; 758 } 759 760 assert(Val.isStrictlyPositive() && "Expect a positive value"); 761 762 if (ATy != BTy) { 763 DEBUG(dbgs() << 764 "LAA: ReadWrite-Write positive dependency with different types\n"); 765 return Dependence::Unknown; 766 } 767 768 unsigned Distance = (unsigned) Val.getZExtValue(); 769 770 // Bail out early if passed-in parameters make vectorization not feasible. 771 unsigned ForcedFactor = (VectorizerParams::VectorizationFactor ? 772 VectorizerParams::VectorizationFactor : 1); 773 unsigned ForcedUnroll = (VectorizerParams::VectorizationInterleave ? 774 VectorizerParams::VectorizationInterleave : 1); 775 776 // The distance must be bigger than the size needed for a vectorized version 777 // of the operation and the size of the vectorized operation must not be 778 // bigger than the currrent maximum size. 779 if (Distance < 2*TypeByteSize || 780 2*TypeByteSize > MaxSafeDepDistBytes || 781 Distance < TypeByteSize * ForcedUnroll * ForcedFactor) { 782 DEBUG(dbgs() << "LAA: Failure because of Positive distance " 783 << Val.getSExtValue() << '\n'); 784 return Dependence::Backward; 785 } 786 787 // Positive distance bigger than max vectorization factor. 788 MaxSafeDepDistBytes = Distance < MaxSafeDepDistBytes ? 789 Distance : MaxSafeDepDistBytes; 790 791 bool IsTrueDataDependence = (!AIsWrite && BIsWrite); 792 if (IsTrueDataDependence && 793 couldPreventStoreLoadForward(Distance, TypeByteSize)) 794 return Dependence::BackwardVectorizableButPreventsForwarding; 795 796 DEBUG(dbgs() << "LAA: Positive distance " << Val.getSExtValue() << 797 " with max VF = " << MaxSafeDepDistBytes / TypeByteSize << '\n'); 798 799 return Dependence::BackwardVectorizable; 800} 801 802bool MemoryDepChecker::areDepsSafe(DepCandidates &AccessSets, 803 MemAccessInfoSet &CheckDeps, 804 const ValueToValueMap &Strides) { 805 806 MaxSafeDepDistBytes = -1U; 807 while (!CheckDeps.empty()) { 808 MemAccessInfo CurAccess = *CheckDeps.begin(); 809 810 // Get the relevant memory access set. 811 EquivalenceClasses<MemAccessInfo>::iterator I = 812 AccessSets.findValue(AccessSets.getLeaderValue(CurAccess)); 813 814 // Check accesses within this set. 815 EquivalenceClasses<MemAccessInfo>::member_iterator AI, AE; 816 AI = AccessSets.member_begin(I), AE = AccessSets.member_end(); 817 818 // Check every access pair. 819 while (AI != AE) { 820 CheckDeps.erase(*AI); 821 EquivalenceClasses<MemAccessInfo>::member_iterator OI = std::next(AI); 822 while (OI != AE) { 823 // Check every accessing instruction pair in program order. 824 for (std::vector<unsigned>::iterator I1 = Accesses[*AI].begin(), 825 I1E = Accesses[*AI].end(); I1 != I1E; ++I1) 826 for (std::vector<unsigned>::iterator I2 = Accesses[*OI].begin(), 827 I2E = Accesses[*OI].end(); I2 != I2E; ++I2) { 828 auto A = std::make_pair(&*AI, *I1); 829 auto B = std::make_pair(&*OI, *I2); 830 831 assert(*I1 != *I2); 832 if (*I1 > *I2) 833 std::swap(A, B); 834 835 Dependence::DepType Type = 836 isDependent(*A.first, A.second, *B.first, B.second, Strides); 837 SafeForVectorization &= Dependence::isSafeForVectorization(Type); 838 839 // Gather dependences unless we accumulated MaxInterestingDependence 840 // dependences. In that case return as soon as we find the first 841 // unsafe dependence. This puts a limit on this quadratic 842 // algorithm. 843 if (RecordInterestingDependences) { 844 if (Dependence::isInterestingDependence(Type)) 845 InterestingDependences.push_back( 846 Dependence(A.second, B.second, Type)); 847 848 if (InterestingDependences.size() >= MaxInterestingDependence) { 849 RecordInterestingDependences = false; 850 InterestingDependences.clear(); 851 DEBUG(dbgs() << "Too many dependences, stopped recording\n"); 852 } 853 } 854 if (!RecordInterestingDependences && !SafeForVectorization) 855 return false; 856 } 857 ++OI; 858 } 859 AI++; 860 } 861 } 862 863 DEBUG(dbgs() << "Total Interesting Dependences: " 864 << InterestingDependences.size() << "\n"); 865 return SafeForVectorization; 866} 867 868SmallVector<Instruction *, 4> 869MemoryDepChecker::getInstructionsForAccess(Value *Ptr, bool isWrite) const { 870 MemAccessInfo Access(Ptr, isWrite); 871 auto &IndexVector = Accesses.find(Access)->second; 872 873 SmallVector<Instruction *, 4> Insts; 874 std::transform(IndexVector.begin(), IndexVector.end(), 875 std::back_inserter(Insts), 876 [&](unsigned Idx) { return this->InstMap[Idx]; }); 877 return Insts; 878} 879 880const char *MemoryDepChecker::Dependence::DepName[] = { 881 "NoDep", "Unknown", "Forward", "ForwardButPreventsForwarding", "Backward", 882 "BackwardVectorizable", "BackwardVectorizableButPreventsForwarding"}; 883 884void MemoryDepChecker::Dependence::print( 885 raw_ostream &OS, unsigned Depth, 886 const SmallVectorImpl<Instruction *> &Instrs) const { 887 OS.indent(Depth) << DepName[Type] << ":\n"; 888 OS.indent(Depth + 2) << *Instrs[Source] << " -> \n"; 889 OS.indent(Depth + 2) << *Instrs[Destination] << "\n"; 890} 891 892bool LoopAccessInfo::canAnalyzeLoop() { 893 // We can only analyze innermost loops. 894 if (!TheLoop->empty()) { 895 emitAnalysis(LoopAccessReport() << "loop is not the innermost loop"); 896 return false; 897 } 898 899 // We must have a single backedge. 900 if (TheLoop->getNumBackEdges() != 1) { 901 emitAnalysis( 902 LoopAccessReport() << 903 "loop control flow is not understood by analyzer"); 904 return false; 905 } 906 907 // We must have a single exiting block. 908 if (!TheLoop->getExitingBlock()) { 909 emitAnalysis( 910 LoopAccessReport() << 911 "loop control flow is not understood by analyzer"); 912 return false; 913 } 914 915 // We only handle bottom-tested loops, i.e. loop in which the condition is 916 // checked at the end of each iteration. With that we can assume that all 917 // instructions in the loop are executed the same number of times. 918 if (TheLoop->getExitingBlock() != TheLoop->getLoopLatch()) { 919 emitAnalysis( 920 LoopAccessReport() << 921 "loop control flow is not understood by analyzer"); 922 return false; 923 } 924 925 // We need to have a loop header. 926 DEBUG(dbgs() << "LAA: Found a loop: " << 927 TheLoop->getHeader()->getName() << '\n'); 928 929 // ScalarEvolution needs to be able to find the exit count. 930 const SCEV *ExitCount = SE->getBackedgeTakenCount(TheLoop); 931 if (ExitCount == SE->getCouldNotCompute()) { 932 emitAnalysis(LoopAccessReport() << 933 "could not determine number of loop iterations"); 934 DEBUG(dbgs() << "LAA: SCEV could not compute the loop exit count.\n"); 935 return false; 936 } 937 938 return true; 939} 940 941void LoopAccessInfo::analyzeLoop(const ValueToValueMap &Strides) { 942 943 typedef SmallVector<Value*, 16> ValueVector; 944 typedef SmallPtrSet<Value*, 16> ValueSet; 945 946 // Holds the Load and Store *instructions*. 947 ValueVector Loads; 948 ValueVector Stores; 949 950 // Holds all the different accesses in the loop. 951 unsigned NumReads = 0; 952 unsigned NumReadWrites = 0; 953 954 PtrRtCheck.Pointers.clear(); 955 PtrRtCheck.Need = false; 956 957 const bool IsAnnotatedParallel = TheLoop->isAnnotatedParallel(); 958 959 // For each block. 960 for (Loop::block_iterator bb = TheLoop->block_begin(), 961 be = TheLoop->block_end(); bb != be; ++bb) { 962 963 // Scan the BB and collect legal loads and stores. 964 for (BasicBlock::iterator it = (*bb)->begin(), e = (*bb)->end(); it != e; 965 ++it) { 966 967 // If this is a load, save it. If this instruction can read from memory 968 // but is not a load, then we quit. Notice that we don't handle function 969 // calls that read or write. 970 if (it->mayReadFromMemory()) { 971 // Many math library functions read the rounding mode. We will only 972 // vectorize a loop if it contains known function calls that don't set 973 // the flag. Therefore, it is safe to ignore this read from memory. 974 CallInst *Call = dyn_cast<CallInst>(it); 975 if (Call && getIntrinsicIDForCall(Call, TLI)) 976 continue; 977 978 // If the function has an explicit vectorized counterpart, we can safely 979 // assume that it can be vectorized. 980 if (Call && !Call->isNoBuiltin() && Call->getCalledFunction() && 981 TLI->isFunctionVectorizable(Call->getCalledFunction()->getName())) 982 continue; 983 984 LoadInst *Ld = dyn_cast<LoadInst>(it); 985 if (!Ld || (!Ld->isSimple() && !IsAnnotatedParallel)) { 986 emitAnalysis(LoopAccessReport(Ld) 987 << "read with atomic ordering or volatile read"); 988 DEBUG(dbgs() << "LAA: Found a non-simple load.\n"); 989 CanVecMem = false; 990 return; 991 } 992 NumLoads++; 993 Loads.push_back(Ld); 994 DepChecker.addAccess(Ld); 995 continue; 996 } 997 998 // Save 'store' instructions. Abort if other instructions write to memory. 999 if (it->mayWriteToMemory()) { 1000 StoreInst *St = dyn_cast<StoreInst>(it); 1001 if (!St) { 1002 emitAnalysis(LoopAccessReport(it) << 1003 "instruction cannot be vectorized"); 1004 CanVecMem = false; 1005 return; 1006 } 1007 if (!St->isSimple() && !IsAnnotatedParallel) { 1008 emitAnalysis(LoopAccessReport(St) 1009 << "write with atomic ordering or volatile write"); 1010 DEBUG(dbgs() << "LAA: Found a non-simple store.\n"); 1011 CanVecMem = false; 1012 return; 1013 } 1014 NumStores++; 1015 Stores.push_back(St); 1016 DepChecker.addAccess(St); 1017 } 1018 } // Next instr. 1019 } // Next block. 1020 1021 // Now we have two lists that hold the loads and the stores. 1022 // Next, we find the pointers that they use. 1023 1024 // Check if we see any stores. If there are no stores, then we don't 1025 // care if the pointers are *restrict*. 1026 if (!Stores.size()) { 1027 DEBUG(dbgs() << "LAA: Found a read-only loop!\n"); 1028 CanVecMem = true; 1029 return; 1030 } 1031 1032 MemoryDepChecker::DepCandidates DependentAccesses; 1033 AccessAnalysis Accesses(TheLoop->getHeader()->getModule()->getDataLayout(), 1034 AA, DependentAccesses); 1035 1036 // Holds the analyzed pointers. We don't want to call GetUnderlyingObjects 1037 // multiple times on the same object. If the ptr is accessed twice, once 1038 // for read and once for write, it will only appear once (on the write 1039 // list). This is okay, since we are going to check for conflicts between 1040 // writes and between reads and writes, but not between reads and reads. 1041 ValueSet Seen; 1042 1043 ValueVector::iterator I, IE; 1044 for (I = Stores.begin(), IE = Stores.end(); I != IE; ++I) { 1045 StoreInst *ST = cast<StoreInst>(*I); 1046 Value* Ptr = ST->getPointerOperand(); 1047 // Check for store to loop invariant address. 1048 StoreToLoopInvariantAddress |= isUniform(Ptr); 1049 // If we did *not* see this pointer before, insert it to the read-write 1050 // list. At this phase it is only a 'write' list. 1051 if (Seen.insert(Ptr).second) { 1052 ++NumReadWrites; 1053 1054 AliasAnalysis::Location Loc = AA->getLocation(ST); 1055 // The TBAA metadata could have a control dependency on the predication 1056 // condition, so we cannot rely on it when determining whether or not we 1057 // need runtime pointer checks. 1058 if (blockNeedsPredication(ST->getParent(), TheLoop, DT)) 1059 Loc.AATags.TBAA = nullptr; 1060 1061 Accesses.addStore(Loc); 1062 } 1063 } 1064 1065 if (IsAnnotatedParallel) { 1066 DEBUG(dbgs() 1067 << "LAA: A loop annotated parallel, ignore memory dependency " 1068 << "checks.\n"); 1069 CanVecMem = true; 1070 return; 1071 } 1072 1073 for (I = Loads.begin(), IE = Loads.end(); I != IE; ++I) { 1074 LoadInst *LD = cast<LoadInst>(*I); 1075 Value* Ptr = LD->getPointerOperand(); 1076 // If we did *not* see this pointer before, insert it to the 1077 // read list. If we *did* see it before, then it is already in 1078 // the read-write list. This allows us to vectorize expressions 1079 // such as A[i] += x; Because the address of A[i] is a read-write 1080 // pointer. This only works if the index of A[i] is consecutive. 1081 // If the address of i is unknown (for example A[B[i]]) then we may 1082 // read a few words, modify, and write a few words, and some of the 1083 // words may be written to the same address. 1084 bool IsReadOnlyPtr = false; 1085 if (Seen.insert(Ptr).second || !isStridedPtr(SE, Ptr, TheLoop, Strides)) { 1086 ++NumReads; 1087 IsReadOnlyPtr = true; 1088 } 1089 1090 AliasAnalysis::Location Loc = AA->getLocation(LD); 1091 // The TBAA metadata could have a control dependency on the predication 1092 // condition, so we cannot rely on it when determining whether or not we 1093 // need runtime pointer checks. 1094 if (blockNeedsPredication(LD->getParent(), TheLoop, DT)) 1095 Loc.AATags.TBAA = nullptr; 1096 1097 Accesses.addLoad(Loc, IsReadOnlyPtr); 1098 } 1099 1100 // If we write (or read-write) to a single destination and there are no 1101 // other reads in this loop then is it safe to vectorize. 1102 if (NumReadWrites == 1 && NumReads == 0) { 1103 DEBUG(dbgs() << "LAA: Found a write-only loop!\n"); 1104 CanVecMem = true; 1105 return; 1106 } 1107 1108 // Build dependence sets and check whether we need a runtime pointer bounds 1109 // check. 1110 Accesses.buildDependenceSets(); 1111 bool NeedRTCheck = Accesses.isRTCheckNeeded(); 1112 1113 // Find pointers with computable bounds. We are going to use this information 1114 // to place a runtime bound check. 1115 bool CanDoRT = false; 1116 if (NeedRTCheck) 1117 CanDoRT = Accesses.canCheckPtrAtRT(PtrRtCheck, NumComparisons, SE, TheLoop, 1118 Strides); 1119 1120 DEBUG(dbgs() << "LAA: We need to do " << NumComparisons << 1121 " pointer comparisons.\n"); 1122 1123 // If we only have one set of dependences to check pointers among we don't 1124 // need a runtime check. 1125 if (NumComparisons == 0 && NeedRTCheck) 1126 NeedRTCheck = false; 1127 1128 // Check that we found the bounds for the pointer. 1129 if (CanDoRT) 1130 DEBUG(dbgs() << "LAA: We can perform a memory runtime check if needed.\n"); 1131 else if (NeedRTCheck) { 1132 emitAnalysis(LoopAccessReport() << "cannot identify array bounds"); 1133 DEBUG(dbgs() << "LAA: We can't vectorize because we can't find " << 1134 "the array bounds.\n"); 1135 PtrRtCheck.reset(); 1136 CanVecMem = false; 1137 return; 1138 } 1139 1140 PtrRtCheck.Need = NeedRTCheck; 1141 1142 CanVecMem = true; 1143 if (Accesses.isDependencyCheckNeeded()) { 1144 DEBUG(dbgs() << "LAA: Checking memory dependencies\n"); 1145 CanVecMem = DepChecker.areDepsSafe( 1146 DependentAccesses, Accesses.getDependenciesToCheck(), Strides); 1147 MaxSafeDepDistBytes = DepChecker.getMaxSafeDepDistBytes(); 1148 1149 if (!CanVecMem && DepChecker.shouldRetryWithRuntimeCheck()) { 1150 DEBUG(dbgs() << "LAA: Retrying with memory checks\n"); 1151 NeedRTCheck = true; 1152 1153 // Clear the dependency checks. We assume they are not needed. 1154 Accesses.resetDepChecks(); 1155 1156 PtrRtCheck.reset(); 1157 PtrRtCheck.Need = true; 1158 1159 CanDoRT = Accesses.canCheckPtrAtRT(PtrRtCheck, NumComparisons, SE, 1160 TheLoop, Strides, true); 1161 // Check that we found the bounds for the pointer. 1162 if (!CanDoRT && NumComparisons > 0) { 1163 emitAnalysis(LoopAccessReport() 1164 << "cannot check memory dependencies at runtime"); 1165 DEBUG(dbgs() << "LAA: Can't vectorize with memory checks\n"); 1166 PtrRtCheck.reset(); 1167 CanVecMem = false; 1168 return; 1169 } 1170 1171 CanVecMem = true; 1172 } 1173 } 1174 1175 if (CanVecMem) 1176 DEBUG(dbgs() << "LAA: No unsafe dependent memory operations in loop. We" 1177 << (NeedRTCheck ? "" : " don't") 1178 << " need a runtime memory check.\n"); 1179 else { 1180 emitAnalysis(LoopAccessReport() << 1181 "unsafe dependent memory operations in loop"); 1182 DEBUG(dbgs() << "LAA: unsafe dependent memory operations in loop\n"); 1183 } 1184} 1185 1186bool LoopAccessInfo::blockNeedsPredication(BasicBlock *BB, Loop *TheLoop, 1187 DominatorTree *DT) { 1188 assert(TheLoop->contains(BB) && "Unknown block used"); 1189 1190 // Blocks that do not dominate the latch need predication. 1191 BasicBlock* Latch = TheLoop->getLoopLatch(); 1192 return !DT->dominates(BB, Latch); 1193} 1194 1195void LoopAccessInfo::emitAnalysis(LoopAccessReport &Message) { 1196 assert(!Report && "Multiple reports generated"); 1197 Report = Message; 1198} 1199 1200bool LoopAccessInfo::isUniform(Value *V) const { 1201 return (SE->isLoopInvariant(SE->getSCEV(V), TheLoop)); 1202} 1203 1204// FIXME: this function is currently a duplicate of the one in 1205// LoopVectorize.cpp. 1206static Instruction *getFirstInst(Instruction *FirstInst, Value *V, 1207 Instruction *Loc) { 1208 if (FirstInst) 1209 return FirstInst; 1210 if (Instruction *I = dyn_cast<Instruction>(V)) 1211 return I->getParent() == Loc->getParent() ? I : nullptr; 1212 return nullptr; 1213} 1214 1215std::pair<Instruction *, Instruction *> LoopAccessInfo::addRuntimeCheck( 1216 Instruction *Loc, const SmallVectorImpl<int> *PtrPartition) const { 1217 if (!PtrRtCheck.Need) 1218 return std::make_pair(nullptr, nullptr); 1219 1220 unsigned NumPointers = PtrRtCheck.Pointers.size(); 1221 SmallVector<TrackingVH<Value> , 2> Starts; 1222 SmallVector<TrackingVH<Value> , 2> Ends; 1223 1224 LLVMContext &Ctx = Loc->getContext(); 1225 SCEVExpander Exp(*SE, DL, "induction"); 1226 Instruction *FirstInst = nullptr; 1227 1228 for (unsigned i = 0; i < NumPointers; ++i) { 1229 Value *Ptr = PtrRtCheck.Pointers[i]; 1230 const SCEV *Sc = SE->getSCEV(Ptr); 1231 1232 if (SE->isLoopInvariant(Sc, TheLoop)) { 1233 DEBUG(dbgs() << "LAA: Adding RT check for a loop invariant ptr:" << 1234 *Ptr <<"\n"); 1235 Starts.push_back(Ptr); 1236 Ends.push_back(Ptr); 1237 } else { 1238 DEBUG(dbgs() << "LAA: Adding RT check for range:" << *Ptr << '\n'); 1239 unsigned AS = Ptr->getType()->getPointerAddressSpace(); 1240 1241 // Use this type for pointer arithmetic. 1242 Type *PtrArithTy = Type::getInt8PtrTy(Ctx, AS); 1243 1244 Value *Start = Exp.expandCodeFor(PtrRtCheck.Starts[i], PtrArithTy, Loc); 1245 Value *End = Exp.expandCodeFor(PtrRtCheck.Ends[i], PtrArithTy, Loc); 1246 Starts.push_back(Start); 1247 Ends.push_back(End); 1248 } 1249 } 1250 1251 IRBuilder<> ChkBuilder(Loc); 1252 // Our instructions might fold to a constant. 1253 Value *MemoryRuntimeCheck = nullptr; 1254 for (unsigned i = 0; i < NumPointers; ++i) { 1255 for (unsigned j = i+1; j < NumPointers; ++j) { 1256 if (!PtrRtCheck.needsChecking(i, j, PtrPartition)) 1257 continue; 1258 1259 unsigned AS0 = Starts[i]->getType()->getPointerAddressSpace(); 1260 unsigned AS1 = Starts[j]->getType()->getPointerAddressSpace(); 1261 1262 assert((AS0 == Ends[j]->getType()->getPointerAddressSpace()) && 1263 (AS1 == Ends[i]->getType()->getPointerAddressSpace()) && 1264 "Trying to bounds check pointers with different address spaces"); 1265 1266 Type *PtrArithTy0 = Type::getInt8PtrTy(Ctx, AS0); 1267 Type *PtrArithTy1 = Type::getInt8PtrTy(Ctx, AS1); 1268 1269 Value *Start0 = ChkBuilder.CreateBitCast(Starts[i], PtrArithTy0, "bc"); 1270 Value *Start1 = ChkBuilder.CreateBitCast(Starts[j], PtrArithTy1, "bc"); 1271 Value *End0 = ChkBuilder.CreateBitCast(Ends[i], PtrArithTy1, "bc"); 1272 Value *End1 = ChkBuilder.CreateBitCast(Ends[j], PtrArithTy0, "bc"); 1273 1274 Value *Cmp0 = ChkBuilder.CreateICmpULE(Start0, End1, "bound0"); 1275 FirstInst = getFirstInst(FirstInst, Cmp0, Loc); 1276 Value *Cmp1 = ChkBuilder.CreateICmpULE(Start1, End0, "bound1"); 1277 FirstInst = getFirstInst(FirstInst, Cmp1, Loc); 1278 Value *IsConflict = ChkBuilder.CreateAnd(Cmp0, Cmp1, "found.conflict"); 1279 FirstInst = getFirstInst(FirstInst, IsConflict, Loc); 1280 if (MemoryRuntimeCheck) { 1281 IsConflict = ChkBuilder.CreateOr(MemoryRuntimeCheck, IsConflict, 1282 "conflict.rdx"); 1283 FirstInst = getFirstInst(FirstInst, IsConflict, Loc); 1284 } 1285 MemoryRuntimeCheck = IsConflict; 1286 } 1287 } 1288 1289 if (!MemoryRuntimeCheck) 1290 return std::make_pair(nullptr, nullptr); 1291 1292 // We have to do this trickery because the IRBuilder might fold the check to a 1293 // constant expression in which case there is no Instruction anchored in a 1294 // the block. 1295 Instruction *Check = BinaryOperator::CreateAnd(MemoryRuntimeCheck, 1296 ConstantInt::getTrue(Ctx)); 1297 ChkBuilder.Insert(Check, "memcheck.conflict"); 1298 FirstInst = getFirstInst(FirstInst, Check, Loc); 1299 return std::make_pair(FirstInst, Check); 1300} 1301 1302LoopAccessInfo::LoopAccessInfo(Loop *L, ScalarEvolution *SE, 1303 const DataLayout &DL, 1304 const TargetLibraryInfo *TLI, AliasAnalysis *AA, 1305 DominatorTree *DT, 1306 const ValueToValueMap &Strides) 1307 : DepChecker(SE, L), NumComparisons(0), TheLoop(L), SE(SE), DL(DL), 1308 TLI(TLI), AA(AA), DT(DT), NumLoads(0), NumStores(0), 1309 MaxSafeDepDistBytes(-1U), CanVecMem(false), 1310 StoreToLoopInvariantAddress(false) { 1311 if (canAnalyzeLoop()) 1312 analyzeLoop(Strides); 1313} 1314 1315void LoopAccessInfo::print(raw_ostream &OS, unsigned Depth) const { 1316 if (CanVecMem) { 1317 if (PtrRtCheck.Need) 1318 OS.indent(Depth) << "Memory dependences are safe with run-time checks\n"; 1319 else 1320 OS.indent(Depth) << "Memory dependences are safe\n"; 1321 } 1322 1323 OS.indent(Depth) << "Store to invariant address was " 1324 << (StoreToLoopInvariantAddress ? "" : "not ") 1325 << "found in loop.\n"; 1326 1327 if (Report) 1328 OS.indent(Depth) << "Report: " << Report->str() << "\n"; 1329 1330 if (auto *InterestingDependences = DepChecker.getInterestingDependences()) { 1331 OS.indent(Depth) << "Interesting Dependences:\n"; 1332 for (auto &Dep : *InterestingDependences) { 1333 Dep.print(OS, Depth + 2, DepChecker.getMemoryInstructions()); 1334 OS << "\n"; 1335 } 1336 } else 1337 OS.indent(Depth) << "Too many interesting dependences, not recorded\n"; 1338 1339 // List the pair of accesses need run-time checks to prove independence. 1340 PtrRtCheck.print(OS, Depth); 1341 OS << "\n"; 1342} 1343 1344const LoopAccessInfo & 1345LoopAccessAnalysis::getInfo(Loop *L, const ValueToValueMap &Strides) { 1346 auto &LAI = LoopAccessInfoMap[L]; 1347 1348#ifndef NDEBUG 1349 assert((!LAI || LAI->NumSymbolicStrides == Strides.size()) && 1350 "Symbolic strides changed for loop"); 1351#endif 1352 1353 if (!LAI) { 1354 const DataLayout &DL = L->getHeader()->getModule()->getDataLayout(); 1355 LAI = llvm::make_unique<LoopAccessInfo>(L, SE, DL, TLI, AA, DT, Strides); 1356#ifndef NDEBUG 1357 LAI->NumSymbolicStrides = Strides.size(); 1358#endif 1359 } 1360 return *LAI.get(); 1361} 1362 1363void LoopAccessAnalysis::print(raw_ostream &OS, const Module *M) const { 1364 LoopAccessAnalysis &LAA = *const_cast<LoopAccessAnalysis *>(this); 1365 1366 LoopInfo *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo(); 1367 ValueToValueMap NoSymbolicStrides; 1368 1369 for (Loop *TopLevelLoop : *LI) 1370 for (Loop *L : depth_first(TopLevelLoop)) { 1371 OS.indent(2) << L->getHeader()->getName() << ":\n"; 1372 auto &LAI = LAA.getInfo(L, NoSymbolicStrides); 1373 LAI.print(OS, 4); 1374 } 1375} 1376 1377bool LoopAccessAnalysis::runOnFunction(Function &F) { 1378 SE = &getAnalysis<ScalarEvolution>(); 1379 auto *TLIP = getAnalysisIfAvailable<TargetLibraryInfoWrapperPass>(); 1380 TLI = TLIP ? &TLIP->getTLI() : nullptr; 1381 AA = &getAnalysis<AliasAnalysis>(); 1382 DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree(); 1383 1384 return false; 1385} 1386 1387void LoopAccessAnalysis::getAnalysisUsage(AnalysisUsage &AU) const { 1388 AU.addRequired<ScalarEvolution>(); 1389 AU.addRequired<AliasAnalysis>(); 1390 AU.addRequired<DominatorTreeWrapperPass>(); 1391 AU.addRequired<LoopInfoWrapperPass>(); 1392 1393 AU.setPreservesAll(); 1394} 1395 1396char LoopAccessAnalysis::ID = 0; 1397static const char laa_name[] = "Loop Access Analysis"; 1398#define LAA_NAME "loop-accesses" 1399 1400INITIALIZE_PASS_BEGIN(LoopAccessAnalysis, LAA_NAME, laa_name, false, true) 1401INITIALIZE_AG_DEPENDENCY(AliasAnalysis) 1402INITIALIZE_PASS_DEPENDENCY(ScalarEvolution) 1403INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) 1404INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass) 1405INITIALIZE_PASS_END(LoopAccessAnalysis, LAA_NAME, laa_name, false, true) 1406 1407namespace llvm { 1408 Pass *createLAAPass() { 1409 return new LoopAccessAnalysis(); 1410 } 1411} 1412