# HG changeset patch # User bharadwaj # Date 1354065855 28800 # Node ID 2aff40cb47031bde5ce55a6b6563b040d050d669 # Parent 2cd5e15048e6cbcc33e5a263a0bae888e61f339a 7092905: C2: Keep track of the number of dead nodes Summary: keep an (almost) accurate running count of the reachable (live) flow graph nodes. Reviewed-by: kvn, twisti, jrose, vlivanov diff -r 2cd5e15048e6 -r 2aff40cb4703 src/share/tools/LogCompilation/README --- a/src/share/tools/LogCompilation/README Tue Nov 27 12:48:52 2012 -0800 +++ b/src/share/tools/LogCompilation/README Tue Nov 27 17:24:15 2012 -0800 @@ -13,6 +13,6 @@ More information about the LogCompilation output can be found at -http://wikis.sun.com/display/HotSpotInternals/LogCompilation+overview -http://wikis.sun.com/display/HotSpotInternals/PrintCompilation -http://wikis.sun.com/display/HotSpotInternals/LogCompilation+tool +https://wikis.oracle.com/display/HotSpotInternals/LogCompilation+overview +https://wikis.oracle.com/display/HotSpotInternals/PrintCompilation +https://wikis.oracle.com/display/HotSpotInternals/LogCompilation+tool diff -r 2cd5e15048e6 -r 2aff40cb4703 src/share/tools/LogCompilation/src/com/sun/hotspot/tools/compiler/CallSite.java --- a/src/share/tools/LogCompilation/src/com/sun/hotspot/tools/compiler/CallSite.java Tue Nov 27 12:48:52 2012 -0800 +++ b/src/share/tools/LogCompilation/src/com/sun/hotspot/tools/compiler/CallSite.java Tue Nov 27 17:24:15 2012 -0800 @@ -38,6 +38,7 @@ private String reason; private List calls; private int endNodes; + private int endLiveNodes; private double timeStamp; CallSite() { @@ -106,7 +107,7 @@ } } if (getEndNodes() > 0) { - stream.printf(" (end time: %6.4f nodes: %d)", getTimeStamp(), getEndNodes()); + stream.printf(" (end time: %6.4f nodes: %d live: %d)", getTimeStamp(), getEndNodes(), getEndLiveNodes()); } stream.println(""); if (getReceiver() != null) { @@ -195,6 +196,14 @@ return endNodes; } + void setEndLiveNodes(int n) { + endLiveNodes = n; + } + + public int getEndLiveNodes() { + return endLiveNodes; + } + void setTimeStamp(double time) { timeStamp = time; } diff -r 2cd5e15048e6 -r 2aff40cb4703 src/share/tools/LogCompilation/src/com/sun/hotspot/tools/compiler/LogCompilation.java --- a/src/share/tools/LogCompilation/src/com/sun/hotspot/tools/compiler/LogCompilation.java Tue Nov 27 12:48:52 2012 -0800 +++ b/src/share/tools/LogCompilation/src/com/sun/hotspot/tools/compiler/LogCompilation.java Tue Nov 27 17:24:15 2012 -0800 @@ -43,7 +43,7 @@ System.out.println(" -S: print compilation statistics"); System.out.println(" -s: sort events by start time"); System.out.println(" -e: sort events by elapsed time"); - System.out.println(" -N: sort events by name and start"); + System.out.println(" -n: sort events by name and start"); System.exit(exitcode); } @@ -137,7 +137,11 @@ v2 = Integer.valueOf(0); } phaseNodes.put(phase.getName(), Integer.valueOf(v2.intValue() + phase.getNodes())); - out.printf("\t%s %6.4f %d %d\n", phase.getName(), phase.getElapsedTime(), phase.getStartNodes(), phase.getNodes()); + /* Print phase name, elapsed time, nodes at the start of the phase, + nodes created in the phase, live nodes at the start of the phase, + live nodes added in the phase. + */ + out.printf("\t%s %6.4f %d %d %d %d\n", phase.getName(), phase.getElapsedTime(), phase.getStartNodes(), phase.getNodes(), phase.getStartLiveNodes(), phase.getLiveNodes()); } } else if (e instanceof MakeNotEntrantEvent) { MakeNotEntrantEvent mne = (MakeNotEntrantEvent) e; diff -r 2cd5e15048e6 -r 2aff40cb4703 src/share/tools/LogCompilation/src/com/sun/hotspot/tools/compiler/LogParser.java --- a/src/share/tools/LogCompilation/src/com/sun/hotspot/tools/compiler/LogParser.java Tue Nov 27 12:48:52 2012 -0800 +++ b/src/share/tools/LogCompilation/src/com/sun/hotspot/tools/compiler/LogParser.java Tue Nov 27 17:24:15 2012 -0800 @@ -268,12 +268,18 @@ if (qname.equals("phase")) { Phase p = new Phase(search(atts, "name"), Double.parseDouble(search(atts, "stamp")), - Integer.parseInt(search(atts, "nodes"))); + Integer.parseInt(search(atts, "nodes")), + Integer.parseInt(search(atts, "live"))); phaseStack.push(p); } else if (qname.equals("phase_done")) { Phase p = phaseStack.pop(); + if (! p.getId().equals(search(atts, "name"))) { + System.out.println("phase: " + p.getId()); + throw new InternalError("phase name mismatch"); + } + p.setEnd(Double.parseDouble(search(atts, "stamp"))); p.setEndNodes(Integer.parseInt(search(atts, "nodes"))); - p.setEnd(Double.parseDouble(search(atts, "stamp"))); + p.setEndLiveNodes(Integer.parseInt(search(atts, "live"))); compile.getPhases().add(p); } else if (qname.equals("task")) { compile = new Compilation(Integer.parseInt(search(atts, "compile_id", "-1"))); @@ -406,6 +412,7 @@ } else if (qname.equals("parse_done")) { CallSite call = scopes.pop(); call.setEndNodes(Integer.parseInt(search(atts, "nodes", "1"))); + call.setEndLiveNodes(Integer.parseInt(search(atts, "live", "1"))); call.setTimeStamp(Double.parseDouble(search(atts, "stamp"))); scopes.push(call); } diff -r 2cd5e15048e6 -r 2aff40cb4703 src/share/tools/LogCompilation/src/com/sun/hotspot/tools/compiler/Phase.java --- a/src/share/tools/LogCompilation/src/com/sun/hotspot/tools/compiler/Phase.java Tue Nov 27 12:48:52 2012 -0800 +++ b/src/share/tools/LogCompilation/src/com/sun/hotspot/tools/compiler/Phase.java Tue Nov 27 17:24:15 2012 -0800 @@ -30,10 +30,13 @@ private final int startNodes; private int endNodes; + private final int startLiveNodes; + private int endLiveNodes; - Phase(String n, double s, int nodes) { + Phase(String n, double s, int nodes, int live) { super(s, n); startNodes = nodes; + startLiveNodes = live; } int getNodes() { @@ -55,6 +58,22 @@ public int getEndNodes() { return endNodes; } + /* Number of live nodes added by the phase */ + int getLiveNodes() { + return getEndLiveNodes() - getStartLiveNodes(); + } + + void setEndLiveNodes(int n) { + endLiveNodes = n; + } + + public int getStartLiveNodes() { + return startLiveNodes; + } + + public int getEndLiveNodes() { + return endLiveNodes; + } @Override public void print(PrintStream stream) { diff -r 2cd5e15048e6 -r 2aff40cb4703 src/share/vm/opto/block.hpp --- a/src/share/vm/opto/block.hpp Tue Nov 27 12:48:52 2012 -0800 +++ b/src/share/vm/opto/block.hpp Tue Nov 27 17:24:15 2012 -0800 @@ -292,7 +292,7 @@ void needed_for_next_call(Node *this_call, VectorSet &next_call, Block_Array &bbs); bool schedule_local(PhaseCFG *cfg, Matcher &m, GrowableArray &ready_cnt, VectorSet &next_call); // Cleanup if any code lands between a Call and his Catch - void call_catch_cleanup(Block_Array &bbs); + void call_catch_cleanup(Block_Array &bbs, Compile *C); // Detect implicit-null-check opportunities. Basically, find NULL checks // with suitable memory ops nearby. Use the memory op to do the NULL check. // I can generate a memory op if there is not one nearby. diff -r 2cd5e15048e6 -r 2aff40cb4703 src/share/vm/opto/c2_globals.hpp --- a/src/share/vm/opto/c2_globals.hpp Tue Nov 27 12:48:52 2012 -0800 +++ b/src/share/vm/opto/c2_globals.hpp Tue Nov 27 17:24:15 2012 -0800 @@ -115,6 +115,12 @@ notproduct(bool, VerifyOpto, false, \ "Apply more time consuming verification during compilation") \ \ + notproduct(bool, VerifyIdealNodeCount, false, \ + "Verify that tracked dead ideal node count is accurate") \ + \ + notproduct(bool, PrintIdealNodeCount, false, \ + "Print liveness counts of ideal nodes") \ + \ notproduct(bool, VerifyOptoOopOffsets, false, \ "Check types of base addresses in field references") \ \ diff -r 2cd5e15048e6 -r 2aff40cb4703 src/share/vm/opto/chaitin.cpp --- a/src/share/vm/opto/chaitin.cpp Tue Nov 27 12:48:52 2012 -0800 +++ b/src/share/vm/opto/chaitin.cpp Tue Nov 27 17:24:15 2012 -0800 @@ -1495,7 +1495,7 @@ cisc->ins_req(1,src); // Requires a memory edge } b->_nodes.map(j,cisc); // Insert into basic block - n->subsume_by(cisc); // Correct graph + n->subsume_by(cisc, C); // Correct graph // ++_used_cisc_instructions; #ifndef PRODUCT diff -r 2cd5e15048e6 -r 2aff40cb4703 src/share/vm/opto/compile.cpp --- a/src/share/vm/opto/compile.cpp Tue Nov 27 12:48:52 2012 -0800 +++ b/src/share/vm/opto/compile.cpp Tue Nov 27 17:24:15 2012 -0800 @@ -316,7 +316,12 @@ } - +static inline bool not_a_node(const Node* n) { + if (n == NULL) return true; + if (((intptr_t)n & 1) != 0) return true; // uninitialized, etc. + if (*(address*)n == badAddress) return true; // kill by Node::destruct + return false; +} // Identify all nodes that are reachable from below, useful. // Use breadth-first pass that records state in a Unique_Node_List, @@ -337,12 +342,27 @@ uint max = n->len(); for( uint i = 0; i < max; ++i ) { Node *m = n->in(i); - if( m == NULL ) continue; + if (not_a_node(m)) continue; useful.push(m); } } } +// Update dead_node_list with any missing dead nodes using useful +// list. Consider all non-useful nodes to be useless i.e., dead nodes. +void Compile::update_dead_node_list(Unique_Node_List &useful) { + uint max_idx = unique(); + VectorSet& useful_node_set = useful.member_set(); + + for (uint node_idx = 0; node_idx < max_idx; node_idx++) { + // If node with index node_idx is not in useful set, + // mark it as dead in dead node list. + if (! useful_node_set.test(node_idx) ) { + record_dead_node(node_idx); + } + } +} + // Disconnect all useless nodes by disconnecting those at the boundary. void Compile::remove_useless_nodes(Unique_Node_List &useful) { uint next = 0; @@ -582,6 +602,8 @@ _inner_loops(0), _scratch_const_size(-1), _in_scratch_emit_size(false), + _dead_node_list(comp_arena()), + _dead_node_count(0), #ifndef PRODUCT _trace_opto_output(TraceOptoOutput || method()->has_option("TraceOptoOutput")), _printer(IdealGraphPrinter::printer()), @@ -873,6 +895,8 @@ _trace_opto_output(TraceOptoOutput), _printer(NULL), #endif + _dead_node_list(comp_arena()), + _dead_node_count(0), _congraph(NULL) { C = this; @@ -1069,6 +1093,72 @@ assert(_top == NULL || top()->is_top(), ""); } +#ifdef ASSERT +uint Compile::count_live_nodes_by_graph_walk() { + Unique_Node_List useful(comp_arena()); + // Get useful node list by walking the graph. + identify_useful_nodes(useful); + return useful.size(); +} + +void Compile::print_missing_nodes() { + + // Return if CompileLog is NULL and PrintIdealNodeCount is false. + if ((_log == NULL) && (! PrintIdealNodeCount)) { + return; + } + + // This is an expensive function. It is executed only when the user + // specifies VerifyIdealNodeCount option or otherwise knows the + // additional work that needs to be done to identify reachable nodes + // by walking the flow graph and find the missing ones using + // _dead_node_list. + + Unique_Node_List useful(comp_arena()); + // Get useful node list by walking the graph. + identify_useful_nodes(useful); + + uint l_nodes = C->live_nodes(); + uint l_nodes_by_walk = useful.size(); + + if (l_nodes != l_nodes_by_walk) { + if (_log != NULL) { + _log->begin_head("mismatched_nodes count='%d'", abs((int) (l_nodes - l_nodes_by_walk))); + _log->stamp(); + _log->end_head(); + } + VectorSet& useful_member_set = useful.member_set(); + int last_idx = l_nodes_by_walk; + for (int i = 0; i < last_idx; i++) { + if (useful_member_set.test(i)) { + if (_dead_node_list.test(i)) { + if (_log != NULL) { + _log->elem("mismatched_node_info node_idx='%d' type='both live and dead'", i); + } + if (PrintIdealNodeCount) { + // Print the log message to tty + tty->print_cr("mismatched_node idx='%d' both live and dead'", i); + useful.at(i)->dump(); + } + } + } + else if (! _dead_node_list.test(i)) { + if (_log != NULL) { + _log->elem("mismatched_node_info node_idx='%d' type='neither live nor dead'", i); + } + if (PrintIdealNodeCount) { + // Print the log message to tty + tty->print_cr("mismatched_node idx='%d' type='neither live nor dead'", i); + } + } + } + if (_log != NULL) { + _log->tail("mismatched_nodes"); + } + } +} +#endif + #ifndef PRODUCT void Compile::verify_top(Node* tn) const { if (tn != NULL) { @@ -2087,7 +2177,7 @@ // Eliminate trivially redundant StoreCMs and accumulate their // precedence edges. -static void eliminate_redundant_card_marks(Node* n) { +void Compile::eliminate_redundant_card_marks(Node* n) { assert(n->Opcode() == Op_StoreCM, "expected StoreCM"); if (n->in(MemNode::Address)->outcnt() > 1) { // There are multiple users of the same address so it might be @@ -2122,7 +2212,7 @@ // Eliminate the previous StoreCM prev->set_req(MemNode::Memory, mem->in(MemNode::Memory)); assert(mem->outcnt() == 0, "should be dead"); - mem->disconnect_inputs(NULL); + mem->disconnect_inputs(NULL, this); } else { prev = mem; } @@ -2133,7 +2223,7 @@ //------------------------------final_graph_reshaping_impl---------------------- // Implement items 1-5 from final_graph_reshaping below. -static void final_graph_reshaping_impl( Node *n, Final_Reshape_Counts &frc ) { +void Compile::final_graph_reshaping_impl( Node *n, Final_Reshape_Counts &frc) { if ( n->outcnt() == 0 ) return; // dead node uint nop = n->Opcode(); @@ -2163,8 +2253,7 @@ #ifdef ASSERT if( n->is_Mem() ) { - Compile* C = Compile::current(); - int alias_idx = C->get_alias_index(n->as_Mem()->adr_type()); + int alias_idx = get_alias_index(n->as_Mem()->adr_type()); assert( n->in(0) != NULL || alias_idx != Compile::AliasIdxRaw || // oop will be recorded in oop map if load crosses safepoint n->is_Load() && (n->as_Load()->bottom_type()->isa_oopptr() || @@ -2213,7 +2302,7 @@ break; case Op_Opaque1: // Remove Opaque Nodes before matching case Op_Opaque2: // Remove Opaque Nodes before matching - n->subsume_by(n->in(1)); + n->subsume_by(n->in(1), this); break; case Op_CallStaticJava: case Op_CallJava: @@ -2337,8 +2426,7 @@ int op = t->isa_oopptr() ? Op_ConN : Op_ConNKlass; // Look for existing ConN node of the same exact type. - Compile* C = Compile::current(); - Node* r = C->root(); + Node* r = root(); uint cnt = r->outcnt(); for (uint i = 0; i < cnt; i++) { Node* m = r->raw_out(i); @@ -2352,14 +2440,14 @@ // Decode a narrow oop to match address // [R12 + narrow_oop_reg<<3 + offset] if (t->isa_oopptr()) { - nn = new (C) DecodeNNode(nn, t); + nn = new (this) DecodeNNode(nn, t); } else { - nn = new (C) DecodeNKlassNode(nn, t); + nn = new (this) DecodeNKlassNode(nn, t); } n->set_req(AddPNode::Base, nn); n->set_req(AddPNode::Address, nn); if (addp->outcnt() == 0) { - addp->disconnect_inputs(NULL); + addp->disconnect_inputs(NULL, this); } } } @@ -2371,7 +2459,6 @@ #ifdef _LP64 case Op_CastPP: if (n->in(1)->is_DecodeN() && Matcher::gen_narrow_oop_implicit_null_checks()) { - Compile* C = Compile::current(); Node* in1 = n->in(1); const Type* t = n->bottom_type(); Node* new_in1 = in1->clone(); @@ -2400,9 +2487,9 @@ new_in1->set_req(0, n->in(0)); } - n->subsume_by(new_in1); + n->subsume_by(new_in1, this); if (in1->outcnt() == 0) { - in1->disconnect_inputs(NULL); + in1->disconnect_inputs(NULL, this); } } break; @@ -2419,7 +2506,6 @@ } assert(in1->is_DecodeNarrowPtr(), "sanity"); - Compile* C = Compile::current(); Node* new_in2 = NULL; if (in2->is_DecodeNarrowPtr()) { assert(in2->Opcode() == in1->Opcode(), "must be same node type"); @@ -2432,7 +2518,7 @@ // oops implicit null check is not generated. // This will allow to generate normal oop implicit null check. if (Matcher::gen_narrow_oop_implicit_null_checks()) - new_in2 = ConNode::make(C, TypeNarrowOop::NULL_PTR); + new_in2 = ConNode::make(this, TypeNarrowOop::NULL_PTR); // // This transformation together with CastPP transformation above // will generated code for implicit NULL checks for compressed oops. @@ -2471,19 +2557,19 @@ // NullCheck base_reg // } else if (t->isa_oopptr()) { - new_in2 = ConNode::make(C, t->make_narrowoop()); + new_in2 = ConNode::make(this, t->make_narrowoop()); } else if (t->isa_klassptr()) { - new_in2 = ConNode::make(C, t->make_narrowklass()); + new_in2 = ConNode::make(this, t->make_narrowklass()); } } if (new_in2 != NULL) { - Node* cmpN = new (C) CmpNNode(in1->in(1), new_in2); - n->subsume_by( cmpN ); + Node* cmpN = new (this) CmpNNode(in1->in(1), new_in2); + n->subsume_by(cmpN, this); if (in1->outcnt() == 0) { - in1->disconnect_inputs(NULL); + in1->disconnect_inputs(NULL, this); } if (in2->outcnt() == 0) { - in2->disconnect_inputs(NULL); + in2->disconnect_inputs(NULL, this); } } } @@ -2501,21 +2587,20 @@ case Op_EncodePKlass: { Node* in1 = n->in(1); if (in1->is_DecodeNarrowPtr()) { - n->subsume_by(in1->in(1)); + n->subsume_by(in1->in(1), this); } else if (in1->Opcode() == Op_ConP) { - Compile* C = Compile::current(); const Type* t = in1->bottom_type(); if (t == TypePtr::NULL_PTR) { assert(t->isa_oopptr(), "null klass?"); - n->subsume_by(ConNode::make(C, TypeNarrowOop::NULL_PTR)); + n->subsume_by(ConNode::make(this, TypeNarrowOop::NULL_PTR), this); } else if (t->isa_oopptr()) { - n->subsume_by(ConNode::make(C, t->make_narrowoop())); + n->subsume_by(ConNode::make(this, t->make_narrowoop()), this); } else if (t->isa_klassptr()) { - n->subsume_by(ConNode::make(C, t->make_narrowklass())); + n->subsume_by(ConNode::make(this, t->make_narrowklass()), this); } } if (in1->outcnt() == 0) { - in1->disconnect_inputs(NULL); + in1->disconnect_inputs(NULL, this); } break; } @@ -2538,7 +2623,7 @@ } } assert(proj != NULL, "must be found"); - p->subsume_by(proj); + p->subsume_by(proj, this); } } break; @@ -2558,7 +2643,7 @@ unique_in = NULL; } if (unique_in != NULL) { - n->subsume_by(unique_in); + n->subsume_by(unique_in, this); } } break; @@ -2571,16 +2656,15 @@ Node* d = n->find_similar(Op_DivI); if (d) { // Replace them with a fused divmod if supported - Compile* C = Compile::current(); if (Matcher::has_match_rule(Op_DivModI)) { - DivModINode* divmod = DivModINode::make(C, n); - d->subsume_by(divmod->div_proj()); - n->subsume_by(divmod->mod_proj()); + DivModINode* divmod = DivModINode::make(this, n); + d->subsume_by(divmod->div_proj(), this); + n->subsume_by(divmod->mod_proj(), this); } else { // replace a%b with a-((a/b)*b) - Node* mult = new (C) MulINode(d, d->in(2)); - Node* sub = new (C) SubINode(d->in(1), mult); - n->subsume_by( sub ); + Node* mult = new (this) MulINode(d, d->in(2)); + Node* sub = new (this) SubINode(d->in(1), mult); + n->subsume_by(sub, this); } } } @@ -2592,16 +2676,15 @@ Node* d = n->find_similar(Op_DivL); if (d) { // Replace them with a fused divmod if supported - Compile* C = Compile::current(); if (Matcher::has_match_rule(Op_DivModL)) { - DivModLNode* divmod = DivModLNode::make(C, n); - d->subsume_by(divmod->div_proj()); - n->subsume_by(divmod->mod_proj()); + DivModLNode* divmod = DivModLNode::make(this, n); + d->subsume_by(divmod->div_proj(), this); + n->subsume_by(divmod->mod_proj(), this); } else { // replace a%b with a-((a/b)*b) - Node* mult = new (C) MulLNode(d, d->in(2)); - Node* sub = new (C) SubLNode(d->in(1), mult); - n->subsume_by( sub ); + Node* mult = new (this) MulLNode(d, d->in(2)); + Node* sub = new (this) SubLNode(d->in(1), mult); + n->subsume_by(sub, this); } } } @@ -2620,8 +2703,8 @@ if (n->req()-1 > 2) { // Replace many operand PackNodes with a binary tree for matching PackNode* p = (PackNode*) n; - Node* btp = p->binary_tree_pack(Compile::current(), 1, n->req()); - n->subsume_by(btp); + Node* btp = p->binary_tree_pack(this, 1, n->req()); + n->subsume_by(btp, this); } break; case Op_Loop: @@ -2645,18 +2728,16 @@ if (t != NULL && t->is_con()) { juint shift = t->get_con(); if (shift > mask) { // Unsigned cmp - Compile* C = Compile::current(); - n->set_req(2, ConNode::make(C, TypeInt::make(shift & mask))); + n->set_req(2, ConNode::make(this, TypeInt::make(shift & mask))); } } else { if (t == NULL || t->_lo < 0 || t->_hi > (int)mask) { - Compile* C = Compile::current(); - Node* shift = new (C) AndINode(in2, ConNode::make(C, TypeInt::make(mask))); + Node* shift = new (this) AndINode(in2, ConNode::make(this, TypeInt::make(mask))); n->set_req(2, shift); } } if (in2->outcnt() == 0) { // Remove dead node - in2->disconnect_inputs(NULL); + in2->disconnect_inputs(NULL, this); } } break; @@ -2674,7 +2755,7 @@ //------------------------------final_graph_reshaping_walk--------------------- // Replacing Opaque nodes with their input in final_graph_reshaping_impl(), // requires that the walk visits a node's inputs before visiting the node. -static void final_graph_reshaping_walk( Node_Stack &nstack, Node *root, Final_Reshape_Counts &frc ) { +void Compile::final_graph_reshaping_walk( Node_Stack &nstack, Node *root, Final_Reshape_Counts &frc ) { ResourceArea *area = Thread::current()->resource_area(); Unique_Node_List sfpt(area); @@ -2741,7 +2822,7 @@ n->set_req(j, in->in(1)); } if (in->outcnt() == 0) { - in->disconnect_inputs(NULL); + in->disconnect_inputs(NULL, this); } } } @@ -3014,7 +3095,8 @@ } Compile::TracePhase::TracePhase(const char* name, elapsedTimer* accumulator, bool dolog) - : TraceTime(NULL, accumulator, false NOT_PRODUCT( || TimeCompiler ), false) + : TraceTime(NULL, accumulator, false NOT_PRODUCT( || TimeCompiler ), false), + _phase_name(name), _dolog(dolog) { if (dolog) { C = Compile::current(); @@ -3024,15 +3106,34 @@ _log = NULL; } if (_log != NULL) { - _log->begin_head("phase name='%s' nodes='%d'", name, C->unique()); + _log->begin_head("phase name='%s' nodes='%d' live='%d'", _phase_name, C->unique(), C->live_nodes()); _log->stamp(); _log->end_head(); } } Compile::TracePhase::~TracePhase() { + + C = Compile::current(); + if (_dolog) { + _log = C->log(); + } else { + _log = NULL; + } + +#ifdef ASSERT + if (PrintIdealNodeCount) { + tty->print_cr("phase name='%s' nodes='%d' live='%d' live_graph_walk='%d'", + _phase_name, C->unique(), C->live_nodes(), C->count_live_nodes_by_graph_walk()); + } + + if (VerifyIdealNodeCount) { + Compile::current()->print_missing_nodes(); + } +#endif + if (_log != NULL) { - _log->done("phase nodes='%d'", C->unique()); + _log->done("phase name='%s' nodes='%d' live='%d'", _phase_name, C->unique(), C->live_nodes()); } } diff -r 2cd5e15048e6 -r 2aff40cb4703 src/share/vm/opto/compile.hpp --- a/src/share/vm/opto/compile.hpp Tue Nov 27 12:48:52 2012 -0800 +++ b/src/share/vm/opto/compile.hpp Tue Nov 27 17:24:15 2012 -0800 @@ -75,6 +75,8 @@ class Unique_Node_List; class nmethod; class WarmCallInfo; +class Node_Stack; +struct Final_Reshape_Counts; //------------------------------Compile---------------------------------------- // This class defines a top-level Compiler invocation. @@ -98,6 +100,8 @@ private: Compile* C; CompileLog* _log; + const char* _phase_name; + bool _dolog; public: TracePhase(const char* name, elapsedTimer* accumulator, bool dolog); ~TracePhase(); @@ -313,6 +317,9 @@ // Node management uint _unique; // Counter for unique Node indices + VectorSet _dead_node_list; // Set of dead nodes + uint _dead_node_count; // Number of dead nodes; VectorSet::Size() is O(N). + // So use this to keep count and make the call O(1). debug_only(static int _debug_idx;) // Monotonic counter (not reset), use -XX:BreakAtNode= Arena _node_arena; // Arena for new-space Nodes Arena _old_arena; // Arena for old-space Nodes, lifetime during xform @@ -534,7 +541,7 @@ ciEnv* env() const { return _env; } CompileLog* log() const { return _log; } bool failing() const { return _env->failing() || _failure_reason != NULL; } - const char* failure_reason() { return _failure_reason; } + const char* failure_reason() { return _failure_reason; } bool failure_reason_is(const char* r) { return (r==_failure_reason) || (r!=NULL && _failure_reason!=NULL && strcmp(r, _failure_reason)==0); } void record_failure(const char* reason); @@ -549,7 +556,7 @@ record_method_not_compilable(reason, true); } bool check_node_count(uint margin, const char* reason) { - if (unique() + margin > (uint)MaxNodeLimit) { + if (live_nodes() + margin > (uint)MaxNodeLimit) { record_method_not_compilable(reason); return true; } else { @@ -558,25 +565,41 @@ } // Node management - uint unique() const { return _unique; } - uint next_unique() { return _unique++; } - void set_unique(uint i) { _unique = i; } - static int debug_idx() { return debug_only(_debug_idx)+0; } - static void set_debug_idx(int i) { debug_only(_debug_idx = i); } - Arena* node_arena() { return &_node_arena; } - Arena* old_arena() { return &_old_arena; } - RootNode* root() const { return _root; } - void set_root(RootNode* r) { _root = r; } - StartNode* start() const; // (Derived from root.) + uint unique() const { return _unique; } + uint next_unique() { return _unique++; } + void set_unique(uint i) { _unique = i; } + static int debug_idx() { return debug_only(_debug_idx)+0; } + static void set_debug_idx(int i) { debug_only(_debug_idx = i); } + Arena* node_arena() { return &_node_arena; } + Arena* old_arena() { return &_old_arena; } + RootNode* root() const { return _root; } + void set_root(RootNode* r) { _root = r; } + StartNode* start() const; // (Derived from root.) void init_start(StartNode* s); - Node* immutable_memory(); + Node* immutable_memory(); - Node* recent_alloc_ctl() const { return _recent_alloc_ctl; } - Node* recent_alloc_obj() const { return _recent_alloc_obj; } - void set_recent_alloc(Node* ctl, Node* obj) { + Node* recent_alloc_ctl() const { return _recent_alloc_ctl; } + Node* recent_alloc_obj() const { return _recent_alloc_obj; } + void set_recent_alloc(Node* ctl, Node* obj) { _recent_alloc_ctl = ctl; _recent_alloc_obj = obj; - } + } + void record_dead_node(uint idx) { if (_dead_node_list.test_set(idx)) return; + _dead_node_count++; + } + uint dead_node_count() { return _dead_node_count; } + void reset_dead_node_list() { _dead_node_list.Reset(); + _dead_node_count = 0; + } + uint live_nodes() { + int val = _unique - _dead_node_count; + assert (val >= 0, err_msg_res("number of tracked dead nodes %d more than created nodes %d", _unique, _dead_node_count)); + return (uint) val; + } +#ifdef ASSERT + uint count_live_nodes_by_graph_walk(); + void print_missing_nodes(); +#endif // Constant table ConstantTable& constant_table() { return _constant_table; } @@ -678,6 +701,7 @@ void identify_useful_nodes(Unique_Node_List &useful); + void update_dead_node_list(Unique_Node_List &useful); void remove_useless_nodes (Unique_Node_List &useful); WarmCallInfo* warm_calls() const { return _warm_calls; } @@ -892,6 +916,11 @@ static juint _intrinsic_hist_count[vmIntrinsics::ID_LIMIT]; static jubyte _intrinsic_hist_flags[vmIntrinsics::ID_LIMIT]; #endif + // Function calls made by the public function final_graph_reshaping. + // No need to be made public as they are not called elsewhere. + void final_graph_reshaping_impl( Node *n, Final_Reshape_Counts &frc); + void final_graph_reshaping_walk( Node_Stack &nstack, Node *root, Final_Reshape_Counts &frc ); + void eliminate_redundant_card_marks(Node* n); public: diff -r 2cd5e15048e6 -r 2aff40cb4703 src/share/vm/opto/escape.cpp --- a/src/share/vm/opto/escape.cpp Tue Nov 27 12:48:52 2012 -0800 +++ b/src/share/vm/opto/escape.cpp Tue Nov 27 17:24:15 2012 -0800 @@ -2320,7 +2320,7 @@ } } } - if ((int)C->unique() + 2*NodeLimitFudgeFactor > MaxNodeLimit) { + if ((int) (C->live_nodes() + 2*NodeLimitFudgeFactor) > MaxNodeLimit) { if (C->do_escape_analysis() == true && !C->failing()) { // Retry compilation without escape analysis. // If this is the first failure, the sentinel string will "stick" diff -r 2cd5e15048e6 -r 2aff40cb4703 src/share/vm/opto/gcm.cpp --- a/src/share/vm/opto/gcm.cpp Tue Nov 27 12:48:52 2012 -0800 +++ b/src/share/vm/opto/gcm.cpp Tue Nov 27 17:24:15 2012 -0800 @@ -1359,7 +1359,7 @@ // If we inserted any instructions between a Call and his CatchNode, // clone the instructions on all paths below the Catch. for( i=0; i < _num_blocks; i++ ) - _blocks[i]->call_catch_cleanup(_bbs); + _blocks[i]->call_catch_cleanup(_bbs, C); #ifndef PRODUCT if (trace_opto_pipelining()) { diff -r 2cd5e15048e6 -r 2aff40cb4703 src/share/vm/opto/graphKit.cpp --- a/src/share/vm/opto/graphKit.cpp Tue Nov 27 12:48:52 2012 -0800 +++ b/src/share/vm/opto/graphKit.cpp Tue Nov 27 17:24:15 2012 -0800 @@ -153,7 +153,7 @@ void GraphKit::stop_and_kill_map() { SafePointNode* dead_map = stop(); if (dead_map != NULL) { - dead_map->disconnect_inputs(NULL); // Mark the map as killed. + dead_map->disconnect_inputs(NULL, C); // Mark the map as killed. assert(dead_map->is_killed(), "must be so marked"); } } @@ -1811,7 +1811,7 @@ } // Disconnect the call from the graph - call->disconnect_inputs(NULL); + call->disconnect_inputs(NULL, C); C->gvn_replace_by(call, C->top()); // Clean up any MergeMems that feed other MergeMems since the diff -r 2cd5e15048e6 -r 2aff40cb4703 src/share/vm/opto/ifg.cpp --- a/src/share/vm/opto/ifg.cpp Tue Nov 27 12:48:52 2012 -0800 +++ b/src/share/vm/opto/ifg.cpp Tue Nov 27 17:24:15 2012 -0800 @@ -573,7 +573,7 @@ (n2lidx(def) && !liveout.member(n2lidx(def)) ) ) { b->_nodes.remove(j - 1); if( lrgs(r)._def == n ) lrgs(r)._def = 0; - n->disconnect_inputs(NULL); + n->disconnect_inputs(NULL, C); _cfg._bbs.map(n->_idx,NULL); n->replace_by(C->top()); // Since yanking a Node from block, high pressure moves up one diff -r 2cd5e15048e6 -r 2aff40cb4703 src/share/vm/opto/lcm.cpp --- a/src/share/vm/opto/lcm.cpp Tue Nov 27 12:48:52 2012 -0800 +++ b/src/share/vm/opto/lcm.cpp Tue Nov 27 17:24:15 2012 -0800 @@ -1006,7 +1006,7 @@ //------------------------------call_catch_cleanup----------------------------- // If we inserted any instructions between a Call and his CatchNode, // clone the instructions on all paths below the Catch. -void Block::call_catch_cleanup(Block_Array &bbs) { +void Block::call_catch_cleanup(Block_Array &bbs, Compile* C) { // End of region to clone uint end = end_idx(); @@ -1068,7 +1068,7 @@ // Remove the now-dead cloned ops for(uint i3 = beg; i3 < end; i3++ ) { - _nodes[beg]->disconnect_inputs(NULL); + _nodes[beg]->disconnect_inputs(NULL, C); _nodes.remove(beg); } @@ -1081,7 +1081,7 @@ Node *n = sb->_nodes[j]; if (n->outcnt() == 0 && (!n->is_Proj() || n->as_Proj()->in(0)->outcnt() == 1) ){ - n->disconnect_inputs(NULL); + n->disconnect_inputs(NULL, C); sb->_nodes.remove(j); new_cnt--; } diff -r 2cd5e15048e6 -r 2aff40cb4703 src/share/vm/opto/loopTransform.cpp --- a/src/share/vm/opto/loopTransform.cpp Tue Nov 27 12:48:52 2012 -0800 +++ b/src/share/vm/opto/loopTransform.cpp Tue Nov 27 17:24:15 2012 -0800 @@ -269,10 +269,10 @@ bool IdealLoopTree::policy_peeling( PhaseIdealLoop *phase ) const { Node *test = ((IdealLoopTree*)this)->tail(); int body_size = ((IdealLoopTree*)this)->_body.size(); - int uniq = phase->C->unique(); + int live_node_count = phase->C->live_nodes(); // Peeling does loop cloning which can result in O(N^2) node construction if( body_size > 255 /* Prevent overflow for large body_size */ - || (body_size * body_size + uniq > MaxNodeLimit) ) { + || (body_size * body_size + live_node_count > MaxNodeLimit) ) { return false; // too large to safely clone } while( test != _head ) { // Scan till run off top of loop @@ -601,7 +601,7 @@ return false; if (new_body_size > unroll_limit || // Unrolling can result in a large amount of node construction - new_body_size >= MaxNodeLimit - phase->C->unique()) { + new_body_size >= MaxNodeLimit - (uint) phase->C->live_nodes()) { return false; } @@ -2268,7 +2268,7 @@ // Skip next optimizations if running low on nodes. Note that // policy_unswitching and policy_maximally_unroll have this check. - uint nodes_left = MaxNodeLimit - phase->C->unique(); + uint nodes_left = MaxNodeLimit - (uint) phase->C->live_nodes(); if ((2 * _body.size()) > nodes_left) { return true; } diff -r 2cd5e15048e6 -r 2aff40cb4703 src/share/vm/opto/loopUnswitch.cpp --- a/src/share/vm/opto/loopUnswitch.cpp Tue Nov 27 12:48:52 2012 -0800 +++ b/src/share/vm/opto/loopUnswitch.cpp Tue Nov 27 17:24:15 2012 -0800 @@ -59,7 +59,7 @@ if (!_head->is_Loop()) { return false; } - uint nodes_left = MaxNodeLimit - phase->C->unique(); + uint nodes_left = MaxNodeLimit - phase->C->live_nodes(); if (2 * _body.size() > nodes_left) { return false; // Too speculative if running low on nodes. } diff -r 2cd5e15048e6 -r 2aff40cb4703 src/share/vm/opto/loopopts.cpp --- a/src/share/vm/opto/loopopts.cpp Tue Nov 27 12:48:52 2012 -0800 +++ b/src/share/vm/opto/loopopts.cpp Tue Nov 27 17:24:15 2012 -0800 @@ -729,7 +729,7 @@ for (DUIterator_Fast imax, i = region->fast_outs(imax); i < imax; i++) { weight += region->fast_out(i)->outcnt(); } - int nodes_left = MaxNodeLimit - C->unique(); + int nodes_left = MaxNodeLimit - C->live_nodes(); if (weight * 8 > nodes_left) { #ifndef PRODUCT if (PrintOpto) diff -r 2cd5e15048e6 -r 2aff40cb4703 src/share/vm/opto/macro.cpp --- a/src/share/vm/opto/macro.cpp Tue Nov 27 12:48:52 2012 -0800 +++ b/src/share/vm/opto/macro.cpp Tue Nov 27 17:24:15 2012 -0800 @@ -2262,7 +2262,7 @@ Node *slow_ctrl = _fallthroughproj->clone(); transform_later(slow_ctrl); _igvn.hash_delete(_fallthroughproj); - _fallthroughproj->disconnect_inputs(NULL); + _fallthroughproj->disconnect_inputs(NULL, C); region->init_req(1, slow_ctrl); // region inputs are now complete transform_later(region); @@ -2327,7 +2327,7 @@ Node *slow_ctrl = _fallthroughproj->clone(); transform_later(slow_ctrl); _igvn.hash_delete(_fallthroughproj); - _fallthroughproj->disconnect_inputs(NULL); + _fallthroughproj->disconnect_inputs(NULL, C); region->init_req(1, slow_ctrl); // region inputs are now complete transform_later(region); diff -r 2cd5e15048e6 -r 2aff40cb4703 src/share/vm/opto/matcher.cpp --- a/src/share/vm/opto/matcher.cpp Tue Nov 27 12:48:52 2012 -0800 +++ b/src/share/vm/opto/matcher.cpp Tue Nov 27 17:24:15 2012 -0800 @@ -342,6 +342,7 @@ // Reset node counter so MachNodes start with _idx at 0 int nodes = C->unique(); // save value C->set_unique(0); + C->reset_dead_node_list(); // Recursively match trees from old space into new space. // Correct leaves of new-space Nodes; they point to old-space. diff -r 2cd5e15048e6 -r 2aff40cb4703 src/share/vm/opto/node.cpp --- a/src/share/vm/opto/node.cpp Tue Nov 27 12:48:52 2012 -0800 +++ b/src/share/vm/opto/node.cpp Tue Nov 27 17:24:15 2012 -0800 @@ -57,7 +57,7 @@ int new_debug_idx = old_debug_idx+1; if (new_debug_idx > 0) { // Arrange that the lowest five decimal digits of _debug_idx - // will repeat thos of _idx. In case this is somehow pathological, + // will repeat those of _idx. In case this is somehow pathological, // we continue to assign negative numbers (!) consecutively. const int mod = 100000; int bump = (int)(_idx - new_debug_idx) % mod; @@ -67,7 +67,7 @@ } Compile::set_debug_idx(new_debug_idx); set_debug_idx( new_debug_idx ); - assert(Compile::current()->unique() < (uint)MaxNodeLimit, "Node limit exceeded"); + assert(Compile::current()->unique() < (UINT_MAX - 1), "Node limit exceeded UINT_MAX"); if (BreakAtNode != 0 && (_debug_idx == BreakAtNode || (int)_idx == BreakAtNode)) { tty->print_cr("BreakAtNode: _idx=%d _debug_idx=%d", _idx, _debug_idx); BREAKPOINT; @@ -802,7 +802,7 @@ //-------------------------disconnect_inputs----------------------------------- // NULL out all inputs to eliminate incoming Def-Use edges. // Return the number of edges between 'n' and 'this' -int Node::disconnect_inputs(Node *n) { +int Node::disconnect_inputs(Node *n, Compile* C) { int edges_to_n = 0; uint cnt = req(); @@ -824,6 +824,9 @@ // Node::destruct requires all out edges be deleted first // debug_only(destruct();) // no reuse benefit expected + if (edges_to_n == 0) { + C->record_dead_node(_idx); + } return edges_to_n; } diff -r 2cd5e15048e6 -r 2aff40cb4703 src/share/vm/opto/node.hpp --- a/src/share/vm/opto/node.hpp Tue Nov 27 12:48:52 2012 -0800 +++ b/src/share/vm/opto/node.hpp Tue Nov 27 17:24:15 2012 -0800 @@ -410,7 +410,7 @@ int replace_edge(Node* old, Node* neww); // NULL out all inputs to eliminate incoming Def-Use edges. // Return the number of edges between 'n' and 'this' - int disconnect_inputs(Node *n); + int disconnect_inputs(Node *n, Compile *c); // Quickly, return true if and only if I am Compile::current()->top(). bool is_top() const { @@ -458,9 +458,9 @@ void replace_by(Node* new_node); // Globally replace this node by a given new node, updating all uses // and cutting input edges of old node. - void subsume_by(Node* new_node) { + void subsume_by(Node* new_node, Compile* c) { replace_by(new_node); - disconnect_inputs(NULL); + disconnect_inputs(NULL, c); } void set_req_X( uint i, Node *n, PhaseIterGVN *igvn ); // Find the one non-null required input. RegionNode only diff -r 2cd5e15048e6 -r 2aff40cb4703 src/share/vm/opto/output.cpp --- a/src/share/vm/opto/output.cpp Tue Nov 27 12:48:52 2012 -0800 +++ b/src/share/vm/opto/output.cpp Tue Nov 27 17:24:15 2012 -0800 @@ -513,7 +513,7 @@ } adjust_block_start += diff; b->_nodes.map(idx, replacement); - mach->subsume_by(replacement); + mach->subsume_by(replacement, C); mach = replacement; progress = true; @@ -1425,7 +1425,7 @@ jmp_rule[i] = mach->rule(); #endif b->_nodes.map(j, replacement); - mach->subsume_by(replacement); + mach->subsume_by(replacement, C); n = replacement; mach = replacement; } diff -r 2cd5e15048e6 -r 2aff40cb4703 src/share/vm/opto/parse1.cpp --- a/src/share/vm/opto/parse1.cpp Tue Nov 27 12:48:52 2012 -0800 +++ b/src/share/vm/opto/parse1.cpp Tue Nov 27 17:24:15 2012 -0800 @@ -601,8 +601,8 @@ set_map(entry_map); do_exits(); - if (log) log->done("parse nodes='%d' memory='%d'", - C->unique(), C->node_arena()->used()); + if (log) log->done("parse nodes='%d' live='%d' memory='%d'", + C->unique(), C->live_nodes(), C->node_arena()->used()); } //---------------------------do_all_blocks------------------------------------- diff -r 2cd5e15048e6 -r 2aff40cb4703 src/share/vm/opto/phaseX.cpp --- a/src/share/vm/opto/phaseX.cpp Tue Nov 27 12:48:52 2012 -0800 +++ b/src/share/vm/opto/phaseX.cpp Tue Nov 27 17:24:15 2012 -0800 @@ -383,6 +383,8 @@ // Identify nodes that are reachable from below, useful. C->identify_useful_nodes(_useful); + // Update dead node list + C->update_dead_node_list(_useful); // Remove all useless nodes from PhaseValues' recorded types // Must be done before disconnecting nodes to preserve hash-table-invariant @@ -1190,7 +1192,7 @@ } } } - + C->record_dead_node(dead->_idx); if (dead->is_macro()) { C->remove_macro_node(dead); } @@ -1199,6 +1201,11 @@ continue; } } + // Constant node that has no out-edges and has only one in-edge from + // root is usually dead. However, sometimes reshaping walk makes + // it reachable by adding use edges. So, we will NOT count Con nodes + // as dead to be conservative about the dead node count at any + // given time. } // Aggressively kill globally dead uses diff -r 2cd5e15048e6 -r 2aff40cb4703 src/share/vm/opto/postaloc.cpp --- a/src/share/vm/opto/postaloc.cpp Tue Nov 27 12:48:52 2012 -0800 +++ b/src/share/vm/opto/postaloc.cpp Tue Nov 27 17:24:15 2012 -0800 @@ -146,7 +146,7 @@ } } // Disconnect control and remove precedence edges if any exist - old->disconnect_inputs(NULL); + old->disconnect_inputs(NULL, C); } return blk_adjust; } @@ -513,7 +513,7 @@ b->_nodes.remove(j--); phi_dex--; _cfg._bbs.map(phi->_idx,NULL); phi->replace_by(u); - phi->disconnect_inputs(NULL); + phi->disconnect_inputs(NULL, C); continue; } // Note that if value[pidx] exists, then we merged no new values here diff -r 2cd5e15048e6 -r 2aff40cb4703 src/share/vm/opto/reg_split.cpp --- a/src/share/vm/opto/reg_split.cpp Tue Nov 27 12:48:52 2012 -0800 +++ b/src/share/vm/opto/reg_split.cpp Tue Nov 27 17:24:15 2012 -0800 @@ -747,7 +747,7 @@ if( i >= cnt ) { // Found one unique input assert(Find_id(n) == Find_id(u), "should be the same lrg"); n->replace_by(u); // Then replace with unique input - n->disconnect_inputs(NULL); + n->disconnect_inputs(NULL, C); b->_nodes.remove(insidx); insidx--; b->_ihrp_index--; diff -r 2cd5e15048e6 -r 2aff40cb4703 src/share/vm/opto/stringopts.cpp --- a/src/share/vm/opto/stringopts.cpp Tue Nov 27 12:48:52 2012 -0800 +++ b/src/share/vm/opto/stringopts.cpp Tue Nov 27 17:24:15 2012 -0800 @@ -241,13 +241,13 @@ _stringopts->gvn()->transform(call); C->gvn_replace_by(uct, call); - uct->disconnect_inputs(NULL); + uct->disconnect_inputs(NULL, C); } } void cleanup() { // disconnect the hook node - _arguments->disconnect_inputs(NULL); + _arguments->disconnect_inputs(NULL, _stringopts->C); } }; @@ -358,7 +358,7 @@ C->gvn_replace_by(mem_proj, mem); } C->gvn_replace_by(init, C->top()); - init->disconnect_inputs(NULL); + init->disconnect_inputs(NULL, C); } Node_List PhaseStringOpts::collect_toString_calls() { @@ -1477,6 +1477,6 @@ kit.replace_call(sc->end(), result); // Unhook any hook nodes - string_sizes->disconnect_inputs(NULL); + string_sizes->disconnect_inputs(NULL, C); sc->cleanup(); }