Mercurial > hg > truffle
annotate src/share/vm/opto/reg_split.cpp @ 1145:e018e6884bd8
6631166: CMS: better heuristics when combatting fragmentation
Summary: Autonomic per-worker free block cache sizing, tunable coalition policies, fixes to per-size block statistics, retuned gain and bandwidth of some feedback loop filters to allow quicker reactivity to abrupt changes in ambient demand, and other heuristics to reduce fragmentation of the CMS old gen. Also tightened some assertions, including those related to locking.
Reviewed-by: jmasa
author | ysr |
---|---|
date | Wed, 23 Dec 2009 09:23:54 -0800 |
parents | 7bb995fbd3c0 |
children | c18cbe5936b8 |
rev | line source |
---|---|
0 | 1 /* |
579 | 2 * Copyright 2000-2009 Sun Microsystems, Inc. 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 * | |
19 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara, | |
20 * CA 95054 USA or visit www.sun.com if you need additional information or | |
21 * have any questions. | |
22 * | |
23 */ | |
24 | |
25 #include "incls/_precompiled.incl" | |
26 #include "incls/_reg_split.cpp.incl" | |
27 | |
28 //------------------------------Split-------------------------------------- | |
605 | 29 // Walk the graph in RPO and for each lrg which spills, propagate reaching |
30 // definitions. During propagation, split the live range around regions of | |
0 | 31 // High Register Pressure (HRP). If a Def is in a region of Low Register |
32 // Pressure (LRP), it will not get spilled until we encounter a region of | |
33 // HRP between it and one of its uses. We will spill at the transition | |
34 // point between LRP and HRP. Uses in the HRP region will use the spilled | |
35 // Def. The first Use outside the HRP region will generate a SpillCopy to | |
36 // hoist the live range back up into a register, and all subsequent uses | |
37 // will use that new Def until another HRP region is encountered. Defs in | |
38 // HRP regions will get trailing SpillCopies to push the LRG down into the | |
39 // stack immediately. | |
40 // | |
41 // As a side effect, unlink from (hence make dead) coalesced copies. | |
42 // | |
43 | |
44 static const char out_of_nodes[] = "out of nodes during split"; | |
45 | |
46 //------------------------------get_spillcopy_wide----------------------------- | |
47 // Get a SpillCopy node with wide-enough masks. Use the 'wide-mask', the | |
48 // wide ideal-register spill-mask if possible. If the 'wide-mask' does | |
49 // not cover the input (or output), use the input (or output) mask instead. | |
50 Node *PhaseChaitin::get_spillcopy_wide( Node *def, Node *use, uint uidx ) { | |
51 // If ideal reg doesn't exist we've got a bad schedule happening | |
52 // that is forcing us to spill something that isn't spillable. | |
53 // Bail rather than abort | |
54 int ireg = def->ideal_reg(); | |
55 if( ireg == 0 || ireg == Op_RegFlags ) { | |
415
4d9884b01ba6
6754519: don't emit flag fixup for NaN when condition being tested doesn't need it
never
parents:
337
diff
changeset
|
56 assert(false, "attempted to spill a non-spillable item"); |
0 | 57 C->record_method_not_compilable("attempted to spill a non-spillable item"); |
58 return NULL; | |
59 } | |
60 if (C->check_node_count(NodeLimitFudgeFactor, out_of_nodes)) { | |
61 return NULL; | |
62 } | |
63 const RegMask *i_mask = &def->out_RegMask(); | |
64 const RegMask *w_mask = C->matcher()->idealreg2spillmask[ireg]; | |
65 const RegMask *o_mask = use ? &use->in_RegMask(uidx) : w_mask; | |
66 const RegMask *w_i_mask = w_mask->overlap( *i_mask ) ? w_mask : i_mask; | |
67 const RegMask *w_o_mask; | |
68 | |
69 if( w_mask->overlap( *o_mask ) && // Overlap AND | |
70 ((ireg != Op_RegL && ireg != Op_RegD // Single use or aligned | |
71 #ifdef _LP64 | |
72 && ireg != Op_RegP | |
73 #endif | |
74 ) || o_mask->is_aligned_Pairs()) ) { | |
75 // Don't come here for mis-aligned doubles | |
76 w_o_mask = w_mask; | |
77 } else { // wide ideal mask does not overlap with o_mask | |
78 // Mis-aligned doubles come here and XMM->FPR moves on x86. | |
79 w_o_mask = o_mask; // Must target desired registers | |
80 // Does the ideal-reg-mask overlap with o_mask? I.e., can I use | |
81 // a reg-reg move or do I need a trip across register classes | |
82 // (and thus through memory)? | |
83 if( !C->matcher()->idealreg2regmask[ireg]->overlap( *o_mask) && o_mask->is_UP() ) | |
84 // Here we assume a trip through memory is required. | |
85 w_i_mask = &C->FIRST_STACK_mask(); | |
86 } | |
87 return new (C) MachSpillCopyNode( def, *w_i_mask, *w_o_mask ); | |
88 } | |
89 | |
90 //------------------------------insert_proj------------------------------------ | |
605 | 91 // Insert the spill at chosen location. Skip over any intervening Proj's or |
0 | 92 // Phis. Skip over a CatchNode and projs, inserting in the fall-through block |
93 // instead. Update high-pressure indices. Create a new live range. | |
94 void PhaseChaitin::insert_proj( Block *b, uint i, Node *spill, uint maxlrg ) { | |
95 // Skip intervening ProjNodes. Do not insert between a ProjNode and | |
96 // its definer. | |
97 while( i < b->_nodes.size() && | |
98 (b->_nodes[i]->is_Proj() || | |
566
91263420e1c6
6791852: assert(b->_nodes[insidx] == n,"got insidx set incorrectly")
kvn
parents:
550
diff
changeset
|
99 b->_nodes[i]->is_Phi() ) ) |
0 | 100 i++; |
101 | |
102 // Do not insert between a call and his Catch | |
103 if( b->_nodes[i]->is_Catch() ) { | |
104 // Put the instruction at the top of the fall-thru block. | |
105 // Find the fall-thru projection | |
106 while( 1 ) { | |
107 const CatchProjNode *cp = b->_nodes[++i]->as_CatchProj(); | |
108 if( cp->_con == CatchProjNode::fall_through_index ) | |
109 break; | |
110 } | |
111 int sidx = i - b->end_idx()-1; | |
112 b = b->_succs[sidx]; // Switch to successor block | |
113 i = 1; // Right at start of block | |
114 } | |
115 | |
116 b->_nodes.insert(i,spill); // Insert node in block | |
117 _cfg._bbs.map(spill->_idx,b); // Update node->block mapping to reflect | |
118 // Adjust the point where we go hi-pressure | |
119 if( i <= b->_ihrp_index ) b->_ihrp_index++; | |
120 if( i <= b->_fhrp_index ) b->_fhrp_index++; | |
121 | |
122 // Assign a new Live Range Number to the SpillCopy and grow | |
123 // the node->live range mapping. | |
124 new_lrg(spill,maxlrg); | |
125 } | |
126 | |
127 //------------------------------split_DEF-------------------------------------- | |
605 | 128 // There are four categories of Split; UP/DOWN x DEF/USE |
0 | 129 // Only three of these really occur as DOWN/USE will always color |
130 // Any Split with a DEF cannot CISC-Spill now. Thus we need | |
131 // two helper routines, one for Split DEFS (insert after instruction), | |
132 // one for Split USES (insert before instruction). DEF insertion | |
133 // happens inside Split, where the Leaveblock array is updated. | |
134 uint PhaseChaitin::split_DEF( Node *def, Block *b, int loc, uint maxlrg, Node **Reachblock, Node **debug_defs, GrowableArray<uint> splits, int slidx ) { | |
135 #ifdef ASSERT | |
136 // Increment the counter for this lrg | |
137 splits.at_put(slidx, splits.at(slidx)+1); | |
138 #endif | |
139 // If we are spilling the memory op for an implicit null check, at the | |
140 // null check location (ie - null check is in HRP block) we need to do | |
141 // the null-check first, then spill-down in the following block. | |
142 // (The implicit_null_check function ensures the use is also dominated | |
143 // by the branch-not-taken block.) | |
144 Node *be = b->end(); | |
145 if( be->is_MachNullCheck() && be->in(1) == def && def == b->_nodes[loc] ) { | |
146 // Spill goes in the branch-not-taken block | |
147 b = b->_succs[b->_nodes[b->end_idx()+1]->Opcode() == Op_IfTrue]; | |
148 loc = 0; // Just past the Region | |
149 } | |
150 assert( loc >= 0, "must insert past block head" ); | |
151 | |
152 // Get a def-side SpillCopy | |
153 Node *spill = get_spillcopy_wide(def,NULL,0); | |
154 // Did we fail to split?, then bail | |
155 if (!spill) { | |
156 return 0; | |
157 } | |
158 | |
159 // Insert the spill at chosen location | |
160 insert_proj( b, loc+1, spill, maxlrg++); | |
161 | |
162 // Insert new node into Reaches array | |
163 Reachblock[slidx] = spill; | |
164 // Update debug list of reaching down definitions by adding this one | |
165 debug_defs[slidx] = spill; | |
166 | |
167 // return updated count of live ranges | |
168 return maxlrg; | |
169 } | |
170 | |
171 //------------------------------split_USE-------------------------------------- | |
172 // Splits at uses can involve redeffing the LRG, so no CISC Spilling there. | |
173 // Debug uses want to know if def is already stack enabled. | |
174 uint PhaseChaitin::split_USE( Node *def, Block *b, Node *use, uint useidx, uint maxlrg, bool def_down, bool cisc_sp, GrowableArray<uint> splits, int slidx ) { | |
175 #ifdef ASSERT | |
176 // Increment the counter for this lrg | |
177 splits.at_put(slidx, splits.at(slidx)+1); | |
178 #endif | |
179 | |
180 // Some setup stuff for handling debug node uses | |
181 JVMState* jvms = use->jvms(); | |
182 uint debug_start = jvms ? jvms->debug_start() : 999999; | |
183 uint debug_end = jvms ? jvms->debug_end() : 999999; | |
184 | |
185 //------------------------------------------- | |
186 // Check for use of debug info | |
187 if (useidx >= debug_start && useidx < debug_end) { | |
188 // Actually it's perfectly legal for constant debug info to appear | |
189 // just unlikely. In this case the optimizer left a ConI of a 4 | |
190 // as both inputs to a Phi with only a debug use. It's a single-def | |
191 // live range of a rematerializable value. The live range spills, | |
192 // rematerializes and now the ConI directly feeds into the debug info. | |
193 // assert(!def->is_Con(), "constant debug info already constructed directly"); | |
194 | |
195 // Special split handling for Debug Info | |
196 // If DEF is DOWN, just hook the edge and return | |
197 // If DEF is UP, Split it DOWN for this USE. | |
198 if( def->is_Mach() ) { | |
199 if( def_down ) { | |
200 // DEF is DOWN, so connect USE directly to the DEF | |
201 use->set_req(useidx, def); | |
202 } else { | |
203 // Block and index where the use occurs. | |
204 Block *b = _cfg._bbs[use->_idx]; | |
205 // Put the clone just prior to use | |
206 int bindex = b->find_node(use); | |
207 // DEF is UP, so must copy it DOWN and hook in USE | |
208 // Insert SpillCopy before the USE, which uses DEF as its input, | |
209 // and defs a new live range, which is used by this node. | |
210 Node *spill = get_spillcopy_wide(def,use,useidx); | |
211 // did we fail to split? | |
212 if (!spill) { | |
213 // Bail | |
214 return 0; | |
215 } | |
216 // insert into basic block | |
217 insert_proj( b, bindex, spill, maxlrg++ ); | |
218 // Use the new split | |
219 use->set_req(useidx,spill); | |
220 } | |
221 // No further split handling needed for this use | |
222 return maxlrg; | |
223 } // End special splitting for debug info live range | |
224 } // If debug info | |
225 | |
226 // CISC-SPILLING | |
227 // Finally, check to see if USE is CISC-Spillable, and if so, | |
228 // gather_lrg_masks will add the flags bit to its mask, and | |
229 // no use side copy is needed. This frees up the live range | |
230 // register choices without causing copy coalescing, etc. | |
231 if( UseCISCSpill && cisc_sp ) { | |
232 int inp = use->cisc_operand(); | |
233 if( inp != AdlcVMDeps::Not_cisc_spillable ) | |
234 // Convert operand number to edge index number | |
235 inp = use->as_Mach()->operand_index(inp); | |
236 if( inp == (int)useidx ) { | |
237 use->set_req(useidx, def); | |
238 #ifndef PRODUCT | |
239 if( TraceCISCSpill ) { | |
240 tty->print(" set_split: "); | |
241 use->dump(); | |
242 } | |
243 #endif | |
244 return maxlrg; | |
245 } | |
246 } | |
247 | |
248 //------------------------------------------- | |
249 // Insert a Copy before the use | |
250 | |
251 // Block and index where the use occurs. | |
252 int bindex; | |
253 // Phi input spill-copys belong at the end of the prior block | |
254 if( use->is_Phi() ) { | |
255 b = _cfg._bbs[b->pred(useidx)->_idx]; | |
256 bindex = b->end_idx(); | |
257 } else { | |
258 // Put the clone just prior to use | |
259 bindex = b->find_node(use); | |
260 } | |
261 | |
262 Node *spill = get_spillcopy_wide( def, use, useidx ); | |
263 if( !spill ) return 0; // Bailed out | |
264 // Insert SpillCopy before the USE, which uses the reaching DEF as | |
265 // its input, and defs a new live range, which is used by this node. | |
266 insert_proj( b, bindex, spill, maxlrg++ ); | |
267 // Use the spill/clone | |
268 use->set_req(useidx,spill); | |
269 | |
270 // return updated live range count | |
271 return maxlrg; | |
272 } | |
273 | |
274 //------------------------------split_Rematerialize---------------------------- | |
275 // Clone a local copy of the def. | |
276 Node *PhaseChaitin::split_Rematerialize( Node *def, Block *b, uint insidx, uint &maxlrg, GrowableArray<uint> splits, int slidx, uint *lrg2reach, Node **Reachblock, bool walkThru ) { | |
277 // The input live ranges will be stretched to the site of the new | |
278 // instruction. They might be stretched past a def and will thus | |
279 // have the old and new values of the same live range alive at the | |
280 // same time - a definite no-no. Split out private copies of | |
281 // the inputs. | |
282 if( def->req() > 1 ) { | |
283 for( uint i = 1; i < def->req(); i++ ) { | |
284 Node *in = def->in(i); | |
285 // Check for single-def (LRG cannot redefined) | |
286 uint lidx = n2lidx(in); | |
287 if( lidx >= _maxlrg ) continue; // Value is a recent spill-copy | |
295
ea18057223c4
6732194: Data corruption dependent on -server/-client/-Xbatch
never
parents:
0
diff
changeset
|
288 if (lrgs(lidx).is_singledef()) continue; |
0 | 289 |
290 Block *b_def = _cfg._bbs[def->_idx]; | |
291 int idx_def = b_def->find_node(def); | |
292 Node *in_spill = get_spillcopy_wide( in, def, i ); | |
293 if( !in_spill ) return 0; // Bailed out | |
294 insert_proj(b_def,idx_def,in_spill,maxlrg++); | |
295 if( b_def == b ) | |
296 insidx++; | |
297 def->set_req(i,in_spill); | |
298 } | |
299 } | |
300 | |
301 Node *spill = def->clone(); | |
302 if (C->check_node_count(NodeLimitFudgeFactor, out_of_nodes)) { | |
303 // Check when generating nodes | |
304 return 0; | |
305 } | |
306 | |
307 // See if any inputs are currently being spilled, and take the | |
308 // latest copy of spilled inputs. | |
309 if( spill->req() > 1 ) { | |
310 for( uint i = 1; i < spill->req(); i++ ) { | |
311 Node *in = spill->in(i); | |
312 uint lidx = Find_id(in); | |
313 | |
314 // Walk backwards thru spill copy node intermediates | |
295
ea18057223c4
6732194: Data corruption dependent on -server/-client/-Xbatch
never
parents:
0
diff
changeset
|
315 if (walkThru) { |
0 | 316 while ( in->is_SpillCopy() && lidx >= _maxlrg ) { |
317 in = in->in(1); | |
318 lidx = Find_id(in); | |
319 } | |
320 | |
295
ea18057223c4
6732194: Data corruption dependent on -server/-client/-Xbatch
never
parents:
0
diff
changeset
|
321 if (lidx < _maxlrg && lrgs(lidx).is_multidef()) { |
ea18057223c4
6732194: Data corruption dependent on -server/-client/-Xbatch
never
parents:
0
diff
changeset
|
322 // walkThru found a multidef LRG, which is unsafe to use, so |
ea18057223c4
6732194: Data corruption dependent on -server/-client/-Xbatch
never
parents:
0
diff
changeset
|
323 // just keep the original def used in the clone. |
ea18057223c4
6732194: Data corruption dependent on -server/-client/-Xbatch
never
parents:
0
diff
changeset
|
324 in = spill->in(i); |
ea18057223c4
6732194: Data corruption dependent on -server/-client/-Xbatch
never
parents:
0
diff
changeset
|
325 lidx = Find_id(in); |
ea18057223c4
6732194: Data corruption dependent on -server/-client/-Xbatch
never
parents:
0
diff
changeset
|
326 } |
ea18057223c4
6732194: Data corruption dependent on -server/-client/-Xbatch
never
parents:
0
diff
changeset
|
327 } |
ea18057223c4
6732194: Data corruption dependent on -server/-client/-Xbatch
never
parents:
0
diff
changeset
|
328 |
0 | 329 if( lidx < _maxlrg && lrgs(lidx).reg() >= LRG::SPILL_REG ) { |
330 Node *rdef = Reachblock[lrg2reach[lidx]]; | |
331 if( rdef ) spill->set_req(i,rdef); | |
332 } | |
333 } | |
334 } | |
335 | |
336 | |
337 assert( spill->out_RegMask().is_UP(), "rematerialize to a reg" ); | |
338 // Rematerialized op is def->spilled+1 | |
339 set_was_spilled(spill); | |
340 if( _spilled_once.test(def->_idx) ) | |
341 set_was_spilled(spill); | |
342 | |
343 insert_proj( b, insidx, spill, maxlrg++ ); | |
344 #ifdef ASSERT | |
345 // Increment the counter for this lrg | |
346 splits.at_put(slidx, splits.at(slidx)+1); | |
347 #endif | |
348 // See if the cloned def kills any flags, and copy those kills as well | |
349 uint i = insidx+1; | |
350 if( clone_projs( b, i, def, spill, maxlrg ) ) { | |
351 // Adjust the point where we go hi-pressure | |
352 if( i <= b->_ihrp_index ) b->_ihrp_index++; | |
353 if( i <= b->_fhrp_index ) b->_fhrp_index++; | |
354 } | |
355 | |
356 return spill; | |
357 } | |
358 | |
359 //------------------------------is_high_pressure------------------------------- | |
360 // Function to compute whether or not this live range is "high pressure" | |
361 // in this block - whether it spills eagerly or not. | |
362 bool PhaseChaitin::is_high_pressure( Block *b, LRG *lrg, uint insidx ) { | |
363 if( lrg->_was_spilled1 ) return true; | |
364 // Forced spilling due to conflict? Then split only at binding uses | |
365 // or defs, not for supposed capacity problems. | |
366 // CNC - Turned off 7/8/99, causes too much spilling | |
367 // if( lrg->_is_bound ) return false; | |
368 | |
369 // Not yet reached the high-pressure cutoff point, so low pressure | |
370 uint hrp_idx = lrg->_is_float ? b->_fhrp_index : b->_ihrp_index; | |
371 if( insidx < hrp_idx ) return false; | |
372 // Register pressure for the block as a whole depends on reg class | |
373 int block_pres = lrg->_is_float ? b->_freg_pressure : b->_reg_pressure; | |
374 // Bound live ranges will split at the binding points first; | |
375 // Intermediate splits should assume the live range's register set | |
376 // got "freed up" and that num_regs will become INT_PRESSURE. | |
377 int bound_pres = lrg->_is_float ? FLOATPRESSURE : INTPRESSURE; | |
378 // Effective register pressure limit. | |
379 int lrg_pres = (lrg->get_invalid_mask_size() > lrg->num_regs()) | |
380 ? (lrg->get_invalid_mask_size() >> (lrg->num_regs()-1)) : bound_pres; | |
381 // High pressure if block pressure requires more register freedom | |
382 // than live range has. | |
383 return block_pres >= lrg_pres; | |
384 } | |
385 | |
386 | |
387 //------------------------------prompt_use--------------------------------- | |
388 // True if lidx is used before any real register is def'd in the block | |
389 bool PhaseChaitin::prompt_use( Block *b, uint lidx ) { | |
390 if( lrgs(lidx)._was_spilled2 ) return false; | |
391 | |
392 // Scan block for 1st use. | |
393 for( uint i = 1; i <= b->end_idx(); i++ ) { | |
394 Node *n = b->_nodes[i]; | |
395 // Ignore PHI use, these can be up or down | |
396 if( n->is_Phi() ) continue; | |
397 for( uint j = 1; j < n->req(); j++ ) | |
398 if( Find_id(n->in(j)) == lidx ) | |
399 return true; // Found 1st use! | |
400 if( n->out_RegMask().is_NotEmpty() ) return false; | |
401 } | |
402 return false; | |
403 } | |
404 | |
405 //------------------------------Split-------------------------------------- | |
406 //----------Split Routine---------- | |
407 // ***** NEW SPLITTING HEURISTIC ***** | |
408 // DEFS: If the DEF is in a High Register Pressure(HRP) Block, split there. | |
409 // Else, no split unless there is a HRP block between a DEF and | |
410 // one of its uses, and then split at the HRP block. | |
411 // | |
412 // USES: If USE is in HRP, split at use to leave main LRG on stack. | |
413 // Else, hoist LRG back up to register only (ie - split is also DEF) | |
414 // We will compute a new maxlrg as we go | |
415 uint PhaseChaitin::Split( uint maxlrg ) { | |
416 NOT_PRODUCT( Compile::TracePhase t3("regAllocSplit", &_t_regAllocSplit, TimeCompiler); ) | |
417 | |
418 uint bidx, pidx, slidx, insidx, inpidx, twoidx; | |
419 uint non_phi = 1, spill_cnt = 0; | |
420 Node **Reachblock; | |
421 Node *n1, *n2, *n3; | |
422 Node_List *defs,*phis; | |
423 bool *UPblock; | |
424 bool u1, u2, u3; | |
425 Block *b, *pred; | |
426 PhiNode *phi; | |
427 GrowableArray<uint> lidxs; | |
428 | |
429 // Array of counters to count splits per live range | |
430 GrowableArray<uint> splits; | |
431 | |
432 //----------Setup Code---------- | |
433 // Create a convenient mapping from lrg numbers to reaches/leaves indices | |
434 uint *lrg2reach = NEW_RESOURCE_ARRAY( uint, _maxlrg ); | |
435 // Keep track of DEFS & Phis for later passes | |
436 defs = new Node_List(); | |
437 phis = new Node_List(); | |
438 // Gather info on which LRG's are spilling, and build maps | |
439 for( bidx = 1; bidx < _maxlrg; bidx++ ) { | |
440 if( lrgs(bidx).alive() && lrgs(bidx).reg() >= LRG::SPILL_REG ) { | |
441 assert(!lrgs(bidx).mask().is_AllStack(),"AllStack should color"); | |
442 lrg2reach[bidx] = spill_cnt; | |
443 spill_cnt++; | |
444 lidxs.append(bidx); | |
445 #ifdef ASSERT | |
446 // Initialize the split counts to zero | |
447 splits.append(0); | |
448 #endif | |
449 #ifndef PRODUCT | |
450 if( PrintOpto && WizardMode && lrgs(bidx)._was_spilled1 ) | |
451 tty->print_cr("Warning, 2nd spill of L%d",bidx); | |
452 #endif | |
453 } | |
454 } | |
455 | |
456 // Create side arrays for propagating reaching defs info. | |
457 // Each block needs a node pointer for each spilling live range for the | |
458 // Def which is live into the block. Phi nodes handle multiple input | |
459 // Defs by querying the output of their predecessor blocks and resolving | |
460 // them to a single Def at the phi. The pointer is updated for each | |
461 // Def in the block, and then becomes the output for the block when | |
462 // processing of the block is complete. We also need to track whether | |
463 // a Def is UP or DOWN. UP means that it should get a register (ie - | |
464 // it is always in LRP regions), and DOWN means that it is probably | |
465 // on the stack (ie - it crosses HRP regions). | |
466 Node ***Reaches = NEW_RESOURCE_ARRAY( Node**, _cfg._num_blocks+1 ); | |
467 bool **UP = NEW_RESOURCE_ARRAY( bool*, _cfg._num_blocks+1 ); | |
468 Node **debug_defs = NEW_RESOURCE_ARRAY( Node*, spill_cnt ); | |
469 VectorSet **UP_entry= NEW_RESOURCE_ARRAY( VectorSet*, spill_cnt ); | |
470 | |
471 // Initialize Reaches & UP | |
472 for( bidx = 0; bidx < _cfg._num_blocks+1; bidx++ ) { | |
473 Reaches[bidx] = NEW_RESOURCE_ARRAY( Node*, spill_cnt ); | |
474 UP[bidx] = NEW_RESOURCE_ARRAY( bool, spill_cnt ); | |
475 Node **Reachblock = Reaches[bidx]; | |
476 bool *UPblock = UP[bidx]; | |
477 for( slidx = 0; slidx < spill_cnt; slidx++ ) { | |
478 UPblock[slidx] = true; // Assume they start in registers | |
479 Reachblock[slidx] = NULL; // Assume that no def is present | |
480 } | |
481 } | |
482 | |
483 // Initialize to array of empty vectorsets | |
484 for( slidx = 0; slidx < spill_cnt; slidx++ ) | |
485 UP_entry[slidx] = new VectorSet(Thread::current()->resource_area()); | |
486 | |
487 //----------PASS 1---------- | |
488 //----------Propagation & Node Insertion Code---------- | |
489 // Walk the Blocks in RPO for DEF & USE info | |
490 for( bidx = 0; bidx < _cfg._num_blocks; bidx++ ) { | |
491 | |
492 if (C->check_node_count(spill_cnt, out_of_nodes)) { | |
493 return 0; | |
494 } | |
495 | |
496 b = _cfg._blocks[bidx]; | |
497 // Reaches & UP arrays for this block | |
498 Reachblock = Reaches[b->_pre_order]; | |
499 UPblock = UP[b->_pre_order]; | |
500 // Reset counter of start of non-Phi nodes in block | |
501 non_phi = 1; | |
502 //----------Block Entry Handling---------- | |
503 // Check for need to insert a new phi | |
504 // Cycle through this block's predecessors, collecting Reaches | |
505 // info for each spilled LRG. If they are identical, no phi is | |
506 // needed. If they differ, check for a phi, and insert if missing, | |
507 // or update edges if present. Set current block's Reaches set to | |
508 // be either the phi's or the reaching def, as appropriate. | |
509 // If no Phi is needed, check if the LRG needs to spill on entry | |
510 // to the block due to HRP. | |
511 for( slidx = 0; slidx < spill_cnt; slidx++ ) { | |
512 // Grab the live range number | |
513 uint lidx = lidxs.at(slidx); | |
514 // Do not bother splitting or putting in Phis for single-def | |
515 // rematerialized live ranges. This happens alot to constants | |
516 // with long live ranges. | |
295
ea18057223c4
6732194: Data corruption dependent on -server/-client/-Xbatch
never
parents:
0
diff
changeset
|
517 if( lrgs(lidx).is_singledef() && |
0 | 518 lrgs(lidx)._def->rematerialize() ) { |
519 // reset the Reaches & UP entries | |
520 Reachblock[slidx] = lrgs(lidx)._def; | |
521 UPblock[slidx] = true; | |
522 // Record following instruction in case 'n' rematerializes and | |
523 // kills flags | |
524 Block *pred1 = _cfg._bbs[b->pred(1)->_idx]; | |
525 continue; | |
526 } | |
527 | |
528 // Initialize needs_phi and needs_split | |
529 bool needs_phi = false; | |
530 bool needs_split = false; | |
330
1c6e3bfb543a
6746892: Register Allocator does not process a data phi with one unique input correctly
kvn
parents:
295
diff
changeset
|
531 bool has_phi = false; |
0 | 532 // Walk the predecessor blocks to check inputs for that live range |
533 // Grab predecessor block header | |
534 n1 = b->pred(1); | |
535 // Grab the appropriate reaching def info for inpidx | |
536 pred = _cfg._bbs[n1->_idx]; | |
537 pidx = pred->_pre_order; | |
538 Node **Ltmp = Reaches[pidx]; | |
539 bool *Utmp = UP[pidx]; | |
540 n1 = Ltmp[slidx]; | |
541 u1 = Utmp[slidx]; | |
542 // Initialize node for saving type info | |
543 n3 = n1; | |
544 u3 = u1; | |
545 | |
546 // Compare inputs to see if a Phi is needed | |
547 for( inpidx = 2; inpidx < b->num_preds(); inpidx++ ) { | |
548 // Grab predecessor block headers | |
549 n2 = b->pred(inpidx); | |
550 // Grab the appropriate reaching def info for inpidx | |
551 pred = _cfg._bbs[n2->_idx]; | |
552 pidx = pred->_pre_order; | |
553 Ltmp = Reaches[pidx]; | |
554 Utmp = UP[pidx]; | |
555 n2 = Ltmp[slidx]; | |
556 u2 = Utmp[slidx]; | |
557 // For each LRG, decide if a phi is necessary | |
558 if( n1 != n2 ) { | |
559 needs_phi = true; | |
560 } | |
561 // See if the phi has mismatched inputs, UP vs. DOWN | |
562 if( n1 && n2 && (u1 != u2) ) { | |
563 needs_split = true; | |
564 } | |
565 // Move n2/u2 to n1/u1 for next iteration | |
566 n1 = n2; | |
567 u1 = u2; | |
568 // Preserve a non-NULL predecessor for later type referencing | |
569 if( (n3 == NULL) && (n2 != NULL) ){ | |
570 n3 = n2; | |
571 u3 = u2; | |
572 } | |
573 } // End for all potential Phi inputs | |
574 | |
330
1c6e3bfb543a
6746892: Register Allocator does not process a data phi with one unique input correctly
kvn
parents:
295
diff
changeset
|
575 // check block for appropriate phinode & update edges |
1c6e3bfb543a
6746892: Register Allocator does not process a data phi with one unique input correctly
kvn
parents:
295
diff
changeset
|
576 for( insidx = 1; insidx <= b->end_idx(); insidx++ ) { |
1c6e3bfb543a
6746892: Register Allocator does not process a data phi with one unique input correctly
kvn
parents:
295
diff
changeset
|
577 n1 = b->_nodes[insidx]; |
1c6e3bfb543a
6746892: Register Allocator does not process a data phi with one unique input correctly
kvn
parents:
295
diff
changeset
|
578 // bail if this is not a phi |
1c6e3bfb543a
6746892: Register Allocator does not process a data phi with one unique input correctly
kvn
parents:
295
diff
changeset
|
579 phi = n1->is_Phi() ? n1->as_Phi() : NULL; |
1c6e3bfb543a
6746892: Register Allocator does not process a data phi with one unique input correctly
kvn
parents:
295
diff
changeset
|
580 if( phi == NULL ) { |
1c6e3bfb543a
6746892: Register Allocator does not process a data phi with one unique input correctly
kvn
parents:
295
diff
changeset
|
581 // Keep track of index of first non-PhiNode instruction in block |
1c6e3bfb543a
6746892: Register Allocator does not process a data phi with one unique input correctly
kvn
parents:
295
diff
changeset
|
582 non_phi = insidx; |
1c6e3bfb543a
6746892: Register Allocator does not process a data phi with one unique input correctly
kvn
parents:
295
diff
changeset
|
583 // break out of the for loop as we have handled all phi nodes |
1c6e3bfb543a
6746892: Register Allocator does not process a data phi with one unique input correctly
kvn
parents:
295
diff
changeset
|
584 break; |
1c6e3bfb543a
6746892: Register Allocator does not process a data phi with one unique input correctly
kvn
parents:
295
diff
changeset
|
585 } |
1c6e3bfb543a
6746892: Register Allocator does not process a data phi with one unique input correctly
kvn
parents:
295
diff
changeset
|
586 // must be looking at a phi |
1c6e3bfb543a
6746892: Register Allocator does not process a data phi with one unique input correctly
kvn
parents:
295
diff
changeset
|
587 if( Find_id(n1) == lidxs.at(slidx) ) { |
1c6e3bfb543a
6746892: Register Allocator does not process a data phi with one unique input correctly
kvn
parents:
295
diff
changeset
|
588 // found the necessary phi |
1c6e3bfb543a
6746892: Register Allocator does not process a data phi with one unique input correctly
kvn
parents:
295
diff
changeset
|
589 needs_phi = false; |
1c6e3bfb543a
6746892: Register Allocator does not process a data phi with one unique input correctly
kvn
parents:
295
diff
changeset
|
590 has_phi = true; |
1c6e3bfb543a
6746892: Register Allocator does not process a data phi with one unique input correctly
kvn
parents:
295
diff
changeset
|
591 // initialize the Reaches entry for this LRG |
1c6e3bfb543a
6746892: Register Allocator does not process a data phi with one unique input correctly
kvn
parents:
295
diff
changeset
|
592 Reachblock[slidx] = phi; |
1c6e3bfb543a
6746892: Register Allocator does not process a data phi with one unique input correctly
kvn
parents:
295
diff
changeset
|
593 break; |
1c6e3bfb543a
6746892: Register Allocator does not process a data phi with one unique input correctly
kvn
parents:
295
diff
changeset
|
594 } // end if found correct phi |
1c6e3bfb543a
6746892: Register Allocator does not process a data phi with one unique input correctly
kvn
parents:
295
diff
changeset
|
595 } // end for all phi's |
1c6e3bfb543a
6746892: Register Allocator does not process a data phi with one unique input correctly
kvn
parents:
295
diff
changeset
|
596 |
1c6e3bfb543a
6746892: Register Allocator does not process a data phi with one unique input correctly
kvn
parents:
295
diff
changeset
|
597 // If a phi is needed or exist, check for it |
1c6e3bfb543a
6746892: Register Allocator does not process a data phi with one unique input correctly
kvn
parents:
295
diff
changeset
|
598 if( needs_phi || has_phi ) { |
0 | 599 // add new phinode if one not already found |
600 if( needs_phi ) { | |
601 // create a new phi node and insert it into the block | |
602 // type is taken from left over pointer to a predecessor | |
603 assert(n3,"No non-NULL reaching DEF for a Phi"); | |
604 phi = new (C, b->num_preds()) PhiNode(b->head(), n3->bottom_type()); | |
605 // initialize the Reaches entry for this LRG | |
606 Reachblock[slidx] = phi; | |
607 | |
608 // add node to block & node_to_block mapping | |
609 insert_proj( b, insidx++, phi, maxlrg++ ); | |
610 non_phi++; | |
611 // Reset new phi's mapping to be the spilling live range | |
612 _names.map(phi->_idx, lidx); | |
613 assert(Find_id(phi) == lidx,"Bad update on Union-Find mapping"); | |
614 } // end if not found correct phi | |
615 // Here you have either found or created the Phi, so record it | |
616 assert(phi != NULL,"Must have a Phi Node here"); | |
617 phis->push(phi); | |
618 // PhiNodes should either force the LRG UP or DOWN depending | |
619 // on its inputs and the register pressure in the Phi's block. | |
620 UPblock[slidx] = true; // Assume new DEF is UP | |
621 // If entering a high-pressure area with no immediate use, | |
622 // assume Phi is DOWN | |
623 if( is_high_pressure( b, &lrgs(lidx), b->end_idx()) && !prompt_use(b,lidx) ) | |
624 UPblock[slidx] = false; | |
625 // If we are not split up/down and all inputs are down, then we | |
626 // are down | |
627 if( !needs_split && !u3 ) | |
628 UPblock[slidx] = false; | |
629 } // end if phi is needed | |
630 | |
631 // Do not need a phi, so grab the reaching DEF | |
632 else { | |
633 // Grab predecessor block header | |
634 n1 = b->pred(1); | |
635 // Grab the appropriate reaching def info for k | |
636 pred = _cfg._bbs[n1->_idx]; | |
637 pidx = pred->_pre_order; | |
638 Node **Ltmp = Reaches[pidx]; | |
639 bool *Utmp = UP[pidx]; | |
640 // reset the Reaches & UP entries | |
641 Reachblock[slidx] = Ltmp[slidx]; | |
642 UPblock[slidx] = Utmp[slidx]; | |
643 } // end else no Phi is needed | |
644 } // end for all spilling live ranges | |
645 // DEBUG | |
646 #ifndef PRODUCT | |
647 if(trace_spilling()) { | |
648 tty->print("/`\nBlock %d: ", b->_pre_order); | |
649 tty->print("Reaching Definitions after Phi handling\n"); | |
650 for( uint x = 0; x < spill_cnt; x++ ) { | |
651 tty->print("Spill Idx %d: UP %d: Node\n",x,UPblock[x]); | |
652 if( Reachblock[x] ) | |
653 Reachblock[x]->dump(); | |
654 else | |
655 tty->print("Undefined\n"); | |
656 } | |
657 } | |
658 #endif | |
659 | |
660 //----------Non-Phi Node Splitting---------- | |
661 // Since phi-nodes have now been handled, the Reachblock array for this | |
662 // block is initialized with the correct starting value for the defs which | |
663 // reach non-phi instructions in this block. Thus, process non-phi | |
664 // instructions normally, inserting SpillCopy nodes for all spill | |
665 // locations. | |
666 | |
667 // Memoize any DOWN reaching definitions for use as DEBUG info | |
668 for( insidx = 0; insidx < spill_cnt; insidx++ ) { | |
669 debug_defs[insidx] = (UPblock[insidx]) ? NULL : Reachblock[insidx]; | |
670 if( UPblock[insidx] ) // Memoize UP decision at block start | |
671 UP_entry[insidx]->set( b->_pre_order ); | |
672 } | |
673 | |
674 //----------Walk Instructions in the Block and Split---------- | |
675 // For all non-phi instructions in the block | |
676 for( insidx = 1; insidx <= b->end_idx(); insidx++ ) { | |
677 Node *n = b->_nodes[insidx]; | |
678 // Find the defining Node's live range index | |
679 uint defidx = Find_id(n); | |
680 uint cnt = n->req(); | |
681 | |
682 if( n->is_Phi() ) { | |
683 // Skip phi nodes after removing dead copies. | |
684 if( defidx < _maxlrg ) { | |
685 // Check for useless Phis. These appear if we spill, then | |
686 // coalesce away copies. Dont touch Phis in spilling live | |
687 // ranges; they are busy getting modifed in this pass. | |
688 if( lrgs(defidx).reg() < LRG::SPILL_REG ) { | |
689 uint i; | |
690 Node *u = NULL; | |
691 // Look for the Phi merging 2 unique inputs | |
692 for( i = 1; i < cnt; i++ ) { | |
693 // Ignore repeats and self | |
694 if( n->in(i) != u && n->in(i) != n ) { | |
695 // Found a unique input | |
696 if( u != NULL ) // If it's the 2nd, bail out | |
697 break; | |
698 u = n->in(i); // Else record it | |
699 } | |
700 } | |
701 assert( u, "at least 1 valid input expected" ); | |
330
1c6e3bfb543a
6746892: Register Allocator does not process a data phi with one unique input correctly
kvn
parents:
295
diff
changeset
|
702 if( i >= cnt ) { // Found one unique input |
1c6e3bfb543a
6746892: Register Allocator does not process a data phi with one unique input correctly
kvn
parents:
295
diff
changeset
|
703 assert(Find_id(n) == Find_id(u), "should be the same lrg"); |
0 | 704 n->replace_by(u); // Then replace with unique input |
705 n->disconnect_inputs(NULL); | |
706 b->_nodes.remove(insidx); | |
707 insidx--; | |
708 b->_ihrp_index--; | |
709 b->_fhrp_index--; | |
710 } | |
711 } | |
712 } | |
713 continue; | |
714 } | |
715 assert( insidx > b->_ihrp_index || | |
716 (b->_reg_pressure < (uint)INTPRESSURE) || | |
717 b->_ihrp_index > 4000000 || | |
718 b->_ihrp_index >= b->end_idx() || | |
719 !b->_nodes[b->_ihrp_index]->is_Proj(), "" ); | |
720 assert( insidx > b->_fhrp_index || | |
721 (b->_freg_pressure < (uint)FLOATPRESSURE) || | |
722 b->_fhrp_index > 4000000 || | |
723 b->_fhrp_index >= b->end_idx() || | |
724 !b->_nodes[b->_fhrp_index]->is_Proj(), "" ); | |
725 | |
726 // ********** Handle Crossing HRP Boundry ********** | |
727 if( (insidx == b->_ihrp_index) || (insidx == b->_fhrp_index) ) { | |
728 for( slidx = 0; slidx < spill_cnt; slidx++ ) { | |
605 | 729 // Check for need to split at HRP boundary - split if UP |
0 | 730 n1 = Reachblock[slidx]; |
731 // bail out if no reaching DEF | |
732 if( n1 == NULL ) continue; | |
733 // bail out if live range is 'isolated' around inner loop | |
734 uint lidx = lidxs.at(slidx); | |
735 // If live range is currently UP | |
736 if( UPblock[slidx] ) { | |
737 // set location to insert spills at | |
738 // SPLIT DOWN HERE - NO CISC SPILL | |
739 if( is_high_pressure( b, &lrgs(lidx), insidx ) && | |
740 !n1->rematerialize() ) { | |
741 // If there is already a valid stack definition available, use it | |
742 if( debug_defs[slidx] != NULL ) { | |
743 Reachblock[slidx] = debug_defs[slidx]; | |
744 } | |
745 else { | |
746 // Insert point is just past last use or def in the block | |
747 int insert_point = insidx-1; | |
748 while( insert_point > 0 ) { | |
749 Node *n = b->_nodes[insert_point]; | |
750 // Hit top of block? Quit going backwards | |
751 if( n->is_Phi() ) break; | |
752 // Found a def? Better split after it. | |
753 if( n2lidx(n) == lidx ) break; | |
754 // Look for a use | |
755 uint i; | |
756 for( i = 1; i < n->req(); i++ ) | |
757 if( n2lidx(n->in(i)) == lidx ) | |
758 break; | |
759 // Found a use? Better split after it. | |
760 if( i < n->req() ) break; | |
761 insert_point--; | |
762 } | |
763 maxlrg = split_DEF( n1, b, insert_point, maxlrg, Reachblock, debug_defs, splits, slidx); | |
764 // If it wasn't split bail | |
765 if (!maxlrg) { | |
766 return 0; | |
767 } | |
768 insidx++; | |
769 } | |
770 // This is a new DEF, so update UP | |
771 UPblock[slidx] = false; | |
772 #ifndef PRODUCT | |
773 // DEBUG | |
774 if( trace_spilling() ) { | |
775 tty->print("\nNew Split DOWN DEF of Spill Idx "); | |
776 tty->print("%d, UP %d:\n",slidx,false); | |
777 n1->dump(); | |
778 } | |
779 #endif | |
780 } | |
781 } // end if LRG is UP | |
782 } // end for all spilling live ranges | |
783 assert( b->_nodes[insidx] == n, "got insidx set incorrectly" ); | |
784 } // end if crossing HRP Boundry | |
785 | |
786 // If the LRG index is oob, then this is a new spillcopy, skip it. | |
787 if( defidx >= _maxlrg ) { | |
788 continue; | |
789 } | |
790 LRG &deflrg = lrgs(defidx); | |
791 uint copyidx = n->is_Copy(); | |
792 // Remove coalesced copy from CFG | |
793 if( copyidx && defidx == n2lidx(n->in(copyidx)) ) { | |
794 n->replace_by( n->in(copyidx) ); | |
795 n->set_req( copyidx, NULL ); | |
796 b->_nodes.remove(insidx--); | |
797 b->_ihrp_index--; // Adjust the point where we go hi-pressure | |
798 b->_fhrp_index--; | |
799 continue; | |
800 } | |
801 | |
802 #define DERIVED 0 | |
803 | |
804 // ********** Handle USES ********** | |
805 bool nullcheck = false; | |
806 // Implicit null checks never use the spilled value | |
807 if( n->is_MachNullCheck() ) | |
808 nullcheck = true; | |
809 if( !nullcheck ) { | |
810 // Search all inputs for a Spill-USE | |
811 JVMState* jvms = n->jvms(); | |
812 uint oopoff = jvms ? jvms->oopoff() : cnt; | |
813 uint old_last = cnt - 1; | |
814 for( inpidx = 1; inpidx < cnt; inpidx++ ) { | |
815 // Derived/base pairs may be added to our inputs during this loop. | |
816 // If inpidx > old_last, then one of these new inputs is being | |
817 // handled. Skip the derived part of the pair, but process | |
818 // the base like any other input. | |
819 if( inpidx > old_last && ((inpidx - oopoff) & 1) == DERIVED ) { | |
820 continue; // skip derived_debug added below | |
821 } | |
822 // Get lidx of input | |
823 uint useidx = Find_id(n->in(inpidx)); | |
824 // Not a brand-new split, and it is a spill use | |
825 if( useidx < _maxlrg && lrgs(useidx).reg() >= LRG::SPILL_REG ) { | |
826 // Check for valid reaching DEF | |
827 slidx = lrg2reach[useidx]; | |
828 Node *def = Reachblock[slidx]; | |
829 assert( def != NULL, "Using Undefined Value in Split()\n"); | |
830 | |
831 // (+++) %%%% remove this in favor of pre-pass in matcher.cpp | |
832 // monitor references do not care where they live, so just hook | |
833 if ( jvms && jvms->is_monitor_use(inpidx) ) { | |
834 // The effect of this clone is to drop the node out of the block, | |
835 // so that the allocator does not see it anymore, and therefore | |
836 // does not attempt to assign it a register. | |
837 def = def->clone(); | |
838 _names.extend(def->_idx,0); | |
839 _cfg._bbs.map(def->_idx,b); | |
840 n->set_req(inpidx, def); | |
841 if (C->check_node_count(NodeLimitFudgeFactor, out_of_nodes)) { | |
842 return 0; | |
843 } | |
844 continue; | |
845 } | |
846 | |
847 // Rematerializable? Then clone def at use site instead | |
848 // of store/load | |
849 if( def->rematerialize() ) { | |
850 int old_size = b->_nodes.size(); | |
851 def = split_Rematerialize( def, b, insidx, maxlrg, splits, slidx, lrg2reach, Reachblock, true ); | |
852 if( !def ) return 0; // Bail out | |
853 insidx += b->_nodes.size()-old_size; | |
854 } | |
855 | |
856 MachNode *mach = n->is_Mach() ? n->as_Mach() : NULL; | |
857 // Base pointers and oopmap references do not care where they live. | |
858 if ((inpidx >= oopoff) || | |
859 (mach && mach->ideal_Opcode() == Op_AddP && inpidx == AddPNode::Base)) { | |
860 if (def->rematerialize() && lrgs(useidx)._was_spilled2) { | |
861 // This def has been rematerialized a couple of times without | |
862 // progress. It doesn't care if it lives UP or DOWN, so | |
863 // spill it down now. | |
864 maxlrg = split_USE(def,b,n,inpidx,maxlrg,false,false,splits,slidx); | |
865 // If it wasn't split bail | |
866 if (!maxlrg) { | |
867 return 0; | |
868 } | |
869 insidx++; // Reset iterator to skip USE side split | |
870 } else { | |
871 // Just hook the def edge | |
872 n->set_req(inpidx, def); | |
873 } | |
874 | |
875 if (inpidx >= oopoff) { | |
876 // After oopoff, we have derived/base pairs. We must mention all | |
877 // derived pointers here as derived/base pairs for GC. If the | |
878 // derived value is spilling and we have a copy both in Reachblock | |
879 // (called here 'def') and debug_defs[slidx] we need to mention | |
880 // both in derived/base pairs or kill one. | |
881 Node *derived_debug = debug_defs[slidx]; | |
882 if( ((inpidx - oopoff) & 1) == DERIVED && // derived vs base? | |
883 mach && mach->ideal_Opcode() != Op_Halt && | |
884 derived_debug != NULL && | |
885 derived_debug != def ) { // Actual 2nd value appears | |
886 // We have already set 'def' as a derived value. | |
887 // Also set debug_defs[slidx] as a derived value. | |
888 uint k; | |
889 for( k = oopoff; k < cnt; k += 2 ) | |
890 if( n->in(k) == derived_debug ) | |
891 break; // Found an instance of debug derived | |
892 if( k == cnt ) {// No instance of debug_defs[slidx] | |
893 // Add a derived/base pair to cover the debug info. | |
894 // We have to process the added base later since it is not | |
895 // handled yet at this point but skip derived part. | |
896 assert(((n->req() - oopoff) & 1) == DERIVED, | |
897 "must match skip condition above"); | |
898 n->add_req( derived_debug ); // this will be skipped above | |
899 n->add_req( n->in(inpidx+1) ); // this will be processed | |
900 // Increment cnt to handle added input edges on | |
901 // subsequent iterations. | |
902 cnt += 2; | |
903 } | |
904 } | |
905 } | |
906 continue; | |
907 } | |
908 // Special logic for DEBUG info | |
909 if( jvms && b->_freq > BLOCK_FREQUENCY(0.5) ) { | |
910 uint debug_start = jvms->debug_start(); | |
911 // If this is debug info use & there is a reaching DOWN def | |
912 if ((debug_start <= inpidx) && (debug_defs[slidx] != NULL)) { | |
913 assert(inpidx < oopoff, "handle only debug info here"); | |
914 // Just hook it in & move on | |
915 n->set_req(inpidx, debug_defs[slidx]); | |
916 // (Note that this can make two sides of a split live at the | |
917 // same time: The debug def on stack, and another def in a | |
918 // register. The GC needs to know about both of them, but any | |
919 // derived pointers after oopoff will refer to only one of the | |
920 // two defs and the GC would therefore miss the other. Thus | |
921 // this hack is only allowed for debug info which is Java state | |
922 // and therefore never a derived pointer.) | |
923 continue; | |
924 } | |
925 } | |
926 // Grab register mask info | |
927 const RegMask &dmask = def->out_RegMask(); | |
928 const RegMask &umask = n->in_RegMask(inpidx); | |
929 | |
930 assert(inpidx < oopoff, "cannot use-split oop map info"); | |
931 | |
932 bool dup = UPblock[slidx]; | |
933 bool uup = umask.is_UP(); | |
934 | |
935 // Need special logic to handle bound USES. Insert a split at this | |
936 // bound use if we can't rematerialize the def, or if we need the | |
937 // split to form a misaligned pair. | |
938 if( !umask.is_AllStack() && | |
939 (int)umask.Size() <= lrgs(useidx).num_regs() && | |
940 (!def->rematerialize() || | |
941 umask.is_misaligned_Pair())) { | |
942 // These need a Split regardless of overlap or pressure | |
943 // SPLIT - NO DEF - NO CISC SPILL | |
944 maxlrg = split_USE(def,b,n,inpidx,maxlrg,dup,false, splits,slidx); | |
945 // If it wasn't split bail | |
946 if (!maxlrg) { | |
947 return 0; | |
948 } | |
949 insidx++; // Reset iterator to skip USE side split | |
950 continue; | |
951 } | |
952 // Here is the logic chart which describes USE Splitting: | |
953 // 0 = false or DOWN, 1 = true or UP | |
954 // | |
955 // Overlap | DEF | USE | Action | |
956 //------------------------------------------------------- | |
957 // 0 | 0 | 0 | Copy - mem -> mem | |
958 // 0 | 0 | 1 | Split-UP - Check HRP | |
959 // 0 | 1 | 0 | Split-DOWN - Debug Info? | |
960 // 0 | 1 | 1 | Copy - reg -> reg | |
961 // 1 | 0 | 0 | Reset Input Edge (no Split) | |
962 // 1 | 0 | 1 | Split-UP - Check HRP | |
963 // 1 | 1 | 0 | Split-DOWN - Debug Info? | |
964 // 1 | 1 | 1 | Reset Input Edge (no Split) | |
965 // | |
966 // So, if (dup == uup), then overlap test determines action, | |
967 // with true being no split, and false being copy. Else, | |
968 // if DEF is DOWN, Split-UP, and check HRP to decide on | |
969 // resetting DEF. Finally if DEF is UP, Split-DOWN, with | |
970 // special handling for Debug Info. | |
971 if( dup == uup ) { | |
972 if( dmask.overlap(umask) ) { | |
973 // Both are either up or down, and there is overlap, No Split | |
974 n->set_req(inpidx, def); | |
975 } | |
976 else { // Both are either up or down, and there is no overlap | |
977 if( dup ) { // If UP, reg->reg copy | |
978 // COPY ACROSS HERE - NO DEF - NO CISC SPILL | |
979 maxlrg = split_USE(def,b,n,inpidx,maxlrg,false,false, splits,slidx); | |
980 // If it wasn't split bail | |
981 if (!maxlrg) { | |
982 return 0; | |
983 } | |
984 insidx++; // Reset iterator to skip USE side split | |
985 } | |
986 else { // DOWN, mem->mem copy | |
987 // COPY UP & DOWN HERE - NO DEF - NO CISC SPILL | |
988 // First Split-UP to move value into Register | |
989 uint def_ideal = def->ideal_reg(); | |
990 const RegMask* tmp_rm = Matcher::idealreg2regmask[def_ideal]; | |
991 Node *spill = new (C) MachSpillCopyNode(def, dmask, *tmp_rm); | |
992 insert_proj( b, insidx, spill, maxlrg ); | |
993 // Then Split-DOWN as if previous Split was DEF | |
994 maxlrg = split_USE(spill,b,n,inpidx,maxlrg,false,false, splits,slidx); | |
995 // If it wasn't split bail | |
996 if (!maxlrg) { | |
997 return 0; | |
998 } | |
999 insidx += 2; // Reset iterator to skip USE side splits | |
1000 } | |
1001 } // End else no overlap | |
1002 } // End if dup == uup | |
1003 // dup != uup, so check dup for direction of Split | |
1004 else { | |
1005 if( dup ) { // If UP, Split-DOWN and check Debug Info | |
1006 // If this node is already a SpillCopy, just patch the edge | |
1007 // except the case of spilling to stack. | |
1008 if( n->is_SpillCopy() ) { | |
1009 RegMask tmp_rm(umask); | |
1010 tmp_rm.SUBTRACT(Matcher::STACK_ONLY_mask); | |
1011 if( dmask.overlap(tmp_rm) ) { | |
1012 if( def != n->in(inpidx) ) { | |
1013 n->set_req(inpidx, def); | |
1014 } | |
1015 continue; | |
1016 } | |
1017 } | |
1018 // COPY DOWN HERE - NO DEF - NO CISC SPILL | |
1019 maxlrg = split_USE(def,b,n,inpidx,maxlrg,false,false, splits,slidx); | |
1020 // If it wasn't split bail | |
1021 if (!maxlrg) { | |
1022 return 0; | |
1023 } | |
1024 insidx++; // Reset iterator to skip USE side split | |
1025 // Check for debug-info split. Capture it for later | |
1026 // debug splits of the same value | |
1027 if (jvms && jvms->debug_start() <= inpidx && inpidx < oopoff) | |
1028 debug_defs[slidx] = n->in(inpidx); | |
1029 | |
1030 } | |
1031 else { // DOWN, Split-UP and check register pressure | |
1032 if( is_high_pressure( b, &lrgs(useidx), insidx ) ) { | |
1033 // COPY UP HERE - NO DEF - CISC SPILL | |
1034 maxlrg = split_USE(def,b,n,inpidx,maxlrg,true,true, splits,slidx); | |
1035 // If it wasn't split bail | |
1036 if (!maxlrg) { | |
1037 return 0; | |
1038 } | |
1039 insidx++; // Reset iterator to skip USE side split | |
1040 } else { // LRP | |
1041 // COPY UP HERE - WITH DEF - NO CISC SPILL | |
1042 maxlrg = split_USE(def,b,n,inpidx,maxlrg,true,false, splits,slidx); | |
1043 // If it wasn't split bail | |
1044 if (!maxlrg) { | |
1045 return 0; | |
1046 } | |
1047 // Flag this lift-up in a low-pressure block as | |
1048 // already-spilled, so if it spills again it will | |
1049 // spill hard (instead of not spilling hard and | |
1050 // coalescing away). | |
1051 set_was_spilled(n->in(inpidx)); | |
1052 // Since this is a new DEF, update Reachblock & UP | |
1053 Reachblock[slidx] = n->in(inpidx); | |
1054 UPblock[slidx] = true; | |
1055 insidx++; // Reset iterator to skip USE side split | |
1056 } | |
1057 } // End else DOWN | |
1058 } // End dup != uup | |
1059 } // End if Spill USE | |
1060 } // End For All Inputs | |
1061 } // End If not nullcheck | |
1062 | |
1063 // ********** Handle DEFS ********** | |
1064 // DEFS either Split DOWN in HRP regions or when the LRG is bound, or | |
1065 // just reset the Reaches info in LRP regions. DEFS must always update | |
1066 // UP info. | |
1067 if( deflrg.reg() >= LRG::SPILL_REG ) { // Spilled? | |
1068 uint slidx = lrg2reach[defidx]; | |
1069 // Add to defs list for later assignment of new live range number | |
1070 defs->push(n); | |
1071 // Set a flag on the Node indicating it has already spilled. | |
1072 // Only do it for capacity spills not conflict spills. | |
1073 if( !deflrg._direct_conflict ) | |
1074 set_was_spilled(n); | |
1075 assert(!n->is_Phi(),"Cannot insert Phi into DEFS list"); | |
1076 // Grab UP info for DEF | |
1077 const RegMask &dmask = n->out_RegMask(); | |
1078 bool defup = dmask.is_UP(); | |
1079 // Only split at Def if this is a HRP block or bound (and spilled once) | |
1080 if( !n->rematerialize() && | |
1081 (((dmask.is_bound1() || dmask.is_bound2() || dmask.is_misaligned_Pair()) && | |
1082 (deflrg._direct_conflict || deflrg._must_spill)) || | |
1083 // Check for LRG being up in a register and we are inside a high | |
1084 // pressure area. Spill it down immediately. | |
1085 (defup && is_high_pressure(b,&deflrg,insidx))) ) { | |
1086 assert( !n->rematerialize(), "" ); | |
1087 assert( !n->is_SpillCopy(), "" ); | |
1088 // Do a split at the def site. | |
1089 maxlrg = split_DEF( n, b, insidx, maxlrg, Reachblock, debug_defs, splits, slidx ); | |
1090 // If it wasn't split bail | |
1091 if (!maxlrg) { | |
1092 return 0; | |
1093 } | |
1094 // Split DEF's Down | |
1095 UPblock[slidx] = 0; | |
1096 #ifndef PRODUCT | |
1097 // DEBUG | |
1098 if( trace_spilling() ) { | |
1099 tty->print("\nNew Split DOWN DEF of Spill Idx "); | |
1100 tty->print("%d, UP %d:\n",slidx,false); | |
1101 n->dump(); | |
1102 } | |
1103 #endif | |
1104 } | |
1105 else { // Neither bound nor HRP, must be LRP | |
1106 // otherwise, just record the def | |
1107 Reachblock[slidx] = n; | |
1108 // UP should come from the outRegmask() of the DEF | |
1109 UPblock[slidx] = defup; | |
1110 // Update debug list of reaching down definitions, kill if DEF is UP | |
1111 debug_defs[slidx] = defup ? NULL : n; | |
1112 #ifndef PRODUCT | |
1113 // DEBUG | |
1114 if( trace_spilling() ) { | |
1115 tty->print("\nNew DEF of Spill Idx "); | |
1116 tty->print("%d, UP %d:\n",slidx,defup); | |
1117 n->dump(); | |
1118 } | |
1119 #endif | |
1120 } // End else LRP | |
1121 } // End if spill def | |
1122 | |
1123 // ********** Split Left Over Mem-Mem Moves ********** | |
1124 // Check for mem-mem copies and split them now. Do not do this | |
1125 // to copies about to be spilled; they will be Split shortly. | |
1126 if( copyidx ) { | |
1127 Node *use = n->in(copyidx); | |
1128 uint useidx = Find_id(use); | |
1129 if( useidx < _maxlrg && // This is not a new split | |
1130 OptoReg::is_stack(deflrg.reg()) && | |
1131 deflrg.reg() < LRG::SPILL_REG ) { // And DEF is from stack | |
1132 LRG &uselrg = lrgs(useidx); | |
1133 if( OptoReg::is_stack(uselrg.reg()) && | |
1134 uselrg.reg() < LRG::SPILL_REG && // USE is from stack | |
1135 deflrg.reg() != uselrg.reg() ) { // Not trivially removed | |
1136 uint def_ideal_reg = Matcher::base2reg[n->bottom_type()->base()]; | |
1137 const RegMask &def_rm = *Matcher::idealreg2regmask[def_ideal_reg]; | |
1138 const RegMask &use_rm = n->in_RegMask(copyidx); | |
1139 if( def_rm.overlap(use_rm) && n->is_SpillCopy() ) { // Bug 4707800, 'n' may be a storeSSL | |
1140 if (C->check_node_count(NodeLimitFudgeFactor, out_of_nodes)) { // Check when generating nodes | |
1141 return 0; | |
1142 } | |
1143 Node *spill = new (C) MachSpillCopyNode(use,use_rm,def_rm); | |
1144 n->set_req(copyidx,spill); | |
1145 n->as_MachSpillCopy()->set_in_RegMask(def_rm); | |
1146 // Put the spill just before the copy | |
1147 insert_proj( b, insidx++, spill, maxlrg++ ); | |
1148 } | |
1149 } | |
1150 } | |
1151 } | |
1152 } // End For All Instructions in Block - Non-PHI Pass | |
1153 | |
1154 // Check if each LRG is live out of this block so as not to propagate | |
1155 // beyond the last use of a LRG. | |
1156 for( slidx = 0; slidx < spill_cnt; slidx++ ) { | |
1157 uint defidx = lidxs.at(slidx); | |
1158 IndexSet *liveout = _live->live(b); | |
1159 if( !liveout->member(defidx) ) { | |
1160 #ifdef ASSERT | |
1161 // The index defidx is not live. Check the liveout array to ensure that | |
1162 // it contains no members which compress to defidx. Finding such an | |
1163 // instance may be a case to add liveout adjustment in compress_uf_map(). | |
1164 // See 5063219. | |
1165 uint member; | |
1166 IndexSetIterator isi(liveout); | |
1167 while ((member = isi.next()) != 0) { | |
1168 assert(defidx != Find_const(member), "Live out member has not been compressed"); | |
1169 } | |
1170 #endif | |
1171 Reachblock[slidx] = NULL; | |
1172 } else { | |
1173 assert(Reachblock[slidx] != NULL,"No reaching definition for liveout value"); | |
1174 } | |
1175 } | |
1176 #ifndef PRODUCT | |
1177 if( trace_spilling() ) | |
1178 b->dump(); | |
1179 #endif | |
1180 } // End For All Blocks | |
1181 | |
1182 //----------PASS 2---------- | |
1183 // Reset all DEF live range numbers here | |
1184 for( insidx = 0; insidx < defs->size(); insidx++ ) { | |
1185 // Grab the def | |
1186 n1 = defs->at(insidx); | |
1187 // Set new lidx for DEF | |
1188 new_lrg(n1, maxlrg++); | |
1189 } | |
1190 //----------Phi Node Splitting---------- | |
1191 // Clean up a phi here, and assign a new live range number | |
1192 // Cycle through this block's predecessors, collecting Reaches | |
1193 // info for each spilled LRG and update edges. | |
1194 // Walk the phis list to patch inputs, split phis, and name phis | |
1195 for( insidx = 0; insidx < phis->size(); insidx++ ) { | |
1196 Node *phi = phis->at(insidx); | |
1197 assert(phi->is_Phi(),"This list must only contain Phi Nodes"); | |
1198 Block *b = _cfg._bbs[phi->_idx]; | |
1199 // Grab the live range number | |
1200 uint lidx = Find_id(phi); | |
1201 uint slidx = lrg2reach[lidx]; | |
1202 // Update node to lidx map | |
1203 new_lrg(phi, maxlrg++); | |
1204 // Get PASS1's up/down decision for the block. | |
1205 int phi_up = !!UP_entry[slidx]->test(b->_pre_order); | |
1206 | |
1207 // Force down if double-spilling live range | |
1208 if( lrgs(lidx)._was_spilled1 ) | |
1209 phi_up = false; | |
1210 | |
1211 // When splitting a Phi we an split it normal or "inverted". | |
1212 // An inverted split makes the splits target the Phi's UP/DOWN | |
1213 // sense inverted; then the Phi is followed by a final def-side | |
1214 // split to invert back. It changes which blocks the spill code | |
1215 // goes in. | |
1216 | |
1217 // Walk the predecessor blocks and assign the reaching def to the Phi. | |
1218 // Split Phi nodes by placing USE side splits wherever the reaching | |
1219 // DEF has the wrong UP/DOWN value. | |
1220 for( uint i = 1; i < b->num_preds(); i++ ) { | |
1221 // Get predecessor block pre-order number | |
1222 Block *pred = _cfg._bbs[b->pred(i)->_idx]; | |
1223 pidx = pred->_pre_order; | |
1224 // Grab reaching def | |
1225 Node *def = Reaches[pidx][slidx]; | |
1226 assert( def, "must have reaching def" ); | |
1227 // If input up/down sense and reg-pressure DISagree | |
1228 if( def->rematerialize() ) { | |
1229 def = split_Rematerialize( def, pred, pred->end_idx(), maxlrg, splits, slidx, lrg2reach, Reachblock, false ); | |
1230 if( !def ) return 0; // Bail out | |
1231 } | |
1232 // Update the Phi's input edge array | |
1233 phi->set_req(i,def); | |
1234 // Grab the UP/DOWN sense for the input | |
1235 u1 = UP[pidx][slidx]; | |
1236 if( u1 != (phi_up != 0)) { | |
1237 maxlrg = split_USE(def, b, phi, i, maxlrg, !u1, false, splits,slidx); | |
1238 // If it wasn't split bail | |
1239 if (!maxlrg) { | |
1240 return 0; | |
1241 } | |
1242 } | |
1243 } // End for all inputs to the Phi | |
1244 } // End for all Phi Nodes | |
1245 // Update _maxlrg to save Union asserts | |
1246 _maxlrg = maxlrg; | |
1247 | |
1248 | |
1249 //----------PASS 3---------- | |
1250 // Pass over all Phi's to union the live ranges | |
1251 for( insidx = 0; insidx < phis->size(); insidx++ ) { | |
1252 Node *phi = phis->at(insidx); | |
1253 assert(phi->is_Phi(),"This list must only contain Phi Nodes"); | |
1254 // Walk all inputs to Phi and Union input live range with Phi live range | |
1255 for( uint i = 1; i < phi->req(); i++ ) { | |
1256 // Grab the input node | |
1257 Node *n = phi->in(i); | |
1258 assert( n, "" ); | |
1259 uint lidx = Find(n); | |
1260 uint pidx = Find(phi); | |
1261 if( lidx < pidx ) | |
1262 Union(n, phi); | |
1263 else if( lidx > pidx ) | |
1264 Union(phi, n); | |
1265 } // End for all inputs to the Phi Node | |
1266 } // End for all Phi Nodes | |
1267 // Now union all two address instructions | |
1268 for( insidx = 0; insidx < defs->size(); insidx++ ) { | |
1269 // Grab the def | |
1270 n1 = defs->at(insidx); | |
1271 // Set new lidx for DEF & handle 2-addr instructions | |
1272 if( n1->is_Mach() && ((twoidx = n1->as_Mach()->two_adr()) != 0) ) { | |
1273 assert( Find(n1->in(twoidx)) < maxlrg,"Assigning bad live range index"); | |
1274 // Union the input and output live ranges | |
1275 uint lr1 = Find(n1); | |
1276 uint lr2 = Find(n1->in(twoidx)); | |
1277 if( lr1 < lr2 ) | |
1278 Union(n1, n1->in(twoidx)); | |
1279 else if( lr1 > lr2 ) | |
1280 Union(n1->in(twoidx), n1); | |
1281 } // End if two address | |
1282 } // End for all defs | |
1283 // DEBUG | |
1284 #ifdef ASSERT | |
1285 // Validate all live range index assignments | |
1286 for( bidx = 0; bidx < _cfg._num_blocks; bidx++ ) { | |
1287 b = _cfg._blocks[bidx]; | |
1288 for( insidx = 0; insidx <= b->end_idx(); insidx++ ) { | |
1289 Node *n = b->_nodes[insidx]; | |
1290 uint defidx = Find(n); | |
1291 assert(defidx < _maxlrg,"Bad live range index in Split"); | |
1292 assert(defidx < maxlrg,"Bad live range index in Split"); | |
1293 } | |
1294 } | |
1295 // Issue a warning if splitting made no progress | |
1296 int noprogress = 0; | |
1297 for( slidx = 0; slidx < spill_cnt; slidx++ ) { | |
1298 if( PrintOpto && WizardMode && splits.at(slidx) == 0 ) { | |
1299 tty->print_cr("Failed to split live range %d", lidxs.at(slidx)); | |
1300 //BREAKPOINT; | |
1301 } | |
1302 else { | |
1303 noprogress++; | |
1304 } | |
1305 } | |
1306 if(!noprogress) { | |
1307 tty->print_cr("Failed to make progress in Split"); | |
1308 //BREAKPOINT; | |
1309 } | |
1310 #endif | |
1311 // Return updated count of live ranges | |
1312 return maxlrg; | |
1313 } |