graal-compiler: src/share/vm/opto/chaitin.cpp comparison

comparison src/share/vm/opto/chaitin.cpp @ 10111: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	2aff40cb4703
children	693e4d04fd09

comparison

equal deleted inserted replaced

-:1c6887c9afaa
+:8373c19be854
 _lidxs[nidx] = lidx;
 }
 #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,
 #ifndef PRODUCT
 print_chaitin_statistics
 #else
 NULL
 #endif
-),
+)
-_names(unique), _uf_map(unique),
+, _lrg_map(unique)
-_maxlrg(0), _live(0),
+, _live(0)
-_spilled_once(Thread::current()->resource_area()),
+, _spilled_once(Thread::current()->resource_area())
-_spilled_twice(Thread::current()->resource_area()),
+, _spilled_twice(Thread::current()->resource_area())
-_lo_degree(0), _lo_stk_degree(0), _hi_degree(0), _simplified(0),
+, _lo_degree(0), _lo_stk_degree(0), _hi_degree(0), _simplified(0)
-_oldphi(unique)
+, _oldphi(unique)
 #ifndef PRODUCT
 , _trace_spilling(TraceSpilling || C->method_has_option("TraceSpilling"))
 #endif
 {
 NOT_PRODUCT( Compile::TracePhase t3("ctorChaitin", &_t_ctorChaitin, TimeCompiler); )
 _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
 double  cutoff = BLOCK_FREQUENCY(1.0); // Cutoff for high frequency bucket
 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++ ) {
+for (uint i = 0; i < NUMBUCKS; i++) {
-buckets[i] = NEW_RESOURCE_ARRAY( Block *, _cfg._num_blocks );
+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 (uint i = 0; i < _cfg._num_blocks; i++) {
-for( j = 0; j < NUMBUCKS; j++ ) {
+for (uint j = 0; j < NUMBUCKS; j++) {
-if( (j == NUMBUCKS-1) || (_cfg._blocks[i]->_freq > buckval[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 (uint i = 0; i < NUMBUCKS; i++) {
-for( j = 0; j < buckcnt[i]; j++ ) {
+for (uint j = 0; j < buckcnt[i]; j++) {
 _blks[blkcnt++] = buckets[i][j];
 }
 }
 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
 // Need live-ness for the IFG; need the IFG for coalescing.  If the
 // liveness is JUST for coalescing, then I can get some mileage by renaming
 // 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
 // ranges or inserting copies.  For the moment, we insert "virtual copies"
 {
 NOT_PRODUCT( Compile::TracePhase t3("computeLive", &_t_computeLive, TimeCompiler); )
 _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
 }
 // Base pointers are currently "used" by instructions which define new
 // derived pointers.  This makes base pointers live up to the where the
 // derived pointer is made, but not beyond.  Really, they need to be live
 // 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) ) {
+if (stretch_base_pointer_live_ranges(&live_arena)) {
-NOT_PRODUCT( Compile::TracePhase t3("computeLive (sbplr)", &_t_computeLive, TimeCompiler); )
+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);
+ifg.init(_lrg_map.max_lrg_id());
-gather_lrg_masks( false );
+gather_lrg_masks(false);
-live.compute( _maxlrg );
+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
 // coalesced get manifested as actual copies
 {
 // meaning I can visit all the Nodes neighbors less than a Node in time
 // O(# of neighbors), but I have to visit all the Nodes greater than a
 // given Node and search them for an instance, i.e., time O(#MaxLRG)).
 _ifg->SquareUp();
-PhaseAggressiveCoalesce coalesce( *this );
+PhaseAggressiveCoalesce coalesce(*this);
-coalesce.coalesce_driver( );
+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);
 }
 {
 NOT_PRODUCT( Compile::TracePhase t3("computeLive", &_t_computeLive, TimeCompiler); )
 _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 (must_spill) {
-if( !_maxlrg ) return;
+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;
+if (C->failing()) {
-_maxlrg = Split(_maxlrg, &split_arena);  // Split spilling LRG everywhere
+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
 {
 NOT_PRODUCT( Compile::TracePhase t3("computeLive", &_t_computeLive, TimeCompiler); )
 _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);
 #endif
 } else {
 C->record_method_not_compilable("failed spill-split-recycle sanity check");
 return;
 }
 }
-if( !_maxlrg ) return;
+if (!_lrg_map.max_lrg_id()) {
-_maxlrg = Split(_maxlrg, &split_arena);  // Split spilling LRG everywhere
+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");
+C->check_node_count(2 * NodeLimitFudgeFactor, "out of nodes after split");
-if (C->failing())  return;
+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
 {
 NOT_PRODUCT( Compile::TracePhase t3("computeLive", &_t_computeLive, TimeCompiler); )
 _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 );
+gather_lrg_masks(true);
-live.compute( _maxlrg );
+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
 cache_lrg_info();           // Count degree of LRGs
 // LRGs of low degree are trivially colorable.
 Simplify();
 // 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.
 _allocator_attempts += _trip_cnt + 1;
 _allocator_successes += 1;
 verify(&live_arena);
 #endif
 // 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
 _framesize = round_to(_framesize, Matcher::stack_alignment_in_slots());
 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
 fixup_spills();
 CompileLog* log = Compile::current()->log();
 if (log != NULL) {
 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());
+alloc_node_regs(_lrg_map.size());
-for (uint i=0; i < _names.Size(); i++) {
+for (uint i=0; i < _lrg_map.size(); i++) {
-if (_names[i]) {           // Live range associated with Node?
+if (_lrg_map.live_range_id(i)) { // Live range associated with Node?
-LRG &lrg = lrgs(_names[i]);
+LRG &lrg = lrgs(_lrg_map.live_range_id(i));
 if (!lrg.alive()) {
 set_bad(i);
 } else if (lrg.num_regs() == 1) {
 set1(i, lrg.reg());
 } else {                  // Must be a register-set
 // Handle all the normal Nodes in the block
 for( uint j = 0; j < cnt; j++ ) {
 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);
 }
 //------------------------------gather_lrg_masks-------------------------------
 // Gather LiveRanGe information, including register masks.  Modification of
 // cisc spillable in_RegMasks should not be done before AggressiveCoalesce.
 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
 for( uint i = 0; i < _cfg._num_blocks; i++ ) {
 Block *b = _cfg._blocks[i];
 uint input_edge_start =1; // Skip control most nodes
 if( n->is_Mach() ) input_edge_start = n->as_Mach()->oper_input_base();
 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 &copy_src = lrgs(clidx);
 copy_src._has_copy = 1;
 }
 // Check for float-vs-int live range (used in register-pressure
 // Convert operand number to edge index number
 inp = n->as_Mach()->operand_index(inp);
 }
 // Prepare register mask for each input
 for( uint k = input_edge_start; k < cnt; k++ ) {
-uint vreg = n2lidx(n->in(k));
+uint vreg = _lrg_map.live_range_id(n->in(k));
-if( !vreg ) continue;
+if (!vreg) {
+continue;
+}
 // If this instruction is CISC Spillable, add the flags
 // bit to its appropriate input
 if( UseCISCSpill && after_aggressive && inp == k ) {
 #ifndef PRODUCT
 } // End for all allocated inputs
 } // end for all instructions
 } // 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) {
 lrg.clear_to_sets();
 }
 // colorability of the graph.  If any live range was of low-degree before
 // coalescing, it should Simplify.  This call sets the was-lo-degree bit.
 // 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;
 if( lrgs(i).lo_degree() ) {
 lrgs(i)._was_lo = 1;      // Trivially of low degree
 //------------------------------cache_lrg_info---------------------------------
 // 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.
 // Low degree, dead or must-spill guys just get to simplify right away
 if( lrg.lo_degree() ||
 // Simplify the IFG by removing LRGs of low degree that have NO copies
 void PhaseChaitin::Pre_Simplify( ) {
 // Warm up the lo-degree no-copy list
 int lo_no_copy = 0;
-for( uint i = 1; i < _maxlrg; i++ ) {
+for (uint i = 1; i < _lrg_map.max_lrg_id(); i++) {
-if( (lrgs(i).lo_degree() && !lrgs(i)._has_copy) ||
+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;
 }
 }
 //------------------------------bias_color-------------------------------------
 // Choose a color using the biasing heuristic
 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
 // of the "at_risk" candidate in order to improve the chances of the
 // "at_risk" candidate of coloring
 if (is_legal_reg(lrg, reg, chunk))
 return reg;
 }
 }
-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] ) {
 OptoReg::Name reg = lrgs(copy_lrg).reg();
 //  And it is legal for you,
 //------------------------------copy_was_spilled-------------------------------
 // Copy 'was_spilled'-edness from the source Node to the dst Node.
 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;
 }
 }
 }
 //------------------------------set_was_spilled--------------------------------
 if( inp != AdlcVMDeps::Not_cisc_spillable ) {
 // Convert operand number to edge index number
 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());
 if( OptoReg::is_stack(src_reg) ) { // If input is on stack
 // This is a CISC Spill, get stack offset and construct new node
 // (where top() node is placed).
 base->init_req(0, _cfg._root);
 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 &&
 _cfg._bbs[base->_idx] == _cfg._bbs[C->top()->_idx], "base NULL should be shared");
 derived_base_map[derived->_idx] = base;
 return base;
 }
 // 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;
 return base;
 }
 //------------------------------stretch_base_pointer_live_ranges---------------
 // At each Safepoint, insert extra debug edges for each pair of derived value/
 // 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() );
 // For all blocks in RPO do...
 for( uint i=0; i<_cfg._num_blocks; i++ ) {
 }
 }
 }
 // Get value being defined
-uint lidx = n2lidx(n);
+uint lidx = _lrg_map.live_range_id(n);
-if( lidx && lidx < _maxlrg /* Ignore the occasional brand-new live range */) {
+// 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?
 JVMState *jvms = n->jvms();
 if( jvms ) {
 const TypePtr *tj = derived->bottom_type()->isa_ptr();
 assert(!derived->bottom_type()->isa_narrowoop() ||
 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 );
+Node *base = find_base_for_derived(derived_base_map, derived, maxlrg);
-assert( base->_idx < _names.Size(), "" );
+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(derived);
-n->add_req( base );
+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
+if ((_lrg_map.live_range_id(base) >= _lrg_map.max_lrg_id() || // (Brand new base (hence not live) or
-!liveout.member( n2lidx(base) ) ) && // not live) AND
+!liveout.member(_lrg_map.live_range_id(base))) && // not live) AND
-(n2lidx(base) > 0)                && // not a constant
+(_lrg_map.live_range_id(base) > 0) && // not a constant
-_cfg._bbs[base->_idx] != b ) {     //  base not def'd in blk)
+_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.
 // Recompute live.
 must_recompute_live = true;
 }
 } // End of scan all live data for derived ptrs crossing GC point
 } // End of if found a GC point
 // Make all inputs live
-if( !n->is_Phi() ) {      // Phi function uses come from prior block
+if (!n->is_Phi()) {      // Phi function uses come from prior block
-for( uint k = 1; k < n->req(); k++ ) {
+for (uint k = 1; k < n->req(); k++) {
-uint lidx = n2lidx(n->in(k));
+uint lidx = _lrg_map.live_range_id(n->in(k));
-if( lidx < _maxlrg )
+if (lidx < _lrg_map.max_lrg_id()) {
-liveout.insert( lidx );
+liveout.insert(lidx);
+}
 }
 }
 } // End of forall instructions in block
 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;
 }
 //------------------------------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 {
+void PhaseChaitin::dump(const Node *n) const {
-uint r = (n->_idx < _names.Size() ) ? Find_const(n) : 0;
+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);
 if( OptoReg::is_valid(second) ) {
 if( OptoReg::is_reg(second) )
 n->out_RegMask().dump();
 }
 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.
 int op = n->Opcode();
 if( r && op != Op_Phi && op != Op_Proj && op != Op_SCMemProj) {
 }
 }
 if( k < n->len() && n->in(k) ) tty->print("| ");
 for( ; k < n->len(); k++ ) {
 Node *m = n->in(k);
-if( !m ) break;
+if(!m) {
-uint r = (m->_idx < _names.Size() ) ? Find_const(m) : 0;
+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);
 }
 if( n->is_Mach() ) n->as_Mach()->dump_spec(tty);
 else n->dump_spec(tty);
 IndexSet *live = _live->live(b);
 IndexSetIterator elements(live);
 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("}");
 }
 tty->print("\n");
 }
 return;
 }
 // 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( );
