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