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