llvm/unittests/CodeGen/SchedBoundary.cpp

   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({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({7, 10});
  38   EXPECT_EQ(X, ResourceSegments({{7, 20}}));
  39 }
  40
  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
  47 TEST(ResourceSegments, ConsecutiveRightWithOverlap) {
  48   auto X = ResourceSegments({{10, 20}});
  49   X.add({20, 22});
  50   EXPECT_EQ(X, ResourceSegments({{10, 22}}));
  51 }
  52
  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
  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
  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
  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
  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
  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
  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 }