1 #include "llvm/CodeGen/MachineScheduler.h"
2 #include "gtest/gtest.h"
3
4 using namespace llvm;
5
6 #ifndef NDEBUG
TEST(ResourceSegmentsDeath,OverwriteOnRight)7 TEST(ResourceSegmentsDeath, OverwriteOnRight) {
8 auto X = ResourceSegments({{10, 20}});
9 EXPECT_DEATH(X.add({15, 30}), "A resource is being overwritten");
10 }
11
TEST(ResourceSegmentsDeath,OverwriteOnLeft)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
TEST(ResourceSegmentsDeath,FullOverwrite)18 TEST(ResourceSegmentsDeath, FullOverwrite) {
19 auto X = ResourceSegments({{10, 20}});
20 EXPECT_DEATH(X.add({15, 18}), "A resource is being overwritten");
21 }
22
TEST(ResourceSegmentsDeath,ZeroSizeIntervalsNotAllowed)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
TEST(ResourceSegments,ConsecutiveLeftNoOverlap)29 TEST(ResourceSegments, ConsecutiveLeftNoOverlap) {
30 auto X = ResourceSegments({{10, 20}});
31 X.add({7, 9});
32 EXPECT_EQ(X, ResourceSegments({{7, 9}, {10, 20}}));
33 }
34
TEST(ResourceSegments,ConsecutiveLeftWithOverlap)35 TEST(ResourceSegments, ConsecutiveLeftWithOverlap) {
36 auto X = ResourceSegments({{10, 20}});
37 X.add({7, 10});
38 EXPECT_EQ(X, ResourceSegments({{7, 20}}));
39 }
40
TEST(ResourceSegments,ConsecutiveRightNoOverlap)41 TEST(ResourceSegments, ConsecutiveRightNoOverlap) {
42 auto X = ResourceSegments({{10, 20}});
43 X.add({21, 22});
44 EXPECT_EQ(X, ResourceSegments({{10, 20}, {21, 22}}));
45 }
46
TEST(ResourceSegments,ConsecutiveRightWithOverlap)47 TEST(ResourceSegments, ConsecutiveRightWithOverlap) {
48 auto X = ResourceSegments({{10, 20}});
49 X.add({20, 22});
50 EXPECT_EQ(X, ResourceSegments({{10, 22}}));
51 }
52
TEST(ResourceSegments,Disjoint)53 TEST(ResourceSegments, Disjoint) {
54 auto X = ResourceSegments({{10, 20}});
55 X.add({22, 23});
56 EXPECT_EQ(X, ResourceSegments({{10, 20}, {22, 23}}));
57 }
58
TEST(ResourceSegments,SortAfterAdd)59 TEST(ResourceSegments, SortAfterAdd) {
60 auto X = ResourceSegments({{10, 20}, {3, 4}});
61 X.add({6, 8});
62 EXPECT_EQ(X, ResourceSegments({{3, 4}, {6, 8}, {10, 20}}));
63 }
64
TEST(ResourceSegments,AddWithCutOff)65 TEST(ResourceSegments, AddWithCutOff) {
66 auto X = ResourceSegments({{1, 2}, {3, 4}});
67 X.add({6, 8}, 2);
68 EXPECT_EQ(X, ResourceSegments({{3, 4}, {6, 8}}));
69 }
70
TEST(ResourceSegments,add_01)71 TEST(ResourceSegments, add_01) {
72 auto X = ResourceSegments({{10, 20}, {30, 40}});
73 X.add({21, 29});
74 EXPECT_EQ(X, ResourceSegments({{10, 20}, {21, 29}, {30, 40}}));
75 }
76
TEST(ResourceSegments,add_02)77 TEST(ResourceSegments, add_02) {
78 auto X = ResourceSegments({{10, 20}, {30, 40}});
79 X.add({22, 29});
80 EXPECT_EQ(X, ResourceSegments({{10, 20}, {22, 29}, {30, 40}}));
81 X.add({29, 30});
82 EXPECT_EQ(X, ResourceSegments({{10, 20}, {22, 40}}));
83 }
84
85 #ifndef NDEBUG
TEST(ResourceSegmentsDeath,add_empty)86 TEST(ResourceSegmentsDeath, add_empty) {
87 auto X = ResourceSegments({{10, 20}, {30, 40}});
88 X.add({22, 22});
89 EXPECT_EQ(X, ResourceSegments({{10, 20}, {30, 40}}));
90 }
91 #endif
92
TEST(ResourceSegments,sort_two)93 TEST(ResourceSegments, sort_two) {
94 EXPECT_EQ(ResourceSegments({{30, 40}, {10, 28}}),
95 ResourceSegments({{10, 28}, {30, 40}}));
96 }
97
TEST(ResourceSegments,sort_three)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
TEST(ResourceSegments,merge_two)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
TEST(ResourceSegments,merge_three)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
TEST(ResourceSegments,intersects)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
TEST(ResourceSegments,getFirstAvailableAtFromTop_oneCycle)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
TEST(ResourceSegments,getFirstAvailableAtFromTop_twoCycles)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
TEST(ResourceSegments,getFirstAvailableAtFromTop_twoCycles_Shifted)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
TEST(ResourceSegments,getFirstAvailableAtFromTop_twoCycles_Shifted_withGap)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
TEST(ResourceSegments,getFirstAvailableAtFromTop_basic)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
TEST(ResourceSegments,getFirstAvailableAtFromTop_advanced)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
TEST(ResourceSegments,getFirstAvailableAtFromBottom)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
TEST(ResourceSegments,getFirstAvailableAtFromBottom_01)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
TEST(ResourceSegments,getFirstAvailableAtFromBottom_02)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
TEST(ResourceSegments,getFirstAvailableAtFromBottom_02_shifted)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
TEST(ResourceSegments,getFirstAvailableAtFromBottom_03)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
TEST(ResourceSegments,getFirstAvailableAtFromBottom_03_shifted)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 }
TEST(ResourceSegments,getFirstAvailableAtFromBottom_empty)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