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