1 #include "llvm/Transforms/Utils/CodeLayout.h" 2 #include "gmock/gmock.h" 3 #include "gtest/gtest.h" 4 #include <vector> 5 6 using namespace llvm; 7 using namespace llvm::codelayout; 8 using testing::ElementsAreArray; 9 10 namespace { 11 TEST(CodeLayout, ThreeFunctions) { 12 // Place the most likely successor (2) first. 13 { 14 const uint64_t Counts[3] = {140, 40, 140}; 15 const std::vector<uint64_t> Sizes(std::size(Counts), 9); 16 const EdgeCount Edges[] = {{0, 1, 40}, {0, 2, 100}, {1, 2, 40}}; 17 const std::vector<uint64_t> CallOffsets(std::size(Edges), 5); 18 auto Order = computeCacheDirectedLayout(Sizes, Counts, Edges, CallOffsets); 19 EXPECT_THAT(Order, ElementsAreArray({0, 2, 1})); 20 } 21 22 // Prefer fallthroughs even in the presence of a heavy successor. 23 { 24 const uint64_t Counts[3] = {180, 80, 180}; 25 const std::vector<uint64_t> Sizes(std::size(Counts), 9); 26 const EdgeCount Edges[] = {{0, 1, 80}, {0, 2, 100}, {1, 2, 80}}; 27 const uint64_t CallOffsets[] = {9, 5, 9}; 28 auto Order = computeCacheDirectedLayout(Sizes, Counts, Edges, CallOffsets); 29 EXPECT_THAT(Order, ElementsAreArray({0, 1, 2})); 30 } 31 } 32 33 TEST(CodeLayout, HotChain) { 34 // Place the hot chain (0,3,4,2) continuously. 35 { 36 const uint64_t Counts[5] = {22, 7, 22, 15, 46}; 37 const std::vector<uint64_t> Sizes(std::size(Counts), 9); 38 const EdgeCount Edges[] = {{0, 1, 7}, {1, 2, 7}, {0, 3, 15}, 39 {3, 4, 15}, {4, 4, 31}, {4, 2, 15}}; 40 const std::vector<uint64_t> CallOffsets(std::size(Edges), 5); 41 auto Order = computeCacheDirectedLayout(Sizes, Counts, Edges, CallOffsets); 42 EXPECT_THAT(Order, ElementsAreArray({0, 3, 4, 2, 1})); 43 } 44 } 45 46 TEST(CodeLayout, BreakLoop) { 47 // There are two loops (1,2,3) and (1,2,4). It is beneficial to place 4 48 // elsewhere. 49 const uint64_t Counts[6] = {177, 371, 196, 124, 70, 177}; 50 std::vector<uint64_t> Sizes(std::size(Counts), 9); 51 const EdgeCount Edges[] = {{0, 1, 177}, {1, 2, 196}, {2, 3, 124}, {3, 1, 124}, 52 {1, 5, 177}, {2, 4, 79}, {4, 1, 70}}; 53 const std::vector<uint64_t> CallOffsets(std::size(Edges), 5); 54 auto Order = computeCacheDirectedLayout(Sizes, Counts, Edges, CallOffsets); 55 EXPECT_THAT(Order, ElementsAreArray({4, 0, 1, 2, 3, 5})); 56 57 // When node 0 is larger, it is beneficial to move node 4 closer to the 58 // (1,2,3) loop. 59 Sizes[0] = 18; 60 Order = computeCacheDirectedLayout(Sizes, Counts, Edges, CallOffsets); 61 EXPECT_THAT(Order, ElementsAreArray({0, 4, 1, 2, 3, 5})); 62 } 63 } // namespace 64