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