Mercurial > hg > truffle
annotate src/share/vm/c1/c1_ValueMap.cpp @ 20543:e7d0505c8a30
8059758: Footprint regressions with JDK-8038423
Summary: Changes in JDK-8038423 always initialize (zero out) virtual memory used for auxiliary data structures. This causes a footprint regression for G1 in startup benchmarks. This is because they do not touch that memory at all, so the operating system does not actually commit these pages. The fix is to, if the initialization value of the data structures matches the default value of just committed memory (=0), do not do anything.
Reviewed-by: jwilhelm, brutisso
| author | tschatzl |
|---|---|
| date | Fri, 10 Oct 2014 15:51:58 +0200 |
| parents | 55fb97c4c58d |
| children | 4ca6dc0799b6 |
| rev | line source |
|---|---|
| 0 | 1 /* |
|
17467
55fb97c4c58d
8029233: Update copyright year to match last edit in jdk8 hotspot repository for 2013
mikael
parents:
9081
diff
changeset
|
2 * Copyright (c) 1999, 2013, Oracle and/or its affiliates. All rights reserved. |
| 0 | 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 * | |
|
1552
c18cbe5936b8
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
0
diff
changeset
|
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA |
|
c18cbe5936b8
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
0
diff
changeset
|
20 * or visit www.oracle.com if you need additional information or have any |
|
c18cbe5936b8
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
0
diff
changeset
|
21 * questions. |
| 0 | 22 * |
| 23 */ | |
| 24 | |
| 1972 | 25 #include "precompiled.hpp" |
| 26 #include "c1/c1_Canonicalizer.hpp" | |
| 27 #include "c1/c1_IR.hpp" | |
| 28 #include "c1/c1_ValueMap.hpp" | |
| 8860 | 29 #include "c1/c1_ValueStack.hpp" |
| 1972 | 30 #include "utilities/bitMap.inline.hpp" |
| 0 | 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 | |
| 96 entry = new ValueMapEntry(entry->hash(), entry->value(), entry->nesting(), NULL); | |
| 97 } | |
| 98 entry->set_next(new_entries.at(new_index)); | |
| 99 new_entries.at_put(new_index, entry); | |
| 100 new_entry_count++; | |
| 101 } | |
| 102 } | |
| 103 | |
| 104 _entries = new_entries; | |
| 105 _entry_count = new_entry_count; | |
| 106 } | |
| 107 | |
| 108 | |
| 109 Value ValueMap::find_insert(Value x) { | |
| 110 const intx hash = x->hash(); | |
| 111 if (hash != 0) { | |
| 112 // 0 hash means: exclude from value numbering | |
| 113 NOT_PRODUCT(_number_of_finds++); | |
| 114 | |
| 115 for (ValueMapEntry* entry = entry_at(entry_index(hash, size())); entry != NULL; entry = entry->next()) { | |
| 116 if (entry->hash() == hash) { | |
| 117 Value f = entry->value(); | |
| 118 | |
| 119 if (!is_killed(f) && f->is_equal(x)) { | |
| 120 NOT_PRODUCT(_number_of_hits++); | |
| 121 TRACE_VALUE_NUMBERING(tty->print_cr("Value Numbering: %s %c%d equal to %c%d (size %d, entries %d, nesting-diff %d)", x->name(), x->type()->tchar(), x->id(), f->type()->tchar(), f->id(), size(), entry_count(), nesting() - entry->nesting())); | |
| 122 | |
| 123 if (entry->nesting() != nesting() && f->as_Constant() == NULL) { | |
| 124 // non-constant values of of another block must be pinned, | |
| 125 // otherwise it is possible that they are not evaluated | |
| 126 f->pin(Instruction::PinGlobalValueNumbering); | |
| 127 } | |
|
4871
f067b4e0e04b
7090976: Eclipse/CDT causes a JVM crash while indexing C++ code
roland
parents:
1972
diff
changeset
|
128 assert(x->type()->tag() == f->type()->tag(), "should have same type"); |
| 0 | 129 |
| 130 return f; | |
| 131 | |
| 132 } | |
| 133 } | |
| 134 } | |
| 135 | |
| 136 // x not found, so insert it | |
| 137 if (entry_count() >= size_threshold()) { | |
| 138 increase_table_size(); | |
| 139 } | |
| 140 int idx = entry_index(hash, size()); | |
| 141 _entries.at_put(idx, new ValueMapEntry(hash, x, nesting(), entry_at(idx))); | |
| 142 _entry_count++; | |
| 143 | |
| 144 TRACE_VALUE_NUMBERING(tty->print_cr("Value Numbering: insert %s %c%d (size %d, entries %d, nesting %d)", x->name(), x->type()->tchar(), x->id(), size(), entry_count(), nesting())); | |
| 145 } | |
| 146 | |
| 147 return x; | |
| 148 } | |
| 149 | |
| 150 | |
| 151 #define GENERIC_KILL_VALUE(must_kill_implementation) \ | |
| 152 NOT_PRODUCT(_number_of_kills++); \ | |
| 153 \ | |
| 154 for (int i = size() - 1; i >= 0; i--) { \ | |
| 155 ValueMapEntry* prev_entry = NULL; \ | |
| 156 for (ValueMapEntry* entry = entry_at(i); entry != NULL; entry = entry->next()) { \ | |
| 157 Value value = entry->value(); \ | |
| 158 \ | |
| 159 must_kill_implementation(must_kill, entry, value) \ | |
| 160 \ | |
| 161 if (must_kill) { \ | |
| 162 kill_value(value); \ | |
| 163 \ | |
| 164 if (prev_entry == NULL) { \ | |
| 165 _entries.at_put(i, entry->next()); \ | |
| 166 _entry_count--; \ | |
| 167 } else if (prev_entry->nesting() == nesting()) { \ | |
| 168 prev_entry->set_next(entry->next()); \ | |
| 169 _entry_count--; \ | |
| 170 } else { \ | |
| 171 prev_entry = entry; \ | |
| 172 } \ | |
| 173 \ | |
| 174 TRACE_VALUE_NUMBERING(tty->print_cr("Value Numbering: killed %s %c%d (size %d, entries %d, nesting-diff %d)", value->name(), value->type()->tchar(), value->id(), size(), entry_count(), nesting() - entry->nesting())); \ | |
| 175 } else { \ | |
| 176 prev_entry = entry; \ | |
| 177 } \ | |
| 178 } \ | |
| 179 } \ | |
| 180 | |
| 181 #define MUST_KILL_MEMORY(must_kill, entry, value) \ | |
| 182 bool must_kill = value->as_LoadField() != NULL || value->as_LoadIndexed() != NULL; | |
| 183 | |
| 184 #define MUST_KILL_ARRAY(must_kill, entry, value) \ | |
| 185 bool must_kill = value->as_LoadIndexed() != NULL \ | |
| 186 && value->type()->tag() == type->tag(); | |
| 187 | |
| 188 #define MUST_KILL_FIELD(must_kill, entry, value) \ | |
| 189 /* ciField's are not unique; must compare their contents */ \ | |
| 190 LoadField* lf = value->as_LoadField(); \ | |
| 191 bool must_kill = lf != NULL \ | |
| 192 && lf->field()->holder() == field->holder() \ | |
|
6618
0bfcb7a3e12d
7171824: assert(_offset >= 1) failed: illegal call to offset()
roland
parents:
4871
diff
changeset
|
193 && (all_offsets || lf->field()->offset() == field->offset()); |
| 0 | 194 |
| 195 | |
| 196 void ValueMap::kill_memory() { | |
| 197 GENERIC_KILL_VALUE(MUST_KILL_MEMORY); | |
| 198 } | |
| 199 | |
| 200 void ValueMap::kill_array(ValueType* type) { | |
| 201 GENERIC_KILL_VALUE(MUST_KILL_ARRAY); | |
| 202 } | |
| 203 | |
|
6618
0bfcb7a3e12d
7171824: assert(_offset >= 1) failed: illegal call to offset()
roland
parents:
4871
diff
changeset
|
204 void ValueMap::kill_field(ciField* field, bool all_offsets) { |
| 0 | 205 GENERIC_KILL_VALUE(MUST_KILL_FIELD); |
| 206 } | |
| 207 | |
| 208 void ValueMap::kill_map(ValueMap* map) { | |
| 209 assert(is_global_value_numbering(), "only for global value numbering"); | |
| 210 _killed_values.set_union(&map->_killed_values); | |
| 211 } | |
| 212 | |
| 213 void ValueMap::kill_all() { | |
| 214 assert(is_local_value_numbering(), "only for local value numbering"); | |
| 215 for (int i = size() - 1; i >= 0; i--) { | |
| 216 _entries.at_put(i, NULL); | |
| 217 } | |
| 218 _entry_count = 0; | |
| 219 } | |
| 220 | |
| 221 | |
| 222 #ifndef PRODUCT | |
| 223 | |
| 224 void ValueMap::print() { | |
| 225 tty->print_cr("(size %d, entries %d, nesting %d)", size(), entry_count(), nesting()); | |
| 226 | |
| 227 int entries = 0; | |
| 228 for (int i = 0; i < size(); i++) { | |
| 229 if (entry_at(i) != NULL) { | |
| 230 tty->print(" %2d: ", i); | |
| 231 for (ValueMapEntry* entry = entry_at(i); entry != NULL; entry = entry->next()) { | |
| 232 Value value = entry->value(); | |
| 233 tty->print("%s %c%d (%s%d) -> ", value->name(), value->type()->tchar(), value->id(), is_killed(value) ? "x" : "", entry->nesting()); | |
| 234 entries++; | |
| 235 } | |
| 236 tty->print_cr("NULL"); | |
| 237 } | |
| 238 } | |
| 239 | |
| 240 _killed_values.print(); | |
| 241 assert(entry_count() == entries, "entry_count incorrect"); | |
| 242 } | |
| 243 | |
| 244 void ValueMap::reset_statistics() { | |
| 245 _number_of_finds = 0; | |
| 246 _number_of_hits = 0; | |
| 247 _number_of_kills = 0; | |
| 248 } | |
| 249 | |
| 250 void ValueMap::print_statistics() { | |
| 251 float hit_rate = 0; | |
| 252 if (_number_of_finds != 0) { | |
| 253 hit_rate = (float)_number_of_hits / _number_of_finds; | |
| 254 } | |
| 255 | |
| 256 tty->print_cr("finds:%3d hits:%3d kills:%3d hit rate: %1.4f", _number_of_finds, _number_of_hits, _number_of_kills, hit_rate); | |
| 257 } | |
| 258 | |
| 259 #endif | |
| 260 | |
| 261 | |
| 262 | |
| 263 class ShortLoopOptimizer : public ValueNumberingVisitor { | |
| 264 private: | |
| 265 GlobalValueNumbering* _gvn; | |
| 266 BlockList _loop_blocks; | |
| 267 bool _too_complicated_loop; | |
| 8860 | 268 bool _has_field_store[T_ARRAY + 1]; |
| 269 bool _has_indexed_store[T_ARRAY + 1]; | |
| 0 | 270 |
| 271 // simplified access to methods of GlobalValueNumbering | |
| 272 ValueMap* current_map() { return _gvn->current_map(); } | |
| 273 ValueMap* value_map_of(BlockBegin* block) { return _gvn->value_map_of(block); } | |
| 274 | |
| 275 // implementation for abstract methods of ValueNumberingVisitor | |
|
6618
0bfcb7a3e12d
7171824: assert(_offset >= 1) failed: illegal call to offset()
roland
parents:
4871
diff
changeset
|
276 void kill_memory() { _too_complicated_loop = true; } |
| 8860 | 277 void kill_field(ciField* field, bool all_offsets) { |
| 278 current_map()->kill_field(field, all_offsets); | |
| 279 assert(field->type()->basic_type() >= 0 && field->type()->basic_type() <= T_ARRAY, "Invalid type"); | |
| 280 _has_field_store[field->type()->basic_type()] = true; | |
| 281 } | |
| 282 void kill_array(ValueType* type) { | |
| 283 current_map()->kill_array(type); | |
| 284 BasicType basic_type = as_BasicType(type); assert(basic_type >= 0 && basic_type <= T_ARRAY, "Invalid type"); | |
| 285 _has_indexed_store[basic_type] = true; | |
| 286 } | |
| 0 | 287 |
| 288 public: | |
| 289 ShortLoopOptimizer(GlobalValueNumbering* gvn) | |
| 290 : _gvn(gvn) | |
| 291 , _loop_blocks(ValueMapMaxLoopSize) | |
| 292 , _too_complicated_loop(false) | |
| 293 { | |
| 8860 | 294 for (int i=0; i<= T_ARRAY; i++){ |
| 295 _has_field_store[i] = false; | |
| 296 _has_indexed_store[i] = false; | |
| 297 } | |
| 298 } | |
| 299 | |
| 300 bool has_field_store(BasicType type) { | |
| 301 assert(type >= 0 && type <= T_ARRAY, "Invalid type"); | |
| 302 return _has_field_store[type]; | |
| 303 } | |
| 304 | |
| 305 bool has_indexed_store(BasicType type) { | |
| 306 assert(type >= 0 && type <= T_ARRAY, "Invalid type"); | |
| 307 return _has_indexed_store[type]; | |
| 0 | 308 } |
| 309 | |
| 310 bool process(BlockBegin* loop_header); | |
| 311 }; | |
| 312 | |
| 8860 | 313 class LoopInvariantCodeMotion : public StackObj { |
| 314 private: | |
| 315 GlobalValueNumbering* _gvn; | |
| 316 ShortLoopOptimizer* _short_loop_optimizer; | |
| 317 Instruction* _insertion_point; | |
| 318 ValueStack * _state; | |
|
9081
84ab5667f290
8011706: specjvm2008 test xml.transform gets array bound exception with c1
roland
parents:
8860
diff
changeset
|
319 bool _insert_is_pred; |
| 8860 | 320 |
| 321 void set_invariant(Value v) const { _gvn->set_processed(v); } | |
| 322 bool is_invariant(Value v) const { return _gvn->is_processed(v); } | |
| 323 | |
| 324 void process_block(BlockBegin* block); | |
| 325 | |
| 326 public: | |
| 327 LoopInvariantCodeMotion(ShortLoopOptimizer *slo, GlobalValueNumbering* gvn, BlockBegin* loop_header, BlockList* loop_blocks); | |
| 328 }; | |
| 329 | |
| 330 LoopInvariantCodeMotion::LoopInvariantCodeMotion(ShortLoopOptimizer *slo, GlobalValueNumbering* gvn, BlockBegin* loop_header, BlockList* loop_blocks) | |
| 331 : _gvn(gvn), _short_loop_optimizer(slo) { | |
| 332 | |
| 333 TRACE_VALUE_NUMBERING(tty->print_cr("using loop invariant code motion loop_header = %d", loop_header->block_id())); | |
| 334 TRACE_VALUE_NUMBERING(tty->print_cr("** loop invariant code motion for short loop B%d", loop_header->block_id())); | |
| 335 | |
| 336 BlockBegin* insertion_block = loop_header->dominator(); | |
| 337 if (insertion_block->number_of_preds() == 0) { | |
| 338 return; // only the entry block does not have a predecessor | |
| 339 } | |
| 340 | |
| 341 assert(insertion_block->end()->as_Base() == NULL, "cannot insert into entry block"); | |
| 342 _insertion_point = insertion_block->end()->prev(); | |
|
9081
84ab5667f290
8011706: specjvm2008 test xml.transform gets array bound exception with c1
roland
parents:
8860
diff
changeset
|
343 _insert_is_pred = loop_header->is_predecessor(insertion_block); |
| 8860 | 344 |
| 345 BlockEnd *block_end = insertion_block->end(); | |
| 346 _state = block_end->state_before(); | |
| 347 | |
| 348 if (!_state) { | |
| 349 // If, TableSwitch and LookupSwitch always have state_before when | |
| 350 // loop invariant code motion happens.. | |
| 351 assert(block_end->as_Goto(), "Block has to be goto"); | |
| 352 _state = block_end->state(); | |
| 353 } | |
| 354 | |
| 355 // the loop_blocks are filled by going backward from the loop header, so this processing order is best | |
| 356 assert(loop_blocks->at(0) == loop_header, "loop header must be first loop block"); | |
| 357 process_block(loop_header); | |
| 358 for (int i = loop_blocks->length() - 1; i >= 1; i--) { | |
| 359 process_block(loop_blocks->at(i)); | |
| 360 } | |
| 361 } | |
| 362 | |
| 363 void LoopInvariantCodeMotion::process_block(BlockBegin* block) { | |
| 364 TRACE_VALUE_NUMBERING(tty->print_cr("processing block B%d", block->block_id())); | |
| 365 | |
| 366 Instruction* prev = block; | |
| 367 Instruction* cur = block->next(); | |
| 368 | |
| 369 while (cur != NULL) { | |
| 370 | |
| 371 // determine if cur instruction is loop invariant | |
| 372 // only selected instruction types are processed here | |
| 373 bool cur_invariant = false; | |
| 374 | |
| 375 if (cur->as_Constant() != NULL) { | |
| 376 cur_invariant = !cur->can_trap(); | |
| 377 } else if (cur->as_ArithmeticOp() != NULL || cur->as_LogicOp() != NULL || cur->as_ShiftOp() != NULL) { | |
| 378 assert(cur->as_Op2() != NULL, "must be Op2"); | |
| 379 Op2* op2 = (Op2*)cur; | |
| 380 cur_invariant = !op2->can_trap() && is_invariant(op2->x()) && is_invariant(op2->y()); | |
| 381 } else if (cur->as_LoadField() != NULL) { | |
| 382 LoadField* lf = (LoadField*)cur; | |
| 383 // deoptimizes on NullPointerException | |
|
9081
84ab5667f290
8011706: specjvm2008 test xml.transform gets array bound exception with c1
roland
parents:
8860
diff
changeset
|
384 cur_invariant = !lf->needs_patching() && !lf->field()->is_volatile() && !_short_loop_optimizer->has_field_store(lf->field()->type()->basic_type()) && is_invariant(lf->obj()) && _insert_is_pred; |
| 8860 | 385 } else if (cur->as_ArrayLength() != NULL) { |
| 386 ArrayLength *length = cur->as_ArrayLength(); | |
| 387 cur_invariant = is_invariant(length->array()); | |
| 388 } else if (cur->as_LoadIndexed() != NULL) { | |
| 389 LoadIndexed *li = (LoadIndexed *)cur->as_LoadIndexed(); | |
|
9081
84ab5667f290
8011706: specjvm2008 test xml.transform gets array bound exception with c1
roland
parents:
8860
diff
changeset
|
390 cur_invariant = !_short_loop_optimizer->has_indexed_store(as_BasicType(cur->type())) && is_invariant(li->array()) && is_invariant(li->index()) && _insert_is_pred; |
| 8860 | 391 } |
| 392 | |
| 393 if (cur_invariant) { | |
| 394 // perform value numbering and mark instruction as loop-invariant | |
| 395 _gvn->substitute(cur); | |
| 396 | |
| 397 if (cur->as_Constant() == NULL) { | |
| 398 // ensure that code for non-constant instructions is always generated | |
| 399 cur->pin(); | |
| 400 } | |
| 401 | |
| 402 // remove cur instruction from loop block and append it to block before loop | |
| 403 Instruction* next = cur->next(); | |
| 404 Instruction* in = _insertion_point->next(); | |
| 405 _insertion_point = _insertion_point->set_next(cur); | |
| 406 cur->set_next(in); | |
| 407 | |
| 408 // Deoptimize on exception | |
| 409 cur->set_flag(Instruction::DeoptimizeOnException, true); | |
| 410 | |
| 411 // Clear exception handlers | |
| 412 cur->set_exception_handlers(NULL); | |
| 413 | |
| 414 TRACE_VALUE_NUMBERING(tty->print_cr("Instruction %c%d is loop invariant", cur->type()->tchar(), cur->id())); | |
| 415 | |
| 416 if (cur->state_before() != NULL) { | |
| 417 cur->set_state_before(_state->copy()); | |
| 418 } | |
| 419 if (cur->exception_state() != NULL) { | |
| 420 cur->set_exception_state(_state->copy()); | |
| 421 } | |
| 422 | |
| 423 cur = prev->set_next(next); | |
| 424 | |
| 425 } else { | |
| 426 prev = cur; | |
| 427 cur = cur->next(); | |
| 428 } | |
| 429 } | |
| 430 } | |
| 0 | 431 |
| 432 bool ShortLoopOptimizer::process(BlockBegin* loop_header) { | |
| 433 TRACE_VALUE_NUMBERING(tty->print_cr("** loop header block")); | |
| 434 | |
| 435 _too_complicated_loop = false; | |
| 436 _loop_blocks.clear(); | |
| 437 _loop_blocks.append(loop_header); | |
| 438 | |
| 439 for (int i = 0; i < _loop_blocks.length(); i++) { | |
| 440 BlockBegin* block = _loop_blocks.at(i); | |
| 441 TRACE_VALUE_NUMBERING(tty->print_cr("processing loop block B%d", block->block_id())); | |
| 442 | |
| 443 if (block->is_set(BlockBegin::exception_entry_flag)) { | |
| 444 // this would be too complicated | |
| 445 return false; | |
| 446 } | |
| 447 | |
| 448 // add predecessors to worklist | |
| 449 for (int j = block->number_of_preds() - 1; j >= 0; j--) { | |
| 450 BlockBegin* pred = block->pred_at(j); | |
| 451 | |
| 8860 | 452 if (pred->is_set(BlockBegin::osr_entry_flag)) { |
| 453 return false; | |
| 454 } | |
| 455 | |
| 0 | 456 ValueMap* pred_map = value_map_of(pred); |
| 457 if (pred_map != NULL) { | |
| 458 current_map()->kill_map(pred_map); | |
| 459 } else if (!_loop_blocks.contains(pred)) { | |
| 460 if (_loop_blocks.length() >= ValueMapMaxLoopSize) { | |
| 461 return false; | |
| 462 } | |
| 463 _loop_blocks.append(pred); | |
| 464 } | |
| 465 } | |
| 466 | |
| 467 // use the instruction visitor for killing values | |
| 468 for (Value instr = block->next(); instr != NULL; instr = instr->next()) { | |
| 469 instr->visit(this); | |
| 470 if (_too_complicated_loop) { | |
| 471 return false; | |
| 472 } | |
| 473 } | |
| 474 } | |
| 475 | |
| 8860 | 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 | |
| 0 | 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) | |
| 8860 | 490 , _compilation(ir->compilation()) |
| 0 | 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 | |
| 8860 | 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 | |
| 0 | 509 // initial, empty value map with nesting 0 |
| 510 set_value_map_of(start_block, new ValueMap()); | |
| 511 | |
| 512 for (int i = 1; i < num_blocks; i++) { | |
| 513 BlockBegin* block = blocks->at(i); | |
| 514 TRACE_VALUE_NUMBERING(tty->print_cr("**** processing block B%d", block->block_id())); | |
| 515 | |
| 516 int num_preds = block->number_of_preds(); | |
| 517 assert(num_preds > 0, "block must have predecessors"); | |
| 518 | |
| 519 BlockBegin* dominator = block->dominator(); | |
| 520 assert(dominator != NULL, "dominator must exist"); | |
| 521 assert(value_map_of(dominator) != NULL, "value map of dominator must exist"); | |
| 522 | |
| 523 // create new value map with increased nesting | |
| 524 _current_map = new ValueMap(value_map_of(dominator)); | |
| 525 | |
| 8860 | 526 if (num_preds == 1 && !block->is_set(BlockBegin::exception_entry_flag)) { |
| 0 | 527 assert(dominator == block->pred_at(0), "dominator must be equal to predecessor"); |
| 528 // nothing to do here | |
| 529 | |
| 530 } else if (block->is_set(BlockBegin::linear_scan_loop_header_flag)) { | |
| 531 // block has incoming backward branches -> try to optimize short loops | |
| 532 if (!short_loop_optimizer.process(block)) { | |
| 533 // loop is too complicated, so kill all memory loads because there might be | |
| 534 // stores to them in the loop | |
| 535 current_map()->kill_memory(); | |
| 536 } | |
| 537 | |
| 538 } else { | |
| 539 // only incoming forward branches that are already processed | |
| 540 for (int j = 0; j < num_preds; j++) { | |
| 541 BlockBegin* pred = block->pred_at(j); | |
| 542 ValueMap* pred_map = value_map_of(pred); | |
| 543 | |
| 544 if (pred_map != NULL) { | |
| 545 // propagate killed values of the predecessor to this block | |
| 546 current_map()->kill_map(value_map_of(pred)); | |
| 547 } else { | |
| 548 // kill all memory loads because predecessor not yet processed | |
| 549 // (this can happen with non-natural loops and OSR-compiles) | |
| 550 current_map()->kill_memory(); | |
| 551 } | |
| 552 } | |
| 553 } | |
| 554 | |
| 8860 | 555 // phi functions are not linked in instructions list, so process them separateley |
| 556 for_each_phi_fun(block, phi, | |
| 557 set_processed(phi); | |
| 558 ); | |
| 0 | 559 |
| 560 TRACE_VALUE_NUMBERING(tty->print("value map before processing block: "); current_map()->print()); | |
| 561 | |
| 562 // visit all instructions of this block | |
| 563 for (Value instr = block->next(); instr != NULL; instr = instr->next()) { | |
| 564 // check if instruction kills any values | |
| 565 instr->visit(this); | |
| 8860 | 566 // perform actual value numbering |
| 567 substitute(instr); | |
| 0 | 568 } |
| 569 | |
| 570 // remember value map for successors | |
| 571 set_value_map_of(block, current_map()); | |
| 572 } | |
| 573 | |
| 8860 | 574 if (_has_substitutions) { |
| 0 | 575 SubstitutionResolver resolver(ir); |
| 576 } | |
| 577 | |
| 578 TRACE_VALUE_NUMBERING(tty->print("****** end of global value numbering. "); ValueMap::print_statistics()); | |
| 579 } | |
| 8860 | 580 |
| 581 void GlobalValueNumbering::substitute(Instruction* instr) { | |
| 582 assert(!instr->has_subst(), "substitution already set"); | |
| 583 Value subst = current_map()->find_insert(instr); | |
| 584 if (subst != instr) { | |
| 585 assert(!subst->has_subst(), "can't have a substitution"); | |
| 586 | |
| 587 TRACE_VALUE_NUMBERING(tty->print_cr("substitution for %d set to %d", instr->id(), subst->id())); | |
| 588 instr->set_subst(subst); | |
| 589 _has_substitutions = true; | |
| 590 } | |
| 591 set_processed(instr); | |
| 592 } |