224 // were already unhooked by using information from detect_ptr_independence()
225 // and find_previous_store().
226
227 if (mem->is_MergeMem()) {
228 MergeMemNode* mmem = mem->as_MergeMem();
229 const TypePtr *tp = t_adr->is_ptr();
230
231 mem = step_through_mergemem(phase, mmem, tp, adr_type(), tty);
232 }
233
234 if (mem != old_mem) {
235 set_req(MemNode::Memory, mem);
236 return this;
237 }
238
239 // let the subclass continue analyzing...
240 return NULL;
241 }
242
243 // Helper function for proving some simple control dominations.
244 // Attempt to prove that control input 'dom' dominates (or equals) 'sub'.
245 // Already assumes that 'dom' is available at 'sub', and that 'sub'
246 // is not a constant (dominated by the method's StartNode).
247 // Used by MemNode::find_previous_store to prove that the
248 // control input of a memory operation predates (dominates)
249 // an allocation it wants to look past.
250 bool MemNode::detect_dominating_control(Node* dom, Node* sub) {
251 if (dom == NULL) return false;
252 if (dom->is_Proj()) dom = dom->in(0);
253 if (dom->is_Start()) return true; // anything inside the method
254 if (dom->is_Root()) return true; // dom 'controls' a constant
255 int cnt = 20; // detect cycle or too much effort
256 while (sub != NULL) { // walk 'sub' up the chain to 'dom'
257 if (--cnt < 0) return false; // in a cycle or too complex
258 if (sub == dom) return true;
259 if (sub->is_Start()) return false;
260 if (sub->is_Root()) return false;
261 Node* up = sub->in(0);
262 if (sub == up && sub->is_Region()) {
263 for (uint i = 1; i < sub->req(); i++) {
264 Node* in = sub->in(i);
265 if (in != NULL && !in->is_top() && in != sub) {
266 up = in; break; // take any path on the way up to 'dom'
267 }
268 }
269 }
270 if (sub == up) return false; // some kind of tight cycle
271 sub = up;
272 }
273 return false;
274 }
275
276 //---------------------detect_ptr_independence---------------------------------
277 // Used by MemNode::find_previous_store to prove that two base
278 // pointers are never equal.
279 // The pointers are accompanied by their associated allocations,
280 // if any, which have been previously discovered by the caller.
281 bool MemNode::detect_ptr_independence(Node* p1, AllocateNode* a1,
282 Node* p2, AllocateNode* a2,
283 PhaseTransform* phase) {
284 // Attempt to prove that these two pointers cannot be aliased.
285 // They may both manifestly be allocations, and they should differ.
286 // Or, if they are not both allocations, they can be distinct constants.
287 // Otherwise, one is an allocation and the other a pre-existing value.
288 if (a1 == NULL && a2 == NULL) { // neither an allocation
289 return (p1 != p2) && p1->is_Con() && p2->is_Con();
290 } else if (a1 != NULL && a2 != NULL) { // both allocations
291 return (a1 != a2);
292 } else if (a1 != NULL) { // one allocation a1
293 // (Note: p2->is_Con implies p2->in(0)->is_Root, which dominates.)
294 return detect_dominating_control(p2->in(0), a1->in(0));
295 } else { //(a2 != NULL) // one allocation a2
296 return detect_dominating_control(p1->in(0), a2->in(0));
297 }
298 return false;
299 }
300
301
302 // The logic for reordering loads and stores uses four steps:
303 // (a) Walk carefully past stores and initializations which we
304 // can prove are independent of this load.
305 // (b) Observe that the next memory state makes an exact match
306 // with self (load or store), and locate the relevant store.
307 // (c) Ensure that, if we were to wire self directly to the store,
308 // the optimizer would fold it up somehow.
309 // (d) Do the rewiring, and return, depending on some other part of
310 // the optimizer to fold up the load.
311 // This routine handles steps (a) and (b). Steps (c) and (d) are
312 // specific to loads and stores, so they are handled by the callers.
313 // (Currently, only LoadNode::Ideal has steps (c), (d). More later.)
314 //
315 Node* MemNode::find_previous_store(PhaseTransform* phase) {
316 Node* ctrl = in(MemNode::Control);
362 continue; // (a) advance through independent store memory
363 }
364
365 // (b) At this point, if the bases or offsets do not agree, we lose,
366 // since we have not managed to prove 'this' and 'mem' independent.
367 if (st_base == base && st_offset == offset) {
368 return mem; // let caller handle steps (c), (d)
369 }
370
371 } else if (mem->is_Proj() && mem->in(0)->is_Initialize()) {
372 InitializeNode* st_init = mem->in(0)->as_Initialize();
373 AllocateNode* st_alloc = st_init->allocation();
374 if (st_alloc == NULL)
375 break; // something degenerated
376 bool known_identical = false;
377 bool known_independent = false;
378 if (alloc == st_alloc)
379 known_identical = true;
380 else if (alloc != NULL)
381 known_independent = true;
382 else if (ctrl != NULL &&
383 detect_dominating_control(ctrl, st_alloc->in(0)))
384 known_independent = true;
385
386 if (known_independent) {
387 // The bases are provably independent: Either they are
388 // manifestly distinct allocations, or else the control
389 // of this load dominates the store's allocation.
390 int alias_idx = phase->C->get_alias_index(adr_type());
391 if (alias_idx == Compile::AliasIdxRaw) {
392 mem = st_alloc->in(TypeFunc::Memory);
393 } else {
394 mem = st_init->memory(alias_idx);
395 }
396 continue; // (a) advance through independent store memory
397 }
398
399 // (b) at this point, if we are not looking at a store initializing
400 // the same allocation we are loading from, we lose.
401 if (known_identical) {
402 // From caller, can_see_stored_value will consult find_captured_store.
403 return mem; // let caller handle steps (c), (d)
1051 Node* p = MemNode::Ideal_common(phase, can_reshape);
1052 if (p) return (p == NodeSentinel) ? NULL : p;
1053
1054 Node* ctrl = in(MemNode::Control);
1055 Node* address = in(MemNode::Address);
1056
1057 // Skip up past a SafePoint control. Cannot do this for Stores because
1058 // pointer stores & cardmarks must stay on the same side of a SafePoint.
1059 if( ctrl != NULL && ctrl->Opcode() == Op_SafePoint &&
1060 phase->C->get_alias_index(phase->type(address)->is_ptr()) != Compile::AliasIdxRaw ) {
1061 ctrl = ctrl->in(0);
1062 set_req(MemNode::Control,ctrl);
1063 }
1064
1065 // Check for useless control edge in some common special cases
1066 if (in(MemNode::Control) != NULL) {
1067 intptr_t ignore = 0;
1068 Node* base = AddPNode::Ideal_base_and_offset(address, phase, ignore);
1069 if (base != NULL
1070 && phase->type(base)->higher_equal(TypePtr::NOTNULL)
1071 && detect_dominating_control(base->in(0), phase->C->start())) {
1072 // A method-invariant, non-null address (constant or 'this' argument).
1073 set_req(MemNode::Control, NULL);
1074 }
1075 }
1076
1077 if (EliminateAutoBox && can_reshape && in(Address)->is_AddP()) {
1078 Node* base = in(Address)->in(AddPNode::Base);
1079 if (base != NULL) {
1080 Compile::AliasType* atp = phase->C->alias_type(adr_type());
1081 if (is_autobox_object(atp)) {
1082 Node* result = eliminate_autobox(phase);
1083 if (result != NULL) return result;
1084 }
1085 }
1086 }
1087
1088 Node* mem = in(MemNode::Memory);
1089 const TypePtr *addr_t = phase->type(address)->isa_ptr();
1090
1091 if (addr_t != NULL) {
2472 bool InitializeNode::detect_init_independence(Node* n,
2473 bool st_is_pinned,
2474 int& count) {
2475 if (n == NULL) return true; // (can this really happen?)
2476 if (n->is_Proj()) n = n->in(0);
2477 if (n == this) return false; // found a cycle
2478 if (n->is_Con()) return true;
2479 if (n->is_Start()) return true; // params, etc., are OK
2480 if (n->is_Root()) return true; // even better
2481
2482 Node* ctl = n->in(0);
2483 if (ctl != NULL && !ctl->is_top()) {
2484 if (ctl->is_Proj()) ctl = ctl->in(0);
2485 if (ctl == this) return false;
2486
2487 // If we already know that the enclosing memory op is pinned right after
2488 // the init, then any control flow that the store has picked up
2489 // must have preceded the init, or else be equal to the init.
2490 // Even after loop optimizations (which might change control edges)
2491 // a store is never pinned *before* the availability of its inputs.
2492 if (!MemNode::detect_dominating_control(ctl, this->in(0)))
2493 return false; // failed to prove a good control
2494
2495 }
2496
2497 // Check data edges for possible dependencies on 'this'.
2498 if ((count += 1) > 20) return false; // complexity limit
2499 for (uint i = 1; i < n->req(); i++) {
2500 Node* m = n->in(i);
2501 if (m == NULL || m == n || m->is_top()) continue;
2502 uint first_i = n->find_edge(m);
2503 if (i != first_i) continue; // process duplicate edge just once
2504 if (!detect_init_independence(m, st_is_pinned, count)) {
2505 return false;
2506 }
2507 }
2508
2509 return true;
2510 }
2511
2512 // Here are all the checks a Store must pass before it can be moved into
|
224 // were already unhooked by using information from detect_ptr_independence()
225 // and find_previous_store().
226
227 if (mem->is_MergeMem()) {
228 MergeMemNode* mmem = mem->as_MergeMem();
229 const TypePtr *tp = t_adr->is_ptr();
230
231 mem = step_through_mergemem(phase, mmem, tp, adr_type(), tty);
232 }
233
234 if (mem != old_mem) {
235 set_req(MemNode::Memory, mem);
236 return this;
237 }
238
239 // let the subclass continue analyzing...
240 return NULL;
241 }
242
243 // Helper function for proving some simple control dominations.
244 // Attempt to prove that all control inputs of 'dom' dominate 'sub'.
245 // Already assumes that 'dom' is available at 'sub', and that 'sub'
246 // is not a constant (dominated by the method's StartNode).
247 // Used by MemNode::find_previous_store to prove that the
248 // control input of a memory operation predates (dominates)
249 // an allocation it wants to look past.
250 bool MemNode::all_controls_dominate(Node* dom, Node* sub) {
251 if (dom == NULL || dom->is_top() || sub == NULL || sub->is_top())
252 return false; // Conservative answer for dead code
253
254 // Check 'dom'.
255 dom = dom->find_exact_control(dom);
256 if (dom == NULL || dom->is_top())
257 return false; // Conservative answer for dead code
258
259 if (dom->is_Start() || dom->is_Root() || dom == sub)
260 return true;
261
262 // 'dom' dominates 'sub' if its control edge and control edges
263 // of all its inputs dominate or equal to sub's control edge.
264
265 // Currently 'sub' is either Allocate, Initialize or Start nodes.
266 assert(sub->is_Allocate() || sub->is_Initialize() || sub->is_Start(), "expecting only these nodes");
267
268 // Get control edge of 'sub'.
269 sub = sub->find_exact_control(sub->in(0));
270 if (sub == NULL || sub->is_top())
271 return false; // Conservative answer for dead code
272
273 assert(sub->is_CFG(), "expecting control");
274
275 if (sub == dom)
276 return true;
277
278 if (sub->is_Start() || sub->is_Root())
279 return false;
280
281 {
282 // Check all control edges of 'dom'.
283
284 ResourceMark rm;
285 Arena* arena = Thread::current()->resource_area();
286 Node_List nlist(arena);
287 Unique_Node_List dom_list(arena);
288
289 dom_list.push(dom);
290 bool only_dominating_controls = false;
291
292 for (uint next = 0; next < dom_list.size(); next++) {
293 Node* n = dom_list.at(next);
294 if (!n->is_CFG() && n->pinned()) {
295 // Check only own control edge for pinned non-control nodes.
296 n = n->find_exact_control(n->in(0));
297 if (n == NULL || n->is_top())
298 return false; // Conservative answer for dead code
299 assert(n->is_CFG(), "expecting control");
300 }
301 if (n->is_Start() || n->is_Root()) {
302 only_dominating_controls = true;
303 } else if (n->is_CFG()) {
304 if (n->dominates(sub, nlist))
305 only_dominating_controls = true;
306 else
307 return false;
308 } else {
309 // First, own control edge.
310 Node* m = n->find_exact_control(n->in(0));
311 if (m == NULL)
312 continue;
313 if (m->is_top())
314 return false; // Conservative answer for dead code
315 dom_list.push(m);
316
317 // Now, the rest of edges.
318 uint cnt = n->req();
319 for (uint i = 1; i < cnt; i++) {
320 m = n->find_exact_control(n->in(i));
321 if (m == NULL || m->is_top())
322 continue;
323 dom_list.push(m);
324 }
325 }
326 }
327 return only_dominating_controls;
328 }
329 }
330
331 //---------------------detect_ptr_independence---------------------------------
332 // Used by MemNode::find_previous_store to prove that two base
333 // pointers are never equal.
334 // The pointers are accompanied by their associated allocations,
335 // if any, which have been previously discovered by the caller.
336 bool MemNode::detect_ptr_independence(Node* p1, AllocateNode* a1,
337 Node* p2, AllocateNode* a2,
338 PhaseTransform* phase) {
339 // Attempt to prove that these two pointers cannot be aliased.
340 // They may both manifestly be allocations, and they should differ.
341 // Or, if they are not both allocations, they can be distinct constants.
342 // Otherwise, one is an allocation and the other a pre-existing value.
343 if (a1 == NULL && a2 == NULL) { // neither an allocation
344 return (p1 != p2) && p1->is_Con() && p2->is_Con();
345 } else if (a1 != NULL && a2 != NULL) { // both allocations
346 return (a1 != a2);
347 } else if (a1 != NULL) { // one allocation a1
348 // (Note: p2->is_Con implies p2->in(0)->is_Root, which dominates.)
349 return all_controls_dominate(p2, a1);
350 } else { //(a2 != NULL) // one allocation a2
351 return all_controls_dominate(p1, a2);
352 }
353 return false;
354 }
355
356
357 // The logic for reordering loads and stores uses four steps:
358 // (a) Walk carefully past stores and initializations which we
359 // can prove are independent of this load.
360 // (b) Observe that the next memory state makes an exact match
361 // with self (load or store), and locate the relevant store.
362 // (c) Ensure that, if we were to wire self directly to the store,
363 // the optimizer would fold it up somehow.
364 // (d) Do the rewiring, and return, depending on some other part of
365 // the optimizer to fold up the load.
366 // This routine handles steps (a) and (b). Steps (c) and (d) are
367 // specific to loads and stores, so they are handled by the callers.
368 // (Currently, only LoadNode::Ideal has steps (c), (d). More later.)
369 //
370 Node* MemNode::find_previous_store(PhaseTransform* phase) {
371 Node* ctrl = in(MemNode::Control);
417 continue; // (a) advance through independent store memory
418 }
419
420 // (b) At this point, if the bases or offsets do not agree, we lose,
421 // since we have not managed to prove 'this' and 'mem' independent.
422 if (st_base == base && st_offset == offset) {
423 return mem; // let caller handle steps (c), (d)
424 }
425
426 } else if (mem->is_Proj() && mem->in(0)->is_Initialize()) {
427 InitializeNode* st_init = mem->in(0)->as_Initialize();
428 AllocateNode* st_alloc = st_init->allocation();
429 if (st_alloc == NULL)
430 break; // something degenerated
431 bool known_identical = false;
432 bool known_independent = false;
433 if (alloc == st_alloc)
434 known_identical = true;
435 else if (alloc != NULL)
436 known_independent = true;
437 else if (all_controls_dominate(this, st_alloc))
438 known_independent = true;
439
440 if (known_independent) {
441 // The bases are provably independent: Either they are
442 // manifestly distinct allocations, or else the control
443 // of this load dominates the store's allocation.
444 int alias_idx = phase->C->get_alias_index(adr_type());
445 if (alias_idx == Compile::AliasIdxRaw) {
446 mem = st_alloc->in(TypeFunc::Memory);
447 } else {
448 mem = st_init->memory(alias_idx);
449 }
450 continue; // (a) advance through independent store memory
451 }
452
453 // (b) at this point, if we are not looking at a store initializing
454 // the same allocation we are loading from, we lose.
455 if (known_identical) {
456 // From caller, can_see_stored_value will consult find_captured_store.
457 return mem; // let caller handle steps (c), (d)
1105 Node* p = MemNode::Ideal_common(phase, can_reshape);
1106 if (p) return (p == NodeSentinel) ? NULL : p;
1107
1108 Node* ctrl = in(MemNode::Control);
1109 Node* address = in(MemNode::Address);
1110
1111 // Skip up past a SafePoint control. Cannot do this for Stores because
1112 // pointer stores & cardmarks must stay on the same side of a SafePoint.
1113 if( ctrl != NULL && ctrl->Opcode() == Op_SafePoint &&
1114 phase->C->get_alias_index(phase->type(address)->is_ptr()) != Compile::AliasIdxRaw ) {
1115 ctrl = ctrl->in(0);
1116 set_req(MemNode::Control,ctrl);
1117 }
1118
1119 // Check for useless control edge in some common special cases
1120 if (in(MemNode::Control) != NULL) {
1121 intptr_t ignore = 0;
1122 Node* base = AddPNode::Ideal_base_and_offset(address, phase, ignore);
1123 if (base != NULL
1124 && phase->type(base)->higher_equal(TypePtr::NOTNULL)
1125 && all_controls_dominate(base, phase->C->start())) {
1126 // A method-invariant, non-null address (constant or 'this' argument).
1127 set_req(MemNode::Control, NULL);
1128 }
1129 }
1130
1131 if (EliminateAutoBox && can_reshape && in(Address)->is_AddP()) {
1132 Node* base = in(Address)->in(AddPNode::Base);
1133 if (base != NULL) {
1134 Compile::AliasType* atp = phase->C->alias_type(adr_type());
1135 if (is_autobox_object(atp)) {
1136 Node* result = eliminate_autobox(phase);
1137 if (result != NULL) return result;
1138 }
1139 }
1140 }
1141
1142 Node* mem = in(MemNode::Memory);
1143 const TypePtr *addr_t = phase->type(address)->isa_ptr();
1144
1145 if (addr_t != NULL) {
2526 bool InitializeNode::detect_init_independence(Node* n,
2527 bool st_is_pinned,
2528 int& count) {
2529 if (n == NULL) return true; // (can this really happen?)
2530 if (n->is_Proj()) n = n->in(0);
2531 if (n == this) return false; // found a cycle
2532 if (n->is_Con()) return true;
2533 if (n->is_Start()) return true; // params, etc., are OK
2534 if (n->is_Root()) return true; // even better
2535
2536 Node* ctl = n->in(0);
2537 if (ctl != NULL && !ctl->is_top()) {
2538 if (ctl->is_Proj()) ctl = ctl->in(0);
2539 if (ctl == this) return false;
2540
2541 // If we already know that the enclosing memory op is pinned right after
2542 // the init, then any control flow that the store has picked up
2543 // must have preceded the init, or else be equal to the init.
2544 // Even after loop optimizations (which might change control edges)
2545 // a store is never pinned *before* the availability of its inputs.
2546 if (!MemNode::all_controls_dominate(n, this))
2547 return false; // failed to prove a good control
2548
2549 }
2550
2551 // Check data edges for possible dependencies on 'this'.
2552 if ((count += 1) > 20) return false; // complexity limit
2553 for (uint i = 1; i < n->req(); i++) {
2554 Node* m = n->in(i);
2555 if (m == NULL || m == n || m->is_top()) continue;
2556 uint first_i = n->find_edge(m);
2557 if (i != first_i) continue; // process duplicate edge just once
2558 if (!detect_init_independence(m, st_is_pinned, count)) {
2559 return false;
2560 }
2561 }
2562
2563 return true;
2564 }
2565
2566 // Here are all the checks a Store must pass before it can be moved into
|