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