1 /*
2 * Copyright (c) 1999, 2013, 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 *
29 #include "c1/c1_ValueStack.hpp"
30 #include "utilities/bitMap.inline.hpp"
31
32 #ifndef PRODUCT
33
34 int ValueMap::_number_of_finds = 0;
35 int ValueMap::_number_of_hits = 0;
36 int ValueMap::_number_of_kills = 0;
37
38 #define TRACE_VALUE_NUMBERING(code) if (PrintValueNumbering) { code; }
39
40 #else
41
42 #define TRACE_VALUE_NUMBERING(code)
43
44 #endif
45
46
47 ValueMap::ValueMap()
48 : _nesting(0)
49 , _entries(ValueMapInitialSize, NULL)
50 , _killed_values()
51 , _entry_count(0)
52 {
53 NOT_PRODUCT(reset_statistics());
54 }
55
56
57 ValueMap::ValueMap(ValueMap* old)
58 : _nesting(old->_nesting + 1)
59 , _entries(old->_entries.length())
60 , _killed_values()
61 , _entry_count(old->_entry_count)
62 {
63 for (int i = size() - 1; i >= 0; i--) {
64 _entries.at_put(i, old->entry_at(i));
65 }
66 _killed_values.set_from(&old->_killed_values);
67 }
68
69
70 void ValueMap::increase_table_size() {
71 int old_size = size();
72 int new_size = old_size * 2 + 1;
73
74 ValueMapEntryList worklist(8);
75 ValueMapEntryArray new_entries(new_size, NULL);
76 int new_entry_count = 0;
77
78 TRACE_VALUE_NUMBERING(tty->print_cr("increasing table size from %d to %d", old_size, new_size));
79
80 for (int i = old_size - 1; i >= 0; i--) {
81 ValueMapEntry* entry;
82 for (entry = entry_at(i); entry != NULL; entry = entry->next()) {
83 if (!is_killed(entry->value())) {
84 worklist.push(entry);
85 }
86 }
87
88 while (!worklist.is_empty()) {
89 entry = worklist.pop();
90 int new_index = entry_index(entry->hash(), new_size);
91
92 if (entry->nesting() != nesting() && new_entries.at(new_index) != entry->next()) {
93 // changing entries with a lower nesting than the current nesting of the table
94 // is not allowed because then the same entry is contained in multiple value maps.
95 // clone entry when next-pointer must be changed
469 instr->visit(this);
470 if (_too_complicated_loop) {
471 return false;
472 }
473 }
474 }
475
476 bool optimistic = this->_gvn->compilation()->is_optimistic();
477
478 if (UseLoopInvariantCodeMotion && optimistic) {
479 LoopInvariantCodeMotion code_motion(this, _gvn, loop_header, &_loop_blocks);
480 }
481
482 TRACE_VALUE_NUMBERING(tty->print_cr("** loop successfully optimized"));
483 return true;
484 }
485
486
487 GlobalValueNumbering::GlobalValueNumbering(IR* ir)
488 : _current_map(NULL)
489 , _value_maps(ir->linear_scan_order()->length(), NULL)
490 , _compilation(ir->compilation())
491 {
492 TRACE_VALUE_NUMBERING(tty->print_cr("****** start of global value numbering"));
493
494 ShortLoopOptimizer short_loop_optimizer(this);
495
496 BlockList* blocks = ir->linear_scan_order();
497 int num_blocks = blocks->length();
498
499 BlockBegin* start_block = blocks->at(0);
500 assert(start_block == ir->start() && start_block->number_of_preds() == 0 && start_block->dominator() == NULL, "must be start block");
501 assert(start_block->next()->as_Base() != NULL && start_block->next()->next() == NULL, "start block must not have instructions");
502
503 // method parameters are not linked in instructions list, so process them separateley
504 for_each_state_value(start_block->state(), value,
505 assert(value->as_Local() != NULL, "only method parameters allowed");
506 set_processed(value);
507 );
508
509 // initial, empty value map with nesting 0
|
1 /*
2 * Copyright (c) 1999, 2016, 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 *
29 #include "c1/c1_ValueStack.hpp"
30 #include "utilities/bitMap.inline.hpp"
31
32 #ifndef PRODUCT
33
34 int ValueMap::_number_of_finds = 0;
35 int ValueMap::_number_of_hits = 0;
36 int ValueMap::_number_of_kills = 0;
37
38 #define TRACE_VALUE_NUMBERING(code) if (PrintValueNumbering) { code; }
39
40 #else
41
42 #define TRACE_VALUE_NUMBERING(code)
43
44 #endif
45
46
47 ValueMap::ValueMap()
48 : _nesting(0)
49 , _entries(ValueMapInitialSize, ValueMapInitialSize, NULL)
50 , _killed_values()
51 , _entry_count(0)
52 {
53 NOT_PRODUCT(reset_statistics());
54 }
55
56
57 ValueMap::ValueMap(ValueMap* old)
58 : _nesting(old->_nesting + 1)
59 , _entries(old->_entries.length(), old->_entries.length(), NULL)
60 , _killed_values()
61 , _entry_count(old->_entry_count)
62 {
63 for (int i = size() - 1; i >= 0; i--) {
64 _entries.at_put(i, old->entry_at(i));
65 }
66 _killed_values.set_from(&old->_killed_values);
67 }
68
69
70 void ValueMap::increase_table_size() {
71 int old_size = size();
72 int new_size = old_size * 2 + 1;
73
74 ValueMapEntryList worklist(8);
75 ValueMapEntryArray new_entries(new_size, new_size, NULL);
76 int new_entry_count = 0;
77
78 TRACE_VALUE_NUMBERING(tty->print_cr("increasing table size from %d to %d", old_size, new_size));
79
80 for (int i = old_size - 1; i >= 0; i--) {
81 ValueMapEntry* entry;
82 for (entry = entry_at(i); entry != NULL; entry = entry->next()) {
83 if (!is_killed(entry->value())) {
84 worklist.push(entry);
85 }
86 }
87
88 while (!worklist.is_empty()) {
89 entry = worklist.pop();
90 int new_index = entry_index(entry->hash(), new_size);
91
92 if (entry->nesting() != nesting() && new_entries.at(new_index) != entry->next()) {
93 // changing entries with a lower nesting than the current nesting of the table
94 // is not allowed because then the same entry is contained in multiple value maps.
95 // clone entry when next-pointer must be changed
469 instr->visit(this);
470 if (_too_complicated_loop) {
471 return false;
472 }
473 }
474 }
475
476 bool optimistic = this->_gvn->compilation()->is_optimistic();
477
478 if (UseLoopInvariantCodeMotion && optimistic) {
479 LoopInvariantCodeMotion code_motion(this, _gvn, loop_header, &_loop_blocks);
480 }
481
482 TRACE_VALUE_NUMBERING(tty->print_cr("** loop successfully optimized"));
483 return true;
484 }
485
486
487 GlobalValueNumbering::GlobalValueNumbering(IR* ir)
488 : _current_map(NULL)
489 , _value_maps(ir->linear_scan_order()->length(), ir->linear_scan_order()->length(), NULL)
490 , _compilation(ir->compilation())
491 {
492 TRACE_VALUE_NUMBERING(tty->print_cr("****** start of global value numbering"));
493
494 ShortLoopOptimizer short_loop_optimizer(this);
495
496 BlockList* blocks = ir->linear_scan_order();
497 int num_blocks = blocks->length();
498
499 BlockBegin* start_block = blocks->at(0);
500 assert(start_block == ir->start() && start_block->number_of_preds() == 0 && start_block->dominator() == NULL, "must be start block");
501 assert(start_block->next()->as_Base() != NULL && start_block->next()->next() == NULL, "start block must not have instructions");
502
503 // method parameters are not linked in instructions list, so process them separateley
504 for_each_state_value(start_block->state(), value,
505 assert(value->as_Local() != NULL, "only method parameters allowed");
506 set_processed(value);
507 );
508
509 // initial, empty value map with nesting 0
|