From 95ef556bd12ad879fd27157ea60cdc213717459d Mon Sep 17 00:00:00 2001 From: Michael Kruse Date: Sat, 13 Feb 2021 00:36:19 -0600 Subject: [PATCH] [Polly] Preserve DetectionContext references. DetectionContext objects are stored as values in a DenseMap. When the DenseMap reaches its maximum load factor, it is resized and all its objects moved to a new memory allocation. Unfortunately Scop object have a reference to its DetectionContext. When the DenseMap resizes, all the DetectionContexts reference now point to invalid memory, even if caused by an unrelated DetectionContext. Even worse, NewPM's ScopPassManager called isMaxRegionInScop with the Verify=true parameter before each pass. This caused the old DetectionContext to be removed an a new on created and re-verified. Of course, the Scop object was already created pointing to the old DetectionContext. Because the new DetectionContext would usually be stored at the same position in the DenseMap, the reference would usually reference the new DetectionContext of the same Region. Usually. If not, the old position still points to memory in the DenseMap allocation (unless also a resizing occurs) such that tools like Valgrind and AddressSanitizer would not be able to diagnose this. Instead of storing the DetectionContext inside the DenseMap, use a std::unique_ptr to a DetectionContext allocation, i.e. it will not move around anymore. This also allows use to remove the very strange DetectionContext(const DetectionContext &&) copy/move(?) constructor. DetectionContext objects now are neither copied nor moved. As a result, every re-verification of a DetectionContext will use a new allocation. Therefore, once a Scop object has been created using a DetectionContext, it must not be re-verified (the Scop data structure requires its underlying Region to not change before code generation anyway). The NewPM may call isMaxRegionInScop only with Validate=false parameter. --- polly/include/polly/ScopDetection.h | 20 +++---------- polly/include/polly/ScopPass.h | 2 +- polly/lib/Analysis/ScopDetection.cpp | 46 +++++++++++++++++------------ polly/test/Isl/CodeGen/multiple-codegens.ll | 2 ++ 4 files changed, 34 insertions(+), 36 deletions(-) diff --git a/polly/include/polly/ScopDetection.h b/polly/include/polly/ScopDetection.h index 835dd13..86a3a8e 100644 --- a/polly/include/polly/ScopDetection.h +++ b/polly/include/polly/ScopDetection.h @@ -188,20 +188,6 @@ public: /// Initialize a DetectionContext from scratch. DetectionContext(Region &R, AAResults &AA, bool Verify) : CurRegion(R), AST(AA), Verifying(Verify), Log(&R) {} - - /// Initialize a DetectionContext with the data from @p DC. - DetectionContext(const DetectionContext &&DC) - : CurRegion(DC.CurRegion), AST(DC.AST.getAliasAnalysis()), - Verifying(DC.Verifying), Log(std::move(DC.Log)), - Accesses(std::move(DC.Accesses)), - NonAffineAccesses(std::move(DC.NonAffineAccesses)), - ElementSize(std::move(DC.ElementSize)), hasLoads(DC.hasLoads), - hasStores(DC.hasStores), HasUnknownAccess(DC.HasUnknownAccess), - NonAffineSubRegionSet(std::move(DC.NonAffineSubRegionSet)), - BoxedLoopsSet(std::move(DC.BoxedLoopsSet)), - RequiredILS(std::move(DC.RequiredILS)) { - AST.add(DC.AST); - } }; /// Helper data structure to collect statistics about loop counts. @@ -226,7 +212,8 @@ private: //@} /// Map to remember detection contexts for all regions. - using DetectionContextMapTy = DenseMap; + using DetectionContextMapTy = + DenseMap>; mutable DetectionContextMapTy DetectionContextMap; /// Remove cached results for @p R. @@ -558,7 +545,8 @@ public: /// /// @param R The Region to test if it is maximum. /// @param Verify Rerun the scop detection to verify SCoP was not invalidated - /// meanwhile. + /// meanwhile. Do not use if the region's DetectionContect is + /// referenced by a Scop that is still to be processed. /// /// @return Return true if R is the maximum Region in a Scop, false otherwise. bool isMaxRegionInScop(const Region &R, bool Verify = true) const; diff --git a/polly/include/polly/ScopPass.h b/polly/include/polly/ScopPass.h index ccd6da1..f3c3020 100644 --- a/polly/include/polly/ScopPass.h +++ b/polly/include/polly/ScopPass.h @@ -247,7 +247,7 @@ public: while (!Worklist.empty()) { Region *R = Worklist.pop_back_val(); - if (!SD.isMaxRegionInScop(*R)) + if (!SD.isMaxRegionInScop(*R, /*Verifying=*/false)) continue; Scop *scop = SI.getScop(R); if (!scop) diff --git a/polly/lib/Analysis/ScopDetection.cpp b/polly/lib/Analysis/ScopDetection.cpp index e357965..c358f76 100644 --- a/polly/lib/Analysis/ScopDetection.cpp +++ b/polly/lib/Analysis/ScopDetection.cpp @@ -352,7 +352,7 @@ ScopDetection::ScopDetection(Function &F, const DominatorTree &DT, // Prune non-profitable regions. for (auto &DIt : DetectionContextMap) { - auto &DC = DIt.getSecond(); + DetectionContext &DC = *DIt.getSecond().get(); if (DC.Log.hasErrors()) continue; if (!ValidRegions.count(&DC.CurRegion)) @@ -405,12 +405,17 @@ bool ScopDetection::isMaxRegionInScop(const Region &R, bool Verify) const { return false; if (Verify) { - DetectionContextMap.erase(getBBPairForRegion(&R)); - const auto &It = DetectionContextMap.insert(std::make_pair( - getBBPairForRegion(&R), - DetectionContext(const_cast(R), AA, false /*verifying*/))); - DetectionContext &Context = It.first->second; - return isValidRegion(Context); + BBPair P = getBBPairForRegion(&R); + std::unique_ptr &Entry = DetectionContextMap[P]; + + // Free previous DetectionContext for the region and create and verify a new + // one. Be sure that the DetectionContext is not still used by a ScopInfop. + // Due to changes but CodeGeneration of another Scop, the Region object and + // the BBPair might not match anymore. + Entry = std::make_unique(const_cast(R), AA, + /*Verifying=*/false); + + return isValidRegion(*Entry.get()); } return true; @@ -1398,10 +1403,12 @@ Region *ScopDetection::expandRegion(Region &R) { LLVM_DEBUG(dbgs() << "\tExpanding " << R.getNameStr() << "\n"); while (ExpandedRegion) { - const auto &It = DetectionContextMap.insert(std::make_pair( - getBBPairForRegion(ExpandedRegion.get()), - DetectionContext(*ExpandedRegion, AA, false /*verifying*/))); - DetectionContext &Context = It.first->second; + BBPair P = getBBPairForRegion(ExpandedRegion.get()); + std::unique_ptr &Entry = DetectionContextMap[P]; + Entry = std::make_unique(*ExpandedRegion, AA, + /*Verifying=*/false); + DetectionContext &Context = *Entry.get(); + LLVM_DEBUG(dbgs() << "\t\tTrying " << ExpandedRegion->getNameStr() << "\n"); // Only expand when we did not collect errors. @@ -1411,7 +1418,7 @@ Region *ScopDetection::expandRegion(Region &R) { // - if false, .tbd. => stop (should this really end the loop?) if (!allBlocksValid(Context) || Context.Log.hasErrors()) { removeCachedResults(*ExpandedRegion); - DetectionContextMap.erase(It.first); + DetectionContextMap.erase(P); break; } @@ -1419,7 +1426,7 @@ Region *ScopDetection::expandRegion(Region &R) { // far). if (LastValidRegion) { removeCachedResults(*LastValidRegion); - DetectionContextMap.erase(getBBPairForRegion(LastValidRegion.get())); + DetectionContextMap.erase(P); } LastValidRegion = std::move(ExpandedRegion); @@ -1430,7 +1437,7 @@ Region *ScopDetection::expandRegion(Region &R) { } else { // Create and test the next greater region (if any) removeCachedResults(*ExpandedRegion); - DetectionContextMap.erase(It.first); + DetectionContextMap.erase(P); ExpandedRegion = std::unique_ptr(ExpandedRegion->getExpandedRegion()); } @@ -1468,9 +1475,10 @@ void ScopDetection::removeCachedResults(const Region &R) { } void ScopDetection::findScops(Region &R) { - const auto &It = DetectionContextMap.insert(std::make_pair( - getBBPairForRegion(&R), DetectionContext(R, AA, false /*verifying*/))); - DetectionContext &Context = It.first->second; + std::unique_ptr &Entry = + DetectionContextMap[getBBPairForRegion(&R)]; + Entry = std::make_unique(R, AA, /*Verifying=*/false); + DetectionContext &Context = *Entry.get(); bool RegionIsValid = false; if (!PollyProcessUnprofitable && regionWithoutLoops(R, LI)) @@ -1705,7 +1713,7 @@ void ScopDetection::printLocations(Function &F) { void ScopDetection::emitMissedRemarks(const Function &F) { for (auto &DIt : DetectionContextMap) { - auto &DC = DIt.getSecond(); + DetectionContext &DC = *DIt.getSecond().get(); if (DC.Log.hasErrors()) emitRejectionRemarks(DIt.getFirst(), DC.Log, ORE); } @@ -1831,7 +1839,7 @@ ScopDetection::getDetectionContext(const Region *R) const { auto DCMIt = DetectionContextMap.find(getBBPairForRegion(R)); if (DCMIt == DetectionContextMap.end()) return nullptr; - return &DCMIt->second; + return DCMIt->second.get(); } const RejectLog *ScopDetection::lookupRejectionLog(const Region *R) const { diff --git a/polly/test/Isl/CodeGen/multiple-codegens.ll b/polly/test/Isl/CodeGen/multiple-codegens.ll index b9bfb55..a40f101 100644 --- a/polly/test/Isl/CodeGen/multiple-codegens.ll +++ b/polly/test/Isl/CodeGen/multiple-codegens.ll @@ -1,4 +1,6 @@ ; RUN: opt %loadPolly -polly-scops -polly-opt-isl -polly-codegen -polly-scops -polly-codegen -S < %s | FileCheck %s +; RUN: opt %loadPolly "-passes=scop(polly-opt-isl,polly-codegen,polly-codegen)" -S < %s | FileCheck %s +; RUN: opt %loadPolly "-passes=scop(polly-opt-isl,polly-codegen),scop(polly-codegen)" -S < %s | FileCheck %s ; ; llvm.org/PR34441 ; Properly handle multiple -polly-scops/-polly-codegen in the same -- 2.7.4