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