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 E : : 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 E : RegisterMask mask = StateHelper::RegisterToRegisterMask(
57 : 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 E : instr.IsInterrupt() ||
147 : 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 : RegisterMask LivenessAnalysis::StateHelper::RegisterToRegisterMask(
204 E : uint8_t reg) {
205 : LivenessAnalysis::StateHelper::RegisterBits mask =
206 E : LivenessAnalysis::StateHelper::REGBITS_NONE;
207 E : switch (reg) {
208 : case R_AL:
209 E : mask = LivenessAnalysis::StateHelper::REGBITS_AL; break;
210 : case R_AH:
211 E : mask = LivenessAnalysis::StateHelper::REGBITS_AH; break;
212 : case R_AX:
213 E : mask = LivenessAnalysis::StateHelper::REGBITS_AX; break;
214 : case R_EAX:
215 E : mask = LivenessAnalysis::StateHelper::REGBITS_EAX; break;
216 : case R_RAX:
217 i : mask = LivenessAnalysis::StateHelper::REGBITS_RAX; break;
218 : case R_BL:
219 E : mask = LivenessAnalysis::StateHelper::REGBITS_BL; break;
220 : case R_BH:
221 E : mask = LivenessAnalysis::StateHelper::REGBITS_BH; break;
222 : case R_BX:
223 E : mask = LivenessAnalysis::StateHelper::REGBITS_BX; break;
224 : case R_EBX:
225 E : mask = LivenessAnalysis::StateHelper::REGBITS_EBX; break;
226 : case R_RBX:
227 i : mask = LivenessAnalysis::StateHelper::REGBITS_RBX; break;
228 : case R_CL:
229 E : mask = LivenessAnalysis::StateHelper::REGBITS_CL; break;
230 : case R_CH:
231 E : mask = LivenessAnalysis::StateHelper::REGBITS_CH; break;
232 : case R_CX:
233 E : mask = LivenessAnalysis::StateHelper::REGBITS_CX; break;
234 : case R_ECX:
235 E : mask = LivenessAnalysis::StateHelper::REGBITS_ECX; break;
236 : case R_RCX:
237 i : mask = LivenessAnalysis::StateHelper::REGBITS_RCX; break;
238 : case R_DL:
239 E : mask = LivenessAnalysis::StateHelper::REGBITS_DL; break;
240 : case R_DH:
241 E : mask = LivenessAnalysis::StateHelper::REGBITS_DH; break;
242 : case R_DX:
243 E : mask = LivenessAnalysis::StateHelper::REGBITS_DX; break;
244 : case R_EDX:
245 E : mask = LivenessAnalysis::StateHelper::REGBITS_EDX; break;
246 : case R_RDX:
247 i : mask = LivenessAnalysis::StateHelper::REGBITS_RDX; break;
248 : case R_SI:
249 E : mask = LivenessAnalysis::StateHelper::REGBITS_SI; break;
250 : case R_ESI:
251 E : mask = LivenessAnalysis::StateHelper::REGBITS_ESI; break;
252 : case R_RSI:
253 i : mask = LivenessAnalysis::StateHelper::REGBITS_RSI; break;
254 : case R_DI:
255 E : mask = LivenessAnalysis::StateHelper::REGBITS_DI; break;
256 : case R_EDI:
257 E : mask = LivenessAnalysis::StateHelper::REGBITS_EDI; break;
258 : case R_RDI:
259 i : mask = LivenessAnalysis::StateHelper::REGBITS_RDI; break;
260 : case R_SP:
261 E : mask = LivenessAnalysis::StateHelper::REGBITS_SP; break;
262 : case R_ESP:
263 E : mask = LivenessAnalysis::StateHelper::REGBITS_ESP; break;
264 : case R_RSP:
265 i : mask = LivenessAnalysis::StateHelper::REGBITS_RSP; break;
266 : case R_BP:
267 E : mask = LivenessAnalysis::StateHelper::REGBITS_BP; break;
268 : case R_EBP:
269 E : mask = LivenessAnalysis::StateHelper::REGBITS_EBP; break;
270 : case R_RBP:
271 i : mask = LivenessAnalysis::StateHelper::REGBITS_RBP; break;
272 : default:
273 : // Unhandled registers are ignored.
274 : break;
275 : }
276 :
277 E : return static_cast<RegisterMask>(mask);
278 E : }
279 :
280 E : void LivenessAnalysis::StateHelper::Clear(State* state) {
281 E : DCHECK(state != NULL);
282 E : state->flags_ = 0;
283 E : state->registers_ = 0;
284 E : }
285 :
286 E : void LivenessAnalysis::StateHelper::SetAll(State* state) {
287 E : DCHECK(state != NULL);
288 E : state->flags_ = static_cast<RegisterMask>(StateHelper::REGBITS_ALL);
289 E : state->registers_ = static_cast<RegisterMask>(StateHelper::REGBITS_ALL);
290 E : }
291 :
292 : bool LivenessAnalysis::StateHelper::AreArithmeticFlagsLive(
293 E : const State& state) {
294 E : return (state.flags_ & (D_ZF | D_SF | D_CF | D_OF | D_PF | D_AF)) != 0;
295 E : }
296 :
297 : bool LivenessAnalysis::StateHelper::IsSet(
298 E : const State& state, RegisterMask mask) {
299 E : return (state.registers_ & mask) == mask;
300 E : }
301 :
302 : bool LivenessAnalysis::StateHelper::IsPartiallySet(
303 E : const State& state, RegisterMask mask) {
304 E : return (state.registers_ & mask) != 0;
305 E : }
306 :
307 E : void LivenessAnalysis::StateHelper::Set(RegisterMask mask, State* state) {
308 E : DCHECK(state != NULL);
309 E : state->registers_ |= mask;
310 E : }
311 :
312 E : void LivenessAnalysis::StateHelper::SetFlags(FlagsMask mask, State* state) {
313 E : DCHECK(state != NULL);
314 E : state->flags_ |= mask;
315 E : }
316 :
317 E : void LivenessAnalysis::StateHelper::Copy(const State& src, State* state) {
318 E : DCHECK(state != NULL);
319 E : state->flags_ = src.flags_;
320 E : state->registers_ = src.registers_;
321 E : }
322 :
323 E : bool LivenessAnalysis::StateHelper::Union(const State& src, State* state) {
324 E : DCHECK(state != NULL);
325 :
326 E : bool changed = ((state->flags_ | src.flags_) != state->flags_) ||
327 : ((state->registers_ | src.registers_) != state->registers_);
328 E : state->flags_ |= src.flags_;
329 E : state->registers_ |= src.registers_;
330 E : return changed;
331 E : }
332 :
333 E : void LivenessAnalysis::StateHelper::Subtract(const State& src, State* state) {
334 E : DCHECK(state != NULL);
335 E : state->flags_ &= ~(src.flags_);
336 E : state->registers_ &= ~(src.registers_);
337 E : }
338 :
339 : void LivenessAnalysis::StateHelper::StateDefOperand(
340 E : const _Operand& operand, State* state) {
341 E : DCHECK(state != NULL);
342 E : if (operand.type == O_REG)
343 E : Set(RegisterToRegisterMask(operand.index), state);
344 E : }
345 :
346 : void LivenessAnalysis::StateHelper::StateUseOperand(
347 : const Instruction& instr,
348 : const _Operand& operand,
349 E : State* state) {
350 E : DCHECK(state != NULL);
351 :
352 E : const Representation& repr = instr.representation();
353 :
354 E : switch (operand.type) {
355 : case O_REG:
356 : case O_SMEM:
357 E : Set(RegisterToRegisterMask(operand.index), state);
358 E : break;
359 : case O_MEM:
360 E : Set(RegisterToRegisterMask(operand.index), state);
361 E : Set(RegisterToRegisterMask(repr.base), state);
362 : break;
363 : }
364 E : }
365 :
366 : void LivenessAnalysis::StateHelper::StateUseOperandLHS(
367 : const Instruction& instr,
368 : const _Operand& operand,
369 E : State* state) {
370 E : DCHECK(state != NULL);
371 :
372 E : if (operand.type == O_REG)
373 E : return;
374 E : StateUseOperand(instr, operand, state);
375 E : }
376 :
377 : bool LivenessAnalysis::StateHelper::GetDefsOf(
378 E : const Instruction& instr, State* state) {
379 E : DCHECK(state != NULL);
380 :
381 E : Clear(state);
382 :
383 E : const Representation& repr = instr.representation();
384 :
385 : // Get information on flags (eflags register).
386 E : SetFlags(repr.modifiedFlagsMask | repr.undefinedFlagsMask, state);
387 :
388 : // Handle instructions with 'REP' prefix.
389 E : if ((FLAG_GET_PREFIX(repr.flags) & (FLAG_REPNZ | FLAG_REP)) != 0) {
390 E : switch (repr.opcode) {
391 : case I_MOVS:
392 E : Set(RegisterToRegisterMask(R_ECX), state);
393 E : Set(RegisterToRegisterMask(R_ESI), state);
394 E : Set(RegisterToRegisterMask(R_EDI), state);
395 E : return true;
396 : case I_STOS:
397 E : Set(RegisterToRegisterMask(R_ECX), state);
398 E : Set(RegisterToRegisterMask(R_EDI), state);
399 E : return true;
400 i : default: return false;
401 : }
402 : }
403 :
404 : // Get information on operand (general purpose registers).
405 E : switch (repr.opcode) {
406 : case I_CMP:
407 : case I_FCOM:
408 : case I_FCOMP:
409 : case I_FCOMPP:
410 : case I_FCOMI:
411 : case I_FCOMIP:
412 : case I_FIST:
413 : case I_FISTP:
414 : case I_FST:
415 : case I_FSTP:
416 : case I_TEST:
417 E : return true;
418 : case I_ADD:
419 : case I_ADC:
420 : case I_AND:
421 : case I_DEC:
422 : case I_INC:
423 : case I_FADD:
424 : case I_FADDP:
425 : case I_FILD:
426 : case I_FLD:
427 : case I_FLD1:
428 : case I_FLDZ:
429 : case I_FMUL:
430 : case I_FMULP:
431 : case I_FSUB:
432 : case I_FSUBP:
433 : case I_LEA:
434 : case I_MOV:
435 : case I_MOVZX:
436 : case I_MOVSX:
437 : case I_NEG:
438 : case I_NOT:
439 : case I_OR:
440 : case I_ROL:
441 : case I_ROR:
442 : case I_SAR:
443 : case I_SBB:
444 : case I_SETA:
445 : case I_SETAE:
446 : case I_SETB:
447 : case I_SETBE:
448 : case I_SETG:
449 : case I_SETGE:
450 : case I_SETL:
451 : case I_SETLE:
452 : case I_SETNO:
453 : case I_SETNP:
454 : case I_SETNS:
455 : case I_SETNZ:
456 : case I_SETO:
457 : case I_SETP:
458 : case I_SETS:
459 : case I_SETZ:
460 : case I_SHL:
461 : case I_SHR:
462 : case I_SUB:
463 : case I_XOR:
464 E : StateDefOperand(repr.ops[0], state);
465 E : return true;
466 : case I_POP:
467 : case I_POPF:
468 E : StateDefOperand(repr.ops[0], state);
469 E : Set(RegisterToRegisterMask(R_ESP), state);
470 E : return true;
471 : case I_CALL:
472 : case I_PUSH:
473 : case I_PUSHF:
474 : case I_RET:
475 E : Set(RegisterToRegisterMask(R_ESP), state);
476 E : return true;
477 : case I_LEAVE:
478 E : Set(RegisterToRegisterMask(R_EBP), state);
479 E : Set(RegisterToRegisterMask(R_ESP), state);
480 E : return true;
481 : case I_LAHF:
482 E : Set(REGBITS_AH, state);
483 E : return true;
484 : case I_SAHF:
485 : // Store register ah into flags (fix a DiStorm bug).
486 E : SetFlags(D_AF | D_CF | D_PF | D_SF| D_ZF, state);
487 E : return true;
488 : case I_MOVS:
489 E : Set(RegisterToRegisterMask(R_ESI), state);
490 E : Set(RegisterToRegisterMask(R_EDI), state);
491 E : return true;
492 : case I_STOS:
493 E : Set(RegisterToRegisterMask(R_EDI), state);
494 E : return true;
495 : case I_CWD:
496 E : Set(RegisterToRegisterMask(R_EAX), state);
497 E : return true;
498 : case I_CDQ:
499 E : Set(RegisterToRegisterMask(R_EAX), state);
500 E : Set(RegisterToRegisterMask(R_EDX), state);
501 E : return true;
502 : case I_MUL:
503 : case I_IMUL:
504 E : if (repr.ops[1].type == O_NONE) {
505 : // Destination is implicit.
506 E : switch (repr.ops[0].size) {
507 : case 8:
508 E : Set(RegisterToRegisterMask(R_AX), state);
509 E : return true;
510 : case 16:
511 E : Set(RegisterToRegisterMask(R_AX), state);
512 E : Set(RegisterToRegisterMask(R_DX), state);
513 E : return true;
514 : case 32:
515 E : Set(RegisterToRegisterMask(R_EAX), state);
516 E : Set(RegisterToRegisterMask(R_EDX), state);
517 E : return true;
518 : }
519 i : } else {
520 : // Destination is explicit.
521 E : DCHECK_EQ(repr.opcode, I_IMUL);
522 E : StateDefOperand(repr.ops[0], state);
523 : }
524 E : return false;
525 : default:
526 E : return false;
527 : }
528 :
529 i : NOTREACHED();
530 E : }
531 :
532 : bool LivenessAnalysis::StateHelper::GetUsesOf(
533 E : const Instruction& instr, State* state) {
534 E : DCHECK(state != NULL);
535 :
536 E : Clear(state);
537 :
538 E : const Representation& repr = instr.representation();
539 :
540 : // Get information on flags (eflags register).
541 E : SetFlags(repr.testedFlagsMask, state);
542 :
543 : // Handle a special case: xor-initialization (i.e. xor eax, eax).
544 : if (repr.opcode == I_XOR &&
545 : repr.ops[0].type == O_REG &&
546 E : repr.ops[1].type == O_REG &&
547 : repr.ops[0].index == repr.ops[1].index) {
548 : // We can assume no uses.
549 E : return true;
550 : }
551 :
552 : // Handle instructions with 'REP' prefix.
553 E : if ((FLAG_GET_PREFIX(repr.flags) & (FLAG_REPNZ | FLAG_REP)) != 0) {
554 E : switch (repr.opcode) {
555 : case I_MOVS:
556 E : Set(RegisterToRegisterMask(R_ECX), state);
557 E : Set(RegisterToRegisterMask(R_ESI), state);
558 E : Set(RegisterToRegisterMask(R_EDI), state);
559 E : return true;
560 : case I_STOS:
561 E : Set(RegisterToRegisterMask(R_EAX), state);
562 E : Set(RegisterToRegisterMask(R_ECX), state);
563 E : Set(RegisterToRegisterMask(R_EDI), state);
564 E : return true;
565 i : default: return false;
566 : }
567 : }
568 :
569 : // Get information on operand (general purpose registers).
570 E : switch (repr.opcode) {
571 : case I_ADD:
572 : case I_ADC:
573 : case I_AND:
574 : case I_CMP:
575 : case I_FADD:
576 : case I_FADDP:
577 : case I_FCOM:
578 : case I_FCOMP:
579 : case I_FCOMPP:
580 : case I_FCOMI:
581 : case I_FCOMIP:
582 : case I_FICOM:
583 : case I_FICOMP:
584 : case I_FILD:
585 : case I_FIST:
586 : case I_FISTP:
587 : case I_FLD:
588 : case I_FLD1:
589 : case I_FLDZ:
590 : case I_FMUL:
591 : case I_FMULP:
592 : case I_FST:
593 : case I_FSTP:
594 : case I_FSUB:
595 : case I_FSUBP:
596 : case I_DEC:
597 : case I_INC:
598 : case I_NEG:
599 : case I_NOT:
600 : case I_ROL:
601 : case I_ROR:
602 : case I_OR:
603 : case I_SBB:
604 : case I_SAR:
605 : case I_SHL:
606 : case I_SHR:
607 : case I_SUB:
608 : case I_TEST:
609 : case I_XOR:
610 E : StateUseOperand(instr, repr.ops[0], state);
611 E : StateUseOperand(instr, repr.ops[1], state);
612 E : return true;
613 : case I_SETA:
614 : case I_SETAE:
615 : case I_SETB:
616 : case I_SETBE:
617 : case I_SETG:
618 : case I_SETGE:
619 : case I_SETL:
620 : case I_SETLE:
621 : case I_SETNO:
622 : case I_SETNP:
623 : case I_SETNS:
624 : case I_SETNZ:
625 : case I_SETO:
626 : case I_SETP:
627 : case I_SETS:
628 : case I_SETZ:
629 E : return true;
630 : case I_LEA:
631 : case I_MOV:
632 : case I_MOVZX:
633 : case I_MOVSX:
634 E : StateUseOperandLHS(instr, repr.ops[0], state);
635 E : StateUseOperand(instr, repr.ops[1], state);
636 E : return true;
637 : case I_PUSHF:
638 E : SetFlags(static_cast<FlagsMask>(REGBITS_ALL), state);
639 E : Set(RegisterToRegisterMask(R_ESP), state);
640 E : return true;
641 : case I_LAHF:
642 E : SetFlags(D_AF | D_CF | D_PF | D_SF| D_ZF, state);
643 E : return true;
644 : case I_SAHF:
645 E : Set(REGBITS_AH, state);
646 E : return true;
647 : case I_POP:
648 : case I_POPF:
649 E : StateUseOperandLHS(instr, repr.ops[0], state);
650 E : Set(RegisterToRegisterMask(R_ESP), state);
651 E : return true;
652 : case I_CALL:
653 : case I_PUSH:
654 : case I_RET:
655 E : StateUseOperand(instr, repr.ops[0], state);
656 E : Set(RegisterToRegisterMask(R_ESP), state);
657 E : return true;
658 : case I_LEAVE:
659 E : Set(RegisterToRegisterMask(R_EBP), state);
660 E : Set(RegisterToRegisterMask(R_ESP), state);
661 E : return true;
662 : case I_MOVS:
663 E : Set(RegisterToRegisterMask(R_ESI), state);
664 E : Set(RegisterToRegisterMask(R_EDI), state);
665 E : return true;
666 : case I_STOS:
667 E : Set(RegisterToRegisterMask(R_EAX), state);
668 E : Set(RegisterToRegisterMask(R_EDI), state);
669 E : return true;
670 : case I_CWD:
671 E : Set(RegisterToRegisterMask(R_AX), state);
672 E : return true;
673 : case I_CDQ:
674 E : Set(RegisterToRegisterMask(R_EAX), state);
675 E : return true;
676 : case I_MUL:
677 : case I_IMUL:
678 E : StateUseOperand(instr, repr.ops[0], state);
679 E : StateUseOperand(instr, repr.ops[1], state);
680 E : StateUseOperand(instr, repr.ops[2], state);
681 :
682 E : if (repr.ops[1].type == O_NONE) {
683 : // The second operand is implicit.
684 E : switch (repr.ops[0].size) {
685 : case 8:
686 E : Set(RegisterToRegisterMask(R_AL), state);
687 E : break;
688 : case 16:
689 E : Set(RegisterToRegisterMask(R_AX), state);
690 E : break;
691 : case 32:
692 E : Set(RegisterToRegisterMask(R_EAX), state);
693 E : break;
694 : default:
695 i : return false;
696 : }
697 : }
698 E : return true;
699 : default:
700 E : return false;
701 : }
702 :
703 i : NOTREACHED();
704 E : }
705 :
706 : bool LivenessAnalysis::StateHelper::GetUsesOf(
707 E : const Successor& successor, State* state) {
708 E : DCHECK(state != NULL);
709 E : switch (successor.condition()) {
710 : case Successor::kConditionAbove:
711 : case Successor::kConditionBelowOrEqual:
712 E : SetFlags(D_CF | D_ZF, state);
713 E : return true;
714 : case Successor::kConditionBelow:
715 : case Successor::kConditionAboveOrEqual:
716 E : SetFlags(D_CF, state);
717 E : return true;
718 : case Successor::kConditionEqual:
719 : case Successor::kConditionNotEqual:
720 E : SetFlags(D_ZF, state);
721 E : return true;
722 : case Successor::kConditionGreater:
723 : case Successor::kConditionLessOrEqual:
724 E : SetFlags(D_ZF | D_SF | D_OF, state);
725 E : return true;
726 : case Successor::kConditionLess:
727 : case Successor::kConditionGreaterOrEqual:
728 E : SetFlags(D_SF | D_OF, state);
729 E : return true;
730 : case Successor::kConditionOverflow:
731 : case Successor::kConditionNotOverflow:
732 E : SetFlags(D_OF, state);
733 E : return true;
734 : case Successor::kConditionParity:
735 : case Successor::kConditionNotParity:
736 E : SetFlags(D_PF, state);
737 E : return true;
738 : case Successor::kConditionSigned:
739 : case Successor::kConditionNotSigned:
740 E : SetFlags(D_SF, state);
741 E : return true;
742 : case Successor::kConditionTrue:
743 E : return true;
744 : default:
745 i : return false;
746 : }
747 :
748 i : NOTREACHED();
749 E : }
750 :
751 : } // namespace analysis
752 : } // namespace block_graph
|