| //===--- LoopRegionAnalysis.cpp -------------------------------------------===// |
| // |
| // This source file is part of the Swift.org open source project |
| // |
| // Copyright (c) 2014 - 2017 Apple Inc. and the Swift project authors |
| // Licensed under Apache License v2.0 with Runtime Library Exception |
| // |
| // See https://swift.org/LICENSE.txt for license information |
| // See https://swift.org/CONTRIBUTORS.txt for the list of Swift project authors |
| // |
| //===----------------------------------------------------------------------===// |
| |
| #define DEBUG_TYPE "sil-loop-region-analysis" |
| #include "swift/SILOptimizer/Analysis/LoopRegionAnalysis.h" |
| #include "swift/Basic/Range.h" |
| #include "llvm/Support/DOTGraphTraits.h" |
| #include "llvm/Support/CommandLine.h" |
| #include "llvm/Support/GraphWriter.h" |
| |
| using namespace swift; |
| |
| //===----------------------------------------------------------------------===// |
| // LoopRegion |
| //===----------------------------------------------------------------------===// |
| |
| LoopRegion::~LoopRegion() { |
| // Blocks do not have subregion data, so everything should just clean up via |
| // RAII. |
| if (isBlock()) |
| return; |
| |
| // Otherwise, we need to cleanup subregion data. |
| getSubregionData().~SubregionData(); |
| } |
| |
| LoopRegion::BlockTy *LoopRegion::getBlock() const { |
| return Ptr.get<BlockTy *>(); |
| } |
| |
| LoopRegion::LoopTy *LoopRegion::getLoop() const { |
| return Ptr.get<LoopTy *>(); |
| } |
| |
| LoopRegion::FunctionTy *LoopRegion::getFunction() const { |
| return Ptr.get<FunctionTy *>(); |
| } |
| |
| void LoopRegion::dump(bool isVerbose) const { |
| print(llvm::outs(), false, isVerbose); |
| llvm::outs() << "\n"; |
| } |
| |
| void LoopRegion::dumpName() const { |
| printName(llvm::outs()); |
| llvm::outs() << "\n"; |
| } |
| |
| void LoopRegion::printName(llvm::raw_ostream &os) const { |
| if (isBlock()) { |
| os << "BB" << getID(); |
| return; |
| } |
| if (isLoop()) { |
| os << "Loop" << getID(); |
| return; |
| } |
| assert(isFunction()); |
| os << "Function" << getID(); |
| return; |
| } |
| |
| void LoopRegion::print(llvm::raw_ostream &os, bool isShort, |
| bool isVerbose) const { |
| os << "(region id:" << ID; |
| if (isShort) { |
| os << ")"; |
| return; |
| } |
| os << " kind:"; |
| if (isBlock()) { |
| os << "bb "; |
| } else if (isLoop()) { |
| os << "loop"; |
| } else if (isFunction()) { |
| os << "func"; |
| } else { |
| llvm_unreachable("Unknown region type"); |
| } |
| |
| os << " ucfh:" << (IsUnknownControlFlowEdgeHead? "true " : "false") |
| << " ucft:" << (IsUnknownControlFlowEdgeTail? "true " : "false"); |
| |
| if (!isVerbose) { |
| return; |
| } |
| os << "\n"; |
| if (isBlock()) { |
| getBlock()->dump(); |
| } else if (isLoop()) { |
| getLoop()->dump(); |
| } else if (isFunction()) { |
| getFunction()->dump(); |
| } else { |
| llvm_unreachable("Unknown region type"); |
| } |
| } |
| |
| llvm::raw_ostream &llvm::operator<<(llvm::raw_ostream &os, LoopRegion &LR) { |
| LR.print(os); |
| return os; |
| } |
| |
| LoopRegion::SuccRange LoopRegion::getSuccs() const { |
| auto Range = InnerSuccRange(Succs.begin(), Succs.end()); |
| return SuccRange(Range, SuccessorID::ToLiveSucc()); |
| } |
| |
| LoopRegion::LocalSuccRange LoopRegion::getLocalSuccs() const { |
| auto Range = InnerSuccRange(Succs.begin(), Succs.end()); |
| return LocalSuccRange(Range, SuccessorID::ToLiveLocalSucc()); |
| } |
| |
| LoopRegion::NonLocalSuccRange LoopRegion::getNonLocalSuccs() const { |
| auto Range = InnerSuccRange(Succs.begin(), Succs.end()); |
| return NonLocalSuccRange(Range, SuccessorID::ToLiveNonLocalSucc()); |
| } |
| |
| /// Replace OldSuccID by NewSuccID, just deleting OldSuccID if what NewSuccID |
| /// is already in the list. |
| void LoopRegion::replaceSucc(SuccessorID OldSucc, SuccessorID NewSucc) { |
| LLVM_DEBUG(llvm::dbgs() << " Replacing " << OldSucc << " with " |
| << NewSucc << "\n"); |
| Succs.replace(OldSucc, NewSucc); |
| } |
| |
| llvm::raw_ostream &llvm::operator<<(llvm::raw_ostream &os, |
| LoopRegion::SuccessorID &S) { |
| return os << "(succ id:" << S.ID |
| << " nonlocal:" << (S.IsNonLocal ? "true" : "false") << ")"; |
| } |
| |
| //===----------------------------------------------------------------------===// |
| // LoopRegionFunctionInfo |
| //===----------------------------------------------------------------------===// |
| |
| LoopRegionFunctionInfo::LoopRegionFunctionInfo(FunctionTy *F, |
| PostOrderFunctionInfo *PI, |
| LoopInfoTy *LI) |
| : F(F), Allocator(), BBToIDMap(), LoopToIDMap(), |
| #ifndef NDEBUG |
| IDToRegionMap(PI->size()), AllBBRegionsCreated(false) { |
| #else |
| IDToRegionMap(PI->size()) { |
| #endif |
| if (F->isExternalDeclaration()) |
| return; |
| LLVM_DEBUG(llvm::dbgs() << "**** LOOP REGION FUNCTION INFO ****\n"); |
| LLVM_DEBUG(llvm::dbgs() << "Analyzing function: " << F->getName() << "\n"); |
| initializeBlockRegions(PI, LI); |
| initializeLoopRegions(LI); |
| initializeFunctionRegion(LI->getTopLevelLoops()); |
| #ifndef NDEBUG |
| verify(); |
| #endif |
| } |
| |
| LoopRegionFunctionInfo::~LoopRegionFunctionInfo() { |
| for (auto *R : IDToRegionMap) { |
| R->~RegionTy(); |
| } |
| IDToRegionMap.clear(); |
| } |
| |
| void LoopRegionFunctionInfo::verify() { |
| #ifndef NDEBUG |
| llvm::SmallVector<unsigned, 8> UniquePredList; |
| for (auto *R : IDToRegionMap) { |
| // Make sure that our region has a pred list without duplicates. We do not |
| // care if the predecessor list is sorted, just that it is unique. |
| { |
| UniquePredList.clear(); |
| std::copy(R->Preds.begin(), R->Preds.end(), std::back_inserter(UniquePredList)); |
| std::sort(UniquePredList.begin(), UniquePredList.end()); |
| auto End = UniquePredList.end(); |
| assert(End == std::unique(UniquePredList.begin(), UniquePredList.end()) && |
| "Expected UniquePredList to not have any duplicate elements"); |
| } |
| |
| // If this node does not have a parent, it should have no non-local |
| // successors. |
| if (!R->ParentID.hasValue()) { |
| auto NLSuccs = R->getNonLocalSuccs(); |
| assert(NLSuccs.begin() == NLSuccs.end() && |
| "Cannot have non local " |
| "successors without a parent node"); |
| continue; |
| } |
| |
| // If this node /does/ have a parent, make sure that all non-local |
| // successors point to a successor in the parent and match whether or not it |
| // is dead. |
| auto *ParentRegion = getRegion(*R->ParentID); |
| unsigned NumParentSuccs = ParentRegion->succ_size(); |
| for (LoopRegion::SuccessorID ID : R->getSuccs()) { |
| // Skip local successors. We are not verifying anything here. |
| if (!ID.IsNonLocal) |
| continue; |
| assert(ID.ID < NumParentSuccs && "Non local successor pointing off the " |
| "parent node successor list?!"); |
| // Since we are not dead, make sure our parent is not dead. |
| assert(ParentRegion->Succs[ID.ID].hasValue() && |
| "non-local successor edge sources should have the same liveness " |
| "properties as non-local successor edge targets"); |
| // Make sure that we can look up the local region corresponding to this |
| // region's successor. |
| auto *OtherR = getRegionForNonLocalSuccessor(R, ID.ID); |
| (void)OtherR; |
| |
| // If R and OtherR are blocks, then OtherR should be a successor of the |
| // real block. |
| if (R->isBlock() && OtherR->isBlock()) |
| assert(R->getBlock()->isSuccessorBlock(OtherR->getBlock()) && |
| "Expected either R was not a block or OtherR was a CFG level " |
| "successor of R."); |
| } |
| } |
| #endif |
| } |
| |
| //===--- |
| // Region Creation Functions |
| // |
| |
| LoopRegionFunctionInfo::RegionTy * |
| LoopRegionFunctionInfo::getRegion(BlockTy *BB) const { |
| assert(AllBBRegionsCreated && "All BB Regions have not been created yet?!"); |
| // Check if we have allocated a region for this BB. If so, just return it. |
| auto Iter = BBToIDMap.find(BB); |
| if (Iter != BBToIDMap.end()) { |
| return IDToRegionMap[Iter->second]; |
| } |
| llvm_unreachable("Unknown BB?!"); |
| } |
| |
| LoopRegionFunctionInfo::RegionTy * |
| LoopRegionFunctionInfo::getRegion(FunctionTy *F) const { |
| if (FunctionRegionID.hasValue()) { |
| return IDToRegionMap[FunctionRegionID.getValue()]; |
| } |
| |
| auto &Self = const_cast<LoopRegionFunctionInfo &>(*this); |
| unsigned Idx = IDToRegionMap.size(); |
| unsigned NumBytes = sizeof(RegionTy) + sizeof(LoopRegion::SubregionData); |
| void *Memory = Self.Allocator.Allocate(NumBytes, alignof(RegionTy)); |
| auto *R = new (Memory) RegionTy(F, Idx); |
| new ((void *)&R[1]) LoopRegion::SubregionData(); |
| Self.IDToRegionMap.push_back(R); |
| Self.FunctionRegionID = Idx; |
| return R; |
| } |
| |
| LoopRegionFunctionInfo::RegionTy * |
| LoopRegionFunctionInfo::getRegion(LoopTy *Loop) const { |
| auto Iter = LoopToIDMap.find(Loop); |
| if (Iter != LoopToIDMap.end()) { |
| return IDToRegionMap[Iter->second]; |
| } |
| |
| auto &Self = const_cast<LoopRegionFunctionInfo &>(*this); |
| unsigned Idx = IDToRegionMap.size(); |
| unsigned NumBytes = sizeof(RegionTy) + sizeof(LoopRegion::SubregionData); |
| void *Memory = Self.Allocator.Allocate(NumBytes, alignof(RegionTy)); |
| auto *R = new (Memory) RegionTy(Loop, Idx); |
| new ((void *)&R[1]) LoopRegion::SubregionData(); |
| Self.IDToRegionMap.push_back(R); |
| Self.LoopToIDMap[Loop] = Idx; |
| return R; |
| } |
| |
| LoopRegionFunctionInfo::RegionTy * |
| LoopRegionFunctionInfo::createRegion(BlockTy *BB, unsigned RPONum) { |
| assert(!AllBBRegionsCreated && "All BB Regions have been created?!"); |
| // Check if we have allocated a region for this BB. If so, just return it. |
| auto Iter = BBToIDMap.find(BB); |
| if (Iter != BBToIDMap.end()) { |
| return IDToRegionMap[Iter->second]; |
| } |
| |
| unsigned Idx = RPONum; |
| auto *R = new (Allocator) RegionTy(BB, RPONum); |
| IDToRegionMap[RPONum] = R; |
| BBToIDMap[BB] = Idx; |
| return R; |
| } |
| |
| //===--- |
| // Block Region Initialization |
| // |
| |
| void LoopRegionFunctionInfo::initializeBlockRegionSuccessors( |
| BlockTy *BB, RegionTy *BBRegion, PostOrderFunctionInfo *PI) { |
| for (auto *SuccBB : BB->getSuccessorBlocks()) { |
| unsigned SuccRPOIndex = *PI->getRPONumber(SuccBB); |
| auto *SuccRegion = createRegion(SuccBB, SuccRPOIndex); |
| BBRegion->addSucc(SuccRegion); |
| SuccRegion->addPred(BBRegion); |
| LLVM_DEBUG(llvm::dbgs() << " Succ: "; |
| SuccBB->printAsOperand(llvm::dbgs()); |
| llvm::dbgs() << " RPONum: " << SuccRPOIndex << "\n"); |
| } |
| } |
| |
| void LoopRegionFunctionInfo::markIrreducibleLoopPredecessorsOfNonLoopHeader( |
| BlockTy *NonHeaderBB, RegionTy *NonHeaderBBRegion, |
| PostOrderFunctionInfo *PI) { |
| for (BlockTy *Pred : NonHeaderBB->getPredecessorBlocks()) { |
| // If we do not have an RPO number for a predecessor, it is because the |
| // predecessor is unreachable and a pass did not clean up after |
| // itself. Just ignore it, it will be cleaned up by simplify-cfg. |
| auto PredRPONumber = PI->getRPONumber(Pred); |
| if (!PredRPONumber || *PredRPONumber < NonHeaderBBRegion->getRPONumber()) |
| continue; |
| |
| auto *PredRegion = createRegion(Pred, *PredRPONumber); |
| LLVM_DEBUG(llvm::dbgs() << " Backedge: "; |
| Pred->printAsOperand(llvm::dbgs()); |
| llvm::dbgs() << " " << PredRegion->getID() << "\n"); |
| |
| // We mark the head/tail as unknown control flow regions since in CFGs like |
| // the following: |
| // |
| // /------\ |
| // v | |
| // BB0 -> BB1 -> BB2 -> BB4 |
| // | |^ |
| // | v| |
| // \----------> BB3 |
| // |
| // We need to ensure that the edge from BB0 -> BB3 does not propagate any |
| // dataflow state into the irreducible loop even if the back edge we see is |
| // from BB3 -> BB2. |
| NonHeaderBBRegion->IsUnknownControlFlowEdgeHead = true; |
| NonHeaderBBRegion->IsUnknownControlFlowEdgeTail = true; |
| PredRegion->IsUnknownControlFlowEdgeHead = true; |
| PredRegion->IsUnknownControlFlowEdgeTail = true; |
| } |
| LLVM_DEBUG(llvm::dbgs() << "\n"); |
| } |
| |
| void |
| LoopRegionFunctionInfo:: |
| markMultipleLoopLatchLoopBackEdges(RegionTy *LoopHeaderRegion, LoopTy *Loop, |
| PostOrderFunctionInfo *PI) { |
| llvm::SmallVector<BlockTy *, 4> Latches; |
| Loop->getLoopLatches(Latches); |
| assert(Latches.size() > 1 && |
| "Assumed that this loop had multiple loop latches"); |
| |
| LoopHeaderRegion->IsUnknownControlFlowEdgeHead = true; |
| for (auto *LatchBB : Latches) { |
| auto *LatchBBRegion = createRegion(LatchBB, *PI->getRPONumber(LatchBB)); |
| LatchBBRegion->IsUnknownControlFlowEdgeTail = true; |
| } |
| } |
| |
| void LoopRegionFunctionInfo::initializeBlockRegions(PostOrderFunctionInfo *PI, |
| LoopInfoTy *LI) { |
| LLVM_DEBUG(llvm::dbgs() << "Visiting BB Regions:\n"); |
| |
| // Initialize regions for each BB and associate RPO numbers with each BB. |
| // |
| // We use the RPO number of a BB as its Index in our data structures. |
| for (auto P : llvm::enumerate(PI->getReversePostOrder())) { |
| BlockTy *BB = P.value(); |
| unsigned RPOIndex = P.index(); |
| auto *BBRegion = createRegion(BB, RPOIndex); |
| assert(BBRegion && "Create region fail to create a BB?"); |
| assert(*PI->getRPONumber(BB) == RPOIndex && |
| "Enumerated Reverse Post Order out of sync with RPO number"); |
| |
| LLVM_DEBUG(llvm::dbgs() << "Visiting BB: "; |
| BB->printAsOperand(llvm::dbgs()); |
| llvm::dbgs() << " RPO: " << RPOIndex << "\n"); |
| |
| // Wire up this BB as an "initial predecessor" of all of its successors |
| // and make each of its successors a successor for the region. |
| initializeBlockRegionSuccessors(BB, BBRegion, PI); |
| |
| // Then try to lookup the innermost loop that BB belongs to. If we get back |
| // a nullptr, then we know that the BB belongs to the function region and is |
| // also not a loop header. |
| auto *Loop = LI->getLoopFor(BB); |
| auto *ParentRegion = Loop? getRegion(Loop) : getRegion(F); |
| |
| // Add BBRegion to the ParentRegion. |
| ParentRegion->addBlockSubregion(BBRegion); |
| |
| // Determine if this basic block is part of an irreducible loop by looking |
| // at all blocks that are: |
| // |
| // 1. Not in any loop identified by loop info. |
| // 2. Or are part of an identified loop but are not a loop header. |
| // |
| // In such a case, check if any predecessors have a smaller PO number. If so |
| // then we know that both this BB and the predecessor are boundaries of a |
| // loop that is not understood by SILLoopInfo. Mark them as unknown control |
| // flow boundaries. Then add the BB as a subregion to its parent region. |
| LLVM_DEBUG(llvm::dbgs() << "Checking Preds for Back Edges\n"); |
| if (!Loop || !LI->isLoopHeader(BB)) { |
| markIrreducibleLoopPredecessorsOfNonLoopHeader(BB, BBRegion, PI); |
| continue; |
| } |
| assert(Loop && "Should have a non-null Loop at this point"); |
| assert(ParentRegion && "Expected a non-null LoopRegion"); |
| |
| // Now we know that the block is in a loop and is a loop header. Check if |
| // this loop has multiple latches. If so, mark the latch head/tail blocks as |
| // head/tail unknown cfg boundaries. |
| // |
| // We rely on Loop canonicalization to separate such loops into separate |
| // nested loops. |
| ParentRegion->getSubregionData().RPONumOfHeaderBlock = RPOIndex; |
| |
| // If we have one loop latch, continue. |
| if (Loop->getLoopLatch()) { |
| LLVM_DEBUG(llvm::dbgs() << "\n"); |
| continue; |
| } |
| |
| // Otherwise, mark each of the loop latches as irreducible control flow edge |
| // tails so we are conservative around them. |
| markMultipleLoopLatchLoopBackEdges(BBRegion, Loop, PI); |
| LLVM_DEBUG(llvm::dbgs() << "\n"); |
| } |
| |
| #ifndef NDEBUG |
| AllBBRegionsCreated = true; |
| #endif |
| } |
| |
| //===--- |
| // Loop and Function Region Initialization |
| // |
| |
| void LoopRegionFunctionInfo::initializeLoopRegions(LoopInfoTy *LI) { |
| // Now visit the loop nest in a DFS. |
| llvm::SmallVector<LoopTy *, 16> LoopWorklist(LI->begin(), LI->end()); |
| llvm::SmallPtrSet<LoopTy *, 16> VisitedLoops; |
| |
| while (LoopWorklist.size()) { |
| LoopTy *L = LoopWorklist.back(); |
| auto *LRegion = getRegion(L); |
| |
| // If we have not visited this loop yet and it has subloops, add its |
| // subloops to the worklist and continue. |
| auto SubLoops = L->getSubLoopRange(); |
| if (VisitedLoops.insert(L).second && SubLoops.begin() != SubLoops.end()) { |
| for (auto *SubLoop : SubLoops) { |
| LoopWorklist.push_back(SubLoop); |
| } |
| continue; |
| } |
| LoopWorklist.pop_back(); |
| |
| // Otherwise, process this loop. We have already visited all of its |
| // potential children loops. |
| initializeLoopFunctionRegion(LRegion, SubLoops); |
| } |
| } |
| |
| /// For each predecessor of the header of the loop: |
| /// |
| /// 1. If the predecessor is not in the loop, make the predecessor a predecessor |
| /// of the loop instead of the header. |
| /// |
| /// 2. If the predecessor *is* in the loop it must be the tail of a backedge. We |
| /// remove these back edges and instead represent them as unknown control flow |
| /// edges. This is because we rely on loop canonicalization to canonicalize |
| /// multiple backedge loops into separate loops. |
| LoopRegionFunctionInfo::RegionTy * |
| LoopRegionFunctionInfo:: |
| rewriteLoopHeaderPredecessors(LoopTy *SubLoop, RegionTy *SubLoopRegion) { |
| auto *SubLoopHeaderRegion = getRegion(SubLoop->getHeader()); |
| assert(SubLoopHeaderRegion->isBlock() && "A header must always be a block"); |
| |
| LLVM_DEBUG(llvm::dbgs() |
| << " Header: " << SubLoopHeaderRegion->getID() << "\n" |
| << " Rewiring Header Predecessors to be Loop Preds.\n"); |
| |
| if (SubLoopHeaderRegion->IsUnknownControlFlowEdgeHead) |
| SubLoopRegion->IsUnknownControlFlowEdgeHead = true; |
| |
| for (unsigned PredID : SubLoopHeaderRegion->Preds) { |
| auto *PredRegion = getRegion(PredID); |
| |
| LLVM_DEBUG(llvm::dbgs() << " " << PredRegion->getID() << "\n"); |
| if (!SubLoopRegion->containsSubregion(PredRegion)) { |
| LLVM_DEBUG(llvm::dbgs() << " Not in loop... Replacing...\n"); |
| // This is always a local edge since non-local edges can only have loops |
| // as heads. Since the head of our edge is SubLoopHeaderRegion, this must |
| // be local. |
| PredRegion->replaceSucc(LoopRegion::SuccessorID(SubLoopHeaderRegion->ID, |
| /*IsNonLocal*/ false), |
| LoopRegion::SuccessorID(SubLoopRegion->ID, |
| /*IsNonLocal*/ false)); |
| propagateLivenessDownNonLocalSuccessorEdges(PredRegion); |
| SubLoopRegion->addPred(PredRegion); |
| continue; |
| } |
| |
| LLVM_DEBUG(llvm::dbgs() << " Is in loop... Erasing...\n"); |
| // Ok, we have a predecessor inside the loop. This must be a backedge. |
| // |
| // We are abusing the fact that a block can only be a local successor. |
| PredRegion->removeLocalSucc(SubLoopHeaderRegion->getID()); |
| propagateLivenessDownNonLocalSuccessorEdges(PredRegion); |
| SubLoopRegion->getSubregionData().addBackedgeSubregion(PredRegion->getID()); |
| } |
| SubLoopHeaderRegion->Preds.clear(); |
| |
| return SubLoopHeaderRegion; |
| } |
| |
| static void getExitingRegions(LoopRegionFunctionInfo *LRFI, SILLoop *Loop, |
| LoopRegion *LRegion, |
| llvm::SmallVectorImpl<unsigned> &ExitingRegions) { |
| llvm::SmallVector<SILBasicBlock *, 8> ExitingBlocks; |
| Loop->getExitingBlocks(ExitingBlocks); |
| |
| // Determine the outer most region that contains the exiting block that is not |
| // this subloop's region. That is the *true* exiting region. |
| for (auto *BB : ExitingBlocks) { |
| auto *Region = LRFI->getRegion(BB); |
| unsigned RegionParentID = *Region->getParentID(); |
| while (RegionParentID != LRegion->getID()) { |
| Region = LRFI->getRegion(RegionParentID); |
| RegionParentID = *Region->getParentID(); |
| } |
| ExitingRegions.push_back(Region->getID()); |
| } |
| |
| // We can have a loop subregion that has multiple exiting edges from the |
| // current loop. We do not want to visit that loop subregion multiple |
| // times. So we unique the exiting region list. |
| // |
| // In order to make sure we have a deterministic ordering when we visiting |
| // exiting subregions, we need to sort our exiting regions by ID, not pointer |
| // value. |
| sortUnique(ExitingRegions); |
| } |
| |
| /// For each exiting block: |
| /// |
| /// 1. Make any successors outside of the loop successors of the loop instead |
| /// of the exiting block. |
| /// |
| /// 2. Any successors that are inside the loop but are not back edges are |
| /// left alone. |
| /// |
| /// 3. Any successors that are inside the loop but are the head of a backedge |
| /// have the edge removed. This is computed by the successor having a greater |
| /// post order number than the exit. |
| /// |
| /// *NOTE* We have to be careful here since exiting blocks may include BBs |
| /// that have been subsumed into a subloop already. Also to determine back |
| /// edges, we need to compare post order numbers potentially of loop headers, |
| /// not the loops themselves. |
| void |
| LoopRegionFunctionInfo:: |
| rewriteLoopExitingBlockSuccessors(LoopTy *Loop, RegionTy *LRegion) { |
| // Begin by using loop info and loop region info to find all of the exiting |
| // regions. |
| // |
| // We do this by looking up the exiting blocks and finding the outermost |
| // region which the block is a subregion of. Since we initialize our data |
| // structure by processing the loop nest bottom up, this should always give us |
| // the correct region for the level of the loop we are processing. |
| auto &ExitingSubregions = LRegion->getSubregionData().ExitingSubregions; |
| getExitingRegions(this, Loop, LRegion, ExitingSubregions); |
| |
| // Then for each exiting region ER of the Loop L... |
| LLVM_DEBUG(llvm::dbgs() << " Visiting Exit Blocks...\n"); |
| for (unsigned ExitingSubregionID : ExitingSubregions) { |
| auto *ExitingSubregion = getRegion(ExitingSubregionID); |
| LLVM_DEBUG(llvm::dbgs() << " Exiting Region: " |
| << ExitingSubregion->getID() << "\n"); |
| bool HasBackedge = false; |
| |
| // For each successor region S of ER... |
| for (auto SuccID : ExitingSubregion->getSuccs()) { |
| LLVM_DEBUG(llvm::dbgs() << " Succ: " << SuccID.ID |
| << ". IsNonLocal: " |
| << (SuccID.IsNonLocal ? "true" : "false") <<"\n"); |
| |
| // If S is not contained in L, then: |
| // |
| // 1. The successor/predecessor edge in between S and ER with a new |
| // successor/predecessor edge in between S and L. |
| // 2. ER is given a non-local successor edge that points at the successor |
| // index in L that points at S. This will enable us to recover the |
| // original edge if we need to. |
| // |
| // Then we continue. |
| auto *SuccRegion = getRegion(SuccID.ID); |
| if (!LRegion->containsSubregion(SuccRegion)) { |
| LLVM_DEBUG(llvm::dbgs() << " Is not a subregion, " |
| "replacing.\n"); |
| SuccRegion->replacePred(ExitingSubregion->ID, LRegion->ID); |
| if (ExitingSubregion->IsUnknownControlFlowEdgeTail) |
| LRegion->IsUnknownControlFlowEdgeTail = true; |
| // If the successor region is already in this LRegion this returns that |
| // regions index. Otherwise it returns a new index. |
| unsigned Index = LRegion->addSucc(SuccRegion); |
| ExitingSubregion->replaceSucc(SuccID, |
| LoopRegion::SuccessorID(Index, true)); |
| propagateLivenessDownNonLocalSuccessorEdges(ExitingSubregion); |
| continue; |
| } |
| |
| // Otherwise, we know S is in L. If the RPO number of S is less than the |
| // RPO number of ER, then we know that the edge in between them is not a |
| // backedge and thus we do not want to clip the edge. |
| if (SuccRegion->getRPONumber() > ExitingSubregion->getRPONumber()) { |
| LLVM_DEBUG(llvm::dbgs() << " Is a subregion, but not a " |
| "backedge, not removing.\n"); |
| continue; |
| } |
| |
| // If the edge from ER to S is a back edge, we want to clip it and add |
| // exiting subregion to |
| LLVM_DEBUG(llvm::dbgs() << " Is a subregion and a backedge, " |
| "removing.\n"); |
| HasBackedge = true; |
| auto Iter = |
| std::remove(SuccRegion->Preds.begin(), SuccRegion->Preds.end(), |
| ExitingSubregion->getID()); |
| SuccRegion->Preds.erase(Iter); |
| } |
| |
| // If we found a backedge, add ER's ID to LRegion's Backedge list. |
| if (!HasBackedge) { |
| continue; |
| } |
| |
| LRegion->getSubregionData().addBackedgeSubregion(ExitingSubregion->getID()); |
| } |
| } |
| |
| /// The high level algorithm is that via the loop info we already know for |
| /// each subloop: |
| /// |
| /// 1. predecessors. |
| /// 2. header. |
| /// 3. exiting blocks. |
| /// 4. successor blocks. |
| /// |
| /// This means that we can simply fix up those BB regions. |
| /// |
| /// *NOTE* We do not touch the successors/predecessors of the current loop. We |
| /// leave those connections in place for our parent loop to fix up. In the case |
| /// we are the function level loop, these will of course be empty anyways. |
| void |
| LoopRegionFunctionInfo:: |
| initializeLoopFunctionRegion(RegionTy *ParentRegion, |
| iterator_range<LoopInfoTy::iterator> SubLoops) { |
| |
| LLVM_DEBUG(llvm::dbgs() << "Initializing Loop Region " |
| << ParentRegion->getID() << "\n"); |
| // For each subloop... |
| for (auto *SubLoop : SubLoops) { |
| // Grab the region associated with the subloop... |
| auto *SubLoopRegion = getRegion(SubLoop); |
| |
| LLVM_DEBUG(llvm::dbgs() << " Visiting Subloop: " |
| << SubLoopRegion->getID() << "\n"); |
| |
| // First rewrite predecessors of the loop header to point at the loop. |
| auto *SubLoopHeaderRegion = rewriteLoopHeaderPredecessors(SubLoop, |
| SubLoopRegion); |
| |
| // Then rewrite successors of all exits. |
| rewriteLoopExitingBlockSuccessors(SubLoop, SubLoopRegion); |
| |
| // Add the subloop region to the subregion data. |
| ParentRegion->addLoopSubregion(SubLoopRegion, SubLoopHeaderRegion); |
| } |
| |
| // Now that we have finished processing this loop, sort its subregions so that |
| // they are now in RPO order. This works because each BB's ID is its RPO |
| // number and we represent loops by the RPO number of their preheader (with a |
| // flag in the first bit to say to look in the subloop array for the *real* ID |
| // of the loop). |
| // |
| // TODO: Is this necessary? We visit BBs in RPO order. This means that we |
| // should always add BBs in RPO order to subregion lists, no? For now I am |
| // going to sort just to be careful while bringing this up. |
| ParentRegion->getSubregionData().sortSubregions(); |
| } |
| |
| void LoopRegionFunctionInfo:: |
| initializeFunctionRegion(iterator_range<LoopInfoTy::iterator> SubLoops) { |
| // We have already processed all of our subloops, so everything there has |
| // already been properly setup. |
| initializeLoopFunctionRegion(getRegion(F), SubLoops); |
| } |
| |
| /// Recursively visit all the descendants of Parent. If there is a non-local |
| /// successor edge path that points to a dead edge in Parent, mark the |
| /// descendant non-local successor edge as dead. |
| void LoopRegionFunctionInfo:: |
| propagateLivenessDownNonLocalSuccessorEdges(LoopRegion *Parent) { |
| llvm::SmallVector<LoopRegion *, 4> Worklist; |
| Worklist.push_back(Parent); |
| |
| while (Worklist.size()) { |
| LoopRegion *R = Worklist.pop_back_val(); |
| |
| for (unsigned SubregionID : R->getSubregions()) { |
| LoopRegion *Subregion = getRegion(SubregionID); |
| bool ShouldVisit = false; |
| |
| // Make sure we can identify when the subregion has at least one dead |
| // non-local edge and no remaining live edges. In such a case, we need to |
| // remove the subregion from the exiting subregion array of R after the |
| // loop. |
| bool HasDeadNonLocalEdge = false; |
| bool HasNoLiveLocalEdges = true; |
| for (auto &SuccID : Subregion->Succs) { |
| // If the successor is already dead, skip it. We should have visited all |
| // its children when we marked it as dead. |
| if (!SuccID) |
| continue; |
| |
| // We do not care about local IDs, we only process non-local IDs. |
| if (!SuccID->IsNonLocal) |
| continue; |
| |
| // If the non-local successor edge points to a parent successor that is |
| // not dead continue. |
| if (R->Succs[SuccID->ID].hasValue()) { |
| HasNoLiveLocalEdges = false; |
| continue; |
| } |
| |
| // Ok, we found a target! Mark it as dead and make sure that we visit |
| // the subregion's children if it is not a block. |
| HasDeadNonLocalEdge = true; |
| ShouldVisit = true; |
| |
| // This is safe to do since when erasing in a BlotSetVector, we do not |
| // invalidate the iterators. |
| Subregion->Succs.erase(*SuccID); |
| } |
| |
| // Remove Subregion from R's exiting subregion array if Subregion no |
| // longer has /any/ non-local successors. |
| if (HasDeadNonLocalEdge && HasNoLiveLocalEdges) { |
| auto &ExitingSubregions = R->getSubregionData().ExitingSubregions; |
| auto Iter = |
| std::remove(ExitingSubregions.begin(), ExitingSubregions.end(), |
| Subregion->getID()); |
| ExitingSubregions.erase(Iter); |
| } |
| |
| if (ShouldVisit) |
| Worklist.push_back(Subregion); |
| } |
| } |
| } |
| |
| LoopRegionFunctionInfo::RegionTy * |
| LoopRegionFunctionInfo:: |
| getRegionForNonLocalSuccessor(const LoopRegion *Child, unsigned SuccID) const { |
| const LoopRegion *Iter = Child; |
| LoopRegion::SuccessorID Succ = {0, 0}; |
| |
| do { |
| Iter = getRegion(*Iter->getParentID()); |
| Succ = Iter->Succs[SuccID].getValue(); |
| SuccID = Succ.ID; |
| } while (Succ.IsNonLocal); |
| |
| return getRegion(SuccID); |
| } |
| |
| void LoopRegionFunctionInfo::dump() const { |
| print(llvm::outs()); |
| llvm::outs() << "\n"; |
| } |
| |
| void LoopRegionFunctionInfo::print(raw_ostream &os) const { |
| // Print out the information for each loop. |
| std::vector<std::pair<LoopRegion *, LoopRegion *>> RegionWorklist; |
| |
| // Initialize the worklist with the function level region. |
| RegionWorklist.push_back({nullptr, getRegion(F)}); |
| |
| // Vectors that we use to sort our local successor/predecessor indices to make |
| // our output deterministic. |
| llvm::SmallVector<unsigned, 4> SortedPreds; |
| llvm::SmallVector<unsigned, 4> SortedSuccs; |
| |
| // Then go to town... |
| while (RegionWorklist.size()) { |
| LoopRegion *Parent, *R; |
| std::tie(Parent, R) = RegionWorklist.back(); |
| RegionWorklist.pop_back(); |
| |
| os << *R; |
| |
| // If we have a parent, print out its id. This is not strictly necessary, |
| // but it makes it easier to read the output from a dump. |
| if (Parent) |
| os << " parent:" << Parent->getID(); |
| os << "\n"; |
| |
| // Print predecessors. |
| SortedPreds.clear(); |
| for (unsigned Pred : R->Preds) |
| SortedPreds.push_back(Pred); |
| std::sort(SortedPreds.begin(), SortedPreds.end()); |
| os << " (preds"; |
| for (unsigned SID : SortedPreds) { |
| os << "\n "; |
| LoopRegion *PredRegion = getRegion(SID); |
| PredRegion->print(os, true); |
| } |
| os << ")\n"; |
| |
| os << " (succs"; |
| |
| // To make our output deterministic, we sort local successor indices. |
| SortedSuccs.clear(); |
| auto LSuccRange = R->getLocalSuccs(); |
| std::copy(LSuccRange.begin(), LSuccRange.end(), |
| std::back_inserter(SortedSuccs)); |
| std::sort(SortedSuccs.begin(), SortedSuccs.end()); |
| for (unsigned SID : SortedSuccs) { |
| os << "\n "; |
| LoopRegion *SuccRegion = getRegion(SID); |
| SuccRegion->print(os, true); |
| } |
| os << ")\n"; |
| |
| os << " (subregs"; |
| if (!R->isBlock()) { |
| // Go through the subregions. |
| for (unsigned SID : R->getSubregions()) { |
| os << "\n "; |
| LoopRegion *Subregion = getRegion(SID); |
| Subregion->print(os, true); |
| RegionWorklist.push_back({R, Subregion}); |
| } |
| } |
| os << ")\n"; |
| |
| SortedSuccs.clear(); |
| auto NonLSuccs = R->getNonLocalSuccs(); |
| std::copy(NonLSuccs.begin(), NonLSuccs.end(), |
| std::back_inserter(SortedSuccs)); |
| std::sort(SortedSuccs.begin(), SortedSuccs.end()); |
| os << " (non-local-succs"; |
| for (unsigned I : SortedSuccs) { |
| os << "\n (parentindex:" << I << ")"; |
| } |
| os << ")\n"; |
| |
| os << " (exiting-subregs"; |
| if (!R->isBlock()) { |
| llvm::SmallVector<unsigned, 4> ExitingSubregions; |
| auto ExitingSubRegs = R->getExitingSubregions(); |
| std::copy(ExitingSubRegs.begin(), ExitingSubRegs.end(), |
| std::back_inserter(ExitingSubregions)); |
| std::sort(ExitingSubregions.begin(), ExitingSubregions.begin()); |
| for (unsigned SubregionID : ExitingSubregions) { |
| os << "\n "; |
| LoopRegion *Subregion = getRegion(SubregionID); |
| Subregion->print(os, true); |
| } |
| } |
| os << ")\n"; |
| |
| os << " (backedge-regs"; |
| if (!R->isBlock()) { |
| auto BackedgeIDs = R->getBackedgeRegions(); |
| if (!BackedgeIDs.empty()) { |
| for (unsigned BackedgeID : BackedgeIDs) { |
| os << "\n "; |
| LoopRegion *BackedgeRegion = getRegion(BackedgeID); |
| BackedgeRegion->print(os, true); |
| } |
| } |
| } |
| os << "))\n"; |
| } |
| } |
| |
| //===----------------------------------------------------------------------===// |
| // Graphing Support |
| //===----------------------------------------------------------------------===// |
| |
| #ifndef NDEBUG |
| |
| /// A lot of the code below is unfortunate and due to the inflexibility of |
| /// GraphUtils. But you gotta do what you gotta do. |
| namespace { |
| |
| struct LoopRegionWrapper; |
| |
| struct LoopRegionFunctionInfoGrapherWrapper { |
| LoopRegionFunctionInfo *FuncInfo; |
| std::vector<LoopRegionWrapper> Data; |
| }; |
| |
| struct alledge_iterator; |
| |
| struct LoopRegionWrapper { |
| LoopRegionFunctionInfoGrapherWrapper &FuncInfo; |
| LoopRegion *Region; |
| |
| LoopRegionWrapper *getParent() const { |
| unsigned ParentIndex = *Region->getParentID(); |
| return &FuncInfo.Data[ParentIndex]; |
| } |
| |
| alledge_iterator begin(); |
| alledge_iterator end(); |
| }; |
| |
| /// An iterator on Regions that first iterates over subregions and then over |
| /// successors. |
| struct alledge_iterator |
| : std::iterator<std::forward_iterator_tag, LoopRegionWrapper> { |
| LoopRegionWrapper *Wrapper; |
| LoopRegion::subregion_iterator SubregionIter; |
| LoopRegion::backedge_iterator BackedgeIter; |
| |
| using SuccIterTy = |
| OptionalTransformIterator<LoopRegion::const_succ_iterator, |
| LoopRegion::SuccessorID::ToLiveSucc>; |
| SuccIterTy SuccIter; |
| |
| alledge_iterator(LoopRegionWrapper *w, |
| swift::LoopRegion::subregion_iterator subregioniter, |
| LoopRegion::const_succ_iterator succiter, |
| LoopRegion::backedge_iterator backedgeiter) |
| : Wrapper(w), SubregionIter(subregioniter), |
| BackedgeIter(backedgeiter), |
| SuccIter(succiter, w->Region->succ_end(), |
| LoopRegion::SuccessorID::ToLiveSucc()) {} |
| |
| // This is not efficient, but this is graphing code... |
| SuccIterTy getSuccEnd() const { |
| return SuccIterTy(Wrapper->Region->succ_end(), Wrapper->Region->succ_end(), |
| LoopRegion::SuccessorID::ToLiveSucc()); |
| } |
| |
| bool isSubregion() const { |
| return SubregionIter != Wrapper->Region->subregion_end(); |
| } |
| |
| bool isNonLocalEdge() const { |
| // If we are not a subregion... |
| if (isSubregion()) |
| return false; |
| |
| // Then if succ iterator is not succ end, we are a non local edge if that |
| // value is Non Local. |
| return getSuccEnd() != SuccIter && (*SuccIter).IsNonLocal; |
| } |
| |
| bool isBackEdge() const { |
| if (isSubregion()) |
| return false; |
| // If our successor iterator has reached the end of the successor list. |
| return getSuccEnd() == SuccIter; |
| } |
| |
| LoopRegionWrapper *operator*() const { |
| // If we have a subregion... return the wrapper for it. |
| if (isSubregion()) { |
| return &Wrapper->FuncInfo.Data[*SubregionIter]; |
| } |
| |
| // If we have a backedge... return the wrapper for that. |
| if (isBackEdge()) { |
| return &Wrapper->FuncInfo.Data[*BackedgeIter]; |
| } |
| |
| // If we have a non-local id, just return the parent region's data. |
| if ((*SuccIter).IsNonLocal) |
| return &Wrapper->FuncInfo.Data[*(Wrapper->Region->getParentID())]; |
| // Otherwise return the data associated with this successor. |
| return &Wrapper->FuncInfo.Data[(*SuccIter).ID]; |
| } |
| |
| alledge_iterator &operator++() { |
| // If we are still a subregion, increment the SubregionIter and return. |
| if (isSubregion()) { |
| ++SubregionIter; |
| return *this; |
| } |
| |
| // Make sure that we skip past any dead successors. If after skipping dead |
| // successors, if our SuccIter is not end, then return. We have a true |
| // successor. |
| if (SuccIter != getSuccEnd()) { |
| ++SuccIter; |
| return *this; |
| } |
| |
| // Ok, now we know that we have a back edge region. Increment the backedge |
| // region. |
| ++BackedgeIter; |
| |
| return *this; |
| } |
| |
| alledge_iterator operator++(int) { |
| alledge_iterator copy = *this; |
| ++copy; |
| return copy; |
| } |
| |
| bool operator==(alledge_iterator rhs) { |
| if (Wrapper->Region != rhs.Wrapper->Region) |
| return false; |
| if (SubregionIter != rhs.SubregionIter) |
| return false; |
| if (SuccIter != rhs.SuccIter) |
| return false; |
| if (BackedgeIter.hasValue() != rhs.BackedgeIter.hasValue()) |
| return false; |
| return BackedgeIter == rhs.BackedgeIter; |
| } |
| |
| bool operator!=(alledge_iterator rhs) { return !(*this == rhs); } |
| }; |
| |
| } // end anonymous namespace |
| |
| alledge_iterator LoopRegionWrapper::begin() { |
| return alledge_iterator(this, Region->subregion_begin(), Region->succ_begin(), |
| Region->backedge_begin()); |
| } |
| |
| alledge_iterator LoopRegionWrapper::end() { |
| return alledge_iterator(this, Region->subregion_end(), Region->succ_end(), |
| Region->backedge_end()); |
| } |
| |
| namespace llvm { |
| template <> struct GraphTraits<LoopRegionWrapper> { |
| using ChildIteratorType = alledge_iterator; |
| typedef LoopRegionWrapper *NodeRef; |
| |
| static NodeRef getEntryNode(NodeRef BB) { return BB; } |
| |
| static ChildIteratorType child_begin(NodeRef N) { return N->begin(); } |
| static ChildIteratorType child_end(NodeRef N) { return N->end(); } |
| }; |
| |
| template <> |
| struct GraphTraits<LoopRegionFunctionInfoGrapherWrapper *> |
| : public GraphTraits<LoopRegionWrapper> { |
| using GraphType = LoopRegionFunctionInfoGrapherWrapper; |
| typedef LoopRegionWrapper *NodeRef; |
| |
| static NodeRef getEntryNode(GraphType *F) { return &F->Data[0]; } |
| |
| using nodes_iterator = |
| pointer_iterator<std::vector<LoopRegionWrapper>::iterator>; |
| |
| static nodes_iterator nodes_begin(GraphType *F) { |
| return nodes_iterator(F->Data.begin()); |
| } |
| static nodes_iterator nodes_end(GraphType *F) { |
| return nodes_iterator(F->Data.end()); |
| } |
| static unsigned size(GraphType *F) { return F->Data.size(); } |
| }; |
| |
| } // end namespace llvm |
| |
| static llvm::cl::opt<unsigned> |
| MaxColumns("view-loop-regions-max-columns", llvm::cl::init(80), |
| llvm::cl::desc("Maximum width of a printed node")); |
| |
| namespace { |
| enum class LongLineBehavior { None, Truncate, Wrap }; |
| } // end anonymous namespace |
| static llvm::cl::opt<LongLineBehavior> LLBehavior( |
| "view-loop-regions-long-line-behavior", |
| llvm::cl::init(LongLineBehavior::Truncate), |
| llvm::cl::desc("Behavior when line width is greater than the " |
| "value provided my -view-loop-regions-max-columns " |
| "option"), |
| llvm::cl::values( |
| clEnumValN(LongLineBehavior::None, "none", "Print everything"), |
| clEnumValN(LongLineBehavior::Truncate, "truncate", |
| "Truncate long lines"), |
| clEnumValN(LongLineBehavior::Wrap, "wrap", "Wrap long lines"))); |
| |
| static llvm::cl::opt<bool> RemoveUseListComments( |
| "view-loop-regions-remove-use-list-comments", llvm::cl::init(false), |
| llvm::cl::desc("Should use list comments be removed")); |
| |
| namespace llvm { |
| template <> |
| struct DOTGraphTraits<LoopRegionFunctionInfoGrapherWrapper *> |
| : public DefaultDOTGraphTraits { |
| |
| DOTGraphTraits(bool isSimple = false) : DefaultDOTGraphTraits(isSimple) {} |
| |
| static std::string |
| getGraphName(const LoopRegionFunctionInfoGrapherWrapper *F) { |
| return "Loop Regions for '" + F->FuncInfo->getFunction()->getName().str() + |
| "' function"; |
| } |
| |
| static std::string |
| getSimpleNodeLabel(LoopRegionWrapper *Node, |
| const LoopRegionFunctionInfoGrapherWrapper *F) { |
| std::string OutStr; |
| raw_string_ostream OSS(OutStr); |
| Node->Region->printName(OSS); |
| return OSS.str(); |
| } |
| |
| static std::string |
| getCompleteNodeLabel(LoopRegionWrapper *Node, |
| const LoopRegionFunctionInfoGrapherWrapper *F) { |
| std::string Tmp0; |
| raw_string_ostream OSS(Tmp0); |
| Node->Region->printName(OSS); |
| if (Node->Region->isUnknownControlFlowEdgeHead()) |
| OSS << " Unknown CF Head"; |
| if (Node->Region->isUnknownControlFlowEdgeTail()) |
| OSS << " Unknown CF Tail"; |
| if (!Node->Region->isBlock()) |
| return OSS.str(); |
| OSS << "\n"; |
| std::string Tmp1; |
| raw_string_ostream OSS2(Tmp1); |
| OSS2 << *Node->Region->getBlock(); |
| std::string OutStr = OSS2.str(); |
| if (OutStr[0] == '\n') |
| OutStr.erase(OutStr.begin()); |
| |
| // Process string output to make it nicer... |
| unsigned ColNum = 0; |
| unsigned LastSpace = 0; |
| for (unsigned i = 0; i != OutStr.length(); ++i) { |
| if (OutStr[i] == '\n') { // Left justify |
| OutStr[i] = '\\'; |
| OutStr.insert(OutStr.begin() + i + 1, 'l'); |
| ColNum = 0; |
| LastSpace = 0; |
| } else if (RemoveUseListComments && OutStr[i] == '/' && |
| i != (OutStr.size() - 1) && OutStr[i + 1] == '/') { |
| unsigned Idx = OutStr.find('\n', i + 1); // Find end of line |
| OutStr.erase(OutStr.begin() + i, OutStr.begin() + Idx); |
| --i; |
| |
| } else if (ColNum == MaxColumns) { // Handle long lines. |
| |
| if (LLBehavior == LongLineBehavior::Wrap) { |
| if (!LastSpace) |
| LastSpace = i; |
| OutStr.insert(LastSpace, "\\l..."); |
| ColNum = i - LastSpace; |
| LastSpace = 0; |
| i += 3; // The loop will advance 'i' again. |
| } else if (LLBehavior == LongLineBehavior::Truncate) { |
| unsigned Idx = OutStr.find('\n', i + 1); // Find end of line |
| OutStr.erase(OutStr.begin() + i, OutStr.begin() + Idx); |
| --i; |
| } |
| |
| // Else keep trying to find a space. |
| } else |
| ++ColNum; |
| if (OutStr[i] == ' ') |
| LastSpace = i; |
| } |
| |
| return OSS.str() + OutStr; |
| } |
| |
| std::string getNodeLabel(LoopRegionWrapper *Node, |
| const LoopRegionFunctionInfoGrapherWrapper *Graph) { |
| if (isSimple()) |
| return getSimpleNodeLabel(Node, Graph); |
| else |
| return getCompleteNodeLabel(Node, Graph); |
| } |
| |
| static bool hasEdgeDestLabels() { return true; } |
| |
| static unsigned numEdgeDestLabels(LoopRegionWrapper *Node) { |
| return std::distance(Node->begin(), Node->end()); |
| } |
| |
| static std::string getEdgeDestLabel(LoopRegionWrapper *Node, unsigned i) { |
| alledge_iterator Iter = Node->begin(); |
| std::advance(Iter, i); |
| return getEdgeSourceLabel(Node, Iter); |
| } |
| |
| static std::string getEdgeSourceLabel(LoopRegionWrapper *Node, |
| alledge_iterator I) { |
| if (I.isNonLocalEdge()) |
| return "NLSuc"; |
| if (I.isSubregion()) |
| return "Sub"; |
| if (I.isBackEdge()) |
| return "B"; |
| return "LSuc"; |
| } |
| |
| /// If you want to override the dot attributes printed for a particular |
| /// edge, override this method. |
| static std::string |
| getEdgeAttributes(const LoopRegionWrapper *Node, alledge_iterator EI, |
| const LoopRegionFunctionInfoGrapherWrapper *Graph) { |
| if (EI.isSubregion()) |
| return "color=red"; |
| if (EI.isNonLocalEdge()) |
| return "color=blue"; |
| if (EI.isBackEdge()) |
| return "color=darkgreen"; |
| return ""; |
| } |
| |
| static bool edgeTargetsEdgeSource(const LoopRegionWrapper *Node, |
| alledge_iterator I) { |
| return I.isNonLocalEdge(); |
| } |
| |
| /// If edgeTargetsEdgeSource returns true, this method is called to determine |
| /// which outgoing edge of Node is the target of this edge. |
| /// |
| /// Currently this can only happen given a non-local edge in which case we |
| /// want the non-local edge to point at its parent's successor edge. |
| static alledge_iterator getEdgeTarget(LoopRegionWrapper *Node, |
| alledge_iterator I) { |
| assert(I.isNonLocalEdge() && "This should only be called given a non " |
| "local edge"); |
| auto *ParentRegion = Node->getParent(); |
| auto SuccIter = ParentRegion->Region->succ_begin(); |
| std::advance(SuccIter, (*I.SuccIter).ID); |
| return alledge_iterator(ParentRegion, ParentRegion->Region->subregion_end(), |
| SuccIter, ParentRegion->Region->backedge_begin()); |
| } |
| }; |
| } // namespace llvm |
| |
| static llvm::cl::opt<std::string> TargetFunction( |
| "view-loop-regions-only-for-function", llvm::cl::init(""), |
| llvm::cl::desc("Only print out the loop regions for this function")); |
| #endif |
| |
| void LoopRegionFunctionInfo::viewLoopRegions() const { |
| // This is a no-op when asserts are disabled. |
| #ifndef NDEBUG |
| // If we have a target function, only print that function out. |
| if (!TargetFunction.empty() && !(F->getName().str() == TargetFunction)) |
| return; |
| LoopRegionFunctionInfoGrapherWrapper Wrapper; |
| Wrapper.FuncInfo = const_cast<LoopRegionFunctionInfo *>(this); |
| for (auto *R : IDToRegionMap) { |
| Wrapper.Data.push_back({Wrapper, R}); |
| } |
| llvm::ViewGraph(&Wrapper, "loop region function info" + F->getName().str()); |
| #endif |
| } |
| |
| //===----------------------------------------------------------------------===// |
| // LoopRegionAnalysis |
| //===----------------------------------------------------------------------===// |
| |
| void LoopRegionAnalysis::initialize(SILPassManager *PM) { |
| SLA = PM->getAnalysis<SILLoopAnalysis>(); |
| POA = PM->getAnalysis<PostOrderAnalysis>(); |
| } |
| |
| //===----------------------------------------------------------------------===// |
| // Main Entry Point |
| //===----------------------------------------------------------------------===// |
| |
| SILAnalysis *swift::createLoopRegionAnalysis(SILModule *M) { |
| return new LoopRegionAnalysis(M); |
| } |