1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/share/vm/c1/c1_ValueMap.cpp Wed Apr 27 01:25:04 2016 +0800
1.3 @@ -0,0 +1,592 @@
1.4 +/*
1.5 + * Copyright (c) 1999, 2013, Oracle and/or its affiliates. All rights reserved.
1.6 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
1.7 + *
1.8 + * This code is free software; you can redistribute it and/or modify it
1.9 + * under the terms of the GNU General Public License version 2 only, as
1.10 + * published by the Free Software Foundation.
1.11 + *
1.12 + * This code is distributed in the hope that it will be useful, but WITHOUT
1.13 + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
1.14 + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
1.15 + * version 2 for more details (a copy is included in the LICENSE file that
1.16 + * accompanied this code).
1.17 + *
1.18 + * You should have received a copy of the GNU General Public License version
1.19 + * 2 along with this work; if not, write to the Free Software Foundation,
1.20 + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
1.21 + *
1.22 + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
1.23 + * or visit www.oracle.com if you need additional information or have any
1.24 + * questions.
1.25 + *
1.26 + */
1.27 +
1.28 +#include "precompiled.hpp"
1.29 +#include "c1/c1_Canonicalizer.hpp"
1.30 +#include "c1/c1_IR.hpp"
1.31 +#include "c1/c1_ValueMap.hpp"
1.32 +#include "c1/c1_ValueStack.hpp"
1.33 +#include "utilities/bitMap.inline.hpp"
1.34 +
1.35 +#ifndef PRODUCT
1.36 +
1.37 + int ValueMap::_number_of_finds = 0;
1.38 + int ValueMap::_number_of_hits = 0;
1.39 + int ValueMap::_number_of_kills = 0;
1.40 +
1.41 + #define TRACE_VALUE_NUMBERING(code) if (PrintValueNumbering) { code; }
1.42 +
1.43 +#else
1.44 +
1.45 + #define TRACE_VALUE_NUMBERING(code)
1.46 +
1.47 +#endif
1.48 +
1.49 +
1.50 +ValueMap::ValueMap()
1.51 + : _nesting(0)
1.52 + , _entries(ValueMapInitialSize, NULL)
1.53 + , _killed_values()
1.54 + , _entry_count(0)
1.55 +{
1.56 + NOT_PRODUCT(reset_statistics());
1.57 +}
1.58 +
1.59 +
1.60 +ValueMap::ValueMap(ValueMap* old)
1.61 + : _nesting(old->_nesting + 1)
1.62 + , _entries(old->_entries.length())
1.63 + , _killed_values()
1.64 + , _entry_count(old->_entry_count)
1.65 +{
1.66 + for (int i = size() - 1; i >= 0; i--) {
1.67 + _entries.at_put(i, old->entry_at(i));
1.68 + }
1.69 + _killed_values.set_from(&old->_killed_values);
1.70 +}
1.71 +
1.72 +
1.73 +void ValueMap::increase_table_size() {
1.74 + int old_size = size();
1.75 + int new_size = old_size * 2 + 1;
1.76 +
1.77 + ValueMapEntryList worklist(8);
1.78 + ValueMapEntryArray new_entries(new_size, NULL);
1.79 + int new_entry_count = 0;
1.80 +
1.81 + TRACE_VALUE_NUMBERING(tty->print_cr("increasing table size from %d to %d", old_size, new_size));
1.82 +
1.83 + for (int i = old_size - 1; i >= 0; i--) {
1.84 + ValueMapEntry* entry;
1.85 + for (entry = entry_at(i); entry != NULL; entry = entry->next()) {
1.86 + if (!is_killed(entry->value())) {
1.87 + worklist.push(entry);
1.88 + }
1.89 + }
1.90 +
1.91 + while (!worklist.is_empty()) {
1.92 + entry = worklist.pop();
1.93 + int new_index = entry_index(entry->hash(), new_size);
1.94 +
1.95 + if (entry->nesting() != nesting() && new_entries.at(new_index) != entry->next()) {
1.96 + // changing entries with a lower nesting than the current nesting of the table
1.97 + // is not allowed because then the same entry is contained in multiple value maps.
1.98 + // clone entry when next-pointer must be changed
1.99 + entry = new ValueMapEntry(entry->hash(), entry->value(), entry->nesting(), NULL);
1.100 + }
1.101 + entry->set_next(new_entries.at(new_index));
1.102 + new_entries.at_put(new_index, entry);
1.103 + new_entry_count++;
1.104 + }
1.105 + }
1.106 +
1.107 + _entries = new_entries;
1.108 + _entry_count = new_entry_count;
1.109 +}
1.110 +
1.111 +
1.112 +Value ValueMap::find_insert(Value x) {
1.113 + const intx hash = x->hash();
1.114 + if (hash != 0) {
1.115 + // 0 hash means: exclude from value numbering
1.116 + NOT_PRODUCT(_number_of_finds++);
1.117 +
1.118 + for (ValueMapEntry* entry = entry_at(entry_index(hash, size())); entry != NULL; entry = entry->next()) {
1.119 + if (entry->hash() == hash) {
1.120 + Value f = entry->value();
1.121 +
1.122 + if (!is_killed(f) && f->is_equal(x)) {
1.123 + NOT_PRODUCT(_number_of_hits++);
1.124 + 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()));
1.125 +
1.126 + if (entry->nesting() != nesting() && f->as_Constant() == NULL) {
1.127 + // non-constant values of of another block must be pinned,
1.128 + // otherwise it is possible that they are not evaluated
1.129 + f->pin(Instruction::PinGlobalValueNumbering);
1.130 + }
1.131 + assert(x->type()->tag() == f->type()->tag(), "should have same type");
1.132 +
1.133 + return f;
1.134 +
1.135 + }
1.136 + }
1.137 + }
1.138 +
1.139 + // x not found, so insert it
1.140 + if (entry_count() >= size_threshold()) {
1.141 + increase_table_size();
1.142 + }
1.143 + int idx = entry_index(hash, size());
1.144 + _entries.at_put(idx, new ValueMapEntry(hash, x, nesting(), entry_at(idx)));
1.145 + _entry_count++;
1.146 +
1.147 + 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()));
1.148 + }
1.149 +
1.150 + return x;
1.151 +}
1.152 +
1.153 +
1.154 +#define GENERIC_KILL_VALUE(must_kill_implementation) \
1.155 + NOT_PRODUCT(_number_of_kills++); \
1.156 + \
1.157 + for (int i = size() - 1; i >= 0; i--) { \
1.158 + ValueMapEntry* prev_entry = NULL; \
1.159 + for (ValueMapEntry* entry = entry_at(i); entry != NULL; entry = entry->next()) { \
1.160 + Value value = entry->value(); \
1.161 + \
1.162 + must_kill_implementation(must_kill, entry, value) \
1.163 + \
1.164 + if (must_kill) { \
1.165 + kill_value(value); \
1.166 + \
1.167 + if (prev_entry == NULL) { \
1.168 + _entries.at_put(i, entry->next()); \
1.169 + _entry_count--; \
1.170 + } else if (prev_entry->nesting() == nesting()) { \
1.171 + prev_entry->set_next(entry->next()); \
1.172 + _entry_count--; \
1.173 + } else { \
1.174 + prev_entry = entry; \
1.175 + } \
1.176 + \
1.177 + 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())); \
1.178 + } else { \
1.179 + prev_entry = entry; \
1.180 + } \
1.181 + } \
1.182 + } \
1.183 +
1.184 +#define MUST_KILL_MEMORY(must_kill, entry, value) \
1.185 + bool must_kill = value->as_LoadField() != NULL || value->as_LoadIndexed() != NULL;
1.186 +
1.187 +#define MUST_KILL_ARRAY(must_kill, entry, value) \
1.188 + bool must_kill = value->as_LoadIndexed() != NULL \
1.189 + && value->type()->tag() == type->tag();
1.190 +
1.191 +#define MUST_KILL_FIELD(must_kill, entry, value) \
1.192 + /* ciField's are not unique; must compare their contents */ \
1.193 + LoadField* lf = value->as_LoadField(); \
1.194 + bool must_kill = lf != NULL \
1.195 + && lf->field()->holder() == field->holder() \
1.196 + && (all_offsets || lf->field()->offset() == field->offset());
1.197 +
1.198 +
1.199 +void ValueMap::kill_memory() {
1.200 + GENERIC_KILL_VALUE(MUST_KILL_MEMORY);
1.201 +}
1.202 +
1.203 +void ValueMap::kill_array(ValueType* type) {
1.204 + GENERIC_KILL_VALUE(MUST_KILL_ARRAY);
1.205 +}
1.206 +
1.207 +void ValueMap::kill_field(ciField* field, bool all_offsets) {
1.208 + GENERIC_KILL_VALUE(MUST_KILL_FIELD);
1.209 +}
1.210 +
1.211 +void ValueMap::kill_map(ValueMap* map) {
1.212 + assert(is_global_value_numbering(), "only for global value numbering");
1.213 + _killed_values.set_union(&map->_killed_values);
1.214 +}
1.215 +
1.216 +void ValueMap::kill_all() {
1.217 + assert(is_local_value_numbering(), "only for local value numbering");
1.218 + for (int i = size() - 1; i >= 0; i--) {
1.219 + _entries.at_put(i, NULL);
1.220 + }
1.221 + _entry_count = 0;
1.222 +}
1.223 +
1.224 +
1.225 +#ifndef PRODUCT
1.226 +
1.227 +void ValueMap::print() {
1.228 + tty->print_cr("(size %d, entries %d, nesting %d)", size(), entry_count(), nesting());
1.229 +
1.230 + int entries = 0;
1.231 + for (int i = 0; i < size(); i++) {
1.232 + if (entry_at(i) != NULL) {
1.233 + tty->print(" %2d: ", i);
1.234 + for (ValueMapEntry* entry = entry_at(i); entry != NULL; entry = entry->next()) {
1.235 + Value value = entry->value();
1.236 + tty->print("%s %c%d (%s%d) -> ", value->name(), value->type()->tchar(), value->id(), is_killed(value) ? "x" : "", entry->nesting());
1.237 + entries++;
1.238 + }
1.239 + tty->print_cr("NULL");
1.240 + }
1.241 + }
1.242 +
1.243 + _killed_values.print();
1.244 + assert(entry_count() == entries, "entry_count incorrect");
1.245 +}
1.246 +
1.247 +void ValueMap::reset_statistics() {
1.248 + _number_of_finds = 0;
1.249 + _number_of_hits = 0;
1.250 + _number_of_kills = 0;
1.251 +}
1.252 +
1.253 +void ValueMap::print_statistics() {
1.254 + float hit_rate = 0;
1.255 + if (_number_of_finds != 0) {
1.256 + hit_rate = (float)_number_of_hits / _number_of_finds;
1.257 + }
1.258 +
1.259 + tty->print_cr("finds:%3d hits:%3d kills:%3d hit rate: %1.4f", _number_of_finds, _number_of_hits, _number_of_kills, hit_rate);
1.260 +}
1.261 +
1.262 +#endif
1.263 +
1.264 +
1.265 +
1.266 +class ShortLoopOptimizer : public ValueNumberingVisitor {
1.267 + private:
1.268 + GlobalValueNumbering* _gvn;
1.269 + BlockList _loop_blocks;
1.270 + bool _too_complicated_loop;
1.271 + bool _has_field_store[T_ARRAY + 1];
1.272 + bool _has_indexed_store[T_ARRAY + 1];
1.273 +
1.274 + // simplified access to methods of GlobalValueNumbering
1.275 + ValueMap* current_map() { return _gvn->current_map(); }
1.276 + ValueMap* value_map_of(BlockBegin* block) { return _gvn->value_map_of(block); }
1.277 +
1.278 + // implementation for abstract methods of ValueNumberingVisitor
1.279 + void kill_memory() { _too_complicated_loop = true; }
1.280 + void kill_field(ciField* field, bool all_offsets) {
1.281 + current_map()->kill_field(field, all_offsets);
1.282 + assert(field->type()->basic_type() >= 0 && field->type()->basic_type() <= T_ARRAY, "Invalid type");
1.283 + _has_field_store[field->type()->basic_type()] = true;
1.284 + }
1.285 + void kill_array(ValueType* type) {
1.286 + current_map()->kill_array(type);
1.287 + BasicType basic_type = as_BasicType(type); assert(basic_type >= 0 && basic_type <= T_ARRAY, "Invalid type");
1.288 + _has_indexed_store[basic_type] = true;
1.289 + }
1.290 +
1.291 + public:
1.292 + ShortLoopOptimizer(GlobalValueNumbering* gvn)
1.293 + : _gvn(gvn)
1.294 + , _loop_blocks(ValueMapMaxLoopSize)
1.295 + , _too_complicated_loop(false)
1.296 + {
1.297 + for (int i=0; i<= T_ARRAY; i++){
1.298 + _has_field_store[i] = false;
1.299 + _has_indexed_store[i] = false;
1.300 + }
1.301 + }
1.302 +
1.303 + bool has_field_store(BasicType type) {
1.304 + assert(type >= 0 && type <= T_ARRAY, "Invalid type");
1.305 + return _has_field_store[type];
1.306 + }
1.307 +
1.308 + bool has_indexed_store(BasicType type) {
1.309 + assert(type >= 0 && type <= T_ARRAY, "Invalid type");
1.310 + return _has_indexed_store[type];
1.311 + }
1.312 +
1.313 + bool process(BlockBegin* loop_header);
1.314 +};
1.315 +
1.316 +class LoopInvariantCodeMotion : public StackObj {
1.317 + private:
1.318 + GlobalValueNumbering* _gvn;
1.319 + ShortLoopOptimizer* _short_loop_optimizer;
1.320 + Instruction* _insertion_point;
1.321 + ValueStack * _state;
1.322 + bool _insert_is_pred;
1.323 +
1.324 + void set_invariant(Value v) const { _gvn->set_processed(v); }
1.325 + bool is_invariant(Value v) const { return _gvn->is_processed(v); }
1.326 +
1.327 + void process_block(BlockBegin* block);
1.328 +
1.329 + public:
1.330 + LoopInvariantCodeMotion(ShortLoopOptimizer *slo, GlobalValueNumbering* gvn, BlockBegin* loop_header, BlockList* loop_blocks);
1.331 +};
1.332 +
1.333 +LoopInvariantCodeMotion::LoopInvariantCodeMotion(ShortLoopOptimizer *slo, GlobalValueNumbering* gvn, BlockBegin* loop_header, BlockList* loop_blocks)
1.334 + : _gvn(gvn), _short_loop_optimizer(slo) {
1.335 +
1.336 + TRACE_VALUE_NUMBERING(tty->print_cr("using loop invariant code motion loop_header = %d", loop_header->block_id()));
1.337 + TRACE_VALUE_NUMBERING(tty->print_cr("** loop invariant code motion for short loop B%d", loop_header->block_id()));
1.338 +
1.339 + BlockBegin* insertion_block = loop_header->dominator();
1.340 + if (insertion_block->number_of_preds() == 0) {
1.341 + return; // only the entry block does not have a predecessor
1.342 + }
1.343 +
1.344 + assert(insertion_block->end()->as_Base() == NULL, "cannot insert into entry block");
1.345 + _insertion_point = insertion_block->end()->prev();
1.346 + _insert_is_pred = loop_header->is_predecessor(insertion_block);
1.347 +
1.348 + BlockEnd *block_end = insertion_block->end();
1.349 + _state = block_end->state_before();
1.350 +
1.351 + if (!_state) {
1.352 + // If, TableSwitch and LookupSwitch always have state_before when
1.353 + // loop invariant code motion happens..
1.354 + assert(block_end->as_Goto(), "Block has to be goto");
1.355 + _state = block_end->state();
1.356 + }
1.357 +
1.358 + // the loop_blocks are filled by going backward from the loop header, so this processing order is best
1.359 + assert(loop_blocks->at(0) == loop_header, "loop header must be first loop block");
1.360 + process_block(loop_header);
1.361 + for (int i = loop_blocks->length() - 1; i >= 1; i--) {
1.362 + process_block(loop_blocks->at(i));
1.363 + }
1.364 +}
1.365 +
1.366 +void LoopInvariantCodeMotion::process_block(BlockBegin* block) {
1.367 + TRACE_VALUE_NUMBERING(tty->print_cr("processing block B%d", block->block_id()));
1.368 +
1.369 + Instruction* prev = block;
1.370 + Instruction* cur = block->next();
1.371 +
1.372 + while (cur != NULL) {
1.373 +
1.374 + // determine if cur instruction is loop invariant
1.375 + // only selected instruction types are processed here
1.376 + bool cur_invariant = false;
1.377 +
1.378 + if (cur->as_Constant() != NULL) {
1.379 + cur_invariant = !cur->can_trap();
1.380 + } else if (cur->as_ArithmeticOp() != NULL || cur->as_LogicOp() != NULL || cur->as_ShiftOp() != NULL) {
1.381 + assert(cur->as_Op2() != NULL, "must be Op2");
1.382 + Op2* op2 = (Op2*)cur;
1.383 + cur_invariant = !op2->can_trap() && is_invariant(op2->x()) && is_invariant(op2->y());
1.384 + } else if (cur->as_LoadField() != NULL) {
1.385 + LoadField* lf = (LoadField*)cur;
1.386 + // deoptimizes on NullPointerException
1.387 + 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;
1.388 + } else if (cur->as_ArrayLength() != NULL) {
1.389 + ArrayLength *length = cur->as_ArrayLength();
1.390 + cur_invariant = is_invariant(length->array());
1.391 + } else if (cur->as_LoadIndexed() != NULL) {
1.392 + LoadIndexed *li = (LoadIndexed *)cur->as_LoadIndexed();
1.393 + cur_invariant = !_short_loop_optimizer->has_indexed_store(as_BasicType(cur->type())) && is_invariant(li->array()) && is_invariant(li->index()) && _insert_is_pred;
1.394 + }
1.395 +
1.396 + if (cur_invariant) {
1.397 + // perform value numbering and mark instruction as loop-invariant
1.398 + _gvn->substitute(cur);
1.399 +
1.400 + if (cur->as_Constant() == NULL) {
1.401 + // ensure that code for non-constant instructions is always generated
1.402 + cur->pin();
1.403 + }
1.404 +
1.405 + // remove cur instruction from loop block and append it to block before loop
1.406 + Instruction* next = cur->next();
1.407 + Instruction* in = _insertion_point->next();
1.408 + _insertion_point = _insertion_point->set_next(cur);
1.409 + cur->set_next(in);
1.410 +
1.411 + // Deoptimize on exception
1.412 + cur->set_flag(Instruction::DeoptimizeOnException, true);
1.413 +
1.414 + // Clear exception handlers
1.415 + cur->set_exception_handlers(NULL);
1.416 +
1.417 + TRACE_VALUE_NUMBERING(tty->print_cr("Instruction %c%d is loop invariant", cur->type()->tchar(), cur->id()));
1.418 +
1.419 + if (cur->state_before() != NULL) {
1.420 + cur->set_state_before(_state->copy());
1.421 + }
1.422 + if (cur->exception_state() != NULL) {
1.423 + cur->set_exception_state(_state->copy());
1.424 + }
1.425 +
1.426 + cur = prev->set_next(next);
1.427 +
1.428 + } else {
1.429 + prev = cur;
1.430 + cur = cur->next();
1.431 + }
1.432 + }
1.433 +}
1.434 +
1.435 +bool ShortLoopOptimizer::process(BlockBegin* loop_header) {
1.436 + TRACE_VALUE_NUMBERING(tty->print_cr("** loop header block"));
1.437 +
1.438 + _too_complicated_loop = false;
1.439 + _loop_blocks.clear();
1.440 + _loop_blocks.append(loop_header);
1.441 +
1.442 + for (int i = 0; i < _loop_blocks.length(); i++) {
1.443 + BlockBegin* block = _loop_blocks.at(i);
1.444 + TRACE_VALUE_NUMBERING(tty->print_cr("processing loop block B%d", block->block_id()));
1.445 +
1.446 + if (block->is_set(BlockBegin::exception_entry_flag)) {
1.447 + // this would be too complicated
1.448 + return false;
1.449 + }
1.450 +
1.451 + // add predecessors to worklist
1.452 + for (int j = block->number_of_preds() - 1; j >= 0; j--) {
1.453 + BlockBegin* pred = block->pred_at(j);
1.454 +
1.455 + if (pred->is_set(BlockBegin::osr_entry_flag)) {
1.456 + return false;
1.457 + }
1.458 +
1.459 + ValueMap* pred_map = value_map_of(pred);
1.460 + if (pred_map != NULL) {
1.461 + current_map()->kill_map(pred_map);
1.462 + } else if (!_loop_blocks.contains(pred)) {
1.463 + if (_loop_blocks.length() >= ValueMapMaxLoopSize) {
1.464 + return false;
1.465 + }
1.466 + _loop_blocks.append(pred);
1.467 + }
1.468 + }
1.469 +
1.470 + // use the instruction visitor for killing values
1.471 + for (Value instr = block->next(); instr != NULL; instr = instr->next()) {
1.472 + instr->visit(this);
1.473 + if (_too_complicated_loop) {
1.474 + return false;
1.475 + }
1.476 + }
1.477 + }
1.478 +
1.479 + bool optimistic = this->_gvn->compilation()->is_optimistic();
1.480 +
1.481 + if (UseLoopInvariantCodeMotion && optimistic) {
1.482 + LoopInvariantCodeMotion code_motion(this, _gvn, loop_header, &_loop_blocks);
1.483 + }
1.484 +
1.485 + TRACE_VALUE_NUMBERING(tty->print_cr("** loop successfully optimized"));
1.486 + return true;
1.487 +}
1.488 +
1.489 +
1.490 +GlobalValueNumbering::GlobalValueNumbering(IR* ir)
1.491 + : _current_map(NULL)
1.492 + , _value_maps(ir->linear_scan_order()->length(), NULL)
1.493 + , _compilation(ir->compilation())
1.494 +{
1.495 + TRACE_VALUE_NUMBERING(tty->print_cr("****** start of global value numbering"));
1.496 +
1.497 + ShortLoopOptimizer short_loop_optimizer(this);
1.498 +
1.499 + BlockList* blocks = ir->linear_scan_order();
1.500 + int num_blocks = blocks->length();
1.501 +
1.502 + BlockBegin* start_block = blocks->at(0);
1.503 + assert(start_block == ir->start() && start_block->number_of_preds() == 0 && start_block->dominator() == NULL, "must be start block");
1.504 + assert(start_block->next()->as_Base() != NULL && start_block->next()->next() == NULL, "start block must not have instructions");
1.505 +
1.506 + // method parameters are not linked in instructions list, so process them separateley
1.507 + for_each_state_value(start_block->state(), value,
1.508 + assert(value->as_Local() != NULL, "only method parameters allowed");
1.509 + set_processed(value);
1.510 + );
1.511 +
1.512 + // initial, empty value map with nesting 0
1.513 + set_value_map_of(start_block, new ValueMap());
1.514 +
1.515 + for (int i = 1; i < num_blocks; i++) {
1.516 + BlockBegin* block = blocks->at(i);
1.517 + TRACE_VALUE_NUMBERING(tty->print_cr("**** processing block B%d", block->block_id()));
1.518 +
1.519 + int num_preds = block->number_of_preds();
1.520 + assert(num_preds > 0, "block must have predecessors");
1.521 +
1.522 + BlockBegin* dominator = block->dominator();
1.523 + assert(dominator != NULL, "dominator must exist");
1.524 + assert(value_map_of(dominator) != NULL, "value map of dominator must exist");
1.525 +
1.526 + // create new value map with increased nesting
1.527 + _current_map = new ValueMap(value_map_of(dominator));
1.528 +
1.529 + if (num_preds == 1 && !block->is_set(BlockBegin::exception_entry_flag)) {
1.530 + assert(dominator == block->pred_at(0), "dominator must be equal to predecessor");
1.531 + // nothing to do here
1.532 +
1.533 + } else if (block->is_set(BlockBegin::linear_scan_loop_header_flag)) {
1.534 + // block has incoming backward branches -> try to optimize short loops
1.535 + if (!short_loop_optimizer.process(block)) {
1.536 + // loop is too complicated, so kill all memory loads because there might be
1.537 + // stores to them in the loop
1.538 + current_map()->kill_memory();
1.539 + }
1.540 +
1.541 + } else {
1.542 + // only incoming forward branches that are already processed
1.543 + for (int j = 0; j < num_preds; j++) {
1.544 + BlockBegin* pred = block->pred_at(j);
1.545 + ValueMap* pred_map = value_map_of(pred);
1.546 +
1.547 + if (pred_map != NULL) {
1.548 + // propagate killed values of the predecessor to this block
1.549 + current_map()->kill_map(value_map_of(pred));
1.550 + } else {
1.551 + // kill all memory loads because predecessor not yet processed
1.552 + // (this can happen with non-natural loops and OSR-compiles)
1.553 + current_map()->kill_memory();
1.554 + }
1.555 + }
1.556 + }
1.557 +
1.558 + // phi functions are not linked in instructions list, so process them separateley
1.559 + for_each_phi_fun(block, phi,
1.560 + set_processed(phi);
1.561 + );
1.562 +
1.563 + TRACE_VALUE_NUMBERING(tty->print("value map before processing block: "); current_map()->print());
1.564 +
1.565 + // visit all instructions of this block
1.566 + for (Value instr = block->next(); instr != NULL; instr = instr->next()) {
1.567 + // check if instruction kills any values
1.568 + instr->visit(this);
1.569 + // perform actual value numbering
1.570 + substitute(instr);
1.571 + }
1.572 +
1.573 + // remember value map for successors
1.574 + set_value_map_of(block, current_map());
1.575 + }
1.576 +
1.577 + if (_has_substitutions) {
1.578 + SubstitutionResolver resolver(ir);
1.579 + }
1.580 +
1.581 + TRACE_VALUE_NUMBERING(tty->print("****** end of global value numbering. "); ValueMap::print_statistics());
1.582 +}
1.583 +
1.584 +void GlobalValueNumbering::substitute(Instruction* instr) {
1.585 + assert(!instr->has_subst(), "substitution already set");
1.586 + Value subst = current_map()->find_insert(instr);
1.587 + if (subst != instr) {
1.588 + assert(!subst->has_subst(), "can't have a substitution");
1.589 +
1.590 + TRACE_VALUE_NUMBERING(tty->print_cr("substitution for %d set to %d", instr->id(), subst->id()));
1.591 + instr->set_subst(subst);
1.592 + _has_substitutions = true;
1.593 + }
1.594 + set_processed(instr);
1.595 +}
