Mercurial > hg > openjdk > jigsaw > hotspot
changeset 4582:8373c19be854
8011621: live_ranges_in_separate_class.patch
Reviewed-by: kvn, roland
Contributed-by: niclas.adlertz@oracle.com
| author | neliasso |
|---|---|
| date | Tue, 16 Apr 2013 10:08:41 +0200 |
| parents | 1c6887c9afaa |
| children | c89eab0b6b30 |
| files | make/bsd/makefiles/vm.make make/linux/makefiles/vm.make make/solaris/makefiles/vm.make make/windows/create_obj_files.sh src/os/bsd/vm/chaitin_bsd.cpp src/os/linux/vm/chaitin_linux.cpp src/os/solaris/vm/chaitin_solaris.cpp src/os/windows/vm/chaitin_windows.cpp src/share/vm/opto/chaitin.cpp src/share/vm/opto/chaitin.hpp src/share/vm/opto/coalesce.cpp src/share/vm/opto/coalesce.hpp src/share/vm/opto/compile.cpp src/share/vm/opto/idealGraphPrinter.cpp src/share/vm/opto/ifg.cpp src/share/vm/opto/live.cpp src/share/vm/opto/live.hpp src/share/vm/opto/postaloc.cpp src/share/vm/opto/reg_split.cpp src/share/vm/opto/regalloc.hpp src/share/vm/runtime/vmStructs.cpp |
| diffstat | 21 files changed, 733 insertions(+), 771 deletions(-) [+] |
line wrap: on
line diff
--- a/make/bsd/makefiles/vm.make Mon Apr 15 16:20:05 2013 -0700 +++ b/make/bsd/makefiles/vm.make Tue Apr 16 10:08:41 2013 +0200 @@ -187,7 +187,7 @@ Src_Dirs/SHARK := $(CORE_PATHS) $(SHARK_PATHS) Src_Dirs := $(Src_Dirs/$(TYPE)) -COMPILER2_SPECIFIC_FILES := opto libadt bcEscapeAnalyzer.cpp chaitin\* c2_\* runtime_\* +COMPILER2_SPECIFIC_FILES := opto libadt bcEscapeAnalyzer.cpp c2_\* runtime_\* COMPILER1_SPECIFIC_FILES := c1_\* SHARK_SPECIFIC_FILES := shark ZERO_SPECIFIC_FILES := zero
--- a/make/linux/makefiles/vm.make Mon Apr 15 16:20:05 2013 -0700 +++ b/make/linux/makefiles/vm.make Tue Apr 16 10:08:41 2013 +0200 @@ -189,7 +189,7 @@ Src_Dirs/SHARK := $(CORE_PATHS) $(SHARK_PATHS) Src_Dirs := $(Src_Dirs/$(TYPE)) -COMPILER2_SPECIFIC_FILES := opto libadt bcEscapeAnalyzer.cpp chaitin\* c2_\* runtime_\* +COMPILER2_SPECIFIC_FILES := opto libadt bcEscapeAnalyzer.cpp c2_\* runtime_\* COMPILER1_SPECIFIC_FILES := c1_\* SHARK_SPECIFIC_FILES := shark ZERO_SPECIFIC_FILES := zero
--- a/make/solaris/makefiles/vm.make Mon Apr 15 16:20:05 2013 -0700 +++ b/make/solaris/makefiles/vm.make Tue Apr 16 10:08:41 2013 +0200 @@ -202,7 +202,7 @@ Src_Dirs/SHARK := $(CORE_PATHS) Src_Dirs := $(Src_Dirs/$(TYPE)) -COMPILER2_SPECIFIC_FILES := opto libadt bcEscapeAnalyzer.cpp chaitin\* c2_\* runtime_\* +COMPILER2_SPECIFIC_FILES := opto libadt bcEscapeAnalyzer.cpp c2_\* runtime_\* COMPILER1_SPECIFIC_FILES := c1_\* SHARK_SPECIFIC_FILES := shark ZERO_SPECIFIC_FILES := zero
--- a/make/windows/create_obj_files.sh Mon Apr 15 16:20:05 2013 -0700 +++ b/make/windows/create_obj_files.sh Tue Apr 16 10:08:41 2013 +0200 @@ -114,7 +114,7 @@ "shark") Src_Dirs="${CORE_PATHS}" ;; esac -COMPILER2_SPECIFIC_FILES="opto libadt bcEscapeAnalyzer.cpp chaitin* c2_* runtime_*" +COMPILER2_SPECIFIC_FILES="opto libadt bcEscapeAnalyzer.cpp c2_* runtime_*" COMPILER1_SPECIFIC_FILES="c1_*" SHARK_SPECIFIC_FILES="shark" ZERO_SPECIFIC_FILES="zero"
--- a/src/os/bsd/vm/chaitin_bsd.cpp Mon Apr 15 16:20:05 2013 -0700 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,42 +0,0 @@ -/* - * Copyright (c) 1999, 2010, Oracle and/or its affiliates. All rights reserved. - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. - * - * This code is free software; you can redistribute it and/or modify it - * under the terms of the GNU General Public License version 2 only, as - * published by the Free Software Foundation. - * - * This code is distributed in the hope that it will be useful, but WITHOUT - * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or - * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License - * version 2 for more details (a copy is included in the LICENSE file that - * accompanied this code). - * - * You should have received a copy of the GNU General Public License version - * 2 along with this work; if not, write to the Free Software Foundation, - * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. - * - * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA - * or visit www.oracle.com if you need additional information or have any - * questions. - * - */ - -#include "precompiled.hpp" -#include "opto/chaitin.hpp" -#include "opto/machnode.hpp" - -void PhaseRegAlloc::pd_preallocate_hook() { - // no action -} - -#ifdef ASSERT -void PhaseRegAlloc::pd_postallocate_verify_hook() { - // no action -} -#endif - - -// Reconciliation History -// chaitin_solaris.cpp 1.7 99/07/12 23:54:22 -// End
--- a/src/os/linux/vm/chaitin_linux.cpp Mon Apr 15 16:20:05 2013 -0700 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,42 +0,0 @@ -/* - * Copyright (c) 1999, 2010, Oracle and/or its affiliates. All rights reserved. - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. - * - * This code is free software; you can redistribute it and/or modify it - * under the terms of the GNU General Public License version 2 only, as - * published by the Free Software Foundation. - * - * This code is distributed in the hope that it will be useful, but WITHOUT - * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or - * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License - * version 2 for more details (a copy is included in the LICENSE file that - * accompanied this code). - * - * You should have received a copy of the GNU General Public License version - * 2 along with this work; if not, write to the Free Software Foundation, - * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. - * - * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA - * or visit www.oracle.com if you need additional information or have any - * questions. - * - */ - -#include "precompiled.hpp" -#include "opto/chaitin.hpp" -#include "opto/machnode.hpp" - -void PhaseRegAlloc::pd_preallocate_hook() { - // no action -} - -#ifdef ASSERT -void PhaseRegAlloc::pd_postallocate_verify_hook() { - // no action -} -#endif - - -// Reconciliation History -// chaitin_solaris.cpp 1.7 99/07/12 23:54:22 -// End
--- a/src/os/solaris/vm/chaitin_solaris.cpp Mon Apr 15 16:20:05 2013 -0700 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,46 +0,0 @@ -/* - * Copyright (c) 1999, 2010, Oracle and/or its affiliates. All rights reserved. - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. - * - * This code is free software; you can redistribute it and/or modify it - * under the terms of the GNU General Public License version 2 only, as - * published by the Free Software Foundation. - * - * This code is distributed in the hope that it will be useful, but WITHOUT - * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or - * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License - * version 2 for more details (a copy is included in the LICENSE file that - * accompanied this code). - * - * You should have received a copy of the GNU General Public License version - * 2 along with this work; if not, write to the Free Software Foundation, - * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. - * - * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA - * or visit www.oracle.com if you need additional information or have any - * questions. - * - */ - -#include "precompiled.hpp" -#include "opto/chaitin.hpp" -#include "opto/machnode.hpp" - -void PhaseRegAlloc::pd_preallocate_hook() { - // no action -} - -#ifdef ASSERT -void PhaseRegAlloc::pd_postallocate_verify_hook() { - // no action -} -#endif - - -//Reconciliation History -// 1.1 99/02/12 15:35:26 chaitin_win32.cpp -// 1.2 99/02/18 15:38:56 chaitin_win32.cpp -// 1.4 99/03/09 10:37:48 chaitin_win32.cpp -// 1.6 99/03/25 11:07:44 chaitin_win32.cpp -// 1.8 99/06/22 16:38:58 chaitin_win32.cpp -//End
--- a/src/os/windows/vm/chaitin_windows.cpp Mon Apr 15 16:20:05 2013 -0700 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,78 +0,0 @@ -/* - * Copyright (c) 1999, 2010, Oracle and/or its affiliates. All rights reserved. - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. - * - * This code is free software; you can redistribute it and/or modify it - * under the terms of the GNU General Public License version 2 only, as - * published by the Free Software Foundation. - * - * This code is distributed in the hope that it will be useful, but WITHOUT - * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or - * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License - * version 2 for more details (a copy is included in the LICENSE file that - * accompanied this code). - * - * You should have received a copy of the GNU General Public License version - * 2 along with this work; if not, write to the Free Software Foundation, - * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. - * - * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA - * or visit www.oracle.com if you need additional information or have any - * questions. - * - */ - -#include "precompiled.hpp" -#include "opto/chaitin.hpp" -#include "opto/machnode.hpp" - -// Disallow the use of the frame pointer (EBP) for implicit null exceptions -// on win95/98. If we do not do this, the OS gets confused and gives a stack -// error. -void PhaseRegAlloc::pd_preallocate_hook() { -#ifndef _WIN64 - if (ImplicitNullChecks && !os::win32::is_nt()) { - for (uint block_num=1; block_num<_cfg._num_blocks; block_num++) { - Block *block = _cfg._blocks[block_num]; - - Node *block_end = block->end(); - if (block_end->is_MachNullCheck() && - block_end->as_Mach()->ideal_Opcode() != Op_Con) { - // The last instruction in the block is an implicit null check. - // Fix its input so that it does not load into the frame pointer. - _matcher.pd_implicit_null_fixup(block_end->in(1)->as_Mach(), - block_end->as_MachNullCheck()->_vidx); - } - } - } -#else - // WIN64==itanium on XP -#endif -} - -#ifdef ASSERT -// Verify that no implicit null check uses the frame pointer (EBP) as -// its register on win95/98. Use of the frame pointer in an implicit -// null check confuses the OS, yielding a stack error. -void PhaseRegAlloc::pd_postallocate_verify_hook() { -#ifndef _WIN64 - if (ImplicitNullChecks && !os::win32::is_nt()) { - for (uint block_num=1; block_num<_cfg._num_blocks; block_num++) { - Block *block = _cfg._blocks[block_num]; - - Node *block_end = block->_nodes[block->_nodes.size()-1]; - if (block_end->is_MachNullCheck() && block_end->as_Mach()->ideal_Opcode() != Op_Con) { - // The last instruction in the block is an implicit - // null check. Verify that this instruction does not - // use the frame pointer. - int reg = get_reg_first(block_end->in(1)->in(block_end->as_MachNullCheck()->_vidx)); - assert(reg != EBP_num, - "implicit null check using frame pointer on win95/98"); - } - } - } -#else - // WIN64==itanium on XP -#endif -} -#endif
--- a/src/share/vm/opto/chaitin.cpp Mon Apr 15 16:20:05 2013 -0700 +++ b/src/share/vm/opto/chaitin.cpp Tue Apr 16 10:08:41 2013 +0200 @@ -145,6 +145,72 @@ #define NUMBUCKS 3 +// Straight out of Tarjan's union-find algorithm +uint LiveRangeMap::find_compress(uint lrg) { + uint cur = lrg; + uint next = _uf_map[cur]; + while (next != cur) { // Scan chain of equivalences + assert( next < cur, "always union smaller"); + cur = next; // until find a fixed-point + next = _uf_map[cur]; + } + + // Core of union-find algorithm: update chain of + // equivalences to be equal to the root. + while (lrg != next) { + uint tmp = _uf_map[lrg]; + _uf_map.map(lrg, next); + lrg = tmp; + } + return lrg; +} + +// Reset the Union-Find map to identity +void LiveRangeMap::reset_uf_map(uint max_lrg_id) { + _max_lrg_id= max_lrg_id; + // Force the Union-Find mapping to be at least this large + _uf_map.extend(_max_lrg_id, 0); + // Initialize it to be the ID mapping. + for (uint i = 0; i < _max_lrg_id; ++i) { + _uf_map.map(i, i); + } +} + +// Make all Nodes map directly to their final live range; no need for +// the Union-Find mapping after this call. +void LiveRangeMap::compress_uf_map_for_nodes() { + // For all Nodes, compress mapping + uint unique = _names.Size(); + for (uint i = 0; i < unique; ++i) { + uint lrg = _names[i]; + uint compressed_lrg = find(lrg); + if (lrg != compressed_lrg) { + _names.map(i, compressed_lrg); + } + } +} + +// Like Find above, but no path compress, so bad asymptotic behavior +uint LiveRangeMap::find_const(uint lrg) const { + if (!lrg) { + return lrg; // Ignore the zero LRG + } + + // Off the end? This happens during debugging dumps when you got + // brand new live ranges but have not told the allocator yet. + if (lrg >= _max_lrg_id) { + return lrg; + } + + uint next = _uf_map[lrg]; + while (next != lrg) { // Scan chain of equivalences + assert(next < lrg, "always union smaller"); + lrg = next; // until find a fixed-point + next = _uf_map[lrg]; + } + return next; +} + //------------------------------Chaitin---------------------------------------- PhaseChaitin::PhaseChaitin(uint unique, PhaseCFG &cfg, Matcher &matcher) : PhaseRegAlloc(unique, cfg, matcher, @@ -153,13 +219,13 @@ #else NULL #endif - ), - _names(unique), _uf_map(unique), - _maxlrg(0), _live(0), - _spilled_once(Thread::current()->resource_area()), - _spilled_twice(Thread::current()->resource_area()), - _lo_degree(0), _lo_stk_degree(0), _hi_degree(0), _simplified(0), - _oldphi(unique) + ) + , _lrg_map(unique) + , _live(0) + , _spilled_once(Thread::current()->resource_area()) + , _spilled_twice(Thread::current()->resource_area()) + , _lo_degree(0), _lo_stk_degree(0), _hi_degree(0), _simplified(0) + , _oldphi(unique) #ifndef PRODUCT , _trace_spilling(TraceSpilling || C->method_has_option("TraceSpilling")) #endif @@ -168,7 +234,6 @@ _high_frequency_lrg = MIN2(float(OPTO_LRG_HIGH_FREQ), _cfg._outer_loop_freq); - uint i,j; // Build a list of basic blocks, sorted by frequency _blks = NEW_RESOURCE_ARRAY( Block *, _cfg._num_blocks ); // Experiment with sorting strategies to speed compilation @@ -176,30 +241,30 @@ Block **buckets[NUMBUCKS]; // Array of buckets uint buckcnt[NUMBUCKS]; // Array of bucket counters double buckval[NUMBUCKS]; // Array of bucket value cutoffs - for( i = 0; i < NUMBUCKS; i++ ) { - buckets[i] = NEW_RESOURCE_ARRAY( Block *, _cfg._num_blocks ); + for (uint i = 0; i < NUMBUCKS; i++) { + buckets[i] = NEW_RESOURCE_ARRAY(Block *, _cfg._num_blocks); buckcnt[i] = 0; // Bump by three orders of magnitude each time cutoff *= 0.001; buckval[i] = cutoff; - for( j = 0; j < _cfg._num_blocks; j++ ) { + for (uint j = 0; j < _cfg._num_blocks; j++) { buckets[i][j] = NULL; } } // Sort blocks into buckets - for( i = 0; i < _cfg._num_blocks; i++ ) { - for( j = 0; j < NUMBUCKS; j++ ) { - if( (j == NUMBUCKS-1) || (_cfg._blocks[i]->_freq > buckval[j]) ) { + for (uint i = 0; i < _cfg._num_blocks; i++) { + for (uint j = 0; j < NUMBUCKS; j++) { + if ((j == NUMBUCKS - 1) || (_cfg._blocks[i]->_freq > buckval[j])) { // Assign block to end of list for appropriate bucket buckets[j][buckcnt[j]++] = _cfg._blocks[i]; - break; // kick out of inner loop + break; // kick out of inner loop } } } // Dump buckets into final block array uint blkcnt = 0; - for( i = 0; i < NUMBUCKS; i++ ) { - for( j = 0; j < buckcnt[i]; j++ ) { + for (uint i = 0; i < NUMBUCKS; i++) { + for (uint j = 0; j < buckcnt[i]; j++) { _blks[blkcnt++] = buckets[i][j]; } } @@ -207,6 +272,77 @@ assert(blkcnt == _cfg._num_blocks, "Block array not totally filled"); } +//------------------------------Union------------------------------------------ +// union 2 sets together. +void PhaseChaitin::Union( const Node *src_n, const Node *dst_n ) { + uint src = _lrg_map.find(src_n); + uint dst = _lrg_map.find(dst_n); + assert(src, ""); + assert(dst, ""); + assert(src < _lrg_map.max_lrg_id(), "oob"); + assert(dst < _lrg_map.max_lrg_id(), "oob"); + assert(src < dst, "always union smaller"); + _lrg_map.uf_map(dst, src); +} + +//------------------------------new_lrg---------------------------------------- +void PhaseChaitin::new_lrg(const Node *x, uint lrg) { + // Make the Node->LRG mapping + _lrg_map.extend(x->_idx,lrg); + // Make the Union-Find mapping an identity function + _lrg_map.uf_extend(lrg, lrg); +} + + +bool PhaseChaitin::clone_projs_shared(Block *b, uint idx, Node *con, Node *copy, uint max_lrg_id) { + Block *bcon = _cfg._bbs[con->_idx]; + uint cindex = bcon->find_node(con); + Node *con_next = bcon->_nodes[cindex+1]; + if (con_next->in(0) != con || !con_next->is_MachProj()) { + return false; // No MachProj's follow + } + + // Copy kills after the cloned constant + Node *kills = con_next->clone(); + kills->set_req(0, copy); + b->_nodes.insert(idx, kills); + _cfg._bbs.map(kills->_idx, b); + new_lrg(kills, max_lrg_id); + return true; +} + +//------------------------------compact---------------------------------------- +// Renumber the live ranges to compact them. Makes the IFG smaller. +void PhaseChaitin::compact() { + // Current the _uf_map contains a series of short chains which are headed + // by a self-cycle. All the chains run from big numbers to little numbers. + // The Find() call chases the chains & shortens them for the next Find call. + // We are going to change this structure slightly. Numbers above a moving + // wave 'i' are unchanged. Numbers below 'j' point directly to their + // compacted live range with no further chaining. There are no chains or + // cycles below 'i', so the Find call no longer works. + uint j=1; + uint i; + for (i = 1; i < _lrg_map.max_lrg_id(); i++) { + uint lr = _lrg_map.uf_live_range_id(i); + // Ignore unallocated live ranges + if (!lr) { + continue; + } + assert(lr <= i, ""); + _lrg_map.uf_map(i, ( lr == i ) ? j++ : _lrg_map.uf_live_range_id(lr)); + } + // Now change the Node->LR mapping to reflect the compacted names + uint unique = _lrg_map.size(); + for (i = 0; i < unique; i++) { + uint lrg_id = _lrg_map.live_range_id(i); + _lrg_map.map(i, _lrg_map.uf_live_range_id(lrg_id)); + } + + // Reset the Union-Find mapping + _lrg_map.reset_uf_map(j); +} + void PhaseChaitin::Register_Allocate() { // Above the OLD FP (and in registers) are the incoming arguments. Stack @@ -231,14 +367,12 @@ // all copy-related live ranges low and then using the max copy-related // live range as a cut-off for LIVE and the IFG. In other words, I can // build a subset of LIVE and IFG just for copies. - PhaseLive live(_cfg,_names,&live_arena); + PhaseLive live(_cfg, _lrg_map.names(), &live_arena); // Need IFG for coalescing and coloring - PhaseIFG ifg( &live_arena ); + PhaseIFG ifg(&live_arena); _ifg = &ifg; - if (C->unique() > _names.Size()) _names.extend(C->unique()-1, 0); - // Come out of SSA world to the Named world. Assign (virtual) registers to // Nodes. Use the same register for all inputs and the output of PhiNodes // - effectively ending SSA form. This requires either coalescing live @@ -258,9 +392,9 @@ _live = NULL; // Mark live as being not available rm.reset_to_mark(); // Reclaim working storage IndexSet::reset_memory(C, &live_arena); - ifg.init(_maxlrg); // Empty IFG + ifg.init(_lrg_map.max_lrg_id()); // Empty IFG gather_lrg_masks( false ); // Collect LRG masks - live.compute( _maxlrg ); // Compute liveness + live.compute(_lrg_map.max_lrg_id()); // Compute liveness _live = &live; // Mark LIVE as being available } @@ -270,19 +404,19 @@ // across any GC point where the derived value is live. So this code looks // at all the GC points, and "stretches" the live range of any base pointer // to the GC point. - if( stretch_base_pointer_live_ranges(&live_arena) ) { - NOT_PRODUCT( Compile::TracePhase t3("computeLive (sbplr)", &_t_computeLive, TimeCompiler); ) + if (stretch_base_pointer_live_ranges(&live_arena)) { + NOT_PRODUCT(Compile::TracePhase t3("computeLive (sbplr)", &_t_computeLive, TimeCompiler);) // Since some live range stretched, I need to recompute live _live = NULL; rm.reset_to_mark(); // Reclaim working storage IndexSet::reset_memory(C, &live_arena); - ifg.init(_maxlrg); - gather_lrg_masks( false ); - live.compute( _maxlrg ); + ifg.init(_lrg_map.max_lrg_id()); + gather_lrg_masks(false); + live.compute(_lrg_map.max_lrg_id()); _live = &live; } // Create the interference graph using virtual copies - build_ifg_virtual( ); // Include stack slots this time + build_ifg_virtual(); // Include stack slots this time // Aggressive (but pessimistic) copy coalescing. // This pass works on virtual copies. Any virtual copies which are not @@ -296,8 +430,8 @@ // given Node and search them for an instance, i.e., time O(#MaxLRG)). _ifg->SquareUp(); - PhaseAggressiveCoalesce coalesce( *this ); - coalesce.coalesce_driver( ); + PhaseAggressiveCoalesce coalesce(*this); + coalesce.coalesce_driver(); // Insert un-coalesced copies. Visit all Phis. Where inputs to a Phi do // not match the Phi itself, insert a copy. coalesce.insert_copies(_matcher); @@ -310,28 +444,36 @@ _live = NULL; rm.reset_to_mark(); // Reclaim working storage IndexSet::reset_memory(C, &live_arena); - ifg.init(_maxlrg); + ifg.init(_lrg_map.max_lrg_id()); gather_lrg_masks( true ); - live.compute( _maxlrg ); + live.compute(_lrg_map.max_lrg_id()); _live = &live; } // Build physical interference graph uint must_spill = 0; - must_spill = build_ifg_physical( &live_arena ); + must_spill = build_ifg_physical(&live_arena); // If we have a guaranteed spill, might as well spill now - if( must_spill ) { - if( !_maxlrg ) return; + if (must_spill) { + if(!_lrg_map.max_lrg_id()) { + return; + } // Bail out if unique gets too large (ie - unique > MaxNodeLimit) C->check_node_count(10*must_spill, "out of nodes before split"); - if (C->failing()) return; - _maxlrg = Split(_maxlrg, &split_arena); // Split spilling LRG everywhere + if (C->failing()) { + return; + } + + uint new_max_lrg_id = Split(_lrg_map.max_lrg_id(), &split_arena); // Split spilling LRG everywhere + _lrg_map.set_max_lrg_id(new_max_lrg_id); // Bail out if unique gets too large (ie - unique > MaxNodeLimit - 2*NodeLimitFudgeFactor) // or we failed to split C->check_node_count(2*NodeLimitFudgeFactor, "out of nodes after physical split"); - if (C->failing()) return; + if (C->failing()) { + return; + } - NOT_PRODUCT( C->verify_graph_edges(); ) + NOT_PRODUCT(C->verify_graph_edges();) compact(); // Compact LRGs; return new lower max lrg @@ -340,23 +482,23 @@ _live = NULL; rm.reset_to_mark(); // Reclaim working storage IndexSet::reset_memory(C, &live_arena); - ifg.init(_maxlrg); // Build a new interference graph + ifg.init(_lrg_map.max_lrg_id()); // Build a new interference graph gather_lrg_masks( true ); // Collect intersect mask - live.compute( _maxlrg ); // Compute LIVE + live.compute(_lrg_map.max_lrg_id()); // Compute LIVE _live = &live; } - build_ifg_physical( &live_arena ); + build_ifg_physical(&live_arena); _ifg->SquareUp(); _ifg->Compute_Effective_Degree(); // Only do conservative coalescing if requested - if( OptoCoalesce ) { + if (OptoCoalesce) { // Conservative (and pessimistic) copy coalescing of those spills - PhaseConservativeCoalesce coalesce( *this ); + PhaseConservativeCoalesce coalesce(*this); // If max live ranges greater than cutoff, don't color the stack. // This cutoff can be larger than below since it is only done once. - coalesce.coalesce_driver( ); + coalesce.coalesce_driver(); } - compress_uf_map_for_nodes(); + _lrg_map.compress_uf_map_for_nodes(); #ifdef ASSERT verify(&live_arena, true); @@ -390,13 +532,18 @@ } } - if( !_maxlrg ) return; - _maxlrg = Split(_maxlrg, &split_arena); // Split spilling LRG everywhere + if (!_lrg_map.max_lrg_id()) { + return; + } + uint new_max_lrg_id = Split(_lrg_map.max_lrg_id(), &split_arena); // Split spilling LRG everywhere + _lrg_map.set_max_lrg_id(new_max_lrg_id); // Bail out if unique gets too large (ie - unique > MaxNodeLimit - 2*NodeLimitFudgeFactor) - C->check_node_count(2*NodeLimitFudgeFactor, "out of nodes after split"); - if (C->failing()) return; + C->check_node_count(2 * NodeLimitFudgeFactor, "out of nodes after split"); + if (C->failing()) { + return; + } - compact(); // Compact LRGs; return new lower max lrg + compact(); // Compact LRGs; return new lower max lrg // Nuke the live-ness and interference graph and LiveRanGe info { @@ -404,26 +551,26 @@ _live = NULL; rm.reset_to_mark(); // Reclaim working storage IndexSet::reset_memory(C, &live_arena); - ifg.init(_maxlrg); + ifg.init(_lrg_map.max_lrg_id()); // Create LiveRanGe array. // Intersect register masks for all USEs and DEFs - gather_lrg_masks( true ); - live.compute( _maxlrg ); + gather_lrg_masks(true); + live.compute(_lrg_map.max_lrg_id()); _live = &live; } - must_spill = build_ifg_physical( &live_arena ); + must_spill = build_ifg_physical(&live_arena); _ifg->SquareUp(); _ifg->Compute_Effective_Degree(); // Only do conservative coalescing if requested - if( OptoCoalesce ) { + if (OptoCoalesce) { // Conservative (and pessimistic) copy coalescing - PhaseConservativeCoalesce coalesce( *this ); + PhaseConservativeCoalesce coalesce(*this); // Check for few live ranges determines how aggressive coalesce is. - coalesce.coalesce_driver( ); + coalesce.coalesce_driver(); } - compress_uf_map_for_nodes(); + _lrg_map.compress_uf_map_for_nodes(); #ifdef ASSERT verify(&live_arena, true); #endif @@ -435,7 +582,7 @@ // Select colors by re-inserting LRGs back into the IFG in reverse order. // Return whether or not something spills. - spills = Select( ); + spills = Select(); } // Count number of Simplify-Select trips per coloring success. @@ -452,9 +599,12 @@ // max_reg is past the largest *register* used. // Convert that to a frame_slot number. - if( _max_reg <= _matcher._new_SP ) + if (_max_reg <= _matcher._new_SP) { _framesize = C->out_preserve_stack_slots(); - else _framesize = _max_reg -_matcher._new_SP; + } + else { + _framesize = _max_reg -_matcher._new_SP; + } assert((int)(_matcher._new_SP+_framesize) >= (int)_matcher._out_arg_limit, "framesize must be large enough"); // This frame must preserve the required fp alignment @@ -462,8 +612,9 @@ assert( _framesize >= 0 && _framesize <= 1000000, "sanity check" ); #ifndef PRODUCT _total_framesize += _framesize; - if( (int)_framesize > _max_framesize ) + if ((int)_framesize > _max_framesize) { _max_framesize = _framesize; + } #endif // Convert CISC spills @@ -475,15 +626,17 @@ log->elem("regalloc attempts='%d' success='%d'", _trip_cnt, !C->failing()); } - if (C->failing()) return; + if (C->failing()) { + return; + } - NOT_PRODUCT( C->verify_graph_edges(); ) + NOT_PRODUCT(C->verify_graph_edges();) // Move important info out of the live_arena to longer lasting storage. - alloc_node_regs(_names.Size()); - for (uint i=0; i < _names.Size(); i++) { - if (_names[i]) { // Live range associated with Node? - LRG &lrg = lrgs(_names[i]); + alloc_node_regs(_lrg_map.size()); + for (uint i=0; i < _lrg_map.size(); i++) { + if (_lrg_map.live_range_id(i)) { // Live range associated with Node? + LRG &lrg = lrgs(_lrg_map.live_range_id(i)); if (!lrg.alive()) { set_bad(i); } else if (lrg.num_regs() == 1) { @@ -537,11 +690,11 @@ Node *n = b->_nodes[j]; // Pre-color to the zero live range, or pick virtual register const RegMask &rm = n->out_RegMask(); - _names.map( n->_idx, rm.is_NotEmpty() ? lr_counter++ : 0 ); + _lrg_map.map(n->_idx, rm.is_NotEmpty() ? lr_counter++ : 0); } } // Reset the Union-Find mapping to be identity - reset_uf_map(lr_counter); + _lrg_map.reset_uf_map(lr_counter); } @@ -551,7 +704,7 @@ void PhaseChaitin::gather_lrg_masks( bool after_aggressive ) { // Nail down the frame pointer live range - uint fp_lrg = n2lidx(_cfg._root->in(1)->in(TypeFunc::FramePtr)); + uint fp_lrg = _lrg_map.live_range_id(_cfg._root->in(1)->in(TypeFunc::FramePtr)); lrgs(fp_lrg)._cost += 1e12; // Cost is infinite // For all blocks @@ -566,14 +719,14 @@ uint idx = n->is_Copy(); // Get virtual register number, same as LiveRanGe index - uint vreg = n2lidx(n); + uint vreg = _lrg_map.live_range_id(n); LRG &lrg = lrgs(vreg); if( vreg ) { // No vreg means un-allocable (e.g. memory) // Collect has-copy bit if( idx ) { lrg._has_copy = 1; - uint clidx = n2lidx(n->in(idx)); + uint clidx = _lrg_map.live_range_id(n->in(idx)); LRG ©_src = lrgs(clidx); copy_src._has_copy = 1; } @@ -773,8 +926,10 @@ } // Prepare register mask for each input for( uint k = input_edge_start; k < cnt; k++ ) { - uint vreg = n2lidx(n->in(k)); - if( !vreg ) continue; + uint vreg = _lrg_map.live_range_id(n->in(k)); + if (!vreg) { + continue; + } // If this instruction is CISC Spillable, add the flags // bit to its appropriate input @@ -857,7 +1012,7 @@ } // end for all blocks // Final per-liverange setup - for (uint i2=0; i2<_maxlrg; i2++) { + for (uint i2 = 0; i2 < _lrg_map.max_lrg_id(); i2++) { LRG &lrg = lrgs(i2); assert(!lrg._is_vector || !lrg._fat_proj, "sanity"); if (lrg.num_regs() > 1 && !lrg._fat_proj) { @@ -879,7 +1034,7 @@ // The bit is checked in Simplify. void PhaseChaitin::set_was_low() { #ifdef ASSERT - for( uint i = 1; i < _maxlrg; i++ ) { + for (uint i = 1; i < _lrg_map.max_lrg_id(); i++) { int size = lrgs(i).num_regs(); uint old_was_lo = lrgs(i)._was_lo; lrgs(i)._was_lo = 0; @@ -913,7 +1068,7 @@ // Compute cost/area ratio, in case we spill. Build the lo-degree list. void PhaseChaitin::cache_lrg_info( ) { - for( uint i = 1; i < _maxlrg; i++ ) { + for (uint i = 1; i < _lrg_map.max_lrg_id(); i++) { LRG &lrg = lrgs(i); // Check for being of low degree: means we can be trivially colored. @@ -949,10 +1104,10 @@ // Warm up the lo-degree no-copy list int lo_no_copy = 0; - for( uint i = 1; i < _maxlrg; i++ ) { - if( (lrgs(i).lo_degree() && !lrgs(i)._has_copy) || + for (uint i = 1; i < _lrg_map.max_lrg_id(); i++) { + if ((lrgs(i).lo_degree() && !lrgs(i)._has_copy) || !lrgs(i).alive() || - lrgs(i)._must_spill ) { + lrgs(i)._must_spill) { lrgs(i)._next = lo_no_copy; lo_no_copy = i; } @@ -1163,7 +1318,7 @@ OptoReg::Name PhaseChaitin::bias_color( LRG &lrg, int chunk ) { // Check for "at_risk" LRG's - uint risk_lrg = Find(lrg._risk_bias); + uint risk_lrg = _lrg_map.find(lrg._risk_bias); if( risk_lrg != 0 ) { // Walk the colored neighbors of the "at_risk" candidate // Choose a color which is both legal and already taken by a neighbor @@ -1179,7 +1334,7 @@ } } - uint copy_lrg = Find(lrg._copy_bias); + uint copy_lrg = _lrg_map.find(lrg._copy_bias); if( copy_lrg != 0 ) { // If he has a color, if( !(*(_ifg->_yanked))[copy_lrg] ) { @@ -1423,10 +1578,10 @@ void PhaseChaitin::copy_was_spilled( Node *src, Node *dst ) { if( _spilled_once.test(src->_idx) ) { _spilled_once.set(dst->_idx); - lrgs(Find(dst))._was_spilled1 = 1; + lrgs(_lrg_map.find(dst))._was_spilled1 = 1; if( _spilled_twice.test(src->_idx) ) { _spilled_twice.set(dst->_idx); - lrgs(Find(dst))._was_spilled2 = 1; + lrgs(_lrg_map.find(dst))._was_spilled2 = 1; } } } @@ -1471,7 +1626,7 @@ MachNode *mach = n->as_Mach(); inp = mach->operand_index(inp); Node *src = n->in(inp); // Value to load or store - LRG &lrg_cisc = lrgs( Find_const(src) ); + LRG &lrg_cisc = lrgs(_lrg_map.find_const(src)); OptoReg::Name src_reg = lrg_cisc.reg(); // Doubles record the HIGH register of an adjacent pair. src_reg = OptoReg::add(src_reg,1-lrg_cisc.num_regs()); @@ -1554,9 +1709,9 @@ Block *startb = _cfg._bbs[C->top()->_idx]; startb->_nodes.insert(startb->find_node(C->top()), base ); _cfg._bbs.map( base->_idx, startb ); - assert (n2lidx(base) == 0, "should not have LRG yet"); + assert(_lrg_map.live_range_id(base) == 0, "should not have LRG yet"); } - if (n2lidx(base) == 0) { + if (_lrg_map.live_range_id(base) == 0) { new_lrg(base, maxlrg++); } assert(base->in(0) == _cfg._root && @@ -1566,7 +1721,7 @@ } // Check for AddP-related opcodes - if( !derived->is_Phi() ) { + if (!derived->is_Phi()) { assert(derived->as_Mach()->ideal_Opcode() == Op_AddP, err_msg_res("but is: %s", derived->Name())); Node *base = derived->in(AddPNode::Base); derived_base_map[derived->_idx] = base; @@ -1629,9 +1784,9 @@ // base pointer that is live across the Safepoint for oopmap building. The // edge pairs get added in after sfpt->jvmtail()->oopoff(), but are in the // required edge set. -bool PhaseChaitin::stretch_base_pointer_live_ranges( ResourceArea *a ) { +bool PhaseChaitin::stretch_base_pointer_live_ranges(ResourceArea *a) { int must_recompute_live = false; - uint maxlrg = _maxlrg; + uint maxlrg = _lrg_map.max_lrg_id(); Node **derived_base_map = (Node**)a->Amalloc(sizeof(Node*)*C->unique()); memset( derived_base_map, 0, sizeof(Node*)*C->unique() ); @@ -1669,15 +1824,18 @@ } // Get value being defined - uint lidx = n2lidx(n); - if( lidx && lidx < _maxlrg /* Ignore the occasional brand-new live range */) { + uint lidx = _lrg_map.live_range_id(n); + // Ignore the occasional brand-new live range + if (lidx && lidx < _lrg_map.max_lrg_id()) { // Remove from live-out set liveout.remove(lidx); // Copies do not define a new value and so do not interfere. // Remove the copies source from the liveout set before interfering. uint idx = n->is_Copy(); - if( idx ) liveout.remove( n2lidx(n->in(idx)) ); + if (idx) { + liveout.remove(_lrg_map.live_range_id(n->in(idx))); + } } // Found a safepoint? @@ -1695,21 +1853,21 @@ derived->bottom_type()->make_ptr()->is_ptr()->_offset == 0, "sanity"); // If its an OOP with a non-zero offset, then it is derived. if( tj && tj->_offset != 0 && tj->isa_oop_ptr() ) { - Node *base = find_base_for_derived( derived_base_map, derived, maxlrg ); - assert( base->_idx < _names.Size(), "" ); + Node *base = find_base_for_derived(derived_base_map, derived, maxlrg); + assert(base->_idx < _lrg_map.size(), ""); // Add reaching DEFs of derived pointer and base pointer as a // pair of inputs - n->add_req( derived ); - n->add_req( base ); + n->add_req(derived); + n->add_req(base); // See if the base pointer is already live to this point. // Since I'm working on the SSA form, live-ness amounts to // reaching def's. So if I find the base's live range then // I know the base's def reaches here. - if( (n2lidx(base) >= _maxlrg ||// (Brand new base (hence not live) or - !liveout.member( n2lidx(base) ) ) && // not live) AND - (n2lidx(base) > 0) && // not a constant - _cfg._bbs[base->_idx] != b ) { // base not def'd in blk) + if ((_lrg_map.live_range_id(base) >= _lrg_map.max_lrg_id() || // (Brand new base (hence not live) or + !liveout.member(_lrg_map.live_range_id(base))) && // not live) AND + (_lrg_map.live_range_id(base) > 0) && // not a constant + _cfg._bbs[base->_idx] != b) { // base not def'd in blk) // Base pointer is not currently live. Since I stretched // the base pointer to here and it crosses basic-block // boundaries, the global live info is now incorrect. @@ -1721,11 +1879,12 @@ } // End of if found a GC point // Make all inputs live - if( !n->is_Phi() ) { // Phi function uses come from prior block - for( uint k = 1; k < n->req(); k++ ) { - uint lidx = n2lidx(n->in(k)); - if( lidx < _maxlrg ) - liveout.insert( lidx ); + if (!n->is_Phi()) { // Phi function uses come from prior block + for (uint k = 1; k < n->req(); k++) { + uint lidx = _lrg_map.live_range_id(n->in(k)); + if (lidx < _lrg_map.max_lrg_id()) { + liveout.insert(lidx); + } } } @@ -1733,11 +1892,12 @@ liveout.clear(); // Free the memory used by liveout. } // End of forall blocks - _maxlrg = maxlrg; + _lrg_map.set_max_lrg_id(maxlrg); // If I created a new live range I need to recompute live - if( maxlrg != _ifg->_maxlrg ) + if (maxlrg != _ifg->_maxlrg) { must_recompute_live = true; + } return must_recompute_live != 0; } @@ -1745,16 +1905,17 @@ //------------------------------add_reference---------------------------------- // Extend the node to LRG mapping -void PhaseChaitin::add_reference( const Node *node, const Node *old_node ) { - _names.extend( node->_idx, n2lidx(old_node) ); + +void PhaseChaitin::add_reference(const Node *node, const Node *old_node) { + _lrg_map.extend(node->_idx, _lrg_map.live_range_id(old_node)); } //------------------------------dump------------------------------------------- #ifndef PRODUCT -void PhaseChaitin::dump( const Node *n ) const { - uint r = (n->_idx < _names.Size() ) ? Find_const(n) : 0; +void PhaseChaitin::dump(const Node *n) const { + uint r = (n->_idx < _lrg_map.size()) ? _lrg_map.find_const(n) : 0; tty->print("L%d",r); - if( r && n->Opcode() != Op_Phi ) { + if (r && n->Opcode() != Op_Phi) { if( _node_regs ) { // Got a post-allocation copy of allocation? tty->print("["); OptoReg::Name second = get_reg_second(n); @@ -1775,11 +1936,13 @@ tty->print("/N%d\t",n->_idx); tty->print("%s === ", n->Name()); uint k; - for( k = 0; k < n->req(); k++) { + for (k = 0; k < n->req(); k++) { Node *m = n->in(k); - if( !m ) tty->print("_ "); + if (!m) { + tty->print("_ "); + } else { - uint r = (m->_idx < _names.Size() ) ? Find_const(m) : 0; + uint r = (m->_idx < _lrg_map.size()) ? _lrg_map.find_const(m) : 0; tty->print("L%d",r); // Data MultiNode's can have projections with no real registers. // Don't die while dumping them. @@ -1810,8 +1973,10 @@ if( k < n->len() && n->in(k) ) tty->print("| "); for( ; k < n->len(); k++ ) { Node *m = n->in(k); - if( !m ) break; - uint r = (m->_idx < _names.Size() ) ? Find_const(m) : 0; + if(!m) { + break; + } + uint r = (m->_idx < _lrg_map.size()) ? _lrg_map.find_const(m) : 0; tty->print("L%d",r); tty->print("/N%d ",m->_idx); } @@ -1839,7 +2004,7 @@ tty->print("{"); uint i; while ((i = elements.next()) != 0) { - tty->print("L%d ", Find_const(i)); + tty->print("L%d ", _lrg_map.find_const(i)); } tty->print_cr("}"); } @@ -1863,10 +2028,14 @@ // Dump LRG array tty->print("--- Live RanGe Array ---\n"); - for(uint i2 = 1; i2 < _maxlrg; i2++ ) { + for (uint i2 = 1; i2 < _lrg_map.max_lrg_id(); i2++) { tty->print("L%d: ",i2); - if( i2 < _ifg->_maxlrg ) lrgs(i2).dump( ); - else tty->print_cr("new LRG"); + if (i2 < _ifg->_maxlrg) { + lrgs(i2).dump(); + } + else { + tty->print_cr("new LRG"); + } } tty->print_cr(""); @@ -1939,7 +2108,7 @@ // Post allocation, use direct mappings, no LRG info available print_reg( get_reg_first(n), this, buf ); } else { - uint lidx = Find_const(n); // Grab LRG number + uint lidx = _lrg_map.find_const(n); // Grab LRG number if( !_ifg ) { sprintf(buf,"L%d",lidx); // No register binding yet } else if( !lidx ) { // Special, not allocated value @@ -1968,7 +2137,7 @@ if( WizardMode && (PrintCompilation || PrintOpto) ) { // Display which live ranges need to be split and the allocator's state tty->print_cr("Graph-Coloring Iteration %d will split the following live ranges", _trip_cnt); - for( uint bidx = 1; bidx < _maxlrg; bidx++ ) { + for (uint bidx = 1; bidx < _lrg_map.max_lrg_id(); bidx++) { if( lrgs(bidx).alive() && lrgs(bidx).reg() >= LRG::SPILL_REG ) { tty->print("L%d: ", bidx); lrgs(bidx).dump(); @@ -2099,14 +2268,17 @@ void PhaseChaitin::dump_lrg( uint lidx, bool defs_only ) const { tty->print_cr("---dump of L%d---",lidx); - if( _ifg ) { - if( lidx >= _maxlrg ) { + if (_ifg) { + if (lidx >= _lrg_map.max_lrg_id()) { tty->print("Attempt to print live range index beyond max live range.\n"); return; } tty->print("L%d: ",lidx); - if( lidx < _ifg->_maxlrg ) lrgs(lidx).dump( ); - else tty->print_cr("new LRG"); + if (lidx < _ifg->_maxlrg) { + lrgs(lidx).dump(); + } else { + tty->print_cr("new LRG"); + } } if( _ifg && lidx < _ifg->_maxlrg) { tty->print("Neighbors: %d - ", _ifg->neighbor_cnt(lidx)); @@ -2121,8 +2293,8 @@ // For all instructions for( uint j = 0; j < b->_nodes.size(); j++ ) { Node *n = b->_nodes[j]; - if( Find_const(n) == lidx ) { - if( !dump_once++ ) { + if (_lrg_map.find_const(n) == lidx) { + if (!dump_once++) { tty->cr(); b->dump_head( &_cfg._bbs ); } @@ -2133,11 +2305,13 @@ uint cnt = n->req(); for( uint k = 1; k < cnt; k++ ) { Node *m = n->in(k); - if (!m) continue; // be robust in the dumper - if( Find_const(m) == lidx ) { - if( !dump_once++ ) { + if (!m) { + continue; // be robust in the dumper + } + if (_lrg_map.find_const(m) == lidx) { + if (!dump_once++) { tty->cr(); - b->dump_head( &_cfg._bbs ); + b->dump_head(&_cfg._bbs); } dump(n); }
--- a/src/share/vm/opto/chaitin.hpp Mon Apr 15 16:20:05 2013 -0700 +++ b/src/share/vm/opto/chaitin.hpp Tue Apr 16 10:08:41 2013 +0200 @@ -265,18 +265,118 @@ int effective_degree( uint lidx ) const; }; -// TEMPORARILY REPLACED WITH COMMAND LINE FLAG +// The LiveRangeMap class is responsible for storing node to live range id mapping. +// Each node is mapped to a live range id (a virtual register). Nodes that are +// not considered for register allocation are given live range id 0. +class LiveRangeMap VALUE_OBJ_CLASS_SPEC { + +private: + + uint _max_lrg_id; + + // Union-find map. Declared as a short for speed. + // Indexed by live-range number, it returns the compacted live-range number + LRG_List _uf_map; + + // Map from Nodes to live ranges + LRG_List _names; + + // Straight out of Tarjan's union-find algorithm + uint find_compress(const Node *node) { + uint lrg_id = find_compress(_names[node->_idx]); + _names.map(node->_idx, lrg_id); + return lrg_id; + } + + uint find_compress(uint lrg); + +public: + + const LRG_List& names() { + return _names; + } + + uint max_lrg_id() const { + return _max_lrg_id; + } + + void set_max_lrg_id(uint max_lrg_id) { + _max_lrg_id = max_lrg_id; + } + + uint size() const { + return _names.Size(); + } + + uint live_range_id(uint idx) const { + return _names[idx]; + } + + uint live_range_id(const Node *node) const { + return _names[node->_idx]; + } + + uint uf_live_range_id(uint lrg_id) const { + return _uf_map[lrg_id]; + } -//// !!!!! Magic Constants need to move into ad file -#ifdef SPARC -//#define FLOAT_PRESSURE 30 /* SFLT_REG_mask.Size() - 1 */ -//#define INT_PRESSURE 23 /* NOTEMP_I_REG_mask.Size() - 1 */ -#define FLOAT_INCREMENT(regs) regs -#else -//#define FLOAT_PRESSURE 6 -//#define INT_PRESSURE 6 -#define FLOAT_INCREMENT(regs) 1 -#endif + void map(uint idx, uint lrg_id) { + _names.map(idx, lrg_id); + } + + void uf_map(uint dst_lrg_id, uint src_lrg_id) { + _uf_map.map(dst_lrg_id, src_lrg_id); + } + + void extend(uint idx, uint lrg_id) { + _names.extend(idx, lrg_id); + } + + void uf_extend(uint dst_lrg_id, uint src_lrg_id) { + _uf_map.extend(dst_lrg_id, src_lrg_id); + } + + LiveRangeMap(uint unique) + : _names(unique) + , _uf_map(unique) + , _max_lrg_id(0) {} + + uint find_id( const Node *n ) { + uint retval = live_range_id(n); + assert(retval == find(n),"Invalid node to lidx mapping"); + return retval; + } + + // Reset the Union-Find map to identity + void reset_uf_map(uint max_lrg_id); + + // Make all Nodes map directly to their final live range; no need for + // the Union-Find mapping after this call. + void compress_uf_map_for_nodes(); + + uint find(uint lidx) { + uint uf_lidx = _uf_map[lidx]; + return (uf_lidx == lidx) ? uf_lidx : find_compress(lidx); + } + + // Convert a Node into a Live Range Index - a lidx + uint find(const Node *node) { + uint lidx = live_range_id(node); + uint uf_lidx = _uf_map[lidx]; + return (uf_lidx == lidx) ? uf_lidx : find_compress(node); + } + + // Like Find above, but no path compress, so bad asymptotic behavior + uint find_const(uint lrg) const; + + // Like Find above, but no path compress, so bad asymptotic behavior + uint find_const(const Node *node) const { + if(node->_idx >= _names.Size()) { + return 0; // not mapped, usual for debug dump + } + return find_const(_names[node->_idx]); + } +}; //------------------------------Chaitin---------------------------------------- // Briggs-Chaitin style allocation, mostly. @@ -286,7 +386,6 @@ int _trip_cnt; int _alternate; - uint _maxlrg; // Max live range number LRG &lrgs(uint idx) const { return _ifg->lrgs(idx); } PhaseLive *_live; // Liveness, used in the interference graph PhaseIFG *_ifg; // Interference graph (for original chunk) @@ -294,16 +393,6 @@ VectorSet _spilled_once; // Nodes that have been spilled VectorSet _spilled_twice; // Nodes that have been spilled twice - LRG_List _names; // Map from Nodes to Live RanGes - - // Union-find map. Declared as a short for speed. - // Indexed by live-range number, it returns the compacted live-range number - LRG_List _uf_map; - // Reset the Union-Find map to identity - void reset_uf_map( uint maxlrg ); - // Remove the need for the Union-Find mapping - void compress_uf_map_for_nodes( ); - // Combine the Live Range Indices for these 2 Nodes into a single live // range. Future requests for any Node in either live range will // return the live range index for the combined live range. @@ -322,7 +411,34 @@ // Helper functions for Split() uint split_DEF( Node *def, Block *b, int loc, uint max, Node **Reachblock, Node **debug_defs, GrowableArray<uint> splits, int slidx ); uint split_USE( Node *def, Block *b, Node *use, uint useidx, uint max, bool def_down, bool cisc_sp, GrowableArray<uint> splits, int slidx ); - int clone_projs( Block *b, uint idx, Node *con, Node *copy, uint &maxlrg ); + + bool clone_projs(Block *b, uint idx, Node *con, Node *copy, LiveRangeMap &lrg_map) { + bool found_projs = clone_projs_shared(b, idx, con, copy, lrg_map.max_lrg_id()); + + if(found_projs) { + uint max_lrg_id = lrg_map.max_lrg_id(); + lrg_map.set_max_lrg_id(max_lrg_id + 1); + } + + return found_projs; + } + + //------------------------------clone_projs------------------------------------ + // After cloning some rematerialized instruction, clone any MachProj's that + // follow it. Example: Intel zero is XOR, kills flags. Sparc FP constants + // use G3 as an address temp. + bool clone_projs(Block *b, uint idx, Node *con, Node *copy, uint &max_lrg_id) { + bool found_projs = clone_projs_shared(b, idx, con, copy, max_lrg_id); + + if(found_projs) { + max_lrg_id++; + } + + return found_projs; + } + + bool clone_projs_shared(Block *b, uint idx, Node *con, Node *copy, uint max_lrg_id); + Node *split_Rematerialize(Node *def, Block *b, uint insidx, uint &maxlrg, GrowableArray<uint> splits, int slidx, uint *lrg2reach, Node **Reachblock, bool walkThru); // True if lidx is used before any real register is def'd in the block @@ -349,20 +465,11 @@ PhaseChaitin( uint unique, PhaseCFG &cfg, Matcher &matcher ); ~PhaseChaitin() {} - // Convert a Node into a Live Range Index - a lidx - uint Find( const Node *n ) { - uint lidx = n2lidx(n); - uint uf_lidx = _uf_map[lidx]; - return (uf_lidx == lidx) ? uf_lidx : Find_compress(n); - } - uint Find_const( uint lrg ) const; - uint Find_const( const Node *n ) const; + LiveRangeMap _lrg_map; // Do all the real work of allocate void Register_Allocate(); - uint n2lidx( const Node *n ) const { return _names[n->_idx]; } - float high_frequency_lrg() const { return _high_frequency_lrg; } #ifndef PRODUCT @@ -374,18 +481,6 @@ // all inputs to a PhiNode, effectively coalescing live ranges. Insert // copies as needed. void de_ssa(); - uint Find_compress( const Node *n ); - uint Find( uint lidx ) { - uint uf_lidx = _uf_map[lidx]; - return (uf_lidx == lidx) ? uf_lidx : Find_compress(lidx); - } - uint Find_compress( uint lidx ); - - uint Find_id( const Node *n ) { - uint retval = n2lidx(n); - assert(retval == Find(n),"Invalid node to lidx mapping"); - return retval; - } // Add edge between reg and everything in the vector. // Same as _ifg->add_vector(reg,live) EXCEPT use the RegMask
--- a/src/share/vm/opto/coalesce.cpp Mon Apr 15 16:20:05 2013 -0700 +++ b/src/share/vm/opto/coalesce.cpp Tue Apr 16 10:08:41 2013 +0200 @@ -35,159 +35,11 @@ #include "opto/regmask.hpp" //============================================================================= -//------------------------------reset_uf_map----------------------------------- -void PhaseChaitin::reset_uf_map( uint maxlrg ) { - _maxlrg = maxlrg; - // Force the Union-Find mapping to be at least this large - _uf_map.extend(_maxlrg,0); - // Initialize it to be the ID mapping. - for( uint i=0; i<_maxlrg; i++ ) - _uf_map.map(i,i); -} - -//------------------------------compress_uf_map-------------------------------- -// Make all Nodes map directly to their final live range; no need for -// the Union-Find mapping after this call. -void PhaseChaitin::compress_uf_map_for_nodes( ) { - // For all Nodes, compress mapping - uint unique = _names.Size(); - for( uint i=0; i<unique; i++ ) { - uint lrg = _names[i]; - uint compressed_lrg = Find(lrg); - if( lrg != compressed_lrg ) - _names.map(i,compressed_lrg); - } -} - -//------------------------------Find------------------------------------------- -// Straight out of Tarjan's union-find algorithm -uint PhaseChaitin::Find_compress( uint lrg ) { - uint cur = lrg; - uint next = _uf_map[cur]; - while( next != cur ) { // Scan chain of equivalences - assert( next < cur, "always union smaller" ); - cur = next; // until find a fixed-point - next = _uf_map[cur]; - } - // Core of union-find algorithm: update chain of - // equivalences to be equal to the root. - while( lrg != next ) { - uint tmp = _uf_map[lrg]; - _uf_map.map(lrg, next); - lrg = tmp; - } - return lrg; -} - -//------------------------------Find------------------------------------------- -// Straight out of Tarjan's union-find algorithm -uint PhaseChaitin::Find_compress( const Node *n ) { - uint lrg = Find_compress(_names[n->_idx]); - _names.map(n->_idx,lrg); - return lrg; -} - -//------------------------------Find_const------------------------------------- -// Like Find above, but no path compress, so bad asymptotic behavior -uint PhaseChaitin::Find_const( uint lrg ) const { - if( !lrg ) return lrg; // Ignore the zero LRG - // Off the end? This happens during debugging dumps when you got - // brand new live ranges but have not told the allocator yet. - if( lrg >= _maxlrg ) return lrg; - uint next = _uf_map[lrg]; - while( next != lrg ) { // Scan chain of equivalences - assert( next < lrg, "always union smaller" ); - lrg = next; // until find a fixed-point - next = _uf_map[lrg]; - } - return next; -} - -//------------------------------Find------------------------------------------- -// Like Find above, but no path compress, so bad asymptotic behavior -uint PhaseChaitin::Find_const( const Node *n ) const { - if( n->_idx >= _names.Size() ) return 0; // not mapped, usual for debug dump - return Find_const( _names[n->_idx] ); -} - -//------------------------------Union------------------------------------------ -// union 2 sets together. -void PhaseChaitin::Union( const Node *src_n, const Node *dst_n ) { - uint src = Find(src_n); - uint dst = Find(dst_n); - assert( src, "" ); - assert( dst, "" ); - assert( src < _maxlrg, "oob" ); - assert( dst < _maxlrg, "oob" ); - assert( src < dst, "always union smaller" ); - _uf_map.map(dst,src); -} - -//------------------------------new_lrg---------------------------------------- -void PhaseChaitin::new_lrg( const Node *x, uint lrg ) { - // Make the Node->LRG mapping - _names.extend(x->_idx,lrg); - // Make the Union-Find mapping an identity function - _uf_map.extend(lrg,lrg); -} - -//------------------------------clone_projs------------------------------------ -// After cloning some rematerialized instruction, clone any MachProj's that -// follow it. Example: Intel zero is XOR, kills flags. Sparc FP constants -// use G3 as an address temp. -int PhaseChaitin::clone_projs( Block *b, uint idx, Node *con, Node *copy, uint &maxlrg ) { - Block *bcon = _cfg._bbs[con->_idx]; - uint cindex = bcon->find_node(con); - Node *con_next = bcon->_nodes[cindex+1]; - if( con_next->in(0) != con || !con_next->is_MachProj() ) - return false; // No MachProj's follow - - // Copy kills after the cloned constant - Node *kills = con_next->clone(); - kills->set_req( 0, copy ); - b->_nodes.insert( idx, kills ); - _cfg._bbs.map( kills->_idx, b ); - new_lrg( kills, maxlrg++ ); - return true; -} - -//------------------------------compact---------------------------------------- -// Renumber the live ranges to compact them. Makes the IFG smaller. -void PhaseChaitin::compact() { - // Current the _uf_map contains a series of short chains which are headed - // by a self-cycle. All the chains run from big numbers to little numbers. - // The Find() call chases the chains & shortens them for the next Find call. - // We are going to change this structure slightly. Numbers above a moving - // wave 'i' are unchanged. Numbers below 'j' point directly to their - // compacted live range with no further chaining. There are no chains or - // cycles below 'i', so the Find call no longer works. - uint j=1; - uint i; - for( i=1; i < _maxlrg; i++ ) { - uint lr = _uf_map[i]; - // Ignore unallocated live ranges - if( !lr ) continue; - assert( lr <= i, "" ); - _uf_map.map(i, ( lr == i ) ? j++ : _uf_map[lr]); - } - if( false ) // PrintOptoCompactLiveRanges - printf("Compacted %d LRs from %d\n",i-j,i); - // Now change the Node->LR mapping to reflect the compacted names - uint unique = _names.Size(); - for( i=0; i<unique; i++ ) - _names.map(i,_uf_map[_names[i]]); - - // Reset the Union-Find mapping - reset_uf_map(j); - -} - -//============================================================================= //------------------------------Dump------------------------------------------- #ifndef PRODUCT -void PhaseCoalesce::dump( Node *n ) const { +void PhaseCoalesce::dump(Node *n) const { // Being a const function means I cannot use 'Find' - uint r = _phc.Find(n); + uint r = _phc._lrg_map.find(n); tty->print("L%d/N%d ",r,n->_idx); } @@ -235,9 +87,9 @@ //------------------------------combine_these_two------------------------------ // Combine the live ranges def'd by these 2 Nodes. N2 is an input to N1. -void PhaseCoalesce::combine_these_two( Node *n1, Node *n2 ) { - uint lr1 = _phc.Find(n1); - uint lr2 = _phc.Find(n2); +void PhaseCoalesce::combine_these_two(Node *n1, Node *n2) { + uint lr1 = _phc._lrg_map.find(n1); + uint lr2 = _phc._lrg_map.find(n2); if( lr1 != lr2 && // Different live ranges already AND !_phc._ifg->test_edge_sq( lr1, lr2 ) ) { // Do not interfere LRG *lrg1 = &_phc.lrgs(lr1); @@ -306,14 +158,18 @@ // I am about to clobber the dst_name, so the copy must be inserted // after the last use. Last use is really first-use on a backwards scan. uint i = b->end_idx()-1; - while( 1 ) { + while(1) { Node *n = b->_nodes[i]; // Check for end of virtual copies; this is also the end of the // parallel renaming effort. - if( n->_idx < _unique ) break; + if (n->_idx < _unique) { + break; + } uint idx = n->is_Copy(); assert( idx || n->is_Con() || n->is_MachProj(), "Only copies during parallel renaming" ); - if( idx && _phc.Find(n->in(idx)) == dst_name ) break; + if (idx && _phc._lrg_map.find(n->in(idx)) == dst_name) { + break; + } i--; } uint last_use_idx = i; @@ -324,24 +180,29 @@ // There can be only 1 kill that exits any block and that is // the last kill. Thus it is the first kill on a backwards scan. i = b->end_idx()-1; - while( 1 ) { + while (1) { Node *n = b->_nodes[i]; // Check for end of virtual copies; this is also the end of the // parallel renaming effort. - if( n->_idx < _unique ) break; + if (n->_idx < _unique) { + break; + } assert( n->is_Copy() || n->is_Con() || n->is_MachProj(), "Only copies during parallel renaming" ); - if( _phc.Find(n) == src_name ) { + if (_phc._lrg_map.find(n) == src_name) { kill_src_idx = i; break; } i--; } // Need a temp? Last use of dst comes after the kill of src? - if( last_use_idx >= kill_src_idx ) { + if (last_use_idx >= kill_src_idx) { // Need to break a cycle with a temp uint idx = copy->is_Copy(); Node *tmp = copy->clone(); - _phc.new_lrg(tmp,_phc._maxlrg++); + uint max_lrg_id = _phc._lrg_map.max_lrg_id(); + _phc.new_lrg(tmp, max_lrg_id); + _phc._lrg_map.set_max_lrg_id(max_lrg_id + 1); + // Insert new temp between copy and source tmp ->set_req(idx,copy->in(idx)); copy->set_req(idx,tmp); @@ -359,14 +220,14 @@ void PhaseAggressiveCoalesce::insert_copies( Matcher &matcher ) { // We do LRGs compressing and fix a liveout data only here since the other // place in Split() is guarded by the assert which we never hit. - _phc.compress_uf_map_for_nodes(); + _phc._lrg_map.compress_uf_map_for_nodes(); // Fix block's liveout data for compressed live ranges. - for(uint lrg = 1; lrg < _phc._maxlrg; lrg++ ) { - uint compressed_lrg = _phc.Find(lrg); - if( lrg != compressed_lrg ) { - for( uint bidx = 0; bidx < _phc._cfg._num_blocks; bidx++ ) { + for (uint lrg = 1; lrg < _phc._lrg_map.max_lrg_id(); lrg++) { + uint compressed_lrg = _phc._lrg_map.find(lrg); + if (lrg != compressed_lrg) { + for (uint bidx = 0; bidx < _phc._cfg._num_blocks; bidx++) { IndexSet *liveout = _phc._live->live(_phc._cfg._blocks[bidx]); - if( liveout->member(lrg) ) { + if (liveout->member(lrg)) { liveout->remove(lrg); liveout->insert(compressed_lrg); } @@ -392,8 +253,9 @@ uint cidx = copy->is_Copy(); if( cidx ) { Node *def = copy->in(cidx); - if( _phc.Find(copy) == _phc.Find(def) ) - n->set_req(k,def); + if (_phc._lrg_map.find(copy) == _phc._lrg_map.find(def)) { + n->set_req(k, def); + } } } @@ -401,7 +263,7 @@ uint cidx = n->is_Copy(); if( cidx ) { Node *def = n->in(cidx); - if( _phc.Find(n) == _phc.Find(def) ) { + if (_phc._lrg_map.find(n) == _phc._lrg_map.find(def)) { n->replace_by(def); n->set_req(cidx,NULL); b->_nodes.remove(l); @@ -410,16 +272,18 @@ } } - if( n->is_Phi() ) { + if (n->is_Phi()) { // Get the chosen name for the Phi - uint phi_name = _phc.Find( n ); + uint phi_name = _phc._lrg_map.find(n); // Ignore the pre-allocated specials - if( !phi_name ) continue; + if (!phi_name) { + continue; + } // Check for mismatch inputs to Phi - for( uint j = 1; j<cnt; j++ ) { + for (uint j = 1; j < cnt; j++) { Node *m = n->in(j); - uint src_name = _phc.Find(m); - if( src_name != phi_name ) { + uint src_name = _phc._lrg_map.find(m); + if (src_name != phi_name) { Block *pred = _phc._cfg._bbs[b->pred(j)->_idx]; Node *copy; assert(!m->is_Con() || m->is_Mach(), "all Con must be Mach"); @@ -430,18 +294,18 @@ // Insert the copy in the predecessor basic block pred->add_inst(copy); // Copy any flags as well - _phc.clone_projs( pred, pred->end_idx(), m, copy, _phc._maxlrg ); + _phc.clone_projs(pred, pred->end_idx(), m, copy, _phc._lrg_map); } else { const RegMask *rm = C->matcher()->idealreg2spillmask[m->ideal_reg()]; - copy = new (C) MachSpillCopyNode(m,*rm,*rm); + copy = new (C) MachSpillCopyNode(m, *rm, *rm); // Find a good place to insert. Kinda tricky, use a subroutine insert_copy_with_overlap(pred,copy,phi_name,src_name); } // Insert the copy in the use-def chain - n->set_req( j, copy ); + n->set_req(j, copy); _phc._cfg._bbs.map( copy->_idx, pred ); // Extend ("register allocate") the names array for the copy. - _phc._names.extend( copy->_idx, phi_name ); + _phc._lrg_map.extend(copy->_idx, phi_name); } // End of if Phi names do not match } // End of for all inputs to Phi } else { // End of if Phi @@ -450,39 +314,40 @@ uint idx; if( n->is_Mach() && (idx=n->as_Mach()->two_adr()) ) { // Get the chosen name for the Node - uint name = _phc.Find( n ); - assert( name, "no 2-address specials" ); + uint name = _phc._lrg_map.find(n); + assert (name, "no 2-address specials"); // Check for name mis-match on the 2-address input Node *m = n->in(idx); - if( _phc.Find(m) != name ) { + if (_phc._lrg_map.find(m) != name) { Node *copy; assert(!m->is_Con() || m->is_Mach(), "all Con must be Mach"); // At this point it is unsafe to extend live ranges (6550579). // Rematerialize only constants as we do for Phi above. - if( m->is_Mach() && m->as_Mach()->is_Con() && - m->as_Mach()->rematerialize() ) { + if(m->is_Mach() && m->as_Mach()->is_Con() && + m->as_Mach()->rematerialize()) { copy = m->clone(); // Insert the copy in the basic block, just before us - b->_nodes.insert( l++, copy ); - if( _phc.clone_projs( b, l, m, copy, _phc._maxlrg ) ) + b->_nodes.insert(l++, copy); + if(_phc.clone_projs(b, l, m, copy, _phc._lrg_map)) { l++; + } } else { const RegMask *rm = C->matcher()->idealreg2spillmask[m->ideal_reg()]; - copy = new (C) MachSpillCopyNode( m, *rm, *rm ); + copy = new (C) MachSpillCopyNode(m, *rm, *rm); // Insert the copy in the basic block, just before us - b->_nodes.insert( l++, copy ); + b->_nodes.insert(l++, copy); } // Insert the copy in the use-def chain - n->set_req(idx, copy ); + n->set_req(idx, copy); // Extend ("register allocate") the names array for the copy. - _phc._names.extend( copy->_idx, name ); + _phc._lrg_map.extend(copy->_idx, name); _phc._cfg._bbs.map( copy->_idx, b ); } } // End of is two-adr // Insert a copy at a debug use for a lrg which has high frequency - if( b->_freq < OPTO_DEBUG_SPLIT_FREQ || b->is_uncommon(_phc._cfg._bbs) ) { + if (b->_freq < OPTO_DEBUG_SPLIT_FREQ || b->is_uncommon(_phc._cfg._bbs)) { // Walk the debug inputs to the node and check for lrg freq JVMState* jvms = n->jvms(); uint debug_start = jvms ? jvms->debug_start() : 999999; @@ -490,9 +355,11 @@ for(uint inpidx = debug_start; inpidx < debug_end; inpidx++) { // Do not split monitors; they are only needed for debug table // entries and need no code. - if( jvms->is_monitor_use(inpidx) ) continue; + if (jvms->is_monitor_use(inpidx)) { + continue; + } Node *inp = n->in(inpidx); - uint nidx = _phc.n2lidx(inp); + uint nidx = _phc._lrg_map.live_range_id(inp); LRG &lrg = lrgs(nidx); // If this lrg has a high frequency use/def @@ -519,8 +386,10 @@ // Insert the copy in the basic block, just before us b->_nodes.insert( l++, copy ); // Extend ("register allocate") the names array for the copy. - _phc.new_lrg( copy, _phc._maxlrg++ ); - _phc._cfg._bbs.map( copy->_idx, b ); + uint max_lrg_id = _phc._lrg_map.max_lrg_id(); + _phc.new_lrg(copy, max_lrg_id); + _phc._lrg_map.set_max_lrg_id(max_lrg_id + 1); + _phc._cfg._bbs.map(copy->_idx, b); //tty->print_cr("Split a debug use in Aggressive Coalesce"); } // End of if high frequency use/def } // End of for all debug inputs @@ -583,17 +452,17 @@ uint idx; // 2-address instructions have a virtual Copy matching their input // to their output - if( n->is_Mach() && (idx = n->as_Mach()->two_adr()) ) { + if (n->is_Mach() && (idx = n->as_Mach()->two_adr())) { MachNode *mach = n->as_Mach(); - combine_these_two( mach, mach->in(idx) ); + combine_these_two(mach, mach->in(idx)); } } // End of for all instructions in block } //============================================================================= //------------------------------PhaseConservativeCoalesce---------------------- -PhaseConservativeCoalesce::PhaseConservativeCoalesce( PhaseChaitin &chaitin ) : PhaseCoalesce(chaitin) { - _ulr.initialize(_phc._maxlrg); +PhaseConservativeCoalesce::PhaseConservativeCoalesce(PhaseChaitin &chaitin) : PhaseCoalesce(chaitin) { + _ulr.initialize(_phc._lrg_map.max_lrg_id()); } //------------------------------verify----------------------------------------- @@ -673,10 +542,14 @@ // Else work back one in copy chain prev_copy = prev_copy->in(prev_copy->is_Copy()); } else { // Else collect interferences - uint lidx = _phc.Find(x); + uint lidx = _phc._lrg_map.find(x); // Found another def of live-range being stretched? - if( lidx == lr1 ) return max_juint; - if( lidx == lr2 ) return max_juint; + if(lidx == lr1) { + return max_juint; + } + if(lidx == lr2) { + return max_juint; + } // If we attempt to coalesce across a bound def if( lrgs(lidx).is_bound() ) { @@ -751,33 +624,43 @@ // See if I can coalesce a series of multiple copies together. I need the // final dest copy and the original src copy. They can be the same Node. // Compute the compatible register masks. -bool PhaseConservativeCoalesce::copy_copy( Node *dst_copy, Node *src_copy, Block *b, uint bindex ) { +bool PhaseConservativeCoalesce::copy_copy(Node *dst_copy, Node *src_copy, Block *b, uint bindex) { - if( !dst_copy->is_SpillCopy() ) return false; - if( !src_copy->is_SpillCopy() ) return false; + if (!dst_copy->is_SpillCopy()) { + return false; + } + if (!src_copy->is_SpillCopy()) { + return false; + } Node *src_def = src_copy->in(src_copy->is_Copy()); - uint lr1 = _phc.Find(dst_copy); - uint lr2 = _phc.Find(src_def ); + uint lr1 = _phc._lrg_map.find(dst_copy); + uint lr2 = _phc._lrg_map.find(src_def); // Same live ranges already? - if( lr1 == lr2 ) return false; + if (lr1 == lr2) { + return false; + } // Interfere? - if( _phc._ifg->test_edge_sq( lr1, lr2 ) ) return false; + if (_phc._ifg->test_edge_sq(lr1, lr2)) { + return false; + } // Not an oop->int cast; oop->oop, int->int, AND int->oop are OK. - if( !lrgs(lr1)._is_oop && lrgs(lr2)._is_oop ) // not an oop->int cast + if (!lrgs(lr1)._is_oop && lrgs(lr2)._is_oop) { // not an oop->int cast return false; + } // Coalescing between an aligned live range and a mis-aligned live range? // No, no! Alignment changes how we count degree. - if( lrgs(lr1)._fat_proj != lrgs(lr2)._fat_proj ) + if (lrgs(lr1)._fat_proj != lrgs(lr2)._fat_proj) { return false; + } // Sort; use smaller live-range number Node *lr1_node = dst_copy; Node *lr2_node = src_def; - if( lr1 > lr2 ) { + if (lr1 > lr2) { uint tmp = lr1; lr1 = lr2; lr2 = tmp; lr1_node = src_def; lr2_node = dst_copy; } @@ -916,17 +799,5 @@ PhaseChaitin::_conserv_coalesce++; // Collect stats on success continue; } - - /* do not attempt pairs. About 1/2 of all pairs can be removed by - post-alloc. The other set are too few to bother. - Node *copy2 = copy1->in(idx1); - uint idx2 = copy2->is_Copy(); - if( !idx2 ) continue; - if( copy_copy(copy1,copy2,b,i) ) { - i--; // Retry, same location in block - PhaseChaitin::_conserv_coalesce_pair++; // Collect stats on success - continue; - } - */ } }
--- a/src/share/vm/opto/coalesce.hpp Mon Apr 15 16:20:05 2013 -0700 +++ b/src/share/vm/opto/coalesce.hpp Tue Apr 16 10:08:41 2013 +0200 @@ -41,23 +41,25 @@ public: // Coalesce copies - PhaseCoalesce( PhaseChaitin &chaitin ) : Phase(Coalesce), _phc(chaitin) { } + PhaseCoalesce(PhaseChaitin &phc) + : Phase(Coalesce) + , _phc(phc) {} virtual void verify() = 0; // Coalesce copies - void coalesce_driver( ); + void coalesce_driver(); // Coalesce copies in this block - virtual void coalesce( Block *b ) = 0; + virtual void coalesce(Block *b) = 0; // Attempt to coalesce live ranges defined by these 2 - void combine_these_two( Node *n1, Node *n2 ); + void combine_these_two(Node *n1, Node *n2); - LRG &lrgs( uint lidx ) { return _phc.lrgs(lidx); } + LRG &lrgs(uint lidx) { return _phc.lrgs(lidx); } #ifndef PRODUCT // Dump internally name - void dump( Node *n ) const; + void dump(Node *n) const; // Dump whole shebang void dump() const; #endif
--- a/src/share/vm/opto/compile.cpp Mon Apr 15 16:20:05 2013 -0700 +++ b/src/share/vm/opto/compile.cpp Tue Apr 16 10:08:41 2013 +0200 @@ -2127,22 +2127,19 @@ } NOT_PRODUCT( verify_graph_edges(); ) - PhaseChaitin regalloc(unique(),cfg,m); + PhaseChaitin regalloc(unique(), cfg, m); _regalloc = ®alloc; { TracePhase t2("regalloc", &_t_registerAllocation, true); - // Perform any platform dependent preallocation actions. This is used, - // for example, to avoid taking an implicit null pointer exception - // using the frame pointer on win95. - _regalloc->pd_preallocate_hook(); - // Perform register allocation. After Chaitin, use-def chains are // no longer accurate (at spill code) and so must be ignored. // Node->LRG->reg mappings are still accurate. _regalloc->Register_Allocate(); // Bail out if the allocator builds too many nodes - if (failing()) return; + if (failing()) { + return; + } } // Prior to register allocation we kept empty basic blocks in case the @@ -2160,9 +2157,6 @@ cfg.fixup_flow(); } - // Perform any platform dependent postallocation verifications. - debug_only( _regalloc->pd_postallocate_verify_hook(); ) - // Apply peephole optimizations if( OptoPeephole ) { NOT_PRODUCT( TracePhase t2("peephole", &_t_peephole, TimeCompiler); )
--- a/src/share/vm/opto/idealGraphPrinter.cpp Mon Apr 15 16:20:05 2013 -0700 +++ b/src/share/vm/opto/idealGraphPrinter.cpp Tue Apr 16 10:08:41 2013 +0200 @@ -616,7 +616,7 @@ buffer[0] = 0; _chaitin->dump_register(node, buffer); print_prop("reg", buffer); - print_prop("lrg", _chaitin->n2lidx(node)); + print_prop("lrg", _chaitin->_lrg_map.live_range_id(node)); } node->_in_dump_cnt--;
--- a/src/share/vm/opto/ifg.cpp Mon Apr 15 16:20:05 2013 -0700 +++ b/src/share/vm/opto/ifg.cpp Tue Apr 16 10:08:41 2013 +0200 @@ -286,15 +286,14 @@ uint idx; uint last = 0; while ((idx = elements.next()) != 0) { - assert( idx != i, "Must have empty diagonal"); - assert( pc->Find_const(idx) == idx, "Must not need Find" ); - assert( _adjs[idx].member(i), "IFG not square" ); - assert( !(*_yanked)[idx], "No yanked neighbors" ); - assert( last < idx, "not sorted increasing"); + assert(idx != i, "Must have empty diagonal"); + assert(pc->_lrg_map.find_const(idx) == idx, "Must not need Find"); + assert(_adjs[idx].member(i), "IFG not square"); + assert(!(*_yanked)[idx], "No yanked neighbors"); + assert(last < idx, "not sorted increasing"); last = idx; } - assert( !lrgs(i)._degree_valid || - effective_degree(i) == lrgs(i).degree(), "degree is valid but wrong" ); + assert(!lrgs(i)._degree_valid || effective_degree(i) == lrgs(i).degree(), "degree is valid but wrong"); } } #endif @@ -342,10 +341,10 @@ Node *n = b->_nodes[j-1]; // Get value being defined - uint r = n2lidx(n); + uint r = _lrg_map.live_range_id(n); // Some special values do not allocate - if( r ) { + if (r) { // Remove from live-out set liveout->remove(r); @@ -353,16 +352,19 @@ // Copies do not define a new value and so do not interfere. // Remove the copies source from the liveout set before interfering. uint idx = n->is_Copy(); - if( idx ) liveout->remove( n2lidx(n->in(idx)) ); + if (idx) { + liveout->remove(_lrg_map.live_range_id(n->in(idx))); + } // Interfere with everything live - interfere_with_live( r, liveout ); + interfere_with_live(r, liveout); } // Make all inputs live - if( !n->is_Phi() ) { // Phi function uses come from prior block - for( uint k = 1; k < n->req(); k++ ) - liveout->insert( n2lidx(n->in(k)) ); + if (!n->is_Phi()) { // Phi function uses come from prior block + for(uint k = 1; k < n->req(); k++) { + liveout->insert(_lrg_map.live_range_id(n->in(k))); + } } // 2-address instructions always have the defined value live @@ -394,11 +396,12 @@ n->set_req( 2, tmp ); } // Defined value interferes with all inputs - uint lidx = n2lidx(n->in(idx)); - for( uint k = 1; k < n->req(); k++ ) { - uint kidx = n2lidx(n->in(k)); - if( kidx != lidx ) - _ifg->add_edge( r, kidx ); + uint lidx = _lrg_map.live_range_id(n->in(idx)); + for (uint k = 1; k < n->req(); k++) { + uint kidx = _lrg_map.live_range_id(n->in(k)); + if (kidx != lidx) { + _ifg->add_edge(r, kidx); + } } } } // End of forall instructions in block @@ -542,10 +545,10 @@ Node *n = b->_nodes[j - 1]; // Get value being defined - uint r = n2lidx(n); + uint r = _lrg_map.live_range_id(n); // Some special values do not allocate - if( r ) { + if(r) { // A DEF normally costs block frequency; rematerialized values are // removed from the DEF sight, so LOWER costs here. lrgs(r)._cost += n->rematerialize() ? 0 : b->_freq; @@ -556,9 +559,11 @@ Node *def = n->in(0); if( !n->is_Proj() || // Could also be a flags-projection of a dead ADD or such. - (n2lidx(def) && !liveout.member(n2lidx(def)) ) ) { + (_lrg_map.live_range_id(def) && !liveout.member(_lrg_map.live_range_id(def)))) { b->_nodes.remove(j - 1); - if( lrgs(r)._def == n ) lrgs(r)._def = 0; + if (lrgs(r)._def == n) { + lrgs(r)._def = 0; + } n->disconnect_inputs(NULL, C); _cfg._bbs.map(n->_idx,NULL); n->replace_by(C->top()); @@ -570,7 +575,7 @@ // Fat-projections kill many registers which cannot be used to // hold live ranges. - if( lrgs(r)._fat_proj ) { + if (lrgs(r)._fat_proj) { // Count the int-only registers RegMask itmp = lrgs(r).mask(); itmp.AND(*Matcher::idealreg2regmask[Op_RegI]); @@ -636,12 +641,12 @@ // Copies do not define a new value and so do not interfere. // Remove the copies source from the liveout set before interfering. uint idx = n->is_Copy(); - if( idx ) { - uint x = n2lidx(n->in(idx)); - if( liveout.remove( x ) ) { + if (idx) { + uint x = _lrg_map.live_range_id(n->in(idx)); + if (liveout.remove(x)) { lrgs(x)._area -= cost; // Adjust register pressure. - lower_pressure( &lrgs(x), j-1, b, pressure, hrp_index ); + lower_pressure(&lrgs(x), j-1, b, pressure, hrp_index); assert( pressure[0] == count_int_pressure (&liveout), "" ); assert( pressure[1] == count_float_pressure(&liveout), "" ); } @@ -727,18 +732,21 @@ // the flags and assumes it's dead. This keeps the (useless) // flag-setting behavior alive while also keeping the (useful) // memory update effect. - for( uint k = ((n->Opcode() == Op_SCMemProj) ? 0:1); k < n->req(); k++ ) { + for (uint k = ((n->Opcode() == Op_SCMemProj) ? 0:1); k < n->req(); k++) { Node *def = n->in(k); - uint x = n2lidx(def); - if( !x ) continue; + uint x = _lrg_map.live_range_id(def); + if (!x) { + continue; + } LRG &lrg = lrgs(x); // No use-side cost for spilling debug info - if( k < debug_start ) + if (k < debug_start) { // A USE costs twice block frequency (once for the Load, once // for a Load-delay). Rematerialized uses only cost once. lrg._cost += (def->rematerialize() ? b->_freq : (b->_freq + b->_freq)); + } // It is live now - if( liveout.insert( x ) ) { + if (liveout.insert(x)) { // Newly live things assumed live from here to top of block lrg._area += cost; // Adjust register pressure
--- a/src/share/vm/opto/live.cpp Mon Apr 15 16:20:05 2013 -0700 +++ b/src/share/vm/opto/live.cpp Tue Apr 16 10:08:41 2013 +0200 @@ -44,7 +44,7 @@ // block is put on the worklist. // The locally live-in stuff is computed once and added to predecessor // live-out sets. This separate compilation is done in the outer loop below. -PhaseLive::PhaseLive( const PhaseCFG &cfg, LRG_List &names, Arena *arena ) : Phase(LIVE), _cfg(cfg), _names(names), _arena(arena), _live(0) { +PhaseLive::PhaseLive( const PhaseCFG &cfg, const LRG_List &names, Arena *arena ) : Phase(LIVE), _cfg(cfg), _names(names), _arena(arena), _live(0) { } void PhaseLive::compute(uint maxlrg) {
--- a/src/share/vm/opto/live.hpp Mon Apr 15 16:20:05 2013 -0700 +++ b/src/share/vm/opto/live.hpp Tue Apr 16 10:08:41 2013 +0200 @@ -80,7 +80,7 @@ Block_List *_worklist; // Worklist for iterative solution const PhaseCFG &_cfg; // Basic blocks - LRG_List &_names; // Mapping from Nodes to live ranges + const LRG_List &_names; // Mapping from Nodes to live ranges uint _maxlrg; // Largest live-range number Arena *_arena; @@ -91,7 +91,7 @@ void add_liveout( Block *p, IndexSet *lo, VectorSet &first_pass ); public: - PhaseLive( const PhaseCFG &cfg, LRG_List &names, Arena *arena ); + PhaseLive(const PhaseCFG &cfg, const LRG_List &names, Arena *arena); ~PhaseLive() {} // Compute liveness info void compute(uint maxlrg);
--- a/src/share/vm/opto/postaloc.cpp Mon Apr 15 16:20:05 2013 -0700 +++ b/src/share/vm/opto/postaloc.cpp Tue Apr 16 10:08:41 2013 +0200 @@ -56,7 +56,7 @@ int i; for( i=0; i < limit; i++ ) { if( def->is_Proj() && def->in(0)->is_Start() && - _matcher.is_save_on_entry(lrgs(n2lidx(def)).reg()) ) + _matcher.is_save_on_entry(lrgs(_lrg_map.live_range_id(def)).reg())) return true; // Direct use of callee-save proj if( def->is_Copy() ) // Copies carry value through def = def->in(def->is_Copy()); @@ -83,7 +83,7 @@ // Count 1 if deleting an instruction from the current block if( oldb == current_block ) blk_adjust++; _cfg._bbs.map(old->_idx,NULL); - OptoReg::Name old_reg = lrgs(n2lidx(old)).reg(); + OptoReg::Name old_reg = lrgs(_lrg_map.live_range_id(old)).reg(); if( regnd && (*regnd)[old_reg]==old ) { // Instruction is currently available? value->map(old_reg,NULL); // Yank from value/regnd maps regnd->map(old_reg,NULL); // This register's value is now unknown @@ -164,7 +164,7 @@ // Not every pair of physical registers are assignment compatible, // e.g. on sparc floating point registers are not assignable to integer // registers. - const LRG &def_lrg = lrgs(n2lidx(def)); + const LRG &def_lrg = lrgs(_lrg_map.live_range_id(def)); OptoReg::Name def_reg = def_lrg.reg(); const RegMask &use_mask = n->in_RegMask(idx); bool can_use = ( RegMask::can_represent(def_reg) ? (use_mask.Member(def_reg) != 0) @@ -209,11 +209,12 @@ // Skip through any number of copies (that don't mod oop-i-ness) Node *PhaseChaitin::skip_copies( Node *c ) { int idx = c->is_Copy(); - uint is_oop = lrgs(n2lidx(c))._is_oop; + uint is_oop = lrgs(_lrg_map.live_range_id(c))._is_oop; while (idx != 0) { guarantee(c->in(idx) != NULL, "must not resurrect dead copy"); - if (lrgs(n2lidx(c->in(idx)))._is_oop != is_oop) + if (lrgs(_lrg_map.live_range_id(c->in(idx)))._is_oop != is_oop) { break; // casting copy, not the same value + } c = c->in(idx); idx = c->is_Copy(); } @@ -225,8 +226,8 @@ int PhaseChaitin::elide_copy( Node *n, int k, Block *current_block, Node_List &value, Node_List ®nd, bool can_change_regs ) { int blk_adjust = 0; - uint nk_idx = n2lidx(n->in(k)); - OptoReg::Name nk_reg = lrgs(nk_idx ).reg(); + uint nk_idx = _lrg_map.live_range_id(n->in(k)); + OptoReg::Name nk_reg = lrgs(nk_idx).reg(); // Remove obvious same-register copies Node *x = n->in(k); @@ -234,9 +235,13 @@ while( (idx=x->is_Copy()) != 0 ) { Node *copy = x->in(idx); guarantee(copy != NULL, "must not resurrect dead copy"); - if( lrgs(n2lidx(copy)).reg() != nk_reg ) break; + if(lrgs(_lrg_map.live_range_id(copy)).reg() != nk_reg) { + break; + } blk_adjust += use_prior_register(n,k,copy,current_block,value,regnd); - if( n->in(k) != copy ) break; // Failed for some cutout? + if (n->in(k) != copy) { + break; // Failed for some cutout? + } x = copy; // Progress, try again } @@ -256,7 +261,7 @@ if (val == x && nk_idx != 0 && regnd[nk_reg] != NULL && regnd[nk_reg] != x && - n2lidx(x) == n2lidx(regnd[nk_reg])) { + _lrg_map.live_range_id(x) == _lrg_map.live_range_id(regnd[nk_reg])) { // When rematerialzing nodes and stretching lifetimes, the // allocator will reuse the original def for multidef LRG instead // of the current reaching def because it can't know it's safe to @@ -270,7 +275,7 @@ if (val == x) return blk_adjust; // No progress? int n_regs = RegMask::num_registers(val->ideal_reg()); - uint val_idx = n2lidx(val); + uint val_idx = _lrg_map.live_range_id(val); OptoReg::Name val_reg = lrgs(val_idx).reg(); // See if it happens to already be in the correct register! @@ -499,12 +504,12 @@ for( j = 1; j < phi_dex; j++ ) { uint k; Node *phi = b->_nodes[j]; - uint pidx = n2lidx(phi); - OptoReg::Name preg = lrgs(n2lidx(phi)).reg(); + uint pidx = _lrg_map.live_range_id(phi); + OptoReg::Name preg = lrgs(_lrg_map.live_range_id(phi)).reg(); // Remove copies remaining on edges. Check for junk phi. Node *u = NULL; - for( k=1; k<phi->req(); k++ ) { + for (k = 1; k < phi->req(); k++) { Node *x = phi->in(k); if( phi != x && u != x ) // Found a different input u = u ? NodeSentinel : x; // Capture unique input, or NodeSentinel for 2nd input @@ -555,10 +560,10 @@ // alive and well at the use (or else the allocator fubar'd). Take // advantage of this info to set a reaching def for the use-reg. uint k; - for( k = 1; k < n->req(); k++ ) { + for (k = 1; k < n->req(); k++) { Node *def = n->in(k); // n->in(k) is a USE; def is the DEF for this USE guarantee(def != NULL, "no disconnected nodes at this point"); - uint useidx = n2lidx(def); // useidx is the live range index for this USE + uint useidx = _lrg_map.live_range_id(def); // useidx is the live range index for this USE if( useidx ) { OptoReg::Name ureg = lrgs(useidx).reg(); @@ -566,7 +571,7 @@ int idx; // Skip occasional useless copy while( (idx=def->is_Copy()) != 0 && def->in(idx) != NULL && // NULL should not happen - ureg == lrgs(n2lidx(def->in(idx))).reg() ) + ureg == lrgs(_lrg_map.live_range_id(def->in(idx))).reg()) def = def->in(idx); Node *valdef = skip_copies(def); // tighten up val through non-useless copies value.map(ureg,valdef); // record improved reaching-def info @@ -594,8 +599,10 @@ j -= elide_copy( n, k, b, value, regnd, two_adr!=k ); // Unallocated Nodes define no registers - uint lidx = n2lidx(n); - if( !lidx ) continue; + uint lidx = _lrg_map.live_range_id(n); + if (!lidx) { + continue; + } // Update the register defined by this instruction OptoReg::Name nreg = lrgs(lidx).reg();
--- a/src/share/vm/opto/reg_split.cpp Mon Apr 15 16:20:05 2013 -0700 +++ b/src/share/vm/opto/reg_split.cpp Tue Apr 16 10:08:41 2013 +0200 @@ -318,9 +318,13 @@ for( uint i = 1; i < def->req(); i++ ) { Node *in = def->in(i); // Check for single-def (LRG cannot redefined) - uint lidx = n2lidx(in); - if( lidx >= _maxlrg ) continue; // Value is a recent spill-copy - if (lrgs(lidx).is_singledef()) continue; + uint lidx = _lrg_map.live_range_id(in); + if (lidx >= _lrg_map.max_lrg_id()) { + continue; // Value is a recent spill-copy + } + if (lrgs(lidx).is_singledef()) { + continue; + } Block *b_def = _cfg._bbs[def->_idx]; int idx_def = b_def->find_node(def); @@ -344,26 +348,28 @@ if( spill->req() > 1 ) { for( uint i = 1; i < spill->req(); i++ ) { Node *in = spill->in(i); - uint lidx = Find_id(in); + uint lidx = _lrg_map.find_id(in); // Walk backwards thru spill copy node intermediates if (walkThru) { - while ( in->is_SpillCopy() && lidx >= _maxlrg ) { + while (in->is_SpillCopy() && lidx >= _lrg_map.max_lrg_id()) { in = in->in(1); - lidx = Find_id(in); + lidx = _lrg_map.find_id(in); } - if (lidx < _maxlrg && lrgs(lidx).is_multidef()) { + if (lidx < _lrg_map.max_lrg_id() && lrgs(lidx).is_multidef()) { // walkThru found a multidef LRG, which is unsafe to use, so // just keep the original def used in the clone. in = spill->in(i); - lidx = Find_id(in); + lidx = _lrg_map.find_id(in); } } - if( lidx < _maxlrg && lrgs(lidx).reg() >= LRG::SPILL_REG ) { + if (lidx < _lrg_map.max_lrg_id() && lrgs(lidx).reg() >= LRG::SPILL_REG) { Node *rdef = Reachblock[lrg2reach[lidx]]; - if( rdef ) spill->set_req(i,rdef); + if (rdef) { + spill->set_req(i, rdef); + } } } } @@ -382,7 +388,7 @@ #endif // See if the cloned def kills any flags, and copy those kills as well uint i = insidx+1; - if( clone_projs( b, i, def, spill, maxlrg ) ) { + if( clone_projs( b, i, def, spill, maxlrg) ) { // Adjust the point where we go hi-pressure if( i <= b->_ihrp_index ) b->_ihrp_index++; if( i <= b->_fhrp_index ) b->_fhrp_index++; @@ -424,17 +430,25 @@ //------------------------------prompt_use--------------------------------- // True if lidx is used before any real register is def'd in the block bool PhaseChaitin::prompt_use( Block *b, uint lidx ) { - if( lrgs(lidx)._was_spilled2 ) return false; + if (lrgs(lidx)._was_spilled2) { + return false; + } // Scan block for 1st use. for( uint i = 1; i <= b->end_idx(); i++ ) { Node *n = b->_nodes[i]; // Ignore PHI use, these can be up or down - if( n->is_Phi() ) continue; - for( uint j = 1; j < n->req(); j++ ) - if( Find_id(n->in(j)) == lidx ) + if (n->is_Phi()) { + continue; + } + for (uint j = 1; j < n->req(); j++) { + if (_lrg_map.find_id(n->in(j)) == lidx) { return true; // Found 1st use! - if( n->out_RegMask().is_NotEmpty() ) return false; + } + } + if (n->out_RegMask().is_NotEmpty()) { + return false; + } } return false; } @@ -464,23 +478,23 @@ bool u1, u2, u3; Block *b, *pred; PhiNode *phi; - GrowableArray<uint> lidxs(split_arena, _maxlrg, 0, 0); + GrowableArray<uint> lidxs(split_arena, maxlrg, 0, 0); // Array of counters to count splits per live range - GrowableArray<uint> splits(split_arena, _maxlrg, 0, 0); + GrowableArray<uint> splits(split_arena, maxlrg, 0, 0); #define NEW_SPLIT_ARRAY(type, size)\ (type*) split_arena->allocate_bytes((size) * sizeof(type)) //----------Setup Code---------- // Create a convenient mapping from lrg numbers to reaches/leaves indices - uint *lrg2reach = NEW_SPLIT_ARRAY( uint, _maxlrg ); + uint *lrg2reach = NEW_SPLIT_ARRAY(uint, maxlrg); // Keep track of DEFS & Phis for later passes defs = new Node_List(); phis = new Node_List(); // Gather info on which LRG's are spilling, and build maps - for( bidx = 1; bidx < _maxlrg; bidx++ ) { - if( lrgs(bidx).alive() && lrgs(bidx).reg() >= LRG::SPILL_REG ) { + for (bidx = 1; bidx < maxlrg; bidx++) { + if (lrgs(bidx).alive() && lrgs(bidx).reg() >= LRG::SPILL_REG) { assert(!lrgs(bidx).mask().is_AllStack(),"AllStack should color"); lrg2reach[bidx] = spill_cnt; spill_cnt++; @@ -629,7 +643,7 @@ break; } // must be looking at a phi - if( Find_id(n1) == lidxs.at(slidx) ) { + if (_lrg_map.find_id(n1) == lidxs.at(slidx)) { // found the necessary phi needs_phi = false; has_phi = true; @@ -651,11 +665,11 @@ Reachblock[slidx] = phi; // add node to block & node_to_block mapping - insert_proj( b, insidx++, phi, maxlrg++ ); + insert_proj(b, insidx++, phi, maxlrg++); non_phi++; // Reset new phi's mapping to be the spilling live range - _names.map(phi->_idx, lidx); - assert(Find_id(phi) == lidx,"Bad update on Union-Find mapping"); + _lrg_map.map(phi->_idx, lidx); + assert(_lrg_map.find_id(phi) == lidx, "Bad update on Union-Find mapping"); } // end if not found correct phi // Here you have either found or created the Phi, so record it assert(phi != NULL,"Must have a Phi Node here"); @@ -721,12 +735,12 @@ for( insidx = 1; insidx <= b->end_idx(); insidx++ ) { Node *n = b->_nodes[insidx]; // Find the defining Node's live range index - uint defidx = Find_id(n); + uint defidx = _lrg_map.find_id(n); uint cnt = n->req(); - if( n->is_Phi() ) { + if (n->is_Phi()) { // Skip phi nodes after removing dead copies. - if( defidx < _maxlrg ) { + if (defidx < _lrg_map.max_lrg_id()) { // Check for useless Phis. These appear if we spill, then // coalesce away copies. Dont touch Phis in spilling live // ranges; they are busy getting modifed in this pass. @@ -744,8 +758,8 @@ } } assert( u, "at least 1 valid input expected" ); - if( i >= cnt ) { // Found one unique input - assert(Find_id(n) == Find_id(u), "should be the same lrg"); + if (i >= cnt) { // Found one unique input + assert(_lrg_map.find_id(n) == _lrg_map.find_id(u), "should be the same lrg"); n->replace_by(u); // Then replace with unique input n->disconnect_inputs(NULL, C); b->_nodes.remove(insidx); @@ -793,16 +807,24 @@ while( insert_point > 0 ) { Node *n = b->_nodes[insert_point]; // Hit top of block? Quit going backwards - if( n->is_Phi() ) break; + if (n->is_Phi()) { + break; + } // Found a def? Better split after it. - if( n2lidx(n) == lidx ) break; + if (_lrg_map.live_range_id(n) == lidx) { + break; + } // Look for a use uint i; - for( i = 1; i < n->req(); i++ ) - if( n2lidx(n->in(i)) == lidx ) + for( i = 1; i < n->req(); i++ ) { + if (_lrg_map.live_range_id(n->in(i)) == lidx) { break; + } + } // Found a use? Better split after it. - if( i < n->req() ) break; + if (i < n->req()) { + break; + } insert_point--; } uint orig_eidx = b->end_idx(); @@ -812,8 +834,9 @@ return 0; } // Spill of NULL check mem op goes into the following block. - if (b->end_idx() > orig_eidx) + if (b->end_idx() > orig_eidx) { insidx++; + } } // This is a new DEF, so update UP UPblock[slidx] = false; @@ -832,13 +855,13 @@ } // end if crossing HRP Boundry // If the LRG index is oob, then this is a new spillcopy, skip it. - if( defidx >= _maxlrg ) { + if (defidx >= _lrg_map.max_lrg_id()) { continue; } LRG &deflrg = lrgs(defidx); uint copyidx = n->is_Copy(); // Remove coalesced copy from CFG - if( copyidx && defidx == n2lidx(n->in(copyidx)) ) { + if (copyidx && defidx == _lrg_map.live_range_id(n->in(copyidx))) { n->replace_by( n->in(copyidx) ); n->set_req( copyidx, NULL ); b->_nodes.remove(insidx--); @@ -864,13 +887,13 @@ // If inpidx > old_last, then one of these new inputs is being // handled. Skip the derived part of the pair, but process // the base like any other input. - if( inpidx > old_last && ((inpidx - oopoff) & 1) == DERIVED ) { + if (inpidx > old_last && ((inpidx - oopoff) & 1) == DERIVED) { continue; // skip derived_debug added below } // Get lidx of input - uint useidx = Find_id(n->in(inpidx)); + uint useidx = _lrg_map.find_id(n->in(inpidx)); // Not a brand-new split, and it is a spill use - if( useidx < _maxlrg && lrgs(useidx).reg() >= LRG::SPILL_REG ) { + if (useidx < _lrg_map.max_lrg_id() && lrgs(useidx).reg() >= LRG::SPILL_REG) { // Check for valid reaching DEF slidx = lrg2reach[useidx]; Node *def = Reachblock[slidx]; @@ -886,7 +909,7 @@ if (def == NULL || C->check_node_count(NodeLimitFudgeFactor, out_of_nodes)) { return 0; } - _names.extend(def->_idx,0); + _lrg_map.extend(def->_idx, 0); _cfg._bbs.map(def->_idx,b); n->set_req(inpidx, def); continue; @@ -1186,10 +1209,10 @@ // ********** Split Left Over Mem-Mem Moves ********** // Check for mem-mem copies and split them now. Do not do this // to copies about to be spilled; they will be Split shortly. - if( copyidx ) { + if (copyidx) { Node *use = n->in(copyidx); - uint useidx = Find_id(use); - if( useidx < _maxlrg && // This is not a new split + uint useidx = _lrg_map.find_id(use); + if (useidx < _lrg_map.max_lrg_id() && // This is not a new split OptoReg::is_stack(deflrg.reg()) && deflrg.reg() < LRG::SPILL_REG ) { // And DEF is from stack LRG &uselrg = lrgs(useidx); @@ -1228,7 +1251,7 @@ uint member; IndexSetIterator isi(liveout); while ((member = isi.next()) != 0) { - assert(defidx != Find_const(member), "Live out member has not been compressed"); + assert(defidx != _lrg_map.find_const(member), "Live out member has not been compressed"); } #endif Reachblock[slidx] = NULL; @@ -1261,7 +1284,7 @@ assert(phi->is_Phi(),"This list must only contain Phi Nodes"); Block *b = _cfg._bbs[phi->_idx]; // Grab the live range number - uint lidx = Find_id(phi); + uint lidx = _lrg_map.find_id(phi); uint slidx = lrg2reach[lidx]; // Update node to lidx map new_lrg(phi, maxlrg++); @@ -1296,11 +1319,13 @@ int insert = pred->end_idx(); while (insert >= 1 && pred->_nodes[insert - 1]->is_SpillCopy() && - Find(pred->_nodes[insert - 1]) >= lrgs_before_phi_split) { + _lrg_map.find(pred->_nodes[insert - 1]) >= lrgs_before_phi_split) { insert--; } - def = split_Rematerialize( def, pred, insert, maxlrg, splits, slidx, lrg2reach, Reachblock, false ); - if( !def ) return 0; // Bail out + def = split_Rematerialize(def, pred, insert, maxlrg, splits, slidx, lrg2reach, Reachblock, false); + if (!def) { + return 0; // Bail out + } } // Update the Phi's input edge array phi->set_req(i,def); @@ -1316,7 +1341,7 @@ } // End for all inputs to the Phi } // End for all Phi Nodes // Update _maxlrg to save Union asserts - _maxlrg = maxlrg; + _lrg_map.set_max_lrg_id(maxlrg); //----------PASS 3---------- @@ -1328,47 +1353,51 @@ for( uint i = 1; i < phi->req(); i++ ) { // Grab the input node Node *n = phi->in(i); - assert( n, "" ); - uint lidx = Find(n); - uint pidx = Find(phi); - if( lidx < pidx ) + assert(n, "node should exist"); + uint lidx = _lrg_map.find(n); + uint pidx = _lrg_map.find(phi); + if (lidx < pidx) { Union(n, phi); - else if( lidx > pidx ) + } + else if(lidx > pidx) { Union(phi, n); + } } // End for all inputs to the Phi Node } // End for all Phi Nodes // Now union all two address instructions - for( insidx = 0; insidx < defs->size(); insidx++ ) { + for (insidx = 0; insidx < defs->size(); insidx++) { // Grab the def n1 = defs->at(insidx); // Set new lidx for DEF & handle 2-addr instructions - if( n1->is_Mach() && ((twoidx = n1->as_Mach()->two_adr()) != 0) ) { - assert( Find(n1->in(twoidx)) < maxlrg,"Assigning bad live range index"); + if (n1->is_Mach() && ((twoidx = n1->as_Mach()->two_adr()) != 0)) { + assert(_lrg_map.find(n1->in(twoidx)) < maxlrg,"Assigning bad live range index"); // Union the input and output live ranges - uint lr1 = Find(n1); - uint lr2 = Find(n1->in(twoidx)); - if( lr1 < lr2 ) + uint lr1 = _lrg_map.find(n1); + uint lr2 = _lrg_map.find(n1->in(twoidx)); + if (lr1 < lr2) { Union(n1, n1->in(twoidx)); - else if( lr1 > lr2 ) + } + else if (lr1 > lr2) { Union(n1->in(twoidx), n1); + } } // End if two address } // End for all defs // DEBUG #ifdef ASSERT // Validate all live range index assignments - for( bidx = 0; bidx < _cfg._num_blocks; bidx++ ) { + for (bidx = 0; bidx < _cfg._num_blocks; bidx++) { b = _cfg._blocks[bidx]; - for( insidx = 0; insidx <= b->end_idx(); insidx++ ) { + for (insidx = 0; insidx <= b->end_idx(); insidx++) { Node *n = b->_nodes[insidx]; - uint defidx = Find(n); - assert(defidx < _maxlrg,"Bad live range index in Split"); + uint defidx = _lrg_map.find(n); + assert(defidx < _lrg_map.max_lrg_id(), "Bad live range index in Split"); assert(defidx < maxlrg,"Bad live range index in Split"); } } // Issue a warning if splitting made no progress int noprogress = 0; - for( slidx = 0; slidx < spill_cnt; slidx++ ) { - if( PrintOpto && WizardMode && splits.at(slidx) == 0 ) { + for (slidx = 0; slidx < spill_cnt; slidx++) { + if (PrintOpto && WizardMode && splits.at(slidx) == 0) { tty->print_cr("Failed to split live range %d", lidxs.at(slidx)); //BREAKPOINT; }
--- a/src/share/vm/opto/regalloc.hpp Mon Apr 15 16:20:05 2013 -0700 +++ b/src/share/vm/opto/regalloc.hpp Tue Apr 16 10:08:41 2013 +0200 @@ -113,7 +113,7 @@ OptoReg::Name offset2reg( int stk_offset ) const; // Get the register encoding associated with the Node - int get_encode( const Node *n ) const { + int get_encode(const Node *n) const { assert( n->_idx < _node_regs_max_index, "Exceeded _node_regs array"); OptoReg::Name first = _node_regs[n->_idx].first(); OptoReg::Name second = _node_regs[n->_idx].second(); @@ -122,15 +122,6 @@ return Matcher::_regEncode[first]; } - // Platform dependent hook for actions prior to allocation - void pd_preallocate_hook(); - -#ifdef ASSERT - // Platform dependent hook for verification after allocation. Will - // only get called when compiling with asserts. - void pd_postallocate_verify_hook(); -#endif - #ifndef PRODUCT static int _total_framesize; static int _max_framesize;
--- a/src/share/vm/runtime/vmStructs.cpp Mon Apr 15 16:20:05 2013 -0700 +++ b/src/share/vm/runtime/vmStructs.cpp Tue Apr 16 10:08:41 2013 +0200 @@ -1115,7 +1115,6 @@ c2_nonstatic_field(PhaseChaitin, _lo_stk_degree, uint) \ c2_nonstatic_field(PhaseChaitin, _hi_degree, uint) \ c2_nonstatic_field(PhaseChaitin, _simplified, uint) \ - c2_nonstatic_field(PhaseChaitin, _maxlrg, uint) \ \ c2_nonstatic_field(Block, _nodes, Node_List) \ c2_nonstatic_field(Block, _succs, Block_Array) \