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