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 : #include "syzygy/block_graph/analysis/liveness_analysis.h"
16 :
17 : #include <set>
18 : #include <stack>
19 : #include <vector>
20 :
21 : #include "syzygy/assm/assembler.h"
22 : #include "syzygy/block_graph/analysis/control_flow_analysis.h"
23 : #include "syzygy/block_graph/analysis/liveness_analysis_internal.h"
24 : #include "syzygy/core/disassembler_util.h"
25 :
26 : #include "mnemonics.h" // NOLINT
27 :
28 : namespace block_graph {
29 : namespace analysis {
30 : namespace {
31 :
32 : using core::Register;
33 : typedef BasicBlockSubGraph::BBCollection BBCollection;
34 : typedef BasicBlock::Instructions Instructions;
35 : typedef BasicBlock::Successors Successors;
36 : typedef Instruction::Representation Representation;
37 : typedef ControlFlowAnalysis::BasicBlockOrdering BasicBlockOrdering;
38 : typedef LivenessAnalysis::State State;
39 : typedef LivenessAnalysis::State::RegisterMask RegisterMask;
40 : typedef LivenessAnalysis::State::FlagsMask FlagsMask;
41 :
42 : } // namespace
43 :
44 : State::State()
45 : : flags_(static_cast<RegisterMask>(StateHelper::REGBITS_ALL)),
46 E : registers_(static_cast<RegisterMask>(StateHelper::REGBITS_ALL)) {
47 E : }
48 :
49 E : State::State(const State& state) {
50 E : StateHelper::Copy(state, this);
51 E : }
52 :
53 E : bool State::IsLive(const Register& reg) const {
54 : // Convert from core::Register representation of registers to the bits
55 : // representation we use internally, by way of the Distorm _RegisterType.
56 : RegisterMask mask = StateHelper::RegisterToRegisterMask(
57 E : core::GetRegisterType(reg));
58 E : return StateHelper::IsPartiallySet(*this, mask);
59 E : }
60 :
61 E : bool State::AreArithmeticFlagsLive() const {
62 E : return StateHelper::AreArithmeticFlagsLive(*this);
63 E : }
64 :
65 E : LivenessAnalysis::LivenessAnalysis() : live_in_() {
66 E : }
67 :
68 : void LivenessAnalysis::GetStateAtEntryOf(const BasicBlock* bb,
69 E : State* state) const {
70 : // This function accepts a NULL basic block and returns a safe state with all
71 : // registers alive.
72 E : DCHECK(state != NULL);
73 :
74 E : if (bb != NULL) {
75 E : LiveMap::const_iterator look = live_in_.find(bb);
76 E : if (look != live_in_.end()) {
77 E : StateHelper::Copy(look->second, state);
78 E : return;
79 : }
80 : }
81 :
82 E : StateHelper::SetAll(state);
83 E : }
84 :
85 : void LivenessAnalysis::GetStateAtExitOf(const BasicBlock* bb,
86 E : State* state) const {
87 : // This function accepts a NULL basic block and returns a safe state with all
88 : // registers alive.
89 E : DCHECK(state != NULL);
90 :
91 : // Initialize liveness information assuming all registers are alive.
92 E : StateHelper::SetAll(state);
93 :
94 E : const BasicCodeBlock* code = BasicCodeBlock::Cast(bb);
95 E : if (code == NULL)
96 E : return;
97 :
98 E : const BasicBlock::Successors& successors = code->successors();
99 E : if (successors.empty())
100 E : return;
101 :
102 : // Merge current liveness information with every successor information.
103 E : StateHelper::Clear(state);
104 E : Successors::const_iterator succ_end = successors.end();
105 E : for (Successors::const_iterator succ = successors.begin();
106 E : succ != succ_end; ++succ) {
107 E : BasicBlock* successor_basic_block = succ->reference().basic_block();
108 E : if (successor_basic_block == NULL) {
109 : // Successor is not a BasicBlock. Assume all registers are alive.
110 E : StateHelper::SetAll(state);
111 E : return;
112 : }
113 :
114 : // Merge successor state into current state.
115 E : State successor_state;
116 E : GetStateAtEntryOf(successor_basic_block, &successor_state);
117 E : StateHelper::Union(successor_state, state);
118 :
119 : // Merge liveness information from the implicit instruction in successor.
120 E : if (StateHelper::GetUsesOf(*succ, &successor_state)) {
121 E : StateHelper::Union(successor_state, state);
122 E : } else {
123 i : StateHelper::SetAll(state);
124 : }
125 E : }
126 E : }
127 :
128 : void LivenessAnalysis::PropagateBackward(const Instruction& instr,
129 E : State* state) {
130 E : DCHECK(state != NULL);
131 :
132 : // Skip 'nop' instructions. It's better to skip them (i.e. mov %eax, %eax).
133 E : if (instr.IsNop())
134 E : return;
135 :
136 : // Remove 'defs' from current state.
137 E : State defs;
138 E : if (StateHelper::GetDefsOf(instr, &defs))
139 E : StateHelper::Subtract(defs, state);
140 :
141 E : if (instr.IsCall() || instr.IsReturn()) {
142 : // TODO(etienneb): Can we verify the calling convention? If so we can do
143 : // better than SetAll here.
144 E : StateHelper::SetAll(state);
145 E : } else if (instr.IsBranch() ||
146 : instr.IsInterrupt() ||
147 E : instr.IsControlFlow()) {
148 : // Don't mess with these instructions.
149 E : StateHelper::SetAll(state);
150 : }
151 :
152 : // Add 'uses' of instruction to current state, or assume all alive when 'uses'
153 : // information is not available.
154 E : State uses;
155 E : if (StateHelper::GetUsesOf(instr, &uses)) {
156 E : StateHelper::Union(uses, state);
157 E : } else {
158 E : StateHelper::SetAll(state);
159 : }
160 E : }
161 :
162 E : void LivenessAnalysis::Analyze(const BasicBlockSubGraph* subgraph) {
163 E : DCHECK(subgraph != NULL);
164 E : DCHECK(live_in_.empty());
165 :
166 : // Produce a post-order basic blocks ordering.
167 E : const BBCollection& basic_blocks = subgraph->basic_blocks();
168 E : std::vector<const BasicCodeBlock*> order;
169 E : ControlFlowAnalysis::FlattenBasicBlocksInPostOrder(basic_blocks, &order);
170 :
171 : // Initialize liveness information of each basic block (empty set).
172 E : BasicBlockOrdering::const_iterator fw_iter = order.begin();
173 E : for (; fw_iter != order.end(); ++fw_iter)
174 E : StateHelper::Clear(&live_in_[*fw_iter]);
175 :
176 : // Propagate liveness information until stable (fix-point). Each set may only
177 : // grow, thus we have a halting condition.
178 E : bool changed = true;
179 E : while (changed) {
180 E : changed = false;
181 :
182 E : BasicBlockOrdering::const_iterator bb_iter = order.begin();
183 E : for (; bb_iter != order.end(); ++bb_iter) {
184 E : const BasicCodeBlock* bb = *bb_iter;
185 :
186 : // Merge current liveness information with every successor information.
187 E : State state;
188 E : GetStateAtExitOf(bb, &state);
189 :
190 : // Propagate liveness information backward until the basic block entry.
191 E : const Instructions& instructions = bb->instructions();
192 E : Instructions::const_reverse_iterator instr_iter = instructions.rbegin();
193 E : for (; instr_iter != instructions.rend(); ++instr_iter)
194 E : PropagateBackward(*instr_iter, &state);
195 :
196 : // Commit liveness information to the global state.
197 E : if (StateHelper::Union(state, &live_in_[bb]))
198 E : changed = true;
199 E : }
200 E : }
201 E : }
202 :
203 E : RegisterMask LivenessAnalysis::StateHelper::RegisterToRegisterMask(uint8 reg) {
204 : LivenessAnalysis::StateHelper::RegisterBits mask =
205 E : LivenessAnalysis::StateHelper::REGBITS_NONE;
206 E : switch (reg) {
207 : case R_AL:
208 E : mask = LivenessAnalysis::StateHelper::REGBITS_AL; break;
209 : case R_AH:
210 E : mask = LivenessAnalysis::StateHelper::REGBITS_AH; break;
211 : case R_AX:
212 E : mask = LivenessAnalysis::StateHelper::REGBITS_AX; break;
213 : case R_EAX:
214 E : mask = LivenessAnalysis::StateHelper::REGBITS_EAX; break;
215 : case R_RAX:
216 i : mask = LivenessAnalysis::StateHelper::REGBITS_RAX; break;
217 : case R_BL:
218 E : mask = LivenessAnalysis::StateHelper::REGBITS_BL; break;
219 : case R_BH:
220 E : mask = LivenessAnalysis::StateHelper::REGBITS_BH; break;
221 : case R_BX:
222 E : mask = LivenessAnalysis::StateHelper::REGBITS_BX; break;
223 : case R_EBX:
224 E : mask = LivenessAnalysis::StateHelper::REGBITS_EBX; break;
225 : case R_RBX:
226 i : mask = LivenessAnalysis::StateHelper::REGBITS_RBX; break;
227 : case R_CL:
228 E : mask = LivenessAnalysis::StateHelper::REGBITS_CL; break;
229 : case R_CH:
230 E : mask = LivenessAnalysis::StateHelper::REGBITS_CH; break;
231 : case R_CX:
232 E : mask = LivenessAnalysis::StateHelper::REGBITS_CX; break;
233 : case R_ECX:
234 E : mask = LivenessAnalysis::StateHelper::REGBITS_ECX; break;
235 : case R_RCX:
236 i : mask = LivenessAnalysis::StateHelper::REGBITS_RCX; break;
237 : case R_DL:
238 E : mask = LivenessAnalysis::StateHelper::REGBITS_DL; break;
239 : case R_DH:
240 E : mask = LivenessAnalysis::StateHelper::REGBITS_DH; break;
241 : case R_DX:
242 E : mask = LivenessAnalysis::StateHelper::REGBITS_DX; break;
243 : case R_EDX:
244 E : mask = LivenessAnalysis::StateHelper::REGBITS_EDX; break;
245 : case R_RDX:
246 i : mask = LivenessAnalysis::StateHelper::REGBITS_RDX; break;
247 : case R_SI:
248 E : mask = LivenessAnalysis::StateHelper::REGBITS_SI; break;
249 : case R_ESI:
250 E : mask = LivenessAnalysis::StateHelper::REGBITS_ESI; break;
251 : case R_RSI:
252 i : mask = LivenessAnalysis::StateHelper::REGBITS_RSI; break;
253 : case R_DI:
254 E : mask = LivenessAnalysis::StateHelper::REGBITS_DI; break;
255 : case R_EDI:
256 E : mask = LivenessAnalysis::StateHelper::REGBITS_EDI; break;
257 : case R_RDI:
258 i : mask = LivenessAnalysis::StateHelper::REGBITS_RDI; break;
259 : case R_SP:
260 E : mask = LivenessAnalysis::StateHelper::REGBITS_SP; break;
261 : case R_ESP:
262 E : mask = LivenessAnalysis::StateHelper::REGBITS_ESP; break;
263 : case R_RSP:
264 i : mask = LivenessAnalysis::StateHelper::REGBITS_RSP; break;
265 : case R_BP:
266 E : mask = LivenessAnalysis::StateHelper::REGBITS_BP; break;
267 : case R_EBP:
268 E : mask = LivenessAnalysis::StateHelper::REGBITS_EBP; break;
269 : case R_RBP:
270 i : mask = LivenessAnalysis::StateHelper::REGBITS_RBP; break;
271 : default:
272 : // Unhandled registers are ignored.
273 : break;
274 : }
275 :
276 E : return static_cast<RegisterMask>(mask);
277 E : }
278 :
279 E : void LivenessAnalysis::StateHelper::Clear(State* state) {
280 E : DCHECK(state != NULL);
281 E : state->flags_ = 0;
282 E : state->registers_ = 0;
283 E : }
284 :
285 E : void LivenessAnalysis::StateHelper::SetAll(State* state) {
286 E : DCHECK(state != NULL);
287 E : state->flags_ = static_cast<RegisterMask>(StateHelper::REGBITS_ALL);
288 E : state->registers_ = static_cast<RegisterMask>(StateHelper::REGBITS_ALL);
289 E : }
290 :
291 : bool LivenessAnalysis::StateHelper::AreArithmeticFlagsLive(
292 E : const State& state) {
293 E : return (state.flags_ & (D_ZF | D_SF | D_CF | D_OF | D_PF | D_AF)) != 0;
294 E : }
295 :
296 : bool LivenessAnalysis::StateHelper::IsSet(
297 E : const State& state, RegisterMask mask) {
298 E : return (state.registers_ & mask) == mask;
299 E : }
300 :
301 : bool LivenessAnalysis::StateHelper::IsPartiallySet(
302 E : const State& state, RegisterMask mask) {
303 E : return (state.registers_ & mask) != 0;
304 E : }
305 :
306 E : void LivenessAnalysis::StateHelper::Set(RegisterMask mask, State* state) {
307 E : DCHECK(state != NULL);
308 E : state->registers_ |= mask;
309 E : }
310 :
311 E : void LivenessAnalysis::StateHelper::SetFlags(FlagsMask mask, State* state) {
312 E : DCHECK(state != NULL);
313 E : state->flags_ |= mask;
314 E : }
315 :
316 E : void LivenessAnalysis::StateHelper::Copy(const State& src, State* state) {
317 E : DCHECK(state != NULL);
318 E : state->flags_ = src.flags_;
319 E : state->registers_ = src.registers_;
320 E : }
321 :
322 E : bool LivenessAnalysis::StateHelper::Union(const State& src, State* state) {
323 E : DCHECK(state != NULL);
324 :
325 : bool changed = ((state->flags_ | src.flags_) != state->flags_) ||
326 E : ((state->registers_ | src.registers_) != state->registers_);
327 E : state->flags_ |= src.flags_;
328 E : state->registers_ |= src.registers_;
329 E : return changed;
330 E : }
331 :
332 E : void LivenessAnalysis::StateHelper::Subtract(const State& src, State* state) {
333 E : DCHECK(state != NULL);
334 E : state->flags_ &= ~(src.flags_);
335 E : state->registers_ &= ~(src.registers_);
336 E : }
337 :
338 : void LivenessAnalysis::StateHelper::StateDefOperand(
339 E : const _Operand& operand, State* state) {
340 E : DCHECK(state != NULL);
341 E : if (operand.type == O_REG)
342 E : Set(RegisterToRegisterMask(operand.index), state);
343 E : }
344 :
345 : void LivenessAnalysis::StateHelper::StateUseOperand(
346 : const Instruction& instr,
347 : const _Operand& operand,
348 E : State* state) {
349 E : DCHECK(state != NULL);
350 :
351 E : const Representation& repr = instr.representation();
352 :
353 E : switch (operand.type) {
354 : case O_REG:
355 : case O_SMEM:
356 E : Set(RegisterToRegisterMask(operand.index), state);
357 E : break;
358 : case O_MEM:
359 E : Set(RegisterToRegisterMask(operand.index), state);
360 E : Set(RegisterToRegisterMask(repr.base), state);
361 : break;
362 : }
363 E : }
364 :
365 : void LivenessAnalysis::StateHelper::StateUseOperandLHS(
366 : const Instruction& instr,
367 : const _Operand& operand,
368 E : State* state) {
369 E : DCHECK(state != NULL);
370 :
371 E : if (operand.type == O_REG)
372 E : return;
373 E : StateUseOperand(instr, operand, state);
374 E : }
375 :
376 : bool LivenessAnalysis::StateHelper::GetDefsOf(
377 E : const Instruction& instr, State* state) {
378 E : DCHECK(state != NULL);
379 :
380 E : Clear(state);
381 :
382 E : const Representation& repr = instr.representation();
383 :
384 : // Get information on flags (eflags register).
385 E : SetFlags(repr.modifiedFlagsMask | repr.undefinedFlagsMask, state);
386 :
387 : // Handle instructions with 'REP' prefix.
388 E : if ((FLAG_GET_PREFIX(repr.flags) & (FLAG_REPNZ | FLAG_REP)) != 0) {
389 E : switch (repr.opcode) {
390 : case I_MOVS:
391 E : Set(RegisterToRegisterMask(R_ECX), state);
392 E : Set(RegisterToRegisterMask(R_ESI), state);
393 E : Set(RegisterToRegisterMask(R_EDI), state);
394 E : return true;
395 : case I_STOS:
396 E : Set(RegisterToRegisterMask(R_ECX), state);
397 E : Set(RegisterToRegisterMask(R_EDI), state);
398 E : return true;
399 i : default: return false;
400 : }
401 : }
402 :
403 : // Get information on operand (general purpose registers).
404 E : switch (repr.opcode) {
405 : case I_CMP:
406 : case I_FCOM:
407 : case I_FCOMP:
408 : case I_FCOMPP:
409 : case I_FCOMI:
410 : case I_FCOMIP:
411 : case I_FIST:
412 : case I_FISTP:
413 : case I_FST:
414 : case I_FSTP:
415 : case I_TEST:
416 E : return true;
417 : case I_ADD:
418 : case I_ADC:
419 : case I_AND:
420 : case I_DEC:
421 : case I_INC:
422 : case I_FADD:
423 : case I_FADDP:
424 : case I_FILD:
425 : case I_FLD:
426 : case I_FLD1:
427 : case I_FLDZ:
428 : case I_FMUL:
429 : case I_FMULP:
430 : case I_FSUB:
431 : case I_FSUBP:
432 : case I_LEA:
433 : case I_MOV:
434 : case I_MOVZX:
435 : case I_MOVSX:
436 : case I_NEG:
437 : case I_NOT:
438 : case I_OR:
439 : case I_ROL:
440 : case I_ROR:
441 : case I_SAR:
442 : case I_SBB:
443 : case I_SETA:
444 : case I_SETAE:
445 : case I_SETB:
446 : case I_SETBE:
447 : case I_SETG:
448 : case I_SETGE:
449 : case I_SETL:
450 : case I_SETLE:
451 : case I_SETNO:
452 : case I_SETNP:
453 : case I_SETNS:
454 : case I_SETNZ:
455 : case I_SETO:
456 : case I_SETP:
457 : case I_SETS:
458 : case I_SETZ:
459 : case I_SHL:
460 : case I_SHR:
461 : case I_SUB:
462 : case I_XOR:
463 E : StateDefOperand(repr.ops[0], state);
464 E : return true;
465 : case I_POP:
466 : case I_POPF:
467 E : StateDefOperand(repr.ops[0], state);
468 E : Set(RegisterToRegisterMask(R_ESP), state);
469 E : return true;
470 : case I_CALL:
471 : case I_PUSH:
472 : case I_PUSHF:
473 : case I_RET:
474 E : Set(RegisterToRegisterMask(R_ESP), state);
475 E : return true;
476 : case I_LEAVE:
477 E : Set(RegisterToRegisterMask(R_EBP), state);
478 E : Set(RegisterToRegisterMask(R_ESP), state);
479 E : return true;
480 : case I_LAHF:
481 E : Set(REGBITS_AH, state);
482 E : return true;
483 : case I_SAHF:
484 : // Store register ah into flags (fix a DiStorm bug).
485 E : SetFlags(D_AF | D_CF | D_PF | D_SF| D_ZF, state);
486 E : return true;
487 : case I_MOVS:
488 E : Set(RegisterToRegisterMask(R_ESI), state);
489 E : Set(RegisterToRegisterMask(R_EDI), state);
490 E : return true;
491 : case I_STOS:
492 E : Set(RegisterToRegisterMask(R_EDI), state);
493 E : return true;
494 : case I_CWD:
495 E : Set(RegisterToRegisterMask(R_EAX), state);
496 E : return true;
497 : case I_CDQ:
498 E : Set(RegisterToRegisterMask(R_EAX), state);
499 E : Set(RegisterToRegisterMask(R_EDX), state);
500 E : return true;
501 : case I_MUL:
502 : case I_IMUL:
503 E : if (repr.ops[1].type == O_NONE) {
504 : // Destination is implicit.
505 E : switch (repr.ops[0].size) {
506 : case 8:
507 E : Set(RegisterToRegisterMask(R_AX), state);
508 E : return true;
509 : case 16:
510 E : Set(RegisterToRegisterMask(R_AX), state);
511 E : Set(RegisterToRegisterMask(R_DX), state);
512 E : return true;
513 : case 32:
514 E : Set(RegisterToRegisterMask(R_EAX), state);
515 E : Set(RegisterToRegisterMask(R_EDX), state);
516 E : return true;
517 : }
518 i : } else {
519 : // Destination is explicit.
520 E : DCHECK_EQ(repr.opcode, I_IMUL);
521 E : StateDefOperand(repr.ops[0], state);
522 : }
523 E : return false;
524 : default:
525 E : return false;
526 : }
527 :
528 i : NOTREACHED();
529 E : }
530 :
531 : bool LivenessAnalysis::StateHelper::GetUsesOf(
532 E : const Instruction& instr, State* state) {
533 E : DCHECK(state != NULL);
534 :
535 E : Clear(state);
536 :
537 E : const Representation& repr = instr.representation();
538 :
539 : // Get information on flags (eflags register).
540 E : SetFlags(repr.testedFlagsMask, state);
541 :
542 : // Handle a special case: xor-initialization (i.e. xor eax, eax).
543 : if (repr.opcode == I_XOR &&
544 : repr.ops[0].type == O_REG &&
545 : repr.ops[1].type == O_REG &&
546 E : repr.ops[0].index == repr.ops[1].index) {
547 : // We can assume no uses.
548 E : return true;
549 : }
550 :
551 : // Handle instructions with 'REP' prefix.
552 E : if ((FLAG_GET_PREFIX(repr.flags) & (FLAG_REPNZ | FLAG_REP)) != 0) {
553 E : switch (repr.opcode) {
554 : case I_MOVS:
555 E : Set(RegisterToRegisterMask(R_ECX), state);
556 E : Set(RegisterToRegisterMask(R_ESI), state);
557 E : Set(RegisterToRegisterMask(R_EDI), state);
558 E : return true;
559 : case I_STOS:
560 E : Set(RegisterToRegisterMask(R_EAX), state);
561 E : Set(RegisterToRegisterMask(R_ECX), state);
562 E : Set(RegisterToRegisterMask(R_EDI), state);
563 E : return true;
564 i : default: return false;
565 : }
566 : }
567 :
568 : // Get information on operand (general purpose registers).
569 E : switch (repr.opcode) {
570 : case I_ADD:
571 : case I_ADC:
572 : case I_AND:
573 : case I_CMP:
574 : case I_FADD:
575 : case I_FADDP:
576 : case I_FCOM:
577 : case I_FCOMP:
578 : case I_FCOMPP:
579 : case I_FCOMI:
580 : case I_FCOMIP:
581 : case I_FICOM:
582 : case I_FICOMP:
583 : case I_FILD:
584 : case I_FIST:
585 : case I_FISTP:
586 : case I_FLD:
587 : case I_FLD1:
588 : case I_FLDZ:
589 : case I_FMUL:
590 : case I_FMULP:
591 : case I_FST:
592 : case I_FSTP:
593 : case I_FSUB:
594 : case I_FSUBP:
595 : case I_DEC:
596 : case I_INC:
597 : case I_NEG:
598 : case I_NOT:
599 : case I_ROL:
600 : case I_ROR:
601 : case I_OR:
602 : case I_SBB:
603 : case I_SAR:
604 : case I_SHL:
605 : case I_SHR:
606 : case I_SUB:
607 : case I_TEST:
608 : case I_XOR:
609 E : StateUseOperand(instr, repr.ops[0], state);
610 E : StateUseOperand(instr, repr.ops[1], state);
611 E : return true;
612 : case I_SETA:
613 : case I_SETAE:
614 : case I_SETB:
615 : case I_SETBE:
616 : case I_SETG:
617 : case I_SETGE:
618 : case I_SETL:
619 : case I_SETLE:
620 : case I_SETNO:
621 : case I_SETNP:
622 : case I_SETNS:
623 : case I_SETNZ:
624 : case I_SETO:
625 : case I_SETP:
626 : case I_SETS:
627 : case I_SETZ:
628 E : return true;
629 : case I_LEA:
630 : case I_MOV:
631 : case I_MOVZX:
632 : case I_MOVSX:
633 E : StateUseOperandLHS(instr, repr.ops[0], state);
634 E : StateUseOperand(instr, repr.ops[1], state);
635 E : return true;
636 : case I_PUSHF:
637 E : SetFlags(static_cast<FlagsMask>(REGBITS_ALL), state);
638 E : Set(RegisterToRegisterMask(R_ESP), state);
639 E : return true;
640 : case I_LAHF:
641 E : SetFlags(D_AF | D_CF | D_PF | D_SF| D_ZF, state);
642 E : return true;
643 : case I_SAHF:
644 E : Set(REGBITS_AH, state);
645 E : return true;
646 : case I_POP:
647 : case I_POPF:
648 E : StateUseOperandLHS(instr, repr.ops[0], state);
649 E : Set(RegisterToRegisterMask(R_ESP), state);
650 E : return true;
651 : case I_CALL:
652 : case I_PUSH:
653 : case I_RET:
654 E : StateUseOperand(instr, repr.ops[0], state);
655 E : Set(RegisterToRegisterMask(R_ESP), state);
656 E : return true;
657 : case I_LEAVE:
658 E : Set(RegisterToRegisterMask(R_EBP), state);
659 E : Set(RegisterToRegisterMask(R_ESP), state);
660 E : return true;
661 : case I_MOVS:
662 E : Set(RegisterToRegisterMask(R_ESI), state);
663 E : Set(RegisterToRegisterMask(R_EDI), state);
664 E : return true;
665 : case I_STOS:
666 E : Set(RegisterToRegisterMask(R_EAX), state);
667 E : Set(RegisterToRegisterMask(R_EDI), state);
668 E : return true;
669 : case I_CWD:
670 E : Set(RegisterToRegisterMask(R_AX), state);
671 E : return true;
672 : case I_CDQ:
673 E : Set(RegisterToRegisterMask(R_EAX), state);
674 E : return true;
675 : case I_MUL:
676 : case I_IMUL:
677 E : StateUseOperand(instr, repr.ops[0], state);
678 E : StateUseOperand(instr, repr.ops[1], state);
679 E : StateUseOperand(instr, repr.ops[2], state);
680 :
681 E : if (repr.ops[1].type == O_NONE) {
682 : // The second operand is implicit.
683 E : switch (repr.ops[0].size) {
684 : case 8:
685 E : Set(RegisterToRegisterMask(R_AL), state);
686 E : break;
687 : case 16:
688 E : Set(RegisterToRegisterMask(R_AX), state);
689 E : break;
690 : case 32:
691 E : Set(RegisterToRegisterMask(R_EAX), state);
692 E : break;
693 : default:
694 i : return false;
695 : }
696 : }
697 E : return true;
698 : default:
699 E : return false;
700 : }
701 :
702 i : NOTREACHED();
703 E : }
704 :
705 : bool LivenessAnalysis::StateHelper::GetUsesOf(
706 E : const Successor& successor, State* state) {
707 E : DCHECK(state != NULL);
708 E : switch (successor.condition()) {
709 : case Successor::kConditionAbove:
710 : case Successor::kConditionBelowOrEqual:
711 E : SetFlags(D_CF | D_ZF, state);
712 E : return true;
713 : case Successor::kConditionBelow:
714 : case Successor::kConditionAboveOrEqual:
715 E : SetFlags(D_CF, state);
716 E : return true;
717 : case Successor::kConditionEqual:
718 : case Successor::kConditionNotEqual:
719 E : SetFlags(D_ZF, state);
720 E : return true;
721 : case Successor::kConditionGreater:
722 : case Successor::kConditionLessOrEqual:
723 E : SetFlags(D_ZF | D_SF | D_OF, state);
724 E : return true;
725 : case Successor::kConditionLess:
726 : case Successor::kConditionGreaterOrEqual:
727 E : SetFlags(D_SF | D_OF, state);
728 E : return true;
729 : case Successor::kConditionOverflow:
730 : case Successor::kConditionNotOverflow:
731 E : SetFlags(D_OF, state);
732 E : return true;
733 : case Successor::kConditionParity:
734 : case Successor::kConditionNotParity:
735 E : SetFlags(D_PF, state);
736 E : return true;
737 : case Successor::kConditionSigned:
738 : case Successor::kConditionNotSigned:
739 E : SetFlags(D_SF, state);
740 E : return true;
741 : case Successor::kConditionTrue:
742 E : return true;
743 : default:
744 i : return false;
745 : }
746 :
747 i : NOTREACHED();
748 E : }
749 :
750 : } // namespace analysis
751 : } // namespace block_graph
|