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

   1 ; RUN: opt %loadPolly -basic-aa -polly-allow-nonaffine-branches -polly-allow-nonaffine-loops=false                       -polly-print-scops -disable-output < %s | FileCheck %s --check-prefix=INNERMOST
   2 ; RUN: opt %loadPolly -basic-aa -polly-allow-nonaffine-branches -polly-allow-nonaffine-loops=true                        -polly-print-scops -disable-output < %s | FileCheck %s --check-prefix=INNERMOST
   3 ; RUN: opt %loadPolly -basic-aa -polly-allow-nonaffine-branches -polly-allow-nonaffine-loops=true -polly-allow-nonaffine -polly-print-scops -disable-output < %s | FileCheck %s --check-prefix=ALL
   4 ;
   5 ; Here we have a non-affine loop (in the context of the loop nest)
   6 ; and also a non-affine access (A[k]). While we can always model the
   7 ; innermost loop as a SCoP of depth 1, we can overapproximate the
   8 ; innermost loop in the whole loop nest and model A[k] as a non-affine
   9 ; access.
  10 ;
  11 ; INNERMOST:      Function: f
  12 ; INNERMOST-NEXT: Region: %bb15---%bb13
  13 ; INNERMOST-NEXT: Max Loop Depth:  1
  14 ; INNERMOST-NEXT: Invariant Accesses: {
  15 ; INNERMOST-NEXT: }
  16 ; INNERMOST-NEXT: Context:
  17 ; INNERMOST-NEXT: [p_0, p_1, p_2] -> {  : 0 <= p_0 <= 1048576 and 0 <= p_1 <= 1024 and 0 <= p_2 <= 1024 }
  18 ; INNERMOST-NEXT: Assumed Context:
  19 ; INNERMOST-NEXT: [p_0, p_1, p_2] -> {  :  }
  20 ; INNERMOST-NEXT: Invalid Context:
  21 ; INNERMOST-NEXT: [p_0, p_1, p_2] -> {  : false }
  22 ; INNERMOST:      p0: {0,+,{0,+,1}<nuw><nsw><%bb11>}<nuw><nsw><%bb13>
  23 ; INNERMOST-NEXT: p1: {0,+,1}<nuw><nsw><%bb11>
  24 ; INNERMOST-NEXT: p2: {0,+,1}<nuw><nsw><%bb13>
  25 ; INNERMOST-NEXT: Arrays {
  26 ; INNERMOST-NEXT:     i32 MemRef_A[*]; // Element size 4
  27 ; INNERMOST-NEXT:     i64 MemRef_indvars_iv_next6; // Element size 8
  28 ; INNERMOST-NEXT:     i32 MemRef_indvars_iv_next4; // Element size 4
  29 ; INNERMOST-NEXT: }
  30 ; INNERMOST-NEXT: Arrays (Bounds as pw_affs) {
  31 ; INNERMOST-NEXT:     i32 MemRef_A[*]; // Element size 4
  32 ; INNERMOST-NEXT:     i64 MemRef_indvars_iv_next6; // Element size 8
  33 ; INNERMOST-NEXT:     i32 MemRef_indvars_iv_next4; // Element size 4
  34 ; INNERMOST-NEXT: }
  35 ; INNERMOST-NEXT: Alias Groups (0):
  36 ; INNERMOST-NEXT:     n/a
  37 ; INNERMOST-NEXT: Statements {
  38 ; INNERMOST-NEXT:     Stmt_bb16
  39 ; INNERMOST-NEXT:         Domain :=
  40 ; INNERMOST-NEXT:             [p_0, p_1, p_2] -> { Stmt_bb16[i0] : 0 <= i0 < p_0 };
  41 ; INNERMOST-NEXT:         Schedule :=
  42 ; INNERMOST-NEXT:             [p_0, p_1, p_2] -> { Stmt_bb16[i0] -> [0, i0] };
  43 ; INNERMOST-NEXT:         ReadAccess :=    [Reduction Type: NONE] [Scalar: 0]
  44 ; INNERMOST-NEXT:             [p_0, p_1, p_2] -> { Stmt_bb16[i0] -> MemRef_A[p_1] };
  45 ; INNERMOST-NEXT:         ReadAccess :=    [Reduction Type: NONE] [Scalar: 0]
  46 ; INNERMOST-NEXT:             [p_0, p_1, p_2] -> { Stmt_bb16[i0] -> MemRef_A[p_2] };
  47 ; INNERMOST-NEXT:         ReadAccess :=    [Reduction Type: +] [Scalar: 0]
  48 ; INNERMOST-NEXT:             [p_0, p_1, p_2] -> { Stmt_bb16[i0] -> MemRef_A[i0] };
  49 ; INNERMOST-NEXT:         MustWriteAccess :=    [Reduction Type: +] [Scalar: 0]
  50 ; INNERMOST-NEXT:             [p_0, p_1, p_2] -> { Stmt_bb16[i0] -> MemRef_A[i0] };
  51 ; INNERMOST-NEXT:     Stmt_bb26
  52 ; INNERMOST-NEXT:         Domain :=
  53 ; INNERMOST-NEXT:             [p_0, p_1, p_2] -> { Stmt_bb26[] };
  54 ; INNERMOST-NEXT:         Schedule :=
  55 ; INNERMOST-NEXT:             [p_0, p_1, p_2] -> { Stmt_bb26[] -> [1, 0] };
  56 ; INNERMOST-NEXT:         MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 1]
  57 ; INNERMOST-NEXT:             [p_0, p_1, p_2] -> { Stmt_bb26[] -> MemRef_indvars_iv_next6[] };
  58 ; INNERMOST-NEXT:         MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 1]
  59 ; INNERMOST-NEXT:             [p_0, p_1, p_2] -> { Stmt_bb26[] -> MemRef_indvars_iv_next4[] };
  60 ; INNERMOST-NEXT: }
  61
  62 ; ALL:      Function: f
  63 ; ALL-NEXT: Region: %bb11---%bb29
  64 ; ALL-NEXT: Max Loop Depth:  2
  65 ; ALL-NEXT: Invariant Accesses: {
  66 ; ALL-NEXT: }
  67 ; ALL-NEXT: Context:
  68 ; ALL-NEXT: {  :  }
  69 ; ALL-NEXT: Assumed Context:
  70 ; ALL-NEXT: {  :  }
  71 ; ALL-NEXT: Invalid Context:
  72 ; ALL-NEXT: {  : false }
  73 ; ALL:      Arrays {
  74 ; ALL-NEXT:     i32 MemRef_A[*]; // Element size 4
  75 ; ALL-NEXT: }
  76 ; ALL-NEXT: Arrays (Bounds as pw_affs) {
  77 ; ALL-NEXT:     i32 MemRef_A[*]; // Element size 4
  78 ; ALL-NEXT: }
  79 ; ALL-NEXT: Alias Groups (0):
  80 ; ALL-NEXT:     n/a
  81 ; ALL-NEXT: Statements {
  82 ; ALL-NEXT:     Stmt_bb15__TO__bb25
  83 ; ALL-NEXT:         Domain :=
  84 ; ALL-NEXT:             { Stmt_bb15__TO__bb25[i0, i1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 };
  85 ; ALL-NEXT:         Schedule :=
  86 ; ALL-NEXT:             { Stmt_bb15__TO__bb25[i0, i1] -> [i0, i1] };
  87 ; ALL-NEXT:         ReadAccess :=    [Reduction Type: NONE] [Scalar: 0]
  88 ; ALL-NEXT:             { Stmt_bb15__TO__bb25[i0, i1] -> MemRef_A[i0] };
  89 ; ALL-NEXT:         ReadAccess :=    [Reduction Type: NONE] [Scalar: 0]
  90 ; ALL-NEXT:             { Stmt_bb15__TO__bb25[i0, i1] -> MemRef_A[i1] };
  91 ; ALL-NEXT:         ReadAccess :=    [Reduction Type: NONE] [Scalar: 0]
  92 ; ALL-NEXT:             { Stmt_bb15__TO__bb25[i0, i1] -> MemRef_A[o0] : 0 <= o0 <= 1048576 };
  93 ; ALL-NEXT:         MayWriteAccess :=    [Reduction Type: NONE] [Scalar: 0]
  94 ; ALL-NEXT:             { Stmt_bb15__TO__bb25[i0, i1] -> MemRef_A[o0] : 0 <= o0 <= 1048576 };
  95 ; ALL-NEXT: }
  96 ;
  97 ;    void f(int *A) {
  98 ;      for (int i = 0; i < 1024; i++)
  99 ;        for (int j = 0; j < 1024; j++)
 100 ;          for (int k = 0; k < i * j; k++)
 101 ;            A[k] += A[i] + A[j];
 102 ;    }
 103 ;
 104 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 105
 106 define void @f(ptr %A) {
 107 bb:
 108   br label %bb11
 109
 110 bb11:                                             ; preds = %bb28, %bb
 111   %indvars.iv8 = phi i64 [ %indvars.iv.next9, %bb28 ], [ 0, %bb ]
 112   %indvars.iv1 = phi i32 [ %indvars.iv.next2, %bb28 ], [ 0, %bb ]
 113   %exitcond10 = icmp ne i64 %indvars.iv8, 1024
 114   br i1 %exitcond10, label %bb12, label %bb29
 115
 116 bb12:                                             ; preds = %bb11
 117   br label %bb13
 118
 119 bb13:                                             ; preds = %bb26, %bb12
 120   %indvars.iv5 = phi i64 [ %indvars.iv.next6, %bb26 ], [ 0, %bb12 ]
 121   %indvars.iv3 = phi i32 [ %indvars.iv.next4, %bb26 ], [ 0, %bb12 ]
 122   %exitcond7 = icmp ne i64 %indvars.iv5, 1024
 123   br i1 %exitcond7, label %bb14, label %bb27
 124
 125 bb14:                                             ; preds = %bb13
 126   br label %bb15
 127
 128 bb15:                                             ; preds = %bb24, %bb14
 129   %indvars.iv = phi i64 [ %indvars.iv.next, %bb24 ], [ 0, %bb14 ]
 130   %lftr.wideiv = trunc i64 %indvars.iv to i32
 131   %exitcond = icmp ne i32 %lftr.wideiv, %indvars.iv3
 132   br i1 %exitcond, label %bb16, label %bb25
 133
 134 bb16:                                             ; preds = %bb15
 135   %tmp = getelementptr inbounds i32, ptr %A, i64 %indvars.iv8
 136   %tmp17 = load i32, ptr %tmp, align 4
 137   %tmp18 = getelementptr inbounds i32, ptr %A, i64 %indvars.iv5
 138   %tmp19 = load i32, ptr %tmp18, align 4
 139   %tmp20 = add nsw i32 %tmp17, %tmp19
 140   %tmp21 = getelementptr inbounds i32, ptr %A, i64 %indvars.iv
 141   %tmp22 = load i32, ptr %tmp21, align 4
 142   %tmp23 = add nsw i32 %tmp22, %tmp20
 143   store i32 %tmp23, ptr %tmp21, align 4
 144   br label %bb24
 145
 146 bb24:                                             ; preds = %bb16
 147   %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
 148   br label %bb15
 149
 150 bb25:                                             ; preds = %bb15
 151   br label %bb26
 152
 153 bb26:                                             ; preds = %bb25
 154   %indvars.iv.next6 = add nuw nsw i64 %indvars.iv5, 1
 155   %indvars.iv.next4 = add nuw nsw i32 %indvars.iv3, %indvars.iv1
 156   br label %bb13
 157
 158 bb27:                                             ; preds = %bb13
 159   br label %bb28
 160
 161 bb28:                                             ; preds = %bb27
 162   %indvars.iv.next9 = add nuw nsw i64 %indvars.iv8, 1
 163   %indvars.iv.next2 = add nuw nsw i32 %indvars.iv1, 1
 164   br label %bb11
 165
 166 bb29:                                             ; preds = %bb11
 167   ret void
 168 }