1 : // Copyright 2012 Google Inc.
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 : // Tests for BasicBlockSubGraph.
16 :
17 : #include "syzygy/block_graph/basic_block_subgraph.h"
18 :
19 : #include "gmock/gmock.h"
20 : #include "gtest/gtest.h"
21 : #include "syzygy/block_graph/basic_block.h"
22 : #include "syzygy/block_graph/block_graph.h"
23 : #include "syzygy/core/assembler.h"
24 :
25 : namespace block_graph {
26 :
27 : namespace {
28 :
29 : using block_graph::BasicBlock;
30 : using block_graph::BasicBlockReference;
31 : using block_graph::BasicBlockReferrer;
32 : using block_graph::BlockGraph;
33 : using block_graph::Instruction;
34 : using block_graph::Successor;
35 :
36 : typedef BasicBlockSubGraph::BlockDescription BlockDescription;
37 : typedef BlockGraph::Reference Reference;
38 :
39 : // Some handy constants.
40 : const size_t kDataSize = 32;
41 : const uint8 kData[kDataSize] = {0};
42 :
43 : // A derived class to expose protected members for unit-testing.
44 : class TestBasicBlockSubGraph : public BasicBlockSubGraph {
45 : public:
46 : using BasicBlockSubGraph::HasValidReferrers;
47 : using BasicBlockSubGraph::HasValidSuccessors;
48 : using BasicBlockSubGraph::MapsBasicBlocksToAtMostOneDescription;
49 : };
50 :
51 : } // namespace
52 :
53 E : TEST(BasicBlockSubGraphTest, AddBasicBlock) {
54 E : BlockGraph::Block block;
55 E : BasicBlockSubGraph subgraph;
56 E : subgraph.set_original_block(&block);
57 :
58 : // Add a basic block.
59 : BasicBlock* bb1 = subgraph.AddBasicBlock(
60 E : "bb1", BasicBlock::BASIC_CODE_BLOCK, 0, kDataSize, kData);
61 E : ASSERT_FALSE(bb1 == NULL);
62 :
63 : // Cannot add one that overlaps.
64 : BasicBlock* bb2 = subgraph.AddBasicBlock(
65 E : "bb2", BasicBlock::BASIC_CODE_BLOCK, kDataSize / 2, kDataSize, kData);
66 E : ASSERT_TRUE(bb2 == NULL);
67 :
68 : // But can add one that doesn't overlap.
69 : BasicBlock* bb3 = subgraph.AddBasicBlock(
70 E : "bb3", BasicBlock::BASIC_CODE_BLOCK, kDataSize, kDataSize, kData);
71 E : ASSERT_FALSE(bb3 == NULL);
72 :
73 : // And they were not the same basic-block.
74 E : ASSERT_FALSE(bb1 == bb3);
75 E : }
76 :
77 E : TEST(BasicBlockSubGraphTest, AddBlockDescription) {
78 E : TestBasicBlockSubGraph subgraph;
79 : BlockDescription* b1 = subgraph.AddBlockDescription(
80 E : "b1", BlockGraph::CODE_BLOCK, 7, 2, 42);
81 E : ASSERT_FALSE(b1 == NULL);
82 E : EXPECT_EQ("b1", b1->name);
83 E : EXPECT_EQ(BlockGraph::CODE_BLOCK, b1->type);
84 E : EXPECT_EQ(7, b1->section);
85 E : EXPECT_EQ(2, b1->alignment);
86 E : EXPECT_EQ(42, b1->attributes);
87 E : EXPECT_TRUE(b1->basic_block_order.empty());
88 E : }
89 :
90 E : TEST(BasicBlockSubGraphTest, MapsBasicBlocksToAtMostOneDescription) {
91 E : TestBasicBlockSubGraph subgraph;
92 E : uint8 data[32] = {0};
93 :
94 : // Add three non-overlapping basic-blocks.
95 : BasicBlock* bb1 = subgraph.AddBasicBlock(
96 E : "bb1", BasicBlock::BASIC_CODE_BLOCK, -1, 0, NULL);
97 E : ASSERT_FALSE(bb1 == NULL);
98 : BasicBlock* bb2 = subgraph.AddBasicBlock(
99 E : "bb2", BasicBlock::BASIC_CODE_BLOCK, -1, 0, NULL);
100 E : ASSERT_FALSE(bb2 == NULL);
101 : BasicBlock* bb3 = subgraph.AddBasicBlock(
102 E : "bb3", BasicBlock::BASIC_CODE_BLOCK, -1, 0, NULL);
103 E : ASSERT_FALSE(bb3 == NULL);
104 :
105 : // They should all be different blocks.
106 E : ASSERT_FALSE(bb1 == bb2);
107 E : ASSERT_FALSE(bb2 == bb3);
108 E : ASSERT_FALSE(bb1 == bb3);
109 :
110 : // Add a block description for a mythical b1.
111 : BlockDescription* b1 = subgraph.AddBlockDescription(
112 E : "b1", BlockGraph::CODE_BLOCK, 0, 1, 0);
113 E : ASSERT_FALSE(b1 == NULL);
114 :
115 : // Add a block description for a mythical b2.
116 : BlockDescription* b2 = subgraph.AddBlockDescription(
117 E : "b2", BlockGraph::CODE_BLOCK, 0, 1, 0);
118 E : ASSERT_FALSE(b2 == NULL);
119 :
120 : // There are no blocks assigned twice (bb1 and bb2 are in separate blocks).
121 E : ASSERT_TRUE(subgraph.MapsBasicBlocksToAtMostOneDescription());
122 :
123 : // Adding bb3 to b1 is still valid.
124 E : b1->basic_block_order.push_back(bb3);
125 E : ASSERT_TRUE(subgraph.MapsBasicBlocksToAtMostOneDescription());
126 :
127 : // But adding bb3 to b2, as well, is no longer valid.
128 E : b2->basic_block_order.push_back(bb3);
129 E : ASSERT_FALSE(subgraph.MapsBasicBlocksToAtMostOneDescription());
130 E : }
131 :
132 E : TEST(BasicBlockSubGraphTest, GetReachabilityMap) {
133 E : BlockGraph::Block external_block;
134 E : BasicBlockSubGraph subgraph;
135 : static const uint8 kData[Reference::kMaximumSize] = { 0 };
136 :
137 : // Create basic-blocks.
138 : BasicBlock* bb1 = subgraph.AddBasicBlock(
139 E : "bb1", BasicBlock::BASIC_CODE_BLOCK, -1, 0, NULL);
140 E : ASSERT_FALSE(bb1 == NULL);
141 : BasicBlock* bb2 = subgraph.AddBasicBlock(
142 E : "bb2", BasicBlock::BASIC_CODE_BLOCK, -1, 0, NULL);
143 E : ASSERT_FALSE(bb2 == NULL);
144 : BasicBlock* bb3 = subgraph.AddBasicBlock(
145 E : "bb3", BasicBlock::BASIC_CODE_BLOCK, -1, 0, NULL);
146 E : ASSERT_FALSE(bb3 == NULL);
147 : BasicBlock* bb4 = subgraph.AddBasicBlock(
148 E : "bb4", BasicBlock::BASIC_CODE_BLOCK, -1, 0, NULL);
149 E : ASSERT_FALSE(bb4 == NULL);
150 : BasicBlock* data = subgraph.AddBasicBlock(
151 E : "data", BasicBlock::BASIC_DATA_BLOCK, -1, sizeof(kData), kData);
152 E : ASSERT_FALSE(data == NULL);
153 :
154 : // Setup references.
155 : static const uint8 kJmp[] = { 0xFF, 0x24, 0x8D, 0xCA, 0xFE, 0xBA, 0xBE };
156 : static const uint8 kRet[] = { 0xC3 };
157 E : bb1->referrers().insert(BasicBlockReferrer(&external_block, 0));
158 E : bb1->instructions().push_back(Instruction(sizeof(kJmp), kJmp));
159 : bb1->instructions().back().SetReference(
160 : 3, BasicBlockReference(BlockGraph::RELATIVE_REF,
161 : BlockGraph::Reference::kMaximumSize,
162 E : data));
163 : data->SetReference(0, BasicBlockReference(BlockGraph::RELATIVE_REF,
164 : BlockGraph::Reference::kMaximumSize,
165 E : bb2));
166 : bb2->successors().push_back(
167 : Successor(Successor::kConditionTrue,
168 : BasicBlockReference(BlockGraph::RELATIVE_REF,
169 : BlockGraph::Reference::kMaximumSize,
170 : bb3),
171 E : BasicBlock::kNoOffset, 0));
172 E : bb3->instructions().push_back(Instruction(sizeof(kRet), kRet));
173 :
174 : // Check reachability.
175 E : BasicBlockSubGraph::ReachabilityMap expected_rm;
176 E : expected_rm.insert(std::make_pair(bb1, true));
177 E : expected_rm.insert(std::make_pair(bb2, true));
178 E : expected_rm.insert(std::make_pair(bb3, true));
179 E : expected_rm.insert(std::make_pair(bb4, false));
180 E : expected_rm.insert(std::make_pair(data, true));
181 :
182 E : BasicBlockSubGraph::ReachabilityMap actual_rm;
183 E : subgraph.GetReachabilityMap(&actual_rm);
184 E : EXPECT_THAT(actual_rm, testing::ContainerEq(expected_rm));
185 E : }
186 :
187 E : TEST(BasicBlockSubGraphTest, HasValidSuccessors) {
188 E : BlockGraph::Block external_block;
189 E : TestBasicBlockSubGraph subgraph;
190 :
191 : BasicBlock* bb1 = subgraph.AddBasicBlock(
192 E : "bb1", BasicBlock::BASIC_CODE_BLOCK, -1, 0, NULL);
193 E : ASSERT_FALSE(bb1 == NULL);
194 E : bb1->referrers().insert(BasicBlockReferrer(&external_block, 0));
195 :
196 : BasicBlock* bb2 = subgraph.AddBasicBlock(
197 E : "bb2", BasicBlock::BASIC_CODE_BLOCK, -1, 0, NULL);
198 E : ASSERT_FALSE(bb2 == NULL);
199 :
200 : // Add a block description for a mythical b1.
201 : BlockDescription* b1 = subgraph.AddBlockDescription(
202 E : "b1", BlockGraph::CODE_BLOCK, 0, 1, 0);
203 E : ASSERT_FALSE(b1 == NULL);
204 E : b1->basic_block_order.push_back(bb1);
205 :
206 : // Add a block description for a mythical b2.
207 : BlockDescription* b2 = subgraph.AddBlockDescription(
208 E : "b2", BlockGraph::CODE_BLOCK, 0, 1, 0);
209 E : ASSERT_FALSE(b2 == NULL);
210 E : b2->basic_block_order.push_back(bb2);
211 :
212 : // Successors are not valid yet.
213 E : EXPECT_FALSE(subgraph.HasValidSuccessors());
214 :
215 : // Add an unconditional succession from bb1 to bb2.
216 : bb1->successors().push_back(
217 : Successor(Successor::kConditionTrue,
218 : BasicBlockReference(BlockGraph::RELATIVE_REF, 4, bb2),
219 E : -1, 0));
220 :
221 : // Successors are still not valid.
222 E : EXPECT_FALSE(subgraph.HasValidSuccessors());
223 :
224 : // Add half of a conditional succession from bb2 to bb1.
225 : bb2->successors().push_back(
226 : Successor(Successor::kConditionAbove,
227 : BasicBlockReference(BlockGraph::RELATIVE_REF, 4, bb1),
228 E : -1, 0));
229 :
230 : // Successors are still not valid.
231 E : EXPECT_FALSE(subgraph.HasValidSuccessors());
232 :
233 : // Add second conditional succession from bb2 to bb1, but not the inverse
234 : // of the first condtition.
235 : bb2->successors().push_back(
236 : Successor(Successor::kConditionAboveOrEqual,
237 : BasicBlockReference(BlockGraph::RELATIVE_REF, 4, bb1),
238 E : -1, 0));
239 :
240 : // Successors are still not valid because the conditions are not inverses.
241 E : EXPECT_FALSE(subgraph.HasValidSuccessors());
242 :
243 : // Remove the bad successor and add a correct secondary successor.
244 E : bb2->successors().pop_back();
245 : bb2->successors().push_back(
246 : Successor(Successor::kConditionBelowOrEqual,
247 : BasicBlockReference(BlockGraph::RELATIVE_REF, 4, bb1),
248 E : -1, 0));
249 :
250 : // Successors are now valid.
251 E : EXPECT_TRUE(subgraph.HasValidSuccessors());
252 E : }
253 :
254 E : TEST(BasicBlockSubGraphTest, HasValidReferrers) {
255 E : BlockGraph::Block b1 = BlockGraph::Block(0, BlockGraph::DATA_BLOCK, 4, "b1");
256 E : BlockGraph::Block b2 = BlockGraph::Block(0, BlockGraph::DATA_BLOCK, 4, "b2");
257 :
258 E : Reference ref(BlockGraph::ABSOLUTE_REF, 4, &b1, 0, 0);
259 E : ASSERT_TRUE(b2.SetReference(0, ref));
260 E : ASSERT_FALSE(b1.referrers().empty());
261 :
262 E : TestBasicBlockSubGraph subgraph;
263 E : subgraph.set_original_block(&b1);
264 :
265 E : ASSERT_FALSE(subgraph.HasValidReferrers());
266 :
267 : BasicBlock* bb1 = subgraph.AddBasicBlock(
268 E : "bb1", BasicBlock::BASIC_DATA_BLOCK, -1, kDataSize, kData);
269 E : ASSERT_FALSE(bb1 == NULL);
270 :
271 : BlockDescription* b1_desc = subgraph.AddBlockDescription(
272 E : "b1_desc", BlockGraph::DATA_BLOCK, 0, 1, 0);
273 E : ASSERT_FALSE(b1_desc == NULL);
274 E : b1_desc->basic_block_order.push_back(bb1);
275 :
276 E : ASSERT_FALSE(subgraph.HasValidReferrers());
277 :
278 E : bb1->referrers().insert(BasicBlockReferrer(&b2, 0));
279 E : ASSERT_TRUE(subgraph.HasValidReferrers());
280 E : }
281 :
282 E : TEST(BasicBlockSubGraphTest, GetMaxSize) {
283 E : TestBasicBlockSubGraph subgraph;
284 :
285 : // Add three non-overlapping basic-blocks.
286 : BasicBlock* code = subgraph.AddBasicBlock(
287 E : "code", BasicBlock::BASIC_CODE_BLOCK, -1, 0, NULL);
288 E : ASSERT_FALSE(code == NULL);
289 : BasicBlock* data = subgraph.AddBasicBlock(
290 E : "data", BasicBlock::BASIC_DATA_BLOCK, -1, kDataSize / 2, kData);
291 E : ASSERT_FALSE(data == NULL);
292 : BasicBlock* padding = subgraph.AddBasicBlock(
293 E : "padding", BasicBlock::BASIC_PADDING_BLOCK, -1, kDataSize, kData);
294 E : ASSERT_FALSE(padding == NULL);
295 :
296 : Instruction::Representation dummy;
297 :
298 E : code->instructions().push_back(Instruction(dummy, -1, 5, kData));
299 E : code->instructions().push_back(Instruction(dummy, -1, 1, kData));
300 E : code->instructions().push_back(Instruction(dummy, -1, 3, kData));
301 E : code->successors().push_back(Successor());
302 E : code->successors().push_back(Successor());
303 :
304 E : subgraph.block_descriptions().push_back(BlockDescription());
305 E : BlockDescription& desc = subgraph.block_descriptions().back();
306 E : desc.basic_block_order.push_back(code);
307 E : desc.basic_block_order.push_back(data);
308 E : desc.basic_block_order.push_back(padding);
309 :
310 : size_t max_block_length = kDataSize + (kDataSize / 2 ) + (5 + 1 + 3) +
311 E : (2 * core::AssemblerImpl::kMaxInstructionLength);
312 :
313 E : DCHECK_EQ(max_block_length, desc.GetMaxSize());
314 E : }
315 :
316 : } // namespace block_graph
|