1 : // Copyright 2012 Google Inc.
2 : //
3 : // Licensed under the Apache License, Version 2.0 (the "License");
4 : // you may not use this file except in compliance with the License.
5 : // You may obtain a copy of the License at
6 : //
7 : // http://www.apache.org/licenses/LICENSE-2.0
8 : //
9 : // Unless required by applicable law or agreed to in writing, software
10 : // distributed under the License is distributed on an "AS IS" BASIS,
11 : // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 : // See the License for the specific language governing permissions and
13 : // limitations under the License.
14 : //
15 : // Tests for the basic block classes.
16 :
17 : #include "syzygy/block_graph/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_(kBlockId, kBlockName, BasicBlock::BASIC_CODE_BLOCK,
41 : kBlockOffset, kBlockSize, kBlockData),
42 : basic_data_block_(kBlockId, kBlockName, BasicBlock::BASIC_DATA_BLOCK,
43 : kBlockOffset, kBlockSize, kBlockData),
44 E : macro_block_(kBlockId, 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 opocode 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 I_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::Representation ret = {};
96 E : ret.addr = 0;
97 E : ret.opcode = I_RET;
98 E : ret.size = 1;
99 E : META_SET_ISC(&ret, ISC_INTEGER);
100 E : return Instruction(ret, -1, sizeof(data), data);
101 E : }
102 :
103 : // Helper function to create a CALL instruction.
104 E : Instruction CreateCall(BasicBlockReference ref) {
105 : static const uint8 data[] = { 0xE8, 0x00, 0x00, 0x00, 0x00 };
106 E : Instruction::Representation call = {};
107 E : call.addr = 0;
108 E : call.opcode = I_CALL;
109 E : call.size = 5;
110 E : META_SET_ISC(&call, ISC_INTEGER);
111 E : Instruction call_inst(call, -1, sizeof(data), data);
112 E : call_inst.SetReference(1, ref);
113 E : EXPECT_FALSE(call_inst.has_label());
114 E : call_inst.set_label(BlockGraph::Label("call", BlockGraph::CALL_SITE_LABEL));
115 E : EXPECT_TRUE(call_inst.has_label());
116 E : EXPECT_TRUE(call_inst.label().has_attributes(BlockGraph::CALL_SITE_LABEL));
117 E : return call_inst;
118 E : }
119 :
120 : // Helper function to create a successor branch instruction.
121 E : Successor CreateBranch(uint16 opcode, Successor::Offset target) {
122 E : return Successor(Successor::OpCodeToCondition(opcode), target, -1, 0);
123 E : }
124 :
125 : // Some handy constants we'll use throughout the tests.
126 : // @{
127 : static const BasicBlock::BlockId kBlockId;
128 : static const BasicBlock::BasicBlockType kBasicBlockType;
129 : static const BlockGraph::BlockType kMacroBlockType;
130 : static const char kBlockName[];
131 : static const BasicBlock::Offset kBlockOffset;
132 : static const BasicBlock::Size kBlockSize;
133 : static const uint8 kBlockData[];
134 : static const size_t kRefSize;
135 : static const Successor::Offset kOffset1;
136 : static const Successor::Offset kOffset2;
137 : // @}
138 :
139 : protected:
140 : BasicBlock basic_code_block_;
141 : BasicBlock basic_data_block_;
142 : BlockGraph::Block macro_block_;
143 : };
144 :
145 : const BasicBlock::BlockId BasicBlockTest::kBlockId = 1;
146 : const BasicBlock::BasicBlockType BasicBlockTest::kBasicBlockType =
147 : BasicBlock::BASIC_CODE_BLOCK;
148 : const BlockGraph::BlockType BasicBlockTest::kMacroBlockType =
149 : BlockGraph::CODE_BLOCK;
150 : const char BasicBlockTest::kBlockName[] = "test block";
151 : const BasicBlock::Offset BasicBlockTest::kBlockOffset = 0;
152 : const BasicBlock::Size BasicBlockTest::kBlockSize = 32;
153 : const uint8 BasicBlockTest::kBlockData[BasicBlockTest::kBlockSize] = {};
154 : const size_t BasicBlockTest::kRefSize = BlockGraph::Reference::kMaximumSize;
155 : const Successor::Offset BasicBlockTest::kOffset1(0xAABBCCDD);
156 : const Successor::Offset BasicBlockTest::kOffset2(0x11223344);
157 :
158 : } // namespace
159 :
160 E : TEST_F(BasicBlockTest, InstructionConstructor) {
161 E : Instruction ret_instr(CreateRet());
162 E : ASSERT_FALSE(ret_instr.owns_data());
163 :
164 : {
165 : // This should not copy the data.
166 E : Instruction ret_temp(ret_instr);
167 E : ASSERT_FALSE(ret_temp.owns_data());
168 E : ASSERT_EQ(ret_instr.data(), ret_temp.data());
169 E : }
170 :
171 : {
172 : // Construction from data should make a copy of the data.
173 E : Instruction ret_temp(ret_instr.size(), ret_instr.data());
174 E : ASSERT_TRUE(ret_temp.owns_data());
175 E : ASSERT_NE(ret_instr.data(), ret_temp.data());
176 E : }
177 :
178 : {
179 : // This should copy the references.
180 : BasicBlockReference r1(
181 E : BlockGraph::RELATIVE_REF, kRefSize, &basic_code_block_);
182 E : Instruction call_instr = CreateCall(r1);
183 E : ASSERT_TRUE(call_instr.references().size() == 1);
184 E : Instruction call_temp(call_instr);
185 E : ASSERT_EQ(call_instr.references(), call_temp.references());
186 E : }
187 E : }
188 :
189 E : TEST_F(BasicBlockTest, BasicBlockAccessors) {
190 E : EXPECT_EQ(kBlockId, basic_code_block_.id());
191 E : EXPECT_EQ(kBasicBlockType, basic_code_block_.type());
192 E : EXPECT_STREQ(kBlockName, basic_code_block_.name().c_str());
193 E : EXPECT_EQ(&kBlockData[0], basic_code_block_.data());
194 E : EXPECT_EQ(kBlockSize, basic_code_block_.size());
195 E : EXPECT_TRUE(basic_code_block_.references().empty());
196 E : EXPECT_TRUE(basic_code_block_.referrers().empty());
197 E : EXPECT_FALSE(basic_code_block_.has_label());
198 E : EXPECT_TRUE(basic_data_block_.has_label());
199 : EXPECT_TRUE(basic_data_block_.label().has_attributes(
200 E : BlockGraph::DATA_LABEL | BlockGraph::CASE_TABLE_LABEL));
201 E : }
202 :
203 E : TEST_F(BasicBlockTest, GetMaxCodeSize) {
204 E : basic_code_block_.instructions().push_back(CreateRet());
205 E : basic_code_block_.instructions().push_back(CreateRet());
206 E : basic_code_block_.instructions().push_back(CreateRet());
207 E : basic_code_block_.instructions().push_back(CreateRet());
208 E : basic_code_block_.successors().push_back(CreateBranch(I_JZ, kOffset1));
209 :
210 : ASSERT_EQ(4 * CreateRet().size() + core::AssemblerImpl::kMaxInstructionLength,
211 E : basic_code_block_.GetMaxSize());
212 E : }
213 :
214 E : TEST_F(BasicBlockTest, GetMaxDataSize) {
215 : BasicBlock bb(kBlockId, kBlockName, BasicBlock::BASIC_DATA_BLOCK,
216 E : kBlockOffset, kBlockSize, kBlockData);
217 :
218 E : ASSERT_EQ(kBlockSize, bb.GetMaxSize());
219 E : }
220 :
221 E : TEST_F(BasicBlockTest, EmptyBasicBlockIsNotValid) {
222 : // Upon creation the basic block (which happens to be a code block) has
223 : // neither instructions nor successors, which we consider to be an invalid
224 : // state.
225 E : ASSERT_FALSE(basic_code_block_.IsValid());
226 E : }
227 :
228 E : TEST_F(BasicBlockTest, BasicBlockWithOnlyConditionalSuccessorIsNotValid) {
229 E : basic_code_block_.successors().push_back(CreateBranch(I_JNZ, kOffset1));
230 E : ASSERT_FALSE(basic_code_block_.IsValid());
231 E : }
232 :
233 : TEST_F(BasicBlockTest,
234 E : BasicBlockWithConditionalAndFallThroughSuccessorsIsValid) {
235 E : basic_code_block_.successors().push_back(CreateBranch(I_JNZ, kOffset1));
236 E : basic_code_block_.successors().push_back(CreateBranch(I_JZ, kOffset2));
237 E : ASSERT_TRUE(basic_code_block_.IsValid());
238 E : }
239 :
240 : TEST_F(BasicBlockTest,
241 E : BasicBlockWithFallThroughSuccessorIsValid) {
242 E : basic_code_block_.successors().push_back(CreateBranch(I_JMP, kOffset2));
243 E : ASSERT_TRUE(basic_code_block_.IsValid());
244 E : }
245 :
246 : TEST_F(BasicBlockTest,
247 E : BasicBlockWithTerminalInstructionNoSuccessorsIsValid) {
248 E : basic_code_block_.instructions().push_back(CreateRet());
249 E : ASSERT_TRUE(basic_code_block_.IsValid());
250 E : }
251 :
252 E : TEST_F(BasicBlockTest, InvalidBasicBlockReference) {
253 : // Validate that a ref that points to nothing is not valid and doesn't claim
254 : // to point to anything.
255 E : BasicBlockReference ref;
256 E : EXPECT_EQ(BasicBlockReference::REFERRED_TYPE_UNKNOWN, ref.referred_type());
257 E : EXPECT_EQ(NULL, ref.block());
258 E : EXPECT_EQ(NULL, ref.basic_block());
259 E : EXPECT_EQ(-1, ref.offset());
260 E : EXPECT_EQ(0, ref.size());
261 E : EXPECT_FALSE(ref.IsValid());
262 E : }
263 :
264 E : TEST_F(BasicBlockTest, BasicBlockReference) {
265 : BasicBlockReference ref(BlockGraph::RELATIVE_REF,
266 : kRefSize,
267 E : &basic_code_block_);
268 :
269 : EXPECT_EQ(BasicBlockReference::REFERRED_TYPE_BASIC_BLOCK,
270 E : ref.referred_type());
271 E : EXPECT_EQ(NULL, ref.block());
272 E : EXPECT_EQ(&basic_code_block_, ref.basic_block());
273 E : EXPECT_EQ(kRefSize, ref.size());
274 E : EXPECT_EQ(0, ref.offset());
275 E : EXPECT_EQ(0, ref.base());
276 E : EXPECT_TRUE(ref.IsValid());
277 E : }
278 :
279 E : TEST_F(BasicBlockTest, BlockReference) {
280 : static const BasicBlockReference::Offset kOffset = 48;
281 : static const BasicBlockReference::Offset kBase = kBlockSize / 2;
282 :
283 : BasicBlockReference ref(BlockGraph::RELATIVE_REF,
284 : kRefSize,
285 : ¯o_block_,
286 : kOffset,
287 E : kBase);
288 :
289 E : EXPECT_EQ(BasicBlockReference::REFERRED_TYPE_BLOCK, ref.referred_type());
290 E : EXPECT_EQ(NULL, ref.basic_block());
291 E : EXPECT_EQ(¯o_block_, ref.block());
292 E : EXPECT_EQ(kRefSize, ref.size());
293 E : EXPECT_EQ(kOffset, ref.offset());
294 E : EXPECT_EQ(kBase, ref.base());
295 E : EXPECT_TRUE(ref.IsValid());
296 E : }
297 :
298 E : TEST_F(BasicBlockTest, CompareBasicBlockReferences) {
299 : BasicBlockReference r1(
300 E : BlockGraph::RELATIVE_REF, kRefSize, &basic_code_block_);
301 : BasicBlockReference r2(
302 E : BlockGraph::RELATIVE_REF, kRefSize, &basic_code_block_);
303 : BasicBlockReference r3(
304 E : BlockGraph::RELATIVE_REF, kRefSize, ¯o_block_, 8, 8);
305 :
306 E : EXPECT_TRUE(r1 == r2);
307 E : EXPECT_TRUE(r2 == r1);
308 E : EXPECT_FALSE(r2 == r3);
309 E : EXPECT_FALSE(r3 == r1);
310 E : }
311 :
312 E : TEST_F(BasicBlockTest, InvalidBasicBlockReferrer) {
313 : // Validate that an empty referrer is not valid.
314 E : BasicBlockReferrer referrer;
315 : EXPECT_EQ(BasicBlockReference::REFERRED_TYPE_UNKNOWN,
316 E : referrer.referrer_type());
317 E : EXPECT_EQ(NULL, referrer.block());
318 E : EXPECT_EQ(NULL, referrer.basic_block());
319 E : EXPECT_EQ(-1, referrer.offset());
320 E : EXPECT_FALSE(referrer.IsValid());
321 E : }
322 :
323 E : TEST_F(BasicBlockTest, BasicBlockReferrer) {
324 : static const BasicBlockReference::Offset kOffset = kBlockSize / 2;
325 :
326 E : BasicBlockReferrer referrer(&basic_data_block_, kOffset);
327 :
328 : EXPECT_EQ(BasicBlockReferrer::REFERRER_TYPE_BASIC_BLOCK,
329 E : referrer.referrer_type());
330 E : EXPECT_EQ(NULL, referrer.block());
331 E : EXPECT_EQ(NULL, referrer.successor());
332 E : EXPECT_EQ(NULL, referrer.instruction());
333 E : EXPECT_EQ(&basic_data_block_, referrer.basic_block());
334 E : EXPECT_EQ(kOffset, referrer.offset());
335 E : EXPECT_TRUE(referrer.IsValid());
336 E : }
337 :
338 E : TEST_F(BasicBlockTest, BlockReferrer) {
339 : static const BasicBlockReference::Offset kOffset = kBlockSize / 2;
340 :
341 E : BasicBlockReferrer referrer(¯o_block_, kOffset);
342 :
343 E : EXPECT_EQ(BasicBlockReferrer::REFERRER_TYPE_BLOCK, referrer.referrer_type());
344 E : EXPECT_EQ(NULL, referrer.basic_block());
345 E : EXPECT_EQ(NULL, referrer.successor());
346 E : EXPECT_EQ(NULL, referrer.instruction());
347 E : EXPECT_EQ(¯o_block_, referrer.block());
348 E : EXPECT_EQ(kOffset, referrer.offset());
349 E : EXPECT_TRUE(referrer.IsValid());
350 E : }
351 :
352 E : TEST_F(BasicBlockTest, InstructionReferrer) {
353 : static const BasicBlockReference::Offset kOffset = 2;
354 E : Instruction instr(Instruction::Representation(), kOffset, 5, kBlockData);
355 E : BasicBlockReferrer referrer(&instr, kOffset);
356 :
357 : EXPECT_EQ(BasicBlockReferrer::REFERRER_TYPE_INSTRUCTION,
358 E : referrer.referrer_type());
359 E : EXPECT_EQ(NULL, referrer.basic_block());
360 E : EXPECT_EQ(NULL, referrer.block());
361 E : EXPECT_EQ(NULL, referrer.successor());
362 E : EXPECT_EQ(&instr, referrer.instruction());
363 E : EXPECT_EQ(kOffset, referrer.offset());
364 E : EXPECT_TRUE(referrer.IsValid());
365 E : }
366 :
367 E : TEST_F(BasicBlockTest, SuccessorReferrer) {
368 E : Successor succ(Successor::kConditionGreater, -12, 5, 5);
369 E : BasicBlockReferrer referrer(&succ);
370 :
371 : EXPECT_EQ(BasicBlockReferrer::REFERRER_TYPE_SUCCESSOR,
372 E : referrer.referrer_type());
373 E : EXPECT_EQ(NULL, referrer.basic_block());
374 E : EXPECT_EQ(NULL, referrer.block());
375 E : EXPECT_EQ(NULL, referrer.instruction());
376 E : EXPECT_EQ(&succ, referrer.successor());
377 E : EXPECT_EQ(BasicBlock::kNoOffset, referrer.offset());
378 E : EXPECT_TRUE(referrer.IsValid());
379 E : }
380 :
381 E : TEST_F(BasicBlockTest, CompareBasicBlockRefererrs) {
382 E : BasicBlockReferrer r1(&basic_data_block_, 4);
383 E : BasicBlockReferrer r2(&basic_data_block_, 4);
384 E : BasicBlockReferrer r3(¯o_block_, 8);
385 :
386 E : EXPECT_TRUE(r1 == r2);
387 E : EXPECT_TRUE(r2 == r1);
388 E : EXPECT_FALSE(r2 == r3);
389 E : EXPECT_FALSE(r3 == r1);
390 E : }
391 :
392 E : TEST_F(BasicBlockTest, InvertConditionalBranchOpcode) {
393 : // This structure represents an entry in the opcode inversion table that
394 : // we'll use to drive the opcode inversion unit-test.
395 : struct OpcodeInversion {
396 : // The original opcode.
397 : uint16 original;
398 :
399 : // The inverted opcode. It will be zero (0) if the opcode isn't invertible.
400 : uint16 inverted;
401 : };
402 :
403 : static const OpcodeInversion kOpcodeInversionTable[] = {
404 : // We'll only encode one direction, and the test will infer the reverse.
405 : { I_JA, I_JBE },
406 : { I_JAE, I_JB },
407 : { I_JG, I_JLE },
408 : { I_JGE, I_JL },
409 : { I_JO, I_JNO },
410 : { I_JP, I_JNP, },
411 : { I_JS, I_JNS, },
412 : { I_JZ, I_JNZ, },
413 :
414 : // @TODO(rogerm): These opcodes are not supported yet.
415 : { I_JCXZ, 0 },
416 : { I_JECXZ, 0 },
417 : { I_LOOP, 0 },
418 : { I_LOOPNZ, 0 },
419 : { I_LOOPZ, 0 },
420 :
421 : // These opcodes are not invertible.
422 : { I_CALL, 0 },
423 : { I_MOV, 0 },
424 : { I_RET, 0 },
425 : };
426 :
427 : // Walk through the table validating that the InvertConditionalBranchOpcode()
428 : // function returns the same inversion results.
429 E : for (int i = 0; i < arraysize(kOpcodeInversionTable); ++i) {
430 E : uint16 opcode = kOpcodeInversionTable[i].original;
431 E : bool should_pass = kOpcodeInversionTable[i].inverted != 0;
432 : EXPECT_EQ(should_pass,
433 E : Instruction::InvertConditionalBranchOpcode(&opcode));
434 E : if (should_pass) {
435 E : EXPECT_EQ(kOpcodeInversionTable[i].inverted, opcode);
436 E : EXPECT_TRUE(Instruction::InvertConditionalBranchOpcode(&opcode));
437 E : EXPECT_EQ(kOpcodeInversionTable[i].original, opcode);
438 E : }
439 : }
440 E : }
441 :
442 : typedef BasicBlockTest SuccessorTest;
443 :
444 E : TEST_F(SuccessorTest, DefaultConstructor) {
445 E : Successor s;
446 E : EXPECT_EQ(Successor::kInvalidCondition, s.condition());
447 E : EXPECT_EQ(-1, s.bb_target_offset());
448 E : EXPECT_EQ(BasicBlockReference(), s.reference());
449 E : EXPECT_EQ(-1, s.instruction_offset());
450 E : EXPECT_EQ(0, s.instruction_size());
451 E : }
452 :
453 E : TEST_F(SuccessorTest, OffsetConstructor) {
454 E : const Successor::Condition kCondition = Successor::kConditionAbove;
455 E : const Successor::Offset kTargetOffset(0x12345678);
456 E : const Successor::Offset kInstructinOffset = 32;
457 E : const Successor::Size kInstructionSize = 5;
458 :
459 : Successor s(kCondition,
460 : kTargetOffset,
461 : kInstructinOffset,
462 E : kInstructionSize);
463 :
464 E : EXPECT_EQ(kCondition, s.condition());
465 E : EXPECT_EQ(kTargetOffset, s.bb_target_offset());
466 E : EXPECT_EQ(BasicBlockReference(), s.reference());
467 E : EXPECT_EQ(kInstructinOffset, s.instruction_offset());
468 E : EXPECT_EQ(kInstructionSize, s.instruction_size());
469 E : }
470 :
471 E : TEST_F(SuccessorTest, BasicBlockConstructor) {
472 E : const Successor::Condition kCondition = Successor::kConditionAbove;
473 E : const Successor::Offset kSuccessorOffset = 4;
474 E : const Successor::Size kSuccessorSize = 5;
475 E : uint8 data[20] = {};
476 E : BasicBlock bb(1, "bb", BasicBlock::BASIC_CODE_BLOCK, 16, sizeof(data), data);
477 E : BasicBlockReference bb_ref(BlockGraph::ABSOLUTE_REF, 4, &bb);
478 :
479 : Successor s(kCondition,
480 : bb_ref,
481 : kSuccessorOffset,
482 E : kSuccessorSize);
483 :
484 E : EXPECT_EQ(kCondition, s.condition());
485 E : EXPECT_EQ(-1, s.bb_target_offset());
486 E : EXPECT_EQ(bb_ref, s.reference());
487 E : EXPECT_EQ(kSuccessorOffset, s.instruction_offset());
488 E : EXPECT_EQ(kSuccessorSize, s.instruction_size());
489 E : }
490 :
491 E : TEST_F(SuccessorTest, SetBranchTarget) {
492 E : uint8 data[20] = {};
493 E : BasicBlock bb(1, "bb", BasicBlock::BASIC_CODE_BLOCK, 16, sizeof(data), data);
494 E : BasicBlockReference bb_ref(BlockGraph::ABSOLUTE_REF, 4, &bb);
495 :
496 E : Successor s;
497 E : s.SetReference(bb_ref);
498 E : EXPECT_EQ(bb_ref, s.reference());
499 E : }
500 :
501 E : TEST_F(SuccessorTest, Labels) {
502 E : Successor successor;
503 E : EXPECT_FALSE(successor.has_label());
504 :
505 E : BlockGraph::Label label("Foo", BlockGraph::CODE_LABEL);
506 E : successor.set_label(label);
507 E : EXPECT_TRUE(successor.has_label());
508 E : EXPECT_TRUE(successor.label() == label);
509 E : }
510 :
511 E : TEST_F(SuccessorTest, OpCodeToCondition) {
512 : struct TableEntry {
513 : uint16 op_code;
514 : Successor::Condition condition;
515 : };
516 :
517 : const TableEntry kOpCodeToConditionTable[] = {
518 E : { I_MOV, Successor::kInvalidCondition },
519 E : { I_JMP, Successor::kConditionTrue },
520 E : { I_JA, Successor::kConditionAbove },
521 E : { I_JAE, Successor::kConditionAboveOrEqual },
522 E : { I_JB, Successor::kConditionBelow },
523 E : { I_JBE, Successor::kConditionBelowOrEqual },
524 E : { I_JCXZ, Successor::kCounterIsZero },
525 E : { I_JECXZ, Successor::kCounterIsZero },
526 E : { I_JG, Successor::kConditionGreater },
527 E : { I_JGE, Successor::kConditionGreaterOrEqual },
528 E : { I_JL, Successor::kConditionLess },
529 E : { I_JLE, Successor::kConditionLessOrEqual },
530 E : { I_JNO, Successor::kConditionNotOverflow },
531 E : { I_JNP, Successor::kConditionNotParity },
532 E : { I_JNS, Successor::kConditionNotSigned },
533 E : { I_JNZ, Successor::kConditionNotEqual },
534 E : { I_JO, Successor::kConditionOverflow },
535 E : { I_JP, Successor::kConditionParity },
536 E : { I_JS, Successor::kConditionSigned },
537 E : { I_JZ, Successor::kConditionEqual },
538 E : { I_LOOP, Successor::kLoopTrue },
539 E : { I_LOOPNZ, Successor::kLoopIfNotEqual },
540 E : { I_LOOPZ, Successor::kLoopIfEqual },
541 : };
542 :
543 : // Four conditions do not have an corresponding instruction (the four symbolic
544 : // inverses kInverseCounterIsZero, kInverseLoop, kInverseLoopIfEqual, and
545 : // kInverseLoopIfNotEqual); two instructions map to kCounterIsZero; and we
546 : // test kInvalidCondition with MOV. So the total number of instructions we
547 : // expect is two less than the total number of branch types.
548 : COMPILE_ASSERT(
549 : arraysize(kOpCodeToConditionTable) == Successor::kMaxCondition - 2,
550 : unexpected_number_of_map_entries);
551 :
552 E : for (size_t i = 0; i < arraysize(kOpCodeToConditionTable); ++i) {
553 E : const TableEntry& entry = kOpCodeToConditionTable[i];
554 E : EXPECT_EQ(entry.condition, Successor::OpCodeToCondition(entry.op_code));
555 E : }
556 E : }
557 :
558 E : TEST_F(SuccessorTest, InvertCondition) {
559 : struct TableEntry {
560 : Successor::Condition original;
561 : Successor::Condition inverse;
562 : };
563 : static const TableEntry kConditionInversionTable[] = {
564 : { Successor::kConditionTrue, Successor::kInvalidCondition },
565 : { Successor::kConditionAbove, Successor::kConditionBelowOrEqual },
566 : { Successor::kConditionAboveOrEqual, Successor::kConditionBelow },
567 : { Successor::kConditionBelow, Successor::kConditionAboveOrEqual },
568 : { Successor::kConditionBelowOrEqual, Successor::kConditionAbove },
569 : { Successor::kConditionEqual, Successor::kConditionNotEqual },
570 : { Successor::kConditionGreater, Successor::kConditionLessOrEqual },
571 : { Successor::kConditionGreaterOrEqual, Successor::kConditionLess },
572 : { Successor::kConditionLess, Successor::kConditionGreaterOrEqual },
573 : { Successor::kConditionLessOrEqual, Successor::kConditionGreater },
574 : { Successor::kConditionNotEqual, Successor::kConditionEqual },
575 : { Successor::kConditionNotOverflow, Successor::kConditionOverflow },
576 : { Successor::kConditionNotParity, Successor::kConditionParity },
577 : { Successor::kConditionNotSigned, Successor::kConditionSigned },
578 : { Successor::kConditionOverflow, Successor::kConditionNotOverflow },
579 : { Successor::kConditionParity, Successor::kConditionNotParity },
580 : { Successor::kConditionSigned, Successor::kConditionNotSigned },
581 : { Successor::kCounterIsZero, Successor::kInverseCounterIsZero },
582 : { Successor::kLoopTrue, Successor::kInverseLoopTrue },
583 : { Successor::kLoopIfEqual, Successor::kInverseLoopIfEqual },
584 : { Successor::kLoopIfNotEqual, Successor::kInverseLoopIfNotEqual },
585 : { Successor::kInverseCounterIsZero, Successor::kCounterIsZero },
586 : { Successor::kInverseLoopTrue, Successor::kLoopTrue },
587 : { Successor::kInverseLoopIfEqual, Successor::kLoopIfEqual },
588 : { Successor::kInverseLoopIfNotEqual, Successor::kLoopIfNotEqual },
589 : };
590 :
591 : COMPILE_ASSERT(
592 : arraysize(kConditionInversionTable) == Successor::kMaxCondition,
593 : unexpected_number_of_inversion_table_entries);
594 :
595 E : for (size_t i = 0; i < arraysize(kConditionInversionTable); ++i) {
596 E : const TableEntry& entry = kConditionInversionTable[i];
597 E : EXPECT_EQ(entry.inverse, Successor::InvertCondition(entry.original));
598 E : }
599 E : }
600 :
601 : typedef BasicBlockTest InstructionTest;
602 :
603 E : TEST_F(InstructionTest, CallsNonReturningFunction) {
604 : // Create a returning code block.
605 E : BlockGraph::Block returning(0, BlockGraph::CODE_BLOCK, 1, "return");
606 :
607 : // Create a non-returning code block.
608 E : BlockGraph::Block non_returning(1, BlockGraph::CODE_BLOCK, 1, "non-return");
609 E : non_returning.set_attribute(BlockGraph::NON_RETURN_FUNCTION);
610 :
611 E : _DInst repr = {};
612 E : repr.opcode = I_CALL;
613 E : repr.meta = FC_CALL;
614 E : repr.ops[0].type = O_PC;
615 E : const uint8 kCallRelative[] = { 0xE8, 0xDE, 0xAD, 0xBE, 0xEF };
616 E : Instruction call_relative(repr, 0, sizeof(kCallRelative), kCallRelative);
617 :
618 : // Call the returning function directly.
619 : call_relative.SetReference(
620 : 1, BasicBlockReference(BlockGraph::RELATIVE_REF,
621 : BlockGraph::Reference::kMaximumSize,
622 E : &returning, 0, 0));
623 E : EXPECT_FALSE(call_relative.CallsNonReturningFunction());
624 :
625 : // Call the non-returning function directly.
626 : call_relative.SetReference(
627 : 1, BasicBlockReference(BlockGraph::RELATIVE_REF,
628 : BlockGraph::Reference::kMaximumSize,
629 E : &non_returning, 0, 0));
630 E : EXPECT_TRUE(call_relative.CallsNonReturningFunction());
631 :
632 : // Setup an indirect call via a static function pointer (for example, an
633 : // import table).
634 E : repr.ops[0].type = O_DISP;
635 : BlockGraph::Block function_pointer(
636 E : 2, BlockGraph::DATA_BLOCK, BlockGraph::Reference::kMaximumSize, "ptr");
637 E : const uint8 kCallIndirect[] = { 0xFF, 0x15, 0xDE, 0xAD, 0xBE, 0xEF };
638 E : Instruction call_indirect(repr, 0, sizeof(kCallIndirect), kCallIndirect);
639 : call_indirect.SetReference(
640 : 2, BasicBlockReference(BlockGraph::RELATIVE_REF,
641 : BlockGraph::Reference::kMaximumSize,
642 E : &function_pointer, 0, 0));
643 :
644 : // Call the returning function via the pointer.
645 : function_pointer.SetReference(
646 : 0, BlockGraph::Reference(BlockGraph::ABSOLUTE_REF,
647 : BlockGraph::Reference::kMaximumSize,
648 E : &returning, 0, 0));
649 E : EXPECT_FALSE(call_indirect.CallsNonReturningFunction());
650 :
651 : // Call the returning function via the pointer.
652 : function_pointer.SetReference(
653 : 0, BlockGraph::Reference(BlockGraph::ABSOLUTE_REF,
654 : BlockGraph::Reference::kMaximumSize,
655 E : &non_returning, 0, 0));
656 E : EXPECT_TRUE(call_indirect.CallsNonReturningFunction());
657 E : }
658 :
659 E : TEST_F(InstructionTest, FindOperandReference) {
660 E : BasicBlock::Instructions instructions;
661 E : BasicBlockAssembler assm(instructions.begin(), &instructions);
662 :
663 : {
664 : // Generate a dual-reference instruction.
665 : assm.mov(Operand(core::eax, core::ebx, core::kTimes4,
666 : Displacement(&basic_code_block_)),
667 E : Immediate(¯o_block_, 30));
668 E : const Instruction& inst = instructions.back();
669 :
670 E : BasicBlockReference ref0;
671 E : EXPECT_TRUE(inst.FindOperandReference(0, &ref0));
672 : EXPECT_EQ(BasicBlockReference::REFERRED_TYPE_BASIC_BLOCK,
673 E : ref0.referred_type());
674 E : EXPECT_EQ(&basic_code_block_, ref0.basic_block());
675 :
676 E : BasicBlockReference ref1;
677 E : EXPECT_TRUE(inst.FindOperandReference(1, &ref1));
678 E : EXPECT_EQ(BasicBlockReference::REFERRED_TYPE_BLOCK, ref1.referred_type());
679 E : EXPECT_EQ(¯o_block_, ref1.block());
680 :
681 E : BasicBlockReference ignore;
682 E : EXPECT_FALSE(inst.FindOperandReference(2, &ignore));
683 E : EXPECT_FALSE(inst.FindOperandReference(3, &ignore));
684 : }
685 :
686 : {
687 : // Generate a singe-reference instruction with an 8-bit immediate.
688 : assm.mov(Operand(core::eax, core::ebx, core::kTimes4,
689 : Displacement(&basic_code_block_)),
690 E : Immediate(0x10, core::kSize8Bit));
691 :
692 E : const Instruction& inst = instructions.back();
693 :
694 E : BasicBlockReference ref0;
695 E : EXPECT_TRUE(inst.FindOperandReference(0, &ref0));
696 : EXPECT_EQ(BasicBlockReference::REFERRED_TYPE_BASIC_BLOCK,
697 E : ref0.referred_type());
698 E : EXPECT_EQ(&basic_code_block_, ref0.basic_block());
699 :
700 E : BasicBlockReference ignore;
701 E : EXPECT_FALSE(inst.FindOperandReference(1, &ignore));
702 E : EXPECT_FALSE(inst.FindOperandReference(2, &ignore));
703 E : EXPECT_FALSE(inst.FindOperandReference(3, &ignore));
704 : }
705 E : }
706 :
707 : } // namespace block_graph
|