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
12using namespace llvm;
13
14namespace {
15
16class 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
27public:
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
67TEST(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
75TEST(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
84TEST(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
95TEST(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
107TEST(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
115TEST(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
135TEST(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

source code of llvm/unittests/Support/OptimizedStructLayoutTest.cpp