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 {
TEST(CodeLayout,ThreeFunctions)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
TEST(CodeLayout,HotChain)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 // -cdsort-max-chain-size disables forming a larger chain and therefore may
45 // change the result.
46 CDSortConfig Config;
47 Config.MaxChainSize = 3;
48 Order =
49 computeCacheDirectedLayout(Config, Sizes, Counts, Edges, CallOffsets);
50 EXPECT_THAT(Order, ElementsAreArray({0, 3, 4, 1, 2}));
51 }
52 }
53
TEST(CodeLayout,BreakLoop)54 TEST(CodeLayout, BreakLoop) {
55 // There are two loops (1,2,3) and (1,2,4). It is beneficial to place 4
56 // elsewhere.
57 const uint64_t Counts[6] = {177, 371, 196, 124, 70, 177};
58 std::vector<uint64_t> Sizes(std::size(Counts), 9);
59 const EdgeCount Edges[] = {{0, 1, 177}, {1, 2, 196}, {2, 3, 124}, {3, 1, 124},
60 {1, 5, 177}, {2, 4, 79}, {4, 1, 70}};
61 const std::vector<uint64_t> CallOffsets(std::size(Edges), 5);
62 auto Order = computeCacheDirectedLayout(Sizes, Counts, Edges, CallOffsets);
63 EXPECT_THAT(Order, ElementsAreArray({4, 0, 1, 2, 3, 5}));
64
65 // When node 0 is larger, it is beneficial to move node 4 closer to the
66 // (1,2,3) loop.
67 Sizes[0] = 18;
68 Order = computeCacheDirectedLayout(Sizes, Counts, Edges, CallOffsets);
69 EXPECT_THAT(Order, ElementsAreArray({0, 4, 1, 2, 3, 5}));
70 }
71 } // namespace
72