[Polly] Allow PHI nodes in exit block

[Meinersbur]

Summary

Remove the check for valid exit blocks, which can now be handled downstream.

[grosser]

LGTM, but please merge with other patches. We do not want to commit incomplete patches that leave Polly in a broken state. (This patch alone without backend changes will trigger assertion failures when run on code with phi nodes in exit)

[Meinersbur]

Merged into D11869

[Meinersbur]

Merged into D11870, not D11869

include/polly/ScopDetection.h

private:
 
   /// @brief Check if all basic block in the region are valid.
   ///
   /// @param Context The context of scop detection.
   ///
   /// @return True if all blocks in R are valid, false otherwise.
   bool allBlocksValid(DetectionContext &Context) const;
 
-  /// @brief Check the exit block of a region is valid.
-  ///
-  /// @param Context The context of scop detection.
-  ///
-  /// @return True if the exit of R is valid, false otherwise.
-  bool isValidExit(DetectionContext &Context) const;
-
   /// @brief Check if a region is a Scop.
   ///
   /// @param Context The context of scop detection.
   ///
   /// @return True if R is a Scop, false otherwise.
   bool isValidRegion(DetectionContext &Context) const;
 
   /// @brief Check if a call instruction can be part of a Scop.

lib/Analysis/ScopDetection.cpp

