Subject: [PATCH] 8255663: Support multiple tails in C2 type flow analysis --- Index: src/hotspot/share/ci/ciTypeFlow.cpp IDEA additional info: Subsystem: com.intellij.openapi.diff.impl.patch.CharsetEP <+>UTF-8 =================================================================== diff --git a/src/hotspot/share/ci/ciTypeFlow.cpp b/src/hotspot/share/ci/ciTypeFlow.cpp --- a/src/hotspot/share/ci/ciTypeFlow.cpp (revision c2c0cb2a4372d78658326461562363de9a1a194f) +++ b/src/hotspot/share/ci/ciTypeFlow.cpp (revision 9d0bd007c334b9a3a22abe4cb6e252630f35c07b) @@ -1906,7 +1906,8 @@ st->print(" loops:"); Loop* lp = loop(); do { - st->print(" %d<-%d", lp->head()->pre_order(),lp->tail()->pre_order()); + st->print(" %d<-", lp->head()->pre_order()); + lp->print_tails_pre_order(st); if (lp->is_irreducible()) st->print("(ir)"); lp = lp->parent(); } while (lp->parent() != NULL); @@ -2233,16 +2234,7 @@ if (ch != NULL) continue; - // Clone head - Block* new_head = head->looping_succ(lp); - Block* clone = clone_loop_head(lp, temp_vector, temp_set); - // Update lp's info - clone->set_loop(lp); - lp->set_head(new_head); - lp->set_tail(clone); - // And move original head into outer loop - head->set_loop(lp->parent()); - + clone_loop_head(lp, temp_vector, temp_set); rslt = true; } return rslt; @@ -2251,73 +2243,94 @@ // ------------------------------------------------------------------ // ciTypeFlow::clone_loop_head // -// Clone lp's head and replace tail's successors with clone. -// -// | -// v -// head <-> body -// | -// v -// exit +// Clone lp's head and replace the successor of each tail (previously the head) with a single clone of the head. +// The single clone becomes a backedge copy of the head which either return to the new_head or to the loop exit. +// The clone is now the unique tail of the loop. The original loop head is moved into the outer loop. // -// new_head -// -// | -// v -// head ----------\ -// | | -// | v -// | clone <-> body -// | | -// | /--/ -// | | -// v v -// exit +// entry +// \ /-----------\ +// v v | +// /--- head <----\ | +// | | | | +// v v | | +// exit body -> tail 2 | +// | | +// v | +// tail 1 ---------/ +// +// new_head is the first block in the old body after head. // -ciTypeFlow::Block* ciTypeFlow::clone_loop_head(Loop* lp, StateVector* temp_vector, JsrSet* temp_set) { +// entry +// | +// v +// head +// / \ +// / v +// | new_head <----\ +// | / \ | +// | v v | +// | tail 1 tail 2 | +// | \ / | +// | v v | +// exit <-- clone ------/ +// +void ciTypeFlow::clone_loop_head(Loop* lp, StateVector* temp_vector, JsrSet* temp_set) { Block* head = lp->head(); - Block* tail = lp->tail(); if (CITraceTypeFlow) { - tty->print(">> Requesting clone of loop head "); head->print_value_on(tty); - tty->print(" for predecessor "); tail->print_value_on(tty); + tty->print(">> Requesting clone of loop head "); + head->print_value_on(tty); + tty->print(" for predecessor "); + lp->print_tails_pre_order(tty); tty->cr(); } + Block* new_head = head->looping_succ(lp); Block* clone = block_at(head->start(), head->jsrs(), create_backedge_copy); assert(clone->backedge_copy_count() == 1, "one backedge copy for all back edges"); - assert(!clone->has_pre_order(), "just created"); clone->set_next_pre_order(); // Insert clone after (orig) tail in reverse post order - clone->set_rpo_next(tail->rpo_next()); - tail->set_rpo_next(clone); + clone->set_rpo_next(lp->first_tail()->rpo_next()); + lp->first_tail()->set_rpo_next(clone); + + for (int i = 0; i < lp->tails()->length(); i++) { + Block* tail = lp->tails()->at(i); - // tail->head becomes tail->clone - for (SuccIter iter(tail); !iter.done(); iter.next()) { - if (iter.succ() == head) { - iter.set_succ(clone); - // Update predecessor information - head->predecessors()->remove(tail); - clone->predecessors()->append(tail); - } - } - flow_block(tail, temp_vector, temp_set); - if (head == tail) { - // For self-loops, clone->head becomes clone->clone - flow_block(clone, temp_vector, temp_set); - for (SuccIter iter(clone); !iter.done(); iter.next()) { - if (iter.succ() == head) { - iter.set_succ(clone); - // Update predecessor information - head->predecessors()->remove(clone); - clone->predecessors()->append(clone); - break; - } - } - } - flow_block(clone, temp_vector, temp_set); + // tail->head becomes tail->clone + for (SuccIter iter(tail); !iter.done(); iter.next()) { + if (iter.succ() == head) { + iter.set_succ(clone); + // Update predecessor information + head->predecessors()->remove(tail); + clone->predecessors()->append(tail); + } + } + flow_block(tail, temp_vector, temp_set); + if (head == tail) { + // For self-loops, clone->head becomes clone->clone + flow_block(clone, temp_vector, temp_set); + for (SuccIter iter(clone); !iter.done(); iter.next()) { + if (iter.succ() == head) { + iter.set_succ(clone); + // Update predecessor information + head->predecessors()->remove(clone); + clone->predecessors()->append(clone); + break; + } + } + } + flow_block(clone, temp_vector, temp_set); + } - return clone; + clone->set_loop(lp); + // Loop has only one tail now, the new cloned block + lp->clear_tails(); + lp->add_tail(clone); + + // Update lp's info + lp->set_head(new_head); + // And move original head into outer loop + head->set_loop(lp->parent()); } // ------------------------------------------------------------------ @@ -2530,7 +2543,8 @@ int lp_pre_order = lp->head()->pre_order(); if (current->head()->pre_order() < lp_pre_order) { return true; - } else if (current->head()->pre_order() > lp_pre_order) { + } else if (current->head()->pre_order() > lp_pre_order && + current->first_tail()->pre_order() > lp->first_tail()->pre_order()) { return false; } // In the case of a shared head, make the most frequent head/tail (as reported by profiling) the inner loop @@ -2557,7 +2571,7 @@ // Child and sibling pointers will be setup later. // Sort is (looking from leaf towards the root) // descending on primary key: loop head's pre_order, and -// ascending on secondary key: loop tail's pre_order. +// ascending on secondary key: loop first discovered tail's pre_order. ciTypeFlow::Loop* ciTypeFlow::Loop::sorted_merge(Loop* lp) { Loop* leaf = this; Loop* prev = NULL; @@ -2605,9 +2619,13 @@ assert(succ->pre_order() <= blk->pre_order(), "should be backedge"); // Create a LoopNode to mark this loop. - lp = new (arena()) Loop(succ, blk); - if (succ->loop() == NULL) + if (succ->loop() == NULL) { + lp = new(arena()) Loop(arena(), succ, blk); succ->set_loop(lp); + } else { + lp = succ->loop(); + succ->loop()->add_tail(blk); + } // succ->loop will be updated to innermost loop on a later call, when blk==succ } else { // Nested loop @@ -2711,16 +2729,33 @@ // ciTypeFlow::Loop::print void ciTypeFlow::Loop::print(outputStream* st, int indent) const { for (int i = 0; i < indent; i++) st->print(" "); - st->print("%d<-%d %s", - is_root() ? 0 : this->head()->pre_order(), - is_root() ? 0 : this->tail()->pre_order(), - is_irreducible()?" irr":""); + st->print("%d<-", is_root() ? 0 : this->head()->pre_order()); + print_tails_pre_order(st, indent); + st->print(" %s", is_irreducible()?" irr":""); st->print(" defs: "); def_locals()->print_on(st, _head->outer()->method()->max_locals()); st->cr(); for (Loop* ch = child(); ch != NULL; ch = ch->sibling()) ch->print(st, indent+2); } + +void ciTypeFlow::Loop::print_tails_pre_order(outputStream* st, int indent) const { + if (_tails->length() == 1) { + st->print("%d", first_tail()->pre_order()); + } else { + st->print("["); + for (int i = 0; i < _tails->length(); i++) { + st->print("%d", _tails->at(i)->pre_order()); + if (i < _tails->length() - 1) { + st->print(","); + } else { + st->print("]"); + } + } + } +} + + #endif // ------------------------------------------------------------------ @@ -2742,7 +2777,7 @@ root_head->set_post_order(0); root_tail->set_pre_order(max_jint); root_tail->set_post_order(max_jint); - set_loop_tree_root(new (arena()) Loop(root_head, root_tail)); + set_loop_tree_root(new (arena()) Loop(arena(), root_head, root_tail)); stk.push(start); Index: src/hotspot/share/ci/ciTypeFlow.hpp IDEA additional info: Subsystem: com.intellij.openapi.diff.impl.patch.CharsetEP <+>UTF-8 =================================================================== diff --git a/src/hotspot/share/ci/ciTypeFlow.hpp b/src/hotspot/share/ci/ciTypeFlow.hpp --- a/src/hotspot/share/ci/ciTypeFlow.hpp (revision c2c0cb2a4372d78658326461562363de9a1a194f) +++ b/src/hotspot/share/ci/ciTypeFlow.hpp (revision 9d0bd007c334b9a3a22abe4cb6e252630f35c07b) @@ -713,7 +713,7 @@ Loop* _sibling; // List of siblings, null terminated Loop* _child; // Head of child list threaded thru sibling pointer Block* _head; // Head of loop - Block* _tail; // Tail of loop + GrowableArray* _tails; // Possibly multiple tails of the loop bool _irreducible; LocalSet _def_locals; @@ -721,21 +721,30 @@ bool at_insertion_point(Loop* lp, Loop* current); public: - Loop(Block* head, Block* tail) : - _parent(NULL), _sibling(NULL), _child(NULL), - _head(head), _tail(tail), - _irreducible(false), _def_locals() {} + Loop(Arena* arena, Block* head, Block* first_tail) : + _parent(NULL), _sibling(NULL), _child(NULL), + _head(head), _irreducible(false), _def_locals() + { + _tails = new (arena) GrowableArray(arena, 1, 0, NULL); + _tails->push(first_tail); + } Loop* parent() const { return _parent; } Loop* sibling() const { return _sibling; } Loop* child() const { return _child; } Block* head() const { return _head; } - Block* tail() const { return _tail; } + // First discovered tail of the loop that is used for sorting. + Block* first_tail() const { + assert(_tails->length() > 0, "Must have at least one element"); + return _tails->at(0); + } + GrowableArray* tails() const { return _tails; } + void clear_tails() { _tails->clear(); } void set_parent(Loop* p) { _parent = p; } void set_sibling(Loop* s) { _sibling = s; } void set_child(Loop* c) { _child = c; } void set_head(Block* hd) { _head = hd; } - void set_tail(Block* tl) { _tail = tl; } + void add_tail(Block* tl) { _tails->push(tl); } int depth() const; // nesting depth @@ -758,9 +767,10 @@ } bool is_irreducible() const { return _irreducible; } - bool is_root() const { return _tail->pre_order() == max_jint; } + bool is_root() const { return first_tail()->pre_order() == max_jint; } void print(outputStream* st = tty, int indent = 0) const PRODUCT_RETURN; + void print_tails_pre_order(outputStream* st = tty, int indent = 0) const PRODUCT_RETURN; }; // Preorder iteration over the loop tree. @@ -801,7 +811,7 @@ bool clone_loop_heads(StateVector* temp_vector, JsrSet* temp_set); // Clone lp's head and replace tail's successors with clone. - Block* clone_loop_head(Loop* lp, StateVector* temp_vector, JsrSet* temp_set); + void clone_loop_head(Loop* lp, StateVector* temp_vector, JsrSet* temp_set); public: // Return the block beginning at bci which has a JsrSet compatible