[Polly] DeLICM test cases

[Meinersbur]

Summary

Not meant for committing; CHECK-lines correspond to output by D12975 (with some additional changes)

test/ScopInfo/delicm_GVN.ll

+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+;
+;    void func(int n, double A[static const n], int m) {
+;      for (int j = 0; j < n; j += 1) { /* parallel loop */
+;        double red = A[j];
+;        for (int i = 0; i < m; i += 1) { /* reduction loop */
+;          red += 4.2;
+;          A[j] = red;
+;       }
+;    }
+
+; Nested reduction standard case
+; After GVN-Pre (LICM cannot because of possible aliasing)
+; Possible difficulties:
+; - Slot %arrayidx is overwritten in loop, indicating that %arraidx is not available for use
+
+define void @func(i32 %n, double* noalias nonnull %A, i32 %m) {
+entry:
+  br label %parallel.for
+
+parallel.for:
+  %j = phi i32 [0, %entry], [%j.inc, %parallel.inc]
+  %arrayidx = getelementptr inbounds double, double* %A, i32 %j
+  %ld = load double, double* %arrayidx
+  %j.cmp = icmp slt i32 %j, %n
+  br i1 %j.cmp, label %reduction.for, label %return
+
+reduction.for:
+  %i = phi i32 [0, %parallel.for], [%i.inc, %reduction.inc]
+  %phi = phi double [%ld, %parallel.for], [%add, %reduction.inc]
+  %i.cmp = icmp slt i32 %i, %m
+  br i1 %i.cmp, label %body, label %parallel.inc
+
+body:
+  %add = fadd double %phi, 4.2
+  store double %add, double* %arrayidx
+  br label %reduction.inc
+
+reduction.inc:
+  %i.inc = add nuw nsw i32 %i, 1
+  br label %reduction.for
+
+parallel.inc:
+  %j.inc = add nuw nsw i32 %j, 1
+  br label %parallel.for
+
+return:
+  ret void
+}
+
+
+; CHECK: Printing analysis 'Polly - Create polyhedral description of Scops' for region: 'reduction.for => parallel.inc' in function 'func':
+; CHECK-NEXT: Invalid Scop!
+; CHECK-NEXT: Printing analysis 'Polly - Create polyhedral description of Scops' for region: 'parallel.for => return' in function 'func':
+; CHECK-NEXT:     Function: func
+; CHECK-NEXT:     Region: %parallel.for---%return
+; CHECK-NEXT:     Max Loop Depth:  2
+; CHECK-NEXT:     Invariant Accesses: {
+; CHECK-NEXT:     }
+; CHECK-NEXT:     Context:
+; CHECK-NEXT:     [n, m] -> {  : n >= -2147483648 and n <= 2147483647 and m >= -2147483648 and m <= 2147483647 }
+; CHECK-NEXT:     Assumed Context:
+; CHECK-NEXT:     [n, m] -> {  :  }
+; CHECK-NEXT:     Boundary Context:
+; CHECK-NEXT:     [n, m] -> {  :  }
+; CHECK-NEXT:     p0: %n
+; CHECK-NEXT:     p1: %m
+; CHECK-NEXT:     Arrays {
+; CHECK-NEXT:         double MemRef_A[*][8] // Element size 8
+; CHECK-NEXT:     }
+; CHECK-NEXT:     Arrays (Bounds as pw_affs) {
+; CHECK-NEXT:         double MemRef_A[*][ { [] -> [(8)] } ] // Element size 8
+; CHECK-NEXT:     }
+; CHECK-NEXT:     Alias Groups (0):
+; CHECK-NEXT:         n/a
+; CHECK-NEXT:     Statements {
+; CHECK-NEXT:       Stmt_body
+; CHECK-NEXT:             Domain :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_body[i0, i1] : i0 >= 0 and i0 <= -1 + n and i1 >= 0 and i1 <= -1 + m };
+; CHECK-NEXT:             Schedule :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_body[i0, i1] -> [i0, i1] };
+; CHECK-NEXT:             ReadAccess := [Reduction Type: NONE] [MAPPED]
+; CHECK-NEXT:                 [n, m] -> { Stmt_body[i0, i1] -> MemRef_A[i0] };
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [MAPPED]
+; CHECK-NEXT:                 [n, m] -> { Stmt_body[i0, i1] -> MemRef_A[i0] };
+; CHECK-NEXT:     }
+; CHECK-NEXT: Printing analysis 'Polly - Create polyhedral description of Scops' for region: 'entry => <Function Return>' in function 'func':
+; CHECK-NEXT: Invalid Scop!

test/ScopInfo/delicm_LICM_cond.ll