Region *ScopDetection::expandRegion(Region &R) {
   while (ExpandedRegion) {
     DetectionContext Context(
         *ExpandedRegion, *AA, NonAffineSubRegionMap[ExpandedRegion.get()],
         BoxedLoopsMap[ExpandedRegion.get()], false /* verifying */);
     DEBUG(dbgs() << "\t\tTrying " << ExpandedRegion->getNameStr() << "\n");
     // Only expand when we did not collect errors.
 
     // Check the exit first (cheap)
-    if (isValidExit(Context) && !Context.Log.hasErrors()) {
+    if (!Context.Log.hasErrors()) {
       // If the exit is valid check all blocks
       //  - if true, a valid region was found => store it + keep expanding
       //  - if false, .tbd. => stop  (should this really end the loop?)
       if (!allBlocksValid(Context) || Context.Log.hasErrors())
         break;
 
       // Store this region, because it is the greatest valid (encountered so
       // far).
for (BasicBlock::iterator I = BB->begin(), E = --BB->end(); I != E; ++I)
         return false;
 
   if (!hasAffineMemoryAccesses(Context))
     return false;
 
   return true;
 }
 
-bool ScopDetection::isValidExit(DetectionContext &Context) const {
-
-  // PHI nodes are not allowed in the exit basic block.
-  if (BasicBlock *Exit = Context.CurRegion.getExit()) {
-    BasicBlock::iterator I = Exit->begin();
-    if (I != Exit->end() && isa<PHINode>(*I))
-      return invalid<ReportPHIinExit>(Context, /*Assert=*/true, I);
-  }
-
-  return true;
-}
-
 bool ScopDetection::isValidRegion(DetectionContext &Context) const {
   Region &CurRegion = Context.CurRegion;
 
   DEBUG(dbgs() << "Checking region: " << CurRegion.getNameStr() << "\n\t");
 
   if (CurRegion.isTopLevelRegion()) {
     DEBUG(dbgs() << "Top level region is invalid\n");
     return false;
bool ScopDetection::isValidRegion(DetectionContext &Context) const {
   }
 
   // SCoP cannot contain the entry block of the function, because we need
   // to insert alloca instruction there when translate scalar to array.
   if (CurRegion.getEntry() ==
       &(CurRegion.getEntry()->getParent()->getEntryBlock()))
     return invalid<ReportEntry>(Context, /*Assert=*/true, CurRegion.getEntry());
 
-  if (!isValidExit(Context))
-    return false;
-
   if (!allBlocksValid(Context))
     return false;
 
   // We can probably not do a lot on scops that only write or only read
   // data.
   if (!DetectUnprofitable && (!Context.hasStores || !Context.hasLoads))
     invalid<ReportUnprofitable>(Context, /*Assert=*/true, &CurRegion);
 

test/ScopDetect/keep_going_expansion.ll

for.end9:                                         ; preds = %for.body4
   %2 = load i32, i32* %arrayidx11, align 4
   %idxprom12 = sext i32 %n to i64
   %arrayidx13 = getelementptr inbounds i32, i32* %B, i64 %idxprom12
   %3 = load i32, i32* %arrayidx13, align 4
   %add = add nsw i32 %3, %2
   ret i32 %add
 }
 
-; CHECK: Valid Region for Scop: for.body => for.cond2.preheader
+; CHECK: Valid Region for Scop: for.body => for.body4

test/ScopDetect/multidim_indirect_access.ll

 ; RUN: opt %loadPolly -polly-detect-unprofitable -polly-detect -analyze < %s | FileCheck %s --check-prefix=INDEPENDENT
 ; RUN: opt %loadPolly -polly-detect-unprofitable -polly-detect -analyze  < %s | FileCheck %s --check-prefix=NON_INDEPENDENT
 ;
 ; With the IndependentBlocks and PollyPrepare passes this will __correctly__
 ; not be recognized as a SCoP and the debug states:
 ;
 ;   SCEV of PHI node refers to SSA names in region
 ;
 ; Without IndependentBlocks and PollyPrepare the access A[x] is mistakenly
 ; treated as a multidimensional access with dimension size x. This test will
 ; check that we correctly invalidate the region and do not detect a outer SCoP.
 ;
-; FIXME:
-; We should detect the inner region but the PHI node in the exit blocks that.
-;
 ;    void f(int *A, long N) {
 ;      int j = 0;
 ;      while (N > j) {
 ;        int x = A[0];
 ;        int i = 1;
 ;        do {
 ;          A[x] = 42;
 ;          A += x;
 ;        } while (i++ < N);
 ;      }
 ;    }
 ;
-; INDEPENDENT-NOT: Valid
-; NON_INDEPENDENT-NOT: Valid
+; INDEPENDENT-NOT: Valid Region for Scop: bb0 => bb1
+; NON_INDEPENDENT-NOT: Valid Region for Scop: bb0 => bb1
 ;
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
 define void @f(i32* %A, i64 %N) {
 bb:
   br label %bb0
 
 bb0:

test/ScopDetect/non-affine-loop-condition-dependent-access_2.ll

 ; RUN: opt %loadPolly -basicaa -polly-detect -polly-allow-nonaffine-branches -polly-allow-nonaffine-loops=false -analyze < %s | FileCheck %s --check-prefix=REJECTNONAFFINELOOPS
 ; RUN: opt %loadPolly -basicaa -polly-detect -polly-allow-nonaffine-branches -polly-allow-nonaffine-loops=true -analyze < %s | FileCheck %s --check-prefix=ALLOWNONAFFINELOOPS
 ; RUN: opt %loadPolly -basicaa -polly-detect -polly-allow-nonaffine -polly-allow-nonaffine-branches -polly-allow-nonaffine-loops=true -analyze < %s | FileCheck %s --check-prefix=ALLOWNONAFFINELOOPSANDACCESSES
 ;
 ; Here we have a non-affine loop (in the context of the loop nest)
 ; and also a non-affine access (A[k]). While we can always detect the
 ; innermost loop as a SCoP of depth 1, we have to reject the loop nest if not
 ; both, non-affine loops as well as non-affine accesses are allowed.
 ;
-; REJECTNONAFFINELOOPS:           Valid Region for Scop: bb15 => bb26
+; REJECTNONAFFINELOOPS:           Valid Region for Scop: bb15 => bb13
 ; REJECTNONAFFINELOOPS-NOT:       Valid
-; ALLOWNONAFFINELOOPS:            Valid Region for Scop: bb15 => bb26
+; ALLOWNONAFFINELOOPS:            Valid Region for Scop: bb15 => bb13
 ; ALLOWNONAFFINELOOPS-NOT:        Valid
 ; ALLOWNONAFFINELOOPSANDACCESSES: Valid Region for Scop: bb11 => bb29
 ;
 ;    void f(int *A) {
 ;      for (int i = 0; i < 1024; i++)
 ;        for (int j = 0; j < 1024; j++)
 ;          for (int k = i *j;  k < 1024; k++)
 ;            A[k] += A[i] + A[j];

test/ScopDetect/non-affine-loop-condition-dependent-access_3.ll

 ; RUN: opt %loadPolly -basicaa -polly-detect -polly-allow-nonaffine-branches -polly-allow-nonaffine-loops=false -analyze < %s | FileCheck %s --check-prefix=REJECTNONAFFINELOOPS
 ; RUN: opt %loadPolly -basicaa -polly-detect -polly-allow-nonaffine-branches -polly-allow-nonaffine-loops=true -analyze < %s | FileCheck %s --check-prefix=ALLOWNONAFFINELOOPS
 ; RUN: opt %loadPolly -basicaa -polly-detect -polly-allow-nonaffine -polly-allow-nonaffine-branches -polly-allow-nonaffine-loops=true -analyze < %s | FileCheck %s --check-prefix=ALLOWNONAFFINELOOPSANDACCESSES
 ;
 ; Here we have a non-affine loop (in the context of the loop nest)
 ; and also a non-affine access (A[k]). While we can always detect the
 ; innermost loop as a SCoP of depth 1, we have to reject the loop nest if not
 ; both, non-affine loops as well as non-affine accesses are allowed.
 ;
-; REJECTNONAFFINELOOPS:           Valid Region for Scop: bb15 => bb26
+; REJECTNONAFFINELOOPS:           Valid Region for Scop: bb15 => bb13
 ; REJECTNONAFFINELOOPS-NOT:       Valid
-; ALLOWNONAFFINELOOPS:            Valid Region for Scop: bb15 => bb26
+; ALLOWNONAFFINELOOPS:            Valid Region for Scop: bb15 => bb13
 ; ALLOWNONAFFINELOOPS-NOT:        Valid
 ; ALLOWNONAFFINELOOPSANDACCESSES: Valid Region for Scop: bb11 => bb29
 ;
 ;    void f(int *A) {
 ;      for (int i = 0; i < 1024; i++)
 ;        for (int j = 0; j < 1024; j++)
 ;          for (int k = 0; k < i * j; k++)
 ;            A[k] += A[i] + A[j];

test/ScopDetect/simple_non_single_entry.ll

for.i:
   %exitcond = icmp eq i64 %indvar.next, %N
   br i1 %exitcond, label %return, label %for.i
 
 return:
   fence seq_cst
   ret void
 }
 
-; CHECK: Valid Region for Scop: next => for.i.head1
+; CHECK: Valid Region for Scop: next => for.i

test/ScopInfo/20111108-Parameter-not-detected.ll

 for.end7:                                         ; preds = %for.cond
   ret i32 0
 }
 
 ; CHECK: Context:
 ; CHECK: p0: {0,+,1}<%for.cond>
 
 ; CHECK: Domain :=
-; CHECK: [p_0] -> { Stmt_if_then[i0] : i0 >= 0 and i0 <= 1022 and i0 >= 999 - p_0 };
+; CHECK: [p_0] -> { Stmt_if_then[i0] : i0 <= 1022 and i0 >= 0 and i0 >= 999 - p_0 };
 

test/ScopInfo/NonAffine/non-affine-loop-condition-dependent-access_2.ll

 ; RUN: opt %loadPolly -basicaa -polly-scops -polly-allow-nonaffine-branches -polly-allow-nonaffine-loops=false -analyze < %s | FileCheck %s --check-prefix=INNERMOST
 ; RUN: opt %loadPolly -basicaa -polly-scops -polly-allow-nonaffine-branches -polly-allow-nonaffine-loops=true -analyze < %s | FileCheck %s --check-prefix=INNERMOST
 ; RUN: opt %loadPolly -basicaa -polly-scops -polly-allow-nonaffine -polly-allow-nonaffine-branches -polly-allow-nonaffine-loops=true -analyze < %s | FileCheck %s --check-prefix=ALL
 ;
 ; Here we have a non-affine loop (in the context of the loop nest)
 ; and also a non-affine access (A[k]). While we can always model the
 ; innermost loop as a SCoP of depth 1, we can overapproximate the
 ; innermost loop in the whole loop nest and model A[k] as a non-affine
 ; access.
 ;
 ; INNERMOST:    Function: f
-; INNERMOST:    Region: %bb15---%bb26
+; INNERMOST:    Region: %bb15---%bb13
 ; INNERMOST:    Max Loop Depth:  1
 ; INNERMOST:    p0: {0,+,{0,+,-1}<nw><%bb11>}<nw><%bb13>
 ; INNERMOST:    p1: {0,+,{0,+,1}<nuw><nsw><%bb11>}<nuw><nsw><%bb13>
 ; INNERMOST:    p2: {0,+,4}<nuw><nsw><%bb11>
 ; INNERMOST:    p3: {0,+,4}<nuw><nsw><%bb13>
 ; INNERMOST:    p4: {0,+,{0,+,4}<nuw><nsw><%bb11>}<%bb13>
 ; INNERMOST:    Alias Groups (0):
 ; INNERMOST:        n/a
 ; INNERMOST:    Statements {
-; INNERMOST:      Stmt_bb16
+; INNERMOST:        Stmt_bb16
 ; INNERMOST:            Domain :=
-; INNERMOST:                [p_0, p_1, p_2, p_3, p_4] -> { Stmt_bb16[i0] : (i0 <= 1023 - p_1 and i0 >= 0 and i0 <= 1024 + p_0) or (i0 >= 0 and i0 >= 1025 - p_1 and i0 <= 1024 + p_0) };
+; INNERMOST:                [p_0, p_1, p_2, p_3, p_4] -> { Stmt_bb16[i0] : (i0 >= 0 and i0 >= 1025 - p_1 and i0 <= 1024 + p_0) or (i0 <= 1023 - p_1 and i0 >= 0 and i0 <= 1024 + p_0) };
 ; INNERMOST:            Schedule :=
-; INNERMOST:                [p_0, p_1, p_2, p_3, p_4] -> { Stmt_bb16[i0] -> [i0] : i0 >= 1025 - p_1 or i0 <= 1023 - p_1 };
+; INNERMOST:                [p_0, p_1, p_2, p_3, p_4] -> { Stmt_bb16[i0] -> [0, i0] : i0 >= 1025 - p_1 or i0 <= 1023 - p_1 };
 ; INNERMOST:            ReadAccess := [Reduction Type: NONE] [Scalar: 0]
 ; INNERMOST:                [p_0, p_1, p_2, p_3, p_4] -> { Stmt_bb16[i0] -> MemRef_A[o0] : 4o0 = p_2 };
 ; INNERMOST:            ReadAccess := [Reduction Type: NONE] [Scalar: 0]
 ; INNERMOST:                [p_0, p_1, p_2, p_3, p_4] -> { Stmt_bb16[i0] -> MemRef_A[o0] : 4o0 = p_3 };
 ; INNERMOST:            ReadAccess := [Reduction Type: +] [Scalar: 0]
 ; INNERMOST:                [p_0, p_1, p_2, p_3, p_4] -> { Stmt_bb16[i0] -> MemRef_A[o0] : 4o0 = p_4 + 4i0 };
 ; INNERMOST:            MustWriteAccess :=  [Reduction Type: +] [Scalar: 0]
 ; INNERMOST:                [p_0, p_1, p_2, p_3, p_4] -> { Stmt_bb16[i0] -> MemRef_A[o0] : 4o0 = p_4 + 4i0 };
+; INNERMOST:        Stmt_bb13
+; INNERMOST:            Domain :=
+; INNERMOST:                [p_0, p_1, p_2, p_3, p_4] -> { Stmt_bb13[] };
+; INNERMOST:            Schedule :=
+; INNERMOST:                [p_0, p_1, p_2, p_3, p_4] -> { Stmt_bb13[] -> [1, 0] };
+; INNERMOST:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; INNERMOST:                [p_0, p_1, p_2, p_3, p_4] -> { Stmt_bb13[] -> MemRef_indvars_iv5[] };
 ; INNERMOST:    }
 ;
 ; ALL:    Function: f
 ; ALL:    Region: %bb11---%bb29
 ; ALL:    Max Loop Depth:  2
 ; ALL:    Context:
 ; ALL:    {  :  }
 ; ALL:    Assumed Context:

test/ScopInfo/NonAffine/non-affine-loop-condition-dependent-access_3.ll

 ; RUN: opt %loadPolly -basicaa -polly-scops -polly-allow-nonaffine-branches -polly-allow-nonaffine-loops=false -analyze < %s | FileCheck %s --check-prefix=INNERMOST
 ; RUN: opt %loadPolly -basicaa -polly-scops -polly-allow-nonaffine-branches -polly-allow-nonaffine-loops=true -analyze < %s | FileCheck %s --check-prefix=INNERMOST
 ; RUN: opt %loadPolly -basicaa -polly-scops -polly-allow-nonaffine -polly-allow-nonaffine-branches -polly-allow-nonaffine-loops=true -analyze < %s | FileCheck %s --check-prefix=ALL
 ;
 ; Here we have a non-affine loop (in the context of the loop nest)
 ; and also a non-affine access (A[k]). While we can always model the
 ; innermost loop as a SCoP of depth 1, we can overapproximate the
 ; innermost loop in the whole loop nest and model A[k] as a non-affine
 ; access.
 ;
 ; INNERMOST:    Function: f
-; INNERMOST:    Region: %bb15---%bb26
+; INNERMOST:    Region: %bb15---%bb13
 ; INNERMOST:    Max Loop Depth:  1
 ; INNERMOST:    Context:
 ; INNERMOST:      [p_0, p_1, p_2] -> {  : p_0 >= 0 and p_0 <= 2147483647 and p_1 >= 0 and p_1 <= 4096 and p_2 >= 0 and p_2 <= 4096 }
 ; INNERMOST:    Assumed Context:
 ; INNERMOST:      [p_0, p_1, p_2] -> {  :  }
 ; INNERMOST:    p0: {0,+,{0,+,1}<nuw><nsw><%bb11>}<nuw><nsw><%bb13>
 ; INNERMOST:    p1: {0,+,4}<nuw><nsw><%bb11>
 ; INNERMOST:    p2: {0,+,4}<nuw><nsw><%bb13>
 ; INNERMOST:    Alias Groups (0):
 ; INNERMOST:        n/a
 ; INNERMOST:    Statements {
 ; INNERMOST:      Stmt_bb16
 ; INNERMOST:            Domain :=
 ; INNERMOST:                [p_0, p_1, p_2] -> { Stmt_bb16[i0] : i0 >= 0 and i0 <= -1 + p_0 };
 ; INNERMOST:            Schedule :=
-; INNERMOST:                [p_0, p_1, p_2] -> { Stmt_bb16[i0] -> [i0] };
+; INNERMOST:                [p_0, p_1, p_2] -> { Stmt_bb16[i0] -> [0, i0] };
 ; INNERMOST:            ReadAccess := [Reduction Type: NONE] [Scalar: 0]
 ; INNERMOST:                [p_0, p_1, p_2] -> { Stmt_bb16[i0] -> MemRef_A[o0] : 4o0 = p_1 };
 ; INNERMOST:            ReadAccess := [Reduction Type: NONE] [Scalar: 0]
 ; INNERMOST:                [p_0, p_1, p_2] -> { Stmt_bb16[i0] -> MemRef_A[o0] : 4o0 = p_2 };
 ; INNERMOST:            ReadAccess := [Reduction Type: +] [Scalar: 0]
 ; INNERMOST:                [p_0, p_1, p_2] -> { Stmt_bb16[i0] -> MemRef_A[i0] };
 ; INNERMOST:            MustWriteAccess :=  [Reduction Type: +] [Scalar: 0]
 ; INNERMOST:                [p_0, p_1, p_2] -> { Stmt_bb16[i0] -> MemRef_A[i0] };