Mercurial > hg > graal-compiler
comparison src/share/vm/compiler/methodLiveness.hpp @ 0:a61af66fc99e jdk7-b24
Initial load
author | duke |
---|---|
date | Sat, 01 Dec 2007 00:00:00 +0000 |
parents | |
children | 37f87013dfd8 |
comparison
equal
deleted
inserted
replaced
-1:000000000000 | 0:a61af66fc99e |
---|---|
1 /* | |
2 * Copyright 1998-2006 Sun Microsystems, Inc. All Rights Reserved. | |
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. | |
4 * | |
5 * This code is free software; you can redistribute it and/or modify it | |
6 * under the terms of the GNU General Public License version 2 only, as | |
7 * published by the Free Software Foundation. | |
8 * | |
9 * This code is distributed in the hope that it will be useful, but WITHOUT | |
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |
12 * version 2 for more details (a copy is included in the LICENSE file that | |
13 * accompanied this code). | |
14 * | |
15 * You should have received a copy of the GNU General Public License version | |
16 * 2 along with this work; if not, write to the Free Software Foundation, | |
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. | |
18 * | |
19 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara, | |
20 * CA 95054 USA or visit www.sun.com if you need additional information or | |
21 * have any questions. | |
22 * | |
23 */ | |
24 | |
25 class ciMethod; | |
26 | |
27 class MethodLivenessResult : public BitMap { | |
28 private: | |
29 bool _is_valid; | |
30 | |
31 public: | |
32 MethodLivenessResult(uintptr_t* map, idx_t size_in_bits) | |
33 : BitMap(map, size_in_bits) | |
34 , _is_valid(false) | |
35 {} | |
36 | |
37 MethodLivenessResult(idx_t size_in_bits) | |
38 : BitMap(size_in_bits) | |
39 , _is_valid(false) | |
40 {} | |
41 | |
42 void set_is_valid() { _is_valid = true; } | |
43 bool is_valid() { return _is_valid; } | |
44 }; | |
45 | |
46 class MethodLiveness : public ResourceObj { | |
47 public: | |
48 // The BasicBlock class is used to represent a basic block in the | |
49 // liveness analysis. | |
50 class BasicBlock : public ResourceObj { | |
51 private: | |
52 // This class is only used by the MethodLiveness class. | |
53 friend class MethodLiveness; | |
54 | |
55 // The analyzer which created this basic block. | |
56 MethodLiveness* _analyzer; | |
57 | |
58 // The range of this basic block is [start_bci,limit_bci) | |
59 int _start_bci; | |
60 int _limit_bci; | |
61 | |
62 // The liveness at the start of the block; | |
63 BitMap _entry; | |
64 | |
65 // The summarized liveness effects of our direct successors reached | |
66 // by normal control flow | |
67 BitMap _normal_exit; | |
68 | |
69 // The summarized liveness effects of our direct successors reached | |
70 // by exceptional control flow | |
71 BitMap _exception_exit; | |
72 | |
73 // These members hold the results of the last call to | |
74 // compute_gen_kill_range(). _gen is the set of locals | |
75 // used before they are defined in the range. _kill is the | |
76 // set of locals defined before they are used. | |
77 BitMap _gen; | |
78 BitMap _kill; | |
79 int _last_bci; | |
80 | |
81 // A list of all blocks which could come directly before this one | |
82 // in normal (non-exceptional) control flow. We propagate liveness | |
83 // information to these blocks. | |
84 GrowableArray<BasicBlock*>* _normal_predecessors; | |
85 | |
86 // A list of all blocks which could come directly before this one | |
87 // in exceptional control flow. | |
88 GrowableArray<BasicBlock*>* _exception_predecessors; | |
89 | |
90 // The following fields are used to manage a work list used in the | |
91 // dataflow. | |
92 BasicBlock *_next; | |
93 bool _on_work_list; | |
94 | |
95 // Our successors call this method to merge liveness information into | |
96 // our _normal_exit member. | |
97 bool merge_normal(BitMap other); | |
98 | |
99 // Our successors call this method to merge liveness information into | |
100 // our _exception_exit member. | |
101 bool merge_exception(BitMap other); | |
102 | |
103 // This helper routine is used to help compute the gen/kill pair for | |
104 // the block. It is also used to answer queries. | |
105 void compute_gen_kill_range(ciBytecodeStream *bytes); | |
106 | |
107 // Compute the gen/kill effect of a single instruction. | |
108 void compute_gen_kill_single(ciBytecodeStream *instruction); | |
109 | |
110 // Helpers for compute_gen_kill_single. | |
111 void load_one(int local); | |
112 void load_two(int local); | |
113 void store_one(int local); | |
114 void store_two(int local); | |
115 | |
116 BasicBlock(MethodLiveness *analyzer, int start, int limit); | |
117 | |
118 // -- Accessors | |
119 | |
120 int start_bci() const { return _start_bci; } | |
121 | |
122 int limit_bci() const { return _limit_bci; } | |
123 void set_limit_bci(int limit) { _limit_bci = limit; } | |
124 | |
125 BasicBlock *next() const { return _next; } | |
126 void set_next(BasicBlock *next) { _next = next; } | |
127 | |
128 bool on_work_list() const { return _on_work_list; } | |
129 void set_on_work_list(bool val) { _on_work_list = val; } | |
130 | |
131 // -- Flow graph construction. | |
132 | |
133 // Add a basic block to our list of normal predecessors. | |
134 void add_normal_predecessor(BasicBlock *pred) { | |
135 _normal_predecessors->append_if_missing(pred); | |
136 } | |
137 | |
138 // Add a basic block to our list of exceptional predecessors | |
139 void add_exception_predecessor(BasicBlock *pred) { | |
140 _exception_predecessors->append_if_missing(pred); | |
141 } | |
142 | |
143 // Split the basic block at splitBci. This basic block | |
144 // becomes the second half. The first half is newly created. | |
145 BasicBlock *split(int splitBci); | |
146 | |
147 // -- Dataflow. | |
148 | |
149 void compute_gen_kill(ciMethod* method); | |
150 | |
151 // Propagate changes from this basic block | |
152 void propagate(MethodLiveness *ml); | |
153 | |
154 // -- Query. | |
155 | |
156 MethodLivenessResult get_liveness_at(ciMethod* method, int bci); | |
157 | |
158 // -- Debugging. | |
159 | |
160 void print_on(outputStream *os) const PRODUCT_RETURN; | |
161 | |
162 }; // End of MethodLiveness::BasicBlock | |
163 | |
164 private: | |
165 // The method we are analyzing. | |
166 ciMethod* _method; | |
167 ciMethod* method() const { return _method; } | |
168 | |
169 // The arena for storing structures... | |
170 Arena* _arena; | |
171 Arena* arena() const { return _arena; } | |
172 | |
173 // We cache the length of the method. | |
174 int _code_size; | |
175 | |
176 // The size of a BitMap. | |
177 int _bit_map_size_bits; | |
178 int _bit_map_size_words; | |
179 | |
180 // A list of all BasicBlocks. | |
181 BasicBlock **_block_list; | |
182 | |
183 // number of blocks | |
184 int _block_count; | |
185 | |
186 // Keeps track of bci->block mapping. One entry for each bci. Only block starts are | |
187 // recorded. | |
188 GrowableArray<BasicBlock*>* _block_map; | |
189 | |
190 // Our work list. | |
191 BasicBlock *_work_list; | |
192 | |
193 #ifdef COMPILER1 | |
194 // bcis where blocks start are marked | |
195 BitMap _bci_block_start; | |
196 #endif // COMPILER1 | |
197 | |
198 // -- Graph construction & Analysis | |
199 | |
200 // Compute ranges and predecessors for basic blocks. | |
201 void init_basic_blocks(); | |
202 | |
203 // Compute gen/kill information for all basic blocks. | |
204 void init_gen_kill(); | |
205 | |
206 // Perform the dataflow. | |
207 void propagate_liveness(); | |
208 | |
209 // The class MethodLiveness::BasicBlock needs special access to some | |
210 // of our members. | |
211 friend class MethodLiveness::BasicBlock; | |
212 | |
213 // And accessors. | |
214 int bit_map_size_bits() const { return _bit_map_size_bits; } | |
215 int bit_map_size_words() const { return _bit_map_size_words; } | |
216 | |
217 // Work list manipulation routines. Called internally by BasicBlock. | |
218 BasicBlock *work_list_get(); | |
219 void work_list_add(BasicBlock *block); | |
220 | |
221 // -- Timing and Statistics. | |
222 | |
223 | |
224 // Timers | |
225 static elapsedTimer _time_build_graph; | |
226 static elapsedTimer _time_gen_kill; | |
227 static elapsedTimer _time_flow; | |
228 static elapsedTimer _time_query; | |
229 static elapsedTimer _time_total; | |
230 | |
231 #ifndef PRODUCT | |
232 | |
233 // Counts | |
234 static long _total_bytes; | |
235 static int _total_methods; | |
236 | |
237 static long _total_blocks; | |
238 static int _max_method_blocks; | |
239 | |
240 static long _total_edges; | |
241 static int _max_block_edges; | |
242 | |
243 static long _total_exc_edges; | |
244 static int _max_block_exc_edges; | |
245 | |
246 static long _total_method_locals; | |
247 static int _max_method_locals; | |
248 | |
249 static long _total_locals_queried; | |
250 static long _total_live_locals_queried; | |
251 | |
252 static long _total_visits; | |
253 | |
254 #endif | |
255 | |
256 public: | |
257 // Create a liveness analyzer for a method | |
258 MethodLiveness(Arena* arena, ciMethod* method); | |
259 | |
260 // Compute liveness information for the method | |
261 void compute_liveness(); | |
262 | |
263 // Find out which locals are live at a specific bci. | |
264 MethodLivenessResult get_liveness_at(int bci); | |
265 | |
266 #ifdef COMPILER1 | |
267 const BitMap get_bci_block_start() const { return _bci_block_start; } | |
268 #endif // COMPILER1 | |
269 | |
270 static void print_times() PRODUCT_RETURN; | |
271 }; |