1 : // Copyright 2013 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 : // Unittests for liveness analysis.
16 :
17 : #include "syzygy/block_graph/analysis/liveness_analysis.h"
18 :
19 : #include "base/bind.h"
20 : #include "gmock/gmock.h"
21 : #include "gtest/gtest.h"
22 : #include "syzygy/block_graph/basic_block_assembler.h"
23 : #include "syzygy/block_graph/analysis/liveness_analysis_internal.h"
24 :
25 : #include "mnemonics.h" // NOLINT
26 :
27 : namespace block_graph {
28 : namespace analysis {
29 :
30 : namespace {
31 :
32 : typedef BasicBlockSubGraph::BBCollection BBCollection;
33 : typedef block_graph::analysis::LivenessAnalysis::State State;
34 : typedef block_graph::analysis::LivenessAnalysis::StateHelper StateHelper;
35 : typedef block_graph::BasicBlockSubGraph::BasicBlock BasicBlock;
36 : typedef block_graph::BasicBlockSubGraph::BasicBlock::Instructions Instructions;
37 : typedef block_graph::BasicBlockSubGraph::BasicBlock::Successors Successors;
38 : typedef block_graph::BasicBlockSubGraph::BasicCodeBlock BasicCodeBlock;
39 : typedef block_graph::BasicBlockSubGraph::BlockDescription BlockDescription;
40 :
41 : // _asm mov eax, 0
42 : const uint8 kMovEaxZero[5] = { 0xB8, 0x00, 0x00, 0x00, 0x00 };
43 : // _asm mov ebx, 0
44 : const uint8 kMovEbxZero[5] = { 0xBB, 0x00, 0x00, 0x00, 0x00 };
45 : // _asm mov ecx, 0
46 : const uint8 kMovEcxZero[5] = { 0xB9, 0x00, 0x00, 0x00, 0x00 };
47 : // _asm mov edx, 0
48 : const uint8 kMovEdxZero[5] = { 0xBA, 0x00, 0x00, 0x00, 0x00 };
49 : // _asm mov esi, 0
50 : const uint8 kMovEsiZero[5] = { 0xBE, 0x00, 0x00, 0x00, 0x00 };
51 : // _asm mov edi, 0
52 : const uint8 kMovEdiZero[5] = { 0xBF, 0x00, 0x00, 0x00, 0x00 };
53 : // _asm mov esp, 0
54 : const uint8 kMovEspZero[5] = { 0xBC, 0x00, 0x00, 0x00, 0x00 };
55 : // _asm mov ebp, 0
56 : const uint8 kMovEbpZero[5] = { 0xBD, 0x00, 0x00, 0x00, 0x00 };
57 : // _asm cmp eax, ebx
58 : const uint8 kCmpEaxEbx[2] = { 0x3B, 0xC3 };
59 : // _asm mov ax, 0
60 : const uint8 kMovAxZero[4] = { 0x66, 0xB8, 0x00, 0x00 };
61 : // _asm mov al, 0
62 : const uint8 kMovAlZero[2] = { 0xB0, 0x00 };
63 :
64 : class LivenessAnalysisTest : public testing::Test {
65 : public:
66 : LivenessAnalysisTest();
67 :
68 E : inline bool is_live(const core::Register& reg) const {
69 E : return state_.IsLive(reg);
70 E : }
71 E : inline bool are_arithmetic_flags_live() const {
72 E : return state_.AreArithmeticFlagsLive();
73 E : }
74 :
75 : template<size_t N>
76 : void AddInstructionFromBuffer(const uint8 (& data)[N]);
77 : void DefineAllRegisters();
78 : void AnalyzeInstructionsWithoutReset();
79 : void AnalyzeInstructions();
80 :
81 : template<size_t N>
82 : void AnalyzeSingleInstructionFromBuffer(const uint8 (& data)[N]);
83 :
84 : bool CheckCarryFlagInstruction(bool expect_on, bool expect_off);
85 :
86 : void AddSuccessorBetween(Successor::Condition condition,
87 : BasicCodeBlock* from,
88 : BasicCodeBlock* to);
89 :
90 : protected:
91 : BlockGraph block_graph_;
92 : BlockGraph::Block* test_block_;
93 : BasicBlock::Instructions instructions_;
94 : BasicBlockAssembler asm_;
95 : LivenessAnalysis liveness_;
96 : LivenessAnalysis::State state_;
97 : };
98 :
99 : LivenessAnalysisTest::LivenessAnalysisTest()
100 : : testing::Test(),
101 : test_block_(NULL),
102 : instructions_(),
103 : asm_(instructions_.end(), &instructions_),
104 : liveness_(),
105 E : state_() {
106 E : test_block_ = block_graph_.AddBlock(BlockGraph::CODE_BLOCK, 10, "test block");
107 E : }
108 :
109 : template<size_t N>
110 E : void LivenessAnalysisTest::AddInstructionFromBuffer(const uint8 (& data)[N]) {
111 : // Decode an instruction and append it to basicblock_.
112 E : DCHECK_GT(core::AssemblerImpl::kMaxInstructionLength, N);
113 :
114 E : block_graph::Instruction temp;
115 E : ASSERT_TRUE(block_graph::Instruction::FromBuffer(&data[0], N, &temp));
116 :
117 : // Expect to decode the entire buffer.
118 E : ASSERT_TRUE(temp.size() == N);
119 :
120 : // Append this instruction to the basic block.
121 E : instructions_.push_back(temp);
122 E : }
123 :
124 E : void LivenessAnalysisTest::DefineAllRegisters() {
125 : // Inserts instructions into basicblock_ so all registers are defined.
126 E : AddInstructionFromBuffer(kMovEaxZero);
127 E : AddInstructionFromBuffer(kMovEbxZero);
128 E : AddInstructionFromBuffer(kMovEcxZero);
129 E : AddInstructionFromBuffer(kMovEdxZero);
130 E : AddInstructionFromBuffer(kMovEsiZero);
131 E : AddInstructionFromBuffer(kMovEdiZero);
132 E : AddInstructionFromBuffer(kMovEspZero);
133 E : AddInstructionFromBuffer(kMovEbpZero);
134 :
135 : // Define arithmetic flags.
136 E : AddInstructionFromBuffer(kCmpEaxEbx);
137 E : }
138 :
139 E : void LivenessAnalysisTest::AnalyzeInstructionsWithoutReset() {
140 : // Perform a backward liveness analysis on instructions in basicblock_.
141 : // Results are kept in 'state_' and may be accessed through IsLive and
142 : // AreArithmeticFlagsLive.
143 E : Instructions::reverse_iterator instr_iter = instructions_.rbegin();
144 E : for (; instr_iter != instructions_.rend(); ++instr_iter) {
145 E : const Instruction& instr = *instr_iter;
146 E : liveness_.PropagateBackward(instr, &state_);
147 E : }
148 E : }
149 :
150 E : void LivenessAnalysisTest::AnalyzeInstructions() {
151 E : LivenessAnalysis::StateHelper::SetAll(&state_);
152 E : AnalyzeInstructionsWithoutReset();
153 E : }
154 :
155 : template<size_t N>
156 : void LivenessAnalysisTest::AnalyzeSingleInstructionFromBuffer(
157 E : const uint8 (& data)[N]) {
158 : // This function creates a basic block with an instruction under test,
159 : // followed by instructions to define all registers and flags. This way, the
160 : // analysis may assume everything was dead before the instruction.
161 E : instructions_.clear();
162 E : StateHelper::SetAll(&state_);
163 :
164 E : AddInstructionFromBuffer(data);
165 E : DefineAllRegisters();
166 E : AnalyzeInstructions();
167 E : }
168 :
169 : bool LivenessAnalysisTest::CheckCarryFlagInstruction(
170 E : bool expect_on, bool expect_off) {
171 E : LivenessAnalysis::State flags;
172 E : StateHelper::Clear(&flags);
173 E : StateHelper::SetFlags(~(D_CF), &state_);
174 :
175 : // Try with the carry flag on.
176 E : StateHelper::Clear(&state_);
177 E : StateHelper::SetFlags(D_CF, &state_);
178 E : AnalyzeInstructionsWithoutReset();
179 E : StateHelper::Subtract(flags, &state_);
180 E : if (are_arithmetic_flags_live() != expect_on)
181 i : return false;
182 :
183 : // Try with the carry flag off.
184 E : StateHelper::Clear(&state_);
185 E : AnalyzeInstructionsWithoutReset();
186 E : StateHelper::Subtract(flags, &state_);
187 E : if (are_arithmetic_flags_live() != expect_off)
188 i : return false;
189 :
190 E : return true;
191 E : }
192 :
193 : void LivenessAnalysisTest::AddSuccessorBetween(Successor::Condition condition,
194 : BasicCodeBlock* from,
195 E : BasicCodeBlock* to) {
196 : from->successors().push_back(
197 : Successor(condition,
198 : BasicBlockReference(BlockGraph::RELATIVE_REF,
199 : BlockGraph::Reference::kMaximumSize,
200 : to),
201 E : 0));
202 E : }
203 :
204 E : TEST(LivenessAnalysisStateTest, StateRegisterMaskOperations) {
205 : // On creation, a state assumes all registers are alive.
206 E : State state_full;
207 E : EXPECT_TRUE(StateHelper::IsSet(state_full, StateHelper::REGBITS_ALL));
208 E : EXPECT_TRUE(StateHelper::IsSet(state_full, StateHelper::REGBITS_AX));
209 :
210 : // The Clear operation should not keep any register partially defined.
211 E : State state_empty;
212 E : StateHelper::Clear(&state_empty);
213 : EXPECT_FALSE(
214 E : StateHelper::IsPartiallySet(state_empty, StateHelper::REGBITS_ALL));
215 : EXPECT_FALSE(
216 E : StateHelper::IsPartiallySet(state_empty, StateHelper::REGBITS_AX));
217 :
218 : // Test sub-registers definition.
219 E : State state_ax;
220 E : State state_cx;
221 E : StateHelper::Clear(&state_ax);
222 E : StateHelper::Clear(&state_cx);
223 E : StateHelper::Set(StateHelper::REGBITS_AX, &state_ax);
224 E : StateHelper::Set(StateHelper::REGBITS_CX, &state_cx);
225 E : EXPECT_TRUE(StateHelper::IsPartiallySet(state_ax, StateHelper::REGBITS_EAX));
226 E : EXPECT_TRUE(StateHelper::IsSet(state_ax, StateHelper::REGBITS_AL));
227 E : EXPECT_TRUE(StateHelper::IsSet(state_ax, StateHelper::REGBITS_AH));
228 E : EXPECT_TRUE(StateHelper::IsSet(state_ax, StateHelper::REGBITS_AX));
229 E : EXPECT_TRUE(StateHelper::IsPartiallySet(state_cx, StateHelper::REGBITS_ECX));
230 E : EXPECT_TRUE(StateHelper::IsSet(state_cx, StateHelper::REGBITS_CL));
231 E : EXPECT_TRUE(StateHelper::IsSet(state_cx, StateHelper::REGBITS_CH));
232 E : EXPECT_TRUE(StateHelper::IsSet(state_cx, StateHelper::REGBITS_CX));
233 :
234 : // Test IsLive operation.
235 E : EXPECT_TRUE(state_full.IsLive(core::eax));
236 E : EXPECT_TRUE(state_full.IsLive(core::ecx));
237 E : EXPECT_FALSE(state_empty.IsLive(core::eax));
238 E : EXPECT_FALSE(state_empty.IsLive(core::ecx));
239 E : EXPECT_TRUE(state_ax.IsLive(core::eax));
240 E : EXPECT_FALSE(state_ax.IsLive(core::ecx));
241 E : EXPECT_FALSE(state_cx.IsLive(core::eax));
242 E : EXPECT_TRUE(state_cx.IsLive(core::ecx));
243 :
244 : // Test copy constructor.
245 E : State state_copy(state_ax);
246 : EXPECT_TRUE(
247 E : StateHelper::IsPartiallySet(state_copy, StateHelper::REGBITS_EAX));
248 E : EXPECT_TRUE(StateHelper::IsSet(state_copy, StateHelper::REGBITS_AL));
249 E : EXPECT_TRUE(StateHelper::IsSet(state_copy, StateHelper::REGBITS_AH));
250 E : EXPECT_TRUE(StateHelper::IsSet(state_copy, StateHelper::REGBITS_AX));
251 :
252 : // Test Copy operation.
253 E : State state_copy_ax;
254 E : StateHelper::Copy(state_ax, &state_copy_ax);
255 : EXPECT_TRUE(
256 E : StateHelper::IsPartiallySet(state_copy_ax, StateHelper::REGBITS_EAX));
257 E : EXPECT_TRUE(StateHelper::IsSet(state_copy_ax, StateHelper::REGBITS_AL));
258 E : EXPECT_TRUE(StateHelper::IsSet(state_copy_ax, StateHelper::REGBITS_AH));
259 E : EXPECT_TRUE(StateHelper::IsSet(state_copy_ax, StateHelper::REGBITS_AX));
260 :
261 : // Test Union operation.
262 E : State state_merged;
263 E : StateHelper::Clear(&state_merged);
264 : EXPECT_FALSE(
265 E : StateHelper::IsPartiallySet(state_merged, StateHelper::REGBITS_AX));
266 : EXPECT_FALSE(
267 E : StateHelper::IsPartiallySet(state_merged, StateHelper::REGBITS_CX));
268 E : StateHelper::Union(state_ax, &state_merged);
269 : EXPECT_TRUE(
270 E : StateHelper::IsPartiallySet(state_merged, StateHelper::REGBITS_AX));
271 : EXPECT_FALSE(
272 E : StateHelper::IsPartiallySet(state_merged, StateHelper::REGBITS_CX));
273 E : StateHelper::Union(state_cx, &state_merged);
274 : EXPECT_TRUE(
275 E : StateHelper::IsPartiallySet(state_merged, StateHelper::REGBITS_AX));
276 : EXPECT_TRUE(
277 E : StateHelper::IsPartiallySet(state_merged, StateHelper::REGBITS_CX));
278 :
279 : // Test Subtract operation
280 E : StateHelper::Subtract(state_ax, &state_merged);
281 : EXPECT_FALSE(
282 E : StateHelper::IsPartiallySet(state_merged, StateHelper::REGBITS_AX));
283 : EXPECT_TRUE(
284 E : StateHelper::IsPartiallySet(state_merged, StateHelper::REGBITS_CX));
285 E : StateHelper::Subtract(state_cx, &state_merged);
286 : EXPECT_FALSE(
287 E : StateHelper::IsPartiallySet(state_merged, StateHelper::REGBITS_AX));
288 : EXPECT_FALSE(
289 E : StateHelper::IsPartiallySet(state_merged, StateHelper::REGBITS_CX));
290 E : }
291 :
292 E : TEST(LivenessAnalysisStateTest, StateFlagsMaskOperations) {
293 : // On creation, a state assumes all flags are alive.
294 E : State state_full;
295 E : EXPECT_TRUE(state_full.AreArithmeticFlagsLive());
296 :
297 : // The Clear operation should not keep any flags alive.
298 E : State state_empty;
299 E : StateHelper::Clear(&state_empty);
300 E : EXPECT_FALSE(state_empty.AreArithmeticFlagsLive());
301 :
302 : // Partially defined flags must be considered alive.
303 E : State state_flagA;
304 E : State state_flagB;
305 E : State state_flagC;
306 E : StateHelper::Clear(&state_flagA);
307 E : StateHelper::Clear(&state_flagB);
308 E : StateHelper::SetFlags(0xF0F0, &state_flagA);
309 E : StateHelper::SetFlags(0xFFFF, &state_flagB);
310 :
311 E : EXPECT_TRUE(state_flagA.AreArithmeticFlagsLive());
312 E : EXPECT_TRUE(state_flagB.AreArithmeticFlagsLive());
313 :
314 : // Test Subtract operation.
315 E : State state_flag_ari1;
316 E : State state_flag_ari2;
317 E : StateHelper::Clear(&state_flag_ari1);
318 E : StateHelper::Clear(&state_flag_ari2);
319 E : StateHelper::SetFlags(D_ZF | D_SF | D_CF, &state_flag_ari1);
320 E : StateHelper::SetFlags(D_OF | D_PF | D_AF, &state_flag_ari2);
321 :
322 E : EXPECT_TRUE(state_flag_ari1.AreArithmeticFlagsLive());
323 E : EXPECT_TRUE(state_flag_ari2.AreArithmeticFlagsLive());
324 :
325 E : State state_merged;
326 E : EXPECT_TRUE(state_merged.AreArithmeticFlagsLive());
327 E : StateHelper::Subtract(state_flag_ari1, &state_merged);
328 E : EXPECT_TRUE(state_merged.AreArithmeticFlagsLive());
329 E : StateHelper::Subtract(state_flag_ari2, &state_merged);
330 E : EXPECT_FALSE(state_merged.AreArithmeticFlagsLive());
331 E : }
332 :
333 E : TEST_F(LivenessAnalysisTest, Mov1Analysis) {
334 E : asm_.mov(core::eax, Immediate(10));
335 E : asm_.mov(core::ecx, core::ebx);
336 E : AnalyzeInstructions();
337 E : EXPECT_FALSE(is_live(core::eax));
338 E : EXPECT_FALSE(is_live(core::ax));
339 E : EXPECT_FALSE(is_live(core::ah));
340 E : EXPECT_TRUE(is_live(core::ebx));
341 E : EXPECT_TRUE(is_live(core::bx));
342 E : EXPECT_TRUE(is_live(core::bl));
343 E : EXPECT_FALSE(is_live(core::ecx));
344 E : }
345 :
346 E : TEST_F(LivenessAnalysisTest, Mov2Analysis) {
347 E : asm_.mov(core::eax, core::ebx);
348 E : asm_.mov(core::edx, Immediate(10));
349 E : asm_.mov(core::ecx, Immediate(test_block_, 0));
350 E : AnalyzeInstructions();
351 E : EXPECT_FALSE(is_live(core::eax));
352 E : EXPECT_FALSE(is_live(core::ax));
353 E : EXPECT_FALSE(is_live(core::ah));
354 E : EXPECT_TRUE(is_live(core::ebx));
355 E : EXPECT_TRUE(is_live(core::bx));
356 E : EXPECT_TRUE(is_live(core::bl));
357 E : EXPECT_FALSE(is_live(core::ecx));
358 E : EXPECT_FALSE(is_live(core::edx));
359 E : }
360 :
361 E : TEST_F(LivenessAnalysisTest, DefineAllRegisters) {
362 : // Validate the tester by defining all registers and using none.
363 E : DefineAllRegisters();
364 E : AnalyzeInstructions();
365 E : EXPECT_FALSE(is_live(core::eax));
366 E : EXPECT_FALSE(is_live(core::ax));
367 E : EXPECT_FALSE(is_live(core::al));
368 E : EXPECT_FALSE(is_live(core::ah));
369 E : EXPECT_FALSE(is_live(core::ebx));
370 E : EXPECT_FALSE(is_live(core::bx));
371 E : EXPECT_FALSE(is_live(core::bl));
372 E : EXPECT_FALSE(is_live(core::bh));
373 E : EXPECT_FALSE(is_live(core::ecx));
374 E : EXPECT_FALSE(is_live(core::cx));
375 E : EXPECT_FALSE(is_live(core::cl));
376 E : EXPECT_FALSE(is_live(core::ch));
377 E : EXPECT_FALSE(is_live(core::edx));
378 E : EXPECT_FALSE(is_live(core::dx));
379 E : EXPECT_FALSE(is_live(core::dl));
380 E : EXPECT_FALSE(is_live(core::dh));
381 E : EXPECT_FALSE(is_live(core::esi));
382 E : EXPECT_FALSE(is_live(core::si));
383 E : EXPECT_FALSE(is_live(core::edi));
384 E : EXPECT_FALSE(is_live(core::di));
385 E : EXPECT_FALSE(are_arithmetic_flags_live());
386 E : }
387 :
388 E : TEST_F(LivenessAnalysisTest, Defs1Analysis) {
389 : // Validate the tester by defining all registers and using some of them.
390 E : AddInstructionFromBuffer(kMovEaxZero);
391 E : AddInstructionFromBuffer(kMovEcxZero);
392 E : AddInstructionFromBuffer(kMovEsiZero);
393 E : AnalyzeInstructions();
394 E : EXPECT_FALSE(is_live(core::eax));
395 E : EXPECT_FALSE(is_live(core::ax));
396 E : EXPECT_FALSE(is_live(core::ah));
397 E : EXPECT_TRUE(is_live(core::ebx));
398 E : EXPECT_TRUE(is_live(core::bx));
399 E : EXPECT_TRUE(is_live(core::bl));
400 E : EXPECT_FALSE(is_live(core::ecx));
401 E : EXPECT_FALSE(is_live(core::cx));
402 E : EXPECT_FALSE(is_live(core::cl));
403 E : EXPECT_TRUE(is_live(core::edx));
404 E : EXPECT_TRUE(is_live(core::dx));
405 E : EXPECT_TRUE(is_live(core::dl));
406 E : EXPECT_FALSE(is_live(core::esi));
407 E : EXPECT_FALSE(is_live(core::si));
408 E : EXPECT_TRUE(is_live(core::edi));
409 E : EXPECT_TRUE(is_live(core::di));
410 E : }
411 :
412 E : TEST_F(LivenessAnalysisTest, Defs2Analysis) {
413 : // Validate the tester by defining all registers and using some of them.
414 E : AddInstructionFromBuffer(kMovEbxZero);
415 E : AddInstructionFromBuffer(kMovEdxZero);
416 E : AddInstructionFromBuffer(kMovEdiZero);
417 E : AnalyzeInstructions();
418 E : EXPECT_TRUE(is_live(core::eax));
419 E : EXPECT_TRUE(is_live(core::ax));
420 E : EXPECT_TRUE(is_live(core::al));
421 E : EXPECT_FALSE(is_live(core::ebx));
422 E : EXPECT_FALSE(is_live(core::bx));
423 E : EXPECT_FALSE(is_live(core::bh));
424 E : EXPECT_TRUE(is_live(core::ecx));
425 E : EXPECT_TRUE(is_live(core::cx));
426 E : EXPECT_TRUE(is_live(core::cl));
427 E : EXPECT_FALSE(is_live(core::edx));
428 E : EXPECT_FALSE(is_live(core::dx));
429 E : EXPECT_FALSE(is_live(core::dl));
430 E : EXPECT_TRUE(is_live(core::esi));
431 E : EXPECT_TRUE(is_live(core::si));
432 E : EXPECT_FALSE(is_live(core::edi));
433 E : EXPECT_FALSE(is_live(core::di));
434 E : }
435 :
436 E : TEST_F(LivenessAnalysisTest, Analysis16Bit) {
437 E : AddInstructionFromBuffer(kMovAxZero);
438 E : AnalyzeInstructions();
439 E : EXPECT_TRUE(is_live(core::eax));
440 E : EXPECT_FALSE(is_live(core::ax));
441 E : EXPECT_FALSE(is_live(core::al));
442 E : EXPECT_FALSE(is_live(core::ah));
443 E : }
444 :
445 E : TEST_F(LivenessAnalysisTest, Analysis8Bit) {
446 E : AddInstructionFromBuffer(kMovAlZero);
447 E : AnalyzeInstructions();
448 E : EXPECT_TRUE(is_live(core::eax));
449 E : EXPECT_TRUE(is_live(core::ax));
450 E : EXPECT_FALSE(is_live(core::al));
451 E : EXPECT_TRUE(is_live(core::ah));
452 E : }
453 :
454 E : TEST_F(LivenessAnalysisTest, OperandTypeLeft) {
455 : // Validate the support of all DiStorm operand types (as first operand).
456 : // _asm add eax, ecx
457 : static const uint8 kOpReg1[] = { 0x03, 0xC1 };
458 E : AnalyzeSingleInstructionFromBuffer(kOpReg1);
459 E : EXPECT_TRUE(is_live(core::eax));
460 E : EXPECT_FALSE(is_live(core::ebx));
461 E : EXPECT_TRUE(is_live(core::ecx));
462 E : EXPECT_FALSE(is_live(core::edx));
463 :
464 : // _asm add [eax], ecx
465 : static const uint8 kOpSmem[] = { 0x01, 0x08 };
466 E : AnalyzeSingleInstructionFromBuffer(kOpSmem);
467 E : EXPECT_TRUE(is_live(core::eax));
468 E : EXPECT_FALSE(is_live(core::ebx));
469 E : EXPECT_TRUE(is_live(core::ecx));
470 E : EXPECT_FALSE(is_live(core::edx));
471 :
472 : // _asm add [eax + 42], ecx
473 : static const uint8 kOpSmemOffet[] = { 0x01, 0x48, 0x2A };
474 E : AnalyzeSingleInstructionFromBuffer(kOpSmemOffet);
475 E : EXPECT_TRUE(is_live(core::eax));
476 E : EXPECT_FALSE(is_live(core::ebx));
477 E : EXPECT_TRUE(is_live(core::ecx));
478 E : EXPECT_FALSE(is_live(core::edx));
479 :
480 : // _asm add [eax + ebx*2 + 42], ecx
481 : static const uint8 kOpMemOffset[] = { 0x01, 0x4C, 0x58, 0x2A };
482 E : AnalyzeSingleInstructionFromBuffer(kOpMemOffset);
483 E : EXPECT_TRUE(is_live(core::eax));
484 E : EXPECT_TRUE(is_live(core::ebx));
485 E : EXPECT_TRUE(is_live(core::ecx));
486 E : EXPECT_FALSE(is_live(core::edx));
487 :
488 : // _asm add DWORD PTR [X], ecx
489 : static const uint8 kOpDispl[] = { 0x01, 0x0D, 0x80, 0x1E, 0xF2, 0x00 };
490 E : AnalyzeSingleInstructionFromBuffer(kOpDispl);
491 E : EXPECT_FALSE(is_live(core::eax));
492 E : EXPECT_FALSE(is_live(core::ebx));
493 E : EXPECT_TRUE(is_live(core::ecx));
494 E : EXPECT_FALSE(is_live(core::edx));
495 E : }
496 :
497 E : TEST_F(LivenessAnalysisTest, OperandTypeRight) {
498 : // Validate the support of all DiStorm operand types (as second operand).
499 : // _asm add ecx, 1
500 : static const uint8 kOpReg1[] = { 0x83, 0xC1, 0x01 };
501 E : AnalyzeSingleInstructionFromBuffer(kOpReg1);
502 E : EXPECT_FALSE(is_live(core::eax));
503 E : EXPECT_FALSE(is_live(core::ebx));
504 E : EXPECT_TRUE(is_live(core::ecx));
505 E : EXPECT_FALSE(is_live(core::edx));
506 :
507 : // _asm add ecx, eax
508 : static const uint8 kOpReg2[] = { 0x03, 0xC8 };
509 E : AnalyzeSingleInstructionFromBuffer(kOpReg2);
510 E : EXPECT_TRUE(is_live(core::eax));
511 E : EXPECT_FALSE(is_live(core::ebx));
512 E : EXPECT_TRUE(is_live(core::ecx));
513 E : EXPECT_FALSE(is_live(core::edx));
514 :
515 : // _asm add ecx, [eax]
516 : static const uint8 kOpSmem[] = { 0x03, 0x08 };
517 E : AnalyzeSingleInstructionFromBuffer(kOpSmem);
518 E : EXPECT_TRUE(is_live(core::eax));
519 E : EXPECT_FALSE(is_live(core::ebx));
520 E : EXPECT_TRUE(is_live(core::ecx));
521 E : EXPECT_FALSE(is_live(core::edx));
522 :
523 : // _asm add ecx, [eax + 42]
524 : static const uint8 kOpSmemOffet[] = { 0x03, 0x48, 0x2A };
525 E : AnalyzeSingleInstructionFromBuffer(kOpSmemOffet);
526 E : EXPECT_TRUE(is_live(core::eax));
527 E : EXPECT_FALSE(is_live(core::ebx));
528 E : EXPECT_TRUE(is_live(core::ecx));
529 E : EXPECT_FALSE(is_live(core::edx));
530 :
531 : // _asm add ecx, [eax + ebx*2 + 42]
532 : static const uint8 kOpMemOffset[] = { 0x03, 0x4C, 0x58, 0x2A };
533 E : AnalyzeSingleInstructionFromBuffer(kOpMemOffset);
534 E : EXPECT_TRUE(is_live(core::eax));
535 E : EXPECT_TRUE(is_live(core::ebx));
536 E : EXPECT_TRUE(is_live(core::ecx));
537 E : EXPECT_FALSE(is_live(core::edx));
538 :
539 : // _asm add ecx, DWORD PTR [X]
540 : static const uint8 kOpDispl[] = { 0x03, 0x0D, 0x80, 0x1E, 0x27, 0x00 };
541 E : AnalyzeSingleInstructionFromBuffer(kOpDispl);
542 E : EXPECT_FALSE(is_live(core::eax));
543 E : EXPECT_FALSE(is_live(core::ebx));
544 E : EXPECT_TRUE(is_live(core::ecx));
545 E : EXPECT_FALSE(is_live(core::edx));
546 E : }
547 :
548 E : TEST_F(LivenessAnalysisTest, InstructionWithoutDefine) {
549 : // Validate instructions that fully overwrite and use the destination.
550 : // _asm cmp eax, [ecx]
551 : static const uint8 kCmp[] = { 0x3B, 0x01 };
552 E : AnalyzeSingleInstructionFromBuffer(kCmp);
553 E : EXPECT_TRUE(is_live(core::eax));
554 E : EXPECT_TRUE(is_live(core::ecx));
555 :
556 : // _asm test ebx, [edx+12]
557 : static const uint8 kTest[] = { 0x85, 0x5A, 0x0C };
558 E : AnalyzeSingleInstructionFromBuffer(kTest);
559 E : EXPECT_TRUE(is_live(core::ebx));
560 E : EXPECT_TRUE(is_live(core::edx));
561 E : }
562 :
563 E : TEST_F(LivenessAnalysisTest, InstructionsWithDefine) {
564 : // Validate instructions that fully overwrite the destination.
565 : // _asm mov ebx, [edx+12]
566 : static const uint8 kCmp[] = { 0x8B, 0x5A, 0x0C };
567 E : AnalyzeSingleInstructionFromBuffer(kCmp);
568 E : EXPECT_FALSE(is_live(core::ebx));
569 E : EXPECT_TRUE(is_live(core::edx));
570 :
571 : // _asm lea ebx, [edx+12]
572 : static const uint8 kTest[] = { 0x8D, 0x5A, 0x0C };
573 E : AnalyzeSingleInstructionFromBuffer(kTest);
574 E : EXPECT_FALSE(is_live(core::ebx));
575 E : EXPECT_TRUE(is_live(core::edx));
576 E : }
577 :
578 E : TEST_F(LivenessAnalysisTest, InstructionsWithPartialDefine) {
579 : // Registers partially defined must be considered alive.
580 : // _asm mov bl, dl
581 : static const uint8 kCmp[] = { 0xB3, 0x0C };
582 : // _asm mov DWORD PTR [X], ebx
583 : static const uint8 kStore[] = { 0x89, 0x1D, 0x80, 0x1E, 0x10, 0x01 };
584 E : AddInstructionFromBuffer(kCmp);
585 E : AddInstructionFromBuffer(kStore);
586 E : AnalyzeInstructions();
587 :
588 E : EXPECT_TRUE(is_live(core::ebx));
589 E : EXPECT_TRUE(is_live(core::bx));
590 E : EXPECT_FALSE(is_live(core::bl));
591 E : EXPECT_TRUE(is_live(core::bh));
592 :
593 E : EXPECT_TRUE(is_live(core::edx));
594 E : EXPECT_TRUE(is_live(core::dx));
595 E : EXPECT_TRUE(is_live(core::dl));
596 E : EXPECT_TRUE(is_live(core::dh));
597 E : }
598 :
599 E : TEST_F(LivenessAnalysisTest, InstructionsWithPartialDefineAll) {
600 : static const uint8 kMovAl[] = { 0xB0, 0x00 };
601 : static const uint8 kMovBl[] = { 0xB1, 0x00 };
602 : static const uint8 kMovCl[] = { 0xB2, 0x00 };
603 : static const uint8 kMovDl[] = { 0xB3, 0x00 };
604 : static const uint8 kMovAh[] = { 0xB4, 0x00 };
605 : static const uint8 kMovBh[] = { 0xB7, 0x00 };
606 : static const uint8 kMovCh[] = { 0xB5, 0x00 };
607 : static const uint8 kMovDh[] = { 0xB6, 0x00 };
608 : static const uint8 kMovAx[] = { 0x66, 0xB8, 0x00, 0x00 };
609 : static const uint8 kMovBx[] = { 0x66, 0xBB, 0x00, 0x00 };
610 : static const uint8 kMovCx[] = { 0x66, 0xB9, 0x00, 0x00 };
611 : static const uint8 kMovDx[] = { 0x66, 0xBA, 0x00, 0x00 };
612 : static const uint8 kMovSi[] = { 0x66, 0xBE, 0x00, 0x00 };
613 : static const uint8 kMovDi[] = { 0x66, 0xBF, 0x00, 0x00 };
614 : static const uint8 kMovSp[] = { 0x66, 0xBC, 0x00, 0x00 };
615 : static const uint8 kMovBp[] = { 0x66, 0xBD, 0x00, 0x00 };
616 :
617 : // 8-bit partial registers.
618 E : AddInstructionFromBuffer(kMovAl);
619 E : AddInstructionFromBuffer(kMovBl);
620 E : AddInstructionFromBuffer(kMovCl);
621 E : AddInstructionFromBuffer(kMovDl);
622 :
623 E : AddInstructionFromBuffer(kMovAh);
624 E : AddInstructionFromBuffer(kMovBh);
625 E : AddInstructionFromBuffer(kMovCh);
626 E : AddInstructionFromBuffer(kMovDh);
627 :
628 : // 16-bit partial registers.
629 E : AddInstructionFromBuffer(kMovAx);
630 E : AddInstructionFromBuffer(kMovBx);
631 E : AddInstructionFromBuffer(kMovCx);
632 E : AddInstructionFromBuffer(kMovDx);
633 :
634 E : AddInstructionFromBuffer(kMovSi);
635 E : AddInstructionFromBuffer(kMovDi);
636 E : AddInstructionFromBuffer(kMovSp);
637 E : AddInstructionFromBuffer(kMovBp);
638 :
639 E : AnalyzeInstructions();
640 :
641 E : EXPECT_TRUE(is_live(core::eax));
642 E : EXPECT_TRUE(is_live(core::ecx));
643 E : EXPECT_TRUE(is_live(core::edx));
644 E : EXPECT_TRUE(is_live(core::eax));
645 E : EXPECT_TRUE(is_live(core::esi));
646 E : EXPECT_TRUE(is_live(core::edi));
647 E : EXPECT_TRUE(is_live(core::esp));
648 E : EXPECT_TRUE(is_live(core::ebp));
649 E : }
650 :
651 E : TEST_F(LivenessAnalysisTest, ArithmeticUnaryInstructions) {
652 : // _asm dec eax
653 : static const uint8 kDec1[] = { 0x48 };
654 E : AnalyzeSingleInstructionFromBuffer(kDec1);
655 E : EXPECT_TRUE(is_live(core::eax));
656 :
657 : // _asm dec [ebx + 1]
658 : static const uint8 kDec2[] = { 0xFE, 0x4B, 0x01 };
659 E : AnalyzeSingleInstructionFromBuffer(kDec2);
660 E : EXPECT_TRUE(is_live(core::ebx));
661 :
662 : // _asm dec [esi + ebx*2 + 1]
663 : static const uint8 kDec3[] = { 0xFE, 0x4C, 0x5E, 0x01 };
664 E : AnalyzeSingleInstructionFromBuffer(kDec3);
665 E : EXPECT_TRUE(is_live(core::esi));
666 E : EXPECT_TRUE(is_live(core::ebx));
667 :
668 : // _asm dec WORD PTR [X]
669 : static const uint8 kDec4[] = { 0x66, 0xFF, 0x0D, 0x80, 0x1E, 0x92, 0x00 };
670 E : AnalyzeSingleInstructionFromBuffer(kDec4);
671 E : EXPECT_FALSE(is_live(core::eax));
672 E : EXPECT_FALSE(is_live(core::ebx));
673 E : EXPECT_FALSE(is_live(core::ecx));
674 E : EXPECT_FALSE(is_live(core::edx));
675 :
676 : // _asm not ebx
677 : static const uint8 kNot1[] = { 0xF7, 0xD3 };
678 E : AnalyzeSingleInstructionFromBuffer(kNot1);
679 E : EXPECT_TRUE(is_live(core::ebx));
680 :
681 : // _asm not [ebx]
682 : static const uint8 kNot2[] = { 0xF6, 0x13 };
683 E : AnalyzeSingleInstructionFromBuffer(kNot2);
684 E : EXPECT_TRUE(is_live(core::ebx));
685 :
686 : // _asm neg ebx
687 : static const uint8 kNeg1[] = { 0xF7, 0xDB };
688 E : AnalyzeSingleInstructionFromBuffer(kNeg1);
689 E : EXPECT_TRUE(is_live(core::ebx));
690 :
691 : // _asm neg [ebx]
692 : static const uint8 kNeg2[] = { 0xF6, 0x1B };
693 E : AnalyzeSingleInstructionFromBuffer(kNeg2);
694 E : EXPECT_TRUE(is_live(core::ebx));
695 :
696 : // _asm inc edx
697 : static const uint8 kInc[] = { 0x42 };
698 E : AnalyzeSingleInstructionFromBuffer(kInc);
699 E : EXPECT_TRUE(is_live(core::edx));
700 E : }
701 :
702 E : TEST_F(LivenessAnalysisTest, DecIncFlagsInstructions) {
703 : // NOTE: inc/dec do not touch the carry flag.
704 : // _asm inc edx
705 : static const uint8 kInc[] = { 0x42 };
706 E : AddInstructionFromBuffer(kInc);
707 E : EXPECT_TRUE(CheckCarryFlagInstruction(true, false));
708 E : instructions_.clear();
709 :
710 : // _asm dec eax
711 : static const uint8 kDec1[] = { 0x48 };
712 E : AddInstructionFromBuffer(kDec1);
713 E : EXPECT_TRUE(CheckCarryFlagInstruction(true, false));
714 E : instructions_.clear();
715 E : }
716 :
717 E : TEST_F(LivenessAnalysisTest, ArithmeticBinaryInstructions) {
718 : // _asm add ebx, ecx
719 : static const uint8 kAdd[] = { 0x03, 0xD9 };
720 E : AnalyzeSingleInstructionFromBuffer(kAdd);
721 E : EXPECT_TRUE(is_live(core::ebx));
722 E : EXPECT_TRUE(is_live(core::ecx));
723 :
724 : // _asm adc ebx, edx
725 : static const uint8 kAdc[] = { 0x13, 0xDA };
726 E : AnalyzeSingleInstructionFromBuffer(kAdc);
727 E : EXPECT_TRUE(is_live(core::ebx));
728 E : EXPECT_TRUE(is_live(core::edx));
729 :
730 : // _asm sub esi, edi
731 : static const uint8 kSub[] = { 0x2B, 0xF7 };
732 E : AnalyzeSingleInstructionFromBuffer(kSub);
733 E : EXPECT_TRUE(is_live(core::esi));
734 E : EXPECT_TRUE(is_live(core::edi));
735 :
736 : // _asm sbb ebx, [eax + edx + 12]
737 : static const uint8 KSbb[] = { 0x1B, 0x5C, 0x10, 0x0C };
738 E : AnalyzeSingleInstructionFromBuffer(KSbb);
739 E : EXPECT_TRUE(is_live(core::eax));
740 E : EXPECT_TRUE(is_live(core::ebx));
741 E : EXPECT_TRUE(is_live(core::edx));
742 :
743 : // _asm and ebx, ecx
744 : static const uint8 kAnd[] = { 0x23, 0xD9 };
745 E : AnalyzeSingleInstructionFromBuffer(kAnd);
746 E : EXPECT_TRUE(is_live(core::ebx));
747 E : EXPECT_TRUE(is_live(core::ecx));
748 :
749 : // _asm or esi, [edi]
750 : static const uint8 kOr[] = { 0x0B, 0x37 };
751 E : AnalyzeSingleInstructionFromBuffer(kOr);
752 E : EXPECT_TRUE(is_live(core::esi));
753 E : EXPECT_TRUE(is_live(core::edi));
754 :
755 : // _asm xor [esi], edi
756 : static const uint8 kXor[] = { 0x31, 0x3E };
757 E : AnalyzeSingleInstructionFromBuffer(kXor);
758 E : EXPECT_TRUE(is_live(core::esi));
759 E : EXPECT_TRUE(is_live(core::edi));
760 :
761 : // _asm shl ebx, 1
762 : static const uint8 kShl1[] = { 0xD1, 0xE3 };
763 E : AnalyzeSingleInstructionFromBuffer(kShl1);
764 E : EXPECT_TRUE(is_live(core::ebx));
765 :
766 : // _asm shr esi, 2
767 : static const uint8 kShr1[] = { 0xC1, 0xEE, 0x02 };
768 E : AnalyzeSingleInstructionFromBuffer(kShr1);
769 E : EXPECT_TRUE(is_live(core::esi));
770 :
771 : // _asm sar ecx, 3
772 : static const uint8 kSar1[] = { 0xC1, 0xF9, 0x03 };
773 E : AnalyzeSingleInstructionFromBuffer(kSar1);
774 E : EXPECT_TRUE(is_live(core::ecx));
775 :
776 : // _asm rol ebx, 1
777 : static const uint8 kRol1[] = { 0xD1, 0xC3 };
778 E : AnalyzeSingleInstructionFromBuffer(kRol1);
779 E : EXPECT_TRUE(is_live(core::ebx));
780 :
781 : // _asm ror esi, 2
782 : static const uint8 kRor1[] = { 0xC1, 0xCE, 0x02 };
783 E : AnalyzeSingleInstructionFromBuffer(kRor1);
784 E : EXPECT_TRUE(is_live(core::esi));
785 :
786 : // _asm shl ebx, cl
787 : static const uint8 kShl2[] = { 0xD3, 0xE3 };
788 E : AnalyzeSingleInstructionFromBuffer(kShl2);
789 E : EXPECT_TRUE(is_live(core::ebx));
790 E : EXPECT_TRUE(is_live(core::ecx));
791 :
792 : // _asm shr esi, cl
793 : static const uint8 kShr2[] = { 0xD3, 0xEE };
794 E : AnalyzeSingleInstructionFromBuffer(kShr2);
795 E : EXPECT_TRUE(is_live(core::esi));
796 E : EXPECT_TRUE(is_live(core::ecx));
797 :
798 : // _asm sar edx, cl
799 : static const uint8 kSar2[] = { 0xD3, 0xFA };
800 E : AnalyzeSingleInstructionFromBuffer(kSar2);
801 E : EXPECT_TRUE(is_live(core::edx));
802 E : EXPECT_TRUE(is_live(core::ecx));
803 :
804 : // _asm rol ebx, cl
805 : static const uint8 kRol2[] = { 0xD3, 0xC3 };
806 E : AnalyzeSingleInstructionFromBuffer(kRol2);
807 E : EXPECT_TRUE(is_live(core::ebx));
808 E : EXPECT_TRUE(is_live(core::ecx));
809 :
810 : // _asm ror esi, cl
811 : static const uint8 kRor2[] = { 0xD3, 0xCE };
812 E : AnalyzeSingleInstructionFromBuffer(kRor2);
813 E : EXPECT_TRUE(is_live(core::esi));
814 E : EXPECT_TRUE(is_live(core::ecx));
815 E : }
816 :
817 E : TEST_F(LivenessAnalysisTest, ArithmeticFlagsInstructions) {
818 : // _asm adc ebx, edx
819 : static const uint8 kAdc[] = { 0x13, 0xDA };
820 E : AnalyzeSingleInstructionFromBuffer(kAdc);
821 E : EXPECT_TRUE(CheckCarryFlagInstruction(true, true));
822 :
823 : // _asm sbb ebx, [eax + edx + 12]
824 : static const uint8 KSbb[] = { 0x1B, 0x5C, 0x10, 0x0C };
825 E : AnalyzeSingleInstructionFromBuffer(KSbb);
826 E : EXPECT_TRUE(CheckCarryFlagInstruction(true, true));
827 E : }
828 :
829 E : TEST_F(LivenessAnalysisTest, ConversionInstructions) {
830 : static const uint8 kCdq[] = { 0x99 };
831 E : AnalyzeSingleInstructionFromBuffer(kCdq);
832 E : EXPECT_TRUE(is_live(core::eax));
833 E : EXPECT_FALSE(is_live(core::edx));
834 E : EXPECT_FALSE(are_arithmetic_flags_live());
835 E : }
836 :
837 E : TEST_F(LivenessAnalysisTest, EpilogueInstructions) {
838 : static const uint8 kLeave[] = { 0xC9 };
839 E : AnalyzeSingleInstructionFromBuffer(kLeave);
840 E : EXPECT_TRUE(is_live(core::ebp));
841 E : EXPECT_FALSE(is_live(core::esp));
842 E : EXPECT_FALSE(are_arithmetic_flags_live());
843 E : }
844 :
845 E : TEST_F(LivenessAnalysisTest, StackInstructions) {
846 : // Validate instructions that push/pop on the stack.
847 : // _asm push eax
848 : static const uint8 kPushd[] = { 0x50 };
849 E : AnalyzeSingleInstructionFromBuffer(kPushd);
850 E : EXPECT_TRUE(is_live(core::esp));
851 E : EXPECT_TRUE(is_live(core::eax));
852 :
853 : // _asm pop eax
854 : static const uint8 kPopd[] = { 0x58 };
855 E : AnalyzeSingleInstructionFromBuffer(kPopd);
856 E : EXPECT_TRUE(is_live(core::esp));
857 E : EXPECT_FALSE(is_live(core::eax));
858 :
859 : // _asm push ax
860 : static const uint8 kPush[] = { 0x66, 0x50 };
861 E : AnalyzeSingleInstructionFromBuffer(kPush);
862 E : EXPECT_TRUE(is_live(core::esp));
863 E : EXPECT_TRUE(is_live(core::eax));
864 :
865 : // _asm pop ax
866 : static const uint8 kPop[] = { 0x66, 0x58 };
867 E : AnalyzeSingleInstructionFromBuffer(kPop);
868 E : EXPECT_TRUE(is_live(core::esp));
869 E : EXPECT_FALSE(is_live(core::eax));
870 :
871 : static const uint8 kPopSMem[] = { 0x66, 0x8F, 0x00 };
872 E : AnalyzeSingleInstructionFromBuffer(kPopSMem);
873 E : EXPECT_TRUE(is_live(core::esp));
874 E : EXPECT_TRUE(is_live(core::eax));
875 E : }
876 :
877 E : TEST_F(LivenessAnalysisTest, SetFlagInstructions) {
878 : // Validate instructions that consume flags. Ensure flags are used.
879 :
880 : // _asm seta al
881 : static const uint8 kSetA[] = { 0x0F, 0x97, 0xC0 };
882 E : AnalyzeSingleInstructionFromBuffer(kSetA);
883 E : EXPECT_TRUE(are_arithmetic_flags_live());
884 :
885 : // _asm setae al
886 : static const uint8 kSetAE[] = { 0x0F, 0x93, 0xC0 };
887 E : AnalyzeSingleInstructionFromBuffer(kSetAE);
888 E : EXPECT_TRUE(are_arithmetic_flags_live());
889 :
890 : // _asm setb al
891 : static const uint8 kSetB[] = { 0x0F, 0x92, 0xC0 };
892 E : AnalyzeSingleInstructionFromBuffer(kSetB);
893 E : EXPECT_TRUE(are_arithmetic_flags_live());
894 :
895 : // _asm setbe al
896 : static const uint8 kSetBE[] = { 0x0F, 0x96, 0xC0 };
897 E : AnalyzeSingleInstructionFromBuffer(kSetBE);
898 E : EXPECT_TRUE(are_arithmetic_flags_live());
899 :
900 : // _asm setg al
901 : static const uint8 kSetG[] = { 0x0F, 0x9F, 0xC0 };
902 E : AnalyzeSingleInstructionFromBuffer(kSetG);
903 E : EXPECT_TRUE(are_arithmetic_flags_live());
904 :
905 : // _asm setge al
906 : static const uint8 kSetGE[] = { 0x0F, 0x9D, 0xC0 };
907 E : AnalyzeSingleInstructionFromBuffer(kSetGE);
908 E : EXPECT_TRUE(are_arithmetic_flags_live());
909 :
910 : // _asm setl al
911 : static const uint8 kSetL[] = { 0x0F, 0x9C, 0xC0 };
912 E : AnalyzeSingleInstructionFromBuffer(kSetL);
913 E : EXPECT_TRUE(are_arithmetic_flags_live());
914 :
915 : // _asm setle al
916 : static const uint8 kSetLE[] = { 0x0F, 0x9E, 0xC0 };
917 E : AnalyzeSingleInstructionFromBuffer(kSetLE);
918 E : EXPECT_TRUE(are_arithmetic_flags_live());
919 :
920 : // _asm setno al
921 : static const uint8 kSetNO[] = { 0x0F, 0x91, 0xC0 };
922 E : AnalyzeSingleInstructionFromBuffer(kSetNO);
923 E : EXPECT_TRUE(are_arithmetic_flags_live());
924 :
925 : // _asm setnp al
926 : static const uint8 kSetNP[] = { 0x0F, 0x9B, 0xC0 };
927 E : AnalyzeSingleInstructionFromBuffer(kSetNP);
928 E : EXPECT_TRUE(are_arithmetic_flags_live());
929 :
930 : // _asm setns al
931 : static const uint8 kSetNS[] = { 0x0F, 0x99, 0xC0 };
932 E : AnalyzeSingleInstructionFromBuffer(kSetNS);
933 E : EXPECT_TRUE(are_arithmetic_flags_live());
934 :
935 : // _asm setnz al
936 : static const uint8 kSetNZ[] = { 0x0F, 0x95, 0xC0 };
937 E : AnalyzeSingleInstructionFromBuffer(kSetNZ);
938 E : EXPECT_TRUE(are_arithmetic_flags_live());
939 :
940 : // _asm seto al
941 : static const uint8 kSetO[] = { 0x0F, 0x90, 0xC0 };
942 E : AnalyzeSingleInstructionFromBuffer(kSetO);
943 E : EXPECT_TRUE(are_arithmetic_flags_live());
944 :
945 : // _asm setp al
946 : static const uint8 kSetP[] = { 0x0F, 0x9A, 0xC0 };
947 E : AnalyzeSingleInstructionFromBuffer(kSetP);
948 E : EXPECT_TRUE(are_arithmetic_flags_live());
949 :
950 : // _asm sets al
951 : static const uint8 kSetS[] = { 0x0F, 0x98, 0xC0 };
952 E : AnalyzeSingleInstructionFromBuffer(kSetS);
953 E : EXPECT_TRUE(are_arithmetic_flags_live());
954 :
955 : // _asm setz al
956 : static const uint8 kSetZ[] = { 0x0F, 0x94, 0xC0 };
957 E : AnalyzeSingleInstructionFromBuffer(kSetZ);
958 E : EXPECT_TRUE(are_arithmetic_flags_live());
959 E : }
960 :
961 E : TEST_F(LivenessAnalysisTest, PushPopFlagsInstructions) {
962 : // Validate instructions that push/pop flags. Ensure flags are used, and stack
963 : // pointer is modified.
964 :
965 : // _asm pushfd
966 : static const uint8 kPushfd[] = { 0x9C };
967 E : AnalyzeSingleInstructionFromBuffer(kPushfd);
968 E : EXPECT_TRUE(are_arithmetic_flags_live());
969 E : EXPECT_TRUE(is_live(core::esp));
970 :
971 : // _asm popfd
972 : static const uint8 kPopfd[] = { 0x9D };
973 E : AnalyzeSingleInstructionFromBuffer(kPopfd);
974 E : EXPECT_FALSE(are_arithmetic_flags_live());
975 E : EXPECT_TRUE(is_live(core::esp));
976 :
977 : // _asm pushf
978 : static const uint8 kPushf[] = { 0x66, 0x9C };
979 E : AnalyzeSingleInstructionFromBuffer(kPushf);
980 E : EXPECT_TRUE(are_arithmetic_flags_live());
981 E : EXPECT_TRUE(is_live(core::esp));
982 :
983 : // _asm popf
984 : static const uint8 kPopf[] = { 0x66, 0x9D };
985 E : AnalyzeSingleInstructionFromBuffer(kPopf);
986 E : EXPECT_FALSE(are_arithmetic_flags_live());
987 E : EXPECT_TRUE(is_live(core::esp));
988 E : }
989 :
990 E : TEST_F(LivenessAnalysisTest, LoadStoreFlagsInstructions) {
991 : // Validate instructions that load/store flags. Ensure flags are defined or
992 : // used, and stack pointer is not modified.
993 :
994 : // _asm sahf
995 : static const uint8 kSahf[] = { 0x9E };
996 E : AnalyzeSingleInstructionFromBuffer(kSahf);
997 E : EXPECT_FALSE(are_arithmetic_flags_live());
998 E : EXPECT_FALSE(is_live(core::esp));
999 E : EXPECT_TRUE(is_live(core::eax));
1000 :
1001 : // _asm lahf
1002 : static const uint8 kLahf[] = { 0x9F };
1003 E : AnalyzeSingleInstructionFromBuffer(kLahf);
1004 E : EXPECT_TRUE(are_arithmetic_flags_live());
1005 E : EXPECT_FALSE(is_live(core::esp));
1006 E : EXPECT_FALSE(is_live(core::eax));
1007 E : }
1008 :
1009 E : TEST_F(LivenessAnalysisTest, ExtendMovInstructions) {
1010 : // _asm movsx eax, cl
1011 : static const uint8 kMovsx1[] = { 0x0F, 0xBE, 0xC1 };
1012 E : AnalyzeSingleInstructionFromBuffer(kMovsx1);
1013 E : EXPECT_FALSE(are_arithmetic_flags_live());
1014 E : EXPECT_FALSE(is_live(core::eax));
1015 E : EXPECT_TRUE(is_live(core::ecx));
1016 :
1017 : // _asm movsx eax, BYTE PTR [ecx]
1018 : static const uint8 kMovsx2[] = { 0x0F, 0xBE, 0x01 };
1019 E : AnalyzeSingleInstructionFromBuffer(kMovsx2);
1020 E : EXPECT_FALSE(are_arithmetic_flags_live());
1021 E : EXPECT_FALSE(is_live(core::eax));
1022 E : EXPECT_TRUE(is_live(core::ecx));
1023 :
1024 : // _asm movzx eax, cl
1025 : static const uint8 kMovzx1[] = { 0x0F, 0xB6, 0xC1 };
1026 E : AnalyzeSingleInstructionFromBuffer(kMovzx1);
1027 E : EXPECT_FALSE(are_arithmetic_flags_live());
1028 E : EXPECT_FALSE(is_live(core::eax));
1029 E : EXPECT_TRUE(is_live(core::ecx));
1030 :
1031 : // _asm movzx eax, BYTE PTR [ecx]
1032 : static const uint8 kMovzx2[] = { 0x0F, 0xB6, 0x01 };
1033 E : AnalyzeSingleInstructionFromBuffer(kMovzx2);
1034 E : EXPECT_FALSE(are_arithmetic_flags_live());
1035 E : EXPECT_FALSE(is_live(core::eax));
1036 E : EXPECT_TRUE(is_live(core::ecx));
1037 E : }
1038 :
1039 E : TEST_F(LivenessAnalysisTest, StringInstructions) {
1040 : // movs dword ptr es:[edi], dword ptr [esi]
1041 : static const uint8 kMovsl[] = { 0xA5 };
1042 E : AnalyzeSingleInstructionFromBuffer(kMovsl);
1043 E : EXPECT_TRUE(is_live(core::esi));
1044 E : EXPECT_TRUE(is_live(core::edi));
1045 E : EXPECT_FALSE(is_live(core::ecx));
1046 E : EXPECT_FALSE(are_arithmetic_flags_live());
1047 :
1048 : // movs byte ptr es:[edi], byte ptr [esi]
1049 : static const uint8 kMovsb[] = { 0xA4 };
1050 E : AnalyzeSingleInstructionFromBuffer(kMovsb);
1051 E : EXPECT_TRUE(is_live(core::esi));
1052 E : EXPECT_TRUE(is_live(core::edi));
1053 E : EXPECT_FALSE(is_live(core::ecx));
1054 E : EXPECT_FALSE(are_arithmetic_flags_live());
1055 :
1056 : // stos dword ptr es:[edi]
1057 : static const uint8 kStosl[] = { 0xAB };
1058 E : AnalyzeSingleInstructionFromBuffer(kStosl);
1059 E : EXPECT_FALSE(is_live(core::esi));
1060 E : EXPECT_TRUE(is_live(core::edi));
1061 E : EXPECT_FALSE(is_live(core::ecx));
1062 E : EXPECT_FALSE(are_arithmetic_flags_live());
1063 :
1064 : // stos byte ptr es:[edi]
1065 : static const uint8 Stosb[] = { 0xAA };
1066 E : AnalyzeSingleInstructionFromBuffer(Stosb);
1067 E : EXPECT_FALSE(is_live(core::esi));
1068 E : EXPECT_TRUE(is_live(core::edi));
1069 E : EXPECT_FALSE(is_live(core::ecx));
1070 E : EXPECT_FALSE(are_arithmetic_flags_live());
1071 E : }
1072 :
1073 E : TEST_F(LivenessAnalysisTest, PrefixedStringInstructions) {
1074 : // repne movs dword ptr es:[edi], dword ptr [esi]
1075 : static const uint8 kMovsl[] = { 0xF2, 0xA5 };
1076 E : AnalyzeSingleInstructionFromBuffer(kMovsl);
1077 E : EXPECT_TRUE(is_live(core::esi));
1078 E : EXPECT_TRUE(is_live(core::edi));
1079 E : EXPECT_TRUE(is_live(core::ecx));
1080 E : EXPECT_FALSE(are_arithmetic_flags_live());
1081 :
1082 : // repne movs byte ptr es:[edi], byte ptr [esi]
1083 : static const uint8 kMovsb[] = { 0xF2, 0xA4 };
1084 E : AnalyzeSingleInstructionFromBuffer(kMovsb);
1085 E : EXPECT_TRUE(is_live(core::esi));
1086 E : EXPECT_TRUE(is_live(core::edi));
1087 E : EXPECT_TRUE(is_live(core::ecx));
1088 E : EXPECT_FALSE(are_arithmetic_flags_live());
1089 :
1090 : // repne stos dword ptr es:[edi]
1091 : static const uint8 kStosl[] = { 0xF2, 0xAB };
1092 E : AnalyzeSingleInstructionFromBuffer(kStosl);
1093 E : EXPECT_FALSE(is_live(core::esi));
1094 E : EXPECT_TRUE(is_live(core::edi));
1095 E : EXPECT_TRUE(is_live(core::ecx));
1096 E : EXPECT_FALSE(are_arithmetic_flags_live());
1097 :
1098 : // repne stos byte ptr es:[edi]
1099 : static const uint8 Stosb[] = { 0xF2, 0xAA };
1100 E : AnalyzeSingleInstructionFromBuffer(Stosb);
1101 E : EXPECT_FALSE(is_live(core::esi));
1102 E : EXPECT_TRUE(is_live(core::edi));
1103 E : EXPECT_TRUE(is_live(core::ecx));
1104 E : EXPECT_FALSE(are_arithmetic_flags_live());
1105 E : }
1106 :
1107 E : TEST_F(LivenessAnalysisTest, FloatingPointInstructions) {
1108 : // _asm fld1
1109 : static const uint8 kFld1[] = { 0xD9, 0xE8 };
1110 : // _asm fldz
1111 : static const uint8 kFldz[] = { 0xD9, 0xEE };
1112 : // _asm fadd
1113 : static const uint8 kFadd[] = { 0xDE, 0xC1 };
1114 : // _asm faddp st(3), st(0)
1115 : static const uint8 kFaddp[] = { 0xDE, 0xC3 };
1116 : // _asm fsub
1117 : static const uint8 kFsub[] = { 0xDE, 0xE9 };
1118 : // _asm fsubp st(3), st(0)
1119 : static const uint8 kFsubp[] = { 0xDE, 0xEB };
1120 : // _asm fmul
1121 : static const uint8 kFmul[] = { 0xDE, 0xC9 };
1122 : // _asm fmulp st(3), st(0)
1123 : static const uint8 kFmulp[] = { 0xDE, 0xCB };
1124 :
1125 : // Floating point instructions don't touch any register nor general registers.
1126 E : AddInstructionFromBuffer(kFld1);
1127 E : AddInstructionFromBuffer(kFldz);
1128 E : AddInstructionFromBuffer(kFadd);
1129 E : AddInstructionFromBuffer(kFaddp);
1130 E : AddInstructionFromBuffer(kFsub);
1131 E : AddInstructionFromBuffer(kFsubp);
1132 E : AddInstructionFromBuffer(kFmul);
1133 E : AddInstructionFromBuffer(kFmulp);
1134 E : DefineAllRegisters();
1135 E : AnalyzeInstructions();
1136 :
1137 E : EXPECT_FALSE(is_live(core::eax));
1138 E : EXPECT_FALSE(is_live(core::ebx));
1139 E : EXPECT_FALSE(is_live(core::ecx));
1140 E : EXPECT_FALSE(is_live(core::edx));
1141 E : EXPECT_FALSE(is_live(core::esi));
1142 E : EXPECT_FALSE(is_live(core::edi));
1143 E : EXPECT_FALSE(are_arithmetic_flags_live());
1144 E : }
1145 :
1146 E : TEST_F(LivenessAnalysisTest, FloatingPointMemoryInstructions) {
1147 : // _asm fld DWORD PTR [eax + ecx]
1148 : static const uint8 kFld[] = { 0xD9, 0x04, 0x08 };
1149 E : AnalyzeSingleInstructionFromBuffer(kFld);
1150 E : EXPECT_TRUE(is_live(core::eax));
1151 E : EXPECT_FALSE(is_live(core::ebx));
1152 E : EXPECT_TRUE(is_live(core::ecx));
1153 E : EXPECT_FALSE(are_arithmetic_flags_live());
1154 :
1155 : // _asm fst DWORD PTR [eax + ecx]
1156 : static const uint8 kFst[] = { 0xD9, 0x14, 0x08 };
1157 E : AnalyzeSingleInstructionFromBuffer(kFst);
1158 E : EXPECT_TRUE(is_live(core::eax));
1159 E : EXPECT_FALSE(is_live(core::ebx));
1160 E : EXPECT_TRUE(is_live(core::ecx));
1161 E : EXPECT_FALSE(are_arithmetic_flags_live());
1162 :
1163 : // _asm fstp DWORD PTR [eax + ecx]
1164 : static const uint8 kFstp[] = { 0xD9, 0x1C, 0x08 };
1165 E : AnalyzeSingleInstructionFromBuffer(kFstp);
1166 E : EXPECT_TRUE(is_live(core::eax));
1167 E : EXPECT_FALSE(is_live(core::ebx));
1168 E : EXPECT_TRUE(is_live(core::ecx));
1169 E : EXPECT_FALSE(are_arithmetic_flags_live());
1170 :
1171 : // _asm fadd DWORD PTR [eax]
1172 : static const uint8 kFadd[] = { 0xD8, 0x00 };
1173 E : AnalyzeSingleInstructionFromBuffer(kFadd);
1174 E : EXPECT_TRUE(is_live(core::eax));
1175 E : EXPECT_FALSE(are_arithmetic_flags_live());
1176 :
1177 : // _asm fsub DWORD PTR [ecx]
1178 : static const uint8 kFsub[] = { 0xD8, 0x21 };
1179 E : AnalyzeSingleInstructionFromBuffer(kFsub);
1180 E : EXPECT_TRUE(is_live(core::ecx));
1181 E : EXPECT_FALSE(are_arithmetic_flags_live());
1182 :
1183 : // _asm fmul DWORD PTR [esi]
1184 : static const uint8 kFmul[] = { 0xD8, 0x0E };
1185 E : AnalyzeSingleInstructionFromBuffer(kFmul);
1186 E : EXPECT_TRUE(is_live(core::esi));
1187 E : EXPECT_FALSE(are_arithmetic_flags_live());
1188 :
1189 : // _asm fild DWORD PTR [eax]
1190 : static const uint8 kFild[] = { 0xDB, 0x00 };
1191 E : AnalyzeSingleInstructionFromBuffer(kFild);
1192 E : EXPECT_TRUE(is_live(core::eax));
1193 E : EXPECT_FALSE(are_arithmetic_flags_live());
1194 :
1195 : // _asm fist DWORD PTR [eax]
1196 : static const uint8 kFist[] = { 0xDB, 0x10 };
1197 E : AnalyzeSingleInstructionFromBuffer(kFist);
1198 E : EXPECT_TRUE(is_live(core::eax));
1199 E : EXPECT_FALSE(are_arithmetic_flags_live());
1200 :
1201 : // _asm fistp DWORD PTR [eax]
1202 : static const uint8 kFistp[] = { 0xDB, 0x18 };
1203 E : AnalyzeSingleInstructionFromBuffer(kFistp);
1204 E : EXPECT_TRUE(is_live(core::eax));
1205 E : EXPECT_FALSE(are_arithmetic_flags_live());
1206 E : }
1207 :
1208 E : TEST_F(LivenessAnalysisTest, FloatingPointCompareInstructions) {
1209 : // _asm fcom
1210 : static const uint8 kFcom[] = { 0xD8, 0xD1 };
1211 E : AnalyzeSingleInstructionFromBuffer(kFcom);
1212 E : EXPECT_FALSE(are_arithmetic_flags_live());
1213 :
1214 : // _asm fcomp
1215 : static const uint8 kFcomp[] = { 0xD8, 0xD9 };
1216 E : AnalyzeSingleInstructionFromBuffer(kFcomp);
1217 E : EXPECT_FALSE(are_arithmetic_flags_live());
1218 :
1219 : // _asm fcompp
1220 : static const uint8 kFcompp[] = { 0xDE, 0xD9 };
1221 E : AnalyzeSingleInstructionFromBuffer(kFcompp);
1222 E : EXPECT_FALSE(are_arithmetic_flags_live());
1223 :
1224 : // _asm fcomi
1225 : static const uint8 kFcomi[] = { 0xDB, 0xF1 };
1226 E : AnalyzeSingleInstructionFromBuffer(kFcomi);
1227 E : EXPECT_FALSE(are_arithmetic_flags_live());
1228 :
1229 : // _asm fcomip
1230 : static const uint8 fcomip[] = { 0xDF, 0xF1 };
1231 E : AnalyzeSingleInstructionFromBuffer(fcomip);
1232 E : EXPECT_FALSE(are_arithmetic_flags_live());
1233 E : }
1234 :
1235 E : TEST_F(LivenessAnalysisTest, FloatingPointCompareMemoryInstructions) {
1236 : // _asm fcom qword ptr [edx+ecx*8]
1237 : static const uint8 kFcom[] = { 0xDC, 0x14, 0xCA };
1238 E : AnalyzeSingleInstructionFromBuffer(kFcom);
1239 E : EXPECT_FALSE(is_live(core::eax));
1240 E : EXPECT_FALSE(is_live(core::ebx));
1241 E : EXPECT_TRUE(is_live(core::ecx));
1242 E : EXPECT_TRUE(is_live(core::edx));
1243 E : EXPECT_FALSE(are_arithmetic_flags_live());
1244 :
1245 : // _asm fcomp word ptr [edx+ecx*8]
1246 : static const uint8 kFcomp[] = { 0xDC, 0x1C, 0xCA };
1247 E : AnalyzeSingleInstructionFromBuffer(kFcomp);
1248 E : EXPECT_FALSE(is_live(core::eax));
1249 E : EXPECT_FALSE(is_live(core::ebx));
1250 E : EXPECT_TRUE(is_live(core::ecx));
1251 E : EXPECT_TRUE(is_live(core::edx));
1252 E : EXPECT_FALSE(are_arithmetic_flags_live());
1253 :
1254 : // _asm ficom qword ptr [edx+ecx*8]
1255 : static const uint8 kFicom[] = { 0xDE, 0x14, 0xCA };
1256 E : AnalyzeSingleInstructionFromBuffer(kFicom);
1257 E : EXPECT_FALSE(is_live(core::eax));
1258 E : EXPECT_FALSE(is_live(core::ebx));
1259 E : EXPECT_TRUE(is_live(core::ecx));
1260 E : EXPECT_TRUE(is_live(core::edx));
1261 E : EXPECT_FALSE(are_arithmetic_flags_live());
1262 :
1263 : // _asm ficomp word ptr [edx+ecx*8]
1264 : static const uint8 kFicomp[] = { 0xDE, 0x1C, 0xCA };
1265 E : AnalyzeSingleInstructionFromBuffer(kFicomp);
1266 E : EXPECT_FALSE(is_live(core::eax));
1267 E : EXPECT_FALSE(is_live(core::ebx));
1268 E : EXPECT_TRUE(is_live(core::ecx));
1269 E : EXPECT_TRUE(is_live(core::edx));
1270 E : EXPECT_FALSE(are_arithmetic_flags_live());
1271 :
1272 : // _asm ficom dword ptr [eax]
1273 : static const uint8 kFicom2[] = { 0xDA, 0x10 };
1274 E : AnalyzeSingleInstructionFromBuffer(kFicom2);
1275 E : EXPECT_TRUE(is_live(core::eax));
1276 E : EXPECT_FALSE(is_live(core::edx));
1277 E : EXPECT_FALSE(are_arithmetic_flags_live());
1278 :
1279 : // _asm ficomp dword ptr [eax]
1280 : static const uint8 ficomp2[] = { 0xDA, 0x18 };
1281 E : AnalyzeSingleInstructionFromBuffer(ficomp2);
1282 E : EXPECT_TRUE(is_live(core::eax));
1283 E : EXPECT_FALSE(is_live(core::edx));
1284 E : EXPECT_FALSE(are_arithmetic_flags_live());
1285 E : }
1286 :
1287 E : TEST_F(LivenessAnalysisTest, FloatingPointCompareWithFlagsInstructions) {
1288 : // Some floating point operations modify eflags.
1289 :
1290 : // _asm fcomi
1291 : static const uint8 kFcomi[] = { 0xDB, 0xF1 };
1292 E : AddInstructionFromBuffer(kFcomi);
1293 E : EXPECT_TRUE(CheckCarryFlagInstruction(false, false));
1294 E : instructions_.clear();
1295 :
1296 : // _asm fcomip
1297 : static const uint8 fcomip[] = { 0xDF, 0xF1 };
1298 E : AddInstructionFromBuffer(fcomip);
1299 E : EXPECT_TRUE(CheckCarryFlagInstruction(false, false));
1300 E : instructions_.clear();
1301 E : }
1302 :
1303 E : TEST_F(LivenessAnalysisTest, UnknownInstruction) {
1304 : // Ensure unknown instructions are processed correctly.
1305 : static const uint8 kRdtsc[] = { 0x0F, 0x31 };
1306 E : AnalyzeSingleInstructionFromBuffer(kRdtsc);
1307 E : EXPECT_TRUE(is_live(core::eax));
1308 E : EXPECT_TRUE(is_live(core::ecx));
1309 E : EXPECT_TRUE(is_live(core::esi));
1310 E : EXPECT_TRUE(is_live(core::ebp));
1311 E : EXPECT_TRUE(are_arithmetic_flags_live());
1312 E : }
1313 :
1314 E : TEST_F(LivenessAnalysisTest, XorInitializationSpecialCase) {
1315 : // Validate an initialization pattern used by x86 compiler.
1316 : // Ensure the flags are assumed modified, and the register is unused.
1317 :
1318 : // _asm xor eax, eax
1319 : static const uint8 kXor1[] = { 0x33, 0xC0 };
1320 E : AnalyzeSingleInstructionFromBuffer(kXor1);
1321 E : EXPECT_FALSE(is_live(core::eax));
1322 E : EXPECT_FALSE(are_arithmetic_flags_live());
1323 :
1324 : // _asm xor ebx, ebx
1325 : static const uint8 kXor2[] = { 0x33, 0xDB };
1326 E : AnalyzeSingleInstructionFromBuffer(kXor2);
1327 E : EXPECT_FALSE(is_live(core::eax));
1328 E : EXPECT_FALSE(are_arithmetic_flags_live());
1329 :
1330 : // _asm xor ecx, ecx
1331 : static const uint8 kXor3[] = { 0x33, 0xC9 };
1332 E : AnalyzeSingleInstructionFromBuffer(kXor3);
1333 E : EXPECT_FALSE(is_live(core::eax));
1334 E : EXPECT_FALSE(are_arithmetic_flags_live());
1335 E : }
1336 :
1337 E : TEST_F(LivenessAnalysisTest, NopInstructionSpecialCase) {
1338 : // Nop should be ignored by the analysis.
1339 E : asm_.mov(core::eax, core::eax);
1340 E : asm_.mov(core::eax, Immediate(10));
1341 E : AnalyzeInstructions();
1342 E : EXPECT_FALSE(is_live(core::eax));
1343 E : }
1344 :
1345 E : TEST_F(LivenessAnalysisTest, GetStateAtEntryOfWithNull) {
1346 : // It is valid to pass a NULL pointer to get a state.
1347 E : liveness_.GetStateAtEntryOf(NULL, &state_);
1348 E : EXPECT_TRUE(is_live(core::eax));
1349 E : EXPECT_TRUE(is_live(core::esi));
1350 E : EXPECT_TRUE(are_arithmetic_flags_live());
1351 E : }
1352 :
1353 E : TEST_F(LivenessAnalysisTest, GetStateAtExitOfWithNull) {
1354 : // It is valid to pass a NULL pointer to get a state.
1355 E : liveness_.GetStateAtExitOf(NULL, &state_);
1356 E : EXPECT_TRUE(is_live(core::eax));
1357 E : EXPECT_TRUE(is_live(core::esi));
1358 E : EXPECT_TRUE(are_arithmetic_flags_live());
1359 E : }
1360 :
1361 E : TEST_F(LivenessAnalysisTest, LivenessAnalysisOverControlFlow) {
1362 E : BasicBlockSubGraph subgraph;
1363 :
1364 : // Build and analyze this flow graph:
1365 : // [if1]
1366 : // / \
1367 : // / \
1368 : // [true1] [false1]
1369 : // mov esi, 1 mov esi, 2
1370 : // mov edi, 2
1371 : // \ /
1372 : // \ /
1373 : // [if2] <-----------
1374 : // / \ \
1375 : // / \ \
1376 : // [true2] [false2] \
1377 : // mov eax, ebx mov ebp, esi |
1378 : // mov esi, edi |
1379 : // mov edi, ebp |
1380 : // mov eax, [esi] |
1381 : // \ / |
1382 : // \ / |
1383 : // [end2] /
1384 : // mov ecx, eax /
1385 : // \ /
1386 : // -----------------/
1387 :
1388 : // Create the control flow graph.
1389 E : BasicCodeBlock* if1 = subgraph.AddBasicCodeBlock("if1");
1390 E : BasicCodeBlock* true1 = subgraph.AddBasicCodeBlock("true1");
1391 E : BasicCodeBlock* false1 = subgraph.AddBasicCodeBlock("false1");
1392 E : BasicCodeBlock* if2 = subgraph.AddBasicCodeBlock("if2");
1393 E : BasicCodeBlock* true2 = subgraph.AddBasicCodeBlock("true2");
1394 E : BasicCodeBlock* false2 = subgraph.AddBasicCodeBlock("false2");
1395 E : BasicCodeBlock* end2 = subgraph.AddBasicCodeBlock("end2");
1396 :
1397 E : ASSERT_TRUE(if1 != NULL);
1398 E : ASSERT_TRUE(true1 != NULL);
1399 E : ASSERT_TRUE(false1 != NULL);
1400 E : ASSERT_TRUE(if2 != NULL);
1401 E : ASSERT_TRUE(true2 != NULL);
1402 E : ASSERT_TRUE(false2 != NULL);
1403 E : ASSERT_TRUE(end2 != NULL);
1404 :
1405 E : AddSuccessorBetween(Successor::kConditionEqual, if1, true1);
1406 E : AddSuccessorBetween(Successor::kConditionNotEqual, if1, false1);
1407 E : AddSuccessorBetween(Successor::kConditionTrue, true1, if2);
1408 E : AddSuccessorBetween(Successor::kConditionTrue, false1, if2);
1409 :
1410 E : AddSuccessorBetween(Successor::kConditionOverflow, if2, true2);
1411 E : AddSuccessorBetween(Successor::kConditionNotOverflow, if2, false2);
1412 E : AddSuccessorBetween(Successor::kConditionLess, true2, end2);
1413 E : AddSuccessorBetween(Successor::kConditionLess, false2, end2);
1414 :
1415 E : AddSuccessorBetween(Successor::kConditionTrue, end2, if2);
1416 :
1417 : // Insert instructions into basic blocks.
1418 : BasicBlockAssembler asm_end2(end2->instructions().end(),
1419 E : &end2->instructions());
1420 E : asm_end2.mov(core::ecx, core::eax);
1421 :
1422 : BasicBlockAssembler asm_true2(true2->instructions().end(),
1423 E : &true2->instructions());
1424 E : asm_true2.mov(core::eax, core::ebx);
1425 :
1426 : BasicBlockAssembler asm_false2(false2->instructions().end(),
1427 E : &false2->instructions());
1428 E : asm_false2.mov(core::ebp, core::esi);
1429 E : asm_false2.mov(core::esi, core::edi);
1430 E : asm_false2.mov(core::edi, core::ebp);
1431 E : asm_false2.mov(core::eax, Operand(core::esi));
1432 :
1433 : BasicBlockAssembler asm_true1(true1->instructions().end(),
1434 E : &true1->instructions());
1435 E : asm_true1.mov(core::esi, Immediate(1));
1436 :
1437 : BasicBlockAssembler asm_false1(false1->instructions().end(),
1438 E : &false1->instructions());
1439 E : asm_false1.mov(core::esi, Immediate(2));
1440 E : asm_false1.mov(core::edi, Immediate(2));
1441 :
1442 : // Perform global liveness analysis.
1443 E : liveness_.Analyze(&subgraph);
1444 :
1445 : // Validate fix-point propagation.
1446 E : liveness_.GetStateAtEntryOf(end2, &state_);
1447 E : EXPECT_TRUE(is_live(core::eax));
1448 E : EXPECT_TRUE(is_live(core::ebx));
1449 E : EXPECT_FALSE(is_live(core::ecx));
1450 E : EXPECT_TRUE(is_live(core::esi));
1451 E : EXPECT_TRUE(is_live(core::edi));
1452 E : EXPECT_FALSE(is_live(core::ebp));
1453 :
1454 E : liveness_.GetStateAtEntryOf(true2, &state_);
1455 E : EXPECT_FALSE(is_live(core::eax));
1456 E : EXPECT_TRUE(is_live(core::ebx));
1457 E : EXPECT_FALSE(is_live(core::ecx));
1458 E : EXPECT_TRUE(is_live(core::esi));
1459 E : EXPECT_TRUE(is_live(core::edi));
1460 E : EXPECT_FALSE(is_live(core::ebp));
1461 :
1462 E : liveness_.GetStateAtEntryOf(false2, &state_);
1463 E : EXPECT_FALSE(is_live(core::eax));
1464 E : EXPECT_TRUE(is_live(core::ebx));
1465 E : EXPECT_FALSE(is_live(core::ecx));
1466 E : EXPECT_TRUE(is_live(core::esi));
1467 E : EXPECT_TRUE(is_live(core::edi));
1468 E : EXPECT_FALSE(is_live(core::ebp));
1469 :
1470 E : liveness_.GetStateAtEntryOf(if2, &state_);
1471 E : EXPECT_FALSE(is_live(core::eax));
1472 E : EXPECT_TRUE(is_live(core::ebx));
1473 E : EXPECT_FALSE(is_live(core::ecx));
1474 E : EXPECT_TRUE(is_live(core::esi));
1475 E : EXPECT_TRUE(is_live(core::edi));
1476 E : EXPECT_FALSE(is_live(core::ebp));
1477 :
1478 E : liveness_.GetStateAtEntryOf(true1, &state_);
1479 E : EXPECT_FALSE(is_live(core::eax));
1480 E : EXPECT_TRUE(is_live(core::ebx));
1481 E : EXPECT_FALSE(is_live(core::ecx));
1482 E : EXPECT_FALSE(is_live(core::esi));
1483 E : EXPECT_TRUE(is_live(core::edi));
1484 E : EXPECT_FALSE(is_live(core::ebp));
1485 :
1486 E : liveness_.GetStateAtEntryOf(false1, &state_);
1487 E : EXPECT_FALSE(is_live(core::eax));
1488 E : EXPECT_TRUE(is_live(core::ebx));
1489 E : EXPECT_FALSE(is_live(core::ecx));
1490 E : EXPECT_FALSE(is_live(core::esi));
1491 E : EXPECT_FALSE(is_live(core::edi));
1492 E : EXPECT_FALSE(is_live(core::ebp));
1493 :
1494 E : liveness_.GetStateAtEntryOf(if1, &state_);
1495 E : EXPECT_FALSE(is_live(core::eax));
1496 E : EXPECT_TRUE(is_live(core::ebx));
1497 E : EXPECT_FALSE(is_live(core::ecx));
1498 E : EXPECT_FALSE(is_live(core::esi));
1499 E : EXPECT_TRUE(is_live(core::edi));
1500 E : EXPECT_FALSE(is_live(core::ebp));
1501 E : }
1502 :
1503 E : TEST_F(LivenessAnalysisTest, AnalyzeWithData) {
1504 E : BasicBlockSubGraph subgraph;
1505 E : const uint8 raw_data[] = { 0, 1, 2, 3, 4 };
1506 :
1507 : BlockDescription* block = subgraph.AddBlockDescription(
1508 E : "b1", "b1.obj", BlockGraph::CODE_BLOCK, 7, 2, 42);
1509 :
1510 E : BasicCodeBlock* bb = subgraph.AddBasicCodeBlock("bb");
1511 : BasicDataBlock* data =
1512 E : subgraph.AddBasicDataBlock("data", sizeof(raw_data), &raw_data[0]);
1513 :
1514 E : block->basic_block_order.push_back(bb);
1515 E : block->basic_block_order.push_back(data);
1516 :
1517 E : BasicBlockAssembler asm_bb(bb->instructions().end(), &bb->instructions());
1518 E : asm_bb.mov(core::eax, core::ebx);
1519 E : asm_bb.ret();
1520 :
1521 : // Analyze the flow graph.
1522 E : liveness_.Analyze(&subgraph);
1523 :
1524 E : liveness_.GetStateAtEntryOf(bb, &state_);
1525 E : EXPECT_FALSE(is_live(core::eax));
1526 E : EXPECT_TRUE(is_live(core::ebx));
1527 E : EXPECT_TRUE(is_live(core::esi));
1528 :
1529 E : liveness_.GetStateAtEntryOf(data, &state_);
1530 E : EXPECT_TRUE(is_live(core::eax));
1531 E : EXPECT_TRUE(is_live(core::ebx));
1532 E : EXPECT_TRUE(is_live(core::esi));
1533 E : }
1534 :
1535 : } // namespace
1536 :
1537 : } // namespace analysis
1538 : } // namespace block_graph
|