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