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