Page MenuHomePhabricator
Differential D28044 Diff 88118 llvm/trunk/lib/Analysis/LoopAccessAnalysis.cpp

Changeset View

Standalone View

View Options

llvm/trunk/lib/Analysis/LoopAccessAnalysis.cpp

Show First 20 Lines • Show All 1245 Lines • ▼ Show 20 Line(s)1211bool MemoryDepChecker::couldPreventStoreLoadForward(uint64_t Distance,
1246 1246​
1247 if (MaxVFWithoutSLForwardIssues < MaxSafeDepDistBytes && 1247​ if (MaxVFWithoutSLForwardIssues < MaxSafeDepDistBytes &&
1248 MaxVFWithoutSLForwardIssues != 1248​ MaxVFWithoutSLForwardIssues !=
1249 VectorizerParams::MaxVectorWidth * TypeByteSize) 1249​ VectorizerParams::MaxVectorWidth * TypeByteSize)
1250 MaxSafeDepDistBytes = MaxVFWithoutSLForwardIssues; 1250​ MaxSafeDepDistBytes = MaxVFWithoutSLForwardIssues;
1251 return false; 1251​ return false;
1252} 1252​}
1253 1253​
1254​/// Given a non-constant (unknown) dependence-distance \p Dist between two
1255​/// memory accesses, that have the same stride whose absolute value is given
1256​/// in \p Stride, and that have the same type size \p TypeByteSize,
1257​/// in a loop whose takenCount is \p BackedgeTakenCount, check if it is
1258​/// possible to prove statically that the dependence distance is larger
1259​/// than the range that the accesses will travel through the execution of
1260​/// the loop. If so, return true; false otherwise. This is useful for
1261​/// example in loops such as the following (PR31098):
1262​/// for (i = 0; i < D; ++i) {
1263​/// = out[i];
1264​/// out[i+D] =
1265​/// }
1266​static bool isSafeDependenceDistance(const DataLayout &DL, ScalarEvolution &SE,
1267​ const SCEV &BackedgeTakenCount,
1268​ const SCEV &Dist, uint64_t Stride,
1269​ uint64_t TypeByteSize) {
1270​
1271​ // If we can prove that
1272​ // (**) |Dist| > BackedgeTakenCount * Step
1273​ // where Step is the absolute stride of the memory accesses in bytes,
1274​ // then there is no dependence.
1275​ //
1276​ // Ratioanle:
1277​ // We basically want to check if the absolute distance (|Dist/Step|)
1278​ // is >= the loop iteration count (or > BackedgeTakenCount).
1279​ // This is equivalent to the Strong SIV Test (Practical Dependence Testing,
1280​ // Section 4.2.1); Note, that for vectorization it is sufficient to prove
1281​ // that the dependence distance is >= VF; This is checked elsewhere.
1282​ // But in some cases we can prune unknown dependence distances early, and
1283​ // even before selecting the VF, and without a runtime test, by comparing
1284​ // the distance against the loop iteration count. Since the vectorized code
1285​ // will be executed only if LoopCount >= VF, proving distance >= LoopCount
1286​ // also guarantees that distance >= VF.
1287​ //
1288​ const uint64_t ByteStride = Stride * TypeByteSize;
1289​ const SCEV *Step = SE.getConstant(BackedgeTakenCount.getType(), ByteStride);
1290​ const SCEV *Product = SE.getMulExpr(&BackedgeTakenCount, Step);
1291​
1292​ const SCEV *CastedDist = &Dist;
1293​ const SCEV *CastedProduct = Product;
1294​ uint64_t DistTypeSize = DL.getTypeAllocSize(Dist.getType());
1295​ uint64_t ProductTypeSize = DL.getTypeAllocSize(Product->getType());
1296​
1297​ // The dependence distance can be positive/negative, so we sign extend Dist;
1298​ // The multiplication of the absolute stride in bytes and the
1299​ // backdgeTakenCount is non-negative, so we zero extend Product.
1300​ if (DistTypeSize > ProductTypeSize)
1301​ CastedProduct = SE.getZeroExtendExpr(Product, Dist.getType());
1302​ else
1303​ CastedDist = SE.getNoopOrSignExtend(&Dist, Product->getType());
1304​
1305​ // Is Dist - (BackedgeTakenCount * Step) > 0 ?
1306​ // (If so, then we have proven (**) because |Dist| >= Dist)
1307​ const SCEV *Minus = SE.getMinusSCEV(CastedDist, CastedProduct);
1308​ if (SE.isKnownPositive(Minus))
1309​ return true;
1310​
1311​ // Second try: Is -Dist - (BackedgeTakenCount * Step) > 0 ?
1312​ // (If so, then we have proven (**) because |Dist| >= -1*Dist)
1313​ const SCEV *NegDist = SE.getNegativeSCEV(CastedDist);
1314​ Minus = SE.getMinusSCEV(NegDist, CastedProduct);
1315​ if (SE.isKnownPositive(Minus))
1316​ return true;
1317​
1318​ return false;
1319​}
1320​
1254/// \brief Check the dependence for two accesses with the same stride \p Stride. 1321​/// \brief Check the dependence for two accesses with the same stride \p Stride.
1255/// \p Distance is the positive distance and \p TypeByteSize is type size in 1322​/// \p Distance is the positive distance and \p TypeByteSize is type size in
1256/// bytes. 1323​/// bytes.
1257/// 1324​///
1258/// \returns true if they are independent. 1325​/// \returns true if they are independent.
1259static bool areStridedAccessesIndependent(uint64_t Distance, uint64_t Stride, 1326​static bool areStridedAccessesIndependent(uint64_t Distance, uint64_t Stride,
1260 uint64_t TypeByteSize) { 1327​ uint64_t TypeByteSize) {
1261 assert(Stride > 1 && "The stride must be greater than 1"); 1328​ assert(Stride > 1 && "The stride must be greater than 1");
▲ Show 20 Lines • Show All 71 Lines • ▼ Show 20 Line(s)1358MemoryDepChecker::isDependent(const MemAccessInfo &A, unsigned AIdx,
1333 // Need accesses with constant stride. We don't want to vectorize 1400​ // Need accesses with constant stride. We don't want to vectorize
1334 // "A[B[i]] += ..." and similar code or pointer arithmetic that could wrap in 1401​ // "A[B[i]] += ..." and similar code or pointer arithmetic that could wrap in
1335 // the address space. 1402​ // the address space.
1336 if (!StrideAPtr || !StrideBPtr || StrideAPtr != StrideBPtr){ 1403​ if (!StrideAPtr || !StrideBPtr || StrideAPtr != StrideBPtr){
1337 DEBUG(dbgs() << "Pointer access with non-constant stride\n"); 1404​ DEBUG(dbgs() << "Pointer access with non-constant stride\n");
1338 return Dependence::Unknown; 1405​ return Dependence::Unknown;
1339 } 1406​ }
1340 1407​
1408​ Type *ATy = APtr->getType()->getPointerElementType();
1409​ Type *BTy = BPtr->getType()->getPointerElementType();
1410​ auto &DL = InnermostLoop->getHeader()->getModule()->getDataLayout();
1411​ uint64_t TypeByteSize = DL.getTypeAllocSize(ATy);
1412​ uint64_t Stride = std::abs(StrideAPtr);
1341 const SCEVConstant *C = dyn_cast<SCEVConstant>(Dist); 1413​ const SCEVConstant *C = dyn_cast<SCEVConstant>(Dist);
1342 if (!C) { 1414​ if (!C) {
1415​ if (TypeByteSize == DL.getTypeAllocSize(BTy) &&
1416​ isSafeDependenceDistance(DL, *(PSE.getSE()),
1417​ *(PSE.getBackedgeTakenCount()), *Dist, Stride,
1418​ TypeByteSize))
1419​ return Dependence::NoDep;
1420​
1343 DEBUG(dbgs() << "LAA: Dependence because of non-constant distance\n"); 1421​ DEBUG(dbgs() << "LAA: Dependence because of non-constant distance\n");
1344 ShouldRetryWithRuntimeCheck = true; 1422​ ShouldRetryWithRuntimeCheck = true;
1345 return Dependence::Unknown; 1423​ return Dependence::Unknown;
1346 } 1424​ }
1347 1425​
1348 Type *ATy = APtr->getType()->getPointerElementType(); ​
1349 Type *BTy = BPtr->getType()->getPointerElementType(); ​
1350 auto &DL = InnermostLoop->getHeader()->getModule()->getDataLayout(); ​
1351 uint64_t TypeByteSize = DL.getTypeAllocSize(ATy); ​
1352 ​
1353 const APInt &Val = C->getAPInt(); 1426​ const APInt &Val = C->getAPInt();
1354 int64_t Distance = Val.getSExtValue(); 1427​ int64_t Distance = Val.getSExtValue();
1355 uint64_t Stride = std::abs(StrideAPtr); ​
1356 1428​
1357 // Attempt to prove strided accesses independent. 1429​ // Attempt to prove strided accesses independent.
1358 if (std::abs(Distance) > 0 && Stride > 1 && ATy == BTy && 1430​ if (std::abs(Distance) > 0 && Stride > 1 && ATy == BTy &&
1359 areStridedAccessesIndependent(std::abs(Distance), Stride, TypeByteSize)) { 1431​ areStridedAccessesIndependent(std::abs(Distance), Stride, TypeByteSize)) {
1360 DEBUG(dbgs() << "LAA: Strided accesses are independent\n"); 1432​ DEBUG(dbgs() << "LAA: Strided accesses are independent\n");
1361 return Dependence::NoDep; 1433​ return Dependence::NoDep;
1362 } 1434​ }
1363 1435​
▲ Show 20 Lines • Show All 817 Lines • Show Last 20 Lines