[Polly] Add handling of Top Level Regions

[lksbhm]

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.

[grosser]

Very cool! I will have a look later. Could you possibly add some test cases?

[lksbhm]

I extended the full-function.ll testcase to reflect that we now analyze the TLR.
Since the testcase was previously failing, this edit also adds a patch for Scop::getRelativeLoopDepth: It made use of Region::outermostLoopInRegion which has an unintuitive corner case for TLRs (which is documented), namely that it always returns nullptr.

[grosser]

LGTM, Philip feel free to commit.

polly/trunk/lib/Analysis/ScopBuilder.cpp

for (auto &Inst : *BB) {
              VirtDef.getKind() == VirtualUse::Hoisted);
     }
   }
 
   if (S->hasSingleExitEdge())
     return;
 
   // PHINodes in the SCoP region's exit block are also uses to be checked.
+  if (!S->getRegion().isTopLevelRegion()) {
     for (auto &Inst : *S->getRegion().getExit()) {
       if (!isa<PHINode>(Inst))
         break;
 
       for (auto &Op : Inst.operands())
         verifyUse(S, Op, LI);
     }
   }
+}
 #endif
 
 void ScopBuilder::buildScop(Region &R, AssumptionCache &AC) {
   scop.reset(new Scop(R, SE, LI, *SD.getDetectionContext(&R)));
 
   buildStmts(R);
   buildAccessFunctions(R);
 
   // In case the region does not have an exiting block we will later (during
   // code generation) split the exit block. This will move potential PHI nodes
   // from the current exit block into the new region exiting block. Hence, PHI
   // nodes that are at this point not part of the region will be.
   // 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);
 
   // Create memory accesses for global reads since all arrays are now known.
   auto *AF = SE.getConstant(IntegerType::getInt64Ty(SE.getContext()), 0);
   for (auto *GlobalRead : GlobalReads)
     for (auto *BP : ArrayBasePointers)
       addArrayAccess(MemAccInst(GlobalRead), MemoryAccess::READ, BP,

polly/trunk/lib/Analysis/ScopDetection.cpp

bool ScopDetection::isValidCFG(BasicBlock &BB, bool IsLoopBranch,
   Region &CurRegion = Context.CurRegion;
 
   TerminatorInst *TI = BB.getTerminator();
 
   if (AllowUnreachable && isa<UnreachableInst>(TI))
     return true;
 
   // Return instructions are only valid if the region is the top level region.
-  if (isa<ReturnInst>(TI) && !CurRegion.getExit() && TI->getNumOperands() == 0)
+  if (isa<ReturnInst>(TI) && CurRegion.isTopLevelRegion())
     return true;
 
   Value *Condition = getConditionFromTerminator(TI);
 
   if (!Condition)
     return invalid<ReportInvalidTerminator>(Context, /*Assert=*/true, &BB);
 
   // UndefValue is not allowed as condition.
bool ScopDetection::isProfitableRegion(DetectionContext &Context) const {
   return invalid<ReportUnprofitable>(Context, /*Assert=*/true, &CurRegion);
 }
 
 bool ScopDetection::isValidRegion(DetectionContext &Context) const {
   Region &CurRegion = Context.CurRegion;
 
   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<UnreachableInst>(CurRegion.getExit()->getTerminator())) {
+  if (CurRegion.getExit() &&
+      isa<UnreachableInst>(CurRegion.getExit()->getTerminator())) {
     DEBUG(dbgs() << "Unreachable in exit\n");
     return invalid<ReportUnreachableInExit>(Context, /*Assert=*/true,
                                             CurRegion.getExit(), DbgLoc);
   }
 
   if (!CurRegion.getEntry()->getName().count(OnlyRegion)) {
     DEBUG({
       dbgs() << "Region entry does not match -polly-region-only";

polly/trunk/lib/Analysis/ScopInfo.cpp

 
 ScopStmt *Scop::getStmtFor(Region *R) const {
   ScopStmt *Stmt = getStmtFor(R->getEntry());
   assert(!Stmt || Stmt->getRegion() == R);
   return Stmt;
 }
 
 int Scop::getRelativeLoopDepth(const Loop *L) const {
-  Loop *OuterLoop =
-      L ? R.outermostLoopInRegion(const_cast<Loop *>(L)) : nullptr;
-  if (!OuterLoop)
+  if (!L || !R.contains(L))
     return -1;
+  // 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<Loop *>(L));
+    assert(OuterLoop);
     return L->getLoopDepth() - OuterLoop->getLoopDepth();
   }
+}
 
 ScopArrayInfo *Scop::getArrayInfoByName(const std::string BaseName) {
   for (auto &SAI : arrays()) {
     if (SAI->getName() == BaseName)
       return SAI;
   }
   return nullptr;
 }

polly/trunk/lib/Support/ScopHelper.cpp

if (isa<UnreachableInst>(BB.getTerminator()))
     return true;
 
   if (LI.isLoopHeader(&BB))
     return false;
 
   // Basic blocks that are always executed are not considered error blocks,
   // as their execution can not be a rare event.
   bool DominatesAllPredecessors = true;
+  if (R.isTopLevelRegion()) {
+    for (BasicBlock &I : *R.getEntry()->getParent())
+      if (isa<ReturnInst>(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;
 
   // FIXME: This is a simple heuristic to determine if the load is executed
   //        in a conditional. However, we actually would need the control
   //        condition, i.e., the post dominance frontier. Alternatively we
   //        could walk up the dominance tree until we find a block that is

polly/trunk/test/ScopInfo/full-function.ll

 ; RUN: opt %loadPolly -polly-scops -analyze -polly-detect-full-functions < %s \
 ; RUN: | FileCheck %s -check-prefix=FULL
 ; 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 :=
 ; FULL-NEXT:             [p] -> { Stmt_loop_1[i0] : p = 42 and 0 <= i0 <= 1025 };
 ; FULL-NEXT:         Schedule :=
 ; FULL-NEXT:             [p] -> { Stmt_loop_1[i0] -> [1, i0] };
 ; FULL-NEXT:         MustWriteAccess := [Reduction Type: NONE] [Scalar: 0]
 ; FULL-NEXT:             [p] -> { Stmt_loop_1[i0] -> MemRef_A[0] };
 ; FULL-NEXT:  Stmt_loop_2
 ; FULL-NEXT:         Domain :=
 ; FULL-NEXT:             [p] -> { Stmt_loop_2[i0] : 0 <= i0 <= 1025 and (p >= 43 or p <= 41) };
 ; FULL-NEXT:         Schedule :=
 ; FULL-NEXT:             [p] -> { Stmt_loop_2[i0] -> [0, i0] : p >= 43 or p <= 41 };
 ; FULL-NEXT:         MustWriteAccess := [Reduction Type: NONE] [Scalar: 0]
 ; 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 :=
 ; WITHOUT-FULL-NEXT:                { Stmt_loop_2[i0] : 0 <= i0 <= 1025 };
 ; WITHOUT-FULL-NEXT:            Schedule :=
 ; WITHOUT-FULL-NEXT:                { Stmt_loop_2[i0] -> [i0] };
 ; WITHOUT-FULL-NEXT:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
 ; 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 :=
 ; WITHOUT-FULL-NEXT:                { Stmt_loop_1[i0] : 0 <= i0 <= 1025 };
 ; WITHOUT-FULL-NEXT:            Schedule :=
 ; WITHOUT-FULL-NEXT:                { Stmt_loop_1[i0] -> [i0] };
 ; WITHOUT-FULL-NEXT:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
 ; WITHOUT-FULL-NEXT:                { Stmt_loop_1[i0] -> MemRef_A[0] };