ScopInfo: Pass domain constraints through error blocks

Previously, we just skipped error blocks during scop construction. With
this change we make sure we can construct domains for error blocks such that
these domains can be forwarded to subsequent basic blocks.

This change ensures that basic blocks that post-dominate and are dominated by
a basic block that branches to an error condition have the very same iteration
domain as the branching basic block. Before, this change we would construct
a domain that excludes all error conditions. Such domains could become _very_
complex and were undesirable to build.

Another solution would have been to drop these constraints using a
dominance/post-dominance check instead of modeling the error blocks. Such
a solution could also work in case of unreachable statements or infinite
loops in the scop. However, as we currently (to my believe incorrectly) model
unreachable basic blocks in the post-dominance tree, such a solution is not
yet feasible and requires first a change to LLVM's post-dominance tree
construction.

This commit addresses the most sever compile time issue reported in:
http://llvm.org/PR25458

llvm-svn: 252713

2 files changed, 18 insertions, 17 deletions

diff --git a/polly/lib/Analysis/ScopDetection.cpp b/polly/lib/Analysis/ScopDetection.cpp
index 889d2989ee9..14f9e3e08de 100644
--- a/polly/lib/Analysis/ScopDetection.cpp
+++ b/polly/lib/Analysis/ScopDetection.cpp
@@ -402,11 +402,15 @@ bool ScopDetection::isValidBranch(BasicBlock &BB, BranchInst *BI,
 }
 
 bool ScopDetection::isValidCFG(BasicBlock &BB, bool IsLoopBranch,
+                               bool AllowUnreachable,
                                DetectionContext &Context) const {
   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)
     return true;
@@ -768,7 +772,7 @@ bool ScopDetection::canUseISLTripCount(Loop *L,
   L->getLoopLatches(LoopControlBlocks);
   L->getExitingBlocks(LoopControlBlocks);
   for (BasicBlock *ControlBB : LoopControlBlocks) {
-    if (!isValidCFG(*ControlBB, true, Context))
+    if (!isValidCFG(*ControlBB, true, false, Context))
       return false;
   }
 
@@ -977,12 +981,17 @@ bool ScopDetection::allBlocksValid(DetectionContext &Context) const {
   }
 
   for (BasicBlock *BB : CurRegion.blocks()) {
-    // Do not check exception blocks as we will never include them in the SCoP.
-    if (isErrorBlock(*BB, CurRegion, *LI, *DT))
-      continue;
+    bool IsErrorBlock = isErrorBlock(*BB, CurRegion, *LI, *DT);
 
-    if (!isValidCFG(*BB, false, Context) && !KeepGoing)
+    // Also check exception blocks (and possibly register them as non-affine
+    // regions). Even though exception blocks are not modeled, we use them
+    // to forward-propagate domain constraints during ScopInfo construction.
+    if (!isValidCFG(*BB, false, IsErrorBlock, Context) && !KeepGoing)
       return false;
+
+    if (IsErrorBlock)
+      continue;
+
     for (BasicBlock::iterator I = BB->begin(), E = --BB->end(); I != E; ++I)
       if (!isValidInstruction(*I, Context) && !KeepGoing)
         return false;
diff --git a/polly/lib/Analysis/ScopInfo.cpp b/polly/lib/Analysis/ScopInfo.cpp
index 4920b118187..3f59459ce20 100644
--- a/polly/lib/Analysis/ScopInfo.cpp
+++ b/polly/lib/Analysis/ScopInfo.cpp
@@ -1940,23 +1940,15 @@ void Scop::buildDomainsWithBranchConstraints(Region *R) {
       }
     }
 
-    // Error blocks are assumed not to be executed. Therefor they are not
-    // checked properly in the ScopDetection. Any attempt to generate control
-    // conditions from them might result in a crash. However, this is only true
-    // for the first step of the domain generation (this function) where we
-    // push the control conditions of a block to the successors. In the second
-    // step (propagateDomainConstraints) we only receive domain constraints from
-    // the predecessors and can therefor look at the domain of a error block.
-    // That allows us to generate the assumptions needed for them not to be
-    // executed at runtime.
-    if (containsErrorBlock(RN, getRegion(), LI, DT)) {
+    if (containsErrorBlock(RN, getRegion(), LI, DT))
       HasErrorBlock = true;
-      continue;
-    }
 
     BasicBlock *BB = getRegionNodeBasicBlock(RN);
     TerminatorInst *TI = BB->getTerminator();
 
+    if (isa<UnreachableInst>(TI))
+      continue;
+
     isl_set *Domain = DomainMap.lookup(BB);
     if (!Domain) {
       DEBUG(dbgs() << "\tSkip: " << BB->getName()