1 /*
2 * Copyright 1999-2006 Sun Microsystems, Inc. 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 Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
20 * CA 95054 USA or visit www.sun.com if you need additional information or
21 * have any questions.
22 *
23 */
24
25 #include "incls/_precompiled.incl"
26 #include "incls/_c1_Instruction.cpp.incl"
27
28
29 // Implementation of Instruction
30
31
32 int Instruction::_next_id = 0;
33
34 #ifdef ASSERT
35 void Instruction::create_hi_word() {
36 assert(type()->is_double_word() && _hi_word == NULL, "only double word has high word");
37 _hi_word = new HiWord(this);
38 }
39 #endif
40
41 Instruction::Condition Instruction::mirror(Condition cond) {
42 switch (cond) {
43 case eql: return eql;
44 case neq: return neq;
45 case lss: return gtr;
46 case leq: return geq;
47 case gtr: return lss;
48 case geq: return leq;
49 }
50 ShouldNotReachHere();
51 return eql;
52 }
53
54
55 Instruction::Condition Instruction::negate(Condition cond) {
56 switch (cond) {
57 case eql: return neq;
58 case neq: return eql;
59 case lss: return geq;
60 case leq: return gtr;
61 case gtr: return leq;
62 case geq: return lss;
63 }
64 ShouldNotReachHere();
65 return eql;
66 }
67
68
69 Instruction* Instruction::prev(BlockBegin* block) {
70 Instruction* p = NULL;
71 Instruction* q = block;
72 while (q != this) {
73 assert(q != NULL, "this is not in the block's instruction list");
74 p = q; q = q->next();
75 }
76 return p;
77 }
78
79
80 #ifndef PRODUCT
81 void Instruction::print() {
82 InstructionPrinter ip;
83 print(ip);
84 }
85
86
87 void Instruction::print_line() {
88 InstructionPrinter ip;
89 ip.print_line(this);
90 }
91
92
93 void Instruction::print(InstructionPrinter& ip) {
94 ip.print_head();
95 ip.print_line(this);
96 tty->cr();
97 }
98 #endif // PRODUCT
99
100
101 // perform constant and interval tests on index value
102 bool AccessIndexed::compute_needs_range_check() {
103 Constant* clength = length()->as_Constant();
104 Constant* cindex = index()->as_Constant();
105 if (clength && cindex) {
106 IntConstant* l = clength->type()->as_IntConstant();
107 IntConstant* i = cindex->type()->as_IntConstant();
108 if (l && i && i->value() < l->value() && i->value() >= 0) {
109 return false;
110 }
111 }
112 return true;
113 }
114
115
116 ciType* LoadIndexed::exact_type() const {
117 ciType* array_type = array()->exact_type();
118 if (array_type == NULL) {
119 return NULL;
120 }
121 assert(array_type->is_array_klass(), "what else?");
122 ciArrayKlass* ak = (ciArrayKlass*)array_type;
123
124 if (ak->element_type()->is_instance_klass()) {
125 ciInstanceKlass* ik = (ciInstanceKlass*)ak->element_type();
126 if (ik->is_loaded() && ik->is_final()) {
127 return ik;
128 }
129 }
130 return NULL;
131 }
132
133
134 ciType* LoadIndexed::declared_type() const {
135 ciType* array_type = array()->declared_type();
136 if (array_type == NULL) {
137 return NULL;
138 }
139 assert(array_type->is_array_klass(), "what else?");
140 ciArrayKlass* ak = (ciArrayKlass*)array_type;
141 return ak->element_type();
142 }
143
144
145 ciType* LoadField::declared_type() const {
146 return field()->type();
147 }
148
149
150 ciType* LoadField::exact_type() const {
151 ciType* type = declared_type();
152 // for primitive arrays, the declared type is the exact type
153 if (type->is_type_array_klass()) {
154 return type;
155 }
156 if (type->is_instance_klass()) {
157 ciInstanceKlass* ik = (ciInstanceKlass*)type;
158 if (ik->is_loaded() && ik->is_final()) {
159 return type;
160 }
161 }
162 return NULL;
163 }
164
165
166 ciType* NewTypeArray::exact_type() const {
167 return ciTypeArrayKlass::make(elt_type());
168 }
169
170
171 ciType* NewObjectArray::exact_type() const {
172 return ciObjArrayKlass::make(klass());
173 }
174
175
176 ciType* NewInstance::exact_type() const {
177 return klass();
178 }
179
180
181 ciType* CheckCast::declared_type() const {
182 return klass();
183 }
184
185 ciType* CheckCast::exact_type() const {
186 if (klass()->is_instance_klass()) {
187 ciInstanceKlass* ik = (ciInstanceKlass*)klass();
188 if (ik->is_loaded() && ik->is_final()) {
189 return ik;
190 }
191 }
192 return NULL;
193 }
194
195
196 void ArithmeticOp::other_values_do(void f(Value*)) {
197 if (lock_stack() != NULL) lock_stack()->values_do(f);
198 }
199
200 void NullCheck::other_values_do(void f(Value*)) {
201 lock_stack()->values_do(f);
202 }
203
204 void AccessArray::other_values_do(void f(Value*)) {
205 if (lock_stack() != NULL) lock_stack()->values_do(f);
206 }
207
208
209 // Implementation of AccessField
210
211 void AccessField::other_values_do(void f(Value*)) {
212 if (state_before() != NULL) state_before()->values_do(f);
213 if (lock_stack() != NULL) lock_stack()->values_do(f);
214 }
215
216
217 // Implementation of StoreIndexed
218
219 IRScope* StoreIndexed::scope() const {
220 return lock_stack()->scope();
221 }
222
223
224 // Implementation of ArithmeticOp
225
226 bool ArithmeticOp::is_commutative() const {
227 switch (op()) {
228 case Bytecodes::_iadd: // fall through
229 case Bytecodes::_ladd: // fall through
230 case Bytecodes::_fadd: // fall through
231 case Bytecodes::_dadd: // fall through
232 case Bytecodes::_imul: // fall through
233 case Bytecodes::_lmul: // fall through
234 case Bytecodes::_fmul: // fall through
235 case Bytecodes::_dmul: return true;
236 }
237 return false;
238 }
239
240
241 bool ArithmeticOp::can_trap() const {
242 switch (op()) {
243 case Bytecodes::_idiv: // fall through
244 case Bytecodes::_ldiv: // fall through
245 case Bytecodes::_irem: // fall through
246 case Bytecodes::_lrem: return true;
247 }
248 return false;
249 }
250
251
252 // Implementation of LogicOp
253
254 bool LogicOp::is_commutative() const {
255 #ifdef ASSERT
256 switch (op()) {
257 case Bytecodes::_iand: // fall through
258 case Bytecodes::_land: // fall through
259 case Bytecodes::_ior : // fall through
260 case Bytecodes::_lor : // fall through
261 case Bytecodes::_ixor: // fall through
262 case Bytecodes::_lxor: break;
263 default : ShouldNotReachHere();
264 }
265 #endif
266 // all LogicOps are commutative
267 return true;
268 }
269
270
271 // Implementation of CompareOp
272
273 void CompareOp::other_values_do(void f(Value*)) {
274 if (state_before() != NULL) state_before()->values_do(f);
275 }
276
277
278 // Implementation of IfOp
279
280 bool IfOp::is_commutative() const {
281 return cond() == eql || cond() == neq;
282 }
283
284
285 // Implementation of StateSplit
286
287 void StateSplit::substitute(BlockList& list, BlockBegin* old_block, BlockBegin* new_block) {
288 NOT_PRODUCT(bool assigned = false;)
289 for (int i = 0; i < list.length(); i++) {
290 BlockBegin** b = list.adr_at(i);
291 if (*b == old_block) {
292 *b = new_block;
293 NOT_PRODUCT(assigned = true;)
294 }
295 }
296 assert(assigned == true, "should have assigned at least once");
297 }
298
299
300 IRScope* StateSplit::scope() const {
301 return _state->scope();
302 }
303
304
305 void StateSplit::state_values_do(void f(Value*)) {
306 if (state() != NULL) state()->values_do(f);
307 }
308
309
310 void BlockBegin::state_values_do(void f(Value*)) {
311 StateSplit::state_values_do(f);
312
313 if (is_set(BlockBegin::exception_entry_flag)) {
314 for (int i = 0; i < number_of_exception_states(); i++) {
315 exception_state_at(i)->values_do(f);
316 }
317 }
318 }
319
320
321 void MonitorEnter::state_values_do(void f(Value*)) {
322 StateSplit::state_values_do(f);
323 _lock_stack_before->values_do(f);
324 }
325
326
327 void Intrinsic::state_values_do(void f(Value*)) {
328 StateSplit::state_values_do(f);
329 if (lock_stack() != NULL) lock_stack()->values_do(f);
330 }
331
332
333 // Implementation of Invoke
334
335
336 Invoke::Invoke(Bytecodes::Code code, ValueType* result_type, Value recv, Values* args,
337 int vtable_index, ciMethod* target)
338 : StateSplit(result_type)
339 , _code(code)
340 , _recv(recv)
341 , _args(args)
342 , _vtable_index(vtable_index)
343 , _target(target)
344 {
345 set_flag(TargetIsLoadedFlag, target->is_loaded());
346 set_flag(TargetIsFinalFlag, target_is_loaded() && target->is_final_method());
347 set_flag(TargetIsStrictfpFlag, target_is_loaded() && target->is_strict());
348
349 assert(args != NULL, "args must exist");
350 #ifdef ASSERT
351 values_do(assert_value);
352 #endif // ASSERT
353
354 // provide an initial guess of signature size.
355 _signature = new BasicTypeList(number_of_arguments() + (has_receiver() ? 1 : 0));
356 if (has_receiver()) {
357 _signature->append(as_BasicType(receiver()->type()));
358 }
359 for (int i = 0; i < number_of_arguments(); i++) {
360 ValueType* t = argument_at(i)->type();
361 BasicType bt = as_BasicType(t);
362 _signature->append(bt);
363 }
364 }
365
366
367 // Implementation of Contant
368 intx Constant::hash() const {
369 if (_state == NULL) {
370 switch (type()->tag()) {
371 case intTag:
372 return HASH2(name(), type()->as_IntConstant()->value());
373 case longTag:
374 {
375 jlong temp = type()->as_LongConstant()->value();
376 return HASH3(name(), high(temp), low(temp));
377 }
378 case floatTag:
379 return HASH2(name(), jint_cast(type()->as_FloatConstant()->value()));
380 case doubleTag:
381 {
382 jlong temp = jlong_cast(type()->as_DoubleConstant()->value());
383 return HASH3(name(), high(temp), low(temp));
384 }
385 case objectTag:
386 assert(type()->as_ObjectType()->is_loaded(), "can't handle unloaded values");
387 return HASH2(name(), type()->as_ObjectType()->constant_value());
388 }
389 }
390 return 0;
391 }
392
393 bool Constant::is_equal(Value v) const {
394 if (v->as_Constant() == NULL) return false;
395
396 switch (type()->tag()) {
397 case intTag:
398 {
399 IntConstant* t1 = type()->as_IntConstant();
400 IntConstant* t2 = v->type()->as_IntConstant();
401 return (t1 != NULL && t2 != NULL &&
402 t1->value() == t2->value());
403 }
404 case longTag:
405 {
406 LongConstant* t1 = type()->as_LongConstant();
407 LongConstant* t2 = v->type()->as_LongConstant();
408 return (t1 != NULL && t2 != NULL &&
409 t1->value() == t2->value());
410 }
411 case floatTag:
412 {
413 FloatConstant* t1 = type()->as_FloatConstant();
414 FloatConstant* t2 = v->type()->as_FloatConstant();
415 return (t1 != NULL && t2 != NULL &&
416 jint_cast(t1->value()) == jint_cast(t2->value()));
417 }
418 case doubleTag:
419 {
420 DoubleConstant* t1 = type()->as_DoubleConstant();
421 DoubleConstant* t2 = v->type()->as_DoubleConstant();
422 return (t1 != NULL && t2 != NULL &&
423 jlong_cast(t1->value()) == jlong_cast(t2->value()));
424 }
425 case objectTag:
426 {
427 ObjectType* t1 = type()->as_ObjectType();
428 ObjectType* t2 = v->type()->as_ObjectType();
429 return (t1 != NULL && t2 != NULL &&
430 t1->is_loaded() && t2->is_loaded() &&
431 t1->constant_value() == t2->constant_value());
432 }
433 }
434 return false;
435 }
436
437
438 BlockBegin* Constant::compare(Instruction::Condition cond, Value right,
439 BlockBegin* true_sux, BlockBegin* false_sux) {
440 Constant* rc = right->as_Constant();
441 // other is not a constant
442 if (rc == NULL) return NULL;
443
444 ValueType* lt = type();
445 ValueType* rt = rc->type();
446 // different types
447 if (lt->base() != rt->base()) return NULL;
448 switch (lt->tag()) {
449 case intTag: {
450 int x = lt->as_IntConstant()->value();
451 int y = rt->as_IntConstant()->value();
452 switch (cond) {
453 case If::eql: return x == y ? true_sux : false_sux;
454 case If::neq: return x != y ? true_sux : false_sux;
455 case If::lss: return x < y ? true_sux : false_sux;
456 case If::leq: return x <= y ? true_sux : false_sux;
457 case If::gtr: return x > y ? true_sux : false_sux;
458 case If::geq: return x >= y ? true_sux : false_sux;
459 }
460 break;
461 }
462 case longTag: {
463 jlong x = lt->as_LongConstant()->value();
464 jlong y = rt->as_LongConstant()->value();
465 switch (cond) {
466 case If::eql: return x == y ? true_sux : false_sux;
467 case If::neq: return x != y ? true_sux : false_sux;
468 case If::lss: return x < y ? true_sux : false_sux;
469 case If::leq: return x <= y ? true_sux : false_sux;
470 case If::gtr: return x > y ? true_sux : false_sux;
471 case If::geq: return x >= y ? true_sux : false_sux;
472 }
473 break;
474 }
475 case objectTag: {
476 ciObject* xvalue = lt->as_ObjectType()->constant_value();
477 ciObject* yvalue = rt->as_ObjectType()->constant_value();
478 assert(xvalue != NULL && yvalue != NULL, "not constants");
479 if (xvalue->is_loaded() && yvalue->is_loaded()) {
480 switch (cond) {
481 case If::eql: return xvalue == yvalue ? true_sux : false_sux;
482 case If::neq: return xvalue != yvalue ? true_sux : false_sux;
483 }
484 }
485 break;
486 }
487 }
488 return NULL;
489 }
490
491
492 void Constant::other_values_do(void f(Value*)) {
493 if (state() != NULL) state()->values_do(f);
494 }
495
496
497 // Implementation of NewArray
498
499 void NewArray::other_values_do(void f(Value*)) {
500 if (state_before() != NULL) state_before()->values_do(f);
501 }
502
503
504 // Implementation of TypeCheck
505
506 void TypeCheck::other_values_do(void f(Value*)) {
507 if (state_before() != NULL) state_before()->values_do(f);
508 }
509
510
511 // Implementation of BlockBegin
512
513 int BlockBegin::_next_block_id = 0;
514
515
516 void BlockBegin::set_end(BlockEnd* end) {
517 assert(end != NULL, "should not reset block end to NULL");
518 BlockEnd* old_end = _end;
519 if (end == old_end) {
520 return;
521 }
522 // Must make the predecessors/successors match up with the
523 // BlockEnd's notion.
524 int i, n;
525 if (old_end != NULL) {
526 // disconnect from the old end
527 old_end->set_begin(NULL);
528
529 // disconnect this block from it's current successors
530 for (i = 0; i < _successors.length(); i++) {
531 _successors.at(i)->remove_predecessor(this);
532 }
533 }
534 _end = end;
535
536 _successors.clear();
537 // Now reset successors list based on BlockEnd
538 n = end->number_of_sux();
539 for (i = 0; i < n; i++) {
540 BlockBegin* sux = end->sux_at(i);
541 _successors.append(sux);
542 sux->_predecessors.append(this);
543 }
544 _end->set_begin(this);
545 }
546
547
548 void BlockBegin::disconnect_edge(BlockBegin* from, BlockBegin* to) {
549 // disconnect any edges between from and to
550 #ifndef PRODUCT
551 if (PrintIR && Verbose) {
552 tty->print_cr("Disconnected edge B%d -> B%d", from->block_id(), to->block_id());
553 }
554 #endif
555 for (int s = 0; s < from->number_of_sux();) {
556 BlockBegin* sux = from->sux_at(s);
557 if (sux == to) {
558 int index = sux->_predecessors.index_of(from);
559 if (index >= 0) {
560 sux->_predecessors.remove_at(index);
561 }
562 from->_successors.remove_at(s);
563 } else {
564 s++;
565 }
566 }
567 }
568
569
570 void BlockBegin::disconnect_from_graph() {
571 // disconnect this block from all other blocks
572 for (int p = 0; p < number_of_preds(); p++) {
573 pred_at(p)->remove_successor(this);
574 }
575 for (int s = 0; s < number_of_sux(); s++) {
576 sux_at(s)->remove_predecessor(this);
577 }
578 }
579
580 void BlockBegin::substitute_sux(BlockBegin* old_sux, BlockBegin* new_sux) {
581 // modify predecessors before substituting successors
582 for (int i = 0; i < number_of_sux(); i++) {
583 if (sux_at(i) == old_sux) {
584 // remove old predecessor before adding new predecessor
585 // otherwise there is a dead predecessor in the list
586 new_sux->remove_predecessor(old_sux);
587 new_sux->add_predecessor(this);
588 }
589 }
590 old_sux->remove_predecessor(this);
591 end()->substitute_sux(old_sux, new_sux);
592 }
593
594
595
596 // In general it is not possible to calculate a value for the field "depth_first_number"
597 // of the inserted block, without recomputing the values of the other blocks
598 // in the CFG. Therefore the value of "depth_first_number" in BlockBegin becomes meaningless.
599 BlockBegin* BlockBegin::insert_block_between(BlockBegin* sux) {
600 // Try to make the bci close to a block with a single pred or sux,
601 // since this make the block layout algorithm work better.
602 int bci = -1;
603 if (sux->number_of_preds() == 1) {
604 bci = sux->bci();
605 } else {
606 bci = end()->bci();
607 }
608
609 BlockBegin* new_sux = new BlockBegin(bci);
610
611 // mark this block (special treatment when block order is computed)
612 new_sux->set(critical_edge_split_flag);
613
614 // This goto is not a safepoint.
615 Goto* e = new Goto(sux, false);
616 new_sux->set_next(e, bci);
617 new_sux->set_end(e);
618 // setup states
619 ValueStack* s = end()->state();
620 new_sux->set_state(s->copy());
621 e->set_state(s->copy());
622 assert(new_sux->state()->locals_size() == s->locals_size(), "local size mismatch!");
623 assert(new_sux->state()->stack_size() == s->stack_size(), "stack size mismatch!");
624 assert(new_sux->state()->locks_size() == s->locks_size(), "locks size mismatch!");
625
626 // link predecessor to new block
627 end()->substitute_sux(sux, new_sux);
628
629 // The ordering needs to be the same, so remove the link that the
630 // set_end call above added and substitute the new_sux for this
631 // block.
632 sux->remove_predecessor(new_sux);
633
634 // the successor could be the target of a switch so it might have
635 // multiple copies of this predecessor, so substitute the new_sux
636 // for the first and delete the rest.
637 bool assigned = false;
638 BlockList& list = sux->_predecessors;
639 for (int i = 0; i < list.length(); i++) {
640 BlockBegin** b = list.adr_at(i);
641 if (*b == this) {
642 if (assigned) {
643 list.remove_at(i);
644 // reprocess this index
645 i--;
646 } else {
647 assigned = true;
648 *b = new_sux;
649 }
650 // link the new block back to it's predecessors.
651 new_sux->add_predecessor(this);
652 }
653 }
654 assert(assigned == true, "should have assigned at least once");
655 return new_sux;
656 }
657
658
659 void BlockBegin::remove_successor(BlockBegin* pred) {
660 int idx;
661 while ((idx = _successors.index_of(pred)) >= 0) {
662 _successors.remove_at(idx);
663 }
664 }
665
666
667 void BlockBegin::add_predecessor(BlockBegin* pred) {
668 _predecessors.append(pred);
669 }
670
671
672 void BlockBegin::remove_predecessor(BlockBegin* pred) {
673 int idx;
674 while ((idx = _predecessors.index_of(pred)) >= 0) {
675 _predecessors.remove_at(idx);
676 }
677 }
678
679
680 void BlockBegin::add_exception_handler(BlockBegin* b) {
681 assert(b != NULL && (b->is_set(exception_entry_flag)), "exception handler must exist");
682 // add only if not in the list already
683 if (!_exception_handlers.contains(b)) _exception_handlers.append(b);
684 }
685
686 int BlockBegin::add_exception_state(ValueStack* state) {
687 assert(is_set(exception_entry_flag), "only for xhandlers");
688 if (_exception_states == NULL) {
689 _exception_states = new ValueStackStack(4);
690 }
691 _exception_states->append(state);
692 return _exception_states->length() - 1;
693 }
694
695
696 void BlockBegin::iterate_preorder(boolArray& mark, BlockClosure* closure) {
697 if (!mark.at(block_id())) {
698 mark.at_put(block_id(), true);
699 closure->block_do(this);
700 BlockEnd* e = end(); // must do this after block_do because block_do may change it!
701 { for (int i = number_of_exception_handlers() - 1; i >= 0; i--) exception_handler_at(i)->iterate_preorder(mark, closure); }
702 { for (int i = e->number_of_sux () - 1; i >= 0; i--) e->sux_at (i)->iterate_preorder(mark, closure); }
703 }
704 }
705
706
707 void BlockBegin::iterate_postorder(boolArray& mark, BlockClosure* closure) {
708 if (!mark.at(block_id())) {
709 mark.at_put(block_id(), true);
710 BlockEnd* e = end();
711 { for (int i = number_of_exception_handlers() - 1; i >= 0; i--) exception_handler_at(i)->iterate_postorder(mark, closure); }
712 { for (int i = e->number_of_sux () - 1; i >= 0; i--) e->sux_at (i)->iterate_postorder(mark, closure); }
713 closure->block_do(this);
714 }
715 }
716
717
718 void BlockBegin::iterate_preorder(BlockClosure* closure) {
719 boolArray mark(number_of_blocks(), false);
720 iterate_preorder(mark, closure);
721 }
722
723
724 void BlockBegin::iterate_postorder(BlockClosure* closure) {
725 boolArray mark(number_of_blocks(), false);
726 iterate_postorder(mark, closure);
727 }
728
729
730 void BlockBegin::block_values_do(void f(Value*)) {
731 for (Instruction* n = this; n != NULL; n = n->next()) n->values_do(f);
732 }
733
734
735 #ifndef PRODUCT
736 #define TRACE_PHI(code) if (PrintPhiFunctions) { code; }
737 #else
738 #define TRACE_PHI(coce)
739 #endif
740
741
742 bool BlockBegin::try_merge(ValueStack* new_state) {
743 TRACE_PHI(tty->print_cr("********** try_merge for block B%d", block_id()));
744
745 // local variables used for state iteration
746 int index;
747 Value new_value, existing_value;
748
749 ValueStack* existing_state = state();
750 if (existing_state == NULL) {
751 TRACE_PHI(tty->print_cr("first call of try_merge for this block"));
752
753 if (is_set(BlockBegin::was_visited_flag)) {
754 // this actually happens for complicated jsr/ret structures
755 return false; // BAILOUT in caller
756 }
757
758 // copy state because it is altered
759 new_state = new_state->copy();
760
761 // Use method liveness to invalidate dead locals
762 MethodLivenessResult liveness = new_state->scope()->method()->liveness_at_bci(bci());
763 if (liveness.is_valid()) {
764 assert((int)liveness.size() == new_state->locals_size(), "error in use of liveness");
765
766 for_each_local_value(new_state, index, new_value) {
767 if (!liveness.at(index) || new_value->type()->is_illegal()) {
768 new_state->invalidate_local(index);
769 TRACE_PHI(tty->print_cr("invalidating dead local %d", index));
770 }
771 }
772 }
773
774 if (is_set(BlockBegin::parser_loop_header_flag)) {
775 TRACE_PHI(tty->print_cr("loop header block, initializing phi functions"));
776
777 for_each_stack_value(new_state, index, new_value) {
778 new_state->setup_phi_for_stack(this, index);
779 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));
780 }
781
782 BitMap requires_phi_function = new_state->scope()->requires_phi_function();
783
784 for_each_local_value(new_state, index, new_value) {
785 bool requires_phi = requires_phi_function.at(index) || (new_value->type()->is_double_word() && requires_phi_function.at(index + 1));
786 if (requires_phi || !SelectivePhiFunctions) {
787 new_state->setup_phi_for_local(this, index);
788 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));
789 }
790 }
791 }
792
793 // initialize state of block
794 set_state(new_state);
795
796 } else if (existing_state->is_same_across_scopes(new_state)) {
797 TRACE_PHI(tty->print_cr("exisiting state found"));
798
799 // Inlining may cause the local state not to match up, so walk up
800 // the new state until we get to the same scope as the
801 // existing and then start processing from there.
802 while (existing_state->scope() != new_state->scope()) {
803 new_state = new_state->caller_state();
804 assert(new_state != NULL, "could not match up scopes");
805
806 assert(false, "check if this is necessary");
807 }
808
809 assert(existing_state->scope() == new_state->scope(), "not matching");
810 assert(existing_state->locals_size() == new_state->locals_size(), "not matching");
811 assert(existing_state->stack_size() == new_state->stack_size(), "not matching");
812
813 if (is_set(BlockBegin::was_visited_flag)) {
814 TRACE_PHI(tty->print_cr("loop header block, phis must be present"));
815
816 if (!is_set(BlockBegin::parser_loop_header_flag)) {
817 // this actually happens for complicated jsr/ret structures
818 return false; // BAILOUT in caller
819 }
820
821 for_each_local_value(existing_state, index, existing_value) {
822 Value new_value = new_state->local_at(index);
823 if (new_value == NULL || new_value->type()->tag() != existing_value->type()->tag()) {
824 // The old code invalidated the phi function here
825 // Because dead locals are replaced with NULL, this is a very rare case now, so simply bail out
826 return false; // BAILOUT in caller
827 }
828 }
829
830 #ifdef ASSERT
831 // check that all necessary phi functions are present
832 for_each_stack_value(existing_state, index, existing_value) {
833 assert(existing_value->as_Phi() != NULL && existing_value->as_Phi()->block() == this, "phi function required");
834 }
835 for_each_local_value(existing_state, index, existing_value) {
836 assert(existing_value == new_state->local_at(index) || (existing_value->as_Phi() != NULL && existing_value->as_Phi()->as_Phi()->block() == this), "phi function required");
837 }
838 #endif
839
840 } else {
841 TRACE_PHI(tty->print_cr("creating phi functions on demand"));
842
843 // create necessary phi functions for stack
844 for_each_stack_value(existing_state, index, existing_value) {
845 Value new_value = new_state->stack_at(index);
846 Phi* existing_phi = existing_value->as_Phi();
847
848 if (new_value != existing_value && (existing_phi == NULL || existing_phi->block() != this)) {
849 existing_state->setup_phi_for_stack(this, index);
850 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));
851 }
852 }
853
854 // create necessary phi functions for locals
855 for_each_local_value(existing_state, index, existing_value) {
856 Value new_value = new_state->local_at(index);
857 Phi* existing_phi = existing_value->as_Phi();
858
859 if (new_value == NULL || new_value->type()->tag() != existing_value->type()->tag()) {
860 existing_state->invalidate_local(index);
861 TRACE_PHI(tty->print_cr("invalidating local %d because of type mismatch", index));
862 } else if (new_value != existing_value && (existing_phi == NULL || existing_phi->block() != this)) {
863 existing_state->setup_phi_for_local(this, index);
864 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));
865 }
866 }
867 }
868
869 assert(existing_state->caller_state() == new_state->caller_state(), "caller states must be equal");
870
871 } else {
872 assert(false, "stack or locks not matching (invalid bytecodes)");
873 return false;
874 }
875
876 TRACE_PHI(tty->print_cr("********** try_merge for block B%d successful", block_id()));
877
878 return true;
879 }
880
881
882 #ifndef PRODUCT
883 void BlockBegin::print_block() {
884 InstructionPrinter ip;
885 print_block(ip, false);
886 }
887
888
889 void BlockBegin::print_block(InstructionPrinter& ip, bool live_only) {
890 ip.print_instr(this); tty->cr();
891 ip.print_stack(this->state()); tty->cr();
892 ip.print_inline_level(this);
893 ip.print_head();
894 for (Instruction* n = next(); n != NULL; n = n->next()) {
895 if (!live_only || n->is_pinned() || n->use_count() > 0) {
896 ip.print_line(n);
897 }
898 }
899 tty->cr();
900 }
901 #endif // PRODUCT
902
903
904 // Implementation of BlockList
905
906 void BlockList::iterate_forward (BlockClosure* closure) {
907 const int l = length();
908 for (int i = 0; i < l; i++) closure->block_do(at(i));
909 }
910
911
912 void BlockList::iterate_backward(BlockClosure* closure) {
913 for (int i = length() - 1; i >= 0; i--) closure->block_do(at(i));
914 }
915
916
917 void BlockList::blocks_do(void f(BlockBegin*)) {
918 for (int i = length() - 1; i >= 0; i--) f(at(i));
919 }
920
921
922 void BlockList::values_do(void f(Value*)) {
923 for (int i = length() - 1; i >= 0; i--) at(i)->block_values_do(f);
924 }
925
926
927 #ifndef PRODUCT
928 void BlockList::print(bool cfg_only, bool live_only) {
929 InstructionPrinter ip;
930 for (int i = 0; i < length(); i++) {
931 BlockBegin* block = at(i);
932 if (cfg_only) {
933 ip.print_instr(block); tty->cr();
934 } else {
935 block->print_block(ip, live_only);
936 }
937 }
938 }
939 #endif // PRODUCT
940
941
942 // Implementation of BlockEnd
943
944 void BlockEnd::set_begin(BlockBegin* begin) {
945 BlockList* sux = NULL;
946 if (begin != NULL) {
947 sux = begin->successors();
948 } else if (_begin != NULL) {
949 // copy our sux list
950 BlockList* sux = new BlockList(_begin->number_of_sux());
951 for (int i = 0; i < _begin->number_of_sux(); i++) {
952 sux->append(_begin->sux_at(i));
953 }
954 }
955 _sux = sux;
956 _begin = begin;
957 }
958
959
960 void BlockEnd::substitute_sux(BlockBegin* old_sux, BlockBegin* new_sux) {
961 substitute(*_sux, old_sux, new_sux);
962 }
963
964
965 void BlockEnd::other_values_do(void f(Value*)) {
966 if (state_before() != NULL) state_before()->values_do(f);
967 }
968
969
970 // Implementation of Phi
971
972 // Normal phi functions take their operands from the last instruction of the
973 // predecessor. Special handling is needed for xhanlder entries because there
974 // the state of arbitrary instructions are needed.
975
976 Value Phi::operand_at(int i) const {
977 ValueStack* state;
978 if (_block->is_set(BlockBegin::exception_entry_flag)) {
979 state = _block->exception_state_at(i);
980 } else {
981 state = _block->pred_at(i)->end()->state();
982 }
983 assert(state != NULL, "");
984
985 if (is_local()) {
986 return state->local_at(local_index());
987 } else {
988 return state->stack_at(stack_index());
989 }
990 }
991
992
993 int Phi::operand_count() const {
994 if (_block->is_set(BlockBegin::exception_entry_flag)) {
995 return _block->number_of_exception_states();
996 } else {
997 return _block->number_of_preds();
998 }
999 }
1000
1001
1002 // Implementation of Throw
1003
1004 void Throw::state_values_do(void f(Value*)) {
1005 BlockEnd::state_values_do(f);
1006 }