38 // definitions. During propagation, split the live range around regions of
39 // High Register Pressure (HRP). If a Def is in a region of Low Register
40 // Pressure (LRP), it will not get spilled until we encounter a region of
41 // HRP between it and one of its uses. We will spill at the transition
42 // point between LRP and HRP. Uses in the HRP region will use the spilled
43 // Def. The first Use outside the HRP region will generate a SpillCopy to
44 // hoist the live range back up into a register, and all subsequent uses
45 // will use that new Def until another HRP region is encountered. Defs in
46 // HRP regions will get trailing SpillCopies to push the LRG down into the
47 // stack immediately.
48 //
49 // As a side effect, unlink from (hence make dead) coalesced copies.
50 //
51
52 static const char out_of_nodes[] = "out of nodes during split";
53
54 //------------------------------get_spillcopy_wide-----------------------------
55 // Get a SpillCopy node with wide-enough masks. Use the 'wide-mask', the
56 // wide ideal-register spill-mask if possible. If the 'wide-mask' does
57 // not cover the input (or output), use the input (or output) mask instead.
58 Node *PhaseChaitin::get_spillcopy_wide( Node *def, Node *use, uint uidx ) {
59 // If ideal reg doesn't exist we've got a bad schedule happening
60 // that is forcing us to spill something that isn't spillable.
61 // Bail rather than abort
62 int ireg = def->ideal_reg();
63 if( ireg == 0 || ireg == Op_RegFlags ) {
64 assert(false, "attempted to spill a non-spillable item");
65 C->record_method_not_compilable("attempted to spill a non-spillable item");
66 return NULL;
67 }
68 if (C->check_node_count(NodeLimitFudgeFactor, out_of_nodes)) {
69 return NULL;
70 }
71 const RegMask *i_mask = &def->out_RegMask();
72 const RegMask *w_mask = C->matcher()->idealreg2spillmask[ireg];
73 const RegMask *o_mask = use ? &use->in_RegMask(uidx) : w_mask;
74 const RegMask *w_i_mask = w_mask->overlap( *i_mask ) ? w_mask : i_mask;
75 const RegMask *w_o_mask;
76
77 int num_regs = RegMask::num_registers(ireg);
78 bool is_vect = RegMask::is_vector(ireg);
79 if( w_mask->overlap( *o_mask ) && // Overlap AND
80 ((num_regs == 1) // Single use or aligned
81 || is_vect // or vector
82 || !is_vect && o_mask->is_aligned_pairs()) ) {
83 assert(!is_vect || o_mask->is_aligned_sets(num_regs), "vectors are aligned");
84 // Don't come here for mis-aligned doubles
85 w_o_mask = w_mask;
86 } else { // wide ideal mask does not overlap with o_mask
87 // Mis-aligned doubles come here and XMM->FPR moves on x86.
88 w_o_mask = o_mask; // Must target desired registers
89 // Does the ideal-reg-mask overlap with o_mask? I.e., can I use
90 // a reg-reg move or do I need a trip across register classes
91 // (and thus through memory)?
92 if( !C->matcher()->idealreg2regmask[ireg]->overlap( *o_mask) && o_mask->is_UP() )
93 // Here we assume a trip through memory is required.
94 w_i_mask = &C->FIRST_STACK_mask();
95 }
96 return new (C) MachSpillCopyNode( def, *w_i_mask, *w_o_mask );
97 }
98
99 //------------------------------insert_proj------------------------------------
100 // Insert the spill at chosen location. Skip over any intervening Proj's or
101 // Phis. Skip over a CatchNode and projs, inserting in the fall-through block
102 // instead. Update high-pressure indices. Create a new live range.
103 void PhaseChaitin::insert_proj( Block *b, uint i, Node *spill, uint maxlrg ) {
104 // Skip intervening ProjNodes. Do not insert between a ProjNode and
105 // its definer.
106 while( i < b->number_of_nodes() &&
107 (b->get_node(i)->is_Proj() ||
108 b->get_node(i)->is_Phi() ) )
109 i++;
110
111 // Do not insert between a call and his Catch
112 if( b->get_node(i)->is_Catch() ) {
113 // Put the instruction at the top of the fall-thru block.
114 // Find the fall-thru projection
115 while( 1 ) {
116 const CatchProjNode *cp = b->get_node(++i)->as_CatchProj();
142 // happens inside Split, where the Leaveblock array is updated.
143 uint PhaseChaitin::split_DEF( Node *def, Block *b, int loc, uint maxlrg, Node **Reachblock, Node **debug_defs, GrowableArray<uint> splits, int slidx ) {
144 #ifdef ASSERT
145 // Increment the counter for this lrg
146 splits.at_put(slidx, splits.at(slidx)+1);
147 #endif
148 // If we are spilling the memory op for an implicit null check, at the
149 // null check location (ie - null check is in HRP block) we need to do
150 // the null-check first, then spill-down in the following block.
151 // (The implicit_null_check function ensures the use is also dominated
152 // by the branch-not-taken block.)
153 Node *be = b->end();
154 if( be->is_MachNullCheck() && be->in(1) == def && def == b->get_node(loc)) {
155 // Spill goes in the branch-not-taken block
156 b = b->_succs[b->get_node(b->end_idx()+1)->Opcode() == Op_IfTrue];
157 loc = 0; // Just past the Region
158 }
159 assert( loc >= 0, "must insert past block head" );
160
161 // Get a def-side SpillCopy
162 Node *spill = get_spillcopy_wide(def,NULL,0);
163 // Did we fail to split?, then bail
164 if (!spill) {
165 return 0;
166 }
167
168 // Insert the spill at chosen location
169 insert_proj( b, loc+1, spill, maxlrg++);
170
171 // Insert new node into Reaches array
172 Reachblock[slidx] = spill;
173 // Update debug list of reaching down definitions by adding this one
174 debug_defs[slidx] = spill;
175
176 // return updated count of live ranges
177 return maxlrg;
178 }
179
180 //------------------------------split_USE--------------------------------------
181 // Splits at uses can involve redeffing the LRG, so no CISC Spilling there.
182 // Debug uses want to know if def is already stack enabled.
183 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 ) {
184 #ifdef ASSERT
185 // Increment the counter for this lrg
186 splits.at_put(slidx, splits.at(slidx)+1);
187 #endif
188
189 // Some setup stuff for handling debug node uses
190 JVMState* jvms = use->jvms();
191 uint debug_start = jvms ? jvms->debug_start() : 999999;
192 uint debug_end = jvms ? jvms->debug_end() : 999999;
193
194 //-------------------------------------------
195 // Check for use of debug info
196 if (useidx >= debug_start && useidx < debug_end) {
197 // Actually it's perfectly legal for constant debug info to appear
198 // just unlikely. In this case the optimizer left a ConI of a 4
199 // as both inputs to a Phi with only a debug use. It's a single-def
200 // live range of a rematerializable value. The live range spills,
201 // rematerializes and now the ConI directly feeds into the debug info.
202 // assert(!def->is_Con(), "constant debug info already constructed directly");
203
204 // Special split handling for Debug Info
205 // If DEF is DOWN, just hook the edge and return
206 // If DEF is UP, Split it DOWN for this USE.
207 if( def->is_Mach() ) {
208 if( def_down ) {
209 // DEF is DOWN, so connect USE directly to the DEF
210 use->set_req(useidx, def);
211 } else {
212 // Block and index where the use occurs.
213 Block *b = _cfg.get_block_for_node(use);
214 // Put the clone just prior to use
215 int bindex = b->find_node(use);
216 // DEF is UP, so must copy it DOWN and hook in USE
217 // Insert SpillCopy before the USE, which uses DEF as its input,
218 // and defs a new live range, which is used by this node.
219 Node *spill = get_spillcopy_wide(def,use,useidx);
220 // did we fail to split?
221 if (!spill) {
222 // Bail
223 return 0;
224 }
225 // insert into basic block
226 insert_proj( b, bindex, spill, maxlrg++ );
227 // Use the new split
228 use->set_req(useidx,spill);
229 }
230 // No further split handling needed for this use
231 return maxlrg;
232 } // End special splitting for debug info live range
233 } // If debug info
234
235 // CISC-SPILLING
236 // Finally, check to see if USE is CISC-Spillable, and if so,
237 // gather_lrg_masks will add the flags bit to its mask, and
238 // no use side copy is needed. This frees up the live range
239 // register choices without causing copy coalescing, etc.
251 }
252 #endif
253 return maxlrg;
254 }
255 }
256
257 //-------------------------------------------
258 // Insert a Copy before the use
259
260 // Block and index where the use occurs.
261 int bindex;
262 // Phi input spill-copys belong at the end of the prior block
263 if( use->is_Phi() ) {
264 b = _cfg.get_block_for_node(b->pred(useidx));
265 bindex = b->end_idx();
266 } else {
267 // Put the clone just prior to use
268 bindex = b->find_node(use);
269 }
270
271 Node *spill = get_spillcopy_wide( def, use, useidx );
272 if( !spill ) return 0; // Bailed out
273 // Insert SpillCopy before the USE, which uses the reaching DEF as
274 // its input, and defs a new live range, which is used by this node.
275 insert_proj( b, bindex, spill, maxlrg++ );
276 // Use the spill/clone
277 use->set_req(useidx,spill);
278
279 // return updated live range count
280 return maxlrg;
281 }
282
283 //------------------------------clone_node----------------------------
284 // Clone node with anti dependence check.
285 Node* clone_node(Node* def, Block *b, Compile* C) {
286 if (def->needs_anti_dependence_check()) {
287 #ifdef ASSERT
288 if (Verbose) {
289 tty->print_cr("RA attempts to clone node with anti_dependence:");
290 def->dump(-1); tty->cr();
291 tty->print_cr("into block:");
310 // Clone a local copy of the def.
311 Node *PhaseChaitin::split_Rematerialize( Node *def, Block *b, uint insidx, uint &maxlrg, GrowableArray<uint> splits, int slidx, uint *lrg2reach, Node **Reachblock, bool walkThru ) {
312 // The input live ranges will be stretched to the site of the new
313 // instruction. They might be stretched past a def and will thus
314 // have the old and new values of the same live range alive at the
315 // same time - a definite no-no. Split out private copies of
316 // the inputs.
317 if( def->req() > 1 ) {
318 for( uint i = 1; i < def->req(); i++ ) {
319 Node *in = def->in(i);
320 uint lidx = _lrg_map.live_range_id(in);
321 // We do not need this for live ranges that are only defined once.
322 // However, this is not true for spill copies that are added in this
323 // Split() pass, since they might get coalesced later on in this pass.
324 if (lidx < _lrg_map.max_lrg_id() && lrgs(lidx).is_singledef()) {
325 continue;
326 }
327
328 Block *b_def = _cfg.get_block_for_node(def);
329 int idx_def = b_def->find_node(def);
330 Node *in_spill = get_spillcopy_wide( in, def, i );
331 if( !in_spill ) return 0; // Bailed out
332 insert_proj(b_def,idx_def,in_spill,maxlrg++);
333 if( b_def == b )
334 insidx++;
335 def->set_req(i,in_spill);
336 }
337 }
338
339 Node *spill = clone_node(def, b, C);
340 if (spill == NULL || C->check_node_count(NodeLimitFudgeFactor, out_of_nodes)) {
341 // Check when generating nodes
342 return 0;
343 }
344
345 // See if any inputs are currently being spilled, and take the
346 // latest copy of spilled inputs.
347 if( spill->req() > 1 ) {
348 for( uint i = 1; i < spill->req(); i++ ) {
349 Node *in = spill->in(i);
350 uint lidx = _lrg_map.find_id(in);
918 continue;
919 }
920
921 // Rematerializable? Then clone def at use site instead
922 // of store/load
923 if( def->rematerialize() ) {
924 int old_size = b->number_of_nodes();
925 def = split_Rematerialize( def, b, insidx, maxlrg, splits, slidx, lrg2reach, Reachblock, true );
926 if( !def ) return 0; // Bail out
927 insidx += b->number_of_nodes()-old_size;
928 }
929
930 MachNode *mach = n->is_Mach() ? n->as_Mach() : NULL;
931 // Base pointers and oopmap references do not care where they live.
932 if ((inpidx >= oopoff) ||
933 (mach && mach->ideal_Opcode() == Op_AddP && inpidx == AddPNode::Base)) {
934 if (def->rematerialize() && lrgs(useidx)._was_spilled2) {
935 // This def has been rematerialized a couple of times without
936 // progress. It doesn't care if it lives UP or DOWN, so
937 // spill it down now.
938 maxlrg = split_USE(def,b,n,inpidx,maxlrg,false,false,splits,slidx);
939 // If it wasn't split bail
940 if (!maxlrg) {
941 return 0;
942 }
943 insidx++; // Reset iterator to skip USE side split
944 } else {
945 // Just hook the def edge
946 n->set_req(inpidx, def);
947 }
948
949 if (inpidx >= oopoff) {
950 // After oopoff, we have derived/base pairs. We must mention all
951 // derived pointers here as derived/base pairs for GC. If the
952 // derived value is spilling and we have a copy both in Reachblock
953 // (called here 'def') and debug_defs[slidx] we need to mention
954 // both in derived/base pairs or kill one.
955 Node *derived_debug = debug_defs[slidx];
956 if( ((inpidx - oopoff) & 1) == DERIVED && // derived vs base?
957 mach && mach->ideal_Opcode() != Op_Halt &&
958 derived_debug != NULL &&
998 }
999 }
1000 // Grab register mask info
1001 const RegMask &dmask = def->out_RegMask();
1002 const RegMask &umask = n->in_RegMask(inpidx);
1003 bool is_vect = RegMask::is_vector(def->ideal_reg());
1004 assert(inpidx < oopoff, "cannot use-split oop map info");
1005
1006 bool dup = UPblock[slidx];
1007 bool uup = umask.is_UP();
1008
1009 // Need special logic to handle bound USES. Insert a split at this
1010 // bound use if we can't rematerialize the def, or if we need the
1011 // split to form a misaligned pair.
1012 if( !umask.is_AllStack() &&
1013 (int)umask.Size() <= lrgs(useidx).num_regs() &&
1014 (!def->rematerialize() ||
1015 !is_vect && umask.is_misaligned_pair())) {
1016 // These need a Split regardless of overlap or pressure
1017 // SPLIT - NO DEF - NO CISC SPILL
1018 maxlrg = split_USE(def,b,n,inpidx,maxlrg,dup,false, splits,slidx);
1019 // If it wasn't split bail
1020 if (!maxlrg) {
1021 return 0;
1022 }
1023 insidx++; // Reset iterator to skip USE side split
1024 continue;
1025 }
1026
1027 if (UseFPUForSpilling && n->is_MachCall() && !uup && !dup ) {
1028 // The use at the call can force the def down so insert
1029 // a split before the use to allow the def more freedom.
1030 maxlrg = split_USE(def,b,n,inpidx,maxlrg,dup,false, splits,slidx);
1031 // If it wasn't split bail
1032 if (!maxlrg) {
1033 return 0;
1034 }
1035 insidx++; // Reset iterator to skip USE side split
1036 continue;
1037 }
1038
1039 // Here is the logic chart which describes USE Splitting:
1040 // 0 = false or DOWN, 1 = true or UP
1041 //
1042 // Overlap | DEF | USE | Action
1043 //-------------------------------------------------------
1044 // 0 | 0 | 0 | Copy - mem -> mem
1045 // 0 | 0 | 1 | Split-UP - Check HRP
1046 // 0 | 1 | 0 | Split-DOWN - Debug Info?
1047 // 0 | 1 | 1 | Copy - reg -> reg
1048 // 1 | 0 | 0 | Reset Input Edge (no Split)
1049 // 1 | 0 | 1 | Split-UP - Check HRP
1050 // 1 | 1 | 0 | Split-DOWN - Debug Info?
1051 // 1 | 1 | 1 | Reset Input Edge (no Split)
1052 //
1053 // So, if (dup == uup), then overlap test determines action,
1054 // with true being no split, and false being copy. Else,
1055 // if DEF is DOWN, Split-UP, and check HRP to decide on
1056 // resetting DEF. Finally if DEF is UP, Split-DOWN, with
1057 // special handling for Debug Info.
1058 if( dup == uup ) {
1059 if( dmask.overlap(umask) ) {
1060 // Both are either up or down, and there is overlap, No Split
1061 n->set_req(inpidx, def);
1062 }
1063 else { // Both are either up or down, and there is no overlap
1064 if( dup ) { // If UP, reg->reg copy
1065 // COPY ACROSS HERE - NO DEF - NO CISC SPILL
1066 maxlrg = split_USE(def,b,n,inpidx,maxlrg,false,false, splits,slidx);
1067 // If it wasn't split bail
1068 if (!maxlrg) {
1069 return 0;
1070 }
1071 insidx++; // Reset iterator to skip USE side split
1072 }
1073 else { // DOWN, mem->mem copy
1074 // COPY UP & DOWN HERE - NO DEF - NO CISC SPILL
1075 // First Split-UP to move value into Register
1076 uint def_ideal = def->ideal_reg();
1077 const RegMask* tmp_rm = Matcher::idealreg2regmask[def_ideal];
1078 Node *spill = new (C) MachSpillCopyNode(def, dmask, *tmp_rm);
1079 insert_proj( b, insidx, spill, maxlrg );
1080 // Then Split-DOWN as if previous Split was DEF
1081 maxlrg = split_USE(spill,b,n,inpidx,maxlrg,false,false, splits,slidx);
1082 // If it wasn't split bail
1083 if (!maxlrg) {
1084 return 0;
1085 }
1086 insidx += 2; // Reset iterator to skip USE side splits
1087 }
1088 } // End else no overlap
1089 } // End if dup == uup
1090 // dup != uup, so check dup for direction of Split
1091 else {
1092 if( dup ) { // If UP, Split-DOWN and check Debug Info
1093 // If this node is already a SpillCopy, just patch the edge
1094 // except the case of spilling to stack.
1095 if( n->is_SpillCopy() ) {
1096 RegMask tmp_rm(umask);
1097 tmp_rm.SUBTRACT(Matcher::STACK_ONLY_mask);
1098 if( dmask.overlap(tmp_rm) ) {
1099 if( def != n->in(inpidx) ) {
1100 n->set_req(inpidx, def);
1101 }
1102 continue;
1103 }
1104 }
1105 // COPY DOWN HERE - NO DEF - NO CISC SPILL
1106 maxlrg = split_USE(def,b,n,inpidx,maxlrg,false,false, splits,slidx);
1107 // If it wasn't split bail
1108 if (!maxlrg) {
1109 return 0;
1110 }
1111 insidx++; // Reset iterator to skip USE side split
1112 // Check for debug-info split. Capture it for later
1113 // debug splits of the same value
1114 if (jvms && jvms->debug_start() <= inpidx && inpidx < oopoff)
1115 debug_defs[slidx] = n->in(inpidx);
1116
1117 }
1118 else { // DOWN, Split-UP and check register pressure
1119 if( is_high_pressure( b, &lrgs(useidx), insidx ) ) {
1120 // COPY UP HERE - NO DEF - CISC SPILL
1121 maxlrg = split_USE(def,b,n,inpidx,maxlrg,true,true, splits,slidx);
1122 // If it wasn't split bail
1123 if (!maxlrg) {
1124 return 0;
1125 }
1126 insidx++; // Reset iterator to skip USE side split
1127 } else { // LRP
1128 // COPY UP HERE - WITH DEF - NO CISC SPILL
1129 maxlrg = split_USE(def,b,n,inpidx,maxlrg,true,false, splits,slidx);
1130 // If it wasn't split bail
1131 if (!maxlrg) {
1132 return 0;
1133 }
1134 // Flag this lift-up in a low-pressure block as
1135 // already-spilled, so if it spills again it will
1136 // spill hard (instead of not spilling hard and
1137 // coalescing away).
1138 set_was_spilled(n->in(inpidx));
1139 // Since this is a new DEF, update Reachblock & UP
1140 Reachblock[slidx] = n->in(inpidx);
1141 UPblock[slidx] = true;
1142 insidx++; // Reset iterator to skip USE side split
1143 }
1144 } // End else DOWN
1145 } // End dup != uup
1146 } // End if Spill USE
1147 } // End For All Inputs
1148 } // End If not nullcheck
1149
1212 // ********** Split Left Over Mem-Mem Moves **********
1213 // Check for mem-mem copies and split them now. Do not do this
1214 // to copies about to be spilled; they will be Split shortly.
1215 if (copyidx) {
1216 Node *use = n->in(copyidx);
1217 uint useidx = _lrg_map.find_id(use);
1218 if (useidx < _lrg_map.max_lrg_id() && // This is not a new split
1219 OptoReg::is_stack(deflrg.reg()) &&
1220 deflrg.reg() < LRG::SPILL_REG ) { // And DEF is from stack
1221 LRG &uselrg = lrgs(useidx);
1222 if( OptoReg::is_stack(uselrg.reg()) &&
1223 uselrg.reg() < LRG::SPILL_REG && // USE is from stack
1224 deflrg.reg() != uselrg.reg() ) { // Not trivially removed
1225 uint def_ideal_reg = n->bottom_type()->ideal_reg();
1226 const RegMask &def_rm = *Matcher::idealreg2regmask[def_ideal_reg];
1227 const RegMask &use_rm = n->in_RegMask(copyidx);
1228 if( def_rm.overlap(use_rm) && n->is_SpillCopy() ) { // Bug 4707800, 'n' may be a storeSSL
1229 if (C->check_node_count(NodeLimitFudgeFactor, out_of_nodes)) { // Check when generating nodes
1230 return 0;
1231 }
1232 Node *spill = new (C) MachSpillCopyNode(use,use_rm,def_rm);
1233 n->set_req(copyidx,spill);
1234 n->as_MachSpillCopy()->set_in_RegMask(def_rm);
1235 // Put the spill just before the copy
1236 insert_proj( b, insidx++, spill, maxlrg++ );
1237 }
1238 }
1239 }
1240 }
1241 } // End For All Instructions in Block - Non-PHI Pass
1242
1243 // Check if each LRG is live out of this block so as not to propagate
1244 // beyond the last use of a LRG.
1245 for( slidx = 0; slidx < spill_cnt; slidx++ ) {
1246 uint defidx = lidxs.at(slidx);
1247 IndexSet *liveout = _live->live(b);
1248 if( !liveout->member(defidx) ) {
1249 #ifdef ASSERT
1250 // The index defidx is not live. Check the liveout array to ensure that
1251 // it contains no members which compress to defidx. Finding such an
1252 // instance may be a case to add liveout adjustment in compress_uf_map().
1319 if (def->rematerialize()) {
1320 // Place the rematerialized node above any MSCs created during
1321 // phi node splitting. end_idx points at the insertion point
1322 // so look at the node before it.
1323 int insert = pred->end_idx();
1324 while (insert >= 1 &&
1325 pred->get_node(insert - 1)->is_SpillCopy() &&
1326 _lrg_map.find(pred->get_node(insert - 1)) >= lrgs_before_phi_split) {
1327 insert--;
1328 }
1329 def = split_Rematerialize(def, pred, insert, maxlrg, splits, slidx, lrg2reach, Reachblock, false);
1330 if (!def) {
1331 return 0; // Bail out
1332 }
1333 }
1334 // Update the Phi's input edge array
1335 phi->set_req(i,def);
1336 // Grab the UP/DOWN sense for the input
1337 u1 = UP[pidx][slidx];
1338 if( u1 != (phi_up != 0)) {
1339 maxlrg = split_USE(def, b, phi, i, maxlrg, !u1, false, splits,slidx);
1340 // If it wasn't split bail
1341 if (!maxlrg) {
1342 return 0;
1343 }
1344 }
1345 } // End for all inputs to the Phi
1346 } // End for all Phi Nodes
1347 // Update _maxlrg to save Union asserts
1348 _lrg_map.set_max_lrg_id(maxlrg);
1349
1350
1351 //----------PASS 3----------
1352 // Pass over all Phi's to union the live ranges
1353 for( insidx = 0; insidx < phis->size(); insidx++ ) {
1354 Node *phi = phis->at(insidx);
1355 assert(phi->is_Phi(),"This list must only contain Phi Nodes");
1356 // Walk all inputs to Phi and Union input live range with Phi live range
1357 for( uint i = 1; i < phi->req(); i++ ) {
1358 // Grab the input node
1359 Node *n = phi->in(i);
|
38 // definitions. During propagation, split the live range around regions of
39 // High Register Pressure (HRP). If a Def is in a region of Low Register
40 // Pressure (LRP), it will not get spilled until we encounter a region of
41 // HRP between it and one of its uses. We will spill at the transition
42 // point between LRP and HRP. Uses in the HRP region will use the spilled
43 // Def. The first Use outside the HRP region will generate a SpillCopy to
44 // hoist the live range back up into a register, and all subsequent uses
45 // will use that new Def until another HRP region is encountered. Defs in
46 // HRP regions will get trailing SpillCopies to push the LRG down into the
47 // stack immediately.
48 //
49 // As a side effect, unlink from (hence make dead) coalesced copies.
50 //
51
52 static const char out_of_nodes[] = "out of nodes during split";
53
54 //------------------------------get_spillcopy_wide-----------------------------
55 // Get a SpillCopy node with wide-enough masks. Use the 'wide-mask', the
56 // wide ideal-register spill-mask if possible. If the 'wide-mask' does
57 // not cover the input (or output), use the input (or output) mask instead.
58 Node *PhaseChaitin::get_spillcopy_wide(MachSpillCopyNode::SpillType spill_type, Node *def, Node *use, uint uidx ) {
59 // If ideal reg doesn't exist we've got a bad schedule happening
60 // that is forcing us to spill something that isn't spillable.
61 // Bail rather than abort
62 int ireg = def->ideal_reg();
63 if( ireg == 0 || ireg == Op_RegFlags ) {
64 assert(false, "attempted to spill a non-spillable item");
65 C->record_method_not_compilable("attempted to spill a non-spillable item");
66 return NULL;
67 }
68 if (C->check_node_count(NodeLimitFudgeFactor, out_of_nodes)) {
69 return NULL;
70 }
71 const RegMask *i_mask = &def->out_RegMask();
72 const RegMask *w_mask = C->matcher()->idealreg2spillmask[ireg];
73 const RegMask *o_mask = use ? &use->in_RegMask(uidx) : w_mask;
74 const RegMask *w_i_mask = w_mask->overlap( *i_mask ) ? w_mask : i_mask;
75 const RegMask *w_o_mask;
76
77 int num_regs = RegMask::num_registers(ireg);
78 bool is_vect = RegMask::is_vector(ireg);
79 if( w_mask->overlap( *o_mask ) && // Overlap AND
80 ((num_regs == 1) // Single use or aligned
81 || is_vect // or vector
82 || !is_vect && o_mask->is_aligned_pairs()) ) {
83 assert(!is_vect || o_mask->is_aligned_sets(num_regs), "vectors are aligned");
84 // Don't come here for mis-aligned doubles
85 w_o_mask = w_mask;
86 } else { // wide ideal mask does not overlap with o_mask
87 // Mis-aligned doubles come here and XMM->FPR moves on x86.
88 w_o_mask = o_mask; // Must target desired registers
89 // Does the ideal-reg-mask overlap with o_mask? I.e., can I use
90 // a reg-reg move or do I need a trip across register classes
91 // (and thus through memory)?
92 if( !C->matcher()->idealreg2regmask[ireg]->overlap( *o_mask) && o_mask->is_UP() )
93 // Here we assume a trip through memory is required.
94 w_i_mask = &C->FIRST_STACK_mask();
95 }
96 return new (C) MachSpillCopyNode(spill_type, def, *w_i_mask, *w_o_mask );
97 }
98
99 //------------------------------insert_proj------------------------------------
100 // Insert the spill at chosen location. Skip over any intervening Proj's or
101 // Phis. Skip over a CatchNode and projs, inserting in the fall-through block
102 // instead. Update high-pressure indices. Create a new live range.
103 void PhaseChaitin::insert_proj( Block *b, uint i, Node *spill, uint maxlrg ) {
104 // Skip intervening ProjNodes. Do not insert between a ProjNode and
105 // its definer.
106 while( i < b->number_of_nodes() &&
107 (b->get_node(i)->is_Proj() ||
108 b->get_node(i)->is_Phi() ) )
109 i++;
110
111 // Do not insert between a call and his Catch
112 if( b->get_node(i)->is_Catch() ) {
113 // Put the instruction at the top of the fall-thru block.
114 // Find the fall-thru projection
115 while( 1 ) {
116 const CatchProjNode *cp = b->get_node(++i)->as_CatchProj();
142 // happens inside Split, where the Leaveblock array is updated.
143 uint PhaseChaitin::split_DEF( Node *def, Block *b, int loc, uint maxlrg, Node **Reachblock, Node **debug_defs, GrowableArray<uint> splits, int slidx ) {
144 #ifdef ASSERT
145 // Increment the counter for this lrg
146 splits.at_put(slidx, splits.at(slidx)+1);
147 #endif
148 // If we are spilling the memory op for an implicit null check, at the
149 // null check location (ie - null check is in HRP block) we need to do
150 // the null-check first, then spill-down in the following block.
151 // (The implicit_null_check function ensures the use is also dominated
152 // by the branch-not-taken block.)
153 Node *be = b->end();
154 if( be->is_MachNullCheck() && be->in(1) == def && def == b->get_node(loc)) {
155 // Spill goes in the branch-not-taken block
156 b = b->_succs[b->get_node(b->end_idx()+1)->Opcode() == Op_IfTrue];
157 loc = 0; // Just past the Region
158 }
159 assert( loc >= 0, "must insert past block head" );
160
161 // Get a def-side SpillCopy
162 Node *spill = get_spillcopy_wide(MachSpillCopyNode::Definition, def, NULL, 0);
163 // Did we fail to split?, then bail
164 if (!spill) {
165 return 0;
166 }
167
168 // Insert the spill at chosen location
169 insert_proj( b, loc+1, spill, maxlrg++);
170
171 // Insert new node into Reaches array
172 Reachblock[slidx] = spill;
173 // Update debug list of reaching down definitions by adding this one
174 debug_defs[slidx] = spill;
175
176 // return updated count of live ranges
177 return maxlrg;
178 }
179
180 //------------------------------split_USE--------------------------------------
181 // Splits at uses can involve redeffing the LRG, so no CISC Spilling there.
182 // Debug uses want to know if def is already stack enabled.
183 uint PhaseChaitin::split_USE(MachSpillCopyNode::SpillType spill_type, Node *def, Block *b, Node *use, uint useidx, uint maxlrg, bool def_down, bool cisc_sp, GrowableArray<uint> splits, int slidx ) {
184 #ifdef ASSERT
185 // Increment the counter for this lrg
186 splits.at_put(slidx, splits.at(slidx)+1);
187 #endif
188
189 // Some setup stuff for handling debug node uses
190 JVMState* jvms = use->jvms();
191 uint debug_start = jvms ? jvms->debug_start() : 999999;
192 uint debug_end = jvms ? jvms->debug_end() : 999999;
193
194 //-------------------------------------------
195 // Check for use of debug info
196 if (useidx >= debug_start && useidx < debug_end) {
197 // Actually it's perfectly legal for constant debug info to appear
198 // just unlikely. In this case the optimizer left a ConI of a 4
199 // as both inputs to a Phi with only a debug use. It's a single-def
200 // live range of a rematerializable value. The live range spills,
201 // rematerializes and now the ConI directly feeds into the debug info.
202 // assert(!def->is_Con(), "constant debug info already constructed directly");
203
204 // Special split handling for Debug Info
205 // If DEF is DOWN, just hook the edge and return
206 // If DEF is UP, Split it DOWN for this USE.
207 if( def->is_Mach() ) {
208 if( def_down ) {
209 // DEF is DOWN, so connect USE directly to the DEF
210 use->set_req(useidx, def);
211 } else {
212 // Block and index where the use occurs.
213 Block *b = _cfg.get_block_for_node(use);
214 // Put the clone just prior to use
215 int bindex = b->find_node(use);
216 // DEF is UP, so must copy it DOWN and hook in USE
217 // Insert SpillCopy before the USE, which uses DEF as its input,
218 // and defs a new live range, which is used by this node.
219 Node *spill = get_spillcopy_wide(spill_type, def,use,useidx);
220 // did we fail to split?
221 if (!spill) {
222 // Bail
223 return 0;
224 }
225 // insert into basic block
226 insert_proj( b, bindex, spill, maxlrg++ );
227 // Use the new split
228 use->set_req(useidx,spill);
229 }
230 // No further split handling needed for this use
231 return maxlrg;
232 } // End special splitting for debug info live range
233 } // If debug info
234
235 // CISC-SPILLING
236 // Finally, check to see if USE is CISC-Spillable, and if so,
237 // gather_lrg_masks will add the flags bit to its mask, and
238 // no use side copy is needed. This frees up the live range
239 // register choices without causing copy coalescing, etc.
251 }
252 #endif
253 return maxlrg;
254 }
255 }
256
257 //-------------------------------------------
258 // Insert a Copy before the use
259
260 // Block and index where the use occurs.
261 int bindex;
262 // Phi input spill-copys belong at the end of the prior block
263 if( use->is_Phi() ) {
264 b = _cfg.get_block_for_node(b->pred(useidx));
265 bindex = b->end_idx();
266 } else {
267 // Put the clone just prior to use
268 bindex = b->find_node(use);
269 }
270
271 Node *spill = get_spillcopy_wide(spill_type, def, use, useidx );
272 if( !spill ) return 0; // Bailed out
273 // Insert SpillCopy before the USE, which uses the reaching DEF as
274 // its input, and defs a new live range, which is used by this node.
275 insert_proj( b, bindex, spill, maxlrg++ );
276 // Use the spill/clone
277 use->set_req(useidx,spill);
278
279 // return updated live range count
280 return maxlrg;
281 }
282
283 //------------------------------clone_node----------------------------
284 // Clone node with anti dependence check.
285 Node* clone_node(Node* def, Block *b, Compile* C) {
286 if (def->needs_anti_dependence_check()) {
287 #ifdef ASSERT
288 if (Verbose) {
289 tty->print_cr("RA attempts to clone node with anti_dependence:");
290 def->dump(-1); tty->cr();
291 tty->print_cr("into block:");
310 // Clone a local copy of the def.
311 Node *PhaseChaitin::split_Rematerialize( Node *def, Block *b, uint insidx, uint &maxlrg, GrowableArray<uint> splits, int slidx, uint *lrg2reach, Node **Reachblock, bool walkThru ) {
312 // The input live ranges will be stretched to the site of the new
313 // instruction. They might be stretched past a def and will thus
314 // have the old and new values of the same live range alive at the
315 // same time - a definite no-no. Split out private copies of
316 // the inputs.
317 if( def->req() > 1 ) {
318 for( uint i = 1; i < def->req(); i++ ) {
319 Node *in = def->in(i);
320 uint lidx = _lrg_map.live_range_id(in);
321 // We do not need this for live ranges that are only defined once.
322 // However, this is not true for spill copies that are added in this
323 // Split() pass, since they might get coalesced later on in this pass.
324 if (lidx < _lrg_map.max_lrg_id() && lrgs(lidx).is_singledef()) {
325 continue;
326 }
327
328 Block *b_def = _cfg.get_block_for_node(def);
329 int idx_def = b_def->find_node(def);
330 Node *in_spill = get_spillcopy_wide(MachSpillCopyNode::InputToRematerialization, in, def, i );
331 if( !in_spill ) return 0; // Bailed out
332 insert_proj(b_def,idx_def,in_spill,maxlrg++);
333 if( b_def == b )
334 insidx++;
335 def->set_req(i,in_spill);
336 }
337 }
338
339 Node *spill = clone_node(def, b, C);
340 if (spill == NULL || C->check_node_count(NodeLimitFudgeFactor, out_of_nodes)) {
341 // Check when generating nodes
342 return 0;
343 }
344
345 // See if any inputs are currently being spilled, and take the
346 // latest copy of spilled inputs.
347 if( spill->req() > 1 ) {
348 for( uint i = 1; i < spill->req(); i++ ) {
349 Node *in = spill->in(i);
350 uint lidx = _lrg_map.find_id(in);
918 continue;
919 }
920
921 // Rematerializable? Then clone def at use site instead
922 // of store/load
923 if( def->rematerialize() ) {
924 int old_size = b->number_of_nodes();
925 def = split_Rematerialize( def, b, insidx, maxlrg, splits, slidx, lrg2reach, Reachblock, true );
926 if( !def ) return 0; // Bail out
927 insidx += b->number_of_nodes()-old_size;
928 }
929
930 MachNode *mach = n->is_Mach() ? n->as_Mach() : NULL;
931 // Base pointers and oopmap references do not care where they live.
932 if ((inpidx >= oopoff) ||
933 (mach && mach->ideal_Opcode() == Op_AddP && inpidx == AddPNode::Base)) {
934 if (def->rematerialize() && lrgs(useidx)._was_spilled2) {
935 // This def has been rematerialized a couple of times without
936 // progress. It doesn't care if it lives UP or DOWN, so
937 // spill it down now.
938 maxlrg = split_USE(MachSpillCopyNode::BasePointerToMem, def,b,n,inpidx,maxlrg,false,false,splits,slidx);
939 // If it wasn't split bail
940 if (!maxlrg) {
941 return 0;
942 }
943 insidx++; // Reset iterator to skip USE side split
944 } else {
945 // Just hook the def edge
946 n->set_req(inpidx, def);
947 }
948
949 if (inpidx >= oopoff) {
950 // After oopoff, we have derived/base pairs. We must mention all
951 // derived pointers here as derived/base pairs for GC. If the
952 // derived value is spilling and we have a copy both in Reachblock
953 // (called here 'def') and debug_defs[slidx] we need to mention
954 // both in derived/base pairs or kill one.
955 Node *derived_debug = debug_defs[slidx];
956 if( ((inpidx - oopoff) & 1) == DERIVED && // derived vs base?
957 mach && mach->ideal_Opcode() != Op_Halt &&
958 derived_debug != NULL &&
998 }
999 }
1000 // Grab register mask info
1001 const RegMask &dmask = def->out_RegMask();
1002 const RegMask &umask = n->in_RegMask(inpidx);
1003 bool is_vect = RegMask::is_vector(def->ideal_reg());
1004 assert(inpidx < oopoff, "cannot use-split oop map info");
1005
1006 bool dup = UPblock[slidx];
1007 bool uup = umask.is_UP();
1008
1009 // Need special logic to handle bound USES. Insert a split at this
1010 // bound use if we can't rematerialize the def, or if we need the
1011 // split to form a misaligned pair.
1012 if( !umask.is_AllStack() &&
1013 (int)umask.Size() <= lrgs(useidx).num_regs() &&
1014 (!def->rematerialize() ||
1015 !is_vect && umask.is_misaligned_pair())) {
1016 // These need a Split regardless of overlap or pressure
1017 // SPLIT - NO DEF - NO CISC SPILL
1018 maxlrg = split_USE(MachSpillCopyNode::Bound, def,b,n,inpidx,maxlrg,dup,false, splits,slidx);
1019 // If it wasn't split bail
1020 if (!maxlrg) {
1021 return 0;
1022 }
1023 insidx++; // Reset iterator to skip USE side split
1024 continue;
1025 }
1026
1027 if (UseFPUForSpilling && n->is_MachCall() && !uup && !dup ) {
1028 // The use at the call can force the def down so insert
1029 // a split before the use to allow the def more freedom.
1030 maxlrg = split_USE(MachSpillCopyNode::CallUse, def,b,n,inpidx,maxlrg,dup,false, splits,slidx);
1031 // If it wasn't split bail
1032 if (!maxlrg) {
1033 return 0;
1034 }
1035 insidx++; // Reset iterator to skip USE side split
1036 continue;
1037 }
1038
1039 // Here is the logic chart which describes USE Splitting:
1040 // 0 = false or DOWN, 1 = true or UP
1041 //
1042 // Overlap | DEF | USE | Action
1043 //-------------------------------------------------------
1044 // 0 | 0 | 0 | Copy - mem -> mem
1045 // 0 | 0 | 1 | Split-UP - Check HRP
1046 // 0 | 1 | 0 | Split-DOWN - Debug Info?
1047 // 0 | 1 | 1 | Copy - reg -> reg
1048 // 1 | 0 | 0 | Reset Input Edge (no Split)
1049 // 1 | 0 | 1 | Split-UP - Check HRP
1050 // 1 | 1 | 0 | Split-DOWN - Debug Info?
1051 // 1 | 1 | 1 | Reset Input Edge (no Split)
1052 //
1053 // So, if (dup == uup), then overlap test determines action,
1054 // with true being no split, and false being copy. Else,
1055 // if DEF is DOWN, Split-UP, and check HRP to decide on
1056 // resetting DEF. Finally if DEF is UP, Split-DOWN, with
1057 // special handling for Debug Info.
1058 if( dup == uup ) {
1059 if( dmask.overlap(umask) ) {
1060 // Both are either up or down, and there is overlap, No Split
1061 n->set_req(inpidx, def);
1062 }
1063 else { // Both are either up or down, and there is no overlap
1064 if( dup ) { // If UP, reg->reg copy
1065 // COPY ACROSS HERE - NO DEF - NO CISC SPILL
1066 maxlrg = split_USE(MachSpillCopyNode::RegToReg, def,b,n,inpidx,maxlrg,false,false, splits,slidx);
1067 // If it wasn't split bail
1068 if (!maxlrg) {
1069 return 0;
1070 }
1071 insidx++; // Reset iterator to skip USE side split
1072 }
1073 else { // DOWN, mem->mem copy
1074 // COPY UP & DOWN HERE - NO DEF - NO CISC SPILL
1075 // First Split-UP to move value into Register
1076 uint def_ideal = def->ideal_reg();
1077 const RegMask* tmp_rm = Matcher::idealreg2regmask[def_ideal];
1078 Node *spill = new (C) MachSpillCopyNode(MachSpillCopyNode::MemToReg, def, dmask, *tmp_rm);
1079 insert_proj( b, insidx, spill, maxlrg );
1080 // Then Split-DOWN as if previous Split was DEF
1081 maxlrg = split_USE(MachSpillCopyNode::RegToMem, spill,b,n,inpidx,maxlrg,false,false, splits,slidx);
1082 // If it wasn't split bail
1083 if (!maxlrg) {
1084 return 0;
1085 }
1086 insidx += 2; // Reset iterator to skip USE side splits
1087 }
1088 } // End else no overlap
1089 } // End if dup == uup
1090 // dup != uup, so check dup for direction of Split
1091 else {
1092 if( dup ) { // If UP, Split-DOWN and check Debug Info
1093 // If this node is already a SpillCopy, just patch the edge
1094 // except the case of spilling to stack.
1095 if( n->is_SpillCopy() ) {
1096 RegMask tmp_rm(umask);
1097 tmp_rm.SUBTRACT(Matcher::STACK_ONLY_mask);
1098 if( dmask.overlap(tmp_rm) ) {
1099 if( def != n->in(inpidx) ) {
1100 n->set_req(inpidx, def);
1101 }
1102 continue;
1103 }
1104 }
1105 // COPY DOWN HERE - NO DEF - NO CISC SPILL
1106 maxlrg = split_USE(MachSpillCopyNode::RegToMem, def,b,n,inpidx,maxlrg,false,false, splits,slidx);
1107 // If it wasn't split bail
1108 if (!maxlrg) {
1109 return 0;
1110 }
1111 insidx++; // Reset iterator to skip USE side split
1112 // Check for debug-info split. Capture it for later
1113 // debug splits of the same value
1114 if (jvms && jvms->debug_start() <= inpidx && inpidx < oopoff)
1115 debug_defs[slidx] = n->in(inpidx);
1116
1117 }
1118 else { // DOWN, Split-UP and check register pressure
1119 if( is_high_pressure( b, &lrgs(useidx), insidx ) ) {
1120 // COPY UP HERE - NO DEF - CISC SPILL
1121 maxlrg = split_USE(MachSpillCopyNode::MemToReg, def,b,n,inpidx,maxlrg,true,true, splits,slidx);
1122 // If it wasn't split bail
1123 if (!maxlrg) {
1124 return 0;
1125 }
1126 insidx++; // Reset iterator to skip USE side split
1127 } else { // LRP
1128 // COPY UP HERE - WITH DEF - NO CISC SPILL
1129 maxlrg = split_USE(MachSpillCopyNode::MemToReg, def,b,n,inpidx,maxlrg,true,false, splits,slidx);
1130 // If it wasn't split bail
1131 if (!maxlrg) {
1132 return 0;
1133 }
1134 // Flag this lift-up in a low-pressure block as
1135 // already-spilled, so if it spills again it will
1136 // spill hard (instead of not spilling hard and
1137 // coalescing away).
1138 set_was_spilled(n->in(inpidx));
1139 // Since this is a new DEF, update Reachblock & UP
1140 Reachblock[slidx] = n->in(inpidx);
1141 UPblock[slidx] = true;
1142 insidx++; // Reset iterator to skip USE side split
1143 }
1144 } // End else DOWN
1145 } // End dup != uup
1146 } // End if Spill USE
1147 } // End For All Inputs
1148 } // End If not nullcheck
1149
1212 // ********** Split Left Over Mem-Mem Moves **********
1213 // Check for mem-mem copies and split them now. Do not do this
1214 // to copies about to be spilled; they will be Split shortly.
1215 if (copyidx) {
1216 Node *use = n->in(copyidx);
1217 uint useidx = _lrg_map.find_id(use);
1218 if (useidx < _lrg_map.max_lrg_id() && // This is not a new split
1219 OptoReg::is_stack(deflrg.reg()) &&
1220 deflrg.reg() < LRG::SPILL_REG ) { // And DEF is from stack
1221 LRG &uselrg = lrgs(useidx);
1222 if( OptoReg::is_stack(uselrg.reg()) &&
1223 uselrg.reg() < LRG::SPILL_REG && // USE is from stack
1224 deflrg.reg() != uselrg.reg() ) { // Not trivially removed
1225 uint def_ideal_reg = n->bottom_type()->ideal_reg();
1226 const RegMask &def_rm = *Matcher::idealreg2regmask[def_ideal_reg];
1227 const RegMask &use_rm = n->in_RegMask(copyidx);
1228 if( def_rm.overlap(use_rm) && n->is_SpillCopy() ) { // Bug 4707800, 'n' may be a storeSSL
1229 if (C->check_node_count(NodeLimitFudgeFactor, out_of_nodes)) { // Check when generating nodes
1230 return 0;
1231 }
1232 Node *spill = new (C) MachSpillCopyNode(MachSpillCopyNode::MemToReg, use,use_rm,def_rm);
1233 n->set_req(copyidx,spill);
1234 n->as_MachSpillCopy()->set_in_RegMask(def_rm);
1235 // Put the spill just before the copy
1236 insert_proj( b, insidx++, spill, maxlrg++ );
1237 }
1238 }
1239 }
1240 }
1241 } // End For All Instructions in Block - Non-PHI Pass
1242
1243 // Check if each LRG is live out of this block so as not to propagate
1244 // beyond the last use of a LRG.
1245 for( slidx = 0; slidx < spill_cnt; slidx++ ) {
1246 uint defidx = lidxs.at(slidx);
1247 IndexSet *liveout = _live->live(b);
1248 if( !liveout->member(defidx) ) {
1249 #ifdef ASSERT
1250 // The index defidx is not live. Check the liveout array to ensure that
1251 // it contains no members which compress to defidx. Finding such an
1252 // instance may be a case to add liveout adjustment in compress_uf_map().
1319 if (def->rematerialize()) {
1320 // Place the rematerialized node above any MSCs created during
1321 // phi node splitting. end_idx points at the insertion point
1322 // so look at the node before it.
1323 int insert = pred->end_idx();
1324 while (insert >= 1 &&
1325 pred->get_node(insert - 1)->is_SpillCopy() &&
1326 _lrg_map.find(pred->get_node(insert - 1)) >= lrgs_before_phi_split) {
1327 insert--;
1328 }
1329 def = split_Rematerialize(def, pred, insert, maxlrg, splits, slidx, lrg2reach, Reachblock, false);
1330 if (!def) {
1331 return 0; // Bail out
1332 }
1333 }
1334 // Update the Phi's input edge array
1335 phi->set_req(i,def);
1336 // Grab the UP/DOWN sense for the input
1337 u1 = UP[pidx][slidx];
1338 if( u1 != (phi_up != 0)) {
1339 maxlrg = split_USE(MachSpillCopyNode::PhiLocationDifferToInputLocation, def, b, phi, i, maxlrg, !u1, false, splits,slidx);
1340 // If it wasn't split bail
1341 if (!maxlrg) {
1342 return 0;
1343 }
1344 }
1345 } // End for all inputs to the Phi
1346 } // End for all Phi Nodes
1347 // Update _maxlrg to save Union asserts
1348 _lrg_map.set_max_lrg_id(maxlrg);
1349
1350
1351 //----------PASS 3----------
1352 // Pass over all Phi's to union the live ranges
1353 for( insidx = 0; insidx < phis->size(); insidx++ ) {
1354 Node *phi = phis->at(insidx);
1355 assert(phi->is_Phi(),"This list must only contain Phi Nodes");
1356 // Walk all inputs to Phi and Union input live range with Phi live range
1357 for( uint i = 1; i < phi->req(); i++ ) {
1358 // Grab the input node
1359 Node *n = phi->in(i);
|