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_NONE = 0x00000000,
51 m : REGBITS_AL = 0x00000001,
52 m : REGBITS_AH = 0x00000002,
53 m : REGBITS_AX = 0x00000003,
54 m : REGBITS_EAX = 0x00000007,
55 m : REGBITS_RAX = 0x0000000F,
56 m : REGBITS_BL = 0x00000010,
57 m : REGBITS_BH = 0x00000020,
58 m : REGBITS_BX = 0x00000030,
59 m : REGBITS_EBX = 0x00000070,
60 m : REGBITS_RBX = 0x000000F0,
61 m : REGBITS_CL = 0x00000100,
62 m : REGBITS_CH = 0x00000200,
63 m : REGBITS_CX = 0x00000300,
64 m : REGBITS_ECX = 0x00000700,
65 m : REGBITS_RCX = 0x00000F00,
66 m : REGBITS_DL = 0x00001000,
67 m : REGBITS_DH = 0x00002000,
68 m : REGBITS_DX = 0x00003000,
69 m : REGBITS_EDX = 0x00007000,
70 m : REGBITS_RDX = 0x0000F000,
71 m : REGBITS_SI = 0x00030000,
72 m : REGBITS_ESI = 0x00070000,
73 m : REGBITS_RSI = 0x000F0000,
74 m : REGBITS_DI = 0x00300000,
75 m : REGBITS_EDI = 0x00700000,
76 m : REGBITS_RDI = 0x00F00000,
77 m : REGBITS_SP = 0x03000000,
78 m : REGBITS_ESP = 0x07000000,
79 m : REGBITS_RSP = 0x0F000000,
80 m : REGBITS_BP = 0x30000000,
81 m : REGBITS_EBP = 0x70000000,
82 m : REGBITS_RBP = 0xF0000000,
83 m : REGBITS_ALL = 0xFFFFFFFF
84 m : };
85 :
86 : // For a given distorm register, returns the corresponding registers mask.
87 : // @param reg A distorm register to convert to a registers mask.
88 : // @returns The resulting registers mask.
89 m : static RegisterMask RegisterToRegisterMask(uint8 reg);
90 :
91 : // Reset the liveness information to assume no registers are live.
92 : // @param state State to clear.
93 m : static void Clear(State* state);
94 :
95 : // Set the liveness information to assume all registers are live.
96 : // @param state to set all registers.
97 m : static void SetAll(State* state);
98 :
99 : // Check if the arithmetic flags have not been proved unused.
100 : // @param state State to check into.
101 : // @returns true if the flags may be used, false otherwise.
102 m : static bool AreArithmeticFlagsLive(const State& state);
103 :
104 : // Check whether the registers in @p mask are 'fully' set in @p state.
105 : // @param state State to inspect.
106 : // @param mask Registers bitset to check.
107 : // @returns true if the registers may be used, false otherwise.
108 m : static bool IsSet(const State& state, RegisterMask mask);
109 :
110 : // Check whether the registers in @p mask mask are 'partially' set.
111 : // @param state State to inspect.
112 : // @param mask Registers bitset to check.
113 : // @returns true if the registers may be used, false otherwise.
114 m : static bool IsPartiallySet(const State& state, RegisterMask mask);
115 :
116 : // Mark the registers in @p mask as live in @p state.
117 : // @param mask Registers bitset to mark as live.
118 : // @param state State to apply modifications.
119 m : static void Set(RegisterMask mask, State* state);
120 :
121 : // Mark the flag in @p mask as live in @p state.
122 : // @param mask Flags bitset to mark as live.
123 : // @param state State to apply modifications.
124 m : static void SetFlags(FlagsMask mask, State* state);
125 :
126 : // Overwrite @p state with the state of @p src.
127 : // @param src State to copy.
128 : // @param state State to receive the copy.
129 m : static void Copy(const State& src, State* state);
130 :
131 : // Merge the state @p src into @p state.
132 : // @param src State to merge with.
133 : // @param state State to apply modifications.
134 : // @returns true if the output state is modified, false otherwise.
135 m : static bool Union(const State& src, State* state);
136 :
137 : // Subtract defined registers in @p src from @p state.
138 : // @param src State to subtract.
139 : // @param state State to apply modifications.
140 m : static void Subtract(const State& src, State* state);
141 :
142 : // Find the registers defined by an operand.
143 : // @param operand Operand to analyze.
144 : // @param state Receives defined registers.
145 m : static void StateDefOperand(const _Operand& operand, State* state);
146 :
147 : // Find the registers used by an operand.
148 : // @param instr Instruction to which belong the operand.
149 : // @param operand Operand to analyze.
150 : // @param state Receives used registers.
151 m : static void StateUseOperand(const Instruction& instr,
152 m : const _Operand& operand,
153 m : State* state);
154 :
155 : // Find the registers used by an operand on left-hand side.
156 : // @param instr Instruction to which belong the operand.
157 : // @param operand Operand to analyze.
158 : // @param state Receives used registers.
159 m : static void StateUseOperandLHS(const Instruction& instr,
160 m : const _Operand& operand,
161 m : State* state);
162 :
163 : // Get the registers defined by the execution of the instruction.
164 : // @param instr Instruction to analyze.
165 : // @param state On success, receives the registers defined by the instruction.
166 : // @returns true if we are able to analyze this instruction, false otherwise.
167 m : static bool GetDefsOf(const Instruction& instr, State* state);
168 :
169 : // Get the registers used by the execution of the instruction.
170 : // @param instr Instruction to analyze.
171 : // @param state On success, receives registers used by the instruction.
172 : // @returns true if we are able to analyze this instruction, false otherwise.
173 m : static bool GetUsesOf(const Instruction& instr, State* state);
174 :
175 : // Get the registers used by the execution of the successor (instruction).
176 : // @param successor Successor to analyze.
177 : // @param state On success, receives registers used by the instruction.
178 : // @returns true if we are able to analyze this successor, false otherwise.
179 m : static bool GetUsesOf(const Successor& successor, State* state);
180 m : };
181 :
182 m : } // namespace analysis
183 m : } // namespace block_graph
184 :
185 : #endif // SYZYGY_BLOCK_GRAPH_ANALYSIS_LIVENESS_ANALYSIS_INTERNAL_H_
|