test/ScopInfo/many-scalar-dependences.ll

   1 ; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
   2 ;
   3 ;    void f(float a[100][100]) {
   4 ;      float x;
   5 ;
   6 ;      for (int i = 0; i < 100; i++) {
   7 ;        for (int j = 0; j < 100; j++) {
   8 ;          for (int k = 0; k < 100; k++) {
   9 ;            if (k == 0)
  10 ;              x = 42;
  11 ;            a[i][j] += x;
  12 ;            x++;
  13 ;          }
  14 ;        }
  15 ;      }
  16 ;    }
  17
  18 ; The scop we generate for this kernel has a very large number of statements
  19 ; and scalar data-dependences due to x being passed along as SSA value or PHI
  20 ; node.
  21
  22 ; CHECK:      Statements {
  23 ; CHECK-NEXT:     Stmt_bb5
  24 ; CHECK-NEXT:         Domain :=
  25 ; CHECK-NEXT:             { Stmt_bb5[i0] : 0 <= i0 <= 100 };
  26 ; CHECK-NEXT:         Schedule :=
  27 ; CHECK-NEXT:             { Stmt_bb5[i0] -> [i0, 0, 0, 0, 0, 0] };
  28 ; CHECK-NEXT:         ReadAccess :=    [Reduction Type: NONE] [Scalar: 1]
  29 ; CHECK-NEXT:             { Stmt_bb5[i0] -> MemRef_x_0__phi[] };
  30 ; CHECK-NEXT:         MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 1]
  31 ; CHECK-NEXT:             { Stmt_bb5[i0] -> MemRef_x_0[] };
  32 ; CHECK-NEXT:     Stmt_bb6
  33 ; CHECK-NEXT:         Domain :=
  34 ; CHECK-NEXT:             { Stmt_bb6[i0] : 0 <= i0 <= 99 };
  35 ; CHECK-NEXT:         Schedule :=
  36 ; CHECK-NEXT:             { Stmt_bb6[i0] -> [i0, 1, 0, 0, 0, 0] };
  37 ; CHECK-NEXT:         ReadAccess :=    [Reduction Type: NONE] [Scalar: 1]
  38 ; CHECK-NEXT:             { Stmt_bb6[i0] -> MemRef_x_0[] };
  39 ; CHECK-NEXT:         MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 1]
  40 ; CHECK-NEXT:             { Stmt_bb6[i0] -> MemRef_x_1__phi[] };
  41 ; CHECK-NEXT:     Stmt_bb7
  42 ; CHECK-NEXT:         Domain :=
  43 ; CHECK-NEXT:             { Stmt_bb7[i0, i1] : 0 <= i0 <= 99 and 0 <= i1 <= 100 };
  44 ; CHECK-NEXT:         Schedule :=
  45 ; CHECK-NEXT:             { Stmt_bb7[i0, i1] -> [i0, 2, i1, 0, 0, 0] };
  46 ; CHECK-NEXT:         ReadAccess :=    [Reduction Type: NONE] [Scalar: 1]
  47 ; CHECK-NEXT:             { Stmt_bb7[i0, i1] -> MemRef_x_1__phi[] };
  48 ; CHECK-NEXT:         MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 1]
  49 ; CHECK-NEXT:             { Stmt_bb7[i0, i1] -> MemRef_x_1[] };
  50 ; CHECK-NEXT:         MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 1]
  51 ; CHECK-NEXT:             { Stmt_bb7[i0, i1] -> MemRef_x_1_lcssa__phi[] };
  52 ; CHECK-NEXT:     Stmt_bb8
  53 ; CHECK-NEXT:         Domain :=
  54 ; CHECK-NEXT:             { Stmt_bb8[i0, i1] : 0 <= i0 <= 99 and 0 <= i1 <= 99 };
  55 ; CHECK-NEXT:         Schedule :=
  56 ; CHECK-NEXT:             { Stmt_bb8[i0, i1] -> [i0, 2, i1, 1, 0, 0] };
  57 ; CHECK-NEXT:         ReadAccess :=    [Reduction Type: NONE] [Scalar: 1]
  58 ; CHECK-NEXT:             { Stmt_bb8[i0, i1] -> MemRef_x_1[] };
  59 ; CHECK-NEXT:         MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 1]
  60 ; CHECK-NEXT:             { Stmt_bb8[i0, i1] -> MemRef_x_2__phi[] };
  61 ; CHECK-NEXT:     Stmt_bb9
  62 ; CHECK-NEXT:         Domain :=
  63 ; CHECK-NEXT:             { Stmt_bb9[i0, i1, i2] : 0 <= i0 <= 99 and 0 <= i1 <= 99 and 0 <= i2 <= 100 };
  64 ; CHECK-NEXT:         Schedule :=
  65 ; CHECK-NEXT:             { Stmt_bb9[i0, i1, i2] -> [i0, 2, i1, 2, i2, 0] };
  66 ; CHECK-NEXT:         ReadAccess :=    [Reduction Type: NONE] [Scalar: 1]
  67 ; CHECK-NEXT:             { Stmt_bb9[i0, i1, i2] -> MemRef_x_2__phi[] };
  68 ; CHECK-NEXT:         MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 1]
  69 ; CHECK-NEXT:             { Stmt_bb9[i0, i1, i2] -> MemRef_x_2[] };
  70 ; CHECK-NEXT:         MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 1]
  71 ; CHECK-NEXT:             { Stmt_bb9[i0, i1, i2] -> MemRef_x_2_lcssa__phi[] };
  72 ; CHECK-NEXT:     Stmt_bb10
  73 ; CHECK-NEXT:         Domain :=
  74 ; CHECK-NEXT:             { Stmt_bb10[i0, i1, i2] : 0 <= i0 <= 99 and 0 <= i1 <= 99 and 0 <= i2 <= 99 };
  75 ; CHECK-NEXT:         Schedule :=
  76 ; CHECK-NEXT:             { Stmt_bb10[i0, i1, i2] -> [i0, 2, i1, 2, i2, 1] };
  77 ; CHECK-NEXT:         ReadAccess :=    [Reduction Type: NONE] [Scalar: 1]
  78 ; CHECK-NEXT:             { Stmt_bb10[i0, i1, i2] -> MemRef_x_2[] };
  79 ; CHECK-NEXT:         MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 1]
  80 ; CHECK-NEXT:             { Stmt_bb10[i0, i1, i2] -> MemRef_x_3__phi[] };
  81 ; CHECK-NEXT:     Stmt_bb11
  82 ; CHECK-NEXT:         Domain :=
  83 ; CHECK-NEXT:             { Stmt_bb11[i0, i1, 0] : 0 <= i0 <= 99 and 0 <= i1 <= 99 };
  84 ; CHECK-NEXT:         Schedule :=
  85 ; CHECK-NEXT:             { Stmt_bb11[i0, i1, i2] -> [i0, 2, i1, 2, 0, 2] };
  86 ; CHECK-NEXT:         MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 1]
  87 ; CHECK-NEXT:             { Stmt_bb11[i0, i1, i2] -> MemRef_x_3__phi[] };
  88 ; CHECK-NEXT:     Stmt_bb12
  89 ; CHECK-NEXT:         Domain :=
  90 ; CHECK-NEXT:             { Stmt_bb12[i0, i1, i2] : 0 <= i0 <= 99 and 0 <= i1 <= 99 and 0 <= i2 <= 99 };
  91 ; CHECK-NEXT:         Schedule :=
  92 ; CHECK-NEXT:             { Stmt_bb12[i0, i1, i2] -> [i0, 2, i1, 2, i2, 3] };
  93 ; CHECK-NEXT:         ReadAccess :=    [Reduction Type: NONE] [Scalar: 1]
  94 ; CHECK-NEXT:             { Stmt_bb12[i0, i1, i2] -> MemRef_x_3__phi[] };
  95 ; CHECK-NEXT:         ReadAccess :=    [Reduction Type: NONE] [Scalar: 0]
  96 ; CHECK-NEXT:             { Stmt_bb12[i0, i1, i2] -> MemRef_a[i0, i1] };
  97 ; CHECK-NEXT:         MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 0]
  98 ; CHECK-NEXT:             { Stmt_bb12[i0, i1, i2] -> MemRef_a[i0, i1] };
  99 ; CHECK-NEXT:         MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 1]
 100 ; CHECK-NEXT:             { Stmt_bb12[i0, i1, i2] -> MemRef_x_3[] };
 101 ; CHECK-NEXT:     Stmt_bb16
 102 ; CHECK-NEXT:         Domain :=
 103 ; CHECK-NEXT:             { Stmt_bb16[i0, i1, i2] : 0 <= i0 <= 99 and 0 <= i1 <= 99 and 0 <= i2 <= 99 };
 104 ; CHECK-NEXT:         Schedule :=
 105 ; CHECK-NEXT:             { Stmt_bb16[i0, i1, i2] -> [i0, 2, i1, 2, i2, 4] };
 106 ; CHECK-NEXT:         MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 1]
 107 ; CHECK-NEXT:             { Stmt_bb16[i0, i1, i2] -> MemRef_x_2__phi[] };
 108 ; CHECK-NEXT:         ReadAccess :=    [Reduction Type: NONE] [Scalar: 1]
 109 ; CHECK-NEXT:             { Stmt_bb16[i0, i1, i2] -> MemRef_x_3[] };
 110 ; CHECK-NEXT:     Stmt_bb19
 111 ; CHECK-NEXT:         Domain :=
 112 ; CHECK-NEXT:             { Stmt_bb19[i0, i1] : 0 <= i0 <= 99 and 0 <= i1 <= 99 };
 113 ; CHECK-NEXT:         Schedule :=
 114 ; CHECK-NEXT:             { Stmt_bb19[i0, i1] -> [i0, 2, i1, 3, 0, 0] };
 115 ; CHECK-NEXT:         MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 1]
 116 ; CHECK-NEXT:             { Stmt_bb19[i0, i1] -> MemRef_x_2_lcssa[] };
 117 ; CHECK-NEXT:         ReadAccess :=    [Reduction Type: NONE] [Scalar: 1]
 118 ; CHECK-NEXT:             { Stmt_bb19[i0, i1] -> MemRef_x_2_lcssa__phi[] };
 119 ; CHECK-NEXT:     Stmt_bb20
 120 ; CHECK-NEXT:         Domain :=
 121 ; CHECK-NEXT:             { Stmt_bb20[i0, i1] : 0 <= i0 <= 99 and 0 <= i1 <= 99 };
 122 ; CHECK-NEXT:         Schedule :=
 123 ; CHECK-NEXT:             { Stmt_bb20[i0, i1] -> [i0, 2, i1, 4, 0, 0] };
 124 ; CHECK-NEXT:         ReadAccess :=    [Reduction Type: NONE] [Scalar: 1]
 125 ; CHECK-NEXT:             { Stmt_bb20[i0, i1] -> MemRef_x_2_lcssa[] };
 126 ; CHECK-NEXT:         MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 1]
 127 ; CHECK-NEXT:             { Stmt_bb20[i0, i1] -> MemRef_x_1__phi[] };
 128 ; CHECK-NEXT:     Stmt_bb21
 129 ; CHECK-NEXT:         Domain :=
 130 ; CHECK-NEXT:             { Stmt_bb21[i0] : 0 <= i0 <= 99 };
 131 ; CHECK-NEXT:         Schedule :=
 132 ; CHECK-NEXT:             { Stmt_bb21[i0] -> [i0, 3, 0, 0, 0, 0] };
 133 ; CHECK-NEXT:         MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 1]
 134 ; CHECK-NEXT:             { Stmt_bb21[i0] -> MemRef_x_1_lcssa[] };
 135 ; CHECK-NEXT:         ReadAccess :=    [Reduction Type: NONE] [Scalar: 1]
 136 ; CHECK-NEXT:             { Stmt_bb21[i0] -> MemRef_x_1_lcssa__phi[] };
 137 ; CHECK-NEXT:     Stmt_bb22
 138 ; CHECK-NEXT:         Domain :=
 139 ; CHECK-NEXT:             { Stmt_bb22[i0] : 0 <= i0 <= 99 };
 140 ; CHECK-NEXT:         Schedule :=
 141 ; CHECK-NEXT:             { Stmt_bb22[i0] -> [i0, 4, 0, 0, 0, 0] };
 142 ; CHECK-NEXT:         ReadAccess :=    [Reduction Type: NONE] [Scalar: 1]
 143 ; CHECK-NEXT:             { Stmt_bb22[i0] -> MemRef_x_1_lcssa[] };
 144 ; CHECK-NEXT:         MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 1]
 145 ; CHECK-NEXT:             { Stmt_bb22[i0] -> MemRef_x_0__phi[] };
 146 ; CHECK-NEXT: }
 147
 148 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 149
 150 define void @f([100 x float]* %a) {
 151 bb:
 152   br label %bb5
 153
 154 bb5:                                              ; preds = %bb22, %bb
 155   %indvars.iv2 = phi i64 [ %indvars.iv.next3, %bb22 ], [ 0, %bb ]
 156   %x.0 = phi float [ undef, %bb ], [ %x.1.lcssa, %bb22 ]
 157   %exitcond4 = icmp ne i64 %indvars.iv2, 100
 158   br i1 %exitcond4, label %bb6, label %bb23
 159
 160 bb6:                                              ; preds = %bb5
 161   br label %bb7
 162
 163 bb7:                                              ; preds = %bb20, %bb6
 164   %indvars.iv = phi i64 [ %indvars.iv.next, %bb20 ], [ 0, %bb6 ]
 165   %x.1 = phi float [ %x.0, %bb6 ], [ %x.2.lcssa, %bb20 ]
 166   %exitcond1 = icmp ne i64 %indvars.iv, 100
 167   br i1 %exitcond1, label %bb8, label %bb21
 168
 169 bb8:                                              ; preds = %bb7
 170   br label %bb9
 171
 172 bb9:                                              ; preds = %bb16, %bb8
 173   %x.2 = phi float [ %x.1, %bb8 ], [ %tmp17, %bb16 ]
 174   %k.0 = phi i32 [ 0, %bb8 ], [ %tmp18, %bb16 ]
 175   %exitcond = icmp ne i32 %k.0, 100
 176   br i1 %exitcond, label %bb10, label %bb19
 177
 178 bb10:                                             ; preds = %bb9
 179   %tmp = icmp eq i32 %k.0, 0
 180   br i1 %tmp, label %bb11, label %bb12
 181
 182 bb11:                                             ; preds = %bb10
 183   br label %bb12
 184
 185 bb12:                                             ; preds = %bb11, %bb10
 186   %x.3 = phi float [ 4.200000e+01, %bb11 ], [ %x.2, %bb10 ]
 187   %tmp13 = getelementptr inbounds [100 x float], [100 x float]* %a, i64 %indvars.iv2, i64 %indvars.iv
 188   %tmp14 = load float, float* %tmp13, align 4
 189   %tmp15 = fadd float %tmp14, %x.3
 190   store float %tmp15, float* %tmp13, align 4
 191   br label %bb16
 192
 193 bb16:                                             ; preds = %bb12
 194   %tmp17 = fadd float %x.3, 1.000000e+00
 195   %tmp18 = add nuw nsw i32 %k.0, 1
 196   br label %bb9
 197
 198 bb19:                                             ; preds = %bb9
 199   %x.2.lcssa = phi float [ %x.2, %bb9 ]
 200   br label %bb20
 201
 202 bb20:                                             ; preds = %bb19
 203   %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
 204   br label %bb7
 205
 206 bb21:                                             ; preds = %bb7
 207   %x.1.lcssa = phi float [ %x.1, %bb7 ]
 208   br label %bb22
 209
 210 bb22:                                             ; preds = %bb21
 211   %indvars.iv.next3 = add nuw nsw i64 %indvars.iv2, 1
 212   br label %bb5
 213
 214 bb23:                                             ; preds = %bb5
 215   ret void
 216 }