1 /*
2 * Copyright (c) 1999, 2021, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 *
23 */
24
25 #include "precompiled.hpp"
26 #include "c1/c1_IR.hpp"
27 #include "c1/c1_Instruction.hpp"
28 #include "c1/c1_InstructionPrinter.hpp"
29 #include "c1/c1_ValueStack.hpp"
30 #include "ci/ciFlatArrayKlass.hpp"
31 #include "ci/ciInlineKlass.hpp"
32 #include "ci/ciObjArrayKlass.hpp"
33 #include "ci/ciTypeArrayKlass.hpp"
34 #include "utilities/bitMap.inline.hpp"
35
36
37 // Implementation of Instruction
38
39
40 int Instruction::dominator_depth() {
41 int result = -1;
42 if (block()) {
43 result = block()->dominator_depth();
44 }
45 assert(result != -1 || this->as_Local(), "Only locals have dominator depth -1");
46 return result;
47 }
48
49 Instruction::Condition Instruction::mirror(Condition cond) {
50 switch (cond) {
51 case eql: return eql;
52 case neq: return neq;
53 case lss: return gtr;
54 case leq: return geq;
55 case gtr: return lss;
56 case geq: return leq;
57 case aeq: return beq;
58 case beq: return aeq;
59 }
60 ShouldNotReachHere();
61 return eql;
62 }
63
64
65 Instruction::Condition Instruction::negate(Condition cond) {
66 switch (cond) {
67 case eql: return neq;
68 case neq: return eql;
69 case lss: return geq;
70 case leq: return gtr;
71 case gtr: return leq;
72 case geq: return lss;
73 case aeq: assert(false, "Above equal cannot be negated");
74 case beq: assert(false, "Below equal cannot be negated");
75 }
76 ShouldNotReachHere();
77 return eql;
78 }
79
80 void Instruction::update_exception_state(ValueStack* state) {
81 if (state != NULL && (state->kind() == ValueStack::EmptyExceptionState || state->kind() == ValueStack::ExceptionState)) {
82 assert(state->kind() == ValueStack::EmptyExceptionState || Compilation::current()->env()->should_retain_local_variables(), "unexpected state kind");
83 _exception_state = state;
84 } else {
85 _exception_state = NULL;
86 }
87 }
88
89 // Prev without need to have BlockBegin
90 Instruction* Instruction::prev() {
91 Instruction* p = NULL;
92 Instruction* q = block();
93 while (q != this) {
94 assert(q != NULL, "this is not in the block's instruction list");
95 p = q; q = q->next();
96 }
97 return p;
98 }
99
100
101 void Instruction::state_values_do(ValueVisitor* f) {
102 if (state_before() != NULL) {
103 state_before()->values_do(f);
104 }
105 if (exception_state() != NULL){
106 exception_state()->values_do(f);
107 }
108 }
109
110 ciType* Instruction::exact_type() const {
111 ciType* t = declared_type();
112 if (t != NULL && t->is_klass()) {
113 return t->as_klass()->exact_klass();
114 }
115 return NULL;
116 }
117
118 ciKlass* Instruction::as_loaded_klass_or_null() const {
119 ciType* type = declared_type();
120 if (type != NULL && type->is_klass()) {
121 ciKlass* klass = type->as_klass();
122 if (klass->is_loaded()) {
123 return klass;
124 }
125 }
126 return NULL;
127 }
128
129 bool Instruction::is_loaded_flattened_array() const {
130 if (UseFlatArray) {
131 ciType* type = declared_type();
132 return type != NULL && type->is_flat_array_klass();
133 }
134 return false;
135 }
136
137 bool Instruction::maybe_flattened_array() {
138 if (UseFlatArray) {
139 ciType* type = declared_type();
140 if (type != NULL) {
141 if (type->is_obj_array_klass() && !type->as_obj_array_klass()->is_elem_null_free()) {
142 // The runtime type of [LMyValue might be [QMyValue due to [QMyValue <: [LMyValue.
143 ciKlass* element_klass = type->as_obj_array_klass()->element_klass();
144 if (element_klass->can_be_inline_klass() && (!element_klass->is_inlinetype() || element_klass->as_inline_klass()->flatten_array())) {
145 return true;
146 }
147 } else if (type->is_flat_array_klass()) {
148 return true;
149 } else if (type->is_klass() && type->as_klass()->is_java_lang_Object()) {
150 // This can happen as a parameter to System.arraycopy()
151 return true;
152 }
153 } else {
154 // Type info gets lost during Phi merging (Phi, IfOp, etc), but we might be storing into a
155 // flattened array, so we should do a runtime check.
156 return true;
157 }
158 }
159 return false;
160 }
161
162 bool Instruction::maybe_null_free_array() {
163 ciType* type = declared_type();
164 if (type != NULL) {
165 if (type->is_obj_array_klass()) {
166 // Due to array covariance, the runtime type might be a null-free array.
167 if (type->as_obj_array_klass()->can_be_inline_array_klass()) {
168 return true;
169 }
170 }
171 } else {
172 // Type info gets lost during Phi merging (Phi, IfOp, etc), but we might be storing into a
173 // null-free array, so we should do a runtime check.
174 return true;
175 }
176 return false;
177 }
178
179 #ifndef PRODUCT
180 void Instruction::check_state(ValueStack* state) {
181 if (state != NULL) {
182 state->verify();
183 }
184 }
185
186
187 void Instruction::print() {
188 InstructionPrinter ip;
189 print(ip);
190 }
191
192
193 void Instruction::print_line() {
194 InstructionPrinter ip;
195 ip.print_line(this);
196 }
197
198
199 void Instruction::print(InstructionPrinter& ip) {
200 ip.print_head();
201 ip.print_line(this);
202 tty->cr();
203 }
204 #endif // PRODUCT
205
206
207 // perform constant and interval tests on index value
208 bool AccessIndexed::compute_needs_range_check() {
209 if (length()) {
210 Constant* clength = length()->as_Constant();
211 Constant* cindex = index()->as_Constant();
212 if (clength && cindex) {
213 IntConstant* l = clength->type()->as_IntConstant();
214 IntConstant* i = cindex->type()->as_IntConstant();
215 if (l && i && i->value() < l->value() && i->value() >= 0) {
216 return false;
217 }
218 }
219 }
220
221 if (!this->check_flag(NeedsRangeCheckFlag)) {
222 return false;
223 }
224
225 return true;
226 }
227
228
229 ciType* Constant::exact_type() const {
230 if (type()->is_object() && type()->as_ObjectType()->is_loaded()) {
231 return type()->as_ObjectType()->exact_type();
232 }
233 return NULL;
234 }
235
236 ciType* LoadIndexed::exact_type() const {
237 ciType* array_type = array()->exact_type();
238 if (delayed() == NULL && array_type != NULL) {
239 assert(array_type->is_array_klass(), "what else?");
240 ciArrayKlass* ak = (ciArrayKlass*)array_type;
241
242 if (ak->element_type()->is_instance_klass()) {
243 ciInstanceKlass* ik = (ciInstanceKlass*)ak->element_type();
244 if (ik->is_loaded() && ik->is_final()) {
245 return ik;
246 }
247 }
248 }
249 return Instruction::exact_type();
250 }
251
252 ciType* LoadIndexed::declared_type() const {
253 if (delayed() != NULL) {
254 return delayed()->field()->type();
255 }
256 ciType* array_type = array()->declared_type();
257 if (array_type == NULL || !array_type->is_loaded()) {
258 return NULL;
259 }
260 assert(array_type->is_array_klass(), "what else?");
261 ciArrayKlass* ak = (ciArrayKlass*)array_type;
262 return ak->element_type();
263 }
264
265 bool StoreIndexed::is_exact_flattened_array_store() const {
266 if (array()->is_loaded_flattened_array() && value()->as_Constant() == NULL && value()->declared_type() != NULL) {
267 ciKlass* element_klass = array()->declared_type()->as_flat_array_klass()->element_klass();
268 ciKlass* actual_klass = value()->declared_type()->as_klass();
269
270 // The following check can fail with inlining:
271 // void test45_inline(Object[] oa, Object o, int index) { oa[index] = o; }
272 // void test45(MyValue1[] va, int index, MyValue2 v) { test45_inline(va, v, index); }
273 if (element_klass == actual_klass) {
274 return true;
275 }
276 }
277 return false;
278 }
279
280 ciType* LoadField::declared_type() const {
281 return field()->type();
282 }
283
284
285 ciType* NewTypeArray::exact_type() const {
286 return ciTypeArrayKlass::make(elt_type());
287 }
288
289 ciType* NewObjectArray::exact_type() const {
290 return ciArrayKlass::make(klass(), is_null_free());
291 }
292
293 ciType* NewMultiArray::exact_type() const {
294 return _klass;
295 }
296
297 ciType* NewArray::declared_type() const {
298 return exact_type();
299 }
300
301 ciType* NewInstance::exact_type() const {
302 return klass();
303 }
304
305 ciType* NewInstance::declared_type() const {
306 return exact_type();
307 }
308
309 ciType* NewInlineTypeInstance::exact_type() const {
310 return klass();
311 }
312
313 ciType* NewInlineTypeInstance::declared_type() const {
314 return exact_type();
315 }
316
317 ciType* CheckCast::declared_type() const {
318 return klass();
319 }
320
321 // Implementation of ArithmeticOp
322
323 bool ArithmeticOp::is_commutative() const {
324 switch (op()) {
325 case Bytecodes::_iadd: // fall through
326 case Bytecodes::_ladd: // fall through
327 case Bytecodes::_fadd: // fall through
328 case Bytecodes::_dadd: // fall through
329 case Bytecodes::_imul: // fall through
330 case Bytecodes::_lmul: // fall through
331 case Bytecodes::_fmul: // fall through
332 case Bytecodes::_dmul: return true;
333 default : return false;
334 }
335 }
336
337
338 bool ArithmeticOp::can_trap() const {
339 switch (op()) {
340 case Bytecodes::_idiv: // fall through
341 case Bytecodes::_ldiv: // fall through
342 case Bytecodes::_irem: // fall through
343 case Bytecodes::_lrem: return true;
344 default : return false;
345 }
346 }
347
348
349 // Implementation of LogicOp
350
351 bool LogicOp::is_commutative() const {
352 #ifdef ASSERT
353 switch (op()) {
354 case Bytecodes::_iand: // fall through
355 case Bytecodes::_land: // fall through
356 case Bytecodes::_ior : // fall through
357 case Bytecodes::_lor : // fall through
358 case Bytecodes::_ixor: // fall through
359 case Bytecodes::_lxor: break;
360 default : ShouldNotReachHere(); break;
361 }
362 #endif
363 // all LogicOps are commutative
364 return true;
365 }
366
367
368 // Implementation of IfOp
369
370 bool IfOp::is_commutative() const {
371 return cond() == eql || cond() == neq;
372 }
373
374
375 // Implementation of StateSplit
376
377 void StateSplit::substitute(BlockList& list, BlockBegin* old_block, BlockBegin* new_block) {
378 NOT_PRODUCT(bool assigned = false;)
379 for (int i = 0; i < list.length(); i++) {
380 BlockBegin** b = list.adr_at(i);
381 if (*b == old_block) {
382 *b = new_block;
383 NOT_PRODUCT(assigned = true;)
384 }
385 }
386 assert(assigned == true, "should have assigned at least once");
387 }
388
389
390 IRScope* StateSplit::scope() const {
391 return _state->scope();
392 }
393
394
395 void StateSplit::state_values_do(ValueVisitor* f) {
396 Instruction::state_values_do(f);
397 if (state() != NULL) state()->values_do(f);
398 }
399
400
401 void BlockBegin::state_values_do(ValueVisitor* f) {
402 StateSplit::state_values_do(f);
403
404 if (is_set(BlockBegin::exception_entry_flag)) {
405 for (int i = 0; i < number_of_exception_states(); i++) {
406 exception_state_at(i)->values_do(f);
407 }
408 }
409 }
410
411
412 StoreField::StoreField(Value obj, int offset, ciField* field, Value value, bool is_static,
413 ValueStack* state_before, bool needs_patching)
414 : AccessField(obj, offset, field, is_static, state_before, needs_patching)
415 , _value(value)
416 , _enclosing_field(NULL)
417 {
418 set_flag(NeedsWriteBarrierFlag, as_ValueType(field_type())->is_object());
419 #ifdef ASSERT
420 AssertValues assert_value;
421 values_do(&assert_value);
422 #endif
423 pin();
424 if (value->as_NewInlineTypeInstance() != NULL) {
425 value->as_NewInlineTypeInstance()->set_not_larva_anymore();
426 }
427 }
428
429 StoreIndexed::StoreIndexed(Value array, Value index, Value length, BasicType elt_type, Value value,
430 ValueStack* state_before, bool check_boolean, bool mismatched)
431 : AccessIndexed(array, index, length, elt_type, state_before, mismatched)
432 , _value(value), _check_boolean(check_boolean)
433 {
434 set_flag(NeedsWriteBarrierFlag, (as_ValueType(elt_type)->is_object()));
435 set_flag(NeedsStoreCheckFlag, (as_ValueType(elt_type)->is_object()));
436 #ifdef ASSERT
437 AssertValues assert_value;
438 values_do(&assert_value);
439 #endif
440 pin();
441 if (value->as_NewInlineTypeInstance() != NULL) {
442 value->as_NewInlineTypeInstance()->set_not_larva_anymore();
443 }
444 }
445
446
447 // Implementation of Invoke
448
449
450 Invoke::Invoke(Bytecodes::Code code, ValueType* result_type, Value recv, Values* args,
451 ciMethod* target, ValueStack* state_before, bool null_free)
452 : StateSplit(result_type, state_before)
453 , _code(code)
454 , _recv(recv)
455 , _args(args)
456 , _target(target)
457 {
458 set_flag(TargetIsLoadedFlag, target->is_loaded());
459 set_flag(TargetIsFinalFlag, target_is_loaded() && target->is_final_method());
460 set_null_free(null_free);
461
462 assert(args != NULL, "args must exist");
463 #ifdef ASSERT
464 AssertValues assert_value;
465 values_do(&assert_value);
466 #endif
467
468 // provide an initial guess of signature size.
469 _signature = new BasicTypeList(number_of_arguments() + (has_receiver() ? 1 : 0));
470 if (has_receiver()) {
471 _signature->append(as_BasicType(receiver()->type()));
472 if (receiver()->as_NewInlineTypeInstance() != NULL) {
473 receiver()->as_NewInlineTypeInstance()->set_not_larva_anymore();
474 }
475 }
476 for (int i = 0; i < number_of_arguments(); i++) {
477 Value v = argument_at(i);
478 ValueType* t = v->type();
479 BasicType bt = as_BasicType(t);
480 _signature->append(bt);
481 if (v->as_NewInlineTypeInstance() != NULL) {
482 v->as_NewInlineTypeInstance()->set_not_larva_anymore();
483 }
484 }
485 }
486
487
488 void Invoke::state_values_do(ValueVisitor* f) {
489 StateSplit::state_values_do(f);
490 if (state_before() != NULL) state_before()->values_do(f);
491 if (state() != NULL) state()->values_do(f);
492 }
493
494 ciType* Invoke::declared_type() const {
495 ciSignature* declared_signature = state()->scope()->method()->get_declared_signature_at_bci(state()->bci());
496 ciType *t = declared_signature->return_type();
497 assert(t->basic_type() != T_VOID, "need return value of void method?");
498 return t;
499 }
500
501 // Implementation of Contant
502 intx Constant::hash() const {
503 if (state_before() == NULL) {
504 switch (type()->tag()) {
505 case intTag:
506 return HASH2(name(), type()->as_IntConstant()->value());
507 case addressTag:
508 return HASH2(name(), type()->as_AddressConstant()->value());
509 case longTag:
510 {
511 jlong temp = type()->as_LongConstant()->value();
512 return HASH3(name(), high(temp), low(temp));
513 }
514 case floatTag:
515 return HASH2(name(), jint_cast(type()->as_FloatConstant()->value()));
516 case doubleTag:
517 {
518 jlong temp = jlong_cast(type()->as_DoubleConstant()->value());
519 return HASH3(name(), high(temp), low(temp));
520 }
521 case objectTag:
522 assert(type()->as_ObjectType()->is_loaded(), "can't handle unloaded values");
523 return HASH2(name(), type()->as_ObjectType()->constant_value());
524 case metaDataTag:
525 assert(type()->as_MetadataType()->is_loaded(), "can't handle unloaded values");
526 return HASH2(name(), type()->as_MetadataType()->constant_value());
527 default:
528 ShouldNotReachHere();
529 }
530 }
531 return 0;
532 }
533
534 bool Constant::is_equal(Value v) const {
535 if (v->as_Constant() == NULL) return false;
536
537 switch (type()->tag()) {
538 case intTag:
539 {
540 IntConstant* t1 = type()->as_IntConstant();
541 IntConstant* t2 = v->type()->as_IntConstant();
542 return (t1 != NULL && t2 != NULL &&
543 t1->value() == t2->value());
544 }
545 case longTag:
546 {
547 LongConstant* t1 = type()->as_LongConstant();
548 LongConstant* t2 = v->type()->as_LongConstant();
549 return (t1 != NULL && t2 != NULL &&
550 t1->value() == t2->value());
551 }
552 case floatTag:
553 {
554 FloatConstant* t1 = type()->as_FloatConstant();
555 FloatConstant* t2 = v->type()->as_FloatConstant();
556 return (t1 != NULL && t2 != NULL &&
557 jint_cast(t1->value()) == jint_cast(t2->value()));
558 }
559 case doubleTag:
560 {
561 DoubleConstant* t1 = type()->as_DoubleConstant();
562 DoubleConstant* t2 = v->type()->as_DoubleConstant();
563 return (t1 != NULL && t2 != NULL &&
564 jlong_cast(t1->value()) == jlong_cast(t2->value()));
565 }
566 case objectTag:
567 {
568 ObjectType* t1 = type()->as_ObjectType();
569 ObjectType* t2 = v->type()->as_ObjectType();
570 return (t1 != NULL && t2 != NULL &&
571 t1->is_loaded() && t2->is_loaded() &&
572 t1->constant_value() == t2->constant_value());
573 }
574 case metaDataTag:
575 {
576 MetadataType* t1 = type()->as_MetadataType();
577 MetadataType* t2 = v->type()->as_MetadataType();
578 return (t1 != NULL && t2 != NULL &&
579 t1->is_loaded() && t2->is_loaded() &&
580 t1->constant_value() == t2->constant_value());
581 }
582 default:
583 return false;
584 }
585 }
586
587 Constant::CompareResult Constant::compare(Instruction::Condition cond, Value right) const {
588 Constant* rc = right->as_Constant();
589 // other is not a constant
590 if (rc == NULL) return not_comparable;
591
592 ValueType* lt = type();
593 ValueType* rt = rc->type();
594 // different types
595 if (lt->base() != rt->base()) return not_comparable;
596 switch (lt->tag()) {
597 case intTag: {
598 int x = lt->as_IntConstant()->value();
599 int y = rt->as_IntConstant()->value();
600 switch (cond) {
601 case If::eql: return x == y ? cond_true : cond_false;
602 case If::neq: return x != y ? cond_true : cond_false;
603 case If::lss: return x < y ? cond_true : cond_false;
604 case If::leq: return x <= y ? cond_true : cond_false;
605 case If::gtr: return x > y ? cond_true : cond_false;
606 case If::geq: return x >= y ? cond_true : cond_false;
607 default : break;
608 }
609 break;
610 }
611 case longTag: {
612 jlong x = lt->as_LongConstant()->value();
613 jlong y = rt->as_LongConstant()->value();
614 switch (cond) {
615 case If::eql: return x == y ? cond_true : cond_false;
616 case If::neq: return x != y ? cond_true : cond_false;
617 case If::lss: return x < y ? cond_true : cond_false;
618 case If::leq: return x <= y ? cond_true : cond_false;
619 case If::gtr: return x > y ? cond_true : cond_false;
620 case If::geq: return x >= y ? cond_true : cond_false;
621 default : break;
622 }
623 break;
624 }
625 case objectTag: {
626 ciObject* xvalue = lt->as_ObjectType()->constant_value();
627 ciObject* yvalue = rt->as_ObjectType()->constant_value();
628 assert(xvalue != NULL && yvalue != NULL, "not constants");
629 if (xvalue->is_loaded() && yvalue->is_loaded()) {
630 switch (cond) {
631 case If::eql: return xvalue == yvalue ? cond_true : cond_false;
632 case If::neq: return xvalue != yvalue ? cond_true : cond_false;
633 default : break;
634 }
635 }
636 break;
637 }
638 case metaDataTag: {
639 ciMetadata* xvalue = lt->as_MetadataType()->constant_value();
640 ciMetadata* yvalue = rt->as_MetadataType()->constant_value();
641 assert(xvalue != NULL && yvalue != NULL, "not constants");
642 if (xvalue->is_loaded() && yvalue->is_loaded()) {
643 switch (cond) {
644 case If::eql: return xvalue == yvalue ? cond_true : cond_false;
645 case If::neq: return xvalue != yvalue ? cond_true : cond_false;
646 default : break;
647 }
648 }
649 break;
650 }
651 default:
652 break;
653 }
654 return not_comparable;
655 }
656
657
658 // Implementation of BlockBegin
659
660 void BlockBegin::set_end(BlockEnd* new_end) { // Assumes that no predecessor of new_end still has it as its successor
661 assert(new_end != NULL, "Should not reset block new_end to NULL");
662 if (new_end == _end) return;
663
664 // Remove this block as predecessor of its current successors
665 if (_end != NULL) {
666 for (int i = 0; i < number_of_sux(); i++) {
667 sux_at(i)->remove_predecessor(this);
668 }
669 }
670
671 _end = new_end;
672
673 // Add this block as predecessor of its new successors
674 for (int i = 0; i < number_of_sux(); i++) {
675 sux_at(i)->add_predecessor(this);
676 }
677 }
678
679
680 void BlockBegin::disconnect_edge(BlockBegin* from, BlockBegin* to) {
681 // disconnect any edges between from and to
682 #ifndef PRODUCT
683 if (PrintIR && Verbose) {
684 tty->print_cr("Disconnected edge B%d -> B%d", from->block_id(), to->block_id());
685 }
686 #endif
687 for (int s = 0; s < from->number_of_sux();) {
688 BlockBegin* sux = from->sux_at(s);
689 if (sux == to) {
690 int index = sux->_predecessors.find(from);
691 if (index >= 0) {
692 sux->_predecessors.remove_at(index);
693 }
694 from->end()->remove_sux_at(s);
695 } else {
696 s++;
697 }
698 }
699 }
700
701
702 void BlockBegin::substitute_sux(BlockBegin* old_sux, BlockBegin* new_sux) {
703 // modify predecessors before substituting successors
704 for (int i = 0; i < number_of_sux(); i++) {
705 if (sux_at(i) == old_sux) {
706 // remove old predecessor before adding new predecessor
707 // otherwise there is a dead predecessor in the list
708 new_sux->remove_predecessor(old_sux);
709 new_sux->add_predecessor(this);
710 }
711 }
712 old_sux->remove_predecessor(this);
713 end()->substitute_sux(old_sux, new_sux);
714 }
715
716
717
718 // In general it is not possible to calculate a value for the field "depth_first_number"
719 // of the inserted block, without recomputing the values of the other blocks
720 // in the CFG. Therefore the value of "depth_first_number" in BlockBegin becomes meaningless.
721 BlockBegin* BlockBegin::insert_block_between(BlockBegin* sux) {
722 int bci = sux->bci();
723 // critical edge splitting may introduce a goto after a if and array
724 // bound check elimination may insert a predicate between the if and
725 // goto. The bci of the goto can't be the one of the if otherwise
726 // the state and bci are inconsistent and a deoptimization triggered
727 // by the predicate would lead to incorrect execution/a crash.
728 BlockBegin* new_sux = new BlockBegin(bci);
729
730 // mark this block (special treatment when block order is computed)
731 new_sux->set(critical_edge_split_flag);
732
733 // This goto is not a safepoint.
734 Goto* e = new Goto(sux, false);
735 new_sux->set_next(e, bci);
736 new_sux->set_end(e);
737 // setup states
738 ValueStack* s = end()->state();
739 new_sux->set_state(s->copy(s->kind(), bci));
740 e->set_state(s->copy(s->kind(), bci));
741 assert(new_sux->state()->locals_size() == s->locals_size(), "local size mismatch!");
742 assert(new_sux->state()->stack_size() == s->stack_size(), "stack size mismatch!");
743 assert(new_sux->state()->locks_size() == s->locks_size(), "locks size mismatch!");
744
745 // link predecessor to new block
746 end()->substitute_sux(sux, new_sux);
747
748 // The ordering needs to be the same, so remove the link that the
749 // set_end call above added and substitute the new_sux for this
750 // block.
751 sux->remove_predecessor(new_sux);
752
753 // the successor could be the target of a switch so it might have
754 // multiple copies of this predecessor, so substitute the new_sux
755 // for the first and delete the rest.
756 bool assigned = false;
757 BlockList& list = sux->_predecessors;
758 for (int i = 0; i < list.length(); i++) {
759 BlockBegin** b = list.adr_at(i);
760 if (*b == this) {
761 if (assigned) {
762 list.remove_at(i);
763 // reprocess this index
764 i--;
765 } else {
766 assigned = true;
767 *b = new_sux;
768 }
769 // link the new block back to it's predecessors.
770 new_sux->add_predecessor(this);
771 }
772 }
773 assert(assigned == true, "should have assigned at least once");
774 return new_sux;
775 }
776
777
778 void BlockBegin::add_predecessor(BlockBegin* pred) {
779 _predecessors.append(pred);
780 }
781
782
783 void BlockBegin::remove_predecessor(BlockBegin* pred) {
784 int idx;
785 while ((idx = _predecessors.find(pred)) >= 0) {
786 _predecessors.remove_at(idx);
787 }
788 }
789
790
791 void BlockBegin::add_exception_handler(BlockBegin* b) {
792 assert(b != NULL && (b->is_set(exception_entry_flag)), "exception handler must exist");
793 // add only if not in the list already
794 if (!_exception_handlers.contains(b)) _exception_handlers.append(b);
795 }
796
797 int BlockBegin::add_exception_state(ValueStack* state) {
798 assert(is_set(exception_entry_flag), "only for xhandlers");
799 if (_exception_states == NULL) {
800 _exception_states = new ValueStackStack(4);
801 }
802 _exception_states->append(state);
803 return _exception_states->length() - 1;
804 }
805
806
807 void BlockBegin::iterate_preorder(boolArray& mark, BlockClosure* closure) {
808 if (!mark.at(block_id())) {
809 mark.at_put(block_id(), true);
810 closure->block_do(this);
811 BlockEnd* e = end(); // must do this after block_do because block_do may change it!
812 { for (int i = number_of_exception_handlers() - 1; i >= 0; i--) exception_handler_at(i)->iterate_preorder(mark, closure); }
813 { for (int i = e->number_of_sux () - 1; i >= 0; i--) e->sux_at (i)->iterate_preorder(mark, closure); }
814 }
815 }
816
817
818 void BlockBegin::iterate_postorder(boolArray& mark, BlockClosure* closure) {
819 if (!mark.at(block_id())) {
820 mark.at_put(block_id(), true);
821 BlockEnd* e = end();
822 { for (int i = number_of_exception_handlers() - 1; i >= 0; i--) exception_handler_at(i)->iterate_postorder(mark, closure); }
823 { for (int i = e->number_of_sux () - 1; i >= 0; i--) e->sux_at (i)->iterate_postorder(mark, closure); }
824 closure->block_do(this);
825 }
826 }
827
828
829 void BlockBegin::iterate_preorder(BlockClosure* closure) {
830 int mark_len = number_of_blocks();
831 boolArray mark(mark_len, mark_len, false);
832 iterate_preorder(mark, closure);
833 }
834
835
836 void BlockBegin::iterate_postorder(BlockClosure* closure) {
837 int mark_len = number_of_blocks();
838 boolArray mark(mark_len, mark_len, false);
839 iterate_postorder(mark, closure);
840 }
841
842
843 void BlockBegin::block_values_do(ValueVisitor* f) {
844 for (Instruction* n = this; n != NULL; n = n->next()) n->values_do(f);
845 }
846
847
848 #ifndef PRODUCT
849 #define TRACE_PHI(code) if (PrintPhiFunctions) { code; }
850 #else
851 #define TRACE_PHI(coce)
852 #endif
853
854
855 bool BlockBegin::try_merge(ValueStack* new_state, bool has_irreducible_loops) {
856 TRACE_PHI(tty->print_cr("********** try_merge for block B%d", block_id()));
857
858 // local variables used for state iteration
859 int index;
860 Value new_value, existing_value;
861
862 ValueStack* existing_state = state();
863 if (existing_state == NULL) {
864 TRACE_PHI(tty->print_cr("first call of try_merge for this block"));
865
866 if (is_set(BlockBegin::was_visited_flag)) {
867 // this actually happens for complicated jsr/ret structures
868 return false; // BAILOUT in caller
869 }
870
871 // copy state because it is altered
872 new_state = new_state->copy(ValueStack::BlockBeginState, bci());
873
874 // Use method liveness to invalidate dead locals
875 MethodLivenessResult liveness = new_state->scope()->method()->liveness_at_bci(bci());
876 if (liveness.is_valid()) {
877 assert((int)liveness.size() == new_state->locals_size(), "error in use of liveness");
878
879 for_each_local_value(new_state, index, new_value) {
880 if (!liveness.at(index) || new_value->type()->is_illegal()) {
881 new_state->invalidate_local(index);
882 TRACE_PHI(tty->print_cr("invalidating dead local %d", index));
883 }
884 }
885 }
886
887 if (is_set(BlockBegin::parser_loop_header_flag)) {
888 TRACE_PHI(tty->print_cr("loop header block, initializing phi functions"));
889
890 for_each_stack_value(new_state, index, new_value) {
891 new_state->setup_phi_for_stack(this, index);
892 TRACE_PHI(tty->print_cr("creating phi-function %c%d for stack %d", new_state->stack_at(index)->type()->tchar(), new_state->stack_at(index)->id(), index));
893 }
894
895 BitMap& requires_phi_function = new_state->scope()->requires_phi_function();
896 for_each_local_value(new_state, index, new_value) {
897 bool requires_phi = requires_phi_function.at(index) || (new_value->type()->is_double_word() && requires_phi_function.at(index + 1));
898 if (requires_phi || !SelectivePhiFunctions || has_irreducible_loops) {
899 new_state->setup_phi_for_local(this, index);
900 TRACE_PHI(tty->print_cr("creating phi-function %c%d for local %d", new_state->local_at(index)->type()->tchar(), new_state->local_at(index)->id(), index));
901 }
902 }
903 }
904
905 // initialize state of block
906 set_state(new_state);
907
908 } else if (existing_state->is_same(new_state)) {
909 TRACE_PHI(tty->print_cr("exisiting state found"));
910
911 assert(existing_state->scope() == new_state->scope(), "not matching");
912 assert(existing_state->locals_size() == new_state->locals_size(), "not matching");
913 assert(existing_state->stack_size() == new_state->stack_size(), "not matching");
914
915 if (is_set(BlockBegin::was_visited_flag)) {
916 TRACE_PHI(tty->print_cr("loop header block, phis must be present"));
917
918 if (!is_set(BlockBegin::parser_loop_header_flag)) {
919 // this actually happens for complicated jsr/ret structures
920 return false; // BAILOUT in caller
921 }
922
923 for_each_local_value(existing_state, index, existing_value) {
924 Value new_value = new_state->local_at(index);
925 if (new_value == NULL || new_value->type()->tag() != existing_value->type()->tag()) {
926 Phi* existing_phi = existing_value->as_Phi();
927 if (existing_phi == NULL) {
928 return false; // BAILOUT in caller
929 }
930 // Invalidate the phi function here. This case is very rare except for
931 // JVMTI capability "can_access_local_variables".
932 // In really rare cases we will bail out in LIRGenerator::move_to_phi.
933 existing_phi->make_illegal();
934 existing_state->invalidate_local(index);
935 TRACE_PHI(tty->print_cr("invalidating local %d because of type mismatch", index));
936 }
937
938 if (existing_value != new_state->local_at(index) && existing_value->as_Phi() == NULL) {
939 TRACE_PHI(tty->print_cr("required phi for local %d is missing, irreducible loop?", index));
940 return false; // BAILOUT in caller
941 }
942 }
943
944 #ifdef ASSERT
945 // check that all necessary phi functions are present
946 for_each_stack_value(existing_state, index, existing_value) {
947 assert(existing_value->as_Phi() != NULL && existing_value->as_Phi()->block() == this, "phi function required");
948 }
949 for_each_local_value(existing_state, index, existing_value) {
950 assert(existing_value == new_state->local_at(index) || (existing_value->as_Phi() != NULL && existing_value->as_Phi()->as_Phi()->block() == this), "phi function required");
951 }
952 #endif
953
954 } else {
955 TRACE_PHI(tty->print_cr("creating phi functions on demand"));
956
957 // create necessary phi functions for stack
958 for_each_stack_value(existing_state, index, existing_value) {
959 Value new_value = new_state->stack_at(index);
960 Phi* existing_phi = existing_value->as_Phi();
961
962 if (new_value != existing_value && (existing_phi == NULL || existing_phi->block() != this)) {
963 existing_state->setup_phi_for_stack(this, index);
964 TRACE_PHI(tty->print_cr("creating phi-function %c%d for stack %d", existing_state->stack_at(index)->type()->tchar(), existing_state->stack_at(index)->id(), index));
965 if (new_value->as_NewInlineTypeInstance() != NULL) {new_value->as_NewInlineTypeInstance()->set_not_larva_anymore(); }
966 if (existing_value->as_NewInlineTypeInstance() != NULL) {existing_value->as_NewInlineTypeInstance()->set_not_larva_anymore(); }
967 }
968 }
969
970 // create necessary phi functions for locals
971 for_each_local_value(existing_state, index, existing_value) {
972 Value new_value = new_state->local_at(index);
973 Phi* existing_phi = existing_value->as_Phi();
974
975 if (new_value == NULL || new_value->type()->tag() != existing_value->type()->tag()) {
976 existing_state->invalidate_local(index);
977 TRACE_PHI(tty->print_cr("invalidating local %d because of type mismatch", index));
978 } else if (new_value != existing_value && (existing_phi == NULL || existing_phi->block() != this)) {
979 existing_state->setup_phi_for_local(this, index);
980 TRACE_PHI(tty->print_cr("creating phi-function %c%d for local %d", existing_state->local_at(index)->type()->tchar(), existing_state->local_at(index)->id(), index));
981 if (new_value->as_NewInlineTypeInstance() != NULL) {new_value->as_NewInlineTypeInstance()->set_not_larva_anymore(); }
982 if (existing_value->as_NewInlineTypeInstance() != NULL) {existing_value->as_NewInlineTypeInstance()->set_not_larva_anymore(); }
983 }
984 }
985 }
986
987 assert(existing_state->caller_state() == new_state->caller_state(), "caller states must be equal");
988
989 } else {
990 assert(false, "stack or locks not matching (invalid bytecodes)");
991 return false;
992 }
993
994 TRACE_PHI(tty->print_cr("********** try_merge for block B%d successful", block_id()));
995
996 return true;
997 }
998
999
1000 #ifndef PRODUCT
1001 void BlockBegin::print_block() {
1002 InstructionPrinter ip;
1003 print_block(ip, false);
1004 }
1005
1006
1007 void BlockBegin::print_block(InstructionPrinter& ip, bool live_only) {
1008 ip.print_instr(this); tty->cr();
1009 ip.print_stack(this->state()); tty->cr();
1010 ip.print_inline_level(this);
1011 ip.print_head();
1012 for (Instruction* n = next(); n != NULL; n = n->next()) {
1013 if (!live_only || n->is_pinned() || n->use_count() > 0) {
1014 ip.print_line(n);
1015 }
1016 }
1017 tty->cr();
1018 }
1019 #endif // PRODUCT
1020
1021
1022 // Implementation of BlockList
1023
1024 void BlockList::iterate_forward (BlockClosure* closure) {
1025 const int l = length();
1026 for (int i = 0; i < l; i++) closure->block_do(at(i));
1027 }
1028
1029
1030 void BlockList::iterate_backward(BlockClosure* closure) {
1031 for (int i = length() - 1; i >= 0; i--) closure->block_do(at(i));
1032 }
1033
1034
1035 void BlockList::values_do(ValueVisitor* f) {
1036 for (int i = length() - 1; i >= 0; i--) at(i)->block_values_do(f);
1037 }
1038
1039
1040 #ifndef PRODUCT
1041 void BlockList::print(bool cfg_only, bool live_only) {
1042 InstructionPrinter ip;
1043 for (int i = 0; i < length(); i++) {
1044 BlockBegin* block = at(i);
1045 if (cfg_only) {
1046 ip.print_instr(block); tty->cr();
1047 } else {
1048 block->print_block(ip, live_only);
1049 }
1050 }
1051 }
1052 #endif // PRODUCT
1053
1054
1055 // Implementation of BlockEnd
1056
1057 void BlockEnd::substitute_sux(BlockBegin* old_sux, BlockBegin* new_sux) {
1058 substitute(*_sux, old_sux, new_sux);
1059 }
1060
1061 // Implementation of Phi
1062
1063 // Normal phi functions take their operands from the last instruction of the
1064 // predecessor. Special handling is needed for xhanlder entries because there
1065 // the state of arbitrary instructions are needed.
1066
1067 Value Phi::operand_at(int i) const {
1068 ValueStack* state;
1069 if (_block->is_set(BlockBegin::exception_entry_flag)) {
1070 state = _block->exception_state_at(i);
1071 } else {
1072 state = _block->pred_at(i)->end()->state();
1073 }
1074 assert(state != NULL, "");
1075
1076 if (is_local()) {
1077 return state->local_at(local_index());
1078 } else {
1079 return state->stack_at(stack_index());
1080 }
1081 }
1082
1083
1084 int Phi::operand_count() const {
1085 if (_block->is_set(BlockBegin::exception_entry_flag)) {
1086 return _block->number_of_exception_states();
1087 } else {
1088 return _block->number_of_preds();
1089 }
1090 }
1091
1092 #ifdef ASSERT
1093 // Constructor of Assert
1094 Assert::Assert(Value x, Condition cond, bool unordered_is_true, Value y) : Instruction(illegalType)
1095 , _x(x)
1096 , _cond(cond)
1097 , _y(y)
1098 {
1099 set_flag(UnorderedIsTrueFlag, unordered_is_true);
1100 assert(x->type()->tag() == y->type()->tag(), "types must match");
1101 pin();
1102
1103 stringStream strStream;
1104 Compilation::current()->method()->print_name(&strStream);
1105
1106 stringStream strStream1;
1107 InstructionPrinter ip1(1, &strStream1);
1108 ip1.print_instr(x);
1109
1110 stringStream strStream2;
1111 InstructionPrinter ip2(1, &strStream2);
1112 ip2.print_instr(y);
1113
1114 stringStream ss;
1115 ss.print("Assertion %s %s %s in method %s", strStream1.as_string(), ip2.cond_name(cond), strStream2.as_string(), strStream.as_string());
1116
1117 _message = ss.as_string();
1118 }
1119 #endif
1120
1121 void RangeCheckPredicate::check_state() {
1122 assert(state()->kind() != ValueStack::EmptyExceptionState && state()->kind() != ValueStack::ExceptionState, "will deopt with empty state");
1123 }
1124
1125 void ProfileInvoke::state_values_do(ValueVisitor* f) {
1126 if (state() != NULL) state()->values_do(f);
1127 }
1128