Mercurial > hg > truffle
annotate src/share/vm/opto/ifg.cpp @ 4710:41406797186b
7113012: G1: rename not-fully-young GCs as "mixed"
Summary: Renamed partially-young GCs as mixed and fully-young GCs as young. Change all external output that includes those terms (GC log and GC ergo log) as well as any comments, fields, methods, etc. The changeset also includes very minor code tidying up (added some curly brackets).
Reviewed-by: johnc, brutisso
author | tonyp |
---|---|
date | Fri, 16 Dec 2011 02:14:27 -0500 |
parents | f95d63e2154a |
children | 8c92982cbbc4 |
rev | line source |
---|---|
0 | 1 /* |
1552
c18cbe5936b8
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
1212
diff
changeset
|
2 * Copyright (c) 1998, 2010, Oracle and/or its affiliates. All rights reserved. |
0 | 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 * | |
1552
c18cbe5936b8
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
1212
diff
changeset
|
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA |
c18cbe5936b8
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
1212
diff
changeset
|
20 * or visit www.oracle.com if you need additional information or have any |
c18cbe5936b8
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
1212
diff
changeset
|
21 * questions. |
0 | 22 * |
23 */ | |
24 | |
1972 | 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" | |
0 | 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 | |
605 | 307 // interferences as an estimate of register pressure. |
0 | 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).mask().overlap(*Matcher::idealreg2regmask[Op_RegI]) ) | |
420 cnt += lrgs(lidx).reg_pressure(); | |
421 } | |
422 return cnt; | |
423 } | |
424 | |
425 //------------------------------count_float_pressure--------------------------- | |
426 uint PhaseChaitin::count_float_pressure( IndexSet *liveout ) { | |
427 IndexSetIterator elements(liveout); | |
428 uint lidx; | |
429 uint cnt = 0; | |
430 while ((lidx = elements.next()) != 0) { | |
431 if( lrgs(lidx).mask().is_UP() && | |
432 lrgs(lidx).mask_size() && | |
433 lrgs(lidx)._is_float ) | |
434 cnt += lrgs(lidx).reg_pressure(); | |
435 } | |
436 return cnt; | |
437 } | |
438 | |
439 //------------------------------lower_pressure--------------------------------- | |
440 // Adjust register pressure down by 1. Capture last hi-to-low transition, | |
441 static void lower_pressure( LRG *lrg, uint where, Block *b, uint *pressure, uint *hrp_index ) { | |
442 if( lrg->mask().is_UP() && lrg->mask_size() ) { | |
443 if( lrg->_is_float ) { | |
444 pressure[1] -= lrg->reg_pressure(); | |
445 if( pressure[1] == (uint)FLOATPRESSURE ) { | |
446 hrp_index[1] = where; | |
447 #ifdef EXACT_PRESSURE | |
448 if( pressure[1] > b->_freg_pressure ) | |
449 b->_freg_pressure = pressure[1]+1; | |
450 #else | |
451 b->_freg_pressure = (uint)FLOATPRESSURE+1; | |
452 #endif | |
453 } | |
454 } else if( lrg->mask().overlap(*Matcher::idealreg2regmask[Op_RegI]) ) { | |
455 pressure[0] -= lrg->reg_pressure(); | |
456 if( pressure[0] == (uint)INTPRESSURE ) { | |
457 hrp_index[0] = where; | |
458 #ifdef EXACT_PRESSURE | |
459 if( pressure[0] > b->_reg_pressure ) | |
460 b->_reg_pressure = pressure[0]+1; | |
461 #else | |
462 b->_reg_pressure = (uint)INTPRESSURE+1; | |
463 #endif | |
464 } | |
465 } | |
466 } | |
467 } | |
468 | |
469 //------------------------------build_ifg_physical----------------------------- | |
470 // Build the interference graph using physical registers when available. | |
471 // That is, if 2 live ranges are simultaneously alive but in their acceptable | |
472 // register sets do not overlap, then they do not interfere. | |
473 uint PhaseChaitin::build_ifg_physical( ResourceArea *a ) { | |
474 NOT_PRODUCT( Compile::TracePhase t3("buildIFG", &_t_buildIFGphysical, TimeCompiler); ) | |
475 | |
476 uint spill_reg = LRG::SPILL_REG; | |
477 uint must_spill = 0; | |
478 | |
479 // For all blocks (in any order) do... | |
480 for( uint i = 0; i < _cfg._num_blocks; i++ ) { | |
481 Block *b = _cfg._blocks[i]; | |
482 // Clone (rather than smash in place) the liveout info, so it is alive | |
483 // for the "collect_gc_info" phase later. | |
484 IndexSet liveout(_live->live(b)); | |
485 uint last_inst = b->end_idx(); | |
566
91263420e1c6
6791852: assert(b->_nodes[insidx] == n,"got insidx set incorrectly")
kvn
parents:
380
diff
changeset
|
486 // Compute first nonphi node index |
91263420e1c6
6791852: assert(b->_nodes[insidx] == n,"got insidx set incorrectly")
kvn
parents:
380
diff
changeset
|
487 uint first_inst; |
91263420e1c6
6791852: assert(b->_nodes[insidx] == n,"got insidx set incorrectly")
kvn
parents:
380
diff
changeset
|
488 for( first_inst = 1; first_inst < last_inst; first_inst++ ) |
91263420e1c6
6791852: assert(b->_nodes[insidx] == n,"got insidx set incorrectly")
kvn
parents:
380
diff
changeset
|
489 if( !b->_nodes[first_inst]->is_Phi() ) |
0 | 490 break; |
491 | |
566
91263420e1c6
6791852: assert(b->_nodes[insidx] == n,"got insidx set incorrectly")
kvn
parents:
380
diff
changeset
|
492 // Spills could be inserted before CreateEx node which should be |
91263420e1c6
6791852: assert(b->_nodes[insidx] == n,"got insidx set incorrectly")
kvn
parents:
380
diff
changeset
|
493 // first instruction in block after Phis. Move CreateEx up. |
91263420e1c6
6791852: assert(b->_nodes[insidx] == n,"got insidx set incorrectly")
kvn
parents:
380
diff
changeset
|
494 for( uint insidx = first_inst; insidx < last_inst; insidx++ ) { |
91263420e1c6
6791852: assert(b->_nodes[insidx] == n,"got insidx set incorrectly")
kvn
parents:
380
diff
changeset
|
495 Node *ex = b->_nodes[insidx]; |
91263420e1c6
6791852: assert(b->_nodes[insidx] == n,"got insidx set incorrectly")
kvn
parents:
380
diff
changeset
|
496 if( ex->is_SpillCopy() ) continue; |
91263420e1c6
6791852: assert(b->_nodes[insidx] == n,"got insidx set incorrectly")
kvn
parents:
380
diff
changeset
|
497 if( insidx > first_inst && ex->is_Mach() && |
91263420e1c6
6791852: assert(b->_nodes[insidx] == n,"got insidx set incorrectly")
kvn
parents:
380
diff
changeset
|
498 ex->as_Mach()->ideal_Opcode() == Op_CreateEx ) { |
91263420e1c6
6791852: assert(b->_nodes[insidx] == n,"got insidx set incorrectly")
kvn
parents:
380
diff
changeset
|
499 // If the CreateEx isn't above all the MachSpillCopies |
91263420e1c6
6791852: assert(b->_nodes[insidx] == n,"got insidx set incorrectly")
kvn
parents:
380
diff
changeset
|
500 // then move it to the top. |
91263420e1c6
6791852: assert(b->_nodes[insidx] == n,"got insidx set incorrectly")
kvn
parents:
380
diff
changeset
|
501 b->_nodes.remove(insidx); |
91263420e1c6
6791852: assert(b->_nodes[insidx] == n,"got insidx set incorrectly")
kvn
parents:
380
diff
changeset
|
502 b->_nodes.insert(first_inst, ex); |
91263420e1c6
6791852: assert(b->_nodes[insidx] == n,"got insidx set incorrectly")
kvn
parents:
380
diff
changeset
|
503 } |
91263420e1c6
6791852: assert(b->_nodes[insidx] == n,"got insidx set incorrectly")
kvn
parents:
380
diff
changeset
|
504 // Stop once a CreateEx or any other node is found |
91263420e1c6
6791852: assert(b->_nodes[insidx] == n,"got insidx set incorrectly")
kvn
parents:
380
diff
changeset
|
505 break; |
91263420e1c6
6791852: assert(b->_nodes[insidx] == n,"got insidx set incorrectly")
kvn
parents:
380
diff
changeset
|
506 } |
91263420e1c6
6791852: assert(b->_nodes[insidx] == n,"got insidx set incorrectly")
kvn
parents:
380
diff
changeset
|
507 |
0 | 508 // Reset block's register pressure values for each ifg construction |
509 uint pressure[2], hrp_index[2]; | |
510 pressure[0] = pressure[1] = 0; | |
511 hrp_index[0] = hrp_index[1] = last_inst+1; | |
512 b->_reg_pressure = b->_freg_pressure = 0; | |
513 // Liveout things are presumed live for the whole block. We accumulate | |
514 // 'area' accordingly. If they get killed in the block, we'll subtract | |
515 // the unused part of the block from the area. | |
566
91263420e1c6
6791852: assert(b->_nodes[insidx] == n,"got insidx set incorrectly")
kvn
parents:
380
diff
changeset
|
516 int inst_count = last_inst - first_inst; |
369
5f85534046c2
6750588: assert(lrg._area >= 0,"negative spill area") running NSK stmp0101 test
rasbold
parents:
295
diff
changeset
|
517 double cost = (inst_count <= 0) ? 0.0 : b->_freq * double(inst_count); |
5f85534046c2
6750588: assert(lrg._area >= 0,"negative spill area") running NSK stmp0101 test
rasbold
parents:
295
diff
changeset
|
518 assert(!(cost < 0.0), "negative spill cost" ); |
0 | 519 IndexSetIterator elements(&liveout); |
520 uint lidx; | |
521 while ((lidx = elements.next()) != 0) { | |
522 LRG &lrg = lrgs(lidx); | |
523 lrg._area += cost; | |
524 // Compute initial register pressure | |
525 if( lrg.mask().is_UP() && lrg.mask_size() ) { | |
526 if( lrg._is_float ) { // Count float pressure | |
527 pressure[1] += lrg.reg_pressure(); | |
528 #ifdef EXACT_PRESSURE | |
529 if( pressure[1] > b->_freg_pressure ) | |
530 b->_freg_pressure = pressure[1]; | |
531 #endif | |
532 // Count int pressure, but do not count the SP, flags | |
533 } else if( lrgs(lidx).mask().overlap(*Matcher::idealreg2regmask[Op_RegI]) ) { | |
534 pressure[0] += lrg.reg_pressure(); | |
535 #ifdef EXACT_PRESSURE | |
536 if( pressure[0] > b->_reg_pressure ) | |
537 b->_reg_pressure = pressure[0]; | |
538 #endif | |
539 } | |
540 } | |
541 } | |
542 assert( pressure[0] == count_int_pressure (&liveout), "" ); | |
543 assert( pressure[1] == count_float_pressure(&liveout), "" ); | |
544 | |
545 // The IFG is built by a single reverse pass over each basic block. | |
546 // Starting with the known live-out set, we remove things that get | |
547 // defined and add things that become live (essentially executing one | |
548 // pass of a standard LIVE analysis). Just before a Node defines a value | |
549 // (and removes it from the live-ness set) that value is certainly live. | |
550 // The defined value interferes with everything currently live. The | |
551 // value is then removed from the live-ness set and it's inputs are added | |
552 // to the live-ness set. | |
553 uint j; | |
554 for( j = last_inst + 1; j > 1; j-- ) { | |
555 Node *n = b->_nodes[j - 1]; | |
556 | |
557 // Get value being defined | |
558 uint r = n2lidx(n); | |
559 | |
560 // Some special values do not allocate | |
561 if( r ) { | |
562 // A DEF normally costs block frequency; rematerialized values are | |
563 // removed from the DEF sight, so LOWER costs here. | |
564 lrgs(r)._cost += n->rematerialize() ? 0 : b->_freq; | |
565 | |
566 // If it is not live, then this instruction is dead. Probably caused | |
567 // by spilling and rematerialization. Who cares why, yank this baby. | |
568 if( !liveout.member(r) && n->Opcode() != Op_SafePoint ) { | |
569 Node *def = n->in(0); | |
570 if( !n->is_Proj() || | |
571 // Could also be a flags-projection of a dead ADD or such. | |
572 (n2lidx(def) && !liveout.member(n2lidx(def)) ) ) { | |
573 b->_nodes.remove(j - 1); | |
574 if( lrgs(r)._def == n ) lrgs(r)._def = 0; | |
575 n->disconnect_inputs(NULL); | |
576 _cfg._bbs.map(n->_idx,NULL); | |
577 n->replace_by(C->top()); | |
578 // Since yanking a Node from block, high pressure moves up one | |
579 hrp_index[0]--; | |
580 hrp_index[1]--; | |
581 continue; | |
582 } | |
583 | |
584 // Fat-projections kill many registers which cannot be used to | |
585 // hold live ranges. | |
586 if( lrgs(r)._fat_proj ) { | |
587 // Count the int-only registers | |
588 RegMask itmp = lrgs(r).mask(); | |
589 itmp.AND(*Matcher::idealreg2regmask[Op_RegI]); | |
590 int iregs = itmp.Size(); | |
591 #ifdef EXACT_PRESSURE | |
592 if( pressure[0]+iregs > b->_reg_pressure ) | |
593 b->_reg_pressure = pressure[0]+iregs; | |
594 #endif | |
595 if( pressure[0] <= (uint)INTPRESSURE && | |
596 pressure[0]+iregs > (uint)INTPRESSURE ) { | |
597 #ifndef EXACT_PRESSURE | |
598 b->_reg_pressure = (uint)INTPRESSURE+1; | |
599 #endif | |
600 hrp_index[0] = j-1; | |
601 } | |
602 // Count the float-only registers | |
603 RegMask ftmp = lrgs(r).mask(); | |
604 ftmp.AND(*Matcher::idealreg2regmask[Op_RegD]); | |
605 int fregs = ftmp.Size(); | |
606 #ifdef EXACT_PRESSURE | |
607 if( pressure[1]+fregs > b->_freg_pressure ) | |
608 b->_freg_pressure = pressure[1]+fregs; | |
609 #endif | |
610 if( pressure[1] <= (uint)FLOATPRESSURE && | |
611 pressure[1]+fregs > (uint)FLOATPRESSURE ) { | |
612 #ifndef EXACT_PRESSURE | |
613 b->_freg_pressure = (uint)FLOATPRESSURE+1; | |
614 #endif | |
615 hrp_index[1] = j-1; | |
616 } | |
617 } | |
618 | |
619 } else { // Else it is live | |
620 // A DEF also ends 'area' partway through the block. | |
621 lrgs(r)._area -= cost; | |
369
5f85534046c2
6750588: assert(lrg._area >= 0,"negative spill area") running NSK stmp0101 test
rasbold
parents:
295
diff
changeset
|
622 assert(!(lrgs(r)._area < 0.0), "negative spill area" ); |
0 | 623 |
624 // Insure high score for immediate-use spill copies so they get a color | |
625 if( n->is_SpillCopy() | |
295
ea18057223c4
6732194: Data corruption dependent on -server/-client/-Xbatch
never
parents:
0
diff
changeset
|
626 && lrgs(r).is_singledef() // MultiDef live range can still split |
0 | 627 && n->outcnt() == 1 // and use must be in this block |
628 && _cfg._bbs[n->unique_out()->_idx] == b ) { | |
629 // All single-use MachSpillCopy(s) that immediately precede their | |
630 // use must color early. If a longer live range steals their | |
631 // color, the spill copy will split and may push another spill copy | |
632 // further away resulting in an infinite spill-split-retry cycle. | |
633 // Assigning a zero area results in a high score() and a good | |
634 // location in the simplify list. | |
635 // | |
636 | |
637 Node *single_use = n->unique_out(); | |
638 assert( b->find_node(single_use) >= j, "Use must be later in block"); | |
639 // Use can be earlier in block if it is a Phi, but then I should be a MultiDef | |
640 | |
641 // Find first non SpillCopy 'm' that follows the current instruction | |
642 // (j - 1) is index for current instruction 'n' | |
643 Node *m = n; | |
644 for( uint i = j; i <= last_inst && m->is_SpillCopy(); ++i ) { m = b->_nodes[i]; } | |
645 if( m == single_use ) { | |
646 lrgs(r)._area = 0.0; | |
647 } | |
648 } | |
649 | |
650 // Remove from live-out set | |
651 if( liveout.remove(r) ) { | |
652 // Adjust register pressure. | |
653 // Capture last hi-to-lo pressure transition | |
654 lower_pressure( &lrgs(r), j-1, b, pressure, hrp_index ); | |
655 assert( pressure[0] == count_int_pressure (&liveout), "" ); | |
656 assert( pressure[1] == count_float_pressure(&liveout), "" ); | |
657 } | |
658 | |
659 // Copies do not define a new value and so do not interfere. | |
660 // Remove the copies source from the liveout set before interfering. | |
661 uint idx = n->is_Copy(); | |
662 if( idx ) { | |
663 uint x = n2lidx(n->in(idx)); | |
664 if( liveout.remove( x ) ) { | |
665 lrgs(x)._area -= cost; | |
666 // Adjust register pressure. | |
667 lower_pressure( &lrgs(x), j-1, b, pressure, hrp_index ); | |
668 assert( pressure[0] == count_int_pressure (&liveout), "" ); | |
669 assert( pressure[1] == count_float_pressure(&liveout), "" ); | |
670 } | |
671 } | |
672 } // End of if live or not | |
673 | |
674 // Interfere with everything live. If the defined value must | |
675 // go in a particular register, just remove that register from | |
676 // all conflicting parties and avoid the interference. | |
677 | |
678 // Make exclusions for rematerializable defs. Since rematerializable | |
679 // DEFs are not bound but the live range is, some uses must be bound. | |
680 // If we spill live range 'r', it can rematerialize at each use site | |
681 // according to its bindings. | |
682 const RegMask &rmask = lrgs(r).mask(); | |
683 if( lrgs(r).is_bound() && !(n->rematerialize()) && rmask.is_NotEmpty() ) { | |
684 // Smear odd bits; leave only aligned pairs of bits. | |
685 RegMask r2mask = rmask; | |
686 r2mask.SmearToPairs(); | |
687 // Check for common case | |
688 int r_size = lrgs(r).num_regs(); | |
689 OptoReg::Name r_reg = (r_size == 1) ? rmask.find_first_elem() : OptoReg::Physical; | |
690 | |
691 IndexSetIterator elements(&liveout); | |
692 uint l; | |
693 while ((l = elements.next()) != 0) { | |
694 LRG &lrg = lrgs(l); | |
695 // If 'l' must spill already, do not further hack his bits. | |
696 // He'll get some interferences and be forced to spill later. | |
697 if( lrg._must_spill ) continue; | |
698 // Remove bound register(s) from 'l's choices | |
699 RegMask old = lrg.mask(); | |
700 uint old_size = lrg.mask_size(); | |
701 // Remove the bits from LRG 'r' from LRG 'l' so 'l' no | |
702 // longer interferes with 'r'. If 'l' requires aligned | |
703 // adjacent pairs, subtract out bit pairs. | |
704 if( lrg.num_regs() == 2 && !lrg._fat_proj ) { | |
705 lrg.SUBTRACT( r2mask ); | |
706 lrg.compute_set_mask_size(); | |
707 } else if( r_size != 1 ) { | |
708 lrg.SUBTRACT( rmask ); | |
709 lrg.compute_set_mask_size(); | |
710 } else { // Common case: size 1 bound removal | |
711 if( lrg.mask().Member(r_reg) ) { | |
712 lrg.Remove(r_reg); | |
713 lrg.set_mask_size(lrg.mask().is_AllStack() ? 65535:old_size-1); | |
714 } | |
715 } | |
716 // If 'l' goes completely dry, it must spill. | |
717 if( lrg.not_free() ) { | |
718 // Give 'l' some kind of reasonable mask, so he picks up | |
719 // interferences (and will spill later). | |
720 lrg.set_mask( old ); | |
721 lrg.set_mask_size(old_size); | |
722 must_spill++; | |
723 lrg._must_spill = 1; | |
724 lrg.set_reg(OptoReg::Name(LRG::SPILL_REG)); | |
725 } | |
726 } | |
727 } // End of if bound | |
728 | |
729 // Now interference with everything that is live and has | |
730 // compatible register sets. | |
731 interfere_with_live(r,&liveout); | |
732 | |
733 } // End of if normal register-allocated value | |
734 | |
369
5f85534046c2
6750588: assert(lrg._area >= 0,"negative spill area") running NSK stmp0101 test
rasbold
parents:
295
diff
changeset
|
735 // Area remaining in the block |
5f85534046c2
6750588: assert(lrg._area >= 0,"negative spill area") running NSK stmp0101 test
rasbold
parents:
295
diff
changeset
|
736 inst_count--; |
5f85534046c2
6750588: assert(lrg._area >= 0,"negative spill area") running NSK stmp0101 test
rasbold
parents:
295
diff
changeset
|
737 cost = (inst_count <= 0) ? 0.0 : b->_freq * double(inst_count); |
0 | 738 |
739 // Make all inputs live | |
740 if( !n->is_Phi() ) { // Phi function uses come from prior block | |
741 JVMState* jvms = n->jvms(); | |
742 uint debug_start = jvms ? jvms->debug_start() : 999999; | |
743 // Start loop at 1 (skip control edge) for most Nodes. | |
744 // SCMemProj's might be the sole use of a StoreLConditional. | |
745 // While StoreLConditionals set memory (the SCMemProj use) | |
746 // they also def flags; if that flag def is unused the | |
747 // allocator sees a flag-setting instruction with no use of | |
748 // the flags and assumes it's dead. This keeps the (useless) | |
749 // flag-setting behavior alive while also keeping the (useful) | |
750 // memory update effect. | |
1212 | 751 for( uint k = ((n->Opcode() == Op_SCMemProj) ? 0:1); k < n->req(); k++ ) { |
0 | 752 Node *def = n->in(k); |
753 uint x = n2lidx(def); | |
754 if( !x ) continue; | |
755 LRG &lrg = lrgs(x); | |
756 // No use-side cost for spilling debug info | |
757 if( k < debug_start ) | |
758 // A USE costs twice block frequency (once for the Load, once | |
759 // for a Load-delay). Rematerialized uses only cost once. | |
760 lrg._cost += (def->rematerialize() ? b->_freq : (b->_freq + b->_freq)); | |
761 // It is live now | |
762 if( liveout.insert( x ) ) { | |
763 // Newly live things assumed live from here to top of block | |
764 lrg._area += cost; | |
765 // Adjust register pressure | |
766 if( lrg.mask().is_UP() && lrg.mask_size() ) { | |
767 if( lrg._is_float ) { | |
768 pressure[1] += lrg.reg_pressure(); | |
769 #ifdef EXACT_PRESSURE | |
770 if( pressure[1] > b->_freg_pressure ) | |
771 b->_freg_pressure = pressure[1]; | |
772 #endif | |
773 } else if( lrg.mask().overlap(*Matcher::idealreg2regmask[Op_RegI]) ) { | |
774 pressure[0] += lrg.reg_pressure(); | |
775 #ifdef EXACT_PRESSURE | |
776 if( pressure[0] > b->_reg_pressure ) | |
777 b->_reg_pressure = pressure[0]; | |
778 #endif | |
779 } | |
780 } | |
781 assert( pressure[0] == count_int_pressure (&liveout), "" ); | |
782 assert( pressure[1] == count_float_pressure(&liveout), "" ); | |
783 } | |
369
5f85534046c2
6750588: assert(lrg._area >= 0,"negative spill area") running NSK stmp0101 test
rasbold
parents:
295
diff
changeset
|
784 assert(!(lrg._area < 0.0), "negative spill area" ); |
0 | 785 } |
786 } | |
787 } // End of reverse pass over all instructions in block | |
788 | |
789 // If we run off the top of the block with high pressure and | |
790 // never see a hi-to-low pressure transition, just record that | |
791 // the whole block is high pressure. | |
792 if( pressure[0] > (uint)INTPRESSURE ) { | |
793 hrp_index[0] = 0; | |
794 #ifdef EXACT_PRESSURE | |
795 if( pressure[0] > b->_reg_pressure ) | |
796 b->_reg_pressure = pressure[0]; | |
797 #else | |
798 b->_reg_pressure = (uint)INTPRESSURE+1; | |
799 #endif | |
800 } | |
801 if( pressure[1] > (uint)FLOATPRESSURE ) { | |
802 hrp_index[1] = 0; | |
803 #ifdef EXACT_PRESSURE | |
804 if( pressure[1] > b->_freg_pressure ) | |
805 b->_freg_pressure = pressure[1]; | |
806 #else | |
807 b->_freg_pressure = (uint)FLOATPRESSURE+1; | |
808 #endif | |
809 } | |
810 | |
811 // Compute high pressure indice; avoid landing in the middle of projnodes | |
812 j = hrp_index[0]; | |
813 if( j < b->_nodes.size() && j < b->end_idx()+1 ) { | |
814 Node *cur = b->_nodes[j]; | |
815 while( cur->is_Proj() || (cur->is_MachNullCheck()) || cur->is_Catch() ) { | |
816 j--; | |
817 cur = b->_nodes[j]; | |
818 } | |
819 } | |
820 b->_ihrp_index = j; | |
821 j = hrp_index[1]; | |
822 if( j < b->_nodes.size() && j < b->end_idx()+1 ) { | |
823 Node *cur = b->_nodes[j]; | |
824 while( cur->is_Proj() || (cur->is_MachNullCheck()) || cur->is_Catch() ) { | |
825 j--; | |
826 cur = b->_nodes[j]; | |
827 } | |
828 } | |
829 b->_fhrp_index = j; | |
830 | |
831 #ifndef PRODUCT | |
832 // Gather Register Pressure Statistics | |
833 if( PrintOptoStatistics ) { | |
834 if( b->_reg_pressure > (uint)INTPRESSURE || b->_freg_pressure > (uint)FLOATPRESSURE ) | |
835 _high_pressure++; | |
836 else | |
837 _low_pressure++; | |
838 } | |
839 #endif | |
840 } // End of for all blocks | |
841 | |
842 return must_spill; | |
843 } |