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