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