+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+;
+;    void func(int n, double A[static const restrict n], int m) {
+;      for (int j = 0; j < n; j += 1) { /* parallel loop */
+;        double red = A[j];
+;        for (int i = 0; i < m; i += 1) /* reduction loop */
+;          if (i % 2 == 0)
+;            red += 4.2;
+;        A[j] = red;
+;    }
+
+; Body executed conditionally
+; Possible difficulties:
+; - %reduction.inc non-existing, where to put the store?
+
+define void @func(i32 %n, double* noalias nonnull %A, i32 %m, double* noalias nonnull %B) {
+entry:
+  br label %parallel.for
+
+parallel.for:
+  %j = phi i32 [0, %entry], [%j.inc, %parallel.inc]
+  %arrayidx = getelementptr inbounds double, double* %A, i32 %j
+  %ld = load double, double* %arrayidx
+  %j.cmp = icmp slt i32 %j, %n
+  br i1 %j.cmp, label %reduction.for, label %return
+
+reduction.for:
+  %i = phi i32 [0, %parallel.for], [%i.inc, %body], [%i.inc, %body.true]
+  %phi = phi double [%ld, %parallel.for], [%phi, %body], [%add, %body.true]
+  %i.cmp = icmp slt i32 %i, %m
+  %i.inc = add nuw nsw i32 %i, 1
+  br i1 %i.cmp, label %body, label %parallel.inc
+
+body:
+  %rem = and i32 %i, 1
+  %cond = icmp eq i32 %rem, 0
+  br i1 %cond, label %body.true, label %reduction.for
+
+body.true:
+  %add = fadd double %phi, 4.2
+  br label %reduction.for
+
+parallel.inc:
+  store double %phi, double* %arrayidx
+  %j.inc = add nuw nsw i32 %j, 1
+  br label %parallel.for
+
+return:
+  ret void
+}
+
+
+; CHECK: Printing analysis 'Polly - Create polyhedral description of Scops' for region: 'body => reduction.for' in function 'func':
+; CHECK-NEXT:     Function: func
+; CHECK-NEXT:     Region: %body---%reduction.for
+; CHECK-NEXT:     Max Loop Depth:  1
+; CHECK-NEXT:     Invariant Accesses: {
+; CHECK-NEXT:     }
+; CHECK-NEXT:     Context:
+; CHECK-NEXT:     [p_0] -> {  : p_0 >= 0 and p_0 <= 1 }
+; CHECK-NEXT:     Assumed Context:
+; CHECK-NEXT:     [p_0] -> {  :  }
+; CHECK-NEXT:     Boundary Context:
+; CHECK-NEXT:     [p_0] -> {  :  }
+; CHECK-NEXT:     p0: (zext i1 {false,+,true}<%reduction.for> to i32)
+; CHECK-NEXT:     Arrays {
+; CHECK-NEXT:         i32 MemRef_i[*] // Element size 4
+; CHECK-NEXT:         double MemRef_phi[*] // Element size 8
+; CHECK-NEXT:     }
+; CHECK-NEXT:     Arrays (Bounds as pw_affs) {
+; CHECK-NEXT:         i32 MemRef_i[*] // Element size 4
+; CHECK-NEXT:         double MemRef_phi[*] // Element size 8
+; CHECK-NEXT:     }
+; CHECK-NEXT:     Alias Groups (0):
+; CHECK-NEXT:         n/a
+; CHECK-NEXT:     Statements {
+; CHECK-NEXT:       Stmt_body
+; CHECK-NEXT:             Domain :=
+; CHECK-NEXT:                 [p_0] -> { Stmt_body[] };
+; CHECK-NEXT:             Schedule :=
+; CHECK-NEXT:                 [p_0] -> { Stmt_body[] -> [0] };
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 [p_0] -> { Stmt_body[] -> MemRef_i[] };
+; CHECK-NEXT:             ReadAccess := [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 [p_0] -> { Stmt_body[] -> MemRef_phi[] };
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 [p_0] -> { Stmt_body[] -> MemRef_phi[] };
+; CHECK-NEXT:       Stmt_body_true
+; CHECK-NEXT:             Domain :=
+; CHECK-NEXT:                 [p_0] -> { Stmt_body_true[] : p_0 = 0 };
+; CHECK-NEXT:             Schedule :=
+; CHECK-NEXT:                 [p_0] -> { Stmt_body_true[] -> [1] };
+; CHECK-NEXT:             ReadAccess := [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 [p_0] -> { Stmt_body_true[] -> MemRef_phi[] };
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 [p_0] -> { Stmt_body_true[] -> MemRef_i[] };
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 [p_0] -> { Stmt_body_true[] -> MemRef_phi[] };
+; CHECK-NEXT:     }
+; CHECK-NEXT: Printing analysis 'Polly - Create polyhedral description of Scops' for region: 'reduction.for => parallel.inc' in function 'func':
+; CHECK-NEXT: Invalid Scop!
+; CHECK-NEXT: Printing analysis 'Polly - Create polyhedral description of Scops' for region: 'parallel.for => return' in function 'func':
+; CHECK-NEXT: Invalid Scop!
+; CHECK-NEXT: Printing analysis 'Polly - Create polyhedral description of Scops' for region: 'entry => <Function Return>' in function 'func':
+; CHECK-NEXT: Invalid Scop!

test/ScopInfo/delicm_LICM_conditional_reductions.ll

+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+;
+;    void func(int n, double A[static const restrict n], int m, int c) {
+;      for (int j = 0; j < n; j += 1) { /* parallel loop */
+;        double red = A[j];
+;        if (c) {
+;          for (int i = 0; i < m; i += 1) /* reduction loop */
+;            red += 4.2;
+;        else {
+;          for (int i = 0; i < m; i += 1) /* reduction loop */
+;            red *= 1.2;
+;        }
+;        A[j] = red;
+;    }
+
+; Nested reduction standard case
+; After LICM 
+; Possible difficulties:
+; - Two independent loop-carried phis can reuse the same %arrayidx (to be distinguished from the case where it can't)
+
+define void @func(i32 %n, double* noalias nonnull %A, i32 %m, i32 %c) {
+entry:
+  br label %parallel.for
+
+parallel.for:
+  %j = phi i32 [0, %entry], [%j.inc, %parallel.inc]
+  %arrayidx = getelementptr inbounds double, double* %A, i32 %j
+  %ld = load double, double* %arrayidx
+  %j.cmp = icmp slt i32 %j, %n
+  br i1 %j.cmp, label %condition, label %return
+
+condition:
+  %ccmp = icmp ne i32 %c, 0
+  br i1 %ccmp, label %reduction1.for, label %reduction2.for
+
+reduction1.for:
+  %i1 = phi i32 [0, %condition], [%i1.inc, %reduction1.inc]
+  %phi1 = phi double [%ld, %condition], [%add, %reduction1.inc]
+  %i1.cmp = icmp slt i32 %i1, %m
+  br i1 %i1.cmp, label %body1, label %parallel.inc
+
+body1:
+  %add = fadd double %phi1, 4.2
+  br label %reduction1.inc
+
+reduction1.inc:
+  %i1.inc = add nuw nsw i32 %i1, 1
+  br label %reduction1.for
+  
+reduction2.for:
+  %i2 = phi i32 [0, %condition], [%i2.inc, %reduction2.inc]
+  %phi2 = phi double [%ld, %condition], [%mul, %reduction2.inc]
+  %i2.cmp = icmp slt i32 %i2, %m
+  br i1 %i2.cmp, label %body2, label %parallel.inc
+
+body2:
+  %mul = fmul double %phi2, 1.2
+  br label %reduction2.inc
+
+reduction2.inc:
+  %i2.inc = add nuw nsw i32 %i2, 1
+  br label %reduction2.for
+
+parallel.inc:
+  %condphi = phi double [%phi1, %reduction1.for], [%phi2, %reduction2.for]
+  store double %condphi, double* %arrayidx
+  %j.inc = add nuw nsw i32 %j, 1
+  br label %parallel.for
+
+return:
+  ret void
+}
+
+
+; CHECK: Printing analysis 'Polly - Create polyhedral description of Scops' for region: 'reduction2.for => parallel.inc' in function 'func':
+; CHECK-NEXT: Invalid Scop!
+; CHECK-NEXT: Printing analysis 'Polly - Create polyhedral description of Scops' for region: 'reduction1.for => parallel.inc' in function 'func':
+; CHECK-NEXT: Invalid Scop!
+; CHECK-NEXT: Printing analysis 'Polly - Create polyhedral description of Scops' for region: 'condition => parallel.inc' in function 'func':
+; CHECK-NEXT: Invalid Scop!
+; CHECK-NEXT: Printing analysis 'Polly - Create polyhedral description of Scops' for region: 'parallel.for => return' in function 'func':
+; CHECK-NEXT:     Function: func
+; CHECK-NEXT:     Region: %parallel.for---%return
+; CHECK-NEXT:     Max Loop Depth:  2
+; CHECK-NEXT:     Invariant Accesses: {
+; CHECK-NEXT:     }
+; CHECK-NEXT:     Context:
+; CHECK-NEXT:     [n, c, m] -> {  : n >= -2147483648 and n <= 2147483647 and m >= -2147483648 and m <= 2147483647 and c >= -2147483648 and c <= 2147483647 }
+; CHECK-NEXT:     Assumed Context:
+; CHECK-NEXT:     [n, c, m] -> {  :  }
+; CHECK-NEXT:     Boundary Context:
+; CHECK-NEXT:     [n, c, m] -> {  :  }
+; CHECK-NEXT:     p0: %n
+; CHECK-NEXT:     p1: %c
+; CHECK-NEXT:     p2: %m
+; CHECK-NEXT:     Arrays {
+; CHECK-NEXT:         double MemRef_A[*][8] // Element size 8
+; CHECK-NEXT:     }
+; CHECK-NEXT:     Arrays (Bounds as pw_affs) {
+; CHECK-NEXT:         double MemRef_A[*][ { [] -> [(8)] } ] // Element size 8
+; CHECK-NEXT:     }
+; CHECK-NEXT:     Alias Groups (0):
+; CHECK-NEXT:         n/a
+; CHECK-NEXT:     Statements {
+; CHECK-NEXT:       Stmt_body1
+; CHECK-NEXT:             Domain :=
+; CHECK-NEXT:                 [n, c, m] -> { Stmt_body1[i0, i1] : (c <= -1 and i0 >= 0 and i0 <= -1 + n and i1 >= 0 and i1 <= -1 + m) or (c >= 1 and i0 >= 0 and i0 <= -1 + n and i1 >= 0 and i1 <= -1 + m) };
+; CHECK-NEXT:             Schedule :=
+; CHECK-NEXT:                 [n, c, m] -> { Stmt_body1[i0, i1] -> [i0, 1, i1] : c <= -1 or c >= 1 };
+; CHECK-NEXT:             ReadAccess := [Reduction Type: NONE] [MAPPED]
+; CHECK-NEXT:                 [n, c, m] -> { Stmt_body1[i0, i1] -> MemRef_A[i0] };
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [MAPPED]
+; CHECK-NEXT:                 [n, c, m] -> { Stmt_body1[i0, i1] -> MemRef_A[i0] };
+; CHECK-NEXT:       Stmt_body2
+; CHECK-NEXT:             Domain :=
+; CHECK-NEXT:                 [n, c, m] -> { Stmt_body2[i0, i1] : c = 0 and i0 >= 0 and i0 <= -1 + n and i1 >= 0 and i1 <= -1 + m };
+; CHECK-NEXT:             Schedule :=
+; CHECK-NEXT:                 [n, c, m] -> { Stmt_body2[i0, i1] -> [i0, 0, i1] };
+; CHECK-NEXT:             ReadAccess := [Reduction Type: NONE] [MAPPED]
+; CHECK-NEXT:                 [n, c, m] -> { Stmt_body2[i0, i1] -> MemRef_A[i0] };
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [MAPPED]
+; CHECK-NEXT:                 [n, c, m] -> { Stmt_body2[i0, i1] -> MemRef_A[i0] };
+; CHECK-NEXT:     }
+; CHECK-NEXT: Printing analysis 'Polly - Create polyhedral description of Scops' for region: 'entry => <Function Return>' in function 'func':
+; CHECK-NEXT: Invalid Scop!

test/ScopInfo/delicm_LICM_consecutive_reductions.ll

+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+;
+;    void func(int n, double A[static const restrict n], int m) {
+;      for (int j = 0; j < n; j += 1) { /* parallel loop */
+;        double red = A[j];
+;        for (int i1 = 0; i1 < m; i1 += 1) /* reduction loop */
+;          red += 4.2;
+;        for (int i2 = 0; i2 < m; i2 += 1) /* reduction loop */
+;          red += 5.3;
+;        A[j] = red;
+;    }
+
+; Two reductions executed sequentially 
+; Possible difficulties:
+; - Two loop-carrying phis that can use the same %arrayidx
+
+define void @func(i32 %n, double* noalias nonnull %A, i32 %m) {
+entry:
+  br label %parallel.for
+
+parallel.for:
+  %j = phi i32 [0, %entry], [%j.inc, %parallel.inc]
+  %arrayidx = getelementptr inbounds double, double* %A, i32 %j
+  %ld = load double, double* %arrayidx
+  %j.cmp = icmp slt i32 %j, %n
+  br i1 %j.cmp, label %reduction1.for, label %return
+
+reduction1.for:
+  %i1 = phi i32 [0, %parallel.for], [%i1.inc, %reduction1.inc]
+  %phi1 = phi double [%ld, %parallel.for], [%add1, %reduction1.inc]
+  %i1.cmp = icmp slt i32 %i1, %m
+  br i1 %i1.cmp, label %body1, label %reduction2.for
+
+body1:
+  %add1 = fadd double %phi1, 4.2
+  br label %reduction1.inc
+
+reduction1.inc:
+  %i1.inc = add nuw nsw i32 %i1, 1
+  br label %reduction1.for
+
+reduction2.for:
+  %i2 = phi i32 [0, %reduction1.for], [%i2.inc, %reduction2.inc]
+  %phi2 = phi double [%phi1, %reduction1.for], [%add2, %reduction2.inc]
+  %i2.cmp = icmp slt i32 %i2, %m
+  br i1 %i2.cmp, label %body2, label %parallel.inc
+
+body2:
+  %add2 = fadd double %phi2, 5.3
+  br label %reduction2.inc
+
+reduction2.inc:
+  %i2.inc = add nuw nsw i32 %i2, 1
+  br label %reduction2.for
+
+parallel.inc:
+  store double %phi2, double* %arrayidx
+  %j.inc = add nuw nsw i32 %j, 1
+  br label %parallel.for
+
+return:
+  ret void
+}
+
+
+; CHECK: Printing analysis 'Polly - Create polyhedral description of Scops' for region: 'reduction2.for => parallel.inc' in function 'func':
+; CHECK-NEXT: Invalid Scop!
+; CHECK-NEXT: Printing analysis 'Polly - Create polyhedral description of Scops' for region: 'reduction1.for => reduction2.for' in function 'func':
+; CHECK-NEXT: Invalid Scop!
+; CHECK-NEXT: Printing analysis 'Polly - Create polyhedral description of Scops' for region: 'parallel.for => return' in function 'func':
+; CHECK-NEXT:     Function: func
+; CHECK-NEXT:     Region: %parallel.for---%return
+; CHECK-NEXT:     Max Loop Depth:  2
+; CHECK-NEXT:     Invariant Accesses: {
+; CHECK-NEXT:     }
+; CHECK-NEXT:     Context:
+; CHECK-NEXT:     [n, m] -> {  : n >= -2147483648 and n <= 2147483647 and m >= -2147483648 and m <= 2147483647 }
+; CHECK-NEXT:     Assumed Context:
+; CHECK-NEXT:     [n, m] -> {  :  }
+; CHECK-NEXT:     Boundary Context:
+; CHECK-NEXT:     [n, m] -> {  :  }
+; CHECK-NEXT:     p0: %n
+; CHECK-NEXT:     p1: %m
+; CHECK-NEXT:     Arrays {
+; CHECK-NEXT:         double MemRef_A[*][8] // Element size 8
+; CHECK-NEXT:     }
+; CHECK-NEXT:     Arrays (Bounds as pw_affs) {
+; CHECK-NEXT:         double MemRef_A[*][ { [] -> [(8)] } ] // Element size 8
+; CHECK-NEXT:     }
+; CHECK-NEXT:     Alias Groups (0):
+; CHECK-NEXT:         n/a
+; CHECK-NEXT:     Statements {
+; CHECK-NEXT:       Stmt_body1
+; CHECK-NEXT:             Domain :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_body1[i0, i1] : i0 >= 0 and i0 <= -1 + n and i1 >= 0 and i1 <= -1 + m };
+; CHECK-NEXT:             Schedule :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_body1[i0, i1] -> [i0, 0, i1] };
+; CHECK-NEXT:             ReadAccess := [Reduction Type: NONE] [MAPPED]
+; CHECK-NEXT:                 [n, m] -> { Stmt_body1[i0, i1] -> MemRef_A[i0] };
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [MAPPED]
+; CHECK-NEXT:                 [n, m] -> { Stmt_body1[i0, i1] -> MemRef_A[i0] };
+; CHECK-NEXT:       Stmt_body2
+; CHECK-NEXT:             Domain :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_body2[i0, i1] : i0 >= 0 and i0 <= -1 + n and i1 >= 0 and i1 <= -1 + m };
+; CHECK-NEXT:             Schedule :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_body2[i0, i1] -> [i0, 1, i1] };
+; CHECK-NEXT:             ReadAccess := [Reduction Type: NONE] [MAPPED]
+; CHECK-NEXT:                 [n, m] -> { Stmt_body2[i0, i1] -> MemRef_A[i0] };
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [MAPPED]
+; CHECK-NEXT:                 [n, m] -> { Stmt_body2[i0, i1] -> MemRef_A[i0] };
+; CHECK-NEXT:     }
+; CHECK-NEXT: Printing analysis 'Polly - Create polyhedral description of Scops' for region: 'entry => <Function Return>' in function 'func':
+; CHECK-NEXT: Invalid Scop!

test/ScopInfo/delicm_LICM_loads.ll

+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+;
+;    void func(int n, double A[static const restrict n], int m, double B[static const restrict n], double C[static const restrict n]) {
+;      for (int j = 0; j < n; j += 1) { /* parallel loop */
+;        B[j] = A[j];
+;        double red = A[j];
+;        red += 5.1;
+;        for (int i = 0; i < m; i += 1) /* reduction loop */
+;          red += 4.2;
+;        A[j] = red;
+;        C[j] = A[j];
+;    }
+
+; Value of A[j] used, outside of reduction
+; Possible difficulties:
+; - Distinguish from case where uses of A[j] is between the reduction intial load and writeback.
+
+define void @func(i32 %n, double* noalias nonnull %A, i32 %m, double* noalias nonnull %B, double* noalias nonnull %C) {
+entry:
+  br label %parallel.for
+
+parallel.for:
+  %j = phi i32 [0, %entry], [%j.inc, %parallel.inc]
+  %arrayidx = getelementptr inbounds double, double* %A, i32 %j
+  %arrayidxB = getelementptr inbounds double, double* %B, i32 %j
+  %arrayidxC = getelementptr inbounds double, double* %C, i32 %j
+  %ld = load double, double* %arrayidx
+  %prep = fadd double %ld, 5.1
+  store double %ld, double* %arrayidxB
+  %j.cmp = icmp slt i32 %j, %n
+  br i1 %j.cmp, label %reduction.for, label %return
+
+reduction.for:
+  %i = phi i32 [0, %parallel.for], [%i.inc, %reduction.inc]
+  %phi = phi double [%ld, %parallel.for], [%add, %reduction.inc]
+  %i.cmp = icmp slt i32 %i, %m
+  br i1 %i.cmp, label %body, label %parallel.inc
+
+body:
+  %add = fadd double %phi, 4.2
+  br label %reduction.inc
+
+reduction.inc:
+  %i.inc = add nuw nsw i32 %i, 1
+  br label %reduction.for
+
+parallel.inc:
+  store double %phi, double* %arrayidx
+  store double %phi, double* %arrayidxC
+  %j.inc = add nuw nsw i32 %j, 1
+  br label %parallel.for
+
+return:
+  ret void
+}
+
+
+; CHECK: Printing analysis 'Polly - Create polyhedral description of Scops' for region: 'reduction.for => parallel.inc' in function 'func':
+; CHECK-NEXT: Invalid Scop!
+; CHECK-NEXT: Printing analysis 'Polly - Create polyhedral description of Scops' for region: 'parallel.for => return' in function 'func':
+; CHECK-NEXT:     Function: func
+; CHECK-NEXT:     Region: %parallel.for---%return
+; CHECK-NEXT:     Max Loop Depth:  2
+; CHECK-NEXT:     Invariant Accesses: {
+; CHECK-NEXT:     }
+; CHECK-NEXT:     Context:
+; CHECK-NEXT:     [n, m] -> {  : n >= -2147483648 and n <= 2147483647 and m >= -2147483648 and m <= 2147483647 }
+; CHECK-NEXT:     Assumed Context:
+; CHECK-NEXT:     [n, m] -> {  :  }
+; CHECK-NEXT:     Boundary Context:
+; CHECK-NEXT:     [n, m] -> {  :  }
+; CHECK-NEXT:     p0: %n
+; CHECK-NEXT:     p1: %m
+; CHECK-NEXT:     Arrays {
+; CHECK-NEXT:         double MemRef_A[*][8] // Element size 8
+; CHECK-NEXT:         double MemRef_B[*][8] // Element size 8
+; CHECK-NEXT:         double MemRef_C[*][8] // Element size 8
+; CHECK-NEXT:     }
+; CHECK-NEXT:     Arrays (Bounds as pw_affs) {
+; CHECK-NEXT:         double MemRef_A[*][ { [] -> [(8)] } ] // Element size 8
+; CHECK-NEXT:         double MemRef_B[*][ { [] -> [(8)] } ] // Element size 8
+; CHECK-NEXT:         double MemRef_C[*][ { [] -> [(8)] } ] // Element size 8
+; CHECK-NEXT:     }
+; CHECK-NEXT:     Alias Groups (0):
+; CHECK-NEXT:         n/a
+; CHECK-NEXT:     Statements {
+; CHECK-NEXT:       Stmt_parallel_for
+; CHECK-NEXT:             Domain :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_parallel_for[i0] : i0 >= 0 and i0 <= n; Stmt_parallel_for[0] : n <= -1 };
+; CHECK-NEXT:             Schedule :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_parallel_for[i0] -> [i0, 0, 0] : i0 <= n; Stmt_parallel_for[0] -> [0, 0, 0] : n <= -1 };
+; CHECK-NEXT:             ReadAccess := [Reduction Type: NONE] [MAPPED]
+; CHECK-NEXT:                 [n, m] -> { Stmt_parallel_for[i0] -> MemRef_A[i0] };
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [MAPPED]
+; CHECK-NEXT:                 [n, m] -> { Stmt_parallel_for[i0] -> MemRef_B[i0] };
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [MAPPED]
+; CHECK-NEXT:                 [n, m] -> { Stmt_parallel_for[i0] -> MemRef_B[i0] };
+; CHECK-NEXT:       Stmt_body
+; CHECK-NEXT:             Domain :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_body[i0, i1] : i0 >= 0 and i0 <= -1 + n and i1 >= 0 and i1 <= -1 + m };
+; CHECK-NEXT:             Schedule :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_body[i0, i1] -> [i0, 1, i1] };
+; CHECK-NEXT:             ReadAccess := [Reduction Type: NONE] [MAPPED]
+; CHECK-NEXT:                 [n, m] -> { Stmt_body[i0, i1] -> MemRef_A[i0] };
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [MAPPED]
+; CHECK-NEXT:                 [n, m] -> { Stmt_body[i0, i1] -> MemRef_A[i0] };
+; CHECK-NEXT:       Stmt_parallel_inc
+; CHECK-NEXT:             Domain :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_parallel_inc[i0] : i0 >= 0 and i0 <= -1 + n };
+; CHECK-NEXT:             Schedule :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_parallel_inc[i0] -> [i0, 2, 0] };
+; CHECK-NEXT:             ReadAccess := [Reduction Type: NONE] [MAPPED]
+; CHECK-NEXT:                 [n, m] -> { Stmt_parallel_inc[i0] -> MemRef_A[i0] };
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [MAPPED]
+; CHECK-NEXT:                 [n, m] -> { Stmt_parallel_inc[i0] -> MemRef_C[i0] };
+; CHECK-NEXT:     }
+; CHECK-NEXT: Printing analysis 'Polly - Create polyhedral description of Scops' for region: 'entry => <Function Return>' in function 'func':
+; CHECK-NEXT: Invalid Scop!

