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