Mercurial > hg > truffle
annotate src/share/vm/c1/c1_ValueMap.cpp @ 4710:41406797186b
7113012: G1: rename not-fully-young GCs as "mixed"
Summary: Renamed partially-young GCs as mixed and fully-young GCs as young. Change all external output that includes those terms (GC log and GC ergo log) as well as any comments, fields, methods, etc. The changeset also includes very minor code tidying up (added some curly brackets).
Reviewed-by: johnc, brutisso
| author | tonyp |
|---|---|
| date | Fri, 16 Dec 2011 02:14:27 -0500 |
| parents | f95d63e2154a |
| children | f067b4e0e04b |
| rev | line source |
|---|---|
| 0 | 1 /* |
| 1972 | 2 * Copyright (c) 1999, 2010, 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" | |
| 29 #include "utilities/bitMap.inline.hpp" | |
| 0 | 30 |
| 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 } | |
| 128 | |
| 129 return f; | |
| 130 | |
| 131 } | |
| 132 } | |
| 133 } | |
| 134 | |
| 135 // x not found, so insert it | |
| 136 if (entry_count() >= size_threshold()) { | |
| 137 increase_table_size(); | |
| 138 } | |
| 139 int idx = entry_index(hash, size()); | |
| 140 _entries.at_put(idx, new ValueMapEntry(hash, x, nesting(), entry_at(idx))); | |
| 141 _entry_count++; | |
| 142 | |
| 143 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())); | |
| 144 } | |
| 145 | |
| 146 return x; | |
| 147 } | |
| 148 | |
| 149 | |
| 150 #define GENERIC_KILL_VALUE(must_kill_implementation) \ | |
| 151 NOT_PRODUCT(_number_of_kills++); \ | |
| 152 \ | |
| 153 for (int i = size() - 1; i >= 0; i--) { \ | |
| 154 ValueMapEntry* prev_entry = NULL; \ | |
| 155 for (ValueMapEntry* entry = entry_at(i); entry != NULL; entry = entry->next()) { \ | |
| 156 Value value = entry->value(); \ | |
| 157 \ | |
| 158 must_kill_implementation(must_kill, entry, value) \ | |
| 159 \ | |
| 160 if (must_kill) { \ | |
| 161 kill_value(value); \ | |
| 162 \ | |
| 163 if (prev_entry == NULL) { \ | |
| 164 _entries.at_put(i, entry->next()); \ | |
| 165 _entry_count--; \ | |
| 166 } else if (prev_entry->nesting() == nesting()) { \ | |
| 167 prev_entry->set_next(entry->next()); \ | |
| 168 _entry_count--; \ | |
| 169 } else { \ | |
| 170 prev_entry = entry; \ | |
| 171 } \ | |
| 172 \ | |
| 173 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())); \ | |
| 174 } else { \ | |
| 175 prev_entry = entry; \ | |
| 176 } \ | |
| 177 } \ | |
| 178 } \ | |
| 179 | |
| 180 #define MUST_KILL_MEMORY(must_kill, entry, value) \ | |
| 181 bool must_kill = value->as_LoadField() != NULL || value->as_LoadIndexed() != NULL; | |
| 182 | |
| 183 #define MUST_KILL_ARRAY(must_kill, entry, value) \ | |
| 184 bool must_kill = value->as_LoadIndexed() != NULL \ | |
| 185 && value->type()->tag() == type->tag(); | |
| 186 | |
| 187 #define MUST_KILL_FIELD(must_kill, entry, value) \ | |
| 188 /* ciField's are not unique; must compare their contents */ \ | |
| 189 LoadField* lf = value->as_LoadField(); \ | |
| 190 bool must_kill = lf != NULL \ | |
| 191 && lf->field()->holder() == field->holder() \ | |
| 192 && lf->field()->offset() == field->offset(); | |
| 193 | |
| 194 #define MUST_KILL_EXCEPTION(must_kill, entry, value) \ | |
| 195 assert(entry->nesting() < nesting(), "must not find bigger nesting than current"); \ | |
| 196 bool must_kill = (entry->nesting() == nesting() - 1); | |
| 197 | |
| 198 | |
| 199 void ValueMap::kill_memory() { | |
| 200 GENERIC_KILL_VALUE(MUST_KILL_MEMORY); | |
| 201 } | |
| 202 | |
| 203 void ValueMap::kill_array(ValueType* type) { | |
| 204 GENERIC_KILL_VALUE(MUST_KILL_ARRAY); | |
| 205 } | |
| 206 | |
| 207 void ValueMap::kill_field(ciField* field) { | |
| 208 GENERIC_KILL_VALUE(MUST_KILL_FIELD); | |
| 209 } | |
| 210 | |
| 211 void ValueMap::kill_exception() { | |
| 212 GENERIC_KILL_VALUE(MUST_KILL_EXCEPTION); | |
| 213 } | |
| 214 | |
| 215 | |
| 216 void ValueMap::kill_map(ValueMap* map) { | |
| 217 assert(is_global_value_numbering(), "only for global value numbering"); | |
| 218 _killed_values.set_union(&map->_killed_values); | |
| 219 } | |
| 220 | |
| 221 void ValueMap::kill_all() { | |
| 222 assert(is_local_value_numbering(), "only for local value numbering"); | |
| 223 for (int i = size() - 1; i >= 0; i--) { | |
| 224 _entries.at_put(i, NULL); | |
| 225 } | |
| 226 _entry_count = 0; | |
| 227 } | |
| 228 | |
| 229 | |
| 230 #ifndef PRODUCT | |
| 231 | |
| 232 void ValueMap::print() { | |
| 233 tty->print_cr("(size %d, entries %d, nesting %d)", size(), entry_count(), nesting()); | |
| 234 | |
| 235 int entries = 0; | |
| 236 for (int i = 0; i < size(); i++) { | |
| 237 if (entry_at(i) != NULL) { | |
| 238 tty->print(" %2d: ", i); | |
| 239 for (ValueMapEntry* entry = entry_at(i); entry != NULL; entry = entry->next()) { | |
| 240 Value value = entry->value(); | |
| 241 tty->print("%s %c%d (%s%d) -> ", value->name(), value->type()->tchar(), value->id(), is_killed(value) ? "x" : "", entry->nesting()); | |
| 242 entries++; | |
| 243 } | |
| 244 tty->print_cr("NULL"); | |
| 245 } | |
| 246 } | |
| 247 | |
| 248 _killed_values.print(); | |
| 249 assert(entry_count() == entries, "entry_count incorrect"); | |
| 250 } | |
| 251 | |
| 252 void ValueMap::reset_statistics() { | |
| 253 _number_of_finds = 0; | |
| 254 _number_of_hits = 0; | |
| 255 _number_of_kills = 0; | |
| 256 } | |
| 257 | |
| 258 void ValueMap::print_statistics() { | |
| 259 float hit_rate = 0; | |
| 260 if (_number_of_finds != 0) { | |
| 261 hit_rate = (float)_number_of_hits / _number_of_finds; | |
| 262 } | |
| 263 | |
| 264 tty->print_cr("finds:%3d hits:%3d kills:%3d hit rate: %1.4f", _number_of_finds, _number_of_hits, _number_of_kills, hit_rate); | |
| 265 } | |
| 266 | |
| 267 #endif | |
| 268 | |
| 269 | |
| 270 | |
| 271 class ShortLoopOptimizer : public ValueNumberingVisitor { | |
| 272 private: | |
| 273 GlobalValueNumbering* _gvn; | |
| 274 BlockList _loop_blocks; | |
| 275 bool _too_complicated_loop; | |
| 276 | |
| 277 // simplified access to methods of GlobalValueNumbering | |
| 278 ValueMap* current_map() { return _gvn->current_map(); } | |
| 279 ValueMap* value_map_of(BlockBegin* block) { return _gvn->value_map_of(block); } | |
| 280 | |
| 281 // implementation for abstract methods of ValueNumberingVisitor | |
| 282 void kill_memory() { _too_complicated_loop = true; } | |
| 283 void kill_field(ciField* field) { current_map()->kill_field(field); }; | |
| 284 void kill_array(ValueType* type) { current_map()->kill_array(type); }; | |
| 285 | |
| 286 public: | |
| 287 ShortLoopOptimizer(GlobalValueNumbering* gvn) | |
| 288 : _gvn(gvn) | |
| 289 , _loop_blocks(ValueMapMaxLoopSize) | |
| 290 , _too_complicated_loop(false) | |
| 291 { | |
| 292 } | |
| 293 | |
| 294 bool process(BlockBegin* loop_header); | |
| 295 }; | |
| 296 | |
| 297 | |
| 298 bool ShortLoopOptimizer::process(BlockBegin* loop_header) { | |
| 299 TRACE_VALUE_NUMBERING(tty->print_cr("** loop header block")); | |
| 300 | |
| 301 _too_complicated_loop = false; | |
| 302 _loop_blocks.clear(); | |
| 303 _loop_blocks.append(loop_header); | |
| 304 | |
| 305 for (int i = 0; i < _loop_blocks.length(); i++) { | |
| 306 BlockBegin* block = _loop_blocks.at(i); | |
| 307 TRACE_VALUE_NUMBERING(tty->print_cr("processing loop block B%d", block->block_id())); | |
| 308 | |
| 309 if (block->is_set(BlockBegin::exception_entry_flag)) { | |
| 310 // this would be too complicated | |
| 311 return false; | |
| 312 } | |
| 313 | |
| 314 // add predecessors to worklist | |
| 315 for (int j = block->number_of_preds() - 1; j >= 0; j--) { | |
| 316 BlockBegin* pred = block->pred_at(j); | |
| 317 | |
| 318 ValueMap* pred_map = value_map_of(pred); | |
| 319 if (pred_map != NULL) { | |
| 320 current_map()->kill_map(pred_map); | |
| 321 } else if (!_loop_blocks.contains(pred)) { | |
| 322 if (_loop_blocks.length() >= ValueMapMaxLoopSize) { | |
| 323 return false; | |
| 324 } | |
| 325 _loop_blocks.append(pred); | |
| 326 } | |
| 327 } | |
| 328 | |
| 329 // use the instruction visitor for killing values | |
| 330 for (Value instr = block->next(); instr != NULL; instr = instr->next()) { | |
| 331 instr->visit(this); | |
| 332 if (_too_complicated_loop) { | |
| 333 return false; | |
| 334 } | |
| 335 } | |
| 336 } | |
| 337 | |
| 338 TRACE_VALUE_NUMBERING(tty->print_cr("** loop successfully optimized")); | |
| 339 return true; | |
| 340 } | |
| 341 | |
| 342 | |
| 343 GlobalValueNumbering::GlobalValueNumbering(IR* ir) | |
| 344 : _current_map(NULL) | |
| 345 , _value_maps(ir->linear_scan_order()->length(), NULL) | |
| 346 { | |
| 347 TRACE_VALUE_NUMBERING(tty->print_cr("****** start of global value numbering")); | |
| 348 | |
| 349 ShortLoopOptimizer short_loop_optimizer(this); | |
| 350 int subst_count = 0; | |
| 351 | |
| 352 BlockList* blocks = ir->linear_scan_order(); | |
| 353 int num_blocks = blocks->length(); | |
| 354 | |
| 355 BlockBegin* start_block = blocks->at(0); | |
| 356 assert(start_block == ir->start() && start_block->number_of_preds() == 0 && start_block->dominator() == NULL, "must be start block"); | |
| 357 assert(start_block->next()->as_Base() != NULL && start_block->next()->next() == NULL, "start block must not have instructions"); | |
| 358 | |
| 359 // initial, empty value map with nesting 0 | |
| 360 set_value_map_of(start_block, new ValueMap()); | |
| 361 | |
| 362 for (int i = 1; i < num_blocks; i++) { | |
| 363 BlockBegin* block = blocks->at(i); | |
| 364 TRACE_VALUE_NUMBERING(tty->print_cr("**** processing block B%d", block->block_id())); | |
| 365 | |
| 366 int num_preds = block->number_of_preds(); | |
| 367 assert(num_preds > 0, "block must have predecessors"); | |
| 368 | |
| 369 BlockBegin* dominator = block->dominator(); | |
| 370 assert(dominator != NULL, "dominator must exist"); | |
| 371 assert(value_map_of(dominator) != NULL, "value map of dominator must exist"); | |
| 372 | |
| 373 // create new value map with increased nesting | |
| 374 _current_map = new ValueMap(value_map_of(dominator)); | |
| 375 | |
| 376 if (num_preds == 1) { | |
| 377 assert(dominator == block->pred_at(0), "dominator must be equal to predecessor"); | |
| 378 // nothing to do here | |
| 379 | |
| 380 } else if (block->is_set(BlockBegin::linear_scan_loop_header_flag)) { | |
| 381 // block has incoming backward branches -> try to optimize short loops | |
| 382 if (!short_loop_optimizer.process(block)) { | |
| 383 // loop is too complicated, so kill all memory loads because there might be | |
| 384 // stores to them in the loop | |
| 385 current_map()->kill_memory(); | |
| 386 } | |
| 387 | |
| 388 } else { | |
| 389 // only incoming forward branches that are already processed | |
| 390 for (int j = 0; j < num_preds; j++) { | |
| 391 BlockBegin* pred = block->pred_at(j); | |
| 392 ValueMap* pred_map = value_map_of(pred); | |
| 393 | |
| 394 if (pred_map != NULL) { | |
| 395 // propagate killed values of the predecessor to this block | |
| 396 current_map()->kill_map(value_map_of(pred)); | |
| 397 } else { | |
| 398 // kill all memory loads because predecessor not yet processed | |
| 399 // (this can happen with non-natural loops and OSR-compiles) | |
| 400 current_map()->kill_memory(); | |
| 401 } | |
| 402 } | |
| 403 } | |
| 404 | |
| 405 if (block->is_set(BlockBegin::exception_entry_flag)) { | |
| 406 current_map()->kill_exception(); | |
| 407 } | |
| 408 | |
| 409 TRACE_VALUE_NUMBERING(tty->print("value map before processing block: "); current_map()->print()); | |
| 410 | |
| 411 // visit all instructions of this block | |
| 412 for (Value instr = block->next(); instr != NULL; instr = instr->next()) { | |
| 413 assert(!instr->has_subst(), "substitution already set"); | |
| 414 | |
| 415 // check if instruction kills any values | |
| 416 instr->visit(this); | |
| 417 | |
| 418 if (instr->hash() != 0) { | |
| 419 Value f = current_map()->find_insert(instr); | |
| 420 if (f != instr) { | |
| 421 assert(!f->has_subst(), "can't have a substitution"); | |
| 422 instr->set_subst(f); | |
| 423 subst_count++; | |
| 424 } | |
| 425 } | |
| 426 } | |
| 427 | |
| 428 // remember value map for successors | |
| 429 set_value_map_of(block, current_map()); | |
| 430 } | |
| 431 | |
| 432 if (subst_count != 0) { | |
| 433 SubstitutionResolver resolver(ir); | |
| 434 } | |
| 435 | |
| 436 TRACE_VALUE_NUMBERING(tty->print("****** end of global value numbering. "); ValueMap::print_statistics()); | |
| 437 } |