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 : // Provide internal basic operations on liveness states.
16 :
17 : #ifndef SYZYGY_BLOCK_GRAPH_ANALYSIS_LIVENESS_ANALYSIS_INTERNAL_H_
18 : #define SYZYGY_BLOCK_GRAPH_ANALYSIS_LIVENESS_ANALYSIS_INTERNAL_H_
19 :
20 : #include "base/basictypes.h"
21 : #include "syzygy/block_graph/analysis/liveness_analysis.h"
22 :
23 m : namespace block_graph {
24 m : namespace analysis {
25 :
26 : // This class provide basic operations on liveness states. This is the internal
27 : // implementation and should not be used by the user. For unit testing purposes
28 : // only. Do not use outside of tests.
29 m : class LivenessAnalysis::StateHelper {
30 m : public:
31 : // A Liveness::State contains 2 bitsets to represent live registers/flags.
32 : // On x86, general purpose registers may be accessed partially, thus we
33 : // represent a full register as a 4-bit mask. Thus a register may be
34 : // partially alive.
35 : //
36 : // register mask hex
37 : // al 0001 0x1
38 : // ah 0010 0x2
39 : // ax 0011 0x3
40 : // eax 0111 0x7
41 : // rax 1111 0xF
42 : //
43 : // Flags bitset is represented the same way as DiStorm.
44 : // [D_IF D_DF D_AF D_PF D_OF D_CF D_SF D_ZF] (see distorm.h).
45 :
46 m : typedef State::RegisterMask RegisterMask;
47 m : typedef State::FlagsMask FlagsMask;
48 :
49 m : enum RegisterBits {
50 m : REGBITS_AL = 0x00000001,
51 m : REGBITS_AH = 0x00000002,
52 m : REGBITS_AX = 0x00000003,
53 m : REGBITS_EAX = 0x00000007,
54 m : REGBITS_RAX = 0x0000000F,
55 m : REGBITS_BL = 0x00000010,
56 m : REGBITS_BH = 0x00000020,
57 m : REGBITS_BX = 0x00000030,
58 m : REGBITS_EBX = 0x00000070,
59 m : REGBITS_RBX = 0x000000F0,
60 m : REGBITS_CL = 0x00000100,
61 m : REGBITS_CH = 0x00000200,
62 m : REGBITS_CX = 0x00000300,
63 m : REGBITS_ECX = 0x00000700,
64 m : REGBITS_RCX = 0x00000F00,
65 m : REGBITS_DL = 0x00001000,
66 m : REGBITS_DH = 0x00002000,
67 m : REGBITS_DX = 0x00003000,
68 m : REGBITS_EDX = 0x00007000,
69 m : REGBITS_RDX = 0x0000F000,
70 m : REGBITS_SI = 0x00030000,
71 m : REGBITS_ESI = 0x00070000,
72 m : REGBITS_RSI = 0x000F0000,
73 m : REGBITS_DI = 0x00300000,
74 m : REGBITS_EDI = 0x00700000,
75 m : REGBITS_RDI = 0x00F00000,
76 m : REGBITS_SP = 0x03000000,
77 m : REGBITS_ESP = 0x07000000,
78 m : REGBITS_RSP = 0x0F000000,
79 m : REGBITS_BP = 0x30000000,
80 m : REGBITS_EBP = 0x70000000,
81 m : REGBITS_RBP = 0xF0000000,
82 m : REGBITS_ALL = 0xFFFFFFFF
83 m : };
84 :
85 : // For a given distorm register, returns the corresponding registers mask.
86 : // @param reg A distorm register to convert to a registers mask.
87 : // @returns The resulting registers mask.
88 m : static RegisterMask RegisterToRegisterMask(uint8 reg);
89 :
90 : // Reset the liveness information to assume no registers are live.
91 : // @param state State to clear.
92 m : static void Clear(State* state);
93 :
94 : // Set the liveness information to assume all registers are live.
95 : // @param state to set all registers.
96 m : static void SetAll(State* state);
97 :
98 : // Check if the arithmetic flags have not been proved unused.
99 : // @param state State to check into.
100 : // @returns true if the flags may be used, false otherwise.
101 m : static bool AreArithmeticFlagsLive(const State& state);
102 :
103 : // Check whether the registers in @p mask are 'fully' set in @p state.
104 : // @param state State to inspect.
105 : // @param mask Registers bitset to check.
106 : // @returns true if the registers may be used, false otherwise.
107 m : static bool IsSet(const State& state, RegisterMask mask);
108 :
109 : // Check whether the registers in @p mask mask are 'partially' set.
110 : // @param state State to inspect.
111 : // @param mask Registers bitset to check.
112 : // @returns true if the registers may be used, false otherwise.
113 m : static bool IsPartiallySet(const State& state, RegisterMask mask);
114 :
115 : // Mark the registers in @p mask as live in @p state.
116 : // @param mask Registers bitset to mark as live.
117 : // @param state State to apply modifications.
118 m : static void Set(RegisterMask mask, State* state);
119 :
120 : // Mark the flag in @p mask as live in @p state.
121 : // @param mask Flags bitset to mark as live.
122 : // @param state State to apply modifications.
123 m : static void SetFlags(FlagsMask mask, State* state);
124 :
125 : // Overwrite @p state with the state of @p src.
126 : // @param src State to copy.
127 : // @param state State to receive the copy.
128 m : static void Copy(const State& src, State* state);
129 :
130 : // Merge the state @p src into @p state.
131 : // @param src State to merge with.
132 : // @param state State to apply modifications.
133 : // @returns true if the output state is modified, false otherwise.
134 m : static bool Union(const State& src, State* state);
135 :
136 : // Subtract defined registers in @p src from @p state.
137 : // @param src State to subtract.
138 : // @param state State to apply modifications.
139 m : static void Subtract(const State& src, State* state);
140 :
141 : // Find the registers defined by an operand.
142 : // @param operand Operand to analyze.
143 : // @param state Receives defined registers.
144 m : static void StateDefOperand(const _Operand& operand, State* state);
145 :
146 : // Find the registers used by an operand.
147 : // @param instr Instruction to which belong the operand.
148 : // @param operand Operand to analyze.
149 : // @param state Receives used registers.
150 m : static void StateUseOperand(const Instruction& instr,
151 m : const _Operand& operand,
152 m : State* state);
153 :
154 : // Find the registers used by an operand on left-hand side.
155 : // @param instr Instruction to which belong the operand.
156 : // @param operand Operand to analyze.
157 : // @param state Receives used registers.
158 m : static void StateUseOperandLHS(const Instruction& instr,
159 m : const _Operand& operand,
160 m : State* state);
161 :
162 : // Get the registers defined by the execution of the instruction.
163 : // @param instr Instruction to analyze.
164 : // @param state On success, receives the registers defined by the instruction.
165 : // @returns true if we are able to analyze this instruction, false otherwise.
166 m : static bool GetDefsOf(const Instruction& instr, State* state);
167 :
168 : // Get the registers used by the execution of the instruction.
169 : // @param instr Instruction to analyze.
170 : // @param state On success, receives registers used by the instruction.
171 : // @returns true if we are able to analyze this instruction, false otherwise.
172 m : static bool GetUsesOf(const Instruction& instr, State* state);
173 :
174 : // Get the registers used by the execution of the successor (instruction).
175 : // @param successor Successor to analyze.
176 : // @param state On success, receives registers used by the instruction.
177 : // @returns true if we are able to analyze this successor, false otherwise.
178 m : static bool GetUsesOf(const Successor& successor, State* state);
179 m : };
180 :
181 m : } // namespace analysis
182 m : } // namespace block_graph
183 :
184 : #endif // SYZYGY_BLOCK_GRAPH_ANALYSIS_LIVENESS_ANALYSIS_INTERNAL_H_
|