test/ScopInfo/delicm_LICM_nested_reductions.ll

+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+;
+;    void func(int n, double A[static const restrict n], int m) {
+;      for (int j = 0; j < n; j += 1) { /* parallel loop */
+;        double red = A[j];
+;        for (int i = 0; i < m; i += 1) /* reduction loop */
+;          for (int k = 0; k < m; k += 1) /* reduction loop */
+;            red += 4.2;
+;        A[j] = red;
+;    }
+
+; Two nested loop-carried phis able to reuse the same %arrayidx
+; Possible difficulties:
+; - Identify that both phis can use the same %arrayidx as scratch space
+
+define void @func(i32 %n, double* noalias nonnull %A, i32 %m) {
+entry:
+  br label %parallel.for
+
+parallel.for:
+  %j = phi i32 [0, %entry], [%j.inc, %parallel.inc]
+  %arrayidx = getelementptr inbounds double, double* %A, i32 %j
+  %ld = load double, double* %arrayidx
+  %j.cmp = icmp slt i32 %j, %n
+  br i1 %j.cmp, label %reduction_outer.for, label %return
+
+reduction_outer.for:
+  %i_outer = phi i32 [0, %parallel.for], [%i_outer.inc, %reduction_outer.inc]
+  %phi_outer = phi double [%ld, %parallel.for], [%phi_inner, %reduction_outer.inc]
+  %i_outer.cmp = icmp slt i32 %i_outer, %m
+  br i1 %i_outer.cmp, label %reduction_inner.for, label %parallel.inc
+
+reduction_inner.for:
+  %i_inner = phi i32 [0, %reduction_outer.for], [%i_inner.inc, %reduction_inner.inc]
+  %phi_inner = phi double [%ld, %reduction_outer.for], [%add, %reduction_inner.inc]
+  %i_inner.cmp = icmp slt i32 %i_inner, %m
+  br i1 %i_inner.cmp, label %body, label %reduction_outer.inc
+
+body:
+  %add = fadd double %phi_inner, 4.2
+  br label %reduction_inner.inc
+
+reduction_inner.inc:
+  %i_inner.inc = add nuw nsw i32 %i_inner, 1
+  br label %reduction_inner.for
+
+reduction_outer.inc:
+  %i_outer.inc = add nuw nsw i32 %i_outer, 1
+  br label %reduction_outer.for
+
+parallel.inc:
+  store double %phi_outer, double* %arrayidx
+  %j.inc = add nuw nsw i32 %j, 1
+  br label %parallel.for
+
+return:
+  ret void
+}
+
+
+; CHECK: Printing analysis 'Polly - Create polyhedral description of Scops' for region: 'reduction_inner.for => reduction_outer.inc' in function 'func':
+; CHECK-NEXT: Invalid Scop!
+; CHECK-NEXT: Printing analysis 'Polly - Create polyhedral description of Scops' for region: 'reduction_outer.for => parallel.inc' in function 'func':
+; CHECK-NEXT: Invalid Scop!
+; CHECK-NEXT: Printing analysis 'Polly - Create polyhedral description of Scops' for region: 'parallel.for => return' in function 'func':
+; CHECK-NEXT:     Function: func
+; CHECK-NEXT:     Region: %parallel.for---%return
+; CHECK-NEXT:     Max Loop Depth:  3
+; CHECK-NEXT:     Invariant Accesses: {
+; CHECK-NEXT:     }
+; CHECK-NEXT:     Context:
+; CHECK-NEXT:     [n, m] -> {  : n >= -2147483648 and n <= 2147483647 and m >= -2147483648 and m <= 2147483647 }
+; CHECK-NEXT:     Assumed Context:
+; CHECK-NEXT:     [n, m] -> {  :  }
+; CHECK-NEXT:     Boundary Context:
+; CHECK-NEXT:     [n, m] -> {  :  }
+; CHECK-NEXT:     p0: %n
+; CHECK-NEXT:     p1: %m
+; CHECK-NEXT:     Arrays {
+; CHECK-NEXT:         double MemRef_A[*][8] // Element size 8
+; CHECK-NEXT:         double MemRef_ld[*] [BasePtrOrigin: MemRef_A] // Element size 8
+; CHECK-NEXT:         double MemRef_phi_inner__phi[*] // Element size 8
+; CHECK-NEXT:         double MemRef_add[*] // Element size 8
+; CHECK-NEXT:     }
+; CHECK-NEXT:     Arrays (Bounds as pw_affs) {
+; CHECK-NEXT:         double MemRef_A[*][ { [] -> [(8)] } ] // Element size 8
+; CHECK-NEXT:         double MemRef_ld[*] [BasePtrOrigin: MemRef_A] // Element size 8
+; CHECK-NEXT:         double MemRef_phi_inner__phi[*] // Element size 8
+; CHECK-NEXT:         double MemRef_add[*] // Element size 8
+; CHECK-NEXT:     }
+; CHECK-NEXT:     Alias Groups (0):
+; CHECK-NEXT:         n/a
+; CHECK-NEXT:     Statements {
+; CHECK-NEXT:       Stmt_parallel_for
+; CHECK-NEXT:             Domain :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_parallel_for[i0] : i0 >= 0 and i0 <= n; Stmt_parallel_for[0] : n <= -1 };
+; CHECK-NEXT:             Schedule :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_parallel_for[i0] -> [i0, 0, 0, 0, 0, 0] : i0 <= n; Stmt_parallel_for[0] -> [0, 0, 0, 0, 0, 0] : n <= -1 };
+; CHECK-NEXT:             ReadAccess := [Reduction Type: NONE] [MAPPED]
+; CHECK-NEXT:                 [n, m] -> { Stmt_parallel_for[i0] -> MemRef_A[i0] };
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 [n, m] -> { Stmt_parallel_for[i0] -> MemRef_ld[] };
+; CHECK-NEXT:       Stmt_reduction_outer_for
+; CHECK-NEXT:             Domain :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_reduction_outer_for[i0, i1] : i0 >= 0 and i0 <= -1 + n and i1 >= 0 and i1 <= m; Stmt_reduction_outer_for[i0, 0] : m <= -1 and i0 >= 0 and i0 <= -1 + n };
+; CHECK-NEXT:             Schedule :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_reduction_outer_for[i0, i1] -> [i0, 1, i1, 0, 0, 0] : i1 <= m; Stmt_reduction_outer_for[i0, 0] -> [i0, 1, 0, 0, 0, 0] : m <= -1 };
+; CHECK-NEXT:             ReadAccess := [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 [n, m] -> { Stmt_reduction_outer_for[i0, i1] -> MemRef_ld[] };
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 [n, m] -> { Stmt_reduction_outer_for[i0, i1] -> MemRef_phi_inner__phi[] };
+; CHECK-NEXT:       Stmt_reduction_inner_for
+; CHECK-NEXT:             Domain :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_reduction_inner_for[i0, i1, i2] : i0 >= 0 and i0 <= -1 + n and i1 >= 0 and i1 <= -1 + m and i2 >= 0 and i2 <= m };
+; CHECK-NEXT:             Schedule :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_reduction_inner_for[i0, i1, i2] -> [i0, 1, i1, 1, i2, 0] };
+; CHECK-NEXT:             ReadAccess := [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 [n, m] -> { Stmt_reduction_inner_for[i0, i1, i2] -> MemRef_phi_inner__phi[] };
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [MAPPED]
+; CHECK-NEXT:                 [n, m] -> { Stmt_reduction_inner_for[i0, i1, i2] -> MemRef_A[i0] };
+; CHECK-NEXT:       Stmt_body
+; CHECK-NEXT:             Domain :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_body[i0, i1, i2] : i0 >= 0 and i0 <= -1 + n and i1 >= 0 and i1 <= -1 + m and i2 >= 0 and i2 <= -1 + m };
+; CHECK-NEXT:             Schedule :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_body[i0, i1, i2] -> [i0, 1, i1, 1, i2, 1] };
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 [n, m] -> { Stmt_body[i0, i1, i2] -> MemRef_add[] };
+; CHECK-NEXT:             ReadAccess := [Reduction Type: NONE] [MAPPED]
+; CHECK-NEXT:                 [n, m] -> { Stmt_body[i0, i1, i2] -> MemRef_A[i0] };
+; CHECK-NEXT:       Stmt_reduction_inner_inc
+; CHECK-NEXT:             Domain :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_reduction_inner_inc[i0, i1, i2] : i0 >= 0 and i0 <= -1 + n and i1 >= 0 and i1 <= -1 + m and i2 >= 0 and i2 <= -1 + m };
+; CHECK-NEXT:             Schedule :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_reduction_inner_inc[i0, i1, i2] -> [i0, 1, i1, 1, i2, 2] };
+; CHECK-NEXT:             ReadAccess := [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 [n, m] -> { Stmt_reduction_inner_inc[i0, i1, i2] -> MemRef_add[] };
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 [n, m] -> { Stmt_reduction_inner_inc[i0, i1, i2] -> MemRef_phi_inner__phi[] };
+; CHECK-NEXT:     }
+; CHECK-NEXT: Printing analysis 'Polly - Create polyhedral description of Scops' for region: 'entry => <Function Return>' in function 'func':
+; CHECK-NEXT: Invalid Scop!

