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/basic_block.h"
18 :
19 : #include "gmock/gmock.h"
20 : #include "gtest/gtest.h"
21 : #include "syzygy/block_graph/basic_block_assembler.h"
22 : #include "syzygy/block_graph/basic_block_subgraph.h"
23 :
24 : #include "distorm.h" // NOLINT
25 : #include "mnemonics.h" // NOLINT
26 :
27 : namespace block_graph {
28 :
29 : namespace {
30 :
31 : using core::AbsoluteAddress;
32 :
33 : class BasicBlockTest: public testing::Test {
34 : public:
35 : // Initializes this fixture.
36 : //
37 : // Note that each test invocation is its own unique instance of this
38 : // fixture, so each will have its own fresh instance of basic_code_block_
39 : // and macro_block_ to play with.
40 : BasicBlockTest()
41 : : basic_code_block_(NULL),
42 : basic_data_block_(NULL),
43 E : macro_block_(NULL) {
44 : macro_block_ = block_graph_.AddBlock(
45 E : kMacroBlockType, kBlockSize, kBlockName);
46 E : basic_code_block_ = subgraph_.AddBasicCodeBlock(kBlockName);
47 : basic_data_block_ =
48 E : subgraph_.AddBasicDataBlock(kBlockName, kBlockSize, kBlockData);
49 : basic_data_block_->set_label(BlockGraph::Label(
50 E : "data", BlockGraph::DATA_LABEL | BlockGraph::CASE_TABLE_LABEL));
51 : basic_end_block_ =
52 E : subgraph_.AddBasicEndBlock();
53 : basic_end_block_->set_label(BlockGraph::Label(
54 E : "end", BlockGraph::DEBUG_END_LABEL));
55 E : }
56 :
57 : // Convert @p opcode to a branch type.
58 : //
59 : // @returns FC_CND_BRANCH on conditional branch opcodes; FC_UNC_BRANCH on
60 : // unconditional branch opcodes; or FC_NONE if the opcode is not a
61 : // branch.
62 : static uint8 BranchToType(uint16 opcode) {
63 : switch (opcode) {
64 : // Unconditional branch instructions.
65 : case I_JMP:
66 : case I_JMP_FAR:
67 : return FC_UNC_BRANCH;
68 :
69 : // Conditional branch instructions.
70 : case I_JA: // Equivalent to JNBE
71 : case I_JAE: // Equivalent to JNB and JNC.
72 : case I_JB: // Equivalent to JNAE and JC.
73 : case I_JBE: // Equivalent to JNA.
74 : case I_JCXZ:
75 : case I_JECXZ:
76 : case I_JG: // Equivalent to JNLE.
77 : case I_JGE: // Equivalent to JNL.
78 : case I_JL: // Equivalent to JNGE.
79 : case I_JLE: // Equivalent to JNG.
80 : case I_JNO:
81 : case I_JNP: // Equivalent to JPO.
82 : case I_JNS:
83 : case I_JNZ: // Equivalent to JNE.
84 : case I_JO:
85 : case I_JP: // Equivalent to JPE.
86 : case I_JS:
87 : case I_JZ: // Equivalent to JE.
88 : case I_LOOP:
89 : case I_LOOPNZ:
90 : case I_LOOPZ:
91 : return FC_CND_BRANCH;
92 :
93 : // Everything else.
94 : default:
95 : ADD_FAILURE() << "Unexpected opcode: " << opcode << ".";
96 : return FC_NONE;
97 : }
98 : }
99 :
100 : // Helper function to create a RET instruction.
101 E : Instruction CreateRet() {
102 : static const uint8 data[] = { 0xC3 };
103 E : Instruction temp;
104 E : EXPECT_TRUE(Instruction::FromBuffer(data, sizeof(data), &temp));
105 E : EXPECT_TRUE(temp.IsReturn());
106 E : return temp;
107 E : }
108 :
109 : // Helper function to create a CALL instruction.
110 E : Instruction CreateCall(BasicBlockReference ref) {
111 : static const uint8 data[] = { 0xE8, 0x00, 0x00, 0x00, 0x00 };
112 E : Instruction call_inst;
113 E : EXPECT_TRUE(Instruction::FromBuffer(data, sizeof(data), &call_inst));
114 E : EXPECT_TRUE(call_inst.IsCall());
115 E : call_inst.SetReference(1, ref);
116 E : EXPECT_FALSE(call_inst.has_label());
117 E : call_inst.set_label(BlockGraph::Label("call", BlockGraph::CALL_SITE_LABEL));
118 E : EXPECT_TRUE(call_inst.has_label());
119 E : EXPECT_TRUE(call_inst.label().has_attributes(BlockGraph::CALL_SITE_LABEL));
120 E : return call_inst;
121 E : }
122 :
123 : // Helper function to create a successor branch.
124 E : Successor CreateBranch(uint16 opcode, Successor::Offset target) {
125 : BasicBlockReference ref(BlockGraph::PC_RELATIVE_REF,
126 : 1, // Size is immaterial in successors.
127 : macro_block_,
128 : target,
129 E : target);
130 E : return Successor(Successor::OpCodeToCondition(opcode), ref, 0);
131 E : }
132 :
133 : // Some handy constants we'll use throughout the tests.
134 : // @{
135 : static const BasicBlock::BasicBlockType kBasicBlockType;
136 : static const BlockGraph::BlockType kMacroBlockType;
137 : static const char kBlockName[];
138 : static const BasicBlock::Offset kBlockOffset;
139 : static const BasicBlock::Size kBlockSize;
140 : static const uint8 kBlockData[];
141 : static const size_t kRefSize;
142 : static const Successor::Offset kOffset1;
143 : static const Successor::Offset kOffset2;
144 : // @}
145 :
146 : protected:
147 : BlockGraph block_graph_;
148 : BasicBlockSubGraph subgraph_;
149 : BasicCodeBlock* basic_code_block_;
150 : BasicDataBlock* basic_data_block_;
151 : BasicEndBlock* basic_end_block_;
152 : BlockGraph::Block* macro_block_;
153 : };
154 :
155 : const BasicBlock::BasicBlockType BasicBlockTest::kBasicBlockType =
156 : BasicBlock::BASIC_CODE_BLOCK;
157 : const BlockGraph::BlockType BasicBlockTest::kMacroBlockType =
158 : BlockGraph::CODE_BLOCK;
159 : const char BasicBlockTest::kBlockName[] = "test block";
160 : const BasicBlock::Offset BasicBlockTest::kBlockOffset = 0;
161 : const BasicBlock::Size BasicBlockTest::kBlockSize = 32;
162 : const uint8 BasicBlockTest::kBlockData[BasicBlockTest::kBlockSize] = {};
163 : const size_t BasicBlockTest::kRefSize = BlockGraph::Reference::kMaximumSize;
164 : const Successor::Offset BasicBlockTest::kOffset1(kBlockSize / 3);
165 : const Successor::Offset BasicBlockTest::kOffset2(kBlockSize / 2);
166 :
167 : } // namespace
168 :
169 E : TEST_F(BasicBlockTest, InstructionConstructor) {
170 : // This also tests Instruction::FromBuffer via CreateRet and CreateCall.
171 E : Instruction nop;
172 E : EXPECT_TRUE(nop.IsNop());
173 E : EXPECT_EQ(1, nop.size());
174 E : EXPECT_EQ(0x90, nop.data()[0]);
175 :
176 E : Instruction ret_instr(CreateRet());
177 :
178 E : ASSERT_TRUE(ret_instr.IsReturn());
179 : {
180 : // This should copy the references.
181 : BasicBlockReference r1(
182 E : BlockGraph::RELATIVE_REF, kRefSize, basic_code_block_);
183 E : Instruction call_instr = CreateCall(r1);
184 E : ASSERT_EQ(1, call_instr.references().size());
185 E : Instruction call_temp(call_instr);
186 E : ASSERT_EQ(call_instr.references(), call_temp.references());
187 E : }
188 E : }
189 :
190 E : TEST_F(BasicBlockTest, Cast) {
191 : // Declare pointer variables to let us select between the const/non-const
192 : // versions of the Cast method.
193 E : BasicBlock* bb_ptr = NULL;
194 E : const BasicBlock* const_bb_ptr = NULL;
195 :
196 : // Should gracefully handle NULL.
197 E : EXPECT_EQ(NULL, BasicCodeBlock::Cast(bb_ptr));
198 E : EXPECT_EQ(NULL, BasicCodeBlock::Cast(const_bb_ptr));
199 E : EXPECT_EQ(NULL, BasicDataBlock::Cast(bb_ptr));
200 E : EXPECT_EQ(NULL, BasicDataBlock::Cast(const_bb_ptr));
201 E : EXPECT_EQ(NULL, BasicEndBlock::Cast(bb_ptr));
202 E : EXPECT_EQ(NULL, BasicEndBlock::Cast(const_bb_ptr));
203 :
204 : // Cast an underlying basic code block.
205 E : bb_ptr = basic_code_block_;
206 E : const_bb_ptr = basic_code_block_;
207 E : EXPECT_EQ(basic_code_block_, BasicCodeBlock::Cast(bb_ptr));
208 E : EXPECT_EQ(basic_code_block_, BasicCodeBlock::Cast(const_bb_ptr));
209 E : EXPECT_EQ(NULL, BasicDataBlock::Cast(bb_ptr));
210 E : EXPECT_EQ(NULL, BasicDataBlock::Cast(const_bb_ptr));
211 E : EXPECT_EQ(NULL, BasicEndBlock::Cast(bb_ptr));
212 E : EXPECT_EQ(NULL, BasicEndBlock::Cast(const_bb_ptr));
213 :
214 : // Should gracefully handle NULL.
215 E : bb_ptr = basic_data_block_;
216 E : const_bb_ptr = basic_data_block_;
217 E : EXPECT_EQ(NULL, BasicCodeBlock::Cast(bb_ptr));
218 E : EXPECT_EQ(NULL, BasicCodeBlock::Cast(const_bb_ptr));
219 E : EXPECT_EQ(basic_data_block_, BasicDataBlock::Cast(bb_ptr));
220 E : EXPECT_EQ(basic_data_block_, BasicDataBlock::Cast(const_bb_ptr));
221 E : EXPECT_EQ(NULL, BasicEndBlock::Cast(bb_ptr));
222 E : EXPECT_EQ(NULL, BasicEndBlock::Cast(const_bb_ptr));
223 :
224 E : bb_ptr = basic_end_block_;
225 E : const_bb_ptr = basic_end_block_;
226 E : EXPECT_EQ(NULL, BasicCodeBlock::Cast(bb_ptr));
227 E : EXPECT_EQ(NULL, BasicCodeBlock::Cast(bb_ptr));
228 E : EXPECT_EQ(NULL, BasicDataBlock::Cast(bb_ptr));
229 E : EXPECT_EQ(NULL, BasicDataBlock::Cast(const_bb_ptr));
230 E : EXPECT_EQ(basic_end_block_, BasicEndBlock::Cast(bb_ptr));
231 E : EXPECT_EQ(basic_end_block_, BasicEndBlock::Cast(const_bb_ptr));
232 E : }
233 :
234 E : TEST_F(BasicBlockTest, BasicCodeBlockAccessors) {
235 E : EXPECT_EQ(BasicBlock::BASIC_CODE_BLOCK, basic_code_block_->type());
236 E : EXPECT_STREQ(kBlockName, basic_code_block_->name().c_str());
237 E : EXPECT_TRUE(basic_code_block_->referrers().empty());
238 :
239 E : basic_code_block_->set_offset(kBlockSize);
240 E : EXPECT_EQ(kBlockSize, basic_code_block_->offset());
241 E : }
242 :
243 E : TEST_F(BasicBlockTest, BasicDataBlockAccessors) {
244 E : EXPECT_EQ(BasicBlock::BASIC_DATA_BLOCK, basic_data_block_->type());
245 E : EXPECT_STREQ(kBlockName, basic_data_block_->name().c_str());
246 E : EXPECT_EQ(&kBlockData[0], basic_data_block_->data());
247 E : EXPECT_EQ(kBlockSize, basic_data_block_->size());
248 : EXPECT_EQ(BasicDataBlock::SourceRange(),
249 E : basic_data_block_->source_range());
250 E : EXPECT_TRUE(basic_data_block_->references().empty());
251 E : EXPECT_TRUE(basic_data_block_->referrers().empty());
252 E : EXPECT_TRUE(basic_data_block_->has_label());
253 : EXPECT_TRUE(basic_data_block_->label().has_attributes(
254 E : BlockGraph::DATA_LABEL | BlockGraph::CASE_TABLE_LABEL));
255 :
256 : const BasicDataBlock::SourceRange
257 E : kTestRange(core::RelativeAddress(0xF00D), 13);
258 E : basic_data_block_->set_source_range(kTestRange);
259 E : EXPECT_EQ(kTestRange, basic_data_block_->source_range());
260 E : }
261 :
262 E : TEST_F(BasicBlockTest, BasicEndBlockAccessors) {
263 E : EXPECT_EQ(BasicBlock::BASIC_END_BLOCK, basic_end_block_->type());
264 E : EXPECT_EQ("<end>", basic_end_block_->name());
265 E : EXPECT_TRUE(basic_end_block_->references().empty());
266 E : EXPECT_TRUE(basic_end_block_->referrers().empty());
267 E : EXPECT_TRUE(basic_end_block_->has_label());
268 : EXPECT_TRUE(basic_end_block_->label().has_attributes(
269 E : BlockGraph::DEBUG_END_LABEL));
270 E : }
271 :
272 E : TEST_F(BasicBlockTest, GetInstructionSize) {
273 E : basic_code_block_->instructions().push_back(CreateRet());
274 E : basic_code_block_->instructions().push_back(CreateRet());
275 E : basic_code_block_->instructions().push_back(CreateRet());
276 E : basic_code_block_->instructions().push_back(CreateRet());
277 E : basic_code_block_->successors().push_back(CreateBranch(I_JZ, kOffset1));
278 :
279 E : ASSERT_EQ(4 * CreateRet().size(), basic_code_block_->GetInstructionSize());
280 E : }
281 :
282 E : TEST_F(BasicBlockTest, EmptyBasicBlockIsNotValid) {
283 : // Upon creation the code block has neither instructions nor successors,
284 : // which we consider to be an invalid state.
285 E : ASSERT_FALSE(basic_code_block_->IsValid());
286 E : }
287 :
288 E : TEST_F(BasicBlockTest, BasicBlockWithOnlyConditionalSuccessorIsNotValid) {
289 E : basic_code_block_->successors().push_back(CreateBranch(I_JNZ, kOffset1));
290 E : ASSERT_FALSE(basic_code_block_->IsValid());
291 E : }
292 :
293 : TEST_F(BasicBlockTest,
294 E : BasicBlockWithConditionalAndFallThroughSuccessorsIsValid) {
295 E : basic_code_block_->successors().push_back(CreateBranch(I_JNZ, kOffset1));
296 E : basic_code_block_->successors().push_back(CreateBranch(I_JZ, kOffset2));
297 E : ASSERT_TRUE(basic_code_block_->IsValid());
298 E : }
299 :
300 : TEST_F(BasicBlockTest,
301 E : BasicBlockWithFallThroughSuccessorIsValid) {
302 E : basic_code_block_->successors().push_back(CreateBranch(I_JMP, kOffset2));
303 E : ASSERT_TRUE(basic_code_block_->IsValid());
304 E : }
305 :
306 : TEST_F(BasicBlockTest,
307 E : BasicBlockWithTerminalInstructionNoSuccessorsIsValid) {
308 E : basic_code_block_->instructions().push_back(CreateRet());
309 E : ASSERT_TRUE(basic_code_block_->IsValid());
310 E : }
311 :
312 : namespace {
313 :
314 E : void TestReferenceCopy(const BasicBlockReference& input) {
315 E : BasicBlockReference copy(input);
316 :
317 E : EXPECT_EQ(input.referred_type(), copy.referred_type());
318 E : EXPECT_EQ(input.block(), copy.block());
319 E : EXPECT_EQ(input.basic_block(), copy.basic_block());
320 E : EXPECT_EQ(input.offset(), copy.offset());
321 E : EXPECT_EQ(input.size(), copy.size());
322 E : EXPECT_EQ(input.IsValid(), copy.IsValid());
323 E : EXPECT_EQ(input.tags(), copy.tags());
324 E : }
325 :
326 : } // namespace
327 :
328 E : TEST_F(BasicBlockTest, InvalidBasicBlockReference) {
329 : // Validate that a ref that points to nothing is not valid and doesn't claim
330 : // to point to anything.
331 E : BasicBlockReference ref;
332 E : TestReferenceCopy(ref);
333 :
334 E : EXPECT_EQ(BasicBlockReference::REFERRED_TYPE_UNKNOWN, ref.referred_type());
335 E : EXPECT_EQ(NULL, ref.block());
336 E : EXPECT_EQ(NULL, ref.basic_block());
337 E : EXPECT_EQ(-1, ref.offset());
338 E : EXPECT_EQ(0, ref.size());
339 E : EXPECT_FALSE(ref.IsValid());
340 E : }
341 :
342 E : TEST_F(BasicBlockTest, BasicBlockReference) {
343 : BasicBlockReference ref(BlockGraph::RELATIVE_REF,
344 : kRefSize,
345 E : basic_code_block_);
346 :
347 : EXPECT_EQ(BasicBlockReference::REFERRED_TYPE_BASIC_BLOCK,
348 E : ref.referred_type());
349 E : ref.tags().insert(&ref);
350 E : TestReferenceCopy(ref);
351 :
352 E : EXPECT_EQ(NULL, ref.block());
353 E : EXPECT_EQ(basic_code_block_, ref.basic_block());
354 E : EXPECT_EQ(kRefSize, ref.size());
355 E : EXPECT_EQ(0, ref.offset());
356 E : EXPECT_EQ(0, ref.base());
357 E : EXPECT_TRUE(ref.IsValid());
358 E : }
359 :
360 E : TEST_F(BasicBlockTest, BlockReference) {
361 : static const BasicBlockReference::Offset kOffset = 48;
362 : static const BasicBlockReference::Offset kBase = kBlockSize / 2;
363 :
364 : BasicBlockReference ref(BlockGraph::RELATIVE_REF,
365 : kRefSize,
366 : macro_block_,
367 : kOffset,
368 E : kBase);
369 E : TestReferenceCopy(ref);
370 :
371 E : EXPECT_EQ(BasicBlockReference::REFERRED_TYPE_BLOCK, ref.referred_type());
372 E : EXPECT_EQ(NULL, ref.basic_block());
373 E : EXPECT_EQ(macro_block_, ref.block());
374 E : EXPECT_EQ(kRefSize, ref.size());
375 E : EXPECT_EQ(kOffset, ref.offset());
376 E : EXPECT_EQ(kBase, ref.base());
377 E : EXPECT_TRUE(ref.IsValid());
378 :
379 E : BasicBlockReference retyped(BlockGraph::PC_RELATIVE_REF, 1, ref);
380 E : EXPECT_EQ(BlockGraph::PC_RELATIVE_REF, retyped.reference_type());
381 E : EXPECT_EQ(BasicBlockReference::REFERRED_TYPE_BLOCK, retyped.referred_type());
382 E : EXPECT_EQ(NULL, retyped.basic_block());
383 E : EXPECT_EQ(macro_block_, retyped.block());
384 E : EXPECT_EQ(1, retyped.size());
385 E : EXPECT_EQ(kOffset, retyped.offset());
386 E : EXPECT_EQ(kBase, retyped.base());
387 E : EXPECT_TRUE(retyped.IsValid());
388 E : }
389 :
390 E : TEST_F(BasicBlockTest, CompareBasicBlockReferences) {
391 : BasicBlockReference r1(
392 E : BlockGraph::RELATIVE_REF, kRefSize, basic_code_block_);
393 : BasicBlockReference r2(
394 E : BlockGraph::RELATIVE_REF, kRefSize, basic_code_block_);
395 : BasicBlockReference r3(
396 E : BlockGraph::RELATIVE_REF, kRefSize, macro_block_, 8, 8);
397 :
398 E : EXPECT_TRUE(r1 == r2);
399 E : EXPECT_TRUE(r2 == r1);
400 E : EXPECT_FALSE(r2 == r3);
401 E : EXPECT_FALSE(r3 == r1);
402 E : }
403 :
404 E : TEST_F(BasicBlockTest, InvalidBasicBlockReferrer) {
405 : // Validate that an empty referrer is not valid.
406 E : BasicBlockReferrer referrer;
407 E : EXPECT_EQ(NULL, referrer.block());
408 E : EXPECT_EQ(-1, referrer.offset());
409 E : EXPECT_FALSE(referrer.IsValid());
410 E : }
411 :
412 E : TEST_F(BasicBlockTest, BlockReferrer) {
413 : static const BasicBlockReference::Offset kOffset = kBlockSize / 2;
414 :
415 E : BasicBlockReferrer referrer(macro_block_, kOffset);
416 :
417 E : EXPECT_EQ(macro_block_, referrer.block());
418 E : EXPECT_EQ(kOffset, referrer.offset());
419 E : EXPECT_TRUE(referrer.IsValid());
420 E : }
421 :
422 E : TEST_F(BasicBlockTest, CompareBasicBlockRefererrs) {
423 E : BlockGraph block_graph;
424 : BlockGraph::Block* b2 = block_graph.AddBlock(kMacroBlockType, kBlockSize,
425 E : kBlockName);
426 :
427 E : BasicBlockReferrer r1(b2, 4);
428 E : BasicBlockReferrer r2(b2, 4);
429 E : BasicBlockReferrer r3(macro_block_, 8);
430 :
431 E : EXPECT_TRUE(r1 == r2);
432 E : EXPECT_TRUE(r2 == r1);
433 E : EXPECT_FALSE(r2 == r3);
434 E : EXPECT_FALSE(r3 == r1);
435 E : }
436 :
437 E : TEST_F(BasicBlockTest, InvertConditionalBranchOpcode) {
438 : // This structure represents an entry in the opcode inversion table that
439 : // we'll use to drive the opcode inversion unit-test.
440 : struct OpcodeInversion {
441 : // The original opcode.
442 : uint16 original;
443 :
444 : // The inverted opcode. It will be zero (0) if the opcode isn't invertible.
445 : uint16 inverted;
446 : };
447 :
448 : static const OpcodeInversion kOpcodeInversionTable[] = {
449 : // We'll only encode one direction, and the test will infer the reverse.
450 : { I_JA, I_JBE },
451 : { I_JAE, I_JB },
452 : { I_JG, I_JLE },
453 : { I_JGE, I_JL },
454 : { I_JO, I_JNO },
455 : { I_JP, I_JNP, },
456 : { I_JS, I_JNS, },
457 : { I_JZ, I_JNZ, },
458 :
459 : // @TODO(rogerm): These opcodes are not supported yet.
460 : { I_JCXZ, 0 },
461 : { I_JECXZ, 0 },
462 : { I_LOOP, 0 },
463 : { I_LOOPNZ, 0 },
464 : { I_LOOPZ, 0 },
465 :
466 : // These opcodes are not invertible.
467 : { I_CALL, 0 },
468 : { I_MOV, 0 },
469 : { I_RET, 0 },
470 : };
471 :
472 : // Walk through the table validating that the InvertConditionalBranchOpcode()
473 : // function returns the same inversion results.
474 E : for (int i = 0; i < arraysize(kOpcodeInversionTable); ++i) {
475 E : uint16 opcode = kOpcodeInversionTable[i].original;
476 E : bool should_pass = kOpcodeInversionTable[i].inverted != 0;
477 : EXPECT_EQ(should_pass,
478 E : Instruction::InvertConditionalBranchOpcode(&opcode));
479 E : if (should_pass) {
480 E : EXPECT_EQ(kOpcodeInversionTable[i].inverted, opcode);
481 E : EXPECT_TRUE(Instruction::InvertConditionalBranchOpcode(&opcode));
482 E : EXPECT_EQ(kOpcodeInversionTable[i].original, opcode);
483 : }
484 E : }
485 E : }
486 :
487 : typedef BasicBlockTest SuccessorTest;
488 :
489 : namespace {
490 :
491 E : void TestSuccessorCopy(const Successor& input) {
492 E : Successor copy(input);
493 :
494 E : EXPECT_EQ(input.condition(), copy.condition());
495 E : EXPECT_EQ(input.reference(), copy.reference());
496 E : EXPECT_EQ(input.label(), copy.label());
497 E : EXPECT_EQ(input.has_label(), copy.has_label());
498 E : EXPECT_EQ(input.source_range(), copy.source_range());
499 E : EXPECT_EQ(input.instruction_size(), copy.instruction_size());
500 E : EXPECT_EQ(input.tags(), copy.tags());
501 E : }
502 :
503 : } // namespace
504 :
505 :
506 E : TEST_F(SuccessorTest, DefaultConstructor) {
507 E : Successor s;
508 :
509 E : TestSuccessorCopy(s);
510 E : EXPECT_EQ(Successor::kInvalidCondition, s.condition());
511 E : EXPECT_EQ(BasicBlockReference(), s.reference());
512 E : EXPECT_EQ(0, s.instruction_size());
513 E : EXPECT_FALSE(s.has_label());
514 E : }
515 :
516 E : TEST_F(SuccessorTest, BasicCodeBlockConstructor) {
517 E : const Successor::Condition kCondition = Successor::kConditionAbove;
518 E : const Successor::Size kSuccessorSize = 5;
519 E : BasicCodeBlock* bb = subgraph_.AddBasicCodeBlock("bb");
520 E : BasicBlockReference bb_ref(BlockGraph::ABSOLUTE_REF, 4, bb);
521 :
522 : Successor s(kCondition,
523 : bb_ref,
524 E : kSuccessorSize);
525 :
526 E : TestSuccessorCopy(s);
527 E : EXPECT_EQ(kCondition, s.condition());
528 E : EXPECT_EQ(bb_ref, s.reference());
529 E : EXPECT_EQ(kSuccessorSize, s.instruction_size());
530 E : }
531 :
532 E : TEST_F(SuccessorTest, SetBranchTarget) {
533 E : BasicCodeBlock* bb = subgraph_.AddBasicCodeBlock("bb");
534 E : BasicBlockReference bb_ref(BlockGraph::ABSOLUTE_REF, 4, bb);
535 :
536 E : Successor s;
537 E : s.SetReference(bb_ref);
538 E : TestSuccessorCopy(s);
539 :
540 E : EXPECT_EQ(bb_ref, s.reference());
541 E : }
542 :
543 E : TEST_F(SuccessorTest, LabelsAndTags) {
544 E : Successor successor;
545 E : EXPECT_FALSE(successor.has_label());
546 :
547 E : BlockGraph::Label label("Foo", BlockGraph::CODE_LABEL);
548 E : successor.set_label(label);
549 E : successor.tags().insert(&successor);
550 :
551 E : TestSuccessorCopy(successor);
552 E : EXPECT_TRUE(successor.has_label());
553 E : EXPECT_TRUE(successor.label() == label);
554 E : EXPECT_EQ(1u, successor.tags().size());
555 E : EXPECT_NE(successor.tags().end(), successor.tags().find(&successor));
556 E : }
557 :
558 E : TEST_F(SuccessorTest, OpCodeToCondition) {
559 : struct TableEntry {
560 : uint16 op_code;
561 : Successor::Condition condition;
562 : };
563 :
564 : const TableEntry kOpCodeToConditionTable[] = {
565 : { I_JA, Successor::kConditionAbove },
566 : { I_JAE, Successor::kConditionAboveOrEqual },
567 : { I_JB, Successor::kConditionBelow },
568 : { I_JBE, Successor::kConditionBelowOrEqual },
569 : { I_JG, Successor::kConditionGreater },
570 : { I_JGE, Successor::kConditionGreaterOrEqual },
571 : { I_JL, Successor::kConditionLess },
572 : { I_JLE, Successor::kConditionLessOrEqual },
573 : { I_JNO, Successor::kConditionNotOverflow },
574 : { I_JNP, Successor::kConditionNotParity },
575 : { I_JNS, Successor::kConditionNotSigned },
576 : { I_JNZ, Successor::kConditionNotEqual },
577 : { I_JO, Successor::kConditionOverflow },
578 : { I_JP, Successor::kConditionParity },
579 : { I_JS, Successor::kConditionSigned },
580 : { I_JZ, Successor::kConditionEqual },
581 E : };
582 :
583 : static_assert(arraysize(kOpCodeToConditionTable) ==
584 : Successor::kMaxConditionalBranch + 1,
585 : "Unexpected number of map entries.");
586 :
587 E : for (size_t i = 0; i < arraysize(kOpCodeToConditionTable); ++i) {
588 E : const TableEntry& entry = kOpCodeToConditionTable[i];
589 E : EXPECT_EQ(entry.condition, Successor::OpCodeToCondition(entry.op_code));
590 E : }
591 :
592 : // These two are non-conditional exceptions.
593 E : EXPECT_EQ(Successor::kInvalidCondition, Successor::OpCodeToCondition(I_MOV));
594 E : EXPECT_EQ(Successor::kConditionTrue, Successor::OpCodeToCondition(I_JMP));
595 E : }
596 :
597 E : TEST_F(SuccessorTest, InvertCondition) {
598 : struct TableEntry {
599 : Successor::Condition original;
600 : Successor::Condition inverse;
601 : };
602 : static const TableEntry kConditionInversionTable[] = {
603 : { Successor::kConditionTrue, Successor::kInvalidCondition },
604 : { Successor::kConditionAbove, Successor::kConditionBelowOrEqual },
605 : { Successor::kConditionAboveOrEqual, Successor::kConditionBelow },
606 : { Successor::kConditionBelow, Successor::kConditionAboveOrEqual },
607 : { Successor::kConditionBelowOrEqual, Successor::kConditionAbove },
608 : { Successor::kConditionEqual, Successor::kConditionNotEqual },
609 : { Successor::kConditionGreater, Successor::kConditionLessOrEqual },
610 : { Successor::kConditionGreaterOrEqual, Successor::kConditionLess },
611 : { Successor::kConditionLess, Successor::kConditionGreaterOrEqual },
612 : { Successor::kConditionLessOrEqual, Successor::kConditionGreater },
613 : { Successor::kConditionNotEqual, Successor::kConditionEqual },
614 : { Successor::kConditionNotOverflow, Successor::kConditionOverflow },
615 : { Successor::kConditionNotParity, Successor::kConditionParity },
616 : { Successor::kConditionNotSigned, Successor::kConditionSigned },
617 : { Successor::kConditionOverflow, Successor::kConditionNotOverflow },
618 : { Successor::kConditionParity, Successor::kConditionNotParity },
619 : { Successor::kConditionSigned, Successor::kConditionNotSigned },
620 : };
621 :
622 : static_assert(arraysize(kConditionInversionTable) == Successor::kMaxCondition,
623 : "Unexpected number of inversion table entries.");
624 :
625 E : for (size_t i = 0; i < arraysize(kConditionInversionTable); ++i) {
626 E : const TableEntry& entry = kConditionInversionTable[i];
627 E : EXPECT_EQ(entry.inverse, Successor::InvertCondition(entry.original));
628 E : }
629 E : }
630 :
631 : typedef BasicBlockTest InstructionTest;
632 :
633 : namespace {
634 :
635 E : void TestInstructionCopy(const Instruction& input) {
636 E : Instruction copy(input);
637 :
638 E : EXPECT_EQ(input.references(), copy.references());
639 E : EXPECT_EQ(input.label(), copy.label());
640 E : EXPECT_EQ(input.has_label(), copy.has_label());
641 E : EXPECT_EQ(input.source_range(), copy.source_range());
642 E : EXPECT_EQ(0, memcmp(input.data(), copy.data(), copy.size()));
643 E : EXPECT_EQ(input.size(), copy.size());
644 E : }
645 :
646 : const uint8 kCallRelative[] = { 0xE8, 0xDE, 0xAD, 0xBE, 0xEF };
647 :
648 : } // namespace
649 :
650 E : TEST_F(InstructionTest, ConstructionFromData) {
651 E : const uint8 kCallRelative[] = { 0xE8, 0xDE, 0xAD, 0xBE, 0xEF };
652 E : Instruction call;
653 : ASSERT_TRUE(
654 E : Instruction::FromBuffer(kCallRelative, arraysize(kCallRelative), &call));
655 :
656 E : _DInst& repr = call.representation();
657 E : EXPECT_EQ(I_CALL, repr.opcode);
658 E : EXPECT_EQ(FC_CALL, META_GET_FC(repr.meta));
659 E : EXPECT_EQ(O_PC, repr.ops[0].type);
660 E : TestInstructionCopy(call);
661 :
662 E : BlockGraph::Label label("Foo", BlockGraph::CODE_LABEL);
663 E : call.set_label(label);
664 E : EXPECT_EQ(label, call.label());
665 E : TestInstructionCopy(call);
666 E : }
667 :
668 E : TEST_F(InstructionTest, Copy) {
669 E : const uint8 kCallRelative[] = { 0xE8, 0xDE, 0xAD, 0xBE, 0xEF };
670 E : Instruction call;
671 : ASSERT_TRUE(
672 E : Instruction::FromBuffer(kCallRelative, arraysize(kCallRelative), &call));
673 E : call.set_source_range(Instruction::SourceRange(core::RelativeAddress(0), 5));
674 E : call.set_label(BlockGraph::Label("foo", 0));
675 E : call.tags().insert(&call);
676 :
677 E : Instruction copy(call);
678 E : EXPECT_EQ(call.opcode(), copy.opcode());
679 E : EXPECT_EQ(call.size(), copy.size());
680 E : EXPECT_EQ(call.references(), copy.references());
681 E : EXPECT_EQ(call.source_range(), copy.source_range());
682 E : EXPECT_EQ(call.label(), copy.label());
683 E : EXPECT_EQ(call.tags(), copy.tags());
684 E : }
685 :
686 E : TEST_F(InstructionTest, ToString) {
687 E : Instruction nop;
688 E : std::string buffer;
689 E : EXPECT_TRUE(nop.ToString(&buffer));
690 E : ASSERT_THAT(buffer, testing::HasSubstr("90"));
691 E : ASSERT_THAT(buffer, testing::HasSubstr("NOP"));
692 E : }
693 :
694 E : TEST_F(InstructionTest, CallsNonReturningFunction) {
695 E : BlockGraph block_graph;
696 :
697 : // Create a returning code block.
698 : BlockGraph::Block* returning =
699 E : block_graph.AddBlock(BlockGraph::CODE_BLOCK, 1, "return");
700 :
701 : // Create a non-returning code block.
702 : BlockGraph::Block* non_returning =
703 E : block_graph.AddBlock(BlockGraph::CODE_BLOCK, 1, "non-return");
704 E : non_returning->set_attribute(BlockGraph::NON_RETURN_FUNCTION);
705 :
706 E : Instruction call_relative;
707 : ASSERT_TRUE(Instruction::FromBuffer(kCallRelative,
708 : sizeof(kCallRelative),
709 E : &call_relative));
710 :
711 E : TestInstructionCopy(call_relative);
712 :
713 : // Call the returning function directly.
714 : call_relative.SetReference(
715 : 1, BasicBlockReference(BlockGraph::RELATIVE_REF,
716 : BlockGraph::Reference::kMaximumSize,
717 E : returning, 0, 0));
718 E : EXPECT_FALSE(call_relative.CallsNonReturningFunction());
719 :
720 : // Call the non-returning function directly.
721 : call_relative.SetReference(
722 : 1, BasicBlockReference(BlockGraph::RELATIVE_REF,
723 : BlockGraph::Reference::kMaximumSize,
724 E : non_returning, 0, 0));
725 E : EXPECT_TRUE(call_relative.CallsNonReturningFunction());
726 :
727 : // Setup an indirect call via a static function pointer (for example, an
728 : // import table).
729 : BlockGraph::Block* function_pointer =
730 : block_graph.AddBlock(BlockGraph::DATA_BLOCK,
731 E : BlockGraph::Reference::kMaximumSize, "ptr");
732 E : const uint8 kCallIndirect[] = { 0xFF, 0x15, 0xDE, 0xAD, 0xBE, 0xEF };
733 E : Instruction call_indirect;
734 : ASSERT_TRUE(Instruction::FromBuffer(kCallIndirect,
735 : sizeof(kCallIndirect),
736 E : &call_indirect));
737 : call_indirect.SetReference(
738 : 2, BasicBlockReference(BlockGraph::RELATIVE_REF,
739 : BlockGraph::Reference::kMaximumSize,
740 E : function_pointer, 0, 0));
741 E : TestInstructionCopy(call_indirect);
742 :
743 : // Call the returning function via the pointer.
744 : function_pointer->SetReference(
745 : 0, BlockGraph::Reference(BlockGraph::ABSOLUTE_REF,
746 : BlockGraph::Reference::kMaximumSize,
747 E : returning, 0, 0));
748 E : EXPECT_FALSE(call_indirect.CallsNonReturningFunction());
749 :
750 : // Call the returning function via the pointer.
751 : function_pointer->SetReference(
752 : 0, BlockGraph::Reference(BlockGraph::ABSOLUTE_REF,
753 : BlockGraph::Reference::kMaximumSize,
754 E : non_returning, 0, 0));
755 E : EXPECT_TRUE(call_indirect.CallsNonReturningFunction());
756 E : }
757 :
758 E : TEST_F(InstructionTest, FindOperandReference) {
759 E : BasicBlock::Instructions instructions;
760 E : BasicBlockAssembler assm(instructions.begin(), &instructions);
761 :
762 : {
763 : // Generate a dual-reference instruction.
764 : assm.mov(Operand(assm::eax, assm::ebx, assm::kTimes4,
765 : Displacement(basic_code_block_)),
766 E : Immediate(macro_block_, 30));
767 E : const Instruction& inst = instructions.back();
768 :
769 E : BasicBlockReference ref0;
770 E : EXPECT_TRUE(inst.FindOperandReference(0, &ref0));
771 : EXPECT_EQ(BasicBlockReference::REFERRED_TYPE_BASIC_BLOCK,
772 E : ref0.referred_type());
773 E : EXPECT_EQ(basic_code_block_, ref0.basic_block());
774 :
775 E : BasicBlockReference ref1;
776 E : EXPECT_TRUE(inst.FindOperandReference(1, &ref1));
777 E : EXPECT_EQ(BasicBlockReference::REFERRED_TYPE_BLOCK, ref1.referred_type());
778 E : EXPECT_EQ(macro_block_, ref1.block());
779 :
780 E : BasicBlockReference ignore;
781 E : EXPECT_FALSE(inst.FindOperandReference(2, &ignore));
782 E : EXPECT_FALSE(inst.FindOperandReference(3, &ignore));
783 E : }
784 :
785 : {
786 : // Generate a singe-reference instruction with an 8-bit immediate.
787 : assm.mov(Operand(assm::eax, assm::ebx, assm::kTimes4,
788 : Displacement(basic_code_block_)),
789 E : Immediate(0x10, assm::kSize8Bit));
790 :
791 E : const Instruction& inst = instructions.back();
792 :
793 E : BasicBlockReference ref0;
794 E : EXPECT_TRUE(inst.FindOperandReference(0, &ref0));
795 : EXPECT_EQ(BasicBlockReference::REFERRED_TYPE_BASIC_BLOCK,
796 E : ref0.referred_type());
797 E : EXPECT_EQ(basic_code_block_, ref0.basic_block());
798 :
799 E : BasicBlockReference ignore;
800 E : EXPECT_FALSE(inst.FindOperandReference(1, &ignore));
801 E : EXPECT_FALSE(inst.FindOperandReference(2, &ignore));
802 E : EXPECT_FALSE(inst.FindOperandReference(3, &ignore));
803 E : }
804 E : }
805 :
806 : } // namespace block_graph
|