From c4861e32ed9096e5f737bc938073077ce279dbcc Mon Sep 17 00:00:00 2001 From: OCHyams Date: Wed, 29 Mar 2023 13:29:51 +0100 Subject: [Assignment Tracking] Elide a map copy in some cases Restructure AssignmentTrackingLowering::join to avoid a map copy in the case where BB has more than one pred. We only need to perform a copy of a pred LiveOut if there's exactly one already-visited pred (Result = PredLiveOut). With more than one pred the result is built by calling Result = join(std::move(Result), PredLiveOut) for each subsequent pred, where join parameters are const &. i.e. with more than 1 pred we can avoid copying by referencing the first two pred LiveOuts in the first join and then using a move + reference for the rest. This reduces compile time for CTMark LTO-O3-g builds. Reviewed By: jmorse Differential Revision: https://reviews.llvm.org/D144732 --- llvm/lib/CodeGen/AssignmentTrackingAnalysis.cpp | 86 ++++++++++++++++--------- 1 file changed, 55 insertions(+), 31 deletions(-) (limited to 'llvm/lib/CodeGen/AssignmentTrackingAnalysis.cpp') diff --git a/llvm/lib/CodeGen/AssignmentTrackingAnalysis.cpp b/llvm/lib/CodeGen/AssignmentTrackingAnalysis.cpp index 4a4e537..02b113b 100644 --- a/llvm/lib/CodeGen/AssignmentTrackingAnalysis.cpp +++ b/llvm/lib/CodeGen/AssignmentTrackingAnalysis.cpp @@ -1759,48 +1759,72 @@ AssignmentTrackingLowering::joinBlockInfo(const BlockInfo &A, bool AssignmentTrackingLowering::join( const BasicBlock &BB, const SmallPtrSet &Visited) { - BlockInfo BBLiveIn; - bool FirstJoin = true; - // LiveIn locs for BB is the join of the already-processed preds' LiveOut - // locs. + + SmallVector VisitedPreds; + // Ignore backedges if we have not visited the predecessor yet. As the + // predecessor hasn't yet had locations propagated into it, most locations + // will not yet be valid, so treat them as all being uninitialized and + // potentially valid. If a location guessed to be correct here is + // invalidated later, we will remove it when we revisit this block. This + // is essentially the same as initialising all LocKinds and Assignments to + // an implicit ⊥ value which is the identity value for the join operation. for (auto I = pred_begin(&BB), E = pred_end(&BB); I != E; I++) { - // Ignore backedges if we have not visited the predecessor yet. As the - // predecessor hasn't yet had locations propagated into it, most locations - // will not yet be valid, so treat them as all being uninitialized and - // potentially valid. If a location guessed to be correct here is - // invalidated later, we will remove it when we revisit this block. This - // is essentially the same as initialising all LocKinds and Assignments to - // an implicit ⊥ value which is the identity value for the join operation. const BasicBlock *Pred = *I; - if (!Visited.count(Pred)) - continue; + if (Visited.count(Pred)) + VisitedPreds.push_back(Pred); + } - auto PredLiveOut = LiveOut.find(Pred); - // Pred must have been processed already. See comment at start of this loop. - assert(PredLiveOut != LiveOut.end()); + // No preds visited yet. + if (VisitedPreds.empty()) { + auto It = LiveIn.try_emplace(&BB, BlockInfo()); + bool DidInsert = It.second; + if (DidInsert) + It.first->second.init(TrackedVariablesVectorSize); + return /*Changed*/ DidInsert; + } + + // Exactly one visited pred. Copy the LiveOut from that pred into BB LiveIn. + if (VisitedPreds.size() == 1) { + const BlockInfo &PredLiveOut = LiveOut.find(VisitedPreds[0])->second; + auto CurrentLiveInEntry = LiveIn.find(&BB); - // Perform the join of BBLiveIn (current live-in info) and PrevLiveOut. - if (FirstJoin) - BBLiveIn = PredLiveOut->second; + // Check if there isn't an entry, or there is but the LiveIn set has + // changed (expensive check). + if (CurrentLiveInEntry == LiveIn.end()) + LiveIn.insert(std::make_pair(&BB, PredLiveOut)); + else if (PredLiveOut != CurrentLiveInEntry->second) + CurrentLiveInEntry->second = PredLiveOut; else - BBLiveIn = joinBlockInfo(std::move(BBLiveIn), PredLiveOut->second); - FirstJoin = false; + return /*Changed*/ false; + return /*Changed*/ true; } - if (FirstJoin) - BBLiveIn.init(TrackedVariablesVectorSize); + // More than one pred. Join LiveOuts of blocks 1 and 2. + assert(VisitedPreds.size() > 1); + const BlockInfo &PredLiveOut0 = LiveOut.find(VisitedPreds[0])->second; + const BlockInfo &PredLiveOut1 = LiveOut.find(VisitedPreds[1])->second; + BlockInfo BBLiveIn = joinBlockInfo(PredLiveOut0, PredLiveOut1); + + // Join the LiveOuts of subsequent blocks. + ArrayRef Tail = ArrayRef(VisitedPreds).drop_front(2); + for (const BasicBlock *Pred : Tail) { + const auto &PredLiveOut = LiveOut.find(Pred); + assert(PredLiveOut != LiveOut.end() && + "block should have been processed already"); + BBLiveIn = joinBlockInfo(std::move(BBLiveIn), PredLiveOut->second); + } + // Save the joined result for BB. auto CurrentLiveInEntry = LiveIn.find(&BB); // Check if there isn't an entry, or there is but the LiveIn set has changed // (expensive check). - if (CurrentLiveInEntry == LiveIn.end() || - BBLiveIn != CurrentLiveInEntry->second) { - LiveIn[&BB] = std::move(BBLiveIn); - // A change has occured. - return true; - } - // No change. - return false; + if (CurrentLiveInEntry == LiveIn.end()) + LiveIn.try_emplace(&BB, std::move(BBLiveIn)); + else if (BBLiveIn != CurrentLiveInEntry->second) + CurrentLiveInEntry->second = std::move(BBLiveIn); + else + return /*Changed*/ false; + return /*Changed*/ true; } /// Return true if A fully contains B. -- cgit v1.1