From 6547ff25af2a41e55c18f7d65f566ba3b5a954ca Mon Sep 17 00:00:00 2001 From: Philip Pfaffe Date: Wed, 24 May 2017 18:39:39 +0000 Subject: [PATCH] [Polly] Add handling of Top Level Regions Summary: My goal is to make the newly added `AllowWholeFunctions` options more usable/powerful. The changes to ScopBuilder.cpp are exclusively checks to prevent `Region.getExit()` from being dereferenced, since Top Level Regions (TLRs) don't have an exit block. In ScopDetection's `isValidCFG`, I removed a check that disallowed ReturnInstructions to have return values. This might of course have been intentional, so I would welcome your feedback on this and maybe a small explanation why return values are forbidden. Maybe it can be done but needs more changes elsewhere? The remaining changes in ScopDetection are simply to consider the AllowWholeFunctions option in more places, i.e. allow TLRs when it is set and once again avoid derefererncing `getExit()` if it doesn't exist. Finally, in ScopHelper.cpp I extended `polly::isErrorBlock` to handle regions without exit blocks as well: The original check was if a given BasicBlock dominates all predecessors of the exit block. Therefore I do the same for TLRs by regarding all BasicBlocks terminating with a ReturnInst as predecessors of a "virtual" function exit block. Patch by: Lukas Boehm Reviewers: philip.pfaffe, grosser, Meinersbur Reviewed By: grosser Subscribers: pollydev, llvm-commits, bollu Tags: #polly Differential Revision: https://reviews.llvm.org/D33411 git-svn-id: https://llvm.org/svn/llvm-project/polly/trunk@303790 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Analysis/ScopBuilder.cpp | 14 ++++++++------ lib/Analysis/ScopDetection.cpp | 7 ++++--- lib/Analysis/ScopInfo.cpp | 14 ++++++++++---- lib/Support/ScopHelper.cpp | 12 +++++++++--- test/ScopInfo/full-function.ll | 3 +++ 5 files changed, 34 insertions(+), 16 deletions(-) diff --git a/lib/Analysis/ScopBuilder.cpp b/lib/Analysis/ScopBuilder.cpp index b7c9c659..8b207560 100644 --- a/lib/Analysis/ScopBuilder.cpp +++ b/lib/Analysis/ScopBuilder.cpp @@ -894,12 +894,14 @@ static void verifyUses(Scop *S, LoopInfo &LI, DominatorTree &DT) { return; // PHINodes in the SCoP region's exit block are also uses to be checked. - for (auto &Inst : *S->getRegion().getExit()) { - if (!isa(Inst)) - break; + if (!S->getRegion().isTopLevelRegion()) { + for (auto &Inst : *S->getRegion().getExit()) { + if (!isa(Inst)) + break; - for (auto &Op : Inst.operands()) - verifyUse(S, Op, LI); + for (auto &Op : Inst.operands()) + verifyUse(S, Op, LI); + } } } #endif @@ -917,7 +919,7 @@ void ScopBuilder::buildScop(Region &R, AssumptionCache &AC) { // To handle these PHI nodes later we will now model their operands as scalar // accesses. Note that we do not model anything in the exit block if we have // an exiting block in the region, as there will not be any splitting later. - if (!scop->hasSingleExitEdge()) + if (!R.isTopLevelRegion() && !scop->hasSingleExitEdge()) buildAccessFunctions(*R.getExit(), nullptr, /* IsExitBlock */ true); diff --git a/lib/Analysis/ScopDetection.cpp b/lib/Analysis/ScopDetection.cpp index a5fcc163..d1d6360a 100644 --- a/lib/Analysis/ScopDetection.cpp +++ b/lib/Analysis/ScopDetection.cpp @@ -578,7 +578,7 @@ bool ScopDetection::isValidCFG(BasicBlock &BB, bool IsLoopBranch, return true; // Return instructions are only valid if the region is the top level region. - if (isa(TI) && !CurRegion.getExit() && TI->getNumOperands() == 0) + if (isa(TI) && CurRegion.isTopLevelRegion()) return true; Value *Condition = getConditionFromTerminator(TI); @@ -1485,13 +1485,14 @@ bool ScopDetection::isValidRegion(DetectionContext &Context) const { DEBUG(dbgs() << "Checking region: " << CurRegion.getNameStr() << "\n\t"); - if (CurRegion.isTopLevelRegion()) { + if (!AllowFullFunction && CurRegion.isTopLevelRegion()) { DEBUG(dbgs() << "Top level region is invalid\n"); return false; } DebugLoc DbgLoc; - if (isa(CurRegion.getExit()->getTerminator())) { + if (CurRegion.getExit() && + isa(CurRegion.getExit()->getTerminator())) { DEBUG(dbgs() << "Unreachable in exit\n"); return invalid(Context, /*Assert=*/true, CurRegion.getExit(), DbgLoc); diff --git a/lib/Analysis/ScopInfo.cpp b/lib/Analysis/ScopInfo.cpp index 4be93387..addb3383 100644 --- a/lib/Analysis/ScopInfo.cpp +++ b/lib/Analysis/ScopInfo.cpp @@ -4824,11 +4824,17 @@ ScopStmt *Scop::getStmtFor(Region *R) const { } int Scop::getRelativeLoopDepth(const Loop *L) const { - Loop *OuterLoop = - L ? R.outermostLoopInRegion(const_cast(L)) : nullptr; - if (!OuterLoop) + if (!L || !R.contains(L)) return -1; - return L->getLoopDepth() - OuterLoop->getLoopDepth(); + // outermostLoopInRegion always returns nullptr for top level regions + if (R.isTopLevelRegion()) { + // LoopInfo's depths start at 1, we start at 0 + return L->getLoopDepth() - 1; + } else { + Loop *OuterLoop = R.outermostLoopInRegion(const_cast(L)); + assert(OuterLoop); + return L->getLoopDepth() - OuterLoop->getLoopDepth(); + } } ScopArrayInfo *Scop::getArrayInfoByName(const std::string BaseName) { diff --git a/lib/Support/ScopHelper.cpp b/lib/Support/ScopHelper.cpp index d288536d..27207ec2 100644 --- a/lib/Support/ScopHelper.cpp +++ b/lib/Support/ScopHelper.cpp @@ -380,9 +380,15 @@ bool polly::isErrorBlock(BasicBlock &BB, const Region &R, LoopInfo &LI, // Basic blocks that are always executed are not considered error blocks, // as their execution can not be a rare event. bool DominatesAllPredecessors = true; - for (auto Pred : predecessors(R.getExit())) - if (R.contains(Pred) && !DT.dominates(&BB, Pred)) - DominatesAllPredecessors = false; + if (R.isTopLevelRegion()) { + for (BasicBlock &I : *R.getEntry()->getParent()) + if (isa(I.getTerminator()) && !DT.dominates(&BB, &I)) + DominatesAllPredecessors = false; + } else { + for (auto Pred : predecessors(R.getExit())) + if (R.contains(Pred) && !DT.dominates(&BB, Pred)) + DominatesAllPredecessors = false; + } if (DominatesAllPredecessors) return false; diff --git a/test/ScopInfo/full-function.ll b/test/ScopInfo/full-function.ll index 23790085..b91a5178 100644 --- a/test/ScopInfo/full-function.ll +++ b/test/ScopInfo/full-function.ll @@ -3,6 +3,7 @@ ; RUN: opt %loadPolly -polly-scops -analyze < %s \ ; RUN: | FileCheck %s -check-prefix=WITHOUT-FULL +; FULL: Region: %bb---FunctionExit ; FULL: Statements { ; FULL-NEXT: Stmt_loop_1 ; FULL-NEXT: Domain := @@ -20,6 +21,7 @@ ; FULL-NEXT: [p] -> { Stmt_loop_2[i0] -> MemRef_A[0] }; ; FULL-NEXT: } +; WITHOUT-FULL: Region: %loop.2---%merge ; WITHOUT-FULL: Statements { ; WITHOUT-FULL-NEXT: Stmt_loop_2 ; WITHOUT-FULL-NEXT: Domain := @@ -30,6 +32,7 @@ ; WITHOUT-FULL-NEXT: { Stmt_loop_2[i0] -> MemRef_A[0] }; ; WITHOUT-FULL-NEXT: } +; WITHOUT-FULL: Region: %loop.1---%merge ; WITHOUT-FULL: Statements { ; WITHOUT-FULL-NEXT: Stmt_loop_1 ; WITHOUT-FULL-NEXT: Domain := -- 2.11.4.GIT