test/DependenceInfo/sequential_loops.ll

   1 ; RUN: opt -S %loadPolly -basicaa -polly-dependences -analyze -polly-dependences-analysis-type=value-based < %s | FileCheck %s -check-prefix=VALUE
   2 ; RUN: opt -S %loadPolly -basicaa -polly-dependences -analyze -polly-dependences-analysis-type=memory-based < %s | FileCheck %s -check-prefix=MEMORY
   3 ; RUN: opt -S %loadPolly -basicaa -polly-dependences -analyze -polly-dependences-analysis-type=value-based -polly-dependences-analysis-level=access-wise < %s | FileCheck %s -check-prefix=VALUE_ACCESS
   4
   5 ; VALUE-LABEL: Printing analysis 'Polly - Calculate dependences' for region: 'S1 => exit.3' in function 'sequential_writes':
   6 ; VALUE-NEXT:      RAW dependences:
   7 ; VALUE-NEXT:          {  }
   8 ; VALUE-NEXT:      WAR dependences:
   9 ; VALUE-NEXT:          {  }
  10 ; VALUE-NEXT:      WAW dependences:
  11 ; VALUE-NEXT:          { Stmt_S1[i0] -> Stmt_S2[i0] : 0 <= i0 <= 9; Stmt_S2[i0] -> Stmt_S3[i0] : 0 <= i0 <= 9; Stmt_S1[i0] -> Stmt_S3[i0] : 10 <= i0 <= 99 }
  12 ;
  13 ;VALUE_ACCESS-LABEL: Printing analysis 'Polly - Calculate dependences' for region: 'S1 => exit.3' in function 'sequential_writes':
  14 ;VALUE_ACCESS-NEXT:        RAW dependences:
  15 ;VALUE_ACCESS-NEXT:                {  }
  16 ;VALUE_ACCESS-NEXT:        WAR dependences:
  17 ;VALUE_ACCESS-NEXT:                {  }
  18 ;VALUE_ACCESS-NEXT:        WAW dependences:
  19 ;VALUE_ACCESS-NEXT:                { Stmt_S1[i0] -> Stmt_S2[i0] : 0 <= i0 <= 9; [Stmt_S1[i0] -> Stmt_S1_Write0_MemRef_A[]] -> [Stmt_S3[i0] -> Stmt_S3_Write0_MemRef_A[]] : 10 <= i0 <= 99; Stmt_S2[i0] -> Stmt_S3[i0] : 0 <= i0 <= 9; [Stmt_S2[i0] -> Stmt_S2_Write0_MemRef_A[]] -> [Stmt_S3[i0] -> Stmt_S3_Write0_MemRef_A[]] : 0 <= i0 <= 9; [Stmt_S1[i0] -> Stmt_S1_Write0_MemRef_A[]] -> [Stmt_S2[i0] -> Stmt_S2_Write0_MemRef_A[]] : 0 <= i0 <= 9; Stmt_S1[i0] -> Stmt_S3[i0] : 10 <= i0 <= 99 }
  20 ;
  21 ; VALUE-LABEL: Printing analysis 'Polly - Calculate dependences' for region: 'S1 => exit.3' in function 'read_after_writes':
  22 ; VALUE-NEXT:      RAW dependences:
  23 ; VALUE-NEXT:          { Stmt_S2[i0] -> Stmt_S3[i0] : 0 <= i0 <= 9; Stmt_S1[i0] -> Stmt_S3[i0] : 10 <= i0 <= 99 }
  24 ; VALUE-NEXT:      WAR dependences:
  25 ; VALUE-NEXT:          {  }
  26 ; VALUE-NEXT:      WAW dependences:
  27 ; VALUE-NEXT:          { Stmt_S1[i0] -> Stmt_S2[i0] : 0 <= i0 <= 9 }
  28 ;
  29 ;VALUE_ACCESS-LABEL: Printing analysis 'Polly - Calculate dependences' for region: 'S1 => exit.3' in function 'read_after_writes':
  30 ;VALUE_ACCESS-NEXT:        RAW dependences:
  31 ;VALUE_ACCESS-NEXT:                { [Stmt_S1[i0] -> Stmt_S1_Write0_MemRef_A[]] -> [Stmt_S3[i0] -> Stmt_S3_Read0_MemRef_A[]] : 10 <= i0 <= 99; Stmt_S2[i0] -> Stmt_S3[i0] : 0 <= i0 <= 9; [Stmt_S2[i0] -> Stmt_S2_Write0_MemRef_A[]] -> [Stmt_S3[i0] -> Stmt_S3_Read0_MemRef_A[]] : 0 <= i0 <= 9; Stmt_S1[i0] -> Stmt_S3[i0] : 10 <= i0 <= 99 }
  32 ;VALUE_ACCESS-NEXT:        WAR dependences:
  33 ;VALUE_ACCESS-NEXT:                {  }
  34 ;VALUE_ACCESS-NEXT:        WAW dependences:
  35 ;VALUE_ACCESS-NEXT:                { Stmt_S1[i0] -> Stmt_S2[i0] : 0 <= i0 <= 9; [Stmt_S1[i0] -> Stmt_S1_Write0_MemRef_A[]] -> [Stmt_S2[i0] -> Stmt_S2_Write0_MemRef_A[]] : 0 <= i0 <= 9 }
  36 ;
  37 ; VALUE-LABEL: Printing analysis 'Polly - Calculate dependences' for region: 'S1 => exit.3' in function 'write_after_read':
  38 ; VALUE-NEXT:      RAW dependences:
  39 ; VALUE-NEXT:          {  }
  40 ; VALUE-NEXT:      WAR dependences:
  41 ; VALUE-NEXT:          { Stmt_S1[i0] -> Stmt_S2[i0] : 0 <= i0 <= 9; Stmt_S1[i0] -> Stmt_S3[i0] : 10 <= i0 <= 99 }
  42 ; VALUE-NEXT:      WAW dependences:
  43 ; VALUE-NEXT:          { Stmt_S2[i0] -> Stmt_S3[i0] : 0 <= i0 <= 9 }
  44 ;
  45 ;VALUE_ACCESS-LABEL: Printing analysis 'Polly - Calculate dependences' for region: 'S1 => exit.3' in function 'write_after_read':
  46 ;VALUE_ACCESS-NEXT:         RAW dependences:
  47 ;VALUE_ACCESS-NEXT:                 {  }
  48 ;VALUE_ACCESS-NEXT:         WAR dependences:
  49 ;VALUE_ACCESS-NEXT:                { Stmt_S1[i0] -> Stmt_S2[i0] : 0 <= i0 <= 9; [Stmt_S1[i0] -> Stmt_S1_Read0_MemRef_A[]] -> [Stmt_S2[i0] -> Stmt_S2_Write0_MemRef_A[]] : 0 <= i0 <= 9; [Stmt_S1[i0] -> Stmt_S1_Read0_MemRef_A[]] -> [Stmt_S3[i0] -> Stmt_S3_Write0_MemRef_A[]] : 10 <= i0 <= 99; Stmt_S1[i0] -> Stmt_S3[i0] : 10 <= i0 <= 99 }
  50 ;VALUE_ACCESS-NEXT:         WAW dependences:
  51 ;VALUE_ACCESS-NEXT:                { Stmt_S2[i0] -> Stmt_S3[i0] : 0 <= i0 <= 9; [Stmt_S2[i0] -> Stmt_S2_Write0_MemRef_A[]] -> [Stmt_S3[i0] -> Stmt_S3_Write0_MemRef_A[]] : 0 <= i0 <= 9 }
  52 ;
  53 ; VALUE-LABEL: Printing analysis 'Polly - Calculate dependences' for region: 'S1 => exit.2' in function 'parametric_offset':
  54 ; VALUE-NEXT:      RAW dependences:
  55 ; VALUE-NEXT:          [p] -> { Stmt_S1[i0] -> Stmt_S2[-p + i0] : i0 >= p and 0 <= i0 <= 99 and i0 <= 9 + p }
  56 ; VALUE-NEXT:      WAR dependences:
  57 ; VALUE-NEXT:          [p] -> {  }
  58 ; VALUE-NEXT:      WAW dependences:
  59 ; VALUE-NEXT:          [p] -> {  }
  60 ;
  61 ;VALUE_ACCESS-LABEL: Printing analysis 'Polly - Calculate dependences' for region: 'S1 => exit.2' in function 'parametric_offset':
  62 ;VALUE_ACCESS-NEXT:        RAW dependences:
  63 ;VALUE_ACCESS-NEXT:                [p] -> { [Stmt_S1[i0] -> Stmt_S1_Write0_MemRef_A[]] -> [Stmt_S2[-p + i0] -> Stmt_S2_Read0_MemRef_A[]] : i0 >= p and 0 <= i0 <= 99 and i0 <= 9 + p; Stmt_S1[i0] -> Stmt_S2[-p + i0] : i0 >= p and 0 <= i0 <= 99 and i0 <= 9 + p }
  64 ;VALUE_ACCESS-NEXT:        WAR dependences:
  65 ;VALUE_ACCESS-NEXT:                [p] -> {  }
  66 ;VALUE_ACCESS-NEXT:        WAW dependences:
  67 ;VALUE_ACCESS-NEXT:                [p] -> {  }
  68
  69 ; MEMORY-LABEL: Printing analysis 'Polly - Calculate dependences' for region: 'S1 => exit.3' in function 'sequential_writes':
  70 ; MEMORY-NEXT:      RAW dependences:
  71 ; MEMORY-NEXT:          {  }
  72 ; MEMORY-NEXT:      WAR dependences:
  73 ; MEMORY-NEXT:          {  }
  74 ; MEMORY-NEXT:      WAW dependences:
  75 ; MEMORY-NEXT:          { Stmt_S1[i0] -> Stmt_S2[i0] : 0 <= i0 <= 9; Stmt_S2[i0] -> Stmt_S3[i0] : 0 <= i0 <= 9; Stmt_S1[i0] -> Stmt_S3[i0] : 0 <= i0 <= 99 }
  76 ;
  77 ; MEMORY-LABEL: Printing analysis 'Polly - Calculate dependences' for region: 'S1 => exit.3' in function 'read_after_writes':
  78 ; MEMORY-NEXT:      RAW dependences:
  79 ; MEMORY-NEXT:          { Stmt_S2[i0] -> Stmt_S3[i0] : 0 <= i0 <= 9; Stmt_S1[i0] -> Stmt_S3[i0] : 0 <= i0 <= 99 }
  80 ; MEMORY-NEXT:      WAR dependences:
  81 ; MEMORY-NEXT:          {  }
  82 ; MEMORY-NEXT:      WAW dependences:
  83 ; MEMORY-NEXT:          { Stmt_S1[i0] -> Stmt_S2[i0] : 0 <= i0 <= 9 }
  84 ;
  85 ; MEMORY-LABEL: Printing analysis 'Polly - Calculate dependences' for region: 'S1 => exit.3' in function 'write_after_read':
  86 ; MEMORY-NEXT:      RAW dependences:
  87 ; MEMORY-NEXT:          {  }
  88 ; MEMORY-NEXT:      WAR dependences:
  89 ; MEMORY-NEXT:          { Stmt_S1[i0] -> Stmt_S2[i0] : 0 <= i0 <= 9; Stmt_S1[i0] -> Stmt_S3[i0] : 0 <= i0 <= 99 }
  90 ; MEMORY-NEXT:      WAW dependences:
  91 ; MEMORY-NEXT:          { Stmt_S2[i0] -> Stmt_S3[i0] : 0 <= i0 <= 9 }
  92 ;
  93 ; MEMORY-LABEL: Printing analysis 'Polly - Calculate dependences' for region: 'S1 => exit.2' in function 'parametric_offset':
  94 ; MEMORY-NEXT:      RAW dependences:
  95 ; MEMORY-NEXT:          [p] -> { Stmt_S1[i0] -> Stmt_S2[-p + i0] : i0 >= p and 0 <= i0 <= 99 and i0 <= 9 + p }
  96 ; MEMORY-NEXT:      WAR dependences:
  97 ; MEMORY-NEXT:          [p] -> {  }
  98 ; MEMORY-NEXT:      WAW dependences:
  99 ; MEMORY-NEXT:          [p] -> {  }
 100
 101 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64"
 102
 103 ;     for(i = 0; i < 100; i++ )
 104 ; S1:   A[i] = 2;
 105 ;
 106 ;     for (i = 0; i < 10; i++ )
 107 ; S2:   A[i]  = 5;
 108 ;
 109 ;     for (i = 0; i < 200; i++ )
 110 ; S3:   A[i] = 5;
 111
 112 define void @sequential_writes() {
 113 entry:
 114   %A = alloca [200 x i32]
 115   br label %S1
 116
 117 S1:
 118   %indvar.1 = phi i64 [ 0, %entry ], [ %indvar.next.1, %S1 ]
 119   %arrayidx.1 = getelementptr [200 x i32], [200 x i32]* %A, i64 0, i64 %indvar.1
 120   store i32 2, i32* %arrayidx.1
 121   %indvar.next.1 = add i64 %indvar.1, 1
 122   %exitcond.1 = icmp ne i64 %indvar.next.1, 100
 123   br i1 %exitcond.1, label %S1, label %exit.1
 124
 125 exit.1:
 126   br label %S2
 127
 128 S2:
 129   %indvar.2 = phi i64 [ 0, %exit.1 ], [ %indvar.next.2, %S2 ]
 130   %arrayidx.2 = getelementptr [200 x i32], [200 x i32]* %A, i64 0, i64 %indvar.2
 131   store i32 5, i32* %arrayidx.2
 132   %indvar.next.2 = add i64 %indvar.2, 1
 133   %exitcond.2 = icmp ne i64 %indvar.next.2, 10
 134   br i1 %exitcond.2, label %S2, label %exit.2
 135
 136 exit.2:
 137   br label %S3
 138
 139 S3:
 140   %indvar.3 = phi i64 [ 0, %exit.2 ], [ %indvar.next.3, %S3 ]
 141   %arrayidx.3 = getelementptr [200 x i32], [200 x i32]* %A, i64 0, i64 %indvar.3
 142   store i32 7, i32* %arrayidx.3
 143   %indvar.next.3 = add i64 %indvar.3, 1
 144   %exitcond.3 = icmp ne i64 %indvar.next.3, 200
 145   br i1 %exitcond.3, label %S3 , label %exit.3
 146
 147 exit.3:
 148   ret void
 149 }
 150
 151
 152 ;     for(i = 0; i < 100; i++ )
 153 ; S1:   A[i] = 2;
 154 ;
 155 ;     for (i = 0; i < 10; i++ )
 156 ; S2:   A[i]  = 5;
 157 ;
 158 ;     for (i = 0; i < 200; i++ )
 159 ; S3:   B[i] = A[i];
 160
 161 define void @read_after_writes() {
 162 entry:
 163   %A = alloca [200 x i32]
 164   %B = alloca [200 x i32]
 165   br label %S1
 166
 167 S1:
 168   %indvar.1 = phi i64 [ 0, %entry ], [ %indvar.next.1, %S1 ]
 169   %arrayidx.1 = getelementptr [200 x i32], [200 x i32]* %A, i64 0, i64 %indvar.1
 170   store i32 2, i32* %arrayidx.1
 171   %indvar.next.1 = add i64 %indvar.1, 1
 172   %exitcond.1 = icmp ne i64 %indvar.next.1, 100
 173   br i1 %exitcond.1, label %S1, label %exit.1
 174
 175 exit.1:
 176   br label %S2
 177
 178 S2:
 179   %indvar.2 = phi i64 [ 0, %exit.1 ], [ %indvar.next.2, %S2 ]
 180   %arrayidx.2 = getelementptr [200 x i32], [200 x i32]* %A, i64 0, i64 %indvar.2
 181   store i32 5, i32* %arrayidx.2
 182   %indvar.next.2 = add i64 %indvar.2, 1
 183   %exitcond.2 = icmp ne i64 %indvar.next.2, 10
 184   br i1 %exitcond.2, label %S2, label %exit.2
 185
 186 exit.2:
 187   br label %S3
 188
 189 S3:
 190   %indvar.3 = phi i64 [ 0, %exit.2 ], [ %indvar.next.3, %S3 ]
 191   %arrayidx.3.a = getelementptr [200 x i32], [200 x i32]* %A, i64 0, i64 %indvar.3
 192   %arrayidx.3.b = getelementptr [200 x i32], [200 x i32]* %B, i64 0, i64 %indvar.3
 193   %val = load i32, i32* %arrayidx.3.a
 194   store i32 %val, i32* %arrayidx.3.b
 195   %indvar.next.3 = add i64 %indvar.3, 1
 196   %exitcond.3 = icmp ne i64 %indvar.next.3, 200
 197   br i1 %exitcond.3, label %S3 , label %exit.3
 198
 199 exit.3:
 200   ret void
 201 }
 202
 203
 204 ;     for(i = 0; i < 100; i++ )
 205 ; S1:   B[i] = A[i];
 206 ;
 207 ;     for (i = 0; i < 10; i++ )
 208 ; S2:   A[i]  = 5;
 209 ;
 210 ;     for (i = 0; i < 200; i++ )
 211 ; S3:   A[i]  = 10;
 212
 213 define void @write_after_read() {
 214 entry:
 215   %A = alloca [200 x i32]
 216   %B = alloca [200 x i32]
 217   br label %S1
 218
 219 S1:
 220   %indvar.1 = phi i64 [ 0, %entry ], [ %indvar.next.1, %S1 ]
 221   %arrayidx.1.a = getelementptr [200 x i32], [200 x i32]* %A, i64 0, i64 %indvar.1
 222   %arrayidx.1.b = getelementptr [200 x i32], [200 x i32]* %B, i64 0, i64 %indvar.1
 223   %val = load i32, i32* %arrayidx.1.a
 224   store i32 %val, i32* %arrayidx.1.b
 225   %indvar.next.1 = add i64 %indvar.1, 1
 226   %exitcond.1 = icmp ne i64 %indvar.next.1, 100
 227   br i1 %exitcond.1, label %S1, label %exit.1
 228
 229 exit.1:
 230   br label %S2
 231
 232 S2:
 233   %indvar.2 = phi i64 [ 0, %exit.1 ], [ %indvar.next.2, %S2 ]
 234   %arrayidx.2 = getelementptr [200 x i32], [200 x i32]* %A, i64 0, i64 %indvar.2
 235   store i32 5, i32* %arrayidx.2
 236   %indvar.next.2 = add i64 %indvar.2, 1
 237   %exitcond.2 = icmp ne i64 %indvar.next.2, 10
 238   br i1 %exitcond.2, label %S2, label %exit.2
 239
 240 exit.2:
 241   br label %S3
 242
 243 S3:
 244   %indvar.3 = phi i64 [ 0, %exit.2 ], [ %indvar.next.3, %S3 ]
 245   %arrayidx.3 = getelementptr [200 x i32], [200 x i32]* %A, i64 0, i64 %indvar.3
 246   store i32 10, i32* %arrayidx.3
 247   %indvar.next.3 = add i64 %indvar.3, 1
 248   %exitcond.3 = icmp ne i64 %indvar.next.3, 200
 249   br i1 %exitcond.3, label %S3 , label %exit.3
 250
 251 exit.3:
 252   ret void
 253 }
 254
 255
 256 ;     for(i = 0; i < 100; i++ )
 257 ; S1:   A[i] = 10
 258 ;
 259 ;     for(i = 0; i < 100; i++ )
 260 ; S2:   B[i] = A[i + p];
 261
 262 define void @parametric_offset(i64 %p) {
 263 entry:
 264   %A = alloca [200 x i32]
 265   %B = alloca [200 x i32]
 266   br label %S1
 267
 268 S1:
 269   %indvar.1 = phi i64 [ 0, %entry ], [ %indvar.next.1, %S1 ]
 270   %arrayidx.1 = getelementptr [200 x i32], [200 x i32]* %A, i64 0, i64 %indvar.1
 271   store i32 10, i32* %arrayidx.1
 272   %indvar.next.1 = add i64 %indvar.1, 1
 273   %exitcond.1 = icmp ne i64 %indvar.next.1, 100
 274   br i1 %exitcond.1, label %S1, label %exit.1
 275
 276 exit.1:
 277   br label %S2
 278
 279 S2:
 280   %indvar.2 = phi i64 [ 0, %exit.1 ], [ %indvar.next.2, %S2 ]
 281   %sum = add i64 %indvar.2, %p
 282   %arrayidx.2.a = getelementptr [200 x i32], [200 x i32]* %A, i64 0, i64 %sum
 283   %arrayidx.2.b = getelementptr [200 x i32], [200 x i32]* %B, i64 0, i64 %indvar.2
 284   %val = load i32, i32* %arrayidx.2.a
 285   store i32 %val, i32* %arrayidx.2.b
 286   %indvar.next.2 = add i64 %indvar.2, 1
 287   %exitcond.2 = icmp ne i64 %indvar.next.2, 10
 288   br i1 %exitcond.2, label %S2, label %exit.2
 289
 290 exit.2:
 291   ret void
 292 }
 293