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 : // Tests for the basic block classes.
16 :
17 : #include "syzygy/block_graph/block_builder.h"
18 :
19 : #include "gmock/gmock.h"
20 : #include "gtest/gtest.h"
21 : #include "syzygy/assm/unittest_util.h"
22 : #include "syzygy/block_graph/basic_block.h"
23 : #include "syzygy/block_graph/basic_block_subgraph.h"
24 : #include "syzygy/block_graph/basic_block_test_util.h"
25 : #include "syzygy/block_graph/block_graph.h"
26 :
27 : namespace block_graph {
28 :
29 : namespace {
30 :
31 : typedef BlockGraph::Block Block;
32 : typedef BlockGraph::Label Label;
33 : typedef BlockGraph::Reference Reference;
34 : typedef Block::Referrer Referrer;
35 :
36 : const uint8 kEmptyData[32] = { 0 };
37 :
38 : // Instructions we'll need in order to build the test subgraph.
39 : const uint8 kCall[5] = { 0xE8, 0x00, 0x00, 0x00, 0x00 };
40 :
41 : // The BlockInfo describes the minimal information needed to represent a single
42 : // basic block within a fake flow-graph. An array of BlockInfos represents the
43 : // full flow-graph. Fields |succ1| and |succ2| are indexes within the array.
44 : struct BlockInfo {
45 : uint8 size;
46 : uint8 succ1;
47 : uint8 succ2;
48 : };
49 :
50 : const uint8 kNoSucc = UINT8_MAX;
51 :
52 : // The following flow-graph was produced by fuzzing. It produced a corner case
53 : // when computing basic block layout.
54 : const BlockInfo kFixPointBasicBlockLayoutCode[] = {
55 : {18, 5, 6}, {26, 2, 7}, {10, 13, 14}, {10, 4, 35}, {17, 36, 37},
56 : {12, 1, kNoSucc}, {8, 1, kNoSucc}, {5, 2, 8}, {28, 9, 11}, {2, 10, 12},
57 : {10, 2, kNoSucc}, {3, 9, kNoSucc}, {3, 10, kNoSucc}, {3, 3, kNoSucc},
58 : {21, 15, kNoSucc}, {9, 16, 25}, {9, 17, 26}, {9, 18, 27}, {11, 28, 29},
59 : {3, 20, 30}, {24, 21, 31}, {11, 22, 32}, {11, 33, 34}, {12, 15, 24},
60 : {3, 3, kNoSucc}, {7, 16, kNoSucc}, {7, 17, kNoSucc}, {7, 18, kNoSucc},
61 : {7, 19, kNoSucc}, {13, 19, kNoSucc}, {7, 20, kNoSucc}, {7, 21, kNoSucc},
62 : {7, 22, kNoSucc}, {2, 23, kNoSucc}, {10, 23, kNoSucc}, {7, 4, kNoSucc},
63 : {13, kNoSucc, kNoSucc}, {21, kNoSucc, kNoSucc}
64 : };
65 :
66 : class BlockBuilderTest : public testing::BasicBlockTest {
67 : public:
68 : static Instruction* AddInstruction(BasicCodeBlock* bb,
69 : const uint8* buf,
70 E : size_t len) {
71 E : CHECK(bb != NULL);
72 E : Instruction tmp;
73 E : EXPECT_TRUE(Instruction::FromBuffer(buf, len, &tmp));
74 E : EXPECT_EQ(len, tmp.size());
75 :
76 E : bb->instructions().push_back(tmp);
77 E : return &bb->instructions().back();
78 E : }
79 :
80 : BasicCodeBlock* CreateCodeBB(const base::StringPiece& name,
81 E : size_t len) {
82 E : Instruction nop;
83 E : EXPECT_EQ(1U, nop.size());
84 E : BasicCodeBlock* bb = subgraph_.AddBasicCodeBlock(name);
85 E : EXPECT_TRUE(bb != NULL);
86 E : for (size_t i = 0; i < len; ++i)
87 E : bb->instructions().push_back(nop);
88 E : return bb;
89 E : }
90 :
91 : Block* CreateLayout(size_t size1,
92 : size_t size2,
93 : size_t size3,
94 : size_t size4,
95 E : bool multi_end_block) {
96 : // Generate a set of puzzle blocks.
97 E : BasicCodeBlock* bb1 = CreateCodeBB("bb1", size1);
98 E : BasicCodeBlock* bb2 = CreateCodeBB("bb2", size2);
99 E : BasicCodeBlock* bb3 = CreateCodeBB("bb3", size3);
100 E : BasicCodeBlock* bb4 = CreateCodeBB("bb4", size4);
101 E : BasicEndBlock* bb5 = subgraph_.AddBasicEndBlock();
102 E : BasicEndBlock* bb6 = NULL;
103 E : if (multi_end_block)
104 E : bb6 = subgraph_.AddBasicEndBlock();
105 :
106 : // BB1 has BB4 and BB2 as successors.
107 : bb1->successors().push_back(
108 : Successor(Successor::kConditionEqual,
109 : BasicBlockReference(BlockGraph::RELATIVE_REF, 4, bb4),
110 E : 0));
111 : bb1->successors().push_back(
112 : Successor(Successor::kConditionNotEqual,
113 : BasicBlockReference(BlockGraph::RELATIVE_REF, 4, bb2),
114 E : 0));
115 :
116 : // BB2 has BB1 as successor.
117 : bb2->successors().push_back(
118 : Successor(Successor::kConditionTrue,
119 : BasicBlockReference(BlockGraph::RELATIVE_REF, 4, bb1),
120 E : 0));
121 :
122 : // BB3 has BB4 as successor.
123 : bb3->successors().push_back(
124 : Successor(Successor::kConditionTrue,
125 : BasicBlockReference(BlockGraph::RELATIVE_REF, 4, bb4),
126 E : 0));
127 :
128 : // BB5 and BB6 both carry labels.
129 E : bb5->set_label(BlockGraph::Label("bb5", BlockGraph::CODE_LABEL));
130 E : if (multi_end_block)
131 E : bb6->set_label(BlockGraph::Label("bb6", BlockGraph::DEBUG_END_LABEL));
132 :
133 : BasicBlockSubGraph::BlockDescription* d1 = subgraph_.AddBlockDescription(
134 E : "new_block", "new_compiland", BlockGraph::CODE_BLOCK, 0, 1, 0);
135 E : d1->basic_block_order.push_back(bb1);
136 E : d1->basic_block_order.push_back(bb2);
137 E : d1->basic_block_order.push_back(bb3);
138 E : d1->basic_block_order.push_back(bb4);
139 E : d1->basic_block_order.push_back(bb5);
140 E : if (multi_end_block)
141 E : d1->basic_block_order.push_back(bb6);
142 :
143 E : BlockBuilder builder(&block_graph_);
144 E : EXPECT_TRUE(builder.Merge(&subgraph_));
145 E : EXPECT_EQ(1, builder.new_blocks().size());
146 :
147 E : Block* new_block = builder.new_blocks()[0];
148 E : EXPECT_TRUE(new_block != NULL);
149 :
150 : // We expect there to be a label beyond the end of the block.
151 E : BlockGraph::Label expected_label;
152 E : if (multi_end_block) {
153 : expected_label = BlockGraph::Label(
154 E : "bb5, bb6", BlockGraph::CODE_LABEL | BlockGraph::DEBUG_END_LABEL);
155 E : } else {
156 E : expected_label = BlockGraph::Label("bb5", BlockGraph::CODE_LABEL);
157 : }
158 E : BlockGraph::Label label;
159 E : EXPECT_TRUE(new_block->GetLabel(new_block->size(), &label));
160 E : EXPECT_EQ(expected_label, label);
161 :
162 E : return new_block;
163 E : }
164 :
165 : // For a given array of BlockInfos, this function produces a fake subgraph and
166 : // uses the block builder to produce a block.
167 E : Block* CreateLayoutFromInfo(const BlockInfo* info, size_t info_length) {
168 E : std::vector<BasicCodeBlock*> basicblocks;
169 E : basicblocks.resize(info_length);
170 :
171 : // Create basic blocks.
172 E : for (size_t i = 0; i < info_length; ++i)
173 E : basicblocks[i] = CreateCodeBB("bb", info[i].size);
174 :
175 : // Add edges between blocks (successors).
176 E : for (size_t i = 0; i < info_length; ++i) {
177 E : size_t succ1 = info[i].succ1;
178 E : size_t succ2 = info[i].succ2;
179 :
180 E : if (succ1 == kNoSucc) {
181 : // No successor.
182 E : continue;
183 E : } else if (succ2 == kNoSucc) {
184 : // One successor.
185 : basicblocks[i]->successors().push_back(
186 : Successor(Successor::kConditionTrue,
187 : BasicBlockReference(BlockGraph::RELATIVE_REF,
188 : 4,
189 : basicblocks[succ1]),
190 E : 0));
191 E : } else {
192 : // Two successors.
193 : basicblocks[i]->successors().push_back(
194 : Successor(Successor::kConditionEqual,
195 : BasicBlockReference(BlockGraph::RELATIVE_REF,
196 : 4,
197 : basicblocks[succ1]),
198 E : 0));
199 : basicblocks[i]->successors().push_back(
200 : Successor(Successor::kConditionNotEqual,
201 : BasicBlockReference(BlockGraph::RELATIVE_REF,
202 : 4,
203 : basicblocks[succ2]),
204 E : 0));
205 : }
206 E : }
207 :
208 : // Create block description.
209 : BasicBlockSubGraph::BlockDescription* d1 = subgraph_.AddBlockDescription(
210 E : "new_block", "new_compiland", BlockGraph::CODE_BLOCK, 0, 1, 0);
211 E : for (size_t i = 0; i < info_length; ++i)
212 E : d1->basic_block_order.push_back(basicblocks[i]);
213 :
214 : // Build block.
215 E : BlockBuilder builder(&block_graph_);
216 E : EXPECT_TRUE(builder.Merge(&subgraph_));
217 E : EXPECT_EQ(1, builder.new_blocks().size());
218 :
219 E : Block* new_block = builder.new_blocks()[0];
220 E : EXPECT_TRUE(new_block != NULL);
221 E : return new_block;
222 E : }
223 :
224 : };
225 :
226 : } // namespace
227 :
228 : // A comparison operator for TagInfo objects. Needed for use with ContainerEq.
229 E : bool operator==(const TagInfo& ti1, const TagInfo& ti2) {
230 : return ti1.type == ti2.type && ti1.block == ti2.block &&
231 E : ti1.offset == ti2.offset && ti1.size == ti2.size;
232 E : }
233 :
234 : // This test constructs the following subgraph then merges it into block graph.
235 : // It adds tags to each element and also ensures that the tagging mechanism
236 : // works as expected.
237 : //
238 : // +-------+
239 : // | Data |
240 : // +---+---+
241 : // |
242 : // +--> +---------+
243 : // bb1 0 | 5 bytes | Ref: 4-byte ref to code block @ 1, Label1 (code+call).
244 : // +---------+
245 : // | 2 bytes | Successor: 1-byte ref to bb1 @ 6.
246 : // +---------+
247 : // | 2 bytes | Successor: 1-byte ref to bb3 @ 8.
248 : // +---------+
249 : // bb2 9 | 2 bytes | Label2 (code).
250 : // +---------+
251 : // | 3 bytes |
252 : // +---------+
253 : // bb3 14 | 2 bytes | Label3 (code).
254 : // +---------+
255 : // | 1 byte |
256 : // +---------+ Successor: elided here. Label4.
257 : // bb4 17 | 7 bytes |
258 : // +---------+
259 : // | 9 bytes |
260 : // +---------+
261 : // | 2 bytes | Successor: 1-byte ref to bb2 @ 34.
262 : // +---------+
263 : // | 1 byte | Injected NOP due to data alignment.
264 : // data 36 +---------+ Label5 (data).
265 : // | 4 bytes | Ref: 4-byte ref to bb1 @ 36.
266 : // +---------+
267 : // | 4 bytes | Ref: 4-byte ref to bb2 @ 40.
268 : // +---------+
269 : // | 4 bytes | Ref: 4-byte ref to bb3 @ 44.
270 : // 48 +---------+
271 : //
272 E : TEST_F(BlockBuilderTest, Merge) {
273 : // Setup a code block which is referenced from a data block and references
274 : // another code block.
275 : BlockGraph::Block* original =
276 E : block_graph_.AddBlock(BlockGraph::CODE_BLOCK, 32, "original");
277 E : ASSERT_TRUE(original != NULL);
278 E : BlockGraph::BlockId original_id = original->id();
279 : BlockGraph::Block* other =
280 E : block_graph_.AddBlock(BlockGraph::DATA_BLOCK, 4, "other");
281 E : ASSERT_TRUE(other != NULL);
282 E : BlockGraph::BlockId other_id = other->id();
283 : ASSERT_TRUE(other->SetReference(
284 E : 0, BlockGraph::Reference(BlockGraph::ABSOLUTE_REF, 4, original, 0, 0)));
285 :
286 : // Verify some expectations.
287 E : ASSERT_EQ(2, block_graph_.blocks().size());
288 E : ASSERT_EQ(1, original->referrers().size());
289 :
290 : // Generate a mock decomposition of the original block.
291 E : subgraph_.set_original_block(original);
292 E : BasicCodeBlock* bb1 = subgraph_.AddBasicCodeBlock("bb1");
293 E : ASSERT_TRUE(bb1 != NULL);
294 E : bb1->tags().insert(bb1);
295 E : BasicCodeBlock* bb2 = subgraph_.AddBasicCodeBlock("bb2");
296 E : ASSERT_TRUE(bb2 != NULL);
297 E : bb2->tags().insert(bb2);
298 E : BasicCodeBlock* bb3 = subgraph_.AddBasicCodeBlock("bb3");
299 E : ASSERT_TRUE(bb3 != NULL);
300 E : bb3->tags().insert(bb3);
301 E : BasicCodeBlock* bb4 = subgraph_.AddBasicCodeBlock("bb4");
302 E : ASSERT_TRUE(bb4 != NULL);
303 E : bb4->tags().insert(bb4);
304 E : BasicDataBlock* table = subgraph_.AddBasicDataBlock("table", 12, kEmptyData);
305 E : ASSERT_TRUE(table != NULL);
306 E : table->tags().insert(table);
307 :
308 : // Flesh out bb1 with an instruction having a reference and 2 successors.
309 E : Instruction* inst = AddInstruction(bb1, kCall, sizeof(kCall));
310 E : Label label_1("1", BlockGraph::CODE_LABEL | BlockGraph::CALL_SITE_LABEL);
311 E : inst->set_label(label_1);
312 E : ASSERT_TRUE(inst != NULL);
313 E : BasicBlockReference bb1_abs_ref(BlockGraph::ABSOLUTE_REF, 4, other, 0, 0);
314 E : bb1_abs_ref.tags().insert(&bb1_abs_ref);
315 E : ASSERT_TRUE(inst->references().insert(std::make_pair(1, bb1_abs_ref)).second);
316 E : Instruction* bb1_inst1 = inst;
317 E : bb1_inst1->tags().insert(bb1_inst1);
318 E : BasicBlockReference bb1_succ1_ref(BlockGraph::RELATIVE_REF, 4, bb1);
319 E : bb1_succ1_ref.tags().insert(&bb1_succ1_ref);
320 E : Successor bb1_succ1(Successor::kConditionEqual, bb1_succ1_ref, 0);
321 E : bb1_succ1.tags().insert(&bb1_succ1);
322 E : bb1->successors().push_back(bb1_succ1);
323 : bb1->successors().push_back(
324 : Successor(Successor::kConditionNotEqual,
325 : BasicBlockReference(BlockGraph::RELATIVE_REF, 4, bb3),
326 E : 0));
327 E : ASSERT_TRUE(bb1->referrers().insert(BasicBlockReferrer(other, 0)).second);
328 :
329 : // Flesh out bb2 with some instructions and no successor.
330 E : inst = AddInstruction(bb2, testing::kNop2, sizeof(testing::kNop2));
331 E : Label label_2("2", BlockGraph::CODE_LABEL);
332 E : inst->set_label(label_2);
333 E : ASSERT_TRUE(inst != NULL);
334 : ASSERT_TRUE(
335 E : AddInstruction(bb2, testing::kNop3, sizeof(testing::kNop3)) != NULL);
336 :
337 : // Flesh out bb3 with some instructions and a single successor.
338 : // We set tags on the successor and its reference. Since these are elided
339 : // we expect zero-sized entries in the tag info map.
340 E : inst = AddInstruction(bb3, testing::kNop2, sizeof(testing::kNop2));
341 E : Label label_3("3", BlockGraph::CODE_LABEL);
342 E : inst->set_label(label_3);
343 E : ASSERT_TRUE(inst != NULL);
344 : ASSERT_TRUE(
345 E : AddInstruction(bb3, testing::kNop1, sizeof(testing::kNop1)) != NULL);
346 E : BasicBlockReference bb3_succ_ref(BlockGraph::RELATIVE_REF, 4, bb4);
347 E : bb3_succ_ref.tags().insert(&bb3_succ_ref);
348 E : Successor bb3_succ(Successor::kConditionTrue, bb3_succ_ref, 0);
349 E : bb3_succ.tags().insert(&bb3_succ);
350 E : bb3->successors().push_back(bb3_succ);
351 E : Label label_4("4", BlockGraph::CODE_LABEL);
352 E : bb3->successors().back().set_label(label_4);
353 :
354 : // Flesh out bb4 with some instructions and a single successor.
355 : ASSERT_TRUE(
356 E : AddInstruction(bb4, testing::kNop7, sizeof(testing::kNop7)) != NULL);
357 : ASSERT_TRUE(
358 E : AddInstruction(bb4, testing::kNop9, sizeof(testing::kNop9)) != NULL);
359 : bb4->successors().push_back(
360 : Successor(Successor::kConditionTrue,
361 : BasicBlockReference(BlockGraph::RELATIVE_REF, 4, bb2),
362 E : 0));
363 :
364 : // Flesh out table with references. Make the table aligned so that we test
365 : // our NOP insertion code.
366 E : Label label_5("5", BlockGraph::DATA_LABEL | BlockGraph::JUMP_TABLE_LABEL);
367 E : table->set_label(label_5);
368 E : table->set_alignment(4);
369 : ASSERT_TRUE(table->references().insert(std::make_pair(
370 E : 0, BasicBlockReference(BlockGraph::ABSOLUTE_REF, 4, bb1))).second);
371 : ASSERT_TRUE(table->references().insert(std::make_pair(
372 E : 4, BasicBlockReference(BlockGraph::ABSOLUTE_REF, 4, bb2))).second);
373 E : BasicBlockReference table_ref3(BlockGraph::ABSOLUTE_REF, 4, bb3);
374 E : table_ref3.tags().insert(&table_ref3);
375 E : ASSERT_TRUE(table->references().insert(std::make_pair(8, table_ref3)).second);
376 :
377 : BasicBlockSubGraph::BlockDescription* d1 = subgraph_.AddBlockDescription(
378 E : "new_block", "new block compiland", BlockGraph::CODE_BLOCK, 0, 1, 0);
379 E : d1->basic_block_order.push_back(bb1);
380 E : d1->basic_block_order.push_back(bb2);
381 E : d1->basic_block_order.push_back(bb3);
382 E : d1->basic_block_order.push_back(bb4);
383 E : d1->basic_block_order.push_back(table);
384 :
385 E : BlockBuilder builder(&block_graph_);
386 E : ASSERT_TRUE(builder.Merge(&subgraph_));
387 E : EXPECT_EQ(NULL, block_graph_.GetBlockById(original_id));
388 E : EXPECT_EQ(other, block_graph_.GetBlockById(other_id));
389 E : EXPECT_EQ(2, block_graph_.blocks().size());
390 E : ASSERT_EQ(1, builder.new_blocks().size());
391 E : BlockGraph::Block* new_block = builder.new_blocks().front();
392 E : EXPECT_EQ(new_block, block_graph_.GetBlockById(new_block->id()));
393 E : EXPECT_EQ(48U, new_block->size());
394 E : EXPECT_EQ(new_block->data_size(), new_block->size());
395 E : EXPECT_EQ(table->alignment(), new_block->alignment());
396 :
397 : // Validate the tags.
398 E : TagInfoMap expected_tags;
399 E : expected_tags[bb1].push_back(TagInfo(kBasicCodeBlockTag, new_block, 0, 9));
400 E : expected_tags[bb2].push_back(TagInfo(kBasicCodeBlockTag, new_block, 9, 5));
401 E : expected_tags[bb3].push_back(TagInfo(kBasicCodeBlockTag, new_block, 14, 3));
402 E : expected_tags[bb4].push_back(TagInfo(kBasicCodeBlockTag, new_block, 17, 18));
403 : expected_tags[table].push_back(
404 E : TagInfo(kBasicDataBlockTag, new_block, 36, 12));
405 E : expected_tags[bb1_inst1].push_back(TagInfo(kInstructionTag, new_block, 0, 5));
406 : expected_tags[&bb1_abs_ref].push_back(
407 E : TagInfo(kReferenceTag, new_block, 1, 4));
408 : expected_tags[&bb1_succ1_ref].push_back(
409 E : TagInfo(kReferenceTag, new_block, 6, 1));
410 E : expected_tags[&bb1_succ1].push_back(TagInfo(kSuccessorTag, new_block, 5, 2));
411 : expected_tags[&bb3_succ_ref].push_back(
412 E : TagInfo(kReferenceTag, new_block, 17, 0));
413 E : expected_tags[&bb3_succ].push_back(TagInfo(kSuccessorTag, new_block, 17, 0));
414 : expected_tags[&table_ref3].push_back(
415 E : TagInfo(kReferenceTag, new_block, 44, 4));
416 E : EXPECT_THAT(builder.tag_info_map(), ::testing::ContainerEq(expected_tags));
417 :
418 : // Validate the new block's references.
419 E : Block::ReferenceMap expected_references;
420 : expected_references[1] = Reference(
421 E : BlockGraph::ABSOLUTE_REF, 4, other, 0, 0);
422 : expected_references[6] = Reference(
423 E : BlockGraph::PC_RELATIVE_REF, 1, new_block, 0, 0);
424 : expected_references[8] = Reference(
425 E : BlockGraph::PC_RELATIVE_REF, 1, new_block, 14, 14);
426 : expected_references[34] = Reference(
427 E : BlockGraph::PC_RELATIVE_REF, 1, new_block, 9, 9);
428 : expected_references[36] = Reference(
429 E : BlockGraph::ABSOLUTE_REF, 4, new_block, 0, 0);
430 : expected_references[40] = Reference(
431 E : BlockGraph::ABSOLUTE_REF, 4, new_block, 9, 9);
432 : expected_references[44] = Reference(
433 E : BlockGraph::ABSOLUTE_REF, 4, new_block, 14, 14);
434 E : EXPECT_EQ(expected_references, new_block->references());
435 :
436 : // Validate the new block's referrers.
437 E : Block::ReferrerSet expected_referrers;
438 E : expected_referrers.insert(Referrer(other, 0));
439 E : expected_referrers.insert(Referrer(new_block, 6));
440 E : expected_referrers.insert(Referrer(new_block, 8));
441 E : expected_referrers.insert(Referrer(new_block, 34));
442 E : expected_referrers.insert(Referrer(new_block, 36));
443 E : expected_referrers.insert(Referrer(new_block, 40));
444 E : expected_referrers.insert(Referrer(new_block, 44));
445 E : EXPECT_EQ(expected_referrers, new_block->referrers());
446 :
447 : // Validate the references of the other block.
448 E : Block::ReferenceMap expected_other_references;
449 : expected_other_references[0] = Reference(
450 E : BlockGraph::ABSOLUTE_REF, 4, new_block, 0, 0);
451 E : EXPECT_EQ(expected_other_references, other->references());
452 :
453 : // Validate the referrers of the other block.
454 E : Block::ReferrerSet expected_other_referrers;
455 E : expected_other_referrers.insert(Referrer(new_block, 1));
456 E : EXPECT_EQ(expected_other_referrers, other->referrers());
457 :
458 : // Validate the labels.
459 E : BlockGraph::Block::LabelMap expected_labels;
460 E : expected_labels.insert(std::make_pair(0, label_1));
461 E : expected_labels.insert(std::make_pair(9, label_2));
462 E : expected_labels.insert(std::make_pair(14, label_3));
463 E : expected_labels.insert(std::make_pair(17, label_4));
464 E : expected_labels.insert(std::make_pair(36, label_5));
465 E : EXPECT_EQ(expected_labels, new_block->labels());
466 :
467 : // Validate that there is a single byte NOP at position 35, just prior to the
468 : // table.
469 E : EXPECT_EQ(0x90, new_block->data()[35]);
470 E : }
471 :
472 E : TEST_F(BlockBuilderTest, FailsForInvalidEndBlockPlacement) {
473 E : BasicCodeBlock* bb1 = CreateCodeBB("bb1", 10);
474 E : BasicEndBlock* bb2 = subgraph_.AddBasicEndBlock();
475 :
476 E : bb2->set_label(BlockGraph::Label("bb2", BlockGraph::CODE_LABEL));
477 :
478 : // Place the end block in an invalid location in the basic block order.
479 : BasicBlockSubGraph::BlockDescription* d1 = subgraph_.AddBlockDescription(
480 E : "new_block", "new_compiland", BlockGraph::CODE_BLOCK, 0, 1, 0);
481 E : d1->basic_block_order.push_back(bb2);
482 E : d1->basic_block_order.push_back(bb1);
483 :
484 E : BlockBuilder builder(&block_graph_);
485 E : EXPECT_FALSE(builder.Merge(&subgraph_));
486 E : }
487 :
488 E : TEST_F(BlockBuilderTest, ShortLayout) {
489 : // This is the block structure we construct. If either of BB1 or BB2's
490 : // successors is manifested too long, they will both have to grow.
491 : // 0 [BB1] 62 bytes
492 : // 62 jeq BB4 (+127 bytes).
493 : // 64 [BB2] 62 bytes
494 : // 126 jmp BB1 (-128 bytes).
495 : // 128 [BB3] 63 bytes.
496 : // 191 [BB4] 1 byte.
497 E : Block* new_block = CreateLayout(62, 62, 63, 1, true);
498 E : ASSERT_TRUE(new_block != NULL);
499 :
500 E : EXPECT_EQ(192, new_block->size());
501 E : Block::ReferenceMap expected_refs;
502 : expected_refs.insert(
503 : std::make_pair(63,
504 : Reference(BlockGraph::PC_RELATIVE_REF,
505 E : 1, new_block, 191, 191)));
506 : expected_refs.insert(
507 : std::make_pair(127,
508 : Reference(BlockGraph::PC_RELATIVE_REF,
509 E : 1, new_block, 0, 0)));
510 E : EXPECT_EQ(expected_refs, new_block->references());
511 E : }
512 :
513 E : TEST_F(BlockBuilderTest, ComplexFixPointBasicBlockLayout) {
514 : // This test validates a corner case of the basic block layout algorithm. The
515 : // fake flow-graph |kFixPointBasicBlockLayoutCode| produces a case where the
516 : // estimated size of a successor was temporarily shrinking and causing a
517 : // DCHECK to fail.
518 E : size_t info_length = arraysize(kFixPointBasicBlockLayoutCode);
519 : Block* new_block = CreateLayoutFromInfo(kFixPointBasicBlockLayoutCode,
520 E : info_length);
521 E : ASSERT_TRUE(new_block != NULL);
522 :
523 E : EXPECT_EQ(575, new_block->size());
524 E : }
525 :
526 E : TEST_F(BlockBuilderTest, OutofReachBranchLayout) {
527 : // 54 + 72 + 2 = 128 - the BB1->BB4 branch is just out of reach.
528 E : Block* new_block = CreateLayout(62, 54, 72, 1, false);
529 E : ASSERT_TRUE(new_block != NULL);
530 :
531 : size_t expected_size = 62 +
532 : assm::kLongBranchSize +
533 : 54 +
534 : assm::kShortJumpSize +
535 : 72 +
536 E : 1;
537 E : EXPECT_EQ(expected_size, new_block->size());
538 E : Block::ReferenceMap expected_refs;
539 : expected_refs.insert(
540 : std::make_pair(62 + assm::kLongBranchOpcodeSize,
541 : Reference(BlockGraph::PC_RELATIVE_REF,
542 : 4,
543 : new_block,
544 : expected_size - 1,
545 E : expected_size - 1)));
546 : size_t succ_location = 62 +
547 : assm::kLongBranchSize +
548 : 54 +
549 E : assm::kShortJumpOpcodeSize;
550 : expected_refs.insert(
551 : std::make_pair(succ_location,
552 : Reference(BlockGraph::PC_RELATIVE_REF,
553 E : 1, new_block, 0, 0)));
554 E : EXPECT_EQ(expected_refs, new_block->references());
555 E : }
556 :
557 E : TEST_F(BlockBuilderTest, OutofReachJmpLayout) {
558 : // 0 - (62 + 2 + 63 + 2) = -129, the jump from BB2->BB1 is just out of reach.
559 E : Block* new_block = CreateLayout(62, 63, 55, 1, false);
560 E : ASSERT_TRUE(new_block != NULL);
561 :
562 : size_t expected_size = 62 +
563 : assm::kShortBranchSize+
564 : 63 +
565 : assm::kLongJumpSize+
566 : 55 +
567 E : 1;
568 E : EXPECT_EQ(expected_size, new_block->size());
569 E : Block::ReferenceMap expected_refs;
570 : expected_refs.insert(
571 : std::make_pair(62 + assm::kShortBranchOpcodeSize,
572 : Reference(BlockGraph::PC_RELATIVE_REF,
573 : 1,
574 : new_block,
575 : expected_size - 1,
576 E : expected_size - 1)));
577 : size_t succ_location = 62 +
578 : assm::kShortBranchSize +
579 : 63 +
580 E : assm::kLongJumpOpcodeSize;
581 : expected_refs.insert(
582 : std::make_pair(succ_location,
583 : Reference(BlockGraph::PC_RELATIVE_REF,
584 E : 4, new_block, 0, 0)));
585 E : EXPECT_EQ(expected_refs, new_block->references());
586 E : }
587 :
588 E : TEST_F(BlockBuilderTest, MergeAssemblesSourceRangesCorrectly) {
589 E : ASSERT_NO_FATAL_FAILURE(InitBlockGraph());
590 E : ASSERT_NO_FATAL_FAILURE(InitBasicBlockSubGraph());
591 :
592 : // Test that re-assembling this decomposition produces an unbroken,
593 : // identical source range as the original block had.
594 : BlockGraph::Block::SourceRanges expected_source_ranges(
595 E : assembly_func_->source_ranges());
596 :
597 E : BlockBuilder builder(&block_graph_);
598 E : ASSERT_TRUE(builder.Merge(&subgraph_));
599 :
600 E : ASSERT_EQ(1, builder.new_blocks().size());
601 :
602 E : BlockGraph::Block* new_block = builder.new_blocks()[0];
603 E : ASSERT_EQ(expected_source_ranges, new_block->source_ranges());
604 E : }
605 :
606 E : TEST_F(BlockBuilderTest, LabelsPastEndAreNotDropped) {
607 E : ASSERT_NO_FATAL_FAILURE(InitBasicBlockSubGraphWithLabelPastEnd());
608 :
609 E : BlockBuilder builder(&block_graph_);
610 E : ASSERT_TRUE(builder.Merge(&subgraph_));
611 :
612 E : ASSERT_EQ(1u, builder.new_blocks().size());
613 :
614 E : BlockGraph::Block* new_block = builder.new_blocks()[0];
615 E : ASSERT_EQ(2u, new_block->labels().size());
616 :
617 : BlockGraph::Block::LabelMap::const_iterator label_it =
618 E : new_block->labels().begin();
619 :
620 E : ASSERT_EQ(0, label_it->first);
621 : ASSERT_EQ(BlockGraph::CODE_LABEL | BlockGraph::DEBUG_START_LABEL,
622 E : label_it->second.attributes());
623 :
624 E : ++label_it;
625 : ASSERT_EQ(static_cast<BlockGraph::Offset>(new_block->size()),
626 E : label_it->first);
627 : ASSERT_EQ(BlockGraph::DEBUG_END_LABEL,
628 E : label_it->second.attributes());
629 E : }
630 :
631 : } // namespace block_graph
|