author | mdoerr |
Wed, 21 Oct 2015 10:37:50 +0200 | |
changeset 34160 | 3240e478a30e |
parent 24318 | 9d2b7bd56778 |
child 35097 | cd29ef2a189d |
permissions | -rw-r--r-- |
1 | 1 |
/* |
34160
3240e478a30e
8138894: C1: Support IRIW on weak memory platforms
mdoerr
parents:
24318
diff
changeset
|
2 |
* Copyright (c) 1999, 2015, Oracle and/or its affiliates. All rights reserved. |
1 | 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 |
* |
|
5547
f4b087cbb361
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
5046
diff
changeset
|
19 |
* Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA |
f4b087cbb361
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
5046
diff
changeset
|
20 |
* or visit www.oracle.com if you need additional information or have any |
f4b087cbb361
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
5046
diff
changeset
|
21 |
* questions. |
1 | 22 |
* |
23 |
*/ |
|
24 |
||
7397 | 25 |
#include "precompiled.hpp" |
26 |
#include "c1/c1_Compilation.hpp" |
|
27 |
#include "c1/c1_FrameMap.hpp" |
|
28 |
#include "c1/c1_GraphBuilder.hpp" |
|
29 |
#include "c1/c1_IR.hpp" |
|
30 |
#include "c1/c1_InstructionPrinter.hpp" |
|
31 |
#include "c1/c1_Optimizer.hpp" |
|
32 |
#include "utilities/bitMap.inline.hpp" |
|
1 | 33 |
|
34 |
||
35 |
// Implementation of XHandlers |
|
36 |
// |
|
37 |
// Note: This code could eventually go away if we are |
|
38 |
// just using the ciExceptionHandlerStream. |
|
39 |
||
40 |
XHandlers::XHandlers(ciMethod* method) : _list(method->exception_table_length()) { |
|
41 |
ciExceptionHandlerStream s(method); |
|
42 |
while (!s.is_done()) { |
|
43 |
_list.append(new XHandler(s.handler())); |
|
44 |
s.next(); |
|
45 |
} |
|
46 |
assert(s.count() == method->exception_table_length(), "exception table lengths inconsistent"); |
|
47 |
} |
|
48 |
||
49 |
// deep copy of all XHandler contained in list |
|
50 |
XHandlers::XHandlers(XHandlers* other) : |
|
51 |
_list(other->length()) |
|
52 |
{ |
|
53 |
for (int i = 0; i < other->length(); i++) { |
|
54 |
_list.append(new XHandler(other->handler_at(i))); |
|
55 |
} |
|
56 |
} |
|
57 |
||
58 |
// Returns whether a particular exception type can be caught. Also |
|
59 |
// returns true if klass is unloaded or any exception handler |
|
60 |
// classes are unloaded. type_is_exact indicates whether the throw |
|
61 |
// is known to be exactly that class or it might throw a subtype. |
|
62 |
bool XHandlers::could_catch(ciInstanceKlass* klass, bool type_is_exact) const { |
|
63 |
// the type is unknown so be conservative |
|
64 |
if (!klass->is_loaded()) { |
|
65 |
return true; |
|
66 |
} |
|
67 |
||
68 |
for (int i = 0; i < length(); i++) { |
|
69 |
XHandler* handler = handler_at(i); |
|
70 |
if (handler->is_catch_all()) { |
|
71 |
// catch of ANY |
|
72 |
return true; |
|
73 |
} |
|
74 |
ciInstanceKlass* handler_klass = handler->catch_klass(); |
|
75 |
// if it's unknown it might be catchable |
|
76 |
if (!handler_klass->is_loaded()) { |
|
77 |
return true; |
|
78 |
} |
|
79 |
// if the throw type is definitely a subtype of the catch type |
|
80 |
// then it can be caught. |
|
81 |
if (klass->is_subtype_of(handler_klass)) { |
|
82 |
return true; |
|
83 |
} |
|
84 |
if (!type_is_exact) { |
|
85 |
// If the type isn't exactly known then it can also be caught by |
|
86 |
// catch statements where the inexact type is a subtype of the |
|
87 |
// catch type. |
|
88 |
// given: foo extends bar extends Exception |
|
89 |
// throw bar can be caught by catch foo, catch bar, and catch |
|
90 |
// Exception, however it can't be caught by any handlers without |
|
91 |
// bar in its type hierarchy. |
|
92 |
if (handler_klass->is_subtype_of(klass)) { |
|
93 |
return true; |
|
94 |
} |
|
95 |
} |
|
96 |
} |
|
97 |
||
98 |
return false; |
|
99 |
} |
|
100 |
||
101 |
||
102 |
bool XHandlers::equals(XHandlers* others) const { |
|
103 |
if (others == NULL) return false; |
|
104 |
if (length() != others->length()) return false; |
|
105 |
||
106 |
for (int i = 0; i < length(); i++) { |
|
107 |
if (!handler_at(i)->equals(others->handler_at(i))) return false; |
|
108 |
} |
|
109 |
return true; |
|
110 |
} |
|
111 |
||
112 |
bool XHandler::equals(XHandler* other) const { |
|
113 |
assert(entry_pco() != -1 && other->entry_pco() != -1, "must have entry_pco"); |
|
114 |
||
115 |
if (entry_pco() != other->entry_pco()) return false; |
|
116 |
if (scope_count() != other->scope_count()) return false; |
|
117 |
if (_desc != other->_desc) return false; |
|
118 |
||
119 |
assert(entry_block() == other->entry_block(), "entry_block must be equal when entry_pco is equal"); |
|
120 |
return true; |
|
121 |
} |
|
122 |
||
123 |
||
124 |
// Implementation of IRScope |
|
125 |
BlockBegin* IRScope::build_graph(Compilation* compilation, int osr_bci) { |
|
126 |
GraphBuilder gm(compilation, this); |
|
127 |
NOT_PRODUCT(if (PrintValueNumbering && Verbose) gm.print_stats()); |
|
128 |
if (compilation->bailed_out()) return NULL; |
|
129 |
return gm.start(); |
|
130 |
} |
|
131 |
||
132 |
||
133 |
IRScope::IRScope(Compilation* compilation, IRScope* caller, int caller_bci, ciMethod* method, int osr_bci, bool create_graph) |
|
134 |
: _callees(2) |
|
135 |
, _compilation(compilation) |
|
136 |
, _requires_phi_function(method->max_locals()) |
|
137 |
{ |
|
138 |
_caller = caller; |
|
139 |
_level = caller == NULL ? 0 : caller->level() + 1; |
|
140 |
_method = method; |
|
141 |
_xhandlers = new XHandlers(method); |
|
142 |
_number_of_locks = 0; |
|
143 |
_monitor_pairing_ok = method->has_balanced_monitors(); |
|
11886
feebf5c9f40c
7120481: storeStore barrier in constructor with final field
jiangli
parents:
7432
diff
changeset
|
144 |
_wrote_final = false; |
23190
e8bbf9cd711e
8031818: Experimental VM flag for enforcing safe object construction
shade
parents:
22234
diff
changeset
|
145 |
_wrote_fields = false; |
34160
3240e478a30e
8138894: C1: Support IRIW on weak memory platforms
mdoerr
parents:
24318
diff
changeset
|
146 |
_wrote_volatile = false; |
1 | 147 |
_start = NULL; |
148 |
||
149 |
if (osr_bci == -1) { |
|
150 |
_requires_phi_function.clear(); |
|
151 |
} else { |
|
152 |
// selective creation of phi functions is not possibel in osr-methods |
|
153 |
_requires_phi_function.set_range(0, method->max_locals()); |
|
154 |
} |
|
155 |
||
156 |
assert(method->holder()->is_loaded() , "method holder must be loaded"); |
|
157 |
||
158 |
// build graph if monitor pairing is ok |
|
159 |
if (create_graph && monitor_pairing_ok()) _start = build_graph(compilation, osr_bci); |
|
160 |
} |
|
161 |
||
162 |
||
163 |
int IRScope::max_stack() const { |
|
164 |
int my_max = method()->max_stack(); |
|
165 |
int callee_max = 0; |
|
166 |
for (int i = 0; i < number_of_callees(); i++) { |
|
167 |
callee_max = MAX2(callee_max, callee_no(i)->max_stack()); |
|
168 |
} |
|
169 |
return my_max + callee_max; |
|
170 |
} |
|
171 |
||
172 |
||
3600
27aa4477d039
6833129: specjvm98 fails with NullPointerException in the compiler with -XX:DeoptimizeALot
cfang
parents:
1623
diff
changeset
|
173 |
bool IRScopeDebugInfo::should_reexecute() { |
27aa4477d039
6833129: specjvm98 fails with NullPointerException in the compiler with -XX:DeoptimizeALot
cfang
parents:
1623
diff
changeset
|
174 |
ciMethod* cur_method = scope()->method(); |
27aa4477d039
6833129: specjvm98 fails with NullPointerException in the compiler with -XX:DeoptimizeALot
cfang
parents:
1623
diff
changeset
|
175 |
int cur_bci = bci(); |
27aa4477d039
6833129: specjvm98 fails with NullPointerException in the compiler with -XX:DeoptimizeALot
cfang
parents:
1623
diff
changeset
|
176 |
if (cur_method != NULL && cur_bci != SynchronizationEntryBCI) { |
27aa4477d039
6833129: specjvm98 fails with NullPointerException in the compiler with -XX:DeoptimizeALot
cfang
parents:
1623
diff
changeset
|
177 |
Bytecodes::Code code = cur_method->java_code_at_bci(cur_bci); |
27aa4477d039
6833129: specjvm98 fails with NullPointerException in the compiler with -XX:DeoptimizeALot
cfang
parents:
1623
diff
changeset
|
178 |
return Interpreter::bytecode_should_reexecute(code); |
27aa4477d039
6833129: specjvm98 fails with NullPointerException in the compiler with -XX:DeoptimizeALot
cfang
parents:
1623
diff
changeset
|
179 |
} else |
27aa4477d039
6833129: specjvm98 fails with NullPointerException in the compiler with -XX:DeoptimizeALot
cfang
parents:
1623
diff
changeset
|
180 |
return false; |
27aa4477d039
6833129: specjvm98 fails with NullPointerException in the compiler with -XX:DeoptimizeALot
cfang
parents:
1623
diff
changeset
|
181 |
} |
1 | 182 |
|
183 |
||
184 |
// Implementation of CodeEmitInfo |
|
185 |
||
186 |
// Stack must be NON-null |
|
16611 | 187 |
CodeEmitInfo::CodeEmitInfo(ValueStack* stack, XHandlers* exception_handlers, bool deoptimize_on_exception) |
1 | 188 |
: _scope(stack->scope()) |
189 |
, _scope_debug_info(NULL) |
|
190 |
, _oop_map(NULL) |
|
191 |
, _stack(stack) |
|
192 |
, _exception_handlers(exception_handlers) |
|
16611 | 193 |
, _is_method_handle_invoke(false) |
194 |
, _deoptimize_on_exception(deoptimize_on_exception) { |
|
1 | 195 |
assert(_stack != NULL, "must be non null"); |
196 |
} |
|
197 |
||
198 |
||
6745 | 199 |
CodeEmitInfo::CodeEmitInfo(CodeEmitInfo* info, ValueStack* stack) |
1 | 200 |
: _scope(info->_scope) |
201 |
, _exception_handlers(NULL) |
|
202 |
, _scope_debug_info(NULL) |
|
5687 | 203 |
, _oop_map(NULL) |
6745 | 204 |
, _stack(stack == NULL ? info->_stack : stack) |
16611 | 205 |
, _is_method_handle_invoke(info->_is_method_handle_invoke) |
206 |
, _deoptimize_on_exception(info->_deoptimize_on_exception) { |
|
1 | 207 |
|
208 |
// deep copy of exception handlers |
|
209 |
if (info->_exception_handlers != NULL) { |
|
210 |
_exception_handlers = new XHandlers(info->_exception_handlers); |
|
211 |
} |
|
212 |
} |
|
213 |
||
214 |
||
5687 | 215 |
void CodeEmitInfo::record_debug_info(DebugInformationRecorder* recorder, int pc_offset) { |
1 | 216 |
// record the safepoint before recording the debug info for enclosing scopes |
217 |
recorder->add_safepoint(pc_offset, _oop_map->deep_copy()); |
|
5687 | 218 |
_scope_debug_info->record_debug_info(recorder, pc_offset, true/*topmost*/, _is_method_handle_invoke); |
1 | 219 |
recorder->end_safepoint(pc_offset); |
220 |
} |
|
221 |
||
222 |
||
223 |
void CodeEmitInfo::add_register_oop(LIR_Opr opr) { |
|
224 |
assert(_oop_map != NULL, "oop map must already exist"); |
|
225 |
assert(opr->is_single_cpu(), "should not call otherwise"); |
|
226 |
||
227 |
VMReg name = frame_map()->regname(opr); |
|
228 |
_oop_map->set_oop(name); |
|
229 |
} |
|
230 |
||
24018
77b156916bab
8032410: compiler/uncommontrap/TestStackBangRbp.java times out on Solaris-Sparc V9
roland
parents:
23190
diff
changeset
|
231 |
// Mirror the stack size calculation in the deopt code |
77b156916bab
8032410: compiler/uncommontrap/TestStackBangRbp.java times out on Solaris-Sparc V9
roland
parents:
23190
diff
changeset
|
232 |
// How much stack space would we need at this point in the program in |
77b156916bab
8032410: compiler/uncommontrap/TestStackBangRbp.java times out on Solaris-Sparc V9
roland
parents:
23190
diff
changeset
|
233 |
// case of deoptimization? |
77b156916bab
8032410: compiler/uncommontrap/TestStackBangRbp.java times out on Solaris-Sparc V9
roland
parents:
23190
diff
changeset
|
234 |
int CodeEmitInfo::interpreter_frame_size() const { |
77b156916bab
8032410: compiler/uncommontrap/TestStackBangRbp.java times out on Solaris-Sparc V9
roland
parents:
23190
diff
changeset
|
235 |
ValueStack* state = _stack; |
77b156916bab
8032410: compiler/uncommontrap/TestStackBangRbp.java times out on Solaris-Sparc V9
roland
parents:
23190
diff
changeset
|
236 |
int size = 0; |
77b156916bab
8032410: compiler/uncommontrap/TestStackBangRbp.java times out on Solaris-Sparc V9
roland
parents:
23190
diff
changeset
|
237 |
int callee_parameters = 0; |
77b156916bab
8032410: compiler/uncommontrap/TestStackBangRbp.java times out on Solaris-Sparc V9
roland
parents:
23190
diff
changeset
|
238 |
int callee_locals = 0; |
77b156916bab
8032410: compiler/uncommontrap/TestStackBangRbp.java times out on Solaris-Sparc V9
roland
parents:
23190
diff
changeset
|
239 |
int extra_args = state->scope()->method()->max_stack() - state->stack_size(); |
1 | 240 |
|
24018
77b156916bab
8032410: compiler/uncommontrap/TestStackBangRbp.java times out on Solaris-Sparc V9
roland
parents:
23190
diff
changeset
|
241 |
while (state != NULL) { |
77b156916bab
8032410: compiler/uncommontrap/TestStackBangRbp.java times out on Solaris-Sparc V9
roland
parents:
23190
diff
changeset
|
242 |
int locks = state->locks_size(); |
77b156916bab
8032410: compiler/uncommontrap/TestStackBangRbp.java times out on Solaris-Sparc V9
roland
parents:
23190
diff
changeset
|
243 |
int temps = state->stack_size(); |
77b156916bab
8032410: compiler/uncommontrap/TestStackBangRbp.java times out on Solaris-Sparc V9
roland
parents:
23190
diff
changeset
|
244 |
bool is_top_frame = (state == _stack); |
77b156916bab
8032410: compiler/uncommontrap/TestStackBangRbp.java times out on Solaris-Sparc V9
roland
parents:
23190
diff
changeset
|
245 |
ciMethod* method = state->scope()->method(); |
1 | 246 |
|
24018
77b156916bab
8032410: compiler/uncommontrap/TestStackBangRbp.java times out on Solaris-Sparc V9
roland
parents:
23190
diff
changeset
|
247 |
int frame_size = BytesPerWord * Interpreter::size_activation(method->max_stack(), |
77b156916bab
8032410: compiler/uncommontrap/TestStackBangRbp.java times out on Solaris-Sparc V9
roland
parents:
23190
diff
changeset
|
248 |
temps + callee_parameters, |
77b156916bab
8032410: compiler/uncommontrap/TestStackBangRbp.java times out on Solaris-Sparc V9
roland
parents:
23190
diff
changeset
|
249 |
extra_args, |
77b156916bab
8032410: compiler/uncommontrap/TestStackBangRbp.java times out on Solaris-Sparc V9
roland
parents:
23190
diff
changeset
|
250 |
locks, |
77b156916bab
8032410: compiler/uncommontrap/TestStackBangRbp.java times out on Solaris-Sparc V9
roland
parents:
23190
diff
changeset
|
251 |
callee_parameters, |
77b156916bab
8032410: compiler/uncommontrap/TestStackBangRbp.java times out on Solaris-Sparc V9
roland
parents:
23190
diff
changeset
|
252 |
callee_locals, |
77b156916bab
8032410: compiler/uncommontrap/TestStackBangRbp.java times out on Solaris-Sparc V9
roland
parents:
23190
diff
changeset
|
253 |
is_top_frame); |
77b156916bab
8032410: compiler/uncommontrap/TestStackBangRbp.java times out on Solaris-Sparc V9
roland
parents:
23190
diff
changeset
|
254 |
size += frame_size; |
77b156916bab
8032410: compiler/uncommontrap/TestStackBangRbp.java times out on Solaris-Sparc V9
roland
parents:
23190
diff
changeset
|
255 |
|
77b156916bab
8032410: compiler/uncommontrap/TestStackBangRbp.java times out on Solaris-Sparc V9
roland
parents:
23190
diff
changeset
|
256 |
callee_parameters = method->size_of_parameters(); |
77b156916bab
8032410: compiler/uncommontrap/TestStackBangRbp.java times out on Solaris-Sparc V9
roland
parents:
23190
diff
changeset
|
257 |
callee_locals = method->max_locals(); |
77b156916bab
8032410: compiler/uncommontrap/TestStackBangRbp.java times out on Solaris-Sparc V9
roland
parents:
23190
diff
changeset
|
258 |
extra_args = 0; |
77b156916bab
8032410: compiler/uncommontrap/TestStackBangRbp.java times out on Solaris-Sparc V9
roland
parents:
23190
diff
changeset
|
259 |
state = state->caller_state(); |
77b156916bab
8032410: compiler/uncommontrap/TestStackBangRbp.java times out on Solaris-Sparc V9
roland
parents:
23190
diff
changeset
|
260 |
} |
77b156916bab
8032410: compiler/uncommontrap/TestStackBangRbp.java times out on Solaris-Sparc V9
roland
parents:
23190
diff
changeset
|
261 |
return size + Deoptimization::last_frame_adjust(0, callee_locals) * BytesPerWord; |
77b156916bab
8032410: compiler/uncommontrap/TestStackBangRbp.java times out on Solaris-Sparc V9
roland
parents:
23190
diff
changeset
|
262 |
} |
1 | 263 |
|
264 |
// Implementation of IR |
|
265 |
||
266 |
IR::IR(Compilation* compilation, ciMethod* method, int osr_bci) : |
|
24318 | 267 |
_num_loops(0) { |
1 | 268 |
// setup IR fields |
269 |
_compilation = compilation; |
|
270 |
_top_scope = new IRScope(compilation, NULL, -1, method, osr_bci, true); |
|
271 |
_code = NULL; |
|
272 |
} |
|
273 |
||
274 |
||
16611 | 275 |
void IR::optimize_blocks() { |
1 | 276 |
Optimizer opt(this); |
6453 | 277 |
if (!compilation()->profile_branches()) { |
278 |
if (DoCEE) { |
|
279 |
opt.eliminate_conditional_expressions(); |
|
1 | 280 |
#ifndef PRODUCT |
6453 | 281 |
if (PrintCFG || PrintCFG1) { tty->print_cr("CFG after CEE"); print(true); } |
282 |
if (PrintIR || PrintIR1 ) { tty->print_cr("IR after CEE"); print(false); } |
|
1 | 283 |
#endif |
6453 | 284 |
} |
285 |
if (EliminateBlocks) { |
|
286 |
opt.eliminate_blocks(); |
|
1 | 287 |
#ifndef PRODUCT |
6453 | 288 |
if (PrintCFG || PrintCFG1) { tty->print_cr("CFG after block elimination"); print(true); } |
289 |
if (PrintIR || PrintIR1 ) { tty->print_cr("IR after block elimination"); print(false); } |
|
1 | 290 |
#endif |
6453 | 291 |
} |
1 | 292 |
} |
16611 | 293 |
} |
294 |
||
295 |
void IR::eliminate_null_checks() { |
|
296 |
Optimizer opt(this); |
|
1 | 297 |
if (EliminateNullChecks) { |
298 |
opt.eliminate_null_checks(); |
|
299 |
#ifndef PRODUCT |
|
300 |
if (PrintCFG || PrintCFG1) { tty->print_cr("CFG after null check elimination"); print(true); } |
|
301 |
if (PrintIR || PrintIR1 ) { tty->print_cr("IR after null check elimination"); print(false); } |
|
302 |
#endif |
|
303 |
} |
|
304 |
} |
|
305 |
||
306 |
||
307 |
static int sort_pairs(BlockPair** a, BlockPair** b) { |
|
308 |
if ((*a)->from() == (*b)->from()) { |
|
309 |
return (*a)->to()->block_id() - (*b)->to()->block_id(); |
|
310 |
} else { |
|
311 |
return (*a)->from()->block_id() - (*b)->from()->block_id(); |
|
312 |
} |
|
313 |
} |
|
314 |
||
315 |
||
316 |
class CriticalEdgeFinder: public BlockClosure { |
|
317 |
BlockPairList blocks; |
|
318 |
IR* _ir; |
|
319 |
||
320 |
public: |
|
321 |
CriticalEdgeFinder(IR* ir): _ir(ir) {} |
|
322 |
void block_do(BlockBegin* bb) { |
|
323 |
BlockEnd* be = bb->end(); |
|
324 |
int nos = be->number_of_sux(); |
|
325 |
if (nos >= 2) { |
|
326 |
for (int i = 0; i < nos; i++) { |
|
327 |
BlockBegin* sux = be->sux_at(i); |
|
328 |
if (sux->number_of_preds() >= 2) { |
|
329 |
blocks.append(new BlockPair(bb, sux)); |
|
330 |
} |
|
331 |
} |
|
332 |
} |
|
333 |
} |
|
334 |
||
335 |
void split_edges() { |
|
336 |
BlockPair* last_pair = NULL; |
|
337 |
blocks.sort(sort_pairs); |
|
338 |
for (int i = 0; i < blocks.length(); i++) { |
|
339 |
BlockPair* pair = blocks.at(i); |
|
340 |
if (last_pair != NULL && pair->is_same(last_pair)) continue; |
|
341 |
BlockBegin* from = pair->from(); |
|
342 |
BlockBegin* to = pair->to(); |
|
343 |
BlockBegin* split = from->insert_block_between(to); |
|
344 |
#ifndef PRODUCT |
|
345 |
if ((PrintIR || PrintIR1) && Verbose) { |
|
346 |
tty->print_cr("Split critical edge B%d -> B%d (new block B%d)", |
|
347 |
from->block_id(), to->block_id(), split->block_id()); |
|
348 |
} |
|
349 |
#endif |
|
350 |
last_pair = pair; |
|
351 |
} |
|
352 |
} |
|
353 |
}; |
|
354 |
||
355 |
void IR::split_critical_edges() { |
|
356 |
CriticalEdgeFinder cef(this); |
|
357 |
||
358 |
iterate_preorder(&cef); |
|
359 |
cef.split_edges(); |
|
360 |
} |
|
361 |
||
362 |
||
5707 | 363 |
class UseCountComputer: public ValueVisitor, BlockClosure { |
1 | 364 |
private: |
5707 | 365 |
void visit(Value* n) { |
1 | 366 |
// Local instructions and Phis for expression stack values at the |
367 |
// start of basic blocks are not added to the instruction list |
|
7100 | 368 |
if (!(*n)->is_linked() && (*n)->can_be_linked()) { |
1 | 369 |
assert(false, "a node was not appended to the graph"); |
5707 | 370 |
Compilation::current()->bailout("a node was not appended to the graph"); |
1 | 371 |
} |
372 |
// use n's input if not visited before |
|
373 |
if (!(*n)->is_pinned() && !(*n)->has_uses()) { |
|
374 |
// note: a) if the instruction is pinned, it will be handled by compute_use_count |
|
375 |
// b) if the instruction has uses, it was touched before |
|
376 |
// => in both cases we don't need to update n's values |
|
377 |
uses_do(n); |
|
378 |
} |
|
379 |
// use n |
|
380 |
(*n)->_use_count++; |
|
381 |
} |
|
382 |
||
5707 | 383 |
Values* worklist; |
384 |
int depth; |
|
1 | 385 |
enum { |
386 |
max_recurse_depth = 20 |
|
387 |
}; |
|
388 |
||
5707 | 389 |
void uses_do(Value* n) { |
1 | 390 |
depth++; |
391 |
if (depth > max_recurse_depth) { |
|
392 |
// don't allow the traversal to recurse too deeply |
|
393 |
worklist->push(*n); |
|
394 |
} else { |
|
5707 | 395 |
(*n)->input_values_do(this); |
1 | 396 |
// special handling for some instructions |
397 |
if ((*n)->as_BlockEnd() != NULL) { |
|
398 |
// note on BlockEnd: |
|
399 |
// must 'use' the stack only if the method doesn't |
|
400 |
// terminate, however, in those cases stack is empty |
|
5707 | 401 |
(*n)->state_values_do(this); |
1 | 402 |
} |
403 |
} |
|
404 |
depth--; |
|
405 |
} |
|
406 |
||
5707 | 407 |
void block_do(BlockBegin* b) { |
1 | 408 |
depth = 0; |
409 |
// process all pinned nodes as the roots of expression trees |
|
410 |
for (Instruction* n = b; n != NULL; n = n->next()) { |
|
411 |
if (n->is_pinned()) uses_do(&n); |
|
412 |
} |
|
413 |
assert(depth == 0, "should have counted back down"); |
|
414 |
||
415 |
// now process any unpinned nodes which recursed too deeply |
|
416 |
while (worklist->length() > 0) { |
|
417 |
Value t = worklist->pop(); |
|
418 |
if (!t->is_pinned()) { |
|
419 |
// compute the use count |
|
420 |
uses_do(&t); |
|
421 |
||
422 |
// pin the instruction so that LIRGenerator doesn't recurse |
|
423 |
// too deeply during it's evaluation. |
|
424 |
t->pin(); |
|
425 |
} |
|
426 |
} |
|
427 |
assert(depth == 0, "should have counted back down"); |
|
428 |
} |
|
429 |
||
5707 | 430 |
UseCountComputer() { |
431 |
worklist = new Values(); |
|
432 |
depth = 0; |
|
433 |
} |
|
434 |
||
1 | 435 |
public: |
436 |
static void compute(BlockList* blocks) { |
|
5707 | 437 |
UseCountComputer ucc; |
438 |
blocks->iterate_backward(&ucc); |
|
1 | 439 |
} |
440 |
}; |
|
441 |
||
442 |
||
443 |
// helper macro for short definition of trace-output inside code |
|
444 |
#ifndef PRODUCT |
|
445 |
#define TRACE_LINEAR_SCAN(level, code) \ |
|
446 |
if (TraceLinearScanLevel >= level) { \ |
|
447 |
code; \ |
|
448 |
} |
|
449 |
#else |
|
450 |
#define TRACE_LINEAR_SCAN(level, code) |
|
451 |
#endif |
|
452 |
||
453 |
class ComputeLinearScanOrder : public StackObj { |
|
454 |
private: |
|
455 |
int _max_block_id; // the highest block_id of a block |
|
456 |
int _num_blocks; // total number of blocks (smaller than _max_block_id) |
|
457 |
int _num_loops; // total number of loops |
|
458 |
bool _iterative_dominators;// method requires iterative computation of dominatiors |
|
459 |
||
460 |
BlockList* _linear_scan_order; // the resulting list of blocks in correct order |
|
461 |
||
462 |
BitMap _visited_blocks; // used for recursive processing of blocks |
|
463 |
BitMap _active_blocks; // used for recursive processing of blocks |
|
464 |
BitMap _dominator_blocks; // temproary BitMap used for computation of dominator |
|
465 |
intArray _forward_branches; // number of incoming forward branches for each block |
|
466 |
BlockList _loop_end_blocks; // list of all loop end blocks collected during count_edges |
|
467 |
BitMap2D _loop_map; // two-dimensional bit set: a bit is set if a block is contained in a loop |
|
468 |
BlockList _work_list; // temporary list (used in mark_loops and compute_order) |
|
16611 | 469 |
BlockList _loop_headers; |
1 | 470 |
|
6453 | 471 |
Compilation* _compilation; |
472 |
||
1 | 473 |
// accessors for _visited_blocks and _active_blocks |
474 |
void init_visited() { _active_blocks.clear(); _visited_blocks.clear(); } |
|
475 |
bool is_visited(BlockBegin* b) const { return _visited_blocks.at(b->block_id()); } |
|
476 |
bool is_active(BlockBegin* b) const { return _active_blocks.at(b->block_id()); } |
|
477 |
void set_visited(BlockBegin* b) { assert(!is_visited(b), "already set"); _visited_blocks.set_bit(b->block_id()); } |
|
478 |
void set_active(BlockBegin* b) { assert(!is_active(b), "already set"); _active_blocks.set_bit(b->block_id()); } |
|
479 |
void clear_active(BlockBegin* b) { assert(is_active(b), "not already"); _active_blocks.clear_bit(b->block_id()); } |
|
480 |
||
481 |
// accessors for _forward_branches |
|
482 |
void inc_forward_branches(BlockBegin* b) { _forward_branches.at_put(b->block_id(), _forward_branches.at(b->block_id()) + 1); } |
|
483 |
int dec_forward_branches(BlockBegin* b) { _forward_branches.at_put(b->block_id(), _forward_branches.at(b->block_id()) - 1); return _forward_branches.at(b->block_id()); } |
|
484 |
||
485 |
// accessors for _loop_map |
|
486 |
bool is_block_in_loop (int loop_idx, BlockBegin* b) const { return _loop_map.at(loop_idx, b->block_id()); } |
|
487 |
void set_block_in_loop (int loop_idx, BlockBegin* b) { _loop_map.set_bit(loop_idx, b->block_id()); } |
|
488 |
void clear_block_in_loop(int loop_idx, int block_id) { _loop_map.clear_bit(loop_idx, block_id); } |
|
489 |
||
490 |
// count edges between blocks |
|
491 |
void count_edges(BlockBegin* cur, BlockBegin* parent); |
|
492 |
||
493 |
// loop detection |
|
494 |
void mark_loops(); |
|
495 |
void clear_non_natural_loops(BlockBegin* start_block); |
|
496 |
void assign_loop_depth(BlockBegin* start_block); |
|
497 |
||
498 |
// computation of final block order |
|
499 |
BlockBegin* common_dominator(BlockBegin* a, BlockBegin* b); |
|
500 |
void compute_dominator(BlockBegin* cur, BlockBegin* parent); |
|
501 |
int compute_weight(BlockBegin* cur); |
|
502 |
bool ready_for_processing(BlockBegin* cur); |
|
503 |
void sort_into_work_list(BlockBegin* b); |
|
504 |
void append_block(BlockBegin* cur); |
|
505 |
void compute_order(BlockBegin* start_block); |
|
506 |
||
507 |
// fixup of dominators for non-natural loops |
|
508 |
bool compute_dominators_iter(); |
|
509 |
void compute_dominators(); |
|
510 |
||
511 |
// debug functions |
|
512 |
NOT_PRODUCT(void print_blocks();) |
|
513 |
DEBUG_ONLY(void verify();) |
|
514 |
||
6453 | 515 |
Compilation* compilation() const { return _compilation; } |
1 | 516 |
public: |
6453 | 517 |
ComputeLinearScanOrder(Compilation* c, BlockBegin* start_block); |
1 | 518 |
|
519 |
// accessors for final result |
|
520 |
BlockList* linear_scan_order() const { return _linear_scan_order; } |
|
521 |
int num_loops() const { return _num_loops; } |
|
522 |
}; |
|
523 |
||
524 |
||
6453 | 525 |
ComputeLinearScanOrder::ComputeLinearScanOrder(Compilation* c, BlockBegin* start_block) : |
1 | 526 |
_max_block_id(BlockBegin::number_of_blocks()), |
527 |
_num_blocks(0), |
|
528 |
_num_loops(0), |
|
529 |
_iterative_dominators(false), |
|
530 |
_visited_blocks(_max_block_id), |
|
531 |
_active_blocks(_max_block_id), |
|
532 |
_dominator_blocks(_max_block_id), |
|
533 |
_forward_branches(_max_block_id, 0), |
|
534 |
_loop_end_blocks(8), |
|
535 |
_work_list(8), |
|
536 |
_linear_scan_order(NULL), // initialized later with correct size |
|
6453 | 537 |
_loop_map(0, 0), // initialized later with correct size |
538 |
_compilation(c) |
|
1 | 539 |
{ |
18073
f02460441ddc
8014431: cleanup warnings indicated by the -Wunused-value compiler option on linux
ccheung
parents:
16611
diff
changeset
|
540 |
TRACE_LINEAR_SCAN(2, tty->print_cr("***** computing linear-scan block order")); |
1 | 541 |
|
542 |
init_visited(); |
|
543 |
count_edges(start_block, NULL); |
|
544 |
||
6453 | 545 |
if (compilation()->is_profiling()) { |
7432
f06f1253c317
7003554: (tiered) assert(is_null_object() || handle() != NULL) failed: cannot embed null pointer
iveresov
parents:
7397
diff
changeset
|
546 |
ciMethod *method = compilation()->method(); |
f06f1253c317
7003554: (tiered) assert(is_null_object() || handle() != NULL) failed: cannot embed null pointer
iveresov
parents:
7397
diff
changeset
|
547 |
if (!method->is_accessor()) { |
f06f1253c317
7003554: (tiered) assert(is_null_object() || handle() != NULL) failed: cannot embed null pointer
iveresov
parents:
7397
diff
changeset
|
548 |
ciMethodData* md = method->method_data_or_null(); |
f06f1253c317
7003554: (tiered) assert(is_null_object() || handle() != NULL) failed: cannot embed null pointer
iveresov
parents:
7397
diff
changeset
|
549 |
assert(md != NULL, "Sanity"); |
f06f1253c317
7003554: (tiered) assert(is_null_object() || handle() != NULL) failed: cannot embed null pointer
iveresov
parents:
7397
diff
changeset
|
550 |
md->set_compilation_stats(_num_loops, _num_blocks); |
f06f1253c317
7003554: (tiered) assert(is_null_object() || handle() != NULL) failed: cannot embed null pointer
iveresov
parents:
7397
diff
changeset
|
551 |
} |
6453 | 552 |
} |
553 |
||
1 | 554 |
if (_num_loops > 0) { |
555 |
mark_loops(); |
|
556 |
clear_non_natural_loops(start_block); |
|
557 |
assign_loop_depth(start_block); |
|
558 |
} |
|
559 |
||
560 |
compute_order(start_block); |
|
561 |
compute_dominators(); |
|
562 |
||
563 |
NOT_PRODUCT(print_blocks()); |
|
564 |
DEBUG_ONLY(verify()); |
|
565 |
} |
|
566 |
||
567 |
||
568 |
// Traverse the CFG: |
|
569 |
// * count total number of blocks |
|
570 |
// * count all incoming edges and backward incoming edges |
|
571 |
// * number loop header blocks |
|
572 |
// * create a list with all loop end blocks |
|
573 |
void ComputeLinearScanOrder::count_edges(BlockBegin* cur, BlockBegin* parent) { |
|
574 |
TRACE_LINEAR_SCAN(3, tty->print_cr("Enter count_edges for block B%d coming from B%d", cur->block_id(), parent != NULL ? parent->block_id() : -1)); |
|
575 |
assert(cur->dominator() == NULL, "dominator already initialized"); |
|
576 |
||
577 |
if (is_active(cur)) { |
|
578 |
TRACE_LINEAR_SCAN(3, tty->print_cr("backward branch")); |
|
579 |
assert(is_visited(cur), "block must be visisted when block is active"); |
|
580 |
assert(parent != NULL, "must have parent"); |
|
581 |
||
582 |
cur->set(BlockBegin::linear_scan_loop_header_flag); |
|
583 |
cur->set(BlockBegin::backward_branch_target_flag); |
|
584 |
||
585 |
parent->set(BlockBegin::linear_scan_loop_end_flag); |
|
1547
ebdd95407cd4
6758445: loop heads that are exception entry points can crash during count_edges/mark_loops
never
parents:
1
diff
changeset
|
586 |
|
ebdd95407cd4
6758445: loop heads that are exception entry points can crash during count_edges/mark_loops
never
parents:
1
diff
changeset
|
587 |
// When a loop header is also the start of an exception handler, then the backward branch is |
ebdd95407cd4
6758445: loop heads that are exception entry points can crash during count_edges/mark_loops
never
parents:
1
diff
changeset
|
588 |
// an exception edge. Because such edges are usually critical edges which cannot be split, the |
ebdd95407cd4
6758445: loop heads that are exception entry points can crash during count_edges/mark_loops
never
parents:
1
diff
changeset
|
589 |
// loop must be excluded here from processing. |
ebdd95407cd4
6758445: loop heads that are exception entry points can crash during count_edges/mark_loops
never
parents:
1
diff
changeset
|
590 |
if (cur->is_set(BlockBegin::exception_entry_flag)) { |
ebdd95407cd4
6758445: loop heads that are exception entry points can crash during count_edges/mark_loops
never
parents:
1
diff
changeset
|
591 |
// Make sure that dominators are correct in this weird situation |
ebdd95407cd4
6758445: loop heads that are exception entry points can crash during count_edges/mark_loops
never
parents:
1
diff
changeset
|
592 |
_iterative_dominators = true; |
ebdd95407cd4
6758445: loop heads that are exception entry points can crash during count_edges/mark_loops
never
parents:
1
diff
changeset
|
593 |
return; |
ebdd95407cd4
6758445: loop heads that are exception entry points can crash during count_edges/mark_loops
never
parents:
1
diff
changeset
|
594 |
} |
ebdd95407cd4
6758445: loop heads that are exception entry points can crash during count_edges/mark_loops
never
parents:
1
diff
changeset
|
595 |
assert(parent->number_of_sux() == 1 && parent->sux_at(0) == cur, |
ebdd95407cd4
6758445: loop heads that are exception entry points can crash during count_edges/mark_loops
never
parents:
1
diff
changeset
|
596 |
"loop end blocks must have one successor (critical edges are split)"); |
ebdd95407cd4
6758445: loop heads that are exception entry points can crash during count_edges/mark_loops
never
parents:
1
diff
changeset
|
597 |
|
1 | 598 |
_loop_end_blocks.append(parent); |
599 |
return; |
|
600 |
} |
|
601 |
||
602 |
// increment number of incoming forward branches |
|
603 |
inc_forward_branches(cur); |
|
604 |
||
605 |
if (is_visited(cur)) { |
|
606 |
TRACE_LINEAR_SCAN(3, tty->print_cr("block already visited")); |
|
607 |
return; |
|
608 |
} |
|
609 |
||
610 |
_num_blocks++; |
|
611 |
set_visited(cur); |
|
612 |
set_active(cur); |
|
613 |
||
614 |
// recursive call for all successors |
|
615 |
int i; |
|
616 |
for (i = cur->number_of_sux() - 1; i >= 0; i--) { |
|
617 |
count_edges(cur->sux_at(i), cur); |
|
618 |
} |
|
619 |
for (i = cur->number_of_exception_handlers() - 1; i >= 0; i--) { |
|
620 |
count_edges(cur->exception_handler_at(i), cur); |
|
621 |
} |
|
622 |
||
623 |
clear_active(cur); |
|
624 |
||
625 |
// Each loop has a unique number. |
|
626 |
// When multiple loops are nested, assign_loop_depth assumes that the |
|
627 |
// innermost loop has the lowest number. This is guaranteed by setting |
|
628 |
// the loop number after the recursive calls for the successors above |
|
629 |
// have returned. |
|
630 |
if (cur->is_set(BlockBegin::linear_scan_loop_header_flag)) { |
|
631 |
assert(cur->loop_index() == -1, "cannot set loop-index twice"); |
|
632 |
TRACE_LINEAR_SCAN(3, tty->print_cr("Block B%d is loop header of loop %d", cur->block_id(), _num_loops)); |
|
633 |
||
634 |
cur->set_loop_index(_num_loops); |
|
16611 | 635 |
_loop_headers.append(cur); |
1 | 636 |
_num_loops++; |
637 |
} |
|
638 |
||
639 |
TRACE_LINEAR_SCAN(3, tty->print_cr("Finished count_edges for block B%d", cur->block_id())); |
|
640 |
} |
|
641 |
||
642 |
||
643 |
void ComputeLinearScanOrder::mark_loops() { |
|
644 |
TRACE_LINEAR_SCAN(3, tty->print_cr("----- marking loops")); |
|
645 |
||
646 |
_loop_map = BitMap2D(_num_loops, _max_block_id); |
|
647 |
_loop_map.clear(); |
|
648 |
||
649 |
for (int i = _loop_end_blocks.length() - 1; i >= 0; i--) { |
|
650 |
BlockBegin* loop_end = _loop_end_blocks.at(i); |
|
651 |
BlockBegin* loop_start = loop_end->sux_at(0); |
|
652 |
int loop_idx = loop_start->loop_index(); |
|
653 |
||
654 |
TRACE_LINEAR_SCAN(3, tty->print_cr("Processing loop from B%d to B%d (loop %d):", loop_start->block_id(), loop_end->block_id(), loop_idx)); |
|
655 |
assert(loop_end->is_set(BlockBegin::linear_scan_loop_end_flag), "loop end flag must be set"); |
|
656 |
assert(loop_end->number_of_sux() == 1, "incorrect number of successors"); |
|
657 |
assert(loop_start->is_set(BlockBegin::linear_scan_loop_header_flag), "loop header flag must be set"); |
|
658 |
assert(loop_idx >= 0 && loop_idx < _num_loops, "loop index not set"); |
|
659 |
assert(_work_list.is_empty(), "work list must be empty before processing"); |
|
660 |
||
661 |
// add the end-block of the loop to the working list |
|
662 |
_work_list.push(loop_end); |
|
663 |
set_block_in_loop(loop_idx, loop_end); |
|
664 |
do { |
|
665 |
BlockBegin* cur = _work_list.pop(); |
|
666 |
||
667 |
TRACE_LINEAR_SCAN(3, tty->print_cr(" processing B%d", cur->block_id())); |
|
668 |
assert(is_block_in_loop(loop_idx, cur), "bit in loop map must be set when block is in work list"); |
|
669 |
||
670 |
// recursive processing of all predecessors ends when start block of loop is reached |
|
671 |
if (cur != loop_start && !cur->is_set(BlockBegin::osr_entry_flag)) { |
|
672 |
for (int j = cur->number_of_preds() - 1; j >= 0; j--) { |
|
673 |
BlockBegin* pred = cur->pred_at(j); |
|
674 |
||
675 |
if (!is_block_in_loop(loop_idx, pred) /*&& !pred->is_set(BlockBeginosr_entry_flag)*/) { |
|
676 |
// this predecessor has not been processed yet, so add it to work list |
|
677 |
TRACE_LINEAR_SCAN(3, tty->print_cr(" pushing B%d", pred->block_id())); |
|
678 |
_work_list.push(pred); |
|
679 |
set_block_in_loop(loop_idx, pred); |
|
680 |
} |
|
681 |
} |
|
682 |
} |
|
683 |
} while (!_work_list.is_empty()); |
|
684 |
} |
|
685 |
} |
|
686 |
||
687 |
||
688 |
// check for non-natural loops (loops where the loop header does not dominate |
|
689 |
// all other loop blocks = loops with mulitple entries). |
|
690 |
// such loops are ignored |
|
691 |
void ComputeLinearScanOrder::clear_non_natural_loops(BlockBegin* start_block) { |
|
692 |
for (int i = _num_loops - 1; i >= 0; i--) { |
|
693 |
if (is_block_in_loop(i, start_block)) { |
|
694 |
// loop i contains the entry block of the method |
|
695 |
// -> this is not a natural loop, so ignore it |
|
696 |
TRACE_LINEAR_SCAN(2, tty->print_cr("Loop %d is non-natural, so it is ignored", i)); |
|
697 |
||
16611 | 698 |
BlockBegin *loop_header = _loop_headers.at(i); |
699 |
assert(loop_header->is_set(BlockBegin::linear_scan_loop_header_flag), "Must be loop header"); |
|
700 |
||
701 |
for (int j = 0; j < loop_header->number_of_preds(); j++) { |
|
702 |
BlockBegin *pred = loop_header->pred_at(j); |
|
703 |
pred->clear(BlockBegin::linear_scan_loop_end_flag); |
|
704 |
} |
|
705 |
||
706 |
loop_header->clear(BlockBegin::linear_scan_loop_header_flag); |
|
707 |
||
1 | 708 |
for (int block_id = _max_block_id - 1; block_id >= 0; block_id--) { |
709 |
clear_block_in_loop(i, block_id); |
|
710 |
} |
|
711 |
_iterative_dominators = true; |
|
712 |
} |
|
713 |
} |
|
714 |
} |
|
715 |
||
716 |
void ComputeLinearScanOrder::assign_loop_depth(BlockBegin* start_block) { |
|
18073
f02460441ddc
8014431: cleanup warnings indicated by the -Wunused-value compiler option on linux
ccheung
parents:
16611
diff
changeset
|
717 |
TRACE_LINEAR_SCAN(3, tty->print_cr("----- computing loop-depth and weight")); |
1 | 718 |
init_visited(); |
719 |
||
720 |
assert(_work_list.is_empty(), "work list must be empty before processing"); |
|
721 |
_work_list.append(start_block); |
|
722 |
||
723 |
do { |
|
724 |
BlockBegin* cur = _work_list.pop(); |
|
725 |
||
726 |
if (!is_visited(cur)) { |
|
727 |
set_visited(cur); |
|
728 |
TRACE_LINEAR_SCAN(4, tty->print_cr("Computing loop depth for block B%d", cur->block_id())); |
|
729 |
||
730 |
// compute loop-depth and loop-index for the block |
|
731 |
assert(cur->loop_depth() == 0, "cannot set loop-depth twice"); |
|
732 |
int i; |
|
733 |
int loop_depth = 0; |
|
734 |
int min_loop_idx = -1; |
|
735 |
for (i = _num_loops - 1; i >= 0; i--) { |
|
736 |
if (is_block_in_loop(i, cur)) { |
|
737 |
loop_depth++; |
|
738 |
min_loop_idx = i; |
|
739 |
} |
|
740 |
} |
|
741 |
cur->set_loop_depth(loop_depth); |
|
742 |
cur->set_loop_index(min_loop_idx); |
|
743 |
||
744 |
// append all unvisited successors to work list |
|
745 |
for (i = cur->number_of_sux() - 1; i >= 0; i--) { |
|
746 |
_work_list.append(cur->sux_at(i)); |
|
747 |
} |
|
748 |
for (i = cur->number_of_exception_handlers() - 1; i >= 0; i--) { |
|
749 |
_work_list.append(cur->exception_handler_at(i)); |
|
750 |
} |
|
751 |
} |
|
752 |
} while (!_work_list.is_empty()); |
|
753 |
} |
|
754 |
||
755 |
||
756 |
BlockBegin* ComputeLinearScanOrder::common_dominator(BlockBegin* a, BlockBegin* b) { |
|
757 |
assert(a != NULL && b != NULL, "must have input blocks"); |
|
758 |
||
759 |
_dominator_blocks.clear(); |
|
760 |
while (a != NULL) { |
|
761 |
_dominator_blocks.set_bit(a->block_id()); |
|
762 |
assert(a->dominator() != NULL || a == _linear_scan_order->at(0), "dominator must be initialized"); |
|
763 |
a = a->dominator(); |
|
764 |
} |
|
765 |
while (b != NULL && !_dominator_blocks.at(b->block_id())) { |
|
766 |
assert(b->dominator() != NULL || b == _linear_scan_order->at(0), "dominator must be initialized"); |
|
767 |
b = b->dominator(); |
|
768 |
} |
|
769 |
||
770 |
assert(b != NULL, "could not find dominator"); |
|
771 |
return b; |
|
772 |
} |
|
773 |
||
774 |
void ComputeLinearScanOrder::compute_dominator(BlockBegin* cur, BlockBegin* parent) { |
|
775 |
if (cur->dominator() == NULL) { |
|
776 |
TRACE_LINEAR_SCAN(4, tty->print_cr("DOM: initializing dominator of B%d to B%d", cur->block_id(), parent->block_id())); |
|
777 |
cur->set_dominator(parent); |
|
778 |
||
779 |
} else if (!(cur->is_set(BlockBegin::linear_scan_loop_header_flag) && parent->is_set(BlockBegin::linear_scan_loop_end_flag))) { |
|
780 |
TRACE_LINEAR_SCAN(4, tty->print_cr("DOM: computing dominator of B%d: common dominator of B%d and B%d is B%d", cur->block_id(), parent->block_id(), cur->dominator()->block_id(), common_dominator(cur->dominator(), parent)->block_id())); |
|
16611 | 781 |
// Does not hold for exception blocks |
782 |
assert(cur->number_of_preds() > 1 || cur->is_set(BlockBegin::exception_entry_flag), ""); |
|
1 | 783 |
cur->set_dominator(common_dominator(cur->dominator(), parent)); |
784 |
} |
|
16611 | 785 |
|
786 |
// Additional edge to xhandler of all our successors |
|
787 |
// range check elimination needs that the state at the end of a |
|
788 |
// block be valid in every block it dominates so cur must dominate |
|
789 |
// the exception handlers of its successors. |
|
790 |
int num_cur_xhandler = cur->number_of_exception_handlers(); |
|
791 |
for (int j = 0; j < num_cur_xhandler; j++) { |
|
792 |
BlockBegin* xhandler = cur->exception_handler_at(j); |
|
793 |
compute_dominator(xhandler, parent); |
|
794 |
} |
|
1 | 795 |
} |
796 |
||
797 |
||
798 |
int ComputeLinearScanOrder::compute_weight(BlockBegin* cur) { |
|
799 |
BlockBegin* single_sux = NULL; |
|
800 |
if (cur->number_of_sux() == 1) { |
|
801 |
single_sux = cur->sux_at(0); |
|
802 |
} |
|
803 |
||
804 |
// limit loop-depth to 15 bit (only for security reason, it will never be so big) |
|
805 |
int weight = (cur->loop_depth() & 0x7FFF) << 16; |
|
806 |
||
807 |
// general macro for short definition of weight flags |
|
808 |
// the first instance of INC_WEIGHT_IF has the highest priority |
|
809 |
int cur_bit = 15; |
|
810 |
#define INC_WEIGHT_IF(condition) if ((condition)) { weight |= (1 << cur_bit); } cur_bit--; |
|
811 |
||
812 |
// this is necessery for the (very rare) case that two successing blocks have |
|
813 |
// the same loop depth, but a different loop index (can happen for endless loops |
|
814 |
// with exception handlers) |
|
815 |
INC_WEIGHT_IF(!cur->is_set(BlockBegin::linear_scan_loop_header_flag)); |
|
816 |
||
817 |
// loop end blocks (blocks that end with a backward branch) are added |
|
818 |
// after all other blocks of the loop. |
|
819 |
INC_WEIGHT_IF(!cur->is_set(BlockBegin::linear_scan_loop_end_flag)); |
|
820 |
||
821 |
// critical edge split blocks are prefered because than they have a bigger |
|
822 |
// proability to be completely empty |
|
823 |
INC_WEIGHT_IF(cur->is_set(BlockBegin::critical_edge_split_flag)); |
|
824 |
||
825 |
// exceptions should not be thrown in normal control flow, so these blocks |
|
826 |
// are added as late as possible |
|
827 |
INC_WEIGHT_IF(cur->end()->as_Throw() == NULL && (single_sux == NULL || single_sux->end()->as_Throw() == NULL)); |
|
828 |
INC_WEIGHT_IF(cur->end()->as_Return() == NULL && (single_sux == NULL || single_sux->end()->as_Return() == NULL)); |
|
829 |
||
830 |
// exceptions handlers are added as late as possible |
|
831 |
INC_WEIGHT_IF(!cur->is_set(BlockBegin::exception_entry_flag)); |
|
832 |
||
833 |
// guarantee that weight is > 0 |
|
834 |
weight |= 1; |
|
835 |
||
836 |
#undef INC_WEIGHT_IF |
|
837 |
assert(cur_bit >= 0, "too many flags"); |
|
838 |
assert(weight > 0, "weight cannot become negative"); |
|
839 |
||
840 |
return weight; |
|
841 |
} |
|
842 |
||
843 |
bool ComputeLinearScanOrder::ready_for_processing(BlockBegin* cur) { |
|
844 |
// Discount the edge just traveled. |
|
845 |
// When the number drops to zero, all forward branches were processed |
|
846 |
if (dec_forward_branches(cur) != 0) { |
|
847 |
return false; |
|
848 |
} |
|
849 |
||
850 |
assert(_linear_scan_order->index_of(cur) == -1, "block already processed (block can be ready only once)"); |
|
851 |
assert(_work_list.index_of(cur) == -1, "block already in work-list (block can be ready only once)"); |
|
852 |
return true; |
|
853 |
} |
|
854 |
||
855 |
void ComputeLinearScanOrder::sort_into_work_list(BlockBegin* cur) { |
|
856 |
assert(_work_list.index_of(cur) == -1, "block already in work list"); |
|
857 |
||
858 |
int cur_weight = compute_weight(cur); |
|
859 |
||
860 |
// the linear_scan_number is used to cache the weight of a block |
|
861 |
cur->set_linear_scan_number(cur_weight); |
|
862 |
||
863 |
#ifndef PRODUCT |
|
864 |
if (StressLinearScan) { |
|
865 |
_work_list.insert_before(0, cur); |
|
866 |
return; |
|
867 |
} |
|
868 |
#endif |
|
869 |
||
870 |
_work_list.append(NULL); // provide space for new element |
|
871 |
||
872 |
int insert_idx = _work_list.length() - 1; |
|
873 |
while (insert_idx > 0 && _work_list.at(insert_idx - 1)->linear_scan_number() > cur_weight) { |
|
874 |
_work_list.at_put(insert_idx, _work_list.at(insert_idx - 1)); |
|
875 |
insert_idx--; |
|
876 |
} |
|
877 |
_work_list.at_put(insert_idx, cur); |
|
878 |
||
879 |
TRACE_LINEAR_SCAN(3, tty->print_cr("Sorted B%d into worklist. new worklist:", cur->block_id())); |
|
880 |
TRACE_LINEAR_SCAN(3, for (int i = 0; i < _work_list.length(); i++) tty->print_cr("%8d B%2d weight:%6x", i, _work_list.at(i)->block_id(), _work_list.at(i)->linear_scan_number())); |
|
881 |
||
882 |
#ifdef ASSERT |
|
883 |
for (int i = 0; i < _work_list.length(); i++) { |
|
884 |
assert(_work_list.at(i)->linear_scan_number() > 0, "weight not set"); |
|
885 |
assert(i == 0 || _work_list.at(i - 1)->linear_scan_number() <= _work_list.at(i)->linear_scan_number(), "incorrect order in worklist"); |
|
886 |
} |
|
887 |
#endif |
|
888 |
} |
|
889 |
||
890 |
void ComputeLinearScanOrder::append_block(BlockBegin* cur) { |
|
891 |
TRACE_LINEAR_SCAN(3, tty->print_cr("appending block B%d (weight 0x%6x) to linear-scan order", cur->block_id(), cur->linear_scan_number())); |
|
892 |
assert(_linear_scan_order->index_of(cur) == -1, "cannot add the same block twice"); |
|
893 |
||
894 |
// currently, the linear scan order and code emit order are equal. |
|
895 |
// therefore the linear_scan_number and the weight of a block must also |
|
896 |
// be equal. |
|
897 |
cur->set_linear_scan_number(_linear_scan_order->length()); |
|
898 |
_linear_scan_order->append(cur); |
|
899 |
} |
|
900 |
||
901 |
void ComputeLinearScanOrder::compute_order(BlockBegin* start_block) { |
|
18073
f02460441ddc
8014431: cleanup warnings indicated by the -Wunused-value compiler option on linux
ccheung
parents:
16611
diff
changeset
|
902 |
TRACE_LINEAR_SCAN(3, tty->print_cr("----- computing final block order")); |
1 | 903 |
|
904 |
// the start block is always the first block in the linear scan order |
|
905 |
_linear_scan_order = new BlockList(_num_blocks); |
|
906 |
append_block(start_block); |
|
907 |
||
908 |
assert(start_block->end()->as_Base() != NULL, "start block must end with Base-instruction"); |
|
909 |
BlockBegin* std_entry = ((Base*)start_block->end())->std_entry(); |
|
910 |
BlockBegin* osr_entry = ((Base*)start_block->end())->osr_entry(); |
|
911 |
||
912 |
BlockBegin* sux_of_osr_entry = NULL; |
|
913 |
if (osr_entry != NULL) { |
|
914 |
// special handling for osr entry: |
|
915 |
// ignore the edge between the osr entry and its successor for processing |
|
916 |
// the osr entry block is added manually below |
|
917 |
assert(osr_entry->number_of_sux() == 1, "osr entry must have exactly one successor"); |
|
918 |
assert(osr_entry->sux_at(0)->number_of_preds() >= 2, "sucessor of osr entry must have two predecessors (otherwise it is not present in normal control flow"); |
|
919 |
||
920 |
sux_of_osr_entry = osr_entry->sux_at(0); |
|
921 |
dec_forward_branches(sux_of_osr_entry); |
|
922 |
||
923 |
compute_dominator(osr_entry, start_block); |
|
924 |
_iterative_dominators = true; |
|
925 |
} |
|
926 |
compute_dominator(std_entry, start_block); |
|
927 |
||
928 |
// start processing with standard entry block |
|
929 |
assert(_work_list.is_empty(), "list must be empty before processing"); |
|
930 |
||
931 |
if (ready_for_processing(std_entry)) { |
|
932 |
sort_into_work_list(std_entry); |
|
933 |
} else { |
|
934 |
assert(false, "the std_entry must be ready for processing (otherwise, the method has no start block)"); |
|
935 |
} |
|
936 |
||
937 |
do { |
|
938 |
BlockBegin* cur = _work_list.pop(); |
|
939 |
||
940 |
if (cur == sux_of_osr_entry) { |
|
941 |
// the osr entry block is ignored in normal processing, it is never added to the |
|
942 |
// work list. Instead, it is added as late as possible manually here. |
|
943 |
append_block(osr_entry); |
|
944 |
compute_dominator(cur, osr_entry); |
|
945 |
} |
|
946 |
append_block(cur); |
|
947 |
||
948 |
int i; |
|
949 |
int num_sux = cur->number_of_sux(); |
|
950 |
// changed loop order to get "intuitive" order of if- and else-blocks |
|
951 |
for (i = 0; i < num_sux; i++) { |
|
952 |
BlockBegin* sux = cur->sux_at(i); |
|
953 |
compute_dominator(sux, cur); |
|
954 |
if (ready_for_processing(sux)) { |
|
955 |
sort_into_work_list(sux); |
|
956 |
} |
|
957 |
} |
|
958 |
num_sux = cur->number_of_exception_handlers(); |
|
959 |
for (i = 0; i < num_sux; i++) { |
|
960 |
BlockBegin* sux = cur->exception_handler_at(i); |
|
961 |
if (ready_for_processing(sux)) { |
|
962 |
sort_into_work_list(sux); |
|
963 |
} |
|
964 |
} |
|
965 |
} while (_work_list.length() > 0); |
|
966 |
} |
|
967 |
||
968 |
||
969 |
bool ComputeLinearScanOrder::compute_dominators_iter() { |
|
970 |
bool changed = false; |
|
971 |
int num_blocks = _linear_scan_order->length(); |
|
972 |
||
973 |
assert(_linear_scan_order->at(0)->dominator() == NULL, "must not have dominator"); |
|
974 |
assert(_linear_scan_order->at(0)->number_of_preds() == 0, "must not have predecessors"); |
|
975 |
for (int i = 1; i < num_blocks; i++) { |
|
976 |
BlockBegin* block = _linear_scan_order->at(i); |
|
977 |
||
978 |
BlockBegin* dominator = block->pred_at(0); |
|
979 |
int num_preds = block->number_of_preds(); |
|
16611 | 980 |
|
981 |
TRACE_LINEAR_SCAN(4, tty->print_cr("DOM: Processing B%d", block->block_id())); |
|
982 |
||
983 |
for (int j = 0; j < num_preds; j++) { |
|
984 |
||
985 |
BlockBegin *pred = block->pred_at(j); |
|
986 |
TRACE_LINEAR_SCAN(4, tty->print_cr(" DOM: Subrocessing B%d", pred->block_id())); |
|
987 |
||
988 |
if (block->is_set(BlockBegin::exception_entry_flag)) { |
|
989 |
dominator = common_dominator(dominator, pred); |
|
990 |
int num_pred_preds = pred->number_of_preds(); |
|
991 |
for (int k = 0; k < num_pred_preds; k++) { |
|
992 |
dominator = common_dominator(dominator, pred->pred_at(k)); |
|
993 |
} |
|
994 |
} else { |
|
995 |
dominator = common_dominator(dominator, pred); |
|
996 |
} |
|
1 | 997 |
} |
998 |
||
999 |
if (dominator != block->dominator()) { |
|
1000 |
TRACE_LINEAR_SCAN(4, tty->print_cr("DOM: updating dominator of B%d from B%d to B%d", block->block_id(), block->dominator()->block_id(), dominator->block_id())); |
|
1001 |
||
1002 |
block->set_dominator(dominator); |
|
1003 |
changed = true; |
|
1004 |
} |
|
1005 |
} |
|
1006 |
return changed; |
|
1007 |
} |
|
1008 |
||
1009 |
void ComputeLinearScanOrder::compute_dominators() { |
|
1010 |
TRACE_LINEAR_SCAN(3, tty->print_cr("----- computing dominators (iterative computation reqired: %d)", _iterative_dominators)); |
|
1011 |
||
1012 |
// iterative computation of dominators is only required for methods with non-natural loops |
|
1013 |
// and OSR-methods. For all other methods, the dominators computed when generating the |
|
1014 |
// linear scan block order are correct. |
|
1015 |
if (_iterative_dominators) { |
|
1016 |
do { |
|
1017 |
TRACE_LINEAR_SCAN(1, tty->print_cr("DOM: next iteration of fix-point calculation")); |
|
1018 |
} while (compute_dominators_iter()); |
|
1019 |
} |
|
1020 |
||
1021 |
// check that dominators are correct |
|
1022 |
assert(!compute_dominators_iter(), "fix point not reached"); |
|
16611 | 1023 |
|
1024 |
// Add Blocks to dominates-Array |
|
1025 |
int num_blocks = _linear_scan_order->length(); |
|
1026 |
for (int i = 0; i < num_blocks; i++) { |
|
1027 |
BlockBegin* block = _linear_scan_order->at(i); |
|
1028 |
||
1029 |
BlockBegin *dom = block->dominator(); |
|
1030 |
if (dom) { |
|
1031 |
assert(dom->dominator_depth() != -1, "Dominator must have been visited before"); |
|
1032 |
dom->dominates()->append(block); |
|
1033 |
block->set_dominator_depth(dom->dominator_depth() + 1); |
|
1034 |
} else { |
|
1035 |
block->set_dominator_depth(0); |
|
1036 |
} |
|
1037 |
} |
|
1 | 1038 |
} |
1039 |
||
1040 |
||
1041 |
#ifndef PRODUCT |
|
1042 |
void ComputeLinearScanOrder::print_blocks() { |
|
1043 |
if (TraceLinearScanLevel >= 2) { |
|
1044 |
tty->print_cr("----- loop information:"); |
|
1045 |
for (int block_idx = 0; block_idx < _linear_scan_order->length(); block_idx++) { |
|
1046 |
BlockBegin* cur = _linear_scan_order->at(block_idx); |
|
1047 |
||
1048 |
tty->print("%4d: B%2d: ", cur->linear_scan_number(), cur->block_id()); |
|
1049 |
for (int loop_idx = 0; loop_idx < _num_loops; loop_idx++) { |
|
1050 |
tty->print ("%d ", is_block_in_loop(loop_idx, cur)); |
|
1051 |
} |
|
1052 |
tty->print_cr(" -> loop_index: %2d, loop_depth: %2d", cur->loop_index(), cur->loop_depth()); |
|
1053 |
} |
|
1054 |
} |
|
1055 |
||
1056 |
if (TraceLinearScanLevel >= 1) { |
|
1057 |
tty->print_cr("----- linear-scan block order:"); |
|
1058 |
for (int block_idx = 0; block_idx < _linear_scan_order->length(); block_idx++) { |
|
1059 |
BlockBegin* cur = _linear_scan_order->at(block_idx); |
|
1060 |
tty->print("%4d: B%2d loop: %2d depth: %2d", cur->linear_scan_number(), cur->block_id(), cur->loop_index(), cur->loop_depth()); |
|
1061 |
||
1062 |
tty->print(cur->is_set(BlockBegin::exception_entry_flag) ? " ex" : " "); |
|
1063 |
tty->print(cur->is_set(BlockBegin::critical_edge_split_flag) ? " ce" : " "); |
|
1064 |
tty->print(cur->is_set(BlockBegin::linear_scan_loop_header_flag) ? " lh" : " "); |
|
1065 |
tty->print(cur->is_set(BlockBegin::linear_scan_loop_end_flag) ? " le" : " "); |
|
1066 |
||
1067 |
if (cur->dominator() != NULL) { |
|
1068 |
tty->print(" dom: B%d ", cur->dominator()->block_id()); |
|
1069 |
} else { |
|
1070 |
tty->print(" dom: NULL "); |
|
1071 |
} |
|
1072 |
||
1073 |
if (cur->number_of_preds() > 0) { |
|
1074 |
tty->print(" preds: "); |
|
1075 |
for (int j = 0; j < cur->number_of_preds(); j++) { |
|
1076 |
BlockBegin* pred = cur->pred_at(j); |
|
1077 |
tty->print("B%d ", pred->block_id()); |
|
1078 |
} |
|
1079 |
} |
|
1080 |
if (cur->number_of_sux() > 0) { |
|
1081 |
tty->print(" sux: "); |
|
1082 |
for (int j = 0; j < cur->number_of_sux(); j++) { |
|
1083 |
BlockBegin* sux = cur->sux_at(j); |
|
1084 |
tty->print("B%d ", sux->block_id()); |
|
1085 |
} |
|
1086 |
} |
|
1087 |
if (cur->number_of_exception_handlers() > 0) { |
|
1088 |
tty->print(" ex: "); |
|
1089 |
for (int j = 0; j < cur->number_of_exception_handlers(); j++) { |
|
1090 |
BlockBegin* ex = cur->exception_handler_at(j); |
|
1091 |
tty->print("B%d ", ex->block_id()); |
|
1092 |
} |
|
1093 |
} |
|
1094 |
tty->cr(); |
|
1095 |
} |
|
1096 |
} |
|
1097 |
} |
|
1098 |
#endif |
|
1099 |
||
1100 |
#ifdef ASSERT |
|
1101 |
void ComputeLinearScanOrder::verify() { |
|
1102 |
assert(_linear_scan_order->length() == _num_blocks, "wrong number of blocks in list"); |
|
1103 |
||
1104 |
if (StressLinearScan) { |
|
1105 |
// blocks are scrambled when StressLinearScan is used |
|
1106 |
return; |
|
1107 |
} |
|
1108 |
||
1109 |
// check that all successors of a block have a higher linear-scan-number |
|
1110 |
// and that all predecessors of a block have a lower linear-scan-number |
|
1111 |
// (only backward branches of loops are ignored) |
|
1112 |
int i; |
|
1113 |
for (i = 0; i < _linear_scan_order->length(); i++) { |
|
1114 |
BlockBegin* cur = _linear_scan_order->at(i); |
|
1115 |
||
1116 |
assert(cur->linear_scan_number() == i, "incorrect linear_scan_number"); |
|
1117 |
assert(cur->linear_scan_number() >= 0 && cur->linear_scan_number() == _linear_scan_order->index_of(cur), "incorrect linear_scan_number"); |
|
1118 |
||
1119 |
int j; |
|
1120 |
for (j = cur->number_of_sux() - 1; j >= 0; j--) { |
|
1121 |
BlockBegin* sux = cur->sux_at(j); |
|
1122 |
||
1123 |
assert(sux->linear_scan_number() >= 0 && sux->linear_scan_number() == _linear_scan_order->index_of(sux), "incorrect linear_scan_number"); |
|
16611 | 1124 |
if (!sux->is_set(BlockBegin::backward_branch_target_flag)) { |
1 | 1125 |
assert(cur->linear_scan_number() < sux->linear_scan_number(), "invalid order"); |
1126 |
} |
|
1127 |
if (cur->loop_depth() == sux->loop_depth()) { |
|
1128 |
assert(cur->loop_index() == sux->loop_index() || sux->is_set(BlockBegin::linear_scan_loop_header_flag), "successing blocks with same loop depth must have same loop index"); |
|
1129 |
} |
|
1130 |
} |
|
1131 |
||
1132 |
for (j = cur->number_of_preds() - 1; j >= 0; j--) { |
|
1133 |
BlockBegin* pred = cur->pred_at(j); |
|
1134 |
||
1135 |
assert(pred->linear_scan_number() >= 0 && pred->linear_scan_number() == _linear_scan_order->index_of(pred), "incorrect linear_scan_number"); |
|
16611 | 1136 |
if (!cur->is_set(BlockBegin::backward_branch_target_flag)) { |
1 | 1137 |
assert(cur->linear_scan_number() > pred->linear_scan_number(), "invalid order"); |
1138 |
} |
|
1139 |
if (cur->loop_depth() == pred->loop_depth()) { |
|
1140 |
assert(cur->loop_index() == pred->loop_index() || cur->is_set(BlockBegin::linear_scan_loop_header_flag), "successing blocks with same loop depth must have same loop index"); |
|
1141 |
} |
|
1142 |
||
1143 |
assert(cur->dominator()->linear_scan_number() <= cur->pred_at(j)->linear_scan_number(), "dominator must be before predecessors"); |
|
1144 |
} |
|
1145 |
||
1146 |
// check dominator |
|
1147 |
if (i == 0) { |
|
1148 |
assert(cur->dominator() == NULL, "first block has no dominator"); |
|
1149 |
} else { |
|
1150 |
assert(cur->dominator() != NULL, "all but first block must have dominator"); |
|
1151 |
} |
|
16611 | 1152 |
// Assertion does not hold for exception handlers |
1153 |
assert(cur->number_of_preds() != 1 || cur->dominator() == cur->pred_at(0) || cur->is_set(BlockBegin::exception_entry_flag), "Single predecessor must also be dominator"); |
|
1 | 1154 |
} |
1155 |
||
1156 |
// check that all loops are continuous |
|
1157 |
for (int loop_idx = 0; loop_idx < _num_loops; loop_idx++) { |
|
1158 |
int block_idx = 0; |
|
1159 |
assert(!is_block_in_loop(loop_idx, _linear_scan_order->at(block_idx)), "the first block must not be present in any loop"); |
|
1160 |
||
1161 |
// skip blocks before the loop |
|
1162 |
while (block_idx < _num_blocks && !is_block_in_loop(loop_idx, _linear_scan_order->at(block_idx))) { |
|
1163 |
block_idx++; |
|
1164 |
} |
|
1165 |
// skip blocks of loop |
|
1166 |
while (block_idx < _num_blocks && is_block_in_loop(loop_idx, _linear_scan_order->at(block_idx))) { |
|
1167 |
block_idx++; |
|
1168 |
} |
|
1169 |
// after the first non-loop block, there must not be another loop-block |
|
1170 |
while (block_idx < _num_blocks) { |
|
1171 |
assert(!is_block_in_loop(loop_idx, _linear_scan_order->at(block_idx)), "loop not continuous in linear-scan order"); |
|
1172 |
block_idx++; |
|
1173 |
} |
|
1174 |
} |
|
1175 |
} |
|
1176 |
#endif |
|
1177 |
||
1178 |
||
1179 |
void IR::compute_code() { |
|
1180 |
assert(is_valid(), "IR must be valid"); |
|
1181 |
||
6453 | 1182 |
ComputeLinearScanOrder compute_order(compilation(), start()); |
1 | 1183 |
_num_loops = compute_order.num_loops(); |
1184 |
_code = compute_order.linear_scan_order(); |
|
1185 |
} |
|
1186 |
||
1187 |
||
1188 |
void IR::compute_use_counts() { |
|
1189 |
// make sure all values coming out of this block get evaluated. |
|
1190 |
int num_blocks = _code->length(); |
|
1191 |
for (int i = 0; i < num_blocks; i++) { |
|
1192 |
_code->at(i)->end()->state()->pin_stack_for_linear_scan(); |
|
1193 |
} |
|
1194 |
||
1195 |
// compute use counts |
|
1196 |
UseCountComputer::compute(_code); |
|
1197 |
} |
|
1198 |
||
1199 |
||
1200 |
void IR::iterate_preorder(BlockClosure* closure) { |
|
1201 |
assert(is_valid(), "IR must be valid"); |
|
1202 |
start()->iterate_preorder(closure); |
|
1203 |
} |
|
1204 |
||
1205 |
||
1206 |
void IR::iterate_postorder(BlockClosure* closure) { |
|
1207 |
assert(is_valid(), "IR must be valid"); |
|
1208 |
start()->iterate_postorder(closure); |
|
1209 |
} |
|
1210 |
||
1211 |
void IR::iterate_linear_scan_order(BlockClosure* closure) { |
|
1212 |
linear_scan_order()->iterate_forward(closure); |
|
1213 |
} |
|
1214 |
||
1215 |
||
1216 |
#ifndef PRODUCT |
|
1217 |
class BlockPrinter: public BlockClosure { |
|
1218 |
private: |
|
1219 |
InstructionPrinter* _ip; |
|
1220 |
bool _cfg_only; |
|
1221 |
bool _live_only; |
|
1222 |
||
1223 |
public: |
|
1224 |
BlockPrinter(InstructionPrinter* ip, bool cfg_only, bool live_only = false) { |
|
1225 |
_ip = ip; |
|
1226 |
_cfg_only = cfg_only; |
|
1227 |
_live_only = live_only; |
|
1228 |
} |
|
1229 |
||
1230 |
virtual void block_do(BlockBegin* block) { |
|
1231 |
if (_cfg_only) { |
|
1232 |
_ip->print_instr(block); tty->cr(); |
|
1233 |
} else { |
|
1234 |
block->print_block(*_ip, _live_only); |
|
1235 |
} |
|
1236 |
} |
|
1237 |
}; |
|
1238 |
||
1239 |
||
1240 |
void IR::print(BlockBegin* start, bool cfg_only, bool live_only) { |
|
1241 |
ttyLocker ttyl; |
|
1242 |
InstructionPrinter ip(!cfg_only); |
|
1243 |
BlockPrinter bp(&ip, cfg_only, live_only); |
|
1244 |
start->iterate_preorder(&bp); |
|
1245 |
tty->cr(); |
|
1246 |
} |
|
1247 |
||
1248 |
void IR::print(bool cfg_only, bool live_only) { |
|
1249 |
if (is_valid()) { |
|
1250 |
print(start(), cfg_only, live_only); |
|
1251 |
} else { |
|
1252 |
tty->print_cr("invalid IR"); |
|
1253 |
} |
|
1254 |
} |
|
1255 |
||
1256 |
||
1257 |
define_array(BlockListArray, BlockList*) |
|
1258 |
define_stack(BlockListList, BlockListArray) |
|
1259 |
||
1260 |
class PredecessorValidator : public BlockClosure { |
|
1261 |
private: |
|
1262 |
BlockListList* _predecessors; |
|
1263 |
BlockList* _blocks; |
|
1264 |
||
1265 |
static int cmp(BlockBegin** a, BlockBegin** b) { |
|
1266 |
return (*a)->block_id() - (*b)->block_id(); |
|
1267 |
} |
|
1268 |
||
1269 |
public: |
|
1270 |
PredecessorValidator(IR* hir) { |
|
1271 |
ResourceMark rm; |
|
1272 |
_predecessors = new BlockListList(BlockBegin::number_of_blocks(), NULL); |
|
1273 |
_blocks = new BlockList(); |
|
1274 |
||
1275 |
int i; |
|
1276 |
hir->start()->iterate_preorder(this); |
|
1277 |
if (hir->code() != NULL) { |
|
1278 |
assert(hir->code()->length() == _blocks->length(), "must match"); |
|
1279 |
for (i = 0; i < _blocks->length(); i++) { |
|
1280 |
assert(hir->code()->contains(_blocks->at(i)), "should be in both lists"); |
|
1281 |
} |
|
1282 |
} |
|
1283 |
||
1284 |
for (i = 0; i < _blocks->length(); i++) { |
|
1285 |
BlockBegin* block = _blocks->at(i); |
|
1286 |
BlockList* preds = _predecessors->at(block->block_id()); |
|
1287 |
if (preds == NULL) { |
|
1288 |
assert(block->number_of_preds() == 0, "should be the same"); |
|
1289 |
continue; |
|
1290 |
} |
|
1291 |
||
1292 |
// clone the pred list so we can mutate it |
|
1293 |
BlockList* pred_copy = new BlockList(); |
|
1294 |
int j; |
|
1295 |
for (j = 0; j < block->number_of_preds(); j++) { |
|
1296 |
pred_copy->append(block->pred_at(j)); |
|
1297 |
} |
|
1298 |
// sort them in the same order |
|
1299 |
preds->sort(cmp); |
|
1300 |
pred_copy->sort(cmp); |
|
1301 |
int length = MIN2(preds->length(), block->number_of_preds()); |
|
1302 |
for (j = 0; j < block->number_of_preds(); j++) { |
|
1303 |
assert(preds->at(j) == pred_copy->at(j), "must match"); |
|
1304 |
} |
|
1305 |
||
1306 |
assert(preds->length() == block->number_of_preds(), "should be the same"); |
|
1307 |
} |
|
1308 |
} |
|
1309 |
||
1310 |
virtual void block_do(BlockBegin* block) { |
|
1311 |
_blocks->append(block); |
|
1312 |
BlockEnd* be = block->end(); |
|
1313 |
int n = be->number_of_sux(); |
|
1314 |
int i; |
|
1315 |
for (i = 0; i < n; i++) { |
|
1316 |
BlockBegin* sux = be->sux_at(i); |
|
1317 |
assert(!sux->is_set(BlockBegin::exception_entry_flag), "must not be xhandler"); |
|
1318 |
||
1319 |
BlockList* preds = _predecessors->at_grow(sux->block_id(), NULL); |
|
1320 |
if (preds == NULL) { |
|
1321 |
preds = new BlockList(); |
|
1322 |
_predecessors->at_put(sux->block_id(), preds); |
|
1323 |
} |
|
1324 |
preds->append(block); |
|
1325 |
} |
|
1326 |
||
1327 |
n = block->number_of_exception_handlers(); |
|
1328 |
for (i = 0; i < n; i++) { |
|
1329 |
BlockBegin* sux = block->exception_handler_at(i); |
|
1330 |
assert(sux->is_set(BlockBegin::exception_entry_flag), "must be xhandler"); |
|
1331 |
||
1332 |
BlockList* preds = _predecessors->at_grow(sux->block_id(), NULL); |
|
1333 |
if (preds == NULL) { |
|
1334 |
preds = new BlockList(); |
|
1335 |
_predecessors->at_put(sux->block_id(), preds); |
|
1336 |
} |
|
1337 |
preds->append(block); |
|
1338 |
} |
|
1339 |
} |
|
1340 |
}; |
|
1341 |
||
16611 | 1342 |
class VerifyBlockBeginField : public BlockClosure { |
1343 |
||
1344 |
public: |
|
1345 |
||
1346 |
virtual void block_do(BlockBegin *block) { |
|
1347 |
for ( Instruction *cur = block; cur != NULL; cur = cur->next()) { |
|
1348 |
assert(cur->block() == block, "Block begin is not correct"); |
|
1349 |
} |
|
1350 |
} |
|
1351 |
}; |
|
1352 |
||
1 | 1353 |
void IR::verify() { |
1354 |
#ifdef ASSERT |
|
1355 |
PredecessorValidator pv(this); |
|
16611 | 1356 |
VerifyBlockBeginField verifier; |
1357 |
this->iterate_postorder(&verifier); |
|
1 | 1358 |
#endif |
1359 |
} |
|
1360 |
||
1361 |
#endif // PRODUCT |
|
1362 |
||
5707 | 1363 |
void SubstitutionResolver::visit(Value* v) { |
1 | 1364 |
Value v0 = *v; |
1365 |
if (v0) { |
|
1366 |
Value vs = v0->subst(); |
|
1367 |
if (vs != v0) { |
|
1368 |
*v = v0->subst(); |
|
1369 |
} |
|
1370 |
} |
|
1371 |
} |
|
1372 |
||
1373 |
#ifdef ASSERT |
|
5707 | 1374 |
class SubstitutionChecker: public ValueVisitor { |
1375 |
void visit(Value* v) { |
|
1376 |
Value v0 = *v; |
|
1377 |
if (v0) { |
|
1378 |
Value vs = v0->subst(); |
|
1379 |
assert(vs == v0, "missed substitution"); |
|
1380 |
} |
|
1 | 1381 |
} |
5707 | 1382 |
}; |
1 | 1383 |
#endif |
1384 |
||
1385 |
||
1386 |
void SubstitutionResolver::block_do(BlockBegin* block) { |
|
1387 |
Instruction* last = NULL; |
|
1388 |
for (Instruction* n = block; n != NULL;) { |
|
5707 | 1389 |
n->values_do(this); |
1 | 1390 |
// need to remove this instruction from the instruction stream |
1391 |
if (n->subst() != n) { |
|
1392 |
assert(last != NULL, "must have last"); |
|
6745 | 1393 |
last->set_next(n->next()); |
1 | 1394 |
} else { |
1395 |
last = n; |
|
1396 |
} |
|
1397 |
n = last->next(); |
|
1398 |
} |
|
1399 |
||
1400 |
#ifdef ASSERT |
|
5707 | 1401 |
SubstitutionChecker check_substitute; |
1402 |
if (block->state()) block->state()->values_do(&check_substitute); |
|
1403 |
block->block_values_do(&check_substitute); |
|
1404 |
if (block->end() && block->end()->state()) block->end()->state()->values_do(&check_substitute); |
|
1 | 1405 |
#endif |
1406 |
} |