Mercurial > hg > graal-compiler

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

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
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 c7b60b601eb4
children 693e4d04fd09
comparison
equal deleted inserted replaced
10109:1c6887c9afaa 10111:8373c19be854
33 #include "opto/machnode.hpp" 33 #include "opto/machnode.hpp"
34 #include "opto/matcher.hpp" 34 #include "opto/matcher.hpp"
35 #include "opto/regmask.hpp" 35 #include "opto/regmask.hpp"
36 36
37 //============================================================================= 37 //=============================================================================
38 //------------------------------reset_uf_map-----------------------------------
39 void PhaseChaitin::reset_uf_map( uint maxlrg ) {
40 _maxlrg = maxlrg;
41 // Force the Union-Find mapping to be at least this large
42 _uf_map.extend(_maxlrg,0);
43 // Initialize it to be the ID mapping.
44 for( uint i=0; i<_maxlrg; i++ )
45 _uf_map.map(i,i);
46 }
47
48 //------------------------------compress_uf_map--------------------------------
49 // Make all Nodes map directly to their final live range; no need for
50 // the Union-Find mapping after this call.
51 void PhaseChaitin::compress_uf_map_for_nodes( ) {
52 // For all Nodes, compress mapping
53 uint unique = _names.Size();
54 for( uint i=0; i<unique; i++ ) {
55 uint lrg = _names[i];
56 uint compressed_lrg = Find(lrg);
57 if( lrg != compressed_lrg )
58 _names.map(i,compressed_lrg);
59 }
60 }
61
62 //------------------------------Find-------------------------------------------
63 // Straight out of Tarjan's union-find algorithm
64 uint PhaseChaitin::Find_compress( uint lrg ) {
65 uint cur = lrg;
66 uint next = _uf_map[cur];
67 while( next != cur ) { // Scan chain of equivalences
68 assert( next < cur, "always union smaller" );
69 cur = next; // until find a fixed-point
70 next = _uf_map[cur];
71 }
72 // Core of union-find algorithm: update chain of
73 // equivalences to be equal to the root.
74 while( lrg != next ) {
75 uint tmp = _uf_map[lrg];
76 _uf_map.map(lrg, next);
77 lrg = tmp;
78 }
79 return lrg;
80 }
81
82 //------------------------------Find-------------------------------------------
83 // Straight out of Tarjan's union-find algorithm
84 uint PhaseChaitin::Find_compress( const Node *n ) {
85 uint lrg = Find_compress(_names[n->_idx]);
86 _names.map(n->_idx,lrg);
87 return lrg;
88 }
89
90 //------------------------------Find_const-------------------------------------
91 // Like Find above, but no path compress, so bad asymptotic behavior
92 uint PhaseChaitin::Find_const( uint lrg ) const {
93 if( !lrg ) return lrg; // Ignore the zero LRG
94 // Off the end? This happens during debugging dumps when you got
95 // brand new live ranges but have not told the allocator yet.
96 if( lrg >= _maxlrg ) return lrg;
97 uint next = _uf_map[lrg];
98 while( next != lrg ) { // Scan chain of equivalences
99 assert( next < lrg, "always union smaller" );
100 lrg = next; // until find a fixed-point
101 next = _uf_map[lrg];
102 }
103 return next;
104 }
105
106 //------------------------------Find-------------------------------------------
107 // Like Find above, but no path compress, so bad asymptotic behavior
108 uint PhaseChaitin::Find_const( const Node *n ) const {
109 if( n->_idx >= _names.Size() ) return 0; // not mapped, usual for debug dump
110 return Find_const( _names[n->_idx] );
111 }
112
113 //------------------------------Union------------------------------------------
114 // union 2 sets together.
115 void PhaseChaitin::Union( const Node *src_n, const Node *dst_n ) {
116 uint src = Find(src_n);
117 uint dst = Find(dst_n);
118 assert( src, "" );
119 assert( dst, "" );
120 assert( src < _maxlrg, "oob" );
121 assert( dst < _maxlrg, "oob" );
122 assert( src < dst, "always union smaller" );
123 _uf_map.map(dst,src);
124 }
125
126 //------------------------------new_lrg----------------------------------------
127 void PhaseChaitin::new_lrg( const Node *x, uint lrg ) {
128 // Make the Node->LRG mapping
129 _names.extend(x->_idx,lrg);
130 // Make the Union-Find mapping an identity function
131 _uf_map.extend(lrg,lrg);
132 }
133
134 //------------------------------clone_projs------------------------------------
135 // After cloning some rematerialized instruction, clone any MachProj's that
136 // follow it. Example: Intel zero is XOR, kills flags. Sparc FP constants
137 // use G3 as an address temp.
138 int PhaseChaitin::clone_projs( Block *b, uint idx, Node *con, Node *copy, uint &maxlrg ) {
139 Block *bcon = _cfg._bbs[con->_idx];
140 uint cindex = bcon->find_node(con);
141 Node *con_next = bcon->_nodes[cindex+1];
142 if( con_next->in(0) != con || !con_next->is_MachProj() )
143 return false; // No MachProj's follow
144
145 // Copy kills after the cloned constant
146 Node *kills = con_next->clone();
147 kills->set_req( 0, copy );
148 b->_nodes.insert( idx, kills );
149 _cfg._bbs.map( kills->_idx, b );
150 new_lrg( kills, maxlrg++ );
151 return true;
152 }
153
154 //------------------------------compact----------------------------------------
155 // Renumber the live ranges to compact them. Makes the IFG smaller.
156 void PhaseChaitin::compact() {
157 // Current the _uf_map contains a series of short chains which are headed
158 // by a self-cycle. All the chains run from big numbers to little numbers.
159 // The Find() call chases the chains & shortens them for the next Find call.
160 // We are going to change this structure slightly. Numbers above a moving
161 // wave 'i' are unchanged. Numbers below 'j' point directly to their
162 // compacted live range with no further chaining. There are no chains or
163 // cycles below 'i', so the Find call no longer works.
164 uint j=1;
165 uint i;
166 for( i=1; i < _maxlrg; i++ ) {
167 uint lr = _uf_map[i];
168 // Ignore unallocated live ranges
169 if( !lr ) continue;
170 assert( lr <= i, "" );
171 _uf_map.map(i, ( lr == i ) ? j++ : _uf_map[lr]);
172 }
173 if( false ) // PrintOptoCompactLiveRanges
174 printf("Compacted %d LRs from %d\n",i-j,i);
175 // Now change the Node->LR mapping to reflect the compacted names
176 uint unique = _names.Size();
177 for( i=0; i<unique; i++ )
178 _names.map(i,_uf_map[_names[i]]);
179
180 // Reset the Union-Find mapping
181 reset_uf_map(j);
182
183 }
184
185 //=============================================================================
186 //------------------------------Dump------------------------------------------- 38 //------------------------------Dump-------------------------------------------
187 #ifndef PRODUCT 39 #ifndef PRODUCT
188 void PhaseCoalesce::dump( Node *n ) const { 40 void PhaseCoalesce::dump(Node *n) const {
189 // Being a const function means I cannot use 'Find' 41 // Being a const function means I cannot use 'Find'
190 uint r = _phc.Find(n); 42 uint r = _phc._lrg_map.find(n);
191 tty->print("L%d/N%d ",r,n->_idx); 43 tty->print("L%d/N%d ",r,n->_idx);
192 } 44 }
193 45
194 //------------------------------dump------------------------------------------- 46 //------------------------------dump-------------------------------------------
195 void PhaseCoalesce::dump() const { 47 void PhaseCoalesce::dump() const {
233 } 85 }
234 #endif 86 #endif
235 87
236 //------------------------------combine_these_two------------------------------ 88 //------------------------------combine_these_two------------------------------
237 // Combine the live ranges def'd by these 2 Nodes. N2 is an input to N1. 89 // Combine the live ranges def'd by these 2 Nodes. N2 is an input to N1.
238 void PhaseCoalesce::combine_these_two( Node *n1, Node *n2 ) { 90 void PhaseCoalesce::combine_these_two(Node *n1, Node *n2) {
239 uint lr1 = _phc.Find(n1); 91 uint lr1 = _phc._lrg_map.find(n1);
240 uint lr2 = _phc.Find(n2); 92 uint lr2 = _phc._lrg_map.find(n2);
241 if( lr1 != lr2 && // Different live ranges already AND 93 if( lr1 != lr2 && // Different live ranges already AND
242 !_phc._ifg->test_edge_sq( lr1, lr2 ) ) { // Do not interfere 94 !_phc._ifg->test_edge_sq( lr1, lr2 ) ) { // Do not interfere
243 LRG *lrg1 = &_phc.lrgs(lr1); 95 LRG *lrg1 = &_phc.lrgs(lr1);
244 LRG *lrg2 = &_phc.lrgs(lr2); 96 LRG *lrg2 = &_phc.lrgs(lr2);
245 // Not an oop->int cast; oop->oop, int->int, AND int->oop are OK. 97 // Not an oop->int cast; oop->oop, int->int, AND int->oop are OK.
304 156
305 // Scan backwards for the locations of the last use of the dst_name. 157 // Scan backwards for the locations of the last use of the dst_name.
306 // I am about to clobber the dst_name, so the copy must be inserted 158 // I am about to clobber the dst_name, so the copy must be inserted
307 // after the last use. Last use is really first-use on a backwards scan. 159 // after the last use. Last use is really first-use on a backwards scan.
308 uint i = b->end_idx()-1; 160 uint i = b->end_idx()-1;
309 while( 1 ) { 161 while(1) {
310 Node *n = b->_nodes[i]; 162 Node *n = b->_nodes[i];
311 // Check for end of virtual copies; this is also the end of the 163 // Check for end of virtual copies; this is also the end of the
312 // parallel renaming effort. 164 // parallel renaming effort.
313 if( n->_idx < _unique ) break; 165 if (n->_idx < _unique) {
166 break;
167 }
314 uint idx = n->is_Copy(); 168 uint idx = n->is_Copy();
315 assert( idx || n->is_Con() || n->is_MachProj(), "Only copies during parallel renaming" ); 169 assert( idx || n->is_Con() || n->is_MachProj(), "Only copies during parallel renaming" );
316 if( idx && _phc.Find(n->in(idx)) == dst_name ) break; 170 if (idx && _phc._lrg_map.find(n->in(idx)) == dst_name) {
171 break;
172 }
317 i--; 173 i--;
318 } 174 }
319 uint last_use_idx = i; 175 uint last_use_idx = i;
320 176
321 // Also search for any kill of src_name that exits the block. 177 // Also search for any kill of src_name that exits the block.
322 // Since the copy uses src_name, I have to come before any kill. 178 // Since the copy uses src_name, I have to come before any kill.
323 uint kill_src_idx = b->end_idx(); 179 uint kill_src_idx = b->end_idx();
324 // There can be only 1 kill that exits any block and that is 180 // There can be only 1 kill that exits any block and that is
325 // the last kill. Thus it is the first kill on a backwards scan. 181 // the last kill. Thus it is the first kill on a backwards scan.
326 i = b->end_idx()-1; 182 i = b->end_idx()-1;
327 while( 1 ) { 183 while (1) {
328 Node *n = b->_nodes[i]; 184 Node *n = b->_nodes[i];
329 // Check for end of virtual copies; this is also the end of the 185 // Check for end of virtual copies; this is also the end of the
330 // parallel renaming effort. 186 // parallel renaming effort.
331 if( n->_idx < _unique ) break; 187 if (n->_idx < _unique) {
188 break;
189 }
332 assert( n->is_Copy() || n->is_Con() || n->is_MachProj(), "Only copies during parallel renaming" ); 190 assert( n->is_Copy() || n->is_Con() || n->is_MachProj(), "Only copies during parallel renaming" );
333 if( _phc.Find(n) == src_name ) { 191 if (_phc._lrg_map.find(n) == src_name) {
334 kill_src_idx = i; 192 kill_src_idx = i;
335 break; 193 break;
336 } 194 }
337 i--; 195 i--;
338 } 196 }
339 // Need a temp? Last use of dst comes after the kill of src? 197 // Need a temp? Last use of dst comes after the kill of src?
340 if( last_use_idx >= kill_src_idx ) { 198 if (last_use_idx >= kill_src_idx) {
341 // Need to break a cycle with a temp 199 // Need to break a cycle with a temp
342 uint idx = copy->is_Copy(); 200 uint idx = copy->is_Copy();
343 Node *tmp = copy->clone(); 201 Node *tmp = copy->clone();
344 _phc.new_lrg(tmp,_phc._maxlrg++); 202 uint max_lrg_id = _phc._lrg_map.max_lrg_id();
203 _phc.new_lrg(tmp, max_lrg_id);
204 _phc._lrg_map.set_max_lrg_id(max_lrg_id + 1);
205
345 // Insert new temp between copy and source 206 // Insert new temp between copy and source
346 tmp ->set_req(idx,copy->in(idx)); 207 tmp ->set_req(idx,copy->in(idx));
347 copy->set_req(idx,tmp); 208 copy->set_req(idx,tmp);
348 // Save source in temp early, before source is killed 209 // Save source in temp early, before source is killed
349 b->_nodes.insert(kill_src_idx,tmp); 210 b->_nodes.insert(kill_src_idx,tmp);
357 218
358 //------------------------------insert_copies---------------------------------- 219 //------------------------------insert_copies----------------------------------
359 void PhaseAggressiveCoalesce::insert_copies( Matcher &matcher ) { 220 void PhaseAggressiveCoalesce::insert_copies( Matcher &matcher ) {
360 // We do LRGs compressing and fix a liveout data only here since the other 221 // We do LRGs compressing and fix a liveout data only here since the other
361 // place in Split() is guarded by the assert which we never hit. 222 // place in Split() is guarded by the assert which we never hit.
362 _phc.compress_uf_map_for_nodes(); 223 _phc._lrg_map.compress_uf_map_for_nodes();
363 // Fix block's liveout data for compressed live ranges. 224 // Fix block's liveout data for compressed live ranges.
364 for(uint lrg = 1; lrg < _phc._maxlrg; lrg++ ) { 225 for (uint lrg = 1; lrg < _phc._lrg_map.max_lrg_id(); lrg++) {
365 uint compressed_lrg = _phc.Find(lrg); 226 uint compressed_lrg = _phc._lrg_map.find(lrg);
366 if( lrg != compressed_lrg ) { 227 if (lrg != compressed_lrg) {
367 for( uint bidx = 0; bidx < _phc._cfg._num_blocks; bidx++ ) { 228 for (uint bidx = 0; bidx < _phc._cfg._num_blocks; bidx++) {
368 IndexSet *liveout = _phc._live->live(_phc._cfg._blocks[bidx]); 229 IndexSet *liveout = _phc._live->live(_phc._cfg._blocks[bidx]);
369 if( liveout->member(lrg) ) { 230 if (liveout->member(lrg)) {
370 liveout->remove(lrg); 231 liveout->remove(lrg);
371 liveout->insert(compressed_lrg); 232 liveout->insert(compressed_lrg);
372 } 233 }
373 } 234 }
374 } 235 }
390 for( uint k = 1; k<ncnt; k++ ) { 251 for( uint k = 1; k<ncnt; k++ ) {
391 Node *copy = n->in(k); 252 Node *copy = n->in(k);
392 uint cidx = copy->is_Copy(); 253 uint cidx = copy->is_Copy();
393 if( cidx ) { 254 if( cidx ) {
394 Node *def = copy->in(cidx); 255 Node *def = copy->in(cidx);
395 if( _phc.Find(copy) == _phc.Find(def) ) 256 if (_phc._lrg_map.find(copy) == _phc._lrg_map.find(def)) {
396 n->set_req(k,def); 257 n->set_req(k, def);
258 }
397 } 259 }
398 } 260 }
399 261
400 // Remove any explicit copies that get coalesced. 262 // Remove any explicit copies that get coalesced.
401 uint cidx = n->is_Copy(); 263 uint cidx = n->is_Copy();
402 if( cidx ) { 264 if( cidx ) {
403 Node *def = n->in(cidx); 265 Node *def = n->in(cidx);
404 if( _phc.Find(n) == _phc.Find(def) ) { 266 if (_phc._lrg_map.find(n) == _phc._lrg_map.find(def)) {
405 n->replace_by(def); 267 n->replace_by(def);
406 n->set_req(cidx,NULL); 268 n->set_req(cidx,NULL);
407 b->_nodes.remove(l); 269 b->_nodes.remove(l);
408 l--; 270 l--;
409 continue; 271 continue;
410 } 272 }
411 } 273 }
412 274
413 if( n->is_Phi() ) { 275 if (n->is_Phi()) {
414 // Get the chosen name for the Phi 276 // Get the chosen name for the Phi
415 uint phi_name = _phc.Find( n ); 277 uint phi_name = _phc._lrg_map.find(n);
416 // Ignore the pre-allocated specials 278 // Ignore the pre-allocated specials
417 if( !phi_name ) continue; 279 if (!phi_name) {
280 continue;
281 }
418 // Check for mismatch inputs to Phi 282 // Check for mismatch inputs to Phi
419 for( uint j = 1; j<cnt; j++ ) { 283 for (uint j = 1; j < cnt; j++) {
420 Node *m = n->in(j); 284 Node *m = n->in(j);
421 uint src_name = _phc.Find(m); 285 uint src_name = _phc._lrg_map.find(m);
422 if( src_name != phi_name ) { 286 if (src_name != phi_name) {
423 Block *pred = _phc._cfg._bbs[b->pred(j)->_idx]; 287 Block *pred = _phc._cfg._bbs[b->pred(j)->_idx];
424 Node *copy; 288 Node *copy;
425 assert(!m->is_Con() || m->is_Mach(), "all Con must be Mach"); 289 assert(!m->is_Con() || m->is_Mach(), "all Con must be Mach");
426 // Rematerialize constants instead of copying them 290 // Rematerialize constants instead of copying them
427 if( m->is_Mach() && m->as_Mach()->is_Con() && 291 if( m->is_Mach() && m->as_Mach()->is_Con() &&
428 m->as_Mach()->rematerialize() ) { 292 m->as_Mach()->rematerialize() ) {
429 copy = m->clone(); 293 copy = m->clone();
430 // Insert the copy in the predecessor basic block 294 // Insert the copy in the predecessor basic block
431 pred->add_inst(copy); 295 pred->add_inst(copy);
432 // Copy any flags as well 296 // Copy any flags as well
433 _phc.clone_projs( pred, pred->end_idx(), m, copy, _phc._maxlrg ); 297 _phc.clone_projs(pred, pred->end_idx(), m, copy, _phc._lrg_map);
434 } else { 298 } else {
435 const RegMask *rm = C->matcher()->idealreg2spillmask[m->ideal_reg()]; 299 const RegMask *rm = C->matcher()->idealreg2spillmask[m->ideal_reg()];
436 copy = new (C) MachSpillCopyNode(m,*rm,*rm); 300 copy = new (C) MachSpillCopyNode(m, *rm, *rm);
437 // Find a good place to insert. Kinda tricky, use a subroutine 301 // Find a good place to insert. Kinda tricky, use a subroutine
438 insert_copy_with_overlap(pred,copy,phi_name,src_name); 302 insert_copy_with_overlap(pred,copy,phi_name,src_name);
439 } 303 }
440 // Insert the copy in the use-def chain 304 // Insert the copy in the use-def chain
441 n->set_req( j, copy ); 305 n->set_req(j, copy);
442 _phc._cfg._bbs.map( copy->_idx, pred ); 306 _phc._cfg._bbs.map( copy->_idx, pred );
443 // Extend ("register allocate") the names array for the copy. 307 // Extend ("register allocate") the names array for the copy.
444 _phc._names.extend( copy->_idx, phi_name ); 308 _phc._lrg_map.extend(copy->_idx, phi_name);
445 } // End of if Phi names do not match 309 } // End of if Phi names do not match
446 } // End of for all inputs to Phi 310 } // End of for all inputs to Phi
447 } else { // End of if Phi 311 } else { // End of if Phi
448 312
449 // Now check for 2-address instructions 313 // Now check for 2-address instructions
450 uint idx; 314 uint idx;
451 if( n->is_Mach() && (idx=n->as_Mach()->two_adr()) ) { 315 if( n->is_Mach() && (idx=n->as_Mach()->two_adr()) ) {
452 // Get the chosen name for the Node 316 // Get the chosen name for the Node
453 uint name = _phc.Find( n ); 317 uint name = _phc._lrg_map.find(n);
454 assert( name, "no 2-address specials" ); 318 assert (name, "no 2-address specials");
455 // Check for name mis-match on the 2-address input 319 // Check for name mis-match on the 2-address input
456 Node *m = n->in(idx); 320 Node *m = n->in(idx);
457 if( _phc.Find(m) != name ) { 321 if (_phc._lrg_map.find(m) != name) {
458 Node *copy; 322 Node *copy;
459 assert(!m->is_Con() || m->is_Mach(), "all Con must be Mach"); 323 assert(!m->is_Con() || m->is_Mach(), "all Con must be Mach");
460 // At this point it is unsafe to extend live ranges (6550579). 324 // At this point it is unsafe to extend live ranges (6550579).
461 // Rematerialize only constants as we do for Phi above. 325 // Rematerialize only constants as we do for Phi above.
462 if( m->is_Mach() && m->as_Mach()->is_Con() && 326 if(m->is_Mach() && m->as_Mach()->is_Con() &&
463 m->as_Mach()->rematerialize() ) { 327 m->as_Mach()->rematerialize()) {
464 copy = m->clone(); 328 copy = m->clone();
465 // Insert the copy in the basic block, just before us 329 // Insert the copy in the basic block, just before us
466 b->_nodes.insert( l++, copy ); 330 b->_nodes.insert(l++, copy);
467 if( _phc.clone_projs( b, l, m, copy, _phc._maxlrg ) ) 331 if(_phc.clone_projs(b, l, m, copy, _phc._lrg_map)) {
468 l++; 332 l++;
333 }
469 } else { 334 } else {
470 const RegMask *rm = C->matcher()->idealreg2spillmask[m->ideal_reg()]; 335 const RegMask *rm = C->matcher()->idealreg2spillmask[m->ideal_reg()];
471 copy = new (C) MachSpillCopyNode( m, *rm, *rm ); 336 copy = new (C) MachSpillCopyNode(m, *rm, *rm);
472 // Insert the copy in the basic block, just before us 337 // Insert the copy in the basic block, just before us
473 b->_nodes.insert( l++, copy ); 338 b->_nodes.insert(l++, copy);
474 } 339 }
475 // Insert the copy in the use-def chain 340 // Insert the copy in the use-def chain
476 n->set_req(idx, copy ); 341 n->set_req(idx, copy);
477 // Extend ("register allocate") the names array for the copy. 342 // Extend ("register allocate") the names array for the copy.
478 _phc._names.extend( copy->_idx, name ); 343 _phc._lrg_map.extend(copy->_idx, name);
479 _phc._cfg._bbs.map( copy->_idx, b ); 344 _phc._cfg._bbs.map( copy->_idx, b );
480 } 345 }
481 346
482 } // End of is two-adr 347 } // End of is two-adr
483 348
484 // Insert a copy at a debug use for a lrg which has high frequency 349 // Insert a copy at a debug use for a lrg which has high frequency
485 if( b->_freq < OPTO_DEBUG_SPLIT_FREQ || b->is_uncommon(_phc._cfg._bbs) ) { 350 if (b->_freq < OPTO_DEBUG_SPLIT_FREQ || b->is_uncommon(_phc._cfg._bbs)) {
486 // Walk the debug inputs to the node and check for lrg freq 351 // Walk the debug inputs to the node and check for lrg freq
487 JVMState* jvms = n->jvms(); 352 JVMState* jvms = n->jvms();
488 uint debug_start = jvms ? jvms->debug_start() : 999999; 353 uint debug_start = jvms ? jvms->debug_start() : 999999;
489 uint debug_end = jvms ? jvms->debug_end() : 999999; 354 uint debug_end = jvms ? jvms->debug_end() : 999999;
490 for(uint inpidx = debug_start; inpidx < debug_end; inpidx++) { 355 for(uint inpidx = debug_start; inpidx < debug_end; inpidx++) {
491 // Do not split monitors; they are only needed for debug table 356 // Do not split monitors; they are only needed for debug table
492 // entries and need no code. 357 // entries and need no code.
493 if( jvms->is_monitor_use(inpidx) ) continue; 358 if (jvms->is_monitor_use(inpidx)) {
359 continue;
360 }
494 Node *inp = n->in(inpidx); 361 Node *inp = n->in(inpidx);
495 uint nidx = _phc.n2lidx(inp); 362 uint nidx = _phc._lrg_map.live_range_id(inp);
496 LRG &lrg = lrgs(nidx); 363 LRG &lrg = lrgs(nidx);
497 364
498 // If this lrg has a high frequency use/def 365 // If this lrg has a high frequency use/def
499 if( lrg._maxfreq >= _phc.high_frequency_lrg() ) { 366 if( lrg._maxfreq >= _phc.high_frequency_lrg() ) {
500 // If the live range is also live out of this block (like it 367 // If the live range is also live out of this block (like it
517 // Insert the copy in the use-def chain 384 // Insert the copy in the use-def chain
518 n->set_req(inpidx, copy ); 385 n->set_req(inpidx, copy );
519 // Insert the copy in the basic block, just before us 386 // Insert the copy in the basic block, just before us
520 b->_nodes.insert( l++, copy ); 387 b->_nodes.insert( l++, copy );
521 // Extend ("register allocate") the names array for the copy. 388 // Extend ("register allocate") the names array for the copy.
522 _phc.new_lrg( copy, _phc._maxlrg++ ); 389 uint max_lrg_id = _phc._lrg_map.max_lrg_id();
523 _phc._cfg._bbs.map( copy->_idx, b ); 390 _phc.new_lrg(copy, max_lrg_id);
391 _phc._lrg_map.set_max_lrg_id(max_lrg_id + 1);
392 _phc._cfg._bbs.map(copy->_idx, b);
524 //tty->print_cr("Split a debug use in Aggressive Coalesce"); 393 //tty->print_cr("Split a debug use in Aggressive Coalesce");
525 } // End of if high frequency use/def 394 } // End of if high frequency use/def
526 } // End of for all debug inputs 395 } // End of for all debug inputs
527 } // End of if low frequency safepoint 396 } // End of if low frequency safepoint
528 397
581 for( i = 1; i<cnt; i++ ) { 450 for( i = 1; i<cnt; i++ ) {
582 Node *n = b->_nodes[i]; 451 Node *n = b->_nodes[i];
583 uint idx; 452 uint idx;
584 // 2-address instructions have a virtual Copy matching their input 453 // 2-address instructions have a virtual Copy matching their input
585 // to their output 454 // to their output
586 if( n->is_Mach() && (idx = n->as_Mach()->two_adr()) ) { 455 if (n->is_Mach() && (idx = n->as_Mach()->two_adr())) {
587 MachNode *mach = n->as_Mach(); 456 MachNode *mach = n->as_Mach();
588 combine_these_two( mach, mach->in(idx) ); 457 combine_these_two(mach, mach->in(idx));
589 } 458 }
590 } // End of for all instructions in block 459 } // End of for all instructions in block
591 } 460 }
592 461
593 //============================================================================= 462 //=============================================================================
594 //------------------------------PhaseConservativeCoalesce---------------------- 463 //------------------------------PhaseConservativeCoalesce----------------------
595 PhaseConservativeCoalesce::PhaseConservativeCoalesce( PhaseChaitin &chaitin ) : PhaseCoalesce(chaitin) { 464 PhaseConservativeCoalesce::PhaseConservativeCoalesce(PhaseChaitin &chaitin) : PhaseCoalesce(chaitin) {
596 _ulr.initialize(_phc._maxlrg); 465 _ulr.initialize(_phc._lrg_map.max_lrg_id());
597 } 466 }
598 467
599 //------------------------------verify----------------------------------------- 468 //------------------------------verify-----------------------------------------
600 void PhaseConservativeCoalesce::verify() { 469 void PhaseConservativeCoalesce::verify() {
601 #ifdef ASSERT 470 #ifdef ASSERT
671 if( prev_copy == src_copy)// Found end of chain and all interferences 540 if( prev_copy == src_copy)// Found end of chain and all interferences
672 break; // So break out of loop 541 break; // So break out of loop
673 // Else work back one in copy chain 542 // Else work back one in copy chain
674 prev_copy = prev_copy->in(prev_copy->is_Copy()); 543 prev_copy = prev_copy->in(prev_copy->is_Copy());
675 } else { // Else collect interferences 544 } else { // Else collect interferences
676 uint lidx = _phc.Find(x); 545 uint lidx = _phc._lrg_map.find(x);
677 // Found another def of live-range being stretched? 546 // Found another def of live-range being stretched?
678 if( lidx == lr1 ) return max_juint; 547 if(lidx == lr1) {
679 if( lidx == lr2 ) return max_juint; 548 return max_juint;
549 }
550 if(lidx == lr2) {
551 return max_juint;
552 }
680 553
681 // If we attempt to coalesce across a bound def 554 // If we attempt to coalesce across a bound def
682 if( lrgs(lidx).is_bound() ) { 555 if( lrgs(lidx).is_bound() ) {
683 // Do not let the coalesced LRG expect to get the bound color 556 // Do not let the coalesced LRG expect to get the bound color
684 rm.SUBTRACT( lrgs(lidx).mask() ); 557 rm.SUBTRACT( lrgs(lidx).mask() );
749 622
750 //------------------------------copy_copy-------------------------------------- 623 //------------------------------copy_copy--------------------------------------
751 // See if I can coalesce a series of multiple copies together. I need the 624 // See if I can coalesce a series of multiple copies together. I need the
752 // final dest copy and the original src copy. They can be the same Node. 625 // final dest copy and the original src copy. They can be the same Node.
753 // Compute the compatible register masks. 626 // Compute the compatible register masks.
754 bool PhaseConservativeCoalesce::copy_copy( Node *dst_copy, Node *src_copy, Block *b, uint bindex ) { 627 bool PhaseConservativeCoalesce::copy_copy(Node *dst_copy, Node *src_copy, Block *b, uint bindex) {
755 628
756 if( !dst_copy->is_SpillCopy() ) return false; 629 if (!dst_copy->is_SpillCopy()) {
757 if( !src_copy->is_SpillCopy() ) return false; 630 return false;
631 }
632 if (!src_copy->is_SpillCopy()) {
633 return false;
634 }
758 Node *src_def = src_copy->in(src_copy->is_Copy()); 635 Node *src_def = src_copy->in(src_copy->is_Copy());
759 uint lr1 = _phc.Find(dst_copy); 636 uint lr1 = _phc._lrg_map.find(dst_copy);
760 uint lr2 = _phc.Find(src_def ); 637 uint lr2 = _phc._lrg_map.find(src_def);
761 638
762 // Same live ranges already? 639 // Same live ranges already?
763 if( lr1 == lr2 ) return false; 640 if (lr1 == lr2) {
641 return false;
642 }
764 643
765 // Interfere? 644 // Interfere?
766 if( _phc._ifg->test_edge_sq( lr1, lr2 ) ) return false; 645 if (_phc._ifg->test_edge_sq(lr1, lr2)) {
646 return false;
647 }
767 648
768 // Not an oop->int cast; oop->oop, int->int, AND int->oop are OK. 649 // Not an oop->int cast; oop->oop, int->int, AND int->oop are OK.
769 if( !lrgs(lr1)._is_oop && lrgs(lr2)._is_oop ) // not an oop->int cast 650 if (!lrgs(lr1)._is_oop && lrgs(lr2)._is_oop) { // not an oop->int cast
770 return false; 651 return false;
652 }
771 653
772 // Coalescing between an aligned live range and a mis-aligned live range? 654 // Coalescing between an aligned live range and a mis-aligned live range?
773 // No, no! Alignment changes how we count degree. 655 // No, no! Alignment changes how we count degree.
774 if( lrgs(lr1)._fat_proj != lrgs(lr2)._fat_proj ) 656 if (lrgs(lr1)._fat_proj != lrgs(lr2)._fat_proj) {
775 return false; 657 return false;
658 }
776 659
777 // Sort; use smaller live-range number 660 // Sort; use smaller live-range number
778 Node *lr1_node = dst_copy; 661 Node *lr1_node = dst_copy;
779 Node *lr2_node = src_def; 662 Node *lr2_node = src_def;
780 if( lr1 > lr2 ) { 663 if (lr1 > lr2) {
781 uint tmp = lr1; lr1 = lr2; lr2 = tmp; 664 uint tmp = lr1; lr1 = lr2; lr2 = tmp;
782 lr1_node = src_def; lr2_node = dst_copy; 665 lr1_node = src_def; lr2_node = dst_copy;
783 } 666 }
784 667
785 // Check for compatibility of the 2 live ranges by 668 // Check for compatibility of the 2 live ranges by
914 if( copy_copy(copy1,copy1,b,i) ) { 797 if( copy_copy(copy1,copy1,b,i) ) {
915 i--; // Retry, same location in block 798 i--; // Retry, same location in block
916 PhaseChaitin::_conserv_coalesce++; // Collect stats on success 799 PhaseChaitin::_conserv_coalesce++; // Collect stats on success
917 continue; 800 continue;
918 } 801 }
919 802 }
920 /* do not attempt pairs. About 1/2 of all pairs can be removed by 803 }
921 post-alloc. The other set are too few to bother.
922 Node *copy2 = copy1->in(idx1);
923 uint idx2 = copy2->is_Copy();
924 if( !idx2 ) continue;
925 if( copy_copy(copy1,copy2,b,i) ) {
926 i--; // Retry, same location in block
927 PhaseChaitin::_conserv_coalesce_pair++; // Collect stats on success
928 continue;
929 }
930 */
931 }
932 }