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