test/ScopInfo/delicm_LICM_nonaffine.ll

+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+;
+;    void func(int n, double A[static const restrict n], int m) {
+;      for (int j = 0; j < n; j += 1) { /* parallel loop */
+;        double red = A[j];
+;        for (int i = 0; i < m; i += 1) /* reduction loop */
+;          if (i*i == 0)
+;            red += 4.2;
+;        A[j] = red;
+;    }
+
+; Body is non-affine subregion
+; Possible difficulties:
+; - Can move through non-affine subregions?
+
+define void @func(i32 %n, double* noalias nonnull %A, i32 %m) {
+entry:
+  br label %parallel.for
+
+parallel.for:
+  %j = phi i32 [0, %entry], [%j.inc, %parallel.inc]
+  %arrayidx = getelementptr inbounds double, double* %A, i32 %j
+  %ld = load double, double* %arrayidx
+  %j.cmp = icmp slt i32 %j, %n
+  br i1 %j.cmp, label %reduction.for, label %return
+
+reduction.for:
+  %i = phi i32 [0, %parallel.for], [%i.inc, %body], [%i.inc, %body.true]
+  %phi = phi double [%ld, %parallel.for], [%phi, %body], [%add, %body.true]
+  %i.cmp = icmp slt i32 %i, %m
+  %i.inc = add nuw nsw i32 %i, 1
+  br i1 %i.cmp, label %body, label %parallel.inc
+
+body:
+  %sqr = mul i32 %i, %i
+  %cond = icmp eq i32 %sqr, 0
+  br i1 %cond, label %body.true, label %reduction.for
+
+body.true:
+  %add = fadd double %phi, 4.2
+  br label %reduction.for
+
+parallel.inc:
+  store double %phi, double* %arrayidx
+  %j.inc = add nuw nsw i32 %j, 1
+  br label %parallel.for
+
+return:
+  ret void
+}
+
+
+; CHECK: Printing analysis 'Polly - Create polyhedral description of Scops' for region: 'body => reduction.for' in function 'func':
+; CHECK-NEXT:     Function: func
+; CHECK-NEXT:     Region: %body---%reduction.for
+; CHECK-NEXT:     Max Loop Depth:  1
+; CHECK-NEXT:     Invariant Accesses: {
+; CHECK-NEXT:     }
+; CHECK-NEXT:     Context:
+; CHECK-NEXT:     {  :  }
+; CHECK-NEXT:     Assumed Context:
+; CHECK-NEXT:     {  :  }
+; CHECK-NEXT:     Boundary Context:
+; CHECK-NEXT:     {  :  }
+; CHECK-NEXT:     Arrays {
+; CHECK-NEXT:         double MemRef_phi[*] // Element size 8
+; CHECK-NEXT:         i32 MemRef_i[*] // Element size 4
+; CHECK-NEXT:     }
+; CHECK-NEXT:     Arrays (Bounds as pw_affs) {
+; CHECK-NEXT:         double MemRef_phi[*] // Element size 8
+; CHECK-NEXT:         i32 MemRef_i[*] // Element size 4
+; CHECK-NEXT:     }
+; CHECK-NEXT:     Alias Groups (0):
+; CHECK-NEXT:         n/a
+; CHECK-NEXT:     Statements {
+; CHECK-NEXT:       Stmt_body__TO__reduction_for
+; CHECK-NEXT:             Domain :=
+; CHECK-NEXT:                 { Stmt_body__TO__reduction_for[] };
+; CHECK-NEXT:             Schedule :=
+; CHECK-NEXT:                 { Stmt_body__TO__reduction_for[] -> [] };
+; CHECK-NEXT:             ReadAccess := [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 { Stmt_body__TO__reduction_for[] -> MemRef_phi[] };
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 { Stmt_body__TO__reduction_for[] -> MemRef_i[] };
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 { Stmt_body__TO__reduction_for[] -> MemRef_phi[] };
+; CHECK-NEXT:     }
+; CHECK-NEXT: Printing analysis 'Polly - Create polyhedral description of Scops' for region: 'reduction.for => parallel.inc' in function 'func':
+; CHECK-NEXT: Invalid Scop!
+; CHECK-NEXT: Printing analysis 'Polly - Create polyhedral description of Scops' for region: 'parallel.for => return' in function 'func':
+; CHECK-NEXT: Invalid Scop!
+; CHECK-NEXT: Printing analysis 'Polly - Create polyhedral description of Scops' for region: 'entry => <Function Return>' in function 'func':
+; CHECK-NEXT: Invalid Scop!

test/ScopInfo/delicm_LICM_reduction.ll

+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+;
+;    void func(int n, double A[static const restrict n], int m) {
+;      for (int j = 0; j < n; j += 1) { /* parallel loop */
+;        double red = A[j];
+;        for (int i = 0; i < m; i += 1) /* reduction loop */
+;          red += 4.2;
+;        A[j] = red;
+;    }
+
+; Nested reduction standard case; After LICM 
+; Possible difficulties:
+; - Put the store into %body or $reduction.inc
+; - Replace %phi in %body with a load, knowing that after the store has been placed in %body or %reduction.inc, it contains %phi
+; - Except the store, all instructions are "rematerializable", when applying the same logic to the loop-carried %phi, so the naive algorithm might try to move all instructions into %parallel.inc and remove the one in %body
+; - There can be no mapped store added to parallel.for (for the %phi) because it is not postdominated by the store  
+
+define void @func(i32 %n, double* noalias nonnull %A, i32 %m) {
+entry:
+  br label %parallel.for
+
+parallel.for:
+  %j = phi i32 [0, %entry], [%j.inc, %parallel.inc]
+  %arrayidx = getelementptr inbounds double, double* %A, i32 %j
+  %ld = load double, double* %arrayidx
+  %j.cmp = icmp slt i32 %j, %n
+  br i1 %j.cmp, label %reduction.for, label %return
+
+reduction.for:
+  %i = phi i32 [0, %parallel.for], [%i.inc, %reduction.inc]
+  %phi = phi double [%ld, %parallel.for], [%add, %reduction.inc]
+  %i.cmp = icmp slt i32 %i, %m
+  br i1 %i.cmp, label %body, label %parallel.inc
+
+body:
+  %add = fadd double %phi, 4.2
+  br label %reduction.inc
+
+reduction.inc:
+  %i.inc = add nuw nsw i32 %i, 1
+  br label %reduction.for
+
+parallel.inc:
+  store double %phi, double* %arrayidx
+  %j.inc = add nuw nsw i32 %j, 1
+  br label %parallel.for
+
+return:
+  ret void
+}
+
+
+; CHECK: Printing analysis 'Polly - Create polyhedral description of Scops' for region: 'reduction.for => parallel.inc' in function 'func':
+; CHECK-NEXT: Invalid Scop!
+; CHECK-NEXT: Printing analysis 'Polly - Create polyhedral description of Scops' for region: 'parallel.for => return' in function 'func':
+; CHECK-NEXT:     Function: func
+; CHECK-NEXT:     Region: %parallel.for---%return
+; CHECK-NEXT:     Max Loop Depth:  2
+; CHECK-NEXT:     Invariant Accesses: {
+; CHECK-NEXT:     }
+; CHECK-NEXT:     Context:
+; CHECK-NEXT:     [n, m] -> {  : n >= -2147483648 and n <= 2147483647 and m >= -2147483648 and m <= 2147483647 }
+; CHECK-NEXT:     Assumed Context:
+; CHECK-NEXT:     [n, m] -> {  :  }
+; CHECK-NEXT:     Boundary Context:
+; CHECK-NEXT:     [n, m] -> {  :  }
+; CHECK-NEXT:     p0: %n
+; CHECK-NEXT:     p1: %m
+; CHECK-NEXT:     Arrays {
+; CHECK-NEXT:         double MemRef_A[*][8] // Element size 8
+; CHECK-NEXT:     }
+; CHECK-NEXT:     Arrays (Bounds as pw_affs) {
+; CHECK-NEXT:         double MemRef_A[*][ { [] -> [(8)] } ] // Element size 8
+; CHECK-NEXT:     }
+; CHECK-NEXT:     Alias Groups (0):
+; CHECK-NEXT:         n/a
+; CHECK-NEXT:     Statements {
+; CHECK-NEXT:       Stmt_body
+; CHECK-NEXT:             Domain :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_body[i0, i1] : i0 >= 0 and i0 <= -1 + n and i1 >= 0 and i1 <= -1 + m };
+; CHECK-NEXT:             Schedule :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_body[i0, i1] -> [i0, i1] };
+; CHECK-NEXT:             ReadAccess := [Reduction Type: NONE] [MAPPED]
+; CHECK-NEXT:                 [n, m] -> { Stmt_body[i0, i1] -> MemRef_A[i0] };
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [MAPPED]
+; CHECK-NEXT:                 [n, m] -> { Stmt_body[i0, i1] -> MemRef_A[i0] };
+; CHECK-NEXT:     }
+; CHECK-NEXT: Printing analysis 'Polly - Create polyhedral description of Scops' for region: 'entry => <Function Return>' in function 'func':
+; CHECK-NEXT: Invalid Scop!

test/ScopInfo/delicm_LICM_split.ll

+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+;
+;    void func(int n, double A[static const restrict n], int m, double B[static const restrict m]) {
+;      for (int j = 0; j < n; j += 1) { /* parallel loop */
+;        double red = A[j];
+;        for (int i = 0; i < m; i += 1) { /* reduction loop */
+;          red += B[i]; /* assume B[i] non-rematerializable */
+;          <split>
+;          red += B[m-i]; /* assume B[m-i] non-rematerializable */
+;        }
+;        A[j] = red;
+;    }
+
+; Body is split into multiple blocks
+; Some more complicated could between body and body.split might keep the block from being joind into one
+; Possible difficulties:
+; - Does body and body.split get their own stores?
+; - If not, does a scalar dependency between them remain?
+
+define void @func(i32 %n, double* noalias nonnull %A, i32 %m, double* noalias nonnull %B) {
+entry:
+  br label %parallel.for
+
+parallel.for:
+  %j = phi i32 [0, %entry], [%j.inc, %parallel.inc]
+  %arrayidx = getelementptr inbounds double, double* %A, i32 %j
+  %ld = load double, double* %arrayidx
+  %j.cmp = icmp slt i32 %j, %n
+  br i1 %j.cmp, label %reduction.for, label %return
+
+reduction.for:
+  %i = phi i32 [0, %parallel.for], [%i.inc, %reduction.inc]
+  %phi = phi double [%ld, %parallel.for], [%add2, %reduction.inc]
+  %i.cmp = icmp slt i32 %i, %m
+  br i1 %i.cmp, label %body, label %parallel.inc
+
+body:
+  %arrayidxB1 = getelementptr inbounds double, double* %B, i32 %i
+  %B1 = load double, double* %arrayidxB1  ; assume non-rematerializable
+  %add1 = fadd double %phi, %B1
+  br label %body.split
+
+body.split:
+  %minusi = sub nuw nsw i32 %m, %i
+  %arrayidxB2 = getelementptr inbounds double, double* %B, i32 %minusi
+  %B2 = load double, double* %arrayidxB2  ; assume non-rematerializable
+  %add2 = fadd double %add1, %B2
+  br label %reduction.inc
+
+reduction.inc:
+  %i.inc = add nuw nsw i32 %i, 1
+  br label %reduction.for
+  
+parallel.inc:
+  store double %phi, double* %arrayidx
+  %j.inc = add nuw nsw i32 %j, 1
+  br label %parallel.for
+
+return:
+  ret void
+}
+
+
+; CHECK: Printing analysis 'Polly - Create polyhedral description of Scops' for region: 'reduction.for => parallel.inc' in function 'func':
+; CHECK-NEXT: Invalid Scop!
+; CHECK-NEXT: Printing analysis 'Polly - Create polyhedral description of Scops' for region: 'parallel.for => return' in function 'func':
+; CHECK-NEXT:     Function: func
+; CHECK-NEXT:     Region: %parallel.for---%return
+; CHECK-NEXT:     Max Loop Depth:  2
+; CHECK-NEXT:     Invariant Accesses: {
+; CHECK-NEXT:     }
+; CHECK-NEXT:     Context:
+; CHECK-NEXT:     [n, m] -> {  : n >= -2147483648 and n <= 2147483647 and m >= -2147483648 and m <= 2147483647 }
+; CHECK-NEXT:     Assumed Context:
+; CHECK-NEXT:     [n, m] -> {  :  }
+; CHECK-NEXT:     Boundary Context:
+; CHECK-NEXT:     [n, m] -> {  :  }
+; CHECK-NEXT:     p0: %n
+; CHECK-NEXT:     p1: %m
+; CHECK-NEXT:     Arrays {
+; CHECK-NEXT:         double MemRef_A[*][8] // Element size 8
+; CHECK-NEXT:         double MemRef_B[*][8] // Element size 8
+; CHECK-NEXT:     }
+; CHECK-NEXT:     Arrays (Bounds as pw_affs) {
+; CHECK-NEXT:         double MemRef_A[*][ { [] -> [(8)] } ] // Element size 8
+; CHECK-NEXT:         double MemRef_B[*][ { [] -> [(8)] } ] // Element size 8
+; CHECK-NEXT:     }
+; CHECK-NEXT:     Alias Groups (0):
+; CHECK-NEXT:         n/a
+; CHECK-NEXT:     Statements {
+; CHECK-NEXT:       Stmt_body
+; CHECK-NEXT:             Domain :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_body[i0, i1] : i0 >= 0 and i0 <= -1 + n and i1 >= 0 and i1 <= -1 + m };
+; CHECK-NEXT:             Schedule :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_body[i0, i1] -> [i0, i1, 0] };
+; CHECK-NEXT:             ReadAccess := [Reduction Type: NONE] [MAPPED]
+; CHECK-NEXT:                 [n, m] -> { Stmt_body[i0, i1] -> MemRef_B[i1] };
+; CHECK-NEXT:             ReadAccess := [Reduction Type: NONE] [MAPPED]
+; CHECK-NEXT:                 [n, m] -> { Stmt_body[i0, i1] -> MemRef_A[i0] };
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [MAPPED]
+; CHECK-NEXT:                 [n, m] -> { Stmt_body[i0, i1] -> MemRef_A[i0] };
+; CHECK-NEXT:       Stmt_body_split
+; CHECK-NEXT:             Domain :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_body_split[i0, i1] : i0 >= 0 and i0 <= -1 + n and i1 >= 0 and i1 <= -1 + m };
+; CHECK-NEXT:             Schedule :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_body_split[i0, i1] -> [i0, i1, 1] };
+; CHECK-NEXT:             ReadAccess := [Reduction Type: NONE] [MAPPED]
+; CHECK-NEXT:                 [n, m] -> { Stmt_body_split[i0, i1] -> MemRef_B[m - i1] };
+; CHECK-NEXT:             ReadAccess := [Reduction Type: NONE] [MAPPED]
+; CHECK-NEXT:                 [n, m] -> { Stmt_body_split[i0, i1] -> MemRef_A[i0] };
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [MAPPED]
+; CHECK-NEXT:                 [n, m] -> { Stmt_body_split[i0, i1] -> MemRef_A[i0] };
+; CHECK-NEXT:     }
+; CHECK-NEXT: Printing analysis 'Polly - Create polyhedral description of Scops' for region: 'entry => <Function Return>' in function 'func':
+; CHECK-NEXT: Invalid Scop!

