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 : // A class that performs an analysis to detect redundant memory accesses over
16 : // a control flow graph.
17 : //
18 : // The redundant memory accesses is a forward analysis which tries to determine
19 : // which memory locations are already accessed, on every possible path, at a
20 : // giving program point.
21 : //
22 : // A global analysis computes information for a whole function by keeping
23 : // internally a state at each basic block entry.
24 : // A local analysis computes information for a single basic block, and does not
25 : // keep any state.
26 : //
27 : // See: http://en.wikipedia.org/wiki/Data-flow_analysis
28 : // http://en.wikipedia.org/wiki/Available_expression
29 :
30 : #ifndef SYZYGY_BLOCK_GRAPH_ANALYSIS_MEMORY_ACCESS_ANALYSIS_H_
31 : #define SYZYGY_BLOCK_GRAPH_ANALYSIS_MEMORY_ACCESS_ANALYSIS_H_
32 :
33 : #include "base/basictypes.h"
34 : #include "syzygy/block_graph/basic_block.h"
35 : #include "syzygy/block_graph/basic_block_assembler.h"
36 : #include "syzygy/block_graph/basic_block_subgraph.h"
37 :
38 m : namespace block_graph {
39 m : namespace analysis {
40 :
41 : // This class implements a local and a global redundant memory access analysis
42 : // on a subgraph.
43 : //
44 : // The redundant memory access analysis is a conservative analysis which tries
45 : // to prove that a memory location was previously used by the execution of a
46 : // instruction for every possible path that may reach the current memory access.
47 : // On failure, the analysis assume the memory access as non redundant.
48 : //
49 : // An instance of 'MemoryAccessAnalysis' keeps track of memory accesses done
50 : // inside the 'State' data structure. To use the information provided
51 : // by this analysis, the instructions in the basic block must be visited in
52 : // order and a call to 'PropagateForward' must be performed on each one. After
53 : // the call, the 'State' contains the set of redundant memory accesses after the
54 : // instruction execution.
55 : //
56 : // Example:
57 : //
58 : // MemoryAccessAnalysis memory_access;
59 : // MemoryAccessAnalysis::State state;
60 : //
61 : // if (state.HasNonRedundantAccess(inst)) {
62 : // // Do something with a non redundant memory access.
63 : // }
64 : // // Move state after the current instruction.
65 : // memory_access.PropagateForward(&inst, &state);
66 : //
67 : // Local analysis
68 : // --------------
69 : //
70 : // The local analysis does not need any computation before use.
71 : // The analysis assumes an empty state at the beginning of each basic block.
72 : //
73 : // Example:
74 : //
75 : // MemoryAccessAnalysis memory_access;
76 : // MemoryAccessAnalysis::State state;
77 : //
78 : // BasicBlock::Instructions::iterator iter = instructions.begin();
79 : // memory_access.GetStateAtEntryOf(bb, &state);
80 : // for (; iter != instructions.end(); ++iter) {
81 : // const Instruction& instr = *iter;
82 : // [do something with redundancy information in state...]
83 : // memory_access.PropagateForward(&instr, &state);
84 : // }
85 : //
86 : // Global analysis
87 : // ---------------
88 : //
89 : // The global analysis needs a pre-computation pass before any use.
90 : // The analysis internally keeps track of a state at the beginning
91 : // of each basic block.
92 : //
93 : // Example:
94 : //
95 : // MemoryAccessAnalysis memory_access;
96 : // MemoryAccessAnalysis::State state;
97 : //
98 : // // Perform the global analysis.
99 : // memory_access.Analyze(subgraph);
100 : //
101 : // BasicBlock::Instructions::iterator iter = instructions.begin();
102 : // for (; iter != instructions.end(); ++iter) {
103 : // const Instruction& instr = *iter;
104 : // [do something with redundancy information in state...]
105 : // liveness.PropagateForward(&instr, &state);
106 : // }
107 :
108 m : class MemoryAccessAnalysis {
109 m : public:
110 m : typedef block_graph::BasicBlockSubGraph BasicBlockSubGraph;
111 :
112 : // Forward declarations.
113 m : class State;
114 :
115 m : MemoryAccessAnalysis();
116 :
117 : // Gets the memory accesses already done at the entry of a basic block.
118 : // When running in local mode, no memory accesses are assumed.
119 : // @param bb Basic block to analyze.
120 : // @param state Receives the set of memory location accessed.
121 m : void GetStateAtEntryOf(const BasicBlock* bb, State* state) const;
122 :
123 : // Simulates the forward execution of an instruction and update the memory
124 : // access information in @p state to reflect side effects of @p instr.
125 : // @param instr Instruction to analyze.
126 : // @param state State to update.
127 m : static void PropagateForward(const Instruction& instr, State* state);
128 :
129 : // Performs a global analysis.
130 : // @param subgraph Subgraph to analyze.
131 m : void Analyze(const BasicBlockSubGraph* subgraph);
132 :
133 m : protected:
134 : // Perform the intersection of the set of memory accesses in @p state with the
135 : // the set kept by the analysis for the basic block @p bb. On the first
136 : // intersection of a basic block, @p state is considered the first set for
137 : // @p bb and is fully copied.
138 m : bool Intersect(const block_graph::BasicBlock* bb, const State& state);
139 :
140 : // Data structure to keep a set of memory locations for each basic block.
141 m : typedef std::map<const block_graph::BasicBlock*,State> StateMap;
142 m : StateMap states_;
143 :
144 m : private:
145 m : DISALLOW_COPY_AND_ASSIGN(MemoryAccessAnalysis);
146 m : };
147 :
148 : // This class contains the memory access information at a given program point.
149 : // The implementation only supports memory access through a single base register
150 : // (e.g. [eax] or [esi+12]). For each general purpose register (eax, ebx, ecx,
151 : // edx, esi, edi, esp, ebp) we keep a set of offsets accessed via the base.
152 m : class MemoryAccessAnalysis::State {
153 m : public:
154 : // On creation, a state is assumed to be empty.
155 m : State();
156 :
157 : // Copy the state @p state.
158 : // @param state State to copy.
159 m : State(const State& state);
160 :
161 : // Check whether @p instr has a non redundant memory access.
162 : // @param instr The instruction on which we need to check each memory operand.
163 : // @returns true if memory accesses are redundant, false otherwise.
164 m : bool HasNonRedundantAccess(const Instruction& instr) const;
165 :
166 m : protected:
167 : // Remove all accessed memory locations from state.
168 m : void Clear();
169 :
170 : // Simulate the execution of @intr and keep track of memory locations
171 : // accessed.
172 : // @param instr Instruction to analyze.
173 m : void State::Execute(const Instruction& instr);
174 :
175 : // Contains active memory accesses. For each base register, we keep a set of
176 : // distances (displacements) done via the base register.
177 m : std::set<int32> active_memory_accesses_[core::kRegisterMax];
178 :
179 m : friend class MemoryAccessAnalysis;
180 m : };
181 :
182 m : } // namespace analysis
183 m : } // namespace block_graph
184 :
185 : #endif // SYZYGY_BLOCK_GRAPH_ANALYSIS_MEMORY_ACCESS_ANALYSIS_H_
|