1 #ifdef USE_PRAGMA_IDENT_HDR
2 #pragma ident "@(#)ciTypeFlow.hpp 1.26 08/11/24 12:20:59 JVM"
3 #endif
4 /*
5 * Copyright 2000-2006 Sun Microsystems, Inc. All Rights Reserved.
6 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
7 *
8 * This code is free software; you can redistribute it and/or modify it
9 * under the terms of the GNU General Public License version 2 only, as
10 * published by the Free Software Foundation.
11 *
12 * This code is distributed in the hope that it will be useful, but WITHOUT
13 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 * version 2 for more details (a copy is included in the LICENSE file that
16 * accompanied this code).
17 *
18 * You should have received a copy of the GNU General Public License version
19 * 2 along with this work; if not, write to the Free Software Foundation,
20 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
21 *
22 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
23 * CA 95054 USA or visit www.sun.com if you need additional information or
24 * have any questions.
25 *
26 */
27
28
29 class ciTypeFlow : public ResourceObj {
30 private:
31 ciEnv* _env;
32 ciMethod* _method;
33 ciMethodBlocks* _methodBlocks;
34 int _osr_bci;
35
36 // information cached from the method:
37 int _max_locals;
38 int _max_stack;
39 int _code_size;
40
41 const char* _failure_reason;
42
43 public:
44 class StateVector;
45 class Block;
46
47 // Build a type flow analyzer
48 // Do an OSR analysis if osr_bci >= 0.
49 ciTypeFlow(ciEnv* env, ciMethod* method, int osr_bci = InvocationEntryBci);
50
51 // Accessors
52 ciMethod* method() const { return _method; }
53 ciEnv* env() { return _env; }
54 Arena* arena() { return _env->arena(); }
55 bool is_osr_flow() const{ return _osr_bci != InvocationEntryBci; }
56 int start_bci() const { return is_osr_flow()? _osr_bci: 0; }
57 int max_locals() const { return _max_locals; }
58 int max_stack() const { return _max_stack; }
59 int max_cells() const { return _max_locals + _max_stack; }
60 int code_size() const { return _code_size; }
61
62 // Represents information about an "active" jsr call. This
63 // class represents a call to the routine at some entry address
64 // with some distinct return address.
65 class JsrRecord : public ResourceObj {
66 private:
67 int _entry_address;
68 int _return_address;
69 public:
70 JsrRecord(int entry_address, int return_address) {
71 _entry_address = entry_address;
72 _return_address = return_address;
73 }
74
75 int entry_address() const { return _entry_address; }
76 int return_address() const { return _return_address; }
77
78 void print_on(outputStream* st) const {
79 #ifndef PRODUCT
80 st->print("%d->%d", entry_address(), return_address());
111 public:
112 JsrSet(Arena* arena, int default_len = 4);
113
114 // Copy this JsrSet.
115 void copy_into(JsrSet* jsrs);
116
117 // Is this JsrSet compatible with some other JsrSet?
118 bool is_compatible_with(JsrSet* other);
119
120 // Apply the effect of a single bytecode to the JsrSet.
121 void apply_control(ciTypeFlow* analyzer,
122 ciBytecodeStream* str,
123 StateVector* state);
124
125 // What is the cardinality of this set?
126 int size() const { return _set->length(); }
127
128 void print_on(outputStream* st) const PRODUCT_RETURN;
129 };
130
131 // Used as a combined index for locals and temps
132 enum Cell {
133 Cell_0, Cell_max = INT_MAX
134 };
135
136 // A StateVector summarizes the type information at some
137 // point in the program
138 class StateVector : public ResourceObj {
139 private:
140 ciType** _types;
141 int _stack_size;
142 int _monitor_count;
143 ciTypeFlow* _outer;
144
145 int _trap_bci;
146 int _trap_index;
147
148 static ciType* type_meet_internal(ciType* t1, ciType* t2, ciTypeFlow* analyzer);
149
150 public:
151 // Special elements in our type lattice.
152 enum {
153 T_TOP = T_VOID, // why not?
154 T_BOTTOM = T_CONFLICT,
155 T_LONG2 = T_SHORT, // 2nd word of T_LONG
156 T_DOUBLE2 = T_CHAR, // 2nd word of T_DOUBLE
157 T_NULL = T_BYTE // for now.
158 };
159 static ciType* top_type() { return ciType::make((BasicType)T_TOP); }
160 static ciType* bottom_type() { return ciType::make((BasicType)T_BOTTOM); }
161 static ciType* long2_type() { return ciType::make((BasicType)T_LONG2); }
162 static ciType* double2_type(){ return ciType::make((BasicType)T_DOUBLE2); }
163 static ciType* null_type() { return ciType::make((BasicType)T_NULL); }
164
165 static ciType* half_type(ciType* t) {
166 switch (t->basic_type()) {
167 case T_LONG: return long2_type();
168 case T_DOUBLE: return double2_type();
169 default: ShouldNotReachHere(); return NULL;
170 }
171 }
172
173 // The meet operation for our type lattice.
174 ciType* type_meet(ciType* t1, ciType* t2) {
175 return type_meet_internal(t1, t2, outer());
176 }
177
178 // Accessors
179 ciTypeFlow* outer() const { return _outer; }
180
181 int stack_size() const { return _stack_size; }
182 void set_stack_size(int ss) { _stack_size = ss; }
183
184 int monitor_count() const { return _monitor_count; }
185 void set_monitor_count(int mc) { _monitor_count = mc; }
186
187 static Cell start_cell() { return (Cell)0; }
188 static Cell next_cell(Cell c) { return (Cell)(((int)c) + 1); }
189 Cell limit_cell() const {
190 return (Cell)(outer()->max_locals() + stack_size());
191 }
192
193 // Cell creation
194 Cell local(int lnum) const {
195 assert(lnum < outer()->max_locals(), "index check");
196 return (Cell)(lnum);
197 }
198
199 Cell stack(int snum) const {
200 assert(snum < stack_size(), "index check");
201 return (Cell)(outer()->max_locals() + snum);
202 }
203
204 Cell tos() const { return stack(stack_size()-1); }
205
206 // For external use only:
236 return t;
237 }
238
239 // Convenience operations.
240 bool is_reference(ciType* type) const {
241 return type == null_type() || !type->is_primitive_type();
242 }
243 bool is_int(ciType* type) const {
244 return type->basic_type() == T_INT;
245 }
246 bool is_long(ciType* type) const {
247 return type->basic_type() == T_LONG;
248 }
249 bool is_float(ciType* type) const {
250 return type->basic_type() == T_FLOAT;
251 }
252 bool is_double(ciType* type) const {
253 return type->basic_type() == T_DOUBLE;
254 }
255
256 void push_translate(ciType* type);
257
258 void push_int() {
259 push(ciType::make(T_INT));
260 }
261 void pop_int() {
262 assert(is_int(type_at_tos()), "must be integer");
263 pop();
264 }
265 void check_int(Cell c) {
266 assert(is_int(type_at(c)), "must be integer");
267 }
268 void push_double() {
269 push(ciType::make(T_DOUBLE));
270 push(double2_type());
271 }
272 void pop_double() {
273 assert(type_at_tos() == double2_type(), "must be 2nd half");
274 pop();
275 assert(is_double(type_at_tos()), "must be double");
344 // a double or long value since it's seconf half is being overwritten.
345 int prev_index = index - 1;
346 if (prev_index >= 0 &&
347 (is_double(type_at(local(prev_index))) ||
348 is_long(type_at(local(prev_index))))) {
349 set_type_at(local(prev_index), bottom_type());
350 }
351 }
352
353 void load_local_object(int index) {
354 ciType* type = type_at(local(index));
355 assert(is_reference(type), "must be reference type");
356 push(type);
357 }
358 void store_local_object(int index) {
359 ciType* type = pop_value();
360 assert(is_reference(type) || type->is_return_address(),
361 "must be reference type or return address");
362 overwrite_local_double_long(index);
363 set_type_at(local(index), type);
364 }
365
366 void load_local_double(int index) {
367 ciType* type = type_at(local(index));
368 ciType* type2 = type_at(local(index+1));
369 assert(is_double(type), "must be double type");
370 assert(type2 == double2_type(), "must be 2nd half");
371 push(type);
372 push(double2_type());
373 }
374 void store_local_double(int index) {
375 ciType* type2 = pop_value();
376 ciType* type = pop_value();
377 assert(is_double(type), "must be double");
378 assert(type2 == double2_type(), "must be 2nd half");
379 overwrite_local_double_long(index);
380 set_type_at(local(index), type);
381 set_type_at(local(index+1), type2);
382 }
383
384 void load_local_float(int index) {
385 ciType* type = type_at(local(index));
386 assert(is_float(type), "must be float type");
387 push(type);
388 }
389 void store_local_float(int index) {
390 ciType* type = pop_value();
391 assert(is_float(type), "must be float type");
392 overwrite_local_double_long(index);
393 set_type_at(local(index), type);
394 }
395
396 void load_local_int(int index) {
397 ciType* type = type_at(local(index));
398 assert(is_int(type), "must be int type");
399 push(type);
400 }
401 void store_local_int(int index) {
402 ciType* type = pop_value();
403 assert(is_int(type), "must be int type");
404 overwrite_local_double_long(index);
405 set_type_at(local(index), type);
406 }
407
408 void load_local_long(int index) {
409 ciType* type = type_at(local(index));
410 ciType* type2 = type_at(local(index+1));
411 assert(is_long(type), "must be long type");
412 assert(type2 == long2_type(), "must be 2nd half");
413 push(type);
414 push(long2_type());
415 }
416 void store_local_long(int index) {
417 ciType* type2 = pop_value();
418 ciType* type = pop_value();
419 assert(is_long(type), "must be long");
420 assert(type2 == long2_type(), "must be 2nd half");
421 overwrite_local_double_long(index);
422 set_type_at(local(index), type);
423 set_type_at(local(index+1), type2);
424 }
425
426 // Stop interpretation of this path with a trap.
427 void trap(ciBytecodeStream* str, ciKlass* klass, int index);
428
429 public:
430 StateVector(ciTypeFlow* outer);
431
432 // Copy our value into some other StateVector
433 void copy_into(StateVector* copy) const;
434
435 // Meets this StateVector with another, destructively modifying this
436 // one. Returns true if any modification takes place.
437 bool meet(const StateVector* incoming);
438
439 // Ditto, except that the incoming state is coming from an exception.
440 bool meet_exception(ciInstanceKlass* exc, const StateVector* incoming);
441
442 // Apply the effect of one bytecode to this StateVector
443 bool apply_one_bytecode(ciBytecodeStream* stream);
444
445 // What is the bci of the trap?
446 int trap_bci() { return _trap_bci; }
447
448 // What is the index associated with the trap?
449 int trap_index() { return _trap_index; }
450
451 void print_cell_on(outputStream* st, Cell c) const PRODUCT_RETURN;
452 void print_on(outputStream* st) const PRODUCT_RETURN;
453 };
454
455 // Parameter for "find_block" calls:
456 // Describes the difference between a public and private copy.
457 enum CreateOption {
458 create_public_copy,
459 create_private_copy,
460 no_create
461 };
462
463 // A basic block
464 class Block : public ResourceObj {
465 private:
466 ciBlock* _ciblock;
467 GrowableArray<Block*>* _exceptions;
468 GrowableArray<ciInstanceKlass*>* _exc_klasses;
469 GrowableArray<Block*>* _successors;
470 StateVector* _state;
471 JsrSet* _jsrs;
472
473 int _trap_bci;
474 int _trap_index;
475
476 // A reasonable approximation to pre-order, provided.to the client.
477 int _pre_order;
478
479 // Has this block been cloned for some special purpose?
480 bool _private_copy;
481
482 // A pointer used for our internal work list
483 Block* _next;
484 bool _on_work_list;
485
486 ciBlock* ciblock() const { return _ciblock; }
487 StateVector* state() const { return _state; }
488
489 // Compute the exceptional successors and types for this Block.
490 void compute_exceptions();
491
492 public:
493 // constructors
494 Block(ciTypeFlow* outer, ciBlock* ciblk, JsrSet* jsrs);
495
496 void set_trap(int trap_bci, int trap_index) {
497 _trap_bci = trap_bci;
498 _trap_index = trap_index;
499 assert(has_trap(), "");
500 }
501 bool has_trap() const { return _trap_bci != -1; }
502 int trap_bci() const { assert(has_trap(), ""); return _trap_bci; }
503 int trap_index() const { assert(has_trap(), ""); return _trap_index; }
504
505 // accessors
506 ciTypeFlow* outer() const { return state()->outer(); }
507 int start() const { return _ciblock->start_bci(); }
508 int limit() const { return _ciblock->limit_bci(); }
509 int control() const { return _ciblock->control_bci(); }
510
511 bool is_private_copy() const { return _private_copy; }
512 void set_private_copy(bool z);
513 int private_copy_count() const { return outer()->private_copy_count(ciblock()->index(), _jsrs); }
514
515 // access to entry state
516 int stack_size() const { return _state->stack_size(); }
517 int monitor_count() const { return _state->monitor_count(); }
518 ciType* local_type_at(int i) const { return _state->local_type_at(i); }
519 ciType* stack_type_at(int i) const { return _state->stack_type_at(i); }
520
521 // Get the successors for this Block.
522 GrowableArray<Block*>* successors(ciBytecodeStream* str,
523 StateVector* state,
524 JsrSet* jsrs);
525 GrowableArray<Block*>* successors() {
526 assert(_successors != NULL, "must be filled in");
527 return _successors;
528 }
529
530 // Helper function for "successors" when making private copies of
531 // loop heads for C2.
532 Block * clone_loop_head(ciTypeFlow* analyzer,
533 int branch_bci,
534 Block* target,
535 JsrSet* jsrs);
536
537 // Get the exceptional successors for this Block.
538 GrowableArray<Block*>* exceptions() {
539 if (_exceptions == NULL) {
540 compute_exceptions();
541 }
542 return _exceptions;
543 }
544
545 // Get the exception klasses corresponding to the
546 // exceptional successors for this Block.
547 GrowableArray<ciInstanceKlass*>* exc_klasses() {
548 if (_exc_klasses == NULL) {
549 compute_exceptions();
550 }
551 return _exc_klasses;
552 }
553
554 // Is this Block compatible with a given JsrSet?
555 bool is_compatible_with(JsrSet* other) {
556 return _jsrs->is_compatible_with(other);
570 // modifying this one. Returns true if any modification takes place.
571 bool meet(const StateVector* incoming) {
572 return state()->meet(incoming);
573 }
574
575 // Ditto, except that the incoming state is coming from an
576 // exception path. This means the stack is replaced by the
577 // appropriate exception type.
578 bool meet_exception(ciInstanceKlass* exc, const StateVector* incoming) {
579 return state()->meet_exception(exc, incoming);
580 }
581
582 // Work list manipulation
583 void set_next(Block* block) { _next = block; }
584 Block* next() const { return _next; }
585
586 void set_on_work_list(bool c) { _on_work_list = c; }
587 bool is_on_work_list() const { return _on_work_list; }
588
589 bool has_pre_order() const { return _pre_order >= 0; }
590 void set_pre_order(int po) { assert(!has_pre_order() && po >= 0, ""); _pre_order = po; }
591 int pre_order() const { assert(has_pre_order(), ""); return _pre_order; }
592 bool is_start() const { return _pre_order == outer()->start_block_num(); }
593
594 // A ranking used in determining order within the work list.
595 bool is_simpler_than(Block* other);
596
597 void print_value_on(outputStream* st) const PRODUCT_RETURN;
598 void print_on(outputStream* st) const PRODUCT_RETURN;
599 };
600
601 // Standard indexes of successors, for various bytecodes.
602 enum {
603 FALL_THROUGH = 0, // normal control
604 IF_NOT_TAKEN = 0, // the not-taken branch of an if (i.e., fall-through)
605 IF_TAKEN = 1, // the taken branch of an if
606 GOTO_TARGET = 0, // unique successor for goto, jsr, or ret
607 SWITCH_DEFAULT = 0, // default branch of a switch
608 SWITCH_CASES = 1 // first index for any non-default switch branches
609 // Unlike in other blocks, the successors of a switch are listed uniquely.
610 };
611
612 private:
613 // A mapping from pre_order to Blocks. This array is created
614 // only at the end of the flow.
615 Block** _block_map;
616
617 // For each ciBlock index, a list of Blocks which share this ciBlock.
618 GrowableArray<Block*>** _idx_to_blocklist;
619 // count of ciBlocks
620 int _ciblock_count;
621
622 // Tells if a given instruction is able to generate an exception edge.
623 bool can_trap(ciBytecodeStream& str);
624
625 public:
626 // Return the block beginning at bci which has a JsrSet compatible
627 // with jsrs.
628 Block* block_at(int bci, JsrSet* set, CreateOption option = create_public_copy);
629
630 // block factory
631 Block* get_block_for(int ciBlockIndex, JsrSet* jsrs, CreateOption option = create_public_copy);
632
633 // How many of the blocks have the private_copy bit set?
634 int private_copy_count(int ciBlockIndex, JsrSet* jsrs) const;
635
636 // Return an existing block containing bci which has a JsrSet compatible
637 // with jsrs, or NULL if there is none.
638 Block* existing_block_at(int bci, JsrSet* set) { return block_at(bci, set, no_create); }
639
640 // Tell whether the flow analysis has encountered an error of some sort.
641 bool failing() { return env()->failing() || _failure_reason != NULL; }
642
643 // Reason this compilation is failing, such as "too many basic blocks".
644 const char* failure_reason() { return _failure_reason; }
645
646 // Note a failure.
647 void record_failure(const char* reason);
648
649 // Return the block of a given pre-order number.
650 int have_block_count() const { return _block_map != NULL; }
651 int block_count() const { assert(have_block_count(), "");
652 return _next_pre_order; }
653 Block* pre_order_at(int po) const { assert(0 <= po && po < block_count(), "out of bounds");
654 return _block_map[po]; }
655 Block* start_block() const { return pre_order_at(start_block_num()); }
656 int start_block_num() const { return 0; }
657
658 private:
659 // A work list used during flow analysis.
660 Block* _work_list;
661
662 // Next Block::_pre_order. After mapping, doubles as block_count.
663 int _next_pre_order;
664
665 // Are there more blocks on the work list?
666 bool work_list_empty() { return _work_list == NULL; }
667
668 // Get the next basic block from our work list.
669 Block* work_list_next();
670
671 // Add a basic block to our work list.
672 void add_to_work_list(Block* block);
673
674 // State used for make_jsr_record
675 int _jsr_count;
676 GrowableArray<JsrRecord*>* _jsr_records;
677
678 public:
679 // Make a JsrRecord for a given (entry, return) pair, if such a record
680 // does not already exist.
681 JsrRecord* make_jsr_record(int entry_address, int return_address);
682
683 private:
684 // Get the initial state for start_bci:
685 const StateVector* get_start_state();
686
687 // Merge the current state into all exceptional successors at the
688 // current point in the code.
689 void flow_exceptions(GrowableArray<Block*>* exceptions,
690 GrowableArray<ciInstanceKlass*>* exc_klasses,
691 StateVector* state);
692
693 // Merge the current state into all successors at the current point
694 // in the code.
695 void flow_successors(GrowableArray<Block*>* successors,
696 StateVector* state);
697
698 // Interpret the effects of the bytecodes on the incoming state
699 // vector of a basic block. Push the changed state to succeeding
700 // basic blocks.
701 void flow_block(Block* block,
702 StateVector* scratch_state,
703 JsrSet* scratch_jsrs);
704
705 // Perform the type flow analysis, creating and cloning Blocks as
706 // necessary.
707 void flow_types();
708
709 // Create the block map, which indexes blocks in pre_order.
710 void map_blocks();
711
712 public:
713 // Perform type inference flow analysis.
714 void do_flow();
715
716 void print_on(outputStream* st) const PRODUCT_RETURN;
717 };
|
1 #ifdef USE_PRAGMA_IDENT_HDR
2 #pragma ident "@(#)ciTypeFlow.hpp 1.26 08/11/24 12:20:59 JVM"
3 #endif
4 /*
5 * Copyright 2000-2008 Sun Microsystems, Inc. All Rights Reserved.
6 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
7 *
8 * This code is free software; you can redistribute it and/or modify it
9 * under the terms of the GNU General Public License version 2 only, as
10 * published by the Free Software Foundation.
11 *
12 * This code is distributed in the hope that it will be useful, but WITHOUT
13 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 * version 2 for more details (a copy is included in the LICENSE file that
16 * accompanied this code).
17 *
18 * You should have received a copy of the GNU General Public License version
19 * 2 along with this work; if not, write to the Free Software Foundation,
20 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
21 *
22 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
23 * CA 95054 USA or visit www.sun.com if you need additional information or
24 * have any questions.
25 *
26 */
27
28
29 class ciTypeFlow : public ResourceObj {
30 private:
31 ciEnv* _env;
32 ciMethod* _method;
33 ciMethodBlocks* _methodBlocks;
34 int _osr_bci;
35
36 // information cached from the method:
37 int _max_locals;
38 int _max_stack;
39 int _code_size;
40 bool _has_irreducible_entry;
41
42 const char* _failure_reason;
43
44 public:
45 class StateVector;
46 class Loop;
47 class Block;
48
49 // Build a type flow analyzer
50 // Do an OSR analysis if osr_bci >= 0.
51 ciTypeFlow(ciEnv* env, ciMethod* method, int osr_bci = InvocationEntryBci);
52
53 // Accessors
54 ciMethod* method() const { return _method; }
55 ciEnv* env() { return _env; }
56 Arena* arena() { return _env->arena(); }
57 bool is_osr_flow() const{ return _osr_bci != InvocationEntryBci; }
58 int start_bci() const { return is_osr_flow()? _osr_bci: 0; }
59 int max_locals() const { return _max_locals; }
60 int max_stack() const { return _max_stack; }
61 int max_cells() const { return _max_locals + _max_stack; }
62 int code_size() const { return _code_size; }
63 bool has_irreducible_entry() const { return _has_irreducible_entry; }
64
65 // Represents information about an "active" jsr call. This
66 // class represents a call to the routine at some entry address
67 // with some distinct return address.
68 class JsrRecord : public ResourceObj {
69 private:
70 int _entry_address;
71 int _return_address;
72 public:
73 JsrRecord(int entry_address, int return_address) {
74 _entry_address = entry_address;
75 _return_address = return_address;
76 }
77
78 int entry_address() const { return _entry_address; }
79 int return_address() const { return _return_address; }
80
81 void print_on(outputStream* st) const {
82 #ifndef PRODUCT
83 st->print("%d->%d", entry_address(), return_address());
114 public:
115 JsrSet(Arena* arena, int default_len = 4);
116
117 // Copy this JsrSet.
118 void copy_into(JsrSet* jsrs);
119
120 // Is this JsrSet compatible with some other JsrSet?
121 bool is_compatible_with(JsrSet* other);
122
123 // Apply the effect of a single bytecode to the JsrSet.
124 void apply_control(ciTypeFlow* analyzer,
125 ciBytecodeStream* str,
126 StateVector* state);
127
128 // What is the cardinality of this set?
129 int size() const { return _set->length(); }
130
131 void print_on(outputStream* st) const PRODUCT_RETURN;
132 };
133
134 class LocalSet VALUE_OBJ_CLASS_SPEC {
135 private:
136 enum Constants { max = 63 };
137 uint64_t _bits;
138 public:
139 LocalSet() : _bits(0) {}
140 void add(uint32_t i) { if (i < (uint32_t)max) _bits |= (1LL << i); }
141 void add(LocalSet* ls) { _bits |= ls->_bits; }
142 bool test(uint32_t i) const { return i < (uint32_t)max ? (_bits>>i)&1U : true; }
143 void clear() { _bits = 0; }
144 void print_on(outputStream* st, int limit) const PRODUCT_RETURN;
145 };
146
147 // Used as a combined index for locals and temps
148 enum Cell {
149 Cell_0, Cell_max = INT_MAX
150 };
151
152 // A StateVector summarizes the type information at some
153 // point in the program
154 class StateVector : public ResourceObj {
155 private:
156 ciType** _types;
157 int _stack_size;
158 int _monitor_count;
159 ciTypeFlow* _outer;
160
161 int _trap_bci;
162 int _trap_index;
163
164 LocalSet _def_locals; // For entire block
165
166 static ciType* type_meet_internal(ciType* t1, ciType* t2, ciTypeFlow* analyzer);
167
168 public:
169 // Special elements in our type lattice.
170 enum {
171 T_TOP = T_VOID, // why not?
172 T_BOTTOM = T_CONFLICT,
173 T_LONG2 = T_SHORT, // 2nd word of T_LONG
174 T_DOUBLE2 = T_CHAR, // 2nd word of T_DOUBLE
175 T_NULL = T_BYTE // for now.
176 };
177 static ciType* top_type() { return ciType::make((BasicType)T_TOP); }
178 static ciType* bottom_type() { return ciType::make((BasicType)T_BOTTOM); }
179 static ciType* long2_type() { return ciType::make((BasicType)T_LONG2); }
180 static ciType* double2_type(){ return ciType::make((BasicType)T_DOUBLE2); }
181 static ciType* null_type() { return ciType::make((BasicType)T_NULL); }
182
183 static ciType* half_type(ciType* t) {
184 switch (t->basic_type()) {
185 case T_LONG: return long2_type();
186 case T_DOUBLE: return double2_type();
187 default: ShouldNotReachHere(); return NULL;
188 }
189 }
190
191 // The meet operation for our type lattice.
192 ciType* type_meet(ciType* t1, ciType* t2) {
193 return type_meet_internal(t1, t2, outer());
194 }
195
196 // Accessors
197 ciTypeFlow* outer() const { return _outer; }
198
199 int stack_size() const { return _stack_size; }
200 void set_stack_size(int ss) { _stack_size = ss; }
201
202 int monitor_count() const { return _monitor_count; }
203 void set_monitor_count(int mc) { _monitor_count = mc; }
204
205 LocalSet* def_locals() { return &_def_locals; }
206 const LocalSet* def_locals() const { return &_def_locals; }
207
208 static Cell start_cell() { return (Cell)0; }
209 static Cell next_cell(Cell c) { return (Cell)(((int)c) + 1); }
210 Cell limit_cell() const {
211 return (Cell)(outer()->max_locals() + stack_size());
212 }
213
214 // Cell creation
215 Cell local(int lnum) const {
216 assert(lnum < outer()->max_locals(), "index check");
217 return (Cell)(lnum);
218 }
219
220 Cell stack(int snum) const {
221 assert(snum < stack_size(), "index check");
222 return (Cell)(outer()->max_locals() + snum);
223 }
224
225 Cell tos() const { return stack(stack_size()-1); }
226
227 // For external use only:
257 return t;
258 }
259
260 // Convenience operations.
261 bool is_reference(ciType* type) const {
262 return type == null_type() || !type->is_primitive_type();
263 }
264 bool is_int(ciType* type) const {
265 return type->basic_type() == T_INT;
266 }
267 bool is_long(ciType* type) const {
268 return type->basic_type() == T_LONG;
269 }
270 bool is_float(ciType* type) const {
271 return type->basic_type() == T_FLOAT;
272 }
273 bool is_double(ciType* type) const {
274 return type->basic_type() == T_DOUBLE;
275 }
276
277 void store_to_local(int lnum) {
278 _def_locals.add((uint) lnum);
279 }
280
281 void push_translate(ciType* type);
282
283 void push_int() {
284 push(ciType::make(T_INT));
285 }
286 void pop_int() {
287 assert(is_int(type_at_tos()), "must be integer");
288 pop();
289 }
290 void check_int(Cell c) {
291 assert(is_int(type_at(c)), "must be integer");
292 }
293 void push_double() {
294 push(ciType::make(T_DOUBLE));
295 push(double2_type());
296 }
297 void pop_double() {
298 assert(type_at_tos() == double2_type(), "must be 2nd half");
299 pop();
300 assert(is_double(type_at_tos()), "must be double");
369 // a double or long value since it's seconf half is being overwritten.
370 int prev_index = index - 1;
371 if (prev_index >= 0 &&
372 (is_double(type_at(local(prev_index))) ||
373 is_long(type_at(local(prev_index))))) {
374 set_type_at(local(prev_index), bottom_type());
375 }
376 }
377
378 void load_local_object(int index) {
379 ciType* type = type_at(local(index));
380 assert(is_reference(type), "must be reference type");
381 push(type);
382 }
383 void store_local_object(int index) {
384 ciType* type = pop_value();
385 assert(is_reference(type) || type->is_return_address(),
386 "must be reference type or return address");
387 overwrite_local_double_long(index);
388 set_type_at(local(index), type);
389 store_to_local(index);
390 }
391
392 void load_local_double(int index) {
393 ciType* type = type_at(local(index));
394 ciType* type2 = type_at(local(index+1));
395 assert(is_double(type), "must be double type");
396 assert(type2 == double2_type(), "must be 2nd half");
397 push(type);
398 push(double2_type());
399 }
400 void store_local_double(int index) {
401 ciType* type2 = pop_value();
402 ciType* type = pop_value();
403 assert(is_double(type), "must be double");
404 assert(type2 == double2_type(), "must be 2nd half");
405 overwrite_local_double_long(index);
406 set_type_at(local(index), type);
407 set_type_at(local(index+1), type2);
408 store_to_local(index);
409 store_to_local(index+1);
410 }
411
412 void load_local_float(int index) {
413 ciType* type = type_at(local(index));
414 assert(is_float(type), "must be float type");
415 push(type);
416 }
417 void store_local_float(int index) {
418 ciType* type = pop_value();
419 assert(is_float(type), "must be float type");
420 overwrite_local_double_long(index);
421 set_type_at(local(index), type);
422 store_to_local(index);
423 }
424
425 void load_local_int(int index) {
426 ciType* type = type_at(local(index));
427 assert(is_int(type), "must be int type");
428 push(type);
429 }
430 void store_local_int(int index) {
431 ciType* type = pop_value();
432 assert(is_int(type), "must be int type");
433 overwrite_local_double_long(index);
434 set_type_at(local(index), type);
435 store_to_local(index);
436 }
437
438 void load_local_long(int index) {
439 ciType* type = type_at(local(index));
440 ciType* type2 = type_at(local(index+1));
441 assert(is_long(type), "must be long type");
442 assert(type2 == long2_type(), "must be 2nd half");
443 push(type);
444 push(long2_type());
445 }
446 void store_local_long(int index) {
447 ciType* type2 = pop_value();
448 ciType* type = pop_value();
449 assert(is_long(type), "must be long");
450 assert(type2 == long2_type(), "must be 2nd half");
451 overwrite_local_double_long(index);
452 set_type_at(local(index), type);
453 set_type_at(local(index+1), type2);
454 store_to_local(index);
455 store_to_local(index+1);
456 }
457
458 // Stop interpretation of this path with a trap.
459 void trap(ciBytecodeStream* str, ciKlass* klass, int index);
460
461 public:
462 StateVector(ciTypeFlow* outer);
463
464 // Copy our value into some other StateVector
465 void copy_into(StateVector* copy) const;
466
467 // Meets this StateVector with another, destructively modifying this
468 // one. Returns true if any modification takes place.
469 bool meet(const StateVector* incoming);
470
471 // Ditto, except that the incoming state is coming from an exception.
472 bool meet_exception(ciInstanceKlass* exc, const StateVector* incoming);
473
474 // Apply the effect of one bytecode to this StateVector
475 bool apply_one_bytecode(ciBytecodeStream* stream);
476
477 // What is the bci of the trap?
478 int trap_bci() { return _trap_bci; }
479
480 // What is the index associated with the trap?
481 int trap_index() { return _trap_index; }
482
483 void print_cell_on(outputStream* st, Cell c) const PRODUCT_RETURN;
484 void print_on(outputStream* st) const PRODUCT_RETURN;
485 };
486
487 // Parameter for "find_block" calls:
488 // Describes the difference between a public and backedge copy.
489 enum CreateOption {
490 create_public_copy,
491 create_backedge_copy,
492 no_create
493 };
494
495 // Successor iterator
496 class SuccIter : public StackObj {
497 private:
498 Block* _pred;
499 int _index;
500 Block* _succ;
501 public:
502 SuccIter() : _pred(NULL), _index(-1), _succ(NULL) {}
503 SuccIter(Block* pred) : _pred(pred), _index(-1), _succ(NULL) { next(); }
504 int index() { return _index; }
505 Block* pred() { return _pred; } // Return predecessor
506 bool done() { return _index < 0; } // Finished?
507 Block* succ() { return _succ; } // Return current successor
508 void next(); // Advance
509 void set_succ(Block* succ); // Update current successor
510 bool is_normal_ctrl() { return index() < _pred->successors()->length(); }
511 };
512
513 // A basic block
514 class Block : public ResourceObj {
515 private:
516 ciBlock* _ciblock;
517 GrowableArray<Block*>* _exceptions;
518 GrowableArray<ciInstanceKlass*>* _exc_klasses;
519 GrowableArray<Block*>* _successors;
520 StateVector* _state;
521 JsrSet* _jsrs;
522
523 int _trap_bci;
524 int _trap_index;
525
526 // pre_order, assigned at first visit. Used as block ID and "visited" tag
527 int _pre_order;
528
529 // A post-order, used to compute the reverse post order (RPO) provided to the client
530 int _post_order; // used to compute rpo
531
532 // Has this block been cloned for a loop backedge?
533 bool _backedge_copy;
534
535 // A pointer used for our internal work list
536 Block* _next;
537 bool _on_work_list; // on the work list
538 Block* _rpo_next; // Reverse post order list
539
540 // Loop info
541 Loop* _loop; // nearest loop
542 bool _irreducible_entry; // entry to irreducible loop
543 bool _exception_entry; // entry to exception handler
544
545 ciBlock* ciblock() const { return _ciblock; }
546 StateVector* state() const { return _state; }
547
548 // Compute the exceptional successors and types for this Block.
549 void compute_exceptions();
550
551 public:
552 // constructors
553 Block(ciTypeFlow* outer, ciBlock* ciblk, JsrSet* jsrs);
554
555 void set_trap(int trap_bci, int trap_index) {
556 _trap_bci = trap_bci;
557 _trap_index = trap_index;
558 assert(has_trap(), "");
559 }
560 bool has_trap() const { return _trap_bci != -1; }
561 int trap_bci() const { assert(has_trap(), ""); return _trap_bci; }
562 int trap_index() const { assert(has_trap(), ""); return _trap_index; }
563
564 // accessors
565 ciTypeFlow* outer() const { return state()->outer(); }
566 int start() const { return _ciblock->start_bci(); }
567 int limit() const { return _ciblock->limit_bci(); }
568 int control() const { return _ciblock->control_bci(); }
569 JsrSet* jsrs() const { return _jsrs; }
570
571 bool is_backedge_copy() const { return _backedge_copy; }
572 void set_backedge_copy(bool z);
573 int backedge_copy_count() const { return outer()->backedge_copy_count(ciblock()->index(), _jsrs); }
574
575 // access to entry state
576 int stack_size() const { return _state->stack_size(); }
577 int monitor_count() const { return _state->monitor_count(); }
578 ciType* local_type_at(int i) const { return _state->local_type_at(i); }
579 ciType* stack_type_at(int i) const { return _state->stack_type_at(i); }
580
581 // Data flow on locals
582 bool is_invariant_local(uint v) const {
583 assert(is_loop_head(), "only loop heads");
584 // Find outermost loop with same loop head
585 Loop* lp = loop();
586 while (lp->parent() != NULL) {
587 if (lp->parent()->head() != lp->head()) break;
588 lp = lp->parent();
589 }
590 return !lp->def_locals()->test(v);
591 }
592 LocalSet* def_locals() { return _state->def_locals(); }
593 const LocalSet* def_locals() const { return _state->def_locals(); }
594
595 // Get the successors for this Block.
596 GrowableArray<Block*>* successors(ciBytecodeStream* str,
597 StateVector* state,
598 JsrSet* jsrs);
599 GrowableArray<Block*>* successors() {
600 assert(_successors != NULL, "must be filled in");
601 return _successors;
602 }
603
604 // Get the exceptional successors for this Block.
605 GrowableArray<Block*>* exceptions() {
606 if (_exceptions == NULL) {
607 compute_exceptions();
608 }
609 return _exceptions;
610 }
611
612 // Get the exception klasses corresponding to the
613 // exceptional successors for this Block.
614 GrowableArray<ciInstanceKlass*>* exc_klasses() {
615 if (_exc_klasses == NULL) {
616 compute_exceptions();
617 }
618 return _exc_klasses;
619 }
620
621 // Is this Block compatible with a given JsrSet?
622 bool is_compatible_with(JsrSet* other) {
623 return _jsrs->is_compatible_with(other);
637 // modifying this one. Returns true if any modification takes place.
638 bool meet(const StateVector* incoming) {
639 return state()->meet(incoming);
640 }
641
642 // Ditto, except that the incoming state is coming from an
643 // exception path. This means the stack is replaced by the
644 // appropriate exception type.
645 bool meet_exception(ciInstanceKlass* exc, const StateVector* incoming) {
646 return state()->meet_exception(exc, incoming);
647 }
648
649 // Work list manipulation
650 void set_next(Block* block) { _next = block; }
651 Block* next() const { return _next; }
652
653 void set_on_work_list(bool c) { _on_work_list = c; }
654 bool is_on_work_list() const { return _on_work_list; }
655
656 bool has_pre_order() const { return _pre_order >= 0; }
657 void set_pre_order(int po) { assert(!has_pre_order(), ""); _pre_order = po; }
658 int pre_order() const { assert(has_pre_order(), ""); return _pre_order; }
659 void set_next_pre_order() { set_pre_order(outer()->inc_next_pre_order()); }
660 bool is_start() const { return _pre_order == outer()->start_block_num(); }
661
662 // Reverse post order
663 void df_init();
664 bool has_post_order() const { return _post_order >= 0; }
665 void set_post_order(int po) { assert(!has_post_order() && po >= 0, ""); _post_order = po; }
666 void reset_post_order(int o){ _post_order = o; }
667 int post_order() const { assert(has_post_order(), ""); return _post_order; }
668
669 bool has_rpo() const { return has_post_order() && outer()->have_block_count(); }
670 int rpo() const { assert(has_rpo(), ""); return outer()->block_count() - post_order() - 1; }
671 void set_rpo_next(Block* b) { _rpo_next = b; }
672 Block* rpo_next() { return _rpo_next; }
673
674 // Loops
675 Loop* loop() const { return _loop; }
676 void set_loop(Loop* lp) { _loop = lp; }
677 bool is_loop_head() const { return _loop && _loop->head() == this; }
678 void set_irreducible_entry(bool c) { _irreducible_entry = c; }
679 bool is_irreducible_entry() const { return _irreducible_entry; }
680 bool is_visited() const { return has_pre_order(); }
681 bool is_post_visited() const { return has_post_order(); }
682 bool is_clonable_exit(Loop* lp);
683 Block* looping_succ(Loop* lp); // Successor inside of loop
684 bool is_single_entry_loop_head() const {
685 if (!is_loop_head()) return false;
686 for (Loop* lp = loop(); lp != NULL && lp->head() == this; lp = lp->parent())
687 if (lp->is_irreducible()) return false;
688 return true;
689 }
690
691 void print_value_on(outputStream* st) const PRODUCT_RETURN;
692 void print_on(outputStream* st) const PRODUCT_RETURN;
693 };
694
695 // Loop
696 class Loop : public ResourceObj {
697 private:
698 Loop* _parent;
699 Loop* _sibling; // List of siblings, null terminated
700 Loop* _child; // Head of child list threaded thru sibling pointer
701 Block* _head; // Head of loop
702 Block* _tail; // Tail of loop
703 bool _irreducible;
704 LocalSet _def_locals;
705
706 public:
707 Loop(Block* head, Block* tail) :
708 _head(head), _tail(tail),
709 _parent(NULL), _sibling(NULL), _child(NULL),
710 _irreducible(false), _def_locals() {}
711
712 Loop* parent() const { return _parent; }
713 Loop* sibling() const { return _sibling; }
714 Loop* child() const { return _child; }
715 Block* head() const { return _head; }
716 Block* tail() const { return _tail; }
717 void set_parent(Loop* p) { _parent = p; }
718 void set_sibling(Loop* s) { _sibling = s; }
719 void set_child(Loop* c) { _child = c; }
720 void set_head(Block* hd) { _head = hd; }
721 void set_tail(Block* tl) { _tail = tl; }
722
723 int depth() const; // nesting depth
724
725 // Returns true if lp is a nested loop or us.
726 bool contains(Loop* lp) const;
727 bool contains(Block* blk) const { return contains(blk->loop()); }
728
729 // Data flow on locals
730 LocalSet* def_locals() { return &_def_locals; }
731 const LocalSet* def_locals() const { return &_def_locals; }
732
733 // Merge the branch lp into this branch, sorting on the loop head
734 // pre_orders. Returns the new branch.
735 Loop* sorted_merge(Loop* lp);
736
737 // Mark non-single entry to loop
738 void set_irreducible(Block* entry) {
739 _irreducible = true;
740 entry->set_irreducible_entry(true);
741 }
742 bool is_irreducible() const { return _irreducible; }
743
744 bool is_root() const { return _tail->pre_order() == max_jint; }
745
746 void print(outputStream* st = tty, int indent = 0) const PRODUCT_RETURN;
747 };
748
749 // Postorder iteration over the loop tree.
750 class PostorderLoops : public StackObj {
751 private:
752 Loop* _root;
753 Loop* _current;
754 public:
755 PostorderLoops(Loop* root) : _root(root), _current(root) {
756 while (_current->child() != NULL) {
757 _current = _current->child();
758 }
759 }
760 bool done() { return _current == NULL; } // Finished iterating?
761 void next(); // Advance to next loop
762 Loop* current() { return _current; } // Return current loop.
763 };
764
765 // Preorder iteration over the loop tree.
766 class PreorderLoops : public StackObj {
767 private:
768 Loop* _root;
769 Loop* _current;
770 public:
771 PreorderLoops(Loop* root) : _root(root), _current(root) {}
772 bool done() { return _current == NULL; } // Finished iterating?
773 void next(); // Advance to next loop
774 Loop* current() { return _current; } // Return current loop.
775 };
776
777 // Standard indexes of successors, for various bytecodes.
778 enum {
779 FALL_THROUGH = 0, // normal control
780 IF_NOT_TAKEN = 0, // the not-taken branch of an if (i.e., fall-through)
781 IF_TAKEN = 1, // the taken branch of an if
782 GOTO_TARGET = 0, // unique successor for goto, jsr, or ret
783 SWITCH_DEFAULT = 0, // default branch of a switch
784 SWITCH_CASES = 1 // first index for any non-default switch branches
785 // Unlike in other blocks, the successors of a switch are listed uniquely.
786 };
787
788 private:
789 // A mapping from pre_order to Blocks. This array is created
790 // only at the end of the flow.
791 Block** _block_map;
792
793 // For each ciBlock index, a list of Blocks which share this ciBlock.
794 GrowableArray<Block*>** _idx_to_blocklist;
795 // count of ciBlocks
796 int _ciblock_count;
797
798 // Tells if a given instruction is able to generate an exception edge.
799 bool can_trap(ciBytecodeStream& str);
800
801 // Clone the loop heads. Returns true if any cloning occurred.
802 bool clone_loop_heads(Loop* lp, StateVector* temp_vector, JsrSet* temp_set);
803
804 // Clone lp's head and replace tail's successors with clone.
805 Block* clone_loop_head(Loop* lp, StateVector* temp_vector, JsrSet* temp_set);
806
807 public:
808 // Return the block beginning at bci which has a JsrSet compatible
809 // with jsrs.
810 Block* block_at(int bci, JsrSet* set, CreateOption option = create_public_copy);
811
812 // block factory
813 Block* get_block_for(int ciBlockIndex, JsrSet* jsrs, CreateOption option = create_public_copy);
814
815 // How many of the blocks have the backedge_copy bit set?
816 int backedge_copy_count(int ciBlockIndex, JsrSet* jsrs) const;
817
818 // Return an existing block containing bci which has a JsrSet compatible
819 // with jsrs, or NULL if there is none.
820 Block* existing_block_at(int bci, JsrSet* set) { return block_at(bci, set, no_create); }
821
822 // Tell whether the flow analysis has encountered an error of some sort.
823 bool failing() { return env()->failing() || _failure_reason != NULL; }
824
825 // Reason this compilation is failing, such as "too many basic blocks".
826 const char* failure_reason() { return _failure_reason; }
827
828 // Note a failure.
829 void record_failure(const char* reason);
830
831 // Return the block of a given pre-order number.
832 int have_block_count() const { return _block_map != NULL; }
833 int block_count() const { assert(have_block_count(), "");
834 return _next_pre_order; }
835 Block* pre_order_at(int po) const { assert(0 <= po && po < block_count(), "out of bounds");
836 return _block_map[po]; }
837 Block* start_block() const { return pre_order_at(start_block_num()); }
838 int start_block_num() const { return 0; }
839 Block* rpo_at(int rpo) const { assert(0 <= rpo && rpo < block_count(), "out of bounds");
840 return _block_map[rpo]; }
841 int next_pre_order() { return _next_pre_order; }
842 int inc_next_pre_order() { return _next_pre_order++; }
843
844 private:
845 // A work list used during flow analysis.
846 Block* _work_list;
847
848 // List of blocks in reverse post order
849 Block* _rpo_list;
850
851 // Next Block::_pre_order. After mapping, doubles as block_count.
852 int _next_pre_order;
853
854 // Are there more blocks on the work list?
855 bool work_list_empty() { return _work_list == NULL; }
856
857 // Get the next basic block from our work list.
858 Block* work_list_next();
859
860 // Add a basic block to our work list.
861 void add_to_work_list(Block* block);
862
863 // Prepend a basic block to rpo list.
864 void prepend_to_rpo_list(Block* blk) {
865 blk->set_rpo_next(_rpo_list);
866 _rpo_list = blk;
867 }
868
869 // Root of the loop tree
870 Loop* _loop_tree_root;
871
872 // State used for make_jsr_record
873 int _jsr_count;
874 GrowableArray<JsrRecord*>* _jsr_records;
875
876 public:
877 // Make a JsrRecord for a given (entry, return) pair, if such a record
878 // does not already exist.
879 JsrRecord* make_jsr_record(int entry_address, int return_address);
880
881 void set_loop_tree_root(Loop* ltr) { _loop_tree_root = ltr; }
882 Loop* loop_tree_root() { return _loop_tree_root; }
883
884 private:
885 // Get the initial state for start_bci:
886 const StateVector* get_start_state();
887
888 // Merge the current state into all exceptional successors at the
889 // current point in the code.
890 void flow_exceptions(GrowableArray<Block*>* exceptions,
891 GrowableArray<ciInstanceKlass*>* exc_klasses,
892 StateVector* state);
893
894 // Merge the current state into all successors at the current point
895 // in the code.
896 void flow_successors(GrowableArray<Block*>* successors,
897 StateVector* state);
898
899 // Interpret the effects of the bytecodes on the incoming state
900 // vector of a basic block. Push the changed state to succeeding
901 // basic blocks.
902 void flow_block(Block* block,
903 StateVector* scratch_state,
904 JsrSet* scratch_jsrs);
905
906 // Perform the type flow analysis, creating and cloning Blocks as
907 // necessary.
908 void flow_types();
909
910 // Perform the depth first type flow analysis. Helper for flow_types.
911 void df_flow_types(Block* start,
912 bool do_flow,
913 StateVector* temp_vector,
914 JsrSet* temp_set);
915
916 // Incrementally build loop tree.
917 void build_loop_tree(Block* blk);
918
919 // Create the block map, which indexes blocks in pre_order.
920 void map_blocks();
921
922 public:
923 // Perform type inference flow analysis.
924 void do_flow();
925
926 void print_on(outputStream* st) const PRODUCT_RETURN;
927
928 void rpo_print_on(outputStream* st) const PRODUCT_RETURN;
929 };
|