1 | #include "llvm/CodeGen/MachineScheduler.h" |
2 | #include "gtest/gtest.h" |
3 | |
4 | using namespace llvm; |
5 | |
6 | #ifndef NDEBUG |
7 | TEST(ResourceSegmentsDeath, OverwriteOnRight) { |
8 | auto X = ResourceSegments({{10, 20}}); |
9 | EXPECT_DEATH(X.add({15, 30}), "A resource is being overwritten" ); |
10 | } |
11 | |
12 | TEST(ResourceSegmentsDeath, OverwriteOnLeft) { |
13 | auto X = ResourceSegments({{10, 20}}); |
14 | EXPECT_DEATH(X.add({5, 11}), "A resource is being overwritten" ); |
15 | ; |
16 | } |
17 | |
18 | TEST(ResourceSegmentsDeath, FullOverwrite) { |
19 | auto X = ResourceSegments({{10, 20}}); |
20 | EXPECT_DEATH(X.add({15, 18}), "A resource is being overwritten" ); |
21 | } |
22 | |
23 | TEST(ResourceSegmentsDeath, ZeroSizeIntervalsNotAllowed) { |
24 | auto X = ResourceSegments({{10, 20}}); |
25 | EXPECT_DEATH(X.add({20, 30}, 0), "0-size interval history has no use." ); |
26 | } |
27 | #endif // NDEBUG |
28 | |
29 | TEST(ResourceSegments, ConsecutiveLeftNoOverlap) { |
30 | auto X = ResourceSegments({{10, 20}}); |
31 | X.add(A: {7, 9}); |
32 | EXPECT_EQ(X, ResourceSegments({{7, 9}, {10, 20}})); |
33 | } |
34 | |
35 | TEST(ResourceSegments, ConsecutiveLeftWithOverlap) { |
36 | auto X = ResourceSegments({{10, 20}}); |
37 | X.add(A: {7, 10}); |
38 | EXPECT_EQ(X, ResourceSegments({{7, 20}})); |
39 | } |
40 | |
41 | TEST(ResourceSegments, ConsecutiveRightNoOverlap) { |
42 | auto X = ResourceSegments({{10, 20}}); |
43 | X.add(A: {21, 22}); |
44 | EXPECT_EQ(X, ResourceSegments({{10, 20}, {21, 22}})); |
45 | } |
46 | |
47 | TEST(ResourceSegments, ConsecutiveRightWithOverlap) { |
48 | auto X = ResourceSegments({{10, 20}}); |
49 | X.add(A: {20, 22}); |
50 | EXPECT_EQ(X, ResourceSegments({{10, 22}})); |
51 | } |
52 | |
53 | TEST(ResourceSegments, Disjoint) { |
54 | auto X = ResourceSegments({{10, 20}}); |
55 | X.add(A: {22, 23}); |
56 | EXPECT_EQ(X, ResourceSegments({{10, 20}, {22, 23}})); |
57 | } |
58 | |
59 | TEST(ResourceSegments, SortAfterAdd) { |
60 | auto X = ResourceSegments({{10, 20}, {3, 4}}); |
61 | X.add(A: {6, 8}); |
62 | EXPECT_EQ(X, ResourceSegments({{3, 4}, {6, 8}, {10, 20}})); |
63 | } |
64 | |
65 | TEST(ResourceSegments, AddWithCutOff) { |
66 | auto X = ResourceSegments({{1, 2}, {3, 4}}); |
67 | X.add(A: {6, 8}, CutOff: 2); |
68 | EXPECT_EQ(X, ResourceSegments({{3, 4}, {6, 8}})); |
69 | } |
70 | |
71 | TEST(ResourceSegments, add_01) { |
72 | auto X = ResourceSegments({{10, 20}, {30, 40}}); |
73 | X.add(A: {21, 29}); |
74 | EXPECT_EQ(X, ResourceSegments({{10, 20}, {21, 29}, {30, 40}})); |
75 | } |
76 | |
77 | TEST(ResourceSegments, add_02) { |
78 | auto X = ResourceSegments({{10, 20}, {30, 40}}); |
79 | X.add(A: {22, 29}); |
80 | EXPECT_EQ(X, ResourceSegments({{10, 20}, {22, 29}, {30, 40}})); |
81 | X.add(A: {29, 30}); |
82 | EXPECT_EQ(X, ResourceSegments({{10, 20}, {22, 40}})); |
83 | } |
84 | |
85 | #ifndef NDEBUG |
86 | TEST(ResourceSegmentsDeath, add_empty) { |
87 | auto X = ResourceSegments({{10, 20}, {30, 40}}); |
88 | X.add(A: {22, 22}); |
89 | EXPECT_EQ(X, ResourceSegments({{10, 20}, {30, 40}})); |
90 | } |
91 | #endif |
92 | |
93 | TEST(ResourceSegments, sort_two) { |
94 | EXPECT_EQ(ResourceSegments({{30, 40}, {10, 28}}), |
95 | ResourceSegments({{10, 28}, {30, 40}})); |
96 | } |
97 | |
98 | TEST(ResourceSegments, sort_three) { |
99 | EXPECT_EQ(ResourceSegments({{30, 40}, {71, 200}, {10, 29}}), |
100 | ResourceSegments({{10, 29}, {30, 40}, {71, 200}})); |
101 | } |
102 | |
103 | TEST(ResourceSegments, merge_two) { |
104 | EXPECT_EQ(ResourceSegments({{10, 33}, {30, 40}}), |
105 | ResourceSegments({{10, 40}})); |
106 | EXPECT_EQ(ResourceSegments({{10, 30}, {30, 40}}), |
107 | ResourceSegments({{10, 40}})); |
108 | // Cycle 29 is resource free, so the interval is disjoint. |
109 | EXPECT_EQ(ResourceSegments({{10, 29}, {30, 40}}), |
110 | ResourceSegments({{10, 29}, {30, 40}})); |
111 | } |
112 | |
113 | TEST(ResourceSegments, merge_three) { |
114 | EXPECT_EQ(ResourceSegments({{10, 29}, {30, 40}, {71, 200}}), |
115 | ResourceSegments({{10, 29}, {30, 40}, {71, 200}})); |
116 | EXPECT_EQ(ResourceSegments({{10, 29}, {30, 40}, {41, 200}}), |
117 | ResourceSegments({{10, 29}, {30, 40}, {41, 200}})); |
118 | EXPECT_EQ(ResourceSegments({{10, 30}, {30, 40}, {40, 200}}), |
119 | ResourceSegments({{10, 200}})); |
120 | EXPECT_EQ(ResourceSegments({{10, 28}, {30, 71}, {71, 200}}), |
121 | ResourceSegments({{10, 28}, {30, 200}})); |
122 | } |
123 | |
124 | //////////////////////////////////////////////////////////////////////////////// |
125 | // Intersection |
126 | TEST(ResourceSegments, intersects) { |
127 | // no intersect |
128 | EXPECT_FALSE(ResourceSegments::intersects({0, 1}, {3, 4})); |
129 | EXPECT_FALSE(ResourceSegments::intersects({3, 4}, {0, 1})); |
130 | EXPECT_FALSE(ResourceSegments::intersects({0, 3}, {3, 4})); |
131 | EXPECT_FALSE(ResourceSegments::intersects({3, 4}, {0, 3})); |
132 | |
133 | // Share one boundary |
134 | EXPECT_TRUE(ResourceSegments::intersects({5, 6}, {5, 10})); |
135 | EXPECT_TRUE(ResourceSegments::intersects({5, 10}, {5, 6})); |
136 | |
137 | // full intersect |
138 | EXPECT_TRUE(ResourceSegments::intersects({1, 2}, {0, 3})); |
139 | EXPECT_TRUE(ResourceSegments::intersects({1, 2}, {0, 2})); |
140 | EXPECT_TRUE(ResourceSegments::intersects({0, 3}, {1, 2})); |
141 | EXPECT_TRUE(ResourceSegments::intersects({0, 2}, {1, 2})); |
142 | |
143 | // right intersect |
144 | EXPECT_TRUE(ResourceSegments::intersects({2, 4}, {0, 3})); |
145 | EXPECT_TRUE(ResourceSegments::intersects({0, 3}, {2, 4})); |
146 | |
147 | // left intersect |
148 | EXPECT_TRUE(ResourceSegments::intersects({2, 4}, {3, 5})); |
149 | EXPECT_TRUE(ResourceSegments::intersects({3, 5}, {2, 4})); |
150 | } |
151 | |
152 | //////////////////////////////////////////////////////////////////////////////// |
153 | // TOP-DOWN getFirstAvailableAt |
154 | TEST(ResourceSegments, getFirstAvailableAtFromTop_oneCycle) { |
155 | auto X = ResourceSegments({{2, 5}}); |
156 | // 0 1 2 3 4 5 6 7 |
157 | // Res X X X |
158 | // ...X... |
159 | EXPECT_EQ(X.getFirstAvailableAtFromTop(0, 0, 1), 0U); |
160 | EXPECT_EQ(X.getFirstAvailableAtFromTop(1, 0, 1), 1U); |
161 | // Skip to five when hitting cycle 2 |
162 | EXPECT_EQ(X.getFirstAvailableAtFromTop(2, 0, 1), 5U); |
163 | } |
164 | |
165 | TEST(ResourceSegments, getFirstAvailableAtFromTop_twoCycles) { |
166 | auto X = ResourceSegments({{4, 5}}); |
167 | // 0 1 2 3 4 5 6 7 |
168 | // Res X |
169 | // ...X X.... |
170 | EXPECT_EQ(X.getFirstAvailableAtFromTop(0, 0, 2), 0U); |
171 | EXPECT_EQ(X.getFirstAvailableAtFromTop(1, 0, 2), 1U); |
172 | EXPECT_EQ(X.getFirstAvailableAtFromTop(2, 0, 2), 2U); |
173 | // Skip to cycle 5 |
174 | EXPECT_EQ(X.getFirstAvailableAtFromTop(3, 0, 2), 5U); |
175 | } |
176 | |
177 | TEST(ResourceSegments, getFirstAvailableAtFromTop_twoCycles_Shifted) { |
178 | auto X = ResourceSegments({{4, 5}}); |
179 | // 0 1 2 3 4 5 6 7 |
180 | // Res X |
181 | // ...c X X... |
182 | EXPECT_EQ(X.getFirstAvailableAtFromTop(0, 1, 3), 0U); |
183 | EXPECT_EQ(X.getFirstAvailableAtFromTop(1, 1, 3), 1U); |
184 | // Skip to cycle 4 |
185 | EXPECT_EQ(X.getFirstAvailableAtFromTop(2, 1, 3), 4U); |
186 | // Stay con cycle 4 |
187 | // 0 1 2 3 4 5 6 7 |
188 | // Res X |
189 | // ...c X X... |
190 | EXPECT_EQ(X.getFirstAvailableAtFromTop(3, 1, 3), 4U); |
191 | // |
192 | EXPECT_EQ(X.getFirstAvailableAtFromTop(4, 1, 3), 4U); |
193 | EXPECT_EQ(X.getFirstAvailableAtFromTop(5, 1, 3), 5U); |
194 | } |
195 | |
196 | TEST(ResourceSegments, getFirstAvailableAtFromTop_twoCycles_Shifted_withGap) { |
197 | auto X = ResourceSegments({{4, 5}, {7, 9}}); |
198 | // 0 1 2 3 4 5 6 7 8 9 |
199 | // Res X X X |
200 | // c X X |
201 | EXPECT_EQ(X.getFirstAvailableAtFromTop(1, 1, 3), 1U); |
202 | // 0 1 2 3 4 5 6 7 8 9 |
203 | // Res X X X |
204 | // c X X --> moves to 4 |
205 | EXPECT_EQ(X.getFirstAvailableAtFromTop(2, 1, 3), 4U); |
206 | // 0 1 2 3 4 5 6 7 8 9 |
207 | // Res X X X |
208 | // c X X --> moves to 4 |
209 | EXPECT_EQ(X.getFirstAvailableAtFromTop(3, 1, 3), 4U); |
210 | // 0 1 2 3 4 5 6 7 8 9 |
211 | // Res X X X |
212 | // c X X --> stays on 4 |
213 | EXPECT_EQ(X.getFirstAvailableAtFromTop(4, 1, 3), 4U); |
214 | // 0 1 2 3 4 5 6 7 8 9 |
215 | // Res X X X |
216 | // c X X --> skips to 8 |
217 | EXPECT_EQ(X.getFirstAvailableAtFromTop(5, 1, 3), 8U); |
218 | } |
219 | |
220 | TEST(ResourceSegments, getFirstAvailableAtFromTop_basic) { |
221 | auto X = ResourceSegments({{5, 10}, {30, 40}}); |
222 | |
223 | EXPECT_EQ(X.getFirstAvailableAtFromTop(0, 3, 4), 0U); |
224 | EXPECT_EQ(X.getFirstAvailableAtFromTop(1, 3, 4), 1U); |
225 | EXPECT_EQ(X.getFirstAvailableAtFromTop(2, 3, 4), 7U); |
226 | EXPECT_EQ(X.getFirstAvailableAtFromTop(3, 3, 4), 7U); |
227 | EXPECT_EQ(X.getFirstAvailableAtFromTop(4, 3, 4), 7U); |
228 | EXPECT_EQ(X.getFirstAvailableAtFromTop(5, 3, 4), 7U); |
229 | EXPECT_EQ(X.getFirstAvailableAtFromTop(6, 3, 4), 7U); |
230 | EXPECT_EQ(X.getFirstAvailableAtFromTop(7, 3, 4), 7U); |
231 | // Check the empty range between the two intervals of X. |
232 | EXPECT_EQ(X.getFirstAvailableAtFromTop(15, 3, 4), 15U); |
233 | // Overlap the second interval. |
234 | EXPECT_EQ(X.getFirstAvailableAtFromTop(28, 3, 4), 37U); |
235 | } |
236 | |
237 | TEST(ResourceSegments, getFirstAvailableAtFromTop_advanced) { |
238 | auto X = ResourceSegments({{3, 6}, {7, 9}, {11, 14}, {30, 33}}); |
239 | |
240 | EXPECT_EQ(X.getFirstAvailableAtFromTop(2, 4, 5), 2U); |
241 | |
242 | EXPECT_EQ(X.getFirstAvailableAtFromTop(2, 3, 4), 3U); |
243 | // Can schedule at 7U because the interval [14, 19[ does not |
244 | // overlap any of the intervals in X. |
245 | EXPECT_EQ(X.getFirstAvailableAtFromTop(1, 7, 12), 7U); |
246 | } |
247 | |
248 | //////////////////////////////////////////////////////////////////////////////// |
249 | // BOTTOM-UP getFirstAvailableAt |
250 | TEST(ResourceSegments, getFirstAvailableAtFromBottom) { |
251 | // Scheduling cycles move to the left... |
252 | // |
253 | // 41 40 39 ... 31 30 29 ... 21 20 19 ... 11 10 9 8 7 6 ... 1 0 |
254 | // Res X X X X X X X X |
255 | // X X X X X X |
256 | // Time (relative to instruction execution) 0 1 2 3 4 5 |
257 | auto X = ResourceSegments({{10, 20}, {30, 40}}); |
258 | // .. but time (instruction cycle) moves to the right. Therefore, it |
259 | // is always possible to llocate a resource to the right of 0 if 0 |
260 | // is not taken, because the right side of the scheduling cycles is |
261 | // empty. |
262 | EXPECT_EQ(X.getFirstAvailableAtFromBottom(0, 0, 1), 0U); |
263 | EXPECT_EQ(X.getFirstAvailableAtFromBottom(0, 0, 9), 0U); |
264 | EXPECT_EQ(X.getFirstAvailableAtFromBottom(0, 0, 10), 0U); |
265 | EXPECT_EQ(X.getFirstAvailableAtFromBottom(0, 0, 20), 0U); |
266 | EXPECT_EQ(X.getFirstAvailableAtFromBottom(0, 0, 21), 0U); |
267 | EXPECT_EQ(X.getFirstAvailableAtFromBottom(0, 0, 22), 0U); |
268 | EXPECT_EQ(X.getFirstAvailableAtFromBottom(0, 0, 29), 0U); |
269 | EXPECT_EQ(X.getFirstAvailableAtFromBottom(0, 0, 30), 0U); |
270 | } |
271 | |
272 | TEST(ResourceSegments, getFirstAvailableAtFromBottom_01) { |
273 | auto X = ResourceSegments({{3, 7}}); |
274 | // 10 9 8 7 6 5 4 3 2 1 0 |
275 | // X X X X |
276 | // ...X... <- one cycle resource placement |
277 | EXPECT_EQ(X.getFirstAvailableAtFromBottom(0, 0, 1), 0U); |
278 | EXPECT_EQ(X.getFirstAvailableAtFromBottom(1, 0, 1), 1U); |
279 | EXPECT_EQ(X.getFirstAvailableAtFromBottom(2, 0, 1), 2U); |
280 | // Skip to 7 |
281 | EXPECT_EQ(X.getFirstAvailableAtFromBottom(3, 0, 1), 7U); |
282 | } |
283 | |
284 | TEST(ResourceSegments, getFirstAvailableAtFromBottom_02) { |
285 | auto X = ResourceSegments({{3, 7}}); |
286 | // 10 9 8 7 6 5 4 3 2 1 0 |
287 | // X X X X |
288 | // ...X X... <- two cycles resource placement |
289 | EXPECT_EQ(X.getFirstAvailableAtFromBottom(0, 0, 2), 0U); |
290 | EXPECT_EQ(X.getFirstAvailableAtFromBottom(1, 0, 2), 1U); |
291 | EXPECT_EQ(X.getFirstAvailableAtFromBottom(2, 0, 2), 2U); |
292 | // skip to 8 |
293 | EXPECT_EQ(X.getFirstAvailableAtFromBottom(3, 0, 2), 8U); |
294 | } |
295 | |
296 | TEST(ResourceSegments, getFirstAvailableAtFromBottom_02_shifted) { |
297 | auto X = ResourceSegments({{3, 7}}); |
298 | // 10 9 8 7 6 5 4 3 2 1 0 |
299 | // X X X X |
300 | // c X X <- two cycles resource placement but shifted by 1 |
301 | // 0 1 2 <- cycles relative to the execution of the |
302 | // instruction |
303 | EXPECT_EQ(X.getFirstAvailableAtFromBottom(0, 1, 3), 0U); |
304 | EXPECT_EQ(X.getFirstAvailableAtFromBottom(1, 1, 3), 1U); |
305 | EXPECT_EQ(X.getFirstAvailableAtFromBottom(2, 1, 3), 2U); |
306 | EXPECT_EQ(X.getFirstAvailableAtFromBottom(3, 1, 3), 3U); |
307 | // 10 9 8 7 6 5 4 3 2 1 0 |
308 | // X X X X |
309 | // c X X -> skip to 9 |
310 | // 0 1 2 |
311 | EXPECT_EQ(X.getFirstAvailableAtFromBottom(4, 1, 3), 9U); |
312 | EXPECT_EQ(X.getFirstAvailableAtFromBottom(5, 1, 3), 9U); |
313 | EXPECT_EQ(X.getFirstAvailableAtFromBottom(6, 1, 3), 9U); |
314 | EXPECT_EQ(X.getFirstAvailableAtFromBottom(7, 1, 3), 9U); |
315 | // 10 9 8 7 6 5 4 3 2 1 0 |
316 | // X X X X |
317 | // c X X <- skip to 9 |
318 | // 0 1 2 |
319 | EXPECT_EQ(X.getFirstAvailableAtFromBottom(8, 1, 3), 9U); |
320 | // 10 9 8 7 6 5 4 3 2 1 0 |
321 | // X X X X |
322 | // c X X |
323 | // 0 1 2 |
324 | EXPECT_EQ(X.getFirstAvailableAtFromBottom(9, 1, 3), 9U); |
325 | // 10 9 8 7 6 5 4 3 2 1 0 |
326 | // X X X X |
327 | // c X X |
328 | // 0 1 2 |
329 | EXPECT_EQ(X.getFirstAvailableAtFromBottom(10, 1, 3), 10U); |
330 | } |
331 | |
332 | TEST(ResourceSegments, getFirstAvailableAtFromBottom_03) { |
333 | auto X = ResourceSegments({{1, 2}, {3, 7}}); |
334 | // 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 |
335 | // X X X X X |
336 | // X |
337 | EXPECT_EQ(X.getFirstAvailableAtFromBottom(0, 0, 1), 0U); |
338 | // 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 |
339 | // X X X X X |
340 | // X |
341 | EXPECT_EQ(X.getFirstAvailableAtFromBottom(1, 0, 1), 2U); |
342 | // 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 |
343 | // X X X X X |
344 | // X |
345 | EXPECT_EQ(X.getFirstAvailableAtFromBottom(2, 0, 1), 2U); |
346 | // 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 |
347 | // X X X X X |
348 | // X X X X X |
349 | EXPECT_EQ(X.getFirstAvailableAtFromBottom(2, 0, 5), 11U); |
350 | EXPECT_EQ(X.getFirstAvailableAtFromBottom(3, 0, 5), 11U); |
351 | EXPECT_EQ(X.getFirstAvailableAtFromBottom(5, 0, 5), 11U); |
352 | EXPECT_EQ(X.getFirstAvailableAtFromBottom(11, 0, 5), 11U); |
353 | // 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 |
354 | // X X X X X |
355 | // X X X X X |
356 | EXPECT_EQ(X.getFirstAvailableAtFromBottom(12, 0, 5), 12U); |
357 | } |
358 | |
359 | TEST(ResourceSegments, getFirstAvailableAtFromBottom_03_shifted) { |
360 | // 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 -1 -2 -3 |
361 | // X X X X X X X X |
362 | auto X = ResourceSegments({{-3, -1}, {1, 2}, {3, 7}, {9, 10}}); |
363 | |
364 | EXPECT_EQ(X.getFirstAvailableAtFromBottom(0, 1, 2), 0U); |
365 | EXPECT_EQ(X.getFirstAvailableAtFromBottom(0, 0, 2), 0U); |
366 | |
367 | // 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 -1 -2 -3 |
368 | // X X X X X X X X |
369 | // X X X -> skip to cycle 12 |
370 | EXPECT_EQ(X.getFirstAvailableAtFromBottom(0, 0, 3), 12U); |
371 | // 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 -1 -2 -3 |
372 | // X X X X X X X X |
373 | // X X |
374 | EXPECT_EQ(X.getFirstAvailableAtFromBottom(0, 1, 3), 1U); |
375 | EXPECT_EQ(X.getFirstAvailableAtFromBottom(0, 1, 4), 13U); |
376 | EXPECT_EQ(X.getFirstAvailableAtFromBottom(12, 1, 4), 13U); |
377 | // 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 -1 -2 -3 |
378 | // X X X X X X X X |
379 | // c X X X |
380 | EXPECT_EQ(X.getFirstAvailableAtFromBottom(13, 1, 4), 13U); |
381 | // 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 -1 -2 -3 |
382 | // X X X X X X X X |
383 | // X X |
384 | EXPECT_EQ(X.getFirstAvailableAtFromBottom(1, 1, 3), 1U); |
385 | // 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 -1 -2 -3 |
386 | // X X X X X X X X |
387 | // C X X 0 -> skip to cycle 9 |
388 | EXPECT_EQ(X.getFirstAvailableAtFromBottom(2, 1, 3), 9U); |
389 | // 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 -1 -2 -3 |
390 | // X X X X X X X X |
391 | // C C X X X X X -> skip to cycle 16 |
392 | EXPECT_EQ(X.getFirstAvailableAtFromBottom(3, 2, 7), 16U); |
393 | } |
394 | TEST(ResourceSegments, getFirstAvailableAtFromBottom_empty) { |
395 | // Empty resource usage can accept schediling at any cycle |
396 | auto X = ResourceSegments(); |
397 | EXPECT_EQ(X.getFirstAvailableAtFromBottom(0, 0, 1), 0U); |
398 | EXPECT_EQ(X.getFirstAvailableAtFromBottom(17, 1, 22), 17U); |
399 | } |
400 | |