1.1 --- a/src/share/vm/ci/ciTypeFlow.hpp Wed Sep 17 08:29:17 2008 -0700
1.2 +++ b/src/share/vm/ci/ciTypeFlow.hpp Wed Sep 17 12:59:52 2008 -0700
1.3 @@ -34,11 +34,13 @@
1.4 int _max_locals;
1.5 int _max_stack;
1.6 int _code_size;
1.7 + bool _has_irreducible_entry;
1.8
1.9 const char* _failure_reason;
1.10
1.11 public:
1.12 class StateVector;
1.13 + class Loop;
1.14 class Block;
1.15
1.16 // Build a type flow analyzer
1.17 @@ -55,6 +57,7 @@
1.18 int max_stack() const { return _max_stack; }
1.19 int max_cells() const { return _max_locals + _max_stack; }
1.20 int code_size() const { return _code_size; }
1.21 + bool has_irreducible_entry() const { return _has_irreducible_entry; }
1.22
1.23 // Represents information about an "active" jsr call. This
1.24 // class represents a call to the routine at some entry address
1.25 @@ -125,6 +128,19 @@
1.26 void print_on(outputStream* st) const PRODUCT_RETURN;
1.27 };
1.28
1.29 + class LocalSet VALUE_OBJ_CLASS_SPEC {
1.30 + private:
1.31 + enum Constants { max = 63 };
1.32 + uint64_t _bits;
1.33 + public:
1.34 + LocalSet() : _bits(0) {}
1.35 + void add(uint32_t i) { if (i < (uint32_t)max) _bits |= (1LL << i); }
1.36 + void add(LocalSet* ls) { _bits |= ls->_bits; }
1.37 + bool test(uint32_t i) const { return i < (uint32_t)max ? (_bits>>i)&1U : true; }
1.38 + void clear() { _bits = 0; }
1.39 + void print_on(outputStream* st, int limit) const PRODUCT_RETURN;
1.40 + };
1.41 +
1.42 // Used as a combined index for locals and temps
1.43 enum Cell {
1.44 Cell_0, Cell_max = INT_MAX
1.45 @@ -142,6 +158,8 @@
1.46 int _trap_bci;
1.47 int _trap_index;
1.48
1.49 + LocalSet _def_locals; // For entire block
1.50 +
1.51 static ciType* type_meet_internal(ciType* t1, ciType* t2, ciTypeFlow* analyzer);
1.52
1.53 public:
1.54 @@ -181,6 +199,9 @@
1.55 int monitor_count() const { return _monitor_count; }
1.56 void set_monitor_count(int mc) { _monitor_count = mc; }
1.57
1.58 + LocalSet* def_locals() { return &_def_locals; }
1.59 + const LocalSet* def_locals() const { return &_def_locals; }
1.60 +
1.61 static Cell start_cell() { return (Cell)0; }
1.62 static Cell next_cell(Cell c) { return (Cell)(((int)c) + 1); }
1.63 Cell limit_cell() const {
1.64 @@ -250,6 +271,10 @@
1.65 return type->basic_type() == T_DOUBLE;
1.66 }
1.67
1.68 + void store_to_local(int lnum) {
1.69 + _def_locals.add((uint) lnum);
1.70 + }
1.71 +
1.72 void push_translate(ciType* type);
1.73
1.74 void push_int() {
1.75 @@ -358,6 +383,7 @@
1.76 "must be reference type or return address");
1.77 overwrite_local_double_long(index);
1.78 set_type_at(local(index), type);
1.79 + store_to_local(index);
1.80 }
1.81
1.82 void load_local_double(int index) {
1.83 @@ -376,6 +402,8 @@
1.84 overwrite_local_double_long(index);
1.85 set_type_at(local(index), type);
1.86 set_type_at(local(index+1), type2);
1.87 + store_to_local(index);
1.88 + store_to_local(index+1);
1.89 }
1.90
1.91 void load_local_float(int index) {
1.92 @@ -388,6 +416,7 @@
1.93 assert(is_float(type), "must be float type");
1.94 overwrite_local_double_long(index);
1.95 set_type_at(local(index), type);
1.96 + store_to_local(index);
1.97 }
1.98
1.99 void load_local_int(int index) {
1.100 @@ -400,6 +429,7 @@
1.101 assert(is_int(type), "must be int type");
1.102 overwrite_local_double_long(index);
1.103 set_type_at(local(index), type);
1.104 + store_to_local(index);
1.105 }
1.106
1.107 void load_local_long(int index) {
1.108 @@ -418,6 +448,8 @@
1.109 overwrite_local_double_long(index);
1.110 set_type_at(local(index), type);
1.111 set_type_at(local(index+1), type2);
1.112 + store_to_local(index);
1.113 + store_to_local(index+1);
1.114 }
1.115
1.116 // Stop interpretation of this path with a trap.
1.117 @@ -450,13 +482,31 @@
1.118 };
1.119
1.120 // Parameter for "find_block" calls:
1.121 - // Describes the difference between a public and private copy.
1.122 + // Describes the difference between a public and backedge copy.
1.123 enum CreateOption {
1.124 create_public_copy,
1.125 - create_private_copy,
1.126 + create_backedge_copy,
1.127 no_create
1.128 };
1.129
1.130 + // Successor iterator
1.131 + class SuccIter : public StackObj {
1.132 + private:
1.133 + Block* _pred;
1.134 + int _index;
1.135 + Block* _succ;
1.136 + public:
1.137 + SuccIter() : _pred(NULL), _index(-1), _succ(NULL) {}
1.138 + SuccIter(Block* pred) : _pred(pred), _index(-1), _succ(NULL) { next(); }
1.139 + int index() { return _index; }
1.140 + Block* pred() { return _pred; } // Return predecessor
1.141 + bool done() { return _index < 0; } // Finished?
1.142 + Block* succ() { return _succ; } // Return current successor
1.143 + void next(); // Advance
1.144 + void set_succ(Block* succ); // Update current successor
1.145 + bool is_normal_ctrl() { return index() < _pred->successors()->length(); }
1.146 + };
1.147 +
1.148 // A basic block
1.149 class Block : public ResourceObj {
1.150 private:
1.151 @@ -470,15 +520,24 @@
1.152 int _trap_bci;
1.153 int _trap_index;
1.154
1.155 - // A reasonable approximation to pre-order, provided.to the client.
1.156 + // pre_order, assigned at first visit. Used as block ID and "visited" tag
1.157 int _pre_order;
1.158
1.159 - // Has this block been cloned for some special purpose?
1.160 - bool _private_copy;
1.161 + // A post-order, used to compute the reverse post order (RPO) provided to the client
1.162 + int _post_order; // used to compute rpo
1.163 +
1.164 + // Has this block been cloned for a loop backedge?
1.165 + bool _backedge_copy;
1.166
1.167 // A pointer used for our internal work list
1.168 - Block* _next;
1.169 - bool _on_work_list;
1.170 + Block* _next;
1.171 + bool _on_work_list; // on the work list
1.172 + Block* _rpo_next; // Reverse post order list
1.173 +
1.174 + // Loop info
1.175 + Loop* _loop; // nearest loop
1.176 + bool _irreducible_entry; // entry to irreducible loop
1.177 + bool _exception_entry; // entry to exception handler
1.178
1.179 ciBlock* ciblock() const { return _ciblock; }
1.180 StateVector* state() const { return _state; }
1.181 @@ -504,10 +563,11 @@
1.182 int start() const { return _ciblock->start_bci(); }
1.183 int limit() const { return _ciblock->limit_bci(); }
1.184 int control() const { return _ciblock->control_bci(); }
1.185 + JsrSet* jsrs() const { return _jsrs; }
1.186
1.187 - bool is_private_copy() const { return _private_copy; }
1.188 - void set_private_copy(bool z);
1.189 - int private_copy_count() const { return outer()->private_copy_count(ciblock()->index(), _jsrs); }
1.190 + bool is_backedge_copy() const { return _backedge_copy; }
1.191 + void set_backedge_copy(bool z);
1.192 + int backedge_copy_count() const { return outer()->backedge_copy_count(ciblock()->index(), _jsrs); }
1.193
1.194 // access to entry state
1.195 int stack_size() const { return _state->stack_size(); }
1.196 @@ -515,6 +575,20 @@
1.197 ciType* local_type_at(int i) const { return _state->local_type_at(i); }
1.198 ciType* stack_type_at(int i) const { return _state->stack_type_at(i); }
1.199
1.200 + // Data flow on locals
1.201 + bool is_invariant_local(uint v) const {
1.202 + assert(is_loop_head(), "only loop heads");
1.203 + // Find outermost loop with same loop head
1.204 + Loop* lp = loop();
1.205 + while (lp->parent() != NULL) {
1.206 + if (lp->parent()->head() != lp->head()) break;
1.207 + lp = lp->parent();
1.208 + }
1.209 + return !lp->def_locals()->test(v);
1.210 + }
1.211 + LocalSet* def_locals() { return _state->def_locals(); }
1.212 + const LocalSet* def_locals() const { return _state->def_locals(); }
1.213 +
1.214 // Get the successors for this Block.
1.215 GrowableArray<Block*>* successors(ciBytecodeStream* str,
1.216 StateVector* state,
1.217 @@ -524,13 +598,6 @@
1.218 return _successors;
1.219 }
1.220
1.221 - // Helper function for "successors" when making private copies of
1.222 - // loop heads for C2.
1.223 - Block * clone_loop_head(ciTypeFlow* analyzer,
1.224 - int branch_bci,
1.225 - Block* target,
1.226 - JsrSet* jsrs);
1.227 -
1.228 // Get the exceptional successors for this Block.
1.229 GrowableArray<Block*>* exceptions() {
1.230 if (_exceptions == NULL) {
1.231 @@ -584,17 +651,126 @@
1.232 bool is_on_work_list() const { return _on_work_list; }
1.233
1.234 bool has_pre_order() const { return _pre_order >= 0; }
1.235 - void set_pre_order(int po) { assert(!has_pre_order() && po >= 0, ""); _pre_order = po; }
1.236 + void set_pre_order(int po) { assert(!has_pre_order(), ""); _pre_order = po; }
1.237 int pre_order() const { assert(has_pre_order(), ""); return _pre_order; }
1.238 + void set_next_pre_order() { set_pre_order(outer()->inc_next_pre_order()); }
1.239 bool is_start() const { return _pre_order == outer()->start_block_num(); }
1.240
1.241 - // A ranking used in determining order within the work list.
1.242 - bool is_simpler_than(Block* other);
1.243 + // Reverse post order
1.244 + void df_init();
1.245 + bool has_post_order() const { return _post_order >= 0; }
1.246 + void set_post_order(int po) { assert(!has_post_order() && po >= 0, ""); _post_order = po; }
1.247 + void reset_post_order(int o){ _post_order = o; }
1.248 + int post_order() const { assert(has_post_order(), ""); return _post_order; }
1.249 +
1.250 + bool has_rpo() const { return has_post_order() && outer()->have_block_count(); }
1.251 + int rpo() const { assert(has_rpo(), ""); return outer()->block_count() - post_order() - 1; }
1.252 + void set_rpo_next(Block* b) { _rpo_next = b; }
1.253 + Block* rpo_next() { return _rpo_next; }
1.254 +
1.255 + // Loops
1.256 + Loop* loop() const { return _loop; }
1.257 + void set_loop(Loop* lp) { _loop = lp; }
1.258 + bool is_loop_head() const { return _loop && _loop->head() == this; }
1.259 + void set_irreducible_entry(bool c) { _irreducible_entry = c; }
1.260 + bool is_irreducible_entry() const { return _irreducible_entry; }
1.261 + bool is_visited() const { return has_pre_order(); }
1.262 + bool is_post_visited() const { return has_post_order(); }
1.263 + bool is_clonable_exit(Loop* lp);
1.264 + Block* looping_succ(Loop* lp); // Successor inside of loop
1.265 + bool is_single_entry_loop_head() const {
1.266 + if (!is_loop_head()) return false;
1.267 + for (Loop* lp = loop(); lp != NULL && lp->head() == this; lp = lp->parent())
1.268 + if (lp->is_irreducible()) return false;
1.269 + return true;
1.270 + }
1.271
1.272 void print_value_on(outputStream* st) const PRODUCT_RETURN;
1.273 void print_on(outputStream* st) const PRODUCT_RETURN;
1.274 };
1.275
1.276 + // Loop
1.277 + class Loop : public ResourceObj {
1.278 + private:
1.279 + Loop* _parent;
1.280 + Loop* _sibling; // List of siblings, null terminated
1.281 + Loop* _child; // Head of child list threaded thru sibling pointer
1.282 + Block* _head; // Head of loop
1.283 + Block* _tail; // Tail of loop
1.284 + bool _irreducible;
1.285 + LocalSet _def_locals;
1.286 +
1.287 + public:
1.288 + Loop(Block* head, Block* tail) :
1.289 + _head(head), _tail(tail),
1.290 + _parent(NULL), _sibling(NULL), _child(NULL),
1.291 + _irreducible(false), _def_locals() {}
1.292 +
1.293 + Loop* parent() const { return _parent; }
1.294 + Loop* sibling() const { return _sibling; }
1.295 + Loop* child() const { return _child; }
1.296 + Block* head() const { return _head; }
1.297 + Block* tail() const { return _tail; }
1.298 + void set_parent(Loop* p) { _parent = p; }
1.299 + void set_sibling(Loop* s) { _sibling = s; }
1.300 + void set_child(Loop* c) { _child = c; }
1.301 + void set_head(Block* hd) { _head = hd; }
1.302 + void set_tail(Block* tl) { _tail = tl; }
1.303 +
1.304 + int depth() const; // nesting depth
1.305 +
1.306 + // Returns true if lp is a nested loop or us.
1.307 + bool contains(Loop* lp) const;
1.308 + bool contains(Block* blk) const { return contains(blk->loop()); }
1.309 +
1.310 + // Data flow on locals
1.311 + LocalSet* def_locals() { return &_def_locals; }
1.312 + const LocalSet* def_locals() const { return &_def_locals; }
1.313 +
1.314 + // Merge the branch lp into this branch, sorting on the loop head
1.315 + // pre_orders. Returns the new branch.
1.316 + Loop* sorted_merge(Loop* lp);
1.317 +
1.318 + // Mark non-single entry to loop
1.319 + void set_irreducible(Block* entry) {
1.320 + _irreducible = true;
1.321 + entry->set_irreducible_entry(true);
1.322 + }
1.323 + bool is_irreducible() const { return _irreducible; }
1.324 +
1.325 + bool is_root() const { return _tail->pre_order() == max_jint; }
1.326 +
1.327 + void print(outputStream* st = tty, int indent = 0) const PRODUCT_RETURN;
1.328 + };
1.329 +
1.330 + // Postorder iteration over the loop tree.
1.331 + class PostorderLoops : public StackObj {
1.332 + private:
1.333 + Loop* _root;
1.334 + Loop* _current;
1.335 + public:
1.336 + PostorderLoops(Loop* root) : _root(root), _current(root) {
1.337 + while (_current->child() != NULL) {
1.338 + _current = _current->child();
1.339 + }
1.340 + }
1.341 + bool done() { return _current == NULL; } // Finished iterating?
1.342 + void next(); // Advance to next loop
1.343 + Loop* current() { return _current; } // Return current loop.
1.344 + };
1.345 +
1.346 + // Preorder iteration over the loop tree.
1.347 + class PreorderLoops : public StackObj {
1.348 + private:
1.349 + Loop* _root;
1.350 + Loop* _current;
1.351 + public:
1.352 + PreorderLoops(Loop* root) : _root(root), _current(root) {}
1.353 + bool done() { return _current == NULL; } // Finished iterating?
1.354 + void next(); // Advance to next loop
1.355 + Loop* current() { return _current; } // Return current loop.
1.356 + };
1.357 +
1.358 // Standard indexes of successors, for various bytecodes.
1.359 enum {
1.360 FALL_THROUGH = 0, // normal control
1.361 @@ -619,6 +795,12 @@
1.362 // Tells if a given instruction is able to generate an exception edge.
1.363 bool can_trap(ciBytecodeStream& str);
1.364
1.365 + // Clone the loop heads. Returns true if any cloning occurred.
1.366 + bool clone_loop_heads(Loop* lp, StateVector* temp_vector, JsrSet* temp_set);
1.367 +
1.368 + // Clone lp's head and replace tail's successors with clone.
1.369 + Block* clone_loop_head(Loop* lp, StateVector* temp_vector, JsrSet* temp_set);
1.370 +
1.371 public:
1.372 // Return the block beginning at bci which has a JsrSet compatible
1.373 // with jsrs.
1.374 @@ -627,8 +809,8 @@
1.375 // block factory
1.376 Block* get_block_for(int ciBlockIndex, JsrSet* jsrs, CreateOption option = create_public_copy);
1.377
1.378 - // How many of the blocks have the private_copy bit set?
1.379 - int private_copy_count(int ciBlockIndex, JsrSet* jsrs) const;
1.380 + // How many of the blocks have the backedge_copy bit set?
1.381 + int backedge_copy_count(int ciBlockIndex, JsrSet* jsrs) const;
1.382
1.383 // Return an existing block containing bci which has a JsrSet compatible
1.384 // with jsrs, or NULL if there is none.
1.385 @@ -651,11 +833,18 @@
1.386 return _block_map[po]; }
1.387 Block* start_block() const { return pre_order_at(start_block_num()); }
1.388 int start_block_num() const { return 0; }
1.389 + Block* rpo_at(int rpo) const { assert(0 <= rpo && rpo < block_count(), "out of bounds");
1.390 + return _block_map[rpo]; }
1.391 + int next_pre_order() { return _next_pre_order; }
1.392 + int inc_next_pre_order() { return _next_pre_order++; }
1.393
1.394 private:
1.395 // A work list used during flow analysis.
1.396 Block* _work_list;
1.397
1.398 + // List of blocks in reverse post order
1.399 + Block* _rpo_list;
1.400 +
1.401 // Next Block::_pre_order. After mapping, doubles as block_count.
1.402 int _next_pre_order;
1.403
1.404 @@ -668,6 +857,15 @@
1.405 // Add a basic block to our work list.
1.406 void add_to_work_list(Block* block);
1.407
1.408 + // Prepend a basic block to rpo list.
1.409 + void prepend_to_rpo_list(Block* blk) {
1.410 + blk->set_rpo_next(_rpo_list);
1.411 + _rpo_list = blk;
1.412 + }
1.413 +
1.414 + // Root of the loop tree
1.415 + Loop* _loop_tree_root;
1.416 +
1.417 // State used for make_jsr_record
1.418 int _jsr_count;
1.419 GrowableArray<JsrRecord*>* _jsr_records;
1.420 @@ -677,6 +875,9 @@
1.421 // does not already exist.
1.422 JsrRecord* make_jsr_record(int entry_address, int return_address);
1.423
1.424 + void set_loop_tree_root(Loop* ltr) { _loop_tree_root = ltr; }
1.425 + Loop* loop_tree_root() { return _loop_tree_root; }
1.426 +
1.427 private:
1.428 // Get the initial state for start_bci:
1.429 const StateVector* get_start_state();
1.430 @@ -703,6 +904,15 @@
1.431 // necessary.
1.432 void flow_types();
1.433
1.434 + // Perform the depth first type flow analysis. Helper for flow_types.
1.435 + void df_flow_types(Block* start,
1.436 + bool do_flow,
1.437 + StateVector* temp_vector,
1.438 + JsrSet* temp_set);
1.439 +
1.440 + // Incrementally build loop tree.
1.441 + void build_loop_tree(Block* blk);
1.442 +
1.443 // Create the block map, which indexes blocks in pre_order.
1.444 void map_blocks();
1.445
1.446 @@ -711,4 +921,6 @@
1.447 void do_flow();
1.448
1.449 void print_on(outputStream* st) const PRODUCT_RETURN;
1.450 +
1.451 + void rpo_print_on(outputStream* st) const PRODUCT_RETURN;
1.452 };
