1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 1.2 +++ b/src/share/vm/ci/ciTypeFlow.hpp Sat Dec 01 00:00:00 2007 +0000 1.3 @@ -0,0 +1,714 @@ 1.4 +/* 1.5 + * Copyright 2000-2006 Sun Microsystems, Inc. All Rights Reserved. 1.6 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 1.7 + * 1.8 + * This code is free software; you can redistribute it and/or modify it 1.9 + * under the terms of the GNU General Public License version 2 only, as 1.10 + * published by the Free Software Foundation. 1.11 + * 1.12 + * This code is distributed in the hope that it will be useful, but WITHOUT 1.13 + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 1.14 + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 1.15 + * version 2 for more details (a copy is included in the LICENSE file that 1.16 + * accompanied this code). 1.17 + * 1.18 + * You should have received a copy of the GNU General Public License version 1.19 + * 2 along with this work; if not, write to the Free Software Foundation, 1.20 + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 1.21 + * 1.22 + * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara, 1.23 + * CA 95054 USA or visit www.sun.com if you need additional information or 1.24 + * have any questions. 1.25 + * 1.26 + */ 1.27 + 1.28 + 1.29 +class ciTypeFlow : public ResourceObj { 1.30 +private: 1.31 + ciEnv* _env; 1.32 + ciMethod* _method; 1.33 + ciMethodBlocks* _methodBlocks; 1.34 + int _osr_bci; 1.35 + 1.36 + // information cached from the method: 1.37 + int _max_locals; 1.38 + int _max_stack; 1.39 + int _code_size; 1.40 + 1.41 + const char* _failure_reason; 1.42 + 1.43 +public: 1.44 + class StateVector; 1.45 + class Block; 1.46 + 1.47 + // Build a type flow analyzer 1.48 + // Do an OSR analysis if osr_bci >= 0. 1.49 + ciTypeFlow(ciEnv* env, ciMethod* method, int osr_bci = InvocationEntryBci); 1.50 + 1.51 + // Accessors 1.52 + ciMethod* method() const { return _method; } 1.53 + ciEnv* env() { return _env; } 1.54 + Arena* arena() { return _env->arena(); } 1.55 + bool is_osr_flow() const{ return _osr_bci != InvocationEntryBci; } 1.56 + int start_bci() const { return is_osr_flow()? _osr_bci: 0; } 1.57 + int max_locals() const { return _max_locals; } 1.58 + int max_stack() const { return _max_stack; } 1.59 + int max_cells() const { return _max_locals + _max_stack; } 1.60 + int code_size() const { return _code_size; } 1.61 + 1.62 + // Represents information about an "active" jsr call. This 1.63 + // class represents a call to the routine at some entry address 1.64 + // with some distinct return address. 1.65 + class JsrRecord : public ResourceObj { 1.66 + private: 1.67 + int _entry_address; 1.68 + int _return_address; 1.69 + public: 1.70 + JsrRecord(int entry_address, int return_address) { 1.71 + _entry_address = entry_address; 1.72 + _return_address = return_address; 1.73 + } 1.74 + 1.75 + int entry_address() const { return _entry_address; } 1.76 + int return_address() const { return _return_address; } 1.77 + 1.78 + void print_on(outputStream* st) const { 1.79 +#ifndef PRODUCT 1.80 + st->print("%d->%d", entry_address(), return_address()); 1.81 +#endif 1.82 + } 1.83 + }; 1.84 + 1.85 + // A JsrSet represents some set of JsrRecords. This class 1.86 + // is used to record a set of all jsr routines which we permit 1.87 + // execution to return (ret) from. 1.88 + // 1.89 + // During abstract interpretation, JsrSets are used to determine 1.90 + // whether two paths which reach a given block are unique, and 1.91 + // should be cloned apart, or are compatible, and should merge 1.92 + // together. 1.93 + // 1.94 + // Note that different amounts of effort can be expended determining 1.95 + // if paths are compatible. <DISCUSSION> 1.96 + class JsrSet : public ResourceObj { 1.97 + private: 1.98 + GrowableArray<JsrRecord*>* _set; 1.99 + 1.100 + JsrRecord* record_at(int i) { 1.101 + return _set->at(i); 1.102 + } 1.103 + 1.104 + // Insert the given JsrRecord into the JsrSet, maintaining the order 1.105 + // of the set and replacing any element with the same entry address. 1.106 + void insert_jsr_record(JsrRecord* record); 1.107 + 1.108 + // Remove the JsrRecord with the given return address from the JsrSet. 1.109 + void remove_jsr_record(int return_address); 1.110 + 1.111 + public: 1.112 + JsrSet(Arena* arena, int default_len = 4); 1.113 + 1.114 + // Copy this JsrSet. 1.115 + void copy_into(JsrSet* jsrs); 1.116 + 1.117 + // Is this JsrSet compatible with some other JsrSet? 1.118 + bool is_compatible_with(JsrSet* other); 1.119 + 1.120 + // Apply the effect of a single bytecode to the JsrSet. 1.121 + void apply_control(ciTypeFlow* analyzer, 1.122 + ciBytecodeStream* str, 1.123 + StateVector* state); 1.124 + 1.125 + // What is the cardinality of this set? 1.126 + int size() const { return _set->length(); } 1.127 + 1.128 + void print_on(outputStream* st) const PRODUCT_RETURN; 1.129 + }; 1.130 + 1.131 + // Used as a combined index for locals and temps 1.132 + enum Cell { 1.133 + Cell_0 1.134 + }; 1.135 + 1.136 + // A StateVector summarizes the type information at some 1.137 + // point in the program 1.138 + class StateVector : public ResourceObj { 1.139 + private: 1.140 + ciType** _types; 1.141 + int _stack_size; 1.142 + int _monitor_count; 1.143 + ciTypeFlow* _outer; 1.144 + 1.145 + int _trap_bci; 1.146 + int _trap_index; 1.147 + 1.148 + static ciType* type_meet_internal(ciType* t1, ciType* t2, ciTypeFlow* analyzer); 1.149 + 1.150 + public: 1.151 + // Special elements in our type lattice. 1.152 + enum { 1.153 + T_TOP = T_VOID, // why not? 1.154 + T_BOTTOM = T_CONFLICT, 1.155 + T_LONG2 = T_SHORT, // 2nd word of T_LONG 1.156 + T_DOUBLE2 = T_CHAR, // 2nd word of T_DOUBLE 1.157 + T_NULL = T_BYTE // for now. 1.158 + }; 1.159 + static ciType* top_type() { return ciType::make((BasicType)T_TOP); } 1.160 + static ciType* bottom_type() { return ciType::make((BasicType)T_BOTTOM); } 1.161 + static ciType* long2_type() { return ciType::make((BasicType)T_LONG2); } 1.162 + static ciType* double2_type(){ return ciType::make((BasicType)T_DOUBLE2); } 1.163 + static ciType* null_type() { return ciType::make((BasicType)T_NULL); } 1.164 + 1.165 + static ciType* half_type(ciType* t) { 1.166 + switch (t->basic_type()) { 1.167 + case T_LONG: return long2_type(); 1.168 + case T_DOUBLE: return double2_type(); 1.169 + default: ShouldNotReachHere(); return NULL; 1.170 + } 1.171 + } 1.172 + 1.173 + // The meet operation for our type lattice. 1.174 + ciType* type_meet(ciType* t1, ciType* t2) { 1.175 + return type_meet_internal(t1, t2, outer()); 1.176 + } 1.177 + 1.178 + // Accessors 1.179 + ciTypeFlow* outer() const { return _outer; } 1.180 + 1.181 + int stack_size() const { return _stack_size; } 1.182 + void set_stack_size(int ss) { _stack_size = ss; } 1.183 + 1.184 + int monitor_count() const { return _monitor_count; } 1.185 + void set_monitor_count(int mc) { _monitor_count = mc; } 1.186 + 1.187 + static Cell start_cell() { return (Cell)0; } 1.188 + static Cell next_cell(Cell c) { return (Cell)(((int)c) + 1); } 1.189 + Cell limit_cell() const { 1.190 + return (Cell)(outer()->max_locals() + stack_size()); 1.191 + } 1.192 + 1.193 + // Cell creation 1.194 + Cell local(int lnum) const { 1.195 + assert(lnum < outer()->max_locals(), "index check"); 1.196 + return (Cell)(lnum); 1.197 + } 1.198 + 1.199 + Cell stack(int snum) const { 1.200 + assert(snum < stack_size(), "index check"); 1.201 + return (Cell)(outer()->max_locals() + snum); 1.202 + } 1.203 + 1.204 + Cell tos() const { return stack(stack_size()-1); } 1.205 + 1.206 + // For external use only: 1.207 + ciType* local_type_at(int i) const { return type_at(local(i)); } 1.208 + ciType* stack_type_at(int i) const { return type_at(stack(i)); } 1.209 + 1.210 + // Accessors for the type of some Cell c 1.211 + ciType* type_at(Cell c) const { 1.212 + assert(start_cell() <= c && c < limit_cell(), "out of bounds"); 1.213 + return _types[c]; 1.214 + } 1.215 + 1.216 + void set_type_at(Cell c, ciType* type) { 1.217 + assert(start_cell() <= c && c < limit_cell(), "out of bounds"); 1.218 + _types[c] = type; 1.219 + } 1.220 + 1.221 + // Top-of-stack operations. 1.222 + void set_type_at_tos(ciType* type) { set_type_at(tos(), type); } 1.223 + ciType* type_at_tos() const { return type_at(tos()); } 1.224 + 1.225 + void push(ciType* type) { 1.226 + _stack_size++; 1.227 + set_type_at_tos(type); 1.228 + } 1.229 + void pop() { 1.230 + debug_only(set_type_at_tos(bottom_type())); 1.231 + _stack_size--; 1.232 + } 1.233 + ciType* pop_value() { 1.234 + ciType* t = type_at_tos(); 1.235 + pop(); 1.236 + return t; 1.237 + } 1.238 + 1.239 + // Convenience operations. 1.240 + bool is_reference(ciType* type) const { 1.241 + return type == null_type() || !type->is_primitive_type(); 1.242 + } 1.243 + bool is_int(ciType* type) const { 1.244 + return type->basic_type() == T_INT; 1.245 + } 1.246 + bool is_long(ciType* type) const { 1.247 + return type->basic_type() == T_LONG; 1.248 + } 1.249 + bool is_float(ciType* type) const { 1.250 + return type->basic_type() == T_FLOAT; 1.251 + } 1.252 + bool is_double(ciType* type) const { 1.253 + return type->basic_type() == T_DOUBLE; 1.254 + } 1.255 + 1.256 + void push_translate(ciType* type); 1.257 + 1.258 + void push_int() { 1.259 + push(ciType::make(T_INT)); 1.260 + } 1.261 + void pop_int() { 1.262 + assert(is_int(type_at_tos()), "must be integer"); 1.263 + pop(); 1.264 + } 1.265 + void check_int(Cell c) { 1.266 + assert(is_int(type_at(c)), "must be integer"); 1.267 + } 1.268 + void push_double() { 1.269 + push(ciType::make(T_DOUBLE)); 1.270 + push(double2_type()); 1.271 + } 1.272 + void pop_double() { 1.273 + assert(type_at_tos() == double2_type(), "must be 2nd half"); 1.274 + pop(); 1.275 + assert(is_double(type_at_tos()), "must be double"); 1.276 + pop(); 1.277 + } 1.278 + void push_float() { 1.279 + push(ciType::make(T_FLOAT)); 1.280 + } 1.281 + void pop_float() { 1.282 + assert(is_float(type_at_tos()), "must be float"); 1.283 + pop(); 1.284 + } 1.285 + void push_long() { 1.286 + push(ciType::make(T_LONG)); 1.287 + push(long2_type()); 1.288 + } 1.289 + void pop_long() { 1.290 + assert(type_at_tos() == long2_type(), "must be 2nd half"); 1.291 + pop(); 1.292 + assert(is_long(type_at_tos()), "must be long"); 1.293 + pop(); 1.294 + } 1.295 + void push_object(ciKlass* klass) { 1.296 + push(klass); 1.297 + } 1.298 + void pop_object() { 1.299 + assert(is_reference(type_at_tos()), "must be reference type"); 1.300 + pop(); 1.301 + } 1.302 + void pop_array() { 1.303 + assert(type_at_tos() == null_type() || 1.304 + type_at_tos()->is_array_klass(), "must be array type"); 1.305 + pop(); 1.306 + } 1.307 + // pop_objArray and pop_typeArray narrow the tos to ciObjArrayKlass 1.308 + // or ciTypeArrayKlass (resp.). In the rare case that an explicit 1.309 + // null is popped from the stack, we return NULL. Caller beware. 1.310 + ciObjArrayKlass* pop_objArray() { 1.311 + ciType* array = pop_value(); 1.312 + if (array == null_type()) return NULL; 1.313 + assert(array->is_obj_array_klass(), "must be object array type"); 1.314 + return array->as_obj_array_klass(); 1.315 + } 1.316 + ciTypeArrayKlass* pop_typeArray() { 1.317 + ciType* array = pop_value(); 1.318 + if (array == null_type()) return NULL; 1.319 + assert(array->is_type_array_klass(), "must be prim array type"); 1.320 + return array->as_type_array_klass(); 1.321 + } 1.322 + void push_null() { 1.323 + push(null_type()); 1.324 + } 1.325 + void do_null_assert(ciKlass* unloaded_klass); 1.326 + 1.327 + // Helper convenience routines. 1.328 + void do_aaload(ciBytecodeStream* str); 1.329 + void do_checkcast(ciBytecodeStream* str); 1.330 + void do_getfield(ciBytecodeStream* str); 1.331 + void do_getstatic(ciBytecodeStream* str); 1.332 + void do_invoke(ciBytecodeStream* str, bool has_receiver); 1.333 + void do_jsr(ciBytecodeStream* str); 1.334 + void do_ldc(ciBytecodeStream* str); 1.335 + void do_multianewarray(ciBytecodeStream* str); 1.336 + void do_new(ciBytecodeStream* str); 1.337 + void do_newarray(ciBytecodeStream* str); 1.338 + void do_putfield(ciBytecodeStream* str); 1.339 + void do_putstatic(ciBytecodeStream* str); 1.340 + void do_ret(ciBytecodeStream* str); 1.341 + 1.342 + void overwrite_local_double_long(int index) { 1.343 + // Invalidate the previous local if it contains first half of 1.344 + // a double or long value since it's seconf half is being overwritten. 1.345 + int prev_index = index - 1; 1.346 + if (prev_index >= 0 && 1.347 + (is_double(type_at(local(prev_index))) || 1.348 + is_long(type_at(local(prev_index))))) { 1.349 + set_type_at(local(prev_index), bottom_type()); 1.350 + } 1.351 + } 1.352 + 1.353 + void load_local_object(int index) { 1.354 + ciType* type = type_at(local(index)); 1.355 + assert(is_reference(type), "must be reference type"); 1.356 + push(type); 1.357 + } 1.358 + void store_local_object(int index) { 1.359 + ciType* type = pop_value(); 1.360 + assert(is_reference(type) || type->is_return_address(), 1.361 + "must be reference type or return address"); 1.362 + overwrite_local_double_long(index); 1.363 + set_type_at(local(index), type); 1.364 + } 1.365 + 1.366 + void load_local_double(int index) { 1.367 + ciType* type = type_at(local(index)); 1.368 + ciType* type2 = type_at(local(index+1)); 1.369 + assert(is_double(type), "must be double type"); 1.370 + assert(type2 == double2_type(), "must be 2nd half"); 1.371 + push(type); 1.372 + push(double2_type()); 1.373 + } 1.374 + void store_local_double(int index) { 1.375 + ciType* type2 = pop_value(); 1.376 + ciType* type = pop_value(); 1.377 + assert(is_double(type), "must be double"); 1.378 + assert(type2 == double2_type(), "must be 2nd half"); 1.379 + overwrite_local_double_long(index); 1.380 + set_type_at(local(index), type); 1.381 + set_type_at(local(index+1), type2); 1.382 + } 1.383 + 1.384 + void load_local_float(int index) { 1.385 + ciType* type = type_at(local(index)); 1.386 + assert(is_float(type), "must be float type"); 1.387 + push(type); 1.388 + } 1.389 + void store_local_float(int index) { 1.390 + ciType* type = pop_value(); 1.391 + assert(is_float(type), "must be float type"); 1.392 + overwrite_local_double_long(index); 1.393 + set_type_at(local(index), type); 1.394 + } 1.395 + 1.396 + void load_local_int(int index) { 1.397 + ciType* type = type_at(local(index)); 1.398 + assert(is_int(type), "must be int type"); 1.399 + push(type); 1.400 + } 1.401 + void store_local_int(int index) { 1.402 + ciType* type = pop_value(); 1.403 + assert(is_int(type), "must be int type"); 1.404 + overwrite_local_double_long(index); 1.405 + set_type_at(local(index), type); 1.406 + } 1.407 + 1.408 + void load_local_long(int index) { 1.409 + ciType* type = type_at(local(index)); 1.410 + ciType* type2 = type_at(local(index+1)); 1.411 + assert(is_long(type), "must be long type"); 1.412 + assert(type2 == long2_type(), "must be 2nd half"); 1.413 + push(type); 1.414 + push(long2_type()); 1.415 + } 1.416 + void store_local_long(int index) { 1.417 + ciType* type2 = pop_value(); 1.418 + ciType* type = pop_value(); 1.419 + assert(is_long(type), "must be long"); 1.420 + assert(type2 == long2_type(), "must be 2nd half"); 1.421 + overwrite_local_double_long(index); 1.422 + set_type_at(local(index), type); 1.423 + set_type_at(local(index+1), type2); 1.424 + } 1.425 + 1.426 + // Stop interpretation of this path with a trap. 1.427 + void trap(ciBytecodeStream* str, ciKlass* klass, int index); 1.428 + 1.429 + public: 1.430 + StateVector(ciTypeFlow* outer); 1.431 + 1.432 + // Copy our value into some other StateVector 1.433 + void copy_into(StateVector* copy) const; 1.434 + 1.435 + // Meets this StateVector with another, destructively modifying this 1.436 + // one. Returns true if any modification takes place. 1.437 + bool meet(const StateVector* incoming); 1.438 + 1.439 + // Ditto, except that the incoming state is coming from an exception. 1.440 + bool meet_exception(ciInstanceKlass* exc, const StateVector* incoming); 1.441 + 1.442 + // Apply the effect of one bytecode to this StateVector 1.443 + bool apply_one_bytecode(ciBytecodeStream* stream); 1.444 + 1.445 + // What is the bci of the trap? 1.446 + int trap_bci() { return _trap_bci; } 1.447 + 1.448 + // What is the index associated with the trap? 1.449 + int trap_index() { return _trap_index; } 1.450 + 1.451 + void print_cell_on(outputStream* st, Cell c) const PRODUCT_RETURN; 1.452 + void print_on(outputStream* st) const PRODUCT_RETURN; 1.453 + }; 1.454 + 1.455 + // Parameter for "find_block" calls: 1.456 + // Describes the difference between a public and private copy. 1.457 + enum CreateOption { 1.458 + create_public_copy, 1.459 + create_private_copy, 1.460 + no_create 1.461 + }; 1.462 + 1.463 + // A basic block 1.464 + class Block : public ResourceObj { 1.465 + private: 1.466 + ciBlock* _ciblock; 1.467 + GrowableArray<Block*>* _exceptions; 1.468 + GrowableArray<ciInstanceKlass*>* _exc_klasses; 1.469 + GrowableArray<Block*>* _successors; 1.470 + StateVector* _state; 1.471 + JsrSet* _jsrs; 1.472 + 1.473 + int _trap_bci; 1.474 + int _trap_index; 1.475 + 1.476 + // A reasonable approximation to pre-order, provided.to the client. 1.477 + int _pre_order; 1.478 + 1.479 + // Has this block been cloned for some special purpose? 1.480 + bool _private_copy; 1.481 + 1.482 + // A pointer used for our internal work list 1.483 + Block* _next; 1.484 + bool _on_work_list; 1.485 + 1.486 + ciBlock* ciblock() const { return _ciblock; } 1.487 + StateVector* state() const { return _state; } 1.488 + 1.489 + // Compute the exceptional successors and types for this Block. 1.490 + void compute_exceptions(); 1.491 + 1.492 + public: 1.493 + // constructors 1.494 + Block(ciTypeFlow* outer, ciBlock* ciblk, JsrSet* jsrs); 1.495 + 1.496 + void set_trap(int trap_bci, int trap_index) { 1.497 + _trap_bci = trap_bci; 1.498 + _trap_index = trap_index; 1.499 + assert(has_trap(), ""); 1.500 + } 1.501 + bool has_trap() const { return _trap_bci != -1; } 1.502 + int trap_bci() const { assert(has_trap(), ""); return _trap_bci; } 1.503 + int trap_index() const { assert(has_trap(), ""); return _trap_index; } 1.504 + 1.505 + // accessors 1.506 + ciTypeFlow* outer() const { return state()->outer(); } 1.507 + int start() const { return _ciblock->start_bci(); } 1.508 + int limit() const { return _ciblock->limit_bci(); } 1.509 + int control() const { return _ciblock->control_bci(); } 1.510 + 1.511 + bool is_private_copy() const { return _private_copy; } 1.512 + void set_private_copy(bool z); 1.513 + int private_copy_count() const { return outer()->private_copy_count(ciblock()->index(), _jsrs); } 1.514 + 1.515 + // access to entry state 1.516 + int stack_size() const { return _state->stack_size(); } 1.517 + int monitor_count() const { return _state->monitor_count(); } 1.518 + ciType* local_type_at(int i) const { return _state->local_type_at(i); } 1.519 + ciType* stack_type_at(int i) const { return _state->stack_type_at(i); } 1.520 + 1.521 + // Get the successors for this Block. 1.522 + GrowableArray<Block*>* successors(ciBytecodeStream* str, 1.523 + StateVector* state, 1.524 + JsrSet* jsrs); 1.525 + GrowableArray<Block*>* successors() { 1.526 + assert(_successors != NULL, "must be filled in"); 1.527 + return _successors; 1.528 + } 1.529 + 1.530 + // Helper function for "successors" when making private copies of 1.531 + // loop heads for C2. 1.532 + Block * clone_loop_head(ciTypeFlow* analyzer, 1.533 + int branch_bci, 1.534 + Block* target, 1.535 + JsrSet* jsrs); 1.536 + 1.537 + // Get the exceptional successors for this Block. 1.538 + GrowableArray<Block*>* exceptions() { 1.539 + if (_exceptions == NULL) { 1.540 + compute_exceptions(); 1.541 + } 1.542 + return _exceptions; 1.543 + } 1.544 + 1.545 + // Get the exception klasses corresponding to the 1.546 + // exceptional successors for this Block. 1.547 + GrowableArray<ciInstanceKlass*>* exc_klasses() { 1.548 + if (_exc_klasses == NULL) { 1.549 + compute_exceptions(); 1.550 + } 1.551 + return _exc_klasses; 1.552 + } 1.553 + 1.554 + // Is this Block compatible with a given JsrSet? 1.555 + bool is_compatible_with(JsrSet* other) { 1.556 + return _jsrs->is_compatible_with(other); 1.557 + } 1.558 + 1.559 + // Copy the value of our state vector into another. 1.560 + void copy_state_into(StateVector* copy) const { 1.561 + _state->copy_into(copy); 1.562 + } 1.563 + 1.564 + // Copy the value of our JsrSet into another 1.565 + void copy_jsrs_into(JsrSet* copy) const { 1.566 + _jsrs->copy_into(copy); 1.567 + } 1.568 + 1.569 + // Meets the start state of this block with another state, destructively 1.570 + // modifying this one. Returns true if any modification takes place. 1.571 + bool meet(const StateVector* incoming) { 1.572 + return state()->meet(incoming); 1.573 + } 1.574 + 1.575 + // Ditto, except that the incoming state is coming from an 1.576 + // exception path. This means the stack is replaced by the 1.577 + // appropriate exception type. 1.578 + bool meet_exception(ciInstanceKlass* exc, const StateVector* incoming) { 1.579 + return state()->meet_exception(exc, incoming); 1.580 + } 1.581 + 1.582 + // Work list manipulation 1.583 + void set_next(Block* block) { _next = block; } 1.584 + Block* next() const { return _next; } 1.585 + 1.586 + void set_on_work_list(bool c) { _on_work_list = c; } 1.587 + bool is_on_work_list() const { return _on_work_list; } 1.588 + 1.589 + bool has_pre_order() const { return _pre_order >= 0; } 1.590 + void set_pre_order(int po) { assert(!has_pre_order() && po >= 0, ""); _pre_order = po; } 1.591 + int pre_order() const { assert(has_pre_order(), ""); return _pre_order; } 1.592 + bool is_start() const { return _pre_order == outer()->start_block_num(); } 1.593 + 1.594 + // A ranking used in determining order within the work list. 1.595 + bool is_simpler_than(Block* other); 1.596 + 1.597 + void print_value_on(outputStream* st) const PRODUCT_RETURN; 1.598 + void print_on(outputStream* st) const PRODUCT_RETURN; 1.599 + }; 1.600 + 1.601 + // Standard indexes of successors, for various bytecodes. 1.602 + enum { 1.603 + FALL_THROUGH = 0, // normal control 1.604 + IF_NOT_TAKEN = 0, // the not-taken branch of an if (i.e., fall-through) 1.605 + IF_TAKEN = 1, // the taken branch of an if 1.606 + GOTO_TARGET = 0, // unique successor for goto, jsr, or ret 1.607 + SWITCH_DEFAULT = 0, // default branch of a switch 1.608 + SWITCH_CASES = 1 // first index for any non-default switch branches 1.609 + // Unlike in other blocks, the successors of a switch are listed uniquely. 1.610 + }; 1.611 + 1.612 +private: 1.613 + // A mapping from pre_order to Blocks. This array is created 1.614 + // only at the end of the flow. 1.615 + Block** _block_map; 1.616 + 1.617 + // For each ciBlock index, a list of Blocks which share this ciBlock. 1.618 + GrowableArray<Block*>** _idx_to_blocklist; 1.619 + // count of ciBlocks 1.620 + int _ciblock_count; 1.621 + 1.622 + // Tells if a given instruction is able to generate an exception edge. 1.623 + bool can_trap(ciBytecodeStream& str); 1.624 + 1.625 +public: 1.626 + // Return the block beginning at bci which has a JsrSet compatible 1.627 + // with jsrs. 1.628 + Block* block_at(int bci, JsrSet* set, CreateOption option = create_public_copy); 1.629 + 1.630 + // block factory 1.631 + Block* get_block_for(int ciBlockIndex, JsrSet* jsrs, CreateOption option = create_public_copy); 1.632 + 1.633 + // How many of the blocks have the private_copy bit set? 1.634 + int private_copy_count(int ciBlockIndex, JsrSet* jsrs) const; 1.635 + 1.636 + // Return an existing block containing bci which has a JsrSet compatible 1.637 + // with jsrs, or NULL if there is none. 1.638 + Block* existing_block_at(int bci, JsrSet* set) { return block_at(bci, set, no_create); } 1.639 + 1.640 + // Tell whether the flow analysis has encountered an error of some sort. 1.641 + bool failing() { return env()->failing() || _failure_reason != NULL; } 1.642 + 1.643 + // Reason this compilation is failing, such as "too many basic blocks". 1.644 + const char* failure_reason() { return _failure_reason; } 1.645 + 1.646 + // Note a failure. 1.647 + void record_failure(const char* reason); 1.648 + 1.649 + // Return the block of a given pre-order number. 1.650 + int have_block_count() const { return _block_map != NULL; } 1.651 + int block_count() const { assert(have_block_count(), ""); 1.652 + return _next_pre_order; } 1.653 + Block* pre_order_at(int po) const { assert(0 <= po && po < block_count(), "out of bounds"); 1.654 + return _block_map[po]; } 1.655 + Block* start_block() const { return pre_order_at(start_block_num()); } 1.656 + int start_block_num() const { return 0; } 1.657 + 1.658 +private: 1.659 + // A work list used during flow analysis. 1.660 + Block* _work_list; 1.661 + 1.662 + // Next Block::_pre_order. After mapping, doubles as block_count. 1.663 + int _next_pre_order; 1.664 + 1.665 + // Are there more blocks on the work list? 1.666 + bool work_list_empty() { return _work_list == NULL; } 1.667 + 1.668 + // Get the next basic block from our work list. 1.669 + Block* work_list_next(); 1.670 + 1.671 + // Add a basic block to our work list. 1.672 + void add_to_work_list(Block* block); 1.673 + 1.674 + // State used for make_jsr_record 1.675 + int _jsr_count; 1.676 + GrowableArray<JsrRecord*>* _jsr_records; 1.677 + 1.678 +public: 1.679 + // Make a JsrRecord for a given (entry, return) pair, if such a record 1.680 + // does not already exist. 1.681 + JsrRecord* make_jsr_record(int entry_address, int return_address); 1.682 + 1.683 +private: 1.684 + // Get the initial state for start_bci: 1.685 + const StateVector* get_start_state(); 1.686 + 1.687 + // Merge the current state into all exceptional successors at the 1.688 + // current point in the code. 1.689 + void flow_exceptions(GrowableArray<Block*>* exceptions, 1.690 + GrowableArray<ciInstanceKlass*>* exc_klasses, 1.691 + StateVector* state); 1.692 + 1.693 + // Merge the current state into all successors at the current point 1.694 + // in the code. 1.695 + void flow_successors(GrowableArray<Block*>* successors, 1.696 + StateVector* state); 1.697 + 1.698 + // Interpret the effects of the bytecodes on the incoming state 1.699 + // vector of a basic block. Push the changed state to succeeding 1.700 + // basic blocks. 1.701 + void flow_block(Block* block, 1.702 + StateVector* scratch_state, 1.703 + JsrSet* scratch_jsrs); 1.704 + 1.705 + // Perform the type flow analysis, creating and cloning Blocks as 1.706 + // necessary. 1.707 + void flow_types(); 1.708 + 1.709 + // Create the block map, which indexes blocks in pre_order. 1.710 + void map_blocks(); 1.711 + 1.712 +public: 1.713 + // Perform type inference flow analysis. 1.714 + void do_flow(); 1.715 + 1.716 + void print_on(outputStream* st) const PRODUCT_RETURN; 1.717 +};