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