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 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/block_graph/basic_block.h"
22 : #include "syzygy/block_graph/basic_block_subgraph.h"
23 : #include "syzygy/block_graph/block_graph.h"
24 :
25 : namespace block_graph {
26 :
27 : namespace {
28 :
29 : typedef BlockGraph::Block Block;
30 : typedef BlockGraph::Label Label;
31 : typedef BlockGraph::Reference Reference;
32 : typedef Block::Referrer Referrer;
33 :
34 : static const uint8 kEmptyData[32] = {0};
35 :
36 E : Instruction* AddInstruction(BasicBlock* bb, Instruction::Size size) {
37 E : CHECK(bb != NULL);
38 : bb->instructions().push_back(
39 E : Instruction(Instruction::Representation(), -1, size, kEmptyData));
40 E : return &bb->instructions().back();
41 E : }
42 :
43 : } // namespace
44 :
45 : // This test constructs the following subgraph then merges it into block graph.
46 : //
47 : // +-------+
48 : // | Data |
49 : // +---+---+
50 : // |
51 : // +--> +---------+
52 : // bb1 0 | 5 bytes | Ref: 4-byte ref to data block @ 1, Label1 (code+call)
53 : // +---------+
54 : // | 6 bytes | Successor: 4-byte ref to bb1 @ 7
55 : // +---------+
56 : // | 5 bytes | Successor: 4-byte ref to bb3 @ 11
57 : // +---------+
58 : // bb2 16 | 2 bytes | Label2 (code)
59 : // +---------+
60 : // | 3 bytes |
61 : // +---------+
62 : // bb3 21 | 2 bytes | Label3 (code).
63 : // +---------+
64 : // | 1 bytes |
65 : // +---------+ Successor: elided here. Label4
66 : // bb4 24 | 7 bytes |
67 : // +---------+
68 : // | 9 bytes |
69 : // +---------+
70 : // | 5 bytes | Successor: 4-byte ref to bb2 @ 11
71 : // data 45 +---------+ Label5 (data).
72 : // | 4 bytes | Ref: 4-byte ref to bb1 @ 45
73 : // +---------+
74 : // | 4 bytes | Ref: 4-byte ref to bb2 @ 49
75 : // +---------+
76 : // | 4 bytes | Ref: 4-byte ref to bb3 @ 53
77 : // 57 +---------+
78 : //
79 E : TEST(BlockBuilderTest, Merge) {
80 E : BlockGraph bg;
81 :
82 : // Setup a code block which is referenced from a data block.
83 : BlockGraph::Block* original =
84 E : bg.AddBlock(BlockGraph::CODE_BLOCK, 32, "original");
85 E : ASSERT_TRUE(original != NULL);
86 E : BlockGraph::BlockId original_id = original->id();
87 : BlockGraph::Block* other =
88 E : bg.AddBlock(BlockGraph::DATA_BLOCK, 4, "other");
89 E : ASSERT_TRUE(other != NULL);
90 E : BlockGraph::BlockId other_id = other->id();
91 : ASSERT_TRUE(other->SetReference(
92 E : 0, BlockGraph::Reference(BlockGraph::ABSOLUTE_REF, 4, original, 0, 0)));
93 :
94 : // Verify some expectations.
95 E : ASSERT_EQ(2, bg.blocks().size());
96 E : ASSERT_EQ(1, original->referrers().size());
97 :
98 : // Generate a mock decomposition of the original block.
99 E : BasicBlockSubGraph subgraph;
100 E : subgraph.set_original_block(original);
101 : BasicBlock* bb1 = subgraph.AddBasicBlock(
102 E : "bb1", BasicBlock::BASIC_CODE_BLOCK, -1, 0, NULL);
103 E : ASSERT_TRUE(bb1 != NULL);
104 : BasicBlock* bb2 = subgraph.AddBasicBlock(
105 E : "bb2", BasicBlock::BASIC_CODE_BLOCK, -1, 0, NULL);
106 E : ASSERT_TRUE(bb2 != NULL);
107 : BasicBlock* bb3 = subgraph.AddBasicBlock(
108 E : "bb3", BasicBlock::BASIC_CODE_BLOCK, -1, 0, NULL);
109 E : ASSERT_TRUE(bb3 != NULL);
110 : BasicBlock* bb4 = subgraph.AddBasicBlock(
111 E : "bb4", BasicBlock::BASIC_CODE_BLOCK, -1, 0, NULL);
112 E : ASSERT_TRUE(bb4 != NULL);
113 : BasicBlock* table = subgraph.AddBasicBlock(
114 E : "table", BasicBlock::BASIC_DATA_BLOCK, -1, 12, kEmptyData);
115 E : ASSERT_TRUE(table != NULL);
116 :
117 : // Flesh out bb1 with an instruction having a reference and 2 successors.
118 E : Instruction* inst = AddInstruction(bb1, 5);
119 E : Label label_1("1", BlockGraph::CODE_LABEL | BlockGraph::CALL_SITE_LABEL);
120 E : inst->set_label(label_1);
121 E : ASSERT_TRUE(inst != NULL);
122 : ASSERT_TRUE(inst->references().insert(
123 : std::make_pair(1, BasicBlockReference(BlockGraph::ABSOLUTE_REF, 4,
124 E : other, 0, 0))).second);
125 : bb1->successors().push_back(
126 : Successor(Successor::kConditionEqual,
127 : BasicBlockReference(BlockGraph::RELATIVE_REF, 4, bb1),
128 E : -1, 0));
129 : bb1->successors().push_back(
130 : Successor(Successor::kConditionNotEqual,
131 : BasicBlockReference(BlockGraph::RELATIVE_REF, 4, bb3),
132 E : -1, 0));
133 E : ASSERT_TRUE(bb1->referrers().insert(BasicBlockReferrer(other, 0)).second);
134 :
135 : // Flesh out bb2 with some instructions and no successor.
136 E : inst = AddInstruction(bb2, 2);
137 E : Label label_2("2", BlockGraph::CODE_LABEL);
138 E : inst->set_label(label_2);
139 E : ASSERT_TRUE(inst != NULL);
140 E : ASSERT_TRUE(AddInstruction(bb2, 3) != NULL);
141 :
142 : // Flesh out bb3 with some instructions and a single successor.
143 E : inst = AddInstruction(bb3, 2);
144 E : Label label_3("3", BlockGraph::CODE_LABEL);
145 E : inst->set_label(label_3);
146 E : ASSERT_TRUE(inst != NULL);
147 E : ASSERT_TRUE(AddInstruction(bb3, 1) != NULL);
148 : bb3->successors().push_back(
149 : Successor(Successor::kConditionTrue,
150 : BasicBlockReference(BlockGraph::RELATIVE_REF, 4, bb4),
151 E : -1, 0));
152 E : Label label_4("4", BlockGraph::CODE_LABEL);
153 E : bb3->successors().back().set_label(label_4);
154 :
155 : // Flesh out bb4 with some instructions and a single successor.
156 E : ASSERT_TRUE(AddInstruction(bb4, 7) != NULL);
157 E : ASSERT_TRUE(AddInstruction(bb4, 9) != NULL);
158 : bb4->successors().push_back(
159 : Successor(Successor::kConditionTrue,
160 : BasicBlockReference(BlockGraph::RELATIVE_REF, 4, bb2),
161 E : -1, 0));
162 :
163 : // Flesh out table with references.
164 E : Label label_5("5", BlockGraph::DATA_LABEL | BlockGraph::JUMP_TABLE_LABEL);
165 E : table->set_label(label_5);
166 : ASSERT_TRUE(table->references().insert(std::make_pair(
167 E : 0, BasicBlockReference(BlockGraph::ABSOLUTE_REF, 4, bb1))).second);
168 : ASSERT_TRUE(table->references().insert(std::make_pair(
169 E : 4, BasicBlockReference(BlockGraph::ABSOLUTE_REF, 4, bb2))).second);
170 : ASSERT_TRUE(table->references().insert(std::make_pair(
171 E : 8, BasicBlockReference(BlockGraph::ABSOLUTE_REF, 4, bb3))).second);
172 :
173 : BasicBlockSubGraph::BlockDescription* d1 = subgraph.AddBlockDescription(
174 E : "new_block", BlockGraph::CODE_BLOCK, 0, 1, 0);
175 E : d1->basic_block_order.push_back(bb1);
176 E : d1->basic_block_order.push_back(bb2);
177 E : d1->basic_block_order.push_back(bb3);
178 E : d1->basic_block_order.push_back(bb4);
179 E : d1->basic_block_order.push_back(table);
180 :
181 E : BlockBuilder builder(&bg);
182 E : ASSERT_TRUE(builder.Merge(&subgraph));
183 E : EXPECT_EQ(NULL, bg.GetBlockById(original_id));
184 E : EXPECT_EQ(other, bg.GetBlockById(other_id));
185 E : EXPECT_EQ(2, bg.blocks().size());
186 E : ASSERT_EQ(1, builder.new_blocks().size());
187 E : BlockGraph::Block* new_block = builder.new_blocks().front();
188 E : EXPECT_EQ(new_block, bg.GetBlockById(new_block->id()));
189 E : EXPECT_EQ(57U, new_block->size());
190 E : EXPECT_EQ(new_block->data_size(), new_block->size());
191 :
192 : // Validate the new block's references.
193 E : Block::ReferenceMap expected_references;
194 : expected_references[1] = Reference(
195 E : BlockGraph::ABSOLUTE_REF, 4, other, 0, 0);
196 : expected_references[7] = Reference(
197 E : BlockGraph::RELATIVE_REF, 4, new_block, 0, 0);
198 : expected_references[12] = Reference(
199 E : BlockGraph::RELATIVE_REF, 4, new_block, 21, 21);
200 : expected_references[41] = Reference(
201 E : BlockGraph::RELATIVE_REF, 4, new_block, 16, 16);
202 : expected_references[45] = Reference(
203 E : BlockGraph::ABSOLUTE_REF, 4, new_block, 0, 0);
204 : expected_references[49] = Reference(
205 E : BlockGraph::ABSOLUTE_REF, 4, new_block, 16, 16);
206 : expected_references[53] = Reference(
207 E : BlockGraph::ABSOLUTE_REF, 4, new_block, 21, 21);
208 E : EXPECT_EQ(expected_references, new_block->references());
209 :
210 : // Validate the new block's referrers.
211 E : Block::ReferrerSet expected_referrers;
212 E : expected_referrers.insert(Referrer(other, 0));
213 E : expected_referrers.insert(Referrer(new_block, 7));
214 E : expected_referrers.insert(Referrer(new_block, 12));
215 E : expected_referrers.insert(Referrer(new_block, 41));
216 E : expected_referrers.insert(Referrer(new_block, 45));
217 E : expected_referrers.insert(Referrer(new_block, 49));
218 E : expected_referrers.insert(Referrer(new_block, 53));
219 E : EXPECT_EQ(expected_referrers, new_block->referrers());
220 :
221 : // Validate the references of the other block.
222 E : Block::ReferenceMap expected_other_references;
223 : expected_other_references[0] = Reference(
224 E : BlockGraph::ABSOLUTE_REF, 4, new_block, 0, 0);
225 E : EXPECT_EQ(expected_other_references, other->references());
226 :
227 : // Validate the referrers of the other block.
228 E : Block::ReferrerSet expected_other_referrers;
229 E : expected_other_referrers.insert(Referrer(new_block, 1));
230 E : EXPECT_EQ(expected_other_referrers, other->referrers());
231 :
232 : // Validate the labels.
233 E : BlockGraph::Block::LabelMap expected_labels;
234 E : expected_labels.insert(std::make_pair(0, label_1));
235 E : expected_labels.insert(std::make_pair(16, label_2));
236 E : expected_labels.insert(std::make_pair(21, label_3));
237 E : expected_labels.insert(std::make_pair(24, label_4));
238 E : expected_labels.insert(std::make_pair(45, label_5));
239 E : EXPECT_EQ(expected_labels, new_block->labels());
240 E : }
241 :
242 : } // namespace block_graph
|