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