400 lines · cpp
1#include "llvm/CodeGen/MachineScheduler.h"2#include "gtest/gtest.h"3 4using namespace llvm;5 6#ifndef NDEBUG7TEST(ResourceSegmentsDeath, OverwriteOnRight) {8 auto X = ResourceSegments({{10, 20}});9 EXPECT_DEATH(X.add({15, 30}), "A resource is being overwritten");10}11 12TEST(ResourceSegmentsDeath, OverwriteOnLeft) {13 auto X = ResourceSegments({{10, 20}});14 EXPECT_DEATH(X.add({5, 11}), "A resource is being overwritten");15 ;16}17 18TEST(ResourceSegmentsDeath, FullOverwrite) {19 auto X = ResourceSegments({{10, 20}});20 EXPECT_DEATH(X.add({15, 18}), "A resource is being overwritten");21}22 23TEST(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 // NDEBUG28 29TEST(ResourceSegments, ConsecutiveLeftNoOverlap) {30 auto X = ResourceSegments({{10, 20}});31 X.add({7, 9});32 EXPECT_EQ(X, ResourceSegments({{7, 9}, {10, 20}}));33}34 35TEST(ResourceSegments, ConsecutiveLeftWithOverlap) {36 auto X = ResourceSegments({{10, 20}});37 X.add({7, 10});38 EXPECT_EQ(X, ResourceSegments({{7, 20}}));39}40 41TEST(ResourceSegments, ConsecutiveRightNoOverlap) {42 auto X = ResourceSegments({{10, 20}});43 X.add({21, 22});44 EXPECT_EQ(X, ResourceSegments({{10, 20}, {21, 22}}));45}46 47TEST(ResourceSegments, ConsecutiveRightWithOverlap) {48 auto X = ResourceSegments({{10, 20}});49 X.add({20, 22});50 EXPECT_EQ(X, ResourceSegments({{10, 22}}));51}52 53TEST(ResourceSegments, Disjoint) {54 auto X = ResourceSegments({{10, 20}});55 X.add({22, 23});56 EXPECT_EQ(X, ResourceSegments({{10, 20}, {22, 23}}));57}58 59TEST(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 65TEST(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 71TEST(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 77TEST(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 NDEBUG86TEST(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#endif92 93TEST(ResourceSegments, sort_two) {94 EXPECT_EQ(ResourceSegments({{30, 40}, {10, 28}}),95 ResourceSegments({{10, 28}, {30, 40}}));96}97 98TEST(ResourceSegments, sort_three) {99 EXPECT_EQ(ResourceSegments({{30, 40}, {71, 200}, {10, 29}}),100 ResourceSegments({{10, 29}, {30, 40}, {71, 200}}));101}102 103TEST(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 113TEST(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// Intersection126TEST(ResourceSegments, intersects) {127 // no intersect128 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 boundary134 EXPECT_TRUE(ResourceSegments::intersects({5, 6}, {5, 10}));135 EXPECT_TRUE(ResourceSegments::intersects({5, 10}, {5, 6}));136 137 // full intersect138 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 intersect144 EXPECT_TRUE(ResourceSegments::intersects({2, 4}, {0, 3}));145 EXPECT_TRUE(ResourceSegments::intersects({0, 3}, {2, 4}));146 147 // left intersect148 EXPECT_TRUE(ResourceSegments::intersects({2, 4}, {3, 5}));149 EXPECT_TRUE(ResourceSegments::intersects({3, 5}, {2, 4}));150}151 152////////////////////////////////////////////////////////////////////////////////153// TOP-DOWN getFirstAvailableAt154TEST(ResourceSegments, getFirstAvailableAtFromTop_oneCycle) {155 auto X = ResourceSegments({{2, 5}});156 // 0 1 2 3 4 5 6 7157 // Res X X X158 // ...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 2162 EXPECT_EQ(X.getFirstAvailableAtFromTop(2, 0, 1), 5U);163}164 165TEST(ResourceSegments, getFirstAvailableAtFromTop_twoCycles) {166 auto X = ResourceSegments({{4, 5}});167 // 0 1 2 3 4 5 6 7168 // Res X169 // ...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 5174 EXPECT_EQ(X.getFirstAvailableAtFromTop(3, 0, 2), 5U);175}176 177TEST(ResourceSegments, getFirstAvailableAtFromTop_twoCycles_Shifted) {178 auto X = ResourceSegments({{4, 5}});179 // 0 1 2 3 4 5 6 7180 // Res X181 // ...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 4185 EXPECT_EQ(X.getFirstAvailableAtFromTop(2, 1, 3), 4U);186 // Stay con cycle 4187 // 0 1 2 3 4 5 6 7188 // Res X189 // ...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 196TEST(ResourceSegments, getFirstAvailableAtFromTop_twoCycles_Shifted_withGap) {197 auto X = ResourceSegments({{4, 5}, {7, 9}});198 // 0 1 2 3 4 5 6 7 8 9199 // Res X X X200 // c X X201 EXPECT_EQ(X.getFirstAvailableAtFromTop(1, 1, 3), 1U);202 // 0 1 2 3 4 5 6 7 8 9203 // Res X X X204 // c X X --> moves to 4205 EXPECT_EQ(X.getFirstAvailableAtFromTop(2, 1, 3), 4U);206 // 0 1 2 3 4 5 6 7 8 9207 // Res X X X208 // c X X --> moves to 4209 EXPECT_EQ(X.getFirstAvailableAtFromTop(3, 1, 3), 4U);210 // 0 1 2 3 4 5 6 7 8 9211 // Res X X X212 // c X X --> stays on 4213 EXPECT_EQ(X.getFirstAvailableAtFromTop(4, 1, 3), 4U);214 // 0 1 2 3 4 5 6 7 8 9215 // Res X X X216 // c X X --> skips to 8217 EXPECT_EQ(X.getFirstAvailableAtFromTop(5, 1, 3), 8U);218}219 220TEST(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 237TEST(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 not244 // overlap any of the intervals in X.245 EXPECT_EQ(X.getFirstAvailableAtFromTop(1, 7, 12), 7U);246}247 248////////////////////////////////////////////////////////////////////////////////249// BOTTOM-UP getFirstAvailableAt250TEST(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 0254 // Res X X X X X X X X255 // X X X X X X256 // Time (relative to instruction execution) 0 1 2 3 4 5257 auto X = ResourceSegments({{10, 20}, {30, 40}});258 // .. but time (instruction cycle) moves to the right. Therefore, it259 // is always possible to llocate a resource to the right of 0 if 0260 // is not taken, because the right side of the scheduling cycles is261 // 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 272TEST(ResourceSegments, getFirstAvailableAtFromBottom_01) {273 auto X = ResourceSegments({{3, 7}});274 // 10 9 8 7 6 5 4 3 2 1 0275 // X X X X276 // ...X... <- one cycle resource placement277 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 7281 EXPECT_EQ(X.getFirstAvailableAtFromBottom(3, 0, 1), 7U);282}283 284TEST(ResourceSegments, getFirstAvailableAtFromBottom_02) {285 auto X = ResourceSegments({{3, 7}});286 // 10 9 8 7 6 5 4 3 2 1 0287 // X X X X288 // ...X X... <- two cycles resource placement289 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 8293 EXPECT_EQ(X.getFirstAvailableAtFromBottom(3, 0, 2), 8U);294}295 296TEST(ResourceSegments, getFirstAvailableAtFromBottom_02_shifted) {297 auto X = ResourceSegments({{3, 7}});298 // 10 9 8 7 6 5 4 3 2 1 0299 // X X X X300 // c X X <- two cycles resource placement but shifted by 1301 // 0 1 2 <- cycles relative to the execution of the302 // instruction303 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 0308 // X X X X309 // c X X -> skip to 9310 // 0 1 2311 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 0316 // X X X X317 // c X X <- skip to 9318 // 0 1 2319 EXPECT_EQ(X.getFirstAvailableAtFromBottom(8, 1, 3), 9U);320 // 10 9 8 7 6 5 4 3 2 1 0321 // X X X X322 // c X X323 // 0 1 2324 EXPECT_EQ(X.getFirstAvailableAtFromBottom(9, 1, 3), 9U);325 // 10 9 8 7 6 5 4 3 2 1 0326 // X X X X327 // c X X328 // 0 1 2329 EXPECT_EQ(X.getFirstAvailableAtFromBottom(10, 1, 3), 10U);330}331 332TEST(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 0335 // X X X X X336 // X337 EXPECT_EQ(X.getFirstAvailableAtFromBottom(0, 0, 1), 0U);338 // 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0339 // X X X X X340 // X341 EXPECT_EQ(X.getFirstAvailableAtFromBottom(1, 0, 1), 2U);342 // 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0343 // X X X X X344 // X345 EXPECT_EQ(X.getFirstAvailableAtFromBottom(2, 0, 1), 2U);346 // 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0347 // X X X X X348 // X X X X X349 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 0354 // X X X X X355 // X X X X X356 EXPECT_EQ(X.getFirstAvailableAtFromBottom(12, 0, 5), 12U);357}358 359TEST(ResourceSegments, getFirstAvailableAtFromBottom_03_shifted) {360 // 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 -1 -2 -3361 // X X X X X X X X362 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 -3368 // X X X X X X X X369 // X X X -> skip to cycle 12370 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 -3372 // X X X X X X X X373 // X X374 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 -3378 // X X X X X X X X379 // c X X X380 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 -3382 // X X X X X X X X383 // X X384 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 -3386 // X X X X X X X X387 // C X X 0 -> skip to cycle 9388 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 -3390 // X X X X X X X X391 // C C X X X X X -> skip to cycle 16392 EXPECT_EQ(X.getFirstAvailableAtFromBottom(3, 2, 7), 16U);393}394TEST(ResourceSegments, getFirstAvailableAtFromBottom_empty) {395 // Empty resource usage can accept schediling at any cycle396 auto X = ResourceSegments();397 EXPECT_EQ(X.getFirstAvailableAtFromBottom(0, 0, 1), 0U);398 EXPECT_EQ(X.getFirstAvailableAtFromBottom(17, 1, 22), 17U);399}400