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/memory_access_analysis.h"
16 :
17 : #include <queue>
18 : #include <set>
19 : #include <vector>
20 :
21 : // TODO(etienneb): liveness analysis internal should be hoisted to an
22 : // instructions helper namespace, and shared between analysis. It is quite
23 : // common to get the information on registers defined or used by an
24 : // instruction, or the memory operand read and written.
25 : #include "syzygy/assm/assembler.h"
26 : #include "syzygy/block_graph/analysis/liveness_analysis_internal.h"
27 :
28 : #include "mnemonics.h" // NOLINT
29 :
30 : namespace block_graph {
31 : namespace analysis {
32 :
33 : namespace {
34 :
35 : using block_graph::Operand;
36 : typedef assm::RegisterId RegisterId;
37 : typedef block_graph::BasicBlockSubGraph::BasicBlock BasicBlock;
38 : typedef block_graph::BasicBlockSubGraph::BasicBlock::Instructions Instructions;
39 :
40 : } // namespace
41 :
42 E : MemoryAccessAnalysis::MemoryAccessAnalysis() {
43 E : }
44 :
45 : void MemoryAccessAnalysis::GetStateAtEntryOf(const BasicBlock* bb,
46 E : State* state) const {
47 : // This function accepts a NULL basic block and returns a safe state.
48 E : DCHECK(state != NULL);
49 :
50 E : state->Clear();
51 :
52 E : if (bb == NULL)
53 E : return;
54 :
55 : // Skip unknown basic block.
56 E : StateMap::const_iterator bbentry_state = states_.find(bb);
57 E : if (bbentry_state == states_.end())
58 E : return;
59 :
60 : // Copy basic block memory information to state.
61 E : *state = bbentry_state->second;
62 E : }
63 :
64 : void MemoryAccessAnalysis::PropagateForward(const Instruction& instr,
65 E : State* state) {
66 E : DCHECK(state != NULL);
67 :
68 E : state->Execute(instr);
69 :
70 E : if (instr.IsCall() || instr.IsControlFlow()) {
71 E : state->Clear();
72 E : return;
73 : }
74 :
75 : // TODO(etienneb): Find a way to expose the defs concept.
76 E : LivenessAnalysis::State defs;
77 E : LivenessAnalysis::StateHelper::Clear(&defs);
78 E : if (!LivenessAnalysis::StateHelper::GetDefsOf(instr, &defs)) {
79 E : state->Clear();
80 E : return;
81 : }
82 :
83 E : for (size_t r = 0; r < assm::kRegister32Count; ++r) {
84 E : if (defs.IsLive(assm::kRegisters32[r])) {
85 : // This register is modified, clear all memory accesses with this base.
86 E : state->active_memory_accesses_[r].clear();
87 : }
88 E : }
89 E : }
90 :
91 : bool MemoryAccessAnalysis::Intersect(const block_graph::BasicBlock* bb,
92 E : const State& state) {
93 E : StateMap::iterator bbentry_state = states_.find(bb);
94 E : if (bbentry_state == states_.end()) {
95 : // First intersection, create a set. This set will never grow again.
96 E : states_[bb] = state;
97 E : return true;
98 : }
99 :
100 E : bool changed = false;
101 : // Subtract non redundant memory accesses.
102 E : for (size_t r = 0; r < assm::kRegister32Count; ++r) {
103 E : const std::set<int32>& from = state.active_memory_accesses_[r];
104 E : std::set<int32>& to = bbentry_state->second.active_memory_accesses_[r];
105 :
106 : // In-place intersection. Remove unknown accesses of the destination set.
107 E : std::set<int32>::iterator it1 = to.begin();
108 E : std::set<int32>::const_iterator it2 = from.begin();
109 E : while (it1 != to.end()) {
110 E : if (it2 == from.end() || *it1 < *it2) {
111 E : std::set<int32>::iterator old = it1;
112 E : ++it1;
113 E : to.erase(old);
114 E : changed = true;
115 E : } else if (*it2 < *it1) {
116 E : ++it2;
117 E : } else { // *it1 == *it2
118 E : ++it1;
119 E : ++it2;
120 : }
121 E : }
122 E : }
123 :
124 E : return changed;
125 E : }
126 :
127 : // This function performs a global redundant memory access analysis.
128 : // It is a fix-point algorithm that produce the minimal set of memory locations,
129 : // at the entry of each basic block. The algorithm uses a work-list to follow
130 : // the control flow and re-insert each modified basic block into the work-list.
131 : // When the end of a basic block is reached, the algorithm performs the
132 : // intersection of the current state with all its successors.
133 E : void MemoryAccessAnalysis::Analyze(const BasicBlockSubGraph* subgraph) {
134 E : DCHECK(subgraph != NULL);
135 :
136 E : std::queue<const BasicBlock*> working;
137 E : std::set<const BasicBlock*> marked;
138 :
139 E : states_.clear();
140 :
141 : // Find initial basic blocks (entry-points), add them to working queue.
142 : const BasicBlockSubGraph::BlockDescriptionList& descriptions =
143 E : subgraph->block_descriptions();
144 : BasicBlockSubGraph::BlockDescriptionList::const_iterator descr_iter =
145 E : descriptions.begin();
146 E : for (; descr_iter != descriptions.end(); ++descr_iter) {
147 : const BasicBlockSubGraph::BasicBlockOrdering& original_order =
148 E : descr_iter->basic_block_order;
149 E : if (original_order.empty())
150 i : continue;
151 E : const BasicBlock* head = original_order.front();
152 E : if (marked.insert(head).second) {
153 E : working.push(original_order.front());
154 E : State empty;
155 E : Intersect(head, empty);
156 E : }
157 E : }
158 :
159 E : DCHECK(!working.empty());
160 :
161 : // Working set algorithm until fixed point.
162 E : while (!working.empty()) {
163 E : const BasicBlock* bb = working.front();
164 E : working.pop();
165 E : marked.erase(bb);
166 :
167 E : const BasicCodeBlock* bb_code = BasicCodeBlock::Cast(bb);
168 E : if (bb_code == NULL) {
169 : // Invalidate all.
170 i : states_.clear();
171 i : return;
172 : }
173 :
174 E : State state;
175 E : GetStateAtEntryOf(bb, &state);
176 :
177 : // Walk through this basic block to obtain an updated state.
178 E : const Instructions& instructions = bb_code->instructions();
179 E : Instructions::const_iterator inst_iter = instructions.begin();
180 E : for ( ; inst_iter != instructions.end(); ++inst_iter) {
181 E : const Instruction& inst = *inst_iter;
182 E : PropagateForward(inst, &state);
183 E : }
184 :
185 : // Commit updated state to successors, and re-insert modified basic blocks
186 : // to the working queue to be processed again.
187 E : const BasicBlock::Successors& successors = bb_code->successors();
188 E : BasicBlock::Successors::const_iterator succ = successors.begin();
189 E : for (; succ != successors.end(); ++succ) {
190 E : BasicBlock* basic_block = succ->reference().basic_block();
191 E : if (basic_block == NULL) {
192 : // Invalidate all.
193 E : states_.clear();
194 E : return;
195 : }
196 :
197 : // Intersect current state with successor 'basic_block'.
198 E : bool changed = Intersect(basic_block, state);
199 E : if (changed) {
200 : // When not already in working queue, mark and add it.
201 E : if (marked.insert(basic_block).second)
202 E : working.push(basic_block);
203 : }
204 E : }
205 E : }
206 E : }
207 :
208 E : MemoryAccessAnalysis::State::State() {
209 E : }
210 :
211 E : MemoryAccessAnalysis::State::State(const State& state) {
212 E : for (size_t r = 0; r < assm::kRegister32Count; ++r) {
213 E : active_memory_accesses_[r] = state.active_memory_accesses_[r];
214 E : }
215 E : }
216 :
217 : bool MemoryAccessAnalysis::State::HasNonRedundantAccess(
218 E : const Instruction& instr) const {
219 E : const _DInst& repr = instr.representation();
220 :
221 : // Load effective address instruction do not perform a memory access.
222 E : if (repr.opcode == I_LEA)
223 E : return false;
224 :
225 : // Skip string instructions.
226 E : if ((FLAG_GET_PREFIX(repr.flags) & (FLAG_REPNZ | FLAG_REP)) != 0)
227 E : return true;
228 :
229 : // Check each operand to find non redundant access.
230 E : for (size_t op_id = 0; op_id < OPERANDS_NO; ++op_id) {
231 E : const _Operand& op = repr.ops[op_id];
232 :
233 : // Filter unrecognized addressing mode.
234 E : switch (op.type) {
235 : case O_DISP:
236 : case O_MEM:
237 E : return true;
238 : case O_SMEM: {
239 E : if (op.index < R_EAX || op.index > R_EDI)
240 i : return true;
241 :
242 : // Simple memory dereference with optional displacement.
243 E : RegisterId base_reg_id = core::GetRegisterId(op.index);
244 E : DCHECK_LE(assm::kRegister32Min, base_reg_id);
245 E : DCHECK_LT(base_reg_id, assm::kRegister32Max);
246 E : size_t base_reg = base_reg_id - assm::kRegister32Min;
247 :
248 E : BasicBlockReference reference;
249 E : if (instr.FindOperandReference(op_id, &reference))
250 E : return true;
251 :
252 E : const std::set<int32>& accesses = active_memory_accesses_[base_reg];
253 E : if (accesses.find(repr.disp) == accesses.end())
254 E : return true;
255 E : }
256 : break;
257 : }
258 E : }
259 :
260 E : return false;
261 E : }
262 :
263 E : void MemoryAccessAnalysis::State::Execute(const Instruction& instr) {
264 E : const _DInst& repr = instr.representation();
265 :
266 : // Skip strings instructions.
267 E : if ((FLAG_GET_PREFIX(repr.flags) & (FLAG_REPNZ | FLAG_REP)) != 0)
268 E : return;
269 :
270 : // Load effective address instruction do not perform a memory access.
271 E : if (repr.opcode == I_LEA)
272 E : return;
273 :
274 : // For each operand, insert them as a redundant access.
275 E : for (size_t op_id = 0; op_id < OPERANDS_NO; ++op_id) {
276 E : const _Operand& op = repr.ops[op_id];
277 :
278 E : if (op.type != O_SMEM)
279 E : continue;
280 :
281 E : if (op.index < R_EAX || op.index > R_EDI)
282 i : continue;
283 :
284 : // Simple memory dereference with optional displacement.
285 E : RegisterId base_reg_id = core::GetRegisterId(op.index);
286 E : DCHECK_LE(assm::kRegister32Min, base_reg_id);
287 E : DCHECK_LT(base_reg_id, assm::kRegister32Max);
288 E : size_t base_reg = base_reg_id - assm::kRegister32Min;
289 :
290 E : BasicBlockReference reference;
291 E : if (instr.FindOperandReference(op_id, &reference))
292 E : continue;
293 :
294 E : active_memory_accesses_[base_reg].insert(repr.disp);
295 E : }
296 E : }
297 :
298 E : void MemoryAccessAnalysis::State::Clear() {
299 E : for (size_t r = 0; r < assm::kRegister32Count; ++r) {
300 E : active_memory_accesses_[r].clear();
301 E : }
302 E : }
303 :
304 : } // namespace analysis
305 : } // namespace block_graph
|