+if (i2 < _ifg->_maxlrg) {
-else tty->print_cr("new LRG");
+lrgs(i2).dump();
+}
+else {
+tty->print_cr("new LRG");
+}
 }
 tty->print_cr("");
 // Dump lo-degree list
 tty->print("Lo degree: ");
 sprintf(buf,"N%d",n->_idx); // Then use Node index
 } else if( _node_regs ) {
 // 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
 strcpy(buf,"Special");
 } else {
 //----------------------dump_for_spill_split_recycle--------------------------
 void PhaseChaitin::dump_for_spill_split_recycle() const {
 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();
 }
 }
 //------------------------------dump_lrg---------------------------------------
 void PhaseChaitin::dump_lrg( uint lidx, bool defs_only ) const {
 tty->print_cr("---dump of L%d---",lidx);
-if( _ifg ) {
+if (_ifg) {
-if( lidx >= _maxlrg ) {
+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( );
+if (lidx < _ifg->_maxlrg) {
-else tty->print_cr("new LRG");
+lrgs(lidx).dump();
+} else {
+tty->print_cr("new LRG");
+}
 }
 if( _ifg && lidx < _ifg->_maxlrg) {
 tty->print("Neighbors: %d - ", _ifg->neighbor_cnt(lidx));
 _ifg->neighbors(lidx)->dump();
 tty->cr();
 int dump_once = 0;
 // For all instructions
 for( uint j = 0; j < b->_nodes.size(); j++ ) {
 Node *n = b->_nodes[j];
-if( Find_const(n) == lidx ) {
+if (_lrg_map.find_const(n) == lidx) {
-if( !dump_once++ ) {
+if (!dump_once++) {
 tty->cr();
 b->dump_head( &_cfg._bbs );
 }
 dump(n);
 continue;
 }
 if (!defs_only) {
 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 (!m)  {
-if( Find_const(m) == lidx ) {
+continue;  // be robust in the dumper
-if( !dump_once++ ) {
+}
+if (_lrg_map.find_const(m) == lidx) {
+if (!dump_once++) {
 tty->cr();
-b->dump_head( &_cfg._bbs );
+b->dump_head(&_cfg._bbs);
 }
 dump(n);
 }
 }
 }

Mercurial > hg > graal-compiler

comparison src/share/vm/opto/chaitin.cpp @ 10111:8373c19be854