polly/test/ScopInfo/NonAffine/non_affine_loop_used_later.ll

   1 ; RUN: opt %loadPolly -polly-allow-nonaffine -polly-allow-nonaffine-branches -polly-allow-nonaffine-loops                                                                        -polly-print-scops -disable-output < %s | FileCheck %s
   2 ; RUN: opt %loadPolly -polly-allow-nonaffine -polly-allow-nonaffine-branches -polly-allow-nonaffine-loops -polly-unprofitable-scalar-accs=true -polly-process-unprofitable=false -polly-print-scops -disable-output < %s | FileCheck %s --check-prefix=PROFIT
   3 ;
   4 ; Verify that we over approximate the read acces of A[j] in the last statement as j is
   5 ; computed in a non-affine loop we do not model.
   6 ;
   7 ; CHECK:      Function: f
   8 ; CHECK-NEXT: Region: %bb2---%bb24
   9 ; CHECK-NEXT: Max Loop Depth:  1
  10 ; CHECK-NEXT: Invariant Accesses: {
  11 ; CHECK-NEXT: }
  12 ; CHECK-NEXT: Context:
  13 ; CHECK-NEXT: [N] -> {  : -2147483648 <= N <= 2147483647 }
  14 ; CHECK-NEXT: Assumed Context:
  15 ; CHECK-NEXT: [N] -> {  :  }
  16 ; CHECK-NEXT: Invalid Context:
  17 ; CHECK-NEXT: [N] -> {  : false }
  18 ; CHECK:      p0: %N
  19 ; CHECK-NEXT: Arrays {
  20 ; CHECK-NEXT:     i32 MemRef_j_0__phi; // Element size 4
  21 ; CHECK-NEXT:     i32 MemRef_j_0; // Element size 4
  22 ; CHECK-NEXT:     i32 MemRef_A[*]; // Element size 4
  23 ; CHECK-NEXT:     i32 MemRef_j_2__phi; // Element size 4
  24 ; CHECK-NEXT:     i32 MemRef_j_2; // Element size 4
  25 ; CHECK-NEXT: }
  26 ; CHECK-NEXT: Arrays (Bounds as pw_affs) {
  27 ; CHECK-NEXT:     i32 MemRef_j_0__phi; // Element size 4
  28 ; CHECK-NEXT:     i32 MemRef_j_0; // Element size 4
  29 ; CHECK-NEXT:     i32 MemRef_A[*]; // Element size 4
  30 ; CHECK-NEXT:     i32 MemRef_j_2__phi; // Element size 4
  31 ; CHECK-NEXT:     i32 MemRef_j_2; // Element size 4
  32 ; CHECK-NEXT: }
  33 ; CHECK-NEXT: Alias Groups (0):
  34 ; CHECK-NEXT:     n/a
  35 ; CHECK-NEXT: Statements {
  36 ; CHECK-NEXT:     Stmt_bb2
  37 ; CHECK-NEXT:         Domain :=
  38 ; CHECK-NEXT:             [N] -> { Stmt_bb2[i0] : 0 <= i0 <= N; Stmt_bb2[0] : N < 0 };
  39 ; CHECK-NEXT:         Schedule :=
  40 ; CHECK-NEXT:             [N] -> { Stmt_bb2[i0] -> [i0, 0] : i0 <= N; Stmt_bb2[0] -> [0, 0] : N < 0 };
  41 ; CHECK-NEXT:         ReadAccess :=    [Reduction Type: NONE] [Scalar: 1]
  42 ; CHECK-NEXT:             [N] -> { Stmt_bb2[i0] -> MemRef_j_0__phi[] };
  43 ; CHECK-NEXT:         MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 1]
  44 ; CHECK-NEXT:             [N] -> { Stmt_bb2[i0] -> MemRef_j_0[] };
  45 ; CHECK-NEXT:     Stmt_bb4__TO__bb18
  46 ; CHECK-NEXT:         Domain :=
  47 ; CHECK-NEXT:             [N] -> { Stmt_bb4__TO__bb18[i0] : 0 <= i0 < N };
  48 ; CHECK-NEXT:         Schedule :=
  49 ; CHECK-NEXT:             [N] -> { Stmt_bb4__TO__bb18[i0] -> [i0, 1] };
  50 ; CHECK-NEXT:         ReadAccess :=    [Reduction Type: NONE] [Scalar: 0]
  51 ; CHECK-NEXT:             [N] -> { Stmt_bb4__TO__bb18[i0] -> MemRef_A[i0] };
  52 ; CHECK-NEXT:         ReadAccess :=    [Reduction Type: NONE] [Scalar: 0]
  53 ; CHECK-NEXT:             [N] -> { Stmt_bb4__TO__bb18[i0] -> MemRef_A[i0] };
  54 ; CHECK-NEXT:         MayWriteAccess :=    [Reduction Type: NONE] [Scalar: 0]
  55 ; CHECK-NEXT:             [N] -> { Stmt_bb4__TO__bb18[i0] -> MemRef_A[i0] };
  56 ; CHECK-NEXT:         MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 1]
  57 ; CHECK-NEXT:             [N] -> { Stmt_bb4__TO__bb18[i0] -> MemRef_j_2__phi[] };
  58 ; CHECK-NEXT:         ReadAccess :=    [Reduction Type: NONE] [Scalar: 1]
  59 ; CHECK-NEXT:             [N] -> { Stmt_bb4__TO__bb18[i0] -> MemRef_j_0[] };
  60 ; CHECK-NEXT:     Stmt_bb18
  61 ; CHECK-NEXT:         Domain :=
  62 ; CHECK-NEXT:             [N] -> { Stmt_bb18[i0] : 0 <= i0 < N };
  63 ; CHECK-NEXT:         Schedule :=
  64 ; CHECK-NEXT:             [N] -> { Stmt_bb18[i0] -> [i0, 2] };
  65 ; CHECK-NEXT:         MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 1]
  66 ; CHECK-NEXT:             [N] -> { Stmt_bb18[i0] -> MemRef_j_2[] };
  67 ; CHECK-NEXT:         ReadAccess :=    [Reduction Type: NONE] [Scalar: 1]
  68 ; CHECK-NEXT:             [N] -> { Stmt_bb18[i0] -> MemRef_j_2__phi[] };
  69 ; CHECK-NEXT:         ReadAccess :=    [Reduction Type: NONE] [Scalar: 0]
  70 ; CHECK-NEXT:             [N] -> { Stmt_bb18[i0] -> MemRef_A[o0] };
  71 ; CHECK-NEXT:         MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 0]
  72 ; CHECK-NEXT:             [N] -> { Stmt_bb18[i0] -> MemRef_A[i0] };
  73 ; CHECK-NEXT:     Stmt_bb23
  74 ; CHECK-NEXT:         Domain :=
  75 ; CHECK-NEXT:             [N] -> { Stmt_bb23[i0] : 0 <= i0 < N };
  76 ; CHECK-NEXT:         Schedule :=
  77 ; CHECK-NEXT:             [N] -> { Stmt_bb23[i0] -> [i0, 3] };
  78 ; CHECK-NEXT:         ReadAccess :=    [Reduction Type: NONE] [Scalar: 1]
  79 ; CHECK-NEXT:             [N] -> { Stmt_bb23[i0] -> MemRef_j_2[] };
  80 ; CHECK-NEXT:         MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 1]
  81 ; CHECK-NEXT:             [N] -> { Stmt_bb23[i0] -> MemRef_j_0__phi[] };
  82 ; CHECK-NEXT: }
  83 ;
  84 ; Due to the scalar accesses we are not able to distribute the outer loop, thus we do not consider the region profitable.
  85 ;
  86 ; PROFIT-NOT: Statements
  87 ;
  88 ;    void f(int *A, int N, int M) {
  89 ;      int i = 0, j = 0;
  90 ;      for (i = 0; i < N; i++) {
  91 ;        if (A[i])
  92 ;          for (j = 0; j < M; j++)
  93 ;            A[i]++;
  94 ;        A[i] = A[j];
  95 ;      }
  96 ;    }
  97 ;
  98 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
  99
 100 define void @f(ptr %A, i32 %N, i32 %M) {
 101 bb:
 102   %tmp = icmp sgt i32 %M, 0
 103   %smax = select i1 %tmp, i32 %M, i32 0
 104   %tmp1 = sext i32 %N to i64
 105   br label %bb2
 106
 107 bb2:                                              ; preds = %bb23, %bb
 108   %indvars.iv = phi i64 [ %indvars.iv.next, %bb23 ], [ 0, %bb ]
 109   %j.0 = phi i32 [ 0, %bb ], [ %j.2, %bb23 ]
 110   %tmp3 = icmp slt i64 %indvars.iv, %tmp1
 111   br i1 %tmp3, label %bb4, label %bb24
 112
 113 bb4:                                              ; preds = %bb2
 114   %tmp5 = getelementptr inbounds i32, ptr %A, i64 %indvars.iv
 115   %tmp6 = load i32, ptr %tmp5, align 4
 116   %tmp7 = icmp eq i32 %tmp6, 0
 117   br i1 %tmp7, label %bb18, label %bb8
 118
 119 bb8:                                              ; preds = %bb4
 120   br label %bb9
 121
 122 bb9:                                              ; preds = %bb15, %bb8
 123   %j.1 = phi i32 [ 0, %bb8 ], [ %tmp16, %bb15 ]
 124   %tmp10 = icmp slt i32 %j.1, %M
 125   br i1 %tmp10, label %bb11, label %bb17
 126
 127 bb11:                                             ; preds = %bb9
 128   %tmp12 = getelementptr inbounds i32, ptr %A, i64 %indvars.iv
 129   %tmp13 = load i32, ptr %tmp12, align 4
 130   %tmp14 = add nsw i32 %tmp13, 1
 131   store i32 %tmp14, ptr %tmp12, align 4
 132   br label %bb15
 133
 134 bb15:                                             ; preds = %bb11
 135   %tmp16 = add nuw nsw i32 %j.1, 1
 136   br label %bb9
 137
 138 bb17:                                             ; preds = %bb9
 139   br label %bb18
 140
 141 bb18:                                             ; preds = %bb4, %bb17
 142   %j.2 = phi i32 [ %smax, %bb17 ], [ %j.0, %bb4 ]
 143   %tmp19 = sext i32 %j.2 to i64
 144   %tmp20 = getelementptr inbounds i32, ptr %A, i64 %tmp19
 145   %tmp21 = load i32, ptr %tmp20, align 4
 146   %tmp22 = getelementptr inbounds i32, ptr %A, i64 %indvars.iv
 147   store i32 %tmp21, ptr %tmp22, align 4
 148   br label %bb23
 149
 150 bb23:                                             ; preds = %bb18
 151   %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
 152   br label %bb2
 153
 154 bb24:                                             ; preds = %bb2
 155   ret void
 156 }