test/ScopInfo/delicm_LICM_two_reductions.ll

+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+;
+;    void func(int n, double A[static const restrict n], int m) {
+;      for (int j = 0; j < n; j += 1) { /* parallel loop */
+;        double red1 = A[j];
+;        double red2 = 0.0;
+;        for (int i = 0; i < m; i += 1) { /* reduction loop */
+;          red1 += 4.2;
+;          red2 += 2.4;
+;        }
+;        A[j] = red1 + red2;
+;    }
+
+; Two reductions in the same loop 
+; Possible difficulties:
+; - Cannot use same %arraryidx for same loop-carried phi; must identify situation and choose one.
+; - If doing global analysis first, must somehow mark already used %arrayidx to avoid use by other reduction
+; - If transforming while doing analysis, analysis for second phi must work on updated MemoryAccesses
+
+define void @func(i32 %n, double* noalias nonnull %A, i32 %m) {
+entry:
+  br label %parallel.for
+
+parallel.for:
+  %j = phi i32 [0, %entry], [%j.inc, %parallel.inc]
+  %arrayidx = getelementptr inbounds double, double* %A, i32 %j
+  %ld = load double, double* %arrayidx
+  %j.cmp = icmp slt i32 %j, %n
+  br i1 %j.cmp, label %reduction.for, label %return
+
+reduction.for:
+  %i = phi i32 [0, %parallel.for], [%i.inc, %reduction.inc]
+  %phi1 = phi double [%ld, %parallel.for], [%add1, %reduction.inc]
+  %phi2 = phi double [0.0, %parallel.for], [%add2, %reduction.inc]
+  %i.cmp = icmp slt i32 %i, %m
+  br i1 %i.cmp, label %body, label %parallel.inc
+
+body:
+  %add1 = fadd double %phi1, 4.2
+  %add2 = fadd double %phi2, 2.4
+  br label %reduction.inc
+
+reduction.inc:
+  %i.inc = add nuw nsw i32 %i, 1
+  br label %reduction.for
+
+parallel.inc:
+  %sum = fadd double %phi1, %phi2
+  store double %sum, double* %arrayidx
+  %j.inc = add nuw nsw i32 %j, 1
+  br label %parallel.for
+
+return:
+  ret void
+}
+
+
+; CHECK: Printing analysis 'Polly - Create polyhedral description of Scops' for region: 'reduction.for => parallel.inc' in function 'func':
+; CHECK-NEXT: Invalid Scop!
+; CHECK-NEXT: Printing analysis 'Polly - Create polyhedral description of Scops' for region: 'parallel.for => return' in function 'func':
+; CHECK-NEXT:     Function: func
+; CHECK-NEXT:     Region: %parallel.for---%return
+; CHECK-NEXT:     Max Loop Depth:  2
+; CHECK-NEXT:     Invariant Accesses: {
+; CHECK-NEXT:     }
+; CHECK-NEXT:     Context:
+; CHECK-NEXT:     [n, m] -> {  : n >= -2147483648 and n <= 2147483647 and m >= -2147483648 and m <= 2147483647 }
+; CHECK-NEXT:     Assumed Context:
+; CHECK-NEXT:     [n, m] -> {  :  }
+; CHECK-NEXT:     Boundary Context:
+; CHECK-NEXT:     [n, m] -> {  :  }
+; CHECK-NEXT:     p0: %n
+; CHECK-NEXT:     p1: %m
+; CHECK-NEXT:     Arrays {
+; CHECK-NEXT:         double MemRef_A[*][8] // Element size 8
+; CHECK-NEXT:         double MemRef_phi1__phi[*] // Element size 8
+; CHECK-NEXT:         double MemRef_phi1[*] // Element size 8
+; CHECK-NEXT:         double MemRef_add1[*] // Element size 8
+; CHECK-NEXT:     }
+; CHECK-NEXT:     Arrays (Bounds as pw_affs) {
+; CHECK-NEXT:         double MemRef_A[*][ { [] -> [(8)] } ] // Element size 8
+; CHECK-NEXT:         double MemRef_phi1__phi[*] // Element size 8
+; CHECK-NEXT:         double MemRef_phi1[*] // Element size 8
+; CHECK-NEXT:         double MemRef_add1[*] // Element size 8
+; CHECK-NEXT:     }
+; CHECK-NEXT:     Alias Groups (0):
+; CHECK-NEXT:         n/a
+; CHECK-NEXT:     Statements {
+; CHECK-NEXT:       Stmt_parallel_for
+; CHECK-NEXT:             Domain :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_parallel_for[i0] : i0 >= 0 and i0 <= n; Stmt_parallel_for[0] : n <= -1 };
+; CHECK-NEXT:             Schedule :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_parallel_for[i0] -> [i0, 0, 0, 0] : i0 <= n; Stmt_parallel_for[0] -> [0, 0, 0, 0] : n <= -1 };
+; CHECK-NEXT:             ReadAccess := [Reduction Type: NONE] [MAPPED]
+; CHECK-NEXT:                 [n, m] -> { Stmt_parallel_for[i0] -> MemRef_A[i0] };
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 [n, m] -> { Stmt_parallel_for[i0] -> MemRef_phi1__phi[] };
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [MAPPED]
+; CHECK-NEXT:                 [n, m] -> { Stmt_parallel_for[i0] -> MemRef_A[i0] };
+; CHECK-NEXT:       Stmt_reduction_for
+; CHECK-NEXT:             Domain :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_reduction_for[i0, i1] : i0 >= 0 and i0 <= -1 + n and i1 >= 0 and i1 <= m; Stmt_reduction_for[i0, 0] : m <= -1 and i0 >= 0 and i0 <= -1 + n };
+; CHECK-NEXT:             Schedule :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_reduction_for[i0, i1] -> [i0, 1, i1, 0] : i1 <= m; Stmt_reduction_for[i0, 0] -> [i0, 1, 0, 0] : m <= -1 };
+; CHECK-NEXT:             ReadAccess := [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 [n, m] -> { Stmt_reduction_for[i0, i1] -> MemRef_phi1__phi[] };
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 [n, m] -> { Stmt_reduction_for[i0, i1] -> MemRef_phi1[] };
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [MAPPED]
+; CHECK-NEXT:                 [n, m] -> { Stmt_reduction_for[i0, i1] -> MemRef_A[i0] };
+; CHECK-NEXT:       Stmt_body
+; CHECK-NEXT:             Domain :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_body[i0, i1] : i0 >= 0 and i0 <= -1 + n and i1 >= 0 and i1 <= -1 + m };
+; CHECK-NEXT:             Schedule :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_body[i0, i1] -> [i0, 1, i1, 1] };
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 [n, m] -> { Stmt_body[i0, i1] -> MemRef_add1[] };
+; CHECK-NEXT:             ReadAccess := [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 [n, m] -> { Stmt_body[i0, i1] -> MemRef_phi1[] };
+; CHECK-NEXT:             ReadAccess := [Reduction Type: NONE] [MAPPED]
+; CHECK-NEXT:                 [n, m] -> { Stmt_body[i0, i1] -> MemRef_A[i0] };
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [MAPPED]
+; CHECK-NEXT:                 [n, m] -> { Stmt_body[i0, i1] -> MemRef_A[i0] };
+; CHECK-NEXT:       Stmt_reduction_inc
+; CHECK-NEXT:             Domain :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_reduction_inc[i0, i1] : i0 >= 0 and i0 <= -1 + n and i1 >= 0 and i1 <= -1 + m };
+; CHECK-NEXT:             Schedule :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_reduction_inc[i0, i1] -> [i0, 1, i1, 2] };
+; CHECK-NEXT:             ReadAccess := [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 [n, m] -> { Stmt_reduction_inc[i0, i1] -> MemRef_add1[] };
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 [n, m] -> { Stmt_reduction_inc[i0, i1] -> MemRef_phi1__phi[] };
+; CHECK-NEXT:       Stmt_parallel_inc
+; CHECK-NEXT:             Domain :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_parallel_inc[i0] : i0 >= 0 and i0 <= -1 + n };
+; CHECK-NEXT:             Schedule :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_parallel_inc[i0] -> [i0, 2, 0, 0] };
+; CHECK-NEXT:             ReadAccess := [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 [n, m] -> { Stmt_parallel_inc[i0] -> MemRef_phi1[] };
+; CHECK-NEXT:             ReadAccess := [Reduction Type: NONE] [MAPPED]
+; CHECK-NEXT:                 [n, m] -> { Stmt_parallel_inc[i0] -> MemRef_A[i0] };
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [MAPPED]
+; CHECK-NEXT:                 [n, m] -> { Stmt_parallel_inc[i0] -> MemRef_A[i0] };
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [MAPPED]
+; CHECK-NEXT:                 [n, m] -> { Stmt_parallel_inc[i0] -> MemRef_A[i0] };
+; CHECK-NEXT:     }
+; CHECK-NEXT: Printing analysis 'Polly - Create polyhedral description of Scops' for region: 'entry => <Function Return>' in function 'func':
+; CHECK-NEXT: Invalid Scop!

