1 : // Copyright 2012 Google Inc. All Rights Reserved.
2 : //
3 : // Licensed under the Apache License, Version 2.0 (the "License");
4 : // you may not use this file except in compliance with the License.
5 : // You may obtain a copy of the License at
6 : //
7 : // http://www.apache.org/licenses/LICENSE-2.0
8 : //
9 : // Unless required by applicable law or agreed to in writing, software
10 : // distributed under the License is distributed on an "AS IS" BASIS,
11 : // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 : // See the License for the specific language governing permissions and
13 : // limitations under the License.
14 :
15 : #include "syzygy/reorder/transforms/basic_block_layout_transform.h"
16 :
17 : #include "gmock/gmock.h"
18 : #include "gtest/gtest.h"
19 : #include "syzygy/block_graph/basic_block_test_util.h"
20 :
21 : namespace reorder {
22 : namespace transforms {
23 :
24 : namespace {
25 :
26 : typedef BasicBlockSubGraphLayoutTransform::BasicBlockMap BasicBlockMap;
27 :
28 : using testing::BasicBlockTest;
29 : using testing::ContainerEq;
30 :
31 : class BasicBlockSubGraphLayoutTransformTest : public BasicBlockTest {
32 : public:
33 E : virtual void SetUp() OVERRIDE {
34 E : BasicBlockTest::SetUp();
35 E : ASSERT_NO_FATAL_FAILURE(InitBlockGraph());
36 E : ASSERT_NO_FATAL_FAILURE(InitBasicBlockSubGraph());
37 E : }
38 :
39 E : bool Insert(size_t offset, size_t block_index, size_t bb_index) {
40 : return bb_map_.insert(std::make_pair(
41 : offset,
42 E : std::make_pair(block_index, bb_index))).second;
43 E : }
44 :
45 E : void LayoutIsAsExpected() {
46 E : BasicBlockMap bb_map;
47 :
48 E : size_t bd_idx = 0;
49 : BasicBlockSubGraph::BlockDescriptionList::const_iterator bd_it =
50 E : subgraph_.block_descriptions().begin();
51 E : for (; bd_it != subgraph_.block_descriptions().end(); ++bd_it, ++bd_idx) {
52 E : size_t bb_idx = 0;
53 : BasicBlockSubGraph::BasicBlockOrdering::const_iterator bb_it =
54 E : bd_it->basic_block_order.begin();
55 E : for (; bb_it != bd_it->basic_block_order.end(); ++bb_it, ++bb_idx) {
56 E : size_t bb_offset = (*bb_it)->offset();
57 E : ASSERT_TRUE(bb_map.insert(std::make_pair(
58 : bb_offset, std::make_pair(bd_idx, bb_idx))).second);
59 E : }
60 E : }
61 E : EXPECT_THAT(bb_map, ContainerEq(bb_map_));
62 E : }
63 :
64 : BasicBlockMap bb_map_;
65 : };
66 :
67 : } // namespace
68 :
69 E : TEST_F(BasicBlockSubGraphLayoutTransformTest, NonContiguousBlockIndicesFails) {
70 : // This is a valid map, but we use block indices of 0 and 2 rather than 0 and
71 : // 1.
72 E : ASSERT_TRUE(Insert(0, 0, 0));
73 E : ASSERT_TRUE(Insert(23, 0, 1));
74 E : ASSERT_TRUE(Insert(24, 0, 2));
75 E : ASSERT_TRUE(Insert(31, 0, 3));
76 E : ASSERT_TRUE(Insert(36, 0, 4));
77 E : ASSERT_TRUE(Insert(37, 2, 0));
78 E : ASSERT_TRUE(Insert(42, 2, 1));
79 E : ASSERT_TRUE(Insert(49, 2, 2));
80 E : ASSERT_TRUE(Insert(52, 2, 3));
81 E : ASSERT_TRUE(Insert(64, 2, 4));
82 E : BasicBlockSubGraphLayoutTransform tx(bb_map_);
83 E : EXPECT_FALSE(tx.TransformBasicBlockSubGraph(&block_graph_, &subgraph_));
84 E : }
85 :
86 : TEST_F(BasicBlockSubGraphLayoutTransformTest,
87 E : NonContiguousBasicBlockPositionsFails) {
88 : // This is a valid map, but we use non-contiguous basic block positions.
89 E : ASSERT_TRUE(Insert(0, 0, 0));
90 E : ASSERT_TRUE(Insert(23, 0, 1));
91 E : ASSERT_TRUE(Insert(24, 0, 2));
92 E : ASSERT_TRUE(Insert(31, 0, 3));
93 E : ASSERT_TRUE(Insert(36, 0, 4));
94 E : ASSERT_TRUE(Insert(37, 0, 5));
95 E : ASSERT_TRUE(Insert(42, 0, 6));
96 E : ASSERT_TRUE(Insert(49, 0, 7));
97 E : ASSERT_TRUE(Insert(52, 0, 8));
98 E : ASSERT_TRUE(Insert(64, 0, 10));
99 E : BasicBlockSubGraphLayoutTransform tx(bb_map_);
100 E : EXPECT_FALSE(tx.TransformBasicBlockSubGraph(&block_graph_, &subgraph_));
101 E : }
102 :
103 E : TEST_F(BasicBlockSubGraphLayoutTransformTest, Identity) {
104 E : ASSERT_TRUE(Insert(0, 0, 0));
105 E : ASSERT_TRUE(Insert(23, 0, 1));
106 E : ASSERT_TRUE(Insert(24, 0, 2));
107 E : ASSERT_TRUE(Insert(31, 0, 3));
108 E : ASSERT_TRUE(Insert(36, 0, 4));
109 E : ASSERT_TRUE(Insert(37, 0, 5));
110 E : ASSERT_TRUE(Insert(42, 0, 6));
111 E : ASSERT_TRUE(Insert(49, 0, 7));
112 E : ASSERT_TRUE(Insert(52, 0, 8));
113 E : ASSERT_TRUE(Insert(64, 0, 9));
114 :
115 E : BasicBlockSubGraphLayoutTransform tx(bb_map_);
116 E : EXPECT_TRUE(tx.TransformBasicBlockSubGraph(&block_graph_, &subgraph_));
117 E : LayoutIsAsExpected();
118 E : }
119 :
120 E : TEST_F(BasicBlockSubGraphLayoutTransformTest, CodeAndDataSplit) {
121 : // Code blocks.
122 E : ASSERT_TRUE(Insert(0, 0, 0));
123 E : ASSERT_TRUE(Insert(24, 0, 1));
124 E : ASSERT_TRUE(Insert(31, 0, 2));
125 E : ASSERT_TRUE(Insert(36, 0, 3));
126 E : ASSERT_TRUE(Insert(37, 0, 4));
127 E : ASSERT_TRUE(Insert(42, 0, 5));
128 E : ASSERT_TRUE(Insert(49, 0, 6));
129 :
130 : // Data blocks.
131 E : ASSERT_TRUE(Insert(52, 1, 0));
132 E : ASSERT_TRUE(Insert(64, 1, 1));
133 :
134 : // We explicitly do not specify the BB at offset 23, which consists of
135 : // padding that can be deleted.
136 :
137 E : BasicBlockSubGraphLayoutTransform tx(bb_map_);
138 E : EXPECT_TRUE(tx.TransformBasicBlockSubGraph(&block_graph_, &subgraph_));
139 E : LayoutIsAsExpected();
140 E : }
141 :
142 : namespace {
143 :
144 : class BasicBlockLayoutTransformTest : public BasicBlockTest {
145 : public:
146 : typedef BasicBlockLayoutTransform::Order Order;
147 :
148 E : virtual void SetUp() OVERRIDE {
149 E : BasicBlockTest::SetUp();
150 : header_block_ = block_graph_.AddBlock(BlockGraph::DATA_BLOCK,
151 E : 10, "Dummy Header Block");
152 E : ASSERT_TRUE(header_block_ != NULL);
153 E : ASSERT_NO_FATAL_FAILURE(InitBlockGraph());
154 E : }
155 :
156 : BlockGraph::Block* header_block_;
157 : };
158 :
159 : } // namespace
160 :
161 E : TEST_F(BasicBlockLayoutTransformTest, NewSectionNoBlocksFails) {
162 E : Order order;
163 E : order.sections.resize(1);
164 E : order.sections[0].id = Order::SectionSpec::kNewSectionId;
165 E : order.sections[0].name = ".text.new";
166 E : order.sections[0].characteristics = text_section_->characteristics();
167 E : order.sections[0].blocks.resize(0);
168 :
169 E : BasicBlockLayoutTransform tx(&order);
170 E : EXPECT_FALSE(tx.TransformBlockGraph(&block_graph_, header_block_));
171 E : }
172 :
173 E : TEST_F(BasicBlockLayoutTransformTest, InvalidExistingSectionFails) {
174 E : Order order;
175 E : order.sections.resize(1);
176 E : order.sections[0].id = 47;
177 E : order.sections[0].name = "foobar";
178 : // Leave characteristics initialized to the default value.
179 E : order.sections[0].blocks.resize(1);
180 E : order.sections[0].blocks[0].block = assembly_func_;
181 :
182 E : BasicBlockLayoutTransform tx(&order);
183 E : EXPECT_FALSE(tx.TransformBlockGraph(&block_graph_, header_block_));
184 E : }
185 :
186 E : TEST_F(BasicBlockLayoutTransformTest, ReorderSection) {
187 E : Order order;
188 E : order.sections.resize(1);
189 :
190 E : order.sections[0].id = text_section_->id();
191 E : order.sections[0].name = text_section_->name();
192 E : order.sections[0].blocks.resize(3);
193 E : order.sections[0].blocks[0].block = func2_;
194 E : order.sections[0].blocks[1].block = assembly_func_;
195 E : order.sections[0].blocks[2].block = func1_;
196 :
197 E : BasicBlockLayoutTransform tx(&order);
198 E : EXPECT_TRUE(tx.TransformBlockGraph(&block_graph_, header_block_));
199 :
200 : // No new blocks or sections were created.
201 E : EXPECT_EQ(5u, block_graph_.blocks().size());
202 E : EXPECT_EQ(2u, block_graph_.sections().size());
203 E : }
204 :
205 E : TEST_F(BasicBlockLayoutTransformTest, CreateNewSection) {
206 E : Order order;
207 E : order.sections.resize(2);
208 :
209 E : order.sections[0].id = text_section_->id();
210 E : order.sections[0].name = ".text.hot";
211 E : order.sections[0].characteristics = text_section_->characteristics();
212 E : order.sections[0].blocks.resize(1);
213 E : order.sections[0].blocks[0].block = assembly_func_;
214 :
215 E : order.sections[1].id = Order::SectionSpec::kNewSectionId;
216 E : order.sections[1].name = ".text.cold";
217 E : order.sections[1].characteristics = text_section_->characteristics();
218 E : order.sections[1].blocks.resize(2);
219 E : order.sections[1].blocks[0].block = func1_;
220 E : order.sections[1].blocks[1].block = func2_;
221 :
222 : // Remember these for validation post-transform.
223 E : DWORD text_section_characteristics = text_section_->characteristics();
224 :
225 E : BasicBlockLayoutTransform tx(&order);
226 E : EXPECT_TRUE(tx.TransformBlockGraph(&block_graph_, header_block_));
227 :
228 : // No new blocks were created, but one new section was.
229 E : EXPECT_EQ(5u, block_graph_.blocks().size());
230 E : EXPECT_EQ(3u, block_graph_.sections().size());
231 :
232 : // The .text section has been renamed but the characteristics are the same.
233 E : EXPECT_EQ(order.sections[0].name, text_section_->name());
234 E : EXPECT_EQ(text_section_characteristics, text_section_->characteristics());
235 E : EXPECT_EQ(text_section_->id(), assembly_func_->section());
236 :
237 : // The new section is as expected.
238 : BlockGraph::Section* new_section =
239 E : &(block_graph_.sections_mutable().rbegin()->second);
240 E : EXPECT_EQ(order.sections[1].id, new_section->id());
241 E : EXPECT_EQ(order.sections[1].name, new_section->name());
242 E : EXPECT_EQ(order.sections[1].characteristics, new_section->characteristics());
243 E : EXPECT_EQ(new_section->id(), func1_->section());
244 E : EXPECT_EQ(new_section->id(), func2_->section());
245 E : }
246 :
247 E : TEST_F(BasicBlockLayoutTransformTest, SplitBlock) {
248 E : Order order;
249 E : order.sections.resize(2);
250 :
251 E : Order::OffsetVector assembly_func_code_bbs;
252 E : assembly_func_code_bbs.push_back(0);
253 E : assembly_func_code_bbs.push_back(24);
254 E : assembly_func_code_bbs.push_back(31);
255 E : assembly_func_code_bbs.push_back(36);
256 E : assembly_func_code_bbs.push_back(37);
257 E : assembly_func_code_bbs.push_back(42);
258 E : assembly_func_code_bbs.push_back(49);
259 :
260 E : Order::OffsetVector assembly_func_data_bbs;
261 E : assembly_func_data_bbs.push_back(52);
262 E : assembly_func_data_bbs.push_back(64);
263 :
264 E : order.sections[0].id = text_section_->id();
265 E : order.sections[0].name = text_section_->name();
266 E : order.sections[0].characteristics = text_section_->characteristics();
267 E : order.sections[0].blocks.resize(3);
268 E : order.sections[0].blocks[0].block = func1_;
269 E : order.sections[0].blocks[1].block = func2_;
270 E : order.sections[0].blocks[2].block = assembly_func_;
271 E : order.sections[0].blocks[2].basic_block_offsets = assembly_func_code_bbs;
272 :
273 E : order.sections[1].id = data_section_->id();
274 E : order.sections[1].name = data_section_->name();
275 E : order.sections[1].characteristics = data_section_->characteristics();
276 E : order.sections[1].blocks.resize(2);
277 E : order.sections[1].blocks[0].block = data_;
278 E : order.sections[1].blocks[1].block = assembly_func_;
279 E : order.sections[1].blocks[1].basic_block_offsets = assembly_func_data_bbs;
280 :
281 E : BlockGraph::BlockId old_assembly_func_id = assembly_func_->id();
282 :
283 E : BasicBlockLayoutTransform tx(&order);
284 E : EXPECT_TRUE(tx.TransformBlockGraph(&block_graph_, header_block_));
285 :
286 : // One new block has been created and no new sections.
287 E : EXPECT_EQ(6u, block_graph_.blocks().size());
288 E : EXPECT_EQ(2u, block_graph_.sections().size());
289 :
290 : // The assembly func block no longer exists.
291 E : EXPECT_TRUE(block_graph_.GetBlockById(old_assembly_func_id) == NULL);
292 :
293 : // Get the 2 new blocks that replaced the assembly func.
294 : BlockGraph::BlockMap::reverse_iterator block_it =
295 E : block_graph_.blocks_mutable().rbegin();
296 E : BlockGraph::Block* new_block2 = &((block_it++)->second);
297 E : BlockGraph::Block* new_block1 = &(block_it->second);
298 :
299 : // We expect these blocks to be in the appropriate sections, and the order to
300 : // have been updated.
301 E : EXPECT_EQ(text_section_->id(), new_block1->section());
302 E : EXPECT_EQ(data_section_->id(), new_block2->section());
303 E : EXPECT_EQ(order.sections[0].blocks[2].block, new_block1);
304 E : EXPECT_EQ(order.sections[1].blocks[1].block, new_block2);
305 E : }
306 :
307 : } // namespace transforms
308 : } // namespace reorder
|