1 /*
2 * Copyright (c) 1998, 2012, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 *
23 */
24
25 #include "precompiled.hpp"
26 #include "compiler/oopMap.hpp"
27 #include "memory/allocation.inline.hpp"
28 #include "opto/addnode.hpp"
29 #include "opto/block.hpp"
30 #include "opto/callnode.hpp"
31 #include "opto/cfgnode.hpp"
32 #include "opto/chaitin.hpp"
33 #include "opto/coalesce.hpp"
34 #include "opto/connode.hpp"
35 #include "opto/indexSet.hpp"
36 #include "opto/machnode.hpp"
37 #include "opto/memnode.hpp"
38 #include "opto/opcodes.hpp"
39
40 //=============================================================================
41 //------------------------------IFG--------------------------------------------
42 PhaseIFG::PhaseIFG( Arena *arena ) : Phase(Interference_Graph), _arena(arena) {
43 }
44
45 //------------------------------init-------------------------------------------
46 void PhaseIFG::init( uint maxlrg ) {
47 _maxlrg = maxlrg;
48 _yanked = new (_arena) VectorSet(_arena);
49 _is_square = false;
50 // Make uninitialized adjacency lists
51 _adjs = (IndexSet*)_arena->Amalloc(sizeof(IndexSet)*maxlrg);
52 // Also make empty live range structures
53 _lrgs = (LRG *)_arena->Amalloc( maxlrg * sizeof(LRG) );
54 memset(_lrgs,0,sizeof(LRG)*maxlrg);
55 // Init all to empty
56 for( uint i = 0; i < maxlrg; i++ ) {
57 _adjs[i].initialize(maxlrg);
58 _lrgs[i].Set_All();
59 }
60 }
61
62 //------------------------------add--------------------------------------------
63 // Add edge between vertices a & b. These are sorted (triangular matrix),
64 // then the smaller number is inserted in the larger numbered array.
65 int PhaseIFG::add_edge( uint a, uint b ) {
66 lrgs(a).invalid_degree();
67 lrgs(b).invalid_degree();
68 // Sort a and b, so that a is bigger
69 assert( !_is_square, "only on triangular" );
70 if( a < b ) { uint tmp = a; a = b; b = tmp; }
71 return _adjs[a].insert( b );
72 }
73
74 //------------------------------add_vector-------------------------------------
75 // Add an edge between 'a' and everything in the vector.
76 void PhaseIFG::add_vector( uint a, IndexSet *vec ) {
77 // IFG is triangular, so do the inserts where 'a' < 'b'.
78 assert( !_is_square, "only on triangular" );
79 IndexSet *adjs_a = &_adjs[a];
80 if( !vec->count() ) return;
81
82 IndexSetIterator elements(vec);
83 uint neighbor;
84 while ((neighbor = elements.next()) != 0) {
85 add_edge( a, neighbor );
86 }
87 }
88
89 //------------------------------test-------------------------------------------
90 // Is there an edge between a and b?
91 int PhaseIFG::test_edge( uint a, uint b ) const {
92 // Sort a and b, so that a is larger
93 assert( !_is_square, "only on triangular" );
94 if( a < b ) { uint tmp = a; a = b; b = tmp; }
95 return _adjs[a].member(b);
96 }
97
98 //------------------------------SquareUp---------------------------------------
99 // Convert triangular matrix to square matrix
100 void PhaseIFG::SquareUp() {
101 assert( !_is_square, "only on triangular" );
102
103 // Simple transpose
104 for( uint i = 0; i < _maxlrg; i++ ) {
105 IndexSetIterator elements(&_adjs[i]);
106 uint datum;
107 while ((datum = elements.next()) != 0) {
108 _adjs[datum].insert( i );
109 }
110 }
111 _is_square = true;
112 }
113
114 //------------------------------Compute_Effective_Degree-----------------------
115 // Compute effective degree in bulk
116 void PhaseIFG::Compute_Effective_Degree() {
117 assert( _is_square, "only on square" );
118
119 for( uint i = 0; i < _maxlrg; i++ )
120 lrgs(i).set_degree(effective_degree(i));
121 }
122
123 //------------------------------test_edge_sq-----------------------------------
124 int PhaseIFG::test_edge_sq( uint a, uint b ) const {
125 assert( _is_square, "only on square" );
126 // Swap, so that 'a' has the lesser count. Then binary search is on
127 // the smaller of a's list and b's list.
128 if( neighbor_cnt(a) > neighbor_cnt(b) ) { uint tmp = a; a = b; b = tmp; }
129 //return _adjs[a].unordered_member(b);
130 return _adjs[a].member(b);
131 }
132
133 //------------------------------Union------------------------------------------
134 // Union edges of B into A
135 void PhaseIFG::Union( uint a, uint b ) {
136 assert( _is_square, "only on square" );
137 IndexSet *A = &_adjs[a];
138 IndexSetIterator b_elements(&_adjs[b]);
139 uint datum;
140 while ((datum = b_elements.next()) != 0) {
141 if(A->insert(datum)) {
142 _adjs[datum].insert(a);
143 lrgs(a).invalid_degree();
144 lrgs(datum).invalid_degree();
145 }
146 }
147 }
148
149 //------------------------------remove_node------------------------------------
150 // Yank a Node and all connected edges from the IFG. Return a
151 // list of neighbors (edges) yanked.
152 IndexSet *PhaseIFG::remove_node( uint a ) {
153 assert( _is_square, "only on square" );
154 assert( !_yanked->test(a), "" );
155 _yanked->set(a);
156
157 // I remove the LRG from all neighbors.
158 IndexSetIterator elements(&_adjs[a]);
159 LRG &lrg_a = lrgs(a);
160 uint datum;
161 while ((datum = elements.next()) != 0) {
162 _adjs[datum].remove(a);
163 lrgs(datum).inc_degree( -lrg_a.compute_degree(lrgs(datum)) );
164 }
165 return neighbors(a);
166 }
167
168 //------------------------------re_insert--------------------------------------
169 // Re-insert a yanked Node.
170 void PhaseIFG::re_insert( uint a ) {
171 assert( _is_square, "only on square" );
172 assert( _yanked->test(a), "" );
173 (*_yanked) >>= a;
174
175 IndexSetIterator elements(&_adjs[a]);
176 uint datum;
177 while ((datum = elements.next()) != 0) {
178 _adjs[datum].insert(a);
179 lrgs(datum).invalid_degree();
180 }
181 }
182
183 //------------------------------compute_degree---------------------------------
184 // Compute the degree between 2 live ranges. If both live ranges are
185 // aligned-adjacent powers-of-2 then we use the MAX size. If either is
186 // mis-aligned (or for Fat-Projections, not-adjacent) then we have to
187 // MULTIPLY the sizes. Inspect Brigg's thesis on register pairs to see why
188 // this is so.
189 int LRG::compute_degree( LRG &l ) const {
190 int tmp;
191 int num_regs = _num_regs;
192 int nregs = l.num_regs();
193 tmp = (_fat_proj || l._fat_proj) // either is a fat-proj?
194 ? (num_regs * nregs) // then use product
195 : MAX2(num_regs,nregs); // else use max
196 return tmp;
197 }
198
199 //------------------------------effective_degree-------------------------------
200 // Compute effective degree for this live range. If both live ranges are
201 // aligned-adjacent powers-of-2 then we use the MAX size. If either is
202 // mis-aligned (or for Fat-Projections, not-adjacent) then we have to
203 // MULTIPLY the sizes. Inspect Brigg's thesis on register pairs to see why
204 // this is so.
205 int PhaseIFG::effective_degree( uint lidx ) const {
206 int eff = 0;
207 int num_regs = lrgs(lidx).num_regs();
208 int fat_proj = lrgs(lidx)._fat_proj;
209 IndexSet *s = neighbors(lidx);
210 IndexSetIterator elements(s);
211 uint nidx;
212 while((nidx = elements.next()) != 0) {
213 LRG &lrgn = lrgs(nidx);
214 int nregs = lrgn.num_regs();
215 eff += (fat_proj || lrgn._fat_proj) // either is a fat-proj?
216 ? (num_regs * nregs) // then use product
217 : MAX2(num_regs,nregs); // else use max
218 }
219 return eff;
220 }
221
222
223 #ifndef PRODUCT
224 //------------------------------dump-------------------------------------------
225 void PhaseIFG::dump() const {
226 tty->print_cr("-- Interference Graph --%s--",
227 _is_square ? "square" : "triangular" );
228 if( _is_square ) {
229 for( uint i = 0; i < _maxlrg; i++ ) {
230 tty->print( (*_yanked)[i] ? "XX " : " ");
231 tty->print("L%d: { ",i);
232 IndexSetIterator elements(&_adjs[i]);
233 uint datum;
234 while ((datum = elements.next()) != 0) {
235 tty->print("L%d ", datum);
236 }
237 tty->print_cr("}");
238
239 }
240 return;
241 }
242
243 // Triangular
244 for( uint i = 0; i < _maxlrg; i++ ) {
245 uint j;
246 tty->print( (*_yanked)[i] ? "XX " : " ");
247 tty->print("L%d: { ",i);
248 for( j = _maxlrg; j > i; j-- )
249 if( test_edge(j - 1,i) ) {
250 tty->print("L%d ",j - 1);
251 }
252 tty->print("| ");
253 IndexSetIterator elements(&_adjs[i]);
254 uint datum;
255 while ((datum = elements.next()) != 0) {
256 tty->print("L%d ", datum);
257 }
258 tty->print("}\n");
259 }
260 tty->print("\n");
261 }
262
263 //------------------------------stats------------------------------------------
264 void PhaseIFG::stats() const {
265 ResourceMark rm;
266 int *h_cnt = NEW_RESOURCE_ARRAY(int,_maxlrg*2);
267 memset( h_cnt, 0, sizeof(int)*_maxlrg*2 );
268 uint i;
269 for( i = 0; i < _maxlrg; i++ ) {
270 h_cnt[neighbor_cnt(i)]++;
271 }
272 tty->print_cr("--Histogram of counts--");
273 for( i = 0; i < _maxlrg*2; i++ )
274 if( h_cnt[i] )
275 tty->print("%d/%d ",i,h_cnt[i]);
276 tty->print_cr("");
277 }
278
279 //------------------------------verify-----------------------------------------
280 void PhaseIFG::verify( const PhaseChaitin *pc ) const {
281 // IFG is square, sorted and no need for Find
282 for( uint i = 0; i < _maxlrg; i++ ) {
283 assert(!((*_yanked)[i]) || !neighbor_cnt(i), "Is removed completely" );
284 IndexSet *set = &_adjs[i];
285 IndexSetIterator elements(set);
286 uint idx;
287 uint last = 0;
288 while ((idx = elements.next()) != 0) {
289 assert(idx != i, "Must have empty diagonal");
290 assert(pc->_lrg_map.find_const(idx) == idx, "Must not need Find");
291 assert(_adjs[idx].member(i), "IFG not square");
292 assert(!(*_yanked)[idx], "No yanked neighbors");
293 assert(last < idx, "not sorted increasing");
294 last = idx;
295 }
296 assert(!lrgs(i)._degree_valid || effective_degree(i) == lrgs(i).degree(), "degree is valid but wrong");
297 }
298 }
299 #endif
300
301 //------------------------------interfere_with_live----------------------------
302 // Interfere this register with everything currently live. Use the RegMasks
303 // to trim the set of possible interferences. Return a count of register-only
304 // interferences as an estimate of register pressure.
305 void PhaseChaitin::interfere_with_live( uint r, IndexSet *liveout ) {
306 uint retval = 0;
307 // Interfere with everything live.
308 const RegMask &rm = lrgs(r).mask();
309 // Check for interference by checking overlap of regmasks.
310 // Only interfere if acceptable register masks overlap.
311 IndexSetIterator elements(liveout);
312 uint l;
313 while( (l = elements.next()) != 0 )
314 if( rm.overlap( lrgs(l).mask() ) )
315 _ifg->add_edge( r, l );
316 }
317
318 //------------------------------build_ifg_virtual------------------------------
319 // Actually build the interference graph. Uses virtual registers only, no
320 // physical register masks. This allows me to be very aggressive when
321 // coalescing copies. Some of this aggressiveness will have to be undone
322 // later, but I'd rather get all the copies I can now (since unremoved copies
323 // at this point can end up in bad places). Copies I re-insert later I have
324 // more opportunity to insert them in low-frequency locations.
325 void PhaseChaitin::build_ifg_virtual( ) {
326
327 // For all blocks (in any order) do...
328 for( uint i=0; i<_cfg._num_blocks; i++ ) {
329 Block *b = _cfg._blocks[i];
330 IndexSet *liveout = _live->live(b);
331
332 // The IFG is built by a single reverse pass over each basic block.
333 // Starting with the known live-out set, we remove things that get
334 // defined and add things that become live (essentially executing one
335 // pass of a standard LIVE analysis). Just before a Node defines a value
336 // (and removes it from the live-ness set) that value is certainly live.
337 // The defined value interferes with everything currently live. The
338 // value is then removed from the live-ness set and it's inputs are
339 // added to the live-ness set.
340 for( uint j = b->end_idx() + 1; j > 1; j-- ) {
341 Node *n = b->_nodes[j-1];
342
343 // Get value being defined
344 uint r = _lrg_map.live_range_id(n);
345
346 // Some special values do not allocate
347 if (r) {
348
349 // Remove from live-out set
350 liveout->remove(r);
351
352 // Copies do not define a new value and so do not interfere.
353 // Remove the copies source from the liveout set before interfering.
354 uint idx = n->is_Copy();
355 if (idx) {
356 liveout->remove(_lrg_map.live_range_id(n->in(idx)));
357 }
358
359 // Interfere with everything live
360 interfere_with_live(r, liveout);
361 }
362
363 // Make all inputs live
364 if (!n->is_Phi()) { // Phi function uses come from prior block
365 for(uint k = 1; k < n->req(); k++) {
366 liveout->insert(_lrg_map.live_range_id(n->in(k)));
367 }
368 }
369
370 // 2-address instructions always have the defined value live
371 // on entry to the instruction, even though it is being defined
372 // by the instruction. We pretend a virtual copy sits just prior
373 // to the instruction and kills the src-def'd register.
374 // In other words, for 2-address instructions the defined value
375 // interferes with all inputs.
376 uint idx;
377 if( n->is_Mach() && (idx = n->as_Mach()->two_adr()) ) {
378 const MachNode *mach = n->as_Mach();
379 // Sometimes my 2-address ADDs are commuted in a bad way.
380 // We generally want the USE-DEF register to refer to the
381 // loop-varying quantity, to avoid a copy.
382 uint op = mach->ideal_Opcode();
383 // Check that mach->num_opnds() == 3 to ensure instruction is
384 // not subsuming constants, effectively excludes addI_cin_imm
385 // Can NOT swap for instructions like addI_cin_imm since it
386 // is adding zero to yhi + carry and the second ideal-input
387 // points to the result of adding low-halves.
388 // Checking req() and num_opnds() does NOT distinguish addI_cout from addI_cout_imm
389 if( (op == Op_AddI && mach->req() == 3 && mach->num_opnds() == 3) &&
390 n->in(1)->bottom_type()->base() == Type::Int &&
391 // See if the ADD is involved in a tight data loop the wrong way
392 n->in(2)->is_Phi() &&
393 n->in(2)->in(2) == n ) {
394 Node *tmp = n->in(1);
395 n->set_req( 1, n->in(2) );
396 n->set_req( 2, tmp );
397 }
398 // Defined value interferes with all inputs
399 uint lidx = _lrg_map.live_range_id(n->in(idx));
400 for (uint k = 1; k < n->req(); k++) {
401 uint kidx = _lrg_map.live_range_id(n->in(k));
402 if (kidx != lidx) {
403 _ifg->add_edge(r, kidx);
404 }
405 }
406 }
407 } // End of forall instructions in block
408 } // End of forall blocks
409 }
410
411 //------------------------------count_int_pressure-----------------------------
412 uint PhaseChaitin::count_int_pressure( IndexSet *liveout ) {
413 IndexSetIterator elements(liveout);
414 uint lidx;
415 uint cnt = 0;
416 while ((lidx = elements.next()) != 0) {
417 if( lrgs(lidx).mask().is_UP() &&
418 lrgs(lidx).mask_size() &&
419 !lrgs(lidx)._is_float &&
420 !lrgs(lidx)._is_vector &&
421 lrgs(lidx).mask().overlap(*Matcher::idealreg2regmask[Op_RegI]) )
422 cnt += lrgs(lidx).reg_pressure();
423 }
424 return cnt;
425 }
426
427 //------------------------------count_float_pressure---------------------------
428 uint PhaseChaitin::count_float_pressure( IndexSet *liveout ) {
429 IndexSetIterator elements(liveout);
430 uint lidx;
431 uint cnt = 0;
432 while ((lidx = elements.next()) != 0) {
433 if( lrgs(lidx).mask().is_UP() &&
434 lrgs(lidx).mask_size() &&
435 (lrgs(lidx)._is_float || lrgs(lidx)._is_vector))
436 cnt += lrgs(lidx).reg_pressure();
437 }
438 return cnt;
439 }
440
441 //------------------------------lower_pressure---------------------------------
442 // Adjust register pressure down by 1. Capture last hi-to-low transition,
443 static void lower_pressure( LRG *lrg, uint where, Block *b, uint *pressure, uint *hrp_index ) {
444 if (lrg->mask().is_UP() && lrg->mask_size()) {
445 if (lrg->_is_float || lrg->_is_vector) {
446 pressure[1] -= lrg->reg_pressure();
447 if( pressure[1] == (uint)FLOATPRESSURE ) {
448 hrp_index[1] = where;
449 if( pressure[1] > b->_freg_pressure )
450 b->_freg_pressure = pressure[1]+1;
451 }
452 } else if( lrg->mask().overlap(*Matcher::idealreg2regmask[Op_RegI]) ) {
453 pressure[0] -= lrg->reg_pressure();
454 if( pressure[0] == (uint)INTPRESSURE ) {
455 hrp_index[0] = where;
456 if( pressure[0] > b->_reg_pressure )
457 b->_reg_pressure = pressure[0]+1;
458 }
459 }
460 }
461 }
462
463 //------------------------------build_ifg_physical-----------------------------
464 // Build the interference graph using physical registers when available.
465 // That is, if 2 live ranges are simultaneously alive but in their acceptable
466 // register sets do not overlap, then they do not interfere.
467 uint PhaseChaitin::build_ifg_physical( ResourceArea *a ) {
468 NOT_PRODUCT( Compile::TracePhase t3("buildIFG", &_t_buildIFGphysical, TimeCompiler); )
469
470 uint spill_reg = LRG::SPILL_REG;
471 uint must_spill = 0;
472
473 // For all blocks (in any order) do...
474 for( uint i = 0; i < _cfg._num_blocks; i++ ) {
475 Block *b = _cfg._blocks[i];
476 // Clone (rather than smash in place) the liveout info, so it is alive
477 // for the "collect_gc_info" phase later.
478 IndexSet liveout(_live->live(b));
479 uint last_inst = b->end_idx();
480 // Compute first nonphi node index
481 uint first_inst;
482 for( first_inst = 1; first_inst < last_inst; first_inst++ )
483 if( !b->_nodes[first_inst]->is_Phi() )
484 break;
485
486 // Spills could be inserted before CreateEx node which should be
487 // first instruction in block after Phis. Move CreateEx up.
488 for( uint insidx = first_inst; insidx < last_inst; insidx++ ) {
489 Node *ex = b->_nodes[insidx];
490 if( ex->is_SpillCopy() ) continue;
491 if( insidx > first_inst && ex->is_Mach() &&
492 ex->as_Mach()->ideal_Opcode() == Op_CreateEx ) {
493 // If the CreateEx isn't above all the MachSpillCopies
494 // then move it to the top.
495 b->_nodes.remove(insidx);
496 b->_nodes.insert(first_inst, ex);
497 }
498 // Stop once a CreateEx or any other node is found
499 break;
500 }
501
502 // Reset block's register pressure values for each ifg construction
503 uint pressure[2], hrp_index[2];
504 pressure[0] = pressure[1] = 0;
505 hrp_index[0] = hrp_index[1] = last_inst+1;
506 b->_reg_pressure = b->_freg_pressure = 0;
507 // Liveout things are presumed live for the whole block. We accumulate
508 // 'area' accordingly. If they get killed in the block, we'll subtract
509 // the unused part of the block from the area.
510 int inst_count = last_inst - first_inst;
511 double cost = (inst_count <= 0) ? 0.0 : b->_freq * double(inst_count);
512 assert(!(cost < 0.0), "negative spill cost" );
513 IndexSetIterator elements(&liveout);
514 uint lidx;
515 while ((lidx = elements.next()) != 0) {
516 LRG &lrg = lrgs(lidx);
517 lrg._area += cost;
518 // Compute initial register pressure
519 if (lrg.mask().is_UP() && lrg.mask_size()) {
520 if (lrg._is_float || lrg._is_vector) { // Count float pressure
521 pressure[1] += lrg.reg_pressure();
522 if( pressure[1] > b->_freg_pressure )
523 b->_freg_pressure = pressure[1];
524 // Count int pressure, but do not count the SP, flags
525 } else if( lrgs(lidx).mask().overlap(*Matcher::idealreg2regmask[Op_RegI]) ) {
526 pressure[0] += lrg.reg_pressure();
527 if( pressure[0] > b->_reg_pressure )
528 b->_reg_pressure = pressure[0];
529 }
530 }
531 }
532 assert( pressure[0] == count_int_pressure (&liveout), "" );
533 assert( pressure[1] == count_float_pressure(&liveout), "" );
534
535 // The IFG is built by a single reverse pass over each basic block.
536 // Starting with the known live-out set, we remove things that get
537 // defined and add things that become live (essentially executing one
538 // pass of a standard LIVE analysis). Just before a Node defines a value
539 // (and removes it from the live-ness set) that value is certainly live.
540 // The defined value interferes with everything currently live. The
541 // value is then removed from the live-ness set and it's inputs are added
542 // to the live-ness set.
543 uint j;
544 for( j = last_inst + 1; j > 1; j-- ) {
545 Node *n = b->_nodes[j - 1];
546
547 // Get value being defined
548 uint r = _lrg_map.live_range_id(n);
549
550 // Some special values do not allocate
551 if(r) {
552 // A DEF normally costs block frequency; rematerialized values are
553 // removed from the DEF sight, so LOWER costs here.
554 lrgs(r)._cost += n->rematerialize() ? 0 : b->_freq;
555
556 // If it is not live, then this instruction is dead. Probably caused
557 // by spilling and rematerialization. Who cares why, yank this baby.
558 if( !liveout.member(r) && n->Opcode() != Op_SafePoint ) {
559 Node *def = n->in(0);
560 if( !n->is_Proj() ||
561 // Could also be a flags-projection of a dead ADD or such.
562 (_lrg_map.live_range_id(def) && !liveout.member(_lrg_map.live_range_id(def)))) {
563 b->_nodes.remove(j - 1);
564 if (lrgs(r)._def == n) {
565 lrgs(r)._def = 0;
566 }
567 n->disconnect_inputs(NULL, C);
568 _cfg._bbs.map(n->_idx,NULL);
569 n->replace_by(C->top());
570 // Since yanking a Node from block, high pressure moves up one
571 hrp_index[0]--;
572 hrp_index[1]--;
573 continue;
574 }
575
576 // Fat-projections kill many registers which cannot be used to
577 // hold live ranges.
578 if (lrgs(r)._fat_proj) {
579 // Count the int-only registers
580 RegMask itmp = lrgs(r).mask();
581 itmp.AND(*Matcher::idealreg2regmask[Op_RegI]);
582 int iregs = itmp.Size();
583 if( pressure[0]+iregs > b->_reg_pressure )
584 b->_reg_pressure = pressure[0]+iregs;
585 if( pressure[0] <= (uint)INTPRESSURE &&
586 pressure[0]+iregs > (uint)INTPRESSURE ) {
587 hrp_index[0] = j-1;
588 }
589 // Count the float-only registers
590 RegMask ftmp = lrgs(r).mask();
591 ftmp.AND(*Matcher::idealreg2regmask[Op_RegD]);
592 int fregs = ftmp.Size();
593 if( pressure[1]+fregs > b->_freg_pressure )
594 b->_freg_pressure = pressure[1]+fregs;
595 if( pressure[1] <= (uint)FLOATPRESSURE &&
596 pressure[1]+fregs > (uint)FLOATPRESSURE ) {
597 hrp_index[1] = j-1;
598 }
599 }
600
601 } else { // Else it is live
602 // A DEF also ends 'area' partway through the block.
603 lrgs(r)._area -= cost;
604 assert(!(lrgs(r)._area < 0.0), "negative spill area" );
605
606 // Insure high score for immediate-use spill copies so they get a color
607 if( n->is_SpillCopy()
608 && lrgs(r).is_singledef() // MultiDef live range can still split
609 && n->outcnt() == 1 // and use must be in this block
610 && _cfg._bbs[n->unique_out()->_idx] == b ) {
611 // All single-use MachSpillCopy(s) that immediately precede their
612 // use must color early. If a longer live range steals their
613 // color, the spill copy will split and may push another spill copy
614 // further away resulting in an infinite spill-split-retry cycle.
615 // Assigning a zero area results in a high score() and a good
616 // location in the simplify list.
617 //
618
619 Node *single_use = n->unique_out();
620 assert( b->find_node(single_use) >= j, "Use must be later in block");
621 // Use can be earlier in block if it is a Phi, but then I should be a MultiDef
622
623 // Find first non SpillCopy 'm' that follows the current instruction
624 // (j - 1) is index for current instruction 'n'
625 Node *m = n;
626 for( uint i = j; i <= last_inst && m->is_SpillCopy(); ++i ) { m = b->_nodes[i]; }
627 if( m == single_use ) {
628 lrgs(r)._area = 0.0;
629 }
630 }
631
632 // Remove from live-out set
633 if( liveout.remove(r) ) {
634 // Adjust register pressure.
635 // Capture last hi-to-lo pressure transition
636 lower_pressure( &lrgs(r), j-1, b, pressure, hrp_index );
637 assert( pressure[0] == count_int_pressure (&liveout), "" );
638 assert( pressure[1] == count_float_pressure(&liveout), "" );
639 }
640
641 // Copies do not define a new value and so do not interfere.
642 // Remove the copies source from the liveout set before interfering.
643 uint idx = n->is_Copy();
644 if (idx) {
645 uint x = _lrg_map.live_range_id(n->in(idx));
646 if (liveout.remove(x)) {
647 lrgs(x)._area -= cost;
648 // Adjust register pressure.
649 lower_pressure(&lrgs(x), j-1, b, pressure, hrp_index);
650 assert( pressure[0] == count_int_pressure (&liveout), "" );
651 assert( pressure[1] == count_float_pressure(&liveout), "" );
652 }
653 }
654 } // End of if live or not
655
656 // Interfere with everything live. If the defined value must
657 // go in a particular register, just remove that register from
658 // all conflicting parties and avoid the interference.
659
660 // Make exclusions for rematerializable defs. Since rematerializable
661 // DEFs are not bound but the live range is, some uses must be bound.
662 // If we spill live range 'r', it can rematerialize at each use site
663 // according to its bindings.
664 const RegMask &rmask = lrgs(r).mask();
665 if( lrgs(r).is_bound() && !(n->rematerialize()) && rmask.is_NotEmpty() ) {
666 // Check for common case
667 int r_size = lrgs(r).num_regs();
668 OptoReg::Name r_reg = (r_size == 1) ? rmask.find_first_elem() : OptoReg::Physical;
669 // Smear odd bits
670 IndexSetIterator elements(&liveout);
671 uint l;
672 while ((l = elements.next()) != 0) {
673 LRG &lrg = lrgs(l);
674 // If 'l' must spill already, do not further hack his bits.
675 // He'll get some interferences and be forced to spill later.
676 if( lrg._must_spill ) continue;
677 // Remove bound register(s) from 'l's choices
678 RegMask old = lrg.mask();
679 uint old_size = lrg.mask_size();
680 // Remove the bits from LRG 'r' from LRG 'l' so 'l' no
681 // longer interferes with 'r'. If 'l' requires aligned
682 // adjacent pairs, subtract out bit pairs.
683 assert(!lrg._is_vector || !lrg._fat_proj, "sanity");
684 if (lrg.num_regs() > 1 && !lrg._fat_proj) {
685 RegMask r2mask = rmask;
686 // Leave only aligned set of bits.
687 r2mask.smear_to_sets(lrg.num_regs());
688 // It includes vector case.
689 lrg.SUBTRACT( r2mask );
690 lrg.compute_set_mask_size();
691 } else if( r_size != 1 ) { // fat proj
692 lrg.SUBTRACT( rmask );
693 lrg.compute_set_mask_size();
694 } else { // Common case: size 1 bound removal
695 if( lrg.mask().Member(r_reg) ) {
696 lrg.Remove(r_reg);
697 lrg.set_mask_size(lrg.mask().is_AllStack() ? 65535:old_size-1);
698 }
699 }
700 // If 'l' goes completely dry, it must spill.
701 if( lrg.not_free() ) {
702 // Give 'l' some kind of reasonable mask, so he picks up
703 // interferences (and will spill later).
704 lrg.set_mask( old );
705 lrg.set_mask_size(old_size);
706 must_spill++;
707 lrg._must_spill = 1;
708 lrg.set_reg(OptoReg::Name(LRG::SPILL_REG));
709 }
710 }
711 } // End of if bound
712
713 // Now interference with everything that is live and has
714 // compatible register sets.
715 interfere_with_live(r,&liveout);
716
717 } // End of if normal register-allocated value
718
719 // Area remaining in the block
720 inst_count--;
721 cost = (inst_count <= 0) ? 0.0 : b->_freq * double(inst_count);
722
723 // Make all inputs live
724 if( !n->is_Phi() ) { // Phi function uses come from prior block
725 JVMState* jvms = n->jvms();
726 uint debug_start = jvms ? jvms->debug_start() : 999999;
727 // Start loop at 1 (skip control edge) for most Nodes.
728 // SCMemProj's might be the sole use of a StoreLConditional.
729 // While StoreLConditionals set memory (the SCMemProj use)
730 // they also def flags; if that flag def is unused the
731 // allocator sees a flag-setting instruction with no use of
732 // the flags and assumes it's dead. This keeps the (useless)
733 // flag-setting behavior alive while also keeping the (useful)
734 // memory update effect.
735 for (uint k = ((n->Opcode() == Op_SCMemProj) ? 0:1); k < n->req(); k++) {
736 Node *def = n->in(k);
737 uint x = _lrg_map.live_range_id(def);
738 if (!x) {
739 continue;
740 }
741 LRG &lrg = lrgs(x);
742 // No use-side cost for spilling debug info
743 if (k < debug_start) {
744 // A USE costs twice block frequency (once for the Load, once
745 // for a Load-delay). Rematerialized uses only cost once.
746 lrg._cost += (def->rematerialize() ? b->_freq : (b->_freq + b->_freq));
747 }
748 // It is live now
749 if (liveout.insert(x)) {
750 // Newly live things assumed live from here to top of block
751 lrg._area += cost;
752 // Adjust register pressure
753 if (lrg.mask().is_UP() && lrg.mask_size()) {
754 if (lrg._is_float || lrg._is_vector) {
755 pressure[1] += lrg.reg_pressure();
756 if( pressure[1] > b->_freg_pressure )
757 b->_freg_pressure = pressure[1];
758 } else if( lrg.mask().overlap(*Matcher::idealreg2regmask[Op_RegI]) ) {
759 pressure[0] += lrg.reg_pressure();
760 if( pressure[0] > b->_reg_pressure )
761 b->_reg_pressure = pressure[0];
762 }
763 }
764 assert( pressure[0] == count_int_pressure (&liveout), "" );
765 assert( pressure[1] == count_float_pressure(&liveout), "" );
766 }
767 assert(!(lrg._area < 0.0), "negative spill area" );
768 }
769 }
770 } // End of reverse pass over all instructions in block
771
772 // If we run off the top of the block with high pressure and
773 // never see a hi-to-low pressure transition, just record that
774 // the whole block is high pressure.
775 if( pressure[0] > (uint)INTPRESSURE ) {
776 hrp_index[0] = 0;
777 if( pressure[0] > b->_reg_pressure )
778 b->_reg_pressure = pressure[0];
779 }
780 if( pressure[1] > (uint)FLOATPRESSURE ) {
781 hrp_index[1] = 0;
782 if( pressure[1] > b->_freg_pressure )
783 b->_freg_pressure = pressure[1];
784 }
785
786 // Compute high pressure indice; avoid landing in the middle of projnodes
787 j = hrp_index[0];
788 if( j < b->_nodes.size() && j < b->end_idx()+1 ) {
789 Node *cur = b->_nodes[j];
790 while( cur->is_Proj() || (cur->is_MachNullCheck()) || cur->is_Catch() ) {
791 j--;
792 cur = b->_nodes[j];
793 }
794 }
795 b->_ihrp_index = j;
796 j = hrp_index[1];
797 if( j < b->_nodes.size() && j < b->end_idx()+1 ) {
798 Node *cur = b->_nodes[j];
799 while( cur->is_Proj() || (cur->is_MachNullCheck()) || cur->is_Catch() ) {
800 j--;
801 cur = b->_nodes[j];
802 }
803 }
804 b->_fhrp_index = j;
805
806 #ifndef PRODUCT
807 // Gather Register Pressure Statistics
808 if( PrintOptoStatistics ) {
809 if( b->_reg_pressure > (uint)INTPRESSURE || b->_freg_pressure > (uint)FLOATPRESSURE )
810 _high_pressure++;
811 else
812 _low_pressure++;
813 }
814 #endif
815 } // End of for all blocks
816
817 return must_spill;
818 }