From b45ae5601b2ed631ce7a60dcf6ebe7413bd64abd Mon Sep 17 00:00:00 2001 From: Tobias Grosser Date: Sat, 26 Nov 2016 07:37:46 +0000 Subject: [PATCH] [ScopDetect] Expand statistics of the detected scops We now collect: Number of total loops Number of loops in scops Number of scops Number of scops with maximal loop depth 1 Number of scops with maximal loop depth 2 Number of scops with maximal loop depth 3 Number of scops with maximal loop depth 4 Number of scops with maximal loop depth 5 Number of scops with maximal loop depth 6 and larger Number of loops in scops (profitable scops only) Number of scops (profitable scops only) Number of scops with maximal loop depth 1 (profitable scops only) Number of scops with maximal loop depth 2 (profitable scops only) Number of scops with maximal loop depth 3 (profitable scops only) Number of scops with maximal loop depth 4 (profitable scops only) Number of scops with maximal loop depth 5 (profitable scops only) Number of scops with maximal loop depth 6 and larger (profitable scops only) These statistics are certainly completely accurate as we might drop scops when building up their polyhedral representation, but they should give a good indication of the number of scops we detect. llvm-svn: 287973 --- polly/include/polly/ScopDetection.h | 32 +++++++-- polly/lib/Analysis/ScopDetection.cpp | 122 ++++++++++++++++++++++++++++------- polly/test/ScopInfo/Alias-0.ll | 2 +- polly/test/ScopInfo/Alias-1.ll | 2 +- polly/test/ScopInfo/Alias-2.ll | 2 +- polly/test/ScopInfo/Alias-3.ll | 2 +- polly/test/ScopInfo/Alias-4.ll | 2 +- 7 files changed, 129 insertions(+), 35 deletions(-) diff --git a/polly/include/polly/ScopDetection.h b/polly/include/polly/ScopDetection.h index c55017e..ef6c95e 100644 --- a/polly/include/polly/ScopDetection.h +++ b/polly/include/polly/ScopDetection.h @@ -189,6 +189,12 @@ public: } }; + /// Helper data structure to collect statistics about loop counts. + struct LoopStats { + int NumLoops; + int MaxDepth; + }; + private: //===--------------------------------------------------------------------===// ScopDetection(const ScopDetection &) = delete; @@ -211,9 +217,7 @@ private: void removeCachedResults(const Region &R); /// Remove cached results for the children of @p R recursively. - /// - /// @returns The number of regions erased regions. - unsigned removeCachedResultsRecursively(const Region &R); + void removeCachedResultsRecursively(const Region &R); /// Add the region @p AR as over approximated sub-region in @p Context. /// @@ -464,10 +468,28 @@ private: /// @return True if the loop is valid in the region. bool isValidLoop(Loop *L, DetectionContext &Context) const; - /// Count the number of beneficial loops in @p R. + /// Count the number of loops and the maximal loop depth in @p L. + /// + /// @param L The loop to check. + /// @param SE The scalar evolution analysis. + /// @param MinProfitableTrips The minimum number of trip counts from which + /// a loop is assumed to be profitable and + /// consequently is counted. + /// returns A tuple of number of loops and their maximal depth. + ScopDetection::LoopStats + countBeneficialSubLoops(Loop *L, ScalarEvolution &SE, + unsigned MinProfitableTrips) const; + + /// Count the number of loops and the maximal loop depth in @p R. /// /// @param R The region to check - int countBeneficialLoops(Region *R) const; + /// @param SE The scalar evolution analysis. + /// @param MinProfitableTrips The minimum number of trip counts from which + /// a loop is assumed to be profitable and + /// consequently is counted. + /// returns A tuple of number of loops and their maximal depth. + ScopDetection::LoopStats + countBeneficialLoops(Region *R, unsigned MinProfitableTrips) const; /// Check if the function @p F is marked as invalid. /// diff --git a/polly/lib/Analysis/ScopDetection.cpp b/polly/lib/Analysis/ScopDetection.cpp index 70fa3aa..438d80a 100644 --- a/polly/lib/Analysis/ScopDetection.cpp +++ b/polly/lib/Analysis/ScopDetection.cpp @@ -188,7 +188,31 @@ StringRef polly::PollySkipFnAttr = "polly.skip.fn"; //===----------------------------------------------------------------------===// // Statistics. -STATISTIC(ValidRegion, "Number of regions that a valid part of Scop"); +STATISTIC(NumScopRegions, "Number of scops"); +STATISTIC(NumLoopsInScop, "Number of loops in scops"); +STATISTIC(NumScopsDepthOne, "Number of scops with maximal loop depth 1"); +STATISTIC(NumScopsDepthTwo, "Number of scops with maximal loop depth 2"); +STATISTIC(NumScopsDepthThree, "Number of scops with maximal loop depth 3"); +STATISTIC(NumScopsDepthFour, "Number of scops with maximal loop depth 4"); +STATISTIC(NumScopsDepthFive, "Number of scops with maximal loop depth 5"); +STATISTIC(NumScopsDepthLarger, + "Number of scops with maximal loop depth 6 and larger"); +STATISTIC(NumProfScopRegions, "Number of scops (profitable scops only)"); +STATISTIC(NumLoopsInProfScop, + "Number of loops in scops (profitable scops only)"); +STATISTIC(NumLoopsOverall, "Number of total loops"); +STATISTIC(NumProfScopsDepthOne, + "Number of scops with maximal loop depth 1 (profitable scops only)"); +STATISTIC(NumProfScopsDepthTwo, + "Number of scops with maximal loop depth 2 (profitable scops only)"); +STATISTIC(NumProfScopsDepthThree, + "Number of scops with maximal loop depth 3 (profitable scops only)"); +STATISTIC(NumProfScopsDepthFour, + "Number of scops with maximal loop depth 4 (profitable scops only)"); +STATISTIC(NumProfScopsDepthFive, + "Number of scops with maximal loop depth 5 (profitable scops only)"); +STATISTIC(NumProfScopsDepthLarger, "Number of scops with maximal loop depth 6 " + "and larger (profitable scops only)"); class DiagnosticScopFound : public DiagnosticInfo { private: @@ -1042,24 +1066,33 @@ bool ScopDetection::isValidLoop(Loop *L, DetectionContext &Context) const { } /// Return the number of loops in @p L (incl. @p L) that have a trip -/// count that is not known to be less than MIN_LOOP_TRIP_COUNT. -static int countBeneficialSubLoops(Loop *L, ScalarEvolution &SE) { +/// count that is not known to be less than @MinProfitableTrips. +ScopDetection::LoopStats +ScopDetection::countBeneficialSubLoops(Loop *L, ScalarEvolution &SE, + unsigned MinProfitableTrips) const { auto *TripCount = SE.getBackedgeTakenCount(L); - int count = 1; + int NumLoops = 1; + int MaxLoopDepth = 1; if (auto *TripCountC = dyn_cast(TripCount)) if (TripCountC->getType()->getScalarSizeInBits() <= 64) - if (TripCountC->getValue()->getZExtValue() < MIN_LOOP_TRIP_COUNT) - count -= 1; + if (TripCountC->getValue()->getZExtValue() <= MinProfitableTrips) + NumLoops -= 1; - for (auto &SubLoop : *L) - count += countBeneficialSubLoops(SubLoop, SE); + for (auto &SubLoop : *L) { + LoopStats Stats = countBeneficialSubLoops(SubLoop, SE, MinProfitableTrips); + NumLoops += Stats.NumLoops; + MaxLoopDepth += std::max(MaxLoopDepth, Stats.MaxDepth + 1); + } - return count; + return {NumLoops, MaxLoopDepth}; } -int ScopDetection::countBeneficialLoops(Region *R) const { +ScopDetection::LoopStats +ScopDetection::countBeneficialLoops(Region *R, + unsigned MinProfitableTrips) const { int LoopNum = 0; + int MaxLoopDepth = 0; auto L = LI->getLoopFor(R->getEntry()); L = L ? R->outermostLoopInRegion(L) : nullptr; @@ -1069,10 +1102,14 @@ int ScopDetection::countBeneficialLoops(Region *R) const { L ? L->getSubLoopsVector() : std::vector(LI->begin(), LI->end()); for (auto &SubLoop : SubLoops) - if (R->contains(SubLoop)) - LoopNum += countBeneficialSubLoops(SubLoop, *SE); + if (R->contains(SubLoop)) { + LoopStats Stats = + countBeneficialSubLoops(SubLoop, *SE, MinProfitableTrips); + LoopNum += Stats.NumLoops; + MaxLoopDepth = std::max(MaxLoopDepth, Stats.MaxDepth); + } - return LoopNum; + return {LoopNum, MaxLoopDepth}; } Region *ScopDetection::expandRegion(Region &R) { @@ -1138,16 +1175,13 @@ static bool regionWithoutLoops(Region &R, LoopInfo *LI) { return true; } -unsigned ScopDetection::removeCachedResultsRecursively(const Region &R) { - unsigned Count = 0; +void ScopDetection::removeCachedResultsRecursively(const Region &R) { for (auto &SubRegion : R) { if (ValidRegions.count(SubRegion.get())) { removeCachedResults(*SubRegion.get()); - ++Count; } else - Count += removeCachedResultsRecursively(*SubRegion); + removeCachedResultsRecursively(*SubRegion); } - return Count; } void ScopDetection::removeCachedResults(const Region &R) { @@ -1170,7 +1204,6 @@ void ScopDetection::findScops(Region &R) { if (HasErrors) { removeCachedResults(R); } else { - ++ValidRegion; ValidRegions.insert(&R); return; } @@ -1208,10 +1241,7 @@ void ScopDetection::findScops(Region &R) { R.addSubRegion(ExpandedR, true); ValidRegions.insert(ExpandedR); removeCachedResults(*CurrentRegion); - - // Erase all (direct and indirect) children of ExpandedR from the valid - // regions and update the number of valid regions. - ValidRegion -= removeCachedResultsRecursively(*ExpandedR); + removeCachedResultsRecursively(*ExpandedR); } } @@ -1295,7 +1325,7 @@ bool ScopDetection::isProfitableRegion(DetectionContext &Context) const { if (!Context.hasStores || !Context.hasLoads) return invalid(Context, /*Assert=*/true, &CurRegion); - int NumLoops = countBeneficialLoops(&CurRegion); + int NumLoops = countBeneficialLoops(&CurRegion, MIN_LOOP_TRIP_COUNT).NumLoops; int NumAffineLoops = NumLoops - Context.BoxedLoopsSet.size(); // Scops with at least two loops may allow either loop fusion or tiling and @@ -1456,6 +1486,39 @@ bool ScopDetection::isReducibleRegion(Region &R, DebugLoc &DbgLoc) const { return true; } +void updateLoopCountStatistic(ScopDetection::LoopStats Stats, + bool OnlyProfitable) { + if (!OnlyProfitable) { + NumLoopsInScop += Stats.NumLoops; + if (Stats.MaxDepth == 1) + NumScopsDepthOne++; + else if (Stats.MaxDepth == 2) + NumScopsDepthTwo++; + else if (Stats.MaxDepth == 3) + NumScopsDepthThree++; + else if (Stats.MaxDepth == 4) + NumScopsDepthFour++; + else if (Stats.MaxDepth == 5) + NumScopsDepthFive++; + else + NumScopsDepthLarger++; + } else { + NumLoopsInProfScop += Stats.NumLoops; + if (Stats.MaxDepth == 1) + NumProfScopsDepthOne++; + else if (Stats.MaxDepth == 2) + NumProfScopsDepthTwo++; + else if (Stats.MaxDepth == 3) + NumProfScopsDepthThree++; + else if (Stats.MaxDepth == 4) + NumProfScopsDepthFour++; + else if (Stats.MaxDepth == 5) + NumProfScopsDepthFive++; + else + NumProfScopsDepthLarger++; + } +} + bool ScopDetection::runOnFunction(llvm::Function &F) { LI = &getAnalysis().getLoopInfo(); RI = &getAnalysis().getRegionInfo(); @@ -1477,6 +1540,8 @@ bool ScopDetection::runOnFunction(llvm::Function &F) { findScops(*TopRegion); + NumScopRegions += ValidRegions.size(); + // Prune non-profitable regions. for (auto &DIt : DetectionContextMap) { auto &DC = DIt.getSecond(); @@ -1484,12 +1549,19 @@ bool ScopDetection::runOnFunction(llvm::Function &F) { continue; if (!ValidRegions.count(&DC.CurRegion)) continue; - if (isProfitableRegion(DC)) + LoopStats Stats = countBeneficialLoops(&DC.CurRegion, 0); + updateLoopCountStatistic(Stats, false /* OnlyProfitable */); + if (isProfitableRegion(DC)) { + updateLoopCountStatistic(Stats, true /* OnlyProfitable */); continue; + } ValidRegions.remove(&DC.CurRegion); } + NumProfScopRegions += ValidRegions.size(); + NumLoopsOverall += countBeneficialLoops(TopRegion, 0).NumLoops; + // Only makes sense when we tracked errors. if (PollyTrackFailures) emitMissedRemarks(F); diff --git a/polly/test/ScopInfo/Alias-0.ll b/polly/test/ScopInfo/Alias-0.ll index 4077266..d63d7b7 100644 --- a/polly/test/ScopInfo/Alias-0.ll +++ b/polly/test/ScopInfo/Alias-0.ll @@ -32,5 +32,5 @@ return: ; preds = %bb3 declare i32 @rnd(...) -; RTA: 1 polly-detect - Number of regions that a valid part of Scop +; RTA: 1 polly-detect - Number of scops ; NORTA: 1 polly-detect - Number of rejected regions: Base address aliasing diff --git a/polly/test/ScopInfo/Alias-1.ll b/polly/test/ScopInfo/Alias-1.ll index 13d566f..e592990 100644 --- a/polly/test/ScopInfo/Alias-1.ll +++ b/polly/test/ScopInfo/Alias-1.ll @@ -33,5 +33,5 @@ return: ; preds = %bb3 declare i32 @rnd(...) -; RTA: 1 polly-detect - Number of regions that a valid part of Scop +; RTA: 1 polly-detect - Number of scops ; NORTA: 1 polly-detect - Number of rejected regions: Base address aliasing diff --git a/polly/test/ScopInfo/Alias-2.ll b/polly/test/ScopInfo/Alias-2.ll index b308aef..5bd6080 100644 --- a/polly/test/ScopInfo/Alias-2.ll +++ b/polly/test/ScopInfo/Alias-2.ll @@ -31,5 +31,5 @@ return: ; preds = %bb ret void } -; RTA: 1 polly-detect - Number of regions that a valid part of Scop +; RTA: 1 polly-detect - Number of scops ; NORTA: 1 polly-detect - Number of rejected regions: Base address aliasing diff --git a/polly/test/ScopInfo/Alias-3.ll b/polly/test/ScopInfo/Alias-3.ll index 4db5f04..b3b476a 100644 --- a/polly/test/ScopInfo/Alias-3.ll +++ b/polly/test/ScopInfo/Alias-3.ll @@ -24,5 +24,5 @@ return: ; preds = %bb } -; RTA: 1 polly-detect - Number of regions that a valid part of Scop +; RTA: 1 polly-detect - Number of scops ; NORTA: 1 polly-detect - Number of rejected regions: Base address aliasing diff --git a/polly/test/ScopInfo/Alias-4.ll b/polly/test/ScopInfo/Alias-4.ll index 7cd4d39..1955a86 100644 --- a/polly/test/ScopInfo/Alias-4.ll +++ b/polly/test/ScopInfo/Alias-4.ll @@ -24,5 +24,5 @@ return: ; preds = %bb } -; RTA: 1 polly-detect - Number of regions that a valid part of Scop +; RTA: 1 polly-detect - Number of scops ; NORTA: 1 polly-detect - Number of rejected regions: Base address aliasing -- 2.7.4