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 a liveness analysis of a subgraph for x86 general
16 : // purpose registers and flags.
17 : //
18 : // The liveness analysis is a backward analysis which tries to determine which
19 : // registers are potentially alive (may be in use) and which registers are
20 : // absolutely dead (cannot be used on any path).
21 : //
22 : // A global analysis computes liveness information for a whole function.
23 : // A local analysis computes liveness information for a single basic block.
24 : //
25 : // See: http://en.wikipedia.org/wiki/Live_variable_analysis
26 :
27 : #ifndef SYZYGY_BLOCK_GRAPH_ANALYSIS_LIVENESS_ANALYSIS_H_
28 : #define SYZYGY_BLOCK_GRAPH_ANALYSIS_LIVENESS_ANALYSIS_H_
29 :
30 : #include <map>
31 :
32 : #include "base/basictypes.h"
33 : #include "syzygy/block_graph/basic_block.h"
34 : #include "syzygy/block_graph/basic_block_subgraph.h"
35 :
36 m : namespace block_graph {
37 m : namespace analysis {
38 :
39 : // This class implements a local and a global liveness analysis on a subgraph.
40 : //
41 : // The liveness analysis is a conservative analysis which tries to prove that
42 : // some registers are unused and the others may be used. When the analysis is
43 : // unable to manage a concept (jump-table, indirect call, calling-convention,
44 : // ...), it simply assumes every register is in use (the most conservative
45 : // decision).
46 : //
47 : // An instance of 'LivenessAnalysis' keeps track of live registers inside the
48 : // 'State' data structure (bitset of registers). To use the information provided
49 : // by this analysis, the instructions in the basic block must be visited in
50 : // reverse order and a call to 'PropagateBackward' performed on each one. After
51 : // the call, the 'State' contains the live registers and flags before
52 : // instruction execution.
53 : //
54 : // Example:
55 : //
56 : // LivenessAnalysis liveness;
57 : // LivenessAnalysis::State state;
58 : //
59 : // liveness.PropagateBackward(&inst, &state);
60 : // if (!state.IsLive(core::eax)) {
61 : // // Register eax is not used, and may be overwritten.
62 : // }
63 : //
64 : // or
65 : //
66 : // liveness.GetStateAtEntryOf(bb, &state);
67 : // if (!state.IsLive(core::eax)) {
68 : // // Register eax is not used, and may be overwritten.
69 : // }
70 : //
71 : // Local analysis
72 : // --------------
73 : //
74 : // The local liveness analysis does not need any computation before use.
75 : // The analysis assumes all live registers at the end of a basic block.
76 : //
77 : // Example:
78 : //
79 : // LivenessAnalysis liveness;
80 : // LivenessAnalysis::State state;
81 : //
82 : // BasicBlock::Instructions::reverse_iterator iter = instructions.rbegin();
83 : // for (; iter != instructions.rend(); ++iter) {
84 : // const Instruction& instr = *iter;
85 : // liveness.PropagateBackward(&instr, &state);
86 : // [do something with liveness information in state...]
87 : // }
88 : //
89 : //
90 : // Global analysis
91 : // ---------------
92 : //
93 : // The global liveness analysis needs a pre-computation pass before any use.
94 : // The analysis internally keeps track of all alive registers at the beginning
95 : // of each basic block.
96 : //
97 : // Local modifications inside a basic block do not invalidate the global
98 : // analysis except if a new live range escapes the scope of the basic block. In
99 : // that case, the whole analysis is invalid and must be recomputed.
100 : //
101 : // Example:
102 : //
103 : // LivenessAnalysis liveness;
104 : // LivenessAnalysis::State state;
105 : //
106 : // // Perform the global analysis.
107 : // liveness.Analyze(subgraph);
108 : //
109 : // // Load the state at the end of the basic block.
110 : // liveness.GetStateAtExitOf(bb, &state);
111 : // BasicBlock::Instructions::reverse_iterator iter = instructions.rbegin();
112 : // for (; iter != instructions.rend(); ++iter) {
113 : // const Instruction& instr = *iter;
114 : // liveness.PropagateBackward(&instr, &state);
115 : // [do something with liveness information in state...]
116 : // }
117 :
118 m : class LivenessAnalysis {
119 m : public:
120 m : typedef block_graph::BasicBlockSubGraph BasicBlockSubGraph;
121 :
122 m : class State;
123 m : class StateHelper;
124 :
125 m : LivenessAnalysis();
126 :
127 : // Get the registers alive at the entry of a basic block.
128 : // When running in local mode, all registers are assumed alive.
129 : // @param bb Basic block to analyze.
130 : // @param state Receives registers alive at entry of basic block.
131 m : void GetStateAtEntryOf(const BasicBlock* bb, State* state) const;
132 :
133 : // Get the registers alive at the exit of a basic block, before running
134 : // any successors. When running in local mode, all registers are assumed
135 : // alive.
136 : // @param bb Basic block to analyze.
137 : // @param state Receives registers alive at basic block exit.
138 m : void GetStateAtExitOf(const BasicBlock* bb, State* state) const;
139 :
140 : // Simulate the backward execution of an instruction and update the liveness
141 : // information in @p state to reflect side effects of @p instr.
142 : // @param instr Instruction to analyze.
143 : // @param state Receives the updated state (defs and uses).
144 m : static void PropagateBackward(const Instruction& instr, State* state);
145 :
146 : // Perform a global analysis and keep track of liveness information for each
147 : // basic block.
148 : // @param subgraph Subgraph to apply the analysis.
149 m : void Analyze(const BasicBlockSubGraph* subgraph);
150 :
151 m : private:
152 : // Contains the registers alive at entry of each basic block.
153 m : typedef std::map<const BasicBlock*, State> LiveMap;
154 m : LiveMap live_in_;
155 :
156 m : DISALLOW_COPY_AND_ASSIGN(LivenessAnalysis);
157 m : };
158 :
159 : // This class contains the liveness information at a given program point.
160 m : class LivenessAnalysis::State {
161 m : public:
162 m : typedef uint32 RegisterMask;
163 m : typedef uint32 FlagsMask;
164 :
165 : // On creation, a state assumes all registers alive.
166 m : State();
167 :
168 : // Copy the state @p state.
169 : // @param state State to copy.
170 m : State(const State& state);
171 :
172 : // Check if a register has not been proven unused.
173 : // @param reg Register to check liveness information.
174 : // @returns true if the register may be alive, false otherwise.
175 m : bool IsLive(const core::Register& reg) const;
176 :
177 : // Check if the arithmetic flags has not been proved unused.
178 : // @returns true if the flags may be used, false otherwise.
179 m : bool AreArithmeticFlagsLive() const;
180 :
181 m : private:
182 m : friend class LivenessAnalysis::StateHelper;
183 :
184 : // Contains liveness of general purpose registers (eax, ebx, ... esp, ebp).
185 m : RegisterMask registers_;
186 : // Contains liveness of arithmetic flags (eflags).
187 m : FlagsMask flags_;
188 m : };
189 :
190 m : } // namespace analysis
191 m : } // namespace block_graph
192 :
193 : #endif // SYZYGY_BLOCK_GRAPH_ANALYSIS_LIVENESS_ANALYSIS_H_
|