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