test/ScopInfo/delicm_LICM_writes.ll

+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+;
+;    void func(int n, double A[static const restrict n], int m, int k) {
+;      for (int j = 0; j < n; j += 1) { /* parallel loop */
+;        A[k] = 2.1;
+;        double red = A[j];
+;        for (int i = 0; i < m; i += 1) /* reduction loop */
+;          red += 4.2;
+;        A[j] = red;
+;        A[k] = 2.3;
+;    }
+
+; %arraidx possibly overwritten, but not in anything relevant for the reduction
+; Possible difficulties:
+; - Store of 2.1 might overwrite A[j] if order reversed in %parallel.for (distinguish the two cases)
+; - Store of 2.3 might overwrite A[j]; distinguish from case where order is reversed in %parallel.inc
+
+define void @func(i32 %n, double* noalias nonnull %A, i32 %m, i32 %k) {
+entry:
+  br label %parallel.for
+
+parallel.for:
+  %j = phi i32 [0, %entry], [%j.inc, %parallel.inc]
+  %arrayidxk = getelementptr inbounds double, double* %A, i32 %k
+  store double 2.1, double* %arrayidxk
+  %arrayidx = getelementptr inbounds double, double* %A, i32 %j
+  %ld = load double, double* %arrayidx
+  %j.cmp = icmp slt i32 %j, %n
+  br i1 %j.cmp, label %reduction.for, label %return
+
+reduction.for:
+  %i = phi i32 [0, %parallel.for], [%i.inc, %reduction.inc]
+  %phi = phi double [%ld, %parallel.for], [%add, %reduction.inc]
+  %i.cmp = icmp slt i32 %i, %m
+  br i1 %i.cmp, label %body, label %parallel.inc
+
+body:
+  %add = fadd double %phi, 4.2
+  br label %reduction.inc
+
+reduction.inc:
+  %i.inc = add nuw nsw i32 %i, 1
+  br label %reduction.for
+
+parallel.inc:
+  store double %phi, double* %arrayidx
+  store double 2.3, double* %arrayidxk
+  %j.inc = add nuw nsw i32 %j, 1
+  br label %parallel.for
+
+return:
+  ret void
+}
+
+
+; CHECK: Printing analysis 'Polly - Create polyhedral description of Scops' for region: 'reduction.for => parallel.inc' in function 'func':
+; CHECK-NEXT: Invalid Scop!
+; CHECK-NEXT: Printing analysis 'Polly - Create polyhedral description of Scops' for region: 'parallel.for => return' in function 'func':
+; CHECK-NEXT:     Function: func
+; CHECK-NEXT:     Region: %parallel.for---%return
+; CHECK-NEXT:     Max Loop Depth:  2
+; CHECK-NEXT:     Invariant Accesses: {
+; CHECK-NEXT:     }
+; CHECK-NEXT:     Context:
+; CHECK-NEXT:     [n, m, k] -> {  : n >= -2147483648 and n <= 2147483647 and m >= -2147483648 and m <= 2147483647 and k >= -2147483648 and k <= 2147483647 }
+; CHECK-NEXT:     Assumed Context:
+; CHECK-NEXT:     [n, m, k] -> {  :  }
+; CHECK-NEXT:     Boundary Context:
+; CHECK-NEXT:     [n, m, k] -> {  :  }
+; CHECK-NEXT:     p0: %n
+; CHECK-NEXT:     p1: %m
+; CHECK-NEXT:     p2: %k
+; CHECK-NEXT:     Arrays {
+; CHECK-NEXT:         double MemRef_A[*][8] // Element size 8
+; CHECK-NEXT:     }
+; CHECK-NEXT:     Arrays (Bounds as pw_affs) {
+; CHECK-NEXT:         double MemRef_A[*][ { [] -> [(8)] } ] // Element size 8
+; CHECK-NEXT:     }
+; CHECK-NEXT:     Alias Groups (0):
+; CHECK-NEXT:         n/a
+; CHECK-NEXT:     Statements {
+; CHECK-NEXT:       Stmt_parallel_for
+; CHECK-NEXT:             Domain :=
+; CHECK-NEXT:                 [n, m, k] -> { Stmt_parallel_for[i0] : i0 >= 0 and i0 <= n; Stmt_parallel_for[0] : n <= -1 };
+; CHECK-NEXT:             Schedule :=
+; CHECK-NEXT:                 [n, m, k] -> { Stmt_parallel_for[i0] -> [i0, 0, 0] : i0 <= n; Stmt_parallel_for[0] -> [0, 0, 0] : n <= -1 };
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [MAPPED]
+; CHECK-NEXT:                 [n, m, k] -> { Stmt_parallel_for[i0] -> MemRef_A[k] };
+; CHECK-NEXT:       Stmt_body
+; CHECK-NEXT:             Domain :=
+; CHECK-NEXT:                 [n, m, k] -> { Stmt_body[i0, i1] : i0 >= 0 and i0 <= -1 + n and i1 >= 0 and i1 <= -1 + m };
+; CHECK-NEXT:             Schedule :=
+; CHECK-NEXT:                 [n, m, k] -> { Stmt_body[i0, i1] -> [i0, 1, i1] };
+; CHECK-NEXT:             ReadAccess := [Reduction Type: NONE] [MAPPED]
+; CHECK-NEXT:                 [n, m, k] -> { Stmt_body[i0, i1] -> MemRef_A[i0] };
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [MAPPED]
+; CHECK-NEXT:                 [n, m, k] -> { Stmt_body[i0, i1] -> MemRef_A[i0] };
+; CHECK-NEXT:       Stmt_parallel_inc
+; CHECK-NEXT:             Domain :=
+; CHECK-NEXT:                 [n, m, k] -> { Stmt_parallel_inc[i0] : i0 >= 0 and i0 <= -1 + n };
+; CHECK-NEXT:             Schedule :=
+; CHECK-NEXT:                 [n, m, k] -> { Stmt_parallel_inc[i0] -> [i0, 2, 0] };
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [MAPPED]
+; CHECK-NEXT:                 [n, m, k] -> { Stmt_parallel_inc[i0] -> MemRef_A[k] };
+; CHECK-NEXT:     }
+; CHECK-NEXT: Printing analysis 'Polly - Create polyhedral description of Scops' for region: 'entry => <Function Return>' in function 'func':
+; CHECK-NEXT: Invalid Scop!

test/ScopInfo/delicm_base.ll

+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+;
+;    void func(int n, double A[static const restrict n], int m) {
+;      for (int j = 0; j < n; j += 1) /* parallel loop */
+;        for (int i = 0; i < m; i += 1) /* reduction loop */
+;          A[j] += 4.2;
+;    }
+;
+
+; Nested reduction standard case
+; Before DeLICM/LICM-Pre
+; Possible difficulties:
+; - No changes, code not to be modified
+
+define void @func(i32 %n, double* noalias nonnull %A, i32 %m) {
+entry:
+  br label %parallel.for
+
+parallel.for:
+  %j = phi i32 [0, %entry], [%j.inc, %parallel.inc]
+  %j.cmp = icmp slt i32 %j, %n
+  br i1 %j.cmp, label %reduction.for, label %return
+
+reduction.for:
+  %i = phi i32 [0, %parallel.for], [%i.inc, %reduction.inc]
+  %i.cmp = icmp slt i32 %i, %m
+  br i1 %i.cmp, label %body, label %parallel.inc
+
+body:
+  %arrayidx = getelementptr inbounds double, double* %A, i32 %j
+  %ld = load double, double* %arrayidx
+  %add = fadd double %ld, 4.2
+  store double %add, double* %arrayidx
+  br label %reduction.inc
+
+reduction.inc:
+  %i.inc = add nuw nsw i32 %i, 1
+  br label %reduction.for
+
+parallel.inc:
+  %j.inc = add nuw nsw i32 %j, 1
+  br label %parallel.for
+
+return:
+  ret void
+}
+
+
+; CHECK: Printing analysis 'Polly - Create polyhedral description of Scops' for region: 'reduction.for => parallel.inc' in function 'func':
+; CHECK-NEXT: Invalid Scop!
+; CHECK-NEXT: Printing analysis 'Polly - Create polyhedral description of Scops' for region: 'parallel.for => return' in function 'func':
+; CHECK-NEXT:     Function: func
+; CHECK-NEXT:     Region: %parallel.for---%return
+; CHECK-NEXT:     Max Loop Depth:  2
+; CHECK-NEXT:     Invariant Accesses: {
+; CHECK-NEXT:     }
+; CHECK-NEXT:     Context:
+; CHECK-NEXT:     [n, m] -> {  : n >= -2147483648 and n <= 2147483647 and m >= -2147483648 and m <= 2147483647 }
+; CHECK-NEXT:     Assumed Context:
+; CHECK-NEXT:     [n, m] -> {  :  }
+; CHECK-NEXT:     Boundary Context:
+; CHECK-NEXT:     [n, m] -> {  :  }
+; CHECK-NEXT:     p0: %n
+; CHECK-NEXT:     p1: %m
+; CHECK-NEXT:     Arrays {
+; CHECK-NEXT:         double MemRef_A[*][8] // Element size 8
+; CHECK-NEXT:     }
+; CHECK-NEXT:     Arrays (Bounds as pw_affs) {
+; CHECK-NEXT:         double MemRef_A[*][ { [] -> [(8)] } ] // Element size 8
+; CHECK-NEXT:     }
+; CHECK-NEXT:     Alias Groups (0):
+; CHECK-NEXT:         n/a
+; CHECK-NEXT:     Statements {
+; CHECK-NEXT:       Stmt_body
+; CHECK-NEXT:             Domain :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_body[i0, i1] : i0 >= 0 and i0 <= -1 + n and i1 >= 0 and i1 <= -1 + m };
+; CHECK-NEXT:             Schedule :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_body[i0, i1] -> [i0, i1] };
+; CHECK-NEXT:             ReadAccess := [Reduction Type: NONE] [MAPPED]
+; CHECK-NEXT:                 [n, m] -> { Stmt_body[i0, i1] -> MemRef_A[i0] };
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [MAPPED]
+; CHECK-NEXT:                 [n, m] -> { Stmt_body[i0, i1] -> MemRef_A[i0] };
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [MAPPED]
+; CHECK-NEXT:                 [n, m] -> { Stmt_body[i0, i1] -> MemRef_A[i0] };
+; CHECK-NEXT:     }
+; CHECK-NEXT: Printing analysis 'Polly - Create polyhedral description of Scops' for region: 'entry => <Function Return>' in function 'func':
+; CHECK-NEXT: Invalid Scop!