1 /*
2 * Copyright (c) 2015, Red Hat, Inc. and/or its affiliates.
3 *
4 * This code is free software; you can redistribute it and/or modify it
5 * under the terms of the GNU General Public License version 2 only, as
6 * published by the Free Software Foundation.
7 *
8 * This code is distributed in the hope that it will be useful, but WITHOUT
9 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
10 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
11 * version 2 for more details (a copy is included in the LICENSE file that
12 * accompanied this code).
13 *
14 * You should have received a copy of the GNU General Public License version
15 * 2 along with this work; if not, write to the Free Software Foundation,
16 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
17 *
18 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
19 * or visit www.oracle.com if you need additional information or have any
20 * questions.
21 *
22 */
23
24 #include "opto/callnode.hpp"
25 #include "opto/movenode.hpp"
26 #include "opto/phaseX.hpp"
27 #include "opto/shenandoahSupport.hpp"
28
29 Node* ShenandoahBarrierNode::skip_through_barrier(Node* n) {
30 if (n->is_ShenandoahBarrier()) {
31 return n->in(ValueIn);
32 } else {
33 return n;
34 }
35 }
36
37 bool ShenandoahBarrierNode::needs_barrier(PhaseTransform* phase, Node* orig, Node* n, Node* rb_mem) {
38 Unique_Node_List visited;
39 return needs_barrier_impl(phase, orig, n, rb_mem, visited);
40 }
41
42 bool ShenandoahBarrierNode::needs_barrier_impl(PhaseTransform* phase, Node* orig, Node* n, Node* rb_mem, Unique_Node_List &visited) {
43
44 if (visited.member(n)) {
45 return false; // Been there.
46 }
47 visited.push(n);
48
49 if (n->is_Allocate()) {
50 // tty->print_cr("killed barrier for newly allocated object");
51 return false;
52 }
53
54 if (n->is_CallJava()) {
55 return true;
56 }
57
58 const Type* type = phase->type(n);
59 if (type->higher_equal(TypePtr::NULL_PTR)) {
60 // tty->print_cr("killed barrier for NULL object");
61 return false;
62 }
63 if (type->isa_oopptr() && type->is_oopptr()->const_oop() != NULL) {
64 // tty->print_cr("killed barrier for constant object");
65 return false;
66 }
67
68 if (n->is_CheckCastPP() || n->is_ConstraintCast()) {
69 return needs_barrier_impl(phase, orig, n->in(1), rb_mem, visited);
70 }
71 if (n->is_Parm()) {
72 return true;
73 }
74 if (n->is_Proj()) {
75 return needs_barrier_impl(phase, orig, n->in(0), rb_mem, visited);
76 }
77 if (n->is_Phi()) {
78 bool need_barrier = false;
79 for (uint i = 1; i < n->req() && ! need_barrier; i++) {
80 Node* input = n->in(i);
81 if (input == NULL) {
82 need_barrier = true; // Phi not complete yet?
83 } else if (needs_barrier_impl(phase, orig, input, rb_mem, visited)) {
84 need_barrier = true;
85 }
86 }
87 return need_barrier;
88 }
89 if (n->is_CMove()) {
90 return needs_barrier_impl(phase, orig, n->in(CMoveNode::IfFalse), rb_mem, visited) ||
91 needs_barrier_impl(phase, orig, n->in(CMoveNode::IfTrue ), rb_mem, visited);
92 }
93 if (n->Opcode() == Op_CreateEx) {
94 return true;
95 }
96 if (n->Opcode() == Op_ShenandoahWriteBarrier) {
97 // tty->print_cr("skipped barrier for chained write barrier object");
98 return false;
99 }
100 if (n->Opcode() == Op_ShenandoahReadBarrier) {
101 if (rb_mem == n->in(Memory)) {
102 // tty->print_cr("Eliminated chained read barrier");
103 return false;
104 } else {
105 return true;
106 }
107 }
108
109 if (n->Opcode() == Op_LoadP) {
110 return true;
111 }
112 #ifdef ASSERT
113 tty->print("need barrier on?: "); n->dump();
114 #endif
115 return true;
116 }
117
118 bool ShenandoahReadBarrierNode::dominates_memory_rb_impl(PhaseTransform* phase,
119 Node* b1,
120 Node* b2,
121 Node* current,
122 Unique_Node_List &visited) {
123 if (current == NULL) {
124 return false; // Incomplete phi. Try again later.
125 } else if (visited.member(current)) {
126 // We have already seen it.
127 return true;
128 }
129 visited.push(current);
130
131 if (current == b1) {
132 return true;
133 } else if (current == phase->C->immutable_memory()) {
134 return false;
135 } else if (current->isa_Phi()) {
136 bool dominates = true;
137 for (uint i = 1; i < current->req() && dominates == true; i++) {
138 Node* in = current->in(i);
139 dominates = dominates && dominates_memory_rb_impl(phase, b1, b2, in, visited);
140 }
141 return dominates;
142 } else if (current->Opcode() == Op_ShenandoahWriteBarrier) {
143 const Type* in_type = current->bottom_type();
144 const Type* this_type = b2->bottom_type();
145 if (is_independent(in_type, this_type)) {
146 Node* in = current->in(Memory);
147 return dominates_memory_rb_impl(phase, b1, b2, in, visited);
148 } else {
149 return false;
150 }
151 } else if (current->Opcode() == Op_ShenandoahWBMemProj) {
152 Node* in = current->in(0);
153 return dominates_memory_rb_impl(phase, b1, b2, in, visited);
154 } else if (current->is_top()) {
155 return true; // Dead path
156 } else if (current->is_Proj()) {
157 return dominates_memory_rb_impl(phase, b1, b2, current->in(0), visited);
158 } else if (current->is_Call()) {
159 return false; // TODO: Maybe improve by looking at the call's memory effects?
160 } else if (current->is_MemBar()) {
161 return false; // TODO: Do we need to stop at *any* membar?
162 } else if (current->is_MergeMem()) {
163 // if (true) return false;
164 // tty->print_cr("current == mergemem: "); current->dump();
165 const TypePtr* adr_type = phase->type(b2)->is_ptr()->add_offset(-8);
166 uint alias_idx = phase->C->get_alias_index(adr_type);
167 Node* mem_in = current->as_MergeMem()->memory_at(alias_idx);
168 return dominates_memory_rb_impl(phase, b1, b2, current->in(TypeFunc::Memory), visited);
169 } else {
170 // tty->print_cr("what else can we see here:");
171 #ifdef ASSERT
172 current->dump();
173 #endif
174 ShouldNotReachHere();
175 return false;
176 }
177 }
178
179 bool ShenandoahReadBarrierNode::dominates_memory_rb(PhaseTransform* phase, Node* b1, Node* b2) {
180 Unique_Node_List visited;
181 return dominates_memory_rb_impl(phase, b1->in(Memory), b2, b2->in(Memory), visited);
182 }
183
184 bool ShenandoahReadBarrierNode::is_independent(const Type* in_type, const Type* this_type) const {
185 assert(in_type->isa_oopptr(), "expect oop ptr");
186 assert(this_type->isa_oopptr(), "expect oop ptr");
187 /*
188 if ((! in_type->isa_oopptr()) || (! this_type->isa_oopptr())) {
189 #ifdef ASSERT
190 tty->print_cr("not oopptr");
191 tty->print("in: "); in_type->dump(); tty->print_cr(" ");
192 tty->print("this: "); this_type->dump(); tty->print_cr(" ");
193 #endif
194 return false;
195 }
196 */
197
198 ciKlass* in_kls = in_type->is_oopptr()->klass();
199 ciKlass* this_kls = this_type->is_oopptr()->klass();
200 if ((!in_kls->is_subclass_of(this_kls)) &&
201 (!this_kls->is_subclass_of(in_kls))) {
202 #ifdef ASSERT
203 // tty->print_cr("independent: ");
204 // tty->print("in: "); in_kls->print(); tty->print_cr(" ");
205 // tty->print("this: "); this_kls->print(); tty->print_cr(" ");
206 #endif
207 return true;
208 }
209 #ifdef ASSERT
210 // tty->print_cr("possibly dependend?");
211 // tty->print("in: "); in_type->dump(); tty->print_cr(" ");
212 // tty->print("this: "); this_type->dump(); tty->print_cr(" ");
213 #endif
214 return false;
215 }
216
217 Node* ShenandoahReadBarrierNode::Ideal(PhaseGVN *phase, bool can_reshape) {
218
219 if (! can_reshape) {
220 return NULL;
221 }
222
223 if (in(Memory) == phase->C->immutable_memory()) return NULL;
224
225 // If memory input is a MergeMem, take the appropriate slice out of it.
226 Node* mem_in = in(Memory);
227 if (mem_in->isa_MergeMem()) {
228 const TypePtr* adr_type = bottom_type()->is_ptr()->add_offset(-8);
229 uint alias_idx = phase->C->get_alias_index(adr_type);
230 mem_in = mem_in->as_MergeMem()->memory_at(alias_idx);
231 set_req(Memory, mem_in);
232 return this;
233 }
234
235 Node* input = in(Memory);
236 if (input->Opcode() == Op_ShenandoahWBMemProj) {
237 input = input->in(0);
238 if (input->is_top()) return NULL; // Dead path.
239 assert(input->Opcode() == Op_ShenandoahWriteBarrier, "expect write barrier");
240 const Type* in_type = phase->type(input);
241 const Type* this_type = phase->type(this);
242 if (is_independent(in_type, this_type)) {
243 phase->igvn_rehash_node_delayed(input);
244 set_req(Memory, input->in(Memory));
245 return this;
246 }
247 }
248 return NULL;
249 }
250
251 bool ShenandoahBarrierNode::has_barrier_users(Node* n, Unique_Node_List &visited) {
252 if (visited.member(n)) {
253 return false;
254 }
255 visited.push(n);
256
257 bool has_users = false;
258 for (DUIterator_Fast jmax, j = n->fast_outs(jmax); j < jmax && ! has_users; j++) {
259 Node* o = n->fast_out(j);
260 if (o->Opcode() == Op_ShenandoahReadBarrier ||
261 o->Opcode() == Op_ShenandoahWriteBarrier) {
262 // tty->print("counting barrier"); o->dump();
263 has_users = true;
264 } else if (o->isa_Phi()) {
265 has_users = has_barrier_users(o, visited);
266 } else if (o->Opcode() == Op_MergeMem) {
267 // Not a user. ?
268 } else {
269 // tty->print_cr("unknown user"); o->dump();
270 ShouldNotReachHere();
271 }
272 }
273 return has_users;
274 }
275
276 Node* ShenandoahWriteBarrierNode::Ideal(PhaseGVN *phase, bool can_reshape) {
277
278 if (! can_reshape) return NULL;
279
280 if (in(Memory) == phase->C->immutable_memory()) return NULL;
281
282 Node* mem_in = in(Memory);
283 if (mem_in->isa_MergeMem()) {
284 const TypePtr* adr_type = bottom_type()->is_ptr()->add_offset(-8);
285 uint alias_idx = phase->C->get_alias_index(adr_type);
286 mem_in = mem_in->as_MergeMem()->memory_at(alias_idx);
287 set_req(Memory, mem_in);
288 return this;
289 }
290
291 Node* mem_proj = find_out_with(Op_ShenandoahWBMemProj);
292 if (mem_proj == NULL) {
293 // tty->print_cr("no mem proj: kill input mem"); dump();
294 set_req(Memory, phase->C->immutable_memory());
295 return this;
296 }
297
298 // if (true) return NULL;
299
300 Unique_Node_List visited;
301 if (! has_barrier_users(mem_proj, visited)) {
302 // tty->print_cr("no users of mem projection. kill input mem"); dump();
303 phase->igvn_rehash_node_delayed(in(Memory));
304 set_req(Memory, phase->C->immutable_memory());
305
306 // tty->print_cr("reshaped wb: ");
307 // dump();
308 return this;
309 }
310 // tty->print_cr("leave mem proj alone");
311 return NULL;
312 }
313 /*
314 bool ShenandoahBarrierNode::dominates_control_impl(PhaseTransform* phase,
315 Node* c1,
316 Node* c2,
317 Node* current,
318 Unique_Node_List & visited) {
319 if (current == NULL) {
320 return true;
321 } else if (visited.member(current)) {
322 return true;
323 }
324 visited.push(current);
325
326 current->dump();
327 ShouldNotReachHere();
328 }
329 */
330
331 bool ShenandoahBarrierNode::dominates_control(PhaseTransform* phase,
332 Node* c1,
333 Node* c2) {
334 if (c1 == c2) {
335 return true;
336 }
337 if (c1 == NULL) {
338 return true;
339 }
340 #ifdef ASSERT
341 tty->print("c1: "); c1->dump(2);
342 tty->print("c2: "); c2->dump(2);
343 #endif
344 ShouldNotReachHere();
345 return false;
346 }
347
348 bool ShenandoahBarrierNode::dominates_memory_impl(PhaseTransform* phase,
349 Node* b1,
350 Node* b2,
351 Node* current,
352 Unique_Node_List &visited) {
353 /*
354 tty->print_cr("phistack:");
355 for (int x = 0; x < phistack->length(); x++) {
356 tty->print("-->");
357 phistack->at(x)->dump();
358 }
359 */
360 if (current == NULL) {
361 return false;
362 } else if (visited.member(current)) {
363 // We have already seen it.
364 return true;
365 }
366
367 visited.push(current);
368
369 if (current == b1) {
370 // tty->print_cr("current == b1: "); current->dump();
371 return true;
372 } else if (current == b2) {
373 // tty->print_cr("current == b2: "); current->dump();
374 return false;
375 } else if (current == phase->C->immutable_memory()) {
376 // tty->print_cr("current == immutable_memory: "); current->dump();
377 return false;
378 } else if (current->isa_Phi()) {
379 // tty->print_cr("current == phi: "); current->dump();
380 bool dominates = true;
381 for (uint i = 1; i < current->req() && dominates == true; i++) {
382 Node* in = current->in(i);
383 dominates = dominates && dominates_memory_impl(phase, b1, b2, in, visited);
384 }
385 return dominates;
386 } else if (current->Opcode() == Op_ShenandoahWriteBarrier) {
387 // tty->print_cr("current == wb: "); current->dump();
388 // Follow through memory input.
389 Node* in = current->in(Memory);
390 return dominates_memory_impl(phase, b1, b2, in, visited);
391 } else if (current->Opcode() == Op_ShenandoahWBMemProj) {
392 // tty->print_cr("current == wb-memproj: "); current->dump();
393 // Follow through memory input.
394 Node* in = current->in(0);
395 return dominates_memory_impl(phase, b1, b2, in, visited);
396 } else if (current->is_top()) {
397 return true; // Dead path
398 } else if (current->is_Proj()) {
399 // tty->print_cr("current == proj: "); current->dump();
400 return dominates_memory_impl(phase, b1, b2, current->in(0), visited);
401 } else if (current->is_Call()) {
402 // tty->print_cr("current == call: "); current->dump();
403 return dominates_memory_impl(phase, b1, b2, current->in(TypeFunc::Memory), visited);
404 } else if (current->is_MemBar()) {
405 // tty->print_cr("current == membar: "); current->dump();
406 return dominates_memory_impl(phase, b1, b2, current->in(TypeFunc::Memory), visited);
407 } else if (current->is_MergeMem()) {
408 // tty->print_cr("current == mergemem: "); current->dump();
409 const TypePtr* adr_type = phase->type(b2)->is_ptr()->add_offset(-8);
410 uint alias_idx = phase->C->get_alias_index(adr_type);
411 Node* mem_in = current->as_MergeMem()->memory_at(alias_idx);
412 return dominates_memory_impl(phase, b1, b2, current->in(TypeFunc::Memory), visited);
413 } else {
414 // tty->print_cr("what else can we see here:");
415 #ifdef ASSERT
416 current->dump();
417 #endif
418 ShouldNotReachHere();
419 return false;
420 }
421 }
422
423 /**
424 * Determines if b1 dominates b2 through memory inputs. It returns true if:
425 * - b1 can be reached by following each branch in b2's memory input (through phis, etc)
426 * - or we get back to b2 (i.e. through a loop) without seeing b1
427 * In all other cases, (in particular, if we reach immutable_memory without having seen b1)
428 * we return false.
429 */
430 bool ShenandoahBarrierNode::dominates_memory(PhaseTransform* phase, Node* b1, Node* b2) {
431 Unique_Node_List visited;
432 return dominates_memory_impl(phase, b1->in(Memory), b2, b2->in(Memory), visited);
433 }
434
435 Node* ShenandoahBarrierNode::Identity_impl(PhaseTransform* phase) {
436 Node* n = in(ValueIn);
437
438 Node* rb_mem = Opcode() == Op_ShenandoahReadBarrier ? in(Memory) : NULL;
439 if (! needs_barrier(phase, this, n, rb_mem)) {
440 return n;
441 }
442
443 // tty->print_cr("find sibling for: "); dump(2);
444 // Try to find a write barrier sibling with identical inputs that we can fold into.
445 for (DUIterator i = n->outs(); n->has_out(i); i++) {
446 Node* sibling = n->out(i);
447 if (sibling == this) {
448 continue;
449 }
450 /*
451 assert(sibling->Opcode() != Op_ShenandoahWriteBarrier ||
452 Opcode() != Op_ShenandoahWriteBarrier || hash() == sibling->hash(),
453 "if this is a write barrier, then sibling can't be write barrier too");
454 */
455 if (sibling->Opcode() != Op_ShenandoahWriteBarrier) {
456 continue;
457 }
458 /*
459 if (sibling->outcnt() == 0) {
460 // Some dead node.
461 continue;
462 }
463 */
464 assert(sibling->in(ValueIn) == in(ValueIn), "sanity");
465 assert(sibling->Opcode() == Op_ShenandoahWriteBarrier, "sanity");
466 // tty->print_cr("candidate: "); sibling->dump();
467
468 if (dominates_control(phase, sibling->in(Control), in(Control)) &&
469 dominates_memory(phase, sibling, this)) {
470
471 /*
472 tty->print_cr("matched barrier:");
473 sibling->dump();
474 tty->print_cr("for: ");
475 dump();
476 */
477 return sibling;
478 }
479
480 /*
481 tty->print_cr("couldn't match candidate:");
482 sibling->dump(2);
483 */
484 }
485 /*
486 tty->print_cr("couldn't match barrier to any:");
487 dump();
488 */
489 return this;
490 }
491
492 Node* ShenandoahBarrierNode::Identity(PhaseTransform* phase) {
493
494 Node* replacement = Identity_impl(phase);
495 if (replacement != this) {
496 // If we have a memory projection, we first need to make it go away.
497 Node* mem_proj = find_out_with(Op_ShenandoahWBMemProj);
498 if (mem_proj != NULL) {
499 phase->igvn_rehash_node_delayed(mem_proj);
500 return this;
501 }
502 }
503 return replacement;
504 }
505
506 Node* ShenandoahReadBarrierNode::Identity(PhaseTransform* phase) {
507
508 // if (true) return this;
509
510 // tty->print("optimizing rb: "); dump();
511 Node* id = ShenandoahBarrierNode::Identity(phase);
512
513 if (id == this && phase->is_IterGVN()) {
514 Node* n = in(ValueIn);
515 // No success in super call. Try to combine identical read barriers.
516 for (DUIterator i = n->outs(); n->has_out(i); i++) {
517 Node* sibling = n->out(i);
518 if (sibling == this || sibling->Opcode() != Op_ShenandoahReadBarrier) {
519 continue;
520 }
521 assert(sibling->in(ValueIn) == in(ValueIn), "sanity");
522 if (phase->is_IterGVN()->hash_find(sibling) &&
523 sibling->bottom_type() == bottom_type() &&
524 sibling->in(Control) == in(Control) &&
525 dominates_memory_rb(phase, sibling, this)) {
526 /*
527 if (in(Memory) != sibling->in(Memory)) {
528 tty->print_cr("interesting rb-fold");
529 dump();
530 sibling->dump();
531 }
532 */
533 return sibling;
534 }
535 }
536 }
537 return id;
538 }
539
540 const Type* ShenandoahBarrierNode::Value(PhaseTransform* phase) const {
541 // Either input is TOP ==> the result is TOP
542 const Type *t1 = phase->type(in(Memory));
543 if (t1 == Type::TOP) return Type::TOP;
544 const Type *t2 = phase->type(in(ValueIn));
545 if( t2 == Type::TOP ) return Type::TOP;
546
547 Node* input = in(ValueIn);
548 const Type* type = phase->type(input);
549 return type;
550 }
551
552 #ifdef ASSERT
553 uint ShenandoahBarrierNode::num_mem_projs() {
554 uint num_mem_proj = 0;
555 for (DUIterator_Fast imax, i = fast_outs(imax); i < imax; i++) {
556 Node* use = fast_out(i);
557 if (use->Opcode() == Op_ShenandoahWBMemProj) {
558 num_mem_proj++;
559 }
560 }
561 return num_mem_proj;
562 }
563
564 void ShenandoahBarrierNode::check_invariants() {
565 // if (Opcode() == Op_ShenandoahWriteBarrier) {
566 // uint mem_projs = num_mem_projs();
567 // if (mem_projs > 1) {
568 // tty->print_cr("num_mem_proj: %u", mem_projs);
569 // dump(2);
570 // }
571 // assert(mem_projs <= 1, "exactly 1 memory projection");
572 // }
573 }
574 #endif
575
576 Node* ShenandoahWBMemProjNode::Identity(PhaseTransform* phase) {
577
578 Node* wb = in(0);
579 if (wb->is_top()) return phase->C->top(); // Dead path.
580
581 assert(wb->Opcode() == Op_ShenandoahWriteBarrier, "expect write barrier");
582 if (wb->as_ShenandoahBarrier()->Identity_impl(phase) != wb) {
583 // If the parent write barrier would go away, make this mem proj go away first.
584 // Poke parent to give it a chance to go away too.
585 phase->igvn_rehash_node_delayed(wb);
586 return wb->in(ShenandoahBarrierNode::Memory);
587 }
588
589 // We can't do the below unless the graph is fully constructed.
590 if (! phase->is_IterGVN()) {
591 return this;
592 }
593
594 // If the mem projection has no barrier users, it's not needed anymore.
595 Unique_Node_List visited;
596 if (! ShenandoahWriteBarrierNode::has_barrier_users(this, visited)) {
597 // tty->print_cr("mem proj has no users. kill"); dump();
598 phase->igvn_rehash_node_delayed(wb);
599 return wb->in(ShenandoahBarrierNode::Memory);
600 }
601
602 return this;
603 }