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