1 | //=== - unittest/Support/OptimizedStructLayoutTest.cpp - Layout tests -----===// |
2 | // |
3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
4 | // See https://llvm.org/LICENSE.txt for license information. |
5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
6 | // |
7 | //===----------------------------------------------------------------------===// |
8 | |
9 | #include "llvm/Support/OptimizedStructLayout.h" |
10 | #include "gtest/gtest.h" |
11 | |
12 | using namespace llvm; |
13 | |
14 | namespace { |
15 | |
16 | class LayoutTest { |
17 | struct Field { |
18 | uint64_t Size; |
19 | Align Alignment; |
20 | uint64_t ForcedOffset; |
21 | uint64_t ExpectedOffset; |
22 | }; |
23 | |
24 | SmallVector<Field, 16> Fields; |
25 | bool Verified = false; |
26 | |
27 | public: |
28 | LayoutTest() {} |
29 | LayoutTest(const LayoutTest &) = delete; |
30 | LayoutTest &operator=(const LayoutTest &) = delete; |
31 | ~LayoutTest() { assert(Verified); } |
32 | |
33 | LayoutTest &flexible(uint64_t Size, uint64_t Alignment, |
34 | uint64_t ExpectedOffset) { |
35 | Fields.push_back(Elt: {.Size: Size, .Alignment: Align(Alignment), |
36 | .ForcedOffset: OptimizedStructLayoutField::FlexibleOffset, .ExpectedOffset: ExpectedOffset}); |
37 | return *this; |
38 | } |
39 | |
40 | LayoutTest &fixed(uint64_t Size, uint64_t Alignment, uint64_t Offset) { |
41 | Fields.push_back(Elt: {.Size: Size, .Alignment: Align(Alignment), .ForcedOffset: Offset, .ExpectedOffset: Offset}); |
42 | return *this; |
43 | } |
44 | |
45 | void verify(uint64_t ExpectedSize, uint64_t ExpectedAlignment) { |
46 | SmallVector<OptimizedStructLayoutField, 8> LayoutFields; |
47 | LayoutFields.reserve(N: Fields.size()); |
48 | for (auto &F : Fields) |
49 | LayoutFields.emplace_back(Args: &F, Args&: F.Size, Args&: F.Alignment, Args&: F.ForcedOffset); |
50 | |
51 | auto SizeAndAlign = performOptimizedStructLayout(Fields: LayoutFields); |
52 | |
53 | EXPECT_EQ(SizeAndAlign.first, ExpectedSize); |
54 | EXPECT_EQ(SizeAndAlign.second, Align(ExpectedAlignment)); |
55 | |
56 | for (auto &LF : LayoutFields) { |
57 | auto &F = *static_cast<const Field *>(LF.Id); |
58 | EXPECT_EQ(LF.Offset, F.ExpectedOffset); |
59 | } |
60 | |
61 | Verified = true; |
62 | } |
63 | }; |
64 | |
65 | } |
66 | |
67 | TEST(OptimizedStructLayoutTest, Basic) { |
68 | LayoutTest() |
69 | .flexible(Size: 12, Alignment: 4, ExpectedOffset: 8) |
70 | .flexible(Size: 8, Alignment: 8, ExpectedOffset: 0) |
71 | .flexible(Size: 4, Alignment: 4, ExpectedOffset: 20) |
72 | .verify(ExpectedSize: 24, ExpectedAlignment: 8); |
73 | } |
74 | |
75 | TEST(OptimizedStructLayoutTest, OddSize) { |
76 | LayoutTest() |
77 | .flexible(Size: 8, Alignment: 8, ExpectedOffset: 16) |
78 | .flexible(Size: 4, Alignment: 4, ExpectedOffset: 12) |
79 | .flexible(Size: 1, Alignment: 1, ExpectedOffset: 10) |
80 | .flexible(Size: 10, Alignment: 8, ExpectedOffset: 0) |
81 | .verify(ExpectedSize: 24, ExpectedAlignment: 8); |
82 | } |
83 | |
84 | TEST(OptimizedStructLayoutTest, Gaps) { |
85 | LayoutTest() |
86 | .fixed(Size: 4, Alignment: 4, Offset: 8) |
87 | .fixed(Size: 4, Alignment: 4, Offset: 16) |
88 | .flexible(Size: 4, Alignment: 4, ExpectedOffset: 0) |
89 | .flexible(Size: 4, Alignment: 4, ExpectedOffset: 4) |
90 | .flexible(Size: 4, Alignment: 4, ExpectedOffset: 12) |
91 | .flexible(Size: 4, Alignment: 4, ExpectedOffset: 20) |
92 | .verify(ExpectedSize: 24, ExpectedAlignment: 4); |
93 | } |
94 | |
95 | TEST(OptimizedStructLayoutTest, Greed) { |
96 | // The greedy algorithm doesn't find the optimal layout here, which |
97 | // would be to put the 5-byte field at the end. |
98 | LayoutTest() |
99 | .fixed(Size: 4, Alignment: 4, Offset: 8) |
100 | .flexible(Size: 5, Alignment: 4, ExpectedOffset: 0) |
101 | .flexible(Size: 4, Alignment: 4, ExpectedOffset: 12) |
102 | .flexible(Size: 4, Alignment: 4, ExpectedOffset: 16) |
103 | .flexible(Size: 4, Alignment: 4, ExpectedOffset: 20) |
104 | .verify(ExpectedSize: 24, ExpectedAlignment: 4); |
105 | } |
106 | |
107 | TEST(OptimizedStructLayoutTest, Jagged) { |
108 | LayoutTest() |
109 | .flexible(Size: 1, Alignment: 2, ExpectedOffset: 18) |
110 | .flexible(Size: 13, Alignment: 8, ExpectedOffset: 0) |
111 | .flexible(Size: 3, Alignment: 2, ExpectedOffset: 14) |
112 | .verify(ExpectedSize: 19, ExpectedAlignment: 8); |
113 | } |
114 | |
115 | TEST(OptimizedStructLayoutTest, GardenPath) { |
116 | // The 4-byte-aligned field is our highest priority, but the less-aligned |
117 | // fields keep leaving the end offset mis-aligned. |
118 | LayoutTest() |
119 | .fixed(Size: 7, Alignment: 4, Offset: 0) |
120 | .flexible(Size: 4, Alignment: 4, ExpectedOffset: 44) |
121 | .flexible(Size: 6, Alignment: 1, ExpectedOffset: 7) |
122 | .flexible(Size: 5, Alignment: 1, ExpectedOffset: 13) |
123 | .flexible(Size: 7, Alignment: 2, ExpectedOffset: 18) |
124 | .flexible(Size: 4, Alignment: 1, ExpectedOffset: 25) |
125 | .flexible(Size: 4, Alignment: 1, ExpectedOffset: 29) |
126 | .flexible(Size: 1, Alignment: 1, ExpectedOffset: 33) |
127 | .flexible(Size: 4, Alignment: 2, ExpectedOffset: 34) |
128 | .flexible(Size: 4, Alignment: 2, ExpectedOffset: 38) |
129 | .flexible(Size: 2, Alignment: 2, ExpectedOffset: 42) |
130 | .flexible(Size: 2, Alignment: 2, ExpectedOffset: 48) |
131 | .verify(ExpectedSize: 50, ExpectedAlignment: 4); |
132 | } |
133 | |
134 | // PR 51131 |
135 | TEST(OptimizedStructLayoutTest, HighAlignment) { |
136 | // Handle the case where a flexible field has such a high alignment |
137 | // requirement that aligning LastEnd to it gives an offset past the |
138 | // end of the gap before the next fixed-alignment field. |
139 | LayoutTest() |
140 | .fixed(Size: 8, Alignment: 8, Offset: 0) |
141 | .fixed(Size: 8, Alignment: 8, Offset: 8) |
142 | .fixed(Size: 64, Alignment: 64, Offset: 64) |
143 | .flexible(Size: 1, Alignment: 1, ExpectedOffset: 16) |
144 | .flexible(Size: 1, Alignment: 1, ExpectedOffset: 17) |
145 | .flexible(Size: 4, Alignment: 128, ExpectedOffset: 128) |
146 | .flexible(Size: 1, Alignment: 1, ExpectedOffset: 18) |
147 | .flexible(Size: 1, Alignment: 1, ExpectedOffset: 19) |
148 | .verify(ExpectedSize: 132, ExpectedAlignment: 128); |
149 | } |
150 | |